基于模型的机器学习与近似推断
一、基于模型的机器学习
近年来，许多机器学习的算法不断增长，但是机器学习算法的选择往往通过不断尝试来选取，效率低下。基于模型的机器学习旨在为每个问题提供定制化的解决方案。它将模型分解为模型结构+推断算法，对于前一部分依赖于问题的假设，对不同问题有不同的结构，而后一部分则是通用的。这样的处理使得我们可以构建一个统一的框架，快速便捷的对特定问题提供适合的机器学习算法。
- 模型结构：模型假设的集合，即模型中变量的类型以及个数，变量与变量之间的相互影响关系。
- 推断算法：用以计算模型某些变量的后验分布。
二、模型结构
如果我们考虑所有变量之间全部两两相关，他们的联合分布几乎无法处理，为此这里只考虑一些具有特殊结构的模型。基于上述关于模型的陈述，我们可以使用概率图模型很好的刻画：
变量—节点
关系—边
有向无环图（有向图）
模型假设定义了两个变量之间的因果关系，表示为
| 符号 | 说明 |
|---|---|
| V \mathcal{V} V | 图中所有节点的集合 |
| x i \mathbf{x}_i xi? | 第 i i i个节点代表的变量 |
| Π i \Pi_i Πi? | 第 i i i个节点的父节点代表的变量的集合 |
| $ | \mathcal{V} |
利用Bayes定理，我们可以利用因子分解将变量的联合概率密度表示为
p
(
x
1
,
x
2
,
?
?
,
x
∣
V
∣
)
=
∏
i
∈
V
p
(
x
i
∣
Π
i
)
(3.1)
p(\mathbf{x}_1, \mathbf{x}_2, \cdots, \mathbf{x}_{|\mathcal{V}|})=\prod\limits_{i\in\mathcal{V}}p(\mathbf{x}_i|\Pi_i)\tag{3.1}
p(x1?,x2?,?,x∣V∣?)=i∈V∏?p(xi?∣Πi?)(3.1)
有向图也被称为Bayes网络。
无向图
若两个变量之间不存在“因果关系”，可用无向图表示
无向图模型同样有类似于因子分解的技巧，即最大团分解。团指是一个关于节点的集合，这个集合中的节点之间相互连通。最大团指无法加入新的节点使得其仍为一个团的团。
| 符号 | 说明 |
|---|---|
| X c \mathcal{X}_c Xc? | 某一个最大团 |
| C \mathcal{C} C | 最大团的全体的下标的集合 |
| ψ \psi ψ | 势函数 |
于是有
p
(
x
1
,
x
2
,
?
?
,
x
∣
V
∣
)
=
1
Z
∏
c
∈
C
ψ
(
X
c
)
,
(3.2)
p(\mathbf{x}_1, \mathbf{x}_2, \cdots, \mathbf{x}_{|\mathcal{V}|})=\frac{1}{Z}\prod\limits_{c\in\mathcal{C}}\psi(\mathcal{X}_c), \tag{3.2}
p(x1?,x2?,?,x∣V∣?)=Z1?c∈C∏?ψ(Xc?),(3.2)
其中
Z
Z
Z为归一化常数。
图模型与经典机器学习算法的联系
许多的机器学习算法可以使用概率图模型的结构进行表示，如PCA以及GMM
三、近似推断
推断分为精确推断与近似推断两个主要类别，精确推断的方法主要有变量消除法（VE）、信念传播算法（BP）以及联合树算法，近似推断则主要包括确定性推断以及随机推断两种，确定性推断的代表是变分推断，随机推断则主要依赖于Monte Carlo方法。对于许多问题精确推断存在难以获取一个解析形式或形式太过于复杂难以数值实现等等困境，这是我们要么进一步加强假设以降低复杂度，要么考虑采用近似推断来近似处理。
Far better an approximate answer to the right question, which is often vague, than an exact answer to the wrong answer, which can always be made precise
我们主要考虑近似推断中的确定性推断算法，将主要介绍两种推断算法Variational Inference(VI)和Expectation Propagation(EP)。
变分推断
- 目标：构造一个后验分布的确定性的解析近似分布。
- 内容：在某个给定的分布族 Q \mathcal{Q} Q中依据某个标准 D D D搜寻最优近似分布 q ? q^* q?。
证据下界（ELBO）
若定义上述标准为KL散度，则有
q
?
(
z
∣
X
)
=
arg
?
min
?
q
∈
Q
D
K
L
(
q
(
z
∣
X
)
∥
p
(
z
∣
X
)
)
,
(3.3)
q^*(\mathbf{z}\mid\mathbf{X})=\mathop{\arg\min}\limits_{q\in\mathcal{Q}}D_{KL}(q(\mathbf{z}\mid\mathbf{X})\|p(\mathbf{z}\mid\mathbf{X})), \tag{3.3}
q?(z∣X)=q∈Qargmin?DKL?(q(z∣X)∥p(z∣X)),(3.3)
其中
D
K
L
(
q
∥
p
)
=
∫
q
(
?
)
log
?
q
(
?
)
p
(
?
)
d
?
(3.4)
D_{K L}(q \| p)=\int q(\epsilon) \log \frac{q(\epsilon)}{p(\epsilon)} d \epsilon \tag{3.4}
DKL?(q∥p)=∫q(?)logp(?)q(?)?d?(3.4)
直接最小化KL散度是不现实的，因为我们不知道真实的后验分布
p
(
z
∣
X
)
p(\mathbf{z}|\mathbf{X})
p(z∣X)，因而我们需要进行一些变形
D
K
L
(
q
(
z
∣
X
)
∥
p
(
z
∣
X
)
)
)
=
∫
q
(
z
∣
X
)
log
?
(
q
(
z
∣
X
)
p
(
z
∣
X
)
)
d
z
=
?
∫
q
(
z
∣
X
)
log
?
(
p
(
x
,
z
)
p
(
x
)
q
(
z
∣
X
)
)
d
z
=
?
(
∫
q
(
z
∣
X
)
log
?
(
p
(
x
,
z
)
q
(
z
∣
X
)
)
d
z
?
∫
q
(
z
∣
X
)
log
?
p
(
x
)
d
z
)
=
?
∫
q
(
z
∣
X
)
log
?
(
p
(
x
,
z
)
q
(
z
∣
X
)
)
d
z
+
log
?
p
(
x
)
∫
q
(
z
∣
X
)
d
z
=
?
E
q
[
log
?
(
p
(
x
,
z
)
q
(
z
∣
X
)
)
]
+
log
?
p
(
x
)
(3.5)
\begin{aligned} \left.D_{K L}(q(\mathbf{z} \mid \mathbf{X}) \| p(\mathbf{z} \mid \mathbf{X}))\right) &=\int q(\mathbf{z} \mid \mathbf{X}) \log \left(\frac{q(\mathbf{z} \mid \mathbf{X})}{p(\mathbf{z} \mid \mathbf{X})}\right) d \mathbf{z} \\ &=-\int q(\mathbf{z} \mid \mathbf{X}) \log \left(\frac{p(\mathbf{x}, \mathbf{z})}{p(\mathbf{x}) q(\mathbf{z} \mid \mathbf{X})}\right) d \mathbf{z} \\ &=-\left(\int q(\mathbf{z} \mid \mathbf{X}) \log \left(\frac{p(\mathbf{x}, \mathbf{z})}{q(\mathbf{z} \mid \mathbf{X})}\right) d \mathbf{z}-\int q(\mathbf{z} \mid \mathbf{X}) \log p(\mathbf{x}) d \mathbf{z}\right) \\ &=-\int q(\mathbf{z} \mid \mathbf{X}) \log \left(\frac{p(\mathbf{x}, \mathbf{z})}{q(\mathbf{z} \mid \mathbf{X})}\right) d \mathbf{z}+\log p(\mathbf{x}) \int q(\mathbf{z} \mid \mathbf{X}) d \mathbf{z} \\ &=-\mathbb{E}_{q}\left[\log \left(\frac{p(\mathbf{x}, \mathbf{z})}{q(\mathbf{z} \mid \mathbf{X})}\right)\right]+\log p(\mathbf{x}) \end{aligned}\tag{3.5}
DKL?(q(z∣X)∥p(z∣X)))?=∫q(z∣X)log(p(z∣X)q(z∣X)?)dz=?∫q(z∣X)log(p(x)q(z∣X)p(x,z)?)dz=?(∫q(z∣X)log(q(z∣X)p(x,z)?)dz?∫q(z∣X)logp(x)dz)=?∫q(z∣X)log(q(z∣X)p(x,z)?)dz+logp(x)∫q(z∣X)dz=?Eq?[log(q(z∣X)p(x,z)?)]+logp(x)?(3.5)
根据(3.5)我们有
log
?
p
(
x
)
=
D
K
L
(
q
(
z
∣
X
)
∥
p
(
z
∣
X
)
)
)
+
E
q
[
log
?
(
p
(
x
,
z
)
q
(
z
∣
X
)
)
]
(3.6)
\log p(\mathbf{x}) =\left.D_{K L}(q(\mathbf{z} \mid \mathbf{X}) \| p(\mathbf{z} \mid \mathbf{X}))\right) + \mathbb{E}_{q}\left[\log \left(\frac{p(\mathbf{x}, \mathbf{z})}{q(\mathbf{z} \mid \mathbf{X})}\right)\right] \tag{3.6}
logp(x)=DKL?(q(z∣X)∥p(z∣X)))+Eq?[log(q(z∣X)p(x,z)?)](3.6)
其中
E
q
[
log
?
(
p
(
x
,
z
)
q
(
z
∣
X
)
)
]
\mathbb{E}_{q}\left[\log \left(\frac{p(\mathbf{x}, \mathbf{z})}{q(\mathbf{z} \mid \mathbf{X})}\right)\right]
Eq?[log(q(z∣X)p(x,z)?)]即为证据下界（ELBO），最小化KL散度等价于最大化ELBO。
对数联合概率分布
log
?
p
(
z
,
X
)
\log p(\mathbf{z},\mathbf{X})
logp(z,X)可以分解为对数似然
log
?
p
(
x
∣
Z
)
\log p(\mathbf{x}\mid \mathbf{Z})
logp(x∣Z)和对数先验
log
?
p
(
z
)
\log p(\mathbf{z})
logp(z)，即
log
?
p
(
z
,
X
)
=
log
?
p
(
x
∣
Z
)
+
log
?
p
(
z
)
\log p(\mathbf{z},\mathbf{X})=\log p(\mathbf{x}\mid \mathbf{Z})+\log p(\mathbf{z})
logp(z,X)=logp(x∣Z)+logp(z)。于是我们可以将ELBO改写成更加易于实现的形式
ELBO
?
(
q
)
=
E
q
[
log
?
p
(
x
,
z
)
]
?
E
q
[
log
?
q
(
z
∣
X
)
]
=
E
q
[
log
?
p
(
x
∣
Z
)
+
log
?
p
(
z
)
]
?
E
q
[
log
?
q
(
z
∣
X
)
]
=
E
q
[
log
?
p
(
x
∣
Z
)
]
?
D
K
L
(
q
(
z
∣
X
)
∥
p
(
z
)
)
(3.8)
\begin{aligned} \operatorname{ELBO}(q) &=\mathbb{E}_{q}[\log p(\mathbf{x}, \mathbf{z})]-\mathbb{E}_{q}[\log q(\mathbf{z} \mid \mathbf{X})] \\ &=\mathbb{E}_{q}[\log p(\mathbf{x} \mid \mathbf{Z})+\log p(\mathbf{z})]-\mathbb{E}_{q}[\log q(\mathbf{z} \mid \mathbf{X})] \\ &=\mathbb{E}_{q}[\log p(\mathbf{x} \mid \mathbf{Z})]-D_{K L}(q(\mathbf{z} \mid \mathbf{X}) \| p(\mathbf{z})) \end{aligned}\tag{3.8}
ELBO(q)?=Eq?[logp(x,z)]?Eq?[logq(z∣X)]=Eq?[logp(x∣Z)+logp(z)]?Eq?[logq(z∣X)]=Eq?[logp(x∣Z)]?DKL?(q(z∣X)∥p(z))?(3.8)
通过(3.8)可以看出，最大化ELBO的过程即使得近似分布尽可能地解释数据，同时通过KL散度的正则化项惩罚偏离先验的结果。从信息论的角度来看，最大化ELBO即尽可能最大化保持原有数据的信息同时尽可能压缩数据的大小。
平均场近似
所有的推断算法均对近似分布族 Q \mathcal{Q} Q作某些假设加以限制，主要有两种方法：
-
确定分布族的参数化形式 q ( z ∣ X ; Ψ ) q(\mathbf{z}\mid \mathbf{X}; \Psi) q(z∣X;Ψ)，集合 Ψ \Psi Ψ为变分参数集合。
-
假设 q q q可以分解为
q ( z ∣ X ) = ∏ i = 1 M q i ( z S i ∣ X ) (3.16) q(\mathbf{z}\mid \mathbf{X})=\prod\limits_{i=1}^{M}q_i(\mathbf{z}_{\mathcal{S}_i}\mid \mathbf{X}) \tag{3.16} q(z∣X)=i=1∏M?qi?(zSi??∣X)(3.16)
其中 ? Z S i = Z \bigcup\mathcal{Z}_{\mathcal{S}_i}=\mathcal{Z} ?ZSi??=Z.
如(3.16)所示的形式的近似后验称为平均场变分推断（MFVI）。我们对每一个 q i q_i qi?都去找它的最优的近似分布 q i ? q^*_i qi??然后形如(3.16)获取到 q q q的局部最优近似分布 q ? q^* q?。平均场近似使得我们能够去获取任意隐变量的边际密度，但是它对隐变量之间的独立性假设限制了它的适用范围。
Coordinate Ascent Variational Inference(CAVI)
CAVI属于MFVI的一种算法，用以寻找最优的 q i ? ( z S i ∣ X ) q^{*}_i(\mathbf{z}_{\mathcal{S}_i}\mid \mathbf{X}) qi??(zSi??∣X)。
根据平均场近似，我们有
q
(
z
∣
X
)
=
∏
i
=
1
M
q
i
(
z
S
i
∣
X
)
(A.4)
q(\mathbf{z} \mid \mathbf{X})=\prod_{i=1}^{M} q_{i}\left(\mathbf{z}_{\mathcal{S}_{i}} \mid \mathbf{X}\right) \tag{A.4}
q(z∣X)=i=1∏M?qi?(zSi??∣X)(A.4)
E L B O ( q ) = E q [ log ? p ( x , z ) ] ? E q [ log ? q ( z ∣ X ) ] (A.5) \mathrm{ELBO}(q)=\mathbb{E}_{q}[\log p(\mathbf{x}, \mathbf{z})]-\mathbb{E}_{q}[\log q(\mathbf{z} \mid \mathbf{X})] \tag{A.5} ELBO(q)=Eq?[logp(x,z)]?Eq?[logq(z∣X)](A.5)
将(A.4)代入到(A.5)中，
ELBO
?
(
q
)
=
∫
(
∏
i
q
i
)
log
?
p
(
x
,
z
)
d
z
?
∫
(
∏
l
q
l
)
log
?
∏
k
q
k
d
z
=
∫
q
j
[
∫
log
?
p
(
x
,
z
)
∏
?
j
(
q
i
d
z
i
)
]
d
z
j
?
∑
k
∫
∏
l
q
l
log
?
q
k
d
z
=
∫
q
j
E
?
j
[
log
?
p
(
x
,
z
)
]
d
z
j
?
∑
k
∫
q
k
log
?
q
k
[
∏
l
≠
k
∫
q
l
d
z
l
]
d
z
k
,
(A.6)
\begin{aligned} \operatorname{ELBO}(q) &=\int\left(\prod_{i} q_{i}\right) \log p(\mathbf{x}, \mathbf{z}) d \mathbf{z}-\int\left(\prod_{l} q_{l}\right) \log \prod_{k} q_{k} d \mathbf{z} \\ &=\int q_{j}\left[\int \log p(\mathbf{x}, \mathbf{z}) \prod_{-j}\left(q_{i} d z_{i}\right)\right] d z_{j}-\sum_{k} \int \prod_{l} q_{l} \log q_{k} d \mathbf{z} \\ &=\int q_{j} \mathbb{E}_{-j}[\log p(\mathbf{x}, \mathbf{z})] d z_{j}-\sum_{k} \int q_{k} \log q_{k}\left[\prod_{l \neq k} \int q_{l} d z_{l}\right] d z_{k}, \end{aligned} \tag{A.6}
ELBO(q)?=∫(i∏?qi?)logp(x,z)dz?∫(l∏?ql?)logk∏?qk?dz=∫qj?[∫logp(x,z)?j∏?(qi?dzi?)]dzj??k∑?∫l∏?ql?logqk?dz=∫qj?E?j?[logp(x,z)]dzj??k∑?∫qk?logqk????l?=k∏?∫ql?dzl????dzk?,?(A.6)
由于
∫
q
l
d
z
l
=
1
\int q_ldz_l =1
∫ql?dzl?=1， 同时定义
p
~
?
j
=
E
?
j
[
log
?
p
(
x
,
z
)
]
+
c
\tilde{p}_{-j}=\mathbb{E}_{-j}\left[\log p(\mathbf{x}, \mathbf{z})\right]+c
p~??j?=E?j?[logp(x,z)]+c，其中常数
c
c
c用于归一化，于是(A.6)可以简化为
ELBO
?
(
q
)
=
∫
q
j
log
?
p
~
?
j
d
z
j
?
∑
k
∫
q
k
log
?
q
k
d
z
k
+
c
=
∫
q
j
log
?
p
~
?
j
d
z
j
?
∫
q
j
log
?
q
j
d
z
j
?
∑
k
≠
j
∫
q
k
log
?
q
k
d
z
k
+
c
=
∫
q
j
log
?
(
p
~
?
j
q
j
)
d
z
j
+
c
′
=
?
D
K
L
(
q
j
∥
p
~
?
j
)
+
c
′
(A.7)
\begin{aligned} \operatorname{ELBO}(q) &=\int q_{j} \log \widetilde{p}_{-j} d z_{j}-\sum_{k} \int q_{k} \log q_{k} d z_{k}+c \\ &=\int q_{j} \log \widetilde{p}_{-j} d z_{j}-\int q_{j} \log q_{j} d z_{j}-\sum_{k \neq j} \int q_{k} \log q_{k} d z_{k}+c \\ &=\int q_{j} \log \left(\frac{\widetilde{p}_{-j}}{q_{j}}\right) d z_{j}+c^{\prime} \\ &=-D_{K L}\left(q_{j} \| \tilde{p}_{-j}\right)+c^{\prime} \end{aligned} \tag{A.7}
ELBO(q)?=∫qj?logp
??j?dzj??k∑?∫qk?logqk?dzk?+c=∫qj?logp
??j?dzj??∫qj?logqj?dzj??k?=j∑?∫qk?logqk?dzk?+c=∫qj?log(qj?p
??j??)dzj?+c′=?DKL?(qj?∥p~??j?)+c′?(A.7)
这里我们仅关注关于
q
j
q_j
qj?的ELBO的最大化，将其他的
q
?
j
q_{-j}
q?j?全部固定。此时，当ELBO最大时，
D
K
L
(
q
j
∥
p
~
?
j
)
=
0
D_{K L}\left(q_{j} \| \tilde{p}_{-j}\right)=0
DKL?(qj?∥p~??j?)=0，于是
log
?
q
j
?
(
z
S
j
∣
X
)
=
E
?
j
[
log
?
p
(
x
,
z
)
]
+
const
?
(3.17)
\log q_{j}^{*}\left(\mathbf{z}_{\mathcal{S}_{j}} \mid \mathbf{X}\right)=\mathbb{E}_{-j}[\log p(\mathbf{x}, \mathbf{z})]+\operatorname{const} \tag{3.17}
logqj??(zSj??∣X)=E?j?[logp(x,z)]+const(3.17)
q j ? ( z S j ∣ X ) ∝ exp ? { E ? j [ log ? p ( x , z ) ] } (3.18) q_{j}^{*}\left(\mathbf{z}_{\mathcal{S}_{j}} \mid \mathbf{X}\right) \propto \exp \left\{\mathbb{E}_{-j}[\log p(\mathbf{x}, \mathbf{z})]\right\} \tag{3.18} qj??(zSj??∣X)∝exp{E?j?[logp(x,z)]}(3.18)
根据(3.17)与(3.18)的结果，我们可以不断迭代更新最优分布直到收敛。CAVI最终得到是ELBO的一个局部最优解。
随机变分推断(SVI)
SVI最开始是用来计算完全分解的MFVI的，在后来被扩展应用到一般的VI模型中去。SVI在每一步迭代利用(3.18)计算期望时并不使用完整的 N N N个点，而是随机均匀的抽取 n n n个点计算期望。这种近似有效需要满足
- 梯度估计 g ^ \hat{g} g^?应该是无偏的 E [ g ^ ] = E [ g ] \mathbb{E}\left[\hat{g}\right]=\mathbb{E}\left[{g}\right] E[g^?]=E[g].
- 学习率序列需要满足 ∑ i = 0 ∞ α i = ∞ \sum_{i=0}^{\infty} \alpha_{i}=\infty ∑i=0∞?αi?=∞和 ∑ i = 0 ∞ α i 2 < ∞ \sum_{i=0}^{\infty} \alpha_{i}^{2}<\infty ∑i=0∞?αi2?<∞.
变分推断的缺陷
变分推断示例
见书44-46页，一维线性回归问题.
假设密度滤波
- 与变分推断的一个重要区别是采用了正向KL散度。
- 中心想法是将联合概率密度 p ( x , z ) p(\mathbf{x},\mathbf{z}) p(x,z)分解为相互独立的因子概率密度 p i ( z ) p_i(\mathbf{z}) pi?(z)的乘积。
依据ADF的基本想法，
p
(
x
,
z
)
=
∏
i
=
1
N
f
i
(
z
)
(3.30)
p(\mathbf{x}, \mathbf{z})=\prod_{i=1}^{N} f_{i}(\mathbf{z}) \tag{3.30}
p(x,z)=i=1∏N?fi?(z)(3.30)
p ( z ∣ X ) = 1 p ( x ) ∏ i = 1 N f i ( z ) (3.31) p(\mathbf{z} \mid \mathbf{X})=\frac{1}{p(\mathbf{x})} \prod_{i=1}^{N} f_{i}(\mathbf{z}) \tag{3.31} p(z∣X)=p(x)1?i=1∏N?fi?(z)(3.31)
需要注意是 f i f_i fi?与 x \mathbf{x} x存在隐性的相关性，在原始论文中 f i ( z ) = p ( x i ∣ Z ) f_i(\mathbf{z})=p(x_i\mid \mathbf{Z}) fi?(z)=p(xi?∣Z)。