机器学习

机器学习（Machine Learning，ML）就是让计算机从数据中进行自动学习，得到某种知识（或规律）。

机器学习问题在早期的工程领域也经常称为模式识别（Pattern Recognition，PR），但模式识别更偏向于具体的应用任务，比如光学字符识别、语音识别、人脸识别等。这些任务的特点是，对于我们人类而言，这些任务很容易完成，但我们不知道自己是如何做到的，因此也很难人工设计一个计算机程序来解决这些任务。一个可行的方法是设计一个算法可以让计算机自己从有标注的样本上学习其中的规律，并用来完成各种识别任务。

对一个预测任务，输入特征向量为${x}$，输出标签为${y}$，我们选择一个函数集合$\mathcal{F}$，通过学习算法$\mathcal{A}$和一组训练样本${\mathcal{D}}$，从$\mathcal{F}$中学习到函数$f^{}(x)$。这样对新的输入${x}$，就可以用函数$f^{}(x)$进行预测。

三要素

模型

机器学习的目标是找到一个模型来近似真实映射函数$g(x)$或真实条件概率分布$p_r(y|\pmb{x})$。

由于我们不知道真实的映射函数$g(x)$或条件概率分布$p_r(y|\pmb{x})$的具体形式，因而只能根据经验来假设一个函数集合$\mathcal{F}$,称为假设空间(Hypothesis Space), 然后通过观测其在训练集$\mathcal{D}$上的特性，从中选择一个理想的假设(Hypothesis) $f^*\in\mathcal{F}$。

假设空间$\mathcal{F}$通常为一个参数化的函数族
$$
\mathcal{F}={f(\boldsymbol{x};\theta)|\theta\in\mathbb{R}^d},
$$
其中$f(x;\theta)$是参数为$\theta$的函数，也称为模型(Model),$d$为参数的数量。
常见的假设空间可以分为线性和非线性两种，对应的模型$f$也分别称为线性模型和非线性模型。

线性模型
线性模型的假设空间为一个参数化的线性函数族，即

$$
f(\boldsymbol{x};\theta)=\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+b,
$$
其中参数$\theta$包含了权重向量$w$和偏置$b$。

非线性模型
广义的非线性模型可以写为多个非线性基函数$\phi(x)$的线性组合
$$
f(\boldsymbol{x};\theta)=\boldsymbol{w}^\mathrm{T}\boldsymbol{\phi}(\boldsymbol{x})+b,
$$
其中$\phi(x)=[\phi_1(x),\phi_2(x),\cdots,\phi_K(x)]^{\mathrm{T}}$为$K$个非线性基函数组成的向量，参数$\theta$包含了权重向量$w$和偏置$b$。
如果$\phi(x)$本身为可学习的基函数，比如
$$
\phi_k(\boldsymbol{x})=h(\boldsymbol{w}_k^\mathrm{T}\boldsymbol{\phi}^{\prime}(\boldsymbol{x})+b_k),\forall1\leq k\leq K,
$$
其中$h(\cdot)$为非线性函数，$\phi^{\prime}(x)$为另一组基函数，$w_k$和$b_k$为可学习的参数，则$f(x;\theta)$ 就等价于神经网络模型。

学习准则

一个好的模型$f(x,\theta^*)$应该在所有$(\pmb{x},y)$的可能取值上都与真实映射函数$y=g(x)$一致，即
$$
\begin{aligned}|f(\boldsymbol{x},\theta^*)-y|<\epsilon,\quad\forall(\boldsymbol{x},y)\in\mathcal{X}\times\mathcal{Y},\end{aligned}
$$

或与真实条件概率分布$p_r(y|x)$一致，即

$$
\begin{aligned}|f_y(\boldsymbol{x},\theta^*)-p_r(y|\boldsymbol{x})|<\epsilon,\quad\forall(\boldsymbol{x},y)\in\mathcal{X}\times\mathcal{Y},\end{aligned}
$$
其中$\epsilon$是一个很小的正数，$f_y(x,\theta^*)$为模型预测的条件概率分布中$y$对应的概率。
模型$f(\pmb{x};\theta)$的好坏可以通过期望风险(Expected Risk)$\mathcal{R}(\theta)$来衡量，其定义为
$$
\mathcal{R}(\theta)=\mathbb{E}_{(\boldsymbol{x},y)\sim p_r(\boldsymbol{x},y)}[\mathcal{L}\big(y,f(\boldsymbol{x};\theta)\big)],
$$

其中$p_r(\pmb{x},y)$为真实的数据分布，$\mathcal{L}(y,f(x;\theta))$为损失函数，用来量化两个变量之间的差异。

损失函数
损失函数是一个非负实数函数，用来量化模型预测和真实标签之间的差异。
0-1损失函数 最直观的损失函数是模型在训练集上的错误率，即0-1损失函数（0-1 Loss Function）：
$\begin{aligned}
\mathcal{L}(y,f(\boldsymbol{x};\theta))& =\begin{cases}&0&\mathrm{if}y=f(\boldsymbol{x};\theta)\\&1&\mathrm{if}y\neq f(\boldsymbol{x};\theta)&\end{cases} \
&=I\big(y\neq f(\boldsymbol{x};\theta)\big), \
\text{其中}I(\cdot)\text{ 是指示函数。}
\end{aligned}$
虽然0-1损失函数能够客观地评价模型的好坏，但其缺点是数学性质不是很好：不连续且导数为0，难以优化。因此经常用连续可微的损失函数替代。
平方损失函数 平方损失函数Quadratic Loss Function）经常用在预测标签y为实数值的任务中，定义为
$\mathcal{L}\big(y,f(\boldsymbol{x};\theta)\big)=\frac{1}{2}\Big(y-f(\boldsymbol{x};\theta)\Big)^2$
平方损失函数一般不适用于分类问题。
交叉熵损失函数 交叉熵损失函数（Cross-Entropy Loss Function）一般用于分类问题。
假设样本的标签$y\in{1,\cdots C}$为离散的类别，模型$f(x;\theta)\in[0,1]^C$ 的输出为类别标签的条件概率分布，即

$$
\begin{aligned}p(y=c|\boldsymbol{x};\theta)=f_{c}(\boldsymbol{x};\theta),\end{aligned}
$$

并满足

$$
f_c(\boldsymbol{x};\theta)\in[0,1],\quad\sum_{c=1}^Cf_c(\boldsymbol{x};\theta)=1
$$

假设样本的类别为k，那么它属于第k类的概率为1，其它类的概率为0。对于两个概率分布，一般可以用交叉熵来衡量它们的差异。标签的真实分布$y$和模型预测分布$f(x;\theta)$之间的交叉熵为
$$
\mathcal{L}(\boldsymbol{y},f(\boldsymbol{x};\theta))=-\sum_{c=1}^Cy_c\log f_c(\boldsymbol{x};\theta).
$$
因为$y$为one-hot向量，上面公式也可以写为

$$
\mathcal{L}\big(y,f(\boldsymbol{x};\theta)\big)=-\log f_{y}(x;\theta),
$$

其中$f_y(x;\theta)$可以看作真实类别$y$的似然函数。因此，交叉熵损失函数也就是负对数似然损失函数(Negative Log-Likelihood Function)。

Hinge损失函数

对于二分类问题，假设$y$的取值为${-1,+1},f(x;\theta)\in\mathbb{R}$。$Hingc$ 损失函数(Hinge Loss Function)为

$$
\begin{aligned}
\mathcal{L}(y,f(\boldsymbol{x};\theta))& =\max\left(0,1-yf(\boldsymbol{x};\theta)\right) \
&\triangleq[1-yf(\boldsymbol{x};\theta)]_{+},
\end{aligned}
$$

其中$[x]_+=\operatorname*{max}(0,x)$。

风险最小化准则
一个好的模型 $f(x;\theta)$ 应当有一个比较小的期望错误，但由于不知道真实的数据分布和映射函数，实际上无法计算其期望风险 $\mathcal{R}(\theta)$。给定一个训练集$\mathcal{D}={(x^{(n)},y^{(n)})}_{n=1}^N$,我们可以计算的是经验风险(Empirical Risk),即在训练集上的平均损失：
$$
\mathcal{R}{\mathcal{D}}^{emp}(\theta)=\frac1N\sum{n=1}^N\mathcal{L}(y^{(n)},f(x^{(n)};\theta)).
$$
因此，一个切实可行的学习准则是找到一组参数$\theta^*$使得经验风险最小，即
$$
\theta^{*}=\arg\min\mathcal{R}_{\theta}^{emp}(\theta),
$$
这就是经验风险最小化(Empirical Risk Minimization, ERM)准则。
验风险最小化原则很容易导致模型在训练集上错误率很低，但是在未知数据上错误率很高。这就是所谓的过拟合（Overfitting）。
过拟合：给定一个假设空间F，一个假设f属于F，如果存在其他的假设f′也属于F,使得在训练集上f的损失比f′ 小，但在整个样本空间上f′ 比f的损失小，那么就说假设f过度拟合训练数据。
优化算法
参数与超参数在机器学习中，优化又可以分为参数优化和超参数优化。模型$f(x;\theta)$中的$\theta$称为模型的参数，可以通过优化算法进行学习。除了可学习的参数$\theta$之外，还有一类参数是用来定义模型结构或优化策略的，这类参数叫做超参数（Hyper-Parameter）。
常见的超参数包括：聚类算法中的类别个数、梯度下降法中的步长、正则化项的系数、神经网络的层数、支持向量机中的核函数等。超参数的选取一般都是组合优化问题，很难通过优化算法来自动学习。因此，超参数优化是机器学习的一个经验性很强的技术，通常是按照人的经验设定，或者通过搜索的方法对一组
超参数组合进行不断试错调整。
梯度下降法：