Learning figures with the Hausdorff metric by fractals - towards computable binary classification

Mahito Sugiyama, Eiju Hirowatari, Hideki Tsuiki, Akihiro YamamotoMachine Learning 2013 · OpenReview

Abstract

We present learning of figures, nonempty compact sets in Euclidean space, based on Gold’s learning model aiming at a computable foundation for binary classification of multivariate data. Encoding real vectors with no numerical error requires infinite sequences, resulting in a gap between each real vector and its discretized representation used for the actual machine learning process. Our motivation is to provide an analysis of machine learning problems that explicitly tackles this aspect which has been glossed over in the literature on binary classification as well as in other machine learning tasks such as regression and clustering. In this paper, we amalgamate two processes: discretization and binary classification. Each learning target, the set of real vectors classified as positive, is treated as a figure. A learning machine receives discretized vectors as input data and outputs a sequence of discrete representations of the target figure in the form of self-similar sets, known as fractals. The generalization error of each output is measured by the Hausdorff metric. Using this learning framework, we reveal a hierarchy of learnable classes under various learning criteria in the track of traditional analysis based on Gold’s learning model, and show a mathematical connection between machine learning and fractal geometry by measuring the complexity of learning using the Hausdorff dimension and the VC dimension. Moreover, we analyze computability aspects of learning of figures using the framework of Type-2 Theory of Effectivity (TTE).

Introduction: The Discretization Gap

Most machine learning algorithms treat real-valued multivariate data as if it can be perfectly represented on a computer. In reality, encoding a real vector exactly requires an infinite sequence of digits. Computers must "discretize" this data, creating a fundamental gap between the original analog value and its digital representation.

While the popular PAC (Probably Approximately Correct) learning model uses probability to handle noise, it doesn't adequately address the "computability" of learning—specifically, which classes of continuous objects can be exactly learned from finite, discretized data. This research aims to provide a computable foundation for binary classification that treats discretization and classification as a single, amalgamated process.

The Learning Framework

The researchers utilize several sophisticated mathematical frameworks to bridge the gap between analog reality and digital computation.

The learning process: a learner receives discretized positive and negative examples of a target figure and outputs a self-similar set (fractal) as a hypothesis.
  • Gold’s Learning Model: Also known as "identification in the limit," this model assumes a learner receives a stream of data and produces a sequence of hypotheses that eventually converges to the correct answer.
  • Fractals as Hypotheses: The authors use self-similar sets (fractals) as their hypothesis space. Because any compact set can be approximated arbitrarily closely by a self-similar set (based on the Collage Theorem), fractals serve as powerful, finite representations of complex figures.
  • Hausdorff Metric: Instead of standard accuracy, the "goodness" of a classifier is measured using the Hausdorff metric, which calculates the distance between two sets (the target figure and the learned hypothesis).

Mathematical Foundations

To analyze the computability and complexity of this process, the paper employs the Type-2 Theory of Effectivity (TTE). This framework treats the learner as a Turing machine processing infinite sequences of discretized data. The following table summarizes the key mathematical notation used in this formalization.

Table of mathematical notation and symbols used throughout the paper.

Key Insights and Results

Bridging Geometry and Learning Theory

The paper establishes a formal mathematical link between fractal geometry (Hausdorff dimension) and computational learning theory (VC dimension). Key insights include:

  • Amalgamation of Discretization and Classification: Discretization is fundamentally part of the learning process, not just a preprocessing step.
  • Fractal Universality: Finite representations of fractals are sufficient to approximate any "figure" (nonempty compact set) in Euclidean space.
  • The Necessity of Negative Examples: "Effective learning"—where generalization error decreases monotonically—requires an "informant" (both positive and negative examples).

Learnability and Complexity

The study yields several significant theoretical results:

  • Learnability Hierarchy: The authors constructed a hierarchy of learnable classes under five different criteria: explanatory, consistent, reliable, refutable, and effective learning.
  • Complexity Bounds: They proved that the number of positive examples required for learning is bounded by a relationship between the Hausdorff dimension (dimH) of the target figure and the VC dimension (dimVC) of the hypothesis space. Specifically, for a large enough resolution k, the number of positive examples is at least 2^(k * dimH K).
  • Computability Proofs: Using TTE, they demonstrated that learning can be viewed as a computable realization of the identity mapping from a set of figures to a space with a finer topology.

Conclusion

This work provides a rigorous theoretical foundation for understanding how computers learn from continuous data. While the current focus is on binary classification, the authors suggest that this framework could be extended to tasks like regression and clustering, potentially leading to a unified theory of computable machine learning for all multivariate data.

Summary updated

Abstract

We present learning of figures, nonempty compact sets in Euclidean space, based on Gold’s learning model aiming at a computable foundation for binary classification of multivariate data. Encoding real vectors with no numerical error requires infinite sequences, resulting in a gap between each real vector and its discretized representation used for the actual machine learning process. Our motivation is to provide an analysis of machine learning problems that explicitly tackles this aspect which has been glossed over in the literature on binary classification as well as in other machine learning tasks such as regression and clustering. In this paper, we amalgamate two processes: discretization and binary classification. Each learning target, the set of real vectors classified as positive, is treated as a figure. A learning machine receives discretized vectors as input data and outputs a sequence of discrete representations of the target figure in the form of self-similar sets, known as fractals. The generalization error of each output is measured by the Hausdorff metric. Using this learning framework, we reveal a hierarchy of learnable classes under various learning criteria in the track of traditional analysis based on Gold’s learning model, and show a mathematical connection between machine learning and fractal geometry by measuring the complexity of learning using the Hausdorff dimension and the VC dimension. Moreover, we analyze computability aspects of learning of figures using the framework of Type-2 Theory of Effectivity (TTE).
BibTeX
@article{sugiyama2013learning,
  author = {Mahito Sugiyama and Eiju Hirowatari and Hideki Tsuiki and Akihiro Yamamoto},
  title = {{Learning figures with the Hausdorff metric by fractals - towards computable binary classification}},
  journal = {Machine Learning},
  year = {2013},
  url = {https://openreview.net/forum?id=G8Li4wYcFs},
}

Loading related content...

Figure