<jupyter_start><jupyter_text>Assignment 1 Due Date: 24th Jan'18In this assignment we will cover the basics of Machine Learning. We will cover the following topics:1) Linear Regression2) Logistic Regression3) EM Algorithm4) K-means/Hirarchical Clustering.It is crucial to get down to the nitty gritty of the code to implement all of these. No external packages (like scipy), which directly give functions for these algorithms, are to be used.   Linear RegressionDefination: Given a data set ${\displaystyle \{y_{i},\,x_{i1},\ldots ,x_{ip}\}_{i=1}^{n}} $ of $n$ statistical units, a linear regression model assumes that the relationship between the dependent variable $y_i$ and the $p$-vector of regressors $x_i$ is linear. This relationship is modeled through a disturbance term or error variable $ε_i$ - an unobserved random variable that adds noise to the linear relationship between the dependent variable and regressors. Thus the model takes the form:$$ {\displaystyle \mathbf {y} =X{\boldsymbol {\beta }}+{\boldsymbol {\varepsilon }},\,} $$where,$$ \mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\\vdots \\y_{n}\end{pmatrix}},\quad $$$$ {\displaystyle X={\begin{pmatrix}\mathbf {x} _{1}^{\top }\\\mathbf {x} _{2}^{\top }\\\vdots \\\mathbf {x} _{n}^{\top }\end{pmatrix}}={\begin{pmatrix}1&x_{11}&\cdots &x_{1p}\\1&x_{21}&\cdots &x_{2p}\\\vdots &\vdots &\ddots &\vdots \\1&x_{n1}&\cdots &x_{np}\end{pmatrix}},}$$$$ {\displaystyle {\boldsymbol {\beta }}={\begin{pmatrix}\beta _{0}\\\beta _{1}\\\beta _{2}\\\vdots \\\beta _{p}\end{pmatrix}},\quad {\boldsymbol {\varepsilon }}={\begin{pmatrix}\varepsilon _{1}\\\varepsilon _{2}\\\vdots \\\varepsilon _{n}\end{pmatrix}}.} $$ For this problem, in the class lecture we covered the Least Square Solution, which can be formulated as:$${\displaystyle {\hat {\boldsymbol {\beta }}}=(\mathbf {X} ^{\top }\mathbf {X} )^{-1}\mathbf {X} ^{\top }\mathbf {y} =\left(\sum \mathbf {x} _{i}\mathbf {x} _{i}^{\top }\right)^{-1}\left(\sum \mathbf {x} _{i}y_{i}\right).} $$  Question 1a) You will write the code to find the LSS for the given data. The data contains 3 columns, each for $y, X_{1}$, and $X_{2}$ respectively. Few of the possible models are:$$ {\displaystyle \mathbf {y} ={\boldsymbol {\beta_{1} }}X_1+{\boldsymbol {\beta_{0} }}+{\boldsymbol {\varepsilon }},\,} $$$$ {\displaystyle \mathbf {y} ={\boldsymbol {\beta_{2} }}X_2+{\boldsymbol {\beta_{0} }}+{\boldsymbol {\varepsilon }},\,} $$$$ {\displaystyle \mathbf {y} ={\boldsymbol {\beta_{1} }}X_1+ {\boldsymbol {\beta_{2} }}X_2+{\boldsymbol {\beta_{0} }}+{\boldsymbol {\varepsilon }},\,} $$Given this data, find the coefficients for each of these models.b) Now that you have three models, you must select the best one. Use Cross-validation with 5 folds on the dataset to find the optimal model (On the basis of RMSE on the test partition).<jupyter_code>import numpy
# Load the dataset 
train_data = np.load('utils/assign_1_data_1_train.npy')
# now write the code for finding the solution for each of the three models.
# Finally, Write The estimates of the betas here:

# Model 1

# Model 2

# Model 3

# partition the dataset into 5 random folds.

# for each fold, approx. model from the remaining folds, and calculate RMSE on the test fold.

# find avg RMSE for each model. 

# Which is the best model?

# Finally, Give the R^2 score of the best model in the test set:
test_data = np.load('utils/assign_1_data_1_test.npy')


# Bonus

# Show a graph between the predicted Y^ and the Ground truth Y

# Try to plot Y vs X_1 in train set.

# can it help you improve your model?
# construct the better model.<jupyter_output><empty_output><jupyter_text>Logistic RegressionGeneraly, Logistic Regression is used to predict categorial variables. For the simple problem of 2-way classification, the output $\hat{y_i}$ is modeled as the probability that $\{X_i\}$ belongs to class $1$ (given two classes $0$, and $1$).$$ P( \{X_i\} \in Set_1 ) = \hat{y_i}, $$ ( $y_i$ is the actual label; $y_i \in \{ 0,1 \}$ )$\hat{y_i}$ is typically modeled as the output of a sigmoid on a linear combination of the input feature $\{X_i\}$:$$ \mathbf {\hat{y}} = \sigma(X{\boldsymbol {\beta }}+{\boldsymbol {\varepsilon }}) = \sigma_\beta(X)$$ Now, The likelihood of some given data for this model can be written as:$${\displaystyle {\begin{aligned}L(\beta |x)&=Pr(Y|X;\beta )\\&=\prod _{i}Pr(y_{i}|x_{i};\beta )\\&=\prod _{i}\sigma_{\beta }(x_{i})^{y_{i}}(1-\sigma_{\beta }(x_{i}))^{(1-y_{i})}\end{aligned}}}$$ Unlike in the case of Linear regression, this equation has no closed form solution. Hence we will use gradient descent on the negative log-likelihood $J(\beta)$ to find the optimal $\beta$$$J(\beta) = \sum_i{\big( y_ilog(\hat{y_i})+ (1-y_i)log(1-\hat{y_i}) \big) }$$with the update equation:$$\beta_j = \beta_j + \alpha \times \frac{ \partial J(\beta)}{\partial \beta}$$  Question 2a) You will write the code to find the optimal logistic regression model for the given data. The data contains 3 columns, each for $y, X_{1}$, and $X_{2}$ respectively. For the rate of learning $\alpha$ use a linearly decaying policy, or step-wise reduction policy. $$ {\displaystyle \mathbf {y} =\sigma \big( {\boldsymbol {\beta_{1} }}X_1+ {\boldsymbol {\beta_{2} }}X_2+{\boldsymbol {\beta_{0} }}+{\boldsymbol {\varepsilon }}} \big) $$b) Explore possible methods of adjusting the learning rate $\alpha$<jupyter_code># Load the train dataset 
train_data = np.load('utils/assign_1_data_2_train.npy')
# now write the code to find the parameters of the optimization.

# test on a validation part every 't' iterations to find when you start overfitting.
# t = ?

# Now for 't' iterations train on the entire dataset for testing on the test_data

# find the accuracy on the test set:
test_data = np.load('utils/assign_1_data_2_test.npy')


# Bonus
# Can you adjust the learning rate alpha in a better way?<jupyter_output><empty_output><jupyter_text>EM algorithmThis is a general framework for likelihood-based parameter estimation.A basic outline of this algorithm is:* start with initial guesses of parameters* E step: estimate memberships given params* M step: estimate params given memberships* Repeat until convergence** Refer to [this link](http://www.rmki.kfki.hu/~banmi/elte/bishop_em.pdf) (9.2.2) .**  Question 3Let ${\displaystyle \mathbf {x} =(\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n})} $ be a sample of $n$ independent observations from a mixture of two multivariate normal distributions of dimension $d$ , and let ${\displaystyle \mathbf {z} =(z_{1},z_{2},\ldots ,z_{n})} $ be the latent variables that determine the component from which the observation originates.$X_i |(Z_i = 1) \sim \mathcal{N}_d(\boldsymbol{\mu}_1,\Sigma_1)$ and $X_i |(Z_i = 2) \sim \mathcal{N}_d(\boldsymbol{\mu}_2,\Sigma_2)$The aim is to estimate the unknown parameters representing the mixing value between the Gaussians and the means and covariances of each:$$ \theta = \big( \boldsymbol{\tau},\boldsymbol{\mu}_1,\boldsymbol{\mu}_2,\Sigma_1,\Sigma_2 \big) $$a) Given the data, find the parameters $\theta$ using EM algorithm.<jupyter_code># Load the train dataset 
data = np.load('utils/assign_1_data_3.npy')
# The data is a 1000*2 numpy array, where each row is a independent observation, and 
# the columns are measurement in dimension x and y respectively. 
# now write the code to find the parameter theta.

# Parameters are given by:

# Visualize the entire data by plotting them as points in a 2-D canvas.  
# Show the estimated means and the standard deviations.<jupyter_output><empty_output><jupyter_text>ClusteringFor clustering we covered two algorithms1) K-means : An iterative method to get 'K' clusters, initializing them randomly2) Hirarchical : An iterative method to get a dendogram of clustering with various numbers of cluster centers. K-means ClusteringWe initialize $K$ cluster centers $\{ c_1,c_2 ,... c_k\}$for $K$-clusters randomly. All the data points are assigned a cluster index $D_i \in \{ 1,2,...,k\}$, based on the closest cluster center to each point.Now, for each cluster, the cluster centers are re-evaluated as the mean of all the points in the center.$$c_i = mean(\{ X_j | D_j = i \})$$This process continues till convergence.  Question 4The dataset contains 1000  color images.Convert them to grayscale images. We need to cluster them into various $n$ clusters based on the similarity of their histograms. For each image, find the histogram with bin size 25 (last bin of 30;i.e.225-255;giving you 10 bins). Now treating each of these bins as seperate dimensions, find:a) Cluster Centers for $n = 5$ clusters, with $L_2$ distance criteria for measuring distance between a pair of images.b) **Bonus**: Use Earth Movers Distance in the above problem.<jupyter_code># For this problem we will be using the 1000 test images of CIFAR-10 dataset.
## Load the data from the following link
# https://www.cs.toronto.edu/~kriz/cifar.html

# Convert it to grayscale values

# find the histograms and get a 10-dimensional representation of each images.

# Use K-means to find  out the number of cluster centers.

# Visualize cluster means to see what they look like.<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13719080309469325, 'fraction_numerical': 0.015364498202026806, 'mean_word_length': 4.603174603174603, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 17, 'https://': 1, 'lorem ipsum': 0, 'www.': 2, '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': '271210', 'license': 'MIT', 'n_tokens_mistral': 2827, 'n_tokens_neox': 2652, 'n_words': 1154, 'path': 'Assignment_1.ipynb', 'repo_name': 'val-iisc/DLCV-assignments', 'size': '9177'}