Julia × N階マルコフ連鎖 で二階堂千鶴の台詞を自動生成する

# 諸注意
・この記事は [LIVE THE@TER NET Users' Advent Calendar 2023](https://adventar.org/calendars/8923) 9日目の記事です。Advent Calendar の企画詳細はリンク先をご参照ください。**Qiita Advent Calendar とは一切関係ありません。**
・この記事は**アイドルマスター ミリオンライブ！のユーザー(通称：プロデューサー)向けの内容**と**Qiitaユーザー向けの内容**の両方を含みます。見出しの直前の以下の標記を参考にご自身に合った部分を読み進められてください。
【P】......プロデューサー向けの内容を含みます。
【Q】......Qiitaユーザー向けの内容を含みます。

# 1. はじめに
## 【P】1.1. ご挨拶
プロデューサーの皆さん，**みりっほー！** まうんてんと申します。
普段はXの他，アイドルマスター ミリオンライブ！のP向けの非公式Misskeyインスタンス [LIVE THE@TER NET](https://live-theater.net) をうろちょろしており，今回，先述のAdvent Calendar 企画に参加させていただきました(※本企画はLIVE THE@TER NETにアカウントを持つ個人による非公式企画であり，インスタンスが主催するものではありません)。

突然ですが，私たちミリPが必ず履修しなければならないプログラミング言語とは何でしょうか？そう，[**Julia**](https://julialang.org) (**ジュリア**)ですね！
Julia言語についての詳細はリンク先をご覧ください。まあ早い話が既存の色んな言語のいいところを詰め合わせた卍最強卍言語です。特に数学や物理の領域での活躍が目立ちます。ロックだな！

**......とはいえ，いきなり数学や物理の話をされても「何が嬉しいんだ？」という方も多いでしょう。**

今回はJuliaの日々のプロデュース活動への援用例として**N階マルコフ連鎖**を取り上げます。簡単に言えば文章の自動生成です。これさえあれば24時間365日いつでも担当の言葉に耳を傾けることができます。

具体例として~~N階だけに~~私の担当である**二階堂千鶴**の台詞を生成してみます。**実質ジュリちづ**です。果たしてN=2でセレブはセレブたり得るでしょうか？早速やっていきましょう。

## 【Q】1.2. 本記事の概要
・JuliaでN階マルコフ連鎖を実装し，特定のキャラクターの台詞を自動生成します。
・形態素解析はAwabi.jlを使用し，学習データの作成と文章生成はJuliaでコーディングします。
・自動生成の例として，[アイドルマスター ミリオンライブ！](https://millionlive-theaterdays.idolmaster-official.jp) に登場するアイドル [二階堂千鶴](https://millionlive-theaterdays.idolmaster-official.jp/idol/chizuru/) を取り上げます(出力結果をより理解するため，リンク先をご一読されることを推奨します)。

# 【P・Q】2. N階マルコフ連鎖とは
詳細な説明については以下を参照なさってください(分かりやすいアウトプットをありがとうございます)。

[[Python]N階マルコフ連鎖で文章生成](https://qiita.com/k-jimon/items/f02fae75e853a9c02127) / [@k-jimon](https://qiita.com/k-jimon) 様
[N階マルコフ連鎖によるキャラクターのセリフ自動生成器を作ってみた](https://qiita.com/takaito0423/items/1a39d790b5e5b8e4cf36) / [@takaito0423](https://qiita.com/takaito0423) 様

とてもざっくりまとめると
・N階マルコフ連鎖(による文章生成)では，(N-1)つ前の単語から現在の単語まで，合計Nつの単語の情報から，次の単語を予測します。
・単語の予測精度は，より多くのデータ(既存の文章)を学習させることで上昇します。
・Nの値が大きいほど，多くの過去の単語を考慮できますが，新規性のある文章を作るのが困難になります。
・Nの値が小さいほど，新規性のある文章が生成される可能性が高まりますが，その分破綻した文章が生成される確率も高まります。

# 3. 実装
## 【Q】3.1. 実装の指針 / 実行環境
以下を参考にJuliaへ翻訳しました。この場をお借りして感謝申し上げます。
[[Python]N階マルコフ連鎖で文章生成](https://qiita.com/k-jimon/items/f02fae75e853a9c02127) / [@k-jimon](https://qiita.com/k-jimon) 様

Juliaおよび使用したパッケージのバージョンは下記の通りです。
```julia
Julia Version 1.9.1
Commit 147bdf428cd (2023-06-07 08:27 UTC)
Platform Info:
  OS: macOS (arm64-apple-darwin22.4.0)
  CPU: 8 × Apple M1
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, apple-m1)
  Threads: 1 on 4 virtual cores
```
```julia
"Awabi" => v"0.1.3"
```

## 3.2. 具体的な実装手順

### 【P・Q】I. 既存の台詞データを集める
当たり前ですが，コンピュータはゼロから個々のキャラクターの文章を生成することはできません。必ず事前にデータを学習させる必要があります。今回は以下のサイトを参考に台詞を書き起こしました。~~正直これが一番大変だった~~

・[ミリオンライブWiki](https://millionlive.info)
・[アイマス ミリシタ攻略まとめwiki【アイドルマスター ミリオンライブ！ シアターデイズ】| Gamerch](https://gamerch.com/imasml-theater/)

但し，以下の台詞は除外しました。
・サイトに掲載されている台詞のうち，ゲーム中で文字情報として確認できないもの(Ex. ミリシタ / ライブ開始時台詞)
・劇中劇の台詞で，本人の人格と関係がないと考えられるもの(Ex. ミリシタ /【夜想令嬢 二階堂千鶴】カード台詞)
・明らかに重複した台詞(Ex. ミリシタ / 各周年SR, SR+カード台詞)
また台詞は「！？。♪」を1文の区切りとして，テキストファイルの1行に1文を記述するように取り決めました~~本当は3点リーダで区切れそうなところもあったけど考えるのをやめました~~。最終的に659行，文字数換算で13,000字以上のデータを集めることができました。これを"Copus_Chizuru_Nikaido.txt"とします。

### 【Q】II. 台詞データを読み込む
それではデータを読み込みましょう。Juliaでは`eachline`を使って以下のようにテキストファイルを1行ずつ読み込むことができます。
```julia
f = open("Copus_Chizuru_Nikaido.txt", "r")
for line in eachline(f)
    # 読み込んだ各行のテキストに対して任意の処理
end
close(f)
```

### 【Q】III. 文章を単語に分ける(形態素解析)
形態素解析には[Awabi.jl](https://github.com/nakagami/Awabi.jl)を用います(但し辞書はMeCabを使用します)。
環境構築は公式ドキュメントの通りです。MeCabをインストールしていなけれはhomebrewでインストールして
```terminal
$ brew install mecab
$ brew install mecab-ipadic
```
Awabi本体はJuliaのパッケージモードから
```julia
(@v1.9) pkg> add Awabi
```
この辺りのパッケージの管理のしやすさはJuliaの強みだなとつくづく思います。
それではREPLで試しに使ってみましょう。公式ドキュメントの例を参考に...
```julia:ERROR
julia> using Awabi

julia> tokenize(Tokenizer(), "すもももももももものうち")
ERROR: MethodError: Cannot `convert` an object of type Type{Nothing} to an object of type String
```
いきなりエラー。確認したところ，mecabrcファイルが見つからないようなので自分で指定。以下の記事が参考になりました。
https://analytics-note.xyz/programming/mecab-config-get-dir/
変更は以下の通りに
```julia:SUCCESS
julia> using Awabi

julia> rcfile = "/opt/homebrew/etc/mecabrc" ;

julia> tokenize(Tokenizer(rcfile), "すもももももももものうち")
7-element Vector{Tuple{String, String}}:
 ("すもも", "名詞,一般,*,*,*,*,すもも,スモモ,スモモ")
 ("も", "助詞,係助詞,*,*,*,*,も,モ,モ")
 ("もも", "名詞,一般,*,*,*,*,もも,モモ,モモ")
 ("も", "助詞,係助詞,*,*,*,*,も,モ,モ")
 ("もも", "名詞,一般,*,*,*,*,もも,モモ,モモ")
 ("の", "助詞,連体化,*,*,*,*,の,ノ,ノ")
 ("うち", "名詞,非自立,副詞可能,*,*,*,うち,ウチ,ウチ")
```
無事動きましたね！
II.と組み合わせると以下の通りです。
```julia
using Awabi

f = open("Copus_Chizuru_Nikaido.txt", "r")
for line in eachline(f)
     result = tokenize(Tokenizer("/opt/homebrew/etc/mecabrc"), line)
     # resultはTupleを要素に持つVectorを返す
end
close(f)
```

### 【Q】IV. 学習
II.〜IV.までの処理をまとめた`make_model(order)`を示します~~かなり力技です~~。
```julia:make_model
using Awabi
using Serialization

function make_model(order)
    model = Dict{Vector{String}, Vector{String}}() ;

    f = open("Copus_Chizuru_Nikaido.txt", "r") ;
    for line in eachline(f)
        result = tokenize(Tokenizer("/opt/homebrew/etc/mecabrc"), line) ;

        # 1文が短すぎる場合にはスキップ(辞書が作れない)
        if length(result) - order > 1
            # sequenceを初期化する
            # sequenceの頭に[BOS]を挿入する
            sequence = Vector{String}(undef, length(result)+1) ;
            sequence[1] = "[BOS]" ;
            # result(1文)をidx順に回して単語毎にsequenceに格納
            for idx in 1:length(result)
                sequence[idx+1] = result[idx][1] ;
            end

            # index = 1から順に，order個をkeyとして取り出し，その次の語をValueとする
            for i in 1:length(result)-order+1
                key = copy(sequence[i:i+order-1]) ;
                if haskey(model, key)
                    push!(model[key], sequence[i+order]) ;
                else
                    model[key] = [sequence[i+order]] ;
                end
            end
        end
    end
    close(f)

    # シリアライズ
    serialize("model_Chizuru_Nikaido.dat", model) ;
end
```
当初は3.1.に示した参考資料に倣って`DataStructures.jl`の`Deque`型を使おうとしましたが無理でした~~なんで浅いコピーができないねん~~。
方針としては
・単語に分解したものを1文毎に`sequence::Vector{String}`に順序通り並べる(この際文頭に`[BOS]`キーワードをつける)。
・Vectorのindexの若い方から順に`order`個の語をkey, 次の語をValueとするような辞書を作る。
の手順です。ここで`order`はN階マルコフ連鎖のNに相当します。後述しますが，今回程度のコーパスの量であれば`Vector`を使っても大きな負担にはなりません。作ったモデルは`serialize`で再利用できるようにします。

### 【Q】V. 出力
いよいよ出力です。先程作ったモデルのファイル名(String)を引数`m`として以下の`make_new_sentence(m)`を使います。
```julia:make_new_sentence
using Random

function make_new_sentence(m)
    # モデルの読み込み(デシリアライズ)
    model = deserialize(m) ;

    output = "\n" ;
    sentence_counter = 0 ;
    # 初期条件候補(modelのkey::Vector{String}のうち，頭が[BOS]であるもの)を格納するVector
    initial_candidates = Vector{Vector{String}}() ;
    # モデルを探索し，頭が[BOS]なるkeyをinitial_candidatesに格納する
    for (key, value) in model
        if first(key) == "[BOS]"
            push!(initial_candidates, key) ;
        end
    end
    # [BOS]が見つからなければerror
    if isempty(initial_candidates)
        error("Not find Keyword") ;
    end
    # 初期条件の決定(now_condition::Vector{String})
    now_condition = rand(initial_candidates) ;
    order = length(now_condition) ;
    for i in 1:1000
        next_word = rand(model[now_condition]) ;
        output = string(output, first(now_condition)) ;
        popfirst!(now_condition) ;
        push!(now_condition, next_word) ;
        if next_word == "。" || next_word == "！" || next_word == "？" || next_word == "♪"
            for j in 1:order
                output = string(output, first(now_condition)) ;
                popfirst!(now_condition) ;
            end
            sentence_counter += 1 ;
            if sentence_counter == 5
                break ;
            end
            now_condition = rand(initial_candidates) ;
            output = string(output, "\n") ;
        end
    end

    print(output)
end
```
生成の手順としては
・`model`のkeyのうち，頭が`[BOS]`であるものを`initial_candidates`として抽出する -> 文章の始まりの際にいずれかが選ばれる。
・現在(と(N-1)までの過去)の状態を`now_condition`とする -> `rand(model[now_condition])`によって，次に続く単語`next_word`をランダムに選択する(これを繰り返す)。
・`next_word`として「！？。♪」が選ばれたら文の終わりだと判断し，一区切りとする。その後改行し，再度文頭の抽選が行われる。
・`sentence_counter`を設定し，規定の文数を出力したら`print`して終了。
となっています。

# 【P・Q】4. 実行結果
まず学習モデルを生成しましょう。3.2.IV.で示した`make_model(order)`を実行することで作られます。例えば~~二階堂~~2階マルコフ連鎖なら
```julia
make_model(2)
```
を実行することで`.dat`ファイルが作られるはずです。ついでに`@time`してみた結果が以下の通り。約1秒で学習モデルが作れます。
```julia:@time make_model
  1.210029 seconds (2.63 M allocations: 209.498 MiB, 1.52% gc time, 4.01% compilation time)
```
ではいよいよお待ちかねの出力のお時間です。まずはN=2の場合。
```julia:Output(N=2)
[BOS]この商店街も、待ちましょう。
[BOS]冷めないうちに、見て歩きましょう！
[BOS]舶来のケーキがありますわよ♪
[BOS]あとは、わたくしの使命ですわね！
[BOS]共に駆け上がりますわ！
```
所々で文脈の破綻も見受けられますが，千鶴さん特有のセレブリティ溢れる語尾は上手く生成できていますね。
今度は少し連鎖の次数を上げて~~四階堂~~N=4ではどうでしょうか。
```julia:Output(N=4)
[BOS]あとは、お菓子がもっと美味しくなるように魔法をかければ、できあがりですわ！
[BOS]夜のパレードは、こんなにも華やかで眩しくて、とても素敵なものなのですね。
[BOS]さ、涙を拭いて……。
[BOS]わたくしには、すこし子どもっぽいかしら？
[BOS]次は夢の中でお会いしましょう。
```
文章としてはよくまとまっていますが，これらは殆ど元の台詞データ通り，つまり**新規性がない文章**です。この辺りの匙加減がマルコフ連鎖の難しいところですね(知ったか)。

最後に`make_new_sentence`についても`@time`で実行時間を確認しておきましょう。
```julia:@time make_new_sentence
0.100770 seconds (287.28 k allocations: 16.743 MiB, 92.75% compilation time)
```
これなら24時間365日，担当の台詞を生成し放題ですね！

## 【P】5.1. まとめ
ということで，~~ミリP必修言語の~~Juliaで二階堂千鶴の台詞を無事生成することができました。私自身初めて自然言語処理に挑戦しましたが，勉強になることが多く楽しかったです。次はゲーム内コミュの会話テキストをデータに含めたりユーザー辞書やその他の精度向上手法を取り入れながら挑戦したいところです。
特にプログラミングをある程度ご存知の方からするとJuliaは数学や物理のためのお堅い言語に見えるかもしれません。ですが，**こういうこともできるんだよ！** というのを知っていただいて，遊びがてらに触っていただければ幸いです。**Julia，楽しいよ！**

さて，本Advent Calendar企画は今月25日まで続きます。既にP達の珠玉の記事が目白押しですので宜しければ是非1日分からご覧ください。面白いですよ！

https://adventar.org/calendars/8923

再度の宣伝になりますが，ミリオンライブのPが集う(非公式)Misskeyインスタンス LIVE THE@TER NET も合わせてよろしくお願いします。こっちも面白いですよ！

https://live-theater.net


## 【Q】5.2. まとめ
JuliaでN階マルコフ連鎖を実装し，実際にキャラクターの台詞を生成してみました。当方は自然言語処理はズブの素人ですが，それでもトータル8時間程度で実装できました。この実装自体はまだまだ初歩で，台詞データを増やしたり，キャラクター特有の表現をユーザー辞書に登録するなどすればより精度の向上も期待できるでしょう。また，メモリの効率化や高速化の余地も十分残されていると感じます。
Juliaでマルコフ連鎖というと，きちんと数学の話をしていることが殆どですが(そこがJuliaコミュニティの良いところなのですが)，もっと初歩的なことも(勿論)できるよ，ということで**自然言語処理~~とミリオンライブ~~を触るきっかけ**になれば幸いです。


# 【P・Q】Add. おまけ
折角なのでN=2で面白かった文章をいくつかご紹介。
```julia:Output
[BOS]働かざる者食うべからず、一緒に美味しい物を食べに参りましょう♪
```
いや食うんかーい！

```julia:Output
[BOS]あいにく急ぎの用事があったので断念しましたわ。
```
それならしゃーない

```julia:Output
[BOS]べべ、別に緊張などしていましたのかもしれませんわよ！
```
これがシュレディンガーの緊張ですか(いいえ)