正定値でないグラム行列を正定値に変換して学習すると精度は変化する？

この記事は何？

カーネル法を用いた機械学習では，データセットに対するグラム行列を生成して学習を行いますが，非正定値カーネルを用いた場合やサンプル間の類似度をカーネルとして用いた場合は，得られるグラム行列が正定値にならない場合があります．
得られたグラム行列が正定値でないとき，何も考えずにそのまま扱ってしまう方法と，正定値に変換してから扱う方法の2つの方法が考えられます．
この記事では，正定値でないグラム行列を正定値となるように変換することで予測精度が変化するかどうかを検証します．

正定値性を満たすように変換する方法

赤穂さんによるカーネル多変量解析 - 岩波書店では，第5.2節で正定値でない類似度･距離からの設計として，次の3つの正定値性を満たすように変換する方法を紹介しています．

グラム行列Kに単位行列のλ倍を加える
グラム行列を固有値展開し，固有値の並んだ対角行列の成分の中で0以下のものを正の小さい値で埋める
指数カーネルを用いる

この記事では，上の2つを実装してみます．

グラム行列Kに単位行列のλ倍を加える方法

$K'=K+\lambda I$ とします．また， $K$ の固有値を $\lambda_i$ ，固有ベクトルを $\textbf{u}_i$ とします．

ここで， $K'=K+\lambda I$ に右から $\textbf{u}_i$ をかけると，
$\begin{eqnarray} K' \textbf{u}_i & = & K \textbf{u}_i + \lambda \textbf{u}_i \\ & = & \lambda_i \textbf{u}_i + \lambda \textbf{u}_i \\ & = & (\lambda_i + \lambda)\textbf{u}_i \end{eqnarray}$
となり， $K'$ の固有値は $K$ の固有値に $\lambda$ が加わったものとなります．

行列の全ての固有値が正であることと，行列が正定値であることは同値であるため，行列の全ての固有値が正となるように $\lambda$ を調整して加えることで正定値性を満たすように変換することができます．

これを実装すると，次のようになります．

def convert_add_lmd(mat, eps=0.0001):
    """
    K' = K + \lmd I
    \lmd is decided as all eigen values are larger than 0
    """
    mat_positive_definite = np.copy(mat)
    eigen_values = np.linalg.eigvals(mat)
    min_eigen_values = np.min(eigen_values)
    if min_eigen_values < 0:
        lmd = -min_eigen_values + eps  # new eigen values are larger than 0
        mat_positive_definite += lmd * np.eye(mat.shape[0])
    return mat_positive_definite

元の行列の最小固有値が正のときは何もしません．最小固有値が負のときは正になるように $\lambda$ を調整します．

固有値分解を用いる方法

$K=PDP^\textrm{T}$ として固有値分解されるとします． $P$ は固有ベクトルが並んだ行列であり， $D$ は対角成分に固有値が並んだ行列です．
ここで， $D$ の対角成分のうち0以下のものを正の小さな値 $\epsilon$ で埋めた行列を $D'$ とします．
得られた $D'$ を用いて， $K'=PD'P^\textrm{T}$ とすると， $K'$ は正定値となります．

これを実装すると，次のようになります．

def convert_with_decomposition(mat, eps=0.0001):
    """
    K' = P D' P^T
    P: eigen vectors matrix
    D: diag eigen values matrix
    D': negative eigen values of D are \epsilon
    """
    eigen_values, eigen_vectors_mat = np.linalg.eig(mat)
    eigen_values[eigen_values <= 0] = eps
    # K' = P D' P^T
    mat_positive_definite = eigen_vectors_mat.dot(np.diag(eigen_values)).dot(eigen_vectors_mat.T)
    return mat_positive_definite

評価

正定値に変換する前と後とで精度が変化するかを検証します．
カーネル関数としてシグモイドカーネルを使います，シグモイドカーネルは正定値カーネルではありません．

データセットとしはscikit-learnのdatasetsモジュールにあるmake_classification関数によって生成します．データサイズを1000としました．

評価は5-fold Cross Validationによる正解率の平均値で行います．

学習器としてSVMを使いました．ハイパーパラメータについて簡単のため，SVMのコストパラメータは1.0，シグモイドカーネルの $\gamma$ パラメータは0.1に固定しています．

結果

正解率の平均値は以下のようになりました．

手法	正解率の平均値
正定値への変換無し	0.830
単位行列のλ倍を加える方法	0.931
固有値分解を用いる方法	0.952

グラム行列を正定値に変換してから学習する方が，予測精度が向上することがわかりました．
ハイパーパラメータチューニングは行っていないのですが，精度が大きく変化することから正定値への変換を考慮する必要があると言えます．

ソースコード

評価に用いたソースコードを載せておきます（jupyter notebookベタ貼り）

# coding: utf-8

# In[1]:

import numpy as np
from sklearn import datasets, metrics, model_selection, svm


# In[2]:

np.random.seed(0)


# In[3]:

def convert_add_lmd(mat, eps=0.0001):
    """
    K' = K + \lmd I
    \lmd is decided as all eigen values are larger than 0
    """
    mat_positive_definite = np.copy(mat)
    eigen_values = np.linalg.eigvals(mat)
    min_eigen_values = np.min(eigen_values)
    if min_eigen_values < 0:
        lmd = -min_eigen_values + eps  # new eigen values are larger than 0
        mat_positive_definite += lmd * np.eye(mat.shape[0])
    return mat_positive_definite


# In[4]:

def convert_with_decomposition(mat, eps=0.0001):
    """
    K' = P D' P^T
    P: eigen vectors matrix
    D: diag eigen values matrix
    D': negative eigen values of D are \epsilon
    """
    eigen_values, eigen_vectors_mat = np.linalg.eig(mat)
    eigen_values[eigen_values <= 0] = eps
    # K' = P D' P^T
    mat_positive_definite = eigen_vectors_mat.dot(np.diag(eigen_values)).dot(eigen_vectors_mat.T)
    return mat_positive_definite


# In[5]:

X, ys = datasets.make_classification(n_samples=1000)


# In[6]:

kf = model_selection.StratifiedKFold(n_splits=5, shuffle=True)


# In[7]:

# sigmoid kernel is not positive definite
K = metrics.pairwise.sigmoid_kernel(X, gamma=0.1)


# In[8]:

def acc_evaluation(K):
    acc_scores = []
    for train_index, test_index in kf.split(K, ys):
        K_train, K_test = K[train_index][:, train_index], K[test_index][:, train_index]
        ys_train, ys_test = ys[train_index], ys[test_index]
        clf = svm.SVC(kernel="precomputed")
        clf.fit(K_train, ys_train)
        acc_score = metrics.accuracy_score(ys_test, clf.predict(K_test))
        acc_scores.append(acc_score)
    return np.mean(acc_scores)


# In[9]:

# without convert to positive definite
print(acc_evaluation(K))


# In[10]:

# with adding lmd * I
K_added_lmd = convert_add_lmd(K)
print(acc_evaluation(K_added_lmd))


# In[11]:

# with decomposition
K_with_decomposition = convert_with_decomposition(K)
print(acc_evaluation(K_with_decomposition))

その他

アイテム間類似度をグラム行列として使うとき，正定値かどうか気にせずに学習してる例が多いように見えます．
精度があまり出なかったりする場合は，正定値性を満たすように変換してから学習する方が良いかもしれません（必ず精度が上がる保証は無いのですががが）．