EdX Columbia ML 8. 线性分类器与感知机

线性分类器

这里我们只讨论二元分类的情况,即\(\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) \] 这样形式的问题学到一个更通用的分类器?一个简单的方法是把分类问题看做是回归问题,分四步

  1. \(y=(y_1, \ldots, y_n)^\mathsf{T}\),其中\(y_i \in \{-1,+1\}\)\(x_i\)的类别标签
  2. \(x_i\)中加入一个全为1的特征,构造矩阵\(X=[x_1, \ldots, x_n]^\mathsf{T}\)
  3. 使用最小二乘法学出权重向量\(w = (X^\mathsf{T}X)^{-1}X^\mathsf{T}y\)
  4. 对新的点\(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\)

这种方法称为梯度下降法,感知机用了随机梯度下降的方法进行学习,步骤为

  1. 初始化权重向量\(w^{(1)} = 0\)
  2. \(t=1,2,\ldots\)
    1. 找到所有错分的样本,即所有\((x_i, y_i) \in \mathcal{D}\)使得\(y_i \not= {\rm sign}(x_i^\mathsf{T}w^{(t)})\)
    2. 如果这样的样本存在,随机选择一个\((x_i, y_i)\)进行更新 \[ w^{(t+1)} = w^{(t)} + \eta y_ix_i \] ​ 否则返回\(w^{(t)}\)(即此时所有样本均已被正确分类)

感知机的缺点有两点

  • 对于线性可分的情况,算法在找到满足条件的\(w\)以后就会停止,不会找到最优分类器
  • 对于线性不可分的情况,算法不会收敛
坚持原创技术分享,您的支持将鼓励我继续创作!