Regression with Linear Factored Functions

Wendelin Böhmer, Klaus Obermayer

TL;DR

This paper introduces Linear Factored Functions (LFF), a novel regression algorithm that learns functions composed of multiplicative "factored" basis functions. LFFs offer significant advantages in handling high-dimensional data by breaking the "curse of dimensionality" and enabling efficient analytical computations, performing competitively with Gaussian Processes while being much more compact.

What Problem Does This Paper Address?

Many real-world applications require estimating complex functions from data, a task often hindered by the "curse of dimensionality." This curse means that as the number of input dimensions increases, the amount of data needed to accurately model the function grows exponentially. Traditional methods like kernel methods and Gaussian Processes (GP) struggle with this, as they often require computationally expensive operations (like integration over the entire input space) that become intractable in high dimensions. This paper aims to develop a regression method that can effectively handle high-dimensional inputs by leveraging a specific function structure that allows for efficient computation and avoids the exponential data requirements.

Methods

The core contribution is the introduction of Linear Factored Functions (LFF). An LFF is defined as a linear combination of factored basis functions. A factored basis function itself is a product of one-dimensional functions, each operating on a single input dimension. This multiplicative structure is key.

The paper proposes a regularized greedy optimization scheme to learn these LFFs. Instead of optimizing all parameters at once, the algorithm iteratively learns one factored basis function at a time. This involves:

  1. Inner Loop: Optimizing a single factored basis function by iteratively updating its one-dimensional components. This optimization is guided by a cost function that balances fitting the data with regularization, which encourages smoothness in regions with sparse data.
  2. Outer Loop: Adding the newly learned factored basis function to the model and re-solving a least-squares problem for the linear coefficients. This process continues until the addition of new basis functions yields diminishing returns.

The regularization term is derived from a Taylor approximation of the cost function and modulates the sample noise distribution based on the input space density, promoting smoothness where data is scarce.

Datasets

The paper evaluates LFF on:

  • Artificial two-dimensional toy-data set: A noisy spiral dataset with a sinus label, where additional independent noise dimensions were added to simulate increasing dimensionality.
  • Five regression benchmarks from the UCI Machine Learning Repository:
    • Concrete compressive strength
    • Combined cycle power plant energy output
    • Wine quality (white and red subsets)
    • Yacht hydrodynamics

Key Insights and Ideas

  • Breaking the Curse of Dimensionality: The multiplicative structure of factored basis functions allows LFF to handle high-dimensional inputs much more gracefully than traditional kernel methods. This is because operations like integration and multiplication can be performed analytically, avoiding the need for sampling the entire high-dimensional space.
  • Compact Representations: LFF models are significantly more compact than GP models, using only a few factored basis functions (3-12 on average) to achieve comparable performance. This is a major advantage for deployment and interpretability.
  • Analytical Computations: The factored structure enables analytical computation of inner products and point-wise products of LFFs. This is crucial for applications like belief propagation and reinforcement learning, where such operations are frequent.
  • Greedy Optimization: The iterative, greedy approach to learning factored basis functions simplifies the optimization problem, avoiding the non-convexity issues of a full LFF optimization.

Key Results

  • On the 2D spiral toy data, LFF significantly outperforms Gaussian Processes (GP) when additional noise dimensions are introduced, demonstrating its robustness to the curse of dimensionality.
  • On the UCI benchmark datasets, LFF achieves performance comparable to sparse and traditional GPs.
  • LFF models are remarkably compact, requiring only 3-12 factored basis functions to match the performance of GPs that use 278-2000 kernel basis functions.
  • In some cases, LFF showed a statistically significant advantage over GP on benchmark datasets (e.g., concrete compressive strength).

Limitations and Future Work

  • Optimization Challenges: The optimization of LFF is not globally convex, and the current greedy approach may converge to local minima. The paper suggests that the order of updating factor functions can influence the solution.
  • Runtime: The iterative nature of the inner loop for optimizing each factor function can make the algorithm slow compared to standard approaches.
  • Future Work: The authors suggest further research into controlling the non-convex optimization problem, potentially by finding better strategies for selecting the order of updates. They also propose exploring extensions for sparse regression with LFF, which could further improve efficiency and handle applications where only a subset of input dimensions are relevant. The potential for LFF in reinforcement learning and Bayesian inference with junction trees is also highlighted.

Summary updated

Abstract

Many applications that use empirically estimated functions face a curse of dimensionality, because the integrals over most function classes must be approximated by sampling. This paper introduces a novel regression-algorithm that learns linear factored functions (LFF). This class of functions has structural properties that allow to analytically solve certain integrals and to calculate point-wise products. Applications like belief propagation and reinforcement learning can exploit these properties to break the curse and speed up computation. We derive a regularized greedy optimization scheme, that learns factored basis functions during training. The novel regression algorithm performs competitively to Gaussian processes on benchmark tasks, and the learned LFF functions are with 4-9 factored basis functions on average very compact.
BibTeX
@inproceedings{bohmer2014regression,
  author = {Wendelin Böhmer and Klaus Obermayer},
  title = {{Regression with Linear Factored Functions}},
  booktitle = {ECML/PKDD},
  year = {2014},
  url = {https://openreview.net/forum?id=B5x84093yc},
}
Figure