今儿跑代码的百无聊赖的时间，看了一下昨天收藏的周志华老师的一个演讲：Boosting 25周年。链接在这里：
对Adaboost之类的我已经忘得差不多了，还好有当年ESL的笔记可以翻翻。看周老师这张slide，基本上是总结了一下集成学习（ensemble learning）的大概思路。
按照这个思路，Boosting类和bagging以及random forests这种都算作ensemble learning了。然后在简单的回顾了adaboost的前世今生之后，抛出来一个有趣的问题：
理论上我们证明了，Adaboost在多轮学习之后会过拟合，可是为什么实践中很少看到过拟合的现象呢？
嗯...然后就是边界理论和统计观点的两种解释...我就不赘述了，大家去看周老师的slides就好。我好奇的其实是，overfitting本身是怎么可以用一个理论的方法来证明的呢...感觉不那么直观呢...好好奇啊，想找点相关的paper来看看，可又怕是另外一个大坑，上周那个实验设计的大坑还没填平或者弃坑呢。
补上笔记。这节课讲的就是大名鼎鼎的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的相关课程吧...这里推导太多，直觉反而丢了一些。
1. SVM优化问题
1) 原问题
2) 拉格朗日形式的表述
其中，
。
3) 对偶问题
4) SVM分类器
(i) 
(ii) 选
，
，然后
。
(iii)SVM分类器 
2. SMO算法
1) 基本思想：迭代下降、坐标下降
一次要选择两个变量（否则会破坏
的约束），之后就可以解这个双变量优化问题。
2) 两个变量的优化
任取
,
作为变量，其他
作为常量。
展开的矩阵大致如下：
目标函数=
这样
,
,
,
。
约束
(对应对偶问题)
，这里d代表其余不改变的那些
。
化到单变量的话，
所以，
，最优条件
，其中
和
分别为lower/upper bound。故必有最优点在L、H之间或者L、H之一。
，
，可以解得
这里虽然需要迭代很多次，但是迭代的每一步都比较快。
至于如何选择
，第一个变量可以选择
，同时
最大。第二个变量选择
最大的。
这节课主要是讲线性优化的对偶问题。感觉这东西貌似在运筹学的时候被折腾过一遍，现在又来了-_-||
附赠个老的掉牙的段子...
有人问经济学家一个数学问题，经济学家表示不会解...
然后那个人把这个数学问题转成了一个等价的最优化问题，经济学家立马就解出来了...
好吧，我还是乖乖的赘述一遍对偶问题吧，表示被各种经济学最优化问题折磨过的孩子这点儿真是不在话下。
--------------------------------------------------------------------
1) 优化问题
一个典型的最优化问题形如：
(不等式约束)
（等式约束）
2) 优化问题的Lagrange （拉格朗日）函数
3) 对偶函数
称为该优化问题的对偶函数。此时，
，显然这个时候一阶偏导数为0。
4) 对偶问题
我们称
为原优化问题的对偶问题，可化为最优化问题的标准形式
。
如果原优化问题为凸优化，则
必为凹函数，从而最终的标准形式依旧是一个凸优化问题。
5) 弱对偶性
令
为原问题的解，则
，且
，
.
令
为对偶问题的解，则
; 
.
定理（弱对偶性）：
，即对偶问题的优化值必然小于等于原问题优化值。
6) 强对偶性
当
时，两者具有强对偶性；满足该条件的称之为constraint qualifications，如Sliter定理。
强对偶性满足的时候，原优化问题就可以化为一个二步优化问题了。
7) KTT条件（库恩-塔克条件）
局部最优化成立的必要条件：
（一阶条件）
注：SVM满足强对偶性，所以可以直接解对偶问题。
1) SVM的最优化问题
上节课可知，SVM的最优化问题为：
写成标准形式就是
这样这里总计有2N个约束条件。
对应的Lagrange函数为：
这样一阶条件就是
这样最后我们有
.
3) 对偶函数
这里的对偶函数就是
4) 对偶问题
5) KKT条件
6) SVM分类器
, 
：找到一个
（非边界上），从而满足
。由
，我们可得
, 
，故只与内积有关。这样下节课就会讲到解对偶问题的方法，以及SVM和kernel methods的联系。
支持向量机——最大边距方法
前言：这节课我人在北京，只能回来之后抄一下笔记，然后对着书和wiki理解一下....有什么错误还请大家及时指出。
------------------------------
，线性模型先说一下个人理解的SVM的直觉。下图来自wiki。二次元中的SVM就是想找到一条直线（或者对应高维空间下的超平面）来尽可能的分割开两组数据。比如图中H3和H2这两条直线虽然都可以分开这两组数据，但是显然H3离两组数据都远一些——这就是SVM遵循的最大边距准则。
而在实践中，我们把二类分类分别作为正负1，所以两条距离该分割线平行距离1的直线就应景而生。在这两条直线上的点我们称之为支持向量（SV）。
1) 线性可分：存在
使得
为分割超平面。
2) 一个点到超平面
的距离：
3) 分割超平面的正则表示
数据集到某个超平面的距离
。将
标准化，则
。
4) 最大边距准则 
5) 线性可分时的SVM
等同于
这样就有了一个sign分类器。
6) support vector：分离超平面落在隔离带的边缘，满足
的
被称为SV。
7) 优点：
不满足约束的时候，可以做一些放松——引入
作为松弛变量。
这样原来的最优化问题就变成
最优的分类器则为
这里大概示意了
的应用场景。左边是上述完全可分的情况，右边是没法分开，所以我们容忍一些误差，只要误差之和在一个可以接受的范围之内。
这里的直觉大概是，在低维空间较为稠密的点，可以在高维空间下变得稀疏。从而可能可以找到一个高维空间的线性平面，把他们分开。
原来的数据集是：
然后定义一个从低维到高维的映射：
，使得
。其中
原本属于，此时被映射到一个高维的
，可为无限维Hilbert空间（这里我只是照抄笔记...）。
映射之后的
，之后就是传统的寻找一个线性平面。
的例子：
，这样就打散到一个高维的空间（圆）。
下节课是线性SVM的计算。