前回の記事で述べたk-means法でもうちょっと遊んでいる。特徴量の正規化、段階的k-means++法、ヒープによるレベリング、特徴量の先鋭化を実装した。
特徴量の正規化
疎な特徴量であることで様々な厄介事が起こる。そこで、疎であることは大前提として認めつつも、できるだけ密な方向に特徴量を正規化したくなる。クラスタの対象となる各単語の特徴量は類義語や共起語や訳語とそれらのスコアからなる。それら類義語や共起語や訳語を、語幹となる語に正規化できれば、より密になるはずだ。
類義語や共起語は英単語なので、WordNetやWiktionaryから抽出した語幹情報を使って正規化する。例えば「respectfully」は「respectful」の派生語であり、「respectful」は「respect」の派生語であるということがわかってる。これを使って、「respectfully」「respectful」「respect」のいずれもは「respect」に正規化する。「respected」「respectable」「respectability」などなど、「respect」の子孫である単語は全て「respect」に正規化される。この処理を容易にするために、特徴量のTSVデータに各単語の親の情報を載せている。個々の要素が正規化されて同じラベルになる複数の特徴量を持っていた場合、最大値を採用する。これによって、例えば「majesty」は「respectable」と強く共起し、「queen」は「respectfully」と強く共起する場合でも、「majesty」と「queen」の関連性を見出すことができるようになった。
訳語は日本語なので、Mecabで解析した上で、いくつかのヒューリスティクスで正規化する。まず、先頭と末尾の助詞と助動詞を取り除く。例えば、「丁寧な」は「丁寧」になり、「を省略しない」は「省略しない」になる。活用語は語幹に直す。例えば、「走り」は「走る」になる。さらに、もっと過激な正規化も行う。漢字二文字を含む語は、漢字だけ残して平仮名を消してしまうのだ。例えば「起床する」は「起床」になり、「立ち上がる」は「立上」になる。全ての入力データに同じルールを適用していて、意味のある情報が残っているなら、どんな変換をしても構わないのだ。
正規化によって、特徴量ラベルの種類は半分くらいになった。依然として疎な特徴量であることに変わりはないし、種類が減ったから精度が上がるとも限らないのだが、自分でデータを見る限りでは、内容はそんなに悪くない感じだ。「pick」の特徴量は以下のようになる。
- choose=1.000, select=0.934, pluck=0.832, gather=0.805, option=0.754, ..., 選択=0.241, ピック=0.235, 採取=0.163, 選抜=0.135, つるはし=0.132, 摘む=0.120, ...
段階的k-means++法
k-meansの初期値依存の不安定さを回避すべく、k-means++法を元にした方法を採用している。要素の中で距離が互いに遠いものをクラスタの数だけ選んで、各クラスタの初期値を、選んだ要素で初期化するのだ。今回はこれをさらに改良する。
k-means++で初期化すると、k-meansの1回目のイテレーションでは、互いに離れた要素の近くにある要素が集まってクラスタを作るので、いきなりまともなクラスタができることが期待できる。しかし、特徴量が疎な場合、うまく働かない場合がある。k-means++が各クラスタの初期値として選ぶ要素は一つだが、その一つが、クラスタに期待される全ての特徴量の次元に有効な値を持っているわけではない。例えば、最初に「resume」といった多義語が選ばれた場合、「レジュメ」という意味の関連語と「再開する」という意味の関連語が集まった初期クラスタが形成される。この混合状態のままイテレーションを続けると、いつまでたっても収束しないかもしれない。クラスタとしての方向性を決定づけるには、より多くの情報が必要だが、しかし曖昧性は最小化したい。
そこで、2回目のイテレーションではクラスタ内の中心に最も近い2語だけを選んでクラスタの内容を構成する。2回目に「resume」と「interview」が選ばれたなら「レジュメ」という意味のクラスタとして進化するだろう。「resume」と「continue」が選ばれたなら、「再開する」を意味するクラスタとして進化するだろう。あるいは、「resume」に求心力がない場合には、2回目のイテレーションにはそもそも選ばれずに、別の2語がクラスタの方向を決定づけるだろう。3回目のイテレーションでは、上位3語を使う。4回目のイテレーションでは、上位4語を使う。4回もやれば十分だろう。
ヒープによるレベリング
特徴量が疎であることで各クラスタが持つ要素数にばらつきが出ることは前回述べた。そして、それを解決すべく、定期的に要素を強制移住させてクラスタの規模を揃えるレベリング処理を実装していた。この定期的にやるってところがダサいので、毎回のイテレーションで常に最適なレベリングができるように改良した。
例えば10000語を1000個のクラスタに分けるとすると、各クラスタの要素数は10個であることが望ましい。従来の実装では、何回かのイテレーションの後に、要素数が制限を超えていたクラスタから、そうでないクラスタに要素を移動させていた。この移動処理をイテレーションの中に入れてしまう。以下のようなアルゴリズムになる。
- 全ての要素と全てのクラスタの類似度を予め計算して、記録しておく。
- 個々の要素をどこかに格納するとう処理をタスクとみなし、全要素をタスクキューに入れる。
- タスクキューが空でない場合、タスクを取り出す。
時間計算量は、要素数N、クラス数Mに対して、O(N * M * log(N/M)) ということになって、現実的な範囲だ。事前に全ての組み合わせで類似度計算をしておかないと遅くてしょうがないので、その結果を保持すべく、空間計算量が O(NM) になってしまうのは仕方ないところだ。昨今のPCで10000語*1000クラスタくらいなら全く問題ないだろう。
このアルゴリズムだと、各要素の視点で、自分にとって最適なクラスタに一度は所属することができることは保証される。ただし、クラスタには定員があるので、自分よりもそのクラスタにふさわしい奴らに負けて追い出される可能性はある。自分よりふさわしくない奴らには負けないという意味で最適だ。追い出された場合でも、自分にとって次にふわしい場所に必ず挑戦できる。そこで勝って生き残れるかどうかは知らんが。そして、いつかは自分の居場所が必ず見つかる。競争と福祉の絶妙なバランス。世界よ、そうあれかし。
特徴量の先鋭化
レベリングによって全てのクラスタは同じ要素数を持つようになるが、これは下位の要素の精度が悪化することを意味する。第1志望で入ってきた希望に満ちた要素と、第2志望以下の滑り止めとして入らざるを得なかった要素が混在しているのだ。さて、各要素の特徴量を合成してクラスタの特徴量を決めよう。このクラスタの方向性を決めるにあたって、誰の意見に重きを置くべきか。
重心に近い要素に重みを強くして特徴量を拾った方が、落ち武者達に起因するノイズを減らせそうだ。段階的k-means++法と似たような考え方とも言えるか。うまいことに、各要素のクラスタ重心との類似度が0から1に分布するので、それを重みにして、各要素のベクトルを合成しよう。その上で、上位160次元で作業空間を再構成する。
結果
上述の全ての工夫を適用して、改めて英単語のクラスタリングを行った。重要英単語3600語を300クラスタに分けた結果のTSVデータと、重要英単語9600語を600クラスタに分けた結果のTSVデータを置いておく。イテレーションは100回行った。結果をいくつか抜粋してみよう。
- vocal, song, music, harmony, chorus, choir, gospel, groove, soul, pop, acoustic, loud
- yacht, boat, vessel, scooter, steep, aircraft, craft, warp, pirate, ton, navy, basket
- climb, mount, rise, rocket, surge, arise, swell, disgust, revolt, rebel, hip, tower
前回の結果よりも顕著に良くなっている感がある。特徴量の正規化と段階的k-means++法のおかげか、全体的に精度が上がり、なぜそのクラスタができたのかというのを想像しやすくなった。各クラスタにおける各要素の類似度の平均を取ると、3600語の方で0.58を超え、9600語の方で0.61を超えるようになった。また、レベリングの工夫と特徴量先鋭化のおかげか、下位の語の納得感も向上した気がする。下位の語において、下位の語同士の関係性が認められるというよりは、上位の語との関係性が認められるようになったような感じがする。
例によって連想英単語帳の方も更新しておいた。やはり、9600の方が単語の選択肢が多い分だけ納得感の高い結果が出ている。
単語集とは直接の関係はないが、語彙力年齢診断も最新データに更新しておいた。単語集の構築のために入れた各種ヒューリスティクスのおかげでカバレッジがかなり向上している。
