信息检索导论汉字加工

信息检索导论汉字加工

ChineseProcessing1SoFarWhatWeHaveDocumentSimilarity"aBagofWords"Model+TermWeighting(TF-IDF)VectorSpaceModel(VSM)Co-occurrenceAssociationLinkanalysis:Co-citation&CouplingClassificationNaïveBayeskNearestNeighborsSupportVectorMachineProblemsinChinese

Processing"小明日记：今日王叔叔来我家玩妈妈，说我做完作业后，可以吃点心。然后，王叔叔夸我作业做的好，于是抱起了我妈，妈叫叔叔小心一点，之后叔叔又亲了我妈妈，也亲了我。""老师批复：拿回家让你爸看看，是标点符号有问题，还是你王叔叔和你妈妈有问题。"3ProblemsinChinese

Processing新词(out-of-vocabulary,OOV)九把刀拍了部新电影叫等一个人咖啡断词(termsegmentation)消除歧义我国代表现在正面临很大的压力全台大停电不可以营利为目的他才能非凡；他才能胜任4What’stheDifferenceinChinese?AlgorithmsinEnglisharebasedin“Term”

前述主要算法均基于词做运算Document→Paragraph→Sentence→TermSomeexpandtoPhrase有些扩充至词组Somechangeton-gram有些改用n-gramThemajordifferenceinChineseCharacterrangespaceismuchlarger

中文字符个数远多过于其它语言Noobviousboundarybetweencharacters/terms.

中文字或词之间无明显分隔符What’stheDifferenceinChinese?中文英文单位字(元)

Character词词组句子段落文件字母Letter字Word词组Phrase句子Sentence段落Paragraph文件Document统计资料BIG5:常用字约5000个,次常用字约8000个Unicode:约4万个汉字注音:共376个音(不含四声变化)CKIP:二字以上约13万词

WebsterDictionary:470,000ProbleminChineseProcessing(1)TermSegmentation断词(i.e.抢词问题)Example

我国代表现在正面临很大的压力

我到达文西博物馆Solution 1.字典法：例如长词优先法 2.法则式：例如文法式、构词法则、歧义解决法则 3.训练统计式：例如词频法(最大词频组合)等 4.自动分类式：将断词转为分类问题Result

现今主要第3,4类方法,正确率可达9成以上ProbleminChineseProcessing(2)Part-of-SpeechTagging词性标定Example

我国代表现在正面临很大的压力NcNaNdNeqbNvDfaNaNaNaVCNaVKNvTVK NvVADeVCVHDiVHVJAADDa N…名词V….动词D…副词A形容词T语助词ProbleminChineseProcessing(2)Part-of-SpeechTagging词性标定Solution 1.训练统计式：

例如马可夫机率模型 2.自动分类式：

将词性标定转为分类问题Result

正确率可达9成以上

可衍生出许多应用表：中研院平衡语料库词类标记ProbleminChineseProcessing(3)UnknownTerm未知词(或称Out-of-Vocabulary)Example

新鲜人倪安东见面签唱会歌迷热情喊冻蒜

国际运动仲裁庭祕书长瑞伯表示世跆盟可拒仲裁Solution 1.先经过断词，再处理未知部份

未知部份以构词法则处理，或n-gram统计学习 2.不经过断词，直接以训练统计式处理

Result

正确率可达7~8成(含词性标定)ToolforChineseProcessing(1)Yahoo断章取义API /cas/取得应用程序账号使用API(目前停用)断词与词性标注文章关键字撷取ToolforChineseProcessing(2)eLandETool开放完整API主要功能自动关键词自动摘要断词与词性标定情绪判定试用展示自动关键字以n-gram，找出最长且最常结伴出现的字符串需指定所谓“最常出现”的次数门槛值以BACDBCDABACD为例设定thresholdT＝1

FinalList会得到CD：3BACD：2代表撷取出两个关键字

自动摘要重新组合重要的句子“句子”作为单位以关键词计算每个句子的得分由句子得分筛选固定比例的句子作为文章摘要HMM断词HiddenMarkovModel统计式的模型序列资料的描述S0S0S1S2GaussiandistributionOtOt-1Ot+1Ot+2(State)(ObservationValue)S0S1S2S0P00P01P02S1P10P11P12S2P20P21P22TransitionProb.ObservationProb.HMM断词中文断词的应用Ex.

缺乏(V)耐性(N)是(SHI)一(N)项(N)莫大(A)的(D)致命伤(N)S0S0S1S2OtOt-1Ot+1Ot+2State:词性ObservationValue：词VNSHIN缺乏耐性是一HMM断词中文断词的应用取得机率最高的路径VNA..…………缺乏耐性……………情绪判别Abag-of-words上好一流公道引人入胜方便主流叫好卓越…引诱太过出错失常白目丢脸劣质…PositiveTermsNegativeTermsOkapiBM25termsetdocumentavg.documentlengthdocumentlength情绪判别AssociateAttitude建立关联态度词库服务傲慢(-1.0)亲切(1.0)周全(1.0)敷衍(-1.0)…这家代理商的服务一点也不周全…态度反转…这家代理商的服务一点也不周全……这家代理商的服务一点也不周全…Discussions20Hsin-HsiChen9-21ChineseTextRetrievalwithoutUsingaDictionary(Chenetal,SIGIR97)SegmentationBreakastringofcharactersintowordsChinesecharactersandwordsMostChinesewordsconsistoftwocharacters(赵元任)26.7%unigrams,69.8%bigrams,2.7%trigrams

(北京，現代漢語頻率辭典)5%unigrams,75%bigrams,14%trigrams,6%others(Liu)Wordsegmentationstatisticalmethods,e.g.,mutualinformationstatisticsrule-basedmethods,e.g.,morphologicalrules,longest-matchrules,...hybridmethodsHsin-HsiChen9-22IndexingTechniquesUnigramIndexingBreakasequenceofChinesecharactersintoindividualones.Regardeachindividualcharacterasanindexingunit.GB2312-80:6763charactersBigramIndexingRegardalladjacentpairsofhanzicharactersintextasindexingterms.TrigramIndexingRegardalltheconsecutivesequenceofthreehanzicharactersasindexingterms.Hsin-HsiChen9-23ExamplesHsin-HsiChen9-24IndexingTechniques(Continued)StatisticalIndexingCollectoccurrencefrequencyinthecollectionforallChinesecharactersoccurringatleastonceinthecollection.CollectoccurrencefrequencyinthecollectionforallChinesebigramsoccurringatleaseonceinthecollection.ComputethemutualinformationforallChinesebigrams.

I(x,y)=log2(p(x,y)/(p(x)*p(y)))

=log2((f(x,y)/N)/((f(x)/N)*(f(y)/N)))

=log2((f(x,y)*N)/(f(x)*f(y)))Stronglyrelated:muchlargervalueNotrelated:closeto0Negativelyrelated:negative

I(x,y)=log2(p(x,y)/(p(x)*p(y)))

=log2(p(x)/(p(x)*p(y))

=log2(1/*p(y))I(x,y)=log2(p(x,y)/(p(x)*p(y)))

=log2(p(x|y)/p(x))

=log2(p(x|y)/p(x))=0Hsin-HsiChen9-25f(c1):theoccurrencefrequencyvalueofthefirstChinesecharacterofabigramf(c2):theoccurrencefrequencyvalueofthesecondChinesecharacterf(c1c2):theoccurrencefrequencyvalueofabigramI(c1,c2):mutualinformation

I(c1,c2)>>0,c1andc2havestrongrelationship

I(c1,c2)~0,c1andc2havenorelationship

I(c1,c2)<<0,c1andc2havecomplementraryrelationship>0<0Hsin-HsiChen9-26352974671SegmentationasClassification我国代表现在正面临很大的压力

B

E

B

E

B

E

S

B

E

B

E

S

B

E九把刀不同意BIESBE28Trainingdata:inputfeaturesandthetargetC-2T-2C-1T-1C1T1C2T2C0T0目标栏位我B国E表E现B代B国E代B现B在E表E…from"ChineseWordSegmentationbyClassificationofCharacters",2005Appendix:

OtherLanguageIssues杨立伟教授wyang@.tw31TokenizationInput:“Friends,RomansandCountrymen”Output:TokensFriendsRomansCountrymenEachsuchtokenisnowacandidateforfurtherprocessing正規化及語言處理在此一階段就直接丟棄(保留)哪些信息？索引与查询(分析)时的处理要一致TokenizationIssuesintokenization:Finland’scapitalFinland?Finlands?Finland’s?Hewlett-Packard

HewlettandPackardastwotokens?SanFrancisco:onetokenortwo?Howdoyoudecideitisonetoken?Numbers3/12/91 Mar.12,199155B.C.B-52MyPGPkeyis324a3df234cb23e44Often,don’tindexastext.Butoftenveryusefulmixedwithtext:ex.产品型号NikonD700(Oneanswerisusingn-grams)Tokenization:LanguageissuesL'ensemble

onetokenortwo?L?L’?Le?Wantl’ensembletomatchwithunensembleGermannouncompoundsarenotsegmentedLebensversicherungsgesellschaftsangestellter‘lifeinsurancecompanyemployee’Tokenization:languageissuesChineseandJapanesehavenospacesbetweenwords:莎拉波娃现在居住在美国东南部的佛罗里达。NotalwaysguaranteedauniquetokenizationFurthercomplicatedinJapanese,withmultiplealphabetsintermingled混合使用Dates/amountsinmultipleformatsフォーチュン500社は情报不足のため时间あた$500K(约6,000万円)Katakana片假名Hiragana平假名Kanji汉字Romaji罗马拼音断词问题NormalizationNeedto“normalize”termsinindexedtextaswellasquerytermsintothesameformWewanttomatchU.S.A.andUSA索引与查询(分析)时的处理要一致Alternativeistohavemultipletokenizationmixedlanguageprocessingandn-gramapproachNormalization:otherlanguagesAccents:résumévs.resume.Mostimportantcriterion:Eveninlanguagesthatstandardlyhaveaccents,usersoftenmaynottypethemHowwouldyouliketopresentinthefinalresult?German:Tuebingenvs.TübingenShouldbeequivalent7月30日vs.7/30CasefoldingReduceallletterstolowercaseexception:uppercase(inmid-sentence?)e.g.,GeneralMotorsFedvs.fedSAILvs.sailOneapproachistolowercaseeverythinginanalysis,meanwhiletorepresentintheoriginalformStopwordsWithastoplist,youexcludefromdictionaryentirelythecommonestwords.Intuition:Theyhavelittlesemanticcontent:the,a,and,to,beTheytakealotofspace:~30%ofpostingsfortop30Butthetrendisawayfromdoingthis:Youneedthemfor:Phrasequeries:“KingofDenmark”Varioussongtitles,etc.:“Letitbe”,“Tobeornottobe”“Relational”queries:“flightstoLondon”ThesauriandsoundexHandlesynonyms同义字andhomonyms同音字Hand-constructedequivalenceclassese.g.,car=automobilecolor=colourRewritetoformequivalenceclasses原则：两种方式，在索引时处理？或在查询时处理？(1)IndexsuchequivalencesEx.Whenthedocumentcontainsautomobile,indexitundercaraswell(usually,alsovice-versa)(2)expandqueryEx.Whenthequerycontainsautomobile,lookundercaraswellSoundexTraditionalclassofheuristicstoexpandaqueryintophoneticequivalentsLanguagespecific–mainlyfornamesE.g.,chebyshev

tchebycheffLemmatizationReduceinflectional/variantformstobaseformE.g.,am,are,

is

becar,cars,car's,cars'

cartheboy'scarsaredifferentcolors

theboycarbedifferentcolorLemmatizationimpliesdoing“proper”reductiontodictionaryheadwordformStemmingReducetermstotheir“roots”beforeindexing“Stemming”suggestcrudeaffixchopping很粗略地将字首字尾去除languagedependente.g.,automate(s),automatic,automationall