Seminar on Computational Learning and Adaptation
The Matching Representation for Tree Structures
and its Applications to Tree-Based Classifiers
Susan Holmes
Department of Statistics
Stanford University
Stanford, CA 94305-4065
susan@stat.stanford.edu
A challenging task for computational statisticians involves the construction
of taxinomic hierachies or trees from unsupervised training data. However,
previous work in this topic typically lacks a well-defined measure of the
distance between alternative trees or a means for searching the space effectively.
This talk presents a natural coordinate system for semi-labeled binary
trees using a correspondence with the set of perfect matchings in the complete
graph. This correspondence produces a distance between trees, and
a way of enumerating all trees in a minimal step order. It is useful
in randomized algorithms as it enables moves on the space of trees that
make random optimization strategies `mix' quickly. It also promises
a generalization to intermediary trees when data are not decisive as to
their choice of tree, and a new way of constructing Bayesian priors on
tree space.
This is joint work with Persi Diaconis.
| Date: Thurs., Jan. 14 |
Time: 4:15-5:30PM
|
Place: Cordura 100
|
Return to the seminar schedule