Che cos'è l'algoritmo EM in Machine Learning? [Spiegato con esempi]

L'algoritmo EM o algoritmo Expectation-Maximization è un modello di variabile latente proposto da Arthur Dempster, Nan Laird e Donald Rubin nel 1977.

Un modello di variabile latente comprende variabili osservabili e variabili non osservabili. Le variabili osservate sono quelle che possono essere misurate mentre le variabili non osservate (latenti/nascoste) sono dedotte dalle variabili osservate.

Come spiegato dal trio, l'algoritmo EM può essere utilizzato per determinare i parametri di massima verosimiglianza locale (MLE) oi parametri massimi a posteriori (MAP) per variabili latenti (variabili non osservabili che devono essere dedotte da variabili osservabili) in un modello statistico. Viene utilizzato per prevedere questi valori o determinare dati mancanti o incompleti, a condizione che si conosca la forma generale della distribuzione di probabilità associata a queste variabili latenti.

In parole povere, il principio generale alla base dell'algoritmo EM nell'apprendimento automatico prevede l'utilizzo di istanze osservabili di variabili latenti per prevedere valori in istanze che non sono osservabili per l'apprendimento. Questo viene fatto fino a quando non si verifica la convergenza dei valori.

L'algoritmo è uno strumento piuttosto potente nell'apprendimento automatico ed è una combinazione di molti algoritmi non supervisionati. Ciò include l'algoritmo di clustering k-mean, tra le altre varianti dell'algoritmo EM.

Partecipa al corso di Machine Learning online dalle migliori università del mondo: master, programmi post-laurea per dirigenti e programma di certificazione avanzato in ML e AI per accelerare la tua carriera.

L'algoritmo di massimizzazione delle aspettative

Esploriamo il meccanismo dell'algoritmo Expectation-Maximization in Machine Learning:

Fonte

• Passaggio 1: abbiamo una serie di dati mancanti o incompleti e un'altra serie di parametri iniziali. Assumiamo che i dati osservati oi valori iniziali dei parametri siano generati da un modello specifico.
• Passaggio 2: sulla base del valore osservabile nelle istanze osservabili dei dati disponibili, prevediamo o stimeremo i valori nelle istanze non osservabili dei dati o nei dati mancanti. Questo è noto come il passaggio Aspettativa (E - passaggio).
• Passaggio 3: utilizzando i dati generati dal passaggio E-, aggiorneremo i parametri e completeremo il set di dati. Questo è noto come il passo di massimizzazione (M - passo) che viene utilizzato per aggiornare l'ipotesi.

I passaggi 2 e 3 vengono ripetuti fino alla convergenza. Ciò significa che se i valori non stanno convergendo, ripeteremo il passaggio E – e il passaggio M –.

.

Fonte

Vantaggi e svantaggi dell'algoritmo EM

Applicazioni dell'algoritmo EM

Il modello di variabile latente ha molte applicazioni nel mondo reale nell'apprendimento automatico.

1. Viene utilizzato nel raggruppamento di dati non supervisionato e nell'analisi psicometrica.
2. Viene anche utilizzato per calcolare la densità gaussiana di una funzione.
3. L'algoritmo EM trova ampio uso nella previsione dei parametri del modello di Markov nascosto (HMM) e di altri modelli misti.
4. L'algoritmo EM trova ampio uso nell'elaborazione del linguaggio naturale (NLP), nella visione artificiale e nella genetica quantitativa.
5. Altre importanti applicazioni dell'algoritmo EM includono la ricostruzione di immagini nel campo della medicina e dell'ingegneria strutturale.

Cerchiamo di capire l'algoritmo EM usando un modello di miscela gaussiana.

Algoritmo EM per il modello di miscela gaussiana

Per stimare i parametri di un modello di miscela gaussiana, avremo bisogno di alcune variabili osservate generate da due processi separati le cui distribuzioni di probabilità sono note. Tuttavia, i punti dati dei due processi sono combinati e non sappiamo a quale distribuzione appartengano.

Miriamo a stimare i parametri di queste distribuzioni utilizzando la stima della massima verosimiglianza dell'algoritmo EM come spiegato sopra.

Ecco il codice che useremo:

# Data una funzione per la quale dobbiamo calcolare la densità di

# Gaussiano al punto x_i dato mu, sigma: G(x_i, mu, sigma); e

# un'altra funzione per calcolare le verosimiglianze logistiche: L(x, mu, sigma, pi)

def stima_gmm(x, K, tol=0.001, max_iter=100):

”' Stima parametri GMM.

:param x: elenco di variabili osservate con valori reali

:param K: intero per numero di gaussiano

:param tol: modifica tollerata per log-verosimiglianza

:ritorno: parametri mu, sigma, pi

”'

# 0. Inizializza theta = (mu, sigma, pi)

N = len(x)

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

pi = [rand()] * K

curr_L = np.inf

per j nell'intervallo (max_iter):

prev_L = curr_L

# 1. E-step: responsabilità = p(z_i = k | x_i, theta^(t-1))

r = {}

per i nell'intervallo (N):

parti = [pi[k] * G(x_i, mu[k], sigma[k]) for i in range(K)]

totale = somma(parti)

per io in k:

r[(i, k)] = parti[k] / totale

# 2. Passo M: aggiorna i valori mu, sigma, pi

rk = [sum([r[(i, k)] for i in range(N)]) for k in range(K)]

per k nell'intervallo (K):

pi[k] = rk[k] / N

mu[k] = sum(r[(i, k)] * x[i] for i in range(N)) / rk[k]

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

# 3. Verificare la condizione di uscita

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

if abs(prev_L – curr_L) < tol:

rottura

restituisce mu, sigma, pi

Nell'E-Step, possiamo usare il teorema di Bayes per determinare i valori attesi dei punti dati dati che vengono estratti dalle passate iterazioni dell'algoritmo. Nell'M-Step, assumiamo che i valori delle variabili latenti siano fissi per stimare i proxy nelle istanze non osservate utilizzando la massima verosimiglianza. Infine, utilizziamo le formule della media standard e della deviazione standard per stimare i parametri del modello della miscela gaussiana.

Conclusione

Questo ci porta alla fine dell'articolo. Per ulteriori informazioni sui concetti di Machine Learning, contatta i migliori docenti di IIIT Bangalore e Liverpool John Moores University attraverso il programma di Master of Science in Machine Learning e AI di upGrad .

È un corso di 18 mesi che offre oltre 450 ore di contenuti didattici, oltre 12 progetti di settore, 10 opzioni di progetto Capstone e oltre 10 incarichi di codifica. Puoi anche usufruire di tutoraggio personalizzato da parte di esperti del settore e consulenza di orientamento professionale attraverso sessioni dal vivo. Il prossimo lotto inizia il 28 febbraio 2021!