| Presentation | 2014-11-18 Support Consistency of Direct Sparse-Change Learning in Markov Networks Song LIU, Taiji SUZUKI, Masashi SUGIYAMA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We study the problem of learning sparse structure changes between two Markov networks P and Q. Rather than fitting two Markov networks separately to two sets of data and figuring out their differences, a recent work proposed to learn changes directly via estimating the ratio between two Markov network models. Such a direct approach was demonstrated to perform excellently in experiments, although its theoretical properties remained unexplored. In this paper, we give sufficient conditions for successful change detection with respect to the sample size n_p, n_q, the dimension of data m, and the number of changed edges d. More specifically, we prove that the true sparse changes can be consistently identified for n_p=Ω(d^2 log(m^2+m)/2) and n_q=Ω(n^2_p/d), with an exponentially decaying upper-bound on learning error. Our theoretical guarantee can be applied to a wide range of discrete/continuous Markov networks. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Density Ratio Estimation / Change Detection / Markov Network |
| Paper # | IBISML2014-70 |
| Date of Issue |
| Conference Information | |
| Committee | IBISML |
|---|---|
| Conference Date | 2014/11/10(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information-Based Induction Sciences and Machine Learning (IBISML) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Support Consistency of Direct Sparse-Change Learning in Markov Networks |
| Sub Title (in English) | |
| Keyword(1) | Density Ratio Estimation |
| Keyword(2) | Change Detection |
| Keyword(3) | Markov Network |
| 1st Author's Name | Song LIU |
| 1st Author's Affiliation | Department of Computer Science, Tokyo Institute of Technology() |
| 2nd Author's Name | Taiji SUZUKI |
| 2nd Author's Affiliation | Department of Mathematical and Computing Sciences, Tokyo Institute of Technology |
| 3rd Author's Name | Masashi SUGIYAMA |
| 3rd Author's Affiliation | Department of Complexity Science and Engineering, University of Tokyo |
| Date | 2014-11-18 |
| Paper # | IBISML2014-70 |
| Volume (vol) | vol.114 |
| Number (no) | 306 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |