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

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

Fingerprint Dive into the research topics of 'Nonoptimality of the maximum-weight dependence tree in classification'. Together they form a unique fingerprint.

  • Cite this