24:null 25:["$","title",null,{"children":"ML | 3 Linear Classification 3.1 Perceptron and Linear Discriminant Analysis (LDA) | Zhihao Yao | Observable"}] 2a:T75a,
> Sample data which can be linearly classified:

> ${tex.block`\left\{\left(x_{i}, y_{i}\right)\right\}_{i=1}^{N} \\~\\ \text{where } x_{i} \in \mathbb{R}^{p}, y_{i}\{-1,+1\}`} >
> Stochastic gradient descent (SGD) is used to find a hyperplane (${tex`w^{T} x+b=0`}) in the feature space ${tex`\mathbb{R}^{p}`} to classify the data into positive and negative classes (${tex`w \in \mathbb{R}^{p}`} is a vector normal to the hyperplane and ${tex`b`} is an offset). >

> Perceptron is error-driven. Model is ${tex`f(x)=\operatorname{sign}\left(w^{T} x+b\right)`}. ${tex`M`} is the set of misclassified points.

> For the misclassified data points:
> ${tex.block`-y_{i}\left(w^{T} x_{i}+b\right)>0 \\`} > A choice of the loss function is the number of misclassified points:
> ${tex.block`L(w)=\sum_{i=1}^{N} I\left\{-y_{i}\left(w^{T} x_{i}+b\right)>0\right\} \\`} > but such a loss function is not differentiable and cannot be easily optimized. Another loss function is the total distance from the misclassification points to the hyperplane. > The distance from one point ${tex`x_0`} in space ${tex`R^{p}`} to the hyperplane:
> ${tex.block`\frac{\left|w^{T} x_{0}+b\right|}{\|w\|} \\`} > **Perceptron loss function**:
> ${tex.block`L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w^{T} x_{i}+b\right) \\`} > **Gradient of the loss function**:
> ${tex.block`\frac{\partial L(w, b)}{\partial w} =-\sum_{x_{i} \in M} y_{i} x_{i} \\ \frac{\partial L(w, b)}{\partial b} =-\sum_{x_{i} \in M} y_{i} \\`} >> 1. set initial values of ${tex`w_0, b_0`} >> 2. select data point ${tex`(x_i, y_i)`} from the training dataset >> 3. if ${tex`y_{i}\left(w^{T} x_{i}+b\right) \leq 0`}, update the parameters:
>> ${tex`w \leftarrow w+\eta y_{i} x_{i} \\ b \leftarrow b+\eta y_{i}`} >> 4. repeat step 2 until there is no misclassified data point 2b:T1437,> Linear discriminant analysis can be used for binary classification problems. The process is to find an optimal projection direction to minimize the distance inside the same class and maximize the distance between different classes (minimize the variance for each class and maximize the difference between the means of different classes). >

> Data: >
> ${tex.block` X=\left(x_{1}, x_{1}, \cdots, x_{N}\right)^{T}=\left(\begin{array}{c} x_{1}^{T} \\ x_{2}^{T} \\ \vdots \\ x_{N}^{T} \end{array}\right)_{N \times p} Y=\left(\begin{array}{c} y_{1} \\ y_{2} \\ \vdots \\ y_{N} \end{array}\right)_{N \times 1} \\~\\ \left\{\left(x_{i}, y_{i}\right)\right\}_{i=1}^{N}, x_{i} \in \mathbb{R}^{p}, y_{i} \in\left\{\frac{+1}{C_{1}}, \frac{-1}{C_{2}}\right\} \\~\\ x_{C_{1}}=\left\{x_{i} \mid y_{i}=+1\right\}, x_{C_{2}}=\left\{x_{i} \mid y_{i}=-1\right\} \\~\\ \left|x_{C_{1}}\right|=N_{1},\left|x_{C_{2}}\right|=N_{2}, N_{1}+N_{2}=N `}
**Loss function for LDA**
The direction vector of the projection axis is ${tex`w`}. After projecting the sample points onto this axis, the value for each data point ${tex`z_i = w^T x_i`}.
Mean and variance are:

Mean: ${tex`\bar{z}=\frac{1}{N} \sum_{i=1}^{N} z_{i}=\frac{1}{N} \sum_{i=1}^{N} w^{T} x_{i}`}

Variance: ${tex`S_{z}=\frac{1}{N} \sum_{i=1}^{N}\left(w^{T} x_{i}-\bar{z}\right)\left(w^{T} x_{i}-\bar{z}\right)^{T}`}

Mean and variance for each class:

${tex`C_{1}: \\`} ${tex.block` \bar{z}_{1}=\frac{1}{N_{1}} \sum_{i=1}^{N_{1}} w^{T} x_{i} \\ S_{1}=\frac{1}{N_{1}} \sum_{i=1}^{N_{1}}\left(w^{T} x_{i}-\bar{z}_{1}\right)\left(w^{T} x_{i}-\bar{z}_{1}\right)^{T} \\ `} ${tex`C_{2}: \\`} ${tex.block` \bar{z}_{2}=\frac{1}{N_{2}} \sum_{i=1}^{N_{2}} w^{T} x_{i}\\ S_{2}=\frac{1}{N_{2}} \sum_{i=1}^{N_{2}}\left(w^{T} x_{i}-\bar{z}_{2}\right)\left(w^{T} x_{i}-\bar{z}_{2}\right)^{T} \\ `}

The goal of the loss function is to minimize the variance for each class and maximize the difference between the means of two different classes:

${tex.block` J(w)=\frac{\left(\bar{z}_{1}-\bar{z}_{2}\right)^{2}}{S_{1}+S_{2}} \\~\\~\\ \text{Numerator: } \left(\bar{z}_{1}-\bar{z}_{2}\right)^{2}=\left(\frac{1}{N_{1}} \sum_{i=1}^{N_{1}} w^{T} x_{i}-\frac{1}{N_{2}} \sum_{i=1}^{N_{2}} w^{T} x_{i}\right)^{2} \\~\\ =\left[w^{T}\left(\frac{1}{N_{1}} \sum_{i=1}^{N_{1}} x_{i}-\frac{1}{N_{2}} \sum_{i=1}^{N_{2}} x_{i}\right)\right]^{2} \\~\\ =\left[w^{T}\left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right)\right]^{2} \\~\\ =w^{T}\left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right)\left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right)^{T} w \\~\\~\\ \text{Denominator: } S_{1}=\frac{1}{N_{1}} \sum_{i=1}^{N_{1}}\left(w^{T} x_{i}-\bar{z}_{1}\right)\left(w^{T} x_{i}-\bar{z}_{1}\right)^{T} \\~\\ =\frac{1}{N_{1}} \sum_{i=1}^{N_{1}}\left(w^{T} x_{i}-\frac{1}{N_{1}} \sum_{i=1}^{N_{1}} w^{T} x_{i}\right)\left(w^{T} x_{i}-\frac{1}{N_{1}} \sum_{i=1}^{N_{1}} w^{T} x_{i}\right)^{T} \\~\\ =\frac{1}{N_{1}} \sum_{i=1}^{N_{1}} w^{T}\left(x_{i}-\bar{x}_{C_{1}}\right)\left(x_{i}-\bar{x}_{C_{1}}\right)^{T} w \\~\\ =w^{T}\left[\frac{1}{N_{1}} \sum_{i=1}^{N_{1}}\left(x_{i}-\bar{x}_{C_{1}}\right)\left(x_{i}-\bar{x}_{C_{1}}\right)^{T}\right] w \\~\\ =w^{T} S_{C_{1}} w \\~\\ S_{1}+S_{2} =w^{T} S_{C_{1}} w+w^{T} S_{C_{2}} w \\~\\ S_{1}+S_{2}=w^{T} S_{C_{1}} w+w^{T} S_{C_{2}} w=w^{T}\left(S_{C_{1}}+S_{C_{2}}\right) w \\~\\~\\ \therefore J(w)=\frac{w^{T}\left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right)\left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right)^{T} w}{w^{T}\left(S_{C_{1}}+S_{C_{2}}\right) w} \\~\\~\\ \text { let }\left\{\begin{array}{c}S_{b}=\left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right)\left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right)^{T} \\S_{w}=S_{C_{1}}+S_{C_{2}}\end{array}\right. \\~\\ J(w)=\frac{w^{T} S_{b} w}{w^{T} S_{w} w}=w^{T} S_{b} w\left(w^{T} S_{w} w\right)^{-1} \\~\\ \frac{\partial J(w)}{\partial w}=2 S_{b} w\left(w^{T} S_{w} w\right)^{-1}+w^{T} S_{b} w(-1)\left(w^{T} S_{w} w\right)^{-2} 2 S_{b} w \\~\\ =2\left[S_{b} w\left(w^{T} S_{w} w\right)^{-1}+w^{T} S_{b} w(-1)\left(w^{T} S_{w} w\right)^{-2} S_{b} w\right]=0 \\~\\ \left(w^{T} S_{b} w, w^{T} S_{w} w \in \mathbb{R} \text{ since } w^T: 1 \times p \quad S_b: p \times p \quad w: p \times 1 \right) \\~\\ \Rightarrow S_{b} w\left(w^{T} S_{w} w\right)-w^{T} S_{b} w S_{w} w=0 \\~\\ \Rightarrow w^{T} S_{b} w S_{w} w=S_{b} w\left(w^{T} S_{w} w\right) \\~\\ \Rightarrow S_{w} w=\frac{w^{T} S_{w} w}{w^{T} S_{b} w} S_{b} w \\~\\ \Rightarrow w=\frac{w^{T} S_{w} w}{w^{T} S_{b} w} S_{w}^{-1} S_{b} w \\~\\ \text { (Please note: for } w \text { we only care its direction, not size (we can do scaling)) } \\~\\ \Rightarrow w \propto S_{w}^{-1} S_{b} w \\~\\ \Rightarrow w \propto S_{w}^{-1}\left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right) \underbrace{\left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right)^{T} w}_{1 \text { dimension}\in \mathbb{R}} \\~\\ \Rightarrow w \propto S_{w}^{-1}\left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right) \\~\\ \Rightarrow w \propto \left(S_{C_{1}}+S_{C_{2}}\right) \left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right) \\~\\ `} > if ${tex`S_{w}^{-1}`} is a Isotropic diagonal matrix, ${tex`w \propto \left(\bar{x}_{C_{1}}-\bar{x}_{C_{2}}\right)`}2c:[] 28:{"id":"2045f47a13708f42","slug":"ml-3-linear-classification-3-1","title":"ML | 3 Linear Classification 3.1 Perceptron and Linear Discriminant Analysis (LDA)","thumbnail":"5f2be07d39eeae406a7de71be6f1c1aa54662c2b5c445e8fe8fded66e03b90d1","access_level":"public","create_time":"$D2022-03-24T14:02:47.556Z","update_time":"$D2022-04-21T14:48:37.923Z","view_time":null,"first_public_time":"$D2022-03-29T15:38:47.947Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"610db6fe9b10a76c","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":"starter_2024"},"version":599,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"01b5d984f2428b1a","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":null}],"members":[{"type":"individual","id":"01b5d984f2428b1a","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":null,"role":"editor"},{"type":"team","id":"610db6fe9b10a76c","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":"starter_2024","role":"viewer"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"102982dc3961aa5a","slug":"machine-learning-notes","title":"Machine Learning Notes","owner":{"id":"610db6fe9b10a76c","login":"howardyao","name":"Zhihao Yao"}},"type":"notebook","body":{"title":"ML | 3 Linear Classification 3.1 Perceptron and Linear Discriminant Analysis (LDA)","cells":[{"id":0,"value":"# ML | 3 Linear Classification

3.1 Perceptron and
Linear Discriminant Analysis (LDA)\n

","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"> ${tex`\n \\large \\text{Linear Regression} \\xRightarrow[\\text{function}]{\\text{activation}} \\text{Linear Classification} \\\\~\\\\\n`}\n\n> ${tex`\n\\ y=f\\left(w^{T} x+b\\right), y \\in\\left\\{\\begin{array}{l}\n\\{0,1\\}, \\text { Hard classification (decision boundary) } \\\\\n{[0,1], \\text { Soft classification (probability)}}\n\\end{array}\\right. \\\\~\\\\\n\n\\text { Activation function } f: w^{T} x+b \\mapsto\\{0,1\\} /[0,1] \\\\~\\\\\n\\text { Link function } f^{-1} : \\{0,1\\} /[0,1] \\mapsto w^{T} x+b \\\\~\\\\\n`}\n\n

\n\n> ${tex`\n\\text{Linear Classification} \\left\\{\\begin{array}{l}\n{\\color{steelblue} \\text {Hard classification}}\n \\left\\{\\begin{array}{l}\n {\\color{steelblue} \\text {Linear Discriminant Analysis (LDA)}} \\\\\n {\\color{steelblue} \\text {Perceptron}}\n \\end{array}\\right. \\\\~\\\\\n\\text {Soft classification }\n \\left\\{\\begin{array}{l}\n \\text {Gaussian Discriminant Analysis (GDA)} \\\\\n \\text {Naive Bayesian} \\\\\n \\text {Logistic Regression} \n \\end{array}\\right. \\\\\n\\end{array}\\right.\n`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":315,"value":"

\n## Perceptron","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":272,"value":"viewof stepslider","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":269,"value":"viewof selection","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":554,"value":"*Source: https://observablehq.com/@andreaskdk/perceptron*","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":72,"value":"$2a","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":465,"value":"

\n## Linear Discriminant Analysis","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":508,"value":"{\n const p = plotter({\n xLabel:'X1', \n yLabel:'X2',\n grid: false\n });\n const d1 = [[-4,3.4], [-5, 3], [-3,2], [-4.5, 3.5], [-4,2.5], [-2,1]]\n const d2 = [[-4.3,5.4], [-5.1, 6], [-3.2,5], [-4, 7.5], [-3.5,6.5], [-2,5]]\n for (let i=0; i {\n console.log(d);\n },\n });\n p.text('LDA Classification', 6.2, -2, { size: 14, stroke: 'black', baseline: 'auto'})\n return p.node;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":321,"value":"$2b","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":142,"value":"

\n## Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":354,"value":"**Perceptron**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":280,"value":"data2 = aq.table({\n x: PerceptronResult[0],\n y: PerceptronResult[1],\n c: PerceptronResult[3]\n}).objects()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":158,"value":"// py`${funcPerceptron}(${pars.sample}, ${pars.lambda}, ${pars.complex})`\nPerceptronResult = py`${funcPerceptron}()`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"funcPerceptron = py`from sklearn import datasets\nimport numpy as np\nnp.random.seed(10)\n\niris=datasets.load_iris()\nX = np.vstack((iris.data[0:20,:2],iris.data[80:100,:2]))\ny = np.vstack((iris.target[0:20],iris.target[80:100]))\ny=np.array([1 if i==1 else -1 for i in y.flatten()])\n\ndef fp(learning_rate = 0.1):\n w=np.ones((X.shape[1],1))\n b=1\n learning_rate=learning_rate\n Round=0\n All_Correct=False \n errors = []\n \n while not All_Correct:\n misclassified_count=0\n total_error = 0\n for i in range(X.shape[0]):\n XX=X[i,]\n yy=y[i]\n if yy * (np.dot(w.T,XX.T)+b)<0:\n w+=learning_rate * np.dot(XX,yy).reshape(2,1)\n b+=learning_rate * yy\n misclassified_count +=1\n total_error += yy * (np.dot(w.T,XX.T)+b)\n if misclassified_count==0:\n All_Correct=True\n else:\n All_Correct=False\n Round += 1\n errors.append(total_error*-1)\n return [X[:,0], X[:,1], X, y, errors, w, b]\nfp`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":149,"value":"import {py, pyodide} from \"@howardyao/machine-learning-notes-2\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":250,"value":"import {viewof selection, viewof stepslider} \nfrom '@andreaskdk/perceptron'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":358,"value":"**LDA**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":363,"value":"curveData = {\n let x = Array.from({length: 6}, d3.randomNormal(-1, 0.5))\n let y = x.map(d => jstat.normal.pdf(d, -1, 0.5))\n return x.map((d,i) => ({'x': d, 'y': y[i]}))\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":327,"value":"jstat = require('jstat')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":330,"value":"import { plotter } from '50dadfdec01c15a8'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W2c","stdlib":"1","titling":"auto"}} 29:"$28:body"