本文是周志华老师《机器学习》第三章线性模型的学习笔记。  

基本形式

其中 $w=(w_1;w_2;…;w_n)$
线性模型简单,易于建模,可解释性好。

线性回归

根据线性模型基本形式,我们也就是要求适当的 $w,b$ 使得其越接近真实的 $y$。
这里我们用均方误差来度量性能,那么就有:

基于最小化均方误差来求解模型的方法叫做最小二乘法(least square method)
下面我们讨论一下一般情况下(样本由d个属性描述)的最小二乘法估计 $w,b$ 的做法。
首先我们令 $\hat{w}=(w;b)$,同样的,将数据集表示为一个 $m\times(d+1)$ 大小的矩阵 $X$,每行对于一个样本,最后一个元素恒为1,那么就有:

令 $E_{\hat{w}}=(y-X\hat{w})^T(y-X\hat{w})$ ,对其求导:

为了简化讨论,我们令 $X^TX$为满秩矩阵,此时就有:

当然,现实任务中往往不满足满秩的条件,这时我们可以解出多个解,而又选择偏好决定最后输出哪个解。

对数几率回归

为了将线性模型应用到回归上,我们可以找一个单调可微的函数,将分类任务的真实标记和线性回归模型的预测值联系起来,这里常用的就是对数几率函数:

它是一种Sigmoid函数,也就是形似S的函数,我们将其代入,得到:

变换得到:

这里将 $y$ 看做样本为正例的可能, $1-y$ 是其反例的可能性,二者的比值称作几率(odds),对其取对数则为线性回归的预测值,这也是其名字(对数几率回归, logistic regression)的来历。
得到模型后,我们往往通过极大似然法来导出目标函数,

该函数是关于参数的可导连续凸函数,根据凸优化与理论,经典的数值优化算法比如梯度下降,牛顿法都能求得最优解。

这里有30个问题来检验你是否真正理解了对数几率回归。  

线性判别分析

线性判别分析( Linear Discriminat Analysis,LDA),是一种经典的线性学习方法。(由于由Fisher首次提出,又称Fisher线性判别分析)  
其朴素思想为: 给定训练集,将样例投影到一条直线上,是的同类的投影点尽可能近,不同类的投影点尽可能远;对新样本做分类时,同样将其投影到这条直线上,在根据投影点的位置来确定新样本的类别。  
我们令 $X_i,\mu_i,\sum_i$ 表示第 $i$ 类样本的集合,均值向量和协方差矩阵。  
若将数据投影到直线 $w$ 上,则两类样本中心的投影分别为 $w^T\mu_0$ 和 $w^T\mu_1$。  
为了使同类样例投影尽可能小,也就是 $w^T\mu_0w + w^T\mu_1w$ 尽可能小;使类中心距离尽可能大,则为最大化 $||w^T\mu_0-w^t\mu_1 ||_2^2$ 。  
将二者结合,即为最大化:  

定义类内散度矩阵 $S_w=\sum0+\sum_1$
以及类间散度矩阵 $S_b=(\mu_0-\mu_1)(\mu_0-\mu\
1)^T$
则LDA需要最大化的目标就是 $S_b$ 和 $S_w$ 的广义瑞利商。  

这里注意到分子分母都是二次型,也就是说其解仅和方向有关,我们不妨令 $w^TS_ww=1$ 那么,将问题化解为一个约束条件下的优化问题,通过拉格朗日乘子法,我们化约束为乘子得到:  

由于 $S_bw$ 的方向恒为 $\mu_0 -\mu_1$ ,而 $w$的模对结果没有影响, 所以不妨令:  

那么我们就能得到:  

为了推导出$S_B$ 的一般形式,我们先定义“全局散度矩阵”,  

那么就有:  

有多种方式可以实现多分类LDA,常见的有优化如下目标:  

多分类学习  

对于有$N$ 个类别的多分类任务,我们可以将其拆分为多个二分类分类器。
常用拆分有OvO(One vs. One),OvR(One vs Rest),MvM(Many vs Many)。

  • OvO N个类别两两配对,产生 $N(N-1)/2$ 个分类器,并得到 $N(N-1)/2$个结果,最终将预测最多的类别设定为最终分类结果。
  • OvR 将每次一个类的样例作为正例,所有其他类的样例作为房里来训练N个分类器。测试时选择若仅有一个分类器分为正类则判定为该类,若有多个正类,则根据置信来判断。
  • MvM 是OvO和OvR的一般化,每次将若干类作为正例,若干类最为负例。

常见的MvM技术有纠错输出码(Error Correcting Output Codes ECOC)。

类别不平衡

当分类的训练样例数据相差很多,达到一个数量级甚至以上时,我们通常需要通过再缩放(recalling)来平衡数据的分布,通常有几种手段:

  • 欠采样: 去掉数据量多的类别中的部分样本(简单的丢弃数据可能会导致重要信息缺失,可以将该类分割为几个集合供不同分类器训练,然后再将分类器集成)  
  • 过采样: 增加数据量少的类别一部分样本(单纯通过复制样本来增加数据量可能使过拟合风险提高,可以通过一些插值算法来生成)  
  • 调整阈值: 将分类的阈值做相应调整  

习题及答案  

3.1 试析在什么情形下式(3.2)中不必考虑偏置项b.

  1. 能够确定算法结果仅和给出的属性相关;或者有其他影响因素,但是这些因素都相同时。  

3.2 试证明,对于参数 $w$,对率回归的目标函数(3.18)是非凸的,但其对数似然函数是凸的。

3.3 编程实现对数几率回归,并给出西瓜数据集上的结果。
详细代码见Github.
这里用了梯度下降而不是书中的牛顿法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def read_data(file='./dataAlpha.csv'):
# 读入数据
data = pd.read_csv(file, sep=',', header=None)
X = data[[0, 1]]
X.insert(2, 2, 1)
y = data[2]
return X, y

def init_parameter(d):
# 初始化参数
w = np.random.randn(d)
return w

def predict(w, x):
# 预测
t = np.exp(X.dot(w))
return (t / (1 + t)) > 0.5

def cost_function(w, X, y):
# 计算代价函数
T = X.dot(w)
cost = - np.sum(y*T - np.log(1 + np.exp(T)))
return cost

def cal_grad(w, X, y):
# 计算梯度
T = np.exp(X.dot(w))
Z = T / (1 + T)
dw = (y - Z).dot(X)
return dw

def logReg(eta=0.1):
# 对数几率回归
X, y = read_data()
w = init_parameter(X.shape[1])
for i in range(MaxIter):
if (i % 100 == 0):
print(i, cost_function(w, X, y))
dw = cal_grad(w, X, y)
w = w + eta * dw
return w

结果: 由于数据并不是线性可分的,所以结果有误差.
0 True
1 True
2 True
3 True
4 False
5 False
6 False
7 False
8 False
9 False
10 False
11 False
12 False
13 True
14 True
15 False
16 False

3.4 选择两个UCI数据集,比较10折交叉验证法和留一法所估计的对数几率回归的错误率。

首先import包和载入数据,我们这里用了IRIS的数据集,是一个3分类问题,四维连续特征值,150个样本,每类50个样本。

1
2
3
4
5
6
7
8
9
import numpy as np

from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import cross_val_score
iris = load_iris()
print(iris.data.shape)
print(iris.target_names)
['setosa' 'versicolor' 'virginica']

然后我们使用默认超参数的LR模型,算两个CV的分数,分别是score1对应的十折交叉验证和score2对应的留一法,需要注意的是,这里sklearn要求子集中包含至少每类一个样本,所以这里cv数不能直接取样本数。
打印出结果可以看出二者数值很相似,留一法稍高一些。

1
2
3
4
lr = LogisticRegression()
score1 = cross_val_score(lr, iris.data, iris.target, cv=10)
score2 = cross_val_score(lr, iris.data, iris.target, cv=int(iris.data.shape[0]/len(iris.target_names)))
print('10-fold CV :%s\n 1-hold CV :%s'%(score1.mean(), score2.mean()))
10-fold CV :0.953333333333
 1-hold CV :0.96  

具体代码参见Github.

3.5 编程实现线性判别分析,并给出西瓜数据集3.0$\alpha$的结果.
具体代码在Github

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def get_paras(X, y):
# 训练得到参数
m0 = X[y == 0].mean()
m1 = X[y == 1].mean()
sw = np.matrix( (X - m0).T.dot(X - m0) + (X - m1).T.dot(X - m1) )
w = sw.I.dot((m0 - m1))
return w, m0, m1

def lda():
# LDA算法
X, y = read_data()
w, m0, m1 = get_paras(X, y)
edge = (w.dot(m0) + w.dot(m1)) / 2
return w.dot(X.T) < edge

结果是 [ True, True, True, True, True, False, False, False, False,
False, False, False, False, True, True, False, False]
其中True为好瓜, False为坏瓜.