目次。
- 目次。
- はじめに。
- Diffusion-Convolutional Neural Networks
- Quantum Walk Neural Networks for Graph-Structured Data
- Quantum walk neural networks with feature dependent coins
- Non-Markovianity is not a resource for quantum spatial search on a star graph subject to generalized percolation
- Time evolution of continuous-time quantum walks on dynamical percolation graphs
この文章を読んで、面白い！役に立った！...と思った分だけ、投げ銭していただけると嬉しいです。
【宣伝】ギターも歌も下手だけど、弾き語りをやっているので、よければ聴いてください。
はじめに。
==========
ちょくちょく宣伝しているが、新型コロナウイルスの論文を使って、「研究者がどうやって未知のウイルスの正体を暴くのか？」について説明した文章を一般の人向けに書いたので興味のある方はどうぞ。
blog.sun-ek2.com
加えて、PCR検査の仕組みと、それに代わるかもしれないゲノム編集技術を応用した新しい検査方法に関する論文を一般向けに説明したので興味のある方はどうぞ。
blog.sun-ek2.com
==========
「論文版はてなブックマークとは何ぞや？」という話は、以前したので、以下の文章を参照のこと。
blog.sun-ek2.com
機械学習に片足を突っ込んだ。
前回の話はこちらから。
blog.sun-ek2.com
Diffusion-Convolutional Neural Networks
著者・雑誌名。
James Atwood, Don Towsley
arXiv, July 2016
内容。
日本語にしたら「拡散型の畳み込みニューラルネットワーク」になるのだろうか。多分、正式な日本語はないと思う。
ニューラルネットワークは、パーセプトロンが横並び・縦並びに集まったもの。縦並びの数が増えれば、俗にいうディープラーニング（深層学習）。畳み込みニューラルネットワークは、色々ある機械学習モデルの中で代表的なものの1つ。画像認識によく使われていると思う。
画像認識の入力データの実体は、ピクセルの集まり。それぞれのピクセルは8つのピクセルに囲まれている。画像は、1つのノードに8つのエッジがくっついている規則正しい格子構造をとったグラフである。だがしかし、世の中、そんなデータばかりではない。画像のような規則的な格子構造をとっていないグラフ（ネットワーク）の方が多いのである。
拡散型の畳み込みニューラルネットワークは、その名の通り、畳み込み演算をする前に入力データの拡散を行って、任意のグラフ構造をとっているデータを正しく取り扱おうというモデルである。
入力データの拡散には、拡散行列を使う（勝手に命名した）。
は、ノードiからノードjへ割合
のデータが拡散することを表している。
は、ノードiのデータが拡散しない割合。ノードiとノードjが接続されていなければ、
。
と言っても実際は、拡散行列ではなくて、
の冪級行列（そんな言葉ってあるの？）
を入力データに作用させている。
モデルの学習のさせ方は、詳しく書かれていなかった。拡散行列は、どうやって学習させるのだろう...。
このモデルを使えば、ノードのクラス分け、ノードの値の予測、グラフのクラス分けなどができる。
Quantum Walk Neural Networks for Graph-Structured Data
著者・雑誌名。
Stefan Dernbach, Arman Mohseni-Kabir, Siddharth Pal, Don Towsley, Miles Gepner
arXiv, January 2018
内容。
量子ランダムウォークの知見をニューラルネットワークに応用してみたという論文。先ほどの拡散型の畳み込みニューラルネットワークと同様に特有のグラフ構造をとっているデータを学習するのに適している。
量子という名前がついているが、あくまで量子ランダムウォークの知見を応用しただけなので、このニューラルネットワークは、普通のコンピュータで動かすことができる。
このニューラルネットワークは、データの拡散行列に対応するテンソルを量子ランダムウォークによって求めている。量子ランダムウォークのcoin operaterは、各ノード・ステップに対してそれぞれ別々に定義する場合もあるが、この論文で具体的に示していたのは、すべてのノード・ステップに対し、共通して1つのcoin operaterを使うモデル。coin operaterは、の行列で、
は、1つのノードに接続されている最大エッジ数に対応する。ノードに接続されているエッジ数
が
より小さければ、そのノードは、
個のエッジが外に伸びていて、
個のエッジが自己ループを形成していると見なす。
それぞれのノードについているエッジには、1からまでの通し番号が付いている。疑似量子状態は、
。xは、現在のノードの通し番号、mは、そのノードから伸びているエッジの通し番号を表している。
まず、にcoin operaterを作用させ、作用後のそれぞれの状態に合わせて、ノード間の移動を行う。ノードxのエッジmの先にノードyが接続されていて、ノードyから見るとエッジmには、nという通し番号がついていたとすると
は、
に移る。
何ステップか量子ランダムウォークをした後にそれぞれのノードは、
という状態を取っている。
そしては、エッジmを通じて、ノードxのデータがどのくらいの割合で拡散されるかを表している。
その後、量子ランダムウォークで得られたをそれぞれの入力データに作用させ、適当な活性化関数でもって、出力を得る。
モデルの学習については、あんまり詳しく載っていなかったが、coin operaterを最適化するのだと思う。coin operaterは、次元の回転行列が無難。なんなら別にユニタリ演算子にこだわる必要もない（このアルゴリズムは、普通のコンピュータで動く疑似量子アルゴリズムなので）。
Quantum walk neural networks with feature dependent coins
著者・雑誌名。
Stefan Dernbach, Arman Mohseni-Kabir, Siddharth Pal, Miles Gepner, Don Towsley
Applied Network Science, September 2019
内容。
量子ウォークニューラルネットワークを改良したという論文。先ほどは、すべてのノード・ステップに対し、共通して1つのcoin operaterを使うモデルだったが、今回は、ノード一つ一つ・各ステップごとに異なるcoin operaterを使おうという話。
しかし、これだと、今まで1つで済んだcoin operaterをN（ノード数）×T（ステップ数）用意しなければならないし、モデル学習もそれぞれのcoin operaterで行わなければならない。このままだと、必要な計算資源と計算時間が爆発してしまう。また、量子ランダムウォークの時点で入力データはモデルに一切、与えられていなかった。量子ランダムウォーク後、拡散行列に相当するテンソルが得られてやっとデータが与えられる。
「計算量を削減したい」＋「量子ランダムウォークの時点で入力データも加味できるようになればモデルの学習が効率よく進むのでは?」という2つの考えから生まれたのが「bank（銀行）」。それぞれのノードに対応する入力データを引数にとって、coin operaterを戻り値として返す関数である。coinを作るので、bankという名前がついているのだと思う。
coin operaterは、bank（銀行）の関数を元に生成（鋳造）される。
この論文では、2つのが提案されている。
はノードiのデータで、
はノードiに隣接しているノードのデータである。ノードiのcoin operaterを生成するときに入力データもきちんと加味する設計になっている。
モデルの学習は、を採用したのであれば、
を、
を採用したのであれば、
を逆誤差伝播で最適化することによって行う。
を選んだ場合、ノードの番号振りによって、モデルの性能が変わる。この論文では、centrality scoreをそれぞれのノードに対して計算し、それを元に番号振りをすることを提案している。
Non-Markovianity is not a resource for quantum spatial search on a star graph subject to generalized percolation
著者・雑誌名。
Matteo A. C. Rossi, Marco Cattaneo, Matteo G. A. Paris, Sabrina Maniscalco
arXiv, November 2018
内容。
星状構造をとっているグラフ上での量子探索アルゴリズムが環境ノイズによって効率化されるか否かを調べた論文。特に環境ノイズによって変化する非マルコフ性と正しい答えが得られる確率の関係性を調べている。タイトルにもう結論が書かれているが、筆者らが調べた限り、ノイズによってアルゴリズムが効率的になることはなかった。
星状構造をとっているグラフ上での量子探索アルゴリズムの論文と非マルコフ性の定量の仕方に関する論文は、昔、紹介したので、よければどうぞ。
blog.sun-ek2.com
一般的なシミュレーション論文では、ノイズ（RTN）は、疑似乱数を使って発生させるが、それだと、きちんと非マルコフ性（環境ノイズ）とアルゴリズムの性能の関係性が分からない。（知っている人も多いと思うが、コンピュータで完全にランダムな乱数を発生させることは不可能。どうしても偏りが出てしまう）
ノイズがある状態での連続的な量子ランダムウォークの時間発展の解析解を得たという先行研究があるらしく、この論文ではそれを用いて、疑似乱数を使わずに厳密に非マルコフ性（環境ノイズ）とアルゴリズムの性能の関係性を調べていた。
Time evolution of continuous-time quantum walks on dynamical percolation graphs
著者・雑誌名。
Zoltán Darázs, Tamás Kiss
arXiv, September 2014
内容。
（集中力が切れて、途中からあんまりちゃんと読めていない）
連続的かつランダムにノードの接続が切れるグラフ上での連続的な量子ランダムウォークに関する論文。
グラフの形が毎回変わるので、厳密な閉形式を求めることはできないが、グラフが変形するステップが十分小さい、量子ランダムウォークが十分な時間が行われているという条件の下、近似的に閉形式を求めることができる。
その後、求めた式から得られる理論値と実際にシミュレーションを行って得られる実験値を比較していた。
