Unsupervised Syllable Modeling for Spell Checking 1 Preliminaries
- 格式：pdf
- 大小：105.00 KB
- 文档页数：10
Unsupervised Syllable Modeling for SpellCheckingHarald Hammarstr¨o mJanuary9,20061PreliminariesThere has been some work on unsupervised syllable modeling(M¨u ller2002; Cuay´a huitl2004;Lee,Lee,and Cha2002;Martens,Daelemans,Gillis,and Taelman2002;Goldwater and Johnson2005;Kiraz and M¨o bius1998;M¨u ller 2001a;M¨u ller2001b)but1)not with the approach and scope intended here, and to the best of my knowledge,2)not used for spell checking.I aim to investigate if a crude unsupervised syllable modeling strategy can do some decent spell checking(on its own).For clarity,the following considerations are beyond the scope of this study:•a realistic model of phonological changes in syllable boundaries•evaluation on real spell-unchecked corpora,since I lack these resources.•evaluation of the syllable model on a syllable gold standard,since I lack such resources.•evaluation of what use a syllable theory can be for spell checking,again, since I don’t have a syllable gold standard for any language whatsoever.•a integration of syllable modeling and some other heuristic for spell checking(such as word frequency).12Syllable ModelI shall now describe an algorithm for syllable extraction from unlabeled cor-pus data.Unfortunately,parts of it is not well-understood and there is no information theoretic theory or the like behind it,but at least it produces results that look intuitively interesting.I will use the following notation and terminology:•A word is a non-empty character string•f(w):the frequency of the word w in the input corpus•W:the set(not bag!)of words in the input corpusFor a string w=c1c2...c n of characters and1≤i<j≤n:•w[i:j]is the substring c i c i+1...c j•#(w,s):the number of times the substring s occurs in the word w,i.e|{(i,j)|s=w[i:j]}|•#W(s):the number of times the substring s occurs in the set of wordsW,i.e w∈W#(w,s)As a running example,we will use a corpus of the bible(Old and New Testament)in English.It consists of917634word tokens,28lowercase char-acters and|W|=12999.1.Build Segmentation Preferences:Build the set of segments S={s|#W(s)>0}.For each s∈S calculate its left and right segmentation preferenceas:L(s)=s ∈{cs∈W|1=|c|}s sR(s)=s ∈{sc∈W|1=|c|}s sThe segmentation preference of a segment is then:Z(s)=L(s)+R(s)if R(s)>0or L(s)>0 f(s)otherwiseIn our example corpus|S|=101328.22.Rescale Segmentation Scores:The Z-score reflects some kind of seg-mentation preference between segments of the same length,but there is a need for an additional bias to compare segments of different length, since shorter segments occur frequently by chance rather than status as syllables.Something that works decently(and not just a for one or two typologically similar languages)is to simply rescale the Z-score of each segment by the square length of the segment.Here we have chosen,after some ad-hoc experimentation,a more complicated rescale measure that grows exponentially up to a mean length of syllables(in reality)and then decreses approaches zero linearly(p=3and b=25):Z(s)=Z(s)·b|s|−1if|s|≤p Z(s)·b p−1·1|s|−p+1otherwise3.Greedy Parse to Collect Syllables:We can now define an optimalsyllable parse of a word as:P S(w)=argmax[si∈S]:s1s2...s n=w1≤i≤nZ(s i)Unfortunately,the number of segmentations of a word w(which is what the argmax in the formula is quantifying over)is exponential in|w|and, even though words are usually tractably long,in practice full syllable parsing of13000words takes too long.In contrast,the greedy parse only takes O(|w|2)time:P S(w)=[argmax[s∈S]:sx=w Z(s)]+[P S(x)]but is not guaranteed to produce an optimal parse.However,it seems to yield“close enough”results and can parse13000words in notime, so we will stick to it for the rest of the experiment.For example,10(randomly selected)examples of segmentation are given below:3w P S(w) s∈P S(w)Z(s)giddel[’gid’,’del’]252553.693362writings[’writ’,’ings’]3630599.912121hordes[’hor’,’des’]772596.989309foul[’fo’,’ul’]136836.373343four[’four’]366863.106101prices[’pric’,’es’]516183.798198aijalon[’ai’,’ja’,’lon’]447247.182467exorcists[’ex’,’or’,’cis’,’ts’]204158.439917hanging[’hang’,’ing’]3877691.641140deserveth[’de’,’serv’,’eth’]4993107.246895cyprus[’cy’,’p’,’rus’]310484.556484Parsing all the words in W reveals that we do not use all segments in S.Define the syllable collection of a set of words W as:C(W)={s|s∈P S(w)for some w∈W}In our example corpus|C(W)|=4571.In the next phase,we shall actually purge the remaining list of syllables further using the fact that some syllables in C(W)are more frequent in the greedy parsing of W. Denote the number of times a syllable s occurs in the greedy parse of W as#P(s).As an example,the top10and bottom10(in terms of #P)of C(W)is shown below:4s#P(s)ing742eth709ed412est327es254ers229ess224th196re189st180......stay1uba1stan1stal1humbl1asht1trimm1oram1smot1tten14.Purge Syllable Collection:In order to make the syllable collectionmore predictive,we need to purge it even further;the4571segments in C(W)can concatenate to describe pretty much any string and can thus hardly serve for spell checking.We propose the following purging formula:For every set s i∈C(W)such that s1,s2,...,s n−1=s n,remove the s i with minimum#P(s i).A list of s i to be removed is compiled from one instance of C(W)–members are not removed incrementally.The search for satisfying instances is doable in practice since,in contrast to words,most syllables are relatively short.In our running test corpus,1227syllables remain after purging.It is instructive to look at the lengths of the remaining syllables because it5reveals that no syllables of length1remain!#characters#syllables21213357458051596872For clarity,the set of syllables remaining after this purge step is the final product to be used for spell checking and will be denoted S.3Spell Checking ModelIt is very straightfoward to decide whether a word is correctly spelled accord-ing to the model,i.e a set of syllables S:A word w is correctly spelled iffit is in S+For a set of words X denote the subset of it which the model thinks is in correctly spelled by D(X)={w∈X|w/∈S+}.4EvaluationThe spell checking model will be evaluated onfive typologically diverse lan-guages using the bible corpora.I will introduce artificial errors in the word set of each language(a la(Bigert2005)and predecessors cited therein)and then measure precision and recall over the resulting union of the true set of words and the error-prone set.To be more precise,for each language:•A percentage p=5%,10%,15%,20%of W will be chosen for error introduction•Each chosen word will be given one random transposition of adjacent characters resulting in a set of transposited words W•The algorithm will have to classify all words W∪W .E will be used to denote the set E=(W∪W )\W.6•Precision:|D(W∪W )∩E||D(W∪W )|•Recall:|D(W∪W )∩E||E|A few comments are in order.•I haven’t used Misplel because I’d have to supply the error percentages myself anyway(it would be nice if such a tool supplied some“default”realistic error percentages)and I have my doubts as to how language dependent it is.On the other hand,my error introduction,which pays no attention to keyboard layout is unrealistic too since keyboard layout as of today is very language independent.•If W ∩W=∅it simply means that the“real”W i.e E is slightly smaller.I don’t know how to get around this problem without intro-ducing other problems.5ResultsFirst we give some reference data on the bible corpora used:Language#Tokens|W||S|English917634129991227Swedish784533268332251Maori110166590891265Turkish574592571902081Greenlandic4706001141721834The precision and recallfigures are shown in Figures1and2.Since the results are rather poor,we believe this study provides no valu-able insights to the spell checking(or syllable modeling)problem.The out-come syllable model obviously has poor predictive power,it is too restrictive, wherefore this study should not be taken to show that syllable modeling has nothing to offer spell checking.A good syllable model still might.If one still wants to pursue the direction of unsupervised syllable modeling(for spell checking)I believe one needs some kind of sonority constraints baked into the syllable structure(a sonority hierarchy could still conceivably be read offan unlabeled corpus).7Figure1:Precisionfigures for p=0.05,0.10,0.15,0.20. ReferencesBigert,J.(2005).Automatic and Unsupervised Methods in Natural Lan-guage Processing.Ph.D.thesis,Royal Institute of Technology,Stock-holm.Cuay´a huitl,H.(2004).A syllabification algorithm for spanish.In A.Gel-bukh(Ed.),Computational Linguistics and Intelligent Text Processing: 5th International Conference,CICLing2004Seoul,Korea,February 15-21,2004Proceedings,Volume2945of Lecture Notes in Computer Science,pp.412–415.Springer-Verlag,Berlin.Goldwater,S.and M.Johnson(2005).Representational bias in unsuper-vised learning of syllable structure.In Proceedings of the9th Conference on Computational Natural Language Learning(CoNLL),Ann Arbor, June2005,pp.112–119.Kiraz,G.A.and B.M¨o bius(1998).Multilingual syllabification using weightedfinite-state transducers.In Proceedings of the Third European8Figure2:Recallfigures for p=0.05,0.10,0.15,0.20.Speech Communication Association Workshop on Speech Synthesis. Lee,G.G.,J.-H.Lee,and J.Cha(2002).Syllable-pattern-based unknown-morpheme segmentation and estimation for hybrid part-of-speech tag-ging of put.Linguist.28(1),53–70.Martens,E.,W.Daelemans,S.Gillis,and H.Taelman(2002).Where do syllables come from?In W.Gray and C.Schunn(Eds.),Proceedings of the Twenty-Fourth Annual Conference of the Cognitive Science Society, Fairfax,Virginia,pp.637–644.George Mason University.M¨u ller,K.(2001a).Automatic detection of syllable boundaries combining the advantages of treebank and bracketed corpora training.In Proceed-ings of the39th Annual Meeting of the Association for Computational Linguistics(ACL2001),Toulouse,France.M¨u ller,K.(2001b).Probabilistic context-free grammars for syllabification and grapheme-to-phoneme conversion.In Proceedings of the Conference on Empirical Methods in Natural Language Processing(EMNLP2001), Pittsburgh(PA).9M¨u ller,K.(2002).Probabilistic Syllable Modeling Using Unsupervised and Supervised Learning Methods.PhD thesis,University of Stuttgart,In-stitute of Natural Language Processing(IMS),Stuttgart.10。
