本栏目（机器学习）下机器学习基石专题是个人对Coursera公开课机器学习基石（2014）的学习心得与笔记。所有内容均来自Coursera公开课Machine Learning Foundations中Hsuan-Tien Lin林轩田老师的讲解。（https://class.coursera.org/ntumlone-002/lecture）
第11讲——-Linear Models for Classification
在上一讲中，我们了解到线性回归和逻辑回归一定程度上都可以用于线性二值分类，因为它们对应的错误衡量(square error, cross-entropy) 都是“0/1 error” 的上界。
一、3种线性分类模型
本质上讲，线性分类（感知机）、线性回归、逻辑回归都属于线性模型，因为它们的核心都是如下的一个线性score 函数。只是三个model 对其做了不同处理：线性分类对s 取符号；线性回归直接使用s 的值；逻辑回归将s 映射到(0,1) 区间。
为了更方便地比较三个model，对其error function 做一定处理。接下来我们要做的事情就是看看这些Error Function跟ys的关系，在此之前我们先看看ys的物理意义：y代表正确与否correctness，s代表正确或错误的程度score。
通过曲线来比较三个error function （注意：为了让Logistic Error Function完全压在0/1的Error Function上，一般cross-entropy 变为以2为底的scaled cross-entropy），这样很容易通过比较三个error function 来得到分类的0/1 error 的上界。
如果用力把Logistic regression/Linear regression的Error做好，从某种角度来说也把0/1做的还不错。我们就理解了通过逻辑回归或线性回归进行分类的意义。
线性分类(PLA)、线性回归、逻辑回归的优缺点比较：（1）PLA优点：在数据线性可分时高效且准确。缺点：只有在数据线性可分时才可行，否则需要借助POCKET 算法（没有理论保证）。（2）线性回归优点：最简单的优化（直接利用矩阵运算工具）缺点：y*s 的值较大时，与0/1 error 相差较大(loose bound)。（3）逻辑回归优点：比较容易优化（梯度下降）缺点：y*s 是非常小的负数时，与0/1 error 相差较大。
实际中，逻辑回归用于分类的效果优于线性回归的方法和POCKET 算法。线性回归得到的结果w 有时作为其他几种算法的初值。
二、随机梯度下降 (Stochastic Gradient Descent)
传统的随机梯度下降更新方法如下。每次更新都需要遍历所有data，当数据量太大或者一次无法获取全部数据时，这种方法并不可行。
我们希望用更高效的方法解决这个问题，基本思路是：只通过一个随机选取的数据(xn,yn) 来获取“梯度”，，以此对w 进行更新。这种优化方法叫做随机梯度下降。
这种方法在统计上的意义是：进行足够多的更新后，平均的随机梯度与平均的真实梯度近似相等。注意：在这种优化方法中，一般设定一个足够大的迭代次数，算法执行这么多的次数时我们就认为已经收敛（防止不收敛的情况），η经验上的取值在0.1附近会比较合适。
接下感受一下如下的练习题：
三、Multi-class Classification
与二值分类不同的是，我们如何将这些Model延伸来做多类别的分类。一种直观的解决方法是将其转化为多轮的二值分类问题：任意选择一个类作为+1，其他类都看做-1，在此条件下对原数据进行训练，得到w；经过多轮训练之后，得到多个w，如下图得到四个分类器。
对于某个x，在有些时候4个分类器中只会有1个分类器说x就是它的类别；不过对于中间区域的点，4个分类器似乎都会说不是它们的类别，那该如何分类呢？这个时候，就将其分到可能性最大的那个类（例如逻辑回归对于x 属于某个类会有一个概率估计）。如果目标类别是k 个类标签，我们需要k 轮训练，得到k 个w。这种方法叫做One-Versus-All(OVA)。
它的最大缺点是，目标类很多时，每轮训练面对的数据往往非常不平衡(unbalanced)，因为每次训练都是当前类别的概率与其他K-1个类别的概率比较，会严重影响训练准确性。multinomial (‘coupled’) logistic regression 考虑了这个问题，感兴趣的话自学下吧。
四、多元分类vs二元分类
既然这样，One-Versus-All会出现Unbalanced的情况，那么有一种方法叫做One-Versus-One(OVO)尝试解决这个问题。
基本方法：每轮训练时，任取两个类别，一个作为+1，另一个作为-1，其他类别的数据不考虑，这样，同样用二值分类的方法进行训练；目标类有k个时，需要 k*(k-1)/2 轮训练，得到 k*(k-1)/2 个分类器。预测：对于某个x，用训练得到的 k*(k-1)/2 个分类器分别对其进行预测，哪个类别被预测的次数最多，就把它作为最终结果。即通过“循环赛”的方式来决定哪个“类”是冠军。显然，这种方法的优点是每轮训练面对更少、更平衡的数据，而且可以用任意二值分类方法进行训练；缺点是需要的轮数太多(k*(k-1)/2)，占用更多的存储空间，而且预测也更慢。OVA 和 OVO 方法的思想都很简单，可以作为以后面对多值分类问题时的备选方案，并且可以为我们提供解决问题的思路。
第12讲——-Nonlinear Transformation
前面的分析都是基于“线性假设“，它的优点是实际中简单有效，而且理论上有VC 维的保证；然而，面对线性不可分的数据时（实际中也有许多这样的例子），线性方法不那么有效。
一、Quadratic Hypothesis二次假设
对于下面的例子，线性假设显然不奏效，因为数据不是线性可分的。今天要探讨的问题就是如何突破线性假设的限制。
不能接受失败，也意味太想去成功了，从心理学上解释，
