线性模型 (Linear Model)：给定由 $d$ 个属性描述的示例 $\mathit{x}$，线性模型试图学得一个通过属性间的线性组合来进行预测的函数，即：$f(\mathit{x})={\mathit{w}}^{\mathrm{T}}\mathit{x}+b$.

1. 线性回归

给定数据集 $D=\{({\mathit{x}}_1,y_1),({\mathit{x}}_2,y_2),\dots ,({\mathit{x}}_m,y_m)\}$，其中 ${\mathit{x}}_i=(x_{i1},x_{i2},\dots ,x_{id}{)}^{\mathrm{T}},y_i\in \mathbb{R}$. 线性回归试图学得一个线性模型以尽可能准确地预测实值输出标记。

1.1. 单变量线性回归

对于 $d=1$ 的单变量情形，我们的目标是：

$$\begin{array}{rl}(w^{\ast },b^{\ast })& =\underset{(w,b)}{\arg min}\sum _{i=1}^m(f(x_i)-y_i{)}^2\\ & =\underset{(w,b)}{\arg min}\sum _{i=1}^m(y_i-w{x}_i-b{)}^2\end{array}$$

将其分别对 $w,b$ 求偏导再置为 $0$，便可得到该问题的解：

$$\begin{array}{rl}& \{\begin{array}{l}{\displaystyle \frac{\partial E_{(w,b)}}{\partial w}=2(w\sum _{i=1}^m{x}_i^2-\sum _{i=1}^m(y_i-b)x_i)}\\ {\displaystyle \frac{\partial E_{(w,b)}}{\partial b}=2(mb-\sum _{i=1}^m(y_i-w{x}_i))}\end{array}\\ \\ \Rightarrow & \{\begin{array}{l}{\displaystyle w=\frac{\sum _{i=1}^m{y}_i(x_i-\overline{x})}{\sum _{i=1}^m{x}_i^2-\frac{1}{m}(\sum _{i=1}^m{x}_i{)}^2}}\\ {\displaystyle b=\frac{1}{m}\sum _{i=1}^m(y_i-w{x}_i)}\end{array}\end{array}$$

上面这个解看着很眼熟，其实就是我们高中就学过的最小二乘法了。

1.2. 多变量线性回归

对于多变量情形，为了式子简便，将 $\mathit{w}$ 和 $b$ 整合到一起得到：

$${\hat{\mathit{w}}}_{(d+1)\times 1}=\left(\begin{array}{c}\mathit{w}\\ b\end{array}\right)$$

对于数据集，最右侧增加一列 $1$：

$${\mathbf{X}}_{m\times (d+1)}=\left(\begin{array}{ccccc}{x}_{11}& x_{12}& \cdots & x_{1d}& 1\\ x_{21}& x_{22}& \cdots & x_{2d}& 1\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ x_{m1}& x_{m2}& \cdots & x_{md}& 1\end{array}\right)=\left(\begin{array}{cc}{\mathit{x}}_1^{\mathrm{T}}& 1\\ {\mathit{x}}_2^{\mathrm{T}}& 1\\ ⋮& ⋮\\ {\mathit{x}}_m^{\mathrm{T}}& 1\end{array}\right)$$

标记也写成向量形式：

$${\mathit{y}}_{m\times 1}=\left(\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_m\end{array}\right)$$

综上，我们要求的线性模型便是：

$$\mathit{y}=\mathbf{X}\hat{\mathit{w}}$$

我们的目标是：

$${\hat{\mathit{w}}}^{\ast }=\underset{\hat{\mathit{w}}}{\arg min}(\mathit{y}-\mathbf{X}\hat{\mathit{w}}{)}^{\mathrm{T}}(\mathit{y}-\mathbf{X}\hat{\mathit{w}})$$

同样，将其对 $\hat{\mathit{w}}$ 求导得到：

$$\begin{array}{rl}\frac{\partial E_{\hat{\mathit{w}}}}{\partial \hat{\mathit{w}}}& =\frac{\partial }{\partial \hat{\mathit{w}}}(\mathit{y}-\mathbf{X}\hat{\mathit{w}}{)}^{\mathrm{T}}(\mathit{y}-\mathbf{X}\hat{\mathit{w}})\\ & =\frac{\partial }{\partial \hat{\mathit{w}}}({\mathit{y}}^{\mathrm{T}}\mathit{y}-{\mathit{y}}^{\mathrm{T}}\mathbf{X}\hat{\mathit{w}}-{\hat{\mathit{w}}}^{\mathrm{T}}{\mathbf{X}}^{\mathrm{T}}\mathit{y}+{\hat{\mathit{w}}}^{\mathrm{T}}{\mathbf{X}}^{\mathrm{T}}\mathbf{X}\hat{\mathit{w}})\\ & =-2{\mathbf{X}}^{\mathrm{T}}\mathit{y}+2{\mathbf{X}}^{\mathrm{T}}\mathbf{X}\hat{\mathit{w}}\\ & =2{\mathbf{X}}^{\mathrm{T}}(\mathbf{X}\hat{\mathit{w}}-\mathit{y})\end{array}$$

在上面推导的第二行到第三行，用到了以下两个结论：

$$\begin{gathered} \frac{\partial {\mathit{x}}^{\mathrm{T}}\mathbf{A}}{\partial \mathit{x}}=\frac{\partial {\mathbf{A}}^{\mathrm{T}}\mathit{x}}{\partial \mathit{x}}=\mathbf{A} \\ \frac{\partial {\mathit{x}}^{\mathrm{T}}\mathbf{A}\mathit{x}}{\partial \mathit{x}}=(\mathbf{A}+{\mathbf{A}}^{\mathrm{T}})\mathit{x} \end{gathered}$$

当 ${\mathbf{X}}^{\mathrm{T}}\mathbf{X}$ 为满秩矩阵或正定矩阵时，将求导得到的式子置为 $0$ 得到：

$${\hat{\mathit{w}}}^{\ast }=({\mathbf{X}}^{\mathrm{T}}\mathbf{X}{)}^{-1}{\mathbf{X}}^{\mathrm{T}}\mathit{y}$$

综上，学到的线性模型就是：

$$f({\hat{\mathit{x}}}_i)={\hat{\mathit{x}}}_i({\mathbf{X}}^{\mathrm{T}}\mathbf{X}{)}^{-1}{\mathbf{X}}^{\mathrm{T}}\mathit{y}$$

当 ${\mathbf{X}}^{\mathrm{T}}\mathbf{X}$ 不是满秩矩阵和正定矩阵时，可以解出多个 $\hat{\mathit{w}}$，此时可以引入正则化项来选择最好的解。

1.3 广义线性回归

当样本点的输入和输出不满足线性函数时，上面的线性回归方法就不能直接使用了。不过这个问题的解决办法我们高中也学过，即构造一个单调可微函数 $g(\cdot )$，令：

$$\begin{array}{rl}& g(y)={\mathit{w}}^{\mathrm{T}}\mathit{x}+b\\ \Rightarrow & y=g^{-1}({\mathit{w}}^{\mathrm{T}}\mathit{x}+b)\end{array}$$

这样就能解决输入空间到输出空间的非线性函数映射了。

例如若样本点满足 $e^x$ 型的映射，我们可以令 $g(x)=\ln x$，原式就变成：

$$\begin{array}{rl}& \ln y={\mathit{w}}^{\mathrm{T}}\mathit{x}+b\\ \Rightarrow & y=\exp ({\mathit{w}}^{\mathrm{T}}\mathit{x}+b)\end{array}$$

经过变换后，再套用之前的方法就能解决这个问题了。

2. 对数几率回归（逻辑斯谛回归）

上面的线性回归预测的是实值输出标记，如果我们求的问题是二分类问题的话，就得做一些调整。我们首先要找到一个函数，将一个实数转为 0/1 值，可以用的是单位阶跃函数：

$$y=\{\begin{array}{ll}0,& z<0\\ 0.5,& z=0\\ 1,& z>0\end{array}$$

不过这个函数不连续，对后面的计算会有很大的困扰，所以可以换成 Sigmoid 函数：

$$y=\frac{1}{1+e^{-z}}$$

将其作为 $g^{-1}(\cdot )$ 代入得到：

$$\begin{array}{rl}& y=\frac{1}{1+e^{-({\mathit{w}}^{\mathrm{T}}\mathit{x}+b)}}\\ \Rightarrow & \ln \frac{y}{1-y}={\mathit{w}}^{\mathrm{T}}\mathit{x}+b\end{array}$$

将 $y$ 看作 $p(y=1\mid \mathit{x})$，将 $1-y$ 看作 $p(y=0\mid \mathit{x})$，将上式改写为：

$$\ln \frac{p(y=1\mid \mathit{x})}{p(y=0\mid \mathit{x})}={\mathit{w}}^{\mathrm{T}}\mathit{x}+b$$

可以得到：

$$\begin{gathered} p(y=1\mid \mathit{x})=\frac{e^{{\mathit{w}}^{\mathrm{T}}\mathit{x}+b}}{1+e^{{\mathit{w}}^{\mathrm{T}}\mathit{x}+b}} \\ p(y=0\mid \mathit{x})=\frac{1}{1+e^{{\mathit{w}}^{\mathrm{T}}\mathit{x}+b}} \end{gathered}$$

这个情况不好用求导解决，所以用极大似然估计来估计 $\mathit{w},b$，为了式子简洁，首先令：

$$\mathit{\beta }=\left(\begin{array}{c}\mathit{w}\\ b\end{array}\right)$$

首先构造似然函数：

$$\begin{array}{rl}& L(\mathit{\beta })=\prod _{i=1}^{m}p(y_i\mid {\mathit{x}}_i)\\ \Rightarrow & \ln L(\mathit{\beta })=\sum _{i=1}^m\ln p(y_i\mid {\mathit{x}}_i)\\ \Rightarrow & \ln L(\mathit{\beta })=\sum _{i=1}^m\ln (y_{i}p(y=1\mid \mathit{x})+(1-y_i)p(y=0\mid \mathit{x}))\\ \Rightarrow & \ln L(\mathit{\beta })=\sum _{i=1}^m(y_i{\mathit{\beta }}^{\mathrm{T}}{\hat{\mathit{x}}}_i-\ln (1+e^{{\mathit{\beta }}^{\mathrm{T}}{\hat{\mathit{x}}}_i}))\end{array}$$

接下来要做的任务便是：

$$\begin{array}{rl}{\mathit{\beta }}^{\ast }& =\underset{\mathit{\beta }}{\arg max}L(\mathit{\beta })\\ & =\underset{\mathit{\beta }}{\arg min}-L(\mathit{\beta })\end{array}$$

可用牛顿法求解：

$${\mathit{\beta }}^{\prime }=\mathit{\beta }-{\left(\frac{{\partial }^{2}L(\mathit{\beta })}{\partial \mathit{\beta }\partial {\mathit{\beta }}^{\mathrm{T}}}\right)}^{-1}\frac{\partial L(\mathit{\beta })}{\partial \mathit{\beta }}$$

3. 线性判别分析

线性判别分析的思想是，给定训练样本集，将样本投影到一个直线上，并希望同类样本尽可能近，异类样本尽可能远。得到该直线后，对于新样本，将其投影后根据其投影点的位置判别属于哪一类。图示如下：

图片来源：《机器学习》周志华

给定数据集 $D=\{({\mathit{x}}_i,y_i){\}}_{i=1}^m,y_i\in \{0,1\}$，令 $i\in \{0,1\}$ 类的集合为 $X_i$，均值向量为 ${\mathit{\mu }}_i$，协方差矩阵为 ${\mathbf{\Sigma }}_i$.

我们要求一条直线 ${\mathit{w}}^{\mathrm{T}}\mathit{x}+b=0$，使其将样本空间分为两部分，这样我们就能够通过样本点在直线的哪一侧来判断类别了。

首先，将样本点投影到直线 ${\mathit{w}}^{\mathrm{T}}\mathit{x}+b=0$ 的法向量 $\mathit{w}$，那么它们的均值为 ${\mathit{w}}^{\mathrm{T}}{\mathit{\mu }}_i$，协方差为 ${\mathit{w}}^{\mathrm{T}}{\mathbf{\Sigma }}_i\mathit{w}$，并且这两个值都是标量。

点 $\mathit{x}$ 投影到向量 $\mathit{w}$ 的投影点的大小为 ${\mathit{w}}^{\mathrm{T}}\mathit{x}$，下面是简单推导：

设 $\mathit{x}$ 投影到向量 $\mathit{w}$ 的投影点为 $\mathit{p}$，由投影的定义，$\mathit{p}$ 一定与 $\mathit{w}$ 共线，则：$\mathit{p}=c\mathit{w}$

设 $\mathit{p}$ 到 $\mathit{x}$ 的连线为 $\mathit{d}$，由投影的定义，$\mathit{d}\cdot \mathit{p}=0$（或 ${\mathit{d}}^{\mathrm{T}}\mathit{p}=0$）

$$\begin{array}{rl}& {\mathit{d}}^{\mathrm{T}}\mathit{p}=0\\ \Rightarrow & (\mathit{x}-\mathit{p}{)}^{\mathrm{T}}\mathit{p}=0\\ \Rightarrow & (\mathit{x}-c\mathit{w}{)}^{\mathrm{T}}c\mathit{w}=0\\ \Rightarrow & {\mathit{x}}^{\mathrm{T}}c\mathit{w}-c^2{\mathit{w}}^{\mathrm{T}}\mathit{w}=0\\ \Rightarrow & c=\frac{{\mathit{x}}^{\mathrm{T}}\mathit{w}}{{\mathit{w}}^{\mathrm{T}}\mathit{w}}=\frac{{\mathit{w}}^{\mathrm{T}}\mathit{x}}{{\mathit{w}}^{\mathrm{T}}\mathit{w}}\end{array}$$

综上，点 $\mathit{x}$ 投影到向量 $\mathit{w}$ 的投影点为：

$$\mathit{p}=c\mathit{w}=\frac{{\mathit{w}}^{\mathrm{T}}\mathit{x}}{{\mathit{w}}^{\mathrm{T}}\mathit{w}}\mathit{w}={\mathit{w}}^{\mathrm{T}}\mathit{x}\frac{\mathit{w}}{\Vert \mathit{w}\Vert }$$

如果我们只关心大小，不关心方向的话（因为方向一定和 $\mathit{w}$ 一样）：

$$p={\mathit{w}}^{\mathrm{T}}\mathit{x}$$

我们的目标是同类样本尽可能近，异类样本尽可能远，对应到均值方差上就是类别间的均值距离 $\Vert {\mathit{w}}^{\mathrm{T}}{\mathit{\mu }}_0-{\mathit{w}}^{\mathrm{T}}{\mathit{\mu }}_1{\Vert }^2$ 尽可能大，类别内方差 ${\mathit{w}}^{\mathrm{T}}{\mathbf{\Sigma }}_0\mathit{w}+{\mathit{w}}^{\mathrm{T}}{\mathbf{\Sigma }}_1\mathit{w}$ 尽可能小。

$$\begin{array}{rl}J& =\frac{\Vert {\mathit{w}}^{\mathrm{T}}{\mathit{\mu }}_0-{\mathit{w}}^{\mathrm{T}}{\mathit{\mu }}_1{\Vert }^2}{{\mathit{w}}^{\mathrm{T}}{\mathbf{\Sigma }}_0\mathit{w}+{\mathit{w}}^{\mathrm{T}}{\mathbf{\Sigma }}_1\mathit{w}}\\ & =\frac{{\mathit{w}}^{\mathrm{T}}({\mathit{\mu }}_0-{\mathit{\mu }}_1)({\mathit{\mu }}_0-{\mathit{\mu }}_1{)}^{\mathrm{T}}\mathit{w}}{{\mathit{w}}^{\mathrm{T}}({\mathbf{\Sigma }}_0+{\mathbf{\Sigma }}_1)\mathit{w}}\end{array}$$

令：

$$\begin{gathered} {\mathbf{S}}_w={\mathbf{\Sigma }}_0+{\mathbf{\Sigma }}_1 \\ {\mathbf{S}}_b=({\mathit{\mu }}_0-{\mathit{\mu }}_1)({\mathit{\mu }}_0-{\mathit{\mu }}_1{)}^{\mathrm{T}} \end{gathered}$$

则上式可以写为：

$$J=\frac{{\mathit{w}}^{\mathrm{T}}{\mathbf{S}}_b\mathit{w}}{{\mathit{w}}^{\mathrm{T}}{\mathbf{S}}_w\mathit{w}}$$

由于 $\mathit{w}$ 为分类边界的法向量，因此我们只关注 $\mathit{w}$ 的方向，而不关注它的长度。因此不妨固定分母 ${\mathit{w}}^{\mathrm{T}}{\mathbf{S}}_w\mathit{w}=1$，那么求解 $J$ 最大等价于求解分子最大，也等价于负分子最小，即：

$$\begin{gathered} \underset{\mathit{w}}{min}-{\mathit{w}}^{\mathrm{T}}{\mathbf{S}}_b\mathit{w} \\ s.t.{\mathit{w}}^{\mathrm{T}}{\mathbf{S}}_w\mathit{w}=1 \end{gathered}$$

用拉格朗日乘子法，构造拉格朗日函数求解：

$$\begin{array}{r}L(\mathit{w},\lambda )={\mathit{w}}^{\mathrm{T}}{\mathbf{S}}_b\mathit{w}-\lambda ({\mathit{w}}^{\mathrm{T}}{\mathbf{S}}_w\mathit{w}-1)\\ \\ \begin{array}{rl}\frac{\partial L(\mathit{w},\lambda )}{\partial \mathit{w}}& =({\mathbf{S}}_b+{\mathbf{S}}_b^{\mathrm{T}})\mathit{w}-\lambda ({\mathbf{S}}_w+{\mathbf{S}}_w^{\mathrm{T}})\mathit{w}\\ & =2({\mathbf{S}}_b-\lambda {\mathbf{S}}_w)\mathit{w}=0\end{array}\\ \\ \begin{array}{rl}& \Rightarrow {\mathbf{S}}_b{\mathit{w}}^{\ast }=\lambda {\mathbf{S}}_w{\mathit{w}}^{\ast }\\ & \Rightarrow {\mathbf{S}}_w^{-1}{\mathbf{S}}_b{\mathit{w}}^{\ast }=\lambda {\mathit{w}}^{\ast }\\ & \Rightarrow {\mathbf{S}}_w^{-1}({\mathit{\mu }}_0-{\mathit{\mu }}_1)({\mathit{\mu }}_0-{\mathit{\mu }}_1{)}^{\mathrm{T}}{\mathit{w}}^{\ast }=\lambda {\mathit{w}}^{\ast }\\ & \Rightarrow {\mathit{w}}^{\ast }={\mathbf{S}}_w^{-1}({\mathit{\mu }}_0-{\mathit{\mu }}_1)\end{array}\end{array}$$

其中倒数第二行 $({\mathit{\mu }}_0-{\mathit{\mu }}_1{)}^{\mathrm{T}}{\mathit{w}}^{\ast }$ 为标量，$\lambda$ 也为标量，由于我们不关心 $\mathit{w}$ 的长度，因此这两个标量我们全部忽略。最后推导成最后一行的结果：${\mathit{w}}^{\ast }={\mathbf{S}}_w^{-1}({\mathit{\mu }}_0-{\mathit{\mu }}_1)$

上面我们计算出了 $\mathit{w}$，下面还需要计算分类边界的 $b$. 我们可以直接用 ${\mathit{w}}^{\mathrm{T}}{\mathit{\mu }}_0$ 和 ${\mathit{w}}^{\mathrm{T}}{\mathit{\mu }}_1$ 的平均值，即:

$$b=\frac{{\mathit{w}}^{\mathrm{T}}{\mathit{\mu }}_0+{\mathit{w}}^{\mathrm{T}}{\mathit{\mu }}_1}{2}$$

由于我们的数据集的两种类别数量可能不相同，为了防止先验概率不等造成的干扰，可以对其做加权平均：

$$b=\frac{m_0{\mathit{w}}^{\mathrm{T}}{\mathit{\mu }}_0+m_1{\mathit{w}}^{\mathrm{T}}{\mathit{\mu }}_1}{m_0+m_1}$$

这样，我们就计算出来了分类边界 ${\mathit{w}}^{\mathrm{T}}\mathit{x}+b=0$，要对新数据进行分类时，直接将其代入 ${\mathit{w}}^{\mathrm{T}}\mathit{x}+b$，如果结果 $>0$，则为分类边界上面的类别，如果结果 $<0$，则为分类边界下面的类别，如果结果 $=0$，则该数据处于分类边界上。