Omówienie zadania Pisarze (I etap XXVII OI)

Wstępne obserwacje

Zadanie wymaga od nas rozpoznania autora tekstu. Zadanie może się wydawać podobne do zadania "Languages" z IOI 2010, jednak w naszym przypadku mamy dwie istotne różnice:

• Wszystkie fragmenty są w tym samym języku, więc różnice między tekstami będą dużo bardziej subtelne.
• Mamy tylko trzy teksty źródłowe i są one znane przed czasem.

Zadanie z olimpiady międzynarodowej dotyczyło i wymagało budowania "bazy wiedzy" programu na bieżąco, podczas gdy my możemy przygotować ją przed czasem. Niestety, teksty źródłowe są stosunkowo długie – zajmują łącznie prawie 3MiB pamięci, a nawet spakowane dobrymi algorytmami kompresji nie nadają się do "wklejenia" do kodu. Autorowi nie udało się ich spakować do rozmiaru poniżej 800KiB.

Elementy analizy danych

Klasyczna analiza danych polega na zauważeniu zależności w dostępnej próbce danych, a następnie wyciąganiu wniosków o danych spoza próbki (tzw. reszty populacji). O ile niektóre zależności możemy zauważyć sami, inne chcemy wygenerować automatycznie. Te drugie warto skrupulatnie zweryfikować. Tak jak możemy być praktycznie pewni, że słowo "Wokulski" pojawi się w "Lalce" Bolesława Prusa, a nie pojawi się w "Panu Tadeuszu" ani w "Quo Vadis", to już teza o tym, że Mickiewicz pisze krótsze zdania niż Sienkiewicz, jest bardziej niepewna – należy ją sprawdzić.

Zwykle w tym celu analitycy danych dokonują podziału dostępnych danych na kilka grup:

• zbiór treningowy – dane, których używamy do szukania zależności
• zbiór walidacyjny – dane, na których weryfikujemy ogólność zależności znalezionych na zbiorze treningowym; używamy go, by wybrać te lepsze, a odrzucić te gorsze
• zbiór testowy – dane, których używamy do ostatecznego określenia jakości i ogólności naszego rozwiązania

Uważny Czytelnik zastanawia się pewnie, czemu nie wystarczy użyć zbioru treningowego (lub walidacyjnego) do określenia ostatecznej ogólności rozwiązania. Wynika to z faktu, że pewne zależności wystąpią w próbce z uwagi na jej mały rozmiar lub sposób jej doboru. Modele (rozumiane tu jako zbiory zależności), które zawierają takie cechy, nazywamy "przeuczonymi". Pozostawienie na boku zbioru walidacyjnego zwiększa szanse, że cechy te zostaną zidentyfikowane jako błędne.

Zbiór testowy ma nas z kolei zabezpieczyć przed modelami "przeuczonymi" na zbiorze walidacyjnym (zbiór walidacyjny pozwolił nam odrzucić modele "przeuczone" na zbiorze treningowym, ale sam stał się "źródłem informacji" o cechach, a więc zbiorem pseudo-treningowym).

Zadajmy sobie dwa nasuwające się pytania:

• Czy można ustalić automatyczne metody selekcji modeli lub cech, a następnie weryfikować te metody poprzez dodanie dodatkowych "warstw" zbiorów walidacyjnych?
  Owszem, można. Niektórzy puryści analizy danych uważają nawet, że każdy zbiór danych, na którym choćby mogła być podjęta decyzja (automatyczna lub ludzka), jest "spalony" i nie może być zbiorem testowym. Z drugiej strony co zrobić, jeśli na końcu każdego procesu dowiadujemy się, że wynik na zbiorze testowym jest niezadowalający? Sam fakt, że moglibyśmy podjąć decyzję o odrzuceniu naszego modelu, podaje w filozoficzną wątpliwość sens zbioru testowego. Na szczęście ludzie nie mają obowiązku postępować logicznie.
• Czy skoro fałszywe zależności wynikają ze zbyt małej ilości danych oraz sposobu ich doboru, czy możemy oczekiwać, że zależności znalezione na olbrzymich zbiorach danych są faktycznie "prawdziwe"?
  Owszem i duża część dzisiejszych wielkich modeli AI się na tym fakcie opiera, chociaż ciężko zdefiniować zwykle "idealny dobór" próbki, a co dopiero go zaimplementować, więc błędy wciąż się zdarzają.

Zadanie "Pisarze" w kontekście powyższego

Czy potrzebujemy dzielić dane na zbiory treningowy, walidacyjny i testowy?
W pewnym sensie nie. Jesteśmy w stanie generować nieograniczone ilości danych skryptem dostarczonym do zadania. Każde rozwiązanie, które stworzymy, możemy przetestować nowymi zestawami wygenerowanych danych. Każdy nowy wygenerowany zestaw staje się automatycznie wiarygodnym zestawem walidacyjnym lub testowym. To oznacza, że w momencie uzyskania programu rozpoznającego stabilnie jakiś procent tekstów, możemy się spodziewać zbliżonego wyniku w przypadku ogólnym, a więc i na danych testowych autorów zadania.

Rozwiązanie oparte na "klasycznej" analizie danych

Możemy spodziewać się różnic pomiędzy autorami opartych na cechach języka autorów oraz (czasami) specyfiki wydania tekstu:

• Procentowa liczność:
  • liter
  • wielkich liter
  • spacji
  • myślników
  • cyfr
  • cudzysłowów
  • pytajników
  • wielokropków
  • gwiazdek (*)
• Obecność słów podobnie zakończonych (rymów), zwłaszcza oddzielonych odpowiednią liczbą samogłosek ("Pan Tadeusz" jest pisany wierszem 13-zgłoskowym)
• Liczba słów w zdaniu

Lista oczywiście nie wyczerpuje wszystkich opcji – można np. policzyć częstotliwość pojedynczych literek lub n-gramów, a następnie wybrać najbardziej interesujące.

Na podstawie tak wygenerowanych cech możemy zbudować dowolny model tzw. uczenia maszynowego, którego metodę "predykcyjną" (zamieniającą cechy w przewidywany wynik) potrafimy zaimplementować, a zawartość modelu zmieścić w kodzie. Autor poleca modele oparte na tzw. najbliższych sąsiadach: kMeans (do generowania przykładów oraz weryfikacji, czy cechy oddzielają pisarzy między sobą) oraz kNN (jako prosty algorytm predykcyjny korzystający ze skupień wygenerowanych z kMeans). Jako silniejszy model można wykorzystać tzw. Gradient Boosting, które polega na iteracyjnym budowaniu małych drzew klasyfikacyjnych, których zadaniem jest poprawianie błędów tych poprzednich.

Rozwiązanie oparte na haszowaniu

Możemy spodziewać się różnic pomiędzy autorami opartych na pojawianiu się fragmentów, które występują tylko w jednym z dzieł albo w pozostałych występują "prawie nigdy".

Fragmenty nie muszą być nawet pojedynczymi słowami. Jesteśmy w stanie zapisać paręset takich haszy, więcej, jeśli uda nam się je skompresować. Dobór najczęstszych unikatowych słów pozwoli na uzyskanie sensownej punktacji za zadanie. Bardziej skomplikowane metody doboru fragmentów... zaczynają przypominać analizę danych.

Rozwiązania hybrydowe

Oba z powyższych podejść pozwalają "szybko" uzyskać sporo punktów, ale "żyłowanie" skuteczności rozwiązania zaczyna się szybko robić trudne. Na szczęście podejścia te różnią się od siebie, co pozwala spodziewać się, że połączenie ich w jedno pozwoli na wzajemne uzupełnienie niedociągnięć! Możemy zapisać np. po 50 unikatowych częstych słów z każdej książki, a następnie budować modele analizy danych dla fragmentów, które tych słów nie zawierają. Podejścia oparte na łączeniu różnych podejść w analizie danych nazywamy ensemblingiem.

Takie rozwiązanie jest – zdaniem autora – najprostszym sposobem na uzyskanie maksymalnej punktacji za zadanie "Pisarze".