Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних[en] АвтоМН Асоціативні правила Семантичний аналіз[en] Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик[en] Навчання онтологій[en] Мультимодальне навчання[en]
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання[en] AdaBoost[en] Дерева рішень MARS[en] CART Доречно-векторна машина k-сусідів Лінійна регресія Логістична регресія Лінійний розділювальний аналіз Наївний баєсів класифікатор Перцептрон Підмайстрове навчання Опорно-векторна машина Штучні нейронні мережі
Кластерування BIRCH[en] CURE Ієрархічне k-середніх Нечітке Очікування-максимізація DBSCAN OPTICS Спектральне Зсув середнього[en]
Знижування розмірності Факторний аналіз Метод незалежних компонент[en] Канонічна кореляція Дискримінантний аналіз Метод головних компонент Власний узагальнений розклад[en] Розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості Навчання розріджених словників[en]
Структурове передбачування Графові моделі Баєсова мережа Прихована марковська модель Умовне випадкове поле
Виявляння аномалій RANSAC k-НС Коефіцієнт локального відхилення Відстань Кука Ізоляційний ліс[en]
Штучна нейронна мережа Автокодувальник Когнітивні обчислення[en] Глибоке навчання DeepDream Нейронна мережа прямого поширення Рекурентна нейронна мережа ДКЧП ВРВ МВС Резервуарне обчислення Обмежена машина Больцмана ГЗМ Дифузійна модель Самоорганізаційна карта Згорткова нейронна мережа U-Net Трансформер Зоровий Спайкова нейронна мережа[en] Мемтранзистор Електрохімічна ПДД[en] (ECRAM)
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць Багатоагентне навчання з підкріпленням Гра проти себе[en]
Навчання з людьми Активне навчання (машинне навчання)[en] Краудсорсинг Людина-в-циклі
Діагностування моделей Крива спроможності навчатися[en]
Математичні засади Ядрові машини Компроміс зсуву та дисперсії Ймовірнісно приблизно коректне навчання Мінімізація емпіричного ризику Оккамове навчання[en] Регуляризація LASSO[en] Тихонова Еластично-сіткова[en] Статистичне навчання Теорія Вапника — Червоненкіса Теорія обчислювального навчання[en]
Місця машинного навчання ECML PKDD[en] NeurIPS[en] ICML[en] ICLR IJCAI ML JMLR
Пов'язані статті Глосарій штучного інтелекту[en] Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання[en]
п о р

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 {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 \Theta }$.

Іншими словами, ${\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 )}$

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