利尻山 初冠雪

本日（2021-10-17）北海道北部で、今季初の積雪が観測されたとのことです。さっそく、北海道最北端の名山、利尻山（利尻岳）の様子をライブカメラで確認してみました。冠雪というよりも、かなりたくさんの積雪がみられました。これから長い厳冬になります。

http://www.town.rishiri.hokkaido.jp/rishiri/ 
ライブカメラから引用（15:00ころ）

同（翌朝 07:00ころ）

同（翌日 15:00ころ）

スマホでニューラルネットワーク（ml5JS/TensorflowJS利用）その１

 【what is this】分類問題等で保持しているデータを使って機械学習させ、その結果を利用して、未知のデータを予測（分類など）したい場合があります。最近では、Tensorflow/Kerasなどを使えば、それは比較的楽に実現できます。ここでは、学習結果をスマホアプリに組み込み、スマホで利用することを行いました。Javascriptから使えるTensorflowJSやML5JSを利用しました。

■ 例題：1700万種の彩色を９種に分類する
　R、G、Bそれぞれ、0〜255まで取る場合の可能な色彩の種類は約1700万になります。それを９種（緑系、桃色、橙系、青系、茶系、赤系、黄系、紫系、灰色）に分類したいとします。そのためには、以下のようにします。参考資料[1]にあるML5.JSの例題Color_Classifierを利用させていただきました。定番の手書き数字認識MNISTばかりではなく、この例題も魅力的ではないでしょうか？

• ラベル付きの色彩データ（R:81, G:183, B:155→緑系、など）5,600組を用意
• これをPC上の、下図の画面にあるようなニューラルネットワークで学習（各層へのバイアスの表示は略しています。）
• 数十秒で学習は完了（スマホでも実行は可能と思われるが）
• 学習結果のモデル（ネットワーク構造と重みデータ）をsaveしておく

■ 学習結果のモデルをスマホで利用する
　上記でsaveしておいた学習モデルを、スマホへloadします。それを利用するスマホアプリをMIT App Inventorで作成しました。すなわち、約1700万種の彩色のどれを与えても、的確に９種のいずれかに分類できます。下図に、実行例（緑系、紫系、桃色など）を示します。第２候補も示しています。

　ちょっとデザインに凝ってみます。以下の画面設計は如何でしょうか？こちらの方が、ニューラルネットワークでpredictionを行っているというrealityがあると思います。下図左側は、[紫系= 0.90, 青系 = 0.04]、右側は、[橙系 = 0.84, 黄系 = 0.12]という結果でした。どちらも納得できます。

　時間のかかる学習をPCやクラウドで実行させ、学習済みモデルをスマホへloadしてアプリケーションを作成するという一般的な方法ですが、実際にやってみると適用範囲が広そうなことを実感できます。

■ なぜスマホで？

• MIT App Inventorを使うのですが、それに搭載されているWebViewerは強力なJavaScriptエンジンなので、Tensorflow.jsやml5.jsを活用できる。
• デザインが楽しい。上図のように、好みの画面設計がとても容易にできる。
• ニューラルネットワークを使う機械学習にもっと親しめる。

（補足）

• スマホ上で、ML5JSやTensorflowJSを使うには、スマホ上にWebサーバを立ち上げ、ドキュメントルートを設定し、そこへ学習済みモデルファイルと、関連コード一式を配置する必要があります。この辺りが少し面倒ですが、分かってしまえばあまり苦になりません。
• 別の問題として、最近のAndroid OSでは、このように立てたwebサーバに対しても、セキュリティが厳しくなっていて、いくつかのpermissionsが必要になるようです。また、どのWebサーバを使うかにもよります。例えば、Pixcel3a (Android 11)の場合は、比較的新しい"Serve:HTTP Server"と、古めの"KWS"サーバは共にOKですが、古いAndroid OS（Android 8.1）で利用可能だった"KSWEB"サーバは、403 Forbiddenのエラーが発生して使えませんでした。

参考資料

[1] ml5.js examples search, https://examples.ml5js.org

Running Q-Learning on your palm (Part3)

Japanese summary　本シリーズのPart1とPart2では、スマホ向けのQ-Learningアプリを開発し、それを簡単な例（直線の廊下でロボットが宝石を得る）に適用しました。今回は、このアプリを改訂し、２次元グリッドでロボットが行動できるようにしました。そして、グリッドサイズが大きくなるにしたがい、これまでのQ-tableを保持してQ値を更新する方法は、メモリ量と処理量の急増により破綻することを確認しました。それに変わる有望な方法として、Neural Networkの利用を検討し、それを（スマホではなく）PC上のPythonで実現した結果を示します。

Abstract
In Part 1 and Part 2 of this series, I developed a Q-Learning app for smartphones and applied it to a simple example (a robot gets a gem in a straight corridor). This time, I revised this app so that the robot can act on the 2D grid. However, as the grid size increases, the traditional method of holding the Q-table and updating the Q value becomes difficult due to the increase in memory capacity and processing volume. As a promising alternative, I considered using a neural network. And here's the result of doing that with Python on a PC (not a smartphone).

● Revised version of the Q-Learning app
In the revised version of the smartphone app, as shown in Fig. 1(a), the robot is trained to reach the gem while avoiding barriers on the 4x4 grid. The Q-Learning algorithm is basically the same as last time. There is one gem and one barrier, and their positions change randomly for each play (every episode). The robot also starts from a random position. After sufficient training, the robot can always reach the gem in the shortest route. On the other hand, if not well trained, the robot often gets lost and hits a wall, as shown in Fig. 1 (b).

● Memory capacity required for Q-Learning
The size of the Q-table required for this learning can be calculated according to the grid size and the number of gems and barriers. See Fig.2. The number of Q-table entries (i.e., the number of keys) is the total number of possible states, which in Case 1 (4x4) is 3,360. At this level, it can be held sufficiently even on a smartphone, and the amount of calculation is within an acceptable range. However, in Case2 (5x5), the total number of states increases sharply to over 6,000,000, even though only one gem and one barrier have been added. In this situation, regardless of whether it is a smartphone or a PC, processing is almost impossible due to both the amount of memory and the amount of calculation.

● Calculate Q-values with neural network (without holding Q-table)
For cases like Case2 above, you can think of a way to calculate the required Q-value with a neural network without holding the Q-table. To do this, transform the Q-value update formula for the neural network, as shown in Fig.3. This makes it possible to compare output and target  ([1]). It can be used to solve this problem with common supervised machine learning. This machine learning iteration allows the output to be closer to the target and, as a result, the Q-value to be closer to the exact value.

Fig.4 clearly shows how to use this neural network in the case of Case1. Note that in this example, the action "W (west)" is taken in the current state S. In this way, one learning is done only for one action in one state. This learning should be repeated for as many actions as possible, in as many states as possible.

● Calculation example of Q-value by neural network
I implemented a learning method using such a neural network in Python and executed it on a PC. This program is based on the Python program (using Tensorflow / Keras) published by Dr. Makoto Ito in reference [1]. Fig.5 shows the learning process for Case1 (4x4). It shows the situation where 10000 episodes were randomly trained. In the upper graph, the average sum of rewards per episode has reached about 0.8. On the other hand, when the neural network is not used, as shown in the figure on the right of Fig. 1(a) (although the characters are small and difficult to see), it is 0.8305, so both results are almost the same. The lower graph shows that the average number of steps a robot takes to reach the gem is about 2.9. This value is also valid considering the situation in Fig.1.

I have omitted the details, but in the case of Case2 (5x5), I was able to train well with this neural network as well. It took only about 3 minutes to run on a general PC, so I was able to confirm the usefulness of this method. This time I've only used the most basic neural networks, but for more complex problems (for example, if you need to remember the location of an object), you may need other neural networks such as LSTMs.

Acknowledgments
I was able to create a Q-value calculation program using a neural network by referring to the Python program published in the reference [1]. I would like to thank Dr. Makoto Ito, the author of this article.

References
[1] Makoto Ito's Blog Article: M-note Program and Electronic Work (in Japanese)
     http://itoshi.main.jp/tech/

Running Q-Learning on your palm (Part2)

 Japanese summary　前回の記事では、スマホ向けのQ-Learningアプリを開発し、それを簡単な例（ロボットが宝石を得る）に適用しました。今回は、ロボットの行動にいくつかのバリエーションを与えてみました。その場合でも、新しい行動の記述を追加する以外は、このスマホアプリをほとんど変更していません。今回の例題でも、Q-Learningによる学習の結果、ロボットは宝石を得るための最適な手順を自ら発見できました。

Abstract
In the previous article, I developed a Q-Learning app for smartphones and applied it to a simple example (a robot gets a gem). This time, I gave some variations to the behavior of the robot. Even so, I haven't changed much of this smartphone app, except to add a new behavioral description. In this example as well, as a result of learning by Q-Learning, the robot was able to discover the optimal procedure for obtaining the gem.

# For the case where the robot moves on the 2D grid, please see this revised version.

● New examples (two cases)
As in the last time, as shown in the figure below, the task is for the robot to move the corridor and get the gem. The actions that the robot can take are different from the last time, but learning the best steps to successfully acquire a gem is the same.

Consider the following two cases regarding robot behavior and its rewards. In both cases, an episode ends when a "Take" is performed (regardless of success or failure) or the robot deviates from the corridor boundary.

Case1:

• Take: Take the gem (reward = +5 if successful, otherwise -1)
• Forward: Move forward one block in the corridor (reward = -1)
• Jump: Move forward two blocks in the corridor (reward = -1)

Case2:

• Take: Take the gem (reward = +5 if successful, otherwise -1)
• Back: Go back one block in the corridor (reward = -1)
• Skip2: Skip two blocks in the corridor (reward = -1)

● Learning results in Case1 and the robot moving example
As a result of fully executing Q-Learning for Case1, we obtained a highly accurate Q-table. Using it, the robot was able to discover the optimal procedure for obtaining the gem, as shown in Fig.1. In the initial state of this example, the positions of R (Robot) and G (Gem) are expressed as "R . . G . .". The corresponding maximum value of Q-table is given by "Forward" and "Jump" (where, both values are 3.0.). Whichever is adopted, it will be the same after all, but here, "Jump" was taken. At the transition destinations after this, the action that maximizes the Q-table value was also taken, so the gem was successfully acquired. This is the best procedure.

● Learning results in Case2 and the robot moving example
The robot's actions possible in Case2 is different from Case1, but similarly, the robot was able to discover a procedure for obtaining the gem. The situation is shown in Fig.2. In the initial state of this example, the positions of R (Robot) and G (Gem) are expressed as "R . G . . .".  This procedure is optimal by combining "Skip2" and "Back".

Here's another slightly more complicated example in Case2. See the Gif animation below. In this example, the robot found the best steps to get the gem:

“R . . . G .”  →Skip2→Back→Back→Skip2→Take[success]

● Setting rewards according to purpose

The reward values shown above can be changed depending on the purpose. For example, unlike the above, let's say you want to get the gem in the best way, even if the robot starts at any position. In such cases, change the reward design of Case 2 as follows and name it Case 3.

Case3:

• Take: Take the gem (reward = +5 if successful, otherwise -1)
• Back: Go back one block in the corridor (reward = -1 if it is in the corridor after moving, otherwise -2)
• Skip2: Skip two blocks in the corridor (reward = -1 if it is in the corridor after moving, otherwise -2)

This reward design will serve your purpose, as in the examples below:

Running Q-Learning on your palm (Part1)

Japanese summary　このアプリは、人工知能技術の一分野である「強化学習（特にQ-Learning）」の基本的な考え方と仕組みを、簡単な例を動かしながら学ぶものです。強化学習は、AlphaGo（囲碁）や自動運転、自律制御ロボットなどで使われ、注目を集めています。ここでは、そのような実用レベルに立ち向かう前に、身近なスマートフォンを用いて、その技術のエッセンスに触れて親しむことができます。あなたの掌の上のスマホで強化学習を楽しもう！（このアプリは、MIT App Inventorを用いて開発されました。）

This app won the "2021 October's MIT APP INVENTOR OF THE MONTH" award. 

Abstract
This app explains the basic idea and mechanism of reinforcement learning (especially Q-Learning), which is a field of artificial intelligence technology, using simple examples. Reinforcement learning is used in AlphaGo, autonomous driving, autonomous control robots, etc., and is attracting a lot of attention. Here, you can get familiar with the essence of the technology using your familiar smartphone before confronting such a practical level. As an example, a robot is trained to go straight down the corridor and successfully acquire the gem placed along the way. For this purpose, I use the reinforcement learning method called Q-Learning. Results of the training can be confirmed by the animation of the robot movement. I have developed a smartphone app that realizes these using MIT App Inventor. Q-Learning runs on your palm!

# This application for Android is published below:
Source code: here

# This app can also be applied to robots with more complex behaviors than the examples below. In that case, it is enough to add a definition of new actions and rewards. For details, please see Part 2 here.

# For the case where the robot moves on the 2D grid, please see Part3 here. 

● Overview of the Q-Learning app
The configuration of the developed application is explained in Fig. 1. You can see a robot and a green gem in the corridor at the bottom. Train the robot to pick up the gem at the right place. (The robot's behavior will be explained later.) To do that, first press the "init" button, then train with the "train" button. Each "train" will learn 100 steps. One step corresponds to the robot moving one block in the corridor or picking up (taking) the gem.

At each step, the action is rewarded. Positive actions that lead to success are highly rewarded. A series of actions of the robot starting from the left end to the final success or failure is called an episode. Although the position of the gem changes with each play (game), the average rewards sum for successful episodes can be calculated theoretically in this example. Repeat "train" until it approaches this theoretical value. If the theoretical value cannot be calculated, the iteration should be stopped when it is considered to have converged to a certain high value.

The data in the large yellow area (Q-table) on the screen indicates which action is preferable (worth it) depending on the situation along the way. As I will explain later, with repeated training, this Q-table will approach the correct values.

After training, press the "anim for test" button to watch the robot's behavior in animation. A major feature of this reinforcement learning is that the behavior of the robot can be determined by the contents of the Q-table. Therefore, if the Q-table is inaccurate, it often fails as follows:

On the other hand, if the contents of the Q-table are correct, gem acquisition will always succeed, as shown below:

● Challenges imposed on robots and possible actions
Let's take this example in a little more detail. The actions that the robot can take, the conditions for obtaining the gem, and the conditions for completing the task (play) are shown in Fig. 2. On the other hand, Figure 3 illustrates whether “Take” (the action of picking the gem) or “Forward” (moving to the right) leads to success in a certain situation. To get the gem, the robot must do a "Take" action at the same place as the gem. Obviously, in this example, the robot should select (2) "Forward" instead of selecting "Take" in (1). After that, select "Take" in (3) and it will succeed.

It is easy for humans to write a program to solve this problem (challenge). But here, instead, let the robot itself discover the solution through learning. Please note this point!

● How to choose an action
As already mentioned above, I introduced rewards to determine whether to choose between “Take” action and “Forward” action in a particular situation. As shown in Figure 4, the reward is +5 for the "Take" action that succeeds in acquiring the gem, and -1 for the other actions. And it is advantageous to choose an action with a larger sum of rewards mentioned above. 

● Update Q-table
To achieve the above, I use a Q-table that represents the value (in other words, worth) of both actions for the state at that time, as shown in Figure 5. In the figure, in the untrained state (train = 0 step), the action value of "Take" is higher (larger) than that of "Forward", so the "Take" action is selected. But this is wrong because the Q-table is inaccurate. On the other hand, in the fully trained state (train = 800 steps), the Q-table has been updated to a reasonable value, and the "Forward" action is taken correctly. Roughly speaking, Q-table is an estimate of the sum of rewards. 

The Q-table update is based on a famous learning rule called Q-Learning as shown below:

This update formula means that the value of Q when taking an action in the current state is brought close to the highest value of Q that can be taken in the next state. It is known that such updates converge to the optimum Q value, assuming a sufficient number of episodes are attempted for all states. If you need a more detailed explanation, please see one of the references ([1][2][3][4][5]). And the relationship between this value of Q and the Q-table in this application is illustrated below:

In fact, the figure below shows that the contents of the Q-Table have almost reached optimal after 1100 steps of training.

● Expand the app a little
Finally, here is an example of how to expand this app. This app has three hyper parameters (α, γ, ε) to increase versatility. For example, how much will the convergence speed and stability be affected if the value of the learning rate α is changed?

To confirm this, you need to display it as a line graph instead of the slider as above. It's easy to achieve. I used ChartMaker (an extension created by Kate & Emily) in reference [7]. The result is shown in Fig.6.

Enjoy reinforcement learning (Q-Learning) with this smartphone app! 

● Even deeper expansion
The above example is to familiarize you with the basic idea of "Q-Learning". In this example, the number of states is so small that the entire contents of the Q-table could be saved and updated. However, consider an example where the robot's range of movement is not a one-dimensional corridor, but a wide plane, or there are places where it cannot proceed due to obstacles. In such cases, the number of states will be enormous and will not be solved by basic Q-Learning. Therefore, the Q-table needs to be approximated by another method. One promising method is to use neural networks. The training itself will need to be done on a PC, but it will be possible to bring the trained model to a smartphone and run the animation for testing. I would like to discuss such advanced expansions in another article.

Acknowledgments
This app is my original work. However, I refer to the explanation of Q-Learning and the example Python program in reference [6]. I would like to thank Dr. Makoto Ito, the author of this article.

References
[1] Richard S. Sutton and Andrew G. Barto, "Reinforcement Learning: An Introduction, second edition", The MIT Press, 2018.
[2] Vincent François-Lavet, Peter Henderson, Riashat Islam, Marc G. Bellemare, Joelle Pineau, "An Introduction to Deep Reinforcement Learning", Now Publishers, 2019.
[3] Etsuji Nakai, "Reinforcement Learning for Software Engineers", Gijyutsu-Hyoron-Sha, 2020. (in Japanese)
[4] Azuma Ohuchi, Masahito Yamamoto, Hidenori Kawamura, "Theory and application of multi-agent systems - computing paradigm for complex systems engineering", Corona-sha, 2002. (in Japanese)
[5] Tomah Sogabe, "Introduction to reinforcement learning algorithm", Ohmsha, 2019. (in Japanese)
[6] Makoto Ito, “Learn Reinforcement Learning with Python”, Nikkei Software 2021.07, Nikkei BP, 2021, pp.24-39 (in Japanese)
[7] Kate Manning and Emily Kager,
https://github.com/MillsCS215AppInventorProj/chartmaker

スマホアプリで「強化学習」を学ぶ魅力！

【what is this】最近の日経ソフトウェア誌に、「Pythonで強化学習を学ぶ」の解説記事がありました。丁寧に書かれていて分かりやすく、提供されているPythonプログラムも完全に動かすことができました。しかし、ここで留まらずに、理解をさらに深めるため、別のプラットフォーム（Androidスマホ）とプログラミング環境（MIT App Inventor）で、独自にそれを再構築してみました。

■ 解説記事：Pythonで「強化学習」を学ぶ
　まず、図１に示すのがこの記事です。全16ページに渡って、強化学習が非常に丁寧に解説されています。前半７ページでは、簡単な例題を使って強化学習の概念（Q-Learning）と具体的な動作が説明されています。後半９ページでは、Pythonでこれを実現する方法を説いています。コードの説明だけではなく、肝となるQ-Tableの学習則（学習率や割引率を含む）の解説が分かりやすく示されています。

　そして、何よりも嬉しいことに、提供されているPythonプログラム（４つのPythonファイルで合計約970行）が小生の環境でも問題なく、完全に動いたことです。図２はそれを示しています。

　素晴らしい！分かった気になる！でも本当にそうなのか。単にトレースしただけではないのか？という思いもあります。理解を本当に深めるのであれば、自分で、この解説の仕様に沿って、プログラムを独自に再構築するのがいいでしょう！ということで、それを実際にやってみました。

■ スマホアプリとして上記強化学習プログラムを独自に作る

　実は、小生は、上記のPythonコードの中味はほとんど読んでいません。にも拘わらず、図３に示すような、同等機能のスマホアプリを作成することができました。これは、この解説自体が素晴らしかったことに他なりません。MIT App Inventorを利用して開発しました。

■ スマホアプリの強化学習での「学習（訓練）」と「評価（実行）」

　詳細はここには書けませんが、このスマホアプリによる「学習」と「評価」を簡単に示します。まず、図４の(a)と(b)は、それぞれ、学習が不十分な場合と十分な場合に、タスクを実行した様子です。

　ここでは、ロボットの行動は、「右へ前進する」か「宝石を取る」のいずれかです。ロボットが緑色の宝石の位置と一致した時に「宝石を取る」ように学習（訓練）するわけです。図４(a)は、ロボットが宝石を得ることに失敗しています。なぜなら、学習が不十分であり、今の状況（赤枠）では、

Q-Tableの[宝石を取る行動価値, 右へ前進する行動価値] 

= [-0.71757, -1.01168]

となっており、ロボットがまだ宝石の位置にないのに、より行動価値が高い（すなわち、-0.71 > -1.01）と評価された「宝石を取る」行動を行ったためです。

　これに対して、図4(b)は、学習が十分に進んでいたため、Q-Tableの中味は正当なものになっており、ロボットは今ここで「宝石を取る」のではなく、宝石へ向かうことになります。

　そして、図５に示すように、ロボットはさらに宝石に近づき（途中の一歩の図示は省略）、位置が一致したところで、

Q-Tableの[宝石を取る行動価値, 右へ前進する行動価値] 

= [5.0, -1.9]

にしたがい、最終的に自信をもって（すなわち、5.0 > -1.9）、「宝石を取る」行動が成功しています。

　動作を確認するため、十分に学習済み（Q-Tableの内容が妥当になった）後の評価実行例を以下に示します。

■ スマホアプリで「強化学習」の意義
　Pythonプログラミング、もちろん良いでしょう。でも、スマホでアプリを開発するのならば、MIT App Inventorは非常に効率良く行えます。上記解説記事では、Q-Tableの実現に、Pythonの辞書型変数やnumpy配列を使っていますが、App Inventorでも同等のことが可能です。また、Pythonのmatplotlibほど高機能ではありませんが、図３に示したとおり、App Inventorでも折線グラフ（報酬の経緯）も描けています。

　スマホで、強化学習を実行し、その状況をグラフで可視化し、学習結果としてのQ-Tableの数値を確認し、評価のためのアニメーションも実行する。それらを、ボタン操作で、掌ですべてインタラクティブに行える。この魅力は大きなものと改めて感じます！

　例えば、図３で使用したハイパーパラメータを変えて学習させたい、という場合も、図６のように直ぐにその効果（収束速度や安定度など）をグラフで確認できます。

■ MIT App Inventorプログラムの複雑度
　上に述べたとおり、Pythonで約970行とほぼ同等のプログラムをMIT App Inventorで作成しました。それがどの程度の複雑度なのかを詳しく述べることは、ここではできませんが、プログラム全体（ブロック図）をご参考までに示します。小さくで中味は見えませんがご容赦下さい。

生徒・学生のための２つのITコンテストを応援しよう！

　すでに募集は締め切られていますが、生徒・学生のためのIT関連コンテストがありますので、ご紹介します。以下の２つは、いずれも小生が応援しているものです。

●U18 IT夢コンテスト（神奈川工科大学主催）
●MIT App Inventor Summer Appathon（米国MIT主催）

（１）U18 IT夢コンテスト（神奈川工科大学主催）

　IT（情報技術）で実現できる未来の社会や新たなサービスなどに関する「夢」を語ってもらうコンテストです。必ずしも、完成したアプリケーションの提出は必要ありません。以下のとおり、最終審査会がオンラインで開催されますので、誰でも応援できます！

●2021-08-22（土）オンライン最終審査会

https://yumecon.ic.kanagawa-it.ac.jp/

（２）MIT App Inventor Summer Appathon（米国MIT主催）
　こちらは、３つのテーマ（City of the Future, Improving Academics, Community Computational Action）に関するアイディア（説明書とビデオも必須）とそれを実現したスマホアプリの提出が必要です。提出はすでに締め切られています。現在、誰でも投票できる「People's Choice Award」を受け付けています。彼らがどんなアイディアを持ち、どうそれを実現しているかを知って、応援しましょう！（今後、審査員による賞の発表もあります。）
https://appathon.appinventor.mit.edu/

Scratchプログラミングで強化学習の基礎(3)

【what is this】前回の「Scratchで強化学習(2)」の続編です。伊藤真著[1]にある、レベル３の例題を検討します。前回のレベル２では、開始状態から最終状態までの「エピソード」を扱いましたが、今回の例題は最終状態の無いゲームでの得点（報酬）を競うものです。予測報酬（=行動価値Q）の計算において、「割引率」を導入するのがひとつのポイントです。

■ レベル３例題：お化けの飛行訓練ゲーム
　このレベル３例題は、図１に示すように、４つのボタンのいずれかを押す毎に、報酬表にある報酬（-3から3までの整数値）が得られます。負数の場合は左へ、正数の場合は右へその絶対値を歩数として進みます。100回のボタン押下において、できるだけ多くの総報酬（右方向の遠くの位置）を得ようとするものです。

　ボタンｎを押すという行動により現在の状態が状態ｎへ推移します。例えば、現在の状態（from）が状態１の時にボタン２を押すと、次の状態（to）としての状態２へ推移します。その際、報酬表（状態１, 状態２）の値（すなわち１）を報酬として得ます。報酬表の対角要素はすべて-1としてありますので、同じボタンを連続して押した場合は、いつも-1の報酬を得ます。

　報酬表の値は、ゲーム毎に変わりますが、もちろん、それらの値はプレイヤー（人間と「強化学習」）には知らされていません。

■ 「強化学習」プレイヤーの戦略
　今回の強化学習の戦略は、基本はレベル２の場合の学習則と同じです。しかし、冒頭に述べたとおり、今回は最終状態がなく、いつまでもボタン操作が続きます。状態の推移が巡回する場合もあります。（実際には、ここでは100回で打ち切りますが。）このため、得られる報酬がどんどん増大してしまい、行動価値Q(状態、行動）を従来の学習則のままで更新しようとしても収束しない恐れがあります。

　そこで、Q(状態、行動）を更新する際に、右辺のQの値に割引率γ（0.9とか0.8程度の値）を掛けて行き、遠くの報酬を少しづつ小さくします。それによって収束が期待できます。この割引率γを変更することで、遠くで得られる報酬の見積もりを（少なめに）調整することになります。あるQ(状態、行動）は、その絶対値よりも、他の（状態、行動）と比較して価値が高いかどうかが重要なので、この割引率の導入は妥当と思われます。（割引率導入の学習則の詳細は、参考文献[1]をご覧下さい。）

■行動価値Q(状態, 行動)の計算を観察する

　上記の割引率付きの学習則によるQ(状態、行動)の計算結果を観察してみます。上に述べたとおおり、Q(状態、行動) = Q(from-状態、to-状態)とみなすことができます。報酬は、図１に示した報酬表のとおりだとします。

　ボタン操作を100回で打ち切りますが、学習則にはランダム性が含まれているため、Q(from-状態、to-状態)の値は、一意には決まらず、無数に存在します。そのうちの２例を、図２aと図２bに示します。

　図2aと図2bの棒グラフの高さはまちまちのように見えますが、両者には共通の明確な特徴があります。すなわち、以下のような巡回があります。

• 状態１では、最大Qはボタン２の場合であり、状態２へ。
• 次に、状態２では、最大Qはボタン４の場合であり、状態４へ。
• さらに、状態４では、最大Qはボタン１の場合であり、状態１へ。

　結論が出ました！学習により、次のようなボタン押下が最適だ！

ボタン１→ボタン２→ボタン４→ボタン１→ . . . 

■ 感想
　これまで、書籍[1]にあるレベル１，レベル２，レベル３の例題を実際に動かしながら、自分なりの詳細観察を行ってきました。エピソード的な場合と非エピソード的な場合の両方で、Q(状態、行動)とはどんなものかを知る上で、非常に有用と感じました。

　本書は、初心者向けに分かりやすく、との方針に基づき、著者独自のやさしい用語も用いた丁寧な説明に徹しています。しかし、第７章「まとめ」では、今後、強化学習を専門書でさらに深く学ぶ場合に備えて、それらの用語と専門用語の対応についても説明があります。これだけ親切な著書はみたことがありません！ありがとうございました。

参考資料

[1] 伊藤　真：ScratchでAIを学ぼう- ゲームプログラミングで強化学習を体験、日経BP、2020年8月11日第１版

A scene with a slide rule

Sometimes I write old, nostalgic articles. The following is what happened when I went to the United States in July 2014, seven years ago, to present my paper at the MIT App Inventor Summit 2014.

Perhaps modern students have never heard or touched what is called a "slide rule", but it was widely used in the world of technical computing. For example, it was actually used in some US national projects, so it's no wonder that some traces of it remain in the United States. The picture below is the elevator entrance of a hotel near MIT (Massachusetts Institute of Technology) where I was staying. I was surprised that a huge slide rule was hung on the top of the elevator door.

A huge slide rule at the entrance of the elevator

Enlarged view

The slide rule was discontinued 40 years ago with the advent of electronic calculators, but I still hold one of them. It was probably produced over 50 years ago. The photo below shows the calculation of "2 x Pi = 6.28" using this slide rule. In addition to multiplication and division, the slide rule can also be used to calculate trigonometric functions, logarithms, square roots, cube roots, etc. by exchanging the middle pard rule.

"2 x Pi = 6.28" on my slide rule

Most of the slide rules made in Japan, including the one shown in the above figure, were made of bamboo. Therefore, there is little deterioration in accuracy due to temperature and humidity fluctuations, and it has been highly evaluated worldwide. The times have advanced. And in the new era, the physical slide rule has disappeared, but as you can see in the picture below, there is a "slide rule software" for Android smartphones! It is useful for understanding the principle of a slide rule.

"2 x Pi = 6.28" in the slide rule app

Scratchプログラミングで強化学習の基礎(2)

 【what is this】前回の「Scratchで強化学習」の続編です。伊藤真著[1]にある、レベル２の例題を検討します。前回のレベル１では、「行動、報酬」だけでしたが、今回は「状態、行動、報酬」を扱う本格的な強化学習の仕組みが入っています。そこにおいて、各状態での行動に対する予測報酬（=行動価値Q）の計算を観察します。
[->続編はこちら]

■ レベル２例題：月面でダイヤ集めゲーム
　このレベル２例題は、図１に示すように、状態１〜状態３、および最終状態を持ちます。状態１から開始して、左右のどちらかを選択して次の状態へ達します。さらにその状態からふたたび左右のどちらかを選んで最終状態に達します。そこまでを１つのエピソードと呼びます。エピソードのなかで左右を選ぶ毎に、ある確率（報酬確率）でダイヤが出ます。ダイヤが出ると報酬１を、出ないと報酬０を得ます。例えば、50回のエピソードで、できるだけダイヤをたくさん集めて報酬の総計を大きくせよ、という問題です。

　場所によって報酬確率は異なります。図１の中の赤字の数値がそれです。もちろん、それらの確率は、プレイヤーには知らされていません。最も運が良ければ、１エピソードで得られる報酬は最大で２となります。

■ 「強化学習」プレイヤーの戦略
　今回の強化学習の戦略ですが、実は、状態２か、または状態３にいる場合は、前回のレベル１での戦略と同等です。しかし、状態１（開始状態）にいる場合には、左右どちらを選択した場合も、それによって直接得られる報酬に加えて、さらにその先の行動で得られる報酬も考慮する必要があります。例えば図１の場合、状態１においては、直接の報酬については、左が0.2で右が0.3なので右側の報酬確率が高いのですが、その先で得られる報酬の合計を考えると、逆に左側を選んだ方が得になります。

　このような判断を行うために、各状態において、各行動（右選択か左選択か）に対して、行動価値、すなわちQ(状態、行動)と呼ばれる値を学習によって求めることがキーポイントになります。この学習則についての詳細は、参考文献[1]を参照して下さい。このQ(状態、行動)は、その状態においてある行動を取った場合に、最終的にどれだけの総報酬が期待できるかという、期待値を計算するものです。したがって、このQの値が正確な値に近ければ、その状態で取るべき行動の指針となります。

■Q(状態, 行動)の計算を観察する

　以下では、このQ(状態、行動)の計算がどのように進行するのかを観察します。図１の底辺部分から始めます。まず、図2aは、状態２における行動価値Qの推移（エピソードの進行にともなう）を示しています。50エピソード時点でみると、Q(状態２, 左)=0.25、Q(状態２, 右)=0.86が得られています。状態２における実際の報酬確率は、左=0.20、右=0.90ですから、Qの計算結果はかなり正解に近いと言えます。素晴らしい、使える！という気になります。

　次の図2bは、状態３に対するものですが、上記と同様に、Qの計算結果はほぼ、実際の報酬確率に近いことが分かります。

　次の図2cは、状態１に対するものです。この図では、Qの値が、報酬確率とかなり離れているように見えますが、これで良いのです。というのは、冒頭で述べたとおり、状態１でのQの計算は、直後の報酬だけでなく、その先で得られる報酬の総和の期待値になっているからです。

　結論として言えることは、以下のように行動することが最善のようです。（もちろん、ゲーム毎に報酬確率の設定が異なりますので、図１のケースにおいてです。）

　状態１→左側選択→状態２→右側選択

　ただし、もしも、エピソード10が終わった時点で判断すると、図3cからも分かるように、状態１で右側を選んでしまうでしょう。そうすると、最終的に高い総報酬報酬は得られないはずです。どのくらい（エピソード数）学習させるべきかについては、十分な注意が必要でしょう。

■ 感想
　このレベル２の例題は、Q(状態、行動)とはどんなもの？という疑問に答えてくれと思います。そして、強化学習の入り口へ案内してくれるように感じます。

　なお、上のグラフですが、Scratchのリストはテキストファイルとして簡単に取り出せますので、それをExcelに与えて描画させました。

謝辞

著者の伊藤真氏からのご指摘で、記事の途中から「エピソード」が、誤って「エポック」になっていたことに気づき、訂正しました。

参考資料

[1] 伊藤　真：ScratchでAIを学ぼう- ゲームプログラミングで強化学習を体験、日経BP、2020年8月11日第１版