第4章

第3,4都是关于线性模型，第4章是关于线性分类
按照线性回归的思想，我们可以通过multi-output regression的思想来进行分类，即通过每一个output的值，将其中最大的作为当前的预测分类.
但是这在output>=3的时候会出现问题，毕竟回归函数构建的只是一个超平面，但是softmax却可以通过lr构建多分类模型，这点有待考证~~

文中介绍了几种判别分析方法，但是都没有深入下去。
对于LDA，其需要解决的问题是将样本投影到新的空间，使得各个类的样本中心点尽量分开的同时，保证样本内部的方差尽量小，所以LDA会定义个度量公式(此时为二分类)：
($J(w) = \frac {|\hat {u_1}-\hat {u_2}|^2} {\hat {s_1}^2 + \hat{s_2}^2}$)
此时($\hat {u_i}=w^Tu_i$)，($\hat {s_i}^2 = \sum_{j}^N (z_j-\hat {u_i}^2$),其中($u_i$)表示原始类别i中样本的均值，($z_j$)表示i类中样本投影之后的向量。
($\hat {s_i}^2 = \sum_{j}^N w^T(x_i-u_i)w^T(x_i-u_i) = \sum_{j}^N w^T(x_i-u_i)(x_i-u_i)^Tw$)，中间的部分($s_i=\sum_{j}^N (x_i-u_i)(x_i-u_i)^T$) 不就是类别i的样本协方差矩阵么？令($s_w = s_1 + s_2 $)，那么此时($\hat {s_1}^2 + \hat{s_2}^2 = w^Ts_w w$)，不难得知，($s_b=(u_1-u_2)(u_1-u_2)^T$)，所以($J(w) = \frac {w^Ts_bw} {w^Ts_w w}$)，然后令($|w^Ts_ww|=1$)，便可以变为一个等式约束的优化问题了.
并且再经过进一步推导，可以得到LDA其实和LS是一致的。详见参考资料.

逻辑回归的思路来自于desire to 构建对于x是线性的后验概率模型，使用对数比率或者称之为log-transformation的link function来建模，其先验假设是数据服从高斯分布并且有共同的协方差矩阵！形式如下：
($log \frac {P_r(G=j|X=x)} {P_r(G=K|X=x)} = \beta_{(j0)}+\beta_j^Tx$)
($\cdot \cdot \cdot$)
.于是便可以得到后验概率关于x的线性形式的表达式。这里不区分二分类还是多分类，可以得到联合分布为：
($p(y_i|x_i;\theta) = \sum_{j=1}^{k} p(y_i=j|x_i;\theta)^{I(y_i=j)} $)，其中I为示性函数。LR一般使用极大似然作为优化目标，可得：
($L(\theta) = \prod_{i = 1} ^{N} \prod_{j=1}^{k} p(y_i=j|x_i;\theta)^{I(y_i=j)}$)，在逻辑回归中，这里的j=0,1。然后取对数似然：
($ln(\theta) = log(L(\theta)) = \sum_{i = 1} ^{N} \sum_{j=1}^{k}I(y_i=j)p(y_i=j|x_i;\theta)$)为了求得($ln(\theta)$)的最大值，一般使用梯度下降或者拟牛顿方法进行求解。具体的推导可见：http://www.idiotaron.org/?p=128
lda和lr都是为了找到线性决策平面，而另外一种思路也是寻找线性决策边界，但是却可以使得类间的间距尽量大，这也构成了支撑向量分类器的理论基础。对于感知机而言，主要是对错误分类的点进行调整，直到把所有的点都正确分类。其决策函数定义如下：
($f(x) = \beta^Tx + \beta_0$)，优化目标是：max ($D(\beta, \beta_0) = \sum_{i\in mis_classify} {} [y_i(\beta^Tx_i+\beta_0)]$) 一般使用SGD来进行优化，但是这种情况下会出现几个问题，一是解的多样性，平面存在多个，无法尽可能的减少在未知数据上的泛化风险，解决方案是对这个超平面添加若干约束，由此引申出了基于最优超平面的SVM。二是如果数据非线性可分，无法保证收敛，这个解决方案就很好办了，用基展开或者映射函数将特征映射到高维空间中。
最优超平面的思想是在特征空间中找到一个使得它距离样本集中最近点的距离最大的
hyper plane，有点绕的感觉。在很多的资料中，对SVM的解释都是先找函数距离，也就是所谓的sign distance，在满足约束的条件，maximum sign distance，经过归一化处理之后，就得到geometric distance，然后令($|w^TX + b|=1$)，便得到了我们的初步的优化目标：
($min  1/2{||w||}^2 s\cdot t\cdot y_i(w^Tx_i + b) >= 1$)
直接对这个问题进行求解还是比较复杂的，不过前赴后继的研究者们总算给出了一个fantastic的solution，先将上述的约束条件加上拉格朗日乘子构成目标函数：
($L(w,b,\lambda) = \frac {1} {2} ||w||^2 -\sum_{i=1}^n\lambda_i(y_i(w^Tx_i+b)-1)$)
先看上述问题的等价形式：
($p = max_{\lambda} L(w,b,\lambda)$) 
这个很容易理解，如果满足约束条件的话，p必然等价于($\frac {1} {2} ||w||^2 $),如果不满足约束条件，那么此时p值为无穷大，自然不会是所需要求解的最小值，即有：
($min_{w,b} p = p^*$)
此时($p^*$)和原问题等价。
那么其对偶问题为：($d^* = max_{\lambda} min_{w,b} L(w,b,\lambda) $)
很明显存在($p^* >= d^*$)的关系，网上大多数人说：最大值的最小值必然大于等于最小值的最大值，有点不严谨，有人给出了数学证明，略过~ 此时对于所有相似的优化问题都成立，被称为弱对偶。而我们想要找的便是强对偶，即两者取等号的时刻。强对偶条件成立的前提是优化目标满足KKT条件，关于KKT理解的有点模糊，等看完凸优化再来完善吧。之前有被同学问到为什么需要转换为对偶问题求解，不知道当时怎么跟他解释的了，一般而言除了求解更方便之外，也使得kernel的方法有了用武之地，因为最后的优化目标函数中存在向量积的形式。使用dual transformation的思想除了svm之外，在最大熵中也有应用。



参考资料：
http://www.cnblogs.com/jerrylead/archive/2011/04/21/2024389.html
http://ufldl.stanford.edu/wiki/index.php/Softmax%E5%9B%9E%E5%BD%92
http://blog.pluskid.org/?p=702