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

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

Томас Байес — английский священник, живший в XVIII веке, — сам того не подозревая, стал центром новой религии. Такой поворот может показаться удивительным, но стоит заметить, что то же самое произошло и с Иисусом: христианство в том виде, в котором мы его знаем, изобрел апостол Павел, а сам Иисус видел в себе вершину иудейской веры. Аналогично байесианство в привычном для нас виде было изобретено Пьер-Симоном де Лапласом — французом, родившимся на пять десятилетий позже Байеса. Байес был проповедником и первым описал новый подход к вероятностям, но именно Лаплас выразил его идеи в виде теоремы.

Лаплас, один из величайших математиков всех времен и народов, наверное, больше всего известен своей мечтой о ньютоновском детерминизме:

Разум, которому в каждый определенный момент были бы известны все силы, приводящие природу в движение, и положение всех тел, из которых она состоит, будь он также достаточно обширен, чтобы подвергнуть эти данные анализу, смог бы объять единым законом движение величайших тел Вселенной и мельчайшего атома; для такого разума ничего не было бы неясного и будущее существовало бы в его глазах точно так же, как прошлое.

Это забавно, поскольку Лаплас был отцом теории вероятностей, которая, как он полагал, представляла собой просто здравый смысл, сведенный к вычислениям. В сердце его исследований вероятности лежала озабоченность вопросом Юма. Откуда, например, мы знаем, что завтра взойдет солнце? Каждый день, вплоть до сегодняшнего, это происходило, но ведь нет никаких гарантий, что так будет и впредь. Ответ Лапласа состоит из двух частей. Первая — то, что мы теперь называем принципом безразличия или принципом недостаточного основания. Однажды — скажем, в начале времен, которое для Лапласа было приблизительно 5 тысяч лет назад, — мы просыпаемся, прекрасно проводим день, а вечером видим, что солнце заходит. Вернется ли оно? Мы никогда не видели восхода, и у нас нет причин полагать, что оно взойдет или не взойдет. Таким образом мы должны рассмотреть два одинаково вероятных сценария и сказать, что солнце снова взойдет с вероятностью 1⁄2. Но, продолжал Лаплас, если прошлое хоть как-то указывает на будущее, каждый день, когда солнце восходит, должен укреплять нашу уверенность, что так будет происходить и дальше. Спустя пять тысячелетий вероятность, что солнце завтра снова взойдет, должна быть очень близка единице, но не равняться ей, потому что полной уверенности никогда не будет. Из этого мысленного эксперимента Лаплас вывел свое так называемое правило следования, согласно которому вероятность, что солнце снова взойдет после n восходов, равна (n + 1) / (n + 2). Если n = 0, то это просто 1⁄2, а когда n увеличивается, растет и вероятность, стремясь к единице, когда n стремится к бесконечности.