Marcin Wojnarski, mwojnars at mimuw.edu.pl
Tematyka laboratorium:
uczenie maszynowe (Machine Learning, ML),
eksploracja danych (Data Mining, DM), odkrywanie wiedzy z danych
(Knowledge Discovery), inteligencja obliczeniowa (Computational
Intelligence).
Uwaga: powyższe pojęcia są bardzo bliskoznaczne.
Problemy, do których można stosować algorytmy ML, na przykładzie konkursów:
Netflix prize – konkurs o wartości 1 mln $. Zadanie: automatyczna rekomendacja filmów klientom internetowej wypożyczalni DVD, zob. opis.
KDD Cup – tematy konkursów ML/DM, organizowanych przy okazji jednej z głównych konferencji naukowych w tej dziedzinie.
Zapoznaj się z następującymi stronami i oprogramowaniem. W trakcie całego semestru będziemy korzystać z tych narzędzi:
Debellor – platforma (framework) do implementowania algorytmów ML, na której będą oparte rozwiązania zadań laboratoryjnych.
UCI – repozytorium zbiorów danych, wykorzystywanych do testowania i porównywania algorytmów ML.
ARFF – popularny w ML format zapisu danych, wprowadzony przez Wekę.
Weka, Rseslib – biblioteki algorytmów ML ogólnego przeznaczenia, niezwiązanych z konkretną dziedziną zastosowań (operują na prostych tabelkach decyzyjnych). Część algorytmów z Weki i Rsesliba jest dostępna w Debellorze.
Ćwiczenie:
Znajdź w UCI i sciągnij dane „Vowel Recognition” (nie „Japanese vowels”).
Przekształć pełny zbiór danych (990 przykładów, 14 atrybutów) do formatu ARFF, przypisz atrybutom poprawne nazwy, takie jak podane w opisie zbioru.
Sciągnij system Debellor. Uruchom dołączony do niego przykład, plik example.*
Wzorując się na przykładowym kodzie z klasy org.debellor.example.Main (kod źródłowy w pliku debellor.jar) napisz własny kod, generujący klasyfikator J48 Weki lub C45 Rsesliba dla danych Vowel. Na liście classpath musisz podać pliki JAR: debellor.jar, weka.jar, rseslib.jar.
Poeksperymentuj, np. zmień parametry klasyfikatora, usuń część danych itp.
Zaimplementuj algorytm k Najbliższych Sąsiadów (k-NN) jako komórkę Debellora. Przetestuj działanie tego algorytmu na danych Vowel Recognition (po odrzuceniu atrybutów „Train or Test”, „Speaker Number” i „Sex”), dla każdego możliwego wyboru parametru k. Powtórz testy, wykorzystując różne metody testowania:
Train+Test z wykorzystaniem podziału próbek dokładnie takiego, jaki jest opisany w pliku vowel-context.names.
Train+Test z wykorzystaniem losowego podziału w proporcjach 53% Train do 47% Test (w przybliżeniu takie proporcje jak w punkcie 1).
15-krotna kroswalidacja, każda 1/15 część wybierana losowo sposród wszystkich niewybranych dotąd próbek.
15-krotna kroswalidacja, każda 1/15 część wybierana jako 66 kolejnych próbek. Część 1. to próbki 1,2,3,...,66; część 2. to 67,68,...,132 itd.
Wynikiem każdego pojedynczego testu, przy ustalonym k w k-NN, jest procent popełnionych błędów w całym zbiorze danych, czyli liczba rzeczywista między 0 a 100.
Dla każdej metody testowania wykonaj wykres zależności błędu od wartości k. Zinterpretuj i porównaj otrzymane wykresy, odpowiadając krótko na poniższe pytania:
Skąd wynikają różnice w wynikach dla różnych wartości k?
W testach metodą 1 i 4, dla jakiego k błąd jest najmniejszy? Uzasadnij, dlaczego przy k = 1 i k = 100 błąd jest większy niż przy tej optymalnej wartości?
Jaki algorytm otrzymujemy przy maksymalnej możliwej wartości k? Czy potrafiłbyś przewidzieć jego wyniki bez uruchamiania testów? Dla każdej z 4 metod testowania podaj konkretną wartość lub jej jednostronne oszacowanie, wraz z uzasadnieniem.
Skąd wynikają różnice w wynikach metod 1 i 2, szczególnie przy k = 1?
Skąd wynikają różnice w wynikach metod 3 i 4, szczególnie przy k = 1?
Dlaczego błędy raportowane przez Train+Test są większe niż te generowane przez kroswalidację?
Przypuśćmy, że chcesz opracować system do automatycznego rozpoznawania samogłosek, wypowiadanych przez różnych ludzi. W tym systemie wykorzystasz algorytm k-NN, wytrenowany na całym zbiorze Vowel Recognition. Dysponując wynikami testów 1-4 odpowiedz na pytania:
Jaką wartość k będzie najlepiej wykorzystać?
Która z metod testowania 1-4 podaje oszacowanie błędu najbardziej zbliżone do faktycznego błędu, jaki będzie popełniał Twój system w działaniu na nowych danych?
Przypuśćmy, że Twój system będzie stosowany tylko przez tę grupę osób, od której pochodzą próbki zawarte w zbiorze Vowel Recognition (lista osób jest podana w pliku vowel-context.names). System ma więc być dopasowany tylko do tej grupy osób, nie musi natomiast generować prawidłowych wyników dla nieznanych osób. Czy przy takim założeniu zmienią się odpowiedzi na pytania z punktu 7?
Rozwiązanie zadania:
Kod źródłowy z implementacją k-NN i użytych metod testowania (poza metodą 2, do której można wykorzystać klasę TrainAndTest Debellora).
Wykresy.
Odpowiedzi na postawione pytania. Maks. 1000 słów.
Rozwiązanie należy wysłać na adres prowadzącego najpóźniej do 31 marca.
Wyniki dostępne TUTAJ.
Zbiór danych Adult Database z repozytorium UCI: ftp://ftp.ics.uci.edu/pub/machine-learning-databases/adult. Należy przekształcić do formatu ARFF - informacje nagłówkowe (typy i wartości atrybutów) są w pliku z opisem danych (adult.names).
Zadanie: zaimplementuj jako komórkę Debellora algorytm budowy drzewa decyzyjnego z obcinaniem gałęzi, tzn. przerywający dalsze rozwijanie węzła, jeśli ilość obiektów w tym węźle jest mniejsza niż k. Skonstruuj drzewa decyzyjne dla danych Adult, przy różnych wyborach parametru k. Przetestuj otrzymane drzewa na zbiorze testowym oraz treningowym, wyniki przedstaw w formie wykresu błędu w zależności od k. Zinterpretuj wyniki.
W eksperymentach wykorzystaj istniejący podział danych na zbiór treningowy (adult.data) i testowy (adult.test). Pomiń wzorce, które posiadają „brakujące wartości”, oznaczone symbolem „?”.
Dodatkowo, spróbuj wykorzystać algorytm budowy drzewa decyzyjnego do oceny, które atrybuty są najistotniejsze dla prawidłowej klasyfikacji wzorca. W jaki sposób można to zrobić?
Rozwiązanie zadania:
Kod źródłowy.
Wykres.
Raport, maks. 1500 słów:
krótki opis wykonanych eksperymentów,
interpretacja wykresu,
metoda i wyniki oceny istotności atrybutów.
Generując wyniki eksperymentów i tworząc wykres zwróć uwagę, aby wykres:
był czytelny,
obejmował cały przedział możliwych wartości k.
Przy większych k można „próbkować” k z pewnym skokiem. Jeśli wykres dla pełnego przedziału wartości k nie jest wystarczająco czytelny, to można dodatkowo stworzyć wykres(y) obejmujący pewien podprzedział istotny dla analizy.
Interpretując wyniki należy przede wszystkim odpowiedzieć na następujące pytania oraz podać wyjaśnienie zaobserwowanych zjawisk:
Jakie są elementy charakterystyczne wykresów:
ekstrema,
przedziały monotoniczności,
przedziały o stałej wartości funkcji?
Jak uzasadnić ich występowanie?
Jakie są dokładne wartości ekstremów? Czy takich należało się spodziewać?
Jakie są różnice i podobieństwa między wykresami dla zbioru treningowego i testowego? Z czego one wynikają?
Pewne elementy implementacji, na które warto zwrócić szczególną uwagę:
prawidłowe wyliczanie miary jakości testu,
prawidłowy wybór możliwych cięć dla atrybutu numerycznego (w połowie przedziału ograniczonego dwiema sąsiednimi wartościami, przyjmowanymi przez ten atrybut na zbiorze wzorców, które dotarły do danego węzła),
efektywny wybór najlepszego cięcia dla atrybutu numerycznego, w czasie O(n*log n),
prawidłowe kryterium oceny, czy dany węzeł drzewa należy dalej rozwijać.
Rozwiązanie należy wysłać na adres prowadzącego najpóźniej do 5 maja, a potem przedstawić osobiście na zajęciach.
Dnia 7.05.2009 rozpoczął się konkurs dla studentów wykładów: Sztuczna Inteligencja oraz Data Mining. Będzie trwał do 7.06.2009. Strona konkursu: http://tunedit.org/index.php/challenges.
Udział w konkursie jest nieobowiązkowy, ale gorąco do niego zachęcam, ponieważ jest to jedyna okazja, aby sprawdzić i potrenować „w boju” swoje umiejętności analizy danych i opracowywania skutecznych algorytmów uczenia maszynowego.
Konkurs posiada dwie niezależne „ścieżki”: A i B. Obydwie dotyczą tego samego problemu klasyfikacji, ale różnią się formą i sposobem oceny rozwiązania. Na ścieżce A rozwiązaniem jest kod algorytmu uczącego się – przy ocenie rozwiązania kod ten zostanie uruchomiony i użyty do sklasyfikowania nowych próbek; na końcową ocenę będzie miała wpływ nie tylko trafność klasyfikacji, ale też czas działania algorytmu. Natomiast na ścieżce B rozwiązaniem jest plik z decyzjami, przypisanymi przez algorytm próbkom testowym; ocenie będzie więc podlegać jedynie trafność klasyfikacji algorytmu. Wariant A jest wprawdzie – ze względów implementacyjnych – trudniejszy niż B, ale za to jest bardziej realistyczny z punktu widzenia praktycznych zastosowań, bo trzeba opracować algorytm nie tylko skuteczny, ale też odpowiednio szybki.
Można brać udział w obydwu wariantach konkursu jednocześnie. Można wykorzystywać istniejące biblioteki algorytmów, jak Weka, Rseslib lub inne. Można korzystać z istniejących systemów analizy danych, jak R, Matlab, Excel ;-) itd.
Rozwiązania można nadsyłać wielokrotnie, przez cały czas trwania konkursu. Są one na bieżąco weryfikowane, dostępny jest też aktualny ranking.
Udział w konkursie może być uwzględniony przy ustalaniu oceny końcowej z laboratorium:
Zwycięstwo na którejkolwiek ścieżce konkursu zostanie nagrodzone oceną bdb.
Jeśli rozwiązanie zajmie miejsce 2-3 na którejkolwiek ścieżce, to będzie można je zaliczyć jako duży projekt końcowy, pod warunkiem przygotowania raportu z dokładnym opisem algorytmu i przesłania jego kodu źródłowego (tzn. wszystkich fragmentów kodu pisanych przez autora; w przypadku ścieżki B nie musi to być w pełni wykonywalny, spójny kod).
Jeśli rozwiązanie zajmie dalsze miejsce, ale posiada zauważalny wkład intelektualny i eksperymentalny – nie jest to jedynie zastosowanie istniejącego algorytmu z jakiejś biblioteki; autor sam coś zaimplementował i wykonał eksperymenty porównawcze dla kilku wariantów swojego rozwiązania (najlepiej jeśli te wyniki będą zarejestrowane w systemie TunedIT) – wówczas będzie je można zaliczyć jako mały projekt końcowy, przy tych samych warunkach co wcześniej (raport, kod źródłowy).
Dodatkowo, aby zachęcić Państwa do podjęcia próby startu w konkursie, przyznawane będą punkty za samo wysłanie rozwiązania, pod warunkiem że jego wynik końcowy będzie choćby minimalnie lepszy od wyniku „Baseline”: po 1 punkcie dla każdej ze ścieżek. Punkty te będą dodawane do punktów uzyskanych za „zwykłe” zadania zaliczeniowe.
Do wyboru projekt “duży” na ocenę końcową max 5 lub “mały” na max 4. Termin zaliczania: przed końcem sesji czerwcowej.
Propozycje tematów na “duży” projekt (można proponować własny temat):
Uwaga: rozwiązanie należy najpierw przesłać mailem, a potem przedstawić osobiście prowadzącemu.
1. Rozpoznawanie ręcznie pisanych cyfr (OCR)
- Ściągnij z internetu dane MNIST [http://yann.lecun.com/exdb/mnist/].
- Zbuduj na nich klasyfikator oparty na sieci neuronowej [wykład 11] – algorytm należy samemu zaimplementować. Dobierz optymalną strukturę klasyfikatora i wartości parametrów uczenia (np. liczbę neuronów, stałe uczenia itp.) – wymaga to wykonania pewnej liczby eksperymentów, nie wystarczy jedno uruchomienie algorytmu (!). Opisz w raporcie przebieg i wyniki eksperymentów, optymalne wartości parametrów, błąd klasyfikatora na zbiorze treningowym i testowym.
- Napisz program demonstracyjny, wykorzystujący stworzony klasyfikator do rozpoznawania cyfr, pisanych na ekranie za pomocą myszki. Cyfry mogą być pisane jedna obok drugiej, w linii, więc przed wykonaniem klasyfikacji musisz je rozdzielić (segmentacja obrazu). Uwaga: program musi wykonywać przetwarzanie wstępne obrazu cyfry dokładnie takie, jakie zostało użyte do stworzenia zbioru MNIST – opis na stronie z danymi, w razie wątpliwości służę wyjaśnieniami.
2. Rozpoznawanie wzorów matematycznych
Program powinien umożliwiać użytkownikowi narysowanie myszką wzoru matematycznego, który następnie zostanie rozpoznany - np. przetworzony na format Latexa. Oczywiście należy ograniczyć się do jakiegoś małego podzbioru możliwych wzorów i do niewielkiego zbioru dopuszczalnych symboli. Algorytm klasyfikacji: drzewo decyzyjne lub sieć neuronowa. Dane wejściowe reprezentowane w formie trajektorii, a nie surowego obrazka (inaczej poprawne rozpoznanie byłoby bardzo trudne). Trudność: trzeba samemu zgromadzić dane treningowe i testowe.
3. Wizualizacja sieci neuronowej uczonej na danych 2D
Dane 2D to takie, gdzie są tylko 2 atrybuty wejściowe, o wartościach rzeczywistych. Takie dane można przedstawić graficznie jako punkty na płaszczyźnie. Jeśli mamy system klasyfikujący dane 2D, to można próbować na tej samej płaszczyźnie zaznaczyć odpowiedzi tego systemu (np. kolorem obszary o różnych decyzjach klasyfikacyjnych; lub za pomocą krzywych zaznaczać granice decyzyjne). Tematem zadania jest wymyślenie i zaimplementowanie takiej wizualizacji dla sieci neuronowej wielowarstwowej. Wizualizacja powinna działać w trakcie uczenia sieci, tak aby można było obserwować przebieg algorytmu uczenia. Powinna też umożliwiać wybór wizualizowanych neuronów i warstw oraz być interaktywna, tzn. udostępniać pewne dokładniejsze informacje o sieci lub konkretnych neuronach np. po kliknięciu myszką w pewien obszar płaszczyzny.
Projekt „mały”:
Zaimplementuj algorytm k-środków (k-means) [wykład 12].
Wygeneruj dane dwuwymiarowe (2 artybuty: x,y) poprzez losowanie:
500 razy z rozkładu jednostajnego na kole K((0.3,0.3);0.2)
200 razy z rozk. jedn. na K((0.5,0.8);0.1)
200 razy z rozk. jedn. na K((0.8,0.5);0.2)
(Uwaga: jak prawidłowo symulować rozkład jednostajny na kole?)
Uruchom algorytm k-środków na otrzymanych danych, dla k = 1,...,10, za każdym razem wypisując do pliku otrzymane środki oraz liczebność wszystkich klastrów. Jak zachowuje się algorytm przy zwiększaniu k? Czy potrafi prawidłowo wykryć trzy koliste grupy wzorców?
Uruchom algorytm po 3 razy dla tego samego k, startując od różnych konfiguracji początkowych (tzn. początkowego położenia środków). Czy za każdym razem otrzymujesz ten sam podział na klastry? Sprawdź k = 3, 5, 8.
Uruchom algorytm na danych Vowel z zadania I, wykorzystując pełne dane (połączone zbiory treningowy i testowy). Czy otrzymany podział na klastry pokrywa się w jakimś stopniu z zadanym podziałem na klasy? Sprawdź kilka różnych k.
Rozwiązanie: kod źródłowy, wygenerowane pliki (dane i wyniki algorytmu), raport. Należy wysłać na adres prowadzącego. Nie jest wymagana osobista prezentacja.