2021年3月14日日曜日

5本の指で0〜31を数えるジェスチャの認識:handpose利用

 【what is this】手の指のランドマーク(キーポイント)21点をリアルタイムに検出する学習モデルhandpose (MediaPipe Hands)[1]があります。そのAPIを利用して、5本の指で0〜31までを数えるジェスチャを認識するデモアプリを作成しました。

■5本の指で0〜31を数える
 2進法を使えば、5本の指で、0〜31を数えることができます。具体的には、図1のように、親指、人差指、中指、薬指、小指を折り曲げることで、各々1、2、4、8、16を与えます。通常、深層学習でこのようなパタンを認識させる場合は、この32種のそれぞれに500枚程度の画像を用意して学習させます。しかし、ここでは、そのような学習をせずに、handpose (MediaPipe Hands)から得られるランドマークを利用して簡単に認識させたい。



■handpose (MediaPipe Hands)の利用
 handposeでは、図2のとおり、5本の指の関節合計21点をリアルタイムに検出します。それを、PythonやJavaScriptからAPIで使えるようになっています。ここでは、上記の目的に沿って、21点のうち、15点を利用します。すなわち、図1にあるとおり、各指の先端、第1関節、第2関節の検出結果のみを使います。



■handpose (MediaPipe Hands)を利用した指の折れ曲りの検出で数値を決定
 各指の折れ曲がりの判定は、図1の説明にあるとおり、指の先端と第2関節の座標の差分を使って行います。ただし、親指の場合は、x座標を、その他の指はy座標に着目します。例えば、薬指の場合は、先端のy座標が第2関節のy座標よりも大きければ折れていることになります。図1の左図では、薬指と親指が折れていますので、9(=8+1)を意味します。
 この方法で指の形状を認識して、リアルタイムに2進法の数値を10進整数で表示します。実行結果のいくつかを図3に示します。なお、下部のGIF画像は、PCでの実行画面の録画から作成したものです。(折り曲げた指は"*"、伸ばした指は"_"で示しています。0〜31までを連続して示しています。)



■感想
 正面から撮影するという条件下では、このようなジェスチャ32種を、ほぼ100%認識することができました。「学習」を行わずに、短めのPythonプログラムによって比較的簡単に実現できたことに驚きます。ただし、ランドマークがリアルタイムに得られるというのは、すでにそのための深層学習が十分に実行されているからです。
 状況によっては、指の折れ状態をもっと厳格に(他の関節点も利用するなど)する必要があるかも知れません。この例以外にも、何か応用ができそうです。

参考文献
[1] MediaPipe Hands, https://google.github.io/mediapipe/solutions/hands

2021年3月10日水曜日

祝:MIT App InventorがiOSでも利用可能となった!

素晴らしい朗報が入りました!
 2016年10月にスタートしたこのこのプロジェクトですが、幾多の困難を乗り越え、約4年半の年月を費やし、ついに、MIT App InventorがiOSでも利用できるようになりました(図1)!特筆すべきは、これまでAndroid向けに開発されたソースプログラムは、全くそのままiOS用にも使えるという点です。

 「そんなに大変なの?」と思う人もいるでしょうが、AndoridとiOSという全く異なるアーキテクチャとOSを考えれば、この実現の偉大さは分かると思います。さらに、Appleの強い閉鎖性と極めて厳格な資源管理を考えれば、Apple側との交渉に膨大な時間がかかったことも想像に難くありません。
 マンパワーも膨大であり、約66,000行の新たなプログラム開発になったとのことです。当時、開発費を工面するためクラウドファウンデイングが行われており、小生も、同僚だったH.Tan先生とY.Sud先生と共に幾らかの寄付を行いました。それも懐かしいです。

 現時点では、図2のとおり、iOS用にはインタプリタ方式(Companionで接続)のリリースとなっており、コンパイル方式は2021年秋ころとなっています。また、出来たてなのでもちろん不具合もあるでしょう。それは問題ではありません。とにかく、素晴らしいスタートが切られたことをお祝いしたい!


 この記念すべき出来事を祝って、過去に大学のオープンキャンパスの高校生向け講座のためにつくられたApp InventorソースプログラムをiOSで実行させてみました。図3のとおり、完璧に動きました!この図からも分かりますが、スライダーやボタン等は、Androidとは若干異なる、iOS独特の美しいデザインが感じられます。

 なお、このApp Inventorの例題は、須藤康裕准教授が、ソーラーカーを鈴鹿サーキットで実際に走行させた時にリアルタイムに発進した位置情報を、後でトレースするものになっています。毎秒の位置情報の発信アプリも、須藤先生がAndroid用にApp Inventorで作成されたものです。


2021年2月24日水曜日

中学数学で折り紙ピラミッド

 YouTubeに「ドル札で折るピラミッド(Dollar Origami Pyramid)」なる動画(下部参照)がありました。良さそうに思い、やってみました。1ドル紙幣以外にも、数種類の長方形の紙で折ってみましたが、なかなかおしゃれな作品となります。古代エジプトピラミッドに比べると、先端がより鋭く尖っているようです。

 
 横長の紙を使うのですが、この折り方では、ピラミッドの大きさは縦方向の長さで決まります。横の長さには依存しませんが、横の長さが短すぎると底辺部が不安定になり、長すぎると底辺部を折り込む際に邪魔になります。動画にあるとおり、ドル札の縦横比がちょうどいいようです。

 このピラミッドは、2等辺のなす角度がいつも45度の三角形で構成されます。すなわち、どんな長方形の紙でも、その三角形は相似になります。中学数学(もしかすると小学校算数)の世界のようです。簡単だけど美しい。机上において眺めると、ちょっと心が落ち着くような気がします。


参考資料:Dollar Origami Pyramid
https://www.youtube.com/watch?v=dfnuhYNQEn0

2021年2月22日月曜日

私は誰でしょう

今回はクイズです。

 ある入力データに対する出力結果が図1に示してあります。入力データは、「千山万水」の四字熟語から、ランダムに漢字を選んで次々と並べた、長さ12の文字列です。このような入力データは、約1,700万個(4の12乗個)作れますが、図1にはその一部を示しています。それに対する「ある処理」を行った結果の出力データが右側に示されています。

 私は、このようなどの入力データに対しても、(恐らく)100%正しく出力結果を示すことができます。私は、図2のようなヒント(赤字の情報)は一切もらっていません。入力と出力の組みを5万個見て、「その処理」をひたすら学習しただけです。その結果、その処理内容を把握できたことを確信しました!

 さて、私は誰でしょうか。人間ではありませんが。
答えは、こちらの記事にあります。
(入力データのボキャビュラリが、「A,T,G,C」から「千,山,万,水」に変わっただけなのですが、Attention付きSeq2seqの感動が尾を引いていましたので、こんなクイズ記事になっています。)

2021年2月12日金曜日

新型M1 Mac miniに期待

【what is this】これまでのIntelプロセッサに替わり、Apple独自のM1(arm64)プロセッサ搭載のMacが発売になっています。Appleシリコン搭載とも呼ばれています。何といっても、「8コアCPU+ 8コアGPU+16コアNeural Engine」と言われると、長年のMacファンとして買わざるを得ませんでした。基本的なソフトウェアのネイティブ本格対応はこれからのようですが、現時点でも、手元の例題で、Intel版に対して、Javaアプリで3.2倍、Pythonアプリで2.5倍高速となりました。今後の、M1向けTensorflow(アルファ版はすでに公開)などが楽しみです。

雑然とした「研究室」に置かれた新型M1 Mac mini
(別のMacからリモートで利用のためモニターに接続されていません)

■Javaアプリで試す
 小生の使う開発言語は、Java、Python、NetLogo、MIT App Inventorなどです。まず、Javaのアプリで確認します。Androidアプリで扱ったHamilton閉路問題のうち、サイズを少し大きくした、Groetzschグラフ(11ノード)を例題とします。最も原始的な解法なのですが、10ノード(出発は第0番ノードに固定するので)の順列(約360万個)を全て調べるものです。もちろん、可能な限り早期に適合しないパスは棄却します。図1に示すような、Hamilton閉路20個を全て答えます。



 このJavaプログラムの主要部(というよりも全体制御部)は、図2のとおりです。並列ストリームを使っています。実行の結果、M1 MacはIntel Macよりも、約3.2倍高速でした。素晴らしい!PC買い換えで3倍超の性能アップは、なかなかないです。



■Pythonアプリで試す
 次にPythonアプリです。例題としては、すでに報告しました、ショットガン法によるDNAの復元問題(トイプログラム)です。Deep Learningでのprediction部分です。ここでは、上記Javaのようなparallel機能は特に意識せず、GPUの使用もありません。ですが、CPUのコア数の違いが、図3のとおり、実行性能に現れています。この例でも、M1 MacはIntel Macよりも2.5倍高速でした。


 このグラフ、緑はユーザプロセス、赤はシステムプロセスのはずです。M1 Macでは、8コアの利用率が、計算時に100%近くに達しています。それは良いのですが、システムの割合が大きいことがちょと気になります。Interl MacはPython3.8で、M1 Macは(最適化された)Python3.9です。もしかすると、ユーザプログラムの実行時にPython3.9のある部分がシステムプロセス扱いになっているのかも知れない。

■今後の期待:M1用に最適化されたTensorflow等
 以上、現時点で試せるJavaとPythonの例題をM1 Mac miniで実行してみました。従来よりも2.5倍〜3.2倍の高速化となったことは素晴らしいと思います。現時点ですでに、GPUやNeural Engineを駆使するであろうTensorflowのアルファ版は公開されています。今後、それも利用していけば、Deep Learningを手元のマシンで実現できる場面が広がりそうです。



2021年2月6日土曜日

春の息吹

 立春を過ぎたとはいえ、まだ2月6日です。寒い日が続くなか、時には少し暖かな日もあります。散歩で、早くも春の息吹を見つけました。以下の写真はいずれも、厚木市郊外で2021--02-6に撮影しました。

梅のつぼみ、すでに開花したものも

やなぎの木も芽吹いてきた


2021年2月5日金曜日

Enjoy finding out Hamiltonian Cycles

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

 Abstract 

This app solves the Hamiltonian cycle problem for a given graph. The problem is to find out paths in a directed graph of n vertices, starting from one starting point, visiting all vertices only once, and returning to the starting point. This is known as an NP-complete problem and no efficient solution is known in general. From the perspective of programming education, I provide a solution for small graphs with six or fewer vertices, along with an easy-to-use user interface. 

Basically, it searches all possible paths, but the method is not so trivial and you need to think carefully about the procedure. The use of multiple lists and recursive functions in implementing the algorithm is useful for improving programming capabilities. You should also consider the graphical user interface for setting up and displaying graphs. The sense of accomplishment gained by completing this app enhances the educational effect. It's also fun to run the finished app and see the results on the graph. 

This time, I used MIT App Inventor to create this app. The use of App Inventor's familiar feature blocks (especially Lists, AnyComponent, Canvas, Checkboxes, etc.) was very useful for efficient program development. 

●This app is published on the Google Play Store:
https://play.google.com/store/apps/details?id=appinventor.ai_Fujio_YAMAMOTO.HamiltonianCycles1

●The source code of this app is published below :
https://gallery.appinventor.mit.edu/?galleryid=3048beec-25b8-46ba-a746-25c0dc3702b6

Directed graphs and the Hamiltonian cycle

Figure 1 shows an example of a directed graph and the Hamiltonian cycle. A single matrix can be used to represent the connections between nodes. In this matrix, the "From" node is in the row and the "To" node is in the column. In the example, there are two Hamiltonian cycles. This app provides both a way to give a directed graph with such a matrix and a way to automatically generate a random graph. 


How to use the app for the Hamiltonian cycle problem

Fig.2 shows the GUI of the app developed this time. The number of nodes can be specified in the range of 2 to 6. If you want to specify a directed graph in the matrix on the left, check the check box "prefer Matrix". After that, when you press the button "genGraph", a graph with an arrow will be drawn on the canvas at the top. Next, if you press the button "solve", the Hamiltonian cycle will be searched, and as a result, the number of cycles and the path of each cycle will be displayed. On the other hand, if you want to generate a graph randomly instead of specifying the graph yourself, uncheck the check box "prefer Matrix". Even then, the matrix corresponding to the generated graph is automatically displayed. It would be fun to discover such a cycle for different graphs.


Acknowledgments

In this app, I referred to the following documents when generating permutations:
Asao Kasai, "Introduction to algorithms in Java”, chapter 4, Gijyutsu-Hyouron-sha, July 2001.(in Japanese)

2021年2月3日水曜日

プログラミング例題(ハミルトン閉路問題):Android版+RNN学習

   【what is this】小規模(5ノード)の有向ハミルトン閉路問題を、前回はマイクロビット(micro:bit)単体で解きました。今回は、それをAndroidスマホで実現しました。MIT App Inventorを用いて、チェックボックスによる接続指定や矢印付きグラフの描画も含めて見やくしました。さらに、Deep Learning(RNN(LSTM))を用いて、グラフとそのハミルトン閉路の個数の対を、多数学習させる実験も行いました。

■MIT App Inventorを用いたハミルトン閉路解法アプリ
 micro:bit単体では、出力表示が5x5のLEDに限られますが、Androidスマホを使えば、入出力とも、大幅に改善できます。また、この解法は全パス検索となるのですが、具体的なその方法は(順列生成を含めて)、それほど自明ではありません。ですから、スマホでこの解法アプリを設計製作することは、高校〜大学初級におけるプログラミング題材の候補になるはずです。小生のアイディアを以下にご紹介します。
 例えば、以下のような4ノードの有向ハミルトン経路を調べるとします。(目視ですぐに分かるのですが)


 図1(a)のようにして、このアプリで解くことができます。4x4のチェックボックスにチェックを入れることで、ノード間の有向接続を指定します。ボタン"genGraph"によって、それを矢印付きのグラフで表示します。そして、ボタン"solve"を押すと、解が得られます。この例では、解は存在しませんでしたが。

 では次に、ノード数を6に設定して、別のグラフでやってみます。図1(b)の通りです。この例では解は2つ見つかりました。そのうちの一つについては、グラフ上に赤い矢印を付してその経路を明示しています。



■ディープラーニングでハミルトン閉路の個数を学習させる
 次にやってみたのは、「ディープラーニングでハミルトン閉路の個数を発見させる」試みです。5ノードの場合でも、それから作られる有向グラフは、約100万個になります。そのうちの、20万個をランダムに選択します。その各グラフ(接続情報)に対して、上記のような方法で求めたハミルトン閉路の個数をラベルとして付与し、学習させました。図2がその場合の学習データです。

 この学習データをある構造のRNN(LSTM)で学習させた結果を図3に示します。20万件のうち、18万件を学習(訓練)データに、2万件をテストデータとした場合の、テストデータの正解率は、50エポックで99.75%に達しました!
 すなわち、「5ノードのどんな有向グラフを与えても99.7%程度の確率でハミルトン閉路の個数を正答する」ように学習できた、と言えるでしょう。

(注)この学習は、スマホではなく、PCで行いました。


2021年1月28日木曜日

プログラミング例題(ハミルトン閉路問題):micro:bit版

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

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

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

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



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


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

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

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


■micro:bitは誰のものか?
 micro:bitは、通常、小中高生のプログラミング教育などに広く利用されています。大学ではあまり関心は高くないようです。ですが、上記の経験からも、これは大学でも、初級プログラミングにはかなり使えのではないかと思った次第です。
 micro:bit単体では、確かに作れるアプリに限界があります。しかし、他の機器やスマホとの連動機能も豊富なので、それを使うとかなり高度なアプリも楽しく作れると思います。

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

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

2021年1月24日日曜日

DNA鎖を再帰的ニューラルネットワークSeq2seqの学習データに(2)

 【what is this】リカレント(再帰的)ニューラルネットワークの一種であるSeq2seqを理解する際に必要となるデータセットの準備です。前回に引き続き、分子生物学のDNA鎖を入力データとして利用しました。前回のものよりも学習が難しいと思われたデータ(ゲノムショットガン法の考え方に基づく)を採用したのですが、難なく学習を完了することができました。

■Attention付きSeq2seqへの学習データ
 今回用意した学習データをFig.1に示します。使用文字は、塩基を表す4文字(A, T, G, C)です。入力データは12文字から成ります。これに対して、「ある変換規則」でラベル(9〜12文字)を生成しています。全部で60,000件あります。これを使った学習が完全に終われば、この「変換規則」を見い出したことになります。


■Attention付きSeq2seqでの学習の結果
 結論から言いますと、Fig.2のとおり、なんなく学習が完了しました。すなわち、入力60,000件のうち9割を訓練用に、1割をテスト用にした場合、エポック8で正解率100%に達しました。実際に、学習後には、60,000件のデータ全てに対して正解のラベルが得られました。改めて、Attention付きAeq2seqの性能を堪能できました。



■入力データからラベルへの変換規則
 ここで、上に述べた入力データをラベルに対応させる「ある変換規則」を示します。Fig.3にあるとおりですが、ゲノムショットガン法と呼ばれる方法の一部を利用しています。すなわち、まず、入力データを2等分し、左側の末尾と右側の先頭で連続した共通部(最大3文字まで)を見つけ、それを「のりしろ」として、両者を再結合させたものがラベルとなります。

 ただし、入力データを全くランダムに作成するのではなく、4つのパターン(a)(b)(c)(d)がほぼ均等に出現するように、入力データの生成を工夫しています。