a lonely miner

距離計量学習とカーネル学習について

こんにちは．英語が書けなくて悩んでいる今日このごろです．

先月に引き続き，仲間内で行っている小さな勉強会にて論文紹介をしてまいりました．

ちょっと古めの論文ですが，あまり踏み込んだことのない分野なので，名著っぽいものから確実におさえていくスタンスで．

発表スライドは以下においておきます．最後のスライドにいろいろ文献リンクしておいたので，ご興味をもって頂けましたら是非そちらも当たってみてください．

距離計量学習(以下単に距離学習)とは何ぞや，というのは小町さんの日記をご参照いただけると良いと思うのですが， ざっくり言うと，「分類しやすいように前処理として空間を歪めてしまおう」という技法です．ケーキで表す（！）と以下のような感じ．マシンラーニングケーキかっこいい！

Large Margin Nearest Neighbors

要するに，同じクラスの事例同士は近く，異なるクラスの事例同士は遠くなるように，元の空間を歪めてしまうのです．

この論文では，距離学習を多変量正規分布間の KL Divergence (の特別な場合である LogDet Divergence )の最適化問題として定式化するとともに，カーネル学習との等価性について述べています．実際のアルゴリズムは，Bregman Projectionとか名前はごっついけど実際はそんなに難しくない．

確かに，カーネル行列というのは，バラすと特徴量空間での距離を畳み込んだものと言えますし，関連はありそうだと思ったものがきれいに証明されていてけっこう感動しました．

さらには，(正直あまり理解できませんでしたが)元の距離学習のカーネル化やオンライン化（Regret Boundまで！）などなど，8ページギッシリ詰められています．

ただ，学習されるのは単なるマハラノビス距離行列という単なる線形変換なので，どれほどのタスクで効くのかどうかは疑問が残ります．

たとえば，元の空間で線形分離不可能な問題というのは，どんな線形変換を施したとしても，きれいに線形分離できるようにはならないでしょうし，特徴空間での回転（マハラノビス距離行列の非対角要素）は何を表しているのか正直よくわかりません．

もっとも，このアルゴリズムはカーネル化ができることが示されているので，分離しやすい空間へ飛ばしてから距離学習を行えば別なのかもしれませんけど・・・けど・・・けど・・・．

こういう点では，多様体学習（詳しくないのですが，たとえばLaplacian Eigenmapsとか）のような非線形のアプローチのほうが，もともとの目的（分類しやすいように前処理する）に合っているように感じます．

計算量的な問題でいろいろ難しいのかもしれませんが，こういうSupervisedな距離学習あるいは次元削減で，オススメの文献がありましたら是非教えてください．

は〜英語書きに戻ろう．実際に書いている時間なんてほんの僅かで，書けないよーってうんうん呻ってる時間がほとんどなのだけれど．

そういえば，そういえば，一昨日第一回コンペが終わったCrowdSolvingについてはどれくらい書いていいのかな？いずれにしても，また次回．

  • 4/22 14:00 論文等へのリンクが間違っていたので修正しました．

グラフ結合度に基づく教師なし語義曖昧性解消について

完全に春ですね．そろそろ新入生が来る時期．

書類を整理していたら，むかし読んだ Roberto Navigli (knowledge based WSDの大家) によるgraph based unsupervised WSDに関する論文の感想が出てきたのでちょっと再編集して公開してみます．あくまでメモなので，非常に読みづらいかも．もしご興味をもって頂けましたら，元論文をあたってみてください．

グラフの G = (V, E) をコンテキストおよび、ワードネットのネットワークから作成し，その上で 各語義 (vertexに対応)の重要度をはかるという方法に基づいたWSDに関するお話．

具体的には、まずコンテキスト（本論文では文）内の単語の各語義をグラフのノードとして初期化し、それぞれの語義からグラフ内のほかの語義へのリンクをDFSで探し，みつかればそのルート中の語義をグラフに追加していき，その間にエッジを張る．ということを行っている．

この操作で出来たグラフの「あるノード」の重要度が高いようであれば，その語義はコンテキスト内での重要度が高く，語義候補である可能性が高い，という直感に基づいている．

グラフは以下の図のような感じ．これは，{動詞drink, 名詞milk}の例．それぞれ5つ，4つの語義が定義されていて，それらが 名詞boozing_1, 名詞beverage_1 ような語義を通して間接的に連結されていることがわかる．

肝心の重要度尺度であるが，彼らは local な尺度と globalな尺度という，大きく分けて二種類の尺度について実験を行っている．

localな尺度を用いた手法では、グラフ内のノードをPagerankや度数といった指標に基づいてランキングし、もっともSenses(wi)に対応するノードの中で最も高いランクを得た語義を出力．こっちは簡単．

globalな尺度はグラフ全体に対してスカラーの値を与えるものなので，語義選択においてはそのままでは用いることができない．そこで， G の部分集合となるような G’(コンテキスト内の単語それぞれについて語義ひとつだけを考えたもの) を考え，そのサブグラフのglobal measureの値が高いものを語義の組み合わせとして導きだす． たとえば，文が 2単語から成っており、それぞれが， 3つ，4つの語義を持っている場合は、3 *4 で12個のサブグラフを作り，それぞれに対して global measureを計算する。もっとも高いglobal measueを得たサブグラフを語義の組み合わせとして出力する．（計算量が爆発するという意味でオリジナルのLeskアルゴリズムと類似している）

過去の研究として，

  • R. Barzilay and M. Elhadad, “Using Lexical Chains for Text Summarization,” Proc. ACL Workshop Intelligent Scalable Text Summarization, pp. 10-17, 1997.
  • R. Mihalcea, “Unsupervised Large-Vocabulary Word Sense Disambiguation with Graph-Based Algorithms for Sequence Data Labeling,” Proc. Human Language Technology and Empirical Methods in Natural Language Processing, pp. 411-418, 2005
  • M. Galley and K. McKeown, “Improving Word Sense Disambiguation in Lexical Chaining,” Proc. 18th Int’l Joint Conf. Artificial Intelligence, pp. 1486-1488, 2003.

が比較に挙げられているが，本論文の手法は one sense per one discourse を強く仮定しない(同じドキュメント内で同じ対象語に対してもコンテキストが異なれば違う語義が出力されうる)．また、グラフをunlabeled & unweightedに構築している点が異なる．これには以下の二つの理由があるらしい．

  • 広く合意を得たweightingの方法が確立されていない
  • 研究の焦点を絞りたい(まぁweightingは今のところ特に興味ない)

また、WordNet にくっついている MFS(というより，語義頻度) は本論文ではつかっていない．なんでかというと，それはhand-labeledなSemcorコーパスから得られたものであり，他の言語とかドメインに対しても有効な指標とは言えないから（この点は激しく同意）．

以下，それぞれの尺度についてまとめる．

local measure

local measureは特定のグラフのノードの重要度を表すもの．あるノードのグラフ全体に対する影響度，とみなすこともできる 値域は [0,1] で、1に近ければ重要、0に近ければ重要ではない．

  • Degree これは単なる次数。deg(v) = vの次数とすると， C_degree(v) = deg(v) / (|V| - 1)というように正規化しておく

  • Eigenvector ようは PagerankとHITS．特筆すべきことはなし．

  • KPP（あとで読む)

  • Betweeness shortest pathの数を用いる． σst = s->tへのshortest pathの数，　σst(v) そのうち、vを通るもの．σst(v) / σst をすべてのノードペアに対して和をとって，betweeness(v)とする．そして(|V| - 1)(|V| - 2)で割って正規化．

global measure

さきほどのlocal measureがグラフのノードに対して重要度を与えるものだったのに対して，こちらは特定の語義の組み合わせからなるグラフに対して[0,1]のスカラー値を与えるもの．

  • Compactness, Graph entropy, Edge density いわゆるグラフのコンパクト性などの一般的な尺度

global measureは計算量的に無理がある（文内のすべての単語に対する語義の組み合わせを列挙してそれぞれに対して求めなければならない)ので工夫をしている．

global measure計算における工夫

  • Simulated Annealing まずランダムに語義選択を初期化，ひとつ取りかえて上記 global measure の差分(ΔE)をみる．もしよくなっていれば採択、悪くなっている場合でも exp(ΔE/T)の確率で採択．Tは何らかの定数，これを u 回繰り返した結果を採用．書いてて思いましたが，Simulated Annealingというよりは，Metropolis Hastingsですねこれ．

  • Genetic Algorithms なんか面倒そうなので略．結局パラメータ調整は面倒だしあんまりいいこと無い，みたいな結論に至っており，若干残念な感じ．

Experiment

データはSemCor, Senseval-3, Semeval-2007．Sensemapつかって全部WordNet2.0にマップしてある．

Sense-inventoryにはWordNet2.0 と EnWordNetというものを使っている．EnWordNetはcollocational relationをもちいてedgeを6万本くらい増やしたWordNetらしい．具体的な構築方法はよく分からないが． WN++みたいなものか．

ふつうのWordNetから構築したグラフと，EnWordNetから構築したグラフの性質の比較も行っている．

  • small world effect : l = グラフのスモールワールド性（任意の頂点ペアの間の最短距離の平均)

  • clustering rate(or transitivity) : C = probability that two neighbors of a vertex are connected 詳しくは式参照 ネットワーク内の三角形の数で計算するらしい。

  • cumulative degree distribution : P_k = Σ p_k’ (<- k次のノードの割合)

結果として，EnWordNetから構築したグラフのほうがdenseでござるという当たり前の議論が．(そりゃあエッジ足してるだけなのだから当然)

グラフ生成におけるDFSの深さは6にしている（SemCor上で実験して決めたらしい)

その他、GA, SAのパラメータについてうんたらかんたら．

Result

Degree（もっとも単純なlocal measure,ノードの次数そのもの) がもっともよく，いろいろ工夫した他のlocal measureやglobal measureは振るわなかった．残念．．．

WordNet vs EnWordNetの比較では，EnWordNetの方が若干ながら良い結果．

しかしながら，unsupervised WSDの常として，MFS(First Sense Baseline)は非常に強く，F1 measureで20ポイント以上の差をつけられてしまっている．

感想

グラフとしては最も基本的な， unlabeled, undirected, unweightedなものの上で何ができるか，を追求した研究といえる．

単純な指標がうまくいってしまい，いろいろ工夫しても無駄っぽいのは残念だが，unsupervised WSDの難しさは語義粒度とknowledge baseの質如何でいくらでも変動しうるので，言語資源の整備が進めば，また違った結果が得られるかもしれない．

WSDにおいて宿命になっている，”MFSに勝てない問題”については，近年は

のように，知識ベース(WordNet)側をガンガン強化することで，ほぼ遜色ない性能を出すことができる手法も出てきている．しかし，こちらも，もっとも性能の良い尺度はDegreeなので，なんだかなぁという気はする．

結局知識ベースの品質に強く依存するknowledge based WSDではあるが，まだ何かできることは無いかと考えると，うまくいくかはともかくとして，いろいろ面白そうだ．（ニッチなためか，機械学習屋さんがまだあまり進出してこない分野でもあるので）

Posterior Regularization と Unified Expectation Maximizationについて

桜がとってもきれいですね．すずかけ台は8分咲きといったところです．ところで，仲間で行っている小規模な勉強会で

を紹介してきたので，資料をslideshareにあげておきました．

Unified EMというと，じゃっかん大風呂敷な感じのタイトルですが，キーとなるアイデアはとても単純で，EMアルゴリズムのE-Stepで最小化するKLダイバージェンスにちょっと細工を入れることで，Hard-EMとふつうのEMの中間くらいの性質を持ったアルゴリズムになりますよ．というお話です．Deterministic Annealing EMの逆バージョンみたいな雰囲気(実際，DAEMもこの枠組で書けることが示されています) 手元にEMのコードがあれば，実装も非常に容易．

ただ，やっぱりそれだけだと一発ネタにしかならないので，「制約付きEM」のほうへ話を進めています．「制約付きEM」というと聞きなれないアルゴリズムですが，Un(semi-)supervised learningにおいて，事前知識を用いてモデルがとんでもない方向へ飛ぶのを防ごう，というモチベーションに基づく技法のようです．

自然言語処理におけるアプリケーションでは，たとえば以下のような制約を考えることができます：

  • 品詞タグ付けなら

    • ある文には，名詞と動詞が最低一つづつ含まれる
    • ある語が，複数のPOSに割り当てられることは稀

  • 機械翻訳におけるアラインメントなら

    • L1->L2のアラインメントと，L2->L1のアラインメントは一致する
    • L1の一つの語が，L2の多数の語と対応付けられることは稀

  • 関係抽出なら

    • ある種のエンティティと，ある種のエンティティの間には，特定のリレーションしか成り立たない
      • (PERSON, LOCATION) -> LIVE IN
      • (ORGANIZATION, PERSON) -> WORK FOR

こういった事前知識に基づく制約を満たすモデルを，確率分布の集合として表現し，そこから離れないようにEMアルゴリズムを行うことによって，ラベルつきデータが利用可能ではない（または，少量しか存在しない）状況において，うまく学習が行おうというのが，「制約付きEM」の肝となる部分です．直感的には，Posterior Regularizationの論文から引用した以下の図が分かりやすいかもしれません．（日本語注釈は私によるものです）

歯切れのよいタイトルに惹かれて軽い気持ちで選んだ論文でしたが，そこそこホットな分野のようで，ACL 2011のチュートリアルで1トラックまるまるこの話題だったりしたらしく，問題設定や前提を理解するのにけっこう苦労しました．

結果として，UEMの本題ではなく，問題設定や先行研究の紹介に半分近くのスライドを割くことに・・・．まぁ，楽しんで頂けたようなのでなによりです．しかしひさびさに緊張感のあるプレゼンだった．

最後のスライドにも記載しましたが，以下の文献が，理解の助けになると思います．

  • “Rich Prior Knowledge in Learning for Natural Language Processing” ACL 2011 tutorial
    • ACLで行われたチュートリアルの資料です．このファミリーに属するアルゴリズムについての資料の多くはここからたどれるようになっています．各種のアルゴリズムのあいだの関係についてよくまとまっていますし，著者らによって異なる表記系もすっきりまとめられているので読みやすい．今回は取り上げませんでしたが，Labeled Feature とかも追ってみるとおもしろそうなトピックなので，ぜひ．
  • “Posterior Regularization for Structured Latent Variable Models” JMLR 2010
    • 今回紹介した論文の元ネタになっている Posterior Regularizationの論文です．品調ラベルづけにおける例とともに，少しづつ丁寧に議論が進められており，さすがジャーナルだけあって読みやすいです．

ひさびさに負荷の高い一週間だったので，来週はすこしゆっくりしたいと思います．（日記）

Prowl+zshで快適お昼寝タイム

眠いですね．

とくに機械学習のクロスバリデーションや，ごっつい集計クエリなどの時間のかかるバッチジョブを流す間，とても眠い．

私の場合，そういう時にはディスプレイの前を離れて，お昼寝タイムにすることが多いです（基本いつも眠い）．実行時間の見積もりがつくようなジョブなら適当にアラームかけておけばよいのですが，実際はそうも行かないことも多いですよね．

そこで，iOSデバイスにプッシュ通知を送れるアプリケーション Prowl を用いて，ジョブの終了をiPhoneに通知してくれる短いRubyスクリプトを書いてみました．ジョブ終わったらブルッと鳴って目覚めスッキリ．

Requirement

gem は gem intall prowl でインストールできます．

Instalation

まず，ProwlのウェブサイトからAPIキーを取得します．いちおう登録＆ログインが必要ですが，メールアドレスは不要のようです，ログインして，API keys のページに進むと フォームが二つありますが，Provider keyは第三者にキー入りアプリを配布するときに使うものなので，今回は Generate a new API key のほうでOK．Noteは空でもいいのでとにかくサブミットボタンを押すと，API keyが取得できます．

そんでもってスクリプトの中身はこんな感じ．API_KEYには先ほど取得したキーを．

環境変数 PROWL_NOTICE_TITLE, PROWL_NOTICE_CONT にメッセージをセットしておくと，その中身を通知してくれます．通知を受け取りたいプロセスと環境変数の設定をラップするようなシェルスクリプトを組んでおくと良いかもしれません．ARGV についてはあとで説明します．

Example

1

$ sleep 10 && ruby prowlnotification.rb

という感じでプロセスを実行すると，終了時にこんな感じで通知してくれます．

1
2
3

$ export PROWL_NOTICE_TITLE='たいとるだよ'
$ export PROWL_NOTICE_DESC='おわったよ〜'
$ ruby prowlnotification.rb

とかするとこんな感じ．

zsh(precmd/preexec)との組み合わせ

しかし，毎回コマンド打つのは面倒ですね．そこで，処理時間が一定以上かかったらGrowlで通知するzshrc - 心魅 - cocoromi で紹介されている方法を使うと， コマンドに一定以上の時間がかかったときに自動で通知してくれます． 今回のスクリプトに合わせてちょっと改造してみました．PROWL_NOTICE_TIMEを適当に設定して.zshrcに潜ませてみてください．

とくに環境変数が設定されていない場合は，プロセスの名前と引数が通知されてきます．(ARGVを通してRubyスクリプトに渡されます)

まとめ

  • 眠い時でも思う存分バッチを走らせることができるRubyスクリプトを書いてみました．
  • 実行に一定時間以上かかったら自動で通知してくれるzshの設定例を紹介しました．
  • 勤務時間中の居眠りは計画的に．

Prowlは有料(執筆現在250円)アプリですが，単に通知を受け取るだけではなく，通知を他のアプリにフォワードしてくれる機能があったり，Chromeで開いているページを通知してくれるプラグインが用意されていたり，そこそこ遊べそうなので，今回導入してみました．

もし同様の機能の無料アプリをご存知でしたら是非教えてください．

参考