Semantyka języka naturalnego

Semantyka języka naturalnego

Skrt: wykady 7-11 i troch semantyki z wykadu 6 Semantyka czyli znaczenie ustalenie co jest znaczeniem konkretnego wyraenia w jzyku naturalnym nazwy obiektw, relacji midzy nimi, ... sieci semantyczne wskazujce na hierarchi i pokrewiestwo terminw ustalenie sposobu reprezentowania znaczenia okrelenie niezbdnego zakresu wiedzy pragmatycznej okrelenie zasad wnioskowania warstwy problemu reprezentacja znaczenia : metoda zapisu potrzebnych informacji

wnioskowanie : uzyskiwanie nowych informacji z ju dostpnych analiza semantyczna : automatyczne generowanie zapisu znaczenia zda (rwnoczenie lub nie z analiz syntaktyczn) Reprezentacja znaczenia W jaki sposb mona reprezentowa semantyk jzyka naturalnego, czyli jakie mechanizmy formalne mona tym celu wykorzysta (zdefiniowa)? ... W praktyce moe to by cokolwiek, co odpowiada praktycznym potrzebom programu dokonujcego interpretacji semantycznej Kiedy potrzebna jest semantyka: odpowiedzi na pytania ustalenie, czy dane zdanie jest prawdziwe wnioskowanie, etc. Rachunek predykatw I rzdu Naturaln metod reprezentowania semantyki jest rachunek predykatw I rzdu

Nie jest to idealny sposb zapisu, nie pozwala na wyraenie wszystkich znacze, ale ma wiele waciwych cech: pozwala zapisa czy jaki fakt jest prawdziwy czy faszywy pozwala zapisywa pytania (uycie zmiennych) s metody wnioskowania Wybr rachunku pred. I rzdu nie jest cakowicie arbitralny czy sterowany konkretnymi aplikacjami. Mona zauway pewne analogie midzy jzykiem naturalnym a jzykiem rachunku predykatw. Cechy rachunku pred. I rzdu: wprowadzenie zmiennych, uycie kwantyfikatorw, czciowo kompozycyjna semantyka Struktura predykatowo-argumentowa Nawet do pobiena analiza wykazuje, e struktura predykatowo -argumentowa dobrze oddaje znaczenie wielu elementw jzyka naturalnego. W szczeglnoci niektre typy sw w atwy sposb mona przetumaczy na predykaty, podczas gdy inne peni funkcje ich argumentw: sowa kojarzone z predykatami: czasowniki (frazy czasownikowe), przyimki, przymiotniki,

niektre czasowniki sowa kojarzone z argumentami: rzeczowniki (frazy rzeczownikowe) Przykad zapisu znaczenia Reprezentacja rzeczownikw: - imiona wasne -> tumaczone na unikalne nazwy Jan -> Jan, Marii -> Maria (czsto to nie wystarcza) - rzeczowniki pospolite nie okrelaj konkretnego obiektu, ale pewien obiekt o jaki znanych cechach ksika -> x Isa(x, Book) Przykad zapisu znaczenia Przykad: Jan da Marii ksik. Tumaczenie bezporednie: Da(Jan, Maria, ksika) Lepsze (dokadniejsze) tumaczenie: (naley stosowa ten sposb) czasownik decyduje o nazwie predykatu, liczbie i roli jego argumentw, da oznacza wic: w,x,y,z Giving(x) Giver(w, x) Givee(y, x) Given(z, x)

dla powysszego zdania wic: x,y Giving(x) Giver(John, x) Givee(Mary, x) Given(y, x) Isa(y, Book) Rnica midzy zapisem rzeczownikw Jan i ksika to rnica interpretacji rzeczownikw wasnych i pospolitych Analiza semantyczna Analiza semantyczna to proces przeksztacenia wyraenia lingwistycznego w zapis jego znaczenia S miliony sposobw dokonania takiego przeksztacenia, od rozwiza cakowicie ad hoc, opracowanych na potrzeby konkretnych aplikacji do wyrafinowanych metod teoretycznych o czsto wtpliwym znaczeniu praktycznym Wikszo metod analizy semantycznej opiera si na wynikach analizy syntaktycznej (albo jest dokonywana rwnolegle z ni)

Semantyka kompozycyjna Wikszo metod zapisu znaczenia zakada KOMPOZYCYJNO semantyki, tzn. przyjmuje zaoenie, e znaczenie wikszych fragmentw teksu (zdania) moe zosta okrelona jako funkcja znacze jego elementw, czyli sw i fraz Na czy polega to w praktyce? Pokaemy na przykadzie zdania: (AyCaramba to nazwa restauracji (niewgetariaskiej)) AyCaramba serves meat Przykad AyCaramba serves meat S e Isa(e, Serving) Server(e, AyCaramba) Served(e, Meat) NP VP NP

Proper-Noun Verb AyCaramba serves Mass-Noun meat Rozszerzone reguy syntaktyczne Jak uzyska znaczenie zdania ze znaczenia elementw? Doczymy do regu gramatyki CFG dodatkowe informacje (podobnie jak miao to miejsce przy rozszerzaniu CFG do gramatyk unifikacyjnych) Regua gramatyki bdzie miaa teraz posta: A 1 ... n { f(j.sem, ... , k.sem) } W powyszym przykadzie: ProperNoun AyCaramba {AyCaramba} MassNoun meat {Meat} NP ProperNoun {ProperNoun:sem} NP MassNoun {MassNoun:sem}

Verb serves { e, x, y Isa(e, Serving) Server(e, x) Served(e, y)} Wyraenia Lambda Jak wczy semantyk argumentw do semantyki czasownika? Wyraenia Lambda : xP(x) xP(x)(A) P(A) Verb serves {xy {e Isa(e, Serving) Server(e, y) Served(e, x)} S NP VP VP Verb NP {VP:sem(NP:sem)} {Verb:sem(NP:sem)} Przykad analizy semantycznej S ( AyCaramba serves meat ) e Isa(e, Serving) Server(e, AyCaramba) Served(e, Meat) NP AC VP

ye Isa(e, Serving) Server(e, y) Served(e, Meat)} NP Meat Proper-Noun AC Verb AyCaramba serves meat Mass-Noun Meat Kolejny przykad W restauracji podaj miso. Wydaje si, e interpretacj powyszego zdania powinno by: e,x Isa(e, Serving) Server(e, x) Served(e, Meat) Isa(x, Restaurant) ale, jeeli zaoymy, e interpretacj wyrazu restauracja jest wyraenie: x Isa(x, Restaurant) to jak uzyska powysze tumaczenie z: {xy {e Isa(e, Serving) Server(e, y) Served(e, x)} Proste zastpienie zmiennej wyraeniem nie prowadzi do waciwego rezultatu. Wynikiem jest: e Isa(e, Serving) Server(e, xIsa(x, Restaurant)) Served(e, Meat) niestety powyszy zapis nie jest wyraeniem rach. pred. I rz. (FOPC)

Wprowadzenie termw zoonych Rozwizaniem problemu jest taki zapis semantyki fraz rzeczownikowych, aby jej elementy byy dostpne z zewntrz: Wprowadzenie termw zoonych i sposobu ich przeksztacania: < Quantifier variable body > , np. x Isa(x; Restaurant) e Isa(e, Serving) Server(e, < xIsa(x, Restaurant) >) Served(e, Meat) Przeksztacenie na wyraenie logiki I rzdu: P (< Quantifier variable body >) Quantifier variable body Connective P(variable) Server(e, < xIsa(x, Restaurant) >) xIsa(x, Restaurant) Server(e, x) Niejednoznacznoci Struktura skadniowa (i znaczenie) Pacjent opuci sal operacyjn w dobrym stanie nawiasowanie negacji Nie zrobisz tego? Nie (nie zrobi albo wanie, e zrobi)

kwantyfikacja Kady chce mie pikny samochd. (kady inny) Kady chce wygra szczliwy los. (ten jedyny) wizane zaimkw Jan kaza Piotrowi wyczyci swoje buty. Wieloznaczno kwantyfikatorw Every restaurant has a menu. Czy to ... x (Isa(x, Restaurantx) e, y Having(e) ^ Haver(e, x) ^ Isa(y, Menu) ^ Had(e, y) ) czy ... y (Isa(y, Menu) ^ x Isa(x, Restaurant) e Having(e) ^ Haver(e, x) ^ Had(e, y) )

przy wieloznaczno zakresu kwantyfikatorw, brak jest oglnych regu rozstrzygania Statystyka a jzyk naturalny Chomsky, 1969 It must be recognized that the notion of a probability of a sentence is an entirely useless one, under any interpretation of this term Powszechnie zaakceptowane powinno by stwierdzenie, e prawdopodobiestwo zdania jest pojciem cakowicie nieprzydatnym, niezalenie od sposobu jego zdefiniowania. ale jednak tak nie jest Podejcie statystyczne dane: teksty w jzyku naturalnym metody analizy: liczenie wyrazw, liter, znakw moliwe wnioski: kolejno sw, stae frazy (nazwy produktw, firm, ...) wspwystpowanie sw (np. w tekcie, w ktrym czsto pojawia si sowo drzewa sowo bal ma pewnie znaczenie inne ni w tekcie, w

ktrym wystpuje czsto sowo suknia czy frak) - podzia tekstw na kategorie tematyczne rozpoznanie jzyka, w ktrym jest tekst (nie trzeba mie sownika), np. dua liczba sw zaczynajcych si od wielkiej litery moe sugerowa niemiecki, czstotliwo zbitek th lub ph angielski ... Podejcie statystyczne, cd. Dane: teksty w jzyku naturalnym z anotacjami (tagami) zawierajcymi: informacje o czci mowy i cechach fleksyjnych metody analizy: liczenie wyrazw lub tagw (i ich sekwencji) 1 wersja: anotacje wzite ze sownika, niejednoznaczne piec rzeczownik, r. m3, mianownik, czasownik, bezokolicznik 2 wersja: anotacje ujednoznacznione (rcznie lub automatycznie ,

w szczeglnoci metodami statystycznymi) 3: inne rodzaje anotacji: informacje o granicach zda, fraz, o strukturze skadniowej ... Podejcie statystyczne, cd. Co mona osign? anotacje ujednoznacznione znacznie zwikszaj skuteczno wyszukiwania, np. w odpowiedzi na pytanie mama (we wszystkich formach) nie otrzymamy form czasownika mie aby jednak dalej poprawi skuteczno potrzebne s anotacje semantyczne: np. serwis : porcelanowy, sportowy/giedowy czy pocztek gry wyszukiwa okrelonego typu informacje bnez znajomoci dokadnej struktury tesktu formuowanie hipotez o budowie tekstu (znajdowanie granic fraz, zda, wzorcw syntaktyznych) Rozstrzyganie niejednoznacznoci. Reguy czy statystyka?

Przykady problemw, jednoznaczno w kontekcie, np.: she books, ona pali --> books, pali (?) to czasowniki regua: jeeli niejednoznaczne sowo (rzeczownik/czasownik) poprzedzone jest (zgodnym) zaimkiem, to jest to czasownik ale nie zawsze, np. przecie ona pali nie przesuna niejasne sytuacje: on pali, nie potnie teraz tych pali on pali, o ile wiem, nie potnie, pali poci bal -> czasowniki narzucaj wymagania na typ obiektw opisywanych przez ich wymagania przygotowywa si na bal podnie bal ale: taczy na balu Postulaty Nie

zgaduj, jeli wiesz morfologia (odmiana) sowniki (listy sw) jednoznaczne nazwy by moe cz staych fraz reguy syntaktyczne?? Wykorzystuj statystyk (opierajc si o dane rzeczywiste) dla ustalania preferencji Prawo Bayesa p(A,B) = p(B,A) bo p(A pB czyli: skoro p(A|B)=p(A B) /p(B) to p(A B) = p(A|B) p(B) i p(A B) = p(B|A) p(A) p(A|B) p(B) = p(B|A) p(A) i p(A|B) = p(B|A) p(A) / p(B) p(B|A) = p(A|B) p(B) / p(A) Powysza regua znana jest jako prawo Bayesa. Pozwala ona na przechodzenie midzy prawdopodobiestwami p(A|B) i p(B|A) w

zalenoci od tego, jakimi danymi dysponujemy Noisy Channel Model Zadaniem jest odkodowanie sygnau rdowego Input Output(noisy) 0,1,1,1,0,1,0,1,... SOURCE The channel The channel (adds noise) 0,1,1,0,0,1,1,0,... (adds noise) NOISY CHANNEL DECODER word noisy word guess at original word Model to prawdopodobiestwo bdw (szumu): Przykad: p(0|1) = .25 (otrzymalimy 1 a byo 0 - czyli prawdopodobiestwo e byo 0 pod warunkiem, ze otrzymalimy 1) p(1|1) = .75 (otrzymalimy 1 i byo 1) p(1|0) = .5 (otrzymalimy 0, a byo 1) p(0|0) = .5 Noisy Channel - zastosowania

Wiele problemw zwizanych z NLP moe by widziane jako problemy zwizane z likwidacj szumw (noisy channel problems), m.in. OCR text print (adds noise), scan image rozpoznawanie pisma odrcznego text neurones, muscles (noise), scan/digitize image poprawianie bdw pisowni (spelling correctors) rozpoznawanie mowy (dyktowanie, wydawanie polece) text conversion to acoustic signal (noise) acoustic waves ??tumaczenie maszynowe text in target language translation (noise) source language tagowanie (Part of Speech Tagging) sequence of tags selection of word forms text Wykorzystanie prawa Bayesa W przypadku zaszumienia sygnau poszukujemy najbardziej prawdopodobnego cigu wejciowego, ktry mgby odpowiada zaobserwowanemu sygnaowi. Poszukujemy wic:

argmax Source P(Source|Signal) p(A|B) = p(B|A) p(A) / p(B) Niestety zwykle brak niezbdnych danych. Jednak: P (Source|Signal) = P (Signal|Source) P(Source) / P (Signal) co nam daje: argmax Source P(Signal|Source)P(Source) / P(Signal) W jaki sposb to nam moe pomc, skoro dysponujemy jedynie zaobserwowanym sygnaem, a nie znamy sygnau waciwego? Wiemy, jaka jest przestrze moliwych danych pocztkowe. Moemy wstawi kad z nich do powyszego rwnania, policzy prawdopodobiestwa i wybra hipotez o najwyszym prawdopodobiestwie. Wykorzystanie prawa Bayesa do kontroli pisowni

dane (signal): sowo le napisane rezultat (source): poprawne sowo Zamy, e V jest przestrzeni moliwych sw, w oznacza prawidowe sowo, a s bdn jego pisowni w = argmax wV P(w|s) = argmax wV P(s|w)P(w) / P(s) Do policzenia powyszego potrzebujemy: P(s|w) , P(w), P(s) P(s) - prawdopodobiestwo pojawienia si bdnego sowa s P(w) - prawdopodobiestwo pojawienia si w tekcie sowa w P(s|w) - prawdopodobiestwo pojawienia si s zamiast w Rozwamy przykad: w tekcie pojawio si acress zamiast actress ... musimy policzy prawdopodobiestwo zrobienia takiego bdu ... Rodzaje bdw pisowni

Postulat zbadania czstoci wystpowania konkretnych bdw w poszczeglnych sowach jest nierealistyczny. Nie da si zebra danych odpowiedniej wielkoci Trzeba wic policzy P(s|w) nie dysponujc bezporednimi danymi. rda bdw: wstawienie zbdnej litery: ther - the, jeje - jej brak litery: ther - there, jj - jej zastpienie prawidowej litery inn: noq - now, zmiana kolejnoci liter: teh - the, nei - nie Wystpienie sowa acress zamiast actress moe by potraktowane jako bd braku t, a wic poszukiwane prawdopodobiestwo to ... Naley wic w odpowiednio duym (niepoprawianym) korpusie policzy czsto braku litery t. Metoda Kernighana (1990) Tabela prawdopodobiestw pomyek (na podstawie korpusu)

P (t|c) = del[c p-1, cp] / count[c p-1cp] if deletion ile razy zamiast c p-1cp wystpio c p-1 ins[c p-1, tp] / count[cp-1] if insertion ile razy zamiast c p-1 wystpio c p-1cp sub[t p, cp] / count[cp] if substitution ile razy zamiast cp wystpio t p trans[c p, c p+1 ] / count[c pcp+1] if transposition ile razy zamiast c p-1cp wystpio cpc p-1 Przykadowo jeli chcemy poda prawdopodobiestwo bdu jje zamiast jej liczymy czsto wystpienia je zamiast ej. Metoda Kernighana, cd. zaoenie podstawowe: w sowie jest tylko jeden bd generujemy wszystkie moliwe pojedyncze bdy dla danego

(bdnego) sowa wyznaczamy wszystkie moliwe rezultaty tych bdw i sprawdzamy, ktre z nich s sowami naszego jzyka wyznaczamy prawdopodobiestwo wystpienia poszczeglnych sw proponujemy sowa w kolejnoci ich prawdopodobiestw Wyniki dla acress zamiast actress Korpus 44 milionw sw, poprawka dla sw niewystpujcych w korpusie - dodanie 0.5 do wszystkich czstoci P(c) = (C(c)+0.5) /(N+0.5*V) V- liczba sw w sowniku c freq(c)

actress cress caress access across acres acres p(t|c)p(c) % .000117 3.69 x 10 -9 .00000144 2.02 x 10-14 .00000164 1.64 x 10-13 .000000209 1.21 x 10-11 .0000093 1.77 x 10-9 .0000342 2.22 x 10-9 .0000342 2.22 x 10-9 p(c) 1343 0 4 2280

8436 2879 2879 p(t|c) .0000315 . 00000014 . 000001 .000058 .00019 .000065 .000065 37% 0% 0% 0% 18% 21% 21% Podsumowanie metody

Brak wykorzystania kontekstu, np.. a stellar and versatile acress whose... (actress) Zamiast obliczania prawdopodobiestwa bdu na podstawie korpusu ustalenie pocztkowo wszystkich prawdopodobiestw jako rwnych i uczenie si na podstawie dostarczanych zbiorw danych (pary sw bdnych i poprawnych) ! Jest (bardzo) wiele sposobw, na jakie mona w danej sytuacji zastosowa model Bayesa - zaley to gownie od rodzaju danych jakie chcemy/moemy zebra Problemy zwizane z tym podejciem: potrzeba istnienia korpusw szczeglne traktowanie sw, ktre nie wystpiy ani razu Automaty z prawdopodobiestwem, rozpoznawanie mowy Jeeli zaoymy, e reprezentacja wymowy jest niestandardow pisowni moemy rozpoznawanie mowy potraktowa jako szczeglny przykad korektora pisowni

Do rozpoznawania mowy konstruujemy automat, w ktrym stany reprezentuj elementy wejcia (phones, letters, etc). przejcia wzbogacone s o prawdopodobiestwa mwice jakie jest jego prawdopodobiestwo, Suma prawdopodobiestw na przejciach wychodzcych z jednego stanu musi wynosi 1 z uwagi na tradycj symbole zgodnie z ktrymi dokonywane s przejcia przypisywane s do stanw, a nie samych przej Poniewa analizujemy tekst w jzyku naturalnym ograniczymy automaty do takich, w ktrych wszystkie przejcia prowadz w przd Prob, FSA, modele sw Automat rozpoznajcy wymow sowa need start ... n1 n a14=.11 iy2 .89

d3 iy Observation Sequence (phone symbols) d end ... Wykorzystanie probabilistycznych FSA Wykorzystujc probabilistyczne FSA moemy odpowiedzie na pytania: jakie jest prawdopodobiestwo wygenerowania konkretnego wyraenia?

Jaka jest najbardziej prawdopodobna cieka przejcia dla danego wyraenia ? Jaki jest najbardziej prawdopodobny rezultat (wyjcie) dla danego wejcia? Jak przypisa prawdopodobiestwa do przej? (??) Model Bayesa dla wymowy Zadanie: na podstawie serii fonemw obliczy najbardziej prawdopodobne sowo, ktre im odpowiada (zaoymy chwilowo, e fonemy te s prawidowo rozpoznane i e znamy granice sowa) Przykad: zaoymy, e rozpatrywan sekwencj jest [ni] korpus mwionego jzyka angielskiego (Switchboard Corpus) podaje nastpujce sowa, ktrych wymowa jest [ni]: the, neat (neat little), new (New York), need, knee, to (talking to you) , you ! Wybr zgodnie z regu w = argmax wW P(y|w) P(w) y= [ni], w -jedno z 7 sw

Jak wyznaczy p(y|w) ? Reguy probabilistyczne Propozycja 1: analogicznie jak dla bdw pisowni (tabele czstoci pojedynczych bdw (dla pisowni byy to: zamiana, opuszczenie, wstawianie, przestawienie kolejnoci) przeszkoda: zmian wymowy moe by w jednym sowie wiele, s od siebie zalene (dotycz nie tylko jednego fonemu) Idea: reguy probabilistyczne przykad: regua, ktra mwi, e po wyrazie zakoczonym na n, lub m (goska nosowa) sowo the moe by wymwione jako [ni] (a dokadniej dwik [] moe by zastpiony przez [n]): n / [+nasal]# __ zmiana ta nie zachodzi jednak zawsze: [.15] n / [+nasal]# __ Jak ustali warto [.15]? - odpowied: na podstawie korpusu Przykad, I need, cd. Sowo the neat

need new regua nasal assimilation pominicie kocowego t pominicie kocowego d zmiana u przed y w freq(w) knee 61 the 115 neat 338 need 1417 new 2625 p(w) 0.00024 0.046 0.00013 0.00056 0.001 P

n / [+nasal]# __ [.15] t / V __ # [.52] d / V __ # [.11] u i / __ #y [.36] p(y|w) 1 0 0.52 0.11 0.36 p(y|w)p(w) 0.000024 0 0.000068 0.000062 0.00036 Poprawa wyniku - uwzgldnienie kontekstu (np. bigramy) Metody statystyczne w inynierii lingwistycznej, cz.2 Sowa w kontekcie

Most zaprojektowany prawie 100 lat temu przez Leonarda da Vinci otwarto w rod w Norwegii. GW, 3-4.11.2001 W wielu przypadkach jestemy w stanie przewidzie kolejne sowo (a przynajmniej klas do jakiej naley) Rodzaje zasobw wiedzy, z ktrej korzystamy: wiedza oglna o wiecie i dotyczca konkretnej dziedziny wiedza syntaktyczna wiedza leksykalna Sowa w kontekcie Postulat: Du cz wiedzy niezbdnej do przewidywania moliwego dalszego cigu wypowiedzi moemy analizowa korzystajc z metod statystycznych. W szczeglnoci moemy mwi o prawdopodobiestwie zdania (wypowiedzi)

Czy rzeczywicie chcemy przewidywa jakie bdzie nastpne sowo? NIE, ale jeeli umiemy to zrobi, to znaczy, e umiemy porwnywa prawdopodobiestwa pewnych pocze - umiemy ocenia prawdopodobiestwo/poprawno zdania. np. Przy analizie mowy moemy oceni ktra z naszych hipotez jest najbardziej prawdopodobna Rzeczywiste bdy pisowni Wiadomo, e pewne typy bdw prowadz do sw, ktre wystpuj w sowniku (wykrycie ich wymaga uwzgldniania kontekstu); sposb traktowania takich bdw, np. budowa listy czsto mylonych sw: piece/peace, whether/weather/, their/there etc. Jeeli w zdaniu wystpuje ktre z czsto mylonych sw - konstrukcja alternatywnego zdania, zbadanie prawdopodobiestwa konkurencyjnych zda i wybr sowa, ktre wchodzio w skad zdania o wikszym prawdopod. np.: ... blah blah blah the whether... vs blah blah blah the weather... Prawdopodobiestwo zdania moe by widziane jako iloczyn prawdopodobiestwa sw, w nim wystpujcych, np.

P(The big cat)= P (the ^ big ^ cat) acuchy (Chain Rule) Przypomnijmy definicj prawdopodobiestwa warunkowego: p(A|B) = p(A^B) / p(B) czyli p(A ^ B) = p(B|A) p(A) tzn. p(The ^ dog) = p(dog|the) p(the) W oglnoci: p(A1, A2, A3, A4, ..., An) = p(A1|A2,A3,A4,...,An) p(A2|A3,A4,...,An) p(A3|A4,...,An) ... p(An-1|An) p(An) inaczej p(wn1) = p(w 1 )p(w2 | w1) p(w3 |w21) ... p(wn | wn-11) = n k=1 p(wk | wk-11) (regua acucha to bezporednia konsekwencja reguy Bayesa) !

Zota regua (klasycznej statystycznej inynierii lingwistycznej) Jeeli jestemy zainteresowani zdarzeniem A pod warunkiem B i jeli bezporednie oszacowanie p(A|B) jest praktycznie trudne bd niezgodne z naszymi zamierzeniami: zgodnie z regu Bayesa liczymy: argmaxA p(A|B) = argmaxA p(B|A) . p(A) / p(B) = argmaxA p(B|A) p(A) ! ... gdy p(B) jest stae dla zmieniajcych si A Zota regua ... OCR, ASR, MT, ... ... OCR, ASR,HR, HR, MT, p(A|B) = p(B|A) p(A) / p(B) (formua Bayesa)

Abest = argmaxA p(B|A) p(A) (zota zasada) p(B|A): model akustyczny, leksykalny, ... (nazwa zalena od aplikacji) p(A): model jzyka W statystycznych aplikacjach dotyczcych jzyka naturalnego wiedza o rdle danych nazywana jest czciej modelem jzyka (Language Model) ni gramatyk. Idealny model jzyka Jzyk to cig form wyrazowych notacja: A ~ W = (w1,w2,w3,...,wd) zadanie (cel modelowania): p(W) = ? Oczywicie jest regua: p(W) = p(w1,w2,w3,...,wd) = = p(w1) p(w2|w1)p(w3|w1,w2)p(wd|w1,w2,...,wd-1) ale niezbyt praktyczna -> zbyt wiele parametrw nawet przy maym d acuchy Markova W

idealnym modelu - pami nieskoczona: dla wi, znamy wszystkich poprzednikw w1,w2,w3,...,wi-1 Przyblianie - zaoenie Markova: P (w n | wn-11) P (w n | wn-1n-N+1) , (robimy zaoenie, ktre umoliwia nam zbieranie statystyk) tzn. pami ograniczona: zapominamy o zbyt dawnych poprzednikach pamitamy tylko kilka (k) poprzedzajcych sw : wi-k,wi-k+1,...,wi-1 metoda ta nazywana jest aproksymacj Markova k-tego rzdu kth order Markov approximation + niezmienno w czasie acuchy Markova, bigramy peny wzr: P (wn1) = P (w 1) P(w 2 | w 1 ) P(w 3 | w 12)... P(w n | w 1n-1) = P(w k | w 1k-1) k=1..n

przyblienie - zaoenie Markova: P (w n | wn-11) P (w n | wn-1n-N+1) zaoenie Markova dla bigramw P (wn1) P(w k | w k-1) k=1..n (N- rzd) acuchy Markova, bigramy Estymacja : P(w k | w k-1) na podstawie czstoci w korpusie treningowym P (w n | wn-1) = c(w n-1 wn) / w c(w n-1 w) =

= c(w n-1 wn) / c(w n-1) Przykady x-Gramy unigrams: (bez pamici) P(dog), P(sen) bigramy: (pami jednego sowa) P(dog|big), P(sen|kolorowy) trigramy: (pami dwch sw) P(dog|the big) quadrigramy: P(sen|nienaturalnie kolorowy) (pami trzech sw) P(dog|the big bad)

P(sen|bardzo nienaturalnie kolorowy) Przykady z Berkeley restaurant project Prawdopodobiestwa poszczeglnych cigw sw mog by przybliane przez liczebnoci w odpowiednio duym korpusie. system odpowiada na pytania dotyczce restauracji w Berkeley, California korzystajc z odpowiedniej bazy danych przykadowe pytania: Im looking for Cantonese food. Id like to eat dinner someplace nearby. Tell me about Chez Panisse. Can you give me a list of the kinds of food that are available? When is cafe Venezia open during the day? Korpus ok. 10 000 zda, 1616 form wyrazowych BERP, bigramy Counts I want to

eat Chinese food lunch Probs I want to eat Chinese food lunch I 8 3 3 0 2 19 4 I .0023 .0025 .00092 0 .0094

.013 .0087 want 1087 0 0 0 0 0 0 want .32 0 0 0 0 0 0 to 0 786 10 2 0 17

0 to 0 .65 .0031 .0021 0 .011 0 eat 13 0 860 0 0 0 0 eat .0038 0 .26 0 0 0 0

P (w n | wn-1) =c(w n-1 wn) / c(w n-1) Chinese 0 6 3 19 0 0 0 Chinese 0 .0049 .00092 .020 0 0 0 food 0 8 0 2 120 0 1

food 0 .0066 0 .0021 .56 0 .0022 lunch 0 6 12 52 1 0 0 lunch 0 .0049 .0037 .055 .0047 0 0 uni.

3437 1215 3256 938 213 1506 459 Prawdopodobiestwo zdania Prawdopodobiestwa policzone z danych: eat on (on|eat) - 0.16 eat at eat some - 0.06 eat Indian 0.04 eat lunch - 0.06 eat Thai 0.03 I - 0.25 I want - 0.32 British food- .6 want to to eat - 0.04

.65 .26 Wyliczone prawdopodobiestwo zdania: P(I want to eat British food) = = 0.000016 P(I|) P(want|I) P(to|want) P(eat|to) P(British|eat) P(food|British) (z uwagi na mae liczby operujemy zwykle na logarytmach, logprob) Kilka uwag o podanych liczbach: Czste poaczenia: P (want|I) = .32 P (to|want) = .65 P (eat|to) = .26 P (food|chinese) = .56 P (lunch|eat) = .055 Rzadkie poczenia: P (I|I) P (I|want) P (I|food) ale nie niemoliwe: P (I|I) I I I I want...

P (I|want) I want I want P (I|food) the kind of food I want is... N-gramowe modele jzyka n-gram Language Models Aproksymacja Markova (n-1)th rzdu n-gram LM: p(W) df i=1..dp(wi|wi-n+1,wi-n+2,...,wi-1) W szczeglnoci (przy sowniku |V| = 60k): 0-gram LM: uniform model, p(w) = 1/|V|, 1 parametr 1-gram LM: unigram model, 2-gram LM: bigram model, 3-gram LM: trigram model, p(w), 6104 parametry p(wi|wi-1) 3.6109 parametry p(wi|wi-2,wi-1) 2.161014 parametry Kilka uwag - wnioski

niewielka liczba zdarze wystpuje z du czstoci dua liczba zdarze wystpuje z niska czstoci. ! Mona szybko zebra dane dotyczce duych czstoci ! Zebranie danych dotyczcych niskich czstoci moe trwa zbyt dugo ! Zera pojawiajce si w tabelach s dwojakiego rodzaju: rzeczywiste 0 0 wynikajce ze zbyt maej prby N-gramy, problem zerowych wystpie w przypadku generowania tekstw jestemy ograniczeni tylko do tych n-gramw, ktre wystpiy w analizowanym korpusie; przy dostatecznej wielkoci korpusu ograniczenie to ma niewielkie znaczenie

praktyczne; przy analizie system przypisuje zerowe prawdopodobiestwa wyraeniom, ktre zawieraj takie elementy, ktre nie wystpiy w korpusie - tak by nie moe. Metody obejcia problemu nie wykorzystywa n-gramw wyszego rzdu wprowadzenie poprawek do modelu (smoothing) zmniejszeni licznoci n-gramw, ktre wystapiy na rzecz tych, ktre nie wystpiy (metody: Add-One , Witten-Bell) rodki matematyczne (backoff (Katz Backoff), interpolacja) BERP, bigramy, model Add One Counts,org. I I 8 want 3 to 3 eat 0 Chinese 2

food 19 lunch 4 Counts+1 I want to eat Chinese food lunch I 6 2 3 0.37 0.36 10 1.1 want to 1087 0 0 786

0 10 0 2 0 0 0 17 0 0 want 740 0.42 0.69 0.37 0.12 0.48 0.22 to 0.68 331 8 1 0.12 9 0.22

eat 13 0 860 0 0 0 0 Chinese food lunch 0 0 0 6 8 6 3 0 12 19 2 52 0 120 1 0

0 0 0 1 0 eat Chinese food lunch 10 0.68 0.68 0.68 0.42 3 4 3 594 3 0.69 9 0.37 7.4 1 20 0.12 0.12 15 0.24

0.48 0.48 0.48 0.48 0.22 0.22 0.44 0.22 Co osignlimy? Add One jest z metod przybliania bardzo due zmiany czstoci (duy % przypisany tym n-gramom, ktre nigdy nie wystpiy) Gale i Church (1994) dowodz, e jest to metoda gorsza nawet od wersji zupenie nie poprawianej mona dodawa mniej ni 1, ale wci nie jest to najlepsza metoda .. Witten-Bell

Idea: prawdopodobiestwo n-gramu, ktry jeszcze nie wystpi jest zalene od tego jaka cz z moliwych n-gramw nie pojawia si jeszcze w korpusie Ile razy rozpoznawalimy jaki n-gram po raz pierwszy? - tyle razy ile stwierdzilimy rnych n-gramw (kady by kiedy rozpoznany po raz pierwszy), T Tak wic prawdopodobiestwo napotkania nowego typu (n-gramu) (czyli suma prawdopodobiestw wszystkich n-gramw, ktre jeszcze nie wystapiy): pi* = T /( N + T) T- liczba typw, ktre wystpiy w korpusie i:ci=0 N-liczba wszystkich wystpie wszystkich typw Witten-Bell Discounting

Ustalilimy prawdopodobiestwo wystpienia wszystkich nie napotkanych jeszcze n-gramw, ale jak je rozdzieli ... Najprostsza propozycja - po rwno Z = 1 czyli Z - liczba typw o licz. 0 pi* = T / Z ( N + T) i:ci=0 inaczej : pi* = T / Z ( N + T) if ci =0 Nie moemy jednak tylko doda przewidywanych prawdopodobiestw - musimy unormowa sum do 1. Tym samym pomniejszamy prawdopodobiestwa tych n-gramw, ktre si pojawiy w korpusie: pi* = ci / (N + T) if (ci > 0) Witten-Bell dla bigramw W przypadku unigramw metoda ta przypomina metod Add One Dla bigramw jednak metoda ta uwzgldnia w pewnien sposb histori: rozdzielanie prawdopodobiestwa rwno pomidzy wszystkie ngramy nie jest najlepsz strategi -- niektre sowa czciej ni inne wprowadzaj nowe konteksty, moemy oszacowa prawdopodobiestwo wprowadzenia nowego

bigramu na podstawie dotychczas zgromadzonych danych: Dla danego sowa liczymy ile rnych bigramw zaczyna i dzielimy przez liczb wystpie wszystkich bigramw zaczynajcych si od niego metoda czsto uywana w systemach rozpoznawania mowy Final Witten-Bell Bigram Equations Cakowite prawdopodobiestwo bigramw, ktre si jeszcze nie pojawiy: i:c(wx wi )=0 pi* (wi|wx) = T (wx) /( N(wx) + T(wx)) T- liczba typw bigramw, N- liczba wystpie Dla poszczeglnych bigramw (tak jak poprzednio): Z(wx)= 1 (ile bigramw ma 0 wystpie)

i:c(wx wi )=0 pi* (wi|wi-1) = T(wi-1) / Z(w i-1) (N + T(wi-1)) if c(wi-1 wi )= 0 BERP Liczba rnych bigramw dla sw z przykadu: I - 95 Chinese - 20 want food - 76 - 82 to -130 lunch - 45 eat

- 124 liczba sw 1616, wic dla kadego sowa moliwych bigramw - 1616 liczba niewidzianych bigramw: I - 1521 want Chinese - 1596 food - 1540 to - 1486 - 1534 lunch - 1571 eat - 1492 BERP, bigramy, model Witten-Bell Counts I want to eat Chinese food lunch

CountsWB I want to eat Chinese food lunch I 8 3 3 0 2 19 4 I 8 3 3 0.75 2 18 4

want to 1087 0 0 786 0 10 0 2 0 0 0 17 0 0 eat 13 0 860 0 0 0 0 want to eat

1060 0.62 13 0.46 740 0.46 0.85 10 827 0.75 2 0.075 0.12 0.01 0.12 0.59 16 0.59 0.26 0.2 0.26 Chinese food lunch 0 0 0 6 8 6 3

0 12 19 2 52 0 120 1 0 0 0 0 1 0 Chinese 0.62 6 3 17 0.12 0.59 0.26 food 0.62 8 0.085

2 109 0.59 1 lunch 0.62 6 12 20 1 0.59 0.26 bigramy, porwnanie Add One i W-B CountsWB I I 8 want 3 to 3 eat 0.75 Chinese 2 food

18 lunch 4 want to eat Chinese food 1060 0.62 13 0.62 0.62 0.46 740 0.46 6 8 0.85 10 827 3 0.085 0.75 2 0.075 17 2 0.12 0.01 0.12

0.12 109 0.59 16 0.59 0.59 0.59 0.26 0.2 0.26 0.26 1 lunch 0.62 6 12 20 1 0.59 0.26 Counts +1 I I 6 want 2

to 3 eat 0.37 Chinese 0.36 food 10 lunch 1.1 want to eat Chinese food lunch 740 0.68 10 0.68 0.68 0.68 0.42 331 0.42 3 4 3 0.69

8 594 3 0.69 9 0.37 1 0.37 7.4 1 20 0.12 0.12 0.12 0.12 15 0.24 0.48 9 0.48 0.48 0.48 0.48 0.22 0.22 0.22 0.22

0.44 0.22 Good-Turing Discouting Idea oglna: (metoda dobra dla estymacji z duych danych) wyznaczenie czstoci wystpowania N-gramw, N(c) okrela ile sw wystpowao c - razy (count-of-counts) estymator prawdopodobiestwa wzgldnego wyznaczony na podstawie czstoci wystpowania: pr(w) = (c(w) + 1) N(c(w) + 1) / (|T| N(c(w))) w szczeglnoci oszacowanie czstoci grupy na podstawie oszacowanego stosunku grupy 1 do 0 (dla sw jeszcze niespotykanych: c(w) = 0) pr(w) = N(1) / (|T| N(0)) maa liczba grup (< 5-10, N(c) wysokie) oczywicie konieczna normalizacja (aby wp(w) = 1) Metody Backoff (cofania, korzystania z wiedzy czciowej) Celem jest znalezienie przyblie dla n-gramw, ktre nie pojawiy si w

zbiorze treningowym, a dokadniej prawdopodobiestwa pojawienia si formy x w konkretnym kontekcie O ile forma ta ju wczeniej wystpowaa (ale w innym kontekcie) moemy oprze nasze przypuszczenia na danych jej dotyczcych. Na przykad: jeeli nie mamy danych dla P(proces|poszlakowy) moemy skorzysta jako z P(proces), ktre zapewne nie jest zerowe. Ale trzeba wzi pod uwag dwa fakty: normowanie cakowitego prawdopodobiestwa do 1, zachowanie proporcji, tak by nie przypisa zerowym wystpieniom prawd. wyszego ni dla wystpie nie zerowych prawdopodobiestwa te ustalane s w rnych przestrzeniach Katz Backoff Jeeli N-gram ma liczno zero, cofamy si do N-1 gramu, jeli ten te ma liczno zero, to do n-2 - gramu ... w przypadku trigramw...

p`(wi| wi-2 wi-1) = pi (wi| wi-2 wi-1) if c(wi-2 wi-1 wi )> 0 1 pi (wi| wi-1) if c(wi-2 wi-1 wi )= 0 and c( wi-1 wi )> 0 2 pi (wi) wpp. Podsumowanie Kada z zaprezentowanych metod oparta jest na jakie obserwacji dotyczcej czstoci wystpowania sw w jzyku. adna z tych obserwacji nie jest nieprawdziwa, ale uwzgldnienie ich prowadzi do modeli dajcych rne rezultaty. Tak naprawd wiele zaley od wielkoci i rodzaju korpusu i potrzeb konkretnej aplikacji. Nie ma metody najlepszej.

Model jzyka najprostszy model jzyka skada si z: zestawu N-gramw opracowanego na podstawie korpusu z czstociami wygadzonymi przy pomocy metody Witten-Bell lub Good-Turing w poczeniu z jak form backoff. Mimo swej prostoty taki model jest uyteczny dla wielu zastosowa Testowanie i uczenie Prbujemy odgadn prawdopodobiestwa zdarze, ktre si nigdy nie wydarzyy ! Jak moemy oceni prawidowo naszych przypuszcze? Podzia zbioru danych na dwa rozczne podzbiory: zbir treningowy wykorzystywany do wyliczenia danych

modelu (uczenie si w tym kontekcie oznacza wyliczanie czstoci wystpowania w korpusie poszczeglnych n-gramw) zbir testowy wykorzystywany do sprawdzania modelu Testowanie i uczenie Lepszy sposb: Podzia danych na trzy rozczne zbiory: zbir treningowy (Training Set) zbir (Dev Test Set) sucy do sprawdzenia modelu, poprawienia go bd wyboru pomidzy alternatywnymi modelami zbir testowy (Test Set) wykorzystywany do kocowej oceny modelu. Dlaczego podzia na wicej ni dwa zbiory? Trudno unikn wielokrotnego sprawdzania modelu, a jeeli tylko sprawdzimy go na danych testowych i wprowadzimy poprawki, to wprowadzamy zakcenia i nasz zbir testowy traci niezaleno - staje si zbiorem treningowym Testowanie i uczenie Held Out Data (cross-validation)

podzia danych na N zbiorw trenowanie modelu na N-1 zbiorach testowanie na N-tym zbiorze powtarzanie tego procesu dla n rnych wyborw zbioru testowego urednienie rezultatw Rozpoznawanie mowy Zadanie: przeksztacenie sygnau mowy na tekst czyli: jakie zdanie jzyka L jest najbardziej prawdopodobnym rdem sygnau akustycznego o. Obecne systemy komercyjne dotycz rnych zastosowa: teksty o szerokiej tematyce (sownik rzdu 5000-60000 sw) teksty z wskiej dziedziny, polecenia pojedyncze sowa

Problemy: wielu mwcw mwicych jednoczenie haaliwe otoczenie szumy kanaw przesyu (telefon, TV, ...) Zadanie rozpoznawania mowy podejcie statystyczne Przypomnienie: Wbest = argmaxw p(W|O) Wbest = argmaxw p(O|W) p(W) (zota zasada) p(O|W): model akustyczny p(W): n-gramowy model jzyka HMM to metoda wyznaczenia p( O | W) Rozpoznawanie mowy, zadanie atwe czy trudne? cig fonemw (dane z korpusu): ay d ih s hh er d s ah m th ih ng ax b aw m uh v ih ng r ih s en l ih

to I just heard something about moving recently atwiejszy przykad [aa n iy dh ax ] I need the Model sowa automat z wagami (acuch Markova) need a14=.11 a01 a12 start n1 ...

n o1 iy2 d3 a23= .89 ly d o2 end a34 ... o3 observation sequence (phone symbols) zakadalimy tu, e znamy fonemy wejciowe, ale tak naprawd nie mamy symboli fonemw tylko sygna, ktry musimy podzieli na fonemy i sowa ... Model sowa, HMM need

a14=.11 start prawdop. n1 b1(o1) b1(o2) iy2 d3 b2(o3) b2(o4) b2(o5) end b3(o6) wyjciowe

...... o1 o2 o3 o4 o5 o6 observation sequence (spectral feature vectors) (trzeba jeszcze doda ptle w stanach n1, iy2 i d3 dla rnej dugoci fonemw) Ukryte modele Markova, Hiden Markov Models, HMM Ukrycie alfabetu

Najprostszy HMM: stany generuj symbole wyjciowe wykorzystujc odpowiedni alfabet, ale nie ma to zwizku z nazw stanw, jest niewidzialne (poniej jeszcze kady stan generuje inny symbol): t e 1 en e h r te re 0.6 0.3 0.4 a

1 0.4 2 0.12 0.88 3 p(4|3) = 0.1 4 0.2 o 1 p(toe) = .6 .881 = .528 Zwikszona elastyczno ... ale rne stany mog powodowa wypisanie takich samych symboli (bo dlaczego nie?): sumowanie prawdopodobiestw dla wszystkich cieek t e

1 e e nt r re e h 0.6 0.3 0.4 t 1 3 0.2 0.4

2 0.12 0.88 p(4|3) = 0.1 4 o 1 p(toe) = .6 .881 + .4 .11 = .568 Wyjcie zwizane z przejciami Jeszcze wiksza elastyczno: generowanie wyjcia na przejciach, nie w stanach t t e e nt e

r he 0.4 1 0.6 re 0.3 3 t e 0.4 0.1 e 2 0.12 0.88

0.2 o 1 1 4 o o p(toe) = .6 .881 + e .4 .11 + .4 .2.3 + .4 .2.4 = .624 ... i w kocu prawdopodobiestwa wyjcia Maksymalna elestyczno: [Unigramowy] rozkad (przestrze alfabet wyjciowy) na kadym wyjciu: p(t)=0 p(o)=0 p(e)=1

p(t)=.8 p(o)=.1 p(e)=.1 !simplified! te n e r re e h 1 0.6 1 0.4 3 p(t)=.5 p(o)=.2

p(e)=.3 0.88 0.88 p(t)=0 p(o)=1 p(e)=0 2 0.12 4 1 p(t)=.1 p(o)=.7 p(e)=.2 p(toe) = .6.881 + .4 1.88 + p(t)=0 .4 1.12 p(o)=.4 .237 p(e)=.6

Inne ujcie Zamiast przypisywa rozkad prawdopodobiestwa do jednego przejcia, mona zapisa odpowiednio wiele przej i kademu przypisa odpowiedni symbol wyjciowy i prawdopodobiestwo: te n e r re e h t,.2 o,.06 e,.06 1 t,.48 o,.08 e,.12 o,1

3 e,.12 e,.176 t,.088 o,.616 4 2 o,.4 e,.6 p(toe) = .48.616.6+ .21.176 + .21.12 .237 W praktyce wykorzystuje si ten sposb, ktry w danej sytuacji jest wygodniejszy. Formalizacja HMM (najoglniejszy przypadek) to (S, s0, Y, PS, PY) , gdzie: S = {s0,s1,s2,...,sT} to zbir stanw, s0 jest stanem pocztkowym, Y = {y1,y2,...,yV} to alfabet wyjciowy, PS(sj|si) zbir prawdopodobiestw przej wielko PS: |S|2.

PY(yk|si,sj) zbir prawdopodobiestw wyjciowych (wygenerowania symboli) Przykad: S = {x, 1, 2, 3, 4}, s0 = x Y = { t, o, e } wielko PY: |S|2 x |Y| HMM, przykad 0.6 1 0.4 Dla omawianego grafu: 3 S = {x, 1, 2, 3, 4}, s0 = x 1

0.88 0.88 2 0.12 4 1 Y = { e, o, t } x x 1PS:2 3 0 .6 0 .4 1 2 3 4 0 0 0 0

4 0 0 .12 0 .88 0 0 0 1 1 0 0 0 0 1 0 0 =1 t x 1 2 3 4 o x PY: 1 2 3 4 e x 1 2 3 4

x 1 2 3 4 1 2 3 4 1 .2 .8 .5 .7 2 .1 3 0 0 4 0 0 =1 Wykorzystanie HMM Generowanie (o niewielkim praktycznym znaczeniu :-)): 1. pocztek w s = s0. 2. przejcie z s do s z prawdopodobiestwem P S(s|s). 3. Wypisanie symbolu yk z prawdopodobiestwem PS(yk|s,s). 4. powtarzanie od kroku 2 (a kto powie do ) analiza:

rozpoznawanie mowy, przypisywanie tagw morfologicznych ... Wykorzystanie HMM HMM: model probabilistyczny i niedeterministyczny sekwencja stanw nie pozwala na jednoznaczne odtworzenie danych dane nie wyznaczaj jednoznacznie cigu stanw najlepsze co mona zrobi to dla danego cigu wejciowego odnale najbardziej prawdopodobny cig stanw (lub odwrotnie, dla danego cigu stanw wskaza najbardziej prawdopodobny cig wejciowy): Dla danego HMM & sekwencji wyjciowej Y = {y1,y2,...,yk}: (Zadanie 1) oblicz prawdopodobiestwo Y; (Zadanie 2) oblicz najbardziej prawdopodobny cig stanw, ktry doprowadzi do wygenerowania Y Zad. 1: obliczenie prawdopodob. (zakadamy dla uatwienia wyjcie deterministyczne) time/position t Trellis(siatka) HMM: 0

1 2 3 ,0 t en rh te A e er e 1 0.12 .6 0.3 0.4 C 0.88

D 0.1 B .6 A,0 rollout B,0 1 C,0 0.2 t o p(toe) = .6 .881 + .4 .11 = .568 .4 ,1 ,2

,3 A,1 A,2 A,3 B,2 B,3 C,2 C,3 B,1 .88 C,1 .1 D,0 - trellis state: (HMM state, position)

- each state: holds one number (prob): - probability of Y: in the last state - za Jan Hajic, 1999 Y: D,1 t D,2 + o 1 D,3 e (,0) = 1 (A,1) = .6 (D,2) = .568 (B,3) = .568 (C,1) = .4 4...

Obliczanie wartoci - start rozpoczynamy w stanie pocztkowym (), position/stage set its (,0) to 1. tworzymy 0 pierwsz kolumn siatki:,0 dla pierwszego symbolu =1 wyjciowego y1 kolumn siatki, uwzgldniajc tylko te stany, w ktrych mona wygenerowa y1 (state,1) = PS(state|) * (,0) ...i zapominamy o kolumie 0

1 .6 A,1 = .6 .4 C,1 e t Nastpny krok t en er re he A 0.3 0.4

e jestemy w kroku i Tworzenie nastpnego kroku: utworzenie komrek siatki dla tych stanw, ktre generuj yi+1, ale tylko dla tych, ktre s osigalne, z ktrego ze stanw kroku i ustalenie (state,i+1) na: PS(state|prev.state) (prev.state, i) (dodanie wszystkich tych wartoci dla ukw dochodzcych do jednej komrki/stanu siatki ) ... i zapominamy o stanie i 0.12 B 0.88 D 0.1 C Zamy, 1

1 0.2 t o p(to) = .6 .881 + .4 .11 = .568 position/stage i=1 2 A,1 = .6 .88 C,1 = .4 .1 D,2 yi+1 = y2:

+ o = .568 Ostatni krok Kontunujemy, a do wyczerpania wyjcia dla przykadu z toe |Y| = 3 czyli do kroku 3 dodajemy wszystkie (state,|Y|) to jest szukane P(Y). last position/stage B, 3 = .568 Uwagi o algorytmie (mie): zuycie pamici: 2|S|

max mnoe: |S|2|Y| 1 D,2 = .568 P(Y) = .568 (S -zbir stanw) Peny przykad (wyjcie nieterministyczne) Stage: ,0 0 .48 1 =1 1 A,2 = .2 A,1 = .48 A,1 .2

2 2 A,2 .12 B,3 = .024 + .177408 = .201408 1 .176 C,1 y1: t = .2 C,1 3 + .616 .6

y2: o e,.12 o,.06 e,.06 A t,.48 e,.176 re e h o,.08 t,.088 e,.12 er t o,1 en t,.2 o,.616 D C B o,.4 e,.6

D,2 .29568 D,2 D,3 = .035200 y3: e P(Y) = P(toe) = .236608 Zadanie 2: Algorytm Viterbi Algorytm znajdowania najbardziej prawdopodobnej cieki stanw, ktrej przejcie mogo doprowadzi do wygenerowania zaobserwowanego sygnau (Y) znajdujemy Sbest = argmaxS P(S|Y) (Y jest stae, wic i P(Y)):

Sbest = argmaxSP(S,Y) = = argmaxSP(s0,s1,s2,...,sk,y1,y2,...,yk) = = argmaxSi=1..k p(yi|si,si-1)p(si|si-1) (prawdopodobiestwo wygenerowania yi przy przejciu ze stanu si-1 do si razy prawdopodobiestwo przejcia z si-1 do si Jednoczenie ) rozwizujemy inny problem - segmentacj wejcia na sowa Algorytm Viterbi oglnie w tablicy viterbi[ stan, pozycja_wejcia_t] przechowujemy max. prawdop., z jakim moglimy doj do tego miejsca w dodatkowej tablicy back_pointers przechowujemy dla kadego stanu numer stanu poprzedniego, ktry lea na najlepszej ciece do przeduenia cieki z s wybieramy s takie, e iloczyn prawdopod. cieki do s razy prawd. przejcia z s do s razy prawd. wygenerowania w s t

jest max (dla wszystkich stanw) Viterbi function Viterbi(observations of len T,state-graph) returns best-path num-states num-of-states(state-graph) Create a path probability matrix viterbi[num-states+2,T+2] viterbi[0,0] 1.0 for each time step t from 0 to T do prawdop. przejcia z s do s for each state s from 0 to num-states do for each transition s from s specified by state-graph new-score viterbi[s, t] * a[s, s] * b s (o t ) prawdop. s|ot if ((viterbi[s, t+1] = 0) or (new-score > viterbi[s , t+1])) then viterbi[s , t+1] new-score back-pointer[s, t+1] s Backtrace from highest probability state in the final column of viterbi[] and return path Viterbi Example r classification (C or V?, sequence?): t,r

t,r te en e er h r 0.6 C C,C V 1 o,e,y,r .2 0.12 1

V,V 1 0.88 0.4 o,e,y,r 0.07 C,V 0.93 V,C .8 o,e,y,r t,r p(t|C) = .3 p(r|C) = .7 p(o|V) = .1

p(e|V) = .3 p(y|V) = .4 p(r|V) = .2 argmaxXYZ p(rry|XYZ) = ? Possible state seq.: (V)(V,C)(C,V)[VCV], (C)(C,C)(C,V)[CCV], (C)(C,V)(V,V) [CVV] Viterbi Computation Y: en te er h r e 0.6 t,r t,r C

0.4 V 1 =1 V,V = .07392 x .07 x .4 .002070 .2 1 V,V 1 0.07 0.93 V,C .8 o,e,y,r

C,C = .42 x .12 x .7 = .03528 = .6 x .7 = .42 o,e,y,r 0.12 C,V y C C,C 0.88 r in trellis

state: best prob from start to here p(t|C) = .3 p(r|C) = .7 p(o|V) = .1 p(e|V) = .3 p(y|V) = .4 p(r|V) = .2 r o,e,y,r t,r C,V C,V C,C = .03528 x 1 x .4 = .42 x .88 x .2 = .07392 .01411 V,C = .056 x .8 x .4

V,C .01792 = max = .08 x 1 x .7 V = .056 = .4 x .2 = .08 { n-best State Sequences Y: Keep track =1 of n best back pointers: Ex.: n= 2:

Two winners: VCV (best) CCV (2nd best) r r y C,C = .42 x .12 x .7 = .03528 C = .6 x .7 = .42 V,V = .07392 x .07 x .4 .002070 C,V C,V C,C = .03528 x 1 x .4 = .42 x .88 x .2 = .07392

? .01411 V,C = .056 x .8 x .4 V,C .01792 = max = .08 x 1 x .7 V = .056 = .4 x .2 = .08 { Potrzebne zasoby Korpus, aby wytrenowa model jzyka. Powinien by duy i reprezentatywny dla konkretnej dziedziny zastosowa Sownik wymowy, ktry posuy do zbudowania biblioteki

modeli wymowy sw. korpus nagra (wave files) z transkrypcj sowo po sowie korpus nagra (spectral feature frames) z transkrypcj zawierajc fonemy Uwagi o zasobach: Model jzyka powinien moliwie dobrze oddawa dziedzin, ktrej dotyczy dyktowany tekst, sownik wymowy prawdopodobnie nie bdzie kompletny, due rcznie anotowane dane zawierajce mow s kosztowne, rcznie anotowane dane na poziomie fonemw s jeszcze kosztowniejsze ! W rzeczywistoci nie da si uzyska wszystkich potrzebnych liczb z danych treningowych (konieczne estymacje)

Uwagi o algorytmie Viterbi Najbardziej prawdopodobny cig stanw (odpowiadajcy najbardziej prawdopodobnemu cigowi fonemw) moe nie odpowiada najbardziej prawdopodobnemu cigowi sw (np. jeli w sowniku jest wiele sposobw wymowy niektrych sw, sowa o jednoznacznej wymowie mog by preferowane) ! Przy podanym sposobie analizy problemu nie przeszukujemy wcale przestrzeni cigw sw. Moliwe bezporednie wykorzystanie tylko modelu bigramowego (dla modelu trigramowego, cieka max. prawdop. nie musi by przedueniem najlepszej iceki z poprzedniego stanu) - to mona omin podajc wicej rozwiza Best First Search Alternatywa - przeszukiwanie przestrzeni moliwych cigw sw przy wykorzystaniu

modelu jzyka do ewaluacji cieki modelu akustycznego do sugerowania najbardziej prawdopodobnych sw prawdopodobiestw stanowicych kombinacj pr. akustycznych i tych z modelu jzyka Algorytm: przeduanie najlepszej cieki, wyznaczanie najlepszej , przeduanie .. A* Problem: Co si stanie, jeli porwnamy prawdopodobiestwo rozszerzonej cieki do pr. innych, krtszych cieek? Rozwizanie: Zmodyfikowanie prawdopodobiestwa tak, by zawierao heurystyk dotyczc prawdopodobiestwa dalszego cigu f *(p)= g(p) + h*(p) f*(p) - pr. caej ciezki g(p) - pr. kawaka p h*(p) - estymacja najlepszego dalszego cigu (trudne do oszacowania, zalene np. od liczby sw, ktre zostay) Statystyczne tagowanie morfologiczne (POS).

Estymacja parametrw HMM. Tagset (przypomnienie) Najczstszy zbir etykiet to spis wszystkich moliwych kombinacji cech gramatycznych dla danego jzyka T C1C2... Cn zwykle cig liter i cyfr: system skrtw: NNS (gen. noun, plural) system pozycyjny: pozycja i odpowiada C : i AAMP3----2A---- (gen. Adj., Masc., Pl., 3rd case (dative), comparative (2nd degree of comparison), Affirmative ) tense, person, variant, etc.: N/A (oznaczone -) Zadanie tagowania morfologicznego Formalnie: A+ T A to alfabet fonemw (A+ niepusty cig fonemw) bardzo czsto zamiast fonemw - litery T jest zbiorem tagw (etykiet) (tagsetem)

Przypomnie naley wielo poziomw analizy jzyka: fonetyka... fonologia ... morfologia ... syntaktyka ... semantyka ... tag gin krok w bok g A+ 2(L,C1,C2,...,Cn) T morphology tagging: disambiguation ( ~ select) Przykady Forma sowa: A+ 2(L,C1,C2,...,Cn) T He always books the violin concert tickets early. MA: books {(book-1,Noun,Pl,-,-),(book-2,Verb,Sg,Pres,3)} tagging (ujednoznacznienie): ... (Verb,Sg,Pres,3)

...was pretty good. However, she did not realize... MA: However {(however-1,Conj/coord,-,-,-),(however2,Adv,-,-,-)} tagging: ... (Conj/coord,-,-,-) [a n d] [g i v] [i t] [t u:] [j u:] (and give it to you) MA: [t u:] {(to-1,Prep),(two,Num),(to-2,Part/inf),(too,Adv)} tagging: ... (Prep) Metody statystyczne (przegld) Probabilistyczne: HMM Merialdo i wiele innych (XLT) Maximum Entropy DellaPietra et al., Ratnaparkhi, i inni oparte na reguach: TBEDL (Transformation Based, Error Driven Learning)

Brills tagger oparte na przykadach Daelemans, Zavrel, inne oparte na opisie cech (jzyki fleksyjne) Classifier Combination (Brills ideas) Tagowanie statystyczne Noisy Channel: Input (tags) NNP VBZ DT... Output (words) The channel (adds noise) John drinks the ... Ponownie ta sama historia:

Argmax P (Tag Sequence|Word Sequence) po przeksztaceniu: Argmax P(Word Sequence|Tag Sequence)P (Tag Sequence) P (Word Sequence) Elementy modelu - P(Tag Sequence) Jeeli zaoymy, e dysponujemy otagowanym korpusem do trenowania naszego tagera i trigramowym modelem jzyka to P (Tag Sequence) moe by przyblione jako: P(t1) P(t2 | t1) n i=3 P(t i | t i-2 t i-1) co mona wyliczy z danych i wygadzi Model word | tag

P (Word Sequence|Tag Sequence) Czynimy w tym miejscu upraszczajce zaoenie, e sowo zaley tylko od tagu. n i=1 P(wi |ti ) czc to z modelem jzyka, poszukujemy sekwencji tagw, ktre maksymalizuj nastpujc wielko: P (t1 )P (t2 | t1)n i=3 P(t i | t i-2 t i-1) (n i=1 P(wi |ti ) ) Tagowanie statystyczne jako HMM Przejcia pomidzy stanami i ich prawdopodobiestwa pochodz z modelu jzyka prawdopodobiestwa wygenerowania symboli wyjciowych pochodz z rozkadu P(word|tag) jak w przypadku innych podobnych zastosowa znajdujemy najbardziej prawdopodobn sekwencj tagw wykorzystujc algorytm Viterbiego

Prosty przykad HMM a:P(a|n)P(n|n) a:P(a|n)P(v|n) n a:P(a|v)P(v|v) v b:P(b|n)P(v|n) b:P(b|n)P(n|n) b:P(b|v)P(v|v) tagi: n v sowa: a b i obu sowom mog by przyporzdkowane oba tagi Znajdowanie najbardziej prawdopodob. cieki (Viterbi, powt.)

Znamy cig wyjciowy, szukamy cigu stanw (t) = arg max P(Word Sequence|Tag Sequence) dla kadego stanu liczymy, jakie jest najwiksze prawdopodobiestwo znalezienia si w nim po t-krokach korzystamy z wynikw dla cieki o 1 krtszej musimy zapamita wynik dla kadego stanu (przy danym wejciu) poprzednie wyniki moemy zapomnie Najbardziej prawdopodobna cieka bbba a:.3 b:.2 b:.1 n a:.2 v a:.4 a:.2 b:.5 bb nn

.2 nv .1 bbb nnn .04 nvv .05 b:.1 stany n cig stanw prawdopod. V cig stanw prawdopod. b n 1.0 v 0 bbba

nnnn .008 nvvv .025 nvvvn .005 nvvvv .005 Obliczanie prawdopodobiestw dla HMM Dla kadego stanu s i liczymy po kadym sowie prawdopodobiestwo z jakim dany cig sw (dugoci t) doprowadziby nas nas tego stanu (warunki pocztkowe - dla cigu pustego, pr. dla stanu pocztkowego =1, dla innych 0) i(t) =(def) P(w 1,t-1 , St=s i ) t>1 (forward probalility) 1. P(w 1,n ) = i=1.. P(w 1,n, Sn+1=s i ) = i=1.. i(n+1)

prawd. uzyskania cigu w 1,n jest sum prawdopodobiestw uzyskania go poprzez dokoczenie cigu o 1 krtszego poprzez przejcie ze wszystkich stanw HMM Obliczanie prawdopodobiestw dla HMM j(t+1) = P(w 1,t , St+1=s j ) = i=1.. P(w 1,t, St=s i, St+1=sj ) = i=1.. P(w 1,t-1, St=s i)P(wt, St+1=sj | w1,t-1, St = sj ) = (Markov as.) i=1.. P(w 1,t-1, St=s i)P(wt, St+1=sj | St = sj )=

i=1.. i (t) P(si ->(wt) sj ) prawd. znalezienia si w momencie t w stanie i razy prawdopodobiestwo przejcia z i do j przy wt Obliczanie prawdopodobiestw dla HMM bbba b:.2 a:.3 n b:.1 v a:.2 a:.4 b:.1 a:.2

b:.5 Time ticks Input 1 2 b 3 bb 4 bbb 5 bbba n(t) V(t) P(w1,t) 1.0

.2 .05 .017 .0148 0.0 .1 .07 .04 .0131 1.0 .3 .12 .057 .0279

Prawdopodobiestwo liczone wstecz i(t) =(def) P(w 1,t-1 , St=s i ) t>1 (forward probalility) i(t) =(def) P(w t,n | St=s i ) (backward probalility) prawdopod. zobaczenia cigu w t,n o ile w kroku t znajdujemy si w s i i(t-1) = j=1.. j (t) P(si ->(wt-1) sj ) prawd. zobaczenia cigu wt w momencie t razy prawdopodobiestwo przejcia z i do j przy wt-1 Obliczanie prawdopodobiestw wstecz dla HMM bbba a:.3 b:.2 b:.1

n a:.2 v a:.4 b:.1 a:.2 b:.5 1 2 Input 3 bbba 4 bba 5 ba

a n(i) V(i) .0279 .063 .18 .7 1 .153 .27 .4 1 Ze stanu n bdziemy mogli przej z a albo do n z pr=.4, albo do v z pr .3

Uczenie Aby zdefiniowa HMM musimy mie prawdopodobiestwa (przej i generowania sw) jeeli dysponujemy danymi, to moemy tak dopasowywa nasz model, by wiksze prawdopodobiestwa nadawa sekwencjom, ktre pojawiy si w danych treningowych w skrajnym przypadku, moemy zapamita dane, ale na to potrzeba bardzo wielu stanw (zupenie niepraktyczne podejcie) jak inaczej: na przykad dla zwykego acucha Markova - liczymy dla danych testowych, ile razy ktre z przej zostao wybrane na wszystkie przejcia z danego stanu a na b v b Uczenie Cig treningowy: abbaababbaa

Licznoci: z n n v v do va nb na nb wyjcie liczno 5 3 2 2 a n b a v b

Uczenie HMM Nie zawsze wiemy, ktre z przej zostao wybrane (zakadamy, e wszystkie i rozdzielamy prawdopodobiestwo zgodnie z prawdopodobiestwem danej cieki) trzeba od czego zacz Problemy z ew. punktami krytycznymi, maximami lokalnymi C(s i -> (wk) s j) = P(s1,n+1 |w1,n ) *licz(s i -> (wk) s j, s1,n w1,n) ile razy (s i -> (wk) s j )pojawia si w cigu generowane jest w1,n stanw jeli Przykad 1:.17

0:.67 a 0:0.16 1:.48 b 1:1.01 Przyblienie 0:0.04 a 0:.48 b 1:1.0 Waciwy model cig treningowy: 01011 moliwe cieki: ababaa abaaa aaabaa aaaaaa Definicja modelu HMM dla tagowania

(prawie) oglny model HMM: output (sowa) emitowany przez stany (nie uki) stany: (n-1)-tka tagw (jeeli wykorzystujemy model n-gramowy) pitka (S, s0, Y, PS, PY), gdzie: S = {s0,s1,s2,...,sT} zbir stanw, s0 stan pocztkowy, Y = {y1,y2,...,yV} alfabet wyjciowy (sowa), PS(sj|si) zbir prawdopodobiestw przej midzy stanami PS(sj|si) = p(ti|ti-n+1,...,ti-1); sj = (ti-n+2,...,ti), si = (ti-n+1,...,ti-1) PY(yk|si) zbir prawdopodobiestw emisji sw uproszczenie: PY(yk|si) = PY(yk|sj) jeli si i sj zawieraj najbardziej na prawo ten sam tag: PY(yk|si) = p(wi|ti) Generowanie tekstw w

jzyku naturalnym Jurafsky Daniel, Martin James H. (2000) Speech and Language Processing. Upper Saddle River, Prentice Hall Mykowiecka, A. (1992) Podstawy przetwarzania jzyka naturalnego. Metody generowania tekstw, Akademicka Oficyna Wydawnicza, RM, Warszawa Charakterystyka problemu Generowanie tekstw: teksty stae wzorce z miejscami do wypeniania tekst budowany ze sw (niewielkich fraz) Najoglniejszy podzia zadania generacji wypowiedzi wyrnia trzy fazy tworzenia tekstu: planowanie treci wypowiedzi, wybr adekwatnych informacji planowanie postaci wypowiedzi,

wybr konstrukcji jzykowych, ostateczne sformuowanie wybr sw, powiza, uzgodnienia Planowanie postaci tekstw W pracach nad komputerowym generowaniem tekstu wyrni mona nastpujce podejcia: ustalenie schematw typowych wypowiedzi w terminach wybranego zestawu predykatw retorycznych (McKeown, 1985), opis znaczenia tworzonej wypowiedzi za pomoc formu specjalnie zdefiniowanej logiki (Appelt, 1985), traktowanie tekstu jako drzewa opisujcego relacje zachodzce pomidzy ssiednimi fragmentami tekstu (Mann & Thompson, 1988), Schematy, McKeown (1982), Paris (1987)

Schematy opisuj stereotypowe ukady zda w typowych tekstach np. definicjach obiektw. Zalet schematw jest atwo ich definiowania i wykorzystywania. Dla wybranego zastosowania okrelane s schematy odpowiadajce wszystkim typom paragrafw, ktre pojawi si mog w generowanych tekstach. Dla kadego wykorzystywanego w schematach typu zdania definiowany jest predykat precyzujcy rodzaj informacji, jak mona za pomoc takiego zdania przekaza oraz pewne dodatkowe dane, np. ile razy ten typ zdania moe pojawi si w ramach jednego paragrafu. Schematy s wic do pewnego stopnia niezalene od konkretnego zastosowania, a wiedza zwizana z dan dziedzin wykorzystywana jest do powizania poszczeglnych elementw schematu z konkretnymi danymi. Schematy Generowanie tekstu w oparciu o schemat polega na sekwencyjnym analizowaniu wszystkich jego elementw. W kadym kroku dokonywana jest ewaluacja warunkw stosowalnoci predykatw powizanych z

kolejnym elementem schematu, wybr wariantu, dla ktrego warunki te s spenione oraz selekcja z odpowiedniej bazy danych informacji potrzebnych do sformuowania wybranego rodzaju zdania. Jednym z ogranicze w stosowaniu schematw jest brak okrelenia funkcji retorycznej penionej przez poszczeglne jego elementy. Z tego wzgldu schematy nie s odpowiednie w przypadku systemw wymagajcych dynamicznego dostosowywania si do zmiennego kontekstu. Inn wad jest brak elastycznoci -- niezalenie od moliwoci zapisu wielu wariantw wypowiedzi schematy zawsze precyzyjnie okrelaj struktur tworzonego tekstu i nie pozwalaj na wprowadzanie zmian (z gry wiadomo dokadnie jakie ukady tekstu s dopuszczalne). TEXT, K. McKeown, lata 80-te Pennsylvania. Univ. Zadaniem systemu TEXT byo udzielanie odpowiedzi na pytania dotyczce struktury bazy danych. Jedna z jego wersji powstaa dla bazy danych zawierajcej informacje dotyczce jednostek pywajcych amerykaskiej marynarki wojennej. Uytkownik systemu mg otrzyma odpowied na pytania typu: co to jest ?, co wiesz o ?, jaka jest rnica pomidzy a ?

dane informacje wyszukiwane byy w opisie bazy danych. Sposb wyszukiwania odpowiednich informacji oraz sposb konstrukcji odpowiedzi by okrelony dla kadego typu pytania. TEXT - wiedza oglna System TEXT przechowuje informacje na temat bazy danych, ktrej dotycz zadawane pytania. Pamitane dane zorganizowane s w hierarchiczn sie semantyczn zawierajc: obiekty wystpujce w bazie danych (np. nazwy atrybutw, hierarchia atrybutw, powizania midzy nimi, sposb w jaki dziel obiekty na klasy), obiekty powizane (uytkownicy nie znajcy struktury bazy danych mog formuowa pytania poj pokrewnych) Przykadowymi faktami dodatkowymi, ktre naley umieci w bazie wiedzy s: definicje atrybutw, np. pracownik administracji, informacje niezmienne w konkretnej bazie, np. pe dla uczniw szkoy mskiej.

Typy zda jzyka naturalnego (Grimes) Opis atrybutu Maja ma t sukienk. Zrwnowaenie Wina wspaniae, to wina z dobrych winnic. Uszczegowienie faktu Wczoraj byo gorco. Termometr_wskazywa_40 Wyjanienie Jan wrci do domu poniewa zapomnia parasola. Potwierdzenie faktu Publiczno zauwaya rnic. Ju po pierwszych kadrach filmu wybuch miech. Analogia Przyrzd t potraw tak jak poprzednio, ale dodaj wicej wina. Podanie cechy wyrniajcej yrafy wyrniaj si dug szyj Wprowadzenie opisu cech bd podklas d bya do dua, biaa, z biaoniebieskim aglem Przedstawienie moliwego cigu zdarze Jeli Piotr wrci wczenie, to nam wszystko opowie. Alternatywa Moemy pj do kina lub do kawiarni. Skutek Nacinicie tego przycisku spowodowao wybuch. Przypuszczenie To byo chyba w maju. Wniosek Nie przyjechae, wic Krzy si obrazi. TEXT, schematy Przy uyciu powyszej klasyfikacji zda zdefiniowane zostay

nastpujce schematy przebiegu wypowiedzi: identyfikacja, opis na podstawie cech czci skadowych, opis cech, opis porwnujco-rnicujcy. Schematy opisano jako sekwencje zda o okrelonych kategoriach, przy czym na jednej pozycji moe w sposb alternatywny pojawi si kilka typw zda. Schemat identyfikacji Identyfikacja { Analogia/ Opis cech/ Atrybut/ Przemianowanie/ Przykad} * Przykad szczegowy/ Potwierdzenie + {} opcjonalno, / alternatywa * powtrzenie zero lub wicej razy, {Podkrelenie/ Analogia/ Opis atrybutu} + powtrzenie co najmniej raz, {Przykad szczegowy/ Potwierdzenie} Przykad tekstu, ktry powsta jako odpowied na pytanie: Co to jest statek?

Statek to jednostka pywajca po powierzchni. Moliwoci przewozowe opisane s przez atrybuty bazy danych DISPLACEMENT i DRAFT. Inne opisujce statek atrybuty to: MAXIMUM_SPEED, PROPULSION, FUEL (FUEL_CAPACITY, FUEL_TYPE). Na przykad DOWNES ma MAXIMUM_SPEED 29, PROPULSION - STMTURGD. TEXT - Planowanie treci wypowiedzi wybr adekwatnego do pytania podzbioru bazy wiedzy. pytania o definicj lub o podanie wszystkich znanych faktw: z bazy wiedzy wydzielany jest fragment zawierajcy dany obiekt, jego atrybuty i czci skadowe oraz obiekty w stosunku do niego nadrzdne. pytania o rnic: dobr informacji zaley od wzajemnego pooenia w hierarchii rozpatrywanych obiektw. Dla elementw pooonych blisko siebie wyznaczany jest podzbir zawierajcy wszystkie ich atrybuty. W przeciwnym przypadku wybierane s tylko atrybuty klas, do ktrych nale wskazane obiekty. TEXT - Planowanie postaci wypowiedzi

Schematy przypisane do typw pyta pytanie o definicj: schemat identyfikacji albo opis czci skadowych pytania o informacj: schemat opisu cech lub czci skadowych. pytania o rnice pomidzy dwoma obiektami: schemat porwnawczo-rnicujcy Wybr schematu zaley od tego, jakie informacje na temat wskazanego obiektu zawarte s w bazie wiedzy. pytania o definicj: schemat opisu czci skadowych wybierany jest wtedy, gdy o samym obiekcie dostpnych jest mniej informacji ni o jego czciach. Wybr w ramach schematu Wybr alternatywnych moliwoci w ramach schematu dokonywany jest wedug zasad sterujcych wyborem tematu kolejnego zdania. [Sinder 79,83].

informacje dotyczce tematu wypowiedzi: biecy temat, lista obiektw mogcych sta si tematem kolejnego zdania stos zawierajcy wszystkie poprzednie tematy. Tematem kolejnego zdania moe by: obiekt, ktry by tematem poprzedniej wypowiedzi, obiekt, ktry zosta wprowadzony w poprzednim zdaniu, obiekt, ktry by tematem ktrego z wczeniejszych zda, obiekt zwizany z innym, speniajcym ktry z powyszych warunkw. Wybr w ramach schematu, cd. Wybr konkretnej moliwoci zaley od celu, jaki chce osign mwca, np.: kontynuacja rozmowy na ten sam temat, rozpoczcie rozmowy na temat wprowadzony w ostatnim zdaniu, powrt do poprzednio omawianych kwestii. Rozwizanie przyjte w systemie TEXT: jeeli istnieje moliwo zmiany tematu to system jej dokonuje,

w przypadku wyboru pomidzy tematem biecym, a ktrym z tematw wczeniejszych system pozostaje przy temacie biecym. Ostateczne sformuowanie wypowiedzi Przypisanie informacji pochodzcych z bazy wiedzy do poszczeglnych zda konstruowanego akapitu. Z kadym typem zdania zwizana jest specyfikacja rodzaju informacji, ktra moe stanowi jego tre. Sposb przyporzdkowania zaleny jest od zastosowania. Nie zaley natomiast od schematu bazy danych. Implementacja schematw: automat, w ktrym stany odpowiadaj pozycjom w schemacie, a uki wyborowi moliwoci. testowanie wszystkich moliwoci na jeden krok naprzd. w kadym stanie odbywa si ewaluacja wszystkich moliwoci, funkcje okrelajce sposb wyboru najlepszej zawieraj zasady wyznaczania tematu nastpnego zdania RST - teoria opisu struktury

wypowiedzi Teoria struktury retorycznej RST (Rhetorical Structure Theory) (Mann, 1988). okrelenie funkcji penionych przez poszczeglne elementy skadowe tekstu poprzez zbudowanie hierarchii ich wzajemnych zalenoci. formalizm ten sta si podstaw kilku praktycznych rozwiza problemu generowania wypowiedzi (m.in. Hovy, 1990; Moore & Swartout, 1991). W stosunku do metody opisu tekstw za pomoc schematw RST zapewnia wiksz rnorodno tworzonych konstrukcji, umoliwia te bezporednie uzalenienie postaci wypowiedzi od celu, jaki chce osign rozmwca. Relacja RST RST opisuje teksty w kategoriach relacji pomidzy ich elementami skadowymi. Kada relacja dotyczy dwch obiektw, z ktrych jeden traktowany jest jako gwny ( nucleus), a drugi jako zaleny (satelite).

Element gwny moe wystpi samodzielnie, natomiast uycie w wypowiedzi tylko elementu zalenego jest niewaciwe. relacja nucleus 1-n satelite n+1 - m element zaleny mona zastpi innym bez szkody dla spjnoci tekstu, zamiana elementu gwnego ma zazwyczaj zasadniczy wpyw na sens caoci. np. wyjanienie jakiego faktu moe zawiera jeden z wielu moliwych sposobw tumaczenia, rne argumenty, ale temat wyjanie jest stay. Skadowe relacji RST warunki, ktre musi spenia obiekt gwny, warunki, ktre powinien spenia element zaleny, zalenoci pomidzy obydwoma obiektami, efekty powodowane przez zastosowanie opisywanej relacji (obl.) Przykadowo relacja wiadectwa (evidence) dotyczy sytuacji, w ktrej budowane

zdanie ma przekona odbiorc o prawdziwoci jakiego faktu. Obiektem gwnym relacji jest goszona teza, a elementami zalenymi argumenty j potwierdzajce. Odpowiednie warunki zdefiniowane s nastpujco: odbiorca nie jest pewny prawdziwoci faktu, odbiorca jest przekonany o susznoci argumentu, zrozumienie argumentu powikszy wiar odbiorcy w fakt. Efekem zastosowania powyszej relacji jest wzrost przekonania odbiorcy o prawdziwoci faktu. Analiza tekstu w terminach RST Analiza tekstu to okrelenie relacji zachodzcych midzy ssiadujcymi ze sob blokami tekstu; utworzona w ten sposb struktura musi by drzewem. Zdefiniowane w powyszy sposb relacje stanowi element skadowy schematw reprezentujcych budow wikszych fragmentw tekstu. Przykadowe schematy to: okoliczno, to, uwiarygodnienie, warunek, interpretacja. Poszczeglne schematy mog zawiera jedn lub wicej relacji. W wersji oryginalnej teoria zawieraa definicje nastpujcych relacji: okoliczno, rozwinicie, umoliwienie, wiadectwo, zamierzona przyczyna,

zamierzony rezultat, antyteza, warunek, interpretacja, ponowne stwierdzenie, nastpstwo, rozwizanie, to, motywacja, potwierdzenie, niezamierzona przyczyna, niezamierzony rezultat, ustpstwo, inaczej, ewaluacja, podsumowanie, kontrast, sposb, porwnanie, wkad, poczenie Przykadowa analiza tekstu 1. W opinii X spadek cen na giedzie by przesadny. 2. 3. 4. 5. 6. Przyczyn tego by wzrost stp procentowych wielu bankw amerykaskich. Ale sceptycyzm jest nadal wysoki. Trudno jest teraz przekona kogo do inwestycji na Wall Street. Moliwe jednak, e rynek zareaguje pozytywnie na wystpienie przew. BRF, ktry podkreli, e bank rezerw nie wzmocni swoich warunkw kredytowych. concession 1-2 backgroud

3 4 cause 6 3-6 bacground 5-6 elaboration 1 2 5 Uwagi oglne Struktury RST zawieraj jedynie cz informacji zwizanej z danym tekstem s reprezentowane powizania midzy poszczeglnymi frazami wchodzcymi w skad wypowiedzi. brak - danych dotyczcych uycia konkretnych konstrukcji jzykowych, kolejnoci poszczeglnych elementw, zasad uzgadniania cech gramatycznych.

Pierwotn funkcj RST byo opisywanie struktury ju istniejcych tekstw. Przy generowaniu wymagane jest narzucenie pewnych warunkw na zasady czenia relacji tak, by tworzony tekst by spjny. Jednym z podstawowych problemw zwizanych z RST jest ustalenie listy relacji, ktre mog zachodzi midzy poszczeglnymi fragmentami tekstu (prba systematyki: Hovy (1990), okoo 350 rnych relacji pochodzcych z prac 25 osb) Porwnanie relacji RST i schematw Zalety schematw: dua czytelno oraz atwo ich definiowania i wykorzystania. Analizujc schemat widzimy od razu (oczywicie w pewnym przyblieniu) struktur kocowego tekstu. Relacje RST tworz zbir oddzielnych regu opisujcych poszczeglne zdania. Powizania wyraone s za pomoc elementw zalenych i porednio poprzez warunki stosowania relacji. Okrelenie struktury wikszych fragmentw tekstu

wymaga wic przeledzenia wielu relacji, trudno te wskaza konsekwencje zmiany poszczeglnych definicji. Porwnanie relacji RST i schematw, cd Zalet relacji RST jest konstruowanie drzewa opisujcego struktur retoryczn tekstu tzn. zalenoci pomidzy poszczeglnymi jego elementami. Za pomoc RST mona kontrolowa struktur mniejszych fragmentw tekstu, nie koniecznie caych paragrafw. Z drugiej strony ustalenie struktury paragrafu przy wykorzystaniu RST jest znacznie trudniejsze. Korzystne byoby poczenie obu technik budowy tekstu, co mona osign poprzez pewne ograniczenia narzucone na wybr relacji. Takie rozwizanie zaproponowa np. Hovy (1991) Hovy, 1991

modu budujcy drzewo struktury paragrafu tekstu, ktry przekaza ma wybrane uprzednio informacje. relacje RST -- plan opisujcy zalenoci, jakie musz zachodzi pomidzy elementami, by mogy by uyte do jego realizacji. Na przykad tekst odpowiadajcy relacji circumstance pomidzy faktami X i Y mona skonstruowa, jeeli Y stanowi opis czasu lub pooenia X. W oryginalnej koncepcji RST kada relacja moga by w dowolny sposb poczona z innymi --> niespjno tworzonej wypowiedzi. Ograniczenia na sposb czenia relacji -- tzw. punkty rozszerzania (growth points) zawierajce list relacji, ktre mog by uyte w kolejnym kroku planowania postaci generowanego tekstu. Tworzenie wypowiedzi Hierarchiczne rozwijanie planu a do wykorzystania wszystkich wyselekcjonowanych elementw zgodnie z nastpujcym schematem: pobranie kolejnego punktu rozszerze ze stosu, wyszukiwanie relacji speniajcych opisane w nim warunki, dopasowanie odnalezionej relacji do rozpatrywanego punku

rozszerze, doczenie nowej relacji do drzewa (o ile dopasowanie powiodo si). Tworzenie wypowiedzi, cd Jeeli wicej ni jedna relacja spenia wymagane warunki tworzone jest alternatywne drzewo struktury wypowiedzi. Proces koczy si gdy zabraknie danych lub gdy adne ze zbudowanych drzew nie moe zosta rozszerzone. Jako ostateczny wynik wybierane s drzewa, ktre zawieraj najwicej informacji, a z nich te, dla ktrych zostao najmniej niezrealizowanych punktw rozszerze. Jeeli wicej ni jedno drzewo spenia te warunki, to wyboru dokonuje si poprzez losowanie. Dziaanie opisywanego systemu przedstawimy na podstawie przykadu dotyczcego ruchu okrtw marynarki wojennej. Przykad, dane wejciowe ((SHIP.EMPLOYMENT A105)

Statek o nazwie Knox, w stanie gotowoci (SHIP.R A105 Knox) C4 znajduje si w drodze do Sasebo, gdzie (SHIP.COURSE.R A105 195) dopynie 24 kwietnia 1987 i bdzie w trakcie (CURRENT.POSITION.R A105 P102) zaadunku przez 4 dni. Aktualne pooenie statku to 18N, 79E, orientacja SSW. (POSITION P102) (LONGITUDE.R P102 79) (LATITUDE.R P102 18) (READINESS.LEVEL.R A104 C4) (NEXT.MAJOR.EMPLOYMENT.R A105 E107) (CURRENT.MAJOR.EMPLOYMENT.R A105 E107) (ENROUTE E105) (EBEG.R E105 8700420) (EEND.R E105 8700424) (DESTINATION.R E105 SASEBO) (LOAD E107) (EBEG.R E107 8700425) (EEND.R E107 8700428) Przykad, cd. grupowaniu informacji dotyczcych tych samych cech i ewentualnemu utworzeniu struktur odpowiadajcych faktom zoonym.

W podanym przykadzie rezultatem tego procesu jest nastpujcy zbir opisw, z ktrych kady bdzie nastpnie wyraony za pomoc zdania. ((ENROUTE E105) (SHIP.R E105 KNOX) (DESTINATION.R E105 SASEBO) (HEADING.R E105 HEADING416) (READINESS.R E105 READINESS408) (NEXT-ACTION.R E105 ARRIVE400)) ... Zamy, e celem przygotowywanej wypowiedzi jest uwiadomienie suchaczowi pozycji statku E105, co zapisywane jest w nastpujcy sposb: (BMB SPEAKER HEARER (POSITION-OF E105 ?NEXT) BMB oznacza obustronn wiar mwcy i adresata wypowiedzi (hearer and speaker mutually belive that ...). Wyznaczony cel dopasowywany jest do pozycji efekt wszystkich zdefiniowanych w systemie planw/relacji RST. W tym przypadku jedynym planem realizujcym wyznaczony cel jest plan

odpowiadajcy relacji sekwencji, ktry przedstawia si nastpujco: Relacja SEQUENCE efekt: ((BMB SPEAKER HEARER (POSITION-OF ?PART ?NEXT))) warunki dla poczenia elementu gwnego i zalenego: (BMB SPEAKER HEARER (NEXT-ACTION.R ?PART ?NEXT))) warunki dla elementu gwnego: (BMB SPEAKER HEARER (TOPIC ?PART)) punkty rozszerze dla elementu gwnego: ((BMB SPEAKER HEARER (CIRCUMSTANCE-OF ?PART ?CIR)) ~(BMB SPEAKER HEARER (ATTRIBUTE-OF ?PART ?VAL)) ~(BMB SPEAKER HEARER (PURPOSE-OF ?PART ?PURP))} warunki dla elementu zalenego: ((BMB SPEAKER HEARER (TOPIC ?NEXT))) punkty rozszerze dla elementu zalenego:

((BMB SPEAKER HEARER (ATTRIBUTE-OF ?NEXT ?VAL)) ~(BMB SPEAKER HEARER (DETAILS-OF ?NEXT ?DETS)) ~(BMB SPEAKER HEARER (POSITION-OF ?NEXT ?FOLL)) Relacja SEQUENCE, cd. porzdek: N S warunek aktywacji: Czy A moe zosta zaprezentowany jako element pewnego acucha akcji, czy odbiorca powinien wiedzie, e A stanowi fragment takiej sekwencji? frazy czce: ``~'' ``then'' ``next' W kolejnym kroku odszukiwane s elementy, ktre speniaj warunki opisujce poczenie elementu gwnego i zalenego. Po przypisaniu dokonanym podczas dopasowywania celu pocztkowego: (BMB SPEAKER HEARER (NEXT-ACTION.R ?PART ?NEXT))) (BMB SPEAKER HEARER (NEXT-ACTION.R E105 ?NEXT)) (BMB SPEAKER HEARER (NEXT-ACTION.R E105 ARRIVE400)) Tworzenie planu Nastpnym krokiem realizacji wybranego planu jest rozpatrzenie punktw

rozszerze. Pierwszym z nich jest: (BMB SPEAKER HEARER (CIRCUMSTANCE-OF E105 ?CIRC)) pasujcy do pola efekt relacji circumstance. nazwa: CIRCUMSTANCE efekt: ((BMB SPEAKER HEARER (CIRCUMSTANCE-OF ?X ?CIRC))) sprawdzamy warunku uwzgldniajc przypisanie ?X do E105, uzyskujc m.in: (BMB SPEAKER HEARER (HEADING.R E105 HEADING416)) Pozwala to na sformuowanie nowej relacji circumstance pomidzy elementami E105 i HEADING416, ktr mona doczy do poprzednio zbudowanej relacji sequence: Tworzenie planu, cd sequence E105

ARRIVE400 circumstance E105 sequence ARRIVE400 HEADING416 W trakcie przebudowy drzewa niezrealizowane punkty rozszerze relacji sequence przenoszone s do elementu gwnego relacji circumstance, co umoliwia dalsz rozbudow drzewa w wle E105. Punkty rozszerze dla elementu zalenego dodawane s do listy niezrealizowanych rozszerze. Tworzenie planu, cd Dalszy cig procesu planowania wypowiedzi przebiega nastpujco:

punkt rozszerze relacji sequence wypeniany jest przez relacj elaboration-attribute pomidzy elementami E105 i READINESS408, punkt rozszerze relacji circumstance wypeniany jest przez relacj elaboration-attribute pomidzy elementami HEADING416 i POSITION410, punkt rozszerze elementu zalenego ARRIVE400 wypeniany jest przez relacj sequence wic go z elementem E107 Tworzenie planu, cd Proces planowania koczy si, gdy wszystkie elementy zbioru wejciowego zostan wyczerpane. Wynik: sequence circumstance elab-attrib E105 elab-attrib RDNSS408 sequence ARRIVE400 E107

POSTN410 HEADING416 Knox, which is C4, is en route to Sasebo. It is at 18N 79E, heading SSW. (Knox, w stanie gotowoci C4 jest w drodze do Sasebo. Jego pozycja to 18N, 79E, orientacja SSW.) Ostateczne formuowanie tekstu Dwa najbardziej znane podejcia: gramatyka systemowa (systemic grammar, Halliday, 1985) gramatyka w formie acyklicznej sieci wyborw funkcyjna gramatyka unifikacyjna (Functional Unification Grammar, Kay, 1979) Ujednoznacznianie sw (WSD, Word sense disambiguation) Wyszukiwanie informacji (dokumentw tekstowych) (IR, Information Retrieval) Natural Language Information Retrieval, T. Strzakowski (ed.), Kluwer Academic Press. 1999

Powizania midzy sowami homonimy - jednakowy ksztat sowa, rne znaczenia np. pokj (pomieszczenie) i pokj (przeciwiestwo wojny) homofony - jednakowe brzmienie sw, rna pisownia, znaczenie np. moe, morze polisemia - wielo powizanych znacze jednego sowa np. gra (pitro domu, cz ubrania ...) Synonimy - rne leksemy o tym samym (prawie) znaczeniu (mogce si nawzajem zastpi w pewnym kontekcie) hyponimy - leksemy o szerszym znaczeniu np. pojazd mechaniczny vs. samochd, Zadania:

ustalenie ile i jakich znacze posiada dane sowo rozpoznawanie w jakim konkretnym znaczeniu wystpio dane sowo - word sense disambiguation taksonomia, hierarchia poj WordNet - baza danych o znaczeniach sw Utworzona rcznie baza zawierajca opisy i powizania semantyczne dla sw danego jzyka (pierwszy by angielski, nie ma jeszcze dla polskiego) zakres WordNet 1.6 dla angielskiego liczba form rzeczowniki czasowniki przymiotniki przyswki liczba znacze

94474 116317 10319 22066 20170 29881 4546 5677 WordNet nie zawiera sw z klas zamknitych, np. spjnikw w praktyce mao sw ma wiele znacze Przykadowy opis znacze Fragment opisu rzeczownika bass w bazie WordNet: 1. bass - the lowest part of the musical range 2. bass, bass part - the lowest part in polyphonic music 3. bass, basso - an adult male singer with the lowest voice 4. sea bass, bass - flesh of lean-flesh saltwater fish 5. fresh water bass, bass - any of varoius North American lean-fleshed freshwater fishes 6. bass, bass voice, basso ... 7. bass ... 8. bass ... Relacje w WordNet Rzeczowniki Rzeczowniki relacja hypernym

hyponym has-member >profesor member-of has-part part-of antonym definicja pojcie -> pojcie nadrzdne pojcie-> pojcie podrzdne grupa -> czonek przykad breakfast->meal meal -> lunch katedra- czonek ->grupa ma czci jest elementem jest przeciwiestwem pilot -> zaoga st -> blat talerz -> serwis pierwszy ->ostatni

Przykadowy opis hiponimii Sense 3 bass, basso -- (an adult singer with the lowest voice) => singer, vocalist => musician, instrumentalist, player => performer, performing artist => entertainer => person, individual, someone ... => life form, organism, being ... => entity, something => causal agent, cause, causal agency => entity, something Role, FrameNet Rola AGENT EXPERIENCER FORCE THEME RESULT CONTENT INSTRUMENT BENEFICIARY SOURCE GOAL

przykad Kot rozla mleko. Jana boli gowa. Wiatr zama drzewo. Kiedy rozbi ld. (uczestnik dowiadczajcy skutkw) Wybudowa dom. Jan spyta Bye tam sam?. Uderzy go kijem. Kupi mu dom. Przylecia z Parya. Poszed do szkoy. Selekcja znacze - ograniczenia na role *I wanna eat someplace thats close to ICSI. I wanna eat some really cheap Chinese food right now. AGENT THEME I /I *someplace ... / ...food Czasownik eat wymaga, by w roli THEME wystpowa

obiekt jadalny Formuowanie ogranicze Przedmiot dla czasownika eat musi by jadalny: Logika pierwszego rzdu: e,x,y eating(e) Agent(e,x) Theme(e,y) Isa(y,EdibleThing) Hierarchia hiponimii w WordNet Theme {food, nutrient} (jeden z 60000 klasyfikatorw, te pojcia musza znale si w hierarchii) hamburger, beefburger -- (a fried cake of minced meet served on a ban) => sandwich => snack food => dish => nutriment, nourishment, sustenance ... =>food nutrient => substance, matter => object, physical object => entity, something Problemy z ujednoznacznianiem Rne ograniczenia na typ argumentw mog pomc przy ujednoznacznianiu przykadw: Which airlines serve Denver? - Pojed do serwisu.

Which one serves breakfast? - Uyj tego granatowego serwisu. Ale: niedostateczny kontekst: Jaki serwis polecasz? Sytuacje niecodzienne On naprawd zjad szklank ! Przeczenie ale zota nie dao si je Bajki dla dzieci, sny...: ni mi si latajcy krokodyl, piama w rowe sonie Ujednoznacznianie Reguy probabilistyczne niczego (prawie) nie wykluczamy cakowicie, podajemy preferencje algorytm podaje to znaczenie, dla ktrego prawdopodobiestwo jest w danym kontekcie najwiksze odpowiednia metoda dla niejednoznacznych czasownikw, ale przy jednoznacznych argumentach Metody machine learning uczenie si na podstawie korpusw anotowanych morfologicznie znajdowanie kontekstw uycia i wyznaczanie prawdopodobiestw dla poszczeglnych znacze Information Retrieval (IR)

Indeksowanie, wyszukiwanie dokumentw tekstowych Wyszukiwanie dokumentw w sieci WWW to obecnie jedna z najczstszych operacji Problemy: wyszukanie waciwych dokumentw efektywne wyszukiwanie w bardzo duych zbiorach Zadanie: Majc: - korpus tekstw pytanie uytkownika Wyznaczy: uporzdkowany zbir dokumentw stanowicy odpowied NLP: powizania z IR NLP to syntaktyczna, semantyczna i pragmatyczna analiza tekstu w jzyku naturalnym, znajomo struktury syntaktycznej i interpretacji semantycznej powinna pozwoli na wyszukiwanie sterowane semantyk, a nie tylko sowami kluczowymi,

Moliwoci powiza: metody ustalania znaczenia sw w oparciu o kontekst (word sense disambiguation), metody identyfikacji informacji w tekcie (information extraction), udzielanie odpowiedzi na podstawie analizy korpusu tekstw. Sowa kluczowe proste okrelenie poprawnoci odpowiedzi - tekst pytania (sowa kluczowe) wystpuje w dokumencie inne kryterium - sowa kluczowe wystpuj w dokumencie czsto, w dowolnej kolejnoci (bag of words) ew. wymagamy, eby byy blisko siebie Problemy z wyszukiwaniem wg sw kluczowych: synonimy: restaurant vs. caf PRC vs. China

terminy wieloznaczne: bat (baseball vs. mammal) - kostka (cukru, nogi) Apple (company vs. fruit) - na prawo bit (unit of data vs. act of eating) - rzd (polski, drzew) Trafno (relevance) Trafno (odpowiednio) jest miar subiektywn. Moe dotyczy m.in.: waciwego tematu, aktualnoci danych, wiarygodnoci danych (pochodzenia z wiarygodnego rda), zaspokojenia potrzeb uytkownika (information need). Inteligentne metody IR musz bra pod uwag: znaczenie uytych w pytaniu sw, porzdek sw w pytaniu, reakcje uytkownika (bezporedni bd poredni feedback), wiarygodno rda informacji. Skadowe systemu IR

Text Operations utworzenie listy sow, wedug ktrej robiony bdzie indeks (tokens). Usunicie sow nieznaczcych (Stopword removal) wyznaczenie form bazowych (Stemming) Indexing skonstruowanie indeksu od sw do dokumentw (an inverted index of word to document pointers). Searching odszukanie dokumentw zawierajcych tokeny z pytania. Ranking przypisanie dokumentom wagi. Skadowe systemu IR (cd) User Interface - interakcja z uytkownikiem : Query input and document output. Relevance feedback. Visualization of results.

Query Operations - przeksztacenie pytania dla zwikszenia skutecznoci wyszukiwania: rozszerzenie pytania przy wykorzystaniu tezaurusa przeksztacenie pytania na podstawie otrzymanej informacji zwrotnej Wyzwania sieci www dla IR Distributed Data: dokumenty ulokowane na milionach serwerw Volatile Data: wiele dokumentw nagle pojawia si lub znika Large Volume: bardzo wiele oddzielnych dokumentw Unstructured and Redundant Data: brak jednolitej struktury, bdy HTML, do 30% (prawie) powielonych dokumentw

Quality of Data: brak kontroli edytorskiej, nieprawdziwe informacje, kiepskiej jakoci teksty, etc. Heterogeneous Data: wiele typw danych (obrazy, filmy, ...) jzykw, zbiorw znakw Liczba indeksowanych stron www SearchEngineWatch, Aug. 15, 2001 Google lists current number of pages searched. Prawo Zipfa Niech Rank (r) bdzie pozycj sowa na licie posortowanej wedug malejcych czstoci. Zipf (1949) odkry e: czsto wystpowania obserwacji r , wyraona jako funkcja jej pozycji na licie czstoci (r) jest wyraana funkcj 1 Pr ~ 1/ra gdzie a jest bliskie jednoci.

f f r k (for constant k ) r jeeli prawdopodobiestwo wystpienia sowa o pozycji r wynosi pr, af N jest A liczb wszystkich wystpie wszystkich for corpus indp. const. A 0.1 r sw,pto: N r Prawo Zipfa a przydatno sw dla indeksowania Zarwno sowa wystpujce bardzo czsto, jak i te wystpujce bardzo rzadko, s mao przydatne z punktu widzenia indeksowania, Luhn

(1958). Prawo Zipfa a korpus Browna k = 100,000 Prawo Zipfa a sie Web Rozkad Zipfa charakteryzuje m.in.: liczb powiza do i ze strony www dugo stron www liczb odwoa do strony www Automatyczna klasyfikacja dokumnetw Rczna klasyfikacja jest pracochonna, subiektywna i obarczona bdami potrzebne s metody automatycznej kategoryzacji dokumentw najlepsze metody oparte s metodach machine learning (pattern recognition) przy wykorzystaniu poetykietowanego

zbioru treningowego (supervised learning). Automatyczne tworzenie hierarchii dokumentw Do klasyfikacji dokumentw potrzebne s hierarchie typw rczne towrzenie hierarchii jest ... pracochonne, subiektywne i obarczone bdami potrzebne sa metody automatycznego tworzenia hoierachii na podstawie zbioru dokumnetw metoda - hierarchical text clustering (unsupervised learning) (Hierarchical Agglomerative Clustering, HAC) IR, Vector Space Model Dokumenty i pytania przedstawiane s w postaci wektorw cech reprezentujcych wystpujce obiekty (dokadniej warto cechy okrela, czy dany obiekt wystpuje czy nie w danym dokumencie) dokument j -- dj = (t1,j , t2,j, ..., tN,j) pytanie k

-- qk = (t1,k , t2,k, ..., tN,k) w wektorach powyej zamiast 0,1 umieszczamy liczby oddajce czstoci dokumenty i pytania s wektorami w przestrzeni N-wymiarowej dla uatwienia porwna normalizujemy wektory, dzielimy kad wsprzdn przez dugo wektora, tj. wi2 i=1,,N IR, Vector Space Model, cd. Odlego midzy znormalizowanymi wektorami: sim(qk, dj) = qk . dj =

wi,k x wj,k (dot product) i-1..N wyznacza cosinus kta midzy wektorami, takie same wektory kt 0 cosinus 1, wektory prostopade, bardzo odlege, cosinus 0. IR, Vector Space Model, cd. Wartoci istotne dla modelu: czsto wystpowania sowa w tekcie dystrybucja sowa w zbiorze tekstw sowa wystpujce rzadko (tylko w niewielu tekstach) dobrze nadaj si do wyboru tego wanie podzbioru sowa czsto wystpujce s niedobre do selekcji czegokolwiek IR, Vector Space Model, cd. Miara przydatnoci obiektw (termw): N/ni N - liczba dokumentw w kolekcji ni - liczba dokumentw, w ktrych wystpuje ni

(1 - term wystpuje we wszystkich dokumentach) idf i = log(N/ni) (inverse document frequency) wi,j = tf i,j x idf i (tfi,j czsto termu i w dokumencie j) Wybr termw Stop lista sowa wystpujce czsto, spjniki ... ale (to be or not to be) -> not (Brown corpus, za Frakes, Baeza-Yates)) ustalenie tematw sw (stemming) - nieodzowny dla jzyka fleksyjnego, ale bardzo trudny przy wielu wymianach tematowych (ma - temat pusty) Poprawianie pyta Stopniowe tworzenie odpowiedzi (relevance feedback)

may zbir odpowiedzi pocztkowych, reakcja uytkownika okrelajcego, ktre z tej grupy s najlepsze iteracja (czsto tylko jeden krok interakcji wystarcza) rozszerzenie pytania (query expansion) dodanie termw pokrewnych tym z pytania (w oparciu o tezaurusy) Ocena wynikw Precyzja Precision = Peno Recall = liczba podanych waciwych dokumentw liczba wszystkich waciwych dokumentw liczba podanych waciwych dokumentw

liczba wszystkich podanych dokumentw Search Results Clustering Definicja problemu: efektywne utworzeniu sensownych grup tematycznie powizanych dokumentw, oraz zwizy opis w sposb zrozumiay dla czowieka Problem nie jest trywialny nie jest znana liczba oczekiwanych grup miara podobiestwa dokumentw jest trudna do zdefiniowania grupy mog si nakada znalezienie opisu dla grup nie jest proste wymagana szybko wykonywania (on-line) dokumenty mog by wielojzyczne opisy s zazwyczaj krtkie (snippets) i niepene Modelowanie podobiestwa modelowanie odlegoci w przetrzeniach n-wymiarowych (Vector Space Model) model grafowy wspwystpowanie sw i fraz

Pojcie bliskoci w macierzy A: jestemy zainteresowani ktem jaki tworz midzy sob wektory dokumentw identyczny kt -> dokumenty zoone s z identycznych sw -> dokumenty s podobne Przykad macierz A Algorytmy grupowania a macierz A wykorzystanie informacji o bliskoci dokumentw w A zastosowanie maj wszelkie metody analizy skupie w danych numerycznych problemy grupy zazwyczaj sferyczne kade sowo jest traktowane oddzielnie problemy ze znalezieniem opisu grup problem z naturalnym kryterium stopu dla wikszoci algorytmw Algorytm STC wykorzystanie fraz Suffix Tree Clustering, Oren Zamir, O. Etzioni fraza = sekwencja wystpujcych po sobie sw

algorytm rozwaa wsplne podfrazy wystpujce w dokumentach zalety brak numerycznej miary odlegoci frazy stanowi zazwyczaj dobre opisy grup liniowa zoono - O(N) wady sabo radzi sobie z szumem problemy z separacj maych grup wraliwo na progi i jzyk dokumentw

Recently Viewed Presentations

  • Project Report - Lean Sigma

    Project Report - Lean Sigma

    Beginning or mid shift 5-10 minutes Lead by member of unit leadership team * SICU Huddle Board * Surgical Unit Huddle Board Lessons for Your Hospital: Strategies that Promote Nurses & Leverage CUSP Frontline staff are an integral part of...
  • Domestic Benefits Orientation

    Domestic Benefits Orientation

    Flexible Spending Accounts (FSA) Pretax savings vehicles for medical and dependent care. 2018 limits: Medical - $2,650/year. Dependent Care - $5,000/year. If you have contributed through another employer, your annual limit is across all FSA plans, so you will have...
  • Space News Update - January 20, 2017 In

    Space News Update - January 20, 2017 In

    Don't Judge an Asteroid by its Cover. In this computer graphic, NASA's Voyager 1 probe, moving toward upper left, nears the edge of the sun's influence, flying through a region of space dominated by a "magnetic highway" that helps mediate...
  • The Mexican Revolution: Intellectuals and the Arts

    The Mexican Revolution: Intellectuals and the Arts

    "Mexican culture during the period 1920 to 1940 came to the service of the Revolution. The artistic, literary, and scholarly communities, with an abiding faith in the new thrust of Mexican life, supported revolutionary ideals by contributing their unique talents...
  • 5S BASIC TRAINING - tocforme

    5S BASIC TRAINING - tocforme

    5S BASIC TRAINING What is 5S and why do we want to do it? 5S Some New Words New Words - Continued Some 5S Examples 5S Examples - Sort, Set in Order 5S Examples - Shine 5S Examples - Standardize...
  • An Introduction to - SMART Recovery

    An Introduction to - SMART Recovery

    This is the critical principle of SMART, and the cornerstone of the ABC process, which we use to test the rationality of our thoughts and beliefs. ... Post a message on our message board and introduce yourself! Attend an online...
  • Welcome to McGill

    Welcome to McGill

    myCourses. McGill Library Subject Guides for LIS. Working & work experience. McGill Work Study program. Writing, language, and academic support. Graphos - courses, peer writing groups, etc. Note: there may be fees involved for courses. Please read fine print and...
  • PaLRaP Copyeditor Training - D-Scholarship@Pitt

    PaLRaP Copyeditor Training - [email protected]

    "PaLRaP is 1st and foremost a peer reviewed journal for the research out put and best practices of PA's library community and we hope to maintain the strong presence of scholarly content in this journal. We may always have more...