فرض کنید که مشاهدات
x
1
,
x
2
,
.
.
.
,
x
n
{\displaystyle x_{1},x_{2},...,x_{n}}
را با
d
{\displaystyle d}
نمایش دهیم، متغیرهای پنهان
h
1
,
h
2
,
.
.
.
,
h
n
{\displaystyle h_{1},h_{2},...,h_{n}}
را با
h
{\displaystyle h}
و همهٔ پارامترهای توزیع را نیز با
θ
{\displaystyle \theta }
. در این صورت لگاریتم درست نمایی کل دادهها (پنهان و نمایان=مشاهدات) برابر خواهد بود با:
L
(
θ
)
=
log
p
(
d
;
θ
)
=
log
∑
h
p
(
d
,
h
;
θ
)
{\displaystyle {\mathcal {L}}(\theta )=\log {p(d;\theta )}=\log {\sum _{h}{p(d,h;\theta )}}}
از آنجا که لگاریتم تابع اکیداً صعودی است، میتوان لگاریتم درست نمایی کل دادهها را نسبت به
θ
{\displaystyle \theta }
بیشینه کرد. هرچند، آرگومان لگاریتم یک مجموع است و نمیتوان به سادگی پاسخ تحلیلی برای
θ
{\displaystyle \theta }
یافت. از این رو، الگوریتم ب-ا ترفندی را برای بیشینه کردن حد پایین لگاریتم درست نمایی بکار میبرد. این حد پایین از نابرابری ینسن بدست میآید.
بر اساس نابرابری ینسن که از کوژ بودن تابع لگاریتم استفاده میکند برای هر دسته
k
{\displaystyle k}
تایی از
t
i
{\displaystyle t_{i}}
ها و
w
i
{\displaystyle w_{i}}
ها اگر
t
i
>
0
{\displaystyle t_{i}>0}
و
∑
w
i
=
1
{\displaystyle \sum {w_{i}}=1}
، خواهیم داشت:
∑
i
=
1
k
w
i
log
t
i
≤
log
∑
i
=
1
k
w
i
t
i
{\displaystyle \sum _{i=1}^{k}{w_{i}\log {t_{i}}}\leq \log {\sum _{i=1}^{k}{w_{i}t_{i}}}}
اکنون
L
{\displaystyle {\mathcal {L}}}
را به صورت زیر باز مینویسیم
L
(
θ
)
=
log
∑
h
q
(
h
)
p
(
d
,
h
;
θ
)
q
(
h
)
≥
∑
h
q
(
h
)
log
p
(
d
,
h
;
θ
)
q
(
h
)
=
J
(
q
,
θ
)
{\displaystyle {\mathcal {L}}(\theta )=\log {\sum _{h}{q(h){\frac {p(d,h;\theta )}{q(h)}}}}\geq \sum _{h}{q(h)\log {\frac {p(d,h;\theta )}{q(h)}}}={\mathcal {J}}(q,\theta )}
با گزینش
q
(
h
)
=
p
(
h
;
d
,
θ
)
{\displaystyle q\left(h\right)=p\left(h;d,\theta \right)}
نابرابری بالا تنگ میشود. این به معنای آن است که نابرابری به برابری تبدیل میشود. این گام الگوریتم همانند بیشینه کردن حدپایین درست نمایی (
J
{\displaystyle {\mathcal {J}}}
) نسبت به
q
{\displaystyle q}
است. در نتیجه روش کار الگوریتم امید ریاضی-بیشینه کردن به صورت زیر است:
پارامترها را مقدار آغازین
θ
(
0
)
{\displaystyle \theta ^{(0)}}
میدهیم.
تا زمان همگرایی به بیشینه محلی ادامه میدهیم:
گام-ا (مید ریاضی):
q
(
t
)
=
arg
max
q
J
(
q
,
θ
(
t
)
)
{\displaystyle q^{(t)}=\arg \max _{q}{{\mathcal {J}}(q,\theta ^{(t)})}}
گام-ب (بیشینه کردن):
θ
(
t
+
1
)
=
arg
max
θ
J
(
q
(
t
)
,
θ
)
{\displaystyle \theta ^{(t+1)}=\arg \max _{\theta }{{\mathcal {J}}(q^{(t)},\theta )}}
مقادیر نهایی
θ
{\displaystyle \theta }
و
q
{\displaystyle q}
را باز گردان
این دیدگاه نسبت به الگوریتم امید ریاضی-بیشینه کردن متعلق به نیل و هینتون است.[ ۱]
بدین ترتیب در هر گام الگوریتم، حد پایین درست نمایی کل دادهها افزایش مییابد تا آنجا که در یک بیشینه محلی همگرا شود. برای رهایی از بیشینههای محلی، این الگوریتم را معمولاً چندین بار با شرایط آغازین متفاوت اجرا میکنند.
اگر
x
=
(
x
1
,
x
2
,
…
,
x
n
)
{\displaystyle \mathbf {x} =(\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n})}
،
n
{\displaystyle n}
داده مستقل از یک توزیع مخلوط گاوسی با بُعد
d
{\displaystyle d}
باشد و
z
=
(
z
1
,
z
2
,
…
,
z
n
)
{\displaystyle \mathbf {z} =(z_{1},z_{2},\ldots ,z_{n})}
متغیرهای پنهانِ مسئله باشد که نشان میدهد هر بار داده از کدام یک از توزیعهای گاوسی آمده است، آنگاه رابطه
x
i
{\displaystyle \mathbf {x_{i}} }
با
z
i
{\displaystyle \mathbf {z_{i}} }
به این شکل خواهد بود (برای سادگی کار تعداد توزیعهای مخلوط گاوسی دو در نظر گرفته شده):[ ۲]
X
i
|
(
Z
i
=
1
)
∼
N
d
(
μ
1
,
Σ
1
)
{\displaystyle X_{i}|(Z_{i}=1)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{1},\Sigma _{1})}
و
X
i
|
(
Z
i
=
2
)
∼
N
d
(
μ
2
,
Σ
2
)
{\displaystyle X_{i}|(Z_{i}=2)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{2},\Sigma _{2})}
و
P
(
Z
i
=
1
)
=
τ
1
{\displaystyle \operatorname {P} (Z_{i}=1)=\tau _{1}\,}
و
P
(
Z
i
=
2
)
=
τ
2
=
1
−
τ
1
{\displaystyle \operatorname {P} (Z_{i}=2)=\tau _{2}=1-\tau _{1}}
هدف یادگیری پارامترهای این دو توزیع و نحوه مخلوط کردن آنهاست یعنی
θ
=
(
τ
,
μ
1
,
μ
2
,
Σ
1
,
Σ
2
)
{\displaystyle \theta ={\big (}{\boldsymbol {\tau }},{\boldsymbol {\mu }}_{1},{\boldsymbol {\mu }}_{2},\Sigma _{1},\Sigma _{2}{\big )}}
، تابع درست نمایی برابر است با
L
(
θ
;
x
)
=
∏
i
=
1
n
∑
j
=
1
2
τ
j
f
(
x
i
;
μ
j
,
Σ
j
)
{\displaystyle L(\theta ;\mathbf {x} )=\prod _{i=1}^{n}\sum _{j=1}^{2}\tau _{j}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j})}
.
حال اگر مقادیر متغیرهای پنهان مشخص بود تابع درست نمایی با عبارت پایین برابر میشد:
L
(
θ
;
x
,
z
)
=
p
(
x
,
z
|
θ
)
=
∏
i
=
1
n
∏
j
=
1
2
[
f
(
x
i
;
μ
j
,
Σ
j
)
τ
j
]
I
(
z
i
=
j
)
{\displaystyle L(\theta ;\mathbf {x} ,\mathbf {z} )=p(\mathbf {x} ,\mathbf {z} \vert \theta )=\prod _{i=1}^{n}\prod _{j=1}^{2}\ [f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j})\tau _{j}]^{\mathbb {I} (z_{i}=j)}}
و اگر این عبارت را بسط دهیم به این معادله میرسیم:
L
(
θ
;
x
,
z
)
=
exp
{
∑
i
=
1
n
∑
j
=
1
2
I
(
z
i
=
j
)
[
log
τ
j
−
1
2
log
|
Σ
j
|
−
1
2
(
x
i
−
μ
j
)
⊤
Σ
j
−
1
(
x
i
−
μ
j
)
−
d
2
log
(
2
π
)
]
}
{\displaystyle 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\}}
f
{\displaystyle f}
تابع چگالی احتمال توزیع گاوس است و
I
{\displaystyle \mathbb {I} }
تابع مشخصه است. در معادله خط قبلی برای هر
i
{\displaystyle i}
دقیقا یک تابع مشخصه یک است و دیگری صفر، یعنی دقیقا برای یکی از
j
{\displaystyle j}
ها
I
(
z
i
=
j
)
{\displaystyle \mathbb {I} (z_{i}=j)}
برابر با یک خواهد بود.
طبق قضیه بیز
θ
(
t
)
{\displaystyle \theta ^{(t)}}
که همان احتمال شرطی
Z
i
{\displaystyle Z_{i}}
است به این شکل محاسبه میشود:
T
j
,
i
(
t
)
:=
P
(
Z
i
=
j
|
X
i
=
x
i
;
θ
(
t
)
)
=
τ
j
(
t
)
f
(
x
i
;
μ
j
(
t
)
,
Σ
j
(
t
)
)
τ
1
(
t
)
f
(
x
i
;
μ
1
(
t
)
,
Σ
1
(
t
)
)
+
τ
2
(
t
)
f
(
x
i
;
μ
2
(
t
)
,
Σ
2
(
t
)
)
{\displaystyle 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)})}}}
همچنین تابع
Q
{\displaystyle Q}
الگوریتم به شکل ذیل بدست میآید:
Q
(
θ
|
θ
(
t
)
)
=
E
Z
|
X
,
θ
(
t
)
[
log
L
(
θ
;
x
,
Z
)
]
=
E
Z
|
X
,
θ
(
t
)
[
log
∏
i
=
1
n
L
(
θ
;
x
i
,
z
i
)
]
=
E
Z
|
X
,
θ
(
t
)
[
∑
i
=
1
n
log
L
(
θ
;
x
i
,
z
i
)
]
=
∑
i
=
1
n
E
Z
i
|
X
;
θ
(
t
)
[
log
L
(
θ
;
x
i
,
z
i
)
]
=
∑
i
=
1
n
∑
j
=
1
2
P
(
Z
i
=
j
|
X
i
=
x
i
;
θ
(
t
)
)
log
L
(
θ
j
;
x
i
,
z
i
)
=
∑
i
=
1
n
∑
j
=
1
2
T
j
,
i
(
t
)
[
log
τ
j
−
1
2
log
|
Σ
j
|
−
1
2
(
x
i
−
μ
j
)
⊤
Σ
j
−
1
(
x
i
−
μ
j
)
−
d
2
log
(
2
π
)
]
{\displaystyle {\begin{aligned}Q(\theta |\theta ^{(t)})&=\operatorname {E} _{\mathbf {Z} |\mathbf {X} ,\mathbf {\theta } ^{(t)}}[\log L(\theta ;\mathbf {x} ,\mathbf {Z} )]\\&=\operatorname {E} _{\mathbf {Z} |\mathbf {X} ,\mathbf {\theta } ^{(t)}}[\log \prod _{i=1}^{n}L(\theta ;\mathbf {x} _{i},\mathbf {z} _{i})]\\&=\operatorname {E} _{\mathbf {Z} |\mathbf {X} ,\mathbf {\theta } ^{(t)}}[\sum _{i=1}^{n}\log L(\theta ;\mathbf {x} _{i},\mathbf {z} _{i})]\\&=\sum _{i=1}^{n}\operatorname {E} _{\mathbf {Z_{i}} |\mathbf {X} ;\mathbf {\theta } ^{(t)}}[\log L(\theta ;\mathbf {x} _{i},\mathbf {z} _{i})]\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}P(Z_{i}=j|X_{i}=\mathbf {x} _{i};\theta ^{(t)})\log L(\theta _{j};\mathbf {x} _{i},\mathbf {z} _{i})\\&=\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{aligned}}}
امید ریاضی
log
L
(
θ
;
x
i
,
z
i
)
{\displaystyle \log L(\theta ;\mathbf {x} _{i},\mathbf {z} _{i})}
در معادله بالا نسبت به توزیع احتمال مشروط
Z
i
{\displaystyle Z_{i}}
یعنی
P
(
Z
i
|
X
i
=
x
i
;
θ
(
t
)
)
{\displaystyle P(Z_{i}|X_{i}=\mathbf {x} _{i};\theta ^{(t)})}
گرفته می شود. این احتمال برای هر
x
i
{\displaystyle \mathbf {x} _{i}}
میتواند مقداری متفاوت داشته باشد.
τ
(
t
+
1
)
=
a
r
g
m
a
x
τ
Q
(
θ
|
θ
(
t
)
)
=
a
r
g
m
a
x
τ
{
[
∑
i
=
1
n
T
1
,
i
(
t
)
]
log
τ
1
+
[
∑
i
=
1
n
T
2
,
i
(
t
)
]
log
τ
2
}
{\displaystyle {\begin{aligned}{\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{aligned}}}
τ
j
(
t
+
1
)
=
∑
i
=
1
n
T
j
,
i
(
t
)
∑
i
=
1
n
(
T
1
,
i
(
t
)
+
T
2
,
i
(
t
)
)
=
1
n
∑
i
=
1
n
T
j
,
i
(
t
)
{\displaystyle \tau _{j}^{(t+1)}={\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)}}
(
μ
1
(
t
+
1
)
,
Σ
1
(
t
+
1
)
)
=
a
r
g
m
a
x
μ
1
,
Σ
1
Q
(
θ
|
θ
(
t
)
)
=
a
r
g
m
a
x
μ
1
,
Σ
1
∑
i
=
1
n
T
1
,
i
(
t
)
{
−
1
2
log
|
Σ
1
|
−
1
2
(
x
i
−
μ
1
)
⊤
Σ
1
−
1
(
x
i
−
μ
1
)
}
{\displaystyle {\begin{aligned}({\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{aligned}}}
بر طبق برآورد درست نمایی بیشنه توزیع گاوسی ، مقادیر میانگین و کوواریانس را به این شکل محاسبه میکنیم:
μ
1
(
t
+
1
)
=
∑
i
=
1
n
T
1
,
i
(
t
)
x
i
∑
i
=
1
n
T
1
,
i
(
t
)
{\displaystyle {\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)}}}}
و
Σ
1
(
t
+
1
)
=
∑
i
=
1
n
T
1
,
i
(
t
)
(
x
i
−
μ
1
(
t
+
1
)
)
(
x
i
−
μ
1
(
t
+
1
)
)
⊤
∑
i
=
1
n
T
1
,
i
(
t
)
{\displaystyle \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)}}}}
و
μ
2
(
t
+
1
)
=
∑
i
=
1
n
T
2
,
i
(
t
)
x
i
∑
i
=
1
n
T
2
,
i
(
t
)
{\displaystyle {\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)}}}}
و
Σ
2
(
t
+
1
)
=
∑
i
=
1
n
T
2
,
i
(
t
)
(
x
i
−
μ
2
(
t
+
1
)
)
(
x
i
−
μ
2
(
t
+
1
)
)
⊤
∑
i
=
1
n
T
2
,
i
(
t
)
{\displaystyle \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)}}}}
مراحل E و M را بهصورت متناوب آنقدر اجرا میکنیم تا جایی که میزان افزایش تابع امید ریاضی مشروط از یک حد از پیش تعیین شدهای مانند
ϵ
{\displaystyle \epsilon }
بیشتر نشود، به زبان ریاضی یعنی زمانی که نابرابری پایین صدق کند.
E
Z
|
θ
(
t
)
,
x
[
log
L
(
θ
(
t
)
;
x
,
Z
)
]
≤
E
Z
|
θ
(
t
−
1
)
,
x
[
log
L
(
θ
(
t
−
1
)
;
x
,
Z
)
]
+
ϵ
{\displaystyle E_{Z|\theta ^{(t)},\mathbf {x} }[\log L(\theta ^{(t)};\mathbf {x} ,\mathbf {Z} )]\leq E_{Z|\theta ^{(t-1)},\mathbf {x} }[\log L(\theta ^{(t-1)};\mathbf {x} ,\mathbf {Z} )]+\epsilon }