ЧЕРНОВИК главы от 9 марта 2010 г.
Глава 20
Моделей смесей
20.1 Оценка плотности с использованием смесей
Модель смеси - это модель, в которой набор моделей компонентов объединяется для получения более насыщенной модели:
Переменная v является ‘видимой’ или ‘наблюдаемой’, и h = 1, . . . , H индексирует каждый компонент модели p(v|h) вместе с его весом p(h). Смешанные модели имеют естественное применение при кластеризации данных, где h индексирует кластер. Эту интерпретацию можно получить, рассмотрев, как сгенерировать выборочную точку данных v из уравнения модели (20.1.1). Сначала мы выберем кластер h из p(h), а затем построим видимое состояние v из p(v|h).
Для набора данных ввода-вывода i.i.d. v 1 , . . . , v N модель смеси имеет вид, рис.(20.1),
Кластеризация достигается путем вывода значения
, что, благодаря факторизованной форме распределения, эквивалентно вычислению параметра arg max hn p(hn |vn ) для каждой точки данных. Таким образом, мы можем сгруппировать многие виды данных, для которых измерение "расстояния" в смысле классического алгоритма K-средних, раздел (20.3.5), не является очевидным напрямую.
Явно записав зависимость от параметров, получим модель
Оптимальные параметры ;v|h , ;h модели смеси чаще всего задаются по принципу Максимального Правдоподобия,
Численно это может быть достигнуто с помощью процедуры оптимизации, такой как градиентные подходы. В качестве альтернативы, рассматривая индексы компонентов как скрытые переменные, можно также применить алгоритм EM, описанный в следующем разделе, который во многих классических моделях позволяет получать простые формулы обновления.
365 Максимизация ожиданий для смесевых моделей
Рисунок 20.1: Модель смеси имеет простое графическое представление- запись в виде DAG с единственным скрытым узлом, который может находиться в одном из H состояний, i = 1 . . . , H. Предполагается, что параметры являются общими для всех точек данных.
Пример 86. Данные на рис. 20.2, естественно, имеют два кластера и могут быть смоделированы с помощью смеси двух двумерных Гауссиан, причем каждый Гауссиан описывает один из кластеров. Здесь дается четкая визуальная интерпретация значения термина "кластер", поскольку смешанная модель помещает две точки данных в один и тот же
кластер, если они, скорее всего, будут сгенерированы одним и тем же компонентом модели.
20.2 Максимизация ожидаемых результатов для моделей смешивания
Манипулируя индексом h как отсутствующей переменной, модели смеси могут быть обучены с помощью алгоритма EM, раздел (11.2). Существует два набора параметров – ;v|h для каждой модели компонентов p(v|h, ;v|h ) и ;h для веса смеси p(h|;h ). В соответствии с общим подходом к расчетным данным, описанным в разделе (11.2), нам необходимо учитывать энергетический член:
где
и максимизировать (20.2.2) относительно параметров ;v|h , ;h , h = 1, . . . , H.
20.2.1 Неограниченные дискретные таблицы
Здесь мы рассмотрим обучение простой сети убеждений p(v|h, ;v|h )p(h| ;h ), v = 1, . . . , V , h = 1, . . . , H, в которой таблицы не ограничены. Это частный случай более общей структуры, рассмотренной в разделе (11.2).
Рисунок 20.2: Двумерные данные, отображающие кластеры. В этом случае модель Гауссовой смеси 1/2 N (x| m1 , C1 ) + 1/2 N (x |m2 , C2 ) будет хорошо соответствовать данным для подходящих средних m1 , m2 и ковариаций C1 , C2 .
ЧЕРНОВИК от 9 марта 2010 г. Максимизация ожиданий для моделей смесей
M-шаг: p(h)
Если не задано никаких ограничений в p(h|;h ) мы можем записать параметры просто как p(h), понимая, что 0 ; p(h) ; 1 и ;hp(h) = 1. Изолируя зависимость уравнения (20.2.2) от p(h), получим
Теперь мы хотим максимизировать уравнение (20.2.4) относительно p(h) при условии, что ;jp(h) = 1. Обычно для решения этой задачи максимизации используются множители Лагранжа, см. упражнение (203). Здесь мы воспользуемся альтернативным подходом, основанным на признании сходства приведенного выше уравнения с формой дивергенции Кульбака- Лейблера. Сначала мы определяем распределение
Тогда уравнение максимизации (20.2.4) эквивалентно уравнению максимизации
, поскольку эти два выражения связаны постоянным коэффициентом ;h ;Nn=1 pold (h|v). Вычитая ;- независимый член <log ~p(h)>~p(h) из уравнения (20.2.6), мы получаем отрицательную дивергенцию Кульбака-Лейблера KL(~p|p). Это означает, что оптимальным p(h) является такое распределение, которое минимизирует расхождение Кульбака-Лейблера. Следовательно, оптимально ~p(h) = p(h), так что
M-шаг : p(v|h)
Зависимость уравнения (20.2.2) от p(v|h) равна
Если распределения p(v|h, ;v|h) не ограничены, мы можем применить аналогичный метод Кульбака-Лейблера, как мы это делали в разделе (11.2). Для совместимости с другими текстами, здесь мы далее демонстрируем процедуру стандартного метода Лагранжа. Нам нужно убедиться, что p(v|h) является распределением для каждого из состояний смеси h = 1, . . . , H. Этого можно достичь, используя набор множителей Лагранжа, дающих лагранжиан:
Дифференцируя относительно p (v = i|h = j) и приравнивая нулю,
Следовательно
что, используя требование нормализации, дает
ЧЕРНОВИК от 9 марта 2010 367 Максимизация ожиданий для смешанных моделей
Рисунок 20.3: Смесь из произведения распределений Бернулли. В Байесовской обработке используется параметр приор. В тексте мы просто задаем параметры, используя Максимальное Правдоподобие.
E-шаг
В соответствии с общей процедурой EM, приведенной в разделе(11.2), оптимально установить pnew (h|v n) = p(h|v n ):
Уравнения (20.2.7,20.2.12,20.2.13) повторяются до тех пор, пока не будет достигнута сходимость. Инициализация таблиц и смешение вероятностей могут серьезно повлиять на качество найденного решения, поскольку вероятность часто имеет локальные оптимумы. Если используются случайные инициализации, рекомендуется записать само приведенное значение вероятности, чтобы увидеть, какие параметры имеют более высокую вероятность. Предпочтение следует отдавать решению с наибольшей вероятностью.
20.2.2 Смесь произведений распределений Бернулли
Мы описываем простую модель смешения, которая может быть использована для кластеризации бинарных векторов, v = (v1 , . . . , vD )T , vi ; {0, 1}. Модель смешения произведений Бернулли1 задается формулой
где каждый член p (vi | h) является распределением Бернулли. Модель изображена на рис.20.3 и имеет параметры p(h) и p(vi = 1|h), h = 1 . . . , H.
Обучение EM
Для обучения модели с Максимальным Правдоподобием удобно использовать EM алгоритм, который, как обычно, может быть получен путем записи энергии:
, а затем выполняет максимизацию по записям таблицы. Из наших общих результатов, раздел(11.2), мы можем сразу перейти к обновлениям. M-шаг задается как
и E-шаг по
1Это похоже на наивный байесовский классификатор, в котором метки классов всегда скрыты.
ПРОЕКТ от 9 марта 2010 г. 368 Максимизация ожиданий для моделей смешивания
Рисунок 20.4: Данные, полученные из ответов на вопросник. Каждому из 150 человек было задано по 5 вопросов с ответами "да" (белый цвет) и ‘нет’ (серый цвет). Черный цвет означает отсутствие ответа (недостающие данные). Эти обучающие данные были получены с помощью двухкомпонентной биномиальной смеси. Отсутствующие данные были смоделированы путем случайного удаления значений из набора данных.
Уравнения (20.2.16,20.2.17) повторяются до тех пор, пока не будет достигнута сходимость.
Если атрибут i отсутствует для точки данных n, необходимо просуммировать состояния соответствующего vin . Результатом выполнения суммирования для этой модели является простое удаление соответствующего коэффициента p( vin |h) из алгоритма, см. упражнение(200).
Инициализация
Алгоритм EM может быть очень чувствителен к начальным условиям. Рассмотрим следующую инициализацию: p(vi =1|h = j) = 0,5, при этом p(h) устанавливается произвольно. Это означает, что на первой итерации pold (h = j|vn) = p(h = j). Последующие обновления на M-шаге
для любого j, j ` . Это означает, что параметры p(v|h) немедленно становятся независимыми от h, и модель численно оказывается в симметричном решении. Поэтому имеет смысл инициализировать параметры несимметричным образом.
Пример 87 (Анкета). Компания рассылает анкету, содержащую набор вопросов типа "да/нет"
, нескольким клиентам. Двоичные ответы клиента хранятся в векторе v = (v1 , . . . , vD )T . В общей сложности N клиентов прислали обратно свои анкеты, v1 , . . . , vN , и компания желает провести проверку анализ, позволяющий определить, какие типы клиентов у нее есть. Компания предполагает, что существует H основных типов клиентов, для которых профиль ответов определяется только типом клиента.
Данные из анкеты, содержащей 5 вопросов, с участием 150 респондентов, представлены на рисунке (20.4). В данных содержится большое количество пропущенных значений. Мы предполагаем, что существует H = 2 типа респондентов, и пытаемся отнести каждого респондента к одному из двух кластеров. Запускаем алгоритм EM на основе этих данных со случайными начальные значения для таблиц дают результаты, показанные на рис.20.5. На основе присвоения каждой точке данных vn кластера с максимальной апостериорной вероятностью hn = arg maxh p(h|vn), учитывая обученную модель p(v|h)p(h), модель присваивает 86% данных правильному кластеру (который известен в этом моделируемом случае). Смотрите рис.20.5. и MIXprodBern.m.
Рисунок 20.5: Обучение смеси продуктов Бернулли. (a): Истинное значение p(h) (слева) и обученное значение p(h) (справа) для h = 1, 2. (b): Истинное значение p (v|h) (слева) и обученное значение p(v|h) (справа) для v = 1, . . . , 5. Каждая пара столбцов соответствует p(vi |h = 1) (красный) и p(vi |h = 2) (синий) при i = 1, . . . , 5. Полученные вероятности достаточно близки к истинные значениям.
ПРОЕКТ от 9 марта 2010 369 Модель гауссовой смеси
Рисунок 20.6: Вверху: выборка из 200 из 5000 написанных от руки цифр в обучающем наборе. Внизу: обученный кластер выдает значение p(vi = 1|h) для h = 1, ... , 20 смесей. Смотрите демонстрационный вариант demoMixBernoulliDigits.m.
Пример 88 (Цифры, написанные от руки). У нас есть коллекция из 5000 цифр, написанных от руки, которые мы хотим сгруппировать в 20 групп, рис.20.6. Каждая цифра представляет собой двоичный вектор размером 28 ; 28 = 784. Используя смесь произведений Бернулли, обученных с помощью 50 итераций EM (со случайным изменением среднего значения данные, используемые в качестве инициализации), кластеры представлены на рис.20.6. Как мы видим, метод фиксирует естественные кластеры в данных – например, есть два вида 1, один из которых немного наклонен, два вида 4 и т.д.
20.3 Модель Гауссовой Смеси
Гауссовы коэффициенты являются особенно удобными компонентами непрерывной смеси, поскольку они представляют собой "выпуклости" вероятностной массы, способствующие интуитивной интерпретации модели. Напомним, что D-мерное гауссово распределение для непрерывной переменной x представляет собой
где m - среднее значение, а S - ковариационная матрица. Тогда смесь Гауссианов равна
где p(i) - вес смеси для компонента i. Для набора данных X = x1 , . . . , xN и при обычном предположении логарифмической вероятности логарифмическая вероятность равна
, где параметры ; = {mi , Si , p(i), i = 1, . . . , H}. Оптимальные параметры ; можно задать с помощью Максимальной Вероятности, принимая во внимание ограничение на то, что Si должен быть симметричным положительно определенным матрицы, в дополнение к 0 ; p(i) ; 1, ;i p(i) = 1. Подходы к оптимизации на основе градиента возможны при параметризации Si (например, декомпозиция Холецкого) и p(i) (например, softmax), которые обеспечивают соблюдение ограничений. Альтернативой является подход EM, который в данном случае особенно удобен, поскольку он автоматически обновляет параметры, обеспечивающие соблюдение этих ограничений.
20.3.1 EM алгоритм
Энергетический член равен
370 ЧЕРНОВИК от 9 марта 2010 г. Модель гауссовой смеси
Подключив определение гауссовых компонент, мы получим
Выполнение M-го шага требует максимизации вышеуказанного значения по отношению к mi , Si , p(i).
M- шаг: оптимальный mi
Максимизация уравнения (20.3.5) по отношению к mi эквивалентна минимизации
Дифференцируя относительно mi и приравнивая к нулю, мы имеем
Следовательно, оптимально,
Определяя распределение членов
который количественно определяет принадлежность точек данных к кластеру i, мы можем записать уравнение (20.3.8) более компактно в виде
M-шаг: оптимальное Si
Уравнение оптимизации (20.3.5) по отношению к Si эквивалентно минимизации
где ;ni ; xn ; mi . Чтобы облегчить матричный анализ, мы выделяем зависимость от Si, чтобы получить
Дифференцируя относительно S;1i и приравнивая к нулю, мы получаем
Используя коэффициент принадлежности pold(n|i), оптимальный Si определяется как
ПРОЕКТ от 9 марта 2010 371 Модель гауссовой смеси
Рисунок 20.7: Тренировка смеси из 10 изотропных Гауссиан (а): Если мы начнем с больших отклонений для Гауссиан, то даже после одной итерации Гауссианы будут центрированы близко к среднему значению гауссианы. данные. (b): Гауссианы начинают разделяться (c): Один за другим гауссианы перемещаются к соответствующим частям данных (d): Окончательное сходящееся решение. Гауссианы должны иметь отклонения, превышающие заданную величину. Смотрите демонстрацию demoGMMem.m.
Это гарантирует, что Si является симметричным положительным полуопределенным значением. Особый случай заключается в том, чтобы ограничить ковариации Si диагональными, для которых выполняется обновление, см. упражнение (201),
где указанный выше diag (M) означает формирование новой матрицы из матрицы M с нулевыми записями, за исключением диагональные элементы M. Более экстремальным случаем является изотропный Гауссиан Si = ;i2 I. Читатель может показать, что оптимальное обновление для ;i2 в этом случае задается путем вычисления среднего значения диагональных записей обновления ковариации с диагональными ограничениями,
M-шаг: оптимальные коэффициенты смешивания
Если на веса не наложено никаких ограничений, обновление выполняется по общей формуле, приведенной в уравнении (20.2.7),
E-шаг
В явном виде это определяется ответственностью
Приведенные выше уравнения (20.3.8,20.3.14,20.3.17,20.3.19) повторяются до тех пор, пока не будет достигнута сходимость.
Эффективность EM для гауссовых смесей может сильно зависеть от инициализации, которую мы обсудим ниже. Кроме того, для поиска разумных решений требуются ограничения на ковариационную матрицу.
372 ЧЕРНОВИК от 9 марта 2010 г. Модель гауссовой смеси
20.3.2 Практические вопросы
Бесконечные неприятности
Сложность возникает при использовании Максимального Правдоподобия для соответствия модели гауссовой смеси. Рассмотрим возможность размещения компонента p(x |mi , Si ) со средним значением mi в одной из точек данных mi = xn . Вклад от этого Гауссова значения будет равен
В пределе, когда "ширина" ковариации стремится к нулю (собственные значения Si стремятся к нулю), эта плотность вероятности становится бесконечной. Это означает, что можно получить Максимально Правдоподобное решение с помощью размещения Гауссиан нулевой ширины в выбранных точках данных приводит к бесконечному правдоподобию. Это явно нежелательно и связано с тем, что в этом случае решение с Максимальным Правдоподобием не ограничивает параметры разумным образом. Обратите внимание, что это не связано с алгоритмом EM, а является свойством самого метода Максимального Правдоподобия. Таким образом, все вычислительные методы, которые направлены на подгонку неограниченных комбинаций Гауссианов с использованием Максимального Правдоподобия, позволяют находить "разумные" решения, просто получая в ловушке благоприятных локальных максимумов. Решение заключается в дополнительном ограничении ширины Гауссианов, гарантирующем, что они не станут слишком маленькими. Один из подходов заключается в отслеживании собственных значений каждой ковариационной матрицы, и если обновление приведет к получению нового собственного значения, меньшего желаемого порогового значения, обновление отклоняется. В GMMem.m мы используем аналогичный подход, при котором мы ограничиваем детерминант ( произведение собственных значений) ковариаций, чтобы они были больше желаемого заданного минимального значения. Один можно увидеть формальный сбой метода Максимального Правдоподобия в случае Гауссовых смесей из-за несоответствующего априора. Метод Максимального Правдоподобия эквивалентен MAP, в котором на каждую матрицу Si помещен плоский априор. Это неразумно, поскольку требуется, чтобы матрицы были положительно определены и имели ненулевую ширину. Возможно Байесовское решение этой проблемы, основанное на использовании ковариационных матриц. Естественным приоритетом в этом случае является Распределение Уишарта или Гамма-распределение в случае диагональной ковариации.
Инициализация
Полезной стратегией инициализации является установка ковариаций по диагонали с большими отклонениями. Это дает компонентам возможность "почувствовать", где находятся данные. Иллюстрация эффективности алгоритма приведена на рис.20.7.
Нарушение симметрии
Если ковариации инициализированы большими значениями, то на первых итерациях алгоритм EM, по-видимому, не достигает большого прогресса, поскольку каждый компонент сталкивается с другими, пытаясь объяснить данные. В конце концов один Гауссовский компонент отделяется и берет на себя ответственность за объяснение данных, находящихся поблизости от него, см. рис. 20.7. То причиной такой путаницы является присущая решению симметрия – это не влияет на вероятность, если мы изменим названия компонентов. Эта симметрия перестановок вызывает первоначальную путаницу в отношении того, какая модель должна объяснять какие части данных. В конечном счете, эта симметрия нарушается, и находится локальное решение. Симметрии могут серьезно затруднить EM в подборе большого количества моделей в смеси, поскольку количество перестановок резко возрастает с увеличением количества компонентов. Эвристический подход заключается в том, чтобы начать с небольшого числа компонентов, скажем, с двух, для которых нарушение симметрии менее проблематично. Как только найдено локальное нарушенное решение, в смесь добавляется больше моделей, инициализированных в соответствии с текущими решениями. Таким образом, предусмотрена иерархическая схема нарушения. Другим популярным методом инициализации является привязка средств к тем, которые были найдены с помощью алгоритма K-means, однако это само по себе требует эвристической инициализации.
20.3.3 Классификация с использованием моделей Гауссовой смеси
Рассмотрим данные, полученные из двух классов, c ; {1, 2}. Мы можем сопоставить GMM p(x|c = 1, X1 ) с данными X1 из класса 1, а другой GMM p(x|c = 2, X2 ) с данными X2 из класса 2. Это приводит к двум GMM, зависящим от класса,
ЧЕРНОВИК от 9 марта 2010 г. 373 Модель гауссовой смеси
Рисунок 20.8: (а): Модель гауссовой смеси с H = 4 компонентами. Имеется компонент (фиолетовый) с большой дисперсией и малым весом, который практически не влияет на распределение вблизи того места, где остальные три компонента имеют заметную массу. По мере того, как мы удаляемся, этот дополнительный компонент приобретает все большее влияние. (b): Функция плотности вероятности GMM, полученная из (a). (c): Построенное в логарифмическом масштабе, влияние каждого из этих Гауссовых значений, удаленных от начала координат, становится более четким.
Для новой точки x; вероятность апостериорного класса равна
где p(c) - вероятность для предыдущего класса. Параметр Максимального Правдоподобия заключается в том, что p(c) пропорционален количеству точек обучения в классе c.
Рассмотрим тестовую точку x;, расположенную на значительном расстоянии от данных обучения для обоих классов. Для такой точки вероятность того, что данные были сгенерированы любой из двух моделей класса, очень мала. Однако одно из них будет намного
ниже другого (поскольку Гауссианы экспоненциально быстро снижаются), что означает, что апостериорная вероятность будет уверенно близка к 1 для того класса, который имеет компонент, наиболее близкий к x;. Это неудачная опора- скорее всего, так как в конечном итоге мы бы уверенно предсказывали класс новых данных, который не похож ни на что из того, что мы видели раньше. Мы бы предпочли противоположный эффект, когда для новых данных, отличных от обучающих данных, достоверность классификации падает, и все классы становятся равновероятными.
Выходом из этой ситуации является включение дополнительного компонента в Гауссову смесь для каждого очень широкого класса. Сначала мы собираем входные данные из всех классов в набор данных X , и пусть m - среднее значение из всех этих данных и вычисляем ковариацию. Затем для модели каждого класса данных c мы включаем дополнительные Гауссовы (исключая зависимость от X в нотации)
где
где ; - небольшое положительное значение, а ; увеличивает ковариацию (мы принимаем ; = 0,0001 и ; = 10 в demoGMMclass.m). Влияние дополнительного компонента на вероятность обучения незначительно, поскольку он имеет небольшой вес и большую дисперсию по сравнению с другими компонентами, см. рис.20.8. Однако, поскольку мы при удалении от области, где первые компоненты H имеют заметную массу, дополнительный компонент приобретает большее влияние, поскольку он имеет более высокую дисперсию. Если мы включим один и тот же дополнительный компонент в GMM для каждого класса c, то влияние этого дополнительного компонента будет одинаковым для каждого класса, доминируя по мере удаления от влияния других компонентов. Для точки, удаленной от обучающих данных, вероятность будет примерно одинаковой для каждого класса, поскольку в этой области доминирует дополнительный широкий компонент в равной степени. В этом случае апостериорное распределение будет стремиться к вероятности p(c) для предыдущего класса, уменьшая вредный эффект доминирования одного GMM, когда тестовая точка находится далеко от обучающих данных.
374 ЧЕРНОВИК от 9 марта 2010 г. Модель гауссовой смеси
Рисунок 20.9: Обучение и классификация GMM, обусловленной классом. (а): Данные из двух
разных классов. Мы сопоставляем GMM с двумя компонентами с данными из каждого класса. (Пурпурный) ромб - это контрольная точка мы будем классифицировать данные, далекие от тренировочных. (b): Верхняя подпанель - это вероятности классов p(c = 1|n) для 40 тренировочных точек, а 41-я точка является контрольной точкой. Нижняя подпанель представляет собой вероятности классов, но включает дополнительный Гауссовский член с большой дисперсией. Смотрите демонстрацию demoGMMclass.m.
Пример 89. Данные на рис.20.9,а) имеют кластерную структуру для каждого класса. На основе сопоставления GMM с каждым из двух классов тестовая точка (ромб), удаленная от обучающих данных, с уверенностью классифицируется как относится к классу 1. Это нежелательный эффект, поскольку мы бы предпочли, чтобы точки, удаленные от обучающих данных, не классифицировались с какой-либо определенностью. При включении дополнительной Гауссовой составляющей с большой дисперсией для каждого класса это мало влияет на вероятности классов в обучающих данных, но дает желаемый эффект, делая вероятность класса для тестовой точки максимально неопределенной, рис.20.9б).
20.3.4 Оценка Парцена
Оценка плотности Парцена формируется путем размещения "выпуклости массы", ;(x|xn), в каждой точке данных,
Популярным вариантом является (для D-мерного x)
получение смеси Гауссиан
Для оценки Парцена не требуется обучение – необходимо сохранить только положения N точек данных. Хотя метод Парцена является разумным и дешевым способом формирования оценки плотности, он не позволяет нам сформировать какое-либо более простое описание данных. В частности, мы не можем выполнить кластеризацию, поскольку существует предполагается, что в основе процесса генерации данных лежит не меньшее количество кластеров. Это отличается от GMMs, обученных с использованием метода Максимального Правдоподобия для фиксированного числа компонентов H ; N.
20.3.5 K-Значение
Рассмотрим смесь из K изотропных гауссиан, в которой каждая ковариация ограничена равным ;2I,
В то время как алгоритм EM не работает, если гауссову компоненту разрешено устанавливать mi равным точке
данных с ;2 ; 0, ограничивая все компоненты одинаковой дисперсией ;2, алгоритм работает хорошо
ЧЕРНОВИК от 9 марта 2010 г.
375 Модель гауссовой смеси
Алгоритм 19 K-means
1: Инициализируем центры mi , i = 1, . . . , K.
2: пока они не сходятся, делаем
3: Для каждого центра i найдите все xn, для которых i является ближайшим (в евклидовом смысле) центром.
4: Вызовем этот набор точек Ni . Пусть Ni - количество точек данных в наборе Ni .
5: Обновим средние значения
6: конец пока
Рисунок 20.10: (а): 550 точек данных, сгруппированных с использованием K-средних значений по 3 компонентам. Средние значения обозначены красными крестиками. (b): Изменение среднеквадратичного расстояния до ближайшего центра по итерациям алгоритма. Средние значения были инициализированы так, чтобы они были близки к общему среднему значению данных. Смотрите демонстрации demoKmeans.m.
предел определен как ;2 ; 0. Читатель может показать в упражнении (202), что в этом случае
уравнение распределения членов (20.3.9) становится детерминированным
, если mi ближе всего к xn
, в противном случае
В этом случае обновление EM (20.3.10) для среднего mi задается путем вычисления среднего значения точек, наиболее близких к mi . Этот ограничивающий и ограничиваемый GMM затем сводится к так называемому алгоритму K-средних, алгоритму (19). Несмотря на свою простоту, алгоритм K-средних быстро сходится и часто дает приемлемую кластеризацию, при условии, что центры инициализированы правильно. См. Рис.20.10.
K-средние часто используются как простая форма сжатия данных. Вместо того, чтобы отправлять точку данных xn, пользователь отправляет индекс центра, с которым она связана. Это называется векторным квантованием и является формой сжатия с потерями. Для улучшения качества может быть передано больше информации, такой как приблизительное значение разницы между x и соответствующим средним значением m, которое может быть использовано для улучшения восстановление сжатой точки данных.
20.3.6 Байесовские модели смеси
Байесовские расширения включают в себя установку приоритетов для параметров каждой модели в смеси, а также для распределения компонентов. В большинстве случаев это приводит к тому, что предельная вероятность является неразрешимым интегралом. Методы, которые приближают интеграл, включают методы выборки [98]. Смотрите также [109, 67] для приближенной вариационной обработки, основанной на Байесовских моделях смеси Гаусса.
20.3.7 Обучение под непосредственным наблюдением
В некоторых случаях мы можем знать, к какому компоненту смеси относятся определенные точки данных. Учитывая эту информацию, мы хотим создать модель смеси с заданным количеством компонентов H и параметрами ;. Мы записываем (v;m , hm ; ), m = 1, . . . , M для M известных точек данных и соответствующих компонентов, и (vn , hn ), n = 1, . . . , N для остальных точек данных, компоненты которых hn неизвестны. Таким образом, мы стремимся максимально увеличить число
376 ПРЕДВАРИТЕЛЬНЫЙ вариант от 9 марта 2010 г. Состав экспертов
Рисунок 20.11: Модель смеси экспертов. Прогнозирование выходных данных yn (реальных или непрерывных) с учетом входных данных xn в среднем- возраст превышает возраст отдельных экспертов p(yn |xn , whn ). Эксперт hn выбирается стробирующим механизмом с вероятностью p(hn |xn , U), так что некоторые эксперты будут более способны предсказать результат для xn в "своей’ части пространства. Параметры W, U могут быть получены с помощью метода Максимального Правдоподобия после маргинализации по скрытым экспертным переменным.
Вероятность
Если бы мы объединили все точки данных вместе, это, по сути, было бы эквивалентно стандартному неконтролируемому в этом случае следует ожидать, что некоторые из h будут зафиксированы в известных состояниях. Таким образом, единственное изменение в алгоритме EM заключается в терминах pold (h|v), которые являются дельта-функциями в известном состоянии, что приводит к незначительной модификации стандартного алгоритма, упражнение(205).
20.4 Смесь Экспертов
Модель смеси экспертов[149] связана с дискриминационным обучением выходного y-распределения, обусловленного входными данными x. Это может быть использовано в любом из контекстов регрессии классификации и имеет общую форму, см. рис.(20.11),
Здесь h обозначает компонент смеси. У каждого эксперта есть параметры W = [w1 , . . . , wH ] и соответствующие параметры стробирования U = [u1 , . . . , uH ]. В отличие от стандартной модели смеси, распределение компонентов p(h|x, U) зависит от входных данных x. Обычно это так называемое стробирующее распределение имеет форму softmax
Идея заключается в том, что у нас есть набор из H прогнозирующих моделей (экспертов), p(y|x, wh), каждая из которых имеет свой параметр wh, h = 1, . . . , H. Определяется, насколько модель h подходит для прогнозирования с текущими входными данными x путем согласования входных данных x с весовым вектором uh . Таким образом, входные данные x автоматически распределяются между соответствующими экспертами.
Обучение с Максимальной Вероятностью может быть достигнуто с помощью EM. Мы не будем полностью выводить алгоритм EM для модели смеси экспертов, а просто укажем направление, в котором будет продолжаться вывод. Для одной точки данных x энергетическим термином EM является
Для регрессии простым выбором является
и для (бинарной) классификации
ЧЕРНОВИК от 9 марта 2010 года 377 Индикаторные модели
В обоих случаях вычисление производных энергии по параметрам W является простым, так что легко доступен ЕМ алгоритм. Альтернативой EM является прямое вычисление градиента
вероятности с использованием стандартного подхода, рассмотренного в разделе (11.7).
Байесовский подход заключается в рассмотрении
, где обычно предполагается, что p(W) = ;hp(wh), p(U) = ;hp(uh). Интегралы, как правило, являются трудноразрешимой задачей, и требуются аппроксимации. Вариационный подход к регрессии и [43] вариационный подход к классификации приведены в [290]. В [143] рассматривается расширение выбора Байесовской модели, в которой оценивается количество
экспертов.
20.5 Индикаторные Модели
В рамках индикаторного подхода мы задаем распределение по кластерным назначениям. Для соответствия литературным данным мы используем показатель z, а не скрытую переменную h, хотя они играют ту же роль. A модель кластеризации с параметрами ; на компонентных моделях и совместным индикатором до p(z1:N ) принимает вид
Поскольку z n указывает на принадлежность к кластеру,
Ниже мы обсудим роль различных приоритетных показателей p(z1:N ) в кластеризации.
20.5.1 Подход к совместному показателю: факторизированный предварительный
Предполагая предварительную независимость показателей,
получаем из уравнения (20.5.2)
который восстанавливает стандартное уравнение смешанной модели (20.1.2). Как мы обсудим ниже, для явного управления сложностью назначений индикаторов можно использовать более сложные предварительные значения совместных индикаторов и открыть путь к, по сути, "бесконечномерным’ моделям.
20.5.2 Совместный индикаторный подход : приор Поля \Polya prior
Для большого количества доступных кластеров (компонентов смеси) K » 1 использование факторизованного распределения общих показателей потенциально может привести к переобучению, что приведет к незначительной или вообще не имеющей смысла кластеризации. Одним из способов управления эффективным количеством используемых компонентов является использование параметра ;, который регулирует сложность,
378 ЧЕРНОВИК от 9 марта 2010 г. Модели индикаторов
Рисунок 20.12: (а): Общая модель смеси для данных v1:N . Каждый zn указывает кластер для каждой точки данных. ; - это набор параметров, и zn = k выбирает параметр ;k для точки данных vn . (b): Для потенциально большого числа кластеров одним из способов управления сложностью является ограничение распределения общего \соединения, связки\ показателя \индикатора. (c): Обозначение на табличке (b).
Рисунок 20.13: Количество уникальных кластеров U при выборке показателей из распределения Поля уравнение (20.5.8) с ; = 2 и N = 50 точками данных. (a): K = 50, (b): K = 100, (c): K = 1000. Несмотря на то, что количество доступных кластеров K больше, чем количество точек данных, эффективное количество используемых кластеров остается ограниченным. Смотрите demoPolya.m.
где p(z|;) - категориальное распределение,
Удобным выбором для p(;) является распределение Дирихле (поскольку оно сопряжено с категориальным распределением),
Интеграл по ; в уравнении (20.5.5) можно вычислить аналитически, чтобы получить распределение Поля:
Количество используемых уникальных кластеров тогда задается как U =; k I [Nk > 0]. Распределение по вероятным числам кластеров контролируется параметром ;. Масштабирование ;/K в уравнении (20.5.7) обеспечивает разумный предел в виде K ; ;, см. рис.(20.13), в этом пределе модели известны как модели смеси процессов Дирихле. Такой подход означает, что нам не нужно явно ограничивать количество возможных компонентов K
поскольку количество активных компонентов U остается ограниченным даже при очень большом K.
Кластеризация достигается путем учета
На практике принято учитывать
К сожалению, апостериорный вывод p(z n |v 1:N ) для этого класса моделей формально не поддается вычислению, и требуются методы приближенного вывода. Подробное обсуждение этих методов выходит за рамки данной книги, и мы отсылаем читателя к [165] для детерминированного (вариационного) подхода и [206] для обсуждения подходов к выборке.
ПРОЕКТ от 9 марта 2010 г. 379 Смешанных моделей членства
Рисунок 20.14: Скрытое распределение \размещение \ Дирихле. Для документа n мы сначала выберем распределение тем ; n . Затем для каждой позиции w слова в документе n выберем распределение тем. Задав тему, мы затем выбираем тему zwn для выборки слова из распределения слов в этой теме. Параметрами модели являются распределения слов для каждой темы ; и параметры распределения тем ;.
20.6 Смешанные Модели Членства
В отличие от стандартных смешанных моделей, в которых предполагается, что каждый объект был создан из одного кластера, в моделях смешанного членства объект может быть членом более чем одной группы. Распределение, обсуждаемое ниже, является примером такой модели смешанного членства и является одной из ряда моделей, разработанных в последние годы [4, 91].
20.6.1 Скрытое \Латентное распределение\ размещение Дирихле
До сих пор мы рассматривали кластеризацию в том смысле, что предполагается, что каждое наблюдение было сгенерировано из одного кластера. Напротив, скрытое распределение Дирихле[44] и связанные с ним методы являются порождающими моделями смешанного членства, в которых каждая точка данных может принадлежать более чем одному кластеру. Типичный приложение предназначено для определения тематических групп в коллекции документов. Один документ содержит последовательность слов, например
Если каждому слову в доступном словаре присвоено уникальное состояние (скажем, dog = 1, tree = 2, cat = 3, . . .), то мы можем представить n-й документ в виде вектора
, где Wn - количество слов в n-м документе. Количество слов Wn в каждом документе может варьироваться, хотя общий словарь, из которого они взяты, является фиксированным.
Цель состоит в том, чтобы найти общие темы в документах, предполагая, что любой документ потенциально может содержать более одной темы. Полезно сначала подумать о базовой модели порождения слов, включая скрытые темы (которые мы позже объединим). Сначала мы выбираем распределение вероятностей (гистограмму), которое представляет темы, которые могут встречаться в этом документе. Затем для каждого слова-позиции в документе выбираем тему, а затем слово из распределения слов по этой теме. Математически для n и позиции слова w -ой в документе vwn, мы используем zn ; {1, . . . , K}, чтобы указать, какой из K возможных тем, к которым относится это слово. Для каждой темы k в словаре имеется категориальное распределение по всем словам i = 1, . . . , D:
Тема "животные" с высокой вероятностью содержит слова, похожие на животных, и т.д. Для каждого документа n у нас есть распределение тем ; n при ;; k=1 K ; kn = 1, которое дает скрытое описание документа в терминах его тематической принадлежности\ членства. Например, документ n (в котором обсуждаются вопросы, связанные с сохранением дикой природы) возможно, у вас будет распределение тем с большим количеством скрытых тем "животные" и "окружающая среда". Обратите внимание, что темы действительно являются скрытыми – название ‘животные’ будет дано постфактум в зависимости от типа слов
380 ПРОЕКТ от 9 марта 2010 г. - Смешанные модели членства
, которые будут генерироваться в скрытой теме, ;i|k . Как и в разделе(20.5.2), для контроля сложности можно использовать Дирихле, чтобы ограничить количество тем, активных в любом конкретном документе:
где ; - вектор длины, обозначающий количество тем.
Генеративная модель для выборки документа vn с Wn позициями слов такова:
1. Выберите ; n ~ Dirichlet (; n |;)
2. Для каждой позиции слова vw n , w = 1, . . . , Wn :
(а) Выберите тему zwn~p(zwn|;n)
(b) Выберите слово
Обучение модели LDA соответствует обучению параметров ;, которые относятся к количеству тем, и ;, которые описывают распределение слов в каждой теме. К сожалению, поиск необходимых маргинальных значений для обучения на основе апостериорных данных формально трудноразрешим с точки зрения вычислений. Эффективный приближенный логический вывод для этого класса моделей представляет исследовательский интерес, и недавно были разработаны как вариационные, так и выборочные подходы[44, 273, 225].
Существует большое сходство между LDA и PLSA[113], раздел (15.6.1), оба из которых описывают документ в терминах распределения по скрытым темам. LDA - это вероятностная модель, для которой такие вопросы, как настройка гиперпараметров, могут быть решены с использованием метода Максимального Правдоподобия. PLSA, с другой стороны, по сути, представляет собой метод матричной декомпозиции (такой как PCA). Такие вопросы, как настройка гиперпараметров, таким образом, для PLSA обрабатываются с использованием данных проверки. В то время как PLSA представляет собой описание только обучающих данных, LDA представляет собой модель генерирующих данных и в принципе может использоваться для синтеза новых документов.
Пример 90. Иллюстрация использования LDA приведена на рисунке (20.15)[44]. Документы взяты из корпуса TREC Associated Press, содержащего 16 333 новостных статьи с 23 075 уникальными терминами. После удаления стандартного списка стоп-слов (частых слов, таких как "the", "a" и т.д., которые в противном случае доминировали бы статистика), алгоритм EM (с вариационным приближенным выводом) был использован для нахождения параметров Дирихле и условных категориальных параметров для 100-тематической модели LDA. Лучшие слова из четырех полученных категориальных распределений ;i|k показаны на рисунке (20.15, а). Эти распределения отражают некоторые из основных тем в корпусе. Представлен пример документа из корпуса вместе со словами, окрашенными в соответствии с наиболее вероятной скрытой темой, которой они соответствуют.
20.6.2 Представление данных на основе графов
Смешанные модели членства используются в различных контекстах и отличаются также формой доступных данных. Здесь мы фокусируемся на анализе представления взаимодействий между коллекцией объектов; в частности, данные были обработаны таким образом, что вся интересующая информация характеризуется матрицей взаимодействий. Для графического представления данных два объекта подобны, если они являются соседями на графике, представляющем объекты данных. Например, в области социальных сетей каждый человек является представлен в виде узла на графе со связью между двумя узлами, если люди являются друзьями. При наличии графика может возникнуть желание идентифицировать сообщества тесно связанных друзей. На рисунке (20.16, а), изображенном как социальная сеть, пользователь 3 является членом своей рабочей группы (1, 2, 3), а также покерной группы (3, 4, 5). В остальном эти две группы пользователей не связаны. Обнаружение таких группировок контрастирует с разбиением графа на части, в котором каждому узлу присваивается только один из набора подграфов (рис.20.16, б), для которого типичный критерием является то, что каждый подграф должен быть примерно одинакового размера и что между подграфами должно быть мало связей [156].
ПРОЕКТ от 9 марта 2010 г. 381 Смешанные модели членства
Искусства
новый
фильм
кинопоказ, шоу
музыка
кинопостановка, кино
игра
мюзикл, музыкальный
лучшая
актёр
первый
йоркского
оперный театр
актриса
любовь
Бюджеты
миллион
тариф
программа
бюджет
миллиард
федеральный
год
расходы
новый
государственный
план
денежные
программы
правительство
конгресс
Дети
дети
женщины
люди
в детском
возрасте
семьи
работают
родители
говорят
о семейном
благополучии
мужчины
в процентах
заботятся
о жизни
Образование
школ
учащиеся
школы
образование
учителя
высшей
общественной
учитель
школы
Беннет
манигат
Намфи
штата
президент
элементарный
Гаити
(a)
Фонд Уильяма Рэндольфа Херста выделит 1,25 миллиона долларов Центру Линкольна, Метрополитен Опера, Нью-Йоркскому филармоническому оркестру и Джиллардской школе. "Наш совет директоров счел, что у нас появилась реальная возможность повлиять на будущее исполнительского искусства с помощью этих грантов, которые не менее важны, чем наши традиционные направления поддержки в области здравоохранения, медицинских исследований, образования и социальных услуг", - заявил президент Фонда Херста Рэндольф
А. Херст, объявляя о выделении грантов. Доля Линкольн-центра в строительстве нового здания, в котором разместятся молодые художники и будут созданы новые общественные помещения, составит 200 000 долларов. Метрополитен-опера и Нью-Йорк Филармонический оркестр получит по 400 000 долларов каждый. Джульярдская школа, где преподается исполнительское искусство и музыка, получат 250 000 долларов. Фонд Херста, ведущий спонсор Объединённого Корпоративного Фонда Линкольн-центра, также сделает свое обычное ежегодное пожертвование в размере 100 000 долларов.
(b)
Рисунок 20.15: (а): Подмножество скрытых тем, обнаруженных LDA, и слова с высокой вероятностью, связанные с каждой темой. Каждый столбец представляет тему, название которой, например, "искусство" , присваивается вручную после просмотра наиболее вероятных слов, соответствующих теме. (б): Документ с тренинга данные, в которых слова окрашены в соответствии с наиболее вероятной скрытой темой. Это демонстрирует смешанный характер модели, поскольку точка данных (в данном случае документ) присваивается нескольким кластерам (темам). Воспроизведено по [44].
Рисунок 20.16: (а) Социальная сеть группы из 5 человек, представленная в виде неориентированного графа. Здесь индивид 3 принадлежит к группе (1, 2, 3), а также (3, 4, 5). (b) Напротив, при разбиении графа на разделы граф разбивается на непересекающиеся разделы примерно одинакового размера, такие как что каждый узел является членом только одной секции с минимальным количеством ребер между секциями.
Другим примером является то, что узлы на графе представляют продукты, а связь между узлами i и j указывает на то, что клиенты, которые выбирают продукт i, часто также покупают продукт j. Цель состоит в том, чтобы разбить граф на группы, каждая из которых соответствует продуктам, которые клиенты обычно покупают совместно[116]. Растущая область применения графических представлений - биоинформатика, в которой узлы представляют гены, а связь между ними указывает на то, что эти два гена имеют сходные профили активности. Затем задача состоит в том, чтобы идентифицировать группы генов с аналогичным поведением[5].
20.6.3 Двоичные \ диадик данные
Рассмотрим два типа объектов, например, фильмы и клиентов. Каждый фильм имеет индекс f = 1, . . . , F , а каждый пользователь - u = 1, . . . , U . Взаимодействие пользователя u с фильмом f может быть описано элементом матрицы Muf, представляющим оценку, которую пользователь дает фильму. Двоичный набор данных состоит из такой матрицы, и цель состоит в том, чтобы разложить эту матрицу, чтобы объяснить рейтинги, найдя типы фильмов и типы пользователей.
В другом примере рассмотрим набор документов, объединенных матрицей взаимодействия, в которой Mwd равно 1, если слово w встречается в документе d, и равно нулю в противном случае. Эта матрица может быть представлена в виде двудольного графа, как показано на рис.20.17а). Верхние узлы представляют документы, а нижние — слова, между которыми есть связь, если это слово встречается в данном документе. Один из способов заключается в распределении документов по группам или скрытым "темам", чтобы кратко объяснить структуру связей двудольного графа с помощью небольшой таблицы\ числа скрытых узлов, схематично изображенных на рис.20.17, б). Это можно рассматривать как форму разложения матрицы на множители[136, 189]
, где t индексирует темы, а матрицы признаков U и V управляют сопоставлением слова с темой и темы с документом. Это отличается от скрытого распределения Дирихле, которое имеет вероятностную интерпретацию: сначала генерируется тема, а затем слово, в зависимости от выбранной темы. Здесь взаимодействие между матрицей V "документ-тема" и матрицей U "слово-тема" не является вероятностным. В более общем плане мы можем
382 ЧЕРНОВИК от 9 марта 2010 г. Модели смешанного членства
Рисунок 20.17: Графическое представление двоичных данных. (а): Имеется 6 документов и 13 слов. Ссылка указывает на то, что в наборе данных встречается конкретная пара слово-документ. (b): Скрытая декомпозиция (a) с использованием 3 "тем". Тема соответствует набору слов, а каждый документ - набору тем. Открытые узлы указывают на скрытые переменные.
написать распределение
, где U и V - матрицы признаков. В [189] вещественные данные моделируются с использованием
где U и V считаются двоичными, а действительное значение W - это матрица взаимодействия тем. С этой точки зрения обучение состоит из вывода U, W, V, учитывая диадическую матрицу наблюдений M. Предполагая факторизованные априорные значения, апостериорная матрица над матрицами равна
Удобным выбором является гауссово априорное распределение для W с матрицами признаков U и V, отобранными из априоров Бета-Бернулли. Результирующее апостериорное распределение формально является вычислительно трудноразрешимым, и в [189] это решается с помощью аппроксимации выборки.
20.6.4 Монадические данные
В монадических данных существует только один тип объектов, и взаимодействие между объектами представлено квадратной матрицей взаимодействия. Например, можно получить матрицу с элементами Aij = 1, если белки i и j могут связываться друг с другом, и 0 в противном случае. Матрица взаимодействий представлена в виде графа , на котором ребро представляет взаимодействие, например, на рис.20.18. В следующем разделе мы обсудим конкретную модель смешанного членства и выделим потенциальные области применения. Метод основан на клике декомпозиции графов и, как таковые, нам требуется краткий экскурс в представления графов на основе клик.
20.6.5 Клики и матрицы смежности для монадических двоичных \ бинари\ данных
Симметричная матрица смежности содержит элементы Aij ; {0, 1}, где 1 указывает на связь между узлами i и j. Для графа на рис.20.18 матрица смежности имеет вид
где мы включаем самостоятельные соединения по диагонали. Учитывая A, наша цель состоит в том, чтобы найти "более простое" описание, раскрывающее лежащую в основе кластерную структуру, такую как (1, 2, 3) и (2, 3, 4) на рис.20.18. Учитывая неориентированный граф на рис.20.18, матрица инцидентности Finc является альтернативным описанием структуры смежности[81].
Рисунок 20.18: Минимальное количество участников в кликах (1, 2, 3), (2, 3, 4).
ПРОЕКТ от 9 марта 2010 г. 383 Модели Смешанного членства
Рисунок 20.19: Двудольные представления разложений на рис. 20.18. Заштрихованные узлы представляют наблюдаемые переменные, а открытые узлы - скрытые переменные. (a) Представление матрицы инцидентности. (b) Минимальное разложение по кликам.
Учитывая V узлов на графе, мы строим Finc следующим образом: Для каждой связи i ~ j на графе формируем столбец матрицы Finc с нулевыми записями, за исключением 1 в i-й и j-й строках. Порядок столбцов следующий произвольный. Например, для графа на рис. 20.18 матрица инцидентности имеет вид
Матрица инцидентности обладает тем свойством, что структура смежности исходного графа определяется внешним произведением матрицы инцидентности на саму себя. Диагональные элементы содержат степень (количество связей) каждого узла. Для нашего примера это дает
так что
Здесь H(·) - поэлементная ступенчатая функция Хевисайда, [H(M)]ij = 1, если Mij > 0, и равно 0 в противном случае. Полезная точка зрения матрицы инцидентности заключается в том, что она идентифицирует две группы \клика на графе (здесь мы используем термин "группа \клика" в немаксимальном смысле). На рис. 20.18 представлено пять групп по 2 группы, и в каждом столбце Finc определяет, какие элементы входят в каждую 2-клику. Графически мы можем изобразить эту декомпозицию инцидентности в виде двудольного графа, как показано на рис. 20.19, а, где открытые вершины представляют пять 2-кликов. Матрица инцидентности \частоты, событий\ может быть обобщена для описания более крупных групп. Рассмотрим следующую матрицу как разложение на рис.20.18 и ее внешнее произведение:
Интерпретация заключается в том, что F представляет собой разложение на две 3-клики. Как и в матрице инцидентности, каждый столбец представляет собой клику, а строки, содержащие "1", указывают, какие элементы находятся в клике, определенной этим столбцом. Это разложение можно представить в виде двудольного графа на рис.20.19, б). Для графа на рис.20.18 и Finc, и F удовлетворяют
Можно рассматривать уравнение (20.6.14) как форму разложения двоичной матрицы на множители двоичной квадратной (симметричной) матрицы A в неквадратичные двоичные матрицы. Для наших целей кластеризации декомпозиция с использованием F предпочтительнее декомпозиции по инцидентности, поскольку F разбивает граф на меньшее число более крупных кликов. Формальной спецификацией задачи нахождения минимального числа максимальных полносвязных подмножеств является вычислительная задача MIN CLIQUE COVER [103, 251]. Действительно, F решает задачу MIN CLIQUE COVER для рис.(20.18).
384 ПРОЕКТ от 9 марта 2010 г. Модели смешанного членства
Рисунок 20.20: Функция ;(x) ; 1 + e;(0,5;x) ) -1 для ; = 1, 10, 100. Как ; увеличивается, эта сигмовидная функция стремится к ступенчатой функции.
Определение 106 (Матрица Клик). Учитывая матрицу смежности [A]ij , i, j = 1, . . . , V (Aii = 1), матрица клики F содержит элементы Fic ; {0, 1} , i = 1, . . . , V, c = 1, . . . , C, такие, что A = H(FFТ ). Диагональные элементы [ FFT ]ii выражает количество кликов/столбцов, в которых встречается узел i. Недиагональные элементы [FFT ]ij содержат количество кликов/столбцов, которые совместно занимают узлы i и j [18].
В то время как найти разложение по кликам F просто (например, используйте матрицу инцидентности), найти разложение по кликам2 с минимальным количеством столбцов, т.е. решить задачу МИНИМАЛЬНОГО ПОКРЫТИЯ КЛИК- MIN CLIQUE COVER, является NP-сложной задачей [103, 10].
Порождающая модель матриц смежности
Решение задачи МИНИМАЛЬНОГО ПОКРЫТИЯ КЛИКАМИ- MIN CLIQUE COVER является сложной вычислительной задачей, и приближения, как правило, неизбежны. Ниже мы ослабим строгое требование к кликам и предположим, что при условии наличия лишь небольшого числа ссылок если "почти клика" отсутствует, то это можно считать достаточно хорошо связанной группой узлов, чтобы сформировать кластер.
Учитывая матрицу смежности A и предшествующую матрицу кликов F, нас интересует следующее
Сначала мы сосредоточимся на производящем члене p(A|F). Чтобы найти "хорошо связанные" кластеры, мы ослабляем ограничение на то, что разложение в исходном графе происходит в виде клик, и рассматриваем отсутствие связей как статистические отклонения от идеальной клики. Учитывая матрицу F размера V ; C, мы хотим, чтобы чем выше чем больше перекрытие между строками 3 fi и fj, тем больше вероятность связи между i и j. Это может быть достигнуто, например, с помощью,
при
где ; управляет крутизной функции, см. рис.(20.20). Сдвиг на 0,5 в уравнении (20.6.17) гарантирует, что ; приблизительно соответствует ступенчатой функции, поскольку аргумент ; является целым числом. Согласно уравнению (20.6.16), если fi и fj имеют хотя бы одну "1" в одной позиции, то fi fjT ; 0,5 > 0 и значение p(Aij = 1|F) велико. Отсутствует вклад ссылки p(Aij = 0|F) = 1 ; p(Aij = 1|F). Параметр ; определяет, насколько строго ;(fi fjT ) соответствует A; при больших значениях ; допускается очень малая гибкость, и будут идентифицированы только клики. При малом ; подмножества, которые были бы кликами, если бы не небольшое количество недостающих ссылок, объединяются в кластеры. Настройка ; зависит от пользователя и проблемы.
Предполагая, что каждый элемент матрицы смежности выбирается независимо от процесса генерации, общая вероятность наблюдения A равна (без учета его диагональных элементов),
Наибольший интерес представляет апостериорное распределение структуры клик, уравнение (20.6.15), для которого мы теперь задаем априорное значение p(F) для матриц клик.
3 Мы используем нижние индексы fi для обозначения i-й строки F.
ПРОЕКТ от 9 марта 2010 г. 385 Модели смещанного членства
Рисунок 20.21: (а): Таблица смежности 105 Книг о Политике (черный цвет=1). (b): Матрица клик: 521 ненулевая попытка. (c): Реконструкция смежности с использованием приблизительной матрицы клик с 10 кликами – см. также рис. 20.22 и demoCliqueDecomp.m.
1000 лет мести
Буш против Кольцевая дорога
Война Чарли Уилсона
Потеря Бен Ладена
Спящий с дьяволом
Человек, Который предупреждал Америку
Почему Америка спала
Призрачные войны
Национальной Партии больше нет
Страна буша
Нарушение служебных обязанностей
Наследие
Отрубить им Головы
Преследование
Война Рамсфелда
Разрушение
Предательство
Заткнись и пой
Должен был стать
Правильным человеком
В десяти минутах от нормы
План Хиллари
Предательство французами Америки
Истории с Левого берега
Ненавидящий Америку
Третий террорист
Эндшпиль
Сестры-пиарщицы
Все люди шаха
Опасная дипломатия
Цена верности
Дом Бушей, Дом Саудов
Смерть правых и неправых
Полезные идиоты
Фактор О'Рейли
Пусть звучит свобода
Те, кто вторгается на чужую территорию
Предвзятость
Клевета
Дикая нация
Избавь нас от Зла
Дай мне передышку
Враг внутри нас
Настоящая Америка
Кто за Вами присматривает?
Официальное руководство "Обширный заговор правых"
Силовые игры
Высокомерие
Идеальная жена
Буши
За что стоит Бороться
Неожиданность, безопасность, Американский опыт
Союзники
Почему важна смелость
Голливуд прервал нас
Сопротивляемся
Мы победим
Вера Джорджа Буша-Младшего
Восстание вулканцев
Сократите это!
Глупые белые люди
Раш Лимбо - Большой жирный идиот
Лучшая демократия, которую можно купить за деньги
Культура страха
Свободная Америка
Выбор
Великий развал
Нация-изгой
Мягкая сила
Колосс
Горести империи
Против всех врагов
Американская династия
Большая ложь
Ложь Джорджа У. Буш
Хуже, чем Уотергейт
План нападения
Буш в состоянии войны
Новый Перл-Харбор
Женщины Буша
Мыльный пузырь американского превосходства
Живая история
Политика правды
Фанатики и дураки
Изнуренный
Разоружение Ирака
Ложь и лжецы, которые ее рассказывают
"50 способов любить свою страну" от MoveOn
Покупка президента, 2004 год
Совершенно законно
Гегемония или выживание
Исключение для правителей
Свободомыслящие
Надоело?
Это все еще экономика, Тупица!
Мы правы, а они нет
Какие либеральные СМИ?
Войны Клинтонов
Оружие массового обмана
Чувак, где Моя Страна?
Воры на высоких постах
Кустарник
Взбодрись, подлизывайся
Будущее свободы
Империя
Рисунок 20.22: Политические книги. Матрица клик размером 105 ; 10, разбитая политически
проницательным читателем на 3 группы. Черный квадрат означает q(fic ) > 0,5. Либеральные книги (красные), Консервативные книги (зеленые), Нейтральные книги (желтые). По результатам проверки, группы 5,6,7,8,9 в основном соответствуют "консервативным" книгам.
Матрица групп до p(F)
Поскольку нас интересует кластеризация, в идеале мы хотим разместить в кластере как можно больше узлов графа. Это означает, что мы хотим изменить вклады в матрицу смежности A, чтобы они происходили от небольшого числа столбцов F. Чтобы достичь этого, мы сначала переопределяем параметры F как
где ;c ; {0, 1} играют роль индикаторов, а fc - столбец c из F. Cmax - предполагаемое максимальное число кластеров. В идеале мы хотели бы найти F с небольшим числом показателей ;1 , . . . , ;Cmax в состоянии 1. Для достижения этой цели мы определяем предварительное распределение на бинарном гиперкубе ; = (;1 , . . . ,;Cmax ),
Чтобы небольшое число ;`cs было равно 1, мы используем бета-априорное значение p(;) с подходящими параметрами, гарантирующими, что ; меньше 0,5. Это приводит к Бета-распределению Бернулли
где B(a, b) - бета-функция, а N = ;Cmax c=1 ;c - это количество индикаторов в состоянии 1. Чтобы
гарантировать, что только небольшое количество компонентов должно быть активным, мы установили a = 1, b = 3 (что соответствует среднему значению ;, равному 0,25, и дисперсии 0,0375. Распределение (20.6.21) находится в вершинах бинарного гиперкуба {0, 1}Cmax со смещением в сторону вершин, близких к началу координат (0, . . . , 0). Согласно уравнению (20.6.19), предшествующее значение ; индуцирует предшествующее значение F. Результирующее распределение p(F, ;|A) ; p(F|;)p(;) формально неразрешимо, и в [18] это решается с помощью вариационного метода. Смотрите cliquedecomp.c и cliquedecomp.m.
Матрицы клик также играют естественную роль в параметризации положительно определенных матриц, см. упражнение(206)[18].
386 ЧЕРНОВИК от 9 марта 2010 года Упражнения
Пример 91 (Кластеризация Книг по Политике). Данные состоят из 105 книг о политике США, проданных онлайн-книготорговцем Amazon. Матрица смежности с элементом Aij = 1 (рис.20.21, а) отражает частоту совместных покупок книг i и j (Валдис Кребс, www.orgnet.com). Кроме того, книги могут быть названы "либеральными", "нейтральными" или "консервативными", в зависимости от мнения политически проницательного читателя (www-personal.umich.edu/;mejn/netdata/). Интерес заключается в распределении книг по группам, используя только, а затем посмотрите, соответствуют ли эти группы каким-либо образом политическим тенденциям, описанным в каждой книге. Обратите внимание, что информация здесь минимальна – алгоритму кластеризации известно только, какие книги были приобретены совместно (матрица А); никакая другая информация о содержании или названии книг алгоритмом не используется. При начальном значении Cmax = 200 кликов, Бета-параметрах a = 1, b = 3 и крутизне ; = 10 наиболее вероятное решение с задним пределом содержит 142 клика (рис.20.21, б), что дает идеальную реконструкцию из смежности А. Для сравнения, матрица инцидентности содержит 441 2-клик. Однако эта матрица кликов слишком велика, чтобы обеспечить компактную интерпретацию данных – на самом деле кластеров больше, чем книг. Чтобы сгруппировать данные более эффективно, мы фиксируем значение Cmax = 10 и повторно запускаем алгоритм. Это приводит только к приблизительному разложению по кликам, A ; H(FFT ), как показано на рис.20.21в). Результирующая приблизительная матрица кликов размером 105 ; 10 представлена на рис.20.22 и демонстрирует, как отдельные книги представлены в более одного кластера. Интересно, что кластеры, найденные только на основе матрицы смежности, имеют некоторое соответствие с политической направленностью каждой книги; группы 5, 6, 7, 8, 9 соответствуют в основном ‘консервативным’ книгам. Большинство книг принадлежат более чем одной группе / кластеру, что позволяет предположить, что они не являются книгами по одной теме, что согласуется с предположением о смешанной модели членства.
20.7 Дальнейшее чтение
Литература по моделированию смесей обширна, и хороший обзор и введение в литературу содержатся в [188].
20.8 Код
MIXprodBern.m: Демонстрация смеси продуктовых распределений
MIXprodBernoulli.m: Демонстрация смеси продуктовых распределений Бернулли
GMMem.m: Демонстрация смеси гауссовых уравнений.
GMMloglik.m: Демонстрация логарифмической вероятности
GMMMEM.m: Демонстрация EM для смеси гауссиан
demoGMMclass.m: Демонстрация GMM для классификации
Kmeans.m: Демонстрация K-средних значений Kmeans
demoKmeans.m: Демонстрация K-средних значений
demoPolya.m: Демонстрация количества активных кластеров из распределения Поля
dirrnd.m: Генератор случайного распределения Дирихле
cliquedecomp.m: Разложение матрицы клик
cliquedecomp.c: Разложение матрицы клик (C-код)
DemoCliqueDecomp.m: Демонстрационная декомпозиция матрицы кликов
20.9 Упражнения
Упражнение 200. Рассмотрим несколько разложенных на множители моделей
ЧЕРНОВИК от 9 марта 2010 года 387 Упражнения
Для предполагаемых данных ввода-вывода i.i.d. vn , n = 1, . . . , N некоторые компоненты наблюдений могут отсутствовать, так что, например , третий компонент пятой точки данных, v35, неизвестен. Покажите, что обучение с максимальным правдоподобием на наблюдаемых данных соответствует игнорированию отсутствующих компонентов vin.
Упражнение 201. Выведите оптимальное обновление EM для подгонки смеси гауссианов при условии, что ковариации являются диагональными.
Упражнение 202. Рассмотрим смесь из K изотропных гауссианов, каждый из которых имеет одинаковую ковариацию, Si = ;2I. В пределе ;2 ; 0 покажите, что алгоритм EM стремится к алгоритму кластеризации с использованием K-средних.
Упражнение 203. Рассмотрим термин
Мы хотим оптимизировать вышеописанное в отношении распределения p(h). Этого можно достичь, определив Лагранжиан
Дифференцируя Лагранжиан относительно p (h) и используя ограничение нормализации, покажем, что оптимально
Упражнение 204. Мы показали, что подгонка неограниченной смеси Гауссианов с использованием Максимального Правдоподобия проблематична, поскольку, помещая один из гауссианов поверх точек данных и позволяя детерминанту ковариации равняться нулю, мы получаем бесконечную вероятность. Напротив, при подгонке одного Гауссова значения N (x µ, ;) к i.i.d. данные x1 , x2 , . . . , xN показывают, что оптимум Максимального Правдоподобия для ; имеет ненулевой определитель и что оптимальное Правдоподобие остается конечным.
Упражнение 205. Измените GMMem.m соответствующим образом, чтобы он мог работать с частично контролируемым сценарием, в котором известен компонент смеси h некоторых наблюдений v.
Упражнение 206. Вы хотите параметризовать ковариационные матрицы S при условии, что указанные элементы равны нулю. Ограничения задаются с использованием матрицы A с элементами Aij = 0, если Sij = 0, и Aij = 1 в противном случае. Рассмотрим матрицу кликов Z, для которой
и матрица
при
для параметров ;. Покажите, что для любого ;, S; является положительно полуопределенным и параметризует ковариационные матрицы при нулевых ограничениях, заданных A.
388 ЧЕРНОВИК от 9 марта 2010 года Глава
Глава 21
Скрытые линейные модели
21.1 Факторный анализ
В главе (15) мы обсуждали Анализ Главных Компонент, который формирует представления данных с меньшей размерностью, основываясь на предположении, что данные лежат близко к гиперплоскости. Здесь мы описываем соответствующую вероятностную модель, для которой могут быть предусмотрены расширения Байесовских методов. Любая вероятностная модель может также использоваться в качестве компонента более крупной и сложной модели, такой как смешанная модель, что позволяет проводить естественные обобщения.
Мы используем v для описания реального вектора данных, чтобы подчеркнуть, что это видимая (наблюдаемая) величина. Затем набор данных задается набором векторов,
где dim (v) = D. Наш интерес состоит в том, чтобы найти вероятностное описание этих данных с меньшей размерностью. Если данные лежат близко к H-мерной гиперплоскости, мы можем точно аппроксимировать каждую точку данных с помощью низкой H-мерной системы координат. В общем случае точки данных не будут точно располагаться на гиперплоскости, и мы моделируем это расхождение с помощью Гауссовского шума. Математически модель FA генерирует наблюдение v в соответствии с
где шум ; распределен по Гауссу,
Постоянное смещение c задает начало отсчета системы координат. Матрица загрузки факторов F играет ту же роль, что и базисная матрица в PCA, см. раздел (15.2). Аналогично, скрытые координаты h играют роль компонентов, которые мы использовали в разделе (15.2).
Разница между PCA и Факторным Анализом заключается в выборе ;:
Вероятностный PCA
Факторный Анализ
389 Факторный Анализ
Рисунок 21.1: Факторный анализ. Видимая векторная переменная v связана со скрытой векторной переменной h линейным отображением с независимым аддитивным Гауссовым шумом для каждой видимой переменной. Предыдущее значение скрытой переменной может быть принято за изотропную Гауссову переменную, таким образом, независимо от ее компонентов.
Вероятностное описание
Из уравнения (21.1.2) и уравнения (21.1.3), учитывая h, данные распределены по Гауссу со средним значением Fh + c и ковариацией ;
Чтобы завершить построение модели, нам нужно указать скрытое распределение p(h). Удобным выбором является гауссово
В этом случае координаты h будут предпочтительно сосредоточены вокруг значений, близких к 0. Если мы выберем значение h из p(h), а затем построим значение для v, используя p (v|h), выбранные векторы v дадут блюдце или ‘блин’ из точек в пространстве v. Использование коррелированного гауссовского априора p (h) = N (h|0, ;H) не влияет на сложность модели, поскольку ;H может быть учтено в F, упражнении(209). Поскольку v линейно связано с h с помощью уравнения (21.1.2), а ; и h являются гауссовыми, то v распределено по Гауссу. Среднее значение и ковариацию можно вычислить, используя результаты распространения в разделе (8.6.3).:
Неизменность вероятности при вращении факторов
Поскольку матрица F появляется в конечной модели p(v) только через FFT + ;, вероятность не изменится, если мы повернем F, используя FR, с RRT = I:
Таким образом, пространство решений для F не является уникальным – мы можем произвольно поворачивать матрицу F и создавать равновероятную модель данных. Поэтому при интерпретации записей в F требуется некоторая осторожность. Varimax обеспечивает более удобную для интерпретации F, используя подходящую матрицу вращения R. Цель состоит в том, чтобы создать повернутую F, для которой в каждом столбце было бы только небольшое количество больших значений. Поиск подходящего поворота это приводит к задаче нелинейной оптимизации, которую необходимо решать численно. Подробности см. в [185].
21.1.1 Поиск оптимального смещения
Для набора данных V и с использованием обычного предположения i.i.d. логарифмическая вероятность равна
где
Дифференцируя уравнение (21.1.10) относительно c и приравнивая его нулю, мы получаем оптимальную настройку вероятности Максимального Правдоподобия, при которой смещение c является средним значением данных,
390 ЧЕРНОВИК от 9 марта 2010 Факторный анализ : Максимальная вероятность
Рисунок 21.2: Факторный анализ: 1000 баллов, полученных на основе модели. (a): 1000 скрытых двумерных точек hn, отобранных из N (h|0, I). Они преобразуются в точки на трехмерной плоскости с помощью xn0 = c + Fhn . Ковариация x0 является вырожденной, с ковариационной матрицей FFT . (b): Для каждой точки xn0 на плоскости из N (; |0, ;) берется вектор случайного шума и добавляется к вектору на плоскости, чтобы сформировать выборку xn, выделенную красным цветом. Распределение точек в пространстве образует "блин". Точки "под" плоскостью не отображаются.
Мы будем использовать эту настройку повсюду. При такой настройке логарифмическое уравнение правдоподобия (21.1.10) может быть записано как логарифмическое
где S - выборочная ковариационная матрица
21.2 Факторный Анализ : Максимальное Правдоподобие
Сейчас мы специализируемся на предположении, что ; = diag (;1 , . . . ,;D ). Мы рассмотрим два метода изучения факторных нагрузок F: "прямой" подход1, раздел (21.2.1) и EМ-подход, раздел (21.2.2).
21.2.1 Прямая оптимизация вероятности
Оптимальное значение F при фиксированном ;
Чтобы найти значение максимального правдоподобия F, мы дифференцируем логарифмическое уравнение правдоподобия (21.1.13) относительно F и приравниваем к нулю. Это дает
Используя ;F (FFT ) = F(;F FT ) + (;F F)FT , задается стационарная точка , когда
Поскольку ;D обратимо, оптимальное значение F удовлетворяет
Используя определение ;D, уравнение (21.1.11), можно переписать ;;1 DF как (см. упражнение(210))
1Изложение здесь полностью соответствует изложению в [302].
ЧЕРНОВИК от 9 марта 2010 г. 391Факторный анализ : максимальное правдоподобие
Если включить это в условие нулевой производной, уравнение (21.2.3) примет вид
Использование повторных параметров
уравнение (21.2.5) может быть записано в ‘изотропной’ форме
Мы предполагаем, что преобразованная матрица коэффициентов ^F имеет тонкую SVD-декомпозицию
где dim UH = D ; H, dim L = H ; H, dim V = H ; H и
и L = diag (l1 , . . . , lH ) - сингулярные значения ^F. Применив это предположение к уравнению (21.2.7), получим
, что дает
Уравнение (21.2.11), таким образом, является собственным уравнением для UH . Интуитивно понятно, что тогда нам нужно найти вычисляем собственное значение ~S и затем устанавливаем в столбцах UH те собственные векторы, которые соответствуют наибольшим собственным значениям. Это более формально описано ниже.
Определяем соответствующие собственные значения
Мы можем связать форму решения с собственным разложением ~S
, где Ur - произвольные дополнительные столбцы, выбранные для заполнения UH с образованием ортогональной U, U T U = UU T= I. Используя ; = diag (;1 , ... , ;D ), уравнение (21.2.11) определяет 1 + li2 = ;i , или li = ;;i ; 1. Учитывая решение для ~F, решение для F найдено из уравнения (21.2.6). Чтобы определить оптимальный ;i, мы запишем логарифмическую вероятность в терминах ;i следующим образом. Используя новую параметризацию,
и S = ; 1/2 ~S; 1/2 , мы имеем
Логарифмическое уравнение правдоподобия (21.1.10) в этой новой параметризации имеет следующий вид
Используя ;i = 1 + li2 и уравнение (21.2.8), мы можем записать
392 ЧЕРНОВИК от 9 марта 2010 г. Факторный анализ : максимальная вероятность
,так что
Аналогично
Используя это, мы можем записать логарифмическую вероятность как функцию собственных значений (для фиксированного ;) в виде
Чтобы максимизировать вероятность, нам нужно минимизировать правую часть приведенного выше уравнения. Поскольку log ; < ;, мы должны поместить наибольшие собственные значения H в член ;i log ;i. Таким образом, решение для фиксированного ; является
, где
- это H наибольших собственных значений ;-1/2 S;-1/2, где UH - матрица соответствующих собственных векторов. R - произвольная ортогональная матрица.
Подход, основанный на SVD
вместо того, чтобы находить собственное разложение ;- 2 s;; 2, мы можем избежать формирования ковариационной матрицы, рассмотрев тонкое SVD;разложение
, где матрица данных равна
Дано тонкое разложение
мы получаем собственные значения ;i = ~;2ii . Для D > N это удобно, поскольку вычислительная сложность при использовании этого метода SVD составляет O(min (H, N )3) . Когда матрица X слишком велика для хранения в памяти, онлайн-вычисление выполнимо с помощью доступных методов SVD[49].
Поиск оптимального ;
Нулевая производная логарифмического правдоподобия выполняется, когда
где F задается уравнением (21.2.20). У уравнений (21.2.25, 21.2.20) нет решения в замкнутом виде. A простая итерационная схема заключается в том, чтобы сначала угадать значения для диагональных элементов ;, а затем найти оптимальное значение F, используя уравнение (21.2.20). Впоследствии ; обновляется с помощью
Мы обновляем F, используя уравнение (21.2.20), а ;, используя уравнение (21.2.26), до достижения сходимости.
Альтернативные схемы обновления матрицы шума ; могут значительно улучшить сходимость. Например, обновление только одного компонента ; при неизмененных остальных может быть достигнуто с помощью выражения закрытой формы[302].
ПРОЕКТ от 9 марта 2010 г. 393 Факторный анализ : максимальное правдоподобие
21.2.2 Максимизация ожиданий
Популярным способом обучения Факторному Анализу в машинном обучении является использование EM. Мы предполагаем, что смещение c было оптимально установлено на среднее значение данных ;v.
M-шаг
Как обычно, нам нужно учитывать энергию, которая, пренебрегая константами, равна
где dn ; vn ; ;v. Оптимальное вариационное распределение q(h|vn ) определяется с помощью приведенного ниже электронного шага. Максимизируя E (F, ;) относительно F, получаем
где
Окончательно
Е- \Электро, Электронный\ шаг
Приведенные выше рекурсии зависят от статистики <h>q(h|vn ) и <hhT> q(h|vn ) . Используя оптимальный выбор EM для электронного \E- шага, мы имеем
при
Используя эти результаты, мы можем выразить статистику в уравнении (21.2.29) в виде
Уравнения (21.2.28,21.2.30,21.2.32) повторяются до сходимости. Как и для любого алгоритма EM, вероятность уравнение (21.1.10) (при диагональном ограничении на ;) увеличивается с каждой итерацией. Конвергенция с использованием этого метода ЕМ может быть медленнее, чем при использовании прямого собственного подхода, описанного в разделе (21.2.1), и по этой причине коммерческие реализации обычно избегают ЕМ. Однако при условии, что используется разумная инициализация, производительность двух алгоритмов обучения может быть одинаковой. Полезной инициализацией является использование PCA, а затем установка F на основные направления.
Сочетание FA
Преимущество вероятностных моделей заключается в том, что они могут быть использованы в качестве компонентов в более сложных моделях, таких как в виде смесей FA[275]. Затем обучение может быть выполнено с использованием подходов, основанных на EM или градиенте. Байесовские расширения, безусловно, представляют интерес; хотя формально они трудноразрешимы, их можно решить с помощью приближенных методов, например [98, 178, 109].
394 ЧЕРНОВИК от 9 марта 2010 г. Вставка: Моделирование лиц
происхождение
Рисунок 21.3: Модель Cкрытой Идентичности. Среднее значение ; соответствует среднему значению лиц\граней. Подпространство F представляет направления изменения различных граней, так что f1 = µ + Fh1 является средним лицом \ гранью\ для индивидуума 1, и аналогично для f2 = µ+Fh2 . Подпространство G обозначает направления изменчивости для любого отдельного лица, вызванные позой, освещением и т.д. Предполагается, что эта изменчивость одинакова для каждого человека. Конкретное среднее значение лица затем определяется средним значением лица человека плюс изменением позы/освещенности, например , ;x12 = f1 + Gw12 . Затем лицо\ грань выборки определяется как среднее лицо\грань ;xij плюс гауссовский шум из N (;ij | 0, ;).
Рисунок 21.4: j-е изображение i-го человека, xij , смоделировано с использованием линейной скрытой модели с параметрами ;.
21.3 Перерыв \вставка , передышка: Моделирование лиц
Факторный анализ широко применяется в статистике и машинном обучении. В качестве инновационного приложения FA, подчеркивающего вероятностный характер модели, мы описываем метод моделирования лица, в основе которого лежит скрытая линейная модель[228]. Рассмотрим галерею изображений лиц X = {xij , i = 1, . . . , I; j = 1, . . . , J} таким образом, чтобы вектор xij представлял j-е изображение i-го человека. В качестве скрытой линейной модели граней мы рассматриваем
Здесь F (dim F = D ; F ) используется для моделирования вариабельности между людьми, а G (dim G = D ; G) моделирует вариативность, связанная с позой, освещением и т.д. в разных изображениях каждого человека. Вклад
объясняет различия между разными людьми, оставаясь неизменным для индивидуального i. Для фиксированного i вклад
объясняет различия в изображениях человека i, объясняя, почему два изображения одного и того же человека выглядят по-разному. Графическое представление приведено на рис. 21.3. В качестве вероятностной линейной модели скрытой переменной мы имеем изображение xij :
Параметры ; = {F, G, µ, ;}. Для сбора изображений, предполагая, что данные i.i.d.,
для которого графическая модель изображена на рис.21.4. В этом случае задача обучения состоит в максимизации вероятности
ЧЕРНОВИК от 9 марта 2010 г. 395 Вставка: Моделирование лиц
(a) Среднее
(c)
(d)
(e)
(b) Дисперсия
(f)
(g)
(h)
Рисунок 21.5: Модель скрытой идентичности изображений лиц. Каждое изображение представлено вектором размером 70 ; 70 ; 3 (цифра 3 соответствует цветовой кодировке RGB). В базе данных I = 195 человек и J = 4 изображения на человека. (a): Среднее значение данных. (b): Стандартное отклонение на пиксель – черный цвет низкий, белый цвет высокий. (c, d, e): три направления из межиндивидуального подпространства F. (f, g, h): Три выборки из модели с фиксированным значением h и произвольным выводом из w в подпространстве G. Воспроизведено из [228].
Эту модель можно рассматривать как ограниченную версию Факторного Анализа с использованием сложенных векторов (здесь только для одного человека, I = 1).
Обобщение на множество индивидуумов с I > 1 является простым — в лоб. Модель можно обучить, используя либо ограниченную форму прямого метода, либо EM, как описано в [228]. Примеры изображений из обученной модели представлены на рис.21.5.
Распознавание
В закрытом режиме распознавания лиц новое "пробное" лицо x; должно быть сопоставлено с человеком n в галерее обучающих лиц. В модели Mn n-е лицо в галерее вынуждено использовать свою скрытую идентификационную переменную hn совместно с тестируемым лицом, что указывает на то, что эти лица принадлежат одному и тому же персоналу2. Предполагается, что на человека приходится один экземпляр (J = 1).,
Затем правило Байеса присваивает апостериорный класс
Для однородного априора член p(Mn ) постоянен, и им можно пренебречь. Требуемые величины, указанные выше, задаются как
2 Это аналогично Байесовскому анализу результатов в разделе (13.5), в котором гипотезы предполагают, что ошибки были вызваны либо той же, либо другой моделью.
396 ПРОЕКТ от 9 марта 2010 г. Вероятностный анализ основных компонентов
Рисунок 21.6: Модель распознавания лиц (представлена только для одного примера на человека, J = 1). (а): В модели M1 предполагается, что тестовое изображение (или "пробник") x; получено от человека 1, хотя и с другой позой/освещением. (b): Для модели M2 предполагается, что тестовое изображение получено от человека 2. Вычисляются значения p (x1 , x2 , x; |M1 ) и (x1 , x2 , x; |M2 ), а затем используется правило Байеса, чтобы определить, какому человеку с наибольшей вероятностью принадлежит тестовое изображение x;.
, где p(x, h, w) получается из уравнения (21.3.6) (где мы предполагаем, что параметры ; являются фиксированными, поскольку они были получены с использованием метода Максимального Правдоподобия). Обратите внимание, что в уравнении (21.3.12) мы не вводим h;, поскольку предполагается, что и xn, и x; происходят от одного и того же человека со скрытой идентичностью hn. Эти предельные вероятности легко вычислить, поскольку они являются предельными значениями Гауссианов.
На практике наилучшие результаты получаются при использовании измерения между отдельными подпространствами F и в пределах- размерность отдельного подпространства G равна 128. Таким образом, эта модель обладает производительностью, не уступающей современным[228]. Преимущество вероятностной модели заключается в том, что распространение этой модели на смеси, по сути, является простым, что еще больше повышает производительность. Связанные модели также могут быть использованы для решения задачи распознавания лиц с "открытым набором", в которой исследуемое лицо может принадлежать или не принадлежать одному из лиц в базе данных[228].
21.4 Вероятностный Анализ Главных\ Принципиальных , Основных\ Компонентов
PPCA соответствует Факторному Анализу при ограничении ;= ;2 ID . Включение этого предположения в уравнение прямого оптимизационного решения (21.2.20) дает
где собственные значения (диагональные элементы ;H ) и соответствующие им собственные векторы (столбцы UH ) являются наибольшими собственными значениями ; -2 S. Поскольку собственные значения ; -2 S - это значения S, просто масштабируемые на ; -2 (и собственные векторы остаются неизменными), мы можем эквивалентно записать
где R - произвольная ортогональная матрица с RT R = I и UH , ;H - собственные векторы и соответствующие- соответствующие собственные значения выборочной ковариации S. Классический PCA, раздел (15.2), восстанавливается в пределе ;2 ; 0. Обратите внимание, что для полного соответствия с PCA необходимо задать R = I, что указывает F вдоль основного направления.
Оптимальное значение ;2
Особое удобство PPCA заключается в том, что оптимальный уровень шума ;2 может быть найден немедленно. Мы упорядочиваем собственные значения S так, чтобы ;1 ; ;2 , ... ; ;D . В уравнении (21.2.19) приведено выражение для логарифмического правдоподобия, в котором собственными значениями являются значения ; -2 S. Таким образом, заменив ;i на ;i /;2, мы можем записать явное выражение для логарифмического правдоподобия в терминах ;2 и собственных значений A,
ЧЕРНОВИК от 9 марта 2010 года 397 Канонический корреляционный анализ и факторный анализ
Рисунок 21.7: Для модели из 5 скрытых единиц измерения здесь представлены результаты обучения PPCA и FA на 100 примерах написанной от руки цифры семь. В верхней строке приведены 5 коэффициентов факторного анализа, а в нижней строке - 5 наибольших собственных векторов из PPCA.
Путем дифференцирования L(;2 ) и приравнивания к нулю оптимальное значение максимального правдоподобия для ;2 равно
Таким образом, PPCA получается путем вычисления основных собственных значений и соответствующих собственных векторов выборки ковариационной матрицы S и определение дисперсии с помощью уравнения (21.4.4). Однократный характер обучения PPCA делает его привлекательным алгоритмом, а также обеспечивает полезную инициализацию для Факторного Анализа.
Пример 92 (Сравнение FA и PPCA). Мы обучили PPCA и FA моделировать написанные от руки цифры числа 7. Из базы данных, содержащей 100 таких изображений, мы подобрали как PPCA, так и FA (100 повторений EM в каждом случае с одинаковой случайной инициализацией), используя 5 скрытых единиц измерения. Полученные факторы для эти модели представлены на рис. 21.7. Чтобы получить представление о том, насколько хорошо каждая из этих моделей отражает данные, мы взяли по 25 образцов из каждой модели, как показано на рис. 21.8, а. По сравнению с PPCA, в FA индивидуальный шум на каждом пикселе наблюдения позволяет получить более четкое представление областей с нулевой выборочной дисперсией.
21.5 Канонический Корреляционный Анализ и Факторный Анализ
Мы расскажем, как CCA, как обсуждалось в разделе (15.8), соотносится с ограниченной формой FA. В качестве краткого напоминания, CCA рассматривает два пробела X и Y, где, например, X может представлять аудиоряд лица говорящего человека и соответствующий видеоряд с изображением лица говорящего человека. Эти два потока данных зависят друг от друга, поскольку мы ожидаем, что участки вокруг рта будут соотнесены с речевым сигналом. Цель CCA состоит в том, чтобы найти представление с низкой размерностью, которое объясняет корреляцию между пространствами X и Y.
Модель, которая обеспечивает эффект, аналогичный эффекту CCA, заключается в использовании скрытого фактора h, который лежит в основе данных как в пространстве X, так и в Y. То есть
где
(a) Факторный анализ
Рисунок 21.8: (а): 25 выборок из обученной модели FA. Обратите внимание, как дисперсия шума зависит от пикселя и равна нулю для пикселей на границе изображения.
(b): 25 выборок из обученной модели PPCA.
398 ЧЕРНОВИК от 9 марта 2010 г. Анализ независимых компонентов
Канонический Корреляционный Анализ. CCA соответствует модели скрытой переменной, в которой общая скрытая переменная генерирует как наблюдаемые переменные x, так и переменные y. Таким образом, это результат ограниченного Факторного Анализа.
Мы можем выразить уравнение (21.5.2) как форму Факторного Анализа, записав
Используя сложенные векторы
и, интегрируя скрытую переменную h, получаем
Из уравнения результатов FA (21.2.5) следует, что оптимальное значение f определяется как
таким образом, оптимально, чтобы f задавалось главным собственным вектором S;;1 . Вводя ;x = ;x2 I, ;Y = ;y2 I
, приведенное выше уравнение может быть выражено в виде связанных уравнений
Исключая b, мы имеем, что для произвольной константы пропорциональности ;,
В пределе ;x2 , ;y2 ; 0 это приводит к уравнению условия нулевой производной (15.8.8), так что CCA фактически можно рассматривать как ограничение формы FA (более полное соответствие приведено в [12]). При рассмотрении CCA таким образом становятся очевидными возможности использования более чем одного скрытого измерения H, см. упражнение(208), в дополнение к преимуществам вероятностной интерпретации.
Как мы уже указывали, CCA соответствует тренировке одной из форм FA путем максимизации совместной вероятности p (x, y|w, u). Альтернативно, обучение, основанное на максимизации условного значения p (y|x, w, u), соответствует частному случаю метода, называемого Частичными Наименьшими Квадратами, см., например, [78]. Это соответствие оставлено в качестве упражнения для заинтересованного читателя.
Распространение FA на варианты ядра не является простым делом, поскольку при замене x на нелинейное отображение ;(x), нормализация выражения exp(;(;(x);wh)2), как правило, неразрешима.
21.6 Независимый Анализ Компонентов
Анализ Независимых Компонентов (ICA) - это линейная декомпозиция данных v, при которой компоненты базовой скрытой векторной переменной h независимы[221, 138]. Другими словами, мы ищем линейную систему координат, в которой координаты независимы. Такие независимые системы координат, возможно, образуют
ПРОЕКТ от 9 марта 2010 г. 399 Анализ независимых компонентов
Рис. 21.9: Латентные данные отбираются из предыдущего p(xi ) ; exp(-5 ;|xi |) с матрицей смешения A, показанной зеленым цветом, для создания наблюдаемых двумерных векторов y = Ax. Красные линии - это матрица смешивания, рассчитанная ica.m на основе наблюдений. Для сравнения, PCA отображает синие (пунктирные) компоненты. Обратите внимание, что компоненты были масштабированы для улучшения визуализации. Как и ожидалось, PCA находит ортогональные направления максимального изменения. ICA, однако, правильно оценивает направления, в которых компоненты были созданы независимо друг от друга. Смотрите демонстрацию demoICA.m.
является естественным представлением данных и может привести к появлению представлений, сильно отличающихся от PCA, см. рис.21.9. С вероятностной точки зрения модель описывается формулой
В ICA принято считать, что наблюдения линейно связаны со скрытыми переменными h. По техническим причинам наиболее удобным практическим решением является использование 3
v = Ah (21.6.2)
где A - квадратная матрица смешения, так что вероятность наблюдения v равна
В этом случае исходные допущения о независимости такие же, как и для PPCA (в пределе нулевого выходного шума). Однако ниже мы выберем неГауссовское значение p(hi ).
Для заданного набора данных V =( v1 , . . . , vN) и предшествующего p(h) наша цель ; найти A. Для исходных данных логарифмическая вероятность удобно записывается в виде B = A-1 ,
отмечаю, что для Гауссовского предшествующего \априора
логарифмическая вероятность становится равной
который инвариантен относительно ортогонального вращения B ; RB, при RT R = I. Это означает, что для Гауссовского априорного p (h) мы не можем однозначно оценить матрицу смешивания. Поэтому, чтобы нарушить эту вращательную инвариантность, нам нужно использовать неГауссовское предварительное значение. Предполагая, что у нас есть неГауссово предварительное значение p (h), используя производную w.r.t. от Bab, мы получаем
где
3Этот подход повторяет метод, представленный в [183].
ЧЕРНОВИК от 9 марта 2010 г. Упражнения
Простое правило обучения подъему по градиенту для B состоит в том, что
Альтернативный алгоритм "естественного градиента" [8, 183], который аппроксимирует обновление по Ньютону, задается путем умножения градиента на BTB справа, чтобы получить обновление
Здесь ; - скорость обучения, указанная в коде ica.m мы номинально установили равным 0,5.
Естественным продолжением является рассмотрение шума на выходных данных, упражнение (212), для которого легко доступен алгоритм EM. Однако в пределе низкого уровня выходного шума ЭМ формально выходит из строя, что связано с общим обсуждением в разделе (11.4).
Популярным альтернативным методом оценки является FastICA4, который может быть связан с итеративной процедурой оптимизации максимального сходства. ICA также может быть реализован в нескольких альтернативных направлениях, включая теория информации[29]. Мы отсылаем читателя к [138] для подробного обсуждения ICA и связанных с ней расширений.
21.7 Код
FA.m: Факторный анализ
demoFA.m: Демонстрация факторного анализа
ica.m: Анализ независимых компонентов
demoIca.m: Демонстрация ICA
21.8 Упражнения
Упражнение 207. Факторный анализ и масштабирование. Предположим, что для x справедлива модель с H-фактором. Теперь рассмотрим преобразование y = Cx, где C - неособая квадратная диагональная матрица. Покажите, что Факторный Анализ не зависит от масштаба, т.е. что модель H-фактора также справедлива для y с факторными нагрузками соответствующими масштабу. Как следует масштабировать конкретные факторы?
Упражнение 208. Для модели Анализа ограниченных Факторов
выведите алгоритм EM Максимального Правдоподобия для матриц A и B, предполагая, что точки данных x1 , . . . , xN равны нулю.
Упражнение 209. Очевидным расширением анализа FA является рассмотрение коррелированного предшествующего
Покажите, что при условии отсутствия ограничений на матрицу загрузки факторов F, использование коррелированной априорной модели p(h) является эквивалентной исходной некоррелированной модели FA.
Упражнение 210. Используя тождество Вудбери и определение ;D в уравнении (21.2.2), покажите, что можно переписать ;D -1 F как
4Смотрите www.cis.hut.fi/projects/ica/fastica/
ЧЕРНОВИК от 9 марта 2010 г. 401 Упражнение
Упражнение 211. Для получения логарифмической функции правдоподобия
Покажем, что L(;2 ) является максимальным для
Упражнение 212. Рассмотрим модель ICA
при
1. Для приведенной выше модели выведите алгоритм EM для набора данных ввода-вывода y1 , . . . , yN и покажите, что требуемыми статистическими данными для M-шага являются <x>p(x|yn , W) и <xxT >p(x|yn , W) .
2. Покажите, что для неГауссова предшествующего p (xi ), последующее
является нефакторизованным, неГауссовым и, как правило, трудноразрешимым (его константа нормализации не может быть эффективно вычислена).
3. Покажите, что в пределе ;2 ; 0 алгоритм EM дает сбой.
402 ЧЕРНОВИК от 9 марта 2010 г. Глава
Глава 22
Модели скрытых способностей
22.1 Модель Раша
Рассмотрим экзамен, на котором студент s отвечает на вопрос q либо правильно (xqs = 1), либо неправильно (xqs = 0). Для набора из N учащихся и Q вопросов успеваемость всех учащихся представлена в виде двоичной матрицы X размером Q ; N. Основываясь только на этих данных, мы хотим оценить способности каждого учащегося. Один из подходов заключается в определении способностей как доли вопросов, на которые учащиеся ответили правильно. Более тонкий анализ состоит в том, чтобы признать, что некоторые вопросы сложнее других, так что студент, ответивший на трудные вопросы должны оцениваться выше, чем у студента, ответившего на такое же количество простых вопросов. Априори мы не знаем, какие вопросы являются трудными, и это должно быть оценено на основе X. Чтобы учесть внутренние различия в сложности вопросов, мы можем смоделировать вероятность того, что студент-ы получит правильный ответ на вопрос q зависит от скрытых способностей учащегося as и скрытой сложности вопроса ;q. Простая обобщающая модель ответа такова
где ; (x) = 1/(1 + e;x). Согласно этой модели, чем выше скрытая способность по сравнению со скрытой сложностью вопроса, тем больше вероятность того, что учащийся ответит на вопрос правильно.
22.1.1 Обучение с Максимальным Правдоподобием
Исходя из предположения, что вероятность данных X в рамках этой модели равна
Логарифмическая вероятность равна
Рисунок 22.1: Модель Раша для анализа вопросов. Каждый элемент двоичной матрицы X, при xqs = 1, если студент s получает правильный вопрос, q генерируется с использованием скрытых способностей учащегося ;s и скрытой сложности вопроса ;q .
403 Конкурентные модели
с производными
Простой способ узнать параметры - использовать градиентный подъем, см. demoRasch.m, с расширениями для методов Ньютона просто в лоб.
Обобщение на более чем два ответа xqs ; {1, 2, . . .} может быть достигнуто с помощью функции в стиле softmax. В более общем плане, модель Раша является примером теории элементарных ответов, предметом которой является анализ анкет [94].
Недостающие данные
Предполагая, что данные отсутствуют случайным образом, недостающие данные могут быть обработаны путем вычисления вероятности наличия только наблюдаемых элементов X. В rasch.m предполагается, что отсутствующие данные кодируются как nan, так что вероятность и градиенты легко вычисляются на основе суммирования только по терминам, содержащим записи, отличные от nan.
Пример 93. На рис. 22.2 показан пример использования модели Раша, в котором оцениваются скрытые способности 20 учащихся на основе набора из 50 вопросов. Исходя из количества вопросов, на которые каждый студент ответил правильно, лучшими студентами являются (ранжируются с первого места) 8, 6, 1, 19, 4, 17, 20, 7, 15, 5, 12, 16, 2, 3, 18, 9, 11, 14, 10, 13. В качестве альтернативы, ранжирование учащихся в соответствии со скрытыми способностями дает 8, 6, 19, 1, 20, 4, 17, 7, 15, 12, 5, 16, 2, 3, 18, 9, 11, 14, 10, 13. Это отличается (лишь незначительно в в данном случае) из рейтинга по количеству правильных ответов, поскольку модель Раша учитывает тот факт, что некоторые учащиеся правильно ответили на сложные вопросы. Например, 20 учащихся правильно ответили на несколько сложных вопросов.
22.1.2 Байесовские модели Раша
Модель Раша потенциально может переопределять данные, особенно при наличии небольшого объема данных. В этом случае естественным расширением является использование Байесовской методики, устанавливающей независимые приоритетные значения для способности и сложности вопроса, чтобы апостериорная способность и сложность вопроса определялись с помощью
Естественными причинами\ априорами\ являются
где ;2 и ;2 - гиперпараметры, которые могут быть получены путем максимизации p(X|;2 , ;2 ). Даже при использовании гауссовых априорных значений апостериорное распределение p(;, ;|X) не имеет стандартной формы, и требуются аппроксимации. Однако в этом случае задняя часть логарифмически вогнута, так что потенциально адекватными являются методы аппроксимации, основанные на вариационных методах или методах Лапласа, или, в качестве альтернативы, можно использовать выборочные аппроксимации.
22.2 Модели Конкуренции \Соревнований
22.2.1 Модель Брэдли-Терри-Люса
Модель Брэдли-Терри-Люса оценивает способности игроков на основе матчей один на один. Здесь мы описываем игры, в которых возможны только выигрышные исходы, оставляя в стороне усложняющую ситуацию возможность ничьих. Для этого
404 ПРОЕКТ от 9 марта 2010 г. Модели соревнований
предполагаемая сложность
студент
вопрос
предполагаемая доля правильных ответов на вопросы
Рисунок 22.2: Модель Раша. (а): Данные о правильных ответах (белый цвет) и неправильных ответах (черный цвет). (b): Предполагаемая скрытая сложность каждого вопроса. (c): Доля вопросов, на которые каждый учащийся ответил правильно. (d): Предполагаемая скрытая способность.
сценарий выигрыша/проигрыша, модель BTL является простой модификацией модели Раша, так что для скрытой способности ;i игрока i и скрытой способности ;j игрока j вероятность того, что i победит j, определяется как
где i|> j означает, что игрок i побеждает игрока j. На основе матрицы игровых данных X с
0, в противном случае
вероятность модели определяется как
, где Mij = ;n xnij - количество раз, когда игрок i обыгрывал игрока j. Затем можно продолжить обучение с использованием метода Максимального Правдоподобия или Байесовского метода, как в модели Раша.
В случае взаимодействия только двух объектов эти модели называются моделями попарного сравнения. Терстоун в 1920-х годах применил такие модели к широкому спектру данных, и модель Брэдли-Терри-Люса фактически является частным случаем его работы[73].
Пример 94. Пример применения модели BTL приведен на рисунке(22.3), на котором приведена матрица X, содержащая количество раз, когда участник i победил конкурента j. Элементы матрицы X были взяты из модели BTL, основанной на "истинных способностях". Используя только X, оценка Максимального Правдоподобия этих скрытых способностей находится в тесном соответствии с истинными способностями.
ПРОЕКТ от 9 марта 2010 г. 405 Модели соревнований
участник
оценочные способности
конкурент
истинные способности
Рисунок 22.3: Модель BTL. (а): Данные X, где Xij - это количество раз, когда конкурент i побеждал конкурента j. (b): Истинная и предполагаемая способность. Несмотря на то, что данные довольно скудны, можно получить разумную оценку скрытых способностей каждого конкурента.
22.2.2 Модель ранжирования Ело\Elo
Система Ело\Elo [89], используемая в шахматном рейтинге, тесно связана с описанной выше моделью BTL, хотя и имеет дополнительное усложнение, связанное с возможностью ничьих. Кроме того, система Elo учитывает меру о вариабельности результатов. Для данной способности ;i фактическая производительность ;i игрока i в игре определяется как
где ;i ; N (;i | 0, ;2) . Дисперсия ;2 фиксирована для всех игроков и, таким образом, учитывает внутреннюю изменчивость результатов. Более формально модель Elo модифицирует модель BTL, чтобы дать
, где p(X|;) задается уравнением (22.2.3) при замене ; на ;.
22.2.3 Гликко и Верное Умение\ Трю Скилл, TrueSkill
Glicko[114] и ТрюСкилл [130] по сути являются Байесовскими версиями модели Ело \Elo с тем уточнением, что скрытая способность моделируется не одним числом, а Гауссовым распределением
Это может отражать тот факт, что игрок может быть стабильно разумным (довольно высокий µi и низкий ;i2 ) или непредсказуемым гением (высокий µi, но с большим ;i2 ). Тогда параметры модели следующие
для набора из S игроков. Модель взаимодействия p(X|;) аналогична модели выигрыша/проигрыша Elo, уравнение (22.2.1). Вероятность для модели с заданными параметрами равна
Этот интеграл формально трудноразрешим, и требуются численные аппроксимации. В этом контексте распространение ожиданий оказалось полезным методом[195].
Система TrueSkill используется, например, для оценки способностей игроков в онлайн-играх, а также с учетом способностей отдельных команд в турнирах. Недавно для переоценки изменения способностей шахматистов со временем было использовано временное расширение[72].
406 ЧЕРНОВИК от 9 марта 2010 года Упражнения
22.3 Код
rasch.m: Демонстрация модели Rasch для обучения
demoRasch.m: Демонстрация модели Rasch
22.4 Упражнения
Упражнение 213 (Брыкающий\ Прыгающий бронко). Сайт bronco.mat содержит информацию о соревнованиях по бегу на лошадях. В соревнованиях принимают участие 500 спортсменов и 20 брыкающихся лошадей. Участник j пытается удержаться на брыкающемся коне i в течение минуты. Если участник побеждает, то значение Xij равно 1, в противном случае - 0. Каждый участник может прокатиться только на трех брыкающихся бронкос (недостающие данные обозначены как nan). Просмотрев все 500 участников-любителей, отчаявшийся Дэн участвует в соревнованиях и подкупает организаторов, чтобы они позволили ему избежать участия в гонках на сложных "бронкос". Основываясь на модели Rasch, назовите 10 самых сложных "бронкос" в порядке убывания сложности.
Упражнение 214 (Тренировка BTL).
1. Покажите, что логарифмическая вероятность для модели Брэдли-Терри-Люса определяется формулой
, где Xij - количество раз, когда игрок i обыгрывает игрока j в серии игр.
2. Вычислите градиент L(;).
3. Вычислите Гессиан модели BTL и убедитесь, что он является отрицательным полуопределенным значением.
Упражнение 215 (Королева).
1. Запрограммируйте простую процедуру подъема по склону, чтобы обучить скрытые способности участников, основываясь на серии победных и проигрышных исходов.
2. В модифицированной форме швейцарской коровьей "борьбы" несколько коров соревнуются, толкая друг друга до тех пор, пока не сдадутся. По окончании конкурса одна корова считается "королевой". На основании данных в BTL.mat (для которого Xij содержит количество раз, когда корова i побеждала корову j), примените модель BTL и получите ранжированный список из десяти лучших бойцовых коров, сначала "королеву".
Упражнение 216. Расширением модели BTL является учет дополнительных "факторов’, описывающих состояние участников, когда они играют. Например, у нас есть набор из S футбольных команд и набор матриц X1 , . . . , XN , где Xijn = 1, если команда i обыграла команду j в матче n. Кроме того, у нас есть для каждого матча и команды вектор бинарных коэффициентов fin ; {0, 1}, который описывает команду. Например, для команды i = 1 ("Мэдчестер Юнайтед"), коэффициент f1,1 = 1, если играет Бозо, и 0, если нет. Предполагается, что способность команды i в игре n измеряется величиной
где fh,i n = 1, если фактор h присутствует в команде i в игре n. di - это скрытая способность команды по умолчанию, которая предполагается, что она постоянна во всех играх. У нас есть такой набор коэффициентов для каждого матча, который дает fh,in.
1. Используя приведенное выше определение скрытой способности в модели BTL, нам интересно найти веса W и способности d, которые наилучшим образом предсказывают способности команды, учитывая, что у нас есть набор исторических игр (Xn , Fn ), n = 1, . . . , N . Запишите вероятность для модели BTL как функцию набора весов всех команд W, d.
ЧЕРНОВИК от 9 марта 2010 г. 407 Упражнения
2. Вычислите градиент логарифмического правдоподобия этой модели.
3. Объясните, как можно использовать эту модель для оценки важности вклада Бозо в развитие "Мэдчестер Юнайтед" .
4. Учитывая изученные W, d и то, что завтра "Мэдчестер Юнайтед" (команда 1) сыграет с "Челски" (команда 2) , объясните, как, учитывая список факторов f для "Челски" (который включает в себя такие вопросы, как, например, кто будет играть в команде), можно выбрать лучшую команду "Мэдчестер Юнайтед" (для участия в турнире), чтобы увеличить вероятность выигрыша в игре.
20-22Байесовские рассуждения смыслы и машинное обу
© Copyright: Джон Темплтон, 2025
Свидетельство о публикации №125110906791
Свидетельство о публикации №125110906791
Рецензии