<jupyter_start><jupyter_text>PS4In this problem set, you will implement multidimensional scaling (MDS) from scratch. You may use standard matrix/vector libraries (e.g. numpy) but you must implement two dimensional MDS itself on your own and not use an existing software package. MDS attempts to find an arrangement of points such that the distances between points match human-judged similarities.  InstructionsRemember to do your problem set in Python 3. Fill in `YOUR CODE HERE`.Make sure: - that all plots are scaled in such a way that you can see what is going on (while still respecting specific plotting instructions) - that the general patterns are fairly represented.- to label all x- and y-axes, and to include a title.<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
# to import the data set
from scipy.io import loadmat<jupyter_output><empty_output><jupyter_text>Import and examine dataWe will be using a data set from <NAME>., <NAME>., & <NAME>. (1993). Predicting Clustering from Semantic Structure. Psychological Science, 4(1), 28-34, via https://faculty.sites.uci.edu/mdlee/similarity-data/. The data set is saved in PS4_dataset.mat, and includes pairwise similarity measures between 21 sports. Make sure that the PS notebook and the data set are in the same directory!As our first step, we will download and examine the data:<jupyter_code>data_set = loadmat('PS4_dataset.mat')
similarity = data_set['similarity']
sport_names = data_set['sport_names']<jupyter_output><empty_output><jupyter_text>As we can see, our data contains information for 21 different sports as listed below:<jupyter_code>print(sport_names)<jupyter_output><empty_output><jupyter_text>We also have a similarity matrix for each sport, which gives us the psychological similarity of that sport with all the other sports in the data:<jupyter_code>#Look at the first similarity matrix, which corresponds to football's similarity with itself and all other sports
print(similarity[0])<jupyter_output><empty_output><jupyter_text>Q1. Visualize similarity [5pts, HELP] Plot the "similarity" measures from the data as a heatmap. Don't forget to:       1)Label the heatmap's rows and columns with the corresponding sport (rotate the x-axis labels by 45 degrees so that the labels are readable)       2)Add a title to your figure (e.g. similarity)       3)Add a colorbar. Limit the colobar values between 0 and 1.       4)Use default colormap       5)Upload figure PS4_Q1.png to gradescope.Hint - look up matplotlib's imshow.<jupyter_code>#YOUR CODE HERE

figure.savefig('PS4_Q1.png')<jupyter_output><empty_output><jupyter_text>Q2. Distance [2 pts, SOLO]To implement MDS, we need a measure of psychological **distance**. The dataset includes measures of similarity, not distance. Here we will use *d = 1-s* as a  method to transform similarity to distance.  Write a function that converts all similarity measures in the dataset into distances, using the above provided transformation method. Function should return the output called distance (Hint: this variable will be used as an input in some of the functions you'll write in the following questions).Plot a scatterplot of the dataset's distances (x axis) against their similarity (y axis). Label your figure.Upload figure PS4_Q2.png to gradescope.<jupyter_code>#YOUR CODE HERE


figure.savefig('PS4_Q2.png')<jupyter_output><empty_output><jupyter_text>Q3. Stress [5 pts, SOLO] To perform MDS, we will try to find, for each sport i, a position $p_i=(x_i,y_i)$ in the 2d space that captures the participants’ similarities. To do so, we will build an algorithm that minimizes the stress. We’ll define stress slightly differently than in class- the squared difference between psychological distance $\psi_{ij}= (1-s_{ij})$ and the MDS distance in 2D space: $$ \mathrm{Stress \ S} = \sum_{i>j} (\psi_{ij} - dist(p_i,p_j))^2$$Where $\psi$ is the psychological distance between sport i and sport j that was reported by subjects, and *dist(pi,pj)* corresponds to the **Euclidean distance**:$\sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}$ Write a function that computes the Euclidean Distance between two points $p_1$ and $p2$. Then, write a function that takes a $(n,2)$ (n=number of sports) matrix of $(x,y)$ positions for each sport, and computes the stress based on the equation above, using your Euclidean Distance function. Copy the StressCalc function into gradescope.<jupyter_code>def EuclideanDistance(p1,p2):
    ''' Takes positions defined by p1 and p2, and returns a euclidean distance value (single number).
    Implement EQ equation provided in the question. Hint: if p1=p2, the function should return the value of 0'''
    
    
    
    
    

    #YOUR CODE HERE
    return ED
def StressCalc(positions, distance):
    ''' Takes positions (n,2) and (n,n) matrix of distance measures
    (You will use the distance matrix from Q2). 
    Uses these distances and the EuclideanDistance function above which computes ED based on positions
    to calculate the Stress between psychological and ED distances, according to the provided formula.''' 
    
    #YOUR CODE HERE
    
    
    
    
    
    
    return stress
    
    
# Test case! 
'''
Test case for StressCalc: create an array of positions, where each entry is 1.
Use this positions matrix and distance matrix from Q2 to call StressCalc function
'''

positions = np.ones((len(similarity),2))
print(['Stress value should be 111.57. Output stress value is: ' + str(StressCalc(positions,distance))])<jupyter_output><empty_output><jupyter_text>Q4. Gradient [10 pts, HELP]To minimize the stress, we will numerically compute the gradient using a multidimensional version of the simple rule for derivatives:$$ \frac{df}{dp}(p) = \frac{f(p+\delta)-f(p-\delta)}{2\delta}$$where $\delta$ takes on a small value, and $f$ is the stress function you wrote in the previous question. To compute the gradient, we will compute this approximate derivative with respect to each coordinate of each point.Write a function that takes an n-by-2 matrix (n=number of sports) of (x,y) positions for each sport and computes the gradient (i.e. applies the numerical rule above to each coordinate location). This should return an n-by-2 gradient matrix.Use $\delta$ = 0.01Copy your code into gradescope.<jupyter_code>delta = .01
positions = np.random.rand(len(similarity),2)

#YOUR CODE HERE<jupyter_output><empty_output><jupyter_text>Q5.1 MDS [10 pts, HELP]Write the MDS code: the code that follows a gradient in order to find positions that minimize the stress. Start from a random position, and be sure to take small steps in the direction of the gradient (e.g.  α*gradient, with step size  α=0.01), to find a set of positions that minimizes the stress. Use 100 steps of gradient descent.Copy your code in gradescope.<jupyter_code>#YOUR CODE HERE<jupyter_output><empty_output><jupyter_text>Q5.2 [5 pts, SOLO]Plot the names of sports at the resulting coordinates.Hint: look up axis.text for plotting the sports names.Upload PS4_Q5_2.png in gradescope.<jupyter_code>#YOUR CODE HERE

figure.savefig('PS4_Q5_2.png')<jupyter_output><empty_output><jupyter_text>Q5.3 [5 pts, SOLO]Plot the stress as a function of step number (x axis = step number, y axis= stress).Upload PS4_Q5_3 in gradescope.<jupyter_code>#YOUR CODE HERE

figure.savefig('PS4_Q5_3.png')<jupyter_output><empty_output><jupyter_text>Q6. Validation [5pts, SOLO] Make a scatter plot of the distances obtained by running your MDS function vs. people's reported distances *d=(1-s)*. Upload PS4_Q6.png to gradescope. Briefly describe what a good and bad MDS-psychological distance relationship would look like, and whether yours is good or bad. Enter your response in gradescope.<jupyter_code>#YOUR CODE HERE

figure.savefig('PS4_Q6.png')<jupyter_output><empty_output><jupyter_text>Q7.1 Iterating MDS [3pts, SOLO]Run your MDS code 9 times, and plot the corresponding final positions in a figure with subplots in a 3x3 grid. Indicate the code iteration number in each subplot title. Scale the figure size using figsize=(15,15). Are they all the same or not? Why? Enter your response in gradescope.Upload PS4_Q7_1.png in gradescope.<jupyter_code>#YOUR CODE HERE

figure.savefig('PS4_Q7_1.png')<jupyter_output><empty_output><jupyter_text>Q7.2 Best representation [3pts, SOLO]In another figure, plot the final stress value as a function of the MDS iteration (9) in the previous question. If you wanted to pick the best final representation based on this plot, how would you do it? What criteria would you use? Which iteration is your best?Enter your answer in gradescope.Upload PS4_Q7_2.png.<jupyter_code>#YOUR CODE HERE

figure.savefig('PS4_Q7_2.png')<jupyter_output><empty_output><jupyter_text>Q7.3 [4pts, SOLO]Do your best results agree with your intuitions about how this domain might be organized? Why or why not? Answer in 2-3 sentences. Enter your response in gradescope.  Q8 [5pts, SOLO]Run MDS 2 times, with 2 different step sizes (α=.02 and  α=.05). Plot Stress over time for each run in the same plot. Don't forget to add a legend,labeling which MDS step size the line refers to, in addition to the usual axis labels and title. What happens if you use a bigger step in your MDS? Why?Enter your answer in gradescope.Upload PS4_Q8.png.<jupyter_code>#YOUR CODE HERE

figure.savefig('PS4_Q8.png')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07656935087156454, 'fraction_numerical': 0.01700352903432788, 'mean_word_length': 4.968091895341416, 'pattern_counts': {'":': 0, '<': 64, '<?xml version=': 0, '>': 65, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '15', 'dir': 'jupyter-structured-clean-dedup', 'id': '554197', 'license': 'BSD-3-Clause', 'n_tokens_mistral': 2871, 'n_tokens_neox': 2691, 'n_words': 1202, 'path': 'PS4/PS4.ipynb', 'repo_name': 'smitchaute/COGSCI-C131-PSYCH-123-FA20', 'size': '9373'}