Bootstrapping Training-Data Representations for Inductive Learning: A Case Study in Molecular Biology

Haym Hirsh, Nathalie JapkowiczAAAI 1994

Introduction

In the field of machine learning, the effectiveness of inductive learning systems, such as decision trees, is heavily dependent on the quality of data representation. In molecular biology, raw data typically consists of long nucleotide sequences (A, C, G, T), where the underlying biological logic is often obscured. While domain experts can manually engineer high-level features to improve model performance, this process is labor-intensive and difficult to scale.

This paper introduces a "bootstrapping" approach to feature engineering designed to amplify expert knowledge. By utilizing a small set of human-created features as a "seed," the system automatically generates new features that mimic their syntactic structure. This method significantly improves the accuracy of models identifying DNA promoter sequences without requiring continuous expert intervention.

Methodology: The Bootstrapping Process

The authors propose a three-stage bootstrapping process to expand the feature space based on the syntactic patterns of existing expert-defined features. The primary learner used in this study is the C4.5 decision tree algorithm.

  1. Stage 1: Intra-Feature Extrapolation: The system analyzes the internal patterns of expert features. For instance, if a feature identifies a sequence starting with three purines (A or G), the system generates all possible variations adhering to that specific structural template.
  2. Stage 2: Inter-Feature Extrapolation: This stage identifies patterns across different features. If multiple expert features appear to be truncated versions of longer sequences, the system applies this "rule" to other known features to create new, related ones.
  3. Stage 3: Feature Specialization: General features are refined into more specific versions. If a successful feature utilizes a general category like "any pyrimidine," the system creates specialized versions specifying exact nucleotides (e.g., Cytosine) based on their utility in earlier model iterations.

Experimental Setup

The study focuses on DNA Promoter Recognition using a dataset from the UC Irvine Repository of Machine Learning Datasets. To ensure biological accuracy, the authors utilized a cleaned version of the dataset (following Norton, 1994) consisting of 100 examples: 47 positive promoters and 53 negative non-promoters. The performance of the bootstrapped representations was compared against "Raw" DNA strings and the "Hirsh-Noordewier" representation, which consists of 25 expert-engineered features.

Key Insights and Discussion

A central premise of this work is that syntactic similarity can serve as a proxy for biological significance. If an expert identifies a specific pattern as important, other patterns with a similar structure are likely to be relevant. This approach allows for the amplification of expertise rather than its replacement.

To validate the effectiveness of the method, the authors compared bootstrapped features against "random" control representations of equivalent length.

Comparison of bootstrapped features against random control representations (Representations 1-4) across different generation stages.

As illustrated in the figure above, the bootstrapped features consistently outperformed the random controls. Furthermore, while adding bootstrapped features improved performance, adding too many random features eventually introduced spurious correlations, leading to overfitting and decreased accuracy.

Key Results

The transition through the bootstrapping stages resulted in a dramatic reduction in error rates. By the final stage, the error rate was reduced by more than half compared to the raw data baseline, significantly outperforming the manually engineered features alone.

Detailed error rates for unpruned and pruned C4.5 models across all representation stages.

The final error rate for the unpruned model reached 12.9%, a substantial improvement over the 33.3% error rate of the raw data and the 22.9% error rate of the initial expert features.

Conclusion and Future Work

While the bootstrapping concept is general, the specific operators used in this study were tailored to molecular biology. A significant challenge remains in the manual creation of these operators. The authors' long-term goal is "Constructive Induction"—the development of systems that can automatically recognize patterns in features and generate their own transformation operators. Additionally, the computational cost of Stage 3 specialization necessitated feature pruning, highlighting the need for more efficient search strategies in massive feature spaces.

Summary updated

BibTeX
@inproceedings{hirsh1994bootstrapping,
  author = {Haym Hirsh and Nathalie Japkowicz},
  title = {{Bootstrapping Training-Data Representations for Inductive Learning: A Case Study in Molecular Biology}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure