Tree-shape Uncertainty for Analyzing the Inherent Branching Bias of Unsupervised Parsing Models (2023)

Abstract: This paper presents the formalization of tree-shape uncertainty that enables us to analyze the inherent branching bias of unsupervised parsing models using raw texts alone. Previous work analyzed the branching bias of unsupervised parsing models by comparing the outputs of trained parsers with gold syntactic trees. However, such approaches do not consider the fact that texts can be generated by different grammars with different syntactic trees, possibly failing to clearly separate the inherent bias of the model and the bias in train data learned by the model. To this end, we formulate tree-shape uncertainty and derive sufficient conditions that can be used for creating texts that are expected to contain no biased information on branching. In the experiment, we show that training parsers on such unbiased texts can effectively detect the branching bias of existing unsupervised parsing models. Such bias may depend only on the algorithm, or it may depend on seemingly unrelated dataset statistics such as sequence length and vocabulary size.

## introduction in unsupervised parsing, a model receives raw texts as training data and produces trained parsers. the branching bias of an unsupervised parsing model is the bias in the branching direction of tree structures it is likely to learn (li et al., 2020a), where branching direction refers to whether trees grow deeper on the left or right side. such a bias is important in applications; for example, a model with a right-branching bias is likely to be more accurate for a right-branching language such as english but less accurate for a left-branching language like japanese. a theoretical bias analysis was done by dyer et al. (2019), but their method is specific to certain models, such as prpn (shen et al., 2018), and not general in nature. instead, the branching bias of a model is observed by empirically comparing the performances of trained parsers for figure 1 : an illustration of the critical problem in branching bias analysis of unsupervised parsing models languages with different gold tree branching directions, e.g., different natural-language treebanks such as english and japanese (li et al., 2020b), original and reversed treebanks (li et al., 2020a), and synthetic languages (jin et al., 2018). however, performance comparison based on gold syntactic trees is theoretically incomplete as bias analysis. in principle, to analyze the inherent bias of a model in a model-agnostic way, we need to examine the bias in the output tree structures of trained parsers. yet, to make this procedure theoretically valid, it needs to be clarified what information the train texts can provide to the models regarding branching direction because the bias observable in the parser outputs are two folds: the inductive bias inherent in the model and the bias in the train data that can be learned by a parser. we call the latter the potential branching bias of texts. the problem with previous work is that the bias in the branching directions of gold trees may not be equal to the potential branching bias of the texts. for example, jin et al. (2018) assumed the language l 0 ≡ {ab n | @xmath0: g l ); similarly, they assumed l 1 ≡ {a n b | @xmath1. they train parsers on each language and compare the likelihoods to show that models have no bias. however, in fact, l 0 can also be generated by a rightbranching grammar (figure 1 : g r ), and l 1 by a left-branching grammar. therefore, it is not trivial to claim that the texts drawn from l 0 provide leftbranching information to models and, hence, that the performance gap between l 0 and l 1 reveals the models' inherent branching bias. this points out that assumptions about gold trees may lead to a misestimate of the potential branching bias of texts and, thus, the branching bias of the models. how can we avoid such problems? one solution is to use texts that contain no potential branching bias. similar to how kharitonov and chaabouni (2020) study the inductive bias of sequence-to-sequence models by training them on non-informative data, if we train parsers on unbiased texts, we can directly observe the model's inherent branching bias as the bias in the outputs of trained parsers without the need to compare with gold trees. in other words, parsers must decide the branching directions based solely on the bias inherited from the model if the train texts give no information about the branching directions. in this paper, we first introduce the concept of tree-shape uncertainty, which formulates the property of certain texts that can be produced by syntactic trees of different shapes. then, we revisit the work by li et al. (2020a) and derive sufficient conditions for tree-shape uncertainty to construct texts with no potential branching bias. in the experiments, we analyze the inherent branching bias of models by constructing unbiased texts based on natural language corpora. to examine the biases in the parser outputs, we extend existing tree imbalance measures (fischer et al., 2021) to capture branching directions. the experiments on popular unsupervised parsing models diora (drozdov et al., 2019), prpn (shen et al., 2018), and urnng (kim et al., 2019b) demonstrate that our method can effectively detect the different branching biases of these models. we also find that the bias of urnng may be sensitive to seemingly unrelated dataset statistics such as sequence length and vocabulary size. ## measuring branching direction in this section, we describe the measures for branching direction. we denote by t the set of all, possi-bly non-binary, unlabeled trees and formalize the requirements for a branching measure as follows. definition 1. we call a function b : @xmath2, 1] branching measure if it meets the following requirements: here, flipping a tree is defined as reversing the order of the child subtrees for all internal nodes. in the field of phylogeny, a number of treeshape metrics have been proposed based on leaf depths (kirkpatrick and slatkin, 1993; coronado et al., 2020; fischer, 2021), number of leaves (heard, 1992; mooers and heard, 1997), and number of inner vertices satisfying certain conditions (rogers, 1996; kersting and fischer, 2021; norström et al., 2012). however, these metrics are mostly about the (im)balance of tree structures and do not address branching directions. for this reason, we pick up and modify three metrics, namely, the corrected colles index (heard, 1992), the equal weights colles index (mooers and heard, 1997), and the rogers j index (rogers, 1996). furthermore, since these three metrics are only defined for binary trees, we naively generalize them to apply to non-binary trees. as can be seen in ## sufficient conditions for unbiased texts in this section, we revisit the approach taken by li et al. (2020a) and extend it to derive sufficient conditions for tree-shape uncertainty, which is useful for branching bias analysis. li et al. (2020a) analyzed the branching bias of the syntactic trees extracted from pre-trained language models such as bert (devlin et al., 2019; liu et al., 2019) and gpt2 (radford et al., 2019). to do this, they trained language model m on natural language treebank corpus d and m ′ on the reversed corpus d -1 . let f1(m, t gold ) be the f1 score of m for the gold syntactic trees t gold of d; they measured the branching bias by the difference in accuracy f1(m, t gold ) -f1(m ′ , t gold -1 ), based on the intuition that reversing the text of a right-branching language yields the text of a leftbranching language. however, such bias evaluation is highly dependent on the choice of gold trees. it becomes problematic when d can be generated by trees with different shapes from t gold , potentially over/underestimating the bias of the models. the problem above is that the potential branching bias of texts is not necessarily the same as that @xcite an automorphism ϕ on σ is a bijective function σ → σ. theorem 1. the following holds for any text corpus d: g that is production-flip and symbol-mapping invariant, where |ϕ| denotes the order of ϕ, and f (z) ≡ ϕ(z -1 ) flips each sequence in z and remaps each symbol by ϕ. @xcite proof. first, we show that if @xmath3, then d is tree-shape uncertain with respect to n c g and n b t . take any g and t . for any sequence s and tree t, it can be seen that since n c g is production-flip and symbol-mapping invariant, we also have g -1 ϕ ∈ n c g (g), which leads to the tree-shape uncertainty of d. therefore, to prove the theorem, it suffices to show @xmath4: the intuition behind considering automorphisms on terminal symbols is that when we use one-hot encoding or randomly initialize word embedding, exchanging the embedding between different words does not make any essential difference to models. @xcite in our formalization, such intuition is formulated as the symbol-mapping invariance of the grammar neighborhood. thus, theorem 1 can be interpreted as indicating that we can construct a text corpus d with any base texts z and vocabulary automorphism ϕ (|ϕ| = 2n) such that the underlying branching direction cannot be identified from the texts alone when using one-hot encoding or randomly initialized word embedding. consideration for natural language one might wonder if natural language texts satisfy the sufficient conditions introduced in theorem 1 . the answer, in short, is probably no. this can be seen from a very simple example. consider texts @xmath5, @xmath6. if there is an automorphism ϕ such that @xmath7, then it is clear that for x, s must map to v, but for y, s must map to o, contradicting that ϕ is an automorphism. however, theorem 1 shows only sufficient conditions, and whether natural language texts are tree-shape uncertain or not is an open problem. moreover, it is still difficult to design toy languages that are not tree-shape uncertain. this is because, to prove that given texts are not treeshape uncertain, we must construct a grammar and show that any similarly complex grammar does not generate the texts with the same probability or with differently shaped syntactic trees, which is not trivial. ## experimental settings to analyze the inherent branching bias of unsupervised parses, we utilize theorem 1 . more concretely, we create d z ϕ ≡ ## conclusion this paper proposes a theoretically founded branching bias analysis of unsupervised parsing models. we consider the possibility of the same texts being generated by pcfgs that assign differently shaped tree structures, which we formalize as tree-shape uncertainty. we derive sufficient conditions for tree-shape uncertainty with respect to branching direction under a reasonable grammar complexity assumption and use it to construct text corpora that are expected to contain no potential branching bias. by training unsupervised parsers on such unbiased texts, we demonstrate that the inherent branching bias of models can be directly observed by quantifying the branching direction of the output tree structures without the need to compare them with gold trees.