线性分类器
这里我们只讨论二元分类的情况，即\(\mathcal{Y} \in \{-1, +1\}\)或\(\mathcal{Y} \in \{0, 1\}\)。在这种情况下，假设我们使用贝叶斯分类器，而且对某个新数据判定其类别为1，则肯定有 \[ \begin{align*} &p(x|y=1)P(y=1) > p(x|y=0)P(y=0) \\ \Rightarrow & \ln\frac{p(x|y=1)P(y=1)}{p(x|y=0)P(y=0)} > 0 \end{align*} \]
假设对\(y=0\ {\rm or}\ 1\)其期望密度共享同一个协方差矩阵，即\(p(x|y) = N(x|\mu, \Sigma)\)，那么代入前一讲的概率密度函数，有 \[ \ln\frac{p(x|y=1)P(y=1)}{p(x|y=0)P(y=0)} = \ln \frac{\pi_1}{\pi_0} - \frac{1}{2} (\mu_1 + \mu_0)^\mathsf{T}\Sigma^{-1}(\mu_1 - \mu_0) + x^\mathsf{T}\Sigma^{-1}(\mu_1 - \mu_0) \] 其中不带\(x\)的是一个常数项，可以写作\(w_0\)，\(x^\mathsf{T}\)的系数可以写作\(w\)。得到的这个线性式子也称作线性判别分析（LDA）
因此该贝叶斯分类器的决策规律可以写为一个线性函数，即 \[ f(x) = {\rm sign}(x^\mathsf{T}w + w_0) \]
如果我们放宽之前的假设（即两个类别各自是高斯分布，且共享协方差矩阵），可以得到一个更广义的（二元）线性分类器 \[ f(x) = {\rm sign}(x^\mathsf{T}w + w_0) \]
其中\(w \in \mathbb{R}^d, w_0 \in \mathbb{R}\)。这个分类器要求样本\(x\)是（大致）线性可分的。\(\mathbb{R}^d\)的两个子集\(A,B\)被称为是线性可分的，如果满足以下条件 \[ x^\mathsf{T}w + w_0 \begin{cases} >0 & {\rm if\ }x \in A \\ <0 & {\rm if\ }x \in B \end{cases} \] 这里\((w,w_0)\)定义了一个仿射超平面
为了理解仿射超平面的概念，先看一下超平面的概念。\(\mathbb{R}^d\)中的超平面是其\(d-1\)维的线性子空间。作为线性子空间，超平面肯定会包含原点。任意超平面\(H\)可以用向量\(w\)来表示，即 \[ H = \{x \in \mathbb{R}^d | x^\mathsf{T}w = 0\} \]
从几何上讲，在最简单的情况下（二维空间），对于给定的向量\(w\)，其超平面是有所有与其正交的点（从该点到原点能连出一个向量，这个向量与\(w\)正交 ）所组成的一条过原点的直线\(ax\)
对于任一向量\(x\)，可以计算它与\(w\)的夹角。可知三角形的另外一边为\(x-w\)，那么由余弦定理，有 \[ \begin{align*} |\!|x-w|\!|^2 &= |\!|x|\!|^2 + |\!|w|\!|^2 - 2|\!|x|\!||\!|w|\!|\cos \theta \\ (x-w)^\mathsf{T}(x-w) &= |\!|x|\!|^2 + |\!|w|\!|^2 - 2|\!|x|\!||\!|w|\!|\cos \theta \\ |\!|x|\!| - x^\mathsf{T}w - w^\mathsf{T}x + |\!|x|\!|^2 &= |\!|x|\!|^2 + |\!|w|\!|^2 - 2|\!|x|\!||\!|w|\!|\cos \theta \\ 2x^\mathsf{T}w &= 2|\!|x|\!||\!|w|\!|\cos \theta \\ \therefore |\!|x|\!||\cos\theta| &= \frac{|x^\mathsf{T}w|}{|\!|w|\!|} \end{align*} \]
即从\(x\)到\(w\)的距离是\(|x^\mathsf{T}w|\)。而且只有当\(\theta \in (-\frac{\pi}{2}, \frac{\pi}{2})\)时，才有\(\cos \theta > 0\)。因此\(x\)在\(w\)的哪边是由其夹角余弦值决定，即有 \[ {\rm sign}(\cos \theta) = {\rm sign}(x^\mathsf{T}w) \]
将超平面平移标量\(w_0\)，就得到了仿射超平面，决策平面也变成了\(H=x^\mathsf{T}w+w_0 = 0\)。当\(w_0>0\)时，将超平面往逆向\(w\)的方向移动；当\(w_0<0\)时，将超平面往向着\(w\)的方向移动。
与线性回归类似，也可以通过将特征组合成高维特征的方法，将低维的线性不可分样本集变为高维线性可分样本集。另外，如果对两个类别，其期望密度各自对应一个协方差矩阵，即\(p(x|y) = N(x|\mu_y, \Sigma_y)\)，那么与前面不同的是，有 \[ \ln\frac{p(x|y=1)P(y=1)}{p(x|y=0)P(y=0)} = C + x^\mathsf{T}(\Sigma_1^{-1}\mu_1 - \Sigma_0^{-1}\mu_0) + x^\mathsf{T}\left(\frac{\Sigma_0^{-1} - \Sigma_1^{-1}}{2}\right)x \]
这里第三项是一个关于\(x\)的二次项，因此也称作二次判别分析（不过权重是线性的）
\(\{-1, +1\}\)上的最小二乘
如何对诸如 \[ f(x) = {\rm sign}(x^\mathsf{T}w+w_0) \] 这样形式的问题学到一个更通用的分类器？一个简单的方法是把分类问题看做是回归问题，分四步
- 令\(y=(y_1, \ldots, y_n)^\mathsf{T}\)，其中\(y_i \in \{-1,+1\}\)是\(x_i\)的类别标签
- 往\(x_i\)中加入一个全为1的特征，构造矩阵\(X=[x_1, \ldots, x_n]^\mathsf{T}\)
- 使用最小二乘法学出权重向量\(w = (X^\mathsf{T}X)^{-1}X^\mathsf{T}y\)
- 对新的点\(x_0\)，其标签标记为\(y_0 = {\rm sign}(x_0^\mathsf{T}w)\)
当然可以使用\(\ell_p\)回归来代替最小二乘，进行正则化或者特征选择
这种方法最大的问题是容易受到离群点的影响，而且影响会很大
感知机
对线性分类器 \[ y = f(x) = {\rm sign}(x^\mathsf{T}w) \]
感知机算法试图最小化的损失函数为 \[ \mathcal{L} = -\sum_{i=1}^n(y_i \cdot x_i^\mathsf{T}w)1\{y_i \not= {\rm sign}(x_i^\mathsf{T}w)\} \]
因为对\(y \in \{-1, +1\}\)，有 \[ \begin{align*} y_i \cdot x_i^\mathsf{T}w \begin{cases} >0 & \ {\rm if\ }y_i = {\rm sign}(x_i^\mathsf{T}w) \\ <0 & \ {\rm if\ }y_i \not= {\rm sign}(x_i^\mathsf{T}w) \end{cases} \end{align*} \] 通过最小化\(\mathcal{L}\)，我们试着总去预测出正确的标签
但是\(\nabla_w \mathcal{L} = 0\)对\(w\)没有解析解，所以只能迭代求解。不过\(\nabla_w\mathcal{L}\)指出了\(w\)沿着哪个方向可以增大\(\mathcal{L}\)。因此，对足够小的\(\eta\)，如果按照 \[ w' \leftarrow w - \eta \nabla_w \mathcal{L} \] 来更新\(w\)，则有\(\mathcal{L(w')} < \mathcal{L(w)}\)，即我们得到了更好的\(w\)
这种方法称为梯度下降法，感知机用了随机梯度下降的方法进行学习，步骤为
- 初始化权重向量\(w^{(1)} = 0\)
- 对\(t=1,2,\ldots\)
- 找到所有错分的样本，即所有\((x_i, y_i) \in \mathcal{D}\)使得\(y_i \not= {\rm sign}(x_i^\mathsf{T}w^{(t)})\)
- 如果这样的样本存在，随机选择一个\((x_i, y_i)\)进行更新 \[ w^{(t+1)} = w^{(t)} + \eta y_ix_i \] 否则返回\(w^{(t)}\)（即此时所有样本均已被正确分类）
感知机的缺点有两点
- 对于线性可分的情况，算法在找到满足条件的\(w\)以后就会停止，不会找到最优分类器
- 对于线性不可分的情况，算法不会收敛
