Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
WSDM 2016勉強会資料
Search
Shinichi Takayanagi
March 17, 2016
Research
1
1.1k
WSDM 2016勉強会資料
「WSDM 2016勉強会」(
https://atnd.org/events/74341)の担当箇所資料
。
Shinichi Takayanagi
March 17, 2016
Tweet
Share
More Decks by Shinichi Takayanagi
See All by Shinichi Takayanagi
[NeurIPS 2023 論文読み会] Wasserstein Quantum Monte Carlo
stakaya
0
390
[KDD2021 論文読み会] ControlBurn: Feature Selection by Sparse Forests
stakaya
2
1.8k
[ICML2021 論文読み会] Mandoline: Model Evaluation under Distribution Shift
stakaya
0
1.9k
[情報検索/推薦 各社合同 論文読み祭 #1] KDD ‘20 "Embedding-based Retrieval in Facebook Search"
stakaya
2
520
【2020年新人研修資料】ナウでヤングなPython開発入門
stakaya
28
20k
論文読んだ「Simple and Deterministic Matrix Sketching」
stakaya
1
970
Quick Introduction to Approximate Bayesian Computation (ABC) with R"
stakaya
3
260
The Road to Machine Learning Engineer from Data Scientist
stakaya
5
4k
論文読んだ「Winner’s Curse: Bias Estimation for Total Effects of Features in Online Controlled Experiments」
stakaya
1
4.5k
Other Decks in Research
See All in Research
一人称視点映像解析の基礎と応用(CVIMチュートリアル)
takumayagi
0
800
Off-Policy Evaluation of Slate Bandit Policies via Optimizing Abstraction(日本語版)
aiueola
0
120
LLM based AI Agents Overview -What, Why, How-
masatoto
1
120
20240710_熊本県議会・熊本市議会_都市交通勉強会
trafficbrain
0
560
[輪講資料] Text Embeddings by Weakly-Supervised Contrastive Pre-training
hpprc
3
720
ランサーズエージェント_フリーランスエンジニアの年収・キャリアの実態調査2024
lancers_pr
0
310
Mathematical Optimization +Artificial Intelligence =MOAI
mickey_kubo
1
230
SSII2024 [OS2] GPT-4Vで画像認識は終わるのか(オープニング)
ssii
PRO
0
640
SSII2024 [OS3] 企業における基盤モデル開発の実際
ssii
PRO
0
490
RCEへの近道
kawakatz
1
620
How to Perform Manual Classification for Deep Learning Using CloudCompare
kentaitakura
0
950
バスのサービスレベル向上と運賃策による熊本都市圏の渋滞緩和効果推計 ~公共交通への公的投資に向けた感度と集計QVに基づく迅速なシナリオ検討~
trafficbrain
0
180
Featured
See All Featured
BBQ
matthewcrist
82
9k
KATA
mclloyd
20
13k
Building Flexible Design Systems
yeseniaperezcruz
323
37k
Web Components: a chance to create the future
zenorocha
307
41k
Producing Creativity
orderedlist
PRO
340
39k
Writing Fast Ruby
sferik
623
60k
Fashionably flexible responsive web design (full day workshop)
malarkey
399
65k
Agile that works and the tools we love
rasmusluckow
325
20k
Optimising Largest Contentful Paint
csswizardry
18
2.6k
Rails Girls Zürich Keynote
gr2m
93
13k
Pencils Down: Stop Designing & Start Developing
hursman
118
11k
Gamification - CAS2011
davidbonilla
78
4.9k
Transcript
WSDM 2016勉強会 「Wiggins: Detecting Valuable Information in Dynamic Networks Using
Limited Resources」 Ahmad Mahmoody, Matteo Riondato, Eli Upfal 株式会社リクルートコミュニケーションズ ICTソリューション局アドテクノロジーサービス開発部 高柳慎一
モチベーション • 動的ネットワーク上での情報検知は有用 – 新しいWebページの検出 – 電気回路上での欠陥の伝搬 – 水の汚染の検出 •
情報がネットワーク上を伝搬していく • 情報を新規性のあるうちに見つけたい • 一方、全ノードを常に監視するのは難しい – 各時点において一部のノードを調査できる状況を考える • どうノードを調査すべきかの最適なスケジューリン グを考えたい 2
やったこと • 各種定義 – ネットワーク上での情報の生成と伝搬過程の定式化 • (明示的に書いてないけど)測度論ベース – スケジュールに沿ったノードの調査法の定義 –
異なるスケジュール間のコストを定義 • これらを最適調査計画問題(Optimal Probing Schedule Problem)として定義づける • 制約付の凸計画問題として定式化し、それを解くた めにWIGGINSというアルゴリズム提案 – MapReduce適用な形で提案 – WIGGINSってのはシャーロックホームズに出てくる諜報 機関?のリーダの名前らしい 3
2:問題の定式化 • グラフ構造: • ノード数: • ノードの部分集合族: • ある関数(確率): :
→ • グラフ上での情報生成・伝搬過程: – 時点tにおいて生成される情報(集合族): – あるノード部分集合 が に含まれる確率 • Sは論文中ではσ加法族と区別するために導入 – 単なるVの部分集合と考える、かつ、その生起確率を定義 • (t, S): “時点tに生成された情報が 手元にある る”を表現(アイテムと呼称) 4
2:問題の定式化 • “時点tにおいて調査する” =アイテム集合を得る • 過去に生成された情報の和集合: • 全時点ではc個のノードのみを調べる • :時点tより以前に取得
• :時点tにおいてまだここにない • 情報の新規性: • まだ見ぬ情報集合 によるLoad 5
• スケジュールpはノードV上の確率分布 • 時点tにおいてc個のうち 個ノードを選択 • コスト関数を定義(スケジュールpに依存!) • これを解く: (θ,
c)-OPSP – (θ, c)-Optimal Probing Schedule Problem – スケジュール集合: 6 2:問題の定式化
3: 関連研究 • 水汚染の検出[1, 13, 20, 24, 29] • 伝染病の検出[7]
• センサーのバッテリー消費最適化[11, 19, 21, 22] • SNS上での急伸トピックの検出[4, 25] • クローリング [8, 32] • ニュースフィードの更新[3, 15, 28, 30] 7
4:WIGGINSアルゴリズム • が既知の場合 • は凸関数 • 拘束条件付きの最適化問題として以下を解く 8
4:WIGGINSアルゴリズム 9
• 限られた(離散的な)情報しかわからない場合 • アルゴリズムはこの部分だけを変更する • Sごとにmapして計算(mapReduce) 10 4:WIGGINSアルゴリズム
5:数値実験 • Independent-Cascade (IC) model [17]を使用 • 生成(creation)フェイズ – ノード上に噂”rumor”を生成し、そのノードの出次数
(出 て行く辺数、outdegree, deg+)に応じて確率にbiasを付 けて生成を行わせる • 伝搬(diffusion)フェイズ – 確率1/伝搬先の入次数(入ってくる辺数indegree, deg-) で伝搬 11
• 他のベンチマーク的な方法 – 一様、out or indegree・接続数に比例で選択 • これらに比べてコスト関数が小さくなる 12 5:数値実験
• 一度最適化したもの に負荷を与える(灰 色箇所始端からノー ドの値をランダムに ひっくり返す) • 緑色箇所にてまた最 適化計算 13
5:数値実験
• ノイズの影響がまた消える 14 5:数値実験
まとめ • ネットワーク上での情報の生成と伝搬過程の定式化 • (明示的に書いてないけど)測度論ベース – スケジュールに沿ったノードの調査法の定義 – 異なるスケジュール間のコストを定義 •
これらを最適調査計画問題(Optimal Probing Schedule Problem)として定式化 • 制約付の凸計画問題として定式化し、それを解くた めにWIGGINSというアルゴリズム提案 • 数値検証実施 15