Wikispeedia: An Online Game for Inferring Semantic Distances between Concepts

Robert West, Joelle Pineau, Doina PrecupIJCAI 2009 · OpenReview

Abstract

Computing the semantic distance between real-world concepts is a fundamental challenge for intelligent systems. Traditional corpus-based methods often struggle to capture the nuance of human "common sense." We present a novel method that leverages data from Wikispeedia, an online game where players navigate from one Wikipedia article to another using only internal hyperlinks. By applying an information-theoretic approach to human click-streams, we extract semantic relationships that are more cognitively grounded than those found by purely automated methods. Our results show that this approach significantly outperforms Latent Semantic Analysis (LSA) in psychometric evaluations.

The Challenge of Semantic Distance

Quantifying how "related" two concepts are—semantic distance—is essential for tasks ranging from information retrieval to natural language processing. While Wikipedia provides a massive graph of human knowledge, its raw structure is difficult to use for distance measurement due to the "small world" phenomenon. In Wikipedia, the average distance between any two articles is only 4.6 links. For instance, both "Baseball" and "Archimedes" are two clicks away from "Carl Friedrich Gauss," yet only one is truly semantically relevant. Automated methods often fail to distinguish between a link added for navigational convenience and one representing a deep conceptual connection.

Methodology: Games with a Purpose

To solve this, the researchers utilized a "Game with a Purpose" (GWAP) called Wikispeedia. Players are given a starting article and a goal article and must reach the goal using only internal hyperlinks. This setup forces players to rely on their internal semantic map of the world to find a path.

The Information-Theoretic Measure

The core technical contribution is a semantic distance measure based on information theory:

  1. Click Probabilities: The model calculates the probability of a player choosing a specific link given their current location and ultimate goal.
  2. Path-Specific Distance: The "information content" of a path is measured by how many bits are required to encode the human's choice of links.
  3. PageRank Normalization: To prevent popular articles (like "United States") from skewing results, distances are normalized using the goal article's Google PageRank.
  4. The "Homing-In" Filter: Human navigation typically occurs in two phases: an initial "getting away" phase (moving toward general hubs) and a "homing in" phase (narrowing down to the goal). The authors used a neural network to identify this split point, focusing only on the semantically rich "homing in" data.

Analysis of Human Navigation

A key insight of the study is the discrepancy between mathematical shortest paths and human intuitive paths. While a computer can find the most direct link-to-link route, humans rely on semantic associations, leading to paths that are consistently longer but more meaningful.

Figure 1: Comparison of human path lengths (black) versus mathematical shortest paths (grey). Human paths are consistently longer, reflecting a reliance on semantic associations rather than exhaustive graph search.

This behavior highlights that human paths are not just "suboptimal" searches; they are reflections of how we relate ideas. Furthermore, the authors found that semantic distance is often asymmetric. For example, "Minneapolis" strongly triggers an association with "Minnesota," but "Minnesota" might more likely trigger "Lakes" or "St. Paul." The Wikispeedia measure preserves this psychological asymmetry, which traditional geometric models often ignore.

Evaluation and Results

The method was evaluated against Latent Semantic Analysis (LSA) using Amazon Mechanical Turk. Human raters were asked to choose which method provided more relevant "semantic neighbors" for a given concept.

Figure 4: Human preference results comparing Wikispeedia to LSA. Wikispeedia was preferred in over 64% of cases.

Wikispeedia significantly outperformed LSA, particularly in handling polysemy. For the concept "AIDS," LSA (which is word-based) became confused by the plural of "aid" (helper), suggesting neighbors like "Speaker" and "Listener." In contrast, Wikispeedia correctly identified "HIV," "Africa," and "World Health Organization" based on the paths players took to reach the article.

Conclusion

By treating human click-streams as a proxy for common sense, Wikispeedia provides a scalable and cognitively plausible way to map the web of human concepts. While currently limited by the sparsity of game traces, future work involving dimensionality reduction could allow the system to infer distances for concept pairs that have not yet been played. This research demonstrates that the "wisdom of the crowd," when captured through structured play, can surpass sophisticated corpus-based algorithms in understanding human meaning.

Summary updated

Abstract

Computing the semantic distance between realworld concepts is crucial for many intelligent applications. We present a novel method that leverages data from 'Wikispeedia', an online game played on Wikipedia; players have to reach an article from another, unrelated article, only by clicking links in the articles encountered. In order to automatically infer semantic distances between everyday concepts, our method effectively extracts the common sense displayed by humans during play, and is thus more desirable, from a cognitive point of view, than purely corpus-based methods. We show that our method significantly outperforms Latent Semantic Analysis in a psychometric evaluation of the quality of learned semantic distances.
BibTeX
@inproceedings{west2009wikispeedia,
  author = {Robert West and Joelle Pineau and Doina Precup},
  title = {{Wikispeedia: An Online Game for Inferring Semantic Distances between Concepts}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=rk-HJVG_-H},
}
Figure