Usługi tłumaczeniowe i lokalizacyjne certyfikowane normami ISO 17100:2015, ISO 27001:2017 oraz ISO 18587
Menu
LoginSzybka wycena
Menu

Na czym polega automatyczna klasyfikacja tekstów?

Automatyczna klasyfikacja tekstów polega na przydzielaniu ich do określonych kategorii przez system komputerowy. W przypadku niektórych zastosowań system sam decyduje, w jaki sposób określić kategorie (czy inaczej: klasy) tekstów. Jeśli na przykład człowiek chce pogrupować najnowsze newsy, a nie jest pewien, jakich tematów będą one dotyczyć, może zlecić systemowi sztucznej inteligencji ich podział na określoną liczbę (np. 10) klas. System grupuje wtedy newsy w taki sposób, aby w każdej z kategorii znalazły się te z nich, które posługują się podobnym słownictwem.

Według scenariusza alternatywnego to człowiek podejmuje decyzję, w jaki sposób zdefiniować klasy, w oparciu o które nastąpi grupowanie. Na przykład w przypadku zadania polegającego na klasyfikacji maili (patrz również: /blog/nlp-co-to-jest-i-do-czego-sie-przydaje) zlecamy sztucznej inteligencji, aby dla każdej kolejnej wiadomości mailowej dokonała jej klasyfikacji w oparciu o kryterium przydatności na potrzeby adresata, bądź to przydzielając ją do kategorii SPAM, bądź też przekazując ją do jego skrzynki odbiorczej (klasa NIE-SPAM).

Podobnie też w przypadku analizy wydźwięku (patrz: /blog/nlp-co-to-jest-i-do-czego-sie-przydaje) klasyfikator ma zadecydować, do której z trzech kategorii – określonych z góry według kryterium nastawienia autora tekstu do opisywanej rzeczywistości – a mianowicie: negatywna, pozytywna lub neutralna, kwalifikuje się dana recenzja.

Podstawowym sposobem podziału tekstów na zdefiniowane z góry przez człowieka kategorie jest tzw. metoda Bayesa. To właśnie tę metodę klasyfikacji omówię w niniejszym wpisie na blogu.

Uczenie nadzorowane

Metoda Bayesa należy do metod uczenia nadzorowanego. Określenie to oznacza, że system sztucznej inteligencji uczy się wykonywać pewne zadanie poprzez analizę danych, dla których zadanie to zostało już wcześniej wykonane. W przypadku rozpoznawania spamu system uczy się swojej pracy z wykorzystaniem maili, które zostały już wcześniej odpowiednio zaklasyfikowane przez człowieka.

Jak przygotować dane na potrzeby uczenia nadzorowanego

Przygotowanie danych na potrzeby uczenia maszynowego jest zadaniem dość pracochłonnym, a do tego niezbyt ciekawym intelektualnie. Wymaga wielokrotnego powtarzania bardzo podobnych czynności, których jakość wykonania trudno rzetelnie zweryfikować.

Mechaniczny Turek

Skuteczny sposób na przezwyciężenie tego typu niedogodności wymyślono w firmie Amazon, wprowadzając model pracy zwany Mechanicznym Turkiem (ang. Amazon Mechanical Turk). Stosowany jest on na potrzeby zadań wymagających ludzkiej inteligencji, lecz niekoniecznie specjalizacji w jakiejkolwiek dziedzinie. Zgodnie z nim zadania przekazywane są odpowiednio licznej grupie pracowników (zwanych – zgodnie “z najlepszymi zasadami politycznej poprawności” – Mechanicznymi Turkami) w tak małych porcjach, aby każdy z zatrudnionych mógł zrealizować swoje obowiązki o dowolnej dogodnej dla siebie porze dnia, z zachowaniem możliwości przerwania wykonywanego zadania, ilekroć będzie to konieczne (np. podczas wysiadania z autobusu lub tramwaju). Co więcej, dokładnie te same porcje zadań przydzielane są różnym wykonawcom, niemającym ze sobą kontaktu, co umożliwia weryfikację zgodności uzyskanych rozwiązań i premiowanie tych spośród nich, które pokrywają się wzajemnie u rozmaitych autorów.

Oznaczanie danych tekstowych

W przypadku zadania polegającego na klasyfikacji maili najmniejszą porcją pracy do wykonania przez Mechanicznego Turka będzie przypisanie pojedynczej wiadomości mailowej do jednej z dwóch klas: SPAM lub NIE-SPAM. Zbiorcze efekty pracy licznej grupy Mechanicznych Turków posłużyć mogą jako obszerny korpus uczący na potrzeby przygotowania systemu sztucznej inteligencji – w analizowanym przypadku: odsiewającego niepożądaną korespondencję elektroniczną.

Do czego przydaje się rachunek prawdopodobieństwa?

Kłopot ze sztuczną inteligencją polega jednak na tym, że nigdy nie możemy jej zawierzyć w stu procentach. W przypadku zadania polegającego na klasyfikacji sztuczna inteligencja stwierdza na przykład jedynie, że dany obiekt prawdopodobnie należy do danej kategorii. Jeżeli użytkownik wymaga więc, aby system wskazał konkretnie pojedynczą klasę, do której dany obiekt należy przydzielić (a tak jest w praktyce najczęściej), system wskazuje tę spośród klas, dla której wyliczone przez niego prawdopodobieństwo przynależności jest najwyższe.

Jak działa klasyfikator Bayesa?

Klasyfikator Bayesa wyznacza dla każdego obiektu prawdopodobieństwo, z jakim obiekt ten przynależy do poszczególnych klas, posługując się w tym celu dwoma czynnikami: prawdopodobieństwem przed faktem (ang. prior probability) oraz prawdopodobieństwem po fakcie (ang. posterior probability).

Prawdopodobieństwo przed faktem

Pierwsza z powyższych dwóch wartości wyznaczana jest przed przystąpieniem do analizy danego obiektu. Na przykład prawdopodobieństwo przed faktem tego, że dany mail jest spamem, wyznaczane jest wyłącznie na podstawie danych informujących o tym, jaka część wiadomości mailowych w zbiorze uczącym zakwalifikowana została do kategorii SPAM. Jeśli na przykład w 100-elementowym zbiorze uczącym 30 maili sklasyfikowanych zostało jako SPAM, prawdopodobieństwo przed faktem, że dany mail jest spamem wynosi 30%.

Prawdopodobieństwo po fakcie

Prawdopodobieństwo po fakcie obliczane jest po dokonaniu analizy danego obiektu. Zidentyfikowane zostają jego cechy charakterystyczne, na podstawie których ustalona zostaje klasa, której cechy te najbliżej odpowiadają.

Powyższy zrzut ekranowy zawiera tematy maili sklasyfikowanych jako SPAM. Załóżmy, że stanowią one zbiór uczący, na podstawie którego system ma zakwalifikować nową wiadomość mailową o następującym nagłówku:

Okazja! Abonament 200 zł miesięcznie. Sprawdź!

Cechą charakterystyczną powyższego maila jest zastosowanie w jego treści wykrzykników. Okazuje się, że jest to właściwość typowa dla wiadomości z kategorii SPAM, gdyż w obrębie 10 elementów zbioru uczącego oznaczonych jako SPAM znak ten pojawił się aż pięciokrotnie.

W praktyce klasyfikator Bayesa stosowany jest w taki sposób, że dla każdej z cech charakterystycznych danego obiektu oblicza się, jak bardzo cecha ta typowa jest dla konkretnej klasy. W przypadku klasyfikacji tekstów dla każdego wyrazu lub znaku interpunkcyjnego danego dokumentu ustala się, z jaką częstością pojawia się on w treści wszystkich dokumentów przypisanych do danej kategorii. Wartości uzyskane dla wszystkich takich cech mnoży się następnie przez siebie, otrzymując w wyniku wartość prawdopodobieństwa po fakcie.

System kwalifikuje obiekt do tej spośród klas, dla której iloczyn obu prawdopodobieństw: prawdopodobieństwa przed faktem oraz prawdopodobieństwa po fakcie jest najwyższy.

Podsumowanie

Proste? Na pewno nie jakoś nadzwyczaj skomplikowane – a przy tym diabelsko skuteczne. Często przyjmuje się, że skuteczność klasyfikatora Bayesa stanowi punkt odniesienia dla innych, bardziej wysublimowanych rozwiązań. Wcale nie tak łatwo jest go pobić!

Sztuczna inteligencja (ang. Artificial Intelligence lub w skrócie: AI) to system komputerowy, którego zadaniem jest naśladowanie czynności wykonywanych przez człowieka.

Jak ocenić, czy system AI wykonuje swoje zadanie skutecznie? Na to pytanie postaram się odpowiedzieć w niniejszym wpisie..

Sztuczna inteligencja w grach

Przez długi czas wierzono, iż królewska gra planszowa, jaką są szachy, jest tak skomplikowana, że maszyna cyfrowa nigdy nie będzie w stanie pokonać szachowego arcymistrza. Pierwszy raz komputer (a konkretnie program Deep Blue) zwyciężył mistrza świata w roku 1996 – choć trzeba wspomnieć, że w kilku następnych partiach Garri Kasparow skutecznie mu się “odgryzł”. Wzrost mocy obliczeniowych w kolejnych latach spowodował jednak, że dziś nawet najwspanialszy geniusz ludzki nie ma najmniejszych szans w starciu z “komputerowym rzemieślnikiem”.

W roku 2016 padł kolejny bastion ludzkiej dominacji. Program o nazwie AlphaGo pokonał w stosunku 4 do 1 Lee Seedola – mistrza gry w go. Jedną z ostatnich domen ludzkiego intelektu w obszarze gier pozostaje więc brydż. Bronimy się co prawda dzielnie przed komputerowymi barbarzyńcami, lecz i tu nasze dni są już najwyraźniej policzone.

Możemy zatem zaryzykować następujące kryterium pozytywnej oceny skuteczności sztucznej inteligencji w dziedzinie gier: sztuczna inteligencja gra skutecznie, jeśli wygrywa z mistrzem świata.

Sztuczna inteligencja w postrzeganiu rzeczywistości

Metody sztucznej inteligencji sprawdzają się bardzo dobrze w zadaniach określonych sztywnymi regułami. Właśnie dlatego tak świetnie radzą sobie w grach – których zasady są precyzyjnie ustalone. W zadaniach związanych z postrzeganiem otaczającej rzeczywistości – gdzie nie obowiązują już tak sztywne reguły – kompetencje “Matrixa” pozostają jednak póki co w tyle za umiejętnościami człowieka.

https://deepomatic.com/en/introduction-to-computer-vision-and-image-recognition/

Nawet trzyletnie dziecko bez trudu rozpozna, że na powyższym obrazku przedstawiony jest pies, a nie kot. Zaawansowany system sztucznej inteligencji nie będzie miał niestety aż tak niezachwianej pewności w tym względzie (według niego zapewne jest to pies – 97%, ale ostatecznie... kto wie?).

W przypadku postrzegania zewnętrznego świata nie oczekujemy od sztucznej inteligencji więcej niż od samych siebie. Wręcz przeciwnie: porównujemy skutki jej działania z efektami percepcji ludzkiej i jesteśmy usatysfakcjonowani, gdy kompetencje maszyny okazują się przynajmniej zbliżone do umiejętności człowieka. Jaką mamy zatem korzyść z zastosowania sztucznej inteligencji, jeśli postrzega ona rzeczywistość w sposób niedoskonały? Ano taką, że ona to robi niesłychanie szybko. Sztuczna inteligencja w przeciągu sekundy przegląda miliony obrazków i automatycznie wybiera z nich – nawet jeśli tylko z 97-procentową pewnością – wszystkie te, na których zaprezentowany jest pies. Wypoczęty człowiek być może nie pomyli się w tym względzie ani razu, lecz w ciągu sekundy jest w stanie przeanalizować co najwyżej kilka obrazków.

Miary jakości

W celu oceny skuteczności systemu komputerowego w obrębie zadań związanych z postrzeganiem otaczającej nas rzeczywistości efekty działania sztucznej inteligencji porównuje się z wynikami percepcji ludzkiej. Uznajemy, że system działa skutecznie, jeśli zachodzi wysoka zgodność pomiędzy tym, co odnotowuje komputer, a tym, co postrzega człowiek. Posłużmy się w tym względzie przykładem, jakim jest zadanie identyfikacji spamu.

Złoty wzorzec

Aby ocenić skuteczność działania systemu, wybieramy pewną próbkę – np. 100 losowo dobranych wiadomości mailowych – po czym prosimy człowieka o zaklasyfikowanie każdej z nich do jednej z dwóch klas: SPAM lub NIE-SPAM.

Próbkę, której wszystkie obiekty zostały zaklasyfikowane przez człowieka, określamy mianem złotego wzorca (ang. golden standard).

Miara dokładności

Miara dokładności (ang. accuracy) mówi, jaka część obiektów złotego wzorca została przez system zaklasyfikowana w sposób zgodny z decyzjami człowieka. Jeśli na przykład system klasyfikuje wszystkie maile identycznie jak człowiek, miara jego dokładności wynosi 100%. Klasyfikator, który działa z dokładnością powyżej 90%, może zostać uznany za skuteczny.

Wysoka miara dokładności nie zawsze jednak prowadzi do zaspokojenia naszych oczekiwań wobec systemu. Zmodyfikujmy nieco nasze wcześniejsze zadanie dla systemu sztucznej inteligencji, definiując je tym razem w sposób następujący: “Wykryj wszystkie maile, w których mowa jest o turystyce”.

Załóżmy, że w złotym wzorcu 3 spośród 100 maili zaklasyfikowane zostały przez człowieka jako związane z turystyką (zgodnie ze średnim rozkładem tematyki korespondencji elektronicznej trafiającej do przypadkowego odbiorcy), a pozostałe 97 – jako związane z innymi tematami. Wyobraźmy sobie teraz, że po wielu miesiącach żmudnych wysiłków opracowaliśmy wreszcie sztuczną inteligencję, która rozpoznaje maile turystyczne z dokładnością 95%. Całkiem nieźle, prawda?

Tyle tylko, że ktoś inny wpadł tymczasem na zupełnie inny pomysł: opracował mianowicie system, który działa z wyższą dokładnością, gdyż... wszystkie maile klasyfikuje jako NIE-turystyczne, w wyniku czego wykazuje na złotym wzorcu dokładność 97%!

Jaki z tego wniosek? Miara dokładności nie ma praktycznego zastosowania w sytuacji, w której jedna z klas wyraźnie dominuje nad innymi pod względem liczności. Trzeba w takim przypadku poszukać innych miar skuteczności.

Miara precyzji

Miara precyzji (ang. precision) mówi, jaka część obiektów przypisanych przez system do interesującej nas klasy została wskazana poprawnie. Jeśli na przykład opracowana przez nas sztuczna inteligencja zidentyfikowała cztery maile turystyczne wśród stu objętych złotym wzorcem, przy czym w zbiorze tym faktycznie znalazły się wszystkie trzy wiadomości zaklasyfikowane jako turystyczne przez człowieka, miara precyzji naszego rozwiązania wynosi 75%.

To oczywiście całkiem niezły wynik. Znowuż jednak znalazł się ktoś, kto opracował system, który pośród stu maili zidentyfikował co prawda tylko jeden o tematyce turystycznej, za to w pełni prawidłowo. Miara precyzji jego rozwiązania wynosi zatem 100%, pomimo iż dwa z trzech maili zostały przecież przez jego system pominięte!

Potrzebujemy zatem jeszcze innego kryterium oceny.

Miara pokrycia

Miara pokrycia (ang. recall) mówi, jaka część obiektów należących do interesującej nas klasy została poprawnie wskazana przez system. Pod względem tej miary nasze rozwiązanie okazuje się absolutnie bezkonkurencyjne – osiąga bowiem pokrycie na poziomie 100%, podczas gdy wspomniany powyżej system, który zidentyfikował zaledwie jeden mail o tematyce turystycznej, wykazuje pokrycie na poziomie jedynie 33%!

Nasza radość nie trwa niestety długo, gdyż znowu ktoś błyskawicznie opracował rozwiązanie, które identyfkuje aż 10 maili o tematyce turystycznej – w tym jednak wszystkie trzy zaklasyfikowane jako turystyczne przez człowieka, dzięki czemu jego program działa co prawda gorzej pod względem miary precyzji (osiąga w tym względzie skuteczność na poziomie zaledwie 30%), jednak pod względem pokrycia w pełni dorównuje naszemu (100%).

I jak tu żyć?

Miara F

Wniosek jest taki, że obiektywna miara ewaluacji skuteczności systemu sztucznej inteligencji powinna brać pod uwagę jednocześnie precyzję oraz pokrycie. Warunek ten spełnia miara F (ang. F-measure), która jest średnią harmoniczną obu powyższych miar: jest to ich podwojony iloczyn podzielony przez ich sumę.

Obliczmy zatem miarę F dla naszego rozwiązania. Najpierw mnożymy: 2 x 75% x 100%, co daje 150%. Następnie dzielimy powyższą wartość przez sumę miar, czyli przez: 75% + 100% = 175%, w wyniku czego otrzymujemy miarę F o wartości 85,7%.

Miara F dla rozwiązania, które wskazało tylko jeden obiekt, wynosi natomiast odpowiednio:

2 x 100% x 33,3% / 133,3% = 50%

podczas gdy miara F dla rozwiązania, które wskazało 10 obiektów wynosi odpowiednio:

2 x 30% x 100% / 130% = 46,2%

Jest jednak na tym świecie jakaś sprawiedliwość!

Post scriptum

Można zadać pytanie: Po co komplikować sobie życie, definiując ostateczną miarę jakości jako średnią harmoniczną dwóch wartości, a nie – jako dobrze wszystkim znaną średnią arytmetyczną?

Chodzi o to, żeby premiować rozwiązania, w których obie miary “współżyją w harmonii”.

Na przykład, dla systemu, który klasyfikuje obiekty z wartościami precyzji i pokrycia po 50%, zarówno średnia arytmetyczna, jak i harmoniczna wynoszą równe 50%.

Jeśli jednak za mocno “przykręcimy śrubę” i skonstruujemy rozwiązanie o wysokiej precyzji na poziomie 90% kosztem niskiego pokrycia na poziomie 10%, to średnia arytmetyczna obu miar ponownie wyniesie 50%, jednak średnia harmoniczna wyraźnie spadnie – dokładnie do wartości 18%.

Dbając o wysoką precyzję, nie zapominajmy o zachowaniu wysokiego pokrycia!

I odwrotnie!

Czym jest analiza morfologiczna i do czego się przydaje?

Analiza morfologiczna ma na celu określenie, jak zbudowany jest wyraz. Wynikiem takiej analizy może być na przykład stwierdzenie, że wyraz mercedesa składa się z rdzenia mercedes oraz końcówki a, która jest w języku polskim charakterystyczna dla przypadków dopełniacza i biernika rzeczowników rodzaju męskiego. Na podstawie tych informacji można wywnioskować, że wyraz mercedesa jest najpewniej dopełniaczem lub biernikiem rzeczownika o formie podstawowej1 mercedes.

Tego typu rozumowanie bardzo przydatne jest między innymi w przypadku wyszukiwania kontekstowego. Dzięki odszyfrowaniu prawdopodobnego kontekstu skierowanego zapytania (czyli na przykład określeniu kim jest pytający, gdzie się aktualnie znajduje oraz jakiego typu informacji poszukuje) zidentyfikowany zostaje dokument najbliżej odpowiadający potrzebom pytającego – nawet jeśli dokument ten nie zawiera dokładnie tych form wyrazowych, których użyto w pytaniu.

W odpowiedzi na frazę “kupię mercedesa” wyszukiwarka Google wyświetla na przykład snippet2 o treści: “Znajdziesz najpopularniejsze modele samochodów Mercedes, takie jak AMG GT, A-klasa, ... Wszystko kupisz. ... Sprzedam Mercedes . Zauważmy, że w snippecie tym nie występuje sensu stricto żadne ze słów zawartych w zapytaniu. Jeśli chodzi o wyraz mercedesa, snippet zawiera jego formę podstawową mercedes, natomiast w przypadku wyrazu kupię – formę innej osoby liczby pojedynczej (kupisz).

Aby móc poprawnie odmieniać wyrazy (tak jak w powyższym przykładzie), system wyszukiwania kontekstowego wymaga wspomagania słownikiem, w którym zawarte będą wszystkie formy wyrazowe danego języka. W przypadku niektórych zastosowań tak wielki zasób stanowi jednak zbędny balast. Na potrzeby klasyfikacji tekstów pod względem ich tematyki bardzo dobrze sprawdza się na przykład uproszczona wersja analizy morfologicznej zwana stemowaniem (ang. stemming). Polega ona na odcięciu końcówki wyrazu (a niekiedy również jego początku) w celu identyfikacji rdzenia. Przykładowo, wynik stemowania dla wyrazów budowa, budowniczy oraz budowlany będzie taki sam: budow. Stemowanie jest procesem znacznie szybszym niż analiza słownikowa, a dla celów klasyfikacji tematycznej – całkowicie wystarczającym.

Analiza wyrazów ze słownikiem

Lematyzacja

Lematyzacja to proces, który dla każdego wyrazu występującego w dokumencie wskazuje wszystkie formy podstawowe, od której wyraz ten może potencjalnie pochodzić. Na przykład w przypadku wyrazu czci tzw. lematyzator (tj. program dokonujący lematyzacji) zwraca informację, iż wyraz ten może pochodzić albo od czasownika czcić, albo od rzeczownika cześć. Podobnie wyraz mamy rozpoznawany jest jako forma pochodna bądź to od czasownika mieć, bądź też od rzeczownika mama, natomiast w przypadku wyrazu droga wskazane zostaje, iż jest on albo formą podstawową odpowiedniego rzeczownika, albo też formą rodzaju żeńskiego przymiotnika drogi.

Współczesne lematyzatory analizują kontekst, w jakim występuje dany wyraz i w przypadku istnienia kilku form podstawowych zwracają tylko tę, która wynika z kontekstu. A zatem nowoczesny lematyzator dla zdania Moja droga siostra nie czci swojej mamy poda informację, że formą podstawową wyrazu droga w tym konkretnym zdaniu jest przymiotnik drogi, formą podstawową wyrazu czci jest czasownik czcić, a formą podstawową wyrazu mamy jest rzeczownik mama.

POS-tagging

Celem tagowania (ang. POS-tagging od: Part of Speech Tagging) jest jednoznaczne określenie, jaką część mowy reprezentuje dany wyraz w zdaniu, w którym został użyty. W przypadku zdania: Moja droga siostra nie czci swojej mamy POS-tagger powinien stwierdzić, że w analizowanym kontekście słowo droga użyte zostało jako przymiotnik, słowo czci – jako czasownik, natomiast słowo mamy – jako rzeczownik.

Współczesne POS-taggery działają natomiast ze skutecznością na poziomie ok. 95–98%, co oznacza, że w niektórych przypadkach zdarza im się zwrócić nieprawidłowy wynik.

Analiza wyrazów bez użycia słownika

W przypadku braku słownika, w którym system komputerowy mógłby sprawdzić istnienie danego wyrazu, analiza jego budowy, a w szczególności stemowanie, odbywa się w sposób dość prymitywny. Większość opracowanych dotychczas na powyższe potrzeby metod opiera się na odcinaniu kolejnych liter od końca wyrazu począwszy – tak długo jak spełnione pozostają odpowiednio zdefiniowane warunki.

Algorytm Portera

Jedną z najpopularniejszych metod stemowania jest algorytm Portera. Powyższy zrzut ekranowy demonstruje efekty działania tej metody. Jak widać, dla wyrazu isolation algorytm wyznaczył rdzeń isol poprzez odcięcie końcówki ation. Jednak wynikiem stemowania wyrazu ration jest całość tego słowa. Wynika to z faktu, że potencjalny rdzeń pozostały po odcięciu końcówki ation, czyli pojedyncza litera r, jest zbyt krótki według założeń przyjętych przez algorytm, by możliwe było zastosowanie tego typu odcięcia. Podobna sytuacja ma miejsce w przypadku pary wyrazów: conditionalzonal. Końcówka ness została z kolei odcięta od wyrazu madness. W wyrazie hopefulness algorytm wykonuje odcięcie dwóch końcówek: rzeczownikowej ness oraz przymiotnikowej ful, natomiast wymyślony przez użytkownika rozwiązania wyraz aness pozostaje nienaruszony przez algorytm z dokładnie tego samego powodu co wyraz ration.

Reguły algorytmu Portera

Algorytm opiera się na ręcznie opracowanych regułach. Każda z nich składa się z dwóch części: pierwsza z części mówi, jakie warunki musi spełniać potencjalny rdzeń, aby można było zastosować operację odcięcia zdefiniowaną w drugiej części.

Przykładowa reguła algorytmu Portera ma następującą postać:

(m>0) ational -> ate

Pierwsza część powyższej reguły (m>0) narzuca ograniczenie na rozmiar rdzenia po odcięciu końcówki – rozmiar ten (który w pewnym przybliżeniu jest równoważny liczbie sylab) musi być większy niż zero. Druga część reguły (ational -> ate) wskazuje, jak powinna zostać zastąpiona końcówka.

Zgodnie z powyższą regułą wyraz relational zastąpiony zostanie wyrazem relate, jednakże wyraz rational pozostanie bez zmian, gdyż rdzeń r nie spełnia zdefiniowanego warunku rozmiaru.

Czy komputer może być kreatywny?

Jedną z przeszkód dla skutecznej automatycznej analizy morfologicznej z użyciem słownika stanowi ludzka kreatywność leksykalna. Praktycznie co dzień powstają w każdym języku nowe słowa. Aktualizowany na bieżąco Ciekawe zestawienie i ranking polskich neologizmów z ostatnich 10 lat można znaleźćna stronie: https://polszczyzna.pl/neologizmy-ranking/.

W momencie tworzenia niniejszego wpisu czołówka prezentowała się akurat następująco:

  1. plażing
  2. urlop tacierzyński
  3. alternatywka
  4. jesieniara
  5. smakówka

A przecież możliwości tworzenia nowych słów poprzez dodawanie końcówek lub przedrostków – czy to do wyrazów polskich, czy też zaczerpniętych z języka obcego, w szczególności angielskiego – są praktycznie nieograniczone (porównaj chociażby takie słowa jak: megafajny, makroproducent czy fejsować).

Algorytmy maszynowe nie powinny w tym zakresie pozostawać w tyle. Aby system komputerowy miał możliwość analizy słownikowej nowo powstałych wyrazów, powinny się one znaleźć w jego słowniku.

W powyższym celu system może samodzielnie wygenerować potencjalne neologizmy – na przykład łącząc popularne słowa z popularnymi przedrostkami. Dzięki temu w słowniku systemowym znaleźć się mogą wyrazy, których na próżno szukać w tradycyjnych źródłach leksykograficznych – takie jak chociażby: supermaszyna czy eko-promocja.

Tego typu kreatywność słowotwórczą komputera trzeba jednak odpowiednio kontrolować. Przede wszystkim bowiem proces łączenia jednostek leksykalnych będzie nieuchronnie prowadził do wygenerowania wyrazów niestosowanych w języku. Ten problem można akurat skutecznie wyeliminować, poddając każde wygenerowane automatycznie słowo odpowiedniej weryfikacji, a następnie dołączając do systemowego słownika jedynie wyrazy o odpowiednio wysokiej częstości występowania w wybranym korpusie tekstów (chociażby w treściach indeksowanych przez wyszukiwarkę Google).

Co gorsza jednak, słowa automatycznie wygenerowane przez system mogą okazać się tzw. fałszywymi derywatami, czyli wyrazami o zupełnie innym znaczeniu niż sugerowałyby to ich elementy składowe, na przykład:

mini+ster ≠ minister
nie+dzielny ≠ niedzielny
pod+miot ≠ podmiot
pod+ręcznik ≠ podręcznik
tera+kota ≠ terakota

Odpowiadając zatem na pytanie postawione w tytule bieżącej sekcji niniejszego wpisu: Tak, komputer może być kreatywny. I to niestety aż za bardzo!

Podsumowanie

Analiza morfologiczna, czyli analiza budowy wyrazów, jest niezbędnym elementem wielu systemów przetwarzania języka naturalnego. W przypadku niektórych zastosowań konieczne jest korzystanie z wyczerpującego słownika danego języka. Obecnie dąży się do tego, aby w pojedynczym procesie połączyć lematyzację z tagowaniem.

Niekiedy jednak wystarczające okazują się metody bezsłownikowe, których działanie ogranicza się do ustalenia rdzeni poszczególnych wyrazów.

Kreatywność ludzka prowadzi do nieustannego powstawania nowych wyrazów. Komputer też można skłonić do kreatywności słowotwórczej, jednakże jej rezultaty mogą być bardzo nieoczekiwane, a wręcz zabawne.


1 Forma podstawowa wyrazu to ta, która pojawia się w słownikach – np. mianownik liczby pojedynczej w przypadku rzeczowników czy bezokolicznik w przypadku czasowników.
2 Snippet to wycinek strony internetowej zwracany przez wyszukiwarkę w odpowiedzi na sformułowane zapytanie.

Jak czyta tekst człowiek

W jaki sposób dziecko uczy się najczęściej czytania w swym ojczystym języku? Najpierw poznaje wszystkie symbole graficzne (litery, znaki interpunkcyjne, oznaczenia akcentów, itp.), za pomocą których zapisywana jest jego rodzima mowa. Następnie uczy się powiązań pomiędzy symbolami graficznymi a głoskami oraz łączenia głosek w wyrazy i frazy w miarę odczytu. Po jakimś czasie jest już w stanie jednym spojrzeniem oka ogarnąć nawet całe zdania.

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:

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:

<w> p3
p o2
o s2
s p2
p i3
i e3
e s3
s z3
z <w>2
<w> s2
s i2
i ę2
ę <w>2
z y/td>1
y <w>1

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<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<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<w>po sp ie sz <w> s i ę <w>

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

<w>po sp ie sz <w>s <w>p ie sz<w>po sp ie sz <w>s <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ą.

Koncepcja przedstawiania wyrazów czy złożonych z nich tekstów za pomocą liczb jest “stara jak świat”. W procesie szyfrowania teksty przekształcane są w ciągi liczb, natomiast podczas deszyfrowania, w sposób wiadomy tylko odbiorcy, dokonuje się operacji odwrotnej. Dzięki temu szyfrowana wiadomość nie dostanie się w niepowołane ręce. Podobno już w starożytnej Grecji stosowano narzędzia szyfrujące: “Wąski pasek pergaminu lub skóry nawijano na laskę, zapisując tekst wzdłuż niej na stykających się brzegach. Będący adresatem posiadacz laski o identycznej grubości mógł szybko odczytać tekst przesłania. W postaci rozwiniętej, z pozbawionymi sensu, rozrzuconymi literami nie miał żadnej wartości dla osoby niepowołanej; zrozumiały był jedynie dla właściwego odbiorcy, który dopasował go do swego wzorca.” (https://pl.wikipedia.org/wiki/Skytale).

Już w 1949 roku amerykański matematyk Warren Weaver sformułował tezę mówiącą, że metodami szyfrowania i deszyfrowania można automatycznie, czyli za pomocą maszyn liczących, przełożyć tekst z jednego języka na inny. Jego wizja spełniła się jednak dopiero po 65 latach, gdy zaczęto publikować pierwsze artykuły o praktycznym wykorzystaniu sieci neuronowych na potrzeby tłumaczenia automatycznego. Dlaczego nie wcześniej? Zapewne z tego powodu, że nie potrafiono wtedy jeszcze reprezentować numerycznie tekstu w taki sposób, aby operacje wykonywane przez sieci neuronowe nie prowadziły do zagubienia sensu wypowiedzi.

Na czym polega trudność w przypadku liczbowej reprezentacji wyrazów?

Wydaje się na pozór, że wyrazy można reprezentować w postaci kolejnych liczb naturalnych, chociażby w kolejności alfabetycznej – przynajmniej w obrębie dokumentu, który jest przetwarzany. Przypuśćmy zatem, że chcemy przetworzyć komputerowo (na przykład w celu przetłumaczenia na inny język czy na potrzeby wyekstrahowania z niego wiedzy) dokument składający się z następujących czterech zdań:

Stolicą Austrii jest Wiedeń.
Stolicą Australii jest Canberra.
Walutą Austrii jest euro.
Walutą Australli jest dolar.

W celu zastosowania metod uczenia maszynowego musimy dokument ten przekształcić do postaci numerycznej. Ułóżmy zatem wszystkie występujące w powyższym tekście wyrazy w porządku alfabetycznym (pomijając kwestię wielkich i małych liter), a następnie przypiszmy poszczególnym wyrazom kolejne liczby naturalne:

australii: 1
austrii: 2
canberra: 3
dolar: 4
auro: 5
jest: 6
stolicą: 7
walutą: 8
wiedeń: 9

Przypuśćmy, że każde z przedstawionych powyżej czterech zdań przedstawimy jako wektor wyrazów wchodzących w jego skład, przy czym każdy wyraz będzie reprezentowany przez odpowiadającą mu liczbę. W takim przypadku dwa pierwsze zdania dokumentu moglibyśmy przedstawić następująco:

Stolicą Austrii jest Wiedeń → {7, 2, 6, 9}
Stolicą Australli jest Canberra → {7, 1, 6, 3}

Chcielibyśmy teraz określić numeryczną reprezentację obu powyższych zdań łącznie. Naturalną operacją wydaje się dodanie obu wektorów:

{7, 2, 6, 9} +
{7, 1, 6, 3} =
{14, 3, 12, 12}

Powstały w ten sposób wektor wynikowy zawiera na trzech miejscach indeksy wyrazów, które nie występują w dokumencie (14 oraz dwukrotnie 12), a na jednym miejscu – wartość 3, czyli liczbę odpowiadającą wyrazowi “canberra”. Okazuje się zatem, że połączenie wyrazów “austrii” oraz “australii” dało nam wyraz “canberra”!

Sieci neuronowe mogą co prawda wykonywać znacznie bardziej złożone operacje na liczbach (oprócz dodawania także mnożenie czy działania z użyciem funkcji), jednak przy zastosowaniu powyższej reprezentacji u podłoża tego typu wyliczeń leżałoby nieuzasadnione założenie, iż np. wyraz “canberra” ma wartość równą sumie wartości wyrazów “australia” oraz “austria”. Nie ma ono niestety sensu semantycznego, dlatego poszukać należy zupełnie innej reprezentacji liczbowej wyrazów.

Co to jest “gorąca jedynka”?

Przyjmijmy, że wszystkie wyrazy mają taką samą wartość – dokładnie 1. Ponownie uszeregujmy teraz zbiór wyrazów zawartych w dokumencie w pewien określony sposób (na przykład w porządku alfabetycznym), reprezentując jednak tym razem każdy z wyrazów w postaci wektora, który na “właściwym” miejscu ma wartość 1, natomiast na wszystkich pozostałych miejscach – wartość zero.

Przykładowo wyraz “australii” (pierwszy w alfabecie) ma jedynkę na pierwszym miejscu:

{1, 0, 0, 0, 0, 0, 0, 0, 0}

podczas gdy wyraz “dolar” (czwarty w alfabecie) ma jedynkę na czwartym miejscu:

{0, 0, 0, 1, 0, 0, 0, 0, 0}

Reprezentację całego zdania otrzymuje się w takim przypadku poprzez wyznaczenie sumy logicznej wektorów wszystkich składających się na to zdanie wyrazów (przy czym suma logiczna dwóch jedynek ma wartość jeden). Na przykład reprezentację zdania:

Stolicą Austrii jest Wiedeń

wyznaczamy następująco:

{0, 0, 0, 0, 0, 0, 1, 0, 0} +
{0, 1, 0, 0, 0, 0, 0, 0, 0} +
{0, 0, 0, 0, 0, 1, 0, 0, 0} +
{0, 0, 0, 0, 0, 0, 0, 0, 1} =
{0, 1, 0, 0, 0, 1, 1, 0, 1}

Analogicznie postępujemy w celu połączenia informacji zawartych w zdaniach. Na przykład łączna reprezentacja zdań: pierwszego (“Stolicą Austrii jest Wiedeń”) i drugiego (“Stolicą Australii jest Canberra”) ma postać:

{1, 1, 1, 0, 0, 1, 1, 0, 1}

Jedynki występują powyżej na miejscach odpowiadających wyrazom, które pojawiły się w pierwszym lub w drugim zdaniu.

Reprezentacja całego dokumentu (wszystkich czterech podanych wcześniej zdań) ma natomiast postać:

{1, 1, 1, 1, 1, 1, 1, 1, 1}

Taki sposób numerycznego reprezentowania wyrazów nosi angielską nazwę “one-hot encoding”, co z przymrużeniem oka przetłumaczyć można jako “kodowanie z gorącą jedynką”. Bardziej adekwatnym polskim odpowiednikiem formalnym powyższej nazwy angielskiej wydaje się jednak tłumaczenie: “kodowanie 1 z n”.

Jak reprezentować liczność występowania?

Oczywistym niedostatkiem “kodowania z gorącą jedynką” jest fakt, że nie bierze ono pod uwagę liczności wystąpienia poszczególnych wyrazów. Choćby w pewnym dokumencie 1000 razy pojawił się wyraz “stolica”, jego waga będzie identyczna jak wyrazu “jarmuż”, o ile tylko drugi z powyższych wyrazów pojawił się w dokumencie choć raz (i to być może przez pomyłkę). System rozpoznawania tematyki takiego dokumentu może w takim przypadku błędnie przyjąć, że tekst dotyczy zdrowej żywności, a nie kwestii polityczno-administracyjnych.

Dlatego właśnie często spotykanym sposobem kodowania jest liczność występowania, zgodnie z którą w wektorze umieszcza liczby wystąpień poszczególnych wyrazów. Reprezentacja naszego przykładowego czterozdaniowego dokumentu ma w przypadku takiego kodowania następującą postać:

{2, 2, 1, 1, 1, 4, 2, 2, 1}

Wyraz “jest”, któremu odpowiada szósty element wektora, występuje w naszym dokumencie 4 razy itd.

Jak reprezentować częstość występowania?

W zestawach złożonych z wielu dokumentów liczność występowania faworyzuje jednak te z wyrazów, które pojawiają się w dłuższych dokumentach (siłą rzeczy ich wystąpień jest po prostu w takich dokumentach więcej). Aby więc “wyrównać szanse” wyrazów pochodzących z krótszych dokumentów, stosuje się reprezentację za pomocą częstości występowania. Zgodnie z nią liczność występowania wyrazu dzielona jest przez liczbę wszystkich wyrazów danego dokumentu. Nasz przykładowy cztero-zdaniowy dokument z niniejszego artykułu jest zgodnie z powyższą metodą reprezentowany w postaci następującego wektora (łącznie wyrazów w dokumencie jest 16, więc każdy z elementów wektora liczności dzielimy przez 16):

{⅛, ⅛, 1/16, 1/16, 1/16,¼, ⅛, ⅛, 1/16}

Polskiemu pojęciu częstość występowania odpowiada angielskie określenie term frequency, oznaczane skrótem TF.

Co oznacza reprezentacja TF-IDF?

Załóżmy, że system komputerowy ma określić tematykę danego tekstu. Wydaje się rozsądne, aby w pierwszej kolejności wziął on pod uwagę wyrazy występujące w tym tekście najczęściej. Czy słusznie? W naszym przykładowym dokumencie najczęściej występuje akurat wyraz “jest”, który niestety niewiele mówi nam o tematyce stosownego tekstu.

Remedium na powyższą bolączkę stanowi reprezentacja TF-IDF. Z jednej strony bierze ona pod uwagę częstość występowania poszczególnych wyrazów w dokumencie (TF), z drugiej jednak strony obniża ona wartość wszechobecnym wyrazom “mało informatywnym” (czyli takim jak: “jest”, “w” czy “z”) poprzez wprowadzenie drugiego czynnika – IDF.

Załóżmy, że oprócz naszego przykładowego dokumentu system analizuje dodatkowo jeszcze trzy inne dokumenty (dysponujemy zatem teraz zestawem czterech dokumentów). Przypuśćmy też, że w każdym z pozostałych trzech dokumentów pojawia się wyraz “jest”, jednak nie występuje w nich żaden inny z wyrazów użytych w naszym przykładowym dokumencie. Wartość IDF (ang. Inverse Document Frequency) danego wyrazu obliczana jest następująco: liczba wszystkich dokumentów zestawu dzielona przez liczbę dokumentów zawierających ten wyraz. Dla wyrazu “jest” IDF wynosi 1 (4/4), natomiast dla pozostałych wyrazów – 4 (4/1).

W przypadku reprezentacji TF-IDF oba czynniki (TF oraz IDF) mnożone są przez siebie, przy czym w odniesieniu do do drugiego z nich stosowana jest najczęściej funkcja logarytmiczna, który to szczegół w tym momencie jednak pominiemy. Reprezentacja naszego przykładowego dokumentu ma więc następującą reprezentację TF-IDF:

{½, ½, ¼, ¼, ¼, ¼, ½, ½, ¼}

I to nam się podoba! Najwyższą wartość mają w przypadku takiej reprezentacji wyrazy: stolicą, prezydentem, Polski, Rosji, które właściwie oddają tematykę analizowanego tekstu.

Co oznacza hipoteza dystrybucyjna?

Reprezentacje: “gorącej jedynki” czy też częstościowe dostarczają informacji na temat zależności pomiędzy wyrazami a dokumentami (informują one, czy dany wyraz pojawia się w dokumencie, jak często w nim występuje i jak częstość ta ma się do częstości jego występowania w innych dokumentach). Nie zawierają one jednak jakichkolwiek informacji na temat znaczenia analizowanych wyrazów.

Czy istnieje zatem jakikolwiek sposób liczbowej reprezentacji znaczenia wyrazów? Z pomocą przychodzi nam w  tym miejscu tzw. hipoteza dystrybucyjna, która mówi, że słowa występujące w podobnych kontekstach w obrębie dużych zbiorów danych tekstowych mają prawdopodobnie podobne znaczenie.

Nasz przykładowy dokument w dużym stopniu potwierdza tę hipotezę: w podobnych kontekstach pojawiają się bowiem w  nim pary wyrazów: <dolar, euro>, <canberra, wiedeń> oraz <stolicą, walutą>. Z powyższych trzech par pierwsze dwie można śmiało uznać za pary wyrazów o podobnym znaczeniu.

Jest dość prawdopodobne, że wyrazy “canberra” oraz “wiedeń” występują w podobnych kontekstach również w innych dokumentach. Natomiast prawdopodobieństwo wystąpienia w podobnych kontekstach wyrazów z ostatniej pary, czyli “stolicą” oraz “walutą”, wydaje się już dużo niższe. Dlatego właśnie w sformułowaniu hipotezy dystrybucyjnej pojawia się pojęcie “dużych zbiorów danych tekstowych”.

Spróbujmy teraz dla podobnych znaczeniowo wyrazów “austrii” i “australii“zbudować ich reprezentację wektorową, wykorzystując w tym celu informacje na temat wyrazów współwystępujących z nimi w tych samych zdaniach w obrębie naszego przykładowego dokumentu.

Dla przypomnienia nasz przykładowy dokument ma następującą postać:

Stolicą Austrii jest Wideń.
Stolicą Australli jest Canberra.
Walutą Austrii jest euro.
Waliutą Australii jest dolar.

Poszczególne wyrazy z powyższego dokumentu po uszeregowaniu alfabetycznym prezentują się zaś następująco:

australii: 1
austrii: 2
canberra: 3
dolar: 4 euro: 5 jest: 6
stolicą: 7
walutą: 8
wideń: 9

Na podstawie pierwszego ze zdań naszego przykładowego dokumentu zbudujmy teraz wektor dla wyrazu “austrii”, informujący o liczbie wystąpień wyrazów z nim współwystępujących w analizowanym zdaniu (na miejscach odpowiadających wyrazom: “jest”, “stolicą” oraz “wiedeń” pojawią się jedynki, natomiast na pozostałych – zera):

{0, 0, 0, 0, 0, 1, 1, 0, 1}

Zbudujmy analogicznie wektor dla wyrazu “australii” na podstawie drugiego zdania z naszego dokumentu:

{0, 0, 1, 0, 0, 1, 1, 0, 0}

Wektory te są do siebie dość podobne: różnią się na zaledwie dwóch miejscach z dziewięciu.

Podobnie zbudować możemy wektory dla wskazanych powyżej dwóch wyrazów na podstawie zdań trzeciego i czwartego:

{0, 0, 0, 0, 1, 1, 0, 1, 0} (wektor wyrazów współwystępujących dla wyrazu “austrii”)
{0, 0, 0, 1, 0, 1, 0, 1, 0} (wektor wyrazów współwystępujących dla wyrazu wyrazu “australii”)

Możemy teraz zsumować oba wektory opisujące wyraz “austrii”:

{0, 0, 0, 0, 0, 1, 1, 0, 1} +
{0, 0, 0, 0, 1, 1, 0, 1, 0} =
{0, 0, 0, 0, 1, 2, 1, 1, 1}

Możemy również zsumować informacje z obu wektorów opisujących wyraz “australii”:

{0, 0, 1, 0, 0, 1, 1, 0, 0} +
{0, 0, 0, 1, 0, 1, 0, 1, 0} =
{0, 0, 1, 1, 0, 2, 1, 1, 0}

Czy wektory obliczone na podstawie całego dokumentu dla wyrazów “austrii” oraz “australii” są do siebie podobne? Spróbujmy to obliczyć.

Jak wyznaczyć podobieństwo reprezentacji wektorowych?

Czy można jakimś prostym wzorem obliczyć, jak bardzo wektory reprezentujące różne wyrazy są do siebie podobne? Można. Służy do tego miara podobieństwa cosinusowego, której wartości zawierają się między 0 a 1. Podobieństwo wektorów identycznych wynosi 1, natomiast maksymalnie różniących się od siebie wynosi 0.

Odpowiedni wzór przedstawia się następująco:

Obliczmy najpierw iloczyn skalarny wektorów reprezentujących odpowiednio wyrazy “austrii” oraz “australii” (licznik powyższego wzoru):

A * B = (0 + 0 + 0 + 0 + 0 + 4 + 1 + 1 + 0) = 6

Obliczmy teraz miary euklidesowe obu wektorów (wchodzące w skład mianownika):

||A|| = sqrt(1 + 4 + 1 + 1 + 1) = sqrt(8)

||B|| = sqrt(1 + 1 + 4 + 1 + 1) = sqrt(8)

similarity = 6 / (srtq(8) * sqrt(8)) = ¾

Okazuje się zatem, że miara podobieństwa obu wektorów jest rzeczywiście dość wysoka.

Czym jest reprezentacja Word2Vec?

Kłopot w przypadku reprezentacji zgodnej z hipotezą dystrybucyjną stanowi sam wymiar wektorów, który jest dokładnie tak duży, jak liczba wyrazów wchodzących w skład zestawu dokumentów (w skrajnym przypadku może ona osiągać wartości rzędu milionów). Wektory o tak dużej liczbie elementów nie nadają się na przykład do obliczeń realizowanych za pomocą sieci neuronowych.

Word2Vec jest reprezentacją wyrazów, u której podstaw leży hipoteza dystrybucyjna, mającą jednak tę dodatkową własność, że wymiar wektora nie przekracza w jej przypadku wartości rzędu kilkuset współrzędnych. Co więcej, wymiar ten nie zależy od wielkości słownika, lecz może być arbitralnie wybrany przez architekta systemu. Reprezentacja Word2Vec oddaje zatem relację podobieństwa wyrazów, a jednocześnie umożliwia realizację zadań z zakresu NLP (takich jak tłumaczenie automatyczne, analiza wydźwięku czy automatyczne generowanie tekstu) przy użyciu sieci neuronowych.

Poniższe zestawienia przedstawiają listy wyrazów, dla których wektory obliczone na podstawie tekstów z Wikipedii są najbardziej podobne do wektorów odpowiadających wyrazom z nagłówków obu kolumn, czyli odpowiednio: “nagoya” (dla lewej kolumny) oraz “coffee” (dla prawej kolumny), co oznacza, że miara podobieństwa osiąga w przypadku tych wyrazów najwyższą wartość.

Podsumowanie

Istnieje wiele sposobów reprezentacji wyrazów za pomocą liczb. Obecnie najbardziej popularną z nich jest wektor liczbowy wyznaczany za pomocą metody Word2Vec. Ma on wymiar ustalony przez architekta systemu – mieszczący się najczęściej w przedziale od 300 do 500 współrzędnych. Wektor ten odzwierciedla znaczenie wyrazów w taki sposób, że wyrazom o podobnym znaczeniu odpowiadają wektory, dla których miara podobieństwa ma wysoką wartość.

Jedną z głównych zalet reprezentowania dokumentów w postaci cyfrowej jest łatwość wyszukiwania w nich wyrazów i fraz. W wersji papierowej księgi “Gra o tron” próba odnalezienia pierwszego wystąpienia imienia bohaterki Daenerys może przypominać “poszukiwanie igły w stogu siana”. A w wersji cyfrowej? Wystarczy użyć funkcji “Znajdź”. Równie łatwo jest zrealizować proces zastępowania – stosując globalnie polecenie “Zamień”, możemy na przykład wszystkie wystąpienia imienia Daenerys podmienić na pisownię Denerys.

Funkcja “Zamień / Zastąp” nie pozwala jednak odszukać prostych wzorców, które człowiek z łatwością spostrzega gołym okiem. Wprawnemu czytelnikowi wystarczy bowiem krótkie spojrzenie na stronę tekstu, by bez większego trudu wychwycić na niej wszelkie wystąpienia jakiejkolwiek daty, czy też dowolnego adresu pocztowego bądź mailowego. Jak natomiast dokonać tego samego za pomocą funkcji “Znajdź”? Nie jest to niestety wcale takie łatwe!

Wyszukiwaniu i zastępowaniu różnorodnych fragmentów tekstu o regularnej budowie służy mechanizm określany mianem wyrażeń regularnych.

Co to jest wyrażenie regularne?

Wyrażenie regularne to – prosto rzecz ujmując – wzorzec reprezentujący zbiór wszystkich napisów, które do niego pasują. Dla wskazanego wyrażenia regularnego odpowiednio skonstruowany mechanizm komputerowy potrafi wyszukać w tekście wszystkie pasujące do niego napisy.

  1. Wyrażeniem regularnym może być dowolny znak, który (jeśli nie jest znakiem specjalnym – porównaj poniżej) reprezentuje wyłącznie sam siebie. Gdy na przykład wyrażenie regularne ma postać litery “a”, mechanizm obsługujący to wyrażenie szuka w tekście pierwszego wystąpienia wskazanej litery (np. Ola ma kota).
  2. Wyrażeniem regularnym może być też ciąg znaków, który również reprezentuje wyłącznie sam siebie. Jeśli wyrażeniem regularnym jest ciąg liter: “kot”, mechanizm szuka w tekście dokładnie takiego zapisu (np. Ola ma kota).
  3. Znak specjalny * w wyrażeniu regularnym reprezentuje powtórzenie poprzedzającego go znaku dowolną liczbę razy lub też brak takiego powtórzenia bądź całkowity brak wystąpienia powyższego znaku. Na przykład do wyrażenia regularnego “hur*a*” pasują napisy: hu, hua, hur, hura, hurra, hurraa itd.
  4. Fragmenty wyrażeń regularnych można grupować za pomocą nawiasów. Na przykład do wyrażenia regularnego “hu(ra)*” pasują napisy: hu, hura, hurara itd.
  5. Znak specjalny | w wyrażeniu regularnym reprezentuje alternatywę. Na przykład do wyrażenia regularnego “Kowalsk(i|a)” pasują napisy: Kowalski oraz Kowalska.

Błędy i pomyłki

W praktyce zdarza się, że program wyszukujący napisy pasujące do danego wyrażenia regularnego działa jednak nie do końca tak, jak byśmy tego oczekiwali. Jak to możliwe? Zapewne autor wyrażenia regularnego popełnił w tym przypadku błąd, a najczęstszą przyczyną zaistniałej pomyłki jest błędne zrozumienie priorytetu operacji.

Priorytet operacji

W przypadku wyrażeń regularnych priorytet operacji przedstawia się następująco:

  1. grupowanie za pomocą nawiasów: ()
  2. znak specjalny *
  3. połączenie (ciąg) znaków
  4. znak specjalny |

Do wyrażenia regularnego “(ha)*” pasują zatem napisy: ha, haha, hahaha itd., gdyż najpierw grupujemy znaki h oraz a za pomocą nawiasów, a dopiero potem wykonujemy powtórzenie za pomocą gwiazdki. Do wyrażenia regularnego “ha*” pasują natomiast napisy h, ha, haa, haaa itd., ponieważ najpierw stosujemy operację powtórzenia dla znaku a, a dopiero potem łączymy wynik z pozostałym ciągiem znaków.

Do wyrażenia regularnego “Kowalski|a” pasują z kolei napisy: Kowalski oraz a (ale już nie napis Kowalska), gdyż połączenie znaków wiąże mocniej niż alternatywa.

Równoważność wyrażeń regularnych

Różne wyrażenia regularne mogą reprezentować te same zbiory napisów. Na przykład wyrażenie “kot|pies” jest równoważne wyrażeniu “pies|kot”, a wyrażenie (kot)* jest równoważne wyrażeniu ((kot)*)*. Wydaje się, że taka własność wyrażeń regularnych jest cechą bardzo korzystną – można bowiem dzięki niej na różne sposoby wyrazić polecenie odszukania odpowiedniego tekstu (tak jak przy rozwiązywaniu zadania matematycznego dopuszcza się rozmaite metody uzyskania poprawnego wyniku). Kłopot w tym, że autorowi wyrażenia regularnego może wydawać się, iż stosowany przez niego zapis jest równoważny z innym, podczas gdy tak naprawdę wcale nie jest (np. wyrażenie regularne “Kowalski|a” nie jest równoważne z wyrażeniem regularnym “Kowalski|Kowalska”).

Ułatwienia i rozszerzenia

Wymienione powyżej operacje wyczerpują podstawową (tj. matematyczną) definicję wyrażeń regularnych. Informatycy posunęli się jednak nieco dalej niż matematycy, wprowadzając cały szereg innych działań, które można stosować w przypadku posługiwania się wyrażeniami regularnymi. Najpopularniejsze z nich to: klasy znaków, znak kropki, kwantyfikatory oraz kotwice.

Klasy znaków

Klasy znaków – zapisywane w nawiasach kwadratowych – to inny sposób reprezentacji alternatywy. Na przykład do wyrażenia “[AEO]la” pasują napisy Ala, Ela i Ola. Do wzorca “[A-Z]la” pasują dodatkowo: Bla, Cla, Dla itd.

Można również zdefiniować tzw. klasy negatywne. Wyrażenie “[^pl]” (ze znakiem karetki po nawiasie otwierającym) dopasowuje wszystkie znaki oprócz pl. Tak więc wzorzec regularny “[^pl]asem]” w tekście:

Idzie Jassem lasem, wymachując pasem, ale tylko czasem.

dopasuje wyłącznie fragment zasem z wyrazu czasem.

Klasy znaków można również zapisywać skrótowo; na przykład “\d” oznacza dowolną cyfrę, “\w” oznacza dowolną literę, a “\s” – dowolny biały znak (spacja, tabulator lub podział wiersza).

Znak kropki

Kropka jest znakiem specjalnym. Zastosowana w wyrażeniu specjalnym dopasowuje dowolny znak. Tak więc do wyrażenia regularnego “r.k” dopasują się napisy: rak, rok oraz ryk, ale także na przykład napis: r5k.

Jeśli z kolei chcemy, aby wyrażenie regularne reprezentowało znak specjalny (np. kropkę), musimy taki znak poprzedzić symbolem \. Na przykład posługując się wyrażeniem regularnym: “ai\.POLENG\.pl”, możemy odnaleźć wystąpienie adresu mailowego pracownika naszej firmy.

Kwantyfikatory

Kwantyfikatory służą do wyszukiwania powtórzeń, a jednym z nich jest wspomniany już wcześniej znak specjalny gwiazdki.

Znak specjalny + oznacza co najmniej jedno powtórzenie. Na przykład wyrażenie “hur+a+ dopasuje napisy hura, hurra, hurraa itd., ale nie dopasuje napisu hu.

Znak specjalny ? oznacza z kolei zero lub jedno wystąpienie. Wyrażenie ‘’2020 r\.?’’ dopasowuje zarówno zapis zakończony kropką, jak i jej pozbawiony.

Kwantyfikatory mogą także ograniczać liczbę powtórzeń. Wyrażenie regularne: \d{4} oznacza wystąpienie dokładnie czterech cyfr, a wyrażenie: \w{5,10} – wyraz o długości od pięciu do dziesięciu znaków.

Kotwice

Kotwice ograniczają miejsce wystąpienia napisu w tekście.

Znak specjalny ^ informuje o tym, że dopasowany napis musi znajdować się na początku tekstu.

Znak specjalny $ informuje o tym, że dopasowany napis musi znajdować się na końcu tekstu.

Wyrażenie regularne “^\d+$” dopasowuje zatem wyłącznie teksty składające się wyłącznie z cyfr.

Kotwica \b oznacza granicę pomiędzy wyrazami. Do wyrażenia “\bkot\b” nie zostanie dopasowany żaden fragment tekstu “Ala ma kota”, gdyż w sformułowaniu tym po wyrazie kot nie występuje granica wyrazów.

Flagi

Przy obsłudze wyrażeń regularnych przydają się także flagi, które rozszerzają możliwości przeszukiwania tekstów. Na przykład flaga i oznacza, że do wyrażenia regularnego mają pasować również napisy różniące się wielkością litery od wzorca, a flaga g – że mechanizm stosujący wyrażenia regularne ma odszukać wszystkie napisy pasujące do wzorca, a nie tylko pierwszy z nich.

Flaga nie jest częścią wyrażenia regularnego. Informację o tym, że dana flaga ma być stosowana, użytkownik mechanizmu przeszukującego teksty podaje oddzielnie (w różny sposób w zależności od rozwiązania).

Przykłady popularnych wyrażeń regularnych

([12]\d{3}-(0[1-9]|1[0-2])-(0[1-9]|[12]\d|3[01]))

Powyższe wyrażenie regularne dopasowuje najbardziej popularny aktualnie format i zakres dat. Zgodnie z nim data powinna rozpoczynać się od cyfry 1 lub 2 ([12]), po której następują trzy dowolne cyfry (\d{3}). Potem występuje łącznik (-), a po nim określenie miesiąca: jest to albo napis dwucyfrowy zaczynający się od zera (oprócz 00), albo jeden z napisów: 10, 11, 12 (0[1-9]|1[0-2]). Po kolejnym łączniku (-) następuje deklaracja dnia miesiąca – zbudowana jest ona z dwóch cyfr, z których albo pierwsza jest zerem, a druga należy do zakresu od 1 do 9 (0[1-9]), albo pierwsza ma wartość 1 lub 2, a druga dowolną ([12]\d), albo też pierwsza jest trójką, a druga – zerem lub jedynką (3[01]).

\b[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,}\b

Powyższe wyrażenie – przy zastosowaniu flagi i – dopasuje większość adresów mailowych. Adres mailowy zaczyna się zgodnie z nim od co najmniej jednego wystąpienia litery, cyfry lub dowolnego innego dozwolonego znaku (b[A-Z0-9._%+-]+), po czym wystąpić musi znak @, a po nim co najmniej jeden napis zakończony kropką ([A-Z0-9.-]+\.), po którym stać będzie oznaczenie domeny składające się z co najmniej dwóch liter ([A-Z]{2,}).

Jak sprawdzić wyrażenie regularne?

Istnieje cały szereg narzędzi on-line umożliwiających sprawdzenie, czy skonstruowane przez nas wyrażenie regularne “działa” dokładnie tak, jak powinno. Jedno z nich udostępnione zostało na stronie: regex101.com.

W okienku edycyjnym umieszczamy nasze wyrażenie regularne, a w polu tekstowym – tekst, który ma zostać przeszukany. Narzędzie podświetla w powyższym tekście pierwsze wystąpienie napisu zgodnego z testowanym przez nas wyrażeniem regularnym:

Zauważmy, że w powyższym przykładzie mechanizm wyszukiwania stosuje flagę i (włączoną uprzednio poprzez kliknięcie w prawym rogu okienka edycyjnego). Wyłączenie tej flagi spowoduje, że adres mailowy nie zostanie znaleziony:

Podsumowanie

Jednym z głównych powodów, dla których teksty coraz częściej przechowywane są w formie cyfrowej, jest łatwość wyszukiwania w nich informacji. O ile odszukanie w stogu siana pojedynczej igły (czyli konkretnego napisu) jest zadaniem stosunkowo łatwym, a co za tym idzie, funkcję tego typu udostępnia praktycznie każdy edytor tekstów, o tyle odnalezienie w nim wielu igieł (czyli wszystkich napisów określonego typu) nie jest już takie banalne.

Wyrażenia regularne są obecnie najbardziej popularnym mechanizmem wyszukiwania w tekstach napisów określonego typu. Warto zatem na pewno ten mechanizm poznać – choćby w podstawowym zakresie, przedstawionym w niniejszym wpisie.

4 elementy rozmowy z komputerem

Aby rozmowa z komputerem przypominała rozmowę z człowiekiem, komputer musi opanować cztery elementy dialogu:

Rozpoznawanie mowy

Rozpoznawanie mowy to proces, w ramach którego komputer słucha wypowiedzi człowieka, generując jej pisemny odpowiednik. Proces ten można zaobserwować na przykład podczas niektórych programów informacyjnych, kiedy to z nieznacznym opóźnieniem na ekranie telewizora pojawia się tekst wypowiedziany przez dziennikarza.

W ostatnich latach systemy tego typu poczyniły ogromne postępy w skutecznym rozpoznawaniu sygnału mowy praktycznie dowolnego języka naturalnego na świecie. Jeszcze nie tak dawno poprawne rozpoznanie przez system nawigacji samochodowej wypowiedzianego przez człowieka adresu graniczyło z cudem; dziś natomiast dziwimy się, gdy w rozpoznaniu tego typu komunikatu pojawi się najmniejszy błąd.

Synteza mowy

Nie dawniej niż kilka lat temu głos wygenerowany komputerowo uderzał swym jednostajnym rytmem i nienaturalną intonacją. Dziś odróżnienie głosu syntetycznego od ludzkiego to już zadanie dla osób o wybitnie wyczulonym słuchu.

Generowanie wypowiedzi

Generowanie wypowiedzi to proces tworzenia wypowiedzi języka naturalnego na podstawie wiedzy zakodowanej w komputerze. Na przykład na podstawie informacji typu: “<stacja odjazdu: Warszawa; typ pociągu: pospieszny, stacja docelowa: Poznań, opóźnienie: 30>” system informatyczny generuje wypowiedź: “Pociąg pośpieszny z Warszawy do Poznania jest opóźniony o trzydzieści minut”.

Generowanie wypowiedzi może odbywać się na podstawie opracowanego przez człowieka zestawu reguł lub wzorców i jest to zadanie znacznie łatwiejsze niż rozumienie języka, o którym mowa w kolejnym punkcie.

Rozumienie języka

Powiemy, że system informatyczny rozumie język naturalny, jeśli w reakcji na wypowiedź człowieka podejmuje on działanie zgodne z oczekiwaniami mówcy. Na przykład w odpowiedzi na zadane pytanie system udziela relewantnej informacji, w reakcji na polecenie realizuje czynności w nim zawarte, a w odpowiedzi na wyrażoną opinię kontynuuje dialog w sposób charakterystyczny dla człowieka.

Rozumienie wypowiedzi języka naturalnego jest najtrudniejszym i wciąż dalekim od rozwiązania elementem prowadzenia dialogu przez komputer. Wynika to z faktu, że nieskończony zbiór możliwych wypowiedzi ludzkich bardzo trudno jest ogarnąć skończonym zestawem reguł czy zasad.

Jeżeli jednak umówimy się, że system informatyczny ma działać wyłącznie w pewnej uproszczonej rzeczywistości, w której wypowiedzi użytkownika ograniczone są pod względem słownictwa i struktury, wówczas możliwe – a wręcz niespecjalnie skomplikowane – staje się napisanie programu komputerowego, który rozumie język naturalny.

W tym wpisie na blogu opiszę krok po kroku, jak taki system można stworzyć. Niezbędny na te potrzeby przykład zostanie opracowany z użyciem języka programowania Python, jednakże wydaje się, że nawet bez znajomości tego języka – czy wręcz bez znajomości jakiegokolwiek języka programowania – czytelnik nauczy się skutecznie budować podobnego typu systemy.

Wirtualny sprzedawca

Stworzony w ramach naszego przykładu system będzie wirtualnym sprzedawcą, realizującym misję zawierającą się w słowach: “Kupię, by potem sprzedać”. Będzie to system nieskomplikowany, reagujący na niedługie i proste składniowo zdania. Z myślą o poszerzeniu potencjalnego rynku zbytu nasz sprzedawca komunikował się będzie w języku angielskim, a jego rozmówca będzie wydawał mu polecenia za pomocą komend typu:

Buy 5 large blue metal boxes.
Sell 3 tiny red plastic rings.

Nasz sprzedawca będzie robił wszystko, aby za każdym razem dobić targu. Każde polecenie zakupu zaakceptuje, a następnie zarejestruje w swoim spisie towarów informacje na jego temat. Polecenie sprzedaży będzie realizować tylko wówczas, gdy uprzednio zakupił odpowiednią ilość towaru.

Uznamy, że nasz system rozumie, co się do niego mówi, jeśli jego spis towarów będzie na bieżąco zgodny z poczynionymi zakupami oraz zrealizowanymi transakcjami sprzedaży.

Jak pracuje wirtualny sprzedawca?

Nasz program ma działać w sposób następujący:

Użytkownik wydaje komendę językiem naturalnym, np.:

Buy 5 large blue metal boxes.

  1. System identyfikuje towar, o którym mowa, czyli w tym przypadku:
    large blue metal boxes
  2. Każdy towar, którym handluje sprzedawca, ma swój indeks w spisie towarów. System wyznacza indeks wskazanego towaru w określony sposób (jest to element rozumienia wypowiedzi), przy czym w naszym systemie będzie nim czterocyfrowa liczba – np. 1215.
  3. System analizuje pierwsze słowo komendy, by sprawdzić, czy chodzi o kupno, czy też o sprzedaż (oczywiście z jego punktu widzenia).
    3.1. Jeśli chodzi o kupno, akceptuje wydane polecenie bezwarunkowo, a w swoim spisie towarów zwiększa posiadaną liczbę sztuk towaru o danym indeksie.
    3.2. Jeśli chodzi o sprzedaż, najpierw sprawdza w spisie towarów, czy posiada na stanie wymaganą liczbę sztuk towaru o danym indeksie. Jeśli nie posiada, odmawia wykonania polecenia; jeśli zaś posiada, dokonuje transakcji sprzedaży, po czym zapisuje ubytek w spisie towarów.

Piszemy program

Słownik

Typy tokenów czyli znaczenia wyrazów

Musimy zawrzeć w słowniku wszystkie wyrazy, które system ma zrozumieć. Będziemy je nazywać tokenami. Przedtem jednak musimy określić dopuszczalne znaczenia wyrazów, zwane typami tokenów. Odpowiedni kod źródłowy w języku Python ma następującą postać:

    tokens = (
        'OPERATE',
        'NUMBER',
        'SIZE',
        'COLOR',
        'MATERIAL'
        'KIND',
    )

Zdefiniowaliśmy sześć typów tokenów, odpowiadających różnym znaczeniom tokenów. Za chwilę określimy na przykład, że w słowniku dopuszczalny jest token “Buy” należący do typu OPERATE.

Zadanie dla czytelnika

Zgadnij, do których z powyższych typów przydzielone zostaną kolejne tokeny zdania:

“Buy 5 large blue metal boxes”.

Odpowiedź już za chwilę...

Zawartość słownika

W kolejnym kroku dla każdego typu określamy, jakie tokeny do niego należą i co system ma zrobić, gdy określony token pojawi się w komendzie użytkownika:

Operacje
    def t_OPERATE(t):
    r'Buy | Sell'
    return t

Powyższy kod przypisuje do typu OPERATE dwa wyrazy: Buy lub Sell (drugi wiersz) oraz nakazuje systemowi zapamiętać podaną operację, gdy taki token pojawi się w komendzie użytkownika (trzeci wiersz).

Liczby
    def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)
    return t

Powyższy kod przypisuje do typu NUMBER dowolny napis składający się z samych cyfr (drugi wiersz), przekształca taki napis składający się z cyfr na odpowiadającą mu wartość liczbową (trzeci wiersz) i nakazuje systemowi zapamiętać tę wartość, gdy taki token pojawi się w komendzie użytkownika (czwarty wiersz).

Atrybuty
    def t_MATERIAL(t):
    r'metal | plastic'
    if t.value =='metal':
    t.value = 1
    elif t.value == 'plastic':
    t.value = 2
    return t

Powyższy kod przypisuje do typu MATERIAL napisy metal lub plastic, a następnie (i tu nowość!) nakazuje systemowi zapamiętać albo 1 (gdy materiałem jest metal), albo 2 (gdy materiałem jest plastic).

Analogicznie do typu MATERIAL utworzyć możemy pozostałe typy tokenów:

    def t_COLOR(t):
    r'(black | white | red | green | blue)'
    if t.value =='black':
    t.value = 1
    elif t.value == 'white':
    t.value = 2
    elif t.value == 'red':
    t.value = 3
    elif t.value == 'green':
    t.value = 4
    elif t.value == 'blue':
    t.value = 5
    return t

    def t_SIZE(t):
    r'tiny | small | big | large'
    if t.value =='tiny':
    t.value = 1
    elif t.value =='small':
    t.value = 2
    elif t.value =='big':
    t.value = 3
    elif t.value =='large':
    t.value = 4
    return t
Rodzaje towarów
    def t_KIND(t):
    r'box(es)? | ring(s)?'
    if t.value[0] =='b':
    t.value = 1
    else:
    t.value = 2
    return t

W definicji typu KIND zadbaliśmy, aby w słowniku zawarte były wyrazy box, boxes, ring oraz rings. Gdy pojawia się token związany z pudełkami, zapamiętywana jest wartość 1, a gdy token związany z krążkami – wartość 2.

Indeks towarów

W jaki sposób komputerowy sprzedawca wyznacza indeks towaru, o którym mowa w komendzie? Pomaga mu w tym podręczna tabela, która zawiera wartości określone dla poszczególnych tokenów.

WartośćKINDSIZEMATERIALCOLOR
1box(es)tinymetalblack
2ring(s)smallplasticwhite
3bigred
4largegreen
5blue

Ilekroć system musi wyznaczyć indeks kupowanego lub sprzedawanego artykułu, odwołuje się on do powyższej tabeli – przy czym istotna jest kolejność jej kolumn.

Aby na przykład wyznaczyć indeks towaru:

large blue metal boxes

system musi najpierw ułożyć podane cechy towaru w takiej kolejności, na jaką wskazują kolumny przedstawionej powyżej tabeli, a mianowicie: KIND, SIZE, MATERIAL, COLOR, czyli:

boxes large metal blue

a następnie przypisać po kolei poszczególnym tokenom cyfry w zgodzie z treścią powyższej tabeli:

1415

(boxes → 1; large → 4 metal → 1 blue → 5)

Indeksem towaru large blue metal boxes jest zatem 1415, przy czym zauważmy, że nawet gdyby kolejność atrybutów towaru podana została w innej kolejności, indeks artykułu pozostałby niezmieniony.

Reguły gramatyki

Wirtualny sprzedawca zrozumie tylko takie komendy, które będą zgodne z regułami gramatyki podanymi przez autora programu. Każda reguła mówi o tym, w jaki sposób mniejsze części zdania składać można w większe całości. Na przykład reguła mówiąca o tym, że w skład komendy wchodzić muszą po kolei: token oznaczający operację, token oznaczający liczbę oraz składowa określająca artykuł mogłaby mieć następującą postać:

command: OPERATE NUMBER article

W odpowiedniej regule gramatyki można również zawrzeć instrukcje, które ma wykonać program, gdy rozpozna, że analizowany tekst jest zgodny z tą właśnie regułą.

Reguły dotyczące atrybutów

Zacznijmy od reguł najprostszych, dotyczących atrybutów towarów:

    def p_attribute_color(p):
    'attribute : COLOR'
    p[0] = p[1]

Reguła o nazwie p_attribute_color (nazwa reguły musi zaczynać się od zapisu “p_”, po którym autor programu może przyjąć dowolny zapis) mówi, że część zdania o nazwie attribute może się składać wyłącznie z tokenu typu COLOR (drugi wiersz). Trzeci wiersz mówi, że w takiej sytuacji wartość składowej attribute (oznaczanej jako p[0]) ma być tożsama z wartością tokenu COLOR (p[1] oznacza pierwszą – w tym wypadku jedyną – składową).

Tak więc atrybut black, jeśli pojawi się w komendzie, będzie miał wartość 1, atrybut white – wartość 2, itd.

    def p_attribute_material(p):
    'attribute : MATERIAL'
    p[0] = 10 * p[1]

Reguła o nazwie p_attribute_material mówi, że część zdania o nazwie attribute może się alternatywnie składać wyłącznie z tokenu typu MATERIAL (drugi wiersz). Trzeci wiersz mówi, że w takiej sytuacji wartość składowej attribute ma być tożsama z wartością tokenu MATERIAL pomnożonego przez 10.

Tak więc atrybut metal ma wartość 10, atrybut plastic ma wartość 20.

Analogicznie:

    def p_attribute_size(p):
    'attribute : SIZE'
    p[0] = 100 * p[1]

Reguły dotyczące artykułów

Opis artykułu może składać się z samego rodzaju artykułu:

    def p_article_kind(p):
    'article : KIND'
    p[0] = 1000 * p[1]

“Wartość” pudełka wynosi 1000, a “wartość” krążka – 2000.

Opis artykułu może być poprzedzony dowolnego typu atrybutem:M.

    def p_article_attribute(p):
    'article : attribute article'
    p[0] = p[1] + p[2]

Dodanie atrybutu do opisu artykułu zwiększa jego wartość. Na przykład zapis “boxes” ma wartość 1000, zapis “metal boxes” – 1010, “blue metal boxes” – 1015, a “large blue metal boxes” – 1415.

Reguła dotycząca komendy

Najważniejsza reguła dotyczy całej komendy:

    # Main parser rule (command)
    def p_command(p):
    'command : OPERATE NUMBER article'
    index = p[3]

    #Buy article
    if p[1] == 'Buy':
    tab[index] += p[2]
    print('OK. I am buying ' + str(p[2])+ ' new articles indexed as ' + str(index) +'.')
    print('No of articles in shop: '+ str(tab[index]))

    #Sell article
    elif p[1] == 'Sell':
    if p[2] > tab[index]:
    print('I do not have as many articles as you want.')
    else:
    tab[index] -= p[2]
    print('OK. I am selling ' + str(p[2])+ ' articles indexed as ' + str(index) + '.')
    print('No of articles in shop: ' +  str(tab[index]))

Analizowana komenda musi składać się kolejno z: operacji (token OPERATE), liczby artykułów (token NUMBER) oraz opisu artykułu (article) – pierwszy wiersz. Jako indeks towaru, o którym mowa w komendzie, wyznaczana jest wartość artykułu (p[3]). W przypadku kupna zwiększa się odpowiednio informację w spisie towarów o wartość tokenu NUMBER oraz podaje odpowiedni komunikat. W przypadku sprzedaży dodatkowo sprawdza się, czy w spisie dostępna jest odpowiednia liczba artykułów.

Przykładowa sesja rozmowy z wirtualnym sprzedawcą

What can I do for you?
Buy 10 large blue metal boxes
OK. I am buying 10 new articles indexed as 1415.
No of articles in shop: 10

What can I do for you?
Buy 5 tiny white plastic rings
OK. I am buying 5 new articles indexed as 2122.
No of articles in shop: 5

What can I do for you?
Sell 5 large blue metal boxes
OK. I am selling 5 articles indexed as 1415.
No of articles in shop: 5

What can I do for you?
Sell 3 tiny white plastic rings
OK. I am selling 3 articles indexed as 2122.
No of articles in shop: 2

What can I do for you?
Sell 3 tiny white plastic rings
I do not have as many articles as you want.

What can I do for you?
Bye
>>>

Post Scriptum

Poniżej znajduje się pełny kod programu – z niezbędnymi “dekoracjami”.

# Import lexer and parser from ply module
    import ply.lex as lex
    import ply.yacc as yacc

    # List of token types.
    tokens = (
    'NUMBER',
    'OPERATE',
    'SIZE',
    'KIND',
    'COLOR',
    'MATERIAL'
    )

    # Token types may be defined as regular expressions, e.g. r'Buy | Sell'
    def t_OPERATE(t):
    r'Buy | Sell'
    return t

    def t_MATERIAL(t):
    r'metal | plastic'
    if t.value =='metal':
    t.value = 1
    elif t.value == 'plastic':
    t.value = 2
    return t

    def t_COLOR(t):
    r'(black | white | red | green | blue)'
    if t.value =='black':
    t.value = 1
    elif t.value == 'white':
    t.value = 2
    elif t.value == 'red':
    t.value = 3
    elif t.value == 'green':
    t.value = 4
    elif t.value == 'blue':
    t.value = 5
    return t

    def t_SIZE(t):
    r'tiny | small | big | large'
    if t.value =='tiny':
    t.value = 1
    elif t.value =='small':
    t.value = 2
    elif t.value =='big':
    t.value = 3
    elif t.value =='large':
    t.value = 4
    return t

    def t_KIND(t):
    r'box(es)? | ring(s)?'
    if t.value[0] =='b':
    t.value = 1
    else:
    t.value = 2
    return t

    def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)
    return t

    # Lexer error handling rule (Handle words out of vocabulary)
    def t_error(t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(1)

    # Ignore white spaces
    t_ignore  = ' \t'

    # Main parser rule (command)
    def p_command(p):
    'command : OPERATE NUMBER article'
    index = p[3]
    #Buy article
    if p[1] == 'Buy':
    tab[index] += p[2]
    print('OK. I am buying ' + str(p[2])+ ' new articles indexed as ' + str(index) +'.')
    print('No of articles in shop: '+ str(tab[index]))
    #Sell article
    elif p[1] == 'Sell':
    if p[2] > tab[index]:
    print('I do not have as many articles as you want.')
    else:
    tab[index] -= p[2]
    print('OK. I am selling ' + str(p[2])+ ' articles indexed as ' + str(index) + '.')
    print('No of articles in shop: ' +  str(tab[index]))

    # Parser rule (attribute)
    def p_attribute_color(p):
    'attribute : COLOR'
    p[0] = p[1]

    # Parser rule (attribute)
    def p_attribute_material(p):
    'attribute : MATERIAL'
    p[0] = 10 * p[1]

    # Parser rule (attribute)
    def p_attribute_size(p):
    'attribute : SIZE'
    p[0] = 100 * p[1]

    # Parser rule (article - stop)
    def p_article_kind(p):
    'article : KIND'
    p[0] = 1000 * p[1]

    # Parser rule (article - recursion)
    def p_article_attribute(p):
    'article : attribute article'
    p[0] = p[1] + p[2]

    # Syntax error handling rule
    def p_error(p):
    print("Syntax error in input!")

    #######################################
    #Main program

    #Initialize table of articles (zero articles at the beginning)
    tab = []
    for index in range(3000):
    tab.append(0)

    #Build the lexer
    lexer = lex.lex()

    #Tokenize (short version)
    # for tok in lexer:
    #    print(tok)

    #Build the parser
    parser = yacc.yacc()

    #Main loop
    while True:
    s = input('What can I do for you? \n')
    if s == 'Bye':
    break
    parser.parse(s)

Jak najłatwiej przetwarzać teksty?

Przyjęło się uważać, że przetwarzanie dokumentów tekstowych wymaga znajomości języka programowania wysokiego poziomu. Kilkanaście lat temu “wypadało” dobrze znać język Perl, natomiast dziś specjalista w tej dziedzinie “absolutnie musi” mieć opanowany język Python. Czy naprawdę jest to niezbędne?

W niniejszym wpisie pokażę, że nawet całkiem zaawansowane zadania związane z przetwarzaniem tekstu można łatwo i szybko wykonać bez znajomości ani jednego polecenia jakiegokolwiek języka programowania.

Ile wyrazów ma mój tekst?

Zacznijmy od zadania najprostszego: sprawdźmy, ile wyrazów ma pewien dokument tekstowy. Można to zrobić za pomocą następującego ciągu poleceń:

Jeśli wynik swojego zadania chcemy zapamiętać (zapisać w jakimś pliku), ciąg poleceń może mieć poniższą postać:

Platforma Bash Box

Polecenia takiego typu są dostępne w systemie operacyjnym Linux. Aby uzyskać pożądany wynik, należy wpisać odpowiednie nazwy poleceń, których trzeba się uprzednio nauczyć. Polecam jednak coś znacznie bardziej atrakcyjnego: program graficzny, w którym zamiast wpisywania “trudnych do wyuczenia się na pamięć” poleceń można po prostu przesuwać puzzle.

Wejdźmy na stronę: https://s416072.students.wmi.amu.edu.pl/, gdzie naszym oczom ukaże się taki oto ekran:

Spośród ponad 20 dostępnych puzzli przeciągamy na pasek znajdujący się pod nimi tylko te, które chcemy wykorzystać – na przykład w celu zliczenia wyrazów w danym dokumencie:

Zauważmy, że pierwszy puzzel (Pobierz dane z pliku) ma wypustkę tylko z prawej strony, co oznacza, że oczekuje on na dołączenie innego elementu tylko z tejże strony. Kształt drugiego puzzla sugeruje z kolei gotowość na dołączenie puzzli z obu stron, podczas gdy trzeci element (Zapisz do pliku) wyłącznie domyka całą układankę.

W jakim dokumencie chcemy policzyć wyrazy? Bash Box daje nam tutaj do wyboru cztery możliwości:

Jeśli wybierzemy plik zawierający informacje o młodych przestępcach, wyświetli nam się na ekranie zawartość odpowiedniego dokumentu:

Pierwszy z widocznych powyżej wierszy informuje o tym, że w roku 2010 odnotowano w Polsce 741 przestępczyń płci żeńskiej w wieku 17 lat. Kolejne wersy zawierają analogiczne informacje – dla odpowiedniego wieku oraz odpowiedniej płci.

Aby zliczyć liczbę wyrazów w tym dokumencie, dokonujemy “tłumaczenia” ciągu poleceń zapisanego wcześniej za pomocą puzzli na odpowiednie polecenie systemu Linux. Odbywa się to z użyciem poniższego przycisku:

W systemie Linux dostępne jest specjalne środowisko (zwane potocznie “czarnym okienkiem”), które służy do wydawania poleceń – jest to powłoka Bash. Przetłumaczony przez nas ciąg poleceń ma w powłoce Bash następującą postać:

Zapis wygląda na odrobinę skomplikowany, spróbujmy go jednak przeanalizować.

W oknie obok możemy zobaczyć wynik działania całego potoku, czyli ciągu poleceń:

Okazuje się więc, że dokument o młodych przestępcach zawiera 819 wyrazów.

Zagadki

W systemie Bash Box można pobawić się też w przetwarzanie tekstu, rozwiązując zagadki w stylu historii westernowych. Uruchamia je poniższy przycisk, umiejscowiony w lewym górnym rogu ekranu:

Rozwiążmy zatem pierwszą z zagadek:

Format dokumentu ze wspomnianej bazy osób wyświetlony jest obok zagadki:

Aby uzyskać wymaganą odpowiedź, należy wykonać następujące kroki:

Przeciągamy zatem na ekranie odpowiednie puzzle:

Następnie sprawdzamy poprawność uzyskanej odpowiedzi:

Przycisk Sprawdź zabarwia się na pomarańczowo, co oznacza, że to nie była prawidłowa odpowiedź!

Przeciągamy więc trzeci puzzel na jego pierwotne miejsce, zastępując go innym:

Teraz przycisk Sprawdź zabarwia się już na zielono, co oznacza, że możemy spokojnie przejść do kolejnej z ośmiu zagadek.

Przykład zastosowania poleceń powłoki Bash

Jeśliby zapytać studenta informatyki, w jaki sposób uzyskać listę częstości występowania poszczególnych wyrazów, użytych na przykład we wszystkich dziełach Szekspira razem wziętych, najczęściej usłyszymy odpowiedź, iż najprościej będzie napisać odpowiedni kod w języku programowania Python. Można to jednak uczynić znacznie łatwiej – przy użyciu pojedynczego polecenia w powłoce Bash:

cat sh.txt | tr -sc ’A-Za-z’ ’\n’ | sort | uniq -c > sh_frequency_list

Załóżmy, że plik tekstowy sh.txt zawiera wszystkie dzieła Szekspira. Wtedy:

Podsumowanie

Przetwarzanie dokumentów tekstowych w systemie Linux jest bardzo efektywne. Za pomocą jednego polecenia można tutaj uzyskać takie same efekty jak w wyniku działania złożonych programów. Trudnością, którą trzeba pokonać, jest wyłącznie zapoznanie się z odpowiednimi poleceniami oraz nabycie umiejętności układania ich w potok.

Na pewno jednak warto, a platforma Bash Box może w tym wydatnie pomóc!

Klasyfikacja a regresja

W jednym z wcześniejszych wpisów na blogu omówiłem zadanie klasyfikacji, które polega na automatycznym określaniu, do jakiej klasy należy badany obiekt. System klasyfikacji przypisuje badanemu obiektowi etykietę klasy, przy czym liczba możliwych etykiet jest z góry określona.

W zadaniu regresji system uczenia maszynowego przydziela natomiast badanemu obiektowi pewną wartość liczbową z nieskończonego spektrum możliwości. Weźmy jako przykład komplet recenzji pewnej restauracji w serwisie TripAdvisor. Oto wybrana recenzja ze wspomnianego zbioru:

Recenzja w serwisie TripAdvisor

Dla takiego zestawu danych zdefiniować można co najmniej kilka różnych zadań klasyfikacji – na przykład:

  1. przypisz recenzję do jednej z trzech klas według kryterium nastawienia autora: pozytywne, negatywne lub neutralne;
  2. określ lokalizację opisywanej restauracji, mając do wyboru szesnaście polskich województw;
  3. określ typ kuchni serwowanej w opisywanej restauracji (np. polska, europejska, azjatycka itp.).

Przykładowe zadanie regresji dla takiego zestawu recenzji może mieć natomiast następującą formę:

Na podstawie recenzji określ jakość opisywanej w niej usługi w postaci liczby rzeczywistej z przedziału od 0 do 5.

Wartością obliczoną przez system regresji na podstawie recenzji może być na przykład liczba 3,45, przy czym oczekujemy, że wartość zwrócona przez system będzie adekwatna do opinii wyrażonej w recenzji: jeśli opinia ta jest bardzo pozytywna, będzie ona zbliżona do liczby 5, a jeśli zdecydowanie negatywna – będzie ona bliska zeru.

Do czego może przydać się regresja?

Regresja dostarcza bardziej precyzyjnych informacji niż klasyfikacja. Dzięki niej możemy na przykład śledzić na bieżąco postępy, jakie czyni obserwowana restauracja w zakresie jakości oferowanych usług, poprzez porównywanie wartości opinii na jej temat na przestrzeni czasu. System regresji może też z wykorzystaniem tego typu analiz przewidywać przyszłe wartości indeksów giełdowych – a tutaj już dokładność, nawet do wielu miejsc po przecinku, staje się kluczowa.

Cechy obiektu

Metoda regresji umożliwia obliczenie wartości przewidywanej na podstawie cech obiektu. W uczeniu maszynowym cechą obiektu nazywamy taką jego własność, której wartość można określić liczbowo. Cechą recenzji może być na przykład liczba zawartych w niej wyrazów o nacechowaniu pozytywnym lub liczba zawartych w niej wyrazów o wydźwięku negatywnym. Opracowując system komputerowy wykorzystujący metodę regresji, inżynier systemu sam określa zestaw cech, które będą brane pod uwagę.

Regresja liniowa

Metoda regresji liniowej zakłada, że przewidywaną wartość można wyliczyć z zastosowaniem funkcji liniowej wartości cech. Możemy na przykład przyjąć założenie, że wartość danej opinii jest wprost proporcjonalna do liczby zawartych w niej wyrazów o nacechowaniu pozytywnym, co wyraża się wzorem:

WARTOŚĆ = Ⲁ x LICZBA WYRAZÓW POZYTYWNYCH

gdzie Ⲁ jest liczbą dodatnią.

Możemy dodatkowo przyjąć, że przewidywana wartość jest odwrotnie proporcjonalna do liczby wyrazów o wydźwięku negatywnym:

WARTOŚĆ = Ⲁ x LICZBA WYRAZÓW POZYTYWNYCH
+ ? x LICZBA WYRAZÓW NEGATYWNYCH

gdzie ? jest liczbą ujemną.

Jeśli zdefiniowana przez nas w ten sposób funkcja zwraca przykładowo wartości w zakresie od -1 do 4, a pożądane jest, aby wyniki mieściły się w zakresie od 0 do 5, możemy “przesunąć” zakres zwracanych wartości poprzez dodanie “parametru przesunięcia”:

WARTOŚĆ = Ⲁ x LICZBA WYRAZÓW POZYTYWNYCH
+ ? x LICZBA WYRAZÓW NEGATYWNYCH
+ ?

Zadanie regresji liniowej polega w tym wypadku na wyznaczeniu takich wartości współczynników Ⲁ, ? oraz ?, aby wartość wyliczana powyższym wzorem była zgodna z oczekiwaniami.

Kiedy mówimy, że wyniki regresji są zgodne z oczekiwaniami?

Jeśli regresję stosujemy do oceny obiektów (np.: Jakie jest nastawienie autora recenzji do recenzowanej usługi w skali od 0 do 5?), metoda działa zgodnie z oczekiwaniami, gdy zwracane przez nią wartości w dużym stopniu pokrywają się z intuicją ludzką.

Jeśli metodę regresji stosujemy do prognozowania (np.: Jakie będą w następnym miesiącu wartości indeksów giełdowych? Jaka będzie wartość sprzedaży podręczników we wrześniu?), jej wyniki są zgodne z oczekiwaniami, jeżeli prognozy różnią się od rzeczywistości o niewielką wartość (co można sprawdzić post factum).

Jak wyznacza się współczynniki regresji?

Współczynniki regresji obliczane są na podstawie danych uczących, czyli zestawu obiektów, dla których znane są zarówno wartości ich cech, jak i wartości przewidywane. Na przykład daną uczącą może być recenzja restauracji zaprezentowana na początku tego wpisu. Zawiera ona 5 wyrazów pozytywnych (mega, przyjemnie, najlepsze, dziękujemy, miłą) oraz jedno słowo negatywne (nie), a ocena punktowa przydzielona przez autora opinii recenzowanemu lokalowi (będąca w tym wypadku wartością przewidywaną) to liczba 5 (przy recenzji widoczne jest pięć zielonych kropek). Gdybyśmy mieli wyznaczyć współczynniki regresji na bazie wyłącznie tego jednego przykładu, mogłyby mieć one następujące wartości:

Ⲁ = 1
? = -1
? = 1

W takim przypadku wartość przewidywana recenzji wyliczona z podanego wcześniej wzoru powyżej wyniosłaby:

WARTOŚĆ = 1 x 5 + (-1) x 1 + 1 = 5

Wartość wyliczona ze wzoru na regresję liniową byłaby zatem identyczna z oceną punktową recenzji ze zbioru uczącego. Brawo!

Załóżmy jednak, że inna opinia ze zbioru uczącego – również opatrzona pięcioma punktami – ma następującą treść:

Super restauracja! Nie mogę się doczekać, kiedy znowu do niej pójdę!

Zastosowanie tych samych wartości współczynników Ⲁ, ? oraz ?, gdy liczba wyrazów pozytywnych (Super) i negatywnych (nie) wynosi po 1, obliczona według podanego wcześniej wzoru wynosi:

WARTOŚĆ = 1 x 1 + (-1) x 1 + 1 = 1

W tym przypadku wartość wyliczona ze wzoru na regresję liniową różni się zatem od oceny samego użytkownika aż o 4 punkty! Wprowadzenie drugiej danej do zbioru uczącego pociąga więc za sobą konieczność zmiany współczynników – na przykład na poniższe:

Ⲁ = 0,5
? = -0,5
? = 4

Po powyższej modyfikacji współczynników wartość funkcji oceny dla omawianej wcześniej pierwszej danej uczącej wynosi 6 (czyli o 1 za dużo), podczas gdy dla analizowanej powyżej drugiej danej uczącej wynosi ona 4 (a zatem o jeden za mało). Dla obu danych łącznie różnica między wartością funkcji a wartością rzeczywistą wynosi jednak zaledwie 2 – podczas gdy przy poprzednim doborze wartości współczynników wynosiła ona 4.

Funkcja kosztu

Współczynniki regresji wyznacza się w taki sposób, aby suma różnic między wynikiem funkcji liniowej a wartością rzeczywistą łącznie dla wszystkich danych uczących była jak najmniejsza. Taką łączną sumę różnic między wynikami funkcji liniowej a wartościami rzeczywistymi określa się mianem funkcji kosztu.

Posługując się językiem matematycznym: celem metody regresji jest znalezienie takich wartości współczynników regresji, dla których funkcja kosztu osiąga swoje minimum.

Metoda gradientu prostego

Metoda gradientu prostego służy do znalezienia minimum funkcji, czyli wartości argumentu (argumentów), dla którego (których) funkcja przyjmuje najmniejszą wartość. Wyjaśnijmy jej istotę, posługując się przykładem, w którym funkcja ma tylko jeden argument.

Wartość minimalna i maksymalna

https://tutorial.math.lamar.edu/problems/calci/minmaxvalues.aspx

Jak widać na powyższym wykresie, analizowana funkcja przyjmuje najmniejszą wartość (równą -6) dla wartości argumentu x = 2. Wartość 2 stanowi zatem minimum tej funkcji. Na potrzeby zobrazowania metody gradientu posłużymy się Opowieścią o pustym baku.

Opowieść o pustym baku

Opowieść o pustym baku

Wyobraźmy sobie, że wybraliśmy się na samochodową wycieczkę w góry. W połowie zbocza pokonywanego wzniesienia auto nagle zatrzymało się – z najbardziej prozaicznego powodu, jaki mógłby przyjść nam do głowy: w jego baku zabrakło po prostu paliwa. Trzeba będzie zatem dotrzeć teraz piechotą na najbliższą stację benzynową.

Nie znamy co prawda jej lokalizacji, lecz jedno wiemy na pewno: stacja znajduje się w najniższym punkcie naszej drogi. W którą stronę zatem się udać? Rozglądamy się dokoła: w jedną stronę droga prowadzi do góry, w drugą zaś – w dół. Robimy więc krok w dół, po czym powtarzamy powyższą procedurę.

Opowieść o pustym baku

Czy w ten sposób na pewno dotrzemy do poszukiwanej stacji paliw? Jeśli przekrój drogi wygląda tak jak na lewym z powyższych rysunków, na pewno nam się to uda. Jeśli jednak przekrój ten ma kształt taki jak na rysunku po prawej stronie – już niekoniecznie.

Metoda gradientu prostego działa analogicznie do Opowieści o pustym baku:

  1. Zacznij w dowolnym miejscu (np. dla zerowej wartości argumentu), po czym powtarzaj kroki 2) i 3).
  2. Jeśli funkcja jest w danym miejscu malejąca (tzn. jej wartość maleje, gdy wartość argumentu rośnie), przemieść się po wykresie funkcji w prawo.
  3. W przeciwnym wypadku (tzn. jeśli wartość funkcji maleje, gdy wartość argumentu maleje), przemieść się po wykresie funkcji w lewo.

Poruszaj się w ten sposób do momentu, kiedy funkcja nie maleje w żadną ze stron. Jesteś na miejscu!

Funkcje wypukłe

Taki algorytm skutecznie znajduje minimum dla wszystkich funkcji, których wykres przypomina rysunek po lewej stronie – czyli takich, które mają one dokładnie jeden “dołek”. Funkcje takie nazywane są funkcjami wypukłymi. Algorytm ten może jednak nie zadziałać poprawnie w przypadku funkcji takich jak ta, której wykres przedstawiono na rysunku po stronie prawej.

Tak się na szczęście składa, że interesująca nas funkcja kosztu jest funkcją wypukłą. Metoda gradientu prostego działa zatem na potrzeby tej funkcji idealnie!

Regresja logistyczna

Wyniki zwracane przez regresję liniową nie zawsze niestety w pełni satysfakcjonują odbiorcę. Owszem, gdy oczekujemy od systemu prognozy temperatury, cieszy nas wynik w skali Celsjusza. Kiedy potrzebna jest nam prognoza giełdowej wyceny akcji, jesteśmy zadowoleni, gdy system zwraca nam wartość wyrażoną w złotówkach. Wartość oceny wyrażonej w recenzji podana jako 3,45 pozostaje jednak dla nas niejasna, o ile nie jest nam znana skala, jaką operujemy. Być może w takim przypadku lepiej byłoby uzyskać wynik w skali procentowej (np. 69%)? Gdybyśmy natomiast chcieli przewidzieć szanse Szymona Hołowni w wyborach na urząd prezydenta w roku 2025, to już na pewno oczekiwalibyśmy wyniku wyrażonego w procentach, a nie liczby z nieznanego nam bliżej zakresu.

Funkcja logistyczna

Regresja logistyczna umożliwia przeliczenie wyniku uzyskanego w efekcie zastosowania regresji liniowej w taki sposób, aby jego wartość zawierała się w przedziale od 0 do 1. W tym celu na wynik uzyskany z zastosowaniem regresji liniowej nakładana jest tzw. funkcja logistyczna, której wartości zawierają się w powyższym zakresie.

Przykładem funkcji logistycznej jest funkcja sigmoidalna:

Wartość minimalna i maksymalna

https://archive.lib.msu.edu

Jak widać na powyższym wykresie, jeśli wartość zwrócona przez funkcję liniową wynosi 0, funkcja sigmoidalna przekształca ją na wartość równą 0,5. Wartości ujemne odwzorowywane są przez funkcję sigmoidalną na liczby z przedziału od 0 do 0,5, natomiast dodatnie – na wartości zawarte w przedziale od 0,5 do 1. Wszystkie wartości funkcji sigmoidalnej zawierają się zatem w zakresie od 0 do 1. I o to chodzi!

Zakończenie

Regresja logistyczna jest jedną z podstawowych metod uczenia maszynowego. Stosowana jest ona między innymi w sieciach neuronowych, które dzięki nowym rozwiązaniom technologicznym (wyspecjalizowane karty graficzne, wydajne procesory tensorowe itp.) szturmem zdobywają kolejne bastiony ludzkiej inteligencji.

Ale o sieciach neuronowych będzie już mowa w innym wpisie na naszym blogu!

Czym jest model?

Model to reprezentacja jakiegoś bytu, która ułatwia operowanie nim. Model jest często miniaturą pewnego obiektu. W trakcie zabawy miniaturowym modelem samolotu dziecko może dołączyć skrzydła, doklejać albo też demontować różne elementy, np. może od modelu odłączyć silnik. W atlasie czy na globusie, które reprezentują Ziemię, możemy jednym pociągnięciem palca “pokonać” setki lub tysiące kilometrów. Jeśli z kolei chcemy obserwować ruch cząstek elementarnych, model atomu musi być znacznie większy od swego pierwowzoru. Model jako odwzorowanie jakiegoś bytu ułatwia nam poznanie i zrozumienie jego całości, od ogółu do szczegółów.

Model dla komputera

Model może zostać stworzony po to, aby umożliwić operowanie nim w aplikacji komputerowej. Cyfrowy model architektury budynku pozwala na łatwe dokonywanie zmian w projekcie – modyfikacji dokonuje człowiek w środowisku komputerowym. Dźwięk modelowany jest w komputerze za pomocą reprezentacji cyfrowej, którą program komputerowy może przekształcać (np. podwyższenia tonu wypowiedzi) – nawet bez ingerencji człowieka.

Komputerowy model języka

Komputerowy model języka jest taką reprezentacją języka, która umożliwia komputerowi dokonywanie w tym modelu pewnych operacji, takich jak na przykład analiza sensu wypowiedzi, wykonywanie instrukcji wypowiedzianych w danym języku czy poprawne tłumaczenie sformułowanego w nim tekstu na inny język. Gdy mówimy o komputerowym modelu języka (w skrócie: modelu języka), mamy zazwyczaj na myśli reprezentację samego tekstu – z pominięciem takich informacji dźwiękowych jak na przykład intonacja czy wysokość tonu.

Regułowy model języka

W wieku XX wierzono, że język, którym posługuje się człowiek (inaczej: język naturalny), można zapisać za pomocą reguł. Każdym językiem, jak bowiem sądzono, rządzi pewien skończony zbiór reguł, decydujący o tym, jak z wyrazów poprawnie składać zdania. Co więcej, dzięki tym regułom można dla danej wypowiedzi stwierdzić, z jakich składowych jest ona zbudowana, a następnie określić jej znaczenie.

W przypadku języka polskiego następujące trzy reguły umożliwiają przykładowo formułowanie zdań prostych:

  1. Zdanie proste = Część podmiotu + Część orzeczenia
  2. Część podmiotu = Przymiotnik (mianownik) + Rzeczownik (mianownik)
  3. Część orzeczenia = Czasownik + Rzeczownik (biernik)

Zgodnie z tymi regułami można na przykład utworzyć następujące zdanie proste:

Szary kotek pije wodę.

Pierwszą składową zdania jest “Część podmiotu” szary kotek, zbudowana z przymiotnika w mianowniku (szary) oraz rzeczownika w mianowniku (kotek). Drugą składową zdania stanowi natomiast “Część orzeczenia” pije wodę, zbudowana z czasownika (pije) oraz rzeczownika w bierniku (wodę).

Jak określić znaczenie wypowiedzi w regułowym modelu języka?

Znając podstawowe składowe zdania, można określić znaczenie wypowiedzi. Można na przykład przyjąć, że Część podmiotu oznacza wykonawcę czynności, czasownik reprezentuje czynność, a rzeczownik w bierniku – obiekt czynności. Znaczenie powyższej wypowiedzi można wtedy przedstawić następująco:

Wykonawca: szary kotek
Czynność: picie
Obiekt: woda

Czy model regułowy dobrze reprezentuje język?

Jak dotąd dla żadnego języka nie udało się niestety stworzyć zestawu reguł, który spełniałby następujące dwa postulaty:

Trudność spełnienia pierwszego postulatu wynika stąd, że ludzie są niewiarygodnie kreatywni w wymyślaniu konstrukcji językowych, o których nie śniło się filozofom (by o tym się przekonać, wystarczy posłuchać polityków). Trudność spełnienia drugiego postulatu można natomiast przedstawić na przykładzie następującego zdania: Jałowy autobus brzmi kotka. Choć zdanie to zgodne jest z trzema podstawowymi regułami polskiej gramatyki, nie ma ono żadnego sensu. Nikt takiego zdania zapewne nigdy nie wypowiedział w innym miejscu i pewnie nie wypowie powtórnie. Nie powinno zatem być ono uznane za zdanie poprawne w języku polskim.

Korpus tekstów

Korpus tekstów to zbiór dokumentów zgromadzonych w jednym miejscu w celu dokonywania w jego ramach zbiorczych analiz. Na przykład zbiór wszystkich dzieł Szekspira umieszczony w jednej lokalizacji (w bibliotece, jeśli są to teksty papierowe, lub na dysku, jeśli są to ich reprezentacje cyfrowe) stanowi korpus tekstów, w obrębie którego można dokonywać analizy stylu pisarskiego wymienionego powyżej wybitnego dramaturga.

Posiadaczem największego cyfrowego korpusu na świecie jest zapewne firma Google, która może dokonywać zbiorczych analiz w ramach wszystkich tekstów, do których ma dostęp jej wyszukiwarka.

Statystyczny model języka

Statystyczny model danego języka to jego reprezentacja wyznaczona na podstawie pewnego korpusu tekstów zapisanych w tym języku. Statystyczny model języka polskiego może na przykład zostać zbudowany z wykorzystaniem zestawu wszystkich tekstów zapisanych w języku polskim, do których dostęp ma wyszukiwarka Google.

Modele danego języka mogą znacznie się od siebie różnić, jeśli zbudujemy je na podstawie różnych korpusów. Możemy na przykład konstruować specjalistyczne modele języka, które wyznaczone zostają z wykorzystaniem korpusu tekstów wyłącznie z obszaru danej specjalności.

Model języka dla scrabblistów

Gracze w scrabble spierają się czasem, czy dany wyraz jest dopuszczalny. Wyrocznią w tej sprawie jest często portal internetowy sjp.pl (słownik języka polskiego). Język jednak cały czas się rozwija, a słownik nie zawsze za tymi zmianami nadąża.

A gdyby tak przyjąć nieco inne podejście, a mianowicie: Wyraz uważamy za poprawny, jeśli pojawia się on w konkretnym korpusie – na przykład w korpusie tekstów polskich wyszukiwarki Google? Nowopowstały, popularny wśród młodzieży wyraz plażing uznawany jest na przyklad przez sjp.pl za niedopuszczalny, podczas gdy wyszukiwarka Google wskazuje ponad 100 tys. przykładów użycia powyższego słowa.

Możemy zatem zdefiniować statystyczny model języka polskiego dla scrabblistów oparty na polskich tekstach indeksowanych przez Google w sposób następujący: Wyraz uważamy za dopuszczalny, jeśli według wyszukiwarki Google liczba jego wystąpień w tekstach polskich przekracza pułap 1 000. Odpowiedni próg definiujemy w sposób arbitralny, mając na celu eliminację wyrazów, które znalazły się w Internecie przypadkowo (chociażby w wyniku błędu typograficznego).

Jednowyrazowy model języka

Niektóre wyrazy występują w danym korpusie częściej, a inne – rzadziej. Można zatem zbudować statystyczny model języka, który da nam możliwość premiowania wyrazów o wyższej częstości występowania. Stopień poprawności danego wyrazu określamy w skali od 0 (całkowicie niepoprawny) do 1, przy czym wyliczamy jego wartość dzieląc liczbę jego wystąpień w korpusie przez liczbę wszystkich zawartych w tym korpusie wyrazów. Jeśli na przykład dany wyraz występuje pięć razy w korpusie składającym się ze stu wyrazów, jego stopień poprawności wynosi 0,05. Stopień poprawności wyrazów spoza korpusu wynosi oczywiście 0.

Powyższy model można zastosować też do całych zdań. Obliczamy po kolei stopień poprawności każdego z wyrazów w zdaniu, a następnie mnożymy przez siebie otrzymane wyniki. Jeśli którykolwiek z wyrazów nie występuje w korpusie, całe zdanie otrzymuje wartość 0; w przeciwnym wypadku zdanie otrzymuje pewną niezerową wartość mniejszą od 1. Tego typu model nazywamy jednowyrazowym modelem języka, gdyż na jego gruncie każdy wyraz rozpatrujemy niezależnie od wyrazów pozostałych.

Wielowyrazowy model języka

Możemy pokusić się teraz o definicję modelu języka: Model języka to funkcja, która każdemu wyrażeniu danego języka przydziela liczbę z zakresu od 0 do 1, informującą o jego poprawności (względem pewnego korpusu).

Możemy na przykład zastosować model jednowyrazowy oparty na korpusie Google w odniesieniu do przytoczonego już wcześniej zdania: Jałowy autobus brzmi kotka. Otrzymamy w takim przypadku pewną liczbę większą od zera, gdyż każdy z wyrazów powyższego zdania znajduje swe potwierdzenie w wykorzystywanym korpusie. Wynik taki nie jest jednak zgodny z naszą intuicją, gdyż powyższe połączenie poszczególnych wyrazów nie wydaje się mieć sensu.

Wielowyrazowy model języka bierze już natomiast pod uwagę wystąpienia wyrazów w pewnym kontekście. Na przykład model dwuwyrazowy sprawdza dla danej pary wyrazów, jak często drugi jej element występuje po elemencie pierwszym. Okazuje się przykładowo, że Google wskazuje 461 tys. wystąpień wyrazu “jałowy”, ale tylko raz po tym wyrazie występuje wyraz “autobus”. W związku z powyższym stopień poprawności pary “jałowy autobus” ma wartość bliską zeru.

Dwuwyrazowy model języka wyznacza stopnie poprawności wszystkich par wyrazowych danego zdania (np. jałowy autobus, autobus brzmi, brzmi kotka), po czym mnoży je przez siebie. Zdania pozbawione sensu otrzymują w wyniku powyższej operacji wartości bardzo bliskie zeru.

W podobny sposób można budować trzywyrazowe oraz czterowyrazowe modele języka. Modeli dłuższych niż cztery wyrazy raczej się nie konstruuje.

Wykorzystanie modelu języka na potrzeby pisania SMS-ów

Najbardziej znane nam zastosowanie modelu języka to podpowiadacz treści SMS-ów. Wystarczy wpisać pierwszy wyraz tekstu, aby system podpowiedział nam wyraz następny. Po kolejnym wpisanym słowie otrzymujemy nowy zestaw podpowiedzi.

Jak to działa? System podpowiada takie wyrazy, które w połączeniu z poprzedzającymi mają najwyższy stopień poprawności (czyli w korpusie występują najczęściej). Jeśli zatem wpiszemy wyraz dzień, system podpowiada, że według jemu znanego korpusu najbardziej poprawnymi kontynuacjami będą dzień dobry, dzień kobiet lub dzień jak co dzień.

Model języka w tłumaczeniu automatycznym i rozpoznawaniu mowy

W przypadku tłumaczenia automatycznego system w pierwszym kroku generuje kilka potencjalnych możliwości translacji zdania – różniących się np. doborem spośród wyrazów bliskoznacznych lub ich kolejnością. Model języka podpowiada, która z możliwości jest najbardziej poprawna – i właśnie ta wypowiedź jest podawana przez system jako zdanie przetłumaczone.

Podobną funkcję model języka spełnia w automatycznym rozpoznawaniu mowy. To właśnie model języka decyduje, że podyktowane zdanie “Tak mi dopomóż Bóg” system komputerowy rozpozna prawidłowo (czyli poda jego pisownię zgodną z intencją wypowiedzi), a nie na przykład jako “Tak mi dopomóż Bug” czy “Tak mi dopomóż buk”, choć wszystkie te trzy wersje mają identyczne brzmienie.

Podsumowanie – model statystyczny a model neuronowy

Statystyczny model języka to metoda reprezentacji języka naturalnego w oparciu o określony korpus tekstów. Taki model języka “premiuje” wypowiedzi składające się z wyrazów i fraz, które często w tym korpusie występują.

Pewnym ograniczeniem statystycznego modelu języka jest jednak fakt, że bierze on pod uwagę wyłącznie powiązania pomiędzy wyrazami z sobą sąsiadującymi. Przeanalizujmy bowiem następujące przykładowe zdanie:

Umowa powyższa zawiera błędy merytoryczne, więc nie mogę jej podpisać.

W zdaniu tym wyrazy “umowa” oraz “podpisać” są od siebie mocno oddalone (oddziela je od siebie aż osiem innych wyrazów). Statystyczny model języka nie jest w stanie wykryć, że zachodzi pomiędzy nimi jakiekolwiek powiązanie znaczeniowe, a przecież dotyczą one tej samej czynności: podpisania umowy.

Tego typu odległe powiązania są natomiast w stanie wykrywać tzw. neuronowe modele języka. Ich podstawowa rola jest co prawda podobna do funkcji modeli statystycznych – określają one stopień poprawności wypowiedzi względem pewnego korpusu tekstów. Różnica pomiędzy nimi związana jest jednak z metodą obliczania powyższego stopnia poprawności – dzięki zaawansowanej strukturze sieci neuronowych brane są pod uwagę również zależności pomiędzy wyrazami odległymi.

crossmenuchevron-down linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram