只是习惯性的刷feedly(不再是google reader)的时候刷出来Andrew的这篇post...
看到Heckman的时候眼睛顿时一亮。嗯，这是怎么个情况？谁来给我讲讲这里面的宿怨？
然后顺藤摸瓜的，就跑到Rubin causal model那里去了。一直对econometrics宣称的causality有所顾虑，但是没想到这东西居然还在各个领域被发扬光大（越来越体会到economist开山收徒弟的威力）。先不管这个东西的基础到底如何，从实用的角度确实符合了大众的需求——要不这些人早就失业了吧？
但是从实践来看，无论是随机试验还是RD之类的，总是有各种各样的问题，总让我对casual inference的信心越来越低...有的时候，只能一句“呵呵”打发了...
降维完全属于unsupervised learning了，即给定数据集
，我们希望降到q维的
。从这个角度来讲，降维和聚类还是有相通之处的，都是对于特征的提取。只是一个从行的角度出发，一个对列操作的感觉。
个人觉得这也是起名字起的比较好的模型之一...乍一听起来很有用的感觉 -_-||
1. 求
,
使得
，且
最大。
直觉上来讲，就是想寻找一个主方向。
这样，求解问题为：
。所以我们只需要求一阶导数
即可。
设A为对称矩阵，则存在正交阵
使得
，其中
为A的特征值矩阵，故
(列向量为特征向量）。不失一般性，我们可以排序使得
（从大到小排序）。
最大特征值: 
同时
为x的相关矩阵，
，从而
2. 找到(q维的子空间）
将
投影到该q维空间，这样
，且
最小。
A矩阵的范数：
tr表示矩阵的迹（对角线元素和）。
则上述问题等价于，求
使得
最小。
最小。
即使得
最大（注意没有负号）。
称为数据的相似矩阵
。
和
均为对称阵，且两个阵有相同的特征值。记
为A的秩，AA'的特征向量
，A'A的特征向量
，则
，
。做奇异值分解，则
.
由此，求得的和前述结果等价。
回到PCA。如果降维后需要重构，则
，解
即可。
3. 对偶PCA。如果
即数据非常高的时候，可以转置后再做。
4. KPCA （kernel）PCA也可以先用核函数
，即实现非线性的降维。需要注意，降维的过程需要保持可逆。
---------------
PS. PCA不适合解决overfitting的问题。如果需要解决，加regularization项。
补上笔记。这节课讲的就是大名鼎鼎的Kernel Method...
定义 
, 
满足：
1) 对称： 
2) 正定： n个观测
，
正定（或者非负定）。
举例：
，或广义下
，其中
，从
。性质：
1. 封闭性
1) 正定，
，则
正定。
2) 
正定，
正定，则
正定，
正定。
3) 
正定，
，则正定。
4) 
正定
5) 
正定。
2. 归一性
正定，
。
（走神一下：关于这个命名的吐槽猛击 -> 翻译版、 英文原版Normal Deviate）
1. Hilbert空间：完备内积空间，可以视作欧氏空间的推广。
。
在这个空间中，我们定义：
, 
。
：对称性
;线性 
，
.
，则
定义为零元素。
且
，则
。（收敛到该空间内）。2. 再生核Hilbert空间
给定正定，可以构造Hilbert空间H使得
，
；且构造一个
，使得，即核函数可以写成内积形式。
这样对于
，
。
1. 基本思想
将线性模型推广到非线性模型的方法（其中较为简单的一种）
，从
到
的一个映射。举例：
，这样就可以拓展为广义线性模型。
2. SVM
可以转化为：
令
，
，则
非线性变换之后，
注意此时
的维数有变化（
）。
---------------------
如果各位更关心SVM后面的直觉，还是去看看Andrew Ng的相关课程吧...这里推导太多，直觉反而丢了一些。
聚类讲的比较简单...怎么感觉老师不怎么待见unsupervised learning捏？...
---------------笔记开始---------------------
1)分类与聚类（分类标识）
评测纯度。我们有测试集
，这样定义纯度为
.
2) 输入
。
，其中相似度的计算可以是
的内积。显然，向量表示很容易可以计算相似度表示。
，其中距离可以用二阶范数定义，比如
。3) 输出： 
，对应K个聚类。这里还分为：
（注意不要和KNN搞混了，都是K开头的...）
1) K-means方法（特征表示）
输入：
，K——聚类的个数。
算法：
初始化，随机选定类中心.
分配到距离最近的类。，使得
。重复上面两步。2) K-medoids方法（相似度表示）
输入：s,k
初始化。然后根据
分配，再按照
确定新的中心。
3) 模糊的K-means方法
输入：，K
初始化。
,计算
，然后根据这个距离的比重来“软”分配(需要归一化分配权重）。
，利用
中的进行加权平均。重复上述两步。
4) 谱聚类（向量表示）
输入：，K
然后对原始数据做转换，形成新的数据集
，然后再做K-means聚类。
其中转换的步骤如下：
，
。
，则
是U的第i行，这样就从p维降到了K维。1) 自底向上的方法（聚合）
初始：每个都为一类
而后对于最相似的两类，合并到一类。对于类的最相似，可以定义为距离最近的类。而对于距离，则可以定义为三者之一：
，称之为单连。
，称之为全连。
.2) 自顶向下的方法（分裂）
初始：所有的x作为一类。选用一种非层次的方法进行聚类，递归使用。
例子：二分法。
初始：
，
。而后选择离G最远的一个点g。
修改
，
。重复步骤，选择离H近的离G远的逐渐加入H。
直到分不动了，彻底分为两类。
---------------------
下节课讲的是降维方法。
笔记（二十二）需要等我找到上一本笔记本再说，暂时不知道扔到哪里去了...汗。届时补上。
这一章主要是讲的原型方法（prototype）和最近邻（KNN）。相对而言直觉更强，公式没那么复杂。
--------------------------笔记开始-------------------
1) 1-NN 最近邻居方法
最极端的情况：只找到最近的一位邻居。
数据集
，输入，在
中找到与最近的邻居
，输出对应的类标记
。
2) 类中心的方法
类中心： 
，相当于对于一群有着同样类标记的点，对x取平均。
输入：，而后在所有类中心中与其最近的类中心
。
输出：对应的类标记。
3) 对每个类可计算若干个“中心”（称之为原型或者样板，比如在每类中做聚类）。
输入：，而后在所有类中心中与其最近的类中心。
输出：对应的类标记。
4) K-NN方法
输入：，在中找到与最近的K个邻居。
输出：
(最多的那一类，从众原则的感觉）。
由于这一类方法都比较懒，所以称之为lazy learning methods.
1) 结果
设
为Bayes分类器的错误概率（最优分类器）；
为1-NN分类器的错误概率。
则有：当样本数
时，
。接下来会证明这个优良的性质。
2) 分类问题
给定，则
。
这里我们称 
为先验分布，
为类分布。从而
，称之为后验概率。
3) Bayes分类器
x对应的
，即使得后验概率最大的k。
所以，
，从
。
4) 1-NN分类器
1-NN输出的是离x最近的
对应的
，则
。
由于
只限训练集，而
那部分只跟测试集有关，所以由独立性我们可以拆分为：
，则当时，
,
，上面一项可以收敛为
，为后验概率（条件误差）。
5)由于
，设
为所有
中最大的，则
6)
。得证。
下一章会讲到聚类，然后就是降维了。