Learning Nonstructural Distance Metric by Minimum Cluster Distortion

Learning Nonstructural Distance Metric by Minimum Cluster Distortions Daichi Mochihashi, Genichiro Kikui ATR Spoken Language Translation research laboratories Hikaridai 2-2-2, Keihanna Science City Kyoto 619-0288, Japan daichi.mochihashi@atr.jp genichiro.kikui@atr.jp Kenji Kita Center for Advanced Information Technology, Tokushima University Minamijosanjima 2-1 Tokushima 770-8506, Japan kita@is.tokushima-u.ac.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 cor- relations. To answer these problems, we propose an optimal metric distance that can be used as an alter- native to the cosine distance, thus accommodating the two problems at the same time. This metric is optimal in the sense of global quadratic minimiza- tion, and can be obtained from the clusters in the training data in a supervised fashion. We confirmed the effect of the proposed metric distance by a synonymous sentence retrieval task, document retrieval task and the K-means clustering of general vectorial data. The results showed con- stant improvement over the baseline method of Eu- clid and tf.idf, and were especially prominent for the sentence retrieval task, showing a 33% increase in the 11-point average precision. 1 Introduction Natural language processing involves many kinds of linguistic expressions, such as sentences, phrases, documents and the collection of documents. Com- paring these expressions based on semantic proxim- ity is a fundamental task and has many applications. Generally, two basic approaches exist to compare two expressions: (a) structural and (b) nonstruc- tural. Structural approaches make use of syntactic parsing or dependency analysis to make a rigorous comparison; nonstructural approaches use vector representation and provide a rough but fast compar- ison 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 non- structural comparison. This is not only because non- structural comparison constitutes an integral part in structural methods (that is, even in hierarchi- cal methods the leaf comparison is still atomic), but because it is frequently embedded in many ap- plications where structural parsings are not avail- able or computationally too expensive. For exam- ple, information retrieval has long used the ‘bag of words’ approach (Baeza-Yates and Ribeiro-Neto, 1999; Sch¨utze, 1992) mainly due to a lack of scal- able segmentation algorithms and the huge amount of data involved. While segmentation algorithms, such as TEXTTILING (Hearst, 1994) and its recent successors using the inter-paragraph similarity ma- trix (Choi, 2000), all themselves use nonstructural cosine similarity as a measure of semantic proxim- ity 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 a simple 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 …

Content truncated to 500 words