Expression of Fractals Through Neural Network Functions

Nadav Dym, Barak Sober, Ingrid Daubechies

TL;DR

This paper demonstrates that deep neural networks (DNNs) can efficiently represent fractal-like functions generated by Iterated Function Systems (IFS) using a number of parameters that grows linearly with the fractal's complexity, not exponentially. This finding offers a theoretical explanation for why DNNs excel at tasks involving self-similar patterns, like image processing, and suggests new avenues for image compression and representation.

What Problem Does This Paper Address?

Deep neural networks (DNNs) have achieved remarkable success, particularly in computer vision. While it's known that DNNs can approximate a vast range of functions, understanding why their depth is so crucial for performance, especially compared to shallow networks, remains an active research area. One key theoretical aspect is the "expressiveness" of DNNs – the types of functions they can represent. DNNs, with their piecewise linear (ReLU) activation functions, generate piecewise linear (PwL) functions. Researchers have observed that the number of linear regions (ℓ) in these PwL functions can grow exponentially with the number of network parameters (p). However, a simple dimension argument reveals that DNNs cannot generate all PwL functions with many linear regions (ℓ >> p). This raises a fundamental question: what specific families of PwL functions can DNNs efficiently represent, especially those with ℓ >> p? This paper tackles this by investigating the connection between DNNs and fractal structures, which are known to exhibit self-similarity and can be generated by Iterated Function Systems (IFS).

Methods

The core of the paper's contribution lies in showing that DNNs can efficiently represent functions generated by Iterated Function Systems (IFS). The authors first establish theoretical groundwork by defining Neural Network Functions (NNFs) and outlining basic NN operations like composition, splitting, and summation. They then introduce the concept of a "CPwL indicator function" – a piecewise linear function that approximates the indicator function of a set (i.e., it's positive inside the set and non-positive outside).

The main technical achievement is proving Theorem 1: For a specific class of IFS (those with nice compact initial sets and invertible affine transformations), the CPwL indicator functions of the fractal sets generated by these IFS can be represented by NNFs with a number of parameters that grows linearly with the "depth" of the fractal construction (denoted by k), rather than exponentially. This is achieved by constructing the CPwL indicator for the k-th iteration of the fractal (Ck) by composing the CPwL indicator of the initial set (C1) with a carefully constructed NNF that represents the inverse affine transformations of the IFS.

Theorem 2 extends this to "just touching" IFS (those with nice open initial sets), showing that DNNs can approximate the indicator functions of these fractal sets to arbitrary precision.

The proofs rely on:

  • Constructing CPwL indicator functions: This involves using combinations of "min" and "max" operations (which are themselves implemented as NNFs) and affine transformations.
  • Composition of NNFs: The paper leverages the fact that composing NNFs results in another NNF, with parameters and depth scaling predictably.
  • Iterated Function Systems (IFS) theory: The paper uses properties of IFS, particularly the concept of "nice sets" and invertible affine transformations, to build the connection.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and the properties of functions generated by IFS, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • DNNs are naturally suited for self-similar structures: The paper provides a theoretical basis for why DNNs excel at tasks involving fractals and self-similarity, which are prevalent in natural images.
  • Efficient representation of fractal complexity: The key insight is that DNNs can represent fractal structures generated by IFS with a number of parameters that scales linearly with the fractal's complexity (k), which is a significant improvement over exponential scaling. This is a crucial finding for understanding the power of depth in DNNs.
  • Bridging IFS and DNNs: The work establishes a formal link between the mathematical framework of IFS and the representational capabilities of DNNs, opening doors for new theoretical analyses and practical applications.
  • Implications for image processing: The findings suggest that the success of DNNs in image processing might be partly due to their ability to efficiently capture the inherent self-similarities present in natural images, similar to how IFS generate textures.

Key Results

  • Theorem 1: CPwL indicator functions for fractal sets generated by a specific class of IFS can be represented by NNFs with parameters scaling linearly with the fractal's iteration count (k), i.e., O(k).
  • Theorem 2: For another class of IFS, DNNs can approximate the indicator functions of fractal sets to arbitrary precision with similar parameter efficiency.
  • Dimension Argument (Lemma 3): DNNs with a limited number of parameters (p) cannot represent all piecewise linear functions with a large number of linear regions (ℓ > p), highlighting the need to understand which functions are efficiently representable.

Limitations and Future Work

  • Limitations:
    • The theorems apply to specific classes of IFS (those with nice compact/open initial sets and invertible affine transformations). The paper mentions that any IFS can be "lifted" to a higher dimension to fit these conditions, but this adds complexity.
  • The paper focuses on CPwL indicator functions. While these can approximate indicator functions to arbitrary precision, they are not the exact indicator functions themselves (which are discontinuous).
  • The theoretical results are not directly validated with empirical experiments on image datasets.
  • Future Work:
    • The authors suggest exploring improved image compression algorithms based on DNNs, leveraging their ability to efficiently represent fractal structures.
  • Investigating the connection between DNNs' efficiency in encoding IFS and the human visual system's perception of self-similarity in images.
  • Developing practical DNN-based algorithms for representing self-similarities in images.
  • Further exploring the theoretical underpinnings of DNN expressiveness, particularly concerning the trade-off between depth, parameters, and the complexity of representable functions.

Summary updated

Abstract

To help understand the underlying mechanisms of neural networks (NNs), several groups have studied the number of linear regions ℓ of piecewise linear (PwL) functions, generated by deep neural networks (DNN). In particular, they showed that ℓ can grow exponentially with the number of network parameters p, a property often used to explain the advantages of deep over shallow NNs. Nonetheless, a dimension argument shows that DNNs cannot generate all PwL functions with ℓ linear regions when ℓ > p.It is thus natural to seek to characterize specific families of functions with ℓ > p linear regions that can be constructed by DNNs. Iterated Function Systems (IFS) recursively construct a sequence of PwL functions Fk with a number of linear regions which is exponential in k. We show that Fk can be generated by a NN using only O(k) parameters. IFS are used extensively to generate natural-looking landscape textures in artificial images as well as for compression of natural images. The surprisingly good performance of this compression suggests that human visual system may lock in on self-similarities. The combination of this phenomenon with the capacity of DNNs to efficiently approximate IFS may contribute to the success of DNNs, particularly striking for image processing tasks.
BibTeX
@article{dym2020expression,
  author = {Nadav Dym and Barak Sober and Ingrid Daubechies},
  title = {{Expression of Fractals Through Neural Network Functions}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2020},
  url = {https://openreview.net/forum?id=2NygBd2m7bt},
}
Figure