Github Pagesに移行します

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

nktmemo_ja

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

 

 

正例とラベル無しデータからの学習 (PU classification)

追記(2016/07/22)
sample weightingによるPUClassificationも実装しました

– https://gist.github.com/nkt1546789/d4ffebb452fe738b8aaa8005fc08a068

任意の分類器を使えるのでこちらの方が良い気がします.


通常の2値分類問題では,正例と負例が与えられています. しかし扱う問題によっては,このようなデータを用意するのが困難な時があります. 例えば,抽出型のタスクです. 抽出型のタスクでは,抽出したい対象を正例と考えます. この場合の負例は「正例以外のデータ」と定義するほかありません. しかし,集めた正例に対し,それ以外のデータを負例と定義してしまうと, それ以外のデータに含まれる正例も負例として扱ってしまいます.

このように負例を定義するのが難しい場合には,正例とラベルなしデータから学習する枠組み,PU classificationが有用です. PU classificationについては,Elkan and Noto 2008を参照していただければと思うのですが,少しだけ解説しておきます. 3つの確率変数x,y,sを考えます.ここで,x \in \mathbb{R}, y \in \{-1,1\}, s \in \{0,1\}だとします. xは入力,yはクラスラベル,そしてsはデータがラベリングされるかどうかを表しています. 我々が欲しいのは,p(y|x)ですが,PU classificationではyは観測することができません. 我々のゴールは,\{(x_i,s_i)\}_{i=1}^nからp(y|x)を学習することです. 結果からいうと,2つの仮定をおくことで,

p(y=1|x) = \frac{p(s=1|x)}{p(s=1|y=1)}

と表せます.p(s=1|x)は与えられたデータから推定できます. そして,p(s=1|y=1)は開発データから推定できます. 詳しくはElkan and Noto 2008の2章にまとめられています. 今回はElkan and Noto 2008の手法を用いてPU classificationを行っていきます.

では,以下のような正解データを考えましょう. true_labeled.png

このデータに対して,実際に与えられるのは以下のようなデータです. pu_data.png

このデータに対して,まずは通常のロジスティック回帰を適用してみます. なお,今回は負例が多いので,交差確認法には正例側のF値を用います. 結果は以下のようになりました. result_of_tradclf.png

ご覧のように,全て負例だと予測してしまいました. 次に,PU classificationを適用してみます. result_of_puclassification.png

正例とラベルなしデータから,うまく分類境界を学習できていることがわかります.

デモ用のコードは以下に載せておきますのでぜひ試してみてください. ちなみに,非線形な分類境界を表現するためのrbfmodel_wrapper.py と PU Classificationのためのpuwrapper.py も合わせてDLしてください.

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

Word2Vecを使った単語間関係分類

単語間には様々な関係があります. 今回は,単語間の関係をWord2Vecで学習させようと思います. Word2Vecにはアナロジーを捉えられるという話があります. あの有名な,king – man + woman = queen というやつですね. これは,king – man = queen – womanとも書けます. つまり,2語間の差が関係を表しており, この例だと,kingとmanの関係とqueenとwomanの関係が同じであると捉えることができます.

さて,Word2Vecで学習したベクトル表現を使うと,差ベクトルがうまいこと関係を表すと書きましたが, 必ずしもそうなっているとは限りません. 加えて,ユーザが扱いたい関係とWord2Vecで学習した関係が一致しているとも限りません. そこで,今回も例のごとく教師あり学習を使います. ユーザは教師データを通して,扱いたい関係をアルゴリズムに伝えることができます.

最初からあまり多くの関係を対象にするのはしんどいので,今回はis-a, has-a関係のみに着目します. これは,僕の理解では,柔道 is-a スポーツ,スポーツ has-a 柔道みたいなものだと思っています. まずはtraining dataを用意します. is-aとhas-aは反対の関係になっていると思うので,has-aのデータだけ用意します. この中には (スポーツ,野球)というhas-a関係を表す順序対がリストで格納されています. リスト内の順序対に対して差ベクトルを計算し,一つのデータとして扱います.

コードは以下のようになりました.

import training
from gensim.models import Word2Vec
import numpy as np
from sklearn.linear_model import LogisticRegressionCV
np.random.seed(1)

model=Word2Vec.load("/path/to/your/w2v_model")

data=[]
X=[]
y=[]
for w1,w2 in training.data:
    if w1 in model and w2 in model:
	data.append([w1,w2])
	data.append([w2,w1])
	X.append(model[w1]-model[w2])
	X.append(model[w2]-model[w1])
	y.append(1)
	y.append(-1)

X=np.array(X)
y=np.array(y)

idx=np.random.permutation(len(y))
ntr=int(len(y)*0.7)
itr=idx[:ntr]
ite=idx[ntr:]

Xtr=X[itr]
ytr=y[itr]
Xte=X[ite]
yte=y[ite]

clf=LogisticRegressionCV().fit(Xtr,ytr)

ypred=clf.predict(Xte)

from sklearn import metrics
print metrics.accuracy_score(yte,ypred) # >>> 0.99502487562189057

今回は厳密な実験はせずに,簡単に性能を見てみました. テストデータに対して,99%の精度を出すことができました. 以下簡単なテストデータへの予測例です.

for j,i in enumerate(ite):
    w1,w2=data[i]
    if ypred[j]==1:
	print w1,"has-a",w2
    else:
	print w1,"is-a",w2

# results:
ブルーベリー is-a 果物
動物 has-a モルモット
動物 has-a ワタボウシタマリン
スポーツ is-a スポーツ
登山 is-a スポーツ
ロデオ is-a スポーツ
動物 has-a ユーラシアカワウソ
スポーツ has-a フリーダイビング
競馬 is-a スポーツ
スポーツ has-a ゴルフ
...

いかがでしょうか?うまく狙った関係が分類できていると思います. とりあえずはうまくいきました!これで成功です! これがどこまで実用に耐えられるかはやってみないとわかりませんが…

Word2Vec+教師あり次元削減で文書分類+単語分類

前回:

の続きです.

まずは,前回のおさらい. 前回は,文書に対してはラベル付きデータが与えられており,単語についてはラベルなしデータが与えられているという設定を考えました. そして,文書と単語が同じ空間に存在すれば,半教師付き学習に帰着することを示しました. 詳しくは前回の記事を見ていただくとして,これからは半教師付き学習の設定で話を進めます.

今回は,前回の記事でいう単語ベクトル集合\{x_i\}_{i=n_d}^{n}をWord2Vecで学習させます. 食わせるコーパスは分類対象の文書集合です.

その後,教師あり次元削減手法であるFisher Discriminant Analysis (FDA)を使ってB:\mathbb{R}^d\rightarrow\mathbb{R}^mを学習させます. これによって,Word2Vecで学習した単語ベクトルたちは,より低次元の空間に落とし込まれます. つまり,z=Bxとして,\{(z_i,y_i)\}_{i=1}^{n_d}\{z_i\}_{i=n_d}^{n}を得ます. 今回は,m=c-1としました,ただし,cはクラス数です.

なぜこのような処理をするかというと,Word2Vecのような教師なし学習では,必ずしも「望ましい結果」が得られるとは限りません. なぜなら,「望ましい結果」についての情報を一切与えていないからです. 今回の目的は文書分類+単語分類です. この目的に対して,Word2Vecが必ずしも望ましい結果を返すとは限らないのです.

そこで,教師あり次元削減を使います. FDAは,簡単にいうと,同じクラスに属するサンプルは近く,異なるクラスに属するサンプルは遠くなるよう,射影行列を学習します. ここでは,「望ましい結果」教師データとして与えるので,学習後の空間は分類という目的に対して望ましい空間になっていると期待できます.

さて,あとは対して面白いことはしていません. \{(z_i,y_i)\}_{i=1}^{n_d}で確率的分類器を学習させ,\{z_i\}_{i=n_d}^{n}に対して予測をします.

前回と同じデータを使って実験をしました. 結果の出力には同様にwordcloudを使わせてもらいました.

ガールズ: girls.png

ニュース・ゴシップ: news.png

エンタメ・カルチャー: entertainment.png

おでかけ・グルメ: spot.png

暮らし・アイデア: life.png

レシピ: recipe.png

カラダ: wellness.png

ビジネススキル: business.png

IT・ガジェット: tech.png

デザイン・アート: design.png

雑学: trivia.png

おもしろ: humor.png

定番: popular.png

評価データがなくて定性的に評価するしかないのですが,前回と比べて,かなり改善されている気がします. 雑学とかおもしろ,定番なんかは定義がよくわからなくて判断しにくいですが,それ以外はうまく単語分類ができていると思います.

今回は,Word2Vec+教師あり次元削減 (FDA) を使って文書分類器を作成し,それを使って単語分類をしてみました. 結果として,このアプローチはなかなか良いと感じました. 文書分類,単語分類については,これでひと段落した感じがします. 本当は単語分類なんかはマルチラベル分類問題として解くべくなのかもしれませんが,あまりこの問題に執着してもあれなので. 次は要約や,トレンド抽出なんかをやっていきたいなあなんて思っています.

前回と今回はコードを載せていません. これはコードがなかなか複雑なためです. もし,見てみたいという方がいたら,コメントからでも,Twitterからでもなんでも良いので言ってください! 読んでいただき,ありがとうございました.

文書分類器で単語分類をしてみる

keywords: 文書分類 (document classification), 単語分類(word classification), Pointwise mutual information

はじめに

文書へのラベリングと単語へのラベリングはどちらが簡単だろう? 例えば多くのニュースサイトではすでに文書は分類されている. しかし,単語が分類されているのは見たことがない. というより,そんなものを表に出してもあまり意味がないので表に出ていないのだろう. この状況を踏まえると,データをクロールする側からすると,ラベル付き文書データを入手するのは容易で, ラベル付き単語データを入手するのは困難だと言える.

いま,文書データをクロールして,検索エンジンを作ることを考えよう. 各文書にはラベルが付いている. このラベル情報を活かせないか? 例えばクエリにラベルが付いていれば,クエリと文書のラベルを見て,一致するものを出せばよい,あるいはそういう場合にスコアが高くなるように,検索エンジンのスコアを設計すれば良い. このように,単語へのラベリングはある程度需要があると推測される.

定式化

さて,今回やるのは,ラベル付き文書データを使って,単語分類をしようというもの. つまり,持っているものは,\{(d_i,y_i)\}_{i=1}^{n_d}\{w_i\}_{i=1}^{n_w}, ただし,d_i \in \mathcal{D}は文書,y_i \in \mathcal{Y}は文書に対するラベル, w_i \in \mathcal{W}は単語を意味する.

ここで,もし単語と文書が同じ空間に存在すれば,文書分類器を使って単語分類ができると思われる. つまり,\mathcal{S}=\mathcal{D}=\mathcal{W}とし,なんらかの変換\phi:\mathcal{S} \rightarrow \mathcal{X}を定義すればよい. ここまで来れば,x_i=\phi(d_i) \ \forall i=1,\ldots,n_d, \ x_{n_w+j}=\phi(w_j) \ \forall j=1,\ldots,n_wとし, \{(x_i,y_i)\}_{i=1}^{n_d}\{x_i\}_{i=n_d}^{n}を得る.ただしn=n_d+n_w. こうして見てみると,単語と文書を同じ空間に写像すれば,これは半教師付き分類問題に帰着することがわかる.

簡単のために,\mathcal{X}=\mathbb{R}^d, \ \mathcal{Y}=\{1,\ldots,c\}とする. 今回は,「文書は単語の線形結合で表される」という仮定を置いてみる.つまり,

d=\sum_{i=1}^{n_w} \alpha^{(d)}_i w_i, \ \alpha^{(d)}_i \in \mathbb{R} \ \forall_i=1,\ldots,n_w

となる.さらに,「\phiは線形写像である」という仮定を置くと,

\phi(d)=\sum_{i=1}^{n_w} \alpha^{(d)}_i \phi(w_i)

となる.というわけで,\phiではなくて,コーパスから\{\phi(w_i)\}_{i=1}^{n_w}を学習することにする.

さて,やらなければならないのは,

  1. コーパスから\{\phi(w_i)\}_{i=1}^{n_w}を学習する
  2. \alphaの決定

である.だいぶシンプルになったな.1に関しては死ぬほど研究されているので,その中から適用な手法を使うことにする. ここでは,PPMIを使って単語ベクトルを決定してみる.この辺は特に珍しくもないので,例えば以下を参照してください.

残る問題は2だ.とりあえずシンプルさを追求して,単語の出現回数を使うことにする.つまり,\alpha^{(d)}_i=c(w_i,d)とする. ただし,c(w_i,d)は,文書dにおける単語w_iの出現回数である. これで全ての問題が一応解決した.さあ,あとは実装するだけ.

実装

コードは後日載せます. やっていることは,PPMIを要素とした単語-文脈行列を作り,その各行を単語ベクトルとします. あとは↑の定式化通りに文書ベクトルを生成し,文書分類器を作ります. その後,単語ベクトルたちを分類器にかけます. 文書分類器には,ロジスティック回帰(sklearn.linear_model.LogisticRegressionCV)を用います. デフォルト設定です(アプローチの可能性を見たいだけなので).

実験

データはnaverまとめからクロールしたものを使う. カテゴリとそれに対応するクロールした文書数を以下の表に示す. これが今回の訓練データ.

カテゴリ 文書数
ガールズ 600
ニュース・ゴシップ 976
エンタメ・カルチャー 480
おでかけ・グルメ 867
暮らし・アイデア 737
レシピ 702
カラダ 708
ビジネススキル 558
IT・ガジェット 231
デザイン・アート 479
雑学 667
おもしろ 584
定番 257

総異なり語数は14767件で,これが今回の分類対象となる. さて,結果はただ単語を羅列してもおもしろくないので,wordcloudを使おうと思う. これについては以下を参考にしました,ありがとうございます.

ガールズ

girls.png

ニュース・ゴシップ

news.png

エンタメ・カルチャー

entertainment.png

おでかけ・グルメ

spot.png

暮らし・アイデア

life.png

レシピ

recipe.png

カラダ

wellness.png

ビジネススキル

business.png

IT・ガジェット

tech.png

デザイン・アート

design.png

雑学

trivia.png

おもしろ

humor.png

定番

該当単語なし

おわりに

今回はラベル付き文書データから文書分類器を学習し,それを単語分類に使用してみた. 結果は定性的に測るしかないが,うまくいっているところはあるのでアプローチは悪くないのかなと思う. 定番に該当がないのは定番だからなのだろうか?笑 ただ,もっと分類器をチューニングしたほうが良い気がする. いまはただロジスティック回帰にぶん投げているだけなので.

次回は,教師あり次元削減,具体的にはFisher Discriminant Analysis (FDA)をかけてみます. いまは生の単語-文脈行列を使っているので,情報をもっと圧縮させて次元を削減しようと思います. さらに,教師ありデータを使うことで,同じラベルを持つものは近くなり,異なるラベルを持つものは遠くなるよう次元削減後の空間を学習します(正確には射影行列). まぁとりあえずいいんではなかろうか.

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])

ラプラス正則化 (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カーネルモデルにすべてのデータ点を使っているものポイント.