Оглавление

Байесовское машинное обучение

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

Бейсовский подход — это наиболее академичный взгляд на машинное обучение. Это и хорошо и плохо.

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

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

Обобщённый взгляд на машинное обучение

На самом деле, любые подходы к машинному обучению делают одно и тоже. У нас всегда есть две основных вещи:

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

Во-вторых, у нас есть набор обучающих данных.

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

Байесовский подход даёт точный численный критерий для решения этой задачи.

Классическая вероятность

С классической вероятностью мы часто имеем дело в физических и инженерных задачах. Тут всё просто, надо поставить много экспериментов и поделить количество «успехов» на количество экспериментов.

Это частотное понимание вероятности.

Скажем, если вы бросили монетку 100 раз и 49 раз выпал «орёл», то можно говорить, что вероятность выпадания «орла» близка к 49% (чем больше экспериментов, тем точнее мы оценим вероятность).

То есть тут у нас есть модель и мы хотим подсчитать вероятность какого-либо исхода. Это прямая задача.

Модель «монетка» очень проста: у неё две стороны и она не может встать на ребро.

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

Но, давайте обо всём по-порядку.

Пример обратной задачи со скрытой переменной и вероятностный подход к моделям

Чтобы показать, как это работает, давайте просто рассмотрим конкретную задачу.

Пусть у нас есть корзина с яблоками. Яблоки бывают красные и зелёные. Мы берём из корзины N яблок и видим R красных яблок и G зелёных. Естественно, R+G=N.

Конечно, этот наш опыт может быть повторен несколько раз. Но давайте ограничимся одним. Это упростит наши рассуждения и совсем не ограничит общность изложения.

Теперь мы хотим узнать, каков процент зелёных яблок, а каков красных. В корзине.

Переведём это на язык машинного обучения: у нас есть

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

Это ключевая идея всего подхода. Остальное — детали.

Теорема Байеса

Теорема Байеса очень проста. Она является очевидным тождеством, однако, это не умоляет её важность.

Напомню обозначения.

Теорема Байеса является следствием очевидного утверждения

p(a∧b) = p(a|b)p(b) = p(b|a)p(a)

То есть:

          p(b|a)p(a)
p(a|b) = ────────────
             p(b)

Естественно p(b) должно быть больше 0, но это и понятно, если b является невероятным событием, то и p(a|b) тоже невероятно.

Применим теорему Байеса к машинному обучению

Давайте обозначим наши данные — D, а наши гипотезы — h. Тогда нам надо найти вероятность гипотезы для наших данных p(h|D), которая по теореме Байеса равна:

          p(D|h)p(h)
p(h|D) = ────────────
             p(D)

Нас интересует только соотношение вероятностей, поэтому мы можем выкинуть из этого выражения p(D) (D не зависит от h) и p(h) (будем считать, что все гипотезы равновероятны; строго говоря, это не всегда так, мы ещё вернёмся к этому вопросу, но во многих случаях это справедливо).

Получается, что нам надо найти такую гипотезу h, для которой максимально p(D|h).

Говоря математическим языком, мы должны для каждой гипотезы вычислить её апостериорную вероятность и выбрать гипотезу, для которой эта вероятность максимальна.

Этот подход называется maximum a posteriori probability (MAP). Если строго следовать ему, то вы получите лучшую гипотезу. И это математически доказано.

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

Вернёмся к нашему примеру

Пока у нас нет ни конкретных данных, ни множества гипотез. Давайте же придумаем их.

Пусть мы вынули N=3 яблок: R=1 красных и G=2 зелёных.

Давайте выдвинем две гипотезы:

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

Немного комбинаторики

Обозначим количество красных и зелёных яблок в корзине: R₀ и G₀. Сколькими способами можно взять R яблок из R₀?

              R₀!
C(R₀, R) = ─────────
           (R₀-R)!R!

Это, знакомый многим, биномиальный коэффициент. То есть, если у нас есть 3 яблока, то мы можем вынуть из них 2 яблока тремя способами: ●●○, ●○●, ○●●. С(3,2)=3!/(1!·2!)=(1·2·3)/((1)·(1·2))=3. Если вы не знакомы с этой формулой — ничего страшного. Она не относится к Байсовскому подходу, а нужна лишь для решения нашей конкретной задачм.

Искомая вероятность тогда равна

                  C(R₀, R) · C(G₀, G)
p(R₀, R, G₀, G) = ───────────────────
                     C(R₀+G₀, R+G)

Осталось применить это к нашим гипотезам:

Гипотеза h₁: p(3, 7, 1, 2) = 0.525
Гипотеза h₂: p(7, 3, 1, 2) = 0.175

Видно, что побеждает первая гипотеза.

Расширяем набор гипотез: переобученность

Давайте не будем ограничиваться двумя гипотезами. Рассмотрим любые сочетания R₀ и G₀. (R и G оставим прежними).

У нас получится табличка:

     |G₀= 0      1      2      3      4      5      6      7
-----+--------------------------------------------------------
R₀=0 | 0      0      0      0      0      0      0      0
   1 | 0      0      1.0000 0.7500 0.6000 0.5000 0.4286 0.3750
   2 | 0      0      0.5000 0.6000 0.6000 0.5714 0.5357 0.5000
   3 | 0      0      0.3000 0.4500 0.5143 0.5357 0.5357 0.5250
   4 | 0      0      0.2000 0.3429 0.4286 0.4762 0.5000 0.5091
   5 | 0      0      0.1429 0.2679 0.3571 0.4167 0.4545 0.4773
   6 | 0      0      0.1071 0.2143 0.3000 0.3636 0.4091 0.4406
   7 | 0      0      0.0833 0.1750 0.2545 0.3182 0.3671 0.4038

Здесь видны даже две проблемы.

Меньшая: многие гипотезы имеют одинаковую вероятность (например (R₀=1, G₀=5) и (R₀=2 и G₀=5)). На больших данных этой проблемы обычно нет.

Но самая большая проблема: мы получили, что наилучшее решение — (R₀=1, G₀=2). Это решение столько же точно, сколь и бесполезно.

То есть машина нам сказала: раз вы вынули из корзины одно красное яблока и два зелёных, то, скорее всего, там и были одно красное и два зелёных.

Это действительно так. При этом раскладе у вас просто нет шанса вытащить из корзины что-то другое.

Машина права. Но нужен ли нам такой ответ? Очевидно, это не то, что мы ожидали.

Это и есть переобученность. Наш искусственный интеллект «зазубрил» обучающие данные. Скорее всего, он не в состоянии качественно решать задачи, но на все обучающие вопросы он безупречно выдаёт точный обучающий ответ.

Происходит это по двум основным причинам:

Первая, — у нас очень мало обучающих данных. Увеличение обучающего массива может дать положительный результат. Но этот ресурс не бесконечен. При достижении определённого размера, дальнейшее наращивание становится бессмысленным. Начинают играть роль шумы или просто неоднородность условий, при которых были собраны данные (ведь в реальной жизни ничто не вечно).

Вторая, — мы выбрали слишком широкий спектр гипотез. Мы решили, что возможно всё.

Мы можем сузить спектр гипотез. Фактически, это есть p(h), которую мы выкинули в начале. Чтобы сделать цифры наглядней, я не буду здесь использовать именно вероятность, но фактически, я сделаю именно этот учёт.

Допустим, мы откуда-то знаем, что в корзине можем быть только 6, 7 или 8 яблок. Вероятность других гипотез — 0. Тогда наша табличка принимает вид:

     |G₀= 0      1      2      3      4      5      6      7
-----+--------------------------------------------------------
R₀=0 | 0      0      0      0      0      0      0      0
   1 | 0      0      0      0      0      0.5000 0.4286 0.3750
   2 | 0      0      0      0      0.6000 0.5714 0.5357 0
   3 | 0      0      0      0.4500 0.5143 0.5357 0      0
   4 | 0      0      0.2000 0.3429 0.4286 0      0      0
   5 | 0      0      0.1429 0.2679 0      0      0      0
   6 | 0      0      0.1071 0      0      0      0      0
   7 | 0      0      0      0      0      0      0      0

Видно, что при этом условии выигрывает гипотеза (R₀=2, G₀=4). Так же видно, что (R₀=2, G₀=5) лишь чуть менее правдоподобна.

Это уже не плохой результат!

Подводные камни MAP-обучения

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

На самом деле, всё не совсем так радужно.

Обозначу только самые фундаментальные проблемы.

Во-первых. Честное Байесовское обучение предполагает, что вы вычислите вероятности всех возможных гипотез для всех обучающих данных. То есть, если у вас 1000 гипотез и 1000 обучающих патернов, то вам придётся рассчитать 1000000 апостериорых вероятностей. В реальной жизни, обычно, числа больше на порядки. Выполнить полный рассчёт просто невозможно.

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

Вторая важная проблема возникает при создании классификаторов на основе Байесовского обучения. Не вдаваясь в математику рассмотрим простой пример. Мы хотим решить: мужчина перед нами, или женщина. У нас есть 4 гипотезы. Их вероятности распределяются так:

p(Ж|h₁) = 0.2
p(Ж|h₂) = 0.2
p(Ж|h₃) = 0.2
p(М|h₄) = 0.4

Если мы выберем MAP-гипотезу, то это будет h₄. И она скажет нам, что перед нами мужчина. Однако, сумма остальных гипотез — 0.6, что больше, чем 0.4. То есть, следовало бы ответить, что перед нами женщина.

Проблема не в том, что Байесовсое обучение плохо. Просто в данном случае мы должны рассматривать не отдельные гипотезы, а все возможные сочетание гипотез. Тогда мы получим идеальный Байесовский классификатор. Основная его проблема даже не в том, как его получить, а уже в том, как его использовать. Ведь даже имея идеальный классификатор, чтобы им воспользоваться вам надо вычислить некую идеальную комбинацию всех гипотез! На помощь приходят различные статистические подходы. Такие как классификатор Гиббса.

Но обо всех этих вещах я, возможно, напишу отдельно.