Верховный алгоритм

Поначалу может показаться, что это не так, но наивный байесовский алгоритм тесно связан с перцептронами. Перцептрон добавляет веса, а байесов­ский алгоритм умножает вероятности, но, если логарифмировать, последнее сведется к первому. И то и другое можно рассматривать как обобщение простых правил «Если…, то…», где каждый предшественник может вносить больший или меньший вклад в вывод, вместо подхода «все или ничего». Этот факт — еще один пример глубокой связи между алгоритмами машинного обучения и намек на существование Верховного алгоритма. Вы можете не знать теорему Байеса (хотя теперь уже знаете), но в какой-то степени каждый из десяти миллиардов нейронов в вашем мозге — это ее крохотный частный случай.

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

От «Евгения Онегина» до Siri

В преддверии Первой мировой войны русский математик Андрей Марков опубликовал статью, где вероятности применялись, помимо всего прочего, к поэзии. В своей работе он моделировал классику русской литературы — пушкинского «Евгения Онегина» — с помощью подхода, который мы сейчас называем цепью Маркова. Вместо того чтобы предположить, что каждая буква сгенерирована случайно, независимо от остальных, Марков ввел абсолютный минимум последовательной структуры: допустил, что вероятность появления той или иной буквы зависит от буквы, непосредственно ей предшествующей. Он показал, что, например, гласные и согласные обычно чередуются, поэтому, если вы видите согласную, следующая буква (если игнорировать знаки пунктуации и пробелы) с намного большей вероят­ностью будет гласной, чем если бы буквы друг от друга не зависели. Может показаться, что это невеликое достижение, но до появления компьютеров требовалось много часов вручную подсчитывать символы, и идея была довольно новой. Если гласная_i — это булева переменная, которая верна, если i-я по счету буква «Евгения Онегина» — гласная, и неверна, если она согласная, можно представить модель Маркова как похожий на цепочку график со стрелками между узлами, указывающими на прямую зависимость между соответствующими переменными:

Марков сделал предположение (неверное, но полезное), что в каж­дом месте текста вероятности одинаковы. Таким образом нам нужно оценить только три вероятности: P(гласная₁ = верно); P(гласная_i+1 = верно | гласная_i = верно) и P(гласная_i+1 = верно | гласная_i = верно). (Поскольку сумма вероятностей равна единице, из этого можно сразу получить P(гласная₁ = ложно) и так далее.) Как и в случае наивного байесовского алгоритма, переменных можно взять сколько угодно, не опасаясь, что число вероятностей, которые надо оценить, пробьет потолок, однако теперь переменные зависят друг от друга.

Если измерять не только вероятность гласных в зависимости от согласных, но и вероятность следования друг за другом для всех букв алфавита, можно поиграть в генерирование новых текстов, имеющих ту же статистику, что и «Евгений Онегин»: выбирайте первую букву, потом вторую, исходя из первой, и так далее. Получится, конечно, полная чепуха, но, если мы поставим буквы в зависимость от нескольких предыдущих букв, а не от одной, текст начнет напоминать скорее бессвязную речь пьяного — местами разборчиво, хотя в целом бессмыслица. Все еще недостаточно, чтобы пройти тест Тьюринга, но модели вроде этой — ключевой компонент систем машинного перевода, например Google Translate, которые позволяют увидеть весь интернет на английском (или почти английском), независимо от того, на каком языке написана исходная страница.

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

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