Categories
事儿关经济

说说我所认识的“最小二乘君”(配图版)

由于近些年常常跟搞数据分析的人混迹在一起,所以很多时候说话方式有点偏向机器学习了...顺便心里暗暗的忧伤一下当年的心路历程(不知道我的基本轨迹的可以先去看看CV..)。这里聊作一二记录,讲讲我所认识的“最小二乘法”(下称最小二乘君)。那个,语言稍显浮夸,大家随便看看哈,别较真。

<锲子>

是写小说的时候大家都兴先来个“锲子”么。7年前,我还是一个年幼无知的大学新生儿。当时我们系开了两门传说中各挂50%的数学课:微积分和线性代数。同学们大都学的死去活来,我也学的死去活来,一度开始怀疑自己的智商...其实现在想想,我也不知道当年为什么学的那么痛苦,现在随手用个微积分貌似都很水到渠成的样子。嗯,可能是老师授课方式不够好吧。那年直到期末考试,我也不知道我学了一年的微积分有什么用处,除了背下来少数的几个证明推导和学会了一堆算微积分的“技巧”之外。

从前有棵树,叫高树,树上挂了很多人……挂了很多人的高树...

线性代数也是一样的。当年翻看某本计算机类入门书(可能是算法与数据结构),前言一开始就是一行金字,大意是“矩阵论是当代计算机基础×××”。然后翻翻后面的果然看不懂,于是默默的去图书馆把这本书还了,然后借了一本黄皮的泛着金光《矩阵论》回来。同样悲催的,啥也没看懂,然后默默的放弃了我在这个领域深修的打算,乖乖的回去上必修课了。(所以我当年学习高级计算机知识的一腔热情就被这么无情的浇灭了哇!果断考完当时的计算机等级考试——C语言和数据库就扔掉编程了...)

线性代数一直学到最后,我还是以为这东西就是来替代“高斯消元法”解联立方程式的...什么特征根啊,奇异值分解啊,格拉姆-施密特正交化啊,直到最后我也没明白是干嘛用的,除了会算几个数之外...没想到,那日一别,重逢已是花落花开好几轮之后...当真是良辰美景虚设!只是万万没有想到,他乡遇旧友,而这厮竟和日后的最小二乘君紧密相连,难分难舍。

138112_091242423086_2良辰美景虚设

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记(二十五):降维和PCA

 降维

降维完全属于unsupervised learning了,即给定数据集,我们希望降到q维的。从这个角度来讲,降维和聚类还是有相通之处的,都是对于特征的提取。只是一个从行的角度出发,一个对列操作的感觉。

PCA(主成分分析,Principle Component Analysis)

个人觉得这也是起名字起的比较好的模型之一...乍一听起来很有用的感觉 -_-||

1. 求,使得,且最大。

PCA

直觉上来讲,就是想寻找一个主方向。

这样,求解问题为:

。所以我们只需要求一阶导数即可。

设A为对称矩阵,则存在正交阵使得,其中为A的特征值矩阵,故(列向量为特征向量)。不失一般性,我们可以排序使得(从大到小排序)。

最大特征值:

同时为x的相关矩阵,,从而

2. 找到(q维的子空间)

投影到该q维空间,这样,且最小。

A矩阵的范数:
tr表示矩阵的迹(对角线元素和)。

则上述问题等价于,求使得最小。

最小。

即使得最大(注意没有负号)。

称为数据的相似矩阵

均为对称阵,且两个阵有相同的特征值。记为A的秩,AA'的特征向量,A'A的特征向量,则。做奇异值分解,则.

由此,求得的和前述结果等价。

回到PCA。如果降维后需要重构,则,解即可。

3. 对偶PCA。如果即数据非常高的时候,可以转置后再做。

4. KPCA (kernel)PCA也可以先用核函数,即实现非线性的降维。需要注意,降维的过程需要保持可逆。

---------------

PS. PCA不适合解决overfitting的问题。如果需要解决,加regularization项。

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记(二十二):核函数和核方法

补上笔记。这节课讲的就是大名鼎鼎的Kernel Method...

核函数(正定)

定义 , 满足:

1) 对称:

2) 正定: n个观测 正定(或者非负定)。

举例:

  • 常数——
  • 内积—— ,或广义下,其中,从

性质:

1. 封闭性

1) 正定,,则正定。

2) 正定,正定,则正定,正定。

3) 正定,,则正定。

4) 正定

5) 正定。

2. 归一性

正定,

再生核Hilbert空间(RKHS)

(走神一下:关于这个命名的吐槽猛击 -> 翻译版、 英文原版Normal Deviate

1. Hilbert空间:完备内积空间,可以视作欧氏空间的推广。

在这个空间中,我们定义:

  • 加法:x+y
  • 数乘:,
  • 内积:对称性;线性 .
  • 零元素:若,则定义为零元素。
  • 完备性:如果,则。(收敛到该空间内)。

2. 再生核Hilbert空间

给定正定,可以构造Hilbert空间H使得;且构造一个,使得,即核函数可以写成内积形式。

这样对于

核方法

1. 基本思想

将线性模型推广到非线性模型的方法(其中较为简单的一种)

,从的一个映射。举例:,这样就可以拓展为广义线性模型。

2. SVM

可以转化为:

,则

非线性变换之后,

注意此时的维数有变化()。

---------------------

如果各位更关心SVM后面的直觉,还是去看看Andrew Ng的相关课程吧...这里推导太多,直觉反而丢了一些。

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记(二十四):聚类

聚类讲的比较简单...怎么感觉老师不怎么待见unsupervised learning捏?...

---------------笔记开始---------------------

1. 一般概念

1)分类与聚类(分类标识)

评测纯度。我们有测试集,这样定义纯度为.

2) 输入

  • 特征向量的表示:
  • 相似矩阵的表示:,其中相似度的计算可以是的内积。显然,向量表示很容易可以计算相似度表示。
  • 距离矩阵的表示(不相似度):,其中距离可以用二阶范数定义,比如

3) 输出: ,对应K个聚类。这里还分为:

  • 非层次的
  • 层次的(类似于树结构)

2. K-means方法(非层次聚类)

(注意不要和KNN搞混了,都是K开头的...)

1) K-means方法(特征表示)

输入:,K——聚类的个数。

算法:

初始化,随机选定类中心.

  • (i)根据分配到距离最近的类。
  • (ii)修改,使得。重复上面两步。

2) K-medoids方法(相似度表示)

输入:s,k

初始化。然后根据分配,再按照确定新的中心。

3) 模糊的K-means方法

输入:,K

初始化。

  • (i) ,计算,然后根据这个距离的比重来“软”分配(需要归一化分配权重)。
  • (ii) ,利用中的进行加权平均。

重复上述两步。

4) 谱聚类(向量表示)

输入:,K

然后对原始数据做转换,形成新的数据集,然后再做K-means聚类。

其中转换的步骤如下:

  • (i) 计算相似矩阵S
  • (ii) 计算L=D-S,其中
  • (iii)计算L最小的K个特征值对应的特征向量
  • (iv)让U=,则是U的第i行,这样就从p维降到了K维。
  • (v)对Z进行K-means聚类。

3. 层次聚类

1) 自底向上的方法(聚合)

初始:每个都为一类

而后对于最相似的两类,合并到一类。对于类的最相似,可以定义为距离最近的类。而对于距离,则可以定义为三者之一:

  • (i) ,称之为单连。
  • (ii) ,称之为全连。
  • (iii) .

2) 自顶向下的方法(分裂)

初始:所有的x作为一类。选用一种非层次的方法进行聚类,递归使用。

例子:二分法。

初始:。而后选择离G最远的一个点g。

修改。重复步骤,选择离H近的离G远的逐渐加入H。

直到分不动了,彻底分为两类。

---------------------

下节课讲的是降维方法。

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记(二十三):原型方法和最近邻KNN

笔记(二十二)需要等我找到上一本笔记本再说,暂时不知道扔到哪里去了...汗。届时补上。

这一章主要是讲的原型方法(prototype)和最近邻(KNN)。相对而言直觉更强,公式没那么复杂。

--------------------------笔记开始-------------------

1. 原型方法

1) 1-NN 最近邻居方法

最极端的情况:只找到最近的一位邻居。

数据集,输入,在中找到与最近的邻居,输出对应的类标记

2) 类中心的方法

类中心: ,相当于对于一群有着同样类标记的点,对x取平均。

输入:,而后在所有类中心中与其最近的类中心

输出:对应的类标记。

3) 对每个类可计算若干个“中心”(称之为原型或者样板,比如在每类中做聚类)。

输入:,而后在所有类中心中与其最近的类中心

输出:对应的类标记。

4) K-NN方法

输入:,在中找到与最近的K个邻居。

输出:(最多的那一类,从众原则的感觉)。

由于这一类方法都比较懒,所以称之为lazy learning methods.

2. K-NN方法的错误率(渐近性质)

1) 结果

为Bayes分类器的错误概率(最优分类器);为1-NN分类器的错误概率。

则有:当样本数时,。接下来会证明这个优良的性质。

2) 分类问题

给定,则

这里我们称 为先验分布,为类分布。从而

,称之为后验概率。

3) Bayes分类器

x对应的,即使得后验概率最大的k。

所以,,从

4) 1-NN分类器

1-NN输出的是离x最近的对应的,则

由于只限训练集,而那部分只跟测试集有关,所以由独立性我们可以拆分为:

,则当时,,,上面一项可以收敛为,为后验概率(条件误差)。

5)由于,设为所有中最大的,则

6)。得证。

下一章会讲到聚类,然后就是降维了。