这本书主要介绍第一类学习类型，监督学习。
未知的P(X,Y)联合概率模型产生的独立同分布的数据，统计学习基于三要素学习这些数据，并期许学习到的模型能对未知数据有较好的预测能力。
能与数据相吻合的概率模型或数学模型。
用于评判模型优劣的标准。一般由一个损失函数表示。分为两种：经验风险及结构风险。
经验风险：关于训练数据的平均损失。由于（由于P(X,Y)未知，所以对训练数据平等看待）（可能出现过拟合）（采用经验风险的例子：极大似然估计）结构风险（正则化）：在经验风险基础上在加上模型复杂度的惩罚项。（采用结构风险的例子：最大厚颜概率估计）通过最优化数值计算，选取（计算）出最优模型。
一味提高对训练数据的预测能力，致使模型复杂度过高。导致对已知数据的预测能力好，对未知数据的预测能力差。
有两种方法选择合适的模型：正则化及交叉验证。
正则化（结构风险）：在经验风险的损失函数中加上模型参数向量的范数，作为新的损失函数。交叉验证：数据充足时，把训练数据分成训练集，验证集和测试集，分别用于训练模型，模型选择和评估模型。数据不充足时，切分数据，重复组合数据，分别用于训练，选择和评估。即模型对未知数据的预测能力 泛化误差上界：样本多则小；假设空间大则大。
学习P(X,Y)，从而得出P(Y|X)。 收敛快（朴素贝叶斯，隐马链）
学习y=f(x)或P(Y|X)。 准（kNN，。。。）
分别为：分类，标注和回归。 标注：一个样本序列对应多个标签。（用于信息抽取：抽取名词短语。隐马，条件随机场） 回归：函数拟合（最小二乘）
适用于分类问题，是kNN（k近邻）与SVM（支持向量机）的基础。
线性分类，判别模型
f(x) = sign( w*x+b )w*x+b=0 对应一个超平面，这个超平面将特征空间分为两部分。w对应法向量，b对应截距。
存在 w*x+b=0能完美划分数据集
误分类点驱动，使用随机梯度下降。
随机选取一个误分类点，利用其梯度值更新模型。适用于分类与回归。无显示的学习过程。 主要步骤有：k值的选择，距离度量及分类决策规则。
根据距离将特征空间划分，新数据选取前k个距离最近的划分，并决策。
k值小：近似误差小，估计误差大，模型复杂，会过拟合。 k值大：近似误差大，估计误差小，模型简单。 （近似误差：只有较近的实例才对结果起作用。估计误差：对近邻的实例非常敏感。）
多数表决 等价于 经验风险最小。
训练数据多，如何进行快速k近邻搜索。考虑使用特殊的存储结构存储训练数据。
kd树是一个二叉树，对特征空间进行划分。 循环取各个特征（深度可超过维度） 取中位数为切分点
先从根节点触发，找到包含目的节点的叶节点，之后递归向上回退，寻找更近的节点。（查看矩形区域与圆是否相交） 回退到根节点结束。
更适用于实例数远大于空间维数的时候。每个节点对应一个超矩形区域。
由训练数据的导出 P(X,Y)，对输入x，取使后验概率最大的y作为输出。（生成模型） 朴素贝叶斯与贝叶斯估计是不同的概念。
进而得出 P(X,Y)。 但是条件概率参数过多（每个取值对应一个概率）： 因此提出条件独立性假设，简化学习：
取使后验概率最大的y值作为输出 而后验概率可通过下式计算得出： 预测输出为： 进一步化简：
等价于期望风险（概率由计算得出）最小化（0-1损失函数）
用于后验概率计算。
有计算出的个别概率为零的情况。（致使后验概率等于零） 采用以下方法（加个因子）：
选取对训练数据具有有效分类能力的特征。 以信息增益or信息增益比作为选择标准。
熵： 熵只与变量的分布有关。 条件熵： 用于计算熵的概率可由估计得到（极大似然估计）。 信息增益（互信息）： 特征A对训练数据集D的信息增益 g(D;A) 为：
生成局部最优树，可由剪枝得到全局最优树。
算法：选取信息增益最大的特征作为节点特征，由该特征的不同取值建立子节点，再对子节点递归调用以上方法，构建决策树。终止条件：直到所有特征的信息增益均很小或没有特征可以选择为止。
问题：若某个特征选取的值过多，如ID号，其信息增益大。因此需要对此引入惩罚，即使用信息增益比：
利用信息增益比选取特征。
|T|为叶节点个数，Nt为叶节点样本个数，H(T)为叶节点的熵。 C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数a控制两者之间的影响。
等价于正则化的极大似然估计
通过比较剪枝前后的损失函数，判断是否剪枝。
二叉树（上述的ID3，C4.5为多叉树） 分为分类树与回归树
递归构建二叉树，回归问题通过平均误差最小化选取最优输出；分类问题通过基尼系数选取特征和切分点。
回归树（最小二乘回归树） 含义：将特征空间划分成单元，每个单元对应一个固定输出值Cm。 采用启发式方法对空间进行划分：
分类树 基尼系数： 表示训练集D的不确定性。
基尼系数和熵都可以近似代表分类误差率。取基尼系数最小的切分点作为最优特征和切割点。通过某项判定规则，不断地对树的内部节点进行剪枝，生成一个决策树序列，然后通过交叉验证对决策树进行测试，从而选取最优决策树。
对于内部节点 t： 剪枝前的损失函数： 剪枝后的损失函数： 使内部节点t剪枝前和剪枝后损失函数相等，得到参数a的值。 a小，则剪枝后增加的不确定度C(t)-C(Tt)=a(|T|-1)越小。所以优先选取a小的内部节点进行剪枝。 所以剪枝的原则是：不增加损失函数的前提下，选取能最有效降低决策树复杂度（a越小）的内部节点进行剪枝。 步骤： 先自下而上计算数值： 然后自上而下选取内部节点进行剪枝。
logistic regression/max entropy 是对数线性模型
曲线图： 分布函数与阶跃函数（感知器）相比充分考虑所以样本的期望损失。
由分布函数导出：
用极大似然估计，估计模型参数w。 使似然函数最大，利用梯度下降，拟牛顿求参数。
熵最大的概率模型是最好的模型（最稳定）。即基于已知信息平等对待未知信息。 均匀分布熵最大。
通过估计得出 定义特征函数（符合特征能提供信息）：
期许模型 P(y|x) 能学习经验信息 P~(X,Y) 的信息，即特征函数的期望值相等，并使模型的条件熵最大的模型称为最大熵模型：
通过引进拉格朗日乘子，对应于多个特征函数。 利用对偶问题求解参数w。 进而可得模型：
适用于二类分类问题。求取间隔最大的线性分类器+核方法。 核方法：将输入空间映射到特征空间（非线性）。
参考优化问题，SVM1，SVM2
感知器目标是使误分类最少，存在多个解；SVM目标是间隔最大化，存在唯一解。
|w*x+b|表示样本点距离超平面的距离，由距离来表示分类的确信度。取确信度为y(w*x+b)，此成为函数间隔。 但 w 和 b 的缩放不会改变超平面，但是会改变函数间隔的大小。使模型评判不准确。所以对 w 和 b 进行归一化的间隔即为几何间隔。
优化目标：使间隔 r/|w| 取最大值； 约束：是所有样本点距离都大于 r 。
一般取 r=1，则： 等价
距离超平面最近的样本点称为：支持向量 支持向量间的间隔带称为：间隔边界 超平面由（少数）支持向量确定，因此支持向量很重要。
原始问题： 拉格朗日函数： 经过数值运算，得：
某些样本点不能满足》1的约束条件。因此引入松弛变量，并对松弛变量引入惩罚。
支持向量由对偶问题给出。。。 对偶问题中 a>0 的样本为支持向量 软间隔最大化的另一种解释是：合页损失函数最小化。
只有超曲面（非线性）才能分类的数据。 核方法：对输入数据作变换，使得可以使用超平面（线性）进行分类。 核函数： 将核函数应用到对偶问题中（将内积换成核函数）即为核方法。
对于SVM，当样本多时，学习慢，以此引入SMO方法，加速学习。是一种启发式算法。（启发式：有线选择距离终点最近的节点，而Dijkstra优选选择离源节点最近的节点。） SMO：在对偶问题中，取其中两个变量先优化，再持续优化两个两个的变量。（利用KKT条件选变量）一个变量选违反KKT条件最严重的（启发式？），另一个变量来由约束条件自动确定。
强可学习：一个类（概念）存在一个多项式学习，是预测正确率高。弱可学习：最好的预测，其正确率仅比随机猜测略好。 提升方法：改变训练数据的概率分布（权值分布），训练出一系列分类器，将这些分类器组合构成一个强学习器。
对于带权值数据的学习算法：1. 通过修改弱分类器的损失函数为w*cost(x)；2. 对训练样本进行bootstrap抽样，每次抽样的概率等于样本的权值。 AdaBoost对线性分类器起不到效果。
参数计算： 等价于
（算法的另一种解释： 模型：加法模型 损失函数： 学习方法：前向分布算法（每部只学习一个b(x,r)） ）
采用加法模型（基函数的线性组合）与前向分步算法，当以基函数为决策树时，称为提升树。
根据问题挑选损失函数。对于回归问题，相当于拟合残差以学习一个新的回归树。
对于一般损失函数，可以用损失函数的负梯度近似为残差值，用以拟合回归树。
EM：期望最大（expectation max） 当观测变量包含了所有变量（可利用极大似然估计 or 贝叶斯估计）；当观测变量未包含所有变量（有隐变量，采用EM算法）。
由极大化 导出：
应用于非监督学习时，只有输入没有输出，EM算法可用于学习生成模型P(X,Y)。算法迭代递增，但不一定收敛于极大值；可取多组初始值，多次训练，取最好的模型。
需要预知模型的结构？
HMM 用于标注问题；是生成模型。用于语音识别，NLP，生物信息，模式识别。
是关于时序的概率模型。 用隐藏（未知）的马链产生 随机状态序列，通过观测随机状态序列，得到随机观测序列。通过随机观测序列学习模型。
模型由以下三部分组成： 初始状态概率向量：
状态转移概率矩阵： 观测概率矩阵：
给定观测序列，预测标记序列，如标记词性。
计算量大 采用动态规划算法：
前向概率：到时刻 t ，部分观测序列为 o1, o2, … , ot，且状态为 qt的概率。
算法
路径结构
后向概率：在时刻 t 状态为 qi 条件下，从 t+1 到 T 的部分观测序列为 ot+1 , ot+2 , … , oT 的概率。 算法 路径结构
进而可求得在时刻 t 处于状态 qi 的概率。
有观测数据和状态序列。 可以用极大似然估计 得出模型。 转移概率
观测概率 与转移概率类似的方法。
初始概率
人工标注的代价高
即为隐变量的概率模型： 状态序列为隐变量 I。利用EM算法实现参数学习。
取每个时刻 t 最有可能出现的状态作为预测结果。 计算简单，但是不能保证预测的状态序列整体是最有可能的状态序列。
用动态规划求概率最大路径。 定义
算法递推
由无向图表示联合概率分布。
因子分解：把P(Y)写成若干个子联合概率的乘积。 团：两两有边连接的节点的集合，集合最大的团称为最大团。 P(Y) 可以表示为最大团变量的函数的乘积。（因子分解）
序列化的最大熵模型 条件随机场：在给定随机变量X下，随机变量Y的马尔可夫随机场。主要讨论线性链（序列）条件随机场。 用于标注：观测得X ， 预测出标注Y。 最大团： 相邻的两个节点组成最大团。 线性链条件随机场： 线性链满足马尔可夫性：
t 为转移特征，s 为状态特征。通常 t，s 取值为 1或0。
转化为向量表示： 特征向量： 特征权值： 简化形式：
指定标记序列，计算其概率值。 M类似转移概率矩阵。即由特征函数及其权值表征的标注转移概率矩阵。
用于选取最符合特征的标注序列
前向递推公式： 后向递推公式：
通过极大化训练数据的对数似然概率来求解 参数 w。 对数似然函数，即各个样本点的条件概率p(y|x)的乘积的对数。 使用梯度下降方法。 分别对每个变量求偏导并使其等于0。得出为两个期望相等。。 带惩罚项 or
也就是说样本点中符合第 j 个特征的样本数目 应该等于 在目前模型下第 j 个特征的期望数目。（类似最大熵模型）
给定P(Y|X)和观测序列，求使条件概率最大的序列Y，与隐马类似。
HMM只考虑状态之间的邻接关系。CRF还考虑了观测序列间的关系。？ 因此CRF更好
区别：损失函数不同
感知器：只考虑误分类点logistic：考虑所有点，并大大减小离超平面较远的点的权重SVM：只考虑和分类最相关的少数点