\documentclass[12pt]{article}

\setlength{\textwidth}{6.5in}
 \setlength{\textheight}{8.5in}
\setlength{\topmargin}{0.0in}
\setlength{\oddsidemargin}{0.0in}


\usepackage{graphicx}
\usepackage{curves}

\usepackage{url}


\begin{document}

\large

Kruskal, J. B. (1964). Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. \emph{Psychometrika}, \emph{29}, 1--27; Nonmetric multidimensional scaling: A numerical method. \emph{29}, 115--129. (5773 citations in Google Scholar as of 4/1/2016)


\bigskip

The now familiar topic of nonmetric multidimensional scaling (NMDS) was introduced into the quantitative psychology literature by the publication of two highly-cited companion papers from Roger Shepard:

\smallskip

Shepard, R. N. (1962). The analysis of proximities: Multidimensional scaling with an unknown distance function. I. II. \emph{Psychometrika}, \emph{27}, 125--140; 219---246. (2309 citations in Google Scholar as of 4/1/2016)

\smallskip

\noindent These two papers discuss the task of embedding a set of $n$ objects, say, $\{O_{1}, \ldots, O_{n}\}$, into a Euclidean space of $K$ dimensions based on a given numerical proximity measure, $p_{ij}$, defined for each object pair, $O_{i}$ and $O_{j}$.  It will be assumed for convenience that these proximities are keyed as dissimilarities so larger values for $p_{ij}$ reflect objects that are more dissimilar.  The embedding was to be done in such a way that: (1) the rank-ordering of the proximities would reflect as closely as possible the rank-ordering of the induced (Euclidean) distances in the $K$-dimensional space, and (2), that the number of dimensions used (that is, the value of $K$), would be as small as possible.  The term ``nonmetric'' arises from a reliance on only the rank-ordering of the proximities and not on their actual (``metric'') numerical values.

\smallskip

To implement his ideas for nonmetric multidimensional scaling, Shepard developed a FORTRAN program to carry out an iterative process of embedding $n$ objects into a space of minimum dimensionality that would have a satisfactory rank-order correspondence between the proximities and the induced Euclidean distances.  In Shepard's hands, some dramatic data analysis examples were given in the \emph{Psychometrika} paper labeled as II (for example, the famous two-dimensional color circle example based on data from Ekman).  What was less clear from these two Shepard papers was whether a naive practitioner could could get the same type of results using Shapard's program, which apparently was guided by some trial-and-error adjustments during the iterative process.  This is the point where Roger Shepard's Bell Labs colleague, Joe Kruskal, enters the picture, and which led to the two highly-cited \emph{Psychometrika} papers that is the main purpose of this specific note.  Shepard himself notes the role of Kruskal in comments he made on the occasion of his two \emph{Psychometika} papers being named ``Citation Classics'' (May 31, 1979):

\smallskip

\normalsize


After a period of trial-and-error adjustment of
the parameters of the iterative process,
success came with dramatic suddenness on
March 17, 1961. According to the computer
log, it was at precisely 2.33 p.m.\ EST on that
day that the iterative process first converged to
a stationary configuration, revealing a
remarkably exact recovery of an underlying
test configuration. The excitement of that
moment was rivaled only by the birth of my
daughter on the very next day. Since then my
daughter has developed into a fine young
woman; and, thanks in part to the subsequent
contributions of my mathematical colleague
Joseph Kruskal, nonmetric multidimensional
scaling is now finding wide application
throughout the cognitive, behavioral, and
biomedical sciences.


\large

\smallskip

The genius of the two Kruskal papers is that they took Shepard's intuitive ideas and turned them into a reliable means of carrying out a nonmetric multidimensional scaling.  Specifically, Kruskal began by defining and explicit loss function to minimize, called stress; he then proposed a numerical strategy for its optimization through the ``method of steepest descent.''  To effect a sole reliance on the rank-order of the proximities, ``monotone regression'' steps were interspersed within the steepest descent mechanism based on a separately important ``pool adjacent violators algorithm'' (PAVA).

\smallskip

To define the stress of a given fixed configuration, suppose the $n$ objects are embedded in a $K$-dimensional space with an interpoint distance, $d_{ij}$, between objects $O_{i}$ and $O_{j}$.  Stress, $S$, is then given by 
\[  \sqrt{\frac{\sum_{i < j} (d_{ij} - \hat{d_{ij}})^{2}}{\sum_{i < j} d_{ij}^{2}}}  \] 
\noindent here, the $\hat{d_{ij}}$ are called \emph{disparities} and are those numbers that minimize $S$ subject to the constraint that the $\hat{d_{ij}}$ have the same rank-order as the $p_{ij}$: $\hat{d_{ij}}  \le \hat{d_{i'j'}}$ whenever $p_{ij} \le p_{i'j'}$.  This later minimization of $S$ is the monotone regression step that is carried out using PAVA.  At this point, the iterative method of steepest descent ``is used to improve $S$, which then leads to another monotone regression step, and so on until convergence (that is, until $S$ can no longer be improved).

\smallskip

A prime contributions of the Kruskal papers is that they came with a practical way of carrying out a nonmetric multidimensional scaling through a companion FORTRAN program \verb+mdscal.f+.  This program as well as its various Bell Labs successors, such as KYST2a, are still available on various \verb+netlib.org+ sites.  An additional advantage of using one of these routines was the availability of various graphics and plots, such as what has become called the ``Shepard diagram.''  The latter is a scatterplot of final interpoint distances on the $y$-axis and dissimilarities on the $x$-axis.  The disparities, $\hat{d_{ij}}$, are plotted as ``predicted values'' from the monotone regression, tracing out the monotone regression line that either stays at the same horizontal level or increases moving toward that more positive dissimilarity values along the $x$-axis.  The degree to which the values cluster compactly around the monotone regression line, gives an indication of how well the scaling reflects the original dissimilarities.

\end{document} 