マルコフ連鎖によるアルゴリズムの設計

マルコフ連鎖の概要と設計方針

※マルコフ連鎖に関する説明はWeb上にたくさんあるので、要点だけ説明します。

（単純）マルコフ連鎖は、将来（次）の状態は、現在の状態のみで決まるという系列です。

コード進行で言うなら、次の和音は、現在の和音によって確率的に決まるという仮定に基づいています*1。

例えば、３つの和音 {C, F, G} が以下のような確率で状態遷移するとします。

この状態遷移に関する遷移行列は次のように書けます。

この遷移行列をＰとすると、k番目の状態を漸化式で表すことができます。

つまり、

初期状態：最初の和音
遷移行列：各和音が、次にどの和音に進行しやすいか

を設定すれば、先ほどの漸化式を用いてコード進行を自動生成することができます。

なお、遷移行列の具体的な遷移確率を設定する方法は、(1) データを集めて事前学習、(2) 人が手動で調整の２つがあります。

(1) だと、そのデータっぽい感じにコード進行を生成できますが、データの収集・処理をする必要があります*2。また、状態が多くなると、その分、多くのサンプルを集めないとアルゴリズムのパフォーマンスが出にくいです。

一方で (2) だと、データ収集・処理の必要がなくお手軽ですが、アルゴリズムのパフォーマンスをよくするためには手間暇かけて値を調整する必要があります。遷移状態が増えるとしんどいです。

データだけだと信用しきれない部分がある*3ので、突き詰めるなら (1) + (2) のハイブリッドになると思います。

Python での実装

クリックで展開

import sys
import time
import numpy as np
import matplotlib.pyplot as plt


S = ["C", "F", "G"]
P = np.array(
    [[0.20, 0.40, 0.40],
     [0.33, 0.17, 0.50],
     [0.50, 0.33, 0.17],
     ])

     
n_iter = int(sys.argv[1])
state = np.zeros(len(S))
P_cum = [np.array([P[m, 0:n+1].sum() for n in range(P.shape[1])]) for m in range(P.shape[0])]
P_r = np.zeros(P.shape)
state_index = 0
state[state_index] = 1.0
print(f"Step      State\tStationary")
print(f"=====================================")
for iter in range(0, n_iter):
    print(f"{iter:0=8}: {S[state_index]}\t{np.round(state,4)}")
    # Transition
    r = np.random.random()
    pre_state_index = state_index
    state_index = np.where(P_cum[state_index] > r)[0][0]
    state = np.dot(P.T, state)
    P_r[pre_state_index, state_index] += 1.0
    time.sleep(0.0001)

print("\n> Stationary dist.")
eig_val, eig_vec = np.linalg.eig(P.T)
idx = np.argmin(np.abs(np.real(eig_val) - 1))
# Get an eigenvector correspond to the eigenvalue equal to 1.
w = np.real(eig_vec[:, idx]).T 
w /= np.sum(w) # Normalize
print(f"Recurrence relation:\t{np.round(state,2)}")
print(f"Eigen-decomposition:\t{np.round(w,2)}\n")

# Check transition matrix
for k in range(len(S)):
    P_r[k] /= P_r[k].sum()
print("P")
print(P)
print("P_r")
print(np.round(P_r, 2))