EM algoritme

EM-algoritme ( eng. Expectation-maximization (EM) algorithm ) er en algoritme, der bruges i matematisk statistik til at finde maksimale sandsynlighedsestimater for parametrene for probabilistiske modeller, i det tilfælde, hvor modellen afhænger af nogle skjulte variable . Hver iteration af algoritmen består af to trin. I E-trinnet (forventning) beregnes den forventede værdi af likelihood-funktionen , mens de latente variable behandles som observerbare . I M-trinnet (maksimering) beregnes det maksimale sandsynlighedsestimat, hvilket øger den forventede sandsynlighed beregnet i E-trinnet. Denne værdi bruges derefter til E-trinnet i den næste iteration. Algoritmen udføres indtil konvergens.

Ofte bruges EM-algoritmen til at adskille en blanding af gaussere .

Beskrivelse af algoritmen

Lad være nogle af værdierne af de observerede variabler, og vær skjulte variabler. Tilsammen danner de et komplet datasæt. Generelt kan der være nogle tip, der gør det nemmere at løse problemet, hvis det er kendt. For eksempel, hvis der er en blanding af fordelinger , er sandsynlighedsfunktionen let udtrykt i form af parametrene for de individuelle fordelinger af blandingen. ${\textbf {X}}$ ${\textbf {T}}$ ${\textbf {X}}$ ${\textbf {T}}$ ${\textbf {T}}$

Lad os antage , at det er sandsynlighedstætheden (i det kontinuerlige tilfælde) eller sandsynlighedsfunktionen (i det diskrete tilfælde) af et komplet datasæt med parametre : Denne funktion kan forstås som sandsynligheden for hele modellen, hvis vi betragter den som en funktion af parametrene . Bemærk, at den betingede fordeling af den skjulte komponent under nogle observationer og et fast sæt af parametre kan udtrykkes som følger: $s$ $\Theta$ $p({\mathbf X},{\mathbf T}|\Theta ).$ $\Theta$

p(\mathbf {T} |\mathbf {X} ,\Theta )={\frac {p(\mathbf {X} |\mathbf {T} ,\Theta )p(\mathbf {T} | \Theta )}{p(\mathbf {X} |\Theta )}}={\frac {p(\mathbf {X} |\mathbf {T} ,\Theta )p(\mathbf {T} |\Theta )}{\int p(\mathbf {X} |\mathbf {\hat {T)) ,\Theta )p(\mathbf {\hat {T)) |\Theta )d\mathbf {\hat {T} } }}

ved at bruge den udvidede Bayes- formel og den samlede sandsynlighedsformel . Således behøver vi kun at kende fordelingen af den observerede komponent for en fast latent og sandsynligheden for de latente data . $p({\mathbf X}|{\mathbf T},\Theta )$ $p({\mathbf T}|\Theta )$

EM-algoritmen forbedrer iterativt den indledende score ved at beregne nye scoreværdier og så videre. Ved hvert trin udføres overgangen til fra som følger: $\Theta _{0}$ $\Theta _{1},\Theta _{2},$ $\Theta _{{n+1}}$ $\Theta_n$

\Theta _{{n+1}}=\arg \max _{{\Theta }}Q(\Theta)

hvor er den forventede logaritme for sandsynligheden. Med andre ord kan vi ikke umiddelbart beregne den nøjagtige sandsynlighed, men ud fra de kendte data ( ) kan vi finde et efterfølgende estimat af sandsynligheden for forskellige værdier af de latente variable . For hvert sæt værdier og parametre kan vi beregne forventningen til sandsynlighedsfunktionen for dette sæt . Det afhænger af den tidligere værdi, fordi denne værdi påvirker sandsynligheden for de latente variabler . $Q(\Theta )$ $x$ $T$ $T$ $\Theta$ $x$ $\Theta$ $T$

$Q(\Theta )$ beregnes som følger:

Q(\Theta )=E_{{{\mathbf T))}\!\!\left[\log p\left({\mathbf X},{\mathbf T}\,|\,\Theta \right) {\Big |}{\mathbf X}\right]

det vil sige, at dette er en betinget forventning under betingelsen . $\log p\venstre({\mathbf X},{\mathbf T}\,|\,\Theta \right)$ $\mathbf {X}$

Med andre ord er den værdi, der maksimerer (M) den betingede middelværdi (E) af log-sandsynligheden for de givne værdier af de observerede variable og den tidligere værdi af parametrene. I det kontinuerlige tilfælde beregnes værdien således : $\Theta _{{n+1}}$ $Q(\Theta )$

Q(\Theta )=E_{\mathbf {T} }\!\!\left[\log p\left(\mathbf {X} ,\mathbf {T} \,|\,\Theta \right ){\Big |}\mathbf {X} \right]=\int _{-\infty }^{\infty }p\left(\mathbf {T} \,|\,\mathbf {X} ,\Theta _{n}\right)\log p\left(\mathbf {X} ,\mathbf {T} \,|\,\Theta \right)d\mathbf {T}

Alternativ beskrivelse

Under visse omstændigheder er det praktisk at tænke på EM-algoritmen som to alternerende maksimeringstrin. [1] [2] Overvej funktionen:

F(q,\theta )=\operatørnavn {E}_{q}[\log L(\theta ;x,Z)]+H(q)=-D_{({\tekst{KL)))){ \big (}q{\big \|}p_{{Z|X}}(\cdot |x;\theta ){\big )}+\log L(\theta ;x)

hvor q er sandsynlighedsfordelingen af uobserverede variable Z ; p Z | X ( · | x ; θ ) er den betingede fordeling af uobserverede variabler for faste observerbare x og parametre θ ; H er entropien , og D KL er afstanden Kullback-Leibler .

Derefter kan trinene i EM-algoritmen repræsenteres som:

Forventningstrin : Vælg q for at maksimere F :

q^{(t)}=\operatørnavn {*} {\arg \,\max }_{q}\ F(q,\theta ^{(t)})

M(aksimisering) trin : Vælg θ for at maksimere F :

\theta ^{(t+1)}=\operatørnavn {*} {\arg \,\max }_{\theta }\ F(q^{(t)},\theta )

Eksempler på brug

k-means - klyngealgoritme bygget på ideen om EM-algoritmen
Elastisk kortmetode til ikke-lineær datadimensionalitetsreduktion
Baum-walisisk algoritme - en algoritme til at estimere parametrene for skjulte Markov-modeller

Noter

↑ Radford; Neal; Hinton, Geoffrey . En visning af EM-algoritmen, der retfærdiggør inkrementelle, sparsomme og andre varianter // Learning in Graphical Models : journal / Michael I. Jordan . - Cambridge, MA: MIT Press, 1999. - P. 355-368 . — ISBN 0262600323 .
↑ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome. 8.5 EM-algoritmen // The Elements of Statistical Learning (neopr.) . - New York: Springer, 2001. - S. 236-243. — ISBN 0-387-95284-5 .

Links

Machine learning og data mining
Opgaver	Klassificeringsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG