机器学习——3.线性模型_线性判别函数模型

1. 基本形式

    给定 $d$ 维的数据集$\mathcal{X}=(x_1,x_2...x_d)$，其中$x_i$是$\mathcal{X}$在第 i个特征上的取值，线性模型(Linear model) 试图学得一个通过特征的线性组合来进行预测的函数，即：
$$f(x)=w_1{x}_1+w_2{x}_2+...+w_d{x}_d+b$$

可用向量形式示：
$$f(x)=w^{T}x+b$$
其中 $w=(w_1;w_2;...;w_d)$,学得$w,b$后即确定了模型。

1. 线性模型简单可解释性强
2. 可在线性模型基础上加入一些结构变成非线性模型，表达更强

    

2. 线性回归

2.1 线性回归

    给定数据集$D=({\mathcal{X}}_1,y_1),({\mathcal{X}}_2,y_2),...({\mathcal{X}}_m,y_m)$,其中$\mathcal{X}=(x_{i1};x_{i2};...x_{id})$, “线性回归”（linear regression) 试图学得一个线性模型以尽可能准确地预测实值输出的标记。

    将数据输入到模型时，要求输入模型是数值，所以对离散数值通常我们也有如下的做法：

• 离散特征存在“序”关系，直接转换为连续值，例如(“低”，“中”，“高”)转化为(1,2,3)
• 离散特征不存在“序”关系，通过一些编码的方式转换位数值，例如(“西瓜”，“南瓜”，“黄瓜”)使用OneHot编码转化为([1,0,0],[0,1,0],[0,0,1])

    模型将试图学得
$$f(x_i)=w{x}_i+b,f(x_i)\simeq y_i$$

2.2 最小化均方误差

    如何学得对应的$w,b$呢，通常回归任务可以通过最小化均方误差的方式。
$$\begin{gathered} (w^{\ast },b^{\ast })=argmi{n}_{(w,b)}\sum _{i=1}^m(f(x_i)-y_i{)}^2 \\ =argmi{n}_{(w,b)}\sum _{i=1}^m(y_i-w{x}_i-b{)}^2 \end{gathered}$$

2.3 凸函数求最值问题

    上述的最小化均方误差求解 $w,b$ 本质上是对多元函数求最值的问题，即是凸函数求最值点的问题。所以我们以下的步骤是：

1. 证明该均方误差${\sum }_{i=1}^m(y_i-w{x}_i-b{)}^2$ 为一个凸函数
2. 利用凸函数求最值的方法解得参数$w,b$

2.3.1 凸函数

定理：设 $D\subset R^n$ 是非空开凸集，$f:D\subset R^n\to R$,且$f(x)$在$D$上二价连续可微，如果$f(x)$的Hessian矩阵在$D$上是半正定的，则$f(x)$是$D$上的凸函数。

    以上，所以只需证明均方误差${\sum }_{i=1}^m(y_i-w{x}_i-b{)}^2$ 的Hessian矩阵
[ ∂ 2 E ( w , b ) ∂ w 2 ∂ 2 E ( w , b ) ∂ w ∂ b ∂ 2 E ( w , b ) ∂ b ∂ w ∂ 2 E ( w , b ) ∂ b 2 ] = [ 2 ∑ i = 1 m x i 2 2 ∑ i = 1 m x i 2 ∑ i = 1 m x i 2 m ] \left[

$$\begin{matrix} \frac{\partial ^2E_{(w,b)}}{\partial w^2} & \frac{\partial ^2E_{(w,b)}}{\partial w \partial b} \\ \frac{\partial ^2E_{(w,b)}}{\partial b \partial w}& \frac{\partial ^2E_{(w,b)}}{\partial b^2} \end{matrix}$$ \right] = \left[ $$\begin{matrix} 2\sum_{i=1}^{m} x_i^2 & 2\sum_{i=1}^{m} x_i \\ 2\sum_{i=1}^{m} x_i & 2m \end{matrix}$$ \right] [∂w2∂2E(w,b)​​∂b∂w∂2E(w,b)​​​∂w∂b∂2E(w,b)​​∂b2∂2E(w,b)​​​]=[2∑i=1m​xi2​2∑i=1m​xi​​2∑i=1m​xi​2m​] 是一个半正定矩阵，即可得${\sum }_{i=1}^m(y_i-w{x}_i-b{)}^2$ 是一个关于 $w,b$ 的凸函数

半正定矩阵判定定理之一：若是对称矩阵的所有顺序主子式均为非负，则该矩阵为半正定矩阵

可证上述HEssian矩阵所有顺序主子式为非负(证明略)

2.4 求解模型参数

求解$w,b$使${\sum }_{i=1}^m(y_i-w{x}_i-b{)}^2$最小化的过程，称为线性回归模型的最小二乘“参数估计(parameter estimation)”。我们可将$E_{(w,b)}$分别对$w,b$求导
$$\begin{gathered} \frac{\partial E_{(w,b)}}{\partial w}=\frac{\partial }{\partial w}[\sum _{i=1}^m(y_i-w{x}_i-b{)}^2] \\ =\sum _{i=1}^m\frac{\partial }{\partial w}[(y_i-w{x}_i-b{)}^2] \\ =\sum _{i=1}^m[2\ast (y_i-w{x}_i-b)\ast (-x_i)] \\ =\sum _{i=1}^m[2\ast (w{x}_i^2-y_i{x}_i+b{x}_i)] \\ =2\ast (w\sum _{i=1}^m{x}_i^2-\sum _{i=1}^m{y}_i{x}_i+b\sum _{i=1}^m{x}_i) \\ =2(w\sum _{i=1}^m{x}_i^2-\sum _{i=1}^m(y_i-b)x_i) \end{gathered}$$

$$\begin{gathered} \frac{\partial E_{(w,b)}}{\partial b}=\frac{\partial }{\partial b}[\sum _{i=1}^m(y_i-w{x}_i-b{)}^2] \\ =\sum _{i=1}^m\frac{\partial }{\partial b}[(y_i-w{x}_i-b{)}^2] \\ =\sum _{i=1}^m[2\ast (y_i-w{x}_i-b)\ast (-1)] \\ =\sum _{i=1}^m[2\ast (b-y_i+w{x}_i)] \\ =2\ast (\sum _{i=1}^{m}b-\sum _{i=1}^m{y}_i+\sum _{i=1}^{m}w{x}_i) \\ =2(mb-\sum _{i=1}^m(y-w{x}_i)) \end{gathered}$$

令$\frac{\partial E_{(w,b)}}{\partial w}=0$,即：

$$\begin{gathered} 0=w\sum _{i=1}^m{x}_i^2-\sum _{i=1}^m(y_i-b)x_i \\ w\sum _{i=1}^m{x}_i^2=\sum _{i=1}^m{y}_i{x}_i-\sum _{i=1}^{m}b{x}_i \end{gathered}$$

令$\frac{\partial E_{(w,b)}}{\partial b}=0$,可得：
$$b=\frac{1}{m}\sum _{i=1}^m(y_i-w{x}_i)$$
因为$\frac{1}{m}{\sum }_{i=1}^m{y}_i=\overline{y},\frac{1}{m}{\sum }_{i=1}^m{x}_i=\overline{x}$ , 即有 $b=\overline{y}-w\overline{x}$

    代入b代入 $\frac{\partial E_{(w,b)}}{\partial w}=0$中，得：
$$\begin{gathered} w\sum _{i=1}^m{x}_i^2=\sum _{i=1}^m{y}_i{x}_i-\sum _{i=1}^m(\overline{y}-w\overline{x})x_i \\ w\sum _{i=1}^m{x}_i^2=\sum _{i=1}^m{y}_i{x}_i-\overline{y}\sum _{i=1}^m{x}_i+w\overline{x}\sum _{i=1}^m{x}_i \\ w=\frac{{\sum }_{i=1}^m{y}_i{x}_i-\overline{y}{\sum }_{i=1}^m{x}_i}{{\sum }_{i=1}^m{x}_i^2-\overline{x}{\sum }_{i=1}^m{x}_i} \end{gathered}$$
即
$$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}$$
    

2.5 广义线性模型

    当我们输出标记的对数作为线性模型逼近的目标:
$$lny=w^{T}x+b$$
上式即是 “对数线性回归"(log-linear regression)，实际上是让$e^{w^{T}x+b}$逼近y,但 $lny=w^{T}x+b$仍是线性回归。

一般地，考虑单调可微函数$g(.)$,令
$$y=g^{-1}(w^{T}x+b)$$
    这样得到的模型称为 “广义线性模型”(generalized linear model) 。其中函数$g(.)$称为 “联系函数”(link function)
        
    

3. 对数几率回归

    上述讨论了用线性模型进行了回归任务的学习，加若要做分类任务，则可以利用广义线性回归的理论，找到一个联系函数将线性模型和预测目标联系起来。

    假设在二分类任务中，输出标记即 y ∈ { 0 , 1 } \mathcal{y} \in \{0,1\} y∈{0,1},我们则需要利用一个联系函数将$z=w^{T}x+b$与$y$联系起来，即将$z$值转换位0/1值。

    我们找到将一个联系函数,$y=\frac{1}{1+e^{-z}}$,代入$z$则有：
$$\begin{gathered} y=\frac{1}{1+e^{-(w^{T}x+b)}} \\ y+y{e}^{-(w^{T}x+b)}=1 \\ {e}^{-(w^{T}x+b)}=\frac{1-y}{y} \\ -(w^{T}x+b)=ln\frac{1-y}{y} \\ ln\frac{y}{1-y}=w^{T}x+b \end{gathered}$$
    其中$\frac{y}{1-y}$称为几率，则$ln\frac{y}{1-y}$称之为对数几率。上述的模型用线性回归模型的预测结果去逼近真实标记的对数几率，称之为 “对数几率回归”(logistic regression)
    

4. 线性判别分析(Linear Discriminant Analysis，LDA)

4.1 基本思想

    假设给定一个二维的，二类别任务数据集，LDA则设法将样本投影到一条直线上，使得同类的样本的投影点尽可能接近，反之尽可能远离。则新样本分类时，则对其投影到直线再根据区域对其进行分类。

4.2 原理

• 给定数据集 D = ( x i , y i ) i = 1 m , y i ∈ { 0 , 1 } D = {(x_i,y_i)}_{i=1}^m,y_i \in \{0,1\} D=(xi​,yi​)i=1m​,yi​∈{0,1}
• ${\mathcal{X}}_i,{\mu }_i,{\sum }_i$分别表示类别 i ∈ { 0 , 1 } i \in \{0,1\} i∈{0,1}的数据集、均值向量，协方差矩阵
• 则两类样本的中心在直线上的投影分别为$w^T{\mu }_0$和$w^T{\mu }_1$
• 投影后样本的协方差为$w^T{\sum }_{0}w,w^T{\sum }_{1}w$

    为了将同类样本尽可能接近，异类样本尽可能远离。即两类样本的协方差和$w^T{\sum }_{0}w+w^T{\sum }_{1}w$尽量小，两个类中的中心$||w^T{\mu }_0-w^T{\mu }_1||$尽可能远离。
则得到最大化目标：
$$\begin{gathered} J=\frac{||w^T{\mu }_0-w^T{\mu }_1|{|}_2^2}{w^T{\sum }_{0}w+w^T{\sum }_{1}w} \\ =\frac{w^T({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^{T}w}{w^T({\sum }_0+{\sum }_1)w}=\frac{w^T{S}_{b}w}{w^T{S}_{w}w} \end{gathered}$$
其中记$S_b=({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^T,S_w={\sum }_0+{\sum }_1$

5. 多分类学习

 考虑$N$个类别$C_1,C_2,...C_N$,多分类的基本思路是“拆解法”，即将多分类任务拆为若干个二分类的任务求解。

5.1 “一对一”(One vs One,OvO)

    OvO将$N$个类别的两两配对，从而产生$N(N-1)/2$个分类任务。例如，OvO将为区分类别$C_i$和$C_j$训练一个分类器，该分类器将同时提交给所有分类器，于是我们将得到$N(N-1)/2$个分类节气，最终结果可通过投票产生。

5.1 “一对其余”(One vs Rest,OvR)

    OvR则是每次将一类的样例作为正例，所有其他类别的样本作为反例来训练$N$个分类。

5.1 “多对多”(Many vs Many,MvM)

    MvM是每次将若干个类作为正类，若干个类作为反类。

6. 参考资料

1.《机器学习》周志华 著. 机器学习, 北京: 清华大学出版社
2.《统计学习方法》李航 著. 北京: 清华大学出版社
3. 南瓜书
4. datawhale讲解