jump to navigation

Parę użytecznych rzeczy na temat eksploracji danych 03/17/2013

Posted by Mikołaj Morzy in eksploracja danych, teoria.
trackback

Pedro DomingosNa ubiegłorocznej konferencji CACM’2012 opublikowany został bardzo ciekawy artykuł Pedro Domingosa z University of Washington. Artykuł nosi tytuł „A Few Useful Things to Know about Machine Learning”  i postaram się go pokrótce streścić, żeby zachęcić do lektury.
Domingos zaczyna od zdefiniowania dziedziny uczenia maszynowego jako *uczenia programów na podstawie danych*. Nie jest to definicja wzbudzająca jakieś kontrowersje, choć interesujące jest przeniesienie nacisku z poszukiwania wzorców na znajdowanie programów. W swoim artykule koncentruje się przede wszystkim na problemie klasyfikacji i regresji, pomijając inne obszary (poszukiwanie asocjacji, analiza skupień, poszukiwanie wartości odstających). Dla niego proces uczenia się jest kombinacją trzech czynników: reprezentacji, oceny i optymalizacji. Reprezentacja to wybór sposobu, w jaki model będzie opisywany. Jest to o tyle istotne, że wybor konkretnej reprezentacji pośrednio definiuje zbiór wszystkich klasyfikatorów których dany model może się nauczyć. Jeśli dany klasyfikator nie mieści się w przestrzeni hipotez konkretnego modelu, taki klasyfikator po prostu nie może zostać wygenerowany. Oprócz wyboru reprezentacji dla modelu krok ten obejmuje sobą także wybór cech danych jakie będą podlegały uczeniu. Drugim czynnikiem jest ocena, czyli wybór funkcji wykorzystywanej do porównywania nauczonych klasyfikatorów. Trzeci czynnik, optymalizacja, to proces wyszukania w przestrzeni dostępnych klasyfikatorów tego klasyfikatora, który maksymalizuje funkcję wykorzystywaną do oceny. Taki podział algorytmów uczących na trzy niezależne czynniki jest o tyle interesujący, że pozwala dostrzec możliwości użycia kombinacji które nie są typowe.

  • reprezentacja: kNN, SVM, naiwny klasyfikator Bayesa, regresja logistyczna, drzewa decyzyjne, klasyfikator regułowy, sieć neuronowa, sieć Bayesowska
  • ocena: dokładność, precyzja i zwrot, błąd kwadratowy, prawdopodobieństwo a posteriori, Information Gain, Dywergencja KL
  • optymalizacja: algorytm zachłanny, beam search, B&B, metody gradientowe, Quasi-Newton, programowanie liniowe, programowanie kwadratowe

Jak się okazuje, można powiązać większość z wyżej przedstawionych konkretyzacji i uzyskać nowy model uczenia. Przykładowo, wybieramy kNN z miarą błędu kwadratowego i zachłannym poszukiwaniem najlepszej wartości parametru k. Nie każde połączenie ma tyle samo sensu, ale wiele z nich generuje egzotyczne algorytmy uczące.

Domingos kładzie bardzo duży nacisk na kwestię generalizacji. Przypomina o fundamentalnych zasadach testowania modeli i przestrzega przed nadmiernym optymizmem przy testowaniu na zbiorze uczącym. Zwraca też uwagę na interesujący aspekt uczenia maszynowego: w przeciwieństwie do innych problemów optymalizacyjnych w przypadku uczenia klasyfikatora nie dysponujemy funkcją którą próbujemy optymalizować, w związku z czym posługujemy się wyznaczonym błędem na zbiorze uczącym jako zastępstem rzeczywistego błędu.

Interesujące jest też nawiązanie do słynnego twierdzenia Davida Wolperta o braku darmowego lunchu w wyszukiwaniu i optymalizacji. Domingos pokazuje to na prostym przykładzie: niech zbiór danych jest opisany za pomocą 100 zmiennych binarnych. Dysponuję w moim zbiorze uczącym milionem etykietowanych przypadków. Milion to przecież bardzo dużo, w zupełności wystarczy żeby generalizować nauczony model, prawda? Niestety, nie… Przy 100 zmiennych i 1 000 000 rekordów przestrzeń wyszukiwania nadal zawiera 2^{100} - 10^{6} przypadków, dla których nie znam wartości zmiennej zależnej! Jeśli nie posiadam dodatkowej wiedzy eksperckiej, wówczas żaden algorytm eksploracji danych nie jest w stanie przebić zwykłego losowego rzucania monetą. Oczywiście powyższe to najgorszy z możliwych scenariuszy, w rzeczywistości funkcje których próbujemy się nauczyć nie są rozłożone jednostajnie w przestrzeni wszystkich możliwych 2^{100} funkcji. Korzystając z założenia o tym, że podobne przypadki należą do podobnych klas lub dodatkowej wiedzy o zależnościach między atrybutami możemy bardzo znacząco ograniczyć przestrzeń wyszukiwania. Ten indukcyjny proces uzyskiwana użytecznej wiedzy z niewielkiej ilości wiedzy początkowej stanowi sedno całej dziedziny uczenia maszynowego. Jak pisze Domingos:

[…] induction is a knowledge lever: it turns a small amount of input knowledge into a large amount of output knowledge. Induction is a vastly more powerful leveer than decuction, requiring much less input knowledge to produce useful results, but it still needs more than zero input knowledge to work.

Bardzo podobało mi się także proste i czytelne wytłumaczenie zjawiska przetrenowania modelu (ang. overfitting) zarówno pod kątem wariancji, jak i systematycznej tendencyjności (ang. bias) za pomocą jednego rysunku:

bias-varianceDomingos sporo miejsca poświęca też przekleństwu wymiarowości (ang. curse of dimensionality). Nawet, jeśli jesteśmy świadomi problemu, umyka on naszemu intuicyjnemu rozumieniu. Przykładowo, jeśli funkcja której próbujemy się nauczyć to f(x)=x_1 \wedge x_2, to zadanie jest proste. Teraz dodajmy 98 niezwiązanych z funkcją celu zmiennych x_3, \ldots, x_{100} i okaże się, że szum informacyjny dodatkowych wymiarów całkowicie przykrywa funkcję celu. Może rozwiązaniem jest zwiększenie zbioru danych? Próżne nadzieje, w przypadku 100 wymiarów binarnych (a przecież trudno jeszcze tu mówić o wielkiej liczbie wymiarów) i monstrualnym zbiorze danych liczącym bilion rekordów, nadal pokrywamy zaledwie 10^{-18} część przestrzeni… Ogromna liczba wymiarów fatalnie też wpływa na wszystkie metody bazujące na odległości między przypadkami, ponieważ każdy kolejny wymiar zwiększa liczbę przypadków położonych w tej samej odległości od danego przypadku, sprowadzając metody najbliższych sąsiadów do losowego wyboru sąsiadów.
Pozostałe problemy opisywane przez Domingosa dotyczą użyteczności teoretycznych granic błędów, znaczenia metod ekstrakcji atrybutów, przydatności ogromnych wolumenów danych (mimo wszystko), oraz dominacji metod wykorzystujących łączenie wielu modeli (ang. ensembles). Cały artykuł jest napisany bardzo czytelnie i przystępnie, dla początkujących adeptek i adeptów eksploracji danych będzie to dobre wprowadzenie i zbudowanie solidnych podstaw „filozoficznych”, ale i osoby doświadczone mogą ze zdumieniem odkryć dla siebie nowe aspekty eksploracji danych.

Na koniec, jako zachęta, lista tytułów sekcji:

  • Learning = Representation+Evaluation+Optimization
  • It’s Generalization That Counts
  • Data Alone Is Not Enough
  • Overfitting Has Many Faces
  • Intuition Fails in High Dimensions
  • Theoretical Guarantees Are Not What They Seem
  • Feature Engineering Is the Key
  • More Data Beats a Cleverer Algorithm
  • Learn Many Models, Not Just One
  • Simplicity Does Not Imply Accuracy
  • Representable Does Not Imply Learnable
  • Correlation Does Not Imply Causation

Domingos, P. (2012). A few useful things to know about machine learning Communications of the ACM, 55 (10) DOI: 10.1145/2347736.2347755

Komentarze»

1. Łukasz - 03/17/2013

Whoa, poznałem gościa ze zdjęcia… Był/jest zamieszany w (jedno z paru) narzędzi do pracy z Markov Logic Networks (jedno z kilkudziesięciu podejść do statistical relational learning). Ostatnio wyszła wersja 2.0, czekamy na dokumentację http://alchemy.cs.washington.edu/

2. Gammon No.82 - 06/26/2013

Cudowne! Praktycznie nic nie rozumiem!


Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d bloggers like this: