-
数据集：一组样本构成的集合为数据集。一般将数据集分为两部分，训练集和测试集。训练集中的样本是用来训练模型的；测试集是用来验证模型好坏的。
-
特征向量：我们通常用一个𝐷 维向量$x=[x_, x_2, ...,x_D]^T$表示一个芒果的所有特征构成的向量，称为特征向量（Feature Vector），其中每一维表示一个特征。
-
独立同分布假设：机器学习假设每个样本都是独立同分布地从样本中抽取出来的。
-
机器学习三要素：模型、策略、算法
-
模型$f(x;\theta)$的好坏可以用期望风险来衡量： $$ R(\theta)=E_{(x,y)\sim p_r(x,y)}[L(y, f(x;\theta))] $$ 其中$p_r(x,y)$为真实分布，$L(y, f(x;\theta))$为损失函数，用来衡量两个分布之间的差异
由于真实的分布正是我们想要求的，所以无法求出期望风险
-
损失函数：损失函数是一个非负实数函数，用来量化模型预测和真实标签之间的差异
-
0-1损失函数也就是错误率，虽然0-1损失函数能够客观地评价模型的好坏，但其缺点是数学性质不是很好；不连续且导数为0，难以优化。因此经常用连续可微的损失函数替代：
-
平方损失函数：平方损失函数（Quadratic Loss Function）经常用在预测标签𝑦为实数值的任务中，定义为：（平方损失函数一般不适用于分类问题） $$ L(y, f(x;\theta)=\frac{1}{2}(y-f(x;\theta)))^2 $$
-
交叉熵损失函数：一般用于分类问题，假设样本标签$y\in[1,2,...C]$为离散的类别，模型为：$f(x;\theta)\in [0,1]^C$的输出为类别标签的条件概率分布，即： $$ p(y=c|x;\theta)=f_c(x;\theta)\ f_c(x;\theta)\in[0,1], \sum_{c=1}^Cf_c(x;\theta)=1 $$ 我们可以用一个𝐶 维的one-hot向量𝒚来表示样本标签。假设样本的标签为𝑘，那么标签向量𝒚只有第𝑘维的值为1，其余元素的值都为0。标签向量𝒚可以看作样本标签的真实条件概率分布𝑝𝑟 (𝒚|𝒙)，即第𝑐维（记为𝑦𝑐，1 ≤ 𝑐 ≤ 𝐶）是类别为 𝑐 的真实条件概率。假设样本的类别为 𝑘，那么它属于第 𝑘 类的概率为 1，属于其他类的概率为0。
对于两个概率分布，一般用交叉熵衡量它们的差异。标签的真实分布y和，模型的预测分布$f(x;\theta)$之间的交叉熵为： $$ \begin{aligned} L(y, f(x;\theta))&=-y^Tlog(f(x;\theta))\ &=\sum_{c=1}^Cy_clog(f_c(x;\theta)) \end{aligned} $$ 比如一个三分类问题，真实分布为：y=[0,0,1]，模型预测的标签分布为：$f(x;\theta)=[0.3,0.3,0.4]^T$，则它们的交叉熵为：−(0 ×
log(0.3) + 0 ×log(0.3) + 1 × log(0.4)) = − log(0.4)。
因为y是one-hot向量，公式也可以写为： $$ L(y, f(x;\theta))=-log(f_y(x;\theta)) $$ 其中$f_y(x;\theta)$可以看做真实类别y的似然函数，因此交叉熵损失函数就是负的对数似然函数。
-
Hinge损失函数：对于二分类问题，假设y的取值为{-1,+1}，$f(x;\theta)\in R$： $$ L(y,f(x;\theta))=max(0, 1-yf(x;\theta))\triangleq[1-yf(x;\theta)]+，其中[x]+=max(0,x) $$
-
风险最小化准则：
一个比较好的模型应当有比较小的期望风险错误，但是由于不知道真实的数据分布和映射函数，实际上无法计算期望风险$R(\theta)$，给定一个训练集$D={x^{(n)}, y^{(n)}}{n=1}^N$，我们可以计算的是经验风险，即在训练集上的平均损失： $$ R_D^{emp}(\theta)=\frac{1}{N}L(y^{(n)}, f(x^{(n)};\theta)) $$ 因此一个切实可行的学习准则就是找到一组参数$\theta^$使得经验风险最小： $$ \theta^=argmin{\theta}R_D^{emp} $$ 过拟合：根据大数定理可知，当训练集大小 |𝒟| 趋向于无穷大时，经验风险就趋向于期望风险然而通常情况下，我们无法获取无限的训练样本，并且训练样本往往是真实数据的一个很小的子集或者包含一定的噪声数据，不能很好地反映全部数据的真实分布。经验风险最小化原则很容易导致模型在训练集上错误率很低，但是在未知数据上错误率很高。这就是所谓的过拟合（Overfitting）。
过拟合问题往往是由于训练数据少和噪声以及模型能力强等原因造成的。为了解决过拟合问题，一般在经验风险最小化的基础上再引入参数的正则化（Regularization）来限制模型能力，使其不要过度地最小化经验风险。这种准则就是结构风险最小化（Structure Risk Minimization，SRM）准则： $$ \begin{aligned} \theta^*&=argmin_{\theta}R_D^{struct}(\theta)\ &=argmin_{\theta}R_D^{emp}+\frac{1}{2}\lambda ||\theta||^2\ &=argmin_{\theta}\frac{1}{N}L(y^{(n)}, f(x^{(n)};\theta))+\frac{1}{2}\lambda ||\theta||^2 \end{aligned} $$ 上面的正则化项采用的是$l_2$范数，还可以使用$l_1$范数，用来减少参数空间，避免过拟合。
欠拟合：模型不能很好地拟合数据，一般是由于模型拟合能力不足造成的。
-
优化算法：
-
梯度下降法：在机器学习中，最简单、常用的优化算法就是梯度下降法，即首先初始化参数$\theta_0$，然后按下面的迭代公式来计算训练集𝒟 上风险函数的最小值： $$ \begin{aligned} \theta_{t+1}&=\theta_t-\eta\frac{\partial R_D(\theta)}{\partial \theta}\ &=\theta_t-\eta\frac{1}{N}\sum_{n=1}^N\frac{\partial L(y^{(n)}, f(x^{(n)};\theta))}{\partial \theta} \end{aligned} $$
-
提前停止：针对梯度下降的优化算法，除了加正则化项之外，还可以通过提前停止来防止过拟合。在梯度下降训练的过程中，由于过拟合的原因，在训练样本上收敛的参数，并不一定在测试集上最优。因此，除了训练集和测试集之外，有时也会使用一个验证集（Validation Set）来进行模型选择，测试模型在验证集上是否最优。验证集也叫作开发集（Development Set）。在每次迭代时，把新得到的模型 𝑓(𝒙; 𝜃) 在验证集上进行测试，并计算错误率。如果在验证集上的错误率不再下降，就停止迭代。这种策略叫提前停止（EarlyStop）。如果没有验证集，可以在训练集上划分出一个小比例的子集作为验证集。
-
随机梯度下降法：在上面的的梯度下降法中，目标函数是整个训练集上的风险函数，这种方式称为批量梯度下降法（Batch Gradient Descent，BGD）。批量梯度下降法在每次迭代时需要计算每个样本上损失函数的梯度并求和。当训练集中的样本数量𝑁 很大时，空间复杂度比较高，每次迭代的计算开销也很大。在机器学习中，我们假设每个样本都是独立同分布地从真实数据分布中随机抽取出来的，真正的优化目标是期望风险最小。批量梯度下降法相当于是从真实数据分布中采集 𝑁 个样本，并由它们计算出来的经验风险的梯度来近似期望风险的梯度。为了减少每次迭代的计算复杂度，我们也可以在每次迭代时只采集一个样本，计算这个样本损失函数的梯度并更新参数，即随机梯度下降法（Stochastic Gradient Descent，SGD）。随机梯度下降法也叫作增量梯度下降法。当经过足够次数的迭代时，随机梯度下降也可以收敛到局部最优解[Nemirovski et al., 2009]。
-
小批量随机梯度下降法：随机梯度下降法的一个缺点是无法充分利用计算机的并行计算能力。小批量梯度下降法（Mini-Batch Gradient Descent）是批量梯度下降和随机梯度下降的折中。每次迭代时，我们随机选取一小部分训练样本来计算梯度并更新参数，这样既可以兼顾随机梯度下降法的优点，也可以提高训练效率。 $$ \theta_{t+1}=\theta_t-\eta\frac{1}{K}\sum_{(x,y)\in\delta_t}\frac{\partial L(y, f(x;\theta))}{\partial \theta} $$
-
从机器学习的角度来看，自变量就是样本的特征向量$x\in R^D$（每一维对应一个自变量），因变量是标签𝑦，这里𝑦 ∈ ℝ是连续值（实数或连续整数）。假设空间是一组参数化的线性函数： $$ f(x;w,b)=w^Tx+b $$ 为了简单起见，将公式简化为： $$ f(x;\hat{w})=\hat{w}\hat{x} $$ 其中$\hat{w}$和$\hat{x}$分别称为增广权重向量和增广特征向量： $$ \hat{x}=[x_1, x_2, ..., x_D, 1]\ \hat{w}=[w_1, w_2, ...,w_D, b] $$ 给定一组包含N个训练样本的训练集$D={(x^{(n)},y^{(n)})}_{n-1}^N$，我们希望能够学习一个最优的线性回归模型参数$w$
我们使用四种不同的参数估计方法：
1.经验风险最小化：
由于线性回归的标签y和模型输出都为连续的实数值，因此平方损失函数非常合适衡量真实标签和预测标签的差异：
$$
\begin{aligned}
R(w)&=\sum_{n=1}^NL(y^{(n)}, f(x^{(n)};\theta))\
&=\frac{1}{2}\sum_{n=1}^N(y^{(n)}-w^Tx^{(n)})^2\
&=\frac{1}{2}||y-X^Tw||^2
\end{aligned}
$$
风险函数$R(w)$是关于w的凸函数，对w的偏导为：
$$
\begin{aligned}
\frac{\partial R(w)}{\partial w}&=\frac{1}{2}\frac{\partial||y-X^Tw||}{\partial w}\
&=-X(y-X^Tw)
\end{aligned}
$$
令$\frac{\partial R(w)}{\partial w}=0$得到的最优参数为：
$$
\begin{aligned}
w^*&=(XX^T)^{-1}Xy\
&=(\sum_{n=1}^Nx^{(n)}(x^{(n)})^T)^{-1}(\sum_{n=1}^Nx^{(n)}y^{(n)})
\end{aligned}
$$
这种方法也叫作最小二乘法，在最小二乘法中，$XX^T\in R^{(D+1)\times (D+1)}$必须存在逆矩阵，即$XX^T$必须是满秩的(
1).先用主成分分析等方法来预处理数据，消除不同特征之间的相关性，然后再使用最小二乘法来估计参数
2).使用梯度下降算法来估计参数
2.结构风险最小化
在经验风险最小化的基础上加入正则化项： $$ R(w)=\frac{1}{2}||y-X^Tw||^2+\frac{1}{2}\lambda||w||^2 $$ 3.最大似然估计
机器学习任务可以分为两类：(1).样本的特征向量x与标签y存在未知的函数关系y=h(x)；(2)两者的条件概率p(y|x)服从某个分布。前面的最小二乘法属于第一类，直接建模x和y之间的函数关系。
假设y为一个随机变量，并且由函数$f(x;\theta)=w^Tx$加上一个随机噪声$\epsilon$决定： $$ \begin{aligned} y&=f(x;w)+\epsilon\ &=w^Tx+\epsilon \end{aligned} $$ 其中$\epsilon$服从均值为0，方差为$\sigma^2$的高斯分布，这样y服从均值为$w^Tx$、方差为$\sigma^2$的高斯分布： $$ \begin{aligned} p(y|x;w,\sigma)&=N(y;w^Tx,\sigma^2)\ &=\frac{1}{\sqrt{2\pi\sigma}}exp(-\frac{(y-w^Tx)^2}{2\sigma^2}) \end{aligned} $$ 参数w在D上的似然函数为： $$ \begin{aligned} p(y|X;w,\sigma)&=\prod_{n=1}^Np(y^{(n)}|x^{(n)};w,\sigma)\ &=\prod_{n=1}^NN(y^{(n)};w^Tx^{(n)},\sigma^2) \end{aligned} $$ 为了计算方便，对数似然函数取对数得到对数似然函数： $$ \begin{aligned} \log p(y|x;w,\sigma)&=\sum_{n=1}^N\log N(y^{(n)};w^Tx^{(n)},\sigma^2)\ &=\sum_{n=1}^N(-\frac{1}{2}\log 2\pi\sigma^2-\frac{(y-w^Tx)^2}{2\sigma^2}) \end{aligned} $$ 令$\frac{\partial \log p(y|X;w,\sigma)}{\partial w}=0$，可以得到： $$ w=(XX^T)^{-1}Xy $$ 结果和最小二乘法解一致。
4.最大后验估计
最大似然估计的缺点在于训练数据比较少时会发生过拟合，估计的参数可能不准确，为了避免过拟合，可以对参数加上一些先验知识：
假设参数w是一个随机向量，并服从一个先验分布$p(w;v)$，为了简单起见一般令$p(w;v)$为各向同性的高斯分布(即协方差矩阵为$v^2 I$，其中$I$为单位阵)： $$ p(w;v)=N(w;0,v^2I) $$ 根据贝叶斯公式，参数w的后验分布为： $$ p(w|X,y;v,\sigma)=\frac{p(w,y|X;v,c)}{\sum_wp(w,y|X;v,\sigma)}\propto p(y|X,w;\sigma)p(w;v) $$ 最大后验估计是指最优参数为后验分布$p(w|X,y;v,\sigma)$中概率密度最高的参数： $$ w^{MAP}=argmax_wp(y|x,w;\sigma)p(w;v) $$ 取对数似然函数： $$ \begin{aligned} \log p(w|X,y;v,\sigma)&=\log p(y|x,w;\sigma)+\log p(w;v)\ &\propto -\frac{1}{2\sigma^2}||y-X^Tw||^2-\frac{1}{2v^2}w^Tw\ &=-\frac{1}{2\sigma^2}||y-X^Tw||^2-\frac{1}{2v^2}w^Tw \end{aligned} $$ 可以看出，最大后验概率等价于平方损失的结构风险最小化，其中正则化系数$\lambda =\frac{\sigma^2}{v^2}$
为了避免过拟合，我们经常会在模型的拟合能力和复杂度之间进行权衡。拟合能力强的模型一般复杂度会比较高，容易导致过拟合。相反，如果限制模型的复杂度，降低其拟合能力，又可能会导致欠拟合。因此，如何在模型的拟合能力和复杂度之间取得一个较好的平衡，对一个机器学习算法来讲十分重要。偏差-方差分解（Bias-Variance Decomposition）为我们提供了一个很好的分析和指导工具。
以回归问题为例，假设样本的真实分布为$p_r(x,y)$，并采用平方损失函数，模型f(x)的期望错误为： $$ R(\theta)=E_{(x,y)\sim p_r(x,y)}[L(y, f(x;\theta))] $$ 那么最优模型为： $$ f^(x)=E_{y\sim p_r(x,y)}[y] $$ $f^(x)$为使用平方损失作为优化目标的最优模型，其损失为： $$ \epsilon=E_{(x,y)\sim p_r(y|x)}[(y-f^*(x))^2] $$ 损失$\epsilon$通常由样本分布及噪声引起的，无法通过优化模型来减少。
期望错误可以分解为： $$ \begin{aligned} R(f)&=E_{(x,y)\sim p_r(x,y)}[(y-f^(x)+f^(x)-f(x))^2]\ &=E_{x\sim p_r(x)}[(f(x)-f^(x))^2]+\epsilon \end{aligned} $$ 在实际训练一个模型 𝑓(𝒙) 时，训练集 𝒟 是从真实分布 $𝑝_𝑟(𝒙, 𝑦) $上独立同分布地采样出来的有限样本集合。不同的训练集会得到不同的模型。令 $𝑓_𝒟(𝒙)$ 表示在训练集𝒟 上学习到的模型，一个机器学习算法（包括模型以及优化算法）的能力可以用不同训练集上的模型的平均性能来评价。差距为： $$ \begin{aligned} E_D[(f_D(x)-f^(x))^2]&=E_D[(f_D(x)-E_D[f_D(x)]+E_D[f_D(x)]-f^(x))^2]\ &=(E_D[f_D(x)]-f^(x))^2+(E_D[(f_D(x))-f^*(x)])^2 \end{aligned} $$ 其中第一项为偏差（Bias），是指一个模型在不同训练集上的平均性能和最优模型的差异，可以用来衡量一个模型的拟合能力。第二项是方差（Variance），是指一个模型在不同训练集上的差异，可以用来衡量一个模型是否容易过拟合。
方差一般会随着训练样本的增加而减少。当样本比较多时，方差比较少，这时可以选择能力强的模型来减少偏差。然而在很多机器学习任务上，训练集往往都比较有限，最优的偏差和最优的方差就无法兼顾。随着模型复杂度的增加，模型的拟合能力变强，偏差减少而方差增大，从而导致过拟合。以结构风险最小化为例，我们可以调整正则化系数 𝜆 来控制模型的复杂度。当 𝜆 变大时，模型复杂度会降低，可以有效地减少方差，避免过拟合，但偏差会上升。当 𝜆 过大时，总的期望错误反而会上升。因此，一个好的正则化系数 𝜆 需要在偏差和方差之间取得比较好的平衡。下图给出了机器学习模型的期望错误、偏差和方差随复杂度的变化情况，其中红色虚线表示最优模型。最优模型并不一定是偏差曲线和方差曲线的交点。
偏差和方差分解给机器学习模型提供了一种分析途径，但在实际操作中难以直接衡量。一般来说，当一个模型在训练集上的错误率比较高时，说明模型的拟合能力不够，偏差比较高。这种情况可以通过增加数据特征、提高模型复杂度、减小正则化系数等操作来改进。当模型在训练集上的错误率比较低，但验证集上的错误率比较高时，说明模型过拟合，方差比较高。这种情况可以通过降低模型复杂度、加大正则化系数、引入先验等方法来缓解。此外，还有一种有效降低方差的方法为集成模型，即通过多个高方差模型的平均来降低方差。
监督学习：
- 回归
- 分类
- 结构化学习(如：序列标注)
无监督学习
强化学习
特征选择（Feature Selection）是选取原始特征集合的一个有效子集，使得基于这个特征子集训练出来的模型准确率最高。简单地说，特征选择就是保留有用特征，移除冗余或无关的特征。
- 子集搜索
-
$l1$ 正则化
线性判别分析、主成分分析和自编码器