COGSCI 131 – Assignment 5 DUE: March 5th at class start
In 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. To do this, we will minimize the stress, which is the squared difference between psychological and MDS distances:
Stress S =
where ψij is the psychological distance between stimulus i and j that was reported by subjects and pi and pj are the positions of stimulus i and j in MDS space (here, ). Thus, pi and pj are vectors of coordinates (x-locations and y-locations). To minimize the stress,we will write code that will numerically compute the gradient using a multidimensional version of the simple rule for derivatives,
where is small. We’ll be using a version of this rule to compute the derivative of stress with respect to each coordinate of each pi. It will be convenient to organize positions p into a matrix giving the x- and y-locations in each column, and an item in each row. When you deal with this “matrix” you will have to remember that it’s really a vector that you’ve put this shape (to make computing, plotting easier).
1. [5pts, SOLO] The dataset1 provides similarities, not distances. Write down three ways you could convert a similarity to a distance ψij and choose one to use in the code. Briefly explain why you chose it over the others.
2. [5pts, SOLO] Write a function that takes a vector/matrix of positions for each item and computes the stress.
3. [5pts, HELP] Write down a function that takes a vector/matrix of positions and computes the gradient (e.g. applies the above numerical method of df/dp to each coordinate location).
4. [20pts, HELP] Write the code that follows a gradient in order to find positions that minimize the stress – be sure to take small steps in the direction of the gradient (e.g. 0.01*gradient). Plot the sport names at the resulting coordinates. Do the results agree with your intuitions about how this domain might be organized? Why or why not?
5. [5pts, SOLO] Make a scatter plot of the the pairwise distances MDS found vs. people’s reported distances. Briefly describe what good and bad plots would look like and whether yours is good or bad.
6. [5pts, SOLO] Plot the stress over iterations of your MDS. How should you use this plot in order to figure out how many iterations are needed?
1 From Romney, A. K., Brewer, D. D., & Batchelder, W. H. (1993). Predicting Clustering from Semantic Structure. Psychological Science, 4(1), 28-34, via https://faculty.sites.uci.edu/mdlee/similarity-data/, which has many other examples to play with.
7. [5pts, SOLO] Run the MDS code you wrote 10 times and show small plots, starting from random initial positions. Are they all the same or not? Why?
8. [5pts, SOLO] If you wanted to find one “best” answer but had run MDS 10 times, how would you pick the best? Why? Show a plot of the best and any code you used to find it.