Structural Change Detection (last update: Nov.28.2013)

   

Introduction

We provide the MATLAB(R) code of the algorithm for direct structural changes detection in Markov netwoks (Liu, et al., 2013). The code does the following work automatically:

  • Sample 500 points from 50 dimensional multivariate Gaussian distribution P with random correlation among random varibales.

  • Sample another 500 points from a altered distribution Q which is obtained by randomly weakening 18 pairwise correlation from P.

  • Perform structural change detection using the proposed method described in Liu, et al. 2013, and visualize the regularization path.

This package require minFunc and minConF to run, please download them and include it to your MATLAB(R) path.

This distribution is under GPL license.

The Problem Setting and Optimization

Given two sets of samples {mathbf{x}^P}_{i = 1}^{n^P} sim P, {mathbf{x}^Q}_{i = 1}^{n^Q} sim Q, we are solving the following problem:

 	mathrm{argmin}_{mathbf{theta}} logsum_{i=1}^{n^Q}mathrm{exp}left( sum_{t}mathbf{theta}_t^top f_t(mathbf{x}^Q_i) right) - frac{1}{n^P}sum_i^{n^P}sum_t mathbf{theta}_t^top f_t(mathbf{x}^P_i) + lambda_1 |mathbf{theta}|_2^2 + lambda_2 sum_t | mathbf{theta}_t |_2

where f is a function basis, which is polynomial basis in this implementation and t indexes each uni/pairwise factors in Markov Networks.

For detailed explanation of optimization problem, please see Liu et al., 2013.

Download

Primal and Dual Program (New! Nov.28.2013)

Results

Run the script named “demo.m (or demo_dual.m)”, you should be able to see the following charts (dual is significantly faster):

700 
700 

Reference

Liu, S., Quinn, J. A., Gutmann, M. U., Sugiyama, M.,
Direct Learning of Sparse Changes in Markov Networks by Density Ratio Estimation.,
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD 2013). to appear

Acknowledgements

Thanks Mark Schmidt for making his minFunc and minConF packages available online.

Song Liu (song@sg.cs.titech.ac.jp)