Github Pagesに移行します

読んでいただきありがとうございます.
WordPressでの数式の表現力に限界を感じたため,
このブログをGithub Pagesに移行しようと思います.
移行先は,

nktmemo_ja

になります.徐々に最新の記事から移行しているのでしばらくかかります.
引き続きよろしくお願いします!

 

 

RBF (Gaussian) Kernel Modelを使うためのWrapper Classを作りました

分類問題において,非線形な決定境界を表現するための一つの方法に,RBF Kernel Modelがあります. これは,入力xを以下で定義される\phi(x)に変換するものです.

\phi_i(x)=\exp\left(-\gamma\|x-x_i\|\right), \ \forall i=1,\ldots,n.

コードはGistに載せてあります:

https://gist.github.com/nkt1546789/e41199340f7a42c515be

使い方は,例えばsklearnのLogisticRegressionに適用したい場合は,

clf=RbfModelWrapper(LogisticRegression()).fit(X,y)

同様にRidgeに適用したい場合は,

clf=RbfModelWrapper(Ridge()).fit(X,y)

ちなみにGridSearchもできるようになっています:

gs=GridSearchCV(RbfModelWrapper(Ridge()),param_grid={"gamma":np.logspace(-2,0,9),"alpha":[1,10,100]}).fit(X[itr],y[itr])

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をこのコーパスでトレーニングしてもいいかも.

局所性保存射影 (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とかについて書きたい.

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

類似度を設計するのと,特徴ベクトルを設計するのはどちらが難しいだろうか?とりあえず今は類似度を設計する方が簡単だとしよう.そしてその類似度が正定値カーネルになるように設計し,kとしよう:

– http://ibisforest.org/index.php?正定値カーネル

n個のデータ\{x_i\}_{i=1}^nを持っているとしよう.大事なのはxはなんでもいいってこと.文字列でも,木でも画像でも動画でも.ただ,類似度を設計すれば良い(この類似度を学ぶ枠組みもある).データとカーネルから,グラム行列(カーネル行列とも言われる)K, \ K_{ij}=k(x_i,x_j)を構成しよう.この段階で使える機械学習アルゴリズムは多々ある.例えばSVM,ロジスティック回帰,その他諸々.しかし,K \in \mathbb{R}^{n \times n}であり,nが大きくなると,すなわちデータが膨大な量だとこのまま使うのは計算量的にもメモリ的にも厳しい.

そこで,Kの固有値分解K=USU^Tを考えよう.なお,これらは固有値の大きい順にソートされているとする.そして,\Phi=US^{\frac{1}{2}}としよう.そうすると,K=\Phi\Phi^Tとなり,なんとこれが最初に設計した類似度に対応する特徴ベクトル(を縦並べたもの)になっている.さらに,Kはしばしばlow-rankであり,Sの対角成分の多くは0である.そこで,Sの固有値が0でないm個の成分だけ使おう.そうすると\Phi \in \mathbb{R}^{n \times m}となり低次元表現を得る.依然としてK=\Phi\Phi^Tである.

ここでmをコントロールすることで,Kの近似表現を得ることができると気づく.これである程度の近似性能を保ちながら,次元を削減することができる.ゲットした特徴ベクトルは,クラスタリングに投げたりできる.

しかしながら,大きな大きな問題がある.それはサンプルに入ってない新しい点が来たときにどうするか?ということ.そう,このままでは分類や回帰に使えない.これを今後調べていく.何かやり方をご存知だったら教えてください.