Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling

ICML 2016 best paper by Christopher De Sa, Kunle Olukotun, Christopher Ré

- http://icml.cc/2016/?page_id=2009

Transcript

1. RCO論文輪読会(2016/07/29) “Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling”(ICML 2016) Christopher De Sa, Kunle Olukotun, Christopher Ré ICTソリューション局アドテクノロジーサービス開発部 高柳慎一
2. （C）Recruit Communications Co., Ltd. Abstract 1
3. （C）Recruit Communications Co., Ltd. 1. Introduction 2
4. （C）Recruit Communications Co., Ltd. Gibbs samplingとは 3
5. （C）Recruit Communications Co., Ltd. ビッグデータ時代におけるGibbs samplingの弱点 4
6. （C）Recruit Communications Co., Ltd. 今回の中心となるアルゴリズム：HOGWILD! 5
7. （C）Recruit Communications Co., Ltd. この論文でやること 6
8. （C）Recruit Communications Co., Ltd. Total influence α 7
9. （C）Recruit Communications Co., Ltd. ここから先やること(詳細後述) 8
10. （C）Recruit Communications Co., Ltd. 2. Related Work 9
11. （C）Recruit Communications Co., Ltd. HOGWILD!-Gibbs sampling アルゴリズム 10
12. （C）Recruit Communications Co., Ltd. HOGWILD!-Gibbs sampling アルゴリズム 11
13. （C）Recruit Communications Co., Ltd. 3. Modeling Asynchronicity 12
14. （C）Recruit Communications Co., Ltd. 条件 13
15. （C）Recruit Communications Co., Ltd. 条件 14
16. （C）Recruit Communications Co., Ltd. 4. The First Challenge: Bias 15
17. （C）Recruit Communications Co., Ltd. Total Variance Distance(以下、TVと呼称) 16
18. （C）Recruit Communications Co., Ltd. Gibbs samplingの場合 17
19. （C）Recruit Communications Co., Ltd. 4.1. Bias Example 18
20. （C）Recruit Communications Co., Ltd. 4.1. Bias Example 19
21. （C）Recruit Communications Co., Ltd. 4.1. Bias Example 20
22. （C）Recruit Communications Co., Ltd. 4.2. Bounding the Bias 21
23. （C）Recruit Communications Co., Ltd. Sparse Variation Distance(以下、SVと呼称) 22
24. （C）Recruit Communications Co., Ltd. Sparse Variation Distance 23
25. （C）Recruit Communications Co., Ltd. Sparse Estimation Time 24
26. （C）Recruit Communications Co., Ltd. Total Influence 25
27. （C）Recruit Communications Co., Ltd. Claim1 (詳細な証明はArxivの論文見ないとダメ) 26
28. （C）Recruit Communications Co., Ltd. Claim1を証明するための定理 27
29. （C）Recruit Communications Co., Ltd. 定理1 28
30. （C）Recruit Communications Co., Ltd. 定理2 29
31. （C）Recruit Communications Co., Ltd. 5. The Second Challenge: Mixing Times 30
32. （C）Recruit Communications Co., Ltd. 5.1. Mixing Time Example 31
33. （C）Recruit Communications Co., Ltd. 5.1. Mixing Time Example 32
34. （C）Recruit Communications Co., Ltd. 5.2. Bounding the Mixing Time 33 ※前述の例は Dobrushin’s条 件を満たしてい ない例なのでこ この定理とは無 矛盾
35. （C）Recruit Communications Co., Ltd. 5.2. Bounding the Mixing Time 34
36. （C）Recruit Communications Co., Ltd. 5.3. A Positive Example: Ising Model 35
37. （C）Recruit Communications Co., Ltd. 5.4. Proof Outline 36
38. （C）Recruit Communications Co., Ltd. 6. Experiments 37
39. （C）Recruit Communications Co., Ltd. 6. Experiments 38
40. （C）Recruit Communications Co., Ltd. 7. Conclusion 39