机器学习 课件 第6章　支持向量机

概率无向图模型概率图模型

（probabilisticgraphicalmodels）是一种用图结构来描述多元随机变量之间条件独立关系的概率模型。简称图模型（graphicalmodel，GM）图中每个结点表示一个随机变量或⼀组随机变量，节点之间的边表⽰这些变量之间的概率关系。概率图模型有向图模型无向图模型使用有向无环图表示变量间的关系使用无向图表示变量间的关系概率图模型概率无向图模型概率无向图模型

uvO

没有直连边的任意两个节点独立概率无向图模型局部马尔可夫性

概率无向图模型全局马尔可夫性

概率无向图模型概率无向图模型概率无向图模型：设有联合概率分布P(Y)，由无向图G=(V,E)

表示,V

是结点集，E是边集，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布

P(Y)

满足成对、局部或全局马尔可夫性，则称此联合概率分布为概率无向图模型或马尔可夫随机场。概率无向图模型----因子分解团（clique)

：无向图

G

中任何两个结点均有边连接的结点子集。最大团（maximalclique)：若C是无向图G的一个团，并且不能再加进任何一个

G

的结点使其成为一个更大的团，则称此C

为最大团。团有7个：{x1,x2},{x1,x3},{x1,x4},{x2,x3},{x3,x4},{x1,x2,x3},{x1,x3,x4}最大团有2个：{x1,x2,x3},{x1,x3,x4}{x1,

x2,x3,x4}概率无向图模型----因子分解因子分解：将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数乘积形式的操作。概率无向图模型----因子分解Hammersley-Clifford定理：如果一个分布

p(x)>0

满足无向图

G

中的局部马尔可夫性质，当且仅当

p(x)

可以表示为一系列定义在最大团上的非负函数的乘积形式，即：

其中，Q

为G中的最大团集合，

是定义在团C上的势能函数（potentialfunction），

是配分函数（partitionfunction），用来将乘积归一化为概率形式。概率无向图模型----因子分解吉布斯分布（Gibbsdistribution）：

联合概率分布可以写成：

根据Hammersley-Clifford定理，概率无向图模型和吉布斯分布是一致的。吉布斯分布一定满足马尔可夫随机场的条件独立性质，并且马尔可夫随机场的概率分布一定可以表示成吉布斯分布。概率无向图模型----因子分解势能函数一般为正：其中是能量函数这种形式的分布又称为玻尔兹曼分布（BoltzmannDistribution）。任何一个无向图模型都可以用上述公式来表示其联合概率分布。概率无向图上的联合概率分布：TheEnd逻辑斯蒂回归模型主讲人：李侃逻辑斯蒂回归模型型对数线性模型利用特征函数以及参数的方式对势函数进行定义

势能函数：联合概率p(x)的对数形式：对数线性模型是定义在

上的特征向量，是权重向量逻辑斯蒂回归模型（logisticregressionmodel）最大熵模型（maximumentropymodel）

逻辑斯蒂回归模型逻辑斯蒂回归模型

:在线性回归模型的基础上，使用Sigmoid函数，将线性模型的结果压缩到[0,1]之间，使其拥有概率意义，它可以将任意输入映射到[0,1]区间内，实现由值到概率的转换。主要思想：根据现有数据对分类边界线（decisionboundary）建立回归公式，以此分类。优点：直接对分类的可能性建模，无需事先假设数据分布，避免了假设分布不准确带来的问题。由于它是针对分类的可能性进行建模，不仅能预测出类别，还可得到属于该类别的概率。属于概率性判别式模型

线性分类算法逻辑斯蒂回归模型也是深度学习中的重要单元逻辑斯蒂回归模型假设某事件发生的概率为

p，那么此事件不发生的概率为(1-p)，则称p/(1-p)为此事件发生的几率。取此事件发生几率的对数定义

logit(p)：

取logit函数的反函数，称为logistic函数，即Sigmoid函数：逻辑斯蒂函数逻辑斯蒂回归模型逻辑斯蒂分布逻辑斯蒂分布的分布函数F(x)逻辑斯蒂分布的密度函数

f(x)

设X是连续随机变量，则：是位置参数，是形状参数逻辑斯蒂回归模型逻辑斯蒂回归模型对于二分类的逻辑斯蒂回归模型有：

分类算法是求解

，用逻辑斯蒂分布的分布函数sigmoid函数建模通过上两式得：

几率比值比、机会比、优势比逻辑斯蒂回归模型线性模型：参数向量：基函数：

逻辑斯蒂回归模型可重写为：逻辑斯蒂回归模型

逻辑斯蒂回归模型可重写为：逻辑斯蒂回归模型极大似然估计模型参数对于一个二分类的数据集

似然函数：

对数似然函数：逻辑斯蒂回归模型引入一个负号转换为梯度下降法来求解，目标函数为：模型学习中通常有用梯度下降法或牛顿法、拟牛顿法（DFP、BFGS、L-BFGS）。极大似然估计模型参数梯度下降法求解：每次迭代更新：TheEnd最大熵模型主讲人：李侃概率无向图模型最大熵模型（maximumentropymodel，MaxEnt）基本思想：在学习概率模型时，所有可能的模型中熵最大的模型是最好的模型；若概率模型需要满足一些约束，则在满足已知约束的条件集合中选择熵最大的模型。最大熵模型最大熵原理前提

：需满足一定约束；

不做任何假设，在约束外的事件发生概率为等概率。1957年由EdwinThompsonJaynes提出在已知部分知识的前提下，关于未知分布最合理的推断就是符合已知知识最不确定或最随机的推断，这是可以做出的不偏不倚的选择。最大熵原理是对一个随机事件的概率分布进行预测时，预测应当满足全部已知的约束，而对未知的情况不做任何主观假设。在这种情况下，概率分布最均匀，预测的风险最小，因此得到的概率分布的熵最大。最大熵模型最大熵模型约束条件：

引入特征函数f(x,y)：

最大熵原理应用于分类问题得到最大熵模型特征函数

f(x,y)描述x与y之间的某一事实最大熵模型最大熵模型

最大熵模型最大熵模型给定n个特征函数

从满足约束的模型集合

C

中找到使得

P(Y|X)的熵最大即为最大熵模型。经验分布与特征函数结合能代表概率模型需要满足的约束，只需使得两个期望相等最大熵模型需要满足的约束最大熵模型最大熵模型条件分布

P(Y|X)的熵：

最大熵模型

最大熵模型：

最大熵模型

无约束化的最优化问题拉格朗日乘子法

有约束条件的最优化问题最大熵模型

最大熵模型形式化为便于拉格朗日对偶处理的极小极大的问题：

L(P,w)的极小极大问题与极大极小问题等价：

最大熵模型

上式的解：最大熵模型

最大熵模型

进而可以得到：

最大熵模型

求其对偶问题的外部极大化即可，将最优解记做w*：

最大熵模型最大熵模型

最大熵模型最大熵模型

最大熵模型

极大化似然估计解法

最大熵模型最大熵模型

最大熵模型最大熵模型

最大熵模型作为分类方法：优点：信息熵极大，准确率较高灵活设置约束条件，调整对未知数据的适应度和对已知数据的拟合程度缺点：迭代过程计算量大，实际应用比较难。TheEnd条件随机场主讲人：李侃概率无向图模型条件随机场

一种条件概率分布模型P(Y|X)，表示的是给定一组输入随机变量的条件下另一组输出随机变量的马尔可夫随机场一种直接建模条件概率的判别式无向图模型（conditionalrandomfield，CRF）JohnLafferty等人2001年提出条件随机场条件随机场

假设条件随机场的最大团集合为C，其条件概率为：

条件随机场条件随机场

对任意结点v成立，则称条件概率分布p(Y

|X)为条件随机场。其中表示结点v可以取无向图中除结点u以外的任一结点，

表示结点u的邻接结点集条件随机场线性条件随机场

以词性标注为例，X表示输入的句子，

表示第n-1位置上的文本；Y表示对应的词性序列，表示第n-1位置上的词性。条件随机场条件概率定义为：条件随机场使用势函数和图结构上的团来定义条件概率

。选择合适的势函数，即可得下面的条件概率，在条件随机场中，选用指数势函数并引入特征函数是定义在观测序列的两个相邻标记位置上的转移特征函数，用于刻画相邻标记变量之间的相关关系以及观测序列对它们的影响；是定义在观测序列的标记位置i上的状态特征函数，用于刻画观测序列对标记变量的影响；和是参数，z是规范化因子条件随机场

若两个特征函数统一为，则：

条件随机场

以自然语言处理的词性标注任务为例观测数据为单词序列，标记为相应的词性序列，具有线性序列结构。

若采用转移特征函数：

若采用状态特征函数：

条件随机场

条件随机场需解决下面三个关键问题：

（1）特征函数的选择（2）参数估计（3）模型推断从已经标注好的训练数据集学习条件随机场模型的参数，即各特征函数的权重向量在给定条件随机场参数

下，预测出最可能的状态序列特征函数的选择直接关系模型的性能条件随机场参数估计极大似然估计迭代缩放条件随机场

取对数形式：

条件随机场

条件随机场模型中极大似然函数：

条件随机场

条件随机场

迭代缩放算法GIS算法（generalisediterativescaling）IIS算法（improvediterativescaling）

Laffety提出两个迭代缩放的算法用于估计条件随机场的极大似然参数迭代缩放是一种通过更新规则来更新模型中的参数，通过迭代改善联合或条件概率模型分布的方法。条件随机场迭代基本原理：

条件随机场条件随机场对数似然值的变化可以表示为：

条件随机场引入辅助函数：

条件随机场迭代过程：

条件随机场

定义一个全局修正特征S(x,y)：

条件随机场更新值按下式计算：

条件随机场

①GIS算法的收敛速度由计算更新值的步长确定。C值越大，步长越小，收敛速度就越慢；反之C值越小，步长越大，收敛的速度也就越快。②GIS算法是依赖于一个额外的全局修正特征S(x,y)，以确保对于每个(x,y)的有效特征总和是一个常量。但是一旦加入这个新的特征，就认为这个特征和特征集中所有其他的特征之间是相互独立的，并且它的参数也需要使用上式来更新。计算期望需要对