Learning from Non-Binary Constituency Trees via Tensor Decomposition (2020)

Abstract: Processing sentence constituency trees in binarised form is a common and popular approach in literature. However, constituency trees are non-binary by nature. The binarisation procedure changes deeply the structure, furthering constituents that instead are close. In this work, we introduce a new approach to deal with non-binary constituency trees which leverages tensor-based models. In particular, we show how a powerful composition function based on the canonical tensor decomposition can exploit such a rich structure. A key point of our approach is the weight sharing constraint imposed on the factor matrices, which allows limiting the number of model parameters. Finally, we introduce a Tree-LSTM model which takes advantage of this composition function and we experimentally assess its performance on different NLP tasks.

## introduction one of the fundamental problems in natural language processing (nlp) is learning a distributed encoding of sentences, as this is the stepping stone for many nlp tasks, such as sentence classification, sentiment analysis and natural language inference. the multitude of approaches addressing this problem can be categorised according to how a sentence is represented. the simpler sentence representation is bag-of-words, which depicts sentences as words multisets ignoring the word order. despite the simple representation, it has been used to obtain meaningful sentence encodings @xcite @xcite . sequence representation overcomes this limitation considering the sentence as an ordered sequence of words. it allows building models which progressively constructs a sentence encoding, processing one word at the time. recurrent neural network @xcite and long-short term memory (lstm) @xcite are probably the most famous models which use this representation. a key aspect of sentences, which is missing in sequential processing, is compositionality. for example, the sentence "the sky is blue and the grass is green" is obtained by composing the two sub-phrases "the sky is blue" and "the grass is green" with the conjunction "and". the intrinsic compositionality of sentences makes them suitable for a tree representation, where the whole sentence (the root) is built in terms of sub-phrases (the internal nodes) which in turn are defined in terms of smaller constituents; the base cases are words (the leaves) since they are the atomic piece of information. this representation takes the name of constituency tree. in fig. 1a we show the constituency tree of the sentence "effective but too-tepid biopic": the leaves are the words while internal nodes represent syntactic categories which are the constituents of the whole sentence. there are many models which compute a sentence encoding starting from its constituency tree. for our purposes, we restrict the discussion on bottom-up recursive neural networks (recnns) @xcite . the parsing direction is constrained by the structure of constituency trees, having information (i.e. words) on leaf nodes. in this domain, we refer to the term composition function to indicate the state-transition function which computes the representation (i.e. the hidden state) of a tree node combining the representation of its constituents (i.e. the hidden state of its child nodes). then, the hidden state of the root (i.e. the whole sentence) is taken as sentence encoding. the matrix-vector recurrent neural network (mv-rnn) @xcite and the recursive neural tensor network (rntn) @xcite apply the recnn architecture to binary constituency trees using complex composition functions. @xcite extends the well known long-short term memory @xcite architecture to tree-structured data. they propose two different tree-lstms (that we discuss in section 2.1): the n -ary tree-lstm defines a composition function which considers constituent order while the child-sum tree-lstm ignores such an order. however, only the former model is applied to binary constituency trees. the latter is applied to dependency trees, which are another kind of tree representation for sentences, out of our scope. in recent years, tree-lstm has been used as a building block to develop more sophisticated models. for example, @xcite , @xcite , @xcite , @xcite build new tree-lstm models which define dynamic composition functions depending on syntactic categories (i.e. part-of-speech tags). instead, @xcite introduces a bidirectional tree-lstm which takes advantage of both parsing directions: bottom-up and top-down. as we stated before, constituency trees are intrinsically bottom-up; to this end, the author introduces a first bottom-up pass, called head lexicalization, to propagate information from leaves to the root. all these models are applied only to binary constituency trees. thus far, we have shown that most of the models compute sentences encodings starting from binary constituency trees. this simplification solves one crucial problem of tree-structured data: the variable number of child nodes. however, the price to pay is the loss of structural information. for example, in fig. 1b and fig. 1c we report the constituency and the binary constituency tree of the sentence "effective but too-tepid biopic". comparing the two representation, we can observe that binary tree has one more node that breaks the ternary relation in the non-binary tree; in general, to break a node with l child nodes, we need to add l -2 new nodes. all these new nodes create a chain which moves away the child nodes of the n-ary relation from their parent. the composition of them is obtained by considering one child at a time, as it happens in sequence representation. hence, the binarisation removes the equality among child nodes, with the risk of weakening contribution of child nodes that are moved far away from their parent and strengthening the contribution of the ones that remain close. as far as we know, the only work which builds a model suitable for non-binary constituency trees is the treenet @xcite . the idea is to consider all child nodes in a chain: the hidden state of a node depends on the hidden state of its left sibling and its rightmost child. even if the model itself works with non-binary trees, the composition function expressed is binary since it always composes two elements. we discuss this observation in details in sec. 3. the definition of models for non-binary constituency trees requires to go beyond the standard definition of composition function. standard recnns define learnable composition functions which are based on the summation of the contribution of each constituent. @xcite proposed a generalisation of such sum-based composition functions leveraging more expressive multi-affine maps represented as tensors. the exponential number of parameters with respect to the tree out-degree (i.e. the maximum number of children for each node in the tree) required by the full-tensorial approach can be controlled by applying tensor decomposition. the tensorial models outperform sum-based models, especially when the tree out-degree increases @xcite . within the scope of this paper, we unveil that non-binary constituency trees can be effectively exploited to improve predictive performance in nlp task, showing that more powerful composition functions are necessary to take advantages of such a rich representation. to this end, we introduce two new tree-lstm models which leverage canonical tensor decomposition: the former is suitable for binarised constituency trees, while the latter can process general non-binary constituency trees imposing weight sharing on the tensor decomposition factors. finally, we test the quality of sentence encodings produced by our models on different nlp tasks, showing that the combination of a rich representation and a powerful composition function is able to outperform baseline models using the same number of parameters. ## related models in this section, we discuss three architectures from the literature that are related to the approach put forward in this paper and are used as baselines in our empirical analysis. ## canonical tree-lstm this section aims to introduce new tree-lstm models that extend the recurrent approach to tensor-based processing tailored for constituency trees. these two models rely on tensor tree-lstm @xcite and canonical tensor decomposition. we focus on such decomposition since it can be combined with a weight sharing constraint, developing a composition function which can exploit nonbinary constituency trees without increasing the model parameters number. since these models are applied on constituency trees, we define them only on the nodes which apply composition functions (i.e. the internal nodes). the input label x v , which is attached only on leaf nodes, is processed using the same computation described in eq. 4. ## experiments we test the models introduced in the previous section on two tasks: sentence classification and semantic textual similarity. sentence classification. the goal of this task is to predict the class of the given input sentence. hence, we use a tree-lstm to encode the constituency tree of the input sentence in a succinct representation (h root ) and then we feed it to a single-layer neural network to predict the class @xmath0. . . m}: ## conclusion in this paper, we show that using non-binary constituency trees can be beneficial, especially in semantic similarity tasks. moreover, we highlight the need of powerful composition function to exploit such a rich representation. to this end, we have introduced a new tree-lstm model which leverages tensor canonical decomposition and weight sharing to process non-binary trees without adding new parameters. such results pave the way to the definition of new tensor models which leverage suitable tensor decomposition to take advantage of non-binary constituency trees. to this end, the next step would be the application of other tensor decompositions. among the others, the tensor train decomposition seems to be promising to define new composition functions which are sensitive to child nodes order. ultimately, we would like to test multiple tensor-based models on different nlp tasks, studying the relation between the bias introduced by each different tensor decomposition and the intrinsic property of the task.