Timezone: »
Spotlight
Inverse Density as an Inverse Problem: the Fredholm Equation Approach
Qichao Que · Mikhail Belkin
Sat Dec 07 11:48 AM  11:52 AM (PST) @ Harvey's Convention Center Floor, CC
We address the problem of estimating the ratio $\frac{q}{p}$ where $p$ is a density function and $q$ is another density, or, more generally an arbitrary function. Knowing or approximating this ratio is needed in various problems of inference and integration, in particular, when one needs to average a function with respect to one probability distribution, given a sample from another. It is often referred as {\it importance sampling} in statistical inference and is also closely related to the problem of {\it covariate shift} in transfer learning as well as to various MCMC methods. Our approach is based on reformulating the problem of estimating the ratio as an inverse problem in terms of an integral operator corresponding to a kernel, and thus reducing it to an integral equation, known as the Fredholm problem of the first kind. This formulation, combined with the techniques of regularization and kernel methods, leads to a principled kernelbased framework for constructing algorithms and for analyzing them theoretically. The resulting family of algorithms (FIRE, for Fredholm Inverse Regularized Estimator) is flexible, simple and easy to implement. We provide detailed theoretical analysis including concentration bounds and convergence rates for the Gaussian kernel for densities defined on $\R^d$ and smooth $d$dimensional submanifolds of the Euclidean space. Model selection for unsupervised or semisupervised inference is generally a difficult problem. Interestingly, it turns out that in the density ratio estimation setting, when samples from both distributions are available, there are simple completely unsupervised methods for choosing parameters. We call this model selection mechanism CDCV for CrossDensity CrossValidation. Finally, we show encouraging experimental results including applications to classification within the covariate shift framework.
Author Information
Qichao Que (The Ohio State University)
Mikhail Belkin (Ohio State University)
Related Events (a corresponding poster, oral, or spotlight)

2013 Poster: Inverse Density as an Inverse Problem: the Fredholm Equation Approach »
Sun. Dec 8th 03:00  07:59 AM Room Harrah's Special Events Center, 2nd Floor
More from the Same Authors

2021 Poster: Risk Bounds for Overparameterized Maximum Margin Classification on SubGaussian Mixtures »
Yuan Cao · Quanquan Gu · Mikhail Belkin 
2021 Poster: Multiple Descent: Design Your Own Generalization Curve »
Lin Chen · Yifei Min · Mikhail Belkin · Amin Karbasi 
2018 Poster: Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate »
Mikhail Belkin · Daniel Hsu · Partha P Mitra 
2017 Poster: Diving into the shallows: a computational perspective on largescale shallow learning »
SIYUAN MA · Mikhail Belkin 
2017 Spotlight: Diving into the shallows: a computational perspective on largescale shallow learning »
SIYUAN MA · Mikhail Belkin 
2016 Poster: Graphons, mergeons, and so on! »
Justin Eldridge · Mikhail Belkin · Yusu Wang 
2016 Oral: Graphons, mergeons, and so on! »
Justin Eldridge · Mikhail Belkin · Yusu Wang 
2016 Poster: Clustering with Bregman Divergences: an Asymptotic Analysis »
Chaoyue Liu · Mikhail Belkin 
2015 Poster: A PseudoEuclidean Iteration for Optimal Recovery in Noisy ICA »
James R Voss · Mikhail Belkin · Luis Rademacher 
2014 Poster: Learning with Fredholm Kernels »
Qichao Que · Mikhail Belkin · Yusu Wang 
2013 Workshop: Modern Nonparametric Methods in Machine Learning »
Arthur Gretton · Mladen Kolar · Samory Kpotufe · John Lafferty · Han Liu · Bernhard Schölkopf · Alexander Smola · Rob Nowak · Mikhail Belkin · Lorenzo Rosasco · peter bickel · Yue Zhao 
2013 Poster: Fast Algorithms for Gaussian Noise Invariant Independent Component Analysis »
James R Voss · Luis Rademacher · Mikhail Belkin 
2011 Poster: Data Skeletonization via Reeb Graphs »
Xiaoyin Ge · Issam I Safa · Mikhail Belkin · Yusu Wang 
2009 Poster: Semisupervised Learning using Sparse Eigenfunction Bases »
Kaushik Sinha · Mikhail Belkin 
2007 Spotlight: The Value of Labeled and Unlabeled Examples when the Model is Imperfect »
Kaushik Sinha · Mikhail Belkin 
2007 Poster: The Value of Labeled and Unlabeled Examples when the Model is Imperfect »
Kaushik Sinha · Mikhail Belkin 
2006 Poster: On the Relation Between Low Density Separation, Spectral Clustering and Graph Cuts »
Hariharan Narayanan · Mikhail Belkin · Partha Niyogi 
2006 Poster: Convergence of Laplacian Eigenmaps »
Mikhail Belkin · Partha Niyogi