Jak komputer czyta tekst?

Komputer dzieli tekst

Jak nauczyć komputer czytania tekstu? Czy podobnie jak człowieka, czy jednak w jakiś inny sposób? O tym właśnie będzie mowa w niniejszym wpisie.

Dzielenie tekstu, w którym występują separatory

Załóżmy, że nasz “cyfrowy podopieczny” posiadł już znajomość alfabetu pewnego języka. Jak wyrobić w nim umiejętność identyfikowania słów? Na pozór wydaje się to zadaniem łatwym – wystarczy przecież połączyć ze sobą litery położone obok siebie pomiędzy spacjami! Ten prosty przepis, jak poniżej zobaczymy, nie zawsze jednak działa.

Kłopoty ze spacją

Przyjrzyjmy się następującemu tekstowi:

Wydałem w Las Vegas na pewno ponad 10 000$.

Logiczny podział powyższego zdania na jednostki powinien być następujący:

Wydałem | w | Las Vegas | na pewno | ponad | 10 000 | $ | .

Uzasadnienie dla takiego podziału jest następujące: jednostki: “Las Vegas, “na pewno” i “10 000”, choć rozdzielone spacją, stanowią nierozerwalną całość znaczeniową.

Natomiast podział według schematu od spacji do spacji jest zgoła odmienny:

Wydałem | w | Las | Vegas | na | pewno | ponad | 10 | 000$.

Zaproponowany powyżej logiczny podział tekstu na jednostki nie do końca odpowiada klasycznemu podziałowi na słowa. W przetwarzaniu komputerowym stosuje się bowiem pojęcie tokenu, który oznacza ciąg następujących po sobie znaków, i to niekoniecznie alfabetycznych. W szczególności tokenem może być słowo, liczba, data, numer telefonu czy adres internetowy.

Ludzkiemu dzieleniu tekstu na wyrazy odpowiada zaś komputerowy termin tokenizacja, oznaczający dzielenie tekstu na tokeny.

Kłopoty z kropką

Spory kłopot w dzieleniu tekstu na tokeny sprawiają kropki. Weźmy pod uwagę następujące zdanie:

Adres mailowy prof. Kowalskiego to kowalski@poleng.pl.

Pożądany podział takiego tekstu na tokeny wygląda następująco:

Adres | mailowy | prof. | Kowalskiego | to | kowalski@poleng.pl | .

Aby tak “stokenizować” powyższe zdanie, program komputerowy musi jednak umieć odróżniać kropki będące częścią skrótu czy adresu mailowego od tych kończących zdanie. Podobnego typu kłopoty sprawiają także między innymi znaki: łącznika, myślnika czy apostrofu oraz emotikony.

Jak komputery radzą sobie z dzieleniem tekstu?

Istnieją dwa podstawowe podejścia do zadania tokenizacji. W metodach opartych na słownikach i regułach przygotowywane są leksykony wyrazów specyficznych, np. skrótów zakończonych kropką. Ponadto opracowywane są wzorce wybranych tokenów (takich jak daty, adresy internetowe itp.) – najczęściej w postaci wyrażeń regularnych, które pozwalają na wyodrębnienie tego typu fragmentów z tekstu.

W metodach stosujących uczenie maszynowe opracowuje się z kolei dane uczące, w skład których wchodzą przykłady poprawnie podzielonych tekstów. Oczekuje się, że system nauczy się dzielenia tekstu wyłącznie na podstawie tychże danych.

Dzielenie tekstu, w którym nie występują separatory

Istnieją też jednak języki, które nie stosują separatorów międzywyrazowych. Jednym z nich jest urzędowy język Chińskiej Republiki Ludowej – mandaryński.

Aby dokonać podziału na tokeny tekstu w tym języku zastosować można tzw. algorytm MaxMatch.

Algorytm MaxMatch

Algorytm MaxMatch zakłada istnienie leksykonu, w którym zawarte są wszystkie słowa danego języka. Rozpoczynając od pierwszego znaku interesującego nas tekstu, identyfikujemy najdłuższy ciągu znaków, który występuje we wspomnianym leksykonie, po czym odcinamy go od reszty tekstu (jeśli nie zidentyfikowano ani jednego słowa z leksykonu, odcinamy od reszty tekstu jeden znak). Powyższą procedurę powtarzamy dla pozostałej części tekstu.

Prześledźmy, jak algorytm ten zadziałałby dla przykładowego zdania polskiego, gdyby w naszym języku nie występowały między wyrazami spacje. Niech zdaniem tym będzie:

Barankawałopowiadałani.

Chcielibyśmy uzyskać podział:

Baran | kawał | opowiada | łani |.

względnie:

Baran | kawał | opowiadał | ani |.

Niestety nic z tego! Algorytm MaxMatch zwróci bowiem następujący podział:

Baranka | wał | opowiadała | ni | .

Wniosek z tego taki, że spacje międzywyrazowe w naszym języku to jednak prawdziwe dobrodziejstwo!

Komputer dzieli tekst na zdania

Wydaje się, że zdanie jest podstawowym fragmentem tekstu, posiadającym spójną interpretację. Czytamy tekst “zdanie po zdaniu”. Przemawiamy “zdanie po zdaniu”. Tłumaczymy tekst “zdanie po zdaniu”. Komputer stara się nas w tym względzie naśladować, starając się dzielić tekst na zdania. Najprostsza z pozoru reguła: “Dziel po kropce, przed spacją i dużą literą” może jednak czasem zawieść:

Tekst przed podziałem:

W 2019 r. Kowalski zwiedził wiele krajów, m.in. Niemcy, Francję i Kanadę. On wprost uwielbia podróżować!

Tekst po podziale:

W 2019 r. | Kowalski zwiedził wiele krajów, m.in. | Niemcy, Francję i Kanadę. | On wprost uwielbia podróżować!

Trochę tu zbyt wiele znaków podziału zdaniowego, nieprawdaż?

Metody podziału tekstu na zdania

Podobnie jak w przypadku podziału zdania na tokeny również w przypadku podziału tekstu na zdania dostępne są dwa podejścia:

• regułowe: określone zostają zasady mówiące o tym, w jakich miejscach tekst powinien być dzielony na zdania;
• uczenie maszynowe: system uczy się dzielić tekst na zdania na podstawie przygotowanych wcześniej danych treningowych.

Komputer dzieli tekst po swojemu

Kiedy w zadaniach związanych z przetwarzaniem języka naturalnego poważną rolę odgrywać zaczęły sztuczne sieci neuronowe (w tłumaczeniu automatycznym “neuronowy przełom” nastąpił w roku 2014), okazało się, że tradycyjny podział tekstu na tokeny nie sprawdza się. Warstwę wejściową do sieci neuronowych stanowić musi bowiem wektor o rozmiarze równym liczbie wszystkich wyrazów stosowanych w przetwarzanym dokumencie, a w skrajnym przypadku mogą to być wartości rzędu milionów. Obliczenia w tak olbrzymich sieciach pozostają niestety nadal poza zasięgiem konstruowanych współcześnie maszyn.

Algorytm BPE

Należało więc znaleźć sposób na skompresowanie słownika, czyli zmniejszenie jego objętości liczonej w słowach. Jednym z takich sposobów jest algorytm BPE. Dane wejściowe powyższego algorytmu stanowią: tekst (lub zbiór tekstów), który ma zostać przetworzony, oraz pożądana objętość słownika, która w przypadku praktycznych zastosowań zamknąć powinna się liczbą w okolicach 50 000. Elementy takiego słownika określane są mianem podwyrazów (ang. subwords).

Algorytm BPE opiera się w swym działaniu na łączeniu ze sobą najczęstszych bigramów, przy czym bigramem nazywamy parę sąsiednich fragmentów tekstu.

Przeanalizujmy działanie algorytmu BPE dla zadanej objętości słownika równej 10 oraz następującego tekstu:

Pospiesz się, pieszy, pospiesz się!

W pierwszym kroku usunięte zostają z powyższego tekstu znaki interpunkcyjne, a tekst podzielony zostaje na pojedyncze litery. Granica pomiędzy wyrazami (oznaczona tutaj jako <w>) traktowana jest na równi z literą:

<w> p o s p i e s z <w> s i ę <w> p i e s z y <w> p o s p i e s z <w> s i ę <w>

Słownik składa się z 9 podwyrazów:

{<w> p, o, s, i, e, z, ę, y}

Liczba wystąpień poszczególnych bigramów w powyższym tekście jest następująca:

Scalamy pierwszy bigram o liczbie wystąpień 3: <w> p i dodajemy go do słownika, który zawiera teraz 10 podwyrazów:

{<w> p, o, s, i, e, z, ę, y, <w>p}

Cały dokument ma postać:

<w>p o s p i e s z <w> s i ę <w>p i e s z y <w>p o s p i e s z <w> s i ę <w>

Jedno wystąpienie bigramu p i w ten sposób zniknęło, gdyż w wyrazie pieszy litera p została sklejona z poprzedzającym  znakiem <w>.

Kolejnym bigramem o liczności występowania 3 jest i e. Scalamy go w jedność i dodajemy do słownika, który zawiera teraz 11 podwyrazów:

{<w> p, o, s, i, e, z, ę, y, <w>p, ie}

Cały dokument ma postać:

<w>p o s p ie s z <w> s i ę <w>p ie s z y <w>p o s p ie s z <w> s i ę <w>

Zniknęły nam w ten sposób bigramy postaci e s, jednakże wciąż możemy połączyć s oraz z, uzyskująć słownik z 12 podwyrazami:

{<w> p, o, s, i, e, z, ę, y, <w>p, ie, sz}

Cały dokument ma postać:

<w>p o s p ie sz <w> s i ę <w>p ie sz y <w>p o s p ie sz <w> s i ę <w>

Przyszła teraz pora na bigramy o liczności 2. Pierwszym z nich w kolejności występowania jest <w>p o. Łączymy bigramy, zwiększając o 1 wielkość słownika:

{<w> p, o, s, i, e, z, ę, y, <w>p, ie, sz, <w>o}

<w>po s p ie sz <w> s i ę <w>p ie sz y <w>po s p ie sz <w> s i ę <w>

Następnie scalamy kolejne bigramy o liczności występowania 2:

<w>po sp ie sz <w> s i ę <w>p ie sz y <w>po sp ie sz <w> s i ę <w>

<w>po sp ie sz <w>s i ę <w>p ie sz y <w>po sp ie sz <w>s i ę <w>

<w>po sp ie sz <w>s ię <w>p ie sz y <w>po sp ie sz <w>s ię <w>

W ostatniej z powyższych reprezentacji słownik składa się już z 16 podwyrazów:

{<w>, p, o, s, i, e, z, ę, y, <w>p, ie, sz, <w>po,  sp, <w>s , ię}

Pora zatem kończyć… zarówno działanie opisywanego algorytmu, jak i niniejszy wpis na blogu.

Podsumowanie

Człowiek chciałby, aby sztuczna inteligencja przetwarzała język naturalny w sposób jemu podobny. Pierwsze systemy analizy języka naturalnego oparte były więc na regułach budowy zdań podobnych do tych, które znane są nam z lekcji gramatyki. Systemy tłumaczenia automatycznego stosowały zaś zasady tłumaczenia zaczerpnięte żywcem z podręczników do nauki języka obcego.

Okazało się jednak, że faktyczny przełom w komputerowym przetwarzaniu języka naturalnego nastąpił dopiero wtedy, gdy pozwoliliśmy maszynom “wykazać się”, tj. uczyć się samodzielnie na podstawie dostarczonych przez nas danych. Jeszcze do niedawna wydawało się, że podział tekstu na wyrazy, zdania i akapity pozostanie domeną systemów regułowych – działających na zasadzie analogii do czynności podejmowanych przez człowieka. Dziś wydaje się, że i w tym zadaniu maszyny podążą swoją własną drogą.