Maximum Mean Discrepancy for Class Ratio Estimation: Convergence Bounds and Kernel Selection
Arun Shankar Iyer, Saketha Nath, Sunita Sarawagi · 2014
In recent times, many real world applications have emerged that require estimates of class ra-tios in an unlabeled instance collection as op-posed to labels of individual instances in the col-lection. In this paper we investigate the use of maximum mean discrepancy (MMD) in a repro-ducing kernel Hilbert space (RKHS) for estimat-ing such ratios. First, we theoretically analyze the MMD-based estimates. Our analysis establishes that, under some mild conditions, the estimate is statistically consistent. More importantly, it provides an up-per bound on the error in the estimate in terms of intuitive geometric quantities like class sep-aration and data spread. Next, we use the in-sights obtained from the theoretical analysis, to propose a novel convex formulation that auto-matically learns the kernel to be employed in the MMD-based estimation. We design an efficient cutting plane algorithm for solving this formula-tion. Finally, we empirically compare our esti-mator with several existing methods, and show significantly improved performance under vary-ing datasets, class ratios, and training sizes. 1.