Sideswipe

情報工学、計算論的神経科学など、真面目なこと書くブログ。お仕事の話は Twitter: @kazoo04 にお願いします。

Deep Learning の概要

はじめに

去年の 機械学習×プログラミング勉強会 vol.2 で、Deep Learning の概要について発表させていただきました。誘っていただいた @07c00 さん、ありがとうございました。

詳しくは上記のスライドを御覧ください（注：Auto Encoder と DBM をごっちゃに説明しているので正しくありません、そのうち直します）。

Deep Learning とは

Deep Learning は、ニューラルネットワーク*1のひとつで、5層とか10層とか、従来の手法ではうまく学習できなかった深い層の学習をうまくできるようにしたアルゴリズムです。

Deep Learning が目指したところ

入力に近い層では、単純な特徴抽出しかできませんが、それらの重み付け和をとると表現能力が上がります。それをさらに上位の層に入力していけば、どんどんモデルの表現能力が上がると考えられます。これが基本的なアイディアです。

人間の大脳新皮質も同じように情報を処理していると考えられており、たとえば視覚野ではV1と呼ばれる領域では、特定の角度の線*2 にだけ対応する部分が集まっています。
V2は、V1の入力を受け取っており、つまり複数の線の組み合わせを表現していると考えられています。ひとつひとつは単純な刺激でも、階層的に特徴を抽出・組み合わせていくことにより、高度な表現ができるわけです。

従来手法の問題点

ところが、これは考え方は合っているのですがなかなかうまくいきません。たとえば、Backpropagation は発火するノードがスパースになるようには設計されていませんし、多層になると誤差信号はうまく伝わらなくなる問題 ( Vanishing Gradient Problem )があります。

Deep Learningでは、 Restricted Boltzmann Machine (RBM) を 学習させ、1層ずつ増やしていく方法でこれらの問題を解決しています。

Deep Learningの欠点

Deep Learningが画像認識において衝撃を与えたことは間違いありませんが、学習が遅い、パラメータ調整が面倒くさいなどの問題もあります。
また、大脳新皮質に似ていると思われる処理から、ハードAIへの応用を期待する記事も見られますが、このブログでは

To paraphrase an old parable, Hinton has built a better ladder; but a better ladder doesn’t necessarily get you to the moon.

と述べられているのが印象的ですね。

さいごに

Deep Learning は従来職人技だった特徴量抽出を教師なし学習でやってしまうという点で画期的です。これにより、特徴量の設計が難しいがゆえに機械学習でうまく扱えなかった問題を改善できるかもしれません。

RBMの詳細な部分までは時間の都合上調べきれなかったので資料も概要的なものにとどまっていますが、このスライドに目を通せば他のWebページや論文の内容が理解しやすくなるのではないかな、と思います。

*1:あまりこの言葉は好きではないのですが

*2:正確には線ではなく、縞模様

オンライン線形分類器とSCW

はじめに

こんにちは。Machine Learning Advent Calendar 2012 、 12/20 を担当させていただく @kazoo04 です。
普段は（株）ウサギィでエンジニアをやっています。

今日の話

今日は Exact Soft Confidence-Weight Learning (Wang et al, ICML2012) (以下SCW)のご紹介を致します。
SCWは線形オンライン形分類器のひとつで、

  • 学習が高速
  • オンライン学習
  • ノイズに強い
  • 精度が良い

という素晴らしいアルゴリズムです。 SCWはCWを改良したアルゴリズムですが、本記事ではPerceptronから始まり、PA、CWなどを経てSCWに至るまでの過程とSCWのアルゴリズムについてまとめたいと思います。

数式の表記

すみません、はてなブログを始めたばかりで、ベクトルを太字の立体にする方法がイマイチわかりませんでした。すこし表記が揺れているところがありますがご了承いただければと思います。

線形分類器

線形分類器は、 x \in \mathbb{R}^m から出力 y={-1, +1}を推定する関数 f(\mathbf{x}; \mathbf{w}) を学習するというものです。また、各訓練事例が1つ与えられるたびにパラメータを更新する方法をオンライン学習と呼びます。

Perceptron

もっとも単純なオンライン線形分類器としては、 Rosenblatt の Perceptron が挙げられます。訓練事例 (\mathbf{x}, y) が与えられた時、現在の分類器で正しく分類できるかどうかを調べ、間違っている場合は \mathbf{w}_{i+1} = \mathbf{w}_i + y\mathbf{x} に従って更新します。単純ではありますが、線形分離可能な問題であれば有限回の更新ですべての訓練事例を正しく分類できることが保証されており(Perceptronの収束定理)、またそうでない場合でもまあまあな結果が得られます（問題にもよるが）。

Passive Aggressive

CrammerのPAは、Gmailの優先トレイにも使われているアルゴリズムです。
PAでも、訓練事例が正しく分類できたら重みは変更しません(Passive)。うまく動いてるものには手を触れないという方針なのです。
逆に、正しく分類ができなかったら、その訓練事例が正しく分類できる最小限だけ分離面を動かします(Aggressive)。
下の図を見てください。左の例では、提示されたデータが正しく分類できているので、分離面は動かしません（なにもしません）。
右の例では、提示されたデータがうまく分類できなかったので、分類ができる最小限だけ分離面を動かしています（わかりやすさのため、最小限よりはちょっと多めに動かしていますが）。

f:id:kazoo04:20121219213823p:plain

ただ、この方法はアグレッシブすぎて、ノイズがあったときに分離面が振り回されてしまうというデメリットがあります。
そこで、 PA-I, PA-IIでは誤識別をある程度許容することでノイズに対してロバスト性を確保しています。

Confidence-Weighted Algorithm *1

CWは、今までの線形分類器とは異なる考え方を導入し、収束を早めると同時に精度も高くしたという夢の様なアルゴリズムです。
機械学習に食わせる訓練事例は、ふつう各特徴の頻度に大きなばらつきがあります。また、低頻度の特徴が大きな影響を持っていることも多々あります。
先に挙げた手法では、各訓練事例の出現頻度は考慮されていないため、高頻度の特徴は比較的信頼できる一方で、低頻度の特徴は重みがあまり更新されていないので、あまり信頼できないと言えます。

そこで、CWでは「過去にどれくらい現れたか」を考慮した上で学習を行います。
CWでは、重みベクトル w にガウス分布 N(\mu, \Sigma) を導入し、平均と共分散を同時に更新していきます。
\mu は、その時点で一番もっともらしい重みベクトルで、 \Sigma はその重みにどれくらい自信があるのかを表す共分散行列になります。
分散の大きいパラメータは、まだあまり自信がないので、思い切って大きめに更新します。逆に分散が小さいパラメータはある程度正確に学習できていると考え、小さめに更新します。

例として、既存のアルゴリズムで、文を肯定か否定かに分類する場合の更新を考えてみましょう(参考: Confidence Weighted Linear Classificationを読んだ - 射撃しつつ前転)。 "I liked this author." という肯定的な文があったとして、この事例の分類に失敗した場合（つまり否定的な文だと分類された場合）は、 I, liked, this, author それぞれについて重みが加算されます。 また、 "I liked this author, but found the book is dull." という否定的な文の分類に失敗した場合は、 I, liked, this, author, but, found, the, book, is, dull それぞれについて重みが減算されます。このとき、それぞれの重みは同じだけ加減算されます。
たくさん出現する単語であれば、少しくらいノイズがあっても頑健なパラメータ推定が可能であると考えられます。たとえば、否定的な文に liked という単語が入っていても、肯定的な文により多くの liked という単語が入っていれば、うまく学習できます。

この方法だと、よく出現する単語については正確なパラメータの推定が可能になると考えられますが、めったに出現したい単語(dullなど)はうまくパラメータを推定できない（推定出来るだけの事例がない）ので、思い切って大きく重みを更新します。

既存のアルゴリズムでは、重みはたとえば 0.8→0.6 に更新する、といった単純な加減算からなりますが(図の上側)、CWの場合は \mu を0.8→ 0.6 にすると共に、 \Sigma は少し減らす（すこし自信がでてきた）ようにします（図の下側）。

f:id:kazoo04:20121220140516p:plain

このように、低頻度の特徴を活用することで、収束が非常に早くなったのがCWの大きなメリットです。通常のオンライン学習では全学習データを何度か学習させますが、CWは最初に1回でほぼ収束する（それ以上学習させても精度に大きな違いがない）ことがわかります。

具体的にはPassive Aggressiveの場合と似ていて、

  • 現在の訓練例を正しく分類できる
  • 今までの分布になるべく近くする

の2つを満たす分布 (\mu, \Sigma) を探すことになります。

{{\rm arg~min}\limits}_{\mathbf{\mu}, \Sigma} D_{KL} (\rm N(\mathbf{\mu}, \Sigma) || \rm N(\mathbf{\mu}, \Sigma)) s.t. Pr_{\mathbf{w} \sim \rm N(\mathbf{\mu}, \Sigma)} [y \mathbf{w}_i^T \mathbf{x} \ge 0] \ge \eta

この最適化問題は嬉しいことに閉じた解を持っており、簡単に計算できます。すばらしいですね！

Adaptive Regularization of Weight Vectors (AROW) *2

ところが、CWには弱点があり、訓練事例にノイズがあると急激に性能が劣化します。Passive Aggressiveと同様、与えられた訓練事例を確実に分類できるように更新してしまうためです。 Crammer によって考案されたAROWは、次の3つの条件を同時に考慮して最適化します。

  1. 各特徴の分散は少しずつ小さくしていく(自信を上げる)
  2. 現在の訓練例を正しく分類する(PA, CW と同じ)
  3. 今までの分布に近い

{{\rm arg~min}\limits}_{\mathbf{\mu}, \Sigma} D_{KL} (\rm N(\mathbf{\mu}, \Sigma) || \rm N(\mathbf{\mu}, \Sigma)) + \lambda_1 L(\mathbf{x}, y, \mu) + \lambda_2 L(\mathbf{x}^T \Sigma \mathbf{x})

\lambda_1は条件1, \lambda_2は条件2をどれくらい重視するかのパラメータです。「そのパラメータの設定が大変なんでしょう？」と思うかもしれませんが、これは結構適当でも大丈夫で、問題によって調整する必要はありません(たとえば0.1とか)。

ごちゃごちゃと書きましたが、実装は難しくありません。論文中の擬似コードはこんな感じです。

f:id:kazoo04:20121220000918p:plain

昔書いたD言語のコードだとこんなかんじです。

    int Update(feature[] fv, int label) 
      in
      {
        assert(label == -1 || label == +1);
        assert(fv != null);
      }
      out (result)
      {
        assert(result == 0 || result == 1);
      }
      body
      {
        double m = GetMargin(fv);

        if(m * label >= 1) return 0;

        double confidence = GetConfidence(fv);
        double beta = 1.0 / (confidence + hyperparameter);
        double alpha = (1.0 - label * m) * beta;

        //Update mean(μ)
        //平均の更新
        foreach (v; fv) {
          mean[v.index] += alpha * cov[v.index] * label * v.weight;
        }

        //Update covariance(∑)
        //分散の更新
        foreach (v; fv) {
          cov[v.index] = 1.0
            / ((1.0 / cov[v.index]) + v.weight * v.weight / hyperparameter);
        }

        //損失の計算 (Squared Hinge-loss)
        int loss = m * label < 0 ? 1 : 0;

        return loss;
      }

Exact Soft Confidence-Weight Learning (SCW) *3

さて、ようやく本題のSCWです。
SCWも、CWの「ノイズに弱い」という部分を改良したアルゴリズムであるという点では、AROW（やその他のアルゴリズム― NHERDやNAROWなど）と同じですが、ソフトマージンSVMのように、マージン最適化も行うという点で画期的です。また、マージンを考慮するためAROWなどのアルゴリズムよりさらに高速に収束するという特徴もあります。

SCWの考え方は、ある程度( 1 - \eta )の誤分類を許容して、パラメータの急激な変化を防ぐことです。
何度か述べているように、訓練事例に現れた頻度によって、自信のあるパラメータとそうでないパラメータが存在します。そこで、現在の識別超平面から信頼度による重み付けマージンを計算して、それを損失関数 l に組み込みます( \phi はちょっとわかりにくいのですが、 ガウス分布の累積密度関数の逆関数を、さらに \eta で評価したものです)。

l(\rm N(\mu_t, \Sigma_t);(\mathbf{x}_t, y_t)) = {\rm max} (0, \phi \sqrt{\mathbf{x}_t^T \Sigma x_t} - y_t(\mu_t \cdot \mathbf{x})_t)

そして、次の2つの条件を同時に考慮して最適化します。

  1. ガウス分布間の重み付けマージンを最適化する
  2. 今までの分布に近い

{{\rm arg~min}\limits}_{\mathbf{\mu}, \Sigma} D_{KL} (\rm N(\mathbf{\mu}, \Sigma) || \rm N(\mathbf{\mu}, \Sigma)) +C (l(N(\mu_t, \Sigma_t);(x_t, y_t)))

Cは、どれくらい条件1を考慮するかというパラメータです。上に挙げたのは SCW-I というバージョンで、

{{\rm arg~min}\limits}_{\mathbf{\mu}, \Sigma} D_{KL} (\rm N(\mathbf{\mu}, \Sigma) || \rm N(\mathbf{\mu}, \Sigma)) +C (l(N(\mu_t, \Sigma_t);(x_t, y_t))^2)

というものもあり、こちらは SCW-II と著者は呼んでいます。まあ実験結果を見る限り、そこまで大きな差はないのでSCW-Iでいいんじゃないかな？と思います。
論文から擬似コードを抜粋するとこんな感じで、非常に簡単です。AROWやCWとあまり変わりません。

f:id:kazoo04:20121219215301p:plain

パラメータが2つ出てきてしまいましたが、 AROWと同じく、 \eta も C もかなり適当でいいです。

まとめ

オンライン線形分類器は、高速に処理ができる上に、追加学習や実装も容易です。一時はCWの登場で大幅な精度向上を達成しましたが、ノイズに弱いという点を克服するためにAROWやSCWなどのアルゴリズムが考案されました。

Algorithm Large Margin Confidence Non-Separable Adaptive Margin
PA ○ ○
CW ○ ○ ○
AROW ○ ○ ○
SCW ○ ○ ○ ○

特にSCWはノイズに対してロバストなことはもちろん、信頼度による重み付けマージンを導入し、ソフトマージンの最適化をしている点や、損失上限の証明がなされているなどのメリットがあります。
元の論文の実験でもSCWは他の手法より優れた成績を残しており、非常に実用的なものになっています。

実装上の注意点ついては、CW, AROW, SCWともに、共分散行列をまともに扱うとメモリを食いますし実装も面倒なので、対角項だけ計算すればOKです（非対角項は0にする）。こうしても精度はほとんどかわりません。

論文を見てわかるとおり、AROWやSCWにいたってはSVMよりよい成績を叩きだしており、線形識別器が欲しいのであればSCWを使えばいいんじゃないかなとおもいます。

NHERDもたまに見ますが、AROWと比べるとAROWのほうがいいことが多いです。それにSCWのほうが基本的に精度が良いので、迷ったらとりあえずSCWを使えばいいんじゃないかなとおもいます。

SCWについては、kisaさんの記事が非常に参考になるので、ご興味がありましたらぜひこちらもご覧ください。

それでは。

追記

その後 SCW と AROW を使う機会（画像の分類）があり、実践してみたので所感を。

  • SCW-II はぜんぜんダメ SCW-I を使おう
  • SCW はパラメータが2個あるので調整が面倒
  • AROW はパラメータが1個しかないので楽（気持ちAROWのほうがパラメータに敏感でないのでそれもまた使いやすい）
  • パラメータを調整した AROW とパラメータを調整した SCW-I はほぼ同じ性能（まあ平均すると SCW−I のほうがすこし良いが）

というわけでデータセットにもよりますが個人的には AROW のほうがいいなあという感じです。

  • すこしでも精度を上げたくて、そのために良いパラメータの探索を行うのが苦でないのなら SCW
  • そうでないなら AROW

が良いと思います。

*1:Dredze, Mark, Crammer, Koby, and Pereira, Fernando. Confidence-weighted linear classification. In ICML, pp. 264–271, 2008.

*2:Crammer, Koby, Kulesza, Alex, and Dredze, Mark. Adaptive regularization of weight vectors. In NIPS, pp. 345–352, 2009b.

*3:Peilin Zhao, Jialei Wang, Steven C.H. Hoi. Exact Soft Confidence-Weighted Learning. ICML 2012.

選択ソートと挿入ソートの違い

両者を同一視している方が多い上に、ぱっと見アルゴリズムが似ているこの2つ。
実は結構差があるので詳しく見てみましょう。

アルゴリズム

ふたつのアルゴリズムの詳細については wikipedia がそこそこ詳しいのでそちらを参照してください。

挿入ソート

挿入ソートは「既にソート済みのデータ列に対して、新しい要素を正しい位置に挿入する」ことを繰り返していくアルゴリズムです（ wikipedia:挿入ソート ）。

選択ソート

対して、選択ソートは「整列されていない最小（最大）の要素を1つ取り出し、整列済みデータの末尾に加える」操作を繰り返していくアルゴリズムです（wikipedia:選択ソート）。

計算量

平均計算量、最悪計算量はどちらも O(n^2) です。
ところが、最良計算量は挿入ソートが O(n)に対して、選択ソートはO(n^2)になります。ここについて詳しく見てみましょう*1。
以下では昇順にソートすることを前提としています。

n個の要素があり、既にソート済みの要素がm個あるとします(もちろん n \geq m)。つまり、ある時点でソートされていないデータは n-m個です。

挿入ソート

1番目のデータは、比較するまでもなく挿入位置が決定できます。2番目以降のデータは、ソート済みの各要素と比較して挿入する場所を決める必要があります。
最短の場合だと、1回の比較で挿入位置が決定できますが、最悪m回の比較が必要です。要素がランダムであると仮定すれば、平均 \frac{m}{2} 回の比較が必要です*2。

平均計算量

さて、ある時点でソートされていないデータはm個あり、mは1から(n-1)まで増加していくので、比較回数は次のようになります。

\frac{1}{2} + \frac{2}{2} + \frac{3}{2} + ... + \frac{n-1}{2} = \displaystyle \sum_{i=1}^{n-1} \frac{i}{2} = \frac{1}{2} \displaystyle \sum_{i=1}^{n-1}{i}

これは次のように書けます。

\frac{1}{2} \displaystyle \sum_{i=1}^{n-1}{i} = \frac{1}{2} \cdot \frac{n(n-1)}{2} = \frac{1}{2} \cdot \frac{n^2-n}{2} = \frac{n^2-n}{4}

ということで、平均計算量は O(n^2) です。

最悪計算量

最悪の場合は常にm回の比較が必要なので、

1 + 2+ 3 + ... + (n-1) = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \frac{n^2-n}{2}

となります。よって、最悪計算時間も O(n^2)です(分母が変わっていますけどね)。

最良計算時間

最良の場合は、常に1回の比較のみで挿入位置が決まる、つまりソート済みのデータをソートする場合です。1回の比較をn-1回繰り返すのですから

\displaystyle \sum_{i=1}^{n-1} 1 = n - 1

となり、 最良計算時間は O(n) です。

選択ソート

次に、選択ソートを見てみましょう。選択ソートでは、まず1つのデータの位置を確定するために (n-1) 回の比較が必要です。
次は比較対象のデータが1つ減っているので、 (n-2) 回の比較が必要です。これを繰り返していくので、

(n-1)+(n-2)+...+(n-(n-2))+(n-(n-1)) = (n-1) + (n-2) + ... + 2 + 1

となりますが、これは要するに1からn-1までの総和を求めているだけなので、

\displaystyle \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \frac{n^2-n}{2}

と表せます。比較回数は最良の場合も最悪の場合も常に同じなので、入力によらず計算量は O(n^2) です。

まとめ

オーダを見ると、挿入ソートは最良の場合 O(n) でソートできるというメリットがあります。最悪の場合でも選択ソートと同じですし、基本的には挿入ソートを選ぶべき*3です。

「整列済みのデータに新しい要素を加える」といった場面では、挿入ソートは非常に高速に動作するので非常に便利です。また、ほとんど整列済みのデータに対しても早いので、他のソートアルゴリズム(例えばクイックソート)でおおまかにソートしたあと、最後に挿入ソートを使うといった手法もあります。データの種類にもよりますが、クイックソートの場合は要素数が7〜30くらいになったら挿入ソートに切り替えたほうが早くなります。クイックソートは確かに高速なアルゴリズムですが、オーバーヘッドが大きいので小さいデータに対しては O(n^2) なアルゴリズムが早いことがあるのです。

また、リストは挿入が O(1) でできるので、特に挿入ソートが効果的になります。

どちらも安定なソートで内部ソートという点では同じですし、先程も触れた通り選択ソートよりは挿入ソートのほうが優れていると言えます。

*1:厳密な意味での計算量を計算しているわけではないので注意、雰囲気だけです

*2:交換回数は常に比較回数より少ないので、以下では比較回数についてのみ考えている

*3:選択ソートのほうが優れている点をご存じの方がいたら教えてください

Quicksort の攻撃方法

以前 Quicksort の計算量について話したので、ブログにも書いておきます。

 

参考にしたのは、 M. D. MCILROY の A Killer Adversary for Quicksort です。

 

Quicksort は、 pivot の選択方法がまずいとオーダが O(n^2) になってしまうという弱点があります。

 

まずい選択というのは、分割対象の数列の最小（最大）の要素をpivotにしてしまうときで、そのような場合は、最小（最大）の値を含むものと、それ以外の集合に分割されてしまい、結局選択ソートと似たような挙動になってしまいます。

そこで、通常は各区間の「左端」・「中央」・「右端」の3つの値をとってきて*1、その中央値をpivotとするといった実装がよく見られます。

 

ところが、この手法にも問題があり、工夫されたデータ列に対してはやはり O(n^2)になってしまいます。詳細についてはスライドを参照していただきたいのですが、一部の実装ではまさにこの方法でpivotの選択が行われており、攻撃データを入力すると処理が終わらなくなってしまいます（PHPの場合はタイムアウトする）。

 

これらを完全に避けるためには、 Introsort のようなクイックソートを改良したものを使ったり、 Timsort のようなクイックソート以外のアルゴリズムをベースにしたものを使う必要があります。

また、 Quicksort でもpivotの選択方法を乱択にすることでこれらの問題を回避することができます。単純な実装としては、ランダムな位置から3つの要素を取ってきて、その中央値をとるなどの方法が考えられます。

 

*1:メモリ上のデータに右や左はありませんが…