TL;DR
This paper investigates the Strahler number, a measure of tree complexity originally from river networks, and applies it to natural language sentence structures. They find that sentence trees have a Strahler number similar to random trees, suggesting this complexity measure is not unique to human language and might explain the "magical number" of 3-5 often observed in cognitive psychology and NLP parsing.
What Problem Does This Paper Address?
The Strahler number, a metric for characterizing the complexity of branching structures, was famously found to be a constant 4 for rivers in England. This paper explores whether this number holds true for natural language sentence structures and, more importantly, why certain cognitive and computational processes related to language seem to hover around a "magical number" of 3-5. Previous work has observed this number in short-term memory capacity and the number of memory areas required for parsing, but lacked a theoretical explanation. The authors aim to bridge this gap by analyzing the Strahler number of sentence trees and comparing it to random tree structures.
Methods
The core of the paper involves:
- Defining and Computing Strahler Numbers: The authors provide a clear definition of the Strahler number for binary trees and extend it to dependency trees by using binarization methods.
- Binarization of Dependency Trees: Two methods are proposed to convert dependency trees (where words are nodes and relationships are edges) into binary trees:
- Binary1: Uses a manually crafted grammar to guide the binarization.
- Binary2: Employs heuristics based on modifier distance from the head word.
- Calculating Upper and Lower Limits: For any given tree, they devise methods to compute the maximum and minimum possible Strahler numbers across all binarization strategies.
- Theoretical Analysis of Random Trees: They analytically derive the mean, upper, and lower bounds of the Strahler number for random binary trees.
- Empirical Analysis: They compute these metrics for natural language sentence trees from a large dataset and compare them to the theoretical results for random trees.
Datasets
The primary dataset used is the Universal Dependencies (UD) dataset, version 2.8. This is a large-scale, multilingual corpus containing grammatically annotated sentences across 114 languages. The authors specifically utilize the dependency structure representations from this dataset.
Key Insights and Ideas
- Strahler Number as a Memory Lower Bound: The paper establishes a theoretical link between the Strahler number and the minimum memory required for processing tree structures, particularly through the shift-reduce parsing method. This provides a computational basis for the observed "magical number" in NLP.
- Logarithmic Growth, Not Constant: Contrary to the river bifurcation finding, the Strahler number for sentences is shown to grow logarithmically with sentence length (tree size), rather than being a fixed value. The apparent constancy in previous observations is attributed to the limited range of sentence lengths.
- Natural Language vs. Random Trees: A crucial finding is that the Strahler number of natural language sentence trees is statistically indistinguishable from that of random trees of similar size. This suggests that the complexity observed is not inherently tied to the linguistic nature of sentences but rather to the general properties of tree structures.
- "Magical Number" Explained: The consistent appearance of 3-5 in cognitive and NLP studies is explained by the Strahler number's logarithmic growth. For typical sentence lengths, the lower bound of the Strahler number falls within this range, suggesting it represents a fundamental constraint on processing complexity.
Key Results
- The average Strahler number for natural language sentences is found to be around 3 or 4.
- The Strahler number grows logarithmically with the size (number of nodes) of the sentence tree.
- The upper and lower limits of the Strahler number for natural language sentence trees are close to those of random trees of the same size.
- The distribution of Strahler numbers for natural language sentences shows a median of 4 for the upper limit and 3 for all other cases, with numbers larger than 4 being scarce.
- The paper demonstrates that the Strahler number is independent of compression rate, suggesting it captures a different aspect of complexity than sequence-based measures like Shannon entropy.
Limitations and Future Work
- Binarization Dependence: The Strahler number calculation for dependency trees relies on binarization methods, and while the paper shows similar results for two methods, the choice of binarization can influence the exact values. The authors acknowledge that the upper and lower limits are calculated while ignoring word order and non-intersection constraints, which might be a simplification.
- Shift-Reduce Setting: The connection to memory requirements is specifically tied to the shift-reduce evaluation method. While this is a fundamental parsing technique, it might not encompass all aspects of sentence processing.
- Future Work: The authors suggest that their findings provide a theoretical grounding for the "magical number" observed in psychology and NLP. They predict that the lower limit of memory necessary for parsing also grows logarithmically, and that the observed 3-4 range is a consequence of typical sentence lengths. Further research could explore this logarithmic growth in parsing techniques and investigate if the "magical number" is indeed a general property of tree structures beyond natural language.
Summary updated