jubatusの分類器：前編(分類の基本・線形分類器のアルゴリズム)

この記事は[Jubatus Advent Calendar](http://qiita.com/advent-calendar/2016/jubatus) 19日目の記事です．

こんにちは、@imaimai1125です

普段良く使う、Jubatusの分類器の中身のアルゴリズム、あまり中身が分からずに使っている方も多いのではないのでしょうか。
一応[Jubatus HP](http://jubat.us/ja/method.html)にもアルゴリズム解説はあるのですが、上級者向けになっているので、少し噛み砕きながら説明します。


# 分類とは？

イメージとしては、ハリーポッターに出てくる**組み分け帽子**のようなものを想像してください。

帽子を被ると、グリフィンドール・スリザリン・ハッフルパフ・レイブンクローに分けてくれます。

機械学習的な言葉で言えば、帽子が分類器、帽子を被った人が入力、被った人の性格、才能、身長や体重といったものが特徴量になります。(実際何を基準に組み分けされているかは知りませんが。)
何らかの特徴量から判断をして、あの組み分け帽はハリーたちをクラスに分けていくのです。

どういう感じで分類がなされているか、図にしてみました。

![分類.png](https://qiita-image-store.s3.amazonaws.com/0/151502/1f6d8487-0f66-ca90-c49e-289bf0fc18cf.png)

この図では、図示の都合上特徴量が２つですが、この特徴量は状況によって増やすことができます。
また、クラスの数も増やすことが可能です。

黒の太線が、分離平面です。先ほどの例で言えば、どのクラスになるかというギリギリの線ということになります。
この**分離平面を決定する**のが分類器の役割です。

青と赤の丸は、予め用意されたラベルつき**教師データ**です。「この特徴量ならクラス1だ」というようなデータを**予め用意**しておいて、
それを使って**分離面を作っていきます。**

図のように、分離平面の作り方によって、**線形分類器・非線形分類器**と、大きく2種類に分かれます。

- **線形分類器**では、まっすぐな線を引くため、分類の仕方に限界があります。なので、図のように、クラス1側が全部クラス1のデータ！というわけにはいかないこともあります。
- **非線形分類器**では、ぐにゃぐにゃと線を引けるため、教師データの分類に関してはほぼ100%分類ができます。しかし、あまりにも**教師データ**にあわせすぎると、ほかの新しいデータに対してうまく分けれなくなるかもしれないというような問題があります。

図では、(a)と(b)で分類結果が違うという例を挙げました。どちらを信じればいいかは機械学習の本質的に難しい問題ともいえます。興味のある人は**モデル選択**とか、**バイアス・バリアンス**という言葉で調べてみてください。

この分離平面を決めるアルゴリズムを`jubaclassifier`では数種類用意しています。

# jubaclassifierで使える分類アルゴリズム

jubaclassifierでは、分類アルゴリズムとして、下記を用意しています

![jubaclassifier.png](https://qiita-image-store.s3.amazonaws.com/0/151502/7d7552cd-2138-3cb0-8176-4befc89ef47b.png)

前編では、**線形分類器**について、説明します！ 

# オンライン線形分類器

## 核となるアルゴリズム
Jubatusの線形分類器は様々な種類が用意されています。しかし、核となるアルゴリズムはどれも一緒です。

事前準備として、先ほどの図(a)について、もう少し数式を使ってみてみましょう。

![omomi.png](https://qiita-image-store.s3.amazonaws.com/0/151502/641dc52a-eb00-6d28-9ede-0885eeba544f.png)


この図からわかるように、**$w$**をうまく決めることが、分類器の肝となるのが、わかると思います。これを踏まえて、線形分類の核となるアルゴリズムをみていきましょう。

↓図が、核となるアルゴリズムになります。

![algorithm.png](https://qiita-image-store.s3.amazonaws.com/0/151502/e682dff5-d0d2-7461-d8c6-18b66a2a8d6e.png)

$E$, $\alpha$と, $A$について、先ほどのアルゴリズムを見ていくと、

![al.png](https://qiita-image-store.s3.amazonaws.com/0/151502/5317e18c-a7e5-2a55-1e69-5d686fd98815.png)


となります。これがjubatus線形分類器の中身です。

とはいっても、設計思想がわからないので、少し詳しく見ていきましょう

## Perceptron
- 更新式 : $\mathbf{w^{(t+1)}}=w^{(t)}+y\mathbf{x}$

最も単純なアルゴリズムで、間違っていたらそのときの特徴量分、重みとして正解に近づくように足し合わせるようになっています

## Passive Agressive
### PA

![PA.png](https://qiita-image-store.s3.amazonaws.com/0/151502/7ee3c40a-496e-6646-85f1-83a74366f76f.png)


サポートベクターマシン(SVM)のオンラインバージョンになっていて、

- 必ず正しく分類する**(Agressive)**
- あまり重みを更新しすぎず、なるべく最小限に更新する**(Passive)**

という2つを考慮して重みを更新していく(更新の仕方は、ラグランジュの未定乗数法を使う)

### PA-I, PA-II
ただし、この**絶対分類しろ**というのが厳しく、ひとつのミスも許されないという厳しいものになっているので、
もうちょっとマイルドにしてやろうと考えたのが、PA-IやPA-IIです。

変わったところは、ミスを許すようにした代わりに、罰則項として更新時にミスを考慮させるようにしたというところです。

![PAI-II.png](https://qiita-image-store.s3.amazonaws.com/0/151502/0723101c-68e3-4b28-8a60-1df555bf4b43.png)

このCの値は、こちら側で調節できるようになっていて、jubaclassifierでも`regularization_weight`をいじることで、調整ができます

```json
{
  "method" : "PA2",
  "parameter" : {
    "regularization_weight" : 1.0
  },
  "converter" : {
    "string_filter_types" : {},
    "string_filter_rules" : [],
    "num_filter_types" : {},
    "num_filter_rules" : [],
    "string_types" : {},
    "string_rules" : [
      { "key" : "*", "type" : "str", "sample_weight" : "bin", "global_weight" : "bin" }
    ],
    "num_types" : {},
    "num_rules" : [
      { "key" : "*", "type" : "num" }
    ]
  }
```

## Confidential Weight

![CW.png](https://qiita-image-store.s3.amazonaws.com/0/151502/25efcb4d-433d-f2c2-226e-575733641a68.png)


思想としてはPAとほとんど同じで、「$w$を前とあまり変えすぎずに上手に分類してほしい」のですが、
CWでは、**重みがガウス分布に従う**という仮定が入ります。$\mathbf{w}\sim N(\mathbf{\mu},\Sigma)$、ガウス分布のパラメータである平均と分散を更新することで、重みを更新します。

$\mu$の更新式は

```math
\begin{eqnarray}
\mu^{(t+1)}=\mu{(t)}+\alpha^{(t)}y^{(t)}\Sigma^{(t)}\mathbf{x}^{(t)}
\end{eqnarray}
```

となります。ここでの$\Sigma$はガウス分布の分散項で、その重みを決めたときのいわゆる**自信**みたいなもので、自信があれば(分散が小さければ)もうあまり$\mu$を更新しないし、自信が無ければ思い切って更新をするといったものになっています。

$\Sigma$自体、更新を繰り返すごとに0に近づいていき、そのスピードは分離できるものであればとても早いです。
弱点としては、PAと同じように**分離できないものに対して弱く**、データにノイズが載ったりすると著しく精度が落ちることが知られています。

jubaclassifierで設定できるパラメータとして、`regularization_weight`を用意しています。
厳密には$\eta$ではないのですが、上の数式の$\eta$に密接に関係する量を調節しています。

- `regularization_weight` 大 ⇔ $\eta$ 大 : ミスは許さない.代わりに学習は早い
- `regularization_weight` 小 ⇔ $\eta$ 小 : 多少のミスは許すが、学習は遅くなる

という特徴があります。

## Adaptive Regularization of Weight Vectors

CWの弱点である**ノイズに対して弱い**を、正規化項を加えることで克服しようとしているものです。更新式はこちら

![AROW.png](https://qiita-image-store.s3.amazonaws.com/0/151502/fccba411-ade3-019d-0fd4-732feec47bda.png)

(細かい内容は論文を参照してください。)

CWが、何が何でも正解率$\eta$を見つけてくるような条件式になっていたのに対し、AROWはもうちょっと穏やかです. 

更新式からもわかるように、3つの条件を**バランスよく**保ちながら、$w$を決める平均と分散を更新していきます。

jubaclassifierで設定できるパラメータとして、`reguralization_weight`を用意しています。
上式において`reguralization_weight`$=1/r$となっているため

- `regularization_weight` 大 ⇔ 何が何でも正しく分類しようとする。CWっぽい挙動
- `regularization_weight` 小 ⇔ 分布の更新幅重視になる。学習は遅い

という特徴があります。

## NHERD

こちらも、CWの弱点を解消しようとしたものです。

更新式としてはAROWに似たものになっているのですが、論文での導出過程をみると、更新式の裏のココロはかなり異なっているようです。
CWやAROWが、重みベクトルの分布をなるべく変えないような更新をするために、KL divergence($D_{KL}$)を最小化しようとしていたのに対して、
NHERDは重みベクトルの分布を**速度**だとみなして、その速度にしたがって重みベクトルを更新する。という見方をしています。

![NHERD.png](https://qiita-image-store.s3.amazonaws.com/0/151502/aee8122d-3632-379e-b568-a0ba1cee31a3.png)

重みベクトルの更新としては

```math
\begin{eqnarray}
w_{i+1} = Aw_i+b\end{eqnarray}
```

のように従って行います。このときに、wの分布の計算を、KL divergenceではなく、**マハラノビス距離**で計算しているところも、AROWやCWと違うところです。
ただ、更新式に($A$)は明には出てこず、結果としては下図のような更新式となります。
(細かい内容は論文のAlgorithmの章を参考にしてください)

![nherd_update.png](https://qiita-image-store.s3.amazonaws.com/0/151502/05f98df7-80c4-3eb4-ef2c-06a013f65598.png)

jubaclassifierで設定できるパラメータとして、`reguralization_weight`を用意しています。
上式において`reguralization_weight`$C$となっているため

- `regularization_weight` 大 ⇔ 学習が早くなるが、ノイズに弱くなる
- `regularization_weight` 小 ⇔ ノイズ耐性が増す代わりに、学習が遅くなる

という特徴があります。


ところで、先日の@shiodatさんが書いてくれた可視化の記事([link](http://qiita.com/shiodat/items/590243d49b24edf5695e))を見ると、AROWよりNHERDのほうがばたつきが少ないことがわかります。

これは、NHERDのdiscussionに書かれていて、**NHERDのほうが始め積極的に更新するが、その分分散の収束が早い**のです。具体的に$\Sigma$の更新式を見ると、NHERDのほうがAROWより常に収束が早いことがわかります。

![nherd_sigma.png](https://qiita-image-store.s3.amazonaws.com/0/151502/0a1fdb86-e04f-4b14-9941-8f77e28ff1d9.png)

この影響を受けている分。AROWよりもNHERDのほうが早くばたつきが少なくなるのでは？と考えられます。


# 長くなったので
続きは明日にします！

明日の内容は

- 非線形分類器(k近傍法)
- jubaclassifierで設定できるパラメータ毎の挙動の違いを可視化

あたりを書きたいと思います。


# 参考文献
## 論文
- PA [Online Passive-Aggressive Algorithms, NIPS2003](https://papers.nips.cc/paper/2360-online-passive-aggressive-algorithms.pdf), 
- CW [Confidence-Weighted Linear Classification, ICML2008](https://www.cs.jhu.edu/~mdredze/publications/icml_variance.pdf)
- AROW [Adaptive Regularization Of Weight Vectors, NIPS2009](https://papers.nips.cc/paper/3848-adaptive-regularization-of-weight-vectors.pdf)
- NHERD [Learning via Gaussian Herding, NIPS2010](https://papers.nips.cc/paper/3893-learning-via-gaussian-herding.pdf)

## 参考書
[オンライン機械学習](https://www.amazon.co.jp/%E3%82%AA%E3%83%B3%E3%83%A9%E3%82%A4%E3%83%B3%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92-%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%83%97%E3%83%AD%E3%83%95%E3%82%A7%E3%83%83%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E6%B5%B7%E9%87%8E-%E8%A3%95%E4%B9%9F/dp/406152903X)