3.2.机器学习

    机器学习（ML）就是让计算机从数据中进行自动学习，得到某种知识（或规律），通常指从观测数据（样本）中寻找规律，并利用学习的规律（模型）对未知或无法观测的数据进行预测，早期又称作模式识别（Pattern Recognition，PR）。

1.基本概念

    例：一堆苹果，每个苹果都有自己的特征Feature（重量、尺寸、颜色），最终还包含需要预测的标签Label（目标值），标签本身可以是连续值，也可以是离散值，我们可以将一个标记好特征和标签的苹果当做样本（Sample），又称为实例（Instance）。

    一组样本构成的集合称为数据集（Data Set），一般分：

1. 训练集（Training Set），用来训练模型，又称为训练样本（Training Sample）。

2. 测试集（Test Set），用来验证模型好坏，又称为测试样本（Testing Sample）。

    通常使用一个D维向量$x = [x_1, x_2, ..., x_D]^T$表示这个苹果的所有特征集合，又称特征向量（Feature Vector），每一个维度表示一个特征，苹果的标签则使用$y$表示。

    假设训练集$D$由$N$个样本组成，每个样本都是独立同分布的（Identically and Independently Distributed, IID），即独立从相同数据分布中抽取：$D = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，我们期望从一个函数集合$F = \{f_1(x),f_2(x),...\}$中找到一个最优解$f^?(x)$来趋近特征向量$x$和$y$之间的真实映射关系，对这样的样本可通过$f^?(x)$预测实际标签值：

$\hat{y} = f^?(x), \hat{p}(y|x) = f_y^?(x)$

    如何寻找这个“最优”的函数就是机器学习的关键，一般通过机器学习算法（Learning Algorithme）来完成，这个过程就称为学习（Learning）和训练（Training）过程，之后在测试集上计算结果并评估该函数的效果（精确率计算）：

$Acc(f^?(x)) = \frac{1}{D^{'}} \sum\limits_{(x,y) \in D^{'}} I(f^?(x) = y)$

2.三个基本要素

2.1.模型

    对机器学习而言，先确定输入空间$X$和输出空间$y$，不同机器学习任务只是输出空间不同：

1. 二分类：$y=\{+1,-1\}$或$y=\{1,0\}$

2. C分类：$y=\{1,2,...,C\}$

3. 回归问题：$y=R$，$R$是实数集

    $X + Y$就是一个样本空间，对于空间中$(x,y) \in X \times Y$，假设它们之间可通过下边两个函数来描述：

• 真实映射函数$y = g(x)$
• 真实条件概率分布$p_r(y|x)$

    机器学习的目标就是找到一个模型和两个函数结果逼近，我们假设一个函数集合$F$（假设空间,Hypothesis Space），通过观测$F$在$D$上的表现，从中选择一个理想的假设$F^?\in F$，最终如下：

$F = \{f(x;\theta)|\theta \in R^D\}$

    $f(x;\theta)$就是参数为$\theta$的函数，即模型（Modal），$D$为参数数量。

2.1.1.线性模型

    线性模型的假设空间为参数与的线性函数表：

$f(x;\theta) = w^T x + b$

    参数$\theta$包含了权重向量$w$和偏置项$b$。

2.1.2.非线性模型

    广义非线性模型可以写成多个非线性基函数（$\Phi(x)$）的线性组合：

$f(x;\theta) = w^T \Phi(x) + b$

    其中$\Phi(x) = [\Phi_1(x),\Phi_2(x),...,\Phi_K(x)]^T$为$K$个非线性基函数组成的向量，参数$\theta$包含了权重向量$w$和偏置项$b$，而之中$\Phi_K(x)$本身可以是一个学习的基函数，如：

$\Phi_k(x) = h(w_k^T \Phi^{'}(x) + b_k), \forall1 \le k \le K$

    神经网络模型$f(x;\theta)$的定义如下：

• $h(\cdot)$是非线性函数
• $\Phi^{'}(x)$是另一组基函数
• $w_k,b_k$是学习的参数

    上述条件构成了神经网络模型。

2.2.学习准则

    训练集$D = \{(x_n,y_n)\}_{n=1}^N$是$N$个独立同分布的（Identically and Independently Distributed, IID）样本组成，即每个样本是从$X \times Y$中按照某个未知分布$p_r(x,y)$独立随机产生。

此处$p_r(x,y)$必须是固定的，不会随时间变化，如果本身可变，那么就无法进行学习了。

    一个号的模型$f(x,\theta^?)$应该在所有的$(x,y)$的可能取值都逼近下边两个函数：

• 真实映射函数：$y = g(x)$

  $|f(x,\theta^?) - y| < \epsilon, \forall(x, y) \in X \times Y$
• 真实条件概率分布：$p_r(y|x)$

  $|f(x,\theta^?) - p_r(y|x)| < \epsilon, \forall(x, y) \in X \times Y$

其中$\epsilon$是一个很小整数，$f(x,\theta^?)$为模型预测条件概率分布中$y$对应的概率。

    模型$f(x,\theta^?)$的好坏通过期望风险（Expected Risk）来衡量，其定义为：

$R(\theta) = E_{(x,y) \thicksim p_r(x,y)}[L(y,f(x;\theta))]$

• $p_r(x,y)$为真实的数据分布
• $L(y,f(x;\theta))$为损失函数

2.2.1.损失函数

    常见的损失函数如下：

0-1损失函数（0-1 Loss Function）

    模型在训练集上的错误率：

$$L(y,f(x;\theta)) = \left\{ \begin{aligned} & 0, (y = f(x;\theta) \\ & 1, (y \neq f(x;\theta) \end{aligned} \right. = I(y \neq f(x; \theta))$$

    其中$I(\cdot)$是指示函数，它的缺点是数学性质不好，不连续且导数为0。

平方损失函数（Quadratic Loss Function）

    经常在预测$y$为实数值中使用（不适用于分类问题），定义如：

$L(y,f(x;\theta)) = \frac{1}{2}(y - f(x;\theta))^2$

交叉熵损失函数（Cross-Entropy Loss Function）

    一般用于分类问题，假设样本标签$y \in \{1,...,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\limits_{c=1}^C f_c(x;\theta) = 1$

    对于两个概率分布，一般可以用交叉熵来衡量它们的差异，标签的真实分布$y$和模型预测分布$f(x;\theta)$交叉熵如：

$L(y,f(x;\theta)) = -y^T \log f(x;\theta) = -\sum\limits_{c=1}^C y_c \log f_c(x;\theta)$

    其实$f(x;\theta)$可以看做真实类别$y$的似然函数，因此，交叉损失函数也就是负对数似然函数（Negative Log-Likelihood）

Hinge损失函数（Hinge Loss Function）

    一般用于二分类问题，假设$y$的取值为$\{-1,+1,\}, f(x;\theta) \in R$，它的Hinge损失函数为

$L(y,f(x;\theta) = \max(0, 1 - yf(x;\theta)) \triangleq[1 - yf(x;\theta)]_+$

    其中$[x]_+ = \max(0,x)$

2.2.2.风险最小化准则

    一个好的模型$f(x;\theta)$应当有一个比较小的期望错误，但由于不知道真实的数据分布和映射函数，实际上无法计算其期望风险$R(\theta)$，给定一个训练集$D = \{(x_n,y_n)\}_{n = 1}^N$，根据训练集可计算经验风险（Empirical Risk），即在训练集上的平均损失函数如：

$R_D^{emp}(\theta) = \frac{1}{N} \sum\limits_{n=1}^N L(y_n, f(x_n;\theta))$

    因此，一个切实可行的学习准则是找到一组参数$\theta^?$使得经验风险最小，即：

$\theta^? = arg \underset{\theta}{\min} R_D^{emp}(\theta)$

    上述表达式就是经验风险最小化（Empirical Risk Minimization，ERM）法则。

过拟合

    如果训练集大小$|D|$趋向于无穷大，经验风险就趋向于期望风险，但是：

1. 我们无法获取无限的训练样本。

2. 训练样本往往是真实数据的一个很小的子集或包含噪声，不能反应真实分布。

    ERM法则容易导致训练集错误率低，但在未知数据上错误率高，这就是过拟合（Overfitting）。

过拟合：给定一个假设空间$F$，一个假设$f$属于$F$，如果存在其他的假设$f^{'}$也属于$F$，使得在训练集上$f$的损失比$f^{'}$的损失小，但在整个样本空间上$f^{'}$的损失比$f$的损失小，那么就说假设$f$过度拟合训练数据。

    为了解决过拟合问题，通常在经验风险最小化的基础上引入参数的正则化（Regularization）来限制模型能力，使其不要过度地最小化经验风险，该准则为结构风险最小化（Structure Risk Minimization, SRM）：

$$= arg \underset{\theta}{\min} R_D^{emp}(\theta) + \frac{1}{2}\lambda||\theta||^2 \\ = arg \underset{\theta}{\min} \frac{1}{N} \sum\limits_{n=1}^N L(y_n, f(x_n;\theta)) + \frac{1}{2}\lambda||\theta||^2$$

    上述表达式中$||\theta||$是$l_2$范数的正则化项，用来减少参数空间，避免过拟合，$\lambda$则用来控制正则化强度。正则化项还可使用其他函数，如$l_1$范数，该范数的引入通常会有一定稀疏性——从贝叶斯角度，正则化是引入了先验分布，不依赖训练数据。

欠拟合

    过拟合相反的一个概念是欠拟合（Underfitting），即模型无法拟合训练数据，在训练集上的错误率比较高，欠拟合即模型能力不足。

2.3.优化算法

    如何找到最优的模型就是一个之后的优化问题。

    参数与超参数：机器学习中的优化分为参数优化和超参数优化：

1. 模型$f(x;\theta)$中的$\theta$称为模型参数，通过优化算法进行学习。
2. 用来定义模型结构优化策略的，称为超参数（Hyper-Parameter），如：

   1. 聚类算法中的类别个数

   2. 梯度下降法中的步长

   3. 正则化项的系数

   4. 神经网络的层数

   5. 支持向量机中的核函数

超参数选取一般是组合优化问题，很难通过优化自动学习，因此超参数要依赖经验，并通过一定手段探索最好的超参数组合。

2.3.1.梯度下降法

    为了利用成熟的优化方法，如共轭梯度、拟牛顿法，很多机器学习方法都选择成熟模型寻找最好的优化目标。机器学习中，最简单、常用的优化算法是梯度下降法，先初始化参数，然后按照下边公式计算风险函数的最小值：

$$= \theta_t - \alpha \frac{1}{N} \sum\limits_{n=1}^N \frac{\partial L(y_x, f(x_n;\theta))}{\partial \theta}$$

    其中$\theta_t$是第$t$次迭代时的参数值，$\alpha$为搜索步长，在机器学习过程中，$\alpha$就是学习率（Learning Rate）。

2.3.2.提前停止

    在梯度下降训练的过程中，由于过拟合原因，在训练样本上收敛的参数，并不一定在测试集上最优，所以除了测试集和测试集之外，有时候会使用验证集（Validation Set）进行模型训练。如果在验证集上的错误率不再下降，就停止迭代，这种策略就是提前停止（Early Stop）。

2.3.3.随机梯度下降

    在下边公式的梯度下降中：

$\theta_{t + 1} = \theta_t - \alpha \frac{\partial R_D(\theta)}{\partial \theta}$

    目标函数是整个训练集上的风险函数，这种方式称为批量梯度下降法（Batch Gradient Descent, BGD），批量梯度从真实数据分布中采集$N$个样本，并由它计算出来的经验风险的梯度近似期望风险的梯度——为了减少每次迭代的计算复杂度，我们可以在每次迭代时只采集一个样本，计算这个样本损失函数的梯度并更新，即随机梯度下降法（Stochastic Gradient Descent, SGD）。

    随机梯度下降vs批量梯度下降：每次迭代的优化目标是对所有样本的平均损失函数还是对单个样本的损失函数，由于SGD比BGD收敛更快，所以使用更广泛，而随机梯度下降相当于在批量梯度下降中引入了随机噪声。

2.3.4.小批量梯度下降

    SGD随机梯度下降无法使用计算机的并行运算能力。小批量梯度下降（Mini-Batch Gradient Descent，MBGD）是批量梯度下降和随机梯度下降的折中，每次迭代时，不是随机选取单个样本而是随机选取一小部分训练样本来计算梯度并更新参数。

    第$t$次迭代时，随机选取一个包含$K$个样本的子集$S_t$，计算该子集上每个样本损失函数梯度并且平均，然后更新参数：

$\theta_{t+1} \leftarrow \theta_t - \alpha \frac{1}{K} \sum\limits_{(x,y) \in S_t} \frac{\partial L(y_x, f(x_n;\theta))}{\partial \theta}$

    小批量梯度优点：

1. 运算速度很快

2. 计算开销也很小

3.线性回归

    线性回归（Linear Regression）是机器学习和统计学中最基础和最广泛应用的模型，它主要用来对自变量和因变量之间关系进行建模的回归分析：

1. 自变量数量为1时称为简单回归

2. 自变量数量大于1时称为多元回归

    线性函数公式如下：

$f(x;w,b) = w^Tx + b$

• 样本特征向量$x \in R^D$，每一个维度对应的自变量
• 因变量标签$y$是连续值（$y \in R$）

    其中权重向量$w \in R^D$和偏置项$b \in R$是可学习的参数，该模型称为线性模型，在数学中公式简化后得到：

$f(x;\hat{w}) = \hat{w}^T \hat{x}$

• $\hat{w}$为增广权重向量。
• $\hat{x}$为增广特征向量。

    之后简写成$f(x;w) = w^T x$

3.1.参数学习

    给定一组包含了$N$个训练样本的训练集$D = \{(x_n, y_n)\}_{n=1}^N$，我们希望学习一个最优的线性回归模型参数$w$，此处有四种不同的优化方法：

3.1.1.经验风险最小化

    这种方式平方损失函数非常适合衡量真实标签和预测标签之间的差异，该训练集的经验风险定义为：

$R(w) = \frac{1}{2}||y - X^Tw||^2$

• 其中$y = [y_1, ..., y_N]^T$是样本真实结果组成的列向量
• $x \in R^{{(D + 1)} \times N}$是样本输入特征组成的矩阵
• 风险函数$R(w)$是关于$w$的凸函数，对于$w$的偏导数如：

  $\frac{\partial R(w)}{\partial w} = \frac{1}{2} \frac{\partial||y - X^Tw||^2}{\partial w} = -X(y - X^Tw)$

上述公式中，设$\frac{\partial}{\partial w} R(w) = 0$则可以得到最优参数。

    这种求解线性回归参数的方法也叫最小二乘法（Least Square Method, LSM）。最小二乘法中，$XX^T \in R^{(D + 1) \times (D + 1)}$必须存在逆矩阵，即$XX^T$是满秩的（$rank(XX^T) = D + 1$）；也就是说，$X$中的行向量之间是线性不相关，即每个特征都和其他特征相互独立。如果$XX^T$不可逆，解法如：

1. 使用主成分分析等方法来预处理数据，消除不同特征之间相关性，然后再使用最小二乘法估计参数。

2. 使用梯度下降法估计参数，先初始化$w = 0$，然后使用公式迭代：$w \leftarrow w + \alpha X(y - X^Tw)$，这种利用梯度下降方法求解称为最小均方（Least Mean Squares, LMS）。

3.1.2.结构风险最小化

    如果特征之间有较大的多重共线性（Multicollinearity），会使得$XX^T$的逆在数值上无法准确计算，如此操作会让最小二乘法的计算不稳定，——为解决这种问题，提出了岭回归（Ridge Regression）。

    为$XX^T$的对角线元素都加上一个常数$\lambda$使$(XX^T + \lambda I)$满秩，即行列式不为0，最优参数如：

$w^? = (XX^T + \lambda I)^{-1}Xy$

• $\lambda > 0$为预先设置超参数
• $I$为单位矩阵

    岭回归的解$w^?$可看做结构风险最小化准则下的最小二乘法估计，最终目标函数可写成：

$R(w) = \frac{1}{2}||y - X^Tw||^2 + \frac{1}{2}\lambda ||w||^2$

    $\lambda > 0$为正则化系数。

3.1.3.最大似然估计

    机器学习任务两大类：

• 样本的特征向量$x$和标签$y$之间存在未知函数关系$y = h(x)$（前文提到的最小二乘法）。
• 另一类是条件概率$p(y|x)$服从某个未知分布

    假设$y$是一个随机变量，由$f(x;w) = w^Tx$加上随机噪声$\epsilon$：

$y = f(x:w) + \epsilon = w^Tx + \epsilon$

    上述表达式中

• $\epsilon$服从均值0、方差为$\sigma^2$的高斯分布
• $y$服从均值$w^Tx$、方差为$\sigma^2$的高斯分布

$p(y|x;w,\sigma) = N(y;w^T x, \sigma^2) = \frac{1}{\sqrt{2 \pi} \sigma} \exp (- \frac{(y - w^Tx)^2}{ 2 \sigma^2})$

    于是参数$w$在D上：

• 似然函数（Likelihood）：$p(y|X;w,\sigma) = \prod\limits_{n=1}^N p(y_n|x_n;w,\sigma) = \prod\limits_{n=1}^N N(y_n; w^T x_n, \sigma^2)$
• 「方便计算」对数似然函数（Log Likelihood）：$\log p(y|X;w,\sigma) = \sum\limits_{n=1}^N \log N(y_n; w^T x_n, \sigma^2)$
• 最大似然估计（Maximum Likelihood Estimation, MLE）表示找到一组参数$w$使得似然函数结果最大（或对数函数最大）：$w^{ML} = (XX^T)^{-1}Xy$

    缺点：如果训练数据比较少容易过拟合，估计参数不准确。

3.1.4.最大后验估计

    假设$w$是一个随机向量，并服从一个先验分布$p(w;v)$，为了简单，令它为各向同性的高斯分布：

$p(w;v) = N(w;0,v^2 I)$

• $v^2$就是每一个维上的方差

    根据贝叶斯公式，后验分布（Posterior Distribution）为：

$p(w|X,y;v,\sigma) = \frac{p(w,y|X;v,\sigma)}{\sum_w p(w,y|X;v,\sigma)} \varpropto p(y|X,w;\sigma)p(w;v)$

• 这种估计参数$w$的后验概率分布的方法为贝叶斯估计（Bayesian Estimation），是一种统计推断问题。
• 采用贝叶斯估计的线性回归也称贝叶斯线性回归（Bayesian Linear Regression）

    如果希望得到一个最优的参数值（点估计），可使用最大后验估计（Maximum A Posteriori Estimation, MAP），它表示最优参数为后验分布中概率密度最高的参数：

$w^{MAP} = arg \underset{w}{max} p(y|X,w;\sigma)p(w;v)$

    最大后验概率等价于平方损失的结构风险最小化，正则化系数$\lambda = \sigma^2 / v^2$

当 $v \rightarrow \infty$，先验分布$$p(w;v)退化成均匀分布，称无信息先验（Non-Informative Prior），最大后验估计退化成最大似然估计。

4.偏差-方差分解

    在模型拟合能力和复杂度之间权衡：

• 拟合能力强的模型复杂度比较高，容易过拟合。

• 如果限制模型复杂度，拟合能力低，容易欠拟合。

    偏差-方差分解（Bias-Variance Decomposition）是一个不错的指导工具。

    单个样本，不同训练集$D$得到的模型$f_D(x)$和最优模型$f^?(x)$的期望差距如：

$E_D[(f_D(x) - f^?(x))^2] = (E_D[f_D(x)] - f^?(x))^2 + E_D[(f_D(x) - E_D[f_D(x)])^2]$

• $(bias)^2 = E_x[(E_D[f_D(x)] - f^?(x))^2]$，偏差——一个模型在不同训练集上的平均性能和最优之间的差异，衡量拟合能力。
• $variance = E_x[E_D[(f_D(x) - E_D[f_D(x)])^2]]$，方差——一个模型在不同训练集上的差异，用来衡量模型是否过拟合。

5.算法类型

    监督学习（Supervised Learning，SL）：如果训练集中每个样本都有标签，通常称为监督学习，根据标签的不同又分：

1. 回归（Regression），y是连续值。

2. 分类（Classification），y是离散类别，模型此时称为分类器。

   1. 二分类（Binary Classification）

   2. 多分类（Multi-Class Classification）

3. 结构化学习（Structured Learning），一种特殊分类问题，y是结构化的对象（序列、树、图）

监督学习中还包含弱监督学习（Weakly Supervised Learning）和半监督学习（Semi-Supervised Learning，SSL）。

    无监督学习（Unsupervised Learning, RL）：从不包含目标标签的迅联样本中自动学习一些有价值的信息：聚类、密度估计、特征学习、降维。

    强化学习（Reinforcement Learning，RL）：一类通过交互来学习的机器学习算法，智能调整。

    它们和学习准则的关系

	监督学习	无监督学习	强化学习
训练样本	训练集$\{(x_n,y_n)\}_{n=1}^N$	训练集$\{x_n\}_{n=1}^N$	智能体和环境交互的轨迹$\tau$和累积奖励$G_{\tau}$
优化目标	$y = f(x)$或`p(y	x)`	$p(x)$或带隐变量$z$的`p(x
学习准备	期望风险最小化 最大似然估计	最大似然估计 最小重构错误	策略评估 策略改进

6.数据特征表示

    实际应用中，数据的类型多种多样，如文本、音频、图像、视频，不同类型数据的原始特征（Raw Feature）空间也不相同。

    图像特征：$M \times N$的图像直接使用$M \times N$维的向量，每一维的值为像素灰度值。

    文本特征：类别$y \in \{+1,-1\}$标记正面或负面评价，将样本$x$从文本形式转换成向量形式。

• 词袋（Bag-Of-Words, BoW）：一种简单的转换，假设训练集中词都来源于一个词表$V$，大小为$|V|$，每个样本都可以表示成$|V|$维的向量$x \in R^{|V|}$，如：

  • 我 喜欢 读书：$x_1 = [1 1 0 1]^T$
  • 我 讨厌 读书：$x_2 = [1 0 1 1]^T$

    词袋模型将文本看做词的集合，不考虑词序信息，不能精确表示文本信息。

• N元特征（N-Gram Feature），每N个连续词构成一个基本单元，然后用词袋模型表示，最简单的是二元特征（2-Gram），实际应用中，N元特征维度一般很高。

    表示学习——直接使用数据原始特征进行机器学习的问题：

1. 特征比较单一，需要线性（非线性）组合才能发挥作用。

2. 特征之间冗余度比较高

3. 并不是所有特征都对预测有用

4. 很多特征通常是易变的

5. 特征中往往存在一些噪声

    尝试大量的特征来寻找最佳特征——特征工程（Feature Engineering）；如何让机器自动地学习有效的特征——特征学习（Feature Learning），又称为表示学习（Representation Learning）。

6.1.传统特征学习

6.1.1.特征选择

    特征选择（Feature Selection）是选取原始特征的一个有效子集：保留部分特征，移除冗余或无关特征。子集搜索，一种直接特征选择方法（Subset Search），假设原始特征为D，则公有$2^D$个候选子集，特征选择目的是找到最优的候选子集。

1. 从空集开始，每一轮添加最优特征，为向前搜索（Forward Search）。

2. 从原始特征集合，每一轮删除最无用的特征，为向后搜索（Backward Search）。

    子集搜索方法分类：

1. 过滤式方法（Filter Method），不依赖具体机器学习模型的方法，每次增加最有用信息特征或删除最没有用的信息特征，特征信息量用信息增益（Information Gain）来衡量。

2. 包裹式方法（Wrapper Method），使用后续机器学习模型的准确率作为评价选择一个特征子集的方法，这种方法是将机器学习模型包裹到特征选择内部。

    $l_1$正则化——稀疏特征，因此可做特征选择。

6.1.2.特征抽取

    特征抽取（Feature Extraction）是构造一个新的特征空间，并将原始特征投影在新的空间中得到新的表示。

$x^{'} = Wx$

    这里$W \in R^{K \times D}$为映射矩阵。特征抽取可分有监督和无监督

• 有监督是抽取对一个特定预测任务最有用的特征，如线性判别分析（Linear Discriminant Analysis, LDA）。

• 无监督和具体任务无关，主要是减少冗余信息，如主成分分析（Principal Component Analysis, PCA）和自编码器（Auto-Encoder, AE）

特征选择和特征抽取经常称为维度约减或降维（Dimension Reduction）。

6.2.深度学习方法

    如果将特征的表示学习和机器学习有机地统一到一个模型中，建立一个端到端的学习算法，就可以有效地避免它们之间准则的不一致性，这种表示学习方法称为深度学习（Deep Learning, DL），它的难点：如何评价表示学习对最终系统输出结果的贡献和影响——贡献度分配问题。

7.评价指标

    分类问题评价指标：

    准确率（Accuracy），最常用的一个指标：

$A = \frac{1}{N} \sum\limits_{n=1}^N I(y_n = \hat{y_n})$

    错误率（Error Rate）

$\Epsilon = 1 - A = \frac{1}{N} \sum\limits_{n=1}^N I (y_n \neq \hat{y_n})$

    精确率和召回率：准确率是所有类别整体性能的平均，如果希望每个类都进行性能评估，则要计算精确率（Precision）和召回率（Recall），混淆矩阵中的四个格子的含义：

• 真正例（True Positive, TP）：一个样本真实类别为c，并且模型正确预测为c，记为：

  $TP_c = \sum\limits_{n=1}^N I ( y_n = \hat{y_n} = c )$
• 假负例（False Negative, FN）：一个样本真实类别为c，模型错误地预测为其他类，记为：

  $FN_c = \sum\limits_{n=1}^N I ( y_n = c \land \hat{y_n} \neq c )$
• 假正例（False Positive, FP）：一个样本的真实类别为其他类，模型错误预测为c，记为：

  $FP_c = \sum\limits_{n=1}^N I ( y_n \neq c \land \hat{y_n} = c )$
• 真负例（True Negative, TN）：一个样本的真实类别为其他类，模型也预测为其他类——对类别c来说，这种情况一般不用去关注。

    最终的混淆矩阵如下：

	预测	预测
	$\hat{y_n} = c$	$\hat{y_n} \neq c$
真实	$y=c$	$TP_c$	$FN_c$
真实	$y \neq c$	$FP_c$	$TN_c$

    精确率（Precision），也叫精度或查准率，类别c的查准率是所有预测为类别c的样本中正确的比例：

$P_c = \frac{TP_c}{TP_c + FP_c}$

    召回率（Recall），也叫查全率，类别c的查全率是所有真实标签为类别c的样本中预测正确的比例：

$R_c = \frac{TP_c}{TP_c + FN_c}$

    F值（F Measure）是一个综合指标，精确率和召回率的调和平均：

$F_c = \frac{(1 + \beta^2) \times P_c \times R_c}{\beta^2 \times P_c + R_c}$

    表达式中$\beta$用于平衡精确率和召回率的重要性。

    微平均和宏平均：为了计算分类算法在所有类别上的总体精确率、召回率和F1值，经常使用两种平均方法，分别为：

• Macro Arerage，宏平均

• Micro Average，微平均

    各种计算方法如：

$P_{macro} = \frac{1}{C} \sum\limits_{c=1}^C P_c$

$P_{micro} = \frac{1}{C} \sum\limits_{c=1}^C R_c$

$F1_{macro} = \frac{2 \times P_{macro} \times R_{macro}}{P_{macro} + R_{macro}}$

    微平均是每一个样本性能指标的算术平均值，对于单个样本而言，它的精确率和召回率是相同的，因此精确率的微平均和召回率的微平均也相同；实际应用中，可通过调整阈值来进行全面评价：

• AUC：Area Under Curve

• ROC：Receiver Operating Characteristic（曲线）

• PR：Precision-Recall（曲线）

    交叉验证（Cross-Validation）是一种比较好的衡量机器学习模型的统计方法，可避免划分训练集和测试机的随机性对评价结果的影响。

8.理论/定理

8.1.PAC学习理论

    希望通过一套理论能够分析问题难度、计算模型能力，为算法提供理论保证，并指导学习模型和算法设计——计算学习理论。计算学习理论（Computational Learning Theory）是机器学习的理论基础，其中最基础的理论是可能近似正确（Probably Approximately Correct, PAC）学习理论。

    机器学习中很关键的问题是期望错误和经验错误之间的差异，称为泛化错误（Generalization Error），泛化错误可衡量一个机器学习模型是否可泛化：

$G_D(f) = R(f) - R_D^{emp}(f)$

    根据大数定律，训练集大小$|D|$趋向无穷大时，泛化错误趋向于0：

$\underset{|D| \rightarrow \infty}{lim} R(f) - R_D^{emp}(f) = 0$

    由于$p(x,y)$和$g(x)$都未知，因此需要降低学习算法的期望，只要求学习算法可以以一定的概率学习到一个近似正确的假设，即PAC学习（PAC Learning），一个PAC可学习（PAC-Learnable）的算法是指该学习算法能在多项式时间内从合理数量的训练数据中学习到一个近似正确的值。PAC学习的两部分：

1. 近似正确（Approximately Correct）

   1. 假设$f \in F$是“近似正确”，即在泛化错误$G_D(f)$小于一个界限值$\epsilon$
   2. $\epsilon$一般介于0到1/2之间：$0 < \epsilon < \frac{1}{2}$
   3. 如果$G_D(f)$比较大，则模型不能用来正确预测
2. 可能（Probably）：一个学习算法$A$有可能以$1 - \delta$的概率学习到一个近似正确的假设，$\delta$一般介于0到1/2之间，$0 < \delta < \frac{1}{2}$

    最终的PAC公式如：

$P((R(f) - R_D^{emp}(f)) \le \epsilon) \ge 1 - \delta$

    其中参数$\epsilon, \delta$是和样本数量$N$以及假设空间$F$相关的变量，如果$\epsilon, \delta$固定，则可计算需要的样本数量：

$N(\epsilon,\delta) \ge \frac{1}{2 \epsilon^2} (\log{|F|} + \log{\frac{2}{\delta}})$

    为提高模型泛化能力，通常需要正则化（Regularization）限制模型复杂度。

8.2.没有免费午餐定理

    没有免费午餐定理（No Free Launch Theorem, NFL）：对于基于迭代的最优算法，不存在某种算法对所有问题（有限的搜索空间内）都有效，所以：不存在一种机器学习算法适合于任何领域或任务。

8.3.奥卡姆剃刀原理

    奥卡姆剃刀（Occam's Razor）：如无必要，勿增实体。它的一种形式化是最小描述长度（Minimum Description Length, MDL）原则，即对一个数据集$D$，最好的模型$f \in F$会使得数据集的压缩效果最好，即编码长度最小。最小描述长度可通过贝叶斯学习观点解释，它的后验概率为：

$\underset{f}{max} \log p(f|D) = \underset{f}{max} \log p(D|f) + \log p(f) = \underset{f}{min} - \log p(D|f) - \log p(f)$

$-\log p(f), -\log p(D|f)$可以分别看作模型$f$的不编码长度和在该模型下数据集$D$的编码长度。

8.4.丑小鸭定理

    丑小鸭定理（Ugly Duckling Theorem）：丑小鸭和白天鹅之间的区别和两只白天鹅之间区别一样大。

8.5.归纳偏置

    机器学习中，很多学习算法会对学习的问题做一些假设，这些假设称为归纳偏置（Inductive Bias），归纳偏置在贝叶斯学习中也经常称为先验（Prior）。