October 20, 2023

Learning and Computing
Data Mining (データマイニング)
Mahito Sugiyama (杉山麿人)

Objective of Today’s Lecture• Learn a fundamental mechanism of machine learning– Machine learning is a core process in many applications in data mining• Computational aspects of machine learning are mainly discussed• Key issues:◦ Finite/infinite– Computing (single) vs Learning (double)– Learning targets (mathematical objects) vsRepresentations (programs)

1/34

Learning from Examples (Generalization)[Schoelkopf, 2013]• 1, 2, 4, 7, ...

→ What are succeeding numbers?

2/34

Learning from Examples (Generalization)[Schoelkopf, 2013]• 1, 2, 4, 7, ... → What are succeeding numbers?
1, 2, 4, 7, 11, 16, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑛 − 1)

2/34

Learning from Examples (Generalization)[Schoelkopf, 2013]• 1, 2, 4, 7, ... → What are succeeding numbers?
1, 2, 4, 7, 11, 16, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑛 − 1)
1, 2, 4, 7, 12, 20, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 1)

2/34

Learning from Examples (Generalization)[Schoelkopf, 2013]• 1, 2, 4, 7, ... → What are succeeding numbers?
1, 2, 4, 7, 11, 16, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑛 − 1)
1, 2, 4, 7, 12, 20, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 1)
1, 2, 4, 7, 13, 24, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 𝑎𝑛−3 )2/34

Learning from Examples (Generalization)[Schoelkopf, 2013]• 1, 2, 4, 7, ... → What are succeeding numbers?
1, 2, 4, 7, 11, 16, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑛 − 1)
1, 2, 4, 7, 12, 20, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 1)
1, 2, 4, 7, 13, 24, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 𝑎𝑛−3 )1, 2, 4, 7, 14, 28(divisors of 28)

2/34

Learning from Examples (Generalization)[Schoelkopf, 2013]• 1, 2, 4, 7, ... → What are succeeding numbers?
1, 2, 4, 7, 11, 16, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑛 − 1)
1, 2, 4, 7, 12, 20, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 1)
1, 2, 4, 7, 13, 24, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 𝑎𝑛−3 )1, 2, 4, 7, 14, 28(divisors of 28)
1, 2, 4, 7, 1, 1, 5, ... (𝜋 = 3.1415 … and 𝑒 = 2.718 … )2/34

Learning from Examples (Generalization)[Schoelkopf, 2013]• 1, 2, 4, 7, ... → What are succeeding numbers?
1, 2, 4, 7, 11, 16, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑛 − 1)
1, 2, 4, 7, 12, 20, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 1)
1, 2, 4, 7, 13, 24, ... (𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 𝑎𝑛−3 )1, 2, 4, 7, 14, 28(divisors of 28)
1, 2, 4, 7, 1, 1, 5, ... (𝜋 = 3.1415 … and 𝑒 = 2.718 … )• More than 1229 rules! (https://oeis.org)

2/34

Analyze Learning as Scientific Problem• Which is the correct answer (or generalization)
for succeeding numbers of 1, 2, 4, 7, … ?
– Any answer is possible!

3/34

Analyze Learning as Scientific Problem• Which is the correct answer (or generalization)
for succeeding numbers of 1, 2, 4, 7, … ?
– Any answer is possible!

• We should take two points into consideration:◦ There are two agents (teacher and learner) in learning,which are different from “computation”(i) We need to formalize the problem of “learning”◦ A learner usually never knows thatthe current hypothesis is perfectly correct(ii) Learning is an infinite process

3/34

Framework of Learning (ML vs DM)
Machine Learning(Teacher)
User

Data(Learner)
Computer

Law that
generalizes
4/34

Framework of Learning (ML vs DM)
Data Mining (Knowledge Discovery)
Machine Learning(Teacher)
Objects(Natural phenomenon, market, ...)

Data (Learner) Data(Teacher)
User

Law that
generalizes(Learner)
Computer

Law that
generalizes
4/34

Computation — Core Engine of Learning/Mining• Machine learning/data mining is usually achieved using acomputer• Computing behavior is mathematically formulated byAlan Turing in 1936
– A. M. Turing, On Computable Numbers, with the Application to the

Entscheidungsproblem, Proceedings of the London Mathematical Society, 42(1),230–265, 1937

• The model of computation, known as a Turing machine,
is developed for simulating computation by human beings
5/34

8/34

9/34

10/34

Turing Machine
TapeStateMachine– Read a symbol 𝑎 of a cell
– Do the following from the symbol 𝑎 and the current state 𝑠
according to a set of rules in its memory• The machine repeats the following:◦ Replace the symbol 𝑎 at the square◦ Move the head
◦ Change the state 𝑠

11/34

Computing vs Learning• In computation, the process is completed on its own◦ The Turing machine automatically works
according to programmed rules– No interaction– A finite process

12/34

Computing vs Learning• In computation, the process is completed on its own◦ The Turing machine automatically works
according to programmed rules– No interaction– A finite process• In learning, there are two agents (teacher and learner)◦ A learning protocol between a teacher and a learneris essentially needed– Interaction between agents should be considered– An infinite process
12/34

Formalize Learning in ComputationalManner
1. What are targets of learning?
2. How to represent targets and hypotheses?
3. How are data provided to a learner?
4. How does the learner work?
5. When can we say that the learner correctly learns the target?

13/34

Learning of Binary Classifier

14/34

Learning of Binary Classifier
wx + b = 0

14/34

Example: Perceptron (by F. Rosenblatt, 1958)• Learning target: two subsets 𝐹, 𝐺 ⊆ ℝ𝑑 s.t. 𝐹 ∩ 𝐺 = ∅– Assumption: 𝐹 and 𝐺 are linearly separable◦ There exists a function (classifier) 𝑓∗ (𝑥) = 𝑤∗ 𝑥 + 𝑏 s.t.
𝑓∗ (𝑥) > 0 ∀𝑥 ∈ 𝐹,𝑓∗ (𝑥) < 0 ∀𝑥 ∈ 𝐺

15/34

Example: Perceptron (by F. Rosenblatt, 1958)• Learning target: two subsets 𝐹, 𝐺 ⊆ ℝ𝑑 s.t. 𝐹 ∩ 𝐺 = ∅– Assumption: 𝐹 and 𝐺 are linearly separable◦ There exists a function (classifier) 𝑓∗ (𝑥) = 𝑤∗ 𝑥 + 𝑏 s.t.
𝑓∗ (𝑥) > 0 ∀𝑥 ∈ 𝐹,𝑓∗ (𝑥) < 0 ∀𝑥 ∈ 𝐺• Hypotheses: hyperplanes on ℝ𝑑– If we consider a linear equation 𝑓(𝑥) = 𝑤𝑥 + 𝑏, each line can be
uniquely specified by a pair of two parameters (𝑤, 𝑏) (hypothesis)

15/34

Example: Perceptron (by F. Rosenblatt, 1958)• Learning target: two subsets 𝐹, 𝐺 ⊆ ℝ𝑑 s.t. 𝐹 ∩ 𝐺 = ∅– Assumption: 𝐹 and 𝐺 are linearly separable◦ There exists a function (classifier) 𝑓∗ (𝑥) = 𝑤∗ 𝑥 + 𝑏 s.t.
𝑓∗ (𝑥) > 0 ∀𝑥 ∈ 𝐹,𝑓∗ (𝑥) < 0 ∀𝑥 ∈ 𝐺• Hypotheses: hyperplanes on ℝ𝑑– If we consider a linear equation 𝑓(𝑥) = 𝑤𝑥 + 𝑏, each line can be
uniquely specified by a pair of two parameters (𝑤, 𝑏) (hypothesis)• Data: a sequence of pairs (𝑥1 , 𝑦1 ), (𝑥2 , 𝑦2 ), …

– (𝑥𝑖 , 𝑦𝑖 ): (a real-valued vector in ℝ𝑑 , a label)– 𝑥𝑖 ∈ 𝐹 ∪ 𝐺, 𝑦𝑖 ∈ {1, −1}, and 𝑦𝑖 = 1 (𝑦𝑖 = −1) if 𝑥𝑖 ∈ 𝐹 (𝑥𝑖 ∈ 𝐺)

15/34

Learning Model for Perceptron
Gf(x) = wx + b = 0
A hypothesis, a hyperplanein general, is uniquely specifiedF
by a pair (w, b)(xi, 1)
Data(xj, –1)

16/34

Learning Procedure of Perceptron

1. 𝑤 ← 0, 𝑏 ← 0 (or a small random value)
2. for 𝑖 = 1, 2, 3, … do
3. Receive 𝑖-th pair (𝑥𝑖 , 𝑦𝑖 )∑𝑑𝑗
4. Compute 𝑎 = 𝑗=1 𝑤𝑗 𝑥𝑖 + 𝑏
5. if 𝑦𝑖 ⋅ 𝑎 < 0 then6.
𝑤 ← 𝑤 + 𝑦𝑖 𝑥𝑖
7.
𝑏 ← 𝑏 + 𝑦𝑖
8. end if
9. end for// initialization// 𝑥𝑖 is misclassified// update the weight// update the bias

17/34

Correctness of Perceptron• It is guaranteed that a perceptron always converges
to a correct classifier– A correct classifier is a function 𝑓 s.t.
𝑓(𝑥) > 0 ∀𝑥 ∈ 𝐹,𝑓(𝑥) < 0 ∀𝑥 ∈ 𝐺– The convergence theorem• Note: there are (infinitely) many functionsthat correctly classify 𝐹 and 𝐺– A perceptron converges to one of them

18/34

Summary: Perceptron
TargetTwo disjoint subsets of ℝ𝑑

Representation

Two parameters (𝑤, 𝑏) of linear

Data

Real vectors from target subsets

Algorithm

Perceptron

Correctness

Convergence theorem

equation 𝑓(𝑥) = 𝑤𝑥 + 𝑏

19/34

Example 2: Maximum Likelihood Estimation• Estimate the probability of a coin being a head in a toss
TargetBernoulli distribution

Representation

Parameter (probability) 𝑝

Data

Sampling

Algorithm

Maximum Likelihood Estimation

Correctness

Consistency𝑝̂ = 𝑘∕𝑛

20/34Basic Definitions of Learning• Target: a classifier 𝑓∗ ∶ 𝑋 → {0, 1}– A class 𝒞 of classifiers is usually pre-determined– Each target can be viewed as the set 𝐹∗ = {𝑎 ∈ 𝑋 ∣ 𝑓∗ (𝑎) = 1}
◦ 𝐹∗ is called a concept

21/34

Basic Definitions of Learning• Target: a classifier 𝑓∗ ∶ 𝑋 → {0, 1}– A class 𝒞 of classifiers is usually pre-determined– Each target can be viewed as the set 𝐹∗ = {𝑎 ∈ 𝑋 ∣ 𝑓∗ (𝑎) = 1}
◦ 𝐹∗ is called a concept• Hypothesis space: ℛ– Each hypothesis 𝐻 ∈ ℛ represents a classifier– ℛ ⊆ Σ∗ usually holds (Σ∗ is the set of finite strings)

21/34

Basic Definitions of Learning• Target: a classifier 𝑓∗ ∶ 𝑋 → {0, 1}– A class 𝒞 of classifiers is usually pre-determined– Each target can be viewed as the set 𝐹∗ = {𝑎 ∈ 𝑋 ∣ 𝑓∗ (𝑎) = 1}
◦ 𝐹∗ is called a concept• Hypothesis space: ℛ– Each hypothesis 𝐻 ∈ ℛ represents a classifier– ℛ ⊆ Σ∗ usually holds (Σ∗ is the set of finite strings)• Data: Example (𝑎, 𝑓∗ (𝑎))– 𝑎∈𝑋
– An example (𝑎, 1) is called positive, (𝑎, 0) is called negative
21/34

Learning ModelX

A class ofclassifiers

A target classifier(concept) f*

Hypothesis

Data(x1, 0), (x2, 1),(x3, 1), (x4, 0), ...

Learner

22/34

Learning Model (e.g. Perceptron)dℝ

A target of linear
equation f*

A class oflinearly
separable setsData
(x1, 0), (x2, 1),(x3, 1), (x4, 0), ...

(w, b)
Perceptron(in f(x) = wx + b)
23/34

Gold’s Learning Model(Identification in the Limit)• Gold gave the first basic learning model, called“Identification in the limit”– E. M. Gold, Language identification in the limit,Information and Control, 10(5), 447–474, 1967

• This model was originally introduced to analyze
the learnability of formal languages– His motivation was to model infant’s learning process of naturallanguages
24/34

25/34

Formal Languages• Alphabet Σ: a nonempty finite set– Each element 𝑎 ∈ Σ is called a symbol• Word 𝑤 = 𝑎1 𝑎2 … 𝑎𝑛 : a finite sequence of symbols– Null word 𝜀, whose length is 0

• The set of words Σ∗ (with 𝜀) and Σ+ (without 𝜀)Σ∗ = { 𝑎1 𝑎2 … 𝑎𝑛 ∣ 𝑎𝑖 ∈ Σ, 𝑛 ≥ 0 }Σ+ = { 𝑎1 𝑎2 … 𝑎𝑛 ∣ 𝑎𝑖 ∈ Σ, 𝑛 ≥ 1 } = Σ∗ ⧵ {𝜀}• Formal language: a subset of Σ∗

26/34

Representation of Languages• We connect syntax and semantics using a mapping 𝑓• For a hypothesis 𝐻 ∈ ℛ, 𝑓(𝐻, 𝑤) is 0 or 1 for 𝑤 ∈ Σ∗
– 𝐻 is a program of a classifier– 𝑤 is a (binary) code of the input to 𝐻

• 𝐿(𝐻) = { 𝑤 ∈ Σ∗ ∣ 𝑓(𝐻, 𝑤) = 1 }• ℛ is usually a recursively enumerable set– There is an algorithm that enumerates all elements of ℛ
– ℛ is often identified with ℕ◦ Each natural number encodes a classifier (hypothesis)
27/34

Setting of Gold’s Learning Model• A class of languages 𝒞 ⊆ { 𝐴 ∣ 𝐴 ⊆ Σ∗ } is chosen• For a language 𝐿 ∈ 𝒞, an infinite sequence 𝜎 = (𝑥1 , 𝑦1 ), (𝑥2 , 𝑦2 ), …
is a complete presentation of 𝐿 if(i) {𝑥1 , 𝑥2 , … } = Σ∗(ii) 𝑦𝑖 = 1 ⇐⇒ 𝑥𝑖 ∈ 𝐿 for all 𝑖– 𝜎[𝑖] = (𝑥1 , 𝑦1 ), … , (𝑥𝑖 , 𝑦𝑖 ) (a prefix of 𝜎)• A learner is a procedure 𝑀 that receives 𝜎 andgenerates an infinite sequence of hypotheses 𝛾 = 𝐻1 , 𝐻2 , …
– 𝑀 outputs 𝐻𝑖 if it gets 𝜎[𝑖]28/34Identification in the Limit• If 𝛾 converges to some hypothesis 𝐻 and 𝐻 represents 𝐿,
we say that 𝑀 identifies 𝐿 in the limit• If 𝑀 identifies any 𝐿 ∈ 𝒞 in the limit,
we say that 𝑀 identifies 𝒞 in the limit

29/34

Basic Strategy: Generate and Test
• Input: a complete presentation 𝜎 of a language 𝐿• Output: 𝛾 = 𝐻1 , 𝐻2 , …
1. 𝑖 ← 1, 𝑆 ← ∅2. Repeat
3. 𝑆 ← 𝑆 ∪ {(𝑥𝑖 , 𝑦𝑖 )}4. 𝑘 ← min { 𝑗 ∈ ℕ ∣ 𝐿(𝐻(𝑗)) consistent with 𝑆 }5.
// 𝐻(𝑗) is a hypothesis encoded by a natural number 𝑗
6. 𝐻𝑖 ← 𝐻(𝑘) and output 𝐻𝑖
7. 𝑖 ← 𝑖 + 1
8. until forever

30/34

Power of Generate and Test Strategy• For any class 𝒞 of languages,Generate and Test strategy identifies 𝒞 in the limit– That is, Generate and Test strategy identifies
every language 𝐿 ∈ 𝒞 in the limit• Unfortunately, this strategy is very inefficient– More intelligent strategy can be designed
for each learning target– One of the most important tasks in studies ofmachine learning!

31/34

Learning from Positive Data
• In many cases, in particular in data mining,
we obtain only positive data
• A positive presentation of a language 𝐿 ∈ 𝒞
is an infinite sequence 𝑥1 , 𝑥2 , … s.t. 𝐿 = {𝑥1 , 𝑥2 , … }– Imagine supervised vs unsupervised learning• If 𝛾 (an infinite sequence of hypotheses of a learner 𝑀) converges
to a hypothesis 𝐻 s.t. 𝐿(𝐻) = 𝐿,we say that 𝑀 identifies 𝐿 in the limit from positive data

32/34

Limitation of Learning from Positive Data
• Consider the following class 𝒞(i) All finite languages are included in 𝒞(ii) At least one infinite language is included in 𝒞
– 𝒞 is called superfinite• Gold proved that a superfinite class cannot be learned
from positive data

– e.g. Σ = {𝑎}, 𝒞 contains all finite languages and {𝑎𝑛 ∣ 𝑛 ≥ 1}

• Although this fact shows a limitation, there still exist rich classes ofinteresting languages– For example, pattern language
33/34References• If you are interested in computational learning theory, thefollowing books might be interesting:– 榊原康文, 横森貴, 小林聡, 計算論的学習, 培風館, 2001
– S. Jain, D. N. Osherson, J. S. Royer, A. Sharma, Systems That Learn, A
Bradford Book, 1999

• These books are not necessarily for this lecture

34/34