Active Learning by Query by Committee with Robust Divergences

Suppose we have a small initial training dataset $S_{0}=\{(\bm{x}_{i},y_{i})\}$, and the initial predictive model $y=h_{0}(\bm{x})$ is trained with $S_{0}$. In active learning, a learner is supposed to select a sample $\bm{x}$ for which the value of the corresponding output variable $y$ is unknown by some criteria, thereby obtaining the value of $y$. The function that returns the value of the explanatory variable for $\bm{x}$ is often called the oracle. In statistics, for most sequential designs, a setting is assumed in which observation points can be freely selected according to some standard; this is called membership query synthesis in the context of active learning [3]. On the other hand, in the literature on active learning, it is often assumed that the learner has access to a set of pooled unlabeled samples denoted by $\mathcal{X}_{p}$ and selects one sample from $\mathcal{X}_{p}$ in one iteration of the active learning procedure on the basis of the value of an acquisition function $a(\bm{x})$. Then, the output value $y$ for the chosen sample $\bm{x}$ is measured, and the dataset for learning the predictive model is updated as $S_{t+1}=S_{t}\cup\{(\bm{x},y)\}$. We follow this problem setting.

Given a set of input and output pairs $S_{t}=\{(\bm{x}_{i},y_{i})\}_{i=1,\dots,n_{t}}$, we define $X_{t}=(\bm{x}_{1},\dots,\bm{x}_{n_{t}})^{\top}\in\mathbb{R}^{n_{t}\times d}$ as the design matrix and a vector of realizations of output $\bm{y}=(y_{1},\dots,y_{n_{t}})$. We consider the joint distribution $p(\bm{y}|X_{t},\bm{\xi})$ of $\bm{y}$ parameterized by $\bm{\xi}\in\mathbb{R}^{m}$ and estimate $\bm{\xi}$ by the maximum likelihood method. An exponential family is a broad class of statistical models, which includes Gaussian distribution and Poisson distribution, for example. A generalized linear model (GLM; [16]) considers that each output $y$ is assumed to be generated from a particular distribution in an exponential family. Statistical inference on the GLM is investigated from the viewpoint of information geometry [19, 11]. There are several equivalent representations for GLM, and we adopt the following form:

where $\phi$ is a dispersion parameter and is assumed to be known in this paper. The function $\psi(\xi(\bm{x}))$ is the cumulant generating function. Here, $\xi\in\mathbb{R}$ is the canonical parameter of the distribution, but in the framework of the generalized linear model, we further introduce the linear predictor $\xi(\bm{x})=h(\bm{x};\bm{\theta})=\langle\bm{\theta},\bm{x}\rangle$ and consider $\bm{\theta}$ as the target of estimation, where $\langle\;\cdot\;,\;\cdot\;\rangle$ is the Euclidean inner product, and accordingly, $p(y|\xi(\bm{x}))=p(y|\bm{x};\bm{\theta})$. As a basic requirement, $\xi$ is in $(-\infty,\infty)$, so that the linear model $\xi=\langle\bm{\theta},\bm{x}\rangle$ is always well-defined for any regression parameter $\bm{\theta}\in\mathbb{R}^{d}$.

Since the generalized linear model (1) is determined by design $X_{t-1}$ and parameter $\bm{\theta}$, the model manifold is denoted as

In the framework of active learning, we assume, by using $\bm{y}$ and $X_{t-1}$, that an estimate of parameter $\hat{\bm{\theta}}_{t-1}$ has been obtained. Then, by using the information contained in $\bm{y},X_{t-1}$ and $\hat{\bm{\theta}}_{t-1}$, we explore a point $\bm{x}_{t}\in\mathcal{X}_{p}$. Considering the fact that the canonical parameter for the generalized linear model $\xi$ is expressed by $\langle\bm{\theta},\bm{x}\rangle=\xi(\bm{x})$, we consider fixing $\bm{\theta}=\hat{\bm{\theta}}_{t-1}$ and $\bm{x}$ as the element of the algebraic dual space of $\bm{\theta}\in\Theta$. Then, the problem of exploring the sample point $\bm{x}\in\mathcal{X}_{p}$ in active learning is considered as the problem of finding $\bm{x}$ by maximizing an acquisition function characterized by $p(y|\bm{x};\hat{\bm{\theta}}_{t-1})$. The dimensionality of joint distribution is $t-1$ in $M_{X_{t-1}}$ and $t$ in $M_{X_{t}}$, while the dimensionality of parameter $\bm{\theta}$ remains the same. The parameter $\bm{\theta}$ specifies a point of the model manifold $M_{X_{t}}$ or $M_{X_{t-1}}$. From this perspective, the updated dataset $S_{t}=S_{t-1}\cup\{(\bm{x}_{t},y_{t})\}$ in the process of active learning is regarded as the extension of the model space $M_{X_{t-1}}$ to $M_{X_{t}}$ as schematically depicted in Figure 1. We consider an active learning problem that explores an additional observation point $\bm{\theta}_{t}$ based on the current model parameter $\hat{\bm{\theta}}_{t-1}$. In Fig.1, the dotted arrow connects the different model spaces, and the solid arrow connects model parameters within the same model space $M_{X_{t}}$. The cross mark specifies a point in $M_{X_{t-1}}$ while open circles specify points in $M_{X_{t}}$. Note that the parameter $\hat{\bm{\theta}}_{t-1}$ corresponds to a point obtained by MLE with $S_{t-1}$ in $M_{X_{t-1}}$. Additional observation $(\bm{\theta}_{t},y_{t})$ defines an updated model space $M_{X_{t}}$. The parameter $\hat{\bm{\theta}}_{t-1}$ specifies a point in the updated model space $M_{X_{t}}$, but it is not the parameter $\hat{\bm{\theta}}_{t}$ obtained by MLE using the updated dataset $S_{t}$ in general.

The design of the acquisition function is one of the central issues in active learning studies. Several acquisition functions aim to quantify the difficulty of label prediction in some way and actively incorporate difficult-to-predict samples into learning. This approach of designing acquisition functions is called the uncertainty-based approach. As another approach, it is reasonable to sample inputs so as to reflect the distribution of explanatory variables, and methods that are based on the idea of annotating representative samples [27, 30] have been proposed. In addition, several methods have recently been proposed to learn acquisition functions according to the environment and data [24, 17, 33].

In this work, we consider the uncertain-based approach. In particular, we adopt a simple and intuitive method for quantifying the uncertainty called the query by committee (QBC).

One of the criteria for selecting new observations in active learning is the query by committee (QBC; [32]). This is an approach that selects the sample on which there will be the most disagreement in a sense of a consensus of multiple predictive models. Each time a new sample $\bm{x}\in\mathcal{X}_{p}$ or query is issued, committee members vote on the response $y$ for the query $\bm{x}$. Various methods have been proposed and discussed in relation to ensemble learning [13] and the resulting reduction of version space [15]. As a simple representative method, the following procedure is proposed in [25]:

1. 1.

   Learn $C$ predictive models with different parameters $\bm{\theta}_{c,t-1},c=1,\dots,C$ by, for example, Bagging [9].

2. 2.

   Select a sample from the pool as $\bm{x}_{t}=\mathop{\rm arg~{}max}\limits_{\bm{x}\in\mathcal{X}_{p}}a(\bm{x})$ by using the acquisition function

   $\displaystyle a_{0}(\bm{x})=\sum_{c=1}^{C}w_{c}D_{0}(p(Y|\xi_{c,t-1}(\bm{x})),p(Y|\bar{\xi}(\bm{x}))),$

   (5)

   where $D_{0}$ is the Kullback–Leibler (KL) divergence, and $\bar{\xi}(\bm{x})$ is the consensus model parameter defined later, and $\xi_{c,t-1}(\bm{x})=\langle\bm{\theta}_{c,t-1},\bm{x}\rangle$. Measure the response $y$ corresponding to the selected $\bm{x}_{t}$ and denote it as $y_{t}$.

3. 3.

   Update the training dataset $S_{t}=S_{t-1}\cup\{(\bm{x}_{t},y_{t})\}$.

In Eq. (5), the divergences are mixed with the mixing weight $w_{c},c=1,\dots,C$ where $w_{c}\geq 0$ and $\sum_{c=1}^{C}w_{c}=1$. The weight $w=(w_{1},\dots,w_{C})$ reflects the reliability of committee members, and can be fixed in advance or determined during the learning procedure for a committee member. In this work, we consider $w_{c}=1/C$ and fixed throughout the active learning process.

The consensus model is explicitly obtained by minimizing

where we used $\psi^{\prime}(\xi)=\mathbb{E}_{\xi}[Y]$. Then, solving $\frac{\partial J(\xi)}{\partial\xi}=\psi^{\prime\prime}(\xi)\sum_{c=1}^{C}w_{c}(\xi-\xi_{c})=0$, we have $\bar{\xi}=\sum_{c=1}^{C}w_{c}\xi_{c}$.

Note that the maximization of Eq. (5) is often not a well-defined optimization problem when $\bm{x}$ freely takes any value in $\mathcal{X}$. In fact, the domain of $\bm{x}$ is a set of candidate measurement points $\mathcal{X}_{p}$ given in advance, the so-called pool, and maximization is carried out by evaluating all the elements of this set. Therefore, there is no need for mathematical optimization, and the maximization is simply carried out by evaluating the acquisition function $a_{0}(\bm{x})$.

The consensus model and the acquisition function are originally defined on the basis of the KL divergence, which is vulnerable to outliers. In the QBC procedure explained above, committee models are trained by using a small amount of training data. If we use Bagging to construct various committee members, the situation would be worse, and it is highly possible that some of the committee members behave as outliers. To alleviate this problem, we consider using robust divergence measures instead of a standard KL divergence for computing the consensus model and defining the acquisition function.

Let $U$ be a monotonically increasing convex function on $\mathbb{R}$ and $u$ be the derivative of $U$. We define $U^{\ast}(\zeta)=\sup_{z\in\mathbb{R}}\{z\zeta-U(z)\}$, that is, the Legendre transform of $U$, and $u^{\ast}=u^{-1}$ as the derivative of $U^{\ast}$. We consider transforming the function $f$ by $u^{\ast}(f)$, and denote the transformed function as $\breve{f}=u^{\ast}(f)$, which is called the $u$-representation of the function $f$. Then, the Bregman potential between two functions $f$ and $g$ is defined as

and the Bregman divergence [8] is defined as

where $p$ and $q$ are the probability density or probability mass functions. Note that we omit the integral variable $y$ for notational simplicity. Then, the $u$-cross entropy and $u$-entropy are defined as

respectively. Using these entropies, we define the Bregman divergence or the $u$-divergence from $p$ to $q$ as

The most popular convex function $U$ and its related functions for the Bregman divergence would be the exponential function, which leads to the Kullback–Leibler divergence where

The Euclidean distance is recovered with

Other important examples include the $\eta$-type with $\eta\geq 0$

and the $\beta$-type with $\beta\geq 0$

Both the $\eta$-type and $\beta$-type functions lead to robust estimators. In this work, we concentrate on the $\beta$-type and only consider the $\beta$-divergence

as an instance of the Bregman divergence.

In [6], it is proposed that a class of power divergences, and discussed a robust parameter estimation on the basis of this class. It is shown to be robust to outliers, and its relationship with the pseudo-spherical score was investigated in [14, 22, 23].

The standard $\gamma$-power divergence is given by

which satisfies the scale invariance for the second argument as $D_{\gamma}(p,zq)=D_{\gamma}(p,q)$ for any constant $z>0$.

Alternatively, we consider a dual $\gamma$ power divergence as

for $p$ and $q$ of $\mathcal{P}$. Note that $D^{*}_{\gamma}(zp,q)=D^{*}_{\gamma}(p,q)$ for any constant $z>0$. This implies that, if $p$ and $q$ are density functions with a finite mass, then $D^{*}_{\gamma}(p,q)\geq 0$ with equality $p=zq$. On the other hand, if $p$ and $q$ are in $\cal P$, then $D^{*}_{\gamma}(p,q)=0$ means $p=q$. It is worth noting that the dual $\gamma$-power divergence is closely related to the $\beta$-divergence defined in Eq. (17). Consider a scale adjustment as $\min_{v>0}D_{\beta}(vp,q)$. We observe that

in which the minimizer is given by $v^{*}=\big{(}\frac{\int pq^{\beta}\mathrm{d}\Lambda}{\int p^{\beta+1}\mathrm{d}\Lambda}\big{)}^{\frac{1}{\beta}},$ so that we have the minimum

We note that this divergence is scale-invariant for the first argument. By a power transformation for two terms on the right side of Eq. (21), we obtain

Accordingly, we get $D^{*}_{\gamma}(p,q)$ by the difference between both sides of (22) if $\beta=\gamma$.

It is nontrivial how to calculate the consensus model with the Bregman divergence defined by using a $\beta$-type convex function. However, the following theorem provides a way to achieve the minimizer of the sum of Bregman divergences.

The model $p_{u}(y;w)$ is called the $u$-mixture of $p_{c}(y),c=1,\dots,C$ associated with weight $w$. The constant $b$ is a normalizing factor so that $p_{u}$ is a valid probability density or mass function.

To be concrete, for the $\beta$-divergence,

hence we have

We note that in this expression, the consensus model does not have an explicit consensus parameter $\bar{\xi}$; therefore, we will denote the consensus model as $p_{u}(y|\bm{x};w)$ instead of $p(y|\bar{\xi}(\bm{x});w)$ henceforth. This expression contains a normalization factor $b(\bm{x})$, which depends on the input variable $\bm{x}$; therefore, the analytical calculation is prohibitive.

We characterize the robustness of the $u$-mixture in terms of the influence function [29]. Consider the mixture of models $p_{c}(y)=p(y;\xi_{c})$ with respect to the $u$-divergences with a weight $w_{c}$. We will omit $\bm{x}$ for notational simplicity. Then, we define an $\epsilon$-contamination weight operator $W_{\epsilon}$

where $\delta$ denotes the Dirac measure degenerated at zero. For notational simplicity, we write $p(y;w(\epsilon))=W_{\epsilon}[p]$.

The outlier $\xi_{\mathrm{out}}$ is a parameter value far from other committee members $\xi_{c}$. In GLM, the parameter $\xi$ is composed of $\bm{\theta}$ and $\bm{x}$; hence there are two possible reasons for the outlying point. One is the outlying input point $\bm{x}$, and the other is the outlying regression coefficient $\bm{\theta}$. In this work, the pool $\mathcal{X}_{p}$ is fixed and $\|\bm{x}\|$ is bounded, but it is meaningful to consider the situation that the parameter $\xi=\langle\bm{\theta},\bm{x}\rangle$ takes a very large value. The regression coefficient $\bm{\theta}$ is, in principle, not bounded and it may make $\xi$ arbitrary value.

With this $\epsilon$-contamination weight operator, we replace the weighted sum operation such as $(1-\epsilon)\sum_{c=1}^{C}w_{c}p(y;\xi_{c})+\epsilon p(y;\xi_{\mathrm{out}})$ by $W_{\epsilon}[p]=p(y;w(\epsilon))$, which is reduced to $\sum_{c=1}^{C}w_{c}p(y;\xi_{c})$ when $\epsilon=0$.

We focus on the contamination of the outlier model $p(y;\xi_{\mathrm{out}})$ in the mixture and consider its influence on the minimizer $p_{u}(y;w)$ of $A_{U}(q;w)$.

If the domain of $u^{\ast}$ is restricted to a subset of $\mathbb{R}$, then there does not exist such a normalizing constant $b$ in Eq. (25). For example, when $D_{U}$ is the $\beta$-power divergence, the minimizer is written as

If $p_{c}(y)>0$ for all $y$ of $\mathbb{R}$, $\lim_{\>|y|\rightarrow\infty}p_{c}(y)=0$. Hence, it must be $\beta>0$ and $b\leq 0$ since $\lim_{\>|y|\rightarrow\infty}p_{u}(y;w)=(-b)^{\frac{1}{\beta}}$. If $b<0$, $p_{u}(y;w)$ is not integrable because $p_{u}(y;w)\geq(-b)^{\frac{1}{\beta}}$. Note that this problem will occur unless the support of $p_{c}(y)$ is finite-discrete.

The model $p_{\gamma}(y;w)$ is called the dual $\gamma$-mixture of $p_{c}(y),c=1,\dots,C$ associated with weight $w$.

We now focus on the behaviors of the minimizers discussed above. For this, it is assumed that $p_{c}(y)=p(y;\xi_{c})$, where $p(y;\xi)=\exp\Big{\{}\frac{y\xi-\psi(\xi)}{\phi}+c(y,\phi)\Big{\}}.$