Podstawy Positive-Unlabeled Learning

28.04.2020 | Mateusz Kaleta

Wstęp

Można zaryzykować stwierdzenie, że data scientist rzadko spotyka w codziennej pracy zbiory danych o wysokiej jakości, w pełni oznaczone i “skore do kooperacji”. Chleb powszedni stanowią brakujące wartości, obserwacje odstające czy wręcz błędne. Każdy, kto choć raz podjął trudy pracy nad danymi, mógłby przytoczyć zapewne wiele więcej lub bardziej ciekawych przykładów, problemów, z którymi trzeba było się zmierzyć, jeszcze przed rozpoczęciem modelowania czy wyciągania wniosków.

Rozmyślając nad tematem niniejszego artykułu, brałem pod uwagę przede wszystkim kłopoty, z którymi mierzymy się w pracy zawodowej, a o których rzadko się mówi we wstępnych kursach lub po prostu są dość specyficzne.

Zdałem sobie sprawę, że jest jedno miejsce w procesie budowania inteligentnych rozwiązań, które bierzemy często za niewymagające naszej specjalnej uwagi, intuicyjne i proste. A to może rodzić poważne błędy. To miejsce to definicja problemu.

Klasyfikacja, a może analiza skupień? Jaki typ uczenia?​

Jedną z pierwszych czynności, którą powinniśmy wykonać we wczesnej fazie projektu, to odpowiedzenie sobie na pytanie: co chcemy osiągnąć? Czy chcemy wskazać anomalie? Oszacować prawdopodobieństwo przynależności próbki do jakiejś klasy? A może wyodrębnić podobne do siebie grupy obserwacji? Tu zwykle problemu jeszcze nie ma.

Druga sprawa to typ uczenia, jaki możemy zastosować. Jeżeli nie posiadamy etykiet w ogóle, mamy do czynienia z uczeniem nienadzorowanym. Gdy szczęśliwie, jesteśmy w posiadaniu zbioru w pełni oznaczonego, możemy zastosować techniki uczenia nadzorowanego.

I tu proponuję się na chwilkę zatrzymać. Myśląc o swoich doświadczeniach zawodowych dochodzę do obserwacji, że chyba nigdy nie pracowałem nad problemem uczenia w pełni nadzorowanego. Rzeczywistość, w której najczęściej się znajdowałem, to posiadanie dużego zbioru danych z garstką etykiet lub z zestawem etykiet tylko dla jednej klasy. Te warunki wskazują na problem uczenia częściowo nadzorowanego (ang. semi-supervised learning).

Niby prosta sprawa, a jednak wydarzenia wokół trwającej pandemii wirusa SARS-CoV-2 pokazują, że nie jest to tak intuicyjne, jak by się tego chciało. Ile razy nie słyszeliśmy wypowiedzi ekspertów, którzy używali terminu “potwierdzony przypadek” naprzemiennie z “liczbą chorych”? Jak często odpowiadamy w wywiadzie medycznym, że jesteśmy zdrowi, mimo, że oczywiście nie zostaliśmy przebadani na wszystkie możliwe (zwłaszcza rzadkie) choroby? Czy to, że użytkownikowi wyświetlono reklamę, ale nie zakupił produktu oznacza, że nie jest nim zainteresowany?

Często nawet mimo posiadania właściwych odpowiedzi na powyższe pytania, kusi nas, by zastosować jakiś algorytm klasy supervised learning. Czasem jest to prawidłowe, czasem nie.

Positive-Unlabeled Learning

PU learning to specyficzny problem klasyfikacji binarnej w sytuacji, gdzie część obserwacji klasy pozytywnej jest oznaczona, a pozostałe obserwacje nie posiadają etykiety i mogą należeć do którejś z dwóch klas. Cel pozostaje taki sam: zbudowanie modelu, który jest w stanie odróżnić obserwacje klasy pozytywnej od obserwacji klasy negatywnej. Droga do zbudowania finalnego rozwiązania w przypadku PU learning jest jednak nieco bardziej kręta i wyboista. Wystarczy spojrzeć na poniższy wykres, by zauważyć, że nie będzie tak łatwo, jakby się tego chciało.​

Założenia

Pomysłów na rozwiązanie takiego problemu jest mnóstwo, natomiast wiele z nich wymaga prawdziwości pewnych założeń. Przedstawię kilka z nich, o które mogą być oparte algorytmy PU Learning. Część dotyczy procesu oznaczania obserwacji, część - samych danych. Założenia te są jednak całkiem intuicyjne.

1. Dane
   
   Najsilniejszym założeniem o danych w przypadku PU Learning jest to o posiadaniu takiej samej etykiety przez obserwacje podobne, znajdujące się w przestrzeni blisko siebie (ang. smoothness assumption). O ile korzystamy z tego założenia w uczeniu maszynowym w ogóle, to jednak biorąc pod uwagę, że mamy do czynienia z semi-supervised learning, a etykiet jest najczęściej za mało, postanowiłem to szczególnie podkreślić.
2. Proces oznaczania
   
   Najprzyjemniejsza sytuacja to taka, w której obserwacje wybrano do oznaczenia zupełnie losowo, a ich rozkład odzwierciedla rozkład całej populacji. Z takiego założenia ludzkość korzysta w niezliczonych zastosowaniach (chociażby exit polls, A/B testing na portalach społecznościowych). Trudno jednak o praktyczny przykład w świecie danych PU.
   

   Sytuację obrazuje wykres powyżej. Mimo, iż znaczna część zbioru danych pozostaje zupełnie nieoznaczona, to prawdopodobnie jedyne etykiety, którymi dysponujemy mogą okazać się wystarczające z uwagi na podobny rozkład obserwacji oznaczonych do rzeczywistej klasy pozytywnej. Rozwiązanie, w tym przypadku, można by było sprowadzić do zbudowania zwykłego binarnego klasyfikatora, ale z ewentualnym zastosowaniem zmodyfikowanych wag dla znanej klasy. Wyznaczenie granicy decyzyjnej nie powinno sprawić trudności. To założenie jest jednak, poniekąd oderwane od rzeczywistości.

   Częściej spotykamy się wszakże z sytuacją, gdzie rozkład atrybutów oznaczonych instancji nie odpowiada rozkładowi całej populacji. Intuicyjnie, tak będzie bardzo często w przypadku danych medycznych, czy wszelkich anomalii.

   Wyobraźmy sobie, że naszym celem jest zastąpienie silnika regułowego modelem uczenia maszynowego i posiadamy historię zweryfikowanych ręcznie, zaklasyfikowanych, jako true positive’y obserwacji. I tak na przykład, mając do czynienia z analizą fraudów na kartach kredytowych, moglibyśmy posiadać oznaczone tylko fraudowe transakcje wykonane za granicą, powyżej kwoty 100 Euro. Widać więc wprost, że prawdopodobieństwo posiadania przez daną obserwację etykiety zależy w pewien sposób od jej atrybutów.

   Tę sytuację ilustruje następujące zestawienie:

   Część rozkładu klasy pozytywnej (po lewej stronie) zostało zupełnie pominięte przez proces etykietowania danych. W tym przypadku sprawa nie będzie już tak łatwa.
3. Prawdopodobieństwo a priori
   
   

   Bardzo przydatnym narzędziem w budowie modelu w zadaniu PU learning byłby prior, czyli pewne wstępne oczekiwanie, co do rozkładu zmiennej niezależnej (tu: oczekiwany stosunek liczności klas). Często jednak nie mamy możliwości dokonania takich założeń. Na przykładzie pandemii SARS-CoV-2: nie jest znany odsetek osób, które faktycznie przechodzą obecnie tę chorobę.

   Szczególnie interesującą, ale i równie rozczarowującą konsekwencją powyższego jest to, iż de facto... tracimy możliwość dostrajania hiperparametrów i finalnej ewaluacji modelu! Bo jak wyliczyć F1, czy precyzję bez etykiet?

Porażka?

Sytuacja jest, jak widać, dość trudna. Warto sobie uświadomić, że jeżeli projekt ma się zakończyć kiedyś sukcesem, to koniecznie należy dołożyć starań, by znaleźć się w wygodniejszym położeniu - najpierw zbudować mały zbiór walidacyjny, następnie kontynuować oznaczanie danych treningowych. W pewnym momencie będzie można już prawdopodobnie pracować w warunkach binarnej klasyfikacji.

Wciąż jednak nie jesteśmy bezbronni. Pozostają nam jeszcze techniki z grupy metod dwukrokowych. Te lubię i polecam, bo choć stanowią mniejszość, są pozbawione szeregu założeń, a przez to praktyczne.

Techniki dwukrokowe

Jak już wspominałem, istotne jest to, że podobne do siebie przypadki mają adekwatnie większe prawdopodobieństwo przynależności do tej samej klasy, niż przypadki od siebie się różniące. W przypadku danych medycznych, pacjenci posiadający podobne symptomy prawdopodobnie chorują na tą samą chorobę i raczej nie otrzymają takiej diagnozy, jak ktoś wykazujący zupełnie inne objawy.

Techniki dwukrokowe oparte są o intuicyjną myśl, iż oznaczone próbki posiadają inny rozkład, niż pewien nieznany podzbiór klasy negatywnej. Ogólny algorytm jest bardzo prosty:

1. W zbiorze nieoznaczonym wyodrębniany jest podzbiór obserwacji, które znacznie kontrastują ze znanymi, pozytywnymi przypadkami. Ten podzbiór określany będzie mianem reliable negatives.
2. W oparciu o zbiór reliable negatives i oznaczonych obserwacji, realizowany jest trening klasyfikatora binarnego.

Istnieją różne implementacje tego algorytmu. Różnice dotyczą m.in. sposobu utworzenia zbioru reliable negatives i sposobu inkorporacji tego zbioru w procesie uczenia klasyfikatora. Pokrótce opiszę jedną z kombinacji algorytmów, którą można zastosować.

1. C-CRNE (Clustering-based method for Collecting Reliable Negative Examples)
   
   Jedną ze strategii wyboru rzetelnych negatywnych obserwacji jest to, aby dokonać klasteryzacji całego zbioru (pozytywów i nieoznaczonych instancji). Ten klaster, do którego trafi relatywnie najmniej znanych obserwacji klasy pozytywnej, posłuży, jako surogat klasy negatywnej w treningu klasyfikatora.
   
   Zobrazowane jest to na wykresie poniżej. Zbiór uległ procesowi klasteryzacji, powstały cztery grupy. Najmniejszy udział znanych pozytywnych obserwacji przypada na grupę numer trzy (kolor fioletowy).
   
   Z założenia gładkości, można dalej kontynuować trening modelu w oparciu o zbiór instancji klasy pozytywnej oraz właśnie wyznaczonych reliable negatives.
   
2. Iterative SVC
   
   Posiadając już tak przygotowany zbiór, pozostaje zbudowanie klasyfikatora. Iterative SVC polega na tym, że w każdym kroku budowany jest Support Vector Classifier oparty o oznaczone we wcześniejszym etapie dane, przy czym po każdej iteracji dokonywane jest przez model określenie etykiet pozostałych obserwacji (na powyższym obrazku - unlabeled). Te, które model wskaże, jako negatywne są dołączane do zbioru reliable negatives w dalszym uczeniu.
   
   Proces powtarzany jest na przykład do momentu, kiedy granica decyzyjna już bardziej się nie przesuwa, przepaliliśmy wszystkie pieniądze na AWS albo na przykład wykonaliśmy już jakąś okrągłą liczbę iteracji.

Kod

Nareszcie! Koniec dywagacji! Czym byłyby powyższe słowa bez praktycznego ćwiczenia?

Zupełnie bez konieczności instalacji dodatkowego oprogramowania na swoim sprzęcie, można skorzystać z notatników on-line, zawierające przykładowy kod w Pythonie.

Udostępniam dwie wersje notebooka:

1. Tylko do odczytu, z wynikami (link). Nie wymaga logowania.
2. Edytowalną (link). Tu do pracy potrzebne jest konto google, a uruchomienie sprowadza się do kombinacji Ctrl+F9. Zapraszam do grzebania w kodzie.

Co dalej?

Jeżeli temat przypadł do gustu, to szczególnie zachęcam do przeczytania przydługawego, ale jednak kompleksowego artykułu autorstwa Bekker i Davis, stanowiącego przegląd technik uczenia w oparciu o dane PU. Strategie są tam omawiane z niewiele większą dozą szczegółów, niż w niniejszym artykule.

W praktycznym przykładzie zostały wykorzystane dane Banknot Authentication Dataset, pochodzące ze zbiorów UCI.