Learning Nonstructural Distance Metricby Minimum Cluster Distortions
Daichi Mochihashi, Genichiro Kikui
ATR Spoken Language Translation
research laboratories
Hikaridai 2-2-2, Keihanna Science City
Kyoto 619-0288, Japandaichi.mochihashi@atr.jp
genichiro.kikui@atr.jp
Abstract
Much natural language processing still depends on
the Euclidean (cosine) distance function between
two feature vectors, but this has severe problems
with regard to feature weightings and feature correlations. To answer these problems, we propose an
optimal metric distance that can be used as an alternative to the cosine distance, thus accommodating
the two problems at the same time. This metric is
optimal in the sense of global quadratic minimization, and can be obtained from the clusters in the
training data in a supervised fashion.
We confirmed the effect of the proposed metricdistance by a synonymous sentence retrieval task,
document retrieval task and the K-means clusteringof general vectorial data. The results showed constant improvement over the baseline method of Euclid and tf.idf, and were especially prominent forthe sentence retrieval task, showing a 33% increasein the 11-point average precision.

1 Introduction
Natural language processing involves many kinds oflinguistic expressions, such as sentences, phrases,
documents and the collection of documents. Comparing these expressions based on semantic proximity is a fundamental task and has many applications.
Generally, two basic approaches exist to compare
two expressions: (a) structural and (b) nonstructural. Structural approaches make use of syntactic
parsing or dependency analysis to make a rigorouscomparison; nonstructural approaches use vector
representation and provide a rough but fast comparison that is required for search/retrieval from a vast
amount of corpora. While structural approaches
have recently become available in a kernel-based
sophisticated treatment (Collins and Duffy, 2001;
Suzuki et al., 2003), here we concentrate on nonstructural comparison. This is not only because nonstructural comparison constitutes an integral partin structural methods (that is, even in hierarchical methods the leaf comparison is still atomic),

Kenji Kita
Center for Advanced Information
Technology, Tokushima University
Minamijosanjima 2-1
Tokushima 770-8506, Japankita@is.tokushima-u.ac.jp

but because it is frequently embedded in many applications where structural parsings are not available or computationally too expensive. For example, information retrieval has long used the ‘bagof words’ approach (Baeza-Yates and Ribeiro-Neto,
1999; Schütze, 1992) mainly due to a lack of scalable segmentation algorithms and the huge amountof data involved. While segmentation algorithms,
such as T EXT T ILING (Hearst, 1994) and its recent
successors using the inter-paragraph similarity matrix (Choi, 2000), all themselves use nonstructuralcosine similarity as a measure of semantic proximity between paragraphs.
However, the distance function so far has been
largely defined and used ad hoc, usually by a tf.idf
weighting scheme (Salton and Yang, 1973) and asimple cosine similarity, equivalently, an Euclidean
dot product. In this paper, we propose an optimal
distance function that is parameterized by a global
metric matrix. This metric is optimal in the sense of
global quadratic minimization, and can be learned
from the given clusters in the training data. Theseclusters are often attributable with many forms, suchas paragraphs, documents or document collections,as long as the items in the training data are not completely independent.
This paper is organized as follows. In section 2
we describe the issue of traditional Euclidean distances, and section 3 places it into general perspective with related works in machine learning. Section
4 introduces the proposed metric, and section 5 validates its effect on the task of sentence retrieval, document retrieval and the K-means clustering. Sections 6 and 7 present discussions and the conclusion.

2 Issues with Euclidean distances
When we address nonstructural matching, linguistic expressions are often modeled by a feature vector ~x ∈ Rn , with its elements x1 . . . xn corresponding to the number of occurrences of i’th feature. If
features are simply words, this is called a ‘bag ofwords’; but in general, features are not restricted tothis kind, and we will use the general term “feature”

in the rest of the paper.
To measure the distance between two vectors~u, ~v , a dot product or Euclidean distanced(~u, ~v )2 = (~u − ~v )T (~u − ~v )=Pn

i=1 (ui − vi )(1)2

(where T denotes a transposition) has been employed so far 1 , with a heuristic feature weighting
such as tf.idf in a preprocessing stage.
However, there are two main problems with thisdistance:(1) The correlation between features is ignored.
(2) Feature weighting is inevitably arbitrary.
Problem (1) is especially important in languages,
because linguistic features (e.g., words) generally
have strong correlations between them, such as collocations or typical constructions. But this correlation cannot be considered in a simple dot product.
While it is possible to address this with a specifickernel function, such as polynomials (Müller et al.,2001), this is not available for many problems, suchas information retrieval or question answering, that
do not fit classifications or cannot be easily “kernelized”. Problem (2) is a more subtle but inherent one:while tf.idf often works properly in practice, there
are several options, especially in tf such as logs orsquare roots, but we have no principle with which
to choose from. Further, it has no theoretical basisthat gives any optimality as a distance function.

3 Related Works
The issues above of feature correlations and feature weightings can be summarized as a problem ofdefining an appropriate metric in the feature space,based on the distribution of data. This problem hasrecently been highlighted in the field of machinelearning research. (Xing et al., 2002) has an objective that is quite similar to that of this paper, andgives a metric matrix that resembles ours based on
sample pairs of “similar points” as training data.
(Bach and Jordan, 2004) and (Schultz and Joachims,
2004) seek to answer the same problem with an additional scenario of spectral clustering and relative
comparisons in Support Vector Machines, respectively. In this aspect, our work is a straight successor of (Xing et al., 2002) where its general usage
in vector space is preserved. We offer a discussion
on the similarity to our method and our advantages
1

When we normalize the length of the vectors |~u| = |~v | = 1
as commonly adopted, (~u − ~v )T (~u − ~v ) = |~u|2 + |~v |2 − 2~u ·~v ∝ −~u · ~v = − cos(~u, ~v ) ; therefore, this includes a cosine
similarity (Manning and Schütze, 1999).

in section 6. Finally, we note that the Fisher kernel of (Jaakkola and Haussler, 1999) has the same
concept that gives an appropriate similarity of two
data through the Fisher information matrix obtained
from the empirical distribution of data. However, it
is often approximated by a unit matrix because of
its heavy computational demand.
In the field of information retrieval, (Jiang andBerry, 1998) proposes a Riemannian SVD (R-SVD)
from the viewpoint of relevance feedback. This
work is close in spirit to our work, but is not aimed
at defining a permanent distance function and does
not utilize cluster structures existent in the trainingdata.

4 Defining an Optimal Metric
To solve the problems in section 2, we note the function that synonymous clusters play. There are many
levels of (more or less) synonymous clusters in linguistic data: phrases, sentences, paragraphs, documents, and, in a web environment, the site that contains the document. These kinds of clusters can often be attributed to linguistic expressions because
they nest in general so that each expression has aparent cluster.
Since these clusters are synonymous, we can expect the vectors in each cluster to concentrate in theideal feature space. Based on this property, we canintroduce an optimal weighting and correlation in asupervised fashion. We will describe this method
below.
4.1 The Basic Idea
As stated above, vectors in the same cluster musthave a small distance between each other in the ideal
geometry. When we measure an L2 -distance between ~u and ~v by a Mahalanobis distance parameterized by M :dM (~u, ~v )2 = (~u − ~v )T M (~u − ~v )
(2)
Pn Pn
= i=1 j=1 mij (ui − vi )(uj − vj ),where symmetric metric matrix M gives both corresponding feature weights and feature correlations.
When we take M = I (unit matrix), we recover theoriginal Euclidean distance (1).
Equation (2) can be rewritten as (3) because M issymmetric:dM (~u, ~v )2 = (M 1/2 (~u − ~v ))T (M 1/2 (~u − ~v )). (3)Therefore, this distance amounts to a Euclidean distance in M 1/2 -mapped space (Xing et al., 2002).
Note that this distance is global, and different
from the ordinary Mahalanobis distance in patternrecognition (for example, (Duda et al., 2000)) that isdefined for each cluster one by one, using a clusterspecific covariance matrix. That type of distancecannot be generalized to new kinds of data; therefore, it has been used for local classifications. What
we want is a global distance metric that is generally
useful, not a measure for classification to predefinedclusters. In this respect, (Xing et al., 2002) shares
the same objective as ours.
Therefore, we require an optimization over all theclusters in the training data. Generally, data in theclusters are distributed as in figure 1(a), comprising
ellipsoidal forms that have high (co)variances forsome dimensions and low (co)variances for other dimensions. Further, the cluster is not usually aligned
to the axes of coordinates. When we find a global
metric matrix M that minimizes the cluster distortions, namely, one that reduces high variances andexpands low variances for the data to make a spherical form as good as possible in the M 1/2 -mapped
space (figure 1(b)), we can expect it to capture necessary and unnecessary variations and correlations
on the features, combining information from manyclusters to produce a more reliable metric that is not
locally optimal. We will find this optimal M below.
xnHigh
covarianceLowvariance

xn

x2

x2
High
variancex1x1(a) Original space(b) Mapped space

Figure 1: Geometry of feature space.

4.2

Global optimization over clusters

Suppose that each data (for example, sentences ordocuments) is a vector ~s ∈ Rn , and the whole corpus can be divided into N clusters, X 1 . . . XN . Thatis, each vector has a dimension n, and the number ofclusters is N . For each clusterP
Xi , cluster centroid
ci is calculated as ~ci = 1/|Xi | ~s∈Xi ~s , where |X|
denotes the number of data in X. When necessary,each element in ~sj or ~ci is referenced as sjk or cik(k = 1 . . . n).
The basic idea above is formulated as follows.
We seek the metric matrix M that minimizes the
distance between each data ~sj and the cluster centroid ~ci , dM (~sj , ~ci ) for all clusters X1 . . . XN .
Mathematically, this is formulated as a quadratic

minimization problem
M = arg min

N X
X

M i=1 ~sj ∈Xi
N X
X= arg mindM (~sj , ~ci )2(~sj − ~ci )T M (~sj − ~ci ) (4)M i=1 ~sj ∈Xiunder a scale constraint (| · | means determinant)|M | = 1.

(5)

Scale constraint (5) is necessary for excluding adegenerate solution M = O. 1 is an arbitrary constant: when we replace 1 by c, c2 M becomes a new
solution. This minimization problem is an extension to the method of MindReader (Ishikawa et al.,1998) to multiple clusters, and has a unique solution
below.
Theorem The matrix that solves the minimization
problem (4,5) is
M = |A|1/n A−1 ,(6)where A = [akl ] is defined by
akl =

N X
X

(sjl − cil )(sjk − cik ) .

(7)

i=1 sj ∈Xi

Proof: See Appendix A.
When A is singular, we can use as A−1 a MoorePenrose matrix pseudoinverse A+ . Generally, A
consists of linguistic features and is very sparse, andoften singular. Therefore, A+ is nearly always necessary for the above computation. For details, see
Appendix B.
4.3 Generalization
While we assumed through the above constructionthat each cluster is equally important, this is not
the case in general. For example, clusters with asmall number of data may be considered weak, andin the hierarchical clustering situation, a “grandmother” cluster may be weaker. If we have confidences ξ1 . . . ξN for the strength of clustering foreach cluster X1 . . . XN , this information can be incorporated into (4) by a set of normalized cluster
weights ξi∗ :M = arg min

N
X

M i=1

ξi∗

X

(~sj − ~ci )T M (~sj − ~ci ),~sj ∈Xi
PN∗
where ξi = ξi / j=1 ξj , and we obtain a respec-tively weighted solution in (7). Further, we note thatwhen N = 1, this metric recovers the ordinary Mahalanobis distance in pattern recognition. However,
we used equal weights for the experiments below
because the number of data in each cluster was approximately equal.

5.1.2 Features and dimensionality reduction
As a feature of a sentence, we adopted unigrams of
all words and bigrams of functional words from thepart-of-speech tags, because the sequence of functional words is important in the conversational corpus.
While the lexicon is limited for travel conversations, the number of features exceeds several thousand or more. This may be prohibitive for the calculation of the metric matrix, therefore, we additionally compressed the features with SVD, the same
method used in Latent Semantic Indexing (Deerwester et al., 1990).
5.1.3 Sentence retrieval results
Qualitative result Figure 5 (last page) shows a sample retrieval result. A sentence with (*) mark at
the end is the correct answer, that is, a sentencefrom the same original cluster as the query. We cansee that the results with the metric distance contain2

When the number of data in the cluster exceeds this limit,
100 sentences are randomly sampled. All sampling are madewithout replacement.

1

1%
5%
10%
20%
50%

0.8
0.6
0.4
0.2

1
0.8
Precision

5.1 Synonymous sentence retrieval
5.1.1 Sentence cluster corpus
We used a paraphrasing corpus of travel conversations (Sugaya et al., 2002) for sentence retrieval.
This corpus consists of 33,723,164 Japanese translations, each of which corresponds to one of theoriginal English sentences. By way of this correspondence, Japanese sentences are divided into
10,610 clusters. Therefore, each cluster consistsof Japanese sentences that are possible translations
from the same English seed sentence that the cluster has. From this corpus, we constructed 10 setsof data. Each set contains random selection of 200
training clusters and 50 test clusters, and each cluster contains a maximum of 100 sentences 2 . Experiments were conducted on these 10 datasets foreach level of dimensionality reduction (see below)
to produce average statistics.

0.6

1%
5%
10%
20%
50%

0.4
0.2

0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Recall(a) Metric distance +idf

0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Recall(b) Euclidean + idf

Figure 2: Precision-recall of sentence retrieval.
0.7
0.6Precision

We evaluated our metric distance on the three tasksof synonymous sentence retrieval, document retrieval, and the K-means clustering of general vectorial data. After calculating M on the training dataof clusters, we applied it to the test data to see how
well its clusters could be recovered. As a measure ofcluster recovery, we use 11-point average precision
and R-precision for the distribution of items of thesame cluster in each retrieval result. Here, R equals
the cardinality of the cluster; therefore, R-precisionshows the precision of cluster recovery.

less noise than a standard Euclid baseline with tf.idf
weighting, achieving a high-precision retrieval. Although the high rate of dimensionality reduction infigure 6 shows degradation due to the dimension
contamination, the effect of metric distance is stillapparent despite bad conditions.
Quantitative result Figure 2 shows the averaged
precision-recall curves of retrieval and figure 3
shows 11-point average precisions, for each rateof dimensionality reduction. Clearly, our method
achieves higher precision than the standard method,and does not degrade much with feature compressions unless we reduce the dimension too much, i.e.,to < 5%.
Precision

5 Experiments

0.5
0.4
0.3
0.2

Metric distance +idf
Euclidean distance +idf

0.1
0
0

5 10 15 20 25 30 35 40 45 50
Dimension Reduction(%)

Figure 3: 11-point average precision.
5.2 Document retrieval
As a method of tackling clusters of texts, the textclassification task has recently made great advanceswith a Naı̈ve Bayes or SVM classifiers (for example, (Joachims, 1998)). However, they all aim atclassifying texts into a few predefined clusters, andcannot deal with a document that fits neither of theclusters. For example, when we regard a website asa cluster of documents, the possible clusters are numerous and constantly increasing, which precludes
classificatory approaches. For these circumstances,
document clustering or retrieval will benefit from a
global distance metric that exploits the multitude ofcluster structures themselves.
5.2.1 Newsgroup text dataset
For this purpose, we used the 20-Newsgroup dataset(Lang, 1995). This is a standard text classification
dataset that has a relatively large number of classes,

Dim.
Red.
0.5%
1%
2%
3%
4%
5%
10%
20%

R-precision
Metric Euclid
0.421
0.399
0.388
0.368
0.359
0.343
0.344
0.330
0.335
0.323
0.329
0.318
0.316
0.307
0.343
0.297

11-pt Avr. Prec.
Metric Euclid
0.476
0.455
0.450
0.430
0.425
0.409
0.411
0.399
0.402
0.392
0.397
0.388
0.379
0.376
0.397
0.365

Table 1: Newsgroup text retrieval results.
3

Normalizing documents to unit length effectively maps
them to a high-dimensional hypersphere; this proved to produce an unsatisfactory result. Defining metrics that work ona hypersphere like spherical K-means (Dhillon and Modha,2001) requires further research.

K-means clustering and general vectorial
data

Metric distance can also be used for clustering or
general vectorial data. Figure 4 shows the K-meansclustering result of applying our metric distance tosome of the UCI Machine Learning datasets (Blake
and Merz, 1998). K-means clustering was conducted 100 times with a random start, where K
equals the known number of classes in the data 4 .
Clustering precision was measured as an average
probability that a randomly picked pair of data will
conform to the true clustering (Xing et al., 2002).
We also conducted the same clustering for documents of the 20-Newsgroup dataset to get a small
increase in precision like the document retrieval experiment in section 5.2.
1

0.9

0.9

Precision

Precision

0.8
0.7
0.6

1

2

5

10

0.8
0.7
0.6

13

1

2

5

10 15 20

Dimension

Dimension(a) “wine” dataset(b) “protein” dataset

1

1

0.9

Precision

5.2.2 Results
Table 1 shows R-precision and 11-point average
precision. Since the test data contains 4 clusters,
the baselines of precision are 0.25. We can see fromboth results that metric distance produces a better
retrieval over the tf.idf and dot product. However,refinements in precision are certain (average p =0.0243) but subtle.
This can be thought of as the effect of the dimensionality reduction performed. We first decompose
data matrix X by SVD: X = U SV −1 and build
a k-dimensional compressed representation X k =Vk X; where Vk denotes a k-largest submatrix of V .
From the equation (3), this means a Euclidean distance of M 1/2 Xk = M 1/2 Vk X. Therefore, Vk may
subsume the effect of M in a preprocessing stage.
Close inspection of table 1 shows this effect as atradeoff between M and Vk . To make the most of
metric distance, we should consider metric induction and dimensionality reduction simultaneously,or reconsider the problem in kernel Hilbert space.

5.3

Precision

20. Among the 20 newsgroups, we selected 16 clusters of training data and 4 clusters of test data, andperformed 5-fold cross validation. The maximum
number of documents per cluster is 100, and when
it exceeds this limit, we made a random sampling of
100 documents as the sentence retrieval experiment.
Because our proposed metric is calculated fromthe distribution of vectors in high-dimensional feature space, it becomes inappropriate if the normof the vectors (largely proportional to document
length) differs much from document to document.
3 Therefore, we used subsampling/oversampling toform a median length (130 words) on training documents. Further, we preprocessed them with tf.idf asa baseline method.

0.8
0.7

1

2

3

Dimension(c) “iris” dataset

4

0.9
0.8
0.7
0.6

1

2

5

10 20 3 5

Dimension(d) “soybean” dataset

Figure 4: K-means clustering of UCI Machine
Learning dataset results. The horizontal axis shows
compressed dimensions (rightmost is original). The
right bar shows clustering precision using Metricdistance, and the left bar shows that using Euclidean
distance.

6 Discussion
In this paper, we proposed an optimal distance metric based on the idea of minimum cluster distortionin training data. Although vector distances have frequently been used in natural language processing,
this is a rather neglected but recently highlighted
problem. Unlike recently proposed methods with
spectral methods or SVMs, our method assumes nosuch additional scenarios and can be considered as
4

Because of the small size of the dataset, we did not apply
cross-validation as in other experiments.

a straight successor to (Xing et al., 2002)’s work.
Their work has the same perspective as ours, andthey calculate a metric matrix A that is similar toours based on a set S of vector pairs (~x i , ~xj ) that canbe regarded as similar. They report that the effectiveness of A increases as the number of the training
pairs S increases; this requires O(n 2 ) sample points
from n training data, and must be optimized by acomputationally expensive Newton-Raphson iteration. On the other hand, our method uses only linear
algebra, and can induce an ideal metric using all thetraining data at the same time. We believe this metric can be useful for many vector-based language
processing methods that have used cosine similarity.
There remains some future directions for research. First, as we stated in section 4.3, the effectof a cluster weighted generalized metric must be investigated and optimal weighting must be induced.
Second, as noted in section 5.2.1, the dimensionality reduction required for linguistic data may constrain the performance of the metric distance. To
alleviate this problem, simultaneous dimensionality
reduction and metric induction may be necessary, or
the same idea in a kernel-based approach is worth
considering. The latter obviates the problem of dimensionality, while it restricts the usage to a situation where the kernel-based approach is available.

7 Conclusion
We proposed a global metric distance that is useful for clustering or retrieval where Euclidean distance has been used. This distance is optimal in thesense of quadratic minimization over all the clusters in the training data. Experiments on sentence
retrieval, document retrieval and K-means clustering all showed improvements over Euclidean distance, with a significant refinement with tight training clusters in sentence retrieval.

Acknowledgement
The research reported here was supported in part bya contract with the National Institute of Information
and Communications Technology entitled ”A studyof speech dialogue translation technology based ona large corpus”.

References
Francis R. Bach and Michael I. Jordan. 2004.
Learning Spectral Clustering. In Advances in
Neural Information Processing Systems 16. MIT
Press.
Ricardo A. Baeza-Yates and Berthier A. Ribeiro-

Neto. 1999. Modern Information Retrieval.
ACM Press / Addison-Wesley.
C. L. Blake and C. J. Merz. 1998. UCI
Repository of machine learning databases.
http://www.ics.uci.edu/˜mlearn/MLRepository.html.
Freddy Y. Y. Choi. 2000. Advances in domain independent linear text segmentation. In Proceedingsof NAACL-00.
Michael Collins and Nigel Duffy. 2001. Convolution Kernels for Natural Language. In NIPS
2001.
S. Deerwester, Susan T. Dumais, and George W.
Furnas. 1990. Indexing by Latent Semantic
Analysis. Journal of the American Society of Information Science, 41(6):391–407.
Inderjit S. Dhillon and Dharmendra S. Modha.
2001. Concept Decompositions for Large Sparse
Text Data Using Clustering. Machine Learning,
42(1/2):143–175.
Richard O. Duda, Peter E. Hart, and David G. Stork.
2000. Pattern Classification *Second Edition.
John Wiley & Sons.
Marti Hearst. 1994. Multi-paragraph segmentationof expository text. In 32nd. Annual Meeting of
the Association for Computational Linguistics,
pages 9–16.
Yoshiharu Ishikawa, Ravishankar Subramanya, andChristos Faloutsos. 1998. MindReader: Querying Databases Through Multiple Examples. In
Proc. 24th Int. Conf. Very Large Data Bases,
pages 218–227.
Tommi S. Jaakkola and David Haussler. 1999. Exploiting generative models in discriminative classifiers. In Proc. of the 1998 Conference on Advances in Neural Information Processing Systems, pages 487–493.
Eric P. Jiang and Michael W. Berry. 1998. Information Filtering Using the Riemannian SVD (RSVD). In Proc. of IRREGULAR ’98, pages 386–
395.
Thorsten Joachims. 1998. Text categorization withsupport vector machines: learning with many
relevant features. In Proceedings of ECML-98,
number 1398, pages 137–142.
Ken Lang. 1995. Newsweeder: Learning to filter
netnews. In Proceedings of the Twelfth International Conference on Machine Learning, pages
331–339.
Christopher D. Manning and Hinrich Schütze.
1999. Foundations of Statistical Natural Language Processing. MIT Press.
K. R. Müller, S. Mika, G. Ratsch, and K. Tsuda.
2001. An introduction to kernel-based learningalgorithms. IEEE Neural Networks, 12(2):181–
201.
G. Salton and C. S. Yang. 1973. On the specification of term values in automatic indexing. Journal of Documentation, 29:351–372.
Matthew Schultz and Thorsten Joachims. 2004.
Learning a Distance Metric from Relative Comparisons. In Advances in Neural Information
Processing Systems 16. MIT Press.
Hinrich Schütze. 1992. Dimensions of Meaning. In Proceedings of Supercomputing’92, pages
787–796.
F. Sugaya, T. Takezawa, G. Kikui, and S. Yamamoto. 2002. Proposal for a very-large-corpus
acquisition method by cell-formed registration.
In Proc. LREC-2002, volume I, pages 326–328.
Jun Suzuki, Tsutomu Hirao, Yutaka Sasaki, andEisaku Maeda. 2003. Hierarchical Directed
Acyclic Graph Kernel: Methods for Structured
Natural Language Data. In Proc. of the 41th Annual Meeting of Association for Computational
Linguistics (ACL2003), pages 32–39.
Eric W. Weisstein. 2004. Moore-Penrose Matrix
Inverse. http://mathworld.wolfram.com/MoorePenroseMatrixInverse.html.
Eric P. Xing, Andrew Y. Ng, Michael I. Jordan,
and Stuart Russell. 2002. Distance metric learning, with application to clustering with sideinformation. In NIPS 2002.

Thereforen X
nX

where Mkl denotes an adjugate matrix of mkl .
Therefore, we come to minimize (10) under theconstraint (11).
By introducing the Lagrange multiplier λ, we defineL="
N X XX
X(sjk − cik )mkl (sjl − cil )i=1 ~sj

k

−λ

XX
k

⇔ |Mkl | =− λ(−1)k+l |Mkl | = 0i~sj (sjk − cik )(sjl − cil )

P P

(9)

(−1)k+l |Mkl ||M |= (−1)k+l |Mkl | (... (9))
P P
i~sj (sjk − cik )(sjl − cil )=(13)λ(... (12))

and from (9), for all k(−1)k+l mkl |Mkl | = 1 .

as

N X
X

A = [akl ](14)(sjl − cil )(sjk − cik ) ,(15)

i=1 ~sj ∈Xi#(sjk − cik )mkl (sjl − cil ) , (10)k=1 l=1l=1. (12)Let us define M −1 = [m−1kl ]. Then,akl =Expanding (8), we getnX

λ(−1)k+l

Therefore, when we define|M | = 1.

~sj

mkl |Mkl | − n .

ljunder the constraint

i

#

(8)

M i=1 ~sj ∈Xi

" n n
XX X
X

(−1)

k+l

XX
∂L
=
(sjk − cik )(sjl − cil )
∂mkl
i ~s

m−1
=
kl

(~sj − ~ci )T M (~sj − ~ci ) ,

"

l

#

Differentiating by mkl and setting to zero, we obtain

Here we prove theorem 1, namely deriving M thatsatisfies the condition
n X
X

(11)

k=1 l=1

Appendix A.
Derivation of the metric matrixmin(−1)k+l mkl |Mkl | = n,from (13),A = λM −1... |A| = λn |M −1 | = λn... λ = |A|1/n ,where A is defined by (14), (15).

Appendix B.
Moore-Penrose Matrix Pseudoinverse
The Moore-Penrose matrix pseudoinverse A + of A
is a unique matrix that has a property of normal inverse in that x = A+ y is a shortest length leastsquares solution to Ax = y even if A is singular(Weisstein, 2004).
A+ can be calculated simply by a MATLAB
function pinv. Or alternatively (Ishikawa et al.,1998), we can decompose A as
A = U ΣU T ,where U is an orthonormal n × n matrix and Σ =diag(σ1 , . . . , σR , 0, . . . , 0) (R = rank(A)). Then,
A+ is calculated as++

T

A = UΣ U ,where Σ+Therefore,=diag(1/σ1 , . . . , 1/σR , 0, . . . , 0).

M = (σ1 σ2 · · · σR )1/R A+ .

  

Query: “”(‘How much is the total?’)Metric distance:
distance
0.2712
0.34440.34440.369
0.43770.44790.45050.45580.4602
0.46820.47290.4851  *! "# %$%
&'%( ") *#$+%,-") *#$
 */. 102$ * */. 102$/ *34  %$% * 65%78902$ * 65%78902$/ * 65%7:2/%; * 20!$ * 20!$/%; *synonymous sentence

Euclidean distance:
distance
0.1732
1.781
1.902
1.966
1.966
1.974
1.983
2.283
2.505
2.65
2.729
2.749

34  %$% *%<) *#$ *=%>?@A/$
! "# %$%
&'%( ") *#$+%,-") *#$
34 %<) *#$ *BC/7!DEF$
BC/7!GHF$<JI%K%$
L%M NO%P 9Q);RFS1
=%>?@A/$T

synonymous sentence(* denotes the right answers.)

UFVWYX6Z[]\_^ 9`a  _bc-d  ”

Figure 5: Sentence retrieval example.
Query: “(‘I’d like some fruit for dessert.’)Metric distance:
distance
0.35310.37090.596
0.61040.621
0.62550.62950.63430.66850.7966e/fgh1$ji;5lk/7%/
mJn ojp!q*Q rshtk 01$ *e/fgh1$ji;5lku01vC
w%xh!$yi;5z{kF01$
w%xh!$yi;5z{kF01$;
<1|}%gh!$ji5tk 01$
w%xh!$yi;5z{kF0!v/C%/
<1|}%gh!$ji5tk 0!v/C%
w%xh!$yi;5z{k7%$
mJn ojp{5%"~rs]h]{k/7%$ *synonymous sentence

Euclidean distance:
distance
1.036
1.421
1.491
1.499
1.535
1.622
1.622
:
2.787
2.854

e/fgh1$ji;5lk/7%/
z "JC h4 59uC *7%
J2Fo/h!#K#{k/7%
J2Fo/h!)tk7%/%;
htk7
%h4-56 C *7/#%h4-56 C *7/#:
mJn ojp!q*Q 2rshtk/7% *
2/h -{59%;RFSF97%

synonymous sentence

Figure 6: High rate of dimensionality reduction.