Given N learners each capable of learning concepts (subsets) in the sense of Valiant (1985), we are interested in combining them using a single fuser. We consider two cases. In open fusion the fuser is given the sample and the hypotheses of the individual learners; we show that a fusion rule can be obtained by formulating this problem as another learning problem. We show sufficiency conditions that ensure the composite system to be better than the best of the individual. Second, in closed fusion the fuser does not have an access to either the training sample or the hypotheses of the individual learners. By using a linear threshold fusion function (of the outputs of individual learners) we show that the composite system can be made better than the best of the statistically independent learners.>

We model computer transactions as generated by two stationary stochastic processes, the legitimate (normal) process N and the misuse process M. We define misuse (anomaly) detection to be the identification of transactions most likely to have been generated by M. We formally demonstrate that the accuracy of misuse detectors is bounded by a function of the difference of the densities of the processes N and M over the space of transactions. In practice, detection accuracy can be far below this bound, and generally improves with increasing sample size of historical (training) data. Careful selection of transaction attributes also can improve detection accuracy; we suggest several criteria for attribute selection, including adequate sampling rate and separation between models. We demonstrate that exactly optimizing even the simplest of these criteria is NP-hard, thus motivating a heuristic approach. We further differentiate between modeling (density estimation) and nonmodeling approaches.>

Computer use is modeled as a mixture of two stochastic processes, normal and misuse. Intrusion detection is formally defined as identifying those transactions generated by the misuse process. Bounds for detection performance are derived in terms of the ratios of the densities of the processes at the individual transactions. It is shown that any optimal intrusion detection system must rank transaction suspicion consistently with these ratios. Sparsity of data requires that transactions be grouped into equivalence classes that preserve the order of the true ratio ranking and reduce the number of singleton and unobserved transactions. Results are described that demonstrate that in general this 'singleton reduction' problem is NP-hard.>

Given N learners each capable of learning concepts (subsets) in the sense of Valiant (1985), we are interested in combining them using a single fuser. We consider two cases. In open fusion the fuser is given the sample and the hypotheses of the individual learners; we show that a fusion rule can be obtained by formulating this problem as another learning problem. We show sufficiency conditions that ensure the composite system to be better than the best of the individual. Second, in closed fusion the fuser does not have an access to either the training sample or the hypotheses of the individual learners. By using a linear threshold fusion function (of the outputs of individual learners) we show that the composite system can be made better than the best of the statistically independent learners. >

Classifier systems are “discovery” production rule systems that utilize the genetic algorithm for discovery and allocate credit through the bucket brigade. For any given problem, the success of a classifier system depends on the choice of representation, the system's ability to attain reward or punishment states (evaluation states), accurate estimation of the relative merit of individual classifiers, and the genetic algorithm's ability to use information about the current population of rules to generate better rules. This article addresses the adequacy of the bucket brigade and backward averaging for credit assignment and reviews a preliminary study of two variants in conjunction with rules that are fully enumerated as well as with discovery. Potential difficulties with each of these methods are highlighted in several theoretical examples, including one from the literature. Preliminary results and tentative similarities between these hybrids and Sutton's Adaptive Heuristic Critic (AHC) are suggested.

Functions are partially characterized as easy or hard for genetic algorithms to optimize. The failure modes of inappropriate embedding, crossover disruption, and deceptiveness are introduced, analyzed, and resolved in part. Virtually all optimizable (by any method) real valued functions defined on a finite domain are shown to be theoretically easy for genetic algorithms given appropriately chosen representations. Unfortunately, problems that are easy in theory can be difficult in practice because of sampling error. Also, the transformations required to induce favorable representations are generally arbitrary permutations, and the space of permutations is so large that search for good ones is intractable. The space of inversions is amenable to search, but inversions are insufficiently powerful to overcome deceptiveness. On the other hand, affine transformations (over the diadic group) are shown to be sufficiently powerful to transform at least selected deceptive problems into easy ones. These new results should be useful in guiding empirical studies and are expected to provide a foundation for further theoretical analysis.

The authors discusses Wisdom and Sense (W&S), a computer security anomaly detection system. W&S is statistically based. It automatically generates rules from historical data and, in terms of those rules, identifies computer transactions that are at variance with historically established usage patterns. Issues addressed include how W&S generates rules from a necessarily small sample of all possible transactions, how W&S deals with inherently categorical data, and how W&S assists system security officers in their review of audit logs. Preliminary results with W&S show that the software does periodically detect anomalies of high interest even in data though to be free of such events.>