What is a Morelli Number

HINT: A Morelli number has 7 binary digits.

Example	Morelli Number?
1 1 1 1 1 1 1	Yes
0 0 0 0 0 0 0	No
1 0 0 1 1 0 1	Yes
1 0 0 0 1 0 1	No

Some Sample Concepts

• Odd number of 1s: 1000000 v 0100000 v 0010000 v ...
• Middle digit is 1: 0001000 v 0011000 v 0001100 v ...
• Last digit is 1: 0000001 v 1000001 v 101010101 v ...
• Exactly three 1s: 1101010 v 1110000 v 0000111 v ...

Some Observations

• How many possible examples of Morelli Numbers are there? 2⁷ = 128
• How many possible concepts are there? 2²⁷ = 10³⁸

Concept Learning Algorithm

Primitive Hypotheses: We start with a set of primitive hypotheses:

• h1, hypothesis 1: Odd number of 1s
• h2, hypothesis 2: Middle digit is 1
• h3, hypothesis 3: Exactly three 1s
• h4, hypothesis 4: Last digit is 1

Representing a Concept To form a concept, we can combine these primitive hypotheses into any combination of the four. We can represent the hypothesis as a four-tuple, [h1,h2,h3,h4], where each of the h_i can be replaced by Y or N to indicate whether the primitive hypothesis is included or not. So [Y,Y,Y,Y] means h1 AND h2 AND h3 AND h4.

Example	Morelli Number?	[h1,h2,h3,h4]
1 1 1 1 1 1 1	Yes	[Y,Y,N,Y]
0 0 0 0 0 0 0	No	[N,N,N,N]
1 0 0 1 1 0 1	Yes	[N,Y,N,Y]
1 0 0 0 1 0 1	No	[Y,N,Y,Y]
1 1 1 1 0 0 1	Yes	[Y,Y,N,Y]
0 0 1 1 0 0 0	Yes	[N,Y,N,N]
0 0 1 1 1 0 0	Yes	[N,Y,Y,N]

Algorithm (Guaranteed to find most specific hypothesis)

1. Let ? mean any value is acceptable and 0 mean no value is acceptable.
2. Start with the most specific hypothesis: h₀: [0,0,0,0]
3. For each positive example, make h_i just more general enough to cover the positive example.
4. Ignore negative examples.

Result: [?,Y,?,?] (middle digit is 1) is a Morelli Number.

Some Observations

What if the correct concept was not among the hypotheses?

This algorithm assumes that the target concept is one of the primitive hypotheses. This is its inductive bias.

In general, inductive bias is any criterion the learner uses to constrain the concept space or to select concepts within the space.

Could we represent all possible concepts?

We can't represent all possible concepts if we restrict ourselves to h₁ AND h₂ AND h₃. For example, we can't represent the hypothesis "either a 1 in the first or the last digit but not both."

What if we could represent all possible concepts?

H = (x₁ OR x₃ OR x₆ OR x₇) AND NOT( x₂ OR x₄)

Here H represents all training examples we considered above. If we use AND, OR and, NOT we can represent every possible concept. But then we couldn't generalize (i.e., learn), because the concept is too specific.

Moral: Unbiased learning is impossible.

Without some a priori assumptions about the target concept, classification is impossible. Our algorithm assumes that the target concept could be represented by a conjunction of primitive concepts.