统计学习方法 笔记
- 本书提到的基本都是有监督学习算法, 特别是分类与标注问题的方法
- statistical learning, 也称 statistical machine learning. 基本上是机器学习的同义词.
- 输入空间与特征空间: 有时相同, 有时需做一次映射. 模型实际上都是定义在特征空间上的.
- 本书记法
- 输入和输出：随机变量 X,Y；变量取值 x,y；变量可以是向量或标量. 向量默认为列向量.
- 上标表示第 i 个特征, 下标表示第 i 个输入变量 (跟 coursera 课程上刚好相反 😅 )
- 标注问题：输入变量和输出变量均为变量序列
- 监督学习的基本假设是存在联合分布 P(X,Y). 训练数据和测试数据被看做依 P(X,Y) 独立同分布产生的.
- 概率模型或非概率模型，分别表示为：条件概率 P(Y|X) 或 决策函数 Y=f(X)
- 监督学习的两个过程：学习，预测
- 假设空间可定义为：
- 决策函数的集合，由参数向量决定的函数族 （非概率模型）
- 条件概率的集合，由参数向量决定的条件概率分布族 （概率模型）
- 损失函数/代价函数: L(Y, f(X)), 度量模型一次预测的好坏.
- 常用的损失函数: 0-1损失, 平方损失, 绝对损失, 对数损失
- 风险函数/期望损失/期望风险: 损失函数关于联合分布 P(X,Y) 的期望. 度量平均意义下模型预测的好坏. 即 out-of-sample error.
$R_{exp}(f) = E_P[L(Y, f(X))] = \int_{\mathcal{X}\times\mathcal{Y}} L(y,f(x))P(x,y)dxdy$ - // 有时 E_out 定义为在输入空间上的期望 (不管输出空间), 是假定存在一个 deterministic target f(x) 并忽略了噪音.
- 经验风险: 模型关于训练样本集的平均损失. 即 in-sample error.
- 两种基本策略
- 经验风险最小化
- 样本容量足够大时效果好, 样本容量小时会过拟合.
- 例子: MLE. 当模型是条件概率分布, 损失函数是对数损失函数时, 经验风险最小化等价于 MLE.
- 结构风险最小化: 等价于正则化.
- 增加一个 penalty term:
$\lambda$ * 模型复杂度J(f) - 例子: 贝叶斯估计中的最大后验概率估计 (MAP). 当模型是条件概率分布, 损失函数是对数损失函数, 模型复杂度由模型的先验概率表示时, 结构风险最小化等价于 MAP.
- 增加一个 penalty term:
- 经验风险最小化
- 模型和策略确定后, 统计学习问题就变成了最优化问题 (优化目标是经验风险或结构风险)
- 通常解析解不存在，需要用数值计算的方法求解. 挑战在于: 保证找到全局最优解; 使求解过程高效.
- 两种常用的模型选择方法: 正则化; 交叉验证
- 1.5.2 交叉验证
- LFD 里把 cross validation 作为 validation 的一种特殊情形, 或者至少是并列的. 本书中则把普通 validation 看做交叉验证的一种情况, 名为”简单交叉验证”. 另外, 这部分文字里”测试”和”验证”两个词用得似乎不够严谨.
- 1.7 生成模型与判别模型
- 生成模型 generative model: 学习联合分布 P(X,Y), 然后求出条件概率分布.
- 特点: 收敛速度更快; 存在隐变量时仍可学习.
- 判别模型 discriminative model: 直接学习 f(X) 或 P(X|Y).
- 特点: 直接面对预测, 准确率更高; 可以对数据进行抽象, 定义并使用特征, 简化学习问题 (?).
- 生成模型 generative model: 学习联合分布 P(X,Y), 然后求出条件概率分布.
- 分类问题: 概率模型学得 P(Y|X), 根据给定 X 输出条件概率最大的 Y; 非概率模型 Y=f(X) 直接输出标记值.
- 回归问题: 只有非概率模型 Y=f(X). 学习过程等价于函数拟合.
1.1 说明伯努利模型的极大似然估计及贝叶斯估计中的统计学习方法三要素
- 两种估计的模型应该都是条件概率
$p(k|\theta,n) = \theta^k(1-\theta)^{n-k}$ - 极大似然估计
- 似然函数
$L(\theta|n,k) = p(k|\theta,n) = \theta^k (1-\theta)^{n-k}$ -
$\hat{\theta} = argmax(L) = argmin(-\log L) = argmin(J)$ ,- 极大似然估计等价于经验风险最小化. ← 策略
- 似然函数
- 贝叶斯估计
- 后验概率
$p(\theta|n,k) \propto p(k|\theta,n)p(\theta)$ . 取对数$\log p(\theta|n,k) = \log p(n,k|\theta) + \log p(\theta) + C$ - 假定
$\theta$ 的先验概率服从高斯分布,$p(\theta) \propto \exp(-\frac{(\theta-\mu)^2}{2\sigma^2})$ -
$\hat{\theta} = argmax p(\theta|n,k) = argmin[-\log p(\theta|n,k)] = argmin(J + \frac{1}{2\sigma^2}(\theta-\mu)^2)$ - 这里先验概率取对数相当于正则化项. 因此后验概率最大化等价于结构风险最小化. ← 策略
- 后验概率
- 模型:
$f(x) = sign(w\cdot x +b)$ -
$w\cdot x + b = 0$ 是特征空间$R^n$中的一个超平面 S- 超平面 (hyperplane) 就是比原空间维数小1的子空间. 比如常见的二维特征空间的超平面是直线, 三维空间的超平面就是平面.
-
- 策略: 损失函数 ~ 误分类点到超平面 S 的总距离.
-
点
$x_0$ 到超平面的距离:$\frac{1}{| w|} |w\cdot x_0 + b|$ - 损失函数
$L(w,b) = -\sum_{x_i\in M} y_i(w\cdot x_i + b)$ - 忽略
$1/|w|$ 项 - M 为误分类点的集合
-
$y_i$ 仅起到调整符号的作用. 对误分类点,$y_i$ 与$w\cdot x_i + b$ 反号, 前面的符号保证结果为正.
- 忽略
-
点
- 算法
- “原始形式”: 随机梯度下降 (每次随机选一个误分类点)
- 对线性可分数据是收敛的, 能找到正确的分离超平面.
- 但算法的解不唯一, 依赖于初值和误分类点选择顺序.
- 为得到唯一的解, 需要对分离超平面增加约束条件 → 线性支持向量机
- 对线性不可分数据, 算法不收敛, 迭代结果会发生震荡
- “对偶形式”: 将 w 和 b 表示为
$x_i$ 和$y_i$ 的线性组合. 计算中可用 Gram 矩阵来存储实例间的内积.
- 动手实现一个简单的感知机例子. → Learning from data Hw1
k近邻法特点:
- 没有显式的学习过程
- 实际上利用训练数据对特征空间进行划分
三个基本要素: 距离度量, k值选择, 分类决策规则
- 距离度量
- 常用的是欧氏距离
- 更一般的有 Lp 距离 (或 Minkowski 距离): 对n维向量
$x_i, x_j$ ,$L_p(x_i,x_j) = (\sum_l|x_i^{(l)} - x_j^{(l)}|^p)^{1/p}$ - p = 1 时为曼哈顿距离. p = 2 即为欧氏距离.
- k值选择
- k越大, E_in 越大, E_out - E_in 越小. k值用交叉验证确定.
- 分类决策规则
- 一般用多数表决规则, 等价于经验风险最小化
- kd树是一种在k维空间中实现高效搜索的数据结构 (Coursera 算法课的 assignment5 )
- 注意 “kd树” 里的k表示空间维数, 跟 “k近邻” 里的k含义不同
- 本书中对 kd 树的讲解与 算法课的区别:
- 本书介绍的是平衡kd树, 也就是每次切分空间时选该坐标的中位数. 而算法课里没考虑平衡. 不过作者也提到, 平衡kd树的搜索效率未必最高.
- 最近邻搜索的实现: 算法课里使用一次向下递归; 而本书是先用一次向下递归找到包含目标点的区域对应的叶节点, 然后递归地向上回退寻找更近点.
- kd 树适用于数据量远大于空间维数的情况
这个算法 DL101 有学过, 也写过笔记 朴素贝叶斯法用于情感分类 , 情感分类有个很好的资料是 SLP ch6.
- 朴素贝叶斯是生成模型, 试图学习 P(X,Y), 预测时依据后验概率P(Y|X)最大化. 而 P(X,Y) = P(X|Y) x P(Y). 学习的具体目标是条件概率 P(X|Y) 和先验概率 P(Y)
- P(X|Y) 参数太多, 故引入条件独立性假设. (注意, 条件独立和独立是两回事)
- 朴素贝叶斯的后验概率最大化等价于期望风险最小化 (试着推导一下)
- 估计概率的两种方法
- 极大似然估计: 仅依据样本里的频率信息来估计概率
- 贝叶斯估计: 引入拉普拉斯平滑. 至于为什么引入平滑就是贝叶斯估计, 还不大理解.
- 本书主要讨论分类决策树.
- 决策树可以认为是 if-then 规则的集合, 也可以认为是定义在特征空间和类空间上的条件概率分布.
- 三个步骤: 特征选择, 决策树的生成, 决策树的修剪
- 内部节点表示特征, 叶节点表示类
- 决策树的损失函数通常是正则化的极大似然函数
- 选择全局最优决策树是 NP 完全问题, 现实中常采用启发式方法近似求解.
- 决策树学习算法: 通常是递归地选择最有特征, 并根据该特征对训练数据进行分割, 使各子数据集有最好的分类
- 特征选择: 选取对训练数据分类能力最强的特征. 准则: 信息增益或信息增益比
- 条件熵
- X给定条件下Y的条件熵:
$H(Y|X) = \sum_i p_i H(Y|X=x_i)$ , 其中$p_i = P(X=x_i)$ - 当熵和条件熵中的概率由数据估计 (特别是极大似然估计) 得到时, 分别叫 经验熵 (empirical entropy) 和经验条件熵
- X给定条件下Y的条件熵:
- 信息增益 information gain
- 表示得知特征X的信息而使得类Y的信息的不确定性减少的成都
- 特征A对数据集D的信息增益: 定义为经验熵与经验条件熵之差.
$g(D,A) = H(D)-H(D|A)$ - 一般地, 熵H(Y) 与条件熵H(Y|X) 之差成为互信息. 决策树中的信息增益等价于训练数据集中类与特征的互信息.
- 根据信息增益准则选择特征
- 取信息增益最大的特征. 信息增益的算法见 P61. (试着回想一下)
- 信息增益比
- 用信息增益准则选择特征, 存在的问题是偏向于选择取值较多的特征 (这样的特征信息增益较大, 但分类能力可能不强). 信息增益比可以校正这一问题.
- 信息增益比 = 信息增益 / D关于特征A的值的熵
$H_A(D)$ - 这个熵比较特别. 前面计算信息增益时的熵都是关于类别值的.
- ID3 算法: 选择信息增益最大的特征, 以该特征的所有取值创建分支.
- C4.5 算法: 用信息增益比
- 这两种算法主要针对分类问题
- 在损失函数中引入对复杂度的惩罚项: 叶节点数量. 等价于正则化.
- 记叶节点数量为 |T|, 叶节点 t 上有
$N_t$ 个样本点,$H_t(T)$ 为叶节点t上的经验熵 - 损失函数
$C_\alpha(T) = \sum_t N_t H_t(T) + \alpha|T|$
- 记叶节点数量为 |T|, 叶节点 t 上有
- 剪枝算法
- 计算每个节点的经验熵
- 递归地从叶节点向上回缩. 若一组叶节点 (即属于同一父节点的叶节点) 回缩后的损失函数值变小, 就把这些叶节点剪掉
- (可以由一种动态规划算法实现)
- 参机器学习技法 Lec9: +ml_机器学习技法_lim: Lec9-Decision-tree
- CART 算法特点: 二叉树, 分支准则基于平方误差或基尼指数
- 用于回归时, 也叫最小二乘回归树
- 用于分类时, 用基尼指数选择最优特征并决定切分点
- 概率分布的基尼指数:
$\mathrm{Gini}(p) = 1 - \sum_k p_k^2$ - 二分类问题中基尼指数, 熵的一半, 分类误差率 三个量的比较
- 基尼指数与熵之半的曲线很接近, 都可以近似代表分类误差率
- CART 算法剪枝
- 剪枝得到一个子树序列
- 序列中每个子树分别为某个
$\alpha$ 取值区间内的最优子树. 其中, 第一个子树就是整体树, 为$\alpha= 0$ 时的最优子树. 最后一个子树只有三个节点, 对应的$\alpha$ 最大 (更极端地, 当$\alpha \rightarrow \infty$ 时, 最优子树是单节点树)
- 序列中每个子树分别为某个
- 通过交叉验证从序列中选取最优子树.
- 在选择最优子树的同时, 也选定了最优的正则化系数
$\alpha$
- 在选择最优子树的同时, 也选定了最优的正则化系数
- 比较 tricky, 详细过程见 P72
- 剪枝得到一个子树序列
- LR 和最大熵模型都是对数线性模型
- 逻辑斯谛分布
- 分布函数
$F(x) = \frac{1}{1+\exp(-(x-\mu)/\gamma)}$ - 密度函数
$f(x) = \frac{\exp(-(x-\mu)/\gamma)}{\gamma(1+\exp(-(x-\mu)/\gamma)^2}$ -
$\mu$ 为位置参数,$\gamma$ 为形状参数
- 分布函数
- 二项逻辑斯谛回归模型
- 事件的几率 odds: 发生与不发生的概率之比 p/(1-p).
- logit 函数:
$\mathrm{logit}(p) = \log\frac{p}{1-p}$ - 对逻辑斯谛回归:
$\log\frac{P(Y=1|x)}{1-P(Y=1|x)} = w\cdot x$ . 即, Y=1 的对数几率是x的线性函数- 注: b 项已并入 w 向量
- 模型参数估计: 用极大似然估计
- 记
$P(Y=1|x) = h_w(x)$ . 方便起见, 简写为 h(x). - 似然函数:
$\prod_i [h(x_i)]^{y_i} [1-h(x_i)]^{1-y_i}$ - 对数似然函数:
$L(w) = \sum_i[y_i\log h(x_i) + (1-y_i)\log (1-h(x_i))] = \sum_i[y_i(w\cdot x_i)-\log(1+\exp(w\cdot x_i))]$
- 记
- 多项逻辑斯谛回归模型:
$y\in {1,2,...,K}$ $P(Y=k|x) = \frac{\exp(w_k\cdot x)}{1+\sum_{k=1}^{K-1}\exp(w_k\cdot x)},\ k=1,2,...,K-1$ $P(Y=K|x) = \frac{1}{1+\sum_{k=1}^{K-1}\exp(w_k\cdot x)}$
- 最大熵原理
- 概率模型学习的一个准则. 在满足约束条件的模型集合中选择熵最大的模型.
- 直观理解
- 概率模型首先要满足已有事实, 即约束条件
- 不确定的部分应该是”等可能的”. 通过熵的最大化来表示等可能性.
- 最大熵模型是最大熵原理在分类问题上的应用
- 三个概率分布
- 模型: 条件概率分布 P(Y|X)
- 联合分布的经验分布
$\tilde{P}(X,Y)$ $\tilde{P}(X=x,Y=y) = \frac{\nu(X=x,Y=y)}{N}$
- 边缘分布的经验分布
$\tilde{P}(X)$ $\tilde{P}(X=x) = \frac{\nu(X=x)}{N}$
- 约束条件的表示
- 特征函数 f(x,y): 描述输入x和输出y之间的某个事实
- 特征函数关于经验分布
$\tilde{P}(X,Y)$ 的期望值:$E_{\tilde{P}}(f) = \sum_{x,y}\tilde{P}(x,y)f(x,y)$ - 特征函数关于模型 P(Y|X) 和经验分布
$\tilde{P}(x)$ 的期望值:$E_P(f) = \sum_{x,y}\tilde{P}(x)P(y|x)f(x,y)$ - 模型获取训练数据中的信息 →
$E_P(f) = E_{\tilde{P}}(f)$
- 满足所有约束条件的模型集合:
$C\equiv {P\in\mathcal{P}|E_P(f_i)=E_{\tilde{P}}(f_i),\ i=1,2,...,n}$ - 条件熵:
$H(P) = -\sum_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)$ - 最大熵模型: 集合C中条件熵最大的模型
- 三个概率分布
- 最大熵模型的学习
- 约束最优化问题. 转化为无约束优化的对偶问题.
- 引入拉格朗日乘子
$w_i$ , 定义拉格朗日函数 L(P, w). 对偶问题:$\max_w\min_{P\in C}L(P,w)$ - 对偶函数:
$\Psi(w) = \min_{P\in C}L(P,w)$ . 最大熵模型的学习归结为对偶函数的极大化.
- 对偶函数等价于对数似然函数. 对偶函数的极大化等价于最大熵模型的极大似然估计.
- 最大熵模型的一般形式
$P_w(y|x) = \frac{1}{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 为权值向量
- LR 和最大熵模型的目标函数具有很好的性质, 是光滑的凸函数, 多种最优化方法都适用. 本节介绍最大熵模型的两种学习算法.
- 改进的迭代尺度法 (improved iterative scaling)
- 拟牛顿法
- 相关资料:
- Coursera 机器学习 week7: 从 hinge loss 切入, 内容少且浅. 给出了 LR 和 SVM 的选择建议.
- LFD 的 Lec14 SVM, Lec15 Kernel methods
- 脉络: 线性可分/硬间隔 → 线性/软间隔 → 非线性/核函数
- 什么是 SVM
- 一种二分类模型. 基本模型是定义在特征空间上的间隔最大的线性分类器, 间隔最大 使它有别于感知机.
- 引入核技巧(kernel trick), 就成为非线性分类器
- 三类: 线性可分 → 线性 → 非线性
- 学习策略: 间隔最大化 (可形式化为一个求解凸二次规划的问题)
- 什么是 核技巧与核方法
- 核技巧 kernel trick
- 当输入空间为欧氏空间或离散集合, 特征空间为希尔伯特空间时, 核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积.
- 通过使用核函数可以学习非线性支持向量机, 等价于隐式地在高维特征空间中学习线性支持向量机.
- 核方法 kernel method: 比 SVM 更为一般的机器学习方法
- 核技巧 kernel trick
- 法向量指向的一侧为正类
- 平面 wx + b = 0 的单位法向量: w/||w||
- 当数据线性可分时:
- 感知机利用误分类最小的策略, 有无穷多个解;
- 线性可分SVM利用间隔最大化求最优分离超平面, 解是唯一的.
- 函数间隔 functional margin
- 点距离分离超平面的远近可以表示分类预测的确信程度. 在超平面 w, b 确定的情况下, |wx + b| 能相对地表示点 x 距离超平面的远近. 进一步考虑符号, 则 y(wx+b) 可以表示分类的正确性及确信度
- 定义:
- 超平面 (w,b) 关于样本点 (x_i, y_i) 的函数间隔为
$\hat \gamma_i = y_i(w \cdot x_i + b)$ - 关于训练数据集的函数间隔为对各点函数间隔的最小值:
$\hat\gamma = \min_i \hat\gamma_i$
- 超平面 (w,b) 关于样本点 (x_i, y_i) 的函数间隔为
- 函数间隔不能唯一确定超平面, 因为等比例改变w和b时, 超平面不变, 但函数间隔改变.
- 几何间隔 geometric margin
- 定义:
- 超平面 (w,b) 关于样本点 (x_i, y_i) 的几何间隔为:
$\gamma_i = \frac{y_i}{||w||}(w\cdot x_i + b)$ - 关于训练数据集的几何间隔为
$\gamma = \min_i \gamma_i$
- 超平面 (w,b) 关于样本点 (x_i, y_i) 的几何间隔为:
- 几何间隔是实例点到超平面的带符号的距离
- 定义:
- 最大间隔分离超平面
- 求最大间隔分离超平面, 就是这样一个约束最优化问题
$\max_{w,b} \quad \gamma$ $\text{s.t.} \quad \frac{y_i}{||w||} (w\cdot x_i + b) \geq \gamma, i=1,2,...N$
- 等价于:
$\min_{w,b} \quad ||w||^2/2$ $\text{s.t.} \quad y_i(w\cdot x_i + b) -1 \geq 0, i=1,2,...N \quad(7.14)$
- 这是一个凸二次规划问题 (convex quadratic programming)
- 目标函数为二次函数, 约束函数为仿射函数
- 求最大间隔分离超平面, 就是这样一个约束最优化问题
- 可以证明, 线性可分训练数据集的最大间隔分离超平面是存在且唯一的
- 支持向量和间隔边界
-
支持向量: 线性可分情况下指与分离超平面距离最近的样本点. 满足
$y_i(w\cdot x_i +b) -1 = 0$ - 支持向量中的正例点和负例点分别位于超平面
$w\cdot x + b = \pm 1$ 上. - 这两个超平面为间隔边界. 两平面之间的距离为间隔, 等于 2/||w||.
- 支持向量中的正例点和负例点分别位于超平面
- 在决定分离超平面时只有支持向量起作用. 支持向量的个数一般很少, 所以 SVM 由很少的 “重要的” 训练样本确定.
-
支持向量: 线性可分情况下指与分离超平面距离最近的样本点. 满足
- 应用拉格朗日对偶性, 可以把原始问题转化为对偶问题.
- 优点: 1. 对偶问题往往更易求解. 2. 方便引入核函数
- 构建拉格朗日函数
- 对每个不等式约束引入 拉格朗日乘子
$\alpha_i \geq 0, i=1,2,...N$ $L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^N \alpha_i y_i (w\cdot x_i + b) + \sum_{i=1}^N \alpha_i \quad(7.18)$
- 对每个不等式约束引入 拉格朗日乘子
- 对偶问题是极大极小问题
$\max_{\alpha} \min_{w,b} L(w,b,\alpha)$ . 求解步骤:- 求
$\min_{w,b} L(w,b,\alpha)$ .- 可分别对 w, b 求偏导并令等于0. 可得
$w = \sum_{i=1}^N \alpha_i y_i x_i$ $\sum_{i=1}^N \alpha_i y_i = 0$
- 代入 7.18 可消去 w, b
- 可分别对 w, b 求偏导并令等于0. 可得
- 求
$\min_{w,b} L(w,b,\alpha)$ 对$\alpha$ 的极大. 变换符号, 等价于以下问题:
- 求
- 求出最优的
$\alpha^*$ 后:$w^* = \sum_i \alpha_i^* y_i x_i$ - $b^$ 可由任一 $\alpha_j^ > 0$ 的实例点求得
- 分离超平面为
$\sum_i \alpha_i^* y_i(x \cdot x_i)+b^* =0$ - 分类决策只依赖于输入 x 和训练样本输入的内积
-
w 和 b 只依赖于**
$\alpha_i^* > 0$ 的样本点, 这些点称为支持向量- KKT 条件之一:
$\alpha_i^* (y_i(w^* \cdot x_i + b^*) - 1) = 0, \quad i=1,2...N$ - 即: 样本点要么
$\alpha_i^* = 0$ , 要么在间隔边界上.
- 即: 样本点要么
- KKT 条件之一:
- 软间隔最大化
- 为每个样本点引入一个松弛变量
$\xi_i \geq 0$ , 约束条件变为$y_i(w\cdot x_i + b) \geq 1-\xi_i$ - //
$\xi_i$ 反映样本点由间隔边界偏向误分类侧的距离.
- //
- 目标函数变为
$\frac{1}{2} ||w||^2 + C \sum_i \xi_i$ - 前一项目标是使间隔尽量大, 后一项目标是使误分类点尽量少.
- 前一项相当于正则化, 后一项是 hinge loss
- C: 惩罚参数.
- 为每个样本点引入一个松弛变量
- 此时 w 的解唯一, b 的解不唯一
- 对偶问题: 与线性可分情况的区别, 仅仅是
$\alpha_i \geq 0$ 变成了$0 \leq \alpha_i \leq C$
- 软间隔的支持向量定义仍然是:
$\alpha_i^* > 0$ 的样本点. 但与硬间隔不同, 此时支持向量不一定在间隔边界上.-
$\alpha_i^* < C$ 的支持向量在间隔边界上 -
$\alpha_i^* = C$ 时- 若
$0<\xi_i<1$ , 支持向量在间隔边界与分离超平面之间 - 若
$\xi_i = 1$ , 支持向量在分离超平面上 - 若
$\xi_i > 1$ , 支持向量位于分离超平面误分一侧
- 若
-
- 线性 SVM 的另一种解释:
$\min_{w,b} \quad \sum_{i=1}^N [1-y_i(w\cdot x_i+b)]_+ + \lambda||w||^2$ - 其中第一项为经验损失
-
$[z]_+ = \max(0, z)$ 也即 relu 函数 -
$L(y(w\cdot x+b)) = [1-y(w\cdot x+b)]_+$ 称为合页损失函数 (hinge loss function) - 即: 函数间隔大于1时, 损失为0. 否则损失为
$1 - y_i(w \cdot x_i + b)$
-
- 第二项为正则化项
- 合页损失函数
- 合页损失函数是 0-1 损失函数的上界
- 虚线是感知机的损失函数. 相比之下 合页损失函数的要求更高. (不仅要分类正确, 而且确信度足够高时损失才是 0)
- 核函数
- 设
$\mathcal{X}$ 是输入空间,$\mathcal{H}$ 是特征空间, - 如果存在映射
$\phi(x): \mathcal{X}\rightarrow\mathcal{H}$ 使得$\forall x,z\in \mathcal{X},\ K(x,z)=\phi(x)\cdot\phi(z)$ - 则称 K(x,z) 为核函数.
- 设
- 在线性SVM的对偶问题中, 无论目标函数或决策函数都只涉及输入实例与实例之间的内积
- 核技巧: 只定义核函数 K(x,z), 不显式定义特征空间和映射函数
$\phi$ . 学习是隐式地在特征空间进行的.
- 多项式核函数
$K(x,z) = (x\cdot z + 1)^p$ - 高斯核函数
$K(x, z) = \exp(-\frac{||x-z||^2}{2\sigma^2})$ - 高斯函数是一种 radial basis function
- 字符串核函数:
-
$k_n(s,t)$ 给出字符串 s 和 t 中长度等于 n 的所有子串组成的特征向量的余弦相似度.
-
- 选择合适的 K(x,z). 把线性SVM的对偶问题的目标函数和决策函数里的内积换成核函数即可.
- 当 K(x,z) 为正定核函数时, 问题为凸二次规划问题, 有解.
- AdaBoost 算法
- 另见: 机器学习技法 Lec8 (notes)
- AdaBoost 算法的训练误差分析
- 这一节给出了训练误差的上界.
- 记
$\gamma_m = 0.5-e_m$ . 推论8.1 指出, 当$\gamma_m$ 存在下界$\gamma>0$ 时, 训练误差$\leq \exp(-2M\gamma^2)$ , 随着训练轮数M的增加以指数速率下降.
- AdaBoost 算法的另一种解释
- AdaBoost 算法等价于: 模型为加法模型, 损失函数为指数函数, 学习算法为前向分步算法时的二分类学习方法
-
加法模型与前向分步算法
- 加法模型: 由一系列基函数按一定系数组合而成的模型.
$f(x) = \sum_{m=1}^M \beta_m b(x;\gamma_m)$ - 加法模型参数多, 直接优化较复杂.
- 前向分步算法: 按累加顺序, 每步只学习一个基函数及其系数, 逐步逼近最优解, 降低优化的复杂度.
- 加法模型: 由一系列基函数按一定系数组合而成的模型.
- 提升树 boosting tree
- 以决策树为基函数的提升方法.
- 可表示为决策树的加法模型.
$f_M(x) = \sum_{m=1}^M T(x;\Theta_m)$ - 注: 没有组合系数.
- 针对不同问题提升树算法
- 用指数损失函数的分类问题
- 对于二类分类问题, 提升树可看做 AdaBoost 的特殊情况
- 用平方损失函数的回归问题
- 第m步的损失为
$L(y,f_{m-1}(x)+T(x;\Theta_m)) = [r-T(x;\Theta_m)]^2$ . 其中$r = y-f_{m-1}(x)$ 为残差. ← residual fitting
- 第m步的损失为
- 用一般损失函数的一般决策问题
- 用指数损失函数的分类问题
- 梯度提升
- 当提升树的损失函数为平方损失或指数损失时, 每一步优化很简单. 但对一般损失函数则不然.
- 针对这一问题, 梯度提升是一种近似方法, 用负梯度的值作为残差的近似值. (why?)