Generalized Direct Change Estimation in Ising Model Structure

Farideh Fazayeli, Arindam Banerjee
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2281-2290, 2016.

Abstract

We consider the problem of estimating change in the dependency structure of two p-dimensional Ising models, based on respectively n_1 and n_2 samples drawn from the models. The change is assumed to be structured, e.g., sparse, block sparse, node-perturbed sparse, etc., such that it can be characterized by a suitable (atomic) norm. We present and analyze a norm-regularized estimator for directly estimating the change in structure, without having to estimate the structures of the individual Ising models. The estimator can work with any norm, and can be generalized to other graphical models under mild assumptions. We show that only one set of samples, say n_2, needs to satisfy the sample complexity requirement for the estimator to work, and the estimation error decreases as \fracc\sqrt\min(n_1,n_2), where c depends on the Gaussian width of the unit norm ball. For example, for \ell_1 norm applied to s-sparse change, the change can be accurately estimated with \min(n_1,n_2)=O(s \log p) which is sharper than an existing result n_1= O(s^2 \log p) and n_2 = O(n_1^2). Experimental results illustrating the effectiveness of the proposed estimator are presented.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-fazayeli16, title = {Generalized Direct Change Estimation in Ising Model Structure}, author = {Fazayeli, Farideh and Banerjee, Arindam}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2281--2290}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/fazayeli16.pdf}, url = {https://proceedings.mlr.press/v48/fazayeli16.html}, abstract = {We consider the problem of estimating change in the dependency structure of two p-dimensional Ising models, based on respectively n_1 and n_2 samples drawn from the models. The change is assumed to be structured, e.g., sparse, block sparse, node-perturbed sparse, etc., such that it can be characterized by a suitable (atomic) norm. We present and analyze a norm-regularized estimator for directly estimating the change in structure, without having to estimate the structures of the individual Ising models. The estimator can work with any norm, and can be generalized to other graphical models under mild assumptions. We show that only one set of samples, say n_2, needs to satisfy the sample complexity requirement for the estimator to work, and the estimation error decreases as \fracc\sqrt\min(n_1,n_2), where c depends on the Gaussian width of the unit norm ball. For example, for \ell_1 norm applied to s-sparse change, the change can be accurately estimated with \min(n_1,n_2)=O(s \log p) which is sharper than an existing result n_1= O(s^2 \log p) and n_2 = O(n_1^2). Experimental results illustrating the effectiveness of the proposed estimator are presented.} }
Endnote
%0 Conference Paper %T Generalized Direct Change Estimation in Ising Model Structure %A Farideh Fazayeli %A Arindam Banerjee %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-fazayeli16 %I PMLR %P 2281--2290 %U https://proceedings.mlr.press/v48/fazayeli16.html %V 48 %X We consider the problem of estimating change in the dependency structure of two p-dimensional Ising models, based on respectively n_1 and n_2 samples drawn from the models. The change is assumed to be structured, e.g., sparse, block sparse, node-perturbed sparse, etc., such that it can be characterized by a suitable (atomic) norm. We present and analyze a norm-regularized estimator for directly estimating the change in structure, without having to estimate the structures of the individual Ising models. The estimator can work with any norm, and can be generalized to other graphical models under mild assumptions. We show that only one set of samples, say n_2, needs to satisfy the sample complexity requirement for the estimator to work, and the estimation error decreases as \fracc\sqrt\min(n_1,n_2), where c depends on the Gaussian width of the unit norm ball. For example, for \ell_1 norm applied to s-sparse change, the change can be accurately estimated with \min(n_1,n_2)=O(s \log p) which is sharper than an existing result n_1= O(s^2 \log p) and n_2 = O(n_1^2). Experimental results illustrating the effectiveness of the proposed estimator are presented.
RIS
TY - CPAPER TI - Generalized Direct Change Estimation in Ising Model Structure AU - Farideh Fazayeli AU - Arindam Banerjee BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-fazayeli16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2281 EP - 2290 L1 - http://proceedings.mlr.press/v48/fazayeli16.pdf UR - https://proceedings.mlr.press/v48/fazayeli16.html AB - We consider the problem of estimating change in the dependency structure of two p-dimensional Ising models, based on respectively n_1 and n_2 samples drawn from the models. The change is assumed to be structured, e.g., sparse, block sparse, node-perturbed sparse, etc., such that it can be characterized by a suitable (atomic) norm. We present and analyze a norm-regularized estimator for directly estimating the change in structure, without having to estimate the structures of the individual Ising models. The estimator can work with any norm, and can be generalized to other graphical models under mild assumptions. We show that only one set of samples, say n_2, needs to satisfy the sample complexity requirement for the estimator to work, and the estimation error decreases as \fracc\sqrt\min(n_1,n_2), where c depends on the Gaussian width of the unit norm ball. For example, for \ell_1 norm applied to s-sparse change, the change can be accurately estimated with \min(n_1,n_2)=O(s \log p) which is sharper than an existing result n_1= O(s^2 \log p) and n_2 = O(n_1^2). Experimental results illustrating the effectiveness of the proposed estimator are presented. ER -
APA
Fazayeli, F. & Banerjee, A.. (2016). Generalized Direct Change Estimation in Ising Model Structure. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2281-2290 Available from https://proceedings.mlr.press/v48/fazayeli16.html.

Related Material