Cellular Tree Classifiers
(invited lecture for ALT 2014)
Author: Luc Devroye
School of Computer Science, McGill University
This is joint work with Gerard Biau.
Suppose that binary classification is done by a tree
method in which the leaves of a tree
correspond to a partition of d-space.
Within a partition, a majority vote is used.
Suppose furthermore that this tree must
be constructed recursively by implementing
just two functions, so that the construction can
be carried out in parallel by using "cells": first of all,
given input data, a cell must decide whether it
will become a leaf or internal node in the tree.
Secondly, if it decides on an internal node, it must decide
how to partition the space linearly.
Data are then split into two parts and sent downstream
to two new independent cells.
We discuss the design and properties of such
Luc P. Devroye is a Belgian computer scientist/mathematician and a
James McGill Professor in the School of Computer Science of McGill
University in Montreal, Canada. He studied at Katholieke Universiteit
Leuven and subsequently at Osaka University and in 1976 received his
PhD from University of Texas at Austin under the supervision of Terry
Wagner. Devroye specializes in the probabilistic analysis of
algorithms, random number generation and enjoys typography. Since
joining the McGill faculty in 1977 he has won numerous awards,
including an E.W.R. Steacie Memorial Fellowship (1987), a Humboldt
Research Award (2004), the Killam Prize (2005) and the Statistical
Society of Canada gold medal (2008). He received an honorary doctorate
from the Université catholique de Louvain in 2002, and he received an
honorary doctorate from Universiteit Antwerpen on March 29, 2012.