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

Точно неизвестно, кто изобрел наивный байесовский алгоритм. Он был упомянут без автора в 1973 году в учебнике по распознаванию паттернов, но распространение получил лишь в 1990-е, когда исследователи заметили, что, как ни странно, он часто бывает точнее, чем намного более сложные обучающиеся алгоритмы. В то время я был старшекурсником. Запоздало решил включить наивный байесовский алгоритм в свои эксперименты и был шокирован, потому что оказалось, что он работает лучше, чем все другие, которые я сравнивал. К счастью, было одно исключение — алгоритм, который я разрабатывал для дипломной работы, — иначе, наверное, я не писал бы эти строки.

Наивный байесовский алгоритм сейчас используется очень широко: на нем основаны, например, многие спам-фильтры. Это применение придумал Дэвид Хекерман, выдающийся ученый-байесовец, врач. Ему пришла в голову мысль, что к спаму надо относиться как к заболеванию, симптомы которого — слова в электронном письме. «Виагра» — это симптом, и «халява» тоже, а имя лучшего друга, вероятно, указывает, что письмо настоящее. Затем можно использовать наивный байесовский алгоритм для классификации писем на спам и не-спам, но только при условии, что спамеры генерируют свои письма путем произвольного выбора слова. Это, конечно, странное допущение, которое было бы верно, не будь у предложений ни синтаксиса, ни содержания. Но тем же летом Мехран Сахами[87], тогда еще студент Стэнфорда, попробовал применить этот подход во время стажировки в Microsoft Research, и все отлично сработало. Когда Билл Гейтс спросил Хекермана, как это может быть, тот ответил, что для выявления спама вникать в подробности сообщения не обязательно: достаточно просто уловить суть, посмотрев, какие слова оно содержит.

В простейших поисковых системах алгоритмы, довольно похожие на наивный байесовский, используются, чтобы определить, какие сайты выдавать в ответ на запрос. Основное различие в том, что вместо классификации на спам и не спам нужно определить, подходит сайт к запросу или не подходит. Список проблем прогнозирования, к которым был применен наивный байесовский алгоритм, можно продолжать бесконечно. Питер Норвиг, директор по исследованиям в Google, как-то рассказал, что у них этот подход используется шире всего, а ведь Google применяет машинное обучение везде где только можно. Несложно догадаться, почему наивный Байес приобрел в Google такую популярность. Даже не говоря о неожиданной точности, он позволяет легко увеличить масштаб. Обучение наивного байесовского классификатора сводится к простому подсчету, сколько раз каждый атрибут появляется с каждым классом, а это едва ли занимает больше времени, чем считывание данных с диска.

Наивный байесовский алгоритм в шутку можно использовать даже в большем масштабе, чем Google, и смоделировать с его помощью всю Вселенную. Действительно, если верить в существование всемогущего бога, можно создать модель Вселенной как обширного распределения, где все происходит независимо при условии божьей воли. Ловушка, конечно, в том, что божественный разум нам недоступен, но в главе 8 мы узнаем, как получать наивные байесовские модели, даже не зная классов примеров.

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

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

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

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

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