forventningsmaksimering

1. 1

   Algoritmen består af to trin: (E) forventningstrin, hvor den forventede log-sandsynlighed for den komplette datasæt beregnes givet nuværende parameterestimater; (M) maksimeringstrin, hvor parametrene opdateres ved at maksimere denne forventede log-sandsynlighed.

   • EM-algoritmen anvendes til at estimere parametrene i en Gaussian Mixture Model.
   • Forventningsmaksimering konvergerer monotont mod et lokalt maksimum af likelihoodfunktionen.

EM anvendes i mange maskinlæringsopgaver, herunder klyngedannelse (Gaussian Mixture Models), skjulte Markov-modeller og behandling af manglende data. Det er særligt nyttigt, når sandsynlighedsfunktionen er kompleks, men den komplette datasandsynlighed (inkl. latente variable) er lettere at optimere.

Forventningstrin: Q(θ|θ^t) = E_{Z|X,θ^t}[log p(X,Z|θ)]
Maksimeringstrin: θ^{t+1} = argmax_θ Q(θ|θ^t)

import numpy as np
def gmm_em(data, k, max_iter=100):
    # Initialize
    means = np.random.randn(k)
    vars_ = np.ones(k)
    weights = np.ones(k)/k
    for _ in range(max_iter):
        # E-step
        pdf = np.array([w * np.exp(-(data-m)**2/(2*v))/np.sqrt(2*np.pi*v) for m,v,w in zip(means,vars_,weights)])
        resp = pdf / pdf.sum(axis=0)
        # M-step
        Nk = resp.sum(axis=1)
        means = (resp @ data) / Nk
        vars_ = (resp @ (data - means[:,None])**2) / Nk
        weights = Nk / len(data)
    return means, vars_, weights

Simpel EM-implementering for en 1D Gaussian Mixture Model.

Begrebet blev introduceret af Dempster, Laird og Rubin i 1977. 'Forventning' henviser til beregning af den forventede log-sandsynlighed over de latente variable, og 'maksimering' til optimering af parametrene.

• Dempster, A.P., Laird, N.M., Rubin, D.B. (1977). 'Maximum Likelihood from Incomplete Data via the EM Algorithm'