next up previous
Next: References Up: Detecting Imperfect Patterns in Previous: Finding Dependencies in Synthetic

Conclusions

Although computational problems have been overcome, testing and collecting more dependencies exacts a cost in terms of certainty and model deluge. The algorithm requires serial testing of hypotheses: contingency table analysis is run on similar patterns for the same data repeatedly in the course of local search. Consequently, the probability threshold of .05 is no longer an accurate figure. We are currently investigating methods of adjusting tex2html_wrap_inline372 down to compensate for the serial testing inherent in this algorithm. Given the fairly shallow depth of the search (number of tests to be run during a search) and the low values of P found in the most significant dependencies, it appears that adjusting tex2html_wrap_inline372 will enhance the certainty of the results without unduly dropping the number of dependencies detected in the data.

From the point of view of someone interpreting dependencies, it is easy to be overwhelmed with the number found. Local search addresses this problem in two ways: First, only the most significant dependencies are likely to be found. Although the algorithm is doing multiple hill-climbs, it will likely find repeats in subsequent trials of the same pattern at the top of a large hill. Second, the search neighborhood in local search provides a natural clustering: the basins of attraction around most locally optimal patterns. These basins ensure that only one of the set of similar dependencies will be returned, and they can be exploited to cluster dependencies that contain the same subsequences.

Subsequences that are repeated across dependencies are probably themselves significant or may indicate cases in which several events exert a similar influence. For example, in the Phoenix data, some of the failures were variants on the same problem (e.g., two of them were failures in calculating paths), and some of the recovery actions were variants on the same method (e.g., two of them replanned, but from different points in the plan). We would like to cluster related dependencies to find commonalities and to reduce the burden of looking over a long list.

Clusters can be formed by finding locally optimal patterns and then backing out of the basin at individual positions to find other highly significant related patterns. The algorithm was augmented to ``back out'' of local maxima and gather patterns from the neighborhood that were also significant. If we examine patterns local to the maxima found in the test with precursors of length three and window of length seven, then we find that at each position in the pattern at least one and as many as six out of sixteen other patterns are significant. With local search, we can find clusters of somewhat less significant but highly similar composition.

Local search dependency detection is data directed, finds highly significant dependencies and provides a convenient method of clustering. As demonstrated on the Phoenix data, the local search method is effective at detecting long dependencies in data with considerable overlap in the elements of the dependencies: it finds a large number of the most significant dependencies in a manageable amount of computation time. However, not too surprisingly, when tested on synthetic data, it does not perform nearly as well when there is little relationship between subsequences and the long sequences that form dependencies.

This research was supported by a Colorado State University Diversity Career Enhancement grant and ARPA/Rome Laboratory contract F30602-93-C-0100. The US Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon. I wish to thank Darrell Whitley for his advice on the application of local search, Aaron Fuegi for his programming, Steve Leathard for running tests, Tim Oates for the synthetic data generator, and Douglas Fisher and anonymous reviewers for their patient and careful reading and suggestions for improvement.


next up previous
Next: References Up: Detecting Imperfect Patterns in Previous: Finding Dependencies in Synthetic

adele howe
Wed Mar 6 09:01:10 MST 1996