百面机器学习06-概率图模型
01：概率图模型的联合概率分布
场景描述
概率图模型最为“精彩”的部分就是能够用简洁清晰的图示形式表达概率生成的关系 。而通过概率图还原真概率分布不仅是概率图模型最重要的功能，也是掌握概率图模型最重要的标准 。 本节考查面试者能否根据贝叶斯网络刊马尔可夫网络的概率图还原其联合概率分布
知识点：概率图，贝叶斯网络，马尔可夫网络
问题1：能否写出图 6.1 ( a ）中贝叶斯网络的联合概率分布？
分析与解答
由图可见，在给定 A 的条件下 B 相 C 是条件独立的，基于条件概率的定义可得
P
(
C
∣
A
,
B
)
=
P
(
B
,
C
∣
A
)
P
(
B
∣
A
)
=
P
(
B
∣
A
)
P
(
C
∣
A
)
P
(
B
∣
A
)
=
P
(
C
∣
A
)
\begin{aligned} P(C \mid A, B) &=\frac{P(B, C \mid A)}{P(B \mid A)}=\frac{P(B \mid A) P(C \mid A)}{P(B \mid A)} \\ &=P(C \mid A) \end{aligned}
P(C∣A,B)=P(B∣A)P(B,C∣A)=P(B∣A)P(B∣A)P(C∣A)=P(C∣A)
同理，在给定
B
B
B 和
C
C
C 的条件下
A
A
A 和
D
D
D 是条件独立的，可得
P
(
D
∣
A
,
B
,
C
)
=
P
(
A
,
D
∣
B
,
C
)
P
(
A
∣
B
,
C
)
=
P
(
A
∣
B
,
C
)
P
(
D
∣
B
,
C
)
P
(
A
∣
B
,
C
)
=
P
(
D
∣
B
,
C
)
\begin{aligned} P(D \mid A, B, C) &=\frac{P(A, D \mid B, C)}{P(A \mid B, C)}=\frac{P(A \mid B, C) P(D \mid B, C)}{P(A \mid B, C)} \\ &=P(D \mid B, C) \end{aligned}
P(D∣A,B,C)=P(A∣B,C)P(A,D∣B,C)=P(A∣B,C)P(A∣B,C)P(D∣B,C)=P(D∣B,C)
由式 (6.1) 和式 (6.2) 可得联合概率
P
(
A
,
B
,
C
,
D
)
=
P
(
A
)
P
(
B
∣
A
)
P
(
C
∣
A
,
B
)
P
(
D
∣
A
,
B
,
C
)
=
P
(
A
)
P
(
B
∣
A
)
P
(
C
∣
A
)
P
(
D
∣
B
,
C
)
\begin{aligned} P(A, B, C, D) &=P(A) P(B \mid A) P(C \mid A, B) P(D \mid A, B, C) \\ &=P(A) P(B \mid A) P(C \mid A) P(D \mid B, C) \end{aligned}
P(A,B,C,D)=P(A)P(B∣A)P(C∣A,B)P(D∣A,B,C)=P(A)P(B∣A)P(C∣A)P(D∣B,C)
问题2：能否写出图 6.1 ( b）中马尔科夫网络的联合概率分布？
分析与解答
在马尔可夫网络中，联合概率分布的定义为
P
(
x
)
=
1
Z
∏
Q
∈
C
φ
Q
(
x
Q
)
P(x)=\frac{1}{Z} \prod_{Q \in C} \varphi_{Q}\left(x_{Q}\right)
P(x)=Z1Q∈C∏φQ(xQ)
其中
C
C
C 为图中最大团所构成的集合,
Z
=
∑
x
∏
Q
∈
C
φ
Q
(
x
Q
)
Z=\sum_{x} \prod_{Q \in C}\varphi_{Q}\left(x_{Q}\right)
Z=∑x∏Q∈CφQ(xQ) 为归一化因子，用来保证
P
(
x
)
P(x)
P(x) 是被正确定义的概率，
φ
Q
\varphi_{Q}
φQ 是与团
Q
Q
Q 对应的势函数。势函数是 非负的，并且应该在概率较大的变量上取得较大的值，例如指数函数
φ
Q
(
x
Q
)
=
e
−
H
Q
(
x
Q
)
\varphi_{Q}\left(x_{Q}\right)=\mathrm{e}^{-H_{Q}\left(x_{Q}\right)}
φQ(xQ)=e−HQ(xQ)
其中
H
Q
(
x
Q
)
=
∑
u
,
v
∈
Q
,
u
≠
v
α
u
,
v
x
u
x
v
+
∑
v
∈
Q
β
v
x
v
H_{Q}\left(x_{Q}\right)=\sum_{u, v \in Q, u \neq v} \alpha_{u, v} x_{u} x_{v}+\sum_{v \in Q} \beta_{v} x_{v}
HQ(xQ)=u,v∈Q,u=v∑αu,vxuxv+v∈Q∑βvxv
对于图中所有节点
x
=
{
x
1
,
x
2
,
…
,
x
n
}
x=\left\{x_{1}, x_{2}, \ldots, x_{n}\right\}
x={x1,x2,…,xn} 所构成的一个子集，如果在这个子集中，任意两点之间都存在边相连，则这个子集中的所有节点构成了一个团。如果在这个子集中加入任意其他节点，都不能构成一个团，则称这样的子集构成了一个最大团。在图 6.1 所示的网络结构中, 可以看到
(
A
,
B
)
,
(
A
,
C
)
,
(
B
,
D
)
,
(
C
,
D
)
(A, B),(A, C),(B, D),(C, D)
(A,B),(A,C),(B,D),(C,D)均构成团，同时也是最大团。因此联合概率分布可以表示为
P
(
A
,
B
,
C
,
D
)
=
1
Z
φ
1
(
A
,
B
)
φ
2
(
A
,
C
)
φ
3
(
B
,
D
)
φ
4
(
C
,
D
)
P(A, B, C, D)=\frac{1}{Z} \varphi_{1}(A, B) \varphi_{2}(A, C) \varphi_{3}(B, D) \varphi_{4}(C, D)
P(A,B,C,D)=Z1φ1(A,B)φ2(A,C)φ3(B,D)φ4(C,D)
如果采用式（ 6.5 ) 定义的指数函数作为势函数，则有
H
(
A
,
B
,
C
,
D
)
=
α
1
A
B
+
α
2
A
C
+
α
3
B
D
+
α
4
C
D
+
β
1
A
+
β
2
B
+
β
3
C
+
β
4
D
H(A, B, C, D)=\alpha_{1} A B+\alpha_{2} A C+\alpha_{3} B D+\alpha_{4} C D+\beta_{1} A+\beta_{2} B+\beta_{3} C+\beta_{4} D
H(A,B,C,D)=α1AB+α2AC+α3BD+α4CD+β1A+β2B+β3C+β4D
于是,
P
(
A
,
B
,
C
,
D
)
=
1
Z
e
−
H
(
A
,
B
,
C
,
D
)
P(A, B, C, D)=\frac{1}{Z} \mathrm{e}^{-H(A, B, C, D)}
P(A,B,C,D)=Z1e−H(A,B,C,D)
02：概率图表示
场景描述
上一节考查了面试者通过概率图还原模型联合概率分布的能力，本小节反其道而行之，考查面试者能否给出模型的慨率图表示。
知识点：朴素贝叶斯模型，概率图，最大熵模型
问题1：解释朴素贝肘斯模型的原理，并给出概率图模型表示？
分析与解答
朴素贝叶斯模型通过预测指定样本属于特定类别的概率
P
(
y
i
∣
x
)
P\left(y_{i} \mid x\right)
P(yi∣x) 来
预测该样本的所属类别，即
y
=
max
y
i
P
(
y
i
∣
x
)
y=\max _{y_{i}} P\left(y_{i} \mid x\right)
y=yimaxP(yi∣x)
P
(
y
i
∣
x
)
P\left(y_{i} \mid x\right)
P(yi∣x) 可以写成
P
(
y
i
∣
x
)
=
P
(
x
∣
y
i
)
P
(
y
i
)
P
(
x
)
P\left(y_{i} \mid x\right)=\frac{P\left(x \mid y_{i}\right) P\left(y_{i}\right)}{P(x)}
P(yi∣x)=P(x)P(x∣yi)P(yi)
其中
x
=
(
x
1
,
x
2
,
…
,
x
n
)
x=\left(x_{1}, x_{2}, \ldots, x_{n}\right)
x=(x1,x2,…,xn) 为样本对应的特征向量,
P
(
x
)
P(x)
P(x) 为样本的先验概率。对于特定的样本
x
x
x 和任意类别
y
i
,
P
(
x
)
y_{i},P(x)
yi,P(x) 的取值均相同，并不会影响
P
(
y
i
∣
x
)
P\left(y_{i} \mid x\right)
P(yi∣x) 取值的相对大小，因此在计算中可以被忽略。假设特征
x
1
,
x
2
,
…
,
x
n
x_{1}, x_{2}, \ldots, x_{n}
x1,x2,…,xn 相互独立，可以得到 :
P
(
y
i
∣
x
)
∝
P
(
x
∣
y
i
)
P
(
y
i
)
=
P
(
x
1
∣
y
i
)
P
(
x
2
∣
y
i
)
⋯
P
(
x
n
∣
y
i
)
P
(
y
i
)
P\left(y_{i} \mid x\right) \propto P\left(x \mid y_{i}\right) P\left(y_{i}\right)=P\left(x_{1} \mid y_{i}\right) P\left(x_{2} \mid y_{i}\right) \cdots P\left(x_{n} \mid y_{i}\right) P\left(y_{i}\right)
P(yi∣x)∝P(x∣yi)P(yi)=P(x1∣yi)P(x2∣yi)⋯P(xn∣yi)P(yi)
其中
P
(
x
1
∣
y
i
)
,
P
(
x
2
∣
y
i
)
,
…
,
P
(
x
n
∣
y
i
)
,
P\left(x_{1} \mid y_{i}\right), P\left(x_{2} \mid y_{i}\right), \ldots, P\left(x_{n} \mid y_{i}\right),
P(x1∣yi),P(x2∣yi),…,P(xn∣yi), 以及
P
(
y
i
)
P\left(y_{i}\right)
P(yi) 可以通过训练样本统计得到。可以看到后验概率
P
(
x
j
∣
y
i
)
P\left(x_{j} \mid y_{i}\right)
P(xj∣yi) 的取值决定了分类的结果，并且任意特征
x
j
x_{j}
xj 都由
y
i
y_{i}
yi 的取值所影响。因此概率图模型可以用图 6.2 表示。
注意，图 6.2 的表示为盘式记法。盘式记法是一种简洁的概率图模型表示方法, 如果变量
y
y
y 同时对
x
1
,
x
2
,
…
,
x
N
x_{1}, x_{2}, \ldots, x_{N}
x1,x2,…,xN 这
N
N
N 个变量产生影响，则可以简记成图 6.2 的形式 。
问题2：解释最大精模型的原理，并绘出概率图模型表示。
信息是指人们对事物理解的不确定性的降低或消除，而嫡就是不确定性的度量，嫡越大，不确定性也就越大。最大嫡原理是概率模型学习的一个准则，指导思想是在满足约束条件的模型集合中选取嫡最大的模型，即不确定性最大的模型。在平时生活中，我们也会有意无意地使用最大嫡的准则，例如人们常说的鸡蛋不能放在一个篮子里，就是指在事情具有不确定性的时候，我们倾向于尝试它的多种可能性，从而降低结果的风险。同时，在摸清了事情背后的某种规律之后，可以加入一个约束，将不符合规律约束的情况排除，在剩下的可能性中去寻找使得嫡最大的决策。
假设离散随机变量
x
x
x 的分布是
P
(
x
)
,
P(x),
P(x), 则关于分布
P
P
P 的嫡定义为
H
(
P
)
=
−
∑
x
P
(
x
)
log
P
(
x
)
H(P)=-\sum_{x} P(x) \log P(x)
H(P)=−x∑P(x)logP(x)
可以看出当
x
x
x 服从均匀分布时对应的嫡最大，也就是不确定性最高。
给定离散随机变量
x
x
x 和
y
y
y 上的条件概率分布
P
(
y
∣
x
)
,
P(y \mid x),
P(y∣x), 定义在条件概率分布上的条件嫡为
H
(
P
)
=
−
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
log
P
(
y
∣
x
)
H(P)=-\sum_{x, y} \tilde{P}(x) P(y \mid x) \log P(y \mid x)
H(P)=−x,y∑P~(x)P(y∣x)logP(y∣x)
其中
P
~
(
x
)
\tilde{P}(x)
P~(x) 为样本在训练数据集上的经验分布，即
x
x
x 的各个取值在样本中出现的频率统计。
最大嫡模型就是要学习到合适的分布
P
(
y
∣
x
)
,
P(y \mid x),
P(y∣x), 使得条件嫡
H
(
P
)
H(P)
H(P) 的取值最大。在对训练数据集一无所知的情况下，最大嫡模型认为
P
(
y
∣
x
)
P(y \mid x)
P(y∣x)是符合均匀分布的。那么当我们有了训练数据集之后呢？我们希望从中找到一些规律，从而消除一些不确定性，这时就需要用到特征函数
f
(
x
,
y
)
f(x, y)
f(x,y) 。特征函数
f
f
f 描述了输入
x
x
x 和输出
y
y
y 之间的一个规律, 例如当
x
=
y
x=y
x=y 时
f
(
x
,
y
)
f(x, y)
f(x,y) 等于一个比较大的正数。为了使学习到的模型
P
(
y
∣
x
)
P(y \mid x)
P(y∣x) 能够正确捕捉训练数据集中的这一规律（特征
）
,
）,
）, 我们加入一个约束，使得特征函数
f
(
x
,
y
)
f(x, y)
f(x,y) 关于经验分布
P
~
(
x
,
y
)
\tilde{P}(x, y)
P~(x,y) 的期望值与关于模型
P
(
y
∣
x
)
P(y \mid x)
P(y∣x) 和经验分布
P
~
(
x
)
\tilde{P}(x)
P~(x) 的期望值相等，即
E
p
~
(
f
)
=
E
P
(
f
)
E_{\tilde{p}}(f)=E_{P}(f)
Ep~(f)=EP(f)
其中，特征函数
f
(
x
,
y
)
f(x, y)
f(x,y) 关于经验分布
P
~
(
x
,
y
)
\tilde{P}(x, y)
P~(x,y) 的期望值计算公式为
E
p
ˉ
(
f
)
=
∑
x
,
y
P
~
(
x
,
y
)
f
(
x
,
y
)
E_{\bar{p}}(f)=\sum_{x, y} \tilde{P}(x, y) f(x, y)
Epˉ(f)=x,y∑P~(x,y)f(x,y)
f
(
x
,
y
)
f(x, y)
f(x,y) 关于模型
P
(
y
∣
x
)
P(y \mid x)
P(y∣x) 和经验分布
P
~
(
x
)
\tilde{P}(x)
P~(x) 的期望值计算公式为
E
P
(
f
)
=
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
f
(
x
,
y
)
E_{P}(f)=\sum_{x, y} \tilde{P}(x) P(y \mid x) f(x, y)
EP(f)=x,y∑P~(x)P(y∣x)f(x,y)
综上，给定训练数据集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
N
,
y
N
)
}
,
T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\},
T={(x1,y1),(x2,y2),…,(xN,yN)}, 以及M 个特征函数
{
f
i
(
x
,
y
)
,
i
=
1
,
2
,
…
,
M
}
,
\left\{f_{i}(x, y), i=1,2, \ldots, M\right\},
{fi(x,y),i=1,2,…,M}, 最大嫡模型的学习等价于约束最优化问题：
max
P
H
(
P
)
=
−
∑
x
,
y
P
~
(
x
)
P
(
y
∣
x
)
log
P
(
y
∣
x
)
s.t.,
E
p
~
(
f
i
)
=
E
P
(
f
i
)
,
∀
i
=
1
,
2
,
…
,
M
∑
y
P
(
y
∣
x
)
=
1
\begin{array}{l} \max _{P} H(P)=-\sum_{x, y} \tilde{P}(x) P(y \mid x) \log P(y \mid x) \\ \text { s.t., } E_{\tilde{p}}\left(f_{i}\right)=E_{P}\left(f_{i}\right), \forall i=1,2, \ldots, M \\ \quad \sum_{y} P(y \mid x)=1 \end{array}
maxPH(P)=−∑x,yP~(x)P(y∣x)logP(y∣x) s.t., Ep~(fi)=EP(fi),∀i=1,2,…,M∑yP(y∣x)=1
求解之后可以得到最大嫡模型的表达形式为
P
w
(
y
∣
x
)
=
1
Z
exp
(
∑
i
=
1
M
w
i
f
i
(
x
,
y
)
)
P_{w}(y \mid x)=\frac{1}{Z} \exp \left(\sum_{i=1}^{M} w_{i} f_{i}(x, y)\right)
Pw(y∣x)=Z1exp(i=1∑Mwifi(x,y))
最终，最大嫡模型归结为学习最佳的参数
w
,
w,
w, 使得
P
w
(
y
∣
x
)
P_{w}(y \mid x)
Pw(y∣x) 最大化。
从概率图模型的角度理解，我们可以看到
P
w
(
y
∣
x
)
P_{w}(y \mid x)
Pw(y∣x) 的表达形式非常类似于势函数为指数函数的马尔可夫网络，其中变量
x
x
x 和
y
y
y 构成了一个最大团，如图 6.3 所示。
03：生成式模型与判别式模型
场景描述
生成式模型和判别式模型的区别是机器学习领域非常重要的基础知识，也是经常用来考察面试者的面试题，但能准确区分开二者并不是一件非常容易的事情。
知识点：生成式模型，判别式模型
问题1：常见的概率图模型中，哪些是生成式模型，哪些是判剧式模型？
分析与解答
要想正确回答这个问题首先要弄清楚生成式模型和判别式模型的区别。假设可观测到的变量集合为
X
,
X,
X, 需要预测的变量集合为
Y
,
Y,
Y, 其他的变量集合为
Z
∘
Z_{\circ}
Z∘ 生成式模型是对联合概率分布
P
(
X
,
Y
,
Z
)
P(X, Y, Z)
P(X,Y,Z) 进行建模,
在给定观测集合
X
X
X 的条件下，通过计算边缘分布来得到对变量集合
Y
Y
Y的推断，即
P
(
Y
∣
X
)
=
P
(
X
,
Y
)
P
(
X
)
=
∑
Z
P
(
X
,
Y
,
Z
)
∑
Y
,
Z
P
(
X
,
Y
,
Z
)
P(Y \mid X)=\frac{P(X, Y)}{P(X)}=\frac{\sum_{Z} P(X, Y, Z)}{\sum_{Y, Z} P(X, Y, Z)}
P(Y∣X)=P(X)P(X,Y)=∑Y,ZP(X,Y,Z)∑ZP(X,Y,Z)
判别式模型是直接对条件概率分布
P
(
Y
,
Z
∣
X
)
P(Y, Z \mid X)
P(Y,Z∣X) 进行建模，然后消掉无关变量
Z
Z
Z 就可以得到对变量集合
Y
Y
Y 的预测，即
P
(
Y
∣
X
)
=
∑
Z
P
(
Y
,
Z
∣
X
)
P(Y \mid X)=\sum_{Z} P(Y, Z \mid X)
P(Y∣X)=Z∑P(Y,Z∣X)
常见的概率图模型有朴素贝叶斯、最大嫡模型、贝叶斯网络、隐马尔可夫模型、条件随机场、pLSA、LDA 等。基于前面的问题解答,我们知道朴素贝叶斯、贝早斯网络、pLSA、LDA 等模型都是先对联合概率分布进行建模，然后再通过计算边缘分布得到对变量的预测，所以它们都属于生成式模型; 而最大嫡模型是直接对条件概率分布进行建模，因此属于判别式模型。隐马尔可夫模型和条件随机场模型是对序列数据进行建模的方法，将在后面的章节中详细介绍，其中隐马尔可夫模型属于生成式模型，条件随机场属于判别式模型。
04：马尔可夫模型
场景描述
在介绍隐马尔可夫模型之前，先简单了解马尔可夫过程。马尔可夫过程是满足无后效
性的随机过程。假设一个随机过程中，
t
n
t_{n}
tn 时刻的状态
x
n
x_{n}
xn 的条件分布，仅仅与其前一个状态
x
n
−
1
x_{n-1}
xn−1 有关, 即
P
(
x
n
∣
x
1
,
x
2
⋯
x
n
−
1
)
=
P
(
x
n
∣
x
n
−
1
)
,
P\left(x_{n} \mid x_{1}, x_{2} \cdots x_{n-1}\right)=P\left(x_{n} \mid x_{n-1}\right),
P(xn∣x1,x2⋯xn−1)=P(xn∣xn−1), 则将其称为马尔可夫过程，时间和状态的取值都是离散的马尔可夫过程也称为马尔可夫链，如图 6.4 所示。
隐马尔可夫模型是对含有未知参数（隐状态
）
）
） 的马尔可夫链进行建模的生成模型，概率图模型如图 6.5 所示。在简单的马尔可夫模型中，所有状态对于观测者都是可见的,因此在马尔可夫模型中仅仅包括状态间的转移概率。而在隐马尔可夫模型中，隐状态
x
i
x_{i}
xi对于观测者而言是不可见的，观测者能观测到的只有每个隐状态
x
i
x_{i}
xi 对应的输出
y
i
,
y_{i},
yi, 而观测状态
y
i
y_{i}
yi 的概率分布仅仅取决于对应的隐状态
x
i
∘
x_{i} \circ
xi∘ 在隐马尔可夫模型中，参数包括了隐状态间的转移概率、隐状态到观测状态的输出概率、隐状态
x
x
x 的取值空间、观测状态
y
y
y 的取值空间以及初始状态的概率分布。
知识点：马尔可夫模型，隐马尔可夫模型
问题1：如何对中文词问题用隐马尔可夫模型进行建模和训练？
分析与解答
下面用一个简单的例子来说明隐马尔可夫模型的建模过程。假设有 3 个不同的胡芦，每个甜芦里有好药和坏药若干，现在从 3个胡芦中按以下规则倒出药来。
（1）随机挑选一个胡芦。
（2) 从胡芦里倒出一颗药，记录是好药还是坏药后将药放回。
（3）从当前胡芦依照一定的概率转移到下一个胡芦。
（4 ) 重复步骤（2 ）和（3）。
在整个过程中，我们并不知道每次拿到的是哪一个胡芦。用隐马尔可夫模型来描述以上过程，隐状态就是当前是哪一个胡芦，隐状态的取值空间为
{
\{
{ 胡芦
1
,
1,
1, 胡芦
2
,
2,
2, 胡芦 3
}
,
\},
}, 观测状态的取值空间为
{
\{
{ 好药,坏药
}
,
\},
}, 初始状态的概率分布就是第 ( 1 ) 步随机挑选胡芦的概率分布，隐状态间的转移概率就是从当前胡芦转移到下一个胡芦的概率，而隐状态到观测状态的输出概率就是每个胡芦里好药和坏药的概率。记录下来的药的顺序就是观测状态的序列，而每次拿到的胡芦的顺序就是隐状态的序列。
隐马尔可夫模型包括概率计算问题、预测问题、学习问题三个基本问题。
（ 1 ) 概率计算问题：已知模型的所有参数，计算观测序列
Y
Y
Y 出现
的概率，可使用前向和后向算法求解。
（2 ) 预测问题：已知模型所有参数和观测序列
Y
,
Y,
Y, 计算最可能的隐状态序列
X
,
X,
X, 可使用经典的动态规划算法一一维特比算法来求解最可能的状态序列。
（3 ) 学习问题：已知观测序列
Y
,
Y,
Y, 求解使得该观测序列概率最大的模型参数，包括隐状态序列、隐状态之间的转移概率分布以及从隐状态到观测状态的概率分布，可使用 Baum-Welch 算法进行参数的学习, Baum-Welch 算法是最大期望算法的一个特例。
上面提到的问题和算法在此不多做介绍，感兴趣的读者可以查阅相关资料。下面回到开头的问题。隐马尔可夫模型通常用来解决序列标注问题，因此也可以将分词问题转化为一个序列标注问题来进行建模。例如可以对中文句子中的每个字做以下标注， B B B 表示一个词开头的第一个字， E E E 表示一个词结尾的最后一个字， M M M 表示一个词中间的字， S S S 表示一个单字词，则隐状态的取值空间为 { B , E , M , S } ∘ \{B, E, M, S\} \circ {B,E,M,S}∘ 同时对隐状态的转移概率可以给出一些先验知识， B B B 和 M M M 后面只能是 M M M 或者 E , S E, S E,S 和 E E E 后面只能是 B B B 或者 S ∘ S_{\circ} S∘ 而每个字就是模型中的观测状态 , , ,取值空间为语料中的所有中文字。完成建模之后，使用语料进行训练可以分有监督训练和无监督训练。有监督训练即对语料进行标注，相当于根据经验得到了语料的所有隐状态信息，然后就可以用简单的计数法来对模型中的概率分布进行极大似然估计 。无监督训练可以用上文提到的 Baum-Welch 算法，同时优化隐状态序列和模型对应的概率分布。
问题2：最大熵马尔可夫模型为什么会产生标注偏置问题？如何解决？
分析与解答：
隐马尔可夫模型等用于解决序列标注问题的模型中，常常对标注进行了独立性假设。以隐马尔可夫模型为例介绍标注偏置问题（Label Bias Problem）。
在隐马尔可夫模型中，假设隐状态（即序列标注问题中的标注）x_i的状态满足马尔可夫过程，
t
t
t 时刻的状态
x
i
x_{i}
xi 的条件分布，仅仅与其前一个状态
x
t
−
1
x_{t-1}
xt−1 有关, 即
P
(
x
i
∣
x
1
,
x
2
,
…
,
x
t
−
1
)
=
P
(
x
i
∣
x
t
−
1
)
;
P\left(x_{i} \mid x_{1}, x_{2}, \ldots, x_{t-1}\right)=P\left(x_{i} \mid x_{t-1}\right) ;
P(xi∣x1,x2,…,xt−1)=P(xi∣xt−1); 同时隐马尔可夫模型假设观测序列中各个状态仅仅取决于它对应的隐状态
P
(
y
t
∣
x
1
,
x
2
,
…
,
x
n
,
y
i
,
P\left(y_{t} \mid x_{1}, x_{2}, \ldots, x_{n}, y_{i},\right.
P(yt∣x1,x2,…,xn,yi,
y
2
,
…
,
y
t
−
1
,
y
t
+
1
,
…
)
=
P
(
y
t
∣
x
i
)
∘
\left.y_{2}, \ldots, y_{t-1}, y_{t+1}, \ldots\right)=P\left(y_{t} \mid x_{i}\right) \circ
y2,…,yt−1,yt+1,…)=P(yt∣xi)∘ 隐马尔可夫模型建模时考虑了隐状态间的转移概率和隐状态到观测状态的输出概率。
实际上，在序列标注问题中，隐状态（标注 ) 不仅和单个观测状态相关，还和观察序列的长度、上下文等信息相关。例如词性标注问题中,个词被标注为动词还是名词，不仅与它本身以及它前一个词的标注有关,还依赖于上下文中的其他词，于是引出了最大嫡马尔可夫模型（Maximum Entropy Markov Model, MEMM )， 如图 6.6 所示。最大嫡马尔可夫模型在建模时，去除了隐马尔可夫模型中观测状态相互独立的假设, 考虑了整个观测序列，因此获得了更强的表达能力。同时，隐马尔可夫模型是:种对隐状态序列和观测状态序列的联合概率
P
(
x
,
y
)
P(x, y)
P(x,y) 进行建模的生成式模型,而最大嫡马尔可夫模型是直接对标注的后验概率
P
(
y
∣
x
)
P(y \mid x)
P(y∣x) 进行建模的判别式模型。
最大嫡马尔可夫模型建模如下
p
(
x
1
⋯
n
∣
y
1
⋯
n
)
=
∏
i
=
1
n
p
(
x
i
∣
x
i
−
1
,
y
1
⋯
n
)
p\left(x_{1 \cdots n} \mid y_{1 \cdots n}\right)=\prod_{i=1}^{n} p\left(x_{i} \mid x_{i-1}, y_{1 \cdots n}\right)
p(x1⋯n∣y1⋯n)=i=1∏np(xi∣xi−1,y1⋯n)
其中
p
(
x
i
∣
x
i
−
1
,
y
1
…
n
)
p\left(x_{i} \mid x_{i-1}, y_{1} \ldots_{n}\right)
p(xi∣xi−1,y1…n) 会在局部进行归一化，即枚举
x
i
x_{i}
xi 的全部取值进行求
和之后计算概率，计算公式为
p
(
x
i
∣
x
i
−
1
,
y
1
⋯
n
)
=
exp
(
F
(
x
i
,
x
i
−
1
,
y
1
…
n
)
)
Z
(
x
i
−
1
,
y
1
…
n
)
p\left(x_{i} \mid x_{i-1}, y_{1 \cdots n}\right)=\frac{\exp \left(F\left(x_{i}, x_{i-1}, y_{1} \ldots_{n}\right)\right)}{Z\left(x_{i-1}, y_{1} \ldots_{n}\right)}
p(xi∣xi−1,y1⋯n)=Z(xi−1,y1…n)exp(F(xi,xi−1,y1…n))
其中
Z
Z
Z 为归一化因子
Z
(
x
i
−
1
,
y
1
⋯
n
)
=
∑
x
i
exp
(
F
(
x
i
,
x
i
−
1
,
y
1
⋯
n
)
)
Z\left(x_{i-1}, y_{1 \cdots n}\right)=\sum_{x_{i}} \exp \left(F\left(x_{i}, x_{i-1}, y_{1 \cdots n}\right)\right)
Z(xi−1,y1⋯n)=xi∑exp(F(xi,xi−1,y1⋯n))
其中
F
(
x
i
,
x
i
−
1
,
y
1
,
…
n
)
F\left(x_{i}, x_{i-1}, y_{1}, \ldots_{n}\right)
F(xi,xi−1,y1,…n) 为
x
i
,
x
i
−
1
,
y
1
…
n
x_{i}, x_{i-1}, y_{1} \ldots_{n}
xi,xi−1,y1…n 所有特征的线性叠加。
最大嫡马尔可夫模型存在标注偏置问题，如图 6.7 所示。可以发现，状态 1 倾向于转移到状态
2
,
2,
2, 状态 2 倾向于转移到状态 2 本身。但是实际计算得到的最大概率路径是
1
−
>
1
−
>
1
−
>
1
,
1->1->1->1,
1−>1−>1−>1, 状态 1 并没有转移到状态2, 如图 6.8 所示。这是因为，从状态 2 转移出去可能的状态包括
1
、
2
、
3
、
4
、
5
1、2、3、4、5
1、2、3、4、5 概率在可能的状态上分散了，而状态 1 转移出去的可能状态仅仅为状态 1 和 2 ， 概率更加集中 。由于局部一化的影响，隐状态会倾向于转移到那些后续状态可能更少的状态上 ， 以提高整体的后验概率 。这就是标注偏置问题 。
条件随机场（ Conditional Random Field, CRF ）在最大熵马尔可夫模型的基础上，进行了全局归一化，如图 6.9 所示 。
条件随机场建模如下
p
(
x
1
⋯
n
∣
y
1
⋯
n
)
=
1
Z
(
y
1
⋯
n
)
∏
i
=
1
n
exp
(
F
(
x
i
,
x
i
−
1
,
y
1
⋯
n
)
)
p\left(x_{1 \cdots n} \mid y_{1 \cdots n}\right)=\frac{1}{Z\left(y_{1} \cdots_{n}\right)} \prod_{i=1}^{n} \exp \left(F\left(x_{i}, x_{i-1}, y_{1 \cdots n}\right)\right)
p(x1⋯n∣y1⋯n)=Z(y1⋯n)1i=1∏nexp(F(xi,xi−1,y1⋯n))
其中归一化因子
Z
(
y
1
…
n
)
Z\left(y_{1} \ldots n\right)
Z(y1…n) 是在全局范围进行归一化，枚举了整个隐状态序列
x
1
…
n
x_{1} \ldots n
x1…n 的全部可能，从而解决了局部归一化带来的标注偏置问题。
05：主题模型
场景描述
基于词袋模型或
N
\mathrm{N}
N -gram 模型的文本表示模型有一个明显的缺陷，就是无法识别出两个不同的词或词组具有相同的主题。因此，需要一种技术能够将具有相同主题的词或词组映射到同一维度上去，于是产生了主题模型。主题模型是一种特殊的概率图模型。想象一下我们如何判定两个不同的词具有相同的主题呢? 这两个词可能有更高的概率同时出现在同一篇文档中; 换句话说，给定某一主题，这两个词的产生概率都是比较高的，而另一些不太相关的词汇产生的概率则是较低的。假设有
K
K
K 个主题，我们就把任意文章表示成一个
K
K
K 维的主题向量，其中向量的每一维代表一个主题，权重代表这篇文章属于这个特定主题的概率。主题模型所解决的事情，就是从文本库中发现有代表性的主题（得到每个主题上面词的分布）,并且计算出每篇文章对应着哪些主题。
知识点：pLSA ( Probabilistic Latent Semantic Analysis) , LDA ( Latent Dirichlet Allocation)
问题1：常见的主题模型苟明即说介绍其原理。
-
pLSA
pLSA是用一个生成模型采建模文章的生成过程 。 假设高 K个主题，M篇文章， 对语料库中的任意文章 d d d，假设该文章奇 N个词，则对于真中的每一个词，我们首先选择一个主题 z，然后在当前主题的基础上生成一个词 w w w。 国 6.1 0 是 pLSA 图模型。
生成主题 z z z 和词 w w w 的过程遵照一个确定的概率分布。设在文章 d d d 中生成主题 z z z 的概 率 为 p ( z ∣ d ) , p(z \mid d), p(z∣d), 在选定主题的条件下生成词 w w w 的概 率 为 p ( w ∣ z ) , p(w \mid z), p(w∣z), 则给 定文章 d , d, d, 生成词 w w w 的概率可以写成:
p ( w ∣ d ) = ∑ z p ( w ∣ z , d ) p ( z ∣ d ) 。 p(w \mid d)=\sum_{z} p(w \mid z, d) p(z \mid d) 。 p(w∣d)=∑zp(w∣z,d)p(z∣d)。 在这里我们做一个简化，假设给定主题 z z z 的条件下，生成词 w w w 的概率是与特定的文章无关的，则公式可以简化为 : p ( w ∣ d ) = ∑ z p ( w ∣ z ) p ( z ∣ d ) 。 : p(w \mid d)=\sum_{z} p(w \mid z) p(z \mid d) 。 :p(w∣d)=∑zp(w∣z)p(z∣d)。 整个语料库中的文本生成概率可以用 似然函数表示为
L = ∏ m M ∏ n N p ( d m , w n ) c ( d m , w n ) L=\prod_{m}^{M} \prod_{n}^{N} p\left(d_{m}, w_{n}\right)^{c\left(d_{m}, w_{n}\right)} L=m∏Mn∏Np(dm,wn)c(dm,wn)
于是，Log 似然函数可以写成：
l = ∑ m M ∑ n N c ( d m , w n ) log p ( d m , w n ) = ∑ m M ∑ n N c ( d m , w n ) log ∑ k K p ( d m ) p ( z k ∣ d m ) p ( w n ∣ z k ) \begin{aligned} l &=\sum_{m}^{M} \sum_{n}^{N} c\left(d_{m}, w_{n}\right) \log p\left(d_{m}, w_{n}\right) \\ &=\sum_{m}^{M} \sum_{n}^{N} c\left(d_{m}, w_{n}\right) \log \sum_{k}^{K} p\left(d_{m}\right) p\left(z_{k} \mid d_{m}\right) p\left(w_{n} \mid z_{k}\right) \end{aligned} l=m∑Mn∑Nc(dm,wn)logp(dm,wn)=m∑Mn∑Nc(dm,wn)logk∑Kp(dm)p(zk∣dm)p(wn∣zk)
在上面的公式中，定义在文章上的主题分布 p ( z k ∣ d m ) p\left(z_{k} \mid d_{m}\right) p(zk∣dm) 和定义在主题上的词分布 p ( w n ∣ z k ) p\left(w_{n} \mid z_{k}\right) p(wn∣zk) 是待估计的参数。我们需要找到最优的参数，使得整个语料库的 Log 似然函数最大化。由于参数中包含的 z k z_{k} zk 是隐含变量（即无法直接观测到的变量 )，因此无法用最大似然估计直接求解，可以利用最大期望算法来解决。 -
LDA
LDA 可以看作是 pLSA 的贝早斯版本，其文本生成过程与 pLSA基本相同，不同的是为主题分布和词分布分别加了两个狄利克雷（Dirichlet ) 先验。为什么要加入狄利克雷先验呢？这就要从频率学派和贝叶斯学派的区别说起。pLSA 采用的是频率派思想，将每篇文章对应的主题分布 p ( z k ∣ d m ) p\left(z_{k} \mid d_{m}\right) p(zk∣dm) 和每个主题对应的词分布 p ( w n ∣ z k ) p\left(w_{n} \mid z_{k}\right) p(wn∣zk) 看成确定的未知常数，并可以求解出来; 而 LDA 采用的是贝叶斯学派的思想，认为待估计的参数（主题分布和词分布 ） ） ） 不再是一个固定的常数，而是服从一定分布的随机变量。这个分布符合一定的先验概率分布（即狄利克雷分布），并且在观察到样本信息之后，可以对先验分布进行修正，从而得到后验分布。LDA 之所以选择狄利克雷分布作为先验分布，是因为它为多项式分布的共轭先验概率分布，后验概率依然服从狄利克雷分布，这样做可以为计算带来便利。图 6.11 是 LDA 的图模型，其中 α \alpha α, β \beta β 分别为两个狄利克雷分布的超参数，为人工设定。
语料库的生成过程为：对文本库中的每一篇文档 d i , d_{i}, di, 采用以下操作
(1) 从超参数为 α \alpha α 的狄利克雷分布中抽样生成文档 d i d_{i} di 的主题分
布 θ i ∘ \theta_{i^{\circ}} θi∘
（2) 对文档 d i d_{i} di 中的每一个词进行以下 3 个操作。 -
从代表主题的多项式分布 θ i \theta_{i} θi 中抽样生成它所对应的主题 z i j ∘ z_{i j} \circ zij∘
-
从超参数为 β \beta β 的狄利克雷分布中抽样生成主题 z i j z_{i j} zij 对应的词分布 ψ z y ∘ \psi_{z_{y}^{\circ}} ψzy∘ 从代表词的多项式分布 ψ z y \psi_{z_{y}} ψzy 中抽样生成词 w i j w_{i j} wij
我们要求解出主题分布 θ i \theta_{i} θi 以及词分布 ψ z i j \psi_{z_{i j}} ψzij 的期望，可以用吉布斯采样（Gibbs Sampling ) 的方式实现。首先随机给定每个单词的主题，然后在其他变量固定的情况下，根据转移概率抽样生成每个单词的新主题。对于每个单词来说，转移概率可以理解为：给定文章中的所有单词以及除自身以外其他所有单词的主题，在此条件下该单词对应为各个新主题的概率。最后，经过反复迭代，我们可以根据收敛后的采样结果计算主题分布和词分布的期望 。
问题2：如何确定 LDA 模型中的主题个数？
分析与解答
在 LDA 中，主题的个数
K
K
K 是一个预先指定的超参数。对于模型超参数的选择，实践中的做法一般是将全部数据集分成训练集、验证集、和测试集 3 部分，然后利用验证集对超参数进行选择。例如，在确定LDA 的主题个数时，我们可以随机选取
60
%
60 \%
60% 的文档组成训练集，另外
20
%
20 \%
20% 的文档组成验证集，剩下
20
%
20 \%
20% 的文档组成测试集。在训练时，尝试多组超参数的取值，并在验证集上检验哪一组超参数所对应的模型取得了最好的效果。最终，在验证集上效果最好的一组超参数和其对应的模型将被选定，并在测试集上进行测试。为了衡量 LDA 模型在验证集和测试集上的效果，需要寻找一个合适的评估指标。一个常用的评估指标是困惑度（perplexity
）
）
） 。在文档集合
D
D
D 上，模型的困惑度被定义为
perplexity
(
D
)
=
exp
{
−
∑
d
=
1
M
log
p
(
w
d
)
∑
d
=
1
M
N
d
}
\operatorname{perplexity}(D)=\exp \left\{-\frac{\sum_{d=1}^{M} \log p\left(\boldsymbol{w}_{d}\right)}{\sum_{d=1}^{M} N_{d}}\right\}
perplexity(D)=exp{−∑d=1MNd∑d=1Mlogp(wd)}
其中
M
M
M 为文档的总数
,
w
d
, w_{d}
,wd 为文档
d
d
d 中单词所组成的词袋向量,
p
(
w
d
)
p\left(w_{d}\right)
p(wd) 为模型所预测的文档
d
d
d 的生成概率
,
N
d
, N_{d}
,Nd 为文档
d
d
d 中单词的总数。
一开始，随着主题个数的增多，模型在训练集和验证集的困惑度呈下降趋势，但是当主题数目足够大的时候，会出现过拟合，导致困惑度指标在训练集上继续下降但在验证集上反而增长。这时，可以取验证集的困惑度极小值点所对应的主题个数作为超参数。在实践中，困惑度的极小值点可能出现在主题数目非常大的时候，然而实际应用并不能承受如此大的主题数目，这时就需要在实际应用中合理的主题数目范围内进行选择，比如选择合理范围内困惑度的下降明显变慢（抛点 ) 的时候。
另外一种 方法是在 LDA 基础之上融入分层狄利克雷过程（ Hierarchical Dirichlet Process, HDP ) , 构成一种非参数主题模型 H D P − L D A \mathrm{HDP}-\mathrm{LDA} HDP−LDA 。非参数主题模型的好处是不需要预先指定主题的个数，模型可以随着文档数目的变化而自动对主题个数进行调整; 它的缺点是在 LDA 基础上融入 HDP 之后使得整个概率图模型更加复杂，训练速度也更加缓慢，因此在实际应用中还是经常采用第一种方法确定合适的主题数目。
问题3：如何用主题模型解决推荐系统中的冷启动问题？
分析与解答：
首先对题目做进一步的解释。推荐系统中的冷启动问题是指在没有大量用户数据的情况下如何给用户进行个性化推荐，目的是最优化点击率、转化率或用户体验（用户停留时间、留存率等
）
）
） 。冷启动问题一般分为用户冷启动、物品冷启动和系统冷启动三大类。用户冷启动是指对一个之前没有行为或行为极少的新用户进行推荐; 物品冷启动是指为一个新上市的商品或电影（这时没有与之相关的评分或用户行为数据
）
）
） 寻找到具有潜在兴趣的用户; 系统冷启动是指如何为一个新开发的网站设计个性化推荐系统。
解决冷启动问题的方法一般是基于内容的推荐。以 Hulu 的场景为例，对于用户冷启动来说，我们希望根据用户的注册信息（如：年龄、性别、爱好等 ）、搜索关键词或者合法站外得到的其他信息（例如用户使用 Facebook 胀号登录，并得到授权，可以得到 Facebook 中的朋友关系和评论内容 ) 来推测用户的兴趣主题。得到用户的兴趣主题之后，我们就可以找到与该用户兴趣主题相同的其他用户，通过他们的历史行为来预测用户感兴趣的电影是什么。同样地，对于物品冷启动问题，我们也可以根据电影的导演、演员、类别、关键词等信息推测该电影所属于的主题，然后基于主题向量找到相似的电影，并将新电影推荐给以往喜欢看这些相似电影的用户。可以使用主题模型（pLSA、LDA 等 ） ） ）得到用户和电影的主题。以用户为例，我们将每个用户看作主题模型中的一篇文档，用户对应的特征作为文档中的单词，这样每个用户可以表示成一袋子特征的形式。通过主题模型学习之后，经常共同出现的特征将会对应同一个主题，同时每个用户也会相应地得到一个主题分布。每个电影的主题分布也可以用类似的方法得到。
那么如何解决系统冷启动问题呢？ 首先可以得到每个用户和电影对应的主题向量，除此之外，还需要知道用户主题和电影主题之间的偏好程度，也就是哪些主题的用户可能喜欢哪些主题的电影。当系统中没有任何数据时，我们需要一些先验知识来指定，并且由于主题的数目通常比较小，随着系统的上线，收集到少量的数据之后我们就可以对主题之间的偏好程度得到一个比较准确的估计。