\documentclass[twoside,11pt]{article}
\usepackage{./jmlr2e}
\usepackage[T1]{fontenc}
\usepackage{epsfig}
\usepackage{textcomp}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amscd}
\usepackage{graphicx}
%\usepackage{times}

\newcommand{\mpdir}{./figures}

\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\Sd}{\ensuremath{\mathbb{S}_D}}

\jmlrheading{5}{2004}{801-818}{12/03}{7/04}{Julian Laub and Klaus-Robert Müller}
\ShortHeadings{Feature Discovery in Non-Metric Pairwise Data}{Laub and Müller}
\firstpageno{801}

\begin{document}

\title{Feature Discovery in Non-Metric Pairwise Data}

\author{\name Julian Laub \email julian.laub@first.fhg.de \\
\addr Fraunhofer FIRST.IDA\\
 Kekulestrasse 7\\
12489 Berlin, Germany
\AND
\name Klaus-Robert Müller \email klaus@first.fhg.de \\
\addr Fraunhofer FIRST.IDA\\
 Kekulestrasse 7\\
12489 Berlin, Germany, and\\
\addr University of Potsdam, Department of Computer Science\\
August-Bebel-Strasse 89\\
14482 Potsdam, Germany}

\editor{Isabelle Guyon}

\maketitle

\begin{abstract}%
Pairwise proximity data, given as similarity or dissimilarity matrix, can violate metricity. This occurs either due to
noise, fallible estimates, or due to intrinsic non-metric features
such as they arise from human judgments. So far the problem of non-metric
pairwise data has been tackled by essentially omitting the negative eigenvalues
or shifting the spectrum of the associated (pseu\-\mbox{do-)}\-covariance
matrix for a subsequent embedding. However, little attention
has been paid to the negative part of the spectrum itself. In
particular no answer was given to whether the directions associated
to the negative eigenvalues would at all code variance other than
noise related. We show by a simple, \emph{exploratory} analysis that the negative eigenvalues \emph{can} code for
relevant structure in the data, thus leading to the discovery of new
features, which were lost by conventional data analysis techniques.
The information hidden in the negative eigenvalue part of the
spectrum is illustrated and discussed for three data sets, namely USPS
handwritten digits, text-mining and  data from cognitive psychology. \\
\end{abstract}

\begin{keywords}
Feature discovery, exploratory data analysis, embedding, non-metric, pairwise data, unsupervised learning
\end{keywords}
\section{Introduction}
A large class of data analysis algorithms is based on a vectorial representation of the data. However, for major fields such as bioinformatics \citep[e.g.][]{altschul97gapped}, image analysis \citep{hofmann98unsupervised,jacobs00classification} or cognitive psychology \citep{gati82rep,goldstone91rel}, the data is not available as points lying in some vector space but solely arises as scores of pairwise comparisons, typically measuring similarity or dissimilarity between the data points. A global overview of pairwise proximity data can be found in \citet{everitt97prox}. Table~\ref{simpex} gives a simple instance of pairwise data obtained from human similarity judgments of Morse code \citep{everitt97prox}.

\begin{table}[h!]
\label{simpex}
\centering\begin{tabular}{c|ccccc}
&1&2&3&4&5\\
\hline
1&84&63&13&8&10\\
2&62&89&54&20&5\\
3&18&64&86&31&23\\
4&5&26&44&89&42\\
5&14&10&30&69&90
\end{tabular}
\caption{Test subjects are asked to judge the pairwise similarity of auditory Morse code (long and short tones). Here we show the similarity matrix for the first five digits. The entries correspond to the percentage of a large number of observers who responded `same' to the row signal followed by the column signal. (Excerpt from Table~1.3 given in \citet{everitt97prox}). Note that this proximity matrix is \emph{asymmetric}.}
\end{table}

These pairwise proximities, or ``data points'', are  in no natural way related to the common  viewpoint of objects lying in some ``well behaved'' space like a vector space which  always is---albeit possibly high dimensional---a very restrictive structure. 

There is a class of algorithms specifically designed for pairwise data, e.g. KNN, pairwise $k$-means \citep{DudHarSto01}. Otherwise the pairwise data is first "embedded" into a vector space in order to make it available for the numerous algorithms based on vectorial input \citep{cox94multidimensional}. Pairwise data satisfying restrictive conditions can be embedded distortionless with respect to metricity into a Euclidean space \citep{roth02clust}.

Often pairwise data is non-metric and the dissimilarity matrix does not satisfy the mathematical requirements of a metric function. Metric violations preclude the use of well established machine learning methods, which typically have been formulated for metric data only, and more precisely, for vectorial data, thus limiting the interest of raw pairwise data. Non-metric pairwise data can not be embedded distortionless into a (Euclidean) vector space.  So, in general, embedding  into a Euclidean space (and often subsequent dimension reduction) amounts to distorting pairwise data to enforce Euclidean metricity. This procedure is exemplified by Multi Dimensional Scaling \citep{cox94multidimensional}. Other popular methods are e.g. \emph{Locally Linear Embedding} \citep{lle} and \emph{Isomap} \citep{isomap}.

However, little is known about the real information loss incurred by enforcing metricity, when non-metric data is forcefully embedded into a vector space on the assumption that non-metricity be a mere artifact of noise. 
This assumption certainly holds for many cases, especially
when the pairwise comparison is the output of some algorithm tuned to
be metric but relying on some random initialization. It does not hold for pairwise data which
is inherently non-metric, e.g. for human similarity judgments, summarizing
geometrical (metric) and categorial thinking (possibly non-metric).

Technically, non-metricity translates into indefinite
similarity matrices, also called ``pseudo-covariance'' matrices \citep{torgerson58scaling}, a
fact, which imposes severe constraints on the data analysis
procedures. Typical approaches to tackle these problems involve omitting altogether the negative eigenvalues like in classical scaling \citep{young38discussion} or shifting the spectrum \citep{roth02goi} for subsequent (kernel-)PCA \citep{sch98nonlinear}.
 
The central and so far unanswered question is therefore: \emph{Does the negative
part of the spectrum of a similarity matrix code anything useful other
than noise?}

This work will contribute by showing that the negative eigenvalues
\emph{can} code for relevant structure in the data. The
\emph{exploratory} technique outlined below can lead to the discovery
of \emph{systematically new} features, which were so far lost or have gone unnoticed by existing algorithms. This is discussed for three illustrative examples after a brief theoretic discussion of the issue of
negative eigenvalues and a simple explanation of \emph{how} negative spectra
can code specific information.

\section{Embedding of Non-Metric Data}
In this section we will describe the issue of embedding pairwise proximity data into a vector space. Embedding pairwise data corresponds to finding points in a vector space, such that their mutual distance is as close as possible to the initial dissimilarity matrix with respect to some cost function.  Embedding yields points in a vector space, thus making the data available to the numerous machine learning techniques which require vectorial input. Embedding also allows visualization after dimension reduction.  

Let $D=(D_{ij})$ be an $n\times n$ dissimilarity matrix. We want to find $n$ vectors $x_i$ in a $p$-dimensional vector space such that the distance between $x_i$ and $x_j$ is close to the dissimilarity $D_{ij}$ with respect to some cost function measuring the distortion incurred by the embedding procedure. 

Let $X$ be the matrix whose column are given by the vectors $x_i$. The matrix defined by $\frac{1}{n}XX^\top$ is called the \emph{covariance} matrix and is positive semi-definite, i.e., all its eigenvalues $\lambda_i$ are positive or zero ($\lambda_i\geq 0$). The covariance matrix plays an important role in spectral methods like (ker\-\mbox{nel-)}\-PCA. The directions corresponding to the leading eigenvalues describe the directions which capture large variance in the data. Thus we expect to find interesting features there. 

\subsection{Mathematical Statement of the Embedding Problem}\label{embprob}
We will briefly state the mathematical formulation of the embedding problem and give the necessary and sufficient condition for a Euclidean embedding.

A dissimilarity matrix $D$ will be called \emph{metric} if there exists a metric function $d$ such that $D_{ij}=d(\cdot,\cdot)$. In other words, $D$ is positive and symmetric, its elements are $0$ if and only if they are on the diagonal,\footnote{We reasonably suppose that there are no two identical data points with different labels in the data set.} and they satisfy the triangle inequality.
$D=(D_{ij})$ will be called squared-Euclidean if the metric function $d$ derives from the Euclidean norm $l_2$.

% \subsection{Necessary and sufficent condition for a Euclidean embedding.}

Let $C=-\frac{1}{2}QDQ$ where $Q=I-\frac{1}{n}ee'$. $Q$ is the projection
matrix onto the orthogonal complement of $e=(1,1,\ldots\,1)^\top$. The operation $D\rightarrow QDQ$ corresponds to the \emph{centralizing} operation. The meaning of $C$ will become clear subsequently.

We have the following important theorem \citep{torgerson58scaling,young38discussion}:
\begin{theorem}\label{mainthm}
$D$ is squared-Euclidean iff $C$ is positive semi-definite.
\end{theorem}
In other words, the pairwise dissimilarities given by $D$ can be embedded into a Euclidean vector space if and only if the associated matrix $C$ is positive semi-definite.

\subsection{Embedding when $D$ is Squared-Euclidean}
When $D$ is squared-Euclidean, $C$ is semi-definite positive and can readily be interpreted as covariance matrix (via simple algebra). The embedded vectors can be recovered by usual kernel-PCA \citep{sch98nonlinear,cox94multidimensional}:
 
\begin{equation*}
\begin{split}
&D \xrightarrow{\text{\phantom{xxx}$C=-1/2 QDQ$\phantom{xxx}}} C\text{ with $n$ positive eigenvalues }\\
&C \xrightarrow{\text{\phantom{xxx}spectral decomposition\phantom{xxx}}} V \Lambda V^\top\\
&X_K = |\Lambda_K|^{1/2} V_K^\top,
\end{split}
\end{equation*}
where $V = (v_1,\ldots,v_n)$ with eigenvectors $v_i$'s and
$\Lambda = {\rm diag}(\lambda_1,\ldots,\lambda_n)$ with
eigenvalues $\lambda_1 \geq \cdots \geq \lambda_{n} \geq 0$. $K$ is the subspace of chosen directions $v_i$.  
The columns of $X_K$ contain the vectors $x_i$ in $p$-dimensional subspace $K$, where $V_K$ is the column-matrix of the selected eigenvectors and 
$\Lambda_K$ the diagonal matrix of the corresponding eigenvectors.
 
If $K=\{v_1\ldots\, v_p\}$ the distances between these vectors differ the least from the distances $D$ with respect to the quadratic approximation error. For $p=n-1$ the mutual distances coincide with $D$, i.e. $D_{ij}=||x_i-x_j||^2$. In other words: \emph{there is a direct algebraic transformation between $D$ and the set of $x_i$'s}.

\begin{figure}[!ht]
\centering\includegraphics[width=11pc]{\mpdir/spectra/spectra.3}\hfil\includegraphics[width=11pc]{\mpdir/spectra/spectra.1}\hfil\includegraphics[width=11pc]{\mpdir/spectra/spectra.2}
\caption{Examples of spectra of $C$ for a squared-Euclidean dissimilarity (left) and  non squared-Euclidean dissimilarity matrices. The eigenvalues are plotted against rank order.}\label{distfig}
\end{figure}

\subsection{Embedding for General $D$'s}
For non squared-Euclidean dissimilarity matrices $D$ the associated $C$ is not positive semi-definite and is not a covariance matrix. In this case we will call it \emph{pseudo-covariance} matrix. Figure~\ref{distfig} shows an instance of a spectrum associated to a positive semi-definite $C$ (left) and two instances of negative
spectra: in the middle, a spectrum associated to a pairwise dissimilarity which
essentially is metric but corrupted by noise which translates into a spectrum with only a few negative eigenvalues of small magnitude. On the right, a spectrum with negative eigenvalues large in magnitude associated to intrinsic non-metricity.

In order to study the possible loss incurred by omitting the negative
part of the spectrum we propose the following simple algorithm, which
allows to specifically visualize the information coded by the negative
eigenvalues. %It essentially relies upon the embedding of non-metric pairwise data into a pseudo-Euclidean space (see Section~\ref{issueinfloss}).


\paragraph{Algorithm.}\label{mainalg}
Start with some symmetric dissimilarity $D$ or similarity $S$. If non-symmetric cases the pairwise proximity matrix must first be symmetrized. Furthermore, when the proximity data are similarities, a problem specific dissimilarity is computed. $D$ typically is related to $S$ via, e.g., $D_{ij}=1-S_{ij}$ or $D_{ij}=S_{ii}+S_{jj}-2S_{ij}$. Recall that $Q=I-\frac{1}{n}ee'$ with $e=(1,1,\ldots\,1)^\top$. $C$ denotes the pseudo-covariance matrix.
\begin{equation*}
\begin{split}
&D \xrightarrow{\text{\phantom{xxx}$C=-1/2 QDQ$\phantom{xxx}}} C\text{ with $p$ positive and $q$ negative eigenvalues }\\
&C \xrightarrow{\text{\phantom{xxx}spectral decomposition\phantom{xxx}}} V \Lambda V^\top=V|\Lambda|^\frac{1}{2}M|\Lambda|^\frac{1}{2}V^\top\\
&X_K = |\Lambda_K|^{1/2} V_K^\top,
\end{split}
\end{equation*}
where $M$ is the block matrix consisting of the blocks $I_{p\times p}$, $-I_{q\times q}$ and $0_{k\times k}$ (with $k=n-p-q$).

The columns of $X_K$ contain the 
vectors $x_i$ in the $p$-dimensional subspace $K$. At this point $K$ can be very general. However, as for PCA, we will find it sensible to choose a few leading  eigendirections \emph{which can also include eigendirections associated to the negative part of the spectrum}. 

\paragraph{Visualization.} Retaining only the first two coordinates ($K=\{v_1, v_2\}$) of the obtained vectors corresponds to a projection onto the first two leading eigendirections. Retaining the last two ($K=\{v_{n-1}, v_{n}\}$) is a projection onto the last two eigendirections: \emph{This corresponds to a projection onto directions related to the metric violations of $C$}

This simple algorithm\footnote{A Matlab implementation can be found under \texttt{http://}\texttt{ida.}\texttt{first.fraunhofer.de/\~{}jlaub/}.} is very akin to the well known PCA algorithm except that it does not require the spectrum to be positive.\\

To finish this short overview about embedding pairwise data, it is important to stress the fact that in general metricity is not enough for pairwise data to be loss-free embeddable into a Euclidean vector space. Pairwise data may be metric, yet have an associated spectrum with negative eigenvalues. The interesting case, however, is given for the Euclidean metric since Theorem~\ref{mainthm} establishes a very simple relationship between the requirements on the dissimilarity matrix and its loss-free embeddability into a Euclidean vector space. 


\subsection{Issue of Information Loss}\label{issueinfloss}
Classical approaches to the embedding into a Euclidean vector space usually involve techniques
like multi-dimensional scaling \citep{cox94multidimensional}. In its simplest
version, classical scaling, MDS proceeds as the algorithm in Section~\ref{embprob}.
However $\Lambda_K^{1/2} $ is only defined for $K\subset \{v_1\ldots\, v_p\}$ with $p \leq t$ where $t$ is
the number of positives eigenvalues. The requirement $p \leq t$ leads
to a cut-off of the negative eigenvalues. Another variant of MDS is called \emph{non-metric} MDS and treats ordinal-scale data, where the projections only try to preserve the rank order between the distances, not their absolute value \citep{krus64,shep62}. It is important to notice here that in our work non-metricity refers to the violations of metric requirements and the subsequent impossibility of a loss-free embedding into a Euclidean vector space. Non-metric MDS does not discover the information coded specifically by metric violations. 

Recently \emph{Constant
 Shift Embedding} was introduced which guarantees distortionless
embedding of non-metric pairwise data w.r.t. cluster assignment in
the case of a shift invariant cluster cost function \citep{roth02clust,roth02goi}. However, in practical
applications, the need for dimension reduction to speed up
optimization and robustify solutions, effectively results in retaining
only the leading eigendirections and cutting off large parts of the
spectrum. For other cases than noise
corrupted non-metric pairwise data (Figure~\ref{distfig}, middle) it is an open question whether the
removal of negative eigenvalues leads to an information loss.

The above methods, unlike ours, do not permit to specifically study the information coded by non-metricity. 

\section{Interpretation and Modeling of Negative Spectra}
In this section we will discuss the issue of information loss raised by the preceding considerations. We will first show by simple from-scratch constructions how negative spectra can occur. Further understanding will be gained by interpretation of the negative eigenspaces. In particular, a model is presented that can explain negative spectra in the case of human similarity judgments in cognitive psychology. A simple toy illustration will conclude this section.

\subsection{Constructing Negative Spectra} 
Let us first introduce two simple constructions of non-metric
pairwise data sets whose non-metric part codes for specific
information. These constructions typically come about in situations involving penalization and/or
competition of dissimilarity measures by subtraction or division:
\begin{equation}\label{simplemodel}
D_{ij}=(D_1 - D_2)_{ij} \quad \mbox{or} \quad D_{ij}=\frac{(D_1)_{ij}}{(D_2)_{ij}},
\end{equation}
with the assumption that $(D_2)_{ij}\neq 0\; \forall
i,j=1,2\ldots\,n$ in the latter case. See Figure~\ref{penalization} for a schematic illustration. The structure of the penalized cells is reflected in non-metricity. Such similarity scores occur in various image
matching algorithms or in text mining via e.g. the \emph{min-max}
dis/similarity \citep{ban02cli,dag95con}, but also in alignment algorithms from e.g. bioinformatics.

\begin{figure}[!ht]
\begin{equation*}
\begin{split}
D_1&=
\begin{pmatrix}
\mbox{\includegraphics{\mpdir/block/block.1}}
\end{pmatrix}
\text{\quad and\quad}
D_2=
\begin{pmatrix}
\mbox{\includegraphics{\mpdir/block/block.2}}
\end{pmatrix}\\
D&=
\begin{pmatrix}
\mbox{\includegraphics{\mpdir/block/block.3}}
\end{pmatrix}
\;\xrightarrow{\text{\phantom{x}snapshot\phantom{x}}}
\begin{matrix}
\phantom{x}\\
\mbox{\includegraphics{\mpdir/block/block.4}}\\
\text{Penalized dissimilarities}\\
\end{matrix}
\end{split}
\end{equation*}
\caption{Principle of penalization: the penalized cells can form a structure on their own, which is reflected in non-metricity. The snapshot shows the alternate structure of the penalized entries (small circles).}
\label{penalization}
\end{figure}

\subsection{Interpreting Negative Eigenspaces}
For a positive semi-definite $C$ the projections along the leading eigendirections can readily be interpreted as projections along the axis of high variances of the data. For pseudo-covariance matrices this still holds up to a scaling factor when shifting the spectrum so as to assure positive semi-definiteness.

For projections onto the negative eigendirections the interpretation is not so straightforward since there is no clear intuition on what ``negative variance'' represents.  However the above presented algorithm relies on a pseudo-Euclidean-style decomposition of the embedding space. The pseudo-Euclidean space effectively amounts to two Euclidean spaces one of which has a positive semi-definite inner product and the other a negative semi-definite inner product. 
An interesting interpretation of the distances in a squared-Euclidean space is that they can be looked at as a difference of squared-Euclidean distances from the ``positive'' and the ``negative'' space, by the decomposition $\R^{(p,q)}=\R^p+i\R^q$, so that $D_{ij}=D_{ij}^{(\R^p)}-D_{ij}^{(\R^q)}$, where the $D_{ij}$ are squared-Euclidean. 
This is the rationale behind the first construction of a non-metric $D$ via  $D_{ij}=(D_1 - D_2)_{ij}$.

The power of this decomposition resides in the fact that the negative eigenvalues now admit the natural interpretation of variances of the data projected onto directions in $\R^q$. Thus the variance along $v_n$ is $\sqrt{|\lambda_n|}$, the variance along  $v_{n-1}$ is $\sqrt{|\lambda_{n-1}|}$, etc. \citep[c.f.][]{pekalska01gen}.

\subsection{Modeling Negative Spectra}\label{cogpsymodel}
While the dissimilarity matrix constructions obtained from Equation~\ref{simplemodel} can account for a class of non-metric pairwise data from domains such as image matching, text-mining or bioinformatics, where penalization models underlie the computed similarities, they cannot necessarily appropriately model the generic case where a pairwise dissimilarity matrix is given from an experiment, say in cognitive psychology. The simple model for non-metric pairwise data introduced in the following is inspired by approaches in cognitive psychology to explain human similarity judgments \citep{tenenbaum96learning}.
Let $\{f_1,f_2,\ldots\,f_n\}$ be a basis. A given data point $x_i$ can be decomposed in this basis as
$x_i=\sum_{k=1}^n\alpha_k^{(i)}f_k.$
The squared $l_2$ distance between $x_i$ and $x_j$ therefore reads:
$d_{ij}=||x_i-x_j||^2=\big|\big|\sum_{k=1}^n \big(\alpha_k^{(i)}-\alpha_k^{(j)}\big)f_k\big|\big|^2.$
However this assumes constant feature-perception, i.e. a constant mental image with respect to different tasks. In the realm of human perception this is often not the case, as illustrated by the following well known visual ``traps'' (Figure~\ref{trap}).
\begin{figure}[!ht]
\begin{center}
\includegraphics[width=4cm]{\mpdir/whatdoyousee.eps}\hspace{2cm}\includegraphics[width=4cm]{\mpdir/kopfeinstein.ps}
\caption{Left: What do you see? A small cube in the corner of a room or a large cube with a cubic hole or a small cube sticking with one corner on a large one? Right: What do you see? A young lady or an old woman? If you were to compare this picture to a large set of images of young ladies or old women, the (unwilling) perception switch could induce large individual weights on the similarity.}
\label{trap}
\end{center}
\end{figure}
Our perception has several ways to interpret the figures which can give rise to asymmetry \citep{thomas97con} by a different weighting of the perceived dissimilarities. It is important to notice here that for human similarity judgments, one can hardly speak of artifact or erroneous judgments with respect to a Euclidean norm. The latter seems rather exceptional in these cases. 

A possible way to model different interpretations of a given geometric object is to introduce states $\{\omega^{(1)},\omega^{(2)}\ldots\,\omega^{(d)}\}$, $\omega^{(l)}\in\R^n$ for $l=1,2,\ldots\,d$, affecting the features. The similarity judgment between objects then depends on the perceptual state (weight) the observer is in. Assuming that the person is in state $\omega^{(l)}$ the distance becomes
\begin{equation}\label{cogpsyd}
d_{ij}=||x_i-x_j||^2=\Big|\Big|\sum_{k=1}^n \big(\alpha_k^{(i)}-\alpha_k^{(j)}\big)\omega_k^{(l)}f_k\Big|\Big|^2.
\end{equation}
\emph{With no further restriction this model yields non metric distance matrices.}

In the worst case $l$ is random, but usually perception-switches can be modeled and $l$ becomes some function of $(i,j)$. For random $l$, non-metricity is an artifact of sample size, since when averaging the $d$'s over $p$ observers the mean dissimilarity is asymptotically metric in $p$ ($\langle d\rangle\rightarrow$ metric as $p\rightarrow\infty$): the mean $\omega$ becomes constant for all $i,j$ equal to the expectation of its distribution. 

On the other hand, if we suppose that the function $l$ of $(i,j)$ does not vary much between observers, then the averaging does not flatten out the non-metric structure induced by the systematic perception-switch.

\subsection{Illustration (Proof of Principle)}
The importance of the information coded by the negative eigenvalues is
exemplified by the following simple example: consider $n$ objects, labeled $1,2,\ldots\,n$, presenting two
salient features. Suppose that they cluster into
$\{1,\ldots\,\frac{n}{2}\}$ and $\{\frac{n}{2}+1,\ldots\,n\}$
according to the first feature, and into $\{1,3,5,\ldots\,n-1\}$ and
$\{2,4,6,\ldots\,n\}$ according to the second. Let $D_1$ and $D_2$ be
the dissimilarity matrices corresponding to feature $1$ and $2$
respectively. Save very pathological cases the spectra associated to the $D$
obtained by subtraction or division of $D_1$ and $D_2$ contain steeply falling
negative eigenvalues. Furthermore the projection onto the first two
eigenvalues exhibits a clear distinction w.r.t. feature $1$ whereas the
projection onto the last two eigenvalues exhibits a clear distinction
w.r.t. feature $2$.

Let e.g. $n=8$. Two artificial dissimilarity matrices $D_1$ and $D_2$ were constructed to reflect the above surmise about the underlying structure:
\begin{equation*}
D_1=
\left(
\begin{smallmatrix}
0.00 & 2.36 & 2.59 & 1.78 & 4.74 & 4.82 & 4.98 & 4.72\\
2.36 & 0.00 & 2.39 & 1.60 & 4.98 & 5.06 & 5.22 & 4.96\\
2.59 & 2.39 & 0.00 & 2.09 & 5.29 & 5.37 & 5.53 & 5.27\\
1.78 & 1.60 & 2.09 & 0.00 & 5.08 & 5.16 & 5.32 & 5.06\\
4.74 & 4.98 & 5.29 & 5.08 & 0.00 & 1.20 & 1.82 & 1.62\\
4.82 & 5.06 & 5.37 & 5.16 & 1.20 & 0.00 & 2.98 & 1.78\\
4.98 & 5.22 & 5.53 & 5.32 & 1.82 & 2.98 & 0.00 & 2.02\\
4.72 & 4.96 & 5.27 & 5.06 & 1.62 & 1.78 & 2.02 & 0.00
\end{smallmatrix}
\right)
\text{ and }
D_2=
\left(
\begin{smallmatrix}
0.00 & 4.15 & 2.03 & 4.14 & 1.26 & 4.33 & 0.690 & 4.85\\
4.15 & 0.00 & 4.70 & 0.570 & 4.37 & 1.82 & 4.24 & 2.02\\
2.03 & 4.70 & 0.00 & 4.69 & 1.85 & 4.88 & 1.68 & 5.40\\
4.14 & 0.570 & 4.69 & 0.00 & 4.36 & 1.83 & 4.23 & 2.67\\
1.26 & 4.37 & 1.85 & 4.36 & 0.00 & 4.55 & 0.730 & 5.07\\
4.33 & 1.82 & 4.88 & 1.83 & 4.55 & 0.00 & 4.42 & 2.14\\
0.690 & 4.24 & 1.68 & 4.23 & 0.730 & 4.42 & 0.00 & 4.94\\
4.85 & 2.02 & 5.40 & 2.67 & 5.07 & 2.14 & 4.94 & 0.00
\end{smallmatrix}
\right).
\end{equation*}
Figure~\ref{toy2} shows the result obtained by Algorithm~\ref{mainalg}.  The spectrum associated to $D=D_1-D_2$ is non positive. The information contained in the positive and the negative part is recovered:
\begin{figure}[!ht]
\centering\includegraphics[width=11pc]{\mpdir/sm1/sm1.3}\hfil\includegraphics[width=11pc]{\mpdir/sm1/sm1.4}\hfil\includegraphics[width=11pc]{\mpdir/sm1/sm1.5}
\caption{Sorted spectrum associated to the non-metric $E$ (right), Projection onto the two leading positive eigendirection and projection onto the two leading negative eigendirections (right).}
\label{toy2}
\end{figure}
We see that the information represented in the first two
eigendirections is related to the variance due to the cluster
structure $\{1,\ldots\,4\}$ and $\{5,\ldots\,8\}$ whereas the
information represented in the last two eigendirection relates to the
cluster structure $\{1,3,\ldots\,7\}$ and $\{2,4,\ldots\,8\}$.
\emph{This last information would have been lost by usual methods
 relying on high variance and thus neglecting the negative eigenvalues}.

\section{Summary}
We summarize the procedure and the rationale behind it (see \emph{schematic} diagram Figure~\ref{diagram}). 

Consider the following illustrative setting: we have apples of different sizes and two colors. There are two salient features: size (geometric) and color (categorial).
\begin{figure}[!ht]
\hspace{1.65cm}\includegraphics[width=20cm]{\mpdir/apples/apples_.1}
\caption{Summarizing diagram.}
\label{diagram}
\end{figure}
These apples are pairwise compared, either by a computer algorithm, a human test subject or any other mechanism. This comparison yields a dissimilarity matrix $D$ or a similarity matrix $S$. In the latter case a problem specific dissimilarity matrix $D$ is obtained from $S$.

From $D$ we compute the centralized (pseudo-)covariance matrix $C$ and its spectrum. $C$ is positive semi-definite if and only if $D$ is squared-Euclidean. For generic $D$ this is not the case and the usual techniques fail to take this into account.

We project the data onto the first two leading eigenvectors explaining the variance associated to the first feature (size). Second, we project the data onto the last two eigenvectors accounting for the variance of the second feature (color). This last step is done by an embedding into the pseudo-Euclidean space. 

The second feature is lost by any method relying exclusively on high variance, that is, the majority of machine learning techniques. We propose the exploration of the negative eigenspectrum for \emph{feature discovery}.


\section{Further Illustrative Applications}
To go beyond toy examples showing that non-metricity can code for interesting features, we will now illustrate our feature discovery technique by three applications from real-world domains, namely image matching, text mining and cognitive psychology.

\subsection{USPS Handwritten Digits}
A similarity matrix is computed from binary image matching on the
digits $0$ and $7$ of the USPS data set. Digits $0$ and $7$ have been
chosen since they exhibit clear geometric differences. All images have
been sorted according to decreasing sum of pixel value ($1$ to $256$) thus
separating the bold digits from the light ones. A total of $1844$
samples have been retained. The images have been normalized and
discretized to have binary pixel values $0$ and $1$.

\emph{Binary image matching.}
Let $r$ and $s$ denote the labels of two images and $S_{rs}$ the score rating mutual similarity. 
In the case of binary images, $S_{rs}$ is a function of $a$, $b$, $c$ and $d$, where $a$ counts the number of variables where both objects $s$ and $r$ score $1$, $b$ the number where $r$ scores $1$ and $s$ scores $0$, $c$ the number of variables where $r$ scores $0$ and $s$ scores $1$ and $d$ the number of where both objects score $0$.
The counting variables $a$, $b$, $c$ and $d$ allow to define a variety of similarity scores $S_{rs}$ \citep[see][]{cox94multidimensional}. 
We will be interested in the \emph{Simpson} score, defined by
\begin{equation*}
S_{rs}=\frac{a}{\min{(a+b,a+c)}}.
\end{equation*}
It exhibits a strongly falling negative spectrum, corresponding to highly non-metric data. 
Projection onto the eigenvectors associated to the first leading eigenvalues and projection onto the eigenvectors associated to the last eigenvalues yield results different in nature. 

\begin{figure}[!ht]
\centering\includegraphics[width=25pc]{\mpdir/simposneg/simposneg_with_insets.1}
\caption{Projection onto the first two positive eigendirections. The explained variance is associated to the geometric shape.}
\label{simpos}
\end{figure}
\begin{figure}[!ht]
\centering\includegraphics[width=25pc]{\mpdir/simposneg/simposneg_with_insets.2} 
\caption{Projection onto the last two negative eigendirections. The explained variance is associated to the stroke weight.}
\label{simneg}
\end{figure}
In each case there is a clear interpretation of the variance according to salient features: (i) Figure~\ref{simpos} shows that the variance in the ``positive'' eigenvectors corresponds to the geometrical distinction between the shapes of the $0$'s and the $7$'s; (ii) Figure~\ref{simneg} on the other hand shows that in the ``negative'' eigenvectors the variance is associated to the feature of stroke weight. 
\emph{This interesting feature would have been lost if we had embedded the data by conventional methods thereby discarding the negative part of the spectrum.}

\subsection{Text-Mining}
We are interested in the semantic structure of nouns and adjectives from two topically unrelated sources, namely Grimm's Fairy Tales \citep{grimm} and popular science articles about space exploration \citep{nasa}. Both sources contributed $60$ documents containing roughly between $500$ and $1500$ words each. 
A subset of $120$ nouns and adjectives has been selected, containing both very specific and very general terms out of both data sources.

\emph{Similarity measure for words.}
From a set of $p$ documents and a choice of $n$ keywords we can construct a contingency table, by simply indicating whether word $i$ ($1\leq i \leq n$) appears in document $k$ ($1\leq k \leq p$) or not. This yields a $p\times n$ boolean matrix.

We will take the \emph{Keyword Semantic Proximity} as similarity
measure \citep{rocha01talk,rocha01bio}, which expresses that two words are similar if they often
appear together in a document. This similarity is penalized if they
individually spread over a large number of documents:
\begin{equation*}
s_{ij}=\frac{\#\{\text{documents where word $i$ \emph{and} word $j$ appear}\}}{\#\{\text{documents where word $i$ \emph{or} word $j$ appear}\}}.
\end{equation*}
From this similarity measure, we obtain a dissimilarity matrix via, e.g. $d_{ij}=-\log(s_{ij})$. In \citet{rocha01talk} the author uses $d_{ij}=1/s_{ij}-1$ which is another possible choice. In either case, the resulting dissimilarity matrix $d$ is not squared-Euclidean such that the associated \mbox{(pseudo-)}covariance matrix exhibits strong negative eigenvalues (see inset in Figure~\ref{textpos}).

\begin{figure}[!ht]
\centering\includegraphics[width=30pc]{\mpdir/text/text.1}
\caption{Projection onto the first two eigendirections.}
\label{textpos}
\end{figure}

% Figure 2
\begin{figure}[!ht]
\centering\includegraphics[width=30pc]{\mpdir/text/text.2}
\caption{Projection onto the last two negative eigendirections.}
\label{textneg}
\end{figure}

The data is projected on the first two leading eigenvectors (Figure~\ref{textpos}).
On the far left we find the words stemming from the popular science articles (e.g. ``nuclear'', ``computer'', ``physics'' etc.) whereas on the far right we have those from Grimm's Fairy Tales (e.g. ``castle'', ``queen'', ``ravens'' etc.). The captured variance can be interpreted as the semantic context of the words. 

Projection onto the last two eigendirections yields a distribution
over a new interesting feature (Figure~\ref{textneg}). We notice that
in the upper half we find words of high specificity of either of the
sources (e.g. ``astronauts'', ``wolf'', ``witch'' etc.). In the lower
half we see an accumulation of words with general, unspecific,
meaning, expected to be found in a large variety of documents (e.g.
``day'', ``world'', ``thing'' etc.). Thus to our understanding the
variance associated to the last eigendirection again corresponds to
the \emph{specificity} of the words (relative to the data source).
\emph{This feature would have gone unnoticed by algorithms not specifically
 taking into account the negative eigenvalues.}


\subsection{Cognitive Psychology}
We finally present an example from human similarity judgments in cognitive psychology. This will also allow us to illustrate the model presented in Section~\ref{cogpsymodel}.

The pairwise dissimilarity data is obtained from \citet{gati82rep}. The stimuli tested consist of $16$ images of flowers having leaves of varying elongation and stems of increasing size (Figure~\ref{distfiglargeneg2}). These two stimuli were presented to a group of thirty undergraduate students from the Hebrew University who, individually, evaluated the mutual dissimilarity of the flowers on a 20-point scale \citep[see][]{gati82rep}.

We have processed the data according to Algorithm~\ref{mainalg}. 
In the positive eigendirections we obtain a very good reconstruction of the two geometric features, namely the elongation of the leaves and the size of the stem: see Figure~\ref{distfiglargeneg4}, middle. There seems to be no tendency to favor one over the other. The first component explains the variance in leaf elongation (horizontal axis), the second the variance of the stem size (vertical axis).

Interestingly, the projection onto the last two negative eigendirections exhibits further structure, as shown by Figure~\ref{distfiglargeneg4}, right.  The interpretation, however, is not so straightforward.
Two clusters loosely form, separated by the last eigendirection (vertical axis). They are $\{1,2,$ $5,6,11,12,15,16\}$ and $\{3,4,7,8,9,10,13,14\}$. A possible feature could be the oddness of a plant, such that the first cluster contains the odd plants, and the second the ``normal'' ones, since one could expect plants with small leaves to be of small size and plants with large leaves to be of greater size. The odds here are the small plants with large leaves and the large plants with small leaves. This would correspond to categorial perception while judging similarity. 

Features related to the concept of normality, or expectation, are not uncommon in cognitive psychology. In \citet{nav02com} features like the normality or usuality of faces are discussed in the context of the Modified Contrast Model, along with certainly not easily graspable features like relationships in parenthood. While the authors focus on common and distinctive features and distinguish between conceptual and perceptual features, the interpretation of the discovered features remains as a second independent step in data analysis. 

\begin{figure}[!ht]
\centering
\includegraphics[width=1pc]{\mpdir/plants/plants.1}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.2}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.3}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.4}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.5}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.6}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.7}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.8}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.9}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.10}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.11}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.12}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.13}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.14}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.15}\hspace{3mm}
\includegraphics[width=1pc]{\mpdir/plants/plants.16}\hspace{3mm}
\caption{Images of the flowerpots as presented to the test person.}
\label{distfiglargeneg2}
\end{figure}


\begin{figure}[!ht]
\centering\includegraphics[width=10pc]{\mpdir/flowerpot/flowerpot.1}
\hfil\includegraphics[width=11pc]{\mpdir/flowerpot/flowerpot.2}\hfil\includegraphics[width=11pc]{\mpdir/flowerpot/flowerpot.3}\hfil
\caption{Left: Sorted eigenvalues. Middle: Projection onto the leading two positive eigenvalues. Right: projection onto the last two eigendirections.}
\label{distfiglargeneg4}
\end{figure}
We explain the flowerpot experiment according to the model presented  in Section~\ref{cogpsymodel}, starting from a uniform distribution of $16$ points in three dimensions and choosing the feature vectors $f_k$, $k=1,2,3$ to be the unit vectors $e_1=(1,0,0)$ etc.

The states are obtained by fitting the $d$ defined in Equation~\ref{cogpsyd} heuristically to the experimental dissimilarity by minimization of the difference of the means over all matrix elements. 
 
We obtain a good model fit for six states $\{(8.3,0,0),$ $(0,3.5,0),$  $(4.7,4.7,4.7),$ $(6.4,6.4,0),$ $(0, 3.4,3.4),$ $(3.1,0,3.1)\}$. See Figure~\ref{flowerpot_prediction}.

In other words, following the semantics of the model presented, one can explain the results of the obtained dissimilarities by six perceptual states of the observer; i.e. the weight vectors model the bias in perception. These seem to outnumber the actually observed features (in the two-dimensional representations) which are three in number (the two geometric features in the positives and the categorial one in the negatives). However, we must keep in mind that one may reduce the number of weights required to approximate $d$ by a deeper knowledge of the initial feature presentation, including its dimensionality. We have taken a uniform distribution in three dimensions for lack of more precise knowledge.

\begin{figure}[!ht]
\centering\includegraphics[width=10pc]{\mpdir/flowerpot_model/flowerpot_model.1}\hfil\includegraphics[width=11pc]{\mpdir/flowerpot_model/flowerpot_model.2}\hfil\includegraphics[width=11pc]{\mpdir/flowerpot_model/flowerpot_model.3}\hfil
\caption{Prediction of flowerpot experiment.}
\label{flowerpot_prediction}
\end{figure}


\section{Conclusion and Outlook}
This work studies the potential of relevant information being coded
specifically by the non-metric part of the spectrum of a
pseudo-covariance matrix. It has been shown that non-metricity \emph{can}
indeed code for features relevant to a better understanding of the data set. The proposed algorithm effectively overcomes the drawback of most variance based algorithms which take only into account the variance of the leading eigendirections.
Model.illustrations provide a simple intuition and explanation of the phenomena.  
Note, however, that spectra like Figure~\ref{distfig} (right) are only
potentially---not necessarily---containing interesting information in their negative part,
some fancy noise process might also be the cause of such a structure.

Concluding, it is an important step in unsupervised data
analysis to find out whether the negative part of the spectrum codes
for interesting variance. The present technique can be employed as a general exploratory feature discovery tool. Application fields range from cognitive psychology, marketing, biology, engineering and bioinformatics, where in principle new structure awaits its discovery.

A further interesting direction is to go beyond visualization toward automated structure learning. 
Investigations to overcome low-dimensional feature discovery based on visualization will focus on, e.g., stability analysis \citep{roth02,MeiZieKawMue02} of various projections onto the possibly negative eigenspace in order to assess quantitatively relevant structure and to rule out noise related, erroneous, feature interpretations. 

A major focus will concern the automated distinction of structure induced by intrinsic non-metricity from mere artifacts of some fancy noise process with the overall goal to provide automated learning and procedures that can optimally
 make use of  the information coded by intrinsic non-metricity.


\acks{
Special thanks go to Volker Roth for valuable discussions, as well as
to Motoaki Kawanabe, Christin Schäfer, Sebastian Mika, Mikio Braun and Andreas Ziehe for thorough reading of the manuscript. This work is partially supported by DFG
grants \# MU 987/1-1 and \# JA 379/13-2 as well as PASCAL Network of Excellence (EU \# 506778).

A particular acknowledgment goes to the reviewers and the action editor who helped with many stringent and interesting remarks and suggestions improve this work. }
\bibliography{jmlr}
\end{document}
