BackPropagation in Neural Network with an Example (XOR) Using Multiple Micro:bits

In this article I would like to attempt Backpropagation in a neural network using micro:bit.

Back propagation in a neural network made with micro:bits

In the previous article, I used micro:bit to construct a neural network and took up the recognition of XOR using it.

http://sparse-dense.blogspot.com/2018/06/microbittwo-layer-perceptronxor.html

At that time, since we used the neural network weights completely learned about z = XOR (x, y), the value of z for any input pair (x, y) could be calculated with only one forward propagation.

As before, I use micro:bit neural network again. But at this time, the Backpropagation which is the foundation of Deep Learning is applied. In general, it takes a long time to learn in a neural network, since it requires repetition of forward propagation and backward propagation many times. So, here we use some good (but not complete) weights that we got before from another projects, as initial weight values. Starting from that, we should complete weights update within a small number of iterations, even on the micro:bit neural network. Please check the actual operation with the following video:

This video is also published on Youtube:
https://youtu.be/tsYr01lQ_HY

Weight updates to recognize XOR are required for the four cases of input (1, 1), (1, 0), (0, 1), (0, 0). Successively for all these cases, updates should be repeated until the error (difference between the answer and the evaluated value z) becomes smaller than the tolerance (here, 0.1). However, for the sake of simplicity, we only show weight updates for the first case x = 1, y = 1 in this demonstration. It converged after 5 iterations.

Please note that the neurons (micro:bit) of the Hidden layer and Output layer display eastward arrows or westward arrows depending on whether they are in Forward or in Bacward. Also, after the Backward is over, button A on micro:bit is pressed before Forward starts. This is to ensure the proper timing between receive and send on micro:bit radio.

プログラミング例題（ハミルトン閉路問題）：micro:bit版

  【what is this】マイクロビット（micro:bit）のプログラミング例題として、有向グラフのハミルトン閉路問題をやってみました。これは（NP完全問題）であり、効率的な解法は無いようです。そこで、全パス検索になるのですが、DNA（分子生物学の）を使って試験管のなかでこの問題を解いたAdelmanに習い、解の候補となる経路を事前に生成して、それをふるいにかける方式としました。この例題作成をとおして、micro:bitのプログラミングシステムが非常に優れていることを再確認しました。

（⇒本記事の続編はこちらにあります。）

■micro:bitでの有向グラフのハミルトン閉路問題
　micro:bitは最近Version2が発表され、メモリの増強（RAM 8倍化、Flash 2倍化）、タッチセンサやマイク、スピーカーの内蔵などがなされています。今回、これを記念して？ハミルトン閉路問題（始点ノードから出発して、全てのノードを１度だけ訪問し、始点へ戻る経路を探索）を解いてみます。高校生向け講座などの例題になるかも知れません。

　問題設定ですが、micro:bitには、5x5のLED表示しかありませんので、5ノードの有向グラフに限定します。図１のように、ボタンAを押してランダムに５ノード間の接続行列を作るようにします。

　次にボタンBを押すとその解を探索し、見つかった解の個数を表示します。解がなければ0個となります。さらにタッチセンサに触れると、解を電光掲示板方式で１文字づつ流して表示します。これだけですが、ちょっと楽しいプログラミングとなるはずです。

■有向グラフのハミルトン経路問題の解法
　この解法は、全パス検索になります。ただし、AdelmanのDNAを利用した（試験管のなかでの）解法を念頭におき、事前に解の候補をすべて生成します。すなわち、ノード1, 2, 3, 4の順列（4! = 24個しかありませんが）を生成し、その先頭と末尾に0を付加した経路シーケンスが、上で生成した接続行列から作れるかを検査します。出題となる接続行列の個数は約100万個（= 2の20乗）あるのですが、そのいずれに対しても24個の可能性を調べれば良いことになります。ランダムに生成した接続行列では、解が存在しない場合も多く、解があっても、数個程度以内となります。

■micro:bitプログラミング
　この解法のプログラムの主要部を図３に示します。ブロック形式、μPython、JavaScriptの3種が利用できます。ここで特筆すべきは、大まかには最初にブロック形式で作成して、細部をμPythonで作ることができることです。図ではmakePathという関数を作っているのですが、再帰的構造になり、ブロック形式で作成していると細部が考えにくい状況になりました。そこで、μPythonに切り替えて作成するとかなり楽でした。そして、その後、再度ブロック形式に戻ることができるのです！

　さらに素晴らしいと思ったのは、実機のmicro:bitでやる前に、PCでエディタやシュミレータを使えることです。それには、デバッガーやコンソールも使えるという優れた開発環境になっているのです。

■micro:bitは誰のものか？
　micro:bitは、通常、小中高生のプログラミング教育などに広く利用されています。大学ではあまり関心は高くないようです。ですが、上記の経験からも、これは大学でも、初級プログラミングにはかなり使えのではないかと思った次第です。

　micro:bit単体では、確かに作れるアプリに限界があります。しかし、他の機器やスマホとの連動機能も豊富なので、それを使うとかなり高度なアプリも楽しく作れると思います。

■小生がこれまでに作成したmicro:bitアプリもご参考に

　ちょっと手前味噌になりますが、小生がこれまでに、micro:bitと他の機器などと連携させて作成したアプリの情報は以下にあります。ご参考になれば幸いです。

1. Demonstrating Block Chain with a set of micro:bits using radio
2. BBCのmicro:bitで暗号仮想通貨の基礎を知る
3. Consturuct a neural network (multilayer perceptrons) using micro:bit
4. BackPropagation in Neural Network with an Example (XOR) Using Multiple Micro:bits
5. Cooperation between micro:bit and MIT App Inventor with Eddystone signals (No.1)
6. Cooperation between micro:bit and MIT App Inventor with Eddystone signals (No.2)
7. Cooperation between micro:bit and MIT App Inventor (No.3)

⇒本記事の続編はこちらにあります。

Consturuct a neural network (multilayer perceptrons) using micro:bit

notice:
This article treats only forward propagation, whereas, backward propagation is also demonstrated in another article. -> Please see here.

Let's learn the basics of neural networks using micro:bit. Understanding deepens by actually programming. For neural network learning to solve various tasks, back propagation is generally required. Learning with this back propagation requires considerably long time calculations. It is not realistic to do this with such a tiny microbit with low computing power, even though it is not impossible. Therefore, here we will try forward calculation only, using the edge weights of the already learned neural network. Even so, you can experience some of the important points of the neural network.

Neural network with micro:bit

　this illustrates evaluation of z = XOR(1,1) = 0

One thing to notice here is that one microbit plays a role of one neuron. By doing so, you can have an image that is close to real neurons. Here, XOR (Exclusive OR) is the problem. z = XOR (x, y) shows 1 only if either x or y is exclusively 1. Otherwise the value of z is 0. In the microbit, JavaScript and MicroPython can be used, but here we use MicroPython. The reason is that microbit JavaScript currently does not support calculation of float type data. Float type operation is mandatory for calculation of Neural network. Also, neurons (microbit) exchange signals with each other. For that we use send / receive on radio. This is not Bluetooth. Additionally, as the activation function, we use the sigmoid function.

The weights of the edge used above are the results of being learned by the following NetLogo program that is based on the following one:

• Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.       

The red line denotes a negative value, the blue line denotes a positive value, and the thickness shows the magnitude of the absolute value.

Weights used in the above example were obtained by this NetLogo  simulation

Please see the video for an actual operation example.

https://youtu.be/PPUcsXgCnZ4

In the first half, z = XOR (x, y) is calculated where x = 1, y = 1, and then the value 0.0178... was obtained, so that "0" was finally displayed. On the other hand, the second half is the case of x = 1 and y = 0. Now that 0.9852... has been obtained, "1" was displayed as the final result of z.

Ideas into Reality

　あるシンポジウムで、短い口頭発表を行う予定でしたが、新型コロナウィルスの影響でそれは中止になりました。そこで、中止発表当日に！完成したスライド16枚とその説明をここに掲載したいと思います。Web自主発表？です。（オンライン発表ではないですが。）

[末尾に、参考資料を追記しました。2020-3-10]

    AIの適用が拡大しています。そして、個人のニーズと嗜好の多様化に伴い、個人的な面でもそれは拡大しています。その背景として、AI活用の容易化、そして、AIはブラックボックス的でもあるが使える！という機運の高まりがあります。ここでの目的は、「Ideas into Realityの推進」にあります。具体的には、AIを活用した数例のアイディアを検討し、それを高レベルの開発環境で迅速にプロトタイピングできることを示します。それをさらに多様なAIアプリケーションの開発力向上に繋げて行きたいと思います。

    そのAIアプリケーション開発ですが、開発環境を概観した図がこちらです。様々な環境に包まれていますが、ここでは、緑色で示した「高レベル学習モデル作成」と「スマホアプリ開発環境」、それといくつかの従来型プログラミング言語とライブラリを使って行きます。

    これまでに、AIを活用したいくつかのアイディアを発案し、それを実装してきました。あまり難しいものはありませんが、こちらに示すようなものです。今回はそのうち、(1)ニューロンをmicro:bitで実装、(2)綺麗な風景の自動認識、の２つについてお話します。

    最初のアイディアは「Neural Networkのニューロンの動作をmicro:bit[1]を使って実感したい！」です。こちらは、手書き数字認識をDepp Learningで学習している例[2]です。ここにあるニューロンひとつづつを、１台のmicro:bitで実装したいということです。しかしながら、そのためには、この例は明らかに複雑過ぎますので、非常に簡単な例を考えます。意味のある最も単純な例としてのXORの認識[3]です。ですが、根幹となるバックプロパゲーション[4]は実装します。それが肝なのですから。ところで、なぜこのような原始的な実装をするのか？それは、そうすることで、実感を持って理解が深まること、そして、なによりも楽しい！からです。

    こちらは、７台のmicro:bitの連携でXORを学習しているところです。論理的な結線を書いてありますが、実際には結線はありません。全て無線通信でデータをやりとりしています。先ほどのバックプロパゲーションですが、この手書きの式にしたがって、Pythonで20行ほどの短いプログラムとしてmicro:bitに組み込みました。なお、micro:bitは性能が低いので、学習を加速させるため、こちらのNetLogo[5]で予め辺の重みの大まかな値（近似値）を求めておき、それを使って出発させます。

　こちらは、その動作状況のビデオの一部です。バックプロパゲーションのフェーズから示していますが、次にフォーワードプロパゲーションになると、出力Zに結果の数値が（一桁づつ）表示されます。正解と出力Zの差が一定値以下になると学習が終わったことになります。この画面では、x=1, y=1に対して、出力Z= 0を学習した状態です。

    このビデオはYouTubeで公開[6]しているのですが、それが図のとおり、micro:bitの公式Twitterで紹介されました。micro:bitは主に学校向けでありますから、通常はこのような使い方はしないのですが、これが取り上げられたということは、研究成果も教育へ還元して行こう、という姿勢の表れではないかと考えています。

    次に２番目のアイディアです。曇りがちだが、晴れると美しい山があります。しかし、いつそうなるか分かりませんので、綺麗に見える時にスマホへ自動通知する、というものです。具体的には、北海道の北部に利尻岳があります。島になっています。隣の礼文島からこれを写しているライブカメラ[7]がありますので、それを利用します。ここが海峡になっていることもあり、通常は曇っていて、unluckyな状況ですが、時々、goodな風景になります。そして希に、山全体が見えるexcellentになります。このexcellentになった時に、スマホに自動通知し、さらに先ほどのmicro:bitに大きな山のイメージを表示します。

　こちらは、作成したスマホアプリです。動かしてみます。最初は、曇っているがgoodな風景です。次に、excellentなのが出てきます。最後の画面では、confidence 0.99でexcellentと認識されています。

    この場合の画像の学習は、Google Teachable Machine2[8]で行いました。ブラウザで行えます。すなわち、excellent, good, unluckyな画像をそれぞれ30枚以上用意すると、すぐに学習を実行できます。学習が終われば、ここに新たな画像を与えると、３つのうちのどれに該当するかが判定されます。これらの操作はブラウザだけで閉じて行えます。しかし、ここでは、Androidアプリで利用するため、後で、この学習済みモデルを取り出します。

    ところで、このTeachable Machineは非常に高レベルの開発環境なのですが、それを完全なブラックボックスとせずに、システムからのフィードバック情報に基づいた調整が必要です。すなわち、学習の進行に伴う誤差の低減状況や、ラベル毎の正解率が得られますので、それを見ながら、入力画像の適合性や枚数の調整、さらに、こちらにある学習用ハイパーパラメータの調整を行うべきです。

    Androidアプリケーションとして作成するためのファイルの構成がこちらの図です。先ほどの学習済みモデルはこちらですが、具体的には３つのファイルで構成されています。それを操作するための、短い、JavaScript, HTMLを作成して、それらを、AndroidのローカルWebサーバへ配置します。それを動かすための制御プログラムは、MIT App Inventor[9]で作成しました。

    この図が、そのApp Inventorプログラムです。明解なブロック型のプログラム構造になっていることが分かります。すなわち、(1)ライブカメラから分類すべき画像を得る。(2)その画像を取得できたら認識を開始する。(3)先ほどの学習済みモデルを使って認識を実行する。(4)認識が終わると最後のブロックが呼び出されるので、そのなかで、分類結果がexcellentであればnotifyする。という流れです。

    ここ１、2年で、大学などを中心に、AIやデータサイエンスの教育研究が急速に盛んになってきました。ここに挙げたのは一部に過ぎませんが、例えば、神奈川工科大学の研究ブランディング事業でAIシステム[10]というのもあります。これらの取り組みのなかでも、今回のようなIdeas into Realityの実践は重要になっていくのではないかと思います。

    まとめです。AIを活用したいくつかのアイディアとそのスマホ等での実現についてお話しました。そのなかで、高レベルな開発環境とPythonの併用、さらに、App InventorとJavaScriptとの連携の強みを確認できました。今後の課題としては、例題に留まらない、実用レベルでのAIの活用をさらに蓄積して行く必要を感じます。一方、AIが出した結果に従うことに慣れてしまう怖さも感じます。例えば、サラリーマン川柳に、「AIに 営業スマイル 審査され」[11]というのがあります。これは、ちょっと考えさせられる句ではないでしょうか。最後に、高レベルの開発であっても、原理、動作、結果を的確に把握して行くという姿勢が重要と考えます。

Thank you for your attention

参考資料
[1] Micro:bit Educational Foundation
https://microbit.org/
https://twitter.com/microbit_edu
[2] Deep Neural Networks and Dropout
http://modelingcommons.org/browse/one_model/4445#model_tabs_browse_info
[3] 高卒でもわかる機械学習 (3) 多層パーセプトロン
http://hokuts.com/2015/12/04/ml3-mlp/
[4] 高卒でもわかる機械学習 (6) 誤差逆伝播法 その2
http://hokuts.com/2016/10/09/bp2/
[5] Artificial Neural Net - Multilayer
https://ccl.northwestern.edu/netlogo/models/ArtificialNeuralNet-Multilayer
[6] BackPropagation in Neural Network with an Example (XOR) Using Multiple Micro:bits
https://www.youtube.com/watch?v=tsYr01lQ_HY
[7] 礼文町　ライブカメラ
http://www.town.rebun.hokkaido.jp
[8] Teachable Machine2
https://teachablemachine.withgoogle.com/
[9] MIT App Inventor
http://appinventor.mit.edu/
[10] 神奈川工科大学　私立大学研究ブランディング事業
https://www.kait.jp/topics/branding/
[11] 第33回サラリーマン川柳　優秀100句
https://event.dai-ichi-life.co.jp/company/senryu/

micro:bitを使ってニューラルネットワークの基礎を学ぶ

　アルゼンチンのDr. Leandro Batlle（Sadosky Foundationという教育関係財団に所属）から、教育用に「micro:bitを使ったニューラルネット」を作り、いくつかのアプリを公開したとの知らせをいただきました。そのきっかけとなったのが、私が以前に書いたブログ記事だとのことでした。ブログ記事を書いていて良かった！という一つの事例ですので、簡単にご紹介します。

　以下のGitHubにあります。スペイン語ですので、日本語または英語に翻訳してご覧ください。
https://github.com/fundacion-sadosky/microbitML

　謝辞を日本語に訳すと以下のようです：
「この活動は、2024年にそのフレームワークの開発を促し、その名称「microbitML」は、ネイティブのBLE機能を拡張するものであり、もともと機械学習のために考案されたことに由来します。また、Fujio Yamamoto 教授の論文「MicrobitネットワークによるMLPのエミュレーションの構築」に基づいています。」

　そして、私が書いたブロブ記事は以下の２件でした。

🟢 micro:bitsで、Forward Propagation
https://sparse-dense.blogspot.com/2018/06/microbittwo-layer-perceptronxor.html

🟢 micro:bitsで、Back Propagation
https://sparse-dense.blogspot.com/2018/06/backpropagation-in-neural-network-with.html

NetLogo関連のブログ記事

ある必要に迫られて、小生がNetLogo（エージェントベーストモデリング向け）の利用に関して、これまでに書いたブログの記事をまとめてみました。

他の方にはほとんど役に立たないかも知れませんが、小生自身が再度エージェント指向モデリングをやる場合の資料的価値はありそうです。

ブログ記事は、一般的に言って、他の人に迷惑にならなければ、参考になる場合があるかも知れません。

（上図は、ここにある記事から再掲）

「このブログ（sparse-dense byFoYo）」に掲載の記事

◎卒研のレベルを高める手がかり：Multi-level Models In NetLogo 6（その２）
  http://sparse-dense.blogspot.com/2017/02/multi-level-models-in-netlogo-6_22.html
◎クリスマスプレゼントか、NetLogo 6.0リリース（日本語に恩恵）
  https://sparse-dense.blogspot.com/2016/12/netlogo-60.html
◎スマホでマルチエージェントモデリング！
  https://sparse-dense.blogspot.com/2017/07/blog-post.html
◎卒研のレベルを高める手がかり：Multi-level Models In NetLogo 6
  https://sparse-dense.blogspot.com/2017/02/multi-level-models-in-netlogo-6.html
◎Deep Learningのビジュアライゼーション
  https://sparse-dense.blogspot.com/2016/11/deep-learning_18.html
◎マルチエージェントでDeep Learningの基礎
  https://sparse-dense.blogspot.com/2016/12/deep-learning.html
◎Construct a neural network (multilayer perceptrons) using micro:bit
  https://sparse-dense.blogspot.com/2018/06/microbittwo-layer-perceptronxor.html
◎Java 8 ラムダ式の初歩（続き１）
  https://sparse-dense.blogspot.com/2017/05/java-8_81.html  
◎NetLogo
  https://sparse-dense.blogspot.com/2016/11/netlogo.html
◎マルチエージェントシステム NetLogo3D
  https://sparse-dense.blogspot.com/2017/03/netlogo3d.html
◎KAITシンポジウム2016で「現実感のある」エージェント指向モデリングを展示
  https://sparse-dense.blogspot.com/2016/12/kait2016.html

「神奈川工科大学 情報工学科 ブログ」に掲載の記事

◎NetLogoのネットワーク（社会的／電子的）
  http://blog.cs.kanagawa-it.ac.jp/2013/02/netlogo.html
◎Android端末をリモコンとして活用！
  http://blog.cs.kanagawa-it.ac.jp/2012/06/android.html
◎ホタルの季節です
  http://blog.cs.kanagawa-it.ac.jp/2015/06/blog-post_21.html
◎NetLogoの３D機能で再びサボテンを観察する
  http://blog.cs.kanagawa-it.ac.jp/2013/02/netlogod.html
◎情報学部棟（１２階建て）からの階段による避難
  http://blog.cs.kanagawa-it.ac.jp/2012/06/blog-post_16.html
◎平成27年度第1回のi-Androidの会が開催されました[5/27]
  http://blog.cs.kanagawa-it.ac.jp/2015/05/271i-android527.html
◎春休みにWebでお勉強（複雑系）
  http://blog.cs.kanagawa-it.ac.jp/2014/03/web.html
◎百円ショップで買ったサボテンにフィボナッチ数列を見る
  http://blog.cs.kanagawa-it.ac.jp/2013/01/blog-post_14.html
◎（続）NetLogoプログラミングのススメ
  http://blog.cs.kanagawa-it.ac.jp/2012/06/netlogo.html
◎NetLogoプログラミングのススメ
  http://blog.cs.kanagawa-it.ac.jp/2012/05/netlogo.html
◎多忙にも余裕を、硬派にも癒しを
  http://blog.cs.kanagawa-it.ac.jp/2012/05/blog-post_04.html
◎i-Androidの会が開催されました(12/24)
  http://blog.cs.kanagawa-it.ac.jp/2015/01/i-android1224.html
◎蝶の山越え：３年セミナーの一場面
  http://blog.cs.kanagawa-it.ac.jp/2014/01/blog-post_30.html
◎（続）６月９日オープンキャンパス研究室公開
  http://blog.cs.kanagawa-it.ac.jp/2013/06/blog-post_10.html
◎通算２０回目の情報工学科アンドロイドの会が行われました
  http://blog.cs.kanagawa-it.ac.jp/2013/06/blog-post_5.html
◎段階的に｢交通シミュレータ｣
  http://blog.cs.kanagawa-it.ac.jp/2013/05/blog-post_24.html

追記：小生による「NetLogoのチュートリアル」は以下にあります：

https://sites.google.com/site/yamlabnetlogo/home