Abstract
Automatically identifying the polarity of words is a critical task in Natural Language Processing (NLP) with applications ranging from sentiment analysis of product reviews to mining online discussions. We propose a method for identifying word polarity by applying a Markov random walk model to a large word relatedness graph. This approach produces polarity estimates for any given word quickly and accurately. A key advantage of the model is its versatility; it can be used in both a semi-supervised setting with a labeled training set and an unsupervised setting using a handful of seed words. Experimental results on a manually labeled set of positive and negative words demonstrate that our method outperforms state-of-the-art techniques in semi-supervised settings and remains competitive in unsupervised scenarios without requiring massive corpora.
Introduction
In the field of sentiment analysis, determining whether a word carries a positive or negative connotation is a foundational challenge. Existing methodologies generally fall into two categories: corpus-heavy statistical methods and graph-based lexical methods. Corpus-heavy approaches, such as SO-PMI, often require massive datasets—sometimes exceeding 100 billion words—and thousands of search engine queries to calculate associations. Conversely, traditional graph-based methods, like shortest-path algorithms, often struggle with "noise" in lexical databases where antonyms (e.g., "good" and "bad") may appear close together due to shared contexts.
This paper introduces a graph-based approach that leverages Markov random walks to navigate these complexities. By measuring the "hitting time"—the time it takes a random walker to travel from an unknown word to a set of labeled "seed" words—we achieve high accuracy without the computational burden of web-scale corpus analysis.
Methodology
The core of our approach is the construction of a word relatedness graph and the application of a random walk model.
Graph Construction
We build a network where nodes represent word/part-of-speech pairs (e.g., "fine" as an adjective vs. "fine" as a noun). Edges are established based on WordNet relations, primarily synonyms and hypernyms, to capture semantic proximity.
The Random Walk Model
To determine the polarity of an unlabeled word, we simulate a random walker starting at that node. The walk continues until the surfer hits a "seed" word with a known polarity. We calculate the "mean first-passage time" (hitting time) for both positive and negative seed sets. If a word is positive, the walker should, on average, reach a positive seed significantly faster than a negative one.
Optimization and Estimation
Because exact hitting times on large graphs are computationally expensive, we employ a Monte Carlo simulation. We run $k$ independent random walks from each word and average the results. Furthermore, we found that limiting the maximum number of steps ($m$) in a walk improves accuracy. As shown in Figure 1, accuracy peaks when $m$ is restricted, preventing "lost" walkers from hitting incorrect seeds and introducing noise into the sentiment estimate.
Experimental Results
We evaluated our method using the General Inquirer Lexicon (4,206 words) as a gold standard and WordNet for graph construction.
Performance Metrics
In a semi-supervised setting using 10-fold cross-validation (CV), the random walk method achieved an overall accuracy of 93.1%, surpassing the previous state-of-the-art "Spin" model (91.5%). In the unsupervised setting, using only 14 seed words, the method reached 82.1% accuracy. This performance is comparable to corpus-based methods like SO-PMI (82.8%) but is achieved significantly faster and without the need for a 100-billion-word dataset.
As illustrated in Figure 4, the model maintains high performance across various parts of speech, including adjectives, nouns, and verbs. The semi-supervised (CV) approach consistently yields the highest accuracy, while the unsupervised seed-based approach remains robust, particularly for adjectives.
Conclusion
The Markov random walk model provides a fast, efficient, and accurate framework for identifying word polarity. By considering all possible paths in a lexical graph rather than just the shortest one, the model effectively filters out the noise inherent in dictionary-based networks. Future work will focus on addressing word sense ambiguity (polysemy) and exploring hybrid models that combine structured lexical knowledge with co-occurrence statistics from smaller, specialized corpora.
Summary updated