Unsupervised Separation of Transliterable and Native Words for Malayalam
Deepak P

The Unmanned Aerial Vehicle Benchmark:
 Object Detection and Tracking
    ^1Dawei Du, ^2Yuankai Qi, ^2Hongyang Yu, ^1Yifan Yang, ^1Kaiwen Duan, ^1Guorong Li, ^3Weigang Zhang, ^1Qingming Huang, ^4Qi Tian
    December 30, 2023
====================================================================================================================================


Differentiating intrinsic language words from transliterable words is a key step aiding text processing tasks involving different natural languages. We consider the problem of unsupervised separation of transliterable words from native words for text in Malayalam language. Outlining a key observation on the diversity of characters beyond the word stem, we develop an optimization method to score words based on their nativeness. Our method relies on the usage of probability distributions over character n-grams that are refined in step with the nativeness scorings in an iterative optimization formulation. Using an empirical evaluation, we illustrate that our method, DTIM, provides significant improvements in nativeness scoring for Malayalam, establishing DTIM as the preferred method for the task. 



The Unmanned Aerial Vehicle Benchmark:
 Object Detection and Tracking
    ^1Dawei Du, ^2Yuankai Qi, ^2Hongyang Yu, ^1Yifan Yang, ^1Kaiwen Duan, ^1Guorong Li, ^3Weigang Zhang, ^1Qingming Huang, ^4Qi Tian
    December 30, 2023
====================================================================================================================================





§ INTRODUCTION


Malayalam is an agglutinative language from the southern Indian state of Kerala where it is the official state language. It is spoken by 38 million native speakers, three times as many speakers as Hungarian <cit.> or Greek <cit.>, for which specialized techniques have been developed in other contexts. The growing web presence of Malayalam necessitates automatic techniques to process Malayalam text. A major hurdle in harnessing Malayalam text from social and web media for multi-lingual retrieval and machine translation is the presence of a large amount of transliterable words. By transliterable words, we mean both (a) words (from English) like police and train that virtually always appear in transliterated form in contemporary Malayalam, and (b) proper nouns such as names that need to be transliterated than translated to correlate with English text. On a manual analysis of a news article dataset, we found that transliterated words and proper nouns each form 10-12% of all distinct words. It is useful to transliterate such words for scenarios that involve processing Malayalam text in the company of English text;  this will avoid them being treated as separate index terms (wrt their transliteration) in a multi-lingual retrieval engine, and help a statistical translation system to make use of the link to improve effectiveness. In this context, it ia notable that there has been recent interest in devising specialized methods to translate words that fall outside the core vocabulary <cit.>. 


In this paper, we consider the problem of separating out such transliterable words from the other words within an unlabeled dataset; we refer to the latter as “native” words. We propose an unsupervised method, DTIM, that takes a dictionary of distinct words from a Malayalam corpus and scores each word based on their nativeness. Our optimization method, DTIM, iteratively refines the nativeness scoring of each word, leveraging dictionary-level statistics modelled using character n-gram probability distributions. Our empirical analysis establishes the effectiveness of DTIM. 


We outline related work in the area in Section <ref>. This is followed by the problem statement in Section <ref> and the description of our proposed approach in Section <ref>. Our empirical analysis forms Section <ref> followed by conclusions in Section <ref>. 



§ RELATED WORK


Identification of transliterable text fragments, being a critical task for cross-lingual text analysis, has attracted attention since the 1990s. While most methods addressing the problem have used supervised learning, there have been some methods that can work without labeled data. We briefly survey both classes of methods. 








 §.§  Supervised and `pseudo-supervised' Methods




An early work<cit.> focuses on a sub-problem, that of supervised identification of proper nouns for Chinese. <cit.> consider leveraging decision trees to address the related problem of learning transliteration and back-transliteration rules for English/Korean word pairs. Recognizing the costs of procuring training data, <cit.> and <cit.> explore usage of pseudo-transliterable words generated using transliteration rules on an English dictionary for Korean and Hebrew respectively. Such pseudo-supervision, however, would not be able to generate uncommon domain-specific terms such as medical/scientific terminology for usage in such domains (unless specifically tuned), and is hence limited in utility. 



 §.§ Unsupervised Methods


A recent work proposes that multi-word phrases in Malayalam text where their component words exhibit strong co-occurrence be categorized as transliterable phrases <cit.>. Their intuition stems from observing contiguous words such as test dose which often occur in transliterated form while occurring together, but get replaced by native words in other contexts. Their method is however unable to identify single transliterable words, or phrases involving words such as train and police whose transliterations are heavily used in the company of native Malayalam words. A recent method for Korean <cit.> starts by identifying a seed set of transliterable words as those that begin or end with consonant clusters and have vowel insertions; this is specific to Korean since Korean words apparently do not begin or end with consonant clusters. High-frequency words are then used as seed words for native Korean for usage in a Naive Bayes classifier. In addition to the outlined reasons that make both the unsupervised methods inapplicable for our task, they both presume availability of corpus frequency statistics. We focus on a general scenario assuming the availability of only a word lexicon.








 §.§ Positioning the Transliterable Word Identification Task
 

Nativeness scoring of words may be seen as a vocabulary stratification step (upon usage of thresholds) for usage by downstream applications. A multi-lingual text mining application that uses Malayalam and English text would benefit by transliterating non-native Malayalam words to English, so the transliterable Malayalam token and its transliteration is treated as the same token. For machine translation, transliterable words may be channeled to specialized translation methods (e.g., <cit.>) or for manual screening and translation. 



§ PROBLEM DEFINITION


We now define the problem more formally. Consider n distinct words obtained from Malayalam text, 𝒲 = {…, w, …}. Our task is to devise a technique that can use 𝒲 to arrive at a nativeness score for each word, w, within it, as w_n. We would like w_n to be an accurate quantification of native-ness of word w. For example, when words in 𝒲 are ordered in the decreasing order of w_n scores, we expect to get the native words at the beginning of the ordering and vice versa. We do not presume availability of any data other than 𝒲; this makes our method applicable across scenarios where corpus statistics are unavailable due to privacy or other reasons. 



 §.§ Evaluation


Given that it is easier for humans to crisply classify each word as either native or transliterable (nouns or transliterated english words) in lieu of attaching a score to each word, the nativeness scoring (as generated by a scoring method such as ours) often needs to be evaluated against a crisp nativeness assessment, i.e., a scoring with scores in {0, 1}. To aid this, we consider the ordering of words in the labeled set in the decreasing (or more precisely, non-increasing) order of nativeness scores (each method produces an ordering for the dataset). To evaluate this ordering, we use two sets of metrics for evaluation: 





  * Precision at the ends of the ordering: Top-k precision denotes the fraction of native words within the k words at the top of the ordering; analogously, Bottom-k precision is the fraction of transliterable words among the bottom k. Since a good scoring would likely put native words at the top of the ordering and the transliterable ones at the bottom, a good scoring method would intuitively score high on both these metrics. We call the average of the top-k and bottom-k precision for a given k, as Avg-k precision. These measures, evaluated at varying values of k, indicate the quality of the nativeness scoring. 


  * Clustering Quality: Consider the cardinalities of the native and transliterable words from the labeled set as being N and T respectively. We now take the top-N words and bottom-T words from the ordering generated by each method, and compare against the respective labeled sets as in the case of standard clustering quality evaluation[<https://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html>]. Since the cardinalities of the generated native (transliterable) cluster and the native (transliterable) labeled set is both N (T), the Recall of the cluster is identical to its Purity/Precision, and thus, the F-measure too; we simply call it Clustering Quality. A cardinality-weighted average of the clustering quality across the native and transliterable clusters yields a single value for the clustering quality across the dataset. It may be noted that we are not making the labeled dataset available to the method generating the ordering, instead merely using it's cardinalities for evaluation purposes. 










§ OUR METHOD: DTIM


We now introduce our method, Diversity-based Transliterable Word Identification for Malayalam (DTIM). We use probability distributions over character n-grams to separately model transliterable and native words, and develop an optimization framework that alternatively refines the n-gram distributions and nativeness scoring within each iteration. DTIM involves an initialization that induces a “coarse” separation between native and transliterable words followed by iterative refinement. The initialization is critical in optimization methods that are vulnerable to local optima; the pure word distribution needs to be initialized to “coarsely” prefer pure words over transliterable words. This will enable further iterations to exploit the initial preference direction to further refine the model to “attract” the pure words more strongly and weaken any initial preference to transliterable words. The vice versa holds for the transliterable word models. We will first outline the initialization step followed by the description of the method. 







 §.§ Diversity-based Initialization




Our initialization is inspired by an observation on the variety of suffixes attached to a word stem. Consider a word stem |pu|ra|[We will represent Malayalam words in transliterated form for reading by those who might not be able to read Malayalam. A pipe would separate Malayalam characters; for example |pu| corresponds to a single Malayalam character. ], a stem commonly leading to native Malayalam words; its suffixes are observed to start with a variety of characters such as |ttha| (e.g., |pu|ra|ttha|kki|), |me| (e.g., |pu|ra|me|), |mbo| (e.g., |pu|ra|mbo|kku|) and |ppa| (e.g., |pu|ra|ppa|du|). On the other hand, stems that mostly lead to transliterable words often do not exhibit so much of diversity. For example, |re|so| is followed only by |rt| (i.e., resort) and |po|li| is usually only followed by |s| (i.e., police). Some stems such as |o|ppa| lead to transliterations of two English words such as open and operation. Our observation, upon which we model the initialization, is that the variety of suffixes is generally correlated with native-ness (i.e., propensity to lead to a native word) of word stems. This is intuitive since non-native word stems provide limited flexibility to being modified by derivational or inflectional suffixes as compared to native ones. 

For simplicity, we use the first two characters of each word as the word stem; we will evaluate the robustness of DTIM to varying stem lengths in our empirical evaluation, while consistently using the stem length of two characters in our description. We start by associating each distinct word stem in 𝒲 with the number of unique third characters that follow it (among words in 𝒲); in our examples, |pu|ra| and |o|pa| would be associated with 4 and 2 respectively. We initialize the native-ness weights as proportional to the diversity of 3^rd characters beyond the stem:




    w_n_0 = min{ 0.99, |u3(w_stem,𝒲)|/τ}




where u3(w_stem,𝒲) denotes the set of third characters that follow the stem of word w among words in 𝒲. We flatten off w_n_0 scores beyond a diversity of τ (note that a diversity of τ or higher will lead to the second term becoming 1.0 or higher, kicking in the min function to choose 0.99 for w_n_0) as shown in the above equation. We give a small transliterable-ness weight even to highly diverse stems to reduce over-reliance on the initialization. We set τ = 10 based on our observation from the dataset that most word stems having more than 10 distinct characters were seen to be native. As in the case of word stem length, we study DTIM trends across varying τ in our empirical analysis. w_n_0 is in [0,1]; analogously, (1-w_n_0) may be regarded as a score of transliterable-ness. 



 §.§ Objective Function and Optimization Framework


As outlined earlier, we use separate character n-gram probability distributions to model native and transliterable words. We would like these probability distributions support the nativeness scoring, and vice versa. While the size of the n-grams (i.e., whether n=1,2,3 or 4) is a system-level parameter, we use n=1 for simplicity in our description. We denote the native and transliterable distributions as 𝒩 and 𝒯 respectively, with 𝒩(c) and 𝒯(c) denoting the weight associated with the character c according to the distributions. Consider the following function, given a particular state for the 𝒩, 𝒯 and w_ns:


    ∏_w ∈𝒲∏_c ∈ w(  w_n^2 ×𝒩(c) + (1-w_n)^2 ×𝒯(c) )


This measures the aggregate supports for words in 𝒲, the support for each word measured as an interpolated support from across the distributions 𝒩 and 𝒯 with weighting factors squares of the nativeness scores (i.e., w_ns) and transliterableness scores (i.e., (1-w_n)s) respectively. Similar mixing models have been used earlier in emotion lexicon learning <cit.> and solution post discovery <cit.>. The squares of the nativeness scores are used in our model (instead of the raw scores) for optimization convenience. A highly native word should intuively have a high w_n (nativeness) and a high support from 𝒩 and correspondingly low transliterable-ness (i.e., (1-w_n)) and support from 𝒯; a highly transliterable word would be expected to have exactly the opposite. Due to the design of Eq. <ref> in having the higher terms multiplied with each other (and so for the lower terms), this function would be maximized for a desirable estimate of the variables θ = {𝒩, 𝒯, {…, w_n, …}}. Conversely, by striving to maximize the objective function, we would arrive at a desirable estimate of the variables. An alternative construction yielding a minimizing objective would be as follows:


    ∏_w ∈𝒲∏_c ∈ w(  (1-w_n)^2 ×𝒩(c) + w_n^2 ×𝒯(c) )


In this form, given a good estimate of the variables, the native (transliterable) words have their nativeness (transliterableness) weights multiplied with the support from the transliterable (native) models. In other words, maximizing the objective in Eq. <ref> is semantically similar to minimizing the objective in Eq. <ref>. As we will illustrate soon, it is easier to optimize for 𝒩 and 𝒯 using the maximizing formulation in Eq. <ref> while the minimizing objective in Eq. <ref> yields better to optimize for the word nativeness scores, {…, w_n, …}. 



 §.§ Learning 𝒩 and 𝒯 using the Maximizing Objective


We start by taking the log-form of the objective in Eq. <ref> (this does not affect the optimization direction), yielding:


    𝒪_max = ∑_w ∈𝒲∑_c ∈ w ln (  w_n^2 ×𝒩(c) + (1-w_n)^2 ×𝒯(c) )


The distributions, being probability distributions over n-grams, should sum to zero. This constraint, for our unigram models, can be written as:


    ∑_c𝒩(c) = ∑_c𝒯(c) = 1


Fixing the values of {…, w_n, …} and 𝒯 (or 𝒩), we can now identify a better estimate for 𝒩 (or 𝒯) by looking for an optima (i.e., where the objective function has a slope of zero). Towards that, we take the partial derivative (or slope) of the objective for a particular character. :


    ∂𝒪_max/∂𝒩(c') = ( ∑_w ∈𝒲freq(c',w) × w_n^2/( w_n^2 𝒩(c') + (1-w_n)^2 𝒯(c'))) + λ_𝒩


where freq(c',w) is the frequency of the character c' in w and λ_𝒩 denotes the Lagrangian multiplier corresponding to the sum-to-unity constraint for 𝒩. Equating this to zero does not however yield a closed form solution for 𝒩', but a simple re-arrangement yields an iterative update formula:


    𝒩(c') ∝∑_w ∈𝒲freq(c',w) × w_n^2/( w_n^2 + (1-w_n)^2 𝒯(c')/𝒩_P(c'))


The 𝒩 term in the RHS is denoted as 𝒩_P to indicate the usage of the previous estimate of 𝒩. The sum-to-one constraint is trivially achieved by first estimating the 𝒩(c')s by treating Eq. <ref> as equality, followed by normalizing the scores across the character vocabulary. Eq. <ref> is intuitively reasonable, due to establishing a somewhat direct relationship between 𝒩 and w_n (in the numerator), thus allowing highly native words to contribute more to building 𝒩. The analogous update formula for 𝒯 fixing 𝒩 turns out to be:


    𝒯(c') ∝∑_w ∈𝒲freq(c',w) × (1-w_n)^2/( (1-w_n)^2 + w_n^2 𝒩(c')/𝒯_P(c'))


Eq. <ref> and Eq. <ref> would lead us closer to a maxima for Eq. <ref> is their second (partial) derivatives are negative[<http://mathworld.wolfram.com/SecondDerivativeTest.html>]. To verify this, we note that the second (partial) derivative wrt 𝒩(c') is as follows


    ∂^2 𝒪_max/∂^2 𝒩(c') =






    (-1) ×∑_w ∈𝒲freq(c',w) (w_n^2)^2/( w_n^2 𝒩(c') + (1-w_n)^2 𝒯(c'))^2


It is easy to observe that the RHS is a product of -1 and a sum of a plurality of positive terms (square terms that are trivially positive, with the exception being the freq(.,.) term which is also non-negative by definition), altogether yielding a negative value. That the the second (partial) derivative is negative confirms that the update formula derived from the first partial derivative indeed helps in maximizing 𝒪_max wrt 𝒩(c'). A similar argument holds for the 𝒯(c') updates as well, which we omit for brevity. 



 §.§ Learning the nativeness scores, {…, w_n, …}, using the Minimizing Objective


Analogous to the previous section, we take the log-form of Eq. <ref>:


    𝒪_min = ∑_w ∈𝒲∑_c ∈ w ln (  (1-w_n)^2 ×𝒩(c) + w_n^2 ×𝒯(c) )


Unlike the earlier case, we do not have any constraints since the sum-to-unit constraint on the nativeness and transliterableness scores are built in into the construction. We now fix the values of all other variables and find the slope wrt w'_n, where w' indicates a particular word in 𝒲. 


    ∂𝒪_min/∂ w'_n = ∑_c ∈ w'2 w'_n 𝒯(c) + 2 w'_n 𝒩(c)  - 2 𝒩(c)/(w'^2_n 𝒯(c)  + (1-w'_n)^2 𝒩(c))


We equate the slope to zero and form an iterative update formula, much like in the distribution estimation phase. 


    w'_n = ∑_c ∈ w'𝒩(c)/(w'^2_n 𝒯(c)  + (1-w'_n)^2 𝒩(c) )/∑_c ∈ w'𝒩(c) + 𝒯(c)/(w'^2_n 𝒯(c)  + (1-w'_n)^2 𝒩(c) )


Using the previous estimates of w'_n for the RHS yields an iterative update form for the nativeness scores. As in the model estimation phase, the update rule establishes a reasonably direct relationship between w'_n and 𝒩. Since our objective is to minimize 𝒪_min, we would like to verify the direction of optimization using the second partial derivative. 


    ∂^2 𝒪_min/∂^2 w'_n =






    ∑_c ∈ w'𝒩(c) 𝒯(c) - (w'_n 𝒯(c) - (1-w'_n) 𝒩(c))^2/(w'^2_n 𝒯(c)  + (1-w'_n)^2 𝒩(c))^2


We provide an informal argument for the positivity of the second derivative; note that the denominator is a square term making it enough to analyze just the numerator term. Consider a highly native word (high w'_n) whose characters would intuitively satisfy 𝒩(c) > 𝒯(c). For the boundary case of w'_n = 1, the numerator term reduces to 𝒯(c) × (𝒩(c) - 𝒯(c)) which would be positive given the expected relation between 𝒩(c) and 𝒯(c). A similar argument holds for highly transliterable words. For words with w'_n → 0.5 where we would expect 𝒩(c) ≈𝒯(c), the numerator becomes 𝒩(c) 𝒯(c) - 0.25 (𝒯(c) - 𝒩(c))^2, which is expected to be positive since the difference term is small, making it's square very small in comparison to the first product term. To outline the informal nature of the argument, it may be noted that 𝒯(c) > 𝒩(c) may hold for certain characters within highly native words; but as long as most of the characters within highly native words satisfy the 𝒩(c) > 𝒯(c), there would be sufficient positivity to offset the negative terms induced with such outlier characters. 





 §.§ DTIM: The Method


Having outlined the learning steps, the method is simply an iterative usage of the learning steps as outlined in Algorithm <ref>. In the first invocation of the distribution learning step where previous estimates are not available, we simply assume a uniform distribution across the n-gram vocabulary for usage as the previous estimates. Each of the update steps are linear in the size of the dictionary, making DTIM a computationally light-weight method. Choosing n=2 instead of unigrams (as used in our narrative) is easy since that simply involves replacing the c ∈ w all across the update steps by [c_i, c_i+1] ∈ w with [c_i, c_i+1] denoting pairs of contiguous characters within the word; similarly, n=3 involves usage of contiguous character triplets and correspondingly learning the distributions 𝒩 and 𝒯 over triplets. The DTIM structure is evidently inspired by the Expectation-Maximization framework <cit.> involving alternating optimizations of an objective function; DTIM, however, uses different objective functions for the two steps for optimization convenience. 
























































































§ EXPERIMENTS


We now describe our empirical study of DTIM, starting with the dataset and experimental setup leading on to the results and analyses. 



 §.§ Dataset


We evaluate DTIM on a set of 65068 distinct words from across news articles sourced from Mathrubhumi[<http://www.mathrubhumi.com>], a popular Malayalam newspaper; this word list is made available publicly[Dataset: <https://goo.gl/DOsFES>]. For evaluation purposes, we got a random subset of 1035 words labeled by one of three human annotators; that has been made available publicly[Labeled Set: <https://goo.gl/XEVLWv>] too, each word labeled as either native, transliterable or unknown. There were approximately 3 native words for every transliterable word in the labeled set, reflective of distribution in contemporary Malayalam usage as alluded to in the introduction. We will use the whole set of 65068 words as input to the method, while the evaluation would obviously be limited to the labelled subset of 1035 words. 





 §.§ Baselines
 

As outlined in Section <ref>, the unsupervised version of the problem of telling apart native and transliterable words for Malayalam and/or similar languages has not been addressed in literature, to the best of our knowledge. The unsupervised Malayalam-focused method<cit.> (Ref: Sec <ref>) is able to identify only transliterable word-pairs, making it inapplicable for contexts such as a health data scenario where individual english words are often transliterated for want of a suitable malayalam alternative. The Korean method<cit.> is too specific to Korean language and cannot be used for other languages due to the absence of a generic high-precision rule to identify a seed set of transliterable words. With both the unsupervised state-of-the-art approaches being inapplicable for our task, we compare against an intuitive generalization-based baseline, called GEN, that orders words based on their support from the combination of a unigram and bi-gram character language model learnt over 𝒲; this leads to a scoring as follows:


    w_n^GEN =






    ∏_[c_i, c_i+1] ∈ wλ× B_𝒲(c_i+1|c_i) + (1-λ) × U_𝒲(c_i+1)


where B_𝒲 and U_𝒲 are bigram and unigram character-level language models built over all words in 𝒲. We set λ = 0.8 <cit.>. We experimented with higher-order models in GEN, but observed drops in evaluation measures leading to us sticking to the usage of the unigram and bi-gram models. The form of Eq. <ref> is inspired by an assumption similar to that used in both <cit.> and <cit.> that transliterable words are rare. Thus, we expect they would not be adequately supported by models that generalize over whole of 𝒲. We also compare against our diversity-based initialization score from Section <ref>, which we will call as INIT. For ease of reference, we outline the INIT scoring:


    w_n^INIT = min{ 0.99, |u3(w_stem,𝒲)|/τ}


The comparison against INIT enables us to isolate and highlight the value of the iterative update formulation vis-a-vis the initialization. 



 §.§ Evaluation Measures and Setup


As outlined in Section <ref>, we use top-k, bottom-k and avg-k precision (evaluated at varying values of k) as well as clustering quality in our evaluation. For the comparative evaluaton, we set DTIM parameters as the following: τ = 10 and a word-stem length of 2. We will study trends against variations across these parameters in a separate section. 
























 §.§ Experimental Results




  §.§.§ Precision at the ends of the Ordering
 

Table <ref> lists the precision measures over various values of k. It may be noted that any instantiation of DTIM (across the four values of n-gram size, n) is able to beat the baselines convincingly on each metric on each value of k, convincingly establishing the effectiveness of the DTIM formulation. DTIM is seen to be much more effective in separating out the native and transliterable words at either ends of the ordering, than the baselines. It is also notable that EM-style iterations are able to significantly improve upon the initialization (i.e., INIT). That the bottom-k precision is seen to be consistently lower than top-k precision needs to be juxtaposed in the context of the observation that there were only 25% transliterable words against 75% native words; thus, the lift in precision against a random ordering is much more substantial for the transliterable words. The trends across varying n-gram sizes (i.e., n) in DTIM is worth noting too; the higher values of n (such as 3 and 4) are seen to make more errors at the ends of the lists, whereas they catch-up with the n∈{1,2} versions as k increases. This indicates that smaller-n DTIM is being able to tell apart a minority of the words exceedingly well (wrt native-ness), whereas the higher n-gram modelling is able to spread out the gains across a larger spectrum of words in 𝒲. Around n=4 and beyond, sparsity effects (since 4-grams and 5-grams would not occur frequently, making it harder to exploit their occurrence statistics) are seen to kick in, causing reductions in precision. 







  §.§.§ Clustering Quality
 

Table <ref> lists the clustering quality metric across the various methods. Clustering quality, unlike the precision metrics, is designed to evaluate the entire ordering without limiting the analysis to just the top-k and bottom-k entries. As in the earlier case, DTIM convincingly outperforms the baselines by healthy margins across all values of n. Consequent to the trends across n as observed earlier, n ∈{3,4} are seen to deliver better accuracies, with such gains tapering off beyond n=4 due to sparsity effects. The words, along with the DTIM nativeness scores for n=3, can be viewed at <https://goo.gl/OmhlB3> (the list excludes words with fewer than 3 characters). 
















 §.§ Analyzing DTIM


We now analyze the performance of DTIM across varying values of the diversity threshold (τ) and word-stem lengths. 



  §.§.§ Diversity Threshold


Table <ref> analyzes the clustering quality trends of DTIM across varying values of τ. The table suggests that DTIM is extremely robust to variations in diversity threshold, despite a slight preference towards values around 10 and 20. This suggests that a system designer looking to use DTIM need not carefully tune this parameter due to the inherent robustness. 



  §.§.§ Word Stem Length


Given the nature of Malayalam language where the variations in word lengths are not as high as in English, it seemed very natural to use a word stem length of 2. Moreover, very large words are uncommon in Malayalam. In our corpus, 50% of words were found to contain five characters or less, the corresponding fraction being 71% for upto seven characters. Our analysis of DTIM across variations in word-stem length, illustrated in Table <ref> strongly supports this intuition with clustering quality peaking at stem-length of 2 for n ≥ 2. It is notable, however, that DTIM degrades gracefully on either side of 2. Trends across different settings of word-stem length are interesting since they may provide clues about applicability for other languages with varying character granularities (e.g., each Chinese character corresponds to multiple characters in Latin-script). 







§ DISCUSSION




 §.§ Applicability to Other Languages
 

In contrast to earlier work focused on specific languages (e.g., <cit.>) that use heuristics that are very specific to the language (such as expected patterns of consonants), DTIM heuristics are general-purpose in design. The only heuristic setting that is likely to require some tuning for applicability in other languages is the word-stem length. We expect the approach would generalize well to other Sanskrit-influenced Dravidian languages such as Kannada/Telugu. Unfortunately, we did not have any Kannada/Telugu/Kodava knowledge (Dravidian languages have largely disjoint speaker-populations) in our team, or access to labelled datasets in those languages (they are low-resource languages too); testing this on Kannada/Telugu/Tamil would be interesting future work. The method is expected to be less applicable to English, the language being significantly different and with potentially fewer transliterable words. 



 §.§ DTIM in an Application Context
 

Within any target application context, machine-labelled transliterable words (and their automatically generated transliterations) may need to manual screening for accountability reasons. The high accuracy at either ends of the ordering lends itself to be exploited in the following fashion; in lieu of employing experts to verify all labellings/transliterations, low-expertise volunteers (e.g., students) can be called in to verify labellings at the ends (top/bottom) of the lists with experts focusing on the middle (more ambiguous) part of the list; this frees up experts’ time as against a cross-spectrum expert-verification process, leading to direct cost savings. We also expect that DTIM followed by automatic transliterations of bottom-k words would aid in retrieval and machine translation scenarios. 






§ CONCLUSIONS AND FUTURE WORK


We considered the problem of unsupervised separation of transliterable and native words in Malayalam, a critical task in easing automated processing of Malayalam text in the company of other language text. We outlined a key observation on the differential diversity beyond word stems, and formulated an initialization heuristic that would coarsely separate native and transliterable words. We proposed the usage of probability distributions over character n-grams as a way of separately modelling native and transliterable words. We then formulated an iterative optimization method that alternatively refines the nativeness scorings and probability distributions. Our technique for the problem, DTIM, that encompasses the initialization and iterative refinement, was seen to significantly outperform other unsupervised baseline methods in our empirical study. This establishes DTIM as the preferred method for the task. We have also released our datasets and labeled subset to help aid future research on this and related tasks. 





 §.§ Future Work


The applicability of DTIM to other Dravidian languages is interesting to study. Due to our lack of familiarity with any other language in the family, we look forward to contacting other groups to further the generalizability study. While nativeness scoring improvements directly translate to reduction of effort for manual downstream processing, quantifying gains these bring about in translation and retrieval is interesting future work. Exploring the relationship/synergy of this task and Sandhi splitting <cit.> would form another interesting direction for future work. Further, we would like to develop methods to separate out the two categories of transliterable words, viz., foreign language words and proper nouns. Such a method would enable a more fine-grained stratification of the vocabulary. 

Transliterable words are often within Malayalam used to refer to very topical content, for which suitable words are harder to find. Thus, transliterable words could be preferentially treated towards building rules in interpretable clustering <cit.> and for modelling context in regex-oriented rule-based information extraction <cit.>. Transliterable words might also hold cues for detecting segment boundaries in conversational transcripts <cit.>. 













acl

