ĐỀ TÀI: FINDING THE SEMANTIC SIMILARITY IN VIETNAMESE Abstract Our thesis shows the quality of semantic vector representation with random projection and Hyperspace Analogue to Language model under about the researching on Vietnamese. The main goal is how to find semantic similarity or to study synonyms in Vietnamese. We are also interested in the stability of our approach that uses Random Indexing and HAL to represent semantic of words or documents. We build a system to find the synonyms in Vietnamese called Semantic Similarity Finding System. In particular, we also evaluate synonyms resulted from our system. Keywords: Semantic vector, Word space model, Random projection, Apache Lucene Acknowledgments First of all, I wish to express my respect and my deepest thanks to my advisor Pham Bao Son, University of Engineering and Technology, Viet Nam National University, Ha Noi for his enthusiastic guidance, warm encouragement and useful research experiences. I would like to gratefully thank all the teachers of University of Engineering and Technology, VNU for their invaluable knowledge which they provide me during the past four academic years. I would also like to send my special thanks to my friends in K51CA class, HMI Lab. Last, but not least, my family is really the biggest motivation for me. My parents and my brother always encourage me when I have stress and difficulty. I would like to send them great love and gratefulness. Ha Noi, May 19, 2010 Nguyen Tien Dat Contents Abstract Acknowledgments Contents Figure List Table List Table List Chapter 1 Introduction Chapter 2 Background Knowledge 2.1 Lexical relations 2.1.1 Synonym and Hyponymy 2.1.2 Antonym and Opposites 2.2 Word-space model 2.2.1 Definition 2.2.2 Semantic similarity 2.2.3 Document-term matrix 2.2.4 Example: tf-idf weights 2.2.5 Applications 2.3 Word space model algorithms 2.3.1 Context vector 2.3.2 Word-concurrence Matrices 2.3.3 Similarity Measure 2.4 Implementation of word space model 2.4.1 Problems High dimensional matrix Data sparseness Dimension reductions 2.4.2 Latent semantic Indexing 2.4.3 Hyperspace Analogue to Language 2.4.4 Random Indexing Chapter 3 Semantic Similarity Finding System 3.1 System Description 3.2 System Processes Flow 3.3 Lucene Indexing 3.3 Semantic Vector Package 3.4 System output Chapter 4 Experimental setup and Evaluations 4.1 Data setup 4.2 Experimental measure 4.2.1 Test Corpus 4.2.2 Experimental Metric 4.3 Experiment 1: Two kinds of context vector 4.4 Experiment 2: Context-size Evaluation 4.5 Experiment 3: Performance of system 4.6 Discussion Chapter 5 Conclusion and Future work References Appendix Figure List Figure 2.1: Word geometric repersentaion Figure 2.2: Cosine distance Figure 2.3: The processes of Random indexing Figure 3.1: The processes of Semantic Similarity Finding System Figure 3.2: Lucene Index Toolbox - Luke Figure 4.1: Context size Figure 4.2: P[SUB]1[/SUB] when context-size changes Figure 4.3: P[SUB]n[/SUB], n=1 19 for each kind of word Figure 4.4 Average synonym for Test Corpus Table List Table 2.1: A example of documents-term matrix Table 2.2: Word co-occurrence table Table 2.3: Co-occurrences Matrix Table 4.1: All words in Test corpus – Target words Table 4.2 Results of Mode 1 and 2 on Test Corpus Table 4.3: Results of Context-size Experiment Table 4.4: P[SUB]1[/SUB](TestCorpus) for each context-size Table 4.5: the best synonyms Table 4.5: the best synonyms of all target words retuned by our System Table 4.6: Result output for nouns returned by system. Table 4.7: Result output for pronouns returned by system. Table 4.8: Result output for Verbs returned by system Table 4.9: Result output for Verbs returned by system Table 4.10: P[SUB]n[/SUB] , n = 1, 2 19 of each kind of word and Test Corpus Table 4.11: Some interesting results Chapter 1 Introduction Finding semantic similarity is an interesting project in Natural Language Processing (NLP). Determining semantic similarity of a pair of words is an important problem in many NLP applications such as: web-mining [18] (search and recommendation systems), targeted advertisement and domains that need semantic content matching, word sense disambiguation, text categorization [28][30]. There is not much research done on semantic similarity for Vietnamese, while semantic similarity plays a crucial role for human categorization [11] and reasoning; and computational similarity measures have also been applied to many fields such as: semantics-based information retrieval [4][29], information filter [9] or ontology engineering [19]. Nowadays, word space model is often used in current research in semantic similarity. Specifically, there are many well-known approaches for representing the context vector of words such as: Latent Semantic Indexing (LSI) [17], Hyperspace Analogue to Language (HAL) [21] and Random Indexing (RI) [26]. These approaches have been introduced and they have proven useful in implementing word space model [27]. In our thesis, we carry on the word space model and implementation for computing the semantic similarity. We have studied every method and investigated their advantages and disadvantages to select the suitable technique to apply for Vietnamese text data. Then, we built a complete system for finding synonyms in Vietnamese. It is called Semantic Similarity Finding System. Our system is a combination of some processes or approaches to easily return the synonyms of a given word. Our experimental results on the task of finding synonym are promising. Our thesis is organized as following. First, in Chapter 2, we introduce the background knowledge about word space model and also review some of the solutions that have been proposed in the word space implementation. In the next Chapter 3, we then describe our Semantic Similarity Finding System for finding synonyms in Vietnamese. Chapter 4 describes the experiment we carry out to evaluate the quality of our approach. Finally, Chapter 5 is conclusion and our future work. Chapter 2 Background Knowledge 2.1 Lexical relations The first section, we describe the lexical relations to clear the concept of synonym as well as hyponymy. Relations lexical concepts are difficult to define a common way. It is given by Cruse (1986) [36]. A lexical relation is a culturally recognized pattern of association that exists between lexical units in a language. 2.1.1 Synonym and Hyponymy The synonymy is the equality or at least similarity of the importance of different linguistic. Two words are synonymous if they have the same meaning [15]. Words that are synonyms are said to be synonymous, and the sate of being a synonym is called synonymy. For the example, in the English, words “car” and “automobile” are synonyms. In the figurative sense, two words are often said to be synonyms if they have the same extended meaning or connotation. Synonyms can be any part of speech (e.g. noun, verb, adjective or pronoun) as the two words of a pair are the same part of speech. More examples of Vietnamese synonyms: độc giả - bạn đọc (noun) chung quanh – xung quanh (pronoun) bồi thường – đền bù (verb) an toàn – đảm bảo (adjective) In the linguistics dictionary, the synonym is defined in three concepts: 1. A word having the same or nearly the same meaning as another word or other words in a language. 2. A word or an expression that serves as a figurative or symbolic substitute for another. 3. Biology: A scientific name of an organism or of a taxonomic group that has been superseded by another name at the same rank. In the linguistics: Hyponym is a word whose meaning is included in that of other word [14]. Some examples in English: “scarlet”, “vermilion”, and “crimson” are hyponyms of “red”. And in Vietnamese: “vàng cốm”, “vàng choé” and “vàng lụi” are hyponyms of “vàng”, in case, “vàng” is in color. In our thesis, we don’t distinguish clearly between synonym and hyponym. We suppose the hyponym is a kind of synonym. 2.1.2 Antonym and Opposites In the lexical semantics, opposites are the words that are in a relationship of binary incompatibles in opposite as:female-male, long-short and to love – to hate. The notion of incompatibility refers to the fact that one word in an opposite pair entails that it is not the other pair member. The concept of incompatibility here refers to the fact that a word in a pair of facing demands that it not be a member of another pair. For example, “something that is long” entails that “it is not short”. There are two members in a set of opposites, thus it is referred to a binary relationship. The relationship between opposites is determined as opposition. Opposites are simultaneously similar and different in meanings [12]. Usually, they differ in only one dimension of meaning, but are similar in most other aspects, which are similar in grammar and semantics of the unusual location. Some words are non-opposable. For example, animal or plant species have no binary opposites or antonyms. Opposites may be viewed as a special type of incompatibility: An example, incompatibility is also found in the opposite pairs “fast - slow” It’s fast. - It’s not slow. Some features of opposites are given by Cruse (2004): binary, inheritress, and patency. In this section, we introduced Antonyms are gradable opposites. They located at the opposite end of a continuous spectrum of meaning. Antonym is defined: “A word which having a meaning opposite to that of another word is called antonym. “[12] It has also been commonly used with concepts synonyms. More antonym examples in Vietnamese: đi – đứng nam – nữ yêu – ghét Words can have some different antonyms, depending on the meaning or contexts of words. We study antonyms to make clearly a fundamental part of a language, in contrast to synonyms. 2.2 Word-space model Word-space model is an algebraic model to represent text documents or any objects (phrase, paraphrase, term ). It uses a mathematical model as vector to identify or index terms in the text documents. Model is useful in information retrieval, information filter, indexing. The invention can be traced at the Salton's introduction about Vector space Model for information retrieval [29]. This term is due to Hinrich Schutze (1993): “Vector similarity is the only information present in Word Space: semantically related words are close, unrelated words are distant. (page.896) “ 2.2.1 Definition Word-space models contain the related method for representing concepts in a high dimensional vector space. In this thesis, we suggest a name: Semantic vector model through our work. The models include some well-known approach such as: Latent Semantic Indexing [17], Hyperspace Analogue to language [21]. Document and queries are performed as vectors. Each dimension corresponds to a separate term. If document does not include the term, term's value in the vector is zero. In contract, if a term occurs in the documents, its value is non-zero. There are many ways to compute above values, but we study one famous way that has been developed. That is tf-idf weighting [37] (see the part of section below): The core principle is that semantic similarity can be represented as a proximate n-dimensional vector; n can be 1 or the large number. We consider the 1-dimensional and 2-dimensional word space in the Figure: Figure 2.1: Word geometric repersentaion In above geometric representation, it shows the simple words of some Vietnamese. As an example, both semantic spaces, “ụ_tụ” is the closer meaning to “xe_hơi” than “xe_đạp” and “xe_mỏy”. The definition of term depends on each application. Typically terms are single words, or longer phrases. If words are chosen to be terms, the dimensionality of the vector is the number of words in the vocabulary. 2.2.2 Semantic similarity As we have seen in the definition, the word-space model is a model of semantic similarity. On the other hand, the geometric metaphor of meaning is Meanings are locations in a semantic space, and semantic similarity is proximity between the locations. The term-document vector represents the context of term in low granularity. Besides, creating term vector according to the some words surrounding to compute semantic vector [21]. It is a kind of semantic vector model. To compare the semantic similarity in semantic vector model, we use Cosine distance: In practice, it is easier to calculate the cosine of the angel between the vectors instead of angle: