class: theme layout: true --- class: center, middle # Exercise 9.19: Pattern recognition as a noisy channel  2020-04-03 - Saurabh B --- class: middle ### Pattern recognition as a noisy channel * Many pattern recognition problems can be understood in terms of communication channels. ??? We'll consider the case of recognizing handwritten digits here -- * 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\\}$$ ??? this message will be input to our channel Q -- * 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}$$ --- class: middle, center ### Example of element from $A_y$  --- class: middle, center ### Example of element from $A_y$  --- class: middle, center ### Example of element from $A_y$  --- class: middle, center ### Example of element from $A_y$  --- class: middle ### 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 --- class: middle ### 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 ??? The ticket with all 0's, considering chances of getting 0 with each toss is much higher -- * Next most probable ticket?, ticket with one "1" ??? following this method, we can find out what tickets can give us best chance of winning upto certain probability --- class: middle ### 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$ --- class: middle, center ### Smallest ($7 \times 6$ ) patch of non-confusable "2" with white border  --- class: middle, center ### Complete $16 \times 16$ space  --- class: middle ### 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 --- class: middle ### 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$) --- class: middle ### 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}$$ --- class: middle ### Can there be other recognizable patterns is small patch of "2"? -- * Consider fraction $\frac{2^{222}}{2^{256}} = 2^{-34}$ ??? small fraction which is number of "2" patterns out of all possible patterns -- * 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 --- # Thank You! # Thank You! # Thank You! ---