Педро Домингос - Верховный алгоритм

Поэтому мы поступим так, как всегда стоит поступать: пойдем на компромисс. Нужно сделать упрощающие допущения, которые срежут количество подлежащих оценке вероятностей до уровня, с которым под силу справиться. Одно из простых и очень популярных допущений заключается в том, что все следствия данной причины независимы. Это значит, например, что наличие высокой температуры не вли­яет на вероятность кашля, если уже известно, что у больного грипп. Математически это значит, что P(температура, кашель | грипп) — просто P(температура | грипп) × P(кашель | грипп) . Получается, что и то и другое легко оценить на основании небольшого количества наблюдений. В предыдущем разделе мы уже сделали это для высокой температуры, и для кашля или любого другого симптома все будет так же. Необходимое количество наблюдений больше не растет экспоненциально с количеством симптомов. На самом деле оно вообще не растет.

Обратите внимание: речь идет о том, что высокая температура и кашель независимы не в принципе, а только при условии, что у больного грипп. Если неизвестно, есть грипп или нет, температура и кашель будут очень сильно коррелировать, поскольку вероятность кашля при высокой температуре намного выше. P(температура, кашель) не равно P(температура) × P(кашель) . Смысл в том, что если уже известно, что у больного грипп, то информация о высокой температуре не даст никакой дополнительной информации о том, есть ли у него кашель. Аналогично, если вы видите, что звезды гаснут, но не знаете, должно ли взойти солнце, ваши ожидания, что небо прояснится, должны возрасти. Но если вы уже знаете, что восход неизбежен, гаснущие звезды не важны.

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

Алгоритм машинного обучения, который применяет теорему Байеса и исходит из того, что следствия данной причины независимы, называется наивный байесовский классификатор. Дело в том, что такое допущение, прямо скажем, довольно наивное: в реальности температура увеличивает вероятность кашля, даже если уже известно, что у больного грипп, потому что она, например, повышает вероятность тяжелого гриппа. Однако машинное обучение — это искусство безнаказанно делать ложные допущения, а как заметил статистик Джордж Бокс, «все модели неверны, но некоторые полезны». Чрезмерно упрощенная модель, для оценки которой у вас есть достаточно данных, лучше, чем идеальная, для которой данных нет. Просто поразительно, насколько ошибочны и одновременно полезны бывают некоторые модели. Экономист Милтон Фридман в одном очень влиятельном эссе даже утверждал, что чрезмерно упрощенные теории — лучшие, при условии, что они дают точные предсказания: они объясняют больше с наименьшими усилиями. По-моему, это перебор, однако это хорошая иллюстрация того, что, вопреки Эйнштейну, наука часто развивается по принципу «упрощай до тех пор, пока это возможно, а потом упрости еще немного».

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

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

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

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

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