1 Lingwistyka komputerowaZastosowanie automatów skończonych stanów w przetwarzaniu języków naturalnych Marcin Junczys-Dowmunt

2 Lingwistyka komputerowa Co to jest?Lingwistyka komputerowa zajmuje się przetwarzaniem języków naturalnych przy wykorzystaniu komputerów Przedmiot badań to zarówno język pisany (teksty) jak i mowa Synteza informatycznych i językoznawczych metod oraz wiadomości

3 Lingwistyka komputerowa Jedna nazwa - Wiele koncepcjiDyscyplina językoznawstwa (ang. computational linguistics) Dyscyplina wykorzystująca komputery do gromadzenia i przetwarzania danych lingwistycznych Dyscyplina realizująca zjawiska językowe na komputerach (ang. natural language processing) Inżynieria lingwistyczna (ang. language technology)

4 Lingwistyka komputerowa Nauka interdyscyplinarnaJęzykoznawstwo Informatyka Filozofia Sztuczna inteligencja Psychologia kognitywna Matematyka Teoria automatów Języki formalne Teoria grafów Statystyka Rachunek prawdopodobieństwa Logika matematyczna

5 Lingwistyka komputerowa Strona praktyczna oraz teoretycznaL.k. praktyczna Tworzenie formalizmów modelujących różne aspekty języków naturalnych Udostępnianie wiedzy o poszczególnych językach Tworzenie algorytmów i metod do przetwarzania wypowiedzi językowych Ewaluacja systemów lingwistycznych L.k. teoretyczna Badanie złożoności obliczeniowej formalizmów Badanie możliwości opisowych formalizmów Badania możliwości automatycznej nauki i kategoryzacji znaczących podzbiorów językowych

6 Lingwistyka komputerowa ZastosowaniaEkstrakcja informacji z dużych nieuporządkowanych źródeł np. Internet, archiwa elektroniczne itp. Interfejsy językowe do systemów informatycznych np. baz danych Automatyczne rozpoznawanie mowy i tekstów Generowanie mowy i tekstów np. syntezatory mowy Tłumaczenie maszynowe Systemy dialogowe np. zamawianie biletów przez rozmowę z automatem

7 Historia lingwistyki komputerowejLata 40te i 50te: Początki Koncepcja automatu (Turing 1936) Automaty skończone i zbiory regularne (Kleene 1951/1956) Modele Markova (Shannon 1948) Teoria języków formalnych (Chomsky 1956) Pojęcie entropii w teorii informacji (Shannon)

8 Historia lingwistyki komputerowej: Dwa podejścia Metody symboliczny Gramatyka generatywna Parsery syntaktyczne Stuczna inteligencja (AI) Metody statystyczne Metoda Bayes’a Optyczne rozpoznawanie liter Identyfikacja autorów tekstów

9 Historia lingwistyki komputerowej: Cztery paradygmaty Statystyczne modele (HMM do rozpoznawania mowy, synteza mowy) Logika formalna (Prolog, DCG, LFG) Rozumienie języków naturalnych (Winograd: Block World) Modelowanie dyskursu

10 Historia lingwistyki komputerowej: Odrodzenie modeli skończonych stanów i empiryzmu Morfologia i fonologia za pomocą modeli skończonych stanów (Kaplan & Kay 1981) Modele skończonych stanów składni (Church 1980) Metody stochastyczne wykraczają poza rozpoznawanie mowy (IBM)

11 Historia lingwistyki komputerowej: Połączenie sił Zastosowanie metod statystycznych w symbolicznych metodach analizy języka na wszystkich poziomach Wzrost potrzeby na systemy ekstrakcji informacji wraz z rozwojem Internetu Wzrost wydajności komputerów pozwala na komercyjne wykorzystanie wyników badań (rozpoznawanie mowy, korekcja ortografii i gramatyki)

12 Główny problem lingwistyki komputerowej: WieloznacznośćWieloznaczność na wszystkich poziomach systemu językowego Fonetyka: np. Homofonia Morfologia: np. Problem analizy części mowy, homonimia Składnia: np. Problem analizy części zdania Semantyka: np. Polisemia, Idiomy Pragmatyka: np. Metafory, Ironia Trzeba często korzystać z wyższego poziomu języka w celu rozstrzygnięcia wieloznaczności

13 Procesy przy przetwarzaniu mowySygnał Wiedza syntaktyczna Przetwarzanie sygnału Analiza składniowa Akustyczne wektory Hipotezy fraz Wiedza semantyczna Ekstrakcja cech Analiza semantyczna Akustyczne cechy Hipotezy znaczeń Inwentarz jednostek Segmentacja Analiza pragmatyczna Wiedza pragmatyczna Hipotezy jednostek Słownik fonologiczny Lexical matching Zdanie i interpretacja Hipotezy słów

14 Gramatyki formalne Pojęcie gramatyki formalnej zostało wprowadzone przez N. Chomsky’ego Szerokie zastosowanie w językoznawstwie do określania nieskończonych podzbiorów języka naturalnego za pomocą skończonych środków Teoria g. f. rozwinęła się jako odrębna teoria matematyczna (lingwistyka matematyczna)

15 Według hierarchii Chomsky’ego:Gramatyki formalne Według hierarchii Chomsky’ego: Klasa 0: Gramatyki nieograniczone Klasa 1: Gramatyki kontekstowe Klasa 2: Gramatyki bezkonstekstowe Klasa 3: Gramatyki regularne (automatowe, skończenie stanowe)

16 Automaty skończone (FSA)Automat skończony (ang. Finite-State Automaton) to abstrakcja matematyczna, określa język formalny Składa się z skończonej ilości stanów i funkcji przejścia, która określa sposób przechodzenia od jednego stanu w inny Automat wczytuje pojedyncze symbole z taśmy wejściowej i w zależności od aktualnego stanu i wczytanego symbolu przechodzi w inny stan Automat jako akceptor – akceptuje wczytywany ciąg symboli, gdy należy do języka określonego przez dany automat, odrzuci w przypadku przeciwnym

17 Automaty skończone (FSA)Zapis formalny: M = ( Q, Σ, δ, q0, F ) Q - skończony zbiór stanów Σ - skończony alfabet wejściowy δ(q,a) - funkcja przejścia, gdzie q należy do Q, i gdzie a należy do Σ. Wynik δ(q,a) = q’, gdzie q’ należy do Q q0 - stan początkowy należący do Q F - zbiór stanów końcowych zawarty w Q

18 L(M) = { baa!, baaa!, baaaa!, baaaaa!, baaaaaa!, … }Przykład: Sheeptalk L(M) = { baa!, baaa!, baaaa!, baaaaa!, baaaaaa!, … } a b a a ! q0 q1 q2 q3 q4 Start δ a b ! q0 - q1 q2 q3 q4 q4: M = ( Q, Σ, δ, q0, F ) Σ = { a, b, ! } Q = { q0, q1, q2, q3, q4 } F = { q4 }

19 Przykład: Sheeptalk a b a a ! q0 q1 q2 q3 q4 Start q0 b a a a a !

20 Przykład: Sheeptalk a b a a ! q0 q1 q2 q3 q4 Start q1 b a a a a !

21 Przykład: Sheeptalk a b a a ! q0 q1 q2 q3 q4 Start q2 b a a a a !

22 Przykład: Sheeptalk a b a a ! q0 q1 q2 q3 q4 Start q3 b a a a a !

23 Przykład: Sheeptalk a b a a ! q0 q1 q2 q3 q4 Start q3 b a a a a !

24 Przykład: Sheeptalk a b a a ! q0 q1 q2 q3 q4 Start q3 b a a a a !

25 Przykład: Sheeptalk a b a a ! q0 q1 q2 q3 q4 Start q4 b a a a a !

26 Wady i zalety modeli skończenie stanowychBraki pod względem ekspresywności w porównaniu z językami wyższych klas Uważa się, że języki naturalne nie są regularne (ale pewne podzbiory są!) Modele skończenie stanowe nie wnoszą wiele do wiedzy o językach naturalnych Zalety: Matematycznie dogłębnie zbadane Kompaktowa reprezentacja (Minimalizacja) Dobre własności obliczeniowe (Determinizacja) Prostota konstrukcji ze względu na własności zamknięcia

27 Maszyny skończone w przetwarzaniu języków naturalnychModelowanie słowników Przetwarzanie mowy Analiza morfologiczna Analiza składniowa wybranych podzbiorów języków naturalnych Modelowanie gramatyk skończenie stanowych przybliżonych do gramatyk o większych możliwościach generatywnych

28 FSA w morfologii/fonologiiDystrybucja Zbiór otoczeń (kontekstów) w jakich dany element językowy może występować. Istnieją znaczne ograniczenia Morfotaktyka Opis ciągów morfemów współtworzących wyraz. Rodzaj składni międzymorfemowej. Morfofonologia/Fonotaktyka Teoria alternacji morfologicznej. Teoria fonologicznej struktury morfemów.

29 Przykłady z Lingwistyki komputerowejUproszczone słowotwórstwo niektórych polskich wyrazów stół -ek q0 stoł q1 q4 Start -ołowy q2 -arz stol -ka mal q3 -ar -stwo

30 Przykłady z Lingwistyki komputerowejUproszczona fleksja niektórych angielskich czasowników q0 Start reg-verb-stem q1 q3 q2 irreg-verb-stem 3sg (-s) pres-part (-ing) past-part (-ed) past (-ed) irreg-past-verb-stem reg-verb-stem irreg-verb-stem irreg-past-verb-stem past past-part pres-part 3sg walk work catch speak caught spoke -ed -ing -s

31 Przykłady z Lingwistyki komputerowejUproszczona fleksja niektórych niemieckich czasowników q0 Start q1 q2 wat q3 bet hast et ε en e est

32 Przykłady z Lingwistyki komputerowejUproszczona morfologia niemieckich złożeń rzeczownikowych q0 Start q1 q3 q2 N I

33 Automaty skończone jako słownikiWspólne przedrostki dla każdego hasła (drzewo deterministyczne, drzewo Trie) Dodatkowo wspólne przyrostki po minimalizacji drzewa Trie Jeżeli informacje dołączone do haseł zostają umieszczone w stanach końcowych, minimalizacja nie jest pełna – wspólne przyrostki przy wspólnych informacjach

34 Budowa słowników Drzewo deterministyczneL = { agencja, agent, agentka, bank, bat } Start

35 Budowa słowników Drzewo deterministyczneL = { agencja, agent, agentka, bank, bat } a g e n c j a Start 1 2 3 4 5 6 7

36 Budowa słowników Drzewo deterministyczneL = { agencja, agent, agentka, bank, bat } a g e n c j a Start 1 2 3 4 5 6 7 t 8

37 Budowa słowników Drzewo deterministyczneL = { agencja, agent, agentka, bank, bat } a g e n c j a Start 1 2 3 4 5 6 7 t 8 9 10 k a

38 Budowa słowników Drzewo deterministyczneL = { agencja, agent, agentka, bank, bat } a g e n c j a Start 1 2 3 4 5 6 7 t b 11 12 13 14 8 9 10 a n k k a

39 Budowa słowników Drzewo deterministyczneL = { agencja, agent, agentka, bank, bat } a g e n c j a Start 1 2 3 4 5 6 7 t b 11 12 13 14 8 9 10 a n k k a t 15

40 Budowa słowników Drzewo deterministyczneL = { agencja, agent, agentka, bank, bat } Suma liter w hasłach słownikowych: 26 a g e n c j a Start 1 2 3 4 5 6 7 t b 11 12 13 14 8 9 10 a n k k a t 15 Suma liter (przejść) w słowniku: 15

41 Budowa słowników Minimalizacja drzewaL = { agencja, agent, agentka, bank, bat } a g e n c j a Start 1 2 3 4 5 6 7 t b 11 12 13 14 8 9 10 a n k k a t 15

42 Budowa słowników Minimalizacja drzewaL = { agencja, agent, agentka, bank, bat } a g e n c j a Start 1 2 3 4 5 6 t b 7,10, 14,15 11 12 13 8 9 a n k a k t

43 Budowa słowników Minimalizacja drzewaL = { agencja, agent, agentka, bank, bat } Suma liter w hasłach słownikowych: 26 a g e n c j Start 1 2 3 4 5 a 6,8 t b 7,10, 14,15 11 12 13 8 a n k k t t Suma liter (przejść) w słowniku: 14

44 Siła automatów skończonych: Własności zamkniętościAutomaty skończone są: Zamknięte ze względu na sumę Zamknięte ze względu na konkatenację Zamknięte ze względu na domknięcie Kleene’ego Zamknięte ze względu na przecięcie Zamknięte ze względu na dopełnienie

45 Zamkniętość ze względu na sumęq0 ε q0’ Start q0 ε

46 Zamkniętość ze względu na domknięcie Kleene’egoε q0 ε ε

47 Zamkniętość ze względu na konkatenacjęq0 q0 ε ε

48 Zamkniętość ze względu na konkatenacjęq0 ε q0 ε

49 Przykłady z Lingwistyki komputerowejUproszczona morfologia niemieckich złożeń rzeczownikowych q0 Start q1 q3 q2 N I

50 Przykład na korzystanie z własności zamkniętości1 2 N M1 6 7 N M3 3 4 N 5 I M2

51 Przykład na korzystanie z własności zamkniętościε 1 2 N 6 7 M2 N I ε 3 4 5

52 Przykład na korzystanie z własności zamkniętościε 1 2 N 6 7 ε ε N I ε 3 4 5

53 Przykład na korzystanie z własności zamkniętościε ε 1 2 N 6 7 ε ε ε N I ε 3 4 5

54 Przykład na korzystanie z własności zamkniętości1 2 N 3 4 I

55 Przykład na korzystanie z własności zamkniętości1 2 3 I N

56 Przykład na korzystanie z własności zamkniętości1 2 N/N-ling M1 6 7 N M3 3 4 N/N-ling 5 I M2 8 N-ling -s-

57 Przykład na korzystanie z własności zamkniętości1 4 3 I N/N-ling 5 2 N-ling -s-

58 Zamkniętość ze względu na przecięcieFSA M1 FSA M2 wejście FSA M3 FSA M4

59 Zamkniętość ze względu na przecięcieFSA M1 FSA M2 wejście FSA M3 FSA M4

60 Rozszerzenie koncepcji: Transduktory (FST)Transduktor to automat skończony z wyjściem (odwzorowanie ciągów symboli) Transduktor dla każdego wczytanego symbolu z taśmy wejściowego dopisuje odpowiedni symbol do taśmy wyjściowej Interpretacja jako FSA z parami symboli jako etykiety Interpretacja jako podwójny FSA (FSA wejściowy, FSA wyjściowy) Transduktor jako akceptor i analizator ciągów symboli - sprawdza przynależność słowa do języka AS wejściowego i odwzorowuje ja na słowo języka AS wyjściowego

61 Zapis formalny: T = ( Q, Σ1, Σ2, δ, σ, q0, F )Transduktor (FST) Zapis formalny: T = ( Q, Σ1, Σ2, δ, σ, q0, F ) Q - skończony zbiór stanów Σ1 - skończony alfabet wejściowy Σ2 - skończony alfabet wyjściowy δ(q,a) - funkcja przejścia, gdzie q należy do Q, i gdzie a należy do Σ1. Wynik δ(q,a) = q’, gdzie q’ należy do Q σ(q,a) - funkcja wyjściowa. Wynik σ(q,a) = a’, gdzie a’ należy do Σ2 q0 - stan początkowy należący do Q F - zbiór stanów końcowych zawarty w Q

62 Przykład: Sheeptalk - CowtalkLwe(T) = { baa!, baaa!, baaaa!, baaaaa!, baaaaaa!, … } Lwy(T) = { muu!, muuu!, muuuu!, muuuuu!, muuuuuuu!, … } T(baaaa!) = muuuu! a:u b:m a:u a:u ! q0 q1 q2 q3 q4 Start δ a b ! q0 - q1 q2 q3 q4 q4: σ a b ! q0 - m q1 u q2 q3 q4: M = ( Q, Σ, δ, q0, F ) Σ1 = { a, b, ! } Σ2 = { m, u, ! } Q = { q0, q1, q2, q3, q4 } F = { q4 }

63 Przykład: Sheeptalk - Cowtalka:u b:m a:u a:u ! q0 q1 q2 q3 q4 Start q0 Taśma wejściowa b a a a a ! Taśma wyjściowa

64 Przykład: Sheeptalk - Cowtalka:u b:m a:u a:u ! q0 q1 q2 q3 q4 Start q1 Taśma wejściowa b a a a a ! Taśma wyjściowa m

65 Przykład: Sheeptalk - Cowtalka:u b:m a:u a:u ! q0 q1 q2 q3 q4 Start q2 Taśma wejściowa b a a a a ! Taśma wyjściowa m u

66 Przykład: Sheeptalk - Cowtalka:u b:m a:u a:u ! q0 q1 q2 q3 q4 Start q3 Taśma wejściowa b a a a a ! Taśma wyjściowa m u u

67 Przykład: Sheeptalk - Cowtalka:u b:m a:u a:u ! q0 q1 q2 q3 q4 Start q3 Taśma wejściowa b a a a a ! Taśma wyjściowa m u u u

68 Przykład: Sheeptalk - Cowtalka:u b:m a:u a:u ! q0 q1 q2 q3 q4 Start q3 Taśma wejściowa b a a a a ! Taśma wyjściowa m u u u u

69 Przykład: Sheeptalk - Cowtalka:u b:m a:u a:u ! q0 q1 q2 q3 q4 Start q4 Taśma wejściowa b a a a a ! Taśma wyjściowa m u u u u !

70 Przykłady z Lingwistyki komputerowejUproszczona fleksja niektórych niemieckich czasowników (Automat) q0 Start q1 q2 wat q3 bet hast et ε en e est

71 Przykłady z Lingwistyki komputerowejUproszczona fleksja niektórych niemieckich czasowników (Transduktor) q0 Start q1 q2 wat:V q3 bet:V hast:V et:impf et:2pl en:1pl,3pl e:1sg,3sg est:2sg et:3sg,2pl e:1sg T(betest) = V 2sg T(hastet) = V 3sg, V 2pl T(wateten) = V impf 1pl, V impf 3pl

72 Transduktor jako słownik ( Transduktor subsekwencyjny )L = { agencja:N+fem, agent:N+mas, agentka:N+fem, bank:N+mas, bat:N+mas } N+fem 1 a 2 g 3 e 4 n 5 c 6 j 7 8 t 9 k 10 11 b 12 13 14 15 N+mas N+fem N+mas N+mas

73 Transduktor jako słownik ( Transduktor subsekwencyjny )L = { agencja:N+fem, agent:N+mas, agentka:N+fem, bank:N+mas, bat:N+mas } N+fem a g e n c j a 1 2 3 4 5 6 7 t b 11 12 13 14 8 9 10 a n k k a t 15 N+mas N+fem N+mas N+mas

74 Transduktor jako słownik ( Transduktor subsekwencyjny )L = { agencja:N+fem, agent:N+mas, agentka:N+fem, bank:N+mas, bat:N+mas } N+fem a g e n c j a 1 2 3 4 5 6 7 t b 11 12 13 14 8 k a n k t N+mas N+mas

75 Własności zamkniętości TransduktorówTransduktory są: Zamknięte pod względem sumy Zamknięte pod względem konkatenacji Zamknięte pod względem domknięcia Kleene’ego Zamknięte pod względem odwracania Zamknięte pod względem złożenia Nie są zamknięte pod względem intersekcji (ale Transduktory bez przejść ε są)

76 Złożenie FST - Kaskady |T1|(wejście) = wynik1 |T2|(wynik1) = wynik2wyjście |T1|(wejście) = wynik1 |T2|(wynik1) = wynik2 |T3|(wynik2) = wyjście

77 |T|(wejście) = |T3○T2○T1|(wejście) = wyjścieZłożenie FST - Kaskady FST T FST T1 FST T2 FST T3 wejście wynik1 wynik2 wyjście ○ ○ |T|(wejście) = |T3○T2○T1|(wejście) = wyjście

78 |T|(wejście) = wyjścieZłożenie FST - Kaskady FST T wejście wyjście |T|(wejście) = wyjście

79 Intersekcja FST – Reguły równoległeFST T1 FST T2 wejście wyjście FST T3 FST T4

80 Intersekcja FST – Reguły równoległeFST T1 FST T2 wejście wyjście FST T3 FST T4

81 Kilka słów o fonologii Słowo ARPAbet ambrosia lily sunflower[ae m b r ow zh ax] [l ih l iy] [s ah n f l aw axr]

82 Złożenie i przecięcie Transduktorówx +PL f aa s k Poziom leksykalny FST-Słownikowy o ^ x s f aa k z Poziom pośredni FST1 FSTn ortograficzne i fonetyczne reguły o e x s f aa k ix z Poziom wynikowy

83 Przykład na przecięcie Transduktorówx +PL f Poziom leksykalny aa s k +N +PL f FST-Słownikowy o ^ x s f Poziom pośredni aa s k ^ z f FST – Przecięcie reguł o e x s f Poziom wynikowy aa s k ix z f

84 Przykład na przecięcie Transduktorówx +PL f Poziom leksykalny aa s k +N +PL f FST Złożenie słownika z regułami o e x s f Poziom wynikowy aa s k ix z f

85 Inne koncepcje i zastosowania: Automaty i transduktory ważoneWprowadzenie metod statystycznych w symboliczne przetwarzanie mowy. Każde przejście jest dodatkowo oznaczone prawdopodobieństwem wykorzystania tego przejścia. Suma prawdopodobieństw wszystkich przejść wychodzących z jednego stanu jest równa 1.

86 Przykład prostego automatu ważonegoow m aa ey 0.95 0.05

87 Przetwarzanie języka u człowieka a modele skończenie stanowyHipoteza minimalnej redundancji (ang. Minimum redundancy) w morfologii Problemy człowieka ze zrozumieniem zdań wielokrotnie złożonych wskazuje na skończoną pamięć. Gramatyki bezkonstekstowe ze skończonym stosem można opisać za pomocą modeli skończonych (Yngwe 1960) Rozumienie wypowiedzi językowych odbywa się u człowieka w sposób liniowy (deterministyczny), co wskazuje na pewną bliskość do modeli skończonych

88 Dziękuję bardzo za uwagęWreszcie koniec! Dziękuję bardzo za uwagę