Our research focuses on anomaly detection problems in unknown environments using Wireless Sensor Networks (WSN). We are interested in detecting two types of abnormal events: sensory level anomalies (e.g., noise in an office without lights on) and time-related anomalies (e.g., freezing temperature in a mid-summer day).We present a novel, distributed, machine learning based anomaly detector that is able to detect time-related changes. It consists of three components. First, a Fuzzy Adaptive Resonance Theory (ART) neural network classifier is used to label multi-dimensional sensor data into discrete classes and detect sensory level anomalies. Over time, the labeled classes form a sequence of classes. Next, a symbol compressor is used to extract the semantic meaning of the temporal sequence. Finally, a Variable Memory Markov (VMM) model in the form of a Probabilistic Suffix Tree (PST) is used to model and detect time-related anomalies in the environment. To our knowledge, this is the first work that analyzes/models the temporal sensor data using a symbol compressor and PST in a WSN. Our proposed detection algorithm is distributed, “light-weight”, and practical for resource constrained sensor nodes. We verify the proposed approach using a volcano monitoring dataset. Our results show that this approach yields the same performance as the traditional Markov models with much less cost.

Erasure codes have profound uses in wide- and medium-area storage applications. While infinite-size codes have been developed with optimal properties, there remains a need to develop small codes with optimal properties. In this paper, we provide a framework for exploring very small codes, and we use this framework to derive optimal and near-optimal ones for discrete numbers of data bits and coding bits. These codes have heretofore been unknown and unpublished, and should be useful in practice. We also use our exploration to make observations about upper bounds for these codes, in order to gain a better understanding of them and to spur future derivations of larger, optimal and near-optimal codes.

As peer-to-peer and widely distributed storage systems proliferate, the need to perform efficient erasure coding, instead of replication, is crucial to performance and efficiency. Low-density parity-check (LDPC) codes have arisen as alternatives to standard erasure codes, such as Reed-Solomon codes, trading off vastly improved decoding performance for inefficiencies in the amount of data that must be acquired to perform decoding. The scores of papers written on LDPC codes typically analyze their collective and asymptotic behavior. Unfortunately, their practical application requires the generation and analysis of individual codes for finite systems. This paper attempts to illuminate the practical considerations of LDPC codes for peer-to-peer and distributed storage systems. The three main types of LDPC codes are detailed, and a huge variety of codes are generated, then analyzed using simulation. This analysis focuses on the performance of individual codes for finite systems, and addresses several important heretofore unanswered questions about employing LDPC codes in real-world systems.

Software systems composed of highly reliable components may experience few, if any, failures while undergoing heavy testing or field usage. L.M. Kaufman et al. (1997, 1998) applied "statistics of the extremes" to software reliability analysis for failure as an infrequent, unlikely occurrence /sub -/ /sub a/ so-called rare event. This paper combines (i) software failure as a rare event with (ii) a finite-state, discrete-parameter recurrent Markov chain that models both the failures (as transitions to a rare fail state) and the software usage probabilities (as transitions among usage states not involving the fail state). When conditions for rare events are met, reliability analysis in greater detail, with fewer assumptions, may be possible, and there may be additional justification for using the popular Poisson and exponential distributions for certain random variables. We describe how the Markov chain and the "Poisson law of small numbers", which has a central role in the study of rare events and extreme values, yield (a) an explicit error bound on a Poisson approximation for counts of failures as rare events in long realizations of the chain, and (b) an approximate exponential distribution for the interoccurrence time of failures as rare events. We compute both the Poisson error bound and /spl chi//sup 2/ goodness-of-fit tests for samples and the approximate distributions for a small Markov chain. A typical application of these results would be in the analysis of software reliability for systems of high-quality COTS components.

Statistical testing of software establishes a basis for statistical inference about a software system's expected field quality. This paper describes a method for statistical testing based on a Markov chain model of software usage. The significance of the Markov chain is twofold. First, it allows test input sequences to be generated from multiple probability distributions, making it more general than many existing techniques. Analytical results associated with Markov chains facilitate informative analysis of the sequences before they are generated, indicating how the test is likely to unfold. Second, the test input sequences generated from the chain and applied to the software are themselves a stochastic model and are used to create a second Markov chain to encapsulate the history of the test, including any observed failure information. The influence of the failures is assessed through analytical computations on this chain. We also derive a stopping criterion for the testing process based on a comparison of the sequence generating properties of the two chains.>

String alignment by dynamic programming is generalized to include cyclic shift and corresponding optimal alignment cost for strings representing cyclic patterns. A guided search algorithm uses bounds on alignment costs to find all optimal cyclic shifts. The bounds are derived from submatrices of an initial dynamic programming matrix. Algorithmic complexity is analyzed for major stages in the search. The applicability of the method is illustrated with satellite DNA sequences and circularly permuted protein sequences.>

Markov networks are inferred automatically for different classes of learning strings. In subsequent string-to-network alignments for test samples, the networks are used to deduce structural characteristics and to provide similarity measures. By processing the similarity measures as numerical-value features, standard nonparametric decision-theoretic pattern classifiers may be applied to determine class membership. The nearest-neighbor rule and linear discriminant-function classifiers are discussed, and their performances are compared with that of a maximum-likelihood classifier. The hybrid system's ability to determine string orientation correctly is investigated. Experiments with several thousand human banded chromosomes are reported.>

Stochastic context-free grammars are an important tool in syntactic pattern analysis and other applications as well. This paper discusses major results in single-type and multitype branching processes used to study a grammar’s stochastic derivations. Probability generating functions are well-established as a tool in this area and are used extensively here.

A knowledge-based program to assist humans interpret satellite infrared images of a region of the Atlantic Ocean is described. the organization of the system and the nature of its knowledge base are discussed. the operation of the system in tracking mesoscale events in a registered sequence of IR images is illustrated.

An expert system is being developed as a step towards a more automated environment for processing satellite data of a region of the Atlantic Ocean and for interpreting the data with respect to mesoscale events. Oceanic events of interest include the Gulf Stream boundaries, warm-core rings, and cold-core rings.

Inference of Markov networks from finite sets of sample strings is formulated using dynamic programming. Strings are installed in a network sequentially via optimal string-to-network alignments computed with a dynamic programming matrix, the cost function of which uses relative frequency estimates of transition probabilities to emphasize landmark substrings common to the sample set. Properties of an inferred network are described and the method is illustrated with artificial data and with data representing banded human chromosomes.

The worst-case number of variable evaluations (testing cost) of Boolean functions is examined. Following up on a result by Rivest and Vuillemin, we show that all symmetric as well as all linearly separable Boolean functions are exhaustive, that is, have a pessimal worst-case testing cost.

The equivalence of nonterminals of an expansive tree grammar is considered. Algorithms are presented for constructing sets of equivalent nonterminals for an expansive tree grammar, for reducing the grammar, and for determining whether two grammars generate the same language.

The construction of sequential testing procedures from functions of discrete arguments is a common problem in switching theory, software engineering, pattern recognition, and management. The concept of the activity of an argument is introduced, and a theorem is proved which relates it to the expected testing cost of the most general type of decision trees. This result is then extended to trees constructed from relations on finite sets and to decision procedures with cycles. These results are used, in turn, as the basis for a fast heuristic selection rule for constructing testing procedures. Finally, some bounds on the performance of the selection rule are developed.

A formal method of correcting errors of changed, deleted, and inserted terminals in the strings of a context-free language is considered. Grammars generating strings containing these errors are first constructed from a known grammar for the language; these new grammars are then used to specify simple syntax-directed translation schemata which can parse both correct strings and strings with errors and simultaneously produce output strings in the original language. Stochastic aspects of productions and of errors are incorporated into the correction model to assign probabilities to translations produced.

The methods developed in this correspondence represent an approach to the problem of handling error-corrupted syntactic pattern strings, an area generally neglected in the numerous techniques for linguistic pattern description and recognition which have been reported. The basic approach consists of applying error transformations to the productions of context-free grammars in order to generate new grammars (also context-free) capable of describing not only the original error-free patterns, but also patterns containing specific types of errors such as deleted, added, and interchanged symbols which arise often in the pattern-scanning process. Theoretical developments are illustrated in the framework of a syntactic recognition system for chromosome structures.

Random occurrences of three types of errors in the input to a finite automaton are considered: an α error is a deletion of one symbol from the input string; a β error is an insertion of one extra symbol; and a δ error is a change of one symbol into another symbol. A method using operators for determining regular expressions defining error-corrupted strings is developed and is employed in the construction of a finite automaton, the outputs of which are stochastically generated by Bayes' Rule (with certain approximations) to take into account the frequencies with which strings appear as inputs and the probabilities of errors.

The variables in a fuzzy logic system may be assigned any truth value in the closed interval [0,1]. Assuming independent logic value assignments with known probability distributions, the effects of subsequent logic operations are examined.

The one-to-one relationship between finite automata, regular (type-3) languages, and regular expressions is well known. This correspondence demonstrates the use of regular expressions for describing deterministically finite fuzzy automata and regular fuzzy languages, and introduces a normal form for the production of a regular fuzzy grammar when the ``max(min)'' rule is used.