RNNで巡回問題を解く論文を読む

AI論文 自然言語解析

ランニング30分   英語できず

(1) RNNで巡回問題を解く論文を読む

　「Pointer Network」https://arxiv.org/abs/1506.03134

　この論文は深層学習による自然言語処理でよく参照されるが、グラフィカルモデルの最適解も行えるので興味を持ち読んでみました。

　まず有名なseq2seq https://arxiv.org/abs/1409.3215は下図の様な翻訳モデルです。

　　　<A B C> → <W X Y Z>

　RNNで学習するにはencoder-decoderでRNNの重みを学習します。

　入力文字をEncodeしてその結果と出力文字で学習します。

f:id:mabonki0725:20170918195227p:plain

　同様にしてseq2seqを使うと下図の様なグラフィカルな凸被覆問題に適用することができます。

        \lt P_1,P_2,P_3,P_4 \gt  \to \lt P_1,P_2,P_4\gt

        但し

　　P_1=(x_1,y_1) \ P_2=(x_2,y_2) \  P_3=(x_3,y_3) \ P_4 = (x_4,y_4)

    モデルとしては下図の様になります。        

f:id:mabonki0725:20170918195532p:plain

　この論文のPointer Networkではseq2seqが入力項目数(頂点数）に依存するので下図の構造で解いています。

　上図の場合seq2seqは入力項目数と同じencodeの結果e_1 \sim e_4を初期値にして解いています。そのため入力の項目数(頂点）が増減すれば異なるモデルが必要となります。

　そこで入力の項目数に依存したe_1 \sim e_nを全て使わない様にPointer u_iというAttentionを計算して、次に取出す確率を求めています。

        u_i^j = v^T tanh(W_1 e_j + W_2 d_i)

        p(c_i | c_1,c_2,\dots,c_{i-1}) = softmax(u_i)

        ここで

            v  \ W_1 \  W_2は学習パラメータ

            e_jはj番目のencode

　　    d_iはi番目のdecode

　　　c_iは次に取出す座標

　下図では最初の座標(x_1,y_1)が見つかり、この結果をEncoder側に入れています。

　　　　f:id:mabonki0725:20170918200646p:plain

(1.2) 結果

　Pointer-NetworkではRNNの順序学習機能を使って以下の３つの問題を解いています。

    頂点数が50以下であれば殆ど解けています。

　　  ・凸被覆問題(a) (d)

         ・ドロネー図問題(b) (e)

　　 ・セールスマン巡回問題 (c) (f) 

　　　※セールスマン巡回問題はNP困難で近似解しか存在しない

f:id:mabonki0725:20170918201202p:plain