マルコフ過程的な物を連想配列で作ってみた

私の勤務先では自然言語処理が非常に盛ん(なのかな？)で昔マルコフ連鎖を使った文章生成や楽曲生成などをしていた方もいらしたそうな。
そこでライブラリに頼らず(データフレームだけPandas使う)ゼロからマルコフ過程を作ってみようと思った。
自分の記憶が正しければある状態からある状態への遷移する確率だと思うのでそれベースで作りました。

関数

import pandas as pd
def marcov(arr):
    dic = {}
    for i in range(1, len(arr)):
        if arr[i-1] in dic:
            if arr[i] in dic[arr[i-1]]:
                dic[arr[i-1]][arr[i]] = dic[arr[i-1]][arr[i]] + 1
            else:
                dic[arr[i-1]][arr[i]] = 1
        else:
            dic[arr[i-1]] = {}
            dic[arr[i-1]][arr[i]] = 1
    col = []
    sumval = {}
    for val in dic:
        col.append(val)
        for val2 in dic[val]:
            col.append(val2)
            try:
                sumval[val] = sumval[val] + dic[val][val2]
            except:
                sumval[val] = dic[val][val2]
    col = list(set(col))
    for val in dic:
        for val2 in dic[val]:
            dic[val][val2] = dic[val][val2] / sumval[val]
    table = []
    for val in col:
        tmp = []
        for val2 in col:
            try:
                tmp.append(dic[val][val2])
            except:
                tmp.append(0)
        table.append(tmp)
    df = pd.DataFrame(table)
    df.columns = col
    df.index = col
    return df, dic

動かしてみる

moji = ["A", "B", "A", "A", "B", "C", "B", "A", "B"]
df, dic = marcov(moji)
df

出力されるデータフレームです。
基本情報とかの教科書だと行列だけ見ますが分かりやすく表にしました。
見方としてはインデックスが今の状態でカラムが次の状態です。
一般的には逆だそうですが自分はこっちの方が見やすいので。

過程のデータ

dic

{'A': {'B': 0.75, 'A': 0.25},
 'B': {'A': 0.6666666666666666, 'C': 0.3333333333333333},
 'C': {'B': 1.0}}

発展

これを使って実際に配列(今回は配列を使っているため)を生成するには先ほどのデータフレームを降順にして確率を累積化し、0から1まで取った値の中でどのデータとどのデータの間のデータを出力する事で生成する事が出来ます。

※コンピュータの計算は2進数なので10進数に表記した時に小数点以下は誤差があるため連想配列の合計値は1にならない事が多いです。

まとめ

自然言語処理技術難しい