Skip to content

Supervised Learning

Terminology

Classification vs. Regression. 前者预测定性输出（factor, categorical, discrete variables），后者预测定量输出.

Ordered Categorical. 例如小、中、大（存在序关系，但是没有度量概念）.

Dummy Variable. 定性变量通常通过数值方式表达，而最常见的编码方式就是哑变量. 一个 \(K\) 层定性变量可以使用 \(K\) 位二值变量来表示.

Linear & Nearest Neighbors

一个经典的线性模型形如 \(\hat{Y}=X^T \hat{\beta}\). 其中我们将常值变量 \(1\) 包含到 \(X\) 中，从而省略了截距. 最小二乘法通过最小化下面的式子来选择协因子 \(\beta\).

\[\mathrm{RSS}(\beta)=\sum_{i=1}^N (y_i-x_i^T\beta)^2=(\boldsymbol{y}-\boldsymbol{X}\beta)^T(\boldsymbol{y}-\boldsymbol{X}\beta).\]

最近邻方法利用训练集 \(\mathcal{T}\) 中那些在输入空间中最接近 \(x\) 的观测来形成 \(\hat{Y}\). 具体地说，用 \(N_k(x)\) 表示样本中离 \(x\) 前 \(k\) 近的 \(x_i\)，则

\[\hat{Y}(x) = \dfrac{1}{k}\sum_{x_i\in N_k(x)}y_i.\]

最小二乘法依赖于“线性决策边界是合适的”这一假设. 它具有低的方差和潜在高的偏差. \(k\) 近邻则没有依赖关于内在数据的任何严格假设，但是，决策边界依赖于一组输入点和特定的位置，因此是扭曲而不稳定的，即高方差和低偏差. 许多强大的方法是上面方法的变种. 例如

  • 核方法. 将权值平滑地减少至 \(0\)，而不是采用 \(k\) 近邻，前 \(k\) 名为 \(1\)，后面都是 \(0\).

  • 在高维空间，修改距离核来强调某些变量. 例如，引入加权欧氏距离或马氏距离.

  • 局部回归采用局部加权最小二乘，而不是局部拟合常数来拟合线性模型.

  • 线性模型拟合原输入的一个基展开，允许拟合任意复杂的模型.

  • 投影寻踪（projection pursuit）和神经网络由非线性变换的线性模型之和组成.

Statistical Decision Theory

Regression

令 \(X\in \mathbb{R}^p\) 表示一个实值随机输入向量，\(Y\in \mathbb{R}\) 表示一个实值随机输出变量. \(\mathrm{Pr}(X, Y)\) 是它们的联合分布. 我们寻求一个能够预测 \(Y\) 的函数 \(f(X)\)，并通过一个损失函数 \(L(Y, f(X))\) 来惩罚预测的误差. 一个经典的损失是 \(L_2:L(Y, f(X))=(Y-f(X))^2\). 我们可以通过期望预测误差来选择 \(f\).

\[\mathrm{EPE}(f)=\mathbb{E}(Y-f(X))^2=\int [y-f(x)]^2 \mathrm{Pr}(\mathrm{d}x,\mathrm{d}y)=\mathbb{E}_X[\mathbb{E}_{Y\mid X}[(Y-f(X))^2]|X]\]

于是只需要逐点最小，即 \(f(x)=\arg\min_c \mathbb{E}_{Y\mid X}[(Y-c)^2|X=x]=\mathbb{E}[Y|X=x].\)（假如使用 \(L_1\) 损失，新的解是条件中位数，但是其偏导不连续，造成了一些麻烦）\(k\) 近邻算法正是这样的一个过程. 它用样本均值近似期望，将一个点取条件放松成一个点的邻域取条件. 可以证明当 \(N,k\to \infty\) 使得 \(k/N\to 0\) 时，\(\hat{f}(x)\to \mathbb{E}[Y|X=x]\).

似乎 \(k\) 近邻算法是一个普遍的 approximator. 然而，我们通常没有足够多的样本，维度也可能很大. 总的来说，最小二乘假设 \(f\) 可以被一个全局线性函数很好地逼近，而 \(k\) 近邻算法假设 \(f\) 能被一个局部常值函数很好地逼近.

Classification

类似地，考虑分类估计器 \(\hat{G}:\mathbb{R}^p\to \mathcal{G}\). 一个损失函数 \(L\) 可以表示为 \(K\times K\) 的矩阵 \(\boldsymbol{L}\)，其对角线上全是 \(0\)，其他位置均非负，\(K=\mathrm{card}(\mathcal{G})\). 从而期望预测误差为

\[\mathrm{EPE}(\hat{G})=\mathbb{E}[L(G, \hat{G}(X))]=\sum_{k=1}^KL(\mathcal{G}_k, \hat{G}(X))\mathrm{Pr}(X,\mathcal{G}_k)=\mathbb{E}_X\left[\sum_{k=1}^K L(\mathcal{G}_k, \hat{G}(X))\mathrm{Pr}(\mathcal{G}_k|X)\right]\]

于是只需要逐点最小. 假如采用 \(0/1\) 误差，即

\[\hat{G}(x)=\arg \min_g \sum_{k=1}^K L(\mathcal{G}_k, g)\mathrm{Pr}(\mathcal{G}_k|X=x)=\arg \min_g(1-\mathrm{Pr}(g|X=x))=\arg \max_g \mathrm{Pr}(g|X=x).\]

直观地，我们使用条件分布 \(\mathrm{Pr}(G|X)\) 来将 \(x\) 分到最有可能的类. 这个解称为贝叶斯分类器，其误差率称为贝叶斯率. \(k\) 近邻算法仍是这样一个过程. 它使用多数投票方式近似条件概率，将一个点取条件放松成一个点的邻域取条件. 同时可以发现，哑变量回归加上最大拟合值分类（即选择值最大的那一个作为预测值），本质上是贝叶斯分类器. 由于线性回归值可能是负数，我们常引入 softmax 来改造成概率分布.

Curse of Dimensionality

直觉上只使用 \(k\) 近邻分类器就可以逼近理论上最优的条件期望. 然而，这个方法和我们的直觉都会在高维时失效，这称为维数灾难. 例如，输入均匀分布在 \(p\) 维超立方体上，对于一个目标点，考虑一个边长为 \(a\) 的超立方体邻域. 观测这个超立方体，相当于观测了总体积的 \(a^p\). 例如 \(p=10\) 时，令 \(a^p=0.01\)，得 \(a\approx 0.631\)，即我们必须覆盖每个输入变量值域的 \(63.1\%\). 像这样的邻域不再是“局部的”. 同时，所有样本点都会靠近样本的边缘. 例如，考虑均匀分布在 \(p\) 维单位球上的数据点，以原点为例，大多数数据点会更靠近样本空间的边界，从而在训练样本的边缘进行预测会更加地困难. 在高维中，所有可用的训练样本将稀疏地散布在输入空间.

Bias-variance Decomposition

对于一个点的均方根误差 MSE 可以写作

\[ \begin{aligned} \mathrm{MSE}(x_0)&=\mathbb{E}_\mathcal{T}(f(x_0)-y_0)^2\\ &=\mathbb{E}_{\mathcal{T}}(\hat{y_0}-\mathbb{E}_{\mathcal{T}}(\hat y_0))^2+[\mathbb{E}_{\mathcal{T}}(\hat{y}_0)-f(x_0)]^2\\ &=\mathrm{Var}_\mathcal{T}(\hat{y}_0)+\mathrm{Bias}^2(\hat{y_0}) \end{aligned}\]

这被称作偏差-方差分解. 其中偏差是由于学习算法中的错误假设导致的错误（模型本身的误差，可能导致欠拟合），方差是对训练集的敏感性（复杂的模型可能对训练集的变化过于敏感，这是因为算法对训练数据中的随机噪声建模，从而导致了过拟合）. 例如，通过降维和特征选择可以通过简化模型来降低方差，通过增大训练集也可以降低方差. 添加特征往往会降低偏差，但代价是引入额外的方差. 于是，模型应该处于一个合适的复杂程度.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 协议之条款下提供，附加条款亦可能应用