Book Notes on Pattern Recognition and Machine Learning (PRML)
在分类任务中，输入一个 vector x，我们需要将其划分到 K 个离散类中的某一类。而线性分类模型是指我们划分决策区域的边界是关于输入 vector 的线性方程。
在分类任务中，我们更希望能预测出离散的label，或者是更广泛的后验概率。因此，我们需要在之前的线性模型外嵌套一层非线性方程 \(f(\cdot)\)，保证输出值为落在 0 到 1 之间的概率，即此时
\[y_{pred}(X) = f(X\beta)\]我们在这里考虑不添加非线性方程，直接利用线性模型的输出来进行分类。
首先是最简单的二分类问题。在这个任务下，我们可以根据线性模型输出 y(x) 的正负来对应将输入 x 分为两类。此时的分类边界即为 \(y(x)=0\) 。在模型中，\(\beta\) 确定决策平面的方向，而截距 \(\beta_0\) 确定该平面的位置。此外，我们还可以求出输入vector到决策平面的距离为 \(r = y(x)/\vert\vert\beta\vert\vert\)
然而，在多分类(K)问题中，我们就不能采用和二分类一样的分类标准了。
在确定分类方式之后，我们接下来介绍三种学习分类方程参数的方法
和之前回归任务类似，唯一不同的是 ground-truth 被二进制编码为 target vector，即每个输入数据对应的标签被转换为一个 0-1 数组（只有一项为1）。
但在实际中，这种方法的效果很差。尽管根据线性特征，我们的预测输出 vector 内元素和也为1，但每个元素我们无法保证落在0-1之间。而且，最小二乘误差会让那些 “很正确” 的数据点对模型产生负面影响。此外，最小二乘在多分类任务下的表现更加糟糕
该方法的思路是利用线性模型，将输入的高维vector降为一维。我们可以通过控制模型参数 \(\beta\) 来使得不同类别的数据降维后相差尽可能地大。
我们首先考虑最简单的二分类的应用。假设我们有 \(N_1\) 个数据属于类别 \(C_1\) ；\(N_2\) 个数据属于类别 \(C_2\) 。最简单的衡量两个类别间差异的方式是比较他们的均值。我们分别求出两个类别数据的均值向量，记为
\[\mathbf{m_1} = \frac{1}{N_1}\sum_{n\in C_1}\mathbf{x_n}, \quad \mathbf{m_2} = \frac{1}{N_2}\sum_{n\in C_2}\mathbf{x_n}\]这里我们想要降维后的两类数据相差尽可能大，所以我们的目标是最大化两均值向量降维后的差值，即
\[max (m_2-m_1) = \beta^T(\mathbf{m_2}-\mathbf{m_1})\]此外我们还需要对模型参数归一化（\(\sum_i \beta_i = 1\)），否则模型参数越大，降维差异就越大。但仅仅这样还不够，还是会出现不同类之间部分数据有交叉。我们希望同类数据之间相互靠近，异类数据之间相互远离。上式定义了异类之间的差异，我们还需要衡量同类数据的靠近程度。在各个类内，求方差再相加到一起作为整个数据集的同类相似度，即
\[\sigma_{within}^2=\sum_{n\in C_1}(\beta^T\mathbf{x_n}-m_1)^2+\sum_{n\in C_2}(\beta^T\mathbf{x_n}-m_2)^2\]我们最终的优化目标为
\[maxJ(\beta) = \frac{(m_2-m_1)^2}{\sigma_{within}^2} = \frac{\beta^TS_B\beta}{\beta^TS_W\beta}\]其中，\(S_B\) 为类间协方差矩阵，\(S_W\) 为类内协方差矩阵，分别如下
\[S_B = (\mathbf{m_2}-\mathbf{m_1})(\mathbf{m_2}-\mathbf{m_1})^T\] \[S_W = \sum_{n\in C_1}(\mathbf{x_n}-\mathbf{m_1})(\mathbf{x_n}-\mathbf{m_1})^T+\sum_{n\in C_2}(\mathbf{x_n}-\mathbf{m_2})(\mathbf{x_n}-\mathbf{m_2})^T\]为了求解这个优化问题，我们令分母为值为 1，用 Lagrange 方法，可得
\[\lambda S_W \beta = S_B\beta\]我们并不关心模型的具体数值，我们只想知道对应的方向。在上面的概念中，我们已经知道 \(\beta^T(\mathbf{m_2}-\mathbf{m_1})\) 的结果是一个常数，所以上式等号右边对应的方向就是 \(\mathbf{m_2}-\mathbf{m_1}\) ，最后我们有
\[\beta \propto S_w^{-1}(\mathbf{m_2}-\mathbf{m_1})\]可以证明，在二分类的任务下，LDA是最小二乘的一种特殊形式。我们可以设第一类的标签值为 \(N/N_1\) ，第二类的标签值为 \(-N/N_2\) ，此时最小二乘的解等价于 LDA 的解。这种设置下最小二乘对应的二分类标准为 \((\mathbf{x}-\mathbf{m})\beta >0\) 时划为第一类，否则划为第二类
对于 K 分类的任务，我们则不能再降至一维，而是将其降为 H 维。和二维的情况类似，我们定义降维后的数据类间方差和类内方差，即
\[\sigma_{within} = \sum_{k=1}^K\sum_{n\in C_k} (\mathbf{y_n}-\mathbf{\mu_k})(\mathbf{y_n}-\mathbf{\mu_k})^T\] \[\sigma_{between} = \sum_{k=1}^KN_k (\mathbf{\mu_k}-\mathbf{\mu})(\mathbf{\mu_k}-\mathbf{\mu})^T\]这里的 \(\mu_k\) 表示 K 类别下数据降维后输出值的均值，\(\mu\) 表示所有数据降维后输出值的均值。我们有很多中优化标准，比如二分类中的分子分母，这里我们用
\[J(\beta) = Tr\{\sigma_{within}^{-1}\sigma_{between}\} = Tr\{(\beta S_W\beta^T)^{-1} (\beta S_B\beta^T)\}\]而
\[S_W = \sum_{k=1}^K\sum_{n\in C_k} (\mathbf{x_n}-\mathbf{m_k})(\mathbf{x_n}-\mathbf{m_k})^T\] \[S_B = \sum_{k=1}^KN_k (\mathbf{m_k}-\mathbf{m})(\mathbf{m_k}-\mathbf{m})^T\]最后，我们进行求解。模型的权重值由矩阵 \(S_W^{-1}S_B\) 的前 H 大的特征值确定。
这种算法用于处理二分类问题，很难泛化到多分类的任务中。这种算法是将非线性函数作用与输入vector x，再用线性模型处理。最后正值为一类，负值为另一类。可写成
\[y(x) = \beta^T \phi(x)\]接下来是损失函数的选择。尽管该算法关注的是错误分类的样本，我们不能直接用错误分类样本数量作为损失函数，因为其导数几乎处处为零，无法优化。所以我们最后确定的 perceptron criterion 是
\[L(\beta) = -\sum_{n\in W}\beta^T\phi_ny_n^*\]这里 W 表示被错误分类的样本集合。之后我们就可以用 SGD 方法来迭代优化。从这里也可以看出，这个算法的解释是不断遍历训练集，忽略分类正确的数据，利用分类错误的数据修改模型，直到最后收敛。
从中我们也可以发现问题，即在训练过程中，随着模型的修改。有些初始被正确分类的数据可能会被错误分类，所以该方法不能保证稳定降低损失函数。perceptron convergence theorem 告诉我们，当训练集是线性可分时，我们可以在有限训练次数里得到一个解。（这里理论上不止一个解，我们得到的具体某个解取决于模型参数初值和训练顺序等）而当数据是线性不可分时，该算法永远无法收敛
在下面的内容中，我们从概率分布的角度去分析分类任务。
这里我们采用生成模型的方式，建模基于类别的条件概率 \(P(x\vert C_k)\) ，以及类别分布的先验概率 \(P(C_K)\) 。这样我们就可以通过贝叶斯定理得到后验的分类概率 \(P(C_k\vert x)\) 。以二分类问题为例，类别 \(C_1\) 的后验概率可以写成
\[P(C_1 \vert x ) = \frac{P(x\vert C_1)P(C_1)}{P(x\vert C_1)P(C_1)+P(x\vert C_2)P(C_2)} = \frac{1}{1+exp(-a)} = \sigma(a)\] \[where \quad a = ln\frac{P(x\vert C_1)P(C_1)}{P(x\vert C_2)P(C_2)}\]我们这样写是为了凑出 logistic sigmoid function \(\sigma(a) = 1/(1+exp(a))\)
进而，在 K 分类的问题中，我们按相同的思路可以得到
\[P(C_k \vert x ) = \frac{P(x\vert C_k)P(C_k)}{\sum_j P(x\vert C_j)P(C_j)} = \frac{exp(a_k)}{\sum_jexp(a_j)}\] \[where \quad a_k = ln[P(x\vert C_k)P(C_k)]\]这时的函数形式被称为 softmax。下面的内容我们来考虑选用不同形式条件概率 \(P(x\vert C_k)\) 的效果及求解。将分别从连续型输入变量和离散型输入变量讨论
我们首先假设条件概率 \(P(x\vert C_k)\) 服从高斯分布，同时假设所有类的协方差矩阵均相同，那么我们可以写出它的概率密度函数，即
\[P(x\vert C_k) = \frac{1}{(2\pi)^{D/2}}\frac{1}{|\Sigma|^{1/2}}exp\{-\frac{(x-\mu_k)^T\Sigma^{-1}(x-\mu_k)}{2}\}\]结合上文提到的贝叶斯定理，我们可以得到后验概率
\[P(C_k\vert x) = \sigma(\beta_k^Tx+\beta_{k0})\]其中
\[\beta_k = \Sigma^{-1}\mu_k\] \[\beta_{k0} = -\frac{1}{2}\mu_k^T\Sigma^{-1}\mu_k + \ln P(C_k)\]可以发现，在假设高斯分布后，我们又回到了线性模型。而通式中的先验概率 \(P(C_k)\) 只出现在线性模型的截距项 \(\beta_0\) ，表明先验概率只会改变分类边界的位置（控制其平移），不会影响分类边界的形状。在当前假设下，分类边界为线性。
值得一提的是，如果我们放宽假设，假设不同类的高斯分布均有各自的协方差矩阵，那么此时分类边界变为二次函数.
在之前的分析中，我们都假设条件概率 \(P(x\vert C_k)\) 服从高斯分布。如果我们进一步放宽假设，假设 \(P(x\vert C_k)\) 是指数函数，即具有如下形式
\[P(x\vert \lambda_k) = h(x)g(\lambda_k)exp\{\lambda_k^Tx\}\]此时我们同样可推导出线性方程，这里直接给出结果 \(a_k(x) = \lambda_k^Tx + \ln g(\lambda_k) + \ln P(C_k)\)
最后我们考虑离散类型的输入。为了简便，我们假设输入数据 \(x_i\) 为二分类，零或一。数据集总共包含 N 个数据。此时我们同样可以写出条件概率 \(P(x\vert C_k)\) 如下
\[P(x\vert C_k) =\prod_{i=1}^N\mu_{ki}^{x_i}(1-\mu_{ki})^{1-x_i}\]同样结合贝叶斯定理，我们求出后验概率中 logistic 函数的作用变量
\[a_k(x) = \ln P(C_k) +\sum_{i=1}^N (x_i\ln\mu_{ki}+(1-x_i)\ln (1-\mu_{ki}))\]我们发现和连续型变量一样，最终得到的是关于 X 的线性模型。
在这一节我们介绍如何利用极大似然来确定模型求解过程中需要的参数。在求解时我们需要知道先验概率，高斯分布的均值和方差等信息，这些参数如何取最合适呢？
为了便于说明，我们考虑二分类任务，数据集为 \(\{x_i,y_i^*\}\) where i=1,2,…,N ，数据的标签是二进制的，即 1 表示属于类别 \(C_1\) ，0 表示属于类别 \(C_2\) 。此外，我们给出两个类别的先验分布为 \(P(C_1)=\pi\) ， \(P(C_2) = 1-\pi\)
对于类别 \(C_1\) ，对应的标签值为 1，我们可以写出其联合分布为
\[P(x_n,C_1) =P(C_1)P(x_n\vert C_1) = \pi N(x_n\vert \mu_1,\Sigma)\]类别 \(C_2\) 是相似的，我们直接写出似然方程
\[P(y^*\vert \pi ,\mu_1,\mu_2,\Sigma) = \prod_{n=1}^N [ \pi N(x_n\vert \mu_1,\Sigma)]^{y_n^*} [ (1-\pi) N(x_n\vert \mu_2,\Sigma)]^{1-y_n^*}\]对其求导并令导数为零可以发现，此时 \(\pi\) 就是类别 \(C_1\) 所占全部数据的比例。所以极大似然对应的先验概率就是各个类别下的数据所占整体数据比例。我们解决了先验概率的问题。这个结论同样可以泛化到多分类任务中。
对其求导并令导数为零，可以得到
\[\mu_1 =\frac{1}{N_1}\sum_{i=1}^N y_i^* x_i, \quad \mu_2 =\frac{1}{N_2}\sum_{i=1}^N (1-y_i^*) x_i\]同样可以发现，极大似然对应的各类别高斯分布均值就是该类别内所有数据的均值
可以直接看出，当 \(\Sigma=S\) 时，对应取到极大似然。这些结果可以扩展到 K 分类任务中。
在上一节中，我们讨论的是用生成模型结合先验概率来进行分类。在这一节中我们直接用极大似然去估计后验概率 \(P(C_K\vert x)\) ，这样的好处是许多参数不需要知道，而且可以提升预测性能（尤其是条件概率分布的假设和真实分布相差很大的时候）
其实我们已经在生成模型中见过 logistics 函数了。还是先考虑最基本的二分类任务，我们假设对应标签分别为 0 或 1。由于我们直接对后验概率建模，可以写出
\[P_i = P(C_1\vert x) = \sigma(X\beta) = 1/(1+e^{-X\beta})\]由于是二分类问题，\(P(C_0\vert x) =1-P(C_1\vert x)\)，此时我们可以写出极大似然的目标
\[P(Y\vert \beta) = \prod_{i=1}^n P(C_1\vert x)^{y_i^*} P(C_0\vert x)^{1-y_i^*}\]将极大似然取 log 再取反作为损失函数，我们可以得到交叉熵，即
\[L(\beta) = -\ln P(Y\vert \beta) = -\sum_{i=1}^n\{y_i^*\ln p_i+(1-y_i^*)\ln (1-p_i) \}\]我们将 \(p_i = 1/(1+e^{-X_i\beta})\) 代入上式可得到最后的模型
\[\hat{\beta} = argmin_{\beta} \sum_{i=1}^n[y_i^*X_i\beta - \log (1+e^{X_i\beta})]\]用 SGD 的方式进行迭代求解，我们还需要求误差函数的梯度，我们可以得到如下
\[\nabla L(\beta) = -\sum_{i=1}^n(y_i^*-p_i)X_i\]在多分类的任务中，我们需要 K 个二分类模型 \(\beta_i\)，sigmoid 函数变为 softmax 函数。对于某类别 k 来说，此时后验概率可写为
\[P_k = P(C_k\vert X) = \frac{exp(X\beta_k)}{\sum_j exp(X\beta_j)}\]我们用 \(y_{ik}^*\) 表示第 i 个数据在 k 类别下的真实标签（零或一），\(p_{ik}\)表示第 i 个数据在 k 类别下的预测概率（\(\sum_{k}p_{ik} = 1\)）。那么相应的，极大似然应改为
\[P(Y\vert \mathbf{\beta}) = \prod_{i=1}^n\prod_{k=1}^K p_{ik}^{y_{ik}^*}\]我们同样可以写出误差函数的梯度，对于 j 类别对应的模型 \(\beta_j\) 而言
\[\nabla_{\beta_j} L(\beta) = \nabla_{\beta_j} L(\beta_1,...\beta_K) = -\sum_{i=1}^N (y_{ij}^*-p_{ij})X_i\]在 logistic regression 中，我们采用 sigmoid 函数 \(\sigma(\cdot)\) 作为线性模型的激活函数。而实际上，我们也可以采用某一概率密度函数 \(p(\theta)\)的积分作为激活函数，即此时
\[f(a) = \int_{-\infty}^ap(\theta)d\theta\]这样一种基于 probit activation function 的线性模型被称为 probit regression。在实际中，probit regression 的结果和 logistic regression 的结果很相似。而 probit model 可能会对 outlier 更加敏感