[Python]N階マルコフ連鎖で文章生成

概要

マルコフ連鎖を利用してPythonで文章生成を行う。

マルコフ連鎖

マルコフ過程

wikipediaには以下のように説明されています。

マルコフ過程（マルコフかてい、英: Markov process）とは、マルコフ性をもつ確率過程のことをいう。未来の挙動が現在の値だけで決定され、過去の挙動と無関係であるという性質を持つ確率過程である。

今日の天気が晴れなら明日の天気は８０％で晴れ、２０％で雨ということが分かっていれば、未来の挙動（明日の天気）が現在の値（今日の天気）で決定されるので、これはマルコフ過程です。

マルコフ連鎖

wikipediaには以下のように説明されています。

マルコフ連鎖（マルコフれんさ、英: Markov chain）とは、確率過程の一種であるマルコフ過程のうち、とりうる状態が離散的（有限または可算）なもの（離散状態マルコフ過程）をいう。

離散的とは状態と状態が切り離されている、ということです。
サイコロは１、２、３、４、５、６の６つの状態をとり、１と２の間の状態というものはありません。
実に離散的です。
「晴れと雨の間の状態（曇り）があるじゃないか」という考えもあるかと思いますが、「これは晴れ（雨）！」と決める基準を作ってしまえば、状態は「晴れ」と「雨」しかないので離散的となります。

文章生成

文章生成における状態

文章生成における状態とは、「文字」や「単語」、「文節」などです。どれだけ区切りを細かくするかの問題です。

「今日はいい天気です」　という文章を文字ベースの状態遷移で考えると、
「今」→「日」→「は」→「い」→「い」→「天」→「気」→「で」→「す」　となります。
単語ベースの状態遷移で考えると
「今日」→「は」→「いい」→「天気」→「です」　となります。

今回は単語ベースで文章生成していきたいと思います。
つまり、「今日」という単語から次の単語の「は」を選ぶイメージです。
上の一文だけだと「今日」の次に「は」が来る確率は１００％ですが、多くの文章を用いてモデルを作れば、「今日」の次に来る単語は、「は」が２０％、「も」が１５％、・・・のようになってくるはずです。
この確率に従って次の単語を選んでいきます。
ただこれだと日本語として意味のわからない文章を生成しがちです。
助詞の「は」の次に来る単語は無数にありますからね。
そこで、n個の単語を見て次の単語を選択するようにします。

N階マルコフ連鎖と単純マルコフ連鎖

例によってwikipediaからの引用。

次の状態が現在を含めた過去N個の状態履歴に依存して決まる確率過程を、N階マルコフ連鎖（もしくは、N重マルコフ連鎖、N次マルコフ連鎖）という。 これに対して、N=1の通常のマルコフ連鎖は単純マルコフ連鎖と呼ばれることがある。

「いやいや、マルコフ過程というものはそもそも過去の挙動と無関係であるという性質を持つんじゃなかったのか！？」と混乱しますが、過去の状態も込み込みで現在の状態として扱っているわけです。
同じ助詞の「は」でも、「今日」→「は」の時と「ご飯」→「は」の時は別の状態として考えるということです。大人はずるいですね。

N階マルコフ連鎖はN個の単語を元に次に来る単語を絞り込むので、意味の通った文章を生成しやすくなります。
しかし、Nを大きくしていくとモデル生成に使用した元の文章に似てくるので、オリジナリティがなくなってしまいます。

実装

環境

・MacOS Catalina 10.15.1
・Python 3.7

分かち書き

文章を単語ごとに区切っていきます。
形態素解析にはMeCabを使用しています。

markov_chain.py

import re
import MeCab

def wakati(text):
    t = MeCab.Tagger("-Owakati")
    parsed_text = ""
    for one_line_text in one_sentence_generator(text):
        parsed_text += " "
        parsed_text += t.parse(one_line_text)
    wordlist = parsed_text.rstrip("\n").split(" ")
    return wordlist

def one_sentence_generator(long_text):
    sentences = re.findall(".*?。", long_text)
    for sentence in sentences:
        yield sentence

MacOSの場合、MeCabは以下のコマンドで使えるようになります。

$ brew install mecab
$ brew install swig
$ pip install mecab-python3

短い文章を分かち書きをするだけなら以下のようにすればOKです。

t = MeCab.Tagger("-Owakati")
parsed_text = t.parse(text)

ただこれだと長い文章を入れた時にNoneが返される時がありました。
ですので「。」で終わる文章で区切って、１文ずつ分かち書きをしました。
「。」で終わらない文は、文ではないので気にしません。（暴論）
str.split("。")ではなく、正規表現で分割しているのは、str.splitが区切り文字（。）を消してしまうためです。

モデル生成

N個の単語をkey、次の単語をvalueとする辞書オブジェクトを作成します。
keyの作成にはPythonの標準ライブラリcollectionsモジュールのdeque型を使いました。
deque型はlist型に似ていますが、deque型は配列の両端の処理に優れています。
公式ドキュメントには以下のように書かれています。

Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。
list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。

またdeque型は

max_len = 3
queue = deque([], max_len)

のように、最大長を指定することができ、最大長を超えると先頭から要素を削除してくれます。いやもうこれN階マルコフ連鎖のために作成されてますね。（暴論）

この配列をkeyとしたいわけですが、辞書型のkeyはハッシュ可能(hashable)でなければいけません。ハッシュ可能の説明は省きますが、tuple型はハッシュ可能です。ですので、tuple型に変換したものをkeyとして使用します。tuple型への変換は非常に簡単です。

tuple_type = tuple(deque_type)

上記を踏まえて辞書を作成します。
出来上がる辞書はN=2の場合、以下のようなイメージです。
{ ("今日", "は") : ["いい", "晴れ", "雨", ・・・] ,
　("は", "いい") : ["天気","気分","天気", ・・・],
　("いい","天気"):["です","だ","だ",・・・], ・・・}
valueは重複ありの配列にすることで、あとで選択する時に単にランダムに選択すれば、出現頻度に応じた確率で単語が選ばれます。

markov_chain.py

from collections import deque

def make_model(text, order=2):
    model = {}
    wordlist = wakati(text)
    queue = deque([], order)
    queue.append("[BOS]")
    for markov_value in wordlist:
        if len(queue) < order:
            queue.append(markov_value)
            continue

        if queue[-1] == "。":
            markov_key = tuple(queue)
            if markov_key not in model:
                model[markov_key] = []
            model.setdefault(markov_key, []).append("[BOS]")
            queue.append("[BOS]")
        markov_key = tuple(queue)
        model.setdefault(markov_key, []).append(markov_value)
        queue.append(markov_value)
    return model

構造はいたって簡単です。

単語を順番に取り出して

for markov_value in wordlist:

キュー（deque）をタプルに変換して、keyを作成。
keyがモデルにない場合は新しく作成して

model.setdefault(markov_key, [])

単語をvalueの配列に追加して

model.setdefault(markov_key, []).append(markov_value)

最後にキュー（deque）の最後尾に単語を追加して、次の単語の処理に向かいます。
この時、キューの最大長を超えていれば、先頭の単語は勝手に削除されます。

queue.append(markov_value)

今回のコードでは文の始まりに「"[BOS]"」を挿入しています。
BOSとは、Beginning of sentenceのことで文字通り、文頭を表します。
文末を表すEOS(End of sentence)もありますが、今回は句点「。」をEOSと見立てています。

文章生成

モデル作成できたので、次はようやくモデルから文章を生成していきましょう。

markov_chain.py

import random

def make_sentence(model, sentence_num=5, seed="[BOS]", max_words = 1000):    
    sentence_count = 0

    key_candidates = [key for key in model if key[0] == seed]
    if not key_candidates:
        print("Not find Keyword")
        return
    markov_key = random.choice(key_candidates)
    queue = deque(list(markov_key), len(list(model.keys())[0]))

    sentence = "".join(markov_key)
    for _ in range(max_words):
        markov_key = tuple(queue)
        next_word = random.choice(model[markov_key])
        sentence += next_word
        queue.append(next_word)

        if next_word == "。":
            sentence_count += 1
            if sentence_count == sentence_num:
                break
    return sentence

なんだかんだ色々と書いていますが、

next_word = random.choice(model[markov_key])

のところで、単語を選択しています。
後はモデル生成と同様にキューに選択された単語を追加しながら、
またキューをkeyとして次の単語を選択します。
今回のコードでは句点「。」が５回選ばれた時点で終了させています。
句点「。」が永遠に出ない可能性もあるので最大１０００単語に設定しています。

まとめ

ここまでのコードはほぼ関数を定義しただけですので、
実際に文章生成をする場合は、最後に以下を追加してください。

markov_chain.py

if __name__ == "__main__":
    text = "適当なとても長い文章。"
    order = 2
    model = make_model(text)
    sentence = make_sentence(model)
    print(sentence)

変数orderがN階マルコフ連鎖のNにあたります。大きければ、意味の通った原文に近い文章を生成しますし、小さければオリジナリティ溢れる意味不明な文章を生成します。

試しに「走れメロス」で文章生成してみましょう。
N=４としています。

[BOS]殺される為に走るのだ。
[BOS]その王の顔は蒼白で、眉間の皺は、刻み込まれたように深かった。
[BOS]メロスは、王の前に引き出された。
[BOS]老爺は、あたりをはばかる低声で、わずか答えた。
[BOS]私を、待っているだろう。

殺される為に走ってますね...。

ちなみにN=2だとこんな感じなります。

[BOS]メロスに捧げた。
[BOS]御命令を拒めば十字架にかけられて、その品々を買い集め、それから、賢臣のアレキス様を、いま、なんの気がかりも無い。
[BOS]待っているのである。
[BOS]陽は既に西に傾きかけて、メロスは川岸にうずくまり、男泣きに泣きながらゼウスに手を挙げて報いた。
[BOS]私は約束をさえ忘れてしまえ。

命令に背くと品々を買い占められるみたいです。

今後の課題

マルコフ連鎖には以下の弱点があります。

• 過去の情報を拾おうとする（Nを大きくする）と、オリジナリティがなくなる。
• オリジナリティを高めようとする（Nを小さくする）と、意味不明な文章を生成する。

次回はそんなマルコフ連鎖の弱点を克服する（かもしれない）LSTMで文章生成していきたいと思います。

参考

マルコフ連鎖の簡単な説明
　マルコフ連鎖による文章生成
参考にしたコード
　[Python]マルコフ連鎖で自動文章を生成する
dequeの説明
　Pythonのdequeでキュー、スタック、デック（両端キュー）を扱う