NLP系列5：重要模型与算法

1. 隐马尔可夫模型（HMM）
   1. 生成模型 vs 判别模型
   2. EM算法、HMM、CRF的比较
   3. HMM参数含义
   4. 如何寻找最好的Z
   5. 相关算法
   6. 如何计算三大参数
2. 隐变量模型
   1. SVD
   2. FM
3. EM算法
4. k-means算法
5. 高斯混合模型（GMM）
6. 条件随机场（CRF）

核心内容：HMM、隐变量模型、EM算法、k-means算法、GMM、CRF

隐马尔可夫模型（HMM）

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列，称为状态序列（state sequence);每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列（observation sequence)。序列的每一个位置又可以看作是一个时刻。

区分——马尔可夫网络、马尔可夫模型、马尔可夫过程、贝叶斯网络
将随机变量作为结点，若两个随机变量相关或者不独立，则将二者连接一条边；若给定若干随机变量，则形成一个有向图，即构成一个网络。
如果该网络是有向无环图，则这个网络称为贝叶斯网络。
如果这个图退化成线性链的方式，则得到马尔可夫模型；因为每个结点都是随机变量，将其看成各个时刻(或空间)的相关变化，以随机过程的视角，则可以看成是马尔可夫过程。
若上述网络是无向的，则是无向图模型，又称马尔可夫随机场或者马尔可夫网络。
如果在给定某些条件的前提下，研究这个马尔可夫随机场，则得到条件随机场。
如果使用条件随机场解决标注问题，并且进一步将条件随机场中的网络拓扑变成线性的，则得到线性链条件随机场。

1. 给定模型，如何有效计算产生观测序列的概率？换言之，如何评估模型与观测序列之间的匹配程度？
   ——向前算法(Forward Algorithm)、向后算法(Backward Algorithm)
2. 给定模型和观测序列，如何找到与此观测序列最匹配的状态序列？换言之，如何根据观测序列推断出隐藏的模型状态？
   ——维特比算法(Viterbi Algorithm)
3. 给定观测序列，如何调整模型参数使得该序列出现的概率最大？换言之，如何训练模型使其能最好地描述观测数据？
   ——鲍姆-韦尔奇算法(Baum-Welch Algorithm) (约等于EM算法)

生成模型 vs 判别模型

本质的区别：生成模型是使用联合概率的形式p(x,y)来构造目标函数，判别模型一般是写为p(y|x)条件概率的形式

1. 生成模型：由数据学习联合概率密度分布P(X,Y),（概率密度分布函数用于采样，产生更多该数据集的数据），然后再根据贝叶斯公式P(Y|X)求出作为预测模型，即生成模型：P(Y|X)=P(X,Y)/P(X)生成模型需要无穷多的样本才可以达到理论是的预测，因为对于P(X)，需要很多的样本才可以使得其比较可靠。典型的生成模型有朴素贝叶斯，隐马尔可夫模型等。生成模型关注与数据本身，而不像判别模型，关注于最优的分类界面。生成模型还可以用于带有隐层的的模型中，此时的判别模型是无法使用的。
2. 判别模型：由数据直接学习得到一个判别函数P(Y|X)。典型的判别模型主要有：KNN，SVM，决策树。判别模型只关注于如何分类（如何对给定的数据空间进行特征映射和区分，找到最优的分类面）。模型主要反应的是不同类别之间的差异性。判别模型直接对预测进行建模，效率高，效果比较好。

EM算法、HMM、CRF的比较

EM算法是用于含有隐变量模型的极大似然估计或者极大后验估计，有两步组成：1)求期望（expectation）；2)求极大值（maxmization）。本质上EM算法还是一个迭代算法，通过不断用上一代参数对隐变量的估计来对当前变量进行计算，直到收敛。注意：EM算法是对初值敏感的，而且EM是不断求解下界的极大化逼近求解对数似然函数的极大化的算法，也就是说EM算法不能保证找到全局最优值。

隐马尔可夫模型是用于标注问题的生成模型。有几个参数（π，A，B）：初始状态概率向量π，状态转移矩阵A，观测概率矩阵B。称为马尔科夫模型的三要素。马尔科夫三个基本问题：
1、概率计算问题：给定模型和观测序列，计算模型下观测序列输出的概率。->前向后向算法
2、学习问题：已知观测序列，估计模型参数，即用极大似然估计来估计参数。->Baum-Welch(也就是EM算法)和极大似然估计。
3、预测问题：已知模型和观测序列，求解对应的状态序列。->近似算法（贪心算法）和维比特算法（动态规划求最优路径）

条件随机场CRF，给定一组输入随机变量的条件下另一组输出随机变量的条件概率分布密度。条件随机场假设输出变量构成马尔科夫随机场，而我们平时看到的大多是线性链条随机场，也就是由输入对输出进行预测的判别模型。求解方法为极大似然估计或正则化的极大似然估计。

之所以总把HMM和CRF进行比较，主要是因为CRF和HMM都利用了图的知识，但是CRF利用的是马尔科夫随机场（无向图），而HMM的基础是贝叶斯网络（有向图）。而且CRF也有：概率计算问题、学习问题和预测问题。大致计算方法和HMM类似，只不过不需要EM算法进行学习问题。

HMM和CRF对比，其根本还是在于基本的理念不同，一个是生成模型，一个是判别模型，这也就导致了求解方式的不同。

HMM参数含义

三大参数：{A,B,π}（π是数学中的圆周率PI），括号里的三个变量称为隐马尔可夫模型的三要素。加上一个具体的状态集合Q和观测序列V，则构成了HMM的五元组。

状态转移概率矩阵A与初始状态概率向量π确定了隐藏的马尔可夫链，生成不可观测的状态序列。观测概率矩阵B确定了如何从状态生成观测，与状态序列综合确定了如何产生观测序列。
从定义可知，隐马尔可夫模型作了两个基本假设：
(1)齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关。
(2)观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关。

如何寻找最好的Z

相关算法

• F/B算法：给定任何一个时间k，能计算出Zk属于某一个具体状态的概率的多少
• Forward算法：给定1-k时刻所有x的值，得到隐变量Zk的值
• Backward算法：给定Zk，求出下一时刻X(k+1)的值

如何计算三大参数

隐变量模型

SVD

在物品推荐系统中，
1）随着人和物品的增加，系统的推荐效果并不是线性增加的
2）矩阵中元素稀疏，在计算过程中，随机的增减一个维度，对结果影响很大
为了解决上面的问题，于是就有人发明了矩阵分解的方法：
假设用户物品的评分矩阵 A 是 m 乘以 n 维，即一共有 m 个用户，n 个物品。我们选一个相对 m 和 n 很小的数 k，通过一套算法得到两个矩阵 U 和 V，矩阵 U 的维度是 m 乘以 k，矩阵 V 的维度是 n 乘以 k。

FM

上面这种方法的问题是：我们无法对用户和物品显性特征的建模，譬如我们已经得到了用户的用户画像，或者物品的物品画像，但是我们不能融合进入我们的模型，我们如果要对这些显性特征进行建模的话，一个可行的方案就是逻辑回归，于是有人就对矩阵分解和逻辑回归进行了结合，提出了”分解机”的模型.

分解机FM的基本原理是：不仅对显性变量建模，而且对显性变量之间的关系进行建模，在对显性变量关系建模的过程中使用了隐变量的方法。

另外分解机的一个优势是可以部分解决冷启动问题，因为即使没有用户的反馈数据，我们也能够通过显性变量来预测出一个评分来,更多的关于FM的资料可以看我之前的文章CTR 预估之 FM。

EM算法

期望极大算法(expectation maximization algorithm)，简称EM算法，是一种迭代算法，可以用于含义隐变量(hidden variable) 的概率模型参数的极大似然估计，或极大后验概率估计.

假设训练集 {x^(1),x^(2),...,x^(m)}是由m个独立的无标记样本构成。我们有这个训练集的概率分布模型 p(x,z;θ) ，但是我们只能观察到 x 。我们需要使参数 θ 的对数似然性最大化，即：

具体来说，我们需要每次为函数log P(x;θ)上的点θ，找到一个凹函数g(θ) <=P(x;θ)， 每次取 g(θ) 的最大值点为下一个 θ，迭代直到目标函数 logP(x;θ)达到局部最大值.

k-means算法

根据给定的K值和K个初始质心将样本中每个点都分到距离最近的类簇中，当所有点分配完后根据每个类簇的所有点重新计算质心，一般是通过平均值计算，然后再将每个点分到距离最近的新类簇中，不断循环此操作，直到质心不再变化或达到一定的迭代次数。数学上可以证明k-means是收敛的。

除了K-means 聚类算法外，还有其他聚类算法：Mean-Shift、DBSCAN、GMM、凝聚层次聚类

• DBSCAN——基于密度的带噪声的空间聚类的应用

有点类似于“传销”，不断发展“下线”，将周围的点纳入同一类。

相较于其他聚类算法，DBSCAN 提出了一些很棒的优点。首先，它根本不需要预置集群的数量。它还将离群值认定为噪声，不像 mean-shift 中仅仅是将它们扔到一个集群里，甚至即使该数据点的差异性很大也这么做。另外，这个算法还可以很好的找到任意尺寸核任意形状的集群。

SBSCAN 最大的缺点是当集群的密度变化时，它表现的不像其他算法那样好。这是因为当密度变化时，距离的阈值 ε 和用于确定邻居点的 minPoints 也将会随之改变。这个缺点也会发生在很高为的数据中，因为距离阈值 ε 变得很难被估计。

• GMM——基于高斯混合模型(GMM)的期望最大化（EM）聚类

高斯混合模型（GMM）具有更好的灵活性比K-means。使用GMMs，我们需要假设数据点是高斯分布，相对于环形的数据而言，这个假设的严格程度与均值相比弱很多。这样的话，我们有两个参数来描述簇的形状：均值和标准差。以二维为例，意味簇可以是任何一种椭圆形（因为我们有两个标准差在x和y方向）。因此，每个高斯分布会被分配到单一的聚类簇。

为了在每个聚类簇中找到这两个高斯参数（e.g均值和标准差），我们将使用的优化算法称为expectation–maximization（EM）。请看下面的图片，以说明将高斯拟合聚类簇。然后，我们可以处理EM聚类过程使用GMM。

高斯混合模型（GMM）

高斯混合模型（Gaussian Mixture Model）通常简称GMM，是一种业界广泛使用的聚类算法，该方法使用了高斯分布作为参数模型，并使用了期望最大（Expectation Maximization，简称EM）算法进行训练。

GMM是高斯混合模型，属于soft clustering，而k-means是hard clustering，将多个高斯分布叠加在一起，拟合数据的能力更强。example:

k-means：一个人->体育
GMM：一个人->概率分布，体育（30%），科技（50%），音乐（20%）

高斯分布（Gaussian distribution）有时也被称为正态分布（normal distribution），是一种在自然界大量的存在的、最为常见的分布形式。

模型的EM训练过程，直观的来讲是这样：我们通过观察采样的概率值和模型概率值的接近程度，来判断一个模型是否拟合良好。然后我们通过调整模型以让新模型更适配采样的概率值。反复迭代这个过程很多次，直到两个概率值非常接近时，我们停止更新并完成模型训练。

现在我们要将这个过程用算法来实现，所使用的方法是模型生成的数据来决定似然值，即通过模型来计算数据的期望值。通过更新参数μ和σ来让期望值最大化。这个过程可以不断迭代直到两次迭代中生成的参数变化非常小为止。该过程和k-means的算法训练过程很相似（k-means不断更新类中心来让结果最大化），只不过在这里的高斯模型中，我们需要同时更新两个参数：分布的均值和标准差。

高斯混合模型是对高斯模型进行简单的扩展，GMM使用多个高斯分布的组合来刻画数据分布。

K-means算法可以被视为高斯混合模型（GMM）的一种特殊形式。整体上看，高斯混合模型能提供更强的描述能力，因为聚类时数据点的从属关系不仅与近邻相关，还会依赖于类簇的形状。n维高斯分布的形状由每个类簇的协方差来决定。在协方差矩阵上添加特定的约束条件后，可能会通过GMM和k-means得到相同的结果。

整体来看，所有无监督机器学习算法都遵循一条简单的模式：给定一系列数据，训练出一个能描述这些数据规律的模型（并期望潜在过程能生成数据）。训练过程通常要反复迭代，直到无法再优化参数获得更贴合数据的模型为止。

条件随机场（CRF）

Log-Linear Model for Sequential Data

CRF即条件随机场（Conditional Random Fields），是在给定一组输入随机变量条件下另外一组输出随机变量的条件概率分布模型，它是一种判别式的概率无向图模型，既然是判别式，那就是对条件概率分布建模。
CRF较多用在自然语言处理和图像处理领域，在NLP中，它是用于标注和划分序列数据的概率化模型，根据CRF的定义，相对序列就是给定观测序列X和输出序列Y，然后通过定义条件概率P(Y|X)来描述模型。
CRF的输出随机变量假设是一个无向图模型或者马尔科夫随机场，而输入随机变量作为条件不假设为马尔科夫随机场，CRF的图模型结构理论上可以任意给定，但我们常见的是定义在线性链上的特殊的条件随机场，称为线性链条件随机场。