Less is More: Compact Matrix Decomposition for Large Sparse Graphs
□Five Cs
- Category? : グラフデータマイニングとか(隣接行列を行列分解することで特徴・異常を検出)
- Context? : SVD/PCA、CURなどの行列分解方法とか、この方法自体はCURを改良したって感じ？
- Correctness: 論理の流れは妥当
- Contributions: CURと同精度で、1/10程度メモリを削減できるCMDと呼ばれる方法を提案し、その、理論的解析や、静的グラフマイニングや動的グラフマイニングへの応用を提案した
- Clarity: 論文自体は読みやすいような(dramaticallyとか、つょぃ……言葉がよく出てきてるなという感じはしたけど)
隣接行列からGraphのパターンや異常を検出するって方法の1つっぽい
もう少しうまく使えれば面白そう(クラスタリングでグラフラプラシアンとか出てきてるからその辺と関連付けるとか？
第2フェーズはそのうち読む(投げやり)
How to Read a Paper
読んだ(http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/07/paper-reading.pdf)
タイトル : How to Read a Paper
著者 : S. Keshav, David R. (Cheriton School of Computer Science, University of Waterloo)
これなに？
- 実用的で効率的な論文の読み方である"Three-Pass"って方法の紹介
- "Three-Pass"を文献調査へ応用する方法の紹介
この"Three-Pass"って方法のよいところ
- 論文の概観がつかみやすい(大意を掴む前に細部にハマることがない)
- 論文の読む時間が大体わかる
- 時間やニーズにあわせて理解度を調節できる
"Three-Pass"ってなんぞや？
→論文を読む工程を3段階に分解
- その論文に書かれてる一般的なアイデアを得る
- 論文の内容を掴む(証明などを省いて)
- 前段階より深く論文を理解する(頭の中で論文を再構築できるくらいに)
まず1段階目の概要理解フェーズ
- タイトル + アブスト + イントロ をじっくり読む
- 節と小節の見出しを読む
- 論文の数学的内容を見て、基礎的理論を把握
- conclusionを読む
- リファレンス読んで、一度読んだ論文をチェック
これが終わった後以下の質問(Five Cs)に答えられないといけない
- Category: この論文はどんな分野の論文？ 何かの評価？既存のシステムの解析？研究のプロトタイプの解説？
- Context: 他の関連する論文は？ どの基礎理論が用いられている？
- Correctness: 論文における考察・論理は妥当？
- Contributions: 主な貢献は何？
- Clarity: 論文はうまく書かれている？読みやすい？
- この情報を使って、次の手順に行くかどうか、この論文が必要かどうかを決める
- 大体かかる時間は5分から10分くらい
- 逆に、ここで読みにくい・わかりにくい論文はバッサバッサ切られていくと思え(論文を書くときの参考として)
2段階目のじっくり読むフェーズ
とりあえず証明みたいな詳細を除いてちゃんと論文を読んでいく
以下のポイントに注意
- キーポイントやコメントを余白にメモする ex)わからない言葉・質問したいこと
- 図やイラストを注意深く見る
- 特にグラフはめっちゃみる(軸ラベル・データから導き出される結果と結論が統計的に妥当？
- 未読の関連文献にマークを付ける
- 熟練の研究者でもこの手順は1時間以上かかる
- この手順を終えた後、論文の内容を把握できて、その要旨を根拠とともにまとめられて人に伝えることが出来るレベルにならないとダメ(所謂ちょうどいいレベル)
これを経てもわからないときは？
原因は？
- テーマが自分に取って新しい
- よく知らない専門用語や略語が多い
- 知らない実験技術とか根拠がある
- 証明されていない主張とかがあって論文自体がダメ
- 疲れた状態で読んでる
対策として
- 論文を閉じてさよなら(今後の人生でいらないと考える)
- 背景についていろいろ調べて再度読む
- 次のステップに行く
3段階目(再構築フェーズ)
- 論文を脳内で再構築していくフェーズ
- 再構築したものと実際の論文を比較することで以下の点に気づけて自分の物にできたりするっていう利点がある
- 論文の新規性
- 論文に隠された誤りや考察
- 論文における証明技法・表現技法
- このフェーズで将来の研究へのアイデアを書き留めたほうがよい
- 熟練の研究者でも1〜2時間以上はかかるフェーズ
- この手順を終えた後は以下のことができる(らしい)
- 短所と長所がわかる
- 記憶から論文の全体構造を再構築できる
- 隠れた仮定や紐付けられていない関連研究がわかる
- 実験的・解析的な技法の潜在的問題点を指摘できる
文献調査への応用
(第1段階) : その分野での研究の感覚をつかむ
- Google ScholarとかCiteSeerで、調べたい分野でめちゃくちゃ引用されている3〜5つの論文を見つける
- その論文に概要理解フェーズを適用、研究の感覚を掴む
- 関連研究の欄からサーベイ論文だったり、その分野の研究のまとめっぽい論文を探して読んでいく
(第2段階) 有名な論文・著者、トップカンファレンスを見つける
- よく文献で出てくる論文・著者名を見つける
(これがこの分野における有名な論文や研究者) - 見つけた有名な研究者のサイトへ行き、最近どこで発表しているかを確認
(これがこの分野におけるトップカンファレンス)
(第3段階) トップカンファレンスの最新の論文と最初の論文を合わせる
- トップカンファレンスの最新の論文を調査
- 第1段階で見つけた論文、第2段階で見つけた著名な論文、トップカンファレンスの論文を合わせて最初のサーベイとして、これらの論文に対し、「概要理解フェーズ」、「じっくり読むフェーズ」を適用
- 概要理解→じっくり読み→脳内再構築の3段階ってのは頭に入れないとなぁ
- 論文の読み方がなんとなくわかった(気になっただけかもしれないけど)
- surveyの方法がわかれば読むだけだもんなぁ、これに従って
- ただこれは情報系に対応して書いたってわけじゃないからところどころ直さないと行けないと思うけど
More than machines - Nature Machine Intelligence Vol.1 Issue 1
今月から出るジャーナルのEditorialを読んだ。
このジャーナルはだいたい下の3つのテーマについて書かれてるっぽい。
- Machine Intelligenceを構築するためのハードウェアやアルゴリズムの研究開発
- 他分野へのDeep LearningシステムのようなMachine Intelligenceの応用
- 社会・産業・科学におけるMachine Intelligenceの影響の研究
以下感想
- 大規模なデータを、収集・共有・保存できるようになったのがデカイなぁ
- それを計算能力が高いコンピュータでババッと処理できるようになったのがBreakthroughの要因だよね
- Deepは"狭い"けど、その狭さってのは急激な進歩につながってるってのはわかる
だって、人間より正確に人間っぽいことできるのは強いよなぁ - だけど、社会的な影響の危険性とか倫理的な懸念とかも触れないとアカンよね
他にも記事があったので卒論の合間にかいつまんで読みます
あけましておめでとうございます
A NEW METHOD FINIDNG THE K-TH BEST PATH IN A GRAPH
著者 : H. Ishii (鉄道技研の方！)
雑誌 : Journal of the Operations Research (1978)
- 例のごとくK Shortest Pathsに関する論文
- 無向グラフに対するlooplessなKSPを考える
概要
- a minimum set of ring sum of Euler graphs and an arbitrary path between two vertices is a collection of all paths between the vertices. とあるようにこの考え方を用いている(英弱だからあんまり適切な日本語訳がわかっていない)
- Yenのアルゴリズムと同じくらい速い
アルゴリズムの流れ
- 連結なグラフがあったとして最短路木を考える(最短経路に使われる辺からなる木)
- 最短路木に含まれない辺をchord、含まれる辺をbranchと呼ぶよ
- chordをそれぞれe_1,e_2,...,e_fとするよ(fはm-n+1だよね)
- それぞれのe_iに対してC_iってのを考えたい
→chordに含まれる辺をe_iのみ使う、元のグラフの基本サーキットだよ
(僕はグラフ理論弱者なのでわからないですがこのようなサーキットは一意に決まるのでしょうか 決まりそうですけど) - で、P1ってのを最短経路に含まれる辺の集合として
Q1 = P1, R1 = {P1}, E1 = P1 xor Q1(つまり空集合)とするよ - k>=2に対してR_kを以下のように定めるよ
R_k = (R_(k-1)からQ_(k-1)を除いた集合) ∪ {Q_(k-1) xor C_i}
ただし、e_i ∩ E_(k-1) = ∅, Q_(k-1) xor C_i ≠ Q_l (l = 1,...,k-2)
(下から2行目のxorの部分は、元論文だとただの+になってたし、その下の行のk-2の部分はk = 2になってたりとか誤字が多い気がする、k-2のところは実際そうかわからん) - R_kの要素からコストが一番小さい要素を取り出してQ_kとする
んで、E_k = P_1 xor Q_kとするよ
(ここもxorじゃなくて+だった 意味がわからん 多分xorだろ) - Q_kがパスだったらk番目のの要素とするよ 違ったらまたR_kを作るステップに戻るよ
- K個のパスが得られるまでやる おわり
完全グラフに対してしか計算量解析してないけど、Yenと同じくらい速いよ〜って書いてた。
前処理でサーキットさえ求めれば後は集合演算だけでKSPを生成できるの端的に言って強い(方法がスマートだよね)
某Zから始まるデータ構造と相性が良さそう……だし、実装も楽そうだし今度実装してみようと思う(けど、誤植っぽいところはどうしようかなぁ、実際手で動かしてみないとわかんないわね)
Widest Path ProblemとMinimax Path Problem
英語版wikiを和訳しただけ、色々調べる（Todo）しまとめる（Todo）
概要
どんな問題？
- グラフ理論における問題の1つで
重み付きグラフの2つの指定された頂点間のパスにおいて、
最小重みの辺の重みが最大なものを見つけるという問題 - Bottleneck Shortest Path Problem（ボトルネック最短路問題）
Maximum Capacity Path Problem（最大容量パス問題）
などとも呼ばれることがある - パス長さの代わりにボトルネック距離を使うことで、多くの最短経路アルゴリズムを用いてWidest Pathsを計算することが可能（だが、より高速なアルゴリズムあり）
応用例
- 例えば、インターネットにおけるルータ間の接続関係を表したグラフを考える。このとき、ある辺の重みは2つのルータ間の接続の帯域幅を表す
- ここにおいて、Widest Path Problemは、可能な最大限の帯域幅を持つ、ある2つのインターネットノード間のパスを見つける問題となる
- このパスにおける最小の辺重みは、パスの帯域幅や容量と呼ばれる
- 他にも、選挙方式の1つのシュルツ法において当選者を決定する際や、デジタル画像合成、代謝経路分析、最大フローの計算においても重要な要素の一つとなっている
Minimax Path Problem（最小最大パス問題）
- Widest Path Problemと類似した問題として、パスに含まれる辺の重みの最大値を最小化するというMinimax Path Problem（最小最大パス問題）がある
- この応用として運輸計画に関するものがある
- Widest Path Problemに対する任意のアルゴリズムは、Minimax Path Problemに対するアルゴリズムに変形することができ、逆もしかり
- どうすればよいかと言うと、アルゴリズムにより行われる重み比較の意味を逆にするか、全ての辺重みを等しく正反対なものに置き換える
無向グラフにおけるWidest Path Problem
- 無向グラフにおいて、2頂点間のWidest Pathは、グラフにおける最大全域木上に存在し、2頂点間のMinimax Pathは同様に最小全域木上に存在する。[8][9][10]
- 有向、無向に関わらず任意のグラフにおいて、あるWidest Pathにおける最小重みを持つ辺の重みがわかっている場合、そのWidest Pathを見つける愚直なアルゴリズムが存在する。 -> その辺の重みより小さい重みを持つ辺を削除した上で、残りの辺をもとに任意のパスをBFSやDFSを用い探索する
- この観察に基づいた、最大全域木を用いない、無向グラフにおけるWidest s-t pathを見つける線形時間アルゴリズムが存在する
- このアルゴリズムの主なアイデアとして、グラフにおける中央値の辺重みを用い、先程の線形時間でWidest Pathを探索するアルゴリズムを適用する
- 続いて、パスが存在する場合、先程の重みより小さな重みの辺を削除し、存在しない場合は、先程の重みより大きな重みの辺を縮約し、結果として得られる小さなグラフに対し再帰する
Minimax Path Problemの画像合成への応用
- Fernandez, Garfinkel, Arbiol（1998）では、このMinimax Path Problem (Bottleneck Shortest Path) を重複した領域がある複数の画像を組み合わせる、合成航空写真を形作るために用いた
- Widest Path Problemが適用される部分問題において、 2つの画像はすでに共通座標系に変換されていて、残りの課題は、つなぎ目を選択することである。
- つまり、2つの画像の1つから、他の画像を分ける曲線を選択すること
- つなぎ目の片方のピクセルは、画像のうちの1つからコピーされ、つなぎ目のもう一方のピクセルは、もう片方の画像からコピーされる
- 他の両方の画像におけるピクセルの平均をとる合成方法と異なり、この方法は正しい画像を生成することができる(this produces a valid photographic image of every part of the region being photographed. )
- グリッドグラフの辺に対する重みを、そのエッジがつなぎ目としてどのくらい視覚的に見えるかの数値量として、これら重みに対するWidest Pathを探索する(They weight the edges of a grid graph by a numeric estimate of how visually apparent a seam across that edge would be, and find a bottleneck shortest path for these weights.）
- 従来の最短経路ではなくこのパスをつなぎ目として用いることで、他の場所でのより低い視認性のために、画像の一部においてより視認性を高くする犠牲を払うことを可能にすることよりもむしろ、その点すべてにおいて認識が困難なつなぎ目をシステムによって検出することができる(Using this path as the seam, rather than a more conventional shortest path, causes their system to find a seam that is difficult to discern at all of its points, rather than allowing it to trade off greater visibility in one part of the image for lesser visibility elsewhere.[4])
- グリッドグラフの2つの相対する角の間におけるMinimax Path Problemへの解法を用いることで、2つのpolygonal chainの間のweak Frechet distanceを見つけ ることができる
- ここで、各グリッドグラフの頂点は、各チェーンから1つずつ、線分の1つのペアを表し、辺の重みは、1つのペアの線分から別の線分へと移動するのに必要なFrechet distanceを表す
- もし、無向グラフのすべての辺の重みが正であるならば、点間のMinimax距離（Minimax Pathの最大の辺重み）は超距離を形成する
- このようにして、逆にすべての有限な超距離空間は、Minimax距離からくる
- 最小全域木から形成されたデータ構造によって、任意の頂点間のMinimax距離を、Cartesian TreeにおけるLCAクエリを用いることで、1つのクエリに付き定数時間で答えることができる
- Cartesian treeの根は、最小全域木における最大重みの辺を表し、その子は、最大重み辺を削除することによって形成された最小全域木の部分木により、再帰的に形成されたCartesian treeである
- Cartesian treeの葉は入力グラフの頂点を表し、2つの頂点間のMinimax距離は、Cartesian treeにおける、LCAにあたる頂点の重みに等しい
- 最小全域木の辺がソートされている時、このCartesian treeは線形時間で形成することができる
有向グラフ
- 有向グラフにおいて、最大全域木による解法は使用できない
- 代わりにいくつかの異なるアルゴリズムが知られている
- 単一始点かつ単一終点のもの、単一終点のもの、全点対のものなどがある
全点対Widest Path Problem
- 優先順位に基づき投票者が候補者のランク付けを行う双方向選挙における照射決めるためのSchulze法における応用として、全点対Widest Path Problemがある
- Schulze法は、頂点が候補者で、任意の2頂点が辺により連結されている完全有向グラフを形成する
- 各辺は、つながっている2人の候補者の間における、勝者から敗者の向きに向き付されていて、そのコンテストのマージンでラベル付けされている
- 続いて、頂点の全ての対におけるWidest Pathを計算する、そして勝者はその頂点が互いに相対する頂点へのWiderなPathを持つ候補である
- この方法を用いる選挙の結果はコンドルセ法（全ての点対のコンテストに勝利した候補者は自動的に全体の選挙にも勝利する）からなるが、それは一般的に勝者に選択されてしまうことを許してしまう、コンドール法が失敗するときでさえも
- Schulze法は、Wikimedia Foundationを含むいくつかの組織において使用されている
- 投票における応用の一つのような、密な有向グラフにおける、全点対に対するWidest Path幅を計算するために、漸近的に最速の知られている方法として、O(n^(3+ω)/2)の方法がある（ここで、ωは高速行列乗算の指数である）
- 行列乗算に対する知られている最良のアルゴリズムを用いると、この計算量上界は、O(n^2.688）となる
- 代わりに、Schulze法の参照実装は、より簡単なO(n^3)のワーシャるフロイドアルゴリズムを変更したものを用いる
- 疎なグラフに対しては、単一始点のWidest Pathアルゴリズムを繰り返し適用するほうがより効果的である場合がある
単一始点
- もし辺が重み順にソートされている場合、ダイクストラアルゴリズムを変形したものを用い、指定された始点から他のすべての頂点間のBottleneckを線形時間で計算することができる
- 従来のダイクストラアルゴリズムにおけるスピードアップの背後にある考え方は、このアルゴリズムによって考慮される順序における、それぞれの頂点におけるボトルネック距離の列が、辺重みに対しソートされた列である単調な部分列であるということ
- それ故に、ダイクストラアルゴリズムの優先度付きキューは、バケットキューとして実装することができる（1からm[グラフの辺数]で索引付けされた配列で、i番目の要素には順序付けされたi番目の辺の重みのボトルネック距離が含まれている
- この方法はソートと同じくらい早くWidest Path Problemを解くことができ、例えば辺重みが整数で表現されている場合、m個の整数のリストを整数ソートする際の計算量の上界を適用することができる
単一始点と単一終点
- BermanとHandler(1987)は、サービス車両と緊急車両は、サービスコールから基地へ戻る際にMinimax Pathを使うべきだと提案した
- この応用において、車両が戻るのにかかる時間は、他のサービスコールが発生した際の反応時間より重要でない
- 辺の重みが、アル点における辺から最も遠い可能性のあるサービスコールまでのMinimax Pathを用いることにより、サービスコールを受け取ったあとに、反応車両が到着するまでの、可能性がある最大の遅れを最小化することができる
- Ullah, Lee and Hasson(2009)は、彼らのモデル内で、代謝ネットワークにおける支配的な反応連鎖をモデリングするために、Maximin Pathを利用した
- 辺の重みは、対応する代謝反応の自由エネルギーの値である
- Widest Pathの他の応用として、最大フロー問題に対するFord-Fulkerson algorithmがある
- フローの残差ネットワークにおける最大容量のパスに沿ってフローを繰り返し増加させることは、最大フローを見つけるために必要な増加数に関するオーダーO(m log U)を与える（ここで、辺の容量は最大でもU(整数)であると仮定される）
- しかしながら、この分析は正確な最大の容量を持たないパスを見つけることに依存しない、最大値の定数項の範囲内の容量の任意のパスで 十分である
- この近似アイデアと、Edmonds-Karpアルゴリズムにおける、最短経路増加法を組み合わせることにより、最大フローアルゴリズムがO(mn log U)で動く
- 入力グラフの辺重みの比較のみを許し、算術演算を許さないような計算モデルにおいても、単一始点・単一終点のMaximum-CapacityパスやMinimaxパスをとても効率良く見つけることが可能である
- そのアルゴリズムは、最適なパスのボトルネックとなっている辺を含むとして知られている、辺の集合を保つ
- 最初に、Sをグラフの全てのm辺からなる集合に初期化する
- アルゴリズムの繰り返しの各々において、Sがほぼ同じ大きさの部分集合の順序付けられた列に分解される
- この分割における部分集合の数は、O(m)での中央値探索を繰り返すことにより見つかる部分集合間の分割点の全てを選択するという方法で行われる
- そしてグラフの各辺を、その辺が含まれる部分集合のインデックスにより再重み付けし、その再重み付けされたグラフ上において修正されたDijkstraアルゴリズムを適用する
- この計算結果に基づき、ボトルネックとなっている辺重みを含む部分集合がどれかを線形時間で決定することができる
- そしてSを、ボトルネック重みが含まれている部分集合S_iにより置換し、次のループをこの新しい集合Sにおいて始める
- Sの可能な部分集合の数は、各ステップにおいて指数的に増加するため、反復回数は、反復対数関数（iterated logarithm function）に比例し、O(log* n)である、そして合計の時間はO(m log*n )となる
- 各辺の重みが整数データ型の時、このアルゴリズムの繰り返しbisectionする部分を、HanとThorupのリスト分割テクニックに置き換えることができ、SをO(√m)のより小さい集合に、1つのステップで分割することができ、全体として線形時間のオーダーになる
ユークリッド空間上の点集合
- Minimax Path Problemの変種として、ユークリッド空間情の点集合を考慮するものがある
- 無向グラフの問題として、このユークリッドMinimax Path Problemはユークリッド最小全域木を見つけることにより効率的に解くことができる（この木上の全てのパスはMinimax Pathとなる）
- しかし、ホップ長を最小化するだけでなく、同じホップ長を持つパスの中で、パスのトート有るの長さを最小化する or 近似的に最小化することも望まれている場合、問題がより複雑になる
- 近似的な解法としてGeometric Spannerが用いられる
- 数論において、ガウス素数におけるMinimax PathsのMinimax長は上界を持つか否かについて問う、未解決なGaussian moat問題がある。
- 言い換えると以下のようになる
ガウス素数により定義される、無限のユークリッド点集合に含まれる全ての点pとqのペアに対し、ガウス素数pとqの間のMinimaxパスは、たかだかminimax edge長がBであるか？
