威伦特

条件随机场（conditional random field）是一个比感知机更加强大的模型。

背景知识

机器学习模型谱系图

Sklearn对应机器学习算法决策树

使用模板：

生成式模型

模拟数据的生成过程，且随机变量x，y存在因果先后关系：现有y再有x。这种关系通过联合分布模拟：

具体流程：

• 根据p(y)采样y
• 根据p(x|y)采用x
• 生成样本概率p(x,y)
• 通过遍历y的所有取值，获得最大的P(x,y)作为预测结果

通过p(x,y)，可以求得p(x)。

但是，p(x)很难准确估计。因为特征之间并不是相互独立的，存在一定的依赖关系。

eg： 中文分词的一元语法：字符“榴”的后一个字符可以确定是“莲”，但是生成式模型直接认为这两个字符相互独立，忽略的这种依赖关系，导致不合符实际。

判别式模型

对生成式模型的改进。跳过了p(x)，直接对p(y|x)建模。这样不需要考虑x内的各种依赖关系。

在生成式和判别式中，模型都是多维度随机变量分布。这些随机变量可能相互独立，也可能相互依赖，可以通过概率图模型来进行分析多维随机变量分布。

有向和无向概率图模型

概率图模型

通过图来表示p(x,y)，利用结点来表示随机变量，用边来表示有关联的随机变量。

有向图模型

将事情通过前后因果顺序进行连接为有向图。

“发生地震”和“卡车撞墙”会导致“房子摇晃”，同时“发生地震”也会导致“卡车撞墙”，于是将"卡车撞墙"和"发生地震"指向"房子摇晃"，“发生地震"指向"卡车撞墙”。

于是多维随机变量的分布可以分解为：

马尔科夫链就是有向图中的一个例子。

无向图模型：

不需要探究事情的前因后果。仅仅指向有关联的结点。

无向图将概率分解为所有最大团上的某函数的乘积。

团： 无向图的完全子图。

极大团：如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图G的极大团

最大团：最大团就是就是结点数最多的极大团。

在上图中，

团有很多：{0，5}，{0，1}，{0，4，5}，{1，2，4}…

极大团：{0,4,5},{1,2,4},{0,1,4},{4,3}

最大团：{0,4,5},{1,2,4},{0,1,4}

无向图模型定义了一些虚拟的因子节点，每个因子节点只连接部分节点，组成更小的最大团

这样，该图的最大团由一个变为了4个，每个最大团变量节点变为了两个。于是，将多为随机变量的联合分布分解为了各个最大团中的因子的乘积。并且该分布为判别式模型最需要的条件概率分布。

在机器学习中，通常将因子函数设为：

P(y_t|x_t)=\frac{1}{Z(x)}C_t(y_{t-1},y_t,x_t)\
=\frac{1}{Z(x)}exp{\sum_{k=1}^KW_{k}f_{k}(y_{t-1},y_t,x_t)}\其中：
Z(x)=\sum_{y}exp{\sum_{k=1}^KW_{k}f_{k}(y_{t-1},y_t,x_t)}
\K为特征数，f_{k}为特征函数，W_k为特征的权重

define：\\mathbb W ={W_1,W_2,…,W_k}^T\
\mathbb F(y_{t-1},y_t,x_t)={f_1(y_{t-1},y_t,x_t),…,f_k(y_{t-1},y_t,x_t)}\
so:\
P(y_t|x_t)=\frac {exp(\mathbb W\mathbb F(y_{t-1},y_t,x_t))}{Z(x)}

学习问题

我们给定训练数据集X和对应的标记序列Y，K个特征函数fk(x,y)，需要学习模型参数特征权重和条件概率Pw(y|x)，其中条件概率Pw(y|x)和模型权重wk满足以下关系

梯度下降法求解

在使用梯度下降法求解模型参数之前，我们需要定义我们的优化函数，这里采用极大似然函数作为目标函数：

首先计算第一个句子词性为1，2的非规范化概率：\
δ_1(1)=μ1s1=1\δ_1(2)=μ2s2=0.5

接下来进行递推，计算第二个句子：\
δ_2(1)=max{δ_1(1)+t_2λ_2+μ_3s_3,δ_1(2)+t_4λ_4+μ_3s_3}
\=max{1+0.6+0.8,0.5+1+0.8}=2.4\
δ_2(2)=max{δ_1(2)+μ_2s_2,δ_1(1)+t_1λ_1+μ_2s_2}
\=max{0.5+0.5,1+1+0.5}=2.5\

然后计算第三个句子：\
δ_3(1)=max{δ_2(1)+μ_3s_3,δ_2(2)+t_3λ_3+μ_3s_3}
\=max{2.4+0.8,2.5+1+0.8}=4.3\
δ_3(2)=max{δ_2(1)+t_1λ_1+μ_4s_4,δ_2(2)+t_5λ_5+μ_4s_4}
\=max{2.4+1+0.5,2.5+0.2+0.5}=3.9\

比较max(δ_3(1),δ_3(2)，得到y_3=1,再逆推回去\