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

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

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しないといけないけど詳しくない」 という方はとりあえずこれを使ってみるというのはどうでしょうか.