Safety Performance of Neural Networks in the Presence of Covariate Shift
Covariate shift may impact the operational safety performance of neural
networks. A re-evaluation of the safety performance, however, requires
collecting new operational data and creating corresponding ground truth labels,
which often is not possible during operation. We are therefore proposing to
reshape the initial test set, as used for the safety performance evaluation
prior to deployment, based on an approximation of the operational data. This
approximation is obtained by observing and learning the distribution of
activation patterns of neurons in the network during operation. The reshaped
test set reflects the distribution of neuron activation values as observed
during operation, and may therefore be used for re-evaluating safety
performance in the presence of covariate shift. First, we derive conservative
bounds on the values of neurons by applying finite binning and static dataflow
analysis. Second, we formulate a mixed integer linear programming (MILP)
constraint for constructing the minimum set of data points to be removed in the
test set, such that the difference between the discretized test and operational
distributions is bounded. We discuss potential benefits and limitations of this
constraint-based approach based on our initial experience with an implemented
research prototype.
Chih-Hong Cheng, Harald Ruess, Konstantinos Theodorou
# Safety Performance of Neural Networks in the Presence of Covariate Shift

###### Abstract

Covariate shift may impact the operational safety performance of neural networks. A re-evaluation of the safety performance, however, requires collecting new operational data and creating corresponding ground truth labels, which often is not possible during operation. We are therefore proposing to reshape the initial test set, as used for the safety performance evaluation prior to deployment, based on an approximation of the operational data. This approximation is obtained by observing and learning the distribution of activation patterns of neurons in the network during operation. The reshaped test set reflects the distribution of neuron activation values as observed during operation, and may therefore be used for re-evaluating safety performance in the presence of covariate shift. First, we derive conservative bounds on the values of neurons by applying finite binning and static dataflow analysis. Second, we formulate a _mixed integer linear programming_ (MILP) constraint for constructing the minimum set of data points to be removed in the test set, such that the difference between the discretized test and operational distributions is bounded. We discuss potential benefits and limitations of this constraint-based approach based on our initial experience with an implemented research prototype.

Keywords:distribution reshaping machine learning MILP performance estimation

## 1 Introduction

_Covariate shift_ in machine-learned systems occurs when the input distribution changes between training and operation stages [14]. This phenomenon is present in most applications of machine learning, as training sets usually do not sufficiently reflect the complexity of real-world operational contexts and their potential changes. This kind of dataset shift is also a major concern in transfer learning when exposing machine-learned systems to solving different tasks [8].

There is a fundamental dichotomy between covariate shift of machine-learned systems during operation and their underlying safety requirements, which require demonstrating given _safety performance indicators_ (SPIs) [7, 1] prior to deployment. The challenge we are tackling therefore is to incorporate the possibility
of operational covariate shift into safety assurance arguments for safety-related neural networks. Hereby, we assume that the initial test data for SPI evaluation is known but the operational data is unknown, since collecting operational data and creating corresponding ground truth labels is usually not possible during operation.

In tackling this challenge, we develop a specialized online monitoring technique for estimating the change of values of SPIs due to covariate shift. For practical purposes, we restrict ourselves to feed-forward deep neural networks (DNN), and we assume that the values of monitored neurons (in the feature space) of this DNN adequately reflect the input data distribution. Now, for each monitored neuron, one constructs the histogram of distributions based on binning, and distribution shift is observed by comparing the shape of two such histograms. Such information abstracts the details of the observed input in operation, thereby bypassing practical limitations where arbitrarily initiating a data collection regime when the DNN is integrated into an application has technical and societal constraints. One of our measures of similarity, called \(\kappa\)-KL similarity, is inspired by the Kullback-Leibler divergence. The purpose of a second measure, called \(\epsilon\)-portion similarity, is to characterize bounded differences. Key to our approach is that SPI estimations are reduced to constructing a subset of the test data that matches the similarity measure demonstrated by the operation, followed by the recomputation of the SPI on this subset. For \(\epsilon\)-portion similarity, when the input is of bounded range we introduce a _mixed integer linear programming_ (MILP) encoding with 0-1 variables, whereby an upper limit on the number of bins can be obtained from static dataflow analyis.

In Section 2 we review and compare with most closely related work. Section 3 defines \(\epsilon\)-portion similarity for measuring the similarity of distributions based on neuron activations. Next, Section 4 describes distribution reshaping for \(\epsilon\)-portion similarity via test set reduction together its encoding in MILP. This algorithm is evaluated in Section 5 based on standard machine learning benchmarks, and we conclude in Section 6 with discussing the potential benefits and current limitations of our approach.

## 2 Related Work

The divergence between a source and a target distribution, as obtained, say, by dataset shift is usually measured in terms of _mutual information_ or KL divergence [14]. Unfortunately, measuring mutual information from finite data is a notoriously difficult estimation problem [9, 4], and there are statistical limitations on measuring lower bounds on KL divergence from finite data [12]. Since our techniques are intended to be applied during operation, we are therefore measuring covariate shift only indirectly by observing and comparing abstracted distributions on corresponding neuronal excitements. This kind of indirect measurement does not require the original detailed operational data (e.g., images) to be available.
Covariate shift in machine-learned systems may be corrected using, say, _weighted empirical risk minimization_[16], which is based on retraining the system with a calibrated loss function based on the ratio of source and the target distribution of inputs. Retraining of safety-related machine-learned components, however, is problematic, and the best we can do is to adequately measure the potential drop of relevant safety performance indicators which are due to covariate shift. This implies that when data in operation is only made available as abstracted distributions, we need to reshape the test data to create an estimation. \(\epsilon\)-portion similarity, as developed here, is to practically consider the non-linearity caused by KL-divergence as the similarity measure, thereby enabling a reduction to MILP.

Within the research field of safe autonomous driving, _leading measures_[3] are proactive indicators that assess prevention efforts and can be observed and evaluated before a crash occurs. Our approach to SPI re-estimation under distribution reshaping yields a leading measure on the level of a machine-learned component. Our developments also go beyond _out-of-distribution_ techniques for detecting outliers with respect to training inputs [11, 15], as we are constructing an aggregated SPI against all observed data, where even when every data point being observed in operation is _within-distribution_, this does not imply that the SPI will be the same.

## 3 Distribution Similarity based on Neuron Values

\(\mathcal{D}_{op}\) denotes the multiset of data points, which are collected during operation, and \(\mathcal{D}_{test}\) is the multiset of data points used in the (safety) performance evaluation. We assume as given a feed-forward _deep neural network_ (DNN) \(F\stackrel{{\text{def}}}{{:=}}f^{L}\circ\ldots\circ f^{1}\), which is composed of layers \(1\) through \(L\). Each _layer_\(l_{i}\) is a function \(\mathbb{R}^{d_{i-1}}\rightarrow\mathbb{R}^{d_{i}}\), with \(d_{i}\) the dimensions of vectors. Layers consists of a set of neurons for computing a weighted linear sum from the input of the previous layer, followed by applying some monotonically non-decreasing activation function, such as _ReLU_, _Leaky ReLU_, and _tanh_. Without loss of generality, the neurons in \(F\) are fully connected with subsequent layers. The notation \(l_{A}\in\{1,\ldots,L\}\) indicates the chosen layer for analyzing distribution similarity between \(\mathcal{D}_{op}\) and \(\mathcal{D}_{test}\). For a data point in, the output at the \(l\)-th layer is the vector \(F^{l}(\mathsf{in}):=f^{l}(f^{l-1}(\ldots f^{1}(\mathsf{in})))\) of dimension \(d_{l}\). Now, \(F^{l}_{i}(\mathsf{in})\) projects the \(i\)-th output from \(F^{l}(\mathsf{in})\), and \(f^{l}_{i}\) is the output of the \(i\)-th neuron at the \(l\)-th layer; that is, given an input in, \(f^{l}_{i}\) takes \(F^{l-1}(\mathsf{in})\) as input and produces \(f^{l}_{i}(F^{l-1}(\mathsf{in}))\) which equals \(F^{l}_{i}(\mathsf{in})\). Finally, all inputs are bounded by an interval \([v_{min},v_{max}]\), where \(v_{min}\), \(v_{max}\) are fixed constants. In other words, \(\mathsf{in}\in[v_{min},v_{max}]^{d_{0}}\) and \(\mathcal{D}_{op},\mathcal{D}_{test}\subseteq[v_{min},v_{max}]^{d_{0}}\). For a multiset \(\mathcal{D}\) of data points and given DNN \(F\), we define

\[V^{l}_{i}(\mathcal{D})\stackrel{{\text{def}}}{{:=}}\langle F^{l}_ {i}(\mathsf{in})\mid\mathsf{in}\in\mathcal{D}\rangle \tag{1}\]

to be the multiset of all values of the \(i\)-th neuron value at layer \(l\) for all inputs in \(\mathcal{D}\).
Definition 1: For a natural number \(N>0\), a positive real number \(\Delta\) and a real number \(c\in\mathbb{R}\), the \((c,\Delta,N)\)**-binning function**\(b_{N}^{c,\Delta}:[c,c+(N+1)\Delta]\to\{0,1,\ldots,N\}\) is defined as follows:

\[b_{N}^{c,\Delta}(x)=\begin{cases}0&\text{if $x\in[c,c+\Delta]$}\\ j&\text{else if $x\in(c+j\Delta,c+(j+1)\Delta]$, for any $j\in\{1,\ldots,N\}$}\end{cases} \tag{2}\]

We apply each element in \(V_{i}^{l_{A}}(\mathcal{D}_{op})\) with a binning function in order to derive another multiset

\[B_{i}^{l_{A}}(F,\mathcal{D}_{op})\stackrel{{\mathrm{def}}}{{:=}} \langle b_{N}^{c,\Delta}(F_{i}^{l_{A}}(\mathsf{in}))\mid\mathsf{in}\in \mathcal{D}_{op}\rangle. \tag{3}\]

This requires, however, that for all \(\mathsf{in}\in\mathcal{D}_{op}\), \(F_{i}^{l_{A}}(\mathsf{in})\in[c,c+(N+1)\Delta]\). Provided that any input is bounded where \(\mathsf{in}\in[v_{min},v_{max}]^{d_{0}}\), we have the following property.

Lemma 1: _Let \(\Delta\) be a positive constant. Provided that \(\mathcal{D}_{op},\mathcal{D}_{test}\subseteq[v_{min},v_{max}]^{d_{0}}\) and \(F\) is implemented layer-wise with each neuron \(f_{i}^{l}\) implemented by (1) performing a weighted linear sum from the previous layer, followed by (2) applying monotonically non-decreasing computational activation function, there exists a constant \(c\in\mathbb{R}\) and \(N\in\mathbb{N}\) such that for all \(i\in\{1,\ldots,d_{l}\}\), \(F_{i}^{l_{A}}(\mathsf{in})\in[c,c+N\Delta]\), where \(c\) and \(N\) can be computed in time linear to the number of neurons._

Proof: (Sketch) This is based on the known result in neural network verification using abstract interpretation [5, 2, 6], where provided that input is bounded, and \(F\) is implemented with (1) and (2), one can apply computationally efficient interval-bound propagation (boxed abstraction) [2, 6] to derive a conservative minimum and maximum bound \([v_{i,min},v_{i,max}]\) such that \(\{F_{i}^{l_{A}}(\mathsf{in})\mid\mathsf{in}\in[v_{min},v_{max}]^{d_{0}}\} \subseteq[v_{i,min},v_{i,max}]\), where the interval-bound analysis is done in time linear to the total amount of neurons (see Example 1 for illustration).[3] With the following value assignment for \(c\) and \(N\), the lemma then holds.

\[c:=\min(v_{1,min},\ldots,v_{d_{l},min}) \tag{4}\]

\[N:=\lceil\frac{\max(v_{1,max},\ldots,v_{d_{l},max})-c}{\Delta}\rceil \tag{5}\]

Example 1: Consider the example in Figure 1, where we wish to perform the analysis at layer \(l_{A}=2\). Assume \(\Delta=3\), and for each input at the left, it has the domain \([-1,1]\), i.e., \(\mathcal{D}_{op},\mathcal{D}_{test}\subseteq[-1,1]^{3}\). For each neuron (\(f_{1}^{1}\), \(f_{2}^{1}\), \(f_{1}^{2}\), \(f_{2}^{2}\)), its computation is completed by first performing a weighted sum (the corresponding weight is attached in the edge) followed by the nonlinear activation ReLU (\(ReLU(x)\stackrel{{\mathrm{def}}}{{:=}}\max(0,x)\)). The result of interval-bound propagation provides us a conservative estimate \(v_{1,min}=v_{2,min}=0\), \(v_{1,max}=14\), \(v_{2,max}=5\). Therefore, \(c=\min(0,0)=0\) and \(N=\lceil\frac{\max(14,5)-0}{3}\rceil=5\).
By applying each element in \(V_{i}^{l_{A}}(\mathcal{D}_{op})\) with the binning function created using Lemma 1, one derives another multiset \(B_{i}^{l_{A}}(F,\mathcal{D}_{op})\stackrel{{\mathrm{def}}}{{\coloneqq }}\langle b_{N}^{c,\Delta}(F_{i}^{l_{A}}(\mathsf{in}))\mid\mathsf{in}\in \mathcal{D}_{op}\rangle\). Analogously, define \(B_{i}^{l_{A}}(F,\mathcal{D}_{test})\) to abbreviate \(\langle b_{N}^{c,\Delta}(F_{i}^{l_{A}}(\mathsf{in}))\mid\mathsf{in}\in \mathcal{D}_{test}\rangle\). Let \(\mathsf{ct}(j,\mathcal{D})\) be the function that counts the number of elements in multiset \(\mathcal{D}\) having value \(j\), and \(|\mathcal{D}|\) returns the size of the multiset. We now define two types of distribution similarity.

Definition 2: Given a positive constant \(\kappa\), define \(\mathcal{D}_{op}\) and \(\mathcal{D}_{test}\) to be \(\kappa\)-KL similar (subject to DNN \(F\), layer index \(l_{A}\), and binning function \(b_{N}^{c,\Delta}\)), if:

\[\forall i \in \{1,\ldots,d_{l}\} \tag{6}\]

Definition 3: Given a positive constant \(\epsilon\), define \(\mathcal{D}_{op}\) and \(\mathcal{D}_{test}\) to be \(\epsilon\)-portion similar (subject to DNN \(F\), layer index \(l_{A}\), and binning function \(b_{N}^{c,\Delta}\)) if:

\[\forall i\in\{1,\ldots,d_{l}\},\forall j\in\{0,\ldots,N\}:\\ -\epsilon\leq\frac{\mathsf{ct}(j,B_{i}^{l_{A}}(F,\mathcal{D}_{op} ))}{|\mathcal{D}_{op}|}-\frac{\mathsf{ct}(j,B_{i}^{l_{A}}(F,\mathcal{D}_{test} ))}{|\mathcal{D}_{test}|}\leq\epsilon \tag{7}\]

Table 1 summarizes the characteristics of our proposed distribution similarity measures. The definition of \(\kappa\)-KL similarity is based on the well-known definition of KL-divergence in a discrete setting. As the computation \(\frac{\mathsf{ct}(j,B_{i}^{l_{A}}(F,\mathcal{D}_{test}))}{|\mathcal{D}_{test}|}\) and \(\frac{\mathsf{ct}(j,B_{i}^{l_{A}}(F,\mathcal{D}_{op}))}{|\mathcal{D}_{op}|}\) are only the relative frequencies in appearing to a particular bin,

\begin{table}
\begin{tabular}{|c|c|c|c|} \hline Distribution similarity & Sensitive to \(|\mathcal{D}_{op}|\) & Non-emptiness in bin & Dist. reshaping via MILP \\ \hline \(\kappa\)-KL similar & no & needed & no \\ \hline \(\epsilon\)-portion similar & no & not needed & yes \\ \hline \end{tabular}
\end{table}
Table 1: Comparing two distribution similarity measures

Figure 1: An example of using bound propagation to conservatively estimate \(c\) and \(N\).
it is not sensitive to the size of \(\mathcal{D}_{op}\). Nevertheless, due to the nonlinear logarithm function in the definition, the distribution shaping problem with minimum data point removal naturally cannot be formulated using MILP, which is in contrast to distribution reshaping using \(\epsilon\)-portion similarity. It is also crucial to notice that the standard KL divergence is defined when they have only non-zero entries; in our setup, this implies that all bins should be non-empty to ensure \(\kappa\)-KL similarity is well-defined. Here we omit details, but one may employ some heuristics: (1) Omit counting bin \(j\) where both \(\mathcal{D}_{test}\) and \(\mathcal{D}_{op}\) have no contribution to bin \(j\). (2) When \(\mathcal{D}_{test}\) contributes to bin \(j\) but not \(\mathcal{D}_{op}\), return "undefined" or "\(\infty\)" for the \(\kappa\)-KL similarity.

Finally, when \(\kappa\)-KL similarity is well-defined, provided that \(\epsilon\)-portion-similarity holds, one can also derive a conservative \(\kappa\) value where the \(\kappa\)-KL-divergence-similarity measure is guaranteed to hold. It can be accomplished by considering a worst case where "every" bin in operation has the largest difference characterized by \(\epsilon\)-portion-similarity (which is overly conservative, as the sum of all bin-ratios for operation will not be 1), followed by feeding that information to the definition of \(\kappa\)-KL-divergence similarity, in order to derive a conservative bounding \(\kappa\) value.

Note that for simplicity, we have prepared our formulation such that the distribution similarity is defined based on considering all neurons in layer \(l_{A}\) and having a unified binning function for all neurons. The constraint can be easily relaxed to allow distribution similarity to be considered only on a subset of neurons as well as neurons on different layers.

Figure 2: Shaping the test set by removing or adding data points requires simultaneously considering the effect of multiple neurons. For example, although removing \(\mathsf{in}_{1}\) can reduce the count in bin \(j=2\) for \(i=1\), it may also undesirably reduce the count in bin \(j=4\) for \(i=2\). The counts in the Y-axis are not on the same scale but only show the tendency.
## 4 MILP Encoding for Distribution Reshaping

Provided that \(\mathcal{D}_{op}\) and \(\mathcal{D}_{test}\) are not similar in distribution, we are interested in finding a subset of \(\mathcal{D}_{test}\), such that the subset has the similar distribution with \(\mathcal{D}_{op}\). However, this is not an easy task, as demonstrated in the example in Figure 2: When one only looks at the distribution in \(i=1\) and removes data point \(\mathsf{in}_{1}\) in \(\mathcal{D}_{test}\) to create distribution similarity, it can create a negative impact on \(i=2\), where the reduction may not be desired.

When one finds such a subset, due to the distribution similarity one can estimate the performance. However, keeping the subset as large as possible is also desired. This leads to Definition 4, where we artificially introduce \(\mathcal{D}_{can}\) to restrict the set of data points further as candidates to be removed. When \(\mathcal{D}_{can}\) equals \(\mathcal{D}_{test}\), any data point within \(\mathcal{D}_{test}\) can be removed. As demonstrated in later paragraphs, in our MILP encoding scheme, the number of 0-1 integer variables introduced in the MILP equals the size of \(\mathcal{D}_{can}\).

Definition 4 (Distribution Reshaping for \(\epsilon\)-portion similarity via Test Set Reduction): Provided that \(\mathcal{D}_{op}\) and \(\mathcal{D}_{test}\) are not \(\epsilon\)-portion similar, given \(\mathcal{D}_{can}\subseteq\mathcal{D}_{test}\), find \(\mathcal{D}_{can}^{opt}\subseteq\mathcal{D}_{can}\) such that

1. \(\forall i\in\{1,\ldots,d_{l}\}\), \(\mathcal{D}_{op}\) and \(\mathcal{D}_{test}\setminus\mathcal{D}_{can}^{opt}\) are \(\epsilon\)-portion similar.
2. The size of \(\mathcal{D}_{can}^{opt}\) is minimum, among any other multiset \(\mathcal{D}_{can}^{{}^{\prime}}\) that also ensures the first condition.

If we take a data point \(\mathsf{in}\in\mathcal{D}_{can}\), pass it to the DNN and extracts \(F^{l}(\mathsf{in})\), apply the binning function on each computed neuron value \(F_{i}^{l}(\mathsf{in})\), this leads to a vector \(v_{\mathsf{in}}\stackrel{{\text{def}}}{{:=}}(b_{N}^{c,\Delta}(F_ {1}^{l}(\mathsf{in})),\ldots,\)

\(b_{N}^{c,\Delta}(F_{d_{l}}^{l}(\mathsf{in})))\in\{0,\ldots,N\}^{d_{l}}\), where the value in each dimension \(i\in\{1,\ldots,d_{l}\}\) contains the associated binning information for the \(i\)-th output.

For every \(\mathsf{in}\in\mathcal{D}_{can}\), in our MILP encoding, create a 0-1 integer variable \(br_{\mathsf{in}}\) that controls the decision of removing data point in from \(\mathcal{D}_{can}\).

* If \(br_{\mathsf{in}}=1\), then remove the data point in from \(\mathcal{D}_{test}\).
* If \(br_{\mathsf{in}}=0\), then keep the data point in.

For neuron \(i\), recall that the number of elements originally in bin \(j\) equals \(\mathsf{ct}(j,B_{i}^{l_{A}}(F,\mathcal{D}_{test}))\). For data point in \(\in\mathcal{D}_{can}\), if \(F_{i}^{l_{A}}(\mathsf{in})\) falls into bin \(j\), then if we remove the data point, the size of remaining elements in bin \(j\) can be characterized as \(\mathsf{ct}(j,B_{i}^{l_{A}}(F,\mathcal{D}_{test}))-br_{\mathsf{in}}\). Therefore, depending on the decision whether elements in \(\mathcal{D}_{can}\) are removed or not, the number of elements for neuron \(i\), bin \(j\) can be encoded as \(\mathsf{ct}(j,B_{i}^{l_{A}}(F,\mathcal{D}_{test}))-\sum_{\mathsf{in}\in \mathcal{D}_{can}\text{ s.t. }b_{N}^{c,\Delta}(F_{i}^{l}(\mathsf{in}))=j}br_{\mathsf{in}}\).

Lemma 2 (MILP encoding): _The problem in Definition 4 can be reduced to the following MILP problem._
minimize_

\[\sum_{\text{in}\in\mathcal{D}_{can}}\text{br}_{\text{in}}\ \ \text{s.t.}\] \[\forall i\in\{1,\ldots,d_{l}\},\forall j\in\{0,\ldots,N\}:\] \[-\epsilon\leq\frac{\text{ct}(j,B_{i}^{l_{A}}(F,\mathcal{D}_{op})) }{|\mathcal{D}_{op}|}-\frac{\text{ct}(j,B_{i}^{l_{A}}(F,\mathcal{D}_{test}))- \sum_{\text{in}\in\mathcal{D}_{can}\ \text{s.t.}\ b_{N}^{c,\Delta}(F_{i}^{l}(\text{in}))=j}\text{br}_{\text{in}}}{| \mathcal{D}_{test}|-\sum_{\text{in}\in\mathcal{D}_{can}}\text{br}_{\text{in}}} \leq\epsilon \tag{8}\]

Proof: The encoding is straightforward, where the only difference with Equation 3 is (1) the update of the denominator from \(|\mathcal{D}_{test}|\) to \(|\mathcal{D}_{test}|-\sum_{\text{in}\in\mathcal{D}_{can}}\text{br}_{\text{in}}\), reflecting the potential decrease in the data points, and (2) the update of the nominator by subtracting \(\sum_{\text{in}\in\mathcal{D}_{can}\ \text{s.t.}\ b_{N}^{c,\Delta}(f_{i}^{l}( \text{in}))=j}\text{br}_{\text{in}}\), counting the potential decrease of the number of items in bin \(j\). The remaining task is to ensure that the encoding does not lead to non-linear constraints. This holds, as \(\frac{\text{ct}(j,B_{i}^{l_{A}}(F,\mathcal{D}_{op}))}{|\mathcal{D}_{op}|}\) is a constant, one can rewrite the inequality by multiplying \(|\mathcal{D}_{test}|-\sum_{\text{in}\in\mathcal{D}_{can}}\text{br}_{\text{in}}\). 

Example 2: Consider \(\mathcal{D}_{can}\stackrel{{\text{def}}}{{\coloneqq}}\langle \text{in}_{1},\text{in}_{2},\text{in}_{3}\rangle\), where for each element in \(\mathcal{D}_{can}\), its binning information is listed in Table 2. Then consider \(i=3\) and \(j=4\) in Equation 8, the inequality part can be rewritten into Equation 9, where \(\frac{\text{ct}(4,B_{3}^{l_{A}}(F,\mathcal{D}_{op}))}{|\mathcal{D}_{op}|}\), \(|\mathcal{D}_{test}|\), and \(\text{ct}(4,B_{3}^{l_{A}}(F,\mathcal{D}_{test}))\) are constants that can be computed before the MILP encoding. As \(\epsilon\) is also a constant, Equation 9 can be rewritten into two linear constraints.

\[-\epsilon\leq\frac{\text{ct}(4,B_{3}^{l_{A}}(F,\mathcal{D}_{op}))}{|\mathcal{D }_{op}|}-\frac{\text{ct}(4,B_{3}^{l_{A}}(F,\mathcal{D}_{test}))-\text{br}_{ \text{in}_{1}}-\text{br}_{\text{in}_{3}}}{|\mathcal{D}_{test}|-\text{br}_{ \text{in}_{1}}-\text{br}_{\text{in}_{2}}-\text{br}_{\text{in}_{3}}}\leq\epsilon \tag{9}\]

Remark 1: Whenever distribution reshaping does not involve multiple neurons, finding a subset of \(\mathcal{D}_{test}\) to ensure \(\epsilon\)-portion similarity can be done efficiently (with a greedy algorithm), and therefore no MILP encoding required. Reconsider the example in Figure 2 where the goal is only to perform reshaping on \(i=1\). One can simply remove \(\text{in}_{1}\), as there is no side effect that should be considered.

## 5 Evaluation

We have implemented the concept and performed an initial feasibility study based on the MNIST dataset [10]. We use Pytorch [13] to train the DNN and use Google OR-Tools4 to solve the generated MILP problem. For distribution reshaping, we take 20 neurons in close-to-output layers. To simulate the "covariate shift", we have intentionally created the testing dataset with significantly more examples in classes "7", "8" and "9" (with each around 20%), and left classes "1" to "5" have a small portion. The created operational dataset consists of 5300 image samples5, where the portion of "7", "8" and "9" is significantly
reduced, meaning that the assumption on the frequency for class distribution is incorrect. Recall that in our problem definition, one does not have access to the operational data and the associated ground truth labels. The experimental setting here allows us to estimate whether distribution reshaping on neurons (representing the feature space) positively correlates with the data distribution reflected by the associated label. For measuring similarity, we use the bin width \(\Delta=1\) and set \(\epsilon\) to be 0.01. The set \(\mathcal{D}_{can}\), i.e., elements that can be removed for distribution reshaping purposes, ranges from 7000 to 20000. This implies that in the corresponding MILP problem, we have a maximum of 20000 binary integer variables. The whole program and the MILP solver are operated on an Intel i5-9300H laptop equipped with 32GB RAM. Altogether the time required to find the smallest set to be removed for distribution reshaping is commonly below 15 minutes. Figure 3 shows the distribution for two neurons being considered.

Figure 4 presents our preliminary result, where in Figure 3(a), one can observe that although we only perform distribution reshaping on neurons reflecting the feature level, the reshaped test data is moving closer to the operational data when we consider the distribution reflected as the relative frequencies of each class, suggesting that the SPI estimation on the reshaped test dataset can be more precise. Figure 3(b) shows an aggregated result on all experiments being conducted, where the \(x\) coordinate characterizes the sum of the per-class ratio-difference between operational and reshaped test data, and the \(y\) coordinate characterizes the sum of the per-class ratio-difference between operational and the original test data. It also turned out that most of the points are within the top-left region, hinting that the reshaped test data demonstrates a positive correlation with the label distribution of the operational data.

## 6 Concluding Remarks

We investigated the problem of estimating the safety performance in the presence of covariate shift based on test data and (feature-level) neuron value distributions - but not on operational data, which often is unavailable in real-world situations. Our main contribution is a MILP encoding for reshaping the test data to be similar to the (unknown) distribution of the operational data. This reshaped test data now serves as a proxy for evaluating the safety performance in the presence of covariate shift. With this approach, we may compute the distribution profile (as histograms) locally on the device of the DNN under investigation, thereby addressing possible privacy concerns. Initial experiments demonstrate the feasibility of this constraint-solving approach, but, clearly, more experience for more

\begin{table}
\begin{tabular}{|c|c|c|c|} \hline  & \(b_{N}^{c,\Delta}(F_{1}^{I_{A}}(\cdot))\) & \(b_{N}^{c,\Delta}(F_{2}^{I_{A}}(\cdot))\) & \(b_{N}^{c,\Delta}(F_{3}^{I_{A}}(\cdot))\) \\ \hline \(\text{in}_{1}\) & 1 & 4 & 4 \\ \hline \(\text{in}_{2}\) & 2 & 1 & 2 \\ \hline \(\text{in}_{3}\) & 0 & 3 & 4 \\ \hline \end{tabular}
\end{table}
Table 2: An example for the MILP encoding
complex scenarios in real-world situations is needed. However, the maximum number of removable samples is restricted, as this number correlates with the number of 0-1 variables in the generated MILP problem. Constraint solving, in particular, needs to be accelerated considerably. Since the generated MILP encodings are highly-stylized, specialized variable branching heuristics or suitable polynomial-time approximation schemes may be developed. Finally, the problem of reshaping test data can be generalized to also adapt individual test data points to covariate shift based on their respective resilience bounds [2].

#### 4.0.1 Acknowledgements

This work is supported by the StMWi Bayern as part of the project for the thematic development of the Fraunhofer IKS.

Figure 4: Effect of distribution reshaping, observed on the output label distribution

Figure 3: Qualitative result of distribution reshaping simultaneously on multiple neurons