<jupyter_start><jupyter_text>$\newcommand{\xv}{\mathbf{x}} \newcommand{\wv}{\mathbf{w}} \newcommand{\Chi}{\mathcal{X}} \newcommand{\R}{\rm I\!R} \newcommand{\sign}{\text{sign}} \newcommand{\Tm}{\mathbf{T}} \newcommand{\Xm}{\mathbf{X}} \newcommand{\Im}{\mathbf{I}}  \newcommand{\Ym}{\mathbf{Y}}$ ITCS6156 Linear Model for ClassificationThe linear model $$ \Ym = \Xm \wv $$can be used for classification. For this, simply we can discretize the output $\Ym$ for prediction. Here the error function can be written $$E = \frac{1}{N} \sum_{i=1}^{N} \mathbb{1} \Big[ \sign(\wv^\top \xv_i) \ne t_i \Big] $$This error function contains discrete functions such as $\sign$ and the indicator delta function. Thus, the error function is not derivable, so we need a new approach to solve it.   The Perceptron AlgorithmLet us consider a simple binary classifcation as our target problem. A single perceptron is a linear model that applies a step function on the linear output. For classification, it iterate over the training examples, and update the weights in a way that would result in correct classification. Let us consider the case of misclassification. For positive class example, $\xv_i$, $$y_i = \wv^{(k)} \xv_i < 0.$$To fix this classification error, we want to update the weight $\wv^{(k)}$ to increase the output $y_i$.Thus, we expect$$ \wv^{(k+1)} \xv_i >  \wv^{(k)} \xv_i.$$This can be reached by using $\xv_i$ as a gradient as follows: $$\wv^{(k+1)} = \wv^{(k)} + \alpha \xv_i$$where $\alpha$ is the learning rate. When the sample $t_i$ is negative, we need to do the opposite$$ \wv^{(k+1)} \xv_i <  \wv^{(k)} \xv_i.$$To combine both positive and negative cases, we can use the target sample $t_i$ in our update, $$\wv^{(k+1)} = \wv^{(k)} + \alpha t_i \xv_i$$When the data is not linearly separable, there is no guarantee on convergence. Thus, for training, we need to set the maximum number of iteration. Also, the algorithm selects an arbitrary hyperplane that divides two classes, so it is possible to discover a decision boundary that is not the best.<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
# Example data
mu1 = [-1, -1]
cov1 = np.eye(2)

mu2 = [2,3]
cov2 = np.eye(2) * 3

C1 = np.random.multivariate_normal(mu1, cov1, 50)
C2 = np.random.multivariate_normal(mu2, cov2, 50)

plt.plot(C1[:, 0], C1[:, 1], 'or')
plt.plot(C2[:, 0], C2[:, 1], 'xb')

plt.xlim([-3, 6])
plt.ylim([-3, 7])

X = np.vstack((C1, C2))
N = X.shape[0]
X1 = np.hstack((np.ones((N, 1)), X.reshape((X.shape[0], -1))))

T = np.ones(N)
T[:50] *= -1 
#### perceptron learning

maxiter = 1000
alpha = 0.1

w = np.zeros(3) 

plt.plot(T)
for i in range(maxiter):
    
    converged = True
    for k in range(N):
        ##### TODO: add codes here
    
    if converged:
        print("converged at ", i)
        break

print("End of training: ", i)
plt.plot(X1@w)

# show decision boundary 
plt.plot(C1[:, 0], C1[:, 1], 'or')
plt.plot(C2[:, 0], C2[:, 1], 'xb')


xt = np.array([-3, 5])
yt = -w[1] * xt / w[2] - w[0] / w[2]

plt.plot(xt, yt)
plt.xlim([-3, 6])
plt.ylim([-3, 7])<jupyter_output><empty_output><jupyter_text>Pocket Algorithm for Training PerceptronTo overcome the unstability of the previous algorithm, the pocket algorithm keeps the best solution so far *in its pocket*. Thus, $\wv_{pocket}$ will contain the best solution so far.<jupyter_code>from copy import deepcopy as copy 


maxiter = 10000
alpha = 0.1


# return 1 if w is better -1 if wp is better
def compare(X, T, w, wp):
    y = np.sign(X @ w)
    yp = np.sign(X @ wp)

    return 1 if np.sum(y == T) >= np.sum(yp == T) else -1
    
    

w = np.zeros(3)
w_pocket = copy(w)

plt.plot(T)

###### TODO: looking the perceptron algorithm, finish pocket algorithm here





print("End of training: ", i)
plt.plot(X1@w_pocket)
# show decision boundary 
plt.plot(C1[:, 0], C1[:, 1], 'or')
plt.plot(C2[:, 0], C2[:, 1], 'xb')


xt = np.array([-3, 5])
yt = -w_pocket[1] * xt / w_pocket[2] - w_pocket[0] / w_pocket[2]

plt.plot(xt, yt)
plt.xlim([-3, 6])
plt.ylim([-3, 7])<jupyter_output><empty_output><jupyter_text>Ordinary Least Squares for Classification Can we use the ordinary least squares for regression on classificaiton problem? Remember your answer in your mind. Let us answer to this question in class. Until then, assuming that it is possible, try it here and plot it.Does the results here have the same answer?<jupyter_code># linear regression for the classifcation

X1 = # TODO: create X1 with one's column for bias
w_ls = # ordinary least squares 

Y =  # using w_ls, estimate the target

# plot
plt.plot(T)
plt.plot(Y)
# plot results with decision boundary
plt.plot(C1[:, 0], C1[:, 1], 'or')
plt.plot(C2[:, 0], C2[:, 1], 'xb')


xt = np.array([-2, 5])
yt = -w_ls[1] * xt / w_ls[1] - w_ls[0] / w_ls[1]

plt.plot(xt, yt)
plt.xlim([-3, 6])
plt.ylim([-3, 7])<jupyter_output><empty_output><jupyter_text>MeasurementsHow to evaluate a machine learning model is critical for the choice of right tools and performance. For various reason, there are several classification measurements to meet different needs for practical applications. In this section, we examine popular measures. One naive evaluation we can think of is the rate or percentage or correct classification. That is, when there are 1000 target lables to classify, if 950 are correctly classified, we can say 95% accuracy: $$   \text{Accuracy} = \frac{\text{The number of correct classification}}{\text{The number of samples}}.$$This measure, however, can be uninformative, especially when the importance of each class is different. As in our previous discussion about imbalance of data samples, sometimes we need to care more a specific class.For this, confusion matrix lists all the counts for all classes.  Confusion MatrixHere is an example confusion matrix.  | - | +  --|--|-- - | 439 | 28 + | 22 | 511  Table 1. Example Confusion Matrix   Here, each row represents the predictions from model and column represents the actual classes. So, we can read this that for negative samples, 439 samples are correctly classified while 511 samples are correctly classified for positive data. Overall the accuracy is 95% but with confusion matrix we have more information about the classification results. Here follows the short implementation of confusion matrix.Read through the codes and let me know if you have a question in class.<jupyter_code>import numpy as np 
import pandas as pd
# Confustion matrix 

def confusion_matrix(Y, T):
    """
        Y    ndarray
             predicted labels
        T    ndarray
             target labels
             
        @cfm DataFrame
             confusion matrix
    """
    
    if len(Y) != len(T):
        raise ValueError("Wrong prediction and target length!")
    
    classes = np.unique(T)
    n_classes = len(classes)
    
    cfm = pd.DataFrame(np.zeros((n_classes, n_classes)), index=classes, columns=classes, dtype=int)
    
    Tidx = [T == c for c in classes]
    for c in classes:
        pred_idx = Y == c
        cfm.loc[c, :] = [np.sum(np.logical_and(pred_idx, tidx)) for tidx in Tidx]
    
    return cfm
Y = np.array([1,2,1,1,1,2,3,4])
T = np.array([1,3,1,2,1,2,4,4])

confusion_matrix(Y, T)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1328719723183391, 'fraction_numerical': 0.0243598615916955, 'mean_word_length': 3.785430463576159, 'pattern_counts': {'":': 0, '<': 19, '<?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': '587884', 'license': 'MIT', 'n_tokens_mistral': 2522, 'n_tokens_neox': 2372, 'n_words': 911, 'path': 'reading_assignments/questions/2_Note-Linear Classification.ipynb', 'repo_name': 'biqar/Fall-2020-ITCS-8156-MachineLearning', 'size': '7225'}