Airlines routinely overbook flights based on the expectation that some fraction of booked passengers will not show for each flight. Accurate forecasts of the expected number of no-shows for each flight can increase airline revenue by reducing the number of spoiled seats (empty seats that might otherwise have been sold) and the number of involuntary denied boardings at the departure gate. Conventional no-show forecasting methods typically average the no-show rates of historically similar flights, without the use of passenger-specific information.We develop two classes of models to predict cabin-level no-show rates using specific information on the individual passengers booked on each flight. The first of these models computes the no-show probability for each passenger, using both the cabin-level historical forecast and the extracted passenger features as explanatory variables. This passenger-level model is implemented using three different predictive methods: a C4.5 decision-tree, a segmented Naive Bayes algorithm, and a new aggregation method for an ensemble of probabilistic models. The second cabin-level model is formulated using the desired cabin-level no-show rate as the response variable. Inputs to this model include the predicted cabin-level no-show rates derived from the various passenger-level models, as well as simple statistics of the features of the cabin passenger population. The cabin-level model is implemented using either linear regression, or as a direct probability model with explicit incorporation of the cabin-level no-show rates derived from the passenger-level model outputs.The new passenger-based models are compared to a conventional historical model, using train and evaluation data sets taken from over 1 million passenger name records. Standard metrics such as lift curves and mean-square cabin-level errors establish the improved accuracy of the passenger-based models over the historical model. All models are also evaluated using a simple revenue model, and it is shown that the cabin-level passenger-based model can produce between 0.4% and 3.2% revenue gain over the conventional model, depending on the revenue-model parameters.

We develop a new concept for aggregating items of evidence for class probability estimation. In Naive Bayes, each feature contributes an independent multiplicative factor to the estimated class probability. We modify this model to include an exponent in each factor in order to introduce feature importance. These exponents are chosen to maximize the accuracy of estimated class probabilities on the training data. For Naive Bayes, this modification accomplishes more than what feature selection can. More generally, since the individual features can be the outputs of separate probability models, this yields a new ensemble modeling approach, which we call APM (Adjusted Probability Model), along with a regularized version called APMR.

In some classification problems the feature space is heterogeneous in that the best features on which to base the classification are different in different parts of the feature space. In some other problems the classes can be divided into subsets such that distinguishing one subset of classes from another and classifying examples within the subsets require very different decision rules, involving different sets of features. In such heterogeneous problems, many modeling techniques (including decision trees, rules, and neural networks) evaluate the performance of alternative decision rules by averaging over the entire problem space, and are prone to generating a model that is suboptimal in any of the regions or subproblems. Better overall models can be obtained by splitting the problem appropriately and modeling each subproblem separately. This paper presents a new measure to determine the degree of dissimilarity between the decision surfaces of two given problems, and suggests a way to search for a strategic splitting of the feature space that identifies regions with different characteristics. We illustrate the concept using a multiplexor problem, and apply the method to a DNA classification problem.

Generating classification rules or decision trees from examples has been a subject of intense study in the pattern recognition community, the statistics community, and the machine-learning community of the artificial intelligence area. We pursue a point of view that minimality of rules is important, perhaps above all other considerations (biases) that come into play in generating rules. We present a new minimal rule-generation algorithm called R-MINI (Rule-MINI) that is an adaptation of a well-established heuristic-switching-function-minimization technique, MINI. The main mechanism that reduces the number of rules is repeated application of generalization and specialization operations to the rule set while maintaining completeness and consistency. R-MINI results on some benchmark cases are also presented.

Deriving classification rules or decision trees from examples is an important problem. When there are too many features, discarding weak features before the derivation process is highly desirable. When there are numeric features, they need to be discretized for the rule generation. We present a new approach to these problems. Traditional techniques make use of feature merits based on either the information theoretic, or the statistical correlation between each feature and the class. We instead assign merits to features by finding each feature's "obligation" to the class discrimination in the context of other features. The merits are then used to rank the features, select a feature subset, and discretize the numeric variables. Experience with benchmark example sets demonstrates that the new approach is a powerful alternative to the traditional methods. This paper concludes by posing some new technical issues that arise from this approach.

A new global wiring algorithm designed for implementation on special purpose physical design machines is described. This algorithm computes more accurate estimates of wiring channel demand and supply than other known algorithms. It also makes better use of this information in determining wire routes. By exploiting the parallel processing capability of an interconnected array of microcomputers, the global wiring is completed effectively and quickly even for large chips.

A simple procedure to produce a minimum length test set for a parity network is presented. If M is the largest fan in of any EX-OR gate element in the tree, 2M test patterns are chosen by considering only 2M test sequences, of length 2M, assigned to each signal line.

Programmable logic arrays (PLA's) are the logic implementation vehicle for many applications. Due to their regular structure, one is able to model and analyze many more of the likely physical faults than the conventional stuck faults considered for random combinational logic implementations. We investigate shorts between the lines and crosspoint defects (spurious absence or presence), as well as stuck faults in a PLA. It is shown that a complete crosspoint test set also detects most of all faults analyzed. The crosspoint-oriented test set is compact, easy to generate, and technology-invariant. For the test generation, the regularity of the PLA structure is utilized for ease of computation and for test set optimality. Groups of crosspoint defects are sensitized simultaneously. For each such fault group, a test configuration which contains the totality of the tests for the faults under consideration is efficiently generated. When the configuration is empty, there exists no test that detects the particular group of faults. A covering set of tests is then selected from the configuration. Our test generation method (TPLA) uses two basic and effective heuristics; they are the initial word ordering for processing and the use of look-ahead merit function whenever there is a free choice of values in a test input variables.

It is well known that any switching function may be transformed into a completely symmetric function when repetition of the input variables is allowed. We present an algorithm that may be applied to reduce the number of repeated variables when the transformation is performed. The method is based on an iterative construction of symmetric functions by admitting an increasing number of variables towards a completely symmetric function. The algorithm produces a near minimal number of the total number of inputs in the resultant symmetric function. This algorithm can also be used to determine all partially symmetric variable sets of a given function.

Self-reciprocal polynomials (SRP's) are used to generate reversible codes with a read backward property. We characterize all the irreducible SRP's of a given degreer. Furthermore, a method of obtaining a maximal exponent SRP is presented. A short table lists the maximal exponents of SRP's of degree up tor = 34.

The comment is valid in that the authors followed the given algorithm G in footnote 1 to the letter to come to their conclusion. However, the spirit of the algorithm was somewhat misrepresented in the original paper. A clearer version for the algorithm G follows. The two additional tests claimed by the commentors do not arise if the following version is carried to the letter. And therefore our original assertion about the near minimality still seems valid. Similarly, the additional tests claimed by the commentors using procedure NR will be eliminated if the following version of algorithm G is used in procedure NR. This answers the commentors conclusion 2) in [1].

In high-speed multipliers, multiplication is activated by processing a group of bits in parallel. As a result, any defects in circuitry produce possible errors in positions that are separated by fixed periods. A class of codes for the correction of such iterative error patterns resulting from a single fault is presented in this paper. A decoding algorithm together with a simple implementation scheme is also discussed.

A theorem is presented that simplifies the computations necessary for complementing a Boolean function.

The error-correcting codes for symbols from GF (2b) are often used for correction of byte-errors in binary data. In these byte-error-correcting codes each check symbol in GF (2b) is expressed as b binary check digits and each information symbol in GF (2b), likewise, is expressed by b binary information digits. A new class of codes for single-byte-error correction is presented. The code is general in that the code structure does not depend on symbols from GF (2b). In particular, the number of check bits are not restricted to the multiples of b as in the case of the codes derived from GF (2b) codes. The new codes are either perfect or maximal and are easily implementable using shift registers.

The important problem of generating test patterns to detect multiple faults has received little attention, mainly due to their computational complexity. The theoretical results of this paper show that near minimal tests for multiple faults can be generated with complexity of computation comparable to that of single faults.