HMM

隐马尔可夫，隐，说明模型里面含有隐含节点，是我们所无法直接观测到的，这些隐含节点上的状态可以称为隐含状态；马尔科夫，说明模型具有马尔科夫性，一个节点的状态只跟它的邻居有关，与其他节点无关，与时间也无关。

我们把节点分为两类，状态节点（隐）和可观察节点（显）。并且假设状态节点为链式结构，每个输出（可观察节点）仅与当前状态有关。

因此我们有两个矩阵$A$和$B$,前者是状态转移概率矩阵$A_{i,j}$表示状态从$i$转移到$j$的概率，后者是生成概率矩阵$B_{i,j}$表示从状态$i$生成到观测值$j$的概率，加上初始状态概率向量$\pi$构成整个HMM模型参数集。

用法：

1）当整个模型的参数已知，给定观察序列$O$，我们可以求出其生成概率：

$$P(O|\lambda)=\sum_Q P(Q|\lambda)P(O|Q)~~~~~~~~~~~~（1）$$

其中$Q$是状态序列，即在所有状态序列下生成该观察序列概率之和。根据马尔科夫假设与两个概率矩阵我们可以计算出$P(Q|\lambda)$和$P(O|Q)$

具体计算方法可以用前向算法（一种动态规划）来计算。若我们有很多HMM模型，可以选择概率最大的那个作为最可能的模型。

2)当整个模型的参数已知，给定观察序列$O$，我们可以求出其对应最大概率的隐含状态序列：

$$Q=\max_Q P(Q|\lambda)P(O|Q)~~~~~~~~~~~~（2）$$

具体可用Viterbi算法（也是一种动态规划算法）计算，内部用了后向指针指明了隐含状态序列的路径，与最短路径算法Dijkstra类似。

广泛用在词性标注以及各种标注，词性序列看做隐含状态序列，找出最可能的标注序列。

3）估计HMM参数。当之给定观察序列，我们要训练出一个HMM模型，评估其参数$A$和$B$。由于HMM是一个生成模型，根据隐含状态生成观察序列，即$P(O|Q)$,这里我们要根据观察序列反推隐含状态，因此用到了贝叶斯公式。

我们的优化目标是使得$P(O|\lambda)$最大，也即最大似然估计。

训练过程为，在初始状态给参数赋随机值，然后在每次迭代，计算在观察序列条件下所有参数的期望值，作为下次迭代的估计值，一直到收敛。这是一个EM算法，具体计算过程可以采用动态规划前向后向算法，最终达到的是一个局部最优解。

CRF

条件随机场，是在条件给出的情况下，导出的一个场。条件可以看做是系统的外部环境，全局信息，当系统所处环境给定时，系统状态的分布服从能量函数。比如当温度和体积给定时，系统粒子状态分布是玻尔兹曼分布。

在此，条件即是我们的训练样本集，一系列的观察序列，场由隐含状态节点构成，隐含状态节点的结构为一无向马尔科夫链，每个状态节点只与它相邻的两个节点有联系，并受全局信息观察序列$X$的影响。

所有能量模型都要给出能量的定义，该模型中能量定义基于的最小粒度是最大团，这个最大团的成员为$\{X,y_i,y_{i+1}\}$,其中$y_i$是第$i$个隐含节点的状态。因此我们能量函数的定义格式便为

$$E_i=E(y_i,y_{i+1},X,i)$$

该系统处于状态$Y$的概率为

$$P(Y|X)=\frac{e^{\sum_i E(y_i,y_{i+1},X,i)}}{Z}$$

更细化来说，我们每个最大团的总能量函数可以分为多个子能量，这多个子能量以一定的权重累加得到最终总能量。这好比一个粒子的总能量可以分为动能、势能、内能三个子能量的累加。

$$E_i=\sum_k \lambda_k e_k(y_i,y_{i+1},X,i)$$

方便起见，更简单的，我们可以定义子能量函数$e_k$为二值函数，满足条件为1，否则为0。在给定子能量函数（或者称作特征函数）前提下，模型的参数为$\{\lambda_i\}$。

模型的训练过程。

训练前人工定义好子能量函数，训练的每个样本形如$X,Y$,即观察序列和隐含序列已经给定。初始时随机化参数，然后对每个样本可以计算出其概率值，整个样本空间的概率为所有样本概率的连乘。可以用最大似然log-likehood进行参数估计。

模型训练好后，给定$X$,求出最可能的$Y$，可以用Viterbi算法。

使用场景为词性标注，实体识别。

SVD

奇异值分解。把原始矩阵$R$分解为如下形式$R=U^TSV$,其中$S$是对角阵，对角线上从大到小排列的是奇异值，代表该对应特征的权重。$U$的每一列对应原始矩阵行实体的特征向量，$V$的每一列对应原始矩阵列实体的特征向量。

把对角阵保留其前$k$个特征，其它置0，重新得到一个近似矩阵$R_f$,可以做预测用。

使用场景。

1）数据压缩，保留其主要特征的$R_f$为降维后的原始矩阵$R$的近似表示。

2)打分预测，假设原始矩阵的$R_{ij}$表示第$i$个用户对第$j$个东西的打分，那么$R_f$重对应的值便是预测的结果。

3)聚类。分解并降维后的$U$和$V$两个矩阵保存了对应实体的特征向量，这些特征向量具有相同的维度$k$,我们可以用来聚类，比如找到相似用户，找到跟用户相关度最近的几个物品。如果有一个新用户，我们有他的评分向量，根据一定的公式我们可以得到这个新用户的特征向量。query检索，对用户的query生成k维特征向量，对所有文档计算余弦值得到最相似的文档。

4)主题抽取。假设原始矩阵表示文档和词汇，分解并降维后，每个文档对应一个$k$维的特征向量，每个词语同样如此。特征向量的每一个维度可以看做一个主题（LSA）。

PLSA

潜在概率语义分析。潜在，说明主题是隐含状态，不可直接观察到，语义分析是用主题来表示语义。是一个生成模型，生成模型是，根据该模型可以计算出可观察样本的生成概率，然后利用最大似然估计反推模型的参数，所以生成模型有一个生成流程。

样本集有多个文档构成，文档由多个字构成。然后再文档和词语之间，我们假设出一层主题层来，我们假设文档是由主题构成的，我们固定主题个数为k，那么每个文档对应一个主题分布，这个主题是固定的，但是未知的；然后假设一个主题装了好多单词，每个主题对应一个单词的概率分布，这个分布也是固定的，但是未知的。由此我们便有了连个矩阵$A$和$B$,$A_{ij}=P(z_j|d_i)$表示第i个文档中主题j出现的概率，$B_{ij}=P(w_j|z_i)$表示第i个主题中单词j出现的概率。这两个矩阵便是模型的参数。

我们的语料库被生成的流程是这样滴，首先，以$P(d_i)=\frac{count(d_i)}{|all~word|}$的概率选出一个文档，这个概率是已知的可统计出来；然后根据$P(z_j|d_i)$概率选择一个主题$z_j$,这个概率对应A矩阵，是需要估计的；最后根据$P(w_j|z_i)$概率生成一个单词$w_j$,这个概率对应B矩阵是需要估计的。

那么，一个文档$d_i$被生成的概率便为文档中所有单词生成概率的连乘：

$$P(W|d_i)=\prod_j P(w_j|d_i)$$

整个语料的生成概率为
$$P(W|D)=\prod_i P(W|d_i)P(d_i)$$

最大化这个概率即可。

根据生成流程，P(w_j|d_i)可以通过对所有路径$d_i\rightarrow z_k \rightarrow w_j$的概率求和得到

$$P(w_j|d_i)=\sum_k P(z_k|d_i)P(w_j|z_k)$$

训练方法采用EM法，首先随机初始化参数，然后根据条件求出各参数的期望作为下次迭代的估值。参数的期望是一句可观测的$d_i$和$w_j$反推得到的，所以用到了贝叶斯公式。具体的思想是该条路径的概率$d_i\rightarrow z_k \rightarrow w_j$占所有路径概率总和的比例。

使用场景。当模型训练好后，预料中的所有文档都有一个对应的主题向量，可以用来文档聚类，另外，对于每一个单词，我们也可以得到对应的主题向量可以用作基于语义的query检索。即可以依据主题计算文档相似性和词语相似性。

那么，当来了一个新的文档时，我们怎么计算它的主题分布呢，我的想法是，把它里面所有词语的主题向量加和求平均即可。

LDA

潜在Dirichlet分布主题语义分析。与PLSA模型非常类似，也是通过主题生成文档。不同的是，PLSA假设每个文档必对应一个固定的主题分布，每个主题必对应一个固定的词语分布，这有点类似于经典概率论，概率是先天存在好的，只是等着我们测量而已。LDA并不这样假设，两者的分布并不是固定的，其分布是通过更高层的分布生成机制来生成的，只有当你测量时，它才坍缩成一个具体的分布，当你不测量时，它的具体分布是不定的，有点类似于量子概率，处在一个量子状态中，这个量子状态在被测量时会以一定的概率生成可观测的值，这个值在这里就是一个具体的分布。这个“一定的概率”表明了生成分布的倾向，对应Dirichlet分布中的参数$\alpha$和$\beta$，是模型的超参数，根据经验指定。相比于PLSA每个文档都有一个主题分布的向量参数，LDA的参数会非常少，只有$\alpha$和$\beta$两个参数，是两个向量，这个参数表征了训练样本集的"量子态"。

生成语料库的具体流程为：1）根据参数$\beta$生成每个主题的词语分布。2）对每个文档，根据参数$\alpha$生成该文档的主题分布。3）根据第二步的主题分布生成一个主题。4）根据生成的主题和在第一步生成的该主题对应的词语分布，生成一个单词。

训练过程采用gibbs采样。固定所有参数以及状态，然后可以计算出给定词语对应主题的概率，然后根据这概率以轮盘法采样一个主题更新这个词语的主题，直到算法收敛。训练后会求得类似PLSA的两个分布矩阵，用法参考PLSA。

【待续】

参考文献：

http://blog.csdn.net/likelet/article/details/7056068

http://wenku.baidu.com/link?url=L1IdMbJ5lxL2z4JkxBWdJ2LFBCiziiKwohx-QYjmmfqpoeupyfjvpGFwBsLM_2BhneRUV2NZdRngKE0bGpFqvj3RhQI8hM1fUwlIxoo4f_q&pn=51

http://wenku.baidu.com/link?url=STqFlBAJFstKUMCffWyhVvMzvnVXKQ_yePhPi3JkwtwC2Pol3knpfMUhTSGkvt0ZrD9BkrqRZA-GmR1XKMTZeda4loogiQ_RUUONgoSBnKW

http://blog.csdn.net/wuyanyi/article/details/7964883

http://blog.csdn.net/sunmenggmail/article/details/8566275

http://blog.csdn.net/v_july_v/article/details/41209515

http://www.shellsec.com/tech/158684.html

http://vdisk.weibo.com/s/aR2Sk3ifABoZM

http://www.shellsec.com/tech/63868.html