1 Introduction↩︎

With the rapid advancement of the powerful learning abilities of Deep Neural Networks (DNNs) [1], [2], the trustworthiness of DNNs in security-sensitive scenarios has attracted considerable attention in recent years [3], [4]. Generally, samples from the training set and test set of DNNs are viewed as data from some In Distribution (InD) \(\mathbb{P}_{\rm in}\), while samples from other data sets are regarded as those from a different distribution \(\mathbb{P}_{\rm out}\), i.e., Out-of-Distribution (OoD) data. In practical deployments, DNNs trained on InD data can encounter OoD data and yield unreliable results with potential risks. Therefore, detecting whether a new sample is from \(\mathbb{P}_{\rm in}\) or \(\mathbb{P}_{\rm out}\) has been a valuable research topic in trustworthy deep learning, namely OoD detection [5].

Great efforts have been taken to put forward the research on OoD detection from varied perspectives. The key idea of those works lies in the proper use of different responses from DNNs, i.e., the logits [7], [8], gradients [9], [10], and features [11]–[13], to characterize the disparity between InD and OoD data. Among those utilized responses, predictive logits merely encode limited and coarse-grained categorical information, while the parameter gradients necessitate computationally intensive backward propagation processes. More focus has been shed on exploring the features through efficient forward processes, as rich representations in feature spaces enable greater flexibility for more nuanced characterization of the InD-OoD disparity, which is also the main interest in this work.

In feature-based OoD detection, a powerful paradigm is feature rectification, which operates on the premise that extremely large or small feature activations are correlated with anomalous OoD predictions. Such extreme values in features are then clipped (rectified) in different ways to suppress OoD feature responses [11], [14]–[20]. By contrast, another line of work aims at directly measuring the disparity between InD and OoD features through appropriate distances, e.g., Mahalanobis [21], [22] and \(\ell_2\) distances [12], [23] and other distance metrics [24], [25]. Despite their empirical success, the understandings on the InD-OoD disparity of these methods still remain limited. In feature rectification, the clipping is conducted indiscriminately across all dimensions, which risks discarding useful feature responses for InD predictions. For instance, globally removing the top-10% of feature values over all dimensions is shown to cause nearly a 1.3% accuracy drop on InD data [11]. In distance-based detection, it is assumed that the distance metrics can adequately capture the InD-OoD disparities in the feature space. However, those distance metrics fail fundamentally when handling non-linear patterns commonly encountered in real-world data. An example is presented in [25] that the \(\ell_2\) distance [12] fails to distinguish InD and OoD given a non-linear data distribution of a Swiss Roll shape. These findings underscore the importance of more nuanced interpretations on the InD-OoD disparity in the feature space.

In this work, we take the perspective of exploring the non-linear feature subspace, where InD data can be well described and yet OoD data cannot. To be specific, InD features from DNNs are commonly quite abstract and can intrinsically reside in a low-dimensional subspace, while the OoD features inherently cannot be well characterized by this subspace. Hence, such differences in this subspace can be an effective tool for distinguishing OoD data from InD data. Our perspective fundamentally differs from the aforementioned paradigms that directly operate in the whole feature space from DNNs. Instead, our work focuses on investigating the intrinsic patterns of features in a subspace that well distinguish InD from OoD. We further reveal that the immediate utilization of features or a naive linear subspace from InD data is insufficient in separating OoD data, due to the non-linear characteristics of real-world feature distributions, as discussed in [13], [26], [27]. Nevertheless, the non-linear patterns that relate to the InD-OoD separability have not been fully exploited, and it still remains a significant and open question to identify a discriminative non-linear feature subspace for OoD detection.

In our method, the framework of Kernel Principal Component Analysis (KPCA) [28], [29] is leveraged to construct the non-linear feature subspace, where the InD-OoD disparities are sufficiently revealed. Given a DNN \(f(\boldsymbol{x}):\mathbb{R}^d\rightarrow\mathbb{R}^c\) well-trained on InD data, KPCA is applied to the penultimate layer features \(\boldsymbol{z}\in\mathbb{R}^m\) of InD training samples and learns a non-linear subspace spanned by the principal components. In inference, given features \(\boldsymbol{\hat{z}}\) of an unknown sample \(\boldsymbol{\hat{x}}\), one can obtain the reconstructed counterpart of \(\boldsymbol{\hat{z}}\) by projecting \(\boldsymbol{\hat{z}}\) to the non-linear subspace and re-projecting it back. Consequently, the reconstruction error between \(\boldsymbol{\hat{z}}\) and its reconstructed counterpart can reflect the InD-OoD disparities and thereby serves as a detection metric. Here, InD features are compactly allocated along the axes of principal components, leading to small reconstruction errors, while OoD features, which inherently are not well learned with this subspace, give significantly larger reconstruction errors.

When applying KPCA to the OoD detection task, we emphasize two crucial issues w.r.t. efficacy and efficiency.

• Non-linear kernel. By deploying KPCA, a non-linear mapping \(\phi\) with its inducing kernel \(k\), i.e., \(k(\boldsymbol{z}_1,\boldsymbol{z}_2)=\langle\phi(\boldsymbol{z}_1),\phi(\boldsymbol{z}_2)\rangle\), is imposed on input features \(\boldsymbol{z}\). To achieve effective OoD detection, the key is the identification of a suitable \(k\) or \(\phi\) that well models the non-linearity reflecting the InD-OoD disparities in the \(\boldsymbol{z}\)-space.

• Computational complexity. KPCA is generally conducted on the kernel matrix \({\boldsymbol{K}}\in\mathbb{R}^{N_{\rm tr}\times N_{\rm tr}}\) of \(N_{\rm tr}\) training samples. Obviously, when applied to large-scale detection scenarios with a huge InD data size \(N_{\rm tr}\), such as \(N_{\rm tr}=\) 1,281,167 of the ImageNet-1K [30] as InD, KPCA faces nearly prohibitive calculations and a significantly high computational complexity.

In this work, we formulate a KPCA OoD detection framework with the aforementioned two issues resolved. Regarding the kernel selection, we reveal two vital non-linear patterns that closely relate to the InD-OoD disparities in the \(\boldsymbol{z}\)-space, and deduce a Cosine-Gaussian kernel that effectively characterizes such non-linearity. KPCA w.r.t. this Cosine-Gaussian kernel promotes the separability between InD and OoD features and produces substantially improved discriminative reconstruction errors than PCA [31], [32], as demonstrated in Figure 1. On the other hand, to alleviate huge computations on the kernel matrix in the \(\boldsymbol{z}\)-space, we introduce explicit mappings \(\Phi\) to approximate the Cosine-Gaussian kernel. The approximated mapping \(\Phi\) enables KPCA to learn principal components in the \(\Phi(\boldsymbol{z})\)-space and significantly reduces the computational complexity of reconstruction errors. Moreover, in the context of OoD detection, \(\Phi\) is also expected to benefit the differentiation between InD and OoD. In this regard, we explore two representative mappings: the data-independent Random Fourier Features [33] (RFFs) and the data-dependent Nyström method [34], and further refine the latter by involving task-specific insights on the InD data confidence. Our refined Nyström allows KPCA reconstruction errors to be even sensitive to distribution shifts and brings stronger detection results.

To summarize, this study further develops the core idea of KPCA-based reconstruction for OoD detection from our prior conference publication [35] into a formalized and principled KPCA detection framework, with main contributions below:

• On non-linear kernel selection. We reveal two non-linear patterns essential for InD-OoD separability: imbalanced feature norms and \(\ell_2\) feature distances, in Section 3. These two properties not only serve as principled justifications for the Cosine-Gaussian kernel proposed in [35], but also provide crucial design guidelines for selecting and understanding kernel representations specific to differentiate InD and OoD. These insights are neither presented nor sufficiently analyzed in [35].

• On task-driven kernel approximation. We incorporate a data-dependent Nyström approximation technique with a low-Energy sampling scheme specialized for the OoD detection task in Section 4.2. By reallocating landmarks toward boundary regions, this scheme actively promotes InD-OoD separability rather than simply preserving the global kernel reconstruction, yielding superior detection performance and reduced computational costs (Section 4.3). Together with the data-independent RFFs in [35], this work presents systematic explorations on efficient kernel approximation particularly tailored for OoD detection. Numerical approximation analyzes are provided in Section 4.4.

• On learnable kernel representation. We further explore a parametric realization of our KPCA OoD detection framework, as an extension of the non-parametric Cosine-Gaussian kernel in [35]. This parametric learning paradigm supports learnable representations by optimizing kernel hyper-parameters and training neural networks with varied objectives, moving beyond fixed feature projections, as in Section 4.5 and Appendix 10. These primary and yet valuable explorations address the limitation noted in [35] by showcasing data-driven kernel optimization for future work, and also further validate the flexibility of our framework.

• Regarding empirical results. We conduct extensive experiments in Section 5 to validate the new State-Of-The-Art (SOTA) results and low computational demands of our KPCA detection framework, including comparisons with a broader variety of latest strong baselines and in-depth analyses for the two approximation methods.

In the remainder, the background knowledge is outlined in Section 2. Section 3 presents the non-linear kernel selection in detail and Section 4 investigates our approximation techniques for efficient computations and explores learnable kernel representations. Extensive empirical results are shown in Section 5. Related works and concluding discussions are enclosed in Section 6 and Section 7, respectively.

2 Background↩︎

2.1 Out-of-Distribution Detection↩︎

Generally, an OoD detection method justifies whether an input is from InD \(\mathbb{P}_{\rm in}\) or OoD \(\mathbb{P}_{\rm out}\) by a well-designed scoring function \(S(\cdot)\) as follows: \[\label{eq:ood-scoring} \text{category\;of\;}\boldsymbol{x}= \left\{ \begin{array}{ll} \mathrm{InD},&S(\boldsymbol{x})\geq s,\\ \mathrm{OoD},&S(\boldsymbol{x})<s. \end{array} \right.\tag{1}\] The scoring function \(S(\cdot)\) assigns a score \(S(\boldsymbol{x})\) for an input \(\boldsymbol{x}\). If \(S(\boldsymbol{x})\) is greater than a threshold \(s\), \(\boldsymbol{x}\) is viewed as an InD sample, and vice versa. The threshold \(s\) is usually selected such that most InD samples of the test dataset can be correctly identified. Obviously, the detection performance depends on how well the scoring function \(S(\cdot)\) characterizes the InD-OoD disparity. Existing methods leverage different outputs from DNNs and design justified scores correspondingly; a thorough review can refer to Section 6.

2.2 PCA for Out-of-Distribution Detection↩︎

The linear method, PCA [31], [32], is considered for OoD detection [13]. For inputs \(\boldsymbol{x}\in\mathbb{R}^d\), a well-trained DNN \(f:\mathbb{R}^d\rightarrow\mathbb{R}^c\) learns features \(\boldsymbol{z}\in\mathbb{R}^m\) before the last linear layer. In the learning phase, PCA firstly calculates the centered covariance matrix \({\boldsymbol{\Sigma}}\in\mathbb{R}^{m\times m}\) on features \(\{\boldsymbol{z}_i\}_{i=1}^{N_{\rm tr}}\) of the training (InD) data \(\{\boldsymbol{x}_i\}_{i=1}^{N_{\rm tr}}\): \[\label{eq:covar-mat} \boldsymbol{\Sigma}=\sum\nolimits_{i=1}^{N_{\rm tr}}\left(\boldsymbol{z}_i-\boldsymbol{\mu}_{\rm tr} \right)\left(\boldsymbol{z}_i-\boldsymbol{\mu}_{\rm tr}\right)^\top,\tag{2}\] with \(\boldsymbol{\mu}_{\rm tr}={1}/{N_{\rm tr}}\sum_{i=1}^{N_{\rm tr}}\boldsymbol{z}_i\). Through the eigendecomposition \(\boldsymbol{\Sigma}={\boldsymbol{U}}{\boldsymbol{\Lambda}}{\boldsymbol{U}}^\top\), the projection matrix \({\boldsymbol{U}}_q\in\mathbb{R}^{m\times q}\) is obtained by taking the first \(q\) columns of the eigenvector matrix \({\boldsymbol{U}}\in\mathbb{R}^{m\times m}\) w.r.t. the top-\(q\) eigenvalues in \({\boldsymbol{\Lambda}}\in\mathbb{R}^{m\times m}\).

In the inference phase, given a new sample \(\boldsymbol{\hat{x}}\in\mathbb{R}^d\) and its feature \(\boldsymbol{\hat{z}}\in\mathbb{R}^m\) from the DNN \(f\), we can project the centered \(\boldsymbol{\hat{z}}-\boldsymbol{\mu}_{\rm tr}\) to the \({\boldsymbol{U}}_q\)-subspace and re-project it back. The reconstruction error is computed as: \[\label{eq:reconstruction-error} e(\boldsymbol{\hat{x}})=\left\Vert{\boldsymbol{U}}_q{\boldsymbol{U}}_q^\top(\boldsymbol{\hat{z}}-\boldsymbol{\mu}_{\rm tr})-(\boldsymbol{\hat{z}}-\boldsymbol{\mu}_{\rm tr})\right\Vert_2.\tag{3}\] The subspace spanned by \({\boldsymbol{U}}_q\) is learned from InD data and thus gives high variances along principal components with informative patterns of InD, thereby yielding small reconstruction errors. In contrast, OoD data exhibits different patterns from InD data. Thus, in the low-dimensional \({\boldsymbol{U}}_q\)-subspace, OoD data is prone to produce large reconstruction errors along these extracted principal components. The scoring function with PCA for OoD detection is thereby set as \(S(\boldsymbol{\hat{x}})=-e(\boldsymbol{\hat{x}})\).

2.3 Kernel Approximation↩︎

We outline the approximation techniques adopted in our KPCA detection framework. In large-scale kernel methods, the expensive computations have been a long-standing problem, as an \(N_{\rm tr}\times N_{\rm tr}\) kernel matrix \(\boldsymbol{K}\) on training data requires \(\mathcal{O}(N_{\rm tr}^2)\) kernel evaluations, \(\mathcal{O}(N_{\rm tr}^2)\) space complexity, and \(\mathcal{O}(N_{\rm tr}^3)\) time complexity in solving the optimization problem. To alleviate such computational burden, the data-independent random Fourier features [33] and the data-dependent Nyström method [34] are two mainstream methods.

2.3.0.1 Random Fourier features

Random Fourier Features (RFFs) [33] deploy explicit mappings with random features to approximate the kernel function \(k\). RFFs are based on Bochner’s theorem [36] and construct random features \(\phi_{\rm rff}\) for a shift-invariant kernel \(k(\boldsymbol{z}_1,\boldsymbol{z}_2)=k(\boldsymbol{z}_1-\boldsymbol{z}_2)\): \[\begin{align} \label{eq:rff} \phi_{\rm rff}(\boldsymbol{z}) &\triangleq\sqrt{\frac{2}{M_r}}\left[\phi_1(\boldsymbol{z}),\cdots,\phi_{M_r}(\boldsymbol{z})\right],\\ \phi_i(\boldsymbol{z}) &=\cos\;(\boldsymbol{z}^\top\boldsymbol{\omega}_i+u_i),i=1,\cdots,M_r, \end{align}\tag{4}\] where \(M_r\) denotes the number of RFFs, and \(\boldsymbol{\omega}_i\in\mathbb{R}^m\) and \(u_i\in\mathbb{R}\) are i.i.d. sampled from the Fourier transform of the kernel function \(k(\cdot)\) and a uniform distribution \(\mathcal{U}(0,2\pi)\), respectively. We highlight two key properties of RFFs. (i) Computing the explicit mapping \(\phi_{\rm rff}(\boldsymbol{z})\in\mathbb{R}^{M_r}\), rather than the kernel matrix \(\boldsymbol{K}\), can be significantly more efficient when \(M_r\ll N_{\rm tr}\), while one could still guarantee \(k(\boldsymbol{z}_1,\boldsymbol{z}_2)\approx\phi_{\rm rff}(\boldsymbol{z}_1)^\top\phi_{\rm rff}(\boldsymbol{z}_2)\)[33]. (ii) The sampling distributions of \(\boldsymbol{\omega}_i\) and \(u_i\) are data-agnostic, and thereby RFFs are data-independent.

2.3.0.2 Nyström method

Instead of the explicit random features, the Nyström method [34] presents low-rank approximation to the kernel matrix through finite sampling. Firstly, \(M_n\) landmark samples \(\{\boldsymbol{\tilde{z}}_i\}_{i=1}^{M_n}\) are selected from the training set \(\{\boldsymbol{z}_i\}_{i=1}^{N_{\rm tr}}\) (\(M_n\ll N_{\rm tr}\)), and then we can draw sub-matrices \({\boldsymbol{\tilde{K}}}\in\mathbb{R}^{{M_n}\times{M_n}}\) and \({\boldsymbol{\bar} K}\in\mathbb{R}^{{N_{\rm tr}}\times{M_n}}\) from the full kernel matrix \(\boldsymbol{K}\) as \({\boldsymbol{\tilde{K}}}_{ij}=k(\boldsymbol{\tilde{z}}_i,\boldsymbol{\tilde{z}}_j)\) and \({\boldsymbol{\bar} K}_{ij}=k(\boldsymbol{z}_i,\boldsymbol{\tilde{z}}_j)\). Nyström method constructs a low-rank approximation of \(\boldsymbol{K}\) as \({\boldsymbol{\tilde{K}}}_n=\boldsymbol{\bar} K\boldsymbol{\tilde{K}}^\dagger\boldsymbol{\bar} K^\top\), where \(^\dagger\) denotes the matrix pseudo-inverse. Obviously, Nyström method is data-dependent and accelerates computations by working on the approximation associated with the selected \(M_n\) landmarks.

3 Non-Linear Kernel for OoD Detection↩︎

In our work, we leverage Kernel PCA (KPCA) [28], [29] to identify discriminative non-linear feature subspaces for distinguishing InD and OoD data. The key of KPCA lies in finding proper kernels to model the non-linearity that closely relates to InD-OoD separability in the \(\boldsymbol{z}\)-space, so as for discriminative non-linear principal components and distinguishable reconstruction errors on InD and OoD data.

Our KPCA detection framework is illustrated in Figure 2. By analyzing InD and OoD features in the \(\boldsymbol{z}\)-space, we identify two non-linear patterns that reflect their disparities and derive a Cosine-Gaussian kernel to model such non-linearity: alleviating the adverse imbalance of feature norms through a Cosine kernel in Section 3.1 and promoting the beneficial feature distance relation by a Gaussian kernel in Section 3.2.

3.1 Adverse Imbalance of Feature Norms↩︎

Since InD and OoD data are assumed to be from different distributions, a substantial gap exists in their feature norms \(\|\boldsymbol{z}\|_2\). As shown in Figure 3 (a), samples in the CIFAR10 training and test datasets are from InD, and thus have similar feature norms, while samples from OoD datasets exhibit significant deviations in feature norms. In this subsection, we reveal that such norm imbalance between InD and OoD features has an adverse impact for OoD detection by violating the zero-mean assumption, when simply considering the linear subspace from PCA. Then, we further show that a Cosine kernel \(k_{\rm cos}\) can effectively mitigate this issue with KPCA.

An essential pre-processing step of PCA is the centering on the inputs, i.e., inputs subtracted by their means in both learning and inference phases (ref. \((\boldsymbol{z}_i-\boldsymbol{\mu}_{\rm tr})\) in Eqn.@eq:eq:covar-mat and \((\boldsymbol{\hat{z}}-\boldsymbol{\mu}_{\rm tr})\) in Eqn.@eq:eq:reconstruction-error ). In the learning phase, centering is applied to the training data for computing the covariance matrix and the principal components. Particularly, in inference, the centering is also required for given new inputs. In OoD detection, the available feature mean for centering is the mean of InD training features, i.e., \(\boldsymbol{\mu}_{\rm tr}\) in Eqn.@eq:eq:covar-mat , since the feature mean of OoD is unknown. Meanwhile, note that the InD and OoD feature norms are imbalanced, which naturally induces a significant offset between their respective means, as shown by the right dashed line in Figure 3 (b). Therefore, centering OoD features using the InD feature means \(\boldsymbol{\mu}_{\rm tr}\) is impractical for PCA, which results in misleading projections in the subspace and poor performance of reconstruction errors in Figure 3 (c).

In this work, we note that a Cosine kernel \(k_{\rm cos}\) defined below can well address this issue. \[\begin{align} \label{eq:kernel-cosine} k_{\rm cos}(\boldsymbol{z}_1,\boldsymbol{z}_2) &=\frac{\boldsymbol{z}_1^\top\boldsymbol{z}_2}{\|\boldsymbol{z}_1\|_2\cdot\|\boldsymbol{z}_2\|_2} =\phi_{\rm cos}(\boldsymbol{z}_1)^\top\phi_{\rm cos}(\boldsymbol{z}_2),\\ \phi_{\rm cos}(\boldsymbol{z})&=\frac{\boldsymbol{z}}{\|\boldsymbol{z}\|_2}. \end{align}\tag{5}\] \(k_{\rm cos}\) is exactly induced from a non-linear mapping \(\phi_{\rm cos}(\boldsymbol{z})\) that restricts inputs \(\boldsymbol{z}\) onto a unit norm ball. By this construction, given the InD and OoD features, \(k_{\rm cos}\) inherently maps them to the unit sphere and thereby mitigates the adverse impact of their imbalanced feature norms. In this way, the offset between InD and OoD feature means gets significantly reduced, as indicated by the left solid shorter line in Figure 3 (b). Therefore, the centering based on \(\boldsymbol{\mu}_{\rm tr}\) w.r.t. the training data can now allocate OoD features nearby the same origin with InD features, so that the projection matrix learned from InD data can also be effective for OoD data, resulting in discriminative reconstruction errors in Figure 3 (d). In other words, a justified \(\phi_{\rm cos}(\boldsymbol{z})\)-space w.r.t. the cosine kernel \(k_{\rm cos}\), instead of the original \(\boldsymbol{z}\)-space, ensures that the subspace spanned by the principal components can well characterize the InD-OoD disparity.

3.2 Beneficial feature distance relation↩︎

After the imbalance of InD and OoD feature norms gets alleviated through \(k_{\rm cos}\), the resulting \(\phi_{\rm cos}(\boldsymbol{z})\)-space further enables explorations on another non-linear pattern related to the InD-OoD disparity, i.e., the beneficial \(\ell_2\) feature distance relation, which could even promote the InD-OoD separability.

In Figure 4, Multi-Dimensional Scaling (MDS) [40] is applied to InD and OoD data with and without the cosine kernel \(k_{\rm cos}\), respectively. MDS seeks low-dimensional embeddings where the \(\ell_2\) distance aligns well with that in the original space, making it an effective tool for analyzing the underlying \(\ell_2\) distance structure of the data. As illustrated in Figure 4, InD data in the \(\phi_{\rm cos}(\boldsymbol{z})\)-space is more concentrated w.r.t. the MDS embeddings built from the \(\ell_2\) distance information. Aside from the MDS visualizations, another work [12] directly calculates the \(\ell_2\) distances on \(\ell_2\)-normalized InD and OoD features as the detection score. Empirical results in [12] also indicate that the InD-InD \(\ell_2\) distances are significantly smaller than the InD-OoD \(\ell_2\) distances in the \(\phi_{\rm cos}(\boldsymbol{z})\)-space. All these evidences suggest (i) the insufficiency of the cosine kernel \(k_{\rm cos}\) alone in capturing the non-linearity related to the InD-OoD disparity and (ii) the promising potentials of leveraging the \(\ell_2\) distance relation in the \(\phi_{\rm cos}(\boldsymbol{z})\)-space for separating InD and OoD data.

Note that a Gaussian kernel \(k_{\rm gau}\), defined as \[\label{eq:kernel-gau} k_{\rm gau}(\boldsymbol{z}_1,\boldsymbol{z}_2)=e^{-\gamma\|\boldsymbol{z}_1-\boldsymbol{z}_2\|^2_2},\tag{6}\] is exactly able to preserve the \(\ell_2\) distance information between samples. Therefore, based on the above investigations, we leverage the Gaussian kernel \(k_{\rm gau}\) on top of the cosine kernel \(k_{\rm cos}\) to further model the discriminative \(\ell_2\) feature distance existing in InD and OoD data in the \(\phi_{\rm cos}(\boldsymbol{z})\)-space.

To sum up, the eventual kernel we propose for the OoD detection task is a composite Cosine-Gaussian kernel. This Cosine-Gaussian kernel models two vital non-linear properties hidden in InD and OoD features: alleviating the adverse imbalance of feature norms \(\|\boldsymbol{z}\|_2\) and promoting the beneficial \(\ell_2\) distance relation, and finally enables discriminative non-linear feature subspaces for separating InD and OoD data.

4 Kernel Approximation for OoD Detection↩︎

Given the derived Cosine-Gaussian kernel for modeling the non-linearity, we even face challenges of the nearly prohibitive calculations on the kernel matrix \({\boldsymbol{K}}\in\mathbb{R}^{N_{\rm tr}\times N_{\rm tr}}\) under large-scale detection scenarios with a huge InD data size \(N_{\rm tr}\), e.g., the common ImageNet-1K training set with \(N_{\rm tr}=\)​1,281,167. For efficient computations, we introduce approximation techniques in kernel methods, i.e., using an explicit non-linear mapping \(\Phi\) to approximate the Cosine-Gaussian kernel, as illustrated in our framework of Figure 2. In this way, KPCA learns non-linear principal components in the mapped \(\Phi\)-space, which excludes the kernel matrix \(\boldsymbol{K}\) and leads to a significantly reduced computational complexity for calculating the reconstruction error as the detection score.

In the composite Cosine-Gaussian kernel, the Cosine kernel \(k_{\rm cos}\) directly admits an exact mapping \(\phi_{\rm cos}\) in Eqn.@eq:eq:kernel-cosine . In contrast, the mapping associated with the Gaussian kernel \(k_{\rm gau}\) is infinite-dimensional. Nevertheless, \(k_{\rm gau}\) can still be effectively approximated through finite-dimensional mappings. Particularly, we explore two representative approximation mappings that differ in whether data is involved: (i) data-independent random Fourier features [33] in Section 4.1, and (ii) data-dependent Nyström approximation [34] specifically tailored for OoD detection in Section 4.2. Discussions on the advantageous efficiency and analytical approximation properties are presented in Section 4.3 and Section 4.4.

4.1 Random Fourier Features↩︎

The Random Fourier Features (RFFs) [33] are leveraged to approximate the Gaussian kernel \(k_{\rm gau}\). As outlined in Section 2.3, to build the approximated mapping \(\phi_{\rm rff}\) in Eqn.@eq:eq:rff , \(2M_r\) randomly-sampled weights \(\boldsymbol{w}\) and \(u\) are required. To be specific, \(M_r\) weights \(u\) are sampled from a uniform distribution: \(u\sim\mathcal{U}(0,2\pi)\), and the sampling distribution for \(\boldsymbol{\omega}\) is the Fourier transform of the Gaussian kernel \(k_{\rm gau}\), i.e., \(\boldsymbol{\omega}\sim\mathcal{N}({\boldsymbol{0}},\sqrt{2\gamma}{\boldsymbol{I}}_m)\), where \(\gamma\) is the Gaussian kernel width. Hence, \(\phi_{\rm rff}\) in RFFs is agnostic of data and can be straightforwardly applied.

Note that the Cosine-Gaussian kernel in our KPCA detection method is a composite of kernel functions. The final non-linear mapping \(\Phi\) is then formulated as \(\Phi(\boldsymbol{z})\triangleq\phi_{\rm rff}(\phi_{\rm cos}(\boldsymbol{z}))\). Given the mapping \(\Phi\), in the learning phase, the training InD features \(\{\boldsymbol{z}_i\}_{i=1}^{N_{\rm tr}}\) are mapped to \(\Phi\)-space, and a projection matrix \({\boldsymbol{U}}_q^\Phi\) is obtained by the eigendecomposition on the covariance matrix \({\boldsymbol{\Sigma}}^\Phi\) induced from \(\{\Phi(\boldsymbol{z}_i)\}_{i=1}^{N_{\rm tr}}\). In the inference phase, features \(\boldsymbol{\hat{z}}\) of a new sample \(\boldsymbol{\hat{x}}\) are firstly mapped to \(\Phi(\boldsymbol{\hat{z}})\) and then compute the reconstruction error \(e^\Phi\) based on \({\boldsymbol{U}}_q^\Phi\) and the mean \(\boldsymbol{\mu}^\Phi_{\rm tr}\). Algorithm 5 outlines the key steps.

4.2 Nyström Approximation↩︎

In this section, we elaborate how to leverage the Nyström method [34] to construct an explicit mapping to approximate the Gaussian kernel for efficient OoD detection. As outlined in Section 2.3, Nyström is commonly executed to build a low-rank approximation matrix \({\boldsymbol{\tilde{K}}}_n\) based on \(M_n\) landmarks \(\{\boldsymbol{\tilde{z}}_i\}_{i=1}^{M_n}\) selected from \(N_{\rm tr}\) training samples \(\{\boldsymbol{z}_i\}_{i=1}^{N_{\rm tr}}\). This approximated \({\boldsymbol{\tilde{K}}}_n\) can further be decomposed as: \[\begin{align} \label{eq:nys} [{\boldsymbol{\tilde{K}}}_n]_{ij}=\phi_{\rm nys}(\boldsymbol{z}_i)^\top\phi_{\rm nys}(\boldsymbol{z}_j),\quad \phi_{\rm nys}(\boldsymbol{z}) \triangleq{\boldsymbol{\tilde{\Lambda}}}^{-1/2}{\boldsymbol{\tilde{U}}}^\top[k(\boldsymbol{z},\boldsymbol{\tilde{z}}_1),\cdots,k(\boldsymbol{z},\boldsymbol{\tilde{z}}_{M_n})]^\top. \end{align}\tag{7}\] Note that \({\boldsymbol{\tilde{U}}}\) and \({\boldsymbol{\tilde{\Lambda}}}\) are obtained through the eigendecomposition on the submatrix \({\boldsymbol{\tilde{K}}}={\boldsymbol{\tilde{U}}}{\boldsymbol{\tilde{\Lambda}}}{\boldsymbol{\tilde{U}}}^\top\) with \({\boldsymbol{\tilde{K}}}_{ij}=k(\boldsymbol{\tilde{z}}_i,\boldsymbol{\tilde{z}}_j)\). In this sense, the explicit mapping \(\phi_{\rm nys}\) can be adopted as a data-driven approximation towards the Gaussian kernel \(k_{\rm gau}\) through the selected \(M_n\) landmarks.

Obviously, the sampling scheme for the landmarks directly determines the approximation performance of \(\phi_{\rm nys}\), with studies ranging from naive uniform sampling to more sophisticated strategies [41], [42]. Nevertheless, in OoD detection contexts, the approximation performance of the Nyström mapping is no longer the main concern; instead, we aim to identify a set of particular InD landmarks to build the approximated mapping, such that the mapped space w.r.t. these specific landmarks can help reflect the InD-OoD disparity and facilitate the subspace learning for effective OoD detection.

In this work, an energy-based sampling scheme is designed for Nyström, tailored to boost OoD detection performance. To be specific, we consider the following energy function \(E\) applied to the logits of training samples \(\{\boldsymbol{x}_i\}_{i=1}^{N_{\rm tr}}\) from the well-trained DNN \(f\): \[\label{eq:energy-func} E(\boldsymbol{x};f)=E(\boldsymbol{z};f)=T\cdot\log\sum_{i=1}^{c}{\rm exp}\left(\frac{f_i(\boldsymbol{x})}{T}\right),\tag{8}\] where \(f_i(\boldsymbol{x})\) denotes the \(i\)-th element of the logits \(f(\boldsymbol{x})\in\mathbb{R}^c\) and \(T\) indicates the temperature coefficient. Here, high-energy samples correspond to those predictions, where the DNN \(f\) assigns a dominant logit to one class, implying that those samples are likely from InD. In contrast, low-energy samples demonstrate dispersed or nearly uniform logit distributions, indicating that they tend to align with OoD [7].

The proposed energy-based sampling scheme selects \(M_n\) low-energy InD training samples \(\{\boldsymbol{\tilde{x}}_i\}_{i=1}^{M_n}\) w.r.t. the smallest energy values \(E(\boldsymbol{\tilde{x}}_i;f)\) as landmarks to build the Nyström approximation mapping \(\phi_{\rm nys}\) of Eqn.@eq:eq:nys . These landmarks are from InD and typically reside near the InD-OoD boundary, where \(f\) is less confident on them. For KPCA-based OoD detection, the detection threshold is governed by the largest gap in landmark coverage over the InD support, since the reconstruction error at any point can be controlled by its distance to nearby landmarks. Uniform or density-proportional sampling concentrates landmarks in high-density regions, leaving large coverage gaps near low-density boundary areas, where the worst-case reconstruction error tends to be most pronounced. Our low-Energy scheme reallocates landmarks toward these under-covered boundary regions, thereby shrinking the largest coverage gap and suppressing the detection threshold. This yields a more compact acceptance region and directly limits false acceptance of OoD samples. We formalize this reasoning as follows, with an intuitive illustration in Figure 6.

Based on the proposed low-energy supporting landmarks, the final non-linear mapping \(\Phi\) via Nyström approximation for the Cosine-Gaussian kernel is \(\Phi(\boldsymbol{z})\triangleq\phi_{\rm nys}(\phi_{\rm cos}(\boldsymbol{z}))\). The corresponding KPCA detection procedure is basically the same as KPCA via RFFs in Section 4.1, which is also outlined in Algorithm 5. We use KPCA\(_{\rm rff}\) and KPCA\(_{\rm nys}\) to denote our KPCA detection method via RFFs and Nyström, respectively.

4.3 Computation Complexity↩︎

With approximation schemes, the computational efficiency of our KPCA detection framework is greatly improved. As illustrated in Algorithm 5, the computation of the kernel matrix K w.r.t. \(N_{\rm tr}\) training samples is skipped. Particularly, in the inference phase, the KPCA reconstruction error \(e^\Phi\) requires the approximated mapping \(\Phi\), the projection matrix \({\boldsymbol{U}}^\Phi_q\) and the mean mapped training feature vector \(\boldsymbol{\mu}^\Phi\). Both \({\boldsymbol{U}}^\Phi_q\) and \(\boldsymbol{\mu}^\Phi\) are computed only once in the learning phase and thus stored in preparation for inference. Therefore, the computation cost of \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\) in inference comes from the construction of the explicit mapping \(\Phi\) on new features \(\boldsymbol{\hat{z}}\).

Regarding \(\Phi\), the primary mapping \(\phi_{\rm cos}\) w.r.t. the common cosine kernel \(k_{\rm cos}\) in \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\) is an in-place operation and does not require additional computations. Thus, the mappings \(\phi_{\rm rff}\) and \(\phi_{\rm nys}\) to approximate the Gaussian kernel \(k_{\rm gau}\) take the main computation:

• As illustrated in Eqn.@eq:eq:rff of \(\phi_{\rm rff}\), \(2M_r\) samplings of \(\boldsymbol{\omega}_i\) and \(u_i\), \(M_r\) dot-products and \(M_r\) additions are required for \(\phi_{\rm RFF}(\boldsymbol{\hat{z}})\). Accordingly, the time and memory complexity of \(\rm KPCA_{rff}\) is \({\cal O}(M_r)\).

• To build \(\phi_{\rm nys}(\boldsymbol{\hat{z}})\) by Eqn.@eq:eq:nys , two eigenmatrices \(\boldsymbol{\tilde{\Lambda}}\), \(\boldsymbol{\tilde{U}}\) and \(M_n\) kernel evaluations on the \(M_n\) landmarks \(\{\boldsymbol{\tilde{z}}_i\}_{i=1}^{M_n}\) are demanded. Hence, the time and memory complexity of \(\rm KPCA_{nys}\) is \({\cal O}(M_n)\).

Note that there exists a relevant method KNN [12] that also explores the imbalanced feature norms and the beneficial \(\ell_2\) distance for OoD detection. KNN takes a rather straightforward way and adopts the non-parametric \(\ell_2\)-distance nearest neighbor searching on \(\ell_2\)-normalized inputs as the score: \[\label{eq:knn-score} S_{\rm knn}(\boldsymbol{\hat{x}})=-\min_{i:1,\cdots,N_{\rm tr}}\left\|\frac{\boldsymbol{\hat{z}}}{\|\boldsymbol{\hat{z}}\|_2}-\frac{\boldsymbol{z}_i}{\|\boldsymbol{z}_i\|_2}\right\|_2.\tag{9}\] Aside from the distinctive kernel perspective, our KPCA further outperforms KNN in the computational overhead. As in Eqn.@eq:eq:knn-score , KNN requires that all the training features \(\{\boldsymbol{z}_i\}_{i=1}^{N_{\rm tr}}\) have to be stored at hand and iterated in inference, implying a heavy \(\mathcal{O}(N_{\rm tr})\) time and memory complexity. In contrast, the \({\cal O}(M_r)\)/\({\cal O}(M_n)\) of \(\rm KPCA_{rff}\)/\(\rm KPCA_{nys}\) is substantially more efficient than the \(\mathcal{O}(N_{\rm tr})\) of KNN given that \(M_r,M_n\ll N_{\rm tr}\). Detailed comparisons on detection performance and efficiency are provided in Sections 5.2 and 5.3.

4.4 Analytical Discussion on Approximation Performance↩︎

The primary objective of our approximated KPCA is to enhance OoD detection performance. In this section, we supplement an analysis of the approximation performance on InD and OoD data for a comprehensive investigation into our detection method. While the statistical optimality of approximated KPCA via RFFs and Nyström has been extensively studied within the traditional machine learning regime under well-defined assumptions [43]–[48], we extend the analysis to this deep learning regime, bridge theoretical approximation guarantees with practical detection scenarios, and provide actionable insights for implementation.

We consider the empirical version for the exact KPCA on a finite training set \(\{\boldsymbol{z}_i\}_{i=1}^{N_{\rm tr}}\) without any approximations. This requires that the reconstruction error should be calculated in the original \(\boldsymbol{z}\)-space based on the kernel matrix \({\boldsymbol{K}}\in\mathbb{R}^{N_{\rm tr}\times N_{\rm tr}}\). To be specific, projections to the principal subspace based on \(\boldsymbol{K}\) can be easily implemented [28], [29], but how to reconstruct the projections in the principal subspace back to the original \(\boldsymbol{z}\)-space remains a non-trivial issue, known as the pre-image problem [49]. To address this issue, the following Proposition 2 [35] shows a flexible approach to directly obtain the KPCA reconstruction error \(e^{k}\) without building reconstructed features.

Given the eigen-decomposition on the kernel matrix \(\boldsymbol{K}\) of the training set \(\{\boldsymbol{z}_i\}_{i=1}^{N_{\rm tr}}\) as \({\boldsymbol{K}}={\boldsymbol{U}}^{k}{\boldsymbol{\Lambda}}^{k}{\boldsymbol{U}}^{{k}\top}\), and \(\boldsymbol{k}_{\boldsymbol{\hat{z}}}=[k(\boldsymbol{z}_1,\boldsymbol{\hat{z}}),\cdots,k(\boldsymbol{z}_{N_{\rm tr}},\boldsymbol{\hat{z}})]^\top\in\mathbb{R}^{N_{\rm tr}}\) as a vector of kernel values between new data \(\boldsymbol{\hat{z}}\) and \(\{\boldsymbol{z}_i\}_{i=1}^{N_{\rm tr}}\), we have Proposition 2 below for exact KPCA reconstruction errors \(e^k(\boldsymbol{\hat{z}})\) based on \(\boldsymbol{K}\) (no approximation) with proofs in Appendix 8.

Given Proposition 2, numerical comparisons can be executed between exact KPCA and our approximated KPCA, with results of reconstruction errors on InD and OoD data shown in Figure 7. As illustrated, for this practical OoD detection scenario within the deep learning scheme, the RFFs and energy-based Nyström lead to a marginal gap in the reconstruction errors when compared to exact KPCA, empirically verifying their approximation performance. In addition, the data-dependent Nyström achieves better convergence than the data-independent RFFs.

Again, we highlight that the approximation performance is not the focus of this study, and we recommend related literature [43]–[48] for more in-depth and insightful theoretical explorations. Instead, the essence of our work lies in (i) exploring the non-linearity in InD and OoD data via task-specific kernels, and (ii) facilitating OoD detection in practical large-scale scenarios via task-specific kernel approximations.

4.5 Explorations on Learnable Kernels↩︎

While the non-parametric Cosine-Gaussian kernel is validated with effective feature subspaces promoting InD-OoD separability, it would be interesting to further investigate learnable representations for optimizing non-linear feature subspaces. Motivated by this, we consider data-driven kernel hyper-parameter optimization and parametric neural network formulations, each tailored to varied learning objectives. These studies underscore an important insight: for learnable kernels, the objective function should be carefully designed to effectively capture distribution shifts, so that the representations are learned to be discriminative for InD and OoD in the non-linear low-dimensional feature subspace. Such primary investigations further demonstrate the potential of our framework for scenarios demanding higher flexibility and these tentative explorations may help inspire more comprehensive future work in this direction. Details on implementation and numerical results are provided in Appendix 10.

5 Experiments↩︎

5.1 Setups↩︎

In line with [23], [50], the proposed KPCA detection framework is mainly evaluated on the large-scale ImageNet-1K benchmark [30] to illustrate its advantages in effectiveness and efficiency. The ImageNet-1K dataset is more challenging and diverse than the classic CIFAR benchmark [37]: There are 1,281,167 training images of \(224\times224\times3\) within 1,000 categories in ImageNet-1K, while CIFAR10 only contains 50,000 \(32\times32\times3\) training images from 10 classes. Besides, multiple different network structures are involved in experiments, including ResNet [51], MobileNet [52] and ViT (Vision Transformer) [53] models.

For ImageNet-1K as InD, OoD datasets include iNaturalist [54], SUN [55], Places [39] and Textures [56], which have been widely adopted in existing methods. We select ResNet50 models [51] of standard training and supervised contrastive learning [57], MobileNetV2 [52] of standard training, and the prevalent ViT-B/16 [53] for a fair comparison. Images from ImageNet-1K and the paired OoD datasets are resized and cropped to \(224\times224\times3\) as inputs for ResNet50 and MobileNetV2, and to \(384\times384\times3\) for ViT-B/16, respectively.

\(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\) are compared with a wide variety of prevailing OoD detection methods, covering logits-based, gradients-based, and features-based ones. A thorough review of these approaches can be found in Section 6.

For the evaluation metrics, we employ the widely-used (i) False Positive Rate (FPR) of OoD samples with 95% true positive rate on the InD test dataset, and (ii) Area Under the Receiver Operating Characteristic curve (AUROC). The average FPR and AUROC values over the selected multiple OoD datasets are viewed as the final comparison metrics.

The source code of this work has been publicly released¹. All experiments are executed on 1 NVIDIA GeForce RTX 3090 GPU.

Section 5.2 presents comparisons with these strong baselines on the ImageNet-1K benchmark with ResNet50 and ViT-B/16. Additional experiments, including those on MobileNetV2 and CIFAR, are provided in Appendix 9 for reference, along with complete results w.r.t. the following Tables 3, 5, ¿tbl:tab:exp-ablation-sampling?.

5.2 Comparisons on Detection Performance↩︎

5.2.1 Results on ResNet↩︎

Table 1 shows the detection performance of various detection methods on ResNet50 models of standard training and regularized training. For the former, our KPCA employs the PyTorch-released ResNet50 checkpoint [64] that is trained by a standard cross-entropy loss. For the latter, our KPCA adopts the ResNet50 checkpoint released with KNN [12], which is trained with supervised contrastive learning [57]. In both cases, the detection score of KPCA is the negative of the reconstruction error \(S(\boldsymbol{\hat{x}})=-e^\Phi(\boldsymbol{\hat{x}})\).

In Table 1, our KPCA detection method achieves the lowest FPR and highest AUROC values, and indicates that exploring non-linear patterns is more advantageous than other compared methods in distinguishing OoD data from InD data. Besides, the substantial improvements of \(\rm KPCA_{nys}\) over \(\rm KPCA_{rff}\) indicate that the data-dependent Nyström approximation is more beneficial in learning a discriminative InD subspace than the data-independent RFFs.

5.2.2 Results on ViT↩︎

Table 2 shows comparisons on the ViT-B/16 model. We follow the settings in [23] and adopt a ViT-B/16 checkpoint that is sequentially pre-trained on ImageNet-21K and fine-tuned on ImageNet-1K. This transfer learning is a common and practical learning scheme. As shown in Table 2, \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\) are suitable for features learned by the visual attention mechanism of ViT and achieve superior performance than KNN [12], indicating the effectiveness of appropriate non-linear kernels. Besides, the ensemble of \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\) achieves new SOTA detection performance over other compared baselines.

5.2.3 Comparisons with feature rectification↩︎

A series of methods propose that the abnormal responses in features lead to over-confidence on OoD data and should be removed. Generally, those extremely large or small feature values are viewed as anomalous information causing OoD predictions. Therefore, a range of techniques have been developed to clip extreme feature values [11], [14]–[20], termed feature rectification. Feature rectification still relies on an additional detector applied to the refined features or logits to produce detection scores, yet it has demonstrated outstanding detection performance and also a highly-flexible compatibility with other features-based detection methods [12], [13].

Our KPCA detection method can be equipped with feature rectification for even improved detection results. To be specific, a fusion strategy is proposed in [13] to combine regularized PCA reconstruction errors with feature rectification. Thereby, for a fair comparison, we follow this fusion strategy in [13] and boost KPCA reconstruction errors via a pioneering, simple, and effective feature rectification method ReAct [11]. Table 3 presents comparisons with more feature rectification methods on ImageNet-1K with ResNet50.

Table 3 indicates the superior detection performance of KPCA boosted by feature rectification. Our KPCA equipped with ReAct outperforms other powerful feature rectification methods [14]–[19]. Besides, under the same feature-clipping technique, KPCA also achieves the lowest FPR and highest AUROC values among other strong baselines [9], [10], [13], [23], [65]. The potential of KPCA can be further enhanced by incorporating more advanced feature rectification techniques.

All these experiments support the critical role of the non-linearity for separating InD and OoD data. The derived Cosine-Gaussian kernel and the corresponding non-linear feature subspace well seize the InD-OoD disparities and produce reconstruction errors that are sensitive to distribution shifts with new SOTA detection results.

5.3 Comparisons on Computation Complexity↩︎

We provide numerical results on the time and memory complexity of our KPCA detection method in the inference phase, i.e., the computation cost for calculating the KPCA reconstruction error \(e^\Phi\) given features \(\boldsymbol{\hat{z}}\) of a new sample \(\boldsymbol{\hat{x}}\). Particularly, the KNN method [12] is incorporated as a reference baseline, since both the Cosine-Gaussian kernel and the nearest neighbor searching explore the imbalanced feature norms and the \(\ell_2\) distance relation for OoD detection but in rather different perspectives and implementations.

Table 4 shows detailed numerical comparisons on ImageNet-1K with ResNet50. In the inference phase for new features \(\boldsymbol{\hat{z}}\), it is essential for KNN [12] to store and iterate all the 1,281,167 training features for the nearest neighbor searching, costing nearly 20 GiB memory and 16 ms to calculate the nearest distance for \(\boldsymbol{\hat{z}}\). In contrast, as outlined in Algorithm 5, our KPCA constructs explicit mappings without keeping and visiting the whole training set in inference, and achieves a significantly cheap computation complexity:

• \(\rm KPCA_{rff}\) directly samples \(M_r=4,096\) weights of \(\boldsymbol{\omega}_i\) and \(u_i\) to obtain mapped features \(\Phi(\boldsymbol{\hat{z}})\), and adopts pre-calculated projection matrix \({\boldsymbol{U}}^\Phi_q\) and mean training vector \(\boldsymbol{\mu}^\Phi\) to determine the reconstruction error \(e^\Phi\).

• \(\rm KPCA_{nys}\) only needs to keep and iterate \(M_n=2,048\) support landmarks \(\{\boldsymbol{\tilde{z}}\}_{i=1}^{M_{n}}\) and pre-calculated matrices \(\boldsymbol{\tilde{\Lambda}}\), \(\boldsymbol{\tilde{U}}\), \({\boldsymbol{U}}^\Phi_q\) and \(\boldsymbol{\mu}^\Phi\) to acquire \(\Phi(\boldsymbol{\hat{z}})\) and \(e^\Phi\).

As shown in Table 4, both \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\) are highly resource-efficient compared with KNN, and complete inference in less than 1 ms and fewer than 100 MiB of memory occupancy. Besides, \(\rm KPCA_{nys}\) even outperforms \(\rm KPCA_{rff}\), indicating the superiority of the data-dependent approximation over data-independent random features.

5.4 Alternative Kernels↩︎

We explore alternative kernels for OoD detection, extending beyond the proposed Cosine-Gaussian kernel.

• A Laplacian kernel \(k_{\rm lap}\) characterizes the \(\ell_1\) distance between two samples \(\boldsymbol{z}_1\) and \(\boldsymbol{z}_2\): \[\label{eq:kernel-lap} k_{\rm lap}(\boldsymbol{z}_1,\boldsymbol{z}_2)=e^{-\gamma\|\boldsymbol{z}_1-\boldsymbol{z}_2\|_1}.\tag{10}\] The Laplacian kernel \(k_{\rm lap}\) is shift-invariant, thus RFFs of Eqn.@eq:eq:rff can be applied to approximate \(k_{\rm lap}\). Note that the Fourier transform of \(k_{\rm lap}\) to sample \(\boldsymbol{\omega}_i\) is a Cauchy distribution \(\boldsymbol{\omega}\sim\frac{\gamma^2}{\pi\gamma(\boldsymbol{\omega}^2+\gamma^2)}\).

• A Polynomial kernel \(k_{\rm poly}\) does not hold the \(\ell_1\) nor \(\ell_2\) distance-preserving property and is defined based on the inner product as follows: \[\label{eq:kernel-poly} k_{\rm poly}(\boldsymbol{z}_1,\boldsymbol{z}_2)=(\boldsymbol{z}_1^\top\boldsymbol{z}_2+c)^d.\tag{11}\] \(k_{\rm poly}\) is not shift-invariant and thereby the RFFs cannot be employed to approximate \(k_{\rm poly}\). We adopt another technique to obtain an explicit random mapping for \(k_{\rm poly}\), namely the Tensor Sketch approximation [68].

We evaluate these individual kernels and their concatenations with the Cosine kernel for OoD detection; results are compared comprehensively in Table 5. All experiments are executed on the ImageNet-1K benchmark and the PyTorch-released ResNet50 model. We can have the following observations.

5.4.0.1 The Cosine kernel is indispensable for OoD detection

Without the Cosine kernel, these individual Polynomial, Laplacian, and Gaussian kernels all show a substantial detection performance drop. Besides, KPCA w.r.t. a single Cosine kernel significantly enhances PCA. It implies that feature normalization via the Cosine kernel is essential for learning a discriminative subspace to separate InD and OoD data.

5.4.0.2 The Gaussian kernel shows the best detection results on top of the Cosine kernel

In Table 5, both Cosine-Laplacian kernel and Cosine-Polynomial kernel cannot bring detection performance gains compared to the single Cosine kernel, which illustrates that the \(\ell_1\)-distance relation from \(k_{\rm lap}\) and the inner-product information from \(k_{\rm poly}\) in the \(\phi_{\rm cos}(\boldsymbol{z})\)-space actually hurt the separability between InD and OoD features.

5.4.0.3 The data-dependent Nyström approximation outperforms the data-independent random features in OoD detection

For the three kernels of Cosine-Polynomial, Cosine-Laplacian, and Cosine-Gaussian, KPCA via Nyström achieves lower FPR and higher AUROC values than that via random features, which implies the superiority of data-dependent approximation over the data-independent way.

Ablation studies on the sampling scheme for Nyström in \(\rm KPCA_{nys}\). Average detection results are reported.

Detection performance of KPCA applied to intermediate-layer features. Average detection results are reported.

5.5 Ablation Studies↩︎

In our \(\rm KPCA_{nys}\), an energy-based sampling scheme is specifically devised for Nyström, which selects those low-energy InD training samples \(\{\boldsymbol{\tilde{x}}_i\}_{i=1}^{M_n}\) with the smallest-\(M_n\) energy values as support landmarks. This sampling scheme shows to produce discriminative non-linear principal components capturing InD-OoD disparities and improved detection results. Ablations are studied in this section to verify its effectiveness. Particularly, we consider another two sampling configurations as follows:

• A uniform sampling is widely adopted in Nyström [34], [41] and is investigated in OoD detection for ablations.

• Regarding the proposed energy-based sampling scheme, we consider those high-energy InD training samples with the largest-\(M_n\) energy values as landmarks for ablations.

Comparisons among different sampling schemes are presented in Table ¿tbl:tab:exp-ablation-sampling?, with full results in Table ¿tbl:response:tab:full-auroc? of Appendix 9.

As illustrated, our low-energy support landmarks outperform the uniformly-sampled landmarks for \(\rm KPCA_{nys}\), which indicates that appropriate landmarks in relation to this specific OoD detection task can bring detection performance gains. Besides, low-energy landmarks show to be superior over high-energy ones in separating InD and OoD with \(\rm KPCA_{nys}\). The reason can be that the approximation based on those boundary InD samples leads to reconstruction errors that are more sensitive to distribution shifts, as discussed in Section 4.2.

While our subspace learning is typically applied to penultimate-layer features, this study extends the analysis by evaluating KPCA on intermediate-layer features of a ResNet50 model to assess their discriminative capability. A typical ResNet50 architecture² consists of one beginning convolution block, followed by four sequential layer blocks (layer1, layer2, layer3 and layer4), and a final linear classification layer. Beyond its default use at layer4, we apply KPCA to features from earlier blocks (layer1, layer2 and layer3) to investigate performance in their respective non-linear subspaces with results shown in Table ¿tbl:tab:exp-interlayer-feat?.

As demonstrated, shallow-layer features (layer1 and layer2) does not yield effective non-linear subspaces to well separate InD and OoD data, while deeper features (layer3 and layer4) exhibit enhanced detection results. This observation aligns with the hierarchical learning of DNNs: shallow layers capture fine-grained image patterns and higher-level semantic discrimination emerges in deeper layers. Consequently, the penultimate-layer features (layer4), adopted in our work by default, demonstrate the strongest discriminative ability and achieve the best detection performance for both \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\). This choice is also supported by prior findings that penultimate-layer feature collapse can aid OoD detection [69].

5.6 Sensitivity Analysis↩︎

A comprehensive sensitivity analysis is executed to illustrate the effects of hyper-parameters in our KPCA detection framework. \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\) share two common hyper-parameters: the bandwidth \(\gamma\) of the Gaussian kernel and the number of columns \(q\) of the projection matrix \({\boldsymbol{U}}^\Phi_q\). Besides, their distinctive hyper-parameters are the number of RFFs \(M_r\) in \(\rm KPCA_{rff}\) and the number of support landmarks \(M_n\) in \(\rm KPCA_{nys}\). In the following, we discuss the influence of each hyper-parameter, and report detection results by varying one hyper-parameter with the others fixed. All experiments are conducted on the ImageNet-1K benchmark and the PyTorch-released ResNet50 checkpoint.

The column size \(q\) in the projection matrix \({\boldsymbol{U}}^\Phi_q\) indicates the number of preserved principal components and determines the amount of information captured by the projected subspace for InD and OoD data. Generally, \(q\) is selected as the minimum number of principal components required to capture a cumulative explained variance ratio that exceeds a given threshold. Thereby, we investigate the effect of \(q\) by exploring the detection performance under varied values of the explained variance ratio, which is calculated as the ratio of the sum of eigenvalues w.r.t. the preserved principal components over the sum of all eigenvalues.

Figure 8 illustrates the detection performance of \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\) under varied explained variance ratios. For \(\rm KPCA_{nys}\), a sufficiently large value of the explained variance ratio, i.e., over 99%, is essential to keep most principal components for superior detection results. Regarding \(\rm KPCA_{rff}\), a modest value of the explained variance ratio is instead suggested, which might be due to the fact that the random features make the useful information for distinguishing OoD samples concentrated in fewer principal components.

The Gaussian kernel width \(\gamma\) directly affects the mapped data distribution. For a large \(\gamma\), \(k_{\rm gau}(\boldsymbol{z}_1,\boldsymbol{z}_2)=e^{-\gamma\left\Vert\boldsymbol{z}_1-\boldsymbol{z}_2\right\Vert_2^2}\approx0\) for \(\boldsymbol{z}_1\neq\boldsymbol{z}_2\), which indicates that the mappings of \(\boldsymbol{z}_1\) and \(\boldsymbol{z}_2\) are (nearly) mutually-orthogonal. In this case, a PCA in the mapped space would become meaningless. For a small \(\gamma\), KPCA reconstruction errors will approach standard PCA ones, as discussed in [70].

Figure 9 demonstrates the FPR and AUROC values of varied Gaussian kernel widths \(\gamma\) in \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\). Clearly, neither a too large nor a too small kernel width can well characterize the patterns of InD-OoD disparities, and a mild value of \(\gamma\) should be carefully tuned in both \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\) for outstanding detection performance. Moreover, it can be observed that \(\rm KPCA_{nys}\) is significantly more sensitive to variations in \(\gamma\) compared to \(\rm KPCA_{rff}\). This difference may stem from the fact that the low-rank approximation based on selected InD landmark InD requires more precise kernel configurations to effectively learn discriminative subspaces than the data-independent random features approximation.

In \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\), the number of RFFs \(M_r\) and the number of support landmarks \(M_n\) respectively determine the approximation ability of random features to the kernel function and of the low-rank matrix to the full kernel matrix. Thereby, the larger the \(M_r\) and \(M_n\), the better random features and low-rank features approximate the Gaussian kernel \(k_{\rm gau}\) [33], [34].

Figure 10 indicates the FPR and AUROC values of \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\) under varied numbers of RFFs and support landmarks \(M_r,M_n\). As \(M_r\) and \(M_n\) increase, the detection performance of both \(\rm KPCA_{rff}\) and \(\rm KPCA_{nys}\) improves, since the random features and low-rank features gradually converge to the Gaussian kernel. Besides, Figure 10 also provides supplementary results to discussions on the computational complexity in Section 5.3. Under the same value of \(M_r\) and \(M_n\), the low-rank mapping of \(\rm KPCA_{nys}\) significantly outperforms the random mapping of \(\rm KPCA_{rff}\) in detection performance. We can further find in Figure 10 that the low-rank mapping built by sampling 1,024 support landmarks even exceeds the detection performance of the 4,096-dimensional random mapping, which strongly supports the superiority of the data-dependent low-rank approximation in OoD detection.

6 Related Work↩︎

Prevalent OoD detection methods devise the scoring function \(S(\cdot)\) of Eqn.@eq:eq:ood-scoring based on different outputs from DNNs to characterize the InD-OoD disparities, categorized as follows.

Logits-based approaches exploit the abnormal responses reflected in the predictive logits or probabilities from DNNs to detect OoD data. Early methods adopt either the maximum logits [59] or probability [58], [60] or the energy function on logits [7] as the detection score. Besides, decoupling on logits is explored to regularize the model training from the perspectives of InD confidence [71] and similarity [62], respectively. The Wasserstein distance [8] is applied to the predictive probabilities and leads to a novel loss function to optimize the network for enhanced detection performance.

Gradients-based methods investigate gradient disparities between InD and OoD data for OoD detection. Norms of full gradients are firstly studied in [9]. The projections of gradients onto a low-rank feature space are investigated in [66] for more discriminative gradient norms. Gradient information is also utilized to regularize the model training together with auxiliary sampled OoD data [72]. A recent work [10] leverages low-dimensional gradient representations to train an auxiliary linear network for effective detection.

Features-based approaches capture the feature information causing over-confident OoD predictions in different ways. A series of feature rectification methods clip the abnormal feature values [11], [14]–[20] to remove anomalous information in distinct ways. Besides, feature distances in different forms, such as the Mahalanobis distance [21], [22], the \(\ell_2\) distance [12], [23], the tangent distance [25], and the Hopfield energy [24], can be efficacious detection metrics. More explorations on feature norms [61], [73] and feature subspaces [13], [35], [74], [75], have exhibited excellent detection performance.

Aside from the aforementioned 3 types of detection methods, a broad variety of researches have been developed for investigating InD-OoD disparities from distinctive perspectives with novel insights, including but not limited to utilizing the parameters [50], [65], the ensemble technique [76], the diffusion models [77], and the contrastive learning [78]. In addition to those practical approaches, theoretical understandings for OoD detection are discussed in [79], [80]. OoD detection is also extended in more scenarios, such as applications on the tabular data [81] and balancing the InD generalization [82].

Random Fourier Features (RFFs) [33], as explicit mappings to approximate kernels, are initially developed to accelerate large-scale kernel machines, and have been extensively studied and applied across a broad range of fields, such as kernel approximation [83], kernel learning [84], generalization [85], optimization [86] and deep network architectures [87].

Nyström method [34] with various sampling schemes [42] has been applied not only to kernels, such as kernel learning [41], [88] and approximated KPCA [43]–[48], but also to diverse domains beyond kernels, e.g., interpreting the self-attention in transformers [89] and differentiation optimization [90]. There is significant potential in bridging these classic machine learning methods with modern deep learning frameworks, leveraging their theoretical foundations and computational efficiency to address contemporary challenges.

7 Conclusion and Discussion↩︎

Exploring the non-linear feature subspace remains a fresh, significant, and open perspective for OoD detection. In this work, we leverage the framework of KPCA to identify discriminative non-linear feature subspaces to detect OoD data in an efficacious and efficient way. Firstly, we analyze InD and OoD features, observe the non-linear patterns related to InD-OoD disparities, and derive an effective Cosine-Gaussian kernel that models such patterns. Then, two distinct explicit mappings \(\Phi(\cdot)\) to approximate the Cosine-Gaussian kernel are leveraged: data-independent random features and data-driven Nyström approximation, so as to achieve efficient computations of the KPCA reconstruction errors in the \(\Phi(\boldsymbol{z})\)-space. Particularly, an energy-based sampling scheme is proposed to refine the Nyström method for more discriminative subspaces between InD and OoD. Extensive experiments verify that our KPCA method achieves new SOTA OoD detection performance with high efficiency, and provide in-depth analyses on kernel choices, sampling schemes, intermediate-layer features, and hyper-parameters.

One limitation of KPCA detection is the hyper-parameter tuning of its task-specific Cosine-Gaussian kernel for non-linear mappings. Our preliminary explorations on learnable kernel representations in Section 4.5 and Appendix 10 mitigate this issue through different learning techniques, while also suggesting further improvements, such as incorporating outliers and tailored optimization objectives for distribution shifts. We hope that the proposed effective kernel verified empirically in our work could benefit the research community from the perspective of exploring the non-linearity in feature space in future studies on OoD detection.

References↩︎