We build long chains of inference based on the results of data mining. But how do we certify the results of these inference so that we can say things like "there's a 51% chance you're a US person?" And more importantly, how can we generate compact certificates to give to users to validate labels being assigned to them?

Formally, suppose I'm given a clustering of a set of points into groups. How do I assign a score (or set of scores) to a point that captures the strength of its assignment to a group? In this talk I'll describe a method that draws on Voronoi-based interpolation techniques to define such a score, and uses epsilon-samples and convex body sampling to compute the score efficiently. I'll then illustrate the use of such a score with example applications.

This is joint work with Parasaran Raman.

Video Recording