Learning Nonstructural Distance Metricby Minimum Cluster Distortions
Daichi Mochihashi *#,Genichiro Kikui, and Kenji Kita ** ATR Spoken Language Translation
Research Laboratories, Japan# Graduate School of Information Science,
NAIST, JapanEMNLP 2004

Today’s Topic
We propose a Metric distance functionthat can be used as an alternative/in conjunction
with tf.idf.
z Agenda:– How to get an optimal metric?
– Problems we met with texts.
zOverview
Motivation and Backgroundz Two distance functions– Euclid and generalized Mahalanobisz Quadratic Minimization Problem
z Recent Related Worksz Experiments– Sentence retrieval, Document retrieval– General Machine Learning dataz Discussion & ConclusionzBackgroundz

Comparing two linguistic expressions:– Structural• Tree kernel (Collins and Duffy 2001), HDAG(Suzuki et al. 2003), …
• Not all NLP can be kernelized• Leaf comparison is still done non-hierarchically• Rough but fast search is needed (IR, QA, EBMT)– Non-structural comparison is even necessary• But ...

Non-structural comparison
Comparison in vector spacez Many NLP methods still depend on naïvecosine distance function– Information Retrieval– Subtopic segmentation (ex.Hearst 94, Choi 00)z• Method for structural text comparison itself
depends on cosine distance between paragraphs!
zFeature weightings and correlations– like Polynomial kernel– But there aren’t any.

Euclidean distancer rr r r rd (u , v ) = (u − v )' (u − v ) = ∑ (ui − vi ) 2
iCosine distance is identical to Euclidean(if normalized)
z Problems：– Ignores correlation between the features(i.e. dimensions)– Ad hoc feature weighting (tf.idf)z• No theoretical justification w.r.t. distances

Generalized Mahalanobis distancer rr rr r
d M (u , v ) = (u − v )' M (u − v )= ∑∑ mij (ui − vi )(u j − v j )ijSimultaneous feature correlation and weighting
as mijz Famous distance for pattern recognition– M is often a covariance matrix of some cluster– However, M is arbitrary in generalz What is an optimal M?
zFeature space and data
Training data is not independent in generalz Often, data have a cluster structure– Nested linguistic structuresz Usually, cluster doesn’t form a true spherebut an ellipsoidal form (feature correlations)
zfnData△△ｘ△ｘｘ ｘ ｘｘ

△ △f2Clusters
f1

Minimization Problem
Centroid△ｘ

△▲

ｘ▲ ｘｘ
△△ △ｘｘｘｘ ｘｘ ▲ ｘ
△ △ ｘ

△▲
△ △

z

Minimization of within-cluster distancesr rmeasured by d M (u , v )zMinimization of total sum of distances
between cluster data and its centroidQuadratic Optimization
zFor training cluster c in C, when we writercentroid of c as c ,r rr rr rmin ∑∑ d M ( x , c ) = min ∑∑ ( x − c )' M ( x − c )rc∈C x∈crc∈C x∈c– Constraint: |M|=1 (to avoid M=0)z Solution
Let A the sum of covariance matrixof each cluster,

M =| A |1/ n−1A ∝A– Proof: by Lagrangian.
(Extension to Ishikawa98)−1

NotesFor linguistic feature vector, A is often singular+
A– Moore-Penrose pseudoinverse as A−1
z Interpreted as Linear projection+Euclid distancer rr rr rd M (u , v ) = (u − v )' M (u − v )rr
1/ 2 r
1/ 2 r= ( M (u − v ))' ( M (u − v ))z

– Euclidean distance in M 1/ 2-mapped space(optimal geometry)Related Works
Xing,Ng,Jordan (NIPS ‘02)
r r– Induce M from set S of “similar” pairs ( xi , x j )– Optimization via Newton-Raphson– O(n^2) pairs are required→Our method can induce M all at oncez Fisher kernel (Jaakkola 98)– Same concept in kernel-based method
zK ( x, y ) = U ( x)' I −1U ( y ) （I: Fisher information matrix）– Unit matrix approximation in reality

Experiments
Synonymous sentence retrievalz Document retrievalz General vectorial data in Machine Learningz

Synonymous sentence retrievalz

ATR paraphrasing corpus (Sugaya et al., 2002)– English sentence → multiple Japanesetranslations• English 10,610, Japanese 33,723,164 sentences– Possible Japanese translations as a cluster

Paraphrasing as a Cluster
Japanese sentences
English sentence Translation

Japanese sentences
English sentence Translation

ClusterszPossible translations can be regarded
as a synonymous cluster.

Synonymous sentence retrievalz

Basic procedure:– Calculate a metric matrix from training clusters– How well the test data’s clusters can berecovered?
z Feature‥ Unigrams, bigrams of function words– Large number of features→ Dimension reduction through SVD (LSI)– idf feature weighting as a baseline.

Sentence retrieval result 1z

Query: “How much is total?” (「全部でいくらですか」)
Euclid distance (~cosine) Metric distance0.1732
1.781
1.902
1.966
1.966
1.974
1.983
2.283
2.505
2.65
2.729
2.749

全部でいくらですか
合計でおいくらですか
紫外線防止ですか
内金はいくらですか入場料はいくらですか
手付金はいくらですか
全部でおいくらですか
どんな兆候ですか
どんな症状ですかお一人ですか
放送で呼び出してください
紫外線防止ですね

Blue: Correct answer
Red : Wrong answer

0.2712
0.34440.34440.369
0.43770.44790.45050.45580.4602
0.46820.47290.4851

合計でいくらでしょうか
内金はいくらですか
入場料はいくらですか
手付金はいくらですか
合計でいくらいたしますか
合計でいくらいたしますでしょうか
全部でいくらですか
合計でいくらになりますか
合計でいくらになりますでしょうか
合計でいくらになるでしょうか
合計でいくらしますか
合計でいくらしますでしょうかResult 2 (sentence retrieval)
Precision-Recall Curve
11

0.8

0.8

Precision

Precision

z0.6
0.4

0.6

0.4

0.2

0.2

000.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1z

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

RecallRecallEuclidean+idf

Metric+idf

1DimensionReduction
── 1%
── 5%
── 10%
── 20%
── 50%

200/50 training/test clusters (100 sents/cluster)– 10-fold cross validation

Result 3 (sentence retrieval)
11 Point Average Precision
0.7
0.6Precision

z0.5
0.4

Metric+idf
Euclid+idf

0.3
0.2
0.101 2 3 4 5 10 15 20 25 50

Dimensionality Reduction(%)

Document retrieval
20-Newsgroup dataset (@ai.mit.edu)– 5-fold cross validation (16/4 training/test)– tf.idf feature weighting as a baselinez General text‥‥Lengths differ much(vector norm problem)– Cannot treat as a cluster in vector spacez– Sub/over sampling to median length (130words)
Length normalization (mapping to hypersphere)
didn’t work well.

Result (Document retrieval)zDim.red. R-precision

11pt Avr. Prec.

1%

0.388

0.368

0.450

0.430

2%

0.359

0.343

0.425

0.409

5%

0.329

0.318

0.397

0.38810%

0.316

0.307

0.379

0.376

20%

0.343

0.297

0.397

0.365

Data from Yahoo.com web directory(http://dir.yahoo.com/*/) has the same tendency

Analysis (Document retrieval)
Only slight increase in precision→ Dimensionality reduction
z Dim. red. by SVD：
X = USV −1 → X k = Vk X
M 1/ 2 X k = M 1/ 2 ⋅ Vk X
– Dimensionality reduction V subsumes M
because of diffuse clusters
z Simultaneous metric induction and dim. red.
z Effective when clusters are tight or dim. red. isunnecessary (sentence retrieval, general data)zUCI Machine Learning datasets“wine” dataset“protein” dataset

K-means clustering x 100, # of clusters known
z Precision of clustering is apparently higher.
zDiscussion
Of course, our criterion is one of the possibilities
z Latest NIPS‘03 saw two related works:– Spectral clustering setting (Bach&Jordan 04)– Relative comparison data with SVM(Schultz&Joachims 04)zz“Minimum distortion” concept in kernel Hilbert
space?

Conclusion
Introduced an optimal metric distance invector space using training clusters– Result of quadratic minimization problem
z Simpler and faster induction
than previous work and intuitive result
z Validated by sentence retrieval, document
retrieval, and general vectorial data
– Simultaneous induction of metric and dim. red.
may be necessary for texts– Same minimization in kernel Hilbert space?
z