统计学习&监督学习概论
约 3256 个字 11 张图片 预计阅读时间 11 分钟
一、 总体分类
1.1 监督学习 & 无监督学习
- 监督学习：
- 训练样数据集：\(T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}\)
- 输入空间：\(\mathcal{X} \subset \mathbb{R}^n, x_i \in \mathcal{X}\)
- 输出空间：\(\mathcal{Y}, y_i \in \mathcal{Y}\)
- 实例（instance）：\(x_i = (x_i^{(1)}, x_i^{(2)}, \cdots, x_i^{(n)})^T\)
- 特征（feature）：\(x_i^{(2)}\) 表示 \(x_i\) 的第二个特征
- 无监督学习：
- 半监督学习：
- 少量标注数据，大量未标注数据
- 利用未标注数据的信息，辅助标注数据，进行监督学习
- 较低成本
示意图：
1.2 按模型分类
概率模型与非概率模型
监督学习中，概率模型取条件概率分布形式 \(P(y|x)\)，非概率模型取函数形式 \(y = f(x)\)，无监督学习中，概率模型取条件概率分布形式 \(P(z|x)\) 或者 \(P(x|z)\)，非概率模型取函数形式 \(z = g(x)\)。
概率模型与非概率模型的区别不在与输入与输出之间的映射关系，而在于模型的内在结构，概率模型一定可以表示为联合概率分布的形式，其中的变量表示输入，输出，隐变量甚至参数。而针对非概率模型不一定存在这样的联合概率分布。
- 概率模型举例：决策树，朴素贝叶斯，隐马尔可夫模型，条件随机场，概率潜在语义分析，潜在狄利克雷分配，高斯混合模型
- 非概率模型举例：感知机，支持向量机，k近邻，AdaBoost，k均值，潜在语义分析，神经网络
线性模型与非线性模型
若函数 \(y = f(x)\) 或者 \(z = g(x)\) 是线性函数，则称模型为线性模型，否则成为非线性模型。
线性模型举例：感知机，k近邻，k均值，线性支持向量机
非线性模型举例：基于核函数的支持向量机，深度学习
1.3 核方法
二维平面没法用直线分割 \(\rightarrow\) 三维中用平面分割
二、统计机器学习三要素
2.1 统计机器学习三要素
- 方法 = 模型 + 策略 + 算法
2.2 模型：
- 决策函数的集合：\(\mathcal{F} = \{f|Y = f(X)\}\)
- 参数空间：\(\mathcal{F} = \{f|Y = f_\theta(X), \theta \in \mathbb{R}^n\}\)
- 条件概率的集合：\(\mathcal{F} = \{P|P(Y|X)\}\)
- 参数空间：\(\mathcal{F} = \{P|P_\theta(Y|X), \theta \in \mathbb{R}^n\}\)
2.3 策略（怎么学）：损失函数
常用损失函数：
- 0-1损失函数 0-1 loss function \(L(Y, f(X)) = \begin{cases} 1, & Y \neq f(X) \\ 0, & Y = f(X) \end{cases}\)
- 平方损失函数 quadratic loss function：\(L(Y, f(X)) = (Y - f(X))^2\)
- 绝对损失函数 absolute loss function：\(L(Y, f(X)) = |Y - f(X)|\)
- 对数损失函数 logarithmic loss function 或对数似然损失函数 loglikelihood loss function：\(L(Y, P(Y|X)) = -\log P(Y|X)\)
2.4 学习
- 希望 \(E[(Y - f(X))^2]\) 尽可能小
\(= \int_{X \times Y} (Y - f(x))^2 d \rho(x, y)\)
由于\(\rho(x, y)\)是未知的，只能回到数据集进行估计。
我们定义：
经验风险/损失 \(R_{emp}(f) = \frac{1}{N} \sum_{i=1}^{N} L(y_i, f(x_i))\)
目标：\(f^* = \arg\min_{f \in \mathcal{F}} E[(P(X) - y)^2]\) （求不出来）
\(f_N = \arg\min_{f \in \mathcal{F}} R_{emp}(f) = \frac{1}{N} \sum_{i=1}^{N} (y_i - f(x_i))^2\)
模型正确率/误差分析：\(f_N\) 和实际 \(f^*\)
2.5 过拟合/欠拟合
- 过拟合：模型过于复杂，训练集上过于紧密
- 欠拟合：
在统计学习和机器学习中，为了避免或减轻过拟合现象，须要使用额外的技巧（如模型选择、交叉验证、提前停止、正则化、剪枝、贝叶斯信息准则、赤池信息量准则或dropout）
例：
- 假设给定训练数据集 \(T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}\)
模型 \(f_M(x, w) = w_0 + w_1x + w_2x^2 + \cdots + w_Mx^M = \sum_{j=0}^{M} w_jx^j\)
策略 经验风险最小：\(\arg\min L(w)\)
其中：\(L(w) = \frac{1}{2} \sum_{i=1}^{N} (f(x_i, w) - y_i)^2\)
如下图所示，选取的Model Complexity 最好能使两条线都相对低
正则化
∴ 加了正则化项，就相当于加了一个不等式约束，从而可以控制参数个数。
交叉验证
交叉验证：
-
简单交叉验证
把数据随机分成两部分，一部分做训练集，一部分做测试集 -
S折交叉验证（S-fold cross validation）
把数据随机分成S份互不相交大小相同的子集，S-1份做训练，1份做测试 -
留一交叉验证（leave one out cross validation）
S=N，N为数据集的容量，也即N-1个训练，1个做测试
2.6 泛化能力/泛化误差
-
泛化能力：是指由该方法学习得到的模型对未知数据的预测能力。
-
泛化误差：若学到的模型为 \(\hat{f}\)，则这个模型对未知数据的预测的误差即为泛化误差（generalization error），也即模型的期望风险：
\(\(R_{exp}(\hat{f}) = \mathbb{E}_p[L(Y, \hat{f}(X))] = \int_{X \times Y} L(y, f(x)) P(x, y) dxdy\)\)
通常情况下，我们通过计算\(R_{exp}(\hat{f})\)来评价模型学的好不好。实际中，\(R_{exp}(\hat{f})=|E(\hat{f}(x)-y)^2|=\int (\hat{f}(x)-y)^2 \text{d} \rho (x,y)\)依旧无法计算，我们只能估计它的上界。
我们定义\(R(f)\)为经验误差：\(R(f)=E[L(Y,f(X))]\)，其估计\(\hat{R}(f)=\frac{1}{N}\sum_{i=1}^N L(y_i,f(x_i))\)，有泛化误差上界：\(\(R(f)\leq \hat{R}(f)+\epsilon (d,N,\delta)\)\)
其中
其具有以下性质：
1. 它是样本容量\(N\)的函数，当N增加时，上界趋于0.
2. 它是假设空间容量（模型复杂度）的函数，假设空间容量越大，模型就越难学，上界通常也越大。
这两个不等式也可以和性质一一对应。
- \(N\)越大，\(\epsilon \rightarrow 0\)
- \(d\)越大，\(\epsilon\) 越大
利用 二分类问题 进行泛化误差上界证明：
-
一些定义：
-
损失函数是0-1损失
- \(f\) 的期望风险
-
\(f\) 的经验风险
$$
\hat{R}(f) = \frac{1}{N} \sum_{i=1}^{N} L(y_i, f(x_i)) \tag{1.29}
$$ -
经验风险最小化函数是
\(f_N\) 依赖训练数据集的样本容量 \(N\)。
- 人们更关心的是 \(f_N\) 的泛化能力
下面讨论从有限集合 \(\mathcal{F} = \{f_1, f_2, \cdots, f_d\}\) 中任意选出的函数 \(f\) 的泛化误差上界。
- 具体证明：
Hoeffding不等式：
设 \(X_1, X_2, \cdots, X_N\) 是独立随机变量，且 \(X_i \in [a_i, b_i], i = 1, 2, \cdots, N; \bar{X}\) 是 \(X_1, X_2, \cdots, X_N\) 的经验均值，即 \(\bar{X} = \frac{1}{N} \sum_{i=1}^{N} X_i\)，则对任意 \(t > 0\)，以下不等式成立：
令 \(X\) 为损失函数 \(L(Y, f(X))\)
- \(\bar{X} = \frac{1}{N} \sum_{i=1}^{N} L(y_i, f(x_i))\)，经验风险。
- \(E(\bar{X}) = E(X)\)
- \(E(\frac{1}{N} \sum_{i=1}^{N} X_i) = \frac{1}{N} E(\sum_{i=1}^{N} X_i) = \frac{1}{N} \sum_{i=1}^{N} E(X_i) = \frac{1}{N} \cdot n \cdot E(X) = E(X)\)
- 因此 \(E(\bar{X}) = E[L(y_i, f(x_i))] = R(f)\)，期望风险。
代入 (1.35)
损失函数为0-1损失，\(\therefore X \in [0, 1], a_i = 0, b_i = 1\)
又：\(\mathcal{F} = \{f_1, f_2, \cdots, f_d\}\) 是一个有限集合，
令事件 \(A: \exists f \in \mathcal{F}: R(f) - \hat{R}(f) \geq \varepsilon\)
令 \(s = d \exp(-2N\varepsilon^2)\)。
有对于 \(\forall f\)
由于 \(s = d \exp(-2N\varepsilon^2)\)，\(\therefore \varepsilon\) 是 \(s, d, N\) 的函数。
即 \(R(f) \leq \hat{R}(f) + \varepsilon(s, d, N)\)
具体推一下 \(\varepsilon\)：
三、生成模型和判别模型
3.1 生成模型 \(\rightarrow P(X, Y)\)
生成方法根据学习联合概率分布 \(P(X, Y)\)，然后求出条件概率分布 \(P(Y|X)\) 作为预测的模型，即生成模型：
这样的方法之所以称为生成方法，是因为模型表示了给定输入 \(X\) 产生输出 \(Y\) 的生成关系。典型的生成模型有朴素贝叶斯法和隐马尔可夫模型
3.2 判别模型 \(\rightarrow P(Y|X)\)
典型的判别模型包括：\(k\) 近邻法、感知机、决策树、逻辑斯谛回归模型、最大熵模型、支持向量机、提升方法和条件随机场等，将在后面章节讲述。
生成方法的特点：
- 生成方法可以还原出联合概率分布 \(P(X, Y)\)，而判别方法则不能；
- 生成方法的学习收敛速度更快，即当样本容量增加的时候，学到的模型可以更快地收敛于真实模型；
- 当存在隐变量时，仍可以用生成方法学习，此时判别方法就不能用。
判别方法的特点：
- 判别方法直接学习的是条件概率 \(P(Y|X)\) 或决策函数 \(f(X)\)，直接面对预测，往往学习的准确率更高；
- 由于直接学习 \(P(Y|X)\) 或 \(f(X)\)，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。
3.3 例子
假设我们有训练数据 \((X, Y)\)，\(X\) 是属性集合，\(Y\) 是类别标记。这时来了一个新的样本 \(x\)，我们想要预测它的类别 \(y\)。
我们最终的目的是求得最大的条件概率 \(P(y|x)\) 作为新样本的分类。
判别式模型这么做：
根据训练数据得到分类函数和分界面，比如说根据SVM模型得到一个分界面，然后直接计算条件概率 \(P(y|x)\)，我们将最大的 \(P(y|x)\) 作为新样本的分类。判别式模型是对条件概率建模，学习不同类别之间的最优边界，无法反映训练数据本身的特性，能力有限，其只能告诉我们分类的类别。
生成式模型这么做：
一般会对每一个类建立一个模型，有多少个类别，就建立多少个模型。比如说类别标签有（猫，狗，猪），那首先根据猫的特征学习出一个猫的模型，再根据狗的特征学习出狗的模型，之后分别计算新样本 \(x\) 属于三个类别的联合概率 \(P(x, y)\)，然后根据贝叶斯公式：
分别计算 \(P(y|x)\)，选择三类中最大的 \(P(y|x)\) 作为样本的分类。
3.4 两个模型的小结
不管是生成式模型还是判别式模型，它们最终的判断依据都是条件概率 \(P(y|x)\)，但是生成式模型先计算了联合概率 \(P(x, y)\)，再由贝叶斯公式计算得到条件概率。因此，生成式模型可以体现更多数据本身的分布信息，其普适性更广。
四、统计学习应用
4.1 分类问题
- 准确率并非越高越好——由于样本的不均匀性
-
if 99 苹果 + 1 香蕉，回答对苹果实际上不值得奇怪
-
定义：
（记法：第一个字母：预测结果是否正确；第二个字母，预测为正（Positive）/负（Negative））
TP —— 将正类预测为正类数；
FP —— 将负类预测为正类数；
TN —— 将负类预测为负类数；
FN —— 将正类预测为负类数。
精确率：预测结果为正类的样本中，有多少是真正正类：
召回率：实际是正类的例子里有多少被识别出来了：
此外，还有 \(F_1\) 值，是精确率和召回率的调和均值，即
精确率和召回率都高时，\(F_1\) 值也会高。
精确率和召回率是矛盾的。
- 提高阈值：
- 当我们提高分类阈值时，模型会变得更加“苛刻”和“保守”，只有在非常有把握的情况下才会将样本预测为正例。
- 这会导致 FP（假正例）的数量减少，因为很多模棱两可的负例不会再被轻易误判为正例。
- 因此，根据公式，精确率会提高。
- 但与此同时，一些概率分数较低的真正例（TP）可能会因为达不到更高的阈值而被错误地预测为负例，导致 FN（假负例）的数量增加。
- 因此，根据公式，召回率会降低。
- 精确率：有把握才选
- 召回率：宁可错选不放过
4.2 标注问题
输出
\(P(Y^{(1)}, Y^{(2)}, \cdots, Y^{(n)} | X^{(1)}, X^{(2)}, \cdots, X^{(n)})\)
输入
\((X^{(1)}, X^{(2)}, \cdots, X^{(n)})\)
例 6：
举一个信息抽取的例子。从英文文章中抽取基本名词短语（base noun phrase）。为此，要对文章进行标注。英文单词是一个观测，英文句子是一个观测序列。标记表示名词短语的“开始”、“结束”或“其他”（分别以 B, E, O 表示），标记序列表示英文句子中基本名词短语的所在位置。信息抽取时，将标记“开始”到标记“结束”的单词作为名词短语。例如，给出以下的句子序列，即英文句子，标注结果产生相应的标记序列，即给出句子中的基本名词短语。输入：At Microsoft Research, we have an insatiable curiosity and the desire to create new technology that will help define the computing experience.
输出：A/O Microsoft/B Research/E we/O have/O an/O insatiable/B curious-ity/E and/O the/O desire/BE to/O create/O new/B technology/E that/O will/O help/O define/O the/O computing/B experience/E
评估标注模型的指标与评价分类模型的指标一样，常用的有标注准确率、精确率和召回率。其定义与分类模型相同。
标注常用的统计学习方法有隐马尔可夫模型、条件随机场。
4.3 回归问题
回归问题的学习等价于函数拟合：选择一条函数曲线使其很好地拟合已知数据且很好地预测未知数据（参照 1.4.2 节）。
回归问题按照输入变量的个数，分为一元回归和多元回归；按照输入变量和输出变量之间关系的类型即模型的类型，分为线性回归和非线性回归。
回归学习最常用的损失函数是平方损失函数，在此情况下，回归问题可以由著名的最小二乘法（least squares）求解。
五、习题
1.1 说明伯努利模型的极大似然估计以及贝叶斯估计中的统计学习方法三要素。伯努利模型是定义在取值为 0 与 1 的随机变量上的概率分布。假设观测到伯努利模型 n 次独立的数据生成结果，其中 k 次的结果为 1，这时可以用极大似然估计或贝叶斯估计来估计结果为 1 的概率。
复习1：MLE - 极大似然估计
极大似然估计（MLE）：已知样本，求概率模型的参数。
一般步骤：
1. 写出概率密度函数
2. (可选) \(L(\lambda)\) 取对数
3. 求导并解方程
例：总体 \(X \sim P(X)\) , \(x_1 \dots x_n\), \(\lambda\)是\(P(\lambda)\)的极大似然估计，求\(\lambda\).
-
概率密度函数：
$$
P(X=k) = \frac{\lambda^k}{k!} e^{-\lambda}
$$ -
似然函数：
$$
L(\lambda) = \prod_{i=1}^{n} \frac{x_i}{n_i!} e^{-\lambda}
$$ -
对数似然函数：
$$
\ln L(\lambda) = -\ln(x_i!) + (x_1 + \cdots + x_n)\ln \lambda - n\lambda
$$ -
求导并解方程：
$$
\frac{d \ln L(\lambda)}{d \lambda} = \frac{x_1 + x_2 + \cdots + x_n}{\lambda} - n = 0
$$
$$
\lambda = \frac{x_1 + x_2 + \cdots + x_n}{n} = \bar{x}
$$
复习（预习）2：MAP - 贝叶斯估计
由贝叶斯公式，容易推得 \(P(A|B) = \frac{P(B|A)}{P(B)} \cdot P(A)\)
\((P(A|B) \cdot P(B) = P(B|A) \cdot P(A) = P(AB))\)
下面，将参数 \(\theta\) 看作事件 A，数据 D 看作事件 B，有
解题1：极大似然估计
假设 \(X \sim P(x)\)，\(x_1, \cdots, x_n\)，\(\lambda\) 是 \(P(x)\) 极大似然估计，求解：
-
似然函数：
$$
L(x; \theta) = \theta^k (1-\theta)^{n-k}
$$ -
对数似然函数：
$$
\ln L(x; \theta) = k \ln \theta + (n-k) \ln (1-\theta)
$$ -
求导：
$$
\frac{d \ln L(x; \theta)}{d \theta} = \frac{k}{\theta} - \frac{n-k}{1-\theta}
$$ -
解方程：
$$
k(1-\theta) = \theta (n-k) \quad \Rightarrow \quad \theta = \frac{k}{n}
$$
解题2：贝叶斯估计
贝叶斯估计：数据之外依赖于先验概率分布。
设 \(\theta \sim \beta\) 分布 \(\rightarrow f(x; \alpha, \beta) = \frac{x^{\alpha-1} (1-x)^{\beta-1}}{B(\alpha, \beta)}\)
-
似然函数：
$$
L(x; \theta) = P(x_1, x_2, \cdots, x_n | \theta) P(\theta)
$$
$$
= \theta^k (1-\theta)^{n-k} \cdot \theta^{\alpha-1} (1-\theta)^{\beta-1}
$$ -
对数似然函数：
$$
\ln L(x; \theta) = (k+\alpha-1) \ln \theta + (n-k+\beta-1) \ln (1-\theta)
$$ -
解方程：
$$
(k+\alpha-1)(1-\theta) = \theta (n-k+\beta-1)
$$
$$
\theta = \frac{k+\alpha-1}{n+\alpha-1+\beta-1}
$$
1.2 通过经验风险最小化推导极大似然估计。证明模型是条件概率分布，当损失函数是对数损失函数时，经验风险最小化等价于极大似然估计。
先考虑极大似然估计：
- 似然函数：
$$
L = P(y_1|x_1) P(y_2|x_2) \cdots P(y_n|x_n)= \prod_{i=1}^{n} P(y_i|x_i)
$$ -
对数似然函数：
$$
\ln L = \sum_{i=1}^{n} \ln P(y_i|x_i)
$$ -
极大似然估计：改变某个参数，使\(\sum_{i=1}^{n} \ln P(y_i|x_i)\)最大
而 \(\max \frac{1}{N} \sum_{i=1}^N \ln P(y_i|x_i) \quad \Leftrightarrow \quad \min \frac{1}{N} \sum_{i=1}^N \ln P(x_i|y_i)\)
再考虑经验风险最小化：
-
损失函数为对数损失函数，\(-\log P(Y|X)\)
-
经验风险最小化模型：
$$
\min \frac{1}{N} \sum_{i=1}^{N} L(y_i, f(x_i)) \quad \Leftrightarrow \quad \min \frac{1}{N} \sum_{i=1}^{N} (-\log P(y_i|x_i))
$$ -
经验风险最小化的模型和极大似然估计等价。