3.1.1 第一个问题解法
遍历算法：
这个是最简单的算法了，假设第一天(T=1 时刻)是晴天，想要购物，那么就把图上的对应概率相乘就能够得到了。
第二天(T=2 时刻)要做的事情，在第一天的概率基础上乘上第二天的概率，依次类推，最终得到这三天(T=3 时刻)所要做的事情的概率值，这就是遍历算法，简单而又粗暴。但问题是用遍历算法的复杂度会随着观测序列和隐藏状态的增加而成指数级增长。
复杂度为： 2TNT ，于是就有了第二种算法
前向算法：
1. 假设第一天要购物，那么就计算出第一天购物的概率(包括晴天和雨天)；假设第一天要散步，那么也计算出来，依次枚举。
2. 假设前两天是购物和散步，也同样计算出这一种的概率；假设前两天是散步和打扫卫生，同样计算，枚举出前两天行为的概率。
3. 第三步就是计算出前三天行为的概率。
细心的读者已经发现了，第二步中要求的概率可以在第一步的基础上进行，同样的，第三步也会依赖于第二步的计算结果。那么这样做就能够节省很多计算环节，类似于动态规划。
这种算法的复杂度为： N2T
后向算法
跟前向算法相反，我们知道总的概率肯定是1，那么B_t=1，也就是最后一个时刻的概率合为1，先计算前三天的各种可能的概率，在计算前两天、前一天的数据，跟前向算法相反的计算路径。
3.1.2 第二个问题解法
维特比算法(Viterbi)
维特比算法是现代数字通信中最常用的算法，同时也是很多自然语言处理采用的解码算法。
维特比算法是一个特殊但应用最广的动态规划算法。利用动态规划，可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图—篱笆网络（Lattice）的有向图最短路径问题而提出的。它之所以重要，是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。
维特比算法一般用于模式识别，通过观测数据来反推出隐藏状态，下面一步步讲解这个算法。
因为是要根据观测数据来反推，所以这里要进行一个假设，假设这三天所做的行为分别是：散步、购物、打扫卫生，那么我们要求的是这三天的天气(路径)分别是什么。
1. 初始计算第一天下雨和第一天晴天去散步的概率值：
- Δ1(R) 表示第一天下雨的概率
- πR 表示中间的状态(下雨)s概率
- bR(O1=w) 表示下雨并且散步的概率
- aR−R 表示下雨天到下雨天的概率
初始路径为：
2. 计算第二天下雨和第二天晴天去购物的概率值：
对应路径为：
3. 计算第三天下雨和第三天晴天去打扫卫生的概率值：
对应路径为：
4. 比较每一步中 △ 的概率大小，选取最大值并找到对应的路径，依次类推就能找到最有可能的隐藏状态路径。
第一天的概率最大值为 Δ1S ，对应路径为Sunny，
第二天的概率最大值为 Δ2S ，对应路径为Sunny，
第三天的概率最大值为 Δ3R ，对应路径为Rainy。
5. 合起来的路径就是Sunny->Sunny->Rainy，这就是我们所求。
3.1.3 第三个问题解法
鲍姆-韦尔奇算法(Baum-Welch Algorithm) (约等于EM算法)
4.马尔可夫网络
我们已经知道，有向图模型，又称作贝叶斯网络，但在有些情况下，强制对某些结点之间的边增加方向是不合适的。使用没有方向的无向边，形成了无向图模型（Undirected Graphical Model,UGM）, 又被称为马尔可夫随机场或者马尔可夫网络（Markov Random Field, MRF or Markov network）。
设 X=(X1,X2,...,Xn) 和Y=(Y1,Y2,...,Yn)都是联合随机变量，若随机变量Y构成一个无向图 G=(V,E)表示的马尔可夫随机场（MRF），则条件概率分布P(Y|X)称为条件随机场（Conditional Random Field, 简称CRF。如下图所示，便是一个线性链条件随机场的无向图模型：
在概率图中，求某个变量的边缘分布是常见的问题。这问题有很多求解方法，其中之一就是把贝叶斯网络或马尔可夫随机场转换成因子图，然后用sum-product算法求解。换言之，基于因子图可以用sum-product 算法高效的求各个变量的边缘分布。
5.条件随机场(CRF)
一个通俗的例子
假设你有许多小明同学一天内不同时段的照片，从小明提裤子起床到脱裤子睡觉各个时间段都有（小明是照片控！）。现在的任务是对这些照片进行分类。比如有的照片是吃饭，那就给它打上吃饭的标签；有的照片是跑步时拍的，那就打上跑步的标签；有的照片是开会时拍的，那就打上开会的标签。问题来了，你准备怎么干？
一个简单直观的办法就是，不管这些照片之间的时间顺序，想办法训练出一个多元分类器。就是用一些打好标签的照片作为训练数据，训练出一个模型，直接根据照片的特征来分类。例如，如果照片是早上6:00拍的，且画面是黑暗的，那就给它打上睡觉的标签;如果照片上有车，那就给它打上开车的标签。
乍一看可以！但实际上，由于我们忽略了这些照片之间的时间顺序这一重要信息，我们的分类器会有缺陷的。举个例子，假如有一张小明闭着嘴的照片，怎么分类？显然难以直接判断，需要参考闭嘴之前的照片，如果之前的照片显示小明在吃饭，那这个闭嘴的照片很可能是小明在咀嚼食物准备下咽，可以给它打上吃饭的标签；如果之前的照片显示小明在唱歌，那这个闭嘴的照片很可能是小明唱歌瞬间的抓拍，可以给它打上唱歌的标签。
所以，为了让我们的分类器能够有更好的表现，在为一张照片分类时，我们必须将与它相邻的照片的标签信息考虑进来。这——就是条件随机场(CRF)大显身手的地方！这就有点类似于词性标注了，只不过把照片换成了句子而已，本质上是一样的。
如同马尔可夫随机场，条件随机场为具有无向的图模型，图中的顶点代表随机变量，顶点间的连线代表随机变量间的相依关系，在条件随机场中，随机变量Y 的分布为条件机率，给定的观察值则为随机变量 X。下图就是一个线性连条件随机场。
条件概率分布P(Y|X)称为条件随机场。
6.EM（最大期望算法）算法、HMM、CRF的比较
1. EM算法是用于含有隐变量模型的极大似然估计或者极大后验估计，有两步组成：E步，求期望（expectation）；M步，求极大（maxmization）。本质上EM算法还是一个迭代算法，通过不断用上一代参数对隐变量的估计来对当前变量进行计算，直到收敛。注意：EM算法是对初值敏感的，而且EM是不断求解下界的极大化逼近求解对数似然函数的极大化的算法，也就是说EM算法不能保证找到全局最优值。对于EM的导出方法也应该掌握。
2. 隐马尔可夫模型是用于标注问题的生成模型。有几个参数（π，A，B）：初始状态概率向量π，状态转移矩阵A，观测概率矩阵B。称为马尔科夫模型的三要素。马尔科夫三个基本问题：
- 概率计算问题：给定模型和观测序列，计算模型下观测序列输出的概率。–》前向后向算法
- 学习问题：已知观测序列，估计模型参数，即用极大似然估计来估计参数。–》Baum-Welch(也就是EM算法)和极大似然估计。
- 预测问题：已知模型和观测序列，求解对应的状态序列。–》近似算法（贪心算法）和维比特算法（动态规划求最优路径）
3. 条件随机场CRF，给定一组输入随机变量的条件下另一组输出随机变量的条件概率分布密度。条件随机场假设输出变量构成马尔科夫随机场，而我们平时看到的大多是线性链条随机场，也就是由输入对输出进行预测的判别模型。求解方法为极大似然估计或正则化的极大似然估计。
4. 之所以总把HMM和CRF进行比较，主要是因为CRF和HMM都利用了图的知识，但是CRF利用的是马尔科夫随机场（无向图），而HMM的基础是贝叶斯网络（有向图）。而且CRF也有：概率计算问题、学习问题和预测问题。大致计算方法和HMM类似，只不过不需要EM算法进行学习问题。
5. HMM和CRF对比：其根本还是在于基本的理念不同，一个是生成模型，一个是判别模型，这也就导致了求解方式的不同。
三、主题模型(Topic Model)
1.LDA模型是什么
LDA可以分为以下5个步骤：
- - 一个函数：gamma函数。
- - 四个分布：二项分布、多项分布、beta分布、Dirichlet分布。
- - 一个概念和一个理念：共轭先验和贝叶斯框架。
- - 两个模型：pLSA、LDA。
- - 一个采样：Gibbs采样
关于LDA有两种含义，一种是线性判别分析（Linear Discriminant Analysis），一种是概率主题模型：隐含狄利克雷分布（Latent Dirichlet Allocation，简称LDA），本文讲后者。
LDA是一种主题模型，它可以将文档集中每篇文档的主题以概率分布的形式给出，从而通过分析一些文档抽取出它们的主题（分布）出来后，便可以根据主题（分布）进行主题聚类或文本分类。同时，它是一种典型的词袋模型，即一篇文档是由一组词构成，词与词之间没有先后顺序的关系。此外，一篇文档可以包含多个主题，文档中每一个词都由其中的一个主题生成。
人类是怎么生成文档的呢？首先先列出几个主题，然后以一定的概率选择主题，以一定的概率选择这个主题包含的词汇，最终组合成一篇文章。如下图所示(其中不同颜色的词语分别对应上图中不同主题下的词)。
那么LDA就是跟这个反过来：根据给定的一篇文档，反推其主题分布。
在LDA模型中，一篇文档生成的方式如下：
- 从狄利克雷分布 α 中取样生成文档 i 的主题分布 θi 。
- 从主题的多项式分布θi中取样生成文档i第 j 个词的主题 zi,j 。
- 从狄利克雷分布 β 中取样生成主题zi,j对应的词语分布 ϕzi,j 。
- 从词语的多项式分布 ϕzi,j中采样最终生成词语 wi,j 。
其中，类似Beta分布是二项式分布的共轭先验概率分布，而狄利克雷分布（Dirichlet分布）是多项式分布的共轭先验概率分布。此外，LDA的图模型结构如下图所示（类似贝叶斯网络结构）：
1.1 5个分布的理解
先解释一下以上出现的概念。
1. 二项分布（Binomial distribution）
二项分布是从伯努利分布推进的。伯努利分布，又称两点分布或0-1分布，是一个离散型的随机分布，其中的随机变量只有两类取值，非正即负{+，-}。而二项分布即重复n次的伯努利试验，记为 X∼b(n,p) 。简言之，只做一次实验，是伯努利分布，重复做了n次，是二项分布。
2. 多项分布
是二项分布扩展到多维的情况。多项分布是指单次试验中的随机变量的取值不再是0-1的，而是有多种离散值可能（1,2,3...,k）。比如投掷6个面的骰子实验，N次实验结果服从K=6的多项分布。其中：
3. 共轭先验分布
在贝叶斯统计中，如果后验分布与先验分布属于同类，则先验分布与后验分布被称为共轭分布，而先验分布被称为似然函数的共轭先验。
4. Beta分布
二项分布的共轭先验分布。给定参数 α>0 和 β>0 ，取值范围为[0,1]的随机变量 x 的概率密度函数：
其中：
注：这便是所谓的gamma函数，下文会具体阐述。
5. 狄利克雷分布
是beta分布在高维度上的推广。Dirichlet分布的密度函数形式跟beta分布的密度函数如出一辙：
至此，我们可以看到二项分布和多项分布很相似，Beta分布和Dirichlet 分布很相似。
总之，可以得到以下几点信息。
- beta分布是二项式分布的共轭先验概率分布：对于非负实数 α 和 β ，我们有如下关系：
其中 (m1,m2) 对应的是二项分布 B(m1+m2,p) 的记数。针对于这种观测到的数据符合二项分布，参数的先验分布和后验分布都是Beta分布的情况，就是Beta-Binomial 共轭。
- 狄利克雷分布（Dirichlet分布）是多项式分布的共轭先验概率分布，一般表达式如下：
针对于这种观测到的数据符合多项分布，参数的先验分布和后验分布都是Dirichlet 分布的情况，就是 Dirichlet-Multinomial 共轭。
- 贝叶斯派思考问题的固定模式：
先验分布 π(θ) + 样本信息X = 后验分布 π(θ|x) 。
1.2 3个基础模型的理解
在讲LDA模型之前，再循序渐进理解基础模型：Unigram model、mixture of unigrams model，以及跟LDA最为接近的pLSA模型。为了方便描述，首先定义一些变量：
- w 表示词，V示所有单词的个数（固定值）。
- z 表示主题，k主题的个数（预先给定，固定值）。
- D=(W1,...,WM) 表示语料库，其中的M是语料库中的文档数（固定值）。
- W=(w1,w2,...,wN) 表示文档，其中的N表示一个文档中的词数（随机变量）。
1. Unigram model
对于文档 W=(w1,w2,...,wN) ，用 p(wn) 表示词 wn 的先验概率，生成文档w的概率为：
2. Mixture of unigrams model
该模型的生成过程是：给某个文档先选择一个主题z,再根据该主题生成文档，该文档中的所有词都来自一个主题。假设主题有 z1,...,zn ，生成文档w的概率为：
3. PLSA模型
理解了pLSA模型后，到LDA模型也就一步之遥——给pLSA加上贝叶斯框架，便是LDA。
在上面的Mixture of unigrams model中，我们假定一篇文档只有一个主题生成，可实际中，一篇文章往往有多个主题，只是这多个主题各自在文档中出现的概率大小不一样。比如介绍一个国家的文档中，往往会分别从教育、经济、交通等多个主题进行介绍。那么在pLSA中，文档是怎样被生成的呢？
假定你一共有K个可选的主题，有V个可选的词，咱们来玩一个扔骰子的游戏。
一、假设你每写一篇文档会制作一颗K面的“文档-主题”骰子（扔此骰子能得到K个主题中的任意一个），和K个V面的“主题-词项” 骰子（每个骰子对应一个主题，K个骰子对应之前的K个主题，且骰子的每一面对应要选择的词项，V个面对应着V个可选的词）。
比如可令K=3，即制作1个含有3个主题的“文档-主题”骰子，这3个主题可以是：教育、经济、交通。然后令V = 3，制作3个有着3面的“主题-词项”骰子，其中，教育主题骰子的3个面上的词可以是：大学、老师、课程，经济主题骰子的3个面上的词可以是：市场、企业、金融，交通主题骰子的3个面上的词可以是：高铁、汽车、飞机。
二、每写一个词，先扔该“文档-主题”骰子选择主题，得到主题的结果后，使用和主题结果对应的那颗“主题-词项”骰子，扔该骰子选择要写的词。
先扔“文档-主题”的骰子，假设（以一定的概率）得到的主题是教育，所以下一步便是扔教育主题筛子，（以一定的概率）得到教育主题筛子对应的某个词：大学。
上面这个投骰子产生词的过程简化下便是：“先以一定的概率选取主题，再以一定的概率选取词”。
三、最后，你不停的重复扔“文档-主题”骰子和”主题-词项“骰子，重复N次（产生N个词），完成一篇文档，重复这产生一篇文档的方法M次，则完成M篇文档。
上述过程抽象出来即是PLSA的文档生成模型。在这个过程中，我们并未关注词和词之间的出现顺序，所以pLSA是一种词袋方法。生成文档的整个过程便是选定文档生成主题，确定主题生成词。
反过来，既然文档已经产生，那么如何根据已经产生好的文档反推其主题呢？这个利用看到的文档推断其隐藏的主题（分布）的过程（其实也就是产生文档的逆过程），便是主题建模的目的：自动地发现文档集中的主题（分布）。
文档d和词w是我们得到的样本，可观测得到，所以对于任意一篇文档，其 P(wj|di) 是已知的。从而可以根据大量已知的文档-词项信息 P(wj|di)，训练出文档-主题 P(zk,di) 和主题-词项 P(wj,zk) ，如下公式所示：
由于 P(di) 可事先计算求出，而 P(wj|zk) 和P(zk,di)未知，所以 θ=(P(wj|zk),P(zk|di)) 就是我们要估计的参数（值），通俗点说，就是要最大化这个θ。
用什么方法进行估计呢，常用的参数估计方法有极大似然估计MLE、最大后验证估计MAP、贝叶斯估计等等。因为该待估计的参数中含有隐变量z，所以我们可以考虑EM算法。
1.3 LDA模型
事实上，理解了pLSA模型，也就差不多快理解了LDA模型，因为LDA就是在pLSA的基础上加层贝叶斯框架，即LDA就是pLSA的贝叶斯版本（正因为LDA被贝叶斯化了，所以才需要考虑历史先验知识，才加的两个先验参数）。
下面，咱们对比下本文开头所述的LDA模型中一篇文档生成的方式是怎样的：
- 按照先验概率 P(di) 选择一篇文档 di 。
- 从狄利克雷分布（即Dirichlet分布） α 中取样生成文档 di 的主题分布 θi ，换言之，主题分布 θi由超参数为 α的Dirichlet分布生成。
- 从主题的多项式分布θi 中取样生成文档 di第 j 个词的主题 zi,j 。
- 从狄利克雷分布（即Dirichlet分布） β 中取样生成主题 zi,j对应的词语分布 ϕzi,j ，换言之，词语分布 ϕzi,j由参数为 β的Dirichlet分布生成。
- 从词语的多项式分布ϕzi,j 中采样最终生成词语 wi,j 。
LDA中，选主题和选词依然都是两个随机的过程，依然可能是先从主题分布{教育：0.5，经济：0.3，交通：0.2}中抽取出主题：教育，然后再从该主题对应的词分布{大学：0.5，老师：0.3，课程：0.2}中抽取出词：大学。
那PLSA跟LDA的区别在于什么地方呢？区别就在于：
PLSA中，主题分布和词分布是唯一确定的，能明确的指出主题分布可能就是{教育：0.5，经济：0.3，交通：0.2}，词分布可能就是{大学：0.5，老师：0.3，课程：0.2}。
但在LDA中，主题分布和词分布不再唯一确定不变，即无法确切给出。例如主题分布可能是{教育：0.5，经济：0.3，交通：0.2}，也可能是{教育：0.6，经济：0.2，交通：0.2}，到底是哪个我们不再确定（即不知道），因为它是随机的可变化的。但再怎么变化，也依然服从一定的分布，即主题分布跟词分布由Dirichlet先验随机确定。正因为LDA是PLSA的贝叶斯版本，所以主题分布跟词分布本身由先验知识随机给定。
换言之，LDA在pLSA的基础上给这两参数 、(P(zk|di)、P(wj|zk))加了两个先验分布的参数（贝叶斯化）：一个主题分布的先验分布Dirichlet分布 α ，和一个词语分布的先验分布Dirichlet分布 β 。
综上，LDA真的只是pLSA的贝叶斯版本，文档生成后，两者都要根据文档去推断其主题分布和词语分布（即两者本质都是为了估计给定文档生成主题，给定主题生成词语的概率），只是用的参数推断方法不同，在pLSA中用极大似然估计的思想去推断两未知的固定参数，而LDA则把这两参数弄成随机变量，且加入dirichlet先验。
所以，pLSA跟LDA的本质区别就在于它们去估计未知参数所采用的思想不同，前者用的是频率派思想，后者用的是贝叶斯派思想。
LDA参数估计：Gibbs采样
2.怎么确定LDA的topic个数？
- 基于经验 主观判断、不断调试、操作性强、最为常用。
- 基于困惑度（主要是比较两个模型之间的好坏）。
- 使用Log-边际似然函数的方法，这种方法也挺常用的。
- 非参数方法：Teh提出的基于狄利克雷过程的HDP法。
- 基于主题之间的相似度：计算主题向量之间的余弦距离，KL距离等。
3.如何用主题模型解决推荐系统中的冷启动问题？
推荐系统中的冷启动问题是指在没有大量用户数据的情况下如何给用户进行个性化推荐，目的是最优化点击率、转化率或用户 体验（用户停留时间、留存率等）。冷启动问题一般分为用户冷启动、物品冷启动和系统冷启动三大类。
- 用户冷启动是指对一个之前没有行为或行为极少的新用户进行推荐；
- 物品冷启动是指为一个新上市的商品或电影（这时没有与之相关的 评分或用户行为数据）寻找到具有潜在兴趣的用户；
- 系统冷启动是指如何为一个 新开发的网站设计个性化推荐系统。
解决冷启动问题的方法一般是基于内容的推荐。以Hulu的场景为例，对于用户冷启动来说，我们希望根据用户的注册信息（如：年龄、性别、爱好等）、搜索关键词或者合法站外得到的其他信息（例如用户使用Facebook账号登录，并得到授权，可以得到Facebook中的朋友关系和评论内容）来推测用户的兴趣主题。得到用户的兴趣主题之后，我们就可以找到与该用户兴趣主题相同的其他用户， 通过他们的历史行为来预测用户感兴趣的电影是什么。
同样地，对于物品冷启动问题，我们也可以根据电影的导演、演员、类别、关键词等信息推测该电影所属于的主题，然后基于主题向量找到相似的电影，并将新电影推荐给以往喜欢看这 些相似电影的用户。可以使用主题模型（pLSA、LDA等）得到用户和电影的主题。
以用户为例，我们将每个用户看作主题模型中的一篇文档，用户对应的特征 作为文档中的单词，这样每个用户可以表示成一袋子特征的形式。通过主题模型 学习之后，经常共同出现的特征将会对应同一个主题，同时每个用户也会相应地 得到一个主题分布。每个电影的主题分布也可以用类似的方法得到。
那么如何解决系统冷启动问题呢？首先可以得到每个用户和电影对应的主题向量，除此之外，还需要知道用户主题和电影主题之间的偏好程度，也就是哪些主题的用户可能喜欢哪些主题的电影。当系统中没有任何数据时，我们需要一些先验知识来指定，并且由于主题的数目通常比较小，随着系统的上线，收集到少量的数据之后我们就可以对主题之间的偏好程度得到一个比较准确的估计。
参考：
