Unfolding Latent Tree Structures using 4th Order Tensors

Mariya Ishteva, Haesun Park, Le Song
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):316-324, 2013.

Abstract

Discovering the latent structure from many observed variables is an important yet challenging learning task. Existing approaches for discovering latent structures often require the unknown number of hidden states as an input. In this paper, we propose a quartet based approach which is agnostic to this number. The key contribution is a novel rank characterization of the tensor associated with the marginal distribution of a quartet. This characterization allows us to design a nuclear norm based test for resolving quartet relations. We then use the quartet test as a subroutine in a divide-and-conquer algorithm for recovering the latent tree structure. Under mild conditions, the algorithm is consistent and its error probability decays exponentially with increasing sample size. We demonstrate that the proposed approach compares favorably to alternatives. In a real world stock dataset, it also discovers meaningful groupings of variables, and produces a model that fits the data better.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-ishteva13, title = {Unfolding Latent Tree Structures using 4th Order Tensors}, author = {Ishteva, Mariya and Park, Haesun and Song, Le}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {316--324}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/ishteva13.pdf}, url = {https://proceedings.mlr.press/v28/ishteva13.html}, abstract = {Discovering the latent structure from many observed variables is an important yet challenging learning task. Existing approaches for discovering latent structures often require the unknown number of hidden states as an input. In this paper, we propose a quartet based approach which is agnostic to this number. The key contribution is a novel rank characterization of the tensor associated with the marginal distribution of a quartet. This characterization allows us to design a nuclear norm based test for resolving quartet relations. We then use the quartet test as a subroutine in a divide-and-conquer algorithm for recovering the latent tree structure. Under mild conditions, the algorithm is consistent and its error probability decays exponentially with increasing sample size. We demonstrate that the proposed approach compares favorably to alternatives. In a real world stock dataset, it also discovers meaningful groupings of variables, and produces a model that fits the data better.} }
Endnote
%0 Conference Paper %T Unfolding Latent Tree Structures using 4th Order Tensors %A Mariya Ishteva %A Haesun Park %A Le Song %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-ishteva13 %I PMLR %P 316--324 %U https://proceedings.mlr.press/v28/ishteva13.html %V 28 %N 3 %X Discovering the latent structure from many observed variables is an important yet challenging learning task. Existing approaches for discovering latent structures often require the unknown number of hidden states as an input. In this paper, we propose a quartet based approach which is agnostic to this number. The key contribution is a novel rank characterization of the tensor associated with the marginal distribution of a quartet. This characterization allows us to design a nuclear norm based test for resolving quartet relations. We then use the quartet test as a subroutine in a divide-and-conquer algorithm for recovering the latent tree structure. Under mild conditions, the algorithm is consistent and its error probability decays exponentially with increasing sample size. We demonstrate that the proposed approach compares favorably to alternatives. In a real world stock dataset, it also discovers meaningful groupings of variables, and produces a model that fits the data better.
RIS
TY - CPAPER TI - Unfolding Latent Tree Structures using 4th Order Tensors AU - Mariya Ishteva AU - Haesun Park AU - Le Song BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-ishteva13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 316 EP - 324 L1 - http://proceedings.mlr.press/v28/ishteva13.pdf UR - https://proceedings.mlr.press/v28/ishteva13.html AB - Discovering the latent structure from many observed variables is an important yet challenging learning task. Existing approaches for discovering latent structures often require the unknown number of hidden states as an input. In this paper, we propose a quartet based approach which is agnostic to this number. The key contribution is a novel rank characterization of the tensor associated with the marginal distribution of a quartet. This characterization allows us to design a nuclear norm based test for resolving quartet relations. We then use the quartet test as a subroutine in a divide-and-conquer algorithm for recovering the latent tree structure. Under mild conditions, the algorithm is consistent and its error probability decays exponentially with increasing sample size. We demonstrate that the proposed approach compares favorably to alternatives. In a real world stock dataset, it also discovers meaningful groupings of variables, and produces a model that fits the data better. ER -
APA
Ishteva, M., Park, H. & Song, L.. (2013). Unfolding Latent Tree Structures using 4th Order Tensors. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):316-324 Available from https://proceedings.mlr.press/v28/ishteva13.html.

Related Material