ALT October , Learning Figures with the Hausdorﬀ
Metric by Fractals
Mahito SUGIYAMA1,2 , Eiju HIROWATARI3 ,Hideki TSUIKI1 & Akihiro YAMAMOTO1
1 Kyoto University, 2 JSPS Research Fellow
3 The University of Kitakyushu

/Goal and Approach• Constructing a computational learning model for analog
data with discretization
. Gold-style learning model as a base model
. Computable Analysis to give theoretical support for discretizing process of analog data
. Fractals to represent (and compute) continuous objects

/Goal and Approach• Constructing a computational learning model for analog
data with discretization
. Gold-style learning model as a base model
. Computable Analysis to give theoretical support for discretizing process of analog data
. Fractals to represent (and compute) continuous objects

Targets: Figures (non-empty compact sets in ℝn)/Goal and Approach• Constructing a computational learning model for analog
data with discretization
. Gold-style learning model as a base model
. Computable Analysis to give theoretical support for discretizing process of analog data
. Fractals to represent (and compute) continuous objects

Targets: Figures (non-empty compact sets in ℝn)

Examples for learning: Rational closed intervals
/Goal and Approach• Constructing a computational learning model for analog
data with discretization
. Gold-style learning model as a base model
. Computable Analysis to give theoretical support for discretizing process of analog data
. Fractals to represent (and compute) continuous objects

Targets: Figures (non-empty compact sets in ℝn)Hypotheses: Codes (Programs)− representing fractals

Examples for learning: Rational closed intervals
/Goal and Approach• Constructing a computational learning model for analog
data with discretization
. Gold-style learning model as a base model
. Computable Analysis to give theoretical support for discretizing process of analog data
. Fractals to represent (and compute) continuous objects

Targets: Figures (non-empty compact sets in ℝn)Hypotheses: Codes (Programs)− representing fractals
Evaluation of hypotheses:
Hausdorff metric (generalization errors)
Examples for learning: Rational closed intervals
/Main Results
. We formulated learning of ﬁgures with self-similar sets(fractals) using the Gold-style learning model• Collage Theorem gives justiﬁcation for self-similar sets
. We analyzed the hierarchy of learnabilities (next slide). We revealed the mathematical connection between Fractal Geometry and Computational Learning• The complexity of learning (sample size) is measured byusing the Hausdorﬀ dimension and the VC dimension– The Hausdorﬀ dimension and the VC dimension are
key concepts of Fractal Geometry and the Valiantstyle learning model, respectively
/Precise Result of the Hierarchy
FIGEX-INF = FIGCONS-INF = FIGRELEX-INF
FIGEFEX-INF

FIGEX-TXT = FIGCONS-TXT= FIGEXε-INF = FIGEXε-TXT

FIGREFEX-INF

FIGRELEX-TXT

FIGREFEX-TXT
FIGEFEX-TXT = ∅

CR1
CR2

⇔ CR2 ⊊ CR1

/Outline• Background• Methods for learning ﬁgures• Learnabilities under various learning criteria• Characterization with dimH and dimVC• Conclusion

/Outline• Background• Methods for learning ﬁgures• Learnabilities under various learning criteria• Characterization with dimH and dimVC• Conclusion

/Discretization and Learning
Analog data (reals)
att. A

att. B

1
2
3
4

Goal: Learning the relation between attributes A and B
/Discretization and Learning
Analog data (reals)
att. A

att. B12
3
4
Discretization by measurement
Goal: Learning the relation between attributes A and B
/Discretization and Learning
Analog data (reals)
att. A

att. B

Digital data (rationals)
att. A

att. B

1

1.5

0.6

2

0.6

0.2

3

1.1

0.4

4

1.8

0.7

Discretization by measurement
Goal: Learning the relation between attributes A and B
/Discretization and Learning
Analog data (reals)
att. A

Digital data (rationals)

att. B

att. A

att. B1

1.539582...

0.6069...

1.5

0.6

2

0.676711...

0.2655...

0.6

0.2

3

1.111577...

0.4998...

1.1

0.4

4

1.871501...

0.7569...

1.8

0.7

Discretization by measurement
Goal: Learning the relation between attributes A and B
/Discretization and Learning
Analog data (reals)
att. A

Digital data (rationals)

att. B

att. A

att. B

0.6069...

1.5

0.6

1

1.539582...

2

Data assumed
0.676711...
0.2655...

3

1.111577...

0.4998...

Data used
for
0.6
0.2
learning
1.1
0.4

4

1.871501...

0.7569...

1.8

theoretically

0.7

Discretization by measurement
Goal: Learning the relation between attributes A and B
/An Fatal Error Caused by Discretization• Solve the system of linear equations [Schroder, ]
40157959.0 x + 67108865.0 y = 1
67108864.5 x + 112147127.0 y = 0– Obtained by the well-known formulab1 a22 − b2 a12
b2 a11 − b1 a21, y=x=
a11 a22 − a21 a12
a11 a22 − a21 a12• By ﬂoating point arithmetic with double precision variables (IEEE ) :x = 112147127, y = −67108864.5• The correct solution:x = 224294254, y = −134217729
/Our Strategy• Use eﬀective computing in Computable Analysis to treat
discretization precess appropriately– While a computer reads more and more precise information of the input, it produces more and more accurate approximations of the result• Construct an eﬀective learning with the Gold-style learning model– While a learner reads more and more precise examplesof the target, it produces more and more accurate hypotheses of the target∘ This accuracy corresponds to a generalization error

/Treat Data as Intervals
Continuous objects (reals)
att. A

att. B

Digital data (rationals)
att. A

att. B1

1.2~1.6 0.6~0.8

2

0.4~0.8 0.2~0.4

3

1.1~1.2 0.4~0.5

4

1.8~1.9 0.7~0.8
Discretization by measurement

Goal: Learning the relation between attributes A and B
/Leaning from Geometrical View
1

Digital data (rationals)
att. A

att. B

1.2~1.6 0.6~0.8
0.4~0.8 0.2~0.4
01

2 1.1~1.2 0.4~0.5
・Discretized data are intervals in ℝn 1.8~1.9 0.7~0.8- The width of an interval means
an error of the datum
・A learner learns a figure that intersects withall intervals
/Outline• Background• Methods for learning ﬁgures• Learnabilities under various learning criteria• Characterization with dimH and dimVC• Conclusion

/Summary of Learning Process
Positive examples: Rational closed intervals intersecting the learning target
Negative examples: Rational closed intervals disjoint with the learning target
Positive example

Learner

Targetfigure/Summary of Learning Process
Positive examples: Rational closed intervals intersecting the learning target
Negative examples: Rational closed intervals disjoint with the learning target
Positive example

Learner

Targetfigure/Summary of Learning Process
Positive examples: Rational closed intervals intersecting the learning target
Negative examples: Rational closed intervals disjoint with the learning target
Positive example

Learner

Targetfigure/Summary of Learning Process
Positive examples: Rational closed intervals intersecting the learning target
Negative examples: Rational closed intervals disjoint with the learning target
Positive example

Learner

TargetfigureNegative
example/Summary of Learning Process
Positive examples: Rational closed intervals intersecting the learning target
Negative examples: Rational closed intervals disjoint with the learning target
Positive example

Learner

TargetfigureNegative
example/Summary of Learning Process
Positive examples: Rational closed intervals intersecting the learning target
Negative examples: Rational closed intervals disjoint with the learning target
Positive example

Learner

TargetfigureNegative
exampleReads a presentation(infinite sequence of
examples), and produces hypotheses

/Summary of Learning Process
Positive examples: Rational closed intervals intersecting the learning target
Negative examples: Rational closed intervals disjoint with the learning target

H ypotheses: Codes
that represent selfsimilar sets (self-similar
programs)

Positive example

Learner

TargetfigureNegative
exampleReads a presentation(infinite sequence of
examples), and produces hypotheses

Self-similar set
represented bya hypothesis

/Summary of Learning Process
Positive examples: Rational closed intervals intersecting the learning target
Negative examples: Rational closed intervals disjoint with the learning target

H ypotheses: Codes
that represent selfsimilar sets (self-similar
programs)

Positive example

Learner

TargetfigureNegative
exampleReads a presentation(infinite sequence of
examples), and produces hypotheses

Self-similar set
represented bya hypothesis

/Summary of Learning Process
Positive examples: Rational closed intervals intersecting the learning target
Negative examples: Rational closed intervals disjoint with the learning target

H ypotheses: Codes
that represent selfsimilar sets (self-similar
programs)

Positive example

Learner

TargetfigureNegative
exampleReads a presentation(infinite sequence of
examples), and produces hypotheses

Self-similar set
represented bya hypothesis

/Generalization Errors• We measure “goodness” of a hypothesis by a generalization error– We use the Hausdorﬀ metric (distance between ﬁgures)• The Hausdorﬀ distance between ﬁgures A and B (denotedby dH (A, B)) is the minimum ε satisfying A ⊂ Bε and B ⊂ Aε

Aε: ε-neiborhood of A
Bε: ε-neiborhood of B

A
B

/

Hypotheses Represent Self-Similar Sets
• We use logic programs to represent self-similar sets

Sierpiński triangle

φ1

=½

φ2

=½

+

φ3

=½

+

Path(λ)Path(0x) ← Path(x)Path(1x) ← Path(x)Path(3x) ← Path(x)• Any ﬁgure can be approximated by some self-similar set(Corollary of Collage Theorem) [Falconer, ]– For all ﬁgure K and δ > 0, there exists a self-similar set V
such that dH (K, V) < δ/Outline• Background• Methods for learning ﬁgures• Learnabilities under various learning criteria• Characterization with dimH and dimVC• Conclusion

/Learning Self-Similar Sets in the Limit• We formulate learning of self-similar sets based on theGold-style learning model– A target is always represented by some program• A learner FIGEX-INF-learns (FIGEX-TXT-learns) a set of ﬁguresℱ ⊆ 𝒦∗ ⟺ For all K ∈ ℱ and informants (texts), its
output converges to a hypothesis P, where GE(K, P) = 0– 𝒦∗ : The set of ﬁgures, GE(K, P) ≔ dH (K, κ(P))∘ κ(P) denotes the set represented by a program P– Notation: ℱ is CR-learnable ⟺ ℱ ∈ CR
• We also consider consistent learning (FIGCONS-INF- andFIGCONS-TXT-learning), where every hypothesis is consistent with received examples so far
/The Hierarchy of Learnabilities
FIGEX-INF = FIGCONS-INF = FIGRELEX-INF
FIGEFEX-INF

FIGEX-TXT = FIGCONS-TXT= FIGEXε-INF = FIGEXε-TXT

FIGREFEX-INF

FIGRELEX-TXT

FIGREFEX-TXT
FIGEFEX-TXT = ∅

CR1
CR2

⇔ CR2 ⊊ CR1

/Approach to All Figures• In FIGEX-learning, the space ℱ for learning (concept space)is given (a priori)– When a target ﬁgure K ∉ ℱ, nothing is guaranteed• Here we give some guarantee to such cases– We treat not only self-similar sets, but also ﬁgures– The similar model has been studied in learning of languages [Mukouchi and Arikawa, ]. Refutable learning: a learner stops (if a target K ∉ ℱ)
. Reliable learning: hypotheses do not converge (if K ∉ ℱ)
. Eﬀective learning: generalization errors converge to zero. Learning with generalization error bounds: hypotheses
converge under the error bounds
/The Hierarchy of Learnabilities
FIGEX-INF = FIGCONS-INF = FIGRELEX-INF
FIGEFEX-INF

FIGEX-TXT = FIGCONS-TXT= FIGEXε-INF = FIGEXε-TXT

FIGREFEX-INF

FIGRELEX-TXT

FIGREFEX-TXT
FIGEFEX-TXT = ∅

CR1
CR2

⇔ CR2 ⊊ CR1

/Conclusion So Far• Learning of ﬁgures was realized in computational mannerusing the Gold-style learning model– Discretization process was treated by using the eﬀective
computing model in Computable Analysis– Generalization error of a hypothesis was measured by
the Hausdorﬀ metric• Learnabilities of ﬁgures were analyzed under existing andnew learning criteria

/Conclusion So Far• Learning of ﬁgures was realized in computational mannerusing the Gold-style learning model– Discretization process was treated by using the eﬀective
computing model in Computable Analysis– Generalization error of a hypothesis was measured by
the Hausdorﬀ metric• Learnabilities of ﬁgures were analyzed under existing andnew learning criteria• We show a mathematical connection between Fractal Geometry and Computational Learning using the Hausdorﬀ
dimension and the VC dimension
/Outline• Background• Methods for learning ﬁgures• Learnabilities under various learning criteria• Characterization with dimH and dimVC• Conclusion

/The Hausdorﬀ Dimension (dimH )• The Hausdorﬀ dimension is a central concept of fractals– This indicates how much space a sets occupies near toeach of its points– Deﬁned by the Hausdorﬀ measure• Extension of usual (topological) dimension

Point

=0

Cube

=3

Line

=1

Sierpiński triangle

Plane

=2

= log3 / log2
= 1.584...
/The Hausdorﬀ Dimension (dimH )• The Hausdorﬀ dimension is a central concept of fractals– This indicates how much space a sets occupies near toeach of its points– Deﬁned by the Hausdorﬀ measure• Hausdorﬀ measures generalize ideas of length, area, …
– Deﬁned by using “covering” of a set• s-dimensional Hausdorﬀ measure of K ≔ limε→0 ℋsε (K)– Countable set U is a ε-cover of K ⟺∞∀U ∈ U. |U| ⩽ ε, and X ⊂ ⋃U∈U U– ℋsε (K)s0
= inf{ ∑U∈U |U| ∣ U is a ε-cover of K }dimHK ns

/Characterization with dimH
• General case:If level k is large enough, for every target ﬁgure K and forany s < dimH K, the ﬁgure K can be covered by N intervals,
ks
where N ⩾ b• Special case:Moreover, if a target ﬁgure K is represented by some selfsimilar program P, then K can be covered by N intervals,
where N ⩾ bkdimH K– We use base-b partition in both cases

/Characterization with dimH
• Example:– K: The Sierpiński triangle(dimH K = 1.584 … )– N(K):  of level-k positive examples• With -dimensional base- partition– Level : 3 ⩽ N(K) (2dimH K = 3)
– Level : 9 ⩽ N(K) (4dimH K = 9)
• With -dimensional base- partition– Level : 6 ⩽ N(K) (3dimH K = 5.70 … )/The VC Dimension (dimVC )• The VC dimension is a parameter of separability (complexity) of a class– How many points can be separated?
– In the Valiant-style (PAC) learning model, the sample
size is characterized by the VC dimension

I: The class of open intervals H: The class of half spaces inin the real line ℝ
2-dimensional real-space ℝ2

dimVC I = 2

dimVC H = 3
/Characterization with dimH and dimVC• The VC dimension of the set of level k programs 𝒫k isequal to the cardinality of the number of level k intervals

/Characterization with dimH and dimVC• The VC dimension of the set of level k programs 𝒫k isequal to the cardinality of the number of level k intervals• General case:If level k is large enough, for every target ﬁgure K and forany s < dimH K, the ﬁgure K can be covered by N intervals,
where N ⩾ bks• Special case:Moreover, if a target ﬁgure K is represented by some selfsimilar program P, then K can be covered by N intervals,
where N ⩾ bkdimH K– We use base-b partition in both cases
/Characterization with dimH and dimVC• The VC dimension of the set of level k programs 𝒫k isequal to the cardinality of the number of level k intervals• General case:If level k is large enough, for every target ﬁgure K and forany s < dimH K, the ﬁgure K can be covered by N intervals,
where N ⩾ (dimVC 𝒫k )s/n
• Special case:Moreover, if a target ﬁgure K is represented by some selfsimilar program P, then K can be covered by N intervals,
where N ⩾ (dimVC 𝒫k )dimH K/n– We use base-b partition in both cases
/Outline• Background• Methods for learning ﬁgures• Learnabilities under various learning criteria• Characterization with dimH and dimVC• Conclusion

/Conclusion• Learning of ﬁgures was realized in computational mannerusing the Gold-style learning model– Discretization process was treated by using the eﬀective
computing model in Computable Analysis– Generalization error of a hypothesis was measured by
the Hausdorﬀ metric• Learnabilities of ﬁgures were analyzed under existing andnew learning criteria• A novel mathematical connection between Fractal Geometry and Computational Learning was shown using
the Hausdorﬀ dimension and the VC dimension

/Appendix

/Background• Machine learning from analog data
– The discrete Fourier analysis is a typical method∘ But only the direction of the time axis is discretized– We discretized all axes and give a fully computational
learning model• What kind of representation system is appropriate?
– Recursive algorithms are key to bridge continuous anddiscrete∘ FFT is used in the discrete Fourier analysis– Fractals are geometric concepts of recursiveness∘ They are recursive algorithms to generate fractals• Formulate “Learning ﬁgures by fractals”
/Computational and Statistical Learning
analyzed in detail started fromthe Gold-style learning model

great success in
Knowledge Discovery

Computational learning Statistical learning
Targets

Discrete(languages)

Continuous(real-valued functions)Representations Symbol-level
Signal-level(Hypotheses)(multilayer perceptrons)(algorithms)
Generalization error Generalization error
Evaluation(Characteristic func.)(KL divergence)/Computational and Statistical Learning
analyzed in detail started fromthe Gold-style learning model great success in
Knowledge Discovery
introduce geometricconcept
Computational learning Statistical learning
Targets

Discrete(languages)

Continuous(real-valued functions)Representations Symbol-level
Signal-level(Hypotheses)(multilayer perceptrons)(algorithms)
Generalization error Generalization error
Evaluation(Characteristic func.)(KL divergence)/Computational and Statistical Learning
analyzed in detail started fromthe Gold-style learning model great success in
Knowledge Discovery
introduce geometricconcept
Computational learning Statistical learning
Targets

Continuous
Discrete
Continuous(real-valued functions)(languages) (Figures)

Symbol-level
Representations Symbol-level
Signal-level(Self-similar
sets)(Hypotheses)(multilayer perceptrons)(algorithms)
Generalization error Generalization
Generalizationerror
error
Evaluation(Hausdorff
metric)(Characteristic func.)(KL divergence)/Self-Similar Sets
• Self-similar sets are in a class of fractals– deﬁned as a ﬁxed point of a ﬁnite set of contractions• φ: X → X is a contraction ⟺ d(φ(x), φ(y)) ≤ cd(x, y)(0 < c < 1, d is a metric on X)

Φ0(K) = K

φ1

=½

φ2

=½

+

φ3

=½

+

3

Φ(K) =  φ (K )i =1

Φ1(K) = Φ(K) Φ2(K) = Φ(Φ(K))

Fix(Φ) =  Φ k (K)k=0(Sierpiński triangle)
/Self-Similar Programs• Represent Φ as a logic program (self-similar program)
SP(W) = {Path(λ)} ∪ {Path(wx) ← Path(x) ∣ w ∈ W}
• Bottom-up construction of the least Herbrand model of
SP(W) corresponds to computing Fix(Φ) eﬀectively• Example:
Path(λ), Path(0x) ← Path(x),SP({0, 1, 3}) =Path(1x) ← Path(x), Path(3x) ← Path(x)– Bottom-up construction:{Path(λ)}, {Path(0), Path(1), Path(3)},Path(00), Path(01), Path(03), Path(10), Path(11),…
Path(13), Path(30), Path(31), Path(33)

{

{

}

}

/

Collage Theorem• Hausdorﬀ distance between a ﬁgure K and a self-similar
set V can be bounded (Collage Theorem) [Barnsley, ]dH (K, ⋃φ∈C φ(K))
dH (K, V) ⩽1−c
(V is a self-similar set for C, c is a contractivity factor of C)• Any ﬁgure can be approximated (in the meaning of theHausdorﬀ metric) by some self-similar set arbitrarilyclosely [Falconer, ]For any ﬁgure K and δ > 0, there exists a self-similar
set V satisfying dH (K, V) < δ


/

Learning in the Limit• Introduce a criterion corresponding to EX-learning• A learner M FIGEX-INF-learns (FIGEX-TXT-learns) a set of ﬁgures ℱ ⊆ 𝒦∗ ⟺ For all K ∈ ℱ and informants (texts) of
K, M(σK ) converges to a hypothesis P such that GE(K, P) = 0– GE(K, P) is a generalization error，deﬁne by dH (K, κ(P))∘ dH is the Hausdorﬀ distance– Hypotheses converge ⟺ every hypothesis is samefrom some point• ℱ is CR-learnable if some learner M CR-learns ℱ ⊆ 𝒦∗
– CR denotes the class of CR-learnable sets of ﬁgures∘ ℱ is CR-learnable ⟺ ℱ ∈ CR/Analysis of Learnability in the Limit• The set κ(𝒫∗ ) is FIGEX-INF-learnable (𝒦∗ is not FIGEX-INFlearnable)– κ(𝒫∗ ) is recursively enumerable– For all P ∈ 𝒫∗ and w, whether ρ(w) ∈ 𝒬(κ(P)) can bedecidable in ﬁnite time
– Use the strategy of “generate and test”• The set κ(𝒫∗ ) is not FIGEX-TXT-learnable• The set κ(𝒫N ) (N is ﬁnite set of natural numbers) is
FIGEX-TXT-learnable– If a learner knows the number of contractions a priori, it
can learn from texts
/The Hierarchy of Learnabilities
FIGEX-INF = FIGCONS-INF = FIGRELEX-INF
FIGEFEX-INF

FIGEX-TXT = FIGCONS-TXT= FIGEXε-INF = FIGEXε-TXT

FIGREFEX-INF

FIGRELEX-TXT

FIGREFEX-TXT
FIGEFEX-TXT = ∅

CR1
CR2

⇔ CR2 ⊊ CR1

/Consistent Learning• A learner M FIGCONS-INF-learns (FIGCONS-TXT-learns) a set ofﬁgures ℱ ⊆ 𝒦∗ ⟺ M FIGEX-INF-learns (FIGEX-TXT-learns)ℱ, and every hypothesis is consistent with received examples so far– ℱ is FIGCONS-INF-learnable ⇒ ℱ is FIGEX-INF-learnable– ℱ is FIGCONS-TXT-learnable ⇒ ℱ is FIGEX-TXT-learnable• FIGEX-INF = FIGCONS-INF– If ℱ ∈ FIGEX-INF, M always outputs a consistent hypothesis• FIGEX-TXT = FIGCONS-TXT– If ℱ ∈ FIGEX-TXT, M always outputs a consistent hypothesis
/The Hierarchy of Learnabilities
FIGEX-INF = FIGCONS-INF = FIGRELEX-INF
FIGEFEX-INF

FIGEX-TXT = FIGCONS-TXT= FIGEXε-INF = FIGEXε-TXT

FIGREFEX-INF

FIGRELEX-TXT

FIGREFEX-TXT
FIGEFEX-TXT = ∅

CR1
CR2

⇔ CR2 ⊊ CR1

/Extension of Learning in the Limit• In FIGEX-INF- (and FIGEX-TXT-) learning, ℱ is given as a concept space a priori– When a target ﬁgure K ∉ ℱ, nothing is guaranteed• Here we give some guarantee to such cases, where a target ﬁgure K ∉ ℱ– More diﬃcult than FIGEX-INF- and FIGEX-TXT-learning• We consider the following criteria: ) refutable learning,) reliable learning, ) eﬀective learning, and ) learningwith generalization error bounds– If a target K ∉ ℱ, ) a learner stops, ) hypotheses do
not converge, ) generalization errors converge to zero,and ) converges under the error bounds
/Reliable Learning• A learner M FIGRELEX-INF-learns (FIGRELEX-TXT-learns) a set
of ﬁgures ℱ ⊆ 𝒦∗ ⟺ M FIGEX-INF-learns (FIGEX-TXTlearns) ℱ, and if a target K ∈ 𝒦∗ ⧵F, then for all informants(texts) σK , M(σK ) does not converge to any hypothesis• FIGEX-INF = FIGRELEX-INF– If K ∈ 𝒦∗ ⧵F, then for all P ∈ 𝒫∗ , there exists an example
that is not consistent with P• κ(𝒫N ) is FIGRELEX-TXT-learnable only if N = {1}– Example: Let N = {2} and K = {(0, 0), (1/2, 1/2), (1, 1)}).
Then K ⊂ κ(SP({0, 3})), and outputs converges to thisprogram• In learning of languages, a class ℒ is reliably inferablefrom texts if and only if ℒ contains no inﬁnite concept
/The Hierarchy of Learnabilities
FIGEX-INF = FIGCONS-INF = FIGRELEX-INF
FIGEFEX-INF

FIGEX-TXT = FIGCONS-TXT= FIGEXε-INF = FIGEXε-TXT

FIGREFEX-INF

FIGRELEX-TXT

FIGREFEX-TXT
FIGEFEX-TXT = ∅

CR1
CR2

⇔ CR2 ⊊ CR1

/Refutable Learning• A learner M FIGREFEX-INF-learns (FIGREFEX-TXT-learns) a set
of ﬁgures ℱ ⊆ 𝒦∗ ⟺ M FIGEX-INF- (FIGEX-TXT-) learns ℱ,
and if a target K ∈ 𝒦∗ ⧵ F, then for all informants (texts),
M stops and outputs a special symbol ⊥• κ(𝒫m ) (m ∈ ℕ) is not FIGREFEX-INF-learnable– FIGRELEX-TXT ⊈ FIGREFEX-INF• FIGREFEX-INF ⊈ FIGRELEX-TXT holds• FIGREFEX-TXT ⊆ FIGRELEX-TXT from Deﬁnition, and trivially
FIGREFEX-TXT ≠ FIGRELEX-TXT• FIGREFEX-TXT ⊂ FIGREFEX-INF also holds• FIGREFEX-TXT ≠ ∅/The Hierarchy of Learnabilities
FIGEX-INF = FIGCONS-INF = FIGRELEX-INF
FIGEFEX-INF

FIGEX-TXT = FIGCONS-TXT= FIGEXε-INF = FIGEXε-TXT

FIGREFEX-INF

FIGRELEX-TXT

FIGREFEX-TXT
FIGEFEX-TXT = ∅

CR1
CR2

⇔ CR2 ⊊ CR1

/

Eﬀective Learning• A learner M FIGEFEX-INF-learns (FIGEFEX-TXT-learns) a set ofﬁgures ℱ ⊆ 𝒦∗ ⟺ M FIGEX-INF- (FIGEX-TXT-) learns ℱ,
and if a target K ∈ 𝒦∗ ⧵ F, then for all informants (texts),
there exists some monotone function ε: ℕ → ℝ+ , wherelimi→∞ ε(i) = 0 and GE(K, M(σK )(i)) ≤ ε(i)• κ(𝒫) is FIGEFEX-INF-learnable, and κ(𝒫m ) (m ∈ ℕ) is not
FIGEFEX-INF-learnable– FIGEFEX-INF ⊈ FIGEX-TXT and FIGEX-TXT ⊈ FIGEFEX-INF• FIGREFEX-INF ⊆ FIGEFEX-INF from Deﬁnition, and trivially
FIGREFEX-INF ≠ FIGEFEX-INF• FIGEFEX-TXT = ∅– FIGEFEX-TXT ⊂ FIGREFEX-TXT (diﬀerent from learning frominformants)
/The Hierarchy of Learnabilities
FIGEX-INF = FIGCONS-INF = FIGRELEX-INF
FIGEFEX-INF

FIGEX-TXT = FIGCONS-TXT= FIGEXε-INF = FIGEXε-TXT

FIGREFEX-INF

FIGRELEX-TXT

FIGREFEX-TXT
FIGEFEX-TXT = ∅

CR1
CR2

⇔ CR2 ⊊ CR1

/Approximative Learning• A learner M FIGEXε -INF-learns (FIGEXε -TXT-learns) a set of ﬁgures ℱ ⊆ 𝒦∗ ⟺ For all K ∈ 𝒦∗ and informants (texts)
σK , M(σK ) converges to P such that GE(K, P) = 0 if K ∈ ℱ,
and to Q such that GE(K, Q) ≤ ε if K ∈ 𝒦∗ ⧵ F• For all ε ∈ ℝ+ , FIGEXε -TXT = FIGEX-TXT• For all ε ∈ ℝ+ , FIGEXε -TXT = FIGEXε -INF
– Since if ℱ ∈ FIGEXε -INF, then F ⊆ 𝒫≤k• FIGREFEX-INF ⊂ FIGEXε -INF

/The Hierarchy of Learnabilities
FIGEX-INF = FIGCONS-INF = FIGRELEX-INF
FIGEFEX-INF

FIGEX-TXT = FIGCONS-TXT= FIGEXε-INF = FIGEXε-TXT

FIGREFEX-INF

FIGRELEX-TXT

FIGREFEX-TXT
FIGEFEX-TXT = ∅

CR1
CR2

⇔ CR2 ⊊ CR1

/