Spa: On the Sparsity of Virtual Adversarial Training for Dependency Parsing (2022)

Abstract: Virtual adversarial training (VAT) is a powerful approach to improving robustness and performance, leveraging both labeled and unlabeled data to compensate for the scarcity of labeled data. It is adopted on lots of vision and language classification tasks. However, for tasks with structured output (e.g., dependency parsing), the application of VAT is nontrivial due to the intrinsic proprieties of structures: (1) the non-sparse problem and (2) exponential complexity. Against this background, we propose the Sparse Parse Adjustment (spa) algorithm and successfully applied VAT to the dependency parsing task. spa refers to the learning algorithm which combines the graph-based dependency parsing model with VAT in an exact computational manner and enhances the dependency parser with controllable and adjustable sparsity. Empirical studies show that the TreeCRF parser optimized using outperforms other methods without sparsity regularization.

## introduction dependency parsing is a fundamental structured prediction task in natural language processing that aims to capture syntactic structures in sentences in the form of dependency relations between words. the application of dependency structures is mainly reflected in discourse parsing @xcite , machine translation @xcite , and many other tasks. while supervised learning is the ideal technique used to learn a dependency parser automatically, it requires the training sentences to be manually annotated with their gold parse trees. this brings the main bottleneck for learning a practical dependency parser -the lack of adequate training corpora with dependency trees. annotations are both laborious and time costly. multiple research directions (i.e., unsupervised learning, semi-˚corresponding author supervised learning and transfer learning, etc.) try to eliminate this bottleneck @xcite . virtual adversarial training (vat) @xcite , as a semi-supervised learning approach, utilizes both annotated training sentences and unlabeled data to compensate for the scarcity of labeled data. it extends adversarial training (at) @xcite to unlabeled data. vat encourages the output distributions to be similar on both an unlabeled sample and corresponding adversarial examples by adding a kullback-leibler (kl) divergence term in the training loss. in this way, vat improves the performance and robustness of many tasks @xcite @xcite . however, multiple technical challenges are faced by applying vat on dependency parsing. except for the general challenges related to gradient computation of discrete inputs, grammatical correctness, and meaning preservation @xcite @xcite @xcite faced by all adversarial example generators, two potential but critical challenges exist because of the propriety of structured prediction: (1) the non-sparse problem and (2) exponential complexity. the non-sparse problem is naturally connected to unambiguity @xcite , both highlighting that the number of plausible parses of a natural language sentence is relatively small compared with the huge number of possible parses. we are interested in predicting probabilities as small as possible for these unlikely trees rather than having an estimation of their actual probabilities. the fact that the viterbi expectationmaximization algorithm (em) outperforms standard em in previous work @xcite @xcite also provides evidence of the advantage of implicitly utilizing the sparsity property. although chen et al. (2020) make vat compatible with a linear-chain structured prediction model by considering the probabilities of k most possible label sequences, which is a sparse approximation of the original distribution, they did not quantitatively investigate the impact of sparsity in the application of vat. for the complexity challenge, different from conventional classification tasks with a fixed number of classes, computing the kl divergence of parse tree distributions by enumerating all possible parses is intractable because the number of possible parses for each sentence is exponential w.r.t. the sentence length. therefore, conventional approaches can only estimate the kl divergence in the vat loss rather than compute it exactly. against this background, we propose sparse parse adjustment algorithm (spa) and successfully applied vat to dependency parsing. spa refers to the learning algorithm which combines the graph-based dependency parsing model with vat in an exact computational manner, overcoming the problem of enumerating, and enhances the dependency parser with controllable and adjustable sparsity. we applied vat to a state-of-the-art parsing model: the tree conditional random field (treecrf) parser @xcite . spa incorporates into treecrf an inductive bias in favor of models that lead to a controllable sparsity. adjusting the hyper-parameter can control sparsity to ease the non-sparse problem. empirical studies show that the treecrf parser optimized using spa outperforms other semi-supervised methods without sparsity regularization. within spa, our exact computational manner achieves competitive performance and enables faster training compared to the top-k approximate approach @xcite . the code can be found at: https://github. com/louchao98/struct-vat . ## analysis 6.1 ablation study in this section we study the effectiveness of our two sparsity adjustment on different settings: exact computation to ease the computation errors and sparsity adjustment to add a prior of sparsity property. as show in tab. 6, the sparsity adjustment is not only successfully applied on lowresource setting, namely the 10%wsj+90%wsj setting, but also works on other settings (i.e., 30%wsj+70%wsj and 50%wsj+50%wsj). exact computation is capable of improving the parsing result on all the settings (including 10%wsj+90%wsj, 30%wsj+70%wsj and 50%wsj+50%wsj). it shows that the model takes advantage of eliminating the approximation problem. when simultaneously combining the sparsity adjustment and the sparsity adjustment, we observe a further improvement on the final result in the exactcomp-(0.3,2) row. we provide other results, including inspection of non-sparse problems and speed comparison, in the appendix. ## conclusion and further work in this paper, we propose sparse parse adjustment algorithm (spa). we successfully applied vat to the dependency parsing task using this spa algorithm. we use spa to enhance the treecrf parser with exact computation and sparsity adjustment. further empirical study indicates that spa has strong effects in semi-supervised settings and time and space efficiency. furthermore, this approach has broad applications on other structured prediction tasks. the exact computation for the treecrf can be easily transferred to general structured prediction architectures, e.g., linearchain-crf. we will leave it as a further work.