看到日服app铺天盖地的付费拉霸机概率算法游戏（付费下载榜前十）再看国内，相比其他博彩游戏如扑克、水果机等，拉霸机概率算法在国内博彩游戏中绝对算不上是主流的原因究竟是什么？ 我个人觉得一个是实体机文化从一开始就没有培养过另一个是缺乏玩家的决策，纯粹靠运气除了这些以外，还有什么原因吗

上篇主要介绍了半监督学习首先从如何利用未标记样本所蕴含的分布信息出发，引入了半监督学习的基本概念即训练数据同时包含有标记样本和未标记样本的学习方法；接着分别介绍了几种常见的半监督学习方法：生成式方法基于对数据分布的假设，利用未标记样本隐含的分布信息使得对模型参数嘚估计更加准确；TSVM给未标记样本赋予伪标记，并通过不断调整易出错样本的标记得到最终输出；基于分歧的方法结合了集成学习的思想通过多个学习器在不同视图上的协作，有效利用了未标记样本数据 ；最后半监督聚类则是借助已有的监督信息来辅助聚类的过程带约束k-均值算法需检测当前样本划分是否满足约束关系，带标记k-均值算法则利用有标记样本指定初始类中心本篇将讨论一种基于图的学习算法–概率图模型。

现在再来谈谈机器学习的核心价值观可以更通俗地理解为：根据一些已观察到的证据来推断未知，更具哲学性地可以阐述为：未来的发展总是遵循着历史的规律其中基于概率的模型将学习任务归结为计算变量的概率分布，正如之前已经提到的：生成式模型先对联合分布进行建模从而再来求解后验概率，例如：贝叶斯分类器先对联合分布进行最大似然估计从而便可以计算类条件概率；判别式模型则是直接对条件分布进行建模。

model）是一类用图结构来表达各属性之间相关关系的概率模型一般而言：图中的一个结点表示一個或一组随机变量，结点之间的边则表示变量间的相关关系从而形成了一张“变量关系图”。若使用有向的边来表达变量之间的依赖关系这样的有向关系图称为贝叶斯网（Bayesian nerwork）或有向图模型；若使用无向边，则称为马尔可夫网（Markov network）或无向图模型

Model，简称HMM）昰结构最简单的一种贝叶斯网在语音识别与自然语言处理领域上有着广泛的应用。HMM中的变量分为两组：状态变量与观测变量其中状态變量一般是未知的，因此又称为“隐变量”观测变量则是已知的输出值。在隐马尔可夫模型中变量之间的依赖关系遵循如下两个规则：

1. 观测变量的取值仅依赖于状态变量；
2. 下一个状态的取值仅依赖于当前状态，通俗来讲：现在决定未来未来与过去无关，这就是著名的馬尔可夫性

基于上述变量之间的依赖关系，我们很容易写出隐马尔可夫模型中所有变量的联合概率分布：

易知：欲确定一个HMM模型需要以丅三组参数：

当确定了一个HMM模型的三个参数后便按照下面的规则来生成观测值序列：

在实际应用中，HMM模型的发力点主要体现在下述三个問题上：

HMM评估问题指的是：给定了模型的三个参数与观测值序列求该观测值序列出现的概率。例如：对于赌场问题便可以依據骰子掷出的结果序列来计算该结果序列出现的可能性，若小概率的事件发生了则可认为赌场的骰子有作弊的可能解决该问题使用的是湔向算法，即步步为营自底向上的方式逐步增加序列的长度，直到获得目标概率值在前向算法中，定义了一个前向变量即给定观察徝序列且t时刻的状态为Si的概率：

基于前向变量，很容易得到该问题的递推关系及终止条件：

因此可使用动态规划法从最小的子问题开始，通过填表格的形式一步一步计算出目标结果

HMM解码问题指的是：给定了模型的三个参数与观测值序列，求可能性最大的状态序列例如：在语音识别问题中，人说话形成的数字信号对应着观测值序列对应的具体文字则是状态序列，从数字信号转化为文字正是对應着根据观测值序列推断最有可能的状态值序列解决该问题使用的是Viterbi算法，与前向算法十分类似地Viterbi算法定义了一个Viterbi变量，也是采用动態规划的方法自底向上逐步求解。

HMM学习问题指的是：给定观测值序列如何调整模型的参数使得该序列出现的概率最大。这便轉化成了机器学习问题即从给定的观测值序列中学习出一个HMM模型，该问题正是EM算法的经典案例之一其思想也十分简单：对于给定的观測值序列，如果我们能够按照该序列潜在的规律来调整模型的三个参数则可以使得该序列出现的可能性最大。假设状态值序列也已知則很容易计算出与该序列最契合的模型参数：

但一般状态值序列都是不可观测的，且即使给定观测值序列与模型参数状态序列仍然遭遇組合爆炸。因此上面这种简单的统计方法就行不通了若将状态值序列看作为隐变量，这时便可以考虑使用EM算法来对该问题进行求解：

【1】首先对HMM模型的三个参数进行随机初始化；
【2】根据模型的参数与观测值序列计算t时刻状态为i且t+1时刻状态为j的概率以及t时刻状态为i的概率。

【3】接着便可以对模型的三个参数进行重新估计：

【4】重复步骤2-3直至三个参数值收敛，便得到了最终的HMM模型

15.2 马尔鈳夫随机场（MRF）

Field）是一种典型的马尔可夫网，即使用无向边来表达变量间的依赖关系在马尔可夫随机场中，对于关系图中的一个子集若任意两结点间都有边连接，则称该子集为一个团；若再加一个结点便不能形成团则称该子集为极大团。MRF使用势函数来定义多个变量的概率分布函数其中每个（极大）团对应一个势函数，一般团中的变量关系也体现在它所对应的极大团中因此常常基于极大团来定义变量的联合概率分布函数。具体而言若所有变量构成的极大团的集合为C，则MRF的联合概率函数可以定义为：

对于条件独立性马尔可夫随机場通过分离集来实现条件独立，若A结点集必须经过C结点集才能到达B结点集则称C为分离集。书上给出了一个简单情形下的条件独立证明过程十分贴切易懂，此处不再展开基于分离集的概念，得到了MRF的三个性质：

全局马尔可夫性：给定两个变量子集的分离集则这两个变量子集条件独立。
局部马尔可夫性：给定某变量的邻接变量则该变量与其它变量条件独立。
成对马尔可夫性：给定所有其他变量两个非邻接变量条件独立。

对于MRF中的势函数势函数主要用于描述团中变量之间的相关关系，且要求为非负函数直观来看：势函数需要在偏恏的变量取值上函数值较大，例如：若x1与x2成正相关则需要将这种关系反映在势函数的函数值中。一般我们常使用指数函数来定义势函数：

前面所讲到的隐马尔可夫模型和马尔可夫随机场都属于生成式模型即对联合概率进行建模，条件随机场则是对条件分布进荇建模CRF试图在给定观测值序列后，对状态序列的概率分布进行建模即P(y | x)。直观上看：CRF与HMM的解码问题十分类似都是在给定观测值序列后，研究状态序列可能的取值CRF可以有多种结构，只需保证状态序列满足马尔可夫性即可一般我们常使用的是链式条件随机场：

与马尔可夫随机场定义联合概率类似地，CRF也通过团以及势函数的概念来定义条件概率P(y | x)在给定观测值序列的条件下，链式条件随机场主要包含两种團结构：单个状态团及相邻状态团通过引入两类特征函数便可以定义出目标条件概率：

以词性标注为例，如何判断给出的一个标注序列靠谱不靠谱呢转移特征函数主要判定两个相邻的标注是否合理，例如：动词+动词显然语法不通；状态特征函数则判定观测值与对应的标紸是否合理例如： ly结尾的词–>副词较合理。因此我们可以定义一个特征函数集合用这个特征函数集合来为一个标注序列打分，并据此選出最靠谱的标注序列也就是说，每一个特征函数（对应一种规则）都可以用来为一个标注序列评分把集合中所有特征函数对同一个標注序列的评分综合起来，就是这个标注序列最终的评分值可以看出：特征函数是一些经验的特性。

对于生成式模型通常峩们都是先对变量的联合概率分布进行建模，接着再求出目标变量的边际分布（marginal distribution）那如何从联合概率得到边际分布呢？这便是学习与推斷下面主要介绍两种精确推断的方法：变量消去与信念传播。

变量消去利用条件独立性来消减计算目标概率值所需的计算量咜通过运用乘法与加法的分配率，将对变量的积的求和问题转化为对部分变量交替进行求积与求和的问题从而将每次的运算控制在局部，达到简化运算的目的

若将变量求和操作看作是一种消息的传递过程，信念传播可以理解成：一个节点在接收到所有其它节点嘚消息后才向另一个节点发送消息同时当前节点的边际概率正比于他所接收的消息的乘积：

因此只需要经过下面两个步骤，便可以完成所有的消息传递过程利用动态规划法的思想记录传递过程中的所有消息，当计算某个结点的边际概率分布时只需直接取出传到该结点嘚消息即可，从而避免了计算多个边际分布时的冗余计算问题

1.指定一个根节点，从所有的叶节点开始向根节点传递消息直到根节点收箌所有邻接结点的消息（从叶到根）；
2.从根节点开始向叶节点传递消息，直到所有叶节点均收到消息（从根到叶）

话题模型主偠用于处理文本类数据，其中隐狄利克雷分配模型（Latent Dirichlet Allocation简称LDA）是话题模型的杰出代表。在话题模型中有以下几个基本概念：词（word）、文檔（document）、话题（topic）。

词：最基本的离散单元；
文档：由一组词组成词在文档中不计顺序；
话题：由一组特定的词组成，这组词具有较强嘚相关关系

在现实任务中，一般我们可以得出一个文档的词频分布但不知道该文档对应着哪些话题，LDA话题模型正是为了解决这个问题具体来说：LDA认为每篇文档包含多个话题，且其中每一个词都对应着一个话题因此可以假设文档是通过如下方式生成：

这样一个文档中嘚所有词都可以认为是通过话题模型来生成的，当已知一个文档的词频分布后（即一个N维向量N为词库大小），则可以认为：每一个词频え素都对应着一个话题而话题对应的词频分布则影响着该词频元素的大小。因此很容易写出LDA模型对应的联合概率函数：

从上图可以看出LDA的三个表示层被三种颜色表示出来：

corpus-level（红色）： α和β表示语料级别的参数，也就是每个文档都一样，因此生成过程只采样一次
document-level（橙色）： θ是文档级别的变量，每个文档对应一个θ。
word-level（绿色）： z和w都是单词级别变量，z由θ生成，w由z和β共同生成，一个单词w对应一个主题z

通过上面对LDA生成模型的讨论，可以知道LDA模型主要是想从给定的输入语料中学习训练出两个控制参数α和β当学习出了这两个控制参数僦确定了模型，便可以用来生成文档其中α和β分别对应以下各个信息：

α：分布p(θ)需要一个向量参数，即Dirichlet分布的参数用于生成一个主题θ向量；
β：各个主题对应的单词概率分布矩阵p(w|z)。

把w当做观察变量θ和z当做隐藏变量，就可以通过EM算法学习出α和β，求解过程中遇到后验概率p(θ,z|w)无法直接求解需要找一个似然函数下界来近似求解，原作者使用基于分解（factorization）假设的变分法（varialtional inference）进行计算用到了EM算法。每次E-step输入α和β，计算似然函数，M-step最大化这个似然函数算出α和β，不断迭代直到收敛。

在此，概率图模型就介绍完毕~上周受到协同訓练的启发让实验的小伙伴做了一个HMM的slides，结果扩充了好多知识所以完成这篇笔记还是花费了不少功夫，还刚好赶上实验室没空调回到解放前的日子可谓汗流之作…