December 6, 2016

Discretization and Learning
Data Mining Theory (データマイニング工学)

Mahito Sugiyama (杉山麿人)

Today’s Outline• Recap the main points of last week’s lecture• Discretization on learning• Real number computation (実数計算)• Learning = computing = discretization?
• All slides are at:
http://mahito.info/materials.html

1/28

Structurization of Hypothesis Space• To search hypotheses,(i) The structure of the hypothesis space H(ii) An operator that enables to traverse the space

are indispensable• The structured space is mathematically modeled
as a poset (partially ordered set; 半順序集合)• As an operator, we use refinement (精密化)– For each hypothesis, a learner can “refine” it andderive a set of one level-specific hypotheses

2/28

Structurization of Hypothesis SpaceNo structure
in hypothesis space

Poset with refinement

Subset inclusion
relationships inconcept space

3/28

Discretization and Learning
Analog data（reals）
Feature A

Feature B Class

1120

3

140

Goal: Learning of a classifier
4/28

Discretization and Learning
Analog data（reals）
Feature A

Feature B Class

11203140
Discretization by measurement

Goal: Learning of a classifier4/28

Discretization and Learning
Analog data（reals）
Feature A

Digital data（rationals）

Feature B Class

Feature A Feature B Class

111.5

0.6

12

00.6

0.2

03

1

1.1

0.4

14

0

1.8

0.7

0

Discretization by measurement
Goal: Learning of a classifier
4/28

Discretization and Learning
Analog data（reals）

Digital data（rationals）

Feature A

Feature B Class

Feature A Feature B Class

11.539582...

0.6069... 1

1.5

0.6

12

0.676711...

0.2655... 0

0.6

0.2

03

1.111577...

0.4998... 1

1.1

0.4

14

1.871501...

0.7569... 01.8

0.7

0Discretization by measurement
Goal: Learning of a classifier
4/28

Discretization and Learning
Analog data（reals）

Digital data（rationals）

Feature A

Feature B Class

Feature A Feature B Class1

1.539582...

0.6069... 12

Data in theory
0.676711...
0.2655... 0

0.6
0Data on0.2
computer

31.111577...

0.4998... 1

1.1

0.4

14

1.871501...

0.7569... 0

1.8

0.7

0

1.5

0.6

1

Discretization by measurement
Goal: Learning of a classifier
4/28

Fatal Error Caused by Discretization• Solve the system of equations [Schröder, 2003]
40157959.0 x + 67108865.0 y = 167108864.5 x + 112147127.0 y = 0– We can solve by the well-known formula:b 1 a 22 − b 2 a 12
b 2 a 11 − b 1 a 21
x = a a −a a , y= a a −a a
11 22
21 12
11 22
21 12

• Computation by floating point arithmetic with double
precision variables (IEEE 754):
x = 112147127, y = −67108864.5• Correct solution:x = 224294254, y = −134217729

5/28

Treat Data as Intervals
Analog data（reals）

Digital data（rationals）

Feature A

Feature B Class

Feature A Feature B Class1

1.539582...

0.6069... 1

1.2~1.6 0.6~0.8

120.676711...

0.2655... 0

0.4~0.8 0.2~0.4

03

1.111577...

0.4998... 1

1.1~1.2 0.4~0.5

141.871501...

0.7569... 0

1.8~1.9 0.7~0.80Discretization by measurement
Goal: Learning of a classifier
6/28

Geometric Point of View
Digital data（rationals）

1

Feature A Feature B Class012

1.2~1.6 0.6~0.8

1

0.4~0.8 0.2~0.4

0

1.1~1.2 0.4~0.5

1

1.8~1.9 0.7~0.80• Discretized data are intervals in ℝd– The width of an interval corresponds to the error of a data point• A learner finds a set intersecting intervals of class 1
7/28

How to Compute Real Numbers?
• Consider computation of f (x) = 3 ⋅ x• For example: f (1/3) = 3 ⋅ 1/3• Since 1/3 = 0.33333 . . . , a computer should output
0.99999 . . . (or 1.00000 . . . )• However, it cannot output any digit since:– If an input is 0.333 . . . forever, the output is 0.999 . . .
– If an input is 0.333 . . . 34 at some point,
the output is 1.000 . . . 02

• Thus the computer cannot determine even the first digitat any moment

8/28

What is Problem in Real Number
Computation?
• The problem is caused by the representation ofreal numbers (実数表現)• Decimal representation (10 進表現) lacks
redundancy (冗長性)– We need more sequences that represent the same number• Solution: signed digit representation (符号付き 2 進数)– Use three symbols: 1, 0, and 1̄ (1̄ means −1) and defined as:∞ρ(a 1 a 2 . . . ) = ∑ i=1 a i ⋅ 2−i◦ Same as the binary representation if we use only 0 and 19/28

Position

Signed Digit Representation532
10–10110/28

Position

Signed Digit Representation
532
10–1

0

1/3

110/28Position

Signed Digit Representation
532
111111...

0–1

01/3

110/28Position

Signed Digit Representation
532
101011...

0–1

0

1/3

110/28

Gray Code• Using signed digit representation, we can achieve
computation over reals in a natural sense• Another interesting representation is Gray code (グレイコード) by Frank Gray (1947) and Émile Baudot (1878)– Originally, another binary encoding of natural numbers◦ Important in applications of conversion between
analog and digital information [Knuth, 2005]• Gray codes for natural numbers:
Binary
Gray

0

12

3

4

5

6

7000000001
001010011

011010100
110101111

110
101

111
100
11/28

Gray Code Embedding• Gray code can be used for real number representation– We use three symbols 0, 1, and ⊥• The Gray code embedding (グレイコード埋め込み) is aninjection γ G that maps x ∈ [0, 1] to an infinite sequencep 0 p 1 p 2 . . . , where– p i ≔ 1 if 2−i m − 2−(i+1) < x < 2−i m + 2−(i+1) for an odd m,– p i ≔ 0 if the same holds for an even m,– p i ≔ ⊥ if x = 2−i m − 2−(i+1) for some integer m• Power of representations for real number computation:
Gray code = signed digit representation [Dusky, 2002]> binary representation
12/28

Position

Gray Code on Reals
5321000.5

1

13/28

Position

Gray Code on Reals53210
00.1

0.25

00010...
0⊥100...

0.50.8110101...
13/28

Position

Binary Representation
4321000.25

0.50.75

1

14/28

Position

Binary Representation
432
1000.1 0.2

0.5

0.75

100011...
00110...
14/28

Computation via Type-2 Machine• Computation of real numbers is realized as conversion
between their representations (infinite sequences)• Computation on infinite sequences in Σ ω is formulatedusing Type-2 machine

Σω

ξg/


X

ω

Σ


f/

ζ

Y
15/28

Type-2 Machine

Input tape (one way）

Work tapes

Output tape（one way）

16/28

Discretization and Learning• In finite time, a computer (Type-2 machine) receives
a finite prefix (接頭辞) of an infinite sequencethat represents a real number– The input is thus discretized (離散化)• A computer continues to output succeeding digitsof output which is getting closer to the true value

17/28

Discretization and Learning• In finite time, a computer (Type-2 machine) receives
a finite prefix (接頭辞) of an infinite sequencethat represents a real number– The input is thus discretized (離散化)• A computer continues to output succeeding digitsof output which is getting closer to the true value• This is similar to the mechanism of learning– Discretized approximation (in computing)– Partial information of concepts (in learning)

17/28

Discretization and Learning
Partial informationof the target
Discretized
real number

ComputingComputerApproximationof the result
Discretized
real numberLearning
Data

Learner

Hypotheses
18/28

Real Number Computation as Learning• Concept (learning target): a real number x ∈ R• Hypothesis: a finite sequence H = a 1 a 2 . . . a k– A hypothesis H represents an interval υ(H)• Data: prefixes of x = ρ(a 1 a 2 . . . )• Correctness:– Consistency: H is always consistent with x , i.e., x ∈ υ(H)– Instead of convergence in identification in the limit,
we have effectivity:
For a sequence of hypotheses w 1 , w 2 , w 3 , . . . ,υ(w i ) ⊇ υ(w i+1 ) always holds
19/28

Summary of Real Number Computationin Machine Learning Framework
TargetReal number

Representation

Gray code/signed digit representation

DataPrefix (Discretized value, interval)

Algorithm

Depends on functions

Correctness

Consistency & Effectivity
20/28

Example: Binary Representation• Σ = {0, 1}• Binary representation ρ ∶ Σ ω → [0, 1]:∞

ρ(a 1 a 2 . . . ) = ∑ a i ⋅ 2−ii=1• Binary representation for finite sequence∗υ ∶ Σ → P ([0, 1]):
υ(a 1 a 2 . . . a k ) = [ ρ(a 1 a 2 . . . a k 000 . . . ), ρ(a 1 a 2 . . . a k 111 . . . )]k−ik−i−k= [ ∑ ai ⋅ 2 , ∑ ai ⋅ 2 + 2 ]i=1

i=121/28

Position

Binary Representation
432
1000.25

0.50.75

122/28

Example: Signed Digit Representation• Σ = {0, 1, 1̄}ω• Signed digit representation ρ ∶ Σ → [0, 1]:∞

ρ(a 1 a 2 . . . ) = ∑ a i ⋅ 2−i

i=1• Signed digit representation for finite sequence∗υ ∶ Σ → P ([0, 1]):
υ(a 1 a 2 . . . a k ) = [ ρ(a 1 a 2 . . . a k 1̄1̄1̄ . . . ), ρ(a 1 a 2 . . . a k 111 . . . )]k−i−kk−i−k= [ ∑ ai ⋅ 2 − 2 , ∑ ai ⋅ 2 + 2 ]
i=1

i=1

23/28

Position

Signed Digit Representation
53210–10124/28

Refinement• Refinement of signed digit representation is simple:
ρ(i) w → w0ρ(ii) w → w1
ρ(iii) w → w 1̄• “Learning with refinement”= “Real number computation”

25/28

Efficient Learning with Refinement
1. i ← 1, S ← ∅, H ← ⊤, Q ← ∅ // Q is a list of candidate hypotheses
2. repeat3.
S ← S ∪ {(x i , y i )}4.
while H is not consistent with S
5.
if x ∈ υ(H) for some (x, 0) ∈ S then
6.
Append all ρ(H) to the tail of Q
7.
end if8.
H ← the first hypothesis in Q , and remove it from Q
9.
end while10.
H i ← H and output H i
11.
i ← i+1
12. until forever

26/28

Conclusion• Computing and learning have been studied
in different fields• However, if we consider computation over R, there is a
close connection between computing and learning• This is still a developing field– No textbook!
– Some interesting papers:◦ de Brecht, M., Topological and Algebraic Aspects ofAlgorithmic Learning Theory, PhD thesis (2010)◦ Sugiyama, M. and Hirowatari, E. and Tsuiki, H. and Yamamoto,
A., Learning Figures with the Hausdorff Metric by
Fractals—Towards Computable Binary Classification,
27/28
Machine Learning (2012)

Take-Home Massages
1. Learning ≃ Computing on R =/ Computing on N
2. Representation of objects is essential
3. Structure of hypothesis space is crucial for efficiency
4. We are learners in data mining

28/28