プログラミング例題（ハミルトン閉路問題）：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)

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

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

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

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

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

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

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

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

【what is this】リカレント（再帰的）ニューラルネットワークの一種であるSeq2seqは、ある時系列データを別の時系列データへ変換します。その理解のために、分子生物学に出てくるDNA鎖を入力データとして利用しました。長さ６の２つのDNAの連接とそれに必要な相補配列を5万セット学習させた結果、必要な相補配列を100%予測できるようになりました。

■Attention付きSeq2seqへの学習データ
　このタイプのリカレントニューラルネットワークについては、別の記事で簡単に書きました。その際は、英文→和文、あるいは、和文→英文を言語コーパスとして与えて学習させ、機械翻訳を行いました。今回は別の種類のコーパスとして、DNA鎖をとりあげます。と言っても、ここでは、それを塩基（A, T, G, C）の文字列として扱うに過ぎません。

　図１に示すような学習データを用意しました。各行は、12文字からなる入力データ（DNA）と、それに対して「ある規則」で生成したラベル（相補配列）６文字で構成されています。使われる文字は、４つ（A, T, G, C）だけです。この場合、入力データは約1,700万個（4の12乗）作れますが、ここでは、そのうちからランダムに5万個（5万行）を選択しました。

■DNA鎖と対応相補配列の学習
　このデータを、前回と同様に、Attention付きSeq2seqで学習させます。5万件のうち、訓練には45,000件を、テスト用には5,000件を使いました。学習状況は図２のとおりです。６epochsで、テスト用5,000行に対して全て正解（正解率100%）となりました。実際、全データ5万件に対して全て正解でした。

■入力データとラベルの対応規則
　入力データからラベルを生成する「ある規則」とは図３(a)に示したとおりです。それには、ワトソン･クリック相補性が使われています。すなわち、入力データを（T→A, A→T, G→C, C→G）に従って置換したものをラベルとしました。ただし、置換する部分は、入力の中央の６文字に対してだけであることにご注意下さい。ということは、入力のうち左端と右端のそれぞれ連続３文字はラベルに影響を与えていません。一方、図３(b)は、置換開始位置を左へ１文字ずらした場合です。

（補足）入力データは12文字になっていますが、本当は長さ６の２つのDNAが、ラベルのDNA（相補配列）によって連接していること（ハイブリダイゼーション）を想定しています。

■学習済みモデルの可視化
　上記のとおり、学習済みモデルが入力データに対して100%の正解率を出したということは、図１のデータにある「入力データ→ラベル」の対応規則を発見できたことを意味します。それを裏付けるデータが図４(a)にあります。横軸は入力データ（TCATGCTTATAA）、縦軸は正解である予測結果（ACGAAT）です。マス目の色の明るさは、入力文字が縦軸（予測結果）の文字へ反応している強さを示しています。この図から、以下のことが自動的に認識されたと言えます。

(a) 入力データの中央６文字に対して、置換（T⇔A, G⇔C）を行うと正解文字列（ラベル）が得られること。
(b) 入力データのうち、先頭と末尾の連続３文字は、予測に影響を与えていないこと。

    以下の図４(b)は、図3(b)のような入力データとラベルを学習させた場合です。ハイブリダイゼーションの位置が左に１文字ずれた影響が確認できます。

　今回の学習データを使った検討によって、改めて、Attention付きSeq2seqの可能性を知ることができました。

Awesome Dancing with AI Tutorial

 【what is this】MIT App Inventorの人工知能チュートリアル第７弾として、PoseNetを利用した身体動作（ダンス）の検出アプリ[1]が公開されました。骨格17節点の座標をリアルタイムに得られるブロックが新設されたため、スポーツ解析やジェスチャ応用などのスマホアプリを作りやすくなります。

■PoseNet Extension for MIT App Inventor
　身体動作を検出するAIソフトとして、OpenPoseやPoseNetが利用されています。しかし、スマホのアプリの一部にそれを取り込みには、ちょっと敷居が高いと思います。そこで、今回のMIT App Inventor用のPoseNet Extensionの登場です。図１に示すとおり、身体骨格の節点17点の座標をリアルタイムに得ることができる機能（ブロック）が提供されました。

■PoseNet Extension を利用した人工知能チュートリアル
　MIT App Inventorでは、主に高校生向けに、人工知能チュートリアルを提供しています。今回はその第７弾として、このPoseNetを利用した図２に示すような４種類のダンスの検出アプリが公開されました。

　AIチュートリアルですから、最初からソースプログラム（ブロック）は示されていません。順を追って説明とヒントが与えられるので、各自が考えながら、プログラムを作って行きます。例えば、図３には、4種類のダンスの検出ブロックがあるのですが、その中味は示されていません。赤字の部分を自分で考えながら（各節点の上下関係や節点を結んだ線分どおしの平行性や角度などを考慮して）作り上げて行くのです。自分の動きを撮影して、自分がどれだけうまくダンスができたかを判定する部分も作ります。

■映像の中の動作も検出してみる
　このアプリを完成させても、（誰かに撮影してもらえる場合は良いのですが）自分自身でダンス動作を確認することはちょっと難しいです。また、撮影する際の背景にもかなり影響を受けるようです。そこで、手軽にアプリをテストするために、図４にあるように、Youtubeにあるテレビ体操を写してみました。ここでは、肩が水平になっているか否かも検出してみました。うまく行っているようです。画面の上側（骨格画像）と下側（実映像）にはタイムラグがあり、若干ずれて表示されます。図５は、水平検出コードです。

■今後の活用
　PoseNetが、スマホアプリのなかで手軽に使えそうです。動作検出AIの学習済みモデルが、このextensionに含まれているため、実行時にネットワークへ接続する必要はありません。身体動作をインタフェースとするいろいろな応用が考えられるように思います。

【補足】

　今回と同様の身体動作を利用したソフトウェアの例として、過去にScratchプログラミングをとりあげました。こちらもご参考にしていただければ幸いです。

【参考資料】
[1] Artificial Intelligence with MIT App Inventor
http://appinventor.mit.edu/explore/ai-with-mit-app-inventor

Attention機構を備えたニューラル機械翻訳の小実験

【what is this】ニューラル機械翻訳、特にAttention付きの機能を学びたいと考え実験しています。これまでの日英翻訳に加え、今回は英日翻訳をやってみました。日英でも英日でも、全く同じプログラムで翻訳ができてしまうことに感動を覚えます。これが、Attention付きseq2seq（シーケンスtoシーケンス）の威力だと実感できました。

■どんな機械翻訳プログラムなのか
　詳細は省きますが、斉藤康毅氏の著作[1]にあるPythonプログラムを元にしました。Attention機構を有するニューラルネットワークRNN(LSTM)が使われています。この書籍の特徴は、「ゼロから作る」というだけあって、良く使われているTensorFlowやKerasは使わずに組み立てられていることです。そのため、詳細部までよく把握できます。実際、小生も、必要な部分をカスタマイズして使っています。これは非常にありがたく、著者の斉藤氏に感謝したいと思います。

■英文和訳の機械翻訳実験の準備
　上記書籍では、いくつかのシーケンスtoシーケンス変換例は説明されていますが、機械翻訳の例題は載っていません。そこで、英日翻訳のための対訳コーパスを独自に作成することから始めました。
　図１はそのための英文生成法を、図２にはそれに対応する和文生成法をそれぞれバッカス記法風に示しています。簡単なものですが、これから、英和対訳例文を36,288件自動生成することができます。ここで扱えるボキャブラリは、図１からわかるとおり、僅かなものに過ぎません。ただ、このseq2seqでは、英単語としてではなく、出現する英字（および日本語文字）１文字の種類をボキャブラリとして扱っています。その意味でのボキャブラリは、約100個（日英それぞれ）になります。

　この図１と図２から生成される英和対訳文の例を図３に示します。以下のような対訳文を学習させるわけです。

■英和対訳文を学習させる
　では、この対訳コーパスを上に説明した翻訳プログラムで学習させます。入力は、全部で36,288件ですが、そのうち９割を訓練に、残り１割をテスト用として学習させた状況を図４に示します。思いのほか収束が速く（乱数系列により変わりますが）、ある実行では、43 epochsで学習時ロス= 0.00、テストデータに対する正解率 = 100%に達しました。

　この結果、図１から生成される英文36,228件全てに対して、正解の和文を与える英日翻訳器が完成したことになります！（実際に、全件正解を確認しました。）

■Attention機構の可視化によって学習内容を確認できる
　このような結果を与えたAttention機構の役割を図５で確認してみます。この図は訳文（縦軸：和文）を生成する際に、入力文（横軸：英文）のどこに着目しているかを示していると考えられます。この翻訳器には、上で作成した対訳コーパスを入力として与えているだけであり、「Taro - 太郎」、「One morning in December - １２月の午前」等の対応を明示的には与えていません。それにも拘わらず、この図は、そのような対応を学習できていることを示しています。

■翻訳機能の柔軟性も確認できる
　最後に、この学習済みの翻訳モデルに対して、与える入力を少し揺らしてみます。例えば、図６の[1a]の英文のうち、「December」と「leaving」の綴りを間違えたものが[1b]の英文です。これを翻訳させたところ、[1a]に対する和文と同一の和文が得られました。すなわち、かなり似た単語（文字列）であれば、妥当な翻訳結果に落ち着くようです。ただし、一般には、学習していない単語（綴り）に遭遇した場合は、当然ながら悲惨な結果となるでしょう。

　もうひとつ、別の例を示します。[2a]の「road」を「river」に変えたものが[2b]です。これらに対する和訳文をみると、「銀行」が「土手」に変わっています！これはどうしてなのか？おわかりですね。それは、図１と図２からも分かりますが、bankという単語と共にroad、riverが出てきた場合は、それぞれ異なる和文が作られるようにしてあります。すなわち、bankは、状況により「銀行」か「土手」になります。それをコーパスから学習した結果なのです。

■まとめ
　前回の和文英訳と今回の英文和訳のどちらに対しても、機械翻訳プログラムは同一です。この機械翻訳では、入力文の構文解析らしきことは何もやっていません。入力文に出現する文字列の区切り（単語）の認識と文字の種類の辞書登録の操作くらいしかやっていません。それでも、これだけの翻訳を可能にする、Attentionとseq2seqには驚嘆します。さらに調査検討したいという気にさせます。

参考文献：
[1] 斉藤康毅：ゼロから作るDeep Learning② 自然言語処理編、オライリー、2018年7月