YouTubeに「ドル札で折るピラミッド(Dollar Origami Pyramid)」なる動画(下部参照)がありました。良さそうに思い、やってみました。1ドル紙幣以外にも、数種類の長方形の紙で折ってみましたが、なかなかおしゃれな作品となります。古代エジプトピラミッドに比べると、先端がより鋭く尖っているようです。
I am a professor emeritus of CS at Kanagawa Institute of Technology, Japan. Originally my specialty was parallel and distributed systems. My current interests include machine learning, natural language processing, creating mobile apps with MIT App Inventor, and quantum computing. In the web version of this blog, clicking the icon on the right (a plastic sphere) will take you to the "List of Quantum Computing Articles". - Fujio Yamamoto (for e-mail, add "@ieee.org" after "yamamotof")
2021年2月24日水曜日
中学数学で折り紙ピラミッド
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(アルファ版はすでに公開)などが楽しみです。
■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用に最適化されたTensorflow等
以上、現時点で試せるJavaとPythonの例題をM1 Mac miniで実行してみました。従来よりも2.5倍〜3.2倍の高速化となったことは素晴らしいと思います。現時点ですでに、GPUやNeural Engineを駆使するであろうTensorflowのアルファ版は公開されています。今後、それも利用していけば、Deep Learningを手元のマシンで実現できる場面が広がりそうです。
2021年2月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.
In this app, I referred to the following documents when generating permutations:
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ノードの有向ハミルトン経路を調べるとします。(目視ですぐに分かるのですが)
では次に、ノード数を6に設定して、別のグラフでやってみます。図1(b)の通りです。この例では解は2つ見つかりました。そのうちの一つについては、グラフ上に赤い矢印を付してその経路を明示しています。
■ディープラーニングでハミルトン閉路の個数を学習させる
次にやってみたのは、「ディープラーニングでハミルトン閉路の個数を発見させる」試みです。5ノードの場合でも、それから作られる有向グラフは、約100万個になります。そのうちの、20万個をランダムに選択します。その各グラフ(接続情報)に対して、上記のような方法で求めたハミルトン閉路の個数をラベルとして付与し、学習させました。図2がその場合の学習データです。
この学習データをある構造のRNN(LSTM)で学習させた結果を図3に示します。20万件のうち、18万件を学習(訓練)データに、2万件をテストデータとした場合の、テストデータの正解率は、50エポックで99.75%に達しました!
すなわち、「5ノードのどんな有向グラフを与えても99.7%程度の確率でハミルトン閉路の個数を正答する」ように学習できた、と言えるでしょう。
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個の可能性を調べれば良いことになります。ランダムに生成した接続行列では、解が存在しない場合も多く、解があっても、数個程度以内となります。
この解法のプログラムの主要部を図3に示します。ブロック形式、μPython、JavaScriptの3種が利用できます。ここで特筆すべきは、大まかには最初にブロック形式で作成して、細部をμPythonで作ることができることです。図ではmakePathという関数を作っているのですが、再帰的構造になり、ブロック形式で作成していると細部が考えにくい状況になりました。そこで、μPythonに切り替えて作成するとかなり楽でした。そして、その後、再度ブロック形式に戻ることができるのです!
さらに素晴らしいと思ったのは、実機のmicro:bitでやる前に、PCでエディタやシュミレータを使えることです。それには、デバッガーやコンソールも使えるという優れた開発環境になっているのです。
micro:bitは、通常、小中高生のプログラミング教育などに広く利用されています。大学ではあまり関心は高くないようです。ですが、上記の経験からも、これは大学でも、初級プログラミングにはかなり使えのではないかと思った次第です。
- Demonstrating Block Chain with a set of micro:bits using radio
- BBCのmicro:bitで暗号仮想通貨の基礎を知る
- Consturuct a neural network (multilayer perceptrons) using micro:bit
- BackPropagation in Neural Network with an Example (XOR) Using Multiple Micro:bits
- Cooperation between micro:bit and MIT App Inventor with Eddystone signals (No.1)
- Cooperation between micro:bit and MIT App Inventor with Eddystone signals (No.2)
- Cooperation between micro:bit and MIT App Inventor (No.3)
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)がほぼ均等に出現するように、入力データの生成を工夫しています。
2021年1月20日水曜日
DNA鎖を再帰的ニューラルネットワークSeq2seqの学習データに(1)
【what is this】リカレント(再帰的)ニューラルネットワークの一種であるSeq2seqは、ある時系列データを別の時系列データへ変換します。その理解のために、分子生物学に出てくるDNA鎖を入力データとして利用しました。長さ6の2つのDNAの連接とそれに必要な相補配列を5万セット学習させた結果、必要な相補配列を100%予測できるようになりました。
■Attention付きSeq2seqへの学習データ
このタイプのリカレントニューラルネットワークについては、別の記事で簡単に書きました。その際は、英文→和文、あるいは、和文→英文を言語コーパスとして与えて学習させ、機械翻訳を行いました。今回は別の種類のコーパスとして、DNA鎖をとりあげます。と言っても、ここでは、それを塩基(A, T, G, C)の文字列として扱うに過ぎません。
図1に示すような学習データを用意しました。各行は、12文字からなる入力データ(DNA)と、それに対して「ある規則」で生成したラベル(相補配列)6文字で構成されています。使われる文字は、4つ(A, T, G, C)だけです。この場合、入力データは約1,700万個(4の12乗)作れますが、ここでは、そのうちからランダムに5万個(5万行)を選択しました。
このデータを、前回と同様に、Attention付きSeq2seqで学習させます。5万件のうち、訓練には45,000件を、テスト用には5,000件を使いました。学習状況は図2のとおりです。6epochsで、テスト用5,000行に対して全て正解(正解率100%)となりました。実際、全データ5万件に対して全て正解でした。
■入力データとラベルの対応規則
入力データからラベルを生成する「ある規則」とは図3(a)に示したとおりです。それには、ワトソン・クリック相補性が使われています。すなわち、入力データを(T→A, A→T, G→C, C→G)に従って置換したものをラベルとしました。ただし、置換する部分は、入力の中央の6文字に対してだけであることにご注意下さい。ということは、入力のうち左端と右端のそれぞれ連続3文字はラベルに影響を与えていません。一方、図3(b)は、置換開始位置を左へ1文字ずらした場合です。
■学習済みモデルの可視化
上記のとおり、学習済みモデルが入力データに対して100%の正解率を出したということは、図1のデータにある「入力データ→ラベル」の対応規則を発見できたことを意味します。それを裏付けるデータが図4(a)にあります。横軸は入力データ(TCATGCTTATAA)、縦軸は正解である予測結果(ACGAAT)です。マス目の色の明るさは、入力文字が縦軸(予測結果)の文字へ反応している強さを示しています。この図から、以下のことが自動的に認識されたと言えます。
(a) 入力データの中央6文字に対して、置換(T⇔A, G⇔C)を行うと正解文字列(ラベル)が得られること。
(b) 入力データのうち、先頭と末尾の連続3文字は、予測に影響を与えていないこと。
2021年1月14日木曜日
Awesome Dancing with AI Tutorial
【what is this】MIT App Inventorの人工知能チュートリアル第7弾として、PoseNetを利用した身体動作(ダンス)の検出アプリ[1]が公開されました。骨格17節点の座標をリアルタイムに得られるブロックが新設されたため、スポーツ解析やジェスチャ応用などのスマホアプリを作りやすくなります。
■PoseNet Extension for MIT App Inventor
身体動作を検出するAIソフトとして、OpenPoseやPoseNetが利用されています。しかし、スマホのアプリの一部にそれを取り込みには、ちょっと敷居が高いと思います。そこで、今回のMIT App Inventor用のPoseNet Extensionの登場です。図1に示すとおり、身体骨格の節点17点の座標をリアルタイムに得ることができる機能(ブロック)が提供されました。
■PoseNet Extension を利用した人工知能チュートリアル
MIT App Inventorでは、主に高校生向けに、人工知能チュートリアルを提供しています。今回はその第7弾として、このPoseNetを利用した図2に示すような4種類のダンスの検出アプリが公開されました。
AIチュートリアルですから、最初からソースプログラム(ブロック)は示されていません。順を追って説明とヒントが与えられるので、各自が考えながら、プログラムを作って行きます。例えば、図3には、4種類のダンスの検出ブロックがあるのですが、その中味は示されていません。赤字の部分を自分で考えながら(各節点の上下関係や節点を結んだ線分どおしの平行性や角度などを考慮して)作り上げて行くのです。自分の動きを撮影して、自分がどれだけうまくダンスができたかを判定する部分も作ります。
■映像の中の動作も検出してみる
このアプリを完成させても、(誰かに撮影してもらえる場合は良いのですが)自分自身でダンス動作を確認することはちょっと難しいです。また、撮影する際の背景にもかなり影響を受けるようです。そこで、手軽にアプリをテストするために、図4にあるように、Youtubeにあるテレビ体操を写してみました。ここでは、肩が水平になっているか否かも検出してみました。うまく行っているようです。画面の上側(骨格画像)と下側(実映像)にはタイムラグがあり、若干ずれて表示されます。図5は、水平検出コードです。
PoseNetが、スマホアプリのなかで手軽に使えそうです。動作検出AIの学習済みモデルが、このextensionに含まれているため、実行時にネットワークへ接続する必要はありません。身体動作をインタフェースとするいろいろな応用が考えられるように思います。
【参考資料】
[1] Artificial Intelligence with MIT App Inventor
http://appinventor.mit.edu/explore/ai-with-mit-app-inventor

































