Talk: What is the information content of an algorithm?

SpeakerJoachim M. Buhmann
AffiliationComputer Science Department, Machine Learning Laboratory, ETH, Zurich
Date and Time Nov. 7, 2013, 3 p.m. - 04:00 p.m.
LocationStar Seminar Room (32-D463), Stata - Bldg (32), MIT
HostTomaso Poggio

Brains, Minds & Machines Seminar Series presents
Porf. Joachim M. Buhmann, ETH Zurich

 

Abstract: Algorithms are exposed to randomness in the input or noise during the computation. How well can they preserve the information in the data w.r.t. the output space? Algorithms especially in Machine Learning are required to generalize over input fluctuations or randomization during execution. This talk elaborates a new framework to measure the "informativeness" of algorithmic procedures and their "stability" against noise. An algorithm is considered to be a noisy channel which is characterized by a generalization capacity (GC). The generalization capacity objectively ranks different algorithms for the same data processing task based on the bit rate of their respective capacities. The problem of grouping data is used to demonstrate this validation principle for clustering algorithms, e.g. k-means, pairwise clustering, normalized cut, adaptive ratio cut and dominant set clustering. Our new validation approach selects the most informative clustering algorithm, which filters out the maximal number of stable, task-related bits relative to the underlying hypothesis class. The concept also enables us to measure how many bit are extracted by sorting algorithms when the input and thereby the pairwise comparisons are subject to fluctuations.

The Brains, Minds & Machines Seminar Series* 2013-2014 is being organized by the IIT@MIT lab (a joint lab between MIT and the Italian Institute of Technology.)

The purpose of the seminar series is to bring together students and faculty at CBCL and CSAIL who aim to understand the problem of intelligence in terms of its realization in the mind and the brain. One important focus of the series is on the problem of learning which is emerging as the gateway to understanding and reproducing intelligence, both biological and artificial.

*This seminar series was formerly known as "Brains & Machines Seminar Series."

There are no comments yet

Post a new comment...