Linear Classification

笔记作者：BrickLoo

Parametric & Non-parametric

回顾前面的章节，我们的思路是使用判别函数 $g_i(x)=p(\omega_i|x)$ 对类别为 $i$ 的可能性进行评估，并通过对比其数值大小进行决策。鉴于“对比数值大小”是一种二元的操作，我们不妨先从最简单的二分类问题来看——我们最终的判别函数其实相当于 $g(x)=g_1(x)-g_2(x)$，我们只需要判断 $g(x)$ 的正负性即可判断出这个输入 $x$ 属于哪一类。

进一步展开计算，我们使用了 Bayes 公式将 $p(\omega_i|x)$ 进行转换，并且做出了“似然满足标准正态分布”的假设。然而，这一假设通常是不符合实际情况的（例如，在某个特定的类别下，变量的概率密度函数通常都会有多个极值，而不像正态分布只有一个极值），我们也很难对变量的分布做出一个假设，即，难以确定其概率密度函数的参数形式。

既然都要做出可能错误的假设，为何不直接假设 $g(x)$ 的公式形式？因此我们不妨从最简单的形式开始，直接将其设为线性函数 $g(x)=w^\intercal x+w_0$。这时，我们只需要找到一组参数，使得刚好能通过输出数值的正负性来区分类别。

当然，避免假设变量的概率密度函数的方法不止这种思路。为了从这个角度上做出区分，我们把 “无需假设概率密度函数的参数形式”的方法统称为“非参数化方法”。而像前面的章节一样，对“概率密度函数的参数形式做出了假设”的方法被称为“参数化方法”。

名称里的“参数”比较容易让人误解。无论是哪种方法，我们都会涉及到“参数”的学习，然而名称这里讨论的仅仅是我们是否对“概率密度函数”的“参数形式”做出假设，而非“判别函数”或是其他的“参数形式”。

在这个章节中，我们直接尝试假设“判别函数”的“参数形式”已知，即线性函数，并通过有监督学习来求出这些参数；但是与此同时我们并没有假设“变量分布”的“参数形式”。根据定义，这种方法是非参数化方法。

Least-Squares Classification

前面我们已经假设了一种只聚焦于二分类问题的判别函数 $g(x)=g_1(x)-g_2(x)=w^\intercal x+w_0$，接下来我们看看如何找到一组合适的参数。

Augmented Feature Vector

首先对于一组合适的参数，我们希望对于某个样本 $x_i$，判别函数的输出 $g(x_i)$ 等于某个能反映其类别的常数 $c_i$，即 $w^\intercal x_i+w_0=c_i$。为了区别等式两边的常数 $w_0$ 和 $c_i$，我们尝试将要学习的参数合并到一起，即 $$\begin{align*} w&\leftarrow(w_0,w)\newline x&\leftarrow(x_0,x) \end{align*}$$ 其中 $x_0$ 固定取值为 $x_0=1$ 以实现待学习参数的合并，使得最终的判别函数变为 $g(x)=w^\intercal x$。

Sum-of-Squared-Error

要找到合适的参数 $w$，我们优化的目标是最小化所有分类结果 $g(x_i)$ 和其类别对应的常数 $c_i$ 之间的差距，即最小化 $$L(w)=\sum^n_{i=1}|g(x_i)-c_i|$$ 为了方便计算，将绝对值替换成平方也是一样的效果，所以我们将最小化目标变为 $$L(w)=\sum^n_{i=1}\big(g(x_i)-c_i\big)^2$$

不过公式中的 $c_i$ 还不够优雅。事实上，对于二分类问题，我们只需要绝对值相等的两个常数 $+c$ 和 $-c$；同时对于中心对称的判别函数 $g(x)=w^\intercal x$，我们有 $g(-x)=-g(x)$，因此我们可以将类别 $c_i=-c$ 的样本输入值整个取反（注意引入的 $x_0=1$ 也一起变为 $-1$）。这时，误差公式中就可以只剩下一种不带下标的常数 $c$ 了，即 $$\begin{align*}L(w)&=\sum^n_{i=1}\big(g(x_i)-c\big)^2\newline&=\sum^n_{i=1}(w^\intercal x_i-c)^2\end{align*}$$ 这个公式被称为 sum of squared error。我们的目标是使其最小化，以达成分类效果，这种分类方法称为 Least-squares Classification。

接下来我们分析在这个最小化目标下应该如何得到判别函数的参数 $w$。

Approaches

1. Pseudo-inverse Method

线性代数可以理解为批量计算的数学工具。由于输入样本 $x$ 众多，我们可以试着将其转置后叠放在一个矩阵 $X$ 中进行批量计算，即 $$ X=\begin{bmatrix} x_{10} & x_{11} & \dots & x_{1d} \newline x_{20} & x_{21} & \dots & x_{2d} \newline \vdots & \vdots & \ddots & \vdots \newline x_{n0} & x_{n1} & \dots & x_{nd} \newline \end{bmatrix}$$ 这样，最小化的目标就变为了 $$L(w)=\lVert Xw-c\rVert^2$$

显而易见，当参数取值为 $w=X^{-1}c$ 时，我们的优化目标能够取到最小值，所以一种简单粗暴的解决思路就是直接求解这个等式。不过 $X$ 通常是一个行数远超过列数的矩阵，对其求逆是比较麻烦的，所以这里可以用到一个转化技巧： $$\begin{align*} Xw&=c \newline X^\intercal Xw&=X^\intercal c \newline w&=(X^\intercal X)^{-1}X^\intercal c \end{align*}$$ 其中，我们可以给 $c$ 人为指定一个常数进行计算，通常为 $1$。

经过这样一通操作，我们就只需要对行列数相等的矩阵求逆了。虽然看起来式子更加复杂，但是其实计算起来会更加简单。这种处理方法就叫做伪逆法。

这种方法的缺点在于，$X^\intercal X$ 不一定是非奇异矩阵，有可能无法求逆。一种解决方法是对这部分叠加一个很小的单位矩阵，使其变为 $$X^\prime=\lim_{\epsilon\rightarrow0}(X^\intercal X+\epsilon I)^{-1}X^\intercal$$ 并使用最后计算出的结果 $w=X^\prime c$ 来近似实际值。

2. Least-Mean-Squares (LMS) Algorithm

除了伪逆法，我们还可以用 LMS 解决参数选择的问题。相比于伪逆法，LMS 的思路是使用梯度下降的思路来逐步优化，而不再使用包含所有数据的矩阵进行参数计算，因此矩阵计算中的各种潜在问题都可以避免。同时，对于不严格遵守线性可分的数据（线性可分即能够使用线性函数准确地划分开不同类别的数据），LMS 处理起来也更加灵活。不过缺点是使用这种逐步优化的方法得到参数的耗时相对更长。

分析我们希望最小化的误差 $$L(w)=\sum^n_{i=1}(w^\intercal x_i-c)^2$$ 如果对于单个样本，它就是 $$L(w)=(w^\intercal x-c)^2$$ 此时，它对于参数 $w$ 的梯度是 $$\nabla L(w)=2(w^\intercal x-c)x$$ 这个梯度反映了使得目标 $L(x)$ 变大最快的方向，因此我们只需要将 $w$ 沿着反方向进行移动即可。即，对于第 $k$ 次迭代，我们传入样本 $x_k$ 来更新此时的参数 $w_k$，新的参数 $w_{k+1}$ 应该为 $$w_{k+1}=w_k-\eta_k(w^\intercal x_k-c)x_k$$ 式子中的 $\eta_k$ 指的是第 $k$ 次迭代的步长，它理论上会随着迭代次数的增加而越来越小，使得我们能相对较快地接近目标附近并进一步收敛到一个比较精确的值。对于 LMS 方法，参数初始值 $w_1$ 可以随意选择。

事实上，这个 LMS 方法还可以泛化到广义的线性模型，即此时的判别函数为 $$g(x)=\sum^d_{i=1}w_i\phi_i(x)$$ 对于变量 $x$，每一部分 $\phi_i(x)$ 都不必满足线性关系，但是最终我们依旧可以通过求解误差函数对于参数 $w_i$ 的梯度方向 $\nabla L(w_i)=2\big(g(x)-c\big)\phi_i(x)$ 来更新模型的参数。

Multiple Classes Problem

虽然我们前面讨论的都是二分类问题下的线性模型，但如果遇到多类别的分类问题，我们也可以直接“照搬”。照搬二分类线性模型的两种思路是：

• one-versus-one
  • 正如 Bayes 章节中比较判别函数哪个最大，我们总要对它们的取值两两对比；所以我们对每一对两两对比都可以训练出一个二分类线性模型
  • 对于 $n$ 个类别，需要 $n(n-1)/2$ 个线性模型
• one-versus-the-rest
  • 选择一个选项就是否定其他选项，而否定一个选项就是选择其他选项；所以我们也可以从“是否是它”的角度来训练二分类线性模型
  • 对于 $n$ 个类别，需要 $n$ 个线性模型

Geometry of Linear Discriminant Functions

了解线性模型的几何特性有助于我们更好地理解线性模型的，同时有助于我们根据原理进行改进，得到更好的模型，例如后续章节会介绍的支持向量机。因此，的这里介绍一下线性模型的几何特性。

Convexity of Decision Regions

对于线性模型，它满足决策区域非凹的几何特性。这个特性的意义在于，当我们确定了两个点属于相同类别后，这两个点中的所有点都可以直接判定为相同类别，不需要对它们重新判断。

这个特性的证明比较简单。基于判别函数为 $g(x)=w^\intercal x+w_0$ 的前提，我们可知对于两个确定类别的点 $x_a$ 和 $x_b$，它们中间的点满足 $g(x)=\lambda g(x_a)+(1-\lambda)g(x_b)$，其中 $\lambda \in [0,1]$。无论这个判别函数的决策边界在哪，只要 $g(x_a)$ 和 $g(x_b)$ 与决策边界的关系保持一致，$g(x)$ 也能推导出一致的关系。

例如，对于类别 $i$ 和 $j$，当 $g_i(x_a)>g_j(x_a)$ 且 $g_i(x_b)>g_j(x_b)$，中间的点 $x$ 有 $$g_i(x)=\lambda g_i(x_a)+(1-\lambda)g_i(x_b)\gt\lambda g_j(x_a)+(1-\lambda)g_j(x_b)=g_j(x)$$ 换成我们前文用的线性分类器，即用正值和负值作为分类依据也是同理，只需要将上面的 $g_i(x)$ 改为 $g(x)$，决策边界 $g_j(x)$ 改为数值 $0$ 即可。

Distance to Surface

对于线性的判别函数 $g(x)=w^\intercal x+w_0$（这里的向量都不是前面提到的 Augmented Vector，均为非增强的原始向量），它的决策边界是一个超平面。对于任意的变量 $x$，我们可以求解出它到平面的距离 $d_x$。这里提供两种思路：

• 思路一：将变量 $x$ 投影到过原点的超平面垂线上得到 $x_p$。
  • 思路解析：
    • 由于投影操作垂直于这条垂线，这条垂线又垂直于超平面，因此投影操作相当于沿着超平面平移了变量 $x$，过程中距离 $d_x$ 保持不变。但，投影后我们可以用原点 $O$ 到点 $x_p$ 的距离，以及原点 $O$ 到超平面的距离 $d_O$ 来表示 $d_x$。
  • 求解原点 $O$ 到点 $x_p$ 的距离：
    • 投影操作对应向量计算中的点乘，点乘后的结果刚好是向量在投影方向上的长度。但是我们需要先求出超平面垂线的方向向量，即超平面的法向量 $\vec{n}$
    • 对于决策边界上的任意两点 $x_a$ 和 $x_b$，我们都有 $g(x_a)=g(x_b)=0$，即 $g(x_a)-g(x_b)=w^\intercal(x_a-x_b)=0$，也就是说 $w$ 表示的向量垂直于超平面的任意一条直线。根据高中的几何学知识，$w$ 表示的向量就是这个超平面的垂线的方向向量。再消除 $w$ 的长度影响，我们就能得到超平面的法向量 $$\vec{n}=\frac{\vec{w}}{\lVert\vec{w}\rVert}$$
    • 这时我们就可以用点乘来得到原点 $O$ 到点 $x_p$ 的距离 $$\vec{x}\cdot\vec{n}=\frac{\vec{x}\cdot\vec{w}}{\lVert\vec{w}\rVert}$$
    • 值得注意的是，我们通常讨论的距离都是正值，而这里的计算结果却是有可能取到负值的。这是因为这里的计算过程中还携带了方向信息，这个距离的正负性反映的是 $\vec{x_p}$ 的方向（或者等同于考虑 $\vec{x}$ 的方向）与法向量 $\vec{n}$ 方向的异同关系。所以我们将其称为“原点 $O$ 到点 $x_p$ 的距离”，这个先后顺序如果反过来的话是不合适的。
  • 求解原点 $O$ 到超平面的距离 $d_O$：
    • 我们已经知道超平面的法向量为 $\vec{n}=\vec{w}/\lVert\vec{w}\rVert$，所以我们不妨用 $d_O\cdot\vec{n}=d_O\vec{w}/\lVert\vec{w}\rVert$ 来表示原点 $O$ 到其超平面上的投影点的向量；又因为超平面上的点满足 $g(x)=0$，因此我们将这个向量代入判别函数 $g(x)$ 可以得到 $$\vec{w}\cdot\frac{d_O\vec{w}}{\lVert\vec{w}\rVert}+w_0=d_O\lVert\vec{w}\rVert+w_0=0$$
    • 这时再简单移动一下就可以得到距离 $$d_O=-\frac{w_0}{\lVert\vec{w}\rVert}$$
    • 与前面同理，这个距离的正负性反映的是原点 $O$ 到超平面的方向与法向量 $\vec{n}$ 方向的异同关系。
  • 求解 $d_x$：
    • 根据前面的思路解析，这时就可以通过对前面两项进行相减来表示 $d_x$ 了。既然它们的正负性统一都是以法向量 $\vec{n}$ 方向作为参照，那么他们直接按照向量的运算法则来直接进行相减运算其实是没有问题的，即 $$d_x=\vec{x}\cdot\vec{n}-d_O=\frac{\vec{x}\cdot\vec{w}+w_0}{\lVert\vec{w}\rVert}=\frac{w^\intercal x+w_0}{\lVert\vec{w}\rVert}$$
    • 非常巧的是，分子刚好是 $g(x)$ 的表达式，因此我们可以得到更加简洁的式子 $$d_x=\frac{g(x)}{\lVert\vec{w}\rVert}$$
    • 根据向量的运算法则，这时的正负性反映的则是超平面到点 $x$ 的方向与法向量 $\vec{n}$ 方向的异同关系。如果不需要这个方向信息的话直接取绝对值 $\lvert d_x \rvert$ 即可。
• 思路二：将变量 $x$ 投影到超平面上得到 $x_p$。
  • 思路解析：
    • 利用垂直关系，我们可以使用 $d_x\vec{n}$ 来表示从 $x_p$ 到 $x$ 的向量（因为法向量 $\vec{n}$ 从超平面出发，这里我们也保持一致，从超平面上的点 $x_p$ 出发），其中 $\vec{n}$ 的表达式已经在另一个思路中探讨过了，因此这里不再赘述；而根据向量计算的三角形法则我们同时也可以用原点 $O$ 到 $x$ 的向量以及原点 $O$ 到 $x_p$ 的向量来表示这个向量。结合点 $x_p$ 在超平面上具有 $g(x_p)=0$ 的性质，我们可以列等式来求出其长度 $d_x$。
  • 求解等式：
    • 对于等式 $\vec{x}-\vec{x_p}=d_x\vec{n}=d_x\vec{w}/\lVert\vec{w}\rVert$，我们可以将 $x_p$ 放到一边，方便代入 $g(x_p)=0$ 这条等式，即 $$\vec{x_p}=\vec{x}-\frac{d_x\vec{w}}{\lVert\vec{w}\rVert}$$
    • 然后将上式代入 $g(x_p)=0$ 这条等式，整理得到 $$w^\intercal x-\frac{w^\intercal d_x w}{\lVert\vec{w}\rVert}+w_0=w^\intercal x+w_0-d_x\lVert\vec{w}\rVert=0$$
    • 发现 $w^\intercal x+w_0$ 正是 $g(x)$ 的展开式，因此合并后再简单移一下项就能得到 $$d_x=\frac{g(x)}{\lVert\vec{w}\rVert}$$
    • 同样的，这个值的正负性反映的是点 $x_p$ 到点 $x$ 的方向与法向量 $\vec{n}$ 方向的异同关系，与另一种思路是一致的。可以回顾刚开始含有法向量 $\vec{n}$ 的等式，原因并不难理解。