《统计学习方法》

机器学习 读书笔记 DOING

---

第1章 统计学习方法概论

统计学习

统计学习是关于计算机基于数据结构构建概论统计模型并运用模型对数据进行预测与分析的一门学科。

统计学习的对象是数据，从数据出发，提取数据的特征，抽象出数据的模型，发现数据中的知识，又回到对数据的分析与预测中去。作为统计学习的对象，数据是多样的，包括计算机以及网络上的各种数字、文字、图像、视频、音频数据以及它们的组合。关于数据的基本假设是同类数据具有一定的统计规律性。

统计学习的目标是考虑学习怎么样的模型和如何学习模型，以使模型能对数据进行准确的预测与分析，同时也要考虑尽可能地提高学习效率。

统计学习的方法：监督学习、非监督学习、半监督学习、强化学习。

假设数据是独立同分布产生的；要学习的模型属于某个函数的集合，称为假设空间；应用某个评价准则，从假设空间中选择一个最优的模型；最优模型的选取由算法实现。

统计学习的三要素：模型（model，模型的假设空间）、策略（strategy，模型选择的准则）、算法（algorithm，模型学习的算法）。

实现统计学习方法的步骤：
1. 得到一个有限的训练集数据集合；
2. 确定包含所有可能的模型的假设空间，即学习模型的集合；
3. 确定模型选择的准则，即学习的策略；
4. 实现求解最优模型的算法，即学习的算法；
5. 通过学习方法选择最优模型；
6. 利用学习的最优模型对新数据进行预测或分析；

监督学习

监督学习（supervised learning）的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出作出一个好的预测。

输入空间（input space），输出空间（output space）

将输入与输出所有可能取值的集合，可以为有限元素的集合，也可以为整个欧式空间，通常输出空间小于输入空间

实例（instance）

每个具体的输入，通常由特征向量（feature veector）表示 $$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T$$

特征空间（feature space）

所有特征向量存在的空间，特征空间的每一维对应一个特征，输入空间可以与特征空间，有时需要将输入空间映射到特征空间，模型是定义在特征空间上的

训练集数据（training data）

$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_n)\}$

输入变量X与输出变量Y的类型

可以由不同的类型组成，可以为离散，也可以为连续；输入与输出均为连续称为回归；输出变量为有限个离散称为分类；输出与输入均为变量序列的预测问题称为标注

联合概率分布（P(X,Y)）

假设输入与输出的随机变量X和Y遵循联合分布P(X,Y)，表示分布函数或分布密度函数。假定这一概率存在，实际上是未知的。训练数据与测试数据由该概率独立同分布产生

假设空间（hypothesis space）

监督学习在于学习一个由输入到输出的映射，这一映射由模型来表示。模型属于输入到输出空间的映射的集合（假设空间）。模型可以为概率模型（条件概率分布$P(Y|X)$）或非概率模型（决策函数$Y=f(X)$）

统计学习三要素

模型

假设空间

$$\mathscr f = \{f|Y=f_{\theta}(X),\theta\in R^n\}$$ $$\mathscr f = \{P|P=P_{\theta}(Y|X),\theta\in R^n\}$$

策略

损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏

损失函数（loss function/cost function）

输出的预测值与实际值可能不一致，用损失函数或代价函数来度量预测错误的程度，非负实值函数$L(Y,f(X))$

• 0-1损失函数（0-1 loss function）
  $$L(Y,f(X))=\begin{cases} 1, & Y \ne f(X) \\ 0, & Y = f(X) \end{cases}$$
• 平方损失函数（quadratic loss function）
  $$L(Y,f(X))=(Y-f(x))^2$$
• 绝对损失函数（absolute loss function）
  $$L(Y,f(X))=|Y-f(X)|$$
• 对数损失函数（logarithmic loss function）或对数似然损失函数（log-likelihood loss function）
  $$L(Y,P(Y|X))=-log P(Y|X)$$

风险函数(risk function/expected function)

理论上模型f(X)关于联合分布P(X,Y)的平均意义下的损失，损失函数的期望
$$R_{exp}(f)=E_p[L(Y,f(X))]=\int_{X\times Y}L(y,f(x))P(x,y)dxdy$$ 学习的目标就是选择期望风险最小的模型，然而联合分布是未知的。

经验风险（expirical risk）/经验损失（empirical loss）

模型f(X)关于训练数据集的平均损失 $$R_{emp}(f)={1\over N}\sum_{i=1}^NL(y_i,f(x_i))$$ 根据大数定理，当样本容量N趋向于无穷时，经验风险趋于期望风险

经验风险最小化（empirical risk minimization，ERM）

经验风险最小的模型是最优的模型，就转化为求解最优化问题 $$min_{f\in F}{1\over N}\sum_{i=1}^NL(y_i,f(x_i))$$ 当样本空间足够大时，可以保证有很好学习效果。极大似然估计（maximum likelihood estimation）就是经验风险最小化的例子。当样本容量较小时，可能产生过拟合现象。

结构风险最小化（structural risk minimization，SRM）

为防止过拟合，等价于正则化，结构风险在经验风险上加上表示模型复杂度的正则化项（regularizer）或罚项（penalty term）,J(f)为模型的复杂度，是定义在假设空间上的泛函 $$R_{srm}(f)={1\over N}\sum_{i=1}^NL(y_i,f(x_i))+\lambda J(f)$$ $$min_{f\in F}{1\over N}\sum_{i=1}^NL(y_i,f(x_i))+\lambda J(f)$$ 贝叶斯估计中的最大后验概率估计就是结构风险最小化的一个例子

算法

统计学习问题归结为最优化问题，统计学习的算法成为求解最优化问题的算法。

模型评估与模型选择

训练误差（training error）

$R_{emp}(f)={1\over N}\sum_{i=1}^NL(y_i,f(x_i))$，N为训练集样本容量

测试误差（test error）

$e_{test}(f)={1\over N'}\sum_{i=1}^{N'}L(y_i,f(x_i))$，N'为测试集样本容量，当损失函数是0-1时，测试误差就变为错误率

模型选择

如果假设空间中存在“真”模型，那么所选的模型就应该逼近真模型，所选择的参数个数，参数向量都应该和真模型相近。如果一味提高对训练数据的预测能力，所选模型的复杂度则往往比真模型高，就是过拟合。学习时选择的模型所包含的参数过多，以至于出现对已知数据预测很好，对未知数据很差。

正则化与交叉验证

正则化（regularization）

正则化是结构风险最小化策略，是在经验风险上加一个正则化项（regularizer）或罚项（penalty term）。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大，可以是模型参数向量的范数。常见形式为（$\lambda\ge 0$） $$\min_{f\in F}{1\over N}\sum_{i=1}^NL(y_i,f(x_i))+\lambda J(f)$$
L2范数 $+{\lambda \over 2}||w||^2$
L1范数 $+{\lambda }||w||^1$
正则化符合奥卡姆剃刀原理。

交叉验证（cross validation）

随机将数据集切分成三部分，分别为训练集（training set）、验证集（validation set）、测试集（test set）。训练集用来训练模型，验证集用于模型的选择，而测试集用于最终对学习方法的评估。

• 简单交叉验证
  随机将数据分成两部分，训练集和测试集（例如7:3），然后在各种条件（不同参数个数）下训练模型，得到多个模型，然后在测试集上评估，选择测试误差最小的模型
• S折交叉验证（S-fold cross validation）
  随机将数据拆分成S个互不相交的大小相同的子集，然后利用S-1个子集进行训练，选择剩余一个进行测试，对可能的S种选择重复进行，选择S次评测中平均测试误差最小的模型
• 留一交叉验证
  S折交叉验证的特殊情形，S=N

泛化能力

泛化能力

是指学习到的模型对未知数据的预测能力，是学习方法本质上重要的性质。现实中采用最多的方法是通过测试误差来评价学习方法的泛化能力

泛化误差（generalization error）

$R_{exp}(\hat f)=E_p[L(Y,\hat f(X))]=\int_{X\times Y}L(y,\hat f(x))P(x,y)dxdy$，泛化误差是所学到的模型的期望风险

生成模型与判别模型

监督学习方法分为生成方法（generative approach）和判别方法（discriminative approach），所学模型分别为生成模型和判别模型

生成方法

由数据学习联合概率分布P(X,Y)，然后求出概率分布，朴素贝叶斯、隐马尔科夫模型，特点是能够还原出联合概率分布P(X,Y)，收敛速度块，当存在隐变量时，仍然可以使用

判别方法

由数据直接学习决策函数f(x)或者条件概率分布P(Y|X)作为预测模型。k-近邻、感知机、决策树、逻辑回归、最大熵、SVM、Adaboost、条件随机场，特点是直接学习条件概率或决策函数，准确率较高，简化学习问题

分类问题

评价指标

分类准确率（accuracy），正确分类样本数与总样本数之比，也就是损失函数是0-1损失时测试数据集上的准确率

对于二类分类问题：

• 四种情况（TF代表True/Flase，PN代表positive/negative）
  
  • TP，将正类预测为正类（常关注的类）
  • FN，将正类预测为负类
  • FP，将负类预测为正类
  • TN，将负类预测为负类
• 准确率， $P={TP\over TP+FP}$，预测为正类中实际正类比例
• 召回率， $R={TP\over TP+FN}$，所有正类中实际找到的正类的比例
• F1，P和R的调和均值，${2\over F_1}={1\over P}+{1\over R}\rightarrow F_1={2TP\over 2TP+FP+FN}$

标注问题

标注问题的输入是一个观察序列，输出是一个标记序列或状态序列
N为样本空间个数，n为样本序列长度，对不同的样本可以有不同的值。学习系统基于训练集构建一个模型，其表示为条件概率 $P(Y^{(1)},Y^{(2)}...Y^{(n)}|X^{(1)},X^{(2)}...X^{(n)})$，一般n远远小于N。

常用的统计方法有：隐马尔科夫模型/条件随机场。在信息提取/自然语言处理等领域被广泛使用。

回归问题

回归用于预测输入变量（自变量）和输出变量（因变量）之间的关系。回归模型正是表示从输入变量到输出变量之间映射的函数。

回归问题根据输入变量的个数可以分为一元回归和多元回归；按照输入变量和输出变量之间的关系的模型及模型的类型，分为线性回归和非线性回归

回归问题最常用的损失函数是平方损失函数，在此情况下，回归问题可以用著名的最小二乘法求解。

第2章 感知机

感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取-1/1二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，对数据进行线性划分，属于判别模型。是神经网络与支持向量机的基础。

感知机模型

感知机

$$f(x)=sign(w\cdot x+b)$$ w和b为感知机模型参数，w称为权值（weight）或权值向量（weight vector），b称为偏置（bias）。假设空间是定义在特征空间中的所有线性分类模型（linear classification model）或线性分类器（linear classifier）。几何解释：线性方程w.x+b=0对应于一个超平面S，w是超平面的法向量，b是超平面的截距（$-{b\over ||w||}$）。S称为分离超平面（separating hyperplane）。

感知机学习策略

线性可划分

如果一个数据集存在某个超平面$w\cdot x+b=0$能够将所有正实例点和负实例点完全正确地划分到超平面的两侧，则称数据集T是线性划分的。

策略

损失函数的自然选择是误分类点的总数。这样的函数不是参数w、b的连续可导函数，不易优化。另一选择是误分类点到超平面S的总距离，M为误分类点集合。其距离总和为 $$-{1\over ||w||}\sum_{x_i\in M}y_i(w\cdot x_i+b)$$ 简化得损失函数 $$L(w,b)=-\sum_{x_i \in M}y_i(w\cdot x_i+b)$$

感知机学习算法

求解损失函数最小化的w，b

$$\min_{w,b}L(w,b)=-\sum_{x_i \in M}y_i(w\cdot x_i+b)$$

采用随机梯度下降法（stochastic gradient descent）

首先任意选取一个w0，b0，然后采用梯度下降算法不断极小化目标函数，极小化过程不是一次使M中所有误分类点的梯度下降而是一次随机选取一个误分类点使其梯度下降。损失函数的梯度如下（相当于取导）： $$\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i$$ $$\nabla_bL(w,b)=-\sum_{x_i\in M}y_i$$ 随机选取一个误分类点（xi，yi），则更新公式如下，$\eta$为步长，又称学习率（learning rate） $$w = w - \eta \nabla=w+\eta y_ix_i$$ $$b=b-\eta \nabla=b+\eta y_i$$

原始形式

输入：T，学习率$\eta(0\lt\eta\le1)$
输出：w，b，模型$f(x)=sign(w\cdot x+b)$
1. 选取初始值$w_0,b_0$
2. 在训练集中选取$(x_i,y_i)$
3. 如果$y_i(w\cdot x_i+b)\le0$ $$w\leftarrow w+\eta y_ix_i$$ $$b\leftarrow b+\eta y_i$$
4. 转到2，直到训练集中无误分类点
该算法由于采用的初值不同或者选取的误分类点不同，解可能不同

收敛性

对于完全线性可分的数据集，原始形式经过有限次迭代可以得到一个将训练数据完全正确划分的分离超平面及感知机模型。感知机算法再训练数据集上的误分类次数k满足不等式 $$k \le ({R\over r})^2$$

对偶形式

将w和b初始设置为0，通过原始形式最后可得，其中$\alpha_i\ge0$ $$w=\sum_{i=1}^N\alpha_iy_ix_i$$ $$b=\sum_{i=1}^N\alpha_iy_i$$
输入：线性可划分数据集T，学习率$0<\eta\le1$
输出：$\alpha,b$,感知机模型$f(x)=sign(\sum_{j=1}^N\alpha_jy_jx_j\cdot x+b)$
1. $\alpha\leftarrow0,b\leftarrow0$
2. 在训练集中选取$(x_i,y_i)$
3. 如果$y_i(\sum_{j=1}^N\alpha_jy_jx_j\cdot x_i +b)\le0$ $$\alpha_i\leftarrow\alpha_i+\eta$$ $$b\leftarrow b +\eta y_i$$
4. 转到2直到无分类错误
可以预先将训练集中的训练实例的内积计算出来，Gram矩阵$G=[x_i\cdot x_j]_{N\times N}$

第3章 k-近邻法

k-近邻法（k-nearest neighbor，K-NN）是一种基本的分类和回归方法。k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的模型，不具有显式的学习过程。k的选择、距离度量及分类决策规则是其三个基本要素。

k-近邻算法

输入：T
输出：实例x所属的类y

1. 根据给定的距离度量，在训练集中找到与x最接近的k个点，覆盖这k个点的邻域记着$N_k(x)$
2. 在$N_k(x)$中根据分类决策规则（如多数表决）决定x的类别y： $$y=arg\max_{c_j}\sum_{x_i\in N_k(x)}I(y_i=c_j)$$

k-近邻模型

模型由三个基本要素：距离度量、k值的选择和分类决策规则决定。

特征空间中，对每个训练实例点xi，距离该点比其他点更近的所有点组成一个区域，叫做单元（cell）。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。

距离度量

$L_p$距离（Lp distance，也称Minkowski距离）

$$L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{1\over p}$$

• $p=2$时，欧式距离
• $p=1$时，曼哈顿距离
• $p=\infty$时，是各坐标间的最大值，$L_\infty(x_i,x_j)=\max_l|x_i^{(l)}-x_j^{(l)}|$

k值的选择

• k值较小
  
  • 学习的“近似”误差会变小，“估计”误差变大，对实例点非常敏感
  • 整体模型变得复杂，容易过拟合
• k值较大
  
  • 可以减小学习的“估计”误差
  • 整体模型变得简单
• 实际做法
  
  • 一般选取一个比较小的k值
  • 通常采用交叉验证法来选取k值

分类决策规则

往往采用多数表决，相当于经验风险最小

k-近邻法的实现：kd树

k-近邻最简单的方法是线性扫描，训练集非常大时，计算耗时。

构造kd树

kd树是二叉树，表示对k维空间的一个划分。相当于不断用垂直于坐标轴的超平面将k维空间划分，形成一系列的k维超矩形区域，一般选择训练实例点在选定坐标轴上的中位数为切分点，这样的kd树是平衡的。平衡kd树的搜索效率未必最优。

输入：k维空间数据集T
输出：kd树

1. 构造根节点，根节点对应于包含T的k维空间的超矩形区域，选择$x^{(1)}$为坐标轴，以T中所有数据的$x^{(1)}$坐标的中位数为切分点，将矩阵区域切分成两个子区域。切分通过与坐标轴垂直的超平面实现，根节点生成两子节点，左边为小于，右边为大于
2. 重复，对深度为j的节点，选择$x^{(l)}$为切分的的坐标轴（$l=j(mod k)+1$），同上采用中位数，对应区域切分为两个子区域
3. 直到两个子区域无实例存在时停止

搜索kd树

输入：已构造的kd树，目标点x
输出：x的最近邻

1. 在kd树中查找包含目标点的叶节点，从根出发，递归向下访问kd树，如果其当前维坐标值小于切分点的坐标，选择左子树，否则右子树
2. 以此节点为当前”最近点“
3. 递归向上回退，进行如下操作
   
   • 如果该节点保存的实例点比当前最近点距离目标点最近，则以该实例点为“当前最近点”
   • 当前最近点一定存在于该节点一个子节点对应的区域，检查该子节点的父节点的另一子节点对应的区域是否有更近的节点，具体检查另一节点对应的区域是否与以目标点为球心，以目标点与“当前最近点”的距离为半径的超球体相交，如果相交，可能在另一个子节点对应的区域内存在距离目标点更近的点，移动到另以个子节点，接着递归地进行最近邻搜索，如果不相交，向上回退
4. 回退到根节点时，搜索结束

如果实例为随机分布，kd搜索树平均计算复杂度为O(logN)

第4章 朴素贝叶斯法

前提假设为特征条件独立

朴素贝叶斯法是基于贝叶斯定理与 特征条件独立假设 的分类方法。对于给定的训练数据集，首先是基于特征条件独立假设学习输入/输出的联合概率分布；然后基于此模型，对给定的输入x，利用贝叶斯定理求出后验概率最大的输出y。

朴素贝叶斯法的学习与分类

条件概率分布有

$$P(X=x|Y=c_k) = P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k)$$ 其参数个数为$K\prod_{j=1}^nS_j$，假设特征条件独立，参数个数降为$K\sum_{j=1}^nSj$： $$=\prod_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k)$$
属于生成模型

分类时将后验概率最大的类作为x的类输出：

$$P(Y=c_k|X=x) = {P(X=x|Y=c_k)P(Y=c_k)\over\sum_k P(X=x|Y=c_k)P(Y=c_k)}$$ $$={P(Y=c_k)\prod_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k) \over\sum_k P(Y=c_k)\prod_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k)}$$
由于分母对所有类别来说是一样的，因此原类别就转变为：
$$y=arg \max_{c_k}P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)$$

期望风险

$$R_{exp}(f)=E[L(Y, f(X))]=E_X\sum_{k=1}^K[L(c_k, f(X))]P(c_k|X)$$ 由此就是使每一个x损失最小 $$f(x)=arg\min_{y\in Y}\sum_{k=1}^KL(c_k,y)P(c_k|X=x)=arg\min_{y\in Y}\sum_{k=1}^KP(y\ne c_k|X=x)$$ $$=arg\min_{y\in Y}(1-P(y=c_k|X=x))=arg\max_{y\in Y}P(y=c_k|X=x)$$ $$=arg\max_{c_k}P(c_k|X=x)$$

朴素贝叶斯法的参数估计

• 极大似然估计
  先验概率，I为指示函数
  $$P(Y=c_k)={\sum_{i=1}^NI(y_i=c_k)\over N}$$ $$P(X_{(j)}=a_{jl}|Y=c_k) = {\sum_{i=1}^NI(x_i^{(j)}=a_{jl},y_i=c_k)\over\sum_{i=1}^NI(y_i=c_k)}$$
  采用极大似然估计可能会出现所要估计的概率值为0的情况。
• 贝叶斯估计
  $$P_{\lambda}(X_{(j)}=a_{jl}|Y=c_k)={\sum_{i=1}^NI(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda\over\sum_{i=1}^NI(y_i=c_k)+S_j\lambda}$$ $$P(Y=c_k)={\sum_{i=1}^NI(y_i=c_k)+\lambda\over N + K\lambda}$$
  其中$S_j$为取值种类，$K$为列表种类。物理意思可以理解为每类默认存在 $\lambda$ 单位个值。当$\lambda=0$时就是最大似然估计，$\lambda=1$时为拉普拉斯平滑（Laplace smoothing）。

第5章 决策树

决策树是一种基本的分类和回归方法。决策树模型呈树形结构，在分类过程中，表示基于特征对实例进行分类的过程。可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。学习时，根据损失函数最小化的原则训练决策树模型。

决策树模型与学习

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由节点（node）和有向边（directed edge）组成。节点由两种类型：内部节点和叶节点，内部节点表示一个特征或者属性，而叶节点表示一个类。

可以将决策树看着一个if-then规则的集合。路径上的内部节点的特征对应着规则的条件，而叶节点的类对应着规则的结论。决策树的路径或者其对应的if-then规则集合由一个重要的性质：互斥并且完备。

决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上，将特征空间划分为互不相交的单元或者区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。一条路径对应划分的一个单元。可以定义为P(Y|X)，X取值于给定划分下单元的集合，Y取值于类的集合。

决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练集数据不矛盾的决策树可能有多个，也可能一个也没有。需要的是与训练数据矛盾较小的决策树，同时具有很好的泛化能力。

损失函数通常是正则化的极大似然函数。从所有可能的决策树中选取最优决策树是NP完全问题，现实中往往采用启发式方法，近似求解，获得次最优。算法通常递归选择最优特征，根据该特征对训练集进行划分，使得对各个子数据集由一个最好的分类的过程。这一过程对应于特征空间的划分，也对应于决策树的构建。

该过程生成的决策树可能有过拟合现象，需要对树从下到上进行剪枝，将树变简单，有更好泛化能力。具体操作就是去掉过于细化的叶节点将其回退到父节点或更高，然后将其改为叶节点。

特征数量很多，可以在预处理时对特征进行选择。

特征选择

特征选择在于选取对训练数据具有分类能力的特征。

信息增益

熵（entropy）：表示随机变量不确定性的度量，对数通常以2或者e作为底，比特（bit）或者纳特（nat）。熵只依赖于X的分布，与取值无关。

$$H(X)=-\sum_{i=1}^np_i\log p_i$$ $$0\le H(x)\le \log n$$
条件熵：表示在已知随机变量X的条件下随机变量Y的不确定性，定义为X给定条件下Y的条件概率分布的熵对X的数学期望 $$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)$$

当熵和条件熵的概率由数据估计（特别是极大似然估计）得到时，分别称为经验熵和经验条件熵

信息增益（information gain）：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵(D)与特征A给定条件下D的经验条件熵H(D|A)之差，表示由于特征A而使得数据集D的分类的不确定性减少的程度

$$g(D,A)=H(D)-H(D|A)$$

信息增益比

使用信息增益容易选择取值较多的特征，使用信息增益比进行校正。
信息增益比：定义为其信息增益与训练数据集关于特征A的值的熵之比

$$g_R(D,A)={g(D,A)\over H_A(D)}$$ $$H_A(D)=-\sum_{i=1}^n{|D_i|\over|D|}log_2{|D_i|\over|D|};n为特征A取值个数$$

决策树的生成

ID3算法

输入：训练数据集D，特征集A，阀值e；
输出：决策树T

1. D中属于同一类，则T为单节点树，返回T
2. 若A为空，为单节点树，将D中实例树最大的类作为类标记，返回T
3. 计算各特征的信息增益，选择增益最大的特征Ag
4. 如果Ag的增益小于e，则构建单节点树，选择最多类，返回
5. 否则对Ag的每一个取值划分D为子集Di，将Di中实例数最大的类作为标记，构建子节点，由节点及其子节点构建成树T，返回T
6. 对第i个子节点，Di为训练集，A-{Ag}为特征集，递归调用，得到子树Ti

ID3算法只有树的生成，容易产生过拟合

C4.5算法

C4.5使用信息增益比来选择特征

决策树的剪枝

过拟合的原因是学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决方法是对已生成的决策树进行简化。

剪枝（pruning）：在决策树学习中将已生成的树进行简化的过程，从已生成的树上裁掉一些子树和节点，并将其根节点或父亲节点作为新的叶子节点。通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。

损失函数定义：叶子节点个数$|T|$，$t$是叶子节点，其有$N_t$个样本点，其中$k$类$N_{tk}$个，$H_t(T)$为叶子节点$t$上的经验熵，$\alpha>=0$为参数。

$$C_{\alpha}(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$$ $$H_t(T)=-\sum_k{N_{tk}\over N_t}log{N_{tk}\over N_t}$$ $$C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}log{N_{tk}\over N_t}$$
$C(T)$用以表示模型对于训练数据的预测误差，$|T|$用以表示模型复杂度，$\alpha$控制两者之间的影响。较大的$\alpha$促使选择较简单的模型，较小的促使选择较复杂的模型。

输入：生成算法产生的树T，以及参数alpha
输出：修建后的树Tx

1. 计算每个节点的经验熵
2. 递归从树的叶子节点向上回缩，设回缩前后的整体树分布为Tb，Ta，其对应损失函数分别为Cx(Tb),Cx(Ta)，如果Cx(Ta)<=Cx(Tb)则进行剪枝，将父亲节点变成新的叶子节点
3. 返回2，直到不能继续为止

CART算法

CART（classification and regression tree）分类与回归树，是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法，其是二叉树，左分支为取值为是的分支，右分支是取值为否的分支。

两步：

1. 生成：基于训练数据集生成决策树，生成的决策树要尽量大
2. 剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，以损失函数最小为剪枝标准

生成

对回归树使用平方误差最小化准则，对分类树使用基尼指数最小化准则，进行特征选择，生成二叉树。

回归树

一个回归树对应着输入空间（即特征空间）的一个划分以及在划分单元上的输出值。于是模型可表示为

$$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$$
使用平方误差$\sum_{x_i\in R_m}(y_i-f(x_i))^2$来表示对于训练数据的预测误差，则有最优为均值 $$\hat c_m=ave(y_i|x_i\in R_m)$$
采用启发式的方法，选举第j个变量$x^{(j)}$和它的取值s，作为切分变量和切分点，定义区域 $$R_1(j,s)=\{x|x^{(j)}\le s\}和R_2(j,s)=\{x|x^{(j)}\gt s\}$$ 具体求解 $$min_{j,s}[min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2 + min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$$ 这样的回归树通常被称为最小二乘回归树。

分类树

基尼指数

假设K个类，样本属于第k类的概率为$p_k$，则概率分布的基尼指数定义为 $$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$$
样本集合D根据A是否可以取某一可能值$a$被分割成D1和D2两个部分，即 $$D_1=\{(x,y)\in D|A(x)=a\}, D_2=D-D_1$$
在特征A的条件下，集合D的基尼指数定义为 $$Gini(D,A)={|D_1|\over |D|}Gini(D_1)+{|D_2|\over |D|}Gini(D_2)$$
基尼系数用来表示集合的不确定性，其值越大，不确定性也越大

生成算法递归对每个特征可能取值将样本空间进行划分成两部分，分别计算其基尼指数，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点
算法停止计算的条件是结点中的样本个数小于预定阀值，或样本集的基尼指数小于预定阀值，或者没有更多特征

CART剪枝

由两步组成，首先从生成算法产生的决策树底端开始不断剪枝，直到根结点，形成子树序列$\{T_0, ... T_n\}$,然后通过交叉验证法在独立的验证数据集上对子树进行测试，选择最优子树。

原理

子树的损失函数$C_\alpha(T)=C(T)+\alpha|T|$，C为预测误差（如基尼指数、平方误差）
对于任一$\alpha$，必定存在使损失函数最小的唯一最优子树
可以通过增加$\alpha$产生一系列的子树
$\alpha$较小时，有$C_\alpha(T_t)<C_\alpha(t)$，当$\alpha$增大时，在某一$\alpha$有 $C_\alpha(T_t)=C_\alpha(t)$，$T_t$表示以t为根的子树，t表示单结点树，$C_\alpha(t)=C(t)+\alpha，C_\alpha(T_t)=C(T_t)+\alpha|T_t|$
因此只要$\alpha={C(t)-C(T_t)\over |T_t|-1}$，$T_t$和t有相同损失函数，而t结点少，应该进行剪枝

剪枝算法

1). 设k=0，T=$T_0$
2). 设$\alpha=+\infty$
3). 自下而上地对各内部结点t计算$C(T_t)，|T_t|$，以及 $$g(t)={C(t)-C(T_t)\over |T_t|-1}$$ $$\alpha=min(\alpha,g(t))$$ $T_t$表示以t为根节点的子树，$C(T_t)$是对训练数据的预测误差，$|T_t|$是$T_t$的叶结点个数
4). 自上而下访问内部结点t，如果有$g(t)=\alpha$，进行剪枝，并对叶节点t以多数表决法决定其类，得到树T
5). 设k=k+1，$\alpha_k=\alpha，T_k=T$
6). 如果T不是由根结点单独构成的树，则回到4
7). 采用交叉验证法在子树序列$T_0,T_1...,T_n$中选取最优子树$T_\alpha$

汇总

算法	特征选择	树型	特征删除	剪枝	损失函数
ID3	信息增益	多叉树	是	定义多参数选择	$C_{\alpha}(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$
C4.5	信息增益比	多叉树	是	定义多参数选择	$C_{\alpha}(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$
CART	基尼指数	二叉树	否	递归计算选择$\alpha$验证	$C_\alpha(T)=C(T)+\alpha|T|$

第6章 逻辑斯谛回归与最大熵模型

逻辑斯谛回归模型

逻辑斯谛分布

X为连续随机变量，X具有如下分布函数和密度函数，其中$\mu$为位置参数，$\gamma$为形状参数 $$F(x)=P(X\le x)={1\over 1+{e^{-(x-\mu)/\gamma}}}$$ $$f(x)=F'(x)={e^{-(x-\mu)/\gamma}\over\gamma( 1+{e^{-(x-\mu)/\gamma})^2}}$$ 密度曲线在中间较大，两侧较小，有$F(-x+\mu)-1/2=-F(x+\mu)+1/2$

二项逻辑斯谛回归模型

是如下的条件概率分布 $$P(Y=1|x)={\exp(w\cdot x+b)\over 1+\exp(w\cdot x+b)}$$ $$P(Y=0|x)={1\over 1+\exp(w\cdot x+b)}$$ w为权重，b为偏置，添加$x_0=1$，将扩充b到w中
几率是指一个事件发生的概率与该事件不发生的概率的比值（odds）。则有对数几率(log odds)或logit函数 $$logit(p)=\log({p\over 1-p})=w\cdot x$$

模型参数估计

采用极大似然估计法估计模型参数，设$P(Y=1|x)=\pi(x),P(Y=0|x)=1-\pi(x)$
似然函数为$\prod_{i=1}^N[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}$
对数似然函数为 $$L(w)=\sum_{i=1}^N[y_i\log\pi(x_i)+(1-y_i)\log(1-\pi(x_i))]$$ $$=\sum_{i=1}^N[y_i\log{\pi(x_i)\over (1-\pi(x_i))}+\log(1-\pi(x_i))]$$ $$=\sum_{i=1}^N[y_i(w\cdot x_i)-\log(1+\exp(w\cdot x_i))]$$

多项逻辑斯谛回归模型

模型为 $$P(Y=k|x)={\exp(w_k*x)\over 1+\sum_{k=1}^{K-1}\exp(w_k\cdot x)},k=1...K-1$$ $$P(Y=K|x)={1\over 1 + \sum_{k=1}^{K-1}\exp(w_k\cdot x)}$$

最大熵模型

最大熵原理

学习概率模型时，在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。可表述在满足约束条件的模型集合中选取熵最大的模型。
直观认识：选择的模型必须满足已有事实，不确定的部分都是“等可能性的”。通过熵的最大化来表示等可能性

推理

给定训练数据集，可以确定联合分布P(X, Y)和边缘分布P(X)的经验分布 $$\hat P(X=x, Y=y)={V(X=x, Y=y)\over N};\hat P(X=x)={V(X=x)\over N}$$ 用特征函数（feature function）f(x, y)描述输入x和输出y之间的某一个事实 $$f(x,y) = \begin{cases} 1, & x与y满足某一事实 \\[2ex] 0, & 否则 \end{cases}$$
特征函数f关于经验分布的期望值有 $$E_{\hat P}(f)=\sum_{x,y}\hat P(x,y)f(x,y)$$
特征函数f关于模型与经验边缘分布的期望值有 $$E_{P}(f)=\sum_{x,y}\hat P(x)P(y|x)f(x,y)$$
由两者相等有 $$\sum_{x,y}\hat P(x,y)f(x,y) = \sum_{x,y}\hat P(x)P(y|x)f(x,y)$$ 假设有n个特征函数就有n个约束条件

定义

假设满足所有约束条件的模型集合为 $$C = \{P\in \mathcal P|E_{\hat P}(f_i)=E_{P}(f_i),i=1,2...n\}$$ 定义再条件概率分布P(Y|X)上的条件熵为 $$H(P)=-\sum_{x,y}\hat P(x)P(y|x)\log P(y|x)$$ 模型集合中H(P)最大的模型称为最大熵模型，式子中为自然对数

学习

即为求解 $$\max_{P\in C} H(P)\ \ \ s.t.\ E_{\hat P}(f_i)=E_{P}(f_i),\sum_{y}P(y|x)=1$$
即为求解 $$\min_{P\in C} -H(P)\ \ \ s.t.\ E_{\hat P}(f_i)=E_{P}(f_i),\sum_{y}P(y|x)=1$$
定义拉格朗日函数L(P,w) $$L(P, w)=-H(P)+w_0(1-\sum_{y}P(y|x))+\sum_{i=1}^nw_i(E_{\hat P}(f_i)-E_{P}(f_i))$$
最优化原始问题为$\min_{P\in C}\max_w L(P,w)$，对偶问题为$\max_w\min_{P\in C}L(P,w)$
求其对P(y|x)偏导并令其为0有 $$\sum_{x,y}\hat P(x)(\log P(y|x)+1-w_0-\sum_{i=1}^nw_if_i(x,y))=0$$
有 $$P(y|x)=\exp(\sum_{i=1}^nw_if_i(x,y)+w_0-1)={\exp(\sum_{i=1}^nw_if_i(x,y))\over \exp(1-w_0)}$$
由$\sum_yP(y|x)=1$有 $$P_w(y|x)={1\over Z_w(x)}\exp(\sum_{i=1}^nw_if_i(x,y));Z_w(x)=\sum_y\exp(\sum_{i=1}^nw_if_i(x,y))$$
然后求解极大化问题 $$w^*=arg\max_w\psi(w)=arg\max_w\min_{P\in C}L(P, w)=arg\max_w L(P_w,w)$$

极大似然估计

条件概率分布的对数似然表示为 $$L_{\hat P}(P_w)=\log\prod_{x,y}P(y|x)^{\hat P(x,y)}=sum_{x,y}\hat P(x,y)\log P(y|x)$$
由其为最大熵有 $$=\sum_{x,y}\hat P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_x\hat P(x)\log Z_w(x)$$
与$\psi(w)$比较有 $$\psi(w)=L_{\hat P}(P_w)$$ 于是证明看最大熵模型学习中的对偶函数极大化等价于最大熵模型的极大似然估计

最优化方法

改进的迭代尺度法

对于参数由w改变为$w+\delta$，其对数似然改变为 $$L(w+\delta)-L(w)=\sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta_if_i(x,y)-\sum_x\hat P(x)\log {Z_{w+\delta}(x)\over Z_w(x)}$$
利用不等式$-\log\alpha \ge 1-\alpha,\alpha>0$ $$\ge sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\hat P(x){Z_{w+\delta}(x)\over Z_w(x)}$$ $$\ge sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\hat P(x)\sum_yP_w(y|x)\exp\sum_{i=1}^n\delta_if_i(x,y)$$
IIS试图一次只优化其中一个变量$\delta_i$，而固定其他变量$\delta_j$
令$f'(x,y)=\sum_{i}f_i(x,y)$，表示所有特征再(x,y)出现的次数

IIS算法（改进的迭代尺度法）

输入：特征函数f；模型分布$\hat P(X,Y)$，模型$P_w(y|x)$
输出：最优参数值$w_i^*$;最优模型$P_{w^*}$

1. 对所有$i\in{1,2...n}$,取初值$w_i=0$
2. 对每一$i\in{1,2...n}$:
   a. 令$\delta_i$是方程 $$\sum_{x,y}\hat P(x)P(y|x)f_i(x,y)\exp(\delta_if'(x,y))=E_{\hat P}(f_i)$$ 的解$f'(x,y)=\sum_{i=1}^nf_i(x,y)$
   b. 更新$w_i$值：$w_i\leftarrow w_i+\delta_i$
3. 如果不是所有$w_i$都收敛，重复2

拟牛顿法

todo

第7章 支持向量机

基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使其有别于感知机；其还包含核技巧，使它成为实质上的非线性分类器。

线性可分支持向量机与硬间隔最大化

输入空间为欧式空间或离散空间，特征空间为欧式空间或者希尔伯特空间。线性可分支持向量机/线性支持向量机假设这两个空间的元素一一对应，可通过映射，同理，非线性支持向量机通过非线性映射完成。支持向量机的学习是在特征空间进行的。

分离超平面对应的方程为 $w\cdot x+b = 0$，将特征空间分成两部分，法向量指向的一侧为正类，另一侧为负类。

线性可分支持向量机

给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习而得的分离超平面为 $$w^*\cdot x + b^*=0$$ 以及相应的分类函数为 $$f(x)=sign(w^*\cdot x+b^*)$$ 称为线性可分支持向量机。

函数间隔

一个点距离分类超平面的远近可以表示分类预测的确信程度。给定数据集T和超平面(w,b)，定义超平面关于样本$(x_i,y_i)$的函数间隔为 $$\hat r_i=y_i(w\cdot x_i +b)$$ 定义超平面关于Ｔ的函数间隔为超平面关于Ｔ中所有样本点的函数间隔最小值 $$\hat r=\min_{i=1,...,N}\hat r_i$$
如果同比例改变ｗ和ｂ，超平面未改变而函数间隔改变了。

几何间隔

对于Ｔ和(w,b)，定义超平面关于样本点$(x_i,y_i)$的几何间隔为 $$r_i=y_i({w\over ||w||}\cdot x_i+{b\over ||w||})$$ 定义超平面关于数据集Ｔ的几何间隔为超平面关于Ｔ中所有点的几何间隔的最小值 $$r=\min_{i=1,...,N}r_i$$

函数间隔与几何间隔的关系

$$r={\hat r\over ||w||}$$ 当||w||=1时，两者相同。

间隔最大化

对数据集找出几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。

求解问题

$$\max_{w,b}r$$ $$s.t\space\space\space y_i({w\over ||w||}\cdot x_i+{b\over ||w||})\ge r,i=1,2,...N$$
可以变换为 $$\max_{w,b}{\hat r\over||w||}$$ $$s.t\space\space\space y_i({w}\cdot x_i+{b})\ge \hat r,i=1,2,...N$$
由于函数间隔$\hat r$的取值不影响超平面，其等同于ｗｂ同时改变，因此可以设其为１，同时最大化$1\over ||w||$与最小化${1\over 2}||w||^2$等价，于是变换为 $$\min_{w,b}{1\over 2}||w||^2$$ $$s.t\space\space\space y_i({w}\cdot x_i+{b}) - 1\ge 0,i=1,2,...N$$

解的性质

• 存在性
  由于线性可分，因此必定存在可行解，又由于既有正类点也有负类点，因此$w^*\ne 0$
• 唯一性
  假设存在两个解，则有$||w_1^*||=||w_2^*||=c$，令$w={w_1^*+w_2^*\over 2},b={b_1^*+b_2^*\over 2}$，可知其必然为解，则有 $$c\le ||w||\le 1/2||w_1^*||+1/2||w_2^*||=c$$ 于是有$||w||= 1/2||w_1^*||+1/2||w_2^*||$，从而有$w_1^*=\lambda w_2^*,|\lambda|=1$，如果$\lambda = -1$则w=0,必有$\lambda=1$，可得w唯一，根据间隔为１的点，可以证明b唯一

支持向量和间隔边界

支持向量

是使约束条件等号成立即$y_i(w\cdot x_i+b)-1=0$的点，$y_i=1$为正实例点

间隔

间隔依赖于分离超平面的法向量w，等于${2\over ||w||}$，两条分割线称为间隔边界

决定超平面时只有支持向量起作用，其他实例点不起作用。支持向量的个数一般很少，支持向量机是由很少的重要的训练样本决定的。

学习的对偶算法

拉格朗日函数，引进拉格朗日乘子$\alpha_i\ge0,i=1,...N$,有

$$L(w,b,\alpha)={1\over 2}||w||^2-\sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i$$
原始问题的对偶问题是 $$\max_{\alpha}\min_{w,b}L(w,b,\alpha)$$
针对w,b求偏导并等于０有 $$w-\sum_{i=1}^N\alpha_iy_ix_i=0;\sum_{i=1}^N\alpha_iy_i=0$$
将结果代入有 $$\min_{w,b}L(w,b,\alpha)=-{1\over 2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i$$
再次转换有 $$\min_\alpha {1\over 2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i$$ $$s.t.\ \ \ \sum_{i=1}^N\alpha_iy_i=0;\alpha_i\ge 0,i=1,2...N$$
则求解有 $$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$$ 存在下标ｊ，有$\alpha_j>0$ $$b^*=y_j-\sum_{i=1}^N\alpha_j^*y_i(x_i\cdot x_j)$$ 分类决策函数可以写成 $$f(x)=sign(\sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*)$$ w和ｂ只依赖于$\alpha_i>0$的那些点，这些点称为支持向量

软间隔最大化

线性不可分意味着某些样本点不满足函数间隔大于等于１的约束条件。针对每个样本点引入一个松弛变量$\xi_i\ge0$，使得函数间隔加上松弛变量大于等于１，约束添加就变为$y_i(w\cdot x_i+b)\ge1-\xi_i$,对每个松弛变量支付代价，则目标函数由$1/2||w||^2$变为

$${1\over 2}||w||^2+C\sum_{i=1}^N\xi_i;C>0为惩罚参数$$ 前项使间隔尽量大，后项使得误分类的点尽量少

支持向量

对应于$\alpha_i^*>0$的点，其或在间隔边界上，或者间隔边界与分离超平面之间，或在误分类的另一侧。其实例点到分割面的距离为$\xi_i\over ||w||$

• $\alpha_i^*<C$，则有$\xi_i=0$，存在分界上
• $\alpha_i^*=C且0<\xi_i<1$，则分类正确，位于超平面与间隔之间
• $\alpha_i^*=C且\xi_i=1$，则其再分离超平面上
• $\alpha_i^*=C且\xi_i>1$，则其位于分离超平面误分一侧

合页损失函数

另外一种解释，就是最小化如下目标函数

$$\sum_{i=1}^N[1-y_i(w\cdot x_i+b)]_++\lambda||w||^2$$ 第一项为经验损失或经验风险，小标＋表示以下取正值的函数 $$[z]_+ = \begin{cases} z, & z>0 \\ 0, & z\le0 \end{cases}$$
令$[1-y_i(w\cdot x_i+b)]_+=\xi_i$，则有 $$\min_{w,b}\sum_{i=1}^N\xi_i+\lambda||w||^2$$
令$\lambda={1\over 2C}$，则有 $$\min_{w,b}{1\over C}({1\over 2}||w||^2+C\sum_{i=1}^N\xi_i)$$
与前面的式子等价
合页损失函数不仅要分类正确，而且确信度要足够高才会损失为０，合页损失函数对学习有更高的要求

非线性支持向量机与核函数

核技巧

如果能用超曲面将正负例正确分开的问题称为非线性可分问题。
解决方法是进行非线性变换，将非线性问题转为线性问题。

核函数

设$\mathcal X$是输入空间（欧式空间$R^n$的子集或离散集合），又设$\mathcal H$为特征空间（希尔伯特空间），如果存在一个从$\mathcal X$到$\mathcal H$的映射 $$\phi(x):\mathcal X\rightarrow\mathcal H$$ 使得对所有$x,z\in\mathcal X$，函数K(x,z)满足 $$K(x,z)=\phi(x)\cdot\phi(z)$$ 则称Ｋ为核函数，$\phi(x)$为映射函数

核技巧的思想是，在学习和预测中只定义核函数Ｋ，而不显式地定义映射函数$\phi$

在线性支持向量机的对偶问题中，无论是母女函数还是决策函数都只涉及输入实例之间的内积。在对偶问题的目标函数中的内积可以使用核函数$K(x_i,x_j)=\phi(x_i)\cdot\phi(x_j)$来代替。目标函数就变为

$$W(\alpha)=1/2\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i$$
分类函数也可以变为 $$f(x)=sign(\sum_{i=1}^{N_S}\alpha_i^*y_iK(x_i,x)+b^*)$$

正定核

设$\mathcal X\subset R^n，K(x,z)$是定义在$\mathcal X ×\mathcal X$上的对称函数，如果对任意$x_i\in\mathcal X,i=1,2...m,K(x,z)$对应的Gram矩阵

$$K=[K(x_i,x_j)]_{m*m}$$ 是半正定矩阵，则称K(x,z)是正定核

常用核函数

• 多项式核函数(pilynomial kernel function)
  $K(x,z)=(x\cdot z+1)^p$
  决策函数为$f(x)=sign(\sum_{i=1}^{N_s}\alpha_i*y_i(x_i\cdot x+1)^p+b^*)$
• 高斯核函数(Gaussian Kernel funciton)
  $K(x,z)=exp(-{||x-z||^2\over 2\sigma^2})$
  对应支持向量机是高斯径向基函数$f(x)=sign(\sum_{i=1}^N_s\alpha_i^*y_i\exp(-{||x-x_i||^2\over 2\sigma^2})+b^*)$
• 字符串核函数

序列最小最优化算法

SMO算法要解如下凸二次规划的对偶问题

$$\min_\alpha{1\over 2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i$$ $$s.t.\ \ \sum_{i=1}^N\alpha_iy_i=0;0\le\alpha_i\le C,i=1,2,...N$$

是一种启发式算法，如果所有变量都满足KKT条件，则这个就是最优解，否则选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。该问题的解应该更接近原始二次规划问题的解，会使得原始二次规划的目标函数值变得更小。子问题有两个变量，一个是违反KKT条件最严重的那个，另一个由约束条件自动确定。

两个变量二次规划求解方法

即是求解

$$\min_{\alpha_1,\alpha_2}={1\over 2}K_{11}\alpha_1^2+{1\over 2}K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_iK_{i1}+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK_{i2}$$ $$s.t.\ \alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^Ny_i\alpha_i=\xi;0\le\alpha_i\le C,i=1,2$$
当$y_1\ne y_2$时，$\alpha_1-\alpha_2=k$，当$y_1= y_2$时，$\alpha_1+\alpha_2=k$

第8章 提升方法

提升方法AdaBoost算法

提升方法的基本思路

基于思想，对于复杂任务来说，多个专家的判断进行适当的综合得出的判断比其中一个单独要好。

强可学的（strongly learnable）

在概率近似正确学习的框架中，一个概念（一个类），如果存在一个多项式的学习算法能够学习它，而且正确率很高。

弱可学的（weakly learnable）

在概率近似正确学习的框架中，一个概念（一个类），如果存在一个多项式的学习算法能够学习它，而且正确率仅比随机猜测略好。强可学与弱可学是等价的。

大多数的提升方法都是改变训练数据的概率分布（调整训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

2 questions

1）每一轮如何改变训练数据的权值或概率分布；2）如何将弱分类器合成一个强分类器；

AdaBoost算法

输入：T，Y
输出：最终分类器G（x）

1. 初始化训练数据的权值分布，设为1/N $$D_1 = (w_{11},w_{12},...,w_{1N}),\space\space w_{1i}={1\over N},i=1,2,..,N$$
2. 对m=1，...，M
   
   1. 使用具有权值分布Dm的训练数据集学习，得到基本分类器 $$G_m(x):X\rightarrow \{-1,+1\}$$
   2. 计算Gm在训练数据集上的分类误差率 $$e_m=P(G_m(x_i)\ne y_i)=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\ne y_i)$$
   3. 计算Gm的系数（自然对数），em越小，alpha越大，其最终结果中权值也越大 $$\alpha_m={1\over 2}\log{1-e_m\over e_m}$$
   4. 更新训练数据集的权值分布 $$D_{m+1}=(w_{m+1,1},...,w_{m+1,N})$$ $$w_{m+1,i}={w_{mi}\over Z_m}\exp(-\alpha_my_iG_m(x_i)),i=1,2,...,N$$ Zm为规范化因子 $$Z_m=\sum_{i=1}^Nw_{mi}\exp(-\alpha_my_iG_m(x_i))$$ 相当于 $$w_{m+1,i}=\begin{cases} {w_{mi}\over Z_m}e^{-\alpha_m}, & \text{G_m(x_i)=y_i} \\ {w_{mi}\over Z_m}e^{\alpha_m}, & \text{G_m(x_i)!=y_i} \end{cases}$$ 错误分类的权值得以扩大，误分类样本权值被扩大 $$e^{2\alpha_m}={e_m\over 1-e_m}$$
3. 构建基本分类器的线性组合 $$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$ 最终分类器为 $$G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_m(x))$$

AdaBoost算法的训练误差分析

最终分类其的训练误差界

$${1\over N}\sum_{i=1}^NI(G(x_i)\ne y_i)\le {1\over N}\sum_i\exp(-y_if(x_i))=\prod_mZ_m$$ $$\prod_{m=1}^MZ_m=\prod_{m=1}^M[2\sqrt{e_m(1-e_m)}]=\prod_{m=1}^M[2\sqrt{(1-4r_m^2)}\le \exp(-2\sum_{m=1}^Mr_m^2),r_m={1\over 2}-e_m$$

AdaBoost算法的解释

可以认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法时的二类分类学习算法。

提升树

提升树模型

提升树是采用加法模型（即基函数的线性组合）与前向分布算法，以决策树为基函数的提升方法。对分类问题是二叉分类树，对回归问题是二叉回归树。

$$f_M(x)=\sum_{m=1}^MT(x;\theta_m)$$ $T表示决策树，\theta表示决策树参数，M为树的个数$

提升树算法

采用前向分布算法，第m步模型为

$$f_m(x)=f_{m-1}(x)+T(x;\theta_m)$$ 通过经验风险极小化确定下一棵决策树的参数 $$\hat \theta m=arg \min_{\theta_m}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\theta_m))$$

回归问题的提升树算法
输入：训练数据集T
输出：提升树fm

1. 初始化$f_0(x)=0$
2. 对m=1，...，M
   
   1. 计算残差 $$r_{mi}=y_i-f_{m-1}(x_i)$$
   2. 拟合残差$r_{mi}$学习一个回归树，得到$T(x;\theta_m)$
   3. 更新$f_m(x)=f_{m-1}(x)+T(x;\theta_m)$
3. 得到回归问题提升树 $$f_M(x)=\sum_{m=1}^MT(x;\theta_m)$$

梯度提升

对一般损失函数而言，每一步优化可能不太容易，利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型中的值

$$-[{\partial L(y,f(x_i))\over\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$$ 作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

输入：训练集T，损失函数L
输出：回归树f

1. 初始化 $$f_0(x)=arg \min_c\sum_{i=1}^NL(y_i,c)$$
2. 对m=1,2..，M
   
   1. 对i=1..N计算 $$r_{mi}=-[{\partial L(y,f(x_i))\over\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$$
   2. 对rmi拟合一个回归树，得到第n棵树的叶子节点区域Rmj，j=1...J
   3. 对j=1,2...J，计算 $$c_{mj}=arg\min_c\sum_{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$$
   4. 更新$f_m(x)=f_{m-1}(x)+\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$
3. 得到回归树 $$\hat f(x)=f_M(x)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$$

第9章 EM算法及其推广

EM算法是一种迭代算法，用于含有隐变量（hidden variable）的概率模型参数的极大似然估计，或者极大后验概率估计。每次迭代两步完成，E步，求期望（expectation），M步，求最大（maximization）。所以称为期望极大算法（expectation maximization algorithm）。

EM算法的引入

EM算法

三硬币模型

先根据A的正反面选择B或者C，然后正面1负面0，独立n次，出现序列已知，估计3个硬币的正面出现概率
$$P(y|\theta)=\sum_zP(y,z|\theta)=\sum_zP(z|\theta)P(y|z,\theta)=\pi p^y(1-p)^{1-y}+(1-\pi)q^y(1-q)^{1-y}$$ y为0或者1，z是隐变量，表示A的结果；$\theta=(\pi,p,q)是模型参数$，进而 $$P(Y|\theta)=\prod_{j=1}^n[\pi p^{y_j}(1-p)^{1-y_j}+(1-\pi)q^{y_j}(1-q)^{1-y_j}]$$ 考虑求模型参数的极大似然估计 $$\hat \theta=arg\max_\theta\log P(Y|\theta)$$

EM算法

输入：观测变量数据Y，隐变量数据Z，联合分布$P(Y,Z|\theta)$，条件分布$P(Z|Y,\theta)$
输出：模型参数
1. 选择参数的初始值
2. E步：计算 $$Q(\theta,\theta^{(i)})=E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]$$ $$=\sum_Z\log P(Y,Z|\theta)P(Z|Y,\theta^{(i)})$$
3. M步：求使Q极大的theta $$\theta^{(i+1)}=arg\max_\theta Q(\theta,\theta^{(i)})$$
4. 重复第2步和第3步，直到收敛
说明：初始可以随意指定，但是算法对初值敏感；停止条件一般是对于较小的正数 $$||\theta^{(i+1)-\theta^{(i)}}||<\epsilon_1 或 ||Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i-1)})||<\epsilon_2$$

第10章 隐马尔科夫模型

用于标注问题，属于生成模型。

基本概念

隐马尔科夫模型

是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔科夫链随机生成的状态的序列称为状态序列（state sequence）；每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列（observation sequence）。序列的每个位置又可以看着一个时刻。
隐马尔科夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定。定义如下：Q是所有可能状态的集合，V是所有可能的观测的集合 $$Q=\{q_1,q_2,...,q_N\},V=\{v_1,v_2,...,v_M\}$$ I是长度为T的状态序列，O是对应的观测序列 $$I=\{i_1,i_2,...,i_T\},O=\{o_1,o_2,...,o_T\}$$ A是状态转移概率矩阵 $$A=[a_{ij}]_{N\times N}$$ 其中 $$a_{ij}=P(i_{t+1}=q_j|i_t=q_i),i=1,2,...N;j=1,2,...N$$ 是在时刻t处于状态qi的条件下在时刻t+1转移到状态qj的概率，B是观测矩阵 $$B=[b_j(k)]_{N\times M}$$ 其中 $$b_j(k)=P(o_t=v_k|i_t=q_j),k=1,2,...M;j=1,2,...N$$ 是在时刻t处于状态qj的条件下生成观测vk的概率
$\pi$是初始状态概率向量 $$\pi=(\pi_i)$$ 其中， $$\pi_i=P(i_1=q_i),i=1,2,...N$$
隐马尔科夫模型由初始状态概率向量pi，状态转移概率矩阵A，观测概率矩阵B决定，称为该模型的三要素 $$\lambda = (A,B,\pi)$$

做了两个基本假设：

• 齐次马尔科夫假设，假设任意时刻t的状态只依赖于前一时刻的状态，与其他时刻的状态和观测无关，也与时刻无关 $$P(i_t|i_{t-1},o_{t-1},...i_1,o_1)=P(i_t|i_{t-1}),t=1,2,...T$$
• 观测独立性假设，假设任意时刻的观测只依赖于该时刻的状态，与其他观测和状态无关 $$P(o_t|i_T,o_T,i_{T-1},o_{T-1},...,i_1,o_1)=P(o_t|i_t)$$

观测序列的生成过程

输入：隐马尔科夫模型$\lambda=(A,b,\pi)$，观测序列长度Ｔ
输出：观测序列Ｏ

1. 按照初始状态分布$\pi$产生状态$i_1$
2. 令t=1
3. 按照状态it的观测概率分布$b_{i_t}(k)$生成$o_t$
4. 按照状态it的状态转移概率分布$a_{i_ti_{t+1}}$产生状态$i_{t+1}，i_{t+1}=1,2...N$
5. 令t=t+1；如果t < T，转步3，否则停止

3个基本问题

• 概率计算问题，已知模型和O，求$P(O|\lambda)$
• 学习问题，已知O，估计模型$\lambda$参数，即使O出现的概率最大
• 预测问题，也称为解码问题，已知模型和观测序列，即给定观测序列，求最可能的状态序列

概率计算算法

直接计算算法

计算量很大，是$O(TN^T)$，计算不可行

前向算法

前向概率

给定模型，定义到时刻t部分观测序列为o1～ot且状态为qi的概率为前向概率，记住 $$\alpha_t(i)=P(o_1,o_2,...o_t,i_t=q_i|\lambda)$$

观测序列概率的前向算法

输入：隐马尔科夫模型lambda，观测序列O
输出：观测序列概率$P(O|\lambda)$
1）初值 $$\alpha_1(i)=\pi_ib_i(o_1)，i=1,2,..,N$$
2)递推，对t=1,2,...,N-1 $$\alpha_{t+1}(i)=[\sum_{j=1}^N\alpha_t(j)a_{ji}]b_i(o_{t+1})，i=1,2,...N$$
3）终止 $$P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)$$

减少计算量的原因在于每次直接计算引用前一时刻的计算结果，避免重复计算。计算量是$O(N^2T)$的。

后向算法

后向概率

给定模型，定义在t时刻状态为qi的条件下，从t+1到T的部分观测序列为ot+1,...oT的概率为后向概率，记住 $$\beta_t(i)=P(t_{t+1},o_{t+2},...,o_T|i_t=q_i,\lambda)$$

后向算法

输入：模型，观测序列O
输出：观测概率
1） $$\beta_T(i)=1,i=1,2,...N$$
2）对t=T-1，T-2，...1 $$\beta_t(i)=\sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j),i=1,2,..N$$
3） $$P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)$$

统一

$$P(O|\lambda)=\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j),t=1,2,...T-1$$

部分概率与期望值的计算

• 给定模型和观测，在时刻t处于状态qi的概率 $$r_t(i)={\alpha_t(i)\beta_t(i)\over P(O|\lambda)}={\alpha_t(i)\beta_t(i)\over \sum_{j=1}^N \alpha_t(j)\beta_t(j)}$$
• 给定模型和观测，在时刻t处于qi且在时刻t+1处于qj的概率 $$\epsilon_t(i,j)={P(i_t=q_i,i_{t+1}=q_j,O|\lambda) \over P(O|\lambda)}={\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)\over \sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}$$
• 将对各个时刻求和，可以得到有用的期望值
  
  • 在观测O下状态i出现的期望值 $$\sum_{t=1}^Tr_t(i)$$
  • 在观测O下由状态i转移的期望值 $$\sum_{t=1}^{T-1}r_t(i)$$
  • 在观测O下由状态i转移状态j的期望值 $$\sum_{t=1}^{T-1}\epsilon_t(i,j)$$

学习算法

监督学习方法

假设已有训练数据集包含S个长度相同的观测序列和对应的状态序列{(O1,I1),(O2,I2),...,(Os,Is)}，那么可以使用极大似然法来估计隐马尔科夫模型的参数

• 转移概率aij的估计,Aij为时刻t处于状态i时刻t+1处于状态j的频数 $$\hat a_{ij}={A_{ij}\over \sum_{j=1}^N A_{ij}}, i=1,2,...N;j=1,2,...N$$
• 观测概率bj(k)的估计,Bjk为状态为j观测为k的频数 $$\hat b_j(k)={B_{jk}\over \sum_{k=1}^MB_{jk}}, j=1...N;k=1...M$$
• 初始状态概率的估计
  初始状态概率为S个样本数据中初始状态为qi的概率

Baum-Welch算法

假定数据只包含S个长度为T的观测序列，而没有对应的状态序列，目标是学习参数。将观测序列数据看着O，状态序列数据看着不可观测的隐数据I，那么

$$P(O|\lambda)=\sum_{I}P(O|I,\lambda)P(I|\lambda)$$ ，参数可由EM算法求解

EM算法说明

利用ＥＭ算法
1. 确定完全数据的对数似然函数
所有观测数据写成O，隐数据写成I，完全数据是$(O,I)=(o_1,o_2,...o_T,i_1,i_2,...i_T)$,其对数似然函数为$\log P(O,I|\lambda)$
2. EM算法的E步，求Q函数 $$Q(\lambda,\hat\lambda)=\sum_I\log P(O,I|\lambda)P(O,I|\hat\lambda)$$ $\hat \lambda$为当前估计，$\lambda$为极大化的隐马尔科夫模型参数 $$P(O,I|\lambda)=\pi_{i_1}b_{i_1}(o_i)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}i_T}b_{i_T}(o_T)$$ 由此， $$Q(\lambda,\hat \lambda)=\sum_I\log\pi_{i_1}P(O,I|\hat\lambda)+\sum_I(\sum_{t=1}^{T-1}\log a_{i_ti_{t+1}})P(O,I|\hat\lambda)+\sum_I(\sum_{t=1}^T\log b_{i_t}(o_t))P(O,I|\hat\lambda)$$ 求和是对所有训练数据的训练总长度T进行的
3. EM算法的M步，极大化Q函数球模型参数
第一项可以写成 $$\sum_I\log\pi_{i_1}P(O,I|\hat\lambda)=\sum_{i=1}^N\log\pi_iP(O,i_1=i|\hat\lambda)$$
由条件$\sum\pi_i=1$和拉格朗日乘子法有 $$\sum_{i=1}^N\log\pi_iP(O,I|\hat\lambda)+r(\sum_{i=1}^N\pi_i-1)$$
对其求偏导$\pi_i$，并令其等于０有 $$P(O,I|\hat\lambda)+r\pi_i=0;r=-P(O|\hat\lambda)$$
有 $$\pi_i={P(O,i_1=i|\hat\lambda)\over P(O|\hat\lambda)}$$
4. 针对第二项有 $$=\sum_{i=1}^N\sum_{j=1}^N\sum_{t=1}^{T-1}\log a_{ij}P(O,i_t=i,i_{t+1}=j|\hat\lambda)$$ 根据$\sum_{j=1}^Na_{ij}=1$使用拉格朗日有 $$a_{ij}={\sum_{t=1}^{T-1}P(O,i_t=i,i_{t+1}=j|\hat\lambda)\over \sum_{t=1}^{T-1}P(O,i_t=i|\hat\lambda)}$$
5. 针对第三项有 $$=\sum_{j=1}^N\sum_{t=1}^T\log b_j(o_t)P(O,i_t=j|\hat\lambda)$$ 利用约束条件$\sum_{k=1}^Mb_j(k)=1$，有 $$b_j(k)={\sum_{t=1}^TP(O,i_t=j|\hat\lambda)I(o_t=v_k)\over \sum_{t=1}^TP(O,i_t=j|\hat\lambda)}$$

Baum-Welch算法

输入：观测数据$O=(o_1,o_2,...,o_T)$
输出：隐马尔科夫模型参数
1. 初始化
对n=0，选取$a_{ij}^{(0)},h_j(k)^{(0)},\pi_i^{(0)}$，得到模型$\lambda^{(0)}=(A^{(0)},B^{(0)},\pi^{(0)})$
2. 递推，对$n=1,2,...$ $$a_{ij}^{(n+1)}={\sum_{t=1}^{T-1}\xi_t(i,j)\over \sum_{t=1}^{T-1}\mathcal r_t(i)}$$ $$b_j(k)^{(n+1)}={\sum_{t=1,o_t=v_k}^T\mathcal r_t(j)\over \sum_{t=1}^T\mathcal r_t(j)}$$ $$\pi_i^{(n+1)}=\mathcal r_1(i)$$ 右端各值按观测O和模型$\lambda^{(n)}=(A^{(n)},B^{(n)},\pi^{(n)})$计算
3. 终止，得到模型

预测算法

近似算法

思想：在每个时刻ｔ选择在该时刻最有可能出现的状态$i_t^*$

$$\mathcal r_t(i)={\alpha_t(t)\beta_t(i)\over \sum_{j=1}^N\alpha_t(j)\beta_t(j)}$$ 每一个时刻最有可能的状态 $$i_t^*=arg\max{1\le i\le N}[\mathcal r(i)],t=1,2...T$$

缺点是其不保证是最有可能的状态序列。上述得到的状态序列是有可能存在转移概率为０的相邻状态。

维特比算法

维特比算法是用动态规划解隐马尔科夫模型预测问题，即求解概率最大路径（最优路径）。

最优路径特性：如果最优路径再时刻ｔ通过结点$i_t^*$，则这一路经从$i_t^*$到$i_T^*$的部分路径，对于两者之间的所有可能的路径来说，必须是最优的

维特比算法
:　输入：模型$\lambda=(A,B,\pi)$，观测$O=(o_1,o_2,...o_T)$
输出：最优路径$I^*=(i_1^*,i_2^*...i_T^*)$
1. 初始化

$$\delta_1(i)=\pi_ib_i(o_1),i=1,2,..N$$ $$\psi_1(i)=0,i=1,2...N$$
2. 递推，对$t=2,3,...T$ $$\delta_t(i)=\max_{1\le j\le N}[\delta_{t-1}(j)a_{ji}]b_i(o_t),i=1,2,...,N$$ $$\psi_t(i)=arg\max_{1\le j\le N}[\delta_{t-1}(j)a_{ji}],i=1,2,...N$$ 3. 终止$$P^=\max_{1\le i\le N}\delta_T(i)i_T^=arg\max_{1\le i\le N}[\delta_T(i)] $$4. 最优路径回溯，对$t=T-1,T-2,...1$$ $i_t^=\psi_{t+1}(i_{t+1}^)$$

第11章 条件随机场

条件随机场是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型，其特点是假定输出随机变量构成马尔科夫随机场。

概率无向图模型

图（graph）是由结点（node）以及连接结点的边（edge）组成的集合。图记住G(V,E)。
概率图模型是由图表示的概率分布。设有概率分布P(Y)，$Y\in\mathcal Y$是一组随机变量。由该图表示概率分布，结点$v\in V$表示一个随机变量$Y_v,Y=(Y_v)_{v\in V}$，边$e\in E$表示随机变量之间的概率依赖关系。

成对马尔科夫性

设u和v是Ｇ中任意两个没有边相连的结点，其他所有结点为O，该性质是指在给定随机变量组$Y_O$的条件下随机变量$Y_u$和$Y_v$是条件独立的。 $$P(Y_u,Y_v|Y_O)=P(Y_u|Y_O)P(Y_v|Y_O)$$

局部马尔科夫性

设v为任意一点，W是与v有边相连的所有结点，O是v,W除外的所有点，该特性是指在给定$Y_W$的情况下随机变量$Y_v$和$Y_O$是条件独立的。 $$P(Y_v,Y_O|Y_W)=P(Y_v|Y_W)P(Y_O|Y_W)$$ 在$P(Y_O|Y_W)>0$时有$P(Y_v|Y_W)=P(Y_v|Y_W,Y_O)$

全局马尔科夫性

设结点集合A,B是在无向图中被结点集合C分开的任意结点集合，该特性是指给定随机变量组$Y_C$条件下随机变量组$Y_A$和$Y_B$是条件独立的。 $$P(Y_A,Y_B|Y_C)=P(Y_A|Y_C)P(Y_B|Y_C)$$

概率无向图：设有联合概率分布P(Y)，由无向图$G=(V,E)$表示，在图G中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布$P(Y)$满足成对、局部或全局马尔科夫性，就称此联合概率分布为概率无向图模型（probability undirected graphical model），或马尔科夫随机场（Markov random field）。

因子分解

团与最大团

无向图G中任意两个结点均有边连接的结点子集称为团（clique）,若C是其一个团，并且不能在加进任何一个G的结点使其称为一个更大的团，则称此C为最大团(maximal clique)。

将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作，称为概率无向图模型的因子分解(factorization)。

$$P(Y)={1\over Z}\prod_C\psi_C(Y_C)$$ 其中Z是规范化因子，$Z=\sum_Y\prod_C\psi_C(Y_C)$
函数$\psi_C(Y_C)$称为势函数(potential function)，这里要求该函数是严格正的，通常定义为指数函数 $$\psi_C(Y_C)=\exp\{-E(Y_C)\}$$

条件随机场的定义与形式

条件随机场

设

第12章 统计学习方法总结