项目github地址：bitcarmanlee easy-algorithm-interview-and-practice

欢迎大家star，留言，一起学习进步
SVM是一种典型的两类分类器，即它只回答属于正类还是负类的问题。而现实中要解决的问题，往往是多类的问题（少部分例外，例如垃圾邮件过滤，就只需要确定“是”还是“不是”垃圾邮件），比如文本分类，比如数字识别。如何由两类分类器得到多类分类器，就是一个值得研究的问题。
其中一种一劳永逸的方法，就是真的一次性考虑所有样本，并求解一个多目标函数的优化问题，一次性得到多个分类面。多个超平面把空间划分为多个区域，每个区域对应一个类别，给一篇文章，看它落在哪个区域就知道了它的分类。
看起来很美对不对？只可惜这种算法还基本停留在纸面上，因为一次性求解的方法计算量实在太大，大到无法实用的地步。
稍稍退一步，我们就会想到所谓“一类对其余”的方法，就是每次仍然解一个两类分类的问题。比如我们有5个类别，第一次就把类别1的样本定为正样本，其余2，3，4，5的样本合起来定为负样本，这样得到一个两类分类器，它能够指出一篇文章是还是不是第1类的；第二次我们把类别2 的样本定为正样本，把1，3，4，5的样本合起来定为负样本，得到一个分类器，如此下去，我们可以得到5个这样的两类分类器（总是和类别的数目一致）。到了有文章需要分类的时候，我们就拿着这篇文章挨个分类器的问：是属于你的么？是属于你的么？哪个分类器点头说是了，文章的类别就确定了。这种方法的好处是每个优化问题的规模比较小，而且分类的时候速度很快（只需要调用5个分类器就知道了结果）。但有时也会出现两种很尴尬的情况，例如拿一篇文章问了一圈，每一个分类器都说它是属于它那一类的，或者每一个分类器都说它不是它那一类的，前者叫分类重叠现象，后者叫不可分类现象。分类重叠倒还好办，随便选一个结果都不至于太离谱，或者看看这篇文章到各个超平面的距离，哪个远就判给哪个。不可分类现象就着实难办了，只能把它分给第6个类别了……更要命的是，本来各个类别的样本数目是差不多的，但“其余”的那一类样本数总是要数倍于正类（因为它是除正类以外其他类别的样本之和嘛），这就人为的造成了上一节所说的“数据集偏斜”问题。
因此我们还得再退一步，还是解两类分类问题，还是每次选一个类的样本作正类样本，而负类样本则变成只选一个类（称为“一对一单挑”的方法，哦，不对，没有单挑，就是“一对一”的方法，呵呵），这就避免了偏斜。因此过程就是算出这样一些分类器，第一个只回答“是第1类还是第2类”，第二个只回答“是第1类还是第3类”，第三个只回答“是第1类还是第4类”，如此下去，你也可以马上得出，这样的分类器应该有5 X 4/2=10个（通式是，如果有k个类别，则总的两类分类器数目为k(k-1)/2）。虽然分类器的数目多了，但是在训练阶段（也就是算出这些分类器的分类平面时）所用的总时间却比“一类对其余”方法少很多，在真正用来分类的时候，把一篇文章扔给所有分类器，第一个分类器会投票说它是“1”或者“2”，第二个会说它是“1”或者“3”，让每一个都投上自己的一票，最后统计票数，如果类别“1”得票最多，就判这篇文章属于第1类。这种方法显然也会有分类重叠的现象，但不会有不可分类现象，因为总不可能所有类别的票数都是0。看起来够好么？其实不然，想想分类一篇文章，我们调用了多少个分类器？10个，这还是类别数为5的时候，类别数如果是1000，要调用的分类器数目会上升至约500,000个（类别数的平方量级）。这如何是好？
看来我们必须再退一步，在分类的时候下功夫，我们还是像一对一方法那样来训练，只是在对一篇文章进行分类之前，我们先按照下面图的样子来组织分类器（如你所见，这是一个有向无环图，因此这种方法也叫做DAG SVM）

这样在分类时,我们就可以先问分类器“1对5”（意思是它能够回答“是第1类还是第5类”），如果它回答5，我们就往左走，再问“2对5”这个分类器，如果它还说是“5”，我们就继续往左走，这样一直问下去，就可以得到分类结果。好处在哪？我们其实只调用了4个分类器（如果类别数是k，则只调用k-1个），分类速度飞快，且没有分类重叠和不可分类现象！缺点在哪？假如最一开始的分类器回答错误（明明是类别1的文章，它说成了5），那么后面的分类器是无论如何也无法纠正它的错误的（因为后面的分类器压根没有出现“1”这个类别标签），其实对下面每一层的分类器都存在这种错误向下累积的现象。
不过不要被DAG方法的错误累积吓倒，错误累积在一对其余和一对一方法中也都存在，DAG方法好于它们的地方就在于，累积的上限，不管是大是小，总是有定论的，有理论证明。而一对其余和一对一方法中，尽管每一个两类分类器的泛化误差限是知道的，但是合起来做多类分类的时候，误差上界是多少，没人知道，这意味着准确率低到0也是有可能的，这多让人郁闷。

　　而且现在DAG方法根节点的选取（也就是如何选第一个参与分类的分类器），也有一些方法可以改善整体效果，我们总希望根节点少犯错误为好，因此参与第一次分类的两个类别，最好是差别特别特别大，大到以至于不太可能把他们分错；或者我们就总取在两类分类中正确率最高的那个分类器作根节点，或者我们让两类分类器在分类的时候，不光输出类别的标签，还输出一个类似“置信度”的东东，当它对自己的结果不太自信的时候，我们就不光按照它的输出走，把它旁边的那条路也走一走，等等。
大Tips：SVM的计算复杂度

　　使用SVM进行分类的时候，实际上是训练和分类两个完全不同的过程，因而讨论复杂度就不能一概而论，我们这里所说的主要是训练阶段的复杂度，即解那个二次规划问题的复杂度。对这个问题的解，基本上要划分为两大块，解析解和数值解。

　　解析解就是理论上的解，它的形式是表达式，因此它是精确的，一个问题只要有解（无解的问题还跟着掺和什么呀，哈哈），那它的解析解是一定存在的。当然存在是一回事，能够解出来，或者可以在可以承受的时间范围内解出来，就是另一回事了。对SVM来说，求得解析解的时间复杂度最坏可以达到O(Nsv3)，其中Nsv是支持向量的个数，而虽然没有固定的比例，但支持向量的个数多少也和训练集的大小有关。

数值解就是可以使用的解，是一个一个的数，往往都是近似解。求数值解的过程非常像穷举法，从一个数开始，试一试它当解效果怎样，不满足一定条件（叫做停机条件，就是满足这个以后就认为解足够精确了，不需要继续算下去了）就试下一个，当然下一个数不是乱选的，也有一定章法可循。有的算法，每次只尝试一个数，有的就尝试多个，而且找下一个数字（或下一组数）的方法也各不相同，停机条件也各不相同，最终得到的解精度也各不相同，可见对求数值解的复杂度的讨论不能脱开具体的算法。

一个具体的算法，Bunch-Kaufman训练算法，典型的时间复杂度在O(Nsv3+LNsv2+dLNsv)和O(dL2)之间，其中Nsv是支持向量的个数，L是训练集样本的个数，d是每个样本的维数（原始的维数，没有经过向高维空间映射之前的维数）。复杂度会有变化，是因为它不光跟输入问题的规模有关（不光和样本的数量，维数有关），也和问题最终的解有关（即支持向量有关），如果支持向量比较少，过程会快很多，如果支持向量很多，接近于样本的数量，就会产生O(dL2)这个十分糟糕的结果（给10，000个样本，每个样本1000维，基本就不用算了，算不出来，呵呵，而这种输入规模对文本分类来说太正常了）。

　　这样再回头看就会明白为什么一对一方法尽管要训练的两类分类器数量多，但总时间实际上比一对其余方法要少了，因为一对其余方法每次训练都考虑了所有样本（只是每次把不同的部分划分为正类或者负类而已），自然慢上很多。

之前说要用SVM实现表情识别来着，所以找个简单例子练练手。


惯例开始放结果，实现结果如下：
//这里简单对四个点分了四类，图片显示得很直观。
//支持向量总共6个。
//最后测试了两个点进行分类。





只需要配置好Opencv3的环境即可运行。
这里用到的是cv::SVM, 老版本Opencv2410之前用的是CvSvm,推荐用最新的Opencv310。


配置环境链接：
1.常规方法：http://blog.csdn.net/zmdsjtu/article/details/52235056
2.一键安装方法：http://blog.csdn.net/zmdsjtu/article/details/52794260


//代码的备注自我感觉写得挺多啦
下面就是简单粗暴的代码啦：
#include<opencv2\opencv.hpp> 

using namespace std;
using namespace cv;
using namespace cv::ml;

int main()
{


	//训练需要用到的数据
	int 标签[4] = { 1, 2, 3, 4 };
	float 训练数据[4][2] = { { 31, 12 },{ 65, 220 },{ 440, 350 },{ 400, 400 } };
	//转为Mat以调用
	Mat 训练Mat(4, 2, CV_32FC1, 训练数据);
	Mat 标签label(4, 1, CV_32SC1, 标签);
	//训练的初始化
	Ptr<SVM> svm = SVM::create();
	svm->setType(SVM::C_SVC);
	svm->setKernel(SVM::LINEAR);
	svm->setTermCriteria(TermCriteria(TermCriteria::MAX_ITER, 100, 1e-6));
	//开始训练
	svm->train(训练Mat, ROW_SAMPLE, 标签label);

	//-----------无关紧要的美工的部分-----------------------	
	//----其实对每个像素点的坐标也进行了分类----------------
	int 宽 = 512, 高 = 512;
	Mat 演示图片 = Mat::zeros(高, 宽, CV_8UC3);
	Vec3b green(0, 255, 0), blue(255, 0, 0), red(0, 0, 255), black(0, 0, 0);
	for (int i = 0; i < 演示图片.rows; ++i)
		for (int j = 0; j < 演示图片.cols; ++j)
		{
			Mat sampleMat = (Mat_<float>(1, 2) << j, i);
			float response = svm->predict(sampleMat);

			if (response == 1)
				演示图片.at<Vec3b>(i, j) = green;
			else if (response == 2)
				演示图片.at<Vec3b>(i, j) = blue;
			else if (response == 3)
				演示图片.at<Vec3b>(i, j) = red;
			else if (response == 4)
				演示图片.at<Vec3b>(i, j) = black;
		}
	//--------把初始化训练的点画进图片------------
	int thickness = -1;
	int lineType = 8;
	for (int 画点 = 0; 画点 < sizeof(标签) / sizeof(int); 画点++) {
		circle(演示图片, Point(训练数据[画点][0], 训练数据[画点][1]), 10, Scalar(255, 255, 255), thickness, -1);
	}
	// 把 support vectors  cout粗来看看……
	Mat sv = svm->getSupportVectors();
	cout << "Support Vectors为：" << endl;
	for (int i = 0; i < sv.rows; ++i)
	{
		const float* v = sv.ptr<float>(i);
		cout << v[0] << " " << v[1] << endl;
	}

	//测试测试

	Mat 结果;
	float teatData[2][2] = { { 20, 11 },{ 310, 411 } };
	Mat query(2, 2, CV_32FC1, teatData);

	svm->predict(query, 结果);
	cout << "分类结果为：" << endl;
	cout << 结果;
	imshow("SVM显示", 演示图片);
	waitKey(-1);

}


祝大家使用分类器愉快咯，有问题欢迎留言交流哈~

首先说明，求导不只是链式法则这么简单。我们常常不知道需要对谁求导，如何从最后的损失函数一步一步的计算到每一个参数上。此外，我们也有可能遇到不知道根据公式来进行编程，根本原因在于公式和编程并不是同样的语言，这是有差别的，我们如何跨越这个差别呢？

如果你有以上两个困惑，希望本文和下一篇博客能助你一臂之力。
本文主要针对第一个问题。第二个问题将会在下篇博客详细说明。
损失函数的计算
首先说明本文解决的是softmax的多分类器的梯度求导，以下先给出损失函数的计算方式：

这里将最终的loss分为4步进行计算，如下所示，当然，这里不解释为什么是这样的计算方式。

注意到，本文并不限制训练样本的数量，训练样本的特征数，以及最后分为几类。



这里x表示输入，w表示权重参数。

说明：这里的x和w的下标表示x的某一行和w的某一列相乘在逐项相加得到s。

然后再根据s计算每一个类的概率，如下公式（2）



这里采用的下标和公式（1）不相同，其中，n表示样本的个数，y表示样本为n时的正确分类标号。k表示有多少分类。这个公式就是先将s进行e次方计算，然后归一化，求得该样本正确分类下的概率p.

根据p可以计算出每一个样本的损失，如公式（3）：



这个公式说明，每一个样本的损失仅仅是正确分类对应的概率值的log函数，这里准确说应该是ln函数，也就是以自然对数为底的，这样计算导数更方便，后面会以ln为版本进行计算。

最后，根据公式（4）计算所有样本的损失：



也就是将所有样本的损失求平均数。

注意：以上下标是独立系统，与下面的推导过程没有必然关系，这里特别指ij，其他字母的含义基本相同。
基本求导法则
所谓梯度，就是求损失函数对参数w的导数，将其用在更新参数w上，达到优化的目的。

我们知道，梯度计算遵循着链式法则，而基本求导公式也是需要的，防止有人忘记，我先给出这里将会用到的基本求导公式。知道的请跳过这一节，直接看下一节。












以下开始正式求梯度
计算整个损失函数对w（下标为ij）的导数。

根据链式法则，考虑到总损失为每个样本损失的平均数，且每个样本的损失都与wij相关，这个说明很有必要，假如某个损失与wij无关，我们就不用对它进行求导了。

有公式（5）



这里Ln表示样本为n时的损失函数。

不失一般性，这里对最后一项进行继续推导，然后将其相加。

同样的，由于pny是和wij的函数，有公式（6）：



结合公式（2），前一部分有有公式（7）：



后一个部分我们继续来考虑，pny的上下两项是否都是wij的函数？肯定的回答是，这不一定，由公式（2）和（1）可知，如果公式2中分子的下标y不是j,那么实际上这里公式2的分子就不是wij的函数。

我们细说一下，由公式1，ij是公式1中的下标，当sij与wij有关系建立在这个j相等的情况，但是公式2的分子并不一定就满足这个关系的，什么情况满足呢？那就是样本n的正确分类的下标j和wij中的下标j相等时；否则这就没有关系。

因此，我们需要分为两种情况来进一步计算公式（6）的后半部分。

（实际上，我们也可以先认为他们相关，然后进一步处理，这里我先不这么做）

情况一，公式（2）中的分子与wij无关：也就是以下公式中y与j不相等

公式（2）中分母必然与wij有关，且只有一个与wij有关。那就是公式（2）中分母的下标k与wij的就相等时，而其他都与wij无关。

进一步考虑到e的s次方，s与wij的关系，因此针对情况一，有公式（8）



继续对第二项展开有公式（9）：



这里还是细细说一下，这个过程，始终记住一点，那就是中间变量与wij是什么关系，可以根据公式看出来。根据公式（1），当且仅当s的下标中是ij时才会与wij有关，而对sij对wij求导时得到的就是xii，(两个i不一样的含义)只需要把公式（1）中的x和w的下标中的点号换成i即可。也就是说，s对w求导时，x的第一个下标是s的第一个下标，x的第二个下标是w的第一个下标。当然，这里我们需要再将s的下标i换成n，这样才能满足以上的推导。

我们将公式（9）根据公式（2）化简一下，再带入公式（6），可以得到公式（10），也就是情况一下的最终一个样本的梯度：



其中，用了一个简写，也就是求和的项简写了，请留意。

写成pnj是因为我们计算过程中会产生这个数，而且这样写起来也更整齐。

情况二，公式（2）中的分子是wij的函数：

注意到这里，公式（2）中pny的下标y和wij的下标j是相等的，也就是y=j。

情况2比情况1复杂在公式（2）的分母上，其余相同，因此，对其求导过程如下：

这里先使用ynj(nj是下标)表示样本为n时第j个分类的真实值，要么是0，要么是1，1表示真实分类就是这个j.

情况一根据（1\u)'求导，情况二则根据（v/u)'来求导，因此有一点差别。

以下一步一步的写：



根据公式（2）将后面展开可得：



化简一下可以得到：



根据公式（2）继续化简：



对上式去括号操作：



继续求导并且根据公式2化简得公式（11）



可以看出，这与上面的情况一相差在最后一项上，而前面一项是相等的。

接下来我们一起探讨一下怎么求后面的一项，毕竟这还无法完全理解清楚，因为这还是一个导数，也不是输入或者中间求到的某个数。

前面我们已经说到，情况二下公式（2）中的y和wij的j是相等的。

这时候计算知道：



所以公式（11）进一步计算可得最终的求导公式：公式（12）


综合两个情况
情况二比情况一多减去一项。

一般情况下，我们直接使用pnj * xni即可。

而当wij中j是当前样本n的正确分类时要多减去xni。
以上既是多分类器softmax的梯度求导公式。
后话
其实个人感觉梯度的计算还是挺难的，而且本文只是推导公式，还没有真正的编程计算。

实际上，我们通常为了保证我们的程序正确，会写一个数值求导，正确情况下两者不会相差很多。

本文的理论推导，将会在下一篇博客中写明如何进行计算。

1.bagging 使用多个分类其结果进行投票，投票结果为分类结果

2.ADABoost：将多个弱分类器合成一个较强的分类器




转：bootstrps bagging boosting这几个概念经常用到，现仔细学习了一下：

他们都属于集成学习方法，(如：Bagging，Boosting，Stacking)，将训练的学习器集成在一起,原理来源于PAC学习模型（Probably
 Approximately CorrectK）。Kearns和Valiant指出，在PAC学习模型中，若存在一

个多项式级的学习算法来识别一组概念，并且识别正确率很高，那么这组概念是强可学习的；而如果学习算法识别一组概念的正确率仅比随机猜测略好，那么这组概念是弱可学习的。他们提出了弱学习算法与强学习算法的等价性问题，即是否可以将弱学习算法提升成强学习算法。如果两者等价，那么在学习概念时，只要找到一个比随机猜测略好的弱学习算法，就可以将其提升为强学习算法，而不必直接去找通常情况下很难获得的强学习算法。

bootstraps:名字来自成语“pull up by your own bootstraps”，意思是依靠你自己的资源，它是一种有放回的抽样方法，学习中还发现有种叫jackknife的方法，它是每一次移除一个样本。

bagging: bootstrap
 aggregating的缩写。让该学习算法训练多轮，每轮的训练集由从初始的训练集中随机取出的n个训练倒组成，初始训练例在某轮训练集中可以出现多次或根本不出现训练之后可得到一个预测函数序列h．，⋯ ⋯h 最终的预测函数H对分类问题采用投票方式，对回归问题采用简单平均方法对新示例进行判别。

–(训练R个分类器fi，分类器之间其他相同就是参数不同。其中fi是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。 –对于新文档d，用这R个分类器去分类，得到的最多的那个类别作为d的最终类别.)



boosting:其中主要的是AdaBoost（Adaptive
 Boosting）。初始化时对每一个训练例赋相等的权重1／n，然后用该学算法对训练集训练t轮，每次训练后，对训练失败的训练例赋以较大的权重，也就是让学习算法在后续的学习中集中对比较难的训练铡进行学习，从而得到一个预测函数序列h 一⋯h其中h．也有一定的权重，预测效果好的预测函数权重较大，反之较小。最终的预测函数H对分类问题采用有权重的投票方式，对回归问题采用加权平均的方法对新示例进行判别。( 类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率).

Bagging与Boosting的区别：在于Bagging的训练集的选择是随机的，各轮训练集之间相互独立，而Boostlng的训练集的选择是独立的，各轮训练集的选择与前面各轮的学习结果有关；Bagging的各个预测函数没有权重，而Boosting是有权重的；Bagging的各个预测函数可以并行生成，而Boosting的各个预测函数只能顺序生成。对于象神经网络这样极为耗时的学习方法。Bagging可通过并行训练节省大量时间开销。　　　bagging和boosting都可以有效地提高分类的准确性。在大多数数据集中，boosting的准确性比bagging高。在有些数据集中，boosting会引起退化。---Overfit



文本分类中使用的投票方法（Voting，也叫组合分类器）就是一种典型的集成机器学习方法。它通过组合多个弱分类器来得到一个强分类器，包括Bagging和Boosting两种方式，二者的主要区别是取样方式不同。Bagging采用均匀取样，而Boosting根据错误率来取样，因此Boosting的分类精度要优于Bagging。投票分类方法虽然分类精度较高，但训练时间较长。Boosting思想的一种改进型AdaBoost方法在邮件过滤、文本分类方面都有很好的性能。







from： http://home.kaoyan.com/space.php?uid=772709&do=blog&id=31082