<jupyter_start><jupyter_text>MIT 6.036 Spring 2019: Homework 2This colab notebook provides code and a framework for problems 7-10 of [the homework](https://openlearninglibrary.mit.edu/courses/course-v1:MITx+6.036+1T2019/courseware/Week2/week2_homework/1).  You can work out your solutions here, then submit your results back on the homework page when ready. **Setup**First, download the code distribution for this homework that contains test cases and helper functions (such as `positive`).Run the next code block to download and import the code for this lab.<jupyter_code>!rm -f code_for_hw02.py*
!wget --no-check-certificate --quiet https://introml_oll.odl.mit.edu/6.036/static/homework/hw02/code_for_hw02.py
from code_for_hw02 import *
help(tidy_plot)<jupyter_output>Help on function tidy_plot in module code_for_hw02:

tidy_plot(xmin, xmax, ymin, ymax, center=False, title=None, xlabel=None, ylabel=None)
    Set up axes for plotting
    xmin, xmax, ymin, ymax = (float) plot extents
    Return matplotlib axes<jupyter_text><jupyter_code>def test(a):
  return a + 53
def methodB(a):
  return test(a)
def someMethod():
  test = 7
  return methodB(test + 3)
someMethod()<jupyter_output><empty_output><jupyter_text>**7) Implement perceptron**Implement [the perceptron algorithm](https://lms.mitx.mit.edu/courses/course-v1:MITx+6.036+2019_Spring/courseware/Week2/perceptron/2), where* `data` is a numpy array of dimension $d$ by $n$* `labels` is numpy array of dimension $1$ by $n$* `params` is a dictionary specifying extra parameters to this algorithm; your algorithm should run a number of iterations equal to $T$* `hook` is either None or a function that takes the tuple `(th, th0)` as an argument and displays the separator graphically.  We won't be testing this in the Tutor, but it will help you in debugging on your own machine.It should return a tuple of $\theta$ (a $d$ by 1 array) and $\theta_0$ (a 1 by 1 array).We have given you some  data sets in the code file for you to test your implementation.Your function should initialize all parameters to 0, then run through the data, in the order it is given, performing an update to the parameters whenever the current parameters would make a mistake on that data point. Perform $T$ iterations through the data.<jupyter_code>import numpy as np
print(data1, labels1)
ax=tidy_plot(-10,10,-10,10)
print(data1.shape)
print(labels1.shape)
plot_separator(ax,np.array([[3],[3]]),1)
plot_data(data1,labels1,ax)

def perceptron(data, labels, params = {}, hook = None):    
    # if T not in params, default to 100
    T = params.get('T', 100)
    # Your implementation here
    d, n = data.shape
    theta = np.zeros((d,1))
    theta_0 = np.zeros(1)
    print("d = {}, n = {}, theta shape = {}, theta_0 shape = {}".format(d,n,theta.shape,theta_0.shape))
  
    for t in range(T):     
      for i in range(n):
        y = labels[0,i]
        x = data[:,i]
        
        a = np.dot(x,theta)+theta_0
        #print("a = {}".format(a))
        positive = np.sign(y*a)
        
        if np.sign(y*a) <=0: # update the thetas
          theta[:,0] = theta[:,0]+ y*x
          theta_0 = theta_0 + y
          
    print("shape x = {}, y = {}, theta = {}, theta_0 = {}".format(x.shape,y.shape,theta.shape,theta_0.shape))
    return (theta,theta_0)
        
          
theta, theta_0=perceptron(data1,labels1)
print(theta)
print(theta_0[0])
ax1=tidy_plot(-10,10,-10,10)
plot_separator(ax1,theta,theta_0[0])
plot_data(data1,labels1,ax1)
test_perceptron(perceptron)<jupyter_output>d = 2, n = 4, theta shape = (2, 1), theta_0 shape = (1,)
shape x = (2,), y = (), theta = (2, 1), theta_0 = (1,)
-----------Test Perceptron 0-----------
Passed! 

d = 2, n = 4, theta shape = (2, 1), theta_0 shape = (1,)
shape x = (2,), y = (), theta = (2, 1), theta_0 = (1,)
-----------Test Perceptron 1-----------
Passed!<jupyter_text>8) Implement averaged perceptronRegular perceptron can be somewhat sensitive to the most recent examples that it sees. Instead, averaged perceptron produces a more stable output by outputting the average value of `th` and `th0` across all iterations.Implement averaged perceptron with the same spec as regular perceptron, and using the pseudocode below as a guide.procedure averaged_perceptron({(x^(i), y^(i)), i=1,...n}, T)    th = 0 (d by 1); th0 = 0 (1 by 1)    ths = 0 (d by 1); th0s = 0 (1 by 1)    for t = 1,...,T do:        for i = 1,...,n do:	        if y^(i)(th . x^(i) + th0) <= 0 then              th = th + y^(i)x^(i)              th0 = th0 + y^(i)	        ths = ths + th	        th0s = th0s + th0    return ths/(nT), th0s/(nT)<jupyter_code>def averaged_perceptron(data, labels, params={}, hook=None):
    # if T not in params, default to 100
    T = params.get('T', 100)
    d, n = data.shape
    theta = np.zeros((d,1))
    theta_0 = np.zeros(1)
    ths = np.zeros((d,1))
    th0s = np.zeros(1)
    print("d = {}, n = {}, theta shape = {}, theta_0 shape = {}".format(d,n,theta.shape,theta_0.shape))
  
    for t in range(T):     
      for i in range(n):
        y = labels[0,i]
        x = data[:,i]
        
        a = np.dot(x,theta)+theta_0
        #print("a = {}".format(a))
        positive = np.sign(y*a)
        
        if np.sign(y*a) <=0: # update the thetas
          theta[:,0] = theta[:,0]+ y*x
          theta_0 = theta_0 + y
        
        ths += theta
        th0s += theta_0
        
          
    #print("shape x = {}, y = {}, theta = {}, theta_0 = {}".format(x.shape,y.shape,theta.shape,theta_0.shape))
    return (ths/(n*T),th0s/(n*T))
test_averaged_perceptron(averaged_perceptron)<jupyter_output>d = 2, n = 4, theta shape = (2, 1), theta_0 shape = (1,)
-----------Test Averaged Perceptron 0-----------
Passed! 

d = 2, n = 4, theta shape = (2, 1), theta_0 shape = (1,)
-----------Test Averaged Perceptron 1-----------
Passed!<jupyter_text>9) Implement evaluation strategies   9.1)  Evaluating a classifierTo evaluate a classifier, we are interested in how well it performs on data that it wasn't trained on. Construct a testing procedure that uses a training data set, calls a learning algorithm to get a linear separator (a tuple of $\theta, \theta_0$), and then reports the percentage correct on a new testing set as a float between 0. and 1..The learning algorithm is passed as a function that takes a data array and a labels vector.  Your evaluator should be able to interchangeably evaluate `perceptron` or `averaged_perceptron` (or future algorithms with the same spec), depending on what is passed through the `learner` parameter.The `eval_classifier` function should accept the following parameters:* learner - a function, such as perceptron or averaged_perceptron* data_train - training data* labels_train - training labels* data_test - test data* labels_test - test labelsAssume that you have available the function `score` from HW 1, which takes inputs:* data: a d by n array of floats (representing n data points in d dimensions)* labels: a 1 by n array of elements in (+1, -1), representing target labels* th: a d by 1 array of floats that together with* th0: a single scalar or 1 by 1 array, represents a hyperplaneand returns 1 by 1 matrix with an integer indicating number of data points correct for the separator.<jupyter_code>def eval_classifier(learner, data_train, labels_train, data_test, labels_test):
    theta, theta_0 = learner(data_train,labels_train)
    print("theta shape = {}, theta_0 shape = {}, data_test shape = {}".format(theta.shape, theta_0.shape, data_test.shape))
    print(theta)
    # shape = n by 1
    a = np.matmul(data_test.T,theta)+theta_0
    #print("a shape = {}".format(a.shape))
    #print(labels_test)
   
    # shape 1 by n
    predict_labels = np.transpose(np.sign(a))
  
    #print(predict_labels)
    scores = (predict_labels == labels_test)
    #print(scores)
    final_score = np.mean(scores)
    
    return final_score
test_eval_classifier(eval_classifier,perceptron)<jupyter_output>d = 2, n = 30, theta shape = (2, 1), theta_0 shape = (1,)
shape x = (2,), y = (), theta = (2, 1), theta_0 = (1,)
theta shape = (2, 1), theta_0 shape = (1,), data_test shape = (2, 30)
[[3.19695273]
 [0.10839974]]
-----------Test Eval Classifier 0-----------
Passed! 

d = 2, n = 30, theta shape = (2, 1), theta_0 shape = (1,)
shape x = (2,), y = (), theta = (2, 1), theta_0 = (1,)
theta shape = (2, 1), theta_0 shape = (1,), data_test shape = (2, 30)
[[-2.53272084]
 [ 2.5282913 ]]
-----------Test Eval Classifier 1-----------
Passed!<jupyter_text>9.2) Evaluating a learning algorithm using a data sourceConstruct a testing procedure that takes a learning algorithm and a data source as input and runs the learning algorithm multiple times, each time evaluating the resulting classifier as above. It should report the overall average classification accuracy.You can use our implementation of `eval_classifier` as above.Write the function `eval_learning_alg` that takes:* learner - a function, such as perceptron or averaged_perceptron* data_gen - a data generator, call it with a desired data set size; returns a tuple (data, labels)* n_train - the size of the learning sets* n_test - the size of the test sets* it - the number of iterations to average overand returns the average classification accuracy as a float between 0. and 1..  ** Note: Be sure to generate your training data and then testing data in that order, to ensure that the pseudorandomly generated data matches that in the test code. **<jupyter_code>def eval_learning_alg(learner, data_gen, n_train, n_test, it):
    score = 0
    for i in range(it):
        data_train, labels_train = data_gen(n_train)
        data_test, labels_test = data_gen(n_test) 
        score_i = eval_classifier(learner, data_train, labels_train, data_test, labels_test)
        print("score_i = {}".format(score_i))
        
        score+= score_i
    
    return score/it
test_eval_learning_alg(eval_learning_alg,perceptron)<jupyter_output>d = 2, n = 10, theta shape = (2, 1), theta_0 shape = (1,)
shape x = (2,), y = (), theta = (2, 1), theta_0 = (1,)
theta shape = (2, 1), theta_0 shape = (1,), data_test shape = (2, 10)
[[0.13368101]
 [0.87537888]]
score_i = 0.5
d = 2, n = 10, theta shape = (2, 1), theta_0 shape = (1,)
shape x = (2,), y = (), theta = (2, 1), theta_0 = (1,)
theta shape = (2, 1), theta_0 shape = (1,), data_test shape = (2, 10)
[[-0.40522929]
 [-3.71502634]]
score_i = 0.2
d = 2, n = 10, theta shape = (2, 1), theta_0 shape = (1,)
shape x = (2,), y = (), theta = (2, 1), theta_0 = (1,)
theta shape = (2, 1), theta_0 shape = (1,), data_test shape = (2, 10)
[[-3.27116076]
 [ 0.41978856]]
score_i = 0.3
d = 2, n = 10, theta shape = (2, 1), theta_0 shape = (1,)
shape x = (2,), y = (), theta = (2, 1), theta_0 = (1,)
theta shape = (2, 1), theta_0 shape = (1,), data_test shape = (2, 10)
[[5.42252635]
 [1.80439054]]
score_i = 0.9
d = 2, n = 10, theta shape = (2, 1), theta_0 shape = (1,)
shape x = (2,), y = (), theta = (2[...]<jupyter_text>9.3) Evaluating a learning algorithm with a fixed datasetCross-validation is a strategy for evaluating a learning algorithm, using a single training set of size $n$. Cross-validation takes in a learning algorithm $L$, a fixed data set $\mathcal{D}$, and a parameter $k$. It will run the learning algorithm $k$ different times, then evaluate the accuracy of the resulting classifier, and ultimately return the average of the accuracies over each of the $k$ "runs" of $L$. It is structured like this:divide D into k parts, as equally as possible;  call them D_i for i == 0 .. k-1 be sure the data is shuffled in case someone put all the positive examples first in the data!for j from 0 to k-1:    D_minus_j = union of all the datasets D_i, except for D_j    h_j = L(D_minus_j)    score_j = accuracy of h_j measured on D_jreturn average(score0, ..., score(k-1))So, each time, it trains on  $k−1$ of the pieces of the data set and tests the resulting hypothesis on the piece that was not used for training.When $k=n$, it is called *leave-one-out cross validation*.Implement cross validation **assuming that the input data is shuffled already** so that the positives and negatives are distributed randomly. If the size of the data does not evenly divide by k, split the data into n % k sub-arrays of size n//k + 1 and the rest of size n//k. (Hint: You can use numpy.array_splitand numpy.concatenate with axis arguments to split and rejoin the data as you desire.)Note: In Python, n//k indicates integer division, e.g. 2//3 gives 0 and 4//3 gives 1.<jupyter_code>def xval_learning_alg(learner, data, labels, k):
    data_split = np.array_split(data,k)
    labels_split = np.array_split(labels,k)
    
    print("k = {}, len of split = {}".format(k,len(data)))
    
    for i in range(k):
      data
    
test_xval_learning_alg(xval_learning_alg,perceptron)<jupyter_output>k = 5, len of split = 5
-----------Test Cross-eval Learning Algo-----------
Test Failed.
Your code output  None
Expected  0.61<jupyter_text>10) TestingIn this section, we compare the effectiveness of perceptron and averaged perceptron on some data that are not necessarily linearly separable.Use your `eval_learning_alg` and the `gen_flipped_lin_separable` generator in the code file to evaluate the accuracy of `perceptron` vs. a`veraged_perceptron`. `gen_flipped_lin_separable` can be called with an integer to return a data set and labels. Note that this generates linearly separable data and then "flips" the labels with some specified probability (the argument pflip); so most of the results will not be linearly separable. You can also specifiy pflip in the call to the generator. You should use the default values of th and th_0 to retain consistency with the Tutor.Run enough trials so that you can confidently predict the accuracy of these algorithms on new data from that same generator; assume training/test sets on the order of 20 points. The Tutor will check that your answer is within 0.025 of the answer we got using the same generator.<jupyter_code>print(eval_learning_alg(perceptron, gen_flipped_lin_separable(pflip=.1), 20, 20, 5))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12434350603264727, 'fraction_numerical': 0.03633782824698368, 'mean_word_length': 3.62, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 27, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '103035', 'license': 'MIT', 'n_tokens_mistral': 4956, 'n_tokens_neox': 4515, 'n_words': 1753, 'path': 'MIT6_036_hw02_perceptron_task.ipynb', 'repo_name': 'harryangstrom/MEANstack', 'size': '14090'}