ラプラス正則化 (Laplacian Regularization) を使った半教師付き分類

教師ありデータ\{(x_i,y_i)\}_{i=1}^{n_l}と教師なしデータ\{x_j\}_{j=n_l+1}^{n}を 用いて学習する枠組みを半教師付き学習と呼ぶ. 少量の教師ありデータと大量の教師なしデータを持っているという設定は非常に現実的で, 半教師付き学習は実用的な枠組みだと思う.

ラプラス正則化の基本的なアイデアは,「似ているものは同じラベルを持つ」というもの. 具体的には,類似度行列Wを受け取り, 類似度が高いものは予測値も近くなるような正則化を行う. 今回はラプラス正則化のリッジ回帰への適用例を考えてみる. 目的関数は以下で与えられる.

\min_{\theta} \ \sum_{i=1}^{n_l} (y_i-f_{\theta}(x_i))^2 + \alpha \|\theta\|^2 + \beta \sum_{j=n_l+1}^{n} \sum_{k=n_l+1}^n W_{jk} (f_\theta(x_j)-f_\theta(x_k))^2

最後の項がラプラス正則化項. この項は結局ラプラス行列というもので表されるのでラプラス正則化と呼ばれている.

ここで,非線形な決定境界を表現するために,f_\thetaには以下で定義するRBFカーネルモデルを用いることにする.

f_{\theta}(x) = \sum_{\ell=1}^n \theta_\ell k(x,x_\ell), \ k(x,x_\ell)=\exp\left(-\gamma\|x-x_\ell\|^2\right)

コードは以下のようになった.

実行結果はこんな感じ. 左が訓練データで赤と青がラベル付きデータで白い点がラベルなしデータ. このように,たった2つの教師ありデータから正しく分類ができている.

laplacian_regularization_2moons.png

laplacian_regularization_2circles.png

ラプラス正則化は目的関数に一つ項を加えるだけで, 教師なしデータも活用できるのでお手軽で性能も素晴らしいので是非使ってみてください. 課題としてはパラメータチューニングがある. 教師ありデータが十分にあれば,交差検定ができるが,この例では2つしかないので最適なパラメータを得るのは難しい. それと,RBFカーネルモデルにすべてのデータ点を使っているものポイント.

広告

dragnetでHTMLから本文を抽出

HTMLから本文あるいはコンテンツを抽出したいという需要はかなりあると思う. この問題に対して,機械学習的なアプローチをしているdragnetというものがある(ソースは以下).

dragnetはHTMLをまずblockと呼ばれる単位に分割する. その後,そのブロックが本文であるかないかのラベルをつける. このようなラベル付きデータを用いて,分類器をトレーニングしている. データも以下で公開されていて,自由に追加してコミットすることができる.

分類器にはロジスティック回帰が使われているようだ. ロジスティック回帰は,ブロックが本文かどうかという確率を返すので,この閾値を自分なりにいじることでカスタマイズすることもできる. しかし,オリジナルのソースではこの部分がおかしなことになっている. というのも,dragnet.cotent_extractor.set_thresholdで閾値を設定できるのだが, 閾値で区切るところでdragnet.cotent_extractor._block_model.predictに対して閾値で区切っている. これはすごくおかしなことでpredictは0か1を吐くので閾値で切るというのが実際は機能していない.

というわけでフォークしてそこを書き換えてみた. 以下にそのリポジトリがある(なぜかプルリクが投げれなかった).

オリジナルを使う場合は以下の関数を使用すると良い.

このようなcontent extractor共通の悩みだと思うが, ニュースサイトとかではうまくいくけど,動画サイトや,特殊なサイトでは動かないというケースがある. そのようなケースでも閾値で対応できるかもしれないけど,試していない. とりあえず.dragnetは素晴らしいので是非使ってみてください.

追記(2015/07/30):pull requestを投げました.マージされればきちんとthresholdを設定できます.

BOW+TFIDFでニュース記事分類

前回:

の続き.というかこっちを先にするべきだった. 引き続きlivedoorニュースコーパスを使う. クラス数は9で総文書数は7356件. 今回の対象はタイトルと全文. なので各文書がある程度長いことを想定 (次回はここをタイトルのみにして短い文書に対する分類結果も出してみる).

前回はword2vecを使ったが, 今回は普通にBag-of-WordsモデルとそれにTFIDFで重み付けをしたものを比較してみる. 実験の設定は前回と同じなので,前回の結果とも比較できる. 各文書がある程度長いのでBOWでもいい結果が出るだろうと予測したが,どうなんだろうか.

結果は以下のようになった.

BOW BOW+TFIDF w2v
0.95 (0.004) 0.95 (0.004) 0.85 (0.007)

検定はしていないが,おそらくBOW (+ TFIDF)はword2vecを使ったモデルよりも性能が良いと言っていいだろう. 以下の要因が考えられる.

  1. 十分な数のトレーニングデータが与えられているため
  2. 文書がある程度長く,多くの単語を含むため

次回からは,このあたりを制限していって,結果がどう変わるかを見ていこうと思う. あと,word2vecをこのコーパスでトレーニングしてもいいかも.

word2vecでニュース記事分類

word2vecの応用として文書分類,ここではニュース分類をやってみました. データはlivedoorニュースコーパスを使いました. あと,wikipediaのデータで学習させたモデルを使いました.

bag-of-wordsを用いた場合は以下で議論されています.

さて,今回はword2vecを使って文書分類に挑戦してみます. word2vecにより,単語空間は有限次元ベクトル空間で表現されています. 単語xのベクトル表現をv(x)とし長さ1に正規化されているとします (正規化すると内積がcos類似度になる.特に正規化しなくてもよいと思うが念のため). さらに,文書dのベクトル表現をv(d)とします. ここで,文書dは単語を元に持つ集合(順序は考慮しない)とします.

さて,最もシンプルな文書ベクトルは以下のようになるだろう.

v(d) = \frac{1}{|d|} \sum_{x \in d} v(x)

これをモデル1とする.

次に,以下のような重み付きバージョンを考える.

v(d) = \frac{1}{|d|} \sum_{x \in d} \ w(x) \ v(x) \\ \\ \sum_{w \in d} \ w(x)=1

この重みw(x)には,例えばTFIDFやPMIなんかが使えると思う. ちなみに重みは足して1になるようにしておく.これをモデル2とする. 今回は,モデル1とモデル2を比較してみる.

モデル1はすぐに構築できるが,モデル2の重みを何にしようか迷う. 今回のタスクは文書分類なのだから,クラス分類において重要な単語には大きな重みをつけるべきだろう. そう考えると,以下の重み関数はどうだろうか.

w(x,d) = \frac{c(x,d)}{\sum_{x' \in d} c(x',d)}\log\frac{\#\mathcal{Y}}{\#\{y| x \in y\}}

ここでc(x,d)は,単語xの文書dにおける出現回数, \mathcal{Y}=\{1,\ldots,c\}はクラスで,\#は集合の要素数をさす. logの項はidfのクラス版で,その単語がいろんなクラスに出現するなら分母が大きくなり全体が小さくなる. 逆に,その単語があるクラスにしか出てこないならその単語の重みは大きくなる. これはあまりにもハードな重みな気がするが,とりあえずこれ(以下tficfと呼ぶ)を使ってみる.

さて,まずは文書を形態素解析するのだが(形態素解析を使わないバージョンは次に書こうと思う), 辞書には最近流行りのneologdを使う.

ライブドアニュースコーパスのディレクトリ構成は以下のようになっていることを想定.

livedoor_corpus/
  dokujo-tsushin/
  it-life-hack/
  kaden-channel/
  livedoor-homme/
  movie-enter/
  peachy/
  smax/
  sports-watch/
  topic-news/

なお,カテゴリ数は9で総文書数は7376であった. 分類器にはロジスティック回帰を用いた.

以下に実験結果を示す.

uniform tficf
0.85 (0.01) 0.52 (0.03)

tficfが重み付けを行った結果だ.ものすごく悪い. 一方重み付けを行わないモデル (uniform) はかなりいい性能を発揮している. 重み付けによりここまで性能が落ちるとは思わなかった. 何かバグがないか追求してみるが,今のところword2vecで学習した単語空間をそのまま使っても特に問題はなさそうだ. それにしても上のqiitaの記事ではBOW+kNNというシンプルな組み合わせながら精度が89%と報告されている. これはおそらく文書分類というタスクでは,文書が多数の単語を含むのでBOWでも十分にそれを表現できているため,と解釈できる. 逆に,一つの文書が短かったり,単語そのものを分類しなければならないようなタスクでは,word2vecの真価が発揮されるのではないかと思う.

単語分類については以下に簡単な例がある.

実は,短い文書においては,TFICFの有効性を確認した.よって長い文書でも動くはずなのだが,今回は動かなかった. というわけでバグを探すのと,word2vecの他の応用も考えてみる.

実験に使ったコードはGistに置いておくので,気が向いたら試してみてください:

Pythonでscikit-multilearnを使ったマルチラベル分類 (multi-label classification)

通常の分類問題は,各点がたった1つのクラスにしか属さないという仮定のもとで解かれる. しかし,現実には各点が複数のクラスに属するという場合がある. このような問題はマルチラベル分類問題 (multi-label classification) と呼ばれ,盛んに研究されている. マルチラベル分類問題を解くためのモジュールはいくつか存在するが,Pythonにはscikit-multilearnというモジュールがある.

今回はこれを使ってマルチラベル分類問題を解いてみる. データには公式と同じくsceneを使う.

まずはscikit-multilearnをダウンロードして移動する.

git clone https://github.com/scikit-multilearn/scikit-multilearn
cd scikit-multilearn

今回はここに以下のコードを置いて使ってみる.

実行結果:

0.113573021182

やっていることはとてもシンプル. まだソースを見ていないのでなんとも言えないが, 基本的な分類器を用意してそれをskmultilearn.meta_br.BinaryRelevanceがmulti-label用にラップしてくれると解釈している. 今回はlinear SVMを使ってみた. multi-label classificationの評価指標にはhamming lossが使われるようだ. これは[0-1]で,低ければ低いほど良い. 今回は0.11だったのでまぁまぁなのではないか.

以上scikit-multilearnの簡単な使い方を紹介してみた. 「multi-label classificationしないといけないけど詳しくない」 という方はとりあえずこれを使ってみるというのはどうでしょうか.

局所性保存射影 (Locality Preserving Projection, LPP)とラプラス固有写像 (Laplacian Eigenmap)

次元削減手法の局所性保存射影とラプラス固有写像について.これらは局所性を保存する,という特性がある.局所性とはデータの局所的な構造のことで,例えばクラスタ構造なんかがそれに当たる.PCAも含めて,これらは全て固有値問題を解くことで解を求める.この二つの手法は密接に関係している.整理のためのポスト.

局所性保存射影V \in \mathbb{R}^{d \times k}は,データ\{x_i\}_{i=1}^n, \ x_i \in \mathcal{X} \subseteq \mathbb{R}^d, \ \forall i=1,\ldots,nとその類似度行列Wを入力とし,以下の一般化固有値問題の解である.

XLX^Tv=\lambda XDX^Tv

ここで,X=[x_1|\cdots|x_n], \ D=diag(\sum_{j=1}^n W_{1j}, \ldots, \sum_{j=1}^n W_{nj}), \ L=D-Wである.これをカーネル化することを考える.X\Phi=[\phi(x_1)|\cdots|\phi(x_n)]で置き換えて,

\Phi L \Phi^Tv=\lambda \Phi D \Phi^Tv

を得る.例のごとく,v=\Phi \alphaと置くと,

KLK\alpha=\lambda KDK\alpha

を得て,これがカーネルLPP.さらに,\beta=K\alphaとおくと,

L\beta=\lambda D\beta

となり,これがラプラス固有写像.

カーネルLPPで得られた射影行列V=[v_1 | \cdots | v_k]=\Phi [\alpha_1|\cdots|\alpha_k]=\Phi Aを用いて,データXは,V^T \Phi = A^TKと埋め込まれる.ちなみに,ラプラス固有写像の解はB=[\beta_1 | \cdots | \beta_k]=KAであり,B^TはカーネルLPPでサンプルを射影した結果に一致する!つまり,データにカーネルLPPを施したもの=ラプラス固有写像の解,である.

カーネルLPPによって,元のデータはある特徴空間へ射影される.ラプラス固有写像はその結果をダイレクトに求める.ラプラス固有写像は局所性,例えばクラスタ構造を保存するので,クラスタリングの前処理に適しているとされている.ラプラス固有写像を施した後にK-Meansなどのクラスタリングをする手法はスペクトラルクラスタリングと呼ばれ,ものすごく研究されている.

以上自分用メモ.

グラム行列の固有値分解で特徴ベクトルを得るのはkernel PCAをするのと同じこと

前回:

– グラム(カーネル)行列の固有値分解で対応する特徴ベクトルを得る

の続き.前回はグラム行列Kの固有値分解を用いてK=\Phi\Phi^Tを満たす特徴ベクトル(を縦に並べた行列)\Phiを求めてみました.いわゆるlow-rank近似というやつなんですかね.そして,新しい入力に対してその特徴ベクトルが計算できない,という問題がありました.

実はこれ,Kernel PCAと同じことをしているということに気づきました.似ているなぁ,とは思っていたのですが.まず問題を整理しよう.

Kernel PCAは,

\Phi\Phi^Tv_i=\lambda_i v_i, \ \Phi=[\phi(x_1)|\cdots|\phi(x_n)], \ \langle v_i, v_j \rangle=\delta_{ij}

という問題を解く(\Phiの定義が前回と変わっているのでご注意を).

ここでv_i=\Phi \alpha_iと置くと,

K\alpha_i=\lambda_i \alpha_i, \ \langle \alpha_i, \alpha_j \rangle=\delta_{ij}

となり,A=[\alpha_1|\cdots|\alpha_k], \ \lambda_1 \geq \ldots \geq \lambda_kを得る.

ここで,\langle v_i,v_j \rangle=\delta_{ij}であるためには,v_i=\frac{v_i}{\|v_i\|}=\frac{v_i}{\sqrt{\lambda_i}}としてやる必要がある.最終的に,V=[v_1|\cdots|v_k]=\Phi A \Lambda^{-\frac{1}{2}}を得る.

さて,元の空間の元x \in \mathcal{X}z=V^T \phi(x)と変換される.これを現在持っているデータ\Phiに適用すると,V^T \Phi = \Lambda^{-\frac{1}{2}} A^T \Phi^T \Phi = \Lambda^{-\frac{1}{2}} A^T K = \Lambda^{-\frac{1}{2}} \Lambda A^T = \Lambda^{\frac{1}{2}} A^Tとなる.

これは,前回と全く同じ結果である!驚きだ!

ここで,新しい入力x \in \mathcal{X}を考えると,これに対応する特徴ベクトルはz = V^T \phi(x) = \Lambda^{-\frac{1}{2}} A^T \Phi^T \phi(x) = \Lambda^{-\frac{1}{2}} A^T k(x), \ k(x)=[k(x,x_1) \cdots k(x,x_n)]^Tと表される.

これで,out-of-sample問題も解決だ.素晴らしいじゃないか.次はLPPとかについて書きたい.