Soft Confidence Weightedを実装してみる
こんにちは、小澤です。
当エントリは「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'])
おわりに
今回は、オンライン学習の手法であるSCWを実装しました。
数式が多く出てきて怖い思いをした方もいるかもしれませんが、基本的な形はCWとそれほど大きく違いません。 本来であればPassive Aggressiveの解説もあった方がわかりやすかったかと思いますので、いずれそちらも実装したいと思います。
明日は、いよいよ最終日です。 ここまでDeep Learningに触れていませんでしたのでそっちの話題にいきたいと思ったのですが、いきなりの話だと難しいのでDeep Learningの前提となる3層ニューラルネットワークの話をしたいと思います。 お楽しみに！
