Nonoptimality of the maximum-weight dependence tree in classification

Research output: Contribution to journalArticle

Abstract

Half a century ago, Chow and Liu proved that the distribution of the first-order dependence tree that optimally approximates an arbitrary joint distribution in terms of Kullback-Leibler cross entropy is the distribution of the maximum-weight dependence tree (MWDT). In a p -dimensional space, this is a tree with p-1 branches between pairs of variables with each branch having a weight equal to the mutual information between variables at both ends. Today, MWDTs have applications that are more important in classification than only being used to model first-order dependence structure among variables. Nevertheless, whether the MWDT is the optimal first-order tree in classification has been left unexplored so far. In this letter, we study the optimality of the MWDT structure from the stand-point of classification.

Original languageEnglish
Article number7782428
Pages (from-to)71-75
Number of pages5
JournalIEEE Signal Processing Letters
Volume24
Issue number1
DOIs
Publication statusPublished - Jan 1 2017

Fingerprint

Dependence Structure
First-order
Branch
Entropy
Cross-entropy
Tree Structure
Mutual Information
Joint Distribution
Optimality
Arbitrary
Model

Keywords

  • Bayes error
  • classification
  • first-order dependence tree
  • maximum-weight dependence tree (MWDT)

ASJC Scopus subject areas

  • Signal Processing
  • Applied Mathematics
  • Electrical and Electronic Engineering

Cite this

Nonoptimality of the maximum-weight dependence tree in classification. / Zollanvari, Amin.

In: IEEE Signal Processing Letters, Vol. 24, No. 1, 7782428, 01.01.2017, p. 71-75.

Research output: Contribution to journalArticle

@article{fa9e802466774b599cbbfc64a722ec52,
title = "Nonoptimality of the maximum-weight dependence tree in classification",
abstract = "Half a century ago, Chow and Liu proved that the distribution of the first-order dependence tree that optimally approximates an arbitrary joint distribution in terms of Kullback-Leibler cross entropy is the distribution of the maximum-weight dependence tree (MWDT). In a p -dimensional space, this is a tree with p-1 branches between pairs of variables with each branch having a weight equal to the mutual information between variables at both ends. Today, MWDTs have applications that are more important in classification than only being used to model first-order dependence structure among variables. Nevertheless, whether the MWDT is the optimal first-order tree in classification has been left unexplored so far. In this letter, we study the optimality of the MWDT structure from the stand-point of classification.",
keywords = "Bayes error, classification, first-order dependence tree, maximum-weight dependence tree (MWDT)",
author = "Amin Zollanvari",
year = "2017",
month = "1",
day = "1",
doi = "10.1109/LSP.2016.2639341",
language = "English",
volume = "24",
pages = "71--75",
journal = "IEEE Signal Processing Letters",
issn = "1070-9908",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "1",

}

TY - JOUR

T1 - Nonoptimality of the maximum-weight dependence tree in classification

AU - Zollanvari, Amin

PY - 2017/1/1

Y1 - 2017/1/1

N2 - Half a century ago, Chow and Liu proved that the distribution of the first-order dependence tree that optimally approximates an arbitrary joint distribution in terms of Kullback-Leibler cross entropy is the distribution of the maximum-weight dependence tree (MWDT). In a p -dimensional space, this is a tree with p-1 branches between pairs of variables with each branch having a weight equal to the mutual information between variables at both ends. Today, MWDTs have applications that are more important in classification than only being used to model first-order dependence structure among variables. Nevertheless, whether the MWDT is the optimal first-order tree in classification has been left unexplored so far. In this letter, we study the optimality of the MWDT structure from the stand-point of classification.

AB - Half a century ago, Chow and Liu proved that the distribution of the first-order dependence tree that optimally approximates an arbitrary joint distribution in terms of Kullback-Leibler cross entropy is the distribution of the maximum-weight dependence tree (MWDT). In a p -dimensional space, this is a tree with p-1 branches between pairs of variables with each branch having a weight equal to the mutual information between variables at both ends. Today, MWDTs have applications that are more important in classification than only being used to model first-order dependence structure among variables. Nevertheless, whether the MWDT is the optimal first-order tree in classification has been left unexplored so far. In this letter, we study the optimality of the MWDT structure from the stand-point of classification.

KW - Bayes error

KW - classification

KW - first-order dependence tree

KW - maximum-weight dependence tree (MWDT)

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

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

U2 - 10.1109/LSP.2016.2639341

DO - 10.1109/LSP.2016.2639341

M3 - Article

AN - SCOPUS:85015227217

VL - 24

SP - 71

EP - 75

JO - IEEE Signal Processing Letters

JF - IEEE Signal Processing Letters

SN - 1070-9908

IS - 1

M1 - 7782428

ER -