Построение сложных вероятностных моделей22.11.2015 13:07

Математик Дмитрий Ветров о теореме Байеса, целях машинного обучения и сложных вероятностных моделях

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

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

Целью машинного обучения как раз и является выработка алгоритма прогнозирования, который позволил бы для произвольного объекта по его наблюдаемым переменным что-то сказать о скрытных переменных. В качестве исходного материала для анализа у нас есть так называемая обучающая выборка, то есть совокупность объектов, для которых и наблюдаемая, и скрытая компоненты известны. И, на первый взгляд, представляется крайне разумной следующая стратегия: давайте мы среди всего множества возможных алгоритмов прогнозирования выберем тот, который лучше всего работает на обучающей выборке, то есть для обучающих объектов, для которых нам известно значение скрытой переменной. Ее лучше всего предсказывать с наименьшей ошибкой, в идеале с нулевой. Идея на первый взгляд кажется разумной, и так, собственно, и стали поступать на заре машинного обучения и быстро столкнулись с явлением, получившим название «переобучение», или overfitting по-английски. В предельном случае оно выглядит следующим образом: наш алгоритм прогнозирования просто запоминает объекты обучающей выборки, и, когда на вход ему поступает некоторый произвольный объект — то есть значение наблюдаемых компонентов этого объекта — и требуется спрогнозировать его скрытые переменные, компьютер просто проверяет, встречал ли он объект с такими же наблюдаемыми компонентами в обучающей выборке. Если встречал, то выдает тот ответ, который был в обучающей выборке. Если не встречал — выдает случайный ответ, константу или отказывается от прогнозирования. Все три случая, очевидно, имеют нулевую практическую полезность, но формально алгоритм удовлетворяет своим требованиям — он имеет нулевую ошибку на обучающей выборке. Это явление называется переобучением.

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

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

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

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

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

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

Это на сегодняшний день является основным фронтом работ в области машинного обучения. И подобные все более и более сложные вероятностные модели уже находят применение и будут в ближайшие годы находить все больше применений в таких областях, как индивидуализированный веб-поиск, таргетированная реклама и рекомендательный сервис.

Дмитрий Ветров