{"word_count": 487, "character_count": 7219}
Eighth post of our series on classification from scratch. The latest one was on the SVM, and today, I want to get back on very old stuff, with here also a linear separation of the space, using Fisher's linear discriminent analysis.Bayes (naive) classifierConsider the follwing naive classification rule[latex display="true"]m^\star(\mathbf{x})=\text{argmin}_y\{\mathbb{P}[Y=y\vert\mathbf{X}=\mathbf{x}]\}[/latex]or[latex display="true"]m^\star(\mathbf{x})=\text{argmin}_y\left\{\frac{\mathbb{P}[\mathbf{X}=\mathbf{x}\vert Y=y]}{\mathbb{P}[\mathbf{X}=\mathbf{x}]}\right\}[/latex](where [latex]\mathbb{P}[\mathbf{X}=\mathbf{x}][/latex] is the density in the continuous case).In the case where [latex]y[/latex] takes two values, that will be standard [latex]\{0,1\}[/latex] here, one can rewrite the later as[latex display="true"]m^\star(\mathbf{x})=\begin{cases}1\text{ if }\mathbb{E}(Y\vert \mathbf{X}=\mathbf{x})&#62;\displaystyle{\frac{1}{2}}\\0\text{ otherwise}\end{cases}[/latex]and the set[latex display="true"]\mathcal{D}_S =\left\{\mathbf{x},\mathbb{E}(Y\vert \mathbf{X}=\mathbf{x})=\frac{1}{2}\right\}[/latex]is called the decision boundary.Assume that[latex display="true"]\mathbf{X}\vert Y=0\sim\mathcal{N}(\mathbf{\mu}_0,\mathbf{\Sigma})[/latex]and[latex display="true"]\mathbf{X}\vert Y=1\sim\mathcal{N}(\mathbf{\mu}_1,\mathbf{\Sigma})[/latex]then explicit expressions can be derived.[latex display="true"]m^\star(\mathbf{x})=\begin{cases}1\text{ if }r_1^2&#60; r_0^2+2\displaystyle{\log\frac{\mathbb{P}(Y=1)}{\mathbb{P}(Y=0)}+\log\frac{\vert\mathbf{\Sigma}_0\vert}{\vert\mathbf{\Sigma}_1\vert}}\\0\text{ otherwise}\end{cases}[/latex]where [latex]r_y^2[/latex] is the Manalahobis distance, [latex display="true"]r_y^2 = [\mathbf{X}-\mathbf{\mu}_y]^{\text{{T}}}\mathbf{\Sigma}_y^{-1}[\mathbf{X}-\mathbf{\mu}_y][/latex]Let [latex]\delta_y[/latex]be defined as[latex display="true"]\delta_y(\mathbf{x})=-\frac{1}{2}\log\vert\mathbf{\Sigma}_y\vert-\frac{1}{2}[{\color{blue}{\mathbf{x}}}-\mathbf{\mu}_y]^{\text{{T}}}\mathbf{\Sigma}_y^{-1}[{\color{blue}{\mathbf{x}}}-\mathbf{\mu}_y]+\log\mathbb{P}(Y=y)[/latex]the decision boundary of this classifier is [latex display="true"]\{\mathbf{x}\text{ such that }\delta_0(\mathbf{x})=\delta_1(\mathbf{x})\}[/latex]which is quadratic in [latex]{\color{blue}{\mathbf{x}}}[/latex]. This is the quadratic discriminant analysis. This can be visualized bellow.The decision boundary is hereBut that can't be the linear discriminant analysis, right? I mean, the frontier is not linear... Actually, in Fisher's seminal paper, it was assumed that [latex]\mathbf{\Sigma}_0=\mathbf{\Sigma}_1[/latex].In that case, actually, [latex display="true"]\delta_y(\mathbf{x})={\color{blue}{\mathbf{x}}}^{\text{T}}\mathbf{\Sigma}^{-1}\mathbf{\mu}_y-\frac{1}{2}\mathbf{\mu}_y^{\text{T}}\mathbf{\Sigma}^{-1}\mathbf{\mu}_y+\log\mathbb{P}(Y=y)[/latex] and the decision frontier is now linear in [latex]{\color{blue}{\mathbf{x}}}[/latex]. This is the linear discriminant analysis. This can be visualized bellowHere the two samples have the same variance matrix and the frontier isLink with the logistic regressionAssume as previously that[latex display="true"]\mathbf{X}\vert Y=0\sim\mathcal{N}(\mathbf{\mu}_0,\mathbf{\Sigma})[/latex]and[latex display="true"]\mathbf{X}\vert Y=1\sim\mathcal{N}(\mathbf{\mu}_1,\mathbf{\Sigma})[/latex]then[latex display="true"]\log\frac{\mathbb{P}(Y=1\vert \mathbf{X}=\mathbf{x})}{\mathbb{P}(Y=0\vert \mathbf{X}=\mathbf{x})}[/latex]is equal to [latex display="true"]\mathbf{x}^{\text{{T}}}\mathbf{\Sigma}^{-1}[\mathbf{\mu}_y]-\frac{1}{2}[\mathbf{\mu}_1-\mathbf{\mu}_0]^{\text{{T}}}\mathbf{\Sigma}^{-1}[\mathbf{\mu}_1-\mathbf{\mu}_0]+\log\frac{\mathbb{P}(Y=1)}{\mathbb{P}(Y=0)}[/latex]which is linear in [latex]\mathbf{x}[/latex][latex display="true"]\log\frac{\mathbb{P}(Y=1\vert \mathbf{X}=\mathbf{x})}{\mathbb{P}(Y=0\vert \mathbf{X}=\mathbf{x})}=\mathbf{x}^{\text{{T}}}\mathbf{\beta}[/latex]Hence, when each groups have Gaussian distributions with identical variance matrix, then LDA and the logistic regression lead to the same classification rule.Observe furthermore that the slope is proportional to [latex]\mathbf{\Sigma}^{-1}[\mathbf{\mu}_1-\mathbf{\mu}_0][/latex], as stated in Fisher's article. But to obtain such a relationship, he observe that the ratio of between and within variances (in the two groups) was[latex display="true"]\frac{\text{variance between}}{\text{variance within}}=\frac{[\mathbf{\omega}\mathbf{\mu}_1-\mathbf{\omega}\mathbf{\mu}_0]^2}{\mathbf{\omega}^{\text{T}}\mathbf{\Sigma}_1\mathbf{\omega}+\mathbf{\omega}^{\text{T}}\mathbf{\Sigma}_0\mathbf{\omega}}[/latex]which is maximal when [latex]\mathbf{\omega}[/latex] is proportional to [latex]\mathbf{\Sigma}^{-1}[\mathbf{\mu}_1-\mathbf{\mu}_0][/latex], when [latex]\mathbf{\Sigma}_0=\mathbf{\Sigma}_1[/latex].Homebrew linear discriminant analysisTo compute vector [latex]\mathbf{\omega}[/latex]m0 = apply(myocarde[myocarde$PRONO=="0",1:7],2,mean)m1 = apply(myocarde[myocarde$PRONO=="1",1:7],2,mean)Sigma = var(myocarde[,1:7])omega = solve(Sigma)%*%(m1-m0)omega                 [,1]FRCAR -0.012909708542INCAR  1.088582058796INSYS -0.019390084344PRDIA -0.025817110020PAPUL  0.020441287970PVENT -0.038298291091REPUL -0.001371677757For the constant - in the equation [latex]\omega^T\mathbf{x}+b=0[/latex] - if we have equiprobable probabilities, useb = (t(m1)%*%solve(Sigma)%*%m1-t(m0)%*%solve(Sigma)%*%m0)/2Application (on the small dataset)In order to visualize what's going on, consider the small dataset, with only two covariates,x = c(.4,.55,.65,.9,.1,.35,.5,.15,.2,.85)y = c(.85,.95,.8,.87,.5,.55,.5,.2,.1,.3)z = c(1,1,1,1,1,0,0,1,0,0)df = data.frame(x1=x,x2=y,y=as.factor(z))m0 = apply(df[df$y=="0",1:2],2,mean)m1 = apply(df[df$y=="1",1:2],2,mean)Sigma = var(df[,1:2])omega = solve(Sigma)%*%(m1-m0)omega         [,1]x1 -2.640613174x2  4.858705676Using R regular function, we getlibrary(MASS)fit_lda = lda(y ~x1+x2 , data=df)fit_ldaCoefficients of linear discriminants:            LD1x1 -2.588389554x2  4.762614663which is the same coefficient as the one we got with our own code. For the constant, useb = (t(m1)%*%solve(Sigma)%*%m1-t(m0)%*%solve(Sigma)%*%m0)/2If we plot it, we get the red straight lineplot(df$x1,df$x2,pch=c(1,19)[1+(df$y=="1")])abline(a=b/omega[2],b=-omega[1]/omega[2],col="red")As we can see (with the blue points), our red line intersects the middle of the segment of the two barycenterspoints(m0["x1"],m0["x2"],pch=4)points(m1["x1"],m1["x2"],pch=4)segments(m0["x1"],m0["x2"],m1["x1"],m1["x2"],col="blue")points(.5*m0["x1"]+.5*m1["x1"],.5*m0["x2"]+.5*m1["x2"],col="blue",pch=19)Of course, we can also use R functionpredlda = function(x,y) predict(fit_lda, data.frame(x1=x,x2=y))$class==1vv=outer(vu,vu,predlda)contour(vu,vu,vv,add=TRUE,lwd=2,levels = .5)One can also consider the quadratic discriminent analysis since it might be difficult to argue that [latex]\mathbf{\Sigma}_0=\mathbf{\Sigma}_1[/latex]fit_qda = qda(y ~x1+x2 , data=df)The separation curve is hereplot(df$x1,df$x2,pch=19,col=c("blue","red")[1+(df$y=="1")])predqda=function(x,y) predict(fit_qda, data.frame(x1=x,x2=y))$class==1vv=outer(vu,vu,predlda)contour(vu,vu,vv,add=TRUE,lwd=2,levels = .5)