しりとりプログラム

今回はしりとりゲームをいかに長く続けることができるかに挑戦している。
こちらを参考にさせていただきました。
http://catindog.hatenablog.com/entry/2017/01/19/214348

プログラムはこっち
https://github.com/NaotakaKawata/shiritori

しりとりゲームとは
しりとりのルールについてはローカルルールなどを含むときりがないので割愛する。恐らく全員が納得する「ん」で終わる単語が出ればゲーム終了というルールを基本としている。

ルール設定
・「ん」で終わる単語を出力したら終了
・単語の在庫がなくなりしりとりを継続することができなくても終了
・制限時間１分以内、これを超えて出力されたものはカウントしない

辞書データの準備
今回しりとりに用いる辞書データに毎日新聞コーパスを用いた。コーパスをMecabで分かち書きを行い、しりとりの単語として使われるのに妥当だと思われる以下の品詞を抽出してしりとり用の辞書データを作成した。
・名詞
・動詞（基本形）
・形容詞（基本形）
・副詞
正直その単語使うのは変じゃない？ということはナシにしてください、課題で与えられたので仕方ないのです。

それではプログラムについて説明します。以下のサイトを参考にしてプログラムを作成しました。というかほぼまんまです。一応作成したプログラムはGitに上げています。変更したのは最初の単語を任意の入力にしたことと、使用するパラメータです。

プログラムの説明

def search(tail):
    ps = list(map(float, sys.argv[1:]))
    not_found = True
    if random.random() > 0.98:
        random.shuffle(bases)
    for e, _ in enumerate(bases):
        n = bases[e]
        if tail == n.head and "ン" != n.tail:
            if 'ル' == n.tail and random.random() < 1: continue
            if 'ズ' == n.tail and random.random() < 1 : continue
            if 'ヂ' == n.tail and random.random() < 1 : continue
            if 'ウ' == n.tail and random.random() < ps[0]: continue
            if 'ク' == n.tail and random.random() < ps[1]: continue
            if 'ツ' == n.tail and random.random() < ps[2]: continue
            if 'プ' == n.tail and random.random() < ps[3]: continue
            if 'ラ' == n.tail and random.random() < ps[4]: continue
            if 'リ' == n.tail and random.random() < ps[5]: continue
            if 'マ' == n.tail and random.random() < ps[6]: continue
            if 'イ' == n.tail and random.random() < ps[7]: continue
            if 'ワ' == n.tail and random.random() < ps[8]: continue
           　not_found = False
            break

search()は語尾の採択確率から出現する単語を制限する関数。変数tailには語末の文字が含まれています。psにパラメータをいれることで任意の語尾を含む単語の出現確率を操作します。

seed = bases.pop(random.randint(1, len(bases)))
chain.append(seed)
for i in range(100000):
    tail = chain[-1].tail
    t = search(tail)
    chain.append(t)
    print(len(chain), len(bases), t.orig, t.yomi)

大体こんなかんじで単語をつなげていってます。

わりとランダムでもしりとりはつながると思ったがどうもつながらない。その理由の一つとして語頭と語尾の分布の違いが挙げられる。しりとりが終了するのは「ん」で終わる単語を出す以外に単語が出てこないことでも終了する。例を図に示す。このように語尾の数が語頭よりも多い場合、次につながる単語を発見できずしりとりが終了してします。このことから語頭と語尾の偏りを確率を用いて平滑化しようと試みた。
ベイズ最適化
これ読んで理解しました。
https://qiita.com/masasora/items/cc2f10cb79f8c0a6bbaa
https://www.slideshare.net/hoxo_m/ss-77421091

最適化手法の一つであり、設定したパラメータを更新していき、目的関数が最もよくなるパラメータを探している。この手法の良いところは値が良くなる部分を重点的に探索してくれるため、グリッドサーチのように時間があまりかからないという点である。
今回はパラメータとして設定したのは「語尾」であり、偏りが大きいものパラメータにした。パラメータの数を増やしすぎるとかえって性能が落ちるし、適切でないパラメータを選択してもダメ。難しい・・・(´・ω・`)

結果
例として入力単語を「ウニ」としてしりとりを行った結果を表に示す。baselineとは最適化を行わず、単語をランダムに出現させた場合を示す。辞書の総単語数は81030個であった。


コメント

語頭と語尾の偏りを考慮することでしりとりは長く続くことが分かった。他の人がルールベースで書いた結果は約40000単語だったのでこのくらいの規模だと計算しきれるそうだ。辞書データが大きくなればなるほどこの方法は有効であり、語頭と語尾の偏りがなくなるため、よりしりとりが簡単につながると思われる。

ベイズ最適化により事前に確率を定義したが、しりとりをしている最中にある語尾の出現確率を変えることがベストであり、実装しようとしたが割とここから変更するのは手間であり、今の作りで語尾が出るごとに確率をいじったら途中でしりとりをつなげるスピードが遅くなり結果が出るまでに時間がかかるので断念。もしできたらルールベースで書いたものと同等の結果が出るだろう。