《机器学习》学习笔记——Chapter3(3.1-3.3)

这次学习日志，主要是为了记录《机器学习》这本书的学习过程，也是一次入门的过程，同时辅助参与一次自然语言文本处理挑战赛。在学习过程中，其他阅读文献主要是李航老师的《统计学习方法》和”Machine Learning In Action”，同时参考了****上多位博主的博客，我在本文中的多处知识点引用了他们的博客内容，日后针对这些知识点我也会加强学习给出自己的理解，在这里也要感谢一同进行本书学习的交流群内的诸位同学，在公式的推导中也借鉴了各位的聪明才智。这大概算是我的第一篇和机器学习有关的博客了，相信自己能够将这个学习持续下去，博客也能继续写下去。在写作的过程中也存在很多不足，首先就是原创性，整篇文章的行文是按照周老师的书本进行的，许多语句也是直接照搬，也是因为我现在的能力远远不足，未能想到更好的概括性语句，又不能担起误导各位读者的责任。我只是在一些公式的推导中做了一些微小的工作，使书中没有呈现的推导过程详尽一点，我相信也存在一些和我一样的同学在初次阅读时对书中的推导感觉迷茫，我尽量使文章以概括性总结，详细公式推导以及入门的代码实战为主，还请各位读者在阅读过程中指出错误和不足，欢迎讨论，共同学习，共同进步。

1 线性模型

基本形式

1、输入数据 $\vec{x} = (x_{1}; x_{2}; \dots; x_{d})$ ，有 $d$ 个属性；
2、通过属性的线性组合，线性模型学得一个可以预测的函数

f (\vec{x}) = ω_{1} x_{1} + ω_{2} x_{2} + \dots + ω_{d} x_{d} + d

向量形式

f (\vec{x}) = {\vec{ω}}^{T} \vec{x} + b

3、模型确定的过程在于

\vec{ω}

和

b

的学得。

基本思想

1、简单的线性模型通过引入层级结构或高维映射可以得到复杂且功能强大的非线性模型；
2、因为 $\vec{ω}$ 的各分量是对应属性的系数，直观表达了各属性在预测中的重要程度，所以模型具有很好的可解释性。
接下来的篇幅，将从简单的单变量线性回归开始，进一步介绍多变量线性回归，推广到更一般的广义线性模型——对数几率回归，通过广义线性模型将线性模型应用到分类任务中，由此引出二分类和多分类学习任务，在二分类问题中，学习了一种经典的线性学习方法——LDA线性判别分析，最后是介绍了类别不平衡问题。

2 线性回归

2.1 单变量线性回归

理论概述

1、训练数据集只有一个输入属性

D = {(x_{i}, y_{i})}_{i = 1}^{m}, x_{i} \in R

2、目标学得的预测函数

f (x_{i}) = ω x_{i} + b

3、通过训练数据集求得

ω

和

b

的最佳值，使得

f (x_{i}) \approx y_{i}

公式推导

以预测函数与训练数据的实际输出之间的差值作为衡量标准，此处使用均方误差作为回归任务的性能度量，使预测值与实际输出值之间误差尽可能的小也就是均方误差尽可能的小，这种方法就是最小二乘法。

在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧氏距离之和最小。

所以代价函数就是

\begin{matrix} (1) & J （ ω, b) = \sum_{i = 1}^{m} (f (x_{i}) - y_{i})^{2} \end{matrix}

上(1)式代入

f (x_{i})

得

\begin{matrix} (2) & J （ ω, b) = \sum_{i = 1}^{m} (y_{i} - ω x_{i} - b)^{2} \end{matrix}

求解 $ω$ 和 $b$ 使 $J (ω, b)$ 最小化的过程，称为线性回归模型的最小二乘“参数估计”。

求解使得(2)式最小的参数，可将(2)式分别对两个参数求偏导数，这里涉及到凸函数和多元函数求偏导数的概念

\begin{aligned} (3) & \frac{\partial J_{(ω, b)}}{\partial ω} & = \frac{\partial \sum_{i = 1}^{m} (y_{i} - ω x_{i} - b)^{2}}{\partial ω}, \\ (4) & = 2 \cdot \sum_{i = 1}^{m} (y_{i} - ω x_{i} - b) (- x_{i}) \\ (5) & = 2 \cdot \sum_{i = 1}^{m} (ω x_{i}^{2} - (y_{i} - b) x_{i}) \\ (6) & = 2 (ω \sum_{i = 1}^{m} x_{i}^{2} - \sum_{i = 1}^{m} (y_{i} - b) x_{i}), \end{aligned}

\begin{aligned} (7) & \frac{\partial J_{(ω, b)}}{\partial b} & = \frac{\partial \sum_{i = 1}^{m} (y_{i} - ω x_{i} - b)^{2}}{\partial ω} \\ (8) & = 2 \cdot \sum_{i = 1}^{m} (y_{i} - ω x_{i} - b) (- 1) \\ (9) & = 2 \cdot \sum_{i = 1}^{m} (b - (y_{i} - ω x_{i})) \\ (10) & = 2 (m b - \sum_{i = 1}^{m} (y_{i} - ω x_{i})), \end{aligned}

在从(3)

\to

(4)和(7)

\to

(8)的推导过程中用到了复合函数求偏导，这属于大学高等数学的范围，之后就是简单的合并。
然后令(6),(10)分别为零可以求得参数最优解的闭式解

\begin{matrix} (11) & ω \sum_{i = 1}^{m} x_{i}^{2} - \sum_{i = 1}^{m} (y_{i} - b) x_{i} = 0, \end{matrix}

\begin{matrix} (12) & m b - \sum_{i = 1}^{m} (y_{i} - ω x_{i}) = 0, \end{matrix}

由(12)可得

\begin{matrix} (13) & b = \frac{1}{m} \sum_{i = 1}^{m} (y_{i} - ω x_{i}), \end{matrix}

将(13)代入(11)得

\begin{matrix} (14) & ω \sum_{i = 1}^{m} x_{i}^{2} - \sum_{i = 1}^{m} (y_{i} - \frac{1}{m} \sum_{i = 1}^{m} (y_{i} - ω x_{i})) x_{i} = 0, \end{matrix}

\begin{matrix} (15) & ω \sum_{i = 1}^{m} x_{i}^{2} = \sum_{i = 1}^{m} (x_{i} y_{i} - \frac{1}{m} x_{i} \sum_{i = 1}^{m} y_{i} + ω \cdot \frac{1}{m} x_{i} \sum_{i = 1}^{m} x_{i}), \end{matrix}

移项

\begin{aligned} (16) & ω (\sum_{i = 1}^{m} x_{i}^{2} - \frac{1}{m} (\sum_{i = 1}^{m} x_{i})^{2}) & = \sum_{i = 1}^{m} (x_{i} y_{i} - \frac{1}{m} x_{i} \sum_{i = 1}^{m} y_{i}), \\ (17) & = \sum_{i = 1}^{m} x_{i} y_{i} - \sum_{i = 1}^{m} \bar{x} y_{i}, \\ (18) & = \sum_{i = 1}^{m} y_{i} (x_{i} - \bar{x}), \end{aligned}

可得

\begin{matrix} (19) & ω = \frac{\sum_{i = 1}^{m} y_{i} (x_{i} - \bar{x})}{\sum_{i = 1}^{m} x_{i}^{2} - \frac{1}{m} (\sum_{i = 1}^{m} x_{i})^{2}}, \end{matrix}

2.2 多变量线性回归

理论概述

1、训练数据集D有d个输入属性，一共有m个样本数据，D可以表示为矩阵

X = (\begin{matrix} x_{11} & x_{12} & \dots & x_{1 d} & 1 \\ x_{21} & x_{22} & \dots & x_{2 d} & 1 \\ \dots \\ x_{m 1} & x_{m 2} & \dots & x_{m d} & 1 \end{matrix})

每行对应一个样本，该行前d个元素对应于样本的d个元素值，最后一个元素恒为1。
所以属性可以用向量表示

{\vec{x}}_{i} = (x_{i 1}; x_{i 2}; \dots; x_{i d})

2、目标学得的预测函数

f ({\vec{x}}_{i}) = {\vec{ω}}^{T} {\vec{x}}_{i} + b

系数向量

\vec{ω} = (ω 1; ω 2; \dots; ω d)

3、通过训练数据集求得

ω

和

b

的最佳值，使得

f ({\vec{x}}_{i}) \approx y_{i}

也叫做“多元线性回归”

公式推导

此处对 $ω$ 和 $b$ 的确定也可以使用最小二乘法，为了公式推导的方便，此处做了一些整理， $\hat{\vec{ω}} = (ω; b)$ ，数据集中样本的标记用向量表示为 $\vec{y} = (y_{1}; y_{2}; \dots; y_{m})$ ，类比(2)可以得到代价函数

\begin{matrix} (20) & J_{\hat{\vec{ω}}} = (\vec{y} - X ω)^{2}, \end{matrix}

根据矩阵乘法可以表示为矩阵的转置乘以矩阵

\begin{matrix} (21) & J_{\hat{\vec{ω}}} = (\vec{y} - X ω)^{T} (\vec{y} - X ω), \end{matrix}

对

\hat{\vec{ω}}

求导可得

这里的矩阵求导引用同学推荐的资源一份来自维基百科-矩阵求导，另一份则是一份说明性质的微博

\begin{aligned} (22) & \frac{\partial J_{\hat{\vec{ω}}}}{\partial \hat{\vec{ω}}} & = \frac{\partial (\vec{y} - X_{i})^{T} (\vec{y} - X_{i})}{\partial \hat{\vec{ω}}}, \\ (23) & = \frac{\partial ({\vec{y}}^{T} \vec{y} - {\hat{\vec{ω}}}^{T} {\vec{X}}^{T} \vec{y} - {\vec{y}}^{T} \vec{X} \hat{\vec{ω}} + {\hat{\vec{ω}}}^{T} {\vec{X}}^{T} \vec{X} \hat{\vec{ω}})}{\partial \hat{\vec{ω}}}, \\ (24) & = 0 - {\vec{X}}^{T} \vec{y} - ({\vec{y}}^{T} \vec{X})^{T} + 2 {\vec{X}}^{T} \vec{X} \vec{ω}, \\ (25) & = 2 X^{T} (X \hat{\vec{ω}} - \vec{y}), \end{aligned}

上边的推导过程难点在于从(23) $\to$ (24)的过程，首先判断为分母为列向量，则为分母布局，(23)第一项求导的分子为标量，则求导结果为零，第二项分子为分母列向量的转置和一个(d+1) $\times$ 1的列向量的点乘，第三项分子为一个1 $\times$ (d+1)的行向量和分母列向量的点乘，对照维基百科-矩阵求导表格中的第10行可得对应求导结果，第四项则是对应第13行的求导规则进行求导，矩阵的转置乘以矩阵本身是一个对称矩阵。
此外，在这里求导时，有一个比较简单的方法，参考西瓜书402面的链式求导法则和式(A.32)的举例，可以快速准确的得到答案
令(25)为零可得

\hat{\vec{ω}}

最优解的闭式解，此处因为涉及到矩阵逆的计算，所以需要分类讨论：
当

X^{T} X

为满秩矩阵或正定矩阵，矩阵的逆存在，所以由(25)为零可得

\begin{matrix} (26) & X^{T} X \hat{\vec{ω}} = X^{T} \vec{y}, \end{matrix}

等式两边同乘逆矩阵

(X^{T} X)^{- 1}

可得

\begin{matrix} (27) & {\hat{\vec{ω}}}^{*} = (X^{T} X)^{- 1} X^{T} \vec{y}, \end{matrix}

令

\hat{\vec{x}} = (\vec{x}; 1)

，则可得多变量线性回归模型

\begin{matrix} (28) & f (\hat{{\vec{x}}_{i}}) = {\hat{{\vec{x}}_{i}}}^{T} (X^{T} X)^{- 1} X^{T} \vec{y}, \end{matrix}

但是很多情况下，数据集的变量数目远远大于样本数，即 $X$ 的列数多于行数，这种情况下相当于(25)为零所对应的线性方程组存在多组解，都能使均方误差最小化，最后选择哪一组解作为输出将由学习算法的归纳偏好决定，一般引入正则化来解决这个问题

3 广义线性模型

理论概述

此部分是对上边已经得到的线性模型

y = {\vec{ω}}^{T} \vec{x} + b

进行变化，我们的目标是使此模型的预测值尽可能地逼近真实的输出值，当样本对应的输出值是在指数尺度上变化，就可以将输出值的对数作为线性模型逼近的目标，上式也就变化为如下形式

\begin{matrix} (29) & l n \vec{y} = {\vec{ω}}^{T} \vec{x} + b, \end{matrix}

上式就是“对数线性回归”(log-linear regression)，其实质是如下式子

\begin{matrix} (30) & y = e^{{\vec{ω}}^{T} \vec{x} + b}, \end{matrix}

对于(29)来说，在形式上仍是线性回归，但是经过(30)的变换就可以发现这是一个从输入空间到输出空间的非线性函数映射，在这里对数函数起的作用就是将线性回归模型的预测值与真实输出值联系起来。通过下图可以清楚地看到这种联系。
《机器学习》学习笔记——Chapter3(3.1-3.3)

图 1 对 数 线 性 回 归 示 意 图

由此推至更一般的形式，存在单调可微函数

g (\cdot)

,可以更一般的表达上边对数函数所起的这种联系

\begin{matrix} (31) & y = g^{- 1} ({\vec{ω}}^{T} \vec{x} + b), \end{matrix}

至此我们得到(31)就是“广义线性模型(generalized linear model)”，函数

g (\cdot)

为“联系函数(link function)”。当

g (\cdot) = l n (\cdot)

时，广义线性模型就是我们前边讨论的对数线性回归，对此类模型的参数估计通常使用加权最小二乘法或极大似然法。

4 对数几率回归

理论概述

至此，我们已经学习了如何使用线性模型进行回归学习，考虑到如何应用的实际的分类任务，我们的做法就是利用线性回归模型，根据实际的分类任务，选择一个合适的单调可微函数将分类任务的真实输出值与线性回归模型的预测值联系起来。
对于输出值为 $0, 1$ 的二分类任务，我们需要找到一类函数，将线性回归模型的实值预测值 $z = {\vec{ω}}^{T} \vec{x} + b$ 转换为 $0 / 1$ 值，最想的首选是“单位阶跃函数(unit-step function)”

\begin{matrix} (32) & y = {\begin{cases} 0, & if n < 0 \\ 0.5, & if z = 0 \\ 1, & if z >0 \end{cases} \end{matrix}

预测值

z

大于零则判断为正例，小于零则为反例，当为临界值零则任意判别；但是从图中可以看出单位阶跃函数在零处不连续，不满足广义线性模型中可微的条件，我们只能寻找相似函数来代替，这里就引出了我们要讨论的对数几率函数

\begin{matrix} (33) & y = \frac{1}{1 + e^{- z}}, \end{matrix}

这是Sigmoid函数的最重要的代表，这里扩展一下，还可以使用双曲正切函数tanH来代替，因为输出区间为

(- 1, 1)

,且整个函数以0为中心，在分类问题中往往会有更好的表现，下图直观的表现了对数几率函数可以很好地将

z

值转化为接近

0 / 1

的

y

值，近似于标准的单位阶跃函数
《机器学习》学习笔记——Chapter3(3.1-3.3)

图 2 单 位 阶 跃 函 数 和 对 数 几 率 函 数

将(33)作为联系函数代入广义线性模型即可得到

\begin{matrix} (34) & y = \frac{1}{1 + e^{- ({\vec{ω}}^{T} \vec{x} + b)}} ， \end{matrix}

变形为

\begin{matrix} (35) & l n \frac{y}{1 - y} = {\vec{ω}}^{T} \vec{x} + b, \end{matrix}

接下来说明对数几率的来源，可以将上式中

y

看作样本

x

正例的可能性，

1 - y

也就是反例可能性，将两者比值称为“几率(odds)”，表现了

x

作为正例的相对可能性。则对几率取对数就得到“对数几率(log odds also logit)”。至此，我们再回过头去看(34)，就明白相比于之前讨论的线性回归模型，对数几率回归其实是将模型的预测输出值逼近真实输出值的对数几率，同时也要注意，虽然也叫“回归”，但实际上是一种应用于分类任务的学习方法，具有如下优点：
(1)可直接建模，无需假设数据分布，避免假设分布不准确的问题；
(2)不仅可以预测类别，还可以完成近似概率预测；
(3)对数几率函数还是任意阶可导的凸函数，可用许多数值优化算法直接求取最优解。

公式推导

与在线性回归中的推导一样，我们得到模型的表达式，就需要确定函数中参数 $\vec{ω}$ 和 $b$ ，将(34)中的 $y$ 看作类后验概率估计，这里讨论的类后验概率可以点击超链接进行了解，我这里以自己的理解来简单介绍一下，在这里就是，代表某件事的 $x$ 输入了模型，也就是这件事发生了，这个后验概率就代表这个输入 $x$ 也就是这件发生的事属于某一类别的概率，借此，我们就可以对 $x$ 这类事进行归类，后验概率越大，此事属于这个类别的概率也就越大。
(35)可以重写成

\begin{matrix} (36) & l n \frac{p (y = 1 | \vec{x})}{p (y = 0 | \vec{x})} = {\vec{ω}}^{T} + b, \end{matrix}

根据概率知识

p (y = 1 | \vec{x}) + p (y = 0 | \vec{x}) = 1

可得后验概率估计表达式

\begin{matrix} (37) & p (y = 1 | \vec{x}) = \frac{e^{{\vec{ω}}^{T} + b}}{1 + e^{{\vec{ω}}^{T} + b}} ， \end{matrix}

\begin{matrix} (38) & p (y = 0 | \vec{x}) = \frac{1}{1 + e^{{\vec{ω}}^{T} + b}} ， \end{matrix}

接下来就是使用极大似然法(ML)来对参数进行估计，在这个超链接中是一篇对极大似然估计的详解，大家可以作为参考。
在对数几率回归模型中，我们可以得到对于数据集

{({\vec{x}}_{i}, y_{i})}_{i = 1}^{m}

的对数似然函数

\begin{matrix} (39) & l (\vec{ω}, b) = \sum_{i = 1}^{m} l n p (y_{i} | {\vec{x}}_{i}; \vec{ω}, b), \end{matrix}

在这里我谈谈我对这部分的理解，我们之所以使用极大似然法来估计参数，其实是利用这个似然函数来作为一个对模型的评价机制，我们仔细分析(39)可以看到，除了参数 $\vec{ω}, b$ 未知，还有一个未知变量就是类后验概率估计p( $\cdot$ )，这是因为对于确定的数据集，如果使用不同的模型去估计每个样本属于其真实输出值的概率是不一样，当模型的参数改变的时候，这个概率也就是后验概率会发生变化，我们评价标准就是这个概率越大越好，从而找到使这个概率最大时候的参数，从而确定最优的模型，所以针对一个数据集来说，我们就可以得到(39)所示的对数似然函数，这中间省略了一些基本的变化，大家可以参看我上边引用的极大似然法那个博客
按照书本书里的处理方法，我也在这里对式子进行一些简化方便后边的讨论
令

\vec{β} = (\vec{ω}; b) ， \hat{\vec{x}} = (\vec{x}; 1)

,
则

{\vec{ω}}^{T} \vec{x} + b = {\vec{β}}^{T} \hat{\vec{x}}

；
再令

p_{1} (\hat{\vec{x}}; \vec{β}) = p (y = 1 | \vec{x}; \vec{β})

，

p_{0} (\hat{\vec{x}}; \vec{β}) = p (y = 0 | \vec{x}; \vec{β}) = 1 - p_{1} (\hat{\vec{x}}; \vec{β})

则(39)中的似然项可变为

\begin{matrix} (40) & p (y_{i} | {\vec{x}}_{i}; \vec{ω}, b) = y_{i} p_{1} (\hat{\vec{x}}; \vec{β}) + (1 - y_{i}) p_{0} (\hat{\vec{x}}; \vec{β}), \end{matrix}

上式其实一个条件函数的变形，若输出值为1则上式右边第一项保留，第二项为零；同理，当第一项为零，第二项保留就是输出值为0的情况。将(40)代入(39),再用(37)(38)代替(40)

p_{1} (\cdot), p_{0} (\cdot)

两项，推导过程如下

\begin{matrix} (41) & l (\vec{β}) = \sum_{i = 1}^{m} l n (y_{i} \frac{e^{{\vec{β}}^{T} \hat{\vec{x}}}}{1 + e^{{\vec{β}}^{T} \hat{\vec{x}}}} + (1 - y_{i}) \frac{1}{1 + e^{{\vec{β}}^{T} \hat{\vec{x}}}}), \end{matrix}

整理后可得

\begin{matrix} (42) & l (\vec{β}) = \sum_{i = 1}^{m} (l n (y_{i} e^{{\vec{β}}^{T} \hat{\vec{x}}} + (1 - y_{i})) - l n (1 + e^{{\vec{β}}^{T} \hat{\vec{x}}})), \end{matrix}

对上式的整理可以使用条件函数简化的思想
当

y_{i} = 0

可以得到

\begin{matrix} (43) & l (\vec{β}) = \sum_{i = 1}^{m} (- l n (1 + e^{{\vec{β}}^{T} \hat{\vec{x}}})), \end{matrix}

当

y_{i} = 1

可以得到

\begin{matrix} (44) & l (\vec{β}) = \sum_{i = 1}^{m} ({\vec{β}}^{T} \hat{{\vec{x}}_{i}} - l n (1 + e^{{\vec{β}}^{T} \hat{{\vec{x}}_{i}}})), \end{matrix}

由上述两种情况就可以得到下面的式子，这个过程是利用

y_{i}

要么是1要么就是0这一特性，就将(42)简化成(45)的形式

\begin{matrix} (45) & l (\vec{β}) = \sum_{i = 1}^{m} (y_{i} {\vec{β}}^{T} \hat{{\vec{x}}_{i}} - l n (1 + e^{{\vec{β}}^{T} \hat{{\vec{x}}_{i}}})), \end{matrix}

细心会发现我推导出的式子和书上的(3.27)正好相反，这是因为书上的式子是一个关于 $\vec{β}$ 的高阶可导连续凸函数，这样根据凸优化理论，可以使用一些经典的数值优化算法求得最优解，只不过在我们这里是最大化(45)，在书中是最大化下式(46)，具体的求解算法如梯度下降法，牛顿法及求解过程在这里不再赘述，将另开博详述，不过在稍后的代码中将会有所体现

\begin{matrix} (46) & l (\vec{β}) = \sum_{i = 1}^{m} (- y_{i} {\vec{β}}^{T} \hat{{\vec{x}}_{i}} + l n (1 + e^{{\vec{β}}^{T} \hat{{\vec{x}}_{i}}})), \end{matrix}

至此，本书第三章的前三小节笔记结束，下一篇将剩余部分的总结，可能有的朋友会觉得全文过长赘述，我的想法能将我在学习过程中遇到的问题一一记录下来，并尽可能给出解答，作为我日后复习的一份参考资料。谢谢诸位的阅读。

《机器学习》学习笔记——Chapter3(3.1-3.3)

1 线性模型

基本形式

基本思想

2 线性回归

理论概述

公式推导

理论概述

公式推导

3 广义线性模型

理论概述

4 对数几率回归

理论概述

公式推导

相关推荐