Semantic Classification with WordNet Kernels

Diarmuid Ó SéaghdhaNAACL 2009

TL;DR

This paper introduces novel "kernel functions" derived from the structure of WordNet, a lexical database, to perform semantic classification tasks. These graph-based kernels achieve competitive performance against more complex systems on a challenging relation classification benchmark, demonstrating the power of leveraging semantic hierarchies for machine learning.

What Problem Does This Paper Address?

Estimating semantic similarity between words is a fundamental challenge in Natural Language Processing (NLP). Traditional approaches fall into two main categories: distributional similarity (based on word co-occurrence in text) and semantic network similarity (based on word positions in structured knowledge bases like WordNet). While distributional methods have seen recent success with kernel methods, the potential of using semantic network similarity, specifically WordNet's hierarchical structure, within a kernel framework for supervised classification tasks remained less explored. This paper aims to bridge this gap by developing and evaluating WordNet-based kernels for semantic classification.

Methods

The core of this paper lies in deriving kernel functions from the WordNet graph structure. The authors focus on spectral graph theory, specifically using properties of the graph Laplacian. They explore two main types of kernels:

  • Laplacian Pseudoinverse Kernels (L+ and L+): These kernels are derived from the pseudoinverse of the graph Laplacian (and its normalized version). The entries of these matrices are related to "resistance distances" and "average commute times" in an electrical circuit analogy, capturing not just direct connections but also the overall connectivity of the graph.
  • Diffusion Kernels (Ht): These kernels are inspired by heat diffusion or the distribution of a lazy random walk on the graph. They are defined using the eigenvalues and eigenvectors of the Laplacian.

A significant methodological challenge is the computational cost of calculating these kernels for large graphs like WordNet. The authors address this by computing the Laplacian pseudoinverse column by column and using approximations for the diffusion kernel based on a limited number of spectral components.

Datasets

The primary dataset used for evaluation is the SemEval Task 4 relation classification dataset. This dataset consists of candidate sentences for seven two-argument semantic relations, with annotated WordNet senses for the relation arguments. It includes 140 training sentences and approximately 80 test sentences per relation. The authors note that this dataset is particularly suitable because it provides explicit WordNet sense annotations, which directly align with their kernel approach.

Key Insights and Ideas

  • WordNet's structure is a powerful feature: The paper demonstrates that the hierarchical relationships within WordNet can be effectively translated into a kernel function, capturing semantic similarity without relying solely on textual co-occurrence.
  • Spectral graph theory for semantic similarity: Using spectral properties of the graph Laplacian (like resistance distance and diffusion) provides a principled way to quantify similarity between nodes (synsets) in the WordNet hierarchy.
  • Computational efficiency is achievable: Despite the potential for dense and memory-intensive kernel matrices, the authors show that efficient computation is possible through targeted calculations and approximations, making these methods practical.
  • Kernelized semantic network similarity is competitive: The WordNet kernels perform surprisingly well, often outperforming more complex systems that utilize richer feature sets.

Key Results

The paper reports macro-averaged accuracy and F-scores on the SemEval Task 4 dataset. The results show that:

  • The Laplacian pseudoinverse kernels (L+ and L+) consistently outperform a baseline kernel (B) that represents words as binary feature vectors.
  • The best performance is achieved by the L+ kernel approximation using 1,000 eigencomponents.
  • The heat kernel (Ht) fares less well, possibly due to the difficulty in identifying the optimal parameter t.
  • Compared to other SemEval participants, the WordNet-based lexical similarity model performs very well, achieving higher accuracy than all but one system and higher F-score than all but three, despite using only graph structure and not sentence context features.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • Sense-centric vs. Word-centric: The current kernels are defined on WordNet senses (synsets), not directly on words. This means a word with multiple senses requires special handling.
  • Simplified graph structure: The current approach uses only hyponymy and instance hyponymy relations, creating a relatively "impoverished" tree-like structure.
  • Future Directions:
    • Word Kernels: Extend sense-kernels to word-kernels by adding word nodes to the graph, linking each word to its senses.
  • Broader Relation Incorporation: Include other WordNet relations like meronymy and topicality to capture richer semantic associations, potentially for tasks like spelling correction.
  • Augmented Graphs: Combine WordNet graphs with information from other sources, such as corpus-derived similarity links, or apply these kernel functions to graphs derived from parsed corpora.

Summary updated

BibTeX
@inproceedings{seaghdha2009semantic,
  author = {Diarmuid Ó Séaghdha},
  title = {{Semantic Classification with WordNet Kernels}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure