6. 概率图模型

Previous5. 非监督学习 Next7. 优化算法

Last updated 3 years ago

6. 概率图模型

节点：隐含节点（知识）、观测节点（数据）
边：有向边（Bayesian）、无向边（Markov）
模型：朴素贝叶斯，最大熵模型，隐马尔可夫 HMM，条件随机场 CRF，主题模型

6.1 概率图模型的联合概率分布 *

Bayesian Network $P(A,B,C,D)=P(A)P(B|A)P(C|A)P(D|B,C)$
Markov Network $P(A,B,C,D)=\frac1Z \phi_1(A,B)\phi_2(A,C)\phi_3(B,D)\phi_4(C,D)$
- $P(A,B,C,D)=\frac1Z e^{-H(A,B,C,D)}$ ，其中 $H(A,B,C,D)=\alpha_1AB+\alpha_2AC+\alpha_3BD+\alpha_4CD+\beta_1A+\beta_2B+\beta_3C+\beta_4D$

6.2 概率图表示 **

1. 朴素贝叶斯

预测样本属于特定类别的概率 $y=\max_{y_i} P(y_i|x)=\frac{P(x|y_i)P(y_i)}{P(x)}$
假设特征相互独立， $P(y_i|x)\propto 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)$

2. 最大熵模型

满足约束的模型中，选取熵最大的模型 $\max_P H(P)$ => $P_w(y|x)=\frac1Z exp(\sum_{i=1}^M w_i f_i(x,y))$
- 最大熵模型，归结为学习最佳的参数 w，使得 $P_w(y|x)$ 最大化
- 离散分布 $P(x)$ ： $H(P)=-\sum_x P(x)\log P(x)$
- 连续分布 $P(y|x)$ ： $H(P)=-\sum_{x,y} \tilde{P}(x) P(y|x) \log P(y|x)$

6.3 生成式模型与判别式模型 ***

观测变量 X，预测变量 Y，其他变量 Z
- 生成式模型： $P(Y|X)=\frac{P(X,Y)}{P(X)}=\frac{\sum_Z P(X,Y,Z)}{\sum_{Y,Z} P(X,Y,Z)}$
  - 对 联合概率分布 $P(X,Y,Z)$ 建模，计算边缘分布
  - 朴素贝叶斯、Bayesian Network、pLSA、LDA、HMM
- 判别式模型： $P(Y|X)=\sum_Z P(Y,Z|X)$
  - 直接对 条件概率分布 $P(Y,Z|X)$ 建模，然后消掉无关变量 Z
  - 最大熵模型、CRF

6.4 Markov 模型 ****

隐马尔可夫模型 HMM：序列标注问题，e.g. 分词 {Begin,End,Middle,Single} 有监督 / 无监督
- 概率计算问题：已知所有参数，计算观测序列 Y 出现的概率（前向 / 后向算法）
- 预测问题：已知所有参数和观测序列 Y，计算最可能的隐状态序列 X（Vertebi 动态规划）
- 学习问题：已知观测序列 Y，求解模型参数（Baum-Welch 算法 EM的特例）
标注偏置问题 Label Bias Problem
- 最大熵马尔可夫模型 MEMM
  - 去除 HMM 中观测状态相互独立的假设，考虑整个观测序列，表达能力更强
  - HMM - 生成式模型，MEMM - 判别式模型
  - $p(x_{1...n}|y_{1...n})=\prod_{i=1}^n p(x_i|x_{i-1},y_{1...n})$ ，其中 $p(x_i|x_{i-1},y_{1...n})=\frac{exp(F(x_i,x_{i-1},y_{1...n}))}{Z(x_{i-1},y_{1...n})}$
  - Z 为局部归一化因子， $Z(x_{i-1},y_{1...n})=\sum_{x_i}exp(F(x_i,x_{i-1},y_{1...n}))$
- 标注偏置问题：因为 局部归一化，隐状态倾向于转移到后续状态可能较少的状态上，以提高整体后验概率
- 条件随机场 CRF 在 MEMM 基础上，进行 全局归一化，解决局部归一化带来的标注偏置问题
  - $p(x_{1...n}|y_{1...n})=\frac{1}{Z(y_{1...n})}\prod_{i=1}^n exp(F(x_i,x_{i-1},y_{1...n}))$

6.5 主题模型 ***

1. 常见的主题模型 **

特殊的概率图模型，从文本库中发现有代表性的主题（词分布），并计算每篇文章对应哪些主题

pLSA（Probabilistic Latent Semantic Analysis）概率学派
- 文章 d (M)，主题 z (K)，词 w (N)： $p(w|d)=\sum_z p(w|z)p(z|d)$
- 文本生成概率似然函数 $L=\prod_m^M \prod_n^N p(d_m,w_n)^{c(d_m,w_n)}$
- 对数似然函数，EM 算法求解

LDA（Latent Dirichlet Allocation）贝叶斯学派
- pLSA 的贝叶斯版本，主题分布 / 词分布加入 Dirichlet 先验（ $\alpha, \beta$ 是超参数）
- 求解主题分布 $\theta_i$ 、词分布 $\Psi_{z_{ij}}$ 的期望，可以用 Gibbs Sampling（条件分布 <-> 联合分布）
  - 随机给定每个单词的主题，其他固定，根据转移概率抽样每个单词的新主题

2. 如何确定 LDA 主题数量 **

困惑度 $perplexity(D)=exp\{-\frac{\sum_{d=1}^M \log p(w_d)}{\sum_{d=1}^M N_d}\}$
60% train, 20% valid, 20% test，选择困惑度极小值点，或者下降变慢的时候
另一种方法：Hierarchical Dirichlet Process, HDP，非参数模型
- 不需要指定主题数量 K，可以自动调整
- 但概率图模型复杂，训练缓慢，不常用

3. 如何用主题模型解决推荐冷启动问题 ***

冷启动：基于内容的推荐
- 用户：注册信息、搜索关键词、其他信息，推测用户兴趣主题
- 物品：基本信息，推测电影主题
- 系统：用户主题 + 物品主题 + 先验知识（哪些主题的用户喜欢哪些主题的物品）

Previous5. 非监督学习 Next7. 优化算法

Last updated 3 years ago

节点：隐含节点（知识）、观测节点（数据）
边：有向边（Bayesian）、无向边（Markov）
模型：朴素贝叶斯，最大熵模型，隐马尔可夫 HMM，条件随机场 CRF，主题模型

6.1 概率图模型的联合概率分布 *

Bayesian Network $P(A,B,C,D)=P(A)P(B|A)P(C|A)P(D|B,C)$
Markov Network $P(A,B,C,D)=\frac1Z \phi_1(A,B)\phi_2(A,C)\phi_3(B,D)\phi_4(C,D)$
- $P(A,B,C,D)=\frac1Z e^{-H(A,B,C,D)}$ ，其中 $H(A,B,C,D)=\alpha_1AB+\alpha_2AC+\alpha_3BD+\alpha_4CD+\beta_1A+\beta_2B+\beta_3C+\beta_4D$

6.2 概率图表示 **

1. 朴素贝叶斯

预测样本属于特定类别的概率 $y=\max_{y_i} P(y_i|x)=\frac{P(x|y_i)P(y_i)}{P(x)}$
假设特征相互独立， $P(y_i|x)\propto 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)$

2. 最大熵模型

满足约束的模型中，选取熵最大的模型 $\max_P H(P)$ => $P_w(y|x)=\frac1Z exp(\sum_{i=1}^M w_i f_i(x,y))$
- 最大熵模型，归结为学习最佳的参数 w，使得 $P_w(y|x)$ 最大化
- 离散分布 $P(x)$ ： $H(P)=-\sum_x P(x)\log P(x)$
- 连续分布 $P(y|x)$ ： $H(P)=-\sum_{x,y} \tilde{P}(x) P(y|x) \log P(y|x)$

6.3 生成式模型与判别式模型 ***

观测变量 X，预测变量 Y，其他变量 Z
- 生成式模型： $P(Y|X)=\frac{P(X,Y)}{P(X)}=\frac{\sum_Z P(X,Y,Z)}{\sum_{Y,Z} P(X,Y,Z)}$
  - 对 联合概率分布 $P(X,Y,Z)$ 建模，计算边缘分布
  - 朴素贝叶斯、Bayesian Network、pLSA、LDA、HMM
- 判别式模型： $P(Y|X)=\sum_Z P(Y,Z|X)$
  - 直接对 条件概率分布 $P(Y,Z|X)$ 建模，然后消掉无关变量 Z
  - 最大熵模型、CRF

6.4 Markov 模型 ****

隐马尔可夫模型 HMM：序列标注问题，e.g. 分词 {Begin,End,Middle,Single} 有监督 / 无监督
- 概率计算问题：已知所有参数，计算观测序列 Y 出现的概率（前向 / 后向算法）
- 预测问题：已知所有参数和观测序列 Y，计算最可能的隐状态序列 X（Vertebi 动态规划）
- 学习问题：已知观测序列 Y，求解模型参数（Baum-Welch 算法 EM的特例）
标注偏置问题 Label Bias Problem
- 最大熵马尔可夫模型 MEMM
  - 去除 HMM 中观测状态相互独立的假设，考虑整个观测序列，表达能力更强
  - HMM - 生成式模型，MEMM - 判别式模型
  - $p(x_{1...n}|y_{1...n})=\prod_{i=1}^n p(x_i|x_{i-1},y_{1...n})$ ，其中 $p(x_i|x_{i-1},y_{1...n})=\frac{exp(F(x_i,x_{i-1},y_{1...n}))}{Z(x_{i-1},y_{1...n})}$
  - Z 为局部归一化因子， $Z(x_{i-1},y_{1...n})=\sum_{x_i}exp(F(x_i,x_{i-1},y_{1...n}))$
- 标注偏置问题：因为 局部归一化，隐状态倾向于转移到后续状态可能较少的状态上，以提高整体后验概率
- 条件随机场 CRF 在 MEMM 基础上，进行 全局归一化，解决局部归一化带来的标注偏置问题
  - $p(x_{1...n}|y_{1...n})=\frac{1}{Z(y_{1...n})}\prod_{i=1}^n exp(F(x_i,x_{i-1},y_{1...n}))$

6.5 主题模型 ***

1. 常见的主题模型 **

特殊的概率图模型，从文本库中发现有代表性的主题（词分布），并计算每篇文章对应哪些主题

pLSA（Probabilistic Latent Semantic Analysis）概率学派
- 文章 d (M)，主题 z (K)，词 w (N)： $p(w|d)=\sum_z p(w|z)p(z|d)$
- 文本生成概率似然函数 $L=\prod_m^M \prod_n^N p(d_m,w_n)^{c(d_m,w_n)}$
- 对数似然函数，EM 算法求解

LDA（Latent Dirichlet Allocation）贝叶斯学派
- pLSA 的贝叶斯版本，主题分布 / 词分布加入 Dirichlet 先验（ $\alpha, \beta$ 是超参数）
- 求解主题分布 $\theta_i$ 、词分布 $\Psi_{z_{ij}}$ 的期望，可以用 Gibbs Sampling（条件分布 <-> 联合分布）
  - 随机给定每个单词的主题，其他固定，根据转移概率抽样每个单词的新主题

2. 如何确定 LDA 主题数量 **

困惑度 $perplexity(D)=exp\{-\frac{\sum_{d=1}^M \log p(w_d)}{\sum_{d=1}^M N_d}\}$
60% train, 20% valid, 20% test，选择困惑度极小值点，或者下降变慢的时候
另一种方法：Hierarchical Dirichlet Process, HDP，非参数模型
- 不需要指定主题数量 K，可以自动调整
- 但概率图模型复杂，训练缓慢，不常用

3. 如何用主题模型解决推荐冷启动问题 ***

冷启动：基于内容的推荐
- 用户：注册信息、搜索关键词、其他信息，推测用户兴趣主题
- 物品：基本信息，推测电影主题
- 系统：用户主题 + 物品主题 + 先验知识（哪些主题的用户喜欢哪些主题的物品）