监督学习的分类

输入特征空间为欧式空间 $\boldsymbol{X}$，维数为 d，对于二分类问题，输出空间为 $\boldsymbol{Y} (\forall y \in \boldsymbol{Y}, y \in \{-1, 1\})$

$\boldsymbol{x}$ 为输入特征空间的一个随机向量，$y$ 为输出空间中的一个随机变量。$P(\boldsymbol{x}, y)$ 为 $\boldsymbol{x}$ 与 $y$ 的联合分布。

我们不知道分布的具体形式，但是知道这个分布产生的 m 个样本构成训练集 $D = {(\boldsymbol{x}^{(i)}, y^{i})}_{i=1}^{m}$

---

判别模型和生成模型

判别模型

判别模型分为 2 种。

(1) 直接对输入空间到输出空间的映射建模，即学习

$$h: \boldsymbol{X} \rightarrow \boldsymbol{Y}, s.t. y = h(\boldsymbol{x})$$

(2) 对条件概率 $P(y|\boldsymbol{x})$ 进行建模，然后根据贝叶斯风险最小化的准则进行分类:

$$y = \mathop{\arg\max}\limits_{y \in \\{-1, 1\\}}P(y|\boldsymbol{x})$$

举例: 感知机，逻辑回归，支持向量机，神经网络，k近邻，决策树

生成模型

先对 $P(\boldsymbol{x}, y)$ 建模，再根据贝叶斯公式

$$P(y|\boldsymbol{x}) = \frac{P(\boldsymbol{x}|y)P(y)}{P(\boldsymbol{x})}$$

算出 P(y|\boldsymbol{x})，然后根据 $y = \mathop{\arg\max}\limits_{y \in \{-1, 1\}}P(y|\boldsymbol{x})$ 做分类。

“one should solve the [classification] problem directly and never solve a more general problem as an intermediate step[such as modeling P(x|y)].”

                      --《Statistical Learning Theory》作者 Vapnik

按照 Vapnik 的观点，我们只需对 $P(y|\boldsymbol{x})$ 直接进行建模，没必要间接地先对 $P(\boldsymbol{x}, y)$ 建模。

但是对 $P(\boldsymbol{x}, y)$ 进行建模从而达到判别的目的也有它自身的一些优势(参考NIPS2002年论文 《On Discriminative vs. Generative classifiers: A comparison of logistic regression and naive Bayes》)。

举例: 高斯判别分析、朴素贝叶斯、HMM

---

概率模型和非概率模型

非概率模型

直接学习输入空间到输出空间的映射 $h: \boldsymbol{X} \rightarrow \boldsymbol{Y}, s.t. y = h(\boldsymbol{x})$。

学习的过程

• 基本不涉及概率密度的估计，概率密度的积分等操作
• 关键在于最优化问题的求解

为了学习 $h(\boldsymbol{x})$，通常会先根据先验知识选择一个特定的假设空间 $\boldsymbol{H}$ (函数空间)。然后在这个空间中找出泛化误差最小的假设出来。

$$h^{*} = \mathop{\arg\min}\limits_{h \in \boldsymbol{H}} \epsilon(h) = \mathop{\arg\min}\limits_{h \in \boldsymbol{H}} \sum\limits_{\boldsymbol{X}, y}l(h(\boldsymbol{x}), y)P(\boldsymbol{x}, y)$$

• 其中 $l(h(\boldsymbol{x}), y)$ 是损失函数，选择不同的损失函数，所得的假设的泛化误差不一样。
• 事先不知道 $P(\boldsymbol{x}, y)$，即使选择了损失函数，也无法计算出所得假设的泛化误差

选定损失函数后，所得假设都无法计算出泛化误差，那更不可能找到最小泛化误差对应的假设了。

于是我们退而求其次，对于 m 个样本构成训练集 $D = {(\boldsymbol{x}^{(i)}, y^{i})}_{i=1}^{m}$ ，去找哪个使得经验误差最小(ERM)的假设。

$$g = \mathop{\arg\min}\limits_{h \in \boldsymbol{H}} \hat{\epsilon}(h) = \mathop{\arg\min}\limits_{h \in \boldsymbol{H}} \frac{1}{m}\sum\limits_{i=1}\limits^{m}l(h(\boldsymbol{x}^{(i)}), y^{(i)})$$

这种学习的策略叫经验误差最小化。

根据大数定律: 当训练样例无穷多的时候，假设的经验误差会依概率收敛到假设的泛化误差。

要想成功地学习一个问题，必须在学习的过程中注入先验知识(参考 AAAI2016《Label-Free Supervision of Neural Networks with Physics and Domain Knowledge》)。而先验知识除了用于选择假设空间以外，在选定了假设空间之后也是有用的，这体现在对经验误差最小化增加正则化的时候。

$$g = \mathop{\arg\min}\limits_{h \in \boldsymbol{H}} \hat{\epsilon}(h) = \mathop{\arg\min}\limits_{h \in \boldsymbol{H}} \frac{1}{m}\sum\limits_{i=1}\limits^{m}l(h(\boldsymbol{x}^{(i)}), y^{(i)}) + \lambda\Omega(h)$$

正则化项一般都解释为对模型的复杂度进行惩罚，例如先验知识告诉我们模型应当是稀疏的，这时我们会选择L1范数。

也有另一种解释是为了防止对有限样例的过拟合，但这种解释本质还是先验知识认为模型不太复杂。

同时最小化经验误差加上正则化项，这种学习策略为结构风险最小化(SRM)。

非概率模型总结

非概率学习算法 A 根据训练数据集 D，从假设空间中挑出一个假设 g，作为做预测的时候可以用的模型。

学习算法 A 是一个映射，对于每一个给定的数据集 D, 对于选定的学习策略(ERM or SRM)，都有确定的假设 h 与 D 对应

$$A: D \rightarrow h, s.t. h = A(D)$$

举例: 感知机，支持向量机，神经网络，k近邻

概率模型

概率模型认为学习的目的是学出 $P(\boldsymbol{x}, y)$ 或 $P(y|\boldsymbol{x})$，但最后都是根据贝叶斯风险最小化的准则$y = \mathop{\arg\max}\limits_{y \in \{-1, 1\}}P(y|\boldsymbol{x})$ 进行分类。

如果是学习 $P(\boldsymbol{x}, y)$，一般拆成 $P(\boldsymbol{x}|y)$ 和 $P{y}$。无论是对 $P(\boldsymbol{x}|y)$ 和 $P{y}$ 进行估计还是对 $P(y|\boldsymbol{x})$ 进行估计，都会先假设分布的形式。例如逻辑回归假设 $y|\boldsymbol{x}$ 服从伯努利分布。

分布形式固定后，剩下的就是分布参数的估计问题。常用的有极大似然估计(MLE)和极大后验概率估计(MAP)。其中极大后验概率估计涉及到分布参数的先验概率，这是概率模型中注入先验知识的途径。

举例: 逻辑回归、高斯判别分析、朴素贝叶斯

在一定条件下，非概率模型和概率模型有以下对应关系

非概率模型 -> 概率模型
假设空间 $\boldsymbol{H}$ -> 参数分布 $P(y|\boldsymbol{x})$
经验误差最小化 -> 极大似然估计
结构风险最小化 -> 极大后验概率估计
正则化项 -> 分布参数的先验概率

---

参数模型和非参数模型

参数模型

如果我们对所要学习的问题有足够的认识，具备一定的先验知识，此时我们一般会假定要学习的目标函数 $f(\boldsymbol{x})$ 或分布 $P(y|\boldsymbol{x})$ 的具体形式。

然后，通过训练数据集，基于 ERM、SRM、MLE、MAP 等学习策略，估计出目标函数 $f(\boldsymbol{x})$ 或分布 $P(y|\boldsymbol{x})$ 中含有的未知参数。

未知参数估计完毕，训练数据一般来说就失去其作用了，因为这些估计出来的参数就是训练数据的浓缩。通过这种方式建立起来的模型就是参数模型。

参数模型的一个很重要的特点是，如果对于模型的假设正确，那么只需要很少的训练数据就可以从假设空间中学出一个很好的模型。但是如果模型的假设错误，那么无论训练的数据量有多大，学出的模型都会与真实模型出现不可消灭的偏差。

举例: 感知机、逻辑回归、高斯判别分析、朴素贝叶斯、线性支持向量机

对于神经网络，当固定了隐层的数目以及每一层神经元的个数之后也属于参数模型。

但由于隐层数目与每一层神经元个数的不确定性，一般还是认为神经网络是半参数模型。

非参数模型

当我们对所要学习的问题没有什么先验知识。此时我们一般不会对潜在的模型做过多的假设。

在面对预测任务的时候，我们通常会用上所有的训练数据。例如核密度估计(KDE)的表达式中，就带有所有训练数据的信息。通过这种方式建立的模型就是非参数模型。

非参数模型的一个很重要的特点就是：let the data speak for itself. 因此非参数模型的存储开销、计算开销都会比参数模型大的多。

由于不存在模型的错误假定问题，可以证明，当训练数据量趋于无穷大的时候，非参数模型可以逼近任意复杂的真实模型。

非参数模型中一般会含有一个或多个超参数，外加无穷多个普通的参数。

举例: k近邻

---

总结

判别模型

• 直接对输入空间到输出空间的映射 $h(\boldsymbol{x})$ 做预测，或者直接对条件概率分布 $P(y|\boldsymbol{x})$ 做预测
• 感知机，逻辑回归，支持向量机，神经网络，k近邻，决策树
• 模型一般更准确
• 不需要预设条件
• 鲁棒性更高

生成模型

• 先对概率分布 $P(\boldsymbol{x},y)$ 做预测，根据贝叶斯公式得到 $P(y|\boldsymbol{x})$。
• 高斯判别分析、朴素贝叶斯、HMM
• 收敛速度一般更快
• 可以训练包含隐变量的模型
• 需要假设的先验分布
• 可以还原出判别模型，但反过来不行

非概率模型

• 直接对输入空间到输出空间的映射 $h(\boldsymbol{x})$ 做预
• 感知机，支持向量机，神经网络，k近邻

概率模型

• 对条件概率分布 $P(y|\boldsymbol{x})$ 做预测
• 逻辑回归、决策树、高斯判别分析、朴素贝叶斯、HMM

参数模型

• 模型中包含若干参数，训练完成则训练数据无用，根据模型参数预测结果
• 感知机、逻辑回归、高斯判别分析、朴素贝叶斯、线性支持向量机，HMM，固定了隐层数目和每一层神经元个数的NN
• 需要训练数据较少，训练较快
• 需要假设空间与实际映射空间吻合
• 模型容易理解
• 不适合实际映射隐藏的情况## 非参数模型

非参数模型

• 模型由训练数据本身构成
• SVM、KNN、DT
• 需要训练数据较多，训练较慢
• 不需要假定假设空间，如果训练集无限大可以无限逼近真实模型
• 训练集小时容易过拟合
• 预测性能高

---