《统计学习方法》摘要

 

统计学习

特点
  1. 以计算机和网络为平台
  2. 以数据为研究对象
  3. 目的是分析和预测数据
  4. 以统计学习方法构建模型
  5. 在执行过程中不断改善模型性能
分类
  1. 监督学习
  2. 非监督学习
  3. 半监督学习
  4. 强化学习

监督学习

2个假设
  1. 数据是独立同分布产生的;输入与输出的随机变量遵循某个联合概率分布
  2. 模型属于某个假设空间;假设空间就是输入空间到输出空间的映射的集合
3个要素
  1. 模型:输入空间到输出空间的映射;由条件概率分布或决策函数表示
  2. 策略:模型选择的准则;两个基本策略:经验风险最小化、结构风险最小化
  3. 算法:求解最优化问题的算法
6个步骤
  1. 给定一个有限的训练数据集合
  2. 确定假设空间
  3. 确定学习策略
  4. 确定学习算法
  5. 通过学习得到最优模型
  6. 利用最优模型对新数据进行分析预测
3个研究方向
  1. 开发新的学习方法
  2. 探究学习方法的有效性和效率
  3. 应用到实际问题
基本概念

输入空间:输入的所有可能取值。输入看作是定义在输入空间的随机变量的取值
输出空间:输出的所有可能取值。输出看作是定义在输出空间的随机变量的取值
实例:每个具体的输入,由特征向量表示 样本:每个具体的输入和输出对
特征空间:所有特征向量存在的空间。特征空间的一维对应一个特征。特征空间可以是输入空间,也可以是输入空间映射出阿里的。模型定义在特征空间 回归问题:输入与输出均为连续变量的预测问题;常用隐马尔可夫模型、条件随机场
分类问题:输出为有限个离散变量的预测问题
标注问题:输入与输出均为变量序列的预测问题 损失函数:度量模型一次预测的好坏;0-1损失函数、平方损失函数、绝对损失函数、对数损失函数
风险函数/期望损失/期望风险:度量平均意义下模型预测的好坏;等于损失函数在联合分布下的期望
经验风险:模型关于给定训练集的平均损失
结构风险:经验风险加上表示模型复杂度的正则化项
训练误差:学习到的模型关于给定训练集的平均损失
测试误差:学习到的模型关于给定测试集的平均损失
学习方法的泛化能力:由该方法学习到的模型的预测能力
模型的泛化误差:等于期望风险;反应学习方法的泛化能力
泛化误差上界:泛化误差的概率上界;通过比较两种学习方法的泛化误差上界来比较它们的优劣
生成模型:学习联合概率分布,求出条件概率分布;朴素贝叶斯、隐马尔可夫模型
判别模型:直接学习决策函数或条件概率分布;k邻近、感知机、决策树、逻辑回归、最大熵、支持向量机、提升树、条件随机场。
欧式空间:
联合概率分布:
条件概率分布:
先验概率:
后验概率:
极大似然估计:
贝叶斯估计:

经验风险最小化

最初的问题是期望风险最小化;
根据大数定律,当样本容量N趋于无穷时,经验风险趋于期望风险,所以问题转化为经验风险最小化
在假设空间、损失函数、训练集确定的条件下,经验风险函数式就可以确定
当模型是条件概率分布、损失函数是对数损失函数时,经验风险最小化等价于极大似然估计
当样本容量过小时,会发生“过拟合”:学习时选择的模型所含参数过多,以致于这一模型在训练集上表现很好,但在测试集上表现不好

结构风险最小化

为了防止过拟合,在经验风险上加上表示模型复杂度的正则化项,问题转化为:结构风险最小化
在经验风险函数式、模型复杂度表达式确定的条件下,结构风险函数式就可以确定, 结构风险小需要经验风险与模型复杂度同时小
当模型是条件概率分布、损失函数是对数损失函数、模型复杂度由模型的先验概率表示时,结构风险最小化等价于最大后验概率估计
当模型的复杂度增大时,训练误差会逐渐减小到0;测试误差会先减小后增大
选择复杂度合适的模型的2种方法:正则化、交叉验证
结构风险最小化等价于正则化

交叉验证
  1. 简单交叉验证:一部分数据集用作训练、另一部分用作测试;在不同条件下训练出多个模型,挑选在测试集上表现最好的
  2. S折交叉验证:数据集分成S份,其中S-1份用作训练,1份用作测试,每个模型重复S次,挑选平均表现最好的

感知机

输入空间

n维欧氏空间

输出空间

+1、-1

模型

决策函数f(x) = sign(w * x + b)

策略

损失函数:误分类点到分离超平面的总距离
经验风险最小化

算法

随机梯度下降法:

  1. 选取参数的初值
  2. 选取样本点,如果样本点是误分类点,则更新参数(+ 步长 * 梯度)
  3. 重复这个过程,直到没有误分类点

收敛性:
基础假设:数据集是线性可分的,则有定理:存在超平面可以把数据集正确分开;迭代次数存在上限

k邻近

输入空间

n维欧氏空间

输出空间

类别的集合

模型

对每个样本点,距离该点比其它点更近的所有点组成一个区域,叫做单元
每个样本点拥有一个单元
所有样本点的单元构成对输入空间的一个划分
将样本点的类作为其单元中所有点的类
3个要素:

  1. 距离度量:反映两个样本点的相似程度;欧式距离、曼哈顿距离
  2. k值:从训练集中选取距离测试点最近的k个点;k值太小会发生过拟合;k值太大会欠拟合
  3. 分类决策规则:多数表决
kd树

线性扫描,即依次计算每对点的距离,非常耗时,所以有kd树

朴素贝叶斯

输入空间

n维欧氏空间

输出空间

类别的集合

模型

假设训练集和测试集是独立同分布产生的,服从联合概率分布P(X=x, Y= y)

策略

联合概率分布P(X=x, Y=y) 由 先验概率P(Y=y)、条件概率P(X=x|Y=y) 得到
先验概率P(Y=y)、条件概率P(X=x|Y=y) 由 极大似然估计 得到
用极大似然估计可能会出现概率值为0的问题,解决方法是采用贝叶斯估计

算法
  1. 对于给定的训练集,计算先验概率、条件概率(用到条件独立假设)
  2. 对于给定的测试点,用贝叶斯定理计算后验概率
  3. 选取后验概率最大的类作为测试点的类

决策树

输入空间

n维欧氏空间

输出空间

类别的集合

模型

决策树模型是一种描述对实例进行分类的树性结构
内节点表示特征、叶节点表示类

算法

NP完全问题、采用启发式方法。
熵:
条件熵:
信息增益:特征A对训练集D;经验熵H(D) 与 经验条件熵H(D|A) 之差
信息增益比:
基尼指数:特征A对训练集D;

ID3算法:

  1. 计算各特征对训练集D的信息增益,选取最大的特征Ag。
  2. 如果Ag的信息增益比阈值小,则把D中实例数最多的类作为该节点的类。
  3. 否则,用Ag的所有可能取值划分D,把子集中实例数最多的类作为子节点的类。
  4. 对所有子节点重复这个过程,直到特征用完、或者子集无法划分。

C4.5算法:
过程同ID3算法,把信息增益换成信息增益比

剪枝

剪枝是从整体考虑
损失函数:正则化的极大似然函数

  1. 计算每个节点的经验熵。
  2. 递归地从叶节点向上回缩:如果一组叶节点回缩后可以使整棵树的损失函数减小,就回缩
  3. 重复这个过程,直到所有叶节点都不用回缩
CART回归树生成
  1. 使用平方误差最小化准则,选择最优切分变量与切分点。
  2. 用选定的最优切分变量与切分点划分区域、并决定输出值。
  3. 重复这个过程。
CART分类树生成

基尼系数

CART剪枝

逻辑回归

输入空间

n维欧氏空间

输出空间

0、1

模型

逻辑斯蒂分布:
事件的几率:事件发生与不发生概率的比值
逻辑回归模型是如下的条件概率分布:
输出Y=1的对数几率是输入的线性函数
线性函数越接近正无穷,概率值就越接近1;线性函数越接近负无穷,概率值就越接近0

策略

极大似然估计:列出对数似然函数,求极大值,得到参数的估计值

算法

梯度下降法、拟牛顿法

最大熵

模型

最大熵原理:在满足约束条件的模型集合中选取熵最大的模型。
约束条件:特征函数关于联合分布的经验分布的期望值 等于 特征函数关于模型与边缘分布的经验分布的期望值。
最大熵模型:在满足所有约束条件的模型集合中,条件熵最大的模型 称为最大熵模型。

策略

等价于 约束最优化问题,用拉格朗日求解

算法

改进的迭代尺度法、拟牛顿法

支持向量机

提升树

高斯混合模型

隐马尔可夫模型

条件随机场