Algorithms for Language Reconstruction

byGrzegorz Kondrak

A thesis submitted in conformity with the requirements
for the degree of Doctor of Philosophy
Graduate Department of Computer Science
University of Toronto

Copyright c 2002 by Grzegorz Kondrak

Abstract
Algorithms for Language Reconstruction
Grzegorz Kondrak
Doctor of Philosophy
Graduate Department of Computer Science
University of Toronto
2002
Genetically related languages originate from a common proto-language. In theabsence of historical records, proto-languages have to be reconstructed from surviving
cognates, that is words that existed in the proto-language and are still present insome form in its descendants. The language reconstruction methods have so far been
largely based on informal and intuitive criteria. In this thesis, I present techniques andalgorithms for performing various stages of the reconstruction process automatically.
The thesis is divided into three main parts that correspond to the principal stepsof language reconstruction. The rst part presents a new algorithm for the alignmentof cognates, which is suÆciently general to align any two phonetic strings that exhibit
some aÆnity. The second part introduces a method of identifying cognates directlyfrom the vocabularies of related languages on the basis of phonetic and semantic
similarity. The third part describes an approach to the determination of recurrent
sound correspondences in bilingual wordlists by inducing models similar to thosedeveloped for statistical machine translation.
The proposed solutions are rmly grounded in computer science and incorporate
recent advances in computational linguistics, articulatory phonetics, and bioinformatics. The applications of the new techniques are not limited to diachronic phonology,
but extend to other areas of computational linguistics, such as machine translation.
ii

Dedication

To Piotr Kondrak, My Uncle,
Who Started Me on My Wayiii

Acknowledgements
 Graeme Hirst, my academic advisor, convinced me to get into the program andtook the risk of allowing me to choose an unconventional research topic. He
often knew better than me what was good for me.

 Members of my advisory committee, that is, Elan Dresher, Radford Neal, andSuzanne Stevenson, were always there when I needed help.

 Kevin Knight provided valuable comments about the contents of the thesis.
 The faculty in the Department of Linguistics, especially Elizabeth Cowper, Elan

Dresher, Dianne Massam, and Keren Rice, made me feel like a member of theirdepartment.

 Hank Rogers got me hooked on phonetics. The drawings of the vocal tract

included in this thesis are his.

 The members of the computational linguistics research group, including Melanie

Baljko, Alex Budanitsky, Phil Edmonds, Neil Graham, Diana Inkpen, Eric Joanis, Daniel Marcu, and Gerald Penn, contributed to an exciting research environment.

 I thank my oÆce-mates: Yiannis Papoutsakis for the existential discussions,

Stuart Andrews for the music, and Iluju Kiringa for the tips.

 Gemma, mi amor, mi vida, mi inspiracion. Sin ti jamas habra terminado este
trabajo.

iv

Contents
1 Introduction

1

2 Background5

2.1 Evaluating system e ectiveness . . . . . . . . . . . . . . . . . . . . .
2.2 Speech sounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Language change . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Related work

5
6
8
12

3.1 Historical derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Comparative reconstruction . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 Comparative reconstruction from wordlists . . . . . . . . . . . . . . . 18
4 Phonetic alignment

20

4.1 Sequence comparison . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 The basic dynamic programming algorithm . . . . . . . . . . .
4.2 Previous alignment algorithms . . . . . . . . . . . . . . . . . . . . . .
4.3 Finding the optimal phonetic alignment . . . . . . . . . . . . . . . . .
4.3.1 Greedy is not enough . . . . . . . . . . . . . . . . . . . . . . .
4.3.2 Tree search is too much . . . . . . . . . . . . . . . . . . . . .
4.4 Extensions to the basic dynamic programming algorithm . . . . . . .
v

22
24
27
30
30
31
33

4.4.1 Retrieving a set of best alignments . . . . . . . . . . . . . . .
4.4.2 String similarity . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.3 Local and semiglobal alignment . . . . . . . . . . . . . . . . .
4.4.4 AÆne gap functions . . . . . . . . . . . . . . . . . . . . . . .
4.4.5 Additional edit operations . . . . . . . . . . . . . . . . . . . .
4.5 Comparing phonetic segments . . . . . . . . . . . . . . . . . . . . . .
4.5.1 Feature-based metrics . . . . . . . . . . . . . . . . . . . . . .
4.5.2 Multivalued features . . . . . . . . . . . . . . . . . . . . . . .
4.5.3 Similarity and distance . . . . . . . . . . . . . . . . . . . . . .
4.6 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7.1 Data input . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.8 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.8.1 Qualitative evaluation . . . . . . . . . . . . . . . . . . . . . .
4.8.2 Quantitative evaluation . . . . . . . . . . . . . . . . . . . . . .
4.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Identi cation of cognates

33
34
35
37
38
40
41
45
48
49
52
57
60
61
64
65
66

5.1 Phonetic similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 The orthographic approaches . . . . . . . . . . . . . . . . . .
5.1.2 The phonetic approaches . . . . . . . . . . . . . . . . . . . . .
5.2 Semantic similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 WordNet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 The Algonquian data . . . . . . . . . . . . . . . . . . . . . . .
vi

70
70
72
73
74
76
81
82

5.4.2 Properties of the data . . . . . . . . . . . . . . . . . . . . . .
5.4.3 Performance of COGIT . . . . . . . . . . . . . . . . . . . . . .
5.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1 The role of WordNet . . . . . . . . . . . . . . . . . . . . . . .
5.5.2 False positives . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 Determination of correspondences

84
86
92
92
93
98
99

6.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.2 Statistical machine translation . . . . . . . . . . . . . . . . . . . . . . 104
6.2.1 The word-to-word model of translational equivalence . . . . . 105
6.2.2 Noncompositional compounds . . . . . . . . . . . . . . . . . . 108
6.3 Models of phoneme correspondence . . . . . . . . . . . . . . . . . . . 110
6.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.5.1 The data for experiments . . . . . . . . . . . . . . . . . . . . . 113
6.5.2 Determination of correspondences in cognate pairs . . . . . . . 114
6.5.3 Determination of correspondences in word pairs . . . . . . . . 115
6.5.4 Identi cation of cognates in word pairs . . . . . . . . . . . . . 117
6.5.5 Determination of complex correspondences . . . . . . . . . . . 122
6.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7 Wrap-up and outlook

128

7.1 Identi cation of cognates . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.2 Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
7.3 Summary of results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
vii

A The Swadesh 200-word list

139

B A historical derivation program

141

C The alignment code

144

D Covington's test set

150

E A list of English{Latin cognates

159

Bibliography

161

viii

List of Tables
2.1 Summary of English consonants. . . . . . . . . . . . . . . . . . . . . . 7
2.2 The rst verse of Caedmon's \Hymn" and its modern English translation. 9
2.3 A bilingual wordlist [Kessler, 2001]. . . . . . . . . . . . . . . . . . . . 11
4.1 An example alignment of two cognates. . . . . . . . . . . . . . . . . . 20
4.2 The metric axioms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3 Computing the distance between two strings. . . . . . . . . . . . . . . 25
4.4 Retrieving the optimal alignment. . . . . . . . . . . . . . . . . . . . . 25
4.5 The array D after the computation of the distance between two strings. 26
4.6 An alignment retrieved from the array shown in Table 4.5. . . . . . . 26
4.7 Comparison of phonetic alignment/distance algorithms. . . . . . . . . 30
4.8 A correct and an incorrect alignment of a hypothetical cognate pair. . 31
4.9 The conditions for nding near-optimal alignments. . . . . . . . . . . 34
4.10 An example of local alignment. . . . . . . . . . . . . . . . . . . . . . 35
4.11 The basic algorithm for computing local similarities between two strings. 36
4.12 An example of semiglobal alignment. . . . . . . . . . . . . . . . . . . 36
4.13 An example of half-local alignment. . . . . . . . . . . . . . . . . . . . 37
4.14 The modi cation of the basic dynamic programming algorithm required to accommodate aÆne gap scores. . . . . . . . . . . . . . . . . 38
ix

4.15 An example of cognate alignment that requires the operation of compression/expansion. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.16 The modi cation of the dynamic programming algorithm that incorporates the compression/expansion operation. . . . . . . . . . . . . .
4.17 An elementary cost function. . . . . . . . . . . . . . . . . . . . . . . .
4.18 Covington's [1996] \evaluation metric". . . . . . . . . . . . . . . . . .
4.19 A partial distance matrix for Covington's distance function. . . . . .
4.20 Feature vectors adopted from Hartman [1981]. . . . . . . . . . . . . .
4.21 A partial distance matrix based on binary features. . . . . . . . . . .
4.22 The clause-by-clause comparison of Covington's distance function anda feature-based distance function. . . . . . . . . . . . . . . . . . . . .
4.23 The algorithm for computing the alignment of two phonetic strings. .
4.24 Three equivalent alignments. . . . . . . . . . . . . . . . . . . . . . . .
4.25 The procedure for retrieving alignments from the similarity matrix. .
4.26 Scoring functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.27 Features used in ALINE and their salience settings. . . . . . . . . . .
4.28 Multivalued features and their values. . . . . . . . . . . . . . . . . . .
4.29 A partial similarity matrix based on multivalued features with diversied salience values. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.30 The default feature assignments for base letters. . . . . . . . . . . . .
4.31 Additional feature assignments for non-syllabic segments. . . . . . . .
4.32 ALINE's input codes. . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.33 Examples of alignments of English and Latin cognates. . . . . . . . .
4.34 The correct alignment of tooth:dentis. . . . . . . . . . . . . . . . . . .
4.35 Evaluation of alignment algorithms on Covington's data set. . . . . .
x

39
40
41
42
43
44
44
45
51
52
53
54
55
56
57
59
59
60
63
63
64

5.1 Examples of similar words in Spanish and English. . . . . . . . . . . . 66
5.2 An excerpt from a Cree vocabulary list [Hewson, 1999]. . . . . . . . . 69
5.3 An excerpt from an Ojibwa vocabulary list [Hewson, 1999]. . . . . . . 69
5.4 The main lexical relations between nouns in WordNet. . . . . . . . . 75
5.5 Cognate identi cation algorithm. . . . . . . . . . . . . . . . . . . . . 77
5.6 The stop-list of words that are removed from glosses. . . . . . . . . . 78
5.7 Examples of automatically tagged glosses with keywords marked. . . 79
5.8 Semantic similarity levels. . . . . . . . . . . . . . . . . . . . . . . . . 81
5.9 Lists of semantically related words generated from WordNet. . . . . . 82
5.10 An excerpt from the Algonquian dictionary. . . . . . . . . . . . . . . 83
5.11 The size of the vocabulary lists. . . . . . . . . . . . . . . . . . . . . . 84
5.12 The number of shared cognates and the number of possible word pairs
for each language combination (nouns only). . . . . . . . . . . . . . . 85
5.13 Average phonetic similarity values computed by various methods for
randomly selected word pairs and for cognate pairs. . . . . . . . . . . 85
5.14 Average semantic similarity values for randomly selected word pairs
and for cognate pairs. . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.15 Average precision for various phonetic methods. . . . . . . . . . . . . 88
5.16 Average precision for ALINE combined with various semantic methods. 89
5.17 Average precision for LCSR combined with various semantic methods. 90
5.18 Examples of cognate pairs not included in Hewson's dictionary. . . . . 95
5.19 Examples of cognate pairs not included in Hewson's dictionary (cont.). 96
6.1 Examples of English{Latin cognates exhibiting correspondences. . . . 100
xi6.2 English{Latin correspondences discovered by Method D in pure cognate data. The correspondences marked with a y are predicted by
Grimm's Law. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.3 Correspondences discovered by JAKARTA in pure cognate data. . . . 116
6.4 English{Latin correspondences discovered by CORDI in noisy synonym
data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.5 English{Latin correspondences discovered using the 2 statistic. . . . 117
6.6 An example ranking of cognate pairs. . . . . . . . . . . . . . . . . . . 118
6.7 Average cognate identi cation precision on the development set forvarious methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.8 A sample screen from Guy's program COGNATE. . . . . . . . . . . . 121
6.9 Average cognate identi cation precision on the test set for various
methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.10 Average cognate identi cation precision normalized as . . . . . . . . 123
7.1 Average cognate identi cation precision on the test set for various
similarity-based methods. . . . . . . . . . . . . . . . . . . . . . . . . 129
7.2 Average cognate identi cation precision on the test set for various
methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.3 The proportion of cognates among the pairs that have at least one gloss
in common. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
7.4 A partial table of correspondences. . . . . . . . . . . . . . . . . . . . 134
B.1 Tested proto-forms grouped by the accuracy of the output. . . . . . . 142
B.2 Examples of semantic shifts. . . . . . . . . . . . . . . . . . . . . . . . 142
B.3 Examples of the generated words that have no existing counterparts. 143

xii

List of Figures
4.1 Places of articulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.1 The structure of cognate identi cation system. . . . . . . . . . . . . .
5.2 Coverage of the similarity levels. . . . . . . . . . . . . . . . . . . . . .
5.3 Precision-recall curves for various methods. . . . . . . . . . . . . . . .
5.4 Interpolated 3-point average precision of Method W on test sets as afunction of the parameter . . . . . . . . . . . . . . . . . . . . . . . .

77
87
90
91

6.1 The similarity of word alignment in bitexts and phoneme alignment
between cognates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.2 The Fox{Menomini consonantal correspondences determined by a linguist and by CORDI. . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

xiii

xiv

Chapter 1
Introduction
The goal of the computational linguist is to develop a computational theory of language, using the notions of algorithms and data structures fromcomputer science.

James Allen, Natural Language Understanding
It is a common experience for second-language learners who struggle to memorize
alien roots to unexpectedly encounter one that resembles a word from their native
language. It is like seeing a familiar face in a crowd of strangers. At last, the form of
a word gives a clue about its meaning.
How can the similarity of words across languages be explained? Sometimes theanswer is easy. There can be no doubt that the English word sushi is a borrowing |the name was transferred from Japanese together with the food it denotes. Romance
languages are full of cognates, such as Spanish vida and French vie, related words
that have evolved over centuries from common Latin roots. How about Russiannos `nose'? Common sense tells us that it must be cognate with English nose |such basic notions are rarely borrowed. Can such divergent languages as Russian andEnglish originate from a common source? We can look the word up in an etymological1Chapter 1.

Introduction

2

dictionary, written by people who track word histories. But what if languages haveno written records, as is the case with most of the New World languages? Is there
a way to decide whether a pair of similar words are related? Can we guess what
the proto-form of nos and nose was? Is it possible to reconstruct an entire protolanguage?
Over the last two hundred years, historical linguists have developed methods forproviding answers to such questions. By applying the comparative method, they
have established beyond doubt that almost all European languages are related andbelong to a single family. They have reconstructed the hypothetical Proto-IndoEuropean language and proved common origins of completely dissimilar words, suchas Russian sto and English hundred. They have also analyzed and classi ed intofamilies numerous languages from other continents.
As interesting as it seems, why would a computer scientist want to deal with such
issues? What can she or he hope to contribute towards solving problems that had
been studied for decades even before the computer was invented?
The language reconstruction task yields a number of problems that are easy tostate but surprisingly hard to solve. Linguists have worked out solutions for many
riddles related to particular language families. The question that a computer scientist
wants answered is: \Is there an algorithm to do it?". In my opinion, the answer is no| the collection of heuristics called the comparative method of language reconstruction is not nearly suÆciently formalized to be called an algorithm.
Language reconstruction is an extremely time-consuming process that has yet
to be accomplished for many language families. Greenberg [1993], in response to
Ringe [1992], who criticized him for not applying the comparative method to thelanguages of the New World, estimates that the task would take longer than a lifetime.
A computer system able to perform a fully automatic reconstruction of an unrecordedChapter 1.

Introduction

3

proto-language given wordlists representing two or more daughter languages would
certainly be of great assistance to historical linguists. A successful implementationof just one or two steps of the comparative method on the computer could free theexperts to divert their e orts to other, more challenging tasks.
The problems involved in language reconstruction may be classi ed as driving
problems, a source of new methods and insights that are not restricted in application
to historical linguistics. Like the basic research conducted in disciplines such as mathematics, the scope of applications may not be initially apparent or even predictable.
Although the main focus of this thesis is diachronic phonology, I have striven to makethe assumptions of the proposed solutions as general as possible, so that they may
also be of use in other contexts.
Parallel bilingual corpora (bitexts) have been increasingly important in statistical natural language processing. Bitexts are collections of texts available in electronic
form that are translations of each other. Since they convey nearly identical information by means of two di erent languages, bitexts are a rich source of translational
equivalences between words and sentences. In order to exploit this encoded knowledge, it is necessary to align rst the sentences within the corpus, and then the words
within sentences. A number of researchers found that identifying words that are similar in both form and meaning can greatly facilitate the task of bitext alignment. A
great majority of words in this class are cognates and borrowings. One of the goalsof my research on the identi cation of cognates, which is discussed in this thesis, isto contribute to the improvement of the techniques used for bitext alignment as well
as for the related task of inducing machine translation lexicons.
This thesis introduces new algorithms and methods for several stages of the language reconstruction process. The proposed solutions are language independent. I
conducted evaluation experiments for the new methods, and did my best to objectively

Chapter 1.

Introduction

4compare them with the previous proposals. I believe that simply implementing on acomputer the traditional techniques that the linguists have been using for decades is
not the right way to proceed. The intuitive criteria and broad knowledge that humans
apply when dealing with such complex problems are often very diÆcult to encode in
a computer program. My algorithms are based on some of the most recent researchin computational linguistics, computer science, and bioinformatics. By attacking amuch-studied problem from a di erent side, I hoped to obtain fresh insights and abetter understanding of its nature.
The thesis is divided into three main parts that correspond to the principal stepsof language reconstruction. Chapter 4 presents a new algorithm for the alignmentof phonetic strings that combines a number of techniques developed for molecularbiology with a scoring scheme for computing similarity on the basis of multivalued
phonetic features. Chapter 5 introduces a method for identifying cognates in the
vocabularies of related languages that employs the new alignment algorithm, as well
as a procedure for estimating semantic similarity of words. Chapter 6 describes anapproach to the determination of recurrent sound correspondences by inducing models
similar to those developed for statistical machine translation.

Chapter 2
BackgroundResearch in computational linguistics draws from both computer science and linguistics, and should be accessible to specialists from both disciplines. This chapter endeavours to clarify some of the concepts that recur throughout the thesis. Additionalterms will be de ned as they appear in the successive chapters.

2.1 Evaluating system e ectivenessThe notions of precision and recall were developed in the eld of information retrieval.
Precision is the ratio of true positives to the sum of true positives and false positives,
and recall is the ratio of true positives to the sum of true positives and false negatives.
For example, an Internet search-engine query returns an ordered list of pointers, which
are judged to be either relevant or not. In that context, true positives are the retrieved
relevant documents, false positives are the retrieved non-relevant documents, and false
negatives are the non-retrieved relevant documents. Suppose that the answer to ourquery about the names of Canadian provinces is \Alberta, Manitoba, Ontario, andMinnesota." Then, the precision of the answer is 0:75 (three out of four), and its
5Chapter 2.

Background6

recall is 0:3 (three out of ten).
In the context of cognate identi cation, precision is the proportion of selectedpairs that are genuine cognates, and recall is the proportion of all cognates in thedata that the system was able to identify. In general, there is a trade-o between
improving increasing precision and increasing recall. We can achieve a 100% recall
at the price of very low precision by assuming that all word pairs in the data arecognate. Conversely, we may be able to reach 100% precision by correctly guessing asingle cognate pair.
In the situation where all word pairs are ranked according to their likelihoodof being cognate, it is possible to compute precision and recall at any point in theordered list. We may choose to compute precision at various levels of recall andthen compute the average, which is called uninterpolated average precision. Theinterpolated average precision is similar, except for the assumption that precision
can only decrease or stay at the same level as the recall level increases. In order tosatisfy this constraint, if precision goes up while we are moving down the ordered
list, the precision values for all lower recall levels are adjusted upward to match thecurrent precision level.

2.2 Speech sounds
Phonetics is the study of speech sounds. The segmentation of continuous speech into astring of phonetic segments is not always a straightforward task. Phonetic segments
are usually divided into two basic categories: consonants, which involve some typeof obstruction in the vocal tract, and vowels, which are made with a very open vocal
tract. Consonants are often classi ed according to the place of articulation (velar,
dental, palatal, etc.), and according to the manner of articulation (stops, fricatives,

Chapter 2.

7Background

Bilabial
Labio-dental
DentalAlveolar
Palato-alveolar
Retro ex
Palatal
Velar
Labio-velar

Stop
pb

Fricative A ricate Nasalmfv

Liquid

Glide

TD

td

kg

sz
s z

c 

n

l
r

y

N

w

Table 2.1: Summary of English consonants.
nasals, etc.). Table 2.1 contains a summary of English consonants. Vowels have threebasic articulatory qualities: height, backness, and rounding. For example, thevowel that occurs in the English word rat is identi ed as low, front, and unrounded.
Glides are consonants that are phonetically similar to vowels. English has two glides:/y/ as in yell, and /w/ as in well.
Phonology, another major area of linguistics, is concerned with the sound patterns in language. The area is usually divided into synchronic and diachronic phonology. The former deals with languages as they exist at one point in time, while thelatter is concerned with language development through time.
Phonemes are phonetic segments that are distinctive in a given language. By
contrasting with each other, phonemes serve to distinguish words. Phonetic segmentsthat are distinct phonemes in one language are not necessarily contrastive in anotherlanguage. The segments that are considered variants of a single phoneme are called
allophones. For example, /t/ and /th /, which di er only in the degree of aspiration,

Chapter 2.

Background8

are distinct phonemes in Thai, but no more than allophones in English.
Features are units of speech, smaller than a segment, describing an aspect ofarticulation. Features can be unary, binary, or multivalued, depending on thenumber of possible values. Every speech sound can be characterized by specifying
a vector of feature values, but the characterization depends on the set of featuresthat has been selected. A well known system of binary features is the one devised by
Chomsky and Halle [1968]. A binary feature has exactly two possible values, a `plus'
value and a `minus' value. For example, a binary feature speci cation for the bilabial
voiced stop /b/ includes [+voice], [{coronal], and [{continuant]. Feature vectors of anumber of sounds are given in Table 4.20 on page 44.
Morphology is the study of the internal structure of words. Lexemes are words
in the sense of an abstract vocabulary item, which can have various realizations, orword-forms. For example, choking, choke, and choked are di erent realizations of
the lexeme. A word stripped of any in ectional aÆxes is called a stem. A
root is the irreducible core of a word, which is always present in the realizations of
the lexeme. The stem of the Latin in nitive volare `to y' is obtained by discarding
the in ectional ending -re, while its root is even more reduced: vol-.
choke

2.3 Language change
All languages change through time. Table 2.2 gives an example of how much English
has evolved within the last fourteen hundred years. Words that make up languages undergo sound changes (nu ! now) as well as semantic shifts (`guardian' ! `ward').
Lexical replacement is a process in which lexemes drop out of usage altogether,and are substituted by other, unrelated words (herigean ! praise). Morphologicalendings change and disappear as well (-on in sculon).

Chapter 2.

Background

Old English:
Modern English:

9Nu sculon
herigean heofonrces
weard
Now we should praise heaven-kingdom's guardian

Table 2.2: The rst verse of Caedmon's \Hymn" and its modern English translation.
When two groups of people that speak a common language lose contact with eachother, their respective languages begin to diverge, and eventually become mutually
unintelligible. In such cases, we may still be able to determine that the languages
are genetically related by examining cognates, that is words that have developed
from the same etymon, or proto-form. For example, French lait, Spanish leche, andItalian latte constitute a cognate set, as they are all descendants, or re exes, of
Latin lacte. In general, the longer the time that has passed since the linguistic split,
the smaller the number of cognates that remain as a proof of a genetic relationship.
Because of gradual changes over long periods of time, cognates often acquire very
di erent phonetic shapes. For example, English hundred, French cent, and Polishsto are all descendants of Proto-Indo-European *kmtom (an asterisk denotes a reconstructed form). The semantic change can be no less dramatic; for example, English
guest and Latin hostis `enemy' are cognates even though their meanings are diametrically di erent. On the other hand, not all similar sounding words that have the same
meaning are cognates. It can be a matter of chance resemblance, as in English day
and Latin die `day', or an instance of a borrowing, as in English sprint and Japanesesupurinto. Borrowings, or loan words, are lexical items that have been incorporated(possibly in modi ed form) into one language from another.
An important phenomenon that allows us to distinguish between cognates andborrowings is the regularity of sound change. The regularity principle states that achange in pronunciation applies to sounds in a given phonological context across allChapter 2.

Background10

words in the language. Regular sound changes tend to produce regular correspondences of phonemes in corresponding cognates. /d/:/t/ is a regular correspondence
between English and German, as evidenced by cognate pairs such as day { tag, dry{ trocken, and drink { trinken. Following Kessler [2001], I prefer to use the term recurrent sound correspondences, because in practice the matchings of phonemesin cognate pairs are more tendencies than hard-and-fast rules.
The comparative method of language reconstruction is the technique used bylinguists to reconstruct proto-forms of the parent language by examining cognates in
its daughter languages. It consists of several stages. After deciding that languages
are related, words with similar meanings are placed side by side. Those pairs thatexhibit some phonological similarity are identi ed as putative cognates. Next, thecognates are aligned by pairing related phonetic segments, and analyzed in order tond systematic correspondences. A proto-phoneme or a proto-allophone is positedfor each established correspondence. The proto-forms that gave rise to the identi ed
cognate sets are then reconstructed. The resulting phonological system of the protolanguage is adjusted in order to conform to general linguistic principles. Naturally,
the results of the subsequent steps can be used to re ne the judgements made in theearlier ones.
The input data for establishing the relatedness of languages and reconstructing
their common ancestor is often given in the form of a bilingual wordlist, a list ofword pairs from two languages such that the corresponding words have the same,well-de ned meaning. One of the most widely used set of meanings is the Swadesh
200-word list [Swadesh, 1952]. The 200 basic meanings in the list, given in full inAppendix A, are relatively resistant to lexical replacement and occur in most of
the world's languages. The Swadesh 200-word lists have been compiled for a large
number of languages. Table 2.3 contains an excerpt from the German{AlbanianChapter 2.

11Background

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

`all'
`and'
`animal'`ashes'`at'`back'`bad'`bark'`because'`belly'German
al@
unt
tr
as@
an
ruk@nslext
rind@
vayl
bawx

AlbanianéiT@ekafs@
hin@spin@kec
sk@lboz@
sepse
bark

Table 2.3: A bilingual wordlist [Kessler, 2001].
wordlist. Although the two languages are related, the entire list contains few cognates
because after several thousand years of divergence, the lexical replacement process
has obliterated almost all traces of the common origins.
A vocabulary list, or simply vocabulary, is a list of lexemes from a single
language accompanied by glosses that explain their meaning. Glosses may be single
words or complex phrases. I take a vocabulary item to mean a lexeme together
with the corresponding gloss or glosses. A sample vocabulary list can be found on
page 69.

Chapter 3
Related work
Computational diachronic phonology is concerned with two main tasks: deriving
the modern forms from the old ones, and reconstructing the old forms from themodern ones. This chapter reviews previous algorithmic approaches to historicalderivation and to comparative reconstruction. Other, closely related work is reviewed
in subsequent chapters.

3.1 Historical derivation
Sound changes are regular in the sense that they normally apply to sounds in agiven phonological context across all words in the language. Since the early seventies,
there have been several proposals of derivation programs that take advantage of thisregularity in order to simulate evolution of languages. While most of the programs
discussed in this section have only a modest algorithmic content, they constitutestarting points for more-computational approaches described in other sections.
The derivation programs can be used to verify the correctness of a particular set ofsound-change rules and their relative chronology. If there are discrepancies between
12Chapter 3.

Related work13

the expected and the actual output, it may be possible to re ne the set of rules in aninteractive way. They may also be of assistance in the construction of etymologicaldictionaries, or serve as a demonstration of the historical development of a language
for educational purposes.
Eastlack [1977] provides a typical example of a derivation program. He implemented what he calls a computer simulation of systematic sound change in IberoRomance. The program contains about 90 rules that link rst-century Latin with
twelfth-century Castilian Spanish. Each sound-change rule is written as a separate
module. The output consists of derivations that include not only the initial and nal
forms but also all the intermediate ones, together with information identifying therules that triggered the changes. One apparent drawback is that syllable boundaries
must be marked directly in the input, although it is not diÆcult to detect them
automatically.
Burton-Hunter [1976] implemented the evolution of Latin word-forms into their
Old French counterparts through the intermediate stage of Vulgar Latin. She chose
Latin because it is a relatively well-documented proto-language, and French because
it had undergone the greatest changes compared to other Romance languages. The
long-term goal was to build a system consisting of a database of cognates for all
Indo-European languages and programs that would perform both derivations andreconstructions.
Another researcher who used Latin as the proto-language was Hartman [1981],
who implemented a program simulating the evolution of Spanish. His main innovationis representing phonemes as binary vectors in which every bit stands for a single binaryfeature. This allows the implementation of sound changes in a way that closely mirrors
their phonological formulations. However, since there is no universally accepted setof features, their selection must necessarily be arbitrary.

Chapter 3.

Related work

14

An early paper by Smith [1969] provides an example of a derivation programthat deals with a much larger time distance. The goal was to derive modern Russian
from reconstructed Proto-Indo-European forms. These two languages are separated
by at least 5000 years of mostly undocumented changes, as compared to about 1500
years that have passed since Latin split into Romance vernaculars. Out of the totalof 650 Proto-Indo-European etyma that were examined, almost 90% have left nore exes in Russian, and so could not be used to verify the correctness of the program.
Of the remaining 69 etyma, the generated form exactly matched the corresponding
Russian word in only 9 cases, which prompted Smith to rather gloomily conclude that
\historical linguistics may have grossly overestimated the exceptionless character ofsound change." The poor performance of the program, however, was most likely also
due to the incompleteness of the implemented set of sound changes. Appendix B
contains some results of my implementation for modeling the phonological evolutionof Polish that contradict Smith's conclusion.
Remmel [1980] reports a computer procedure for modeling the evolution of vowels
in Estonian. What is di erent about his approach is that he uses acoustic formants forthe description of sound changes. Formants are concentrations of energy at speci cfrequencies of a sound wave. For example, for the vowel that occurs in the English
word pet, the values of the rst three formants are 700 Hz, 2100 Hz, and 3100 Hz,
respectively. Every phoneme represents thus a point in an n-dimensional space, where
n is the number of formants. A sound change can be represented as a vector or a curvein the n-dimensional space, which makes it easy to express \non-discrete" changes
that take place over a period of time. Unfortunately, the paper provides few detailsof how this approach may work in practice.
Raman et al. [1997] use derivation programs to develop distance measures between parent and daughter languages. The diachronic relationship between languages

Chapter 3.

Related work

15

is modeled as a Probabilistic Finite State Automaton, which represents the phonological complexity of the derivation process. The length of the minimal description of
the automaton is taken as a measure of the distance between the earlier and the later
form of a language. The authors apply the model to the modern Chinese dialects inorder to establish their relative distance from the common proto-language.

3.2 Comparative reconstruction
The programs discussed in this section attempt to derive the proto-forms from themodern forms on the basis of regular sound correspondences provided by the user.
Hewson [1974] produced a dictionary of the Proto-Algonquian from wordlists
representing four contemporary Algonquian languages. He does not claim to havereconstructed the proto-language { its sound system and all sound correspondences
had already been established by other historical linguists. Rather, his contribution
was to increase the number of reconstructed words from a few hundred to over fourthousand.
The reconstruction process can be outlined as follows. First, from each input
word of the daughter languages, every possible proto-form was generated using theprovided set of regular sound correspondences. The resulting list was sorted alphabetically in order to detect the words from di erent languages that had identical
proto-projections. The potential cognates were subsequently analyzed by a linguist
whose job was to determine whether they are in fact re exes of the same proto-form
and to decide on its exact form.
Automatic processing of the linguistic data led to a tremendous reduction of timenecessary to devote to the task. Hewson claims that with the aid of computer,the linguists were able to reconstruct about 250 items within a few hours. The nal

Chapter 3.

Related work16

dictionary [Hewson, 1993] contains over 4000 reconstructed proto-forms incorporating
the evidence of over 12,000 modern forms.
Hewson [1989] points out that once there is a suÆciently large database of forms
and reconstructions, it is relatively easy to produce \spin-o " applications. In thecase of the Proto-Algonquian dictionary, the applications that proved useful for related research included a concordance of consonant clusters and a dictionary of wordformatives.
A similar project is reported by Johnson [1985]. The goal was also to produce
a comparative dictionary of the Yuman family of languages spoken in the Southwest
United States. A relatively modest programming e ort resulted in a substantial timesaving over manual compilation of the dictionary. Standard tools such as awk andsort were used in preference to specialized programs. The reconstruction of protoforms was performed by a simple substitution of phonemes according to the soundcorrespondences provided by linguists. Naturally, such a procedure works only forsome sound changes. Nevertheless, Johnson reports that \the number of cases where
two related roots do not reconstruct to the same form is fairly low."
The Reconstruction Engine of Lowe and Mazaudon [1994] is an impressive setof programs designed to aid the historical linguist in reconstruction work. By processing complete lexicons of modern languages, they can establish cognate sets together
with reconstructions; at the same time, they can generate re exes from the provided
proto-forms. The user is allowed a high degree of exibility in choosing the transcription system, the method of data organization, and the type of constituents used in
the analysis. The inclusion of such features shows that the Reconstruction Engine
was designed with a practical utility in mind. However, the authors acknowledge
that in order to be useful to other researchers in historical linguistics, their programs
would have to be integrated with a larger package containing an appropriate inter-

Chapter 3.

Related work

17

face. Moreover, since it was developed and tested on a single family of languages(Tamang), it remains to be seen if it can be applied to other language families withequal success. At the time of writing, the Reconstruction Engine has yet to be madepublicly available.
The common characteristic of the three approaches discussed thus far is that theyattempt to meet the challenge of proceeding backwards in time by providing theirprograms with previously determined regular sound correspondences. Unfortunately,
the determination of sound correspondences is one of the most challenging steps ofthe reconstruction process. A linguist whose job is to retrace the development ofa language family may have only wordlists of modern forms at her disposal. In all
but a handful of cases, there are no records that demonstrate the form of the protolanguage. Most of the indigenous American languages, for instance, have no historical
records at all.
Another diÆculty is caused by the fact that a table of correspondences is not
powerful enough to capture a series of phonological changes. In contrast with thehistorical derivation, proceeding in the opposite time direction is not, in general, adeterministic process. If a later change obliterates the environment that conditioned
an earlier change, or if two independent phonemes merge into one, the reverse derivation of forms is all but impossible. The implicit assumption that all sound changes
operate independently, present in the methods employing tables of correspondences,is untenable.

Chapter 3.

Related work18

3.3 Comparative reconstruction from wordlists
The problem of automatically reconstructing a proto-language from wordlists that
represent its descendants is extremely challenging. I have found only a few publications describing programs designed for this purpose, and none of them is close toproviding a functional solution.
Kay [1964] represents an interesting attempt to formalize a large part of thecomparative method in terms of propositional logic. The criterion that guides thesearch for correspondences is the minimization of the number of proto-phonemes
necessary to account for the input data. The identi ed correspondences determine
which word pairs in a bilingual list are cognate, and how they should be aligned.
The author stops short, however, of converting the list of correspondences into protophonemes.
Kay develops his model with impressive rigor and generality. At one point in his
paper, the entire problem of language reconstruction seems to be reduced to nding asatisfying assignment to a single propositional formula. Unfortunately, his solution iscomputationally impractical. According to my calculations, the number of elementary propositions generated for a pair of words of length n and m is Pnk=1 k nk 11 mk 11 ,which means that a formula corresponding to two lexemes made of sixteen segments
would contain over a billion terms, even before its conversion to disjunctive form. The
program that implemented the model could successfully handle only trivially small
data sets (the English-German wordlist given in the paper contains four pairs). The
ability of the model to handle noisy data is also doubtful.
Remmel [1979] claims to have implemented a complete system for performing all
stages of linguistic reconstruction. He even includes a sample set of seven wordlists
and a corresponding list of 30 reconstructed words. According to him, most of theChapter 3.

Related work

19

generated forms are identical with the commonly accepted reconstructions (which are
not, however, included in the paper). There are virtually no details of the design; thedescription of the whole system takes less than 300 words.
Oakes [2000] describes a set of programs that together perform several steps of thecomparative method, from the determination of regular correspondences in wordlists
to the actual reconstruction of the proto-forms. The paper contains experimental
results of running the programs on a set of wordlists representing four Indonesianlanguages, and compares those to the reconstructions found in the linguistic literature.
I consider Oakes's implementation as important because his goal of performing fully
automatic reconstruction from unprocessed wordlists is very similar to what I hope toachieve in the future. However, his approach is very di erent from the one advocatedin this thesis. Rather than creating a program for reconstructing a speci c protolanguage, my goal is to develop methods that are applicable to any language family.
The author has graciously provided me with the source code of his programs. I will
discuss various components of his system in the following chapters.

Chapter 4
Phonetic alignment
Identi cation of the corresponding segments in phonetic strings is a necessary stepin many applications in both diachronic and synchronic phonology. Usually we areinterested in aligning strings that represent forms that are related in some way: apair of cognates, or the underlying and the surface forms of a word, or the intended
and the actual pronunciations of a word. Table 4.1 shows an example alignment of
two cognates, Spanish poner and Italian porre, which originate from Latin ponere `toput'. Alignment of phonetic strings presupposes transcription of sounds into discrete
phonetic segments, and so di ers from matching of utterances in speech recognition.
On the other hand, it has much in common with the alignment of proteins and DNA
sequences. Many methods developed for molecular biology can be adapted to performaccurate phonetic alignment.
p o r - r e
p o n e r Table 4.1: An example alignment of two cognates.

20

Chapter 4.

Phonetic alignment

21

Alignment algorithms usually contain two main components: a metric for measuring distance between phonetic segments and a procedure for nding the optimalalignment. The former is often calculated on the basis of phonological features that
encode certain properties of phonetic segments. An obvious candidate for the latter isa well-known dynamic programming algorithm for string alignment [Wagner and Fischer, 1974], although other algorithms can be used as well. (Dynamic programming
is a technique of eÆciently solving problems by combining previously computed solutions to smaller subproblems.) The task of nding the optimal alignment is closely
linked to the task of calculating the distance between two strings. The basic dynamic
programming algorithm accomplishes both tasks. Depending on the application, either of the results, or both, can be used.
Within the last few years, several di erent approaches to phonetic alignment havebeen reported. Covington [1996] used depth- rst search and a special distance function to align words for historical comparison. Somers [1998] proposed a special algorithm for aligning children's articulation data with the adult model. Gildea andJurafsky [1996] applied the dynamic programming algorithm to pre-align input andoutput phonetic strings in order to improve the performance of their transducer induction system. Kessler [1995] and Nerbonne and Heeringa [1997] adopted a similar
approach in order to estimate phonetic distance between dialects of Irish and Dutch,
respectively. All the algorithms are described in more detail in Section 4.2.
In this chapter, I present a new algorithm for the alignment of cognates. It combines various techniques developed for sequence comparison with a scoring scheme
for computing phonetic similarity on the basis of multivalued features. The newalgorithm performs better, in terms of accuracy and eÆciency, than comparable algorithms reported by Covington [1996], Somers [1999], and Oakes [2000]. The algorithm
is applicable not only to diachronic phonology but also to any other contexts in which

Chapter 4.

Phonetic alignment22

it is necessary to align phonetic strings, including the applications identi ed in thepreceding paragraph.

4.1 Sequence comparison
Sequence comparison is a term used to describe a number of techniques and algorithms for comparing two or more sequences of elements drawn from some alphabet.
The algorithms have been successfully applied to problems in such diverse elds as
molecular biology, speech recognition and gas chromatography [Kruskal, 1983]. The
increased interest in the analysis and processing of DNA sequences resulted in the
rapid development of related algorithms. It is not surprising that the techniques developed for molecular biology are often applicable in diachronic phonology. In bothcases, sequences made of a limited set of units undergo evolutionary changes andsplits.
In order to avoid terminological confusion, I use the word string, as commonlyused in the computer science literature, rather than sequence, which is preferredin the context of biological applications. Phonetic strings are either entire words,
or their parts, such as roots or stems. A substring is not the same thing as asubsequence. The former must be composed of contiguous units, while the latterneed not.
Typically, one of two cases applies: a) one of the strings being analyzed is a
product of applying a certain number of elementary operations to the other string,or b) both strings represent variants of some underlying string. The edit operations
are usually substitutions and insertions/deletions (indels). Less often the di erences
are described in terms of compressions/expansions and transpositions.
In general, the number of possible alignments grows exponentially with the lengthChapter 4.

Phonetic alignment

23

1. 8a; b : d(a; b)  0
nonnegative property
2. 8a; b : d(a; b) = 0 , a = b
zero property
3. 8a; b : d(a; b) = d(b; a)symmetry
4. 8a; b; c : d(a; b) + d(b; c)  d(a; c) triangle inequality
Table 4.2: The metric axioms.
of strings. Usually, we are interested in nding the alignment that minimizes a certain
numerical function called edit distance. For example, we can de ne the distance as
the minimum number of substitutions and indels necessary to convert one string intoanother (the so-called Levenshtein distance). A distance function that satis es theaxioms in Table 4.2 is called a metric.
The distance function can be made more complex by conditioning the cost of
substitution and/or indels on the type of units involved. The distance between two
strings is then the minimum sum of the costs of all edit operations necessary toconvert one string into another.
Recently there has been a tendency in molecular biology to move away fromedit distance toward probabilistic models, such as Hidden Markov Models [Durbin etal., 1998]. It is not clear at this point whether HMMs indeed outperform standardalignment methods. While HMMs are not dealt with in this thesis, the comparisonof the two paradigms in the context of of phonetic alignment is a fascinating future
research topic.

Chapter 4.

Phonetic alignment

24

4.1.1 The basic dynamic programming algorithm

The basic dynamic programming algorithm [Wagner and Fischer, 1974] accomplishes
two related tasks: nding the optimal alignment of two strings, and calculating the
distance between them. Given two strings of length n and m, the algorithm requires
O(nm) time to calculate the minimal edit distance plus O(n + m) time to determine
the corresponding alignment. Since I refer to the algorithm many times throughout
this thesis, the time invested in studying the pseudocode given in Tables 4.3 and 4.4
will certainly pay o later.
Table 4.3 presents the rst part of the algorithm, which computes the minimum
distance between two strings. The distance is calculated recursively for successively
larger substrings. D[i; j ] holds the minimal distance between the initial substrings of aand b containing i and j elements, respectively. Æ(x; y) is the substitution cost between
elements x and y. Similarly, Æ( ; y) and Æ(x; ) denote the insertion and deletion
cost, respectively. Initially, the rst row and the rst column of D are lled by themultiples of the indel cost (lines 1.1{1.5). The main loop (lines 1.6{1.10) calculates
the value of D[i; j ] by taking the minimum of three distances, which correspond to
three possible ways of extending a partial alignment: by adding a substitution (line1.8), deletion (line 1.9), or insertion (line 1.10). At the end of the computation, thevalue of D[n; m] is the actual distance between the complete strings (line 1.11).
Table 4.4 presents the second part of the algorithm. The optimal alignment isretrieved from D by starting at D[n; m] (line 2.1) and tracing back through theentries until the entry D[0; 0] is reached (line 2.2). The next entry of D after thecurrent one depends on the choice that was made in the rst part of the algorithm:
conditions in line 2.3, 2.6, and 2.9 correspond to lines 1.9, 1.10, and 1.8, respectively.
In fact, the choices made in part 1 can be remembered in a separate n  m array,

Chapter 4.

1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
1.10
1.11

Phonetic alignment

D[0; 0] := 0
for i := 1 to n do
D[i; 0] := D[i 1; 0] + Æ (ai ; )for j := 1 to m do
D[0; j ] := D[0; j 1] + Æ ( ; bj )for i := 1 to n do
for j := 1 to m do
D[i; j ] := min( D[i 1; j 1] + Æ (ai ; bj );D[i 1; j ] + Æ (ai ; );D[i; j 1] + Æ ( ; bj ) )print (D[n; m])Table 4.3: Computing the distance between two strings.

2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11

i := n, j := mwhile i 6= 0 or j 6= 0 do
if D[i; j ] = D[i 1; j ] + Æ (ai ; ) thenprint ((ai ; ))i := i 1
else if D[i; j ] = D[i; j 1] + Æ ( ; bj ) thenprint (( ; bj ))j := j 1
else
print ((ai ; bj ))i := i 1, j := j 1

Table 4.4: Retrieving the optimal alignment.

25

Chapter 4.

26

Phonetic alignment

D(i; j )

c
o
l
o
u
r

0
1
2
3
4
5
6

c o u l e u r

1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 0 1 2 3 4 5 6
2 1 0 1 2 3 4 5
3 2 1 2 1 2 3 4
4 3 2 3 2 3 4 5
5 4 3 2 3 4 3 4
6 5 4 3 4 5 4 3

0
0

Table 4.5: The array D after the computation of the distance between two strings.
thus eliminating the need to redo the summations in lines 2.3 and 2.6.
Table 4.5 shows a completely lled array D after computation of the alignment
between colour and couleur. The insertion/deletion cost is assumed to be 1. The
substitution cost is assumed to be 0 for identical segments, and 2 otherwise. The
values shown in boldface indicate the retrieved path that corresponds to the alignmentshown in Table 4.6.
c o u lc o - l- e u ro - u rTable 4.6: An alignment retrieved from the array shown in Table 4.5.

Chapter 4.

Phonetic alignment

27

4.2 Previous alignment algorithms
In this section, I review several approaches to phonetic alignment that have beenreported within the last few years.
Covington [1996] developed an algorithm for the alignment of cognates on thebasis of phonetic similarity. In a follow-up paper [1998], he extended the algorithm
to align words from more than two languages. His algorithm consists of a speciallydesigned evaluation metric and a depth- rst search procedure for nding the minimalcost alignment. The evaluation metric is a function that speci es the substitution
cost for every pair of segments, and a context-dependent indel cost (Table 4.18 on
page 42). The values of the metric range from 0 for two identical consonants to
100 for two segments with no discernible similarity. The total cost of a particularalignment is calculated by summing the costs of all substitutions and indels. I discuss
Covington's approach in more detail in Section 4.5.
Somers [1998] proposed a special algorithm for aligning children's articulation
data with the adult model. He implemented three versions of the algorithm, which
use di erent methods to compute the cost of substitution: the `CAT' version basedon binary articulatory features, the `FS/P' version based on perceptual features, andthe `Lad' version based on multivalued features. There is no explicit penalty forindels. The algorithm, which depends heavily on the alignment of stressed vowels,
is described in [Somers, 1999]. The author observes that \alignment can become
somewhat arbitrary" in the cases where the compared strings are not very similar.
After running `CAT' on Covington's test data, he concludes that, in terms of accuracy,
it is as good as Covington's algorithm. I point out a weakness in Somers's approachin Section 4.3.1.

Chapter 4.

Phonetic alignment

28

Gildea and Jurafsky [1996] align phonetic strings in their transducer induction

system. The system induces phonological rules directly from a large corpus of corresponding underlying and surface word-forms. The authors found that a pre-alignmentof the forms greatly improves the performance of the system. The pre-alignment isperformed using the dynamic programming algorithm and a metric that is based on
26 binary features. The cost of substitutions is a straightforward Hamming distance
between two feature vectors. The cost of indels is set at one quarter of the maximum
possible substitution cost. Because the surface forms are generated directly from theunderlying forms by the application of a few simple phonological rules, the alignment
algorithm need not be sophisticated.
Nerbonne and Heeringa [1996; 1997; 1999] investigate the problem of measuring phonetic distance between dialects. The distance between two dialects is estimatedby taking the sum of Levenshtein distances between two sets of corresponding words.
They experimented with at least two di erent feature systems, but they don't provide
the details of the systems. The cost of indels is set at half the average of all substitutions. The individual distances are calculated using the dynamic programmingalgorithm. The computed distance is normalized by dividing its value by the lengthof the longer word. Realizing that \not all features are equally important in classifying the sounds", the authors tried weighting each feature by information gain, which
was computed as the average entropy reduction a feature represents when known.
However, they found that the weighting had an adverse e ect on the quality of thealignments. They also concluded that the Manhattan distance is preferable to both
Euclidean distance and Pearson correlation.
Kessler [1995] was also interested in grouping dialects. The dialects were represented by wordlists, each containing about 50 concepts. He tested several di erent
approaches for computing distance between dialects. The most sophisticated method

Chapter 4.

Phonetic alignment

29

employed twelve multivalued phonetic features. The numeric feature values were assigned arbitrarily, and all features were given the same weight. The distance between
phonetic segments was calculated as the di erence averaged across all twelve features.
The cost of indels is not speci ed in the paper. Kessler found that the feature-based
method performed worse than a simpler phoneme-based method, which employed abinary identity function between phonemes. The dynamic programming algorithm
was used for computing the minimal distance between words in both methods.
Oakes's [2000] program JAKARTA contains a phonetically-based alignment algorithm, whose ultimate purpose is the discovery of regular sound changes. The
array of edit operations, which are adapted from a historical linguistics textbook,
is impressive. It includes lenition, fortition, aphaeresis, apocope, syncope, cluster
reduction, excresescence, dissimilation, epenthesis, prothesis, fusion, vowel breaking,assimilation, and dissimilation. The conditions that must be satis ed to trigger theoperations are also implemented. The cost of all the above operations is uniformly
set at 1, while the cost of the standard substitution and insertion/deletion is set at
2. The phonetic characteristics of sound are stored by means of just three features:
place, manner, and voicing, of which the rst two have more than two values. However, the similarity between phonetic segments is estimated by checking the identityof the feature values only; there is no notion of the relative distance between various
places or manners of articulation. In addition, distinct phonetic segments can haveidentical feature assignments. The distance function is therefore somewhat coarse.
Some properties of the approaches described in this section are juxtaposed inTable 4.7. The label explicit identi es the intended function of the algorithm, while
the label implicit marks the functionality that is present but not overtly used.

Chapter 4.

30

Phonetic alignment

Algorithm

Calculation

Calculation

Dynamic

Phonologicalof alignmentof distanceprogramming

features

Covington [1996]

explicit

implicitnonoSomers [1998]

explicitnonomultivalued

Gildea & Jurafsky [1996]

explicit

implicit

yesbinaryNerbonne & Heeringa [1997]

implicit

explicit

yesbinaryKessler [1995]

implicit

explicityesmultivalued

Oakes [2000]

explicit

explicityesmultivalued

Table 4.7: Comparison of phonetic alignment/distance algorithms.

4.3 Finding the optimal phonetic alignment
The dynamic programming algorithm seems to be optimal for the task of aligning
phonetic strings. Nevertheless, both Somers and Covington opt for other searchstrategies. In this section, I argue that this is unwarranted.
4.3.1 Greedy is not enoughSomers's algorithm is unusual because the selected alignment is not necessarily the
one that minimizes the sum of distances between individual segments. Instead, it
recursively selects the most similar segments, or \anchor points", in the strings being
compared. Such an approach has a serious aw. Suppose that the strings to bealigned are tewos and divut (Table 4.8). Even though the corresponding segments
are slightly di erent, the alignment is straightforward. However, a greedy algorithm
that looks for the best-matching segments rst, will erroneously align the two t's.
Because of its recursive nature, the algorithm has no chance of recovering from suchan error. Regardless of the method of choosing the anchor points, an algorithm that

Chapter 4.

Phonetic alignmentt e w o s
d i v u t

31

- - - - t e w o s
d i v u t - - - -Table 4.8: A correct and an incorrect alignment of a hypothetical cognate pair.
never backtracks is not guaranteed to nd the optimal alignment.
Somers [2000] points out that his alignment algorithm works very well on the children's articulation data, where the stressed vowel is a reliable anchor point. This strategy is rather risky in the context of diachronic phonology, where stress is too volatile
to depend on. Even closely related languages may have di erent stress rules. For
example, stress regularly falls on the initial syllable in Czech and on the penultimate
syllable in Polish, while in Russian it can fall anywhere in the word. Somers [1999]
nevertheless attempts to apply his algorithm to the alignment of cognates. In Section 4.8, I will examine the alignments reported in that paper.
4.3.2 Tree search is too much

The alignment problem is characterized by a small number of elements and a limited
number of interactions between them. Unsurprisingly, applying a depth- rst search
to this problem results in the same operations being performed repeatedly in various
branches of the tree. Why does Covington prefer to use such a costly procedure eventhough he is aware that a more eÆcient algorithm exists?
Covington, who uses a straightforward depth- rst search to nd the optimal alignment, provides the following arguments for eschewing the dynamic programming algorithm.
First, the strings being aligned are relatively short, so the eÆciency ofdynamic programming on long strings is not needed. Second, dynamic
programming normally gives only one alignment for each pair of strings,

Chapter 4.

Phonetic alignment

32

but comparative reconstruction may need the n best alternatives, or allthat meet some criterion. Third, the tree search algorithm lends itself tomodi cation1 for special handling of metathesis or assimilation. [Covington, 1996]
I am not convinced by Covington's arguments. If the algorithm is to be of practicaluse, it should be able to operate on large bilingual wordlists. Most words may bequite short, but some words happen to be rather long. For example, the vocabularies
of Algonquian languages [Hewson, 1999] contain many words that are longer than 20
phonemes. In such cases, the number of possible alignments exceeds 320 , according
to Covington. Even with search-tree pruning, such a combinatorial explosion of thenumber of nodes is certain to cause a painful slow-down. Moreover, combining thealignment algorithm with some sort of strategy for identifying cognates on the basisof phonetic similarity is likely to require comparing thousands of words against one
another. Having a polynomially bound algorithm in the core of such a system iscrucial. In any case, since the dynamic programming algorithm involves neither
signi cantly larger overhead nor greater programming e ort, there is no reason to
avoid using it even for relatively small data sets.
The dynamic programming algorithm is not only considerably faster than tree
search but also suÆciently exible to accommodate the proposed modi cations without compromising its polynomial complexity. In Section 4.4, I demonstrate that it
is possible to retrieve from the distance matrix the set of k best alignments, or theset of alignments that are within  of the optimal solution, and that the basic setof editing operations (substitutions and indels) can be augmented to include bothtranspositions of adjacent segments (metathesis) and compressions/expansions.
1 Covington does not elaborate on the nature of the modi cation.

Chapter 4.

Phonetic alignment

33

4.4 Extensions to the basic dynamic programmingalgorithm
In this section, I describe a number of extensions to the basic dynamic programmingalgorithm, which have been proposed primarily to address issues in DNA alignment,
and I show their applicability to phonetic alignment. Appendix C contains the codethat incorporates most of the extensions into a phonetic alignment algorithm.
4.4.1 Retrieving a set of best alignments

The algorithm in Table 4.4 constructs a single best alignment on the basis of thematrix D. At times, it may be desirable to nd a number of alternative alignmentsthat are close to the optimum. The basic dynamic programming algorithm can beadapted to such a task.
Myers [1995] describes a straightforward modi cation of the basic dynamic programming algorithm that produces all alignments that are within  of the optimal
distance. The idea is to recursively recover only those alignments that correspond to
distances below the threshold score of D[n; m] + . Let T (i; j ) be the distance accumulated during the traversal from D[n; m] to D[i; j ]. On reaching D[i; j ], the three
conditions shown in Table 4.9 are checked, and a distinct alignment is constructed foreach satis ed condition. This is in contrast with the algorithm in Table 4.4, which
maintains a unique alignment throughout the computation. Appendix C contains
actual C++ code that integrates this extension into the alignment algorithm.
In order to nd the k-best alignments, the matrix D can be viewed as a graph withnodes corresponding to the entries in the D matrix, the source at D[n; m], the sink at
D[0; 0], and the arc lengths set according to the Æ function. A number of polynomial-Chapter 4.

3.3
3.6
3.9

Phonetic alignment

34

D[n; m] +   T (i; j ) + D[i 1; j ] + Æ (ai ; )D[n; m] +   T (i; j ) + D[i; j 1] + Æ ( ; bj )D[n; m] +   T (i; j ) + D[i 1; j 1] + Æ (ai ; bj )Table 4.9: The conditions for nding near-optimal alignments.
time algorithms for calculating the k-shortest paths from source to sink in order oflength are available from the operations research literature [Fox, 1973]. A recently
proposed algorithm [Eppstein, 1998] discovers the k-shortest paths connecting a pairof nodes in a directed acyclic graph in time O(e + k), where e is the number of edges
in the graph.
4.4.2 String similarity

An alternative way of evaluating the aÆnity of two strings is to measure their similarity, rather than the distance between them. The similarity of two strings is de ned
as the sum of the individual similarity scores between aligned segments. A similarity
scoring scheme normally assigns large positive scores to pairs of related segments;
large negative scores to pairs of dissimilar segments; and small negative scores toindels. The optimal alignment is the one that maximizes the overall score.
The dynamic programming algorithm of Table 4.3 can be adapted to compute thesimilarity by simply replacing the min in line 1.8 by max. Naturally, the function Æ
will denote the similarity score rather than the edit distance.
The similarity approach is clearly related to the distance approach. In fact, it
is often possible to transform one into the other. An important advantage of thesimilarity approach is the possibility of performing local alignment of strings, which
is discussed in the following section.

Chapter 4.

Phonetic alignment

35

4.4.3 Local and semiglobal alignment

Informally, the optimal local alignment [Smith and Waterman, 1981] of two strings isthe highest scoring alignment of their substrings. This notion is particularly useful
in applications where only certain regions of two strings exhibit high similarity. For
example, the correct alignment of Cree apakoss and Fox wapikonoha `mouse' (Table 4.10) matches the roots of the words and leaves out the unrelated aÆxes. (Double
bars delimit the aligned substrings.) Such an aÆx-stripping behaviour is much morediÆcult to achieve with global alignment.
k a p a k o k ssw k a p i k o k noha

Table 4.10: An example of local alignment.
It should be clear by now why the switch from distance to similarity is not just a
trivial change of terminology. If we tried to identify corresponding substrings by minimizing distance, we would almost always end up with empty or identical substrings.
This is because the distance between any substrings that are less than perfect matches
will be greater than zero. In contrast, a well-designed similarity scheme which rewards
good matches and penalizes poor matches will allow regions of similarity to achieve
meaningful lengths.
The basic dynamic programming algorithm can easily be modi ed to perform
local alignment (Table 4.11). The interpretation of S [i; j ] is changed to the maximal
similarity between suÆxes of the initial substrings of a and b containing i and jelements, respectively. The rst row and the rst column of S are initialized withzeroes. S [i; j ] is set to the minimum of four rather than three values, the fourth being
zero. This has an e ect that no entry of S is a negative number. A zero entry isChapter 4.

4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10
4.11

36

Phonetic alignment

S [0; 0] := 0
for i := 1 to n do
S [i; 0] := 0for j := 1 to m do
S [0; j ] := 0
for i := 1 to n do
for j := 1 to m do
S [i; j ] := max( S [i 1; j 1] + Æ (ai ; bj );S [i 1; j ] + Æ (ai ; );S [i; j 1] + Æ ( ; bj );0)

Table 4.11: The basic algorithm for computing local similarities between two strings.
interpreted as the alignment between the empty suÆxes of the initial substrings. The
optimal similarity is no longer found in S [n; m], but rather it is equal to the maximum
entry in S . The optimal alignment is retrieved by tracing back through the array,starting at the maximum entry but stopping as soon as a zero entry is found.
Semiglobal alignment is intermediate between local and global alignment. The
idea is to assign a similarity score of zero to any indels at the beginning or theend of the alignment. Unlike in local alignment, the unmatched substrings that do
not contribute to the total score cannot occur simultaneously in both strings. The
practical e ect for cognate alignment is that a spurious aÆx can be separated fromonly one of the words being compared, as in the alignment in Table 4.12. Note thatthe unaligned segments do not a ect the similarity score of the two strings, which
would be the case if global alignment was used instead.
k a p a k o s 
w k a p i k o - -s k- k noha

Table 4.12: An example of semiglobal alignment.

Chapter 4.

Phonetic alignment37

k - a p a k o k ssk w a p i k o k noha

Table 4.13: An example of half-local alignment.
The modi cations required to make the dynamic programming algorithm performsemiglobal alignment are straightforward. As in the case of local alignment, the rst
row and column of S have to be initialized with zeroes. However, the zero option(line 11 in Table 4.11) is not added. The optimal similarity is the maximum entry in
the union of the last row and the last column of S . Starting from this entry, we canretrieve the optimal alignment using the usual method, stopping when we reach oneof the zeroes in the rst row or column.
Another possible combination of local and global alignment, which I decided tocall half-local alignment, is useful in aligning cognates. It is designed to re ect thegreater relative stability of the initial segments of words in comparison with theirendings, as exempli ed in Table 4.13.
One way to implement half-local alignment is to fully penalize the leading indels,
but make the trailing ones free. The opening phase of the alignment is performed asin the global case, while its completion obeys the local rules. The particulars of thisapproach can be gleaned from the code in Appendix C.
4.4.4 AÆne gap functions

A gap is a consecutive number of indels in one of the two aligned strings. In some
applications, the occurrence of a gap of length k is more probable than the occurrenceof k isolated indels. In order to take this fact into account, the penalty for a gap canbe calculated as a function of its length, rather than as a simple sum of individualChapter 4.

5.8
5.9
5.10

Phonetic alignment

38

AG[i; j ] = max(AG[i 1; j ] s; S [i 1; j ] (r + s))
BG[i; j ] = max(BG[i; j 1] s; S [i; j 1] (r + s))
S [i; j ] = max(S [i 1; j 1] + Æ (ai ; bj ); AG[i; j ]; BG[i; j ])Table 4.14: The modi cation of the basic dynamic programming algorithm required
to accommodate aÆne gap scores.
indels. One solution is to use an aÆne function of the form gap(x) = r + sx, where r
is the penalty for the introduction of a gap, and s is the penalty for each symbol in
the gap.
Gotoh [1982] describes a method for incorporating aÆne gap scores into the dynamic programming alignment algorithm. Two additional arrays (AG and BG) record
the best alignment that ends with a gap in the corresponding string. AG[i; j ] is interpreted as the minimal distance between the initial substrings of a and b when thesubstring of a ends with a gap, Similarly, BG corresponds to the case when the substring of b ends with a gap. The body of the main loop in the modi ed algorithm isshown in Table 4.14 (lines 5.8{5.10 replace lines 1.8{1.10 in Table 4.3).
Gotoh is not totally categorical about the initial settings of AG and BG. I foundthat AG[0; j ] and BG[i; 0] must be set to +1 for all values of i and j . In this way,
we can be sure that the distance between two unrelated strings of length 1 is in fact
equal to 2(r + s), as required.
4.4.5 Additional edit operations

The basic set of edit operations consists of substitutions and insertions/deletions.
Another useful operation is compression/expansion. In the compression/expansion
operation two contiguous units of one string correspond to a single unit of the otherstring. The operations of compression and expansion are distinct in the context ofChapter 4.

39

Phonetic alignmentf a k t- e c -f a k t- e - cf a kt- e cTable 4.15: An example of cognate alignment that requires the operation of compression/expansion.
transforming one string into another by a series of edit operations. However, in thecontext of nding an optimal alignment, they are really mirror images of each other,in the same way as the operations of insertion and deletion. We could as well talkabout various types of correspondences: 0 : 1, 1 : 1, 1 : 2, etc.
In the context of the alignment of cognates, the compression/expansion operation
facilitates the expression of complex correspondences. For example, in the alignmentof stems of Latin factum and Spanish hecho, the a ricate [c] should be linked withboth [k] and [t] rather than with just one of them, because it originates from themerger of the two consonants. Therefore, the rightmost alignment in Table 4.15 is
the most accurate. Note that emulating compression as a sequence of substitution anddeletion is unsatisfactory because it cannot be distinguished from an actual sequenceof substitution and deletion.
Oommen [1995] formally de nes the string alignment algorithm that incorporates
the compression/expansion operation. The modi cation is straightforward. The lines
4.8{4.11 of the algorithm given in Table 4.11 on page 36 should be substituted withthe code shown in Table 4.16. Two additional cases are simply added to the max
expression. Also, minor changes are required in the initialization of the rst two
rows/columns of matrix S , and in the retrieval of the optimal alignment from matrix
S . Appendix C contains the details of the modi cations.
The operation of transposition of adjacent segments can also be integrated into theChapter 4.

40

Phonetic alignment

dynamic programming algorithms, much along the same lines as in the case of compression/deletion. The details of the necessary modi cations are given in [Lowranceand Wagner, 1975] and [Oommen and Loke, 1997].

4.5 Comparing phonetic segments
The distance/similarity function is of crucial importance in the phonetic alignment.
The numerical value assigned by the function to a pair of segments is referred to as
the substitution cost (in the context of distance), or as the substitution score (in thecontext of similarity). The function can be extended to cover other edit operations,such as insertions/deletions and compressions/expansions. Table 4.17 shows the mostelementary distance function de ned on a subset of phonetic segments. It assigns azero cost to identical segments and a unary cost to non-identical segments. Such afunction is simple to implement, but will perform poorly on phonetic alignment. Thissection is concerned with the problem of designing a better function, which would
encode the knowledge about universal characteristics of sounds.
6.8
6.9
6.10
6.11
6.12
6.13

S [i; j ] := max( S [i 1; j 1] + Æ (ai ; bj );S [i 1; j ] + Æ (ai ; );S [i; j 1] + Æ ( ; bj );S [i 2; j 1] + Æ (ai 1 ai ; bj );S [i 1; j 2] + Æ (ai ; bj 1 bj );0)

Table 4.16: The modi cation of the dynamic programming algorithm that incorporates the compression/expansion operation.

Chapter 4.

a
i
y
n
p
r
s

41

Phonetic alignment

a
0
1
1
1
1
1
1

i
1
0
1
1
1
1
1

y
1
1
0
1
1
1
1

n
1
1
1
0
1
1
1

p
1
1
1
1
0
1
1

r
1
1
1
1
1
0
1

s
1
1
1
1
1
1
0

Table 4.17: An elementary cost function.
4.5.1 Feature-based metrics

Covington [1996], for his cognate alignment algorithm, constructed a special distancefunction (Table 4.18). It was developed by trial and error on a test set of 82 cognate
pairs from various related languages. The distance function is very simple; it uses
no phonological features and distinguishes only three types of segments: consonants,
vowels, and glides.
The rather cryptic explanation for assigning a lower penalty to \skips precededby another skip" refers to the fact that in diachronic phonology not only individual
segments but also entire morphemes and syllables are sometimes deleted in a single
event. It is worth noting that the indel penalties in Covington's scheme can be
expressed by an aÆne gap function (cf. section 4.4.4) with r = 10 and s = 40.
Contrary to its name, Covington's distance function is not a metric because it
does not satisfy all of the required axioms enumerated in Table 4.2 on page 23. The
zero property is not satis ed because the function's value for two identical vowels is
2 In this context, precede is used to mean immediately precede.

Chapter 4.

Phonetic alignment

42

Penalty Conditions
0 Exact match of consonants or glides (w, y)
5 Exact match of vowels (re ecting the fact that the aligner
should prefer to match consonants rather than vowels if
it must choose between the two)
10 Match of two vowels that di er only in length, or i and y,or u and w
30 Match of two dissimilar vowels
60 Match of two dissimilar consonants
100 Match of two segments with no discernible similarity
40 Skip preceded2 by another skip in the same word (re ecting
the fact that aÆxes tend to be contiguous)
50 Skip not preceded by another skip in the same word
Table 4.18: Covington's [1996] \evaluation metric".
greater than zero. Also, the triangle inequality does not hold in all cases; for example:p(a; i) = 30 and p(i; y ) = 10, but p(a; y ) = 100, where p(x1 ; x2 ) is the penalty foraligning [x1] with [x2 ].
Table 4.19 illustrates the \low resolution" of Covington's distance function. Many
important characteristics of sounds, such as place or manner of articulation, are ignored, which implies that [m] and [h] are assumed to be as similar as [t] and [th ], andboth yacht and will are treated identically as a glide-vowel-consonant string. Covington [1998] acknowledges that his distance function is \just a stand-in for a moresophisticated, perhaps feature-based, system".
Both Gildea and Jurafsky [1996] and Nerbonne and Heeringa [1997] base theirdistance functions on binary features. Phonetic segments are represented by binary
vectors in which every entry stands for a single articulatory feature. Such a representation allows one to distinguish a large number of phonetic segments. The distanceChapter 4.

a
i
y
n
p
r
s

43

Phonetic alignment

a
5
30
100
100
100
100
100

i
30
5
10
100
100
100
100

y
100
10
0
60
60
60
60

n
100
100
60
0
60
60
60

p
100
100
60
60
0
60
60

r
100
100
60
60
60
0
60

s
100
100
60
60
60
60
0

Table 4.19: A partial distance matrix for Covington's distance function.
between two segments is de ned as the Hamming distance between two feature vectors, that is, the number of binary features by which the two sounds di er. A distancefunction de ned in such a way satis es all metric axioms.
It is interesting to compare the values of Covington's distance function with theaverage Hamming distances produced by a feature-based metric. Since neither Gildea
and Jurafsky [1996] nor Nerbonne and Heeringa [1997] present their feature vectors insuÆcient detail to perform the calculations, I adapted a fairly standard set of binaryfeatures from Hartman [1981]. Twenty- ve letters of the Latin alphabet (all but q)
were taken to represent a sample set of most frequent phonemes. The feature vectors
corresponding to the set are shown in Table 4.20. Table 4.21 contains a portion of
the corresponding distance matrix.
Table 4.22 shows Covington's \penalties" juxtaposed with the average feature
distances between pairs of segments computed for every clause in Covington's metric.
By de nition, the Hamming distance between identical segments is zero. The distance
between the segments covered by clause #3 is also constant and equal to one (theChapter 4.

44

Phonetic alignment

feature name

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

r

s

t

u

v

w

x

y

z

+ { { { + { { { + { { { { { + { { { { + { + { + {[spread glottis]{ { { { { { { + { { { { { { { { { { { { { { { { {+ + { + + { + { + + { + + + + { + { { + + + { + +[voice][back]+ { { { { { + + { { + { { { + { { { { + { + + { {{ { + + { { { { { + { + { + { { + + + { { { { { +[coronal][continuant]+ { { { + + { + + { { { { { + { + + { + + + + + +{ { + { { { + { + + + { { { { { { { { + { + + + {[high][strident]{ { + { { + { { { + { { { { { { { + { { + { { { +[round]{ { { { { { { { { { { { { { + { { { { + { + { { {[syllabic]+ { { { + { { { + { { { { { + { { { { + { { { { {[obstruent]{ + + + { + + + { + + { { { { + { + + { + { + { +{ { { { { { { { { { { { + + { { { { { { { { { { {[nasal][consonantal]{ + + + { + + + { + + + + + { + + + + { + { + { ++ { { { { { { + { { { { { { { { { { { { { { { { {[low][anterior]{ + + + { + { { { + { + + + { + + + + { + { { { +[distributed]+ + + + + { + + + { + { + { + + { + + + { + + + +[delayed release] { { + { { { { { { + { {{ { { { { { { { { { { { {[tense]Table 4.20: Feature vectors adopted from Hartman [1981].

a
i
y
n
p
r
s

a
0
3
4
10
9
8
10

i
3
0
1
9
8
7
9

y
4
1
0
8
7
6
8

n
10
9
8
0
5
2
6

p
9
8
7
5
0
5
3

r
8
7
6
2
5
0
4

s
10
9
8
6
3
4
0

Table 4.21: A partial distance matrix based on binary features.

Chapter 4.

Phonetic alignment

45

Clause in Covington's
distance function

Covington's Average Rescaled
penalty Hamming average
distance distance
1 \identical consonants or glides"
0
0.0
0.0
2 \identical vowels"
5
0.0
0.0
3 \vowel length di erence only"
10
1.0
12.4
4 \non-identical vowels"
30
2.2
27.3
5 \non-identical consonants"
60
4.81
58.1
6 \no similarity"
100
8.29
100.0
Table 4.22: The clause-by-clause comparison of Covington's distance function and afeature-based distance function.
feature in question being [long] or [syllabic]). The remaining average feature distanceswere calculated using the sample set of 25 phonemes. In order to facilitate comparison,
the rightmost column of Table 4.22 contains the average distances rescaled between
the minimum and the maximum value of Covington's metric.
The correlation between Covington's penalties and the average Hamming distances is very high (0:998), which demonstrates that feature-based phonology provides
a theoretical basis for Covington's manually constructed distance function.
4.5.2 Multivalued features

Although binary features are elegant and widely used, they might not be optimal forphonetic alignment. Their primary motivation is to classify phonological oppositions
within a language rather than to re ect universal characteristics of sounds. In astrictly binary system, sounds that are similar often di er in a disproportionately
large number of features. [y], which is the initial sound of the word you, and [j],which is the initial sound of the word Jew, have an astounding 9 contrasting featureChapter 4.

Phonetic alignment

46

values; yet the sounds are close enough to be habitually confused by speakers whose
rst language is Spanish.
It can be argued that allowing features to have several possible values results in amore natural and phonetically adequate system. For example, there are many possible
places of articulation, which form a near-continuum, as illustrated in Figure 4.1.
Ladefoged [1995] devised a phonetically-based multivalued feature system. Thissystem was adapted by Connolly [1997] and implemented by Somers [1998]. It contains about twenty features, some of which, such as Place, can take as many as ten
di erent values, while others, such as Nasal, are basically binary oppositions. For
example, the feature Voice has ve possible values: [glottal stop], [laryngealized],[voice], [murmur], and [voiceless]. All feature values are assigned numerical values
between 0 and 1.
The main problem with both Somers's and Connolly's approaches is that they
do not di erentiate the weights, or saliences, that express the relative importance ofindividual features. For example, they assign the same salience to the feature [place] asto the feature [aspiration], which results in a smaller distance between [p] and [k] thanbetween [p] and [ph ]. In my opinion, in order to avoid such incongruous outcomes,
the salience values need to be carefully di erentiated; speci cally, the features [place]and [manner] should be assigned signi cantly higher saliences than other features.
Although there is no doubt that not all features are equally important in classifying
sounds, the question of how to how to assign salience weights to features in a principledmanner is still open. Nerbonne and Heeringa [1997] experimented with weighting eachfeature by information gain but concluded that it actually had a detrimental e ect on
the produced alignments. Kessler [1995] mentions the uniform weighting of features
as one of possible reasons for the poor performance of his feature-based similarity
measure. Covington [1996] vaguely proposes \using multivariate statistical techniquesChapter 4.

47

Phonetic alignment

Bilabial

DentalLabio−dental

Palato−alveolar

Alveolar

Retroflex

PalatalVelar

UvularFigure 4.1: Places of articulation.

Chapter 4.

Phonetic alignment48

and a set of known `good' alignments" for calculating the relative importance ofeach feature. In my opinion, it seems reasonable to try and derive the saliences
automatically from a large corpus of aligned cognates (Durbin et al. [1998] describe
methods of generating substitution matrices from alignment data). Unfortunately,
it is not clear how to obtain a representative training set in the rst place. Even if
we ignore the problem of the bias introduced by selecting cognates from particularlanguage pairs, the task of establishing the correct alignment of cognates is verytime consuming and often requires detailed knowledge of the history of the languages
involved.
4.5.3 Similarity and distance

Although all previously proposed alignment algorithms (Table 4.7) measure relatedness between phones by means of a distance function, such an approach does notseem to be the best for dealing with phonetic segments. The fact that Covington's
distance function is not a metric is not an accidental oversight; rather, it re ects certain inherent characteristics of phones. Since vowels are in general more volatile thanconsonants, the preference for matching identical consonants over identical vowels isjusti ed. This insight cannot be expressed by a metric, which, by de nition, assigns
a zero distance to all identical pairs of segments. Nor is it certain that the triangle
inequality should hold for phonetic segments. A phone that has two di erent placesof articulation, such as labio-velar [w], can be close to two phones that are distantfrom each other, such as labial [b] and velar [g].
In my algorithm, below, I employ the similarity-based approach to comparing segments (cf. section 4.4.2). The similarity score for two phonetic segments indicates how
similar they are. Under the similarity approach, the score obtained by two identicalChapter 4.

Phonetic alignment

49

segments does not have to be constant. Another important advantage of the similarity approach is the possibility of performing local alignment of phonetic strings, which
is discussed in section 4.4.3. In local, as opposed to global, alignment, only similar
substrings are matched, rather than entire strings. This often has the bene cial e ectof separating in ectional and derivational aÆxes from the roots. Such aÆxes tend to
make nding the proper alignment more diÆcult. It would be unreasonable to expectaÆxes to be stripped before applying the algorithm to the data, because one of thevery reasons to use an automatic aligner is to avoid analyzing every word individually.
It would be ideal to have, as Kessler [1995] puts it, \data telling how likely it isfor one phone to turn into the other in the course of normal language change." Such
universal scoring schemes exist in molecular biology under the name of Dayho 's matrices for amino acids [Dayho et al., 1983]. However, the wealth of data available for
DNA sequences is simply not attainable in diachronic phonology. Moreover, the number of possible sounds is greater than the number of amino acids. The International
Phonetic Alphabet, which is a standard for representing phonetic data, contains over
80 symbols, most of which can be modi ed by various diacritics. Assembling a matrix
of such size by deriving each individual entry is not practicable. In the absence of auniversal scoring scheme for pairs of phonetic segments, the calculation of similarity
scores on the basis of multivalued features with salience coeÆcients seems to be thebest solution.

4.6 The algorithm
Many of the ideas discussed in previous sections have been incorporated into the newalgorithm for the alignment of phonetic strings. Similarity rather than distance isused to determine a set of best local alignments that fall within  of the optimal

Chapter 4.

Phonetic alignment

50alignment. The set of operations contains insertions/deletions, substitutions, andexpansions/compressions. but not transpositions, which have been judged too sporadic to justify their inclusion in the algorithm. Multivalued features are employed
to calculate similarity of phonetic segments. AÆne gap functions seem to make little di erence in phonetic alignment when local comparison is used, so the algorithm
makes no distinction between clustered and isolated indels.
Table 4.23 contains the main components of the algorithm. First, the dynamic
programming approach is applied to compute the similarity matrix S using the scoring functions. For simplicity, S (i; j ) is de ned to return 1 if either i or j isnegative. Since local alignment is assumed, the rst row and the rst column of thematrix S are initialized with zeros. The optimal score is the maximum entry in thewhole matrix. Every matrix entry that exceeds the threshold score T is the starting
point of one or more alignments.
The recursive procedure Retrieve is shown in Table 4.25. The alignment isassembled by traversing the matrix until a zero entry is encountered. The parameters
i and j are the coordinates of the current matrix entry. The partial alignment isstored on the stack Out, which is a last-in- rst-out data structure. The parameter s
accumulates the alignment's score. Note that the alignments are printed out in theorder of decreasing indices. The order may be reversed by simply indexing the string
starting from the end rather than from the beginning.
If a best alignment contains a sequence of two or more consecutive indels alternating between the two strings, some of the retrieved alignments may happen to beequivalent. In such a case, a unique alignment can be obtained by ltering out allalignments in which an indel in the rst string is immediately followed by an indel inthe second string. This constraint, which corresponds to the ordered-alternating-skips
rule of Covington [1998], would suppress both the second and the third alignment ofChapter 4.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
23
24
25
26

Phonetic alignment

51

algorithm Alignment
input: phonetic strings x and youtput: alignment of x and yde ne S (i; j ) = 1 when i < 0orj < 0
for i := 0 to jxj do
S (i; 0) := 0for j := 0 to jy j do
S (0; j ) := 0
for i := 1 to jxj do
for j := 1 to jy j do
S (i; j ) := max(
S (i 1; j ) + skip(xi ),S (i; j 1) + skip(yj ),S (i 1; j 1) + sub (xi ; yj ),S (i 1; j 2) + exp (xi ; yj 1yj ),S (i 2; j 1) + exp (xi 1 xi ; yj ),0)
T := (1 )  maxi;j S (i; j )for i 1 to jxj do
for j 1 to jy j do
if S (i; j )  T thenRetrieve(i; j; 0)

Table 4.23: The algorithm for computing the alignment of two phonetic strings.

Chapter 4.

52

Phonetic alignmentg o - - g - o-  -- g o - -

Table 4.24: Three equivalent alignments.
English go and Latin ire `go' shown in Table 4.24, but not the rst one.
The scoring functions are de ned in Table 4.26. Cskip, Csub, and Cexp are themaximum scores for indels, substitutions, and expansions, respectively. Cvwl determines the relative weight of consonants and vowels. Phonetic segments are expressed
as vectors of feature values. The function di (p; q; f ) returns the di erence between
segments p and q for a given feature f . Set RV contains features relevant for comparing two vowels: Syllabic, Nasal, Retro ex, High, Back, Round, and Long. Set
RC contains features for comparing other segments: Syllabic, Manner, Voice, Nasal,
Retro ex, Lateral, Aspirated, and Place. A special feature Double, which has the same
possible values as Place, indicates the second place of articulation. When dealing withdouble-articulation consonantal segments, only the nearest places of articulation areused. The numerical values of features and their saliences are discussed in the next
section.

4.7 Implementation
ALINE is a publicly available3 implementation of the algorithm for the alignment ofphonetic strings. The program is written in C++ and runs under Unix. It accepts alist of word pairs from the standard input, and produces a list of alignments and theirsimilarity scores on the standard output. Although local comparison is the default,
kondrak/.

3 At http://www.cs.toronto.edu/

Chapter 4.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Phonetic alignment

procedure Retrieve(i; j; s)
if S (i; j ) = 0 thenprint(Out)print(\alignment score is s")else
if S (i 1; j 1) + sub (xi ; yj ) + s  T thenpush(Out, \align xi with yj ")Retrieve(i 1; j 1; s + sub(xi; yj ))pop(Out)
if S (i; j 1) + skip(yj ) + s  T thenpush(Out, \align null with yj ")Retrieve(i; j 1; s + skip(yj ))pop(Out)
if S (i 1; j 2) + exp (xi ; yj 1yj ) + s  T thenpush(Out, \align xi with yj 1yj ")Retrieve(i 1; j 2; s + exp(xi ; yj 1yj ))pop(Out)
if S (i 1; j ) + skip(xi ) + s  T thenpush(Out, \align xi with null")
Retrieve(i 1; j; s + skip(xi))
pop(Out)
if S (i 2; j 1) + exp (yj ; xi 1 xi ) + s  T thenpush(Out, \align xi xi 1 with yj ")Retrieve(i 2; j 1; s + exp(yj ; xi 1 xi))pop(Out)
Table 4.25: The procedure for retrieving alignments from the similarity matrix.

53

Chapter 4.

54

Phonetic alignment

skip (p) = Cskip
sub (p; q ) = CsubÆ (p; q ) V (p) V (q )

exp(p; q1 q2 ) = Cexp Æ (p; q1 ) Æ (p; q2 )V (p) max(V (q1 ); V (q2 ))where(
0 if p is a consonant
V (p) =
Cvwl otherwiseÆ (p; q ) =

where

R =

X
f 2R

(

di (p; q; f )  salience(f )RCRV

if p or q is a consonant
otherwise

Table 4.26: Scoring functions.
the program can be re-compiled to perform global and semiglobal alignment.
The behavior of the program is controlled by command-line parameters: the valueof  for producing near-optimal alignments, and the four constants described in theprevious sections. The default values of the parameters are  = 0, Cskip = {10, Csub
= 35, Cexp = 45, and Cvwl = 10.
Table 4.27 enumerates the features that are currently used by ALINE and theirsalience settings. Feature values are encoded as oating-point numbers in the range[0:0; 1:0]. The numerical values of four principal features are listed in Table 4.28.
The remaining features have exactly two possible values, 0:0 and 1:0. A part of theresulting similarity matrix is shown in Table 4.29.
The numerical values in Table 4.28 are taken from Ladefoged [1995], who established them on the basis of experimental measurements of distances between vocal

Chapter 4.

Phonetic alignment

55

Syllabic 5 Place40
Voice
10 Nasal
10Lateral 10 Aspirated 5High
5 Back5
Manner 50 Retro ex 10Long
1 Round
5
Table 4.27: Features used in ALINE and their salience settings.
organs during speech production. The fact that the scheme is based on articulatory phonetics does not necessarily imply that it is optimal for phonetic alignment.
Similar feature schemes of Connolly [1997] and Kessler [1995] also employ discrete
ordinal values scaled between 0 and 1. The former author incorporates and expandson Ladefoged's proposal, while the latter simply selects the values arbitrarily.
The salience values in Table 4.27 and the default values of the command-line
parameters have been established by trial and error on a small set of alignments that
included the alignments of Covington [1996]. By no means should they be considered
as de nitive, but rather as a starting point for future re nements. It is worth notingthat practically all other alignment algorithms assign equal weight to all features,
which, although super cially more elegant, does not address the problem of unequal
relevance of features.
Unlike the strictly binary feature systems, the feature system proposed here ishighly dynamic in the sense that the similarity matrix can be modi ed by changing
feature saliences or numerical values within features. Such modi cations are important as it would be unrealistic to expect a single set of values to be optimal for
all types of languages. The exibility of the system makes it possible to adapt thesimilarity matrix to the data by using machine-learning techniques.

Chapter 4.

Phonetic alignment

Feature name Phonological term Numerical valuePlace[bilabial]
1.0[labiodental]
0.95[dental]0.9[alveolar]
0.85[retro ex]
0.8[palato-alveolar]
0.75[palatal]
0.7[velar]0.6[uvular]0.5[pharyngeal]
0.3[glottal]
0.1
Manner[stop]
1.0[a ricate]
0.9[fricative]
0.8[approximant]
0.6[high vowel]
0.4[mid vowel]
0.2[low vowel]
0.0High[high]
1.0
[mid]
0.5
[low]
0.0
Back
[front]1.0[central]
0.5[back]
0.0
Table 4.28: Multivalued features and their values.

56Chapter 4.

57

Phonetic alignment

a
i
y
n
p
r
s

a
15
8
2
50
56
28
40

i
8
15
10
26
32
4
16

y
2
10
15
21
27
1
11

n
50
26
21
35
9
7
5

p
56
32
27
9
35
13
19

r
28
4
1
7
13
35
3

s
40
16
11
5
19
3
35

Table 4.29: A partial similarity matrix based on multivalued features with diversi ed
salience values.
4.7.1 Data input

Representing phonetically transcribed words using only the ASCII characters is nota trivial problem. The International Phonetic Alphabet, which is a standard for
representing phonetic data, contains over 80 symbols, most of which can be modi ed
by various diacritics. Systems that assign a numerical value to every combination,such as ISO 10646/Unicode, produce totally opaque data, which is diÆcult to enterand maintain.
The usual solution is to devise an ad-hoc scheme in which a mixture of alphanumeric characters and punctuation marks are used to represent phonetic symbols.
For example, Eastlack [1977], in his simulation of systematic sound change in IberoRomance, represents [O] by the numeral 9, and [ñ] by N followed by a comma. Such
schemes may be adequate to represent sounds from a particular language or language
family, but usually do not scale up very well when more diverse data needs to be
encoded. What is needed is a system powerful enough to express all IPA symbols,

Chapter 4.

Phonetic alignment

58

yet transparent enough to allow visual veri cation of the data.
In order to encode the phonetic data for ALINE, I designed a scheme in which
every phonetic symbol is represented by a single lowercase letter followed by zero or
more uppercase letters. The initial lowercase letter is the base letter most similar tothe sound represented by the phonetic symbol. Tables 4.30 and 4.31 show the default
feature assignments for the base letters. The remaining uppercase letters stand forthe features in which the represented sound di ers from the sound de ned by thebase letter. For example, the French front nasal vowel [÷ ], which occurs in the word
un, is represented by `oFN', where F stands for front, and N stands for nasal. The
full set of codes is given in Table 4.32. The scheme has a number of advantages: it isexible | new codes can be easily introduced; it can represent any sound that canbe expressed using phonetic features; and it leads to readable and concise encodingof the data (the ratio of the number of characters used in the encoding to the numberof encoded phonetic symbols is usually below 1:2). The only drawback of the scheme
is its dependence on the particular feature system that is used in ALINE.
SAMPA (Speech Assessment Methods Phonetic Alphabet) has been proposed asa standard for representing phonetic segments using ASCII characters. The system
is similar to the scheme used in ALINE, but, in my opinion, not nearly as practical.
First, it does not include all IPA symbols. Second, the use of non-alphabetic ASCII
characters makes it somewhat opaque. Finally, unlike my feature-based scheme, it
requires a large lookup table that covers all phonetic symbols. It would not be diÆcult,however, to write a script for converting SAMPA-encoded data to the form requiredby ALINE.

Chapter 4.

a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z

Phonetic alignment

Place
MannerSyl Vce Nas Ret Latvelar
low vowel
11000bilabial
stop
0
1
0
0
0
alveolara ricate
00000alveolar
stop
0
1
0
0
0
palatalmid vowel
1
1000
labiodental
fricative
0
0
0
0
0
velar
stop
0
1
0
0
0
glottalfricative
00000palatalhigh vowel
1
1
0
0
0
alveolara ricate
0
1
0
0
0
velar
stop
0
0
0
0
0
alveolarapproximant 01001bilabial
stop
0
1
1
0
0
alveolar
stop
0
1
1
0
0
velar
mid vowel
11000bilabial
stop
0
0
0
0
0
glottal
stop
0
0
0
0
0
retro exapproximant 010
10alveolarfricative
000
00
alveolar
stop
0
0
0
0
0
velar
high vowel
1
1
0
0
0
labiodental
fricative01
0
00velar (bilabial) high vowel
1
1
0
0
0
velar
fricative
0
0
0
0
0
velar
high vowel
1
1
0
0
0
alveolarfricative01
0
00
Table 4.30: The default feature assignments for base letters.

Place
MannerHigh BackRounda velarlow vowellowcentral0e palatal
mid vowel mid
front
0
i palatal
high vowel high front0
o velarmid vowel midback1
u velarhigh vowel high back1
w velar (bilabial) high vowel high back1
y velarhigh vowel high front
0
Table 4.31: Additional feature assignments for non-syllabic segments.

59

Chapter 4.

Phonetic alignment60

Code Feature name Feature value
A Aspirated[aspirated]
B Back[back]C Back[central]
D Place[dental]F Back[front]H Long[long]N Nasal[nasal]P Place[palatal]
R Round[round]S Manner[fricative]
V Place[palato-alveolar]
Table 4.32: ALINE's input codes.

4.8 Evaluation
A proper evaluation of an alignment algorithm requires a \gold standard" | a suÆciently large set of alignments of nontrivial word pairs. Unfortunately, such a standard
is not easily available, and constructing it from scratch would be costly and diÆcult.
Although linguistic textbooks contain examples of genetically related words, theiralignment is almost never given explicitly. The determination of the correct alignment of two remote cognates is a task that usually calls for an expert historicallinguist. In addition, the compilation of test data by the author of the tested algorithm runs the risk of introducing a subconscious bias re ecting his knowledge of its
strengths and weaknesses.
Instead of building my own test set, I decided to use the 82 cognate pairs compiled
by Covington [1996]. The complete set, which contains mainly words from English,
German, French, Spanish, and Latin, is included in Appendix D. Unfortunately, thefact that the set was also used for tuning the parameters of ALINE reduces the valueof the evaluation described in this section.
Covington's data set is not a particularly good candidate for a benchmark. In

Chapter 4.

Phonetic alignment

61

addition to the errors in the phonetic transcriptions and the inconsistent selection ofmorphological forms, the set contains too many undemanding word pairs: how bad
would an algorithm have to be to misalign long:lang? Nevertheless, it did become
something of a benchmark when Somers [1999], in order to demonstrate that his andCovington's alignments are of comparable quality, applied his algorithm to the set.
4.8.1 Qualitative evaluation

The evaluation involves the alignment algorithms of Covington [1996], Somers [1999],
and Oakes [2000], as well as ALINE. Oakes's program JAKARTA has been provided
by the author. I re-implemented Covington's aligner from the description given in
his article, and veri ed that my version produces the same alignments. Somers'salignments were reconstructed from the description of the di erences between his
and Covington's results, complemented by my understanding of the behaviour of his
algorithm. Appendix D contains a complete set of alignments of the 82 cognate pairs
generated by ALINE side by side with Covington's alignments. In order to performa fair and consistent comparison, I refrained from making any corrections in the setof cognates.
Some of the alignments produced by Covington's algorithm give clues about the
weaknesses of his approach. In Spanish arbol and French arbre, his aligner prefers tomatch [o] with [@] than to match [r] with [l]. The reason is that it has only a binary
notion of identity or non-identity of consonants, without any gradation of similarity
in between. This lack of discernment sometimes causes a proliferation of alternativealignments. In the case of English sh and Latin piscis there are four of them, andwithout the bias against isolated indels there would be six.
The version that Somers applied to the cognate data set (CAT) employs binary,Chapter 4.

Phonetic alignment

62

rather than multivalued, features. Since CAT distinguishes between individual consonants, it sometimes produces more accurate alignments than Covington's aligner.
For example, in the English/Greek pair daughter:thugater, it correctly opts for linking[d] with [th] rather than with [g]. However, because of its unconditional alignment of
the stressed vowels, CAT is guaranteed to fail in all cases when the stress has moved
in one of the cognates. For example, in the Spanish/French pair cabeza:cap, it blindly
matches a labial stop with a dental fricative rather than with another labial stop.
In spite of its comprehensive set of edit operations, Oakes's JAKARTA aligner
performs poorly in comparison with the other algorithms. It does display occasional
brilliance; for example, it posits a complex correspondence between [t] with [ts] intongue:Zunge. However, it also makes elementary mistakes: it frequently aligns consonants with vowels, postulates unusual sound changes with no foundation, and has
a tendency to align shorter words with the suÆxes of the longer words.
With the exception of a few mistakes, ALINE does a good job both on closely
and remotely related language pairs. On the Spanish/French set, ALINE makes no
mistakes at all. Unlike Covington's aligner, it properly aligns [l] in arbol with thesecond [r] in arbre. On the English/German data, it selects the correct alignment inthose cases where Covington's aligner produces two alternatives. In the nal, mixed
set, ALINE makes a single mistake in daughter:thugater, in which it posits a dropped
pre x rather than a syncopated syllable; in all other cases, it is right on target.
The examples in Table 4.33 are taken from the English{Latin set, which is particularly interesting due to the ample diachronic distance between the two languages.
ALINE correctly discards in ectional aÆxes in piscis and are, and posits the operation of compression/expansion to account for the cases of diphthongization of vowels
in I and tooth. In sh:piscis, Covington's aligner produces four alternative alignments, while ALINE selects the correct one. Both algorithms are technically wrong

Chapter 4.

63

Phonetic alignment

three:tres
blow: arefull:plenus
sh:piscis
I:ego
tooth:dentis

Covington's alignments

ALINE's alignments

r
t r
b l
f l
f p l
f p i
- e g
- d e

k T r iy kk t r e k s

T

i y
e s
- - o w
a r e - - u l
e n u s- - i ss k i sa yo - t u w T
n t i - sk b l o k w
k f l a k re
k f u l kk p - l k enus
k f i s k
k p i s k kis
k ay kk e k gok t uw T k
den k t i s k

Table 4.33: Examples of alignments of English and Latin cognates.
on tooth:dentis, but this is hardly an error considering that only the information
contained in the phonetic string is available to the aligners. In order to produce ahistorically correct alignment shown in Table 4.34, an aligner would have to know
something about regular sound correspondences between English and Latin. I will
return to this example in Chapter 6.
k t uw - T k
k d e n t k is

Table 4.34: The correct alignment of tooth:dentis.

Chapter 4.

SubsetPhonetic alignment64# of pairs

Score
Covington Somers Oakes Kondrak
Spanish{French
20
19.0
17.0
15.0
20.0
English{German 20
18.0
18.0
16.0
18.5
English{Latin
25
18.1
19.5
9.0
24.0
Fox{Menomini
10
9.0
9.0
9.0
9.5
Other
7
4.7
3.0
4.0
6.0
Total
82
68.8
66.5
53.0
78.0
Table 4.35: Evaluation of alignment algorithms on Covington's data set.
4.8.2 Quantitative evaluation

The tables containing the generated alignments take up a substantial part of Covington's article. However, the true alignments are never explicitly given; the author
only refers to them indirectly when he discusses the errors made by his program. In
order to make the comparison of various algorithms more rigorous, I recreated theset of true alignments to the best of my knowledge, verifying the diÆcult cases in thehistorical linguistic literature [Buck, 1949; Hall, 1976; Bloom eld, 1946], which takes
into account the results of research conducted over a period of many decades, andoften also historical records that document the evolution of languages.
For the comparison, I adopted a straightforward evaluation scheme. One pointis awarded for every correct unique alignment. In the cases of k > 1 alternativealignments, the score is k1 if one of them is correct, and 0 otherwise. So, for example, Covington's aligner received 0:33 for the pair ager:ajras because one of the three
proposed alignments is right. In order to make the playing eld even, complex correspondences, such as compression/expansion, were treated as optional. The results ofChapter 4.

Phonetic alignment65

the manual evaluation are given in Table 4.35.
ALINE is a clear winner in the comparison, achieving over 95% accuracy. Somers's
results are almost as good as Covington's, which, as Somers [1999] points out, \is agood result for CAT [...] considering that Covington's algorithm is aimed at dealing
with this sort of data." Oakes's JAKARTA scores well below the rest.

4.9 Conclusion
The results on a limited set of cognate pairs show that, overall, ALINE produces
better alignments than Covington's and Somers's algorithms. However, the methodof evaluation used in this chapter is not completely satisfactory. In the absence of amore comprehensive test set, a better form of evaluation would be to apply ALINE toa task on which its performance could be easily appraised. Identi cation of cognates,
which is the topic of Chapter 5, is an example of such a task. An alignment score of
two words can be taken as a measure of their phonetic similarity, which in turn is agood indicator of the likelihood of cognation.
The alignment of corresponding segments in potential cognates is an essential
step of the comparative method of language reconstruction. ALINE, as well as otheralignment algorithms described in this section, aligns one word pair at a time, andhas no learning ability. The lack of knowledge about regular sound correspondences
limits the accuracy of the alignment. In Chapter 6, I will show how the alignment ofcognates can be driven by automatically determined correspondences.

Chapter 5
Identi cation of cognates
In the narrow sense used in historical linguistics, cognates are words in related languages that have developed independently from the same proto-form (so-called genetic cognates). Due to their common origin, genetic cognates often sound alike andhave the same or similar meaning. However, phonetic similarity of words in di erent
languages can also be due to other reasons, which are illustrated in Table 5.1. In general, deciding whether two words are genetically related requires expert knowledge ofthe history of the languages in question.
Spanishsal
sueter
ambicionmuchocarpeta `folder'cuclillomamaEnglishsalt
sweater
ambitionmuchcarpetcuckoomommy

Classi cation
genetic cognates
direct borrowing
borrowing from a third language
chance similarity\false friends"
onomatopoeic words
nursery words

Table 5.1: Examples of similar words in Spanish and English.

66

Chapter 5.

Identification of cognates

67

The identi cation of cognates is a component of two principal tasks of historicallinguistics: establishing the relatedness of languages and reconstructing the histories
of language families. In the past, languages were often grouped in families on the basis of similarity of basic vocabulary. Nowadays, most linguists insist on corroborating
the claims of relatedness with a list of regular sound correspondences. Nevertheless,a recently developed approach of mass comparison [Greenberg, 1987] rejects correspondences in favour of similarity, and has produced several proposals of very remote
genetic relationship.
In computational linguistics, cognates have been employed for a number of bitextrelated tasks.
 sentence and word alignment in bitexts [Simard et al., 1992; Church, 1993;

McEnery and Oakes, 1996; Melamed, 1999],

 improving statistical machine translation models [Al-Onaizan et al., 1999],
 inducing translation lexicons [Koehn and Knight, 2001; Mann and Yarowsky,

2001],

 automatic construction of weighted string similarity measures [Tiedemann, 1999],
 extracting lexicographically interesting word-pairs from multilingual corpora[Brew and McKelvie, 1996].

Most of the above approaches take advantage of the property that almost all cooccurring cognates in bitexts are mutual translations. Note that in computational
linguistics, the term cognate usually denotes words in di erent languages that are
similar in form and meaning, without making a distinction between borrowed andgenetically related words. For example, English sprint and the Japanese loan supur-Chapter 5.

Identification of cognates

68

into are considered cognate for this purpose, even though these two languages areunrelated. This broad de nition is also adopted in this chapter.
The task addressed in this chapter can be formulated in two ways. On the wordlevel, given two words (lexemes) from di erent languages, the goal is to compute avalue that re ects the likelihood of the pair being cognate. I assume that each lexeme
is given in a phonetic notation, and that it is accompanied by one or more glosses
that specify its meaning in a metalanguage for which a lexical resource is available(for example, English). On the language level, given two vocabulary lists representing
two languages, the goal is to order all pairs of vocabulary entries according to theirlikelihood of cognation. Tables 5.2 and 5.3 show sample entries from two typicalvocabulary lists. Such vocabulary lists are sometimes the only data available forlesser-studied languages.
In the traditional approach to cognate identi cation, words with similar meanings
are placed side by side. Those pairs that exhibit some phonological similarity are
analyzed in order to nd systematic correspondences of sounds. The correspondencesin turn can be used to distinguish between genuine cognates and borrowings or chance
resemblances.
The approach adopted in this chapter is based on the intuition that, in spiteof the inevitable diachronic changes, cognates on average display higher semantic
and phonetic similarity than words that are unrelated. In the following sections, I
discuss various ways of measuring phonetic and semantic similarity, and then present
COGIT, a similarity-based cognate-identi cation system. COGIT combines ALINE,
the program described in Chapter 4, with a novel procedure for detecting semantic
relatedness from glosses that employs keyword selection and WordNet. Even though
the similarity-based approach does not di erentiate between cognates and borrowings,
the experiments on data from four native American languages show that it can beChapter 5.

Identification of cognatesaniskohocikan
asikankamamakos
kostacwin
misiyewnamehpinnapakihtaktehtew
wayakeskw

string of beads tied end to end
sock, stocking
butter y
terror, fearlarge partridge, hen, fowl
wild ginger
board
green toadbark

Table 5.2: An excerpt from a Cree vocabulary list [Hewson, 1999].

asikan
anaka'ekkw
kipaskosikankottacwinmemkwan'
misissenamepinnapakissakwtentedock, bridge
bark
medicine to induce clotting
fear, alarm
butter yturkeysuckerplankvery big toad

Table 5.3: An excerpt from an Ojibwa vocabulary list [Hewson, 1999].

69

Chapter 5.

Identification of cognates

70

successfully applied to the task of cognate identi cation.

5.1 Phonetic similarity
The approaches to measuring word similarity can be divided into two groups. The
orthographic approaches disregard the fact that alphabetic symbols express actual
sounds, employing a binary identity function on the level of character comparison. A
one-to-one encoding of symbols has no e ect on the results. The phonetic approaches,on the other hand, attempt to take advantage of the phonetic characteristics of individual sounds in order to estimate their similarity. This presupposes a transcriptionof the words into a phonetic or phonemic representation.
5.1.1 The orthographic approaches

Simard et al. [1992] consider two words to be cognate if they are at least four characters long and their rst four characters are identical. Naturally, such a crude approach
will fail to identify even very similar cognates, such as government and gouvernement.
On the other hand, the simple condition can be checked very quickly. This approach
can be generalized to yield a truncation coeÆcient in the [0; 1] range. One way of
doing this is to divide the length of the longest common pre x by the average of thelengths of the two words being compared. For example, the truncation coeÆcient ofEnglish colour and French couleur is 62:5 ' 0:31 because their longest common pre x
is \co-". The truncation coeÆcient can be computed in O(n) time.
Dice's similarity coeÆcient, originally developed for the comparison of biological specimens, was rst used to compare words by Adamson and Boreham [1974].
It is based on the notion of a bigram | an ordered pair of characters. Adamson
and Boreham chose bigrams rather than single characters expressly to preserve infor-

Chapter 5.

Identification of cognates71

mation about the sequence of the letters in a word. Dice's coeÆcient was adopted
for cognate identi cation by McEnery and Oakes [1996], who concluded that it performed better on the task than a measure based on a simple edit distance. Brew
and McKelvie [1996] proposed four other bigram-based methods. Dice's coeÆcientis determined by the ratio of the number of shared character bigrams to the total
number of bigrams in both words:
2jbigrams(x) \ bigrams(y)j ;DICE(x; y ) =jbigrams(x)j + jbigrams(y)jwhere bigrams(x) is a multi-set of character bigrams in x. For example, colour andcouleur share three bigrams (co, ou, and ur), so their Dice's coeÆcient is 116 ' 0:55.
Notice that the number of bigrams in a word is one less than its length measured incharacters. Dice's coeÆcient can be computed in O(n2) time.
Melamed [1999] detects orthographic cognates by thresholding the Longest Common Subsequence Ratio (LCSR). The LCSR of two words is computed by dividing
the length of their longest common subsequence (LCS) by the length of the longer
word:
jLCS(x; y)j :LCSR(x; y ) =max(jxj; jy j)

For example, LCSR(colour,couleur) = 57 ' 0:71, as their longest common subsequenceis \c-o-l-u-r". Brew and McKelvie [1996] propose a variation in which the denominatoris the average of both word lengths. Melamed explicitly chooses LCSR over DICEand truncation, but he does not provide any experimental results to support his
preference. A simple dynamic programming algorithm computes the LCSR in O(n2)time, and more complicated algorithms are even faster.
It is worth noting that LCSR is closely related to edit distance. If the cost ofa substitution is set at more than twice the cost of an indel, the calculation of an
optimal alignment of the two strings is equivalent to nding their longest common

Chapter 5.

Identification of cognates

72

subsequence [Kruskal, 1983, page 30], and the edit distance d can be expressed interms of LCS:d(x; y ) = jxj + jy j j2  LCS(x; y )j:
5.1.2 The phonetic approaches

The approaches of Kessler [1995] and Nerbonne and Heeringa [1997] to estimatingphonetic distance between dialects have already been discussed in Chapter 4. Kessler's
surprising nding was that a binary distance function based on the identity of phonetic
segments worked better than a feature-based measure. Nerbonne and Heeringa's
conclusion was the opposite. It has to be noted that in neither case was the evaluation
method totally objective: Kessler calculated the correlation with a distance measure
based on the number of isoglosses in a linguistic atlas, while Nerbonne and Heeringa
apparently visually compared their results with a dialect map. In any case, the taskof computing the distance between wordlists, albeit related, is clearly distinct fromthe task of identifying cognates in wordlists.
Oakes [2000], on the other hand, focuses directly on cognate identi cation. His
approach is very simple: two words are deemed to be cognate if their edit distance isbelow a certain threshold; the length of the words is irrelevant. The threshold wasestablished by the analysis of the distances between cognate and non-cognate pairs
in four Indonesian wordlists.
ALINE (described in Chapter 4) was originally developed for aligning phonetic
strings, but since it chooses the optimal alignment on the basis of a similarity score,no substantial modi cation is necessary for the current application. The similarity
score returned by ALINE can be normalized by dividing it by the length of the longer
word multiplied by the maximum possible similarity score between segments, so that

Chapter 5.

Identification of cognates73

it falls in the range [0; 1]. Intuitively, a complex algorithm such as ALINE should be
more accurate than simple, orthographic coeÆcients. By applying various methods
to a speci c task, such as cognate identi cation, their relative performance can beobjectively evaluated.

5.2 Semantic similarity
Since the meanings of the lexemes are given by their glosses, the simplest method
to detect semantic similarity is to check if the lexemes have at least one gloss incommon. For example, the cognates kottacwin `terror, fear' and kostacwin `fear,
alarm' in Tables 5.2 and 5.3 are correctly associated by this method. However, inmany cases, the similarity of semantically related glosses is not recognized by thismethod. The most common reasons are listed below with examples.
1. Spelling errors or variants: `vermilion' and `vermillion', `sweet grass' and `sweetgrass', `plow' and `plough';
2. Morphological di erences: `ash' and `ashes';
3. Determiners: `a mark' and `mark', `my nger' and ` nger', ` sh' and `kind ofsh';
4. Adjectival modi ers: `small stone' and `stone';
5. Nominal modi ers: `goose' and `snow goose';
6. Complements and adjuncts: `stone' and `stone of peach', `island' and `island ina river';
7. Synonymy: `grave' and `tomb';Chapter 5.

Identification of cognates74

8. Small semantic changes: `fowl' and `turkey';
9. Radical semantic changes: `broth' and `grease'.
Spelling errors, which may be especially frequent in data that have been acquired
through optical character recognition, are easy to detect but have to be correctedmanually. Morphological di erences (category 2) can be removed by lemmatization.
Many of the cases belonging to categories 3 and 4 can be handled by adopting a stoplist of determiners, possessive pronouns, and very common modi ers such as certain,
kind of, his, big, female, etc.
Categories 4, 5, and 6 illustrate a common phenomenon of minor semantic shiftsthat can be detected without resorting to a lexical resource. All that is needed isthe determination of the heads of the phrases, or, more generally, keywords. Pairs ofglosses that contain matching keywords are usually semantically related.
For the remaining categories, string matching is of no assistance, and some lexical
resource is called for.
5.2.1 WordNet

WordNet [Fellbaum, 1998] is a publicly available lexical knowledge base for English
developed at Princeton University. Lexical entries are organized into comprehensive
networks of synonym sets (synsets). Words that have more than one meaning (polysemous words) may participate in several di erent synsets. The synsets are linked
by various lexical relations. The noun database is the most developed part of thesemantic network. The main types of lexical links between noun synsets are shown in
Table 5.4. The hypernymy/hyponymy links form the hierarchy of nouns. They linkeach synset to its immediately more general and more speci c synsets. A chain ofChapter 5.

Identification of cognates

75

Type
Name
ExampleInverse of
hypernymy
bird ! animal
hyponymy
hyponymy
bird ! robin
hypernymy
meronymy
beak ! bird
holonymyholonymy
tree ! branchmeronymy
antonymy
leader $ follower itself
Table 5.4: The main lexical relations between nouns in WordNet.
is-asubsumes
part-ofhas-acomplement-of

hypernymy links can be traversed from each synset to one of the 11 abstract concepts
that are at the top of the hierarchy.
The coverage of WordNet is impressive. In version 1.6, the noun network alone ismade of over 60; 000 synsets, which contain over 100; 000 noun senses, and the numberof lexical links exceeds 150; 000. Nonetheless, the coverage of the English vocabulary
is inevitably only partial.
The idea of using WordNet for the detection of semantic relationships comes from
Lowe and Mazaudon [1994, footnote 13, page 406]. WordNet is well-suited not only
for detecting synonyms but also for associating lexemes that have undergone small
semantic changes. Trask [1996] lists several types of semantic change, including thefollowing: generalization (broadening): `partridge' ! `bird';
 specialization (narrowing): `berry' ! `raspberry'; melioration (developing a more favourable sense): `woman' ! `queen'; pejoration (developing a less favourable sense): `farm-worker' ! `villain'; metaphor (extending the literal meaning): `steersman' ! `governor';Chapter 5.

76

Identification of cognates metonymy (using an attribute of an entity to denote the entity itself): `crown'! `king'; synechdoche (using a part to denote a whole, or vice-versa): `hand' ! `sailor'.

Certain types of semantic change have direct parallels among WordNet's lexical
relations. Generalization can be seen as moving up the hierarchy along a hypernymy link, while specialization is moving in the opposite direction, along a hyponymy
link. Synecdoche can be interpreted as a movement along a meronymy/holonymy link.
However, other types of semantic change, such as metonymy, melioration/pejoration,and metaphor, have no direct analogues in WordNet.
The use of WordNet for semantic similarity detection is possible only if English
is the glossing metalanguage. If the available vocabularies are glossed in other languages, one possible solution is to translate the glosses into English, which, however,may increase their ambiguity. A better solution could be to use a multilingual lexical resource, such as EuroWordNet [Vossen, 1998], which is modeled on the originalPrinceton WordNet. In general, WordNet could be replaced by any machine-readable
dictionary or thesaurus, or even word-frequency data extracted from a corpus.
is-a

5.3 Implementation
COGIT, the cognate identi cation system, is schematically depicted in Figure 5.1.
The system is composed of a set of Perl scripts for preprocessing the vocabulary lists,and phonetic and semantic modules written in C++. Given two vocabulary lists representing distinct languages, COGIT produces a list of vocabulary-entry pairs, sorted
according to the estimated likelihood of cognation. In order to take full advantage of
WordNet's noun hierarchies, the vocabulary lists are restricted to contain only nouns.

Chapter 5.

77

Identification of cognates

1. For each gloss in vocabularies L1 and L2 :(a) Remove stop words.
(b) Select keywords.
(c) Perform lemmatization.
(d) Generate lists of semantically related words.
2. For each pair of entries ((li; gi); (lj ; gj )) 2 (L1  L2 ):(a) Compute the phonetic similarity score Simphon (li; lj ).
(b) Compute the semantic similarity score Simsem (gi; gj ).
(c) Simoverall (i; j ) (1 ) Simphon (li; lj ) +  Simsem (gi; gj ).
(d) If Simoverall (i; j )  T , record i, j , and Simoverall (i; j ).
3. Sort the pairs in descending order of Simoverall .
Table 5.5: Cognate identi cation algorithm.

Vocabulary
list L1

Vocabulary
list L2

COGIT
Preprocessing

ALINE

Phonetic
moduleSemantic
moduleBrill tagger
QueryData
WordNetList ofcognatesFigure 5.1: The structure of cognate identi cation system.

Chapter 5.

78

Identification of cognates

The algorithm is presented informally in Table 5.5. Each vocabulary entry consistsof a lexeme l and its gloss g. The overall similarity score is a linear combination of
the similarity scores returned by the phonetic and semantic modules. The parameterre ects the relative importance of the semantic vs. phonetic score.
The preprocessing of the vocabulary data is performed by a suite of Perl scripts.
Checking and correcting the spelling of glosses is assumed to have been done beforehand. Table 5.6 shows the complete list of stop words and phrases that are removed
from glosses in order to facilitate the matching of nearly-identical expressions. Glosses
that exceed 30 characters are truncated, and all comments enclosed in brackets aredeleted. The lemmatization process is carried out by the QueryData module, which
is described below. The phonetic similarity score can be computed either by ALINEor through one of the orthographic methods described in section 5.1.1.
The keyword selection is performed according to a simple heuristic with the aidof a part-of-speech tagger [Brill, 1995]. Since the tagger operates on sentences rather
than on phrases, all glosses are initially prepended with the string `It is a'. The string
is removed after the tagging process is completed. Since the lexemes are restricted tonouns, only words with the tag are considered as possible keywords, except whena gloss contains a single word, in which case the word is taken to be the keyword
regardless of the tag. The gloss is scanned from left to right, and all nouns aremarked as keywords unless a wh-word or a preposition other than `of' is encountered.
Table 5.7 contains examples of keyword selection in action. Keywords are undernn

a
his
big
kind ofanherlittlemanner of

the
very
male
piece ofmylarge
femaleyoursmall
certain

Table 5.6: The stop-list of words that are removed from glosses.

Chapter 5.

79

Identification of cognates` stringNN forIN stretchingVBG hideNN '` uprightJJ ornamentNN wornVBN onIN headNN '` yellowJJ featherNN withIN blackJJ tipNN '` sorcererNN whoWP hasVBZ a serpentNN '` clotNN ofIN bloodNN '` intNN , detonatingVBG capNN onIN cartridgeNN '` snowNN dartNN , iceNN throwingVBG stickVB '` signNN whichWDT pointsNNS the wayNN '` a portageNN , settingVBG ashoreRB '` little storyNN thatWDT isVBZ sometimesRB toldVBN '` mysteriousJJ , hauntedVBN personNN orCC placeNN 'Table 5.7: Examples of automatically tagged glosses with keywords marked.
lined. Words are accompanied by the assigned part-of-speech tags: prepositions aretagged as `IN', while wh-words have tags that start with `W'. Stop-words are shownin a distinct font. It is evident from the handful of examples that the keyword scheme
is far from perfect. Because of the limited accuracy of the part-of-speech tagger, somewords are mistagged to begin with (e.g. `stick'). A comma separating two adjectives,
as in `mysterious, haunted' is indistinguishable from a comma separating two alternative glosses, so `mysterious' is erroneously assumed to be an independent gloss.
Nevertheless, the heuristic seems to pick most of the relevant nouns with reasonableprecision.
For the calculation of a WordNet-based semantic similarity score, I initially used
the length of the shortest path between synsets, measured in the number of links.
One can imagine utilizing a more sophisticated measure of semantic similarity, such as
is-aChapter 5.

Identification of cognates

80

Leacock and Chodorow's [1998] normalized path length, Resnik's [1999] informationbased approach, Lin's [1998] universal similarity measure, or other methods describedin Budanitsky [1999]. However, I found the e ect of considering paths longer than one
link to be negligible. Moreover, the process of determining the link distances between
all possible pairs of glosses, separately for each pair, was too time-consuming.
The solution eventually adopted is to compute the semantic score by a fastermethod that employs QueryData, a Perl interface to the WordNet module [Rennie,
1999]. A list of synonyms, hypernyms, and meronyms is generated for each gloss
and keyword in the preprocessing phase. During the execution of the core C++
program, regular string matching is performed directly on the listed senses. Words are
considered to be related if there is a relationship link between any of their senses. The
semantic score is determined according to a 9-point scale of semantic similarity, whichis shown in Table 5.8. The levels of similarity are considered in order, starting withgloss identity. The scores are not cumulative. For example, if the program detectsthat a keyword in one gloss is a hypernym of a keyword in another gloss (\keyword
hypernymy"), the check for a meronymy relation between the entire glosses (\gloss
meronymy") is not performed. The exact values corresponding to each level were
established by trial and error using the development set.
Let us follow the entire process of computing the similarity between vocabulary
entries on an example involving Cree wahkwa `a lump of roe' and Ojibwa wakk ` sheggs'. After the preprocessing removes the determiner a from the rst gloss, the glosses
are tagged and four nouns are identi ed as keywords in the respective glosses: lump,roe, sh, eggs. The lemmatization removes the plural ending -s from eggs. Neitherof the complete glosses exists in WordNet, but each of the keywords is represented
by several senses. The WordNet sense lists for the keywords are shown in Table 5.9.
COGIT detects two semantic relations: roe is a kind of egg, and roe is a part ofChapter 5.

81

Identification of cognates

Rank
1
2
3
4
5
6
7
8
9

Similarity levelgloss identity
gloss synonymy
keyword identity
gloss hypernymy
keyword synonymy
keyword hypernymy
gloss meronymy
keyword meronymy
none detected

Score
1.00
0.70
0.50
0.50
0.35
0.25
0.10
0.05
0.00

Table 5.8: Semantic similarity levels.
sh. Since keyword hypernymy has a higher precedence than keyword meronymy, theresulting semantic score is 0:25. The combination with the phonetic score of 0:4167
between wahkwa and wakk with set to 0:2 produces an overall similarity coeÆcientof 0:3834.

5.4 Evaluation
The test data suitable for the evaluation of the approach outlined above has to ful llseveral requirements. It should be suÆciently large to contain most of the surviving
cognates. The lexemes should be given in a consistent notation that allows for an
automatic transcription into phonetic form. In order to take advantage of WordNet,
the glosses must be given in English. Finally, the cognation information has to beprovided in the electronic form as well, so that the performance of the program canbe measured objectively. The last condition is perhaps the most diÆcult to satisfy.
Even in the rare cases when machine-readable bilingual lexicons can be acquired,the cognation judgements would have to be laboriously extracted from etymologicalChapter 5.

Identification of cognates

82

Word Synonyms
Hyponyms
Meronyms
lump ball, clod, glob, clump, agglomeration, piece,
chunk, swelling, klutz, part, symptom, clumsypuÆness, lout, clod,
persongoon, stumblebum, oaf,
lubber, lummox, gawk,
hunk
roe hard roe
spawn, egg, seafoodshsh chump, fool, gull, mark, foodstu , food product, pisces, school,
patsy, fall guy, sucker, victim, card game,shoal
shlemiel, soft touch,cards, dupe, aquaticmug, go shvertebrate
egg testis, gonad, testicle,
endocrine gland,male genitalia,ball, ballock, bollock, ductless gland, ovum, family jewels
nut
egg cell, foodstu , foodproduct
Table 5.9: Lists of semantically related words generated from WordNet.
dictionaries. Note that optical scanning of phonetic symbols or unusual diacritics ispractically impossible.
In that situation, it was truly muni cent of John Hewson to provide me with his
Algonquian data.
5.4.1 The Algonquian data

The machine-readable Algonquian data consists of two parts that complement eachother: the etymological dictionary, and the vocabulary lists from which the dictionary
was produced. The dictionary is available in book form [Hewson, 1993]. The computerles that I obtained from John Hewson contain both the dictionary and the raw lists.
The dictionary contains 4,068 cognate sets, including 853 marked as nouns. Twotypical cognate sets are shown in Table 5.10. Each set is composed of a reconstructed
proto-form and the corresponding cognates. The rst line contains the reconstructed
lexeme, a two letter code indicating its grammatical category, the English gloss, theChapter 5.

83

Identification of cognates*kenwe:cye:waCkinose:w
F
keno:ce:waM
kenu:si:w
O
kino:ce:*kenwehkwetamwa
CkinohkotamOkino:kkota:nNA pikefish
pikepickerelpike (kind of fish)
TI cut long(*-ehkwet)
he cuts it long
cut long(er)

1027

1028

Table 5.10: An excerpt from the Algonquian dictionary.
major morpheme of the lexeme (optional), and the lexeme number. The subsequentlines describe the surviving cognates. Each line includes a one-letter language code,
the cognate lexeme, and its English gloss. Nearly all cognates belong to one of thefour principal Algonquian languages (Fox, Menomini, Cree, Ojibwa).
The dictionary le is almost identical with the book version, and required only
minimal clean-up. The lexemes are already in a phonemic transcription, so no sophisticated grapheme-to-phoneme conversion was necessary. A simple coding is used toexpress phonemes that lack ASCII equivalents: c for [s], 3 for [E], etc. In the experiments described in this section, the dictionary le served as a source of the cognation
information (\gold standard").
In contrast with the dictionary, the vocabulary lists can be characterized as noisy
data. They contain many errors, inconsistencies, duplicates, and lacunae. The Fox
le is incomplete. In the Menomini le, three di erent phonemes ([c], [E], and [P])had been merged into one, and had to be painstakingly reconstructed on the basisof phonotactic constraints. As much as possible, the entries were cross-checked withthe dictionary itself, which is much more consistent. Table 5.11 speci es the numberof unique lexemes available for each language. It appears that only about a third of
the nouns present in the vocabulary lists had made it into the dictionary.

Chapter 5.

Language
Fox
Menomini
Cree
OjibwaTotal

84

Identification of cognates

Dictionary only
All words Nouns
1252
193
2231
361
2541
512
2758
535
8782

1601

Dictionary and lists
All words Nouns
4759
575
8550
1540
7507
1628
6334
1023
27150

4766

Table 5.11: The size of the vocabulary lists.
5.4.2 Properties of the data

Table 5.12 shows, for each language combination, the number of cognate noun pairs
extracted from the dictionary, and the total number of possible pairings of lexemes,
which was calculated by multiplying the number of entries in the respective vocabularies. To take the Menomini{Ojibwa pair as an example, the task of the system wasto identify 259 cognate-pairs from 1540  1023 possible lexeme-pairs. On average,
the ratio of non-cognate to cognate pairs was about 6500, which gives an idea of thediÆculty of the task of identifying cognate pairs.
The values in Tables 5.13 and 5.14 con rm that both the phonetic and the semantic
similarity between Algonquian cognates (C) is greater than between randomly selected
lexemes (R). The average weighted phonetic similarity between cognates can be seen
as a measure of the relative \closeness" of a pair of languages. According to allmeasures, Cree{Ojibwa is the most closely related pair, Fox is somewhat removed
from the two, and Menomini is even more distant.
Figure 5.2 compares proportions of all cognate pairs in the data that are coveredby individual semantic similarity levels. Over 60% of cognates have at least one

Chapter 5.

Identification of cognates

85

Languages
Cognates Word pairs
Fox
Menomini
121885,500
Fox
Cree
130
936,100
Fox
Ojibwa136
588,225
Menomini Cree
239
2,507,120
Menomini Ojibwa
259
1,575,420
CreeOjibwa408
1,665,444
Table 5.12: The number of shared cognates and the number of possible word pairs
for each language combination (nouns only).

Languages

Trunc.
DICE
LCSR
ALINE
R C
R C
R C
R C
Fox
Menomini .013 .247 .058 .343 .229 .570 .220 .607
Fox
Cree.012 .290 .067 .466 .248 .633 .223 .616
Fox
Ojibwa.013 .323 .060 .501 .236 .651 .212 .626
Menomini Cree.012 .266 .055 .316 .227 .599 .219 .620
Menomini Ojibwa.012 .216 .046 .277 .212 .551 .206 .590
Cree
Ojibwa.013 .359 .083 .618 .255 .768 .224 .699
Table 5.13: Average phonetic similarity values computed by various methods for
randomly selected word pairs and for cognate pairs.

Chapter 5.

Identification of cognates

86

Languages
Random Cognates
Fox
Menomini
.003
.753
Fox
Cree
.002
.719
Fox
Ojibwa.002.710
Menomini Cree
.003
.698
Menomini Ojibwa
.003
.718
Cree
Ojibwa.002.681
Table 5.14: Average semantic similarity values for randomly selected word pairs andfor cognate pairs.
gloss in common. The cases in which the existence of a WordNet relation in uences
the value of the similarity score account for less than 10% of the cognate pairs. In
particular, instances of meronymy between cognates are very rare.
5.4.3 Performance of COGIT

The Cree{Ojibwa language pair was chosen as the development set. These two languages are represented by the most complete vocabularies and share the largest number of cognates. However, they also turned out to be the most closely related among
the four Algonquian languages, according to all measures of phonetic similarity (Table 5.13). It is quite possible that the overall performance of the system would havebeen better if a di erent language pair had been chosen as the development set.
The values of all parameters, including , ALINE's parameters, and the semantic
similarity scale given in Table 5.8, were established during the development phase of
the system, using only the Cree{Ojibwa data. The optimal value of was found tobe near 0:2. Similarly, ALINE's parameters were set as follows: Cskip = {1, Csub =10, Cexp = 15, and Cvwl = 1. The salience settings were as given in Chapter 4, except

Chapter 5.

87

Identification of cognates

100
100000000000000000000000000000000
11111111111111111111111111111111
0
100000000000000000000000000000000
11111111111111111111111111111111
0
100000000000000000000000000000000
11111111111111111111111111111111.627
0
100000000000000000000000000000000
11111111111111111111111111111111
0
100000000000000000000000000000000
11111111111111111111111111111111
01
0
1
0 .0201
GLOSS SYNONYMY
0
1
0
1
0
1
0000001111110
10000001111110
1000000111111.120
KEYWORD IDENTITY
010000001111110
1000000111111
0
1
00
11
0
1
00
11
0
1
00
11
.024
GLOSS HYPONYMY
0
1
00
11
0
1
00
11
0
1
0
1
0
1
KEYWORD SYNONYMY
0 .012
1
0
1
0
1
0
1
KEYWORD HYPONYMY
01
0 .019
1
0
1
0
1
0
1
0
GLOSS MERONYMY 1
0.003
1
0
1
0
1
0.000
1
KEYWORD MERONYMY 1
0
0
1
0
1
0000000000
1111111111
0
10000000000
1111111111
0
10000000000
1111111111
NONE
.193
0
1
0000000000
1111111111
011111111111
0000000000
01
01111111111111111111111111111111111111
000000000000000000000000000000000000
1
0
1 1
0
0
1 1
0
0
0
1
0
1
0
1
0
1
GLOSS IDENTITY

0

10

20

30

40

50

60

70

Coverage

Figure 5.2: Coverage of the similarity levels.
that the salience of feature Long was set to 5. The semantic similarity scores wereapproximated by inducing a decision tree on the data and interpolating the phonetic
similarity thresholds for each level.
The 11-point interpolated average precision was adopted to measure the e ectiveness of the various cognate identi cation methods. The output of the system is alist of suspected cognate pairs sorted by their similarity scores. Typically, true cognates are very frequent near the top of the list, and become less frequent towards thebottom. The threshold value that determines the cut-o depends on the intended
application, the degree of relatedness between languages, and the particular method
used. Rather than reporting precision and recall values for an arbitrarily selected
threshold, precision is computed for the recall levels of 0%, 10%, 20%, ..., 100%,and then averaged to yield a single number. In the experiments reported below, I
uniformly assumed the precision value at 0% recall to be 1, and the precision value
at 100% recall to be 0.

Chapter 5.

88

Identification of cognates

Languages
Fox
Menomini
Fox
Cree
Fox
OjibwaMenomini Cree
Menomini Ojibwa

Trunc.
.122
.196
.235
.122
.108

DICE
.113
.215
.277
.129
.121

LCSR
.163
.303
.382
.245
.202

ALINE
.383
.424
.508
.389
.375

Average on test set

.157

.171

.259

.416

Cree

.239

.430

.592

.619

OjibwaTable 5.15: Average precision for various phonetic methods.
Table 5.15 compares the average precision achieved by various methods on the six
language pairs. The results on the development set (Cree{Ojibwa) are separated fromthe results on the test set (the remaining ve pairs). ALINE outperforms all orthographic coeÆcients, including LCSR. The dominance of ALINE is more pronounced
for more remote pairs, such as Fox{Menomini. Dice's coeÆcient performs poorly asa cognate identi cation method, being only slightly better than a naive truncation
method.
Table 5.16 and 5.17 show the results when semantic information is combined withLCSR and ALINE, respectively. Methods G, K, and W represent increasingly sophisticated semantic similarity detection: Method G considers gloss identity only,
Method K adds keyword-matching, and Method W employs also WordNet relations.
All methods that use the semantic information provided by the glosses perform substantially better than the purely phonetic methods. Impressive results are reachedeven when only gloss identity is considered. Adding keyword-matching and WordNet
relations brings additional, albeit modest, improvements. Again, ALINE does better

Chapter 5.

89

Identification of cognates

Languages
Menomini
Cree
OjibwaCree
Ojibwa

None
.383
.424
.508
.389
.375

Semantic method
G
K
.579
.616
.631
.636
.633
.655
.548
.562
.554
.588

W
.630
.655
.660
.569
.598

Average on test set

.416

.589

.611

.622

Cree

.619

.739

.750

.762

Fox
Fox
Fox
Menomini
Menomini

OjibwaTable 5.16: Average precision for ALINE combined with various semantic methods.
than LCSR.
Figure 5.3 shows a more detailed comparison of the e ectiveness of various methods on test sets, in the form of precision{recall curves. The gure allows one todetermine an approximate precision level for a broad range of recall levels, and viceversa. For example, Method W is able to identify almost 75% of all cognate pairs
if we are willing to accept a one-to-one ratio of true to false positives (50% precision). The curve for Method K, which would be slightly below the curve for Method
W, is omitted for clarity. The staircase-shaped curve labeled \Semantic" illustrates
the performance of a purely semantic method, in which only the similarity of glosses
is considered. Each step corresponds to a semantic similarity level. For example,
selecting all cases of gloss identity yields .627 recall at .237 precision.
Figure 5.4 illustrates the e ect of varying the setting of the parameter on the average precision of COGIT when Method W is used. Recall that the value of re ects
the relative importance of the semantic vs. phonetic similarity. The average precisionChapter 5.

90

Identification of cognates

Languages
Menomini
Cree
OjibwaCree
Ojibwa

None
.163
.303
.382
.245
.202

Semantic method
G
K
.460
.494
.569
.564
.596
.615
.479
.494
.414
.473

W
.498
.583
.624
.504
.479

Average on test set

.259

.504

.528

.538

Cree

.592

.727

.743

.749

Fox
Fox
Fox
Menomini
Menomini

OjibwaTable 5.17: Average precision for LCSR combined with various semantic methods.
1"Truncation""DICE""LCSR""ALINE""Method G""Method W""Semantic"

0.9
0.8

Interpolated precision

0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0

0.1

0.2

0.3

0.4

0.5
Recall

0.6

0.7

0.8

0.9

1

Figure 5.3: Precision-recall curves for various methods.

Chapter 5.

91

Identification of cognates

0.65
Method W

3-point interpolated average precision

0.6

0.55

0.5

0.45

0.4
0

0.1

0.2

0.3

0.4

0.5
alpha

0.6

0.7

0.8

0.9

1

Figure 5.4: Interpolated 3-point average precision of Method W on test sets as afunction of the parameter .
for = 0 is :416, which represents the performance of ALINE (cf. Table 5.15). The
optimal value of for both the development and the test sets is close to 0.2. Intuitively, more weight has to be given to the phonetic score because phonetic similarity
between cognates is more reliably detected than their semantic relationship. With
approaching 1, the performance levels o at :511, as precedence is increasingly given
to the semantic score, which divides all pairs into nine classes corresponding to thescale of Table 5.8. When is set to 1, Method W reduces to the pure \Semantic"
approach of Figure 5.3: because the phonetic score is no longer available to ordercandidate pairs within semantic classes, the average precision plummets to :161.

Chapter 5.

Identification of cognates

92

5.5 Discussion
5.5.1 The role of WordNet

The contribution of WordNet to the overall performance of the system is relatively
small. This is due both to the properties of the test data and to WordNet's shortcomings. Since the data for all Algonquian languages originates from a single project, it
is quite homogeneous. As a result, many glosses match perfectly within cognate sets,
which limits the need for application of WordNet lexical relations.
Another problem is that even after preprocessing that includes checking the spelling, lemmatization, and stop word removal, many of the glosses are not in a form
that can be recognized by WordNet. Some rare words, such as `spawner', `windigo',`cradleboard', `smartweed', and `spot sh', are simply not in WordNet. Compoundwords that are recorded in WordNet as two words, such as `sweet grass' or `powder
horn' are not identi ed if written as a single word.
When many words have several meanings that participate in di erent synsets,
the senses detected to be related are not necessarily the senses used in the glosses.
For example, star and lead share a synset (`an actor who plays a principal role'),but in the Algonquian vocabularies both words are always used in their most literal
sense. Only in the case of complete identity of glosses can the lexemes be assumed
to be synonymous in all senses. On the other hand, words that are semanticallyvery similar, such as puppy and dog, are often far from each other in the WordNet
hierarchy.
Apart from synonymy, two other semantic relations play a role. By following
the meronymy (is-a part-of) links, COGIT successfully associated such concepts asmattress/bed, our/bread, and bowstring/bow. However, it also linked gun (a pedal

Chapter 5.

Identification of cognates

93

that controls the throttle valve) with airplane, and ear in `ear of corn' with head in`ox, head of cattle'. Examples of concepts correctly associated by the hypernymy(is-a-kind-of) links include gooseberry/currant, kindness/goodness, sea/body of water,
but snare/drum is o target (one of the senses of snare is `a small drum with two heads
and a snare stretched across the lower head').
In the majority of cases, the semantic associations made by WordNet are plausible: acorn is a part of oak, mud is a kind of soil, and spittle is the same thing assaliva. Unfortunately, most of such pairs are not cognates. The detection of semantic
similarity can help, but the main burden of cognate identi cation has to be carriedby the phonetic module.
5.5.2 False positives

The performance gures are adversely a ected by the presence of the usual \noise",which is unavoidable in the case of authentic data. Manual preparation of the vocabulary lists would undoubtedly result in better performance. Nevertheless, I decided
against correcting individual entries or cognation judgements. One reason was thata comprehensive clean-up of the data of such a size would not only be extremely
tedious and time-consuming, but would also require advanced expertise in the eld ofAlgonquian linguistics. Moreover, I felt that a noisy data set provides a more trustworthy test for a cognate identi cation program designed to help solve real linguistic
problems. Only limited automatic validation of the data had been performed: theentries marked as doubtful were omitted; in the case of multiple entries of the same
lexeme, a unique entry was selected, with the preference given to the entries includedin the published dictionary.
It is not always easy to decide whether two similar entries are duplicates or le-Chapter 5.

Identification of cognates

94

gitimate variants. For example, Hewson's dictionary distinguishes three distinct cognate sets that correspond to the following reconstructed Proto-Algonquian etyma:*menehsyi, *menehs-, and *mene'tekwi. The three proto-forms, which are uniformly
glossed as `island', have seven extant re exes in four languages, COGIT cannot be
faulted for identifying all 34 resulting cross-language combinations as probable cognates, but only ve of those are counted as correct guesses because the remaining
ones span di erent cognate sets.
In the case of *mahkahkwi `box', there is just one cognate set containing words
from each of the four Algonquian languages, including Fox mahkahkwi. However,the Fox vocabulary lists contain another similar entry, mahkahkohi `little box, pail',which did not make it into the dictionary, perhaps because it is a diminutive variantof the other word. Clearly, mahkahkohi is cognate with other re exes of *mahkahkwi.
Nevertheless, since it is not listed in the dictionary, it produces a false positive inevery experiment that involves Fox. It would be quite diÆcult to track down all such
entries in the data as neither their lexemes nor their glosses match perfectly.
The performance gures are lower also because of the usual imperfections of thegold standard. In many cases, examination of apparent false positives leads to thediscovery of true cognates that are not identi ed as such in Hewson's dictionary. Tables 5.18 and 5.19 contains examples of such word pairs. Apart from their strong
similarity of form and meaning, they exhibit many of the regular sound correspondences identi ed by Bloom eld [1946]. Although the ultimate judgement belongs to
the Algonquian scholars, it is almost certain that all those pairs are genuine cognates.
The examples in Tables 5.18 and 5.19 are by no means an exhaustive list of all
new cognate pairs that could be obtained from the analysis of COGIT's output,
but rather an illustrative sample. The second column from the left contains thenumbers of the corresponding cognate sets in Hewson's dictionary, if applicable. The

Chapter 5.

Identification of cognates

Similarity score
Set Lang. Lexeme
Glossphon sem overallpsakanapiy `rope, rawhide thong' 0.62 0.00 0.50
1 | CreeOjib. pssakaniyap `string'kaskipitakan `tobacco pouch'
2 | Cree0.88 0.50 0.81
Ojib. kaskipitakan `pouch'skwan`grate for wood'
3 3087 Cree
0.83 0.00 0.67
Ojib. skwan`grindstone'psimohkan `watch, clock'4 | Cree0.72 1.00 0.77
Ojib. pssimokkan `clock'pminikan `twist tobacco'
5 2897 Cree
0.91 0.00 0.73
Ojib. pminikan `auger, screw'
amiskomin `yellow blackberry'
6 1731 Cree
0.82 0.00 0.66
Ojib. miskomin `raspberry'switakan`salt'
7 3114 Cree
0.75 1.00 0.80
Ojib. swittakan `salt'watow`clot of blood'
8 3570 Cree
0.68 0.50 0.64
Fox atowa`blood-clot'
pipon`winter'
9 2665 Cree
0.77 1.00 0.82
Men. pepon`year, winter'switakan`salt'
10 3114 Cree
0.74 1.00 0.79
Men. sewehtakan `salt'kahkakiw`raven'
11 0843 Cree
0.73 1.00 0.79
Men. kakakew`raven'tohtosapoy `milk'
12 | Cree
0.65 1.00 0.72
Men. totohsapoh `milk'
misisahk`horse y'
13 1874 Cree
0.64 1.00 0.71
Men. mesasah `horse y'emihkwan `spoon'
14 0605 Cree
0.62 1.00 0.70
Men. Emeskwan `ladle, spoon'
kisisowin`bodily heat, fever' 0.62 1.00 0.70
15 1112 Cree
Men. kesswan `fever'Creeominis`raisin'
16 | Men. s
0.62 1.00 0.70somen`raisin, grape'mimikwas `butter y'
17 | Cree
0.62 1.00 0.69
Men. mmkwEw `butter y'mosapew`unmarried man'18 | Cree
Men. mosapEwew `bachelor, single man' 0.66 0.70 0.67mkatiweni ` ght'
19 1948 Fox
0.66 0.70 0.67
Men. mkatwan `war, ghting'
Table 5.18: Examples of cognate pairs not included in Hewson's dictionary.

95Chapter 5.

Identification of cognates

96

Similarity score
Set Lang. Lexeme
Glossphon sem overall
pehkwikanakani `ankle'
20 2704 Fox
0.65 1.00 0.72
Men. nepEhkikanakon `ankle'mciweni`food'
21 | Fox
0.58 1.00 0.67
Men. mcehswan`food'
paskesikani`gun'
22 2502 Fox
Men. phkesekan`gun cap, dynamite' 0.64 0.50 0.61
apahkwayikani `reed lodge'
23 | Fox
0.63 0.50 0.60
Men. apahkiwikan `reed house'nahakanihkwewa `daughter in law'
24 2103 Fox
Men. nohahkaniahkiw `daughter-in-law' 0.62 0.50 0.60
kehtikani` eld, farm'
25 1078 Fox
0.66 1.00 0.73
Ojib. kittikan` eld, garden'
manetowa`spirit'26 1570 Fox
Ojib. manitons`worm, insect, spirit' 0.64 1.00 0.71
nakamoni`song'
27 2255 Fox
0.63 1.00 0.71
Ojib. nakamowin`song'
kahkesewi`charcoal'
28 | Fox
0.49 1.00 0.60
Ojib. kekkise`charcoal'kehcpisoni`belt'
29 | Fox
0.50 1.00 0.60
Ojib. kiccippisowin `belt'
atamina`maize-plant'
30 1590 Fox
0.66 0.35 0.60
Ojib. mantamin`grain of corn'atesohkakana`sacred story'
31 0129 Fox
0.60 0.50 0.58
Ojib. atissokkan`story or legend'
pepakeweyan`shirt'32 | Men.
0.74 1.00 0.79
Ojib. papakiwiyan`shirt'wawan`egg'
33 3513 Men.
0.70 1.00 0.76
Ojib. wawanw`egg'somenapoh`wine'
34 | Men.
0.64 1.00 0.72
Ojib. somenapo`wine'suskkahekan` at iron'
35 | Men.
0.64 1.00 0.71
Ojib. soskweka'ikan ` at iron, iron'kohtakan`throat'
36 1371 Men.
0.62 1.00 0.69
Ojib. kuntakan`throat'pkipocekan`plow'
37 2725 Men.
0.69 0.70 0.69
Ojib. pimipocikan `plough'pEsekokasiw`horse'38 | Men.
0.61 1.00 0.69
Ojib. pesikokas`horse'Table 5.19: Examples of cognate pairs not included in Hewson's dictionary (cont.).

Chapter 5.

Identification of cognates

97

phonetic, semantic and overall similarity scores are given in the rightmost columns.
Some glosses have been truncated to preserve the space.
A successful detection of semantic similarity is usually due to some kind of surface
similarity. The majority of pairs in Tables 5.18 and 5.19 have the maximum semantic
similarity score of 1:00, thanks to the identity of at least one gloss. The score of 0:5,
which also comes up with some frequency, identi es the cases where the keywords
match even though the entire glosses do not. In pair 24, `daughter' is identi ed asa keyword after the marking script splits `daughter-in-law' into three words. Pair 23
is an example where marking only the head noun as keyword would not work. One
could consider splitting the glosses containing the `or' conjunction, such as the one in
Pair 31, into two glosses; it is diÆcult however to handle cases like `making or supplyof moccasins'.
The cases where WordNet has made the di erence are fewer. In pair 2, `pouch' isactually a hypernym of `tobacco pouch', but keyword identity gets the same score as
gloss hypernymy. Pair 18 illustrates the precedence of gloss synonymy (`unmarriedman' ' `bachelor') over keyword identity (`man'). In pair 37, WordNet comes to therescue after string matching fails to associate two spelling variants. A real ash ofarti cial intelligence occurs in pair 30, where the semantic similarity of `maize-plant'and `grain of corn' is detected.
The similarity of pairs 1 and 6 was recognized by the early versions of COGIT,
which computed the link distance between concepts. Both `rope'/`string' and `blackberry'/`raspberry' are coordinate terms, that is, words that have the same hypernym.
Such a close relationship is still possible to detect using the current approach: inaddition to comparing a gloss with the hypernymy list of the opposite gloss, the program would have to compare both hypernymy lists with each other. However, thereal problem is that by increasing the radius of the semantic radar the program lets

Chapter 5.

Identification of cognates

98

in an avalanche of false positives (cf. Table 5.9 on page 82). My experiments indicate
that, at least until better lexical resources become available, limiting the range ofcomparisons to the most immediate WordNet neighbours may be the wisest strategy.

5.6 Conclusion
The results show that it is possible to identify a large portion of cognates in related
languages solely on the basis of phonetic and semantic similarity. Phonetic similarity is a more reliable indication of cognation than semantic similarity. ALINE,a phonetically-based program, outperforms the simple orthographic methods on the
cognate identi cation task. Analysis of semantic information extracted from glosses
yields a dramatic increase in the number of identi ed cognates. Most of the gain
comes from detecting entries that have matching glosses, but the use of a lexical
resource can further enhance the contribution of the semantic module.
A system such as COGIT can serve as one of the principal modules of a language
reconstruction system. On its own, it could be of assistance to comparative linguists
dealing with large vocabulary data from languages with which they are unfamiliar.
Beyond diachronic phonology, the techniques and ndings presented here may also be
applicable to tasks such as bitext alignment or automatic construction of translation
lexicons.

Chapter 6
Determination of correspondences
The main objection that can be raised against the algorithm for cognate identi cation
described in the previous chapter is that the phonetic alignment and the phonetic similarity score depend solely on absolute phonetic similarity. Most linguists believe thatrecurrent sound correspondences (henceforth referred to simply as correspondences)provide a more reliable evidence of cognation. For example, the English verb have is
not cognate with Latin habere `to have', as implied by the phonetic and semantic similarity, but rather with capire `to catch'. This follows from the well-known Grimm's
Law, which speci es that English [h] regularly corresponds to Latin [k]. Other known
correspondences between English and Latin, such as t:d, T:t, n:n, are demonstrated by
the word pairs in Table 6.1. The corresponding phonemes shown in boldface originate
from a single proto-phoneme. Thus, correspondences make it possible to distinguishcognates from loan words and chance resemblances. Could correspondences take theplace of phonetic similarity as the basis for the identi cation of cognates?
The correspondences also provide decisive evidence for the relatedness of languages. However, because manual determination of correspondences is an extremely
time-consuming process, it has yet to be accomplished for many proposed language99

Chapter 6.

English
tEn
 t
nEst
n E f j uf o mT r 
sIt
hOrn

100

Determination of correspondences

Latin
deke
ed
nid
nepot
spum
tre
sed
korn

`ten'
`eat'
`nest'`nephew'`foam'`three'`sit'`horn'Englisht u
t u T
n 
fut
wulf
r u t
hart

Latin
duo
dent
gen
ped
lup
radik
kord
br@D@r fratr`two'`tooth'`knee'`foot'`wolf'`root'`heart'`brother'

Table 6.1: Examples of English{Latin cognates exhibiting correspondences.
families. A system able to perform this task automatically from unprocessed bilingual
wordlists could be of great assistance to comparative linguists. The Reconstruction
Engine of Lowe and Mazaudon [1994], a set of programs designed to be an aid inlanguage reconstruction, as well as other approaches reviewed in Section 3.2, requirea set of correspondences to be provided beforehand.
Although it may not be immediately apparent, there is a strong similarity between
the task of matching phonetic segments in a pair of cognate words, and the task ofmatching words in two sentences that are mutual translations (Figure 6.1). The
consistency with which a word in one language is translated into a word in anotherlanguage is mirrored by the consistency of sound correspondences. The former is dueto the semantic relation of synonymy, while the latter follows from the principle of
the regularity of sound change. Thus, as already asserted by Guy [1994], it should bepossible to use similar techniques for both tasks.
The primary objective of the method proposed in this chapter is the automatic
determination of correspondences in bilingual wordlists, such as the one in Table 6.1.
The method exploits the idea of relating correspondences in bilingual wordlists toChapter 6.

Determination of correspondences

Snow

lies

on

the

Nix

iacet

in

terra

w

u

l

l

u

p

101

groundf

Figure 6.1: The similarity of word alignment in bitexts and phoneme alignment between cognates.
translational equivalence associations in bitexts through the employment of models
developed in the context of statistical machine translation. The second task addressedin this chapter is the identi cation of cognates on the basis of the discovered correspondences. The experiments to be described in Section 6.5 show that the method iscapable of determining correspondences in bilingual wordlists in which less than 30%
of pairs are cognates, and outperforms comparable algorithms on cognate identi cation. Although the experiments focus on bilingual wordlists, the approach presented
in this chapter could potentially be applied to other bitext-related tasks.

6.1 Related work
In a schematic description of the comparative method, the two steps that precede
the determination of correspondences are the identi cation of cognate pairs and theirphonetic alignment. Indeed, if a comprehensive set of correctly aligned cognate pairs
is available, the correspondences could be extracted by simply following the alignment
links. Unfortunately, in order to make reliable judgements of cognation, it is necessaryChapter 6.

Determination of correspondences102

to know in advance what the correspondences are. Historical linguists solve thisapparent circularity by guessing a small number of likely cognates and re ning theset of correspondences and cognates in an iterative fashion.
Guy [1994] outlines a correspondence-based algorithm for identifying cognates inbilingual wordlists. It is discussed here rather than in Chapter 5 because it makes
no use of the notion of phonetic similarity. Since the method requires a set of wordpairs large enough to support a statistical analysis, it cannot be applied to an isolated
word pair.
The algorithm estimates the probability of phoneme correspondences by employing a variant of the 2 statistic on a contingency table, which indicates how often two
phonemes co-occur in words of the same meaning. The goal of the algorithm is not todetermine correspondences per se, but rather to use them to estimate the likelihoodof cognation of word pairs. For every word pair, it nds an alignment that maximizes
the sum of the correspondence probabilities, and then converts the alignment score
into an estimate of cognation.
Guy's paper is not a model of clarity or rigour: the algorithm is de ned by example, the theoretical grounding is shaky, and there is no quantitative evaluation on
authentic language data. However, the program COGNATE, which implements thealgorithm, is publicly available and can be put to a test. An experimental evaluationof COGNATE is described in Section 6.5.
Oakes [2000] adopts a much simpler approach to discovering correspondences.
Sound changes are deemed to be regular if they are found to occur more than oncein the aligned cognates. In contrast with Guy's method, Oakes does not compute
any co-occurrence statistics, but relies solely on the phonetic similarity of words. The
discovered correspondences are not used for separating cognates from non-cognates.
Section 6.5 contains an evaluation of one of his programs (JAKARTA) on the cognate

Chapter 6.

Determination of correspondences

103

identi cation task.
Because the tasks of determination of correspondence and the identi cation of
cognates are intertwined, some of the bitext-related algorithms implicitly determineand employ correspondences. Tiedemann [1999] considers automatic constructionof weighted string similarity measures from bitexts. He includes three lists of themost frequent character \mappings" between Swedish and English, which correspondto his three mapping approaches (single characters, vowel and consonant sequences,and non-matching parts of two strings). However, because genetic cognates in thedata seem to be outnumbered by borrowings, the lists contain few genuine correspondences. Mann and Yarowsky [2001] take advantage of language relatedness inorder to automatically induce translation lexicons. In their search for cognates, they
discover most probable character \substitutions" across languages. In the provided
French{Portuguese examples, phonologically plausible correspondences b:v, t:d mix
with mere orthographic regularities c:q, x:s.
Knight and Graehl [1998] in their paper on back-transliteration from the Japanesesyllabic script katakana to the English orthography consider the sub-task of aligning
the English and Japanese phonetic strings. They apply the estimation-maximization(EM) algorithm to generate symbol-mapping probabilities from 8,000 pairs of unaligned English/Japanese sound sequences. It is possible to view the sound pairs
with the highest probabilities as the strongest recurrent correspondences between the
two languages. Naturally, the existence of those correspondences is an artifact of thetransliteration process, rather than a consequence of a genetic language relationship.
Nevertheless, it may be possible to employ a similar approach to discover recurrent
sound correspondences in genuine cognates. A drawback of the alignment model presented in the paper is an asymmetric, one-to-many mapping between the English andJapanese sounds, and a restricted set of edit operations that excludes both insertions

Chapter 6.

Determination of correspondences104

and deletions. These restrictions are designed to make the models less expensive tocompute.

6.2 Statistical machine translation
Statistical machine translation was proposed by the IBM group [Brown et al., 1990a]
as the method of building translation systems automatically from large bitexts byapplying the noisy channel model. The idea is to combine a language model, whichassigns a probability to every sentence in the target language, with a translation
model, which assigns a probability to all pairings of the source language sentences withthe target language sentences. The third main component of a statistical machinetranslation system, the decoder, actually nds the actual target language sentencethat maximizes the product of the probabilities assigned by the language model andthe translation model.
A translation model approximates the probability that two sentences are mutualtranslations by computing the product of the probabilities that each word in thetarget sentence is a translation of some source language word. A model of translationequivalence that determines the word translation probabilities can be induced frombitexts. The diÆculty lies in the fact that the mapping of words in bitexts is notknown in advance. The sentences and the words within the sentences have to be rst
aligned by some method. While the sentence order is by and large identical in bothparts of a bitext, the word order in not. The following section discuses the problem
of word alignment in bitexts in more detail.

Chapter 6.

Determination of correspondences

105

6.2.1 The word-to-word model of translational equivalence

Algorithms for word alignment in bitexts aim at discovering word pairs that are mutual translations. Since words that are mutual translations tend to co-occur more
frequently than other word pairs, a straightforward approach is to estimate the likelihood of translational equivalence by computing a similarity function based on aco-occurrence statistic, such as mutual information, Dice's coeÆcient, or the 2 test.
The underlying assumption is that the association scores for di erent word pairs are
independent of each other.
Melamed [2000] shows that the assumption of independence leads to invalid word
associations, and proposes an algorithm for inducing models of translational equivalence that outperform the models that are based solely on co-occurrence counts. His
models employ the so-called one-to-one assumption, which formalizes the observation that most words in bitexts are translated to a single word in the corresponding
sentence. The algorithm, which is related to the expectation-maximization (EM) algorithm, iteratively re-estimates the likelihood scores which represent the probability
that two word types are mutual translations.
I present here a summary of Melamed's algorithm, followed by a more detailed
description of its parts. In the rst step, the likelihood scores are initialized using
only the co-occurrence information. Next, the likelihood scores are used to induce a
set of one-to-one links between word tokens in the bitext. The links are determinedby a greedy competitive linking algorithm, which proceeds to link pairs that have thehighest likelihood scores. After the linking is completed, the link counts are used tore-estimate the likelihood scores, which in turn are applied to nd a new set of links.
The process is repeated until the translation model converges to the desired degree.
For the initialization of the likelihood scores, Melamed employs the G2 statis-

Chapter 6.

106

Determination of correspondencestic [Dunning, 1993]. The G2 statistic provides, on the basis of a contingency table,
an estimate of how unlikely it is that two tokens co-occur by chance. Let cooc(u; v)
be the number of co-occurrences of u and v, Furthermore,
k1 = cooc(u; v );n1 = cooc(; v ) =Xs

k2 = cooc(u; :v ) =cooc(s; v );k
p1 = 1 ;n1Then, the G2 statistic is de ned as:
G2 (u; v ) =
 

X
t6=v

cooc(u; t)n2 = cooc(; :v ) =

XX

k +k
p= 1 2
n1 + n2kp2 = 2 ;n2

s t6=v

2 log BB(k(k1 j jnn1; ;pp1 ))BB ((kk2 jj nn2;; pp2))
1

1

2

2

cooc(s; t)where B (k j n; p) = nk pk (1 p)n k denotes the probability of k being generated froma binomial distribution with parameters n and p. The pairs in which one word token
is NULL are initialized to an in nitesimal value.
The greedy competitive linking algorithm is used to induce a set of links in the
bitext. First, all likelihood scores are sorted in decreasing order. The pair (u; v) withthe highest score is selected and all co-occurring word pairs (u; v) in the bitext arelinked. For the pairs of the form (u; NULL), all u word tokens are linked to NULL.
Then, the process is repeated for the pair with the next highest score. Each word canbe linked at most once.
Melamed presents three translation-model estimation methods. Method A reestimates the likelihood scores as the logarithm of the probability of jointly generating
the pair of words u and v:
links (u; v )score A (u; v ) = log P
0 0
u0 ;v0 links (u ; v )where links(u; v) denotes the number of links induced between u and v. Note thatthe co-occurrence counts of u and v are not used for the re-estimation.

Chapter 6.

Determination of correspondences

107

In Method B, an explicit noise model with auxiliary parameters + and  is constructed in order to improve the estimation of likelihood scores. + is the probability
that a link is induced between two co-occurring words that are mutual translations,while  is the probability that a link is induced between two co-occurring words thatare not mutual translations. Ideally, + should be close to 1 and  should be close to
0. The actual values of the two parameters are calculated by the standard method of
maximum likelihood estimation. The probability of the link frequency distributions
P r(links j model ) =Yu;v

P r(links (u; v ) j cooc(u; v ); +;  )expressed as a function of + and  has only one dominant global maximum, which
can be established by hill-climbing. The score function is de ned as:
B (links (u; v ) j cooc(u; v ); +):score B (u; v ) = log
B (links (u; v ) j cooc(u; v );  )In Method C, bitext tokens are divided into classes, such as content words, function
words, punctuation, etc., with the aim of producing more accurate translation models.
The auxiliary parameters are estimated separately for each class. The score function
is de ned as:
B (links (u; v ) j cooc(u; v ); +Z ):score C (u; v j Z = class(u; v )) = log
B (links (u; v ) j cooc(u; v ); Z )The evaluation was performed on a 16; 000-word French{English bitext. The
three translation-model estimation methods were compared to Model 1 of Brown
et al. [1990b], which is based exclusively on co-occurrence counts. In all experiments,
Methods B and C achieved signi cantly higher accuracy than Model 1 and Method A.
When all links were considered, Method A outperformed Model 1, and Method C
outperformed Method B. However, when closed-class links were ignored, Model 1 wasbetter than Method A, and the performance of Methods B and C was roughly thesame.

Chapter 6.

Determination of correspondences

108

6.2.2 Noncompositional compounds

As a way of relaxing the one-to-one restriction, Melamed [1997] proposes an elegant
algorithm discovering noncompositional compounds (NCCs) in bitexts. An NCC isa word sequence, such as \high school", whose meaning cannot be synthesized fromthe meaning of its components. Since many NCCs are not translated word-for-word,
their detection is essential in most NLP applications.
Melamed's information-theoretic approach is based on the observation that treating NCCs as a single unit rather than as a sequence of independent words increases thepredictive power of statistical translation models. Therefore, it is possible to establish
whether a particular word sequence should be considered a NCC by comparing two
translation models that di er only in their treatment of that word sequence. For theobjective function that measures the predictive power of a translation model P r(s; t),
Melamed selects mutual information:XX
P r(s; t)
I (S ; T ) =P r(s; t) log
P r(s)P r(t)s2S t2T
Melamed's approach to identi cation of NCCs is to induce a trial translation modelthat involves a candidate NCC and compare the model's total mutual information
with that of a base translation model. The NCC is considered valid only if there isan increase of the mutual information in the trial model. The contribution of s to
I (S ; T ) is given as:X
P r(s; t)i(s) = P r(s; t) log:
P r(s)P r(t)t2T

In order to make this procedure more eÆcient, Melamed proposes inducing the translation model for many candidate NCCs at the same time.
A complex gain-estimation method is used to guess whether a candidate NCC isuseful before inducing a translation model that involves this NCC. Each candidate

Chapter 6.

Determination of correspondences

109

NCC xy causes the net change xy in the objective function, which can be expressedas:xy = i0(x) + i0(y) + i0 (xy) i(x) i(y);where i and i0 are predictive value functions for source words in the base translation
model and in the trial translation model, respectively. i0(x) is estimated on theassumption that the links involving x will not change in the trial translation model
unless y occurs to the right of x:
i0 (x) = i(x : RC 6= y );where (x : RC 6= y) denotes the set of tokens of x whose right context is y. Similarly,
i0 (y ) = i(y : LC 6= x);where LC denotes word context to the left. Finally, i'(xy) is estimated as follows:
i0 (xy ) = i(x : RC = y ) + i(y : LC = x):

Given parallel texts E and F , the algorithm iteratively augments the list of NCCs.
The iteration starts by inducing a base translation model between E and F . All continuous bigrams which are estimated to increase mutual information of the translation
model are placed on a sorted list of candidate NCCs, but for each word token, only themost promising NCC is allowed to remain on the list. Next, a trial translation modelis induced between E 0 and F , where E 0 is obtained from E by fusing each candidate
NCC into a single token. If the net change in mutual information gain contributedby a candidate NCC is greater than zero, all occurrences of that NCC in E are permanently fused; otherwise the candidate NCC is placed on a stop-list. The entire
iteration is repeated until reaching an application-dependent stopping condition.
The method was evaluated on a large English{French bitext containing transcripts
of Canadian parliamentary debates (Hansards). In one experiment, after six iterations

Chapter 6.

Determination of correspondences

110

the algorithm identi ed on both sides of the bitext about four hundred NCCs that
increased the mutual information of the model. Another experiment, which is particularly relevant for the application discussed in this chapter, showed that the method
was capable of discovering meaningful NCCs in a data set consisting of spellings andpronunciations of English words (for example, \ng" was determined to be a NCC ofEnglish spelling because it consistently \translates" into the sound /N/). Nevertheless, the author admits that the full NCC recognition algorithm was not tested in any
real application.

6.3 Models of phoneme correspondence
Thanks to its generality, Melamed's parameter estimation process can be adapted tothe problem of determining correspondences. Moreover, his models are symmetric,
which makes them more suitable for this task than the related IBM models [Brown etal., 1990a]. The main idea is to induce a model of sound correspondence in a bilingual
wordlist, in the same way as one induces a model of translational equivalence amongwords in a parallel corpus. After the model has converged, phoneme pairs with thehighest likelihood scores represent the most likely correspondences.
The most important modi cation of the original algorithm concerns the methodof aligning the segments in two corresponding strings. In sentence translation, thelinks frequently cross and it is not unusual for two words in di erent parts of sentences to correspond. On the other hand, the processes that lead to link intersection in diachronic phonology, such as metathesis, are sporadic. By imposing the
no-crossing-links constraint on alignments, a dramatic reduction of the search spaceis achieved, and the approximate competitive linking algorithm of Melamed can be
replaced with a variant of the well-known dynamic programming algorithm of Wagner

Chapter 6.

Determination of correspondences

111

and Fisher [1974].
Null links in statistical machine translation are induced for words on one side of
the bitext that have no clear counterparts on the other side of the bitext. Melamed'salgorithm explicitly calculates the likelihood scores of null links for every word typeoccurring in a bitext. In diachronic phonology, phonological processes that cause
insertion or deletion of segments usually operate on individual words rather thanacross the language. Therefore, I model insertion and deletion by employing an indel
penalty for unlinked segments.
The alignment score is computed by summing the number of induced links, andapplying a small constant penalty for each unlinked segment, with the exception of
the segments beyond the rightmost link (the so-called half-local alignment describedin Section 4.4.3). The exception re ects the relative instability of word endings in
the course of linguistic evolution. Metathesis is not considered. In order to avoid
inducing links that are unlikely to represent recurrent sound correspondences, only
pairs whose likelihood scores exceed a set threshold are linked. All correspondences
above the threshold are considered to be equally valid. In the cases where more than
one best alignment is found, each link is assigned a weight that is its average over theentire set of best alignments (for example, a link present in only one of two competingalignments receives the weight of 0:5).
The NCC algorithm is adapted with one major change. After inducing a trial
translation model between E 0 and F , the original algorithm accepts all candidate
NCCs that contribute a positive net change in mutual information gain. For thedetection of phoneme NCCs, I decided to accept all candidate NCCs that result ina correspondence that has a likelihood score above the minimum-strength thresholdt described in the following section. I found that the strength of an induced correspondence better re ects the importance of a phoneme cluster than the mutualChapter 6.

Determination of correspondences112

information gain criterion.

6.4 Implementation
The method described above has been implemented as a C++ program, named
CORDI, which takes as input a bilingual wordlist and produces an ordered list ofcorrespondences. A model for a 200-pair list usually converges after 3{5 iterations,which takes only a few seconds on a Sparc workstation. The user can choose between methods A, B, and C, described in Section 6.2, and an additional Method D.
In Method C, phonemes are divided into two classes: non-syllabic (consonants andglides), and syllabic (vowels); links between phonemes belonging to di erent classes
are not induced. Method D di ers from Method C in that the syllabic phonemes do
not participate in any links.
Adjustable parameters include the indel penalty ratio d and the minimum-strength
correspondence threshold t. The parameter d xes the ratio between the negative indel
weight and the positive weight assigned to every induced link. A lower ratio causes the
program to be more adventurous in positing sparse links. The parameter t controls
the tradeo between reliability and the number of links. In Method A, the value oft is the minimum number of links that have to be induced for the correspondence
to be valid. In methods B, C, and D, the value of t implies a score threshold of+t  log  , which is a score achieved by a pair of phonemes that have t links out of t
co-occurrences. In all experiments described below, d was set to 0:15, and t was set
to 1 (suÆcient to reject all non-recurring correspondences). In Method D, where thelack of vowel links causes the linking constraints to be weaker, a higher value of t = 3
was used.
The NCC approach is activated by specifying a -nN option, where N is the maxi-

Chapter 6.

Determination of correspondences

113

mum number of iterations of the algorithm. The algorithm may terminate sooner if
two subsequent iterations fail to produce any candidate NCCs.

6.5 Evaluation
This section describes four experiments aimed at assessing CORDI's accuracy.
6.5.1 The data for experiments

The raw vocabulary lists and the dictionary of Proto-Algonquian described in Section 5.4.1 constitute a valuable test data set also in this chapter. The Algonquiancorrespondences are not included in the set, but they are relatively well documented
in [Bloom eld, 1925; 1946]. Because of the large number of complex 1:2 and 2:2
correspondences, the Algonquian languages are ideal for testing the NCC approach.
The Comparative Indo-European Data Corpus is an important lexical resourcethat is freely available on the World Wide Web. The corpus contains the Swadesh
200 lists for over 80 Indo-European languages and dialects, together with almost complete cognation judgements. It was compiled in the 1960s by the renowned historicallinguist Isidore Dyen of Yale University, and played an important part in lexicostatistical research [Dyen et al., 1992]. The data was originally represented on punchedcards by 26 ASCII letters, with diacritical marks handwritten on the cards. Unfortunately, as the diacritical marks have not yet been transferred to electronic form, thewords are unsuitable for automatic phonetic analysis.
Kessler [2001] includes in his book the Swadesh 200 lists for Albanian, English,
French, German, Latin, Hawaiian, Navajo, and Turkish. The rst ve languages
belong to the Indo-European family and share a number of cognates. The lists areavailable in the XML format from the author's web page. The data is of high quality.

Chapter 6.

Determination of correspondences

114

Four variants of each etymon are provided: the root and the stem are given in aphonetic transcription, and the full word is speci ed both in the phonetic and in theorthographic form. The cognation judgements are speci ed either as incontrovertibleor as doubtful. Succinct notes provide bibliographical references as well as otherinformation.
In order to go beyond the Swadesh list of basic concepts, I extracted from thelinguistic literature a set of 112 established English{Latin cognate pairs. English
words were transcribed into phonetic notation with the aid of the publicly available
Carnegie Mellon Pronouncing Dictionary, version 0.6. A straightforward Perl script
was suÆcient to map letters to sounds in Latin words. The entire set is listed inAppendix E.
6.5.2 Determination of correspondences in cognate pairs

In order to test CORDI's ability to determine correspondences in clean cognate data,
Method D was applied to the set of 112 English{Latin cognate pairs given in Appendix E. The correspondences with scores above the threshold of t = 3 are shownin Table 6.2. The perfect agreement between the number of links and the number ofco-occurrences is striking, but not implausible, considering that the input set includes
many \textbook" examples of cognates, which are usually selected to illustrate theregularity of correspondences. CORDI correctly identi es the most salient segmentsthat have been preserved from Proto-Indo-European, and partially re-discovers thevenerable Grimm's Law, a set of sound changes that occurred in prehistoric times inProto-Germanic. As a result of discovering the t:d and T:t correspondences, the program correctly aligns the troublesome tooth:dente pair, which was beyond the powerof a phonetic aligner (Section 4.8.1). The erroneous y:w correspondence is caused byChapter 6.

Determination of correspondences

115

cooc
links
score
valid
r:r
28
28 193.1 yes
n:n
23
23 158.6 yes
l:l20
20 138.0 yes
s:s17
17 117.3 yes
m:m15
15 103.5 yes
f:p
13
13
89.7 yesy
t:d11
11
75.9 yesy
k:g88
55.1 yesy
y:w
6
6
41.4 nob:f
6
6
41.4 yesy
h:k5
5
34.5 yesy
T:t4
4
27.6 yesy
Table 6.2: English{Latin correspondences discovered by Method D in pure cognate
data. The correspondences marked with a y are predicted by Grimm's Law.

the practice of transcribing the English diphthong [aI] as a vowel-consonant pair ay.
For comparison, Table 6.3 contains the correspondences identi ed by Oakes's program JAKARTA program in the same data. Only the correspondences identi ed
more than three times are shown. JAKARTA is clearly less e ective in linking therelated segments. For example, only 12 out of 20 co-occurrences of /l/ are detected,
whereas CORDI classi es all 20 co-occurrences as correspondences. A quick perusalof the relevant cognates con rms that this is indeed the case. It is not surprising,
therefore, that overall CORDI discovers more correspondences than JAKARTA.
6.5.3 Determination of correspondences in word pairs

The assumption that a set of identi ed cognates is already available as the input forthe program is not very plausible. The very existence of a reliable set of cognate pairs
implies that the languages in question have already been thoroughly analyzed andthat the sound correspondences are known. A more realistic input requirement is alist of word pairs from two languages where that the corresponding words have theChapter 6.

Determination of correspondences

116

RSC cooc count valid
r:r
28
21
yes
n:n
23
17
yes
s:s
17
17
yes
m:m
15
14
yes
l:l
20
12
yes
f:p
13
11
yes
t:t
8
8
yes
b:f
6
5
yes
k:g
8
4
yes
y:k
6
4
no
Table 6.3: Correspondences discovered by JAKARTA in pure cognate data.
same, well-de ned meaning (such as the bilingual wordlist in Table 2.3 on page 11).
Determining correspondences in a list of synonyms is clearly a more challenging task
than extracting them from a list of reliable cognates because the non-cognate pairs
introduce noise into the data. Note that Melamed's original algorithm is designed tooperate on aligned sentences that are mutual translations.
In order to test CORDI's ability to determine correspondences in noisy data,
Method D was applied to Kessler's English{Latin 200-word list. Only 29% of wordpairs are actually cognate; the remaining 71% of the pairs are unrelated lexemes.
The top ten correspondences discovered by the program are shown in Table 6.4.
Remarkably, all but one are valid.
For comparison, the top ten phoneme matchings picked up by the 2 statistic are
shown in Table 6.5. Only four of them are valid correspondences. freq 1 and freq 2
refer to the frequencies of the pertinent phonemes in the English and Latin data,
respectively. Macrons denote double consonants, which are transcribed as single
segments in Kessler's data. One of the weaknesses of the 2 statistic is illustrated by
the fact that four of the pairs in Table 6.5 have high 2 values in spite of a single
co-occurrence in the data. It is tempting to try to correct this bias by establishingChapter 6.

Determination of correspondences

117

cooc
links
score
valid
r:r
26
24
158.7
yes
n:n
24
23
154.2
yes
t:d
18
18
122.4
yes
k:k
12
11
72.5
yes
s:s
11
10
65.7
yes
f:p
9
9
61.2
yes
m:m
10
9
58.9
yes
d:t
10
8
49.8
no
l:l
14
9
49.7
yes
h:k
7
7
47.6
yes
Table 6.4: English{Latin correspondences discovered by CORDI in noisy synonym
data.
freq 1
freq 2
cooc
2
valid
T:s
10
1
1 22.3 noT:r
10
1
1 22.3 non:n
4360
24 14.4 yes
m:m
20
30
10 12.9 yes
f:p
24
24
9 11.6 yes
t:d
49
37
18 11.6 yes
l:f
37
15
9 10.8 no
D:
n
10
2
1
9.0 noN:g
6
213
8.7 nov:y6
3
1
8.4 noTable 6.5: English{Latin correspondences discovered using the 2 statistic.

a threshold for the number of co-occurrences. Guy's [1994] program COGNATE
contains a number of such ad hoc corrections. The following section includes anassessment of the program's e ectiveness.
6.5.4 Identi cation of cognates in word pairs

The quality of correspondences produced by CORDI is diÆcult to validate, quantify, and compare with alternative approaches. However, it is possible to evaluate
the correspondences indirectly by using them to identify cognates. The likelihood

Chapter 6.

Determination of correspondences118

of cognation of a pair of words increases with the number of correspondences thatthey contain. Since CORDI explicitly posits correspondence links between words, thelikelihood of cognation can be estimated by simply dividing the number of induced
links by the length of the words that are being compared. A minimum-length parameter can be set in order to avoid computing cognation estimates for very short words,
which tend to be unreliable. However, in order to provide a fair comparison with theprograms that do not impose any length constraints on words, the minimum-lengthparameter was not used in the experiments described here.
ri word paircognate? i pi
1 /hArt/:/kord/ yes
1 1.002 /hAt/:/kalid/ no
3 /sno/:/niw/ yes
2 0.66
Table 6.6: An example ranking of cognate pairs.
The evaluation method for cognate identi cation algorithms adopted in this section is to apply them to a bilingual wordlist and order the pairs according to theirscores (refer to Table 6.6). The ranking is then evaluated against a gold standard
by computing the n-point average precision, where n is the total number of cognate
pairs in the list. The n-point average precision is obtained by taking the average ofn precision values.
Pnp
P = i=1 inThe partial precision values pi are calculated for each point in the list where we nda cognate pair by the following formula:
pi =

i
ri

where i is the number of the cognate pair counting from the top of the list producedby the algorithm, and ri is the rank of this cognate pair among all word pairs. The

Chapter 6.

Determination of correspondences

119

n-point precision of the ranking in Table 6.6 (1:0+0:66)=2 = 0:83. A perfect orderingof all cognate pairs before all non-cognate pairs achieves P = 1:0. The expectedn-point precision of a program that randomly orders word pairs is close to c, where cis the proportion of cognate pairs in the list.
The n-point precision can further be normalized as:  = P1 cc . Such a normalization allows to compare accuracy without the need to take into account the densityof cognates in the input word list. The maximum value of  is of course 1:0. The
expected value of  for a random ordering turns out to be independent of c, andapproaches zero as the number of pairs N increases:
(N ) = (HN1)=(N 1)

where Hn is the n-th harmonic number. (200) is approximately :0245.
The development set consisted of three Swadesh 200 list pairs adapted from theComparative Indo-European Data Corpus. The Polish{Russian, Spanish{Rumanian,and Italian{Serbo-Croatian were selected because they represent three di erent levels of relatedness, and also because they have relatively transparent grapheme-tophoneme conversion rules. They were transcribed into a phonetic notation by meansof Perl scripts and then stemmed and corrected manually. The ambiguities caused by
the imperfect transcription were corrected with the help of dictionaries and/or native
speakers of the languages in question.
Table 6.7 compares the average precision achieved by methods A, B, C, and D
on the development set. The cognation judgements from the Comparative IndoEuropean Data Corpus served as the gold standard. The `Cognates' column contains
the ratio of the number of cognate pairs to the length of the list. Naturally, thesmaller the ratio, the harder the task becomes.
In order to objectively compare the methods proposed in this paper with otherChapter 6.

120

Determination of correspondences

Languages

Proportion
Methodof cognates A B C D
PolishRussian.735.989 .994 .994 .986
Rumanian Spanish.585.898 .948 .948 .875
Italian
Serbo-Croatian.253.499 .455 .527 .615
Table 6.7: Average cognate identi cation precision on the development set for various
methods.
cognate identi cation programs, ve 200 Swadesh lists compiled by Kessler [2001]
were adopted as the test set. As the lists contain rich phonetic and morphologicalinformation, the stemmed forms were automatically converted from the XML format
with virtually no extra processing. The word pairs classi ed as doubtful cognates
were assumed to be unrelated.
The lists represent ve Indo-European languages: English, German, French, Latin,
and Albanian. Apart from the English{German and the French{Latin pairs, all remaining language pairs are quite challenging for a cognate identi cation program. In
many cases, the gold-standard cognate judgments distill the ndings of decades of
linguistic research. In fact, for some of those pairs, Kessler nds it diÆcult to showby statistical techniques that the surface regularities are unlikely to be due to chance.
Nevertheless, in order to avoid making subjective choices,
was evaluated on
all possible language pairs in Kessler's set.
Two programs mentioned in Section 6.1, COGNATE and JAKARTA, were also
applied to the test set. COGNATE is available as an MS-DOS executable on theWorld Wide Web. A special Perl script was written to transcribe the phonetic input
data into the required one-letter-per-phoneme format. Unfortunately, the program's
highly interactive nature (Table 6.8) makes it diÆcult to analyze the results of procordi

Chapter 6.

f
I
S

p
82
41
0

i
33
70
63

Determination of correspondences

s
55
38
0

k
59
62
49

121

i
33
70
63

fIS/piski (word pair #49, pass #1)
I am 28% sure that they are NOT related.
I allowed only for matches >= 50.
The best I found were: fI S
piski
N(ext), P(revious), J(ump), M(inimum match), O(ther pass), Q(uit) ?

Table 6.8: A sample screen from Guy's program COGNATE.
cessing entire wordlists. The problem is aggravated by the fact that the MS-DOS
operating system is no longer in common use. For each word pair, the output had
to be manually captured and pasted into a le, which was subsequently processed byanother dedicated Perl script. The script ordered the word pairs according to the decreasing con dence scores, with the ties broken randomly. It took several thousandsof mouse clicks to arrive at the average precision gures for the ten test wordlists.
The source code of JAKARTA was obtained directly from the author. Since in its
original form it only recognizes 26 phonemes, the program was amended according
to the author's instructions in order to make it recognize additional phonemes. As
in the case of COGNATE, special scripts handled the input data conversion andthe calculation of the average precision. Word pairs were ordered according to theincreasing edit distances, with random breaking of ties. Because of the adopted
evaluation method, JAKARTA's edit distance threshold of 4 for separating cognatesfrom non-cognates was ignored.

Chapter 6.

Determination of correspondences

122

The results on the test set are shown in Table 6.9. The best result for each language pair is underlined. The performance of COGNATE and JAKARTA is quite
similar, even though they represent two radically di erent approaches to cognate identi cation. On average, methods B, C, and D outperform both comparison programs.
On closely related languages, Method B, with its relatively unconstrained linking,achieves the highest precision. Method D, which considers only consonants, is thebest on fairly remote languages, where vowel correspondences tend to be weak. The
only exception is the extremely diÆcult Albanian{English pair, where the relative
ordering of methods seems to be accidental. As expected, Method A is outperformedby methods that employ an explicit noise model. However, in spite of its extra complexity, Method C is not consistently better than Method B, perhaps because of its
inability to detect important vowel-consonant correspondences, such as the ones between French nasal vowels and Latin /n/. The results of Table 6.9 are normalized as
 in Table 6.10.
6.5.5 Determination of complex correspondences

In all the experiments described so far, the correspondences were assumed to consistof single phonemes. In order to test the suitability of the NCC approach, a separate
experiment was performed on a subset of the Algonquian data. As in Section 6.5.3,
the goal was to determine correspondences from noisy wordlists. In this experiment, it
was possible to rigorously evaluate the resulting list of correspondences by comparing
it to the set of correspondences determined by Bloom eld [1925; 1946].
The input data was automatically extracted from the raw vocabulary lists byselecting all pairs of noun lexemes that had at least one gloss in common. The end
result of such an operation is bilingual wordlists containing both cognate and non-Chapter 6.

123

Determination of correspondences

Languages

Proportion COGNATE JAKARTA
Methodof cognates
A B C D
English German .590
.878
.888 .936 .957 .952 .950
French Latin
.560
.867
.787 .843 .914 .838 .866
English Latin
.290
.590
.447 .584 .641 .749 .853
German Latin
.290
.532
.518 .617 .723 .736 .857
English French
.275
.324
.411 .482 .528 .545 .559
French German .245
.390
.406 .347 .502 .487 .528
Albanian Latin
.195
.449
.455 .403 .432 .568 .606
Albanian French
.165
.306
.432 .249 .292 .319 .437
Albanian German .125
.277
.248 .156 .177 .154 .312
Albanian English
.100
.225
.227 .302 .373 .319 .196
Average

.283

.484

.482

.492 .554 .567 .616

Table 6.9: Average cognate identi cation precision on the test set for various methods.
Languages

Proportion COGNATE JAKARTA
Methodof cognates
A B C D
English German .590
.702
.726 .844 .894 .882 .877
French Latin
.560
.697
.517 .643 .804 .633 .695
English Latin
.290
.423
.221 .415 .494 .646 .794
German Latin
.290
.341
.321 .461 .610 .628 .799
English French
.275
.067
.188 .285 .349 .372 .392
French German .245
.192
.213 .136 .340 .320 .375
Albanian Latin
.195
.315
.322 .258 .294 .463 .511
Albanian French
.165
.169
.320 .101 .153 .185 .325
Albanian German .125
.174
.141 .035 .059 .033 .214
Albanian English
.100
.139
.141 .225 .304 .244 .107
Average

.283

.322

.311

.340 .430 .441 .509

Table 6.10: Average cognate identi cation precision normalized as .

Chapter 6.

Determination of correspondences

124

cognate pairs. This method of producing bilingual wordlists is not only faster thanthe manual compilation, but also has the potential of incorporating cognates that areoutside the basic set of 200 concepts.
The Cree{Ojibwa list served as the development set, and the Fox{Menomini list
as the test set. Again, the latter turned out to be more challenging than the former.
The Cree{Ojibwa contained 732 pairs, including 242 (33.1%) cognate pairs. The Fox{
Menomini list contained 397 word pairs, including only 79 (19.9%) cognate pairs. Thisis less than the number given in Table 5.12 on page 85 because not all cognate pairs
have a gloss in common.
Since the vowel correspondences in Algonquian are rather inconsistent, following
Hewson [1974], I decided to concentrate on consonants and consonant clusters. The
models were induced using Method C, which separates the syllabic and the nonsyllabic phonemes. On the Fox{Menomini data, the algorithm terminated after 12
iterations, which took several minutes. (When the NCC option is switched on, thecomputation takes much longer because each iteration involves inducing anew boththe base and the trial translation models.)Figure 6.2 shows the correspondences determined by CORDI (the right circle)
intersected with the ones enumerated by Bloom eld (the left circle). S represents thephoneme [S], C represents [Ù], and q represents the glottal stop [P]. The intersection ofboth circles contains 20 correspondences that were correctly identi ed by the program.
The three erroneous correspondences on the right (false positives) can be traced toalignments of unrelated words. The resulting precision was therefore 87%. As forthe false negatives on the left, I manually analyzed the 79 cognate pairs available tothe program, and found that s:hk and p:hp occur twice, hc:qc occurs once, and theremaining seven complex correspondences do not occur at all. The h:q correspondence
is dubious because it only occurs within clusters. Since, by de nition, recurrent

Chapter 6.

125

Determination of correspondences

h:q
Sk:hk

n:n

p:hp

h:h

m:m

s:s

p:p

hC:qC

k:hk

hk:Ck

hp:sp

C:C

hC:hC

ht:ht

hk:hk

Sk:sk

C:hC

s:hs

s:qs

S:qs

S:hs

n:hn
Bloomfield

t:t

k:k
t:ht

S:s

hp:hp

s:hn

s:qn

p:C

ht:qt

hk:t
t:sk

CORDI

Figure 6.2: The Fox{Menomini consonantal correspondences determined by a linguist
and by CORDI.
correspondences are those that occur at least twice, the recall on the test set was
91%. For comparison, on the same Fox{Menomini list, JAKARTA identi es only
eight consonantal correspondences: n:n, m:m, h:h, s:s, p:p, t:t, k:k, and h:hs, ofwhich the single complex correspondence is not in Bloom eld's set.
The results of the experiment are extremely encouraging. The accomplishment ofa very high precision and recall on a test set composed of 80% noise con rms thatthe iterative statistical approach advocated here is highly robust. The impressive
outcome should, however, be interpreted with caution. Because of the (unavoidably) small number of target correspondences, the change of a single classi cation

Chapter 6.

Determination of correspondences

126

makes a di erence of about 5% in the resulting precision/recall gures. Moreover,the decision to ignore vowels and glides helped the program to focus on the righttype of correspondences. Finally, the Algonquian consonantal correspondences arealmost context-free, which nicely suits the program's principles. Nevertheless, it isa very satisfying situation when the author has to justify the results that seem toooutstanding.

6.6 Conclusion
I have presented a novel approach to the determination of correspondences in bilingual
wordlists. The results of experiments indicate that the approach is robust enough tohandle a substantial amount of noise that is introduced by unrelated word pairs.
CORDI does well even when the number of non-cognate pairs is more than double
the number of cognate pairs. When tested on the cognate-identi cation task, CORDI
achieves substantially higher precision than comparable programs.
Since the correspondences determined by my program are explicitly posited, they
can be veri ed by examining individual cognate pairs. This is in contrast with statistical approaches of Ringe [1998] and Kessler [2001] that estimate the probability ofthe existence of cognates in bilingual wordlists. Those methods do not provide veri able evidence beyond a single value which expresses the likelihood that the correlation
between languages is statistically signi cant. In addition, due to the stochastic nature of the methods, such results are often diÆcult to reproduce. In my opinion, thesigni cance tests alone are unlikely to convince historical linguists.
Another advantage of the algorithm presented here is its capability of linking
phonemes in any word position. The approaches that rely on the syllabic structureof words [Ringe, 1992] or the character position within word [Tiedemann, 1999] tend

Chapter 6.

Determination of correspondences127

to produce rigid alignments, which are unable to handle phenomena such as epenthesis (insertion of a vowel between consonants) or syncope (loss of a vowel between
consonants).
The results presented here prove that the techniques developed in the context ofstatistical machine translation can be successfully applied to a problem in diachronicphonology. I am convinced that the transfer of methods and insights is also possible
in the other direction.

Chapter 7
Wrap-up and outlook
I have presented algorithms for the three principal steps of the comparative method of
language reconstruction: the alignment of cognates, the identi cation of cognates, andthe determination of correspondences. In this nal chapter, I discuss the possibility ofintegrating all three components into a self-contained program capable of performinga large part of the reconstruction process, and I point out some other directions for
future research. I conclude with a review of the main results presented in the thesis.

7.1 Identi cation of cognates
In this thesis, I have presented two distinct algorithms for the identi cation of cognates: a similarity-based method described in Chapter 5, and a correspondence-based
method introduced in Chapter 6. Both approaches are valid and have been used
before: Oakes's program JAKARTA is an example of the former, while Guy's COGNATE belongs to the latter. Similarly, for the related task of estimating the likelihoodof historical connection between languages, Baxter and Manaster Ramer [2000] andOswalt [1998] employ similarity-based measures, while Ringe [1998] and Kessler [2001]
128

Chapter 7.

Wrap-up and outlook

129

Languages
JAKARTA Trunc. DICE LCSR ALINEEnglish German.888.856 .786 .903
.918
FrenchLatin.787.792 .653 .809
.865
English Latin.447.515 .360 .539
.733
German Latin.518.443 .399 .498
.704
English French.411.570 .428 .561
.616
FrenchGerman.406.435 .382 .483
.497
Albanian Latin.455.558 .437 .582
.623
Albanian French.432.595 .451 .487
.613
Albanian German.248.253 .310 .282
.307
Albanian English.227.151 .194 .181
.276
Average
.482
.517
.440
.533
.615
Table 7.1: Average cognate identi cation precision on the test set for various
similarity-based methods.
concentrate on correspondences. Is it possible to determine which of the two approaches achieves better results?
Although it would be diÆcult to settle this issue once and for all, it is relatively
straightforward to compare the algorithms proposed in this thesis by calculating theiraverage precision on the same input data. Table 7.1 shows the performance of various similarity-based methods on ve 200 Swadesh lists compiled by Kessler [2001].
Because the words in the lists are already matched by meaning, the semantic component of COGIT is not applicable here, which means that the identi cation of cognates
is performed solely on the basis of phonetic similarity. ALINE's parameter settings
are the same as used in Chapter 4. The results con rm again that ALINE performs
consistently better than other methods. Surprisingly, some orthographic measuresoutperform Oakes's program JAKARTA.
In order to facilitate comparison with the correspondence-based methods, Ta-Chapter 7.

130

Wrap-up and outlook

Languages
EnglishGermanFrenchLatin
EnglishLatin
German Latin
EnglishFrenchFrenchGermanAlbanian Latin
Albanian French
Albanian German
Albanian English
Average

Cognates
.590
.560
.290
.290
.275
.245
.195
.165
.125
.100
.283

Method B
.957
.914
.641
.723
.528
.502
.432
.292
.177
.373
.554

Method D
.950
.866
.853
.857
.559
.528
.606
.437
.312
.196
.616

ALINE
.918
.865
.733
.702
.615
.497
.622
.612
.307
.276
.615

Table 7.2: Average cognate identi cation precision on the test set for various methods.
ble 7.2 reproduces some of the results from Chapter 6. On average, ALINE does
about as well as Method D and better than other correspondence-based methods
proposed in Section 6.5.4. Even on the language pairs involving Albanian, where theproportion of cognates is below 20%, ALINE's performance is surprisingly good.
Both the correspondence-based and the similarity-based methods perform well.
Intuitively, a judicious combination of both techniques should produce even better
results. One possible approach is to use the information about correspondences toboost the similarity values of certain phoneme pairs. First, the translation model
would be induced on the data as described in Chapter 6. The phoneme pairs representing strong correspondences (correspondences that have a likelihood score above
the threshold t) would have their similarity scores increased by a constant value. This
constant value should be a parameter that can be established on a development set.
A design problem that must be solved in order to implement this idea is the incorporation of complex, multi-phoneme correspondences into a similarity scheme that is

Chapter 7.

Wrap-up and outlook

131

currently de ned only for pairs of individual phonemes.
The combined similarity-cum-correspondences approach could also be used forthe task of identifying cognates from raw vocabulary data, in the manner describedin Chapter 5. The idea is to rst identify a set of likely cognate pairs, then induce a translation model on the set, and nally use the determined correspondences
to improve COGIT, the cognate identi cation algorithm. Such an approach would
integrate virtually all algorithms proposed in this thesis.
One possible way to determine the set of likely cognate pairs is to select n candidate pairs starting from the top of the ordered list produced by COGIT. After all,these are the most likely cognate pairs. The problem with such an approach is thatthe selected pairs are certain to exhibit high phonetic similarity. When a translation
model is induced on such set, the strongest correspondences can be expected to consist mostly of pairs of identical phonemes. This is because the set of candidates isgoing to be biased by the method used for their selection.
A better idea is to select candidate cognates on the basis of semantic similarity
only. Analysis of the Algonquian vocabulary lists shows that selecting all vocabulary
entries characterized by the highest level of semantic similarity, that is, gloss identity,
produces a set of candidate pairs containing a substantial proportion of cognates.
Table 7.3 shows the number of pairs that have at least one gloss in common, andthe proportion of cognates in such set. The experiments described in Section 6.5.5
indicate that such levels of cognate content may be suÆcient for the determinationof the strongest correspondences. Again, the values of the boosting constant and themixing parameter should be estimated on a development set.

Chapter 7.

132

Wrap-up and outlook

Languages
Fox
Fox
Fox
Menomini
Menomini
Cree

Menomini
Cree
OjibwaCree
OjibwaOjibwa

All
pairs
397
409
326
834
656
732

Cognate
pairs
79
85
86
146
160
242

Proportionof cognates
.199
.208
.263
.175
.244
.331

Table 7.3: The proportion of cognates among the pairs that have at least one gloss
in common.

7.2 Reconstruction
Following the determination of correspondences, the next step of the comparative
method is the reconstruction of proto-phonemes and proto-forms. For each correspondence, the linguist posits a phonetic segment as the hypothetical source of thepair of phonemes that make up the correspondence. In the previous chapters, I haveproposed algorithms for the antecedent stages of the reconstruction process. Is it
possible to automate also this nal step of the comparative method?
The rules of comparative reconstruction are intuitive and informal. The selectionof phonemes requires extensive knowledge about the languages in question, as well as
about the typological principles that determine the plausibility of a given phonologicalsystem. In order to reconstruct, say, Proto-Germanic, the facts about other IndoEuropean sub-families have to be taken into account. Also, the reconstructed systemshould not have abnormal properties (for example, a total lack of fricatives) that areat odds with what is known about existing languages. Ideally, a proposal should

Chapter 7.

Wrap-up and outlook

133

include an ordered set of regular sound changes which transform the hypothesized
proto-language etyma into the attested forms.
The proto-languages proposed by independent researchers are often very di erent.
The following observation by Greenberg summarizes the current views on Proto-IndoEuropean.
After more than a century of e ort, which has involved the majority of thelinguistic community in the nineteenth century and a substantial groupof specialists in the twentieth, it is not too much to say that the only
matters on which everyone agrees in regard to the sound system of ProtoIndo-European are that there were at least four points of articulation forstops, including at least labials and dentals or alveolars, at least threemanners of articulation for stops, and at least one sibilant and one vowel.
[Greenberg, 1993]
He then gives an example of laryngeals, of which \almost every number from zero toten or more has been posited". There does not seem to be any accepted procedure for
evaluating the validity of a hypothesized proto-language. Speci c proposals regarding
relatedness of languages and the shape of the genealogical trees of language families
may become gradually accepted by achieving the support of the majority of linguists.
In my opinion, the design of the phonological proto-system is best left to humanexperts. In the future, I would like to implement a module that facilitates such atask by allowing the user to propose a proto-phoneme for each of the correspondences determined by CORDI, and subsequently generates a proto-form for each of
the identi ed cognate sets. Such an interactive approach would have much in common
with the Reconstruction Engine of Lowe and Mazaudon [1994], with the importantdi erence of relieving the user of the task of determining correspondences. As an example, let us assume that the user has tagged the correspondences in Table 7.4 withthe reconstructed segments shown in boxes, The program could then automatically
posit Proto-Algonquian *m(e:E)ck(w)i(h) for the possible cognate pair meskwi (Fox,`blood') and mEhkh (Menomini, `blood'). The user could continue the reconstruction

Chapter 7.

Wrap-up and outlook

134

Fox Menomini Proto-segment
m
m
m
sk
hk
ck
i

i
Table 7.4: A partial table of correspondences.
by deciding on the status of segments included in brackets, perhaps ending up withsomething like *meckwi.
In the future it should be possible to integrate ALINE, COGIT, and CORDI, andthe proposed reconstruction module into a system that given nothing more than vocabulary lists of two related languages outputs a partial reconstruction of the lexiconof their proto-language. Other issues that should be addressed before such a system
becomes functional include the construction of a comprehensive training corpus ofaligned cognates that would make it possible to to derive the similarity matrices automatically, and the extension of the algorithms proposed here to handle more than
two languages at the same time.
Although it may seem somewhat disappointing to stop short of creating a computer system that performs the entire process of reconstruction of proto-languages
in a fully unsupervised fashion, the algorithms proposed in this thesis are intended
to assist rather than replace comparative linguists. The proposed correspondences,cognates, and their alignments should be considered as a starting point for further
investigations. The information that can be gleaned from the word lists must be
supplemented by other types of information, which include the morphology and syntax of the languages in question, the clues from related languages, general linguisticknowledge, and sometimes even extra-linguistic sources. As in machine translation,
it would be unrealistic to expect a computer program to exceed or even match theChapter 7.

Wrap-up and outlook

135

performance of a human expert on such a diÆcult problem. The best results may
come from combining the speed and thoroughness of the former with the intuition
and knowledge of the latter.

7.3 Summary of results
In this thesis, I have reported innovative algorithms for the three principal steps ofthe comparative method of language reconstruction: the alignment of cognates, theidenti cation of cognates, and the determination of recurrent sound correspondences.
In Chapter 4, I considered the problem of the alignment of phonetic strings, which
is a necessary step in many applications in computational phonology. After discussing
various approaches to phonetic alignment, I presented a new algorithm that combines
the dynamic programming approach to nding the optimal alignment with a complex
scoring scheme for computing phonetic similarity between phonetic segments. The
new algorithm, which is inspired by ideas taken from bioinformatics, incorporates several techniques developed for sequence comparison: an extended set of edit operations
that includes compression and expansion, local and semi-global modes of alignment,
and the capability of retrieving a set of near-optimal alignments. Unlike previously
proposed distance-based algorithms, it is based on the notion of similarity between
sounds, which is likely to better re ect the relatedness of corresponding segments.
The scoring scheme is not tied to any language-speci c system of phonemic contrasts,
but instead is derived from a universal set of phonetic features which is suÆciently
general and exible to express all possible speech sounds that exist in the world's
languages. Similar schemes have been proposed before, but they all lacked the key
concept of feature salience, which is necessary to properly balance the importance ofvarious features. The algorithm was evaluated on an independently compiled set ofChapter 7.

Wrap-up and outlook

136

cognates, and was found to outperform other algorithms reported in the literature.
In Chapter 5, I developed a method for identifying cognates directly from thevocabularies of related languages. The only requirement of the method is that theuser provides two wordlists containing phonetically-transcribed lexemes with their
meaning explained by short English glosses. The wordlists do not have to be synchronized, nor the lexemes forced into semantic slots. The phonetic transcription oforthographic data can be performed automatically for most languages. The overall similarity between vocabulary items is calculated as a linear combination of thephonetic and the semantic similarity. I showed that the phonetic measure proposed
in Chapter 4 outdoes the orthographic measures commonly used in computational
linguistics. The procedure for estimating semantic similarity, which employs an electronic lexical database and a part-of-speech tagger, is able to associate glosses thathave little or no surface aÆnity. The experiments performed on actual vocabularies
of four Algonquian languages demonstrate that the method not only identi es withgood precision a large portion of cognates in the data, but also contributes new entries
to the existing etymological dictionary.
In Chapter 6, I proposed an original approach to the determination of recurrent
sound correspondences in bilingual wordlists based on the idea of relating recurrent correspondences between sounds to translational equivalences between words.
Through induction of statistical models that are similar to those developed for statistical machine translation, the method is able to recover recurrent sound correspondences from bilingual wordlists that consist mostly of unrelated pairs. A cognate identi cation method that takes advantage of the discovered correspondences
achieves higher accuracy than the previously reported algorithms. Finally, I showed
how an algorithm designed for extracting noncompositional compounds from bitexts
can be used to determine complex sound correspondences in wordlists. By applyingChapter 7.

Wrap-up and outlook

137

the powerful expectation-maximization approach, a computer program can withinminutes come close to replicating the results of prolonged linguistic investigations.

7.4 Conclusion
Although it is impossible to predict the impact that this thesis will have on researchin computational linguistics, the responses that I have received so far indicate thatthe scope of applications extends well beyond language reconstruction. The phoneticalignment algorithm described in Chapter 4 has already been found suÆciently practical for implementation in research projects on declarative prosodic morphology [Girgsdies, 2000], and on aligning reference and hypothesized speech transcriptions [Fisher,2000]. During informal discussions following my presentations at computational linguistics conferences, several experts commented positively on the relevance of mywork on the identi cation of cognates to the issues arising in machine translation.
The experiments reported in this thesis provide a novel assessment of various algorithms and resources commonly employed in computational linguistics. Because
genetic cognates arise by evolving from a single word in a proto-language, they are
ideal for testing various lexical and semantic measures of similarity. An objective
evaluation of such measures is diÆcult as evidenced by the fact that Brew and McKelvie [1996] devoted several days to judge the translational equivalence of several thousand word-pairs automatically extracted from a bilingual corpus. In contrast, theaverage precision of the lexical measures computed in Chapter 5 was instantly calculated by comparing it against the standard of previously established cognate sets.
Other experiments that I performed con rm the generality of Melamed's algorithms
for the induction of translational models and for the discovery of noncompositional
compounds, and cast light on the quality of WordNet noun hierarchies.

Chapter 7.

Wrap-up and outlook

138

The focus of this thesis has been the problem of automatic language reconstruction. I do not claim that the algorithms described here o er a comprehensive andfully satisfying solution to the problem. Indeed, I consider it unlikely that such asolution will be found soon. However, the results of the careful evaluations to which
I submitted the proposed methods should leave no doubt that I have advanced thestate of the art in the area of computational diachronic phonology. I hope that theset of publicly available programs that arise from this research will help comparative
linguists to provide conclusive evidence for hitherto conjectural language groupings.

Appendix A
The Swadesh 200-word list
Many variants of the Swadesh 200-word list exist. The following version is used in the
Comparative Indo-European Data Corpus [Dyen et al., 1992]. Kessler [2001] employs
another variation, which includes breast, claw, full, go, grease, horn, hot, human, knee,
knife, moon, now, path, round, true; but not fat, fear, oat, how, leg, live, person, right,
road, rope, turn, walk, warm, when, where.

139

Appendix A.

allandanimal
ashes
at
back
bad
bark
because
belly
big
bird
to biteblack
blood
to blowbone
to breathe
to burn
child
cloud
cold
to cometo count
to cutday
to dieto digdirty
dog
to drink
drydull (knife)
dust
ear
earth
to eateggeye
to fall140

The Swadesh 200-word list

far
fat
fatherto fearfeatherfew
to ghtreshve
to oat
to ow
ower
to y
fog
foot
four
to freeze
fruit
to give
good
grass
green
guts
hair
hand
he
head
to hear
heart
heavy
here
to hitholdhow
to hunt
husband
I
ice
if

in
to killknow
lake
to laughleaf
left (hand)leg
to lie (on side)
to live
liver
long
louse
man (male)manymeat ( esh)mothermountainmouth
namenarrow
near
neck
new
night
nose
not
old
one
other
personto play
to pullto pushto rainred
right (correct)
right (hand)
river
road

root
rope
rotten
rub
salt
sand
to sayscratchsea
to seeseed
to sew
sharp
short
to sing
to sitskinsky
to sleepsmall
to smellsmokesmooth
snake
snow
some
to spitto split
to squeeze
to stabto stand
star
stick
stone
straight
to sucksun
to swellto swim
tail

that
there
they
thick
thin
to think
this
thou
three
to throw
to tietonguetoothtree
to turntwo
to vomit
to walkwarm
to wash
water
we
wet
what
when
where
white
who
wide
wife
wind
wing
wipe
with
woman
woods
worm
you (plural)
year
yellow

Appendix B
A historical derivation programThis appendix describes a Perl program that simulates the phonological evolution ofPolish, and its results. The program takes as input a Proto-Slavic etymon, transforms it by a series of sound changes, and produces a predicted modern Polish word.
The descriptions of sound changes were extracted from textbooks on the historicalphonology of Slavic. The changes are implemented as sequences of regular expressions
substitutions. The program has no notion of phonological features, but uses sets ofphonemes instead.
The program was applied to 706 Proto-Slavic etyma extracted from books on thehistorical phonology of Slavic. 80 (11.3%) of the Proto-Slavic etyma have no extant
cognates in Polish because of the lexical replacement phenomenon. The results on theremaining 626 etyma are summarized in Table B.1. Most of the predictions match theactual Polish words exactly. In other cases, the phonemic edit distance betwen theprediction and the actual word is calculated. The percentage of exact matches could
probably be increased by a more careful implemenation of the sound changes, but it isunlikely to reach 100%. Because of phenomena such as analogy and hypercorrection,
sound changes are never perfectly regular.
141

Appendix B.

A historical derivation program

142

Edit distance Number of forms Percent of total
0
454
72.5%
1
84
13.4%
2
63
10.1%
3
20
3.2%
4
5
0.8%
Total retained
626
100%
Table B.1: Tested proto-forms grouped by the accuracy of the output.
Some words that have undergone semantic shifts are given in Table B.2. Thosewords have survived, but their modern meaning has changed. Some of the words haveretained their original meaning in other Slavic languages.
Proto-Slavic
Xrstuiskatije¸anapast'plut
tmavolst'
znamenije

Gloss
Generated form Modern meaning`cross'chrzest`baptism'`to seek'
iskac`to groom'`disease'jedza`witch'`temptation'napasc`assault'`body'
plec`sex'`darkness, myriad' cma
`moth'`power'wlosc`estate, property'`sign'
znamie`scar'
Table B.2: Examples of semantic shifts.

Table B.3 contains forms produced by applying the sequences of sound changes to
the Proto-Slavic etyma that have been replaced by other words during the evolutionof Polish. The words marked with a y are attested in Old Polish. What is interesting
about the generated forms is that they conform to the phonotactic constraints ofPolish. The words do sound Polish, but their meaning is totally opaque to the native
Polish speakers.

Appendix B.

A historical derivation program

143

Proto-Slavic Gloss
Generated form Modern meaningcrv
`worm'
czerwy?
ydever`husband's brother' dziewierz?
golgolu`word'
glogol?
govoru`noise'
gowor
?
jazva
`wound'jazwa?
klet
`room'klec?
kosnoti`to touch'kosnac?
kovu`ambush'kow?
krovu`roof'krow?
ykysluj`sour'
kisly?
lokavuj`sly'lakawy?
lisiti`to deprive'
liszyc?
l`ubodejica `hussy'
lubodziejka?
mzda`wages'mzda?
napast`temptation'napasc?
nastavniku `supervisor'
nastawnik?
nogut`claw'
nogiec?
otroce`child'otrocze?
pot
`path'
pac?
poglumiti se `to ponder'
poglumic sie?
pospesniku `helper'
pospiesznik?
premuditi`to delay'przemudzic?
rabu`slave'rab?
sumernuj`humble'smierzny?
yskotu`cattle'skot?
stugna`street'stegna?
taina`secret'
tajna
?
umu
`mind'um?
veleti`to order'
wielec?
vreme`time'
wrzemie?
Xramu`temple'chrom?
Xytjniku`predator'
chycnik?
zdati`to wait'z_ dac?
zekti`to burn'z_ ec?
Table B.3: Examples of the generated words that have no existing counterparts.

Appendix C
The alignment code
This appendix contains the C++ code for the phonetic alignment. The code, which
has been constantly evolving since 1999, integrates several extensions of the basic
dynamic programming algorithm described in Section 4.4. It constitutes the core of
ALINE, and is also of prime importance in both COGIT and CORDI. By including
the code, I hope to make it easier for other developers to incorporate advanced features
into their alignment programs. Although I believe that it is essentially error-free, nowarranty is implied.

144

Appendix C.

The alignment code/**************************************************************************The routine `align' finds all alignments that are within a margin of the
optimal alignment, which is set by the parameter `scoreMargin'.
However, if ONE_ONLY is defined, a single alignment isconstructed (which may not be optimal if scoreMargin < 1.0).
The following names correspond to four possible modes of comparison:
GLOBAL, SEMI_GLOBAL, HALF_LOCAL, and LOCAL.
Exactly one of them must be defined.
**************************************************************************/#include "external.h"/*
The following external names are used:
const int MAXL;
const int NUL;
const int DUB;
const int LIM;
const int NoScore;// max length of a word// deletion filler// compression filler// local alignment delimiter// very large negative integer// A straightforward FIFO data structure.
class Stack{public:void clear();// remove all elements
void push( int i1, int i2 = 0 ); // add element (i1) or (i1,i2) to the top
void pop( short k = 1 );// pop k elements from the topbool allowed();// false if insertion follows deletion
void result( int );// output alignment};// An interface between the alignment algorithm and the actual words.
class Sigma{
public:short phlenA();// phonetic length of word A
short phlenB();// phonetic length of word B
int sub( short i, short j );// cost of substituting A[i] with B[j]int expA( short i, short j );// cost of expanding A[i] to B[j-1] B[j]int expB( short j , short i ); // cost of expanding B[j] to A[i-1] A[i]int skipA( short i );// cost of deleting A[i]int skipB( short j );// cost of deleting B[j]};*/// global variables
int S[MAXL][MAXL];// the score matrix
float AcptScore; // minimal acceptable score
Stack Trace;// links between corresponding segments
Stack Out;// alignment constructed by dynamic programming
Stack Cost; // cost of individual operationsbool FallThru;// for ONE_ONLY mode

145

Appendix C.

The alignment code

int similarity( Sigma *sig );void alignment( Sigma *sig, short i, short j, int T );// Wrapper function for the score matrix.
inline int Score( short i, short j ){return ( ( i >= 0 ) && ( j >= 0 ) ? S[i][j] : NoScore );}// Finds all alignments within the scoreMargin.
void align( Sigma *sig, float scoreMargin = 1.0 ){short lenA = sig->phlenA();
short lenB = sig->phlenB();
Cost.clear();Trace.clear();Out.clear();
FallThru = false;
int dpScore = similarity( sig ); // determine the maximum similarity
AcptScore = dpScore * scoreMargin;for ( short i = 0; i <= lenA; i++ ){for ( short j = 0; j <= lenB; j++ ){#if defined(GLOBAL) || defined(HALF_LOCAL)
if ( i < lenA || j < lenB ) // corner start point only
continue;#endif#if defined(SEMI_GLOBAL)
if ( i < lenA && j < lenB ) // border start points only
continue;#endifif ( S[i][j] >= AcptScore ){// padding at the beginningfor ( short j1 = lenB; j1 > j; j1-- )Out.push( NUL, j1 );for ( short i1 = lenA; i1 > i; i1-- )Out.push( i1, NUL );Out.push( LIM, LIM );// delimits the alignmentalignment( sig, i, j, 0 );// recursion starts here
Out.pop(lenA-i+lenB-j+1);
if ( FallThru )return;
}
}
}
}

146

Appendix C.

The alignment code// Fills the score matrix S; returns the similarity between words A and B.
int similarity( Sigma *sig ){short lenA = sig->phlenA();
short lenB = sig->phlenB();
int sgmax = 0; // not meaningful for global case
int m1, m2, m3, m4, m5, lmax;
S[0][0] = 0;
for ( short i = 1; i <= lenA; i++ )#if defined(GLOBAL)
S[i][0] = S[i-1][0] + sig->skipA(i);#else
S[i][0] = 0;
#endiffor ( short j = 1; j <= lenB; j++ )#if defined(GLOBAL)
S[0][j] = S[0][j-1] + sig->skipB(j);#else
S[0][j] = 0;
#endiffor ( short i = 1; i <= lenA; i++ ){for ( short j = 1; j <= lenB; j++ ){m1 = Score(i-1,j) + sig->skipA(i);m2 = Score(i,j-1) + sig->skipB(j);m3 = Score(i-1,j-1) + sig->sub(i,j);
m4 = Score(i-1,j-2) + sig->expA(i,j);
m5 = Score(i-2,j-1) + sig->expB(j,i);#if defined(LOCAL) || defined(HALF_LOCAL)
lmax = max( m1, m2, m3, m4, m5, 0 );#elselmax = max( m1, m2, m3, m4, m5 );#endifS[i][j] = lmax;
if ( lmax > sgmax )#if defined(SEMI_GLOBAL)
if ( i == lenA || j == lenB ) // border only for semi-global#endifsgmax = lmax;}}#if defined(GLOBAL) || defined(HALF_LOCAL)
dpScore = Score( lenA, lenB );#endifreturn sgmax;}

147

Appendix C.

The alignment code// Recursively retrieves alignments from the score matrix S;// i and j indicate the current position within words A and B, respectively;// T accumulates the total score of the current alignment.
void alignment( Sigma *sig, short i, short j, int T ){#ifdef ONE_ONLY
if ( FallThru ) return;#endifif ( i == 0 && j == 0 ){record:assert( Score(i,j) == 0 );if ( Out.allowed() && !FallThru ){Out.push( LIM, LIM );// delimits the alignment// padding at the endfor ( short i1 = i; i1 > 0; i1-- )Out.push( i1, NUL );for ( short j1 = j; j1 > 0; j1-- )Out.push( NUL, j1 );// output the alignment#if defined(GLOBAL)
Out.result( T + (i+j)*sig->skipA(0) );#else
Out.result( T );#endifOut.pop(i+j+1);#ifdef ONE_ONLY
FallThru = true;#endif}}else{#if defined(LOCAL) || defined(HALF_LOCAL) || defined(SEMI_GLOBAL)
if ( ( i == 0 ) || ( j == 0 ) ) goto record; // shortcut#endifint subSc = sig->sub(i,j);
if ( Score(i-1,j-1) + subSc + T >= AcptScore ){Cost.push( subSc );Out.push( i, j );Trace.push( i, j );alignment( sig, i-1, j-1, T + subSc );Trace.pop();
Out.pop();
Cost.pop();}
int insSc = sig->skipB(j);if ( ( i == 0 ) || ( Score(i,j-1) + insSc + T >= AcptScore ) ){Cost.push( insSc );148

Appendix C.

}

The alignment code

Out.push( NUL, j );alignment( sig, i, j-1, T + insSc );Out.pop();
Cost.pop();

int expSc = sig->expA(i,j);
if ( Score(i-1,j-2) + expSc + T >= AcptScore ){Cost.push( expSc );Cost.push( NUL );Out.push( i, j );Out.push( DUB, j-1 );Trace.push( i, j );Trace.push( i, j-1 );alignment( sig, i-1, j-2, T + expSc );Trace.pop(2);Out.pop(2);Cost.pop(2);}int delSc = sig->skipA(i);if ( ( j == 0 ) || ( Score(i-1,j) + delSc + T >= AcptScore ) ){Cost.push( delSc );Out.push( i, NUL );alignment( sig, i-1, j, T + delSc );Out.pop();
Cost.pop();}int cmpSc = sig->expB(j,i);if ( Score(i-2,j-1) + cmpSc + T >= AcptScore ){Cost.push( cmpSc );Cost.push( NUL );Out.push( i, j );Out.push( i-1, DUB );Trace.push( i, j );Trace.push( i-1, j );alignment( sig, i-2, j-1, T + cmpSc );Trace.pop(2);Out.pop(2);Cost.pop(2);}#if defined(LOCAL) || defined(HALF_LOCAL)
if ( Score(i,j) == 0 ) goto record; // shortcut#endif}}149

Appendix D
Covington's test set
This appendix contains the full set of alignments generated by ALINE on Covington's test set of 82 cognates. They are given in the right column. The left column
reproduces the alignments produced by Covington's program. In the cases where
Covington's program produces more than one alternative alignment, only the rst
one is given.

150

Appendix D.

151

Covington's test set

Spanish-French cognate pairs (I)Covington's alignments

ALINE's alignments

yo/je

k
k

y

o


z

@

t

u

t

u


n

o

s

o

t

r

o

s

n

u

{

{

{

{

{

{

k

y

e

n

k

i

{

{

k

{

e

k

w

a

t

o

d

o

s

t

u

{

{

{

tu/tu

k
k

nosotros/nousquien/qui
que/quoikkkk

todos/tous
una/une
u

n

a

u


n

{

d

o

s

d

o


{

k
k

k
k
k
k

dos/deuxkktres/troix
t

r

{

e

s

t

r

w

a

{

o

m

b

r

e

o

m

{

{

{

hombre/homme

k
k
k
k

y

o


z

@

t

u

t

u


n

o

n

u

k

ye

k

i

k

e

k
k
k
k
k
k
k
k

k

k
wa k

t

o

t

u

u

n

u


n

d

o

d

o


k
k

t

r

e

t

r

wa

o

m

o

m

k
k
k
k

k
k

sotros

n

dos

a

s

k
k
bre

s

Appendix D.

152

Covington's test set

Spanish-French cognate pairs (II)Covington's alignments
arbol/arbre
a

r

b

{

o

l

a

r

b

r

@

{

p

l

u

m

a

p

l

u


m

{

k

a

b

e

k

a

p

{

b

o

k

a

b

u


s

{

p

y

e

p

y

e

k

o

r

a

k

o


r

{

b

{

e

r

v

w

a

r

b

e

n

i

r

v

@

n

i

r

d

e

i

r

d

{

i

r

pluma/plumecabeza/cap
boca/bouche
pie/piedcorazon/coeurver/voirvenir/venir
decir/direT{pobre/pauvre

T{

ALINE's alignments
k
k
k
k
k
k

a

{

k
k
k
k
T
{

o

n

{

{

k
k
k
k

p

o

b

r

e

p

o

v

r

@

k
k
k
k
k
k

a

r

b

o

l

a

r

b

{

r

p

l

u

m

p

l

u


m

k

a

b

k

a

p

b

o

k

b

u


s

p

y

e

p

y

e

k

o

r

k

o


r

b

e

r

v

wa

r

k
k

b

e

n

i

r

v

@

n

i

r

d

e

r

{

T
{

i

d

i

r

p

o

b

r

e

p

o

v

r

@

k
k
k
k

k
k

k
k

a

T

e a

a

k
k
k
k

T

a on

k
k
k
k
k
k

@

Appendix D.

153

Covington's test set

English-German cognate pairs (I)Covington's alignments
this/dieses
D

i

{

{

s

d




z

e

s

D



t

d

a

s

w

a

t

v

a

s

n

a

{

t

n

i

x

t

l

o

l

a

N
N

m



n

m

a

n

f

l

e

{


s

f

l

a

y


s

b

l

@

d

b

l

u


t

f

e

D

f


e

d

@
@

h



r

h

a


r

that/daskk

not/nichtkkkkman/Mannkkesh/Fleischblood/Blut

k
k
k
k

feather/Feder
hair/Haar

d


k
k

what/waslong/lang

ALINE's alignments

r
r

k
k
k
k

k
k

D

i

s

z

e

s

D



t

d

a

s

w

a

t

v

a

s

k
k

n

a

{

t

n

i

x

t

l

o

l

a

N
N

k
k

m



n

m

a

n

k
k

f

l

e


s

f

l

ay


s

b

l

@

d

b

l

u


t

f

e

D

f


e

d

@
@

h



r

h

a


r

k
k

k
k

k
k

k
k

k
k
k
k
r
r

k
k

Appendix D.

154

Covington's test set

English-German cognate pairs (II)Covington's alignments
ear/Ohr

ALINE's alignments
k
k

i

r

o


r

a

{

{

a

w

g

@

n

o

w

z

n

a


{

z

{
@

k
k

m

a

w

{

{

T

m

u

n

t

k
k

t

{

@

t

s

u

N
N

{
@

eye/Auge
nose/Nasekkymouth/Mund

tongue/Zungekkfoot/Fu

k
k

f

u

t

f

u


s

-

n

i

y

k

n




{

h



n

d

h

a

n

t

h

a

r

t

{

h

e

r

t

s

l

i

v

l


e

b

knee/Knie
hand/Hand
heart/Herzliver/Leber

t

@
@

k

k
k

r
r

k
k
k
k

k
k

i

r

o


r

a

y

a

w

k
k

n

ow

z

n

a


z

k
k

m

aw

{

T

m

u

n

t

k
k

t

@

s

u

N
N

k
k

@

t

{

@

t

s

u

N
N

k
k

@

f

u

t

f

u


s

k
k

k
k

@

g

@

k
k

n

iy

n




k
k

h



n

d

h

a

n

t

h

a

r

t

h

e

r

t

l

i

v

l


e

b

@
@

k
k
k
k
r
r

s

k
k

Appendix D.

155

Covington's test set

English-Latin cognate pairs (I)Covington's alignments
and/ante

ALINE's alignments



n

d

{

a

n

t

e



t

a

d

b

l

{

{

o

w

f

l

a


r

e

{

i

{

r

{

{

a

w

r

i

s

i

y

t

{

{

{

{

d

e

r

e

{

{

f

i


s

i

s

k

i

s

f

l

o

w

{

{

l

{

{

f

u

e

r

e

s

t

a

r

{

{

s

t


e

l

l

a

-

{

{

f

u

l

p

l


e

n

u

s

at/ad

blow/ areear/auris
eat/ederee-sh/piscispow/ uerestar/stella
full/plenus

k
k
k
k

grass/gramen

k
k

g

r

{

{



s

g

r

a


m

e

n

h

a

r

{

{

t

k

o

r

d

i

s

h

o

r

n

{

k

o

r

n

u


-

{

a

y

e

g

o

{

heart/cordishorn/cornu
I/ego

k
k

k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k

k
k



n

d

a

n

t



t

a

d

k
k

b

l

o

f

l

a


k
k

i

r

aw

r

k
k

is

iy

t

e

d

k
k

ere

f

i


s

p

i

s

f

l

ow

f

l

s
s

e

w
re

k
k

kis

u

k
k

ere

t

a

r

t


e

l

k
k

f

u

l

p

{

l

k
k


enus

g

r



g

r

a


k
k

h

a

r

t

k

o

r

d

h

o

r

n

k

o

r

n

k
k

go

ay
e

la

s
men

k
k

is

k
k

u


Appendix D.

156

Covington's test set

English-Latin cognate pairs (II)Covington's alignments

ALINE's alignments

knee/genu
-

{

n

i

y

g

e

n

u


{

m

@

D

@

r

m

a


t

e

r

m

a

w

n

t

m

o


{

n

{

@
{

n

e

y

m

{

o


{

{

n

m

e

n

n

y

u

w

{

n

{

{

o

w

u

s

w

@

n

{

{

-

u


n

u

s

r

a

{

w

n

d

{

{

r

o

t

u

n

d

u

s

s

o

w

{

{

{

{

s

u

e

r

e

s

i

t

{

{

{

s


e

d

e

r

e

T

r

i

y

t

r


e

s

-

{

{

t

u

w

d

e

n

t

i

{

T

i

n

{

{

{

t

e

n

u

i

s

mother/mater
mountain/mons
name/nomen
new/novus
one/unus

round/rotundus
sew/suere
sit/sedere
three/tres
tooth/dentis
thin/tenuis

ge

k
k
k
k

n
s

k
k
k
k
k
k
k
k
k
k
k
k
k
k
T
s

k
k

n

i

n

u


k
k

m

@

D

@

r

m

a


t

e

r

m

aw

n

t

m

o


n

s

k
k

n

ey

m

n

o


m

k
k

en

n

yu

w

n

o

w

k
k

us

w

@ n

u


n

k
k

us

r

a

{

w

n

d

r

o

t

u

n

d

s

ow

s

u

k
k

ere

s

i

t

s


e

d

T

r

iy

t

r

k
k

ere


e

k
k

s

t

uw

T

t

i

s

k
k

T

i

n

t

e

n

k
k

uis

k
den k
k
k

y

k
k
@

n

k
k

us

Appendix D.

157

Covington's test set

Fox-Menomini cognate pairs

Covington's alignments
kiinwaawa/kenuaq

ALINE's alignments

{
P

k
k

k




n

w

a


w

a

k

e

n

{ {

u

a

n




n

a

{

n

e

n

a

h

n

a


p


e

w a

n

a


p



E

w

w

a


p

i

m i

n

i

w

a


p

e

m e

n

{

n

a

m 
e

s

a

n

a

m 

s

{

o

k

i

m 
a

w

a

o

k


e

m 
a

w

{


s





s




p

a

s


e

{
P

s

e

p

{

a

h

k

o

h

k

w

a

h

k



E

h

{ { {

p

e

m 
a

t

e

s

i

w

e

n

i

p

e

m 
a

t

e

s

e

w

e

n

{

s

e

n

y

a

s

E

n

{ {

niina/nenahkknaapeewa/naapEEwkk{waapimini/waapemen
nameesa/namEEqs
{
E P

k
k
k
k

okimaawa/okeemaaw
sisiipa/seeqsep

ahkohkwa/ahkEEh

k
k
k
k
k
k

a

pemaatesiweni/pemaateswen
asenya/aqsEn
a
a

{
P

k
k
k
k

k




n

w

a


k

e

n

u

a

k wa
k P

n




n

a

n

e

n

a

k
k

h

n

a


p


e

w

n

a


p

E

w

w

a


p

i

m i

n

w

a


p

e

m e

n

n

a

m 
e

a

m

{
E P

s

n

s

o

k

i

m 
a

w

o

k


e

m 
a

w


s




-


s




p

s


e

P

s

e

p

a

h

k

o

h

a

h

k

E

h

k
k

p

e

m 
a

t

e

s

i

w

e

n

p

e

m 
a

t

e

s

e

w

e

n

s

e

n

s

E

n

a
a

{
P

k
k

k
k

a

k
k
k
k
k
k

k
k

i

a

a

a

kwa

ya

k
k

i

Appendix D.

158

Covington's test set

Cognate pairs from other languages

Covington's alignments

ALINE's alignments

didomi/do
d

i

d

o


m

i

-

{

d

o


{

{

u

g

a

t


e

r

o

x

{

t

@

r

thugater/Tochterthtdaughter/thugater

di

k
k

{

d

o

t

@

r

u

g

a

t


e

r

a

{

g

e

r

a




r

a

s

h a
h
p
e

r

a


m

i

r

{

{

o

-

{

k

e

n

t

u

m

h

e

k

a

{

t

o

n

k

e

n

t

u

m

s

a

{

t

@

m

t

h

ager/ajras

bharami/pherobcentum/hekaton
centum/sat@m

k
k
t

h

t

k

d

o


d

o


k
k

u

g

a

t


e

r

o

x

{

t

@

r

mi

h k

d

o

t

@

r

g

a

t


e

r

k
k

a

g

e

r

a




{

r

k
k

as

k
k

h a
h
p
e

r

a


r

o

k
k

k

e

n

t

u

m

he

k
k

k

a

{

t

o

n

k

e

n

t

u

m

s

a

{

t

@

m

t u

k
k

b

k
k

k
k

mi

k
k

k
k

Appendix E
A list of English{Latin cognates
This list of 112 established English{Latin cognate pairs has been taken from linguistic
literature. It is not meant to be complete, and it may contain a few errors. English
words were transcribed into phonetic notation with the aid of the publicly available
Carnegie Mellon Pronouncing Dictionary, version 0.6.
ek@rgnel
Old@r
m
s
ks@l
b
bEr
bIrd
bc
b@rc
bled
br@D@r
kom
kOrn
kaw

agr
angust
aln
sum
orn
aks
fuit
fer
barb
fag
fraksin
foli
fratr
gemm
gran
bowe

`acre'`agnail'`alder'`am'`ash'`axle'`be'`bear'`beard'`beech'`birch'`blade'`brother'`comb'`corn'
`cow'

du
dOr
Ir
t
et
Elbo
yu
ay
fEro
faD@r
fED@r
fd
fld
fIlm
fayv


159

feki
fore
aur
ed
okto
uln
ow
okul
pork
patr
penn
pask
plan
pell
kwinkwepulik`do'`door'`ear'`eat'`eight'`elbow'`ewe'`eye'`farrow'`father'`feather'`feed'` eld'
` lm'
` ve'
` ea'

Appendix E.

o
fom
fut
fOr
ful
gard@n
gus
gEst
hart
hOrn
hawnd
h@ndr@d
ay
Iz
kIn
n
no
lIk
lay
layt
layt
lIs@n
lON
l@v
ml
mElt
mIr
mIk@l
mId@l
maynd
m@nT
m@D@r
maws
m@rd@rnelnek@dnem
nEfyu
nEst
nu

160

A list of English{Latin cognates

plu
spum
pede
kwart
plen
hort
ansr
host
korde
kornu
kan
kent
ego
est
gen
genu
gnosk
ling
lekt
lew
luk
klu
long
lube
mol
moll
mare
magn
medi
mente
mens
matr
mur
morte
ungw
nud
nomine
nepot
nid
now

` ow'
`foam'`foot'`four'`full'`garden'`goose'`guest'`heart'`horn'`hound'`hundred'
`I'
`is'
`kin'
`knee'`know'`lick'`lie'`light' (adj)`light' (noun)`listen'`long'`love'`meal'`melt'`mere'`mickle'`middle'`mind'`month'`mother'`mouse'`murder'`nail'`naked'`name'`nephew'`nest'
`new'

nayt
nayn
noz
nat
ra
rEd
rut
sOlt
sd
sEv@n
so
sOrt
sIst@r
sIt
sIks
sno
spIt
stnd
star
s@k
s@n
swt
tEn
TIn
Tr
Tr@s
t@N
tuT
tr
tu
wOrm
wOt@r
hu
wIdo
waynd
wulf
wul
rIN
yok
y@N

nokte
nowem
nas
non
kruor
rube
radikesal
semen
septem
su
kurt
soror
sedet
seks
niwem
spu
stare
stell
sug
sol
suaw
dekem
tenu
tres
turd
lingw
dente
dur
duo
form
und
kwis
widu
went
lup
lan
wert
iug
yuwenk`night'`nine'`nose'
`not'
`raw'
`red'
`root'`salt'`seed'`seven'`sew'`short'`sister'
`sit'
`six'
`snow'`spit'`stand'`star'`suck'`sun'`sweet'`ten'`thin'`three'`thrush'`tongue'`tooth'`tree'`two'`warm'`water'`who'`widow'`wind'`wolf'`wool'`wring'`yoke'`young'Bibliography[Adamson and Boreham, 1974] George W. Adamson and Jillian Boreham. The useof an association measure based on character structure to identify semanticallyrelated pairs of words and document titles. Information Storage and Retrieval,
10:253{260, 1974.
[Al-Onaizan et al., 1999] Y. Al-Onaizan, J. Curin, M. Jahr, K. Knight, J. La erty,
D. Melamed, F. Och, D. Purdy, N. Smith, and D. Yarowsky. Statistical machinetranslation. Technical report, Johns Hopkins University, 1999.
[Allen, 1995] James Allen. Natural Language Understanding. The Benjamin Cummings Publishing Company, second edition, 1995.
[Baxter and Ramer, 2000] William H. Baxter and Alexis Manaster Ramer. Beyond
lumping and splitting: probabilistic issues in historical linguistics. In Colin Renfrew, April McMahon, and Larry Trask, editors, Time Depth in Historical Linguistics, pages 167{188. The McDonald Institute for Archeological Research, 2000.
[Bloom eld, 1925] Leonard Bloom eld. On the sound-system of central Algonquian.
Language, 1:130{156, 1925.
[Bloom eld, 1946] Leonard Bloom eld. Algonquian. In Harry Hoijer et al., editor,
Linguistic Structures of Native America, volume 6 of Viking Fund Publications in
Anthropology, pages 85{129. New York: Viking, 1946.
[Brew and McKelvie, 1996] Chris Brew and David McKelvie. Word-pair extraction
for lexicography. In K. O azer and H. Somers, editors, Proceedings of the 2nd
International Conference on New Methods in Language Processing, pages 45{55,
Ankara, Bilkent University, 1996.
161

Bibliography

162[Brill, 1995] Eric Brill. Transformation-based error-driven learning and natural language processing: A case study in part-of-speech tagging. Computational Linguistics, 21(4):543{566, 1995.
[Brown et al., 1990a] P. Brown, J. Cocke, S. Della Pietra, V. Della Pietra, F. Jelinek, J. La erty, R. Mercer, and P. Roossin. A statistical approach to machinetranslation. Computational Linguistics, 16(2):79{85, 1990.
[Brown et al., 1990b] P. Brown, S. Della Pietra, V. Della Pietra, and R. Mercer. The
mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263{311, 1990.
[Buck, 1949] Carl Darling Buck. A dictionary of selected synonyms in the principal
Indo-European languages: a contribution to the history of ideas. Universtity of
Chicago Press, 1949.
[Budanitsky, 1999] Alexander Budanitsky. Lexical semantic relatedness and its application in natural language processing. Technical Report CSRG-390, Universityof Toronto, 1999. Available at ftp.cs.toronto.edu/csrg-technical-reports.
[Burton-Hunter, 1976] Sarah K. Burton-Hunter. Romance etymology: a computerized model. Computers and the Humanities, 10:217{220, 1976.
[Chomsky and Halle, 1968] Noam Chomsky and Morris Halle. The Sound Pattern ofEnglish. New York: Harper & Row, 1968.
[Church, 1993] Kenneth W. Church. Char align: A program for aligning paralleltexts at the character level. In Proceedings of ACL-93: 31st Annual Meeting of the
Association for Computational Linguistics, pages 1{8, Columbus, Ohio, 1993.
[Connolly, 1997] John H. Connolly. Quantifying target-realization di erences. Clinical Linguistics & Phonetics, 11:267{298, 1997.
[Covington, 1996] Michael A. Covington. An algorithm to align words for historicalcomparison. Computational Linguistics, 22(4):481{496, 1996.

Bibliography

163[Covington, 1998] Michael A. Covington. Alignment of multiple languages for historical comparison. In Proceedings of COLING-ACL'98: 36th Annual Meeting of

the Association for Computational Linguistics and 17th International Conference
on Computational Linguistics, pages 275{280, 1998.

[Dayho et al., 1983] M. O. Dayho , W. C. Baker, and L.T. Hunt. Establishinghomologies in protein sequences. Methods in Enzymology, 91:524{545, 1983.
[Dunning, 1993] Ted Dunning. Accurate methods for the statistics of surprise andcoincidence. Computational Linguistics, 19(1):61{74, 1993.
[Durbin et al., 1998] Richard Durbin, Sean R. Eddy, Anders Krogh, and Graeme
Mitchison. Biological sequence analysis. Cambridge University Press, 1998.
[Dyen et al., 1992] Isidore Dyen, Joseph B. Kruskal, and Paul Black. An Indoeuropean classi cation: A lexicostatistical experiment. Transactions of
the American Philosophical Society, 82(5), 1992. Word lists available at
http://www.ldc.upenn.edu/ldc/service/comp-ie.
[Eastlack, 1977] Charles L. Eastlack. Iberochange: a program to simulate systematicsound change in Ibero-Romance. Computers and the Humanities, 11:81{88, 1977.
[Eppstein, 1998] David Eppstein. Finding the k shortest paths. SIAM Journal on
Computing, 28(2):652{673, 1998.
[Fellbaum, 1998] Christiane Fellbaum, editor. WordNet: an electronic lexical
database. The MIT Press, Cambridge, MA, 1998.
[Fisher, 2000] William Fisher. Personal communication, 2000.
[Fox, 1973] Bennett L. Fox. Calculating the K th shortest paths. INFOR { Canadian
Journal of Operational Research and Information Processing, 11(1):66{70, 1973.
[Gildea and Jurafsky, 1996] Daniel Gildea and Daniel Jurafsky. Learning bias andphonological-rule induction. Computational Linguistics, 22(4):497{530, 1996.
[Girgsdies, 2000] Stefan Girgsdies. Personal communication, 2000.

Bibliography

164[Gotoh, 1982] Osamu Gotoh. An improved algorithm for matching biological sequences. Journal of Molecular Biology, 162:705{708, 1982.
[Greenberg, 1987] Joseph H. Greenberg. Language in the Americas. Stanford University Press, 1987.
[Greenberg, 1993] Joseph H. Greenberg. Observations concerning Ringe's Calculating the factor of chance in language comparison. Proceedings of the American
Philosophical Society, 137:79{89, 1993.
[Guy, 1994] Jacques B. M. Guy. An algorithm for identifying cognates in bilingual
wordlists and its applicability to machine translation. Journal of Quantitative Linguistics, 1(1):35{42, 1994. MS-DOS executable available at http://garbo.uwasa. .
[Hall, 1976] Robert A. Hall. Proto-Romance phonology. New York: Elsevier, 1976.
[Hartman, 1981] Steven Lee Hartman. A universal alphabet for experiments in comparative phonology. Computers and the Humanities, 15:75{82, 1981.
[Hewson, 1974] John Hewson. Comparative reconstruction on the computer. In Proceedings of the 1st International Conference on Historical Linguistics, pages 191{
197, 1974.
[Hewson, 1989] John Hewson. Computer-aided research in comparative and historicallinguistics. In I. Batori, W. Lenders, and W. Putschke, editors, Computational
linguistics: an international handbook on computer oriented language research andapplications, pages 576{580. Berlin: W. de Gruyter, 1989.

[Hewson, 1993] John Hewson. A computer-generated dictionary of proto-Algonquian.
Hull, Quebec: Canadian Museum of Civilization, 1993.
[Hewson, 1999] John Hewson. Vocabularies of Fox, Cree, Menomini, and Ojibwa,
1999. Computer le.
[Johnson, 1985] Mark Johnson. Computer aids for comparative dictionaries. Linguistics, 23(2):285{302, 1985.

Bibliography

165[Kay, 1964] Martin Kay. The logic of cognate recognition in historical linguistics.
Memorandum RM-4224-PR, The RAND Corporation, Santa Monica, September
1964.
[Kessler, 1995] Brett Kessler. Computational dialectology in Irish Gaelic. In Proceedings of EACL-95: 6th Conference of the European Chapter of the Association for
Computational Linguistics, pages 60{67, 1995.

[Kessler, 2001] Brett Kessler. The Signi cance of Word Lists. Stanford: CSLI Publications, 2001. Word lists available at http://spell.psychology.wayne.edu/bkessler.
[Knight and Graehl, 1998] Kevin Knight and Jonathan Graehl. Machine transliteration. Computational Linguistics, 24(4):599{612, 1998.
[Koehn and Knight, 2001] Philipp Koehn and Kevin Knight. Knowledge sources forword-level translation models. In Proceedings of the 2001 Conference on Empirical
Methods in Natural Language Processing, pages 27{35, 2001.
[Kondrak, 2000] Grzegorz Kondrak. A new algorithm for the alignment of phonetic
sequences. In Proceedings of NAACL 2000: 1st Meeting of the North American
Chapter of the Association for Computational Linguistics, pages 288{295, 2000.
[Kondrak, 2001a] Grzegorz Kondrak. Identifying cognates by phonetic and semantic
similarity. In Proceedings of NAACL 2001: 2nd Meeting of the North American
Chapter of the Association for Computational Linguistics, pages 103{110, 2001.
[Kondrak, 2001b] Grzegorz Kondrak. Review of Brett Kessler's The signi cance ofworld lists. Computational Linguistics, 27:588{591, 2001.
[Kondrak, 2002] Grzegorz Kondrak. Determining recurrent sound correspondences by
inducing translation models. In Proceedings of COLING 2002: 19th International
Conference on Computational Linguistics, 2002. To appear.
[Kruskal, 1983] Joseph B. Kruskal. An overview of sequence comparison. In DavidSanko and Joseph B. Kruskal, editors, Time warps, string edits, and macromolecules: the theory and practice of sequence comparison, pages 1{44. Reading,
Mass.: Addison-Wesley, 1983.

Bibliography

166[Ladefoged, 1995] Peter Ladefoged. A Course in Phonetics. New York: Harcourt
Brace Jovanovich, 1995.
[Leacock and Chodorow, 1998] Claudia Leacock and Martin Chodorow. Combining
local context and WordNet similarity for word sense identi cation. In Christiane
Fellbaum, editor, WordNet: an electronic lexical database, pages 265{283. The MIT
Press, Cambridge, MA, 1998.
[Lin, 1998] Dekang Lin. An information-theoretic de nition of similarity. In Proceedings of the 15th International Conference on Machine Learning, pages 296{304,1998.
[Lowe and Mazaudon, 1994] John B. Lowe and Martine Mazaudon. The reconstruction engine: a computer implementation of the comparative method. Computational Linguistics, 20:381{417, 1994.
[Lowrance and Wagner, 1975] Roy Lowrance and Robert A. Wagner. An extension of
the string-to-string correction problem. Journal of the Association for Computing
Machinery, 22:177{183, 1975.
[Mann and Yarowsky, 2001] Gideon S. Mann and David Yarowsky. Multipath translation lexicon induction via bridge languages. In Proceedings of NAACL 2001:
2nd Meeting of the North American Chapter of the Association for Computational
Linguistics, pages 151{158, 2001.

[McEnery and Oakes, 1996] Tony McEnery and Michael Oakes. Sentence and wordalignment in the CRATER Project. In J. Thomas and M. Short, editors, Using
Corpora for Language Research, pages 211{231. Longman, 1996.
[Melamed, 1997] I. Dan Melamed. Automatic discovery of non-compositional compounds in parallel data. In Proceedings of the Second Conference on Empirical
Methods in Natural Language Processing, pages 97{108, 1997.
[Melamed, 1999] I. Dan Melamed. Bitext maps and alignment via pattern recognition. Computational Linguistics, 25(1):107{130, 1999.

Bibliography

167[Melamed, 2000] I. Dan Melamed. Models of translational equivalence among words.
Computational Linguistics, 26(2):221{249, 2000.
[Myers, 1995] Eugene W. Myers. Seeing conserved signals. In Eric S. Lander andMichael S. Waterman, editors, Calculating the Secrets of Life, pages 56{89. Washington, D.C.: National Academy Press, 1995.
[Nerbonne and Heeringa, 1997] John Nerbonne and Wilbert Heeringa. Measuring
dialect distance phonetically. In Proceedings of SIGPHON-97: 3rd Meeting of
the ACL Special Interest Group in Computational Phonology, 1997. Available at
http://www.cogsci.ed.ac.uk/sigphon.
[Nerbonne et al., 1996] John Nerbonne, Wilbert Heeringa, Erik van den Hout, Petervan der Kooi, Simone Otten, and Willem van de Vis. Phonetic distance between
Dutch dialects. In G. Durieux, W. Daelemans, and S. Gillis, editors, CLIN VI:
Proceedings of the Sixth CLIN Meeting, pages 185{202, Antwerp, Centre for Dutch
Language and Speech (UIA), 1996.
[Nerbonne et al., 1999] John Nerbonne, Wilbert Heeringa, and Peter Kleiweg. Editdistance and dialect proximity. In David Sanko and Joseph B. Kruskal, editors,

Time warps, string edits, and macromolecules: the theory and practice of sequencecomparison, pages v{xv. Stanford: CSLI Publications, 1999.

[Oakes, 2000] Michael P. Oakes. Computer estimation of vocabulary in protolanguage
from word lists in four daughter languages. Journal of Quantitative Linguistics,
7(3):233{243, 2000.
[Oommen and Loke, 1997] B. J. Oommen and R. K. S. Loke. Pattern recognitionof strings with substitutions, insertions, deletions and generalized transpositions.
Pattern Recognition, 30(5):789{800, 1997.
[Oommen, 1995] B. John Oommen. String alignment with substitution, insertion,
deletion, squashing, and expansion operations. Information Sciences, 83:89{107,1995.

Bibliography

168[Oswalt, 1998] Robert L. Oswalt. A probabilistic evaluation of North Eurasiatic Nostratic. In Joseph C. Salmons and Brian D. Joseph, editors, Nostratic: sifting theevidence, pages 199{216. Amsterdam: John Benjamins, 1998.
[Raman et al., 1997] Anand Raman, John Newman, and Jon Patrick. A complexity
measure for diachronic chinese phonology. In Proceedings of SIGPHON-97: Third
Meeting of the ACL Special Interest Group in Computational Phonology, 1997.
[Remmel, 1979] Mart Remmel. Computer techniques in Balto-Finnic historical phonetics. Technical Report Preprint KKI{11, Academy of Sciences of the Estonian
S.S.R., 1979.
[Remmel, 1980] Mart Remmel. Computers in the historical phonetics and phonology
of Balto-Finnic languages: problems and perspectives. Technical Report Preprint
KKI{14, Academy of Sciences of the Estonian S.S.R., 1980.
[Rennie, 1999] Jason Rennie. Wordnet::QueryData Perl module, 1999. Available at
http://www.ai.mit.edu/jrennie.
[Resnik, 1999] Philip Resnik. Semantic similarity in a taxonomy: An informationbased measure and its application to problems of ambiguity in natural language.
Journal of Arti cial Intelligence Research, 11:95{130, 1999.
[Ringe, 1992] Don Ringe. On calculating the factor of chance in language comparison.
Transactions of the American Philosophical Society, 82(1), 1992.
[Ringe, 1998] Don Ringe. Probabilistic evidence for Indo-Uralic. In Joseph C.
Salmons and Brian D. Joseph, editors, Nostratic: sifting the evidence, pages 153{
197. Amsterdam: John Benjamins, 1998.
[Simard et al., 1992] Michel Simard, George F. Foster, and Pierre Isabelle. Using
cognates to align sentences in bilingual corpora. In Proceedings of the Fourth International Conference on Theoretical and Methodological Issues in Machine Translation, pages 67{81, Montreal, Canada, 1992.

[Smith and Waterman, 1981] T. F. Smith and Michael S. Waterman. Identi cationof common molecular sequences. Journal of Molecular Biology, 147:195{197, 1981.

Bibliography

169[Smith, 1969] Raoul N. Smith. A computer simulation of phonological change. ITL:
Tijdschrift voor Toegepaste Linguistiek, 1(5):82{91, 1969.
[Somers, 1998] Harold L. Somers. Similarity metrics for aligning children's articulation data. In Proceedings of COLING-ACL'98: 36th Annual Meeting of the
Association for Computational Linguistics and 17th International Conference on
Computational Linguistics, pages 1227{1231, 1998.

[Somers, 1999] Harold L. Somers. Aligning phonetic segments for children's articulation assessment. Computational Linguistics, 25(2):267{275, 1999.
[Somers, 2000] Harold L. Somers. Personal communication, 2000.
[Swadesh, 1952] Morris Swadesh. Lexico-statistical dating of prehistoric ethnic contacts. Proceedings of the American Philosophical Society, 96:452{463, 1952.
[Tiedemann, 1999] Jorg Tiedemann. Automatic construction of weighted string similarity measures. In Proceedings of the Joint SIGDAT Conference on Empirical
Methods in Natural Language Processing and Very Large Corpora, College Park,
Maryland, 1999.
[Trask, 1996] R. L. Trask. Historical Linguistics. London: Arnold, 1996.
[Vossen, 1998] Piek Vossen, editor. EuroWordNet: a Multilingual Database with Lexical Semantic Networks. Kluwer Academic, Dordrecht, 1998.
[Wagner and Fischer, 1974] Robert A. Wagner and Michael J. Fischer. The stringto-string correction problem. Journal of the Association for Computing Machinery,21(1):168{173, 1974.