1 of 23

Learning with Tree-averaged Densities and Distributions

Sergey Kirshner

Alberta Ingenuity Centre for Machine Learning,

Department of Computing Science,

University of Alberta, Canada

December 5, 2007

NIPS 2007

Poster W12

2 of 23

Overview

Want to fit density to complete multivariate data

New density estimation model based on averaging over tree-dependence structures

Distribution = Univariate Marginals + Copula
Bayesian averaging over tree-structured copulas
Efficient parameter estimation for tree-averaged copulas

Can solve problems with 10-30 dimensions

Learning with Tree-averaged Densities and Distributions

NIPS 2007

I am addressing a problem of fitting a probability density function to complete multivariate real-valued data.

I am proposing a new density estimation model obtained by averaging over dependence structure. This model utilizes copulas, a concept well-known in multivariate statistics, but little used in machine learning. Each multivariate distribution can be decomposed into its univariate marginals and a copula, a multivariate distribution capturing all of the dependence between the variables. I will define tree-structured copulas and employ Bayesian framework over the tree-structures to compute (in closed form) the Bayesian model average over such models. I then obtain an EM algorithm to estimate the parameters for the resulting tree-averaged density. Resulting optimization is quite efficient. In my experiments, I applied this model to datasets of moderate dimensionality (10-30).

3 of 23

4 of 23

What If the Data Is NOT Gaussian?

Learning with Tree-averaged Densities and Distributions

NIPS 2007

5 of 23

Curse of Dimensionality

Learning with Tree-averaged Densities and Distributions

NIPS 2007

1/n

n^d cells

V_[-2,2]d ≈ 0.9545^d

[Bellman 57]

6 of 23

Avoiding the Curse: Step 1�Separating Univariate Marginals

Learning with Tree-averaged Densities and Distributions

NIPS 2007

univariate marginals,

independent variables,

multivariate dependence term,

copula

7 of 23

Monotonic Transformation of the Variables

Learning with Tree-averaged Densities and Distributions

NIPS 2007

8 of 23

Copula

Learning with Tree-averaged Densities and Distributions

NIPS 2007

Copula C is a multivariate distribution (cdf) defined on a unit hypercube with uniform univariate marginals:

9 of 23

Sklar’s Theorem

Learning with Tree-averaged Densities and Distributions

NIPS 2007

[Sklar 59]

10 of 23

Example: Bivariate Gaussian Copula

Learning with Tree-averaged Densities and Distributions

NIPS 2007

11 of 23

Useful Properties of Copulas

Preserves concordance between the variables

Rank-based measure of dependence

Preserves mutual information

Can be viewed as a canonical form of a multivariate distribution for the purpose of the estimation of multivariate dependence

Learning with Tree-averaged Densities and Distributions

NIPS 2007

12 of 23

Copula Density

Learning with Tree-averaged Densities and Distributions

NIPS 2007

13 of 23

Separating Univariate Marginals

Fit univariate marginals (parametric or non-parametric)
Replace data points with cdf’s of the marginals
Estimate copula density

Learning with Tree-averaged Densities and Distributions

NIPS 2007

Inference for the margins [Joe and Xu 96]; canonical maximum likelihood [Genest et al 95]

14 of 23

What Next?

Aren’t we back to square one?

Still estimating multivariate density from data

Not quite

All marginals are fixed
Lots of approaches for copulas

Vast majority focus on bivariate case

Design models that use only pairs of variables

Learning with Tree-averaged Densities and Distributions

NIPS 2007

15 of 23

Tree-Structured Densities

Learning with Tree-averaged Densities and Distributions

NIPS 2007

x₂

x₃

x₄

x₅

x₆

x₁

16 of 23

Tree-Structured Copulas

Learning with Tree-averaged Densities and Distributions

NIPS 2007

17 of 23

Chow-Liu Algorithm (for Copulas)

Learning with Tree-averaged Densities and Distributions

NIPS 2007

A₁A₂

A₁A₃

A₁A₄

A₂A₃

A₂A₄

A₃A₄

c(a₁,a₂)

c(a₁,a₃)

c(a₁,a₄)

c(a₂,a₃)

c(a₂,a₄)

c(a₃,a₄)

a₁

a₃

a₂

a₄

0.3126

0.0229

0.0172

0.0230

0.0183

0.2603

0.3126

0.0229

0.0172

0.0230

0.0183

0.2603

c(a₁,a₂)

c(a₁,a₃)

c(a₁,a₄)

c(a₂,a₃)

c(a₂,a₄)

c(a₃,a₄)

A₁A₂

A₁A₃

A₁A₄

A₂A₃

A₂A₄

A₃A₄

a₁

a₃

a₂

a₄

a₁

a₃

a₂

a₄

18 of 23

Distribution over Spanning Trees

Learning with Tree-averaged Densities and Distributions

NIPS 2007

a₁

a₃

a₂

a₄

β₃₄

β₂₄

β₁₃

β₁₂

β₁₄

β₂₃

a₁

a₃

a₂

a₄

β₃₄

β₂₄

β₁₃

β₁₂

β₁₄

β₂₃

[Meilă and Jaakkola 00, 06]

a₁

a₃

a₂

a₄

β₃₄

β₂₄

β₁₃

β₁₂

β₁₄

β₂₃

O(d³) !!!

19 of 23

Tree-Averaged Copula

Can compute sum over all d^d-2 spanning trees

Can be viewed as a mixture over many, many spanning trees
Can use EM to estimate the parameters

Even though there are d^d-2 mixture components!

Learning with Tree-averaged Densities and Distributions

NIPS 2007

20 of 23

EM for Tree-Averaged Copulas

E-step: compute

Can be done in O(d³) per data point

M-step: update β and Θ

Update of Θ is often linear in the number of points

Gaussian copula: solving cubic equation

Update of β is essentially iterative scaling

Can be done in O(d³) per iteration

Learning with Tree-averaged Densities and Distributions

NIPS 2007

Intractable!!!

21 of 23

Experiments: Log-Likelihood on Test Data

Learning with Tree-averaged Densities and Distributions

NIPS 2007

UCI ML Repository

MAGIC data set

12000 10-dimensional vectors

2000 examples in test sets

Average over 10 partitions

22 of 23

Binary-Continuous Data

Learning with Tree-averaged Densities and Distributions

NIPS 2007

23 of 23

Summary

Multivariate distribution = univariate marginals + copula
Copula density estimation via tree-averaging

Closed form

Tractable parameter estimation algorithm in ML framework (EM)

O(Nd³) per iteration

Only bivariate distributions at each estimation

Potentially avoiding the curse of dimensionality

New model for multi-site rainfall amounts (POSTER W12)

Learning with Tree-averaged Densities and Distributions

NIPS 2007