Qu'est-ce qu'une explication intuitive de la technique de maximisation de l'attente?

Question

Maximisation de l'attente s'il s'agit d'une sorte de méthode probabiliste pour classer les données. S'il vous plaît, corrigez-moi si je me trompe s'il ne s'agit pas d'un classificateur.

Qu'est-ce qu'une explication intuitive de cette technique EM? Qu'attend-on ici et qu'est-ce qui est minimisé?

Answer 1

EM est un algorithme de maximisation d'une fonction de vraisemblance lorsque certaines variables du modèle sont pas observées (c'est à dire quand vous avez des variables latentes).

Vous pourriez à juste titre se demander, si nous essayons simplement de maximiser une fonction, pourquoi ne pas simplement utiliser les mécanismes existants pour la maximisation d'une fonction. Eh bien, si vous essayez d'optimiser en prenant des produits dérivés et leur mise à zéro, vous trouvez que dans de nombreux cas, les conditions de premier ordre n'ont pas une solution. Il y a un dilemme de la poule et de l'oeuf problème à résoudre pour votre modèle de paramètres que vous avez besoin de connaître la répartition de vos données non observées; mais la distribution de vos regards de données est fonction de vos paramètres de modèle.

E-M tente de contourner ce problème par itérative deviner une distribution pour la regards des données, puis d'estimer les paramètres du modèle par la maximisation de quelque chose qui est une borne inférieure sur la réelle fonction de vraisemblance, et répéter jusqu'à ce que la convergence:

L'algorithme EM

Commencez à deviner pour les valeurs des paramètres du modèle

E-étape: Pour chaque point de données qui a des valeurs manquantes, utilisez votre modèle d'équation à résoudre pour la distribution des données manquantes donné votre estimation de paramètres du modèle et compte tenu des données observées (notez que vous êtes à la recherche d'une distribution pour chaque valeur manquante, non pas pour la valeur attendue). Maintenant que nous avons une distribution pour chaque valeur manquante, on peut calculer l' espérance de la fonction de vraisemblance à l'égard des variables non observées. Si notre supposition pour le paramètre du modèle est correct, cette probabilité sera la probabilité de nos données observées; si les paramètres n'étaient pas correctes, il va juste être une limite inférieure.

M-étape: Maintenant que nous avons une probabilité de fonction à n variables non observées en elle, à maximiser la fonction comme vous le feriez dans le cas constaté, pour obtenir une nouvelle estimation des paramètres du modèle.

Répétez jusqu'à ce que la convergence.

Answer 2

Ici est une simple recette de comprendre les Attentes de la Maximisation de l'algorithme:

1- Lire ce EM tutoriel papier en Faire et Batzoglou.

2- Vous pouvez avoir des points d'interrogation dans votre tête, regardez les explications sur ce mathématiques de la pile d'échange la page.

3- Regardez ce code que j'ai écrit en Python qui explique l'exemple de l'EM tutoriel papier de l'article 1:

Avertissement : Le code peut être salissant/sous-optimale, puisque je ne suis pas un développeur Python. Mais il fait le travail.

import numpy as np
import math

#### E-M Coin Toss Example as given in the EM tutorial paper by Do and Batzoglou* #### 

def get_mn_log_likelihood(obs,probs):
    """ Return the (log)likelihood of obs, given the probs"""
    # Multinomial Distribution Log PMF
    # ln (pdf)      =             multinomial coeff            *   product of probabilities
    # ln[f(x|n, p)] = [ln(n!) - (ln(x1!)+ln(x2!)+...+ln(xk!))] + [x1*ln(p1)+x2*ln(p2)+...+xk*ln(pk)]     

    multinomial_coeff_denom= 0
    prod_probs = 0
    for x in range(0,len(obs)): # loop through state counts in each observation
        multinomial_coeff_denom = multinomial_coeff_denom + math.log(math.factorial(obs[x]))
        prod_probs = prod_probs + obs[x]*math.log(probs[x])

multinomial_coeff = math.log(math.factorial(sum(obs))) -  multinomial_coeff_denom
likelihood = multinomial_coeff + prod_probs
return likelihood

# 1st:  Coin B, {HTTTHHTHTH}, 5H,5T
# 2nd:  Coin A, {HHHHTHHHHH}, 9H,1T
# 3rd:  Coin A, {HTHHHHHTHH}, 8H,2T
# 4th:  Coin B, {HTHTTTHHTT}, 4H,6T
# 5th:  Coin A, {THHHTHHHTH}, 7H,3T
# so, from MLE: pA(heads) = 0.80 and pB(heads)=0.45

# represent the experiments
head_counts = np.array([5,9,8,4,7])
tail_counts = 10-head_counts
experiments = zip(head_counts,tail_counts)

# initialise the pA(heads) and pB(heads)
pA_heads = np.zeros(100); pA_heads[0] = 0.60
pB_heads = np.zeros(100); pB_heads[0] = 0.50

# E-M begins!
delta = 0.001  
j = 0 # iteration counter
improvement = float('inf')
while (improvement>delta):
    expectation_A = np.zeros((5,2), dtype=float) 
    expectation_B = np.zeros((5,2), dtype=float)
    for i in range(0,len(experiments)):
        e = experiments[i] # i'th experiment
        ll_A = get_mn_log_likelihood(e,np.array([pA_heads[j],1-pA_heads[j]])) # loglikelihood of e given coin A
        ll_B = get_mn_log_likelihood(e,np.array([pB_heads[j],1-pB_heads[j]])) # loglikelihood of e given coin B

        weightA = math.exp(ll_A) / ( math.exp(ll_A) + math.exp(ll_B) ) # corresponding weight of A proportional to likelihood of A 
        weightB = math.exp(ll_B) / ( math.exp(ll_A) + math.exp(ll_B) ) # corresponding weight of B proportional to likelihood of B                            

        expectation_A[i] = np.dot(weightA, e) 
        expectation_B[i] = np.dot(weightB, e)

    pA_heads[j+1] = sum(expectation_A)[0] / sum(sum(expectation_A)); 
    pB_heads[j+1] = sum(expectation_B)[0] / sum(sum(expectation_B)); 

    improvement = max( abs(np.array([pA_heads[j+1],pB_heads[j+1]]) - np.array([pA_heads[j],pB_heads[j]]) ))
    j = j+1

Answer 3

Techniquement, le terme "EM" est un peu underspecified, mais je suppose que vous vous référez à la Gaussienne Mélange de Modélisation cluster de l'analyse technique, qui est une instance générale de l'EM principe.

En fait, EM analyse de cluster n'est pas un classificateur. Je sais que certaines personnes considèrent que le clustering pour être "classification non supervisée", mais en réalité, analyse de cluster est quelque chose de tout à fait différent.

La différence essentielle, et le grand malentendu classification gens ont toujours avec le cluster de l'analyse est que: dans le groupe analaysis, il n'y a pas de "bonne solution". C'est une connaissance de la découverte de la méthode, il est en fait destiné à trouver quelque chose de nouveau! Cela rend l'évaluation très difficile. Il est souvent évaluée en utilisant une classification de référence, mais qui n'est pas toujours le cas: la classification que vous avez peut ou peut ne pas refléter ce qui est dans les données.

Laissez-moi vous donner un exemple: vous avez un grand ensemble de données de clients, y compris les données sur le sexe. Une méthode qui divise l'ensemble de ces données dans "masculin" et "féminin" est optimale lorsque vous la comparez avec les classes existantes. Dans une "prédiction" façon de penser ce qui est bon, comme pour les nouveaux utilisateurs, vous pouvez maintenant prédire leur sexe. Dans une "découverte de connaissances" façon de penser c'est en fait mauvais, parce que vous avez envie de découvrir quelques nouvelles de la structure dans les données. Une méthode qui serait par exemple fractionner les données sur les personnes âgées et les enfants toutefois, score que le pire qu'il peut obtenir à l'égard des hommes/femmes de la classe. Cependant, que serait un excellent résultat de clustering (si l'âge n'a pas été donné).

Maintenant de retour à l'EM. Essentiellement, il suppose que vos données est composé de multiples normale multivariée des distributions (note que c'est un très hypothèse forte, en particulier lorsque vous corrigez le nombre de clusters!). Il essaie alors de trouver un local modèle optimal pour cette par alternance en améliorer le modèle et l'objet de l'affectation au modèle.

Pour de meilleurs résultats dans la classification contexte, choisir le nombre de clusters plus grand que le nombre de classes, ou même appliquer le regroupement de simples classes seulement (pour savoir si il y a une certaine structure au sein de la classe!).

Dites que vous voulez former un classificateur à dire à part "voitures", "vélo" et "trucks". Il est peu utile en supposant que les données composé d'exactement 3 les distributions normales. Cependant, on peut supposer qu' il n'y a plus d'un type de voitures (et de camions et de motos). Ainsi, au lieu de la formation d'un classificateur pour ces trois catégories, vous cluster de voitures, de camions et de motos dans les 10 clusters (ou peut-être 10 voitures, 3 camions et 3 vélos, peu importe), puis train à un classificateur à dire en dehors de ces 30 classes, puis de fusionner la classe de résultat dans les classes d'origine. Vous pouvez également découvrir qu'il y est un cluster qui est particulièrement difficile à classer, par exemple Trikes. Ils sont un peu les voitures, et un peu de vélos. Ou les camions de livraison, qui sont plus comme surdimensionné voitures que les camions.

Answer 4

EM est utilisé pour maximiser la probabilité d'un modèle de Q avec variables latentes Z.

C'est un processus itératif d'optimisation.

theta <- initial guess for hidden parameters
while not converged:
    #e-step
    Q(theta'|theta) = E[log L(theta|Z)]
    #m-step
    theta <- argmax_theta' Q(theta'|theta)

e-étape: au vu de l'estimation de Z de calculer le loglikelihood fonction

m-étape: trouver thêta qui maximise ce Q

GMM Exemple:

e-étape: estimation de l'étiquette des affectations pour chaque point de données compte tenu de l'actuelle gmm-estimation des paramètres

m-étape: optimiser une nouvelle thêta compte tenu de la nouvelle étiquette assignations de

K-means est également un algorithme EM et il y a beaucoup d'explication des animations sur les K-means.