监督学习简明指南
Star

原创内容 Afshine Amidi 和 Shervine Amidi
翻译: Wang Hongnian. 由朱小虎, Chaoying Xue and Z 审阅

监督学习简介

给定一组数据点 $\{x^{(1)}, ..., x^{(m)}\}$ 和与其对应的输出 $\{y^{(1)}, ..., y^{(m)}\}$，我们想要建立一个分类器，学习如何从 $x$ 预测 $y$。

预测类型不同类型的预测模型总结如下表 :

	回归	分类
输出	连续	类
例子	线性回归	Logistic回归，SVM，朴素贝叶斯

模型类型不同型号总结如下表 :

	判别模型	生成模型
目标	直接估计 $P(y\|x)$	估计 $P(x\|y)$ 然后推导 $P(y\|x)$
所学内容	决策边界	数据的概率分布
例图
示例	回归，SVMs	GDA，朴素贝叶斯

符号和一般概念

假设假设我们选择的模型是 $h_\theta$。对于给定的输入数据 $x^{(i)}$，模型预测输出是 $h_\theta(x^{(i)})$。

损失函数损失函数是一个 $L:(z,y)\in\mathbb{R}\times Y\longmapsto L(z,y)\in\mathbb{R}$ 的函数，其将真实数据值 $y$ 和其预测值 $z$ 作为输入，输出它们的不同程度。常见的损失函数总结如下表：

最小二乘误差	Logistic损失	铰链损失	交叉熵
$\displaystyle\frac{1}{2}(y-z)^2$	$\displaystyle\log(1+\exp(-yz))$	$\displaystyle\max(0,1-yz)$	$\displaystyle-\Big[y\log(z)+(1-y)\log(1-z)\Big]$

线性回归	Logistic回归	SVM	神经网络

成本函数成本函数 $J$ 通常用于评估模型的性能，使用损失函数 $L$ 定义如下：

\[\boxed{J(\theta)=\sum_{i=1}^mL(h_\theta(x^{(i)}), y^{(i)})}\]

梯度下降记学习率为 $\alpha\in\mathbb{R}$，梯度下降的更新规则使用学习率和成本函数 $J$ 表示如下：

\[\boxed{\theta\longleftarrow\theta-\alpha\nabla J(\theta)}\]

备注：随机梯度下降（SGD）是根据每个训练样本进行参数更新，而批量梯度下降是在一批训练样本上进行更新。

似然给定参数 $\theta$ 的模型 $L(\theta)$ 的似然性用于通过最大化似然性来找到最佳参数θ。在实践中，我们使用更容易优化的对数似然 $\ell(\theta)=\log(L(\theta))$。我们有 :

\[\boxed{\theta^{\textrm{opt}}=\underset{\theta}{\textrm{arg max }}L(\theta)}\]

牛顿算法牛顿算法是一种数值方法，目的是找到一个 $\theta$ 使得 $\ell'(\theta)=0$. 其更新规则如下：

\[\boxed{\theta\leftarrow\theta-\frac{\ell'(\theta)}{\ell''(\theta)}}\]

备注：多维泛化，也称为 Newton-Raphson 方法，具有以下更新规则：

\[\theta\leftarrow\theta-\left(\nabla_\theta^2\ell(\theta)\right)^{-1}\nabla_\theta\ell(\theta)\]

线性模型

线性回归

我们假设 $y|x;\theta\sim\mathcal{N}(\mu,\sigma^2)$

正规方程通过设计 $X$ 矩阵，使得最小化成本函数时 $\theta$ 有闭式解：

\[\boxed{\theta=(X^TX)^{-1}X^Ty}\]

LMS算法通过 $\alpha$ 学习率，训练集中 m 个数据的最小均方（LMS）算法的更新规则也称为Widrow-Hoff学习规则，如下 :

\[\boxed{\forall j,\quad \theta_j \leftarrow \theta_j+\alpha\sum_{i=1}^m\left[y^{(i)}-h_\theta(x^{(i)})\right]x_j^{(i)}}\]

备注：更新规则是梯度上升的特定情况。

LWR 局部加权回归，也称为LWR，是线性回归的变体，通过 $w^{(i)}(x)$ 对其成本函数中的每个训练样本进行加权，其中参数 $\tau\in\mathbb{R}$ 定义为 :

\[\boxed{w^{(i)}(x)=\exp\left(-\frac{(x^{(i)}-x)^2}{2\tau^2}\right)}\]

分类和逻辑回归

Sigmoid函数 sigmoid 函数 $g$，也称为逻辑函数，定义如下：

\[\forall z\in\mathbb{R},\quad\boxed{g(z)=\frac{1}{1+e^{-z}}\in]0,1[}\]

逻辑回归我们假设 $y|x;\theta\sim\textrm{Bernoulli}(\phi)$ 。我们有以下形式：

\[\boxed{\phi=p(y=1|x;\theta)=\frac{1}{1+\exp(-\theta^Tx)}=g(\theta^Tx)}\]

备注：对于逻辑回归的情况，没有闭式解。

Softmax回归当存在超过2个结果类时，使用softmax回归（也称为多类逻辑回归）来推广逻辑回归。按照惯例，我们设置 $\theta_K=0$，使得每个类 $i$ 的伯努利参数 $\phi_i$ 等于：

\[\boxed{\displaystyle\phi_i=\frac{\exp(\theta_i^Tx)}{\displaystyle\sum_{j=1}^K\exp(\theta_j^Tx)}}\]

广义线性模型

指数分布族如果可以用自然参数 $\eta$，也称为规范参数或链接函数，充分统计量 $T(y)$ 和对数分割函数 $a(\eta)$ 来表示，则称一类分布在指数分布族中，函数如下：

\[\boxed{p(y;\eta)=b(y)\exp(\eta T(y)-a(\eta))}\]

备注：我们经常会有 $T(y)=y$。此外，$\exp(-a(\eta))$ 可以看作是归一化参数，确保概率总和为1

下表中是总结的最常见的指数分布：

分布	$\eta$	$T(y)$	$a(\eta)$	$b(y)$
伯努利	$\log\left(\frac{\phi}{1-\phi}\right)$	$y$	$\log(1+\exp(\eta))$	$1$
高斯	$\mu$	$y$	$\frac{\eta^2}{2}$	$\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{y^2}{2}\right)$
泊松	$\log(\lambda)$	$y$	$e^{\eta}$	$\displaystyle\frac{1}{y!}$
几何	$\log(1-\phi)$	$y$	$\log\left(\frac{e^\eta}{1-e^\eta}\right)$	$1$

GLM的假设广义线性模型（GLM）是旨在将随机变量 $y$ 预测为 $x\in\mathbb{R}^{n+1}$ 的函数，并依赖于以下3个假设：

$(1)\quad\boxed{y|x;\theta\sim\textrm{ExpFamily}(\eta)}$

$(2)\quad\boxed{h_\theta(x)=E[y|x;\theta]}$

$(3)\quad\boxed{\eta=\theta^Tx}$

备注：普通最小二乘法和逻辑回归是广义线性模型的特例

支持向量机

支持向量机的目标是找到使决策界和训练样本之间最大化最小距离的线。

最优间隔分类器最优间隔分类器 $h$ 是这样的：

\[\boxed{h(x)=\textrm{sign}(w^Tx-b)}\]

其中 $(w, b)\in\mathbb{R}^n\times\mathbb{R}$ 是以下优化问题的解决方案：

\[\boxed{\min\frac{1}{2}||w||^2}\quad\quad\textrm{使得 }\quad \boxed{y^{(i)}(w^Tx^{(i)}-b)\geqslant1}\]

备注：该线定义为 $\boxed{w^Tx-b=0}$。

合页损失合页损失用于SVM，定义如下：

\[\boxed{L(z,y)=[1-yz]_+=\max(0,1-yz)}\]

核给定特征映射 $\phi$，我们定义核 $K$ 为：

\[\boxed{K(x,z)=\phi(x)^T\phi(z)}\]

在实践中，由 $K(x,z)=\exp\left(-\frac{||x-z||^2}{2\sigma^2}\right)$ 定义的核 $K$ 被称为高斯核，并且经常使用这种核。

备注：我们说我们使用“核技巧”来计算使用核的成本函数，因为我们实际上不需要知道显式映射 $\phi$，通常，这非常复杂。相反，只需要 $K(x,z)$ 的值。

拉格朗日我们将拉格朗日 $\mathcal{L}(w,b)$ 定义如下：

\[\boxed{\mathcal{L}(w,b)=f(w)+\sum_{i=1}^l\beta_ih_i(w)}\]

备注：系数 $\beta_i$ 称为拉格朗日乘子。

生成学习

生成模型首先尝试通过估计 $P(x|y)$ 来模仿如何生成数据，然后我们可以使用贝叶斯法则来估计 $P(y|x)$

高斯判别分析

设置高斯判别分析假设 $y$ 和 $x|y=0$ 且 $x|y=1$ 如下：

$(1)\quad\boxed{y\sim\textrm{Bernoulli}(\phi)}$

$(2)\quad\boxed{x|y=0\sim\mathcal{N}(\mu_0,\Sigma)}$

$(3)\quad\boxed{x|y=1\sim\mathcal{N}(\mu_1,\Sigma)}$

估计下表总结了我们在最大化似然时的估计值：

$\widehat{\phi}$	$\widehat{\mu_j}\quad{\small(j=0,1)}$	$\widehat{\Sigma}$
$\displaystyle\frac{1}{m}\sum_{i=1}^m1_{\{y^{(i)}=1\}}$	$\displaystyle\frac{\sum_{i=1}^m1_{\{y^{(i)}=j\}}x^{(i)}}{\sum_{i=1}^m1_{\{y^{(i)}=j\}}}$	$\displaystyle\frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^T$

朴素贝叶斯

假设朴素贝叶斯模型假设每个数据点的特征都是独立的：

\[\boxed{P(x|y)=P(x_1,x_2,...|y)=P(x_1|y)P(x_2|y)...=\prod_{i=1}^nP(x_i|y)}\]

解决方案最大化对数似然给出以下解，$k\in\{0,1\},l\in[\![1,L]\!]$

\[\boxed{P(y=k)=\frac{1}{m}\times\#\{j|y^{(j)}=k\}}\quad\textrm{ 和 }\quad\boxed{P(x_i=l|y=k)=\frac{\#\{j|y^{(j)}=k\textrm{ 和 }x_i^{(j)}=l\}}{\#\{j|y^{(j)}=k\}}}\]

备注：朴素贝叶斯广泛用于文本分类和垃圾邮件检测。

基于树的方法和集成方法

这些方法可用于回归和分类问题。

CART 分类和回归树（CART），通常称为决策树，可以表示为二叉树。它们具有可解释性的优点。

随机森林这是一种基于树模型的技术，它使用大量的由随机选择的特征集构建的决策树。与简单的决策树相反，它是高度无法解释的，但其普遍良好的表现使其成为一种流行的算法。

备注：随机森林是一种集成方法。

提升提升方法的思想是将一些弱学习器结合起来形成一个更强大的学习器。主要内容总结在下表中：

自适应增强	梯度提升
• 在下一轮提升步骤中，错误的会被置于高权重	• 弱学习器训练剩余的错误

其他非参数方法

$k$-最近邻 $k$-最近邻算法，通常称为$k$-NN，是一种非参数方法，其中数据点的判决由来自训练集中与其相邻的k个数据的性质确定。它可以用于分类和回归。

备注：参数 k 越高，偏差越大，参数 k 越低，方差越大。

学习理论

联盟让 $A_1, ..., A_k$ 成为 $k$ 个事件。我们有：

\[\boxed{P(A_1\cup ...\cup A_k)\leqslant P(A_1)+...+P(A_k)}\]

Hoeffding不等式设$Z_1, .., Z_m$是从参数 $\phi$ 的伯努利分布中提取的 $m$ iid 变量。设 $\phi$ 为其样本均值，固定 $\gamma>0$。我们有：

\[\boxed{P(|\phi-\widehat{\phi}|>\gamma)\leqslant2\exp(-2\gamma^2m)}\]

备注：这种不平等也被称为 Chernoff 界限。

训练误差对于给定的分类器 $h$，我们定义训练误差 $\widehat{\epsilon}(h)$，也称为经验风险或经验误差，如下：

\[\boxed{\widehat{\epsilon}(h)=\frac{1}{m}\sum_{i=1}^m1_{\{h(x^{(i)})\neq y^{(i)}\}}}\]

可能近似正确 (PAC) PAC是一个框架，在该框架下证明了许多学习理论的结果，并具有以下假设：
- 训练和测试集遵循相同的分布
- 训练样本是相互独立的

打散给定一个集合 $S=\{x^{(1)},...,x^{(d)}\}$ 和一组分类器 $\mathcal{H}$，如果对于任意一组标签 $\{y^{(1)}, ..., y^{(d)}\}$ 都能对分，我们称 $\mathcal{H}$ 打散 $S$，我们有：

\[\boxed{\exists h\in\mathcal{H}, \quad \forall i\in[\![1,d]\!],\quad h(x^{(i)})=y^{(i)}}\]

上限定理设 $\mathcal{H}$ 是有限假设类，使得 $|\mathcal{H}|=k$ 并且使 $\delta$ 和样本大小 $m$ 固定。然后，在概率至少为 $1-\delta$ 的情况下，我们得到：

\[\boxed{\epsilon(\widehat{h})\leqslant\left(\min_{h\in\mathcal{H}}\epsilon(h)\right)+2\sqrt{\frac{1}{2m}\log\left(\frac{2k}{\delta}\right)}}\]

VC维给定无限假设类 $\mathcal{H}$ 的 Vapnik-Chervonenkis(VC) 维，注意 $\textrm{VC}(\mathcal{H})$ 是由 $\mathcal{H}$ 打散的最大集合的大小。

备注：$\mathcal{H} = \{$2维线性分类器集$\}$ 的 VC 维数为3。

定理 (Vapnik) 设$\mathcal{H}$，$\textrm{VC}(\mathcal{H})=d$，$m$ 为训练样本数。概率至少为 $1-\delta$，我们有：

\[\boxed{\epsilon(\widehat{h})\leqslant \left(\min_{h\in\mathcal{H}}\epsilon(h)\right) + O\left(\sqrt{\frac{d}{m}\log\left(\frac{m}{d}\right)+\frac{1}{m}\log\left(\frac{1}{\delta}\right)}\right)}\]

监督学习简明指南 Star