[西瓜书]学习笔记一:绪论与线性模型

开源学习组织Datawhale对外开放了一个机器学习与数据挖掘的算法兴趣班,这里开始用于打卡工作,这次是报班认真学习西瓜书,希望能有所收获。

西瓜书读书笔记,从零开始的西瓜书

绪论

开篇总是最激动人心的,西瓜书按照周志华先生的说法,这是一本“入门级教科书”。入门阶段需要做的,是弄清基本理念、了结领域概貌。再“按图索骥”,进一步对需要的知识点进行研究。最后再“多读几遍”,初入门径后,数月后再阅,可能会有新得。

引例

古往今来,依靠经验对事物进行判断是人类长久所养成的一种思维方式,依靠这种方式,可以对自身所处环境进行分析。例如,根据西瓜的色泽、根蒂,敲声等来判断这是否是一个好西瓜。这种思维方式符合人类的习性,对于计算机而言,让它利用现有规则与经验,来帮助人类进行判断。这就是机器学习。

计算机中,“经验”以“数据”的方式存在,机器学习研究的主要内容,就是研究通过数据产生“模型”的算法,即“学习算法(learning algorithm)”。

形式化定义,假设:

  • P:计算机程序在某任务类T上的性能。
  • T:计算机程序希望实现的任务类。
  • E:表示经验,即历史的数据集。

若该计算机程序通过利用经验E在任务T上获得了性能P的改善,则称该程序对E进行了学习。

术语说明

机器学习首先要有数据,数据的集合称为数据集(data set)。每条数据是对现有事物或者对象的一种描述,称为样本(sample)、示例(instance)。如(色泽=青绿,根蒂=蜷缩,敲声=浊响)这样一个样本描述一个西瓜的特性,每个特性也叫做属性(attribute)、特征(feature)。所有属性能构成一个二维表格(这里有数据库概念或者excel的二维表格就很好理解),叫做样本空间(sample space),样本个数可以理解为空间维度(线性代数概念,类比矩阵)。

训练集(training set)中学习得到模型的过程称为训练(training),学习过程是为了找出或者逼近真相。

训练完成后,需要对未得到结果的数据进行预测。像((色泽=青绿,根蒂=蜷缩,敲声=浊响),好瓜)这类数据是已知结果的数据,其实可以简单理解为通过已知去求未知。上例当中的结果-“好瓜”被称为label

对于离散的数据进行预测,如判断好瓜坏瓜,可以看作分类(classfication)问题。若是连续值进行预测,如西瓜成熟度0.85,0.9等,被称为回归(regression)问题。

对于机器学习而言,大体被分为两类。一是通过已有label推测未知结果,称为监督学习(supervised learning),二是让算法自动划分组进行聚类(clustering),每个组称为簇(cluster),这种方法被称为无监督学习(unsupervised learning)

关于特征的划分,例如身高的取值“高”、“矮”可以转化为{1.0,0.0},瓜类的取值西瓜,南瓜,黄瓜可以转化为(0,0,1),(0,1,0),(1,0,0)。

其他

“奥卡姆剃刀”原则:“若有多个假设与观察一致,则选最简单的那个。”

注意: 奥卡姆剃刀并非唯一可行的原则;

对于一个学习算法a,若它在某问题上比学习算法b好,则必然存在另一些问题,在那里b比a好.即”没有免费的午餐”定理(No Free Lunch Theorem,NFL).因此要谈论算法的相对优劣,必须要针对具体的学习问题

线性模型

最小二乘法

高中数学课本必修3中,曾经出现过“最小二乘法”的概念,根据给定(x,y)点集,拟合出效果最好的一条直线y。这里所指的效果,指的就是整体点集合的误差(均方误差)最小。即:试图找到一条直线,使所有样本到直线上的欧氏距离之和最小。
在拟合出直线y后,对于一个未知的x值,我们可以预测出对应的y值,这就是一个线性回归问题。

欧氏距离:在m维空间中〖两个点之间的真实距离〗或〖向量的自然长度(该点到原点的距离)〗

一元线性回归

在确定好和b之后,模型就构建完成了。
为了使得均方误差

达到最小,即对误差平方和求最小即可。

如何求最小?

求导。高中知识来了,如这样的函数,求解极小值的方法。分别对和b求偏导,并使其为0进行求解。这样的函数,都是凹函数,其最小值点一般在函数的极小值点处,也就是偏导数为0的点。

对应的解分别为

多元线性回归

扩展到高维表示

其中,是多个a的线性组合,当和b确定之后,线性模型就可以建立。这称为多元线性回归

关于线性回归的推导,西瓜书和南瓜书都给出了详细推导,这里不再详述,简单总结下也是求导找到极值点得到极值,找到最小均方误差,进而得到部分最优。重点记录那些我不懂的。在多元线性空间中,为了将b收入当中,将X扩展一列并令其全为1。



现实情况下往往并非满秩矩阵或非奇异矩阵,即特征的个数超过了样本的个数,这种时候往往需要引入正则化(regularization)。

对数几率回归

为了求取输入空间到输出空间的非线性映射,考虑将模型改写为

对数函数将线性回归模型的预测值和真实标记联系起来,这对于分类任务而言十分重要。分类意味着并非连续的结果,只需要将输出划分。例如在二分类问题中,输出标记。将线性回归中连续值转换为标记值,我们需要找到一个映射函数。

理想的函数是单位越阶函数,输出大于0判正,小于0判负。然而它是不连续的,需要一个连续的函数来替代。对数几率函数(logistic fucntion)

常用于代替,其图像对比如下

对应的模型称为“对数几率回归(logistic regression)”,虽然被称作回归,但是它实际上是一种分类方法。式中y可以理解为样本x被视作正例的可能性(后验概率估计),则对数几率表示为

由式

变换而来。通过极大似然法来估计和b,首先将上式重写

目标设置为:最大化每个样本属于真实标记的概率之和,即

上式最大化可等价于最小化

推导过程由南瓜书3.27说明。对最小可以使用梯度下降法,牛顿法进行求解。

线性判别分析(LDA)

线性判别分析(Linear Discriminant Analysis,简称LDA),其基本思想是:将训练样本投影到一条直线上,使得同类的样例尽可能近,不同类的样例尽可能远。

类中心之间的距离尽可能大,即

投影点的协方差尽可能小,即

其中,表示均值向量,协方差矩阵。因此得到了LDA的最大化目标:

为了进一步简化J,定义了两个散度矩阵。

  • 类内散度矩阵(within-class scatter matrix)
  • 类间散度矩阵(between-class scaltter matrix) 由此最大化目标可重写为:的“广义瑞利商”。从而分类问题转化为最优化求解的问题,当求解出后,对新的样本进行分类时,只需将该样本点投影到这条直线上,根据与各个类别的中心值进行比较,从而判定出新样本与哪个类别距离最近。同时注意到J的分子分母都是关于的二次项,因此其解大小与无关,只与其方向相关。使用拉格朗日乘子法对其求解。

分类学习的拆分策略

多分类学习有两个思路。一种是将二分类学习方法推广到多分类,比如上一节讲到的LDA。另一种则是利用二分类的学习器来解决多分类问题。

最经典的拆分策略有三种,即“一对一(OvO)”、“一对其余(OvR)”、“多对多(MvM)”。

  • OvO:给定数据集D,假定其中有N个真实类别,将这N个类别进行两两配对(一个正类/一个反类),从而产生N(N-1)/2个二分类学习器,在测试阶段,将新样本放入所有的二分类学习器中测试,得出N(N-1)个结果,最终通过投票产生最终的分类结果。

  • OvM:给定数据集D,假定其中有N个真实类别,每次取出一个类作为正类,剩余的所有类别作为一个新的反类,从而产生N个二分类学习器,在测试阶段,得出N个结果,若仅有一个学习器预测为正类,则对应的类标作为最终分类结果。

MvM:给定数据集D,假定其中有N个真实类别,每次取若干个类作为正类,若干个类作为反类(通过ECOC码给出,编码),若进行了M次划分,则生成了M个二分类学习器,在测试阶段(解码),得出M个结果组成一个新的码,最终通过计算海明/欧式距离选择距离最小的类别作为最终分类结果。MvM是OvO和OvR的一般形式,反过来说,OvO和OvR是MvM的特例。

分类器越多,ECOC编码越长,纠错能力越强,但开销越大;而且,如果分类有限,那么可组合的数目也有限,码长超过一定程度,也没有意义了。

类别不平衡问题

以二分类问题为例,该问题一般指的是训练集中正负样本数比例相差过大(比如正例9998个,负例2个),其一般会造成以下的一些情况:

  • 类别少的误判惩罚过低,导致有所偏袒,当样本不确定时倾向于把样本分类为多数类。
  • 样本数量分布很不平衡时,特征的分布同样会不平衡。
  • 传统的评价指标变得不可靠,例如准确率。

解决类别不平衡问题一个基本思路是“再缩放”。常见的做法有三种:

  • 在训练样本较多的类别中进行“欠采样”(undersampling),比如从正例中采出100个,常见的算法有:EasyEnsemble。
  • 在训练样本较少的类别中进行“过采样”(oversampling),例如通过对反例中的数据进行插值,来产生额外的反例,常见的算法有SMOTE。
  • 直接基于原数据集进行学习,对预测值进行“再缩放”处理。其中再缩放也是代价敏感学习的基础。

总结

第一次写了这么长的文。

从开始拿起西瓜书,查博客,查推导。看了这么多,总算是有个初步的了解。

本篇是西瓜书的(第一章)绪论与(第三章)线性模型的总结,机器学习的基础知识,线性模型的基本理论都进行了探讨。

参考链接

南瓜书

知乎文章

某Github笔记