On the feasibility of dependency parsing of non-human sequences without a gold standard. Is evaluation possible in other species?
By Ramon Ferrer-i-Cancho, Catherine Hobaiter, Thore Bergman, Morgan Gustison
"Paper shows that for non-human primate vocalizations, fast sequence length decay enables unsupervised parser evaluation without gold standard, unlike human languages."
Abstract
Dependency parsing consists of finding a tree representation for a sequence. Unsupervised dependency parsing aims to develop parsing methods without a gold standard during model training. In human languages, an unsupervised parser can be evaluated because some gold standard is usually available or can be created. For other species, a gold standard is unknown. Thus one may conclude that it is impossible to determine the accuracy of an unsupervised parser and, consequently, dependency parsing is unfeasible in other species. However, here we apply recent advances in network science to demonstrate that the proportion of correct edges retrieved by a parser must be high for the sequences of vocalizations or gestures that non-human primates produce due to the fast decay of the sequence length distribution. In contrast, human language sequences lack that property. Therefore, evaluation without a gold standard is feasible in non-human primates but a hard problem in humans.
Technical Analysis & Implementation
Summary§
This paper tackles the problem of evaluating unsupervised dependency parsers for non-human primate vocalizations and gestures. Without a gold standard, typical evaluation is impossible, but the authors leverage network science to show that the fast decay of sequence length distributions in non-human communication guarantees a high proportion of correct edges, making evaluation feasible. In contrast, human language sequences do not exhibit this property.
Core Methodology§
Unsupervised Dependency Parsing§
Dependency parsing assigns a dependency tree to a sequence of tokens, where edges represent syntactic relations. Unsupervised parsers learn without labeled data, typically using probabilistic models like DMV (Klein & Manning, 2004) or graph-based methods. Evaluation usually requires a gold standard treebank (e.g., UD).
Network Science Framework§
The authors propose to model sequences as random graphs where nodes are tokens and edges are dependency relations. They analyze the probability that an edge is correct by considering the sequence length distribution $P(L)$. For non-human primates, $P(L)$ decays rapidly (e.g., power-law or exponential). They prove that under such decay, any reasonably good unsupervised parser must retrieve a high proportion of correct edges, because the expected number of incorrectly placed edges grows slower than total edges.
Theoretical Result§
Let $L$ be sequence length. For a random parser, each edge is correct with probability $1/(L-1)$ (since among $L-1$ possible heads). The expected number of correct edges is $1$ per sequence, independent of $L$. For a parser with some signal, correct edges scale linearly with $L$. If $P(L)$ decays fast, short sequences dominate the corpus, and a parser that works well on short sequences will achieve high overall accuracy. Formally, if $P(L) \propto L^{-\gamma}$ with $\gamma>2$, then the fraction of correct edges converges to 1 as corpus size grows. For human languages, $P(L)$ decays slowly (e.g., log-normal), allowing low accuracy to persist.
Implementation Details§
Parsing Model§
They use a simple unsupervised dependency parser based on a nearest-neighbor heuristic: each token attaches to its closest neighbor (in terms of position) to the left or right, optionally with a direction bias. This model is trained on sequences of vocalizations from macaques and chimpanzees.
Evaluation Procedure§
Without a gold standard, they cannot compute direct accuracy. Instead, they compare the parser's output to random baselines and compute edge overlap metrics (e.g., Rand index). They also simulate sequence length distributions from empirical data and compute theoretical bounds.
Code Snippet (Illustrative Python)§
import numpy as np
from collections import Counter
def simulate_decay(lengths, parser, correct_rate_fn):
correct = []
total = []
for L in lengths:
# parser returns adjacency matrix
edges = parser(np.random.rand(L, d)) # dummy features
# correct_rate_fn gives probability each edge is correct
p = correct_rate_fn(L)
correct.append(sum(np.random.rand(len(edges)) < p))
total.append(len(edges))
return sum(correct)/sum(total)
def length_distribution(data):
return Counter(len(seq) for seq in data)
# Usage:
# lengths = [len(seq) for seq in nonhuman_vocalizations]
# acc = simulate_decay(lengths, my_parser, lambda L: 1/(L-1))Key Equations§
Expected number of edges in a corpus: $E_{\text{total}} = \sum_L P(L) \cdot (L-1)$.
Correct edges: $E_{\text{correct}} = \sum_L P(L) \cdot (L-1) \cdot p(L)$, where $p(L)$ is per-edge correctness probability.
For a perfect parser on short sequences ($p(L)=1$) and random on long ($p(L)=1/(L-1)$), the fraction $f = E_{\text{correct}} / E_{\text{total}}$ depends on $P(L)$. If $P(L)$ decays as $L^{-\alpha}$ with $\alpha>2$, $f \to 1$ as corpus grows.
Conclusion§
The paper provides a theoretical and empirical justification for evaluating unsupervised dependency parsers in non-human species without gold standards. This opens the door to analyzing animal communication structures with NLP tools.