狠狠撸

自己紹介
? 名前：楠本 (@ir5)
? 新入社員
? 京大岩間研卒
?アルゴリズム系(理論&応用)の出身
? 今は映像解析や機械学習に着手
?個人的に Learning Theory が面白い

発表内容
先月参加した ICALP 2014 という学会の報告
ICALP 2014 (41st International Colloquium on Automata, Languages and Programming)
? アルゴリズム理論とか計算量とかプログラミング言語とか
オートマトンの学会
?アルゴリズム理論の会議ではヨーロッパでトップ
? デンマーク，コペンハーゲン
? 修論が Accept されたので行った
↓コペンハーゲンの町並み

コペンハーゲンの様子

アルゴリズム理論
? 組合せ問題，最適化問題などに対し，
?性能の良いアルゴリズム (計算時間 / メモリ消費 /
近似度等) を与える
?困難性の証明をする
?性質の定式化を与える
? 漸近的な解析を与えることがメイン
(つまり入力が十分大きいときの性能を考える)
?(c.f., 実データに対するアルゴリズム
例： shortest path problem

会議の雰囲気
(ビジネスミーティングは出席しそびれたため雰囲気だけ)
学会
? Track A (アルゴリズム?計算量)，Track B (プログラミング言語)，
Track C (ネットワーク？) から成る
? Track A には 87 の発表論文
? 採択率は例年は 25%~30% くらいらしい
雰囲気
? アカデミックの人が大半
?たまに MSR, IBM などの人も
? ヨーロッパ人多い(8割くらい？)
? 目視で90～120人くらい居た
? 日本人は2人
↑会場のITコペンハーゲン大学

スケジュール
? 1日目：ワークショップ Day
? オンラインアルゴリズム
?PhD 学生のポスター発表
? 2日目～5日目：発表
?朝最初に招待講演
?朝～昼に口頭発表
?3セッション並列

1日目 : ワークショップ

1日目 : オンラインアルゴリズム
オンラインアルゴリズムとは
? 将来何が起こるか分からない状況下でできるだけ良い判断
(コストが小さくなる，利益を大きく出来る等)をする
アルゴリズムのこと
?例：株価の予測とか
? アルゴリズムの性能は競合比での解析が主流
? コストを小さくしたい場合：
? 競合比が最悪でいくらになりうるかを解析するのが主な目的
(競合比が大きければ大きいほど性能が悪い)
アルゴリズムの出した解のコスト
競合比 = ------------------------------------------------------------
入力を全部知っていた場合の最適コスト

例：ビンパッキング問題
色んな大きさのアイテムがある．容量 1 のビンをいくつか用意
してすべてのアイテムを詰めるにはビンがいくつ必要か？
例：オンラインビンパッキング問題
アイテムがオンラインで来る．その都度，アイテムをすでにある
ビンに詰めるか新たにビンを開封するかの判断をする．
ビ
ン
ア
イ
テ
ム

印象に残ったもの
? オンラインビンパッキング問題
? Advice 付きオンラインアルゴリズム
? オンラインシュタイナー木問題
? オンライン線形計画問題
? オンライングラフ彩色問題

? オンラインで解くことが難しい問題は多い
? 例えばオンラインビンパッキング問題の場合，競合比 ≥ 1.54
Advice 付きオンラインアルゴリズム
? 入力を全部知っている人(神)がいて，入力に関する情報を
事前に教えてもらえる (入力は小さいデータしかないとか)
? ただし神はアルゴリズムにちょっとしか情報を送れない
? オンラインビンパッキングの場合，log n ビットの情報を教え
てもらえると競合比を 1.5 にできる

Advice 付きオンラインアルゴリズム
? オンラインナップサック問題の場合，競合比 = ∞
? しかし 1 ビットの情報を送ってもらえるだけで競合比 = 2 を
達成できる
ナ
ッ
プ
サ
ッ
ク
ア
イ
テ
ム

Claire Mathieu. Homophily and the Glass Ceiling Effect
in Social Networks
? 実社会で起きている現象を数理モデル化して解析する話
? 「なぜアカデミア(特に CS コミュニティ)では男女のバランスが
不均一なのか？」
※図は著者の発表
スライドより引用

? 同じ性質を持った人同士が結びつきやすい性質(“rich gets
richer”; homophily) を表す(数学的な)条件を 3 つ定義
? 次のことを証明した
?条件がすべて同時に成り立つとき不均一が起きる
?逆に条件が1つでも成り立たないと，不均一は起きない
Claire Mathieu. Homophily and the Glass Ceiling Effect
in Social Networks
※図は著者の発表
スライドより引用

Sanjeev Arora. Overcoming the Intractability Obstacle
for Unsupervised Machine Learning

? 教師なし機械学習の話
?データが何かの分布から生成されると仮定して
尤度最大化等をする
?多くの場合 NP 完全になる
? しかし，現実のデータは NP 完全になるような意地悪い入力
じゃないかもしれない
?分布になんらかの現実的な仮定を置くと適当そうな
ヒューリスティックがまともな計算量になるのでは？

↓ヒューリスティックと理論屋の図

? 基本的には講演者のグループでやっている機械学習寄りの
研究の話
?Topic model の non-negative matrix factorization
?Dictionary learning
?Deep nets の解析等

全体の傾向とか
? 色々ある
? 計算量理論(PとかNPとか)
? オンラインアルゴリズム
? ストリーミングアルゴリズム
? 近似アルゴリズム
? 乱択アルゴリズム
? 難しい問題で入力クラスを制限して解けるようにする系
? オラクルに聞いて何かを決める系
? 幾何っぽいの
? etc…

Eric Blais, Johan H?stad, Rocco Servedio and Li-Yang Tan.
On DNF approximators for monotone Boolean functions
? DNF(積和標準形) とは ↓ こういうの
復習: 任意の n ビット論理関数 f : {0,1}n → {0,1} はサイズ(項数)
が高々 2n の DNF で書ける
?逆に Ω(2n) サイズ必要な論理関数が有る
? f を近似する DNF を表すことにすると？
?ε>0 が与えられた時に，ある g で，Pr[f(x) ≠ g(x)] < ε となる
ようなものをできるだけ小さいサイズの DNF で書きたい
?Ω(2(1-4ε)n) は必要らしい
? 今回
?f を単調関数に制限するとサイズ Θ(2n / √n) でいいらしい
f(x1, x2, x3) = x1x2 + x2x3 + x1

(BEST PAPER) Andreas Bj?rklund and Thore Husfeldt.
Shortest Two Disjoint Paths in Polynomial Time
? グラフがあって頂点 s1,t1,s2,t2 が指定される
? s1→t1，s2→t2 に向かうパス対で
互いに頂点を共有しないもので
パス長の和の最小を求める
? 今まで指数時間解法しか知られていなかった．
? 彼らは多項式時間アルゴリズムを提案した
?ただし O(n11) とかかかる

ざっくりした概要：
? 変数入り隣接行列の Permanent を
考えると，多項式で最初に現れる
非ゼロ項の次数が最小パス長に等しい
?元のパスが何なのか分からないが
最小パス長だけは分かる
? Permanent の計算は一般には #P-hard
? しかし今回の目的なら計算したいものが限られているので
うまく計算するアルゴリズムが存在する

なぜ BEST PAPER?
? シンプルな問題設定
? 証明はシンプルでありながら非自明
? 指数→多項式は大きなブレークスルー
? 代数的アルゴリズムの利用
とかが効いている？

Mitsuru Kusumoto and Yuichi Yoshida. Testing Forest-
Isomorphism in the Adjacency List Model
? 僕です

Mitsuru Kusumoto and Yuichi Yoshida. Testing Forest-
Isomorphism in the Adjacency List Model
http://ir5.hatenablog.com/entries/2014/04/12

Amir Abboud, Virginia Vassilevska Williams and Oren Weimann.
Consequences of Faster Alignment of Sequences
? 文字列マッチング系の問題で，?(n2) 時間より速い
アルゴリズムが知られていないものは多い
?編集距離，最長部分列，…
? 今回は配列アラインメントで ?(n2) より真に速いアルゴリズム
は無さそうなことを証明
? 無さそうとは？
?配列アラインメントが O(n2) より真に速く解けるとすると，
他の有名問題で「速く解くのは無いだろうと思われてる
問題(3-SUMとか)」がたくさん解けてしまう，と証明

Konstantin Makarychev and Yury Makarychev.
Nonuniform Graph Partitioning with Unrelated Weights
? グラフの最小 k 分割：
?グラフの頂点を k 個のクラスタに分けて，異なるクラスタ
にまたがる枝の個数を最小化する
?多分NP完全？だが O(√(logn logk)) 近似がある
? Nonuniform グラフ分割
?i 番目のクラスタの大きさは ρin 以下でないといけない
?O(logn) 近似が知られていた
?→ O(√(logn logk)) 近似に改善
? SDPベースのアルゴリズムを使うらしい

Andreas Bj?rklund, Rasmus Pagh, Virginia Vassilevska
Williams and Uri Zwick. Listing Triangles
? Triangle listing : グラフ中の△を全部列挙したい!!
? ’78：O(m√m) 時間アルゴリズム (m は枝数)
?△の個数は Θ(m√m) 個ありうるのでタイト
? でも output sensitive (△の個数を t としたとき t に依存する計
算時間) にしたいですよね？？
?熾烈な計算量の争い

Andreas Bj?rklund, Rasmus Pagh, Virginia Vassilevska
Williams and Uri Zwick. Listing Triangles
? ω は行列積にかかる計算時間の指数部
?現在は ω = 2.3728639
? ω = 2 ならこの計算時間はタイト!! という主張
?(少しアグレッシブすぎではないか…)

ゲーデル赏
3日目の conference dinner でゲーデル赏の授賞式があった
ゲーデル赏 (G?del Prize) は、理論計算機科学分野で優れた功績を残した人
に、ACM（アメリカ計算機学会）のアルゴリズムと計算量理論に関する部会と
EATCS（ヨーロッパ理論コンピュータ学会）が贈る賞である。受賞者には賞金
5,000ドルが贈られる。論理学者クルト?ゲーデルに由来する。計算機科学分
野ではチューリング賞と並んで権威を持つ賞である。 (Wikipedia より)

ゲーデル赏
例年に比べると少し応用に寄っている？

まとめ
? ICALP 2014 のレポートでした
? 来年は京都で開催されるらしいです
感想
? 綺麗だけど複雑な構造を持った問題に対してアプローチ
したい人が多い気がする
? テーマ探しが難しい
?基本的な問題は大体既に解かれている or 解くのがすごく
難しい
?凝った問題設定に走り過ぎるとモチベーションが何か
わからなくなる
? デンマークは物価が高い
謝辞
今回の ICALP 参加は JST/ERATO 河原林巨大グラフプロジェクト
よりご支援を頂きました．関係者の方々に深く感謝致します．

狠狠撸

ICALP 2014 参加记

More Related Content

ICALP 2014 参加记

Editor's Notes