Overestimation learning with guarantees Adrien Gauffriau1 * François Malgouyres2† , Mélanie Ducoffe1‡ 1 IRT Saint Exupéry, Toulouse, France 2 Institut de Mathématiques de Toulouse ; UMR5219 Université de Toulouse ; CNRS ; UPS IMT F-31062 Toulouse Cedex 9, France {adrien.gauffriau, melanie.ducoffe}@irt-saintexupery.com, Francois.Malgouyres@math.univ-toulouse.fr Abstract Inspired by critical systems applications, we require (1) to We describe a complete method that learns a neural network be guaranteed by a formal theorem. We call fw∗ ,b∗ the sur- which is guaranteed to over-estimate a reference function on rogate and call f the model. a given domain. The neural network can then be used as a In the typical application we have in mind, f is the re- surrogate for the reference function. sult of a deterministic but complex phenomenon. It is dif- The method involves two steps. In the first step, we construct ficult to compute and its evaluation requires intensive com- an adaptive set of Majoring Points. In the second step, we putations or extensive memory consumption. We consider optimize a well-chosen neural network to over-estimate the two settings. In the first setting, we can evaluate f (x) for Majoring Points. any x ∈ D. In the second setting, we only know a data set In order to extend the guarantee on the Majoring Points to the (xi , f (xi ))i=1..n of size n ∈ N. whole domain, we necessarily have to make an assumption The constructed surrogate fw∗ ,b∗ permits to rapidly eval- on the reference function. In this study, we assume that the uate an approximation of f at any point of D. Of course, reference function is monotonic. we want the surrogate fw∗ ,b∗ to approximate f well; but We provide experiments on synthetic and real problems. The most importantly we want fw∗ ,b∗ to overestimate f . In the experiments show that the density of the Majoring Points con- typical scenario we have in mind, f models the consump- centrate where the reference function varies. The learned tion of some resource for a critical action. Underestimating over-estimations are both guaranteed to overestimate the ref- erence function and are proven empirically to provide good the model may cause a (potentially deadly) hazard that will approximations of it. not be acceptable for certification authorities especially in Experiments on real data show that the method makes it pos- aeronautics (EASA or FAA). The applications include for sible to use the surrogate function in embedded systems for instance: - the estimation of the braking distance of an au- which an underestimation is critical; when computing the ref- tonomous vehicle; - the number of kilometers that can be erence function requires too many resources. traveled; - the maximum load a structure can carry, - the net- work traveling time etc Guaranteed overestimation can also be used to guarantee the fairness of a score, when underesti- 1 Introduction mation on a sub-population leads to an unfair surrogate func- Overestimation guarantee tion. Providing such fairness or performance guarantee can In this paper, we consider a real value finite function f de- be seen as a niche activity, but it alleviates the limitation that fined on a compact domain D and describe a method that restrains the massive industrialization of neural networks in finds optimal weights w∗ and bias b∗ such that the neural critical applications where passengers lives are at stake. network fw∗ ,b∗ both provides a good approximation of f : Finally, the adaptation of the method to construct an fw∗ ,b∗ ∼ f, under-estimation of f is straightforward and, for ease of pre- sentation, not exposed in the paper. Of course, the combina- and is guaranteed to overestimate f over D: tion of both an over-estimation and an under-estimation per- fw∗ ,b∗ (x) ≥ f (x) for all x ∈ D. (1) mits, for any x, the construction of an interval in which f (x) is guaranteed to be. * seconded from Airbus Operations, Toulouse † This work has benefited from the AI Interdisciplinary Institute Related works ANITI. ANITI is funded by the French ”Investing for the Future – PIA3” program under the Grant agreement n°ANR-19-PI3A-0004. The most standard type of guarantees in machine learning ‡ seconded from Airbus AI Research, Toulouse aim at upper-bounding the risk by upper-bounding the gen- Copyright © 2021 for this paper by its authors. Use permitted under eralization error (see (Anthony and Bartlett 1999) for an Creative Commons License Attribution 4.0 International (CC BY overview). We would like to highlight that the risk measures 4.0). an average cost that does not exclude failures. Moreover, at the writing of this paper, the bounds on the generalization er- Another restriction is that the method cannot be applied ror are very pessimistic when compared to the performance when the dimension d is large and f varies in all directions. observed in practice (Harvey, Liaw, and Mehrabian 2017; In fact, one contribution of the paper is to design algorithms Bartlett et al. 2019) and the recent overview (Jakubovitz, to alleviate this problem and apply the method for larger d, Giryes, and Rodrigues 2019). In particular, neural network but d must anyway remain moderate for most function f . are commonly learned with much less examples than re- These hypotheses permit to have global guarantee that quired by the theory. hold on the whole domain D while weaker hypotheses on Other works provide guarantees on the neural network f only lead to local guarantees, holding in the close vicinity performance (Mirman, Gehr, and Vechev 2018; Boopathy of the learning examples. et al. 2019; Katz et al. 2017) that can be used to exclude failures (in our setting, the under-estimation of f ). The phi- Organization of the paper losophy of these works is to analyze the output of the learn- In the next section, we define Majoring Points and describe a ing phase in order to provide guarantees of robustness. An- grid based and an adaptive algorithm to construct them. The other line of research, is to impose constraints or optimize algorithms are adapted when the function f can be evaluated robustness criteria during the learning phase (Fischer et al. at any new input as well as when we only know a dataset 2019; Raghunathan, Steinhardt, and Liang 2018). This does (xi , f (xi ))i=1..n . In Section 3, we describe a strategy to not permit to guarantee an over-estimation property. construct monotonic, over-estimating neural networks. Fi- Finally, another direction makes probabilistic assump- nally, in Section 4, we provide experiments showing that the tions and provides confidence scores (Gal and Ghahramani Majoring Points are located in the regions where f varies 2016; Pearce et al. 2018; Tagasovska and Lopez-Paz 2019; strongly or is discontinuous. We also illustrate on synthetic Keren, Cummins, and Schuller 2018). The confidence score examples that the method can accurately approximate f , does not necessarily provide a formal guarantee. while being guaranteed to overestimate it. An example on Compared to these approaches, the guarantee on the sur- real data illustrates that the use of over-estimating neural net- rogate fw∗ ,b∗ is due to the attention given to the construction works permits to reduce the memory required to compute an of the learning problem and the hypotheses on the function over-estimation and thus permits to embed it, in a real world f . To the best of our knowledge, and not considering trivial application. overestimation with poor performances, we are not aware of any other construction of a surrogate fw∗ ,b∗ that is guaran- 2 Majoring Points teed to overestimate the model f . Introduction Hypotheses and restrictions Definition 1. Majoring Points m In order to extend the overestimation property to the whole Let (ai , bi )i=1..m ∈ Rd × R . Let D ⊂ Rd be compact domain we can obviously not consider any arbitrary func- and let f : Rd −→ R be finite and non-decreasing. We say tion f . In this paper, we restrict our analysis to real-valued that (ai , bi )i=1..m are Majoring Points for f if and only if and finite non-decreasing functions. The extension to vec- for any non-decreasing g : Rd −→ R : tor valued function is straightforward. The extension to If g(ai ) ≥ bi , ∀i = 1..m, then g(x) ≥ f (x), ∀x ∈ D. non-increasing functions is straightforward too. We delib- When f is upper-bounded on D, the existence of such ma- erately use these restrictive hypotheses to simplify the pre- joring points is established by considering: m = 1, sentation. Furthermore, many extensions of the principles of the method described in the paper to other classes of non- • a1 such that a1 ≤ x for all x ∈ D, monotone functions are possible. • b1 = supx∈D f (x). Formally, for a compact domain D ⊂ Rd , a function g : However, for most function f , any non-decreasing g such D −→ R is non-decreasing if and only if that g(a1 ) ≥ b1 is a poor approximation of f . The goal, g(x) ≤ g(x0 ) for all x ≤ x0 when constructing Majoring Points of f is to have bi ∼ f (ai ), while bi ≥ f (ai ), for all i = 1..m. The number of where the partial order on Rd is defined for any x = points m should remain sufficiently small to make the opti- (xk )k=1..d and x0 = (x0k )k=1..d ∈ Rd by mization of the neural network manageable. x ≤ x0 if and only if xk ≤ x0k , for all k = 1..d. Constructing Majoring Points using a cover Other authors have already studied the approximation of For any y and y 0 ∈ Rd , with y ≤ y 0 , we define the hyper- non-decreasing functions with neural networks (Lang 2005; rectangle between y and y 0 by Daniels and Velikova 2010; Sill 1998). In our context, the monotonic hypothesis is motivated by the fact that mono- Ry,y0 = {x ∈ Rd |y ≤ x < y 0 }. tone function are ubiquitous in industrial applications and in Using hyper-rectangles, we define the considered covers. physics. Moreover, for a given application, where a function Definition 2. Cover 0 f 0 : Rd −→ R needs to be approximated. It is sometimes Let (yi )i=1..m and (yi0 )i=1..m in Rd be such that yi0 ≥ yi , 0 possible to extract features with a function g : Rd −→ Rd for all i = 1..m. We say that (yi , yi0 )i=1..m covers D if and d 0 such that the function f : R −→ R, satisfying f = f ◦ g, only if is monotone. D ⊂ ∪m i=1 Ryi ,yi0 . (2) For any cover C = (yi , yi0 )i=1..m , we define the function solution of an optimization taking into account these two properties. However, the optimization would be intractable fC (x) = min f (yi0 ) , for all x ∈ D. (3) i : x∈Ry ,y0 and we only describe an heuristic algorithm that construct a i i cover. Notice that, since C is a cover, {i|x ∈ Ryi ,yi0 } =6 ∅ and We construct Majoring Points according to two scenarios: fC (x) is well-defined. We can establish that the function fC • We can generate f (x) for all x ∈ Rd . We call the Ma- overestimates f over D: joring Points generated according to this setting Function For all x ∈ D, fC (x) ≥ f (x). (4) Adapted Majoring Points. • We have a dataset (xi , f (xi ))i=1..n . It is not possible to Indeed, for any x ∈ D, there exists i such that x ∈ Ryi ,yi0 have access to more training points. We call the Majoring and fC (x) = f (yi0 ). Therefore, since f is non-decreasing Points generated according to this setting Data Adapted and x ≤ yi0 , we have Majoring Points. In order to define them, we consider the f (x) ≤ f (yi0 ) = fC (x). function f˜ : Rd −→ R defined, for all x ∈ Rymin ,ymax , by Proposition 1. A cover defines Majoring Points f˜(x) = min f (xi ). (8) Let D ⊂ Rd be compact. Let C = (yi , yi0 )i=1..m be i:xi ≥x a cover of D and let f : Rd −→ R be finite and Since f is non-decreasing, we have non-decreasing. The family (yi , f (yi0 ))i=1..m are Majoring Points for f . f˜(x) ≥ f (x) for all x ∈ Rymin ,ymax . Proof. We consider a non-decreasing function g such that, At the core of the constructions described below is the con- struction of a cover C = (yi , yi0 )i=1..m . for all i = 1..m, g(yi ) ≥ f (yi0 ). (5) Grid Based Majoring Points We consider an accuracy We need to prove that, parameter ε > 0 and a norm k.k on Rd . We define for all x ∈ D, g(x) ≥ f (x). kymax − ymin k nmax = d e. To do so, we consider x ∈ D and i such that x ∈ R . yi ,yi0 ε Using respectively that g is non-decreasing, (5), the defini- A simple way to define Majoring Points is to generate tion of fC (3) and (4), we obtain the following sequence of a cover made of equally spaced points between ymin and inequalities: ymax . Setting g(x) ≥ g(yi ) ≥ f (yi0 ) ≥ fC (x) ≥ f (x). (6) ymax − ymin r= ∈ Rd nmax and for all i0 , · · · , id−1 ∈ {1, . . . , N − 1}, we set i = The function fC can be computed rapidly using a look- Pd−1 k up table but requires storing (yi , f (yi0 ))i=1..m . This can be k=0 ik N and prohibitive in some applications.  yi = ymin + (i0 r1 , . . . , id−1 rd ) To deal with this scenario, we describe in Section 3 a yi0 = yi + r method to construct a neural network such that fw∗ ,b∗ is non-decreasing and satisfies fw∗ ,b∗ (yi ) ≥ f (yi0 ), for all Notice that, the parameter r defining the grid satisfies i = 1..m. According to the proposition, such a network pro- krk ≤ ε. Given the cover, the Function Adapted Majoring vides a guaranteed over-estimation of f , whose computation Points (ai , bi )i=0..N d −1 are defined, for i = 0..ndmax − 1, by is rapid. The resources required to store w∗ and b∗ are in-  ai = yi dependent of m. We show in the experiments that it can be (9) bi = f (yi0 ) several orders of magnitude smaller. This makes it possible to embed the overestimating neural network when embed- We can also construct a Grid Based Majoring Points when ding the Majoring Points is not be possible. This advantage the function f cannot be evaluated but a dataset comes at the price of loss of accuracy as fw∗ ,b∗ (x) ≥ fC (x) (xi , f (xi ))i=1..n is available by replacing in the above defi- (fw∗ ,b∗ (x) has the role of g in (6)). nition f by f˜, see (8). The Grid Based Majoring Points are mostly given for ped- Majoring Points construction algorithm agogical reasons. The number of values f (x) that need to be Introduction In this section, we describe algorithmic evaluated and the number of Majoring Points defining the strategies to adapt Majoring Points to the function f . objective of the optimization of the neural network are both Throughout the section, we assume that we know ymin and equal to ndmax = O(ε−d ). It scales poorly with d and this re- ymax ∈ Rd such that strains the application of the Grid Based Majoring Points to small d, whatever the function f . D ⊂ Rymin ,ymax . (7) When f does not vary much in some areas, the Majoring The goal is to build a cover such that fC is close to f and Points in this area are useless. This is what motivates the m is not too large. Ideally, the cover can be expressed as the adaptive algorithms developed in the next sections. Adaptive Majoring Points Bellow, we describe a Di- Algorithm 1 Adaptive cover construction chotomy Algorithm that permits to generate an adaptive Require: ε : Distance below which we stop decomposing cover with regard to the variations of the function f (or f˜). Require: εf : Target upper bound for the error in f It begins with a cover made of the single hyper-rectangle Require: np : number of examples in a decomposable Rymin ,ymax . Then it decomposes every hyper-rectangle of hyper-rectangle the current cover that have not reached the desired accuracy. Require: Inputs needed to compute f (resp. f˜) The decomposition is repeated until all the hyper-rectangle Require: ymin , ymax : Points satisfying (7) of the current cover have the desired accuracy (see Algo- rithm 1). C ← {Rymin ,ymax } Initially, we have D ⊂ Rymin ,ymax . For any hyper- t←0 0 rectangle Ry,y0 , denoting r = y 2−y , the decomposition re- while t 6= 1 do places Ry,y0 by its sub-parts as defined by t←1  C0 ← ∅ Ry+(s1 r1,...,sd rd ),y+(s1 +1)r1,...,(sd +1)rd ) | for Ry,y0 ∈ C do (s1 , . . . , sd ) ∈ {0, 1}d . (10) if Ry,y0 satisfies (11) (resp. (12)) then C 0 ← C 0 ∪ {Ry,y0 } (Hence the term ‘dichotomy algorithm’. ) The union of the else sub-parts equal the initial hyper-rectangle. Therefore, the t←0 cover remains a cover after the decomposition. The final C for all sub-parts R of Ry,y0 (see (10)) do is a cover of D. C 0 ← C 0 ∪ {R} We consider a norm k.k on Rd and real parameters ε > end for 0, εf > 0 and np ∈ N. We stop decomposing an hyper- end if rectangle if a notion of accuracy is satisfied. The notion of end for accuracy depends on whether we can compute f or not. C ← C0 • When we can evaluate f (x): The accuracy of Ry,y0 is de- end while fined by the test return C f (y 0 ) − f (y) ≤ εf or ky 0 − yk ≤ ε (11) • When we only know a dataset (xi , f (xi ))i=1..n : The ac- 3 Overestimating neural networks curacy of Ry,y0 is defined by the test Monotonic Neural Networks f˜(y 0 ) − f˜(y) ≤ εf In this section, we remind known result on the approxi-  or ky 0 − yk ≤ ε (12) or |{i|xi ∈ Ry,y }| ≤ np 0 mation of non-decreasing functions with neural networks having non-negative weights and non-decreasing activa- where |.| is the cardinal of the set. tion functions (Lang 2005; Daniels and Velikova 2010; Sill We stop decomposing if a given accuracy is reached : 1998). • when f (y 0 ) − f (y) ≤ εf or f˜(y 0 ) − f˜(y) ≤ εf : This Proposition 2. Sufficient condition to get a non- happens where the function f varies only slightly. decreasing network For any neural network such that: • when ky 0 − yk: This happens where the function f varies strongly. • its activation functions are non-decreasing • its weights w are non-negative • when |{i|xi ∈ Ry,y0 }| ≤ np : This happens when the number of samples in Ry,y0 does not permit to improve the function fw,b defined by the neural network is non- the approximation of f by f˜ in its sub-parts. decreasing. The cover is constructed according to Algorithm 1. This The conditions are sufficient but not necessary. We can algorithm to stop after at most n0max = think of simple non-decreasing neural network with both  is guaranteed  positive and negative weights. However, as stated in the next dlog2 kymax −y ε min k e iteration of the ‘while loop’. In the theorem, neural networks with non-negative weights are uni- worst case, every hyper-rectangle of the current cover is de- versal approximators of non-decreasing functions. composed into 2d hyper-rectangles. Therefore, the worst- Theorem 1. Universality of neural networks with non- case complexity of the algorithm creates negative weights (Daniels and Velikova 2010) 0 2dnmax = O(ε−d ) Let D ⊂ Rd be compact. For any continuous non- decreasing function g : D → R . For any η > 0, there hyper-rectangles. The worst-case complexity bound is sim- exist a feed-forward neural network with d hidden layers, ilar to the complexity of the Grid Based Majoring Points. a non-decreasing activation function, non-negative weights However, depending on f , the number of hyper-rectangles w∗ and bias b∗ such that generated by the algorithm can be much smaller than this worst-case complexity bound. The smoother the function f , |g(x) − fw∗ ,b∗ (x)| ≤ η , for all x ∈ D, the less hyper-rectangles are generated. where fw∗ ,b∗ is the function defined by the neural network. Notice that, in (Daniels and Velikova 2010), the neural Proof. Since α− β p > 0, there exists η > 0 such that network constructed in the proof of Theorem 1 involves a Heaviside activation function. The choice of the activation m max(α− η p , α+ η 2 ) ≤ α− β p . function is important. For instance, with a convex activation Given Theorem 1, when the network is sufficiently large and function (like ReLU), the function defined by the neural net- θ is sufficiently small there exist a bias b0 and non-negative work with non-negative weights is convex (Amos, Xu, and weights w0 such that for all i = 1..m: Kolter 2017) and may approximate arbitrary poorly a well- chosen non-decreasing non-convex function. |fw0 ,b0 (ai ) − (bi + β)| ≤ η. Theorem 1 guarantees that a well-chosen and optimized Therefore, neural network with non-negative weights can approximate with any required accuracy the smallest non-decreasing ma- E(w∗ , b∗ ) ≤ E(w0 , b0 ) jorant1 of fC , as defined in (3). m X ≤ max(α− η p , α+ η 2 ) Learning the neural network i=1 We consider a feed-forward neural network of depth h. The − p ≤ α β . (15) hidden layers are of width l. The weights are denoted by w and we will restrict the search to non-negative weights: w ≥ If by contradiction we assume that there exists i0 such that 0. The bias is denoted by b. We consider, for a parameter fw∗ ,b∗ (ai0 ) < bi0 θ > 0, the activation function t then we must have σ(t) = tanh( ) for all t ∈ R. θ E(w∗ , b∗ ) ≥ lβ,α+ ,α− ,p (fw∗ ,b∗ (ai0 ) − bi0 ) > α− β p . We consider an asymmetric loss function in order to pe- nalize more underestimation This contradicts (15) and we conclude that (14) holds.  than overestimation α+ (t − β)2 if t ≥ β The proposition guarantees that for a large network, with lβ,α+ ,α− ,p (t) = α− |t − β|p if t < β θ small, we are sure to overestimate the target. Because where the parameters (α+ , α− , β) ∈ R3 are non-negative Theorem 1 does not provide a configuration (depth, width, and p ∈ N. Notice that asymmetric loss functions have al- activation function) that permits to approximate any func- ready been used to penalize either under-estimation or over- tion with an accuracy η, it is not possible to provide such a estimation (Yao and Tong 1996) (Julian, Kochenderfer, and configuration for the parameters in Proposition 3. However, Owen 2019). given a configuration and given weights w∗ and bias b∗ re- Given Majoring Points (ai , bi )i=1..m , we define, for all w turned by an algorithm, it is possible to test if (14) holds. If and b is does not hold, it is always possible to increase the width, m depth, etc and redo the optimization. Theorem 1 and Propo- sition 3, combined with properties of the landscape of large X E(w, b) = lβ,α+ ,α,p (fw,b (ai ) − bi ). i=1 networks such as (Nguyen and Hein 2017), guarantee that such a strategy stops after a finite number of optimization The parameters of the network optimize procedure. argminw≥0,b E(w, b). (13) The function E is smooth but non-convex. In order to solve 4 Experiments (13), we apply a projected stochastic gradient algorithm In this section, we compare the results of several learning (Bianchi and Jakubowicz 2012). The projection on the con- strategies on two synthetic experiments with d = 1 and 2 straint w ≥ 0 is obtained by canceling its negative entries. and on a real dataset from avionic industry. The synthetic As often with neural network, we cannot guarantee that the experiments permit to illustrate the method; the latter real algorithm converges to a global minimizer. dataset show that the method permits to construct a surrogate of a critical function that can be embedded while the true Guaranteeing fw∗ ,b∗ (ai ) ≥ bi critical function cannot. The parameter β ≥ 0 is an offset parameter. Increasing β The python codes that have been used to generate the ex- leads to poorer approximations. We show in the following periments, as well as additional experiments, are provided proposition that β can be arbitrarily small, if the other pa- with the submission and will be made available on an open rameters are properly chosen. source deposit. Proposition 3. Guaranteed overestimation of the sam- ples Methods to be compared Let β > 0, α− > 0, p > 0. If the neural network is The architecture of the network is the same for all experi- sufficiently large and if θ is sufficiently small, then ments and contains 4 fully connected layers with 64 neurons fw∗ ,b∗ (ai ) ≥ bi for all i = 1..m, (14) in each layer. The memory requirement to store the network is 64×d+4×642 +5∗64 = 64d+16705 floating numbers. for any w and b∗ solving (13). ∗ The size of the input layer is d. The size of the output layer 1 Notice fC is not necessarily non-decreasing. 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 com- puted; – 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. Figure 1: 1D synthetic experiment with Grid Based Major- • The Overestimating Neural Network (ONN): Is a neu- ing Points ral network whose parameters solve (13) for the param- eters β, α+ , α and p coarsely tuned for each experiment, and depending on the context, the Grid Based Majoring Points (ONN with GMP), the Function Adapted Major- ing 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 demon- strated in the previous sections, fw∗ ,b∗ is guaranteed to overestimate f . Evaluation metrics Figure 2: Discontinuity of 1D synthetic experiment with We are defining in this section the metrics that are used Grid Based Majoring Points 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   3x + 3 sin(x) − 4 if x ∈ [−10; −1) cases the x0i are iid according to the uniform distribution f1 (x) = −sign(x).x2 + sin(x) if x ∈ [−1; 1] in D. We consider the Majoring Approximation Error  x + cos(x) + 10 if x ∈ (1; 10] (MAE) defined by (16) m 1 X M AE = (bi − f (ai )); The function f1 , fC , fw∗ ,b∗ for Grid Based Majoring m i=1 Points and the 0.2-baseline are displayed on Figure 1, on the Root Mean Square Error (RMSE) defined by the interval [−4.5, −2]. The function f1 f , the Grid Based Majoring Points and fw∗ ,b∗ for Grid Based Majoring   12 Points and the 0.2-baseline are displayed on Figure 2, on the n0 1 interval [0.8, 1.2]. The function f1 , the Data Adapted Ma- X (fw∗ ,b∗ (x0i ) − f (x0i ))2  ; joring Points, the sample (xi , f1 (xi ))i=1..n and fw∗ ,b∗ for n0 i=1 Data Adapted Majoring Points are displayed on Figure 3, the Overestimation proportion (OP) defined by on the interval [−5.5, 0]. We clearly see that the adaptive Majoring Points aggre- 100 gate in dyadic manner in the vicinity of the discontinuities. |{i|fw∗ ,b∗ (x0i ) ≥ f (x0i )}| ; n0 We also see on Figure 2 how Majoring Points permit to an- ticipate the discontinuity and construct an overestimation. and remind if the method guarantees fw∗ ,b∗ overesti- The density of Majoring Points depends on the slope of f1 . mates f Formal Guarantee (FG). This permits to reduce the approximation error. Also, fw∗ ,b∗ For the experiments on the 1D synthetic example the passes in the vicinity of the Majoring Points and provides a methods are also evaluated using visual inspection. good approximation that overestimates f . The MAE, RMSE, OP and FG are provided in Table 1 for 1D synthetic experiment the 0-baseline, the 0.5-baseline, fC and the ONN for three The 1D synthetic experiment aims at overestimating the types of Majoring Points. We see that the RMSE worsen as function f1 defined over [−10, 10] by we impose guarantees and approach the realistic scenario (a) Complete domain (b) Zoom on the discontinuity Figure 4: Data Majoring Points grid Figure 3: 1D synthetic experiment with Data Adapted Ma- joring Points n MAE RMSE OP FG 0-baseline 200 N/A -.04 51.9 % NO 0.5-baseline 200 0.5 0.59 99.5% NO fC 200 N/A 0.10 100 % YES ONN with GMP 200 0.24 0.23 100% YES ONN with FMP 200 0.23 0.55 100% YES ONN with DMP 500 0.82 0.60 100% YES Table 1: Metrics - 1D synthetic experiment (a) Complete domain (b) Zoom on the discontinuity Figure 5: Function Adapted Majoring Points on synthetic where the surrogate is easy to compute and does not require 2D f . too much memory consumption. 2D synthetic experiment The construction of surrogate functions is an important The same phenomenon described on 1D synthetic exper- subject in industry (Lathuilière et al. 2019; Biannic et al. iment occur in dimension 2. We only illustrate here the 2016; Jian et al. 2017; Sudakov et al. 2019). In this work, difference between the Grid Based Majoring Points, Func- we are considering an industrial and heavy simulation code tion Adapted Majoring Points and Data Adapted Majoring that has six inputs d = 6 and one output and that represents Points for the function a complex physic phenomenon of an aircraft. The output is p  an non-decreasing function. During the flight, given flight ∀(x, y) ∈ [0; 15]2 g(x, y) = f1 x2 + y 2 − 10 conditions x the output f (x) is compared to a threshold and the result of the test launch an action. When we replace f by where f1 is the function defined in (16). the overestimating surrogate fw∗ ,b∗ , the airplane launches We display, on Figure 5, the Function Adapted Majoring the action less often. However, the airplane only launches Points returned by the Dichotomy Algorithm. The density the action when the action is guaranteed to be safe. of points is correlated with the amplitude of the gradient of The industrial dataset contains n = 150000 examples on the function. Algorithm 1 permit to diminish the number of a static grid and another set of 150000 sampled according Majoring Points. For instance, for the 2D synthetic example to the uniform distribution on the whole domain. For each for ε = 0.1, the Grid Based Majoring Points counts 22500 inputs, the reference computation code is used to generate points. The Function Adapted Majoring Points counts 14898 the associated true output. points, for ε = 0.5, and 3315, for ε = 2. The Data Adapted We compare 0-baseline,300-baseline with the ONN Majoring Points counts 8734 points, for ε = 0.5, and 1864, learned on Grid Based Majoring Points and Data Adapted for ε = 2. Majoring Points methods. All the methods are learned on the On Figure 4, we represent the dataset and the cover ob- tained using Algorithm 1 for the synthetic 2D example. The inputs ai of the corresponding Majoring Points are displayed Method n nmaj RMSE MAE OP FG on Figure 5. 0-baseline 150k 150k 3.3 N/A 65.1% NO 300-baseline 150k 150k 302.6 300.0 100% NO Industrial application ONN with GMP 150k 150k 309.3 262.7 100% YES The method developed in this paper provides formal guar- ONN with DMP 150k0 110k 445.7 N/A N/A YES antees of overestimation that are safety guarantee directly applicable in critical embedded systems. Table 2: Results on the industrial dataset static grid except OON with Data Adapted Majoring Points. Biannic, J.; Hardier, G.; Roos, C.; Seren, C.; and Verdier, The table 2 presents the metrics for the different methods. L. 2016. Surrogate models for aircraft flight control: some The results are acceptable for the application and memory off-line and embedded applications. AerospaceLab Journal requirement to store and embed the neural network is 17088 (12): pages–1. floating numbers. It is one order of magnitude smaller than Boopathy, A.; Weng, T.-W.; Chen, P.-Y.; Liu, S.; and Daniel, the size of the dataset. L. 2019. Cnn-cert: An efficient framework for certifying robustness of convolutional neural networks. In Proceed- 5 Conclusion - Future Work ings of the AAAI Conference on Artificial Intelligence, vol- We presented a method that enables to formally guarantee ume 33, 3240–3247. that a prediction of a monotonic neural network will always Daniels, H.; and Velikova, M. 2010. Monotone and partially be in an area that preserves the safety of a system. This is monotone neural networks. IEEE Transactions on Neural achieved by the construction of the network, the utilization Networks 21(6): 906–917. of majoring points and the learning phase, which allows us Fischer, M.; Balunovic, M.; Drachsler-Cohen, D.; Gehr, T.; to free ourselves from a massive testing phase that is long Zhang, C.; and Vechev, M. 2019. DL2:- Training and Query- and costly while providing fewer guarantees. ing Neural Networks with Logic. In International Confer- Our work have limitations on functions that can be a ence on Machine Learning. safely approximate, but this is a first step toward a safe use of neural networks in critical applications. Nevertheless, this Gal, Y.; and Ghahramani, Z. 2016. Bayesian Convolutional can already be used in simple safety critical systems that Neural Networks with Bernoulli Approximate Variational verify our hypotheses. Future works will look on possibil- Inference. In 4th International Conference on Learning Rep- ity to leverage the utilization of the monotonic hypothesis. resentations (ICLR) workshop track. Another direction of improvement is to build smarter algo- Harvey, N.; Liaw, C.; and Mehrabian, A. 2017. Nearly-tight rithms that require less majoring points thanks to a better VC-dimension bounds for piecewise linear neural networks. adaptation to the structure of the function. In particular, this In Conference on Learning Theory, 1064–1068. should permit to apply the method to functions whose is in- Jakubovitz, D.; Giryes, R.; and Rodrigues, M. R. 2019. Gen- put space is of larger dimension, when they have the proper eralization error in deep learning. In Compressed Sensing structure. and Its Applications, 153–193. Springer. Jian, Z.-D.; Chang, H.-J.; Hsu, T.-s.; and Wang, D.-W. 2017. Acknowledgements Learning from Simulated World-Surrogates Construction This project received funding from the French ”Investing for with Deep Neural Network. In SIMULTECH, 83–92. the Future – PIA3” program within the Artificial and Natu- Julian, K. D.; Kochenderfer, M. J.; and Owen, M. P. 2019. ral Intelligence Toulouse Institute (ANITI) under the grant Deep Neural Network Compression for Aircraft Collision agreement ANR-19-PI3A-0004. The authors gratefully ac- Avoidance Systems. Journal of Guidance, Control, and Dy- knowledge the support of the DEEL project.2 namics 42(3): 598–608. ISSN 1533-3884. doi:10.2514/1. g003724. URL http://dx.doi.org/10.2514/1.G003724. References Katz, G.; Barrett, C.; Dill, D. L.; Julian, K.; and Kochender- Amos, B.; Xu, L.; and Kolter, J. Z. 2017. Input Convex fer, M. J. 2017. Reluplex: An efficient SMT solver for veri- Neural Networks. In Proceedings of the 34th International fying deep neural networks. In International Conference on Conference on Machine Learning - Volume 70, ICML’17, Computer Aided Verification, 97–117. Springer. 146–155. JMLR.org. Keren, G.; Cummins, N.; and Schuller, B. 2018. Calibrated Anthony, M.; and Bartlett, P. L. 1999. Neural Network prediction intervals for neural network regressors. IEEE Ac- Learning: Theoretical Foundations. Cambridge Univer- cess 6: 54033–54041. sity Press. ISBN 0 521 57353 X. URL http://www.stat. Lang, B. 2005. Monotonic Multi-layer Perceptron Networks berkeley.edu/∼bartlett/nnl/index.html. 404pp. ISBN 978- as Universal Approximators. In Duch, W.; Kacprzyk, J.; Oja, 0-521-57353-X. Reprinted 2001, 2002. Paperback edition E.; and Zadrożny, S., eds., Artificial Neural Networks: For- 2009; ISBN 978-0-521-11862-0. mal Models and Their Applications – ICANN 2005, 31–37. Bartlett, P. L.; Harvey, N.; Liaw, C.; and Mehrabian, A. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978- 2019. Nearly-tight VC-dimension and Pseudodimension 3-540-28756-8. Bounds for Piecewise Linear Neural Networks. Journal of Lathuilière, S.; Mesejo, P.; Alameda-Pineda, X.; and Ho- Machine Learning Research 20(63): 1–17. raud, R. 2019. A comprehensive analysis of deep regres- Bianchi, P.; and Jakubowicz, J. 2012. Convergence of a sion. IEEE transactions on pattern analysis and machine multi-agent projected stochastic gradient algorithm for non- intelligence . convex optimization. IEEE transactions on automatic con- Mirman, M.; Gehr, T.; and Vechev, M. 2018. Differ- trol 58(2): 391–405. entiable Abstract Interpretation for Provably Robust Neu- ral Networks. In Dy, J.; and Krause, A., eds., Pro- 2 https://www.deel.ai/ ceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learn- ing Research, 3578–3586. Stockholmsmässan, Stockholm Sweden: PMLR. URL http://proceedings.mlr.press/v80/ mirman18b.html. Nguyen, Q.; and Hein, M. 2017. The loss surface of deep and wide neural networks. In Proceedings of the 34th In- ternational Conference on Machine Learning-Volume 70, 2603–2612. JMLR. org. Pearce, T.; Brintrup, A.; Zaki, M.; and Neely, A. 2018. High-Quality Prediction Intervals for Deep Learning: A Distribution-Free, Ensembled Approach. In Proceedings of the 35th International Conference on Machine Learning, ICML, 4072–4081. Raghunathan, A.; Steinhardt, J.; and Liang, P. 2018. Certi- fied Defenses against Adversarial Examples. Sill, J. 1998. Monotonic Networks. In Jordan, M. I.; Kearns, M. J.; and Solla, S. A., eds., Advances in Neural Information Processing Systems 10, 661–667. MIT Press. URL http:// papers.nips.cc/paper/1358-monotonic-networks.pdf. Sudakov, O.; Koroteev, D.; Belozerov, B.; and Burnaev, E. 2019. Artificial Neural Network Surrogate Modeling of Oil Reservoir: a Case Study. In International Symposium on Neural Networks, 232–241. Springer. Tagasovska, N.; and Lopez-Paz, D. 2019. Single- Model Uncertainties for Deep Learning. arXiv preprint arXiv:1811.00908, To appear in NeurIPS . Yao, Q.; and Tong, H. 1996. Asymmetric least squares re- gression estimation: a nonparametric approach. Journal of nonparametric statistics 6(2-3): 273–292.