Background
Detecting Transliterated
Orthographic Variants
via Two Similarity Metrics
Kiyonori Ohtake† , Youichi Sekiguchi‡ andKazuhide Yamamoto‡† ATR Spoken Language Translation Research Laboratories, Japan‡ Nagaoka University of Technology, Japan
August 24, 2004

Huge corpora are available
Corpus-based Natural Language
Processing
Orthographic variants cause problems:mismatch at looking up a dictionary
raise perplexity
etc.

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 1

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 2

Objectives
To detect transliterated orthographicvariants in a corpus.
To detect mis-typed words in a corpus.

Transliterated variants

English word:
TransliteratedJapanese

reportrepootoripootoNot only Japanese; e.g., in English,
Chinese proper noun: Shanhaiguan,
Shanhaikwan, or Shanhaikuan
Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 3

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 4

Approaches
Rule-based
high accuracy, weak at irregularvariants
Back-transliteration
very difficult
Approximate string matchingrobust, but not accurate

Approaches
Rule-based
high accuracy, weak at irregularvariants
Back-transliteration
very difficult
Approximate string matching[Take!]
Enhancements for high accuracy:
extend edit distanceuse contextual information

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 5

Katakana transliteration
approximate pronunciation
there is no specific guideline
several source languagese.g., English word virus
uirusu (Latin) ↔ viirusu (German)
sometimes transliterated from its
spelling
There is considerable variation.

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 5

Overview of detecting method
CorpusKatakana
words
ripootorepootouirusuviirusu. . .

analyze

Dependency
Analyzed
Corpusextract

Contextual
Vectorsvec( ripooto )vec( repooto)
stringuirusu ) contextual
similarity vec(similarityvec( viirusu ). . .

score > threshold ?
detected variant: ripooto

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 6

repootoDetecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 7

Overview of detecting method
CorpusKatakana
words
ripootorepootouirusuviirusu. . .

analyze

Dependency
Analyzed
Corpusextract

Contextual
Vectorsvec( ripooto )vec( repooto)
stringuirusu ) contextual
similarity vec(similarityvec( viirusu ). . .

String similarity
Input: katakana words w1 and w2
S1 [1..m], S2 [1..n]: romanized strings for w1
and w2
Sims (w1 , w2 ) = 1 −EDk (S1 , S2)
m+n

EDk (S1 , S2 ) = D(m, n)score > threshold ?
detected variant: ripooto

repootoDetecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 7

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 8

Edit distance for katakanaD(i − 1, j) + id(i, j),D(i, j) = min  D(i − 1, j − 1) + 2t(i, j),  ,D(i, j − 1) + id(i, j)

where t(i, j) = 0 if S1(i) = S2(j); otherwise
the value follows t(i, j)-table,and id(i, j) follows id(i, j)-table thatassigns an insertion-deletion distance.
Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 9

id(i, j)-tablesimilar to t(i, j)-table (13 rules)
Some characters easily inserted anddeleted in particular context → relax
For example:
English word decanter
dekyantaa ↔ dekantaat(i, j)-table
rules for katakana matching (20 rules)
i−3

i−2

i−1

i

i+1

i+2

i+3

j−3

j−2

j−1

j

j+1

j+2

j+3

∗

∗

t[ou]u∗∗∗∗t[ou]u∗∗t(i, j)0.4∗∗[dz]i∗∗
0.25∗∗∗[dz]i∗∗‘∗’ means any character.
‘[ ]’ means character class in a regular expression.
∗Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 10

Contextual similarity
given by inner product of two vectors:
simc (kwi , kwj ) = cos(vec(kwi ), vec(kwj )),where vec(kwi) is the contextual vector
that corresponds to the katakana word
kwi.

Consonant insertion-deletion → penalize

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 11

Contextual vector
syanpen ogurasu dekudasai(basic form is kudasaru)(A glass of champagne, please.)vec(syanpen) =[N;gurasu:1, P;kudasaru:1,PP;o-kudasaru:1]
vec(gurasu) =[N;syanpen:1, P;kudasaru:1,PP;de-kudasaru:1]

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 13

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 12

Weighting element of vector
frequently appear 6= important
There are words
co-occur with many other words,
co-occur with a specific word.
Load tf-idf-like weight onto each elementof the contextual vector.

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 14

ExperimentHow to decide a variant
follows a decision list considering thefollowing points:

Corpus: ATR Basic Travel Expression
Corpus [200k sentences]160k: used for parameter estimation,and verification of rules
40k: used as a test set

lengthfrequency in the corpus
string similarity with ordinal edit distanceConditions:string similarity with edit distance for katakana words

Dictionary (8k entries): use / not use
Contextual similarity: use / not use

contextual similarity
dictionary (almost 8,000 entries)

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 15

Experimental result
Dic. Context
yes

RecallPrecision

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 16

Discussion
F

yes

0.827 (62/75) 0.886 (62/70) 0.855

yes

no0.907 (68/75) 0.872 (68/78) 0.889

no

yes

0.800 (60/75) 0.822 (60/73) 0.811

nono

0.880 (66/75) 0.725 (66/91) 0.795

Dictionary: recall ↑ precision ↑Contextual similarity: recall ↓precision ↑dictionary helped detection for shortwords and proper nounssome mis-types were detected;
e.g., buraun’ ↔ buran’ (brown)
contextual similarity caused side effectdata sparseness→ statistical approach may be unfit forvariants detection

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 17

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 18

Future works

Conclusions

To automate estimation of parametersmodified edit distance for katakana
words
contextual similarity didn’t work with
ATR corpus
dictionary worked very well

To use large dictionary (e.g., morethan 100k entries)
To detect other types of variante.g., cross-script orthographic variants(kanji vs. hiragana vs. katakana)

performed almost 90% in F-measureDetecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 19

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 20

ErrataFormulas (1) and (2) (pages 711 & 712, Sections 3and 3.1)

Thank you very much.

2ED → ED
Formula (5) (p. 713, Section 3)
W (kwi , ei ) = f (kwi , ei )logN
sf (kwi )Parameter (p. 713, Section 4, 2nd paragraph)
T Hst1 = 9.4 → T Hst1 = 0.94
Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 21

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 22

Appendix - weighting element of vector
Very simple tf-idf like weightingN
W (kwi , ei) = f (kwi, ei) log
sf (kwi )kwi : katakana wordei : element of a vectorf (kwi , ei ): frequency of ei which is a element of kwi -vector
N : # of katakana words in the corpus
sf (kwi ): sentence frequency which includes kwi

Appendix - Decision list
lengthfrequency

simedsims

simc> T Hlen∗> T Hed1> T Hst1∗

variant<= T Hlen> T Hf req∗∗

< T Hcos1

not variant< T Hlen∗∗∗> T Hcos2

variant

Both words have entries in pre-defined dictionary∗∗> T Hed2

decision

not variant> T Hst2∗variant∗∗

not variant∗∗∗‘∗’ means any conditions.

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 23

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 24

Appendix - dictionary impactAppendix - closed test

F-measureDic. Con.

10.90.8
with dictionary

0.7

without dictionary

RecallPrecisionF

yes

yes0.820 (296/361) 0.931 (296/318) 0.872

yes

no0.850 (307/361) 0.930 (307/330) 0.889

no

yes

0.823 (297/361) 0.903 (297/329) 0.861

nono0.850 (307/361) 0.862 (307/356) 0.856

0.6
0.5

246810
word length1214
Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 26

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 25

Appendix - detected examples
successfully detectedaisyadoo - aisyadou (eye shadow)
pikurusu - pikkuruzu (pickles)
mis-detectedmari (Mari) - marii (Mary )maaton (Murton) - maton (mutton)

Appendix - Dictionary sample@aisyeedo@@aisyadoo@@aisyadou@...
@uirusu@@biirusu@@viirusu@...
...
@syunookeru@@sunookeru@...

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 27

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 28

Appendix - trick at t(i, j)

Appendix - trick at t(i, j)English word: simulate

English word: simulatesimyureeto

M

SSSS

M

M

M

M

Msyumireetosimyureeto

M RRRR

M

M

M

M

Msu

mireetoy

M=0
S=2
ED=8simyureeto

M

S

R

S

S

M

M

M

M

M

M=0
S=2
R=-2syumireetoED k =4

R=1
ED k =4

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 29

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 29

Transliteration for foreign words
3 types of Japanese characters:
hiragana and katakana → syllabaryand kanji (Chinese character)
Katakana: used to transliterate foreignwords

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 30

Appendix - Romanization
Katakana corresponds to one or twophonemes
We use romanization to capture
pronunciation and to make matchingrules simple.

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 31

Overview of contextual vector

Using dictionary

Context: a sentence
What nouns co-occur
How to depend a verb, and what verbs
are depended
Construct contextual vector by using adependency analyzer

We have already known
the words that are not similar, but they
are variants, andthe words that are very similar, butthey are not variants.

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 32↓
A dictionary will help detecting variants.

Detecting Transliterated Orthographic Variantsvia Two Similarity Metrics – p. 33