Beyond maximum likelihood: Boosting the Chow-Liu algorithm for large alphabets

Jiantao Jiao; Yanjun Han; Tsachy Weissman

doi:10.1109/ACSSC.2016.7869051

Beyond maximum likelihood: Boosting the Chow-Liu algorithm for large alphabets

Jiantao Jiao, Yanjun Han, Tsachy Weissman

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We show that in high dimensional distributions, i.e., the regime where the alphabet size of each node is comparable to the number of observations, the Chow-Liu algorithm on learning graphical models is highly sub-optimal. We propose a new approach, where the key ingredient is to replace the empirical mutual information in the Chow-Liu algorithm with a minimax rate-optimal estimator proposed recently by Jiao, Venkat, Han, and Weissman [1]. We demonstrate the improved performance of the new approach in two problems: learning tree graphical models and Bayesian network classification.

Original language	English (US)
Title of host publication	Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016
Editors	Michael B. Matthews
Publisher	IEEE Computer Society
Pages	321-325
Number of pages	5
ISBN (Electronic)	9781538639542
DOIs	https://doi.org/10.1109/ACSSC.2016.7869051
State	Published - Mar 1 2017
Event	50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 - Pacific Grove, United States Duration: Nov 6 2016 → Nov 9 2016

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)	1058-6393

Other

Other	50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016
Country/Territory	United States
City	Pacific Grove
Period	11/6/16 → 11/9/16

Keywords

Chow-Liu algorithm
approximation theory
high dimensional statistics
mutual information estimation
nonsmooth functional estimation

ASJC Scopus subject areas

Signal Processing
Computer Networks and Communications

Access to Document

10.1109/ACSSC.2016.7869051

Cite this

Jiao, J., Han, Y., & Weissman, T. (2017). Beyond maximum likelihood: Boosting the Chow-Liu algorithm for large alphabets. In M. B. Matthews (Ed.), Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 (pp. 321-325). Article 7869051 (Conference Record - Asilomar Conference on Signals, Systems and Computers). IEEE Computer Society. https://doi.org/10.1109/ACSSC.2016.7869051

Beyond maximum likelihood: Boosting the Chow-Liu algorithm for large alphabets. / Jiao, Jiantao; Han, Yanjun; Weissman, Tsachy.
Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. ed. / Michael B. Matthews. IEEE Computer Society, 2017. p. 321-325 7869051 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Jiao, J, Han, Y & Weissman, T 2017, Beyond maximum likelihood: Boosting the Chow-Liu algorithm for large alphabets. in MB Matthews (ed.), Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016., 7869051, Conference Record - Asilomar Conference on Signals, Systems and Computers, IEEE Computer Society, pp. 321-325, 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016, Pacific Grove, United States, 11/6/16. https://doi.org/10.1109/ACSSC.2016.7869051

Jiao J, Han Y, Weissman T. Beyond maximum likelihood: Boosting the Chow-Liu algorithm for large alphabets. In Matthews MB, editor, Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. IEEE Computer Society. 2017. p. 321-325. 7869051. (Conference Record - Asilomar Conference on Signals, Systems and Computers). doi: 10.1109/ACSSC.2016.7869051

Jiao, Jiantao ; Han, Yanjun ; Weissman, Tsachy. / Beyond maximum likelihood : Boosting the Chow-Liu algorithm for large alphabets. Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. editor / Michael B. Matthews. IEEE Computer Society, 2017. pp. 321-325 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

@inproceedings{70b01b9f5699439c90089fe944397f33,

title = "Beyond maximum likelihood: Boosting the Chow-Liu algorithm for large alphabets",

abstract = "We show that in high dimensional distributions, i.e., the regime where the alphabet size of each node is comparable to the number of observations, the Chow-Liu algorithm on learning graphical models is highly sub-optimal. We propose a new approach, where the key ingredient is to replace the empirical mutual information in the Chow-Liu algorithm with a minimax rate-optimal estimator proposed recently by Jiao, Venkat, Han, and Weissman [1]. We demonstrate the improved performance of the new approach in two problems: learning tree graphical models and Bayesian network classification.",

keywords = "Chow-Liu algorithm, approximation theory, high dimensional statistics, mutual information estimation, nonsmooth functional estimation",

author = "Jiantao Jiao and Yanjun Han and Tsachy Weissman",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 ; Conference date: 06-11-2016 Through 09-11-2016",

year = "2017",

month = mar,

day = "1",

doi = "10.1109/ACSSC.2016.7869051",

language = "English (US)",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

publisher = "IEEE Computer Society",

pages = "321--325",

editor = "Matthews, {Michael B.}",

booktitle = "Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016",

}

TY - GEN

T1 - Beyond maximum likelihood

T2 - 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016

AU - Jiao, Jiantao

AU - Han, Yanjun

AU - Weissman, Tsachy

PY - 2017/3/1

Y1 - 2017/3/1

N2 - We show that in high dimensional distributions, i.e., the regime where the alphabet size of each node is comparable to the number of observations, the Chow-Liu algorithm on learning graphical models is highly sub-optimal. We propose a new approach, where the key ingredient is to replace the empirical mutual information in the Chow-Liu algorithm with a minimax rate-optimal estimator proposed recently by Jiao, Venkat, Han, and Weissman [1]. We demonstrate the improved performance of the new approach in two problems: learning tree graphical models and Bayesian network classification.

AB - We show that in high dimensional distributions, i.e., the regime where the alphabet size of each node is comparable to the number of observations, the Chow-Liu algorithm on learning graphical models is highly sub-optimal. We propose a new approach, where the key ingredient is to replace the empirical mutual information in the Chow-Liu algorithm with a minimax rate-optimal estimator proposed recently by Jiao, Venkat, Han, and Weissman [1]. We demonstrate the improved performance of the new approach in two problems: learning tree graphical models and Bayesian network classification.

KW - Chow-Liu algorithm

KW - approximation theory

KW - high dimensional statistics

KW - mutual information estimation

KW - nonsmooth functional estimation

UR - http://www.scopus.com/inward/record.url?scp=85016280955&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016280955&partnerID=8YFLogxK

U2 - 10.1109/ACSSC.2016.7869051

DO - 10.1109/ACSSC.2016.7869051

M3 - Conference contribution

AN - SCOPUS:85016280955

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 321

EP - 325

BT - Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016

A2 - Matthews, Michael B.

PB - IEEE Computer Society

Y2 - 6 November 2016 through 9 November 2016

ER -

Beyond maximum likelihood: Boosting the Chow-Liu algorithm for large alphabets

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this