Nearest Neighbour and Linear Classification $(30$ marks$)$

We have studied a linear classifier Logistic Regression y $=$ $($wx $+$ w$0).$ If z $>=0,$ $($z$)>=$

$0\mathrm{.}5$ and y can be regarded as class $1,$ and otherwise $0$ if z $<0.$ The parameters to be

learnt are w and w$0.$ The $$Nearest neighbour classifier$($NN$)$ is a different approach to

learning from data. Suppose we are given N points $($x$1,$ y$1),...,($xN $,$ yN $)$ where yi in $\{0,1\}$;

for a parameter k and given a new point x $,$ the k$-$NN approach does the following: find

xj$1,...,$ xjk the k$-$closest points to x $,$ then output $$y $$ as the majority label from the set

$\{$yj$1,...,$ yjk $\},$ i$.$e$.,$ the most commonly occurring label among the k$-$nearest neighbours.

$1.$ What advantage$($s$)$ does the k$-$NN approach offer over a linear classifier like the logistic

regression? $(10$ marks$)$

$2.$ What advantage$($s$)$ does the logistic regression offer over the k$-$NN approach? $(10$

marks$)$

$3.$ What is the computational cost of predicting the label $$y $?(10$ marks$)$