
## 2. A Graphical View Of Similarity

Before we can construct an embedding algorithm for multi-modal data, we must first establish the form of side-information that will drive the algorithm, i.e., the similarity measurements that will be collected from human labelers. There is an extensive body of work on the topic of constructing a geometric representation of data to fit perceptual similarity measurements. Primarily, this work falls under the umbrella of multi-dimensional scaling (MDS), in which perceptual similarity is modeled by numerical responses corresponding to the perceived "distance" between a pair of items, *e.g.*, on a similarity scale of 1–10. (See Cox and Cox (1994); Borg and Groenen (2005) for comprehensive overviews of MDS techniques.)
Because "distances" supplied by test subjects may not satisfy metric properties - in particular, they may not correspond to Euclidean distances - alternative *non-metric* MDS (NMDS) techniques have been proposed (Kruskal, 1964). Unlike classical or metric MDS techniques, which seek to preserve quantitative distances, NDMS seeks an embedding in which the rank-ordering of distances is preserved.

Since NMDS only needs the rank-ordering of distances, and not the distances themselves, the task of collecting similarity measurements can be simplifed by asking test subjects to *order pairs of* points by similarity:
"Are i and j more similar than k and ℓ?"
or, as a special case, the "triadic comparison"
"Is i more similar to j or ℓ?"
Based on this kind of *relative comparison* data, the embedding problem can be formulated as follows. Given is a set of objects X , and a set of similarity measurements C = {(i, j, k, ℓ)**} ⊆ X** 4, where a tuple (**i, j, k, ℓ**) is interpreted as "i and j are more similar than k and ℓ." (This formulation subsumes the triadic comparisons model when i = k.) The goal is to find an embedding function g : X → R
dsuch that

$$\forall(i,j,k,\ell)\in{\mathcal{C}}:\ \|g(i)-g(j)\|^{2}+1<\|g(k)-g(\ell)\|^{2}.$$
2. (1)
The unit margin is forced between the constrained distances for numerical stability.

Agarwal et al. (2007) work with this kind of relative comparison data and describe a generalized NMDS algorithm (GNMDS), which formulates the embedding problem as a semi-definite program.

Schultz and Joachims (2004) derive a similar algorithm which solves a quadratic program to learn a linear, axis-aligned transformation of data to fit relative comparisons.

Previous work on relative comparison data often treats each measurement (i, j, k, ℓ) ∈ C as effectively independent (Schultz and Joachims, 2004; Agarwal et al., 2007). However, due to their semantic interpretation as encoding pairwise similarity comparisons, and the fact that a pair (**i, j**)
may participate in several comparisons with other pairs, there may be some *global* structure to C
which these previous methods are unable to exploit.

In Section 2.1, we develop a graphical framework to infer and interpret the global structure exhibited by the constraints of the embedding problem. Graph-theoretic algorithms presented in Section 2.2 then exploit this representation to filter this collection of noisy similarity measurements for consistency and redundancy. The final, reduced set of relative comparison constraints defines a partial order, making for a more robust and efficient embedding problem.