NYCU - ML Homework2   - Solved

1. Naive Bayes classifier 
Create a Naive Bayes classifier for each handwritten digit that support discrete and

continuous features. 

            Input: 

1.    Training image data from MNIST 

 You Must download the MNIST from this website and parse the data by yourself. (Please do not use the build in dataset or you'll not get 100.) Please read the description in the link to understand the format. 

 Basically, each image is represented by bits (Whole binary file is in big endian format; you need to deal with it), you can use char arrary to store an a image. 

     There are some headers you need to deal with as well, please read the link for more details. 

2.    Training lable data from MNIST. 

3.    Testing image from MNIST 

4.    Testing label from MNIST 

5.    Toggle option 

 0: discrete mode 

1: continuous mode 

 

TRAINING SET IMAGE FILE (train-images-idx3-ubyte) 

offset 
type 
value 
description 
0000 
32 bit integer 
0x00000803(2051) 
magic number 
0004 
32 bit integer 
60000 
number of images 
0008 
32 bit integer 
28 
number of rows 
0012 
32 bit integer 
28 
number of columns 
0016 
unsigned byte 
?? 
pixel 
0017 
unsigned byte 
?? 
pixel 
... 
... 
... 
... 
xxxx 
unsigned byte 
?? 
pixel 
 

TRAINING SET LABEL FILE (train-labels-idx1-ubyte) 

 

offset 
type 
value 
description 
0000 
32 bit integer 
0x00000801(2049) 
magic number 
0004 
32 bit integer 
60000 
number of items 
0008 
unsigned byte 
?? 
label 
0009 
unsigned byte 
?? 
label 
... 
... 
... 
... 
xxxx 
unsigned byte 
?? 
label 
The labels values are from 0 to 9. 

 Output: 

Print out the the posterior (in log scale to avoid underflow) of the ten categories (0-9) for each image in INPUT 3. Don't forget to marginalize them so sum it up will equal to 1. 

  For each test image, print out your prediction which is the category having the highest posterior, and tally the prediction by comparing with INPUT 4. 

 Print out the imagination of numbers in your Bayes classifier 

For each digit, print a   binary image which 0 represents a white pixel, and 1 represents a black pixel. 

The pixel is 0 when Bayes classifier expect the pixel in this position should less then 128 in original image, otherwise is 1. Calculate and report the error rate in the end. 

 Function: 

1.    In Discrete mode: 

  Tally the frequency of the values of each pixel into 32 bins. For example, The gray level 0 to 7 should be classified to bin 0, gray level 8 to 15 should be bin 1 ... etc. Then perform Naive Bayes classifier. Note that to avoid empty bin, you can use a peudocount (such as the minimum value in other bins) for instead. 

2.    In Continuous mode: 

  Use MLE to fit a Gaussian distribution for the value of each pixel. Perform Naive Bayes classifier. 

 

 

40 
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 
 
41 
 
42 
 
43 
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 
 
44 
0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 
 
45 
0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 
 
46 
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 
 
47 
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 
 
48 

49 
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 
 
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 
 
50 
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 
 
51 
0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 
 
52 
0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 
 
53 
 
54 
 
55 
0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
56 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
57 
 
58 

59 

60 
 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
                                                                                                                 

    ... all other imagination of numbers goes here ...         

                                                                                                                 

   9:                                                                                                                                   

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
61 
 
62 
 
63 
 
64 
 
65 
 
66 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
67 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
68 

69 

70 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 
 
71 
 
72 

73 
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 
 
0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 
 
74 
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 
 
75 
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 
 
76 
0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 
 
77 
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 
 
78 
0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 
 
79 

80 
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 
 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 
 
81 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 
 
82 

83 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 
 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 
 
84 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
85 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
86 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
87 
 
88 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
 
 
 

2. Online learning 
Use online learning to learn the beta distribution of the parameter p (chance to see 1) of the coin tossing trails in batch. 

        Input: 1. A file contains many lines of binary outcomes: 

          

 

2.    parameter a for the initial beta prior 

3.    parameter b for the initial beta prior 

                                   Output: Print out the Binomial likelihood (based on MLE, of course), Beta prior and posterior

 

 

5 

6 
 

case 2: 0110101 
7 
Likelihood: 0.29375515303997485 
8 
   Beta prior:     a = 11 
b = 11 
9 
Beta posterior: a = 15 
b = 14 
10 

11 
 

case 3: 010110101101 
 
12 

13 

14 

15 

16 

17 

18 

19 

20 

21 

22 

23 
Likelihood: 0.2286054241794335 
   Beta prior:     a = 15 
b = 14 
Beta posterior: a = 22 
b = 19 
 
 
case 4: 0101101011101011010 
Likelihood: 0.18286870706509092 
   Beta prior:     a = 22 
b = 19 
Beta posterior: a = 33 
b = 27 
 
 
case 5: 111101100011110 
Likelihood: 0.2143070548857833 
   Beta prior:     a = 33 
b = 27 
24 
Beta posterior: a = 43 
b = 32 
25 
 

case 6: 101110111000110 

Likelihood: 0.2065976052
9408 
26 
27 
28 

29 

30 

31 

32 

33 

34 

35 

36 

37 
   Beta prior:     a = 43 
b = 32 
Beta posterior: a = 52 
b = 38 
 
 
 
 
case 7: 1010010111 
 
Likelihood: 0.25082265600000003 
   Beta prior:     a = 52 
b = 38 
Beta posterior: a = 58 
b = 42 
 
 
 
 
case 8: 11101110110 
 
Likelihood: 0.2619678932
864457 
38 
   Beta prior:     a = 58 
b = 42 
39 
Beta posterior: a = 66 
b = 45 
40 

41 
 

case 9: 01000111101 
 
42 
Likelihood: 0.23609128871506807 
43 
   Beta prior:     a = 66 
b = 45 
44 
Beta posterior: a = 72 
b = 50 
45 

46 
 

case 10: 110100111 
 
47 
Likelihood: 0.27312909617436365 
48 
   Beta prior:     a = 72 
b = 50 
49 
Beta posterior: a = 78 
b = 53 
50 

51 
 

case 11: 01101010111 
 
52 
Likelihood: 0.24384881449471862 
53 
   Beta prior:      a = 78 b = 53 
 

 


3. Prove Beta-Binomial conjugation 
 

Try to proof Beta-Binomial conjugation and write the process on paper. 

※ You should write down the proof process on paper and take a picture. When you hand in HW02, it must contain your code and picture. 

 

 Use whatever programming language you prefer. 


  HW02 must contain your code and proof process (can be .pdf or any image format).