We describe a complete method that learns a neural network which is guaranteed to over-estimate a reference function on a given domain. The neural network can then be used as a surrogate for the reference function. The method involves two steps. In the first step, we construct an adaptive set of Majoring Points. In the second step, we optimize a well-chosen neural network to over-estimate the Majoring Points. In order to extend the guarantee on the Majoring Points to the whole domain, we necessarily have to make an assumption on the reference function. In this study, we assume that the reference function is monotonic. We provide experiments on synthetic and real problems. The experiments show that the density of the Majoring Points concentrate where the reference function varies. The learned over-estimations are both guaranteed to overestimate the reference function and are proven empirically to provide good approximations of it. Experiments on real data show that the method makes it possible to use the surrogate function in embedded systems for which an underestimation is critical; when computing the reference function requires too many resources.
(1)
Inspired by critical systems applications, we require (1) to be guaranteed by a formal theorem. We call fw ;b the surrogate and call f the model.
In the typical application we have in mind, f is the result of a deterministic but complex phenomenon. It is difficult to compute and its evaluation requires intensive computations or extensive memory consumption. We consider two settings. In the first setting, we can evaluate f (x) for any x 2 D. In the second setting, we only know a data set (xi; f (xi))i=1::n of size n 2 N.
The constructed surrogate fw ;b permits to rapidly evaluate an approximation of f at any point of D. Of course, we want the surrogate fw ;b to approximate f well; but most importantly we want fw ;b to overestimate f . In the typical scenario we have in mind, f models the consumption of some resource for a critical action. Underestimating the model may cause a (potentially deadly) hazard that will not be acceptable for certification authorities especially in aeronautics (EASA or FAA). The applications include for instance: - the estimation of the braking distance of an autonomous vehicle; - the number of kilometers that can be traveled; - the maximum load a structure can carry, - the network traveling time etc Guaranteed overestimation can also be used to guarantee the fairness of a score, when underestimation on a sub-population leads to an unfair surrogate function. Providing such fairness or performance guarantee can be seen as a niche activity, but it alleviates the limitation that restrains the massive industrialization of neural networks in critical applications where passengers lives are at stake.
Finally, the adaptation of the method to construct an under-estimation of f is straightforward and, for ease of presentation, not exposed in the paper. Of course, the combination of both an over-estimation and an under-estimation permits, for any x, the construction of an interval in which f (x) is guaranteed to be.
The most standard type of guarantees in machine learning
aim at upper-bounding the risk by upper-bounding the
generalization error (see
Other works provide guarantees on the neural network
performance
Finally, another direction makes probabilistic
assumptions and provides confidence scores
Compared to these approaches, the guarantee on the surrogate fw ;b is due to the attention given to the construction of the learning problem and the hypotheses on the function f . To the best of our knowledge, and not considering trivial overestimation with poor performances, we are not aware of any other construction of a surrogate fw ;b that is guaranteed to overestimate the model f .
In order to extend the overestimation property to the whole domain we can obviously not consider any arbitrary function f . In this paper, we restrict our analysis to real-valued and finite non-decreasing functions. The extension to vector valued function is straightforward. The extension to non-increasing functions is straightforward too. We deliberately use these restrictive hypotheses to simplify the presentation. Furthermore, many extensions of the principles of the method described in the paper to other classes of nonmonotone functions are possible.
Formally, for a compact domain D Rd, a function g : D ! R is non-decreasing if and only if
Other authors have already studied the approximation of
non-decreasing functions with neural networks
Another restriction is that the method cannot be applied when the dimension d is large and f varies in all directions. In fact, one contribution of the paper is to design algorithms to alleviate this problem and apply the method for larger d, but d must anyway remain moderate for most function f .
These hypotheses permit to have global guarantee that hold on the whole domain D while weaker hypotheses on f only lead to local guarantees, holding in the close vicinity of the learning examples.
In the next section, we define Majoring Points and describe a grid based and an adaptive algorithm to construct them. The algorithms are adapted when the function f can be evaluated at any new input as well as when we only know a dataset (xi; f (xi))i=1::n. In Section 3, we describe a strategy to construct monotonic, over-estimating neural networks. Finally, in Section 4, we provide experiments showing that the Majoring Points are located in the regions where f varies strongly or is discontinuous. We also illustrate on synthetic examples that the method can accurately approximate f , while being guaranteed to overestimate it. An example on real data illustrates that the use of over-estimating neural networks permits to reduce the memory required to compute an over-estimation and thus permits to embed it, in a real world application.
2
Let (ai; bi)i=1::m 2 Rd R m. Let D Rd be compact and let f : Rd ! R be finite and non-decreasing. We say that (ai; bi)i=1::m are Majoring Points for f if and only if for any non-decreasing g : Rd ! R :
If g(ai) bi; 8i = 1::m; then g(x) f (x); 8x 2 D:
When f is upper-bounded on D, the existence of such majoring points is established by considering: m = 1, • a1 such that a1 • b1 = supx2D f (x).
x for all x 2 D, However, for most function f , any non-decreasing g such that g(a1) b1 is a poor approximation of f . The goal, when constructing Majoring Points of f is to have bi f (ai), while bi f (ai), for all i = 1::m. The number of points m should remain sufficiently small to make the optimization of the neural network manageable.
For any y and y0 2 Rd, with y rectangle between y and y0 by y0, we define the hyperRy;y0 = fx 2 Rdjy x < y0g: Using hyper-rectangles, we define the considered covers.
Let (yi)i=1::m and (yi0)i=1::m in Rd be such that yi0 yi, for all i = 1::m. We say that (yi; yi0)i=1::m covers D if and only if For any cover C = (yi; yi0)i=1::m, we define the function fC(x) =
min i : x2Ryi;yi0 f (yi0) , for all x 2 D: Notice that, since C is a cover, fijx 2 Ryi;yi0 g 6= ; and fC(x) is well-defined. We can establish that the function fC overestimates f over D:
For all x 2 D; fC(x) f (x): Indeed, for any x 2 D, there exists i such that x 2 Ryi;yi0 and fC(x) = f (yi0). Therefore, since f is non-decreasing and x yi0, we have f (x)
f (yi0) = fC(x):
Let D Rd be compact. Let C = (yi; yi0)i=1::m be a cover of D and let f : Rd ! R be finite and non-decreasing. The family (yi; f (yi0))i=1::m are Majoring Points for f .
Proof. We consider a non-decreasing function g such that, for all i = 1::m; g(yi) f (yi0):
solution of an optimization taking into account these two properties. However, the optimization would be intractable and we only describe an heuristic algorithm that construct a cover.
We construct Majoring Points according to two scenarios: • We can generate f (x) for all x 2 Rd. We call the Majoring Points generated according to this setting Function Adapted Majoring Points. • We have a dataset (xi; f (xi))i=1::n. It is not possible to have access to more training points. We call the Majoring Points generated according to this setting Data Adapted Majoring Points. In order to define them, we consider the function f~ : Rd ! R defined, for all x 2 Rymin;ymax , by f~(x) = min f (xi):
i:xi x Since f is non-decreasing, we have f~(x) f (x)
for all x 2 Rymin;ymax : At the core of the constructions described below is the construction of a cover C = (yi; yi0)i=1::m.
Grid Based Majoring Points We consider an accuracy parameter " > 0 and a norm k:k on Rd. We define nmax = d kymax ymink :
e "
A simple way to define Majoring Points is to generate a cover made of equally spaced points between ymin and ymax. Setting (3) (4) (5) (6) (8) (9) for all x 2 D; g(x) f (x): To do so, we consider x 2 D and i such that x 2 Ryi;yi0 . Using respectively that g is non-decreasing, (5), the definition of fC (3) and (4), we obtain the following sequence of inequalities:
The function fC can be computed rapidly using a lookup table but requires storing (yi; f (yi0))i=1::m. This can be prohibitive in some applications.
To deal with this scenario, we describe in Section 3 a method to construct a neural network such that fw ;b is non-decreasing and satisfies fw ;b (yi) f (yi0), for all i = 1::m. According to the proposition, such a network provides a guaranteed over-estimation of f , whose computation is rapid. The resources required to store w and b are independent of m. We show in the experiments that it can be several orders of magnitude smaller. This makes it possible to embed the overestimating neural network when embedding the Majoring Points is not be possible. This advantage comes at the price of loss of accuracy as fw ;b (x) fC(x) (fw ;b (x) has the role of g in (6)).
Introduction In this section, we describe algorithmic strategies to adapt Majoring Points to the function f . Throughout the section, we assume that we know ymin and ymax 2 Rd such that
Rymin;ymax :
D The goal is to build a cover such that fC is close to f and m is not too large. Ideally, the cover can be expressed as the (7) ai = yi bi = f (yi0) We can also construct a Grid Based Majoring Points when the function f cannot be evaluated but a dataset (xi; f (xi))i=1::n is available by replacing in the above definition f by f~, see (8).
The Grid Based Majoring Points are mostly given for pedagogical reasons. The number of values f (x) that need to be evaluated and the number of Majoring Points defining the objective of the optimization of the neural network are both equal to ndmax = O(" d). It scales poorly with d and this restrains the application of the Grid Based Majoring Points to small d, whatever the function f .
When f does not vary much in some areas, the Majoring Points in this area are useless. This is what motivates the adaptive algorithms developed in the next sections. and for all i0; Pd 1 k=0 ikN k and r = ymax
ymin nmax 2 R
d ; id 1 2 f1; : : : ; N
1g, we set i = yi = ymin + (i0r1; : : : ; id 1rd) yi0 = yi + r Notice that, the parameter r defining the grid satisfies krk ". Given the cover, the Function Adapted Majoring Points (ai; bi)i=0::Nd 1 are defined, for i = 0::ndmax 1, by
chotomy Algorithm that permits to generate an adaptive cover with regard to the variations of the function f (or f~). It begins with a cover made of the single hyper-rectangle Rymin;ymax . Then it decomposes every hyper-rectangle of the current cover that have not reached the desired accuracy. The decomposition is repeated until all the hyper-rectangle of the current cover have the desired accuracy (see Algorithm 1).
Initially, we have D Rymin;ymax . For any hyperrectangle Ry;y0 , denoting r = y02 y , the decomposition replaces Ry;y0 by its sub-parts as defined by
Ry+(s1r1;:::;sdrd);y+(s1+1)r1;:::;(sd+1)rd)j
(s1; : : : ; sd) 2 f0; 1gd : (10) (Hence the term ‘dichotomy algorithm’. ) The union of the sub-parts equal the initial hyper-rectangle. Therefore, the cover remains a cover after the decomposition. The final C is a cover of D.
We consider a norm k:k on Rd and real parameters " > 0, "f > 0 and np 2 N. We stop decomposing an hyperrectangle if a notion of accuracy is satisfied. The notion of accuracy depends on whether we can compute f or not. • When we can evaluate f (x): The accuracy of Ry;y0 is defined by the test f (y0) f (y) "f ky0
yk or or • when ky0
strongly. • When we only know a dataset (xi; f (xi))i=1::n: The accuracy of Ry;y0 is defined by the test f~(y0) or f~(y)
"f jfijxi 2 Ry;y0 gj where j:j is the cardinal of the set. np ky0 yk We stop decomposing if a given accuracy is reached : • when f (y0) f (y) "f or f~(y0) f~(y) "f : This happens where the function f varies only slightly. yk: This happens where the function f varies " " (11) (12) • when jfijxi 2 Ry;y0 gj np: This happens when the number of samples in Ry;y0 does not permit to improve the approximation of f by f~ in its sub-parts.
The cover is constructed according to Algorithm 1. This algorithm is guaranteed to stop after at most n0max = dlog2 kymax " ymink e iteration of the ‘while loop’. In the worst case, every hyper-rectangle of the current cover is decomposed into 2d hyper-rectangles. Therefore, the worstcase complexity of the algorithm creates
2dn0max = O(" d) hyper-rectangles. The worst-case complexity bound is similar to the complexity of the Grid Based Majoring Points. However, depending on f , the number of hyper-rectangles generated by the algorithm can be much smaller than this worst-case complexity bound. The smoother the function f , the less hyper-rectangles are generated.
Algorithm 1 Adaptive cover construction Require: " : Distance below which we stop decomposing Require: "f : Target upper bound for the error in f Require: np : number of examples in a decomposable hyper-rectangle Require: Inputs needed to compute f (resp. f~) Require: ymin; ymax : Points satisfying (7)
C fRymin;ymax g t 0 while t 6= 1 do t 1 C0 ; for Ry;y0 2 C do if Ry;y0 satisfies (11) (resp. (12)) then
C0 C0 [ fRy;y0 g else t 0 for all sub-parts R of Ry;y0 (see (10)) do
C0 C0 [ fRg end for end if end for
C C0 end while return C
In this section, we remind known result on the
approximation of non-decreasing functions with neural networks
having non-negative weights and non-decreasing
activation functions
For any neural network such that: • its activation functions are non-decreasing • its weights w are non-negative the function fw;b defined by the neural network is nondecreasing.
The conditions are sufficient but not necessary. We can think of simple non-decreasing neural network with both positive and negative weights. However, as stated in the next theorem, neural networks with non-negative weights are universal approximators of non-decreasing functions.
Let D Rd be compact. For any continuous nondecreasing function g : D ! R . For any > 0, there exist a feed-forward neural network with d hidden layers, a non-decreasing activation function, non-negative weights w and bias b such that jg(x) fw ;b (x)j , for all x 2 D; where fw ;b is the function defined by the neural network.
Notice that, in
Theorem 1 guarantees that a well-chosen and optimized neural network with non-negative weights can approximate with any required accuracy the smallest non-decreasing majorant1 of fC, as defined in (3).
We consider a feed-forward neural network of depth h. The hidden layers are of width l. The weights are denoted by w and we will restrict the search to non-negative weights: w 0. The bias is denoted by b. We consider, for a parameter > 0, the activation function
t (t) = tanh( ) for all t 2 R:
We consider an asymmetric loss function in order to
penalize more underestimation than overestimation
+(t )2 if t
l ; +; ;p(t) = jt jp if t <
where the parameters ( +; ; ) 2 R3 are non-negative
and p 2 N. Notice that asymmetric loss functions have
already been used to penalize either under-estimation or
overestimation (Yao and Tong 1996)
Given Majoring Points (ai; bi)i=1::m, we define, for all w and b
m E(w; b) = X l ; +; ;p(fw;b(ai)
i=1
The parameters of the network optimize
bi):
argminw 0;b E(w; b):
(13)
The function E is smooth but non-convex. In order to solve
(13), we apply a projected stochastic gradient algorithm
The parameter 0 is an offset parameter. Increasing leads to poorer approximations. We show in the following proposition that can be arbitrarily small, if the other parameters are properly chosen.
Let > 0, > 0, p > 0. If the neural network is sufficiently large and if is sufficiently small, then fw ;b (ai) bi Given Theorem 1, when the network is sufficiently large and is sufficiently small there exist a bias b0 and non-negative weights w0 such that for all i = 1::m: jfw0;b0 (ai)
(bi + )j
E(w ; b )
E(w0; b0) m X max( i=1 p: p; + 2) p: : (15) p: If by contradiction we assume that there exists i0 such that fw ;b (ai0 ) < bi0 then we must have
E(w ; b ) l ; +; ;p(fw ;b (ai0 ) bi0 ) > This contradicts (15) and we conclude that (14) holds.
The proposition guarantees that for a large network, with
small, we are sure to overestimate the target. Because
Theorem 1 does not provide a configuration (depth, width,
activation function) that permits to approximate any
function with an accuracy , it is not possible to provide such a
configuration for the parameters in Proposition 3. However,
given a configuration and given weights w and bias b
returned by an algorithm, it is possible to test if (14) holds. If
is does not hold, it is always possible to increase the width,
depth, etc and redo the optimization. Theorem 1 and
Proposition 3, combined with properties of the landscape of large
networks such as
4
In this section, we compare the results of several learning strategies on two synthetic experiments with d = 1 and 2 and on a real dataset from avionic industry. The synthetic experiments permit to illustrate the method; the latter real dataset show that the method permits to construct a surrogate of a critical function that can be embedded while the true critical function cannot.
The python codes that have been used to generate the experiments, as well as additional experiments, are provided with the submission and will be made available on an open source deposit.
The architecture of the network is the same for all experiments and contains 4 fully connected layers with 64 neurons in each layer. The memory requirement to store the network is 64 d + 4 642 + 5 64 = 64d + 16705 floating numbers. The size of the input layer is d. The size of the output layer is 1. We compare: • The -baseline: For a parameter 0, it is a simple neural network, with an `2 loss. It is trained: – on the points (ai; f (ai)+ )i=1::m, when f can be computed; – on the modified dataset (xi; f (xi) + )i=1::n, when f cannot be computed.
The -baseline is in general not guaranteed to provide an overestimation. The 0-baseline is expected to provide a better approximation of the true function f than the other methods but it fails to always overestimating it.
If is such that f (ai) + bi, for all i = 1::m, the -baseline is guaranteed to provide an overestimation. • The Overestimating Neural Network (ONN): Is a neural network whose parameters solve (13) for the parameters ; +; and p coarsely tuned for each experiment, and depending on the context, the Grid Based Majoring Points (ONN with GMP), the Function Adapted Majoring Points (ONN with FMP), the Grid Based Majoring Points (ONN with DMP).
We always take = 1. The size of the network and the values of s ; +; and p always permit to have fw ;b (ai) bi, for all i = 1::m. Therefore, as demonstrated in the previous sections, fw ;b is guaranteed to overestimate f .
We are defining in this section the metrics that are used to compare the methods. Some metrics use a test dataset (x0i; f (x0i))i=1::n0 .
For the 1D synthetic example, we take n0 = 100000 and for the industrial example, we take n0 = 75000. In both cases the x0i are iid according to the uniform distribution in D. We consider the Majoring Approximation Error (MAE) defined by the Root Mean Square Error (RMSE) defined by 1 m
X(bi m
i=1 M AE =
f (ai)); 0 f (x0i))2A ; the Overestimation proportion (OP) defined by 100 n0 jfijfw ;b (x0i) f (x0i)gj ; and remind if the method guarantees fw ;b overestimates f Formal Guarantee (FG).
For the experiments on the 1D synthetic example the methods are also evaluated using visual inspection.
The 1D synthetic experiment aims at overestimating the function f1 defined over [ 10; 10] by
The function f1, fC, fw ;b for Grid Based Majoring Points and the 0:2-baseline are displayed on Figure 1, on the interval [ 4:5; 2]. The function f1f , the Grid Based Majoring Points and fw ;b for Grid Based Majoring Points and the 0:2-baseline are displayed on Figure 2, on the interval [0:8; 1:2]. The function f1, the Data Adapted Majoring Points, the sample (xi; f1(xi))i=1::n and fw ;b for Data Adapted Majoring Points are displayed on Figure 3, on the interval [ 5:5; 0].
We clearly see that the adaptive Majoring Points aggregate in dyadic manner in the vicinity of the discontinuities. We also see on Figure 2 how Majoring Points permit to anticipate the discontinuity and construct an overestimation. The density of Majoring Points depends on the slope of f1. This permits to reduce the approximation error. Also, fw ;b passes in the vicinity of the Majoring Points and provides a good approximation that overestimates f .
The MAE, RMSE, OP and FG are provided in Table 1 for the 0-baseline, the 0:5-baseline, fC and the ONN for three types of Majoring Points. We see that the RMSE worsen as we impose guarantees and approach the realistic scenario where the surrogate is easy to compute and does not require too much memory consumption.
The same phenomenon described on 1D synthetic experiment occur in dimension 2. We only illustrate here the difference between the Grid Based Majoring Points, Function Adapted Majoring Points and Data Adapted Majoring Points for the function 8(x; y) 2 [0; 15]2 g(x; y) = f1 px2 + y2 10 where f1 is the function defined in (16).
We display, on Figure 5, the Function Adapted Majoring Points returned by the Dichotomy Algorithm. The density of points is correlated with the amplitude of the gradient of the function. Algorithm 1 permit to diminish the number of Majoring Points. For instance, for the 2D synthetic example for " = 0:1, the Grid Based Majoring Points counts 22500 points. The Function Adapted Majoring Points counts 14898 points, for " = 0:5, and 3315, for " = 2. The Data Adapted Majoring Points counts 8734 points, for " = 0:5, and 1864, for " = 2.
On Figure 4, we represent the dataset and the cover obtained using Algorithm 1 for the synthetic 2D example. The inputs ai of the corresponding Majoring Points are displayed on Figure 5.
The method developed in this paper provides formal guarantees of overestimation that are safety guarantee directly applicable in critical embedded systems. (a) Complete domain
(b) Zoom on the discontinuity
The construction of surrogate functions is an important
subject in industry
The industrial dataset contains n = 150000 examples on a static grid and another set of 150000 sampled according to the uniform distribution on the whole domain. For each inputs, the reference computation code is used to generate the associated true output.
We compare 0-baseline,300-baseline with the ONN learned on Grid Based Majoring Points and Data Adapted Majoring Points methods. All the methods are learned on the Method 0-baseline 300-baseline ONN with GMP ONN with DMP n static grid except OON with Data Adapted Majoring Points. The table 2 presents the metrics for the different methods. The results are acceptable for the application and memory requirement to store and embed the neural network is 17088 floating numbers. It is one order of magnitude smaller than the size of the dataset.
5
We presented a method that enables to formally guarantee that a prediction of a monotonic neural network will always be in an area that preserves the safety of a system. This is achieved by the construction of the network, the utilization of majoring points and the learning phase, which allows us to free ourselves from a massive testing phase that is long and costly while providing fewer guarantees.
Our work have limitations on functions that can be a safely approximate, but this is a first step toward a safe use of neural networks in critical applications. Nevertheless, this can already be used in simple safety critical systems that verify our hypotheses. Future works will look on possibility to leverage the utilization of the monotonic hypothesis. Another direction of improvement is to build smarter algorithms that require less majoring points thanks to a better adaptation to the structure of the function. In particular, this should permit to apply the method to functions whose is input space is of larger dimension, when they have the proper structure.
This project received funding from the French ”Investing for the Future – PIA3” program within the Artificial and Natural Intelligence Toulouse Institute (ANITI) under the grant agreement ANR-19-PI3A-0004. The authors gratefully acknowledge the support of the DEEL project.2