# 支持向量机SMO算法求解过程分析

2016/06/27 16:32

## 2. 对核函数进行缓存

#define OFFSET(x, y) 	((x) > (y) ? (((x)+1)*(x) >> 1) + (y) : (((y)+1)*(y) >> 1) + (x))
//...
for (unsigned i = 0; i < count; ++i)
for (unsigned j = 0; j <= i; ++j)
cache[OFFSET(i, j)] = y[i] * y[j] * kernel(x[i], x[j], DIMISION);
//...

## 3. 求解梯度

	for (unsigned i = 0; i < count; ++i)
{
for (unsigned j = 0; j < count; ++j)
gradient[i] += cache[OFFSET(i, j)] * alpha[j];
}

## 5. 制定选取规则

，则，此时应选取

，则，此时应选取,

unsigned x0 = 0, x1 = 1;
//根据梯度选取进行优化的alpha值
{
double gmax = -DBL_MAX, gmin = DBL_MAX;
for (unsigned i = 0; i < count; ++i)
{
if ((alpha[i] < C && y[i] == POS || alpha[i] > 0 && y[i] == NEG) && -y[i] * gradient[i] > gmax)
{
x0 = i;
}
else if ((alpha[i] < C && y[i] == NEG || alpha[i] > 0 && y[i] == POS) && -y[i] * gradient[i] < gmin)
{
x1 = i;
}
}
}


## 6. 开始进行求解

alpha要求在区间[0,C]内，对不符合条件的alpha值进行调整,调整规则如下。

if (y[x0] != y[x1])
{
double coef = cache[OFFSET(x0, x0)] + cache[OFFSET(x1, x1)] + 2 * cache[OFFSET(x0, x1)];
if (coef <= 0) coef = DBL_MIN;
double diff = alpha[x0] - alpha[x1];
alpha[x0] += delta;
alpha[x1] += delta;
unsigned max = x0, min = x1;
if (diff < 0)
{
max = x1;
min = x0;
diff = -diff;
}
if (alpha[max] > C)
{
alpha[max] = C;
alpha[min] = C - diff;
}
if (alpha[min] < 0)
{
alpha[min] = 0;
alpha[max] = diff;
}
}

{
double coef = cache[OFFSET(x0, x0)] + cache[OFFSET(x1, x1)] - 2 * cache[OFFSET(x0, x1)];
if (coef <= 0) coef = DBL_MIN;
double sum = alpha[x0] + alpha[x1];
alpha[x0] += delta;
alpha[x1] -= delta;
unsigned max = x0, min = x1;
if (alpha[x0] < alpha[x1])
{
max = x1;
min = x0;
}
if (alpha[max] > C)
{
alpha[max] = C;
alpha[min] = sum - C;
}
if (alpha[min] < 0)
{
alpha[min] = 0;
alpha[max] = sum;
}
}

for (unsigned i = 0; i < count; ++i)
gradient[i] += cache[OFFSET(i, x0)] * delta0 + cache[OFFSET(i, x1)] * delta1;

## 7.进行权重的计算

double maxneg = -DBL_MAX, minpos = DBL_MAX;
SVM *svm = &bundle->svm;
for (unsigned i = 0; i < count; ++i)
{
double wx = kernel(svm->weight, data[i], DIMISION);
if (y[i] == POS && minpos > wx)
minpos = wx;
else if (y[i] == NEG && maxneg < wx)
maxneg = wx;
}
svm->bias = -(minpos + maxneg) / 2;

2
2 收藏

0 评论
2 收藏
2