面试和算法心得

潇洒紫焰

第七章 机器学习

7.1K近邻算法

1.1、什么是K近邻算法
　　何谓K近邻算法，即K-Nearest Neighbor algorithm，简称KNN算法，单从名字来猜想，可以简单粗暴的认为是：K个最近的邻居，当K=1时，算法便成了最近邻算法，即寻找最近的那个邻居。为何要找邻居？打个比方来说，假设你来到一个陌生的村庄，现在你要找到与你有着相似特征的人群融入他们，所谓入伙。
　　用官方的话来说，所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居），这K个实例的多数属于某个类，就把该输入实例分类到这个类中。根据这个说法，咱们来看下引自维基百科上的一幅图：
　　如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。

• 我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手，所谓观其友，而识其人。我们不是要判别上图中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。但一次性看多少个邻居呢？从上图中，你还能看到：
  
• 如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
  如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。
  

　　于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。

1.2、近邻的距离度量表示法
　　上文第一节，我们看到，K近邻算法的核心在于找到实例点的邻居，这个时候，问题就接踵而至了，如何找到邻居，邻居的判定标准是什么，用什么来度量。这一系列问题便是下面要讲的距离度量表示法。但有的读者可能就有疑问了，我是要找邻居，找相似性，怎么又跟距离扯上关系了？
　　这是因为特征空间中两个实例点的距离和反应出两个实例点之间的相似性程度。K近邻模型的特征空间一般是n维实数向量空间，使用的距离可以使欧式距离，也是可以是其它距离，既然扯到了距离，下面就来具体阐述下都有哪些距离度量的表示法，权当扩展。
　　1.欧氏距离，最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中，如点 x = (x1,…,xn) 和 y = (y1,…,yn) 之间的距离为：
　　(1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离：
　　(2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离：
　　(3)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离：
　　也可以用表示成向量运算的形式：
　　其上，二维平面上两点欧式距离，代码可以如下编写：

//unixfy：计算欧氏距离  
double euclideanDistance(const vector<double>& v1, const vector<double>& v2)  
{  
assert(v1.size() == v2.size());  
double ret = 0.0;  
for (vector<double>::size_type i = 0; i != v1.size(); ++i)  
{  
ret += (v1 - v2) * (v1 - v2);  
}  
return sqrt(ret);  
}

　　2.曼哈顿距离，我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标（x1, y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为：，要注意的是，曼哈顿距离依赖座标系统的转度，而非系统在座标轴上的平移或映射。
　　通俗来讲，想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”，此即曼哈顿距离名称的来源， 同时，曼哈顿距离也称为城市街区距离(City Block distance)。
　　(1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离
　　(2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的曼哈顿距离
　　3.切比雪夫距离，若二个向量或二个点p 、and q，其座标分别为及，则两者之间的切比雪夫距离定义如下：，
　　这也等于以下Lp度量的极值：，因此切比雪夫距离也称为L∞度量。
　　以数学的观点来看，切比雪夫距离是由一致范数（uniform norm）（或称为上确界范数）所衍生的度量，也是超凸度量（injective metric space）的一种。
　　在平面几何中，若二点p及q的直角坐标系坐标为及，则切比雪夫距离为：。
　　玩过国际象棋的朋友或许知道，国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？。你会发现最少步数总是max( | x2-x1 | , | y2-y1 | ) 步 。有一种类似的一种距离度量方法叫切比雪夫距离。
　　(1)二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离
　　(2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的切比雪夫距离 　　
　　这个公式的另一种等价形式是
　　4.闵可夫斯基距离(Minkowski Distance)，闵氏距离不是一种距离，而是一组距离的定义。
　　(1) 闵氏距离的定义
　　两个n维变量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：
　　其中p是一个变参数。
　　当p=1时，就是曼哈顿距离
　　当p=2时，就是欧氏距离
　　当p→∞时，就是切比雪夫距离
　　根据变参数的不同，闵氏距离可以表示一类的距离。
　　5.标准化欧氏距离 (Standardized Euclidean distance)，标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，那先将各个分量都“标准化”到均值、方差相等。至于均值和方差标准化到多少，先复习点统计学知识。
　　假设样本集X的数学期望或均值(mean)为m，标准差(standard deviation，方差开根)为s，那么X的“标准化变量”X*表示为：(X-m）/s，而且标准化变量的数学期望为0，方差为1。
即，样本集的标准化过程(standardization)用公式描述就是：
　　标准化后的值 = ( 标准化前的值 － 分量的均值 ) /分量的标准差
　　经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的标准化欧氏距离的公式：
　　如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离(Weighted Euclidean distance)。
　　6.马氏距离(Mahalanobis Distance)
　　（1）马氏距离定义
　　有M个样本向量X1~Xm，协方差矩阵记为S，均值记为向量&mu;，则其中样本向量X到u的马氏距离表示为：
　　（协方差矩阵中每个元素是各个矢量元素之间的协方差Cov(X,Y)，Cov(X,Y) = E{ [X-E(X)] [Y-E(Y)]}，其中E为数学期望）
　　而其中向量Xi与Xj之间的马氏距离定义为：
　　若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了：
　　也就是欧氏距离了。
　　若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。
　　(2)马氏距离的优缺点：量纲无关，排除变量之间的相关性的干扰。
　　「微博上的seafood高清版点评道：原来马氏距离是根据协方差矩阵演变，一直被老师误导了，怪不得看Killian在05年NIPS发表的LMNN论文时候老是看到协方差矩阵和半正定，原来是这回事」
　　7.巴氏距离（Bhattacharyya Distance），在统计中，Bhattacharyya距离测量两个离散或连续概率分布的相似性。它与衡量两个统计样品或种群之间的重叠量的Bhattacharyya系数密切相关。Bhattacharyya距离和Bhattacharyya系数以20世纪30年代曾在印度统计研究所工作的一个统计学家A. Bhattacharya命名。同时，Bhattacharyya系数可以被用来确定两个样本被认为相对接近的，它是用来测量中的类分类的可分离性。
　　（1）巴氏距离的定义
　　对于离散概率分布 p和q在同一域 X，它被定义为：
　　其中：
　　是Bhattacharyya系数。
　　对于连续概率分布，Bhattacharyya系数被定义为：
　　在这两种情况下，巴氏距离并没有服从三角不等式.（值得一提的是，Hellinger距离不服从三角不等式）。
　　对于多变量的高斯分布，，
和是手段和协方差的分布。
　　需要注意的是，在这种情况下，第一项中的Bhattacharyya距离与马氏距离有关联。
　　（2）Bhattacharyya系数
　　Bhattacharyya系数是两个统计样本之间的重叠量的近似测量，可以被用于确定被考虑的两个样本的相对接近。
　　计算Bhattacharyya系数涉及集成的基本形式的两个样本的重叠的时间间隔的值的两个样本被分裂成一个选定的分区数，并且在每个分区中的每个样品的成员的数量，在下面的公式中使用
　　考虑样品a 和 b ，n是的分区数，并且，被一个 和 b i的日分区中的样本数量的成员。更多介绍请参看：http://en.wikipedia.org/wiki/Bhattacharyya_coefficient。
　　8.汉明距离(Hamming distance)， 两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。
或许，你还没明白我再说什么，不急，看下上篇blog中第78题的第3小题整理的一道面试题目，便一目了然了。如下图所示：

//动态规划：   
//f[i,j]表示s[0...i]与t[0...j]的最小编辑距离。   
f[i,j] = min { f[i-1,j]+1,  f[i,j-1]+1,  f[i-1,j-1]+(s==t[j]?0:1) }   
//分别表示：添加1个，删除1个，替换1个（相同就不用替换）。

　　与此同时，面试官还可以继续问下去：那么，请问，如何设计一个比较两篇文章相似性的算法？（这个问题的讨论可以看看这里：http://t.cn/zl82CAH，及这里关于simhash算法的介绍：http://www.cnblogs.com/linecong/archive/2010/08/28/simhash.html），接下来，便引出了下文关于夹角余弦的讨论。
（上篇blog中第78题的第3小题给出了多种方法，读者可以参看之。同时，程序员编程艺术系列第二十八章将详细阐述这个问题）
　　9.夹角余弦(Cosine) ，几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。
　　(1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式：
　　(2) 两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夹角余弦
　　类似的，对于两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)，可以使用类似于夹角余弦的概念来衡量它们间的相似程度，即：
　　夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1。
　　10.杰卡德相似系数(Jaccard similarity coefficient)
　　(1) 杰卡德相似系数
　　两个集合A和B的交集元素在A，B的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号J(A,B)表示。
　　杰卡德相似系数是衡量两个集合的相似度一种指标。
　　(2) 杰卡德距离
　　与杰卡德相似系数相反的概念是杰卡德距离(Jaccard distance)。
　　杰卡德距离可用如下公式表示：
　　杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。
　　(3) 杰卡德相似系数与杰卡德距离的应用
　　可将杰卡德相似系数用在衡量样本的相似度上。
　　举例：样本A与样本B是两个n维向量，而且所有维度的取值都是0或1，例如：A(0111)和B(1011)。我们将样本看成是一个集合，1表示集合包含该元素，0表示集合不包含该元素。
　　M11 ：样本A与B都是1的维度的个数
　　M01：样本A是0，样本B是1的维度的个数
　　M10：样本A是1，样本B是0 的维度的个数
　　M00：样本A与B都是0的维度的个数
　　依据上文给的杰卡德相似系数及杰卡德距离的相关定义，样本A与B的杰卡德相似系数J可以表示为：
　　这里M11+M01+M10可理解为A与B的并集的元素个数，而M11是A与B的交集的元素个数。而样本A与B的杰卡德距离表示为J’：
　　11.皮尔逊系数(Pearson Correlation Coefficient)
　　在具体阐述皮尔逊相关系数之前，有必要解释下什么是相关系数 ( Correlation coefficient )与相关距离(Correlation distance)。
　　相关系数 ( Correlation coefficient )的定义是：
　　(其中，E为数学期望或均值，D为方差，D开根号为标准差，E{ [X-E(X)] [Y-E(Y)]}称为随机变量X与Y的协方差，记为Cov(X,Y)，即Cov(X,Y) = E{ [X-E(X)] [Y-E(Y)]}，而两个变量之间的协方差和标准差的商则称为随机变量X与Y的相关系数，记为)
　　相关系数衡量随机变量X与Y相关程度的一种方法，相关系数的取值范围是[-1,1]。相关系数的绝对值越大，则表明X与Y相关度越高。当X与Y线性相关时，相关系数取值为1（正线性相关）或-1（负线性相关）。
　　具体的，如果有两个变量：X、Y，最终计算出的相关系数的含义可以有如下理解：
　　当相关系数为0时，X和Y两变量无关系。
　　当X的值增大（减小），Y值增大（减小），两个变量为正相关，相关系数在0.00与1.00之间。
　　当X的值增大（减小），Y值减小（增大），两个变量为负相关，相关系数在-1.00与0.00之间。
　　相关距离的定义是：
　　OK，接下来，咱们来重点了解下皮尔逊相关系数。
　　在统计学中，皮尔逊积矩相关系数（英语：Pearson product-moment correlation coefficient，又称作 PPMCC或PCCs, 用r表示）用于度量两个变量X和Y之间的相关（线性相关），其值介于-1与1之间。
　　通常情况下通过以下取值范围判断变量的相关强度：
　　相关系数
0.8-1.0 极强相关
0.6-0.8 强相关
0.4-0.6 中等程度相关
0.2-0.4 弱相关
0.0-0.2 极弱相关或无相关
　　在自然科学领域中，该系数广泛用于度量两个变量之间的相关程度。它是由卡尔·皮尔逊从弗朗西斯·高尔顿在19世纪80年代提出的一个相似却又稍有不同的想法演变而来的。这个相关系数也称作“皮尔森相关系数r”。
　　(1)皮尔逊系数的定义：
　　两个变量之间的皮尔逊相关系数定义为两个变量之间的协方差和标准差的商：
　　以上方程定义了总体相关系数, 一般表示成希腊字母&rho;(rho)。基于样本对协方差和方差进行估计，可以得到样本标准差, 一般表示成r：
　　一种等价表达式的是表示成标准分的均值。基于(Xi, Yi)的样本点，样本皮尔逊系数是
　　其中、及，分别是标准分、样本平均值和样本标准差。
　　或许上面的讲解令你头脑混乱不堪，没关系，我换一种方式讲解，如下：
　　假设有两个变量X、Y，那么两变量间的皮尔逊相关系数可通过以下公式计算：

• 　　公式一：
  　　注：勿忘了上面说过，“皮尔逊相关系数定义为两个变量之间的协方差和标准差的商”，其中标准差的计算公式为：
  
  
• 　　公式二：
  
  
• 　　公式三：
  
  
• 　　公式四：
  
  

　　以上列出的四个公式等价，其中E是数学期望，cov表示协方差，N表示变量取值的个数。
　　(2)皮尔逊相关系数的适用范围
　　当两个变量的标准差都不为零时，相关系数才有定义，皮尔逊相关系数适用于：

• 两个变量之间是线性关系，都是连续数据。
  
• 两个变量的总体是正态分布，或接近正态的单峰分布。
  
• 两个变量的观测值是成对的，每对观测值之间相互独立。
  

　　(3)如何理解皮尔逊相关系数
　　rubyist：皮尔逊相关系数理解有两个角度
　　其一, 按照高中数学水平来理解, 它很简单, 可以看做将两组数据首先做Z分数处理之后, 然后两组数据的乘积和除以样本数，Z分数一般代表正态分布中, 数据偏离中心点的距离.等于变量减掉平均数再除以标准差.(就是高考的标准分类似的处理)
　　样本标准差则等于变量减掉平均数的平方和，再除以样本数，最后再开方，也就是说，方差开方即为标准差，样本标准差计算公式为：
　　所以, 根据这个最朴素的理解,我们可以将公式依次精简为:
　　其二, 按照大学的线性数学水平来理解, 它比较复杂一点,可以看做是两组数据的向量夹角的余弦。下面是关于此皮尔逊系数的几何学的解释，先来看一幅图，如下所示：
　　回归直线： y=gx(x) [红色] 和 x=gy(y) [蓝色]
　　如上图，对于没有中心化的数据, 相关系数与两条可能的回归线y=gx(x) 和 x=gy(y) 夹角的余弦值一致。
对于没有中心化的数据 (也就是说, 数据移动一个样本平均值以使其均值为0), 相关系数也可以被视作由两个随机变量 向量 夹角 的 余弦值（见下方）。
　　举个例子，例如，有5个国家的国民生产总值分别为 10, 20, 30, 50 和 80 亿美元。 假设这5个国家 (顺序相同) 的贫困百分比分别为 11%, 12%, 13%, 15%, and 18% 。 令 x 和 y 分别为包含上述5个数据的向量: x = (1, 2, 3, 5, 和 y = (0.11, 0.12, 0.13, 0.15, 0.18)。
　　利用通常的方法计算两个向量之间的夹角 (参见 数量积), 未中心化 的相关系数是:
　　我们发现以上的数据特意选定为完全相关: y = 0.10 + 0.01 x。 于是，皮尔逊相关系数应该等于1。将数据中心化 (通过E(x) = 3.8移动 x 和通过 E(y) = 0.138 移动 y ) 得到 x = (&minus;2.8, &minus;1.8, &minus;0.8, 1.2, 4.2) 和 y = (&minus;0.028, &minus;0.018, &minus;0.008, 0.012, 0.042), 从中
　　(4)皮尔逊相关的约束条件
　　从以上解释, 也可以理解皮尔逊相关的约束条件:

• 两个变量间有线性关系
  
• 变量是连续变量
  
• 变量均符合正态分布,且二元分布也符合正态分布
  
• 两变量独立
  

　　在实践统计中,一般只输出两个系数,一个是相关系数,也就是计算出来的相关系数大小,在-1到1之间;另一个是独立样本检验系数,用来检验样本一致性。
　　简单说来，各种“距离”的应用场景简单概括为，空间：欧氏距离，路径：曼哈顿距离，国际象棋国王：切比雪夫距离，以上三种的统一形式:闵可夫斯基距离，加权：标准化欧氏距离，排除量纲和依存：马氏距离，向量差距：夹角余弦，编码差别：汉明距离，集合近似度：杰卡德类似系数与距离，相关：相关系数与相关距离。

1.3、K值的选择
　　除了上述1.2节如何定义邻居的问题之外，还有一个选择多少个邻居，即K值定义为多大的问题。不要小看了这个K值选择问题，因为它对K近邻算法的结果会产生重大影响。如李航博士的一书「统计学习方法」上所说：

• 如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
  
• 如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
  
• K=N，则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的累，模型过于简单，忽略了训练实例中大量有用信息。
  

　　在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是一部分样本做训练集，一部分做测试集）来选择最优的K值。


7.2支持向量机

第一层、了解SVM
　　支持向量机，因其英文名为support vector machine，故一般简称SVM，通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。

1.1、线性分类
　　理解SVM，咱们必须先弄清楚一个概念：线性分类器。

1.1.1、分类标准
　　考虑一个二类的分类问题，数据点用x来表示，类别用y来表示，可以取1或者-1，分别代表两个不同的类，且是一个n 维向量，w^T中的T代表转置。一个线性分类器的学习目标就是要在n维的数据空间中找到一个分类超平面，其方程可以表示为：
　　可能有读者对类别取1或-1有疑问，事实上，这个1或-1的分类标准起源于logistic回归，为了过渡的自然性，咱们就再来看看这个logistic回归。

1.1.2、1或-1分类标准的起源：logistic回归
　　Logistic回归目的是从特征学习出一个0/1分类模型，而这个模型是将特性的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此，使用logistic函数（或称作sigmoid函数）将自变量映射到(0,1)上，映射后的值被认为是属于y=1的概率。
　　假设函数
　　其中x是n维特征向量，函数g就是logistic函数。
　　而的图像是
　　可以看到，通过logistic函数将自变量从无穷映射到了(0,1)，而假设函数就是特征属于y=1的概率。
　　从而，当我们要判别一个新来的特征属于哪个类时，只需求，若大于0.5就是y=1的类，反之属于y=0类。
　　再审视一下，发现只和有关，>0，那么>0.5，g(z)只不过是用来映射，真实的类别决定权还在。还有当>>0时，=1，反之=0。如果我们只从出发，希望模型达到的目标无非就是让训练数据中y=1的特征>>0，而是y=0的特征<<0。Logistic回归就是要学习得到，使得正例的特征远大于0，负例的特征远小于0，强调在全部训练实例上达到这个目标。

1.1.3、形式化标示

• 我们这次使用的结果标签是y=-1,y=1，替换在logistic回归中使用的y=0和y=1。
  
• 同时将替换成w和b。
  
• 以前的，其中认为，现在我们替换为b；
  
• 后面的 替换为（即）。
  

　　这样，我们让，进一步。也就是说除了y由y=0变为y=-1，只是标记不同外，与logistic回归的形式化表示没区别。
　　再明确下假设函数
　　上面提到过我们只需考虑的正负问题，而不用关心g(z)，因此我们这里将g(z)做一个简化，将其简单映射到y=-1和y=1上。映射关系如下：
　　于此，想必已经解释明白了为何线性分类的标准一般用1 或者-1 来标示。

1.2、线性分类的一个例子
　　假定现在有一个一个二维平面，如下图所示，平面上有两种不同的点，分别用两种不同的颜色表示，一种为红颜色的点，另一种为蓝颜色的点，如果我们要在这个二维平面上找到一个可行的超平面的话，那么这个超平面可以是下图中那根红颜色的线(在二维空间中，超平面就是一条直线)。
　　从上图中我们可以看出，这条红颜色的线作为一个超平面，把红颜色的点和蓝颜色的点分开来了，在超平面一边的数据点所对应的y全是 -1 ，而在另一边全是1。
　　接着，我们可以令分类函数：
　　显然，如果 f(x)=0 ，那么x是位于超平面上的点。我们不妨要求对于所有满足 f(x)<0 的点，其对应的 y 等于 -1 ，而 f(x)>0 则对应 y=1 的数据点。
　　注：上图中，定义特征到结果的输出函数，与我们之前定义的实质是一样的。为什么？因为无论是，还是，不影响最终优化结果。下文你将看到，当我们转化到优化的时候，为了求解方便，会把yf(x)令为1，即yf(x)是y(w^x + ，还是y(w^x - ，对我们要优化的式子max1/||w||已无影响。
　　从而在我们进行分类的时候，将数据点 x代入 f(x) 中，如果得到的结果小于 0 ，则赋予其类别 -1 ，如果大于 0 则赋予类别 1 。如果 f(x)=0，则很难办了，分到哪一类都不是。
　　此外，有些时候，或者说大部分时候数据并不是线性可分的，这时满足这样条件的超平面可能就根本不存在，这里咱们先从最简单的情形开始推导，就假设数据都是线性可分的，亦即这样的超平面是存在的。

1.3、函数间隔Functional margin与几何间隔Geometrical margin
　　一般而言，一个点距离超平面的远近可以表示为分类预测的确信或准确程度。

• 在超平面w*x+b=0确定的情况下，|w*x+b|能够相对的表示点x到距离超平面的远近，而w*x+b的符号与类标记y的符号是否一致表示分类是否正确，所以，可以用量y*(w*x+b)的正负性来判定或表示分类的正确性和确信度。
  

　　于此，我们便引出了定义样本到分类间隔距离的函数间隔functional margin的概念。

1.3.1、函数间隔Functional margin
　　我们定义函数间隔functional margin 为：
　　接着，我们定义超平面(w，b)关于训练数据集T的函数间隔为超平面(w，b)关于T中所有样本点(xi，yi)的函数间隔最小值，其中，x是特征，y是结果标签，i表示第i个样本，有：
　　= mini (i=1，…n)
　　然与此同时，问题就出来了：上述定义的函数间隔虽然可以表示分类预测的正确性和确信度，但在选择分类超平面时，只有函数间隔还远远不够，因为如果成比例的改变w和b，如将他们改变为2w和2b，虽然此时超平面没有改变，但函数间隔的值f(x)却变成了原来的2倍。
　　事实上，我们可以对法向量w加些约束条件，使其表面上看起来规范化，如此，我们很快又将引出真正定义点到超平面的距离–几何间隔geometrical margin的概念（很快你将看到，几何间隔就是函数间隔除以个||w||，即yf(x) / ||w||）。

1.3.2、点到超平面的距离定义：几何间隔Geometrical margin
　　对于一个点 x ，令其垂直投影到超平面上的对应的为 x0 ，w 是垂直于超平面的一个向量，为样本x到分类间隔的距离，
　　我们有
　　其中，||w||表示的是范数。
　　又由于 x0 是超平面上的点，满足 f(x0)=0 ，代入超平面的方程即可算出：
　　不过这里的是带符号的，我们需要的只是它的绝对值，因此类似地，也乘上对应的类别 y即可，因此实际上我们定义 几何间隔geometrical margin 为(注：别忘了，上面的定义，=y(wTx+b)=yf(x) )：
　　代人相关式子可以得出：yi*(w/||w|| + b/||w||)。
　　综上，函数间隔y*(wx+b)=y*f(x)实际上就是|f(x)|，只是人为定义的一个间隔度量；而几何间隔|f(x)|/||w||才是直观上的点到超平面距离。

1.4、最大间隔分类器Maximum Margin Classifier的定义
　　由上，我们已经知道，函数间隔functional margin 和 几何间隔geometrical margin 相差一个的缩放因子。按照我们前面的分析，对一个数据点进行分类，当它的 margin 越大的时候，分类的 confidence 越大。对于一个包含 n 个点的数据集，我们可以很自然地定义它的 margin 为所有这n个点的 margin 值中最小的那个。于是，为了使得分类的 confidence 高，我们希望所选择的超平面hyper plane 能够最大化这个 margin 值。
　　且

• 　　functional margin 明显是不太适合用来最大化的一个量，因为在 hyper plane 固定以后，我们可以等比例地缩放 w 的长度和 b 的值，这样可以使得的值任意大，亦即 functional margin可以在 hyper plane 保持不变的情况下被取得任意大，
  
  
• 　　而 geometrical margin 则没有这个问题，因为除上了这个分母，所以缩放 w 和 b 的时候的值是不会改变的，它只随着 hyper plane 的变动而变动，因此，这是更加合适的一个 margin 。
  
  

　　这样一来，我们的 maximum margin classifier 的目标函数可以定义为：
　　当然，还需要满足一定的约束条件：
　　其中 (等价于= /||w||，故有稍后的 =1 时， = 1 / ||w||)，处于方便推导和优化的目的，我们可以令=1(对目标函数的优化没有影响) ，此时，上述的目标函数转化为：
　　其中，s.t.，即subject to的意思，它导出的是约束条件。
　　通过求解这个问题，我们就可以找到一个 margin 最大的 classifier ，通过最大化 margin ，我们使得该分类器对数据进行分类时具有了最大的 confidence，从而设计决策最优分类超平面。
　　如下图所示，中间的红色线条是 Optimal Hyper Plane ，另外两条线到红线的距离都是等于的(便是上文所定义的geometrical margin，当令=1时，便为1/||w||，而我们上面得到的目标函数便是在相应的约束条件下，要最大化这个1/||w||值)：

1.5、到底什么是Support Vector
　　通过上节1.4节最后一张图：
　　我们可以看到两个支撑着中间的 gap 的超平面，到中间的纯红线separating hyper plane 的距离相等，即我们所能得到的最大的 geometrical margin，而“支撑”这两个超平面的必定会有一些点，而这些“支撑”的点便叫做支持向量Support Vector。
　　换言之，Support Vector便是下图中那蓝色虚线和粉红色虚线上的点：
　　很显然，由于这些 supporting vector 刚好在边界上，所以它们满足，而对于所有不是支持向量的点，也就是在“阵地后方”的点，则显然有。

第二层、深入SVM

2.1、从线性可分到线性不可分

2.1.1、从原始问题到对偶问题的求解
　　根据我们之前得到的目标函数（subject to导出的则是约束条件）：
　　由于求的最大值相当于求的最小值，所以上述目标函数等价于：

• 这样，我们的问题成为了一个凸优化问题，因为现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。这个问题可以用任何现成的 QP (Quadratic Programming) 的优化包进行求解，一言以蔽之：在一定的约束条件下，目标最优，损失最小。
  
• 进一步，虽然这个问题确实是一个标准的 QP 问题，但由于它的特殊结构，我们可以通过 Lagrange Duality 变换到对偶变量 (dual variable) 的优化问题，这样便可以找到一种更加有效的方法来进行求解，而且通常情况下这种方法比直接使用通用的 QP 优化包进行优化要高效得多。
  

　　换言之，除了用解决QP问题的常规方法之外，还可以通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。
　　那什么是Lagrange duality？简单地来说，通过给每一个约束条件加上一个 Lagrange multiplier(拉格朗日乘值)，即引入拉格朗日乘子，如此我们便可以通过拉格朗日函数将约束条件融和到目标函数里去(也就是说把条件融合到一个函数里头，现在只用一个函数表达式便能清楚的表达出我们的问题)：
　　然后我们令
　　容易验证：

• 当某个约束条件不满足时，例如，那么我们显然有（只要令即可）。
  
• 而当所有约束条件都满足时，则有，亦即我们最初要最小化的量。
  

　　因此，在要求约束条件得到满足的情况下最小化，实际上等价于直接最小化（当然，这里也有约束条件，就是≥0,i=1,…,n） ，因为如果约束条件没有得到满足，会等于无穷大，自然不会是我们所要求的最小值。
　　具体写出来，我们现在的目标函数变成了：
　　这里用表示这个问题的最优值，这个问题和我们最初的问题是等价的。不过，现在我们来把最小和最大的位置交换一下：
　　当然，交换以后的问题不再等价于原问题，这个新问题的最优值用来表示。并且，我们有≤ ，这在直观上也不难理解，最大值中最小的一个总也比最小值中最大的一个要大。总之，第二个问题的最优值在这里提供了一个第一个问题的最优值的一个下界，在满足某些条件的情况下，这两者相等，这个时候我们就可以通过求解第二个问题来间接地求解第一个问题。
　　也就是说，下面我们可以先求L 对w、b的极小，再求L 对的极大。而且，之所以从minmax的原始问题，转化为maxmin的对偶问题，一者因为是的近似解，二者，转化为对偶问题后，更容易求解。

2.1.2、KKT条件
　　与此同时，上段说“在满足某些条件的情况下”，这所谓的“满足某些条件”就是要满足KKT条件。那KKT条件的表现形式是什么呢？
　　据维基百科：KKT 条件的介绍，一般地，一个最优化数学模型能够表示成下列标准形式：
　　其中，f(x)是需要最小化的函数，h(x)是等式约束，g(x)是不等式约束，p和q分别为等式约束和不等式约束的数量。同时，我们得明白以下两个定理：

• 凸优化的概念：为一凸集， 为一凸函数。凸优化就是要找出一点 ，使得每一 满足 。
  
• KKT条件的意义：它是一个非线性规划（Nonlinear Programming）问题能有最优化解法的必要和充分条件。
  

　　而KKT条件就是指上面最优化数学模型的标准形式中的最小点 x* 必须满足下面的条件：
　　经过论证，我们这里的问题是满足 KKT 条件的（首先已经满足Slater condition，再者f和gi也都是可微的，即L对w和b都可导），因此现在我们便转化为求解第二个问题。
　　也就是说，现在，咱们的原问题通过满足一定的条件，已经转化成了对偶问题。而求解这个对偶学习问题，分为3个步骤，首先要让L(w，b，a) 关于 w 和 b 最小化，然后求对&alpha;的极大，最后利用SMO算法求解对偶因子。

2.1.3、对偶问题求解的3个步骤
　　1）、首先固定，要让 L 关于 w 和 b 最小化，我们分别对w，b求偏导数，即令 &part;L/&part;w 和 &part;L/&part;b 等于零（对w求导结果的解释请看本文评论下第45楼回复）：
　　以上结果代回上述的 L：
　　得到：
　　提醒：有读者可能会问上述推导过程如何而来？说实话，其具体推导过程是比较复杂的，如下图所示：
　　最后，得到：
　　如 jerrylead所说：“倒数第4步”推导到“倒数第3步”使用了线性代数的转置运算，由于ai和yi都是实数，因此转置后与自身一样。“倒数第3步”推导到“倒数第2步”使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法运算法则。最后一步是上一步的顺序调整。
　　L(
从上面的最后一个式子，我们可以看出，此时的拉格朗日函数只包含了一个变量，那就是，然后下文的第2步，求出了便能求出w，和b，由此可见，上文第1.2节提出来的核心问题：分类函数也就可以轻而易举的求出来了。
　　2）、求对的极大，即是关于对偶问题的最优化问题，从上面的式子得到：
　　(不得不提醒下读者：经过上面第一个步骤的求w和b，得到的拉格朗日函数式子已经没有了变量w，b，只有，而反过来，求得的将能导出w，b的解，最终得出分离超平面和分类决策函数。为何呢？因为如果求出了，根据，即可求出w。然后通过，即可求出b )
　　3）、如前面所说，这个问题有更加高效的优化算法，即我们常说的SMO算法。
　　####2.1.4、序列最小最优化SMO算法
细心的读者读至上节末尾处，怎么拉格朗日乘子的值可能依然心存疑惑。实际上，关于的求解可以用一种快速学习算法即SMO算法，这里先简要介绍下。
　　OK，当：
　　要解决的是在参数上求最大值W的问题，至于和都是已知数（其中 是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。和上文最后的式子对比一下，可以看到唯一的区别就是现在 dual variable 多了一个上限 C ，关于C的具体由来请查看下文第2.3节）。
　　要了解这个SMO算法是如何推导的，请跳到下文第3.5节、SMO算法。
　　到目前为止，我们的 SVM 还比较弱，只能处理线性的情况，下面我们将引入核函数，进而推广到非线性分类问题。

2.2、核函数Kernel

2.2.1、特征空间的隐式映射：核函数
　　在线性不可分的情况下，支持向量机通过某种事先选择的非线性映射(核函数)将输入变量映射到一个高维特征空间，在这个空间中构造最优分类超平面。我们使用SVM进行数据集分类工作的过程首先是同预先选定的一些非线性映射将输入空间映射到高维特征空间(下图很清晰的表达了通过映射到高维特征空间，而把平面上本身不好分的非线性数据分了开来)：
　　使得在高维属性空间中有可能最训练数据实现超平面的分割，避免了在原输入空间中进行非线性曲面分割计算，且在处理高维输入空间的分类时，这种方法尤其有效，其工作原理如下图所示：
　　而在我们遇到核函数之前，如果用原始的方法，那么在用线性学习器学习一个非线性关系，需要选择一个非线性特征集，并且将数据写成新的表达形式，这等价于应用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器，因此，考虑的假设集是这种类型的函数：
　　这里ϕ：X->F是从输入空间到某个特征空间的映射，这意味着建立非线性学习器分为两步：

• 首先使用一个非线性映射将数据变换到一个特征空间F，
  
• 然后在特征空间使用线性学习器分类。
  

　　这意味着假设可以表达为训练点的线性组合，因此决策规则可以用测试点和训练点的内积来表示：
　　如果有一种方式可以在特征空间中直接计算内积〈&phi;(xi · &phi;(x)〉，就像在原始输入点的函数中一样，就有可能将两个步骤融合到一起建立一个非线性的学习器，这样直接计算法的方法称为核函数方法，于是，核函数便横空出世了。
　　定义：核是一个函数K，对所有x，z(-X，满足，这里&phi;是从X到内积特征空间F的映射。

2.2.2、核函数：如何处理非线性数据
　　我们已经知道，如果是线性方法，所以对非线性的数据就没有办法处理。举个例子来说，则是如下图所示的两类数据，分别分布为两个圆圈的形状，这样的数据本身就是线性不可分的，此时咱们该如何把这两类数据分开呢？
　　此时，一个理想的分界应该是一个“圆圈”而不是一条线（超平面）。如果用 X1 和 X2 来表示这个二维平面的两个坐标的话，我们知道一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写作这样的形式：
　　如果我们构造另外一个五维的空间，其中五个坐标的值分别为 Z1=X1, Z2=X21, Z3=X2, Z4=X22, Z5=X1X2，那么显然，上面的方程在新的坐标系下可以写作：
　　关于新的坐标 Z ，这正是一个 hyper plane 的方程！也就是说，如果我们做一个映射 ϕ:R2→R5 ，将 X 按照上面的规则映射为 Z ，那么在新的空间中原来的数据将变成线性可分的，从而使用之前我们推导的线性分类算法就可以进行处理了。这正是 Kernel 方法处理非线性问题的基本思想。
　　再进一步描述 Kernel 的细节之前，不妨再来看看这个例子映射过后的直观例子。具体来说，我这里的超平面实际的方程是这个样子（圆心在 X2 轴上的一个正圆）：
　　因此我只需要把它映射到 Z1=X21, Z2=X22, Z3=X2 这样一个三维空间中即可，下图即是映射之后的结果，将坐标轴经过适当的旋转，就可以很明显地看出，数据是可以通过一个平面来分开的：
　　回忆一下，我们上一次2.1节中得到的最终的分类函数是这样的：
　　映射过后的空间是：
　　而其中的 &alpha; 也是通过求解如下 dual 问题而得到的：
　　这样一来问题就解决了吗？其实稍想一下就会发现有问题：在最初的例子里，我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到 19 维的新空间，这个数目是呈爆炸性增长的，这给 ϕ(&sdot;) 的计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算了。所以就需要 Kernel 出马了。
　　还是从最开始的简单例子出发，设两个向量和，而ϕ(&sdot;)即是到前面2.2.1节说的五维空间的映射，因此映射过后的内积为：
　　（公式说明：上面的这两个推导过程中，所说的前面的五维空间的映射，这里说的前面便是文中2.2.1节的所述的映射方式，仔细看下2.2.1节的映射规则，再看那第一个推导，其实就是计算x1，x2各自的内积，然后相乘相加即可，第二个推导则是直接平方，去掉括号，也很容易推出来）
　　另外，我们又注意到：
　　二者有很多相似的地方，实际上，我们只要把某几个维度线性缩放一下，然后再加上一个常数维度，具体来说，上面这个式子的计算结果实际上和映射
　　之后的内积的结果是相等的，那么区别在于什么地方呢？
　　一个是映射到高维空间中，然后再根据内积的公式进行计算；
而另一个则直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果。
（公式说明：上面之中，最后的两个式子，第一个算式，是带内积的完全平方式，可以拆开，然后，通过凑一个得到，第二个算式，也是根据第一个算式凑出来的）
　　回忆刚才提到的映射的维度爆炸，在前一种方法已经无法计算的情况下，后一种方法却依旧能从容处理，甚至是无穷维度的情况也没有问题。
　　我们把这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数 (Kernel Function) ，例如，在刚才的例子中，我们的核函数为：
　　核函数能简化映射空间中的内积运算——刚好“碰巧”的是，在我们的 SVM 里需要计算的地方数据向量总是以内积的形式出现的。对比刚才我们上面写出来的式子，现在我们的分类函数为：
　　其中 由如下 dual 问题计算而得：
　　这样一来计算的问题就算解决了，避开了直接在高维空间中进行计算，而结果却是等价的。

2.3、使用松弛变量处理 outliers 方法
　　在本文第一节最开始讨论支持向量机的时候，我们就假定，数据是线性可分的，亦即我们可以找到一个可行的超平面将数据完全分开。后来为了处理非线性数据，在上文2.2节使用 Kernel 方法对原来的线性 SVM 进行了推广，使得非线性的的情况也能处理。虽然通过映射 ϕ(&sdot;) 将原始数据映射到高维空间之后，能够线性分隔的概率大大增加，但是对于某些情况还是很难处理。
　　例如可能并不是因为数据本身是非线性结构的，而只是因为数据有噪音。对于这种偏离正常位置很远的数据点，我们称之为 outlier ，在我们原来的 SVM 模型里，outlier 的存在有可能造成很大的影响，因为超平面本身就是只有少数几个 support vector 组成的，如果这些 support vector 里又存在 outlier 的话，其影响就很大了。例如下图：
　　用黑圈圈起来的那个蓝点是一个 outlier ，它偏离了自己原本所应该在的那个半空间，如果直接忽略掉它的话，原来的分隔超平面还是挺好的，但是由于这个 outlier 的出现，导致分隔超平面不得不被挤歪了，变成途中黑色虚线所示（这只是一个示意图，并没有严格计算精确坐标），同时 margin 也相应变小了。当然，更严重的情况是，如果这个 outlier 再往右上移动一些距离的话，我们将无法构造出能将数据分开的超平面来。
　　为了处理这种情况，SVM 允许数据点在一定程度上偏离一下超平面。例如上图中，黑色实线所对应的距离，就是该 outlier 偏离的距离，如果把它移动回来，就刚好落在原来的超平面上，而不会使得超平面发生变形了。
　　我们原来的约束条件为：
　　现在考虑到outlier问题，约束条件变成了：
　　其中称为松弛变量 (slack variable) ，对应数据点允许偏离的 functional margin 的量。当然，如果我们运行任意大的话，那任意的超平面都是符合条件的了。所以，我们在原来的目标函数后面加上一项，使得这些的总和也要最小：
　　其中 C 是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。注意，其中 是需要优化的变量（之一），而 C 是一个事先确定好的常量。完整地写出来是这个样子：
　　用之前的方法将限制或约束条件加入到目标函数中，得到新的拉格朗日函数，如下所示：
　　分析方法和前面一样，转换为另一个问题之后，我们先让针对w、b和最小化：
　　将 w 带回 并化简，得到和原来一样的目标函数：
　　不过，由于我们得到而又有ri >= 0（作为 Lagrange multiplier 的条件），因此有，所以整个 dual 问题现在写作：
　　把前后的结果对比一下（错误修正：图中的Dual formulation中的Minimize应为maxmize）：
　　可以看到唯一的区别就是现在 dual variable 多了一个上限 C 。而 Kernel 化的非线性形式也是一样的，只要把换成即可。这样一来，一个完整的，可以处理线性和非线性并能容忍噪音和 outliers 的支持向量机才终于介绍完毕了。
　　行文至此，可以做个小结，不准确的说，SVM它本质上即是一个分类方法，用w^T+b定义分类函数，于是求w、b，为寻最大间隔，引出1/2||w||^2，继而引入拉格朗日因子，化为对拉格朗日乘子a的求解（求解过程中会涉及到一系列最优化或凸二次规划等问题），如此，求w.b与求a等价，而a的求解可以用一种快速学习算法SMO，至于核函数，是为处理非线性情况，若直接映射到高维计算恐维度爆炸，故在低维计算，等效高维表现。

第三层、扩展SVM

3.1、损失函数
　　在本文1.0节有这么一句话“支持向量机(SVM)是90年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。”但初次看到的读者可能并不了解什么是结构化风险，什么又是经验风险。要了解这两个所谓的“风险”，还得又从监督学习说起。
　　监督学习实际上就是一个经验风险或者结构风险函数的最优化问题。风险函数度量平均意义下模型预测的好坏，模型每一次预测的好坏用损失函数来度量。它从假设空间F中选择模型f作为决策函数，对于给定的输入X，由f(X)给出相应的输出Y，这个输出的预测值f(X)与真实值Y可能一致也可能不一致，用一个损失函数来度量预测错误的程度。损失函数记为L(Y, f(X))。
　　常用的损失函数有以下几种（基本引用自《统计学习方法》）：
　　如此，SVM有第二种理解，即最优化+损失最小，或如@夏粉_百度所说“可从损失函数和优化算法角度看SVM，boosting，LR等算法，可能会有不同收获”。
　　关于损失函数，还可以看看张潼的这篇《Statistical behavior and consistency of classification methods based on convex risk minimization》。各种算法中常用的损失函数基本都具有fisher一致性，优化这些损失函数得到的分类器可以看作是后验概率的“代理”。
　　此外，他还有另外一篇论文《Statistical analysis of some multi-category large margin classification methods》，在多分类情况下margin loss的分析，这两篇对Boosting和SVM使用的损失函数分析的很透彻。

3.2、SMO算法
　　在上文2.1.2节中，我们提到了求解对偶问题的序列最小最优化SMO算法，但并未提到其具体解法。
　　事实上，SMO算法是由Microsoft Research的John C. Platt在1998年发表的一篇论文《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》中提出，它很快成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。
　　接下来，咱们便参考John C. Platt的这篇文章来看看SMO的解法是怎样的。

3.2.1、SMO算法的解法
　　咱们首先来定义特征到结果的输出函数为
　　再三强调，这个u与我们之前定义的实质是一样的。
　　接着，咱们重新定义咱们原始的优化问题，权当重新回顾，如下：
　　求导得到：
　　代入中，可得。
　　引入对偶因子后，得：
　　s.t：且
　　注：这里得到的min函数与我们之前的max函数实质也是一样，因为把符号变下，即有min转化为max的问题，且yi也与之前的等价，yj亦如此。
　　经过加入松弛变量后，模型修改为：
　　从而最终我们的问题变为：
　　继而，根据KKT条件可以得出其中取值的意义为：
　　这里的还是拉格朗日乘子(问题通过拉格朗日乘法数来求解)

• 　　对于第1种情况，表明是正常分类，在边界内部（我们知道正确分类的点yi*f(xi)>=0）；
  
  
• 　　对于第2种情况，表明了是支持向量，在边界上；
  
  
• 　　对于第3种情况，表明了是在两条边界之间；
  
  

　　而最优解需要满足KKT条件，即上述3个条件都得满足，以下几种情况出现将会出现不满足：
　　<=1但是<C则是不满足的,而原本=C
　　>=1但是>0则是不满足的而原本=0
　　=1但是=0或者=C则表明不满足的，而原本应该是0<<C
　　所以要找出不满足KKT条件的这些ai，并更新这些ai，但这些ai又受到另外一个约束，即
　　注：别忘了2.1.1节中，L对a、b求偏导，得到：
　　因此，我们通过另一个方法，即同时更新ai和aj，要求满足以下等式：
　　就能保证和为0的约束。
　　利用yiai+yjaj=常数，消去ai，可得到一个关于单变量aj的一个凸二次规划问题，不考虑其约束0<=aj<=C,可以得其解为：
　　这里，，表示旧值。
　　然后考虑约束0<=aj<=C可得到a的解析解为：
　　把SMO中对于两个参数求解过程看成线性规划来理解来理解的话，那么下图所表达的便是约束条件：
　　根据yi和yj同号或异号，可得出两个拉格朗日乘子的上下界分别为：
　　对于。
　　那么如何求得ai和aj呢？

• 对于ai，即第一个乘子，可以通过刚刚说的那3种不满足KKT的条件来找；
  
• 而对于第二个乘子aj可以找满足条件 ：求得。
  

　　而b的更新则是：
　　在满足下述条件：
　　下更新b，且每次更新完两个乘子的优化后，都需要再重新计算b，及对应的Ei值。
最后更新所有ai，y和b，这样模型就出来了，从而即可求出咱们开头提出的分类函数
　　此外，这里也有一篇类似的文章，大家可以参考下。

3.2.2、SMO算法的步骤
　　这样，SMO的主要步骤如下：
　　意思是，
　　第一步选取一对ai和aj，选取方法使用启发式方法；
　　第二步，固定除ai和aj之外的其他参数，确定W极值条件下的ai，由aj表示ai。
　　假定在某一次迭代中，需要更新，对应的拉格朗日乘子，，那么这个小规模的二次规划问题写为：
　　那么在每次迭代中，如何更新乘子呢？引用这里的两张PPT说明下：
　　知道了如何更新乘子，那么选取哪些乘子进行更新呢？具体选择方法有以下两个步骤：

• 　　步骤1：先“扫描”所有乘子，把第一个违反KKT条件的作为更新对象，令为a2；
  
  
• 　　步骤2：在所有不违反KKT条件的乘子中，选择使|E1 &minus;E2|最大的a1（注：别忘了，其中，而，求出来的E代表函数ui对输入xi的预测值与真实输出类标记yi之差）。
  
  

　　值得一提的是，每次更新完两个乘子的优化后，都需要再重新计算b，及对应的Ei值。
　　与此同时，乘子的选择务必遵循两个原则：

• 使乘子能满足KKT条件
  
• 对一个满足KKT条件的乘子进行更新，应能最大限度增大目标函数的值（类似于梯度下降）
  

　　综上，SMO算法的基本思想是将Vapnik在1982年提出的Chunking方法推到极致，SMO算法每次迭代只选出两个分量ai和aj进行调整，其它分量则保持固定不变，在得到解ai和aj之后，再用ai和aj改进其它分量。与通常的分解算法比较，尽管它可能需要更多的迭代次数，但每次迭代的计算量比较小，所以该算法表现出整理的快速收敛性，且不需要存储核矩阵，也没有矩阵运算。

3.5.3、SMO算法的实现
　　行文至此，我相信，SVM理解到了一定程度后，是的确能在脑海里从头至尾推导出相关公式的，最初分类函数，最大化分类间隔，max1/||w||，min1/2||w||^2，凸二次规划，拉格朗日函数，转化为对偶问题，SMO算法，都为寻找一个最优解，一个最优分类平面。一步步梳理下来，为什么这样那样，太多东西可以追究，最后实现。如下图所示：
　　至于下文中将阐述的核函数则为是为了更好的处理非线性可分的情况，而松弛变量则是为了纠正或约束少量“不安分”或脱离集体不好归类的因子。
　　台湾的林智仁教授写了一个封装SVM算法的libsvm库，大家可以看看，此外这里还有一份libsvm的注释文档。
　　除了在这篇论文《fast training of support vector machines using sequential minimal optimization》中platt给出了SMO算法的逻辑代码之外，这里也有一份SMO的实现代码，大家可以看下。

读者评论
　　本文发表后，微博上的很多朋友给了不少意见，以下是节选的一些精彩评论：

• 　　“压力”陡增的评论→//@藏了个锋：我是看着July大神的博文长大的啊//@zlkysl：就是看了最后那一篇才决定自己的研究方向为SVM的。--http://weibo.com/1580904460/zraWk0u6u?mod=weibotime。
  
  
• 　　@张金辉：“SVM的三重境界，不得不转的一篇。其实Coursera的课堂上Andrew Ng讲过支持向量机，但显然他没有把这作为重点，加上Ng讲支持向量机的方法我一时半会难以完全消化，所以听的也是一知半解。真正开始了解支持向量机就是看的这篇“三重境界”，之后才对这个算法有了大概的概念，以至如何去使用，再到其中的原理为何，再到支持向量机的证明等。总之，这篇文章开启了我长达数月的研究支持向量机阶段，直到今日。”--http://zhan.renren.com/profile/249335584?from=template#!//tag/三重境界。
  
  
• 　　@孤独之守望者：“最后，推出svm的cost function 是hinge loss，然后对比其他的方法的cost function，说明其实他们的目标函数很像，那么问题是svm为什么这么popular呢？您可以再加些VC dimension跟一些error bound的数学，点一下，提供一个思路和方向”。--http://weibo.com/1580904460/AiohoyDwq?mod=weibotime。
  
  
• 　　@夏粉_百度：“在面试时，考察SVM可考察机器学习各方面能力：目标函数,优化过程,并行方法，算法收敛性,样本复杂度，适用场景,调参经验，不过个人认为考察boosting和LR也还不错啊。此外，随着统计机器学习不断进步，SVM只被当成使用了一个替代01损失hinge研究，更通用的方法被提出，损失函数研究替代损失与贝叶斯损失关系，算法稳定性研究替代损失与推广性能关系,凸优化研究如何求解凸目标函数，SVM,boosting等算法只是这些通用方法的一个具体组建而已。”
  
  
• 　　@居里猴姐：关于SVM损失函数的问题，可以看看张潼老师的这篇《Statistical behavior and consistency of classification methods based on convex risk minimization》。各种算法中常用的损失函数基本都具有fisher一致性，优化这些损失函数得到的分类器可以看作是后验概率的“代理”。此外，张潼老师还有另外一篇论文《Statistical analysis of some multi-category large margin classification methods》，在多分类情况下margin loss的分析，这两篇对Boosting和SVM使用的损失函数分析的很透彻。
  
  
• 　　@夏粉_百度：SVM用了hinge损失，hinge损失不可导，不如其它替代损失方便优化并且转换概率麻烦。核函数也不太用，现在是大数据时代，样本非常大，无法想象一个n^2的核矩阵如何存储和计算。 而且，现在现在非线性一般靠深度学习了。//@Copper_PKU:请教svm在工业界的应用典型的有哪些？工业界如何选取核函数，经验的方法？svm的训练过程如何优化？
  
  
• 　　@Copper_PKU：July的svm tutorial 我个人觉得还可以加入和修改如下部分：(1) 对于支持向量解释，可以结合图和拉格朗日参数来表达，松弛中sv没有写出来. (2) SMO算法部分，加入Joachims论文中提到的算法，以及SMO算法选取workset的方法，包括SMO算法的收敛判断，还有之前共轭梯度求解方法，虽然是较早的算法，但是对于理解SMO算法有很好的效果。模型的优化和求解都是迭代的过程，加入历史算法增强立体感。--http://weibo.com/1580904460/Akw6dl3Yk#_rnd1385474436177。
  
  
• 　　//@廖临川: 之所以sgd对大训练集的效果更好，1.因为SGD优化每次迭代使用样本子集，比使用训练全集（尤其是百万数量级）要快得多；2.如果目标函数是凸的或者伪凸的，SGD几乎必然可以收敛到全局最优；否则，则收敛到局部最优；3.SGD一般不需要收敛到全局最优，只要得到足够好的解，就可以立即停止。//@Copper_PKU：sgd的核心思想：是迭代训练，每拿到一个样本就算出基于当前w(t) 的loss function，t代表训练第t次，然后进行下一w（t+1）的更新，w(t+1)=w(t)-(learning rate) * loss function的梯度，这个类比神经网络中bp中的参数训练方法。 sample by sample就是每次仅处理一个样本 而不是一个batch。
  
  
• 　　//@Copper_PKU：从损失函数角度说：primal问题可以理解为正则化项+lossfunction，求解目标是在两个中间取平衡 如果强调loss function最小则会overfitting，所以有C参数。 //@研究者July：SVM还真就是在一定限定条件下，即约束条件下求目标函数的最优值问题，同时，为减少误判率，尽量让损失最小。
  
  
• 　　…
  
  

参考文献及推荐阅读

• 《支持向量机导论》，[美] Nello Cristianini / John Shawe-Taylor 著；
  
• 支持向量机导论一书的支持网站：http://www.support-vector.net/；
  
• 《数据挖掘导论》，[美] Pang-Ning Tan / Michael Steinbach / Vipin Kumar 著；
  
• 《数据挖掘：概念与技术》，(加)Jiawei Han;Micheline Kamber 著；
  
• 《数据挖掘中的新方法：支持向量机》，邓乃扬 田英杰 著；
  
• 《支持向量机–理论、算法和扩展》，邓乃扬 田英杰 著；
  
• 支持向量机系列，pluskid：http://blog.pluskid.org/?page_id=683；
  
• http://www.360doc.com/content/07/0716/23/11966_615252.shtml；
  
• 数据挖掘十大经典算法初探；
  
• 《模式识别支持向量机指南》，C.J.C Burges 著；
  
• 《统计学习方法》，李航著(第7章有不少内容参考自支持向量机导论一书，不过，可以翻翻看看)；
  
• 《统计自然语言处理》，宗成庆编著，第十二章、文本分类；
  
• SVM入门系列，Jasper：http://www.blogjava.net/zhenandaci/category/31868.html；
  
• 最近邻决策和SVM数字识别的实现和比较，作者不详；
  
• 斯坦福大学机器学习课程原始讲义：http://www.cnblogs.com/jerrylead/archive/2012/05/08/2489725.html；
  
• 斯坦福机器学习课程笔记：http://www.cnblogs.com/jerrylead/tag/Machine Learning/；
  
• http://www.cnblogs.com/jerrylead/archive/2011/03/13/1982639.html；
  
• SMO算法的数学推导：http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html；
  
• 数据挖掘掘中所需的概率论与数理统计知识、上；
  
• 关于机器学习方面的文章，可以读读：http://www.cnblogs.com/vivounicorn/category/289453.html；
  
• 数学系教材推荐：http://blog.sina.com.cn/s/blog_5e638d950100dswh.html；
  
• 《神经网络与机器学习(原书第三版)》，[加] Simon Haykin 著；
  
• 正态分布的前世今生：http://t.cn/zlH3Ygc；
  
• 《数理统计学简史》，陈希孺院士著；
  
• 《最优化理论与算法(第2版)》，陈宝林编著；
  
• A Gentle Introduction to Support Vector Machines in Biomedicine：http://www.nyuinformatics.org/downloads/supplements/SVM_Tutorial_2010/Final_WB.pdf，此PPT很赞，除了对引入拉格朗日对偶变量后的凸二次规划问题的深入度不够之外，其它都挺好，配图很精彩，本文有几张图便引自此PPT中；
  
• 来自卡内基梅隆大学carnegie mellon university(CMU)的讲解SVM的PPT：http://www.autonlab.org/tutorials/svm15.pdf；
  
• 发明libsvm的台湾林智仁教授06年的机器学习讲义SVM：http://wenku.baidu.com/link?url=PWTGMYNb4HGUrUQUZwTH2B4r8pIMgLMiWIK1ymVORrds_11VOkHwp-JWab7IALDiors64JW_6mD93dtuWHwFWxsAk6p0rzchR8Qh5_4jWHC；
  
• http://staff.ustc.edu.cn/~ketang/PPT/PRLec5.pdf；
  
• Introduction to Support Vector Machines (SVM)，By Debprakash Patnai M.E (SSA)，https://www.google.com.hk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CCwQFjAA&url=http%3A%2F%2Fwww.pws.stu.edu.tw%2Fccfang%2Findex.files%2FAI%2FAI%26ML-Support%20Vector%20Machine-1.ppt&ei=JRR6UqT5C-iyiQfWyIDgCg&usg=AFQjCNGw1fTbpH4ltQjjmx1d25ZqbCN9nA；
  
• 多人推荐过的libsvm：http://www.csie.ntu.edu.tw/~cjlin/libsvm/；
  
• 《machine learning in action》，中文版为《机器学习实战》；
  
• SMO算法的提出：Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines：http://research.microsoft.com/en-us/um/people/jplatt/smoTR.pdf；
  
• 《统计学习理论的本质》，[美] Vladimir N. Vapnik著，非常晦涩，不做过多推荐；
  
• 张兆翔，机器学习第五讲之支持向量机http://irip.buaa.edu.cn/~zxzhang/courses/MachineLearning/5.pdf；
  
• VC维的理论解释：http://www.svms.org/vc-dimension/，中文VC维解释http://xiaoxia001.iteye.com/blog/1163338；
  
• 来自NEC Labs America的Jason Weston关于SVM的讲义http://www.cs.columbia.edu/~kathy/cs4701/documents/jason_svm_tutorial.pdf；
  
• 来自MIT的SVM讲义：http://www.mit.edu/~9.520/spring11/slides/class06-svm.pdf；
  
• PAC问题：http://www.cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf；
  
• 百度张潼老师的两篇论文：《Statistical behavior and consistency of classification methods based on convex risk minimization》http://home.olemiss.edu/~xdang/676/Consistency_of_Classification_Convex_Risk_Minimization.pdf，《Statistical analysis of some multi-category large margin classification methods》；
  
• http://jacoxu.com/?p=39；
  
• 《矩阵分析与应用》，清华张贤达著；
  
• SMO算法的实现：http://blog.csdn.net/techq/article/details/6171688；
  
• 常见面试之机器学习算法思想简单梳理：http://www.cnblogs.com/tornadomeet/p/3395593.html；
  
• 矩阵的wikipedia页面：http://zh.wikipedia.org/wiki/矩阵；
  
• 最小二乘法及其实现：http://blog.csdn.net/qll125596718/article/details/8248249；
  
• 统计学习方法概论：http://blog.csdn.net/qll125596718/article/details/8351337；
  
• http://www.csdn.net/article/2012-12-28/2813275-Support-Vector-Machine；
  
• A Tutorial on Support Vector Regression：http://alex.smola.org/papers/2003/SmoSch03b.pdf；SVR简明版：http://www.cmlab.csie.ntu.edu.tw/~cyy/learning/tutorials/SVR.pdf。
  
• SVM Org：http://www.support-vector-machines.org/；
  
• R. Collobert. Large Scale Machine Learning. Universit&eacute; Paris VI phd thesis. 2004：http://ronan.collobert.com/pub/matos/2004_phdthesis_lip6.pdf；
  
• Making Large-Scale SVM Learning Practical：http://www.cs.cornell.edu/people/tj/publications/joachims_99a.pdf；
  
• 文本分类与SVM：http://blog.csdn.net/zhzhl202/article/details/8197109；
  
• Working Set Selection Using Second Order Information
  for Training Support Vector Machines：http://www.csie.ntu.edu.tw/~cjlin/papers/quadworkset.pdf；
  
• SVM Optimization: Inverse Dependence on Training Set Size：http://icml2008.cs.helsinki.fi/papers/266.pdf；
  
• Large-Scale Support Vector Machines: Algorithms and Theory：http://cseweb.ucsd.edu/~akmenon/ResearchExam.pdf；
  
• 凸优化的概念：http://cs229.stanford.edu/section/cs229-cvxopt.pdf；
  
• 《凸优化》，作者: Stephen Boyd / Lieven Vandenberghe，原作名: Convex Optimization；
  
• Large-scale Non-linear Classification: Algorithms and Evaluations，Zhuang Wang，讲了很多SVM算法的新进展：http://ijcai13.org/files/tutorial_slides/te2.pdf；
  

附录 更多题型

附录A 语言基础
　　1、C++中虚拟函数的实现机制。
　　2、指针数组和数组指针的区别。
　　3、malloc-free和new-delete的区别。
　　4、sizeof和strlen的区别。
　　5、描述函数调用的整个过程。
　　6、C++ STL里面的vector的实现机制，

• 当调用push_back成员函数时，怎么实现？
  
• 内存足则直接 placement new构造对象，否则扩充内存，转移对象，新对象placement new上去。
  
• 当调用clear成员函数时，做什么操作，如果要释放内存该怎么做。
  
• 调用析构函数，内存不释放。 clear没有释放内存，只是将数组中的元素置为空了，释放内存需要delete。
  

附录B 概率统计
　　1
　　已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10。
　　分析：这题主要考的是对概率的理解。程序关键是要算出rand10，1到10，十个数字出现的考虑都为10%.根据排列组合，连续算两次rand7出现的组合数是7*7=49，这49种组合每一种出现考虑是相同的。怎么从49平均概率的转换为1到10呢？方法是：

• 1.rand7执行两次，出来的数为a1=rand7()-1，a2=rand7()-1.
  
• 2.如果a17+a2<40,b=(a17+a2)/4+1；如果a1*7+a2>=40,重复第一步。参考代码如下所示：
  

int rand7()
{
return rand() % 7 + 1;
}
int rand10()
{
int a71, a72, a10;
do
{
a71 = rand7() - 1;
a72 = rand7() - 1;
a10 = a71 * 7 + a72;
} while (a10 >= 40);
return (a71 * 7 + a72) / 4 + 1;
}

　　2
　　给你5个球，每个球被抽到的可能性为30、50、20、40、10，设计一个随机算法，该算法的输出结果为本次执行的结果。输出A，B，C，D，E即可。
　　3
　　2D平面上有一个三角形ABC，如何从这个三角形内部随机取一个点，且使得在三角形内部任何点被选取的概率相同。
　　4
　　英雄升级，

• 从0级升到1级，概率100%。
  
• 从1级升到2级，有1/3的可能成功；1/3的可能停留原级；1/3的可能下降到0级；
  
• 从2级升到3级，有1/9的可能成功；4/9的可能停留原级；4/9的可能下降到1级。
  

　　每次升级要花费一个宝石，不管成功还是停留还是降级。求英雄从0级升到3级平均花费的宝石数目。
　　提示：从第n级升级到第n+1级成功的概率是(1/3)^n（指数），停留原级和降级的概率一样，都为[1-(1/3)^n]/2）。
　　5
　　甲包8个红球 2个蓝球，乙包2个红球 8个蓝球。抛硬币决定从哪个包取球，取了11次，7红4蓝。注，每次取后还放进去，只抛一次硬币。问选的是甲包的概率？
　　提示：贝叶斯公式 + 全概率公式作答。
　　6
　　一个桶里面有白球、黑球各100个，现在按下述规则取球：

• i 、每次从通里面拿出来两个球；
  
• ii、如果取出的是两个同色的求，就再放入一个黑球；
  
• ii、如果取出的是两个异色的求，就再放入一个白球。
  问：最后桶里面只剩下一个黑球的概率是多少？
  

　　7
　　一个文件中含有n个元素，只能遍历一遍，要求等概率随机取出其中之一。
　　提示：5个人抽5个签，只有一个签意味着“中签”，轮流抽签，5个人中签的概率一样大，皆为1/5，也就是说，抽签先后顺序不影响公平性。


附录C 智力逻辑
　　1
　　五个海盗抢到了100颗宝石，每一颗都一样大小和价值连城。他们决定这么分： 抽签决定自己的号码（1、2、3、4、5）
　　首先，由1号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔进大海喂鲨鱼
　　如果1号死后，再由2号提出分配方案，然后剩下的4人进行表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼，依此类推。
　　条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。
　　问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？
　　2
　　用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平，最多可以从y个小球中找出较轻的那个，求y与x的关系式。
　　3
　　有12个小球,外形相同,其中一个小球的质量与其他11个不同，给一个天平,问如何用3次把这个小球找出来，并且求出这个小球是比其他的轻还是重。
　　4
　　13个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球?
　　5
　　有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。
　　6
　　有8瓶水，其中有一瓶有毒，最少尝试几次可以找出来。
　　7
　　五只猴子分桃。半夜，第一只猴子先起来，它把桃分成了相等的五堆，多出一只。于是，它吃掉了一个，拿走了一堆； 第二只猴子起来一看，只有四堆桃。于是把四堆合在一起，分成相等的五堆，又多出一个。于是，它也吃掉了一个，拿走了一堆；…其他几只猴子也都是这样分的。问：这堆桃至少有多少个？
　　分析：先给这堆桃子加上4个，设此时共有X个桃子，最后剩下a个桃子：

• 第一只猴子分完后还剩:(1-1/5)X=(4/5)X;
  
• 第二只猴子分完后还剩:(1-1/5)2X;
  
• 第三只猴子分完后还剩:(1-1/5)3X;
  
• 第四只猴子分完后还剩:(1-1/5)4X;
  
• 第五只猴子分完后还剩:(1-1/5)5X=(1024/3125)X;
  

　　得：a=(1024/3125)X；要使a为整数，X最小取3125，减去加上的4个，所以，这堆桃子最少有3121个。
　　8
　　我们有很多瓶无色的液体，其中有一瓶是毒药，其它都是蒸馏水，实验的小白鼠喝了以后会在5分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠，请问一下，我们用这五只小白鼠，5分钟的时间，能够检测多少瓶液体的成分？
　　9
　　25匹赛马，5个跑道，也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的5匹马。
　　10
　　宿舍内5个同学一起玩对战游戏。每场比赛有一些人作为红方，另一些人作为蓝方。请问至少需要多少场比赛，才能使任意两个人之间有一场红方对蓝方和蓝方对红方的比赛？

　　提示：答案为4场。
　　11、单词博弈
　　甲乙两个人用一个英语单词玩游戏。两个人轮流进行，每个人每次从中删掉任意一个字母，如果剩余的字母序列是严格单调递增的（按字典序a < b < c <…<z)，则这个人胜利。两个人都足够聪明（即如果有赢的方案，都不会选输的方案 ），甲先开始，问他能赢么？
　　例如: 输入 bad， 则甲可以删掉b或者a,剩余的是ad或者bd，他就赢了，输出1。
又如: 输入 aaa， 则甲只能删掉1个a，乙删掉一个a,剩余1个a，乙获胜，输出0。


附录D 系统设计
　　1、搜索关键词智能提示suggestion
　　百度搜索框中，输入“北京”，搜索框下面会以北京为前缀，展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词，输入“结构之”，会提示“结构之法”，“结构之法 算法之道”等搜索词。
请问，如何设计此系统，使得空间和时间复杂度尽量低。
　　提示：此题比较开放，简单直接的方法是：用trie树存储大量字符串，当前缀固定时，存储相对来说比较热的后缀。然后用hashmap+堆，统计出如10个近似的热词，也就是说，只存与关键词近似的比如10个热词，我们把这个统计热词的方法称为TOP K算法。
　　当然，在实际中，还有很多细节需要考虑，有兴趣的读者可以继续参阅相关资料。
　　2
　　某服务器流量统计器，每天有1000亿的访问记录数据，包括时间、URL、IP。设计系统实现记录数据的保存、管理、查询。要求能实现以下功能：

• 计算在某一时间段（精确到分）时间内的，某URL的所有访问量。
  
• 计算在某一时间段（精确到分）时间内的，某IP的所有访问量。
  

　　3
　　假设某个网站每天有超过10亿次的页面访问量，出于安全考虑，网站会记录访问客户端访问的IP地址和对应的时间，如果现在已经记录了1000亿条数据，想统计一个指定时间段内的区域IP地址访问量，那么这些数据应该按照何种方式来组织，才能尽快满足上面的统计需求呢？
设计完方案后，并指出该方案的优缺点，比如在什么情况下，可能会非常慢？


提示：用B+树来组织，非叶子节点存储（某个时间点，页面访问量），叶子节点是访问的IP地址。这个方案的优点是查询某个时间段内的IP访问量很快，但是要统计某个IP的访问次数或是上次访问时间就不得不遍历整个树的叶子节点。或者可以建立二级索引，分别是时间和地点来建立索引。
　　4
　　给你10台机器，每个机器2个CPU和2GB内存，现在已知在10亿条记录的数据库里执行一次查询需要5秒，问用什么方法能让90%的查询能在100毫秒以内返回结果。
　　提示：将10亿条记录排序，然后分到10个机器中，分的时候是一个记录一个记录的轮流分，确保每个机器记录大小分布差不多，每一次查询时，同时提交给10台机器，同时查询，因为记录已排序，可以采用二分法查询。
　　如果无排序，只能顺序查询，那就要看记录本身的概率分布，否则不可能实现。毕竟一个机器2个CPU未必能起到作用，要看这两个CPU能否并行存取内存，取决于系统架构。
　　5
　　有1000万条URL，每条URL长度为50字节，只包含主机前缀，要求实现URL提示系统，并满足以下条件：

• 实时更新匹配用户输入的地址，每输出一个字符，输出最新匹配URL
  
• 每次只匹配主机前缀，例如对www.abaidu.com和www.baidu.com，用户输入www.b时只提示www.baidu.com
  
• 每次提供10条匹配的URL
  

　　6
　　例如手机朋友网有n个服务器，为了方便用户的访问会在服务器上缓存数据，因此用户每次访问的时候最好能保持同一台服务器。
已有的做法是根据ServerIPIndex[QQNUM%n]得到请求的服务器，这种方法很方便将用户分到不同的服务器上去。但是如果一台服务器死掉了，那么n就变为了n-1，那么ServerIPIndex[QQNUM%n]与ServerIPIndex[QQNUM%(n-1)]基本上都不一样了，所以大多数用户的请求都会转到其他服务器，这样会发生大量访问错误。
　　问： 如何改进或者换一种方法，使得：

• 一台服务器死掉后，不会造成大面积的访问错误，
  
• 原有的访问基本还是停留在同一台服务器上；
  
• 尽量考虑负载均衡。
  

　　提示：一致性hash算法。
　　7
　　对于给定的整数集合S，求出最大的d，使得a+b+c=d。a,b,c,d互不相同，且都属于S。集合的元素个数小于等于2000个，元素的取值范围在[-2^28，2^28 - 1]，假定可用内存空间为100MB，硬盘使用空间无限大，试分析时间和空间复杂度，找出最快的解决方法。
　　有一大批数据，百万级别的。数据项内容是：用户ID、科目ABC各自的成绩。其中用户ID为0~1000万之间，且是连续的，可以唯一标识一条记录。科目ABC成绩均在0~100之间。有两块磁盘，空间大小均为512MB，内存空间64MB。

• 为实现快速查询某用户ID对应的各科成绩，问磁盘文件及内存该如何组织；
  
• 改变题目条件，ID为0~10亿之间，且不连续。问磁盘文件及内存该如何组织；
  
• 在问题2的基础上，增加一个需求。在查询各科成绩的同时，获取该用户的排名，问磁盘文件及内存该如何组织。
  

　　8
　　有几百亿的整数，分布的存储到几百台通过网络连接的计算机上，你能否开发出一个算法和系统，找出这几百亿数据的中值？就是在一组排序好的数据中居于中间的数。显然，一台机器是装不下所有的数据。也尽量少用网络带宽。
　　9
　　类似做一个手机键盘，上面有1到9个数字，每个数字都代表几个字母（比如1代表abc三个字母，z代表wxyz等等），现在要求设计当输入某几个数字的组合时，查找出通讯录中的人名及电话号码。
　　10
　　这是一种用户登录验证手段，例如银行登录系统，这个设备显示6位数字，每60秒变一次，再经过服务器认证，通过则允许登录。问How to design this system？

• 系统设计思路？服务器端为何能有效认证动态密码的正确性？
  
• 如果是千万量级永固，给出系统设计图示或说明，要求子功能模块划分清晰，给出关键的数据结构或数据库表结构。
  考虑用户量级的影响和扩展性，用户密码的随机性等，如果设计系统以支持这几个因素.
  
• 系统算法升级时，服务器端和设备端可能都要有所修改，如何设计系统，能够使得升级过程（包括可能的设备替换或重设）尽量平滑？
  

　　11
　　http服务器会在用户访问某一个文件的时候，记录下该文件被访问的日志，网站管理员都会去统计每天每文件被访问的次数。写一个小程序，来遍历整个日志 文件，计算出每个文件被访问的访问次数。

• 请问这个管理员设计这个算法
  
• 该网站管理员后来加入腾讯从事运维工作，在腾讯，单台http服务器不够用的，同样的内容，会分布在全国各地上百台服务器上。每台服务器上的日志数量， 都是之前的10倍之多，每天服务器的性能更好，之前他用的是单核cpu，现在用的是8核的，管理员发现在这种的海量的分布式服务器，基本没法使用了，请重新设计一个算法。
  

　　12
　　一在线推送服务，同时为10万个用户提供服务，对于每个用户服务从10万首歌的曲库中为他们随机选择一首，同一用户不能推送重复的，设计方案，内存尽可能小，写出数据结构与算法。
　　13
　　每个城市的IP段是固定的，新来一个IP，找出它是哪个城市的，设计一个后台系统。
　　14
　　请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在队列中所处的位置和变化，队伍可能随时有人加入和退出；当有人退出影响到用户的位置排名时需要及时反馈到用户。
　　15
　　设计相应的数据结构和算法，尽量高效的统计一片英文文章（总单词数目）里出现的所有英文单词，按照在文章中首次出现的顺序打印输出该单词和它的出现次数。
　　16
　　有几百亿的整数，分布的存储到几百台通过网络连接的计算机上，你能否开发出一个算法和系统，找出这几百亿数据的中值？就是在一组排序好的数据中居于中间的数。显然，一台机器是装不下所有的数据。也尽量少用网络带宽。
　　17
　　假设已有10万个敏感词，现给你50个单词，查询这50个单词中是否有敏感词。
　　分析：换句话说，题目要你判断这50个单词是否存在那10万个敏感词库里，明显是字符串匹配，由于是判断多个单词不是一个，故是多模式字符串匹配问题，既是多模式字符串匹配问题，那么便有一类称之为多模式字符串匹配算法，而这类算法无非是KMP、hash、trie、AC自动机、wm等等。
　　那到底用哪种算法呢？这得根据题目的应用场景而定。
　　10万 + 50，如果允许误差的话，你可能会考虑用布隆过滤器；否则，只查一次的话，可能hash最快，但hash消耗空间大，故若考虑tire的话，可以针对这10万个敏感词建立trie树，然后对那50个单词搜索这棵10万敏感词构建的tire树，但用tire树同样耗费空间，有什么更好的办法呢？Double Array Trie么？请读者继续思考。


附录E 操作系统
　　1
　　请问死锁的条件是什么？以及如何处理死锁问题？
　　解答：互斥条件（Mutual exclusion）：

• 1、资源不能被共享，只能由一个进程使用。
  
• 2、请求与保持条件（Hold and wait）：已经得到资源的进程可以再次申请新的资源。
  
• 3、非剥夺条件（No pre-emption）：已经分配的资源不能从相应的进程中被强制地剥夺。
  
• 4、循环等待条件（Circular wait）：系统中若干进程组成环路，该环路中每个进程都在等待相邻进程正占用的资源。
  

　　如何处理死锁问题：

• 1、忽略该问题。例如鸵鸟算法，该算法可以应用在极少发生死锁的的情况下。为什么叫鸵鸟算法呢，因为传说中鸵鸟看到危险就把头埋在地底下，可能鸵鸟觉得看不到危险也就没危险了吧。跟掩耳盗铃有点像。
  
• 2、检测死锁并且恢复。
  
• 3、仔细地对资源进行动态分配，以避免死锁。
  
• 4、通过破除死锁四个必要条件之一，来防止死锁产生。
  

　　2
　　请阐述动态链接库与静态链接库的区别。
　　解答：静态链接库是.lib格式的文件，一般在工程的设置界面加入工程中，程序编译时会把lib文件的代码加入你的程序中因此会增加代码大小，你的程序一运行lib代码强制被装入你程序的运行空间，不能手动移除lib代码。
　　动态链接库是程序运行时动态装入内存的模块，格式*.dll，在程序运行时可以随意加载和移除，节省内存空间。
　　在大型的软件项目中一般要实现很多功能，如果把所有单独的功能写成一个个lib文件的话，程序运行的时候要占用很大的内存空间，导致运行缓慢；但是如果将功能写成dll文件，就可以在用到该功能的时候调用功能对应的dll文件，不用这个功能时将dll文件移除内存，这样可以节省内存空间。
　　3
　　请阐述进程与线程的区别。
　　解答：

• ①从概念上：
  
• 进程：一个程序对一个数据集的动态执行过程，是分配资源的基本单位。
  
• 线程：一个进程内的基本调度单位。线程的划分尺度小于进程，一个进程包含一个或者更多的线程。
  
• ②从执行过程中来看：
  
• 进程：拥有独立的内存单元，而多个线程共享内存，从而提高了应用程序的运行效率。
  
• 线程：每一个独立的线程，都有一个程序运行的入口、顺序执行序列、和程序的出口。但是线程不能够独立的执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
  
• ③从逻辑角度来看（重要区别）：
  
• 多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但是，操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理及资源分配。
  

　　4
　　用户进程间通信主要哪几种方式？
　　解答：主要有以下6种：

• 1、管道：管道是单向的、先进先出的、无结构的、固定大小的字节流，它把一个进程的标准输出和另一个进程的标准输入连接在一起。写进程在管道的尾端写入数据，读进程在管道的道端读出数据。数据读出后将从管道中移走，其它读进程都不能再读到这些数据。管道提供了简单的流控制机制。进程试图读空管道时，在有数据写入管道前，进程将一直阻塞。同样地，管道已经满时，进程再试图写管道，在其它进程从管道中移走数据之前，写进程将一直阻塞。
  
• 无名管道：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系（通常是指父子进程关系）的进程间使用。
  
• 命名管道：命名管道也是半双工的通信方式，在文件系统中作为一个特殊的设备文件而存在，但是它允许无亲缘关系进程间的通信。当共享管道的进程执行完所有的I/O操作以后，命名管道将继续保存在文件系统中以便以后使用。
  
• 2、信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其它进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
  
• 3、消息队列：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
  
• 4、信号：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
  
• 5、共享内存：共享内存就是映射一段能被其它进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的IPC方式，它是针对其它进程间通信方式运行效率低而专门设计的。它往往与其它通信机制（如信号量）配合使用，来实现进程间的同步和通信。
  
• 6、套接字：套接字也是一种进程间通信机制，与其它通信机制不同的是，它可用于不同机器间的进程通信。