注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

Weka开发[27]——SMO源代码分析[3]   

2009-09-19 22:27:41|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

else {

    // Look at endpoints of diagonal

    f1 = SVMOutput(i1, m_data.instance(i1));

    f2 = SVMOutput(i2, m_data.instance(i2));

    v1 = f1 + m_b - y1 * alph1 * k11 - y2 * alph2 * k12;

    v2 = f2 + m_b - y1 * alph1 * k12 - y2 * alph2 * k22;

    double gamma = alph1 + s * alph2;

    Lobj = (gamma - s * L) + L - 0.5 * k11 * (gamma - s * L)

           * (gamma - s * L) - 0.5 * k22 * L * L - s * k12

           * (gamma - s * L) * L - y1 * (gamma - s * L) * v1 - y2

           * L * v2;

    Hobj = (gamma - s * H) + H - 0.5 * k11 * (gamma - s * H)

           * (gamma - s * H) - 0.5 * k22 * H * H - s * k12

           * (gamma - s * H) * H - y1 * (gamma - s * H) * v1 - y2

           * H * v2;

    if (Lobj > Hobj + m_eps) {

       a2 = L;

    } else if (Lobj < Hobj - m_eps) {

       a2 = H;

    } else {

       a2 = alph2;

    }

}

if (Math.abs(a2 - alph2) < m_eps * (a2 + alph2 + m_eps)) {

    return false;

}

       这段代码的解释在Platt论文的47页。In any event, SMO will work even when eta is not negative, in which case the objective function W should be evaluated at each end of the line segment. Only those terms in the objective function that depend on alpha_2 need be evaluated (see equation (12.23)). SMO moves the Lagrange multipliers to the end point with the highest value of the objective function. If the objective function is the same at the both ends and the kernel obeys Mercer’s conditions, then the joint maximization cannot make progress.

       Gamma的计算公式Platt论文的(12.22),LobjHobj就是论文提到的W should be evaluated at each end of the line segment.公式是12.23。下面的if / else if/ else则对应SMO moves the Lagrane multipliers to the end point with the highest value of the objective function. 最后的一个if对应If the objective function is the same at the both ends and the kernel obeys Mercer’s conditions, then the joint maximization cannot make progress.

// To prevent precision problems

if (a2 > C2 - m_Del * C2) {

    a2 = C2;

} else if (a2 <= m_Del * C2) {

    a2 = 0;

}

       精度问题处理代码,m_Del是一个非常小的数,看a2是不是已经可以认为是C2或是0了。

// Recompute a1

a1 = alph1 + s * (alph2 - a2);

 

// To prevent precision problems

if (a1 > C1 - m_Del * C1) {

    a1 = C1;

} else if (a1 <= m_Del * C1) {

    a1 = 0;

}

       Platt的公式12.8,和精度问题的处理。

// Update sets

if (a1 > 0) {

    m_supportVectors.insert(i1);

} else {

    m_supportVectors.delete(i1);

}

if ((a1 > 0) && (a1 < C1)) {

    m_I0.insert(i1);

} else {

    m_I0.delete(i1);

}

if ((y1 == 1) && (a1 == 0)) {

    m_I1.insert(i1);

} else {

    m_I1.delete(i1);

}

if ((y1 == -1) && (a1 == C1)) {

    m_I2.insert(i1);

} else {

    m_I2.delete(i1);

}

if ((y1 == 1) && (a1 == C1)) {

    m_I3.insert(i1);

} else {

    m_I3.delete(i1);

}

if ((y1 == -1) && (a1 == 0)) {

    m_I4.insert(i1);

} else {

    m_I4.delete(i1);

}

if (a2 > 0) {

    m_supportVectors.insert(i2);

} else {

    m_supportVectors.delete(i2);

}

if ((a2 > 0) && (a2 < C2)) {

    m_I0.insert(i2);

} else {

    m_I0.delete(i2);

}

if ((y2 == 1) && (a2 == 0)) {

    m_I1.insert(i2);

} else {

    m_I1.delete(i2);

}

if ((y2 == -1) && (a2 == C2)) {

    m_I2.insert(i2);

} else {

    m_I2.delete(i2);

}

if ((y2 == 1) && (a2 == C2)) {

    m_I3.insert(i2);

} else {

    m_I3.delete(i2);

}

if ((y2 == -1) && (a2 == 0)) {

    m_I4.insert(i2);

} else {

    m_I4.delete(i2);

}

       m_supportVectorsm_I0m_I1m_I2m_I3m_I4是加入i1i2还是删除i1i2。看Keerthi论文的639 对它们的定义,m_supprotVectors是支持向量索引数组,就是乘子大于0的样本索引。

// Update weight vector to reflect change a1 and a2, if linear SVM

if (!m_useRBF && m_exponent == 1.0) {

    Instance inst1 = m_data.instance(i1);

    for (int p1 = 0; p1 < inst1.numValues(); p1++) {

       if (inst1.index(p1) != m_data.classIndex()) {

           m_weights[inst1.index(p1)] += y1 * (a1 - alph1)

                  * inst1.valueSparse(p1);

       }

    }

    Instance inst2 = m_data.instance(i2);

    for (int p2 = 0; p2 < inst2.numValues(); p2++) {

       if (inst2.index(p2) != m_data.classIndex()) {

           m_weights[inst2.index(p2)] += y2 * (a2 - alph2)

                  * inst2.valueSparse(p2);

       }

    }

}

       更新权重向量,Platt的公式12.12

// Update error cache using new Lagrange multipliers

for (int j = m_I0.getNext(-1); j != -1; j = m_I0.getNext(j)) {

    if ((j != i1) && (j != i2)) {

       m_errors[j] += y1 * (a1 - alph1)

              * m_kernel.eval(i1, j, m_data.instance(i1)) + y2

              * (a2 - alph2)

              * m_kernel.eval(i2, j, m_data.instance(i2));

    }

}

       Platt的公式12.11

// Update error cache for i1 and i2

m_errors[i1] += y1 * (a1 - alph1) * k11 + y2 * (a2 - alph2) * k12;

m_errors[i2] += y1 * (a1 - alph1) * k12 + y2 * (a2 - alph2) * k22;

       还是公式12.11,只是k11k12k22没有必要再次计算。

// Update array with Lagrange multipliers

m_alpha[i1] = a1;

m_alpha[i2] = a2;

       更新Lagrange乘子数组。

// Update thresholds

m_bLow = -Double.MAX_VALUE;

m_bUp = Double.MAX_VALUE;

m_iLow = -1;

m_iUp = -1;

for (int j = m_I0.getNext(-1); j != -1; j = m_I0.getNext(j)) {

    if (m_errors[j] < m_bUp) {

       m_bUp = m_errors[j];

       m_iUp = j;

    }

    if (m_errors[j] > m_bLow) {

       m_bLow = m_errors[j];

       m_iLow = j;

    }

}

if (!m_I0.contains(i1)) {

    if (m_I3.contains(i1) || m_I4.contains(i1)) {

       if (m_errors[i1] > m_bLow) {

           m_bLow = m_errors[i1];

           m_iLow = i1;

       }

    } else {

       if (m_errors[i1] < m_bUp) {

           m_bUp = m_errors[i1];

           m_iUp = i1;

       }

    }

}

if (!m_I0.contains(i2)) {

    if (m_I3.contains(i2) || m_I4.contains(i2)) {

       if (m_errors[i2] > m_bLow) {

           m_bLow = m_errors[i2];

           m_iLow = i2;

       }

    } else {

       if (m_errors[i2] < m_bUp) {

           m_bUp = m_errors[i2];

           m_iUp = i2;

       }

    }

}

if ((m_iLow == -1) || (m_iUp == -1)) {

    throw new Exception("This should never happen!");

}

       先在m_I0找看有没有在[m_bLow,m_bUp]之外的值,有则更新,然后在m_I3m_I4m_I1m_I2中对i1i2索引的m_errors判断。

       回到BinarySMO中的buildClassifier

// Set threshold

m_b = (m_bLow + m_bUp) / 2.0;

 

// Save memory

m_kernel.clean();

 

m_errors = null;

m_I0 = m_I1 = m_I2 = m_I3 = m_I4 = null;

       设置阈值,释放空间。

// If machine is linear, delete training data

// and store weight vector in sparse format

if (!m_useRBF && m_exponent == 1.0) {

 

    // We don't need to store the set of support vectors

    m_supportVectors = null;

 

    // We don't need to store the class values either

    m_class = null;

 

    // Clean out training data

    if (!m_checksTurnedOff) {

       m_data = new Instances(m_data, 0);

    } else {

       m_data = null;

    }

 

    // Convert weight vector

    double[] sparseWeights = new double[m_weights.length];

    int[] sparseIndices = new int[m_weights.length];

    int counter = 0;

    for (int i = 0; i < m_weights.length; i++) {

       if (m_weights[i] != 0.0) {

           sparseWeights[counter] = m_weights[i];

           sparseIndices[counter] = i;

           counter++;

       }

    }

    m_sparseWeights = new double[counter];

    m_sparseIndices = new int[counter];

    System.arraycopy(sparseWeights, 0, m_sparseWeights, 0, counter);

    System.arraycopy(sparseIndices, 0, m_sparseIndices, 0, counter);

 

    // Clean out weight vector

    m_weights = null;

 

    // We don't need the alphas in the linear case

    m_alpha = null;

}

       释放空间的代码,和给m_sparseWeightsm_sparseIndices赋值的代码。
  评论这张
 
阅读(1425)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017