TIME: 11:00am--noon, May 9, 2006 PLACE: CSE 503 TITLE: Model free stability results in clustering and Intransitivity and machine learning -- some open problems SPEAKER: Marina Meila, University of Washington ABSTRACT: This is a two part talk. The first (and longest) part will present some new results on clustering. The second part (cca 15 minutes) will describe some problems that have captured my interest recently. Model free stability results in clustering: If we have found a "good" clustering C of data set X, can we prove that C is not far from the (unknown) best clustering C* of this data set? Perhaps surprisingly, the answer to this question is sometimes yes. We can show bounds on the distance( C, C* ) for two clustering cost functions: the Normalized Cut and the squared distance cost of K-means clustering. These bounds exist in the case when the data X admits a "good" clustering for the given cost. Intransitivity and machine learning -- some open problems: This reasearch deals with making a choice between m>2 alternatives, like in multiway classification, or in decision making, from a set of pairwise preferences between objects (or the outputs of a set of binary classifiers). The graph of preferences is not necessarily transitive. What is then the "best choice"? This is just one example of how intransitivity can arise in multiway decision problems. I will describe some other sources of intransitivity. While these sources have been long identified, little has been done to construct algorithms that "invert the models", i.e finding the hidden combination of causes that produced a set of observed (intransitive) preferences. [Joint work with Jeff Bilmes]