The memory centre

Przemyslaw Spurek, Jacek TaborarXiv 2012 · OpenReview

TL;DR

This paper proposes a novel method for finding an optimal "center" for data compression by minimizing the average number of bits required to encode data points. The core idea is to shift the origin of the coordinate system to minimize this average bit count, effectively finding the most efficient representation for a given dataset.

What Problem Does This Paper Address?

Data compression aims to represent information using the fewest bits possible. A common approach involves assigning shorter codes to more frequent data points and longer codes to less frequent ones. For continuous data, this often involves discretizing the data and considering the "amount of bits" needed to represent a value with a certain accuracy. The authors tackle the problem of finding the best "origin" or "center" for this coding scheme. Instead of just finding the optimal code lengths for a fixed origin, they ask: where should we place the origin (represented by the parameter 'a') so that the average number of bits needed to encode data from a random variable X is minimized? This is crucial because the choice of origin can significantly impact the efficiency of the resulting compression.

Methods

The paper's approach is rooted in minimizing an expected value. For a given accuracy $h$, the number of bits to encode a value $x$ is approximated by $m_h(x) \approx \log_2(\max\{1, |x/h|\})$. The goal is to find $a$ that minimizes $E[m_h(X-a)]$.

A key theoretical result (Theorem 2.1) shows that as the accuracy $h$ approaches zero (meaning we are looking for a more precise representation), the problem of minimizing the expected bit count asymptotically reduces to minimizing the integral of $\ln(|x-a|)f(x)dx$, where $f(x)$ is the probability density function of the random variable $X$. This integral is related to the concept of differential entropy.

When the density function $f(x)$ is unknown, the authors propose using a kernel density estimation method to approximate it. However, directly minimizing the resulting function can be numerically challenging. To address this, they introduce a function $L(a)$ (related to the integral mentioned above) and its approximation, the Cauchy M-estimator, which is more robust and numerically stable.

The core of their practical solution lies in an Iterated Reweighted Least Squares (IRLS) algorithm. This algorithm iteratively refines an estimate of the optimal center 'a' by calculating weighted averages of the data points, where the weights are derived from the properties of the chosen objective function (specifically, the Cauchy M-estimator). This process converges to a local minimum of the function that represents the average memory cost.

Datasets

The paper uses synthetic datasets generated from mixtures of normal and uniform distributions to test their algorithm. They also present an example using real-world Forex data (USD/EUR index) to demonstrate the density estimation and the algorithm's performance. No new benchmark datasets are introduced.

Key Insights and Ideas

  • Shifting the Origin for Compression: The fundamental insight is that the choice of the origin (or "center") for data representation significantly impacts compression efficiency. By optimizing this origin, we can achieve better compression.
  • Asymptotic Equivalence to Differential Entropy: For high accuracy (small $h$), the problem of minimizing average bits is closely related to minimizing the integral of $\ln(|x-a|)f(x)dx$, which has connections to differential entropy. This provides a theoretical foundation for their approach.
  • Robustness through M-estimators: The use of the Cauchy M-estimator is a crucial practical insight. It makes the optimization process more robust to outliers in the data, which is important for real-world applications where data might not perfectly follow a theoretical distribution.
  • IRLS for Efficient Optimization: The IRLS algorithm provides an effective and computationally feasible way to find the minimum of the objective function, even when the density is unknown and estimated.

Key Results

  • The paper demonstrates that the optimal center 'a' asymptotically becomes independent of the accuracy parameter $h$.
  • They show that their algorithm, based on the Cauchy M-estimator and IRLS, provides a good approximation to the global minimum of the memory cost function.
  • In experiments with synthetic data (mixtures of normal and uniform distributions), their algorithm's result is very close to the true global minimum, significantly outperforming the simple barycenter (mean) of the data, especially for non-unimodal densities.
  • The Forex data example shows a successful application of their density estimation and optimization method.

Limitations and Future Work

  • Numerical Instability: The paper acknowledges numerical instability issues when dealing with the function $L(a)$ for values of $a$ close to 1. While they propose using an approximation (Cauchy M-estimator), this is a noted challenge.
  • Assumptions on Density: The theoretical derivations often rely on assumptions about the density function (e.g., locally bounded). While the kernel estimation and M-estimator approach aim to mitigate the need for a known density, the performance might still be influenced by the underlying data distribution.
  • Future Work: The paper implicitly suggests that further exploration of different kernel functions and M-estimators could lead to even more robust and efficient methods. The focus on a single dimension ($a \in \R$) also suggests potential extensions to higher dimensions.

Summary updated

Abstract

Let $x \in \R$ be given. As we know the, amount of bits needed to binary code $x$ with given accuracy ($h \in \R$) is approximately $ \m_{h}(x) \approx \log_{2}(\max {1, |\frac{x}{h}|}). $ We consider the problem where we should translate the origin $a$ so that the mean amount of bits needed to code randomly chosen element from a realization of a random variable $X$ is minimal. In other words, we want to find $a \in \R$ such that $$ \R \ni a \to \mathrm{E} (\m_{h} (X-a)) $$ attains minimum.
BibTeX
@misc{spurek2012memory,
  author = {Przemyslaw Spurek and Jacek Tabor},
  title = {{The memory centre}},
  year = {2012},
  eprint = {1204.0281},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1204.0281},
}
Figure