Machine Learning manuscript No.
(will be inserted by the editor)

Learning figures with the Hausdorff metric by fractals— towards computable binary classification
Mahito Sugiyama · Eiju Hirowatari · Hideki Tsuiki · Akihiro
Yamamoto

Received: date / Accepted: date

Abstract We present learning of figures, nonempty compact sets in Euclidean space, based on Gold’s learningmodel 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 dataand 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 andfractal 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 Theoryof Effectivity (TTE).
Keywords Binary classification · Discretization · Self-similar set · Gold’s learning model · Hausdorff metric ·Type-2 Theory of Effectivity

Mahito Sugiyama
The Institute of Scientific and Industrial Research (ISIR), Osaka University, Mihogaoka 8-1, Ibaraki, Osaka, 567-0047, Japan
Tel: +81-6-6879-8540
Fax: +81-3-6879-8544
E-mail: mahito@ar.sanken.osaka-u.ac.jp
Eiju HirowatariCenter for Fundamental Education, The University of Kitakyushu
Hideki Tsuiki
Graduate School of Human and Environmental Studies, Kyoto University
Akihiro Yamamoto
Graduate School of Informatics, Kyoto University* Most of this work was accomplished when the first author was at Kyoto University.

2

Mahito Sugiyama et al.

1 Introduction
Discretization is a fundamental process in machine learning from analog data. For example, Fourier analysis is
one of the most essential signal processing methods and its discrete version, discrete Fourier analysis, is used
for learning or recognition on a computer from continuous signals. However, in the method, only the directionof the time axis is discretized, so each data point is not purely discretized. That is to say, continuous (electrical)
waves are essentially treated as finite/infinite sequences of real numbers, hence each value is still continuous(analog). The gap between analog and digital data therefore remains.
This problem appears all over machine learning from observed multivariate data. The reason is that an
infinite sequence is needed to encode a real vector exactly without any numerical error, since the cardinalityof the set of real numbers, which is the same as that of infinite sequences, is much larger than that of the setof finite sequences. Thus to treat each data point on a computer, it has to be discretized and considered as an
approximate value with some numerical error. However, to date, most machine learning algorithms ignore thegap between the original value and its discretized representation. This gap could result in some unexpectednumerical errors1 . Since now machine learning algorithms can be applied to massive datasets, it is urgent togive a theoretical foundation for learning, such as classification, regression, and clustering, from multivariate
data, in a fully computational manner to guarantee the soundness of the results of learning.
In the field of computational learning theory, Valiant’s learning model (also called PAC, Probably Approximately Correct, learning model), proposed by Valiant (1984), is used for theoretical analysis of machinelearning algorithms. In this model, we can analyze the robustness of a learning algorithm in the face of noise or
inaccurate data and the complexity of learning with respect to the rate of convergence or the size of the input using the concept of probability. Blumer et al (1989) and Ehrenfeucht et al (1989) provided the crucial conditions
for learnability, that is, the lower and upper bounds for the sample size, using the VC (Vapnik-Chervonenkis)
dimension (Vapnik and Chervonenkis 1971). These results can be applied to various concept representations
that handle real-valued inputs and use real-valued parameters, for example, to analyze learning of neural networks (Baum and Haussler 1989). However, this learning model is not in line with discrete and computational
analysis of machine learning. We cannot know which class of continuous objects is exactly learnable and whatkind of data are needed to learn from a finite expression of discretized multivariate data. Although PAC learningfrom axis-parallel rectangles has already been investigated (Blumer et al 1989; Kearns and Vazirani 1994; Longand Tan 1998), which can be viewed as a variant of learning from multivariate data with numerical error, it is
not applicable in the study. Our goal is to investigate computational learning, focusing on a common groundbetween “learning” and “computation” of real numbers based on the behavior of Turing machines, without
any reference to probability distributions. For the purpose of the investigation, we need to distinguish abstract
mathematical objects such as real numbers and their concrete representations, or codes, on a computer.
Instead, in this paper we use Gold’s learning model (also called identification in the limit), which is originally designed for learning of recursive functions (Gold 1965) and languages (Gold 1967). In the model, alearning machine is assumed to be a procedure, i.e., a Turing machine (Turing 1937) which never halts, thatreceives training data from time to time, and outputs representations (hypotheses) of the target from time totime. All data are usually assumed to be given at some point in the future. Starting from this learning model,
learnability of classes of discrete objects, such as languages and recursive functions, has been analyzed indetail under various learning criteria (Jain et al 1999). However, analysis of learning for continuous objects,
such as classification, regression, and clustering for multivariate data, with Gold’s model is still under development, despite such settings being typical in modern machine learning. To the best of our knowledge, the only
line of studies devoted to learning of real-valued functions was by Hirowatari and Arikawa (1997); Apsı̄tis et al(1999); Hirowatari and Arikawa (2001); Hirowatari et al (2003, 2005, 2006), where they addressed the analysisof learnable classes of real-valued functions using computable representations of real numbers2 . We therefore
need a new theoretical and computational framework for modern machine learning based on Gold’s learningmodel with discretization of numerical data.
1
2

Müller (2001) and Schröder (2002a) give some interesting examples in the study of computation for real numbers.
Sugiyama et al (2006, 2009) have also contributed to the area, but their work was only presented at closed workshops.

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

3

In this paper we consider the problem of binary classification for multivariate data, which is one of the mostfundamental problems in machine learning and pattern recognition. In this task, a training dataset consists ofa set of pairs {(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )}, where xi ∈ Rd is a feature vector, yi ∈ {0, 1} is a label, and thed-dimensional Euclidean space Rd is a feature space. The goal is to learn a classifier from the given training
dataset, that is, to find a mapping h : Rd → {0, 1} such that, for all x ∈ Rd , h(x) is expected to be the same as
the true label of x. In other words, such a classifier h is the characteristic function of a subset L = {x ∈ Rd |h(x) = 1} of Rd , which has to be similar to the true set K = {x ∈ Rd | the true label of x is 1} as far as possible.
Throughout the paper, we assume that each feature is normalized by some data preprocessing such as min-max
normalization for simplicity, that is, the feature space is the unit interval (cube) I d = [0, 1] × · · · × [0, 1] in thed-dimensional Euclidean space Rd . In many realistic scenarios, each target K is a closed and bounded subsetof I d , i.e., a nonempty compact subset of I d , called a figure. Thus here we address the problem of binaryclassification by treating it as “learning of figures”.
In this machine learning process, we implicitly treat any feature vector through its representation, or code
on a computer, that is, each feature vector x ∈ I d is represented by a sequence p over some alphabet Σ using
an encoding scheme ρ . Here such a surjective mapping ρ is called a representation and should map the set of“infinite” sequences Σ ω to I d since there is no one-to-one correspondence between finite sequences and real
numbers (or real vectors). In this paper, we use the binary representation ρ : Σ ω → [0, 1] with Σ = {0, 1}, which
is defined by ρ (p) := ∑ pi · 2−(i+1) for an infinite sequence p = p0 p1 p2 . . . . For example, ρ (0100 . . . ) = 0.25,
ρ (1000 . . . ) = 0.5, and ρ (0111 . . . ) = 0.5. However, we cannot treat infinite sequences on a computer in finite
time and, instead, we have to use discretized values, i.e., truncated finite sequences in any actual machinelearning process. Thus in learning of a classifier h for the target figure K, we cannot use an exact data pointx ∈ K but have to use a discretized finite sequence w ∈ Σ ∗ which tells us that x takes one of the values in theset {ρ (p) | w ⊏ p} (w ⊏ p means that w is a prefix of p). For instance, if w = 01, then x should be in theinterval [0.25, 0.5]. For a finite sequence w ∈ Σ ∗ , we define ρ (w) := {ρ (p) | w ⊏ p with p ∈ Σ ω } using thesame symbol ρ . From a geometric point of view, ρ (w) means a hyper-rectangle whose sides are parallel to theaxes in the space I d . For example, for the binary representation ρ , we have ρ (0) = [0, 0.5], ρ (1) = [0.5, 1],
ρ (01) = [0.25, 0.5], and so on. Therefore in the actual learning process, while a target set K and each pointx ∈ K exist mathematically, a learning machine can only treat finite sequences as training data.
Here the problem of binary classification is stated in a computational manner as follows: Given a training
dataset {(w1 , y1 ), (w2 , y2 ), . . . , (wn , yn )} (wi ∈ Σ ∗ for each i ∈ {1, 2, . . . , n}), where yi = 1 if ρ (wi ) ∩ K ̸= 0/ fora target figure K ⊆ I d and yi = 0 otherwise, learn a classifier h : Σ ∗ → {0, 1} for which h(w) should be thesame as the true label of w for all w ∈ Σ ∗ . Each training datum (wi , yi ) is called a positive example if yi = 1 anda negative example if yi = 0.
Assume that a figure K is represented by a set P of infinite sequences, i.e., {ρ (p) | p ∈ P} = K, using thebinary representation ρ . Then learning the figure is different from learning the well-known prefix closed set
Pref(P), defined as Pref(P) := {w ∈ Σ ∗ | w ⊏ p for some p ∈ P}, since generally Pref(P) ̸= {w ∈ Σ ∗ | ρ (w) ∩K ̸= 0}/ holds. For example, if P = {p ∈ Σ ω | 1 ⊏ p}, the corresponding figure K is the interval [0.5, 1]. Then, theinfinite sequence 0111 . . . is a positive example since ρ (0111 . . . ) = 0.5 and ρ (0111 . . . ) ∩ K ̸= 0,/ but it is notcontained in Pref(P). This problem is fundamentally due to rational numbers having two representations, forexample, both 0111 . . . and 1000 . . . represent 0.5. Solving this mismatch between objects of learning and theirrepresentations is one of the challenging problems of learning continuous objects based on their representation
in a computational manner.
For finite expression of classifiers, we use self-similar sets known as fractals (Mandelbrot 1982) to exploit
their simplicity and the power of expression theoretically provided by the field of fractal geometry. Specifically,
we can approximate any figure by some self-similar set arbitrarily closely (derived from the Collage Theorem
given by Falconer (2003)) and can compute it by a simple recursive algorithm, called an IFS (Iterated Function
System) (Barnsley 1993; Falconer 2003). This approach can be viewed as the analog of the discrete Fourier
analysis, where FFT (Fast Fourier Transformation) is used as the fundamental recursive algorithm. Moreover,in the process of sampling from analog data in discrete Fourier analysis, scalability is a desirable property. It
requires that when the sample resolution increases, the accuracy of the result is monotonically refined. We formalize this property as effective learning of figures, which is inspired by effective computing in the framework

4

Mahito Sugiyama et al.

Positive examples
Negative examples
Learner

Target figure

Self-similar set represented
by a hypothesis

Fig. 1 Our framework of learning figures.

of Type-2 Theory of Effectivity (TTE) studied in computable analysis (Schröder 2002b; Weihrauch 2000).
This model guarantees that as a computer reads more and more precise information of the input, it produces
more and more accurate approximations of the result. Here we adapt this model from computation to learning,where if a learner (learning machine) receives more and more accurate training data, it learns better and betterclassifiers (self-similar sets) approximating the target figure.
To summarize, our framework of learning figures (shown in Figure 1) is as follows: Positive examples areaxis-parallel rectangles intersecting the target figure, and negative examples are those disjoint with the target.
A learner reads a presentation (infinite sequence of examples), and generates hypotheses. Hypotheses are finite
sequences (codes) that are discrete expressions of self-similar sets. To evaluate “goodness” of each classifier,
we use the concept of generalization error and measure the error by the Hausdorff metric since it induces thestandard topology on the set of figures (Beer 1993).
The main contributions of this paper are as follows:
1. We formalize the learning of figures using self-similar sets based on Gold’s learning model towards realizing fully computable binary classification (Section 3). We construct a representational system for learning
using self-similar sets based on the binary representation of real numbers, and show desirable properties ofit (Lemmas 3.2, 3.3, and 3.4).
2. We construct a learnability hierarchy under various learning criteria, summarized in Figure 3 (Section 4
and 5). We consider five criteria for learning: explanatory learning (Section 4.1), consistent learning (Section 4.2), reliable and refutable learning (Section 4.3), and effective learning (Section 5).
3. We show a mathematical connection between learning and fractal geometry by measuring the complexityof learning using the Hausdorff dimension and the VC dimension (Section 6). Specifically, we give a lower
bound on the number of positive examples using the dimensions.
4. We also show a connection between computability of figures studied in computable analysis and learnability of figures discussed in this paper using TTE (Section 7). Learning can be viewed as computablerealization of the identity from the set of figures to the same set equipped with a finer topology.
The rest of the paper is organized as follows: We review related work in comparison to the present workin Section 2. We formalize computable binary classification as learning of figures in Section 3 and analyze
the learnability hierarchy induced by variants of our model in Section 4 and Section 5. The mathematicalconnection between fractal geometry and Gold’s model with the Hausdorff and the VC dimensions is presented
in Section 6 and between computability and learnability of figures in Section 7. Section 8 gives the conclusion.
A preliminary version of this paper was presented at the 21st International Conference on Algorithmic
Learning Theory (Sugiyama et al. 2010). In this paper, formalization of learning in Section 3 is completely
updated for clarity and simplicity, and all theorems and lemmas have formal proofs (they were omitted in theconference paper). Furthermore, discussion about related work in Section 2 and TTE analysis in Section 7 are
new contributions. In addition, several examples and figures are added for readability.

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

5

Table 1 Notation.
N
N+
Q
R
R+
d
Rd
K∗
Id
K, L
#X
F
φ
C
Φ
Σ
Σd
Σ∗
Σ+
Σω
λ
u, v, w
w⊑ p
↑w
⟨·⟩
|w|
diam(k)
p, q
V, W
ρ
ξ, ζ
ξ ⩽ζ
ξ ≡ζ
νQd
νQ
H
H
h
κ
M
σ
Pos(K)
Posk (K)
Neg(K)
dE
dH
H
dimH
dimB
dimS
dimVC

The set of natural numbers including 0
The set of positive natural numbers, i.e., N+ = N \ {0}The set of rational numbers
The set of real numbers
The set of positive real numbers
The number of dimensions (d ∈ N+ )d-dimensional Euclidean space
The set of figures (nonempty compact subsets of Rd )The unit interval [0, 1] × · · · × [0, 1]
Figures (nonempty compact sets)
The number of elements in X
Set of figures
Contraction for real numbers
Finite set of contractions
Contraction for figures
Alphabet
The set of finite sequences whose length are d, i.e., Σ d = {a1 a2 . . . ad | ai ∈ Σ }The set of finite sequences
The set of finite sequences without the empty string λThe set of infinite sequences
The empty string
Finite sequences
w means a prefix of p (w ⊏ p is w ⊑ p and w ̸= p)
The set {p ∈ Σ ω | w ⊏ p}
The tupling function, i.e., ⟨p1 , p2 , . . . , pd ⟩ := p10 p20 . . . pd0 p11 p21 . . . pd1 p12 p22 . . . pd2 . . .
The length of w. If w = ⟨w1 , . . . , wd ⟩ ∈ (Σ d )∗ , |w| = |w1 | =√· · · = |wd |The diameter of the set ρ (w) with |w| = k, i.e., diam(k) = d · 2−kInfinite sequences
Set of finite or infinite sequences
Binary representation
Representation, i.e., a mapping from finite or infinite sequences to some objects
ξ is reducible to ζξ is equivalent to ζ
Representation for rational numbers
Representation for finite sets of rational numbers
The hypothesis space (The set of finite sets of finite sequences)
Hypothesis
Classifier of hypothesis H
The mapping from hypotheses to figures
LearnerPresentation (informant or text)
The set of finite sequences of positive examples of K, i.e., {w | ρ (w) ∩ K ̸= 0}/
The set {w ∈ Pos(K) | |w| = k}
The set of finite sequences of negative examples of K, i.e., {w | ρ (w) ∩ K = 0}/
The Euclidean distance
The Hausdorff distance
The Hausdorff measure
The Hausdorff dimension
The box-counting dimension
The similarity dimension
The VC dimension

2 Related Work
Statistical approaches to machine learning are now achieving great success since they are originally designed
for analyzing observed multivariate data and, to date, many statistical methods have been proposed to treat
continuous objects such as real-valued functions (Bishop 2007). However, most methods pay no attention todiscretization and the finite representation of analog data on a computer. For example, multi-layer perceptrons

6

Mahito Sugiyama et al.

are used to learn real-valued functions, since they can approximate every continuous function arbitrarily andaccurately. However, a perceptron is based on the idea of regulating analog wiring (Rosenblatt 1958), hencesuch learning is not purely computable, i.e., it ignores the gap between analog raw data and digital discretized
data. Furthermore, although several discretization techniques have been proposed by Elomaa and Rousu (2003);
Fayyad and Irani (1993); Gama and Pinto (2006); Kontkanen et al (1997); Li et al (2003); Lin et al (2003);
Liu et al (2002); Skubacz and Hollmén (2000), they treat discretization as data preprocessing for improving theaccuracy or efficiency of machine learning algorithms. The process of discretization is therefore not consideredfrom a computational point of view, and “computability” of machine learning algorithms is not discussed at
sufficient depth.
There are several related articles considering learning under various restrictions in Gold’s model (Goldman
et al 2003), Valiant’s model (Ben-David and Dichterman 1998; Decatur and Gennaro 1995), and other learning context (Khardon and Roth 1999). Moreover, recently learning from partial examples, or examples withmissing information, has attracted much attention in Valiant’s learning model (Michael 2010, 2011). In this paper we also consider learning from examples with missing information, which are truncated finite sequences.
However, our model is different from the cited work, since the “missing information” in this paper corresponds
to measurement error of real-valued data. Our motivation comes from actual measurement/observation of aphysical object, where every datum obtained by an experimental instrument must have some numerical error
in principle (Baird 1994). For example, if we measure the size of a cell by a microscope equipped with micrometers, we cannot know the true value of the size but an approximate value with numerical error, which
depends on the degree of magnification by the micrometers. In this paper we try to treat this process as learning from multivariate data, where an approximate value corresponds to a truncated finite sequence and error
becomes small as the length of the sequence increases. The model of computation for real numbers within
the framework of TTE, as mentioned in the introduction, fits our motivation, and this approach is unique incomputational learning theory.
Self-similar sets can be viewed as a geometric interpretation of languages recognized by ω -automata (Perrin and Pin 2004), first introduced by Büchi (1960), and learning of such languages has been investigated by
De La Higuera and Janodet (2001); Jain et al (2011). Both works focus on learning ω -languages from their prefixes, i.e. texts (positive data), and show several learnable classes. This approach is different from ours since our
motivation is to address computability issues in the field of machine learning from numerical data, and hence
there is a gap between prefixes of ω -languages and positive data for learning in our setting as mentioned in the
introduction. Moreover, we consider learning from both positive and negative data, which is a new approach inthe context of learning of infinite words.
Recently, two of the authors, Sugiyama and Yamamoto (2010), have addressed discretization of real vectors
in a computational approach and proposed a new similarity measure, called coding divergence. It evaluates
the similarity between two sets of real vectors and can be applied to many machine learning tasks such asclassification and clustering. However, it does not address the issue of the learnability or complexity of learningof continuous objects.
3 Formalization of Learning
To analyze binary classification in a computable approach, we first formalize learning of figures based onGold’s model. Specifically, we define targets of learning, representations of classifiers produced by a learning
machine, and a protocol for learning. In the following, let N be the set of natural numbers including 0, Q theset of rational numbers, and R the set of real numbers. The set N+ (resp. R+ ) is the set of positive natural (resp.
real) numbers. The d-fold product of R is denoted by Rd and the set of nonempty compact subsets of Rd isdenoted by K ∗ . Notations used in this paper are summarized in Table 1.
Throughout this paper, we use the binary representation ρ d : (Σ d )ω → I d as the canonical representation
for real numbers. If d = 1, this is defined as follows: Σ = {0, 1} and∞ρ 1 (p) := ∑ pi · 2−(i+1)
i=0

(1)

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

7

for an infinite sequence p = p0 p1 p2 . . . . Note that Σ d denotes the set {a1 a2 . . . ad | ai ∈ Σ } and Σ 1 = Σ . For
example, ρ 1 (0100 . . . ) = 0.25, ρ 1 (1000 . . . ) = 0.5, and so on. Moreover, by using the same symbol ρ , weintroduce a representation ρ 1 : Σ ∗ → K ∗ for finite sequences defined as follows:[]ρ 1 (w) := ρ 1 (↑w) = [ ρ 1 (w000 . . . ), ρ 1 (w111 . . . ) ] = ∑ wi · 2−(i+1) , ∑ wi · 2−(i+1) + 2−|w| ,(2)
where ↑w = {p ∈ Σ ω | w ⊏ p}. For instance, ρ 1 (01) = [0.25, 0.5] and ρ 1 (10) = [0.5, 0.75].
In a d-dimensional space with d > 1, we use the d-dimensional binary representation ρ d : (Σ d )ω → I ddefined in the following manner.
()ρ d (⟨p1 , p2 , . . . , pd ⟩) := ρ 1 (p1 ), ρ 1 (p2 ), . . . , ρ 1 (pd ) ,(3)
where d infinite sequences p1 , p2 , . . . , and pd are concatenated using the tupling function ⟨·⟩ such that
⟨p1 , p2 , . . . , pd ⟩ := p10 p20 . . . pd0 p11 p21 . . . pd1 p12 p22 . . . pd2 . . . .
Similarly, we define a representation ρ d : (Σ d )∗ → K ∗ by

ρ d (⟨w1 , w2 , . . . , wd ⟩) := ρ d (↑⟨w1 , w2 , . . . , wd ⟩),where⟨w1 , w2 , . . . , wd ⟩ := w10 w20 . . . wd0 w11 w21 . . . wd1 . . . w1n w2n . . . wdn .
with |w1 | = |w2 | = · · · = |wd | = n. Note that, for any w = ⟨w1 , . . . , wd ⟩ ∈ (Σ d )∗ , |w1 | = |w2 | = · · · = |wd | always
holds, and we denote the length by |w| in this paper. For a set of finite sequences, i.e., a language L ⊂ (Σ d )∗ ,we defineρ d (L) := { ρ d (w) | w ∈ L } .
We omit the superscript d of ρ d if it is understood from the context.
A target set of learning is a set of figures F ⊆ K ∗ fixed a priori, and one of them is chosen as a target ineach learning phase. A learning machine uses self-similar sets, known as fractals and defined by finite sets ofcontractions. This approach is one of the key ideas in this paper. Here, a contraction is a mapping φ : Rd → Rdsuch that, for all x, y ∈ X, d(φ (x), φ (y)) ⩽ cd(x, y) for some real number c with 0 < c < 1. For a finite set ofcontractions C, a nonempty compact set F satisfying
F=

∪

φ (F)

φ ∈C

is determined uniquely (see (Falconer 2003) for a formal proof). The set F is called the self-similar set of C.
Moreover, if we define a mapping Φ : K ∗ → K ∗ by∪

Φ (K) :=

φ (K)

(4)

φ ∈C

and defineΦ 0 (K) := K and Φ k+1 (K) := Φ (Φ k (K))
for each k ∈ N recursively, then
F=

∞
∩
k=0

Φ k (K)(5)

8

Mahito Sugiyama et al.

for every K ∈ K ∗ such that φ (K) ⊂ K for every φ ∈ C. This means that we have a level-wise construction
algorithm with Φ to obtain the self-similar set F.
A learning machine produces hypotheses, each of which is a finite language and becomes a finite expression of a self-similar set that works as a classifier. Formally, for a finite language H ⊂ (Σ d )∗ , we consider
H 0 , H 1 , H 2 , . . . such that H k is recursively defined as follows:{

H 0 := { λ } ,H k := { ⟨w1 u1 , w2 u2 , . . . , wd ud ⟩ | ⟨w1 , w2 , . . . , wd ⟩ ∈ H k−1 and ⟨u1 , u2 , . . . , ud ⟩ ∈ H } ,We can easily construct a fixed program P(·) which generates H 0 , H 1 , H 2 , . . . when receiving a hypothesis H.
We give the semantics of a hypothesis H by the following equation:

κ (H) :=∞ ∪∩

ρ (H k ).

(6)

k=0

∪

∪

∪

Since ρ (H k ) ⊃ ρ (H k+1 ) holds for all k ∈ N, κ (H) = limk→∞ ρ (H k ). We denote the set of hypotheses{H ⊂ (Σ d )∗ | H is finite} by H and call it the hypothesis space. We use this hypothesis space throughout the
paper. Note that, for a pair of hypotheses H and L, H = L implies κ (H) = κ (L), but the converse may not hold.
Example 3.1 Assume d = 2 and let a hypothesis H be the set {⟨0, 0⟩, ⟨0, 1⟩, ⟨1, 1⟩} = {00, 01, 11}. We have
H 0 = 0,/H 1 = { ⟨0, 0⟩, ⟨0, 1⟩, ⟨1, 1⟩ } = { 00, 01, 11 } ,H 2 = { ⟨00, 00⟩, ⟨00, 01⟩, ⟨01, 01⟩, ⟨00, 10⟩, ⟨00, 11⟩, ⟨01, 11⟩, ⟨10, 10⟩, ⟨10, 11⟩, ⟨11, 11⟩ }= { 0000, 0001, 0011, 0100, 0101, 0111, 1100, 1101, 1111 } , . . .
and the figure κ (H) defined in the equation (6) is the Sierpiński triangle (Figure 2). If we consider the following
three mappings:[ ] [ ]
[ ] [ ]
[ ] [ ]
[ ]
[ ]
[ ]
1 x1
1 x1
1 x1
x1
0
x1
0
x1
1/2
φ1
=
+
, φ2
=
+
, φ3
=
+
,
x2
x2
x2
0
1/2
1/2
2 x2
2 x2
2 x2
the three squares φ1 (I d ), φ2 (I d ), and φ3 (I d ) are exactly the same as ρ (00), ρ (01), and ρ (11), respectively.
Thus each sequence in a hypothesis can be viewed as a representation of one of these squares, which are called
generators for a self-similar set since if we have the initial set I d and generators φ1 (I d ), φ2 (I d ), andφ3 (I d ), we can reproduce the three mappings φ1 , φ2 , and φ3 and construct the self-similar set from them.
Note that there exist infinitely many hypotheses L such that κ (H) = κ (L) and H ̸= L. For example, L = {⟨0, 0⟩,⟨1, 1⟩, ⟨00, 10⟩, ⟨00, 11⟩, ⟨01, 11⟩}.
Lemma 3.2 (Soundness of hypotheses) For every hypothesis H ∈ H , the set κ (H) defined by the equation(6) is a self-similar set.
Proof Let H = {w1 , w2 , . . . , wn }. We can easily check that the set of rectangles ρ (w1 ), ρ (w2 ), . . . , ρ (wn ) is a
generator defined by the mappings φ1 , φ2 , . . . , φn , where each φi maps the unit interval I d to the figure ρ (wi ).
Define Φ and Φ k in the same way as the equations (4) and (5). For each k ∈ N,∪

ρ (H k ) = Φ k (I d )holds. It therefore follows that the set κ (H) is exactly the same as the self-similar set defined by the mappings∪
φ1 , φ2 , . . . , φn , that is, κ (H) = φi (κ (H)) holds.
⊓⊔

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

1

0
1

0

ρ(H0)

1

0
ρ(H4)

1

0

1

0
1

0

ρ(H1)

1

0
ρ(H5)

1

0

1

0
1

0

ρ(H2)

9

1

0
ρ(H6)

1

0

1

0
1

0

ρ(H3)

0
ρ(H7)

1

0

1

Fig. 2 Generation of the Sierpiński triangle from the hypothesis H = {⟨0, 0⟩, ⟨0, 1⟩, ⟨1, 1⟩} (Example 3.1).

To evaluate the “goodness” of each hypothesis, we use the concept of generalization error, which is usuallyused to score the quality of hypotheses in a machine learning context. The generalization error of a hypothesis
H for a target figure K, written by GE(K, H), is defined by the Hausdorff metric dH on the space of figures, i.e.,GE(K, H) := dH (K, κ (H)) = inf { δ | K ⊆ κ (H)δ and κ (H) ⊆ Kδ } ,where Kδ is the δ -neighborhood of K defined byKδ := { x ∈ Rd | dE (x, a) ⩽ δ for some a ∈ K } .
The metric dE is the Euclidean metric such thatvudud (x, a) = t (xi − ai )2
E

∑

i=1

for x = (x1 , . . . , xd ), a = (a1 , . . . , ad ) ∈ Rd . The Hausdorff metric is one of the standard metrics on the spacesince the metric space (K ∗ , dH ) is complete (in the sense of topology) and GE(K, H) = 0 if and only if
K = κ (H) (Beer 1993; Kechris 1995). The topology on K ∗ induced by the Hausdorff metric is called the
Vietoris topology. Since the cardinality of the set of hypotheses H is smaller than that of the set of figures
K ∗ , we often cannot find the exact hypothesis H for a figure K such that GE(K, H) = 0. However, following
the Collage Theorem given by Falconer (2003), we show that the power of representation of hypotheses is still
sufficient, that is, we always can approximate a given figure arbitrarily closely by some hypothesis.
Lemma 3.3 (Representational power of hypotheses) For any δ ∈ R and for every figure K ∈ K ∗ , there
exists a hypothesis H such that GE(K, H) < δ .

10Mahito Sugiyama et al.

Proof Fix a figure K and the parameter δ . Here we denote the diameter of the set ρ (w) with |w| = k by diam(k).
Then we havediam(k) =√d · 2−k .

√√For example, diam(1) = 1/2 and diam(2) = 1/4 if d = 1, and diam(1) = 1/ 2 and diam(2) = 1/ 8 if d = 2.
For k with diam(k) < δ , let
H = { w ∈ (Σ d )∗ | |w| = k and ρ (w) ∩ K ̸= 0/ }.
We can easily check that the diam(k)-neighborhood of K contains κ (H) and the diam(k)-neighborhood ofκ (H) contains K. Therefore we have GE(K, H) < δ .
⊓⊔Moreover, to work as a classifier, every hypothesis H has to be computable, that is, the function h : (Σ d )∗ →{0, 1} such that, for all w ∈ (Σ d )∗ ,{h(w) =

10

if ρ (w) ∩ κ (H) ̸= 0,/
otherwise(7)

should be computable. We say that such h is the classifier of H. The computability of h is not trivial, sincefor a finite sequence w, the two conditions h(w) = 1 and w ∈ H k are not equivalent. Intuitively, this is because
each interval represented by a finite sequence is closed. For example, in the case of Example 3.1, h(10) = 1
because ρ (10) = [0.5, 1] × [0, 0.5] and ρ (10) ∩ κ (H) = {(0.5, 0.5)} ̸= 0/ whereas 10 ∈/ H k for any k ∈ N. Herewe guarantee this property of computability.
Lemma 3.4 (Computability of classifiers) For every hypothesis H ∈ H , the classifier h of H defined by theequation (7) is computable.
Proof First we consider whether or not the boundary of an interval is contained in κ (H). Suppose d = 1 and let
C be a finite set of contractions and F be the self-similar set of C. We have the following property: Let [x, y] =φ1 ◦ φ2 ◦ · · · ◦ φn (I 1 ) for some φ1 , φ2 , . . . , φn ∈ C and let I = φ1′ ◦ φ2′ ◦ · · · ◦ φn′ ′ (I 1 ) for φ1′ , φ2′ , . . . , φn′ ′ ∈ C.
Assume that, if n′ is large enough, there is no such I satisfying x ∈ I and min I < x (resp. max I > y). Then,
we have x ∈ F (resp. y ∈ F) if and only if 0 ∈ φ (I 1 ) (resp. 1 ∈ φ (I 1 )) for some φ ∈ C. This means that′
if [x, y] = ρ (v) with a sequence v ∈ H k (k ∈ N) for a hypothesis H, where there is no sequence v′ ∈ H k with′′′′x ∈ ρ (v ) and min ρ (v ) < x (resp. max ρ (v ) > y) when k is large enough, we have x ∈ κ (H) (resp. y ∈ κ (H))
if and only if u ∈ {0}+ (resp. u ∈ {1}+ ) for some u ∈ H.
We show a pseudo-code of the classifier h in Algorithm 1 and prove that the output of the algorithm is 1
if and only if h(w) = 1, i.e., ρ (w) ∩ κ (H) ̸= 0.
/ In the algorithm, vs and vs denote the previous and subsequentssssbinary sequences of v with |v | = |v | = |v | in the lexicographic order, respectively. For example, if vs = 001,
vs = 000 and vs = 010. Moreover, we use the special symbol ⊥ meaning undefinedness, that is, v = w if andonly if vi = wi for all i ∈ {0, 1, . . . , |v| − 1} with vi ̸= ⊥ and wi ̸= ⊥.
The “if” part: For an input of a finite sequence w and a hypothesis H, if h(w) = 1, there are two possibilities
as follows:
1. For some k ∈ N, there exists v ∈ H k such that w ⊑ v. This is because ρ (w) ⊇ ρ (v) and ρ (v) ∩ κ (H) ̸= 0.
/
2. The above condition does not hold, but ρ (w) ∩ κ (H) ̸= 0.
/
In the first case, the algorithm goes to line 7 and stops with outputting 1. The second case means that thealgorithm uses the function C HECK B OUNDARY. Since h(w) = 1, there should exist a sequence v ∈ H such thatu = aaa . . . a for some u ∈ H, where a is obtained in lines 1–10. C HECK B OUNDARY therefore returns 1.
The “only if” part: In Algorithm 1, if v ∈ H k satisfies conditions in line 6 or line 8, h(w) ∩ κ (H) ̸= 0.
/ Thush(w) = 1 holds.
⊔⊓

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

11

Algorithm 1: Classifier h of hypothesis H
Input: Finite sequence w and hypothesis H
Output: Class label 1 or 0 of w
1: k ← 0
2: repeat3:k ← k+1
4: until minv∈H k |v| > |w|
5: for each v ∈ H k
6:
if w ⊑ v then7:
output 1 and halt
8:
else if C HECK B OUNDARY(w, v, H) = 1 then9:
output 1 and halt
10:
end if
11: end for
12: output 0
function C HECK B OUNDARY(w, v, H)
1: for each s in {1, 2, . . . , d}2:
if ws ⊑ vs then as ← ⊥
3:
else
4:
if ws ⊑ vs then as ← 0
5:else if ws ⊑ vs then as ← 1
6:else return 0
7:
end if8:
end if
9: end for
10: a ← a1 a2 . . . ad // a is a finite sequence whose length is d
11: for each u ∈ H
12:
if u = aaa . . . a then return 1
13: end for
14: return 0

The set {κ (H) | H ⊂ (Σ d )∗ and the classifier h of H is computable} exactly corresponds to an indexed family ofrecursive concepts / languages discussed in computational learning theory (Angluin 1980), which is a common
assumption for learning of languages. On the other hand, there exists some class of figures F ⊆ K ∗ that is not
an indexed family of recursive concepts. This means that, for some figure K, there is no computable classifier
which classifies all data correctly. Therefore we address the problems of both exact and approximate learningof figures to obtain a computable classifier for any target figure.
We consider two types of input data stream, one includes both positive and negative data and the otherincludes only positive data, to analyze learning based on Gold’s learning model. Formally, each training datumis called an example and is defined as a pair (w, l) of a finite sequence w ∈ (Σ d )∗ and a label l ∈ {0, 1}. For atarget figure K,{l=

1 if ρ (w) ∩ K ̸= 0/ (positive example),0 otherwise (negative example).

In the following, for a target figure K, we denote the set of finite sequences of positive examples {w ∈ (Σ d )∗ |
ρ (w) ∩ K ̸= 0}/ by Pos(K) and that of negative examples by Neg(K). Moreover, we denote Posk (K) = {w ∈Pos(K) | |w| = k}. From the geometric nature of figures, we obtain the following monotonicity of examples:12

Mahito Sugiyama et al.

Table 2 Relationship between the conditions for each finite sequence w ∈ Σ ∗ and the standard notation of binary classification.

Target figure K

Hypothesis Hw ∈ Pos(K)(ρ (w) ∩ K ̸= 0)/

w ∈ Neg(K)(ρ (w) ∩ K = 0)/h(w) = 1(ρ (w) ∩ κ (H) ̸= 0)/

True positive

False positive(Type I error)

h(w) = 0(ρ (w) ∩ κ (H) = 0)/

False negative(Type II error)

True negative

Lemma 3.5 (Monotonicity of examples) If (v, 1) is an example of K, then (w, 1) is an example of K for all
prefixes w ⊑ v, and (va, 1) is an example of K for some a ∈ Σ d . If (w, 0) is an example of K, then (wv, 0) is an
example of K for all v ∈ (Σ d )∗ .
Proof From the definition of the representation ρ in the equations (1) and (3), if w ⊑ v, we have ρ (w) ⊇ ρ (v),hence (w, 1) is an example of K. Moreover,∪ρ (va) = ρ (u)a∈Σ dholds. Thus there should exist an example (va, 1) for some a ∈ Σ d . Furthermore, for all v ∈ Σ ∗ , ρ (wv) ⊂ ρ (w).
Therefore if K ∩ ρ (w) = 0,
/ then K ∩ ρ (wv) = 0/ for all v ∈ (Σ d )∗ , and (wv, 0) is an example of K.
⊓⊔
We say that an infinite sequence σ of examples of a figure K is a presentation of K. The ith example is denotedby σ (i − 1), and the set of all examples occurring in σ is denoted by range(σ )3 . The initial segment of σ oflength n, i.e., the sequence σ (0), σ (1), . . . , σ (n−1), is denoted by σ [n−1]. A text of a figure K is a presentation
σ such that
{ w | (w, 1) ∈ range(σ ) } = Pos(K) (= { w | ρ (w) ∩ K ̸= 0/ }),and an informant is a presentation σ such that
{ w | (w, 1) ∈ range(σ ) } = Pos(K) and{ w | (w, 0) ∈ range(σ ) } = Neg(K).
Table 2 shows the relationship between the standard terminology in classification and our definitions. For atarget figure K and the classifier h of a hypothesis H, the set {w ∈ Pos(K) | h(w) = 1} corresponds to true
positive, {w ∈ Neg(K) | h(w) = 1} false positive (type I error), {w ∈ Pos(K) | h(w) = 0} false negative (typeII error), and {w ∈ Neg(K) | h(w) = 0} true negative.
Let h be the classifier of a hypothesis H. We say that the hypothesis H is consistent with an example (w, l)
if l = 1 implies h(w) = 1 and l = 0 implies h(w) = 0, and consistent with a set of examples E if H is consistent
with all examples in E.
A learning machine, called a learner, is a procedure, (i.e. a Turing machine that never halts) that reads apresentation of a target figure from time to time, and outputs hypotheses from time to time. In the following, we
denote a learner by M and an infinite sequence of hypotheses produced by M on the input σ by Mσ , and Mσ (i−1) denotes the ith hypothesis produced by M. Assume that M receives j examples σ (0), σ (1), . . . , σ ( j − 1) so
far when it outputs the ith hypothesis Mσ (i − 1). We do not require the condition i = j, that is, the inequalityi ⩽ j usually holds since M can “wait” until it receives enough examples. We say that an infinite sequence of
hypotheses Mσ converges to a hypothesis H if there exists n ∈ N such that Mσ (i) = H for all i ⩾ n.
3

The reason for this notation is that σ can be viewed as a mapping from N (including 0) to the set of examples.

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

13

FIGEX-INF = FIGCONS-INF = FIGRELEX-INF = FIGEFEX-INF

FIGREFEX-INF

FIGEX-TXT = FIGCONS-TXT
FIGRELEX-TXT

FIGREFEX-TXT
FIGEFEX-TXT = ∅Fig. 3 Learnability hierarchy. For each line, the lower set is a proper subset of the upper set.

4 Exact Learning of Figures
We analyze “exact” learning of figures. This means that, for any target figure K, there should be a hypothesis
H such that the generalization error is zero (i.e., K = κ (H)), hence the classifier h of H can classify all data
correctly with no error, that is, h satisfies the equation (7). The goal is to find such a hypothesis H fromexamples (training data) of K.
In the following two sections (Sections 4 and 5), we follow the standard path of studies in computational
learning theory (Jain et al 1999; Jain 2011; Zeugmann and Zilles 2008), that is, we define learning criteria tounderstand various learning situations and construct a learnability hierarchy under the criteria. We summarize
our results in Fig. 3.

4.1 Explanatory Learning
The most basic learning criterion in Gold’s model is EX-learning (EX means EXplain), i.e., learning in thelimit proposed by Gold (1967). We call these criteria FIGEX-INF- (INF means an informant) and FIGEX-TXTlearning (TXT means a text) for EX-learning from informants and texts, respectively. We introduce these criteria
into the learning of figures, and analyze the learnability of figures.
Definition 4.1 (Explanatory learning) A learner M FIGEX-INF-learns (resp. FIGEX-TXT-learns) a set of figures F ⊆ K ∗ if for all figures K ∈ F and all informants (resp. texts) σ of K, the outputs Mσ converge to ahypothesis H such that GE(K, H) = 0.
For every learning criterion CR introduced in the following, we say that a set of figures F is CR-learnable
if there exists a learner that CR-learns F , and denote by CR the collection of CR-learnable sets of figures
following the standard notation of this field (Jain et al 1999).
First, we consider FIGEX-INF-learning. Informally, a learner can FIGEX-INF-learn a set of figures if it
has the ability to enumerate all hypotheses and to judge whether or not each hypothesis is consistent withthe received examples (Gold 1967). Here we introduce a convenient enumeration of hypotheses. An infinite
sequence of hypotheses H0 , H1 , . . . is called a normal enumeration if { Hi | i ∈ N } = H and, for all i, j ∈ N,
i < j implies
max |v| ⩽ max |w|.
v∈Hi

w∈H j

We can easily implement a procedure that enumerates H through a normal enumeration.

14

Mahito Sugiyama et al.

Procedure 1: Learning procedure that FIGEX-INF-learns κ (H )Input: Informant σ = (w0 , l0 ), (w1 , l1 ), . . . of figure K ∈ κ (H )Output: Infinite sequence of hypotheses Mσ (0), Mσ (1), . . .
1:
2:
3:
4:
5:
6:
7:
8:

i←0
E ← 0/ // E is a set of received examples
repeatread σ (i) and add to E // σ (i) = (wi , li )search the first hypothesis H consistent with E through a normal enumeration
output H // Mσ (i) = Hi ← i+1
until forever

Theorem 4.2 The set of figures κ (H ) = { κ (H) | H ∈ H } is FIGEX-INF-learnable.
Proof This learning can be done by the well-known strategy of identification by enumeration. We show a
pseudo-code of a learner M that FIGEX-INF-learns κ (H ) in Procedure 1. The learner M generates hypotheses through normal enumeration. If M outputs a wrong hypothesis H, there must exist a positive or negative
example that is not consistent with the hypothesis since, for a target figure K∗ ,Pos(K∗ ) ⊖ Pos(κ (H)) ̸= 0/
for every hypothesis H with κ (H) ̸= K∗ , where X ⊖ Y denotes the symmetric difference, i.e., X ⊖ Y = (X ∪Y ) \ (X ∩Y ). Thus the learner M changes the wrong hypothesis and reaches a correct hypothesis H∗ such that
κ (H∗ ) = K∗ in finite time. If M produces a correct hypothesis, it never changes the hypothesis, since every⊓⊔
example is consistent with it. Therefore the learner M FIGEX-INF-learns κ (H ).
Next, we consider FIGEX-TXT-learning. In learning of languages from texts, the necessary and sufficientconditions for learning have been studied in detail by Angluin (1980, 1982); Kobayashi (1996); Lange et al(2008); Motoki et al (1991); Wright (1989), and characterization of learnability using finite tell-tale sets is oneof the crucial results. We adapt these results into the learning of figures and show the FIGEX-TXT-learnability.
Definition 4.3 (Finite tell-tale set, cf. Angluin (1980)) Let F be a set of figures. For a figure K ∈ F , a finite
subset T of the set of positive examples Pos(K) is a finite tell-tale set of K with respect to F if for all figures
L ∈ F , T ⊂ Pos(L) implies Pos(L) ̸⊂ Pos(K) (i.e., L ̸⊂ K). If every figure K ∈ F has finite tell-tale sets withrespect to F , we say that F has finite tell-tale sets.
Theorem 4.4 Let F be a subset of κ (H ). Then F is FIGEX-TXT-learnable if and only if there is a procedure
that, for every figure K ∈ F , enumerates a finite tell-tale set W of K with respect to F .
This theorem can be proved in exactly the same way as that for learning of languages given by Angluin(1980). Note that such procedure does not need to stop. Using this theorem, we show that the set κ (H ) is
not FIGEX-TXT-learnable.
Theorem 4.5 The set κ (H ) does not have finite tell-tale sets.
Proof Fix a figure K = κ (H) ∈ κ (H ), where there exists a pair v, w ∈ H such that ρ (vvv . . . ) ̸= ρ (www . . . ),and fix a finite set T = { w1 , w2 , . . . , wn } contained in Pos(K). Suppose that #Posm (K) > n holds for a natural
number m. For each finite sequence wi , there exists ui ∈ Pos(K) such that |ui | > m, wi ⊏ ui , and ui ∈ H k forsome k. For the figure L = κ (U) with U = {u1 , u2 , . . . , un }, T ⊂ Pos(L) and Pos(L) ⊂ Pos(K) hold. Therefore⊔⊓
K has no finite tell-tale set with respect to κ (H ).
Corollary 4.6 The set of figures κ (H ) is not FIGEX-TXT-learnable.

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

15

In any realistic scenarios of machine learning, however, this set κ (H ) is too large to search for the best
hypothesis since we usually want to obtain a “compact” representation of a target figure. Thus we (implicitly)
have an upper bound on the number of elements in a hypothesis. Here we give a positive result for the above
situation, that is, if we fix the number of elements #H in each hypothesis H a priori, the resulting set of figures
becomes FIGEX-TXT-learnable. Intuitively, this is because if we take k large enough, the set {w ∈ Pos(K) ||w| ⩽ k} becomes a finite tell-tale set of K. Here we denote by Red(H) the hypothesis in which for every pairv, w ∈ H with |v| ⩽ |w|, w is removed if ρ (vvv . . . ) = ρ (www . . . ). For a finite subset of natural numbers N ⊂ N,
we define the set of hypotheses HN := {H ∈ H | #Red(H) ∈ N}.
Theorem 4.7 There exists a procedure that, for all finite subsets N ⊂ N and all figures K ∈ κ (HN ), enumerates
a finite tell-tale set of K with respect to κ (HN ).
Proof First, we assume that N = {1}. It is trivial that there exists a procedure that, for an arbitrary figureK ∈ κ (HN ), enumerates a finite tell-tale set of K with respect to κ (HN ), since we always have L ̸⊂ K for all
pairs of figures K, L ∈ κ (HN ).
Next, fix N ⊂ N with N ̸= {1}. Let us consider the procedure that enumerates elements of the sets
Pos1 (K), Pos2 (K), Pos3 (K), . . . .
We show that this procedure enumerates a finite tell-tale set of K with respect to κ (HN ). It is enough to showthat there exists a natural number m, where there is no hypothesis H such that κ (H) ⊂ K, #H ⩽ max N, andPos(κ (H)) ⊃ Posm (K).
We construct a tree as follows (the similar technique called d-explorer was used by Jain and Sharma(1997)). Each node has a pair (H, w) as its label, where κ (H) ⊂ K and w ∈ Pos(K) \ Pos(κ (H)). The root
node is labeled (0,/ v) with a finite sequence v ∈ Pos(K). The tree is constructed iteratively by adding children
for each node of the tree, whose depth (the length to the root) is at most max N − 1. Let the label of such a nodebe (H, w). For every finite sequence w′ with |w′ | ⩽ |w|, if there exists a finite sequence w′′ satisfying |w′′ | > |w|
and w′′ ∈ Pos(K) \ κ (H ∪ {w′ }), add a child labeled (H ∪ {w′ }, w′′ ) to the node.
The above tree is bounded in depth max N and the number of children for any node is always finite, hence
the number of nodes of the tree is finite. Let m be the length of the longest w such that (H, w) is the label of anode of the tree. Then, we can easily check that there is no hypothesis H ′ such that κ (H ′ ) ⊂ K, #H ′ ⩽ max N,⊔⊓
and Pos(κ (H ′ )) ⊃ Posm (K).
Corollary 4.8 For all finite subsets of natural numbers N ⊂ N, the set of figures κ (HN ) is FIGEX-TXTlearnable.

4.2 Consistent Learning
In a learning process, it is natural that every hypothesis generated by a learner is consistent with the examples
received by it so far. Here we introduce FIGCONS-INF- and FIGCONS-TXT-learning (CONS means CONSistent).
These criteria correspond to CONS-learning that was first introduced by Blum and Blum (1975)4 . This model
was also used (but implicitly) in the Model Inference System (MIS) proposed by Shapiro (1981, 1983), andstudied in the computational learning of formal languages and recursive functions (Jain et al 1999).
Definition 4.9 (Consistent learning) A learner M FIGCONS-INF-learns (resp. FIGCONS-TXT-learns) a set of
figures F ⊆ K ∗ if M FIGEX-INF-learns (resp. FIGEX-TXT-learns) F and for all figures K ∈ F and all informants (resp. texts) σ of K, each hypothesis Mσ (i) is consistent with Ei that is the set of examples received by
M until just before it generates the hypothesis Mσ (i).
Assume that a learner M achieves FIGEX-INF-learning of κ (H ) using Procedure 1. We can easily checkthat M always generates a hypothesis that is consistent with the received examples.
4

Consistency was also studied in the same form by Barzdin (1974).

16

Mahito Sugiyama et al.

Corollary 4.10 FIGEX-INF = FIGCONS-INF.
Suppose that F ⊂ κ (H ) is FIGEX-TXT-learnable. We can construct a learner M in the same way as in the caseof EX-learning of languages from texts (Angluin 1980), where M always outputs a hypothesis that is consistent
with received examples.
Corollary 4.11 FIGEX-TXT = FIGCONS-TXT.

4.3 Reliable and Refutable Learning
In this subsection, we consider target figures that might not be represented exactly by any hypothesis since
there are infinitely many such figures, and if we have no background knowledge, there is no guarantee of theexistence of an exact hypothesis. Thus in practice this approach is more convenient than the explanatory or
consistent learning considered in the previous two subsections.
To realize the above case, we use two concepts, reliability and refutability. The aim of the concepts is tointroduce targets which cannot be exactly represented by any hypotheses. Reliable learning was introduced byBlum and Blum (1975); Minicozzi (1976) and refutable learning by Mukouchi and Arikawa (1995); Sakurai(1991) in computational learning of languages and recursive functions, and developed by Jain et al (2001);
Merkle and Stephan (2003); Mukouchi and Sato (2003). Here we introduce these concepts into the learning of
figures and analyze learnability.
First, we treat reliable learning of figures. Intuitively, reliability requires that an infinite sequence of hypotheses only converges to a correct hypothesis.
Definition 4.12 (Reliable learning) A learner M FIGRELEX-INF-learns (resp. FIGRELEX-TXT-learns) a setof figures F ⊆ K ∗ if M satisfies the following conditions:
1. The learner M FIGEX-INF-learns (resp. FIGEX-TXT-learns) F .
2. For any target figure K ∈ K ∗ and its informants (resp. texts) σ , the infinite sequence of hypotheses Mσdoes not converge to a wrong hypothesis H such that GE(K, κ (H)) ̸= 0.
We analyze reliable learning of figures from informants. Intuitively, for any target figure K ∈ F , if a learnercan judge whether or not the current hypothesis H is consistent with the target, i.e., κ (H) = K or not in finite
time, then the set F is reliably learnable.
Theorem 4.13 FIGEX-INF = FIGRELEX-INF.
Proof The statement FIGRELEX-INF ⊆ FIGEX-INF is trivial, thus we prove FIGEX-INF ⊆ FIGRELEX-INF. Fix
a set of figures F ⊆ κ (H ) with F ∈ FIGEX-INF, and suppose that a learner M FIGEX-INF-learns F using
Procedure 1. The goal is to show that F ∈ FIGRELEX-INF. Assume that a target figure K belongs to K ∗ \ F .
Here we have the following property: for all figures L ∈ F , there must exist a finite sequences w ∈ (Σ d )∗ suchthatw ∈ Pos(K) ⊖ Pos(L),hence for any M’s current hypothesis H, M changes H if it receives a positive or negative example (w, l) suchthat w ∈ Pos(K) ⊖ Pos(κ (H)). This means that an infinite sequence of hypotheses does not converge to any
hypothesis. Thus we have F ∈ FIGRELEX-INF.
⊓⊔
In contrast, we have an interesting result on reliable learning from texts. We show in the following that
FIGEX-TXT ̸= FIGRELEX-TXT holds and that a set of figures F is reliably learnable from positive data only if
any figure K ∈ F is a singleton. Remember that HN denotes the set of hypotheses {H ∈ H | #H ∈ N} for asubset N ⊂ N and, for simplicity, we denote H{n} by Hn for a natural number n ∈ N.
Theorem 4.14 The set of figures κ (HN ) is FIGRELEX-TXT-learnable if and only if N = {1}.

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

17

Proof First we show that the set of figures κ (H1 ) is FIGRELEX-TXT-learnable. From the self-similar sets
property of hypotheses, we have the following: A figure K ∈ κ (H ) is a singleton if and only if K ∈ κ (H1 ).
Let K ∈ K ∗ \ κ (H1 ), and assume that a learner M FIGEX-TXT-learns κ (H1 ). We can naturally suppose that
M changes the current hypothesis H whenever it receives a positive example (w, 1) such that w ̸∈ Pos(κ (H))
without loss of generality. For any hypothesis H ∈ H1 , there exists w ∈ (Σ d )∗ such thatw ∈ Pos(K) \ Pos(κ (H)).
Thus if the learner M receives such a positive example (w, 1), it changes the hypothesis H. This means thatan infinite sequence of hypotheses does not converge to any hypothesis. Therefore κ (H1 ) is FIGRELEX-TXTlearnable.
Next, we prove that κ (Hn ) is not FIGRELEX-TXT-learnable for any n > 1. Fix such n ∈ N with n > 1. We
can easily check that, for a figure K ∈ κ (Hn ) and any of its finite tell-tale sets T with respect to κ (Hn ), there
exists a figure L ∈ K ∗ \ κ (Hn ) such that L ⊂ K and T ⊂ Pos(L). This means that
Pos(L) ⊆ Pos(K) and T ⊆ Pos(L)hold. Thus if a learner M FIGEX-TXT-learns κ (Hn ), Mσ for some presentation σ of such L must converge tosome hypothesis in Hn . Consequently, we have κ (Hn ) ̸∈ FIGRELEX-TXT.
⊓⊔
Corollary 4.15 FIGRELEX-TXT ⊂ FIGEX-TXT.
Sakurai (1991) proved that a set of concepts C is reliably EX-learnable from texts if and only if C contains
no infinite concept (p. 182, Theorem 3.1)5 . However, we have shown that the set κ (H1 ) is FIGRELEX-TXTlearnable, though all figures K ∈ κ (H1 ) correspond to infinite concepts since Pos(K) is infinite for all K ∈κ (H1 ). The monotonicity of the set Pos(K) (Lemma 3.5), which is a constraint naturally derived from thegeometric property of examples, causes this difference.
Next, we extend FIGEX-INF- and FIGEX-TXT-learning by paying our attention to refutability. In refutablelearning, a learner tries to learn figures in the limit, but it understands that it cannot find a correct hypothesis in
finite time, that is, outputs the refutation symbol △ and stops if the target figure is not in the considered space.
Definition 4.16 (Refutable learning) A learner M FIGREFEX-INF-learns (resp. FIGREFEX-TXT-learns) a setof figures F ⊆ K ∗ if M satisfies the following conditions. Here, △ is the refutation symbol.
1. The learner M FIGEX-INF-learns (resp. FIGEX-TXT-learns) F .
2. If K ∈ F , then for all informants (resp. texts) σ of K, Mσ (i) ̸= △ for all i ∈ N.
3. If K ∈ K ∗ \ F , then for all informants (resp. texts) σ of K, there exists m ∈ N such that Mσ (i) ̸= △ for
all i < m, and Mσ (i) = △ for all i ⩾ m.
Conditions 2 and 3 in the above definition mean that a learner M refutes the set F in finite time if and only if
a target figure K ∈ K ∗ \ F . We compare FIGREFEX-INF-learnability with other learning criteria.
Theorem 4.17 FIGREFEX-INF ̸⊆ FIGEX-TXT and FIGEX-TXT ̸⊆ FIGREFEX-INF.
Proof First we consider FIGREFEX-INF ̸⊆ FIGEX-TXT. We show an example of a set of figures F with F ∈FIGREFEX-INF and F ̸∈ FIGEX-TXT in the case of d = 2. Let K0 = κ ({⟨0, 0⟩, ⟨1, 1⟩}), Ki = κ ({⟨w, w⟩ | w ∈Σ i \ {1}i }) for every i ⩾ 1, and F = {Ki | i ∈ N}. Note that K0 is the line y = x and Ki ⊂ K0 for all i ⩾ 1.
We prove that F ∈ FIGREFEX-INF. It is trivial that F ∈ FIGEX-INF, thereby assume that a target figure K ∈K ∗ \F . If a target figure K ⊃ K0 , it is trivial that, for any informant σ of K, the set of examples range(σ [n]) forsome n ∈ N is not consistent with any Ki ∈ F (consider a positive example for a point x ∈ K \ K0 ). Otherwise
if K ⊂ K0 , there should exist a negative example ⟨v, v⟩ ∈ Neg(K). Then we have K ̸= Ki for all i > |v|. Thus alearner can refute candidates {K1 , K2 , . . . , K|v| } in finite time. Therefore F ∈ FIGREFEX-INF holds.
5 The article (Sakurai 1991) is written in Japanese. The same theorem is mentioned by Mukouchi and Arikawa (1995, p. 60,
Theorem 3).

18

Mahito Sugiyama et al.

Next we show that F ̸∈ FIGEX-TXT. Let K0 be the target figure. For any finite set of positive examples
T ⊂ Pos(K0 ), there exists a figure Ki ∈ F such that Ki ⊂ K0 and T is consistent with Ki . Therefore it has no
finite tell-tale set with respect to F and hence F ̸∈ FIGEX-TXT from Theorem 4.4.
Second we check FIGEX-TXT ̸⊆ FIGREFEX-INF. Assume that F = κ (H{1} ) and a target figure K is asingleton {x} with K ̸∈ F . It is clear that, for any informant σ of K and n ∈ N, range(σ [n]) is consistent withsome figure L ∈ F . Thus F ̸∈ FIGREFEX-INF whereas F ∈ FIGEX-TXT.
⊓⊔
Corollary 4.18 FIGRELEX-TXT ̸⊆ FIGREFEX-INF and FIGREFEX-INF ̸⊆ FIGRELEX-TXT.
Note that it is trivial that FIGRELEX-TXT ̸⊆ FIGREFEX-INF since we have κ (H{1} ) ̸∈ FIGREFEX-INF in theabove proof and κ (H{1} ) ∈ FIGRELEX-TXT from Theorem 4.14. Moreover, the condition FIGREFEX-INF ̸⊆FIGRELEX-TXT holds since FIGREFEX-INF ̸⊆ FIGEX-TXT and FIGRELEX-TXT ⊂ FIGEX-TXT. These resultsmean that both FIGREFEX-INF- and FIGRELEX-TXT-learning are difficult, but they are incomparable in termsof learnability. Furthermore, we have the following hierarchy.
Theorem 4.19 FIGREFEX-TXT ̸= 0/ and FIGREFEX-TXT ⊂ FIGREFEX-INF.
Proof Let a set of figures F be a singleton {K} such that K = κ (w) for some w ∈ (Σ d )∗ . Then there exists alearner M that FIGREFEX-TXT-learns F , i.e., F ∈ FIGREFEX-TXT, since all M has to do is to check whether
or not, for a given positive example (v, 1), v ⊑ u for some u ∈ Pos(K) = {x | x ⊑ www . . . }.
Next, let F = {K} such that K = κ (H) with #Red(H) ⩾ 2. We can easily check that F ̸∈ FIGREFEX-TXT
because if a target figure L is a proper subset of K, no learner can refute F in finite time. Conversely, F ∈FIGREFEX-INF since for all L with L ̸= K, there exists an example with which the hypothesis H is not consistent.
⊓⊔
Corollary 4.20 FIGREFEX-TXT ⊂ FIGRELEX-TXT.

5 Effective Learning of Figures
In learning under the proposed criteria, i.e. explanatory, consistent, reliable, and refutable learning, each hypothesis is just considered as exactly “correct” or not, that is, for a target figure K and for a hypothesis H, H
is correct if GE(K, H) = 0 and is not correct if GE(K, H) ̸= 0. Thus we cannot know the rate of convergenceto the target figure and how far it is from the recent hypothesis to the target. It is therefore more useful if we
consider approximate hypotheses by taking various generalization errors into account in the learning process.
We define novel learning criteria, FIGEFEX-INF- and FIGEFEX-TXT-learning (EF means EFfective), tointroduce into learning the concept of effectivity, which has been analyzed in computation of real numbers in
the area of computable analysis (Weihrauch 2000). Intuitively, these criteria guarantee that for any target figure,a generalization error becomes smaller and smaller monotonically and converges to zero. Thus we can know
when the learner learns the target figure “well enough”. Furthermore, if a target figure is learnable in the limit,
then the generalization error goes to zero in finite time.
Definition 5.1 (Effective learning) A learner M FIGEFEX-INF-learns (resp. FIGEFEX-TXT-learns) a set of
figures F ⊆ K ∗ if M satisfies the following conditions:
1. The learner M FIGEX-INF-learns (resp. FIGEX-TXT-learns) F .
2. For an arbitrary target figure K ∈ K ∗ and all informants (resp. texts) σ of K, for all i ∈ N,
GE(K, Mσ (i)) ⩽ 2−i .
This definition is inspired by the Cauchy representation of real numbers (Weihrauch 2000, Definition 4.1.5).
Effective learning is related to monotonic learning (Lange and Zeugmann 1993, 1994; Kinber 1994; Zeugmann et al 1995) originally introduced by Jantke (1991); Wiehagen (1991), since both learning models consider monotonic convergence of hypotheses. In contrast to their approach, where various monotonicity over

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

19

languages was considered, we geometrically measure the generalization error of a hypothesis by the Hausdorff
metric. On the other hand, the effective learning is different from BC-learning developed in the learning of
languages and recursive functions (Jain et al 1999) since BC-learning only guarantees that generalization errors
go to zero in finite time. This means that BC-learning is not effective.
First we show that we can bound the generalization error of the hypothesis H using the diameter diam(k)of the set ρ (w) with |w| = k. Recall that we have√diam(k) = d · 2−k(see Proof of Lemma 3.3). In the following, we denote the set of examples {(w, l) | |w| = k} in σ by E k andcall each example in it a level-k example.
Lemma 5.2 Let σ be an informant of a figure K and H be a hypothesis that is consistent with the set ofexamples E k = {(w, l) | |w| = k}. We have the inequality
GE(K, H) ⩽ diam(k).
Proof Since H is consistent with E k ,{κ (H) ∩ ρ (w)̸= 0/ if (w, 1) ∈ E k ,= 0/ if (w, 0) ∈ E k .

Thus for δ = diam(k), the δ -neighborhood of κ (H) contains K and the δ -neighborhood of K contains κ (H).
It therefore follows that GE(K, H) = dH (K, κ (H)) ⩽ diam(k).
⊓⊔Theorem 5.3 The set of figures κ (H ) is FIGEFEX-INF-learnable.
Proof We show the learner M that FIGEFEX-INF-learns κ (H ) in Procedure 2. We use the function√
g(k) = ⌈ k + log2 d ⌉.
Then for all k ∈ N, we havediam(g(k)) =√d · 2−g(k) ⩽ 2−k .

The learner M stores examples, and when it receives all examples at the level g(k), it outputs a hypothesis.
Every kth hypothesis Mσ (k) is consistent with the set of examples E g(k) . Thus we haveGE(K, Mσ (k)) ⩽ diam(g(k)) ⩽ 2−kfor all k ∈ N from Lemma 5.2.
Assume that K ∈ κ (H ). If M outputs a wrong hypothesis, there must be a positive or negative example thatis not consistent with the hypothesis, and it changes the wrong hypothesis. If it produces a correct hypothesis,
then it never changes the correct hypothesis, since every example is consistent with the hypothesis. Thus there
exists n ∈ N with GE(K, Mσ (i)) = 0 for all i ⩾ n. Therefore M FIGEFEX-INF-learns κ (H ).
⊓⊔Corollary 5.4 FIGEFEX-INF = FIGRELEX-INF = FIGEX-INF.
Thus the learner with Procedure 2 can treat the set of all figures K ∗ as learning targets, since for any figure
K ∈ K ∗ , it can approximate the figure arbitrarily closely using only the figures represented by hypotheses in
the hypothesis space H .
In contrast to FIGEX-TXT-learning, there is no set of figures that is FIGEFEX-TXT-learnable.
Theorem 5.5 FIGEFEX-TXT = 0.
/20

Mahito Sugiyama et al.

Procedure 2: Learning procedure that FIGEFEX-INF-learns κ (H )Input: Informant σ = (w0 , l0 ), (w1 , l1 ), . . . of figure K ∈ κ (H )Output: Infinite sequence of hypotheses Mσ (0), Mσ (1), . . .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

i←0
k←0
E ← 0/ // E is a set of received examples
repeatread σ (i) and add to E // σ (i) = (wi , li )√if E g(k) ⊆ E then // E g(k) = { (w, l) ∈ range(σ ) | |w| = g(k) } and g(k) = ⌈ k + log2 d ⌉search the first H that is consistent with E through a normal enumeration
output P // Mσ (i) = Hk ← k+1
end ifi ← i+1
until forever

Proof We show a counterexample of a target figure which no learner M can approximate effectively. Assume
that d = 2 and a learner M FIGEFEX-TXT-learns a set of figures F ⊆ K ∗ . Let us consider two target figures
K = {(0, 0), (1, 1)} and L = {(0, 0)}. For a text σ of L, for all examples (w, 1) ∈ range(σ ), w ∈ {00}∗ . Since
M FIGEFEX-TXT-learns F , it should output the hypothesis H as Mσ (2) such that GE(L, H) < 1/4. Supposethat M receives n examples before outputting the hypothesis H. Then there exists a presentation τ of the
figure K such√that τ [n − 1] = σ [n − 1], and M outputs the hypothesis H with receiving τ [n − 1]. However,GE(K, H) ⩾ 2 − 1/4 holds from the triangle inequality, contradicting our assumption that M FIGEFEX-TXTlearns F . This proof can be applied for any F ⊆ K ∗ , thereby we have FIGEFEX-TXT = 0.
/⊓⊔
Since FIGREFEX-TXT ̸= 0,/ we have the relation
FIGEFEX-TXT ⊂ FIGREFEX-TXT.
This result means that we cannot learn any figures “effectively” by using only positive examples.

6 Evaluation of Learning Using Dimensions
Here we show a novel mathematical connection between fractal geometry and Gold’s learning under the proposed learning model described in Section 3. More precisely, we bound the number of positive examples, one of
the complexities of learning, using the Hausdorff dimension and the VC dimension. The Hausdorff dimension
is known as the central concept of fractal geometry, which measures the density of figures, and VC dimension
is the central concept of Valiant’s model (PAC learning model) (Kearns and Vazirani 1994), which measuresthe complexity of classes of hypotheses.

6.1 Preliminaries for Dimensions
First we introduce the Hausdorff dimension and related dimensions: the box-counting dimension, the similarity
dimension, and also introduce the VC dimension.
For X ⊆ Rn and s ∈ R with s > 0, define{}Hsδ (X) := inf∑ |U|s U is a δ -cover of X

U∈ U

.

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

21

The s-dimensional Hausdorff measure of X is limδ →0 Hsδ (X), denoted by Hs (X). We say that U is a δ -cover∪of X if U is countable, X ⊆ U∈ U U, and |U| ⩽ δ for all U ∈ U . When we fix a set X and view Hs (X) as afunction with respect to s, it has at most one value where the value Hs (X) changes from ∞ to 0 (Federer 1996).
This value is called the Hausdorff dimension of X. Formally, the Hausdorff dimension of a set X, written as
dimH X, is defined by
dimH X := sup { s | Hs (X) = ∞ } = inf { s ⩾ 0 | Hs (X) = 0 } .
The box-counting dimension, also known as the Minkowski-Bouligand dimension, is one of the mostwidely used dimensions since its mathematical calculation and empirical estimation are relatively easy compared to the Hausdorff dimension. Moreover, if we try to calculate the box-counting dimension, which is given
as the limit of the following equation (8) by decreasing δ , the values obtained often converge to the Hausdorff
dimension at the same time. Thus we can obtain an approximate value of the Hausdorff dimension by an empirical method. Let X be a nonempty bounded subset of Rn and Nδ (X) be the smallest cardinality of a δ -coverof X. The box-counting dimension dimB X of X is defined bydimB X := lim

δ →0

log Nδ (X)− log δ(8)

if this limit exists. Falconer (2003, Equivalent definitions 3.1, P.43) also shows that we have the equivalent
box-counting dimension dimB X if Nδ (K) is the smallest number of cubes of side δ that cover K, or the numberof δ -mesh cubes that intersect K. We have
dimH X ⩽ dimB X
for all X ⊆ Rn .
It is usually difficult to find the Hausdorff dimension of a given set. However, we can obtain the dimensionof a certain class of self-similar sets in the following manner. Let C be a finite set of contractions, and F be theself-similar set of C. The similarity dimension of F, denoted by dimS F, is defined by the equation∑ L(φ )dimS F = 1,

φ ∈C

where L(φ ) is the contractivity factor of φ , which is defined by the infimum of all real numbers c with 0 < c < 1such that d(φ (x), φ (y)) ⩽ cd(x, y) for all x, y ∈ X. We have
dimH F ⩽ dimS F
and if C satisfies the open set condition,
dimH F = dimB F = dimS F(Falconer 2003). Here, a finite set of contractions C satisfies the open set condition if there exists a nonempty
bounded open set O ⊂ Rn such that φ (O) ⊂ O for all φ ∈ C and φ (O) ∩ φ ′ (O) = 0/ for all φ , φ ′ ∈ C with φ ̸= φ ′ .
Intuitively, the Vapnik-Chervonenkis (VC) dimension (Blumer et al 1989; Valiant 1984; Vapnik and Chervonenkis 1971) is a parameter of separability and it gives lower and upper bounds for the sample size in
Valiant’s (PAC) learning model (Kearns and Vazirani 1994). For all R ⊆ H and W ⊆ Σ ∗ , defineΠR (W ) := { Pos(κ (H)) ∩W | H ∈ R } .
If ΠR (W ) = 2W , we say that W is shattered by R. Here the VC dimension of R, denoted by dimVC R, is the
cardinality of the largest set W shattered by R.

22

Mahito Sugiyama et al.

6.2 Measuring the Complexity of Learning with Dimensions
We show that the Hausdorff dimension of a target figure gives a lower bound to the number of positive examples.
√ Remember that Posk (K) = {w ∈ Pos(K) | |w| = k} and the diameter diam(k) of the set ρ (w) with |w| = k
is d2−k . Moreover, the size #{w ∈ (Σ d )∗ | |w| = k} = 2kd for all k ∈ N.
Theorem 6.1 For every figure K ∈ K ∗ and for any s < dimH K, if we take k large enough,#Posk (K) ⩾ 2ks .
Proof Fix s < dimH K. From the definition of the Hausdorff measure,√
Hsdiam(k) (K) ⩽ #Posk (K) · ( d2−k )s√since diam(k) = d2−k . If we take k large enough,√Hsdiam(k) (K) ⩾ ( d)sbecause Hsδ (K) is monotonically increasing with decreasing δ , and goes to ∞. Thus√√√
#Posk (K) ⩾ Hsdiam(k) (K)( d2−k )−s ⩾ ( d)s ( d2−k )−s = 2ks .

⊓⊔Moreover, if a target figure K can be represented by some hypothesis, that is, K ∈ κ (H ), we can use the exact
dimension dimH K as a bound for the number of positive examples #Posk (K).
Theorem 6.2 For every figure K ∈ κ (H ), if we take k large enough,#Posk (K) ⩾ 2k dimH K .
Proof Since the set of contractions encoded by a hypothesis H meets the open set condition, dimH κ (H) =dimB κ (H) = dimS κ (H) holds. Thus we have
dimH K = dimB K = lim

δ →0

log #Posk (K)log Nδ (X)⩽ lim,
k→∞ − log 2−k− log δwhere 2−k is the length of one side of an interval ρ (w) with |w| = k. The above inequality is trivial from thedefinition of the box-counting dimension since Nδ (X) ⩽ #Posk (K). Therefore if we take k large enough,log #Posk (K) ⩾ dimH K · − log 2−k ,#Posk (K) ⩾ 2kdimH K .

⊓⊔Example 6.3 Let us consider the figure K in Example 3.1. It is known that dimH K = log 3/ log 2 = 1.584 . . . .
From Theorem 6.2,
Pos1 (K) ⩾ 2dimH K = 3
holds at level 1 andPos2 (K) ⩾ 4dimH K = 9
holds at level 2. Actually, Pos1 (K) = 4 and Pos2 (K) = 13. Note that K is already covered by 3 and 9 intervals
at level 1 and 2, respectively (Fig. 4).
The VC dimension can also be used to characterize the number of positive examples. Define
H k := { H ∈ H | |w| = k for all w ∈ H } ,and call each hypothesis in the set a level-k hypothesis. We show that the VC dimension of the set of level khypotheses H k is equal to #{ w ∈ (Σ d )∗ | |w| = k } = 2kd .

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

1

0

23

1

0

1

0

0

1

Fig. 4 Positive and negative examples for the Sierpiński triangle at level 1 and 2. White (resp. gray) squares mean positive (resp.
negative) examples.

Lemma 6.4 At each level k, we have dimVC H k = 2kd .
Proof First of all,dimVC H k ⩽ 2kd
kd

is trivial since #H k = 22 . Let Hnk denote the set { H ∈ H k | #Red(H) = n }. For all H ∈ H1k , there exists
w ∈ Pos(κ (H)) such that w ̸∈ Pos(κ (G)) for all G ∈ H1k with H ̸= G. Thus if we assume H1k = {H1 , . . . , H2kd },there exists the set of finite sequences W = {w1 , . . . , w2kd } such that for all i ∈ {1, . . . , 2kd }, wi ∈ Pos(κ (Hi )) andwi ∈/ Pos(κ (H j )) for all j ∈ {1, . . . , 2kd } with i ̸= j. For every pair V,W ⊂ (Σ d )∗ , V ⊂ W implies κ (V ) ⊂ κ (W ).
Therefore the set W is shattered by H k , meaning that we have dimVC H k = 2kd .
⊓⊔Therefore we can rewrite Theorems 6.1 and 6.2 as follows.
Theorem 6.5 For every figure K ∈ K ∗ and for any s < dimH K, if we take k large enough,#Posk (K) ⩾ (dimVC H k )s/d .
Moreover, when K ∈ κ (H ), if we take k large enough,#Posk (K) ⩾ (dimVC H k )dimH K/d .
These results demonstrate a relationship among the complexities of learning figures (numbers of positive examples), classes of hypotheses (VC dimension), and target figures (Hausdorff dimension).

6.3 Learning the Box-Counting Dimension through Effective Learning
One may think that FIGEFEX-INF-learning can be achieved without the proposed hypothesis space. For instance, if a learner just outputs figures represented by a set of received positive examples, the generalization
error becomes smaller and smaller. Here we show that one “quality” of a target figure, the box-counting dimension, is also learned in FIGEFEX-INF-learning, whereas if a learner outputs figures represented by a setof received positive examples, the box-counting dimension (and also the Hausdorff dimension) of any figure
represented by a hypothesis is always d.
Recall that for all hypotheses H ∈ H , dimH κ (H) = dimB κ (H) = dimS κ (H), since the set of contractions
encoded by the hypothesis H meets the open set condition.
Theorem 6.6 Assume that a learner M FIGEFEX-INF-learns κ (H ). For every target figure K ∈ K ∗ ,lim dimB κ (Mσ (k)) = dimB K.

k→∞

24

Mahito Sugiyama et al.

Proof First, we assume that a target figure K ∈ κ (H ). For every informant σ of K, Mσ converges to a hypothesis H with κ (H) = K. Thuslim dimB κ (Mσ (k)) = dimB K = dimH K.

k→∞Next, we assume K ∈ K ∗ \ κ (H ). Since GE(K, Mσ (i)) ⩽ 2−i holds for every i ∈ N, for each k ∈ N wehave some i ⩾ k such that the hypothesis Mσ (i) is consistent with the set of level-k examples E k = {(w, l) ∈range(σ ) | |w| = k}. Thus
log #Posk (K).
k→∞ − log 2−kdimB κ (Mσ (i)) = lim

Falconer (2003, Equivalent definitions 3.1, P.43) shows that the box-counting dimension dimB K is defined
equivalently bydimB K = limk→∞log #Posk (K).
− log 2−kTherefore from the definition of the box-counting dimension, we havelog #Posk (K)= dimB K.
k→∞ − log 2−klim dimB κ (Mσ (i)) = lim

i→∞

⊓
⊔

7 Computational Interpretation of Learning
Recently, the concept of “computability” for continuous objects has been introduced in the framework of Type2 Theory of Effectivity (TTE) (Schröder 2002b; Weihrauch 2000, 2008; Weihrauch and Grubba 2009; Tavanaand Weihrauch 2011), where we treat an uncountable set X as objects for computing through infinite sequences
over a given alphabet Σ . Using the framework, we analyze our learning model from the computational pointof view. Some studies by de Brecht and Yamamoto (2009); de Brecht (2010) have already demonstrated aclose connection between TTE and Gold’s model, and our analysis becomes an instance and extension of theiranalysis.

7.1 Preliminaries for Type-2 Theory of Effectivity
We prepare mathematical notations for TTE. In the following in this section, we assume Σ = {0, 1, [, ], ∥, ♢}. A
partial (resp. total) function g from a set A to a set B is denoted by g :⊆ A → B (resp. g : A → B). A representationof a set X is a surjection ξ :⊆ C → X, where C is Σ ∗ or Σ ω . We see p ∈ dom(ξ ) as a name of the encoded
element ξ (p).
Computability of string functions f :⊆ X → Y , where X and Y are Σ ∗ or Σ ω , is defined via a Type-2
machine, which is a usual Turing machine with one-way input tapes, some work tapes, and a one-way output
tape (Weihrauch 2000). The function fM :⊆ X → Y computed by a Type-2 machine M is defined as follows:
When Y is Σ ∗ , fM (p) := q if M with input p halts with q on the output tape, and when Y is Σ ω , fM (p) := q if
M with input p writes step by step q onto the output tape. We say that a function f :⊆ C → D is computable
if there is a Type-2 machine that computes f , and a finite or infinite sequence p is computable if the constantfunction f which outputs p is computable. A Type-2 machine never changes symbols that have already been
written onto the output tape, thus each prefix of the output depends only on a prefix of the input.
By treating a Type-2 machine as a translator between names of some objects, a hierarchy of representations
is introduced. A representation ξ is reducible to ζ , denoted by ξ ⩽ ζ , if there exists a computable function fsuch that ξ (p) = ζ ( f (p)) for all p ∈ dom(ξ ). Two representations ξ and ζ are equivalent, denoted by ξ ≡ ζ ,if both ξ ⩽ ζ and ζ ⩽ ξ hold. As usual, ξ < ζ means ξ ⩽ ζ and not ζ ⩽ ξ .
Computability for functions is defined through representations and computability of string functions.

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

25

Definition 7.1 Let ξ and ζ be representations of X and Y , respectively. An element x ∈ X is ξ -computable if
there is some computable p such that ξ (p) = x. A function f :⊆ X → Y is (ξ , ζ )-computable if there is somecomputable function g such thatf ◦ ξ (p) = ζ ◦ g(p)for all p ∈ dom(ξ ). This g is called a (ξ , ζ )-realization of f .
Thus the abstract function f is “realized” by the concrete function (Type-2 machine) g through the two representations ξ and ζ .
Various representations of the set of nonempty compact sets K ∗ are well studied by Brattka and Weihrauch(1999); Brattka and Presser (2003). Let
Q = { A ⊂ Qd | A is finite and nonempty }and define a representation νQ :⊆ Σ ∗ → Q byνQ ([w0 ∥w1 ∥ . . . ∥wn ]) := { νQd (w0 ), . . . , νQd (wn ) } ,where νQd :⊆ (Σ d )∗ → Qd is the standard binary notation of rational numbers defined by|w1 |−1|w2 |−1|wd |−1

i=0

i=0

i=0

νQd (⟨w1 , w2 , . . . , wd ⟩) :=  ∑ w1i · 2−(i+1) , ∑ w2i · 2−(i+1) , . . . ,∑ wdi · 2−(i+1) and “[”, “]”, and “∥” are special symbols used to separate two finite sequences. For a finite set of finite sequences{w0 , . . . , wm }, for convenience we introduce the mapping ι which translates the set into a finite sequence defined by ι (w0 , . . . , wm ) := [w0 ∥ . . . ∥wm ]. Note that νQd (⟨w1 , . . . , wd ⟩) = (min ρ (w1 ), . . . , min ρ (wd )) for our
representation ρ introduced in equation (2). The standard representation of the topological space (K ∗ , dH ),given by Brattka and Weihrauch (1999, Definition 4.8), is defined in the following manner.
Definition 7.2 (Standard representation of figures) Define the representation κH :⊆ Σ ω → K ∗ of figuresby κH (p) = K if p = w0 ♢w1 ♢w2 ♢ . . . ,dH (K, νQ (wi )) < 2−ifor each i ∈ N, and limi→∞ νQ (wi ) = K, where ♢ denotes a separator of two finite sequences.
This representation κH is known to be an admissible representation of the space (K ∗ , dH ), which is the key
concept in TTE (Schröder 2002b; Weihrauch 2000), and is also known as the Σ 01 -admissible representation
proposed by de Brecht and Yamamoto (2009).

7.2 Computability and Learnability of Figures
First, we show computability of figures in κ (H ).
Theorem 7.3 For every figure K ∈ κ (H ), K is κH -computable.
Proof It is enough to prove that there exists a computable function f such that κ (H) = κH ( f (H)) for all
H ∈ H . Fix a hypothesis H ∈ H such that κ (H) = K. For all k ∈ N and for Hk defined by
Hk := {w ∈ (Σ d )∗ | w ⊑ v with v ∈ H m for some m, and |w| = k},we can easily check thatdH (K, νQ (ι (Hk ))) < diam(k) =√d · 2−k .

26Moreover, for each k,

Mahito Sugiyama et al.

√d · 2−g(k) < 2−k , where√g(k) = ⌈ k + log2 d ⌉.

Therefore there exists a computable function f which translates H into a representation of K given as follows:f (H) = p with p = w0 ♢w1 ♢ . . . such that ι (Hg(k) ) = wk for all k ∈ N.
⊓⊔
Thus a hypothesis H can be viewed as a “program” of a Type-2 machine that produces a κH -representation of
the figure κ (H).
Both informants and texts are also representations (in the sense of TTE) of compact sets. Define the mapping ηINF by ηINF (σ ) := K for every K ∈ K ∗ and informant σ of K, and the mapping ηTXT by ηTXT (σ ) := K
for every K ∈ K ∗ and text σ of K. Trivially ηINF < ηTXT holds, that is, some Type-2 machine can translate ηINF to ηTXT , but no machine can translate ηTXT to ηINF . Moreover, we have the following hierarchy ofrepresentations.
Lemma 7.4 ηINF < κH , ηTXT ̸⩽ κH , and κH ̸⩽ ηTXT .
Proof First we prove ηINF ⩽ κH , that is, there is some computable function f such that ηINF (σ ) = κH ( f (σ )).
Fix a figure K and its informant σ ∈ dom(ηINF ). For all k ∈ N, we have√dH (K, Posk (K)) ⩽ diam(k) = d · 2−k√

d · 2−g(k) < 2−k , where√g(k) = ⌈ k + log2 d ⌉.

and Posk (K) can be obtained from σ . Moreover, for each k,

Therefore there exists a computable function f that translates σ into a representation of K as follows: f (σ ) = p,
where p = w0 ♢w1 ♢ . . . such that wk = ι (Posg(k) (K)) for all k ∈ N.
Second, we prove ηTXT ̸⩽ κH . Assume that the opposite, ηTXT ⩽ κH holds. Then there exists a computablefunction f such that ηTXT (σ ) = κH ( f (σ )) for every figure K ∈ K ∗ . Fix a figure K and its text σ ∈ dom(ηTXT ).
This means that for any small ε ∈ R, f can pick up finite sequences w1 , w2 , . . . , wn from Pos(K) such thatdH (K, νQ (ι (w1 , w2 , . . . , wn ))) ⩽ ε . However, if such f exists, we can easily check that {K} ∈ FIGEFEX-TXT,
contradicting to our result (Theorem 5.5). It follows that ηTXT ̸⩽ κH .
Third, we prove κH ̸⩽ ηINF and κH ̸⩽ ηTXT . There is a figure K such that K ∩ ρ (w) = {x} for some w ∈ Σ ∗ ,i.e., K and ρ (w) intersect in only one point x. Such a w must be in σ as a positive example, that is, w ∈ Pos(K).
However, a representation of K can be constructed without w. There exists an infinite sequence p ∈ κH with
p = w0 ♢w1 ♢ . . . such that x ̸∈ νQ (wk ) for all k ∈ N. Thus, if there exists a computable f which outputs an
example (w, 1) from such a sequence after only seeing w0 ♢w1 ♢ . . . ♢wn , one can extend the sequence in sucha way for some figure L with w ̸∈ Pos(L), in contradiction to the reduction. Therefore there is no computablefunction that outputs an example (w, 1) from p, meaning that κH ̸⩽ ηINF and κH ̸⩽ ηTXT .
⊓⊔Here we interpret learning of figures as computation based on TTE. If we see the output of a learner, i.e.,
an infinite sequence of hypotheses, as an infinite sequence encoding a figure, the learner can be viewed as atranslator of codes of figures. Naturally, we can assume that the hypothesis space H is a discrete topologicalspace, that is, every hypothesis H ∈ H is isolated and is an open set itself. Define the mapping limH : H ω →H , where H ω is the set of infinite sequences of hypotheses in H , by limH (τ ) := H if τ is an infinite
sequence of hypotheses that converges to H, i.e., there exists n ∈ N such that τ (i) = τ (n) for all i ⩾ n. This
coincides with the naı̈ve Cauchy representation given by Weihrauch (2000) and Σ 02 -admissible representationof hypotheses introduced by de Brecht and Yamamoto (2009). For any set F ⊆ K ∗ , let FD denote the space
F equipped with the discrete topology, that is, every subset of F is open, and the mapping idF : F → FD
be the identity on F . The computability of this identity is not trivial, since the topology of FD is finer thanthat of F . Intuitively, this means that FD is more informative than F . We can interpret learnability of F as
computability of the identity idF . The results in the following are summarized in Figure 5.

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

INF(F )

ηINF

M

/



Hω

F


idF

/

κ ◦ limH

FD

INF(K ∗ )

ηINF

M

/

Hω



K∗


id

27

/

γ ≡ κHK∗

Fig. 5 The commutative diagram representing FIGEX-INF-learning of F (left), and FIGEFEX-INF-learning of F (both left andright). In this diagram, INF(F ) denotes the set of informants of K ∈ F .

Theorem 7.5 A set F ⊆ K ∗ is FIGEX-INF-learnable (resp. FIGEX-TXT-learnable) if and only if the identity
idF is (ηINF , κ ◦ limH )-computable (resp. (ηTXT , κ ◦ limH )-computable).
Proof We only prove the case of FIGEX-INF-learning, since we can prove the case of FIGEX-TXT-learning inexactly the same way.
The “only if” part: There is a learner M that FIGEX-INF-learns F , hence for all K ∈ F and all σ ∈dom(ηINF ), Mσ converges to a hypothesis H ∈ H such that κ (H) = K. Thus
idF ◦ ηINF (σ ) = κ ◦ limH (Mσ ),(9)and this means that idF is (ηINF , κ ◦ limH )-computable.
The “if” part: For some M, the above equation (9) holds for all σ ∈ dom(ηINF ). This means that M is alearner that FIGEX-INF-learns F .
⊓⊔Here we consider two more learning criteria, FIGFIN-INF- and FIGFIN-TXT-learning, where the learner generates only one correct hypothesis and halts. This learning corresponds to finite learning or one shot learning
introduced by Gold (1967); Trakhtenbrot and Barzdin (1970) and it is a special case of learning with a boundof mind change complexity, the number of changes of hypothesis, introduced by Freivalds and Smith (1993)
and used to measure the complexity of learning classes (Jain et al 1999). We obtain the following theorem.
Theorem 7.6 A set F ⊆ K ∗ is FIGFIN-INF-learnable (resp. FIGFIN-TXT-learnable) if and only if the identity
idF is (ηINF , κ )-computable (resp. (ηTXT , κ )-computable).
Proof We only prove the case of FIGFIN-INF-learning, since we can prove the case of FIGFIN-TXT-learning inexactly the same way.
The “only if” part: There is a learner M that FIGFIN-INF-learns F , hence for all K ∈ F and all σ ∈dom(ηINF ) of K, we can assume that Mσ = H such that κ (H) = K. Thus we haveidF ◦ ηINF (σ ) = κ (Mσ ).

(10)This means that idF is (ηINF , κ )-computable.
The “if” part: For some M, the above equation (10) holds for all σ ∈ dom(ηINF ). This means that M is alearner that FIGFIN-INF-learns F .
⊓⊔Finally, we show a connection between effective learning of figures and the computability of figures. Since
FIGEFEX-TXT = 0/ (Theorem 5.5), we only treat effective learning from informants. We define the representation γ :⊆ H ω → K ∗ by γ (p) := K if p = H0 , H1 , . . . such that Hi ∈ H and dH (K, κ (Hi )) ⩽ 2−i for all i ∈ N.
Lemma 7.7 γ ≡ κH .

28

Mahito Sugiyama et al.

Proof First we prove γ ⩽ κH . For the function g : N → R such that√g(i) = ⌈ i + log2 d ⌉,√we have diam(g(i)) = d · 2−g(i) ⩽ 2−i for all i ∈ N. Thus there exists a computable function f such that, forall p ∈ dom(γ ), f (p) is a representation of κH since, for an infinite sequence of hypotheses p = H0 , H1 , . . . , allg(i)f has to do is to generate an infinite sequence q = w0 ♢w1 ♢w2 ♢ . . . such that wi = ι (Hg(i) ) for all i ∈ N, which
results in√
dH (K, νQ (wi )) ⩽ diam(g(i)) = d · 2−g(i) ⩽ 2−ifor all i ∈ N.
Next, we prove κH ⩽ γ . Fix q ∈ dom(κH ) with q = w0 ♢w1 ♢ . . . . For each i ∈ N, let wi = ι (wi,0 , wi,1 , . . .
, wi,n ). Then the set {wi,0 , . . . , wi,n }, which we denote Hi , becomes a hypothesis. From the definition of κH ,dH (K, κ (Hi )) ⩽ 2−iholds for all i ∈ N. This means that, for the sequence p = w0 , w1 , . . . , γ (p) = K. We therefore have γ ≡ κH .

⊔⊓By using this lemma, we interpret effective learning of figures as the computability of two identities (Fig. 5).
Theorem 7.8 A set F ⊆ K ∗ is FIGEFEX-INF-learnable if and only if there exists a computable function fsuch that f is a (ηINF , κ ◦ limH )-realization of the identity idF , and f is also a (ηINF , γ )-realization of theidentity id : K ∗ → K ∗ .
Proof We prove the latter half of the theorem, since the former part can be proved exactly as for Theorem 7.5.
The “only if” part: We assume that a learner M FIGEFEX-INF-learns F . For all K ∈ K ∗ and all σ ∈dom(ηINF ),id ◦ ηINF (σ ) = γ (Mσ )holds since the identity id is (ηINF , γ )-computable.
The “if” part: For some M, id ◦ ηINF (σ ) = γ (Mσ ) for all σ ∈ dom(ηINF ). It follows that M is a learner that
FIGEFEX-INF-learns F .
⊓⊔Thus in FIGEFEX-INF- and FIGEFEX-TXT-learning of a set of figures F , a learner M outputs a hypothesis H
with κ (H) = K in finite time if K ∈ F , and M outputs the “standard” representation of K if K ∈ K ∗ \ F since
we prove that γ ≡ κH in Lemma 7.7. Informally, this means that there is not too much loss of information of
figures even if they are not explanatorily learnable.
8 Conclusion
We have proposed the learning of figures using self-similar sets based on Gold’s learning model towards a
new theoretical framework of binary classification focusing on computability, and demonstrated a learnability
hierarchy under various learning criteria (Fig. 3). The key to the computable approach is the amalgamation of
discretization of data and the learning process. We showed a novel mathematical connection between fractal
geometry and Gold’s model by measuring the lower bound of the size of training data with the Hausdorff
dimension and the VC dimension. Furthermore, we analyzed our learning model using TTE (Type-2 Theory of
Effectivity) and presented several mathematical connections between computability and learnability.
Many recent methods in machine learning are based on a statistical approach (Bishop 2007). The reason
is that many data in the real world are in analog (real-valued) form, and the statistical approach can treat suchanalog data directly in theory. However, all learning methods are performed on computers. This means that all
machine learning algorithms actually treat discretized digital data and, now, most research pays no attention to
the gap between analog and digital data. In this paper we have proposed a novel and completely computablelearning method for analog data, and have analyzed the method precisely. This work provides a theoreticalfoundation for computable learning from analog data, such as classification, regression, and clustering.

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

29

Acknowledgements The authors sincerely thank to the editor and anonymous reviewers for their lots of useful comments andsuggestions which have led to invaluable improvements of this paper. This work was partly supported by Grant-in-Aid for Scientific
Research (A) 22240010 and for JSPS Fellows 22·5714.

References
Angluin D (1980) Inductive inference of formal languages from positive data. Information and Control 45(2):117–135
Angluin D (1982) Inference of reversible languages. Journal of the ACM 29(3):741–765
Apsı̄tis K, Arikawa S, Freivalds R, Hirowatari E, Smith CH (1999) On the inductive inference of recursive real-valued functions.
Theoretical Computer Science 219(1–2):3–12
Baird DC (1994) Experimentation: An Introduction to Measurement Theory and Experiment Design, 3rd edn. Benjamin Cummings
Barnsley MF (1993) Fractals Everywhere, 2nd edn. Morgan Kaufmann
Barzdin YM (1974) Inductive inference of automata, languages and programs (in Russian). In: Proceedings of the International
Congress of Mathematicians, vol 2, pp 455–460
Baum EB, Haussler D (1989) What size net gives valid generalization? Neural computation 1(1):151–160
Beer GA (1993) Topologies on Closed and Closed Convex Sets, Mathematics and Its Applications, vol 268. Kluwer Academic
Publishers
Ben-David S, Dichterman E (1998) Learning with restricted focus of attention. Journal of Computer and System Sciences
56(3):277–298
Bishop C (2007) Pattern Recognition and Machine Learning (Information Science and Statistics). Springer
Blum L, Blum M (1975) Toward a mathematical theory of inductive inference. Information and Control 28(2):125–155
Blumer A, Ehrenfeucht A, Haussler D, Warmuth MK (1989) Learnability and the Vapnik-Chervonenkis dimension. Journal of the
ACM 36(4):929–965
Brattka V, Presser G (2003) Computability on subsets of metric spaces. Theoretical Computer Science 305(1-3):43–76
Brattka V, Weihrauch K (1999) Computability on subsets of Euclidean space I: Closed and compact subsets. Theoretical Computer
Science 219(1-2):65–93
de Brecht M (2010) Topological and algebraic aspects of algorithmic learning theory. PhD thesis, Graduate School of Informatics,
Kyoto University
de Brecht M, Yamamoto A (2009) Σα0 -admissible representations. In: Proceedings of the 6th International Conference on Computability and Complexity in Analysis
Büchi JR (1960) On a decision method in restricted second order arithmetic. In: Proceedings of International Congress on Logic,
Methodology and Philosophy of Science, pp 1–12
De La Higuera C, Janodet JC (2001) Inference of ω -languages from prefixes. In: Abe N, Khardon R, Zeugmann T (eds) Algorithmic
Learning Theory, Springer, Lecture Notes in Computer Science, vol 2225, pp 364–377
Decatur SE, Gennaro R (1995) On learning from noisy and incomplete examples. In: Proceedings of the 8th Annual Conference on
Computational Learning Theory, pp 353–360
Ehrenfeucht A, Haussler D, Kearns M, Valiant L (1989) A general lower bound on the number of examples needed for learning.
Information and Computation 82(3):247–261
Elomaa T, Rousu J (2003) Necessary and sufficient pre-processing in numerical range discretization. Knowledge and Information
Systems 5(2):162–182
Falconer K (2003) Fractal Geometry: Mathematical Foundations and Applications. Wiley
Fayyad UM, Irani KB (1993) Multi-interval discretization of continuous-valued attributes for classification learning. In: Proceedingsof the 13th International Joint Conference on Artificial Intelligence, pp 1022–1029
Federer H (1996) Geometric Measure Theory. Springer
Freivalds R, Smith CH (1993) On the role of procrastination in machine learning. Information and Computation 107(2):237–271
Gama J, Pinto C (2006) Discretization from data streams: applications to histograms and data mining. In: Proceedings of the 21st
Annual ACM Symposium on Applied Computing, pp 23–27
Gold EM (1965) Limiting recursion. The Journal of Symbolic Logic 30(1):28–48
Gold EM (1967) Language identification in the limit. Information and Control 10(5):447–474
Goldman SA, Kwek SS, Scott SD (2003) Learning from examples with unspecified attribute values. Information and Computation
180(2):82–100
Hirowatari E, Arikawa S (1997) Inferability of recursive real-valued functions. In: Li M, Maruoka A (eds) Algorithmic Learning
Theory, Springer, Lecture Notes in Computer Science, vol 1316, pp 18–31
Hirowatari E, Arikawa S (2001) A comparison of identification criteria for inductive inference of recursive real-valued functions.
Theoretical Computer Science 268(2):351–366
Hirowatari E, Hirata K, Miyahara T, Arikawa S (2003) Criteria for inductive inference with mind changes and anomalies of recursive
real-valued functions. IEICE Transactions on Information and Systems 86(2):219–227
Hirowatari E, Hirata K, Miyahara T, Arikawa S (2005) Refutability and reliability for inductive inference of recursive real-valued
functions. IPSJ Digital Courier 1:141–152
Hirowatari E, Hirata K, Miyahara T (2006) Prediction of recursive real-valued functions from finite examples. In: Washio T, Sakurai
A, Nakajima K, Takeda H, Tojo S, Yokoo M (eds) New Frontiers in Artificial Intelligence, Springer, Lecture Notes in Computer
Science, vol 4012, pp 224–234

30

Mahito Sugiyama et al.

Jain S, Sharma A (1997) Elementary formal systems, intrinsic complexity, and procrastination. Information and Computation
132(1):65–84
Jain S (2011) Hypothesis spaces for learning. Information and Computation 209(3):513–527
Jain S, Osherson D, Royer JS, Sharma A (1999) Systems That Learn, 2nd edn. The MIT Press
Jain S, Kinber E, Wiehagen R, Zeugmann T (2001) Learning recursive functions refutably. In: Abe N, Khardon R, Zeugmann T(eds) Algorithmic Learning Theory, Lecture Notes in Computer Science, vol 2225, pp 283–298
Jain S, Luo Q, Semukhin P, Stephan F (2011) Uncountable automatic classes and learning. Theoretical Computer Science412(19):1805–1820
Jantke KP (1991) Monotonic and non-monotonic inductive inference. New Generation Computing 8(4):349–360
Kearns MJ, Vazirani UV (1994) An Introduction to Computational Learning Theory. The MIT Press
Kechris AS (1995) Classical Descriptive Set Theory. Springer
Khardon R, Roth D (1999) Learning to reason with a restricted view. Machine Learning 35(2):95–116
Kinber E (1994) Monotonicity versus efficiency for learning languages from texts. In: Algorithmic Learning Theory, Springer,
Lecture Notes in Computer Science, vol 872, pp 395–406
Kobayashi S (1996) Approximate identification, finite elasticity and lattice structure of hypothesis space. Tech. Rep. CSIM 96-04,
Department of Computer Science and Information Mathematics, The University of Electro-Communications
Kontkanen P, Myllymäki P, Silander T, Tirri H (1997) A bayesian approach to discretization. In: Proceedings of the European
Symposium on Intelligent Techniques, pp 265–268
Lange S, Zeugmann T (1993) Monotonic versus non-monotonic language learning. In: Nonmonotonic and Inductive Logic,
Springer, Lecture Notes in Computer Science, vol 659, pp 254–269
Lange S, Zeugmann T (1994) Characterization of language learning front informant under various monotonicity constraints. Journalof Experimental & Theoretical Artificial Intelligence 6(1):73–94
Lange S, Zeugmann T, Zilles S (2008) Learning indexed families of recursive languages from positive data: A survey. TheoreticalComputer Science 397(1–3):194–232
Li M, Chen X, Li X, Ma B, Vitányi P (2003) The similarity metric. In: Proceedings of the 14th Annual ACM-SIAM Symposium
on Discrete Algorithms, pp 863–872
Lin J, Keogh E, Lonardi S, Chiu B (2003) A symbolic representation of time series, with implications for streaming algorithms. In:
Proceedings of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pp 1–11
Liu H, Hussain F, Tan CL, Dash M (2002) Discretization: An enabling technique. Data Mining and Knowledge Discovery 6(4):393–
423
Long PM, Tan L (1998) PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples.
Machine Learning 30(1):7–21
Mandelbrot BB (1982) The Fractal Geometry of Nature. W. H. Freeman
Merkle W, Stephan F (2003) Refuting learning revisited. Theoretical Computer Science 298(1):145–177
Michael L (2010) Partial observability and learnability. Artificial Intelligence 174(11):639–669
Michael L (2011) Missing information impediments to learnability. In: 24th Annual Conference on Learning Theory, pp 1–2
Minicozzi E (1976) Some natural properties of strong-identification in inductive inference. Theoretical Computer Science 2(3):345–
360
Motoki T, Shinohara T, Wright K (1991) The correct definition of finite elasticity: Corrigendum to identification of unions. In:
Proceedings of the 4th Annual Workshop on Computational Learning Theory, p 375
Mukouchi Y, Arikawa S (1995) Towards a mathematical theory of machine discovery from facts. Theoretical Computer Science
137(1):53–84
Mukouchi Y, Sato M (2003) Refutable language learning with a neighbor system. Theoretical Computer Science 298(1):89–110
Müller N (2001) The iRRAM: Exact arithmetic in C++. In: Blanck J, Brattka V, Hertling P (eds) Computability and Complexity inAnalysis, Springer, Lecture Notes in Computer Science, vol 2064, pp 222–252
Perrin D, Pin JÉ (2004) Infinite words. Elsevier
Rosenblatt F (1958) The perceptron: A probabilistic model for information storage and organization in the brain. Psychological
Review 65(6):386–408
Sakurai A (1991) Inductive inference of formal languages from positive data enumerated primitive-recursively. In: Algorithmic
Learning Theory, JSAI, pp 73–83
Schröder M (2002a) Admissible representations for continuous computations. PhD thesis, dem Fachbereich Informatik, der FernUniversit at – Gesamthochschule in Hagen
Schröder M (2002b) Extended admissibility. Theoretical Computer Science 284(2):519–538
Shapiro EY (1981) Inductive inference of theories from facts. Tech. rep., Department of Computer Science, Yale University
Shapiro EY (1983) Algorithmic Program Debugging. The MIT Press
Skubacz M, Hollmén J (2000) Quantization of continuous input variables for binary classification. In: Intelligent Data Engineeringand Automated Learning — IDEAL 2000. Data Mining, Financial Engineering, and Intelligent Agents, Springer, Lecture Notes
in Computer Science, vol 1983, pp 42–47
Sugiyama M, Yamamoto A (2010) The coding divergence for measuring the complexity of separating two sets. In: Proceedings of
2nd Asian Conference on Machine Learning, JMLR Workshop and Conference Proceedings, vol 13, pp 127–143
Sugiyama M, Hirowatari E, Tsuiki H, Yamamoto A (2006) Learning from real-valued data with the model inference mechanism through the Gray-code embedding. In: Proceedings of 4th Workshop on Learning with Logics and Logics for Learning(LLLL2006), pp 31–37

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

31

Sugiyama M, Hirowatari E, Tsuiki H, Yamamoto A (2009) Learning figures with the Hausdorff metric by self-similar sets. In:
Proceedings of 6th Workshop on Learning with Logics and Logics for Learning (LLLL2009), pp 27–34
Sugiyama, M., Hirowatari, E., Tsuiki, H., & Yamamoto, A. (2010). Learning figures with the Hausdorff metric by fractals. In M.
Hutter, F. Stephan, V. Vovk, & T. Zeugmann (Eds.), Lecture notes in computer science: Vol. 6331. Algorithmic learning theory(pp. 315–329). Canberra: Springer.
Tavana NR, Weihrauch K (2011) Turing machines on represented sets, a model of computation for analysis. Logical Methods in
Computer Science 7(2):1–21
Trakhtenbrot B, Barzdin YM (1970) Konetschnyje awtomaty (powedenie i sintez). English Translation: Finite automata-behavior
and synthesis, Fundamental Studies in Computer Science 1, 1975
Turing AM (1937) On computable numbers, with the application to the entscheidungsproblem. Proceedings of the London Mathematical Society 1(42):230–265
Valiant LG (1984) A theory of the learnable. Communications of the ACM 27(11):1134–1142
Vapnik V, Chervonenkis A (1971) On the uniform convergence of relative frequencies of events to their probabilities. Theory ofProbability and its Applications 16(2):264–280
Weihrauch K (2000) Computable Analysis: An Introduction. Springer
Weihrauch K (2008) The computable multi-functions on multi-represented sets are closed under programming. Journal of Universal
Computer Science 14(6):801–844
Weihrauch K, Grubba T (2009) Elementary computable topology. Journal of Universal Computer Science 15(6):1381–1422
Wiehagen R (1991) A thesis in inductive inference. In: Dix J, Jantke KP, Schmitt PH (eds) Nonmonotonic and Inductive Logic,
Springer, Lecture Notes in Computer Science, vol 543, pp 184–207
Wright K (1989) Identification of unions of languages drawn from an identifiable class. In: Proceedings of the 2nd Annual Workshop
on Computational Learning Theory, pp 328–333
Zeugmann T, Zilles S (2008) Learning recursive functions: A survey. Theoretical Computer Science 397(1-3):4–56
Zeugmann T, Lange S, Kapur S (1995) Characterizations of monotonic and dual monotonic language learning. Information andComputation 120(2):155–173