Что такое байесовский подход

Учимся на опыте — байесовский путь

Издательство «Манн, Иванов и Фербер»/ISO Republic/Indicator.Ru

Сначала я должен сделать признание от имени всего статистического сообщества. Формальная основа для обучения на данных несколько запутанна. Несмотря на многочисленные попытки создать единую теорию статистических выводов, ни одна версия так и не была полностью принята. Неудивительно, что математики не любят преподавать статистику.

Мы уже познакомились с конкурирующими идеями Фишера и Неймана — Пирсона. Пришло время исследовать третий, байесовский подход к работе. Хотя он получил известность только в последнее пятидесятилетие, его базовые принципы восходят к далекому прошлому, фактически к преподобному Томасу Байесу, пресвитерианскому священнику и математику из Танбридж-Уэллса, занимавшемуся философией и теорией вероятностей.

Хорошая новость состоит в том, что байесовский подход открывает новые возможности для создания сложных данных.

Плохая — он означает, что вам придется отложить в сторону почти все, что вы узнали из этой и других книг об оценивании, доверительных интервалах, P-значениях, проверке гипотез и так далее.

В чем суть байесовского подхода?

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

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

Источник

Введение в Байесовские методы

В качестве введения

В настоящее время Байесовские методы получили достаточно широкое распространение и активно используются в самых различных областях знаний. Однако, к сожалению, не так много людей имеют представление о том, что же это такое и зачем это нужно. Одной из причин является отсутствие большого количества литературы на русском языке. Поэтому здесь попытаюсь изложить их принципы настолько просто, насколько смогу, начав с самых азов (прошу прощения, если кому-то это покажется слишком простым).

В дальнейшем я бы хотел перейти к непосредственно Байесовскому анализу и рассказать об обработке реальных данных и о, на мой взгляд, отличной альтернативе языку R (о нем немного писалось тут) — Python с модулем pymc. Лично мне Python кажется гораздо более понятным и логичным, чем R с пакетами JAGS и BUGS, к тому же Python дает гораздо большую свободу и гибкость (хотя в Python есть и свои трудности, но они преодолимы, да и в простом анализе встречаются нечасто).

Немного истории

В качестве краткой исторической справки скажу, что формула Байеса была опубликована аж в 1763 году спустя 2 года после смерти ее автора, Томаса Байеса. Однако, методы, использующие ее, получили действительно широкое распространение только к концу ХХ века. Это объясняется тем, что расчеты требуют определенных вычислительных затрат, и они стали возможны только с развитием информационных технологий.

О вероятности и теореме Байеса

Формула Байеса и все последующее изложение требует понимания вероятности. Подробнее о вероятности можно почитать на Википедии.
На практике вероятность наступления события есть частота наступления этого события, то есть отношение количества наблюдений события к общему количеству наблюдений при большом (теоретически бесконечном) общем количестве наблюдений.
Рассмотрим следующий эксперимент: мы называем любое число из отрезка [0, 1] и смотрим за тем, что это число будет между, например, 0.1 и 0.4. Как нетрудно догадаться, вероятность этого события будет равна отношению длины отрезка [0.1, 0.4] к общей длине отрезка [0, 1] (другими словами, отношение «количества» возможных равновероятных значений к общему «количеству» значений), то есть (0.4 — 0.1) / (1 — 0) = 0.3, то есть вероятность попадания в отрезок [0.1, 0.4] равна 30%.

Теперь посмотрим на квадрат [0, 1] x [0, 1].

Допустим, мы должны называть пары чисел (x, y), каждое из которых больше нуля и меньше единицы. Вероятность того, что x (первое число) будет в пределах отрезка [0.1, 0.4] (показан на первом рисунке как синяя область, на данный момент для нас второе число y не важно), равна отношению площади синей области к площади всего квадрата, то есть (0.4 — 0.1) * (1 — 0) / (1 * 1) = 0.3, то есть 30%. Таким образом можно записать, что вероятность того, что x принадлежит отрезку [0.1, 0.4] равна p(0.1

Источник

Анализ малых данных

КвазиНаучный блог Александра Дьяконова

Байесовский подход

В этом посте расскажем о формуле Байеса и её применении в машинном обучении. С этого года я буду читать много всяких новых курсов, в том числе, потоковый курс по «Машинному обучению и анализу данных» на факультете ВМК МГУ. Поэтому сейчас пребываю в поисках правильных формы/объёма/манеры подачи материала (чтобы не сильно лезть в теорию, но дать представление, зачем теория нужна). Постарался сделать максимально доступно, но предварительные знания по терверу нужны…

Формула Байеса хорошо известна из курса теории вероятностей и математической статистики и позволяет пересчитывать условную вероятность (или плотность) P(A|B) через P(B|A), см. рис. 1.

Рис. 1. Формула Байеса.

Прежде чем читать дальше полезно посмотреть этот небольшой пост, содержащий решение задачи «Тест на болезнь «зеленуху» имеет вероятность ошибки 0.1 (как позитивной, так и негативной), зеленухой болеет 10% населения. Какая вероятность того, что человек болен зеленухой, если у него позитивный результат теста (т.е. тест говорит «болен»)?» (а лучше попробовать самостоятельно решить эту задачу и потом проверить себя).

Кстати, задача решается очень просто графически, на рис. 2 показано множество всех людей в виде квадрата: левая часть (90%) — здоровые, правая часть (10%) — больные. Верхняя часть (90%) — те, у кого тест показывает верный результат, нижняя часть (10%) — те, у кого тест обманывает.

Рис. 2. Графическое решение задачи о зеленухе.

Розовым цветом выделено множество людей, у которых тест показывает «болен»: это больные с правильными показаниями и здоровые с ошибочными. Теперь видно, что эти две розовые группы «одного объёма». Поэтому, если тест показывает «болен», то с вероятностью 0.5 человек болен и тест верен, а с вероятностью 0.5 он здоров и тест ошибается.

Как видите, очень простое графическое решение — без всяких формул. На самом деле, почти все задачи в теории вероятностей можно решать вот так — на картинках, поскольку теория вероятностей — это часть теории меры, т.е. о том, как измерять «объём» множества, и если это множество умело изобразить, то и ответ будет понятен.

Оптимальное решение задач классификации

Предположим, что в задаче классификации на K классов мы знаем такие вероятности

— вероятности принадлежности к классам (conditional class probabilities), т.е. вероятности того, что объект принадлежит классу k при условии, что его признаковое описание x. Тогда очевидно, что для решения задачи классификации надо просто выбрать максимальную вероятность! Именно это и делает байесовский классификатор. Кстати, P может быть и плотностью (для них всё аналогично и даже формула Байеса верна, и дальше мы будем их часто «путать»).

Но как же вычислить указанные вероятности? Давайте воспользуемся формулой Байеса…

искомая вероятность выражается через априорную вероятность (prior probability) класса P(y=k) (смысл очевиден — если дан случайный объект, то с какой вероятностью он принадлежит классу k) и вероятность / плотность (density) распределения объектов класса P(x|y=k).

Смысл P(x|y=k) тоже понятен: если мы будем рассматривать только объекты класса k, то они как-то распределены… дискретное распределение описывается вероятностями, а непрерывное — плотностями. Здесь как раз стоит одна из таких функций, в которую мы подставили x (признаковое описание).

В знаменателе формулы стоит P(x) — это уже вероятность / плотность распределения всех объектов, но, по сути, она нам не очень нужна: выбор максимальной вероятности принадлежности к классам не зависит от этого значения.

Посмотрим на рис. 3 — розовая и синяя линии изображают плотности распределения двух классов в однопризнаковой задаче. Они могут быть заданы изначально, а могут быть восстановлены по данным (возможно, с некоторыми априорными предположениями, например, что данные распределены нормально). Если бы классы были равновероятны, то точки пересечения линий определяли бы «разделяющие поверхности классов» (да, у нас одномерное пространство, поэтому точки тут это «поверхности»).

Рис. 3. Плотности распределения в классах.

Но если классы не равновероятны, то эти самые вероятности классов по формуле Байеса «масштабируют» наши плотности и смещают разделяющие поверхности, см. рис. 4:

Рис. 4. Разделяющие точки для неравновероятных классов.

Можно подробно рассмотреть случай однопризнаковой задачи бинарной классификации с нормальными распределениями классов:

Здесь знак «<>» означает сравнение с целью определения максимального значения и классификации. В итоге (после логарифмирования) всё свелось к неравенству порядка не выше 2 (старшая степень при x). Если дисперсии распределений обоих классов равны, то для классификации мы будем значение признака просто сравнивать с порогом, что согласуется с рис. 5.

Рис. 5. Разделяющая точка в случае равных дисперсий.

Если дисперсии различны, то обязательно получится неравенство 2го порядка и здесь разделяющая поверхность состоит из 2х точек (см. рис. 4) или ни одной… если неравенство не имеет решения или решение — вся числовая прямая (это соответствует ситуации, когда какой-то класс очень редкий — вероятность принадлежности к нему близка к нулю).

Кстати, если классы равновероятны и нормально распределены с одинаковой дисперсией, то разделяющая поверхность — точка, которая является средним арифметическим матожиданий классов.

Рис. 6. Разделяющая точка в случае равновероятных классов и одинаковых дисперсий.

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

В различных библиотеках алгоритмов машинного обучения Вы встретите, скорее всего, реализацию наивного байесовского классификатора (naive Bayes). Связано это со сложностью оценки плотностей. Вероятность класса можно оценить пропорцией, в которой представители этого класса есть в обучающей выборке. А вот плотность распределения в классе в многомерном пространстве сложно оценить надёжно из-за проклятия размерности. Поэтому делают сильное предположение, что все признаки независимы, тогда плотность представляется в виде произведения плотностей по отдельным признакам:

Не смотря на то, что предположение сильное и на практике почти никогда не выполняется (если Вы сами не преобразуете признаки), метод часто работает неплохо… почему? Потому что поиск решения в классе простых решений — хороший способ борьбы с переобучением;)

Метод максимального правдоподобия (MLE)

Прежде чем описывать байесовский подход, вспомним самый популярный метод оценивания параметров в математической статистике — метод максимального правдоподобия. Если есть плотность (вероятность) распределения p(y|θ), известная с точностью до параметра θ, то для его оценки надо максимизировать функцию правдоподобия — произведение значений вероятностей в элементах нашей выборки (предполагаем, что они независимые и распределены по p(y|*), * — неизвестное нам истинное значение параметра θ):

Точка, в которой правдоподобие достигает максимального значения называется оценкой максимального правдоподобия (MLE = Maximum Likelihood Estimation). Кстати, будем держать в уме, что параметр θ может быть вектором (т.е. это параметры).

Рис. 7. Оценка максимального правдоподобия.

Приведём в качестве примера проблему нечестной монетки (coin-toss problem). Пусть кто-то бросает монету и мы наблюдаем исходы: 1 — выпал орёл, 0 — выпала решка. Наша задача оценить вероятность выпадения орла. Предполагая, что наблюдаемая случайная величина подчиняется распределению Бернулли, получаем:

Здесь вместо максимизации правдоподобия применили стандартный приём — максимизацию его логарифма. Максимум ищется просто приравниванием к нулю производной (функция вогнута). Я опускаю некоторые довольно простые выкладки. Получили достаточно очевидный ответ: оценка параметра распределения Бернулли (который и является вероятностью выпадения орла) — среднее арифметическое наблюдаемых случайных величин, т.е. доля выпадения орла.

Отметим недостатки полученной оценки:

А теперь подход, который одним махом исправит все эти недостатки;)

Байесовский подход

Перепишем формулу Байеса в терминах задачи моделирования данных и приведём нужные термины:

Апостериорная плотность именно то, что нам и нужно после наблюдения данных D. С помощью формулы Байеса мы видим, как наша априорная плотность (до наблюдения данных) превращается в апостериорную. Важно сразу понять, что формулу можно применять итерационно после поступления каждой новой порции данных. Текущее распределение параметра считается априорным, поступили данные — получили апостериорное распределение, потом, при необходимости, оно становится априорным для нового применения формулы.

Посмотрим, что даст применение байесовского подхода в задаче с монеткой… Допустим, у нас нет никаких априорных знаний о монетке, тогда считаем, что априорное распределение параметра равномерное p(θ)=1 на отрезке [0, 1]. Напомним, что это параметр распределения Бернулли и одновременно вероятность выпадения орла. Если был произведён ровно один бросок и выпал орёл, то правдоподобие p(y|θ) = θ. На рис. 8 показаны априорное распределение, правдоподобие и их произведение, нормированное так, чтобы получилась плотность (площадь под кривой равнялась единице): 1·θ / 0.5.

Рис. 8. Превращение априорного распределения в апостериорное после выпадения орла.

Теперь пусть наше априорное распределение это полученное апостериорное p(θ) = 2θ, т.е. мы верим, что скорее монета выпадает орлом, а не решкой. Пусть опять сделан ровно один бросок и выпала решка, тогда функция правдоподобия p(y|θ) = 1-θ, после применения формулы Байеса (перемножения и нормировки) получили апостериорную плотность p(θ|y) =6θ(1-θ)

Рис. 9. Превращение априорного распределение в апостериорное после выпадения решки.

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

Как ответить, какая вероятность выпадения орла? Мы получили целое распределение на возможных значениях этой вероятности. Можно найти моду (точку, в которой она максимальна) — это метод максимизации апостериорной плотности (MAP = Maximum a Posteriori). На рис. 9 это 0.5, что вполне логично после двух бросков и одного выпавшего орла. Давайте прологарифмируем формулу Байеса и запишем задачу максимизации:

(максимизация производится по θ, мы удалили слагаемое, которое от него не зависит).

Видно, что метод MAP максимизирует логарифм правдоподобия (как и MLE) плюс логарифм априорного распределения. Второе слагаемое играет роль своеобразного регуляризатора, которое позволяет не переобучаться (ниже покажем почему).

Задача с монеткой и MAP

Предположим, что априорное распределение на значения оцениваемого параметра распределения Бернулли — бета-распределение:

Если вдруг Вам показалось такое предположение странным и/или Вы вообще до этого не работали с бета-распределением, боитесь гамма-функций (но они тут только для вычислений нормировочных констант), то подождите немного, дальше будет понятно, почему выбрано именно оно. Пока скажем, что это довольно большой класс распределений, на рис. 10 показаны некоторые его представители

Рис. 10. Представители семейства бета-распределений.

Запишем выражение для максимизации методом MAP, возьмём производную и приравняем к нулю:

Интересно, что при α=β=1 оценки MLE и MAP совпадают. Если же α+β>2 и эти параметры целые, то по-сути они играют роль фиктивных экспериментов в количестве α+β-2 штук, в которых выпал α—1 орёл. Теперь оценка параметра будет адекватнее вести себя при малом числе экспериментов! Кстати, такая оценка часто называется сглаживанием Лапласа.

Почему же мы взяли бета-распределение? Всё дело в том, что если функцию правдоподобия для распределения Бернулли умножить на плотность бета-распределения, то мы снова получим бета-распределение:

Таким образом, мы не просто переходим от априорного распределения к апостериорному, а ещё и остаёмся в одном классе распределений! Да и вообще, все формулы красиво аналитически считаются… Распределения, которые не выводят из класса априорного распределения (как здесь Бернулли и бета), называются сопряжёнными.

С помощью бета-распределений удобно формализовать свою веру в то, что вероятность имеет определённое значение. Как мы видели, это вера будет просто эквивалентна серии фиктивных бросков. На рис. 11 показано несколько функций, которые формализуют априорную информацию о том, что θ=2/3.

Рис. 11. Представители бета-распределения с центром в точке 2/3.

Обоснование регуляризации

Вспомним статистическую теорию линейной регрессии. Пусть нам известно, что целевая переменная зависит от других линейно с точностью до нормального шума:

Тогда можно искать коэффициенты с помощью MLE:

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

Теперь давайте применим байесовский подход. До наблюдения обучающей выборки мы ничего не знаем о нашей модели, но мы можем сформулировать наши пожелания. Например, пусть неизвестные (а, следовательно, случайные) коэффициенты линейной регрессии будут нормально распределены:

В задаче минимизации мы оставили только слагаемые, которые зависят от w. Здесь легко узнаётся формула, которая используется в ридж-регрессии. Первое слагаемое — квадратичная ошибка, второе — член L2-регуляризации. Как мы и обещали, логарифм априорного распределения играет роль регуляризатора. Таким образом, мы доказали корректность регуляризации (фактически вывели её) в рамках рассматриваемых ограничений.

Рис. 12. Априорные и апостериорные распределения в задаче регрессии.

На рис. 12 показано, как априорная плотность «оттягивает» решение задачи MAP к нулю. MLE получает нерегуляризованное решение. С точки зрения байесовского подхода, регуляризация — априорное распределение параметров.

Отметим, что если бы коэффициенты линейной регрессии были распределены по Лапласу, то мы бы получили L1-регуляризацию. Обычно в ридж-регрессии при регуляризационном члене стоит параметр — коэффициент регуляризации. Здесь он тоже есть, более того, он теперь имеет теоретический смысл: это отношение дисперсий шума и априорного распределения параметров.

Вопрос для проверки понимания: а почему отношение, а не произведение? Аналогично можно было рассмотреть и логистическую регрессию. Там регуляризационный член добавляется к логлоссу.

Итак, байесовский подход теоретически обосновывает регуляризацию (мы привели один пример, но примеров много), придаёт используемым параметрам теоретический смысл.

Байесовский подход к машинному обучению

До сих пор мы говорили о нахождении параметров модели, т.е. фактически о машинном обучении (как известно, сама процедура обучения и есть не что иное, как настройка параметров). Вместо одного значения параметра мы научились находить целое распределение на множестве значений. Что с ним делать дальше, когда потребуется сделать классификацию (или регрессию) новых объектов? Итак, по формуле Байеса, в случае, когда у нас есть обучающая выборка (X, Y), мы получили распределение параметров

Если со штрихами обозначить тестовый объект, то

Здесь интегрирование проводится по распределению параметра модели w. Получается своеобразный ансамбль: мы используем модель сразу при всех значениях параметра! Правда, такое интегрирование не всегда удаётся выполнить, поэтому вместо него используют модель с параметром, который получается с помощью MAP-оценки:

Предположим, что параметр w сам, в свою очередь, зависит от некоторого параметра α. Тогда надо определить значение α. Воспользуемся опять формулой Байеса:

Правдоподобие параметра α

называется обоснованностью (evidence) — интегрированием мы просто исключаем переменную w. Принцип максимальной обоснованности состоит в том, чтобы найти значение параметра

и потом при классификации / регрессии использовать его. Именно так выводится метод Relevance Vector Machine (RVM). Метод похож на SVM, но вместо опорных векторов, которые находятся на границе классов, здесь решение зависит от «релевантных векторов», которые находятся «внутри класса». Часто это преподносится как большой плюс: при моделировании мы смотрим не на пограничные случаи, а на типичные. Желающие могут почитать классическую работу Типпинга (у которой уже почти 1000 цитирований).

Итак, байесовский подход позволяет получать новые методы машинного обучения!

Что такое случайность

В теории вероятностей есть два классических подхода к пониманию того, что такое случайность. Наиболее широко распространённый — частотный подход, который предполагает, что случайность – объективная неопределённость. Поэтому, чтобы установить истину, надо делать эксперименты… в пределе она и устанавливается, подобно тому, как частота выпадения орлов сходится к вероятности. Понятно, что MLE — классический метод частотников.

Второй подход, более распространённый среди специалистов по машинному обучению, — байесовский (Bayesian). Здесь случайность – мера нашего незнания, соответственно, эксперименты просто уменьшают незнание переходом от априорной информации к апостериорной. MAP — пример метода байесианцев. Заметьте, что даже параметры в распределениях здесь случайные (они же неизвестны!).

Второй подход кажется более общим и красивым (мы уже привели значительное число плюсов). Есть правда несколько «но»

На самом деле, я описал лишь 2/3 того, что хотел… но пост уже получился большим. Дочитал ли кто-нибудь до конца? Все пожелания и замечания оставляйте в комментариях.

Что почитать

П.С. В заключение несколько малоизвестных фактов.

1. Вы, наверное, видели изображение Томаса Байеса, см. рис.12

Рис. 12. Томас Байес или кто-то ещё…

Так вот, точно не известно, кто изображён на этом рисунке. По одной из гипотез — Байес. На самом деле, о его жизни мы знаем очень мало… например, точно не известен год (1701 или 1702) и место рождения (скорее всего, Hertfordshire).

2. Правильно фамилия учёного произносится [бейз], т.е. надо бы говорить «формула Бейза».

3. На википедии написано, что Байес опубликовал две работы. Одна из них «Divine Benevolence, or an Attempt to Prove That the Principal End of the Divine Providence and Government is the Happiness of His Creatures«. На самом деле, автор этой работы Джон Нун. По одной из гипотез — «Нун» это псевдоним Томаса Байеса.

Немного об основной идее этой работы. Это не математическая, а философская статья, в которой рассматривается проблема существования зла: как в мире, который создал Бог (а Бог есть добро), может существовать зло. Если кратко, то ответ прост — дело в нас (людях).

4. В том виде, в котором мы знаем формулу Байеса, её вывел не Байес, а Пьер-Симон Лаплас. Они с Байесом очень не похожи друг на друга. Например, Лаплас был атеистом, а Байес — священником.

5. Термин «байесовский» (Bayesian) впервые применил Рональд Фишер. Но в его лексиконе этот термин был ругательным. Он считал, что теория Байеса «должна быть полностью отвергнута».

Источник