Session 20: Statistical Methods 【VLDB 2011勉強会】 Session 20: Statistical Methods 担当： 石川佳治(名大） Some figures are copied from VLDB 2011 proceedings.

Session 20: Statistical Methods 担当：石川（名大） Tuffy: Scaling up Statistical Inference in Markov Logic networks using an RDBMS Feng Niu, Christopher Ré, AnHai Doan, Jude Shavlik (U. Wisconsin-Madison) マルコフ論理ネットワーク（Markov logic network）におけ る大規模推論を可能とするためRDBMS技術を活用 マルコフ論理ネットワーク（P. Domingos / U. Washington) 論理型言語と確率的推論を統合：DB的に言うと，「ルールに 重みを入れたDatalog」 同じ論文には一般に同じ カテゴリが付与 ルール 重み cat(p, c1), cat(p, c2) => c1 = c2 5 wrote(x, p1), wrote(x, p2), cat(p1, c) => cat(p2, c) 1 cat(p1, c), refers(p1, p2) => cat(p2, c) 2 paper(p, u) => x. wrote(x, p) + cat(p, `Networking’) -1 同じ著者が書いた論文の カテゴリは同じことが多い 述語： paper(id, URL) wrote(author, paper) refers(paper, paper) cat(paper, category) 参照先論文のカテゴリは 参照論文と同じことが多い 論文には必ず著者がいる （ハードな制約） ネットワークに関する 論文はこのDBにはない Session 20: Statistical Methods 担当：石川（名大）

Session 20: Statistical Methods 担当：石川（名大） マルコフ論理ネットワークの概要 プログラムの評価 ・述語インスタンスをもとに，ルール　 　に基づいてネットワーク構築：グラフ構造は 　マルコフ確率場（MRF）に相当 ・MaxSATによる最大事後確率（MAP）推定： 　ヒューリスティックを利用（WalkSAT） refers(p1, p2) cat(p1, “DB”) cat(p2, “AI”) cat(p3, DB) wrote(“Mike”, p1) wrote(“Tom”, p2) wrote(“Tom”, p3) groundingフェーズ が重い! wrote refers cat paper Author Paper Mike p1 Tom p2 p3 … Paper p1 p2 … Paper Category p1 DB p2 AI p3 … PaperID URL … 2フェーズでの推論処理 1. grounding：グラフ構造を構築し， 　 大規模な重み付きSAT式を生成 2. search：SAT式に対する 低コストの重み（解）の割り当て Session 20: Statistical Methods 担当：石川（名大）

Session 20: Statistical Methods 担当：石川（名大） 本研究のアイデア 評価戦略の変更（groundingフェーズ） トップダウン評価（Prolog の証明戦略）から RDBMS を用いた ボトムアップ評価へ 7時間の grounding 処理（Alchemy）が2分（Tuffy）に 例：ルール wrote(x, p1), wrote(x, p2), cat(p1, c) => cat(p2, c) に対するSQL生成 Search フェーズの効率化 ①RDBMSと分担，②グラフを分解し部分問題を並列処理 プロトタイプ：http://research.cs.wisc.edu/hazy/tuffy/ 機械学習の専門家より：学習法のアプローチが古いかも SELECT w1.author, w1.paper, w2.paper, c1.category, c2.category FROM wrote w1, wrote w2, cat c1, cat c2 WHERE w1.author = w2.author AND w1.paper = c1.paper AND w2.paper = c2.paper Session 20: Statistical Methods 担当：石川（名大）

Dissemination of Models over Time-Varying Data Yongluan Zhou, Zografoula Vagena, Jonas Haustad (U. Southern Denmark / Rice U.) 時系列データ（株価，交通情報など）のネット配信 受信する各ユーザの要求はさまざま：生データが必要 or 要 約データでよい 解決策：モデルの配信 各ユーザの要求に応じて要約した時系列を送る P2P的な配信：各ユーザをノード（ピア）とする配信木 （dissemination tree）を構築 問題定義 無限に続く時系列データを配信 各ユーザは精度要求（accuracy requirement）を指定 Session 20: Statistical Methods 担当：石川（名大）

Session 20: Statistical Methods 担当：石川（名大） 手法の概略（１） 精度要求の尺度 近似の範囲を指定 [v – , v + ] ．．．他にもいろいろ可能 基本的には，精度要求の間に 全順序 ari < arj がつけばよい 配信システム 受信者（data receiver）をノードとした配信木をオーバーレイネ ットワーク上に構築 目的：時系列データに対する n 個のモデル {m1, …, mn}，各受 信者 nk の精度要求 ark，および配信木が与えられたとき，nk に対して適用できるモデルの集合 Mk を選択 時系列全体がカバーできるように Mk を選択 ネットワーク上を配信されるモデル数を最小化 Model Producer DR1 DR2 DR3 DR4 DR5 Session 20: Statistical Methods 担当：石川（名大）

Session 20: Statistical Methods 担当：石川（名大） 手法の概略（２） ここでいうモデルとは? 何でもよく，手法は問わない モデル mi はいくつかの時区間 をカバーして近似 近似精度 aij の間には全順序 が存在することのみ考慮 最適化のアプローチ ヒューリスティクスに基づく処理 枝刈り + クラスタリング 拡張：分散ルーティング 配信処理の制御を分散して実行 コメント：阪大西尾研のコメントを聞きたい [Fig 2 of VLDB 2011 paper] Session 20: Statistical Methods 担当：石川（名大）

Storing Matrices on Disk: Theory and Practice Revisited Yi Zhang, Kamesh Munagala, Jun Yang (Duke U.) 大規模な多次元配列のディスク上での管理方式 多様な応用（例：科学データベース，信号処理，数値計算）・ア クセスパターンに対応 更新処理に効率的に対応 配列のsparsityに適応的に対応：疎行列⇔密行列の変化に対 し追従 LAB-木 (Linearlized Array B-tree） B-木の構造に基づく配列データの管理 適応的なノード分割処理 バッチ的な更新 コメント：すごくちまちました話 Session 20: Statistical Methods 担当：石川（名大）

Session 20: Statistical Methods 担当：石川（名大） LAB-木の概要 離散データを対象 線形化（linearlization）関数による格納レイアウト指定 d 次元配列のデータを1次元にどのように並べるか，ユーザが 指定可能 デフォルト値（通常は0を設定）：データが挿入されていな いエントリにはデフォルト値が入っているように振舞う 配列要素へのアクセス方式 配列の添え字によるアクセス 線形化関数を指定することによる繰り返し（iteration）：LAB- 木構築時に指定した線形化関数と違うものを指定してもよい 矩形領域を指定してのread/write Session 20: Statistical Methods 担当：石川（名大）

Session 20: Statistical Methods 担当：石川（名大） 効率化のための工夫 ノード分割戦略 複数の戦略を比較検討（正直いって細かい） 空間の無駄がどの程度生じるか 処理時間 理論的な評価尺度 オフラインの最適戦略に対する競合比を理論的に解析 No-dead-spaceの性質があるか否か：将来の挿入がどうであっても 空のままの領域が生じうるときをいう バッチ的な更新処理 継続的な挿入はバッファ上のページに反映 どのタイミングでどのページをフラッシュするか いくつかの戦略を提案・比較 1 3 4 7 1 3 4 7 Session 20: Statistical Methods 担当：石川（名大）

Online Aggregation for Large MapReduce Jobs Niketan Pansare, Vinayak Borker, Chris Jermaine, Tyson Condie (Rice U. / UC Irvine / Yahoo! Research) オンライン集約（Online Aggregation; OLA） Joe Heller Stein, Peter Haasら：SIGMOD 2007 Test of Time Award受賞 問合せ処理とサンプリング＋統計的推定手法の組合せ 問合せ結果の推定値と信頼区間を提示：問合せ処理の進行 につれ精度が向上 – 満足した時点でユーザは問合せ終了可 例：SELECT avg(株価) from 株価DB where 企業 = ‘X’ 1分後に，95%の確率で [0, 2000] という推定値を提示 2分後に，95%の確率で [900, 1100] という推定値を提示 … 2時間後に問合せ処理終了：結果値 1000 を出力 Session 20: Statistical Methods 担当：石川（名大）

Session 20: Statistical Methods 担当：石川（名大） 研究の概要（１） MapReduce環境におけるオンライン集約 サンプリング＋集約処理はクラウド環境に向く ユーザはMapReduceのプログラムを記述：ただし，指定された プログラミングインタフェースを利用 システム側が展開して実行 実行モデルの定式化 オンライン集約の議論のために，MapReduceの実行処理を簡 略化して整理 データはブロック単位に分けられている ブロックはキューに入れられ，マッパーは次に処理するブロックを GetNext() で入手 ブロックのマッパーへの割り当てはスケジューラが担当 スナップショット処理：現時点の処理結果を集約 Session 20: Statistical Methods 担当：石川（名大）

Session 20: Statistical Methods 担当：石川（名大） 研究の概要（２） 統計処理の立場から見た問題 単一マシンの場合はランダムサンプルの取得は容易 ブロック単位の処理の場合，ブロックの処理時間と集約値の 間に相関が存在しうる 例：SUMの計算では，データ数の少ないブロックが早く終わるため， 推定値が小さくなる方にバイアスがかかる 解決策：値 xi，スケジュール時刻 tisch，処理の所要時間 tiproc の3パラメタからなる統計モデルを考える 例：スケジュールに5秒かかり，処理にこれまで125秒かかっているブ ロックに対する推定値を f(xi | tisci = 5, tiproc >= 125) と表現 ベイズ推定に基づく信頼区間の計算：理論的にはここがメイン Hyracks（ICDE 2011）における実装 パイプライン処理機能を活用，オンライン集約機能を入れる Session 20: Statistical Methods 担当：石川（名大）