【免费】支持向量机算法很游泳啊资源-CSDN文库

共2个文件

txt：1个

pdf：1个

需积分: 0 186 浏览量 2008-11-25 15:32:38 上传评论收藏 234KB RAR 举报

资源详情

资源评论

资源推荐

收起资源包目录

SVM.rar （2个子文件）

www.pudn.com.txt 218B

smo.pdf 394KB

Sequential Minimal Optimization for SVM

Contents

1 Introduction to Support Vector Machine (SVM) 2

1.1 Linear SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 The dual problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Non-linear SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Imperfect separation . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.5 The KKT conditions . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.6 Checking KKT condition without using threshold b . . . . . . . . 7

2 SMO Algorithm 9

2.1 Optimize two α

’s . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 SMO Algorithm: Updating after a successful optimization step . 13

2.3 SMO Algorithm: Pick two α

’s for optimization . . . . . . . . . . 14

3 C

Implementation 15

3.1 The main routine . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2 The examineExample routine . . . . . . . . . . . . . . . . . . . . 18

3.3 The takeStep routine . . . . . . . . . . . . . . . . . . . . . . . . 20

3.4 Evaluating classiﬁcation function . . . . . . . . . . . . . . . . . . 24

3.5 Functions to compute dot product . . . . . . . . . . . . . . . . . 26

3.6 Kernel functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.7 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.7.1 Get parameters by command line . . . . . . . . . . . . . . 29

3.7.2 Read in data . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.7.3 Saving and loading model parameters . . . . . . . . . . . 34

3.8 Compute error rate . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.9 Multiclass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.10 Makeﬁles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

A The weight vectors of the parallel supporting planes 41

B The objective function of the dual problem 42











Abstract

This is a C

implementation of John C. Platt’s sequential minimal

optimization (SMO) for training a support vector machine (SVM). This

program is based on the pseudocode in Platt (1998).

This is both the documentation and the C

code. It is a NUWEB doc-

ument from which both the L

X ﬁle and the C

ﬁle can be generated.

The documentation is essentially my notes when reading the papers (most

of them being cut-and-paste from the papers).

1 Introduction to Support Vector Machine (SVM)

This introductio to Support Vector Machine for binary classiﬁcation is based on

Burges (1998).

1.1 Linear SVM

First let us look at the linear support vector machine. It is based on the idea

of hyperplane classiﬁer, or linearly separability.

Suppose we have N training data points {(x

, y

), (x

, y

), . . . , (x

, y

)}

where x

∈ R

and y

∈ {±1}. We would like to learn a linear separating

hyperplane classiﬁer:

f(x) = sgn(w · x − b).

Furthermore, we want this hyperplane to have the maximum separating mar-

gin with respect to the two classes. Speciﬁcally, we want to ﬁnd this hyperplane

H : y = w·x−b = 0 and two hyperplanes parallel to it and with equal distances

to it,

: y = w · x − b = +1,

: y = w · x − b = −1,

with the condition that there are no data points between H

and H

, and the

distance between H

and H

is maximized.

For any separating plane H and the corresponding H

and H

, we can always

“normalize” the coeﬃcients vector w so that H

will be y = w · x − b = +1,

and H

will be y = w · x − b = −1. See Appendix A for details.

We want to maximize the distance between H

and H

. So there will be some

positive examples on H

and some negative examples on H

. These examples

are called support vectors because only they participate in the deﬁnition of

the separating hyperplane, and other examples can be removed and/or moved

around as long as they do not cross the planes H

and H

Recall that in 2-D, the distance from a point (x

, y

) to a line Ax+By+C = 0

|Ax

+By

+C|

√

. Similarly, the distance of a point on H

to H : w · x − b = 0

|w·x−b|

kwk

, and the distance between H

and H

kwk

. So, in order

to maximize the distance, we should minimize kwk = w

w with the condition

that there are no data points between H

and H

w · x − b ≥ +1, for positive examples y

= +1,

w · x − b ≤ −1, for negative examples y

= −1.

These two conditions can be combined into

(w · x

− b) ≥ 1.

So our problem can be formulated as

min

w,b

w subject to y

(w · x

− b) ≥ 1.

This is a convex, quadratic programming problem (in w, b), in a convex set.

Introducing Lagrange multipliers α

, α

, . . . , α

≥ 0, we have the following

Lagrangian:

L (w, b, α) ≡

w −

i=1

(w · x

− b) +

i=1

1.2 The dual problem

We can solve the Wolfe dual instead: maximize L (w, b, α) with respect to α,

subject to the constraints that the gradient of L (w, b, α) with respect to the

primal variables w and b vanish:

∂L

∂w

= 0, (1)

∂L

∂b

= 0, (2)

and that

α ≥ 0.

From Equations 1 and 2, we have

w =

i=1

= 0.

Substitute them into L (w, b, α), we have

≡

i=1

−

i,j

· x

in which the primal variables are eliminated.

When we solve α

, we can get w =

i=1

, (we will later show how to

compute the threshold b), and we can classify a new object x with

f(x) = sgn(w · x + b)

= sgn((

i=1

) · x + b)

= sgn(

i=1

· x) + b).

Please note that in the objective function and the solution, the training

vectors x

occur only in the form of dot product.

Before going into the details to how to solve this quadratic programming

problem, let’s extend it in two directions.

1.3 Non-linear SVM

What if the surface separating the two classes are not linear? Well, we can

transform the data points to another high dimensional space such that the data

points will be linearly separable. Let the transformation be Φ(·). In the high

dimensional space, we solve

≡

i=1

−

i,j

Φ(x

) · Φ(x

)

Suppose, in addition, Φ(x

) · Φ(x

) = k(x

, x

). That is, the dot product in

that high dimensional space is equivalent to a kernel function of the input space.

So we need not be explicit about the transformation Φ(·) as long as we know

that the kernel function k(x

, x

) is equivalent to the dot product of some other

high dimensional space. There are many kernel functions that can be used this

way, for example, the radial basis function (Gaussian kernel)

K(x

, x

) = e

−kx

−x

/2σ

The Mercer’s condition can be used to determine if a function can be used

as a kernel function:

There exists a mapping Φ and an expansion

K(x, y) =

Φ(x)

Φ(y)

if and only if, for any g(x) such that

g(x)

dx is ﬁnite,

then

K(x, y)g(x)g(y)dxdy ≥ 0.

1.4 Imperfect separation

The other direction to extend SVM is to allow for noise, or imperfect separation.

That is, we do not strictly enforce that there be no data points between H

and

, but we deﬁnitely want to penalize the data points that cross the boundaries.

The penalty C will be ﬁnite. (If C = ∞, we come back to the original perfect

separating case.)

We introduce non-negative slack variables ξ

≥ 0, so that

w · x

− b ≥ +1 − ξ

for y

= +1,

w · x

− b ≤ −1 + ξ

for y

= −1,

≥ 0, ∀i.

and we add to the objective function a penalizing term:

minimize

w,b,ξ

w + C(

)

where m is usually set to 1, which gives us

minimize

w,b,ξ

w + C

i=1

subject to y

− b) + ξ

− 1 ≥ 0, 1 ≤ i ≤ N

≥ 0, 1 ≤ i ≤ N

评论收藏

内容反馈

w200888w

粉丝: 0
资源: 1

支持向量机算法很游泳啊

评论0

最新资源

支持向量机算法很游泳啊

评论0

代码 基于SVM支持向量机算法的降水量预测模型代码

支持向量机算法的研究及其应用

基于python的SVM支持向量机算法设计与实现

支持向量机算法及其应用研究

支持向量机算法java数据挖掘算法源码.rar

支持向量机算法的详细推导PPT学习教案.pptx

代码 基于SVM支持向量机算法的降水量预测模型代码.rar

支持向量机matlab算法

支持向量机SVM和支持向量回归SVR算法合集(亲测可用)

支持向量机等各种算法和模型的优点和缺点.docx

一种新的最小二乘支持向量机算法.pdf

基于支持向量机的多分类算法研究

论文研究-支持向量机算法多目标模型选择 .pdf

基于声发射表征冲击地压的粒子群优化支持向量机算法

论文研究-改进的渐进直推式支持向量机算法.pdf

线性支持向量机算法实现matlab

遗传算法优化支持向量机算法

基于SVM支持向量机算法的降水量预测模型代码_SVM_SVM预测_blues1l_基于SVM支持向量机对降水量的预测_降水、_源

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

XCP协议的规范文档

GD32替换STM32注意事项.pdf

NPPJSONViewer.zip

CANoe通过CAPL脚本实现自动测试

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

蓝牙BLE协议中文版.pdf

BaiduOCR.zip

最新资源

代码基于SVM支持向量机算法的降水量预测模型代码

代码基于SVM支持向量机算法的降水量预测模型代码.rar

Qt 5实现串口调试助手（源工程文件、0积分下载）