In this paper we study the problem of predictability in partially observable discrete event systems, i.e., the question whether an observer can predict the occurrence of a fault. We extend the definition of predictability to consider the time interval where the fault will occur: the @math -predictability does not only specify that the fault will be predicted before it occurs, but also that the predictor will be able to predict that its occurrence will occur in @math to @math observations from now. We also provide a quadratic algorithm that decides predictability of the system.
Brand 'an Briones and Madalinski presented the notions of @math -predictability and @math -predictability @cite_15 . @math -predictability is similar to our definition of @math -predictability meaning that the fault is predicted at least @math observations before the fault occurs. @math -predictability is the equivalent of our property of @math -predictability, meaning that it is possible to predict the fault occurrence before it occurs but when at most @math observations are still possible before the fault (in other words, the fault prediction is not too early).
@cite_15
2329723054
A discrete event system that is predictable can anticipate faults and act accordingly. However, bare predictability (as found in the literature) has some drawbacks. One does not know exactly when a fault occurs (it could be immediately or long after it is predicted). We propose lower and upper bound refinements of predictability, called (lb; ub)-predictability. A lower bound guarantees a fault to occur after certain execution steps, whereas an upper bound guarantees a fault to occur, in the future, but before some steps. This information can be exploited by the system to adopt the best contingency plan. We formally define the notions of lb-predictability and ub-predictability, present a decision algorithm to verify it on arbitrary systems, and illustrate them with examples. Most classifiers operate by selecting the maximum of an estimate of the conditional distribution @math where @math stands for the features of the instance to be classified and @math denotes its label. This often results in a hubristic bias : overconfidence in the assignment of a definite label. Usually, the observations are concentrated on a small volume but the classifier provides definite predictions for the entire space. We propose constructing conformal prediction sets which contain a set of labels rather than a single label. These conformal prediction sets contain the true label with probability @math . Our construction is based on @math rather than @math which results in a classifier that is very cautious: it outputs the null set --- meaning "I don't know" --- when the object does not resemble the training examples. An important property of our approach is that adversarial attacks are likely to be predicted as the null set or would also include the true label. We demonstrate the performance on the ImageNet ILSVRC dataset and the CelebA and IMDB-Wiki facial datasets using high dimensional features obtained from state of the art convolutional neural networks. We study fault-tolerant distributed optimization of a sum of convex (cost) functions with real-valued scalar input output in the presence of crash faults or Byzantine faults. In particular, the goal is to optimize a global cost function @math , where @math is the collection of agents, and @math is agent @math 's local cost function, which is initially known only to agent @math . Since the above global cost function cannot be optimized exactly in presence of crash faults or Byzantine faults, we define two weaker versions of the problem for crash faults and Byzantine faults, respectively. When some agents may crash, the goal for the weaker problem is to generate an output that is an optimum of a function formed as @math where @math is the set of non-faulty agents, @math is the set of faulty agents (crashed agents), @math for each @math and @math is a normalization constant such that @math . We present an iterative algorithm in which each agent only needs to perform local computation, and send one message per iteration. When some agents may be Byzantine, the system cannot take full advantage of the data kept by non-faulty agents. The goal for the associated weaker problem is to generate an output that is an optimum of a function formed as @math such that @math for each @math and @math . We present an iterative algorithm, where only local computation is needed and only one message per agent is sent in each iteration, that ensures that at least @math agents have weights ( @math 's) that are lower bounded by @math . A natural requirement of many distributed structures is fault-tolerance: after some failures, whatever remains from the structure should still be effective for whatever remains from the network. In this paper we examine spanners of general graphs that are tolerant to vertex failures, and significantly improve their dependence on the number of faults @math , for all stretch bounds. For stretch @math we design a simple transformation that converts every @math -spanner construction with at most @math edges into an @math -fault-tolerant @math -spanner construction with at most @math edges. Applying this to standard greedy spanner constructions gives @math -fault tolerant @math -spanners with @math edges. The previous construction by Chechik, Langberg, Peleg, and Roddity [STOC 2009] depends similarly on @math but exponentially on @math (approximately like @math ). For the case @math and unit-length edges, an @math -approximation algorithm is known from recent work of Dinitz and Krauthgamer [arXiv 2010], where several spanner results are obtained using a common approach of rounding a natural flow-based linear programming relaxation. Here we use a different (stronger) LP relaxation and improve the approximation ratio to @math , which is, notably, independent of the number of faults @math . We further strengthen this bound in terms of the maximum degree by using the Local Lemma. Finally, we show that most of our constructions are inherently local by designing equivalent distributed algorithms in the LOCAL model of distributed computation. This paper studies fault-tolerant algorithms for the problem of gathering @math autonomous mobile robots. A gathering algorithm, executed independently by each robot, must ensure that all robots are gathered at one point within finite time. In a failure-prone system, a gathering algorithm is required to successfully gather the nonfaulty robots, independently of the behavior of the faulty ones. Both crash and Byzantine faults are considered. It is first observed that most existing algorithms fail to operate correctly in a setting allowing crash failures. Subsequently, an algorithm tolerant against one crash-faulty robot in a system of three or more robots is presented. It is then observed that all known algorithms fail to operate correctly in a system prone to Byzantine faults, even in the presence of a single fault. Moreover, it is shown that in an asynchronous environment it is impossible to perform a successful gathering in a @math -robot system, even if at most one of them might fail in a Byzantine manner. Thus, the problem is studied in a fully synchronous system. An algorithm is provided in this model for gathering @math robots with at most a single faulty robot, and a more general gathering algorithm is given in an @math -robot system with up to @math faults, where @math . The resources allocated for software quality assurance and improvement have not increased with the ever-increasing need for better software quality. A targeted software quality inspection can detect faulty modules and reduce the number of faults occurring during operations. We present a software fault prediction modeling approach with case-based reasoning (CBR), a part of the computational intelligence field focusing on automated reasoning processes. A CBR system functions as a software fault prediction model by quantifying, for a module under development, the expected number of faults based on similar modules that were previously developed. Such a system is composed of a similarity function, the number of nearest neighbor cases used for fault prediction, and a solution algorithm. The selection of a particular similarity function and solution algorithm may affect the performance accuracy of a CBR-based software fault prediction system. This paper presents an empirical study investigating the effects of using three different similarity functions and two different solution algorithms on the prediction accuracy of our CBR system. The influence of varying the number of nearest neighbor cases on the performance accuracy is also explored. Moreover, the benefits of using metric-selection procedures for our CBR system is also evaluated. Case studies of a large legacy telecommunications system are used for our analysis. It is observed that the CBR system using the Mahalanobis distance similarity function and the inverse distance weighted solution algorithm yielded the best fault prediction. In addition, the CBR models have better performance than models based on multiple linear regression. Analyzing, understanding and predicting failure is of paramount importance to achieve effective fault management. While various fault prediction methods have been studied in the past, many of them are not practical for use in real systems. In particular, they fail to address two crucial issues: one is to provide location information (i.e., the components where the failure is expected to occur on) and the other is to provide sufficient lead time (i.e., the time interval preceding the time of failure occurrence). In this paper, we first refine the widely-used metrics for evaluating prediction accuracy by including location as well as lead time. We, then, present a practical failure prediction mechanism for IBM Blue Gene systems. A Genetic Algorithm based method is exploited, which takes into consideration the location and the lead time for failure prediction. We demonstrate the effectiveness of this mechanism by means of real failure logs and job logs collected from the IBM Blue Gene P system at Argonne National Laboratory. Our experiments show that the presented method can significantly improve fault management (e.g., to reduce service unit loss by up to 52.4 ) by incorporating location and lead time information in the prediction. We introduce the framework of blind regression motivated by matrix completion for recommendation systems: given @math users, @math movies, and a subset of user-movie ratings, the goal is to predict the unobserved user-movie ratings given the data, i.e., to complete the partially observed matrix. Following the framework of non-parametric statistics, we posit that user @math and movie @math have features @math and @math respectively, and their corresponding rating @math is a noisy measurement of @math for some unknown function @math . In contrast with classical regression, the features @math are not observed, making it challenging to apply standard regression methods to predict the unobserved ratings. Inspired by the classical Taylor's expansion for differentiable functions, we provide a prediction algorithm that is consistent for all Lipschitz functions. In fact, the analysis through our framework naturally leads to a variant of collaborative filtering, shedding insight into the widespread success of collaborative filtering in practice. Assuming each entry is sampled independently with probability at least @math with @math , we prove that the expected fraction of our estimates with error greater than @math is less than @math plus a polynomially decaying term, where @math is the variance of the additive entry-wise noise term. Experiments with the MovieLens and Netflix datasets suggest that our algorithm provides principled improvements over basic collaborative filtering and is competitive with matrix factorization methods. Suppose we are given a time series or a signal @math for @math . We consider the problem of predicting the signal in the interval @math based on a knowledge of its history and nothing more. We ask the following question: what is the largest value of @math for which a prediction can be made? We show that the answer to this question is contained in a fundamental result of information theory due to Wyner, Ziv, Ornstein, and Weiss. In particular, for the class of chaotic signals, the upper bound is @math in the limit @math , with @math being entropy in a sense that is explained in the text. If @math is small for @math , where @math is of the order of a characteristic time scale, the pattern of events leading up to @math is similar to the pattern of events leading up to @math . It is reasonable to expect @math to be a good predictor of @math . All existing methods for prediction use this idea... The purpose of this paper is the detection of salient areas in natural video by using the new deep learning techniques. Salient patches in video frames are predicted first. Then the predicted visual fixation maps are built upon them. We design the deep architecture on the basis of CaffeNet implemented with Caffe toolkit. We show that changing the way of data selection for optimisation of network parameters, we can save computation cost up to @math times. We extend deep learning approaches for saliency prediction in still images with RGB values to specificity of video using the sensitivity of the human visual system to residual motion. Furthermore, we complete primary colour pixel values by contrast features proposed in classical visual attention prediction models. The experiments are conducted on two publicly available datasets. The first is IRCCYN video database containing @math videos with an overall amount of @math frames and eye fixations of @math subjects. The second one is HOLLYWOOD2 provided @math movie clips with the eye fixations of @math subjects. On IRCYYN dataset, the accuracy obtained is of @math . On HOLLYWOOD2 dataset, results in prediction of saliency of patches show the improvement up to @math with regard to RGB use only. The resulting accuracy of @math is obtained. The AUC metric in comparison of predicted saliency maps with visual fixation maps shows the increase up to @math on a sample of video clips from this dataset. Background: The accurate prediction of where faults are likely to occur in code can help direct test effort, reduce costs, and improve the quality of software. Objective: We investigate how the context of models, the independent variables used, and the modeling techniques applied influence the performance of fault prediction models. Method: We used a systematic literature review to identify 208 fault prediction studies published from January 2000 to December 2010. We synthesize the quantitative and qualitative results of 36 studies which report sufficient contextual and methodological information according to the criteria we develop and apply. Results: The models that perform well tend to be based on simple modeling techniques such as Naive Bayes or Logistic Regression. Combinations of independent variables have been used by models that perform well. Feature selection has been applied to these combinations when models are performing particularly well. Conclusion: The methodology used to build models seems to be influential to predictive performance. Although there are a set of fault prediction studies in which confidence is possible, more studies are needed that use a reliable methodology and which report their context, methodology, and performance comprehensively. To facilitate proactive fault management in large-scale systems such as IBM Blue Gene P, online failure prediction is of paramount importance. While many techniques have been presented for online failure prediction, questions arise regarding two commonly used approaches: period-based and event-driven. Which one has better accuracy? What is the best observation window (i.e., the time interval used to collect evidence before making a prediction)? How does the lead time (i.e., the time interval from the prediction to the failure occurrence) impact prediction arruracy? To answer these questions, we analyze and compare period-based and event-driven prediction approaches via a Bayesian prediction model. We evaluate these prediction approaches, under a variety of testing parameters, by means of RAS logs collected from a production supercomputer at Argonne National Laboratory. Experimental results show that the period-based Bayesian model and the event-driven Bayesian model can achieve up to 65.0 and 83.8 prediction accuracy, respectively. Furthermore, our sensitivity study indicates that the event-driven approach seems more suitable for proactive fault management in large-scale systems like Blue Gene P. This paper tackles two related questions at the heart of machine learning; how can we predict if a minimum will generalize to the test set, and why does stochastic gradient descent find minima that generalize well? Our work is inspired by (2017), who showed deep networks can easily memorize randomly labeled training data, despite generalizing well when shown real labels of the same inputs. We show here that the same phenomenon occurs in small linear models. These observations are explained by evaluating the Bayesian evidence, which penalizes sharp minima but is invariant to model parameterization. We also explore the "generalization gap" between small and large batch training, identifying an optimum batch size which maximizes the test set accuracy. Interpreting stochastic gradient descent as a stochastic differential equation, we identify a "noise scale" @math , where @math is the learning rate, @math training set size and @math batch size. Consequently the optimum batch size is proportional to the learning rate and the training set size, @math . We verify these predictions empirically. We engineer an algorithm to solve the approximate dictionary matching problem. Given a list of words @math , maximum distance @math fixed at preprocessing time and a query word @math , we would like to retrieve all words from @math that can be transformed into @math with @math or less edit operations. We present data structures that support fault tolerant queries by generating an index. On top of that, we present a generalization of the method that eases memory consumption and preprocessing time significantly. At the same time, running times of queries are virtually unaffected. We are able to match in lists of hundreds of thousands of words and beyond within microseconds for reasonable distances. We define the relevant information in a signal @math as being the information that this signal provides about another signal @math . Examples include the information that face images provide about the names of the people portrayed, or the information that speech sounds provide about the words spoken. Understanding the signal @math requires more than just predicting @math , it also requires specifying which features of @math play a role in the prediction. We formalize this problem as that of finding a short code for @math that preserves the maximum information about @math . That is, we squeeze the information that @math provides about @math through a bottleneck' formed by a limited set of codewords @math . This constrained optimization problem can be seen as a generalization of rate distortion theory in which the distortion measure @math emerges from the joint statistics of @math and @math . This approach yields an exact set of self consistent equations for the coding rules @math and @math . Solutions to these equations can be found by a convergent re-estimation method that generalizes the Blahut-Arimoto algorithm. Our variational principle provides a surprisingly rich framework for discussing a variety of problems in signal processing and learning, as will be described in detail elsewhere. The knowledge about the software metrics which serve as defect indicators is vital for the efficient allocation of resources for quality assurance. It is the process metrics, although sometimes difficult to collect, which have recently become popular with regard to defect prediction. However, in order to identify rightly the process metrics which are actually worth collecting, we need the evidence validating their ability to improve the product metric-based defect prediction models. This paper presents an empirical evaluation in which several process metrics were investigated in order to identify the ones which significantly improve the defect prediction models based on product metrics. Data from a wide range of software projects (both, industrial and open source) were collected. The predictions of the models that use only product metrics (simple models) were compared with the predictions of the models which used product metrics, as well as one of the process metrics under scrutiny (advanced models). To decide whether the improvements were significant or not, statistical tests were performed and effect sizes were calculated. The advanced defect prediction models trained on a data set containing product metrics and additionally Number of Distinct Committers (NDC) were significantly better than the simple models without NDC, while the effect size was medium and the probability of superiority (PS) of the advanced models over simple ones was high ( @math p = . 016 , @math r = - . 29 , @math PS = . 76 ), which is a substantial finding useful in defect prediction. A similar result with slightly smaller PS was achieved by the advanced models trained on a data set containing product metrics and additionally all of the investigated process metrics ( @math p = . 038 , @math r = - . 29 , @math PS = . 68 ). The advanced models trained on a data set containing product metrics and additionally Number of Modified Lines (NML) were significantly better than the simple models without NML, but the effect size was small ( @math p = . 038 , @math r = . 06 ). Hence, it is reasonable to recommend the NDC process metric in building the defect prediction models. Given @math noisy samples with @math dimensions, where @math , we show that the multi-step thresholding procedure based on the Lasso -- we call it the Thresholded Lasso , can accurately estimate a sparse vector @math in a linear model @math , where @math is a design matrix normalized to have column @math norm @math , and @math . We show that under the restricted eigenvalue (RE) condition (Bickel-Ritov-Tsybakov 09), it is possible to achieve the @math loss within a logarithmic factor of the ideal mean square error one would achieve with an oracle while selecting a sufficiently sparse model -- hence achieving sparse oracle inequalities ; the oracle would supply perfect information about which coordinates are non-zero and which are above the noise level. In some sense, the Thresholded Lasso recovers the choices that would have been made by the @math penalized least squares estimators, in that it selects a sufficiently sparse model without sacrificing the accuracy in estimating @math and in predicting @math . We also show for the Gauss-Dantzig selector (Cand e s-Tao 07), if @math obeys a uniform uncertainty principle and if the true parameter is sufficiently sparse, one will achieve the sparse oracle inequalities as above, while allowing at most @math irrelevant variables in the model in the worst case, where @math is the smallest integer such that for @math , @math . Our simulation results on the Thresholded Lasso match our theoretical analysis excellently. Recent studies have revealed the vulnerability of deep neural networks - A small adversarial perturbation that is imperceptible to human can easily make a well-trained deep neural network mis-classify. This makes it unsafe to apply neural networks in security-critical applications. In this paper, we propose a new defensive algorithm called Random Self-Ensemble (RSE) by combining two important concepts: @math and @math . To protect a targeted model, RSE adds random noise layers to the neural network to prevent from state-of-the-art gradient-based attacks, and ensembles the prediction over random noises to stabilize the performance. We show that our algorithm is equivalent to ensemble an infinite number of noisy models @math without any additional memory overhead, and the proposed training procedure based on noisy stochastic gradient descent can ensure the ensemble model has good predictive capability. Our algorithm significantly outperforms previous defense techniques on real datasets. For instance, on CIFAR-10 with VGG network (which has @math accuracy without any attack), under the state-of-the-art C&W attack within a certain distortion tolerance, the accuracy of unprotected model drops to less than @math , the best previous defense technique has @math accuracy, while our method still has @math prediction accuracy under the same level of attack. Finally, our method is simple and easy to integrate into any neural network. The planted partition model (also known as the stochastic blockmodel) is a classical cluster-exhibiting random graph model that has been extensively studied in statistics, physics, and computer science. In its simplest form, the planted partition model is a model for random graphs on @math nodes with two equal-sized clusters, with an between-class edge probability of @math and a within-class edge probability of @math . Although most of the literature on this model has focused on the case of increasing degrees (ie. @math as @math ), the sparse case @math is interesting both from a mathematical and an applied point of view. A striking conjecture of Decelle, Krzkala, Moore and Zdeborov 'a based on deep, non-rigorous ideas from statistical physics gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if @math and @math , then conjectured that it is possible to cluster in a way correlated with the true partition if @math , and impossible if @math for some sufficiently large @math . We prove half of their prediction, showing that it is indeed impossible to cluster if @math . Following , our work establishes a rigorous connection between the clustering problem, spin-glass models on the Bethe lattice and the so called reconstruction problem. This connection points to fascinating applications and open problems. Consider a sequence of bits where we are trying to predict the next bit from the previous bits. Assume we are allowed to say 'predict 0' or 'predict 1', and our payoff is +1 if the prediction is correct and -1 otherwise. We will say that at each point in time the loss of an algorithm is the number of wrong predictions minus the number of right predictions so far. In this paper we are interested in algorithms that have essentially zero (expected) loss over any string at any point in time and yet have small regret with respect to always predicting 0 or always predicting 1. For a sequence of length @math our algorithm has regret @math and loss @math in expectation for all strings. We show that the tradeoff between loss and regret is optimal up to constant factors. Our techniques extend to the general setting of @math experts, where the related problem of trading off regret to the best expert for regret to the special' expert has been studied by Even- (COLT'07). We obtain essentially zero loss with respect to the special expert and optimal loss regret tradeoff, improving upon the results of Even- and settling the main question left open in their paper. The strong loss bounds of the algorithm have some surprising consequences. A simple iterative application of our algorithm gives essentially optimal regret bounds at multiple time scales, bounds with respect to @math -shifting optima as well as regret bounds with respect to higher norms of the input sequence.