Wednesday, May 23, 2007


There is a heap of results on clustering problems, many differing in just how one measures the quality of clustering. Even as the community struggles through these variations, thinking through them and applying them to practice, one line of research I liked is the (somewhat?) left-field approach eg in An Impossibility Theorem for Clustering by Jon Kleinberg. Roughly, this paper sets up some basic requirements of any clustering procedure without nailing down optimization criteria and shows impossibility results for determining a clustering that meets all such requirements.

In a somewhat unrelated world, a question I would like to see addressed in such a fundamental theoretical way is related to sponsored search mechanisms. These mechanisms have different properties based on whether one works in the world of impressions, clicks or conversions (ranking and/or pricing), and there is a lot of tension based on which world one adopts. Is there a general way to reduce these worlds to each other, so equilibrium properties and mechanisms we know for some will get related to others? The question is vague and in limited cases, there will be negative answers, but a nifty approach here will be cool.


Post a Comment

<< Home