\documentclass[10pt,a4paper,twoside,final]{article}
%general packages
\usepackage[round]{natbib}
\usepackage{color}
\usepackage{supertabular}
\usepackage{setspace}
\usepackage{graphicx}
\usepackage{lettrine}
\usepackage{picture}
\usepackage{bar}
\usepackage{multirow}
\usepackage[preprocess]{itrans}
\usepackage[colorlinks=false,urlcolor=blue,anchorcolor=blue,
                     anchorcolor=blue,filecolor=blue,linkcolor=blue,
                     citecolor=blue]{hyperref}
\usepackage[english]{babel}
\usepackage{floatflt,graphicx}

%%%%%%%%%% switches %%%%%%%%%%%%%%%%%%%%%%%%

\textwidth 6.5in
\textheight 9.35in
\oddsidemargin 0.1in
\evensidemargin 0.1in
\topskip 0.30in
\footskip 0.2in
\topmargin -1.1cm
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt}
\setlength{\parsep}{0pt}
\setlength{\headsep}{0pt}
\setlength{\topskip}{0pt}
\setlength{\topmargin}{0pt}
\setlength{\topsep}{0pt}
\setlength{\partopsep}{0pt}
\makeatletter
\renewcommand\section{\@startsection{section}{1}{\z@}%
                                  {-1ex \@plus -1ex \@minus -.2ex}%
                                  {1ex \@plus.2ex}%
                                  {\normalfont\large\bfseries}}
\makeatother
\sloppy

\tolerance=5000

%%%%% GATE utilities %%%%%%%%%%%%%%%%%%%%%%%%%
\input{../utils}

%%%%%%%%%%%% the document %%%%%%%%%

\begin{document}
\pagenumbering{arabic}
\pagestyle{empty}
\begin{center}
\Large
{\bf English-Hindi Transliteration using Multiple Similarity Metrics} \\
\large
Niraj Aswani and Robert Gaizauskas \\
\normalsize
n.aswani@dcs.shef.ac.uk r.gaizauskas@dcs.shef.ac.uk \\
University of Sheffield \\
\end{center}

\large
{\bf Abstract} \\
\normalsize
In this paper, we present an approach to measure the transliteration similarity 
of English-Hindi word pairs. Our approach has two components. First we propose
a bi-directional mapping between one or more characters in the Devanagari script
and one or more characters in the Roman script (pronounced as in English). This 
allows a given Hindi word written in Devanagari to be transliterated into the 
Roman script and vice-versa.  Second, we present an algorithm for computing a 
similarity measure that is a variant of Dice's coefficient measure and the LCSR 
measure and which also takes into account the constraints needed to match 
English-Hindi transliterated words. Finally, by evaluating various similarity 
metrics individually and together under a  multiple measure agreement scenario, 
we show that it is possible to achieve a 0.92 f-measure in identifying 
English-Hindi word pairs that are transliterations.  In order to assess the 
portability of our approach to other similar languages we adapt our system to 
the Gujarati language.

\section{Introduction}

In India, English is one of the most widespread foreign languages. It is 
becoming very common for people to use both English and Hindi vocabulary in 
the same sentence \citep{Clair02}. When writing such mixed code sentences, 
people use the Devanagari script to write Hindi words and use equivalent Hindi 
transliterations for the English words. There are many words in Hindi which have
been derived from the English (e.g. \textit{School, Doctor}) and vice-versa 
(e.g. \textit{Bungalow}). Apart from such cognates, named entities such as 
person names, names of places, organizations are other types of words that 
need transcribing into another writing system \citep{Kondrak03}. We estimate 
that in the EMILLE English-Hindi corpora approximately 7\% of words are 
transliterations.

In this paper, we present a Transliteration Similarity metric (TSM) that is 
based on the letter correspondences between the writing systems of the English 
and the Hindi languages.  It is a part of our effort to develop a general 
framework for text alignment \citep{Aswani09} where it is currently used in 
an English-Hindi word alignment system for aligning words such as proper 
names and cognates. We give a mapping for one or more characters in the 
Devanagari script into one or more characters in the Roman script. Given a Hindi
word, this mapping allows one or more candidate transliterated forms in the 
Roman script to be obtained. To choose which of these candidates most closely 
matches a candidate target word requires a string similarity measure. We review 
some of the well known string similarity metrics and propose an algorithm for 
computing a similarity measure. We evaluate the performance of these similarity 
metrics individually and in various combinations to discover the best 
combination of similarity metrics and a threshold value that can be used to 
maintain the optimal balance between accuracy and coverage.  To test the 
portability of our approach to other similar languages we adapt our system to 
the Gujarati language. 

\section{Our Approach}

Figure \ref{fig:mainmapping} lists letter correspondences between the writing 
systems of the two languages where one or more Hindi characters are associated 
with one or more English characters. For example $[$f$]$ can be f, or ph (e.g. 
frame, photo).  This transliteration mapping (TM) was derived manually and 
provides a two way lookup facility. The following illustration explains how to use 
the TM to obtain possible transliterations for the Hindi word $[$kensar$]$ which 
means \textit{cancer} in English. For Hindi letter at the $i^{th}$ position in the 
Hindi word HW (where $i = 1..n$ and $n = |HW|$ (i.e. the length of HW)), we 
define a set $TS_i$ that contains all possible phonetic mappings for that letter.  

\begin{figure}[th]
\centering
{\includegraphics[height=9cm]{img/e-h-mappings}}
\caption{English-Hindi Transliteration mapping} 
\label{fig:mainmapping}
\end{figure} 

In order to optimize the process, we remove from the $TS_i$ all mapped 
characters that do not exist in the candidate target string. Below, we list 
mappings for the letters of the word $[$kensar$]$.  The mappings which need to 
be removed from the $TS_i$ are enclosed in round brackets: $[$k$]$ = $[$c, (k), 
(ch)$]$; $[$e$]$ = $[$e, a, (ai)$]$; $[$n$]$ = $[$n$]$; $[$s$]$ = $[$c,(s)$]$; 
$[$r$]$ = $[$r$]$.  From these mappings we define a set $TS$ of n-tuples such 
that $TS = TS_1 \times TS_2 \times ...  \times TS_n$ (i.e. $TS$ is a Cartesian 
product of all the previously defined sets ($TS_{i=1..n}$) for each letter in 
the Hindi word). Each n-tuple in $TS$ is one possible transliteration of the 
original Hindi word.  In total there are $|TS|$ transliterated strings. In the 
above example the value of $|TS|$ is 2 (1 x 2 x 1 x 1 x 1) (i.e. Cencr and 
Cancr). Each transliterated string ($S_{j=1.. |TS| \in TS}$) is compared with the
English word using one of the string similarity metrics (explained in the next 
section).  If the English word and any of the transliterated strings has a similarity
score above a specified threshold, the strings are deemed to be transliterations. 

\section{String Similarity Metrics}

Given a pair of strings, string similarity metrics give us a measure of how 
similar the two strings are.  The matching coefficient is the simplest measure 
of all, where only the count of characters that match is taken as the similarity 
measure. There are different variants of the matching coefficient such as Dice's
coefficient (DC) and overlap coefficient.  However, for these measures the 
number of matching characters is more important than positions of the 
characters.  In case of LCSR (Longest Common Subsequence Ratio) and 
n-gram similarity metrics, the position of characters is also taken into 
consideration. The Levenshtein distance measure (LD) \citep{Levenshtein66} 
is used for calculating the minimum number of edit operations needed to 
transform one string into an other.  In case of the Jaro-Winkler metric (JW) 
\citep{Jaro89,Winkler99}, characters in the source string need to match within 
a window (calculated from the lengths of the two strings) of corresponding 
indices in the target string.  The Soundex metric \citep{Russell18,Russell22} 
groups consonants according to their sound similarity and ignores vowels unless 
they appear at the start of the strings.

In the case of English-Hindi strings it was observed during our experiments that 
for the two strings to be similar the first and the last characters from both the 
strings - the English word (E) and the transliterated string (T), must match.  This
ensures that the words have same phonetic starting and same ending. However
some English words start or end with silent vowels (e.g. \textit{p} in 
\textit{psychology} and \textit{e} in \textit{programme}). Therefore in such
cases the first character of the transliterated string should be compared with 
second character of the E and similarly the last character of the transliterated 
string should be compared with the second last character of the E. Our
experiments show that unless the length of the shorter string is at least 65\%
of the length of the other string, they are unlikely to be phonetically similar.

The similarity algorithm takes two strings, E and S, as input where $E_{i=1..n}$ 
and $T_{j=1..m}$ refer to characters at position {\it i} and position {\it j} in 
the two strings with lengths {\it n} and {\it m} respectively.  Starting with 
$i=1$ and $j=1$, character $E_{i}$ is compared with characters $T_{j}$, 
$T_{j+1}$ and $T_{j+2}$. If $E_{i}$ matches with one of the $T_{j}$, 
$T_{j+1}$ and $T_{j+2}$, the pointer {\it i} advances one position and the 
pointer {\it j} is set to one position after the letter that matches with $E_{i}$. If
there is no match, the pointer {\it i} advances and {\it j} does not. We award 
every match a score of 2 and calculate similarity using the 
matchScore/(f(s) + f(t)) where f(x) = number of letters in the x string.

\section{Experiments}

We compare our similarity metric TSM with other string similarity metrics such 
as the standard DC metric, LSCR metric, JW metric, n-gram metric and LD 
metric. In order to perform this comparison we manually obtained 1000 unique 
words pairs from the EMILLE corpus. Out of the 1000 words pairs collected, 732 
pairs were correct transliterations of each other and 268 pairs were not. We 
obtained a set of transliterations (using the TMs) for each Hindi word in the 
collected sample data. For each similarity metric the task was to identify correct
transliteration pairs and avoid recognizing incorrect pairs by giving them a very 
low similarity score. The following procedure was repeated for each similarity 
metric. For each Hindi word in these test pairs we obtained a transliteration with
highest score. Then, we clustered the results in six predefined groups: 
$>=0.95$, $>=0.90$, $>=0.85$, $>=0.80$, $>=0.75$, and $>=0.70$ where, 
the group {\tt $>=Sim$} contains pairs with similarity greater than or equal to 
$Sim$. For each group, we calculated the precision, recall and f-measure.

From this, we were able to obtain the best threshold value for each of the 
similarity metrics. For example, in case of the DC metric, the best f-measure 
score (0.77) was recorded when the threshold value was {\tt $>= 0.80$}. 
Similarly, for TSM, LCSR, JW, n-gram, and LD, the recorded f-measure and 
threshold values were (0.77,$>=$0.75), (0.67,$>=$0.7), (0.73,$>=$0.7), 
(0.39,$>=$0.7) and (0.74,$>=$0.7) respectively.   It must be noted that the DC 
metric does not take positions of characters into account where as the TSM 
does. Although the f-measure figures for these two metrics are same, this is 
because our dataset does not have examples such as {\it teacher} vs $[$cheater$]$
which according to the DC is a correct transliteration pair (even with threashold 
set to 100).

\begin{table}[tbh]
\centering
\begin{tabular}{|l|l|r|}
\hline
\textbf{Similarity Metrics} & \textbf{Threshold} & \textbf{F-Measure} \\
\hline
DC + TS + JW + LD & $>= 70$ & 0.84 \\
DC + TSM + JW & $>= 0.75$ & 0.85 \\
DC + TSM + JW & $>= 0.78$ & 0.86 \\
DC + TSM + JW & $>= 0.79$ & \textbf{0.92} \\
DC + TSM + JW & $>= 0.80$ & \textbf{0.92} \\
DC + TSM + JW & $>= 0.81$ & \textbf{0.91} \\
DC + TSM + JW & $>= 0.85$ & 0.78 \\
DC + TSM + LCSR & $>= 0.90$ & 0.62 \\
DC + LCSR + JW & $>= 0.95$ & 0.4 \\
\hline
\end{tabular}
\caption{Multiple Measure Agreement Strategy Results}
\end{table}

Given the different criteria that these similarity metrics work on, it is 
possible that given a pair of strings one metric gives it a very high score 
where as the others very low. In order to exploit the multiple measure 
agreement strategy\footnote{A word pair is a valid transliterated pair only if it 
receives majority vote from the members of the similarity metrics group.}, we 
conducted a further experiment, whereby we recorded top combination of 
metrics that performed best (f-measure) given different threshold values.  We 
found that the combination of DC, TSM and the JW metrics works best with 
threshold value set between 0.79 and 0.81.

Although the scripts used by Gujarati and Hindi are different, the consonants 
and vowels in their scripts are similar and pronounced the same way. With the 
help of a native Gujarati speaker, we replaced the Hindi letters in our mappings 
table with their corresponding Gujarati letters. Using the same combination of 
similarity metrics and the same threshold, we obtained 0.91 f-measure on the 
Gujarati test data.

\renewcommand{\bibname}{{\Large References}}
\bibliographystyle{plainnat}
\bibliography{./na}
\end{document}
