часть II
Обучение в вероятностных моделях
137
ГЛАВА 8
Статистика для машинного обучения:
8.1 Распределения
Определение 54 (Кумулятивная функция распределения). Для одномерного распределения p(x) CDF определяется как
Для неограниченной области cdf (;;) = 0 и cdf (;) = 1.
8.2Обобщение распределений
Определение 55 (Режим). Режим x; распределения p(x) - это состояние x, при котором распределение принимает наибольшее значение, x; = argmax p(x). Распределение может иметь более одного узла (быть мультимодальным). Широко распространенное злоупотребление терминологией заключается в том, что любой изолированный локальный максимум p(x) называют модой.
Определение 56 (Средние значения и математическое ожидание).
обозначает среднее значение или математическое ожидание f (x) по отношению к распределению p(x). Распространенным альтернативным обозначением является
Когда контекст понятен, можно отказаться от нотационной зависимости от p(x). Обозначение
является сокращением для среднего значения f (x), обусловленного знанием состояния переменной y, т.е. среднего значения f (x) по отношению к распределению p(x|y).
139 Суммирование распределений
Преимущество математических ожиданий заключается в том, что они сохраняются независимо от того, является ли распределение более непрерывным или дискретных переменных. В дискретном случае
и для непрерывных переменных,
Читатель может задаться вопросом, что означает <x>, когда x является дискретным. Например, если dom(x) = {яблоко, апельсин, груша}, с соответствующими вероятностями p(x) для каждого из состояний, к чему относится <x>? Очевидно, что <f (x)> имеет смысл, если f (x = x) преобразует состояние x в числовое значение. Например f (x = яблоко) = 1, f (x = апельсин) = 2, f (x = груша) = 3, для которых значение <f (x)> имеет смысл. Если только значение состояния дискретной переменной связаны с числовым значением, тогда <x> не имеет значения.
Определение 57 (Моменты). k-й момент распределения определяется как среднее значение xk по распределению:
Для k = 1 мы имеем среднее значение, обычно обозначаемое µ,
Определение 58 (Дисперсия и корреляция).
Квадратный корень из дисперсии ; называется стандартным отклонением. Обозначение var(x) также используется для того, чтобы подчеркнуть, для какой переменной вычисляется дисперсия. Читатель может показать, что эквивалентным выражением является
Для многомерного распределения используется матрица с элементами
где µi = <xi >называется ковариационной матрицей. Диагональные элементы ковариационной матрицы содержат дисперсию каждой переменной. Эквивалентным выражением является
Корреляционная матрица содержит элементы
где ;i - отклонение переменной xi . Корреляция представляет собой нормализованную форму ковариации, так что каждый элемент ограничен -1 ; ;ij ; 1.
140 ЧЕРНОВИК от 9 марта 2010 г. Обобщающие \Суммирующие распределения
Для независимых переменных xi и xj , xi ; xj |; ковариация ;ij равна нулю. Аналогично, независимые переменные имеют нулевую корреляцию - они "некоррелированы". Однако обратите внимание, что обратное, как правило, неверно – два переменные могут быть некоррелированными, но зависимыми. Особым случаем является случай, когда xi и xj распределены по Гауссу, тогда независимость эквивалентна некоррелированности, см. упражнение(81).
Определение 59 (Асимметрия и Эксцесс). Асимметрия \Скрученность - это мера асимметрии распределения:
, где ;2 - дисперсия x по отношению к p(x). Положительная асимметрия означает, что распределение имеет сильный сдвиг вправо. Аналогично, отрицательная асимметрия означает, что распределение имеет сильный сдвиг влево.
Эксцесс - это показатель того, насколько сильно распределение приближается к среднему значению:
Распределение с положительным эксцессом имеет большую массу вокруг своего среднего значения, чем гауссово распределение с таким же средним значением и дисперсией. Их также называют супергауссовыми. Аналогично, отрицательный эксцесс (субгауссово) распределение имеет меньшую массу вокруг своего среднего значения, чем соответствующее гауссово распределение. Эксцесс определяется таким образом, что гауссово распределение имеет нулевой эксцесс (что объясняет значение -3 в определении).
Определение 60 (Эмпирическое Распределение). Для набора точек данных x1 , ... , xN , которые являются состояниями случайной величины x, эмпирическое распределение имеет массу вероятности, равномерно распределенную по точкам данных, и нулевую в других местах.
Для дискретной переменной x эмпирическое распределение равно
, где N - количество точек данных.
Для непрерывного распределения мы имеем
, где ; (x) - Дельта-функция Дирака.
Выборочное среднее значение точек данных определяется по формуле
и выборочная дисперсия определяется по формуле
ПРОЕКТ от 9 марта 2010 г. 141 Подведение итогов \Суммирование распределений
Для векторов выборочный вектор среднего значения содержит элементы
, и выборочная ковариационная матрица содержит элементы
Определение 61 (Дельта-функция). Для непрерывной функции x мы определяем дельта-функцию Дирака
;(x ; x0 ) (8.2.21)
которое равно нулю везде, где ожидается точка x0 , где происходит скачок.
и
Дельта;функцию Дирака можно представить в виде бесконечно узкой гауссовой функции:
Дельта Кронекера,
аналогично равны нулю везде, за исключением ;x0 ,x0 = 1. Дельта Кронекера эквивалентна ;x,x0 = I [x = x0 ]. Мы используем выражение ; (x, x0 ) для обозначения дельты Дирака или Кронекера, в зависимости от контекста.
8.2.1 Оценщик смещения
Определение 62 (Несмещенная оценка). Учитывая данные X = x1 , . . . , xN , из распределения p(x|;) мы можем использовать данные X для оценки параметра ;, который использовался для генерации данных. Оценщик - это функция из данных, которые мы записываем ^;(X ). Для получения несмещенной оценки
В более общем плане, рассмотрим любую функцию оценки ^;(X ) данных. Это несмещенная оценка величины ;, если <^;(X )>p(x)= ;.
Рисунок 8.1: Эмпирическое распределение по дискретной переменной с 4 состояниями. Эмпирические выборки состоят из n выборок в каждом из состояний 1, 2, 4 и 2n выборок в состоянии 3, где n > 0. При нормализации это дает распределение со значениями 0.2, 0.2, 0.4, 0.2 по 4 состояниям.
ЧЕРНОВИК от 9 марта 2010 г. 142 Дискретные распределения
Классическим примером погрешности оценки являются среднее значение и дисперсия. Пусть
Это несмещенная оценка среднего значения <x>p(x), поскольку
С другой стороны, рассмотрим оценку дисперсии,
Это искажение, поскольку (пропущено несколько строк алгебры)
8.3 Дискретные распределения
Определение 63 (Распределение Бернулли). Распределение Бернулли относится к дискретной двоичной переменной x, где dom(x) = {0, 1}. Состояния являются не просто символическими, а реальными значениями 0 и 1.
p(x = 1) = ; (8.3.1)
Из нормализации следует, что p(x = 0) = 1 ; ;. Отсюда
<x> = 0 ; p(x = 0) + 1 ; p(x = 1) = ; (8.3.2)
Дисперсия задается как var(x) = ; (1 ; ;).
Определение 64 (Категориальное распределение). Категориальное распределение обобщает распределение Бернулли на более чем два (символических) состояния. Для дискретной переменной x с символическими состояниями dom(x) = {1, . . . , C},
Уравнение Дирихле сопряжено с категориальным распределением.
Определение 65 (Биномиальное Распределение). Биномиал описывает распределение дискретной переменной x с двумя состояниями, где dom(x) = {1, 0}, где состояния являются символическими. Вероятность того, что в n испытаниях Бернулли (независимых выборках) будет наблюдаться k состояний успеха 1, равна
ПРОЕКТ от 9 марта 2010 г. 143 Непрерывные Распределения
, где (n k) это биномиальный коэффициент. Среднее значение и дисперсия равны
Бета-распределение является сопряженным, предшествующим Биномиальному распределению.
Определение 66 (Мультиномиальное распределение). Рассмотрим переменную с несколькими состояниями x, где dom(x) = {1, . . . , K}, с соответствующими вероятностями состояний ;1 , . . . , ;K . Затем мы берем n выборок из этого распределения. Вероятность наблюдения состояния 1 y1 раз, состояния 2 y2 раз, . . . , состояния K yK раз в n выборках равна
где
Распределение Дирихле является сопряженным априорным для полиномиального распределения.
Определение 67 (Распределение Пуассона). Распределение Пуассона можно использовать для моделирования ситуаций, в которых ожидаемое количество событий зависит от длины интервала, в течение которого события могут произойти. Если ; - ожидаемое число событий на единичный интервал, то распределение числа событий x в интервале t; равно
Для интервала единичной длины (t = 1)
Распределение Пуассона может быть получено как предельный случай Биномиального распределения, в котором вероятность успеха измеряется как ; = ;/n в пределе n ; ;.
8.4 Непрерывные распределения
8.4.1 Ограниченные распределения
Определение 68 (Равномерное распределение). Для переменной x распределение является равномерным, если p(x) = const во всей области действия переменной.
Определение 69 (Экспоненциальное Распределение). При x ; 0
Можно показать, что для скорости ;
144 ЧЕРНОВИК от 9 марта 2010 г. Непрерывные распределения
Рисунок 8.2: (а): Экспоненциальное распределение. (b): Распределение по Лапласу (двойная экспонента).
Альтернативная параметризация b = 1/; называется шкалой.
Определение 70 (Гамма-Распределение).
; называется параметром формы, ; - параметром масштаба и
Параметры связаны со средним значением и дисперсией через
где µ - среднее значение распределения, а s - стандартное отклонение. Режим \мода\ задается как (; ; 1) ;, для ; ; 1.
Альтернативная параметризация использует обратную шкалу
Определение 71 (Обратное Гамма-распределение).
Это означает среднее значение ;/(; ; 1) для ; > 1 и дисперсию ;2 /(;;1)2 /(;;2) для ; > 2.
Определение 72 (Бета-распределение).
где бета-функция определяется как
ЧЕРНОВИК от 9 марта 2010 года 145 Непрерывные распределения
а ;(x) - это гамма-функция. Обратите внимание, что распределение можно изменить, заменив x на 1 ; x, что эквивалентно замене ; и ;.
Среднее значение задается через
8.4.2 Неограниченные распределения
Определение 73 ((Двойное Экспоненциальное) Распределение Лапласа).
Для шкалы b
Одномерное Гауссово распределение
Гауссово распределение является важным распределением в науке. Его техническое описание приведено в определении (74).
Определение 74 (Одномерное гауссово распределение).
где µ - среднее значение распределения, а ;2 - дисперсия. Это также называется нормальным распределением.
Можно показать, что параметры действительно соответствуют
При µ = 0 и ; = 1 гауссово распределение называется стандартным нормальным распределением.
Определение 75 (t-распределение Стьюдента).
Рисунок 8.3: (а): Гамма- распределение с изменяющимся ; для фиксированного ;. (b): Гамма-распределение с изменяющимся ; при фиксированном ;.
ЧЕРНОВИК от 9 марта 2010 г. Многомерные дистрибутивы \Распределения
Рисунок 8.4: Вверху: 200 точек данных x1 , . . . , x200, взятых из Гауссова распределения. Каждая вертикальная линия обозначает точку данных с соответствующим значением x на горизонтальной оси. По средине: Гистограмма с использованием 10 равномерно расположенных ячеек точек данных. Внизу: гауссово распределение N (x |µ = 5, ; = 3), из которого были взяты 15 точек данных. В условиях неограниченного объема данных и ограниченно малого размера ячейки нормализованная гистограмма стремится к гауссовой функции плотности вероятности.
где µ - среднее значение, ; - степени свободы, а ; масштабирует распределение. Дисперсия задается как
При ; ; ; распределение стремится к гауссову со средним значением µ и дисперсией 1/;. При уменьшении ; хвостыраспределения становятся толще.
t-распределение может быть получено из масштабированной смеси
Обычно для повторной настройки используют значения ; = 2a и ; = a/b.
8.5 Многомерные распределения
Определение 76 (Распределение Дирихле). Распределение Дирихле - это распределение вероятностных распределений
, где
Принято обозначать распределение как
ЧЕРНОВИК от 9 марта 2010 г. Многомерный гауссовский
Рисунок 8.5: Распределение Дирихле с параметрами (u1 , u2 , u3 ), отображаемыми на симплексе x1 , x2 , x3 ; 0, x1 + x2 + x3 = 1. Черный цвет обозначает низкую вероятность, а белый - высокую вероятность. (a): (3, 3, 3) (b): (0.1, 1, 1). (c): (4, 3, 2). (d): (0.05, 0.05, 0.05).
Параметр u определяет, насколько сильно масса распределения смещена к углам симплекса. Значение uq = 1 для всех q соответствует равномерному распределению, рис.8.5. В бинарном случае Q = 2 это эквивалентно Бета-распределению.
Произведение двух распределений Дирихле равно
Маргинал Дирихле:
Предельное значение одного компонента ;i - это Бета - распределение:
8.6 Многомерный гауссовский
Многомерная функция Гаусса играет центральную роль на протяжении всей этой книги, и поэтому мы довольно подробно обсуждаем ее свойства.
Определение 77 (Многомерное Распределение Гаусса).
где µ - средний вектор распределения, а ; - ковариационная матрица. Обратная ковариация ;;1 называется точностью.
Можно показать
148 ЧЕРНОВИК от 9 марта 2010 года Многомерный гауссовский
Рисунок 8.6: (а): Двумерная гауссова функция со средним значением (0, 0) и ковариацией [1, 0.5; 0.5, 1.75]. На вертикальной оси отложено значение плотности вероятности p(x). (b): Контуры плотности вероятности для одной и той же двумерной гауссовой функции. На графике представлены единичные собственные векторы, масштабированные по квадратному корню из их собственных значений ; ;i .
Многомерный гауссиан приведен в определении(77). Обратите внимание, что det (;M) = ;D det (M), где M - матрица D; D, что объясняет не зависящее от размерности обозначение в константе нормализации определения(77).
В моментном представлении используются µ и ; для параметризации гауссовой функции. Альтернативное каноническое представление
связано с представлением момента через
Многомерный гауссиан широко используется, и это полезно для понимания геометрической картины. Это можно получить, просмотрев распределение в другой системе координат. Сначала мы используем, что каждая вещественная симметричная матрица D ; D имеет собственное разложение
где ET E = I и ; = diag (;1 , . . . , ;D ). В случае ковариационной матрицы все собственные значения ;i положительны. Это означает, что можно использовать преобразование
так, что
При таком преобразовании многомерный гауссиан сводится к произведению D одномерных Гауссиан с нулевой средней единичной дисперсией (поскольку Якобиан преобразования является константой). Это означает, что мы можем рассматривать многомерную Гауссову систему как сдвинутую, масштабированную и повернутую версию изотропной Гауссовой системы, в которой центр задается средним значением, поворот - собственными векторами, а масштаб - квадратным корнем из собственных значений, как показано на рис. 8.6, b).
Изотропный означает ‘одинаковый при вращении’. Для любого изотропного распределения контуры с равной вероятностью являются сферическими вокруг начала координат.
Ниже приведены некоторые полезные свойства гауссовой функции:
ПРОЕКТ от 9 марта 2010 г. 149 Многомерная гауссова функция
Определение 78 (Разделенная гауссова функция). Для распределения N (z µ, ;), определенного совместно по двум векторам x и y потенциально различных размерностей,
с соответствующим средним значением и разделенной ковариацией
где ;yx ;;Txy . Предельное распределение задается формулой
и условным
Определение 79 (Произведение двух Гауссиан). Произведение двух гауссианов равно другому гауссиану с мультипликативным коэффициентом, упражнение(114):
где S ; ;1 + ;2 , а среднее значение и ковариация задаются формулой
Определение 80 (Линейное преобразование гауссовой функции). Для линейного преобразования
где x ~ N (x| µ, ;),
Определение 81 (Энтропия гауссовой функции). Дифференциальная энтропия многомерной гауссовой функции p (x) = N (x| µ, ;) равна
где D = dim x. Обратите внимание, что энтропия не зависит от среднего значения µ.
150 ЧЕРНОВИК от 9 марта 2010 года Многомерный гауссовский
Рисунок 8.7: Бета-распределение. Параметры ; и ; также могут быть изменены с точки зрения среднего значения и вариации, что приводит к альтернативной параметризации, см. упражнение(94).
8.6.1 Обусловливание как обращение системы
Для совместного распределения p(x, y) рассмотрим условное p(x|y). Статистику p(x|y) можно получить, используя линейную систему вида
где
и этот обратный шум не коррелирует с y.
Чтобы показать это, нам нужно привести статистику x в соответствии с этой линейной системой в соответствие с данными, приведенными в операции кондиционирования, (8.6.11). Среднее значение линейной системы определяется как
и ковариации (обратите внимание, что изменение системы не влияет на ковариацию y)
Из уравнения (8.6.21) мы имеем
которое, используя в уравнении (8.6.20), дает
Используя уравнение (8.6.19), мы аналогично получаем
Это означает, что мы можем написать явную линейную систему уравнений вида (8.6.17), где параметры заданы в терминах статистики исходной системы. Эти результаты являются лишь повторным изложением результатов моделирования, но показывают, как их можно интерпретировать как линейную систему. Это полезно при выводе результатов в Линейных Динамических Системах.
8.6.2 Завершение квадрата
Полезным приемом при манипулировании гауссианами является завершение квадрата. Например, выражение
можно преобразовать следующим образом. Сначала мы завершаем квадрат:
Следовательно,
Из этого можно вывести
ПРОЕКТ от 9 марта 2010 г. 151 Многомерный гауссовский
8.6.3 Гауссово распространение
Пусть y линейно связано с x через
где ; ~ N (µ, ;) и x ~ N (µx , ;x ).
Тогда предельное значение p(y) =;x p(y|x)p(x) является Гауссовым
8.6.4 Отбеливание и центрирование
Для набора данных x1 , . . . , xN с dim xn = D мы можем преобразовать эти данные в y1 , . . . , yN с нулевым средним значением, используя центрирование:
где среднее значение m данных задается через
Кроме того, мы можем преобразовать значения z1 , . . . , zN, которые имеют нулевое среднее значение и единичную ковариацию, используя отбеливание
где ковариация S данных задается формулой
Эквивалентный подход заключается в вычислении SVD-декомпозиции матрицы центрированных точек данных
затем
имеет нулевое среднее значение и единичную ковариацию, см. упражнение(111).
8.6.5 Обучение с максимальным правдоподобием
Учитывая набор обучающих данных X = {x1 , . . . , xN }, полученных из гауссовой функции N (x| µ, ;) с неизвестным средним значением µ и ковариацией ;, как мы можем найти эти параметры? Предполагая, что данные получены в режиме реального времени, логарифмическая правдоподобность равна
152 ЧЕРНОВИК от 9 марта 2010 Многомерный гауссовский
Оптимальный µ
Взяв частную производную по вектору µ, получим векторную производную
Приравнивание к нулю дает, что при оптимуме логарифмического правдоподобия
и, следовательно, оптимально
Оптимальное ;
Производная от L по матрице ; требует дополнительной работы. Удобно изолировать зависимость от ковариации, а также параметризовать, используя обратную ковариацию, ;;1 ,
Используя M = MT , мы получаем
Приравнивание производной к нулевой матрице и решение для ; дает
Уравнения (8.6.40) и (8.6.43) определяют среднее значение решения с максимальным правдоподобием и ковариацию для обучающих данных X. В соответствии с нашими предыдущими результатами, на самом деле эти уравнения просто устанавливают параметры для своей выборочной статистики эмпирического распределения. То есть среднее значение задается как среднее значение выборки данных, а ковариация - как ковариация выборки.
8.6.6 Байесовский вывод среднего значения и дисперсии
Для простоты здесь мы рассматриваем одномерный случай. Предполагая, что исходные данные верны, вероятность равна
Для байесовской обработки нам требуется апостериорный из параметров
Наша цель - найти сопряженные априорные значения для среднего значения и дисперсии. Удобный выбор априора для среднего значения µ заключается в том, что это гауссиан, центрированный на µ0 :
ЧЕРНОВИК от 9 марта 2010 года 153 Многомерный гауссовский
Тогда апостериорный
Удобно записать это в виде
Поскольку уравнение (8.6.47) имеет квадратичный вклад в µ в показателе степени, условное апостериорное значение p (µ |;2 , X ) является гауссовым. Чтобы определить это значение Гаусса, мы перемножаем члены в показателе степени, чтобы получить
при
Используя идентификатор
мы можем написать
Мы сталкиваемся с трудностями при попытке найти сопряженный априор для ;2 , поскольку член b2 /a не является простым выражением ;2 . По этой причине мы ограничиваем
для некоторого фиксированного гиперпараметра ;. Определение констант
у нас есть
Используя это выражение в уравнении (8.6.52), получаем
Таким образом, если мы используем обратное гамма-распределение, то получим сопряженный априор для ;2 . Для априора Гаусса-Обратной Гаммы:
задняя часть \ постериор\ также является Обратной по Гауссу Гаммой с
154 ЧЕРНОВИК от 9 марта 2010 г. Представительная семья
8.6.7 Гамма-распределение Гаусса
Обычно используется предварительное значение точности, определяемое как обратная дисперсия
Если мы затем используем предварительную гамму
Апостериорное значение будет
где
Априорное распределение по Гауссовой Гамме
является сопряженным априором для гауссова уравнения с неизвестным средним значением µ и точностью ;.
Апостериор для этого априора представляет собой Гамма-распределение Гаусса с параметрами
Предельное значение p(µ|X , µ0 , ;, ;, ;) представляет собой t-распределение Стьюдента. Пример априорного/апостериорного решения с использованием гаммы Гаусса приведен на рис. 8.8.
Решение с максимальным правдоподобием восстанавливается в пределе ‘плоского’ (неправильного) априора µ0 = 0, ; ; ;, ; = 1/2, ; ; ;, смотрите упражнение(102). Несмещенные оценки для среднего и дисперсии даны с использованием соответствующих предварительных значений µ0 = 0, ; ; ;, ; = 1, ; ; ;, упражнение (103).
Для многомерного случая расширение этих методов использует многомерное Гауссово распределение для сопряженного априора по среднему значению и обратное распределение Уишарта для сопряженного априора по ковариации[124].
8.7 Экспоненциальное Семейство
Теоретически удобным классом распределений является экспоненциальное семейство, которое содержит множество стандартных распределений, включая гауссово, гамма-, Пуассоново, Дирихле, Уишарта, Мультиномиальное, Марковское Случайное Поле.
Определение 82 (Экспоненциальное семейство). Для распределения по (возможно, многомерной) переменной x (непрерывной или дискретной) экспоненциальная модель семейства имеет вид
; - это параметры, Ti (x) - статистика тестирования, а ; (;) - функция разбиения журнала на разделы, обеспечивающая нормализацию
ЧЕРНОВИК от 9 марта 2010 г. 155 Экспоненциальные семейства
(а) Предыдущее (б) Последующее
Рисунок 8.8: Байесовский подход к определению среднего значения и точности (обратной дисперсии) Гауссова уравнения на основе N = 10 случайно выбранных точек данных. (а): Предварительная Гамма по Гауссу с µ0 = 0, ; = 2, ; = 1, ; = 1. (b): Последующая Гамма по Гауссу, зависящая от данных. Для сравнения выборочное среднее значение данных равно 1,87, а оптимальная дисперсия с Максимальным Правдоподобием равна 1,16 (вычисляется с использованием нормализации N). 10 точек данных были получены из Гауссова уравнения со средним значением 2 и дисперсией 1. Смотрите demoGaussBayes.m.
Всегда можно преобразовать параметры в виде ; (;) = ;. в этом случае распределения каноническая форма:
Например, одномерный гауссиан может быть записан в виде
Определяя
тогда
Обратите внимание, что параметризация не обязательно уникальна – мы можем, например, перемасштабировать функции Ti (x) и обратно масштабировать ;i на ту же величину, чтобы получить эквивалентное представление.
8.7.1 Сопряженные априорные значения
В принципе, байесовское обучение для экспоненциального семейства является простым. В канонической форме
Для априора с гиперпараметрами ;, ;,
обратная сторона \постериор\
таким образом, предыдущее уравнение (8.7.7) сопряжено с уравнением правдоподобия экспоненциального семейства (8.7.6). Хотя вероятность относится к экспоненциальному семейству, сопряженное предыдущее не обязательно относится к экспоненциальному семейству.
156 ДРАФТ от 9 марта 2010 г. Дивергенция Кульбака-Лейблера КЛ(q|p)
8.8 Дивергенция Кульбака-Лейблера KL(q|p)
Дивергенция Кульбака-Лейблера KL(q|p) измеряет ‘разницу’ между распределениями q и p[68].
Определение 83. Расхождение KL для двух распределений q(x) и p(x)
где <f (x)>r(x) обозначает среднее значение функции f (x) по отношению к распределению r(x).
Расхождение KL ; 0
Расхождение KL широко используется, и поэтому важно понимать, почему расхождение является положительным.
Чтобы убедиться в этом, рассмотрим следующую линейную привязку функции log(x)
как показано на рисунке справа. Заменим x на p(x)/q(x) в приведенной выше привязке
Поскольку вероятности неотрицательны, мы можем умножить обе части на q(x), чтобы получить
Теперь мы интегрируем (или суммируем в случае дискретных переменных) обе части. Используя ; p(x)dx = 1, ;q(x)dx = 1,
Перестановка дает
Расхождение KL равно нулю тогда и только тогда, когда два распределения в точности совпадают.
8.8.1 Энтропия
Как для дискретных, так и для непрерывных переменных энтропия определяется как
Для непрерывных переменных это также называется дифференциальной энтропией, смотрите также упражнение(113). Энтропия является мерой неопределенности в распределении. Один из способов убедиться в этом заключается в том, что
где u - равномерное распределение. Поскольку KL(p|u) ; 0, чем меньше p похоже на равномерное распределение, тем меньше будет энтропия. Или, наоборот, чем больше p похоже на равномерное распределение, тем больше будет равна энтропии. Поскольку равномерное распределение содержит наименьшую информацию о том, в каком состоянии находится p(x), энтропия, следовательно, является мерой априорной неопределенности в отношении занятости состояния. Для дискретного распределения мы можем переставлять метки состояний без изменения энтропии. Для дискретного распределения энтропия положительна, тогда как дифференциальная энтропия может быть отрицательной.
ЧЕРНОВИК от 9 марта 2010 г. 157 Упражнение
8.9 Код
demoGaussbayes.m: Байесовская подгонка одномерной Гауссовой
logGaussGamma.m: Процедура построения графика для Гамма-распределения Гаусса
8.10 Упражнения
Упражнение 80. На публичной лекции профессор экспериментальной психологии произнес следующую фразу: "Согласно недавнему опросу, 90% людей утверждают, что их интеллект выше среднего, что явно является чепухой!’ [Смех в аудитории]. Теоретически возможно ли, чтобы 90% людей обладали интеллектом выше среднего? Если да, то приведите пример, а в противном случае объясните, почему нет. Как насчет интеллекта выше среднего? Упражнение 81. Рассмотрим распределение, определенное для реальных переменных x, y:
Покажите, что <x> = <y> = 0. Кроме того, покажите, что x и y не связаны, <xy> = <x> <y>. Хотя x и y не связаны, покажите, что они, тем не менее, зависят друг от друга.
Упражнение 82. Для переменной x с dom(x) = {0, 1} и p(x = 1) = ; покажите, что при n независимых выводах x1 , . . . , xn из этого распределения, вероятность наблюдения k состояний 1 является Биномиальным распределением
Упражнение 83 (Константа нормализации гауссова распределения). Константа нормализации гауссова распределения связана с интегралом
Рассматривая
и преобразуя в полярные координаты, покажем, что
Упражнение 84. Для одномерного гауссова распределения покажите, что
Упражнение 85. Покажите, что граница распределения Дирихле является другим распределением Дирихле:
Упражнение 86. Для Бета-версии покажите, что
и, используя ;(x + 1) = x;(x), выведите явное выражение для k-го момента Бета- распределения.
158 ЧЕРНОВИК от 9 марта 2010 г. Упражнения
Упражнение 87. Определим функцию, генерирующую момент, как
Показывать что
Упражнение 88 (Смена переменных). Рассмотрим одномерную непрерывную случайную величину x с соответствующим значением p(x). Для переменной y = f (x), где f (x) - монотонная функция, покажите, что распределение y является
Упражнение 89 (Нормализация многомерной гауссовой функции). Считать
Используя преобразование
показывать что
Упражнение 90. Рассмотрим секционированную матрицу
для которой мы хотим найти обратное значение M;1 . Мы предполагаем, что A равно m ; m и обратимо, а D равно n ; n и обратимо. По определению, разделенное обратное
должен удовлетворять
где - единичная матрица m ; m той же размерности, что и А, а 0 - нулевая матрица того же размера, что и D. Используя вышеизложенное, можно получить результаты
Упражнение 91. Покажите, что для гауссова распределения p(x) =N( x| µ, ;2 ) асимметрия и эксцесс равны ноль.
Упражнение 92. Рассмотрим небольшой интервал времени ;t и определим вероятность того, что событие произойдет в течение этого промежутка времени как ;;t. Выведите распределение, которое выражает вероятность по крайней мере одного события через определенный промежуток времени от 0 до t.
Черновик от 9 марта 2010 года 159 Упражнения
Упражнение 93. Рассмотрим векторную переменную x = (x1 , . . . ,xn) набор функций, определенных для каждого компонента из x, ;i (xi ). Например, для x = (x1 , x2) мы имеем
Рассмотрим распределение
где ;(x) - векторная функция с i-й составляющей ;i (xi), и ;- вектор параметров. Каждый компонент это интегрирует в том смысле, что
это может быть вычислено аналитически или с приемлемой численной точностью. Показать что
1. xi ; x2 | ; .
2. Константа нормализации Z может быть легко вычислена.
3. Рассмотрим трансформацию
Для обратимой матрицы M. Показать, что распределение p(y|M,;) является управляемым\ прогонным (его константа нормализации известна, и что, в общем случае, yi ;yi | ;. Объяснить значение этого, выведя управляемые\ прогонные, проходимые\ многомерные распределения.
Упражнение 94. Покажите, что мы можем повторно параметризовать Бета-распределение, определение (72), записав паpaметры ; и ; ,- как функции среднего значения m и дисперсии s , используя
Упражнение 95. Рассмотрим функцию
показать, что
следовательно, что
Используя этот результат, показать таким образом что
где B(;, ;) - Бета-функция. Показать дополнительно, что
Используя тот факт, что
Где ; (x) - Гамма-функция, Называемая функцией дигаммы, определяемая как
160 Черновик от 9 марта 2010 года Упражнения
Упражнение 96. Используя аналогичный подход "генерирующей функции", как в упражнении (95), как объясните как рассчитать
Упражнение 97. Рассмотрим функцию
Покажите, что преобразование Лапласа f (x),
есть
Используя обратное преобразование Лапласа, покажем, что
Следовательно, покажите, что константа нормализации распределения Дирихле с параметрами u задается через
Упражнение 98. Используя преобразование Лапласа, как в упражнении (97), покажите, что граница\ предльное значение, маржинал\ распределения Дирихле является распределением Дирихле.
Упражнение 99. Выведите формулу для дифференциальной энтропии многовариантного гауссова уравнения.
Упражнение 100. Покажите, что для гамма;распределения Gam (x|;, ;) режим задается через
x; = (; - 1) ; (8.10.34)
при условии, что ; ; 1.
Упражнение 101. Рассмотрим распределение p(x|;) и распределение с ;, измененным на небольшую величину ;. Возьмем разложение Тейлора для
KL(p(x|;)|p(x|; + ;)) (8.10.35)
для малого ; и покажем, что оно равно
В более общем плане для распределения, параметризованного вектором ;i + ;i , покажите, что небольшое изменение параметра приводит к
, где Информационная Матрица Фишера определяется как
Покажите, что информационная матрица Фишера является положительной (полуопределенной), выразив ее эквивалентно как
ЧЕРНОВИК от 9 марта 2010 г. 161 Упражнения
Упражнение 102. Рассмотрим совместное предыдущее распределение
Покажите, что при µ0 = 0, ; ; ;, ; ; ; предыдущее распределение становится "плоским" (не зависящим от µ и ;) при ; = 1/2. Покажите, что при этих настройках среднее значение и дисперсия, которые совместно максимизируют апостериорное уравнения (8.6.64) задаются стандартными настройками Максимального Правдоподобия
Упражнение 103. Покажите, что в пределе µ0 = 0, ; ; ;, ; = 1, ; ; ; совместное оптимальное среднее значение и дисперсия, полученные из
задаются формулой
где ;;2 = 1/;; . Обратите внимание, что они соответствуют стандартным "несмещенным" оценкам среднего значения и дисперсии.
Упражнение 104. Для заднего значения Гауссовой Гаммы p (µ, ;|µ0, ;, ;, X ), приведенного в уравнении (8.6.64), вычислите предельное заднее значение p(µ|µ0 , ;, ;, X). Каково среднее значение этого распределения?
Упражнение 105. Выведите уравнение (8.6.30).
Упражнение 106. Рассмотрим многомерное гауссово распределение p(x) ~N (x |µ, ;) на векторе x с компонентами x1 , . . . , xn :
Вычислить p(xi |x1 , . . . , xi;1 , xi+1 , . . . , xn ).
Упражнение 107. Наблюдения y0 , . . . , yn;1 представляют собой зашумленные внутренние измерения базовой переменной x с p(x) ~ N( x| 0, ;02) и p(yi |x) ~ N (yi| x, ;2) для i = 0, . . . , n;1. Покажите, что p(x|y0 , . . . , yn;1 ) является Гауссовым со средним значением
где -y = (y0 + y1 + . . . + yn;1 )/n и дисперсия ;n2 такая, что
Упражнение 108. Рассмотрим набор данных x1 , . . . , xN, полученных по Гауссу с известным средним значением µ и неизвестной дисперсией ; 2 . Предположим, что гамма-распределение предшествовало по ; = 1/;2 ,
1. Покажите, что апостериорное распределение равно
162 ЧЕРНОВИК от 9 марта 2010 г. Упражнения
2. Покажите, что распределение для x равно
Упражнение 109. Распределение Пуассона - это дискретное распределение целых неотрицательных чисел, где
Вам предоставляется выборка из n наблюдений x1 , . . . , xn, взятых из этого распределения. Определите максимальную вероятностную оценку параметра Пуассона ;.
Упражнение 110. Для модели гауссовой смеси
показать, что p(x) имеет среднее значение
и ковариация
Упражнение 111. Покажите, что для выбеленной матрицы данных, приведенной в уравнении (8.6.36), ZZT = N I.
Упражнение 112. Рассмотрим равномерное распределение pi = 1/N, определенное для состояний i = 1, . . . , N . Показать, что энтропия этого распределения равна
, и это означает, что при увеличении числа состояний N до бесконечности энтропия уменьшается до бесконечности.
Упражнение 113. Рассмотрим непрерывное распределение p(x), x ; [0, 1]. Мы можем сформировать дискретное приближение с вероятностями pi к этому непрерывному распределению, определив непрерывное значение i/N для каждого состояния i = 1, . . . , N . При этом
покажем, что энтропия H = ;; i pi log pi определяется как
Поскольку для непрерывного распределения
дискретная аппроксимация этого интеграла в ячейках размером 1/N дает
ЧЕРНОВИК от 9 марта 2010 г. 163 Упражнения
Следовательно, для больших N
, где константа стремится к бесконечности при N ; ;. Обратите внимание, что этот результат говорит о том, что непрерывное распределение имеет особенно, по существу, бесконечное число состояний, степень неопределенности в распределении бесконечна (в качестве альтернативы, нам потребовалось бы бесконечное количество битов, чтобы задать непрерывное значение). Это мотивирует определение дифференциальной энтропии, которое пренебрегает бесконечной константой в предельном случае дискретной энтропии.
Упражнение 114. Рассмотрим два многомерных Гауссиана N (x |µ1 , ;1 ) и N (x |µ2 , ;2 ).
1. Покажите, что логарифмическое произведение двух Гауссианов задается формулой
2. Определив
мы можем записать вышеизложенное в виде
Запись ; = A;1 и µ = A;1b показывает, что произведение гауссианов является гауссианом с ковариацией
среднее значение
и логарифмический предиктор \префактор\
3. Покажите, что это можно записать как
Упражнение 115. Покажите, что
164 ЧЕРНОВИК от 9 марта 2010 года
9 глава
Обучение как вывод
9.1 Обучение как логический вывод
В предыдущих главах мы в основном предполагали, что все распределения полностью определены для задач логического вывода. Однако в машинном обучении и смежных областях распределения необходимо обучать на основе данных. Таким образом, обучение - это проблема интеграции данных со знаниями предметной области в среде моделирования.
Определение 84 (Первичные и вторичные данные). Первичные и вторичные данные обычно относятся к распределениям параметров до (до) и после (после) просмотра данных. Формально правило Байеса связывает их через
где ; - интересующий параметр, а V представляет наблюдаемые (видимые) данные.
9.1.1 Обучение смещения монеты
Рассмотрим данные, выражающие результаты подбрасывания монеты. Мы записываем v n = 1, если при подбрасывании n монета выпадает выпадет орел, а vn = 0, если выпадет решка. Наша цель – оценить вероятность ; того, что монета выпадет орлом, p(vn = 1|;) = ;- это называется "смещением" монеты. Для честной игры ; = 0,5. Переменными в этой среде являются v1 , ... , vN и ;, и нам требуется модель вероятностного взаимодействия переменных p(v1 , ... , vN , ;). Предполагая, что между наблюдаемыми бросками нет никакой зависимости, кроме как через ;, мы имеем Сеть Убеждений
который изображен на рис. 9.1. Предположение о том, что каждое наблюдение распределяется одинаково и независимо, называется предположением i.i.d.
Обучение подразумевает использование наблюдений v1 , ... , vN для вывода ;. В этом контексте нас интересует
Нам все еще нужно полностью указать предыдущее значение p(;). Чтобы избежать сложностей, связанных с непрерывными переменными, мы рассмотрим дискретный ;, имеющий только три возможных состояния ; ; {0.1, 0.5, 0.8}. В частности, мы предполагаем, что
p(; = 0,1) = 0,15, p(; = 0,5) = 0,8, p(; = 0,8) = 0,05 (9.1.4)
165 Обучение как вывод
Рисунок 9.1: (а): Сеть Убеждений для модели подбрасывания монеты. (b): Обозначение
на табличке, эквивалентное (а). Табличка\ табло повторяет значения внутри таблички столько раз, сколько указано на табличке.
, как показано на рисунке(9.2a). Этот пример показывает, что мы на 80% уверены в том, что монета "честная", на 5% уверены, что монета выпадет орлом (при ; = 0,8), и на 15% уверены, что монета выпадет решкой (при ; = 0,1). Распределение ; с учетом имеющихся данных и наших убеждений таково
В приведенном выше ;Nn=1 I [v n = 1] - это количество вхождений заголовков, которое нам удобнее обозначить как NH . Аналогично, ;Nn=1 I [v n = 0] - это число хвостов, NT . Следовательно
Для эксперимента с NH = 2, NT = 8 апостериорное распределение равно
, где V - сокращение от v1 , . . . , v N . Исходя из требований нормализации, мы получаем 1/k = 6,46 ; 10-4 + 7.81 ; 10-4 + 8.19 ; 10-8 = 0.0014, так что
p(; = 0,1|V) = 0,4525, p(; = 0,5|V) = 0,5475, p(; = 0,8|V) = 0,0001 (9.1.11)
, как показано на рисунке(9.2b). Это "апостериорные" значения параметров. В этом случае, если бы нас попросили выбрать одно апостериорное наиболее вероятное значение для ;, оно было бы ; = 0,5, хотя наша уверенность в этом невелика, поскольку апостериорное предположение о том, что ; = 0,1, также заметно. Этот результат интуитивно понятен, поскольку, несмотря на то, что мы наблюдали больше решек, чем орлов, мы изначально полагали, что монета, скорее всего, честная.
Повторяя вышеописанное с NH = 20, NT = 80, заднее значение\ последующее, постериор\ изменяется на
p(; = 0,1|V) = 1-1,93;10-6 ,
p(; = 0,5|V) = 1,93;10-6 ,
p(; = 0,8|V) = 2,13;10-35 (9.1.12)
рис.(9.1в), так что преобладает апостериорная вера в ; = 0,1. Это разумно, поскольку в данной ситуации решка выпадает гораздо чаще, чем орел, и маловероятно, что это произойдет из-за честной игры. Хотя мы априори считали, что монета была честной, апостериори у нас есть достаточно доказательств, чтобы изменить свое мнение.
Рисунок 9.2: (а): Предварительное кодирование наших предположений о количестве орлов в монете . (b): Задняя часть, видевшая 2 орел и 8 решек. (c): Задний , видевший 20 голов и 80 хвостов.
ЧЕРНОВИК от 9 марта 2010 г. Обучение как вывод
9.1.2 Принятие решений
Сам по себе байесовский апостериор просто отражает наши убеждения и ничего не говорит о том, как наилучшим образом обобщить эти убеждения. В ситуациях, когда решения необходимо принимать в условиях неопределенности, нам необходимо дополнительно указать, в чем заключается полезность любого решения, как описано в главе (7).
В сценарии подбрасывания монеты, где ; принимается равным 0,1, 0,5 или 0,8, мы ставим задачу принятия решения следующим образом: если мы правильно определим смещение монеты, то получим 10 очков; если мы ошибемся, то потеряем 20 очков. Мы можем написать это, используя
где ;0 - истинное значение смещения. Ожидаемая полезность решения о том, что монета равна ; = 0,1, равна
U (; = 0,1) = U (; = 0,1, ;0 = 0,1)p(;0 = 0,1|В)
+ У (; = 0.1, ;0 = 0.5)п(;0 = 0.5|В) + у (; = 0.1, ;0 = 0.8)п(;0 = 0.8|в) (9.1.14)
Подставляя числа из уравнения (9.1.11), получаем
U (; = 0.1) = 10 ; 0.4525 ; 20 ; 0.5475 ; 20 ; 0.0001 = -6.4270
(9.1.15)
Аналогично
U (; = 0.5) = 10 ; 0.5475 ; 20 ; 0.4525 ; 20 ; 0.0001 = -3.5770 (9.1.16)
и
U (; = 0.8) = 10 ; 0.0001 ; 20 ; 0.4525 ; 20 ; 0.5475 = -19.999 (9.1.17)
Так что лучшим решением будет сказать, что монета является беспристрастной, ; = 0,5.
Повторив приведенные выше вычисления для NH = 20, NT = 80, мы получим
так что лучшим решением в этом случае будет выбрать ; = 0,1.
По мере получения дополнительной информации о распределении p(v, ;) апостериорное значение p(;|V) постоянно растет, что помогает нам в процессе принятия решений.
9.1.3 Совокупность параметров
В разделе(9.1.1) мы рассмотрели только три возможных значения ;. Здесь мы обсуждаем совокупность параметров.
Используя плоское априорное
Сначала мы рассмотрим случай "плоского" или однородного априорного значения p(;) = k для некоторой константы k. Для непрерывных переменных нормализация требует
Поскольку 0 ; ; ; 1,
ПРОЕКТ от 9 марта 2010 г. 167Обучение как вывод
Рисунок 9.3: Задняя точка \постериор \ p(;|V), предполагающая плоскость перед ;. (красный) NH = 2, NT = 8 и (синий) NH = 20, NT = 80. В обоих случаях наиболее вероятное значение апостериора равно 0,2, что интуитивно понятно, поскольку соотношение "Орел-решка" в обоих случаях равно 0,2. При наличии большего количества данных апостериор более достоверен и приближается к наиболее вероятному значению. Максимальное А апостериорное значение ; = 0,2 в обоих случаях, это значение ;, при котором апостериорное значение достигает своего максимального значения.
Повторяя предыдущие вычисления с этим плоским непрерывным априорным значением, мы получаем
где c ; константа, определяемая путем нормализации,
, где B(;, ;) - бета-функция.
Определение 85 (сопряженность). Если апостериорное значение имеет ту же параметрическую форму, что и предшествующее, то мы называем предшествующее сопряженным распределением для распределения правдоподобия\ вероятности.
Используя сопряженное предшествующее значение
Для определения константы нормализации непрерывного распределения требуется, чтобы можно было вычислить интеграл от ненормализованного апостериорного значения. В случае подбрасывания монеты ясно, что если априорное значение имеет форму бета-распределения, то апостериорная часть будет иметь ту же параметрическую форму:
задняя часть равна
так что
Предыдущий и последующий дистрибутивы имеют одинаковую форму (оба бета-дистрибутива), но просто с разными параметрами. Следовательно, бета-распределение "сопряжено" с биномиальным распределением.
9.1.4 Решения, основанные на непрерывных интервалах времени
В результате эксперимента с подбрасыванием монеты получилось NH = 2 орла и NT = 8 решек. Теперь вам нужно принять решение.- условие: вы выигрываете 10 долларов, если ваше предположение о том, что монета с большей вероятностью выпадет орлом, чем решкой, окажется верным. Если ваше предположение неверно, вы теряете миллион долларов. Каково ваше решение? (Предположим, что исходное значение неинформативно).
Нам нужны две величины: ; для нашей догадки и ;` для истины. Тогда полезность выражения "Орел" равна
168 ЧЕРНОВИК от 9 марта 2010 г. Максимальное апостериорное значение и максимальная вероятность
В приведенном выше примере
где Ix (a, b) - упорядоченная неполная Бета-функция. Для первого \бывшего\ случая, когда NH = 2, NT = 8, при плоском предыдущем значении,
Поскольку события являются исключительными, p(;0 ; 0,5|V) = 1 ; 0,9673 = 0,0327.
Следовательно, ожидаемая полезность высказывания "головы", скорее всего, заключается
в
Точно так же полезность высказывания "решка" с большей вероятностью заключается
в том, что
Таким образом, нам лучше принять решение о том, что монета, скорее всего, выпадет решкой.
Если мы изменим приведенное выше соотношение таким образом, что потеряем 100 миллионов долларов, если угадаем "решку", хотя на самом деле это будет "орел", ожидаемая полезность выражения "решка" составит -3,27 ; 106, и в этом случае нам лучше будет сказать "орел". В этом случае, несмотря на то, что мы более уверены в том, что монета, скорее всего, выпадет решкой, мы рискуем ошибиться, сказав "решка", и тогда лучше будет сказать "орел".
9.2 Максимальное Апостериорное Значение и Максимальная Вероятность
9.2.1 Подведение итогов последующего
Определение 86 (Максимальное Правдоподобие и Апостериорный Максимум). Максимальное Правдоподобие задает параметр ;, заданный данными V, используя
Апостериорный Максимум использует ту настройку ;, которая максимизирует апостериорное распределение параметра,
, где p(;) - предыдущее распределение.
Грубая сводка апостериорной функции представлена распределением, при котором вся ее масса находится в одном наиболее вероятном состоянии, ;(;, ;MAP ). При таком приближении потенциально полезная информация, касающаяся надежности часть оценки параметра теряется. В отличие от этого, полная апостериорная оценка отражает наши представления о диапазоне возможностей и связанной с ними достоверности.
Можно обосновать MAP с точки зрения теории принятия решений. Если мы предположим, что полезность равна нулю для всех значений, кроме правильного ;,
ЧЕРНОВИК от 9 марта 2010 г. 169 Максимальное апостериорное и максимальное правдоподобие
Рисунок 9.4: (а): Модель взаимосвязи между Раком легких, воздействием Асбеста и Курением. (b): Табличные обозначения, воспроизводящие наблюдаемые n точек данных и устанавливая приоритетные значения поверх CPT, привязанные ко всем точкам данных.
тогда ожидаемая полезность ; равна
Это означает, что решение максимальной полезности для возврата ; с наибольшим последовавшим значением \постериор.
При "плоском" приоре\ предшествующим значении\ p(;) = const \постоянная\ используется согласование MAP параметра равное установленному Максимуму Правдоподобности\Максимальной Вероятности
Термин "Максимальное правдоподобие" относится к параметру ;, для которого наблюдаемые данные с наибольшей вероятностью будут сгенерированы моделью.
Поскольку логарифм является строго возрастающей функцией, то для положительной функции f (;)
чтобы MAP параметры можно было найти либо путем оптимизации цели MAP, либо, что эквивалентно, путем ее логарифмирования,
где константа нормализации, p(V), не является функцией ;.
Логарифмическая вероятность удобна, поскольку в предположении i.i.d. это суммирование значений данных,
таким образом, такие величины, как производные логарифмического правдоподобия от w.r.t. ;, легко \в лоб , прямо \ вычисляются.
Пример 36. В эксперименте с подбрасыванием монеты из раздела (9.1.1) параметр ML равен ; = 0,2 в обоих NH = 2, NT = 8 и NH = 20, NT = 80.
9.2.2 Максимальное правдоподобие и эмпирическое распределение
Учитывая набор данных дискретных переменных X = {x1 , . . . , xN} , мы определяем эмпирическое распределение как
170 ЧЕРНОВИК от 9 марта 2010 г. Максимальное апостериорное и правдоподобное
Рисунок 9.5: База данных, содержащая информацию о воздействии Асбеста (1 означает воздействие), Курении (1 означает, что человек является курильщиком) и Раке легких (1 означает, что у человека рак легких). Каждая строка содержит информацию о конкретном человеке, так что в базе данных есть 7 человек.
в случае, если x - это вектор переменных,
Расхождение Кульбака-Лейблера между эмпирическим распределением q(x) и распределением p(x) равно
Наш интерес представляет функциональная зависимость KL(q|p) от p. Поскольку энтропийный член <log q(x) >q(x) не зависит от p(x), мы можем рассмотреть эту константу и сосредоточиться только на втором члене. Следовательно
Мы принимаем ; Nn=1 log p(xn) в качестве логарифмической вероятности в соответствии с моделью p(x), предполагая, что данные являются прямыми. Это означает, что установка параметров по максимальному правдоподобию эквивалентна установке параметров по минимальному правдоподобию.- вычисление расхождения Кульбака-Лейблера между эмпирическим распределением и параметризованным распределением. В случае, когда p(x) не ограничено, оптимальным выбором является значение p(x) = q(x), а именно максимальное значение оптимальное распределение вероятности соответствует эмпирическому распределению.
9.2.3 Тренировка сетей убеждений с максимальной вероятностью
Рассмотрим следующую модель взаимосвязи между воздействием асбеста (a), курением (s) и заболеваемостью раком легких (c)
p(a, s, c) = p(c|a, s)p(a)p(s) (9.2.13)
которая изображена на рис. 9.4, а. Каждая переменная является двоичной, dom(a) = {0, 1}, dom(s) = {0, 1}, dom(c) = {0, 1}.Мы предполагаем, что прямой связи между курением и воздействием асбеста нет. Это предположение, которое мы можем получить от медицинских экспертов. Кроме того, мы предполагаем, что у нас есть список записей пациентов, рис.9.5, где каждая строка представляет данные пациента. Чтобы узнать записи таблицы p(c|a, s), мы можем сделать это, подсчитав количество c, находящихся в состоянии 1, для каждого из 4 родительских состояний a и s:
Аналогично, на основе подсчета, p(a = 1) = 4/7 и p(s = 1) = 4/7. Затем эти три CPT заполняют
полную спецификацию дистрибутива.
Настройка записей CPT таким образом, путем подсчета относительного числа совпадений, математически соответствует обучению с максимальной вероятностью в предположении i.i.d., как мы покажем ниже.
Максимальная вероятность соответствует подсчету
Для BN существует ограничение на форму p(x), а именно
ПРОЕКТ от 9 марта 2010 г. 171 Максимальное Апостериорное и Максимальное Правдоподобие
Чтобы вычислить значение Максимального Правдоподобия для каждого члена p(xi |pa (xi )), как показано в разделе (9.2.2), мы можем эквивалентно минимизировать расхождение Кульбака-Лейблера между эмпирическим распределением q(x) и p(x). Для BN p(x) и эмпирического распределения q(x) мы имеем
Это следует из общего результата
в котором говорится, что если функция f зависит только от подмножества переменных, то нам нужно знать только предельное распределение этого подмножества переменных для получения среднего значения.
Поскольку q(x) является фиксированным, мы можем добавить энтропийные члены в q и эквивалентно имитировать
Последняя строка представляет собой положительно взвешенную сумму индивидуальных расхождений Кульбака-Лейблера. Минимальная установленая величина Кульбака- Лейблера, соответствующее максимальной вероятности, равно
С точки зрения исходных данных, это
Это выражение соответствует интуитивному предположению, что запись таблицы p(xi |pa (xi )) может быть задана путем подсчета количества раз, когда состояние {xi = s, pa (xi ) = t} встречается в наборе данных (где t - вектор родительских состояний). Затем в таблице приводится относительное количество случаев нахождения в состоянии s по сравнению с другими состояниями s` для фиксированного совместного родительского состояния t.
Альтернативным методом получения этого интуитивно понятного результата является использование множителей Лагранжа, см. упражнение(120). Для читателю, менее знакомому с приведенным выше выводом Кульбака-Лейблера, ниже приведен более прямой пример , в котором используется обозначение
для обозначения количества раз, когда состояния x1 = s1 , x2 = s2 , x3 = s3 , ... встречаются вместе в обучающих данных.
Пример 37. Мы хотим изучить записи таблицы распределения p(x1 , x2 , x3 ) = p(x1 |x2 , x3 )p(x2 )p(x3 ). Здесь мы рассмотрим, как найти запись CPT p(x1 = 1|x2 = 1, x3 = 0) с использованием максимального правдоподобия. Для данных ввода-вывода вклад p(x1 |x2 , x3 ) в логарифмическую вероятность равен
Количество раз, когда p(x1 = 1|x2 = 1, x3 = 0) встречается в логарифмической вероятности, равно # (x1 = 1, x2 = 1, x3 = 0), числу таких случаев в обучающем наборе. Поскольку (в соответствии с ограничением нормализации) p(x1 = 0|x2 =
172
ЧЕРНОВИК от 9 марта 2010 г. Максимальное апостериорное значение и максимальная вероятность
Рисунок 9.6: Переменная y с большим числом родительских элементов x1 , ... , xn требует указания экспоненциально большого числа элементов в условной вероятности p(y|x1 , ... , xn ). Одним из решений этой проблемы является параметризация условного значения p(y|x1 , . . . , xn , ;).
1, x3 = 0) = 1 ; p(x1 = 1|x2 = 1, x3 = 0), общий вклад p(x1 = 1|x2 = 1, x3 = 0) в логарифмическую вероятность равен
Используя ; ; p(x1 = 1|x2 = 1, x3 = 0), мы имеем
Дифференцируя приведенное выше выражение относительно ; и приравнивая к нулю, получаем
Тогда решением для оптимального ; будет
соответствует интуитивно понятной процедуре подсчета.
Функции условной вероятности
Рассмотрим двоичную переменную y с n двоичными родительскими переменными, x = (x1 , . . . , xn ). В таблице имеется 2n записей. значение CPT равно p(y|x), так что невозможно явно сохранить эти записи даже для средних значений n. Чтобы уменьшить сложность этого значения CPT, мы можем ограничить форму таблицы. Например, можно использовать функцию
, где нам нужно только указать n-мерный вектор параметров w.
В этом случае вместо того, чтобы использовать метод Максимального Правдоподобия для непосредственного обучения записей CPT, мы вместо этого обучаем значение параметра w. Поскольку количество параметров в w невелико (n по сравнению с 2n в неограниченном случае), у нас также есть некоторая надежда, что с помощью небольшого числа обучающих примеров мы сможем получить достоверное значение для w.
Пример 38. Рассмотрим следующую модель с тремя переменными: p(x1 , x2 , x3 ) = p(x1 |x2 , x3 )p(x2 )p(x3 ), где xi ; {0, 1} , i = 1, 2, 3. Мы предполагаем, что CPT параметризуется с помощью
Можно проверить, что приведенная выше вероятность всегда положительна и находится в диапазоне от 0 до 1. Из;за нормализации мы должны иметь
ЧЕРНОВИК от 9 марта 2010 года 173 Обучение Байесовской Сети Убеждений
Для неограниченных значений p(x2 ) и p(x3 ) значение Максимального Правдоподобия равно p(x2 = 1) ; # (x2 = 1) и p(x3 =1) ; # (x3 = 1). Вклад в логарифмическую вероятность от члена p(x1 |x2 , x3 , ;), предполагающий, что исходные данные равны, равен
Эту целевую функцию необходимо оптимизировать численно, чтобы найти наилучшие значения ;1 и ;2 . Градиент равен
Градиент может использоваться как часть стандартной процедуры оптимизации (например, сопряженные градиенты, см. Приложение (А)), чтобы облегчить поиск параметров ;1 , ;2 Максимального Правдоподобия .
9.3 Обучение Байесовской Сети Убеждений
Альтернативой обучению \тренировкам\ BN с Максимальным Правдоподобием является использование Байесовского подхода, при котором мы поддерживаем распределение по параметрам. Мы продолжаем рассматривать сценарий с Асбестом, Курением и Раком,
которая может быть представлена в виде Сети Убеждений, рис.9.4а). До сих пор мы указывали только структуру независимости, но не записи в таблицах p(c|a, s), p(a), p(s). Задан набор видимых наблюдений, V = {(an , sn , cn ) , n = 1, . . . , N }, мы хотели бы обучить соответствующие распределения для элементов таблицы.
Для начала нам нужно обозначение для элементов таблицы. Со всеми переменными в двоичном формате у нас есть такие параметры , как
и аналогично для остальных параметров ;c1,1 , ;c0,0 , ;c1,0 . В нашем примере параметрами являются
9.3.1 Независимость от глобальных и локальных параметров
При Байесовском обучении BNs нам необходимо указать априор в записях объединенной таблицы. Поскольку, как правило, работа с многомерными непрерывными распределениями сопряжена с вычислительными трудностями, полезно указывать в априоре только одномерные распределения. Как мы покажем ниже, это имеет приятное последствие, заключающееся в том, что для i.i.d. данные апостериора также преобразуются в однородные распределения.
Глобальный независимости параметр
Удобный предположение, что приор факторизуется по параметрам. Для нашего примера Асбест, Курение, Рак, мы предполагаем,
Предполагая, что данные \идентично независимо распределены\ i.i.d., мы получаем совместную модель
174 ПРОЕКТ от 9 марта 2010 года Тренинга Сети Байесовских Убеждений
Рис. 9.7: Модель параметра Байеса для отношений между Раком легких, Асбестом и Курением с факторизованным параметром приора. Предположение о независимости глобального параметра означает, что предшествующие \приоры\ таблицы преобразуются \факторизуются \ в предшествующие\ приоры\ для каждой таблицы условных вероятностей. Предположение о локальной независимости, которое в данном случае вступает в силу- действует только для p(c|a, s), означает, что p(;c ) умножается \факторизуется , является коэффициентами \ на ;a,s;P p(;ca,s ), где P = {(0, 0), (0, 1), (1, 0), (1, 1)}.
, Сеть Убеждений, для которой показано на рис. 9.7. Таким образом, обучение соответствует выводу
Удобство в факторизации для СУ \ BN\ состоит в том, что \ постериор \ задняя часть\ также факторизуется, поскольку
так что можно рассматривать каждый параметр задней части\ постериора\ отдельно. В этом случае "обучение" включает в себя вычисление апостериорных распределений p(;i |Vi ), где Vi - набор обучающих данных, ограниченных семейством переменных i.
Предположение о глобальной независимости удобно приводит к апостериорному распределению, которое умножается \факторизуется\ на условные таблицы. Однако параметр ;c сам по себе является четырехмерным. Чтобы упростить это, нам нужно сделать еще одно предположение относительно структуры каждой локальной таблицы.
Независимость локальных параметров
Если мы далее предположим, что предыдущее значение \приор\ для таблицы умножается на все состояния a, c:
затем заднюю часть \ постериор\
таким образом, апостериорное значение также умножается на родительские состояния локальной условной таблицы.
Таблица задних краев \ маргиналов постериора, предельных значений задней части, доходов последовавших\
Таблица предельных вероятностей задается, например, следующим образом:
ЧЕРНОВИК от 9 марта 2010 г. 175 Тренинги Сети Байесовских Убеждений
Интеграл по всем остальным таблицам в уравнении (9.3.11) равен единице \есть единица\, и у нас остается
9.3.2 Изучение таблиц двоичных переменных с использованием Бета-версии \ приора, предварительных \
Мы продолжаем рассмотрение примера из раздела (9.3.1), где все переменные являются двоичными, но используется непрерывное предшествующее\ предварительное, приор\ значение из таблицы. Простейший случай - начать с p(a|;a ) , поскольку для этого требуется только одномерное предшествующее распределение p(;a). Вероятность зависит от табличной переменной через
p(a = 1|;a ) = ;a (9.3.13)
таким образом, общий коэффициент\ член\ правдоподобия равен
Следовательно, заднее значение \постериор, последовавшее\ равно
Это означает, что если приор \предварительное\ также имеет форму ;;а (1 ; ;а );, то сопряженность будет соблюдена, и математика процедуры интегрирования будет простой. Это говорит о том, что наиболее удобным выбором является Бета-распределение,
, для которого апостериорное распределение также является Бета-распределением:
Таблица доходная \ маргинальная\ представлена в виде
используя полученный результат для среднего значения Бета-распределения, определением (72).
Ситуация с таблицей p(c|a, s) немного сложнее, поскольку нам нужно указать предшествующее \ предварительное\ значение для каждого из родительских таблиц. Как указано выше, это наиболее удобно, если мы укажем Бета-версию, по одной для каждого из (четырех) родительских состояний. Давайте рассмотрим конкретную таблицу
Предполагая свойство локальной независимости, мы имеем p(;c1,0 |Vc ), заданное формулой
Как и ранее, таблица предельных \ прибыльных\ вероятностей задается в виде
поскольку # (a = 1, s = 0) = # (c = 0, a = 1, s = 0) + #(c = 1, a = 1, s = 0).
Предшествующие \Предварительные\ параметры ;c (a, s) называются гиперпараметрами. Если бы у вас не было предпочтений, вы могли бы установить все ac (a, s) равными одному и тому же значению ; и аналогично для ;. Полное незнание ранее соответствовало бы установке ; = ; = 1, см. рис.(8.7).
176 ПРОЕКТ от 9 марта 2010 года Тренинг Сети Байесовских Убеждений
Предел отсутствия данных N ; 0 В пределе отсутствия данных таблица предельных \прибыльных, расчётных\ вероятностей соответствует предыдущей \ предварительной\, которая в данном случае задается как
Для плоского априорного \предварительного\ значения ; = ; = 1 для всех состояний a, c это дало бы априорную \ предварительная\ вероятность p(c = 1|a = 1, s = 0) = 0.5.
Бесконечный предел данных N ; ; В этом пределе в таблицах предельных вероятностей преобладают значения количества данных, поскольку они обычно увеличиваются пропорционально размеру набора данных. Это означает, что при бесконечном (или очень большом) ограничении данных
что соответствует решению с Максимальным Правдоподобием.
Этот эффект, заключающийся в том, что ограничение на объем данных для Байесовской процедуры соответствует решению с Максимальным Правдоподобием, является общим, если только предыдущее не оказывает патологически сильного воздействия.
Пример 39 (Асбест-Курение - Рак).
Рассмотрим бинарную сеть переменных
Данные V приведены на рис. 9.5. Используя плоскую Бета-версию, предшествующую ; = ; = 1 для всех таблиц условной вероятности, крайние \ расчётные\ апостериорные \ последовавшие\ таблицы задаются как
Для сравнения, значение Максимального Правдоподобия равно 4/7 = 0,571. Байесовский результат немного более осторожен, чем значение Максимального Правдоподобия, что согласуется с нашим прежним мнением о том, что любое значение вероятности одинаково вероятно, и приближает апостериорное\ последовавшее\ значение к 0,5.
Аналогично,
и
ЧЕРНОВИК от 9 марта 2010 года 177 Обучение сети байесовских убеждений
9.3.3 Обучение \ Тренировка \ многомерных дискретных таблиц с использованием априора \ ппредварительного\ Дирихле
Естественное обобщение для более чем двух переменных состояния дается с помощью априора \предварительного \ Дирихле, опять же предполагая, что данные ввода-вывода и локальный и глобальный параметры независимы друг от друга. Поскольку в предположении о независимости глобального параметра апостериорные \последовавшие \ коэффициенты распределяются по переменным (как в уравнении (9.3.7)), мы можем сосредоточиться на апостериорной \ последовавшей \ части одной переменной.
Родительских значений нет
Давайте рассмотрим вклад переменной v с dom(v) = {1, . . . , I}. Вклад в апостериорную \последовавшую\ часть \значение\ от точки данных vn равен
так что задняя часть \последовавшее значение\ пропорциональна
Для априорного \предварительного\ распределения Дирихле с гиперпараметрами u
Используя это предварительное значение, заднее \ последовавшее \ значение становится
, что означает, что апостериорное \последовавшее \ значение задается через
где c - счетный вектор с компонентами
- это количество раз, когда состояние i наблюдалось в обучающих \тренируемых \ данных.
Таблица на полях представлена путем интегрирования
Поскольку предельное \маргинальное, расчётное\ распределение Дирихле с одной переменной является Бета-распределением, в разделе(8.5) таблица предельных \расчётных \ значений представляет собой среднее значение Бета-распределения. Учитывая, что предельное \расчётное \ значение p(;|V) является Бета-распределением с параметрами ; = ui + ci , ; =; j;i uj + cj , таблица предельных \расчётных\ значений представлена в виде
которая обобщает уравнение бинарной формулы состояния (9.3.18).
178 ПРОЕКТ от 9 марта 2010 года Тренинга Сети байесовских убеждений
9.3.4 Родители
Чтобы рассмотреть общий случай переменной v с родительскими параметрами pa (v), обозначим вероятность того, что v находится в состояние i, обусловленное нахождением родителей в состоянии j как
, где ;i;i (v; j) = 1. Это образует компоненты вектора ;(v; j). Обратите внимание, что если у v есть K родительских элементов, то число состояний j будет экспоненциальным в K.
Местная (состояния) независимость означает
И глобальная независимость означает
, где ; = (;(v), v = 1, . . . , V ) представляет собой объединенную таблицу всех переменных. С этого момента мы не будем использовать явный шрифт без засечек для состояний.
Параметр постериор \последовавший\
Благодаря независимости от глобальных параметров апостериорное распределение по таблицам ; факторизуется, и на каждую переменную приходится одна апостериорная таблица. Каждая апостериорная таблица для переменной v зависит только от информации, локальной для семейства каждой переменной D(v). Предполагая, что приор распределения Дирихле
задняя часть \последовавшее \ пропорциональна распределению присоединенному \ в суставе \
, где Z(u) - константа нормализации распределения Дирихле.
Следовательно, апостериорное значение равно
, где предыдущий член гиперпараметра обновляется на основе наблюдаемых значений,
По аналогии со случаем, когда родителей нет, таблица на полях \ расчётная\ приводится в виде (с явным указанием состояний)
ЧЕРНОВИК от 9 марта 2010 г. 179 Байесианская сеть убеждений обучаемая
Рисунок 9.8: База данных с записями пациентов о воздействии Асбеста (1 означает воздействие), Курении (1 означает, что человек является курильщиком) и Раке легких (0 означает отсутствие рака, 1 означает раннюю стадию рака, 2 означает позднюю стадию рака). Каждая строка содержит информацию о конкретном человеке, так что в базе данных есть 7 человек.
Пример 40. Рассмотрим пример с асбестом p(c|a, s)p(s)p(a) с dom(a) = dom(s) = {0, 1}, только
теперь переменная c принимает три состояния, dom(c) = {0, 1, 2}, учитывает различные виды рака. Маргинальная таблица под априором Дирихле тогда задается как
Предполагая плоский априор Дирихле, что соответствует установке всех компонентов u равными 1, здесь дает
ыи аналогично для трех других таблиц p(c|a = 1, s = 0), p(c|a = 0, s = 1), p(c|a = 1, s = 1).
Моделируем вероятность
Для Сети Уверений M общая вероятность всех переменных умножается на локальные вероятности каждой переменной, зависящие от ее родителей:
Для данных ввода-вывода D вероятность в сети M равна
где u - гиперпараметры Дирихле, а u` задается уравнением (9.3.47). Выражение (9.3.54) может быть записано явно в терминах Гамма-функций, см. упражнение(125). В приведенном выше выражении в целом число родительских состояний отличается для каждой переменной v, так что в приведенной выше формуле подразумевается, что произведение состояний на j изменяется от 1 до числа родительских состояний переменной v. Из-за допущений о независимости локальных и глобальных параметров логарифм вероятности модели делится на слагаемые, по одному для каждой переменной v и родительской конфигурации. Это называется свойством разложимости вероятности.
9.3.5 Обучение структуры
До этого момента мы предполагали, что нам дана как структура распределения, так и набор данных" D. Более сложной задачей является изучение структуры сети. Мы рассмотрим случай, когда данные являются полными (т.е. в них нет пропущенных наблюдений). Поскольку для переменных D существует экспоненциально большое количество (в D) структур BN, понятно, что мы не можем выполнить поиск по всем возможным структурам. По этой причине изучение структуры является сложной вычислительной задачей, и мы необходимо полагаться на ограничения и эвристические методы, помогающие вести поиск. Кроме того, для всех, кроме самых редких
180 ПРОЕКТ от 9 марта 2010 года Тренинга Сети байесовских убеждений
Алгоритм 3 Компьютерный алгоритм для изучения скелета.
1: Начните с полного неориентированного графа G на множестве V всех вершин.
3: повторите
для x ; V, сделайте
для y ; Adj {x}, сделайте
Определите, существует ли подмножество S размера i среди соседей x (не включая y), для которых
; y| S. Если это множество существует, удалите связь x ; y из графа G и установите Sxy = S.
7: конец для
8:
конец для
10: до тех пор, пока все узлы не будут иметь соседей ; i.
сетей, оценка зависимостей с любой точностью требует большого объема данных, что затрудняет тестирование зависимостей. Действительно, для конечного объема данных две переменные всегда будут иметь ненулевую взаимную информацию, так что необходимо установить пороговое значение, чтобы определить, является ли измеренная зависимость значимой в рамках конечной выборки, см. раздел (9.3.6). Другие сложности возникают из-за опасений, что Вера \ Доверие\ или Сеть Маркова, основанная только на видимых переменных, может оказаться недостаточным способом представления наблюдаемой информации, если, например, могут существовать скрытые переменные, которые определяют наблюдаемые зависимости. По этим причинам мы не будем подробно обсуждать эту тему здесь и ограничим обсуждение двумя основными подходами.
Особый случай, который поддается вычислительной обработке, - это когда сеть ограничена наличием не более чем одного родительского элемента. Мы отложим обсуждение этого вопроса до раздела (10.4.1).
Алгоритм PC
Алгоритм PC[259] сначала изучает каркас графа, после чего ребра могут быть ориентированы для формирования (частично ориентированного) DAG.
Компьютерный алгоритм PC начинает с первого раунда с полного скелета G и пытается удалить как можно больше ссылок\ связок\. На первом этапе мы тестируем все пары x ;y |;. Если пара x и y считается независимой, то связь x ; y удаляется из полного графа. Это повторяется для всех попарных связей. Во втором раунде, для оставшегося графа, исследуется каждая связь\ связка\ x ; y и задаются условия для одного соседа z из x. Если x ; y| z, то удаляется связь\ связка\ x ; y. Таким образом, повторяются все переменные. На каждом раунде количество соседей в наборе условий увеличивается на единицу. Смотрите алгоритм(3), рис.(9.9)1 и demoPCoracle.m. Усовершенствование этого алгоритма, известное как NPC для необходимого пути PC[261], направлено на ограничение количества независимых проверок, которые в противном случае могут привести к несоответствиям из-за эмпирических оценок условной взаимной информации. Учитывая обученный \тренированный\ каркас, частичный DAG может быть построен с использованием алгоритма(4). Обратите внимание, что это необходимо, поскольку неориентированный граф G является каркасом\ скелетом\, а не Сетью Убеждений \Уверений\ открытых предположений о независимости. Например, у нас может быть граф G с x ; z ; y , в котором связь\ связка\ x ; y была удалена на основании x ;y| ; Sxy = ;. В результате граф x ; z ; y подразумевает x;y, хотя это не согласуется с открытием в первом раунде x ; y. В этом причина ориентационной части: для согласованности мы должны иметь x ; z ; y, для чего x ; y и x;y| z. Обратите внимание, что в алгоритме (4) для теста "не состоящего в браке коллайдера" мы имеем z;;, что в данном случае верно, что приводит к образованию коллайдера. См. также рис.(9.10).
Пример 41 (Ориентация скелета\ каркаса).
Если x (безусловно) независим от y, то z должен быть коллайдером, поскольку в противном случае маргинализация \подрасчётные , промежуточные расчёты\ по сравнению с z привела бы к зависимости между x и y.
1Этот пример приведен в [148] и [208] – также спасибо Серафину Моралю за его онлайн-заметки.
ЧЕРНОВИК от 9 марта 2010 г. 181 Байесовский тренинг сети убеждений
Рисунок 9.9: Компьютерный алгоритм PC. (a): BN, из которого, как предполагается, генерируются данные и в отношении которого будут выполнены тесты на условную независимость. (b): Исходный каркас полностью подключен. (c-l): В первом раунде (i = 0) проверяются все попарные взаимные данные x ; y|;, и связь между x и y удаляется, если она считается независимой (зеленая линия). (m-o): i = 1. Теперь мы рассмотрим связанные подмножества трех переменных x, y, z оставшегося графа, удалив связь x ; y, если x ;y| z истинно. Показаны не все шаги . (p,q): i = 2. Теперь мы рассмотрим все x ; y| {a, b}. После этого раунда алгоритм завершается (когда i увеличивается до 3), поскольку нет узлов с 3 или более соседями. (r): Окончательный скелет. В ходе этого процесса были найдены множества \наборы \ Sx,y = ;, Sx, w = ;, Sz, w = y, Sx,t = {z, w} , Sy,t = {z, w}. Смотрите также демонстрационный demoPCoracle.m
Если x не зависит от y и зависит от z, z не должен быть коллайдером. Уместна любая другая ориентация.
9.3.6 Эмпирическая независимость
При наличии набора данных D, содержащего переменные x, y, z, наш интерес состоит в том, чтобы измерить, соответствует ли x ; y|z. Один из подходов заключается в том, чтобы использовать условную взаимную информацию, которая является средним значением условных расхождений Кульбака-Лейблера.
Определение 87 (Взаимная информация).
где это выражение одинаково справедливо для наборов переменных. Если x ; y| z равно true, то MI(x; y|z) равно нулю, и наоборот. Когда z =;, среднее значение по p(z) отсутствует, и записывается MI(x; y).
При наличии данных мы можем получить оценку условной взаимной информации, используя эмпирическое распределение p(x, y, z), рассчитанное простым подсчетом совпадений в данных. На практике, однако, мы у нас есть только ограниченный объем данных для оценки эмпирического распределения, так что для данных, отобранных из распределения, для которого переменные действительно независимы, эмпирическая взаимная информация, как правило, будет больше нуля. Таким образом, проблема заключается в том, какой порог использовать для эмпирической условной взаимной информации, чтобы определить, достаточно ли она далека от нуля, чтобы быть вызванной зависимостью. Частотный подход заключается в вычислении распределения условной взаимной информации, а затем в определении того, где выборочное значение сравнивается с распределением. Согласно [164] 2N MI(x; y|z) - это распределение по Чи-квадрату
182 ПРОЕКТ от 9 марта 2010 года Тренинг Сети байесовских убеждений
Алгоритм 4. Алгоритм ориентации скелета (возвращает DAG).
1: Незамкнутый коллайдер: Проверьте все ненаправленные связи x ; z ; y. Если z 6; Sxy, установите x ; z ; y.
2: повторите
x;z;y ;x;z ;y
Для x ; y, если существует направленный путь от x к y, ориентируйте x ; y
5: Если для x ; z ; y существует w, такое, что x ; w, y ; w, z ; w, то ориентируйте z ; w
6: до тех пор, пока больше ребер нельзя будет ориентировать.
7: Остальные ребра могут быть ориентированы произвольно при условии, что граф остается DAG и не вводятся дополнительные коллайдеры.
при (X -1)(Y -1)Z степенями свободы, хотя этот тест не очень хорошо работает в случае небольших количеств данных. Альтернативный практический подход заключается в оценке порогового значения на основе эмпирических выборок ИМ в контролируемых независимых/зависимых условиях – смотрите demoCondindepEmp.m для сравнения этих подходов.
Байесовский тест на условную независимость
Байесовский подход к проверке на независимость может быть реализован путем сравнения вероятности данных при гипотезе независимости с вероятностью при гипотезе зависимости. Для гипотезы независимости мы имеем совместное распределение по переменным и параметрам:
Для категориальных распределений удобно использовать априорное значение Дирихле (;|u) для параметров ;, предполагая также независимость как от локальных, так и от глобальных параметров. Для набора предполагаемых исходных данных (X , Y, Z) = (xn , yn , zn ) , n = 1, . . . , N вероятность затем определяется путем интегрирования по параметрам ;:
Благодаря сопряженности, это просто и дает выражение
где ux | z - гиперпараметрическая матрица псевдосчетов для каждого состояния x, заданного для каждого состояния z. Z(v) - константа нормализации распределения Дирихле с векторным параметром v.
Для зависимой гипотезы мы имеем
Тогда вероятность равна
Рисунок 9.10: Алгоритм ориентации скелета. (а): Скелет вместе с Sx,y = ;, Sx, w = ;, Sz, w =
y, Sx,t = {z, w} , Sy,t = {z, w}. (b): z;Sx,y таким образом, образуют коллайдер. (c): t;Sz,w , таким образом, образуют коллайдер. (d): Конечная частично ориентированная DAG. Оставшееся ребро может быть ориентировано по желанию, не нарушая условия DAG. Смотрите также демонстрационный пример demoPCoracle.m.
ЧЕРНОВИК от 9 марта 2010 г.183 Байесовская сеть обучения уверений
Рисунок 9.11: Байесовский тест на условную независимость с использованием коэффициентов \приоров\ Дирихле в таблицах. (а): модель Hindep для условной независимости x ; y|z. (б): Модель Hdep для условной зависимости x;y | z. Вычисляя вероятность того, что данные соответствуют каждой модели, можно получить численную оценку того, соответствуют ли данные предположению об условной независимости. Смотрите demoCondindepEmp.m.
Рисунок 9.12: Тест на условную независимость x ; y | z1 , z2, где x, y, z1 , z2 имеют 3, 2, 4, 2 состояния соответственно. Из показанной Cети Уверений oracle \оракул, в каждом эксперименте таблицы составляются случайным образом, и для формирования набора данных отбираются 20 примеров. Для каждого набора данных проводится тест, чтобы определить, являются ли x и y независимыми при условии z1, z2 (правильный ответ — они независимы). После 500 экспериментов Байесовский тест на условную независимость корректно показал, что переменные являются условно независимыми в 74% случаев, по сравнению с 50%-ной точностью при использовании теста взаимной информации чи-квадрат. Смотрите demoCondindepEmp.m.
Предполагая, что каждая гипотеза одинаково вероятна, для Коэффициента Байеса
больше 1, мы предполагаем, что имеет место условная независимость, в противном случае мы предполагаем, что переменные условно зависимые. Пример demoCondindepEmp.m предполагает, что проверка гипотезы Байеса, как правило, превосходит подход с использованием условной взаимной информации, особенно в случае небольшого размера выборки, см. рис.9.12.
9.3.7 Сетевой скоринг
Альтернативой локальным методам, таким как компьютерный алгоритм, является оценка всей структуры сети. В вероятностном контексте, учитывая структуру модели M, мы хотим вычислить p(M |D) ; p(D|M )p(M ). Здесь требуется некоторая осторожность, поскольку мы должны сначала "подогнать" каждую модель с параметрами ;, p(V|;, M ) к данным D. Если мы делаем это, используя только Максимальное Правдоподобие, без ограничений на ;, и в конечном итоге мы всегда будем отдавать предпочтение модели M с наиболее сложной структурой (предполагая, что p(M ) = const.). Это можно исправить, используя Байесовский метод
Однако в случае управляемых сетей, как мы видели в разделе (9.3), предположения о независимости локальных и глобальных параметров делают интегралы приемлемыми. Для сети с дискретным состоянием и априорных значений Дирихле мы имеем p (D |M), явно заданное Байесовским уравнением оценки Дирихле (9.3.54). Сначала мы определяем гиперпараметры u(v; j), а затем выполните поиск по структурам M, чтобы найти структуру с наилучшей оценкой p(D|M ). Самая простая настройка для гиперпараметров - установить их всех равными единице[66]. Другой настройкой является "неинформативное предварительное значение"[52]
184 ПРОЕКТ от 9 марта 2010 г. Максимальная вероятность для неориентированных моделей
Рисунок 9.13: Изучение структуры Байесовской сети. (а): Правильная структура, в которой все переменные являются двоичными. Порядок следования - 2, 1, 5, 4, 3, 8, 7, 6. Набор данных формируется из 1000 выборок из этой сети. (b): Обученная структура основана на компьютерном алгоритме с использованием Байесовского эмпирического теста условной независимости. Неориентированные ребра могут быть ориентированы произвольно. (c): Обученная структура, основанная на методе подсчета баллов по сети Байеса-Дирихле. Смотрите demoPCdata.m и demoBDscore.m.
где dim x - это количество состояний переменной(ых) x, определяющее оценку BDeu для параметра ; ‘эквивалентного размера выборки’. Обсуждение этих параметров приведено в [129] в рамках концепции эквивалентности вероятности, а именно, что две сети, эквивалентные по Маркову, должны иметь одинаковую оценку. Плотность результирующей сети может быть чувствительна к ;[263, 250, 262]. Включение явного предварительного значения p(M ) в сетях в пользу сетей с разреженными соединениями также является разумной идеей, для чего оценка была изменена на p(D|M )p(M ).
Поиск по структурам является сложной вычислительной задачей. Однако, поскольку логарифмическая оценка разбивается на слагаемые, включающие каждое семейство v, мы можем эффективно сравнивать две сети, различающиеся по одной дуге. Популярны поисковые эвристики, основанные на локальном добавлении/удалении/реверсировании ссылок [66, 129], которые повышают рейтинг [129]. В learnBayesNet.m мы упрощаем задачу для демонстрационных целей, в которых предполагаем, что знаем порядок наследования переменных, а также максимальное число родителей каждой переменной.
Пример 42 (алгоритм ПК против скоринга \оценки \ сети). На рис. (9.13) мы сравниваем алгоритм ПК с Сетевыми BD скоринг на основе (с параметрами Дирихле установленными единице) на 1000 образцов\выборок \ с известной Сетью Убеждений. Тест на условную независимость алгоритма PC основан на Байесовском коэффициенте (9.3.60) в котором во всех случаях использовались коэффициенты \приоры \ Дирихле с ; = 0,1. На рис. 9.13 показано, что метод сетевого подсчета превосходит алгоритм PC. Отчасти это объясняется применяемой в сети методикой подсчета очков с правильным порядком наследования и ограничением, согласно которому каждая переменная имеет максимум двух родителей.
9.4. Максимальное Правдоподобие для Ненаправленных моделей
Рассмотрим распределение p(X ) в сети Маркова, определенное на (не обязательно максимальных) кликах
где
ПРОЕКТ от 9 марта 2010 г. 185максимальная вероятность для неориентированных моделей
обеспечивает нормализацию. Учитывая набор данных, Xn , n = 1, . . . , N , и предполагая, что исходные данные являются логарифмическими, логарифмическая вероятность равна
В общем, обучение оптимальных параметров ;c , c = 1, . . . , C затруднительно, поскольку они связаны через Z(;). В отличие от BN, целевая функция не разбивается на набор изолированных параметров, и, как правило, нам приходится прибегать к численным методам. Однако в особых случаях точные результаты все еще применимы, в частности, когда MN разложима и на форму потенциалов клики не накладывается никаких ограничений, как мы обсуждаем в разделе (9.4.2). Однако в более общем плане могут быть использованы методы, основанные на градиенте, которые также дают представление о свойствах решения с Максимальным Правдоподобием.
9.4.1 Градиент вероятности
где мы использовали полученный результат
Затем градиент можно использовать как часть стандартного пакета численной оптимизации.
Потенциалы экспоненциальной формы
Распространенной формой параметризации является использование экспоненциальной формы
где ; - параметры, а ; c (XC ) - фиксированная "функциональная функция", определенная для переменных клики c. Дифференцируя относительно ; и приравнивая к нулю, мы получаем, что решение с Максимальным Правдоподобием удовлетворяет тому, что эмпирическое среднее значение признаковой функции совпадает со средним значением признаковой функции по модели.:
, где # (Xc ) - количество раз, когда в наборе данных наблюдалось состояние клики Xc. Интуитивная интерпретация заключается в выборке состояний X из обученной модели p(X ) и использовании их для вычисления среднего значения каждой функции-признака. В пределе бесконечного числа выборок, для оптимальной модели с Максимальным Правдоподобием, эти средние значения выборок будут соответствовать средним значениям, основанным на эмпирическом значении.
Неограниченные потенциалы
Для неограниченных потенциалов у нас есть отдельная таблица для каждого из состояний, определенных в клике. Это означает, что мы можем записать
, где произведение находится по всем состояниям потенциала c. Это выражение следует из того, что показатель равен нулю для все, кроме единственного наблюдаемого состояния Xcn . Логарифмическая вероятность тогда равна
186 ПРОЕКТ от 9 марта 2010 г. Максимальное правдоподобие для ненаправленных моделей
Рисунок 9.14: (a): Разложимая сеть Маркова. (b): Дерево соединений для (a). (c): Задайте цепочку для (a), сформированную путем выбора клики x2 , x3 , x5 в качестве корня и последовательного удаления ребер от корня. Каждый разделитель включается в свою дочернюю группу, образуя заданную цепочку.
где
Дифференцируя логарифмическую вероятность относительно конкретной записи таблицы ;(Yc ), мы получаем
Равное нулю, решение с Максимальным Правдоподобием получается, когда
То есть неограниченное оптимальное решение с Максимальным Правдоподобием задается путем установки потенциалов клик таким образом, чтобы предельное распределение в каждой клике p(Yc ) соответствовало эмпирическому распределению в каждой клике ;(Yc ).
9.4.2 Разлагаемые Марковские сети
В случае, когда нет ограничений на форму множителей ;c и если MN, соответствующие этим потенциалам, поддаются разложению, то мы знаем (из представления дерева соединений), что мы можем выразить распределение в виде произведения локальных маргинальных значений, разделенных на разделительные распределения
Преобразуя разделители в числители, мы можем сформировать заданное цепочечное распределение, раздел (6.8)
Поскольку это сделано целенаправленно, решение с Максимальным Правдоподобием для обучения таблиц является тривиальным, поскольку мы присваиваем каждому набору коэффициент цепочки p(XC |XS ) путем подсчета экземпляров в наборе данных[168], см. learnMarkovDecom.m. Возможно, эту процедуру лучше всего объяснить на примере, приведенном ниже. Общее описание приведено в алгоритме(5).
Пример 43. Учитывая набор данных V = {xn , n = 1, . . . , N }, мы хотим с максимальной вероятностью подобрать MN вида
ЧЕРНОВИК от 9 марта 2010 года 187Максимальная вероятность для неориентированных моделей
Алгоритм 5. Обучение неограниченно разлагаемой Марковской сети с использованием метода Максимального Правдоподобия.
У нас есть триангулированная (декомпозируемая) марковская сеть на кликах ;c (Xc ), c = 1, . . . , C и эмпирические предельные распределения на всех кликах и разделителях, # (Xc ), #(Xs )
1: Сформируйте дерево соединений из кликов.
2: Инициализируйте каждую клику ;c (Xc ) в #(Xc ) и каждый разделитель ;s (Xs ) в #(Xs ).
3: Выберите корневую группу в дереве соединений и последовательно ориентируйте ребра от этого корня.
4: Для этого ориентированного дерева соединений разделите каждую группу родительским разделителем.
5: Верните новые потенциалы для каждого клика в качестве решения с максимальным правдоподобием.
где потенциалы представлены в виде таблиц без ограничений, см. рис.(9.14а). Поскольку граф является разложимым, мы знаем, что он допускает факторизацию потенциалов клик, разделенных на разделители:
Мы можем преобразовать это в цепочку множеств, переведя знаменатели в числители, см. раздел (6.8). Например, выбрав клику x2 , x3 , x5 в качестве корня, мы можем записать
, где мы определили факторы с потенциалами клик, а константа нормализации Z равна единице, см. рис.9.14, b). Преимущество заключается в том, что в этом представлении потенциалы клик являются независимыми, поскольку распределение по кластерным переменным является BN. Логарифмическая вероятность для набора данных независимо идентично распределённых\ i.i.d.\ X = {xn , n = 1, . . . , N } равна
, где каждое из слагаемых является независимым параметром модели. Тогда решение с Максимальным Правдоподобием соответствует (как и в случае с BN) простой установке каждого коэффициента в значения данных. Например
9.4.3 Неразлагаемые Марковские сети
В неразложимом или ограниченном случае решения с Максимальным Правдоподобием в замкнутой форме, как правило, не существует, и приходится прибегать к численным методам. Согласно уравнению (9.4.13) решение с Максимальным Правдоподобием таково, что маргиналы клики совпадают с эмпирическими маргиналами. Предполагая, что мы можем включить константу нормализации в произвольно выбранную группу, мы можем отказаться от явного представления константы нормализации. Для группы c есть требование, чтобы предельное значение p соответствовало эмпирическому предельному значению переменных в группе, равному
Учитывая начальную настройку потенциалов, мы можем затем обновить ;(Xc), чтобы удовлетворить вышеуказанному предельному требованию,
ПРОЕКТ от 9 марта 2010 г. Максимальное правдоподобие для неориентированных моделей, которое требуется для каждого из состояний Xc . Путем умножения и деления правой части на ;(Xc ) , которое эквивалентно
Это обновление IPF можно рассматривать как оптимизацию логарифмической вероятности мудрёно по координатам, при которой координата соответствует ;c (Xc ), при этом все остальные параметры остаются неизменными. В данном случае этот условный оптимум аналитически определяется приведенной выше настройкой. Далее выбирается другой потенциал для обновления. Обратите внимание, что, как правило, при каждом обновлении необходимо заново вычислять предельное значение p(Xc ). Вычисление этих предельных значений может быть дорогостоящим, если ширина дерева соединений, сформированного на основе графа, не ограничена соответствующим образом.
Пример 44 (Машинное обучение по Больцману). Мы определяем BM как
для симметричных W и двоичных переменных dom(vi ) = {0, 1}. Учитывая набор обучающих данных, D = v1 , . . . , vN , логарифмическая вероятность равна
Дифференцируя относительно wij , i;j , мы получаем градиент
Простой алгоритм для оптимизации матрицы веса W в использовании градиентного подъема,
для повышения скорости обучения ; > 0 . Интуитивная интерпретация заключается в том, что обучение прекратится (градиент равен нулю), когда статистика второго порядка модели <vi vj> p(v|W) совпадет со статистикой эмпирического распределения, ;n vin vjn /N . Однако обучение BM затруднено, поскольку <vi vj> p(v|W) обычно не поддается вычислениям для произвольного взаимодействия матрицы W и требует аппроксимации. Действительно, они не могут точно рассчитать вероятность L (W), так что мониторинг производительности также затруднен.
9.4.4 Ограниченно разлагаемые Марковские сети
Если, как мы видели, нет утверждений о формах максимальных возможностей сети Маркова, то обучение происходит в лоб. Здесь нас интересует, когда функциональная форма максимальной группы определяется как произведение потенциалов на меньших группах \кликах2:
при отсутствии ограничений объединения\ расположения\ в немаксимальные потенциалы клик ;ic(Xci). В общем, в этом случае нельзя напрямую записать решение с Максимальным Правдоподобием для немаксимальных потенциалов клики ;ic (Xci).
2 Машина Больцмана имеет такую форму, поскольку любые неограниченные двоичные попарные потенциалы могут быть преобразованы в BM. В других случаях,в которых ;ic ограничены, вместо IPF можно использовать Итерационное масштабирование.
ЧЕРНОВИК от 9 марта 2010 г. 189 Максимальная вероятность для ненаправленных моделей
Рисунок 9.15: (а): Интерпретируемый как сеть Маркова, представляет ли граф распределение ;(x1, x4, x5); (x1 , x2 , x4);(x2 , x4 , x3). В виде попарного MN граф представляет ; (х4, х5);(х1 , х4); (х4 , х5); (х1 , х2); (х2 , х4); (х2 , х3); (x3, x4 ). (b): Дерево соединений для попарного MN в (a). У нас есть вариант локализовать клики попарно, и это один из верных вариантов, используя сокращение ;a, b = ;a , b (xa, xb ) и xa, b = {xa, xb }.
Рассмотрим граф на рис. 9.15. В ограниченном случае, когда мы интерпретируем граф как попарный MN, IPF можно использовать для обучения парных таблиц. Поскольку граф распадается, в этом случае все еще можно сэкономить на вычислениях[11]. Для эмпирического распределения ;, Максимальное значение Вероятности требует, чтобы все попарные поля MN совпадали с соответствующими полями, полученными из ;. Как объяснено на рис. (9.15), у нас есть выбор относительно того, к какому перекрестку дерева относится клика каждого потенциала, причем один правильный выбор приведен на рис. (9.15 б). Сохраняя потенциалы клик ;1, 4 ;1, 5 и ;2,3 ;2,4 ;3,4, мы можем обновить потенциалы\ возможности\ клик ;1,2 ;1,4 . Используя столбик для обозначения фиксированных потенциалов, мы получаем предельные требования, согласно которым MN соответствует эмпирическому предельному значению ;(x1, x2), которое можно записать сокращенно как
, которое могут быть выражено как
"Сообщения" y1,4 и y1,2 являются таблицами разделителей границ, когда мы выбираем центральную клику в качестве корневой и переносим управление в корень. Учитывая эти фиксированные сообщения, мы можем затем выполнить обновления корневой клики, используя
После внесения этого обновления мы можем впоследствии обновить ;1,4 аналогичным образом, используя ограничение
так что
Учитывая сходящиеся обновления для этой клики, мы можем выбрать другую клику в качестве корневой, перейти к корню и вычислить разделяющие клики на границе корня. Учитывая эти фиксированные граничные потенциалы клик, мы выполняем IPF внутри клики.
190 ПРОЕКТ от 9 марта 2010 г. Максимальное правдоподобие для неориентированных моделей
Алгоритм 6. Эффективная Итеративная Пропорциональная Подгонка. Учитывая набор ;i , i = 1, . . . , I и соответствующий набор эталонных (эмпирических) предельных распределений по переменным каждого потенциала, ;i , мы стремимся установить все ; таким образом, чтобы все маргиналы сети Маркова соответствовали заданным эмпирическим маргиналам.
1: Задана сеть Маркова с потенциалами ;i , i= 1, . . . , I, проведем триангуляцию графика и сформируем клики C1 , . . . , CC .
2: Назначьте потенциалы кликам. Таким образом, каждая клика имеет набор связанных потенциалов Fc
3: Инициализируйте все потенциалы (например, в unity).
4: повторите
5: Выберите клику c в качестве корневой.
6: Распространите сообщения по направлению к корню и вычислите разделители на границе корня.
7: повторите
8: Выберите потенциал ;i в клике c, i ; Fc .
9: Выполните обновление IPF для ;i, учитывая фиксированные разделители границ и другие потенциалы в c.
10: пока потенциалы в клике c не сойдутся.
11: пока Все маргиналы сети Маркова не сойдутся к эталонным маргиналам.
Эта "эффективная" процедура IPF более подробно описана в алгоритме (6) для эмпирического распределения ;. В более общем плане IPF минимизирует расхождение Кульбака-Лейблера между заданным эталонным распределением ; и сетью Маркова. Смотрите демонстрационные файлы demoFEFF.m и IPF.m.
Пример 45. На рис. 9.17 представлены 36 примеров двоичных символов размером 18 ; 14 = 252 двоичных пикселя, написанных от руки, формируем обучающий \ тренирующий\ набор, из которого мы хотим составить Марковскую сеть. Сначала были вычислены все попарные эмпирические энтропии H(xi , xj ), i, j = 1, . . . , 252, которые использовались для ранжирования ребер, причем ребра с наибольшей энтропией занимали первое место. Ребра были включены в граф G, занявший первое место по ранжированию, при условии, что в триангулированном G все клики были меньше 15. В результате было получено 238 уникальных кликов и матрица смежности для триангулированного G, как показано на рисунке (9.16a). На рис. (9.16, б) показано количество раз, когда пиксель появляется в 238 кликах, и указывает степень важности каждого пикселя для различения между 36 примерами. Затем были обучены две модели и использованы для вычисления наиболее вероятной реконструкции на основе отсутствующих данных p(xmissing |xvisible ). Первой моделью была марковская сеть на максимальных кликах графа, для которой, по сути, не требуется обучение, и настройки для каждого потенциала клика могут быть получены, как описано в алгоритме (5). Модель допускает ошибки в 3,8% при восстановлении отсутствующих пикселей. Обратите внимание, что неблагоприятный эффект восстановление белого пикселя, окруженного черными пикселями, является следствием ограниченности обучающих данных. При больших объемах данных модель распознала бы, что такие эффекты не возникают. Во второй модели использовались те же максимальные клики, но максимальные потенциалы клик были ограничены как произведение всех попарных двух клик в пределах максимальной клики. Это эквивалентно использованию машины Больцмана и было обучено с использованием эффективного подхода IPF алгоритма (6). Соответствующая ошибка восстановления равна 20%. Эта производительность хуже, чем у сети с неограниченными возможностями, поскольку машина Больцмана представляет собой Марковскую сеть с очень высокими ограничениями. См. demoLearnDecMN.m.
Рисунок 9.16: (а): На основе попарных эмпирических энтропий упорядочены ребра H(xi , xj), сначала ребра с высокой энтропией. Показана матрица смежности результирующей Сети Маркова, дерево соединений которой имеет количество кликов ; 15 (белый цвет обозначает ребро). (b): Указано количество кликов, членом которых является каждый пиксель, что указывает на степень важности. Обратите внимание, что наименьшее значение принадлежности к клике равно 1, так что каждый пиксель является членом по крайней мере одной клики.
ЧЕРНОВИК от 9 марта 2010 года 191 Максимальная вероятность для неориентированных моделей
Рисунок 9.17: Обучающие цифры (из системы algoval Саймона Лукаса) с использованием сети Маркова. Верхний ряд: 36 обучающих примеров. Каждый пример представляет собой двоичное изображение размером 18 ; 14 пикселей. Вторая строка: обучающие данные с 50% пропущенных пикселей (серый цвет обозначает пропущенный пиксель). Третья строка: Реконструкция по отсутствующим данным с использованием дерева тонких переходов MN с максимальным размером клика 15. Нижний ряд: Реконструкции с использованием машины Больцмана с тонким деревом переходов с максимальным размером кликов 15, выполненные с использованием эффективного IPF.
9.4.5 Итеративное масштабирование
Мы рассматриваем марковские сети экспоненциального вида
где fc (Vc ) ; 0 и c - диапазоны немаксимальных клик . Требование к нормализации равно
Алгоритм обучения с Максимальным Правдоподобием для сети Маркова, в некоторой степени аналогичный подходу EM, описанному в разделе (11.2), может быть получен следующим образом[32]:
Рассмотрим границу для положительного x:
log x ; x ; 1 ; ; log x ; 1 ; x (9.4.36)
Следовательно
Затем мы можем записать оценку логарифмической вероятности
В нынешнем виде оценку (9.4.38), как правило, нелегко оптимизировать, поскольку параметры каждого потенциала связаны через член Z(;). Для удобства полезно сначала выполнить повторную настройку параметров и записать
Тогда
Это можно разделить, используя дополнительную границу, полученную путем предварительного рассмотрения:
ПРОЕКТ от 9 марта 2010 г. Максимальная вероятность для неориентированных моделей
, где
Поскольку pc ; 0 и ;c pc = 1, мы можем применить неравенство Дженсена, чтобы получить
Следовательно
Подключив эту привязку к (9.4.38), мы получим
Термин в фигурных скобках содержит потенциальные параметры ;c в несвязанном виде. Дифференцируя по отношению к ;c, градиент каждой нижней границы задается через
Это может быть использовано как часть процедуры оптимизации на основе градиента для определения параметров ;c . Потенциальное преимущество перед IPF заключается в том, что все параметры могут обновляться одновременно, тогда как в IPF они должны обновляться последовательно. Интуитивно понятно, что параметры сходятся, когда эмпирическое среднее значение функций f сопоставлено со средним значением функций по выборкам, взятым из распределения, в соответствии с нашим общим условием получения оптимального решения с Максимальной Вероятностью \ Правдоподобием\.
В частном случае, когда сумма функций равна 1, т. е. ;c f c(Vc ) = 1, нулевой градиент может быть найден аналитически, что дает обновление
Ограничение на то, что объекты fc должны быть неотрицательными, можно ослабить за счет дополнительных вариационных параметров, см. Упражнение(129). В случаях, когда невозможно вычислить нулевой градиент с аналитической точки зрения, в целом использование IS может иметь небольшое преимущество по сравнению со стандартными процедурами, основанными на градиенте, непосредственно на логарифмическом правдоподобии [196].
Если дерево соединений, сформированное из этой Марковской сети экспоненциальной формы, имеет ограниченную ширину дерева, можно сэкономить на вычислениях, выполнив IPF над кликами дерева соединений и обновив параметры ; внутри каждой клики с помощью IS[11]. Это модифицированная версия случая ограниченной декомпозиции. Смотрите также [274] для унифицированного описания распространения и масштабирования на деревьях-узлах.
9.4.6 Условные случайные поля
Для входных данных x и выходных данных y CRF определяется условным распределением [266, 166]
для (положительных) потенциалов ;k (y, x).Чтобы упростить обучение, потенциалы обычно определяются как e;k fk (y,x) для фиксированных функций f (y, x) и параметров ;k . В этом случае распределение выходных данных, обусловленное входными данными, равно
ПРОЕКТ от 9 марта 2010 г. 193Максимальная вероятность для неориентированных моделей
Для набора данных ввода-вывода i.i.d., D = {(xn , yn ), n = 1, . . . , N }, обучение основано на условной максимальной вероятности, требующей максимизации
В общем случае не существует решения замкнутой формы для оптимального ;, и это необходимо определить численно. Сначала отметим, что уравнение (9.4.49) эквивалентно уравнению (9.4.34), где параметры ; здесь обозначаются через ;, а переменные v - через y. В случае CRF входные данные просто определяют характеристику fk (y, x). В этом смысле итеративное масштабирование или любой связанный с ним метод Максимальной Вероятности обучающий Марковские сети с ограничениями может быть легко адаптирован, также усрешно получив всю экономию вычислений за счет деревьев соединений ограниченной ширины.
В качестве альтернативы здесь мы кратко опишем обучение на основе градиента. Градиент имеет компоненты
Термины <fi (y, xn)>p(y|x n ,;) могут быть проблематичными, и их проходимость зависит от структуры потенциалов. Для многомерного y, при условии, что структура клик, определенных на подмножествах y, является однозначно-соединенной, тогда вычисление среднего значения, как правило, выполнимо \ проходимо. В более общем плане, при условии, что клики результирующего дерева соединений имеют ограниченную ширину, можно получить точные маргинальные значения. Пример этого приведен для линейно-цепочечного CRF в разделе (23.4.3) – смотрите также пример (46) ниже.
Другой величиной, часто используемой для численной оптимизации, является коэффициент Гесса, который имеет компоненты
где приведенные выше средние значения относятся к p(y|xn , ;). Это выражение представляет собой (отрицательную) сумму элементов ковариации и, следовательно, является отрицательно (полу) определенным. Следовательно, функция L (;) является вогнутой и имеет только один глобальный оптимум. Хотя для оптимального ; не существует решения в замкнутой форме, оптимальные решения могут быть легко найдены с помощью численных методов, таких как сопряженные градиенты.
На практике термины регуляризации часто добавляются для предотвращения переобучения (обсуждение регуляризации приведено в разделе (13.2.3)). Использование термина
для положительных констант регуляризации c2k препятствует тому, чтобы веса ; были слишком большими. Этот член также имеет отрицательную определенность, и, следовательно, общая целевая функция остается вогнутой. Итеративное масштабирование также может быть использовано для обучения CRF, хотя на практике предпочтение отдается методам, основанным на градиенте[196].
После обучения CRF можно использовать для прогнозирования распределения выходных данных для нового входного x; . Наиболее вероятный результат y ; эквивалентно задается формулой
Поскольку член нормализации не зависит от y, нахождение наиболее вероятного результата эквивалентно
194 ПРОЕКТ от 9 марта 2010 г. Максимальная вероятность для неориентированных моделей
Рисунок 9.18: (a): Результаты обучения для линейной цепной CRF. Имеется 5 обучающих последовательностей, по одной для каждой подпанели. В каждом из них верхняя строка соответствует входной последовательности x1:20 , xt ; {1, . . . , 5} ( каждое состояние представлено другим цветом), средняя строка - правильной выходной последовательности y1:20 , yt ; {1, 2, 3} (каждое состояние представлено другим цветом ). Вместе входные и выходные последовательности образуют обучающие данные D. Внизу строка содержит наиболее вероятную последовательность вывода с учетом обученного CRF, аргумент maxy1:20 p(y1:20 |x1:20 , D). (b): Пять дополнительных тестовых последовательностей вместе с правильным выводом и предсказанной последовательностью вывода.
Обработка на естественном языке
В приложении для обработки естественного языка xt может представлять слово, а yt - соответствующий лингвистический тег ("существительное", "глагол" и т.д.). Более подходящей формой в этом случае является ограничение CRF на форму
для двоичных функций gk и hl и параметров µk и pl . Грамматическая структура переходов между тегами кодируется в gk (yt , yt-1 ), а лингвистическая информация о тегах ; в hk (yt , xt ), причем их важность определяется соответствующими параметрами[166]. В этом случае вывод маргинальных значений <yt yt;1 |x1:T> прост, поскольку факторный граф, соответствующий задаче вывода, представляет собой линейную цепочку.
Варианты линейной цепочки CRF широко используются при обработке естественного языка, включая части речи тегирование и машинный перевод (при котором входная последовательность x представляет собой предложение на Английском языке, а выходная последовательность y - соответствующий перевод на Французский). Смотрите, например, [213].
Пример 46 (Линейная цепочка CRF). Мы рассматриваем CRF с X = 5 входными состояниями и Y = 3 выходными состояниями вида
Здесь двоичные функции gk (yt , yt;1 ) = I [yt = ak ], I [yt;1 = bk ], k = 1, . . . , 9 моделируют переходы между два последовательных вывода. Двоичные функции hl (yt , xt ) = I [yt = al ] I [xt = cl ], l = 1, . . . , 15 моделируют преобразование входных данных в выходные. Таким образом, всего имеется 9 + 15 = 24 параметра. На рисунке(9.18) мы строим граф результатов обучения и тестирования на основе небольшого набора данных. Для обучения CRF используется 50 итераций подъема по градиенту со скоростью обучения 0,1. Смотрите проект demoLinearCRF.m.
от 9 марта 2010 г. 195 Свойства Максимального Правдоподобия
9.4.7 Псевдо вероятность \правдоподобность
Рассмотрим множество переменных x с dim x = D вида
Для всех значений ;c, кроме специально ограниченного, статистическая функция Z будет неразрешимой, а вероятность наличия набора данных ввода-вывода также будет неразрешимой. В качестве суррогата используется псевдо правдоподобность вероятности каждой переменной, обусловленной всеми другими переменными (что эквивалентно обусловленности только соседних переменных для MN)
Термины p(xni |xn\i |;) обычно просты в вычислении, поскольку они требуют нахождения нормализации только для одномерного распределения. В этом случае градиент может быть точно вычислен и выполнено обучение параметров ;. По крайней мере, для случая машины Больцмана это дает согласованную оценку[139].
9.4.8 Обучение структуры
Изучение структуры Марковской сети также может быть основано на тестах на независимость, как и в случае Сетей Убеждений. Критерием для нахождения MN на множестве узлов V является тот факт, что ни одно ребро не выходит между x и y, если, при условии всех остальных узлов, x и y считаются независимыми. Это попарного Марковского алгоритма свойство, описанное в разделе(4.2.1). Проверяя x ;y| V\ {x, y} для каждой пары переменных x и y, этот подход к удалению границ в принципе раскрывает структуру сети[219]. Для обучения структуры с помощью оракула этот метод является оптимальным. Однако практическая сложность в случае, когда независимость определяется на основе данных, заключается в том, что проверка того, является ли x ; y| V\ {x, y} в принципе требует огромных объемов данных. Причина этого заключается в том, что при обработке выбираются только те части набора данных, которые соответствуют условиям \кондиционированю. На практике это приведет к очень небольшому количеству оставшихся точек данных, и оценка
независимости на этой основе является ненадежной.
Граничный критерий Маркова[219] использует локальное свойство Маркова, описанное в разделе (4.2.1), а именно, что переменная, зависящая от своих соседей, не зависит от всех других переменных в графе. Начиная с переменной x и пустого набора окрестностей, можно постепенно включать соседей, проверяя, отвечает ли их включение, тому что остальные не-соседи независимы от x. Сложность заключается в том, что если один не имеет правильной Марковской границы, тогда может быть сочтено необходимым включить переменную в набор окрестностей. Чтобы убедиться в этом, рассмотрим сеть, которая соответствует линейной цепочке и в которой x находится на краю цепочки. В этом случае только ближайший сосед x находится на границе Маркова x. Однако, если бы этого ближайшего соседа в данный момент не было в наборе, то был бы включен любой другой не ближайший сосед, даже если это не является строго обязательным. Чтобы противостоять этому, переменные соседства включённые в окрестности x, могут быть позже удалены, если они будут сочтены излишними для границы[102].
В случаях, когда накладываются определенные ограничения, такие как обучающие структуры, результирующая триангуляция которых имеет ограниченную ширину дерева, хотя и остается формально сложной, доступны приближенные процедуры[260].
Что касается сетевых методов оценки для неориентированных сетей, вычисление оценки затруднено тем фактом, что параметры каждой группы объединяются в константу нормализации распределения. Эту проблему можно решить, используя гиперМарковские априоры[75].
9.5 Свойства Максимального Правдоподобия
9.5.1 Обучение \тренировки с использованием правильного класса модели
Рассмотрим набор данных X = {xn , n = 1, . . . , N }, сгенерированный на основе базовой параметрической модели p(x|;0). Наш интерес состоит в том, чтобы подобрать модель p(x|;) той же формы, что и правильная базовая модель p(x|;0 ) , и исследовать
196 ПРОЕКТ от 9 марта 2010 г. Код
соответствует ли параметр ;, полученный с помощью метода Максимального Правдоподобия, правильному параметру ;0 в случае ограничения большого объема данных . Приведенный ниже вывод не является строгим, но подчеркивает суть аргумента.
Предполагая, что данные являются распределенными независимо единствено i.i.d., логарифмическая вероятность L(;) ; log p(X |;) равна
В пределе N ; ; среднее значение выборки может быть заменено средним значением по отношению к распределению, генерирующему данные
С точностью до незначительной константы это расхождение Куллбэка-Лейблера между двумя распределениями в x, просто с разными настройками параметров. Величина ;, которая максимизирует L(;), является той, которая минимизирует отклонение\ расхождение\ Куллбэка- Лейблера, а именно ; = ;0 . В случае большого объема данных мы, в принципе, можем узнать правильные параметры (при условии, что мы знаем правильный класс модели). Свойство оценщика, заключающееся в том, что параметр ; сходится к истинному параметру модели ;0 по мере увеличения последовательности данных, называется согласованностью.
9.5.2 Обучение, когда предполагаемая модель неверна
Мы записываем q(x|;) для предполагаемой модели и p(x|;) для правильной генерирующей модели. Повторяя приведенные выше вычисления в случае, если предполагаемая модель верна, мы получаем, что, в пределе большого количества данных, вероятность равна
Поскольку q и p не имеют одинаковой формы, установка ; на ; не обязательно минимизирует KL(p(x|;)|q(x|;)) и, следовательно, не обязательно оптимизирует L(;).
9.6 Код
condindepEmp.m: Тест Байеса и взаимная информация для эмпирической условной независимости
condMI.m: Условная взаимная информация
condMIemp.m: Условная взаимная информация эмпирического распределения
MIemp.m: Взаимная информация эмпирического распределения
9.6.1 Компьютерный алгоритм с использованием оракула
В этой демонстрации используется оракул для определения x ; y | z, а не данные для определения эмпирической зависимости. Оракул сам по себе представляет собой Cеть Убеждений. Для частичной ориентации используется только первое правило "незамужнего коллайдера".
demoPCoracle.m: Демонстрация алгоритма для ПК с помощью оракула\ oracle
PCskeletonOracle.m: Алгоритм для ПК с использованием оракула\ oracle
PCorient.m: Ориентация скелета
9.6.2 Демонстрация эмпирической условной независимости
Для половины экспериментов данные получены из распределения, для которого x ; y| z является истинным. Для другой половины экспериментов данные получены из случайного распределения, для которого x ; y| z является ложным. Затем мы измеряем долю экспериментов, для которых тест Байеса правильно определяет x ;y| z. Мы также измеряем долю экспериментов, для которых тест взаимной информации правильно определяет x ; y| z, основываясь на
ЧЕРНОВИК от 9 марта 2010 г. 197 Упражнения
Запальный \ предохранитель
Барабан
Тонер \сморщено
Бумага
Ролик
Горение
Качество
Сморщенный
Мульт. Страницы
Замятие бумаги
Рисунок 9.19: Сеть Уверений в кошмарный сон Принтера. Все переменные являются бинарными. Верхние переменные, не имеющие родительских значений, - это возможные проблемы (диагнозы), а нижние переменные - последствия проблем (неисправности).
заданный порог, равный медиане всех эмпирических условных значений взаимной информации. Аналогичный эмпирический порог также может быть получен для коэффициента Байеса (хотя это не является строго кошерным в чистом Байесовском духе, поскольку в принципе порог должен быть равен нулю). Тест, приведен для сравнения основанный на предполагаемом чи-квадрат распределенный с коэффициентом MI, хотя он кажется непрактичным в случаях с небольшими данными.
demoCondIndepEmp.m: Демонстрация эмпирической условной независимости на основе данных
9.6.3 Изучение структуры Байеса-Дирихле
Интересно сравнить результат demoPCdata.m с demoBDscore.m.
PCskeletonData.m: Компьютерный алгоритм, использующий эмпирическую условную независимость
demoPCdata.m: Демонстрация компьютерного алгоритма с данными
BDscore.m: Оценка по методу Байеса-Дирихле (BD) для узла с заданными родителями
learnBayesNet.m: Учитывая порядок предков и максимальное количество родителей, изучите сеть
demoBDscore.m: Демонстрация процесса обучения структуры
9.7 Упражнения
Упражнение 116 (Кошмар для принтера). Честно говоря, Cheapco \Дешёвая Ко-мпания\ - это настоящая заноза в заднице. Они не только купили у StopPress \ Прекратите Нажимать\ старый лазерный принтер с сомнительными характеристиками и безжалостно его использовали, но и пытались избежать наказания за использование некачественных компонентов и материалов. К несчастью для StopPress, у них есть контракт на обслуживание старого боевого коня Cheapco, и в итоге они часто отправляют механика на ремонт принтера. После 10-го посещения они решили создать статистическую модель принтера Cheapco, чтобы иметь четкое представление о неисправности основываясь только на информации, которую секретарь Cheapco сообщает им по телефону. Таким образом, StopPress надеется, что сможет направить в Cheapco только младшего механика по ремонту, который, скорее всего, диагностирует неисправность по телефону.
Основываясь на информации производителя, StopPress имеет четкое представление о зависимостях в принтере и о том, что может непосредственно повлиять на другие компоненты принтера. Сеть предположений на рис. 9.19 отражает эти предположения. Однако конкретный способ, которым Cheapco злоупотребляет своим принтером, остается загадкой, так что точные вероятностные соотношения между неисправностями и проблемами характерны для Cheapco. В StopPress есть следующая таблица неисправностей для каждого из 10 посещений. Каждый столбец представляет собой одно посещение.
неисправность предохранителя в блоке фотобарабана ,
выход тонера,
низкое качество бумаги,
изношенный валик,
запах гари,
низкое качество печати,
смятые страницы,
замятие бумаги при подаче нескольких страниц
198 ЧЕРНОВИК от 9 марта 2010 года Упражнения
1. Приведенная выше таблица содержится в файле printer.mat. Обучите все элементы таблицы на основе Максимальной Вероятности.
2. Запрограммируйте Сеть Убеждений, используя таблицы Максимального Правдоподобия и BRMLtoolbox. Подсчитайте вероятность неисправности блока предохранителей, учитывая, что секретарь жалуется на запах гари и замятие бумаги, а также на отсутствие других проблем.
3. Повторите приведенный выше расчет, используя Байесовский метод, в котором во всех таблицах используется фиксированный Бета-априор.
4. Учитывая вышеприведенную информацию, полученную от секретаря, каков наиболее вероятный диагноз соединения по диагностическим параметрам – это наиболее вероятное соединение p (Использование \Предохранитель, Барабан, Тонер, Бумага, Роликовый|доказательный)?
Используйте метод максимального поглощения для соответствующего дерева соединений.
5. Вычислите наиболее вероятное состояние распределения p (При Использовании \Предохранитель, В Барабане, На Крышке, На Валике|Запах Гари, Замятие Бумаги)
Объясните, как эффективно рассчитать это, используя метод максимального поглощения.
Упражнение 117. Объясните, как использовать факторизованную Бета-версию в случае обучения записей таблицы в Сети Убеждений, в которых каждая переменная имеет максимум одного родителя. Рассмотрим проблемы, связанные с Байесовским подходом Обучения записей двоичной таблицы, когда количество родительских переменных не ограничено.
Упражнение 118. Рассмотрим данные xn , n = 1, . .P . , N . Покажите, что для гауссовского
распределения Максимальной Вероятности оценщик среднего значения равен m = N n=1 x, а дисперсия равна ; = N N n=1 (x ; m) .
Упражнение 119. Обучающий набор состоит из одномерных примеров из двух классов. Обучающими примерами из класса 1 являются
0.5, 0.1, 0.2, 0.4, 0.3, 0.2, 0.2, 0.1, 0.35, 0.25 (9.7.1)
и из класса 2 являются
0.9, 0.8, 0.75, 1.0 (9.7.2)
Сопоставьте (одномерную) гауссову величину с использованием Максимального Правдоподобия для каждого из этих двух классов. Также оцените вероятности классов p1 и p2, используя метод Максимального Правдоподобия. Какова вероятность того, что тестовая точка x = 0,6 относится к классу 1?
Упражнение 120. Для набора из N наблюдений (обучающих данных), X = x1 , . . . , xN и независимо собранных наблюдений логарифмическая вероятность того, что Сеть Убеждений сгенерирует X, равна
Мы определяем обозначение
это означает, что переменная xi находится в состоянии s, а родительские переменные xi находятся в векторе состояний t. Используя Лагранжиан
Покажем, что значение Максимального Правдоподобия для ;si (t) равно
ПРОЕКТ от 9 марта 2010 г.199 Упражнения
Упражнение 121 (Тренировка условного правдоподобия). Рассмотрим ситуацию, в которой мы разделяем наблюдаемые переменные в непересекающиеся множества x и y и что мы хотим найти параметры, которые максимизируют условную вероятность,
для набора обучающих данных {(xn , yn ) , n = 1, . . . , N }. Предполагается, что все данные получены из одного и того же распределения p(x, y|;0 ) = p(y|x, ;0 )p(x|;0 ) для некоторого неизвестного параметра ;0 . В случае большого объема ввода-вывода. по данным тренировки, имеет ли CL(;) оптимальное значение при ;0 ?
Упражнение 122 (Сопоставление моментов). Один из способов задать параметры распределения - сопоставить моменты от распределения к эмпирическим моментам. Иногда это соответствует Максимальному Правдоподобию ( например, для гауссова распределения), хотя в целом это не соответствует Максимальному Правдоподобию.
Для данных со средним значением m и дисперсией s покажите, что для определения бета;распределения по совпадению моментов мы используем
Упражнение 123. Для данных 0 ; xn ; 1, n = 1, . . . , N, полученных на основе Бета-распределения B (x|a, b), покажем , что логарифмическая вероятность определяется как
где B(a, b) - бета-функция. Покажите, что производные равны
где ;(x) ; d log ;(x)/dx - функция дигаммы, и предложите метод для определения параметров a,b.
Упражнение 124. Рассмотрим машину Больцмана, как определено в примере(44).
1. Вычислите градиент по отношению к "смещениям" wii.
2. Запишите псевдовероятность для набора идентификационных данных v1 , ... , vN и вычислите градиент по отношению к wij , i; j.
Упражнение 125. Покажите, что уравнение правдоподобия модели (9.3.54) может быть записано в явном виде в виде
Упражнение 126. Определите множество N как состоящее из 8 узлов Сетей Убеждений, в которых каждый узел имеет не более 2 родителей. Для данного предкового порядка a ограниченный набор записывается как Na
1. Сколько Сетей Убеждений существует в Na?
2. Каково вычислительное время, затрачиваемое на поиск оптимального члена Na с использованием Байесовской оценки Дирихле, предполагая, что вычисление балла BD для любого члена Na занимает 1 секунду, и принимая во внимание возможность разложения балла BD.
3. Сколько времени потребуется, чтобы найти оптимальный член N?
Упражнение 127. Для сети Маркова
выведите алгоритм итеративного масштабирования для изучения неограниченных таблиц ;1 (x, y) и ;2 (x, y) на основе набора данных ввода-вывода X, Y, Z.
200 ЧЕРНОВИК от 9 марта 2010 г. Упражнения
Упражнение 128. Учитывая данные тренировки x1 , ... , xn, выведите алгоритм итеративного масштабирования для максимально вероятной тренировки CRF вида
, где Z(;) = ; x ;ce;cfc(x) и неотрицательные признаки, fc (x) ; 0 (вы можете предположить, что все признаки x не могут быть равны нулю для любого заданного x).
Упражнение 129. Для данных X1 , . . . , Xn рассмотрим Максимально Правдоподобное обучение марковской сети p(X ) = ;c;c (Xc ) с потенциалами вида
где fc (Xc ) являются общими вещественнозначными функциями, а ;c - вещественнозначными параметрами. Учитывая
для вспомогательных переменных pc > 0, таких как ; c pc = 1, объясните, как получить форму итеративного алгоритма обучения масштабированию, в котором каждый параметр ;c может быть обучен отдельно.
ЧЕРНОВИК от 9 марта 2010 г. Упражнения
201
8-9Байесовские рассуждения смыслы и машинное обуче
© Copyright: Джон Темплтон, 2025
Свидетельство о публикации №125110906773
Свидетельство о публикации №125110906773
Рецензии