This assignment is for Introduction to Data Science, this category was not available in the computer science section. The closest option to Data Science was Data Structures.
Homework 4 CS 301 (001), Fall 2022, Introduction to Data Science Due Date: Dec 9 (Friday), 11:59 PM (EST) This homework will focus on understanding and implementation of algorithms relevant to online learning. The dataset we will use is hw4.txt. It consists of T = 103 lines, and each line t ∈ [T ] .= {1, 2, . . . , T} has a binary string of length m = 16, which is followed by a binary value. Please try to interpret the binary string on line t as the predictions from all the m = 16 experts at day t. In other words, the binary string is the vector et = {e1,t, e2,t, . . . , em,t}, where ei,t refers to the prediction of expert i at time t for all i ∈ [m]. The last binary value on line t is rt, i.e., the true value at the time t. 1 Please implement and run the following heuristic policy π to the dataset hw4.txt, where π will make a decision during time t as follows. Let St be the set of experts who have made the fewest mistakes so far during the first t − 1 days with S1 = {1, 2, . . . ,m}. The policy π will follow the majority vote among all experts in St and break the tie arbitrarily if any.1 Please state clearly (1) your pseudo codes and (2) the number of mistakes your algorithm makes at the end of T . (30 points) 2 Please implement and run the Weighted Majority algorithm with η = 1/3, denoted by WM, to the dataset hw4.txt. Please state clearly (1) your pseudo codes, and (2) the number of mistakes your algorithm makes at the end of T , and the exact value of the regret bound shown in the class. Note that to compute the regret bound explicitly, you need to compute Ri∗(T ), which denotes the number of mistakes made by the best expert i∗. (40 points) 3 Please implement and run the Randomized Weighted Majority algorithm with parameter η = 0.1, denoted by RWM(η), to the dataset hw4.txt. Please state clearly (1) your pseudo codes, and (2) the expected number of mistakes your algorithm makes at the end of T , and (3) the exact value of the regret bound presented in the class. For part (2), please run the algorithm to the input instance independently for k times and take the average as the final output, where you can choose a proper integer k from {10, 11, . . . , 100}2. For part (3), you need to compute Ri∗(T ), which denotes the number of mistakes made by the best expert i ∗. (30 points) 1Note that St may change as time t ∈ [T ]. Specifically, it is even possible that St ∩ St′ = ∅ for some t 6= t′. 2Please choose an integer value k as large as possible if the running time is acceptable to you. 1 0111110100101110 1 0110111001101011 1 0001001100000000 0 0101110000001110 1 1001110101110001 0 1001011111101001 0 0011101100000101 1 0010010000000000 0 1001100000111100 0 0110101010001110 1 1110010100100111 0 0001110100111100 1 1101111011010011 0 1100101111001101 0 0011101111000110 1 0011110001111001 1 1100101100100000 1 0001001100010111 0 1010110000011110 1 0011001010111110 0 0101001100001111 0 1110100101001011 0 1010001011101001 0 1010001001100101 1 0011001011101100 0 1000001010011100 0 0100111110101001 1 1011111000100010 1 0011011110110100 0 0000000010111001 0 0111001011011101 1 1110110000011011 1 0000011110011101 0 1010010111010110 0 1100011011001011 1 1100001011110111 0 0001011101000011 0 1001111101101101 1 0010111011111100 0 0110000000100110 0 1101000010101001 0 0000110100010111 0 1100101011000110 1 0000010111011011 0 0010101111101000 0 0101101110100100 1 0000001111101100 0 0011011110100001 0 1000100111001110 1 0100110101101101 1 1011010110000111 1 0000001000011110 0 0110101100101101 1 0000011111110101 0 1001100101110110 1 0101110011100100 1 0010111111001100 1 1101001011011000 1 0010100101000000 1 0110110011010011 1 1100111111000110 1 0000111001110010 0 1010010111011001 0 0100101010111010 1 1111000011010111 0 1011100010100101 1 0111110010001110 1 0110011100000100 0 0100001100000010 1 0111000001110101 0 1000000000000110 0 1100101111100110 1 1101011111011101 1 1110000111011101 0 1001001011111110 0 1100100000101110 0 0100011110001011 0 0000001001000110 0 0001111100111100 1 0010011100110001 0 1000111111101010 1 1110110000100001 1 1001111010011011 1 1110001101110010 0 0101111100010000 1 1100111011001110 1 0000001001101000 1 0000100010001110 0 0110011000101100 0 0100100001111111 1 0110101010111101 1 0011010101110010 0 0110101010101111 1 0010000011100010 1 1100001001100000 1 0001001111001011 1 1010100111101100 1 1101001110001111 1 0101111011110100 1 0000011010100000 1 0000110101010010 1 1111111010011010 1 1100000101010011 0 0011001101110100 1 0101101010011100 1 0010111110110101 1 0101010110010001 0 0011011010001111 0 1100111100000011 1 0110100010010010 1 1011000110101010 0 0000100010110011 1 1110011101111010 0 0011010101101001 0 1000001011010001 0 0111011000000000 1 0010100100110110 1 0101001110010000 1 1001010101100011 0 1110011110110110 0 1001001100101111 1 0000001010101000 1 0111101000000100 1 0110101000000111 1 1001101111111110 1 1001011101010101 0 1011011100001101 0 1110001000100100 0 0001010011011011 0 0110010111010011 0 0001001111100111 0 0100111000000111 1 1101110001111111 0 0100010001100111 1 1011110110100101 0 0101010100101101 1 1100011110010110 0 0110111011000011 0 1110100000110101 1 0110100101011010 0 0110011010001101 0 0010001001011001 0 0010111001101011 1 1010010010001011 0 0011100000100101 1 1001111111111101 0 0101100011111111 0 1011110011100110 1 0111100011110111 1 1101011011110010 0 0000101111000010 0 0000101000110101 1 0110011000010011 1 1110001000001011 1 1001100110100001 1 1110110011110111 0 0110000001110100 0 1111101110101101 1 0111111010010011 1 1111000101100010 0 0001101010101010 0 1001000111010101 0 1101110110111100 0 1100110001101110 1 1110101101110111 1 1011100000010010 1 0101000010101111 0 0011101111100011 0 1011110110000010 1 0011010001010100 0 0110001101111110 1 0011001000001101 0 1010110011110110 0 0101110100110010 1 0000010110110101 0 0111011100001110 1 0111100001101111 1 1110011010100101 0 0110000111010101 0 1011001010001001 1 0110101010111100 1 1100001010101010 1 1000011000100100 1 0101111011101111 1 0101111011001010 1 0101000001010100 0 0110110110000110 1 1001010001001000 0 0010111010101110 1 1010000011000010 0 0010000101010001 0 0001011101001001 0 1101010101100101 1 1011100101100001 1 0010110111111100 1 0001011110100100 0 1100100011011111 1 0101000011001101 0 1001010011110000 1 0010010111001000 0 1010110100100000 1 1001100100101000 1 1110101100101010 1 1100111101101111 1 1100100010111000 1 0110000010100001 0 0100000000001001 0 0101110101001110 1 0100111100000010 1 0001100110111100 1 1001101001011111 1 1100010001110011 0 1011000110011011 0 0100001000101111 1 0010001100011110 1 0101001101100111 0 1101000010110010 1 0010111011011101 1 1000111110011010 1 0011100011010000 1 0110110011100110 0 0010100011111001 1 0111000111001001 0 0000100001101100 1 0010001001000101 0 0010010100011100 0 1101010010100000 0 1110011110000010 0 1100010011001100 1 1011001101011111 0 1110011110000011 0 0011011110110100 0 0010011110001110 0 1100001001001011 0 1001000110101000 1 0001110001000001 0 0011101011010001 1 0011001100101010 1 0101001110100111 0 1010101110101100 1 1110010101001001 0 1001101111010110 1 0001100110101010 1 0100000011011100 1 1111001111000101 0 1011011011011010 0 1101111001101000 0 1110101101000110 0 1010011001101110 0 1000010011000100 0 1000001010001001 0 0000000010100100 1 1111010000110010 0 0010111001011101 1 1101000001001101 0 0010100000010110 0 1011011000111101 1 1001111001111001 1 1110010111000010 0 0100111010111001 0 1011111101110101 1 1111101110011001 0 1001001001000110 0 1001011011111000 1 0101001110101010 0 0101010100101101 0 1010111010001111 1 1111011111000111 0 0010010000101111 0 1100011111000001 1 1101110110100101 1 0111010011010010 0 0100101110111000 0 1110000011100100 1 0100100010000100 1 0000000100100101 0 1110010110010100 0 1100101100001011 1 0000010111000011 0 1110100010010101 1 0110000001111110 0 1111001100011111 0 1111111010100100 0 0100101010100111 1 0001000111001110 0 0111100011110110 1 0110000101110110 0 1001000011001001 0 0000101111100001 0 1000101011001100 1 1110110100100110 0 0011010000111101 0 0111111011100010 1 0111001001111110 1 0000111101011010 0 0011001001000101 0 0000101001000110 0 0101001010110110 0 0010001101011001 1 0110110000011111 1 1011010100110000 0 1111111101000010 1 1000011101011000 0 1101110111010110 1 0011011010100010 0 0011110100101011 1 0111011010010111 0 1101110100001000 1 1110111100011011 1 1100101100111101 1 0010101111111111 1 1100100010011110 1 1101100010100111 0 0101100011100101 0 1110000101000100 0 0111111111101001 0 0001110101011011 1 0010111011001011 1 1100001000110110 0 0001111111101111 1 1110100110111110 1 1001101000100000 1 1101110110111011 1 1101100010000000 0 1000010001010010 0 1011111110000001 1 0001011010001001 1 1000001010000010 1 1100110011101101 1 1100111100110100 0 1101110100010010 1 1001011001011100 1 0000010111100010 1 1111100000100101 1 1000000101000100 0 1011101101100001 0 0111011100001100 0 1110001100010101 0 0001010011010011 0 1010011100011000 1 1100001001111001 0 0001001110100101 0 0011010110001110 0 1011010010000111 0 0000101100110111 1 0111010111100011 0 1101000010011101 0 1100011101111010 1 0110111101101110 1 1000001000001111 0 0000000011011001 0 0011010000000011 0 1110101111110111 1 1010010101100111 0 0001101001010000 1 1110001111001111 0 0001101110100001 0 1010111101010010 1 1100000110001110 0 1110101000111001 1 1101010100001000 0 0011000100111000 0 0000101010110000 1 0101011000100001 1 1100111110000101 1 0001000010101001 0 1000110011110010 0 1000000101101001 0 0001011001101001 1 1001111100011100 1 1101100001111111 0 1101101101101110 1 0110101011000011 1 0100111000100101 1 1000010111110110 0 1100110001010010 1 1110011000010110 0 1001110010111010 0 0110000111011101 0 0010100011010111 1 0110100001000101 0 1110000000100101 0 1000001100010111 1 1110100100100101 1 1101010010111000 0 0110111011110011 1 0111001000101111 1 0000101111001100 0 1010000000101110 0 1101000001101111 0 1100011010110001 0 0110001000111111 1 1001100101110011 0 0001111001000011 0 1101111100010011 1 0110100101000110 1 1101011001100000 0 0010111010101110 1 1101100111000011 1 1100111100111001 1 0101110111111111 1 1000010100101101 0 0000101110001110 1 0101101000010110 1 1110000110100111 0 0010000100111000 0 1000100100011110 0 1000001111001010 0 1111101101111000 1 0011111110010101 1 0000011000111010 0 1001000110111000 0 1011010001111011 0 0000011100111111 0 0010010010011101 0 0111010010000110 1 0101000010000010 0 1111101010010001 1 0110001001110001 0 1001100000010011 1 1011101101100011 1 1000111011101101 0 1010101000111111 0 0000010001100111 0 0000101110010111 1 0011011110100111 0 0011011000010000 0 1001010010101111 0 0110101100001111 1 1011001001011011 0 1110101011110110 1 1011110011011110 0 1000001100111010 0 0010101011100011 1 1010110101111100 1 0000010110110100 0 1101001111100111 0 1001010100111111 0 0010001110000011 0 1010010001010100 0 0100011001000111 1 1010001110110001 0 0001001011010011 0 1101100111010110 1 1111011001101111 0 0110101010101111 1 0010100101011111 1 0101100110010000 1 1101100000001001 1 1100101110000110 1 1010010001011000 0 0011000000001110 1 1001000001000010 0 1000100000010011 1 0110111011111011 1 1101000010011111 1 0111111000110011 0 0100100101011101 1 0001100110010111 0 0001010100000101 0 0101011110110111 0 1100110001011111 1 1000110110011100 1 1101000101001000 1 1000101101110000 1 0000001010001101 0 1000000101000101 0 1100111001110110 0 0110110110000110 1 0111010001110000 0 1100010010000110 0 0100000111101111 0 1100010010010011 0 1011110011110001 1 0100000000011011 0 1110110010110001 1 1010111111111010 1 1011100010001000 1 0111100001100100 1 1001010001101101 0 0111000101110100 1 1011101111101001 1 1100101111110111 0 1001101011010111 0 1000000011010000 0 0011100101100010 1 0000100011011011 1 1100001010001101 0 1111100011010011 1 0100011101011101 0 1011101011001001 1 0010010111111101 0 0110011001111101 0 0001010101000110 0 0100100100110000 1 1001000011001100 0 1110010110101001 1 0100101000111100 1 1110010010011001 1 0101100110010010 1 1011000010010001 0 0001010010100001 0 1001000101000011 0 1100010000101111 0 1110110110010110 0 0111110011011011 1 1110101000011000 1 0001010111100011 0 1111001110111001 0 0011011000100100 0 1110110101000011 0 0001110001111110 1 1110000101001110 0 0100000101000001 0 1100101001011100 1 1111001011110011 0 1111011110100111 0 0010110011100010 1 1001010111101010 1 0001010010101001 0 1110100001001001 1 1101010111010100 0 1100000111010110 0 0100010000011111 0 0000011001111110 1 0101111111001010 1 1001111100001101 1 0100010100010101 1 0010011100101000 0 1110100010000010 1 0010000000011000 0 1100101000000011 0 1111001001111111 0 0000010011001101 1 1111100011111111 0 0000011001111000 1 0010011001101010 1 0110111011101000 1 1101011101010110 0 1011001110111111 0 1101000111001100 0 0101000000110010 0 1111000100101100 0 0000100111010111 0 0010010101110001 0 1001011110010101 0 0011000011001110 1 0011100100101001 1 1010110011101010 1 1100111000100101 1 0110111111011010 0 1100000101100111 1 1010110100000000 0 1100110111001111 1 1010001010111100 0 0001000000011111 1 1101010101100111 1 0111001000111111 1 0011001100001100 0 1111100010011010 0 0110000111010011 0 0000100000010101 0 0010000110110011 0 0100000101000011 1 0111110010011001 1 1110100101111000 1 1110001000111100 0 1111111001101001 0 0101010101001111 0 1111110100000011 1 0011101010101111 1 1010101111010111 1 0001110101000011 0 0000000101101101 0 1011101011101101 0 0000110000101101 0 0011011101000111 0 0101010001111101 1 0010101111100111 1 0010111100100011 1 1000111100110010 1 1111101001000001 1 1011101110111101 0 0111011011011001 0 0000000011011100 1 0100110110100001 1 1010000010001011 1 1110111011001101 1 0001101100011100 1 0101100010001010 1 1111100110100001 1 1101011100001111 0 0111000010111011 0 1110001101011010 0 1001011110011110 0 1110101011001010 0 0011000100101010 0 0000010001000111 0 1111000100001110 0 0011100010001101 0 0011110000001010 1 0001111110011100 0 0110100000111001 1 0100010010000111 0 0000001110100000 0 1111111110100011 1 0000001110001100 0 0000100011100000 1 1010100001000100 0 0011000010001001 0 0100011010001100 0 1001101001010100 1 1110100001111111 1 1110110011011000 1 1101101011111010 0 1000100010100000 1 0010110010100111 0 1100010001010000 0 0101101011010000 0 0101100010001110 1 1001000000001000 0 1111000001101101 0 1001011001111110 0 0110001111011011 0 0110000010110000 1 1000110010001011 1 1011110010111110 1 0100111000110110 1 0111101010101101 1 0010000110101110 0 1101000110110100 0 0010100110101111 1 1000011010001100 0 0001010111100101 0 0011110000001000 0 1111110100011001 0 0101011011000001 0 1010110100001000 1 1011010011100010 0 0110011000111010 0 0000101110011101 1 1010111111111000 0 1010011000011001 0 1010110100010111 0 0111011011001001 0 0011110110011001 1 1011110110111010 1 1010110111101000 1 1010010110100100 0 0111001001100010 1 0011111001001011 1 0000001010110101 1 0001010111101110 0 0101111001100010 1 0110000010100010 0 1100111111001010 0 0111111100000100 1 1000110101110000 1 0001100001011010 1 1010100000001100 1 0110011001000111 0 0110101101110111 0 0110101010011100 1 0000111100000110 0 1010001010100010 0 1000000001100110 1 0101000001011110 1 0100010111110100 1 1111011100001000 0 1110110011010100 1 0000010000101110 0 1001011100111010 1 0110111011110101 1 1110011100011111 1 0000010110100001 0 0000001000001101 0 1011001110100010 0 1011101001101010 1 1010111111010011 1 0111001011111010 1 0000011011100001 0 1000100111100001 0 0110100100010101 1 1110011011110111 0 0011101111001111 1 0110000011011100 1 0111111001011111 1 0101000010110010 0 1011001010010001 0 0011100101101100 1 0000011001101101 0 0110010100110100 0 0101100101011100 1 1101101001010110 1 0010010111010110 0 1100001101101010 0 0001101110010001 1 0100010100000110 0 0000001011001101 0 1110001111101001 0 1010010110110100 0 1001011110001001 0 1001101000010010 1 1111000011101110 0 1111000001001100 0 1000110110000110 0 1001111011101011 0 0000010001111111 1 0110101011100100 1 1010010001101000 1 1101101010000001 0 0000000011101110 0 1100001110101110 0 1001101011110001 1 0111001100101110 0 1101010110010000 0 1101010111111011 1 0100011100000000 1 0111011001001000 0 1110101010111001 1 1101011001000111 0 1101011100011110 0 0010101101000111 0 1001100100001000 1 1101000111111010 1 1001001110100100 0 0100001100001001 0 1110001010010110 1 1101100001011100 1 1001110110101111 1 0111111010110111 1 0100000010111000 1 0011000101000101 0 1001000000000011 0 0100010011011001 0 0110100010110100 1 1101101101011101 1 1010111110001110 1 0110110011010010 0 0100000010101101 0 0001001100111001 0 0101011001110010 0 1010111000010110 1 1011101110000010 0 0111110111111000 1 1001000011000000 0 0001001101100101 0 1110010000001000 1 0101111010100100 1 1110100011111101 0 1100000101011100 0 1110101100000100 1 1101111101011000 1 0110111011001111 1 0001100111111010 1 1010110001110011 1 1001100010100111 1 0001001111001000 1 0010001010110100 0 1101111000100111 1 1010000011000100 1 0101011001101110 0 0000110010011100 1 0111000110001100 0 0110001110001110 1 0001001001100001 1 1101100110000111 1 1101011111100011 0 1100000111011100 0 0111001001100100 1 1010111011011010 1 1011011100100110 1 1000011001010110 0 0001011110011101 1 1110001001101010 0 0000101010101001 1 1011010101011110 1 0111010100001110 0 1010110000111000 1 0000111011100111 1 1110011001010001 0 0101011100001001 0 0110101001001101 0 1100000010100010 0 0110111100000011 1 1000000001100011 0 0011101111100001 1 1100011000011100 0 1001010110000011 0 0101111000111010 0 1100111100110101 1 1111100000110110 1 1101110001110001 1 1111100101010000 1 1000110011011101 1 1001111011000010 1 1011100011010010 1 0011001100011011 0 0101010111101111 0 1000000000011100 0 0000100011111110 1 0010001001011010 0 0110101101010100 1 0110111101110110 1 0010010000001110 0 1111101011011110 1 1110110000000011 0 1110101010100010 1 1110111110001000 0 0111000101111110 0 1011111101001001 1 1111111111111110 1 1000001010001000 0 0100111110111001 1 0010111100001001 1 0000111100101101 0 0100010101010010 1 1110010110001001 0 1101110110110011 1 0110001000010110 0 1000111010100010 0 1111101011101101 1 0100111011101111 1 1101100010110100 0 1101101110011100 1 1101011100011010 0 1010001101011001 0 0011100111101110 1 1100100111000110 1 0011110010000010 1 1001011100111001 1 1001110010110011 1 0110101110001000 1 1110000110101111 1 1101001101010001 1 1011100110110010 1 1111001000111111 1 1101000010000110 1 1101100100000001 1 1101110100101011 0 1100000101100001 1 1010001111111000 1 1110110111010010 1 0000011001100101 1 1000110001111111 1 0011100010100110 0 1111000100001000 1 0110101000010000 1 0111110001110101 0 0111001001111000 0 0000000110110100 1 0101100101100111 1 0011011111110110 0 1000111001111110 1 1000001001010001 1 0011011010011110 1 0100011100101000 0 1111101001010011 1 1011011100101101 0 1101100010100011 1 0011111110101000 1 0100010001001001 0 1000011000101011 0 0000111110010000 0 1000011011000010 1 1011100100111110 0 0110011101100110 1 0011100000100110 0 0000001101101101 0 0000101100101011 1 1010111010100111 1 0111101100011000 0 0111100011010101 1 0100011010111100 0 1011101111011011 1 1111011110110110 1 1001000111110101 0 0111101010010101 1 1110101011110100 1 0111011101010100 1 0101011001110000 1 0000001000010010 0 1001100001111000 1 1101111001001111 1 0110011000000010 0 1110011110111110 0 1111010101100011 0 1010111101101101 1 0110011011010111 1 0001100010011100 0 0000100011000100 1 0110000011100101 1 1011001010111101 0 0000100111010001 1 1010010101100100 1 1000101011100010 1 1100100101110111 0 1111000011011011 0 0010010010101010 1 1000011101000111 0 1101000011110101 0 1100011110110111 0 1011000100110001 0 0101110100101100 1 1101000001111111 0 0000110111000101 1 0010001110111000 1 0100111010010111 0 0101110000010101 1 0000000010111010 0 1010001100101010 0 1001101100110101 1 1100110111001110 1 1100010100100000 0 1110111000100101 1 0001010111001111 0 1000100010100000 0 0010110001110010 1 1100111100010011 1 0111000001001001 1 1001111101001010 1 1111001100100011 1 0110101010000100 0 0011011001111000 0 0100101000011111 1 0111000010101000 0 1010001100110110 0 0100001111001001 0 1110000001010001 0 0001010000111001 1 0000100011000001 0 0100010000100011 0 0101011010011010 1 0000100011001101 1 0011100100001010 1 1110110111001000 1 1100111001011010 1 1101110101101001 0 0001111011000100 1 1110101111110011 1 1100110110011110 0 0100000111101001 0 0111000100001001 0 1011001011110111 0 0001011011100001 1 1011001001111100 0 1010010001011010 1 0111110110001001 1 1101000101001011 1 0111111101101001 1 1100011000001011 1 1100011101001010 1 0111000101101000 0 1011001000110101 0 0011011111010100 0 0101101111000001 1 0010011010110101 1 1000101000001100