Soft Confidence Weightedを実装してみる

データ分析

#機械学習

じょんすみす

2017.12.24

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、小澤です。

当エントリは「Machine Learning Advent Calendar 2017」の24日目のエントリです。

今回は、前回紹介したCWの発展である、Soft Confidence Weighted(以下SCW)を実装させていただきます。

SCWとは

SCWもCWと同様オンラインの線形分類器です。 CWは以下のような制約付きの問題となっていました。

[latex] ({\bf \mu}_{i+1}, \Sigma_{i+1}) = \min D_{KL}( \mathcal{N}({\bf \mu}, \Sigma) || \mathcal{N}({\bf \mu}_i, \Sigma_i) )　\\ st. P(y_i{\bf w}{\bf x}_i) \geq 0) \geq \eta [/latex]

この制約では、常にデータを正解へと導こうとするため、ノイズに対して弱いという性質を持っています。 SCWは損失関数を使っており、SVMのようなマージン最適化も行うような手法になっています。

SCWの損失関数と問題設定

CWの制約は以下のようになっていました。

[latex] P(y_i {\bf w} {\bf x}_i \geq 0) \geq \eta [/latex]

これは以下のように記述することもできます。

[latex] y_i ({\bf \mu} {\bf x}_t) \geq \phi \sqrt{{\bf x}_i^T \Sigma {\bf w}_i} \\ \phi = {\bf \Phi}^{-1}(\eta) [/latex]

これに対する損失関数lを以下のように考えます。

[latex] l^{\phi}(\mathcal{N}({\bf \mu}, \Sigma); ({\bf x}_i, y_i)) = max(0, \phi \sqrt{{\bf x}_i^T \Sigma {\bf x}_i} - y_i {\bf \mu}{\bf x}_i) [/latex]

この式を損失関数を導入すると、CWの問題は、

[latex] ({\bf \mu}_{i+1}, \Sigma_{i+1}) = arg \min_{{\bf \mu}, \Sigma} D_{KL}(\mathcal{N}({\bf \mu}, \Sigma) || \mathcal{N}({\bf \mu}_i, \Sigma_i)) \\ s.t. l^{\phi}(\mathcal{N}({\bf \mu}, \Sigma); ({\bf x}_i, y_i)) = 0, \phi > 0 [/latex]

と書くことができます。

さて、ここで本アドベントカレンダーの記事にはしていなかったのですが、オンライン学習の手法の1つであるPassive Aggressive(PA)と同様の考え方を導入すると、以下のような2通りの条件を緩めた式にすることが可能です。

[latex] ({\bf \mu}_{i+1}, \Sigma_{i+1}) = arg \min_{{\bf \mu}, \Sigma} D_{KL}(\mathcal{N}({\bf \mu}, \Sigma) || \mathcal{N}({\bf \mu}_i, \Sigma_i)) + C l^{\phi} (\mathcal{N}({\bf \mu}, \Sigma);({\bf x}_i, y_i)) \\ ({\bf \mu}_{i+1}, \Sigma_{i+1}) = arg \min_{{\bf \mu}, \Sigma} D_{KL}(\mathcal{N}({\bf \mu}, \Sigma) || \mathcal{N}({\bf \mu}_i, \Sigma_i)) + C l^{\phi} (\mathcal{N}({\bf \mu}, \Sigma);({\bf x}_i, y_i))^2 [/latex]

前者をSCW-I, 後者をSCW-IIと呼びます。

SCWの更新式

導出の過程は省略しますが、SCWの更新式は以下のようになります。

[latex] {\bf \mu}_{i+1} = {\bf \mu}_i + \alpha_i y_i \Sigma_i {\bf x}_i \\ \Sigma_{i+1} = \Sigma_i - \beta_i \Sigma_i {\bf x}_i^T {\bf x}_i \Sigma_i [/latex]

α、βの計算方法がSCW-IかSCW-IIかで異なりますので、それぞれ見ていきましょう。

SCW-I

SCW-Iでのα、βは以下のように計算します。

[latex] \alpha_i = \min \{C, \max \{0, \frac{1}{\upsilon_i \zeta}(-m_i \psi + \sqrt{m_i^2 \frac{\phi^4}{4} + \upsilon_i \phi^2 \zeta)} \}\} \\ \beta_i = \frac{\alpha_i \phi}{sqrt{u_t} + \upsilon_i \alpha_i \phi} [/latex]

ここで、それぞれの変数は以下のようになります。

[latex] u_i = \frac{1}{4}(-\alpha_i \upsilon_i \phi + \sqrt{\alpha_i^2 \upsilon_i^2 \phi^2 + 4 \upsilon_i})^2 \\ \upsilon_i = {\bf x}_i^T \Sigma_i {\bf x}_i \\ m_i = y_i ({\bf \mu}_i {\bf x}_i) \\ \psi = 1 + \frac{\phi^2}{2} \\ \zeta = 1 + \phi^2 [/latex]

SCW-II

SCW-Iでのα、βは以下のように計算します。

[latex] \alpha_i = \max \{0, \frac{-2(m_i n_i + \phi^2 m_i \upsilon_i) + \gamma_i}{2(n_i^2 + n_i \upsilon_i \phi^2)} \} \\ \beta_i = \frac{\alpha_i \phi}{\sqrt{u_i} + \upsilon_i \alpha_i \phi} [/latex]

ここで、それぞれの変数は以下のようになります。

[latex] \gamma_i = \phi \sqrt{\phi^2 m_i^2 \upsilon_i^2 + 4 n_i \upsilon_i (n_i + \upsilon_i \phi^2)} \\ n_i = \upsilon_i + \frac{1}{2C} [/latex]

u, υ, mはSCW-Iと同様になります。

実装

さて、実装してみましょう。今回もおなじみirisの一部を削って二値分類にしたものを利用します。また、φの計算にはscipyを利用します。

処理フローは以下のようになります。

まず必要なものをインポートします。 pandasは最終結果を見るためだけに使っています。

import numpy as np
import pandas as pd

from scipy.stats import norm
from sklearn.datasets import load_iris
from numpy.random import random

次にデータセットをロードします。

iris = load_iris()

# 二値分類をするので1つのラベル分取り除く
iris_data = iris.data[50:]
# ラベルを-1と+1にする
iris_target = iris.target[50:] *2 - 3

# オンライン学習はデータの順番に依存するのでシャッフルする
index = np.arange(len(iris_data))
np.random.shuffle(index)

# 学習データとテストデータに分割
iris_train_data =  iris_data[index[:80]]
iris_train_target = iris_target[index[:80]]

iris_test_data = iris_data[index[80:]]
iris_test_target = iris_target[index[80:]]

では、ここから分岐します。まずは、SCW-Iを実装してみます。

その後ハイパーパラメータのηと、そこから決まる定数を計算しておきます。 μとΣの初期値は、論文中に記載のある

[latex] {\bf \mu}_0 = {\bf 0} \\ \Sigma_0 = I [/latex]

# 初期化
# μ_0 = 0, Σ_0 = Iより
mu = np.zeros(iris_train_data.shape[1])
sigma = np.diag([1]*iris_train_data.shape[1])

さて、ここからはSCW-IとSCW-IIで分岐します。

SCW-I

# ハイパーパラメータ
eta = 0.8
C = 0.1

# 定数
phi = norm.cdf(eta) ** -1
psi = 1 + (phi ** 2 / 2)
zeta = 1 + phi ** 2

続いて、学習を開始します。

# 学習
for x, y in zip(iris_train_data, iris_train_target):
    loss = max(0, phi * np.sqrt(np.dot(x, np.dot(sigma, x))) - y * np.dot(mu, x))
    if loss > 0 :
        upsilon = np.dot(x, np.dot(sigma, x))
        m = y * np.dot(mu, x)
        alpha = 1 / (upsilon * zeta) * (-m * psi + np.sqrt(m**2 * (phi**4 / 4) + upsilon * phi**2 * zeta))
        alpha = min(C, max(0, alpha))

        u = (1 / 4) * (-alpha * upsilon * phi + np.sqrt(alpha**2 * upsilon**2 * phi**2 + 4 * upsilon))**2
        beta = alpha * phi / (np.sqrt(u) + upsilon * alpha * phi)

        mu = mu + alpha * y * np.dot(sigma, x)
        sigma = sigma - beta * np.dot(np.dot(sigma, x), np.dot(mu, sigma))

最後に予測を行ってみましょう。

# 予測値が0以上であれば+1, 未満であれば-1のラベル付けを行う
predict = [(np.dot(x, mu), 1 if np.dot(x, mu) >= 0 else -1, y) for x, y in zip(iris_test_data, iris_test_target)]
pd.DataFrame(predict, columns=['predict_value', 'predict_label', 'target'])

結果は以下のようになりました。

SCW-II

続いて、SCW-IIを見ていきましょう

# ハイパーパラメータ
eta = 0.8
C = 0.1

# 定数
phi = norm.cdf(eta) ** -1

続いて、学習を開始します。

# 学習
for x, y in zip(iris_train_data, iris_train_target):
    loss = max(0, phi * np.sqrt(np.dot(x, np.dot(sigma, x))) - y * np.dot(mu, x))
    if loss > 0 :
        upsilon = np.dot(x, np.dot(sigma, x))
        m = y * np.dot(mu, x)
        n = upsilon + (1 / (2 * C))
        gamma = phi * np.sqrt(phi**2 * m**2 * upsilon**2 + 4 * n * upsilon * (n + upsilon * phi**2))
        alpha = (-(2 * m * n + phi**2 * m * upsilon) + gamma) / (2 * (n**2 + n * upsilon * phi**2))
        alpha = max(0, alpha)

        u = (1 / 4) * (-alpha * upsilon * phi + np.sqrt(alpha**2 * upsilon**2 * phi**2 + 4 * upsilon))**2
        beta = alpha * phi / (np.sqrt(u) + upsilon * alpha * phi)

        mu = mu + alpha * y * np.dot(sigma, x)
        sigma = sigma - beta * np.dot(np.dot(sigma, x), np.dot(mu, sigma))

結果は以下のようになりました。

predict = [(np.dot(x, mu), 1 if np.dot(x, mu) >= 0 else -1, y) for x, y in zip(iris_test_data, iris_test_target)]
pd.DataFrame(predict, columns=['predict_value', 'predict_label', 'target'])