将输出变量的每个类型编码为指示变量,若取值集合 $\mathcal{G}$ 有 K 个类型,则对应着 K 个指示函数 $Y_k$,$k=1,\dots,K$:当 $G=k$ 时 $Y_k=1$,其他时 $Y_k=0$。这些指示函数可组合成一个向量 $Y=(Y_1,\dots,Y_K)$,训练集大小为 $N$,则所有数据可表达成 $N\times K$ 的指示输出变量矩阵 $\mathbf{Y}$。矩阵中只有 0 或 1,而每行中只能有一个 1。对 $\mathbf{Y}$ 的每列进行线性回归拟合:
$$\hat{\mathbf{Y}} = \mathbf{X}(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{Y} \tag{4.3}$$关于线性回归的细节可回溯第三章。注意到对输出变量矩阵的每一个列向量 $\mathbf{y}_k$,都对应着一组系数的估计,因此会相应得到一个 $(p+1)\times K$ 的系数矩阵 $\hat{\mathbf{B}}=(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{Y}$。模型的矩阵 $\mathbf{X}$ 的列数为 $p+1$,对应着 $p$ 个输入变量和截距项(全部等于 1 的列)。当对一个新的输入变量数据点 $x$ 进行分类时:
- 计算长度为 $K$ 的模型拟合输出 $\hat{f}(x)^T=(1,x^T)\hat{\mathbf{B}}$。
- 最终的分类为拟合值中最大值对应的类型: $$\hat{G}(x) = \underset{k\in\mathcal{G}}{\arg\max} \hat{f}_k(x) \tag{4.4}$$
这个方法的背后逻辑是在用回归来估计条件期望。而随机变量 $Y_k$ 的条件期望 $E(Y_k|X=x)=\operatorname{Pr}(G=k|X=x)$,因此每个 $Y_k$ 的条件期望是一个有意义的估计目标。但这个方法也存在问题:严格的线性假设是否能够足够准确地估计条件期望,或者 $\hat{f}_k(x)$ 是否是后验概率 $\operatorname{Pr}(G=k|X=x)$ 的合理估计?并且更关键的是这个问题本身是否有意义?
容易证明当模型包含截距项时(即矩阵 $\mathbf{X}$ 中包含全为 1 的列),对于任意 $x$ 有 $\sum_{k\in\mathcal{G}}\hat{f}_k(x)=1$。但估计值 $\hat{f}_k(x)$ 理论上可以为负数或大于 1,且通常会出现这种情况。这是由线性回归中的严格假设造成的,尤其是在对超出训练样本的数据进行预测时更容易出现。虽然拟合值可能违背了概率的定义,但这并没有破坏掉这个方法本身的可用性,实际上在很多场景下它仍然可以得到与其他线性分类方法类似的结果。如果在线性模型的假设下加入对输入变量的基函数 $h(X)$ 的扩展,这个方法可得到概率的一致估计量。或者说当训练样本 $N$ 增大,通过加入一些基函数扩展项,可以使扩展后的线性回归逼近条件期望。第五章将讨论该扩展方法。
另一个更方便的视角是将每个类型与一个目标向量 $t_k$ 相对应,即 $K\times K$ 单位矩阵的第 k 列。预测问题要解决的便是对一个观测数据生成合适的目标向量。若用之前讨论中的写法,观测样本 i 的输出变量向量 $y_i$(矩阵 $\mathbf{Y}$ 的第 i 行),在 $g_i=k$ 时的取值为 $y_i=t_k$。线性模型的最小二乘拟合:
$$\min_{\mathbf{B}} \sum_{i=1}^N \| y_i - [(1,x_i^T)\mathbf{B}]^T \|^2 \tag{4.5}$$最小化的准则可看作是拟合向量与目标向量的欧式距离的平方和。对训练样本外的新观测数据,模型对其的分类为与拟合向量 $\hat{f}(x)$ 距离最近的目标向量:
$$\hat{G}(x) = \underset{k}{\arg\min} \|\hat{f}(x) - t_k\|^2 \tag{4.6}$$这与本节开端描述的方法(式 4.4)是等价的:
- 模(norm)平方和的准则形式,完全等价于多输出变量线性回归的准则,只是从不同的角度来。由于平方模本身就是一个平方和的形式,若将其中的元素分离重组后,即可得到各个元素独立的线性模型。需要注意的是,之所以可以将该范式分解,是因为模型假设中不存在输出变量之间的相互作用。
- 选取最近目标向量的分类规则 4.6 与选取拟合向量中最大值的分类规则 4.4 是完全等价的。
但是在类型数量 $K\geq3$,尤其在 $K$ 比较大时,这种利用回归来分类的方法存在一个严重的问题。由于线性假设的直线性质,某些类型可能会被其他类型 屏蔽(masked)。图 4.2 以 $K=3$ 下的一个极端例子演示了这个问题。其中的样本有三个类型,可以完美地被线性判别边界分开,而线性回归的分类模型却完全无法得出中间那部分点的类型1。
在图 4.3 中,所有的样本点被投射到连接三个类型区域的中心点的直线上2(此例子中,在垂直于这条直线的方向上没有可影响分类的信息),图中包含了三个类型的指示函数输出变量 $Y_1$,$Y_2$ 和 $Y_3$ 的拟合值。左图为线性回归的三个拟合值曲线,从中可以看出类型二的拟合值曲线趋于水平,而且取值永远低于类型一或类型三。因此类型二的点总被归类为类型一或类型三。右图采用二次回归取代线性回归。在这个简单的例子中,二次回归的拟合即可解决类型二被屏蔽的问题。然而,假如数据中有四个类型,可以想象它们的拟合值的二次曲线仍可能存在被屏蔽的类型区域,需要三次函数才可避免。一般性的规则是对 $K\geq3$ 个类型,需要 $K-1$ 阶的多项式才可以避免有被屏蔽的区域。同时注意上述中的多项式建立在通过样本类型区域的中心点的直线方向上,在实际问题中,这可能是任意的方向。因此在 $p$ 维的输入空间上,要完全避免区域屏蔽的问题,需要 $K-1$ 阶的多项式的一般项和交叉项,总项数的数量级为 $O(p^{K-1})$。
这里举了个比较极端的例子,但在 $K$ 比较大 $p$ 比较小时,很容易产生这种屏蔽现象。图 4.4 提供了一个现实案例的演示,元音识别问题的训练数据集在二维空间上的降维投射图。其中共用 $K=11$ 个类型和 $p=10$ 个维度。这是一个比较困难的分类问题,在测试集上表现最好的方法的错误率仍为 40%。表 4.1 中列出了不同分类方法的错误率,从中可见线性回归的错误率为 67%,与其很相近的线性判别分析的错误率为 56%。看起来屏蔽问题在这个案例中造成了困难。虽然本章中其他的方法也同样基于输入变量的线性函数,但它们采取的应用方式可以避免屏蔽问题。
分类方法 | 训练集错误率 | 测试集错误率 |
---|---|---|
线性回归 | 0.48 | 0.67 |
线性判别分析 | 0.32 | 0.56 |
二次判定分析 | 0.01 | 0.53 |
对数几率回归 | 0.22 | 0.51 |
表 4.1:各种线性分类方法在元音识别问题的训练集和测试集错误率。有 11 个类型,和 10 个输入变量维度,通过主成分分析后其中的三个主成分占了总体变化的 90%。对比训练集和测试集的错误率,可见线性回归被屏蔽问题干扰,使测试集错误率和训练集错误率都(比线性判别分析)高了 10 个百分比以上。
本节练习
证明:当模型包含截距项时(即矩阵 $\mathbf{X}$ 中包含全为 1 的列),对于任意 $x$ 有 $\sum_{k\in\mathcal{G}}\hat{f}_k(x)=1$。
证明
用 $\mathbf{1}_K$ 代表一个长度为 $K$ 的 1 向量:$\mathbf{1}_K=(1,\dots,1)^T$。那么要证明的关系就可写为:
$$\hat{f}(x)^T \mathbf{1}_K=1$$
将其展开:
$$\begin{align} \hat{f}(x) \cdot \mathbf{1}_K &= (1, x^T)\hat{\mathbf{B}} \cdot \mathbf{1}_K \\ &= (1, x^T)(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{Y} \cdot \mathbf{1}_K \\ &= (1, x^T)(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T \mathbf{1}_N \end{align}$$
最后一步中 $\mathbf{Y}\cdot\mathbf{1}_K$,是因为矩阵 $\mathbf{Y}$ 中限制了每一行中只有一个 1,其余都是 0,所以每一行的和是 1。
这样一来,上式的后半部分就是对一个常数输出变量(1)进行线性回归的最小二乘估计。由于输出变量是常数,$\mathbf{X}$ 中又带了截距项(1),所以最小二乘的估计值是 $\hat{\beta}_0=1$ 和 $\hat{\beta}_k=0,k=1,\dots,p$。这个最小二乘对任意的 $x$ 的预测值也就是 1。
$$\hat{f}(x)^T \mathbf{1}_K=(1,x^T)(1, 0,\dots,0)^T=1$$