マルコフ連鎖で文章を自動生成してめぐるちゃんの召喚を試みた話

二次元美少女を現世に召喚、それは誰もが一度は願ったことのある夢です。
ところで、皆様はしゅうまい君をご存知でしょうか。

twitter.com

これは文章を自動生成してツイートを行うbotの一つです。が、例えば

のような、あたかも意思を持っているかのようなTweetを行うことがあります。

さて、そんなしゅうまい君はどのような仕組みで動いているのでしょうか?

しくみ

フォローしている人の発言を拾って形態素にばらして溜める

マルコフ連鎖複数の短文を自動生成

適当な短文を選んでTwitterにつぶやく

引用:http://enpitsu.org/shuumai/

なんと、蓋を開けてみるとたったのこれだけです。つまり、このステップを模倣するだけでしゅうまい君のような文章が自動生成できることになります。
ここでポイントとなるのが1ステップ目の、「フォローしている人の発言を拾う」という部分です。この部分からしゅうまい君はTwitterのタイムラインから単語を拾っていることが推測できます。

では、今日はしゅうまい君に倣って因幡めぐるちゃんのセリフを拾って文章を自動生成してみましょう。

マルコフ連鎖ってなんだ

表題にもあるマルコフ連鎖とは何でしょうか?
説明のため、一般的な音楽ゲームプレイヤーにカメラを取り付けて一週間観察し、その行動の遷移を以下の図にまとめました。

f:id:h1dia:20160426230827p:plain

彼は気の向くままに音ゲーをプレーし、お腹が空いたらとりあえずラーメン屋に向かってラーメンを食べ、また気が済むまでゲームをプレーし続けます。 ここでポイントになるのが、この人は「現在の状態のみを判断して次の行動を起こしている」という点です。 もしもラーメン屋に向かった直後でもお腹が空いたらラーメンを食べますし、お腹が空かなければ何も食べずにゲームセンターと家を永遠に往復することもありえます。

このような「現在の状態のみで未来の状態が決定する」ようなモデルをマルコフ過程といい、図のような飛び飛びの状態(離散状態)のマルコフ過程マルコフ連鎖といいます。

さて、これを自然言語に当てはめて考えてみましょう。文章を考えます。

私は田中です

これはナマコです

この二つの文章を形態素にばらすと、

私 は 田中 です

これ は ナマコ です

となります。形態素ごとに別れた文章に単語に前後関係があるとすると、次のように図示することができます。

f:id:h1dia:20160410201803p:plain

文章のつながりから「私」と「これ」は「は」に向かい、「は」は「田中」か「ナマコ」のどちらかに分岐するといえます。
すると、上記の文章の他に

これは田中です

私はナマコです

と、新たに二つの文章をマルコフ連鎖によって生成することが出来ました。
今回はこのような方法を利用して文章を生成することを目標とします。

めぐるちゃんコーパスを用意する

まずは頑張ってめぐるちゃんのセリフデータを用意します。

chokudai.hatenablog.com

切り抜いた画像を頑張って二値化してGoogle Driveに投げればOCRで読み込んでくれるっぽいので頑張ります。

f:id:h1dia:20160410180224p:plain

二値化しなくてもフォント周りを調整しておけばある程度読んでくれるっぽいのでこのアプローチで適当にセリフデータをテキストに書き出します。

Mecabを利用してめぐるちゃんのセリフを形態素にばらす

書き出した文章を形態素ごとに分割するために、Mecabを利用して文章を分かち書きに直します。
新語にも対応されているmecab-unidic-NEologdを辞書データに利用します。

github.com

これを

f:id:h1dia:20160410203459p:plain

こうじゃ

f:id:h1dia:20160410203506p:plain

マルコフ連鎖を実装する

実装します。上の例では単語ごとのつながりを見ていましたが、文章の流れをある程度保持するために3-gram(3単語をひとまとめとして扱う)でマルコフ連鎖を実装します。

#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <string>
#include <sstream>
#include <random>
#include <functional>
#include <ctime>

int main() {
    // ファイル入力
    std::ifstream ifs("corpus.txt");
    if (ifs.fail()){
        std::cerr << "fail" << std::endl;
        return -1;
    }

    // スペースで分かち書きされた文章を読み込む
    std::vector<std::vector<std::string>> words;
    std::string str;
    while (std::getline(ifs, str))
    {
        std::vector<std::string> res;
        
        int strpos, current = 0;
        while ((strpos = str.find_first_of(" ", current)) != std::string::npos) {
            res.push_back(std::string(str, current, strpos - current));
            current = strpos + 1;
        }

        words.push_back(res);
    }
    
    // 構築
    std::unordered_map<std::string, std::vector<std::pair<std::string, std::string>>> markov;

    for (int i = 0; i < words.size(); i++) {
        std::string index = "_BEGIN";
        int j;
        for (j = 0; j < words.at(i).size() - 1; j++) {
            markov[index].push_back(std::pair<std::string, std::string>(words.at(i).at(j), words.at(i).at(j + 1)));
            index = words.at(i).at(j);
        }
        markov[index].push_back(std::pair<std::string, std::string>(words.at(i).at(j), "_END"));
        index = words.at(i).at(j);
    }

    std::random_device rd;
    auto markov_raw = markov;

    // 出力
    for (int i = 0; i < 100; i++) {
        std::string input = "_BEGIN";
        while (true) {
            if(input == " _BEGIN")
                std::cout << input;

            if (markov[input].size() == 0)
                break;

            // 文章の始まりの単語をランダムに決める
            auto myrand = std::bind(std::uniform_int_distribution<int>(0, markov.at(input).size() - 1), std::mt19937(rd()));
            int rand = myrand();

            std::cout << markov.at(input).at(rand).first;

            if (markov.at(input).at(rand).second == "_END")
                break;

            std::cout << markov.at(input).at(rand).second;
            input = markov.at(input).at(rand).second;
        }
        std::cout << std::endl;
        markov = markov_raw;
    }

    return 0;
}

動かしてみよう

では、めぐるちゃんを召喚してみましょう。めぐるちゃん!しゃべってー!!

f:id:h1dia:20160426234048p:plain

f:id:h1dia:20160426232556p:plain

因幡めぐるちゃんが登場するゲーム、サノバウィッチはいわゆるえっちなゲームです。片っ端からめぐるちゃんのセリフを突っ込むとこうなります。当たり前ですね。
気を取り直してえっちな文章を除いたコーパスで文章を生成してみます。

f:id:h1dia:20160426233846p:plain

だいぶマシになりました。生成された文章からなんとなくめぐるちゃんの香りを感じることができます。

マルコフ連鎖はあくまで文字列同士の前後関係しか見ないため、文中には品詞がめちゃくちゃな順番で現れてしまいます。
Mecabで文章を形態素に分解しているので形態素の品詞情報を取り出すことが一応可能です。

f:id:h1dia:20160426234940p:plain

なので、コーパスにちゃんと品詞情報を書き込んであげて、文法に従って文章を生成してあげるともう少しまともな文章が得られるのではないかなーと思います。面倒そう。