ELEG $6316$ Statistical Learning for Big Data

Spring $2024$

Homework #$2$

$($Due January $31,2024)$

$($a$)$ Read the Perceptron Learning Algorithm $($PLA$)$ in Chapter $1($page $5-8)$ of the reference book: Learning from Data, by Y$.$ Abu$-$Mostafa, M$.$ Magdon$-$Ismail and H$-$T$.$ Lin, AML Press, $2012.$ ISBN: $978-1600490064.$

$($b$)$ Use a target function $f$:$20-2x_1+3x_2=0$ or create your own target function as a random line in a $2-$D plane. One side of the line maps to $+1,$ and the other side maps to $-1.$ Choose the inputs $x_n$ of the data set as random points in the plane, and evaluate the target function on each input to get the corresponding output or $-1).$ Generate a linearly separable data set of size $20$ and plot the data points as well as the target function in figure $1$ using MATLAB or other programming languages. Mark the data points of different classes differently.

$($c$)$ Run the Perceptron Learning Algorithm $($PLA$)$ on the data set above. Report the number of updates that the algorithm takes before converging. Add the obtained hypothesis $g$ in figure $1.$ Comment on whether hypothesis $g$ is close to the target function.

$($d$)$ Repeat everything in $($c$)$ with another randomly generated data set of size $20.$ Compare your results with $($c$).$

$($e$)$ Repeat everything in $($c$)$ with another randomly generated data set of size $100.$ Compare your results with $($c$).$

$($f$)$ Repeat everything in $($c$)$ with another randomly generated data set of size $1000.$ Compare your results with $($c$).$

$($g$)$ Let's increase the dimension of the plane from $2$ to $10.$ Create a linearly separable data set of size $1000$ with $x_{n}in{R}^{10}$ and feed the data set to the algorithm. How many updates does the algorithm take to converge?

$($h$)$ Repeat the algorithm on the same data set in $($g$)$ for $100$ experiments. In the iterations of each experiment, pick $x(t)$ in the update rule randomly instead of deterministically. Plot a histogram for the number of updates that the algorithm takes to converge. $[$update rule: $w(t+1)=w(t)+y(t)x(t)]$

$($i$)$ Summarize your observations and conclusions with respect to accuracy and running time as a function of $N($number of data points$)$ and $d($dimension of the data$).$

Submit your programs and supporting documents as one zip file in ecourses.