Ce este algoritmul EM în Machine Learning? [Explicat cu exemple]

Algoritmul EM sau algoritmul de așteptare-maximizare este un model variabil latent care a fost propus de Arthur Dempster, Nan Laird și Donald Rubin în 1977.

Un model de variabilă latentă cuprinde variabile observabile și variabile neobservabile. Variabilele observate sunt cele care pot fi măsurate, în timp ce variabilele neobservate (latente/ascunse) sunt deduse din variabilele observate.

După cum a explicat trio-ul, algoritmul EM poate fi utilizat pentru a determina parametrii de probabilitate maximă locală (MLE) sau parametrii maxim a posteriori (MAP) pentru variabilele latente (variabile neobservabile care trebuie deduse din variabilele observabile) într-un model statistic. Este folosit pentru a prezice aceste valori sau a determina datele care lipsesc sau sunt incomplete, cu condiția să cunoașteți forma generală de distribuție a probabilității asociată cu aceste variabile latente.

Pentru a spune simplu, principiul general din spatele algoritmului EM în învățarea automată implică utilizarea instanțelor observabile de variabile latente pentru a prezice valori în cazurile care nu sunt observabile pentru învățare. Acest lucru se face până când apare convergența valorilor.

Algoritmul este un instrument destul de puternic în învățarea automată și este o combinație de mulți algoritmi nesupravegheați. Aceasta include algoritmul de grupare k-means, printre alte variante de algoritm EM.

Alăturați-vă Cursului de învățare automată online de la cele mai bune universități din lume – Master, Programe Executive Postuniversitare și Program de Certificat Avansat în ML și AI pentru a vă accelera cariera.

Algoritmul de așteptare-maximizare

Să explorăm mecanismul algoritmului Expectation-Maximization în Machine Learning:

Sursă

• Pasul 1: Avem un set de date lipsă sau incomplete și un alt set de parametri de pornire. Presupunem că datele observate sau valorile inițiale ale parametrilor sunt generate dintr-un anumit model.
• Pasul 2: Pe baza valorii observabile în cazurile observabile ale datelor disponibile, vom prezice sau estima valorile în cazurile neobservabile ale datelor sau ale datelor lipsă. Acesta este cunoscut sub numele de pasul de așteptare (E – pas).
• Pasul 3: Folosind datele generate de la pasul E, vom actualiza parametrii și vom completa setul de date. Acesta este cunoscut sub numele de pasul de maximizare (M – step) care este folosit pentru a actualiza ipoteza.

Pașii 2 și 3 se repetă până la convergență. Adică dacă valorile nu sunt convergente, vom repeta pasul E și pasul M.

.

Sursă

Avantajele și dezavantajele algoritmului EM

Aplicații ale algoritmului EM

Modelul variabil latent are o mulțime de aplicații din lumea reală în învățarea automată.

1. Este utilizat în gruparea nesupravegheată a datelor și analiza psihometrice.
2. Este, de asemenea, folosit pentru a calcula densitatea gaussiană a unei funcții.
3. Algoritmul EM găsește o utilizare extinsă în prezicerea parametrilor modelului Markov ascuns (HMM) și a altor modele mixte.
4. Algoritmul EM își găsește o mulțime de utilizare în procesarea limbajului natural (NLP), viziunea computerizată și genetica cantitativă.
5. Alte aplicații importante ale algoritmului EM includ reconstrucția imaginii în domeniul medicinei și al ingineriei structurale.

Să înțelegem algoritmul EM folosind un model de amestec gaussian.

Algoritmul EM pentru modelul de amestec gaussian

Pentru a estima parametrii unui model de amestec gaussian, vom avea nevoie de câteva variabile observate generate de două procese separate ale căror distribuții de probabilitate sunt cunoscute. Cu toate acestea, punctele de date ale celor două procese sunt combinate și nu știm cărei distribuții aparțin.

Ne propunem să estimăm parametrii acestor distribuții folosind estimarea Maximum Likelihood a algoritmului EM, așa cum a fost explicat mai sus.

Iată codul pe care îl vom folosi:

# Având în vedere o funcție pentru care trebuie să calculăm densitatea de

# Gaussian în punctul x_i dat mu, sigma: G(x_i, mu, sigma); și

# o altă funcție pentru a calcula log-probabilitățile: L(x, mu, sigma, pi)

def estimate_gmm(x, K, tol=0,001, max_iter=100):

”' Estimați parametrii GMM.

:param x: lista de variabile cu valori reale observate

:param K: întreg pentru numărul de Gaussian

:param tol: modificare tolerată pentru log-probabilitate

:return: parametrii mu, sigma, pi

”'

# 0. Inițializați theta = (mu, sigma, pi)

N = len(x)

mu, sigma = [rand()] * K, [rand()] * K

pi = [rand()] * K

curr_L = np.inf

pentru j în interval (max_iter):

prev_L = curr_L

# 1. Pasul E: responsabilitate = p(z_i = k | x_i, theta^(t-1))

r = {}

pentru i în intervalul (N):

părți = [pi[k] * G(x_i, mu[k], sigma[k]) pentru i în interval (K)]

total = sumă (părți)

pentru i în k:

r[(i, k)] = părți[k] / total

# 2. M-step: Actualizați valorile mu, sigma, pi

rk = [sum([r[(i, k)] pentru i în interval (N)]) pentru k în interval (K)]

pentru k în intervalul (K):

pi[k] = rk[k] / N

mu[k] = sum(r[(i, k)] * x[i] pentru i în interval (N)) / rk[k]

sigma[k] = suma(r[(i, k)] * (x[i] – mu[k]) ** 2) / rk[k]

# 3. Verificați starea de ieșire

curr_L = L(x, mu, sigma, pi)

dacă abs(prev_L – curr_L) < tol:

pauză

return mu, sigma, pi

În E-Step, putem folosi teorema Bayes pentru a determina valorile așteptate ale punctelor date date care sunt extrase din iterațiile anterioare ale algoritmului. În pasul M, presupunem că valorile variabilelor latente sunt fixe pentru a estima proxy-urile în cazurile neobservate folosind Probabilitatea Maximă. În cele din urmă, folosim formulele de medie standard și de abatere standard pentru a estima parametrii modelului de amestec gaussian.

Concluzie

Asta ne duce la finalul articolului. Pentru mai multe informații despre conceptele de învățare automată, luați legătura cu facultatea de top de la IIIT Bangalore și Universitatea John Moores din Liverpool prin programul de master în învățare automată și AI al upGrad .

Este un curs de 18 luni care oferă peste 450 de ore de conținut de învățare, peste 12 proiecte industriale, 10 opțiuni de proiect Capstone și peste 10 sarcini de codare. De asemenea, vă bucurați de mentorat personalizat din partea experților din industrie și de consiliere de orientare în carieră prin sesiuni live. Următorul lot începe pe 28 februarie 2021!