两类问题的线性分类器及其求解#

TIP

想象二维平面上有两类点（比如红点和蓝点），线性分类器就是用一条直线把它们分开。

在三维空间里，就是用一个平面分开；更高维空间里，用一个超平面分开。

核心假设：线性可分：数据点可以通过一个 线性函数（超平面）$g(\mathbf{x}) = \mathbf{w}^T \mathbf{x}$ 来分割成不同的类别。

定义：对于输入空间 $\mathbb{R}^d$ 中的一个$d$ 维原始特征向量 $\mathbf{x}=(x_1, x_2, \ldots, x_d)^T$，线性分类器通过一个 线性函数 $g(\mathbf{x}) = \mathbf{w}^T \mathbf{x} + b$ 来进行分类，其中 $\mathbf{w}=(w_1, w_2, \ldots, w_d)^T$ 是权重向量，$b$ 是偏置项。

• 如果 $g(\mathbf{x}) > 0$，则 $\mathbf{x}$ 被分类为正类（例如类别+1）。

• 如果 $g(\mathbf{x}) < 0$，则 $\mathbf{x}$ 被分类为负类（例如类别-1）。

• 如果 $g(\mathbf{x}) = 0$，则 $\mathbf{x}$ 就是决策边界。

• 在权空间中，$\mathbf{w}^T \mathbf{x} = 0$ (均经过增广)定义了一个超平面（分类面）

• 权向量 $\mathbf{w}$ 是垂直于分类面的向量（法向量），指向正类的一侧。如下图的两类二维数据点，黑色的权向量 $\mathbf{w}$ 垂直于分类面（红色虚线），指向黑色点所在的正类区域。

TIP

推导：

对于两类标签 $y_i\in\{-1,1|i=1,2\}$ 训练数据:$y_1\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_{n_1}\}$, $y_2\{\mathbf{x}_{n_1+1}, \mathbf{x}_{n_1+2}, \ldots, \mathbf{x}_{n_1+n_2}\}$ 目标：找到一个 $\mathbf{w}$ 和 $b$ 使得：

$$\begin{cases} \mathbf{w}^T \mathbf{x}_i + b > 0, & \text{for } i=1,2,\ldots,n_1 \\ -(\mathbf{w}^T \mathbf{x}_j + b) > 0, & \text{for } j=n_1+1,n_1+2,\ldots,n_1+n_2 \end{cases}$$

这里的负号是为了统一表示，所有样本都满足 $\mathbf{w}^T \mathbf{x} + b > 0$ 的形式。这一步称为规范化。当标签 $y_i\in\{-1,1|i=1,2\}$ 规范化就是 $y_i(\mathbf{w}^T \mathbf{x}_i + b)$

写成矩阵形式，把两类训练数据合到一个矩阵中,并且纳入偏置项1,称为增广矩阵，$\mathbf{X}$ 是增广矩阵(d+1列)，$\mathbf{w}$ 是增广权重向量。

$$\begin{bmatrix} \mathbf{x}_1^T & \cdots & 1 \\ \mathbf{x}_2^T & \cdots & 1 \\ \vdots & \ddots & \vdots \\ \mathbf{x}_{n_1}^T & \cdots & 1 \\ -\mathbf{x}_{n_1+1}^T & \cdots & -1 \\ -\mathbf{x}_{n_1+2}^T & \cdots & -1 \\ \vdots & \vdots \\ -\mathbf{x}_{n_1+n_2}^T & \cdots & -1 \\ \end{bmatrix} \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_d \\ b \end{bmatrix} > \mathbf{0}\iff \begin{bmatrix} x_{11} & x_{12} & \cdots & x_{1d} &1\\ x_{21} & x_{22} & \cdots & x_{2d} & 1\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ x_{n_1 1} & x_{n_1 2} & \cdots & x_{n_1 d} & 1\\ -x_{n_1+1 1} & -x_{n_1+1 2} & \cdots & -x_{n_1+1 d} & -1\\ -x_{n_1+2 1} & -x_{n_1+2 2} & \cdots & -x_{n_1+2 d} & -1\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ -x_{n_1+n_2 1} & -x_{n_1+n_2 2} & \cdots & -x_{n_1+n_2 d} & -1\\ \end{bmatrix} \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_d \\ b \end{bmatrix} > \mathbf{0}\\[1ex] \mathbf{X}\mathbf{w}>0$$

这个解 不唯一，定义一个准则函数 $J(\mathbf{w})$，当 $\mathbf{w}$ 是解向量时，$J(\mathbf{w})$ 为最小；

采用最优化方法求解标量函数 $J(\mathbf{w})$ 的极小值。

最优化方法采用最多的是梯度下降法，设定初始权值向量 $\mathbf{w}^{(1)}$，然后沿梯度的负方向迭代计算。