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で行いました。