楽器の指遣いを最適化するアルゴリズムを考えて実装してみる

サンプルプロジェクト

https://github.com/Mya-Mya/UnsiOptimizer

本プロジェクトは、原案を私の友人が考え、数学モデルやアルゴリズムの構築、実装等を私が行ないました。

# 概要
楽器を演奏する際は、プロアマ問わず**譜読み**という作業を行います。譜読みとは、どの音をどの指で演奏するか(**運指**)を楽譜にある音符を見ながら決めていく作業で、具体的には音符に番号を付けていくことをいいます。譜読みは、いかに演奏者に負担の少ない、最適な演奏手順を見つけられるかが肝となります。

このように、音楽をやる上で大事な譜読みですが、初心者にとっては少し難しいです。楽譜を読み、音符と楽器の位置の対応を覚える必要があるため、かなりの時間と労力を要し、これが楽器演奏に対する敷居となっているというのです。

そこで友人は思いました。**自動的に譜読みを行い、運指を自動生成してくれるプログラムが欲しい** 、と。

友人に相談されて、私はこう考えました。
これは**演奏者への負担$J$を最小化するような運指$\\{f_i\\}$を見つける最適化問題というように定式化できるのではなかろうか**、と。

本記事では、私たちがどういうことを考え、どういうものを作ったのかを紹介します。

# 問題の定式化
今回は簡単のために、右手でピアノを弾くことを考えます。また、同時に2本以上の指で弾くことがないものとします。
### 図解
![2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/87a4ce08-9b56-579d-fa0e-2647800764d8.png)
まず、演奏者への負担というものを考えてみます。
例えば$i$番目の音がレ、$i+1$番目の音がミになっているような楽譜を弾くことを想定します。さてこの時、どのような運指ができるでしょうか。
![3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/926a31f4-bb86-88ba-0849-bb5354f52823.png)
組み合わせとしては$5\times5=25$通りあることが想定できます。が、それぞれの組み合わせでその難易度が違いそうです。
例えば運指が$2\to3$であれば、容易に動かすことができると思います。
![4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/71d248b0-c5d1-61fb-a303-40d8ca4f69a2.png)
でも、$4\to1$とかだと、手を動かすのがちょっと難しいと思います。ご自分でもやってみて下さい。
![5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/06afb558-b0cd-002c-b39d-33458cc108d5.png)
このように、2音間の運指には25通りあるものの、簡単な運指と難しい運指があります。
一般的な楽譜では音がいくつか連なって1つの楽曲を成しますが、それぞれの音間で簡単な運指と難しい運指が存在し、無数の経路が出現します。
![6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/0adf89b1-04b2-391a-85c6-cacef78511d4.png)
ここから**全体的に見て最も簡単な(=演奏者への負担が最小の)経路**というものを見つけることができれば、今回の最適化問題の解決となりそうです。
![7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/de6dc4a1-50a1-ea83-422b-378bb7633323.png)

### 数式で定式化
音が$N$個並んでいる楽曲を考えます。

以下のような記号を定義します。
* $n_i$ : $i$番目の音の高さ(e.g.$n_i=$`A3#`)
* $f_i$ : $i$番目の音を弾く指、$f_i\in\\{0,1,2,3,4\\}$(普通は指番号は1から始まりますが、プログラミング言語の仕様とかを考慮して今回は0から始めます。)
* $\\{f_i\\}_{i=0}^{N-1}$ : 楽曲全体に渡る運指。
* $C$ : コスト行列と呼ぶもの。2音間の運指の難しさを数値で表している$5\times5$行列。
* $C_{ij}$ : コストと呼ぶもの。1音目を$i$の指で、2音目を$j$の指で弾く時のコスト = 運指の難しさ。
* $\Delta F(i)$ : $i$番目の音から$i+1$番目の音への遷移に**同じ色の鍵の移動**がいくつ含まれているか。
* $\Delta H(i)$ : $i$番目の音から$i+1$番目の音への遷移に**違う色の鍵の移動**がいくつ含まれているか。

$\Delta F$と$\Delta H$について、いくつか例を示します。
遷移|$\Delta F$|$\Delta H$|備考
---|---|---|---
C4→E4|2|0|ドは白い鍵、ミはその2つ隣にある白い鍵。
F4→G4#|1|1|ファ→ソは白い鍵同士ですが、ソとソ#の鍵の色は違います。
C3→C3|0|0
C4#→D4#|1|0|どちらも黒い鍵。
E4→F4|1|0|どちらも白い鍵。
C4→A3|-2|0|下降する場合は、負の値を付けます。
C4→G3#|-2|-1|ド→ラは白い鍵同士、ラ→ソ#は違う色。

お分かりの通り、$\Delta H$は$\Delta F>0$の時$\Delta H\in\\{0,1\\}$、$\Delta F<0$の時$\Delta H\in\\{0,-1\\}$です。

なぜこのような面倒臭いものを定義しているかというと、この$(\Delta F,\Delta H)$の組み合わせは鍵盤上での物理的長さや位置関係と対応しており、これが同じであれば、コスト行列$C$も大体同じだろうという仮定を置いているからです。

ということで、$(\Delta F,\Delta H)$の組み合わせの時のコスト行列を$C(\Delta F,\Delta H)$とおきます。

さてここまでが準備でした。今回解きたい問題は、ズバリこうです。

評価関数$J$を以下のように定義します。
```math
J(\{f_i\}) = \sum_{i=0}^{N-2}
C(\Delta F(i),\Delta H(i))_{f_i,f_{i+1}}
```
楽曲内のそれぞれの音の遷移におけるコストを全て足した和になっています。
これを最小にするような運指列$\\{f_i\\}^*$を探します。
```math
\{f_i\}^*=\arg\min_{\\\{f_i\\\}}J(\{f_i\})
```
これが最適化問題です。

# 解法
解法も色々考えました。友人は巡回セールスマン問題やニューラルネットワークで解けるのではないか。あるいは量子コンピュータを使う必要があるのではないかと話していました。私も遺伝アルゴリズムなどで解けるのではないかなどと考えていましたが...
結局のところ、以下のような**動的計画法**で求まります、はい...。

最適な運指列を求める際、最初から長さ$N$の運指列を作るのではなくて、長さ$0$から始めていき、常にコストが最小になるようにしながら運指列を伸長していくというアイデアです。

### 初期設定
$N\times 5$のサイズを持つ表$T$を用意します。
$T_{n,k}$ には、$n$番目の音符を指 $k$ で弾く時の最適な運指列 $f_{n,k}$ とその時のコストの和 $c_{n,k}$ がタプル形式で格納されます。
初期状態を$T_{0,k}=([k],0)$ for $k\in\\{0,1,2,3,4\\}$とセットします。

### 反復処理
以下の処理を順番に最後の音まで行います。

```math
k_*'=\arg\min_{k'\in\\\{0,1,2,3,4\\\}} c_{n-1,k'}+C(n-1)_{k'k}
```
$n$番目の音符を指$k$で弾くことを考える時、$n-1$番目の音符を何の指で弾いている状態を選べば最もコストが小さくなるかを計算し、その指を$k_*'$とします。その後、コストの和の更新
```math
c_{n,k}\longleftarrow c_{n-1,k_*'}+C(n-1)_{k_*'k} 
```
と運指列の更新
```math
f_{n,k} \longleftarrow \mathtt{concat}(f_{n-1,k_*'}, [k])
```
をします。

ただし$C(i)$は、$i$番目の音から$i+1$番目の音へ遷移する際のコスト行列です。

### 実装
以上の説明をPythonで実装すると、以下のようになります。
```python
# 初期設定
T = [[None for k in range(5)]for n in range(N)]
for k in range(5):
    T[0][k] = ([k], 0)
# 反復処理
for n in range(1,N):
    for k in range(5):
        # k'*を求める
        cost_s_for_nk = []      
        for kdash in range(5):
            cost_for_kdash = T[n-1][kdash][1]+C[n-1][kdash][k]
            cost_s_for_nk.append(cost_for_kdash)
        minimum_cost_for_nk = min(cost_s_for_nk)
        best_kdash = argmin(cost_s_for_nk)
        T[n][k] = (
            T[n-1][best_kdash][0]+[k],#運指列の更新
            minimum_cost_for_nk#コストの和の更新
        )
```

# 数値実験
### コスト行列
まずはコスト行列$C(\Delta F(i),\Delta H(i))$をどう用意しようという話になります。これには

1. いくつかの運指例を取り込んで、逆強化学習みたいな処理を通じて自動作成する。
1. 経験則に基づいて手動で作る。

といったアイデアがありましたが、今回は私がピアノをやっていたので2.を選び、オレオレ経験則に基づいて行列を作成しました。1.は別途やってみたいですけど、なんか難しそうですよね。もしかしたらひとつの研究テーマくらいにはなるかもしれないと、これと似たようなことを研究している身として思います。

私が作ったコスト行列の例を示します。例えば$(\Delta F,\Delta H)=(2,1)$の時のコスト行列は
```
 .7, .1, .3, .3, .3
 .6, .7, .2, .1, .0
 .9, .9, .6, .4, .0
1.0,1.0,1.0, .6, .4
1.0,1.0,1.0,1.0, .8
```
です。これを$(\Delta F,\Delta H)=(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(3,0),(3,1),(4,0)$についてそれぞれ作りました...疲れた。

:::note warn
あれれ？音が下降する時のコスト行列はどうしたの？と思われるでしょう。
実は...面倒臭くて作ってなくて、代わりに、**上昇する時のコスト行列を転置する**ことで代用してます😅数式にすると、$C(\Delta F,\Delta H)=(C(-\Delta F,-\Delta H))^T$ってやってます。
:::


ここら辺の実装は上記GitHubの`myamya1model`辺りを参照して下さい。

### 「永遠のひとつ」(田村ゆかり) を最適化するぜ!!
実際に楽曲を用意して運指を最適化したいと思います。ここではアニメ『ISLAND』のOP「永遠のひとつ」(田村ゆかり)のサビの運指を最適化します。
まずは右手だけの楽曲をMusescoreで作り、.midファイルに書き出します。
![スクリーンショット 2023-05-12 23.36.12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/1bc654fd-cdc4-3822-38eb-d419d28574e8.png)
.midファイルをpretty_midiでそれを読み込み、音列$\\{n_i\\}$を得ます。
まずはランダムな運指$\\{f_i\\}$を作りながらそれぞれの評価関数$J(\\{f_i\\})$を収集し、ヒストグラムを作ってみます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/1c00ebc9-20ce-c323-7f70-988884af90cb.png)
評価関数の平均と標準偏差は$39.3\pm3.8$となりました。さて、ここからどれだけ減らせるでしょうか。

動的計画法アルゴリズムで得られた最適解$\\{f_i\\}^*$の評価関数は...
**なっっなんと、$J=1.8$になりました！！！🎉🎉🎉**
すご！(◎_◎;)めちゃくちゃ最適化されてるやん。

ということで最適解$\\{f_i\\}^*$を見てみるましょう。親指が0であることに注意してください！

```python
[4,3,1,4,3,4,4,3,4,3,2,1,4,3,1,4,3,4,2,1,0,1,0,2,1,0,0,4,3,1,4,3,4,1,4,3,4,4,0,1,1,0,1,0,1,2,0,2,1,2,1,2,1,2,1,2,0,1,4,4]
```

実際に指を動かしてみると、ほとんどの音において負荷の少ないいい感じの運指ができていることが分かります。でも、ちょい微妙なところがあることも事実です。

この解が出た根拠を辿ると自分で定義したコスト行列に行き着きます。なので、運指の最適解が微妙である場合、このコスト行列がまだ正しく設定できていないことが考えられます。今回はオレオレ経験則に基づいてフィーリングでコスト行列を作っていたため、正しくコスト行列を作れていなかった可能性があります。最適なコスト行列を用意するためには、逆強化学習のようなものを使って推定する必要があるかもしれません。

ちなみに「永遠のひとつ」は以下から試聴できます。

<iframe width="560" height="315" src="https://www.youtube.com/embed/n4QWGinK5S0" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>

いやあ、このアニメ好きで、好きで、めっちゃ大好きなんですけど、
でもさ、最後さ、~~そこさ、2人に囲まれれば幸せになれるだろが〜〜〜！！！！~~

# まとめ
楽器の譜読み(運指の設計)を最適化問題に落とし込み、動的計画法を用いて最適な運指を決定しました。結果として、そこそこいい感じの運指を得ることができたものの、完全ではありませんでした。その理由の1つとして、評価関数の元となるコスト行列を正しく作れていないことが考えられます。コスト行列も何かしらの統計処理を用いて推定する仕組みが必要だと思います。

友人のアイデアのおかげで、芸術の分野にもこのような最適化問題が隠れていることが分かり、大変興味深かったです。