支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年
首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的
优势，并能够推广应用到函数拟合等其他机器学习问题中。
正是由于SVM具有很多独特的优势，基于SVM分类器在很多时候都具有
较好的拟合作用。本文对SVM算法在行人检测项目实践中的应用进行详细讲解，同时给出调用OpenCV分类器及可视化的代码实现，便于大家学习实践。
目前的行人检测基本上都是基于法国研究人员Dalal在2005的CVPR发
表的HOG+SVM的行人检测算法(Histograms of Oriented Gradients for Human Detection, Navneet Dalel,Bill Triggs, CVPR2005)。HOG+SVM作
为经典算法也集成到OpenCV里面去了，可以直接调用实现行人检测。
一、HOG特征描述符
HOG（Histogram of Oriented Gradients）HOG特征在对象检测与模式
匹配中是一种常见的特征提取技术（深度学习之前），是基于本地像素块进
行特征直方图提取的一种算法，对像局部的变形与光照影响有很好的稳定性，最初是用HOG特征来识别人像，通过HOG特征提取+SVM训练，可以得到很好
的效果，OpenCV已经有相应的接口。
HOG特征是在2005年CVPR的会议发表，在图像手工特征提取方面具有里
程碑式的意义，当时在行人检测领域获得了极大成功。
1.1 主要思想
局部目标的外表和形状可以被局部梯度的分布很好的描述，即使我们不知
道对应的梯度和边缘的位置。(本质：梯度的统计信息，梯度主要存在于边缘edge或角落corner的地方)
1.2 宏观
特征描述符就是通过提取图像的有用信息，并且丢弃无关信息来简化图像
的表示。HOG特征描述符可以将3通道的彩色图像转换成一定长度的特征向量。那么我们就需要定义什么是“有用的”，什么是“无关的”。这里的“有用”，是指对于什么目的有用，显然特征向量对于观察图像是没有用的，但是它对于
像图像识别和目标检测这样的任务非常有用。当将这些特征向量输入到类似支
持向量机（SVM）这样的图像分类算法中时，会得到较好的结果。那什么样的
“特征”对分类任务是有用，比如我们想检测出马路上的车道线，那么我们可
以通过边缘检测来找到这些车道线，在这种情况下，边缘信息就是“有用的”，而颜色信息是无关的。
方向梯度直方图(HOG)特征描述符常和线性支持向量机(SVM)配合使用，
用于训练高精度的目标分类器。
1.3 微观（硬核）
在HOG特征描述符中，梯度方向的分布，也就是梯度方向的直方图被视作
特征。图像的梯度(x和y导数)非常有用，因为边缘和拐角(强度突变的区域)
周围的梯度幅度很大，并且边缘和拐角比平坦区域包含更多关于物体形状的信息。HOG特征是一种图像局部特征，基本思路是将图像划分为很多小的连通区域，即细胞单元Cell，然后对Cell的梯度幅值和方向进行投票统计，形成基
于梯度特性的直方图。把直方图在图像更大的范围内(又名区间或者Block)进
行归一化。归一化的块描述符叫做HOG描述子feature descriptor。将检测窗
口中的所有块的HOG描述子组合成最终的特征向量。然后使用SVM分类器进行目标和非目标的二分类（检测）。HOG+SVM的工作流程如下：
首先对输入的图片进行预处理，然后计算像素点的梯度特性，包括梯度幅值和梯度方向。然后投票统计形成梯度直方图，然后对blocks进行
normalize，最后收集到检测窗口的HOG feature(一行多维的vector)放入SVM里进行监督学习，实现行人的检测。接下来对上述HOG的主要步骤进行学习。
检测窗口在整个图像的所有位置和尺度进行扫描，并对输出的金字塔进行非极大值抑制来检测目标（检测窗口的大小一般为128x64）
1.4 HOG算法优缺点
HOG算法具有以下优点：
?核心思想是所检测的局部物体外形能够被梯度或边缘方向的分布所描述，HOG能较好地捕捉局部形状信息，对几何和光学变化都有很好的不变性；
?HOG是在密集采样的图像块中求取的，在计算得到的HOG特征向量中隐含了该块与检测窗口之间的空间位置关系。
HOG算法具有以下缺点：
?特征描述子获取过程复杂，维数较高，导致实时性差；
?很难处理遮挡问题，人体姿势动作幅度过大或物体方向改变也不易检测（这个问题后来在DPM中采用可变形部件模型的方法得到了改善）；
?跟SIFT相比，HOG没有选取主方向，也没有旋转梯度方向直方图，因而本身不具有旋转不变性（较大的方向变化），其旋转不变性是通过采用不同旋转方向的训练样本来实现的；
?跟SIFT相比，HOG本身不具有尺度不变性，其尺度不变性是通过缩放检测窗口图像的大小来实现的；
?此外，由于梯度的性质，HOG对噪点相当敏感，在实际应用中，在block和Cell划分之后，对于得到各个区域，有时候还会做一次高斯平滑去除噪点。
二、HOG特征的原理
接下来让我们进入到计算图像的HOG特征描述符的具体步骤。以下面这张图片为例（宽高为100x200）:
2.1 图形预处理
预处理包括灰度化和Gamma变换。灰度处理是可选操作，因为灰度图像和
彩色图像都可以用于计算梯度图。对于彩色图像，先对三通道颜色值分别计算
梯度，然后取梯度值最大的那个作为该像素的梯度。然后进行伽马矫正，调节
图像对比度，减少光照对图像的影响（包括光照不均和局部阴影），使过曝或
者欠曝的图像恢复正常，更接近人眼看到的图像。Gamma矫正公式：，其中表
示图像，表示幂指数。(越大，图像越暗；为1时，表示没有变化。) 如图，当取不同的值时对应的输入输出曲线( =1时输入输出保持一致) ：1）当<1时，输入图像的低灰度值区域动态范围变大，进而图像低灰度值区域对比度得以增强；在高灰度值区域，动态范围变小，进而图像高灰度值区域对比度得以降低。最终，图像整体的灰度变亮。2）当>1时，输入图像的低灰度值区域动态范围
变小，进而图像低灰度值区域对比度得以降低；在高灰度值区域，动态范围变大，进而图像高灰度值区域对比度得以增强。最终，图像整体的灰度变暗。
代码：
import cv2
import numpy as np
from matplotlib import pyplot as plt
img = cv2.imread('*.png', 0)
img = cv2.cvtColor(img,cv2.COLOR_BGR2RGB)
img2 = np.power(img/float(np.max(img)),1/2.2)
plt.imshow(img2)
plt.axis('off')
plt.show()
放图，左图是，中图是，右图是：
作者在他的博士论文里有提到，对于涉及大量的类内颜色变化，如猫，
狗和马等动物，没标准化的RGB图效果更好，而牛，羊的图做gamma颜色校
正后效果更好。是否用gamma校正分情况吧。
2.2 计算图像梯度
为了得到梯度直方图，那么首先需要计算图像水平方向和垂直方向梯度。可以通过使用以下内核过滤图像实现，分别用于计算水平梯度和垂直梯度。
一般使用特定的卷积核对图像滤波实现，可选用的卷积模板有：sobel算子、Prewitt算子、Roberts模板等等。
可以使用内核大小为1的sobel算子获取相同结果，OpenCV也是如此。
利用sobel水平和垂直算子与输入图像卷积计算d
x 、d
y
：
进一步得到图像梯度的幅值：
简化计算，幅值也可以做近似：
图像梯度的方向：
这里需要注意的是：梯度方向和图像边缘方向是互相正交的。
代码：
import cv2
import numpy as np
# Read
imageimg = cv2.imread('*.jpg')
img = np.float32(img) / 255.0 # 归一化
# 计算x和y方向的梯度
gx = cv2.Sobel(img, cv2.CV_32F, 1, 0, ksize=1)
gy = cv2.Sobel(img, cv2.CV_32F, 0, 1, ksize=1)
# 计算合梯度的幅值和方向（角度）
mag, angle = cv2.cartToPolar(gx, gy, angleInDegrees=True)
下图展示了梯度：
第一个图：x-梯度的绝对值，第二个图：y梯度的绝对值，第三个图：梯度的幅值，第四个图：角度。
注意到，x-梯度在垂直线触发，y-梯度在水平线触发。梯度的幅值在有密集的剧烈改变时触发。当区域很平缓时，梯度没有明显变化。梯度图除去了很多不必要的信息（例如有颜色的背景），强调凸显线条。当你看到梯度图像，很容易想到这张图片有一个人。
在每个像素点，梯度有一个幅值和方向。对于有颜色的图像，计算三通道的梯度（如上图所示）。一个像素点的梯度的幅值是三通道中梯度幅值最大的值，角度也是最大梯度对应的角度。
2.3 计算梯度直方图
此时，每一个像素点具有两个值：梯度幅值和梯度方向。
在这一步中，图像被分成若干个8×8的Cell，如下图所示，例如我们将图像resize至64x128的大小，那么这幅图像就被划分为8x16个8x8的Cell单元，并为每个8×8的Cell计算梯度直方图。当然，Cell的划分也可以是其他值：16x16，8x16等，根据具体的场景确定。
计算梯度直方图之前，先了解一下为什么要把图像分为若干个Cell?这是因为如果对一整张梯度图逐像素计算，其中的有效特征是非常稀疏的，不但运算量大，而且会受到一些噪声干扰。使用特征描述符便提供了紧凑的表示。一个8x8的图像块包含8x8x3=192个像素值。一个8x8的Cell包含了8x8x2 = 128个值（每个像素包括梯度的大小和方向）。128个值将由9-bin的直方图（存储9个值的向量，想想坐标应该就明白了）。同时，计算Cell上的梯度直方图更具鲁棒性。逐像素计算梯度会产生噪音，直方图表示对噪音更不敏感。在HOG中，每个8x8的Cell的梯度直方图本质是一个由9个数值组成的向量，对应于0、20、40、60…160的梯度方向(角度)。那么原本Cell中8x8x2 = 128个值就由长度为9的向量来表示，用这种梯度直方图的表示方法，大大降低了计算量，同时又对光照等环境变化更加地鲁棒。
如下图所示，左图是衣服64x128的图像，被划分为8x16个8x8的Cell；中间的图像表示一个Cell中的梯度矢量，箭头朝向代表梯度方向，箭头长度代表梯度大小。
右图是8×8 的Cell中表示梯度的原始数值，注意角度的范围介于0到180度之间，而不是0到360度，这被称为“无符号”梯度，因为两个完全相反的方向被认为是相同的。和是相同的。（经验表明这样处理对于行人检测效果更好。）
接下来，计算Cell中像素的梯度直方图，将0-180度分成9等份，称为9个bins，分别是0，20，40…160。然后对每个bin中梯度的贡献进行统计：
这里采用加权投票统计，比如上面方向图中蓝圈包围的像素，角度为80度，这个像素对应的幅值为2，所以在直方图80度对应的bin加上2。红圈包围的像素，角度为10度，介于0度和20度之间，其幅值为4，那么这个梯度值就被按比例分给0度和20度对应的bin，也就是各加上2。
再比如：（如上图所示）某像素的梯度幅值为13.6，方向为36，36度两侧的角度bin分别为20度和40度，那么按一定加权比例分别在20度和40度对应的bin加上梯度值，加权公式为：
?20度对应的bin：(（40-36）/20) x13.6，分母的20表示20等份，其中4份给20度对应的bin；
?40度对应的bin：(（36-20）/20) x13.6，分母的20表示20等份,其中16份给20度对应的bin；
还有一个细节需要注意，如果某个像素的梯度角度大于160度，也就是在160度到180度之间，那么把这个像素对应的梯度值按比例分给0度和160度对应的bin。如左下图绿色圆圈中的角度为165度，幅值为85，则按照同样的加权方式将85分别加到0度和160度对应的bin中。
对整个Cell进行投票统计，最终得到9-bin直方图：
可以看到直方图中，0度和160附近有很大的权重，说明了大多数像素的梯度向上或者向下，也就是这个Cell是个横向边缘。
2.4 Block归一化
HOG特征将8×8的一个局部区域作为一个Cell，再以2×2个Cell作为一组，称为一个block，也就是说一个block表示16x16的区域。
由于每个Cell有9个值，一个block（2×2个Cell）则有36个值，HOG是通过滑动窗口的方式来得到block的，如下图所示：
为什么需要分Block呢？我们已经为图像的8×8单元构造了基于梯度的直方图，但是图像的梯度对整体光照很敏感。这意味着对于特定的图像，图像的
某些部分与其他部分相比会非常明亮。虽然不能从图像中完全消除，但是可以
通过使用16×16个块来对梯度进行归一化来减少这种光照变化的影响。比如通过将所有像素值除以2来使图像变暗，那么梯度幅值将减小一半，因此直方图
中的值也将减小一半。
接下来对Block进行归一化。（再再再一次强调，归一化的目的是为了
降低光照/迁移的影响）：
归一化的方法有很多：L1-norm、L2-norm、max/min等等，一般选择
L2-norm。
例如对于一个[128，64，32]的三维向量来说，模长是：
这叫做向量的L2范数。将这个向量的每个元素除以146.64就得到了归一
化向量 [0.87, 0.43, 0.22]。现在有一个新向量，是第一个向量的2倍
[128x2, 64x2, 32x2]，也就是[256, 128, 64]，我们将这个向量进行归一化，你可以看到归一化后的结果与第一个向量归一化后的结果相同。所以，对向量
进行归一化可以消除整体光照的影响。知道了如何归一化，现在来对block的
梯度直方图进行归一化（注意不是Cell），一个block有4个直方图，将这4
个直方图拼接成长度为36的向量，然后对这个向量进行归一化。因为使用的是滑动窗口，滑动步长为8个像素，一个Cell大小，每滑动一次，就在这个窗口上进行归一化计算得到长度为36的向量，并重复这个过程。如上图所示。
2.5 获得HOG描述子
每一个16x16大小的block将会得到一个长度为36x1的特征向量，并进行归一化。那会得到多大的特征向量呢？
对于上图被划分8 x16个Cell ，每个block有2x2个Cell的话，那
么Cell的个数为：(8-1)x(16-1)=105。
每个16x16 block由36x1维向量，合并所有105个block的特征，最
终得到由36 x105=3780维向量表示的特征描述符。
获得HOG特征向量，就可以用来可视化和分类了。对于多维的HOG特征，SVM就可以排上用场了。
介绍以下Dalal等人的训练方法：
1.提取正负样本的HOG特征；
2.用正负样本训练一个初始的分类器，然后由分类器生产检测器；
3.然后用初始分类器在负样本原图上进行行人检测，检测出来的矩形区域自然
都是分类错误的负样本，这就是所谓的难例(hard examples)；
4.提取难例的HOG特征并结合第一步中的特征，重新训练，生成最终的检测
器；
这种二次训练的处理过程显著提高了每个检测器的表现，一般可以使得每个窗口的误报率(FPPW False Positives Per Window)下降5%。
2.6 使用HOG特征数据
HOG特征本身是不支持旋转不变性与多尺度检测的，但是通过构建高斯金字塔实现多尺度的开窗检测就会得到不同分辨率的多尺度检测支持，如下图所示。
OpenCV中HOG多尺度对象检测API如下：
virtual void cv::HOGDescriptor::detectMultiScale(
InputArray img,
std::vector< Rect > & foundLocations,
double hitThreshold = 0,
Size winStride = Size(),
Size padding = Size(),
double scale = 1.05,
double finalThreshold = 2.0,
bool useMeanshiftGrouping = false
)
Img-表示输入图像
foundLocations-表示发现对象矩形框
hitThreshold-表示SVM距离度量，默认0表示，表示特征与SVM分类超平面之
间
winStride-表示窗口步长
padding-表示填充
scale-表示尺度空间
finalThreshold-最终阈值，默认为2.0
useMeanshiftGrouping-不建议使用，速度太慢拉
在基于Adaboost算法的人脸检测分类器！这一节我们利用haar特征和级
联分类器Adaboost检测人脸时我们使用过detectMultiScale()函数，级联分
类器对象尝试在输入图像的不同尺度下检测对象，该函数有一个比较重要的参
数scaleFactor(一般设置为1.3)，表示一个比率：即在每层金字塔中所获得的
图像与上一层图像的比率，scaleFactor越小，金字塔的层数就越多，计算就
越慢，计算量也会更大，但是计算结果相对更精确。
三、基于OpenCV的简单实现
3.1 行人检测
代码：
import cv2 as cv
import numpy as np
from matplotlib import pyplot as plt
if __name__ == '__main__':
src = cv.imread("*.jpg")
cv.imshow("input", src)
hog = cv.HOGDescriptor()
hog.setSVMDetector(cv.HOGDescriptor_getDefaultPeopleDetector())
# Detect people in the image
(rects, weights) = hog.detectMultiScale(src,
winStride=(2,4),
padding=(8, 8),
scale=1.2,
useMeanshiftGrouping=False) for (x, y, w, h) in rects:
cv.rectangle(src, (x, y), (x + w, y + h), (0, 255, 0), 2)
cv.imshow("hog-detector", src)
cv.imwrite("hog-detector.jpg",src)
cv.waitKey(0)
cv.destroyAllWindows()
待检测图片：
检测图片(有点不完美，调参调不动了，先酱~)：
3.2 可视化
feature.log函数：
image：可以是灰度图或者彩色图；
orientations：就是把180度分成几份，也就是bin的数量；pixels_per_Cell：一个Cell里包含的像素个数；
Cells_per_block：一个block包含的Cell个数；
visualize：是否返回一个hog图像用于显示，下面会显示这张图；
为了显示效果，把Cell的尺寸改为(16, 16)，对于每一个Cell，画出它归一
化后的梯度直方图。如下图所示，我们可以很明显的看出一个人的轮廓。
from skimage import feature, exposure
import cv2
image = cv2.imread('hog.jpg')
fd, hog_image = feature.hog(image, orientations=9, pixels_per_Cell=(16, 16),
Cells_per_block=(2, 2), visualize=True)
# Rescale histogram for better display
hog_image_rescaled = exposure.rescale_intensity(hog_image, in_range=(0, 10))
cv2.imshow('img', image)
cv2.imshow('hog', hog_image_rescaled)
hog_image_rescaled = 255.0 *hog_image_rescaled
cv2.imwrite('edge_hog.jpg', hog_image_rescaled)
cv2.waitKey(0)==ord('q')
支持向量机（SVM ）原理及应用 一、SVM 的产生与发展 自1995年Vapnik (瓦普尼克)在统计学习理论的基础上提出SVM 作为模式识别的新方法之后，SVM 一直倍受关注。同年，Vapnik 和Cortes 提出软间隔(soft margin)SVM ，通过引进松弛变量i ξ度量数据i x 的误分类(分类出现错误时i ξ大于0)，同时在目标函数中增加一个分量用来惩罚非零松弛变量(即代价函数)，SVM 的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程；1996年，Vapnik 等人又提出支持向量回归 (Support Vector Regression ，SVR)的方法用于解决拟合问题。SVR 同SVM 的出发点都是寻找最优超平面(注：一维空间为点；二维空间为线；三维空间为面；高维空间为超平面。)，但SVR 的目的不是找到两种数据的分割平面，而是找到能准确预测数据分布的平面，两者最终都转换为最优化问题的求解；1998年，Weston 等人根据SVM 原理提出了用于解决多类分类的SVM 方法(Multi-Class Support Vector Machines ，Multi-SVM)，通过将多类分类转化成二类分类，将SVM 应用于多分类问题的判断：此外，在SVM 算法的基本框架下，研究者针对不同的方面提出了很多相关的改进算法。例如，Suykens 提出的最小二乘支持向量机 (Least Square Support Vector Machine ，LS —SVM)算法，Joachims 等人提出的SVM-1ight ，张学工提出的中心支持向量机 (Central Support Vector Machine ，CSVM)，Scholkoph 和Smola 基于二次规划提出的v-SVM 等。此后，台湾大学林智仁(Lin Chih-Jen)教授等对SVM 的典型应用进行总结，并设计开发出较为完善的SVM 工具包，也就是LIBSVM(A Library for Support Vector Machines)。LIBSVM 是一个通用的SVM 软件包，可以解决分类、回归以及分布估计等问题。 二、支持向量机原理 SVM 方法是20世纪90年代初Vapnik 等人根据统计学习理论提出的一种新的机器学习方法，它以结构风险最小化原则为理论基础，通过适当地选择函数子集及该子集中的判别函数，使学习机器的实际风险达到最小，保证了通过有限训练样本得到的小误差分类器，对独立测试集的测试误差仍然较小。 支持向量机的基本思想：首先，在线性可分情况下，在原空间寻找两类样本的最优分类超平面。在线性不可分的情况下，加入了松弛变量进行分析，通过使用非线性映射将低维输
scikit-learn 支持向量机算法库使用小结 之前通过一个系列对支持向量机(以下简称SVM)算法的原理做了一个总结，本文从实践 的角度对scikit-learn SVM算法库的使用做一个小结。scikit-learn SVM算法库封装了libsvm 和liblinear 的实现，仅仅重写了算法了接口部分。 1. scikit-learn SVM算法库使用概述 scikit-learn中SVM的算法库分为两类，一类是分类的算法库，包括SVC， NuSVC，和LinearSVC 3个类。另一类是回归算法库，包括SVR， NuSVR，和LinearSVR 3个类。相关的类都包 裹在sklearn.svm模块之中。 对于SVC， NuSVC，和LinearSVC 3个分类的类，SVC和 NuSVC差不多，区别仅仅在于对 损失的度量方式不同，而LinearSVC从名字就可以看出，他是线性分类，也就是不支持各种低维 到高维的核函数，仅仅支持线性核函数，对线性不可分的数据不能使用。 同样的，对于SVR， NuSVR，和LinearSVR 3个回归的类， SVR和NuSVR差不多，区别也仅仅在于对损失的度量方式不同。LinearSVR是线性回归，只能使用线性核函数。 我们使用这些类的时候，如果有经验知道数据是线性可以拟合的，那么使用LinearSVC 去分类或者LinearSVR去回归，它们不需要我们去慢慢的调参去选择各种核函数以及对应参数， 速度也快。如果我们对数据分布没有什么经验，一般使用SVC去分类或者SVR去回归，这就需要 我们选择核函数以及对核函数调参了。 什么特殊场景需要使用NuSVC分类和 NuSVR 回归呢？如果我们对训练集训练的错误率或者说支持向量的百分比有要求的时候，可以选择NuSVC分类和 NuSVR 。它们有一个参数来控制这个百分比。 这些类的详细使用方法我们在下面再详细讲述。 2. 回顾SVM分类算法和回归算法 我们先简要回顾下SVM分类算法和回归算法，因为这里面有些参数对应于算法库的参数，如果不先复习下，下面对参数的讲述可能会有些难以理解。 对于SVM分类算法，其原始形式是： min12||w||22+C∑i=1mξi min12||w||22+C∑i=1mξi
支持向量机（SVM ）简明学习教程 一、最优分类超平面 给定训练数据),(,),,(11l l y x y x ，其中n i R x ∈，}1,1{-∈i y 。 若1=i y ，称i x 为第一类的，I ∈i x ；若1-=i y ，称i x 为第二类的，II ∈i x 。 若存在向量?和常数b ，使得?????II ∈<-I ∈>-i i T i i T x if b x x if b x ,0,0?? （1），则该训练集可被超平面 0=-b x T ?分开。 （一）、平分最近点法 求两个凸包集中的最近点d c ,'，做d c ,'的垂直平分面x ，即为所求。 02 )(2 22 2 =-- -?-=-d c x d c x d x c T ，则d c -=?，2 ) ()(d c d c b T +-= 。 求d c ,，?? ?? ?≥==≥==∑∑∑∑-=-===. 0,1, . 0,1,1 111 i y i y i i i y i y i i i i i i x d x c αα ααα α
所以2 1 1 2 ∑∑-==-= -i i y i i y i i x x d c αα，只需求出最小的T l ),,(1ααα =。 算法：1）求解. 0,1,1..2121min 1 1 2 12 11≥===-∑∑∑∑∑-===-==i y i y i l i i i i y i i y i i i i i i t s x y x x αααααα；2）求最优超平面0=-b x T ?。 （二）、最大间隔法 附加条件1=?，加上（1）式。记C x C i T x i >=I ∈??min )(1，C x C i T x i <=II ∈??max )(2。 使?????II ∈<-I ∈>-=-= i i T i i T x if b x x if b x t s C C ,0,0,1..2 ) ()()(max 21??????ρ （2） 可以说明在（2）下可以得到一个最优超平面，且该超平面是唯一的。 如何快速生成一个最优超平面？？？ 考虑等价问题：求权向量w 和b ，使?????II ∈-<-I ∈>-i i T i i T x if b x w x if b x w ,1,1，且?最小。 这种写法已经包含最大间隔。 事实上b C C C x if C b x w x if C b x w i i T i i T =+=??????II ∈=+-))()((21),(1),(121021????中心，而w w =?， 故w b C = ，w C C 1 2)()()(21=-=???ρ。 所以（2）式可以转化为求解： 1 )(..min ≥-b x w y t s w i T i （3） 总结，求最优超平面，只需求解： 1 )(..2 1)(min ≥-= Φb x w y t s w w w i T i T （QP1） 对（QP1）构造lagrange 函数： 令∑=---=l i i T i i b x w y w b w L 1 2]1)([21),,(αα，其中0),,(1≥=T l ααα 为lagrange 乘子。 下求L 的鞍点：
模式识别课程大作业报告——支持向量机（SVM）的实现 ： 学号： 专业： 任课教师： 研究生导师：
容摘要 支持向量机是一种十分经典的分类方法，它不仅是模式识别学科中的重要容，而且在图像处理领域中得到了广泛应用。现在，很多图像检索、图像分类算法的实现都以支持向量机为基础。本次大作业的容以开源计算机视觉库OpenCV 为基础，编程实现支持向量机分类器，并对标准数据集进行测试，分别计算出训练样本的识别率和测试样本的识别率。 本报告的组织结构主要分为3大部分。第一部分简述了支持向量机的原理；第二部分介绍了如何利用OpenCV来实现支持向量机分类器；第三部分给出在标准数据集上的测试结果。
一、支持向量机原理概述 在高维空间中的分类问题实际上是寻找一个超平面，将两类样本分开，这个超平面就叫做分类面。两类样本中离分类面最近的样本到分类面的距离称为分类间隔。最优超平面指的是分类间隔最大的超平面。支持向量机实质上提供了一种利用最优超平面进行分类的方法。由最优分类面可以确定两个与其平行的边界超平面。通过拉格朗日法求解最优分类面，最终可以得出结论：实际决定最优分类面位置的只是那些离分类面最近的样本。这些样本就被称为支持向量，它们可能只是训练样本中很少的一部分。支持向量如图1所示。 图1
图1中，H是最优分类面，H1和H2别是两个边界超平面。实心样本就是支持向量。由于最优超平面完全是由这些支持向量决定的，所以这种方法被称作支持向量机（SVM）。 以上是线性可分的情况，对于线性不可分问题，可以在错分样本上增加一个惩罚因子来干预最优分类面的确定。这样一来，最优分类面不仅由离分类面最近的样本决定，还要由错分的样本决定。这种情况下的支持向量就由两部分组成：一部分是边界支持向量；另一部分是错分支持向量。 对于非线性的分类问题，可以通过特征变换将非线性问题转化为新空间中的线性问题。但是这样做的代价是会造成样本维数增加，进而导致计算量急剧增加，这就是所谓的“维度灾难”。为了避免高维空间中的计算，可以引入核函数的概念。这样一来，无论变换后空间的维数有多高，这个新空间中的线性支持向量机求解都可以在原空间通过核函数来进行。常用的核函数有多项式核、高斯核（径向基核）、Sigmoid函数。 二、支持向量机的实现 OpenCV是开源计算机视觉库，它在图像处理领域得到了广泛应用。OpenCV中包含许多计算机视觉领域的经典算法，其中的机器学习代码部分就包含支持向量机的相关容。OpenCV中比较经典的机器学习示例是“手写字母分类”。OpenCV中给出了用支持向量机实现该示例的代码。本次大作业的任务是研究OpenCV中的支持向量机代码，然后将其改写为适用于所有数据库的通用程序，并用标准数据集对算法进行测试。本实验中使用的OpenCV版本是2.4.4，实验平台为Visual Studio 2010软件平台。 OpenCV读取的输入数据格式为“.data”文件。该文件记录了所有数据样
支持向量机算法推导及其分类的算法实现 摘要：本文从线性分类问题开始逐步的叙述支持向量机思想的形成，并提供相应的推导过程。简述核函数的概念，以及kernel在SVM算法中的核心地位。介绍松弛变量引入的SVM算法原因，提出软间隔线性分类法。概括SVM分别在一对一和一对多分类问题中应用。基于SVM在一对多问题中的不足，提出SVM 的改进版本DAG SVM。 Abstract：This article begins with a linear classification problem, Gradually discuss formation of SVM, and their derivation. Description the concept of kernel function, and the core position in SVM algorithm. Describes the reasons for the introduction of slack variables, and propose soft-margin linear classification. Summary the application of SVM in one-to-one and one-to-many linear classification. Based on SVM shortage in one-to-many problems, an improved version which called DAG SVM was put forward. 关键字：SVM、线性分类、核函数、松弛变量、DAG SVM 1. SVM的简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。 对于SVM的基本特点，小样本，并不是样本的绝对数量少，而是与问题的复杂度比起来，SVM算法要求的样本数是相对比较少的。非线性，是指SVM擅长处理样本数据线性不可分的情况，主要通过松弛变量和核函数实现，是SVM 的精髓。高维模式识别是指样本维数很高，通过SVM建立的分类器却很简洁，只包含落在边界上的支持向量。
SVM 支持向量机 目录 一、简介 (1) 二、线性分类器 (3) 三、分类间隔指标 (4) 四、线性分类器的求解 (8) 五、核函数 (9) 六、松弛变量 (11) 七、惩罚因子C (15) 八、SVM用于多类分类 (17) 九、SVM的计算复杂度 (19) 一、简介 支持向量机在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。 支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础 上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力（或称泛化能力）。 以下逐一分解并解释一下：统计机器学习之所以区别于传统机器学习的本质，就在于统计机器学习能够精确的给出学习效果，能够解答需要的样本数等等一系列问题。与统计机器学习的精密思维相比，传统的机器学习基本上属于摸着石头过河，用传统的机器学习方法构造分类系统是一种技巧，一个人做的结果可能很好，另一个人差不多的方法做出来却很差，缺乏指导和原则。 VC维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。SVM关注的是VC维，和样本的维数是无关（甚至样本可以是上万维的，这使得SVM很适合用于解决文本分类的问题，也因此引入了核函数）。 结构风险最小：机器学习本质上就是对问题真实模型的逼近（我们选择一个我们认为比较好的近似模型作为假设），而真实模型是未知的。假设与问题真实解之间的误差，叫做风险（更严格的说，误差的累积叫做风险）。我们选择了一个假设（即分类器）之后，我们可以用某些可以掌握的量来逼近误差，最直观的方法就是使用分类器在样本数据上的分类的结果与真实结果（样本是已标注过的数据，即准确的数据）之间的差值来表示。这个差值叫做经验风险Remp(w)。
. . 实验报告 实验名称：机器学习：线性支持向量机算法实现 学员：张麻子学号： *********** 培养类型：硕士年级： 专业：所属学院：计算机学院 指导教员： ****** 职称：副教授 实验室：实验日期：
. . 一、实验目的和要求 实验目的：验证SVM（支持向量机）机器学习算法学习情况 要求：自主完成。 二、实验内容和原理 支持向量机（Support V ector Machine, SVM）的基本模型是在特征空间上找到最 佳的分离超平面使得训练集上正负样本间隔最大。SVM是用来解决二分类问题的有监督学习算法。通过引入了核方法之后SVM也可以用来解决非线性问题。 但本次实验只针对线性二分类问题。 SVM算法分割原则：最小间距最大化，即找距离分割超平面最近的有效点距离超平面距离和最大。 对于线性问题： w T x+b=0 假设存在超平面可最优分割样本集为两类，则样本集到超平面距离为： ρ = min{|w T x+b| ||w|| }= a ||w|| 需压求取： max a ||w|| s.t. y i(w T x+b)≥a 由于该问题为对偶问题，可变换为： min 1 2 ||w||2 s.t. y i(w T x+b)≥1 可用拉格朗日乘数法求解。 但由于本实验中的数据集不可以完美的分为两类，即存在躁点。可引入正则化参数Ｃ，用来调节模型的复杂度和训练误差。
. . min 1 2||w||2+C ∑εi s.t. y i (w T x +b)≥1?εi , εi >0 作出对应的拉格朗日乘式： 对应的ＫＫＴ条件为： 故得出需求解的对偶问题： {min 1∑∑αi αj y i y j (x i T x j )?∑αi s.t. ∑αi y j = 0 , C≥αi ≥0, 本次实验使用python 编译器，编写程序，数据集共有２７０个案例，挑选其中70%作为训练数据，剩下30%作为测试数据。进行了两个实验，一个是取Ｃ值为１，直接进行ＳＶＭ训练；另外一个是利用交叉验证方法，求取在前面情况下的最优Ｃ值。 三、实验器材 实验环境：windows7操作系统+python 编译器。
支持向量机SVM分类算法 SVM的简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中[10]。 支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力[14]（或称泛化能力）。 以上是经常被有关SVM 的学术文献引用的介绍，我来逐一分解并解释一下。 Vapnik是统计机器学习的大牛，这想必都不用说，他出版的《Statistical Learning Theory》是一本完整阐述统计机器学习思想的名著。在该书中详细的论证了统计机器学习之所以区别于传统机器学习的本质，就在于统计机器学习能够精确的给出学习效果，能够解答需要的样本数等等一系列问题。与统计机器学习的精密思维相比，传统的机器学习基本上属于摸着石头过河，用传统的机器学习方法构造分类系统完全成了一种技巧，一个人做的结果可能很好，另一个人差不多的方法做出来却很差，缺乏指导和原则。所谓VC维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。正是因为SVM关注的是VC维，后面我们可以看到，SVM解决问题的时候，和样本的维数是无关的（甚至样本是上万维的都可以，这使得SVM很适合用来解决文本分类的问题，当然，有这样的能力也因为引入了核函数）。 结构风险最小听上去文绉绉，其实说的也无非是下面这回事。 机器学习本质上就是一种对问题真实模型的逼近（我们选择一个我们认为比较好的近似模型，这个近似模型就叫做一个假设），但毫无疑问，真实模型一定是不知道的（如果知道了，我们干吗还要机器学习？直接用真实模型解决问题不就可以了？对吧，哈哈）既然真实模型不知道，那么我们选择的假设与问题真实解之间究竟有多大差距，我们就没法得知。比如说我们认为宇宙诞生于150亿年前的一场大爆炸，这个假设能够描述很多我们观察到的现象，但它与真实的宇宙模型之间还相差多少？谁也说不清，因为我们压根就不知道真实的宇宙模型到底是什么。 这个与问题真实解之间的误差，就叫做风险（更严格的说，误差的累积叫做风险）。我们选择了一个假设之后（更直观点说，我们得到了一个分类器以后），真实误差无从得知，但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间的差值来表示。这个差值叫做经验风险Remp(w)。以前的机器学习方法都把经验风险最小化作为努力的目标，但后来发现很多分类函数能够在样本集上轻易达到100%的正确率，在真实分类时却一塌糊涂（即所谓的推广能力差，或泛化能力差）。此时的情况便是选择了一个足够复杂的分类函数（它的VC维很高），能够精确的记住每一个样本，但对样本之外的数据一律分类错误。回头看看经验风险最小化原则我们就会发现，此原则适用的大前提是经验风险要确实能够逼近真实风险才行（行话叫一致），但实际上能逼近么？答案是不能，因为样本数相对于现实世界要分类的文本数来说简直九牛
SVM算法推导及其分类的算法实现 摘要：本文从线性分类问题开始逐步的叙述支持向量机思想的形成，并提供相应的推导过程。简述核函数的概念，以及kernel在SVM算法中的核心地位。介绍松弛变量引入的SVM算法原因，提出软间隔线性分类法。概括SVM分别在一对一和一对多分类问题中应用。基于SVM在一对多问题中的不足，提出SVM 的改进版本DAG SVM。 Abstract：This article begins with a linear classification problem, Gradually discuss formation of SVM, and their derivation. Description the concept of kernel function, and the core position in SVM algorithm. Describes the reasons for the introduction of slack variables, and propose soft-margin linear classification. Summary the application of SVM in one-to-one and one-to-many linear classification. Based on SVM shortage in one-to-many problems, an improved version which called DAG SVM was put forward. 关键字：SVM、线性分类、核函数、松弛变量、DAG SVM 1. SVM的简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。 对于SVM的基本特点，小样本，并不是样本的绝对数量少，而是与问题的复杂度比起来，SVM算法要求的样本数是相对比较少的。非线性，是指SVM擅长处理样本数据线性不可分的情况，主要通过松弛变量和核函数实现，是SVM 的精髓。高维模式识别是指样本维数很高，通过SVM建立的分类器却很简洁，只包含落在边界上的支持向量。
svm分类算法 一、数据源说明 1、数据源说远和理解： ticeval2000.txt: 这个数据集是需要预测（ 4000个客户记录）的数据集。它和 ticdata2000.txt它具有相同的格式，只是没有最后一列的目标记录。我们只希望返回预测 目标的列表集，所有数据集都用制表符进行分隔。共有4003（自己加了三条数据），根据要 求，用来做预测。 tictgts2000.txt：最终的目标评估数据。这是一个实际情况下的目标数据，将与我们预 测的结果进行校验。我们的预测结果将放在result.txt文件中。 数据集理解：本实验任务可以理解为分类问题，即分为2类，也就是数据源的第86列， 可以分为0、1两类。我们首先需要对ticdata2000.txt进行训练，生成model，再根据model 进行预测。 2、数据清理 代码中需要对数据集进行缩放的目的在于： a、避免一些特征值范围过大而另一些特征值范围过小； b、避免在训练时为了计算核函数而计算内积的时候引起数值计算的困难。因此，通常将 数据缩放到 [ -1,1] 或者是 [0,1] 之间。 二、数据挖掘的算法说明 1、 svm算法说明 2、实现过程 在源程序里面，主要由以下2个函数来实现： (1) struct svm_model *svm_train(const struct svm_problem *prob, const struct svm_parameter *param); 该函数用来做训练，参数prob，是svm_problem类型数据，具体结构定义如下： struct svm_problem //存储本次参加运算的所有样本(数据集)，及其所属类别。 { int n; //记录样本总数 double *y; //指向样本所属类别的数组 struct svm_node **x; //指向一个存储内容为指针的数组 }; 其中svm_node的结构体定义如下： struct svm_node //用来存储输入空间中的单个特征 { int index; //输入空间序号，假设输入空间数为m double value; //该输入空间的值 }; 所以，prob也可以说是问题的指针，它指向样本数据的类别和输入向量，在内存中的具 体结构图如下： 图1.1libsvm训练时，样本数据在内存中的存放结构 只需在内存中申请n*(m+1)*sizeof(struct svm_node)大小的空间，并在里面填入每个 样本的每个输入空间的值，即可在程序中完成prob参数的设置。参数param，是 svm_parameter数据结构，具体结构定义如下： struct svm_parameter // 训练参数 { int svm_type; //svm类型，
SVM的常用多分类算法概述 摘要：SVM方法是建立在统计学习理论基础上的机器学习方法，具有相对优良的分类性能，是一种非线性分类器。最初SVM是用以解决两类分类问题，不能直接用于多类分类，当前已经有许多算法将SVM推广到多类分类问题，其中最常用两类：OAA和OAO算法，本文主要介绍这两类常用的多分类算法。 关键词：SVM；多分类；最优化 自从90年代初V. Vapnik提出经典的支持向量机理论（SVM），由于其完整的理论框架和在实际应用中取得的很多好的效果，在模式识别、函数逼近和概率密度估计领域受到了广泛的重视。SVM方法是建立在统计学习理论基础上的机器学习方法，具有相对优良的分类性能。SVM是一种非线性分类器。它的基本思想是将输入空间中的样本通过某种非线性函数关系映射到一个特征空间中，使两类样本在此特征空间中线性可分，并寻找样本在此特征空间中的最优线性区分平面。它的几个主要优点是可以解决小样本情况下的机器学习问题，提高泛化性能，解决高维问题、非线性问题，可以避免神经网络结构选择和局部极小点问题。 1. SVM方法 若样本集Q={（x i，y i）|i=1,……,L}∈R d*{-1,+1}是线性可分的。则存在分类超平面w T x+b=0,x∈R d对样本集Q中任一（x i，y i）都满足： 在空间R d中样本x=（x1，…, x d）r到分类超平面的距离d=|w T*x+b|/||w||，其中 ||w||= . 当存在x 使得w T x i+b=±1, 则图1中超平面的分类间隔 margin = 2/ ‖w ‖。 使分类间隔margin 最大的超平面即为最优分类超平面。寻找最优分类超平面的问题将转化为求如下一个二次规划问题: minΦ( w) =1/2‖w ‖ 满足约束条件： y i ( w T x i + b) ≥1 , i = 1 ,2 , ?, L 采用Lagrange 乘子转换为一个对偶问题,形式如下: 满足约束条件:
东北大学 研究生考试试卷 考试科目：信号处理的统计分析方法 课程编号：09601513 阅卷人: 刘晓志 考试日期：2012年11月07日 姓名：赵亚楠 学号：1001236 注意事项 1.考前研究生将上述项目填写清楚. 2.字迹要清楚,保持卷面清洁. 3.交卷时请将本试卷和题签一起上交. 4.课程考试后二周内授课教师完成评卷工作,公共课成绩单与试卷交研究生院培养办公室, 专业课成绩单与试卷交各学院,各学院把成绩单交研究生院培养办公室. 东北大学研究生院培养办公室
目录 一、SVM的产生与发展3 二、支持向量机相关理论4 （一）统计学习理论基础4 （二）SVM原理4 1．最优分类面和广义最优分类面5 2．SVM的非线性映射7 3．核函数8 三、支持向量机的应用研究现状9（一）人脸检测、验证和识别9（二）说话人／语音识别10 （三）文字／手写体识别10 （四）图像处理11 （五）其他应用研究11 四、结论和讨论12
一、SVM 的产生与发展 自1995年Vapnik 在统计学习理论的基础上提出SVM 作为模式识别的新方法之后，SVM 一直倍受关注。同年，Vapnik 和Cortes 提出软间隔(soft margin)SVM ，通过引进松弛变量i ξ度量数据i x 的误分类(分类出现错误时i ξ大于0)，同时在目标函数中增加一个分量用来惩罚非零松弛变量(即代价函数)，SVM 的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程；1996年，Vapnik 等人又提出支持向量回归 (Support Vector Regression ，SVR)的方法用于解决拟合问题。SVR 同SVM 的出发点都是寻找最优超平面，但SVR 的目的不是找到两种数据的分割平面，而是找到能准确预测数据分布的平面，两者最终都转换为最优化问题的求解；1998年，Weston 等人根据SVM 原理提出了用于解决多类分类的SVM 方法(Multi-Class Support VectorMachines ，Multi-SVM)，通过将多类分类转化成二类分类，将SVM 应用于多分类问题的判断：此外，在SVM 算法的基本框架下，研究者针对不同的方面提出了很多相关的改进算法。例如，Suykens 提出的最小二乘支持向量机 (Least Square Support VectorMachine ，LS —SVM)算法，Joachims 等人提出的SVM-1ight ，张学工提出的中心支持向量机 (Central Support Vector Machine ，CSVM)，Scholkoph 和Smola 基于二次规划提出的v-SVM 等。此后，台湾大学林智仁(Lin Chih-Jen)教授等对SVM 的典型应用进行总结，并设计开发出较为完善的SVM 工具包，也就是LIBSVM(A Library for Support Vector Machines)。上述改进模型中，v-SVM 是一种软间隔分类器模型，其原理是通过引进参数v ，来调整支持向量数占输入数据比例的下限，以及参数ρ来度量超平面偏差，代替通常依靠经验选取的软间隔分类惩罚参数，改善分类效果；LS-SVM 则是用等式约束代替传统SVM 中的不等式约束，将求解QP 问题变成解一组等式方程来提高算法效率；LIBSVM 是一个通用的SVM 软件包，可以解决分类、回归以及分布估计等问题，它提供常用的几种核函数可由用户选择，并且具有不平衡样本加权和多类分类等功能，此外，交叉验证(cross validation)方法也是LIBSVM 对核函数参数选取问题所做的一个突出贡献；SVM-1ight 的特点则是通过引进缩水(shrinking)逐步简化QP 问题，以及缓存(caching)技术降低迭代运算的计算代价来解决大规模样本条件下SVM 学习的复杂性问题。
排序学习中的Ranking SVM算法研究 【摘要】本文详细分析了基于支持向量机的排序学习算法Ranking SVM，通过选取不同的惩罚参数在OHSUMED数据集进行实验，衡量了算法在评价准则MAP和NDCG@n下的性能。 【关键词】排序学习；排序支持向量机；算法 Researh of Ranking SVM Algorithm in Learning to Rank DING Wei-min （Weifang University，Weifang Shandong 261061，China） 【Abstract】The paper gives a detailed analysis about the algorithm of Ranking SVM.By experimenting with different penalty parameters on the data set of OHSUMED，the paper also gives the performance in the evaluation criteria of MAP and NDCG@n. 【Key words】Learning to rank；Ranking SVM；Algorithm 0 引言 目前，对于互联网上海量的资源，人们主要通过向搜索引擎提交查询请求获取所需要的信息。搜索引擎根据用户交互组件收到的请求对网页索引数据库检索并将结果交付排序组件进行排序处理，最终以网页排序列表的形式呈现给用户[1]。虽然网页排序列表集合仍十分巨大，实际上用户访问的网页数量却很少，如文献[2]通过分析用户点击数据的日志信息，得到用户点击网页排名的平均值基本在第六条记录左右。因此，如何将相关性强的网页排在列表的前面，而将相关性弱的网页排在后边是搜索引擎排序组件中排序算法需要解决的主要问题，本文在分析排序学习算法Ranking SVM基础上，通过在数据集OHSUMED进行实验，给出算法在评价准则MAP和NDCG@n下的性能。 1 排序学习与Ranking SVM算法[3，4] 排序学习的目的通过使用训练数据和机器学习技术自动创建排序模型。在排序学习中典型的设置是将特征向量和有序分类作为训练数据。通过在训练数据上进行学习得到排序模型，然应用到测试数据上。[5] Ranking SVM算法是通过在训练集构造样本有序数据对的方式将排序问题转化为应用支持向量机方法解决的二分类问题。具体描述为：针对训练集合构造有序数据对集合S={（x■■，x■■），z■}，x■■，x■■表示针对同一查询的返回文档，如果x■■，x■■组成顺序对，则z■值为+1表示。如果为逆序对，则z■值为
机器学习课程作业（1） 提交截止日期：2017年10月10日周二 1. 一个优化问题的原问题（Prime Problem ）与对偶问题（Dual Problem ）定义如下： 原问题 Minimize: ()f ω Subject to: ()0,1,2,...,i g i K ω≤= ()0,1,2,...,i h i M ω== 对偶问题 定义 ()()()()()()()11,,K M T T i i i i i i L f g h f g h ωαβωαωβωωαωβω===++=++∑∑ 对偶问题为： Maximize: ()(),inf ,,L ωθαβωαβ= Subject to: 0,1,2,...,i i K α≥= (a) 证明：如果*ω是原问题的解，*α，*β是对偶问题的解，则有：()()***,f ωθαβ≥ (b) 证明 (强对偶定理)：如果()g A b ωω=+,()h C d ωω=+，且()f ω为凸函数，即对任意1ω和2ω，有()()()()()121211f f f λωλωλωλω+-≤+-, 则有：()()*** ,f ωθαβ= 2. 求下列原问题的对偶问题 (a) (1l and 2l -norm SVM Classification) : Minimize: 221211 12N N i i i i C C ωδδ==++∑∑ Subject to: 0,1,2,...,i i N δ≥= ()1T i i i y x b ω?δ??+≥-??
(b) (SVM regression): Minimize: ()()2221211 12N N i i i i i i C C ωδζδζ==++++∑∑ Subject to: (),1,2,...,T i i i x b y i N ω?εδ+-≤+= (),1,2,...,T i i i y x b i N ω?εζ--≤+= 0i δ≥, 0i ζ≥ (c) (Kernel Ridge Regression): Minimize: 221 12N i i C ωδ=+∑ Subject to: (),1,2,...,T i i i y x i N ω?δ-== (d) (Entropy Maximization Problem): Minimize: ()1log N i i i x x =∑ Subject to: T x b ω≤ 11N i i x ==∑ 3. 如图所示，平面上有N 个点12{,,...,}N x x x ，求一个半径最小的圆，使之能包含这些点。 图1. 平面上N 个点，求最小的圆包含这些点。 (a) 写出这个优化问题的数学表达式。 (b) 写出(a)的对偶问题。 (c) 编写程序求解这个问题（选做）
支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年 首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的 优势，并能够推广应用到函数拟合等其他机器学习问题中。 正是由于SVM具有很多独特的优势，基于SVM分类器在很多时候都具有 较好的拟合作用。本文对SVM算法在行人检测项目实践中的应用进行详细讲解，同时给出调用OpenCV分类器及可视化的代码实现，便于大家学习实践。 目前的行人检测基本上都是基于法国研究人员Dalal在2005的CVPR发 表的HOG+SVM的行人检测算法(Histograms of Oriented Gradients for Human Detection, Navneet Dalel,Bill Triggs, CVPR2005)。HOG+SVM作 为经典算法也集成到OpenCV里面去了，可以直接调用实现行人检测。 一、HOG特征描述符 HOG（Histogram of Oriented Gradients）HOG特征在对象检测与模式 匹配中是一种常见的特征提取技术（深度学习之前），是基于本地像素块进 行特征直方图提取的一种算法，对像局部的变形与光照影响有很好的稳定性，最初是用HOG特征来识别人像，通过HOG特征提取+SVM训练，可以得到很好 的效果，OpenCV已经有相应的接口。 HOG特征是在2005年CVPR的会议发表，在图像手工特征提取方面具有里 程碑式的意义，当时在行人检测领域获得了极大成功。 1.1 主要思想 局部目标的外表和形状可以被局部梯度的分布很好的描述，即使我们不知 道对应的梯度和边缘的位置。(本质：梯度的统计信息，梯度主要存在于边缘edge或角落corner的地方) 1.2 宏观 特征描述符就是通过提取图像的有用信息，并且丢弃无关信息来简化图像 的表示。HOG特征描述符可以将3通道的彩色图像转换成一定长度的特征向量。那么我们就需要定义什么是“有用的”，什么是“无关的”。这里的“有用”，是指对于什么目的有用，显然特征向量对于观察图像是没有用的，但是它对于 像图像识别和目标检测这样的任务非常有用。当将这些特征向量输入到类似支 持向量机（SVM）这样的图像分类算法中时，会得到较好的结果。那什么样的 “特征”对分类任务是有用，比如我们想检测出马路上的车道线，那么我们可 以通过边缘检测来找到这些车道线，在这种情况下，边缘信息就是“有用的”，而颜色信息是无关的。 方向梯度直方图(HOG)特征描述符常和线性支持向量机(SVM)配合使用， 用于训练高精度的目标分类器。 1.3 微观（硬核） 在HOG特征描述符中，梯度方向的分布，也就是梯度方向的直方图被视作 特征。图像的梯度(x和y导数)非常有用，因为边缘和拐角(强度突变的区域) 周围的梯度幅度很大，并且边缘和拐角比平坦区域包含更多关于物体形状的信息。HOG特征是一种图像局部特征，基本思路是将图像划分为很多小的连通区域，即细胞单元Cell，然后对Cell的梯度幅值和方向进行投票统计，形成基 于梯度特性的直方图。把直方图在图像更大的范围内(又名区间或者Block)进 行归一化。归一化的块描述符叫做HOG描述子feature descriptor。将检测窗