<jupyter_start><jupyter_text>Exercise 1 In this exercise, you will implement in Python a first version of your own linear support vector machine with the squared hinge loss. Recall from the lectures that the linear support vector machine with the squared hinge loss writes as$$min_{\beta \in R^d} F(\beta) := \frac{1}{n}\sum_{i=1}^n (max(0, 1 - y_i x_i^T \beta))^2 + \lambda||\beta||_2^2$$You know now by heart the fast gradient algorithm, so no need to recall it here. (1) Compute the gradient $\bigtriangledown F(\beta)$ of F. $$\bigtriangledown F(\beta) = \frac{1}{n} \sum_{i=1}^n  - 2 y_i x_i (max(0, 1 - y_ix_i^T\beta)) + 2\lambda\beta$$ (2) Consider the Spam dataset from The Elements of Statistical Learning. Standardize the data, if you have not done so already.<jupyter_code>spam = pd.read_table('https://statweb.stanford.edu/~tibs/ElemStatLearn/datasets/spam.data', sep=' ', header=None)
test_indicator = pd.read_table('https://statweb.stanford.edu/~tibs/ElemStatLearn/datasets/spam.traintest', sep=' ',
                               header=None)

x = np.asarray(spam)[:, 0:-1]
y = np.asarray(spam)[:, -1]*2 - 1  # Convert to +/- 1
test_indicator = np.array(test_indicator).T[0]


x_train = x[test_indicator == 0, :]
x_test = x[test_indicator == 1, :]
y_train = y[test_indicator == 0]
y_test = y[test_indicator == 1]


scaler = sklearn.preprocessing.StandardScaler()
scaler.fit(x_train)
x_train = scaler.transform(x_train)
x_test = scaler.transform(x_test)


n_train = len(y_train)
n_test = len(y_test)
d = np.size(x, 1)
print(x_train.shape)
print(y_train.shape)<jupyter_output>(3065, 57)
(3065,)<jupyter_text>(3) Write a function mylinearsvm that implements the fast gradient algorithm to train the linear support vector machine with the squared hinge loss. The function takes as input the initial step-size value for the backtracking rule and a maximum number of iterations. $$min_{\beta \in R^d} F(\beta) := \frac{1}{n}\sum_{i=1}^n (max(0, 1 - y_i x_i^T \beta))^2 + \lambda||\beta||_2^2$$$$\bigtriangledown F(\beta) = \frac{1}{n} \sum_{i=1}^n  - 2 y_i x_i (max(0, 1 - y_ix_i^T\beta)) + 2\lambda\beta$$<jupyter_code>def objective(beta, lambduh, x=x_train, y=y_train):
    return 1/len(y)*np.sum(np.maximum(0, (1 - y*x.dot(beta)))**2) + lambduh * np.linalg.norm(beta)**2
beta_init = np.zeros(d)
lambduh = 1
objective(beta_init,lambduh)
def computegrad(beta, lambduh, x=x_train, y=y_train):
    yx = y[:, None]*x
    grad = 1/len(y)*np.sum(- 2*yx*np.maximum(0, (1 - yx.dot(beta[:, np.newaxis]))), axis=0) + 2*lambduh*beta
    return grad
beta_init = np.zeros(d)
lambduh = 1
computegrad(beta_init,lambduh)
def bt_line_search(beta, lambduh, eta=1, alpha=0.5, betaparam=0.8,
                   maxiter=100, x=x_train, y=y_train):
    grad_beta = computegrad(beta, lambduh, x=x, y=y)
    norm_grad_beta = np.linalg.norm(grad_beta)
    found_eta = 0
    iter = 0
    while found_eta == 0 and iter < maxiter:
        if objective(beta - eta * grad_beta, lambduh, x=x, y=y) < objective(beta, lambduh, x=x, y=y) \
                - alpha * eta * norm_grad_beta ** 2:
            found_eta = 1
        elif iter == maxiter - 1:
            print('Warning: Max number of iterations of backtracking line search reached')
        else:
            eta *= betaparam
            iter += 1
    return eta
bt_line_search(beta_init, lambduh)
#The function takes as input the initial step-size value for the backtracking rule and a maximum number of iterations.
def mylinearsvm(eta_init, max_iter, lambduh):
    d = np.size(x_train, 1)
    beta = np.zeros(d)
    theta = np.zeros(d)
    x=x_train
    y=y_train
    
    grad_theta = computegrad(theta, lambduh, x=x, y=y)
    beta_vals = beta
    theta_vals = theta
    iter = 0
    while iter < max_iter:
        eta = bt_line_search(theta, lambduh, eta=eta_init, x=x, y=y)
        beta_new = theta - eta*grad_theta
        theta = beta_new + iter/(iter+3)*(beta_new-beta)
        beta_vals = np.vstack((beta_vals, beta_new))
        theta_vals = np.vstack((theta_vals, theta))
        grad_theta = computegrad(theta, lambduh, x=x, y=y)
        beta = beta_new
        iter += 1
        
    return beta_vals
eta_init = 1/(scipy.linalg.eigh(1/len(y_train)*x_train.T.dot(x_train), eigvals=(d-1, d-1), eigvals_only=True)[0]+lambduh)
max_iter = 50
lambduh = 1
mylinearsvm(eta_init, max_iter,lambduh)<jupyter_output><empty_output><jupyter_text>(4) Train your linear support vector machine with the squared hinge loss on the the Spam dataset for the $\lambda$ = 1. Report your misclassification error for this value of $\lambda$.<jupyter_code>eta_init = 1/(scipy.linalg.eigh(1/len(y_train)*x_train.T.dot(x_train), eigvals=(d-1, d-1), eigvals_only=True)[0]+lambduh)
max_iter = 50
lambduh = 1
betas_fg= mylinearsvm(eta_init, max_iter, lambduh)
def compute_misclassification_error(beta_opt, x, y):
    y_pred = 1/(1+np.exp(-x.dot(beta_opt))) > 0.5
    y_pred = y_pred*2 - 1 
    return np.mean(y_pred != y)
beta_opt = betas_fg[-1]
mc_error = compute_misclassification_error(beta_opt, x_test, y_test)
print("The misclassification error for lambda = 1 is", + mc_error*100,"%")<jupyter_output>The misclassification error for lambda = 1 is 9.50520833333 %<jupyter_text>(5) Run cross-validation to find the optimal value of $\lambda$. Report your misclassification errorfor that value of $\lambda$.<jupyter_code>lambdas = [10**i for i in np.arange(-2, 0.1, 0.1)]
misclass_error = np.zeros_like(lambdas)
max_iter = 50

for i in range(len(lambdas)):
    lambduh = lambdas[i]
    beta_init = np.zeros(d)
    eta_init = 1/(scipy.linalg.eigh(1/len(y_train)*x_train.T.dot(x_train), eigvals=(d-1, d-1), eigvals_only=True)[0]+lambduh)
    betas_svm = mylinearsvm(eta_init, max_iter,lambduh)
    misclass_error[i] = compute_misclassification_error(betas_svm[-1], x_test, y_test)
    
print('Misclassification error from my linear SVM:', misclass_error)

print('Smallest misclassification error value:', min(misclass_error), 'at lambda =', lambdas[np.argmin(misclass_error)])<jupyter_output>Misclassification error from my linear SVM: [ 0.08463542  0.08528646  0.08463542  0.08919271  0.08854167  0.08789062
  0.08789062  0.08919271  0.08984375  0.09114583  0.09179688  0.09114583
  0.08984375  0.08919271  0.08854167  0.08919271  0.09114583  0.09179688
  0.09114583  0.09244792  0.09505208]
Smallest misclassification error value: 0.0846354166667 at lambda = 0.01
{'fraction_non_alphanumeric': 0.13518170426065163, 'fraction_numerical': 0.05451127819548872, 'mean_word_length': 4.067460317460317, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 15, 'https://': 2, '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': '424500', 'license': 'MIT', 'n_tokens_mistral': 2711, 'n_tokens_neox': 2444, 'n_words': 581, 'path': 'Data558 hw/hw7.ipynb', 'repo_name': 'jingyany/Machine-Learning-Algorithms', 'size': '6384'}