# Przetwarzanie języka naturalnego - ćwiczenia 1

# Zaczynamy 14:15!

## Zadanie 1


Wydaje mi się, że problem jest tutaj z popularniejszymi dłuższymi zbitkami liter. Dla przykładu załóżmy, że sufiks `-kała` (`szukała`, `płakała`) jest bardzo częsty. Wtedy algorytm musi wykonać aż cztery iteracje, żeby w końcu zastąpić cząstkę `kała` jednym znakiem (`kała -> kaþ -> əþ -> ð`).

Aby zaoszczędzić wielokrotnego przeglądania całego korpusu, można by zbierać informacje także o połączeniach liter dłuższych niż 2 (np. do 5 liter). Ponadto jeżeli najpopularniejsze zbitki liter, które nie posiadają wspólnych liter, mogą być zastępowane nowym znakiem w jednej iteracji.

## Zadanie 2 Michał Zobniów

Uruchamiamy algorytm BPE na słowniku $S1$ i otrzymujemy niby-alfabet $A1$. Załóżmy, że z $A1$ wiemy tylko o niby-literze $Z = ba$. Weźmy słowo spoza słownika `aacbaacb`. Używając wiedzy z $A1$ otrzymujemy:

aacZacb

Nie da się go bardziej oprościć, bo nie mamy żadnej wiedzy o parze, która może to zrobić. Optymalnym rozwiązaniem, jeżeli zaczęlibyśmy naukę tylko na słowie `aacbaacb`:

aacbaacb - aa->X
XcbXcb - Xc->Y
YbYb - Yb->Z
ZZ
Q

Często więc zastosowanie wiedzy z $S1$ jest nieoptymalne, bo dla słów spoza słownika uproszczenie może być nieznaczne przez występowanie nowych par liter, które nie zostały poznane.

**Uwaga**
Gdyby słowo `aacbaacb` znajdowało się w większym słowniku to oczywiscie nie mamy gwarancji że zostanie rozłożone optymalnie.
## ZADANIE 3 Krzysztof Jadłowski
Metoda naturalna będzie w takich zadaniach strasznie nieoptymalna, ponieważ możemy dostać bardzo dużo różnych tekstów, a niewiele z nich spełnia podany warunek. W poniższych algorytmach będziemy się starać zmniejszyć zbiory z których dokonujemy losowań nie zmniejszając zbytnio(najlepiej w ogóle) liczby poprawnych tekstów, co pozwoli nam częściej uzyskiwać poprawny tekst. W dalszej części zadania następnikiem słowa będę nazywał N-gram który rozpoczyna się w danym słowie, a poprzednikiem N-gram kończący się w danym słowie. Jeśli będę mówił o następniku N-gramu mam na myśli N-gram który zaczyna się w wyrazie w którym kończy się tamten N-gram, analogicznie z poprzednikiem.

* a)
dla naszego słowa na miejscu k, Za pomocą N-gramów ustalamy możliwe następniki i poprzedniki losujemy dowolny następnik i poprzednik. Następnie aż dojdziemy do miejsc 1 i M, losujemy poprzedniki poprzedników i następniki następników. Oczywiście przy napotkaniu słowa bez poprzednika lub następnika powtarzamy losowanie od początku
* b)
Dla 2-gramów, dla każdego indeksu wybieramy tylko takie 2-gramy że odpowiedni parzysty wyraz występuje na odpowiednim miejscu(np dla parzystego indeksu k wybieramy 2-gramy takie że 1 słowo jest naszym wymaganym na k-tym miejscu, dla k nieparzystego takie 2-gramy że drugim słowem jest wymagane k+1 słowo) Sposród tak wybranego zbioru dokonujemy losowania dopóki możemy, jeśli nie znajdziemy odpowiedniego następnika, losujemy od początku
Dla 3-gramów, postępujemy podobnie jednakże dla każdego indeksu musimy wyznaczyć zbiór takich 3-gramów że odpowiednie wyrazy parzyste są na odpowiednich miejscach w tych 3-gramach.
* c)
Dla pierwszego słowa losujemy następniki i dla ostatniego słowa poprzedniki dopóki nie znajdziemy tekstu dla którego któryś kolejny następnik pierwszego słowa ma swój następnik będący którymś z poprzedników. Jeśli już dojdziemy do za długich tesktów, powtarzamy losowanie od początku
* d)
Wybieramy tylko takie N-gramy że spełniają jakiś ciąg sufiksów długości N, następnie losujemy kolejne N-gramy z takiego zbioru, jeśli tekst nie spełnia warunków lub doszliśmy do słowa bez następnika losujemy od początku.

## Zadanie 4
* a) Podejście rekurencyjne

W celu przeprowadzenia pełnego rozbioru zdań przy podejściu rekurencyjnym potrzebne jest przygotowanie **zbioru hierarchicznych reguł definiujących możliwe przypadki rozbioru**. Każda z reguł określa jeden z węzłów drzewa rozbioru. W danym węźle może oczywiście być wiele reguł określających różne warianty drzewa rozbioru. Reguły mają następującą postać BNF (Backus-Naur Form):


Przetwarzanie odbywa się w konwencji zstępującej. Jako element główny występuje element *ZdanieZlozone*, które dzieli się na grupy, grupy dzielą się na grupy, itd. Rozbiór zdania oznacza więc budowanie drzewa na podstawie wielu jego wariantów dopuszczanych przez reguły. Reguła może się składać z 1...n produktów–podelementów reguły. Produkt może zawierać element terminalny lub odniesienie do innej reguły. Dodatkowo w regułach definiowane są **związki zgodności**, np. zgodność liczby i rodzaju przydawki z podmiotem. W regułach ważna jest kolejność produktów, muszą one występować w podanej w regule kolejności, żeby ją spełniać.

* b) Podejście statystyczno-adaptacyjne

Przyjęto tutaj kilka założeń upraszczających:
• Płaska struktura analizy – tokenom przyporządkowywana jest ich rola w zdaniu, np. podmiot, jednak bez pełnej analizy zależności pomiędzy tokenami. W szczególności nie jest budowana hierarchiczna struktura drzewiasta.
• Lokalność analizy – analiza obejmuje wyłącznie pewne sąsiedztwo tokenu. Proces rozpoznawania części zdania sprowadzonodo zadania klasyfikacji na podstawie atrybutów analizowanego tokenu i jego sąsiadów.

W związku z wykorzystywaniem klasyfikacji konieczne jest przeprowadzenie etapu uczenia klasyfikatora. Ogólnie uczenie oparte jest na budowaniu wzorców na podstawie wartości atrybutów tokenu, który służy jako przykład oraz na podstawie wartości atrybutów jego sąsiadów. Rozmiar sąsiedztwa może być ustalany oraz mogą być wybrane atrybuty, które będą klasyfikowane. Podczas klasyfikacji, dla danego tokena przeglądana jest cała **lista reguł** i wybierane są te, które są najlepiej dopasowane do tokena.

* c) Podejście relacyjne

Jest pewnym kompromisem pomiędzy złożonością i precyzją w stosunku do rozbioru rekurencyjnego. Podejście to jest w pewnym stopniu podobne do podejścia statystycznego, jednak zamiast klasyfikatora nauczonego na przykładach stosowany jest **zbiór reguł relacyjnych, które określają relacje między częściami zdania**. Przy czym aplikowane w określonym porządku reguły odnoszą się kolejno do różnych części zdania. Taka metodologia przypomina sposób działania człowieka, który działając w obrębie zdania jest w stanie najpierw zaznaczyć orzeczenie, następnie podmiot, określające go przydawki itd.
Reguły relacyjne, wspierając się występowaniem znaków przystankowych, są w stanie również rozpoznać i oddzielić zdania złożone, w tym także zdania wtrącone. Reguły te pozwalają również na znalezienie pewnych zależności pomiędzy wyrazami (tokenami). Nie jest tutaj budowana pełna hierarchia drzewiasta, jak w przypadku analizy rekurencyjnej. Jednak w praktycznych zastosowaniach nie wszystkie zależności są potrzebne.
Wadą takiego rozwiązania jest duży poziom skomplikowania reguł i trudność ich syntetycznego zapisu o mniejszej sile wyrazu niż występującej we współczesnych językach programowania. Utrudnia to tworzenie i modyfikację takich reguł.

Źródło: P. Sołdacki, “Zastosowanie metod płytkiej analizy tekstu do przetwarzania dokumentów w języku polskim”

## Zadanie 5 (Paweł Grabiński)

Przypomnij, dlaczego do wyznaczania masy prawdopodobieństwa przypisanej słowom niewystępującym w korpusie ($P(UNK)$) , przydatny jest podział korpusu na dwie części ($K_1$ i $K_2$). Załóżmy, że nasz korpus ma pewną strukturę: cały korpus składa się z dokumentów, te z kolei z akapitów, które dzielą się na zdania. Jeżeli chcemy podzielić korpus na dwie części, to możemy przeglądać go porcja po porcji (porcjami mogą być dokumenty, akapity, zdania, albo pojedyncze wyrazy) i z prawdopodobieństwem $p$ przypisywać porcję do korpusu $K_1$, a z prawdopodobieństwem $1 − p$ do korpusu $K_2$.
\begin{align}
P(UNK)=\frac{\text{liczba słów w $K_2$ niewystępujących w $K_1$}}{|K_2|}
\end{align}

### a) Jak wybór $p$ wpływa na $P(UNK)$?
Zauważmy, że dla $p=1$ mamy $P(UNK)=0$, bo w $K_2$ nie ma słów, więc nie ma też takich, które by nie występowały w $K_1$.
Zauważmy, że dla $p=0$ mamy $P(UNK)=1$, bo w $K_2$ są wszystkie słowa, więc liczba takich, których nie ma w $K_1$ wynosi $|K_2|$.
#### Co dzieje się dla $p\in(0,1)$?

Zauważmy, że jeśli korpus $K_1$ jest arbitralnie duży - zawiera wszelkie możliwe tokeny wielokrotnie, to próbkowanie poszczególnych fragmentów z niego nie znajdzie niepowtarzalnych elementów. Jednak po to korzystamy z tej metody szacowania $P(UNK)$, żeby móc zajmować się skończonymi korpusami. Jednak wciąż powinniśmy zachować tę prawidłowość, że popularne tokeny/n-gramy/fragmenty będą rozdzielone do obu korpusów. Jedynie bardzo rzadkie elementy będą trafiać wyłącznie do jednego z korpusów. Oszacowanie tego dokładnie z jakim prawdopodobieństwem powinniśmy próbkować z pierwotnego korpusu. By zachować wspomnianą prawidłowość możemy heursytycznie podzielić pierwotny korpus tak, by:
1. Korpus $K_1$ był (znacznie) większy od $K_2$, by były tam wszyskie popularne fragmenty języka,
2. Korpus $K_2$ był reprezentatywny, czyli zawierał odpowniednio dużo elementów, co sprawi, że nie tylko liczba słów w $K_2$ niewystępujących w $K_1$ będzie niezerowa, ale także czynnik normalizujący $|K_2|$ będzie odpowiednio duży tak, by $P(UNK)$ było mniejsze od prawdopodobieństwa większości popularnych elementów,
3. Można przyjąć na przykład $|K_2|=0.1|K_1|$.

Jeśli popatrzymy na proces losowania słowa $w$, które występuje w korpusie pierwotnym $n_w$ razy, to możemy uznać to za próbkowanie z rozkładu dwumianowego, więc wartość oczekiwana dla korpusu $K_1$ będzie $n_w p$, a dla $K_2$ będzie to $(1-p)n_w$. Jeśli ustalimy "odpowiednio duże n" dla popularnych fragmentów, to możemy oczekiwać, żeby wartość oczekiwana takich elementów w $K_2$ będzie wynosiła $k$, więc dostaniemy $p=1-\frac{k}{n}$, np. dla $n=5$ i $k=1$, $p=0.8$.

### b) Jak wybór tego, czym jest porcja, wpływa na $P(UNK)$?

Problem pojawiający się z przy wyborze rozmiaru porcji korpusu przy podziale jest podobny do problemu niezbalansowania klas występującego w metodzie $k-fold$, gdzie dzielimy zbiór danych na $k$ części i jedną z nich traktujemy jako zbiór testowy (ewaluacyjny) analogicznie do naszego korpusu $K_2$. Problem ten polega na tym, że jeśli zbiór danych ma pewną wewnętrzną strukturę, np. jest posortowany ze względu na jedną z cech, to wybieramy w ten sposób bardzo szczególny fragment tego zbioru. Przykładem tego dla problemów językowych może być wyciągnięcie zbioru aktów prawnych lub publikacji naukowych, które zawierają żargon danej dziedziny, czyli bardzo rzadkie elementy język z punktu widzenia jego całości. Więc jeśli będziemy rozdzielać korpus całymi rozdziałami, to może się zdażyć, że do $K_2$ trafi cała objętość tekstów prawnych lub naukowych z korpusu i nawet *średnio* popularne elementy (np. rozprawa lub algorytm) mogą nie wystąpić w $K_1$, a przez to zawyżyć $P(UNK)$. Idealnie byłoby próbkować poszczególne słowa, co oczywiście wiąże się z koniecznością częstszego generowania liczb losowych, więc dłuższymi obliczeniami.

## Zadanie 6 Szymon Kozicki

Jeżeli rozwiązywałeś Zadanie 4 z pracowni, to pewnie miałeś problemy z porównywaniem naturalności permutacji. Zastanów się, dla którego ze zdań te problemy były silniejsze i dlaczego. Pewne konstrukcje języka polskiego nie są „permutowalne” to znaczy wymagają określonej kolejności wyrazów, bo inaczej będą niepoprawne. Przedstaw co najmniej 3 takie konstrukcje i zilustruj to przykładami zdań lub fraz (najlepiej również pięciowyrazowych, ale dopuszczalne są też nieco dłuższe), dla których bardzo wiele permutacji jest kompletnie niepoprawnych i/lub niezrozumiałych.

Zdania z Zadania 4 z pracowni

Judyta dała wczoraj Stefanowi czekoladki.
Babuleńka miała dwa rogate koziołki.
Wczoraj wieczorem spotkałem pewną piękną kobietę.

Problemy były silniejsze dla ostatniego zdania, a to z tego powodu, że zdanie jest najdłuższe. Wynikiem większości permutacji jest zdanie, którego sens co prawda po pewnej chwili konsternacji zrozumiemy, ale w trakcie połamiemy sobie język. Przy krótszych zdaniach, częściej jesteśmy skłonni powiedzieć, że permutacje brzmią naturalnie.

Niepermutowalne konstrukcje
1. Nazwy wieloczłonowe własne, miast, geograficzne, imiona i nazwiska
- W Ameryce Północnej leży San Francisco.
2. Zdania w których występuje szeregowanie zadań, czas ma wpływ na stan rzeczywistości.
- Nalałem szklankę wody i ją wypiłem.
- Dwa plus dwa to cztery.
3. Wyliczenie
- Ja mam brata, on ma siostre.
- On jest lekarzem, ona pielęgniarką.
4. Przymiotniki
5. Liczebniki

## Zadanie 7 Jacek Kowalski

Końcówek w języku polskim jest o wiele mniej od słów, dlatego jest o wiele większa szansa na to, że w naszym korpusie natrafimy na frazę o takiej samej konstrukcji gramatycznej niż na frazę korzystającą z tych samych słów. Z tego powodu w modelu sufiksowym możemy korzystać z dłuższych ngramów niż w modelu tradycyjnym, gdyż możemy wziąść większe fragmenty korpusów zanim luki w danych zaczną nam przeszkadzać.

Standardowy Deleted Interpolation:
$$P^*(w_n|w_1w_2...w_{n-1}) = \lambda_1P(w_n) + \lambda_2P(w_n|w_{n-1}) + \ldots + \lambda_nP(w_n|w_1w_2...w_n)$$
gdzie $\sum_i^n \lambda_i = 1$, a parametry $\lambda$ są wyznaczane za pomocą korpusów $K1$ i $K2$
Połączyć model tradycyjny z modelem sufiksowym możemy w następujący sposób:
\begin{align}
P^*(w_m|w_1w_2...w_{m-1}) = &\lambda_1P(w_m) + \lambda_2P(w_m|w_{m-1}) + \ldots + \lambda_{m-n}P(w_m|w_{n+1}w_{n+2}...w_m) +\\
&\lambda_{m-n+1}P(s_m|s_n...s_{m-1}) + \ldots + \lambda_mP(s_m|s_1...s_{m-1})
\end{align}
Gdzie $\sum_i^m\lambda_i = 1$, a $s_i$ oznacza sufiks $i$-tego słowa długości $k$, wszystkie parametry $\lambda$ są wyznaczane analogicznie jak w Deleted Interpolation.

## Zadanie 8
**a)**
Dla każdego $T_i$ -- zbioru słów o tagu $t_i$ -- obliczamy, w ilu słowach z $T_i$ występuje dany sufiks $s_j$ (poprzez przejrzenie wszystkich słów z $T_i$). Po przejrzeniu wszystkich słów ze zbioru $T$ otrzymujemy pary $(s_{j, T_i}, n_{s_j, T_i})$, gdzie
* $s_{j, T_i}$ -- dany sufiks $s_j$ występujący w pewnym słowie o tagu $t_i$ oraz
* $n_{s_j, T_i}$ -- łączna liczba sufiksów $s_j$ występujących w słowach z $T_i$.

Usuwamy wszystkie $n = 1$.
Usuwamy powtórzenia $s_j$.

Sortujemy wszystkie pary $(s, n)$ po długości $s$.
Do momentu kiedy nie oznaczymy wszystkich słów w $T$ lub zabraknie par $(s, n)$:
* bierzemy parę o najdłuższym $s_{j, T_i}$ (takie że istnieje jeszcze w zbiorze $T$ słowo o sufiksie $s_j$ i tagu $t_i$)
* otrzymujemy mapowanie $s_j \rightarrow t_i$
* $s_j$ dodajemy do $S$
* usuwamy z $T$ słowa o sufiksie $s_j$ (należące do podzbioru $T_i$, bo wyrzuciliśmy sufiksy powtarzające się między otagowanymi grupami)

Jeśli w $T$ pozostały jakieś słowa, to tworzymy mapowania wykorzystujące te słowa jako sufiksy, zatem te słowa dodajemy do $S$.

Otrzymujemy zbiór sufiksów $S$, który jednoznacznie wyznacza tag słowa.

**b)**
* łatwo znaleźć tag dla nowego słowa
* zbiór $S$ jest dużo mniejszy niż cały słownik

**c)**
Moglibyśmy na początku nie usuwać powtórzeń $s_j$, a w mapowaniu sufiksu słowa na tag zapisać prawdopodobieństwo, że dany sufiks wyznacza oznacza dany tag (np. $s_j \rightarrow (0.6, t_{i1}; 0.4, t_{i2})$)

## Zadanie 9 Piotr Słowik

Rozbiór logiczny zdania polega na wyznaczeniu części składowych zdania (podmiot, orzeczenie, okolicznik, dopełnienie, przydawka).
Drzewem rozbioru nazwiemy wynik rozbioru logicznego zdania.

### Stefan widział latarnię w Ustce.

1. Stefan był w Ustce i widział latarnię.
2. Stefał widział latarnię znajdującą się w Ustce.

### Stefan widział latarnię w Ustce jedynie na zdjęciach Beaty.


1. Stefan widział latarnię w Ustce tylko dlatego że Beata mu ją pokazała na zdjęciu.
2. Stefan był w Ustce i Beata pokazała mu jakąś latarnię na zdjęciu.

### Mam radę: nie mam mamy obietnicami bez pokrycia.

### Wyjazd pociągiem do Krakowa zastąpił bogaty program artystyczny.

1. Program artystyczny zastąpił wyjazd pociągiem.
2. Wyjazd pociągiem zastąpił program artystyczny.

### Wiktor podarował Beacie kwiaty, a Ewie czekoladki.

## zadanie 10 Mikołaj Korobczak
### Visiting aunts can be a nuisance.

digraph {
    "can be" -> visiting[label="what?"];
    visiting -> aunts[label="who?"];
    "can be" -> "a niusance"[label="what?"];
    {rank = same "can be"; visiting};
}

Znaczenia:
1. Odwiedzenie cioć może być uciążliwe dla mnie.
2. Odwiedzenie cioć może być naprzykrzaniem się.

Dodanie słów do tego zdania:
1. I’ve decided to help them, though visiting aunts can be a nuisance.
2. I’ve decided to suprise them, though visting aunts can be a nuisance.