C&C受賞記念講演行ってきた Ullman編
目次
Aho編:
pandaman64.hatenablog.jp
Hopcroft編:
pandaman64.hatenablog.jp
Ullman編: ここ
メモ
Aho, Hopcroftに続いて最後に話したのがUllmanです．
学生へのメッセージは言ってない気がする．聞き取れなかったのかもしれない．
最近はParallel Computationが良く使われている．
これは並列で計算することで高速化を図るためである．
しかし，並列計算を手でやるのは極めて辛い．そこで簡単に並列計算するためのシステムが作られてきた．
並列計算の中でも初期のアルゴリズムであるMapReduceについて詳しく見ていこう．
MapReduceの特徴としては
- 並列処理を陽に書く必要が無い
- 計算が失敗しても自動でハンドリングしてくれる
という点が挙げられる．
しかし，MapReduceにも制限があり，特に"reducer size"と"communication cost"にトレードオフが存在することを明らかにした．
MapReduceはMapとReduceの二つの部分からなる．
Map処理では，それぞれの入力に対してMapperを並列に適用する．
Mapperの戻り値はkey-value pairの集合となる．
このとき，入力に対して多段のmapperを適用することが多い．このような一連のmapperはMap Taskとしてひとつにまとめられる．
その後，並列計算システムが全てのMapperが返したkey-value pairをkeyでグループ化する．
グループ化したデータはkeyをキーとし，それに紐づけられたvalueのリストを値とするようなkey-value pairの集合になる．
これの各key-(valueのリスト)についてreducerを適用することで最終結果を得る．
- MapperとReducerの実行時間
- Reducerにデータを送るときの通信時間(communication cost)
の二つの要因によって変化するが，多くの場合通信時間の方が影響が大きい．
薬の相互作用を突き止めるという課題で実際に生じた問題を紹介する．
これはStanfordのCS 341(data mining)で取り上げたトピックである．
医薬品は3000種類あり，それぞれの医薬品について1MB分の服薬データ（日時とか症状とか）がある．
この中から悪い飲み合わせといったような薬同士の相互作用を見つけたい．
これをMapReduceでやるとすると，ナイーブなアルゴリズムとしては
- Mapperは薬のペアをkey，片方の薬の服薬データをvalueとするデータを用意する
- Reducerは各keyのグループについてsignificantな相互作用が存在するか調べる
というものが考えらえる．
このアルゴリズムの問題点は，key-value pairの数が膨大になってしまうことである．
薬のペアは個存在し，それぞれについて1MBの服薬データがくっつくので，全体で9TBのデータが発生し，これをネットワーク越しにReducerに送らなければならない．
これは1Gbps Ethernetでは全然終わらない量のトラフィックである．
このアルゴリズムを改良には薬をグループ分けしてやれば良い．
例えば，100個の薬を一つのグループとして扱うと，グループのペアの数は個になり，通信量も9TBから90GBに落ちるので数分待てば計算できる．
各ペアにくっつくデータ量は増えるが，計算時間は結局変わらないので全体としては大きく高速化された．
MapReduceの計算モデルを考えると以下のような特徴がある．
MapReduceアルゴリズムの解析で重要になる値を定義する．
- Reducer Size(Q)*1は一つのReducerが処理する入力の最大のサイズである．Qは計算機のメモリサイズで上からバウンドされる．またQが小さいほど計算の並列度が大きくなって嬉しい．
- Replication Rate(r)は一つのMapperが生成するkey-value pairの個数の平均である．rが大きいほどはcommunication costが大きくなってしまう．
先ほどの問題では，
という関係が成り立つ．
係数はグループの個数に依存する．
上式を見るとrとQの間でトレードオフが生じていることが分かる（Qを小さくすると並列度が上がるが，rも大きくなるのでcommunication costが増大する）．
rをQの関数で表すという研究がある．
これができると，あるMapReduceアルゴリズムが上手いこと計算できているかを測定することができる．
rの上界をQの関数で表すことは既にできており，Ullmanは下界を調べた*2．
これには，以下の性質が使える．
- 1つのReducerが扱えるデータはQ個までである（Qの定義から）
- 全ての出力について，その出力を計算するのに必要なだけの入力を受け取るようなReducerが存在する（さもなければその出力が計算できないため）
薬の問題で示した改良後のアルゴリズムはrが下界の2倍になる．
最良のアルゴリズムでは下界+1を達成できることが分かっている．
つまり，Ullmanの与えた下界は極めてタイトである．
他にも色々な問題に対してrとQの関係を調べることができる．
例えば行列の乗算をMapReduceでやることができる．
この場合には，MapReduceを2段にした方が効率が良いことが分かっているので，薬の問題で使った手法（これは1段MapReduce）は改善する必要がある．
ハミング距離1のビット列の問題*3についてもトレードオフが存在することを明らかにした．
一方ハミング距離が2になった場合にはopen problemである．
Marginals of a data cube*4についても調べた．
ここで全員の話は終わりで，16時を少し回ったぐらいだった気がする．
数分の休憩を挟んだ後QAセッションが開始．
最初の質問をした人が最前列の関係者席に座っていたご高齢の方で，聞き取りづらい英語でよー分からん話をグダグダ喋っていて時間がゴリゴリ溶けた．
QAセッションのメモはほとんどとってない．
Ahoが学生に対してNumber theory, Group theory, （量子コンピュータやるなら）Topological Theoryやるのが良いよとアドバイスしていた．
今の学部教育ではロクに数学やらないから考え直さないとかもねとも言ってた．
Hopcroftは人の直観は三次元空間用だから機械学習で出てくる高次元空間では通用しないよねとも言っていた．
また，教科書の話題では，本を書くのはお金を儲けるというよりも良い評判を得るためだよね（ただし中国語版は例外）とも発言していた．
結局3人のQAをした所で30分が過ぎてセッションは終了．
そのまま解散．
色んなトピックの話を聞けて凄い面白かった．
特に，Ahoは自分にとって完全に「ドラゴンブックの人」という扱いだったので，彼の口から量子コンピュータの話が出てきたときには驚いたし*5，最新の研究への言及もあって極めて良い刺激になった．
英語も大体聞き取れた．
メモ取ってる途中に喋られると厳しい～～～～という感じ．
相手も英語話者以外に話すつもりでやってるからね．
講演者後方30cmを陣取れたのも良かった．
UllmanはHopcroftの講演中眼鏡を開いた状態でつるをつまんでくるくるしていたのがかわいかったし，そのときAhoは飲み終えた紙コップを口に押し付けて左右に回転させながらスリスリしていたのが最高だった．
明日（今日？）からは本 Advent Calendarも書いていくのでよろしく．
ネタはまだ考えてません．
adventar.org
