The loss of a few neurons in a brain rarely results in any visible loss of function. However, the insight into what “few” means in this context is unclear. How many random neuron failures will it take to lead to a visible loss of function? In this paper, we address the fundamental question of the impact of the crash of a random subset of neurons on the overall computation of a neural network and the error in the output it produces. We study fault tolerance of neural networks subject to small random neuron/weight crash failures in a probabilistic setting. We give provable guarantees on the robustness of the network to these crashes. Our main contribution is a bound on the error in the output of a network under small random Bernoulli crashes proved by using a Taylor expansion in the continuous limit, where close-by neurons at a layer are similar. The failure mode we adopt in our model is characteristic of neuromorphic hardware, a promising technology to speed up artificial neural networks, as well as of biological networks. We show that our theoretical bounds can be used to compare the fault tolerance of different architectures and to design a regularizer improving the fault tolerance of a given architecture. We design an algorithm achieving fault tolerance using a reasonable number of neurons. In addition to the theoretical proof, we also provide experimental validation of our results and suggest a connection to the generalization capacity problem. Understanding the inner working of artificial neural networks (NNs) is currently one of the most pressing questions (20) in learning theory. As of now, neural networks are the backbone of the most successful machine learning solutions (37; 18) . They are deployed in safety-critical tasks in which there is little room for mistakes (10; 40) . Nevertheless, such issues are regularly reported since attention was brought to the NNs vulnerabilities over the past few years (37; 5; 24; 8) . Fault tolerance as a part of theoretical NNs research. Understanding complex systems requires understanding how they can tolerate failures of their components. This has been a particularly fruitful method in systems biology, where the mapping of the full network of metabolite molecules is a computationally quixotic venture. Instead of fully mapping the network, biologists improved their understanding of biological networks by studying the effect of deleting some of their components, one or a few perturbations at a time (7; 12) . Biological systems in general are found to be fault tolerant (28) , which is thus an important criterion for biological plausibility of mathematical models. Neuromorphic hardware (NH). Current Machine Learning systems are bottlenecked by the underlying computational power (1) . One significant improvement over the now prevailing CPU/GPUs is neuromorphic hardware. In this paradigm of computation, each neuron is a physical entity (9) , and the forward pass is done (theoretically) at the speed of light. However, components of such hardware are small and unreliable, leading to small random perturbations of the weights of the model (41) . Thus, robustness to weight faults is an overlooked concrete Artificial Intelligence (AI) safety problem (2) . Since we ground the assumptions of our model in the properties of NH and of biological networks, our fundamental theoretical results can be directly applied in these computing paradigms. Research on NN fault tolerance. In the 2000s, the fault tolerance of NNs was a major motivation for studying them (14; 16; 4) . In the 1990s, the exploration of microscopic failures was fueled by the hopes of developing neuromorphic hardware (NH) (22; 6; 34) . Taylor expansion was one of the tools used for the study of fault tolerance (13; 26) . Another line of research proposes sufficient conditions for robustness (33) . However, most of these studies are either empirical or are limited to simple architectures (41) . In addition, those studies address the worst case (5) , which is known to be more severe than a random perturbation. Recently, fault tolerance was studied experimentally as well. DeepMind proposes to focus on neuron removal (25) to understand NNs. NVIDIA (21) studies error propagation caused by micro-failures in hardware (3) . In addition, mathematically similar problems are raised in the study of generalization (29; 30) and robustness (42) . The quest for guarantees. Existing NN approaches do not guarantee fault tolerance: they only provide heuristics and evaluate them experimentally. Theoretical papers, in turn, focus on the worst case and not on errors in a probabilistic sense. It is known that there exists a set of small worstcase perturbations, adversarial examples (5), leading to pessimistic bounds not suitable for the average case of random failures, which is the most realistic case for hardware faults. Other branch of theoretical research studies robustness and arrives at error bounds which, unfortunately, scale exponentially with the depth of the network (29) . We define the goal of this paper to guarantee that the probability of loss exceeding a threshold is lower than a pre-determined small value. This condition is sensible. For example, self-driving cars are deemed to be safe once their probability of a crash is several orders of magnitude less than of human drivers (40; 15; 36) . In addition, current fault tolerant architectures use mean as the aggregation of copies of networks to achieve redundancy. This is known to require exponentially more redundancy compared to the median approach and, thus, hardware cost. In order to apply this powerful technique and reduce costs, certain conditions need to be satisfied which we will evaluate for neural networks. Contributions. Our main contribution is a theoretical bound on the error in the output of an NN in the case of random neuron crashes obtained in the continuous limit, where close-by neurons compute similar functions. We show that, while the general problem of fault tolerance is NP-hard, realistic assumptions with regard to neuromorphic hardware, and a probabilistic approach to the problem, allow us to apply a Taylor expansion for the vast majority of the cases, as the weight perturbation is small with high probability. In order for the Taylor expansion to work, we assume that a network is smooth enough, introducing the continuous limit (39) to prove the properties of NNs: it requires neighboring neurons at each layer to be similar. This makes the moments of the error linear-time computable. To our knowledge, the tightness of the bounds we obtain is a novel result. In turn, the bound allows us to build an algorithm that enhances fault tolerance of neural networks. Our algorithm uses median aggregation which results in only a logarithmic extra cost -a drastic improvement on the initial NP-hardness of the problem. Finally, we show how to apply the bounds to specific architectures and evaluate them experimentally on real-world networks, notably the widely used VGG (38) . Outline. In Sections 2-4, we set the formalism, then state our bounds. In Section 5, we present applications of our bounds on characterizing the fault tolerance of different architectures. In Section 6 we present our algorithm for certifying fault tolerance. In Section 7, we present our experimental evaluation. Finally, in Section 8, we discuss the consequences of our findings. Full proofs are available in the supplementary material. Code is provided at the anonymized repo github.com/iclr-2020-fault-tolerance/code. We abbreviate Assumption 1 → A1, Proposition 1 → P1, Theorem 1 → T1, Definition 1 → D1. Fault tolerance is an important overlooked concrete AI safety issue (2) . This paper describes a probabilistic fault tolerance framework for NNs that allows to get around the NP-hardness of the problem. Since the crash probability in neuromorphic hardware is low, we can simplify the problem to allow for a polynomial computation time. We use the tail bounds to motivate the assumption that the weight perturbation is small. This allows us to use a Taylor expansion to compute the error. To bound the remainder, we require sufficient smoothness of the network, for which we use the continuous limit: nearby neurons compute similar things. After we transform the expansion into a tail bound to give a bound on the loss of the network. This gives a probabilistic guarantee of fault tolerance. Using the framework, we are able to guarantee sufficient fault tolerance of a neural network given parameters of the crash distribution. We then analyze the obtained expressions to compare fault tolerance between architectures and optimize for fault tolerance of one architecture. We test our findings experimentally on small networks (MNIST) as well as on larger ones (VGG-16, MobileNet). Using our framework, one is able to deploy safer networks into neuromorphic hardware. Mathematically, the problem that we consider is connected to the problem of generalization (29; 27) since the latter also considers the expected loss change under a small random perturbation , except that these papers consider Gaussian noise and we consider Bernoulli noise. Evidence (32) , however, shows that sometimes networks that generalize well are not necessarily fault-tolerant. Since the tools we develop for the study of fault tolerance could as well be applied in the context of generalization, they could be used to clarify this matter. 12 Variance for P2 is derived in the supplementary material are formal statements of the results referred to in the main paper, they are in the same section as the reference. 4 We abbreviate Assumption 1 → A1, Proposition 1 → P1, Theorem 1 → T1, Definition 1 → D1.
We give a bound for NNs on the output error in case of random weight failures using a Taylor expansion in the continuous limit where nearby neurons are similar This paper considers the problem of dropping neurons from a neural network, showing that if the goal is to become robust to randomly dropped neurons during evaluation, then it is sufficient to just train with dropout. This contribution studies the impact of deletions of random neurons on prediction accuracy of trained architecture, with the application to failure analysis and the specific context of neuromorphic hardware.