A pseudoinverse learning algorithm for feedforward neural networks with stacked generalization applications to software reliability growth data

Ping Guo, Michael R. LyuNeurocomputing 2004 · DOI

TL;DR

This paper introduces a novel "Pseudoinverse Learning Algorithm" (PIL) for feedforward neural networks that offers faster training and perfect learning without the need for user-tuned parameters like learning rates. The algorithm is demonstrated to be effective for complex tasks like stacked generalization, particularly in applications like software reliability growth modeling.

What Problem Does This Paper Address?

Traditional gradient descent algorithms, like backpropagation (BP), for training feedforward neural networks often suffer from slow convergence rates and can get stuck in local minima. Furthermore, they require careful tuning of parameters such as learning rate and momentum, for which there's no clear theoretical basis. This makes them inefficient for applications demanding high precision or involving computationally intensive tasks like stacked generalization, where many networks need to be trained. The paper aims to provide a more efficient, automated, and precise learning algorithm.

Methods

The core of the paper is the Pseudoinverse Learning Algorithm (PIL). This algorithm leverages generalized linear algebra, specifically matrix inner products and pseudoinverse operations. Instead of iterative gradient updates, PIL directly computes the weight matrix for each layer. The key idea is to add hidden layers until the network can perfectly map the training data. This is achieved by ensuring that the matrix representing the hidden layer's output has a rank equal to the number of training examples. When this condition is met, the pseudoinverse can be used to find an exact solution for the weights, effectively eliminating learning errors layer by layer. The algorithm is feedforward-only, meaning it doesn't require error backpropagation.

A significant aspect of PIL is its ability to handle adding or deleting training samples efficiently by leveraging algorithms for updating pseudoinverse matrices, avoiding costly recomputations.

Datasets

The paper uses several synthetic datasets for function mapping and real-world datasets for software reliability growth modeling:

  • Synthetic Datasets:
    • Sine function mapping (50 training examples).
  • Biegler-König and Bärmann's nonlinear mapping (50 training examples).
  • A piecewise linear function (20 and 5 training examples).
  • Real-world Datasets:
    • Sys1 software failure data (54 data pairs, split into 37 training and 17 test samples).
  • Sys3 software failure data (278 data pairs, split into 186 training and 92 test samples).

These datasets are used for both training and testing the network's generalization capabilities.

Key Insights and Ideas

  • Perfect Learning is Achievable: The PIL algorithm demonstrates that perfect learning (zero training error) is achievable for feedforward neural networks, provided the network architecture (number of hidden neurons) is appropriately chosen.
  • Parameter-Free Learning: A major advantage of PIL is its complete independence from user-defined parameters like learning rate or momentum, which are critical for gradient descent methods. This simplifies the training process significantly.
  • Layer-by-Layer Error Elimination: PIL addresses learning errors sequentially, layer by layer. This approach is more direct than global error minimization in gradient descent.
  • Rank Augmentation: The algorithm implicitly relies on the fact that nonlinear activation functions can increase the rank of the transformed matrices, which is crucial for finding the pseudoinverse solution.
  • Efficiency for Complex Tasks: PIL's speed and precision make it particularly well-suited for computationally intensive tasks like stacked generalization, where training numerous networks is required.

Key Results

  • Speed: The paper claims PIL is significantly faster than BP. For a complex task (Sys3 dataset, achieving 10⁻¹⁴ error), PIL took less than 7.8 seconds, while BP required over 10 hours on the same machine.
  • Accuracy: PIL achieves perfect learning on synthetic datasets, with actual learning errors as low as 7.533 × 10⁻¹⁸ (Example 1) and 3.573 × 10⁻²⁵ (Example 2).
  • Generalization: While PIL can achieve perfect training accuracy, the paper explores its performance in generalization tasks. For smooth functions, generalization is good. However, for noisy data (like software reliability data), overfitting in level-0 networks can lead to poor generalization, and stacked generalization doesn't necessarily fix this if the base models are overfitted.
  • Stacked Generalization Performance: For noisy data, stacked generalization, when applied to networks with some training bias (to avoid overfitting), can improve generalization error (e.g., reducing test error from 0.0434 to 0.0152 for Sys1). However, it can also increase computation time.

Limitations and Future Work

  • Network Architecture Determination: While PIL can achieve perfect learning, determining the optimal number of hidden layers and neurons for a given problem remains a challenge. The paper notes that this is data-dependent and difficult to formulate a universal theory for.
  • Overfitting in Noisy Data: The paper highlights that stacked generalization does not inherently solve the problem of overfitting to noise. If level-0 networks overfit, the overall system's generalization will suffer.
  • Comparison with Other Algorithms: The authors acknowledge they haven't performed a comprehensive comparison of PIL's overall performance with other gradient descent algorithms, particularly regarding the number of iterations, as complexity per iteration differs.
  • Future Work: The paper suggests that for large-scale datasets, methods like "divide-and-conquer" or ensemble networks could be explored to reduce individual network size and potentially improve performance. The authors also mention that for some real-world tasks, high learning accuracy might not be necessary, and strategies like early stopping with a three-layer network could be employed to avoid overfitting.

Summary updated

BibTeX
@article{guo2004pseudoinverse,
  author = {Ping Guo and Michael R. Lyu},
  title = {{A pseudoinverse learning algorithm for feedforward neural networks with stacked generalization applications to software reliability growth data}},
  journal = {Neurocomputing},
  year = {2004},
  doi = {10.1016/s0925-2312(03)00385-0},
}
Figure