In this paper, I propose a novel word sense disambiguation method based on global co-occurrence information using Non-negative Matrix Factorization (NMF). When I calculate the dependency relation matrix, the existing method tends to produce very sparse co-occurrence matrix from a small training set. Therefore, the NMF algorithm sometimes does not converge to desired solutions. To obtain a large number of cooccurrence relations, I propose to use co-occurrence frequencies of dependency relations between word features in the whole training set. This enables us to solve data sparseness problem and induce more effective latent features. To evaluate the efficiency of the method of word sense disambiguation, I make some experiments to compare with the result of the two baseline methods. The results of the experiments show this method is effective for word sense disambiguation in comparison with the all baseline methods. Moreover, the proposed method is effective for obtaining a stable effect by analyzing the global co-occurrence information.

Keywords: Word sense disambiguation; Global co-occurrence information; Dependency relations; Non-negative matrix factorization;

Natural language processing (NLP) is a field of computer science designed to interpret and process natural language, in either textual or spoken form. It aims to design computer systems that can understand human language. These techniques allow computers to understand natural language to perform various tasks. Word Sense Disambiguation (WSD) is one of a fundamental problem in the natural language processing. The problem of WSD is defined as the task of finding the most appropriate meaning for a polysemous word within a given context.

The most successful approaches of WSD employ supervised machine learning techniques to extract linguistic knowledge from natural language data automatically. Supervised learning for WSD requires large amounts of labelled training data which consist sense-annotated instances for a specific word to construct a classifier. Then, the obtained classifier is used to identify the appropriate sense for new examples. A typical method for this approach is the classical Bag-Of-Words (BOW) approach, where each document is represented as a feature vector counting the number of occurrences of different words as features [9]. By using such features, it becomes easy to adapt many existing supervised learning methods such as Support Vector Machine (SVM) for the WSD task. However, when the general vector space model, in which a document is represented as a vector using term frequency based weighting methods, is applied to the WSD, the local context words are typically used as features and the global co-occurrence information without dictionary information is not employed in the previous research [1].

In this paper, I propose a novel WSD method based on the global co-occurrence information using Non-Negative Matrix Factorization (NMF). Previous study proposes a novel WSD method of particular word instances using the automatically extracted sense information [5]. When I calculate the dependency relation matrix, the existing method tends to produce very sparse cooccurrence matrix from a small training set. Therefore, the NMF algorithm sometimes does not converge to desired solutions. To avoid this problem and to obtain more effective co-occurrence relations, I propose to use co-occurrence frequencies of dependency relations between word features in the large document set. This enables us to solve data sparseness problem and induce more effective latent features.

The organization of residual of the paper is as follows. Related works Section is devoted to the introduction of the related work in the literature. Wsd Using Global Co-Occurrence Information Section describes the proposed WSD system based on global cooccurrence information using Non-negative Matrix Factorization. In Experiment Section, I describe an outline of experiments. Experimental results and discussions are presented in Experimental Results and Discussions Section. Finally, Conclusion Section concludes this paper.

WSD is the process for identification of appropriate meaning of polysemous words for a particular context. This process is based on the distributional hypothesis that words that occur in the same context tend to have similar meaning [3]. Thus, many approaches to WSD have focused on the contexts formed by the words surrounding the target polysemous word. By using a set of features that represent the contexts of the target word (various combinations of collocations and bag-of-words, etc.), the extracted features are represented in a multidimensional feature vector.

The feature vector such as a bag-of-words model is a simple but effective representation used in natural language processing. This feature space model represents words in a vector space where words that are close in meaning are mapped to nearby points. Latent Semantic Analysis (LSA) is one of the most popular techniques to transform the original feature space to a semantic space of low dimensionality by analysing relationships between a set of documents and the words they contain [2]. In this paper, I employ the modified Non-Negative Matrix Factorization approach to find a low dimensional semantic space.

The proposed method presents a novel approach to capture global co-occurrence information as well as local information for WSD. The local context is a window of words that occur around the target polysemous word in the sentence and includes information about word order, collocation and syntactic structure [4]. The earliest use of local context for WSD was proposed by Lin [7]. This method uses syntactic dependencies to resolve word sense ambiguity.

A WSD system is used to select the appropriate sense for a target polysemous word in context. WSD can be viewed as a classification task in which each target word should be classified into one of the predefined existing senses. In this paper, supervised classification is employed for this WSD task. This supervised method requires a corpus of manually labelled training data to construct classifiers for every polysemous word. Then, each obtained classifier is applied to a set of unlabeled examples.

Non-Negative Matrix Factorization (NMF) is a popular decomposition method for multivariate data [4]. NMF decomposes the m x n non-negative matrix X to the m x k matrix W and the k x n matrix H, while these matrixes have no negative elements. Usually, k is chosen to be smaller value than n and m. $$X\approx WH\text{ (1)}$$ Using the NMF for a term-document matrix X, the matrix H represents the induced result with k topics.

For quantifying the quality of this approximation, cost functions based on Kullback-Leibler divergence is used and minimized using iterative update rules as follows: $$W_{ij}\leftarrow W_{ij}\frac{{\left(XH\right)}_{ij}}{{\left(WH{H}^T\right)}_{ij}}\text{ (2)}$$ $$H_{ij}\leftarrow H_{ij}\frac{{\left(X^{T}H\right)}_{ij}}{{\left(H{W}^{T}W\right)}_{ij}}\text{ (3)}$$ Where W_ij and H_ij indicate the i-th row and the j-th column element respectively. These matrices W and H are initialized randomly with non-negative data and these above update rules are iteratively applied until the max iteration number (or convergence) is reached.

In previous research, proposes a WSD method of particular word instances using the automatically extracted sense information [3]. This method induces latent features for three matrices. The first n×t matrix A, where n is the number of examples that contain the target word and t is the number of words that have dependency relation with the target word, contains co-occurrence frequencies of the target word cross-classified by dependency relations. The second n×s matrix B, where s is the number of words that appear in the context window, contains term frequencies of words that appear in the context window. The third s×t matrix C contains co-occurrence frequencies of words that the co-occurring context words of the target word co-occur with. Then, NMF is applied to the three matrices to factorize each matrix into two nonnegative matrices, while the former results are used to initialize the next factorization, as shown in Figure 1. By inducing these latent factors such as dependency relations of words, context words and co-occurrence frequencies, this method obtains rich context information of the target word in comparison to co-occurrence matrix from training examples used in general WSD methods.

Given a non-negative matrices A, B and C in the beginning of this method, matrices W, H, G and F are initialized randomly with non-negative values. Then, it decomposes the matrix A into the two matrices $W_{n\times k}$ and $H_{k\times t}$ using NMF such that $$A\approx W_{n\times k}{H}_{k\times t}\text{ (4)}$$ Where k is the number of topics, $W_{n\times k}$ is the n×k word-topic matrix and $H_{k\times t}$ is the k×t topic-word matrix. In the decomposition of the matrix B,

the updated matrix W is copied to matrix V and the updated matrices $V_{n\times k}$ and $G_{k\times s}$ is computed using NMF such that $$B\approx V_{n\times k}{G}_{k\times s}\text{ (5)}$$ Where $V_{n\times k}$ is the n×k word-topic matrix and $G_{k\times s}$ is the k×s topic-word matrix. In the decomposition of the matrix C, the transpose of the updated matrix G is copied to matrix U and the updated matrices $U_{s\times k}$ and $F_{k\times t}$ are obtained using NMF such that $$C\approx U_{s\times k}{F}_{k\times t}\text{ (6)}$$