プログラミング例題（ハミルトン閉路問題）：Android版+RNN学習

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

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

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

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

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

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

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

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の可能性を知ることができました。