In this part we address theoretical aspects of density-ratio estimation.

In Chapter 13, we analyze the asymptotic properties of density-ratio estimation. We first establish the consistency and asymptotic normality of the KLIEP method (see Chapter 5) in Section 13.1, and we elucidate the asymptotic learning curve of the LSIF method (see Chapter 6) in Section 13.2. Then, in Section 13.3, we explain that the logistic regression method (see Chapter 4) achieves the minimum asymptotic variance when the parametric model is specified correctly. Finally, in Section 13.4, we compare theoretically the performance of density-ratio estimation methods, showing that separate density estimation (see Chapter 2) is favorable if correct density models are available, and direct density-ratio estimation is favorable otherwise.

In Chapter 14, the convergence rates of KLIEP (see Chapter 5) and uLSIF (see Chapter 6) are investigated theoretically under the non-parametric setup.

In Chapter 15, a parametric method of a two-sample test is described, and its properties are analyzed. We derive an optimal estimator of the divergence in the sense of the asymptotic variance, which is based on parametric densityratio estimation. Then we provide a statistic for two-sample tests based on the optimal divergence estimator, which is proved to dominate the existing empirical likelihood-score test.

Finally, in Chapter 16, the numerical stability of kernelized density-ratio estimators is analyzed. As shown in Section 7.2.2, the ratio fitting and the moment matching methods share the same solution in theory, although the optimization criteria are different.

In this part we show how density-ratio estimation methods can be used for solving various machine learning problems.

In the context of importance sampling (Fishman, 1996), where the expectation over one distribution is computed by the importance-weighted expectation over another distribution, density ratios play an essential role. In Chapter 9, the importance sampling technique is applied to non-stationarity/domain adaptation in the semi-supervised learning setup (Shimodaira, 2000; Zadrozny, 2004; Sugiyama and Müller, 2005; Storkey and Sugiyama, 2007; Sugiyama et al., 2007; Quiñonero- Candela et al., 2009; Sugiyama and Kawanabe, 2011). It is also shown that the same importance-weighting idea can be used for solving multi-task learning (Bickel et al., 2008).

Another major usage of density ratios is distribution comparisons. In Chapter 10, two methods of distribution comparison based on density-ratio estimation are described: inlier-base outlier detection, where distributions are compared in a pointwise manner (Smola et al., 2009; Hido et al., 2011), and two-sample tests, where the overall difference between distributions is compared within the framework of hypothesis testing (Sugiyama et al., 2011c).

In Chapter 11 we show that density-ratio methods allow one to accurately estimate mutual information (Suzuki et al., 2008, 2009a). Mutual information is a key quantity in information theory (Cover and Thomas, 2006), and it can be used for detecting statistical independence between random variables.

In this chapter we explain the usage of density-ratio estimation for comparing probability distributions.

In Section 10.1, the pointwise difference of two densities is considered for evaluating whether a sample drawn from one distribution is “typical” in the other distribution. This problem is referred to as inliner-based outlier detection, where the degree of outlyingness of samples in an evaluation dataset is examined based on another dataset that consists only of inlier samples (Smola et al., 2009; Hido et al., 2011).

In Section 10.2, the overall difference of two densities is considered, which basically corresponds to estimating a divergence between two densities. The estimated divergence can be used for a two-sample test, which is aimed at judging whether two distributions are the same within the framework of hypothesis testing (Sugiyama et al., 2011c).

Inlier-Based Outlier Detection

In this section we show how density-ratio methods can be used for inlier-based outlier detection (Smola et al., 2009; Hido et al., 2011). After an introduction in Section 10.1.1, we formulate the problem of inlier-based outlier detection and show how it can be solved via density-ratio estimation in Section 10.1.2. Various native outlier-detection methods are reviewed in Section 10.1.3, and experimental performance is compared in Section 10.1.4. Finally, the section is concluded in Section 10.1.5.

Introduction

The goal of outlier detection (a.k.a. anomaly detection, novelty detection, or one-class classification) is to find uncommon instances (“outliers”) in a given dataset.

The approaches of direct density-ratio estimation explained in the previous chapters were shown to be promising in experiments with naive kernel density estimation in experiments. However, these methods still perform rather poorly when the dimensionality of the data domain is high.

The purpose of this chapter is to introduce ideas for mitigating this weakness, following Sugiyama et al. (2010a, 2011b). A basic assumption behind the approaches explained here is that the difference between the two distributions in the density ratio (i.e., the distributions corresponding to the numerator and denominator of the density ratio) does not spread over the entire data domain, but is confined in a low-dimensional subspace – which we refer to as the heterodistributional subspace. Once the heterodistributional subspace can be identified, the density ratio is estimated only within this subspace. This will lead to more stable and reliable estimations of density ratios. Such an approach is called direct density-ratio estimation with dimensionality reduction (D3; pronounced “D-cube”).

In this chapter, two approaches to D3 are described. In Section 8.1, a heuristic method based on discriminant analysis is explained. This method is shown to be computationally very efficient, and thus is very practical. On the other hand, in Section 8.2, a more theory-oriented approach based on divergence maximization is introduced. This method is justifiable under general settings, and thus it has a wider applicability. Numerical examples are shown in Section 8.3, and the chapter is concluded in Section 8.4.

Estimating probability distributions is widely viewed as a central question in machine learning. The whole enterprise of probabilistic modeling using probabilistic graphical models is generally addressed by learning marginal and conditional probability distributions. Classification and regression – starting with Fisher's fundamental contributions – are similarly viewed as problems of estimating conditional densities.

The present book introduces an exciting alternative perspective – namely, that virtually all problems in machine learning can be formulated and solved as problems of estimating density ratios – the ratios of two probability densities. This book provides a comprehensive review of the elegant line of research undertaken by the authors and their collaborators over the last decade. It reviews existing work on density-ratio estimation and derives a variety of algorithms for directly estimating density ratios. It then shows how these novel algorithms can address not only standard machine learning problems – such as classification, regression, and feature selection – but also a variety of other important problems such as learning under a covariate shift, multi-task learning, outlier detection, sufficient dimensionality reduction, and independent component analysis.

At each point this book carefully defines the problems at hand, reviews existing work, derives novel methods, and reports on numerical experiments that validate the effectiveness and superiority of the new methods. A particularly impressive aspect of the work is that implementations of most of the methods are available for download from the authors’ web pages.