Initializing RBF-Networks with Small Subsets of Training Examples

AAAI 1999

TL;DR

This paper introduces SELEX, a novel algorithm for initializing Radial Basis Function (RBF) networks by selecting a small, complementary subset of training examples as RBF centers. This approach aims to create smaller, more efficient RBF networks with competitive classification accuracy compared to methods using random subsets or more complex clustering techniques.

What Problem Does This Paper Address?

Radial Basis Function (RBF) networks are powerful tools for function approximation and pattern recognition. A critical challenge in designing RBF networks is determining the "centers" of the Gaussian basis functions. While using all training examples as centers is computationally prohibitive and leads to overly large networks, random selection of a subset can be suboptimal, especially when dealing with noisy or redundant data. Existing methods for selecting centers, such as clustering or decision-tree induction, can be complex or lead to larger networks than desired. This paper addresses the need for an efficient method to select a minimal yet representative set of training examples to serve as RBF centers, thereby creating compact and accurate RBF networks.

Methods

The core of the paper is the SELEX (SELection of EXamples) algorithm. Instead of selecting a single large subset of training examples, SELEX proposes creating three small, complementary subsets ($S_1, S_2, S_3$). Each subset is used to train a simple 1-nearest-neighbor (1-NN) sub-classifier ($C_1, C_2, C_3$). The key idea is that these sub-classifiers should make errors in different parts of the instance space, allowing their individual mistakes to be "outvoted" by the others.

The algorithm iteratively refines the selection of $S_2$ and $S_3$ to minimize the overall error rate of the combined classifier. It leverages a mathematical lemma (Lemma 1) that guides the selection of $S_2$ by balancing the trade-off between reducing the error rate of $C_2$ and ensuring that $C_1$ and $C_2$ disagree on a significant number of examples. The final set of RBF centers is the union of these three small, complementary subsets ($S = S_1 \cup S_2 \cup S_3$). The computational cost of SELEX is shown to be linear in the number of training examples ($O(mn)$).

Datasets

The paper evaluates SELEX on two types of datasets:

  • Synthetic Data: Three noise-free artificial domains were created:
  • Hyperbola: Defined by the inequality $3x^2 - 3y^2 < 1$.
  • Hypercubes: Defined by points falling inside one of three 5-dimensional hypercubes.
  • Hyperspheres: Defined by points falling inside one of three 5-dimensional hyperspheres. These synthetic datasets allowed for controlled experiments with known decision surfaces.

  • Benchmark Data: A selection of real-world datasets from the UCI Machine Learning Repository were used, focusing on two-class problems with numeric attributes. Some datasets with more than two classes were adapted into two-class problems.

Key Insights and Ideas

  • Complementarity is Key: The success of SELEX hinges on the idea that the selected subsets should be complementary. This means they should err on different types of examples, allowing a voting mechanism to correct individual mistakes.
  • Small Subsets, Big Impact: The paper demonstrates that a few carefully selected examples can be more effective than a larger, randomly chosen set for initializing RBF networks.
  • Efficiency Gains: SELEX achieves competitive or superior accuracy with significantly fewer RBF centers compared to other methods, leading to more compact and potentially faster-executing networks.
  • Trade-off Management: The algorithm explicitly manages the trade-off between reducing the error of individual sub-classifiers and ensuring their disagreement, a crucial aspect for effective ensemble-like behavior.

Key Results

  • Superior Accuracy: SELEX consistently outperformed a baseline method using randomly selected examples (RANDEX) across both synthetic and benchmark datasets, especially when using a small number of RBF centers (6 centers). The margin of improvement was as high as 13% on the synthetic hyperbola domain.
  • Compact Networks: SELEX produced RBF networks with a significantly smaller number of centers (e.g., 6 or 15 centers) while achieving comparable or better accuracy than methods that might implicitly use more centers or require more complex initialization.
  • Outperforms Clustering: In benchmark domains, SELEX's initialization approach was found to be superior to initialization using k-means clustering, which is a more computationally intensive method.
  • Impact of Center Count: The advantage of SELEX over random selection was more pronounced with fewer centers. As the number of centers increased, the benefit of SELEX diminished, suggesting that random selection becomes sufficiently representative for larger networks.

Limitations and Future Work

  • Fixed Subset Size: The paper primarily uses fixed sizes for the complementary subsets ($|S_i|=2$ or $|S_i|=5$). The authors acknowledge that different domains might benefit from different subset sizes and suggest future work to find heuristics for determining optimal sizes.
  • Generalization of K-tuples: The current SELEX algorithm focuses on three complementary subsets (triplets). The authors propose extending this to more general K-tuples ($K>3$) to potentially improve performance and explore more general versions of the underlying mathematical framework.
  • Comparison to Decision Trees: While SELEX performs well, the authors note that its performance might not reach the accuracies reported by Kubat (1998) for decision-tree based initialization. However, SELEX offers a significant advantage in network compactness.
  • Heuristics for Subset Size: Future research could focus on developing heuristics to determine the ideal size of the complementary subsets for a given problem.
  • Flexibility in Subset Sizes: Allowing each complementary subset to have a different size could further enhance flexibility.

Summary updated

BibTeX
@inproceedings{1999initializing,
  title = {{Initializing RBF-Networks with Small Subsets of Training Examples}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}

Loading related content...

Figure