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的计算。
前馈神经网，BP算法，AE（自编码器，Auto-Encoders)
前馈神经网大致就是这个样子，一层一层的结构。这样，我们就由第一代的神经元系统繁殖出来了一个神经元群落...看起来很高深的样子。
先说一些参数和记号：
，
：表示第
层中神经元的个数。特别的，
为所有输入变量的个数（x的维数），
是网络输出的个数。
，
，
：相邻两层（到
)之间的连接的权重。
：第层第
个神经元的偏置值。
,,：第层第个神经元的状态值。
,,：第层第个神经元的活性（activation)，或称为输出。基本关系：
，
，模型：
为
的映射。
给定数据
，定义
那么
接下来的拟合优化问题就是最小化
。这里可以采用梯度下降：
，
，所以需要求得这两个梯度（偏导）项。
定义
，这样
，其中
。
类似的，
为了解
这个东西，我们需要后向递归。
首先在第L层：
，然后
For L-1,...,1，我们有
，这样就一直可以迭代反推至第一层。
3. AE（自编码器，Auto-Encoders)
自编码器可以算是一个简化的神经网，大致只有三层：0，1，2。其中输入是x，输出也是x，但是中间进行了一个过滤。直观的讲，就像一个文件压缩了一下，又解压缩。中间压缩包的体积要比源文件小，但是信息却基本没有损失。
AE基本上想达到两个目标：
1. 
，即中间那层的维数小于原始输入的维数p。
2. 或者输出的均值非常小，即从第一层到最上面一层的输出较为稀疏，不是很强烈的关联。
下节课会讲到SVM。
神经网络，这是要开始Deep Learning了么？
神经网络的历史和大起大落还是可以八卦一下的...
第一波：人工神经网络起源于上世纪40年代，到今天已经70年历史了。第一个神经元模型是1943年McCulloch和Pitts提出的，称为thresholdlogic，它可以实现一些逻辑运算的功能。自此以后，神经网络的研究分化为两个方向，一个专注于生物信息处理的过程，称为生物神经网络；一个专注于工程应用，称为人工神经网络。
第二波：上世纪80年代神经网络的研究热潮。带反馈的神经网络开始兴起，其中以Stephen Grossberg和John Hopfield的工作最具代表性。很多复杂的认知现象比如联想记忆都可以用反馈神经网络进行模拟和解释。一位在神经网络领域非常资深的学者跟我聊天时说，在那个年代，只要你的文章跟神经网络扯上点关系，无论什么杂志，都很容易发表。
第三波：直到2006年深度网络（deep network）和深度学习（deep learning）概念的提出，神经网络又开始焕发一轮新的生命。深度网络，从字面上理解就是深层次的神经网络。至于为什么不沿用以前的术语“多层神经网络”，个人猜测可能是为了与以前的神经网络相区分，表示这是一个新的概念。这个名词由多伦多大学的GeoffHinton研究组于2006年创造。事实上，Hinton研究组提出的这个深度网络从结构上讲与传统的多层感知机没有什么不同，并且在做有监督学习时算法也是一样的。唯一的不同是这个网络在做有监督学习前要先做非监督学习，然后将非监督学习学到的权值当作有监督学习的初值进行训练。
上述来自：http://www.caai.cn/contents/118/1934.html
有没有感觉最近deep learning热得一塌糊涂？好像是个人都知道有这么个词儿但是真正知道他干什么的、怎么来的的人却不怎么多。嗯，貌似从这节课开始，要掀起deep
learning的篇章咯。顿时感觉好洋气哇。
----------正文的分割线-----------
这节课先介绍七十多年前的Perceptron模型。
大致就是这样一张图片。神经元细胞有个大大的细胞核，然后有个轴突。如果神经元细胞拼在一起，可以构成一个神经网络。
（我觉得这个细胞模型和后面的东西其实没太直接的联系...就是一个很好看的图...）
Perceptron模型有若干输入：
，标记为
序列。
每个输入都有一个权重（某种程度上可以理解为信息损失）：
，标记为
序列。
最后每个“细胞”还有一个偏（门限）：b，即我们常说的常数项截距。
最终的状态：
输出：
，比较简单的情况下，
可以是一个二元输出函数，比如
或者写作
。但是比较讨厌的是这个函数不可微，所以我们可以转成一个可微的函数（有点类似logistic regression的思路，用概率的密度函数来做）。
可微的情况下，这个输出就是：
，这样就可以做成一个光滑的曲线了。
给定一批数据, 我们希望求得
使得
，如果
；否则，
(即
。
算法：先是我们可以不断重复的无限复制数据：
然后初始化：
,
。
开始循环：
For 
IF 
，then 
定理 如果存在w使得
成立（即平面线性可分），则Perceptron算法在有限步收敛。
证明：
（仅计算改过的）
。
使得，那么我们有
，
，同时我们有
这样就会有
，当k趋近无穷大的时候，显然左式不成立。所以必有在某个k的时候停止迭代。(1) Collins表述
给定 
，求w使得
，除了
外最大。这样
。
。
(2)算法：
,
。
初始化：,.
For
计算 
，
输出：
(3)定理。若为线性平面可分，则在有限步内收敛。