BERT -Based Sequence Labelling Approach for Dependency Parsing in T amil (2022)

Abstract: Dependency parsing is a method for doing surface-level syntactic analysis on natural language texts. The scarcity of any viable tools for doing these tasks in Dravidian Languages has introduced a new line of research into these topics. This paper focuses on a novel approach that uses word-to-word dependency tagging using BERT models to improve the malt parser performance. We used Tamil, a morphologically rich and free word language. The individual words are tokenized using BERT models and the dependency relations are recognized using Machine Learning Algorithms. Oversampling algorithms such as SMOTE (Chawla et al., 2002) and ADASYN (He et al., 2008) are used to tackle data imbalance and consequently improve parsing results. The results obtained are used in the malt parser and this can be accustomed to further highlight that feature-based approaches can be used for such tasks.

## introduction grammatical structures are directly involved in social interactions in the use of languages and this is central for language variation and change. a dependency parser examines a sentence's grammatical structure, finding linkages between head words and modifier words. dependency parsing is a method for doing surface-level syntactic analysis on natural language texts. the dependency parser creates a parse tree by scanning the words of a sentence in linear time. it keeps a partial parse, a stack of words presently being processed, and a buffer of words yet to be processed at each step. in contrast to its corresponding constituency structure, the dependency tree structure is considered a cutting-edge approach for parsing free word order languages such as dravidian languages. a typical challenge for developing parsers in such low resource languages is non-projectivity, which emerges because of languages with free word order or long-distance dependencies, leading to a significant proportion of sentences in many languages requiring a non-projective dependency analysis. tamil is a dravidian language spoken mostly in malaysia, sri lanka, singapore and southern india @xcite . tamil is agglutinative and contains many morphological suffixes. tamil has two core word classes: nouns and verbs, with hundreds of distinct word forms possible through concatenative and derivational morphology @xcite . with the exception of head-final, tamil has a rich morphology that allows it to have any word order. this is a critical challenge in dravidian languages since the subtask of proper label prediction in dependency parsing is extremely imprecise. enhancing the prediction of these proper dependency relations betters the dependency parsing scores considerably on parsing tasks in transition-based parsing algorithms. only a few works on dependency parsing for indic languages have been mentioned in the literature, let alone focusing on improving the prediction of dependency relation labels because there are a limited number of tools available. the lack of organized data makes this process extremely challenging, as unstructured text is difficult to parse on its own. the necessity of developing and improving a parser for tamil is known to find applications in tasks like semantic parsing, machine translation, relation extraction, and many others. a key advantage of dependency parser is its ability to gain important semantic information for languages that are flexible with the placement of their part of speech @xcite . in this paper, we tried to bring about machine learning approaches built upon a novel way of generating word embeddings through various pretrained multilingual bert models @xcite for improving the dependency relation prediction. these models are fine-tuned to improve and study the variational changes within the models and improving the performance of dependency parsing for tamil language. the currently available parsers deal with word and sentence level embeddings, but for a free word language, the word's dependency tags information is held at elementary character level which is fed onto machine learning algorithms like regression, decision tree, random forrest classification, and support vector machine @xcite . the models chosen are specific to understanding the relationship of embeddings of words at character level, where learning through regression and svm infers the dimensional separability and feature space projections, while decision tree and random forest are well known relevant feature extractors. the four different models for dependency parsing compared directly and analyzed. to train the models we have tokenized sentences of tamil ttb into individual words and extracted its respective dependency tags, further this data is embedded and then used to train our models. initial results suggest bias towards the majority dependency class tags, appearing due to the imbalances in dependency tag distribution. where models like svm become difficult to use as the class wise accuracy is strikingly low for minority class labels. one method of tackling the issue of data imbalance is through oversampling algorithms, yielding a higher-class wise accuracy while slightly compromising the overall accuracy which are discussed over the experiment section. the conll-u formatted data is processed and then bert case models are used for the token embedding which is used to train the machine learning models. the dependency of each word is label encoded which is then further used in training the models. our best observed values were for the support vector machines fed with embedding generated by indicbert @xcite with label accuracy of 67%, which was further passed onto a transition-based parser giving 52% labeled and 89% unlabeled attachment score. due to the high imbalance in the dataset, on oversampling of the data, the observed labeled accuracy was around 56% with improvement in the overall class wise accuracy for some of the minority classes. ## dataset description universal dependencies (ud) @xcite is a project that aims to create cross-linguistically consistent treebank annotation for a variety of languages. the purpose is to facilitate multilingual parser creation, cross-lingual learning, and parsing research from the standpoint of language typology. the universal dependency formalism is now widely used to construct universal dependency treebanks (udts) with annotations @xcite , where in udv2.7, indian languages like tamil have fewer than 12k tokens. this paper is worked on over tamil tree bank @xcite , which has longer sentences over multi-word tamil tree bank (mwtt). cored with complex concepts such as elision, relative clauses, conjunct propagation, raising and control structures, and expanded case marking based on the enhanced universal dependency annotation, it forms around 536 sentences @xcite . there are 400 training sentences and 120 testing sentences in the tamil udt (universal dependency treebanks), with around 30 unique observed dependency tags in the dataset. ## related works dependency parsing and the building of annotated treebanks are currently being researched for hindi and telugu @xcite @xcite . in 2009, as part of the icon 2009 conference, there was an nlp tools contest focused on parsing indian languages (hindi, bangla, and telugu). as the data were feasible, the building of a large-scale treebank dependency @xcite for telugu (with a goal of 1 million words) that has about 1500 annotated sentences were one such notable attempt for building a dependency parser in dravidian languages. previous works that used tamil dependency treebanks have been published, a paper @xcite that used a machine learning approach to tamil dependency parsing. this paper described grammar teaching tools in the sentence and word analyzing level for tamil language. as part of the parser development, @xcite created small dependency corpora with 5000 words. other works such as @xcite focused on parsing the spoken language utterances using dependency framework. those works did not make use of treebank to the parser development, rather they were based on linguistic rules. the work @xcite used relative position of words to identify semantic relations. along with the previously mentioned work there was one more work @xcite ) that discussed tamil syntactic parsing. @xcite used morphological analyzer and heuristic rules to identify phrase structures. paper title uas score @xcite 94.5 @xcite 91.82 @xcite 85. 76 the literature on tamil dependency parsing is sparse, though there are some recent works on developing a tamil dependency parser which has been studied in many contexts, a neural based parser @xcite ) and a rulebased parsing @xcite . to our idea, these are the initial attempts to create a tamil dependency treebank. ## methodology the dependency parser's internal structure is made up entirely of directed relationships between lexical components in the sentence. vital information that is typically buried in the more sophisticated phrasestructure parses is explicitly encoded by these headdependent interactions. another reason to employ a dependency-based method is that head-dependent connections approximate the semantic link between predicates and their arguments, making them valuable in a variety of applications including question answering, information extraction, and coreference resolution. hence the correct dependent prediction is crucial in the task of dependency parsing. learning contextual information is essential over generating contextual-independent word embeddings for effectively encoding sentence-level features even inside single-word embeddings, yielding results that are equivalent or even superior to those achieved with sentence representations @xcite . the data extracted with morphological and part of speech information is fed on to various pretrained multilingual bidirectional encoder representation like mbert, xlm-roberta, in-dicbert and distilbert for generating the embedding at character level. the generated embedding is of different dimensions based on the morphology, unified by taking linear combinations of all vectors generated for each word in a sentence. these embeddings are passed on to various machine learning models to analyze performance of which the best model jointly works with transitionbased dependency parsing. we follow the transition-based dependency parser @xcite which, includes two important systems; a transition mechanism that transforms a phrase into a dependency tree, and a machine learning classifier that can predict the next transition for each system structure that passes a statement. dependency parsing can be accomplished as a deterministic search over the transition system, led by the classifier, given these two components. a stack of partially processed tokens, an input buffer containing the remaining tokens, and a collection of arcs representing the partially created dependency tree make up a parser configuration in this system. there are four transitions possible in this system that can only capture projective dependency trees: reduce operations, such as left-arc and right-arc, are named after shift-reduce parsing metaphor in which reducing involves merging components on the stack. when it comes to using operators, there are few prerequisites. when root is the second member on the stack, the left-arc operator cannot be used (since by definition the root node cannot have any incoming arcs). both the left-arc and right-arc operators must have two components on the stack before they may be used. a transition-based parser can also be defined by expressing the current state of the parse as a configuration, which includes the stack, an input buffer of words or tokens and a collection of relations that create a dependency tree. we begin with an initial configuration in which the root node is on the stack, the tokens in the sentence are in the buffer and the parsing is represented by an empty set of relations. the stack and word list should be empty in the end target state and the set of relations will represent the final parse. the approach is similar to neural based parser oracle of @xcite , which is replaced with machine learning algorithms for arc prediction (see figure 1 ), where a sentence with 'n' words @xmath0, w2, w3, . . . , wn] is fed to the encoder for obtaining the concatenation of several token embeddings is @xmath1, e2, e3, . . . , en] from bert models pretrained with indian languages. the best model architecture was observed based on the test set. we used maltparser, an open-source implementation of transition-based dependency parsing with a range of transition systems and customized classifiers, receives the embeddings equipped with a machine learning classifier. to overcome the problem of highly imbalanced label distribution oversampling algorithms such as smote and adasyn algorithms to up sample the tamil training set which improved the results from initial experiments. ## experiments & results ud treebanks in conll-u format annotations are marked with the morphological, pos and dependency label information required for construction of the parse tree. tamil udt provides dataset segregations for training, validation, and testing. to induce the randomness, the data is combined and ran-dom sampled same ratio, following the approach of loganathan et al. @xcite . as part of exploratory data analysis, we analyzed the distribution of dependency relations in the train-test dataset combined (see figure 2 ). as observed, the classification task was highly biased towards the majority classes on account of the high imbalance in the dataset. to extract the character level significance of tamil language, the sentences are broken down on to tokens as specified in the conll-u formatting. in the encoder module, we have used different types of bert models for this task, namely mbert, xlm-roberta, in-dicbert and distilbert with a range of different results. these tokens are embedded using these models which are trained with tamil and other indic languages to retain the contextual information of the token. we have used bert embedding for the tokenization of the input sentences solely because the individual word tokens are exclusively dependent on the sentence itself rather than having just a corresponding index for the word itself like word2vec. each individual sentence requires its own input id's which are a sequence of integers which map every input token with its respective token index in the bert tokenizer vocabulary. the large bert model that is used here has around 24 transformer encoders and each output per token from one of the layers can be used as a work embedding. further as mentioned these embedded tokens can be fed to the parser oracle of the malt parser. malt parser works based on a transition system and two stacks. at each step, a transition is predicted using machine learning models, altered from liblinear and libsvm provided by the open-sourced parser. the input to these models is composed of the encoding of tokens in stacks and the current state of the machine. the embeddings passed on to the oracle are experimented with learning algorithms like linear regression to understand the separability of the data in its dimension in an attempt to establish linear relationship with the words. decision tree and random forrest classifiers are well performing important feature extractors, which is implemented to better the parsing task and study the head-dependent tag relation based from the generated bert embeddings. the algorithm closely follows a rule-based approach for parsing tasks. the sentences are tokenized and fed on to classifier trees, which improved the results over the regression models. a support vector machine classifier is employed to solve the parsing task, which is a multi-class classification problem. the multi-class problem is divided into a series of binary-class problems since svms are binary classifiers, that classify the embeddings generated by projecting it into higher dimension to achieve separability. the graph above (see figure 3 ) , we can clearly observe that there is a large amount of misclassification in quite a few classes. this is mainly because of the high amount of imbalance in our dataset. to counter this issue, we have over-sampled the data using algorithms like adasyn and smote. the main goal of using these techniques was to improve class-wise accuracy. as observed (see figure 4 ), there was a significant improvement in the class-wise accuracy while the overall accuracy remained constant. both adasyn and smote functions are based on the k-nearest neighbours (knn), difference being that adasyn uses density distribution to determine the number of synthetic samples generated respectively for every minority class. this is done by changing the weights of the various minority samples adaptively which compensates for the skewed distributions. smote creates an equivalent number of synthetic samples for each original minority sample. with respect to our experiment, we have seen that adasyn yields better results as compared to smote. the difference being that adasyn uses density distribution to determine the number of synthetic samples generated respectively for every minority class. this is done by changing the weights of the various minority samples adaptively which compensates for the skewed distributions. smote creates an equivalent number of synthetic samples for each original minority sample. we experimented with four different bert models for this task and have achieved varying results based on the model used. indicbert being a multilingual albert pre-trained model trained upon 11 indian languages, outperformed every other bert to overcome such low scores, we move ahead with the method of oversampling, which yielded better results due to the fact that for distinct minority class instances. adasyn uses a weighted distribution based on how difficult it is to learn, with more synthetic data generated and trained for challenging minority class cases lesser in sam-ples. alongside increasing the number of data samples. as perceived (see ## conclusion & future works this paper explores the use of a malt parser for transition-based dependency parsing of tamil language and how an improvement in ls scores can directly improve the overall parser performance. we show that for a morphologically rich, agglutinative language like tamil, with appropriate vector representations from bert trained by indic languages yields enhanced parsing. various bert models were used to improve the dependency relation prediction accuracy and the best performing model's scores are comparable to other methods without mixed language training. the synthetic data generated by oversampling algorithms eliminates the need for more data to an extent, but we suggest training the model using a variety of datasets for the low-resource language to efficiently build a parser with strong contextual embeddings for dravidian languages. we plan to use these techniques to improve our results in the near future on building effective parser for dravidian languages. in the future, we'd like to explore how the outcomes of our data split evolve when additional data is added, this may be an excellent tool for self-training. because the amount of the tuning data for the svm @xcite , @xcite appears to be the most relevant, the uas may be improved by including self-training data in our tuning sets. the approach of contextual embedding and oversampling algorithms can be extended to other parsing algorithms like graph based parsing techniques, which open up wide variety of possibilities of improving the task of dependency parsing for dravidian languages.