{'fraction_non_alphanumeric': 0.021976026153287323, 'fraction_numerical': 0.004449691245913549, 'mean_word_length': 4.930533117932149, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Evaluation of Computational Grammar Formalisms for Indian Languages

Natural Language Parsing has been the most prominent research area since the genesis of Natural Language Processing. Probabilistic Parsers are being developed to make the process of parser development much easier, accurate and fast. In Indian context, identification of which Computational Grammar Formalism is to be used is still a question which needs to be answered. In this paper we focus on this problem and try to analyze different formalisms for Indian languages.


INTRODUCTION
Natural Language Parsing has been an important activity in Natural Language Processing (NLP) development. But, even since the introduction of machine learning techniques into NLP application development, the scenario changed drastically. This new approach appeared to be very promising, as it helped in rapid prototype development of NLP systems. In this technique, large amount of data was used, onto which various models like Hidden Markov Model (HMM), Conditional Random Fields (CRF), Neural Networks (NN), Support Vector Machines (SVM) etc. were applied. These approaches are also termed as statistical approaches or Statistical Natural Language Processing (SNLP). This was a very effective way of application development, with applications attaining 60-75% accuracy with very little effort. Unfortunately, this approach soon lost its shine as after a point of optimized performance, they become very less helpful in improvement of the systems [ Due to this reason, NLP researchers, in order to improve performance of their systems, tried a new approach. They initially stared with a rule based (traditional) approach. This was called the seed data. Once this was done, it was then supplied to machine learning techniques. This approach was termed as hybrid approach (partially rule based and partially statistical). We can find evidence of improved systems in literature which used this approach [2][3]. This approach even helped in development of probabilistic parsers like Stanford parser [4], Charniak parser [5], MaltParser [6]. These all parsers where supplied with different computational grammars formalisms or with treebanks, which were developed using manually parsed sentences, based on one of the formalisms, for example Penn Treebank [7] TIGER Treebank [8] Paraguay Dependency Treebank [9]. In one or the other way, grammar formalisms were used for development of deep parsers. In this paper, we attempt to study the performance of some of the popular computational grammar formalism techniques, which could be used in development of deep language processing applications like a deep parser, machine translators, semantic role labeler etc.
The motivation for this study came from the fact that free word order is one of the areas were grammar formalism has not yet reached the level of good accuracy. In this area there have been numerous claims to prove superiority of dependency grammar over other formalisms [10][11]. But, often discussions based on this formalism ignore more practical aspects like usability and expressivity. In order to examine free word order approach, we conducted our study on Hindi. Since all other Indian languages follow the same phenomena. The approach suggested in this study can be applied to other languages.

COMPUTATIONAL GRAMMAR FORMALISMS
In general computational grammars can be divided into three categories based on their functionality. They are Phrase Structure Grammars, Dependency Grammars, and Hybrid Grammars. A phrase structure grammar is the one which uses the approach shown by transformational grammars where specific tree positions are associated with assignments of various syntactic roles, such as subject and object. This concept is the motivation for having elements appear in various positions in the tree in the process of deriving the final syntactic structure. Some of the popular formalisms of this category are Tree Adjoining Grammar (TAG) [12], Head Driven Phrase Structure (HPSG) [13] Grammar. Hybrid grammar augments phrase structure grammar by expressing non-projective syntactic relations, while maintaining a more formally defined architecture then phrase structure grammar. Lexical Functional Grammar (LFG) [14] is an example of hybrid grammar.
A dependency grammar consists of a set of words and a set of directed binary dependency relations between words, such that  No words depends on itself  Each dependent has one and only one head  A head may have many dependents  There is one distinguished word which is the head of the sentence and depends on no other word  All other words in a sentence are dependents such that the whole sentence is connected.
Dependency grammars have been studied by Gaifman [15] who studied linear precedence in dependency relations, Hudson [16] who introduced word grammar, Starosta [17] who studied lexicase grammar and Bharti et al [18] who showed the similarities between Paninian Grammar (PG) and dependency grammar and the suitability of PG in Indian context.

METHODOLODY
In order to understand the pros and corns of different grammar formalism, we tested all three types of grammar formalisms. From phrase structure stable, we selected TAG, LFG from hybrid and PG from dependency framework.
We developed parallel grammars for all three frameworks and took a detailed note of development process and variations in syntactic structures. We recorded time taken to construct each sentence, the total time taken to complete the task and the average time taken for the task. We also noted the difficulty level with which each grammar was developed.
Since all three grammar formalism are somewhat distinct in nature, it was very much necessary to develop a mechanism which would not be biased towards one grammar and penalize others. To ensure the equivalence, we tested each grammar using the same set of sentences. The test case contained grammatical as well as ungrammatical sentences. Each grammar was required to distinguish between the two categories. Moreover each grammar was required to provide predicate, arguments and modifiers for each sentence which was parsed. Figure 1 and  2  LFG and DG had no problems to handle these type of sentences. We used Lexicalized TAG (LTAG) which is the modification of TAG and can handle word order variation.
We did this study using ten grammar writes, which were provided with the sentences and were asked to construct the grammars for each sentence. In order to understand the usability of each grammar, we provided each writer with 35 sentences from various categories, as discussed above. Each writer was provided with a short tutorial of each grammar. Shortly after the tutorial of a particular grammar, the writers were asked to implement the sentences for the said grammar. Their performance was calculated on the measure discussed above.

RESULTS
We calculated the results for total and average time taken to complete the task, accuracy with which the task was completed, difficulty ratings provided by each writer, for each formalism, on different categories of sentences. The types of errors committed. The results of the study are provided in the following sections. Table 1 summarizes the average time taken to complete the task by each writer and the accuracy with which they did it. Looking at the data, it is clearly seen that time taken to complete the task was least in PG and most in LFG, TAG was in between the two.

Time Taken and Accuracy
The average time taken by the writers to complete the task for PG, TAG and LFG is 10.3 min, 34 min and 56 min respectively. PG took least time with which the sentences were completed. We also measured average accuracy of each writer. Here TAG scored more accuracy then the other formalisms.

Difficulty Rating
After the task, we provided the questionnaire to the writers. We asked them to provide us with the difficulty rating for each type of sentence, for each grammar. We asked them to ranks the difficulty of sentences between 1 and 5, where 1 being the easiest and 5 being the toughest. As it was not possible to provide results for all the writes here. In Table  2, we provide the ranks given majority of writers. The sores without brackets are the ranks given and the ones in bracket are the no. of writers who gave this rank.
We can see that PG sores very well in simple, generative and predictive adjective cases, but do not perform well on other categories of the sentences. TAG on the other hand performs moderately well. It sores highest in four categories of sentences. LFG scores highest in just one.

Error Analysis
We also examined the types of errors committed by different formalisms, as we wanted to know, why writer had great difficulty with LFG as compared to PG or TAG.
In Paninian Grammar, we analyzed that writers faced great difficulty in assigning relationships to dependency structures. This could be due to the notational convention of the formalism or due to the difficulty with the concepts of head and dependents. We also saw that whenever a directional error was made, the correct rule was framed for implementing the dependency. This shows that the difficulty was with the notion and not with the concepts. Moreover PG although being least rigorous out of the three, showed some sluggishness while dealing with complex sentences.
In Tree Adjoining Grammar, we saw that most errors were in the formation of the derived trees. Between adjunction and substitution operations, adjunction proved to be more error prone. Almost 80% errors were made due to incorrect adjunction operation. This shows that writers had great difficulty understanding the adjunction operation.
In Lexical Functional Grammar, we saw that grammar writer's had great difficulty in associating features with constituent structures. In some cases the writers got confused as to use noun phrase and verb phrase in constituent structure or to use subject and predicate in feature structure. Although this formalism is the most perfect in terms of linguistic phenomena as it captures all the aspects of the language's grammar, it is also fairly difficulty to understand, as it takes time for the grammar write to understand and implement grammar using it.

CONCLUSION
We wanted to study the applicability of different grammar formalism on Indian languages, so that different NLP tasks like development of a deep probabilistic parser or development of a Treebank could be under taken. In doing so, we gathered insights into the different formalisms and understood the merits and demerits of each.
We found out that though Paninain Grammar was preferred for simple sentences, overall performance of TAG was good. It scored better in the average accuracy attained to write the sentences. Although this is a preliminary study and more in-depth evaluations are required before making any sound conclusions. But, with some confidence we can say that TAG can perform better in most of the difficult cases as compared to dependency grammar.