機械学習実戦【7】(SMOアルゴリズム実現)

11533 ワード
マシン学習
このブログには、アルゴリズムの紹介やpython実装など、「機械学習実戦」(MachineLearningInAction)の学習過程が記録されています.
SMOアルゴリズム
前の2つの文章はSVMの原理を紹介し、導き出した結果、原始的な問題は以下のように転化した.
minα∑i=1n12∑i,j=1nαiαjyiyjK(xi,xj)−αis.t.,0≤αi≤C,i=1,...,n∑i=1naiyi=0
SMOアルゴリズムはこの問題を解決するために用いられ,これらを解く.
α その後、超平面のパラメータはこれらを通過することができます.
α 計算する.
にじげんさいてきか
SMOアルゴリズムの核心は,元のn個のパラメータの最適化問題を多くの小さなサブ問題に分割し,その中の2個のパラメータのみを最適化して他のパラメータを固定するたびに,2個のパラメータの最適化が速く,最終アルゴリズムの効率が非常に高いことである.n個のパラメータ(α1,...,αn)で選択α1とα1最適化を行い、その他のパラメータはすべて定数と見なされ、元の問題化は以下のように簡略化される.
minΨ(α1,α2)=12K11α21+12K22α22+K12y1y2α1α2−(α1+α2)+y1v1α1+y2v2α2
次のようになります.
vi=∑j=3nαjyjKij=f(xi)−∑j=12αjyjKij−b,i=1,2
次の条件は、次のとおりです.
α1y1+α2y2=−∑i=3nαiyi=ζ
上式の
α1,取得:
minΨ(α2)=12K11(ζ−α2y2)+12K22α22+K12y2(ζ−α2y2)α2−α2−(ζ−α2y2)y1+v1(ζ−α2y2)+y2v2α2
上式ガイド:
∂Ψ(α2)∂α2=(K11+K22−2K12)α2+K12y2ζ−K11y2ζ+y1y2−1−v1y2+v2y2=0
持ち込み
ζ=αold1y1+αold 2 y 2化簡略化:
αnew,unclipped2=αold2+y2(E2−E1)η
ここで、Eは誤差を表す.
Ei=f(xi)−yi
η=K11+K22−2K12
デトリム
上式で計算されたα2境界(0-C)の外にある可能性があるので,結果をトリミング(clip)する必要があり,2つの場合を算出できる.α2の上下境界:y 1≠y 2の場合:L=max(0,αold2−αold1)H=min(C,C+αold2−αold 1)y 1=y 2の場合:L=max(0,αold2+αold1−C)H=min(C,αold2−αold 1)この対α2トリミングを行うと、さらに計算できますα1 .
bの更新
各反復の過程で現在のモデルの予測関数値f(x)を計算する必要があるため、次回の反復で使用するためにbを計算する必要があり、更新時にはいくつかの場合がある.0<α1パラメータのイニシアチブ選択
1番目のパラメータはkkt条件に違反するパラメータを選択し、2番目のパラメータは更新スパンをより大きくするパラメータを選択します.
最初のパラメータの決定(外部ループ):
kkt条件:
αi=0⇒yiui≥1
αi=C⇒yiui≤1
0<αi外部サイクルでは、サンプルセット全体を巡回し、kkt条件に違反するα 最初のパラメータとして選択して更新し、終了後に非境界サンプルセット(0<を満たす)を複数回繰り返します.α2番目のパラメータの決定(内部ループ):
2番目のパラメータは、更新スパンの大きさに基づいて選択するが、η 計算量が大きいので、更新スパンは、近似的に|E 2−E 1|で測定される.すなわち、第1のパラメータが決定された場合、|E 2−E 1|が最大となるように、第2のパラメータが選択される.2番目のパラメータの選択は、まず非境界サンプルセットで行い、十分な更新スパンを持つパラメータが見つからない場合は、全体のサンプルセットで探し、見つからない場合は最初のパラメータを再選択します.
python実装
#                
class optStruct:
    def __init__(self,dataMatIn, classLabels, C, toler, kTup):
        #      
        self.X = dataMatIn
        #      
        self.labelMat = classLabels
        #   C，          
        self.C = C
        #   kkt        
        self.tol = toler
        #    
        self.m = shape(dataMatIn)[0]
        #       
        self.alphas = mat(zeros((self.m,1)))
        self.b = 0
        #     ，            
        self.eCache = mat(zeros((self.m,2)))
        #          
        self.K = mat(zeros((self.m,self.m)))
        for i in range(self.m):
            self.K[:,i] = kernelTrans(self.X, self.X[i,:], kTup)

#     
def calcEk(oS, k):
    fXk = float(multiply(oS.alphas,oS.labelMat).T*oS.K[:,k] + oS.b)
    Ek = fXk - float(oS.labelMat[k])
    return Ek

#    ，          
def selectJ(i, oS, Ei):
    maxK = -1; maxDeltaE = 0; Ej = 0
    oS.eCache[i] = [1,Ei]
    #            ，           ，     
    validEcacheList = nonzero(oS.eCache[:,0].A)[0]
    if len(validEcacheList) > 1:
        for k in validEcacheList:
            if k == i: continue
            Ek = calcEk(oS, k)
            deltaE = abs(Ei - Ek)
            if (deltaE > maxDeltaE):
                maxK = k
                maxDeltaE = deltaE
                Ej = Ek
        return maxK, Ej
    else:
        j = selectJrand(i, oS.m)
        Ej = calcEk(oS, j)
    return j, Ej

#     ，         
def innerL(i, oS):
    Ei = calcEk(oS, i)
    #     kkt            ，                    
    if ((oS.labelMat[i]*Ei < -oS.tol) and (oS.alphas[i] < oS.C)) or ((oS.labelMat[i]*Ei > oS.tol) and (oS.alphas[i] > 0)):
        j,Ej = selectJ(i, oS, Ei)
        alphaIold = oS.alphas[i].copy()
        alphaJold = oS.alphas[j].copy()

        if oS.labelMat[i] != oS.labelMat[j]:
            L = max(0, oS.alphas[j] - oS.alphas[i])
            H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i])
        else:
            L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C)
            H = min(oS.C, oS.alphas[j] + oS.alphas[i])

        if L==H:
            print("L==H")
            return 0
        eta = 2.0 * oS.K[i,j] - oS.K[i,i] - oS.K[j,j]
        if eta >= 0:
            print("eta>=0")
            return 0

        #        
        oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta
        oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)
        updateEk(oS, j) #added this for the Ecache

        if abs(oS.alphas[j] - alphaJold) < 0.00001:
            print("j not moving enough")
            return 0

        #        
        oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])
        updateEk(oS, i)

        b1 = oS.b - Ei- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,i] - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[i,j]
        b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,j]- oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[j,j]
        if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]):
            oS.b = b1
        elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]):
            oS.b = b2
        else:
            oS.b = (b1 + b2)/2.0
        return 1
    else:
        return 0

# smo  ，           ，     
def smoP(dataMatIn, classLabels, C, toler, maxIter,kTup = ('lin', 0)):
    oS = optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler, kTup)
    iter = 0
    #                  
    entireSet = True
    alphaPairsChanged = 0
    #    
    while (iter < maxIter) and (alphaPairsChanged > 0 or entireSet):
        alphaPairsChanged = 0
        #        
        if entireSet:
            for i in range(oS.m):        
                alphaPairsChanged += innerL(i,oS)
                print("fullSet, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
            iter += 1
        #         
        else:
            nonBoundIs = nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]
            for i in nonBoundIs:
                alphaPairsChanged += innerL(i,oS)
                print("non-bound, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
            iter += 1
        #                 
        if entireSet: entireSet = False
        elif alphaPairsChanged == 0: entireSet = True
        print("iteration number: %d" % iter)
    return oS.b,oS.alphas

まとめ
smoアルゴリズムは一度に2つのパラメータを選択して更新し,複雑な最適化問題を1つのよく解決された小さな問題に分解して解消する.機械学習実戦書の実装コードはpaperの理論に比べていくつか簡略化されているが,全体の速度にはあまり影響しないが,その誤差キャッシュ方式には問題があるようで,パラメータを更新した後に対応するデータ誤差のみを更新したが,このときの誤差は失効したはずなのに再計算しなかった.他の誤差があまり変わらないためか、大きな影響はないでしょう.
PositiveSSLで中間証明書の扱い
剣指-28.配列に1回現れる数