Loss Function

损失函数

  • 损失函数可以视为模型与真实的距离的度量
    • 因此损失函数设计关键即,寻找可以代表模型与真实的距离的统计量
    • 同时为求解方便,应该损失函数最好应满足导数存在

Surrogate Loss

代理损失函数:用优化方便的损失函数代替难以优化的损失函数,间接达到优化原损失函数的目标

  • 如 0-1 损失难以优化,考虑使用二次损失、交叉熵损失替代

损失函数设计

  • 对有监督学习:真实 已知,可以直接设计损失函数

  • 对无监督学习:真实 未知,需要给定 真实标准

    • NLP:需要给出语言模型
    • EM 算法:熵最大原理

常用损失函数

01_se_ce_hinge_loss

0-1 Loss

  • 0-1 损失函数梯度要么为 0、要么不存在,无法通过梯度下降方法优化 0-1 损失

  • 适用场合

    • 二分类:Adaboost
    • 多分类:Adaboost.M1

Quadratic / Squared Error Loss

  • 平方错误损失函数可导,可以基于梯度下降算法优化损失函数

  • 适用场合

    • 回归预测:线性回归
    • 分类预测:0-1 二分类(根据预测得分、阈值划分)

Logistic SE

  • 平方损失用于二分类时存在如下问题(模型输出无限制)

    • 若模型对某样本非常确信为正例,给出大于1预测值
    • 此时模型会进行不必要、开销较大的优化
  • 考虑对模型输出进行 sigmoid 变换后作为预测值,再应用平方错误损失函数

    • Logistic SE 损失函数曲线对 0-1 损失拟合优于平方损失
    • 但负区间存在饱和问题,损失最大只有 0.5

Cross Entropy

交叉熵损失

  • $y$:样本实际值
  • $f(x)$:各类别预测概率
  • $K$:分类数目
  • 交叉熵损失综合二次损失、logistic SE 优势,以正样本为例

    • 预测值较大时:损失接近 0,避免无效优化
    • 预测值较小时:损失偏导趋近于 -1,不会出现饱和现象
  • $y$ 为 one-hot 编码时实际值时

    • 分类问题仅某分量为 1:此时交叉熵损失同对数损失(负对数极大似然函数)
    • 标签问题则可有分量为 1
  • 适合场合

    • 多分类问题
    • 标签问题

Hinge Loss

  • $y \in {-1, +1}$
  • 合页损失函数:0-1 损失函数的上界,效果类似交叉熵损失函数

    • 要求分类不仅正确,还要求确信度足够高损失才为 0
    • 即对学习有更高的要求
  • 适用场合

    • 二分类:线性支持向量机

收敛速度对比

  • 指数激活函数时:相较于二次损失,收敛速度更快

  • 二次损失对 $w$ 偏导

    • $\sigma$:sigmoidsoftmax 激活函数
    • $z = wx + b$
    • 考虑到 sigmoid 函数输入值绝对值较大时,其导数较小
    • 激活函数输入 $z=wx+b$ 较大时,$\sigma^{‘}(z)$ 较小,更新速率较慢
  • Softmax 激活函数时,交叉熵对 $w$ 偏导

  • 特别的,对 sigmoid 二分类

    • 考虑 $y \in {(0,1), (1,0)}$、$w$ 有两组
    • 带入一般形式多分类也可以得到二分类结果

不常用损失函数

Absolute Loss

绝对损失函数

  • 适用场合
    • 回归预测

Logarithmic Loss

对数损失函数(负对数极大似然损失函数)

  • 适用场合
    • 多分类:贝叶斯生成模型、逻辑回归

Exponential Loss

指数函数函数

  • 适用场合
    • 二分类:前向分步算法

Pseudo Loss

伪损失:考虑个体损失 $(x_i, y_i)$ 如下,据此构造伪损失

  • $h(x_i, y_i)=1, \sum h(x_i, y)=0$:完全正确预测
  • $h(x_i, y_i)=0, \sum h(x_i, y)=1$:完全错误预测
  • $h(x_i, y_i)=1/M$:随机预测(M为分类数目)
  • $w_j$:样本个体错误标签权重,对不同个体分布可不同
  • $f(x, y^{(j)})$:分类器将输入 $x$ 预测为第 $j$ 类 $y^{(j)}$ 的置信度
  • 伪损失函数考虑了预测 标签 的权重分布

    • 通过改变此分布,能够更明确的关注难以预测的个体标签,而不仅仅个体
  • 伪损失随着分类器预测准确率增加而减小

    • 分类器 $f$ 对所有可能类别输出置信度相同时,伪损失最大达到 0.5,此时就是随机预测
    • 伪损失大于 0.5 时,应该将使用 $1-f$
  • 适用场景

    • 多分类:Adaboost.M2

Perceptron

  • 输入:实例的特征向量
  • 输出:实例类别+1、-1

感知机模型

感知机:线性二分类模型(判别模型)

  • $x \in \chi \subseteq R^n$:输入空间
  • $y \in \gamma \subseteq R^n$:输出空间
  • $w \in R^n, b \in R$:weight vectorbias
  • 也常有$\hat w = (w^T, b^T)^T, \hat x = (x^T + 1)^T$, 则有$\hat w \hat x = wx + b$
  • 感知机模型的假设空间是定义在特征空间的所有 linear classification model/linear classifier,即函数 集合${f|f(x)=wx+b}$

  • 线性方程$wx+b=0$:对应特征空间$R^n$中一个hyperplane

    • $w$:超平面法向量
    • $b$:超平面截距
    • 超平面将特征空间划分为两个部分,其中分别被分为正、负 两类

    • 也被称为separating hyperplane

Linearly Separable Data Set

  • 对数据集$T={(x_1,y_1),\cdots,(x_N,y_N)}$,若存在超平面 $S: wx + b=0$能够将正、负实例点,完全正确划分到超平面 两侧,即 则称数据集T为线性可分数据集

感知机学习策略

感知机学习策略:定义适当损失函数,并将经验风险极小化,确定 参数$w, b$

0-1损失

经验风险:误分率(误分点总数)

  • 不是参数$w, b$的连续可导函数,不易优化

绝对值损失

经验风险:误分类点到超平面距离

  • 对误分类数据$(x_i, y_i)$,有$-y_i(wx_i + b) > 0$

  • 则误分类点$(x_i, y_i)$到超平面S距离

  • 则感知机损失函数可定义为 $L(w,b) = -\sum_{x_i \in M} y_i(wx_i + b)$

    • $M$:误分类点集合
    • 损失函数是$w, b$的连续可导函数:使用$y_i$替代绝对值
  • 损失函数$L(w,b)$梯度有

学习算法

Stochastic Gradient Descent

随机梯度下降法

  • 输入:数据集$T$、学习率$\eta, 0 \leq \eta \leq 1$
  • 输出:$w,b$、感知模型$f(x)=sgn(wx+b)$
  1. 选取初值$w_0, b_0$

  2. 随机选取一个误分类点$(x_i, y_i)$,即$y_i(wx_i+b) \leq 0$ ,对$w, b$进行更新

    • $0 < \eta \leq 1$:learning rate,学习率,步长
  3. 转2,直至训练集中无误分类点

  • 不同初值、随机取点顺序可能得到不同的解
  • 训练数据线性可分时,算法迭代是收敛的
  • 训练数据不线性可分时,学习算法不收敛,迭代结果发生震荡
  • 直观解释:当实例点被误分类,应该调整$w, b$值,使得分离 超平面向误分类点方向移动,减少误分类点与超平面距离, 直至被正确分类

学习算法对偶形式

todo

算法收敛性

为方便做如下记号

  • $\hat w = (w^T, b^T)^T, \hat w \in R^{n+1}$
  • $\hat x = (x^T, 1)^T, \hat x \in R^{n+1}$

此时,感知模型可以表示为

  • 数据集$T={(x_1, y_1), (x_2, y_2),…}$线性可分,其中: $x_i \in \mathcal{X = R^n}$, $y_i \in \mathcal{Y = {-1, +1}}$,则
  • 存在满足条件$|\hat w{opt}|=1$超平面 $\hat w{opt} \hat x = 0$将训练数据完全正确分开,且 $\exists \gamma > 0, yi(\hat w{opt} x_i) \geq \gamma$

  • 令$R = \arg\max_{1\leq i \leq N} |\hat x_i|$,则 随机梯度感知机误分类次数$k \leq (\frac R \gamma)^2$

超平面存在性

  • 训练集线性可分,存在超平面将训练数据集完全正确分开,可以 取超平面为$\hat w_{opt} \hat x = 0$

  • 令$|\hat w_{opt}| = 1$,有

    可取

    满足条件

感知机算法收敛性

  • 给定学习率$\eta$,随机梯度下降法第k步更新为 $\hat wk = \hat w{k-1} + \eta y_i \hat x_i$

  • 可以证明

    • $\hat wk \hat w{opt} \geq k\eta\gamma$

    • $|\hat w_k|^2 \leq k \eta^2 R^2$

  • 则有

  • 直观理解就是超平面最大移动次数不大于最大移动距离 除以最小移动步长

    • $\eta \gamma^2$:超平面法向量最小增加量(移动步长)
    • $\eta R^2$:超平面法向最大增加量(移动距离)
    • 但是超平面不可能将所有点都归为同一侧
  • 误分类次数有上界,经过有限次搜索可以找到将训练数据完全 正确分开的分离超平面,即训练数据集线性可分时,算法的迭代 形式是收敛的