<jupyter_start><jupyter_text>LAB: Random Projections : SOLUTIONS  Authors: <NAME>The aim of this material is to- to show that in practice dimension reduction can be used with no loss of accuracy on some problem- code efficient sparse random projections- apply sparse random projections together with knearestneighbors VERY IMPORTANT- This work **must be done by pairs of students**.- Each paris of students must send their jupyter notebook **before the 24th of November at 21:59** to **<EMAIL>**- The **name of the file must be** constructed as in the next cell Gentle reminder: no evaluation if you don't respect this EXACTLY How to construct the name of your file<jupyter_code># Change here using YOUR first and last names
fn1 = "robert"
ln1 = "gower"
fn2 = "pascal"
ln2 = "bianchi"

filename = "_".join(map(lambda s: s.strip().lower(), 
                        ["lab1", ln1, fn1, "and", ln2, fn2])) + ".ipynb"
print(filename)
#Throughout the notebook you will find commented boxes like this one

### TODO ###   
# please implement blabla
#############<jupyter_output><empty_output><jupyter_text>These boxes need to be replaced by code as explained in the boxes.Solutions will online tomorrow. Good luck!<jupyter_code>%matplotlib inline
import numpy as np
from scipy.linalg import norm
import matplotlib.pyplot as plt
from sklearn.datasets import load_svmlight_file
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LogisticRegression    #Logistic Regression
from sklearn.neighbors import KNeighborsClassifier 

def get_data(dataname):
    data = load_svmlight_file(dataname)
    return data[0], data[1]<jupyter_output><empty_output><jupyter_text>EXERCISE 1: Use LogisticRegression classifier of Scikit-learn to experimentally confirm the following corollary proven in class and test random sparse projections Corollary of Range Space Preserving Theorem  Let $$ X^\top = [x_1, \ldots, x_n]\in \mathbb{R}^{n\times d},$$be our data matrix and let$$  X X^\top= [\hat{x}_1, \ldots, \hat{x}_n]^\top \in \mathbb{R}^{n\times n}. $$We can find a solution to the following training problem$$ w^* \in \min_{w \in \mathbb{R}^d}  \frac{1}{n}\sum_{i=1}^n \ell_i(\langle x_i,w \rangle) \hspace{3cm} (I)$$by instead solving $$ \hat{w}^* \in \min_{w \in \mathbb{R}^n}  \frac{1}{n}\sum_{i=1}^n \ell_i(\langle \hat{x}_i,w \rangle) \hspace{3cm} (II)$$and  $ X ^\top \hat{w}^*$ is a solution to $(I)$**NOTE:** The matrix $X$ is transposed with respect to the data matrix defined in class and in the lectures ! Be careful with dimnensions! End Corollary1) [2pts] Show that by setting the regularization parameter close to zero (C = 10^9) in LogisticRegression, the score obtained by training using $X$ and $XX^\top$ is the same  2) [2pts] Compute a solution $w^*_1$  by directly solving (I).  Compare this $w^*_1$ to the recovered solution $X \hat{w}^*$. Are they the same? Justify based on Corollary.3) [6pts] Using a random generated gaussian matrix $W \in\mathbb{R}^{d\times r}$ , project the data matrix $X \rightarrow XW$. Test for different values of r andapply logistic regression to the resulting projected matrix. Can you explain what you observe?<jupyter_code># download the colon-cancer data set from 
# https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary/colon-cancer.bz2
# Unpack and place in the same folder as this python notebook
dataname = "colon-cancer"  
X, y = get_data(dataname)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33, random_state=42)
n, d = X_train.shape
print('{n} data points and {d} features'.format(n = n,d =d))
C0 = 10**9 # almost no regularization, since this is the inverse of the regularization parameter, i.e, C = 1/lambda
log_reg = LogisticRegression(C = C0) # , multi_class = "multinomial"
log_reg.fit(X_train, y_train)
print('Accuracy on the training set: {:.3f}'.format(log_reg.score(X_train,y_train)))
print('Accuracy on the test set: {:.3f}'.format(log_reg.score(X_test,y_test)))
### TODO ###   
# 2)  Compute a solution $w^*_1$  by directly solving (I).  
# Compare this $w^*_1$ to the recovered solution $X^\top \hat{w}^*$.
# Are they the same? Justify based on Corollary.
#############
### TODO ### 
## Choose a range of different projected dimensions to test
## Suggested range of projected dimensions:
upperbnd = d
project_dimensions = range(1,upperbnd,int((upperbnd )/10))
#############
test_accuracy = []
training_accuracy = []
s = 20
for r in project_dimensions: 
    ### TODO ###   
    # 3)    project the data matrix $X \rightarrow XW$ using Gaussian and fit, 
    #      transform and score using Logstic Regression
    # trainscore =  ??
    trainscore=0 # Change this!
    training_accuracy.append(trainscore)
    # testscore = ??
    testscore=0# Change this!
    test_accuracy.append(testscore)
    #############
    print ("project dimension %4d gives: (train, test) =  (%.4f, %.4f)" % (r, trainscore,testscore))
# coef_recover= log_regt.coef_.dot(X_train.transpose())

plt.plot(project_dimensions,training_accuracy, label='Accuracy of the training set')
plt.plot(project_dimensions,test_accuracy, label='Accuracy of the test set')
plt.ylabel('Accuracy')
plt.xlabel('Projected Dimension')
plt.legend()
index_max = np.argmax(test_accuracy)
print("Best score was for r =%5d with: (train, test) =  (%.4f, %.4f)"% (project_dimensions[index_max], training_accuracy[index_max],test_accuracy[index_max]))<jupyter_output>project dimension    1 gives: (train, test) =  (0.0000, 0.0000)
project dimension  201 gives: (train, test) =  (0.0000, 0.0000)
project dimension  401 gives: (train, test) =  (0.0000, 0.0000)
project dimension  601 gives: (train, test) =  (0.0000, 0.0000)
project dimension  801 gives: (train, test) =  (0.0000, 0.0000)
project dimension 1001 gives: (train, test) =  (0.0000, 0.0000)
project dimension 1201 gives: (train, test) =  (0.0000, 0.0000)
project dimension 1401 gives: (train, test) =  (0.0000, 0.0000)
project dimension 1601 gives: (train, test) =  (0.0000, 0.0000)
project dimension 1801 gives: (train, test) =  (0.0000, 0.0000)
Best score was for r =    1 with: (train, test) =  (0.0000, 0.0000)<jupyter_text>Exercise 2:In class we used $$ X \rightarrow W^\top X $$But here it is instead$$ X \rightarrow X W $$Now we will train a model using a large text based data set. For this you need to code the following random transform $W \in \mathbb{R}^{d \times r}$ that takes a sparsity parameter $s$ as an input and outputs a matrix$$ W_{ij}  = \sqrt{\frac{s}{r}}\begin{cases}1 \quad & \mbox{with probability }\frac{1}{2s} \\0 \quad & \mbox{with probability }1-\frac{1}{s} \\-1 \quad & \mbox{with probability }\frac{1}{2s} \end{cases}$$* Code a function Generate_Sparse_Transform$(s,r,d)$ that takes an input     * sparsity parameter  $s$   * input dimension $d \in \mathbb{N}$   * lower dimensional projected dimension $r \in \mathbb{N}$and gives as outputs the matrix $W$ stored in an efficient sparse format such as the CSC formart (see scipy.sparse.csc_matrix)* Code a function Apply_Sparse_Transform$(R,X)$ that takes an input   * the random transform $W$ as generated by  Generate\_sparse\_transform$(s,r,d)$   * a given data matrix $X \in \mathbb{R}^{n\times d}$the output will be $XW$.*Note* if you have not implemented this efficiently, you will probably run out of memory!  We will test if random projections are able to preserve pairwise distances by applying K-Neighrest Neighbors to projected data.1) [6pts] Code the above two functions (their stub is provided below)2) [1pt] Load the data set X. Then fit, transform and score sklearn's KNeighborsClassifier on this data, where $X = $ {anthracyclineTaxaneChemotherapy, sector.scale}. Below you will find how to load this data.3) [3pts] Repeat the previous step, but first randomly project that data using X -> XW. Repeat this test for different values of the sparsity parameter s and projected dimension parameter r. What can you conclude? *Hint* As a rule of thumb $s = \sqrt{r}$, $s= \log(r)$ or simply $s=20$ often works well.<jupyter_code>import scipy
from sklearn.utils.extmath import safe_sparse_dot   ## <-- I recommend using this function
from sklearn.utils.random import sample_without_replacement  ## <-- I recommend using this function

def GenerateSparseTransform(s,r,d):
    ### TODO ### 
    ##  Implement this function. Make sure that W is a sparse matrix!
    #############
    W = 0
    return W

def ApplySparseTransform(W,X_):
#     W   : Sparse randomly generated matrix of size d by r
#     X_  : Data matrix to be compressed, of size n by d
#    NOTE: The dimensions of W and X_ are such that the product X_*W is defined (which is different that what we used in class)
    ### TODO ### 
    ##  Implement this function. Make sure that W is a sparse matrix!
    #############
    Xtransformed =0
    return Xtransformed<jupyter_output><empty_output><jupyter_text>Load and test easier data set *anthracyclineTaxaneChemotherapy*<jupyter_code>from sklearn.datasets import fetch_openml
chemo = fetch_openml(name='anthracyclineTaxaneChemotherapy')
X = chemo.data
y = chemo.target<jupyter_output><empty_output><jupyter_text>if fetch_openml fails  **ALTERNATIVE HACK for loading the data**  * downloard the data from data set in arff format from: https://www.openml.org/d/1085 * place data in the same folder as this notebook and run the code in the next cell<jupyter_code>## ALTERNATIVE HACK for loading anthracyclineTaxaneChemotherapy ## 
from scipy.io import arff
dataset = arff.loadarff('phpCLGrjq.arff')
import pandas as pd
Xdf = pd.DataFrame(dataset[0])
Xy = Xdf.as_matrix()
n_rows, n_cols = Xy.shape
X = Xy[:,:-1]
X = np.float_(X)
y = Xy[:,-1]
y = (np.int_(y))*2-3
# split test and training. Only use 20% of data for testing because data set is small. 
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.20, random_state=42) 
n, d = X_train.shape
print('{n} training data points and {d} features'.format(n = n,d =d))
# 2) fit, transform and score the knn Classifier
n_neighbors =2 # <-- use this number of neighbours
knn = KNeighborsClassifier(n_neighbors=n_neighbors)

knn.fit(X_train,y_train)
trainscore = knn.score(X_train, y_train)
training_accuracy.append(trainscore)
testscore = knn.score(X_test, y_test)
test_accuracy.append(knn.score(X_test, y_test))
print ("project dim %5d gives: (train, test) =  (%.4f, %.4f)" % (d, trainscore,testscore))
test_accuracy = []
training_accuracy = []
n_neighbors =2  #< -- I recommend 2 neighbors

## Suggested range of projected dimensions:
upperbnd = int(min(10*n,d/2))
minbnd = int(max(n/20,d/2000))
project_dimensions = range(minbnd,upperbnd,int((upperbnd -minbnd)/10))

knn = KNeighborsClassifier(n_neighbors=n_neighbors)
    
for r in project_dimensions:  
    W = GenerateSparseTransform(s =20, r= r,d = d) # function coded above
    Xt_train = ApplySparseTransform(W,X_train)  # function coded above
    Xt_test =  ApplySparseTransform(W,X_test)  # function coded above
    knn.fit(Xt_train,y_train)
    trainscore = knn.score(Xt_train, y_train)
    training_accuracy.append(trainscore)
    testscore = knn.score(Xt_test, y_test)
    test_accuracy.append(knn.score(Xt_test, y_test))
    print ("project dim %5d gives: (train, test) =  (%.4f, %.4f)" % (r, trainscore,testscore))

list_proj_dims = list(project_dimensions)
plt.plot(list_proj_dims,training_accuracy, label='Accuracy of the training set')
plt.plot(list_proj_dims,test_accuracy, label='Accuracy of the test set')
plt.ylabel('Accuracy')
plt.xlabel('Projected Dimension')
plt.legend()
index_max = np.argmax(test_accuracy)
print("Best score was for r =%5d with: (train, test) =  (%.4f, %.4f)"% (list_proj_dims[index_max], training_accuracy[index_max],test_accuracy[index_max]))<jupyter_output><empty_output><jupyter_text>Load and test HARDER data set *sector.scale*  **(only try this data set after successfully testing the anthracyclineTaxaneChemotherapy data set)**<jupyter_code># Download the data set from:
# https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass/sector/sector.scale.bz2
# place data in the same folder as this python notebook
dataname = "sector.scale"  
X, y = get_data(dataname)
n, d = X.shape
print('{n} data points and {d} features'.format(n = n,d =d))
# split test and training 
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33, random_state=42)
n, d = X_train.shape
print('{n} trainig data points and {d} features'.format(n = n,d =d))
### TODO ### 
## repeat the same experiments for this larger data set
## HINT: Only test project dimensions r <= int(min(2*n,d/2))
#############
test_accuracy = []
training_accuracy = []
n_neighbors =1   ## <-- I recommend using this
knn = KNeighborsClassifier(n_neighbors=n_neighbors)
    
for r in project_dimensions:  
    ### TODO ###   
    # 3)    project the data matrix $X \rightarrow XW$ using Gaussian and fit, 
    #      transform and score using knn
    # W = GenerateSparseTransform(???)
    # Xt_train = ApplySparseTransform(W,X_train)
    # Xt_test =  ApplySparseTransform(W,X_test)
    # trainscore =  ??
    # training_accuracy.append(trainscore)
    # testscore = ??
    # test_accuracy.append(testscore)
    #############
    print ("project dim %5d gives: (train, test) =  (%.4f, %.4f)" % (r, trainscore,testscore))

list_proj_dims = list(project_dimensions)
plt.plot(list_proj_dims,training_accuracy, label='Accuracy of the training set')
plt.plot(list_proj_dims,test_accuracy, label='Accuracy of the test set')
plt.ylabel('Accuracy')
plt.xlabel('Projected Dimension')
plt.legend()
index_max = np.argmax(test_accuracy)
print("Best score was for r =%5d with: (train, test) =  (%.4f, %.4f)"% (list_proj_dims[index_max], training_accuracy[index_max],test_accuracy[index_max]))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1264885274469939, 'fraction_numerical': 0.021057217542840546, 'mean_word_length': 4.821217244294167, 'pattern_counts': {'":': 0, '<': 36, '<?xml version=': 0, '>': 31, 'https://': 3, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '176090', 'license': 'MIT', 'n_tokens_mistral': 4847, 'n_tokens_neox': 4561, 'n_words': 1499, 'path': 'pdf/teaching/IA317/Rand_Proj.ipynb', 'repo_name': 'gowerrobert/gowerrobert.github.io', 'size': '13795'}