Rapid Quality Estimation of Neural Network Input Representations

Kevin J. Cherkauer, Jude W. ShavlikNeurIPS 1995

This paper, published in 1995, addresses a classic bottleneck in machine learning: the "black box" nature of neural network training and the high computational cost of feature engineering.

TL;DR

Training neural networks is notoriously slow, making it difficult to iteratively test which data representation works best. This paper introduces "transparency" measures—fast, decision-tree-based metrics—that can predict which input representation will lead to the highest neural network accuracy at a fraction of the computational cost.

The Problem: Wrapper vs. Filter Approaches

In the mid-90s, much like today, the success of an Artificial Neural Network (ANN) depended heavily on how data was represented (the "input representation"). However, ANNs are computationally expensive to train. If a researcher has ten different ways to encode their data, the standard "wrapper" approach requires training ten separate ANNs to see which performs best.

The authors sought a "filter" method: a way to quickly estimate the quality of a representation without actually training the neural network. They specifically wanted to measure transparency, defined as the density of simple, accurate concepts within a representation. If a representation is "transparent," a learning algorithm should be able to find a simple, high-performing model easily.

Methodology

The authors propose three "model-based" transparency measures. All three use decision trees as a proxy for the neural network, based on the transfer assumption: if a problem is easy for a decision tree to solve simply, it will likely be easy for a neural network to solve accurately.

  1. avg(leaves): The average number of leaves in $n$ randomly constructed decision trees that correctly classify the training set.
  2. min(leaves): The minimum number of leaves found across those $n$ random trees.
  3. ID3leaves: The number of leaves in a single tree generated by the standard ID3 algorithm.

These are compared against a baseline called "Blurring," a previously published metric that measures feature interaction (essentially, how much information is "blurred" across multiple features).

The evaluation process involved creating multiple "damaged" versions of input representations (R1 through R10), training ANNs on all versions to get a "ground-truth" ranking of quality, and calculating the transparency measures to see how well their rankings correlated with the ANN ground truth using Spearman’s rank correlation ($r_s$).

Datasets

The authors evaluated their measures on three difficult, real-world pattern recognition problems:

  • DNA: Predicting gene reading frames (20,000 examples, 6 classes).
  • NIST: Recognizing handwritten digits (3,471 examples, 10 classes).
  • Magellan: Detecting volcanoes in radar images of Venus (625 examples, 2 classes).

Key Results

Massive Speedups

The computational savings provided by the filter method were enormous.

Computational time comparison across datasets

For the DNA dataset, training the ANN took 212,900 seconds. In stark contrast, calculating the decision-tree-based measures took mere seconds (e.g., ~4 seconds for ID3leaves), representing a speedup of roughly 50,000x to 90,000x.

High Correlation and Performance

The transparency measures showed remarkable alignment with actual neural network performance.

Ground-truth accuracy and correlation tables for all datasets

The transparency measures—especially ID3leaves and min(leaves)—showed near-perfect correlation ($r_s \approx 0.9$ to $1.0$) with the actual ANN rankings on the DNA and NIST datasets. Furthermore, the new measures consistently outperformed the "Blurring" metric. This was particularly evident on the Magellan dataset, where Blurring failed to provide a statistically significant correlation, while the decision tree measures remained robust.

Key Insights

  • The Transfer Assumption Works: Surprisingly, even though decision trees and neural networks use entirely different mathematical approaches (symbolic logic vs. continuous weights), the "complexity" of a decision tree is a highly accurate predictor of ANN performance.
  • Transparency is Distinct from Sufficiency: A representation can be "sufficient" (meaning it contains enough info to separate classes perfectly) but still be poor because the concept is too complex to learn easily. The authors proved that their measures track this "ease of learning" specifically.
  • The Power of ID3: While random sampling (avg and min leaves) was effective, the simple ID3leaves measure was remarkably robust. It was the only measure that correctly predicted that adding redundant features could actually improve ANN performance by providing more "flexible" paths to a solution.

Limitations and Future Work

  • The Transfer Assumption Limits: While the assumption held for these three datasets, the authors acknowledge that ANNs and decision trees are known to excel at different types of problems. There may be specific domains where this proxy fails.
  • Search Integration: The authors suggest that the next logical step is to use these fast transparency measures as "fitness functions" in automated search algorithms (like genetic algorithms) to evolve or discover optimal input representations without ever touching a neural network during the search process.
  • Dataset Variety: While the three datasets were "real-world," they represent a narrow slice of potential ANN applications. Further testing on modern, high-dimensional data (like raw image pixels or embeddings) would be required to see if the leaf-count proxy still scales.

Summary updated

BibTeX
@inproceedings{cherkauer1995rapid,
  author = {Kevin J. Cherkauer and Jude W. Shavlik},
  title = {{Rapid Quality Estimation of Neural Network Input Representations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1995},
}
Figure