Regular Sound Changes for Cross-Language Information Retrieval

Abstract

The aim of this project is the automatic conversion of query terms in one language into their equivalents in a second, historically related, language, so that documents in the second language can be retrieved. The method is to compile lists of regular sound changes which occur between related words of a language pair, and substitute these in the source language words to generate target language words. For example, if we know b in Italian often corresponds with a v in Spanish, an unaccented o in Italian with ó in Spanish, and a terminal e in Italian is replaced with a null in Spanish, we can construct the Spanish word autómovil (car) from the Italian automobile. A bilingual word list or dictionary is needed at first to first discover the set of regular sound changes, but once this is known, there is no further need for a dictionary to look up individual query words. The method is language pair independent, as long as the two languages belong to the same language family, such as the Romance languages. Buckley et al. (2000) proposed a related method based on knowledge of regular orthographic changes between languages, when corresponding words in two languages are pronounced alike, but the method proposed here is novel in that it also incorporates regular, linguistically attested, sound changes between historically related languages.

-

e -> 0 deletion : l -> l match : i -> i match : b -> v substitution : o -> ó substitution : m -> m match : o -> o match : t -> t match : u -> u match : a -> a match : edit distance = 3 In order to transform the Italian automobile into the Spanish automóvil, three operations (two substitutions and a deletion) are required, and thus the edit distance is 3. The technique of dynamic programming finds the alignment which minimises the edit distance. To convert the edit distance into a measure of the closeness between two words, we use the following formula (McEnery & Oakes, 1996) . This matching coefficient will be 1 for two identically spelled words, and 0 for two words with no characters at all in common. matching _ coefficient = 1 −

edit _ dis tan ce length _ of _ longer _ word A vocabulary list of over 56,000 words was produced consisting of all the Spanish words occurring twice or more in a subset of the Spanish document set. Program clef5.c was written to align each word in the Italian query sets with each Spanish word in the lexicon in turn, using dynamic programming. A subjectively assigned threshold of 0.8 was chosen, such that any word in the Spanish lexicon with a matching coefficient of 0.8 or more with respect to the Italian query word was assumed to be a possible translation of that query word. This method is similar to that used by the Kantrowitz et al. ste mmer (2000 ), an edit distance stemmer with complex edits corresponding to the most common suffixes. The first five Italian queries are shown in figure 2. *c141 lettera bomba per kiesbauer *c142 christo impacchetta parlamento tedesco *c143 conferenza pechino sulle donne *c144 ribellioni sierra leone diamanti *c145 importazioni giapponesi riso 2. Second experimental run: cognates sought by regular sound changes For the second experimental run, we used a more linguistically accurate definition of cognates, namely that cognate words are vocabulary items which occur in two or more historically related languages, such that they have similar meanings, and one can be transformed into the other by a predictable series of phonological changes. For example, Nothofer (1975) has manually produced tables showing the sound equivalences which occur in four languages spoken in or near the Indonesian island of Java, namely Javanese, Madurese, Malay and Sundanese, all of which originate from the common ancestor language Proto-Malayo-Javanic (PMJ). One example of such an equivalence is Javanese d = Madurese jh = Malay j = Sundanese j, as in the words for road, dalan, jhalan, jalan and jalan respectively. Such a system of sound correspondences was first described for Indo-European languages where it is referred to as Grimm’s Law, and it was later shown that such systems are found in all language families (Bloomfield, 1925) . The task of identifying regular sound changes in bilingual word lists has been described by Guy (1994) as “Given a sample word list from two related languages, extract the probable rules for predicting any word of one language from that of the other”.

To find the regular sound changes found in a given language pair, the starting point is a bilingual word list where each word in one language is aligned with its translation. Single character substitutions can be identified using the Wagner & Fischer edit distance algorithm described in section 1. However, in their work on bilingual sentence alignment, Gale & Church (1993) introduced additional operations into the dynamic programming algorithm. While the original algorithm allows only for single character insertions, deletions and substitutions, Gale and Church also considered for example 2:1 correspondence, denoting that two sentences of one language correspond with just one of the other. They also allowed for the fact that some operations are more commonly encountered in real data that others, by assigning higher edit distances to less frequently encountered operations. In program Jakarta. c (Oakes, 2000 ) the allowed operations correspond to the list of the types of sound change which typically occur between related languages throughout the world given by Crowley (1992, Chapter 2). These include single character operations, operations with higher cardinality, operations which can only involve certain characters such as vowels, and operations which can only take place at certain positions (such as initial) in the two words. Program Jakarta.c was used to collate the sound changes discovered in a list of 63 word pairs taken from the introductions to Collins Gem Italian and Spanish dictionaries, examples of which are shown in figure 4 below: The sound changes found in the word pair aggetivo and adjetivo are shown in figure 5. These changes were a fusion of the double t in Italian to a single t in Spanish, and the dissimilation of the gg (producing a single sound) into dj (producing two separate sounds) in Spanish. All word pairs in the bilingual list were compared in this way, and the changes were collated to produce the list shown in figure 6, which includes the number of instances where a character remained as itself. 0 represents a null character. Pairs of words which require an above threshold edit distance of three to transform one into the other are deemed not to be cognate (such as abbreviazione and abbreviatura), and do not contribute to the tally of discovered sound changes. o -> o match : v -> v match : i -> i match : tt -> t fusion : e -> e match : gg -> dj dissimilation : a -> a match : cost = 2 Based on the sound changes seen in figure 6, the basic edit distance program used for the first experimental run (clef5.c) was amended to form program sounds5.c which implements the following metric: a cost of 1 is assigned for each insertion, deletion or single character substitution not recognised as being regular, and a cost of 0 for each exact character match, deletion or single character substitution listed as being regular. The transformations regarded as being regular are shown in figure 7. As for the first experimental run, each Italian query term was matched against the Spanish lexicon, and all Spanish terms matching the Italian terms with an above threshold coefficient were included as Spanish query terms. A slightly higher threshold of 0.85 was used for the second experimental run, as the incorporation of the regular sound changes meant that true cognates matched with slightly higher coefficients, and raising the threshold would reduce the noise caused by false cognates being selected. The first five Spanish query sets produced for the second experimental run are shown in figure 8. z -> c not initial o -> u not initial t -> c not initial v -> d not initial i -> í o -> ó u -> ú g -> j not first or second character delete terminal o delete terminal e

3. The search engine

For both experimental runs, the task was to translate the Italian query sets to Spanish query sets, then match the Spanish query sets against the Spanish document set using a search engine. Our search engine uses a very simple algorithm. The Spanish query sets are submitted in turn, and for each document in the Spanish document set, a score of 1 is given for each word in the document which matches a word in the query set. The overall score for each document is normalised by dividing it by the number of words in the document, and the documents are ranked, so that those with the best normalised matching score are presented first.

4. Conclusions

We believe that our results could be improved in future in a number of ways. Firstly a larger Spanish vocabulary could be produced using the entire Spanish document set. Secondly, we need to determine optimal matching coefficient thresholds which best discriminate between true and false word translations. Thirdly, we need a much larger bilingual word list to better determine the set of sound changes found in Italian and Spanish cognate words. Finally, program sounds5.c could be enhanced to allow regular multiple character substitutions. We have demonstrated a method of generating target language query words using source language keywords and a list of regular sound changes, if the source and target languages are historically related, as they are in the case of Italian and Spanish, which share many cognate words. The differences with respect to Buckley et al.’s approach are firstly that linguistically motivated sound substitutions are used, and secondly that regular sound substitutions are used rather than just orthographic substitutions for homophones.

References

L Bloomfield , On the Sound System of Central Algonquian . Language 1 , pp 130 - 156 , 1925 .

C Buckley , J Walz , M Mitra & C Cardi , “ Using Clustering and Super Concepts Within SMART” , NIST Special Publication 500-240: The Sixth Text Retrieval Conference (TREC6) , 2000 .

http://trec.nist.gov/pubs/trec6/t6_proceedings.html T Crowley . An Introduction to Historical Linguistics . Oxford University Press, 1992 .

W Gale & K Church . A Program for Aligning Sentences in Bilingual Corpora . Computational Linguistics , 19 ( 1 ), pp 75 - 102 , 1993 .

J B M Guy . An Algorithm for Identifying Cognates in Bilingual Word Lists and its Applicability to Machine Translation . Journal of Quantitative Linguistics 1 ( 1 ), pp 34 - 42 , 1994 .

M Kantrowicz , M Behrang & V Mittal , “ Stemming and its Effects on TFIDF Ranking” , Proceedings of the 23rd ACM SIGIR Conference , Athens, Greece, 2000 .

A M McEnery & M P Oakes ,“ Sentence and Word Alignment in the CRATER Project” , in “Using Corpora for Language Research”, ed. J Thomas and M Short , Longman, pp 211 - 231 , 1996 .

B Nothofer . The Reconstruction of Proto-Malayo-Javanic. 's- Gravenhage:Martinus Nijhoff , 1975 .

M P Oakes , Computer Estimation of Vocabulary in a Protolanguage from Word Lists in Four Daughter Languages , Journal of Quantitative Linguistics 7 ( 3 ) 2000 , pp 233 - 244 .

R A Wagner & M J Fischer, The String to String Correction Problem . Journal of the ACM , 21 , p 168 , 1974 .