Strength in Numbers: Averaging and Clustering Effects in Mixture of Experts for Graph-Based Dependency Parsing (2021)

Abstract: We review two features of mixture of experts (MoE) models which we call averaging and clustering effects in the context of graph-based dependency parsers learned in a supervised probabilistic framework. Averaging corresponds to the ensemble combination of parsers and is responsible for variance reduction which helps stabilizing and improving parsing accuracy. Clustering describes the capacity of MoE models to give more credit to experts believed to be more accurate given an input. Although promising, this is difficult to achieve, especially without additional data. We design an experimental set-up to study the impact of these effects. Whereas averaging is always beneficial, clustering requires good initialization and stabilization techniques, but its advantages over mere averaging seem to eventually vanish when enough experts are present. As a by product, we show how this leads to state-of-the-art results on the PTB and the CoNLL09 Chinese treebank, with low variance across experiments.

## introduction combinations of elementary parsers are known to improve accuracy. sometimes called joint systems, they often use different representations, i.e. lexicalized constituents and dependencies @xcite @xcite . these approaches have been devised to join the strengths and overcome the weaknesses of elementary systems. in this work, however, we follow another line of research consisting of mixtures and products of similar experts @xcite , instantiated for parsing in @xcite and especially appealing when individual experts have high variance, typically when training involves neural networks. indeed @xcite used products of experts trained via expectation-maximization (a non-convex function minimization) converging to local minima. in this work we propose to study the combination of parsers, from a probabilistic point of view, as a mixture model, i.e. a learnable convex interpolation of probabilities. this has previously been studied in @xcite for pcfgs with the goal of overcoming the locality assumptions, and we want to see if neural graph-based dependency parsers, with non-markovian feature extractors, can also benefit from this framework. it has several advantages: it is conceptually simple and easy to implement, it is not restricted to projective dependency parsing (although we only experiment this case), and while the time and space complexity increases with the number of systems, this is hardly a problem in practice thanks to gpu parallelization. simple averaging models, or ensembles, can also be framed as mixture models where mixture coefficients are equal. we are able to quantify the variance reduction, both theoretically and empirically and show that this simple model of graph-based parser combinations perform better on average, and achieve a higher accuracy than single systems. while the full mixture model is appealing, since it could in principle both decrease variance and find the optimal interpolation weights to better combine parser predictions, the non-convexity of the learning objective is a major issue that, when added to the non-convexity of potential functions, can prevent parameterization to converge to a good solution. by trying to specialize parsers to specific input, the variance is not decreased. more importantly, experiments indicate that useful data, that is data with an effect on parameterization, becomes too scarce to train the clustering device. another drawback of finite mixture models is that inference, i.e. finding the optimal tree, becomes intractable. we tackle this issue by using an alternative objective similar to minimal bayes-risk @xcite and pcfg-la combination @xcite for which decoding is exact. our contribution can be summarized as follows: ## averaging and variance reduction in this section we assume all experts to be equally weighted. we define the variance of the system on t as the average variance of marginal arc probability: we show how the variance of the moe is smaller than the variance of experts. we focus on structure prediction p(y|x), but definitions are applicable to the labelling model as well. this is an already known result for mixture models in general, but the proof is here instantiated for a mixture of graphbased parsers. moreover, we will recover this result experimentally in section 6. assuming we have a mixture of k elementary systems, we will estimate the marginal probability variance with: with π(k) the probability p k (h, d)|x given by the k th elementary system and average π = 1 k k @xmath0. to see this, we assume that the marginal probability for a well trained expert, over a fixed sentence and a fixed arc, is a measurable function f (h,d),x : @xmath1, which represents the fact that p k is the result of a learning process with many sources of randomization 2 (initialization, stochastic batches, dropout. . . ): with s @xmath2, assumed to be independent for different experts. since in practice a pseudo-random generator is used, the value of marginal probability for particular sentence and arc is deterministic when the random seed is fixed. thus, it is sufficient to use a deterministic function to represent p k ((h, d), x), with random seed s k as input. moreover, we just need the function to be measurable. we can now view f (h,d),x (s) as a random variable and we note its variance as σ 2 (h,d),x . it is in fact the variance of the marginal arc probability given by this expert, for (h, d) given x. for an averaging moe, the marginal probability becomes: with k number of experts in the mixture model. if random variables {s k } @xmath3, {f (h,d),x ((s k )} @xmath4. thus, the variance of the mixture model for particular sentence and arc should be 1 k times the variance of experts: with σ the variance of the mixture model. in other words, the log-variance of a mixture model decreases linearly with log k, with slope -1, i.e.: experiments in section 6 figure 1 show that the estimated log-variance of the averaging system decreases when the number of experts increases and that this relation is close to linear with a slope approaching -1, comforting our independence assumption. ## training with clustering when mixture weights are adjustable, moe models are able to give more credit to experts believed to perform better on specific input. this can be exploited during parameterization. the role of ω is thus to learn how to cluster input into k categories, each category being assigned to an expert. 3 for input sentence x and corresponding tree y, assuming parameterization is performed by maximizing the log-likelihood of the training set via sgd, the objective of mixture model learning with gating network ω can be written as: one may think that the degeneration problem can be alleviated with a smoothing prior or regularization. in practice, we tried entropy as regularization to force towards a uniform distribution on ω k . we found that a heavy entropy penalization is required to avoid the degeneration problem, which makes ω k too uniform to be an accurate clustering device. avoid extreme partition thus, to alleviate the degeneration problem without forcing a strong smoothing constraint, we propose to modify eq. ( 6 ) into: for an example where p k (x) is close to uniform, we can benefit from the averaging effect, while for an example which shows strong preference for a particular expert, we can also learn the partition coefficients proportional to their correctness. stabilize training neuron dropout @xcite is a common technique to avoid overfitting which unfortunately proved difficult in this setting. the problem is that s k (x, y) gives very different results with or without dropout which reflects on p k (y|x) causing drastic changes from one evaluation to the other. to mitigate this problem, we use probabilities without dropout (noted as pk (θ)) to calculate the weighted coefficients of gradient. the final optimization process can be separated into two alternate parts, (i) optimization of the gating parameters: in practice, this permitted reaching a lower loss value after training. experts we run tests with first-order (fop) and second-order parsers (sop) as mixture model experts, with re-implemented versions of the crf and crf2o parsers of @xcite . 4 for decoding, we use the lmbr decoding presented in section 3.2, which guarantees a small but consistent improvement over pipeline mbr decoding. for each input word, these systems use 3 embeddings: the first is a fixed pretrained vector foot_3 , the second is trainable and looked-up in a table, and the third is computed by a bilstm at the character level (charlstm). the first two embeddings are summed and concatenated with the char sequence embedding. for fop and sop, contextual lexical features are the results of 3-layer bilstms applied to word embedding sequences. the scoring of arcs is then similar to @xcite : lexical features are transformed for head or modifier roles by two feed-forward networks and combined to score arcs via a biaffine transformation. on ptb, in order to compare with recent parsing results, we set up bfop and bsop (b for bert), variants of the fop and sop settings: we follow fonseca and martins (2020) and concatenate an additional bert embedding @xcite (the average of the 4 last layers of the bertbase-uncased model) to the embedding vector fed to the bilstm layers. gating (mixture weights ω) is implemented by a k-class softmax over a feed-forward network whose input are the concatenation of initial and final contextual lexical feature vectors returned by the 3-layer bilstm. hyper-parameters are set similarly to @xcite , with the exception of the learning rate decreased to 10 -4 and patience (that is the maximum number of epochs without las increase on the development set) set to 20. we train 12 independent models for each expert type, with random seed set to system time. ## conclusion we framed dependency parser combination as a finite mixture model, showed that this model presents two distinct properties -an averaging effect and a clustering effect-and devised an efficient decoding method. moreover, we studied the impact of the averaging effect, namely variance reduction during training, and consequently better accuracy. we investigated the reasons of instability when learning mixture models, and proposed an em-inspired method to avoid over-specialization. when used as fine-tuning, this method may improve accuracy over averaging. as a by-product, this method gives state-of-the-art results when combined with first-order and second-order projective parsers on two standard datasets. this work can be further expanded in future research: the increase of parameters can be seen as overparameterization, and many parameters must be redundant. a potentially fruitful avenue of research could be the investigation of the subnetwork hypothesis, i.e. whether distillation could give a smaller network with similar performance. hao zhu, yonatan bisk, and graham neubig. 2020. the return of lexical dependencies: neural lexicalized pcfgs. ran zmigrod, tim vieira, and ryan cotterell. 2020. efficient computation of expectations under spanning tree distributions.