和訳: Restricted Boltzmann Machines (RBM) - A friendly introduction

# はじめに
Restricted Boltzmann Machines (RBM) について、Youtubeのある解説動画がfriendlyで分かりやすかったので簡単に和訳してみようと思います。私なりの理解も含まれているので直訳ではないことをご了承ください。専門用語と数式に気をとられてイメージが湧きにくい方におすすめです。アニメーションの方が分かりやすいので、動画を流しながら横で参照していただけると良いかもしれません。
# 引用（Reference）
https://www.youtube.com/watch?v=Fkw0_aAtwIw

Luis Serranoさんの、[Restricted Boltzmann Machines (RBM) - A friendly introduction](https://www.youtube.com/watch?v=Fkw0_aAtwIw)という動画です。
機械学習の本を執筆されていて、動画を見る限りこちらも分かりやすそうです。
https://www.manning.com/books/grokking-machine-learning

# Mystery: ある屋敷の謎をRBMで表す
Aisha, Beto, Cameronの3人の人物が、ある屋敷の庭先に定期的に現れます。記録を取ってみると、彼らの出現には規則性があることに気づきました。AishaとCameronが2人とも現れるか、Betoが1人で現れるかのどちらかです。この3人はお互いを知らないのに、なぜでしょうか？

<details><summary>画像</summary>![1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/d08186a2-b292-bc42-df23-ffaede45ef41.png)</details>

実は、この家にはDescartesという犬と、Eulerという猫がいたのです。そしてAishaとCameronは2人とも犬好きで、Betoは猫好きだということが判明しました。もしかして、彼らの出現にはこの犬と猫が関係しているのではないか？という仮説を立てます。

<details><summary>画像</summary>![2.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/bd9c1a7f-eae2-780b-7f70-b487cfc8aca0.png)</details>


今までの話を数字で表してみます。人間がその動物のことをどれくらい好きかの「好き度」で人間と動物を繋いでいくと、Aishaは犬好きなので犬の好き度は「2」、猫は嫌いなので「-2」という重みづけをしてみます。他の2人、猫好きのBetoと犬好きのCameronについても同様に重みをつけます。
さらにもう1種類、数字が必要です。人間ならびに動物が、他からの影響を何も受けずに、そこにぽっと出現する確率です。これは、人間は3人とも等しく「1」と重みをつけてみます。動物について、今回は犬の方か出てくる確率が高く「2」、猫は犬よりレアキャラで「1」とします。
人間たちは現れたことがぱっと見で分かるので「Visible Layer」、動物たちはよく見ないと屋敷にいることに気づけないので「Hidden Layer」です。

<details><summary>画像</summary>![3.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/a8ffb60b-2a22-cdec-ebd1-ace38aa86b5f.png)</details>


# RBMの学習を理解するための準備
## Scores: RBMにおけるスコア付け
人間と動物の組み合わせ（3人と2匹なので$2^5=32$通り）がどういう条件で発生するのかを知るために、各組み合わせごとに「スコア」を計算していきます。たとえばA~Eが全員出現したときは、今まで出てきた数字を全部足し合わせて
$2+1+1+1+1+2-2-4+4+2-2=-6$
となります。一方で、A, C, Dの組み合わせで出現した場合は、数字を全部足し合わせると8になります。AishaとCameronは犬好きだと分かっていたので、8という比較的大きい数字になったのは納得できます。B, Dの組み合わせの場合はスコアは-1で、Betoは犬嫌いなのでこれも妥当です。
全ての組み合わせについてこのスコアを計算すると、表の通りになります。

<details><summary>画像</summary>![4.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/69401f9e-a556-9122-57c0-a81dd0d56475.png)</details>

以上の計算を、エネルギー$E$の数式で表します。スコアはエネルギーを負にした値で、これはBoltzmann Machineの起源に由来するのでそういうものだと思っておきます。
$$ E=-\sum_{i}b_iv_i-\sum_{i}a_ih_i-\sum_{ij}W_{ij}v_ih_j $$
（補足）急に仰々しくなりましたが、これは先ほどたどった計算を変数で表しているだけで、Visible Layerの人間の出現確率$b_i$、Hidden Layerの動物の出現確率$a_i$、人間ごとの動物の「好き度」$W_{ij}$に、それぞれの個体のステート（出現したら$1$、出現しなかったら$0$）を表す$v_i$と$h_i$をかけることで、その重みを足すか足さないかを決めています。

<details><summary>画像</summary>![5.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/4defac92-21ac-ef44-985c-0822598c4242.png)</details>

## Probabilites: スコアを確率に変換する（ソフトマックス関数）
全組み合わせ分の一覧表にしたスコアを、確率の値に変換します。単純に考えると各スコアをスコアの総和で割れば確率になるのですが、これだとたとえばスコアが$-1$, $0$, $1$のときに分母が$0$で成立しません。
そこで、付いている符号に関わらず全ての数字を正に変換してくれる、指数関数$e$を利用しましょう。正の数字に変換したあと、総和で割って確率で表します。

<details><summary>画像</summary>![6.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/0a9e6379-3681-f069-214d-1386c0b83705.png)
![7.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/503a7e5a-a84f-97fa-f965-59cdb2f4cd6c.png)</details>

指数関数を利用したこの作業を、屋敷の出現組み合わせ表に適用します。確率がとても低い組み合わせは丸めこまれて$0$になってしまいました。

<details><summary>画像</summary>![8.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/4fdb45b9-354b-862b-ae65-9dc30fdfc7c5.png)</details>

ソフトマックスと呼ばれるこの計算を、再び数式で表しておきます。

<details><summary>画像</summary>![9.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/45b82cde-ddca-f2dd-933c-c5486f8d978b.png)</details>

# RBMの学習
## Contrastive Divergence法
これまでA~Eの組み合わせを考えてきましたが、仮にグラフ中の全ての重みが$0$だとすると、全ての組み合わせが同じ確率で発生してしまいます。（簡略化のために数値ではなく黒いバーで確率を表しています。）

<details><summary>画像</summary>![10.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/89093f7d-53ca-d0a3-676b-6308d80529bb.png)</details>

しかし、現実にはA~Cの出現回数や組み合わせに規則性がありました。私たちは、この**実際のA~Cの出現データに基づく確率分布**を得たいのです。

<details><summary>画像</summary>![11.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/0e8d3963-d51a-c339-0d5d-e1e514a655f8.png)</details>

そこで、全ての組み合わせの発生確率が等しい状態からスタートして、

1. まず、実際の出現データに基づいて、その**A~Cの組み合わせが含まれる**ような、A~Eの組み合わせの確率を少し増加させます。
<details><summary>画像</summary>![12.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/bc0ab37c-82a9-5ebf-8680-13192fe63fde.png)</details>
2. 次に、1.で確率を増加させた組み合わせを含む**全ての組み合わせ**の確率を、少し減少させます。
<details><summary>画像</summary>![13.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/2752c63a-bca3-5fc4-7754-2343e230ca43.png)</details>

この2つのステップを繰り返せば、最終的に所望の確率分布が得られるのではないでしょうか。

<details><summary>画像</summary>![14.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/893bf771-fee8-7b37-c696-d537b54d7d76.png)</details>

この計算を、数式で表しておきます。

<details><summary>画像</summary>![15.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/381e885f-3113-567a-08eb-2b674a5eac7e.png)</details>

## 確率を増減させる方法（Learning Rate）
先ほどのステップ1.と2.で確率を「増やす」「減らす」という表現を用いましたが、実際に何をしているかというと、その個体にまつわる全ての重みを少しだけ加算・減算します。この量をLearning Rateと呼びます。

<details><summary>画像</summary>![17.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/dd876625-3701-75f9-7a5c-0e5b8e07683c.png)</details>

## Contrastive Divergence法 + ギブス・サンプリング
さて、屋敷の例では組み合わせが$2^5=32$通りで済みましたが、ノードの数が増えるとその組み合わせは2の累乗で増え、上記Contrastive Divergence法（以下、CD法）の計算量が膨大になってしまいます。例えばVisible Layerが$200$ノード、Hidden Layerが$100$ノードの場合は$2^{300}$通りという途方もない数になります。

そこで、CD法に、ギブス・サンプリングの要素を加えます。

1. 実際に起きたA~Cの組み合わせが含まれるようなA~Eの組み合わせから**ランダムに1つ選び**、その確率を少し増加させます。
2. 1.を含む全ての組み合わせから**ランダムに1つ選び**、その確率を少し減少させます。

これを繰り返すことで、最終的には実際のデータと傾向が一致するような確率分布が得られるということです。

<details><summary>画像</summary>![16.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/8ee327f1-788c-072c-efce-f382fbbbe584.png)</details>

しかし、1.を本当にランダムに選んだ場合は、このような結果にはならないはずです。元データには「AとCが登場した」「Bが登場した」という情報しかなく、AC, ACD, ACE, ACDEならびにB, BD, BE, BDEのどの場合なのかは不明なため、それぞれの確率が等しくなり、画像のようにACDならびにBEが突出するような結果にはなりません。そこで、RBMの隠れ層を考慮した結果になるべく、手順をさらに改良します。

1. 実際に起きたA~Cの組み合わせが含まれるようなA~Eの組み合わせから**条件付きで**ランダムに1つ選び、その確率を少し増加させる。
2. 1.を含む全ての組み合わせから完全にランダムに1つ選び、その確率を少し減少させる。

次の節で1.を、その次の章で2.を、詳しく説明します。

### 1. Picking Random Samples with Conditions: 条件付きランダムランプリング
ここで、今は学習の途中の状態で、次に「AishaとCameronが現れ、Betoは表れなかった」というデータを反映させたい、という場合を考えます。
Visible LayerとHidden Layerのそれぞれのノードは互いに独立なので、今注目しているノード（庭先に現れたAishaとCameron）以外のノードは無視できます。また、人間の出現確率の重みづけも無視します。このときのスコアを計算すると、
$0.9+0.5-0.4=1$
となります。シグモイド関数を用いてこれを$0$から$1$の間の確率に変換すると、$0.73$、つまり現段階でAishaとCameronが揃ったときにDescartesが現れている確率は$73\%$と求められます。

<details><summary>画像</summary>![19.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/ccae3f6e-40d3-7c07-19c2-a29151228f37.png)</details>

同様にAishaとCameronが揃ったときにEulerが現れている確率は$31\%$となります。

<details><summary>画像</summary>![20.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/684c0cb1-7452-60c8-7dca-94b1c9c7245f.png)</details>

（補足）ソフトマックスでは指数関数で変換してから総和で割って確率に変換していましたが、シグモイド関数は総和が分からなくても大体の確率に変換できるというイメージを持っています。

（補足）これにより、CD法+ギブスサンプリングのステップ1.では、下記の確率に応じてAC, ACD, ACE, ACDEのどれかが選ばれることになります。AishaもCameronも犬好きの猫嫌いなので、学習が妥当に進んでいることが理解できます。

|  | 確率 |
|:-:|:-:|
| AC | $(1-0.73)*(1-0.31)=0.1863$ |
| ACD | $0.73*(1-0.31)=0.5037$  |
| ACE | $(1-0.73)*0.31=0.0837$ |
| ACDE | $0.73*0.31=0.2263$ |

<details><summary>画像</summary>![21.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/fdd551a9-7b20-66df-da2e-f89b1af8ce04.png)</details>

### 2. Picking Completely Random Samples: ランダムサンプリング
次に、CD法+ギブスサンプリングのステップ2.で、全ての組み合わせの中から完全にランダムに1つ選択する方法です。学習の途中、ステップ1.でACDを増加させたような状況を考えます。
ここから、複数回ランダムにジャンプしてたどり着いた組み合わせの確率を、減少させます。このジャンプの回数は事前に定義するもので、コンピュータの演算能力の影響も受けます。
ジャンプの道順は、ACDの組み合わせからスタートし、Hidden Layerが同じくDである組み合わせの中から組み合わせをランダムに1つ（例: BCD）選び、ジャンプします。次はVisible LayerがBCDと同じくBCである組み合わせの中から組み合わせをランダムに1つ選び、ジャンプします。これを繰り返し、定義した回数分ジャンプしてたどり着いた組み合わせの発生確率を減少させます。

<details><summary>画像</summary>![24.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/b179d445-605a-6dbd-d2a3-76429258984e.png)</details>

# まとめ
実際のデータに基づきながら、Hidden Layerと重みづけを通して、考え得る全ての組み合わせの確率分布をRBMで表現できるようにしました。構築したRBMから、新たにデータを生成することも可能です。　といった内容だと理解しました。

<details><summary>画像</summary>![22.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/02ed4748-7fc0-0726-f969-4e03b09c9300.png)
![23.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/661344/cc1f3767-089b-ed66-7482-8df1969d1492.png)</details>