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

Теорема Байеса полезна, потому что обычно известна вероятность следствий при данных причинах, а узнать хотим вероятность причин при данных следствиях. Например, мы знаем процент пациентов с гриппом, у которых повышена температура, но на самом деле нам нужно определить вероятность, что пациент с температурой болен гриппом. Теорема Байеса позволяет нам перейти от одного к другому. Ее значимость, однако, этим далеко не ограничивается. Для байесовцев эта невинно выглядящая формула — настоящее F = ma машинного обучения, основа, из которой вытекает множество результатов и практических применений. Каков бы ни был Верховный алгоритм, он должен быть «всего лишь» вычислительным воплощением теоремы Байеса. Я пишу «всего лишь» в кавычках, потому что применение теоремы Байеса в компьютерах оказалось дьявольски непростой задачей для всех проблем, кроме простейших. Скоро мы увидим почему.

Теорема Байеса как основа статистики и машинного обучения страдает не только от вычислительной сложности, но и от крайней противоречивости. Вы можете удивиться: разве она не прямое следствие идеи условной вероятности, как мы видели на примере гриппа? Действительно, с формулой как таковой ни у кого проблем не возникает. Противоречие заключается в том, как именно байесовцы получают вероятности, которые в нее включены, и что эти вероятности означают. Для большинства статистиков единственный допустимый способ оценки вероятностей — вычисление частоты соответствующего события. Например, вероятность гриппа равна 0,2, потому что им болело 20 из 100 обследованных пациентов. Это «частотная» интерпретация вероятности, и она дала название господствующему учению в статистике. Но обратите внимание, что в принципе безразличия Лапласа и в примере с восходом солнца мы просто высасываем вероятность из пальца. Чем оправдано априорное предположение, что вероятность восхода солнца равна одной второй, двум третьим или еще какой-то величине? На это байесов­цы отвечают, что вероятность — это не часто­та, а субъективная степень убежденности, поэтому вам решать, какая она будет, а байесов­ский вывод просто позволяет обновлять априорные убеждения после появления новых доказательств, чтобы получать апостериорные убеждения (это назы­вается «провернуть ручку Байеса»). Поклонники теоремы Байеса верят в эту идею с почти религиозным рвением и 200 лет выдерживают нападки и возражения. С появлением на сцене достаточно мощных компьютеров и больших наборов данных байесовский вывод начал брать верх.

Все модели неверны, но некоторые полезны

Настоящие врачи не диагностируют грипп на основе высокой температуры, а учитывают целый комплекс симптомов, включая боль в горле, кашель, насморк, головную боль, озноб и так далее. Поэтому, когда нам действительно надо вычислить по теореме Байеса P(грипп | температура, кашель, больное горло, насморк, головная боль, озноб, …), мы знаем, что эта вероятность пропорциональна P(температура, кашель, больное горло, насморк, головная боль, озноб, … | грипп). Но здесь мы сталкиваемся с проблемой. Как оценить эту вероятность? Если каждый симптом — булева переменная (он либо есть, либо нет) и врач учитывает n симптомов, у пациента может быть 2n комбинаций симптомов. Если у нас, скажем, 20 симптомов и база данных из 10 тысяч пациентов, мы увидим лишь малую долю из примерно миллиона возможных комбинаций. Еще хуже то, что для точной оценки вероятности конкретного сочетания симптомов нужны как минимум десятки его наблюдений, а это значит, что база данных должна включать десятки миллионов пациентов. Добавьте еще десяток симптомов, и нам понадобится больше пациентов, чем людей на Земле. Если симптомов сто и мы каким-то чудом получим такие данные, не хватит места на всех жестких дисках в мире, чтобы сохранить все эти вероятности. А если в кабинет войдет пациент с не встречавшимся ранее сочетанием симптомов, будет непонятно, как поставить ему диагноз. То есть мы столкнемся с давним врагом: комбинаторным взрывом.

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

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

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

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

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

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