В данной лекции я расскажу о том, каким образом идеи Томаса Байеса, английского математика и священника XVIII века, а также идеи Уильяма Оккама, английского монаха и философа XIV века, оказали огромное влияние на современную науку в XXI веке и легли в основу так называемых байесовских методов машинного обучения. Но давайте обо всем по порядку, сначала введем некоторые определения.
Машинное обучение — это математическая дисциплина, в рамках которой ищутся закономерности в эмпирических данных. На основе закономерностей, выявленных в эмпирических данных, потом можно строить прогнозы. Под данными подразумевается множество объектов, где каждый объект характеризуется своим признаковым описанием. Каждому объекту поставлено в соответствие некоторое выходное значение, которое обычно тоже представимо в виде вектора некоторых характеристик. Например, объект — это фотография, есть какие-то признаки, которые характеризуют эту фотографию, а выходное значение или метка — это какие-то классы предметов, которые на фотографии изображены.
Существует некоторая зависимость между объектом, то есть его признаковым описанием, и соответствующей выходной характеристикой, однако эта зависимость неизвестна. Единственное, что известно, ― это множество прецедентов, то есть пар «признаковое описание объекта и соответствующее значение выходной характеристики». По этому множеству, которое также называется обучающей выборкой, необходимо построить алгоритм прогнозирования или, как говорят, выбрать гипотезу так, чтобы мы могли для нового объекта из того же класса с хорошей точностью прогнозировать его выходные характеристики.
Для того чтобы характеризовать точность алгоритма прогнозирования, вводится специальный алгоритм качества, оценивающий ошибку прогнозирования. Понятно, что можно построить, опираясь на имеющуюся обучающуюся выборку, большое количество различных алгоритмов прогнозирования. Возникает естественный вопрос: какой именно алгоритм прогнозирования надо было бы выбрать для конкретных данных, для конкретной задачи? Кажется естественным следующее инженерное решение. Давайте переберем все возможные алгоритмы прогнозирования и выберем тот, который на обучающей выборке выдает самую маленькую ошибку, а лучше, если эта ошибка вообще будет равна нулю.
Однако, как показывает практика, такой подход не работает и зачастую приводит к так называемому эффекту переобучения. В предельном случае этот эффект можно описать следующим образом. Алгоритм запоминает все объекты из обучающей выборки. Когда приходит новый объект, то алгоритм сравнивает признаковое описание этого объекта с признаковыми описаниями объектов из обучающей выборки. Если для какого-то объекта из обучающей выборки эти признаковые описания совпадают, то в качестве прогноза выходных характеристик алгоритм выдает значения выходных характеристик объекта из обучающей выборки. Если в обучающей выборке не находится аналогичного объекта, алгоритм выдает произвольные выходные значения. Понятно, что при таком способе прогнозирования ошибка на обучающей выборке будет равна нулю. Однако так же очевидно, что если мы попытаемся применить этот алгоритм прогнозирования для какого-либо нового объекта, то точность прогноза его свойств будет очень плохой.
Возникает вопрос: как среди доступных алгоритмов прогнозирования выбрать тот, который и на новых объектах обеспечивал бы хорошую точность прогноза? Исследования показали, что все дело в так называемой сложности алгоритмов или, что фактически то же самое, сложности тех закономерностей, которые мы с помощью этих алгоритмов можем выявить в эмпирических данных. Оказывается, что чем сложнее эти закономерности, тем лучше мы можем приблизить, воспроизвести обучающую выборку, но при этом точность прогнозирования зачастую оказывается невысокой. Верно и обратное: позволив себе ошибку на обучающей выборке, мы оказываемся значительно более робастными в смысле точности прогноза на новых объектах, и ошибка прогноза оказывается достаточно малой. Таким образом, при выборе алгоритма прогнозирования необходимо соблюдать баланс между сложностью алгоритма прогнозирования и точностью, которую мы получаем в смысле прогноза объектов из обучающей выборки.
Впервые такого рода соображение было сформулировано в методологическом принципе, носящем название «бритва Оккама». Этот принцип может быть в кратком виде сформулирован: не надо множить сущности без необходимости. По сути, бритва Оккама сплошь и рядом встречается в повседневной жизни. Действительно, если на каком-то пустыре есть котлован, то, скорее всего, там стройка, а не упал метеорит или кто-то искал клад, вел раскопки — все эти события имеют очень маленькую вероятность. Соответственно, возникает вопрос: а как же все-таки найти компромисс между сложностью модели и точностью на обучающей выборке? Как определить, что такое сложность? Как измерить точность? Более того, учитывая, что эти две величины измеряются в разных единицах, то и сам компромисс как искать? Ответы на эти вопросы дает знаменитая формула Байеса.
Сначала рассмотрим житейский пример применения формулы Байеса. Допустим, вы собрались на пикник, однако с утра облачно. Известно, что облака появляются примерно в 40% случаев утром. С другой стороны, примерно в 50% случаев, если утром было облачно, потом идет дождь. При этом в среднем дождь идет три дня в месяц. Возникает вопрос: какова же вероятность того, что если мы пойдем на пикник, то нас застигнет дождь? Формула Байеса позволяет ответить на этот вопрос. Мы просто пересчитываем априорные вероятности событий, что сегодня будет дождь или с утра было облачно, в апостериорную вероятность события, что во время пикника будет дождь при условии, что утром было облачно. К слову сказать, в данном примере эта вероятность небольшая — всего 12,5%.
Вероятность можно трактовать как степень нашего незнания. Например, процессы, происходящие в атмосфере Земли, неслучайны, однако из-за большого числа факторов, которые сложно учесть, прогнозирование погоды носит вероятностный характер. Поэтому можно говорить о том, что вероятность — это выражение степени нашего незнания о том или ином феномене.
Далее оказывается, что между случайностью объекта и сложностью описания есть соответствие, которое было описано в рамках теории колмогоровской сложности, разработанной одним из величайших математиков XX столетия Андреем Николаевичем Колмогоровым. В основе теории лежит очень естественная идея: сложность объекта измеряется длиной его описания. Неудивительно, что какие-то действительно случайные события практически невозможно предсказать, и поэтому их описание будет очень сложным. Более того, точность алгоритма прогнозирования на обучающей выборке также можно выразить вероятностным образом, а именно с помощью так называемой функции правдоподобия. Она выражает степень нашей уверенности, что обучающая выборка была порождена каким-то определенным алгоритмом прогнозирования, какой-то определенной гипотезой.
Таким образом, задав априорное распределение на пространстве гипотез и подсчитав правдоподобие обучающей выборки для каждой из гипотез, мы можем подсчитать степень нашей уверенности в том, что каждая из гипотез может с хорошей точностью описать выборку, используя формулу Байеса. Используя оценку этой степени уверенности, мы фактически можем произвести выбор наиболее эффективной гипотезы для описания данных. При этом мы будем соблюдать компромисс между сложностью этой гипотезы и точностью представления обучающей выборки. Этот подход оказался весьма плодотворен и лег в основу байесовских методов машинного обучения.
Отметим, что описанный выше подход к решению задачи переобучения ― это не единственное преимущество использования байесовских методов. Одной из основных задач машинного обучения является построение прогноза, однако в приложениях очень важно зачастую не только получить прогноз, но и построить доверительный интервал для него. Например, если прогнозируется спрос на какой-либо товар, важно иметь еще и некоторые оценки нижней и верхней границ спроса. А это, в свою очередь, позволит проработать какие-то экономические сценарии и действия в случае их наступления. Байесовские методы позволяют эффективно измерять уровень неопределенности в данных и изменять этот уровень неопределенности в зависимости от того, какая информация содержится во вновь поступивших данных. Соответственно, они предоставляют инструменты для того, чтобы строить доверительные интервалы при подсчете прогнозов.
Рассмотрим другой, более продвинутый пример использования байесовских методов машинного обучения. Речь идет о так называемом децентрализованном обучении. В настоящее время мобильные устройства, такие как смартфоны, планшеты, активно используются людьми для коммуникации. Эти устройства за счет встроенных датчиков, таких как камера, GPS, акселерометр и другие, собирают очень большое количество информации, она конфиденциальна. При этом она очень полезна, и если бы на ее основе можно было бы построить различные предсказательные модели, то их потом можно было бы использовать в различных онлайн-сервисах ― например, для таргетированной рекламы, для отслеживания аномальных действий. То есть если произошла кража телефона, то это можно автоматически отследить.
Качество предсказательных моделей может быть существенно улучшено, если для их обучения использовать данные с нескольких мобильных устройств. Однако возникает проблема, что данные в силу их конфиденциальности нельзя пересылать с мобильного устройства на центральный сервер. Здесь возникает задача децентрализованного машинного обучения. Мы должны обучать модель таким образом, чтобы само обучение происходило на мобильных устройствах, а части финальной модели собирались уже на сервере. То есть пересылка данных с мобильного устройства на сервер запрещена, но при этом с мобильного устройства мы можем пересылать какую-то часть модели на сервер.
Формула Байеса выдает распределение вероятности тех или иных закономерностей, которые потенциально объясняют обучающую выборку. Соответственно, построив на каждом локальном мобильном устройстве свою вероятностную модель и используя формулу Байеса, на сервере мы эти вероятностные модели можем комбинировать, чтобы построить финальную предсказательную модель, и при этом информацию мы не потеряем.
