Non-negative Bregman Divergence Minimization for Deep Direct Density Ratio Estimation

Masahiro Kato and Takeshi Teshima. 2021. International Conference on Machine Learning (ICML 2021). Proceedings page (PMLR), arXiv:2006.06979. 日本語版

Density ratio estimation is the basis of anomaly detection and domain adaptation, and it can be written uniformly as the minimization of a Bregman divergence. We show that running that minimization with a flexible model such as a deep neural network invites a form of overfitting. The model exploits a property of the empirical loss and drives the training loss down in a way that has nothing to do with fitting the ratio, and we name this train-loss hacking. Adding a non-negativity correction to the empirical loss makes the estimate stable again.

The problem

Methods that estimate the ratio of two densities directly can be written as minimizing an empirical approximation to a Bregman divergence. That approximation, unlike the true divergence, is in some cases not bounded below. A model with enough capacity will then drive the loss down without limit instead of learning a density ratio that fits the data. Under tightly constrained models such as kernel methods the effect stays small. Under deep models it is large enough to wreck the estimate.

The proposed method

The entry point for the overfitting is a part of the empirical loss that ought to be non-negative but is free to go negative. We correct that part to be non-negative and minimize the corrected loss instead. The correction takes the same form for many Bregman divergences, and it requires only a small change to an existing training procedure.

Main results and conditions

For the corrected estimator we prove a generalization error bound. In experiments on inlier-based outlier detection, where outliers are found by reference to normal data, the corrected estimator performs better than the uncorrected one. The guarantee is a generalization error bound, not a claim that the method is best in every anomaly detection setting.

Relation to earlier work

Masashi Sugiyama and coauthors systematized the methodology of estimating a density ratio directly (Sugiyama, Suzuki, and Kanamori, 2012, Density Ratio Estimation in Machine Learning), and uLSIF with its squared loss is the leading representative (Kanamori, Hido, and Sugiyama, 2009, A Least-squares Approach to Direct Importance Estimation). The idea of forcing an empirical loss to be non-negative is shared with the non-negative risk estimator that Kiryo and coauthors proposed for PU learning (2017, Positive-Unlabeled Learning with Non-Negative Risk Estimator). We carry that idea into the general form of Bregman divergence minimization and give a correction, with a theoretical guarantee, for the overfitting of deep density ratio estimation.

Where it applies

When examples of the anomaly are few and anomalies have to be found by comparison with normal data, this gives a stable estimate while keeping the expressive power of a deep model. It helps most on data where the features are better learned than hand-built, such as images and time series. Where this work sits within anomaly detection is described on the Anomaly Detection page.

Paper and materials

BibTeX

@inproceedings{non-negative-bregman-density-ratio-estimation,
  author       = {Masahiro Kato and Takeshi Teshima},
  title        = {Non-negative Bregman Divergence Minimization for Deep Direct Density Ratio Estimation},
  year         = {2021},
  booktitle    = {International Conference on Machine Learning (ICML)},
  eprint       = {2006.06979},
  archivePrefix = {arXiv},
  url          = {https://proceedings.mlr.press/v139/kato21a.html},
}