损失函数

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

Surrogate Loss

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

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

损失函数设计

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

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

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

常用损失函数

0-1 Loss

$$L(y, f(x)) = \left \{ \begin{array}{l} 1, & y \neq f(x) \\ 0, & y = f(x) \end{array} \right.$$

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

• 适用场合

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

Quadratic / Squared Error Loss

$$L(y, f(x)) = \frac 1 2 (y - f(x))^2$$

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

• 适用场合

  • 回归预测：线性回归
  • 分类预测：0-1 二分类（根据预测得分、阈值划分）

Logistic SE

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

  • 若模型对某样本非常确信为正例，给出大于1预测值
  • 此时模型会进行不必要、开销较大的优化

• 考虑对模型输出进行 sigmoid 变换后作为预测值，再应用平方错误损失函数

  $$L(y, f(x)) = \frac 1 2 (y - \sigma(f(x)))^2$$
  • Logistic SE 损失函数曲线对 0-1 损失拟合优于平方损失
  • 但负区间存在饱和问题，损失最大只有 0.5

Cross Entropy

交叉熵损失

$$\begin{align*} L(y, f(x)) & = -ylog(f(x)) \\ & = - \sum_{k=1}^K y_k log f(x)_k \end{align*}$$

• $y$：样本实际值
• $f(x)$：各类别预测概率
• $K$：分类数目

• 交叉熵损失综合二次损失、logistic SE 优势，以正样本为例

  • 预测值较大时：损失接近 0，避免无效优化
  • 预测值较小时：损失偏导趋近于 -1，不会出现饱和现象

• $y$ 为 one-hot 编码时实际值时

  • 分类问题仅某分量为 1：此时交叉熵损失同对数损失（负对数极大似然函数）
  • 标签问题则可有分量为 1

• 适合场合

  • 多分类问题
  • 标签问题

Hinge Loss

$$\begin{align*} L(y, f(x)) & = [1 - yf(x)]_{+} \\ [z]_{+} & = \left \{ \begin{array}{l} z, & z > 0 \\ 0, & z \leq 0 \end{array} \right. \end{align*}$$

• $y \in {-1, +1}$

• 合页损失函数：0-1 损失函数的上界，效果类似交叉熵损失函数

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

• 适用场合

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

收敛速度对比

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

• 二次损失对 $w$ 偏导

  $$\frac {\partial L} {\partial w} = (\sigma(z) - y) \sigma^{'}(z) x$$

  • $\sigma$：sigmoid、softmax 激活函数
  • $z = wx + b$

  • 考虑到 sigmoid 函数输入值绝对值较大时，其导数较小
  • 激活函数输入 $z=wx+b$ 较大时，$\sigma^{‘}(z)$ 较小，更新速率较慢

• Softmax 激活函数时，交叉熵对 $w$ 偏导

  $$\begin{align*} \frac {\partial L} {\partial w} & = -y\frac 1 {\sigma(z)} \sigma^{'}(z) x \\ & = y(\sigma(z) - 1)x \end{align*}$$

• 特别的，对 sigmoid 二分类

  $$\begin{align*} \frac {\partial L} {\partial w_j} & = -(\frac y {\sigma(z)} - \frac {(1-y)} {1-\sigma(z)}) \sigma^{'}(z) x \\ & = -\frac {\sigma^{'}(z) x} {\sigma(z)(1-\sigma(z))} (\sigma(z) - y) \\ & = x(\sigma(z) - y) \end{align*}$$
  • 考虑 $y \in {(0,1), (1,0)}$、$w$ 有两组
  • 带入一般形式多分类也可以得到二分类结果

不常用损失函数

Absolute Loss

绝对损失函数

$$L(y, f(x)) = |y-f(x)|$$

• 适用场合
  • 回归预测

Logarithmic Loss

对数损失函数（负对数极大似然损失函数）

$$L(y, P(y|x)) = -logP(y|x)$$

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

Exponential Loss

指数函数函数

$$L(y, f(x)) = exp\{-yf(x)\}$$

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

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为分类数目）

$$L(y, f(x)) = \frac 1 2 \sum_{y^{(j)} \neq f(x)} w_j (1 - f(x, y) + f(x, y^{(j)}))$$

• $w_j$：样本个体错误标签权重，对不同个体分布可不同
• $f(x, y^{(j)})$：分类器将输入 $x$ 预测为第 $j$ 类 $y^{(j)}$ 的置信度

• 伪损失函数考虑了预测 标签 的权重分布

  • 通过改变此分布，能够更明确的关注难以预测的个体标签，而不仅仅个体

• 伪损失随着分类器预测准确率增加而减小

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

• 适用场景

  • 多分类：Adaboost.M2

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

感知机模型

感知机：线性二分类模型（判别模型）

$$f(x) = sign(wx + b)$$

• $x \in \chi \subseteq R^n$：输入空间
• $y \in \gamma \subseteq R^n$：输出空间
• $w \in R^n, b \in R$：weight vector、bias
• 也常有$\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$能够将正、负实例点，完全正确划分到超平面 两侧，即 $$\begin{align*} wx_i + b > 0, & \forall y_i > 0 \\ wx_i + b < 0, & \forall y_i < 0 \end{align*}$$ 则称数据集T为线性可分数据集

感知机学习策略

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

0-1损失

经验风险：误分率（误分点总数）

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

绝对值损失

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

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

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

  $$\begin{align*} d_i & = \frac 1 {\|w\|} |wx_i + b| \\ & =-\frac 1 {\|w\|} y_i(wx_i + b) \end{align*}$$

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

  • $M$：误分类点集合
  • 损失函数是$w, b$的连续可导函数：使用$y_i$替代绝对值

• 损失函数$L(w,b)$梯度有

  $$\begin{align*} \bigtriangledown_wL(w, b) & = -\sum_{x_i \in M} y_ix_i \\ \bigtriangledown_bL(w, b) & = -\sum_{x_i \in M} y_i \end{align*}$$

学习算法

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$进行更新

   $$\begin{align*} w^{(n+1)} & \leftarrow w^{(n)} + \eta y_ix_i \\ b^{(n+1)} & \leftarrow b^{(n)} + \eta y_i \end{align*}$$

   • $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}$

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

$$xw + b = \hat w \hat x = 0$$

• 数据集$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$，有

  $$\forall i, y_i(\hat w_{opt} \hat x_i) > 0$$

  可取

  $$\gamma = \min_i \{ y_i (\hat w_{opt} \hat x) \}$$

  满足条件

感知机算法收敛性

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

• 可以证明

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

    $$\begin{align*} \hat w_k \hat w_{opt} & = \hat w_{k-1} \hat w_{opt} + \eta y_i \hat w_{opt} \hat x_i \\ & \geq \hat w_{k-1} \hat w_{opt} + \eta\gamma \\ & \geq k\eta\gamma \end{align*}$$

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

    $$\begin{align*} \|\hat w_k\|^2 & = \|\hat w_{k-1} + \eta y_i x_i \|^2 \\ & = \|\hat w_{k-1}\|^2 + 2\eta y_i \hat w_{k-1} \hat x_i + \eta^2 \|\hat x_i\|^2 \\ & \leq \|w_{k-1}\|^2 + \eta^2 \|\hat x_i\|^2 \\ & \leq \|w_{k-1}\|^2 + \eta^2 R^2 \\ & \leq k\eta^2 R^2 \end{align*}$$

• 则有

  $$\begin{align*} k \eta \gamma & \leq \hat w_k \hat w_{opt} \leq \|\hat w\| \|\hat w_{opt}\| = \|\hat w\| \leq \sqrt k \eta R \\ k^2 \gamma^2 & \leq k R^2 \end{align*}$$

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

  • $\eta \gamma^2$：超平面法向量最小增加量（移动步长）
  • $\eta R^2$：超平面法向最大增加量（移动距离）
  • 但是超平面不可能将所有点都归为同一侧

• 误分类次数有上界，经过有限次搜索可以找到将训练数据完全 正确分开的分离超平面，即训练数据集线性可分时，算法的迭代 形式是收敛的