Pool-based sequential Active Learning with Multi Kernels

Given training data $\{({\bf x}_{1},y_{1}),...,({\bf x}_{T},y_{T})\}$, where ${\bf x}_{t}\in\mathcal{X}\subset\mbox{\bb R}^{d}$ and $y_{t}\in\mathcal{Y}\subset\mbox{\bb R}$, the objective is to train a (non-linear) function $f$, which minimizes the accumulated loss over $T$ training samples. In RF-MKL frameworks, the learned function of each kernel $i$ has the form of

where ${\cal H}_{i}$ represents a reproducing kernel Hilbert space (RKHS) induced by a kernel $\kappa_{i}$, the optimization variable $\hat{\theta}$ is a 2D-vector, and

Note that the choice of $D$ can determine the accuracy of the RF approximation [16]. Then, a learned function is obtained by a convex combination of kernel functions, i.e.,

where $P$ indicates the number of single kernels, $\bar{{\cal H}}\stackrel{{\scriptstyle\Delta}}{{=}}{\cal H}_{1}\bigotimes{\cal H}_{2}\bigotimes\cdots\bigotimes{\cal H}_{P}$, and $\hat{p}_{i}\in[0,1]$ denotes the combination weight of the associated kernel function $\hat{f}_{i}({\bf x})$. The RF-MKL in (3) will be used as the baseline learning framework of the proposed AL. To simplify the notation, let $[N]\stackrel{{\scriptstyle\Delta}}{{=}}\{1,...,N\}$ for some positive integer $N$.

We consider a learning problem with $M$ unlabeled samples $\mathcal{S}_{1}=\{{\bf x}_{\tau}:\tau\in[M]\}$, where ${\bf x}_{\tau}\in\mathcal{X}\subset\mathbb{R}^{d}$. Our goal is to choose $T<M$ training samples (or labeled data) actively so that a learned function $\hat{f}({\bf x})$ can minimize the generalization error (or test error) of $M-T$ remaining unlabeled data. A pool-based sequential AL is also assumed, in which one sample is queried at each time. Namely, at each time $t$, a selection criterion actively chooses a sample ${\bf x}_{\tau}$ from the pool of unlabeled data, where the set of such unlabeled samples is denoted by ${\cal S}_{t}\subseteq{\cal S}_{1}$. In the next section, we will propose new selection criteria especially suitable for RF-MKL frameworks.

We explain the proposed selection criteria, called EKD and EKL, by focusing on time (or iteration) $t$. Recall that ${\cal S}_{t}$ denotes the set of unlabeled samples at this iteration, i.e., ${\cal S}_{t}={\cal S}_{1}\setminus{\cal U}_{t-1}$, where ${\cal U}_{t-1}$ denotes the set of the selected data during the $t-1$ iterations. Then, the most informative sample is determined as

where ${\cal Q}_{t}$ measures the usefulness of unlabeled samples. Our main goal is to construct the so-called selection criterion ${\cal Q}_{t}(\cdot)$, by leveraging the useful useful information $\{\hat{f}_{t,i},\hat{p}_{t,i}:i\in[P]\}$ provided by $P$ kernels. The detailed descriptions of EKD and EKL are provided in the below.

i) Expected-kernel-discrepancy (EKD): In this criterion, the informativeness is measured by the largest discrepancy (or inconsistency) of the opinions of $P$ kernels. Specifically, it is assumed that the biggest disagreement among the $P$ kernels has the largest impacts on the model update, thus being able to yield the most useful information on the current model. It can be formally defined as

where ${\cal L}(\cdot,\cdot)$ represents a loss function (e.g., least-square function). Unfortunately, the above criterion is not evaluated as $y_{\tau}$ is unknown. Instead, we evaluate the above term in average sense, assuming that $Y_{\tau}$ is a random variable which can take the values $\{\hat{y}_{i}=\hat{f}_{t,i}({\bf x}_{\tau}):i\in[P]\}$ with the probability mass function (PMF) $(\hat{p}_{t,1},...,\hat{p}_{t,P})$. Then, the selection criterion of EKD is obtained as

Note that the weights $\hat{p}_{t,i}$’s play a major role in assigning higher risks on the losses of more reliable kernels since they have more influence on the construction of an estimated function.

ii) Expected-kernel-loss (EKL): In this criterion, the informativeness is measured by the biggest loss on the current model, where it is assumed that the kernel $i$ can be optimal with the probability $\hat{p}_{t,i}$. Namely, an optimal function at the iteration $t$ is a random variable $F^{\star}$ which can take the values $\hat{f}_{t,i}$ with the probability $\hat{p}_{t,i}$ for $i\in[P]$. Then, EKL criterion can be mathematically defined as

The rationale behind this is that the informative sample would raise the largest change on model parameter (e.g. $\theta$), which naturally leads us to measure the maximum loss value between the current function and updated one with respect to each sample ${\bf x}_{\tau}$.

Connections with QBC and EMC: We remark that the proposed criteria can be regarded as some generalizations of the main concepts of QBC and EMC under RF-MKL frameworks. In this case, QBC (or EMC) can naturally take $P$ kernels as $P$ committee members (or $P$ models), instead of using bootstrapping. Using this and from [9], QBC and EMC can be determined as follows:

We first show that EMC is a special case of the proposed EKL by assuming ${\cal L}(x,y)=[x-y]^{2}$ and equal reliabilities ($\hat{p}_{t,i}=1/P,i\in[P]$). With the same assumptions, the proposed EKD can be simplified as

where the inequality is due to the fact that $\mbox{\bb E}[g(x)]\geq g(\mbox{\bb E}[x])$ for a convex function $g$. Thus, one can think that EKD is a generalization of QBC by taking the reliabilities of committee members into account.

We will explain how to obtain $\{\hat{f}_{t,i}({\bf x}):i\in[P]\}$ and $\{\hat{p}_{t,i}:i\in[P]\}$ in a sequential fashion. As noticed before, they are the key factors of the proposed selection criteria. At time $t$, using the selected data $({\bf x}_{t},y_{t})$ from either EKD or EKL, the proposed kernel-function update consists of the following two steps:

i) Local step : This step optimizes each single kernel independently from other kernels, namely,

where $\hat{\hbox{\boldmath$\theta$}}_{t+1,i}$ is 2$D$-dimensional parameter vector and ${\bf z}_{i}({\bf x})$ is defined in (2). $\hat{\hbox{\boldmath$\theta$}}_{t+1,i}$ is optimized via stochastic gradient descent (SGD) at every iteration $t$ such as

where $\nabla{\cal L}(\hat{\hbox{\boldmath$\theta$}}_{t,i}^{{\sf T}}{\bf z}_{i}({\bf x}_{t}),y_{t})$ denotes the gradient of the loss function defined by $({\bf x}_{t},y_{t})$.

ii) Global step : This step combines every single kernel function in (11) with its proper weight $\{\hat{p}_{t+1,i},i\in[P]\}$ to seek the best $\hat{f}_{t+1}({\bf x})$ in (3) approximation. For the weight update of $P$ kernels, exponential strategy (EXP strategy) [18] is adopted,

with the initial value $\hat{p}_{1,i}=1/P$ for $i\in[P]$.

During the training phase, Algorithm 1 provides the set of labeled data ${\cal U}_{T}=\{({\bf x}_{t},y_{t}):t\in[T]$ and an estimated function $\hat{f}_{T+1}({\bf x})$. Using them, our learned function $\hat{f}({\bf x})$ can be obtained in the following two approaches.

The first approach follows the conventional supervised learning approach by optimizing kernel parameters $\{\hat{\hbox{\boldmath$\theta$}}_{i}:i\in[P]\}$ using the labeled data ${\cal U}_{T}$. From (1), the parameters are obtained as

where ${\bf Z}_{i}$ denotes the $2D\times T$ data matrix whose $j$th column is equal to ${\bf z}_{i}({\bf x}_{j})$ for $j\in[T]$, and ${\bf y}=(y_{1},...,y_{T})^{{\sf T}}$. Also, ${\bf Z}_{i}^{{\dagger}}$ denotes the pseudo-inverse of ${\bf Z}_{i}$. Note that ${\bf Z}_{i}^{{\dagger}}$ exists as $T$ is usually chosen with $T\gg 2D$. Accordingly, the weights (or reliabilities) of kernels are determined as

Then, a learned function is obtained as

The major drawback of the above approach is an expensive computational complexity to obtain a pseudo-inverse matrix when $T$ becomes a large, i.e., $M$ is large. This problem can be addressed by taking $\hat{f}({\bf x})$ as a consequence of active sampling process, i.e.,

This learning process can be regarded as an online learning [18]. Finally, the learned function $\hat{f}({\bf x})$ will be used to estimate the labels of $M-T$ unlabeled data ${\bf x}_{\tau}\in{\cal S}_{T}$.