Mathematical optimization in deep learning

FINAL DEGREE PROJECT Mathematical Optimization in Deep Learning Presented by: Miren Jasone Ramírez Ayerbe Supervised by: DR. EMILIO CARRIZOSA PRIEGO DR. RAFAEL BLANQUERO BRAVO FACULTY OF MATHEMATICS Statistics and Operational Research Department Sevilla, June 2019 Contents Abstract 5 Resumen 7 1 Introduction 9 2 DNN topology 11 3 Training a DNN 15 3.1 The Weights and Bias Optimization Problem . . . . . . . . . . . . . . 15 3.1.1 Complexity of training a ReLU NN . . . . . . . . . . . . . . 16 3.1.2 Regression ........................... 17 3.1.3 Classification.......................... 19 3.2 Computational experiments . . . . . . . . . . . . . . . . . . . . . . . 20 3.2.1 Regression Problem . . . . . . . . . . . . . . . . . . . . . . 21 3.2.2 Classification Problem . . . . . . . . . . . . . . . . . . . . . 25 4 The inverse problem 29 4.1 A trained Deep Neural Network . . . . . . . . . . . . . . . . . . . . 29 4.2 Mixed-Integer Linear Formulation . . . . . . . . . . . . . . . . . . . 30 4.3 Boundtightening ............................ 31 4.4 A Non linear reformulation . . . . . . . . . . . . . . . . . . . . . . . 32 4.5 Computational Experiments . . . . . . . . . . . . . . . . . . . . . . 32 4.5.1 Feature visualization . . . . . . . . . . . . . . . . . . . . . . 33 4.5.2 Adversarial Examples . . . . . . . . . . . . . . . . . . . . . 34 Annex I. Training a DNN 39 Annex II. Applications of a trained DNN 41 Bibliography 43 3 Abstract Mathematical Optimization plays a pillar role in Machine Learning (ML) and Neural Networks (NN) are amongst the most popular and effective ML architectures and are the subject of a very intense investigation. They have also been proven immensely powerful at solving prediction tasks in areas such as speech recognition, image classification, robotics and quantum physics. In this work we present the problem of training a Deep Neural Network (DNN), specifically the continuous optimization problem arising in Feed-Forward Networks with Rectified Linear Unit (ReLU) activation. Then we will discuss the inverse problem, presenting a model for a trained DNN as a 0-1 Mixed Integer Linear Program (MILP). Some applications, such as feature visualization and the construction of adversarial examples will be outlined. Computational experiments are reported for both direct and inverse problem. The remainder of the text contains the AMPL codes used for solving the posed problems. 5 Resumen La optimización matemática juega un papel fundamental en el aprendizaje automático (AA), y las redes neuronales (NN) se encuentran entre las estructuras más populares y efectivas dentro de este campo. Por ello, son objecto de una intensa investigación. Además, han demostrado ser inmensamente potentes resolviendo tareas de predicción en áreas como reconocimiento automático del habla, clasificación de imágenes, robótica y física cuántica. En este trabajo, se presenta el problema de entrenar una red neuronal profunda (DNN), específicamente el problema de optimización continua que surge en las redes neuronales prealimentadas (FNN) con rectificador (ReLU) como función de activación. Posteriormente, se discutirá el problema inverso, presentaremos un modelo para una DNN que ya ha sido entrenada como un problema de programación lineal en enteros mixta. Describiremos algunas aplicaciones, como visualización de características y la construcción de ejemplos maliciosos. Se realizarán los experimentos computacionales para ambos problemas, el directo y el inverso. Los códigos de AMPL para los problemas planteados se encuentran al final del documento. 7 Chapter 1 Introduction Mathematical Optimization plays a pillar role in Machine Learning (ML). Indeed, learning from available data means that the parameters of a chosen system must be computed by solving to optimality a learning problem. Neural Networks (NN) are amongst the most popular and effective ML architectures and are the subject of a very intense investigation. Deep Learning, i.e. computational techniques developed for training Deep Neural Networks (DNN), started with the work of Hinton et al. (2006), which gave empirical evidence that, if DNNs are initialized properly, then one can find good solutions in a reasonable amount of runtime. Since then, Deep Learning has received immense attention, as it has proven really powerful at solving a number of predictive tasks arising in areas such as speech recognition, image classification, and robotics and control. Deep Neural Networks are also a very useful instrument in physic problems. For the most part, NN have been used for particle identification and classification and particletrack reconstruction [11] [2], but some scientists are working also on developing NN that can discover gravitational lenses, massive celestial objects that can distort light from distant galaxies behind them [17]. There is as well an emerging interdisciplinary research area at the intersection of quantum physics and ML, Quantum Machine Learning, whose development is very active nowadays [4]. We emphasize all these applications of Neural Networks in different areas, and, therefore, the importance of the training process and the formulation of a model that describes the computation performed by a Neural Network. Depending on the type of learning problem, we get different classes of optimization problems. We will focus on the class of continuous optimization problems arising in Feed-Forward Neural Networks (FNN). A FNN is a made up of layers of internal units (neurons), each of which computes an affine combination of the outputs of neurons in the previous layer, applies a non-linear operator, known as activation function, and outputs the value. A widely popular activation is the Rectified Linear Unit (ReLU) activation, whose output is the maximum between zero and the input value. It will be 9 16 3.1. The Weights and Bias Optimization Problem constant Rsuch that whenever kwk,kbk ≥ R, then E(w,b)> M. Hence, the levels set A=(w,b) : E(w,b)≤E(w0,b0)are all compact for every w0,b0and the function Eadmits a global minimum (w∗,b∗)such that E(w∗,b∗)≤E(w,b)for all (w,b). This property may not hold if the penalty term is removed, i.e., for λ= 0. One important question to ask is whether global optimization is needed or whether local optimization is enough to solve the problem. To answer this, first we will introduce some results about the complexity of the problem. 3.1.1 Complexity of training a ReLU NN Recently, some results about hardness for ReLU networks have been shown by [6]. The main results are: Theorem 3.1.1. It is NP-hard to solve the training for a two layer ReLU NN with two ReLU nodes in the first layer and one in the last one. Corollary 3.1.1. The training problem of a two layer ReLU NN with two nodes in the first layer and j in the last one is NP-hard, for all j≥1. Theorem 3.1.2. Under the assumption that the dimension of input d is a constant, there exists a poly(N) solution to the training problem of a ReLU NN with two nodes in the first layer and one in the second and last one, where N is the number of data points. Theorem 3.1.3. Given data points {xi, yi}i= 1 . . . N, then the training problem for a ReLU NN with N nodes in the first layer and one in the second and last one has a poly(N,d) radomized algorithm, where Nis the number of data points and dis the dimension of input. In the same line of research, [1] shows: Theorem 3.1.4. There exists an algorithm to find a global optimum of the minimization problem to train a two layer ReLU DNN in time O(2w(D)nwpoly(D, d, w)). Note that the running time is polynomial in the size data for fixed d, dimension of input, and fixed w, number of nodes. These results show that the running time of an algorithm to find the global minimum of a two layer ReLU DNN is exponential in the input dimension and the number of hidden nodes, and only if they are fixed the running time of the algorithm could be polynomial. We observe the complexity of training a ReLU NN even in the easiest network architecture (shallow networks with few neurons). Chapter 3. Training a DNN 17 However, it has been observed in practice that "most local minima yield similar performance from the generalization point of view. Furthermore, as asserted in [7], the probability of finding a bad local minimum, namely one with large training error, decreases quickly with the network size. Hence, for deep ReLU networks the effort of finding the global minimum may not be worthwhile." It has also been suggested by several authors that, because of overfitting phenomena, inaccurate weights minimization can be better than exact ones [15]. Assuming continuous differentiability of the function E, any gradient-based unconstrained method can be applied to the solution of the WBO problem (3.1). Considering previous results, we will solve problem (3.1) with local-search algorithms, such as gradient methods. These methods can guarantee convergence only to stationary points, but in practice it will probably be fully satisfactory from the generalization point of view. We will formulate the WBO problem for two different problems: classification and regression. 3.1.2 Regression Let us consider a feed-forward DNN with K+1 layers and ReLU activation. Given data points (x0 i, y0 i)∈Rm×R, i = 1 . . . n, we consider the problem of finding the weights that minimize the error function. In this case the error function is defined as: Ei(w,b) = kf(x0 i)−y0 ik2+λkwk2+λkbk2(3.2) where f(x0 i) = xK i, and the regularization term λ > 0is fixed. The optimization problem is: min n X i=1 (xK i−y0 i)2+λkwk2+λkbk2(3.3) s.t. xK i=ReLU(WK−1xK−1 i+bK−1) . . . x1 i=ReLU(W0x0 i+b0)      i= 1 . . . n (3.4) There are various ways of modelling the constraints of this problem. First we will study the basic scalar function: x=ReLU(wTy+b) 18 3.1. The Weights and Bias Optimization Problem One can reproduce a formulation for the ReLU as below. wTy+b=x−s xs ≤0 x≥0, s ≥0    (3.5) With this formulation, we separate the positive and negative part of the ReLU. When wTy+b≥0, s = 0 and x=wTy+b, while x= 0 when wTy+b < 0. For us to not work with a bilinear condition such as xs ≤0, one can rewrite the expression by introducing a binary activation variable z. This yields: z= 1 →x≤0 z= 0 →s≤0 z∈ {0,1}    (3.6) Using these new variables, we obtain the following WBO problem: min n X i=1 (xK i−y0 i)2+λkwk2+λkbk2(3.7) s.t. Wk−1xK−1 i=zK ixK i−sK i . . . W0x0 i=z0 ix0 i−s0 i      i= 1 . . . n (3.8) xk i≥0, sk i≥0 zk i∈ {0,1} if zk i= 1,then xk i≤0 if zk i= 0,then sk i≤0        ∀i= 1 . . . n ∀k= 1 . . . K (3.9) This reformulation may be useful in some cases, but introducing an integer variable while working with a non-linear objective function may not be the best idea, as a nonlinear integer optimization problem is a very complex computational problem. Another way to reformulate the ReLU function is using the hyperbolic approximation: max {t, 0} ≃ √t2+ε+t 2,for some small ε > 0(3.10) We obtain now a non-linear optimization problem without integer variables: min n X i=1 (xK i−y0 i)2+λkwk2+λkbk2(3.11) Chapter 3. Training a DNN 19 s.t. xK i=√(WK−1xK−1 i+bK−1)2++WK−1xK−1 i+bK−1 2 . . . x1 i=√(W0x0 i+b0)2++W0x0 i+b0 2        i= 1 . . . n (3.12) 3.1.3 Classification In this case, given data points x0 i∈Rq, i = 1 . . . n and a set of categories yi, yi= 1 . . . p,i= 1 . . . n, the problem consists in finding the weights and bias which maximize the probability of each observation being mapped to its right category. Instead of considering that the last layer consists in one single node whose value is the corresponding class, it will be a p-dimensional vector, whose maximum component will indicate to which category the data point belongs. An individual x0 jwould be classified correctly if (xK j)yj>(xK j)k,for all k={1. . . p}\{yj}, where Kindicates the output layer, and the sub-index refers to the component of the output vector. We assume a random classification rule, in which an individual x0will be assigned to class jwith probability proportional to e(xK)j,j= 1 . . . p, i.e., with probability e(xK)j Pp k=1 e(xK)k. Hence, the probability of correct classification of an individual x0in class yis e(xK)y Pp k=1 e(xK)k. To train the classification problem, we maximize the expected number of correctly classified individuals. Thus, the loss function for this problem is defined as: min − n X j=1 e(xK j)yj Pp k=1 e(xK j)k+λkwk2+λkbk2(3.13) where λ > 0is fixed. For the formulation we use the constraints (3.12) The final formulation is given by: min − n X j=1 e(xK j)yj Pp k=1 e(xK j)k+λkwk2+λkbk2(3.14) s.t. xK i=q(WK−1xK−1 i+bK−1)2++WK−1xK−1 i+bK−1 2 . . . x1 i=q(W0x0 i+b0)2++W0x0 i+b0 2          i= 1 . . . n (3.15) 20 3.2. Computational experiments Instead of maximizing the expected number of correctly classified individuals, we might minimize the number of misclassified points in the data set. To do this we introduce a binary variable ziwhich yields: zi= 1 if (xK i)yi≤(xK i)j, j ={1. . . p}\yj zi= 0 otherwise zi∈ {0,1}i= 1 . . . n    (3.16) This logical implication can be converted into inequalities using the bigM method. This yields (xK i)yj≤zi(xK i)j+M(1 −zi)j={1. . . p}\yi, i = 1 . . . n (3.17) where Mis a finite non-negative value long enough, so that, if z= 0, then the constraint would be not binding. The final formulation in this case is given by: min n X i=1 zi+λkwk2+λkbk2(3.18) s.t. (3.12),(3.17) (3.19) This alternative formulation might be used, but, as it has been commented on early, using binary variables and non-linear constraints is not the best idea. Hence, the first formulation would be used for our computational experiments. 3.2 Computational experiments In this chapter the WBO (3.1) is applied to a given set of data points. As it has been said, the network architecture will be considered fixed, but we will study multiple structures of the NN to see which one is best suited for our problem. As the optimization problem will be solved with local-search algorithms and in practice there will be more than one local minimum, a good way to ensure finding the solution is to apply the multi-start technique, namely, running the algorithm with different starting points. The regression and classification problem will be both addressed, and will be used to solve both problems the NEOS Server, an internet-based Chapter 3. Training a DNN 21 service for solving numerical optimization problems. The AMPL codes can be found in Annex I. The software MINOS, which is designed to solve continuous non linear programming problems, will be used to solve all the examples in this chapter. The running time used for each example will not be presented, as we are using NEOS Server, the software and computer used to solve each example would be different, hence the different running times would not be comparable. 3.2.1 Regression Problem We consider the problem of assessing the heating load requirement of a building, that is the energy efficiency, as a function of building parameters. The dataset, known in the literature as Energy efficiency, was created by Angeliki Xifara and was processed by Athanasios Tsanas [18]. It can be found in [19]. It compromises 750 samples of 12 different buildings, 400 of which will be used to train the network, and 350 to test it. It contains eight attributes (x1, x2, x3, x4, x5, x6, x7, x8) and, originally, two responses (y1, y2). For our experiment, we will use one of them, y1. Predicting the second response y2 would be analogue. The aim is to train our NN to be able to predict the response using the eight factors. These are specifically: •x1: relative compactness •x2: surface area •x3: wall area •x4: roof area •x5: overall height •x6: orientation •x7: glazing area •x8: glazing area distribution •y1: heating load Model (3.11)-(3.12) is applied to these data points. To perform the experiments, four different network architectures will be considered: •DNN1: 1 hidden layer with 3 neurons 22 3.2. Computational experiments •DNN2: 1 hidden layer with 10 neurons •DNN3: 2 hidden layers with 3 neurons each •DNN4: 2 hidden layers with 8 neurons each All DNNs involve an input layer with eight neurons and an output layer with one unit. As parameters, the values λ= 0.01 and = 10−3have been used. Results For each structure we will show the relative error for the training and testing set. The first structure that has been used is very simple. The results are shown in Figure 3.1. Figure 3.1: Performance on a 5-3-1 Neural Network Although the network structure used was very simple, the results obtained are quite satisfactory, as the mean relative error for the training and testing set is around 5 % and 10 % respectively. One thing that must be discussed is the presence of quite some outliers, whose relative error is quite big. We have performed some experiments to identify the records yielding such errors. To do this, we have considered a classification problem in which the class was 1 or 0 whether the relative error was above or below 20 %. A classification tree [14] was run for both data sets, the training and the testing one. The results shown in Figure 3.2 show us that, although it gives us exactly which combination of factors leads to a bigger error, it is not fully clarifying, as both trees do not even coincide for both tests. Chapter 3. Training a DNN 23 Figure 3.2: Classification tree for DNN1. Relative error above or below 20% If we add nodes to the hidden layer, the relative error for the training set is highly reduced, but for the testing one, the results are worse than for the last structure used. While the mean relative error is similar, we found in this case a lot more dispersion, and in general worse capacity of a good prediction. Looking at the results in Figure 3.3, it seems that the model obtained is overfitted, and thus, worse prediction results are achieved. Figure 3.3: Performance on a 8-10-1 Neural Network Maintaining the same number of nodes as DNN1, but adding an additional layer reduces the relative error for the testing data sets, and this result interests us much more, as it means that the prediction capacity of our network has increased. The relative error for the training set does not change and this could possibly mean that, as opposed to the latter case, the model obtained is not overfitted. 24 3.2. Computational experiments Figure 3.4: Performance on a 8-3-3-1 Neural Network In this model, there are some outliers as well. We have performed the same experiment as before to identify them, and using a classification tree we have obtained the combination of attributes that make our model unsuitable for those cases, see Figure 3.5. Although there are some characteristics common for some of them, the trees are all different, hence we can’t determine exactly what factors cause most errors in our model. However, one can observe that the Relative Compactness(X1) and specially the Glazing Area (X7) are the attributes that determine most the probability of having a bigger error. Figure 3.5: Classification tree for DNN3. Relative error above or below 20% At last we consider the largest DNN. For this one, we can clearly see an overfitted model, as shown in Figure 3.6. The error for the training set is the lowest, but for the testing set we obtain the worst results achieved at the moment. The mean relative error Chapter 3. Training a DNN 25 for this one increases to a value of 50 %, and it reaches as far as 140 %, which gives us an impractical model. Figure 3.6: Performance on a 8-8-8-1 Neural Network To sum up, for this regression problem, the best architecture network to use would be DNN3. The results in this case, are fully satisfactory, as we achieve a mean relative error for the testing set of the 7 %, with little variance. This brings to light the fact that a hidden layer can increase the network ability to compute and extract high-order statistics from the input. However, it must be considered that too many parameters tend to overfit the model, as it has been proven in the last case, where increasing the number of nodes excessively makes the network completely ineffective. 3.2.2 Classification Problem In this case we consider the problem of knowing if a specific breast cancer is benign or malignant. The dataset compromises 684 samples obtained from the University of Wisconsin Hospital. The dataset can be found in the UCI Machine Learning Datasets webpage [20]. Each sample contains 9 attributes (X1-X9) and its corresponding class (Y). These are: 1. X1: Clump Thickness: 1-10 2. X2: Uniformity of Cell Size: 1-10 3. X3: Uniformity of Cell Shape: 1-10 4. X4: Marginal Adhesion: 1-10 5. X5: Single Epithelial Cell Size: 1-10 32 4.4. A Non linear reformulation ˆ lk j= nk−1 X i=1 (−w−(k−1) ij lk−1 j−w+(k−1) ij uk−1 j)−bk−1 j(4.12) ˆuk j= nk−1 X i=1 (−w−(k−1) ij lk−1 j−w+(k−1) ij uk−1 j)−bk−1 j(4.13) To propagate the bounds we apply the ReLU activations to the them: ¯ lk j,¯uk j=hmax(0,˜ lk j),max(0,˜uk j)i(4.14) 4.4 A Non linear reformulation An alternative form to model indicator constraints, like ReLUs, is using Mixed Integer Non-linear Programming [3], [5]. Instead of using a linear formulation and the so-called big-M constraint, that can lead to weak continuous relaxations, we present in this section a possible non-linear, non-convex reformulation for the same model. A 0-1 MINLP formulation min K X k=0 nk X j=1 ck jxk j+ K X k=1 nk X j=1 γk jzk j(4.15) s.t. Pnk−1 i=1 wk−1 ij xk−1 i+bk−1 j=xk j−sk j xk j, sk j≥0 ¯zk j∈ {0,1} xk j(1 −¯zk j)≤0 sk j¯zk j≤0            k= 1 . . . K, j = 1 . . . nk(4.16) lk j≤xk j≤uk j ¯ lk j≤sk j≤¯uk jk= 1 . . . K, j = 1 . . . nk(4.17) 4.5 Computational Experiments We will use again the NEOS Server to solve the problems in this section. The AMPL codes can be found in Annex II. The software CPLEX, which is designed to solve mixed-integer linear programming (MILP), will be used to solve all the examples in this section. Chapter 4. The inverse problem 33 Just as we commented on Chapter 3, the running time used for each example will not be shown, as using the NEOS Server does not assure us to have running times hat are comparable. For this reason, the bounds tightening techniques will not be used in this computational experiments. As noted before, the model (4.4) - (4.6) is not suited for training, but we can use it to compute the best-possible input example according to some linear objective function, that will depend on the problem at hand. In this section we will apply our model to a feature visualization problem and we will build adversarial examples. 4.5.1 Feature visualization We consider the classification problem of knowing if a specific breast cancer is benign or malignant. We will use our 0-1 MILP model to find the input examples that maximize the activation xK jof each class. Here xK jdenotes de j-th node of the output layer. To solve this problem the objective function is simply: −xK j(4.18) where j= 1,2depending if one wants to find the input that maximizes the first class or the second one. We will use the trained DNN3 in Chapter 3. This DNN had 2 hidden layers with 3 neurons each, and it produced a test-set accuracy of 91.5 %. Its corresponding weights and bias were used to build our (4.4) - (4.6) model. Results We present in Figure 4.1 the input examples that maximize each class. max-activating input benign (Y1) (0,0,0,10,10,0,10,0,0) malignant (Y2) (10,0,0,0,0,10,0,0,10) Figure 4.1: Input examples that maximizes each class Knowing these results, one could analyse each input and conclude that those whose factors X4 (Marginal Adhesion), X5 (Single Epitheial Cell Size), and X7 (Bland Chromatin) are more prominent, could be classified with more probability as benign, while factors X1 (Clumb Thickness), X6 (Bare Nuclei), and X9 (Mitoses) identify clearly the malignant class. 34 4.5. Computational Experiments 4.5.2 Adversarial Examples In this case we will use our MILP model to simulate the role of a malicious attacker. We want to locate which minimal changes in the model are sufficient to trick the DNN and make a wrong classification. We will use again as illustration the breast cancer classification problem. We are given an input ˜x0that is classified correctly by our DNN as i(benign or malignant). We want to determine the minimum distance between ˜x0and a similar figure x0 that it is wrongly classified as j6=i. To model this situation we impose that in the last layer the activation of the required wrong class is at least 20 % larger than the other activation. In our MILP model (4.4)- (4.6) we just have to add the linear constraints: xK j≥1.2xK i, i, j = 1,2(4.19) In order to minimize the distance between x0and ˜x0in `1norm, we minimize the following objective function: n0 X j=1 |x0 j−˜x0 j|(4.20) In order to have a linear objective, the problem is reformulated as minimizing n0 X j=1 dj(4.21) where the variables djmust satisfy: −dj≤x0 j−˜x0 j≤dj, dj≥0j= 1 . . . n0(4.22) This linear constraint must be also added to model (4.4)-(4.6). We will use again the trained DNN3 in Chapter 3, which had 2 hidden layers with 3 neurons each and it produced a test-set accuracy of 91.5 %. Its corresponding weights and bias were used to build our model. Results Considering two inputs, corresponding to the two different classes, it is shown in Figure 4.2 the minimum changes in the original input that suffice to trick the DNN and therefore it would make a wrong output. One can see that the changes are not minimal, and that there are variables more relevant than others. It can be easily seen that the parameters that one must change in order to trick the DNN are the ones that where calculated in the last example, those who maximized Chapter 4. The inverse problem 35 original input adversarial example Pn0 jdj benign (2,1,1,1,2,1,3,1,1) (2,1,1,1,2,4,3,1,10) 12 malignant (6,10,10,10,8,10,7,10,7) (6,10,10,10,8,1,7,8,1) 17 Figure 4.2: Adversarial examples that trick the DNN their correspondent output. The results are therefore very logical and expected. We can also impose to our model other interesting constraints such as: maximum deviation for each attribute with respect ˜x0or maximum number of changed attributes in the input x0, as illustrated in what follows. First we impose that the maximum allowable deviation for each attribute is 4. We just add to our model that dj≤4, j = 1 . . . n0. The results obtained in this case are: original input adversarial example Pn0 jdj benign (2,1,1,1,2,1,3,1,1) (6,1,1,1,2,5,3,4,5) 15 malignant (6,10,10,10,8,10,7,10,7) (2,10,6,10,8,6,7,6,3) 20 Figure 4.3: Adversarial examples that trick the DNN, maximum deviation each attribute:4 We can see that, imposing this constraint, the changes in the input to trick the NN increase. This is definitely a good sign, as it confirms us the reliability of the network. In fact, if we impose that the maximum allowable change must be 3 or smaller, the optimization problem turns to be infeasible, i.e. there would not be any combination of changes that could trick our network. At last we add that the maximum number of modified attributes must be 2. For us to solve this we must introduce binary variables ri,i= 1 . . . n0. This yields ri= 1 if component iis modified ri= 0 otherwise ri∈ {0,1}    i= 1 . . . n0(4.23) Knowing that, if component jhas changed, then |x0 j−˜x0 j| ≥ 1, otherwise |x0 j− 36 4.5. Computational Experiments ˜x0 j|= 0, the following constraints must be add to our model to limit the number of changes: n0 X j=1 rj≤2(4.24) if ri= 1 then |x0 j−˜x0 j| ≥ 1 if ri= 0 then x0 j≤˜x0 j x0 j≥˜x0 j ri∈ {0,1}        i= 1 . . . n0(4.25) In order to have a linear constraint, another binary variable ti,i= 1 . . . n0is introduced: ti= 1 if ¯x0 i≥x0 i ti= 0 otherwise ti∈ {0,1}    i= 1 . . . n0(4.26) This new binary variable and a big value M, allow us to linearise the absolute value. The final new constraints added to our model are (4.24) and the following: x0 j≥˜x0 j(1 −rj) + rj(˜x0 j+ 1 −Mtj) x0 j≤˜x0 j(1 −rj) + rj(˜x0 j−1 + M(1 −tj))j= 1 . . . n0(4.27) where M is a constant big enough (in this case 10 is enough). Introducing all these factors, the new results are shown in Figure 4.4 original input adversarial example Pn0 jdj benign (2,1,1,1,2,1,3,1,1) (2,1,1,1,2,4,3,1,10) 12 malignant (6,10,10,10,8,10,7,10,7) infeasible - Figure 4.4: Adversarial examples that trick the DNN, maximum number of changes: 2 Imposing the maximum number of changes in only 2 nodes, the result in the first case considered (˜x0benign) does not change, as the optimal solution without constraints had only changed the value of two nodes. But, in the second case, the problem turns out to be infeasible. In fact the minimum number of nodes needed to change in order to trick the DNN is 3. Examining the results in general, one can conclude that it is generally easier to trick the network into misclassifying a benign case as malignant than the other way. Chapter 4. The inverse problem 37 In all this examples, the running time is quite short and one obtains the optimal solution quite easily. This is because all our variables are bounded. (0≤Xi≤10), and we do not use an extremely large value of M, that could probably give us quite a few problems. 38 4.5. Computational Experiments Annex I. Training a DNN In this chapter we include the AMPL codes used in Chapter 3. Regression problem param n; #input dim param epsi; #epsilon param K; #layers param lambda; param nk{i in 0..K}; #number of nodes of each layer param x0{i in 1..n, j in 1..nk[0]}; #input param y{i in 1..n}; #output var b{k in 0..K-1, j in 1..nk[k+1]}; #bias var W{k in 0..K-1, i in 1..nk[k+1], j in 1..nk[k]}; #weights var x{i in 1..n, k in 1..K, j in 1..nk[k]}; param erel{i in 1..n}; minimize error: sum{i in 1..n} sum{j in 1..nk[K]} (x[i,K,j] - y[i])^2 + lambda*(sum{k in 0..K-1} sum{i in 1..nk[k+1]} sum{j in 1..nk[k]} W[k,i,j]^2)+lambda*(sum{k in 0..K-1} sum{j in 1..nk[k+1]} b[k,j]^2); #constraints: subject to res{i in 1..n, k in 2..K, j in 1..nk[k]}: x[i,k,j]=0.5*(sqrt((sum{l in 1..nk[k-1]} W[k-1,j,l]*x[i,k-1,l]+ b[k-1,j])^2+epsi)+sum{l in 1..nk[k-1]}W[k-1,j,l]*x[i,k-1,l]+ b[k-1,j]); 39 40 subject to res0{i in 1..n, j in 1..nk[1]}: x[i,1,j]=0.5*(sqrt((sum{l in 1..nk[0]} W[0,j,l]*x0[i,l]+b[0,j])^2+ epsi) + sum{l in 1..nk[0]} W[0,j,l]*x0[i,l]+b[0,j]); Classification Problem param n; #input dim param epsi; #epsilon param K; #layers param nk{i in 0..K}; #nodes in each layer param lambda; #lamda param clase{i in 1..n}; param err{i in 1..n}; param num; param x0{i in 1..n, j in 1..nk[0]}; #input param y{i in 1..n}; #output var b{k in 0..K-1, j in 1..nk[k+1]}; #bias var W{k in 0..K-1, i in 1..nk[k+1], j in 1..nk[k]}; #weights var x{i in 1..n, k in 1..K, j in 1..nk[k]}; minimize error: -sum{i in 1..n} exp(x[i,K,y[i]])/(sum{j in 1..nk[K]} exp(x[i,K,j])) + lambda*(sum{k in 0..K-1} sum{i in 1..nk[k+1]} sum{j in 1..nk[k]} W[k,i,j]^2)+lambda*(sum{k in 0..K-1}sum{j in 1..nk[k+1]} b[k,j]^2); #constraints: subject to res{i in 1..n, k in 2..K, j in 1..nk[k]}: x[i,k,j]=0.5*(sqrt((sum{l in 1..nk[k-1]} W[k-1,j,l]*x[i,k-1,l]+ b[k-1,j])^2+epsi)+sum{l in 1..nk[k-1]} W[k-1,j,l]*x[i,k-1,l]+ b[k-1,j]); subject to res0{i in 1..n, j in 1..nk[1]}: x[i,1,j]=0.5*(sqrt((sum{l in 1..nk[0]} W[0,j,l]*x0[i,l]+b[0,j])^2 +epsi) + sum{l in 1..nk[0]} W[0,j,l]*x0[i,l]+b[0,j]); Annex II. Applications of a trained DNN In this chapter we include the AMPL codes used in Chapter 4. Feature visualization param K; #layers param nk{i in 0..K}; param W{k in 0..K-1, i in 1..nk[k+1], j in 1..nk[k]}; #weights param b{k in 0..K-1, j in 1..nk[k+1]}; #bias var x{k in 0..K, j in 1..nk[k]} >=0; var s{k in 1..K, j in 1..nk[k]} >=0; var z{k in 1..K, j in 1..nk[k]} binary; var t>=1e-2; param M1; param M2; minimize objective: -x[K,2]; #- sum{k in 0..K} sum{j in 1..nk[k]} x[k,j] ; #constraints: subject to res1{k in 1..K, j in 1..nk[k]}: x[k,j]-s[k,j]=sum{i in 1..nk[k-1]} W[k-1,j,i]*x[k-1,i]+b[k-1,j]; subject to clas1: x[K,1]+t-x[K,2]=0; subject to m1{k in 1..K, j in 1..nk[k]}: 41