Towards Unsupervised HPO for Outlier Detection

In HPOD, we learn a regressor $f(\cdot )$ across all meta-train datasets, named Proxy Performance Evaluator, that maps their {HP settings, data characteristics, additional signals} onto ground truth performance. If $f(\cdot )$ only uses HP settings as the input feature, it fails to capture the performance variation of an HP given different datasets. Thus, we need additional input features to enable $f(\cdot )$ for quantifying dataset similarity, so that $f(\cdot )$ can make similar HP performance predictions on similar datasets, and vice versa.

How can we capture dataset similarity in OD? Recent work by (zhao2021automatic) introduced specialized OD meta-features (MF) to describe general characteristics of OD datasets; e.g., number of samples, basic feature statistics, etc. With the meta-feature extractor, both meta-train datasets and (later) the test dataset can be expressed as fixed-length vectors, and thus any similarity measure applies, e.g., Euclidean distance. To build $f(\cdot )$, we extract meta-features from each meta-train dataset as $M=\{m_1,\dots ,m_n\}=\psi \left(\right\{X_1,\dots ,X_n\left\}\right)\in R^{n\times d}$, where $\psi (\cdot )$ is the extraction module, and $d$ is the number of MF.

Although meta-features describe general characteristics of OD datasets, their similarity does not necessarily correlate with the actual performance. Thus, we enrich the input features of $f(\cdot )$ with internal performance measures (IPMs) (ma2021large), which are more “performance-driven”. IPMs are noisy/weak unsupervised signals that are solely based on the input samples and/or a given model’s output (e.g., outlier scores) that can be used to compare two models goix2016evaluate; marques2020internal. In HPOD, we make the best use of these weak signals by learning in $f(\cdot )$ to regress the IPMs of a given HP setting (along with other signals) onto its true performance with supervision. To build $f(\cdot )$, we extract IPMs of each detector $M_j$ with HP setting ${\lambda }_j\in {\lambda }_{meta}$ on each meta-train dataset $D_i\in D_{\text{train}}$, where $I_{i,j}:=\varphi \left(O_{i,j}\right)$ refers to the IPMs using the $j$-th HP setting for the $i$-th meta-train dataset, and $\varphi (\cdot )$ is the IPM extractor. We defer the details on IPMs to Appx. B.1.

Putting these together, we build Proxy Performance Evaluator $f(\cdot )$ to map {HP setting, meta-features, IPMs} of HP ${\lambda }_j\in {\lambda }_{meta}$ on the $i$-th meta-train dataset onto its ground truth performance, i.e., $f({\lambda }_j,m_i,I_{i,j})\mapsto P_{i,j}$. See training details of $f(\cdot )$ in Appx. B.2.

We find it critical to remark that provided $\psi (\cdot )$, $\varphi (\cdot )$, and the trained $f(\cdot )$ at test time, predicting the detection performance of HP settings becomes possible for the new task without using any ground-truth labels.

Different from $f(\cdot )$ that trains on all meta-train datasets and leverages rich input features (i.e., HPs, MFs, and IPMs) to predict HP performance, we also train $n$ independent regressors with only HPs as input, $T=\{t_1,\dots ,t_n\}$. That is, for each meta-train dataset $D_i\in D_{\text{train}}$, we train a regressor $t_i(\cdot )$ that simply maps the $j$-th HP setting ${\lambda }_j\in {\lambda }_{meta}$ to its detection performance on the $i$-th meta-train dataset, i.e., $t_i\left({\lambda }_j\right)\mapsto P_{i,j}$.

Since these independent regressors only use HP settings as input, they can be readily transferred to the online model selection phase to improve HP performance evaluation on $X_{\text{test}}$. We defer their specific usage to §3.4.2 and §3.5.2.

Given a new dataset $D_{\text{test}}$, we can sample a set of HPs (termed as the evaluation set ${\lambda }_{\text{eval}}\in \Lambda$), and use the proxy performance evaluator $f(\cdot )$ from meta-training to predict their performance, based on which we can output the one with the highest predicted value as follows.

By setting ${\lambda }_{\text{eval}}$ to some randomly sampled HPs and plugging it into Eq. (2), we have the “version 0” of HPOD, referred as HPOD_0. However, $f(\cdot )$ needs IPMs (i.e., $I_{\text{test},k}$ in Eq. (2)) as part of the input, requiring detector building at test time. Thus, we should construct ${\lambda }_{\text{eval}}$ carefully to ensure it captures promising HPs, where random sampling is insufficient. Thus we ask: how can we efficiently identify promising HPs for model building and evaluation at test time?

As we briefly described in §2, SMBO can iteratively optimize an expensive objective (hutter2011sequential), and has been widely used in supervised model selection and HPO (bergstra2015hyperopt). Other than sampling HPs randomly, learning-based SMBO shows better efficiency in finding promising HPs to evaluate in iterations. In short, SMBO constructs a cheap regression model (called surrogate function $s(\cdot )$) and uses it for identifying the promising HPs to be evaluated by the (expensive) true objective function. It then iterates between fitting the surrogate function with newly evaluated HP information and gathering new information based on the surrogate function. We provide the pseudo-code of the supervised HPO by SMBO in Appx. Algorithm A1, and note that it does not directly apply to HPO for OD as perf. cannot be evaluated without ground truth labels (line 4).

We enable (originally supervised) SMBO for unsupervised outlier detection HPO by plugging the PPE $f(\cdot )$ from the meta-train in place of HP performance evaluation. The key steps of online HPO by HPOD are presented below.

To initialize $s(\cdot )$, we train it on a small number of HPs. More specifically, we train $s(\cdot )$ with pairs of HPs and their corresponding predicted performance by $f(\cdot )$ on $X_{\text{test}}$, and also initialize the evaluation set ${\lambda }_{\text{eval}}$ to these HPs. Although we can randomly sample the initial HPs, we propose to set them to top-performing HPs from similar meta-train tasks. Consequently, our initial $s(\cdot )$ is more accurate in predicting likely well-performing HPs on $X_{\text{test}}$. We defer the details of this meta-learning-based surrogate initialization to §3.5.1.

Under the SMBO framework, in each iteration we use $s(\cdot )$ to predict the performance (denoted as $u_k:=s\left({\lambda }_k\right)$) and the uncertainty around the prediction (denoted as ${\sigma }_k$) of sampled ${\lambda }_k\in {\lambda }_{sample}$⁴⁴4 ${\lambda }_{sample}$ is a finite HP candidate set that is randomly sampled from the full (continuous) HP space $\Lambda$ (see details in Appx. C.1). Since $s(\cdot )$ can make fast predictions, ${\lambda }_{sample}$’s size can be large, e.g., 10,000 as in hutter2011sequential. , and then select the most promising one to be “evaluated” by $f(\cdot )$. Intuitively, we would like to evaluate the HPs with both high predicted performance $u_k$ (i.e., exploitation) and high potential/prediction uncertainty ${\sigma }_k$ (i.e., exploration), which is widely known as “exploitation-exploration trade-off” shahriari2015taking. Too much exploitation (i.e., always evaluating the similar HPs) will fail to identify promising HPs, while too much exploration (i.e., only considering high uncertainty HPs) may lead to low-performance HPs. Also, note that the quality of identified HPs depends on the prediction accuracy of $s(\cdot )$, where we propose to transfer knowledge from meta-surrogate functions $T$ by performance similarity (see details in §3.5.2.)

How can we effectively balance the trade-off between exploitation and exploration in HPOD? As an SMBO method, we use the acquisition function $a(\cdot )$ to factor in the trade-off and pick a promising HP setting based on the outputs of the surrogate function. The acquisition function quantifies the “expected utility” of HPs by balancing their predicted performance and the uncertainty. Thus, we output the most promising HP to evaluate by maximizing $a(\cdot )$:

One of the most prominent choices of $a(\cdot )$ is Expected Improvement (EI) (DBLP:journals/jgo/JonesSW98), which is used in HPOD and can be replaced by other choices. EI has a closed-form expression under the Gaussian assumption, and the EI value of HP setting ${\lambda }_k$ is shown below.

In the above, $\Phi (\cdot )$ and $\phi (\cdot )$ respectively denote the cumulative distribution and the probability density functions of a standard Normal distribution, $u_k$ and ${\sigma }_k$ are the predicted performance and the uncertainty around the prediction of ${\lambda }_k$ by the surrogate function $s(\cdot )$, and ${\hat{P}}_{\text{test}}^{\ast }$ is the highest predicted performance by $f(\cdot )$ on ${\lambda }_{\text{eval}}$ so far. We compare EI with other selection criteria in §4.4.1.

At the $e$-th iteration, we plug the surrogate $s^{\left(e\right)}(\cdot )$ into Eq. (3), which returns ${\lambda }^{\left(e\right)}$ to evaluate. Next, we train the OD model $M$ with ${\lambda }^{\left(e\right)}$ to get its outlier scores $O_{\text{test}}^{\left(e\right)}$ and IPMs $I_{\text{test}}^{\left(e\right)}$, and then predict its performance by $f(\cdot )$ as

Finally, we add ${\lambda }^{\left(e\right)}$ to the evaluation set ${\lambda }_{\text{eval}}:={\lambda }_{\text{eval}}\cup {\lambda }^{\left(e\right)}$, and update the surrogate function to $s^{(e+1)}$ with newly evaluated HP information $⟨{\lambda }^{\left(e\right)},{\hat{P}}_{\text{test}}^{\left(e\right)}⟩$.

To sum up, HPOD alternates between (i) identifying the next promising HP by the surrogate function $s(\cdot )$ and (ii) updating $s(\cdot )$ based on newly evaluated HP.

Other than initializing on a small set of randomly sampled HPs, we design a meta-learning initialization strategy for the surrogate function (see §3.4.2), based on the similarity between the test and meta-train datasets. Intuitively, we hope the surrogate function $s(\cdot )$ can make accurate predictions on the top-performing HPs of the test dataset, while the accuracy of the under-performing HP regions is less important. To this end, we use the meta-features (see §3.3.1) to calculate the similarity between the test dataset to each meta-train task $D_i\in D_{\text{train}}$, and initialize $s(\cdot )$ with the top performing HPs from the most similar meta-train dataset; these HPs may yield good performance on the test dataset as well. See the comparison to random initialization in §4.4.2.

As introduced in §2.2, meta-learning can be used to improve the surrogate function $s(\cdot )$ in SMBO by transferring knowledge from meta-train datasets. In HPOD, we train $n$ independent Meta-Surrogate Functions (see §3.3.2) for $n$ meta-train datasets, $T=\{t_1,\dots ,t_n\}$; each with the same regression function as $s(\cdot )$ (i.e., Gaussian Process). To this end, we identify the most similar meta-train dataset $D_i$ in iteration $e$, and use the test surrogate $s(\cdot )$ and $D_i$’s meta-surrogate $t_i$ together to predict the performance of HP ${\lambda }_k$, i.e.,

Instead, we (re)calculate the performance similarity every iteration based on the HPs in ${\lambda }_{\text{eval}}$ between each meta-train task and the test dataset, and dynamically transfer the most similar meta-train dataset’s meta-surrogate function. Specifically, HPOD computes a rank-based similarity by weighted Kendall tau shieh1998weighted) between each meta-train dataset’s ground truth performance and the test dataset’s predicted performance by $f(\cdot )$ on ${\lambda }_{\text{eval}}$ (which gets updated in every iteration). See the effect of surrogate transfer in §4.4.3.

Fig. 1 (right) and 2 show that HPOD outperforms all baselines w.r.t. both the best avg. normalized AP rank and the top q% value. Furthermore, HPOD is also statistically better than all baselines as shown in Table 1(a), including strong meta-learning baseline MetaOD ($p$$=$$0.0398$). Its advantages can be credited to two reasons. First, meta-learning-based HPOD leverages prior knowledge on similar historical tasks to predict HP perf. on the new dataset, whereas simple baselines like Random and MinLoss cannot. Second, only HPOD and HPOD_0 can select HPs from continuous spaces, while other meta-learning baselines are limited to finite discrete HPs as specified for the meta-train datasets which are too few to capture optimal HPs (especially for deep models with huge HP spaces).

HPOD uses the EI acquisition to select an HP based on the surrogate function’s prediction (see §3.4.2). We compare it with random and greedy acquisition (latter picks the HP with the highest predicted performance, ignoring uncertainty) in Fig. 3, where EI-based acquisition shows the best performance.

HPOD uses meta-learning to initialize the surrogate (see §3.5.1). Fig. 4 shows its advantage over random init. with higher performance.

To improve the prediction performance of the surrogate function, HPOD transfers meta-surrogate functions from similar meta-train tasks (see §3.5.2). Fig. 5 shows that this transfer helps find better HPs, demonstrating the added value of meta-learning besides PPE training of $f(\cdot )$ and surrogate initialization.