0
| 本文作者： AI研習(xí)社 | 2017-05-14 14:34 |
雷鋒網(wǎng)按：本文作者謝輝，原文載于作者個(gè)人博客，雷鋒網(wǎng)已獲授權(quán)。
支持向量機(jī)SVM(Support Vector Machine)是一種有監(jiān)督的學(xué)習(xí)模型，它的核心有兩個(gè)：一、核函數(shù)(kernel trick)；二、序列最小優(yōu)化算法SMO（Sequential minimal optimization）是John Platt在1996年發(fā)布的用于訓(xùn)練SVM的有效算法。本文不打算細(xì)化SVM支持向量機(jī)的詳細(xì)推倒算法，只涉及以上兩點(diǎn)的內(nèi)容做一個(gè)說(shuō)明，最后給出算法實(shí)現(xiàn)和一個(gè)實(shí)驗(yàn)對(duì)比圖。
核函數(shù)在處理復(fù)雜數(shù)據(jù)時(shí)效果顯著，它的做法是將某一個(gè)維度的線性不可分?jǐn)?shù)據(jù)采取核函數(shù)進(jìn)行特征空間的隱式映射到高維空間，從而在高維空間將數(shù)據(jù)轉(zhuǎn)化為線性可分，最后回歸到原始維度空間實(shí)施分類(lèi)的過(guò)程，常見(jiàn)的幾個(gè)核函數(shù)如下：
多項(xiàng)式核：
高斯核（徑向基函數(shù)）:
線性核：
即是兩個(gè)矩陣空間的內(nèi)積。
SMO的主要兩個(gè)步驟就是：
1、選擇需要更新的一對(duì)α，采取啟發(fā)式的方式進(jìn)行選擇，以使目標(biāo)函數(shù)最大程度的接近其全局最優(yōu)值；
2、將目標(biāo)函數(shù)對(duì)α進(jìn)行優(yōu)化，以保持其它所有α不變。
以上是兩個(gè)基本步驟，實(shí)現(xiàn)具體推到公式如下：
所需要收到的約束條件為：
同時(shí)更新α，要求滿(mǎn)足如下條件，就可以保證為0的約束
消去α可得
其中
u 的表達(dá)式為：
y為第i個(gè)特征因素的真實(shí)標(biāo)簽值
之后考慮約束條件 0<α<c 則
約束條件的線性表示
依據(jù) y 同號(hào)或是異號(hào)，可得出上下兩個(gè)邊界為
對(duì)于α有
對(duì)于α首先可以通過(guò)E求得j，之后計(jì)算方式可為:
而b的更新為
其中
每次更新完和都需要重新計(jì)算b以及對(duì)應(yīng)的和
有了以上的公式，代碼實(shí)現(xiàn)就比較簡(jiǎn)單了。
完整的Platt-smo算法實(shí)現(xiàn)入口:
public SvmResult plattSmo(final SvmResult svmResult) {
double b = svmResult.getB();
double[] alphas = svmResult.getAlphas();
for(int i=0;i<featuresArray.length;i++){
double ei = this.calcEk(i, alphas, b);
if (((lablesArray[i] * ei < -tolerFactor)
&& (alphas[i] < penaltyFactor))
|| ((lablesArray[i] * ei > tolerFactor) && (alphas[i] > 0))) {
double[] jSelected = this.selectJ(i, ei, alphas, b); //啟發(fā)式實(shí)現(xiàn)j的選擇
int j = (int) jSelected[0];
double ej = jSelected[1];
double alphaIold = alphas[i];
double alphaJold = alphas[j];
double L = 0;
double H = 0;
//邊界計(jì)算
if (lablesArray[i] != lablesArray[j]) {
L = Math.max(0, alphas[j] - alphas[i]);
H = Math.min(penaltyFactor, penaltyFactor + alphas[j]
- alphas[i]);
} else {
L = Math.max(0, alphas[j] + alphas[i] - penaltyFactor);
H = Math.min(penaltyFactor, alphas[j] + alphas[i]);
}
if (L == H) {
logger.info("L==H");
} else {
double eta = (2.0 * this.kernelArray[i][j] - this.kernelArray[i][i] - this.kernelArray[j][j]);
if (eta >= 0) {
logger.info("eta>=0");
} else {
//雙向調(diào)整alphas[j]遞減
alphas[j] -= lablesArray[j] * (ei - ej) / eta;
if (alphas[j] > H) {
alphas[j] = H;
}
if (L > alphas[j]) {
alphas[j] = L;
}
//更新ej
this.updateEk(j, alphas, b);
if (Math.abs(alphas[j] - alphaJold) < 0.00001) {
logger.info("j not moving enough");
} else {
//雙向調(diào)整alphas[i]遞減
alphas[i] += lablesArray[j] * lablesArray[i]
* (alphaJold - alphas[j]);
//更新ei
this.updateEk(i, alphas, b);
//計(jì)算b
double b1 = b - ei- lablesArray[i]*(alphas[i]-alphaIold)*this.kernelArray[i][i] - lablesArray[j]*(alphas[j]-alphaJold)*this.kernelArray[i][j];
double b2 = b - ej- lablesArray[i]*(alphas[i]-alphaIold)*this.kernelArray[i][j] - lablesArray[j]*(alphas[j]-alphaJold)*this.kernelArray[j][j];
if ((0 < alphas[i]) && (penaltyFactor > alphas[i])){
b = b1;
}else if ((0 < alphas[j]) && (penaltyFactor > alphas[j])){
b = b2;
}else{
b = (b1 + b2)/2.0;
}
}
}
}
}
}
return new SvmResult(b, alphas);
}
在以上算法里面重點(diǎn)關(guān)注是j的選擇，
J的選擇:
private double[] selectJ(int i,double ei,double[] alphas,double b){
int maxK = -1;
double maxDeltaE = 0;
double ej = 0;
int j = -1;
double[] eiArray= new double[2];
eiArray[0] = 1d;
eiArray[1] = ei;
this.eCache[i] = eiArray;
boolean hasValidEcacheList = false;
for(int k=0;k<this.eCache.length;k++){
if(this.eCache[k][0] > 0){
if(k == i){
continue;
}
hasValidEcacheList = true;
if(k == this.m){
k = m-1;
}
double ek = this.calcEk(k, alphas, b);
double deltaE = Math.abs(ei - ek);
if (deltaE > maxDeltaE){
maxK = k;
maxDeltaE = deltaE;
ej = ek;
}
}
}
j = maxK;
if(!hasValidEcacheList || j == -1){
j = this.selectJRandom(i);
ej = this.calcEk(j, alphas, b);
}
if(j == this.m){
j = m-1;
}
return new double[]{j,ej};
}
首選采取啟發(fā)式選擇j，通過(guò)計(jì)算deltaE的最大值來(lái)逼近j的選擇，如果選擇不到就隨機(jī)選擇一個(gè)j值，在j選擇里面有一個(gè)Ek的計(jì)算方式
private double calcEk(int k,double[] alphas,double b){
Matrix alphasMatrix = new Matrix(alphas);
Matrix lablesMatrix = new Matrix(lablesArray);
Matrix kMatrix = new Matrix(this.kernelArray[k]);
double fXk = alphasMatrix.multiply(lablesMatrix).dotMultiply(kMatrix.transpose()).dotValue() + b;
double ek = fXk - (float)this.lablesArray[k];
return ek;
}
下面再介紹一下核函數(shù)計(jì)算方式，本文主要采取徑向基函數(shù)(RBF)實(shí)現(xiàn)，如下:
public double[] kernelTrans(double[][] featuresArray,double[] featuresIArray){
int mCount = featuresArray.length;
double[] kernelTransI = new double[mCount];
Matrix featuresMatrix = new Matrix(featuresArray);
Matrix featuresIMatrix = new Matrix(featuresIArray);
if(trainFactorMap.get("KT").equals("lin")){
Matrix result = featuresMatrix.dotMultiply(featuresIMatrix.transpose());
kernelTransI = result.transpose().values()[0];
}else if(trainFactorMap.get("KT").equals("rbf")){
double rbfDelta = (double)trainFactorMap.get("rbfDelta");
for(int j=0;j<mCount;j++){
Matrix xj = new Matrix(featuresArray[j]);
Matrix delta = xj.reduce(featuresIMatrix);
double deltaValue = delta.dotMultiply(delta.transpose()).dotValue();
kernelTransI[j] = Math.exp((-1.0*deltaValue)/(2*Math.pow(rbfDelta, 2)));
}
}
return kernelTransI;
}
最后看下測(cè)試代碼實(shí)現(xiàn):
double[][] datasvs = new double[m][d[0].length];
double[] labelsvs = new double[m];
double[] alphassvs = new double[m];
int n = 0;
for(int i=0;i<alphas.length;i++){
if(alphas[i] != 0){
datasvs[n] = d[i];
labelsvs[n] = l[i];
alphassvs[n] = alphas[i];
n++;
}
}
//model test
int errorCount = 0;
for(int i=0;i<d.length;i++){
double[] kernelTransI = learner.kernelTrans(datasvs, d[i]);
Matrix kernelTransIM = new Matrix(kernelTransI);
Matrix labelsvsM = new Matrix(labelsvs);
Matrix alphassvsM = new Matrix(alphassvs);
double predict = kernelTransIM.dotMultiply(labelsvsM.multiply(alphassvsM).transpose()).dotValue() + b;
System.out.println(i+"\t"+predict+"\t"+l[i]);
if(AdaBoost.sigmoid(predict) != l[i]){
errorCount++;
}
}
測(cè)試代碼是首先找出所有的支持向量，并提取支持向量下的特征向量和標(biāo)簽向量，采取核函數(shù)進(jìn)行隱式映射，最后計(jì)算預(yù)測(cè)值。
本文采取100個(gè)二維平面無(wú)法線性可分的數(shù)據(jù)集合，如下：
通過(guò)徑向基函數(shù)映射后采取支持向量預(yù)測(cè)計(jì)算得到的可分平面如下
本算法100個(gè)數(shù)據(jù)訓(xùn)練準(zhǔn)確率可達(dá)98%。
注：本文算法均來(lái)自Peter Harrington的《Machine Learning in action》
———————————————————————————————————————
人工智能之神經(jīng)網(wǎng)絡(luò)特訓(xùn)班
20年清華大學(xué)神經(jīng)網(wǎng)絡(luò)授課導(dǎo)師，帶你系統(tǒng)學(xué)習(xí)人工智能之神經(jīng)網(wǎng)絡(luò)！
一站式深入了解深度學(xué)習(xí)的發(fā)展現(xiàn)狀、基本原理和主要方法。
雷鋒網(wǎng)(公眾號(hào)：雷鋒網(wǎng))相關(guān)閱讀：
從理論到實(shí)踐，一文詳解 AI 推薦系統(tǒng)的三大算法
監(jiān)督學(xué)習(xí)最常見(jiàn)的五種算法，你知道幾個(gè)？
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見(jiàn)轉(zhuǎn)載須知。
