情報爆発時代における理論と実際 理論研究の現実の場での応用例： 講演者の経験から 徳山 豪 東北大学情報科学研究科 目次 理論研究者と実用研究：成功の例 講演者の体験例 理論研究者と実用研究者の理想的な協力体制 インターネットでのGoogle検索 明らかに実用研究 「徳山 豪」での検索： ヒット104,000 – ほとんどは私と無関係 – “重要な”ページ順に並べて見せてくれる – 同じようなページは重複させない 理論研究者と実用研究 Monika Henzinger （Research Director of Google) の成功例（ACM-SIAM SODA2007) Combinatorial Algorithms for Web Search Engines： Three Success Stories – HyperLink Analysis – Near Duplicate Web Page Detection – Index Server Load Balancing 理論で得た手法を基盤に、実験と理論の双方 を駆使して、実用的なものに転換する 情報爆発時代：理論研究者へのニーズがある Henzingerの成功例その１ HyperLink Analysis – ページランク （S. Brin, L. Page + R. Motwani ら） WEBページにスコアをつける（リンク構造を確率過程と見て） – HITS： （J. Kleinberg, P. Raghavan) WEBから｢オーソリティー」と「ハブ」からなるコミュニティー（高濃度 二部グラフ）を抽出する – アルゴリズムの評価とWEB構造解析の改善（Henzinger) Who Links to Whom: Mining Linkage between Web Sites. ICDM 2001 Query-free news search. WWW 2003: 1-10 成功例その２ Near Duplicate Web Page Detection – 似ているページを探して検索出力を減らす 高速近似パターンマッチング – 2つの理論的手法：ランダム丸めと次元射影 理論の専門家でないと読めないような論文 – 両方とも実用的でない。なぜか？どうするか？ – 理論→実験→理論→実験→実用 Henzinger: Finding near-duplicate web pages: a large-scale evaluation of algorithms（SIGIR2006). Henzinger氏の研究の変遷 動的グラフのデータ構造（二連結成分、サイクル構造、頂点連結度など） （FOCS92、94、95，96、98、STOC95) 平面グラフの最短路アルゴリズム（STOC94） オンライン探索問題（STOC97) アルゴリズムの中心的な 未解決問題へのチャレンジ WEB上のInformation Retrieval （FOCS98) ネットワーク上のデータ転送スケジューリング（STOC99) WWW上のミラーホスト検出（WOWS99) 実世界での中心的な 問題へのチャレンジ Who Links to Whom: Mining Linkage between Web Sites (ICDM01) 重複WEBページの検出 （SIGIR06) 意欲的な理論研究の経験を持った学者が 実用研究を行うと大きな成果が出る 講演者自身の経験 理論： 計算幾何学、組合せ最適化 – 離散数学を中心にした数学 応用の2つの例： – データマイニング – 電子商取引でのオンラインアルゴリズム 環境： – IBM東京基礎研究所 計算理論関係の相談窓口のような立場 今思うと非常に良い環境 データマイニング 画像処理のイメージ切り出しの論文を(社内審査で）読 んだMさんが「すごい勢い」でやってくる (1995年） – Mさん： スタンフォード大学Ullman教授の元で博士号を 取ったデータベースの研究者 データマイニングという新しい分野への応用 毎月新しいテーマと新しい成果が出る – SIGMOD,PODS,VLDB，KDDなど 優秀な若手研究員によるシステム作り ｢初めての計算理論のデータマイニングへの利用」 – その後、世界的に多くの理論研究者がデータマイニングに 取り組んだ事を思うと、きっかけとしての価値が高い 成功の理由 二人ともすごく本気になった – 興味と知識が適度に交わり、意思の疎通がスムーズ – 企業研究者として、必要に迫られていた 人間関係 – 席も近く、毎日お昼にコントラクトブリッジを楽しむ間柄 理論→実験→理論→実験→の理想的なサイクル – すばやいシステム作り (基礎研究所の環境） – デモとお客様からのフィードバック 新しい分野で世界の最先端に触れていたこと – データマイニング： 1993年のR.Agrawalらの論文が発端 – スタンフォードのウルマン教授の研究グループ – IBMアルマデン研究所（R. Agrawal、P. Raghavan） 電子商取引でのオンラインアルゴリズム ネットワークとセキュリティーの専門家のKさんが訪れてくる （1998年春） 「徳山さん、個々のユーザがどんなWEBサーバを訪れるかを 顧客データベースからデータマイニングできない？？」 ｢いったい何に使うの？」 ｢実は電子課金システムを作っていて、サーバ間通信を減らしたい」 プリペイド型 Pay-Per-Click システム： ユーザはあらかじめお金をプリペイして、決まったユニット数の買い物ができる。 課金クリックするごとに前払い金が減る。 問題： ユーザはｋ個のサーバで買い物をする。 前払い金をk個のサーバに分 散しておき、お金がなくなったサーバには他のサーバから送金する。 送金回数を最小化するにはどのようにお金を分配すればいいか？ ｢これはデータマイニングではなくて、オンライン問題 だよね。」 成果と反省 理論： Pay-Per-Click での送金の最適オンラインア ルゴリズム （ACM-SIAM SODAなど) – まずまずの成功 実用： ビジネスモデルとして採択されなかった – 残念だが良くあること 失敗したと思うこと： 研究を継続しなかったこと – – – – WEBで顧客の嗜好をマイニングする クリックベースの課金システム 1998年段階では先進的なアイデア 研究のためのリソースと技術もあった 理論と実用の理想的な環境 Googleが生まれてくる下地 スタンフォード大学 Ullman研究室（１９９７当時） – 教授： J. Ullman (広い知見の世界的な権威） – 助教授： R. Motwani (計算理論の最先端） 最近(現在は主任教授）ではDBと計算理論の両刀 – 理論学生(現在のDBLP論文数）： S. Khanna(99）, P. Indyk(93), C. Chekuri(62), S. Venkatsuburamanian(34) みんなモダントピックで活躍している – 応用系学生： S. Brin, L. Page（Googleの創始者）など – 客員： P. Raghavanなど多数 まとめの代わりに：世界の流れ 情報爆発時代：優秀な理論研究者が応用分野に参入する – – – – M. Henzinger （Google) P. Raghavan (Yahoo Research, Director) フィクサーの役目 J. Kleinberg （Cornel, 2006年ネバリンナ賞受賞者） R. Motwani （Stanford) など 理論手法の導入による新しい実用手法 – – 情報爆発を計算理論で制御する HITS検索エンジン、ストリームアルゴリズム、データマイニング手法など 理論の一つの分野を新しく立ち上げる – 理論分野の活性化→学生の意識の改革 研究者は理論に戻ってくる – 理論ほど面白いものはないから！
© Copyright 2024 ExpyDoc
