The Canonical Distortion Measure for Vector Quantization and Function Approximation

Jonathan BaxterICML 1997

TL;DR

This paper introduces the "Canonical Distortion Measure" (CDM), a novel way to define distance between data points that is derived from an "environment of functions" (e.g., classifiers). The CDM is shown to be optimal for learning piecewise constant approximations of these functions, offering a more principled approach to vector quantization and function approximation than standard metrics like Euclidean distance.

What Problem Does This Paper Address?

When we represent data like images or speech signals using vector quantization, we need a way to measure the "distance" or "distortion" between different data points. Standard metrics, such as squared Euclidean distance, often fail to capture our subjective sense of similarity. For instance, two slightly different images of the same face might have a large Euclidean distance but appear very similar to a human. This mismatch leads to inefficient use of codebook vectors in quantization and hinders the effectiveness of learning algorithms that rely on nearest-neighbor concepts or piecewise constant approximations. The paper aims to bridge this gap by proposing a distortion measure that is intrinsically linked to the task at hand – approximating functions within a given "environment."

Methods

The core contribution is the Canonical Distortion Measure (CDM). The authors propose that the "natural" distortion measure for a space of data points (X) is not inherent but rather induced by an environment of functions (F) defined on X. This environment could be a set of classifiers, for example. The CDM is defined as the average distance between the outputs of randomly chosen functions from this environment when applied to two data points:

ρ(x, x') = ∫<sub>F</sub> σ(f(x), f(x')) dQ(f)

where σ is a distance measure on the function outputs and Q is a probability measure over the function environment F.

The paper then proves a key optimality theorem: the CDM is the optimal distortion measure for generating piecewise constant approximations of the functions in the environment. This means that if your goal is to approximate functions using a set of representative points (quantization) and associated regions (Voronoi cells), using the CDM to define these will yield the best possible approximation.

The paper also explores calculating the CDM in closed form for specific environments (linear, thresholded linear, quadratic) and proposes a method for learning the CDM using neural networks, especially when the environment is unknown.

Datasets

The paper does not focus on standard benchmark datasets. Instead, it introduces a synthetic "robot arm" environment for demonstrating the learning of the CDM. This environment consists of functions representing the squared distance of the end of a two-link robot arm from the origin, parameterized by the link lengths and joint angles. This synthetic environment allows for exact calculation of the true CDM, enabling a direct comparison with the learned CDM.

Key Insights and Ideas

  • Distortion is task-dependent: The paper argues that there's no "a priori" natural distortion measure. Instead, the appropriate measure is dictated by the purpose for which the data is being used, specifically, the type of functions you want to approximate.
  • Environments induce distortion: The set of functions (e.g., classifiers) that operate on the data space implicitly defines a natural way to measure similarity. Similar inputs should yield similar outputs for most functions in the environment.
  • CDM for optimal approximation: The CDM is proven to be the optimal distortion measure for creating piecewise constant approximations. This means it directly addresses the problem of finding the best representative points and regions for approximating a set of functions.
  • Squared Euclidean distance is only optimal for linear functions: A surprising result is that the commonly used squared Euclidean distance is the CDM only for a linear environment. This implies its use is suboptimal for more complex tasks like image or speech recognition, where functions are rarely linear.
  • Learning to learn: Learning the CDM is framed as "learning to learn." Once the CDM is learned, it provides the necessary information to efficiently learn any function within that environment.

Key Results

  • Closed-form CDMs: The paper derives closed-form expressions for the CDM for linear, thresholded linear, and quadratic function environments. For instance, a linear environment yields the squared Euclidean distance, while a thresholded linear environment results in the angle between input vectors.
  • Optimality Theorem: The CDM is mathematically proven to be the optimal distortion measure for generating piecewise constant approximations.
  • CDM Learning: An experiment demonstrates that a neural network can successfully learn the CDM for a synthetic "robot arm" environment.
  • Improved Generalization: When the learned CDM was used to guide the learning of piecewise constant approximations, it resulted in significantly better generalization performance compared to learning functions directly without the CDM, especially with limited training data. For example, in the robot arm experiment, using the learned CDM led to a much lower average generalization error.

Limitations and Future Work

  • Synthetic Environments: The experiments demonstrating the CDM learning and its benefits were conducted on synthetic, toy environments (linear, quadratic, robot arm). The authors acknowledge that the real test will be applying these techniques to more complex, real-world domains like speech and character recognition.
  • Computational Complexity: While the CDM is theoretically optimal, its computation can be complex, especially when the environment is large or unknown. The neural network approach to learning the CDM is a step towards addressing this.
  • Future Work: The authors suggest exploring the application of these techniques to more complex domains. They also highlight that learning the CDM is particularly advantageous when one needs to learn a large number of functions from the same environment, as it provides a foundation for efficient learning.

Summary updated

BibTeX
@inproceedings{baxter1997canonical,
  author = {Jonathan Baxter},
  title = {{The Canonical Distortion Measure for Vector Quantization and Function Approximation}},
  booktitle = {International Conference on Machine Learning},
  year = {1997},
}

Loading related content...

Figure