Scanning and Sequential Decision Making for Multidimensional Data-Part I: The Noiseless Case

Asaf Cohen, Neri Merhav, Tsachy Weissman

TL;DR

This paper introduces and formalizes the "scandiction" problem: optimally scanning and predicting multidimensional data (like images) to minimize prediction loss. The authors show that universal scanning schemes exist for stationary random fields, meaning they perform nearly as well as if the data's true distribution were known, and derive bounds on performance loss when suboptimal scanning is used.

What Problem Does This Paper Address?

Imagine you have a large, multidimensional dataset, like a high-resolution image. To process it efficiently, especially for tasks like compression, you need to decide not only how to predict the value of each data point (pixel) based on what you've seen so far, but also in what order to visit these points. This is the "scandiction" problem. While sequential prediction (where the order is fixed) is well-studied, the freedom to choose the scanning order in multidimensional data introduces significant complexity. The authors aim to understand what constitutes an optimal scanning and prediction strategy, what the minimum achievable prediction loss is, and whether "universal" strategies exist that perform well across a wide range of data distributions without needing to know the specific distribution beforehand.

Methods

The paper tackles the scandiction problem by first defining a "scandictor" as a pair of a scanning strategy (a sequence of site visits) and a prediction strategy. They then introduce the concept of "scandictability" as the best achievable performance for a given data source. A key focus is on "universal scandiction," where a strategy aims to perform nearly as well as the best possible strategy for any data distribution within a certain class (e.g., stationary random fields), without knowing that distribution. They employ techniques from information theory and learning theory, particularly adapting the "exponential weighting algorithm" from expert prediction to the scandiction setting by dividing data into blocks. They also derive theoretical bounds on the "excess loss" incurred when using a suboptimal scanner compared to the optimal one.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of random fields and individual images, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Scandiction is fundamentally harder than prediction: Unlike prediction, where universal strategies can compete with any finite set of predictors on individual sequences, universal scandiction for individual images is shown to be impossible with even just two arbitrary scandictors. This highlights the impact of reordering freedom.
  • Universality is achievable for stationary fields: For spatially stationary random fields, the authors prove the existence of universal scandictors that asymptotically achieve the best possible performance, even without knowing the field's distribution.
  • Block-wise processing is key for universality: The proposed universal scandictor operates by dividing the data into blocks and applying an exponential weighting algorithm to select the best scandictor for each block. This strategy allows for competition with arbitrary finite sets of scandictors.
  • Non-optimal scanners incur bounded excess loss: The paper quantifies the performance penalty of using a suboptimal scanning order while employing an optimal predictor, providing theoretical bounds on this "excess loss."

Key Results

  • Negative result for individual images: It's impossible to universally compete with any two arbitrary scandictors on individual images.
  • Positive result for stationary fields: Universal scandictors exist that achieve the scandictability of any spatially stationary random field.
  • Bounds on excess loss: The paper derives bounds on the performance degradation when using non-optimal scanners, showing it's related to the error in approximating certain information-theoretic quantities (like entropy). For the Hamming loss, this bound is shown to be at most 0.16, but often much lower for compressible images.

Limitations and Future Work

The paper acknowledges that while universal scandiction for stationary fields is established, the problem for individual images remains challenging, with only limited success for specific sets of scandictors. Determining the optimal scandictor for a given random field with a known probability measure is also noted as an open problem. The authors suggest that further research is needed to identify broader classes of scandictors that enable universal scandiction for individual images. The second part of this paper (referenced as [27]) addresses the more complex scenario of noisy data.

Summary updated

Abstract

We investigate the problem of scanning and prediction (ldquoscandiction,rdquo for short) of multidimensional data arrays. This problem arises in several aspects of image and video processing, such as predictive coding, for example, where an image is compressed by coding the error sequence resulting from scandicting it. Thus, it is natural to ask what is the optimal method to scan and predict a given image, what is the resulting minimum prediction loss, and whether there exist specific scandiction schemes which are universal in some sense. Specifically, we investigate the following problems: first, modeling the data array as a random field, we wish to examine whether there exists a scandiction scheme which is independent of the field's distribution, yet asymptotically achieves the same performance as if this distribution were known. This question is answered in the affirmative for the set of all spatially stationary random fields and under mild conditions on the loss function. We then discuss the scenario where a nonoptimal scanning order is used, yet accompanied by an optimal predictor, and derive bounds on the excess loss compared to optimal scanning and prediction. This paper is the first part of a two-part paper on sequential decision making for multidimensional data. It deals with clean, noiseless data arrays. The second part deals with noisy data arrays, namely, with the case where the decision maker observes only a noisy version of the data, yet it is judged with respect to the original, clean data.
BibTeX
@article{cohen2007scanning,
  author = {Asaf Cohen and Neri Merhav and Tsachy Weissman},
  title = {{Scanning and Sequential Decision Making for Multidimensional Data-Part I: The Noiseless Case}},
  journal = {IEEE Trans. Information Theory},
  year = {2007},
  url = {https://openreview.net/forum?id=cN0gpkc34h},
}
Figure