Parsers built from latent-variable grammars give every syntactic category, such as "noun phrase," a handful of hidden sub-types. The sub-types are learned from treebank data by expectation-maximization (EM), an iterative procedure that alternates between guessing the hidden sub-types and re-estimating the grammar's rule probabilities. EM on this problem has many local optima. The strongest pipeline trains in rounds: it splits every sub-type in two, re-runs EM, and merges back the splits that did not help. Each split breaks the symmetry between the two new children by adding a little random noise, and that noise decides which local optimum EM reaches. The field's response has been to live with this: train eight grammars from eight seeds and multiply their predictions together. The ensemble genuinely helps, but it costs eight training runs and eight-fold parsing.
This note proposes replacing the random symmetry-breaking at each split with a spectral one. At the moment a sub-type is split, we look at every place it occurs in the treebank, weighted by how likely the current grammar thinks each occurrence belongs to that sub-type. We then compute the single direction along which what lies inside those constituents co-varies most strongly with the context outside them, and split the sub-type along that direction. This borrows the idea behind spectral initialization in phase retrieval and matrix recovery: a leading eigenvector computed from the data places local search inside a good basin of attraction, the region around a good solution from which local search reliably reaches it. Here we apply that idea at the one step of grammar learning where the randomness actually enters. The claim is that seed variance comes mostly from uninformed splits, not from an irreducibly rugged landscape. If the claim holds, one spectrally split grammar should match the best of many random-seed grammars at a fraction of the cost. It also becomes possible to test directly whether the product-of-grammars gain comes from useful diversity or from averaging out bad splits.
Core Claim
Two lines of work treat spectral methods and EM as mutually exclusive, and neither uses spectral information to guide EM. Latent-Variable PCFGs: Background and Applications and Latent-Variable Synchronous CFGs for Hierarchical Translation estimate all latent parameters in one closed-form step, using a singular value decomposition of inside/outside co-occurrence statistics. They report 55.83 BLEU against EM's 52.93 on the BTEC Chinese–English corpus. The estimates can be negative or unnormalized, and the method replaces EM rather than seeding it. Learning and Inference for Hierarchically Split PCFGs supplies the split-merge procedure we build on, which reaches 91.2% F1 on the Penn Treebank, but its splits are random.
Our claim is specific. For each sub-type $a$ being split, let $\phi$ be a feature vector of the inside subtree and $\psi$ a feature vector of the outside context for an occurrence of $a$. Form the posterior-weighted cross-covariance
$$\Omega_a = \mathbb{E}_a[\phi\,\psi^\top] - \mathbb{E}_a[\phi]\,\mathbb{E}_a[\psi]^\top ,$$
where $\mathbb{E}_a$ averages over occurrences weighted by the current grammar's posterior probability of $a$. The top left and right singular vectors $u, v$ of $\Omega_a$ define a score $s = u^\top(\phi - \bar\phi) + v^\top(\psi - \bar\psi)$ for each occurrence. Each occurrence is softly assigned to the two children in proportion to $\sigma(\beta s)$ and $1-\sigma(\beta s)$, where $\sigma$ is the logistic function and $\beta$ a sharpness constant. The children's rule probabilities are initialized from the resulting expected counts. EM and the usual merge step then proceed unchanged.
The spectral step only produces an initial soft partition, and the parameters are built from nonnegative expected counts, so they are always valid probability distributions. This sidesteps the negativity problem of pure spectral estimation. The prediction is that spectral splitting collapses the seed-to-seed spread in F1 and training likelihood, and lifts a single grammar to roughly the level of the best random seed.
Research Program
The construction reuses standard machinery. We use inside and outside features of the kind already defined for spectral latent-variable grammars: the rule at the node, the child labels, and the head-word cluster for the inside; the parent, grandparent, and sibling labels for the outside. We hash these to a few thousand dimensions and compute $\Omega_a$ from the posteriors that the current EM round already produces. The extra cost per split round is one truncated singular value decomposition per sub-type, which is small next to a round of Inside-Outside. We keep everything else from the split-merge pipeline fixed, including smoothing, merge thresholds, number of rounds, and coarse-to-fine pruning, so that any difference is attributable to the split rule.
The analytic half of the program uses spectral splits as a probe of the landscape. Products of Random Latent Variable Grammars argues that seed variability is a feature: different optima capture complementary phenomena. The optimization view, for example The landscape of empirical risk for nonconvex losses, treats such variability as landing in inferior stationary points. We can separate these views. We measure, across seeds, the training likelihood, the held-out F1, and the pairwise constituent disagreement between grammars. We also measure how much of the eight-grammar product gain survives when the members are spectrally split. For those members, diversity must come from bootstrap resamples of the treebank rather than from noise. If the product gain shrinks sharply once each member is spectrally split, most of the "complementary" diversity was repair of bad splits. If the gain survives, the random optima really do encode distinct, useful structure.
A third strand tests the sample-size intuition from the non-convex literature. Guarantees for spectral starts hold only above a sample threshold, as in the $n \approx 4rd$ transition of A Unified Computational and Statistical Framework for Nonconvex Low-rank Matrix Estimation. Basins also shrink when the problem is ill-conditioned, as Provable accelerated gradient method for nonconvex low rank optimization shows. We therefore expect the spectral split to help most in two situations. One is in later split rounds, where each sub-type has few occurrences. The other is when the treebank is subsampled. We test this by plotting seed variance against training-set fraction and against split round. This will not produce a theorem, since treebank features violate the Gaussian assumptions behind those results. It gives an empirical counterpart to them.
Baselines
The naive reference point is the standard random-split split-merge grammar from Learning and Inference for Hierarchically Split PCFGs. We run it with 16 seeds on the identical preprocessing, binarization, and number of rounds. The file reports 91.2% F1 on the Penn Treebank for that system. The products paper reports its single-grammar baseline at 90.2% on English WSJ and 80.3% on German. These two English numbers presumably reflect different configurations or evaluation sets, so we will reproduce both rather than compare against either quoted figure. Beating this baseline means a higher mean F1 and a clearly smaller seed standard deviation.
The strongest existing method is the unweighted product of eight random grammars from Products of Random Latent Variable Grammars, reported at 91.8% F1 on English WSJ and 84.5% on German. We rebuild it from the same eight seeds used above, with constituent-level inference. We do not expect one spectrally split grammar to beat it outright. The fair comparison is on accuracy per unit of training and parsing compute. Success would be closing at least half the gap between a single grammar and the product at one-eighth the cost. We also compare products of spectrally split members against the random product at equal member count, where a win would be a strict improvement over 91.8.
The cheapest competitor to the core idea is best-of-N random restarts selected by training likelihood. We run it with $N$ chosen so that its total compute matches the spectral method including the singular value decomposition overhead, and also at $N=8$. The spectral split beats it if a single spectral run matches or exceeds the best-of-8 selected grammar.
Pure spectral estimation of the latent-variable grammar, as in Latent-Variable PCFGs: Background and Applications, is the method that avoids EM entirely. No reported result was found on Lacuna for spectral L-PCFG F1 on the Penn Treebank, so we will run it ourselves at matched latent dimension.
Two ablations isolate the key ingredient. The first splits along a random direction, still producing a deterministic soft partition from the same features, which tests whether the spectral direction matters or merely the soft-partition initialization. The second applies the spectral split and then skips EM refinement within each round, which tests whether the benefit lies in the starting point or in the final estimate.
Why not just…?
Why not just ensemble random seeds, since that already works? Because it is the thing we are trying to explain, and it is expensive. The product result shows that seed variance holds real accuracy, but it cannot say whether that accuracy lives in diverse optima or in the variance of bad ones. It also multiplies training and parsing cost by eight. Our comparison of random products and spectral products at equal size settles this. If spectral members gain nothing from being multiplied, the ensemble was mostly correcting splits, and a single spectral grammar is the cheaper route to the same place.
Why not just take the best of several random restarts? This is the real threat, because it is trivially cheap to implement. If best-of-N by likelihood matches spectral splitting at matched compute, the proposal's practical claim fails, and we will report it that way. The one place we expect an advantage is compounding over rounds. A restart selects only the final grammar, while a spectral split informs every one of the five or six rounds. The per-round variance analysis shows whether that compounding actually happens.
Why not just use pure spectral estimation and drop EM? Its parameters can be negative and need ad hoc repair (Latent-Variable PCFGs: Background and Applications). It also cannot perform the adaptive split-merge allocation of sub-types that makes Learning and Inference for Hierarchically Split PCFGs strong. The BTEC result shows spectral beating EM on translation, but in that comparison EM itself was randomly initialized. Our pure-spectral baseline measures the difference on parsing directly.
Why not just convexify, or over-parameterize with neural networks? The convex tree-polytope formulation of A convex and feature-rich discriminative approach to dependency grammar induction eliminates seed dependence for dependency induction, reaching 64.8% average directed accuracy. It works over observed tags, however, and has no mechanism for discovering hidden sub-types. Neural parameterization as in Compound Probabilistic Context-Free Grammars for Grammar Induction is reported to smooth optimization. The grounded variant still loses nine F1 points when the language-modeling objective is removed (Visually Grounded Compound PCFGs), so it does not remove sensitivity. It also targets unsupervised induction rather than refinement of a treebank grammar. Neither replaces the question asked here, although applying spectral splits to neural grammars is a natural follow-up.
Proposed Experiments
The main experiments use the English WSJ Penn Treebank with standard sections and the German treebank used by both Petrov papers. We evaluate on in-domain test sets and on the English Brown corpus to measure out-of-domain transfer. No reported Brown number was found on Lacuna, so all Brown results will be our own reproductions. Each condition runs with 16 seeds. We report the mean and standard deviation of $F_1$ on all sentences and on sentences of 40 words or fewer, the final training log-likelihood, pairwise constituent disagreement across seeds, wall-clock training time, and parsing time.
Three results are decisive. The first is whether the seed standard deviation of spectrally split grammars is less than half that of random splits while the mean F1 is at least as high. The second is whether a single spectral grammar matches the best-of-8 random grammar at roughly one-eighth the compute. The third is whether a product of spectral grammars exceeds the 91.8 English and 84.5 German products at equal member count, or instead shows a vanishing product gain. Either outcome answers the "feature or bug" question about seed variability. The training-fraction sweep at 10%, 25%, 50%, and 100% of the WSJ training set tests the predicted pattern that the spectral advantage grows as data per sub-type shrinks. If the advantage instead disappears at small data, sparse co-occurrence estimates are corrupting the spectral direction. In that case the natural fix is the trimmed statistics used by Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems and Provable Non-convex Phase Retrieval with Outliers: Median TruncatedWirtinger Flow, which we would test as a final variant.
References
- Latent-Variable PCFGs: Background and Applications
- Latent-Variable Synchronous CFGs for Hierarchical Translation
- Learning and Inference for Hierarchically Split PCFGs
- Products of Random Latent Variable Grammars
- The landscape of empirical risk for nonconvex losses
- A Unified Computational and Statistical Framework for Nonconvex Low-rank Matrix Estimation
- Provable accelerated gradient method for nonconvex low rank optimization
- A convex and feature-rich discriminative approach to dependency grammar induction
- Compound Probabilistic Context-Free Grammars for Grammar Induction
- Visually Grounded Compound PCFGs
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
- Provable Non-convex Phase Retrieval with Outliers: Median TruncatedWirtinger Flow