Qu'est-ce que l'algorithme EM dans l'apprentissage automatique ? [Expliqué avec des exemples]

L'algorithme EM ou algorithme d'attente-maximisation est un modèle de variable latente qui a été proposé par Arthur Dempster, Nan Laird et Donald Rubin en 1977.

Un modèle de variables latentes comprend des variables observables et des variables non observables. Les variables observées sont celles qui peuvent être mesurées tandis que les variables non observées (latentes/cachées) sont déduites des variables observées.

Comme expliqué par le trio, l'algorithme EM peut être utilisé pour déterminer les paramètres locaux du maximum de vraisemblance (MLE) ou les paramètres maximaux a posteriori (MAP) pour les variables latentes (variables non observables qui doivent être déduites des variables observables) dans un modèle statistique. Il est utilisé pour prédire ces valeurs ou déterminer des données manquantes ou incomplètes, à condition que vous connaissiez la forme générale de la distribution de probabilité associée à ces variables latentes.

Pour le dire simplement, le principe général de l'algorithme EM dans l'apprentissage automatique consiste à utiliser des instances observables de variables latentes pour prédire des valeurs dans des instances non observables pour l'apprentissage. Ceci est fait jusqu'à ce que la convergence des valeurs se produise.

L'algorithme est un outil assez puissant dans l'apprentissage automatique et est une combinaison de nombreux algorithmes non supervisés. Cela inclut l'algorithme de clustering k-means, parmi d'autres variantes de l'algorithme EM.

Rejoignez le cours d'apprentissage automatique en ligne des meilleures universités du monde - Masters, programmes de troisième cycle pour cadres et programme de certificat avancé en ML et IA pour accélérer votre carrière.

L'algorithme d'espérance-maximisation

Explorons le mécanisme de l'algorithme Expectation-Maximization en Machine Learning :

La source

• Étape 1 : Nous avons un ensemble de données manquantes ou incomplètes et un autre ensemble de paramètres de départ. Nous supposons que les données observées ou les valeurs initiales des paramètres sont générées à partir d'un modèle spécifique.
• Étape 2 : Sur la base de la valeur observable dans les instances observables des données disponibles, nous allons prédire ou estimer les valeurs dans les instances non observables des données ou des données manquantes. C'est ce qu'on appelle l'étape d'attente (étape E).
• Étape 3 : À l'aide des données générées à partir de l'étape E, nous mettrons à jour les paramètres et compléterons l'ensemble de données. C'est ce qu'on appelle l'étape de maximisation (M - étape) qui est utilisée pour mettre à jour l'hypothèse.

Les étapes 2 et 3 sont répétées jusqu'à convergence. Cela signifie que si les valeurs ne convergent pas, nous répéterons l'étape E et l'étape M.

.

La source

Avantages et inconvénients de l'algorithme EM

Applications de l'algorithme EM

Le modèle de variable latente a de nombreuses applications réelles dans l'apprentissage automatique.

1. Il est utilisé dans le regroupement de données non supervisé et l'analyse psychométrique.
2. Il est également utilisé pour calculer la densité gaussienne d'une fonction.
3. L'algorithme EM est largement utilisé pour prédire les paramètres du modèle de Markov caché (HMM) et d'autres modèles mixtes.
4. L'algorithme EM est largement utilisé dans le traitement du langage naturel (PNL), la vision par ordinateur et la génétique quantitative.
5. D'autres applications importantes de l'algorithme EM incluent la reconstruction d'images dans le domaine de la médecine et de l'ingénierie structurelle.

Comprenons l'algorithme EM en utilisant un modèle de mélange gaussien.

Algorithme EM pour le modèle de mélange gaussien

Pour estimer les paramètres d'un modèle de mélange gaussien, nous aurons besoin de certaines variables observées générées par deux processus distincts dont les distributions de probabilité sont connues. Cependant, les points de données des deux processus sont combinés et nous ne savons pas à quelle distribution ils appartiennent.

Nous visons à estimer les paramètres de ces distributions en utilisant l'estimation du maximum de vraisemblance de l'algorithme EM comme expliqué ci-dessus.

Voici le code que nous utiliserons :

# Soit une fonction pour laquelle nous devons calculer la densité de

# Gaussien au point x_i étant donné mu, sigma : G(x_i, mu, sigma); et

# une autre fonction pour calculer les log-vraisemblances : L(x, mu, sigma, pi)

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

”' Estimer les paramètres GMM.

:param x : liste des variables réelles observées

:param K : entier pour nombre de gaussiennes

:param tol : modification tolérée pour la log-vraisemblance

:retour : paramètres mu, sigma, pi

”'

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

N = len(x)

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

pi = [rand()] * K

curr_L = np.inf

pour j dans la plage (max_iter):

prev_L = curr_L

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

r = {}

pour i dans la plage (N):

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

total = somme (parties)

pour i dans k :

r[(i, k)] = parties[k] / total

# 2. M-step : Mettre à jour les valeurs mu, sigma, pi

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

pour k dans la plage(K):

pi[k] = rk[k] / N

mu[k] = somme(r[(i, k)] * x[i] pour i dans la plage(N)) / rk[k]

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

# 3. Vérifiez les conditions de sortie

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

si abs(prev_L – curr_L) < tol :

Pause

retour mu, sigma, pi

Dans l'étape E, nous pouvons utiliser le théorème de Bayes pour déterminer les valeurs attendues des points de données donnés tirés des itérations passées de l'algorithme. Dans l'étape M, nous supposons que les valeurs des variables latentes sont fixées pour estimer les proxys dans les instances non observées à l'aide du maximum de vraisemblance. Enfin, nous utilisons les formules de moyenne standard et d'écart-type pour estimer les paramètres du modèle de mélange gaussien.

Conclusion

Cela nous amène à la fin de l'article. Pour plus d'informations sur les concepts d'apprentissage automatique, contactez les meilleurs professeurs de l'IIIT Bangalore et de l'Université John Moores de Liverpool via le programme de maîtrise ès sciences en apprentissage automatique et IA d' upGrad .

Il s'agit d'un cours de 18 mois qui offre plus de 450 heures de contenu d'apprentissage, plus de 12 projets industriels, 10 options de projet Capstone et plus de 10 missions de codage. Vous bénéficiez également d'un mentorat personnalisé d'experts de l'industrie et de conseils d'orientation professionnelle par le biais de sessions en direct. Le prochain lot commence le 28 février 2021 !