ベイズ最適化と、しりとり
モチベーション
機械学習ばかりやらずに、久々にプログラミングをしたくなったというか、下手の横好きというか、プログラムを書いてみたくなりました。自分で思った通りにロジックを組めるのは楽しいものです。
YouTubeを見ることを趣味の一つにしているのですが、たまに見かけるトリビアの泉の番組が結構面白い。知識欲とは人間が本来持つ本能的な欲求なんですかね。
トリビアの泉で、広辞苑の辞書の単語をつなげていったら、どれくらいつながるかという問題設定で、東大協力のもと、15万語ぐらいを可能な限りつなげていったら、75775語繋がったという話。[1]
図1. 動画は、違法アップロードの可能性があり消されるかも知れない
動画中では何の疑問点もなく、最長のしりとりネットワークを作成したといっていたが、数万を超える単語の問題をソルバー等で解くのは容易ではないのではないかという疑問が結構強く残った。
自分でも再現してみたくなったけど、広辞苑の日本語をワープロソフトで手入力していくのはホント闇というかやりたくないなぁと思ってコメント書いたら突っ込まれた。これもネットの宿命。
単語を集める
有償でも、広辞苑の辞書から単語が引っ張れるのなら電子版を買おうかと思ったが、パースできるかどうか保証がないし、一般的な語にしか対応しておらず、最新の単語データとくらべてしまうとどうも見劣りする。
NEologdという形態素解析エンジンがある。頻繁にアップデートされており、この前Fate/Grand Orderという単語も追加された。
@HOPPOU:~/mecab-ipadic-neologd$ echo "Fate/Grand Order" | mecab Fate/Grand Order 名詞,固有名詞,一般,*,*,*,Fate/Grand Order フェイトグランドオーダー,フェイトグランドオーダー
NEologdのgithubでcloneしてインストールするために様々なファイルをダウンロードすると、ディレクトリの中に、名詞が含まれるcsvが含まれている。
$ ls | egrep "(n|N)oun" Noun.adjv.csv Noun.adverbal.csv Noun.csv Noun.demonst.csv Noun.nai.csv Noun.name.csv Noun.number.csv Noun.org.csv Noun.others.csv Noun.place.csv Noun.proper.csv Noun.verbal.csv neologd-common-noun-ortho-variant-dict-seed.20161017.csv neologd-noun-sahen-conn-ortho-variant-dict-seed.20160323.csv neologd-proper-noun-ortho-variant-dict-seed.20161110.csv $ ls | egrep "(n|N)oun" | xargs wc -l 546969 合計
語尾と語頭を普通につなげていってもうまくいかない
最初は広辞苑より収録数が多いし、適当につなげていってもうまくいくだろうという思惑があったが、うまくいかない。問題点として、語尾で終わる単語の分布と、語頭が特定の単語で始まる分布の違いが明らかになった。
68326個 都ジマ ミヤコジマ 68327個 まわりはな マワリハナ 68328個 鍋もの ナベモノ 68329個 野面 ノツラ 最後の文字は、 野面 ノツラ <- ラで始まる単語を発見できなかった☆
図2. 語頭の分布
図3. 語尾の分布
提案
うまくいかない原因として特定の語尾で終わる単語を頻出させすぎると、語頭でその語で始まる語が消費され尽くしてしまい、上手くいかないのではという仮定がある。
そこで、確率的に採択するように、語尾をキーにして採択確率を変えるという手法を提案する。
さて、単語の採択率を調整するはいいが、どのように決めようかとなる。何らかの最適化アルゴリズムを使うのが妥当だと思われるが、以前なら探査空間を限定したlbfgs[3]を使うことが多かったのだが、iteration何回か指定できない、数値に対して厳密に動作するので確率的に決定する系では難しいなどの理由で、少々使いづらいと考えていた。
最近良く聞く、ベイズ最適化を適応できる問題（機械学習を考えたくなかったけど、近いアルゴリズムを採用せざる得なかっためう）ということに気づいて実装を行った。
ベイズ最適化とは
詳しく説明すると、より詳しい人に刺されるので、表面的な知識だけ。
図4. アクションごとのベイズ最適化
手法にもよるかも知れないが、基本的には背景の分布を説明するのに最も適したガウス過程の事後分布を作っていくものである。観測する回数が大きくなれば、その分、真の事後分布に近づいて行くものと思われる。
あまり賢くない最適化手法では、グリッドサーチで探査空間を量で押し切ったり、極小解に陥ってしまいそうであるが、gifアニメを見てみると、赤の分布が３つほどあるが一番大きな赤を集中して探索しているため、賢いという印象。
実装
実装の詳細はgithubに転載するので、確認する必要があれば参考にしてほしい[4]
基本的には、最初に単語のプールを作って、ランダムにそのプールから取り出していくのであるが、この取り出しのランダム性に細工をして、特定の語尾の単語を引き当てにくくするというアプローチである。
泥臭い実装になってしまったが、まあ私はこんなものです。
nが単語のデータオブジェクトで、n.tailが語尾です。randomで採択関数をスキップしています。
if 'ラ' == n.tail and random.random() < ps[7]: continue if 'ウ' == n.tail and random.random() < ps[6]: continue if 'ゲ' == n.tail and random.random() < ps[5]: continue if 'ズ' == n.tail and random.random() < ps[4]: continue if 'マ' == n.tail and random.random() < ps[3]: continue if 'リ' == n.tail and random.random() < ps[2]: continue if 'ケ' == n.tail and random.random() < ps[1]: continue if 'エ' == n.tail and random.random() < ps[0]: continue
psがベイズ最適化で決定されるパラメータ郡で、最適な不採択率を決定する。
また、今回のベイズ最適化では、Gaussian Processを利用した。
図5. 特定の末尾の文字を持つ単語の採択率をベイズ最適化が決めた定数で下げる
# 目的の分布がこの関数で発生させる。 # 目的関数って言っちゃうとだめというのは知ってる。 # os.systemしてるの、ゴミと言うツッコミは勘弁して def target(x1, x2, x3, x4, x5, x6, x7, x8): xs = map(str, [x1, x2, x3, x4, x5, x6, x7, x8]) command = ["pypy3", "siritori.py"] command.extend(xs) os.system(' '.join(command) + " | tee buff " ) # 結果を取得 fret = float( open('buff').read().split('\n')[-3].split(' ')[0] ) return fret # boオブジェクトと探索範囲の決定 bo = BayesianOptimization(target, {'x1': (0, 1), 'x2': (0, 1), 'x3': (0, 1), 'x4':(0, 1), 'x5':(0, 1), 'x6':(0,1), 'x7':(0,1), 'x8':(0,1)}) bo.explore({'x1': [0, 1], 'x2': [0, 1], 'x3':[0, 1], 'x4':[0, 1], 'x5':[0, 1], 'x6':[0,1], 'x7':[0,1], 'x8':(0,1) }) # maximizeの実行, iter 30 bo.maximize(init_points=5, n_iter=30, kappa=2) # 最大化するときのx1~x8のパラメータの表示 print(bo.res['max'])
結果
139,813語 + 1(ンで終わる単語)で、しりとりチェーンを構築することができたので、まぁ、こんなものなのかなという感じ。詰めればもっと行きそうだけど、しりとりチェーンコンテストとかあっても良いかもしれない。もっとiteration回せば、もっと行くようにも思える。
考察
1. ベイズ最適化はパラメータの探索に非常に効果があると思われる。従来の探査手法よりも、探査が少なく、なおかつ、確率的な系（予測する分布）に対しても有効そうである。(lbfgsbはすぐおかしくなる)
2. 機械学習では結構重い学習も度々行う必要があり、コンペティションなどになると、探査を効率よくできたものが時間的にも精度的にも有利なので積極的に採用していきたい技術である。
3. よくわかんないけど、アドホックな手法を使わずに演繹的にしりとりをこれだけの量解けなくない？Youtubeにサブグループ化してソルバーで解くとの案があったけど、どうなのかな。
結論
早速手持ちの案件に導入してみました。
パラメータサーチテクとして、優秀です。積極的に使っていきましょう。
