分类目录归档:机器学习

一起学机器学习

Dating-with-Machine-Learning

visitor badge

这个春天一起机器学习 —— Python 数据分析课。

Dating-with-python-this-winter 的后续。

机器学习与数据分析

目标

计划总共 14 周,每周两节理论课,

学会机器学习算法基本思想,为模型选择恰当的假设,编写机器学习代码。

前置条件:学过概率统计、线性代数。

课程表

课程文档可以下载文件,用 Typora 在电脑打开。或者上知乎 机器漫游指南

All Cheat Sheets 是几个著名数据分析框架的“作弊表”,有些代码不会写的可以看看就上手。

课节 文档和视频 直播时间(20:00) 课后作业期限(23:59)
1 ML1. 机器学习入门 | 知乎| bilibili 星期三 星期五
2 ML2. 模型评估与选择(数据集构建) | 知乎| bilibili 星期六
3 ML3. 线性模型基础 | 知乎 | bilibili 星期三
4 ML4. 线性回归实验 | ML4. 对数几率回归与广义线性模型 | 知乎| bilibili 星期一
5 ML5. 线性模型识别手写数字 | 知乎 | bilibili 星期三
6 ML6. 层层递进,决策树模型 | 知乎 | bilibili 星期三

课程结构

  1. 机器学习入门
  2. 模型评价与选择:
    1. 经验误差与结构误差
    2. 评价指标
    3. 比较检验与假设检验
  3. 学习理论:频率派和贝叶斯派
  4. 学习理论:PAC 和 VC维
  5. 数据预处理方法
  6. 学习模型:
    1. 最小二乘法线性回归——线性模型
    2. KNN 算法
    3. 决策树
    4. 支持向量机
    5. 梯度提升与随机森林
    6. 贝叶斯分类器
    7. 马尔可夫随机场

参考书目

"Learning from Data"

《统计学习方法》李航

《机器学习》周志华(西瓜书)以及《如何使用本书》

《南瓜书PumpkinBook》 辅助西瓜书

《机器学习实战:基于Scikit-Learn、Keras和 TensorFlow(原书第2版)》

对数几率回归与广义线性模型

为什么线性模型是可行的?

几何意义——生成子空间

假设有 N 个实例 \mathbf{x_i} = (x_0, x_1, x_2, \cdots, x_n)x_i(i \neq 0) 代表了实例的第 i 个属性, x_0 = 1

那么下列矩阵就变成了 N×(n+1) 维的数据矩阵 \mathbf{X} ,它的每一行表示同一个样本的不同属性,每一列表示不同样本中的相同属性。

\begin{aligned}
\left [  \begin{aligned} --\mathbf{x_1^\top} -- \\ --\mathbf{x_2^\top} --\\ --\dots -- \\ --\mathbf{x_N^\top}-- \\ \end{aligned} \right ]  \end{aligned}

模型是 h(\mathbf{x})=\mathbf{w}^\top \mathbf{x}=\sum_{i=0}^{n} w_{i} \cdot x_{i} ,最优解为 \mathbf{w^*} = (\mathbf{X^\top} \mathbf{X} )^{-1} \mathbf{X^\top} \mathbf{y} = X^\dagger \mathbf{y} ,代入 E_\mathrm{in}(\mathbf{w}) = \frac{1}{N} \| \mathbf{X}\mathbf{w} - \mathbf{y} \| ^2 ,得:

\begin{aligned}
E_\mathrm{in}(\mathbf{w^*}) & = \frac{1}{N}  \| \mathbf{X}\mathbf{X}^\dagger \mathbf{y}  - \mathbf{y} \| ^2 \\
& = \frac{1}{N}  \|    \mathbf{y} -  \mathbf{X}\mathbf{X}^\dagger \mathbf{y} \| ^2 \\
& = \frac{1}{N}  \|    (\mathbf{I} - \mathbf{X}\mathbf{X}^\dagger)  \mathbf{y} \| ^2 \\
& = \frac{1}{N}  \|    (\mathbf{I} - \mathbf{H} )  \mathbf{y} \| ^2
\end{aligned}

注:投影矩阵 P ∈ \mathbb{R}_{n×n} 是正交投影矩阵的充要条件 P^\top = P

下载

如果待拟合数据任意两个属性都线性无关的话, \mathbf{X} 就可以看成一个由它的所有列向量所张成的空间。

属性的数目 n 会远远小于数据的数目 N ,因此 \mathbf{X} 张成的是 N 维空间之内的 n 维生成子空间,或者叫 n 维超平面。这个超平面的每一个维度都对应着数据集的一个列向量。理想条件下,输出 \mathbf{y} 作为属性的线性组合,也应该出现在由数据属性构成的超平面上。但受噪声的影响,真正的 \mathbf{y} 是超平面之外的一个点,这时就要退而求其次,在超平面上找到离 \mathbf{y} 最近的点作为最佳的近似。

  • 黄色区域表示由所有属性张成的超平面;
  • 黑色向量 \mathbf{x_1} 和天蓝色向量 \mathbf{x_2} 表示输入向量;
  • 红色实线 \mathbf{y} 表示真实输出,水平的红色虚线 \mathbf{\hat{y}} 表示数据的最优估计值(属性的线性组合);
  • 垂直的红色虚线表示 \mathbf{y} - \mathbf{\hat{y}} (残差),它与超平面正交。

如果我们假设 \mathbf{w^*} 是上帝所知道的规律,那 \mathbf{Xw^*} 也仍然在 \mathbf{X} 的张成空间里。但是由于噪声 \mathbf{z} 的影响使得 \mathbf{y} 出现了偏差。

\mathbf{Xw^*} + \mathbf{z} = \mathbf{y}

这就使得

\begin{aligned}
E_\mathrm{in}(\mathbf{w^*})  
&= \frac{1}{N}\sum_{i=1}^{N}(\mathbf{y} - \mathbf{\hat{y}})^2 \\
&= \frac{1}{N}\sum_{i=1}^{N}((\mathbf{I} - \mathbf{H})\mathbf{y})^2 \\
&= \frac{1}{n}\sum_{i=1}^{N}((\mathbf{I} - \mathbf{H})\mathbf{z})^2 \\
\end{aligned}

还可以看成,这里把 \mathbf{x} 变成了它的转置(虽然输出的结果没有不同)。 \mathbf{w}^\top \mathbf{x} 背后的寓意是每个包含若干输入属性和一个输出结果的样本都被视为一个整体,误差分散在不同的样本点上;而当输出被写成 \mathbf{x}^\top \mathbf{w} 时,每个单独属性在所有样本点上的取值被视为一个整体,误差分散在每个不同的属性上。

注意我们之前令 \mathbf{x} = (x_0, x_1, x_2, \cdots, x_n)x_i(i \neq 0) 代表了实例的第 i 个属性, x_0 = 1

h(\mathbf{x})=1 \cdot w_{0}+\sum_{j=1}^{n} x_{j} \cdot w_{j}=\mathbf{x}^{\top} \mathbf{w}

概率视角——最大似然估计 MLE

高斯噪声是最复杂的噪声,我们一般认为噪声服从正态分布:

\epsilon \sim N(\mu, \sigma^2)

真实的 f() 受到噪声的影响才有了 {y}

y = f(\mathbf{x}) + \epsilon = \mathbf{w^\top}\mathbf{x} +  \epsilon

y 在条件下满足概率分布:

y|_{\mathbf{x_i};\mathbf{w}}  \sim  N(\mathbf{\mu} + \mathbf{w^\top}\mathbf{x}, \sigma^2)

其概率密度函数为:

f_y(y) = \frac{1}{\sqrt{2\pi} \sigma}exp({-\frac{[y - (\mathbf{\mu} + \mathbf{w^\top}\mathbf{x})]^2} {2 \sigma^2}})

根据最大似然估计得出似然函数:

L(\mathbf{w}) = \prod_{i=1}^{N}f_y(y) \\
\begin{aligned}
ln(L(\mathbf{w})) &= \sum_{i=1}^{N} \frac{1}{\sqrt{2\pi} \sigma}exp({-\frac{[y - (\mathbf{\mu} + \mathbf{w^\top}\mathbf{\tilde{x}})]^2} {2 \sigma^2}})  \\
&= \sum_{i=1}^{N} ln(\frac{1}{\sqrt{2\pi} \sigma}) - {\sum_{i=1}^{N} \frac{[y - (\mathbf{\mu} + \mathbf{w^\top}\mathbf{\tilde{x}})]^2} {2 \sigma^2}} \\
&= \sum_{i=1}^{N} ln(\frac{1}{\sqrt{2\pi} \sigma}) - {\sum_{i=1}^{N} \frac{[y - (\mathbf{\mu} + \mathbf{w^\top}\mathbf{\tilde{x}})]^2} {2 \sigma^2}}\\
&= \sum_{i=1}^{N} ln(\frac{1}{\sqrt{2\pi} \sigma}) - {\sum_{i=1}^{N} \frac{[y - ( \mathbf{w^{*\top}}\mathbf{x})]^2} {2 \sigma^2}}

\end{aligned}

最大化似然函数:

\begin{aligned}
\mathbf{w^*} &= \arg \max _{\mathbf{w^*}}L(\mathbf{w})  \\
&=  \arg \max _{\mathbf{w^*}}\sum_{i=1}^{N} ln(\frac{1}{\sqrt{2\pi} \sigma}) - {\sum_{i=1}^{N} \frac{[y - ( \mathbf{w^{*\top}}\mathbf{{x}})]^2} {2 \sigma^2}} \\
&= \arg \min _{\mathbf{w^*}} {\sum_{i=1}^{N} \frac{[y - ( \mathbf{w^{*\top}}\mathbf{x})]^2} {2 \sigma^2}} \\
&= \arg \min _{\mathbf{w^*}} {\sum_{i=1}^{N} [y - ( \mathbf{w^{*\top}}\mathbf{x})]^2 }
\end{aligned}

对数几率回归

回归就是通过输入的属性值得到一个预测值,是否可以通过一个联系函数,将预测值转化为离散值从而进行分类呢?线性几率回归正是研究这样的问题。

为了解决一个最简单的二类分类问题, 我们为每一个点定义一个值域 [0, 1] 的函数, 表示这个点分在A类或者B类中的可能性, 如果非常可能是A类, 那可能性就逼近 1 , 如果非常可能是B类, 那可能性就逼近0(相对A的可能性)。

我们引入一个对数几率函数(logistic function ,logit 函数,也叫 sigmoid 函数)来实现实数集到 [0, 1] 的映射。将预测值投影到0-1之间,从而将线性回归问题转化为二分类问题。

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

C886BFB9-0C77-4894-B1CF-37409315BB57

一个事件发生的几率(odds)是指该事件发生的概率与该事件不发生的概率的比值。如果事件发生的概率是 p ,那么该事件的几率为 \frac{p}{1-p} ,该事件的对数几率是:

logit(y) = \ln \frac{y}{1-y}

由我们输出的得到:

\ln \frac{p(y=1 \mid \mathbf{x})}{p(y=0 \mid \mathbf{x})}=\mathbf{w}^{\mathrm{T}} \mathbf{x}+b
\begin{array}{l}
p(y=1 \mid \mathbf{x})=\frac{e^{\mathbf{w}^{\mathrm{T}} \mathbf{x}+b}}{1+e^{\mathbf{w}^{\mathrm{T}} \mathbf{x}+b}} \\
p(y=0 \mid \mathbf{x})=\frac{1}{1+e^{\mathbf{w}^{\mathrm{T}} \mathbf{x}+b}}
\end{array}

同样用 MLE:

\ell(\mathbf{w})=\sum_{i=1}^{m} \ln  p\left(y_{i} \mid \mathbf{x}_{i} ; \mathbf{w}\right)

会得到所谓的误差函数,也叫做交叉熵:

E_\mathrm{in} = \ln(1 + \exp(-y\mathbf{w^\top x}))

广义线性模型

考虑所有 y 的衍生物的情形,就得到了“广义的线性模型”(generalized linear model),其中, g 称为联系函数(link function)。

y=g^{-1}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\right)

之前的对数几率回归就是代入了 g(c) = \ln \frac{c}{1-c}

机器学习基础(一)- 对数几率回归(Logistic Regression)笔记| 零一人生

线性模型基础

线性回归

回归问题

之前我们说,当预测值为连续值时,称为“回归问题”,离散值时为“分类问题”。但回归是什么,为什么要叫回归?

线性回归问题就是试图学到一个线性模型尽可能准确地预测新样本的输出值。

输入单一属性的问题,比如通过年龄数据预测一个人身高,输入的属性只有一个,即年龄,往往我们会先得到一系列的有标记数据,例如:[15岁,170cm] …… [20岁,175cm]。

输入多属性的问题,比如预测一个人的收入,输入的属性值就不止一个了,例如:(学历,年龄,性别,颜值,身高,体重)–>15k。回归问题就是要根据这些属性,预测新样本中人的收入。

回归的来源:生物统计学家高尔顿研究父母身高和子女身高时的发现。父亲身高和儿子身高呈正相关关系。而在正相关关系背后还有另一个现象:矮个子父亲的儿子更可能比父亲高;而高个子父亲的儿子更可能比父亲矮。高尔顿对此研究后得出的解释是自然界有一种约束力,使人类身高在一定时期是相对稳定的。如果父母身高(或矮了),其子女比他们更高(矮),则人类身材将向高、矮两个极端分化。自然界不这样做,它让身高有一种回归到中心的作用。

他当时给出了一个回归的式子,y 和 x 分别代表以英寸为单位的子代和父代的身高:

y = 3.78+0.516 x

即使父母的身高都很高,其子女不见得会比父母高,而可能会衰退(regression)(回归)至平均身高的倾向。虽然之后的x 与 y 变量之间并不总是具有“衰退”(回归)关系,但是为了纪念高尔顿这位伟大的统计学家,“线性回归”这一名称就保留了下来。

import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(0, 20, 20)
y = 3.78+ 0.516 * x
trainning_set = y + np.random.randn(y.shape[-1]) * 2
plt.plot(x, trainning_set, 'gx')

coeff = np.polyfit(x, trainning_set, 1)
poly1 = np.polyval(coeff, x)
plt.plot(x, poly1, 'b')

plt.show()

线性模型假设

假设内容:输入变量 x 的各个属性(分量)在对应的输出变量 y 中有不同的权值,或者说,输入变量的各个分量的线性组合来拟合 y 值。

\mathbf{x} = (x_1, x_2, \cdots, x_n) 是一个实例, x_i 代表了实例在第 i 个属性上的取值。我们通常令 x_0 = 1

h(\mathbf{x})=\mathbf{w}^{T} \mathbf{x}=\sum_{i=0}^{n} w_{i} \cdot x_{i}

线性模型最大优点不是计算方便,而是易于解释。一些 SOTA(state of the art) 的模型里面也经常组合使用线性模型。

我们确定了模型假设,那么接下来就是确定模型的参数。

在训练集上确定系数 w_i 时,预测输出 h(x) 和真实输出 y 之间的误差是关注的核心指标。

image-20210310192643787

在线性回归中,我们常常以均方误差 (MSE) 来作为模型误差。当线性回归的模型为二维平面上的直线时,均方误差就是预测输出和真实输出之间的欧几里得距离,也就是向量长度( 或者说向量的 L2 范数)。而以使均方误差取得最小值为目标的模型求解方法就是最小二乘法。平方则是为了得到证书,因此它可以刻画样本点与直线之间的距离。

所以线性模型的泛化误差 E_{\mathrm{out}}(h) ,其中 (\mathbf{x}, y) 是未知的样本:

E_{\mathrm{out}}(h)=\mathbb{E}\left[(h(\mathbf{x}) - y)^{2}\right]

经验误差就是:

E_{\mathrm{in}}(h)=\frac{1}{N} \sum_{i=1}^{N}\left(h\left(\mathbf{x}_{i}\right) - y_{i}\right)^{2}

于是我们得到了最终目标 \mathbf{w}^*

\begin{array}{l}
\mathbf{w}^{*}=  \underset{\mathbf{w}}{\arg \min } E_{\mathrm{in}}(h)
\end{array}

式中每个 x_i 代表训练集中的一个样本。

求偏导以得出最值,粗体是向量或矩阵:

\begin{aligned}

E_\mathrm{in}(h) 
& = E_\mathrm{in}(\mathbf{w}) \\
& = \frac{1}{N}\sum^N_{i=1}(\mathbf{w^\top} \mathbf{x_i}  - {y_i})^2 \\
&=  \frac{1}{N}\sum^N_{i=1}(\mathbf{x_i^\top} \mathbf{w}   - {y_i})^2 \\
&=   \frac{1}{N} \left \|
\begin{aligned}
&\mathbf{x_1^\top} \mathbf{w} -   {y_1} \\
&\mathbf{x_2^\top} \mathbf{w} -   {y_2} \\
&\cdots \\
&\mathbf{x_N^\top} \mathbf{w} -   {y_N} \\
\end{aligned}
\right \| ^2 \\

&=   \frac{1}{N} \left \|
\begin{aligned}
\left [  \begin{aligned} \mathbf{x_1^\top} \\ \mathbf{x_2^\top} \\ \cdots \\ \mathbf{x_N^\top} \\ \end{aligned} \right ]  \mathbf{w} - 
\left [ \begin{aligned}  {y_1} \\ {y_2} \\ \cdots \\ {y_N} \\ \end{aligned} \right ] \end{aligned}
\right \| ^2 \\ 
& = \frac{1}{N}  \| \mathbf{X}\mathbf{w} - \mathbf{y} \| ^2

\end{aligned}

目标变成了:

\begin{aligned} 
\mathbf{w}^{*} &=\underset{\mathbf{w}}{\arg \min }  \frac{1}{N}  \| \mathbf{X}\mathbf{w} - \mathbf{y} \| ^2 \\
\\ &=\underset{\mathbf{w}}{\arg \min }   \frac{1}{N} \left(  \mathbf{w^\top} \mathbf{X^\top} \mathbf{X} \mathbf{w} - 2 \mathbf{w^\top} \mathbf{X^\top} \mathbf{y}  + \mathbf{y^\top}\mathbf{y}
\right)
\end{aligned}

求偏导:

\frac{\partial E_\mathrm{in}(\mathbf{w})} {\partial \mathbf{w}} = 
2 \mathbf{X^\top} \mathbf{X} \mathbf{w} - 2\mathbf{X^\top} \mathbf{y}

令其为0 ,考虑到矩阵不可逆(伪逆),得出:

\mathbf{w^*}  =  (\mathbf{X^\top} \mathbf{X} )^{-1} \mathbf{X^\top} \mathbf{y}
= X^\dagger \mathbf{y}

在单变量线性回归任务中,最小二乘法的作用就是找到一条直线,使所有样本到直线的欧式距离之和最小。说到这里,问题就来了:凭什么使均方误差最小化的参数就是和训练样本匹配的最优模型呢?

模型评估与选择(数据集构建)

机器学习过程

回顾高一的运动学实验,探索运动学公式:

x = \frac{1}{2}at^2

把带有滑轮的长木板平放在实验桌上,把滑轮伸出桌面,把打点计时器固定在长木板上没有滑轮的一端,并把打点计时器连接在电源上。此时 a = g = 10 m/s^2

import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(0, 20, 20)
y = 0.5 * 10 * (x**2)
trainning_set = y + np.random.randn(y.shape[-1]) * 2.5
plt.plot(x, trainning_set, 'gx')

plt.show()

png

训练集 X = \{(x_i, y_i)\} 这里等于 X = \{(0, 0), (1, 20.6), (3, 45.2), \cdots \}

测试集

假设空间:一元一次函数,一元 n 次函数,牛顿的假设-一元二次函数

def poly_format(coeff):
    fmt = ["%.2f" % (coeff[-1])]
    cnt = -1
    for i in reversed(coeff):
        cnt += 1
        if cnt == 0:
            continue
        fmt.append("%.2fx^%d + " % (i, cnt))
    fmt = reversed(fmt)
    return "".join(fmt)
coeff = np.polyfit(x, trainning_set, 2)
print(poly_format(coeff))

poly2 = np.polyval(coeff, x)
plt.plot(x, trainning_set, 'gx')
plt.plot(x, poly2, 'b')
plt.show()
5.01x^2 + -0.22x^1 + 0.64

png

coeff = np.polyfit(x, trainning_set, 1)
print(poly_format(coeff))
poly1 = np.polyval(coeff, x)
plt.plot(x, trainning_set, 'gx')
plt.plot(x, poly1, 'b')
plt.plot(x, test_set, 'rx')
plt.show()
100.03x^1 + -315.95

png

coeff = np.polyfit(x, trainning_set, 3)
print(poly_format(coeff))
poly1 = np.polyval(coeff, x)
plt.plot(x, trainning_set, 'gx')
plt.plot(x, poly1, 'b')
plt.plot(x, test_set, 'rx')

plt.show()
-0.00x^3 + 5.08x^2 + -0.73x^1 + 1.37

png

模型归纳偏好

特化与泛化

没有免费的午餐:https://www.leiphone.com/news/201907/jswawIEtorcAYvrB.html

奥卡姆剃刀原则:如无必要,勿增实体

误差

我们将学习器对样本的实际预测结果与样本的真实值之间的差异成为:误差(error)。

  • 在训练集上的误差称为训练误差(training error)或经验误差(empirical error)。
  • 在测试集上的误差称为测试误差(test error)。
  • 学习器在所有新样本上的误差称为泛化误差(generalization error)。

显然,我们希望得到的是在新样本上表现得很好的学习器,即泛化误差小的学习器。因此,我们应该让学习器尽可能地从训练集中学出普适性的“一般特征”,这样在遇到新样本时才能做出正确的判别。然而,当学习器把训练集学得“太好”的时候,即把一些训练样本的自身特点当做了普遍特征;同时也有学习能力不足的情况,即训练集的基本特征都没有学习出来。我们定义:

  • 学习能力过强,以至于把训练样本所包含的不太一般的特性都学到了,称为:过拟合(overfitting)。
  • 学习能太差,训练样本的一般性质尚未学好,称为:欠拟合(underfitting)。

训练集与测试集的构建方法

我们希望用一个“测试集”的“测试误差”来作为“泛化误差”(因为不可能知道)的近似,因此我们需要对初始数据集进行有效划分,划分出互斥的“训练集”和“测试集”。下面介绍几种常用的划分方法:

留出法

将数据集D划分为两个互斥的集合,一个作为训练集 S ,一个作为测试集 T ,满足 D=S∪TS∩T=∅

常见的划分为:大约2/3-4/5的样本用作训练,剩下的用作测试。需要注意的是:训练/测试集的划分要尽可能保持数据分布的一致性,以避免由于分布的差异引入额外的偏差,常见的做法是采取分层抽样。同时,由于划分的随机性,单次的留出法结果往往不够稳定,一般要采用若干次随机划分,重复实验取平均值的做法。

交叉验证法

将数据集 D 划分为两个互斥的集合,一个作为训练集 S ,一个作为测试集 T ,满足 D=S∪T且S∩T=∅ ,常见的划分为:大约 2/3-4/5 的样本用作训练,剩下的用作测试。需要注意的是:训练/测试集的划分要尽可能保持数据分布的一致性,以避免由于分布的差异引入额外的偏差,常见的做法是采取分层抽样。同时,由于划分的随机性,单次的留出法结果往往不够稳定,一般要采用若干次随机划分,重复实验取平均值的做法。

自助法

我们希望评估的是用整个D训练出的模型。但在留出法和交叉验证法中,由于保留了一部分样本用于测试,因此实际评估的模型所使用的训练集比D小,这必然会引入一些因训练样本规模不同而导致的估计偏差。留一法受训练样本规模变化的影响较小,但计算复杂度又太高了。“自助法”正是解决了这样的问题。

自助法的基本思想是:给定包含m个样本的数据集D,每次随机从D 中挑选一个样本,将其拷贝放入D’,然后再将该样本放回初始数据集D 中,使得该样本在下次采样时仍有可能被采到。重复执行m 次,就可以得到了包含m个样本的数据集D’。

调参

大多数学习算法都有些参数(parameter) 需要设定,参数配置不同,学得模型的性能往往有显著差别,这就是通常所说的"参数调节"或简称"调参" (parameter tuning)。

学习算法的很多参数是在实数范围内取值,因此,对每种参数取值都训练出模型来是不可行的。常用的做法是:对每个参数选定一个范围和步长λ,这样使得学习的过程变得可行。

ML1答案

  1. BCD
  2. 特征选择错了

答案可见 ML3 视频开头

机器学习入门

机器学习入门

课程纲要

什么是机器学习?

Improving some performance measure with experience computed from data.

机器从数据中总结经验。

什么时候用机器学习?

  • 事物存在某种潜在规律
  • 人不能直接发现这种规律 (例如牛顿定律)
  • 能获取大量数据

机器学习概念

  • 输入空间: \mathcal{X}
  • 输出空间: \mathcal{Y}
  • 假设空间( hypothesis space ): \mathcal{H} , 包含所有可能的 f :\mathcal{X} \mapsto \mathcal{Y}
  • 所有记录的集合:数据集, \mathcal{D}=\{\left(\mathbf {x_i},Y_i\right)|1\le i\le m\}
  • 一条记录( instance, sample ) \mathbf{x_i}
  • 数据的特征或者属性 feature, attribute : \mathbf{x_i} = \{x_1, x_2, \cdots, x_n \}
  • 训练集
  • 测试集

假设空间——机器学习的过程

new-pic-mine-e1572009324171

机器学习分类

  • 预测值为离散值或连续值的问题为:

    • 分类(classification)(上火问题,是否下雨)
    • 回归(regression) \mathcal{R}
  • 训练数据有标记信息的学习任务为:监督学习(supervised learning),分类和回归都属于监督学习。

  • 训练数据没有标记信息的学习任务为:无监督学习(unsupervised learning),常见的有聚类和关联规则。

  • 还有:batch learning, online learning, active learning, reinforcement Learning

为什么可以学习?

简要解释计算学习理论:

Ein(h)表示在训练集样本中,h(x)不与f(x)不相等的概率。即模型假设对样本(已知)的错误率。

Eout(h)表示实际所有样本中,h(x)与f(x)不相等的概率。即模型假设对真实情况(未知)的错误率。

霍夫丁不等式:

P[|\nu-\mu|>\epsilon] \leq 2 e^{-2 \epsilon^{2} N}

PAC

数据分析的一般流程

  • 数据清理和格式化
  • 探索性数据分析
  • 特征工程和特征选择
  • 基于性能指标比较几种机器学习模型
  • 对最佳模型执行超参数调整
  • 在测试集上评估最佳模型
  • 解释模型结果
  • 得出结论

13bb24f42e5bb98f4a9c15037e523d7d

作业

选择题

以下哪些问题适合用机器学习来解决?

A. 判断今年是闰年还是平年

B. 判断银行能不能给某人开信用卡

C. 判断北京明天的天气

D. 估计北京西直门早高峰的人流量

E. 计算地球运行的轨道

问答题

亚里士多德提出「物体下落的快慢是由物体本身的重量决定的」,他的错误出现在数据分析的哪一步?

SVM 拓展:RankSVM

基本思想

GBRank 和 RankSVM 都是用来解决 LTR 问题的 pairwise 方法。利用 \Phi(q,d) 得出 query 和文档的特征向量,x1、x2分别是d1、d2的特征,取(x1, x2)为正样本,(x2, x1)为负样本,代入 SVM 模型中。

介绍

RankSVM 是在2002年提出的,之前工作关于LTR的工作貌似只有 Pointwise 相关的,比如 PRanking,这样的排序学习算法Work需要含有档位标注的训练样本,一般有以下几种获取方式:

  1. 需要人工/专家标注
  2. 诱导用户对展现的搜索结果进行反馈

这样就会存在会成本高、可持续性低、受标准者影响大等缺点。

而 RankSVM 只需要根据搜索引擎的点击日志构建 Pair 对即可,相对于先前的工作在算法的实用性上有了非常大的改善。

训练样本设计

对于 q 为一次 query,和文档集合 D = \{d_1, \dots,d_m\} ,算法按照相关性给出给出一个文档排序 r^* 。算法一般找不到最优的 r^* ,而是通过其排序顺序 r_{f(q)} 和最优值得差距来评估搜索排序函数 f

一般搜索引擎都会记录用户搜索后展现的结果以及用户的点击情况,这种日志成本较低,并且改造系统也较为方便,而RankSVM的训练样本就是从这种点击日志中进行提取。

由于用户点击的doc概率和排序的位置影响很大,虽然一般都是偏爱相关性较大的doc,但是如果这种doc排在很后面的话其实用户也几乎不会点,所以 RankSVM 就只考虑top级别的点击日志,一般为top 10

另外在构建训练数据时同一 query 下认为用户被点击 doc 相关性要高于没有被点击的 doc ,但是由于用户是从上往下浏览网页的,所以排在前面的 doc 被点击的概率会大于后面的 doc ,因此 RankSVM 使用的最终策略为:

Pair 构建策略:给定一组排序情况 (doc_1,doc_2,doc_3,\cdots) ,以及 C 记录了用户点击 doc 的情况,则有
doc_i{\overset{r^*}{<}} doc_j 对于所有pair1 \leq i ,同时 i \in Cj \notin C

r^* 表示应有的优化排序,也就是被点击文档的相关性要大于排在该文档前面并且未被点击的文档,看上去很绕口,看个栗子:

假如某个用户搜索某个 query 得到首页10个doc,按顺序使用 doc_i 进行表示,如果该用户点击了 1,3,7 三个文档,则认为有:

doc_3 {\overset{r^*}{<}} doc_2 \\
doc_7 {\overset{r^*}{<}} doc_2 \\
doc_7 {\overset{r^*}{<}} doc_4 \\
doc_7 {\overset{r^*}{<}} doc_5 \\
doc_7 {\overset{r^*}{<}} doc_6

表示该 querydoc_3 的相关性要高于 doc_2 ,理应排在前面,而 doc7 的相关性也应该要高于 doc_{2,4,5,6} ,但是可以发现未见 doc_1 的相关性鉴定,这是由于 doc_1 已经是排在了第一位,本身位置点击概率就就是最高的,所以无法判断与其他文档相关性的高低,同理, doc_{8,9,10} 也未纳入相关性的排序中。

训练样本可以通过这样方式进行构建,但是遗憾的是并没有一种机器学习算法能直接使用这种数据进行训练学习-_-

搜索函数的理论框架

在上面的栗子中,我们希望用新算法完成 doc_{1,3,7} 排在top 3,那这样的文档的真实相关性高的将会排到前面,RankSVM 采用Kendall’s Tau (肯德尔等级相关系数)来统计实际排序与算法排序的度量,先看下面两个变量:

  1. P 表示排序序列中保持一致性的 Pair 对数量,也就是真实相关性高的排在第的前面。
  2. Q 表示排序序列中保持不一致的 Pair 对数量(逆序数),也就是由于算法的误差导致真实相关性低的排在了高的前面
  3. 同时 P+Q=\binom{m}{2}m 表示序列中文档的数量,因为长度为 m 的序列可能组成的 Pair 对为 m 的2组合

\tau 的计算方式为:

\tau(r_a,r_b)=\frac{P-Q}{P+Q}=1-\frac{2Q}{\binom{m}{2}}

r_a 为真实排序, r_b 为算法排序

比如实际文档中的顺序为:

d_1{\overset{r^*}{<}}d_2{\overset{r^*}{<}}d_3{\overset{r^*}{<}}d_4{\overset{r^*}{<}}d_5

但是算法的排序顺序为:

d_3{\overset{\hat{r}}{<}}d_2{\overset{\hat{r}}{<}}d_1{\overset{\hat{r}}{<}}d_4{\overset{\hat{r}}{<}}d_5

因此可以发现算法排序中有3对 Pair 不一致了( \{d_2,d_3\}\{d_1,d_2\}\{d_1,d_3\} ),所以 Q=3P=4+3+2+1-3 = 7 ,最终的 \tau(r,\hat{r})=\frac{7-3}{10}=4
\tau 的值越大,表示排序效果越接近真实,比如上面的 \tau(r,r)=\frac{10-0}{10}=1

还证明了由逆序数 Q 的一个式子为平均准确率指标的下界(具体证明看原文附录):

 AvgPrec(\hat{r}) \geq \frac{1}{R} \left[Q+\binom{R+1}{2}\right]^{-1} \left(\sum_{i=1}^{R} \sqrt{i}\right)^2

R 为排序出现的文档中与 query 相关文档数量(这个是[Mean Average Precision](http://kubicode.me/2016/02/15/Machine Learning/Learning-To-Rank-Base-Knowledge/#MAP)中的标注,与 Pair 对的样本稍微有点差别)
从这个角度也可以看到 \tau 来衡量排序效果好坏的合理性.

现在可以定义学习排序函数得问题,对于有 m 个文档的 D 集合上,有固定且未知分布的概率 P{r(q, r^*)} ,目标是学习到一个 f(q) ,其使得肯德尔系数 \tau 最大化。

\tau_{P}(\mathrm{f})=\int \tau\left(\mathrm{r}_{\mathrm{f}(\mathrm{q})}, \mathrm{r}^{*}\right) d \operatorname{Pr}\left(\mathrm{q}, \mathrm{r}^{*}\right)

以下算法采用经验风险最小化,假设现在有 nq_i 作为训练样本,他们各自的目标排序为 r_i^* ,也就是:

(q_1,r_1^*),(q_2,r_2^*),(q_3,r_3^*),\cdots,(q_n,r_n^*)

给定一个大小为 n 且独立同分布的训练样本 S ,其中算法排序为 \hat{r}_i ,则排序算法的优化目标是将下列式子

\tau_{S}(\mathrm{f})=\frac{1}{n} \sum_{i=1}^{n} \tau\left(\mathrm{r}_{\mathrm{f}\left(\mathrm{q}_{i}\right)}, \mathrm{r}_{i}^{*}\right)

最大化。

RankSVM 排序

假设能找到一个排序算法 f 能使得上面的 \tau_s 得到最大化,对于一个指定的查询 q ,每个文档 d_i 使用特征向量映射方法 \Phi(q,d_i)\vec{w} 是通过学习调整的权重向量。 \Phi(q,d) 是映射到描述查询 q 和文档 d 之间的匹配的特征的映射,例如网页 title, h1, h2 标题共有的单词数,或者 d 的页面排名。

如果是直接使用线性排序方法:

\left(\mathrm{d}_{i}, \mathrm{~d}_{j}\right) \in \mathrm{f}_{\vec{w}}(\mathrm{q}) \Longleftrightarrow \vec{w} \Phi\left(\mathrm{q}, \mathrm{d}_{i}\right)>\vec{w} \Phi\left(\mathrm{q}, \mathrm{d}_{j}\right)

\vec{w} 表示权重向量,线性排序下,排序分数为权重 x 特征向量

上图表示一个二维的权重特征图,在排序的顺序的就是特征在权重上的投影位置顺序,比如单从 W_1 维度进行观察可以看到的排序顺序为{1,2,3,4},而如果按 W_2 维度则是{2,3,1,4}

在这里,间隔被定义为当数据点投射到排序向量 w 时两个数据点之间的最近距离,如图 d_1,d_2

image-20201130191345976

为了最大化 \tau_s ,可以最小化 Q 来代替,也就是说对于线性的排序, Q=0 就是表示下面的等式全成立(也就是最大化)

\forall (d_i,d_j) \in r_1^* : \vec{w} \Phi(q,d_i)>\vec{w} \Phi(q,d_j) \\
… \\
\forall (d_i,d_j) \in r_n^* : \vec{w} \Phi(q,d_i)>\vec{w} \Phi(q,d_j)

不幸的是,优化这个是一个NP问题
但我们可以让他们绝大多数都成立,SVM 在由于软间距最大时可以看到熟悉的身影,可以通过引入(非负)松弛变量 \xi_{i,j,k} 并按如下方式最小化上限 \sum\xi_{i,j,k} 来使用SVM技术来近似解。:

\begin{aligned}
&\min[\frac{1}{2} \vec{w} \cdot \vec{w} + C \sum \xi_{i,j,k}]
\\ \\
\text{s.t. }&\forall (d_i,d_j) \in r_1^* : \vec{w} \Phi(q,d_i) \geq \vec{w} \Phi(q,d_j) + 1 - \xi_{i,j,1} \\
&\cdots \\
&\forall (d_i,d_j) \in r_n^* : \vec{w} \Phi(q,d_i) \geq \vec{w} \Phi(q,d_j) +1 - \xi_{i,j,n} \\
&\forall_i \forall_j \forall_k:\xi_{i,j,k} \geq 0
\end{aligned}

\xi 为松弛项, C 表示平衡项

因此优化该问题时可以将约束转为:

\vec{w} \Phi(q,d_i)-\vec{w} \Phi(q,d_j) \geq 1 - \xi_{i,j,1}

并且由于是线性排序,可以进一步精简为:

\vec{w} \left(\Phi(q,d_i)-\Phi(q,d_j)\right) \geq 1 - \xi_{i,j,1}

Pair 对中只可能 d_i 是否排在 d_j 前面是一个二值结果,所以我们可以将 d_i 排在 d_j 前面的 Pair 为正标签,否则为负标签:

y=\left\{
\begin{aligned}
+1 & \quad if \quad \vec{w} \Phi(q,d_i)>\vec{w} \Phi(q,d_j) \\
-1 & \quad otherwise\\
\end{aligned}
\right.

则最终可以将约束可以写成:

y_i \cdot \vec{w} \left(\Phi(q,d_i)-\Phi(q,d_j)\right) \geq 1 - \xi_{i,j,1}

其中传统的偏置项在 RankSVM 是不需要的,以为正好 Pair 相减时就消掉了

所以这样一个问题等价于 SVM 应用于成对向量差上的分类问题。完全将上面构建的样本转为一个分类问题,使用 SVM 的对偶形式进行求解,并且还可以使用核函数进行非线性的分类。 \vec{w} 对应了排序函数,可以对query-doc pair进行打分和排序。

所以 RankSVM 可以看做是一个回归问题,模型应用的时候,使用当前样本的预估值作为排序的依据。

但是样本的构造就发生了变化,每一条样本表示的是一个序关系。所以,损失函数变为(样本 x_i 排名好于 x_j

\begin{matrix} minimize &&\ \ \ \ \frac{1}{2}|w|^2+C\sum_{ij} \xi_{ij}\\s.t. && (wx_i+b) -(wx_j+b) \ge 1-\xi_{ij}\\ &&\xi_{ij}\ge 0 \end{matrix}

上式为了方便理解,没有进行化简,上式也可以依葫芦画瓢引入核函数。

RankSVM 可以看做是寻找一个超平面,使得点对 (x_i , x_j) 对平面的几何间隔差最大。

rsv(q,d_i)= \vec{w}^* \Phi(q,d_i) = \sum_l^n \alpha_{k,l}^*y_i(\Phi(q_k,d_l) \cdot \Phi(q,d_j))

testbinary_classifiy

上面是表示两个不同的 query 所表示的特征空间,不同的形状表示文档与对应 query 的相关性档位,三角形 x_1 表示相关性档位高,圆圈 x_2 表示相关性档位一般,叉叉 x_3 表示相关性档位差。
将这些样本转为 Pair 对之后可以有:

img

可以发现 x_1-x_3x_1-x_2 为正样本,而 x_2-x_1x_3-x_1 为负样本,因此可以形成对应的训练数据进行训练,其实这样形成的样本是对称的,因此在实际使用中一般只保留一侧即可。

总结

RankSVM 很好的解决原始训练样本构建难的问题,根据点击日志构建样本,既考虑了doc之间的顺序,又保证了可持续性,并且其 Pair 对的训练正好可以使用SVM进行求最优化,而SVM分类器已经是非常成熟并且广泛使用的一种机器学习算法。
因此 RankSVM 虽然在2002年就提出,但是至今在工业界还是广泛使用,但是现在的主要难点是样本 Pair 对的构建,针对不同的场景也不同的策略,不一定只是根据点击顺序,实际使用中还要考虑新样本数据。

参考

  1. Joachims T. Optimizing search engines using clickthrough data[C], Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2002:133-142.

  2. Learning to Rank for Information Retrieval and Natural Language Processing, Hang Li

  3. 原始博文来源于 [RankSvm-基于点击数据的搜索排序算法](http://kubicode.me/2016/03/30/Machine Learning/RankSvm-Optimizing-Search-Engines-using-Clickthrough-Data/),但他转述错了论文的某些细节部分,感觉像机翻,所以修正写好重发。

  4. LTR中RankSVM算法的基本思路是什么?

  5. RankSVM原理