Pattern recognition as a noisy channel

• Many pattern recognition problems can be understood in terms of communication channels.

Pattern recognition as a noisy channel

• Many pattern recognition problems can be understood in terms of communication channels.

• Let's say we'd like communicate message from the set $A_x$

$$A_x = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$$

Pattern recognition as a noisy channel

• Many pattern recognition problems can be understood in terms of communication channels.

• Let's say we'd like communicate message from the set $A_x$

$$A_x = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$$

• Output of channel is a pattern of ink on paper

Pattern recognition as a noisy channel

• Many pattern recognition problems can be understood in terms of communication channels.

• Let's say we'd like communicate message from the set $A_x$

$$A_x = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$$

• Output of channel is a pattern of ink on paper

• The ink pattern is represented using 256 binary pixels, so output $A_y$ alphabet:

$$A_y = \{0, 1\}^{256}$$

Question:

• Estimate how many patterns in $A_y$ are recognizable as the character "2"

• OR Demonstrate the existence of as many patterns as possible that are recognizable as 2s

Intuition

• Remember bent coin lottery?

Intuition

• Remember bent coin lottery?

• Lottery ticket number is generated by tossing a bent coin (with $P_1 = 0.1$) 1000 times

Intuition

• Remember bent coin lottery?

• Lottery ticket number is generated by tossing a bent coin (with $P_1 = 0.1$) 1000 times

• If you are allowed to buy only one ticket, which ticket would you buy?

Intuition

• Remember bent coin lottery?

• Lottery ticket number is generated by tossing a bent coin (with $P_1 = 0.1$) 1000 times

• If you are allowed to buy only one ticket, which ticket would you buy?

• The ticket with all 0's

Intuition

• Remember bent coin lottery?

• Lottery ticket number is generated by tossing a bent coin (with $P_1 = 0.1$) 1000 times

• If you are allowed to buy only one ticket, which ticket would you buy?

• The ticket with all 0's

• Next most probable ticket?, ticket with one "1"

Solution

• Intuition from bent coin lottery can be applied to our problem

Solution

• Intuition from bent coin lottery can be applied to our problem

• We have total of $2^{256}$ possible patterns in $A_y$

Solution

• Intuition from bent coin lottery can be applied to our problem

• We have total of $2^{256}$ possible patterns in $A_y$

• To estimate number of pattern recognizable as "2", we focus on biggest contributing terms

Solution

• Intuition from bent coin lottery can be applied to our problem

• We have total of $2^{256}$ possible patterns in $A_y$

• To estimate number of pattern recognizable as "2", we focus on biggest contributing terms

• Here it will recognizable "2" made with least number of available pixels: $7 \times 6$

Number of places where we can place the "2" patch in $16 \times 16$ space

Number of places where we can place the "2" patch in $16 \times 16$ space

• Along rows upto 12th element as last column is empty

Number of places where we can place the "2" patch in $16 \times 16$ space

• Along rows upto 12th element as last column is empty

• Along columns upto 11th element as last row is empty

Number of places where we can place the "2" patch in $16 \times 16$ space

• Along rows upto 12th element as last column is empty

• Along columns upto 11th element as last row is empty

• That gives is us total of $12 \times 11$ possible option for placement

Leftover pixels and white/black border

Leftover pixels and white/black border

• As patch size is $7 \times 6 = 42$ we have $256 - 42 = 214$ pixels leftover

Leftover pixels and white/black border

• As patch size is $7 \times 6 = 42$ we have $256 - 42 = 214$ pixels leftover

• These can be set arbitrarily, i.e total of $2^{214}$ possible values

Leftover pixels and white/black border

• As patch size is $7 \times 6 = 42$ we have $256 - 42 = 214$ pixels leftover

• These can be set arbitrarily, i.e total of $2^{214}$ possible values

• We assumed "2" with white border, calculation remains the same for "2" with black border (i.e just to $\times 2$)

Calculation

• Estimate for total number of recognizable "2" patterns

Calculation

• Estimate for total number of recognizable "2" patterns

• Total number of places "2" patch can be places $\times$ Number of choices for leftover pixes $\times$ 2 (for black border)

Calculation

• Estimate for total number of recognizable "2" patterns

• Total number of places "2" patch can be places $\times$ Number of choices for leftover pixes $\times$ 2 (for black border)

$$12 \times 11 \times 2^{214} \times 2 \approx 2^{222}$$

Can there be other recognizable patterns is small patch of "2"?

Can there be other recognizable patterns is small patch of "2"?

• Consider fraction $\frac{2^{222}}{2^{256}} = 2^{-34}$

Can there be other recognizable patterns is small patch of "2"?

• Consider fraction $\frac{2^{222}}{2^{256}} = 2^{-34}$
• If we consider probability of other remaining 9 recognizable patterns in a small patch of "2"

Can there be other recognizable patterns is small patch of "2"?

• Consider fraction $\frac{2^{222}}{2^{256}} = 2^{-34}$

• If we consider probability of other remaining 9 recognizable patterns in a small patch of "2"

• Of all possible "2" patches only $9 \times 2^{-34}$ fraction could have other recognizable pattern

Can there be other recognizable patterns is small patch of "2"?

• Consider fraction $\frac{2^{222}}{2^{256}} = 2^{-34}$

• If we consider probability of other remaining 9 recognizable patterns in a small patch of "2"

• Of all possible "2" patches only $9 \times 2^{-34}$ fraction could have other recognizable pattern

• This proves very very small fraction of remaining 214 pixels can have any other recognizable pattern