<jupyter_start><jupyter_text>Validation<jupyter_code>import numpy as np
import pandas as pd
import graphlab as gl
in_raw = []
with open('in.txt', 'r') as lines:
    for line in lines:
        in_raw.append(map(float, line.split()))
        
in_sample = pd.DataFrame(in_raw)
#print(in_sample)

out_raw = []
with open('out.txt', 'r') as lines:
    for line in lines:
        out_raw.append(map(float, line.split()))
        
out_sample = pd.DataFrame(out_raw)        
#print len(out_sample)
in_sample_non_linear_transform = np.column_stack((np.ones(len(in_sample)), in_sample[0], in_sample[1], \
                                in_sample[0] * in_sample[0], in_sample[1] * in_sample[1], \
                                in_sample[0] * in_sample[1], abs(in_sample[0] - in_sample[1]), \
                                abs(in_sample[0] + in_sample[1])))

print len(in_sample_non_linear_transform)

training_in_sample = in_sample_non_linear_transform[0:25, :]
print training_in_sample

validation_in_sample = in_sample_non_linear_transform[25:, :]
print len(validation_in_sample)
out_sample_non_linear_transform = np.column_stack((np.ones(len(out_sample)), out_sample[0], out_sample[1], \
                                out_sample[0] * out_sample[0], out_sample[1] * out_sample[1], \
                                out_sample[0] * out_sample[1], abs(out_sample[0] - out_sample[1]), \
                                abs(out_sample[0] + out_sample[1])))
weights_3k = np.dot(np.dot(np.linalg.pinv(np.dot(training_in_sample[:, 0:4].transpose(), training_in_sample[:, 0:4])), training_in_sample[:, 0:4].transpose()), in_sample[2][0:25]) 

# Calculate the sign of predictions
validation_3k_predictions = np.sign(np.dot(validation_in_sample[:, 0:4], weights_3k))

# compare the prediction with output
errors = gl.SArray(validation_3k_predictions == in_sample[2][25:])

validation_3k_errors = 1 - sum(errors) / float(len(errors))

print validation_3k_errors

# Calculate the sign of predictions
testing_3k_predictions = np.sign(np.dot(out_sample_non_linear_transform[:, 0:4], weights_3k))

# compare the prediction with output
errors = gl.SArray(testing_3k_predictions == out_sample[2])

testing_3k_errors = 1 - sum(errors) / float(len(errors))

print testing_3k_errors
weights_4k = np.dot(np.dot(np.linalg.pinv(np.dot(training_in_sample[:, 0:5].transpose(), training_in_sample[:, 0:5])), training_in_sample[:, 0:5].transpose()), in_sample[2][0:25]) 

# Calculate the sign of predictions
validation_4k_predictions = np.sign(np.dot(validation_in_sample[:, 0:5], weights_4k))

# compare the prediction with output
errors = gl.SArray(validation_4k_predictions == in_sample[2][25:])

validation_4k_errors = 1 - sum(errors) / float(len(errors))

print validation_4k_errors

# Calculate the sign of predictions
testing_4k_predictions = np.sign(np.dot(out_sample_non_linear_transform[:, 0:5], weights_4k))

# compare the prediction with output
errors = gl.SArray(testing_4k_predictions == out_sample[2])

testing_4k_errors = 1 - sum(errors) / float(len(errors))

print testing_4k_errors
weights_5k = np.dot(np.dot(np.linalg.pinv(np.dot(training_in_sample[:, 0:6].transpose(), training_in_sample[:, 0:6])), training_in_sample[:, 0:6].transpose()), in_sample[2][0:25]) 

# Calculate the sign of predictions
validation_5k_predictions = np.sign(np.dot(validation_in_sample[:, 0:6], weights_5k))

# compare the prediction with output
errors = gl.SArray(validation_5k_predictions == in_sample[2][25:])

validation_5k_errors = 1 - sum(errors) / float(len(errors))

print validation_5k_errors

# Calculate the sign of predictions
testing_5k_predictions = np.sign(np.dot(out_sample_non_linear_transform[:, 0:6], weights_5k))

# compare the prediction with output
errors = gl.SArray(testing_5k_predictions == out_sample[2])

testing_5k_errors = 1 - sum(errors) / float(len(errors))

print testing_5k_errors
weights_6k = np.dot(np.dot(np.linalg.pinv(np.dot(training_in_sample[:, 0:7].transpose(), training_in_sample[:, 0:7])), training_in_sample[:, 0:7].transpose()), in_sample[2][0:25]) 

# Calculate the sign of predictions
validation_6k_predictions = np.sign(np.dot(validation_in_sample[:, 0:7], weights_6k))

# compare the prediction with output
errors = gl.SArray(validation_6k_predictions == in_sample[2][25:])

validation_6k_errors = 1 - sum(errors) / float(len(errors))

print validation_6k_errors

# Calculate the sign of predictions
testing_6k_predictions = np.sign(np.dot(out_sample_non_linear_transform[:, 0:7], weights_6k))

# compare the prediction with output
errors = gl.SArray(testing_6k_predictions == out_sample[2])

testing_6k_errors = 1 - sum(errors) / float(len(errors))

print testing_6k_errors
weights_7k = np.dot(np.dot(np.linalg.pinv(np.dot(training_in_sample[:, 0:8].transpose(), training_in_sample[:, 0:8])), training_in_sample[:, 0:8].transpose()), in_sample[2][0:25]) 

# Calculate the sign of predictions
validation_7k_predictions = np.sign(np.dot(validation_in_sample[:, 0:8], weights_7k))

# compare the prediction with output
errors = gl.SArray(validation_7k_predictions == in_sample[2][25:])

validation_7k_errors = 1 - sum(errors) / float(len(errors))

print validation_7k_errors

# Calculate the sign of predictions
testing_7k_predictions = np.sign(np.dot(out_sample_non_linear_transform[:, 0:8], weights_7k))

# compare the prediction with output
errors = gl.SArray(testing_7k_predictions == out_sample[2])

testing_7k_errors = 1 - sum(errors) / float(len(errors))

print testing_7k_errors
dataset_25 = in_sample_non_linear_transform[0:25, :]

dataset_10 = in_sample_non_linear_transform[25:, :]

dataset_25_results = in_sample[2][0:25]
dataset_10_results = in_sample[2][25:]

def validation(training_dataset, training_dataset_results, validation_dataset, validation_dataset_results, n):

    weights = np.dot(np.dot(np.linalg.pinv(np.dot(training_dataset[:, 0:n].transpose(), training_dataset[:, 0:n])), training_dataset[:, 0:n].transpose()), training_dataset_results) 

    # Calculate the sign of predictions
    validation_predictions = np.sign(np.dot(validation_dataset[:, 0:n], weights))

    # compare the prediction with output
    errors = gl.SArray(validation_predictions == validation_dataset_results)

    validation_errors = 1 - sum(errors) / float(len(errors))

    #print "training size = %s, k = %s, validation errors is %s" %(len(training_dataset), n-1, format(validation_errors, '.5f'))
    #print sum(errors)

    # Calculate the sign of predictions
    testing_predictions = np.sign(np.dot(out_sample_non_linear_transform[:, 0:n], weights))

    # compare the prediction with output
    errors = gl.SArray(testing_predictions == out_sample[2])

    testing_errors = 1 - sum(errors) / float(len(errors))

    print "training size = %s, k = %s, testing errors is %s" %(len(training_dataset), n-1, format(testing_errors, '.5f'))  
 
validation(n = 4, training_dataset = dataset_25, training_dataset_results = dataset_25_results, validation_dataset = dataset_10, validation_dataset_results = dataset_10_results)
validation(n = 5, training_dataset = dataset_25, training_dataset_results = dataset_25_results, validation_dataset = dataset_10, validation_dataset_results = dataset_10_results)
validation(n = 6, training_dataset = dataset_25, training_dataset_results = dataset_25_results, validation_dataset = dataset_10, validation_dataset_results = dataset_10_results)
validation(n = 7, training_dataset = dataset_25, training_dataset_results = dataset_25_results, validation_dataset = dataset_10, validation_dataset_results = dataset_10_results)
validation(n = 8, training_dataset = dataset_25, training_dataset_results = dataset_25_results, validation_dataset = dataset_10, validation_dataset_results = dataset_10_results)
validation(n = 4, training_dataset = dataset_10, training_dataset_results = dataset_10_results, validation_dataset = dataset_25, validation_dataset_results = dataset_25_results)
validation(n = 5, training_dataset = dataset_10, training_dataset_results = dataset_10_results, validation_dataset = dataset_25, validation_dataset_results = dataset_25_results)
validation(n = 6, training_dataset = dataset_10, training_dataset_results = dataset_10_results, validation_dataset = dataset_25, validation_dataset_results = dataset_25_results)
validation(n = 7, training_dataset = dataset_10, training_dataset_results = dataset_10_results, validation_dataset = dataset_25, validation_dataset_results = dataset_25_results)
validation(n = 8, training_dataset = dataset_10, training_dataset_results = dataset_10_results, validation_dataset = dataset_25, validation_dataset_results = dataset_25_results)
import math
def distance(a, b):
    return math.sqrt(a**2+b**2)

print distance(0.0, 0.1)
print distance(0.1, 0.2)
print distance(0.1, 0.3)
print distance(0.2, 0.2)
print distance(0.2, 0.3)
print 0.192-0.084<jupyter_output>0.108<jupyter_text>Validation Bias<jupyter_code>def mini_learning(n):
    mini_list = list()
    i = 0
    while i < n:
        e1 = np.random.uniform(0, 1)
        #print e1

        e2 = np.random.uniform(0, 1)
        #print e2
        
        mini_list.append(min(e1, e2))
        
        i += 1
        
    return sum(mini_list)/float(len(mini_list))
    
mini_learning(1000000)<jupyter_output><empty_output><jupyter_text>Cross Validation<jupyter_code>def leave_one_out(p):
    data_1 = np.array(([1,-1,0],[1,1,0])) # validation[1,p,1]
    data_2 = np.array(([1,-1,0],[1,p,1])) # validation[1,1,0]
    data_3 = np.array(([1,p,1],[1,1,0])) # validation[1,-1,0]
    
    w_1 = np.dot(np.dot(np.linalg.pinv(np.dot(data_1[:,0:2].transpose(), data_1[:,0:2])), data_1[:,0:2].transpose()), data_1[:,2])
    error_1 = (np.dot(w_1,np.array(([1,p]))) - 1.)**2

    w_2 = np.dot(np.dot(np.linalg.pinv(np.dot(data_2[:,0:2].transpose(), data_2[:,0:2])), data_2[:,0:2].transpose()), data_2[:,2])
    error_2 = (np.dot(w_2,np.array(([1,1]))) - 0.)**2
    
    w_3 = np.dot(np.dot(np.linalg.pinv(np.dot(data_3[:,0:2].transpose(), data_3[:,0:2])), data_3[:,0:2].transpose()), data_3[:,2])
    error_3 = (np.dot(w_3,np.array(([1,-1]))) - 0)**2
    
    return error_1 + error_2 + error_3
print leave_one_out(math.sqrt(math.sqrt(3)+4))
print leave_one_out(math.sqrt(math.sqrt(3)-1))
print leave_one_out(math.sqrt(9+4*math.sqrt(6)))
print leave_one_out(math.sqrt(9-math.sqrt(6)))
# data_1 = np.array(([1,-1,0],[1,1,0])) validation[1,p,1] then b = 0
b_error_1 = (0-1)**2
# data_2 = np.array(([1,-1,0],[1,p,1])) validation[1,1,0] then b= 0.5
b_error_2 = (0.5-0)**2
#data_3 = np.array(([1,p,1],[1,1,0])) # validation[1,-1,0] then b= 0.5
b_error_3 = (0.5-0)**2

b_error_1 + b_error_2 + b_error_3<jupyter_output><empty_output><jupyter_text>PLA vs SVM<jupyter_code>import cvxopt
import random
import graphlab as gl
import matplotlib.pyplot as plt
%matplotlib inline
def output_func(x1, x2, slope, point):
    output = slope*x1 - slope*point[0] + point[1] - x2
    return output

def test(N):
    max_run = 1000 # No. of repeat the experiment
    N = N # sample data size 
    run = 0 # track the run number, inital
    
    # PLA inital setup
    correct_target = N # no. of correct target to converge 
    iter_success_list = list() # track the succssfully converged iteration no. in each run     
    prediction_results_pla = list() # track the relationship between f and g to calculate P[f(x) != g(x)] 
    
    # SVM inital setup
    sv_number_list = list() # count the number of support vectors get in each run
    prediction_results_svm = list() # track the relationship between f and g to calculate P[f(x) != g(x)]
    
    while run < max_run:

        # Generate data 
        features_1 = np.array(([[1]]*N))
        features_2 = np.array((np.random.uniform(-1, 1., size=(N, 2)))) # generating two random, uniformly distributed points in [-1, 1]
        features = np.hstack((features_1, features_2))

        function_f_points = np.array((np.random.uniform(-1, 1., size=(2, 2))))    
    
        # Calculate the slope
        slope = (function_f_points[1,1] - function_f_points[0,1])/(function_f_points[1,0] - function_f_points[0,0])
    
        # Calculate the output
        output = output_func(features_2[:,0], features_2[:,1], slope, function_f_points[0,:])
        output = gl.SArray(np.sign(output))
        
        # Discard the run if all data points are on the one side of the line
        if len(output[output == +1]) == 0 or len(output[output == -1]) == 0:
            continue  
        
        # Show the progress
        if run <= 10 or (run <= 100 and run % 10 == 0) or (run <= 1000 and run % 100 == 0) \
        or (run <= 10000 and run % 1000 == 0) or run % 10000 == 0:
            print "Run # %d :" %run
            
        # generate a random point
        features_3 = np.array((np.random.uniform(-1, 1., size=(1, 2)))) 
        
        # Target function classify the random point
        target_f = output_func(features_3[:,0], features_3[:,1], slope, function_f_points[0,:])
        target_f = gl.SArray(np.sign(target_f))
        
        #Simple PLA
        
        # inital values for each run
        iteration = 0 # track the iteration number
        weights=[0,0,0] # initial vector weights
        errors = [0]*N # inital errors

        while sum(errors) < correct_target:

            # Calculate the sign of predictions
            predictions = gl.SArray(np.sign(np.dot(features, weights)))
            
            # compare the prediction with output
            errors = gl.SArray(predictions == output)       

            misclassified_points = list() # track the misclassifed points index
            mis_points = list() # track the misclassfied points

            for num in xrange(N):
                if errors[num] == 0:
                    misclassified_points.append(num)
                    mis_points.append(features[num,:])

            if sum(errors) < correct_target:

                # Randomly choose one point from misclassified points (choose index in here) 
                misclassified_point = random.choice(misclassified_points)

                # Recalculate the weights
                weights += features[misclassified_point, :] * output[misclassified_point]

            else:

                iter_success_list.append(iteration) # include the successfully converged iteration number

                # predicted function classify the random point
                predict_pla = weights[0] + weights[1]*features_3[:,0] + weights[2]*features_3[:,1]              
                predict_pla = gl.SArray(np.sign(predict_pla))
                
                
                # include the compared classification result of the random point
                prediction_results_pla.append(int((list(predict_pla) == list(target_f)) == True))

                #print "PLA Run #" + str(run) + ": " + "successfully converged @ iteration: " + str(iteration)
                #print "PLA Weights: " + str(weights)
                #print "PLA Target/Predicted function agree: " + str(list(predict_pla) == list(target_f))
                #print "======================================================================"

            iteration += 1
            
            
            
        # SVM
        # Quadratic coefficients
        for i in xrange(N):
    
            f = np.array(([np.dot(output[i]*output[j]*features_2[i,:].transpose(), features_2[j,:]) for j in xrange(N)]))

            if i == 0:
                qe = np.array(f)
            else: 
                qe = np.vstack((qe, f))
        
        # cvxopt parameters
        P = cvxopt.matrix(qe, tc='d')
        q = cvxopt.matrix(np.ones(N) * -1, tc='d')
        G = cvxopt.matrix(np.diag(np.ones(N) * -1))
        h = cvxopt.matrix(np.zeros(N))
        A = cvxopt.matrix(output, (1,N))
        b = cvxopt.matrix(0.0)
        
        # Solve the quadratic program
        cvxopt.solvers.options['show_progress'] = False # Turn off the 'show_progress'
        
        sol = cvxopt.solvers.qp(P,q,G,h,A,b)        
                
        # Lagrange multipliers
        all_a = np.ravel(sol['x'])

        # Support vectors have non zero lagrange multipliers   
        sv_pos = list()
        for i in xrange(len(all_a)):
            if all_a[i] > 1e-5:
                sv_pos.append(i)
  
        #print "%d support vectors out of %d points" % (len(sv_pos), N)                 
        sv_number_list.append(len(sv_pos))        
        
        
        a = all_a[sv_pos] # alpha of the support vectors
        sv_features = features_2[sv_pos] # features matrix of support vectors
        sv_y = np.array(output)[sv_pos]  # output of support vectors
            
        # Weights    
        weights = np.zeros(2)
        for n in xrange(len(a)):
            weights += a[n] * sv_y[n] * sv_features[n] 
        
        # Intercept
        b_list = list()
        
        for i in sv_pos:  
            b_temp = 1/float(output[i]) - np.dot(weights,features_2[i]) 
            b_list.append(b_temp)
            
        b = sum(b_list) / float(len(b_list)) 
        weights = np.hstack((b, weights)) # insert the intercept to the weights
        

        # predicted function classify the random point
        predict_svm = weights[0] + weights[1]*features_3[:,0] + weights[2]*features_3[:,1]              
        predict_svm = gl.SArray(np.sign(predict_svm))


        # include the compared classification result of the random point
        prediction_results_svm.append(int((list(predict_svm) == list(target_f)) == True))

        #print "SVM Weights: " + str(weights) 
        #print "SVM Target/Predicted function agree: " + str(list(predict_svm) == list(target_f))
        #print "======================================================================"    
        
        run += 1 # update the run number
            
    # Simple PLA Calculate the average iteration        
    disagree_prob_pla = 1- sum(prediction_results_pla) / float(len(prediction_results_pla))
    print "PLA Probabily that f and g will disagree on their classfication of a random point: " + '{:.4f}'.format(round(disagree_prob_pla, 4))
    
    # Linear SVM Calculate the disagree probability
    disagree_prob_svm = 1- sum(prediction_results_svm) / float(len(prediction_results_svm))     
    print "SVM Probabily that f and g will disagree on their classfication of a random point: " + '{:.4f}'.format(round(disagree_prob_svm, 4))
    
    print "Avg count of support vectors: " +  str(sum(sv_number_list) / float(len(sv_number_list)))


    return prediction_results_pla, prediction_results_svm
    

prediction_results_pla_10, prediction_results_svm_10 = test(10)
test_10 = [1. if x == -1. else 0 for x in np.array(prediction_results_pla_10) - np.array(prediction_results_svm_10)]
sum(test_10) / float(len(test_10))
prediction_results_pla_100, prediction_results_svm_100 = test(100)
test_100 = [1. if x == -1. else 0 for x in np.array(prediction_results_pla_100) - np.array(prediction_results_svm_100)]
sum(test_100) / float(len(test_100))
def output_func(x1, x2, slope, point):
    output = slope*x1 - slope*point[0] + point[1] - x2
    return output

def test(N):
    
    # PLA inital setup
    correct_target = N # no. of correct target to converge 
    iter_success_list = list() # track the succssfully converged iteration no. in each run     
    
    # SVM inital setup
    sv_number_list = list() # count the number of support vectors get in each run
    

    # Generate data 
    features_1 = np.array(([[1]]*N))
    features_2 = np.array((np.random.uniform(-1, 1., size=(N, 2)))) # generating two random, uniformly distributed points in [-1, 1]
    features = np.hstack((features_1, features_2))

    function_f_points = np.array((np.random.uniform(-1, 1., size=(2, 2))))    

    # Calculate the slope
    slope = (function_f_points[1,1] - function_f_points[0,1])/(function_f_points[1,0] - function_f_points[0,0])

    # Calculate the output
    output = output_func(features_2[:,0], features_2[:,1], slope, function_f_points[0,:])
    output = gl.SArray(np.sign(output))

    # Discard the run if all data points are on the one side of the line
    if len(output[output == +1]) == 0 or len(output[output == -1]) == 0:
        test(N) 

    # generate a random point
    features_3 = np.array((np.random.uniform(-1, 1., size=(100000, 2)))) 

    # Target function classify the random point
    target_f = output_func(features_3[:,0], features_3[:,1], slope, function_f_points[0,:])
    target_f = gl.SArray(np.sign(target_f))

    #Simple PLA

    # inital values for each run
    iteration = 0 # track the iteration number
    weights=[0,0,0] # initial vector weights
    errors = [0]*N # inital errors

    while sum(errors) < correct_target:

        # Calculate the sign of predictions
        predictions = gl.SArray(np.sign(np.dot(features, weights)))

        # compare the prediction with output
        errors = gl.SArray(predictions == output)       

        misclassified_points = list() # track the misclassifed points index
        mis_points = list() # track the misclassfied points

        for num in xrange(N):
            if errors[num] == 0:
                misclassified_points.append(num)
                mis_points.append(features[num,:])

        if sum(errors) < correct_target:

            # Randomly choose one point from misclassified points (choose index in here) 
            misclassified_point = random.choice(misclassified_points)

            # Recalculate the weights
            weights += features[misclassified_point, :] * output[misclassified_point]

        else:

            iter_success_list.append(iteration) # include the successfully converged iteration number

            # predicted function classify the random point
            predict_pla = weights[0] + weights[1]*features_3[:,0] + weights[2]*features_3[:,1]              
            predict_pla = gl.SArray(np.sign(predict_pla))


            # include the compared classification result of the random point
            prediction_results_pla = (gl.SArray(predict_pla) == gl.SArray(target_f))

            #print "PLA Run #" + str(run) + ": " + "successfully converged @ iteration: " + str(iteration)
            #print "PLA Weights: " + str(weights)
            #print "PLA Target/Predicted function agree: " + str(list(predict_pla) == list(target_f))
            #print "======================================================================"

        iteration += 1



    # SVM
    # Quadratic coefficients
    for i in xrange(N):

        f = np.array(([np.dot(output[i]*output[j]*features_2[i,:].transpose(), features_2[j,:]) for j in xrange(N)]))

        if i == 0:
            qe = np.array(f)
        else: 
            qe = np.vstack((qe, f))

    # cvxopt parameters
    P = cvxopt.matrix(qe, tc='d')
    q = cvxopt.matrix(np.ones(N) * -1, tc='d')
    G = cvxopt.matrix(np.diag(np.ones(N) * -1))
    h = cvxopt.matrix(np.zeros(N))
    A = cvxopt.matrix(output, (1,N))
    b = cvxopt.matrix(0.0)

    # Solve the quadratic program
    cvxopt.solvers.options['show_progress'] = False # Turn off the 'show_progress'

    sol = cvxopt.solvers.qp(P,q,G,h,A,b)        

    # Lagrange multipliers
    all_a = np.ravel(sol['x'])

    # Support vectors have non zero lagrange multipliers   
    sv_pos = list()
    for i in xrange(len(all_a)):
        if all_a[i] > 1e-5:
            sv_pos.append(i)

    #print "%d support vectors out of %d points" % (len(sv_pos), N)                 
    sv_number_list.append(len(sv_pos))        


    a = all_a[sv_pos] # alpha of the support vectors
    sv_features = features_2[sv_pos] # features matrix of support vectors
    sv_y = np.array(output)[sv_pos]  # output of support vectors

    # Weights    
    weights = np.zeros(2)
    for n in xrange(len(a)):
        weights += a[n] * sv_y[n] * sv_features[n] 

    # Intercept
    b_list = list()

    for i in sv_pos:  
        b_temp = 1/float(output[i]) - np.dot(weights,features_2[i]) 
        b_list.append(b_temp)

    b = sum(b_list) / float(len(b_list)) 
    weights = np.hstack((b, weights)) # insert the intercept to the weights


    # predicted function classify the random point
    predict_svm = weights[0] + weights[1]*features_3[:,0] + weights[2]*features_3[:,1]              
    predict_svm = gl.SArray(np.sign(predict_svm))


    # include the compared classification result of the random point
    prediction_results_svm = (gl.SArray(predict_svm) == gl.SArray(target_f))

    #print "SVM Weights: " + str(weights) 
    #print "SVM Target/Predicted function agree: " + str(list(predict_svm) == list(target_f))
    #print "======================================================================"    
        

            
    # Simple PLA Calculate the average iteration        
    disagree_prob_pla = 1- sum(prediction_results_pla) / float(len(prediction_results_pla))
    print "PLA Probabily that f and g will disagree on their classfication of a random point: " + '{:.4f}'.format(round(disagree_prob_pla, 4))
    
    # Linear SVM Calculate the disagree probability
    disagree_prob_svm = 1- sum(prediction_results_svm) / float(len(prediction_results_svm))     
    print "SVM Probabily that f and g will disagree on their classfication of a random point: " + '{:.4f}'.format(round(disagree_prob_svm, 4))
    
    print "Avg count of support vectors: " +  str(sum(sv_number_list) / float(len(sv_number_list)))


    return prediction_results_pla, prediction_results_svm
    

prediction_results_pla_10, prediction_results_svm_10 = test(10)
print sum(prediction_results_pla_10)
print sum(prediction_results_svm_10)
prediction_results_pla_100, prediction_results_svm_100 = test(100)
print sum(prediction_results_pla_100)
print sum(prediction_results_svm_100)
def output_func(x1, x2, slope, point):
    output = slope*x1 - slope*point[0] + point[1] - x2
    return output

def test(N):
    max_run = 1000 # No. of repeat the experiment
    N = N # sample data size 
    run = 0 # track the run number, inital
    prediction_results = list()
    
    # PLA inital setup
    correct_target = N # no. of correct target to converge 
    iter_success_list = list() # track the succssfully converged iteration no. in each run     
    
    # SVM inital setup
    sv_number_list = list() # count the number of support vectors get in each run
    
    while run < max_run:

        # Generate data 
        features_1 = np.array(([[1]]*N))
        features_2 = np.array((np.random.uniform(-1, 1., size=(N, 2)))) # generating two random, uniformly distributed points in [-1, 1]
        features = np.hstack((features_1, features_2))

        function_f_points = np.array((np.random.uniform(-1, 1., size=(2, 2))))    
    
        # Calculate the slope
        slope = (function_f_points[1,1] - function_f_points[0,1])/(function_f_points[1,0] - function_f_points[0,0])
    
        # Calculate the output
        output = output_func(features_2[:,0], features_2[:,1], slope, function_f_points[0,:])
        output = gl.SArray(np.sign(output))
        
        # Discard the run if all data points are on the one side of the line
        if len(output[output == +1]) == 0 or len(output[output == -1]) == 0:
            continue  
        
        # Show the progress
        if run <= 10 or (run <= 100 and run % 10 == 0) or (run <= 1000 and run % 100 == 0) \
        or (run <= 10000 and run % 1000 == 0) or run % 10000 == 0:
            print "Run # %d :" %run
            
        # generate a random point
        features_3 = np.array((np.random.uniform(-1, 1., size=(500, 2)))) 
        
        # Target function classify the random point
        target_f = output_func(features_3[:,0], features_3[:,1], slope, function_f_points[0,:])
        target_f = gl.SArray(np.sign(target_f))
        
        #Simple PLA
        
        # inital values for each run
        iteration = 0 # track the iteration number
        weights=[0,0,0] # initial vector weights
        errors = [0]*N # inital errors

        while sum(errors) < correct_target:

            # Calculate the sign of predictions
            predictions = gl.SArray(np.sign(np.dot(features, weights)))
            
            # compare the prediction with output
            errors = gl.SArray(predictions == output)       

            misclassified_points = list() # track the misclassifed points index
            mis_points = list() # track the misclassfied points

            for num in xrange(N):
                if errors[num] == 0:
                    misclassified_points.append(num)
                    mis_points.append(features[num,:])

            if sum(errors) < correct_target:

                # Randomly choose one point from misclassified points (choose index in here) 
                misclassified_point = random.choice(misclassified_points)

                # Recalculate the weights
                weights += features[misclassified_point, :] * output[misclassified_point]

            else:

                iter_success_list.append(iteration) # include the successfully converged iteration number

                # predicted function classify the random point
                predict_pla = weights[0] + weights[1]*features_3[:,0] + weights[2]*features_3[:,1]              
                predict_pla = gl.SArray(np.sign(predict_pla))
                
                
                # include the compared classification result of the random point
                prediction_results_pla= sum(np.array(predict_pla) == np.array(target_f))

                #print "PLA Run #" + str(run) + ": " + "successfully converged @ iteration: " + str(iteration)
                #print "PLA Weights: " + str(weights)
                #print "PLA Target/Predicted function agree: " + str(list(predict_pla) == list(target_f))
                #print "======================================================================"

            iteration += 1
            
            
            
        # SVM
        # Quadratic coefficients
        for i in xrange(N):
    
            f = np.array(([np.dot(output[i]*output[j]*features_2[i,:].transpose(), features_2[j,:]) for j in xrange(N)]))

            if i == 0:
                qe = np.array(f)
            else: 
                qe = np.vstack((qe, f))
        
        # cvxopt parameters
        P = cvxopt.matrix(qe, tc='d')
        q = cvxopt.matrix(np.ones(N) * -1, tc='d')
        G = cvxopt.matrix(np.diag(np.ones(N) * -1))
        h = cvxopt.matrix(np.zeros(N))
        A = cvxopt.matrix(output, (1,N))
        b = cvxopt.matrix(0.0)
        
        # Solve the quadratic program
        cvxopt.solvers.options['show_progress'] = False # Turn off the 'show_progress'
        
        sol = cvxopt.solvers.qp(P,q,G,h,A,b)        
                
        # Lagrange multipliers
        all_a = np.ravel(sol['x'])

        # Support vectors have non zero lagrange multipliers   
        sv_pos = list()
        for i in xrange(len(all_a)):
            if all_a[i] > 1e-5:
                sv_pos.append(i)
  
        #print "%d support vectors out of %d points" % (len(sv_pos), N)                 
        sv_number_list.append(len(sv_pos))        
        
        
        a = all_a[sv_pos] # alpha of the support vectors
        sv_features = features_2[sv_pos] # features matrix of support vectors
        sv_y = np.array(output)[sv_pos]  # output of support vectors
            
        # Weights    
        weights = np.zeros(2)
        for n in xrange(len(a)):
            weights += a[n] * sv_y[n] * sv_features[n] 
        
        # Intercept
        b_list = list()
        
        for i in sv_pos:  
            b_temp = 1/float(output[i]) - np.dot(weights,features_2[i]) 
            b_list.append(b_temp)
            
        b = sum(b_list) / float(len(b_list)) 
        weights = np.hstack((b, weights)) # insert the intercept to the weights
        

        # predicted function classify the random point
        predict_svm = weights[0] + weights[1]*features_3[:,0] + weights[2]*features_3[:,1]              
        predict_svm = gl.SArray(np.sign(predict_svm))


        # include the compared classification result of the random point
        prediction_results_svm = sum(np.array(predict_svm) == np.array(target_f))

        #print "SVM Weights: " + str(weights) 
        #print "SVM Target/Predicted function agree: " + str(list(predict_svm) == list(target_f))
        #print "======================================================================"    
        
        if prediction_results_svm > prediction_results_pla:
            prediction_results.append(1)
        else:
            prediction_results.append(0)
        
        run += 1 # update the run number
              
    print "Avg count of support vectors: " +  str(sum(sv_number_list) / float(len(sv_number_list)))

    print "SVM is more efficient on percentage: " + '{:.4f}'.format(round(sum(prediction_results) / float(len(prediction_results)), 4))

    return sum(prediction_results) / float(len(prediction_results))
    

test(10)
test(100)<jupyter_output>Run # 0 :
Run # 1 :
Run # 2 :
Run # 3 :
Run # 4 :
Run # 5 :
Run # 6 :
Run # 7 :
Run # 8 :
Run # 9 :
Run # 10 :
Run # 20 :
Run # 30 :
Run # 40 :
Run # 50 :
Run # 60 :
Run # 70 :
Run # 80 :
Run # 90 :
Run # 100 :
{'fraction_non_alphanumeric': 0.13247478386167147, 'fraction_numerical': 0.028578290105667627, 'mean_word_length': 2.9367761758449538, 'pattern_counts': {'":': 3, '<': 32, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '167343', 'license': 'MIT', 'n_tokens_mistral': 11272, 'n_tokens_neox': 10657, 'n_words': 2450, 'path': 'Caltech_Datascience/Week 7/Week_7_hw.ipynb', 'repo_name': 'zlhTao2012/Data_Science_Online_Learning', 'size': '33312'}