Верховный алгоритм. Как машинное обучение изменит наш мир - Педро Домингос Страница 50

PageRank — алгоритм, благодаря которому появился Google, — тоже представляет собой марковскую цепь. Идея Ларри Пейджа заключалась в том, что веб-страницы, к которым ведут много ссылок, вероятно, важнее, чем страницы, где их мало, а ссылки с важных страниц должны сами по себе считаться больше. Из-за этого возникает бесконечная регрессия, но и с ней можно справиться с помощью цепи Маркова. Представьте, что человек посещает один сайт за другим, случайно проходя по ссылкам. Состояния в этой цепи Маркова — это не символы, а веб-страницы, что увеличивает масштаб проблемы, однако математика все та же. Суммой баллов страницы тогда будет доля времени, которую человек на ней проводит, либо вероятность, что он окажется на этой странице после долгого блуждания вокруг нее.

Цепи Маркова появляются повсюду, это одна из самых активно изучаемых тем в математике, но это все еще сильно ограниченная разновидность вероятностных моделей. Сделать шаг вперед можно с помощью такой модели:

Состояния, как и ранее, образуют марковскую цепь, но мы их не видим, и надо вывести их из наблюдений. Это называется скрытой марковской моделью, сокращенно СММ (название немного неоднозначное, потому что скрыта не модель, а состояния). СММ — сердце систем распознавания речи, например Siri. В задачах такого рода скрытые состояния — это написанные слова, наблюдения — это звуки, которые слышит Siri, а цель — определить слова на основе звуков. В модели есть два элемента: вероятность следующего слова при известном текущем, как в цепи Маркова, и вероятность услышать различные звуки, когда произносят слово. (Как именно сделать такой вывод — интересная проблема, к которой мы обратимся после следующего раздела.)

Кроме Siri, вы используете СММ каждый раз, когда разговариваете по мобильному телефону. Дело в том, что ваши слова передаются по воздуху в виде потока битов, а биты при передаче искажаются. СММ определяет, какими они должны быть (скрытые состояния), на основе полученных данных (наблюдений), и, если испортилось не слишком много битов, у нее обычно все получается.

Скрытая марковская модель — любимый инструмент специалистов по вычислительной биологии. Белок представляет собой последовательность аминокислот, а ДНК — последовательность азотистых оснований. Если мы хотим предсказать, например, в какую трехмерную форму сложится белок, можно считать аминокислоты наблюдениями, а тип складывания в каждой точке — скрытым состоянием. Аналогично можно использовать СММ для определения мест в ДНК, где инициируется транскрипция генов, а также многих других свойств.

Если состояния и наблюдения — не дискретные, а непрерывные переменные, СММ превращается в так называемый фильтр Калмана ^[88]. Экономисты используют эти фильтры, чтобы убрать шум из временных рядов таких величин, как внутренний валовой продукт (ВВП), инфляция и безработица. «Истинные» значения ВВП — это скрытые состояния. На каждом временном отрезке истинное значение должно быть схоже и с наблюдаемым, и с предыдущим истинным значением, поскольку в экономике резкие скачки встречаются нечасто. Фильтр Калмана находит компромисс между этими условиями и позволяет получить более гладкую, но соответствующую наблюдениям кривую. Кроме того, фильтры Калмана не дают ракетам сбиться с курса, и без них человек не побывал бы на Луне.