Изворни код странице Алгоритам очекивања-максимизације

{{чишћење|разлог=Унос унутрашњих веза и референци|датум=12. 2016.}}
У [[статистика|статистици]], '''алгоритам максимизације очекиване веродостојности''' (EM - {{јез-енг|Expectation-maximization}}) је [[Итерација|итеративна]] процедура за процену параметара на основу критеријума максималне веродостојности (МЛ - {{јез-енг|Maximum Likelihood}}) или оцене апостериорног максимума (МАП - {{јез-енг|Maximum a posteriori}}), код којих су присутне вредности посматраних величина које имају особину ''θ'' која се не може измерити, или се не може директно измерити (латентне променљиве).

ЕМ алгоритам наизменично примењује "корак Е" у којем се генерише функција [[Очекивана вредност|очекиване вредности]] логаритма веродостојности израчунату коришћењем тренутне процене параметара, и "корак М", у којем се израчунавају параметри за које функције генерисана у кораку Е узима максималну вредност. Параметри добијени у кораку М се потом користе за одређивање расподеле латентних варијабли за следећи корак Е.

== Историјат ==

Име ЕМ алгоритма и начин функционисања, дато је у раду из 1977. године, који су написали Артур Демпстер, Нан Лаирд и Доналд Рубин.<ref>{{cite journal
 |last=Dempster |first=A.P. |authorlink1=Arthur P. Dempster
 |last2=Laird |first2=N.M. |authorlink2=Nan Laird |last3=Rubin
 |first3=D.B. |authorlink3=Donald Rubin
 |title=Maximum Likelihood from Incomplete Data via the EM Algorithm
 |journal=[[Journal of the Royal Statistical Society, Series B]]
 |year=1977 |volume=39 |issue=1 |pages=1–38
 |jstor=2984875 | mr = 0501537
}}</ref> Њихов рад је генерализовао методу и скицирао анализу конвергенције за ширу класу проблема. Без обзира на раније проналаске, њихова иновативна метода се прославила у јавности и њивов рад окатегорисан као брилијантан. Рад Демпстер-Лаирд-Рубин је основао ЕМ метод као веома важан део статистичке анализе.<ref name="Sundberg1974">{{cite journal
 |last=Sundberg |first=Rolf
 |title=Maximum likelihood theory for incomplete data from an exponential family
 |journal=Scandinavian Journal of Statistics
 |volume=1 |year=1974 |issue=2 |pages=49–58
 |jstor=4615553 | mr = 381110
}}</ref><ref name="Sundberg1971">Rolf Sundberg. 1971. ''Maximum likelihood theory and applications for distributions generated when observing a function of an exponential family variable''. Dissertation, Institute for Mathematical Statistics, Stockholm University.</ref><ref name="Sundberg1976">{{cite journal
 |last=Sundberg |first=Rolf
 |year=1976
 |title=An iterative method for solution of the likelihood equations for incomplete data from exponential families
 |journal=[[Communications in Statistics]] – Simulation and Computation
 |volume=5 |issue=1 |pages=55–64
 |doi=10.1080/03610917608812007 |mr=443190 }}</ref>

== Увод ==

ЕМ алгоритам се користи за проналажење параметра максималне веродостојности статистичког модела у случајевима код којих се једначине не могу решити директно. Обично ови модели поред непознатих параметара и познатих резултата мерења укључују и латентне променљиве. То значи да, или недостају неке од мерених вредности, или се модел може формулисати једноставније претпостављајући постојање додатних неизмерених вредности посматраних величина.

Проналажење решења максималне веродостојности захтева узимање извода функције вероватноће по свим непознатим вредностима. Код статистичих модела са латентним променљивима ово обично није могуће. Уместо тога, резултат је скуп међусобно повезаних једначина у којој решење за параметре захтева познавање вредности латентних променљивих и обратно, али замена једног скупа једначина у други доводи до нерешивих једначина. ЕМ алгоритам полази од запажања да се ова два сета једначина могу решити нумерички. То се може извести тако што се изаберу произвољне вредности за један од два скупа непознатих, затим се те произвољне вредности употребе за процену другог скупа, а затим помоћу ових нових вредности нађе боља процена првог скупа. Процедура се наставља итеративно док резултујуће вредности не конвергирају ка фиксним тачкама. Није очигледно да се овим алгоритмом може доћи до решења у општем случају, али се може доказати да је могуће у конкретним случајевима. При томе се извод веродостојности може привести произвољно близу нули, што значи да је пронађена тачка или локални максимум или седласта тачка. Није гарантовано да ће пронађени максимум бити глобални максимум. У неким случајевима функција веродостојности има сингуларитете који обично представљају максимуме без смислене интерпретације у контексту у којем се алгоритам примењује.

== Опис алгоритма ==

Дати статистички модел који се састоји од скупа <math>\mathbf{X}</math> посматраних података, скуп непримећених латентних података или вредности које недостају <math>\mathbf{Z}</math> и вектр непознатих параметара <math>\boldsymbol\theta</math>, заједно са функцијом веродостојности <math>L(\boldsymbol\theta; \mathbf{X}, \mathbf{Z}) = p(\mathbf{X}, \mathbf{Z}|\boldsymbol\theta)</math>, процена максималне веродостојности (МЛЕ - {{јез-енг|Maximum likelihood estimate}}) од непознатих параметара одређује маргиналне веродостојности посматраних података

:<math>L(\boldsymbol\theta; \mathbf{X}) = p(\mathbf{X}|\boldsymbol\theta) = \sum_{\mathbf{Z}} p(\mathbf{X}, \mathbf{Z}|\boldsymbol\theta)</math>

Међутим, ово је често нерешиво (нпр. Ако се деси да број вредности расте експоненцијално што је секвенца дужа, онда ће тачан прорачун суме бити изузетно тежак).

ЕМ алгоритам покушава да пронађе МЛЕ од граничне веродостојности итеративном применом следећа два корака:

:'''Корак очекивања (Е корак)''': Израчунава очекивану вредност лог веродостојности функције вероватноће, у погледу на условну расподелу <math>\mathbf{Z}</math> датим <math>\mathbf{X}</math> под тренутном проценом параметара <math>\boldsymbol\theta^{(t)}</math>:
::<math>Q(\boldsymbol\theta|\boldsymbol\theta^{(t)}) = \operatorname{E}_{\mathbf{Z}|\mathbf{X},\boldsymbol\theta^{(t)}}\left[ \log L (\boldsymbol\theta;\mathbf{X},\mathbf{Z})  \right] \,</math>
:'''Корак максимизације (М корак)''': Проналази параметар који максимизује следеће:
::<math>\boldsymbol\theta^{(t+1)} = \underset{\boldsymbol\theta}{\operatorname{arg\,max}} \ Q(\boldsymbol\theta|\boldsymbol\theta^{(t)}) \, </math>

Типични модели на које се примењује ЕМ:
# Посматране тачке података <math>\mathbf{X}</math> могу бити дискретне (узимајући вредности из коначног или пребројиво бесконачног скупа) или непрекидне (узмањући вредности из непребројиво бесконачног скупа). Могу, у ставри, бити и вектор опсевације повезан са сваком тачком података.
# Вредности које недостају (латентне варијабле) <math>\mathbf{Z}</math> су дискретне, извучене из фиксног броја вредности, а постоји једна латентна променљива по посматраној тачки података.
# Параметри су непрекидни, и има две врсте: Параметри који су повезани са свим тачкама података, и параметара повезаним са одређеном вредношћу латентне варијабле.

Међутим, могуће је да се ЕМ примени и на друге врсте модела. Ако знамо вредности параметара <math>\boldsymbol\theta</math>, обично се може наћи вредност латентних варијабли <math>\mathbf{Z}</math> повећавањем лог-веродостојности по свим могућим вредностима <math>\mathbf{Z}</math>, или једноставно итеративно преко <math>\mathbf{Z}</math> или преко алгоритма, као што је Витерби алгоритам за скривене Маркове моделе. Насупрот томе, ако знамо вредности латентних варијабли <math>\mathbf{Z}</math>, можемо наћи процену параметрара <math>\boldsymbol\theta</math> прилично лако, једноставним груписањем посматране тачке података на основу вредности придружене латенте варијабле и просека вредности, или нека функција вредности, од тачака у свакој групи. Ово сугерише итеративни алгоритам, у случају када су <math>\boldsymbol\theta</math> и <math>\mathbf{Z}</math>непознати:
# Прво, иницијализујте параметре <math>\boldsymbol\theta</math> неким случајним вредностима.
# Израчунај најбољу вредност за <math>\mathbf{Z}</math> помоћу ових вредности параметара.
# Затим, користите ове израчунате вредности <math>\mathbf{Z}</math> да израчунате бољу процену параметара <math>\boldsymbol\theta</math>. Параметри повезани са одређеном вредношћу <math>\mathbf{Z}</math> ће користити само оне тачке података код којих придружене латентне варијабле имају ту вредност.
# Вршите итерацију корака 2 и 3 до конвергенције.

Управо описан алгоритам монотоно прилази локаном минимуму функције, а најчешће се назива хард ЕМ. K-mean алгоритам је пример ове класе алгоритма.

== Својства ==

Говорећи о Е кораку, мало је погрешан. Оно што се рачуна у првом кораку су фиксни параметри зависни од података функције Q. Када су параметри Q познати, потпуно су одређени и увећани у другом М кораку ЕМ алогритма. 

Иако ЕМ итерација повећава број посматраних података (тј. маргинали) функције веродостојности, не постоји гаранција да низ конвергира ка процени максималне веродостојности (МЛЕ). За бимодалне дистрибуције, ово значи да ЕМ алгоритам може конвергирати до локалног максимума посматраних података функције веродостојности, зависећи од почетних вредности. Постоји низ хеуристичких или метахеуристичких приступа за "бежање" локалним максимумима, као што су насумични рестарт (кренувши од неколико различитих случајних почетних процена ''θ''<sup>(''t'')</sub>), или применом алгоритма симулације жарења.

ЕМ је нарочито користан када је веродостојност у породици експоненцијалних алгоритама: Е корак постаје збир очекивања довољне статистике, а М корак подразумева максимизовање [[Линеарна функција|линеарне функције]]. У том случају обично је могуће извести исправке у затвореној форми за сваки корак, користећи Сундберг формулу (Објавио Ралф Сундберг користећи необјављене резултате Пер Мартин–Лофа и Андерс Мартин-Лофа).

ЕМ метода је модификована за израчунавање максималне апостериорне процене (МАП), са Бајесовом статистиком, у оригиналном раду Демпстер, Лаирд и Рубин.

Постоје и друге методе за проналажење максималне веродостојности, једна од метода је варијација Гаус-Њутновог алгоритма, а постоје и још неке. За разлику од ЕМ, такве методе обично захтевају процену првог или другог деривата функције веродостојности.

== Доказ коректности ==

ЕМ алгоритам ради на побољшању <math>Q(\boldsymbol\theta|\boldsymbol\theta^{(t)})</math>, а не побољшава директно <math>\log p(\mathbf{X}|\boldsymbol\theta)</math>. Овде смо показали да побољшања првог подразумева побољшање последњг.
За било које <math>\mathbf{Z}</math> са не нултом вероватноћом <math>p(\mathbf{Z}|\mathbf{X},\boldsymbol\theta)</math>, можемо записати
::<math>
\log p(\mathbf{X}|\boldsymbol\theta) = \log p(\mathbf{X},\mathbf{Z}|\boldsymbol\theta) - \log p(\mathbf{Z}|\mathbf{X},\boldsymbol\theta) \,.
</math>
Узимамо очекивање над вредностима <math>\mathbf{Z}</math> множењем обе стране са <math>p(\mathbf{Z}|\mathbf{X},\boldsymbol\theta^{(t)})</math>. Сабирањем и (или интегрисањем) преко <math>\mathbf{Z}</math>. Лева страна је константа очекивања, па добијамо:
::<math>
\begin{align}
\log p(\mathbf{X}|\boldsymbol\theta) &
= \sum_{\mathbf{Z}} p(\mathbf{Z}|\mathbf{X},\boldsymbol\theta^{(t)}) \log p(\mathbf{X},\mathbf{Z}|\boldsymbol\theta)
- \sum_{\mathbf{Z}} p(\mathbf{Z}|\mathbf{X},\boldsymbol\theta^{(t)}) \log p(\mathbf{Z}|\mathbf{X},\boldsymbol\theta) \\
& = Q(\boldsymbol\theta|\boldsymbol\theta^{(t)}) + H(\boldsymbol\theta|\boldsymbol\theta^{(t)}) \,,
\end{align}
</math>
где је <math>H(\boldsymbol\theta|\boldsymbol\theta^{(t)})</math> одређен негирањем суме коју је заменио. Ова последња једначина важи за било коју вредност <math>\boldsymbol\theta</math>, uključujući <math>\boldsymbol\theta = \boldsymbol\theta^{(t)}</math>,
::<math>
\log p(\mathbf{X}|\boldsymbol\theta^{(t)})
= Q(\boldsymbol\theta^{(t)}|\boldsymbol\theta^{(t)}) + H(\boldsymbol\theta^{(t)}|\boldsymbol\theta^{(t)}) \,,
</math>
и одузимањем ове последње једначине са оном из претходне, добијамо
::<math>
\log p(\mathbf{X}|\boldsymbol\theta) - \log p(\mathbf{X}|\boldsymbol\theta^{(t)})
= Q(\boldsymbol\theta|\boldsymbol\theta^{(t)}) - Q(\boldsymbol\theta^{(t)}|\boldsymbol\theta^{(t)})
 + H(\boldsymbol\theta|\boldsymbol\theta^{(t)}) - H(\boldsymbol\theta^{(t)}|\boldsymbol\theta^{(t)}) \,,
</math>
Међутим, Гисова неједнакост нам говори да <math>H(\boldsymbol\theta|\boldsymbol\theta^{(t)}) \ge H(\boldsymbol\theta^{(t)}|\boldsymbol\theta^{(t)})</math>, па можемо закључити да
::<math>
\log p(\mathbf{X}|\boldsymbol\theta) - \log p(\mathbf{X}|\boldsymbol\theta^{(t)})
\ge Q(\boldsymbol\theta|\boldsymbol\theta^{(t)}) - Q(\boldsymbol\theta^{(t)}|\boldsymbol\theta^{(t)}) \,.
</math>
Другим речима, бирајући <math>\boldsymbol\theta</math> да унапредимо <math>Q(\boldsymbol\theta|\boldsymbol\theta^{(t)})</math> изван <math>Q(\boldsymbol\theta^{(t)}|\boldsymbol\theta^{(t)})</math> ће унапредити <math>\log p(\mathbf{X}|\boldsymbol\theta)</math> preko <math>\log p(\mathbf{X}|\boldsymbol\theta^{(t)})</math> најмање толико.

== Апликације ==

Под неким околностима, врло је згодно гледати на ЕМ алгоритам као два наизменична корака максимизирања. Размотримо функцију:
:<math>F(q,\theta) = \operatorname{E}_q [ \log L (\theta ; x,Z)] + H(q) = -D_{\mathrm{KL}}\big(q \big\| p_{Z|X}(\cdot|x;\theta ) \big) + \log L(\theta;x) </math>
где је ''q'' произвољна расподела вероватноћа над непосматраним подацима ''z'', ''p''<sub>''Z''|''X''</sub>(· |''x'';''θ'') је условна расподела непосматраних података где су дати посматрани подаци ''x'', ''H'' је ентропија и ''D''<sub>KL</sub> је Кулбак-Лајблер дивергенција.

Онда се кораци ЕМ алгоритма могу посматрати као:
:'''Корак очекивања''': Изабери ''q'' да максимизујеш ''F'':
::<math> q^{(t)} = \operatorname*{arg\,max}_q \ F(q,\theta^{(t)}) </math>
:'''Корак максимизације''': Изабери ''θ'' да максимизујеш ''F'':
::<math> \theta^{(t+1)} = \operatorname*{arg\,max}_\theta \ F(q^{(t)},\theta) </math>

== Пример ==
=== Гаусова расподела ===

[[Датотека:Em old faithful.gif|мини|240px| Анимација која демонстрира ЕМ алгоритам користећи модел двокомпонентне Гаусове расподеле над подацима гејзира [[Стари Верни]]. Алгоритам иде од насумичне иницијализације до конвергенције.]]

Нека је '''x'''&nbsp;=&nbsp;('''x'''<sub>1</sub>,'''x'''<sub>2</sub>,…,'''x'''<sub>''n''</sub>) пример од n независних опсервација из расподеле две мултиваријационе [[Нормална расподела|нормалне расподеле]] димензије ''d'', и нека је '''z'''=(''z''<sub>1</sub>,''z''<sub>2</sub>,…,''z''<sub>''n''</sub>) латентна варијабла којом се одређује компонента из које потиче посматрање.
:<math>X_i |(Z_i = 1) \sim \mathcal{N}_d(\boldsymbol{\mu}_1,\Sigma_1)</math> i <math>X_i |(Z_i = 2) \sim \mathcal{N}_d(\boldsymbol{\mu}_2,\Sigma_2)</math>
где је

<math>\operatorname{P} (Z_i = 1 ) = \tau_1 \, </math> i <math>\operatorname{P} (Z_i=2) = \tau_2 = 1-\tau_1</math>

Циљ је да се процене непознати параметари који представљају “мешање” вредности између Гаусових и начини и коваријансе сваког.
:<math>\theta = \big(\boldsymbol{\tau},\boldsymbol{\mu}_1,\boldsymbol{\mu}_2,\Sigma_1,\Sigma_2 \big)</math>
где је функција веродостојности:
:<math>L(\theta;\mathbf{x},\mathbf{z}) = P(\mathbf{x},\mathbf{z} \vert \theta) = \prod_{i=1}^n  \sum_{j=1}^2  \mathbb{I}(z_i=j) \ \tau_j \ f(\mathbf{x}_i;\boldsymbol{\mu}_j,\Sigma_j) </math>
где је <math>\mathbb{I}</math> индикатор функције, а ''f'' је расподела вероватноће од више варијанта. Ово може бити преписано фамилији експоненцијалних форми:
:<math>L(\theta;\mathbf{x},\mathbf{z}) = \exp \left\{ \sum_{i=1}^n \sum_{j=1}^2 \mathbb{I}(z_i=j) \big[ \log \tau_j -\tfrac{1}{2} \log |\Sigma_j| -\tfrac{1}{2}(\mathbf{x}_i-\boldsymbol{\mu}_j)^\top\Sigma_j^{-1} (\mathbf{x}_i-\boldsymbol{\mu}_j) -\tfrac{d}{2} \log(2\pi) \big] \right\}. </math>
Да би се видела последња једнакост, имајте на уму да за свако ''i'' сви индикатори <math>\mathbb{I}(z_i=j)</math> су једнаки нули, осим једног који је једнак један. Унутрашња сума се на тај начин смањује на један члан.

==== Корак Е ====

Тренутна процена параметара ''θ''<sup>(''t'')</sup> условна расподела ''Z''<sub>''i''</sub> је детерминисана са [[Бајесова теорема|Бајесовом теоремом]], да буде пропорционалне висине од нормалне расподеле вероватноће, са тежином ''τ'':
:<math>T_{j,i}^{(t)} := \operatorname{P}(Z_i=j | X_i=\mathbf{x}_i ;\theta^{(t)}) = \frac{\tau_j^{(t)} \ f(\mathbf{x}_i;\boldsymbol{\mu}_j^{(t)},\Sigma_j^{(t)})}{\tau_1^{(t)} \ f(\mathbf{x}_i;\boldsymbol{\mu}_1^{(t)},\Sigma_1^{(t)}) + \tau_2^{(t)} \ f(\mathbf{x}_i;\boldsymbol{\mu}_2^{(t)},\Sigma_2^{(t)})} </math>.

Резултат Е корака у функцији:
:<math>\begin{align}Q(\theta|\theta^{(t)})
&= \operatorname{E} [\log L(\theta;\mathbf{x},\mathbf{Z})] \\
&= \sum_{i=1}^n \sum_{j=1}^2 T_{j,i}^{(t)} \big[ \log \tau_j  -\tfrac{1}{2} \log |\Sigma_j| -\tfrac{1}{2}(\mathbf{x}_i-\boldsymbol{\mu}_j)^\top\Sigma_j^{-1} (\mathbf{x}_i-\boldsymbol{\mu}_j) -\tfrac{d}{2} \log(2\pi) \big]
\end{align}</math>
Да бисмо видели последњу једнакост, имајте на уму да смо сумирањем по свим могућим вредностима од ''z'' где је вероватноћа сваког ''z'' производ <math>\prod_{i=1}^n T_{j,i}^{(t)}</math>. Сада погледајмо коефицијенте сваког члана унутар суме за.<math>L(\theta;\mathbf{x},\mathbf{z})</math>. Биће два члана <math>T_{1,i}^{(t)}(\sum_{j=1,2}\prod_{k\ne i}T_{j,k}^{(t)})</math> and <math>T_{2,i}^{(t)}(\sum_{j=1,2}\prod_{k\ne i}T_{j,k}^{(t)})</math>.
Будући да термин у загради маргинализује по свим могућим случајевима кад <math>k\ne i</math>, је једнако 1. Тако су коефицијенти сваког члана <math>T_{1,i}^{(t)}</math> и <math>T_{2,i}^{(t)}</math> који теже једнакости.

==== Корак М ====
Квадратни облик ''Q''(''θ''|''θ''<sup>(''t'')</sup>) значи да одређивање максималне вредности ''θ'' је релативно једноставно. Имајте на уму да ''τ'', ('''μ'''<sub>1</sub>,''Σ''<sub>1</sub>) и ('''μ'''<sub>2</sub>,''Σ''<sub>2</sub>) могу бити све маскимизовано независно једни од других, јер се сви они појављују у одвојеним линеарним члановима. За почетак, узмимо у обзир ''τ'', које има ограничење ''τ''<sub>1</sub> + ''τ''<sub>2</sub>=1:
:<math>\begin{align}\boldsymbol{\tau}^{(t+1)}
&= \underset{\boldsymbol{\tau}} {\operatorname{arg\,max}}\  Q(\theta | \theta^{(t)} ) \\
&= \underset{\boldsymbol{\tau}} {\operatorname{arg\,max}} \ \left\{ \left[  \sum_{i=1}^n T_{1,i}^{(t)} \right] \log \tau_1 + \left[  \sum_{i=1}^n T_{2,i}^{(t)} \right] \log \tau_2  \right\}
\end{align}</math>
Ово има исти облик као МЛЕ за биномну расподелу, тако да:
:<math>\tau^{(t+1)}_j = \frac{\sum_{i=1}^n T_{j,i}^{(t)}}{\sum_{i=1}^n (T_{1,i}^{(t)} + T_{2,i}^{(t)} ) } = \frac{1}{n} \sum_{i=1}^n T_{j,i}^{(t)}</math>

У наредним проценама ('''μ'''<sub>1</sub>,''Σ''<sub>1</sub>):
:<math>\begin{align}(\boldsymbol{\mu}_1^{(t+1)},\Sigma_1^{(t+1)})
&= \underset{\boldsymbol{\mu}_1,\Sigma_1} {\operatorname{arg\,max}}\  Q(\theta | \theta^{(t)} ) \\
&= \underset{\boldsymbol{\mu}_1,\Sigma_1} {\operatorname{arg\,max}}\  \sum_{i=1}^n T_{1,i}^{(t)} \left\{ -\tfrac{1}{2} \log |\Sigma_1| -\tfrac{1}{2}(\mathbf{x}_i-\boldsymbol{\mu}_1)^\top\Sigma_1^{-1} (\mathbf{x}_i-\boldsymbol{\mu}_1) \right\}
\end{align}</math>
Ово има исту форму као и тежак МЛЕ за нормалну расподелу, тако да
:<math>\boldsymbol{\mu}_1^{(t+1)} = \frac{\sum_{i=1}^n T_{1,i}^{(t)} \mathbf{x}_i}{\sum_{i=1}^n T_{1,i}^{(t)}} </math> and <math>\Sigma_1^{(t+1)} = \frac{\sum_{i=1}^n T_{1,i}^{(t)} (\mathbf{x}_i - \boldsymbol{\mu}_1^{(t+1)}) (\mathbf{x}_i - \boldsymbol{\mu}_1^{(t+1)})^\top }{\sum_{i=1}^n T_{1,i}^{(t)}} </math>
и, преко симетрије:
:<math>\boldsymbol{\mu}_2^{(t+1)} = \frac{\sum_{i=1}^n T_{2,i}^{(t)} \mathbf{x}_i}{\sum_{i=1}^n T_{2,i}^{(t)}} </math> and <math>\Sigma_2^{(t+1)} = \frac{\sum_{i=1}^n T_{2,i}^{(t)} (\mathbf{x}_i - \boldsymbol{\mu}_2^{(t+1)}) (\mathbf{x}_i - \boldsymbol{\mu}_2^{(t+1)})^\top }{\sum_{i=1}^n T_{2,i}^{(t)}} </math>.

== Референце ==
{{reflist|2}}

== Литература ==
{{Литература|2}}
* Robert Hogg, Joseph McKean and Allen Craig. ''Introduction to Mathematical Statistics''. pp. 359-364. Upper Saddle River, NJ: Pearson Prentice Hall, 2005.
* [http://www.inference.phy.cam.ac.uk/mackay/itila/ The on-line textbook: Information Theory, Inference, and Learning Algorithms], by [[David J.C. MacKay]] includes simple examples of the EM algorithm such as clustering using the soft ''k''-means algorithm, and emphasizes the variational view of the EM algorithm, as described in Chapter 33.7 of version 7.2 (fourth edition).
* [https://web.archive.org/web/20120717061150/http://www.ee.washington.edu/research/guptalab/publications/EMbookChenGupta2010.pdf Theory and Use of the EM Method] by M. R. Gupta and Y. Chen is a well-written short book on EM, including detailed derivation of EM for GMMs, HMMs, and Dirichlet.
* {{cite document | title = A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models | first = Jeff | last = Bilmes | citeseerx = 10.1.1.28.613 | postscript = , }} includes a simplified derivation of the EM equations for Gaussian Mixtures and Gaussian Mixture Hidden Markov Models.
* [http://www.cse.buffalo.edu/faculty/mbeal/papers/beal03.pdf Variational Algorithms for Approximate Bayesian Inference], by M. J. Beal includes comparisons of EM to Variational Bayesian EM and derivations of several models including Variational Bayesian HMMs ([http://www.cse.buffalo.edu/faculty/mbeal/thesis/index.html chapters]).
* {{cite document | title = The Expectation Maximization Algorithm | first = Frank | last = Dellaert | citeseerx = 10.1.1.9.9735 | postscript = , }} gives an easier explanation of EM algorithm in terms of lowerbound maximization.
* [http://www.seanborman.com/publications/EM_algorithm.pdf The Expectation Maximization Algorithm: A short tutorial], A self-contained derivation of the EM Algorithm by Sean Borman.
* [http://pages.cs.wisc.edu/~jerryzhu/cs838/EM.pdf The EM Algorithm], by Xiaojin Zhu.
* {{cite journal |date= 2011|title=EM algorithm and variants: an informal tutorial |url= |journal= |volume=|issue= |pages= |doi= |arxiv=1105.1476|last1= Roche|first1= Alexis}}
* {{Cite book |last = Bishop   | first = Christopher M. | title = Pattern Recognition and Machine Learning |url = https://archive.org/details/patternrecogniti0000bish   |year=2006| publisher = Springer |isbn=978-0-387-31073-2}}
* {{Cite book |author=Einicke, G.A.|year=2012| title = Smoothing, Filtering and Prediction: Estimating the Past, Present and Future| publisher = Intech| location = Rijeka, Croatia|isbn=978-953-307-752-9|url=http://www.intechopen.com/books/smoothing-filtering-and-prediction-estimating-the-past-present-and-future}}
{{Литература крај}}

== Спољашње везе ==
{{Портал бар|Информатика}}
* -{Various 1D, 2D and 3D [http://wiki.stat.ucla.edu/socr/index.php/SOCR_EduMaterials_Activities_2D_PointSegmentation_EM_Mixture demonstrations of EM together with Mixture Modeling] are provided as part of the paired [[SOCR]] activities and applets. These applets and activities show empirically the properties of the EM algorithm for parameter estimation in diverse settings.}-
* [https://github.com/l-/CommonDataAnalysis -{Class hierarchy in C++ (GPL) including Gaussian Mixtures}-]
* -{Fast and clean C implementation of the [https://github.com/juandavm/em4gmm Expectation Maximization] (EM) algorithm for estimating [https://github.com/juandavm/em4gmm Gaussian Mixture Models] (GMMs).}-

{{нормативна контрола}}

[[Категорија:Теорија естимације]]
[[Категорија:Алгоритми машинског учења]]
[[Категорија:Статистички алгоритми]]
[[Категорија:Оптимизациони алгоритми и методи]]
[[Категорија:Алгоритми кластеризације података]]