{'fraction_non_alphanumeric': 0.034724021767297227, 'fraction_numerical': 0.014857044139241599, 'mean_word_length': 4.84452296819788, '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}}
An Optimal Order of Factors for the Computational Treatment of Personal Anaphoric Devices in Urdu Discourse

Handling of human language by computer is a very intricate and complex task. In natural languages, sentences are usually part of discourse units just as words are part of sentences. Anaphora resolution plays a significant role in discourse analysis for chopping larger discourse units into smaller ones. This process is done for the purpose of better understanding and making easier the further processing of text by computer. This paper is focused on the discussion of various factors and their optimal order that play an important role in personal anaphora resolution in Urdu. Algorithms are developed that resolves pronominal anaphoric devices with 77-80% success rate.


Introduction
In written text, cohesion occurs when some elements in a discourse are dependent on others and that refer to items backward in the text, both in the spoken or written text (Halliday and Hassan, 1976). Consider the following example (1.1) Shah Rukh Khan is off to one of his favorite cities-London, with his family. Now he is looking for another destination, not so much for holidaying though. (The News Islamabad: June 2006) (1.2) Bollywood actress Bipasha Basu has been signed for her new film Corporate. She is a single working woman, wants to get somewhere in life, on her own terms. (The News Islamabad: June 2006) Cohesion in examples 1.1 and 1.2 is introduced due to the terms he, his, her, she and interpretation of these references depends upon some preceding terms. These referring terms are called anaphors or anaphoric devices (ADs). Halliday and Hassan described anaphora as 'cohesion which points back to some previous items' (Halliday and Hassan, 1976). The 'pointing back' words or phrases are called the anaphors (Halliday and Hassan, 1976) and the entities to which these point are called antecedents and the procedure of determining the antecedents of anaphors and subsequent replacement in some particular discourse is called anaphora resolution. According to Halliday and Hassan when anaphors are replaced by their corresponding antecedents, cohesion no more exists. Personal anaphoric devices (ADs) are the most widely used variety of ADs in Urdu text. These are further classified as first person, second person and third person anaphoric devices. A lot of work has been done in English for the purpose of anaphora resolution and various algorithms have been devised for this purpose (Aone and Bennette, 1996;Brenan , Friedman and Pollard, 1987;Ge, Hale and Charniak, 1998;Grosz, Aravind and Weinstein, 1995;McCarthy and Lehnert, 1995;Lappins and Leass, 1994;Mitkov, 1998;Soon, Ng and Lim, 1999). Work has also been done in South Asian Languages such as Hindi and Malayalam for the purpose of anaphora resolution (Prasad and Strube, 2000;Sobha, 1998). Prasad and Strube (2000) worked on anaphora resolution in Hindi. Their approach relies on the discourse salience factors and is primarily inspired by the central idea of Centering theory (Grosz, Aravind and Weinstein, 1995). Centering theory has also guided the development of pronoun resolution algorithms, such as the BFP algorithm (Brenan, Friedman and Pollard, 1987) and the S-list algorithm developed by Strube (Strube, 1998). Prasad and Strube (2000) applied these algorithms to the resolution of pronouns in Hindi texts. They showed that the BFP algorithm cannot be successfully implemented for pronoun resolution in Hindi. They argued that better results can be obtained with an algorithm that does not use the Centering notions of the backward-looking center and the centering transitions for the computation of pronominal antecedents, such as the S-list algorithm (Prasad and Strube, 2000). Prasad and Strube used well established approaches for Hindi anaphora resolution. Sobha (1998) used knowledge poor rule based approach for reference resolution in Hindi and Malayalam languages that stands on very limited syntactic information. In Urdu language very little work has been done on discourse level especially in the field of anaphora resolution. Although, most of the anaphoric devices in Urdu and Hindi are same but the style and organization of discourses are bit different that causes the difference in anaphora resolution. Kulsoom et al worked on Urdu anaphora resolution but it appears to be the tip of an iceberg (Kalsoom and Rashida, 1993). Kulsoom et al (1993) only considered the morphological and lexical filters for the resolution of anaphora in Urdu discourses. However, these filters are not sufficient for Urdu anaphora resolution.
The rest of the paper is organized as follows: Section-2 describes the factors that play a vital role in Urdu anaphora resolution. Section-3 presents algorithms, implementation and evaluation for the resolution of personal anaphora; this is followed by the conclusion.

Factors that play vital role in Urdu anaphora resolution
Factors that can play a very important role in Urdu anaphora resolution beside morphological and lexical filters are topicalized structures, subject preferences, object preferences, repetitions, section heading and distance. How these factors are helpful in anaphora resolution in English language was worked out by Mitkov (Mitkov, 1998), but their role in Urdu discourse for the resolution of personal pronouns is more cherished. How these factors are helpful in the resolution of anaphoric devices in Urdu is done by Khan et al (Khan, Ali and Aamir, 2006). Ali et al also worked on these factors for the resolution of demonstrative ADs in Urdu discourse (Ali, Khan and Aamir, 2007).

Morphological and lexical filters
Consider an example in which anaphora is resolved on the basis of morphological filters. ). It must be noted that whenever topicalized structures appear in the Urdu discourses these become preferred antecedents for second person anaphoric devices.

Count of occurrences
It can be the case that in a particular discourse if a certain NP appears more frequently then it will be the potential antecedent for pronouns appearing in that text. For example, consider the following discourse Here the proper noun ‫ﻣﻨﭩﻮ‬ ([mΛntƱ]) appears repeatedly. So, on the basis of repetition, it will be the potential antecedent for most of personal pronouns e.g. ‫وﮦ‬ ([vәʊh]),‫اﺳﮯ‬ ([ʊseI])and ‫اﺳﮑﮯ‬ ([ʊskeI]) appearing in the above text.

Section headings
Section headings get high preference to become antecedents for most of personal pronouns in Urdu discourses. Consider the following example Shoaib Akhter Shoaib Akhter has become a burden over the cricket board. He is the only bowler in Pakistani cricket team who has not played much cricket rather always took rest because of being unfit. He is lucky to become popular only because he is the fastest bowler in the world. He is given more importance even compared to Imran.
In the above discourse, ‫اﺧﺘﺮ‬ ‫ﺷﻌﻴﺐ‬ ([∫Ʊaeb] [Λxtə(r)])is section heading, so it will be the preferred antecedent for most of anaphoric devices appearing in the discourse and all other NPs will be ruled out to become the potential antecedents.

Distance
Distance plays an important role in finding the antecedents. [mʊlzIm], [ʤΛʤ])of the main clause as their potential antecedents.
Here is an example in which for the resolution of third person anaphoric device ‫وﮦ‬ ([vǝƱh]), potential antecedents are found using subject preference filter. It is the ‫ﺳﻠﻤﯽ‬ who is looking beautiful not the ‫ﻣﺎں‬ ([ma:ñ]), since ‫ﺳﻠﻤﯽ‬ ([sΛlmɒ]) is followed by certain class of words.

Implementations and evaluations
An informal algorithm for the resolution of first person anaphoric devices is as follows: 1. Examine the next clause in the discourse. If no clause exists then finish. 2. If the current clause consists of first person anaphoric devices then go to step-3 else go to step-1. 3. Access the previous clause. 4. If the current clause consists of section headings, noun phrase followed by certain words then assign weight to these filters else assign priority to noun or noun phrase appearing as a subject of the clause. 5. If no subject exists then go to step-3.
Similarly, an informal algorithm for the resolution of second person ADs is as follows: 1. Examine the next clause in the discourse. If no clause exists then finish. 2. If the current clause consists of second person anaphoric devices then go to step-3 else go to step-1. 3. Access the previous clause. 4. If the current clause consists of topicalized structures then assign weight to these filters else assign priority to noun or noun phrase appearing as an object of the clause. 5. If no object exists then go to step-3.

Precision = Number of correctly resolved anaphors / Number of anaphors attempted to be resolved
The results of the three experiments are as follows Experiment# Precision 1 78% 2 80% 3 80% Table-1 shows that in case of first person anaphoric devices the priority has been assigned on the basis of section heading, noun phrase followed by certain words and then subject. It means that if no section heading or noun phrase followed by certain words are present then the subject in the main or previous clause will be the potential antecedent for first person anaphoric devices. Similarly, Table-2 for second person anaphoric devices, exhibits that weights will be assigned in descending order (left -right). It means that the leftmost filter that is topicalized structure will get the highest weight for second person ADs. Consider the following output (Fig-2) produced by anaphora resolution program, for the resolution of second person anaphoric device ‫ﺁﭘﮑﺎ‬ in the discourse 2.4, topicalized structure ‫ﺻﺎﺣﺐ‬ ‫ﮐﻬﺮ‬ gets high priority to become the antecedent.  Table-3 have been assigned in descending order (top -bottom). It means the weight of section heading filter will be larger in value than that of subject filter. Consider a noun or noun phrase which is section heading as well as a repeated noun and also lexical filter applies on it. For this noun or noun phrase all the weights will be summed up. A noun with highest weight will be given preference to become the antecedent for third person anaphoric device. This is demonstrated by the following output generated for discourse (2.8) by our anaphora resolution system. This discourse contains total 13 clauses from 0 -12. Clause 1 contains third person anaphoric device ‫اس‬ ([ʊs]) that is resolved to ‫ﻋﻠ‬ ‫اﻧﻮر‬ ‫ﯽ‬ which is assigned weight 12 on the basis of lexical filter and distance preference, so, ‫ﺳﺎﺗﻬ‬ ‫ﻴ‬ ‫ﻮں‬ is ruled out to become the antecedent since its weight is 1. Similarly for the third person anaphoric device ‫,وﮦ‬ that appears in clause 4, antecedent with highest weight 50 is ‫ﺳﺎﺗﻬ‬ ‫ﻴ‬ ‫ﻮں‬ . By the same token, for the resolution of the first person anaphoric device ‫ﻣ‬ ‫ﻴ‬ ‫ﺮا‬ , preference has been given to the noun ‫ﺳﺎﺗﻬ‬ ‫ﯽ‬ (Fig-2) that is the subject in the previous clause. [mƱ∫Λrf]) on the basis of distance and subject preference filter but ‫ان‬ (ʊn]) is not resolved correctly to have antecedent ‫ﻧﻮاز‬ ([nɒvɒz]).

Conclusion
One central question addressed in this paper is to determine the optimal order of the factors to find the preferred antecedents for the personal ADs in Urdu text. Rule based algorithms for the resolution of personal anaphoric devices are presented which are capable of resolving these anaphoric devices with 78-80% success rate in all kind of text genres. This success rate can be increased with improvement in certain rules especially for third person anaphoric devices.