確率的勾配降下法によるRankSVMの実装

この記事は何？

ランク学習のモデルの一つとしてRankSVMがあります．

RankSVMには様々な最適化手法が提案されていますが，通常のSVMと比較して計算量が大きいため，大きなデータセットに適用するのは難しいと言われています．

一方，D. SculleyによるLarge Scale Learning to Rankでは，
ペアをランダムにサンプリングする確率的勾配降下法によるRankSVMと既存のRankSVM実装を計算速度と予測精度の面から比較しています．

実験結果として，確率的勾配降下法によるRankSVMは既存実装よりも高速かつ，既存実装と同程度の予測精度が得られていました．

この記事では確率的勾配降下法によるRankSVMのpython実装を紹介します．

更新式

Pegasos: Primal Estimated sub-GrAdient SOlver for SVMを参考にすると，確率的勾配降下法によるRankSVMの更新式は以下のように書けます．

${\displaystyle w_{t+1} \leftarrow (1-\frac{1}{t})w_t+ \eta_{t} I [ y_{it} \langle w_t, x_{it} \rangle \lt 1 ] y_{it} x_{it} }$

ここで $I[\cdot]$ はインジケータ関数を表します．これをRankSVMに応用すると，ランダムサンプリングしたペア $(x_{it}^{1}, y_{it}^{1}) , (x_{it}^{2}, y_{it}^{2})$ について， $y_{it}=y_{it}^{1} - y_{it}^{2}, x_{it}=x_{it}^{1} - x_{it}^{2}$ とすることで，先程の更新式を用いることができます．これは，現在の重みベクトルにおける予測で順序を間違えたとき，重みベクトルを更新するという意味になります．

実装

# -*- coding: utf-8 -*-
"""
SPDRankSVM: Stochastic Pairwise Descent RankSVM
"""

import numpy as np


class SPDRankSVM(object):

    def __init__(self, lmd=1e-5, n_iteration=100):
        self.lmd = lmd
        self.n_iteration = n_iteration

    def fit(self, X, ys):
        N, D = X.shape
        self.w = np.zeros(D)

        for i_iteration in range(1, self.n_iteration + 1):
            first_ind = np.random.random_integers(0, N - 1)
            second_ind = np.random.random_integers(0, N - 1)
            pair_x = (X[first_ind], X[second_ind])
            pair_y = (ys[first_ind], ys[second_ind])
            if pair_y[0] > pair_y[1]:
                y_diff = 1
            elif pair_y[1] < pair_y[0]:
                y_diff = -1
            else:
                # 評価値が同じときは重みを更新しない
                continue

            eta = 1. / (self.lmd * i_iteration)
            x_diff = pair_x[0] - pair_x[1]
            # y * <w, x> < 1  -> (1 - eta * lmd) * w + eta * y * x
            # y * <w, x> >= 1 -> (1 - eta * lmd) * w
            self.w *= (1 - eta * self.lmd)
            if y_diff * x_diff.dot(self.w) < 1:
                self.w += eta * y_diff * x_diff

    def predict(self, X):
        return X.dot(self.w)

デモ

sklearnのdatasetsに収録されているdiabetesデータセットを用いて，SVRとRankSVMとで予測精度(ケンドールの順位相関係数)を比較します．

# -*- coding: utf-8 -*-
import numpy as np
from sklearn import datasets, svm
from SPDRankSVM import SPDRankSVM
from scipy import stats

np.random.seed(0)

data = datasets.load_diabetes()
X, ys = data["data"], data["target"]
N_train = 300
X_train, X_test = X[:N_train], X[N_train:]
ys_train, ys_test = ys[:N_train], ys[N_train:]

svr = svm.LinearSVR()
svr.fit(X_train, ys_train)
ranksvm = SPDRankSVM(n_iteration=100000)
ranksvm.fit(X_train, ys_train)

ys_svr_pred = svr.predict(X_test)
ys_ranksvm_pred = ranksvm.predict(X_test)

print("SVR")
print(stats.kendalltau(ys_test, ys_svr_pred))

print("RankSVM")
print(stats.kendalltau(ys_test, ys_ranksvm_pred))

SVR
KendalltauResult(correlation=0.46513316224978862, pvalue=2.1618772811030055e-16)
RankSVM
KendalltauResult(correlation=0.49955041495228963, pvalue=1.1400821070710552e-18)

というわけで，RankSVMの方がケンドールの順位相関係数が高くなりました．