Abstract
Traditional edge-counting methods for measuring semantic similarity in taxonomic ontologies often fail to account for non-uniform concept densities. This paper proposes a novel path computing model based on local area density compensation. By adjusting the shortest path length between concepts using the number of direct hyponyms of their subsumers, the model addresses the non-uniformity problem inherent in large taxonomies like WordNet. Experimental results demonstrate that this model significantly improves the correlation with human judgments on the Miller and Charles (MC30) benchmark, increasing average correlation from below 0.8 to over 0.85. Furthermore, the model offers substantial efficiency advantages over Information Content (IC) methods, particularly in dynamic ontologies.
Introduction
In Natural Language Processing (NLP), determining the semantic similarity between concepts is a fundamental task. Taxonomic ontologies, such as WordNet, provide a structured hierarchy where the distance between nodes (concepts) can be used to estimate similarity. Historically, the "shortest path" or edge-counting method has been the default approach due to its simplicity and low computational cost.
However, large-scale taxonomies are rarely uniform. Some domains are modeled with high granularity (dense clusters), while others are sparse. A single edge in a dense region represents a smaller semantic difference than an edge in a sparse region. While Information Content (IC) methods address this by incorporating corpus-based statistics, they are computationally expensive and difficult to maintain in dynamic environments where the ontology updates frequently.
The Density Compensation Model
This research advocates for separating path computation from similarity algorithms, allowing for modular "path models" that can be plugged into various existing measures. The proposed model introduces a "density compensation" factor based on the local structure of the taxonomy.
The core formula for the compensated path is:
$$Path_{density} = |Edges| + \left( \frac{LocalAreaDensity}{AverageDepth} \right) \times \lambda$$
- Edges: The raw count of steps between concepts.
- Local Area Density: Calculated as the number of direct hyponyms (children) of the subsumers along the shortest path. This measures how "branchy" the local neighborhood is.
- Average Depth: The depth of the concepts' common ancestor, reflecting that semantic distance decreases as concepts become more specific (deeper in the tree).
- $\\lambda$ (Lambda): A tuning parameter (typically 0.3) that balances the influence of density compensation.
This approach aligns with information theory: as local density increases, the semantic "weight" of an edge changes, and as depth increases, the specificity of concepts reduces the relative impact of that density.
Experimental Evaluation
The model was evaluated using WordNet 3.0 against two primary benchmarks: the Miller and Charles (MC30) set and the Rubenstein and Goodenough (RG65) set. The researchers compared standard edge-counting versions of popular similarity measures (e.g., Rada et al., Leacock et al., Wu et al.) against versions using the proposed density-compensated path.
As shown in the experimental data above, the "Edge weight-based" model consistently improves correlation coefficients across nearly all tested measures. On the MC30 benchmark, the model helped push average correlation scores from the 0.75–0.80 range to over 0.85, nearing the human-to-human agreement threshold of 0.90.
Efficiency in Dynamic Ontologies
A critical advantage of this model is its performance in dynamic ontologies like DBpedia. Unlike IC-based methods that require a global "pretreatment" of the entire taxonomy—a process that can take hundreds of seconds—the density compensation model only requires local information. In tests, the proposed model was dozens of times faster, requiring zero pretreatment time while maintaining high accuracy.
Conclusion
The density compensation-based path model successfully bridges the gap between simple edge-counting and complex information-theoretic methods. By accounting for the "branchiness" of local taxonomic structures, it provides a high-accuracy, high-efficiency solution for semantic similarity tasks, particularly suited for modern, rapidly evolving knowledge bases.
Summary updated