WikiSort.ru - Программирование

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

EM-алгоритм (англ. Expectation-maximization (EM) algorithm) — алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.

Часто EM-алгоритм используют для разделения смеси гауссиан.

Описание алгоритма

Пусть ${\displaystyle {\textbf {X}}}$  — некоторые из значений наблюдаемых переменных, а ${\displaystyle {\textbf {T}}}$  — скрытые переменные. Вместе ${\displaystyle {\textbf {X}}}$ и ${\displaystyle {\textbf {T}}}$ образуют полный набор данных. Вообще, ${\displaystyle {\textbf {T}}}$ может быть некоторой подсказкой, которая облегчает решение проблемы в случае, если она известна. Например, если имеется смесь распределений, функция правдоподобия легко выражается через параметры отдельных распределений смеси.

Положим ${\displaystyle p}$  — плотность вероятности (в непрерывном случае) или функция вероятности (в дискретном случае) полного набора данных с параметрами ${\displaystyle \Theta }$ : ${\displaystyle p(\mathbf {X} ,\mathbf {T} |\Theta ).}$ Эту функцию можно понимать как правдоподобие всей модели, если рассматривать её как функцию параметров ${\displaystyle \Theta }$ . Заметим, что условное распределение скрытой компоненты при некотором наблюдении и фиксированном наборе параметров может быть выражено так:

${\displaystyle p(\mathbf {T} |\mathbf {X} ,\Theta )={\frac {p(\mathbf {X} |\mathbf {T} ,\Theta )p(\mathbf {T} |\Theta )}{p(\mathbf {X} |\Theta )}}={\frac {p(\mathbf {X} |\mathbf {T} ,\Theta )p(\mathbf {T} |\Theta )}{\int p(\mathbf {X} |\mathbf {\hat {T}} ,\Theta )p(\mathbf {\hat {T}} |\Theta )d\mathbf {\hat {T}} }}}$ ,

используя расширенную формулу Байеса и формулу полной вероятности. Таким образом, нам необходимо знать только распределение наблюдаемой компоненты при фиксированной скрытой ${\displaystyle p(\mathbf {X} |\mathbf {T} ,\Theta )}$ и вероятности скрытых данных ${\displaystyle p(\mathbf {T} |\Theta )}$ .

EM-алгоритм итеративно улучшает начальную оценку ${\displaystyle \Theta _{0}}$ , вычисляя новые значения оценок ${\displaystyle \Theta _{1},\Theta _{2},}$ и так далее. На каждом шаге переход к ${\displaystyle \Theta _{n+1}}$ от ${\displaystyle \Theta _{n}}$ выполняется следующим образом:

${\displaystyle \Theta _{n+1}=\arg \max _{\Theta }Q(\Theta )}$

где ${\displaystyle Q(\Theta )}$  — матожидание логарифма правдоподобия. Другими словами, мы не можем сразу вычислить точное правдоподобие, но по известным данным (${\displaystyle X}$ ) мы можем найти апостериорную оценку вероятностей для различных значений скрытых переменных ${\displaystyle T}$ . Для каждого набора значений ${\displaystyle T}$ и параметров ${\displaystyle \Theta }$ мы можем вычислить матожидание функции правдоподобия по данному набору ${\displaystyle X}$ . Оно зависит от предыдущего значения ${\displaystyle \Theta }$ , потому что это значение влияет на вероятности скрытых переменных ${\displaystyle T}$ .

${\displaystyle Q(\Theta )}$ вычисляется следующим образом:

${\displaystyle Q(\Theta )=E_{\mathbf {T} }\!\!\left[\log p\left(\mathbf {X} ,\mathbf {T} \,|\,\Theta \right){\Big |}\mathbf {X} \right]}$

то есть это условное матожидание ${\displaystyle \log p\left(\mathbf {X} ,\mathbf {T} \,|\,\Theta \right)}$ при условии ${\displaystyle \mathbf {X} }$ .

Другими словами, ${\displaystyle \Theta _{n+1}}$  — это значение, максимизирующее (M) условное матожидание (E) логарифма правдоподобия при данных значениях наблюдаемых переменных и предыдущем значении параметров. В непрерывном случае значение ${\displaystyle Q(\Theta )}$ вычисляется так:

${\displaystyle Q(\Theta )=E_{\mathbf {T} }\!\!\left[\log p\left(\mathbf {X} ,\mathbf {T} \,|\,\Theta \right){\Big |}\mathbf {X} \right]=\int _{-\infty }^{\infty }p\left(\mathbf {T} \,|\,\mathbf {X} ,\Theta _{n}\right)\log p\left(\mathbf {X} ,\mathbf {T} \,|\,\Theta \right)d\mathbf {T} }$

Альтернативное описание

При определенных обстоятельствах удобно рассматривать EM-алгоритм как два чередующихся шага максимизации.^[1][2] Рассмотрим функцию:

${\displaystyle F(q,\theta )=\operatorname {E} _{q}[\log L(\theta ;x,Z)]+H(q)=-D_{\text{KL}}{\big (}q{\big \|}p_{Z|X}(\cdot |x;\theta ){\big )}+\log L(\theta ;x)}$

где q — распределение вероятностей ненаблюдаемых переменных Z; p_Z|X(· |x;θ) — условное распределение ненаблюдаемых переменных при фиксированных наблюдаемых x и параметрах θ; H — энтропия и D_KL — расстояние Кульбака-Лейблера.

Тогда шаги EM-алгоритма можно представить как:

E(xpectation) шаг: Выбираем q, чтобы максимизировать F:

${\displaystyle q^{(t)}=\operatorname {*} {\arg \,\max }_{q}\ F(q,\theta ^{(t)})}$

M(aximization) шаг: Выбираем θ, чтобы максимизировать F:

${\displaystyle \theta ^{(t+1)}=\operatorname {*} {\arg \,\max }_{\theta }\ F(q^{(t)},\theta )}$

Примеры использования

• k-means — алгоритм кластеризации, построенный на идее EM-алгоритма
• Метод упругих карт для нелинейного сокращения размерности данных
• Алгоритм Баума-Велша — алгоритм для оценки параметров скрытых марковских моделей

Примечания

Ссылки

• Демонстрация разделения смеси гауссиан с помощью EM-алгоритма
• Реализация на Java