Trimmed Density Ratio Estimation
Density ratio estimation is a vital tool in both machine learning and statistical community. However, due to the unbounded nature of density ratio, the estimation procedure can be vulnerable to corrupted data points, which often pushes the estimated ratio toward infinity. In this paper, we present a robust estimator which automatically identifies and trims outliers. The proposed estimator has a convex formulation, and the global optimum can be obtained via subgradient descent. We analyze the parameter estimation error of this estimator under high-dimensional settings. Experiments are conducted to verify the effectiveness of the estimator.
high density region of p(x), we end up with a very different density ratio function and the original parametric pattern in the ratio is ruined. We give such an example in Section 6.
Volatile Samples The change of external environment may be responded in unpredictable ways. It is possible that a small portion of samples react more "aggressively" to the change than the others. These samples may be skewed and show very high density ratios, even if the change of distribution is relatively mild when these volatile samples are excluded. For example, when testing a new fertilizer, a small number of plants may fail to adapt, even if the vast majority of crops are healthy.
Overly large density ratio values can cause further troubles when the ratio is used to weight samples. For example, in the domain adaptation setting, we may reweight samples from one task and reuse them in another task. Density ratio is a natural choice of such "importance weighting" scheme [28,25]. However, if one or a few samples have extremely high ratio, after renormalizing, other samples will have almost zero weights and have little impact to the learning task.
Several methods have been proposed to solve this problem. The relative density ratio estimation [33] estimates a "biased" version of density ratio controlled by a mixture parameter α. The relative density ratio is always upper-bounded by 1 α , which can give a more robust estimator. However, it is not clear how to de-bias such an estimator to recover the true density ratio function. [26] took a more direct approach. It estimates a thresholded density ratio by setting up a tolerance t to the density ratio value. All likelihood ratio values bigger than t will be clipped to t. The estimator was derived from Fenchel duality for f -divergence [18]. However, the optimization for the estimator is not convex if one uses log-linear models. The formulation also relies on the non-parametric approximation of the density ratio function (or the log ratio function) making the learned model hard to interpret. Moreover, there is no intuitive way to directly control the proportion of ratios that are thresholded. Nonetheless, the concept studied in our paper is inspired by this pioneering work.
In this paper, we propose a novel method based on a "trimmed Maximum Likelihood Estimator" [17,10]. This idea relies on a specific type of density ratio estimator (called log-linear KLIEP) [30] which can be written as a maximum likelihood formulation. We simply "ignore" samples that make the empirical likelihood take exceedingly large values. The trimmed density ratio estimator can be formulated as a convex optimization and translated into a weighted M-estimator. This helps us develop a simple subgradient-based algorithm that is guaranteed to reach the global optimum.
Moreover, we shall prove that in addition to recovering the correct density ratio under the outlier setting, the estimator can also obtain a "corrected" density ratio function under a truncation setting. It ignores "pathological" samples and recovers density ratio only using "healthy" samples.
Although trimming will usually result a more robust estimate of the density ratio function, we also point out that it should not be abused. For example, in the tasks of two-sample test, a diverging density ratio might indicate interesting structural differences between two distributions.
In Section 2, we explain some preliminaries on trimmed maximum likelihood estimator. In Section 3, we introduce a trimmed DRE. We solve it using a convex formulation whose optimization procedure is explained in Section 4. In Section 5, we prove the estimation error upper-bound with respect to a sparsity inducing regularizer. Finally, experimental results are shown in Section 6 and we conclude our work in Section 7.
Trimmed Density Ratio Estimation
This paper proposes a convex method for robust density ratio estimation, and provides several theoretical and empirical results. I found the method to be well motivated, and of course Figure 3 is quite fun. Based on the evidence in the paper, I would feel comfortable recommending the method to others.
I would be happy to see these results published; however, I found the presentation to be fairly terse, and thought the paper was very difficult to follow. My main recommendation for the writing would be to focus more on core contributions, and to remove some side remarks to allow for longer discussions.
Moreover, the paper was missing some references.
Noting these issues, my current recommendation for the paper is a middle-of-the-road “accept”; however, if the authors are willing to thoroughly revise their paper, I would be open to considering a higher rating. Below are some specific comments.
Comments on motivation + literature:
- The paper opens the abstract by describing density ratio estimation (DRE) as a “versatile tool” in machine learning. I think this substantially undersells the problem: DRE is a a core statistical and machine learning task, and any advance to it should be of broad interest. I would recommend stressing the many applications of DRE more.
- On a related note, DRE has also received quite a bit of attention in the statistics literature. For example, Efron and Tibshirani (1996) use it to calibrate kernel estimators, and Fithian and Wager (2016) use DRE to stabilize heavy-tailed AB-tests. Fokianos (2004) models the density ratio to fit several densities at once. This literature should also be discussed.
- Are there some applications where trimming is better justified than others? Engineering applications relating to GANs or anomaly detection seem like very natural places to apply trimming; other problems, like two-sample testing, may be more of a stretch. (In applications like anomaly detection, it’s expected to have regions where the density ratio diverges, so regularizing against them is natural. On the other hand, if one finds a diverging density ratio in two-sample testing, that’s very interesting and shouldn’t be muted out.)
Comments on relationship to the one-class SVM:
- I found Section 2 on the one-class SVM to be very distracting. It’s too short to help anyone who isn’t already familiar with the method, and badly cuts the flow of the paper. I think a version of the paper that simply removed Section 2 would be much nicer to read. (The discussion of the one-class SVM is interesting, but belongs in the discussion section of a long journal paper, not on page 2 of an 8-page NIPS paper.)
- The use of the one-SVM in the experiments was interesting. However, I think the median reader would benefit from a lot more discussion. The point is that the proposed method gets to leverage the “background” images, whereas one-SVM doesn’t. So even though one-SVM is a good method, you bring more data to the table, so there’s no way one-SVM could win. (I know that the current draft says this, but it says it so briefly that I doubt anyone would notice it if they were reading at a regular speed.)
- As a concrete recommendation: If the authors were to omit Section 2 and devote the resulting space to adding a paragraph or two to the intro that reviews and motivates the DRE literature to the intro (including the stats literature) and to thoroughly contrasting their results with the one-SVM in the results section, I think the paper would be much easier to read.
Other comments:
- In the setting of 3.1, Fithian and Wager (2016) show that if we assume that one class has much more data than the other, then density ratio models can be fit via logistic regression. Can the authors comment on how the proposed type of trimming can be interpreted in the logistic regression case?
- Section 3.2 is awkwardly placed, and cuts the flow. I recommend moving this material to the intro.
- I wasn’t sold by the connection to the SVM on lines 120-129. The connection seems rather heuristic to me (maybe even cosmetic?); I personally would omit it. The core contributions of the paper are strong enough that there’s no need to fish for tentative connections.
- The most classical approach to convex robust estimation is via Huberization (e.g., Huber, 1972). What’s recommended here seems very different to me —- I think readers may benefit from a discussion of how they’re different.
- The approach of assuming a high-dimensional linear model for the theory and and RBF kernel for the experiments is fine. Highlighting this choice more prominently might help some readers, though.
References:
Efron, Bradley, and Robert Tibshirani. "Using specially designed exponential families for density estimation." The Annals of Statistics 24.6 (1996): 2431-2461.
Fithian, William, and Stefan Wager. "Semiparametric exponential families for heavy-tailed data." Biometrika 102.2 (2014): 486-493.
Fokianos, Konstantinos. "Merging information for semiparametric density estimation." Journal of the Royal Statistical Society: Series B (Statistical Methodology) 66.4 (2004): 941-958.
Huber, Peter J. “Robust statistics: A review." The Annals of Mathematical Statistics (1972): 1041-1067.
##########
UPDATE
In response to the authors’ comprehensive reply, I have increased my rating to an “8”.