A Signal Separation View of Classification (Ryan O’Dowd, CGU)

Abstract: The problem of classification in machine learning has often been approached in terms of function approximation. In this talk, we propose an alternative approach for classification in arbitrary compact metric spaces which, in theory, yields both the number of classes, and a perfect classification using a minimal number of queried labels. Our approach uses localized trigonometric polynomial kernels initially developed for the point source signal separation problem in signal processing. Rather than point sources, we examine a convex combination of probability distributions representing the various classes from the machine learning classification problem. The localized kernel technique developed for separating point sources is then shown to separate the supports of these distributions. This is done in a hierarchical manner in our MASC algorithm to accommodate touching/overlapping class boundaries. The algorithm works in an active learning paradigm, deciding on points to query for their true class label and extending those labels to nearby points. We illustrate our theory on several simulated and real life data sets, including the Salinas and Indian Pines hyperspectral data sets and a document data set.