10 Наивный Байес
10.1 Наивный Байесовский метод и условная независимость
Наивный байесовский метод (NB) - популярный метод классификации, который помогает при обсуждении условной независимости, переобучения и Байесовских методов. В NB мы формируем совместную модель наблюдений x и соответствующую метку класса c, используя сеть Убеждений вида
, Сеть Убеждений которого изображена на рис. 10.1а). В сочетании с подходящим выбором для каждого условного распределения p(xi |c), мы можем затем использовать правило Байеса для формирования классификатора для нового вектора атрибутов x; :
На практике принято рассматривать только два класса dom(c) = {0, 1}. Теория, которую мы описываем ниже, справедлива для любого числа классов c, хотя наши примеры ограничены случаем бинарного класса. Кроме того, атрибуты xi часто используются как двоичные, что мы и будем делать в дальнейшем. Расширение до более чем двух состояний атрибута, или непрерывных атрибутов, является в лоб\ простым.
Пример 47. EZsurvey.org считается, что слушателей Радиостанции удобно разделить на две группы: ‘молодой’ и ‘старый’. Они предполагают, что, учитывая, что клиент либо "молодой", либо "старый", этого достаточно, чтобы определить, понравится ли ему конкретная радиостанция, независимо от того, нравятся ему другие радиостанции или нет.:
где каждая из переменных R1, R2, R3, R4 может принимать значения "нравится" или "не нравится", а переменная "возраст" может принимать значение "молодой" или "старый". Таким образом, информация о возрасте клиента определяет индивидуальные предпочтения в отношении продукта без необходимости знать что-либо еще. Чтобы дополнить описание, учитывая, что клиент молод, у него есть 95% шансов понравиться Radio1, 5% - Radio2, 2% - Radio3 и 20% - Radio4. Аналогично, у старого слушателя есть 3% шансов понравиться Radio1, вероятность понравиться Radio2 составляет 82%, вероятность понравиться Radio3 - 34% и вероятность понравиться Radio4 — 92%. Они знают, что 90% слушателей - пожилые люди \старый\.
203 Оценка с использованием максимального правдоподобия
Рисунок 10.1: Наивный Байесовский классификатор. (а): Центральный предполагается, что для данного класса c атрибуты xi независимы. (b): Предполагая, что данные являются i.i.d. \единственно независимо распределёнными, метод Максимального Правдоподобия определяет оптимальные параметры распределения p(c) и зависящие от класса коэффициенты распределения p(xi |c).
Учитывая эту модель и нового клиента, которому нравятся Radio1 и Radio3, но не нравятся Radio2 и Radio4, какова вероятность того, что они молоды? Это задается через
Используя Наивную Байесовскую структуру, приведенный выше числитель обозначается как
Подставляя значения, мы получаем
0.95 ; 0.95 ; 0.02 ; 0.8 ; 0.1 = 0.0014
Знаменатель определяется этим значением плюс соответствующий член, вычисленный в предположении, что клиент является старым,
0.03 ; 0.18 ; 0.34 ; 0.08 ; 0.9 = 1.3219 ; 10-4
Что дает
10.2 Оценка с использованием Максимального Правдоподобия
Обучение записей таблицы для NB является простым применением более общего метода обучения BN, рассмотренного в разделе (9.2.3). Для полностью наблюдаемого набора данных обучение записей таблицы с Максимальной Вероятностью соответствует подсчету количества совпадений в тренируемых данных, как мы покажем ниже.
10.2.1 Двоичные атрибуты
Рассмотрим набор данных {xn , n = 1, . . . , N }, состоящий из двоичных атрибутов, xni ; {0, 1}, i = 1, . . . , D. Каждая точка данных xn имеет соответствующую метку класса cn . Число точек данных из класса c = 0 равно n0, а число из класса c = 1 обозначается как n1 . Для каждого атрибута из двух классов нам нужно оценить значения p(xi = 1|c) ; ;ic . Другая вероятность, p(xi = 0|c), определяется требованием нормализации, p(xi = 0|c) = 1 ; p(xi = 1|c) = 1 ; ;ic .
204 ПРЕДВАРИТЕЛЬНЫЙ вариант от 9 марта 2010 г. Оценки с использованием метода максимального правдоподобия
На основе предположения об условной независимости NB вероятность наблюдения вектора x может быть компактно записанна
В приведенном выше выражении xi равно либо 0, либо 1, и, следовательно, каждый i член вносит коэффициент ;ic, если xi = 1, или 1 ; ;ic, если xi = 0. Вместе с предположением о том, что обучающие\тренируемые\ данные генерируются путем ввода-вывода \независимо единственно распределёнными, i.i.d.\, логарифмическая вероятность атрибутов и меток классов равна
Это может быть записано более явно в терминах параметров в виде
Мы можем найти оптимальное значение ;ic Максимальной Вероятности, дифференцируя w.r.t. ;ic и приравнивая к нулю, что дает
Аналогично, оптимизируя уравнение (10.2.3) относительно p(c), получаем
Граница классификации
Мы классифицируем новые входные данные x; как класс 1, если
Используя правило Байеса и записав логарифм вышеприведенного выражения, это эквивалентно
Из определения классификатора следует, что это эквивалентно (константа нормализации ; log p(x; ) может быть опущена с обеих сторон)
Используя двоичную кодировку xi ; {0, 1}, мы классифицируем x; как класс 1, если
Это правило принятия решения может быть выражено в виде: классифицируйте x; как класс 1, если ;i wi x;i + a > 0 для некоторого подходящего выбора весовых коэффициентов wi и константы a смотрите упражнение(133). Интерпретация заключается в том, что w определяет гиперплоскость в пространстве атрибутов, а x; классифицируется как 1, если он лежит на положительной стороне гиперплоскости.
ЧЕРНОВИК от 9 марта 2010 г. 205 Оценка с использованием максимального правдоподобия
Рисунок 10.2: (а): вкусы Англичан по различным признакам (песочное печенье, светлое пиво, виски, овсянка, фрикадельки). В каждом столбце представлены вкусы отдельных людей. (b): вкусы Шотландцев.
Пример 48 (Они Шотландцы?). Рассмотрим следующий вектор атрибутов:
(любят песочное печенье, любят светлое пиво, пьют виски, едят овсянку, смотрели, как Англия играет в футбол) (10.2.12)
Вектор x = (1, 0, 1, 1, 0)T будет описывать, что человек любит песочное печенье, не любит светлое пиво, пьет виски, ест овсянку и не смотрел футбольный матч Англии. Вместе с каждым вектором x, имеется метка nat, описывающая национальность человека, dom(nat) = {шотландец, англичанин}, см. рис.10.2.
Мы хотим классифицировать вектор x = (1, 0, 1, 1, 0)T как шотландский или английский. Мы можем использовать правило Байеса для вычисления вероятности того, что x является Шотландцем или Англичанином:
По Максимальному Правдоподобию вероятность ‘предшествующего’ класса p (шотландский) определяется долей людей в базе данных есть Шотландцы, и аналогично, p(английский) задается как доля людей в базе данных, которые являются Англичанами. Это дает p(шотландский) = 7/13 и p(английский) = 6/13.
Для p(x|nat) в соответствии с Наивным Байесовским предположением:
так что, зная, является ли человек Шотландцем, нам не нужно знать ничего другого, чтобы рассчитать вероятность его симпатий и антипатий. Основываясь на таблице на рис.10.2 и используя Максимальную Вероятность, мы получаем:
p(x1 = 1|английский)
p(x1 = 1|шотландский)
Для x = (1, 0, 1, 1, 0)T мы получаем
Поскольку это значение больше 0,5, мы бы классифицировали этого человека как Шотландца.
Учёт небольших данных
В примере(48) рассмотрим попытку классификации вектора x = (0, 1, 1, 1, 1)T . В обучающих данных все Шотландские люди говорят, что им нравится песочное печенье. Это означает, что для данного конкретного случая x, p(x, шотландское) = 0, и, следовательно, мы используем чрезвычайно надежную классификацию p(шотландское|x) = 0. Это демонстрирует сложность использования Максимального Правдоподобия при скудных данных. Один из способов улучшить это - сгладить вероятности, например, добавив некоторое небольшое число к частоте каждого атрибута. Это гарантирует, что
206 ПРЕДВАРИТЕЛЬНАЯ от 9 марта 2010 г. Оценка с использованием метода максимального правдоподобия
в модели нет нулевых вероятностей. Альтернативой является использование Байесовского подхода, который не допускает экстремальных вероятностей, как описано в разделе (10.3).
Возможные ошибки при кодировании
Во многих готовых пакетах, реализующих Наивный Байесовский подход, используются двоичные атрибуты. На практике, однако, часто встречаются недвоичные атрибуты. Рассмотрим следующий атрибут: возраст. В опросе возраст человека указывается с помощью переменной a € 1, 2, 3. a = 1 означает, что человек находится в возрасте от от 0 до 10 лет, a = 2 означает, что человеку от 10 до 20 лет, a = 3 означает, что ему больше 20 лет. Одним из способов преобразования переменной a в двоичное представление было бы использование трех двоичных переменных (a1, a2 , a3 ) с (1, 0, 0), (0, 1, 0), (0, 0, 1) представляющий собой a = 1, a = 2, a = 3 соответственно. Это называется кодированием-1-из -M, поскольку только 1 из двоичных переменных активна при кодировании M состояний. По конструкции означает, что переменные a1 , a2 , a3 являются зависимыми – например, если мы знаем, что a1 = 1, мы знаем, что a2 = 0 и a3 = 0. Независимо от какой-либо классовой принадлежности, эти переменные всегда будут зависимыми, вопреки предположению Наивного Байеса. Правильным подходом является использование переменных с более чем двумя состояниями, как описано в разделе (10.2.2).
10.2.2 Переменные с несколькими состояниями
Для переменной xi с более чем двумя состояниями, dom(xi ) = {1, ... , S}, вероятность наблюдения состояния xi = s обозначается как
с ;s p(xi = s|c) = 1. Для набора векторов данных xn ,n = 1, . . . N, принадлежащих классу c, в соответствии с i.i.d. предполагается, что вероятность того, что модель NB сгенерирует данные из класса c, равна
, что дает классу условную логарифмическую вероятность
Мы можем оптимизировать параметры ;, используя множитель Лагранжа (по одному для каждого из атрибутов i и классов c), чтобы обеспечить нормализацию:
Чтобы найти оптимум для этой функции, мы можем произвести дифференцирование относительно ;si (c) и приравнять к нулю. Решая полученное уравнение, получим
Следовательно, путем нормализации,
Значение Максимального Правдоподобия для параметра p(xi = s|c) равно относительному числу случаев, когда атрибут i находился в состоянии s для класса c.
ЧЕРНОВИК от 9 марта 2010 г. 207 Наивных Байесовских тестов\ Байесианов
Рисунок 10.3: Байесовский наивный алгоритм Байеса с разложенным на множители априором для класса вероятности условного атрибута p(xi = s|c). Для простоты мы предполагаем, что вероятность класса ;c ; p(c) обучается с максимальной вероятностью, так что для этого параметра не существует распределения.
10.2.3 Классификация текстов
Рассмотрим набор документов о политике и другой набор документов о спорте. Наш интерес заключается в разработке метода, который может автоматически классифицировать новый документ как относящийся к спорту или политике. Мы просматриваем оба набора документов, чтобы найти 100 наиболее часто встречающихся слов. В каждом документе затем он представляется в виде 100–мерного вектора, представляющего количество раз, когда каждое из слов встречается в этом документе, - так называемое представление пакета слов (это грубое представление документа, поскольку оно не учитывает порядок слов). Наивная Байесовская модель определяет распределение этого количества вхождений p(xi |c), где xi - количество раз, когда слово i встречается в документах типа c. Этого можно достичь, используя либо представление с несколькими состояниями (как обсуждалось в разделе (10.2.2)), либо используя непрерывный xi для представления частоты слова i в документе. В этом случае p(xi |c) можно было бы удобно смоделировать, используя, например, Бета-распределение.
Несмотря на простоту Наивного Байеса, он может классифицировать документы на удивление хорошо[125]. Интуитивно потенциальное обоснование предположения об условной независимости состоит в том, что если мы знаем, что документ посвящен политике, это является хорошим показателем того, какие другие слова мы найдем в документе. Потому что Наивно Байесовский классификатор является разумным в этом смысле и обладает минимальным объемом памяти и быстрым обучением, он был применен для приложений, критически важных для сохранения времени, таких как автоматическая классификация веб-страниц по типам[289] и фильтрация спама[9].
10.3 Байесовский Наивный Байес
Чтобы предсказать класс c входных данных x, мы используем
Для удобства мы просто зададим p(c|D), используя Максимальное Правдоподобие
Однако, как мы уже видели, установка параметров p(x|D, c) с использованием обучения с Максимальным Правдоподобием может привести к получению сверхнадежных прогнозов в случае разреженных данных. Байесовский подход, который устраняет эту трудность заключается в использовании предварительных значений для вероятностей p(xi = s|c) ; ;si (c), которые препятствуют экстремальным значениям. Модель представлена на рис.10.3.
Предварительное значение \Приор
Мы будем использовать предварительное значение для записей таблицы и сделаем предположение о глобальной факторизации (см. раздел (9.3)).
208 ЧЕРНОВИК от 9 марта 2010 года По-байесовски наивный Байес
Мы рассматриваем дискретные xi, каждое из которых принимает состояния от 1, . . . , S. В этом случае p (xi = s | c) соответствует многочленному распределению, для которого сопряженным предварительным является распределение Дирихле. При разложенном на множители предварительное допущение (10.3.3) мы определяем предварительное допущение для каждого атрибута i и класса c,
где ui (c) - вектор гиперпараметров распределения Дирихле для таблицы p(xi |c).
Далее\ постериор, завершающие, заключительные, конечные, конченные,
Сначала давайте посмотрим, как Байесовский подход используется для классификации новой точки x;. Пусть D обозначает тренирующиеся данные (xn , cn ), n = 1, . . . , N . Из уравнения (10.3.14) член p(x; , D|c;) вычисляется с использованием следующего разложения:
Следовательно, для того, чтобы сделать прогноз, нам требуется параметр постериор. В соответствии с нашими общими результатами Байесовского обучения\тренировок BN в разделе(9.3) параметр постериор\ завершённый\ разлагает на множители
, где
По сопряженности апостериорное распределение для класса c; является распределением Дирихле,
где вектор ^ui (c; ) имеет компоненты
Для гиперпараметров Дирихле ui (c; ) приведенное выше уравнение обновляет гиперпараметр на количество раз, когда переменная i находится в состоянии s для данных класса c;. Обычно по умолчанию все компоненты u принимаются равными 1.
Классификация
Распределение по классам задается
как
Для вычисления p(x; |D, c; ) мы используем
Использование общей идентификации
, где Z(u) - константа нормализации Дирихле распределения Дирихле (·|u) и
ДРАФТ от 9 марта 2010 209 Три дополненных наивных Байеса
Рисунок 10.4: Дерево Чжоу-Лю, в котором каждая переменная xi имеет не более одного родительского элемента. Переменные могут быть проиндексированы таким образом, что 1 ; i ; D.
получим
где
Пример 49 (Байесовский Наивный метод Байеса). Повторяя предыдущий анализ для данных "Являются ли они шотландцами?" из примера(48), вероятность при одинаковом коэффициенте Дирихле для всех таблиц, дает значение 0,236 для вероятности того, что (1, 0, 1, 1, 0) является шотландцем, по сравнению со значением 0,192 в соответствии со стандартным наивным предположением Байеса.
10.4 Наивный байесовский алгоритм, дополненный деревом
Естественным расширением Наивного Байесовского метода является ослабление предположения о том, что атрибуты независимы от класса:
Тогда возникает вопрос – какую структуру мы должны выбрать для p(x|c)? Как мы видели в разделе(9.3.5), обучение структуры является вычислительно неосуществимым для всех атрибутов, кроме очень небольшого числа. Практический алгоритм требует определенной формы ограничения на структуру. Чтобы сделать это, мы сначала сделаем экскурс в обучение деревьев с Максимальным Правдоподобием, для которых требуется не более одного родительского элемента.
10.4.1 Деревья Чау-Лю
Рассмотрим многомерное распределение p (x), которое мы хотим аппроксимировать распределением q (x). В дальнейшем- более того, мы ограничиваем приближение q(x) Сетью Убеждений, в которой каждый узел имеет не более одного родительского элемента. Сначала мы предполагаем, что мы выбрали конкретное обозначение переменных 1 ; i ; D, для которых ограничение DAG на одного родительского элемента означает
где pa(i) - единственный родительский индекс узла i. Чтобы найти наилучшее аппроксимирующее распределение q в этом ограниченном классе, мы можем минимизировать расхождение Кульбака-Лейблера
Поскольку p(x) является фиксированным, первый член является постоянным. Добавив член <log p(xi |xpa(i) )> p(xi ,xpa(i)) , который зависит только от p(x), мы можем записать
210 ПРОЕКТ от 9 марта 2010 года - Дерево, дополненное наивным байесовским алгоритмом
Алгоритм 7 деревьев Чоу-Лю
1: для i = 1 - D делаем
, для j = 1 - D делаем
Вычисляем взаимную информацию для пары переменных xi , xj : wij = MI(xi ; xj )
4:конец для
5: конец для
6: Для неориентированного графа G с весом ребер w найдите неориентированное остовное дерево T с максимальным весом
7: Выберите произвольную переменную в качестве корневого узла дерева T .
8: Сформируйте направленное дерево, ориентируя все ребра от корневого узла.
Это позволяет нам понять, что с точностью до незначительной константы общая дивергенция Кульбака-Лейблера является положительной суммой индивидуальных дивергенций Кульбака-Лейблера, так что оптимальная настройка, таким образом,
Подставляя это решение в уравнение (10.4.3) и используя log p(xi |xpa(i)) = log p(xi , xpa(i)) ; log p(xpa(i)), получим
Нам все еще нужно найти оптимальную родительскую структуру pa(i), которая минимизирует приведенное выше выражение. Если мы добавим и вычтем энтропийный член, то сможем записать
Для двух переменных xi и xj и распределения p(xi , xj ) взаимное информационное определение(87) может быть записано как
которую можно рассматривать как дивергенцию Кульбака-Лейблера KL(p(xi , xj )|p(xi )p(xj )) и, следовательно, она неотрицательна. Используя это, уравнение (10.4.7) имеет вид
Поскольку наша задача состоит в том, чтобы найти родительские индексы pa(i), а энтропийный член ;i <log p(xi )>p(xi ) является независимым из этого сопоставления, нахождение оптимального сопоставления эквивалентно максимизации суммарной взаимной информации
при условии, что pa(i) ; i. Поскольку нам также необходимо выбрать оптимальную начальную маркировку переменных, задача эквивалентна вычислению всей попарной взаимной информации
, а затем нахождению максимального связующего дерева для графа с весами ребер w (см. spantree.m). Это можно рассматривать как форму поиска вширь[61]. После того, как мы нашли, нам нужно идентифицировать направленное дерево с не более одного родительского элемента. Это достигается путем выбора произвольного узла и последующего последовательного удаления ребер от этого узла.
ЧЕРНОВИК от 9 марта 2010 г. 211 Дополненного наивого Байеса Дерево
Рисунок 10.5: Дерево, дополненное наивным Байесом (TAN). Каждая переменная xi имеет не более одного родительского элемента. Оптимальная структура TAN с Максимальным Правдоподобием вычисляется с использованием модифицированного алгоритма Чоу-Лю, в котором условная взаимная информация MI(xi ; xj |c) вычисляется для всех i, j. Затем найдено связующее \остовное\ дерево с максимальным весом и преобразовано в ориентированный граф ориентируя ребра наружу от выбранного корневого узла. Затем записи таблицы можно считывать, используя обычный метод подсчета Максимального Правдоподобия.
Деревья Чжоу-Лю с Максимальным Правдоподобием
Если p(x) - эмпирическое распределение
, тогда
Следовательно, приближение q, которое минимизирует расхождение Кульбака-Лейблера между эмпирическим распределением и p, эквивалентно приближению, которое максимизирует вероятность получения данных. Это означает, что если мы используем взаимную информацию, полученную из эмпирического распределения, то при
тогда полученное дерево Чоу-Лю соответствует решению с наибольшим правдоподобием среди всех деревьев с одним родителем. Краткое описание процедуры приведено в алгоритме(7). Также доступен эффективный алгоритм для работы с разреженными данными [190].
Замечание 10 (Сети Убеждений с Древовидной Структурой Обучения). Алгоритм Чоу-Лю обсуждается в разделе (9.3.5), посвященном обучению структуры Сетей Убеждений на основе данных. При особом ограничении, заключающемся в том, что каждая переменная имеет не более одного родительского элемента, алгоритм Чоу-Лю возвращает структуру Максимальной Вероятности/Правдоподобия, чтобы подогнать данные.
10.4.2 Обучающее дерево, дополненное Наивными Байесовскими сетями
Для распределения p (x|c) в виде древовидной структуры с ограничением на одного родителя мы можем легко найти решение для класса с условным Максимальным Правдоподобием, вычислив дерево Чоу-Лю для каждого класса. Затем к каждой переменной добавляются ссылки\ связки из узла класса c и обучаются условные вероятности классов от c до x, которые могут быть считаны для получения Максимального Правдоподобия с помощью обычного аргумента подсчета. Обратите внимание, что в целом это привело бы к получению другого дерева Чоу-Лю для каждого класса.
Практикующие специалисты обычно ограничивают сеть, чтобы она имела одинаковую структуру для всех классов. Цель Максимального Правдоподобия при ограничении TAN, таким образом, соответствует максимизации условной взаимной информации[97].
смотрите упражнение(136). Как только структура обучена, можно затем задать параметры путем подсчета Максимального Правдоподобия. Методы предотвращения переобучения обсуждаются в [97] и могут быть решены с использованием априоров Дирихле, как и для более простой Наивной Байесовской структуры.
Можно легко рассмотреть структуры с меньшими ограничениями, чем Сети Убеждений с одним родителем. Однако сложность поиска оптимальных структур BN, как правило, не поддается вычислениям, и для ограничения пространства поиска требуются эвристические методы.
212 ЧЕРНОВИК от 9 марта 2010 года Упражнения
10.5 Код
NaiveBayesTrain.m: Наивный Байесовский тест, обученный с Максимальной Вероятностью
NaiveBayesTest.m: Наивный Байесовский тест
NaiveBayesDirichletTrain.m: Наивный Байесовский тест, обученный с помощью Байесовского метода Дирихле
NaiveBayesDirichletTest.m: Наивное Байесовское тестирование с помощью байесовского уравнения Дирихле
NaiveBayes.m: Демонстрация Наивного Байеса
10.6 Упражнения
Упражнение 130. Местный супермаркет, специализирующийся на продаже сухих завтраков, решает проанализировать привычки своих покупателей. Они провели небольшой опрос, в котором приняли участие 6 случайно выбранных людей их возраста (старше или моложе 60 лет) и спросили, какие из сухих завтраков (кукурузные хлопья, тортики, сахарные слойки, хлопья с отрубями) им нравятся. Каждый респондент предоставляет вектор с параметрами 1 или 0, которые соответствуют тому, нравятся ему хлопья или нет. Таким образом, респондент с номером (1101) предпочел бы кукурузные хлопья, торты с глазурью и хлопья с отрубями, но не сахарные слойки. Респонденты старше 60 лет предоставляют следующие данные (1000), (1001), (1111), (0001). Респонденты моложе 60 лет ответили (0110), (1110). Новая покупательница приходит в супермаркет и говорит, что любит только мороженое и слоеные пирожные. Используя наивный метод Байеса с максимальной вероятностью, какова вероятность того, что ей меньше 60 лет?
Упражнение 131. Психолог проводит небольшой опрос на тему ‘счастье’. Каждый респондент предоставляет вектор с параметрами 1 или 0, соответствующими тому, ответили ли они на вопрос "да" или "нет" соответственно. Вектор вопросов имеет атрибуты
x = (богатый, женатый, здоровый) (10.6.1)
Таким образом, ответы (1, 0, 1) будут указывать на то, что респондент "богат", "не женат", ‘здоров’. Кроме того, каждый респондент оценивает c = 1, если он доволен своим образом жизни, и c = 0, если это не так. Следующие ответы были получены от людей, которые также утверждали, что они "довольны".’ : (1, 1, 1), (0, 0, 1), (1, 1, 0), (1, 0, 1) и для ‘не содержательного’: (0, 0, 0), (1, 0, 0), (0, 0, 1), (0, 1, 0), (0, 0, 0).
1. Используя наивный метод Байеса, какова вероятность того, что человек, который "небогат", "женат" и "здоров", является ‘довольный’?
2. Какова вероятность того, что "небогатый" и "женатый" человек является "довольным"? (То есть мы не знаем, здоров он или нет).
3. Рассмотрим следующий вектор атрибутов :
x1 = 1, если клиент моложе 20 лет; x1 = 0 в противном случае (10.6.2)
x2 = 1, если клиенту от 20 до 30 лет ; x2 = 0 в противном случае(10.6.3)
x3 = 1, если клиент старше 30 лет; x3 = 0 в противном случае (10.6.4)
x4 = 1, если клиент ходит на работу пешком; x4 = 0 в противном случае(10.6.5)
Каждому вектору атрибутов соответствует метка класса "богатый" или "бедный". Укажите любые потенциальные трудности с использованием ранее описанного вами подхода к обучению с использованием метода Наивного Байеса. Отсюда опишите, как расширить ваш предыдущий метод Наивного Байеса для работы с этим набором данных.
Упражнение 132. В Whizzco решили создать текстовый классификатор. Для начала они пытаются классифицировать документы как спортивные или политические. Они решают представить каждый документ в виде вектора атрибутов (строк), описывающих наличие или отсутствие слов.
x = (цель, футбол, гольф, защита, нападение, калитка, офис, стратегия)
ЧЕРНОВИК от 9 марта 2010 года 213 Упражнения
Тренируемые данные из спортивных и политических документов представлены ниже в MATLAB в виде матрицы, в которой каждая строка представляет 8 атрибутов.
% Политика
% Спорт
Используя Наивный Байесовский классификатор, какова вероятность того, что документ x = (1, 0, 0, 1, 1, 1, 1, 0) посвящен политике?
Упражнение 133. Наивный байесовский классификатор для бинарных атрибутов xi ; {0, 1} параметризуется как ;i1 = p(xi = 1|класс = 1), ;i0 = p(xi = 1|класс = 0) и p1 = p(класс = 1) и p0 = p(класс = 0). Покажите, что граница принятия решения о классификации точки данных x может быть записана как wT x + b > 0, и явно укажите значения w и b как функции ; 1 , ; 0 , p1 , p0 .
Упражнение 134. Этот вопрос касается фильтрации спама. Каждое электронное письмо представлено вектором
x = (x1 , . . . , xD ) (10.6.7)
где xi ; {0, 1}. Каждая запись вектора указывает, появляется ли в электронном письме определенный символ или слово. Символы/слова
: деньги, наличные, !!!, виагра, . . . и т. д. (10.6.8)
Таким образом, x2 = 1, если в электронном письме появится слово "наличные". Обучающий набор данных состоит из набора векторов и метки класса c, где c = 1 означает, что электронное письмо является спамом, а c = 0 - не спам. Следовательно, тренирующий набор состоит из множества пар (xn , cn ), n = 1, . . . , N . Наивная Байесовская модель задается формулой
1. Нарисуйте Сеть Убеждений для этого распределения.
2. Выведите выражения для параметров этой модели в терминах тренирующих данных, используя Максимальную Вероятность. Предположим, что данные независимы и одинаково\ идентично, единственно\ распределены \i.i.d\
В явном виде параметрами являются
3. Учитывая обученную модель p(x, c), объясните, как сформировать классификатор p(c|x).
4. Если слово "виагра" никогда не появляется в данных для проверки спама, обсудите, как это повлияет на классификацию нового электронного письма, содержащего слово ‘виагра’.
5. Запишите выражение для границы принятия решения
p(c = 1|x) = p(c = 0|x) (10.6.12)
и покажите, что это может быть записано в виде
для соответствующих значений u и b.
214 ЧЕРНОВИК от 9 марта 2010 года Упражнения
Упражнение 135. Для распределения p(x, c) и аппроксимации q(x, c) покажите, что когда p(x, c) соответствует эмпирическому распределению, найдется такое q(x, c), которое минимизирует расхождение Кульбака-Лейблера
, которое соответствует тренировке Максимального Правдоподобия q(x, c).
Упражнение 136. Рассмотрим распределение p(x, c) и аппроксимацию с использованием дерева
Покажите, что для оптимального q(x, c), ограниченного, как указано выше, решение q (x, c), которое минимизирует KL(p(x, c)|q(x, c)) при повторном подключении к выражению Кульбака-Лейблера, получается, как функция родительской структуры,
Это показывает, что при ограничении на одного родителя и при том, что каждое дерево q (x|c) имеет одинаковую структуру, минимизация расхождения Кульбака-Лейблера эквивалентна максимизации суммы условных взаимных информационных условий.
Упражнение 137. Напишите процедуру MATLAB A = ChowLiu(X), где X - матрица данных D ; N, содержащая многомерную точку данных в каждом столбце, которая возвращает дерево максимального правдоподобия Чоу-Лю для X. Древовидная структура должна быть возвращена в разреженной матрице A. Возможно, вам пригодится процедура spantree.m. Файл ChowLiuData.mat содержит матрицу данных для 10 переменных. Используйте свою процедуру, чтобы найти Максимальное Правдоподобие дерева Чоу-Лю, и нарисуйте изображение результирующего DAG с ребрами, ориентированными в сторону от переменной 1.
ЧЕРНОВИК от 9 марта 2010 года 215 Упражнения
216
ЧЕРНОВИК от 9 марта 2010 г. ГЛАВА
ГЛАВА 11
Обучение со скрытыми переменными
11.1 Скрытые Переменные и Недостающие Данные
На практике вводимые данные часто отсутствуют, что приводит к неполноте информации для определения вероятности. Наблюдаемые переменные можно разделить на видимые (те, для которых мы действительно знаем состояние) и отсутствующие (те, состояния которых номинально были бы известны, но отсутствуют для конкретной точки данных).
Другим сценарием, в котором наблюдаются не все переменные в модели, являются так называемые модели со скрытыми переменными. В этом случае есть переменные, которые важны для описания модели, но никогда не используются\ наблюдаемы. Например, физика, лежащая в основе модели, может содержать скрытые процессы, которые необходимы для описания модели, но не поддаются прямому измерению.
11.1.1 Почему скрытые/отсутствующие переменные могут усложнить процедуру\ обработку
При обучении параметров моделей, как описано ранее в главе(9), мы предположили, что у нас есть полная информация для определения всех переменных объединенной модели данных p(v|;). Рассмотрим проблему Асбеста- Курения-Рак сеть раздела (9.2.3). В случае полных данных вероятность равна
что факторизуется\ устанавливаются коэффициенты\ с точки зрения параметров записи таблицы. Мы использовали это свойство, чтобы показать, что таблица записей ; можно обучить, рассматривая только локальную информацию, как в методе Максимального Правдоподобия так и технике Байесовского (уравнения).
Теперь рассмотрим случай, когда о некоторых пациентах доступна лишь частичная информация. Например, для пациента n с записью vn = {c = 1, s = 1} известно, что у пациента рак и он курит, но неизвестно, подвергался ли он воздействию асбеста. Поскольку мы можем использовать только доступные ‘видимые’ данные, информация заключается в том, что представляется разумным оценивать параметры, используя предельную \сметную, полезную, деловую, доходную, прибыльную, подрасчётную\ вероятность
Мы обсудим, когда этот подход применим, в разделе (11.1.2). Использование предельного правдоподобия может привести к вычислительным трудностям, поскольку уравнение (11.1.2) не разложено на множители в таблицах. Это означает, что функция правдоподобия не может быть записана как произведение функций, по одной для каждого отдельного параметра. В этом в этом случае максимизация вероятности является более сложной задачей, поскольку параметры разных таблиц связаны.
Аналогичная проблема возникает и при Байесовском обучении. Как мы видели в разделе (13), при факторизации априорного значения для каждого CPT ; также факторизуется апостериорное значение. Однако, в случае неизвестного воздействия асбеста, член
217 Скрытые переменные и отсутствующие данные
Рисунок 11.1: (а): Допущение о случайном отсутствии. (b) Отсутствует полностью произвольное предположение.
вводится в виде
, которая не может быть записана как произведение функций fs (;s )fa (;a )fc (;c ). Таким образом, отсутствующая переменная вводит зависимости в апостериорное распределение параметров, делая апостериорное распределение более сложным.
Как в случае Максимального Правдоподобия, так и в Байесовском случае имеется четко определенная функция правдоподобия параметров таблицы/апостериора. Таким образом, сложность не концептуальная, а скорее вычислительная – как должны ли мы найти оптимальное значение вероятности/суммировать апостериорные данные?
Обратите внимание, что отсутствие данных не всегда приводит к тому, что апостериорный параметр не учитывается. Например, если состояние рака, описанное выше, не наблюдается, поскольку рак - это коллайдер, не имеющий потомков, условное распределение просто суммируется с 1, и у одного остается коэффициент, зависящий от a, а у другого - от s.
11.1.2 Допущение о пропущенном наугад
При каких обстоятельствах допустимо использовать предельную вероятность для оценки параметров? Мы разделяем переменные x делятся на "видимые", xvis , и "невидимые", xinv , так что набор всех переменных может быть записан как x = [xvis , xinv ]. Для видимых переменных мы имеем наблюдаемое состояние xvis = v, в то время как состояние невидимых переменных неизвестно. Мы используем показатель minv = 1 для обозначения того, что состояние невидимых переменных неизвестно. Тогда для точки данных, которая содержит как видимую, так и невидимую информацию,
Если мы предположим, что механизм, который генерирует невидимые данные, имеет вид
тогда
Только термин \член p(xvis = ;) передает информацию о модели. Следовательно, при условии, что механизм, с помощью которого данные отсутствуют, зависит только от видимых состояний, мы можем просто использовать предельную вероятность для оценки параметров. Это называется предположением о случайном отсутствии данных.
Пример 50 (не пропущенный наугад\ случайное отсутствие). EZsurvey.org останавливает мужчину на улице и спросите, какой цвет ему нравится больше всего. Все мужчины, чей любимый цвет – розовый, отказываются отвечать на вопрос - при выборе любого другого цвета: на вопрос отвечают все мужчины. Основываясь на полученных данных, EZsurvey.org составляет гистограмму любимого цвета мужчин, основываясь на вероятности совпадения только видимых данных, и уверенно заявит, что ни один из них не любит розовый.
218 ЧЕРНОВИК от 9 марта 2010 г. Скрытые переменные и отсутствующие данные
Для простоты предположим, что существует только три цвета: синий, зеленый и розовый. EZsurvey.org пытается найти нужную гистограмму вероятностей ;b , ;g , ;p при ;b + ;g + ;p = 1. Каждый респондент создает видимый ответ xc при dom( xc ) = {синий, зеленый, розовый}, в противном случае mc = 1, если нет ответа. У трех мужчин спрашивают, какой цвет им больше всего нравится, и они сообщают данные
xc , xc , xc = {синий, отсутствует, зеленый} (11.1.9)
Основываясь только на вероятности наличия видимых данных, мы получаем логарифмическую вероятность для данных ввода-вывода i.i.d.
где последний Лагранжа член обеспечивает нормализацию. Максимизируем выражение, к которому мы приходим (см. упражнение(145))
Необоснованный результат, который EZsurvey.org получает из-за неправильного учета для механизма, который генерирует данные.
Правильным механизмом, который генерирует данные (включая отсутствующие данные), является:
где мы использовали p(m2c = 1|;) = ;p, поскольку вероятность того, что точка данных отсутствует, равна вероятности того, что любимый цвет - розовый. Максимизируя вероятность, мы получаем
как и следовало ожидать. С другой стороны, если есть другая видимая переменная, t, обозначающая время суток, и вероятность того, что мужчины ответят на вопрос, зависит только от времени t (например, вероятность пропуска высока в час пик), то мы действительно можем рассматривать пропущенные данные как случайные.
Более сильным предположением, чем MAR, является
это называется случайным совершенным отсутствием. Это относится, например, к моделям со скрытыми переменными, в которых переменное состояние всегда отсутствует, независимо от чего-либо еще.
11.1.3 Максимальная Вероятность
На протяжении всего оставшегося обсуждения мы будем предполагать, что любые недостающие данные искажены или отсутствуют полностью случайным образом. Это означает, что мы можем обрабатывать любые ненаблюдаемые переменные путем суммирования (или интегрирования) по их состояниям. Для достижения Максимального Правдоподобия мы обучаем параметры модели ;, оптимизируя предельное правдоподобие
относительно ;.
11.1.4 Проблемы с идентификацией\ Выводы способности идентифицировать
Целевая функция предельного правдоподобия зависит от параметров только через p(v|;), так что могут существовать эквивалентные решения по параметрам. Например, рассмотрим задачу со скрытой переменной с распределением
ЧЕРНОВИК от 9 марта 2010 года 219 Максимизация ожидания
, при которой переменная x2 никогда не наблюдается. Это означает, что предельная вероятность зависит только от входных данных p(x1 |;) =;x2 ;x1 ,x2 . При заданном Максимально Правдоподобном решении ;; мы всегда можем найти эквивалентное Максимально Правдоподобное установленное решение ;` (см. упражнение(146))
В других случаях пространству параметров предельного правдоподобия присуща симметрия.
Например, рассмотрим сеть с бинарными \двоичными переменными
p(c, a, s) = p(c|a, s)p(a)p(s) (11.1.18)
Наша цель - обучить таблицу
и четыре таблицы
где мы использовали ";", чтобы обозначить, что это оценки параметров.
Мы предполагаем, что у нас отсутствуют данные, так что состояния переменной a никогда не наблюдаются. В этом случае эквивалентное решение (в том смысле, что оно имеет одинаковую предельную вероятность) можно получить, поменяв местами состояния a:
и четырех таблиц
Аналогичная ситуация возникает в более общих условиях, когда состояние переменной постоянно не контролируется (примером могут служить смешанные модели), что приводит к внутренней симметрии в пространстве решений. Хорошо известной характеристикой алгоритмов максимального правдоподобия является то, что на начальных этапах обучения происходит "толкотня", на которой конкурируют эти симметричные решения.
11.2 Максимизация ожиданий
Алгоритм EM - это удобный итеративный подход общего назначения к максимизации вероятности при отсутствии данных/скрытых переменных[187]. Как правило, он прост\ выполняется в лоб\ в реализации и может обеспечить большие скачки в пространстве параметров, особенно на начальных итерациях.
11.2.1 Вариационный EM
Ключевой особенностью алгоритма EM является формирование альтернативной целевой функции, для которой параметр эффект связи \спаривания\, описанный в разделе (11.1.1), устранен, что означает, что можно обновлять отдельные параметры, как в случае с полностью наблюдаемыми данными. Принцип работы заключается в замене предельной вероятности на нижнюю границу – именно эта нижняя граница имеет несвязанную \неспаренную\ форму.
Сначала мы рассмотрим одну пару переменных (v, h), где v означает "видимая", а h - ‘скрытая’. Чтобы получить оценку \вывести границу\ предельной вероятности, рассмотрим расхождение Кульбака-Лейблера между ‘вариационным" распределением q(h|v) и параметрической моделью p(h|v, ;):
220 ПРОЕКТ от 9 марта 2010 г. Максимизация ожиданий
Термин "вариационный" относится к тому факту, что это распределение будет параметром задачи оптимизации. Используя правило Байеса, p(h|v, ;) = p(h, v|;)|p(v|;) и тот факт, что p(v|;) не зависит от h,
Перестраивая, мы получаем оценку предельной вероятности
Энтропия Энергия
Оценка потенциально полезна, поскольку она похожа по форме на полностью наблюдаемый случай, за исключением того, что логарифмическая вероятность членов с отсутствующими данными взвешивается с помощью предиктора. Уравнение (11.2.3) представляет собой оценку предельного правдоподобия для одного тренирующегося примера. В предположении i.i.d. логарифмическая вероятность всех обучающих данных
Суммируя данные тренировок, мы получаем оценку (предельного) логарифма вероятности
Обратите внимание, что граница является точной (то есть правая часть равна логарифмическому правдоподобию), когда мы устанавливаем
Оценка \Граница\ предполагает итеративную процедуру для оптимизации ;:
На Е-шаге для фиксированного ; найдите распределения q(hn |vn ), которые максимизируют уравнение (11.2.5).
На M-шаге для фиксированного {q(hn |vn ), n = 1, ... , N } найдите параметры ;, которые максимизируют уравнение (11.2.5).
11.2.2 Классический EM
В приведенном выше вариационном E-шаге полностью оптимальной настройкой является
Поскольку q не зависит от ;new, M-шаг эквивалентен максимизации только энергетического члена, см. алгоритм(8).
Пример 51 (пример с одним параметром и одним состоянием). Мы рассмотрим модель, достаточно маленькую, чтобы мы могли полностью отобразить эволюцию алгоритма EM. Модель основана на одной видимой переменной v и одной скрытой переменной с двумя состояниями h ; {1, 2}. Мы определяем модель p(v, h) = p(v|h)p(h) при
и p(h = 1) = p(h = 2) = 0,5. Для наблюдения v = 2,75 и ;2 = 0,5 наш интерес состоит в том, чтобы найти параметр ;, который оптимизирует вероятность
1Это аналогично стандартной статистической функции распределения, используемой в статистической физике, откуда заимствованы термины "энергия" и "энтропия".
ПРОЕКТ от 9 марта 2010 г. 221 Максимизация ожиданий
Алгоритм 8 Максимизация математического ожидания. Вычислить значение максимального правдоподобия для данных со скрытыми переменными. Входные данные: распределение p(x|;) и набор данных V. Возвращает значение ML, равное ;.
1: t = 0 . Счетчик итераций
2: Выберите начальную настройку для параметров ; 0 . Инициализация
3: пока ; не совпадет (или вероятность не совпадет), выполните
t;t+1
5: для n = 1 - N выполните . Пройдитесь по всем точкам данных .
6: qtn (hn |vn ) = p(hn |vn , ;t;1 ) Е \Первый шаг
7: конец для
8: ;t = arg max; N n=1 hlog p(h , v |;)iqtn (hn |v n ) . Шаг M
9: завершить , пока
10: вернуть ; t . Оценка параметра максимального правдоподобия.
Рисунок 11.2: (а): Логарифмическая вероятность для модели, описанной в примере(51). (b): Контуры нижней границы LB(q(h = 2), ;). Для первоначального выбора q(h = 2) = 0,5 и ; = 1,9 на графике отображаются последовательные обновления шагов E (по вертикали) и M (по горизонтали). (c): Начиная с ; = 1,95, алгоритм EM сходится к локальному оптимуму.
Логарифмическая вероятность показана на рисунке (11.2,а) с оптимумом при ; = 1,325. Процедура EM итеративно оптимизирует нижнюю границу
где q(h = 1) = 1 ; q(h = 2). Начиная с начального значения ;, алгоритм EM находит распределение q, которое оптимизирует L(q, ;) (E-шаг), а затем обновляет ; (M-шаг). В зависимости от начального значения ; найденное решение является либо глобальным, либо локальным оптимумом вероятности, см. рис.11.2.
В этом случае M-шаг легко вычислить аналитически с помощью ;new = v <h>q(h) / <h2>q(h) . Аналогично, E-шаг устанавливает q new (h) = p(h|v, ;), так что
где мы использовали
222 ПРОЕКТ от 9 марта 2010 г. Максимизация ожиданий
Пример 52. Рассмотрим простую модель
где dom(x1 ) = dom(x2 ) = {1, 2}. Предполагая неограниченное распределение
наша цель - извлечь \ обучить\ ; из данных x1 = (1, 1) , x2 = (1, ?) , x3 = (?, 2). Энергетический член для классического EM - это
Полное написание каждого из приведенных выше слагаемых в отдельной строке дает энергию
Это выражение напоминает стандартную логарифмическую вероятность для полностью наблюдаемых данных, за исключением того, что термины с отсутствующими данными имеют свои взвешенные логарифмические параметры. Параметры удобно разделены в этой привязке (за исключением тривиального ограничения нормализации), так что найти оптимальные параметры несложно \ в лоб. Этот достигается за счет M-ступенчатого обновления, которое дает
где p(x2 |x1 , ;old ) ;x1,x2old (E-шаг) и т.д. Этапы E и M повторяются до тех пор, пока не будет достигнута сходимость.
Алгоритм EM увеличивает вероятность
Хотя по своей конструкции алгоритм EM не может уменьшить оценку вероятности, важный вопрос заключается в том, обязательно ли сама логарифмическая вероятность увеличивается с помощью этой процедуры.
Мы используем ;` для новых параметров и ; для предыдущих параметров в двух последовательных итерациях. С помощью q(hn |v n ) = p(hn |vn , ;) мы видим, что в зависимости от параметров нижняя граница для одной пары переменных (v, h) зависит от ; и ;` :
и
То есть дивергенция Кульбака-Лейблера - это разница между нижней границей и истинной вероятностью. Мы можем записать
Следовательно
ЧЕРНОВИК от 9 марта 2010 года 223 Максимизация ожиданий
Рисунок 11.3: База данных, содержащая информацию о том, что человек является курильщиком (1 означает, что человек является курильщиком), и о раке легких (1 означает, что у человека рак легких). Каждая строка содержит информацию о конкретном человеке, так что в базе данных есть 7 человек.
Первое утверждение верно, поскольку, по определению M-шага, мы ищем значение ;`, которое имеет большее значение для граница больше, чем наше начальное значение ;. Второе утверждение верно в силу свойства дивергенции Кульбака-Лейблера.
Для более чем одной точки данных мы просто суммируем каждую отдельную границу для log p(v n |;). Следовательно, мы приходим к важному выводу, что алгоритм EM увеличивает не только нижнюю границу предельного правдоподобия, но и само предельное правдоподобие (точнее, EM не может уменьшить эти величины).
Общие\ разделённые параметры и таблицы
Случай с таблицами, разделяющими параметры, по сути, прост \в лоб. В соответствии с энергетическим термином, нам необходимо чтобы идентифицировать все слагаемые, в которых встречается общий\ отданный, разделённый\ параметр. В этом случае целью для общего параметра является сумма по всем энергетическим слагаемым, содержащим общий параметр.
11.2.3 Применение к Сетям Убеждений
С концептуальной точки зрения, применение EM для обучения Сетей Убеждений с недостающими данными является простым в лоб. Борьба носит скорее нотационный, чем концептуальный характер. Мы начинаем разработку с примера, из которого можно почерпнуть представление об общем случае.
Пример 53. Рассмотрим сеть.
p(a, c, s) = p(c|a, s)p(a)p(s) (11.2.23)
для которого у нас есть набор данных, но состояния переменной a никогда не наблюдаются, см. рис.11.3. Наша цель - изучить значения CPT p(c|a, s) и p(a) и p(s). Чтобы применить алгоритм(8) к этому случаю, мы сначала предполагаем начальные параметры ;a0 , ;s0 , ;c0 .
Затем на первом электронном шаге для итерации t = 1 определяется набор распределений по скрытым переменным (здесь скрытой переменной является a)
и так далее для 7 обучающих примеров, n = 2, . . . , 7. Для удобства записи мы пишем qtn (a) вместо qtn (a|v n ).
Теперь мы переходим к первому M-шагу. Энергетический член для любой итерации t равен:
Конечным слагаемым является логарифмическая вероятность переменной s, и p(s) явно отображается только в этом слагаемом. Следовательно, применяется обычное правило максимального правдоподобия, и p(s = 1) просто задается относительным числом столько раз
224 ПРОЕКТ от 9 марта 2010 года
, сколько в базе данных встречается значение s = 1, что дает p(s = 1) = 4/7, p(s = 0) = 3/7.
Параметр p(a = 1) встречается в терминах
, который, используя ограничение нормализации, равен
Дифференцируя относительно p(a = 0) и решая для нулевой производной, получим
То есть, в то время как при стандартной оценке Максимального Правдоподобия мы имели бы реальные значения данных в приведенной выше формуле, которые были заменены на наши предполагаемые значения qtn (a = 0) и qtn (a = 1).
Аналогичная ситуация имеет место и для p(c = 1|a = 0, s = 1). Вклад этого термина в энергию заключается в
, что равно
Оптимизация относительно p(c = 1|a = 0, s = 1) дает
Для сравнения, значение параметра в полном наборе данных равно
Между этими обновлениями существует интуитивная взаимосвязь: в случае отсутствия данных мы заменяем индикаторы предполагаемыми распределениями q.
Повторяя шаги E и M, эти уравнения будут сходиться к локальному оптимуму вероятности.
Чтобы свести к минимуму нагрузку на записи, мы предполагаем, что структура отсутствующих переменных фиксирована на всем протяжении, что эквивалентно модели скрытой переменной. Форма энергетического термина для обозначения Сети Убеждений - это
Полезно задать следующие обозначения:
где x = (v, h) представляет все переменные в распределении. Это означает, что qtn (x) устанавливает видимые переменные в наблюдаемом состоянии и определяет условное распределение для ненаблюдаемых переменных. Мы
ЧЕРНОВИК от 9 марта 2010 года 225 Максимизация ожиданий
Алгоритм 9 EM для Сетей Убеждений. Входные данные: структура BN p(xi |pa (xi )), i = 1, . . . , K с пустой таблицей и набор данных для видимых переменных V. Возвращает значение Максимального Правдоподобия таблиц.
1: t = 1 . Счетчик итераций
2: Установите для pt (xi |pa (xi )) начальные значения.. Инициализация
3: пока p (xi |pa (xi )) не сходится (или вероятность не сходится), выполните
4:
5: для n = 1 - N выполните . Прогон по всем точкам данных
6: qtn (x) = pt (hn |vn ) ;(v, vn ) .Шаг E
7: конец для
8: от i = 1 до K до pn . Прогон по всем переменным
9: pt+1 (xi |pa (xi )) = N1 N n=1 qt (xi |pa (xi )) . Шаг M
10: завершение для
11: завершение во время
12: возврат pt (xi |pa (xi )) . Оценка параметра максимального правдоподобия.
затем определим распределение смеси
Энергетический член в уравнении (11.2.5) может быть записан более компактно в виде
Чтобы убедиться в этом, рассмотрим правую часть приведенного выше рисунка
Используя структуру Сети Убеждений, мы получаем
Это означает, что максимизация энергии эквивалентна минимизации
где мы добавили постоянный первый член, чтобы придать ему форму дивергенции Кульбака-Лейблера. Поскольку это сумма независимых расхождений Кульбака-Лейблера, оптимально задать M-шаг, установив
На практике хранение qt (x) по состояниям всех переменных x сопряжено с непомерными затратами. К счастью, поскольку на M-шаге требуется только распределение по семейству каждой переменной xi, требуется только локальное q oldn (xi |pa (xi )). Таким образом, мы можем отказаться от глобальных распределений q old(x), и эквивалентно использовать
При использовании алгоритма EM оптимальной настройкой для E-шага является использование qt (hn |vn ) = pold (hn |vn ). При таком обозначении алгоритм EM может быть сжато сформулирован, как в алгоритме(9). Смотрите также EMbeliefnet.m.
226 ПРОЕКТ от 9 марта 2010 г. Максимизация ожиданий
Пример 54 (Более Общие Сети Убеждений). Рассмотрим распределение с пятью переменными и дискретными переменными,
в котором переменные x2 и x4 последовательно скрыты в тренирующихся данных, а тренируемые данные для x1 , x3 , x5 всегда присутствуют. Распределение может быть представлено в виде Сети Убеждений
В этом случае вклады в энергию имеют вид
, что может быть записано как
Теперь можно использовать полезное свойство, заключающееся в том, что каждый член зависит только от тех скрытых переменных в семействе, которых этот член представляет. Таким образом, мы можем записать
Окончательный член может быть определен с использованием метода Максимального Правдоподобия. Поэтому рассмотрим более сложную таблицу, p(x1 |x2 ). Когда в энергии появится запись таблицы p(x1 = i|x2 = j)? Это происходит всякий раз , когда xn1 находится в состоянии i. Поскольку существует суммирование по всем состояниям переменных x2 (из-за среднего значения), существует также член с переменной x2 в состоянии j. Следовательно, вклад в энергию членов вида p(x1 = i|x2 = j) равен
, где индикаторная функция I [xn1 = i] равна 1, если xn1 находится в состоянии i, и равна нулю в противном случае. Чтобы обеспечить нормализацию таблицы, мы добавляем член Лагранжа:
Дифференцируя относительно p(x1 = i|x2 = j), получим
или
Следовательно
ПРОЕКТ от 9 марта 2010 227 Максимизация ожиданий
логарифм вероятности
Рисунок 11.4: Эволюция логарифмического правдоподобия в сравнении с итерациями в рамках процедуры обучения EM (на примере решения задачи "Ночной кошмар принтера"- выполните упражнение(138) с недостающими данными. Обратите внимание, насколько быстро достигается прогресс в начале, но сближение \ схождение\ может быть медленным.
Используя алгоритм EM, мы имеем
Это оптимальное распределение легко вычислить, поскольку оно является предельным для семейства, учитывая некоторые очевидные переменные. Следовательно, обновление таблицы с шагом M является
Что насчет таблицы p(x2 = i|x3 = j)? Чтобы обеспечить нормализацию таблицы, мы добавляем член Лагранжа:
Как и прежде, дифференцируя и используя настройки EM, мы имеем
В уравнении (11.9.2) и уравнении (11.2.53) есть простая интуитивно понятная схема: если бы не было скрытых данных, уравнение (11.9.2) выглядело бы следующим образом
и уравнение (11.2.53) будет иметь вид
Таким образом, все, что мы делаем в общем случае EM, - это заменяем эти детерминированные функции, такие как I [xn2 = i] по их отсутствующим переменным эквивалентам pold (x2 = i|xn1 , xn3 , xn5 ). Это всего лишь повторное изложение общего обновления, приведенного в уравнении (11.2.41) в соответствии с определением (11.2.34).
11.2.4 Применение к марковским сетям
Для MN, определенного по видимым и скрытым переменным p(v, h|;) = 1/Z(;);c ;c (h, v) вариационная граница EM
Хотя граница разделяет параметры во втором члене, параметры, тем не менее, связаны в нормализации Z(;). Из-за этого мы не можем оптимизировать приведенную выше привязку по каждому параметру. Один из подходов заключается в использовании дополнительной привязки log Z(;) сверху, как для итеративного масштабирования.
228 ПРОЕКТ от 9 марта 2010 г. Изменений в EM
11.2.5 Конвергенция \ Сходимость
Сходимость ЭМ\EM может быть медленной, особенно когда число пропущенных наблюдений превышает ожидаемое количество видимых наблюдений. На практике часто комбинируют ЭМ\EM с процедурами, основанными на градиенте, для улучшения сходимости, см. раздел (11.7). Также обратите внимание, что логарифмическая вероятность обычно является невыпуклой функцией параметров. Это означает, что может быть несколько локальных оптимумов, и найденное решение часто зависит от инициализации.
11.3 Расширения EM
11.3.1 Частичный\ Отдельный шаг M
Нет необходимости находить полный оптимум энергетического члена на каждой итерации. До тех пор, пока не будет найден параметр ;`, который имеет более высокую энергию, чем у текущего параметра ;, тогда требуемые условия будут выполнены, в разделе (11.2.2) все еще сохраняется, и вероятность не может уменьшаться на каждой итерации.
11.3.2 Частичный \Отдельный шаг E
Шаг E требует, чтобы мы нашли оптимальное значение
относительно q(hn |vn ). Полностью оптимальной настройкой является
Для гарантированного увеличения вероятности на каждой итерации, согласно разделу (11.2.2), мы требовали, чтобы использовалась полностью оптимальная настройка q. К сожалению, поэтому, в общем случае, нельзя гарантировать, чтобы такой частичный\ отдельный E шаг всегда увеличивал бы вероятность. Конечно, это гарантированно увеличивало бы нижнюю границу вероятности, но не саму вероятность.
Неразрешимая энергия
Алгоритм EM предполагает, что мы можем вычислить
Однако в целом может оказаться, что мы можем вычислить среднее значение по q только для очень ограниченного класса распределений - например, разложенных на множители распределений q(h|v) = ;jq(hj |v). В таких случаях можно использовать более простой класс распределений Q, например Q = разложенный на множители\факторизованный, factorised\ q(h|v) = ;iq(hi|v), для которого усреднение, требуемое для энергии, может быть более простым.
Мы можем найти наилучшее распределение в классе Q, минимизировав расхождение KL между q(h|v, ;Q) и p(h|v, ;) численно, используя процедуру нелинейной оптимизации:
В качестве альтернативы, можно принять определенную структурированную форму для распределения q и обучить оптимальные коэффициенты распределения с помощью функционального исчисления в свободной форме.
Обучение \Тренировки по Витерби
Крайним случаем является ограничение q(hn |vn ) дельта-функцией. В этом случае энтропийный член <log q(hn |vn )>q(hn |vn ) является постоянным, так что оптимальной дельта-функцией q является установка
ПРОЕКТ от 9 марта 2010 г. 229 Случай сбоя для EM
, где
Это называется обучением\ тренировкой по Витерби и часто используется при обучении \ в тренировках HMM, см. раздел (23.2). Таким образом, обучение\ тренировки\ EM с этим ограниченным классом распределения q гарантированно увеличивает нижнюю границу логарифмической вероятности, но не саму вероятность. Практическое преимущество обучения по Витерби заключается в том, что энергия всегда поддается вычислению, становясь просто
который поддается оптимизации.
При наличии достаточного количества данных можно надеяться, что вероятность, зависящая от параметра ;, резко достигнет оптимального значения. Это означает, что при сходимости аппроксимация заднего значения p(h|v, ;opt ) дельта-функцией будет разумной, и обновление EM с использованием обучения Витерби приведет к созданию нового ;, приблизительно такого же, как ;opt . Однако для любого сильно неоптимального ;, p(h|v, ;) будет далека от дельта-функции, и, следовательно, обновление по методу Витерби менее надежно с точки зрения увеличения вероятности как таковой. Это говорит о том, что инициализация ; для обучения по методу Витерби более важна, чем для стандартного EM.
Стохастическое обучение \ тренировки
Другим приблизительным распределением q(hn |vn ) было бы использование эмпирического распределения, сформированного выборками из полностью оптимального распределения p(hn |vn , ;). То есть, можно использовать выборки (обсуждение см. в главе(27) при выборке) hn1 , . . . , hnL из p(hn |vn , ;) и формирует q-распределение
Тогда энергия становится пропорциональной
таким образом, как и при обучении по Витерби, энергия всегда поддается вычислению для этого ограниченного класса q. При условии, что выборки из p(hn |vn ) надежны, стохастическое обучение выдаст энергетическую функцию с (,в среднем,) теми же характеристиками, что и истинная энергия в соответствии с классическим ЕМ алгоритмом. Этот это означает, что решение, полученное в результате стохастического обучения, должно стремиться к решению, полученному в классическом ЕМ, по мере увеличения числа выборок.
11.4 Случай сбоя для EM
Рассмотрим вероятность того, что форма
Если мы попытаемся применить для этого ЕМ-подход, это не удастся (см. также упражнение(75)). Для более общей модели вида
Первый \ Е -\шаг - это
230 ЧЕРНОВИК от 9 марта 2010 года вариационным Байесом
и наборами M-ступеней \ М-шаг устанавливается
, где мы использовали тот факт, что для этой модели p(h) не зависит от ;. В случае, когда p (v|h, ;) = ; (v, f (h|;)) , тогда
таким образом, для оптимизации энергии требуется
Поскольку P(h|;old ) равна нулю всюду ожидая, что H для которых v= f (h|;), тогда энергия будет эффективно негативное бесконечности, если ; ; ;old . Однако, когда ; = ;old энергия максимальна2 . Таким образом, это является оптимальным значением энергии и, следовательно, представляет собой сбой в обновлении для EM. Такая ситуация возникает на практике и имеет было отмечено, в частности, в контексте независимого компонентного анализа[222].
Можно попытаться исправить это поведение, разработав алгоритм EM, основанный на распределении
где n(h) - произвольное распределение скрытой переменной h. Исходная детерминированная модель соответствует p` (v|h, ;). Определив
у нас есть
Алгоритм EM для p; (v|;), 0 < ; < 1 удовлетворяет
, что подразумевает
Это означает, что алгоритм EM для недетерминированного случая 0 < ;< 1 гарантированно увеличивает вероятность в соответствии с детерминированной моделью p` (v|;) на каждой итерации (если только мы не достигнем сходимости). Видеть [100] за применение этого метода "антифриза" для изучения Марковских процессов принятия решений с помощью ЕМ.
11.5 Вариационный Байесовский подход
Как обсуждалось в разделе (9.2), Максимальное Правдоподобие соответствует форме Байесовского подхода, в которой апостериорное распределение параметра (при плоском априорном распределении) аппроксимируется дельта-функцией p(;|V) ; ;(;, ;opt ). Вариационный Байесовский подход аналогичен EM в том, что он пытается работать со скрытыми переменными, но используя распределение, которое лучше отражает апостериорное распределение, чем заданное методом Максимального Правдоподобия.
Чтобы упростить обозначение, мы сначала примем только одну точку данных с наблюдением v. В таком случае нас интересует параметр posterior
Подход VB предполагает факторизованную аппроксимацию скрытого соединения и заднего \постериор\ параметра:
2 Для дискретных переменных и дельты Кронекера энергия достигает максимального значения при нуле, когда ; = ;old . В случае однако для непрерывных переменных логарифм дельта-функции Дирака определен недостаточно четко. Учитывая, что дельта-функция является пределом гауссовой функции узкой ширины, для любой небольшой, но конечной ширины энергия является наибольшей, когда ; = ;old .
ЧЕРНОВИК от 9 марта 2010 г. 231Вариация Байеса
Оценка\ Граница\ предельной вероятности
Минимизируя расхождение в KL,
мы приходим к граничному
При фиксированном q(;), если мы минимизируем расхождение Кульбака-Лейблера, мы получим самую строгую нижнюю границу для log p(v). Если затем для фиксированного q (h) мы минимизируем расхождение Кульбака-Лейблера относительно w.r.t. q (;), то мы максимизируем член ; <log q(;)>q(;) + <log p(v, h, ;)>q(h)q(;) и, следовательно, увеличиваем границу предельной вероятности. Эта простая процедура определения координат, в которой мы сначала фиксируем q (;) и решаем для q (h), а затем наоборот, аналогична шагам E и M алгоритма EM:
E-шаг
M-шаг
В полной общности для набора наблюдений V и скрытых переменных H используется алгоритм(7). Для распределений q(H) и q(;), которые параметризованы/ограничены, возвращаются наилучшие распределения в смысле минимального KL . В общем, каждая итерация VB гарантированно увеличивает оценку предельного правдоподобия, но не саму предельную вероятность. Как и алгоритм EM, VB может страдать (и часто страдает) от проблем с локальными максимумами. Это означает, что конвергентное решение может зависеть от инициализации.
Неограниченные приближения
При фиксированном q(;) вклад в расхождение KL равен
где
где ~Z - нормализующая константа. Следовательно, при фиксированном q(;) оптимальное q(h) задается через ~p,
Аналогично, для фиксированного q(h) оптимально использовать
Данные ввода-вывода \ i.i.d., независимо идентично распределены
В предположении i.i.d. мы получаем оценку предельной вероятности для всего набора данных:
Граница справедлива для любых q(hn ) и q(;), но наиболее жесткая для сходящихся оценок из процедуры VB.
Для набора данных i.i.d. просто показать, что без потери общности мы можем предположить
При этом мы приходим к алгоритму(11).
232 ПРОЕКТ от 9 марта 2010 года по варианту Байеса
Алгоритм 10 Байеса с вариациями.
1: t = 0 . Счетчик итераций
2: Выберите начальное распределение q0 (;). . Инициализация
3: пока ; не сходится (или не сходится оценка вероятности), выполните
4: t;t+1
5:qtn (H) = arg minq(H) KL(q(H)qt;1 (;)|p(H, ;|V)) . Шаг E
6: qtn (;) = arg minq(;) KL(qtn (H)q(;)|p(H, ;|V)) . Шаг M
7: завершить, пока
8: вернуть qtn (;) .Апостериорная аппроксимация параметров.
Рисунок 11.5: (а): Общая форма модели со скрытыми переменными. (b): Факторизованная
апостериорная аппроксимация используется в Вариационном Байесе.
11.5.1 EM - это частный \специальный\ случай вариационного Байеса
Если мы хотим найти сводку распределения параметров, соответствующую только наиболее вероятной точке ;, то
где ;; - единственное оптимальное значение параметра. Если мы включим это предположение в уравнение (11.5.4), то мы получаем связанный логарифм \границу
Затем M-шаг определяется как
Для неизменного предыдущего значения p(;) = const., следовательно, это эквивалентно максимизации энергии в алгоритме EM. Используя это единственное оптимальное значение в обновлении VB для q(hn ), мы имеем
который является стандартным E-шагом EM. Следовательно, EM является частным \специальным\ случаем VB при плоском предшествующем p(;) = const. и аппроксимации параметра постериор дельта-функцией.
11.5.2 Разложение параметра постериор на множители
Давайте рассмотрим байесовское обучение в бинарной сети переменных
p(a, c, s) = p(c|a, s)p(a)p(s) (11.5.17)
в котором мы используем факторизованный параметр , предшествующий
Когда все данные будут собраны, параметр постериор будет разложен на множители. Как мы обсуждали в разделе(11.1.1), если состояние a не соблюдается, параметр постериор больше не факторизуется:
ПРОЕКТ от 9 марта 2010 233 Вариационный Байес
Алгоритм Байеса с вариацией 11 (исходные данные).
1: t = 0 . Счетчик итераций
2: Выберите начальное распределение q0 (;). . Инициализация
3: пока ; не сходится (или оценка вероятности не сходится), выполните
4: t;t+1
5: для n = 1 ; N, выполните . Пройдитесь по всем точкам данных .
6: hlog p(vn ,hn ,;), iq Следующий \Е-\ шаг
7: конец для
8:Phlog p(vn ,hn |;)iqn (hn ) . M шаг
9: завершите, пока
10: верните qtn (;) . Аппроксимация апостериорного параметра.
Рисунок 11.6: (а): Модель взаимосвязи между Раком легких, воздействием Асбеста и Курением с факторизованными предшествующими параметрами. Переменные c и s соблюдаются, но переменная a постоянно отсутствует. (b): Факторизованный последовавший параметр аппроксимации.
, где суммирование по a предотвращает разложение на множители отдельных параметров таблицы в произведении.
Поскольку с точки зрения представлений удобно работать с разложенными на множители апостериорами, мы можем применить VB, но с факторизованным ограничением на форму q. В VB мы определяем распределение по видимым и скрытым переменным. В этом случае скрытыми переменными являются an , а видимыми - sn , cn . Суммарный результат по всем ненаблюдаемым переменным (параметрам и отсутствующим наблюдениям) равен
Чтобы сделать факторизованную апостериорную аппроксимацию, мы используем
и свести к минимуму расхождение Кульбака-Лейблера между левым и правым из приведенных выше значений.
M-шаг
Следовательно
Следовательно
Удобно использовать Бета;версию распространения предварительного,
234 ЧЕРНОВИК от 9 марта 2010 г. Вариационное Байесовское приближение
, поскольку апостериорное приближение также является Бета-распределением:
Аналогичный расчет дает
и четыре таблицы, по одной для каждого из родительских состояний c. Например
Они напоминают стандартные Байесовские уравнения, уравнение (9.3.17), за исключением того, что значения были заменены на q.
Е- шаг
Нам все еще нужно определить q(an ). Оптимальное значение задается путем минимизации расхождения Кульбака-Лейблера относительно q(an ). Это дает оптимальное решение
Например, если предположить, что для точки данных n, s находится в состоянии 1, а c - в состоянии 0, то
и
Чтобы вычислить такие величины в явном виде, нам нужны значения <log ;>b(;|;,;) и <log (1 ; ;)>B(;|;,;) . Для Бета-распределение, их легко вычислить, смотрите упражнение(95).
Полная процедура VB затем задается путем повторения уравнений (11.5.28,11.5.29,11.5.30) и (11.5.32,11.5.33) до сходимости.
Учитывая конвергентную факторизованную аппроксимацию, вычисление предельной таблицы p (a = 1| V) в этом приближении является простым
Поскольку q(;a |V) является бета-распределением B (;a |;, ;), среднее значение является простым. Использование этого параметра для обоих состояний a приводит к
Применение VB для обучения таблиц в произвольно структурированных BNs является прямым продолжением описанного здесь метода. При факторизованном приближении q(h, ;) = q(h)q(;) всегда будет получено простое обновляемое уравнение, аналогичное полному варианту данных, но с заменой недостающих данных вариационными приближениями. Тем не менее, если переменная имеет много отсутствующих родительских параметров, число состояний в среднем по отношению к распределению q может стать неразрешимым, и потребуются дополнительные ограничения на форму аппроксимации или дополнительные оценки.
Можно легко распространить вышесказанное на случай распределений Дирихле по многочленным переменным, см. Упражнение (142). Действительно, расширение на экспоненциальное семейство является простым.
ПРОЕКТ от 9 марта 2010 г. 235 Оптимизация Вероятности с помощью Градиентных Методов
Рисунок 11.7: (a): Стандартное обучение ML. Наилучший параметр ; определяется путем максимизации вероятности того, что модель сгенерирует наблюдаемые данные ;opt = arg max ; p(v|;). (b): обучение ML-II. В случаях, когда у нас есть предварительное предпочтение параметрам ;, но с неопределенным гиперпараметром ;` , мы можем найти ;` с помощью ; `opt = арг max;` р(v|;` ) = arg max;` <p(v|;)>p(;|;` ) .
11.6 Байесовские методы и МЛ-II
Рассмотрим параметризованное распределение p(v|;), для которого мы хотим узнать оптимальные параметры ; по некоторым данным. Модель p(v|;) изображена на рис. 11.7a, где точка указывает на отсутствие распределения по этой переменной. Для единственной наблюдаемой точки данных v установка ; по Максимальному Правдоподобию соответствует нахождению параметра ;, который максимизирует значение p(v|;).
В некоторых случаях у нас может быть представление о том, какие параметры ; являются более подходящими и могут выражать это предварительное предпочтение с использованием распределения p(;). Если предыдущее значение было полностью указано, то "обучать" нечего, поскольку p(;|v) теперь полностью известно. Однако во многих случаях на практике мы не уверены в точных настройках параметров предшествующего и, следовательно, указываем параметризованный предшествующий, используя распределение p(;|;` ) с гиперпараметром ;` . Это изображено на рис. (11.7 в). Обучение соответствует нахождению оптимального ;`, которое максимизирует вероятность р(v|;` ) = ;; p(v|;)p(;|;` ). Эта процедура известна как ML-II, поскольку она соответствует максимальному правдоподобию, но на более высоком уровне гиперпараметров[33, 183]. Это форма приближенного Байесовского анализа, поскольку, хотя ;` задается с использованием максимального правдоподобия, после обучения мы получаем распределение по параметрам, p(;|v, ;` ).
11.7 Оптимизация вероятности градиентными методами
11.7.1.Ориентированные модели
Алгоритм EM обычно хорошо работает, когда количество недостающей информации невелико по сравнению с полной информацией. В этом случае EM демонстрирует примерно такую же сходимость, как и Ньютоновский основанный на градиентном методе[237]. Однако, если доля недостающей информации приближается к единице, они могут сходиться очень медленно. В случае непрерывных параметров ; альтернативой является прямое вычисление градиента вероятности и использование его как части стандартной процедуры оптимизации непрерывных переменных. Градиент легко вычислить, используя следующее тождество. Рассмотрим логарифмическую вероятность
Производная может быть записана
В этот момент мы берем производную внутри интеграла
где мы использовали ; log f (x) = (1/f (x));f (x). Правая часть представляет собой среднее значение производной логарифмической полной вероятности. Это тесно связано с производной от энергетического члена в алгоритме EM, хотя обратите внимание, что среднее значение здесь вычисляется по текущим параметрам распределения ;, а не ; old, как в случае с EM. При использовании этого метода вычисление производных моделей со скрытыми переменными относительно простое. Затем эти производные могут быть использованы как часть стандартной процедуры оптимизации, такой как сопряженные градиенты[237].
236 ЧЕРНОВИК от 9 марта 2010 года Упражнения
11.7.2 Неориентированные модели
Рассмотрим неориентированную модель, которая содержит как скрытые, так и видимые переменные
Для данных ввода-вывода логарифмическая вероятность для видимых переменных равна (при условии дискретности v и h)
который имеет градиент
зажатый средний
свободное среднее
Для Марковской Сети, которая является неразрешимой (статистическая функция Z не может быть эффективно вычислена), градиент особенно трудно оценить, поскольку он представляет собой разность двух величин, каждая из которых должна быть оценена. Поэтому даже точное определение знака градиента может быть сопряжено с вычислительными трудностями. По этой причине обучение на таких моделях, как машина Больцмана со скрытыми блоками, особенно сложно.
11.8 Код
В демонстрационном коде мы берем исходную сеть Клиник Грудной клетки [170] и извлекаем образцы \выборки\ данных из этой сети. Затем нам интересно посмотреть, сможем ли мы использовать алгоритм EM для оценки таблиц на основе данных (при этом некоторые части данных будут отсутствовать случайным образом). Мы предполагаем, что нам известна правильная структура BN, только неизвестны значения CPT. Мы предполагаем, что таблица логических элементов известна, поэтому нам не нужно ее обучать.
demoEMchestclinic.m: Демонстрация EM при обучении таблиц Chest Clinic \ Клиник Грудной Клетки
Следующий код реализует Максимально Правдоподобное обучение таблиц BN на основе данных с возможными пропущенными значениями.
EMbeliefnet.m: Обучение Сети Убеждений
11.9 Упражнения
Упражнение 138 (Продолжение Кошмара с Принтером). В соответствии с таблицей BN, представленной на рис. 9.19, в следующей таблице представлены данные, собранные на принтере, где ? указывает, что запись отсутствует. Каждый столбец представляет собой точку данных. Используйте алгоритм EM для обучения всех CPT в сети.
неисправность предохранителя
в блоке фотобарабана,
утечка тонера,
низкое качество бумаги,
изношенный валик,
запах гари,
низкое качество печати,
помятые страницы,
замятие бумаги на нескольких страницах
ЧЕРНОВИК от 9 марта 2010г. 237 Упражнения
Таблица содержится в EMprinter.mat, в ней используются состояния 1, 2, nan вместо 0, 1, ? (поскольку в BRMLtoolbox требуется, чтобы состояния были пронумерованы 1,2,....). Учитывая отсутствие мятых страниц, запаха гари и низкое качество печати, какова вероятность неисправности фотобарабана?
Упражнение 139. Рассмотрим следующее распределение по дискретным переменным,
в котором переменные x2 и x4 последовательно скрыты в обучающих данных, а обучающие данные для x1 , x3 , x5 всегда присутствуют. Покажите, что обновление EM для таблицы p(x1 |x2) задается формулой
Упражнение 140. Рассмотрим две простые переменные BN
p(y, x) = p(y|x)p(x) (11.9.3)
где y и x - двоичные переменные, dom(x) = {1, 2}, dom(y) = {1, 2}. У вас есть набор обучающих данных {(yn , xn ) , n = 1, . . . , N }, в которых в некоторых случаях xn может отсутствовать. Мы особенно заинтересованы в обучении таблицы p(x) на основе этих данных. Коллега предполагает, что можно установить p(x), просто просмотрев точки данных, в которых наблюдается x, а затем установив p(x = 1) как долю наблюдаемого x, которое находится в состоянии 1. Объясните, как предлагаемая процедура соотносится с Максимальной Вероятностью и EM.
Упражнение 141. Предположим, что последовательность генерируется цепью Маркова. Для одиночной цепочки длиной T мы имеем
Для простоты обозначим последовательность видимых переменных как
Для одиночной цепи Маркова, обозначенной символом h,
Всего существует множество из H таких Марковских цепей (h = 1, . . . , H). Таким образом, распределение по видимым переменным равно
1. Имеется набор обучающих последовательностей, vn , n = 1, . . . , N . Предполагая, что каждая последовательность vn независимо и идентично взята из модели смешения цепей Маркова с H компонентами, выведите алгоритм Максимизации Математического Ожидания для обучения этой модели.
2. Напишите общую функцию MATLAB в виде
для выполнения ЕМ-обучения для любого набора (одинаковой длины) последовательностей целых чисел vtn ; [1 : V ], t = 1, . . . , T . v - массив ячеек обучающих данных: v{2}(4) - 4-й элемент времени во второй последовательности тренировок. Каждый элемент, скажем, v{2}(4), должен быть целым числом от 1 до V . V — это количество состояний видимых переменных (в приведенном ниже примере биопоследовательности это будет 4). H -
238 ЧЕРНОВИК от 9 марта 2010 года Упражнения
количество компонентов смеси. num_em_loops - это количество итераций EM. A - матрица переходов A{h}(i,j)=p(v(t+1)=i|v(t)=j,h). pv - это предыдущее состояние первой видимой переменной, pv{h}(i)=p(v(t=1)=i|h). ph - это вектор предыдущих вероятностей для состояния смеси, ph(h)=p(h). q - это массив ячеек апостериорных вероятностей q{mu}(h)=p(h|v{mu}). Ваша программа также должна отображать для каждой итерации EM значение логарифмической вероятности. В качестве проверки вашей рутины вероятность регистрации должна увеличиваться с каждой итерацией.
3. Файл sequences.mat содержит набор фиктивных биопоследовательностей в массиве ячеек sequences{mu}(t). Таким образом, sequences {3}(:) - это третья последовательность, GTCTCCTGCCTCTCTGAAC, которая состоит из 20 временных шагов. Всего таких последовательностей 20. Ваша задача - сгруппировать эти последовательности в два кластера, предполагая, что каждый кластер моделируется цепью Маркова. Укажите, какие из последовательностей принадлежат друг другу, присвоив последовательность vn тому состоянию, для которого значение p(h| vn ) является наибольшим.
Упражнение 142. Напишите программу общего назначения VBbeliefnet(pot,x,pars) по аналогии с Embeliefnet.m который выполняет Вариационный Байесовский анализ с использованием априора Дирихле, используя факторизованную аппроксимацию параметров.
Допустим независимость как глобальных, так и локальных параметров для априора и аппроксимации q, раздел (9.3.1).
Упражнение 143. Рассмотрим 3-х "слойную" машину Больцмана, которая имеет вид
где dim v = dim h1 = dim h2 = dim h3 = V
Все переменные являются двоичными с состояниями 0, 1 , а параметры для каждого слоя l равны ;l = {Wl , Al , Bl} .
1. С точки зрения подгонки модели к видимым данным v1 , ... , vN , является ли приведенная выше трехслойная модель более эффективной, чем подгонка двухслойной модели (коэффициент ;(h2 , h3 |;3 ) отсутствует в двухслойном случае)?
2. Если мы используем ограниченный потенциал
является ли трехслойная модель более эффективной в плане соответствия видимым данным, чем двухслойная модель?
Упражнение 144. Сигмовидная Сеть Убеждений определяется многослойной сетью
где векторные переменные имеют двоичные компоненты xl ; {0, 1}wl, а ширина слоя l задается через wl . Кроме того
и
для весового вектора wi,l, описывающего взаимодействие с родительским уровнем. Верхний уровень, p(xL), описывает разложенное на множители распределение p(xL 1 ), ... , p(xwL L).
1. Нарисуйте структуру Сети Убеждений этого распределения.
2. Какова вычислительная сложность вычисления вероятности p(x0 ) для слоя x0, предполагая, что все слои имеют одинаковую ширину w?
ЧЕРНОВИК от 9 марта 2010 г. 239 Упражнения
3. Предполагая полностью факторизованную аппроксимацию для сети равной ширины,
запишите энергетический член Вариационной процедуры EM для единичного наблюдения за данными x0 и обсудите, насколько легко вычислить энергию.
Упражнение 145. Покажите, как найти компоненты 0 ; (;b , ;g , ;p ) ; 1, которые максимизируют уравнение (11.1.10).
Упражнение 146. Таблица вероятностей 2 ; 2, p(x1 = i, x2 = j) = ;i,j , с 0 ; ;i,j ; 1, ;2i=1; 2j=1 ;i,j = 1, обучается с использованием максимального предельного правдоподобия, при котором x2 никогда не наблюдается. Покажите, что если
задается как решение с максимальным предельным правдоподобием, тогда
имеет тот же показатель предельной вероятности.
240 ЧЕРНОВИК главы от 9 марта 2010 года
12
Выбор Байесовской Модели
12.1 Сравнение Моделей по Байесовскому Методу
Учитывая две модели М1 и М2 с параметрами ;1 , ;2 и связанные параметры приор,
как мы можем сравнить эффективность моделей при подборе набора данных D = {x1 , . . . , xN }? Применение правила Байеса к моделям дает основу для ответов на подобные вопросы – форму проверки Байесовской Гипотезы, применяемая на уровне модели. В более общем плане, учитывая индексированный набор моделей M1 , . . . , Мm , и соответствующие предварительные убеждения в уместности каждой модели p(Mi ), нас интересует в апостериорной вероятности модели
где
Модель Mi параметризуется с помощью ;i, а вероятность модели задается с помощью
В пространствах дискретных параметров интеграл заменяется суммированием. Обратите внимание, что количество параметров dim (;i ) не обязательно должно быть одинаковым для каждой модели.
Следует обратить внимание на то, что p(Mi |D) относится только к вероятности относительно указанного набора моделей M1 , . . . , Mm . Это не абсолютная вероятность того, что модель M подходит ‘хорошо’. Чтобы вычислить такую величину, потребовалось бы указать все возможные модели. Хотя интерпретация апостериорного значения p(Mi |D) требует некоторой осторожности, сравнение двух конкурирующих гипотез Mi и Mj является простым и требует только Байесовского коэффициента
Коэффициент Байеса
, который не требует интегрирования/суммирования по всем возможным моделям.
241иллюстрация : подбрасывание монеты
Рисунок 12.1: (а): Дискретная предварительная модель ‘честной’ монеты. (b): Предварительная модель для предвзятой "нечестной" монеты. В обоих случаях мы делаем явный выбор относительно того, что мы считаем ‘справедливым’ и ‘несправедливым’.
12.2 Иллюстрации : подбрасывание монеты
Мы рассмотрим две иллюстрации. В первой используется дискретное пространство параметров, чтобы упростить математику. Во втором случае мы используем непрерывное пространство параметров.
12.2.1 Дискретное пространство параметров
Проще всего было бы рассмотреть две конкурирующие модели, одна из которых соответствует честной монете, а другая - предвзятой. Смещение монеты, а именно вероятность того, что монета упадет орлом, определяется как ;, так что по-настоящему честная монета имеет ; = 0,5. Для простоты мы предполагаем, что dom(;) = {0.1, 0.2, . . . , 0.9}. Для четной монеты мы используем распределение p(;|Mчестной \fair ) на рис. 12.1а, а для монеты со смещением - распределение p(;|M смещение/biased ) на рис.12.1б.
Для каждой модели M вероятность определяется по формуле
Предполагая, что p(M fair ) = p(Mbiased ), коэффициент Байеса определяется отношением двух моделей вероятности.
Пример 55 (Дискретное пространство параметров).
5 Орлов и 2 решки, здесь p(D|Mfair) = 0,00786 и p(D|Mbiased ) = 0,0072. Коэффициент Байеса
равен
это указывает на то, что выборa отличие между этими двумя моделями невелико.
50 орлов и 20 решек , здесь p(D|Mfair ) = 1,5 ; 10-20 и p(D|Mbiased ) = 1,4 ; 10-19 . Коэффициент Байеса
это указывает на то, что у них примерно в 10 раз больше веры в предвзятую модель, чем в справедливую.
12.2.2 Непрерывное пространство параметров
Здесь мы повторяем приведенные выше вычисления, но для непрерывных пространств параметров.
242 ЧЕРНОВИК от 9 марта 2010 года Иллюстрации : подбрасывание монеты
Рисунок 12.2: Плотность вероятности зависит от вероятности выпадения Орла \ Head p(;). (а): Для чистой монеты p(;|Mfair ) = B (;|50, 50). (b): Для монеты со смещением p(;|Mbiased ) = 0,5 (B (;|3, 10) + B (;|10, 3)). Обратите внимание на разные вертикальные шкалы в двух случаях.
Монета со смещением.
Для правильной монеты, уни-модальный приор уместен. Мы используем Бета-распределение
для удобства, поскольку это сопряжено с биномиальным распределением, требуемые интегрирования тривиальны. Разумным выбором для честной монеты является a = 50, b = 50, как показано на рис. 12.2,а).
В целом,
Смещенная монета
Для смещенной монеты мы используем бимодальное распределение, сформированное, для удобства, как смесь двух Бета -распределений:
как показано на рис. 12.2, б). Модельная вероятность p(D|Mbiased ) определяется как
Предполагая отсутствие предварительного предпочтения справедливой или предвзятой монеты p(M ) = const. и повторяя описанный выше сценарий в случае дискретного параметра:
Пример 56 (Непрерывное пространство параметров).
ПРОЕКТ от 9 марта 2010 г. 243 Решение Бритвы Oккама и Байесовские Штрафы за Сложность
Рисунок 12.3: Вероятность выпадения общего количества очков в кубиках, p(t|n) для n = 1 (вверху) - n = 5 (внизу) кубиков. По горизонтальной оси отложено общее количество очков t. Вертикальной линией отмечено сравнение значений p(t = 9|n) для разного количества матриц. Более сложные модели, которые могут достигать большего числа состояний, имеют меньшую вероятность из- за нормализации по t.
5 Орлов и 2 Решки, здесь p(D|Mfair) = 0,0079 и p(D|Mbiased ) = 0,00622. Коэффициент Байеса
равен
это указывает на то, что выбор между этими двумя моделями невелик.
50 Орлов и 20 Решек , здесь p(D|Mfair ) = 9,4 ; 10-21 и p(D|Mbiased ) = 1,09 ; 10-19 . Коэффициент Байеса равен
это указывает на то, что у них примерно в 11 раз больше веры в предвзятую модель, чем в справедливую.
12.3 Бритва Оккама и Байесовская Оценка \ Штраф за\ Сложности
Мы возвращаемся к сценарию игры в кости из раздела (1.3.1). Здесь мы предположили, что есть два кубика, оценки которых s1 и s2 неизвестны. Известна только сумма двух оценок t = s1 + s2. Затем мы вычислили апостериорную совместное распределение очков p(s1 , s2 |t = 9) для двух кубиков. Мы повторяем расчет, но теперь для нескольких кубиков 1 и с той разницей, что Мы не знаем, сколько всего кубиков, знаем только, что сумма очков равна 9. То есть мы знаем, что t =; n i=1 si, и нам присваивается значение t = 9. Однако нам не сообщается количество задействованных кубиков n. Предполагая, что любое число n одинаково вероятно, каково апостериорное распределение по n?
Исходя из правила Байеса, нам нужно вычислить апостериорное распределение по моделям
В приведенном выше
1Это описание "бритвы Оккама" принадлежит Тайлану Джемгилу.
244 ЧЕРНОВИК от 9 марта 2010 г. Продолжительный пример: подгонка кривой.
Рисунок 12.4: Апостериорное распределение p(n|t = 9) количества кубиков с учетом наблюдаемого суммарного балла, равного 9.
, где p(si ) = 1/6 для всех оценок \результатов\ si . Перечислив все 6n состояний, мы можем явно вычислить p(t|n), как показано на рис. 12.3. Важным наблюдением является то, что по мере того, как модели, объясняющие данные, становятся все более ‘сложными" (n увеличивается), становится доступным больше состояний, и масса вероятности обычно уменьшается. Мы видим этот эффект при p (t = 9|n), где, помимо n = 1, значение p (t = 9|n) уменьшается с увеличением n, поскольку большее n имеет массу в большем количестве состояний, становясь более разбросанным. Предполагая, что p(n) = const, заднее значение \постериор\ p(n|t = 9) показано на рис. 12.4. Апостериори, существует только 3 правдоподобные модели, а именно n = 2, 3, 4, поскольку остальные либо слишком сложны, либо невозможны. Это демонстрирует эффект бритвы Оккама, который наказывает за слишком сложные модели.
12.4 Непрерывный пример : подгонка кривой
Рассмотрим аддитивный набор периодических функций
Это удобно записать в векторной форме
где ;(x) - это K + 1-мерный вектор с элементами (1, cos (x), cos(2x), ... , cos(Kx))T, а вектор w содержит веса аддитивной функции. Нам дан набор данных D = {(xn , yn ), n = 1, . . . , N }, взятых из этого распределения, где y - чистый y0 (x), искаженный аддитивным нулевым средним гауссовским шумом с дисперсией ;2 ,
см. рис. 12.5. Предполагая исходные данные i.i.d., нас интересует апостериорная вероятность числа коэффициентов, заданная наблюдаемыми данными:
Будем считать, что p(K) = const. Приведенный выше вероятностный член задается интегралом
Для p (w | K) = N (w|0, IK / ;) подынтегральная функция является Гауссовой в w, для которой легко вычислить интеграл в лоб (см. раздел (8.6) и упражнение(149))
(12.4.6)
Рисунок 12.5: Представление Иерархической Байесовской Модели в виде Сети Убеждений для регрессии, основанной на предположении о наличии данных i.i.d.. Обратите внимание, что промежуточные узлы в y0n включены, чтобы подчеркнуть роль подлежащей модели ‘чистой’. Поскольку p(y|w, x) = ;y0 p(y|y0 )p(y0 |w, x) = ;y0 N (y |y0 , ;2) ; (y0 ; w T x )= N (y |w T x, ;2) , мы можем при желании убрать промежуточный узел y0 и поместить стрелки непосредственно от w и xn к yn.
ПРОЕКТ от 9 марта 2010 г. 245, Приближения Вероятности для Модели
Рисунок 12.6: (а) Данные, полученные с использованием аддитивного Гауссовского шума ; = 0,5 из модели с K = 5 компонентами. (b) Апостериорное значение p(K|D). (c) Реконструкция данных с использованием <w>T ;(x), где <w> - среднее значение апостериорного вектора оптимальной размерной модели p(w|D, K = 5). Непрерывной линией показана реконструкция. Точками показаны истинные, чистые данные, лежащие в основе.
где
Предполагая, что ; = 1 и ; = 0,5, мы взяли некоторые данные из модели с K = 5 компонентами, рис.12.6,а). Мы предполагаем, что знаем правильный уровень шума ;. Заднее значение \постериор\ p(K|D), показанное на рис. 12.6, б, резко возрастает при K = 5, что является "правильным" значением, используемым для генерации данных. Чистые реконструкции для K = 5 показаны на рис. 12.6, с).
12.5 Аппроксимируем Вероятность Модели
Для модели с непрерывным вектором параметров ;, dim (;) = K и данными D вероятность модели
Для общего выражения
если f не имеет особенно простой формы (например, квадратичной по ;), интеграл по (12.5.1) вычислить невозможно, и требуются приближения.
12.5.1 Метод Лапласа
Простое приближение (12.5.1) получено методом Лапласа, раздел(28.2),
где ; ; - решение MAP
и H - это гессиан f (;) в точке ; ; .
246 ПРОЕКТ от 9 марта 2010 г. Упражнения
Для данных D = {x1 , . . . , xN}, то есть, i.i.d. сгенерированный выше, специализируется на
В этом случае метод Лапласа вычисляет оптимум функции
12.5.2 Информационный Критерий Байеса (BIC)
Для внутренних данных используются шкалы Гесса с числом обучающих примеров, N , и грубым приближением состоит в том, чтобы задать H ; N IK, где K = dim ;. В этом случае в качестве процедуры сравнения моделей можно использовать функцию
Для простого априора, который ограничивает длину вектора параметров, p(;|M ) = N (; 0, I), приведенное выше значение сводится к
Информационный Критерий Байеса[244] аппроксимирует (12.5.7), игнорируя штрафной член, и дает
Критерий BIC может быть использован в качестве приблизительного способа сравнения моделей, где значение ;K/2 log N снижает сложность модели. В общем, приближение Лапласа, уравнение (12.5.3), следует предпочесть критерию BIC, поскольку оно более корректно учитывает неопределенность в оценке апостериорных параметров. Другие методы, направленные на усовершенствование метода Лапласа, обсуждаются в разделах (28.3) и (28.7).
12.6 Упражнения
Упражнение 147. Напишите программу для реализации примера выбора модели подбрасывания монеты с учетом справедливости или предвзятости, приведенного в разделе(12.2.1), используя дискретную область для ;. Объясните, как преодолеть возможные числовые проблемы при работе с большими числами NH и NT (порядка 1000).
Упражнение 148. Вы работаете в хедж-фонде Dodder's, и менеджер хочет смоделировать "доходность" на следующий день yt+1 на основе информации за текущий день xt . Вектор "факторов" xt отражает основные аспекты рынка на каждый день. Он утверждает, что простая линейная модель
должнa быть разумной, и просит вас найти весовой вектор w, основываясь на исторической информации D = {(xt , yt+1 ), t = 1, . . . , T ; 1}. Кроме того, он также дает вам оценку "волатильности" ;t2 за каждый день.
1. В предположении, что доходность распределена по Гауссу i.i.d.
объясните, как задать весовой вектор w с учетом Максимального Правдоподобия.
ПРОЕКТ от 9 марта 2010 г. 247 Упражнения
2. Однако менеджер вашего хедж-фонда убежден, что некоторые факторы бесполезны для прогнозирования и хочет удалить как можно больше из них. Для этого вы решили использовать метод выбора Байесовской модели, в котором используется предварительное
где M = 1, . . . , 2K ; 1 индексирует модель. Каждая модель использует только подмножество факторов. Преобразуя целое число M в двоичное векторное представление, модель описывает, какие факторы следует использовать. Например, если K = 3, то будет 7 моделей
{0, 0, 1} , {0, 1, 0} , {1, 0, 0} , {0, 1, 1} , {1, 0, 1} , {1, 1, 0} , {1, 1, 1} (12.6.4)
где первая модель имеет значение yt = w3 x3 с предшествующим весом p(w3 ) = N (w3 |0, 1). Аналогично, модель 7 будет иметь вид yt = w1 x1 + w2 x2 + w3 x3 при p(w1 , w2 , w3 ) = N ((w1 , w2 , w3 ) (0, 0, 0), I3 ). Вы решили использовать плоское значение p(M ) = const. Нарисуйте иерархическую Байесовскую сеть для этой модели и объясните, как найти наилучшую модель для данных, используя выбор Байесовской модели путем соответствующей адаптации уравнения (12.4.6).
3. Используя data dodder.mat, выполните выбор Байесовской модели, как указано выше, для K = 6 и найдите, какие из факторов x1 , . . . , x6 с наибольшей вероятностью объясняют данные.6
Упражнение 149. Здесь мы выведем выражение (12.4.6), а также альтернативную форму.
1. Начиная с
Покажите, что это может быть выражено следующим образом
где
2. Заполнив квадрат (см. раздел (8.6.2)), выведите (12.4.6).
3. Поскольку каждый yn , n = 1, . . . , N линейно связан через w, а w распределен по Гауссу, то совместный вектор y1 , . . . , yn распределен по Гауссу. Используя результаты гауссовского распространения, раздел (8.6.3), выведите альтернативное выражение для log p(y1 , . . . , yN |x1 , . . . , xN ).
248 ПРОЕКТ от 9 марта 2010 г.,
10-12Байесовские рассуждения смыслы и машинное обу
© Copyright: Джон Темплтон, 2025
Свидетельство о публикации №125110906776
Свидетельство о публикации №125110906776
Рецензии