Path Kernels and Multiplicative Updates

Eiji Takimoto, Manfred K. Warmuth

TL;DR

This paper introduces "path kernels" as a novel way to efficiently implement multiplicative updates in machine learning algorithms. By representing complex feature spaces as directed graphs and using kernels that operate on paths within these graphs, the authors provide a unified framework for a range of multiplicative update algorithms, leading to significant computational speedups.

What Problem Does This Paper Address?

Many machine learning algorithms, like Support Vector Machines and Perceptron, rely on linear models in a high-dimensional feature space. On-line versions of these algorithms often use "additive updates," where a multiple of the last input is added to the current weight vector. However, there's another class of algorithms, often motivated by entropic regularization, that use "multiplicative updates." These updates are more challenging to implement efficiently, especially when the feature space is implicitly defined and potentially enormous (e.g., exponential in the number of input features). The authors aim to bridge this gap by developing a kernel-based approach that makes these multiplicative updates computationally tractable.

Methods

The core innovation is the introduction of path kernels. These kernels are defined on directed graphs, where each path from a source to a sink corresponds to a feature. The feature value for a path is the product of inputs along its edges. The paper shows how to define and compute these kernels efficiently, especially when the graph structure can be represented by a regular expression.

The key idea is to use these path kernels to implicitly represent exponentially many path weights. Instead of directly updating these path weights, the algorithm updates weights on the edges of the graph. This is achieved through a "Weight Pushing" algorithm, which re-normalizes edge weights to maintain desirable properties (like probabilistic outflow from vertices) while preserving the overall path weights. This indirect update mechanism, combined with efficient kernel computations, allows for the efficient implementation of multiplicative updates.

The paper also reformulates several existing algorithms (e.g., for learning disjunctions, dynamic routing, and on-line shortest path problems) within this path kernel framework, demonstrating its generality and effectiveness.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Path Kernels as a Unified Framework: The paper demonstrates that a wide range of multiplicative update algorithms can be elegantly expressed and implemented using path kernels on directed graphs. This provides a unifying perspective on these algorithms.
  • Implicit Representation of Exponential Features: Path kernels allow algorithms to work with exponentially many features (paths) without explicitly computing or storing them. This is achieved by operating on edge weights and using kernel computations.
  • Weight Pushing for Efficient Updates: The Weight Pushing algorithm is crucial for maintaining the desired probabilistic properties of edge weights after multiplicative updates, enabling efficient computation.
  • Regular Expressions for Efficient Kernel Computation: When the graph structure can be described by a regular expression, path kernel computations can be significantly sped up, often achieving linear time complexity with respect to the size of the regular expression.
  • Decomposable Losses are Key: The effectiveness of the multiplicative update framework hinges on the ability to decompose the loss function into a sum over the edges of a path. This allows for efficient gradient computation and subsequent updates.

Key Results

  • The paper provides a general method for implementing multiplicative updates using path kernels and the Weight Pushing algorithm.
  • It shows how to efficiently compute path kernels, especially when the underlying graph can be represented by a regular expression.
  • Several existing algorithms for learning disjunctions, dynamic routing, and on-line shortest path problems are reformulated and shown to be special cases of the proposed framework.
  • The paper demonstrates that this approach can lead to significant computational speedups compared to naive implementations.

Limitations and Future Work

  • The paper notes that the "multiplicative update" framework, as presented, requires the loss function to decompose into a sum over edges. This is a key requirement for efficient implementation.
  • An open question is whether similar kernel-based methods can be developed for other families of updates, such as the p-norm updates, which interpolate between the EG family and additive updates.
  • The authors suggest that further exploration of the relationship between special kernels and different update families could be a fruitful area of future research.

Summary updated

BibTeX
@inproceedings{takimoto2002path,
  author = {Eiji Takimoto and Manfred K. Warmuth},
  title = {{Path Kernels and Multiplicative Updates}},
  booktitle = {Conference on Learning Theory},
  year = {2002},
  doi = {10.1007/3-540-45435-7\_6},
}

Loading related content...

Figure