基于Python实现并对比线性分类器与非线性分类器【100011718】

# 实现并对比线性分类器与非线性分类器 ## 一、分类器简述 ### 1.1 线性分类器 分类器将原始数据映射到类别分数的函数（Score Function）上，然后通过损失函数（Loss Function）量化预测分数和真实值标签的差异，再将此转换为一个最小化损失函数的优化问题。 我们假设每一个原始训练数据 $\mathbf{x}^{(i)} \in R_{N,D}$ 都有对应标签 $y_i \in \{1...K\}$，一个原始数据是数据集 $R$ 上的一个有 $D \times 1$ 的向量，标签用一个整数表示，$N$ 时数据样本的个数，$D$ 是一个样本的维度，$K$ 是类别的总数。 首先定义关于分数的函数 $f$，该函数将原始数据映射到每个类的置信度分数上。对于线性分类器（Linear Classifier），这个函数可以表示为： $$ f(\mathbf{x}^{(i)}, \mathbf{W}, \mathbf{b}) = \mathbf{W}\mathbf{x}^{(i)} + \mathbf{b} $$ 其中 $\mathbf{W}$ 是一个 $K \times D$ 的权重矩阵（Weights），$\mathbf{b}$ 是一个 $K \times 1$ 的偏移向量（Bias Vector），计算结果 $\mathbf{y}$ 同样是一个 $K \times 1$的向量，$y_j$ 表示 $\mathbf{x}^{(i)}$ 对应类别 $j$ 的分数。 线性分类器的训练过程就是通过训练集出一个 $\mathbf W$ 和 $\mathbf b$，测试过程就是测试集使用 $f$ 来得到一个分类分数，再经过一些处理（例如 Softmax）来选出预测的标签。 在实现时，做一个矩阵乘法后添加一个偏置向量相当于给所有输入向量添加一个常数为1的偏置维数，得到 $\mathbf{x'}$ ，它是一个 $(D + 1) \times 1$ 的向量，并将权矩阵扩展一个偏置列得到新矩阵 $\mathbf{W'}$，其大小为 $K \times (D + 1)$ 。因此，在实现时我们可以通过在所有向量上附加一个值为1的维度，就可以只学习一个矩阵，而不是权重矩阵和偏移向量。  ### 1.2 Softmax函数和交叉熵损失 首先引入独热向量（One-hot Vector）：对一个有 $K$ 中标签的数据集，标签 $y = i$ 可以表示为一个 $K \times 1$ 的向量，其第 $i$ 个位置为 $1$，其余位置为 $0$。 引入 Softmax 函数，它取一个任意分数的向量，将其映射成在0和1之间、总和为1的向量。 $$ softmax_j(\mathbf{z}) = \frac{e^{\mathbf{z}_j}}{\sum_ke^{\mathbf{z}_k}} $$ 得到一种概率上的表示：样本 $\mathbf{x}$ 的标签是 $i$ 的概率为： $$ f_i(\mathbf{x}) = softmax_j(\mathbf{x'W'}) = \frac{e^{\mathbf{x'W'}_j}}{\sum_ke^{\mathbf{x'W'}_k}} $$ 我们使用交叉熵损失（Cross-Entropy Loss）来衡量样本的损失，其有以下形式，对于样本 $i$： $$ L(\mathbf{W'}) = -\frac1n\sum_{i=1}^n\sum_{j=1}^Ky_j^{(i)}\log softmax_j(\mathbf{x}'^{(i)}\mathbf{W'}) $$ 其中 $y_j^{(i)}$ 指第 $i$ 个样本的标签（独热向量）的第 $j$ 个元素。 ### 1.3 随机梯度下降 为了优化 $\mathbf{W'}$，我们使用随机梯度下降（SGD），其原理为： $$ \frac{df(x)}{dx} = \lim_{h\to 0}\frac{f(x+h)-f(x)}{h} $$ 为提高计算速度，每次选取一部分样本进行梯度计算，即在计算 $f(\mathbf{x}_i, \mathbf{W})$ 时每次只选择一部分样本而非全部样本。 梯度的更新公式为： $$ \mathbf{W'} = \mathbf{W'} - l \times \frac{\part L(\mathbf{W'})}{\mathbf{W'}} $$ 其中 $l$ 为学习率，可以理解为每一次进行梯度下降的步长，在实际应用中，一般采用自适应的学习率算法如Ada算法或Adam算法而非使用固定学习率。 ### 1.4 梯度推导 问题整理如下： $$ \mathbf{z}^{(n)} = \mathbf{W'x}'^{(n)}\\ softmax_i^{(n)} = \frac{e^{z_i^{(n)}}}{\sum_{j = 1}^Ke^{z_j^{(n)}}} \\ L = \frac1N\sum_{k=1}^{N}L^{(n)} = -\frac1N\sum_{k=1}^{N}\sum_{i = 1}^K y_i^{(n)} \ln(softmax_i^{(n)}) $$ 需要计算梯度： $$ \frac{\part L(\mathbf{W'})}{\part \mathbf{W'}} $$ 根据链式法则： $$ \frac{\part L(\mathbf{W'})}{\mathbf{W'}} = \frac{\part L}{\part \mathbf{softmax}} \times \frac{\part \mathbf{softmax}}{\part \mathbf{z}} \times \frac{\part\mathbf{z}}{\part\mathbf{W'}} $$ 首先计算$\frac{\part L^{(n)}}{\part softmax_i^{(n)}}$： $$ \frac{\part L^{(n)}}{\part softmax_j^{(n)}} = \frac{\part(\sum_j y_j^{(n)} \ln softmax_j^{(n)})}{\part softmax_j^{(n)}} = -\sum_jy_j^{(n)}\frac1{softmax_j^{(n)}} $$ 其次计算$\frac{\part softmax_j^{(n)}}{\part z_i^{(n)}}$： $$ \frac{\part softmax_j^{(n)}}{\part z_i^{(n)}} = \frac{\part(\frac{e^{z_i^{(n)}}}{\sum_ke^{z_k^{(n)}}})}{\part z_i^{(n)}} = \begin{cases} \frac{\sum_k e^{z_k^{(n)}}e^{z_i^{(n)}} - (e^{z_i^{(n)}})^2}{\sum_k(e^{z_k^{(n)}})^2} = softmax_i^{(n)}(1-softmax_i^{(n)}), & i = j \\ -\frac{e^{z_j^{(n)}}e^{z_i^{(n)}}}{\sum_k(e^{z_k^{(n)}})^2} = -softmax_i^{(n)}softmax_j^{(n)}, & i \ne j \\ \end{cases} $$ 有$\frac{\part L^{(n)}}{\part z_i^{(n)}}$：其中 $\mathbf{y}^{(n)}$ 是独热向量，有 $\sum_i y_i^{(n)} = 1$ $$ \frac{\part L^{(n)}}{\part z_i^{(n)}} = \sum_jy_j\frac1{softmax_j^{(n)}}\frac{\part softmax_j^{(n)}}{\part z_i^{(n)}}\\ = y_i^{(n)}\frac1{softmax_i^{(n)}}softmax_i^{(n)}(1-softmax_i^{(n)}) + \sum_{j\ne i}\frac{y_j^{(n)}}{softmax_j^{(n)}}softmax_i^{(n)}softmax_j^{(n)}\\ = -y_i^{(n)} + y_i^{(n)}softmax_i^{(n)} +\sum_{i \ne j}y_j^{(n)}softmax_i^{(n)} \\ = -y_i^{(n)}+softmax_i^{(n)}\sum_jy_j = softmax_i^{(n)} - y_i^{(n)} $$ 故有：$\frac{\part L^{(n)}}{\part \mathbf{z}^{(n)}} = \mathbf{softmax}^{(n)} - \mathbf{y}^{(n)} \in \mathbb{R}_{(1 \times K)}$，$\frac{\part L}{\part \mathbf{z}} = \mathbf{softmax} - \mathbf{y} \in \mathbb{R}_{(N \times K)}$ 计算$\frac{\part\mathbf{z}}{\part\mathbf{W'}}$: $$ \frac{\part\mathbf{z}}{\part\mathbf{W'}} = \mathbf{X^T} \in \mathbb{R}_{(K \times D)} $$ 最后计算得到： $$ \frac{\part L(\mathbf{W'})}{\mathbf{W'}} = \frac1N\mathbf{X}^T (\mathbf{softmax} - \mathbf{y}) \in \mathbb{R}_{(N \times D)} $$ ### 1.5 基于基函数的非线性分类器 可以使用基函数将线性分类器转化为非线性分类器，非线性化后会增加权重矩阵 $\mathbf{W'}$ 的维度，例如基函数：$[\mathbf{x}] \to [\mathbf{x}， \mathbf{x}^2， \mathbf{x}^3]$，权重的大小会从线性的 $(D + 1) \times K$ 增大到 $(3D + 1) \times K$。 将线性分类器通过基函数转化成非线性分类器后，梯度和损失函数的计算没有变化，因为权重参数仍是线性的。 ### 1.6 过拟合与正则化 使用正则化（Regularization）的目的是避免对模型对训练数据集过拟合而导致在测试集上的效果变差，常用的正则化方法有L1正则化和L2正则化。 * **L2**：$R(\mathbf{W}) = \sum_k\sum_l \mathbf{W'}_{k,l}^2$ * **L1**：$R(\mathbf{W}) = \sum_k\sum_l |\mathbf{W'}_{k,l}|$ 增加正则化的损失函数如下，引入超参数 $\lambda$（正则化强度） $$ L(\mathbf{W'}) = \frac1N\sum_{i = 1}^N L^{(i)}(f(\mathbf{x}^{(i)},\mathbf{W'}), \mathbf{y}^{(i)}) + \lambda R(\mathbf{W'}) $$ 引入正则化后修改梯度的计算： * **L2**：$\frac{\part L(\mathbf{W'})}{\mathbf{W'}} = \frac1N\mathbf{X}^T (\mathbf{softmax} - \mathbf{y}) + 2\lambda \mathbf{W'} \in \mathbb{R}_{(N \times D)}$ * **L1**：$\frac{\part L(\mathbf{W'})}{\mathbf{W'}} = \frac1N\mathbf{X}^T (\mathbf{softmax} - \mathbf{y}) + \lambda \frac{\mathbf{W'}}{|\mathbf{W'}|} \in \mathbb{R}_{(N \times D)}$ ## 二、分类器实现 ### 2.1 线性分类器 代码文件：`Code/Classifiers/softmax_classfier.py`。 * **训练函数** `train` 关键代码 ``` python # 为训练集增加偏置维度 bias_x = np.ones(X.shape[0]).reshape(-1, 1) X = np.concatenate((X, bias_x), axis=1) loss_history = [] train_num, train_dim = X.shape class_num = np.max(y) + 1 if self.W is None: # 初始化时为权重矩阵赋随机值 self.W = np.random.randn(train_dim, class