Word Segmentation in Sanskrit Using Path Constrained Random Walks

Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 494–504, Osaka, Japan, December 11-17 2016. Word Segmentation in Sanskrit Using Path Constrained Random Walks Amrith Krishna, Bishal Santra*, Pavankumar Satuluri, Sasi Prasanth Bandaru#, Bhumi Faldu, Yajuvendra Singh## and Pawan Goyal *Dept. of Electronics & Electrical Communication Engineering, #Dept. of Electrical Engineering, ##Dept. of Mathematics, Dept. of Computer Science & Engineering Indian Institute of Technology, Kharagpur, WB, India amrith@iitkgp.ac.in Abstract In Sanskrit, the phonemes at the word boundaries undergo changes to form new phonemes through a process called as sandhi. A fused sentence can be segmented into multiple possible segmentations. We propose a word segmentation approach that predicts the most semantically valid segmentation for a given sentence. We treat the problem as a query expansion problem and use the path-constrained random walks framework to predict the correct segments. 1 Introduction Word segmentation is an essential step for most of the text processing tasks. In Sanskrit texts, it is very common that the phonemes at the word boundaries undergo changes to form new phonemes, through a process termed sandhi. It also makes the word boundary between the words that undergo sandhi, in- distinguishable. Proximity between phonemes (sam. hit¯a) is the sole criteria for applying sandhi, thus phonetic transformation takes place between two consecutive words. This poses a big challenge in iden- tifying individual words in a given sentence, as the same fused form can be segmented into many possible segmentations. Though, there has been considerable advancements in tackling word segmentation chal- lenges faced in other languages including Chinese, Korean and Arabic, a direct application of those approaches is not possible in Sanskrit texts due to the phenomena of sandhi. Since the sandhi rules are well documented in the tradition, all the syntactically valid segmentations (splits) of a given sentence in Sanskrit can be enumerated. Sanskrit Heritage Reader provides a nice compact interface to show all the valid solutions (Huet and Goyal, 2013). The main challenge is to identify the most relevant solution from all the possible segmentations. The relevance of contextual information in identifying semantically relevant segments is a well-accepted fact (Hellwig, 2009). Mittal (2010), Natarajan and Charniak (2011) have successfully applied statistical methods for sandhi splitting in Sanskrit. But, both the approaches relied heavily on word co-occurrence features as their context with minimal usage of the morphological information. We, unlike the previous methods, propose a segmentation approach which effectively com- bines the morphological features in addition to the word co-occurrence features from a manually tagged corpus of more than 400,000 sentences (Hellwig, 2009). We treat the problem as a query expansion problem that iteratively selects a segment amongst the competing segmentations and then continues to select the next correct segment with the information from extended context. The algorithm terminates when no more candidates remain to be evaluated. We use the scalable “path-constrained random walks (PCRW)” (Lao and Cohen, 2010) framework with linguistically motivated Inductive Logic Programming (ILP) formulations for finding the correct segmentation. Using extensive experiments, …

Content truncated to 500 words