Inverse Density as an Inverse Problem: the Fredholm Equation Approach
We address the problem of estimating the ratio 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 often referred to as importance sampling in statistical inference. It is also closely related to the problem of covariate shift in transfer learning. 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, known as the Fredholm problem of the first kind. This formulation, combined with the techniques of regularization leads to a principled 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 sub-manifolds of the Euclidean space. Model selection for unsupervised or semi-supervised inference is generally a difficult problem. It turns out that in the density ratio estimation setting, when samples from both distributions are available, simple completely unsupervised model selection methods are available. We call this mechanism CD-CV for Cross-Density Cross-Validation. We show encouraging experimental results including applications to classification within the covariate shift framework.
The authors use two equalities to derive two 
      estimators of the Radon-Nikodym derivative f= p/q: (i) Ep ( k(x,.) 
      f) = E_q k(x,.) and (ii) Ep (k(x,.) f ) ~ q(x) The integral 
      operators are replaced with empirical versions. {k(x,.)} can be seen as a 
      set of test functions over which the difference between the right and left 
      side is minimised. The choice of {k(x,.)} as the family of test functions 
      has the advantage that standard kernel methods can be used for 
      optimisation. Convergence guarantees are given for both settings 
      under smoothness & boundedness assumptions on the densities. The rate 
      of convergence depends crucially on the dimension of the underlying space 
      -- as one would expect for a density estimate. I think it is nice 
      and well executed work. A couple of comments: - For the 
      convergence rates. Optimising over the set {k(x,.)} is sufficient to 
      guarantee convergence to the ratio. For (ii) this is intuitive given the 
      bandwidth dependence. Would be nice to have a short intuitive argument why 
      this also works out in (i). -You optimise on page 2 over L_2,p. 
      Later in (9) you have a combination of L_2,p and L_2,q. Some motivation 
      for the choice of cost function would be nice. I guess ultimately these 
      need to stem from the tasks one is interested in. So would be nice to link 
      the cost function choice to certain important applications. - 
      Speaking of applications, one example you got is importance sampling. Ie 
      q/p is relevant for this to move from Eq to Ep. I'm wondering here: you 
      are effectively estimating E_p and E_q to get your empirical cost 
      function. So why not use directly the E_q you got there? Can E_p (q/p) be 
      any better than directly E_q? I guess I'm asking here for a motivation of 
      the setup since you need to produce estimates E_p and E_q to estimate q/p. 
      You have a sentence on p 5 about it. That is sampling is difficult from 
      E_q. Is this the kind of main application you have in mind? - The 
      regulariser: You enforce smoothness for the ratio q/p. Later in the 
      theorem you got smoothness assumptions on q and p ( which I would say is 
      the natural thing). So I'm wondering if there is any sort of relation 
      between smoothness on q and p and smoothness of the ratio? I guess an 
      answer is here already that you have many different q and p which produce 
      the same ratio; ie just change on countable or on uncountable many points 
      q and p to make it extremely irregular. So it might be more p ,q smooth 
      (possibly bounded away from 0) => ratio smooth (?) or ratio smooth 
      => there exist a smooth p and q which produces the ratio. - 
      Would be nice to discuss the d dependence of your rates -- for what 
      dimensions would you expect your method to be useful? - Is there 
      any good motivation for your family of test functions U? - A more 
      principled question: For this q/p ; covariate shift etc setting one of the 
      main difficulties seems to be to come up with a generic cost function. One 
      approach is to go through expectation operators and throw different test 
      functions at these to extract the underlying densities. Do you feel that 
      you got here "the right" approach with the {k(x,.)} ? There is also some 
      similarity to [1] in terms of playing around with transformations to get 
      hold of the quantities of interest. Certainly, your approach for the Radon 
      Nikodym derivative is nicer by working with test functions. But the 
      overall approach has some similarity. [1] Smooth Operators; 
      Grunewalder, Gretton, Shawe-Taylor