【西瓜书】第三章线性模型

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

基本形式

$f(x)=w^Tw+b$

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

线性回归

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

$(w',b')=\underset{(w,b)}{arg\ min}\sum_{i+1}^m(y_i-wx_i-b)^2$

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

$\hat{w}'=\underset{\hat{w}}{arg\ min}(y-X\hat{w})^T(y-X\hat{w})$

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

$\frac{\partial E_{\hat{w}}}{\partial\hat{w}}=2X^T(X\hat{w}-y)$

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

$\hat{w}'=(X^TX)^{-1}X^Ty$

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

对数几率回归

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

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

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

$y=\frac{1}{e^{-(w^Tw+b)}}$

变换得到：

$ln\frac{y}{1-y}=w^Tw+b$

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

$\underset{w, c}{min\,} \sum_{i=1}^n \log(\exp(- y_i (X_i^T w + c)) + 1)$

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

这里有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$ 。　　
将二者结合，即为最大化：　　

$J=\frac{||w^T\mu_0-w^T\mu_1 ||_2^2}{w^T\mu_0w + w^T\mu_1w} \\ =\frac{w^T(\mu_0-\mu_1)(\mu_0-\mu_1)w}{w^T(\sum_0+\sum_1)w}$

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

$J=\frac{w^TS_bw}{w^TS_ww}$

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

$S_bw=\lambda S_ww$

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

$S_bw=\lambda (\mu_0 - \mu_1)$

那么我们就能得到：　　

$w=S_w^{-1}(\mu_0-\mu_1)$$ 　　在实际操作中，求$S\_w$ 的逆矩阵，可以通过奇异值分解等手段。　　我们把情况进一步一般化，考虑多类情况，很容易将$S\_w$ 进行推广。　　 $$S_w=\sum_{i=1}^{N}S_{w_i}$

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

$S_t=S_w+S_b = \sum_{i=1}^{m}(x_i-\mu)(x_i-\mu)^T$

那么就有：　　

$S_b=\sum_{i=1}^{N}m_i(\mu_i-\mu)(\mu_i-\mu)^T$

有多种方式可以实现多分类ＬＤＡ，常见的有优化如下目标：　　

$\underset{max}{W}\frac{W^TS_bW}{W^TS_wW}$

多分类学习　　

对于有$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.

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

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

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

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个样本。

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数不能直接取样本数。
打印出结果可以看出二者数值很相似，留一法稍高一些。

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

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