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

Марков взвешивает доказательства

Байесовцы шли к мировому господству, но тут произошло нечто забавное. Ученые, пользующиеся байесовскими моделями, стали постоянно замечать, что результат получается лучше, если манипулировать вероятностями недозволенными методами. Например, возведение P(слова) в определенную степень улучшало точность распознавания речи, но тогда это переставало быть теоремой Байеса. Что произошло? Как оказалось, виновата ложная независимость допущений, которые делают порождающие модели. Благодаря упрощенной структуре графа модели становятся обучающимися и стоящи­ми сохранения, но тогда больше даст простое получение наилучших параметров для имеющейся задачи, независимо от того, представляют ли они собой вероятности. Настоящая сила, скажем, наивного байесовского алгоритма заключается в том, что он дает небольшой информативный набор свойств, на основании которого можно предсказать класс, а также быстрый надежный способ узнать соответствующие параметры. В спам-фильтре каждое свойство — это частота определенного слова в спаме, а соответствующий параметр — то, как часто оно встречается. То же самое для не-спама. Если смотреть с этой точки зрения, наивный байесовский алгоритм может оказаться оптимальным в том смысле, что он делает лучшие возможные предсказания, причем зачастую там, где независимость допущений сильно нарушена. Когда я это понял и в 1996 году опубликовал статью на эту тему, подозрение к наивному Байесу уменьшилось и его популярность выросла. Но это стало шагом на пути к модели другого рода, которая в последние два десятилетия все больше вытесняет байесовские сети из машинного обучения, — к сетям Маркова.

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

Как и байесовские сети, сети Маркова можно представить в виде графов, но вместо стрелок будут ненаправленные дуги. Когда две переменные со­единены, это значит, что они прямо зависят друг от друга, если появляются вместе в каком-то свойстве, как «медленная песня» и «песня в исполнении хип-хопера» в свойстве «медленная песня в исполнении хип-хопера».

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

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

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

Логика и вероятность: несчастная любовь

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

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

Байесовцы и символисты соглашаются, что априорные допущения неизбежны, но расходятся в том, какое априорное знание разрешено. Для байесов­цев знание выражается в априорном распределении по структуре и параметрам модели. Априорными параметрами в принципе может быть все что угодно, но, по иронии, байесовцы, как правило, выбирают неинформативные (например, приписывают всем гипотезам одну и ту же вероятность), потому что им так удобнее делать расчеты. И в любом случае люди не очень хорошо умеют оценивать вероятности. Что касается структуры, байесовские сети предполагают интуитивное инкорпорирование знаний: нарисуй стрелку из A в B, если думаешь, что A прямо вызывает B. Символисты намного гибче: можно дать алгоритму машинного обучения в качестве априорного знания все, что можно закодировать путем логики, а логикой можно закодировать практически все при условии, что это «все» — черно-белое.