a lonely miner

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

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

書類を整理していたら，むかし読んだ 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ではあるが，まだ何かできることは無いかと考えると，うまくいくかはともかくとして，いろいろ面白そうだ．（ニッチなためか，機械学習屋さんがまだあまり進出してこない分野でもあるので）

Comments