A backward selection procedure for approximating a discrete probability distribution by decomposable models

Title:

A backward selection procedure for approximating a discrete probability distribution by decomposable models

Creator:

Malvestuto, Francesco M.

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:a4b3efc4-7e19-49bb-afd9-0ef90e5d7fb5
uuid:a4b3efc4-7e19-49bb-afd9-0ef90e5d7fb5

Subject:

backward selection, information divergence, decomposable model, acyclic hypergraph, and k-hypertree

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

Decomposable (probabilistic) models are log-linear models generated by acyclic hypergraphs, and a number of nice properties enjoyed by them are known. In many applications the following selection problem naturally arises: given a probability distribution p over a finite set V of n discrete variables and a positive integer k, find a decomposable model with tree-width k that best fits p. If H is the generating hypergraph of a decomposable model and pH is the estimate of p under the model, we can measure the closeness of pH to p by the information divergence D(p:pH), so that the problem above reads: given p and k, find an acyclic, connected hypergraph H of tree-width k such that D(p:pH) is minimum. It is well-known that this problem is NP-hard. However, for k=1 it was solved by Chow and Liu in a very efficient way; thus, starting from an optimal Chow-Liu solution, a few forward-selection procedures have been proposed with the aim at finding a `good' solution for an arbitrary k. We propose a backward-selection procedure which starts from the (trivial) optimal solution for k=n−1, and we show that, in a study case taken from literature, our procedure succeeds in finding an optimal solution for every k. .

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

[825]-844

Source:

Kybernetika | 2012 Volume:48 | Number:5

Harvested from:

CDK

Metadata only:

false