Uczenie się maszyn: wykład 15
Ćwiczenia

Paweł Cichosz

Date: Semestr zimowy 1997/98

Aby umożliwić weryfikację zrozumienia i utrwalenie materiału przedstawionego na wszystkich dotychczasowych wykładach, a także ułatwić przygotowanie do kolokwium, proponuję do rozważenia podane niżej ćwiczenia. Są one w większości dość proste i, być może z małymi wyjątkami, nie zanadto pracochłonne. Uporządkowane zostały w przybliżeniu w kolejności wykładów, których dotyczą, chociaż niektóre wymagają połączenia wiadomości z różnych wykładów. Przy okazji warto też przejrzeć ponownie notatki, gdyż co najmniej kilkakrotnie znalazły się tam sugestie problemów do przemyślenia. Niektóre z nich powtórzono poniżej, ale prawdopodobnie nie wszystkie.

Spora część podanych ćwiczeń zakłada, że dany jest pewien problem indukcyjnego uczenia się pojęć (tj. dziedzina, atrybuty, klasa pojęć i hipotez) oraz zbiór danych (najczęściej zbiór trenujący do śledzenia działania różnych algorytmów). Przyjmujemy tu dla wygody, że zawsze chodzi o dziedzinę określoną w przykładzie o klasyfikowaniu pogody i podany dla niego zbiór trenujący (niekiedy ograniczamy go do kilku wybranych przykładów), zaś przyjęta przestrzeń hipotez jest podawana treści ćwiczenia lub wynika z algorytmu, którego dotyczy ćwiczenie. Jeśli ćwiczenia tego typu pojawią się na kolokwium, będą dotyczyć oczywiście innej dziedziny i innego zbioru danych.

Kilka ćwiczeń polega na zaproponowaniu pewnych algorytmów lub szkiców algorytmów, będących modyfikacjami lub rozszerzeniami algorytmów omawianych na wykładzie. Chodzi o raczej proste pomysły i ich umiejętne, lecz niekoniecznie bardzo szczegółowe sformułowanie.

1. Czy klasa pojęć reprezentowanych jako prostokąty w $\mathbb{R}^2$ o bokach równoległych do osi układu współrzędnych jest PAC-nauczalna za pomocą przestrzeni hipotez reprezentowanych jako kwadraty w $\mathbb{R}^2$ o bokach równoległych do osi układu współrzędnych? Uzasadnić.
2. Rozważmy dziedzinę i atrybuty jak dla pogody. Niech $\mathbb{H}$ będzie przestrzenią hipotez reprezentowanych przez wszystkie (syntaktycznie) poprawne różne drzewa decyzyjne dla tych atrybutów. Ile przykładów trenujących wystarczy, aby dowolny spójny algorytm uczący się nauczył się dowolnego pojęcia $c\in\mathbb{C}=\mathbb{H}$ z prawdopodobieństwem co najmniej $1-\delta$ hipotezy o błędzie rzeczywistym nie przekraczającym $\epsilon$?

   Wskazówka:

   Zaproponować sensowne (ale niekoniecznie bardzo ścisłe) górne ograniczenie na liczbę różnych hipotez.

3. Rozważmy dziedzinę i atrybuty jak dla pogody. Niech $\mathbb{H}$ będzie przestrzenią hipotez reprezentowanych przez wszystkie różne kompleksy selektorów pojedynczych, pustych i uniwersalnych dla tych atrybutów. Ile przykładów trenujących wystarczy, aby dowolny spójny algorytm uczący się nauczył się dowolnego pojęcia $c\in\mathbb{C}=\mathbb{H}$ z prawdopodobieństwem co najmniej $1-\delta$ hipotezy o błędzie rzeczywistym nie przekraczającym $\epsilon$? Jak zmieni się oszacowanie, jeśli dopuścimy selektory dysjunkcyjne w hipotezach?
4. Zaproponować spójny algorytm uczący się koniunkcji literałów boolowskich dla $n$ zmiennych działający w czasie wielomianowym względem $n$.
5. Podać wymiar VC dla przestrzeni hipotez reprezentowanych przez koniunkcje literałów boolowskich dla $n$ zmiennych.
6. Udowodnić, że jeśli $S$ i $G$ są odpowiednio szczegółowym i ogólnym ograniczeniem przestrzeni wersji $\mathrm{VS}^c_{\mathbb{H},D}$, to $h\in \mathrm{VS}^c_{\mathbb{H},D}$ wtedy i tylko wtedy, gdy $S\preceq h\preceq G$.
7. Przyjmując dziedzinę i atrybuty jak dla pogody oraz przestrzeń hipotez $\mathbb{H}$ reprezentowanych jako kompleksy selektorów (pojedynczych, pustych lub uniwersalnych), podać liczbę hipotez w przestrzeni wersji $\mathrm{VS}^c_{\mathbb{H},D}$ dla zbioru $D$ i pojęcia $c$ określonych przez pierwsze cztery przykłady trenujące dla pogody.
8. Prześledzić działanie algorytmu CAE (podając zbiory $S$ i $G$ po rozpatrzeniu kolejnych przykładów) dla zbioru trenującego składającego się z przykładów 1, 3, 6 i 7 ze zbioru danych dla pogody.
9. Dla dziedziny i atrybutów jak dla pogody oraz przestrzeni hipotez reprezentowanych jako kompleksy selektorów (pojedynczych, pustych lub uniwersalnych) dane są zbiory $S=\{\langle r,?,?,w\rangle,\langle ?,h,?,w\rangle\}$ i $G=\{\langle r,?,?,?\rangle,\langle ?,h,?,?\rangle,\langle ?,?,?,w\rangle\}$. Załóżmy, że nauczyciel proponuje uczniowi wykorzystującemu algorytm CAE ujawnienie kategorii jednego z przykładów 1, 7, 13. Który z nich powinien wybrać uczeń dążący do uzyskania jak najszybszej zbieżności?

   Wskazówka:

   Zakładając, że każdy z podanych trzech przykładów może z jednakowym prawdopodobieństwem być pozytywny lub negatywny, określić oczekiwaną redukcję rozmiaru przestrzeni wersji dla każdego z nich.

10. Dla dziedziny i atrybutów jak dla pogody oraz przestrzeni hipotez reprezentowanej przez drzewa decyzyjne, podać które z podanych poniżej hipotez są porównywalne i w jaki sposób za pomocą relacji większej/mniejszej szczegółowości:

    $h_1$:

    outlook

    = sunny $\rightarrow$ yes

    outlook

    = overcast $\rightarrow$ no

    outlook

    = rain $\rightarrow$ no

    $h_2$:

    outlook

    = sunny

    wind

    = weak $\rightarrow$ no

    wind

    = strong $\rightarrow$ yes

    outlook

    = overcast

    humidity

    = normal $\rightarrow$ yes

    humidity

    = high $\rightarrow$ no

    outlook

    = rain $\rightarrow$ no

    $h_3$:

    wind

    = weak

    outlook

    = sunny $\rightarrow$ yes

    outlook

    = overcast $\rightarrow$ yes

    outlook

    = rain $\rightarrow$ no

    wind

    = strong

    outlook

    = sunny $\rightarrow$ yes

    outlook

    = overcast $\rightarrow$ no

    outlook

    = rain $\rightarrow$ no

    $h_4$:

    wind

    = weak $\rightarrow$ no

    wind

    = strong

    outlook

    = sunny $\rightarrow$ yes

    outlook

    = overcast $\rightarrow$ no

    outlook

    = rain $\rightarrow$ no

11. Dla dziedziny i atrybutów jak dla pogody oraz zbioru trenującego składającego się z przykładów o numerach parzystych, dane jest następujące drzewo decyzyjne w trakcie budowy:

    outlook

    = sunny $\rightarrow$ no

    outlook

    = overcast $\rightarrow$ yes

    outlook

    = rain

    *

    Jaki test zostanie wybrany dla węzła oznaczonego gwiazdką?
12. Przyjmując dziedzinę i atrybuty jak dla pogody, podać drzewo decyzyjne równoważne następującemu zbiorowi reguł:

    IF $\langle s\lor o,?,?,w\rangle$ THEN $y$,
    IF $\langle o,h\lor m,?,?\rangle$ THEN $y$,
    IF $\langle s,?,n?\rangle$ THEN $y$.

13. Przyjmując dziedzinę i atrybuty jak dla pogody, podać dowolny zbiór trenujący, dla którego algorytm ID3 (uczący się dokładnych drzew na podstawie całego zbioru trenującego) wygenerowałby następujące drzewo decyzyjne:

    outlook

    = sunny

    wind

    = weak $\rightarrow$ no

    wind

    = strong $\rightarrow$ yes

    outlook

    = overcast

    humidity

    = normal $\rightarrow$ yes

    humidity

    = high $\rightarrow$ no

    outlook

    = rain $\rightarrow$ no

14. Zaproponować algorytm konstruowania drzew decyzyjnych, który otrzymuje jako parametr maksymalną liczbę węzłów w drzewie i konstruuje możliwie jak najlepsze drzewo przy uwzględnieniu tego ograniczenia.
15. Przyjmując dziedzinę i atrybuty jak dla pogody oraz zbiór trenujący złożony z przykładów o numerach parzystych, podać błąd próbki algorytmu AQ (uczącego się reguł dla kategorii yes) dla zbioru złożonego z przykładów o numerach nieparzystych. Parametry algorytmu: $m=3$, heurystyka oceniająca kompleksy według łącznej liczby pokrywanych przykładów trenujących o kategorii zgodnej z kategorią ziarna i niepokrywanych przykładów trenujących o kategorii różnej od kategorii ziarna (w przypadku równych ocen rozstrzyga mniejsza liczba występujących wartości atrybutów, a gdyby i te były równe -- kolejność), ziarna wybierane ze zbioru trenującego w kolejności numerów przykładów.
16. Załóżmy, że atrybut temperature występujący w zbiorze danych dla pogody ma wartości ciągłe, dla kolejnych przykładów zbioru trenującego złożonego tylko z przykładów o numerach parzystych równe odpowiednio $31$, $24$, $17$, $22$, $25$, $23$, $25$. Które dwa z czterech przedziałów: $(-\infty,20]$,$(20,23]$, $(23,27]$, $(27,\infty)$ zostałyby połączone przez algorytm ChiMerge?
17. Dane jest następujące drzewo grupowania utworzone przez system COBWEB po przetworzeniu przykładów 1-5 dla pogody:

    $\{1,2,3,4,5\}$

    $\{1\}$

    $\{2\}$

    $\{3\}$

    $\{4\}$

    $\{5\}$

    Która z następujących decyzji dotyczących przykładu 6 na poziomie 1 drzewa da w efekcie lepszą jakość grupowania: utworzenie dla niego nowego węzła, czy dołączenie go do węzła zawierającego przykład 5?
18. Zaproponować sposób wykorzystania algorytmu COBWEB do uczenia się z nadzorem pewnego pojęcia docelowego.
19. Przyjmijmy dziedzinę i atrybuty jak dla pogody oraz zbiór trenujący złożony z przykładów o numerach parzystych. Niech przestrzeń hipotez składa się wyłącznie z hipotez reprezentowanych przez kompleksy atomowe dla selektorów pojedynczych oraz kompleks sprzeczny i uniwersalny. Które z przykładów 1, 3, 5 naiwny klasyfikator bayesowski zaklasyfikuje inaczej, niż optymalny klasyfikator bayesowski (przy założeniu, że w przypadku jednakowego prawdopodobieństwa kategorii 0 i $1$ wybiera on 0) oraz hipoteza MAP (pierwsza leksykograficznie, jeśli jest ich wiele) dla tej przestrzeni hipotez? Przyjąć, że wszystkie hipotezy są jednakowo prawdopodobne a priori. Prawdopodobieństwa szacowane na podstawie zbioru trenującego jako 0 zastąpić w obliczeniach przez $0.01$.
20. Przyjmując dziedzinę i atrybuty jak dla pogody oraz zbiór trenujący złożony z przykładów o numerach parzystych, podać błąd próbki naiwnego klasyfikatora bayesowskiego dla zbioru przykładów o numerach nieparzystych.
21. Zaproponować sposób wykorzystania naiwnego klasyfikatora bayesowskiego dla dziedzin charakteryzowanych za pomocą atrybutów ciągłych.
22. Zaproponować sposób wykorzystania zasady minimalnej długości kodu do grupowania pojęciowego podając odpowiedni schemat obliczania długości kodu.
23. Zaproponować sposób wykorzystania zasady minimalnej długości kodu do dyskretyzacji atrybutów ciągłych podając odpowiedni schemat obliczania długości kodu.
24. Zaproponować sposób wykorzystania zasady minimalnej długości kodu do oceny jakości kompleksów podczas indukcji reguł podając odpowiedni schemat obliczania długości kodu.
25. Dany jest zbiór wartości zmiennych $x$ i $y$:

    $x$	$y$
    $1$	$-1.45$
    $3$	$-56.05$
    $8$	$-861.06$
    $17$	$-3910.25$
    $21$	$-3679.45$
    $33$	$28788.95$

    Odkryć równanie $y=f(x)$.
26. Dane jest pojęcie $\textit{dostanie-kredyt}(x,y)$, interpretowane jako stwierdzenie, że $x$ może dostać w swoim banku kredyt konsumpcyjny na sumę $y$, oraz następująca teoria dziedziny:

    $\textit{dochód-na-osobę}(x,v) \land \textsf{większy}(v,0.1y) \rightarrow \textit{dostanie-kredyt}(x,y)$,

    $\textit{dochód-w-rodzinie}(x,w) \land \textit{osoby-w-rodzinie}(x,l) \land \textit{równy}(v,w/l) \rightarrow \textit{dochód-na-osobę}(x,v)$,

    $\textit{wolny}(x) \land \textit{zarabia}(x,v) \rightarrow \textit{dochód-w-rodzinie}(x,v)$,

    $\textit{małżeństwo}(x,y) \land \textit{zarabia}(x,v_1) \land \textit{zarabia}(y,v_2) \land \textit{równy}(v,v_1+v_2) \rightarrow \textit{dochód-w-rodzinie}(x,v)$,

    $\textit{wolny}(x) \land \textit{dzieci}(x,l_1) \land \textit{równy}(l,l_1+1) \rightarrow \textit{osoby-w-rodzinie}(x,l)$,

    $\textit{małżeństwo}(x,y) \land \textit{dzieci}(x,l_1) \land \textit{równy}(l,l_1+2) \rightarrow \textit{osoby-w-rodzinie}(x,l)$.

    Wyjaśnić przykład pozytywny:

    $\textit{dostanie-kredyt}(\textit{Jan},10000)$,

    $\textit{zarabia}(\textit{Jan},2500)$,

    $\textit{małżeństwo}(Jan,Anna)$,

    $\textit{zarabia}(Anna,2000)$,

    $\textit{dzieci}(\textit{Jan},1)$

    i uogólnić uzyskane wyjaśnienie.
27. Prześledzić działanie algorytmu L* uczącego się automatu z alfabetem wejściowym $\{0,1\}$ rozpoznającego wszystkie napisy zaczynające się od $00$ i kończącego się na $11$.
28. Rozważmy środowisko siatki $5\times 5$ z przykładu podanego na wykładzie 12 dla $r_1=0.1$ i $r_2=0$. Dla jakich $\gamma$ strategia $\pi_1$:

    	0	1	2	3	4
    0	$\rightarrow$	$\rightarrow$	$\rightarrow$	$\rightarrow$	$\rightarrow$
    1	$\uparrow$	$\rightarrow$	$\uparrow$	$\rightarrow$	$\uparrow$
    2	$\uparrow$	$\rightarrow$	$\rightarrow$	$\rightarrow$	$\uparrow$
    3	$\uparrow$	$\rightarrow$	$\uparrow$	$\rightarrow$	$\downarrow$
    4	$\rightarrow$	$\rightarrow$	$\rightarrow$	$\rightarrow$	$\rightarrow$

    jest lepsza, niż strategia $\pi_2$:

    	0	1	2	3	4
    0	$\rightarrow$	$\rightarrow$	$\rightarrow$	$\rightarrow$	$\rightarrow$
    1	$\uparrow$	$\rightarrow$	$\uparrow$	$\rightarrow$	$\uparrow$
    2	$\downarrow$	$\rightarrow$	$\rightarrow$	$\rightarrow$	$\downarrow$
    3	$\downarrow$	$\rightarrow$	$\downarrow$	$\rightarrow$	$\downarrow$
    4	$\rightarrow$	$\rightarrow$	$\rightarrow$	$\rightarrow$	$\rightarrow$

29. Dla środowiska z poprzedniego ćwiczenia i $\gamma=0.9$ podać $V^*(x)$ i $Q^*(x,a)$ dla $x=00$ i $a=\downarrow$.
30. Zaproponować algorytm uczenia się ze wzmocnieniem, który uczy się $Q$-funkcji względem aktualnej strategii reprezentowanej za pomocą funkcji strategii $\mu$, jednocześnie modyfikowanej, podobnie jak w algorytmie AHC, i uzasadnić, dlaczego można mieć nadzieję na to (chociaż raczej trudno byłoby to udowodnić), że algorytm ten będzie uczyć się strategii optymalnej.
31. W trakcie wartościowania strategii za pomocą algorytmu TD$(\lambda)$ odwiedzono kolejno stany $x_0,x_1,\dots$, uzyskując odpowiednio nagrody $r_0,r_1,\dots$. Przyjmując, że wszystkie odwiedzone stany są różne, wyrazić sumę błędów, za pomocą których aktualizowana będzie wartość stanu $x_0$, w zależności (tylko) od $V(x_0)$ oraz $r_k$ i $V(x_{k+1})$ dla $k=0,1,\dots$ (tj. bez odwoływania się do śladów aktywności ani $\chi_x(k)$).
32. Rozważmy algorytm TD$(0)$ stosowany do wartościowania strategii. W kroku $t-1$ następuje aktualizacja wartości $V(x_{t-1})$ na podstawie wartości $V(x_t)$. Ale w kolejnym kroku $t$ z kolei wartość $V(x_t)$ jest aktualizowana i staje się przypuszczalnie dokładniejsza, można więc poprzednią aktualizację $V(x_{t-1})$ powtórzyć używając nowej wartości $V(x_t)$. Zaproponować oparty na tym pomyśle algorytm powtarzanego TD$(0)$, w którym po każdej ,,normalnej'' aktualizacji dla $V(x_t)$ w kroku $t$ wykonuje się ,,powtórzone'' aktualizacje kolejno dla $V(x_{t-1}),V(x_{t-2}),\dots,V(x_{t-n+1})$ dla $n>1$, czyli łącznie $n$ aktualizacji w każdym kroku. Czy taki algorytm może mieć jakieś zalety?
33. Dla algorytmu z poprzedniego ćwiczenia z $n=3$ podać ostateczną wartość $V(x_0)$ po przetworzeniu ciągu stanów $x_0,x_1,x_2$ i odpowiednich nagród $r_0,r_1,r_2$, przyjmując początkowo $V(x_0)=V(x_1)=V(x_2)=V(x_3)=0$ i tablicową reprezentację funkcji.
34. Rozważyć możliwość wykorzystania pewnej formy śladów aktywności do przyspieszenia uczenia się algorytmu brygady kubełkowej, biorąc pod uwagę jego podobieństwo do algorytmu TD$(0)$.
35. Które spośród omawianych na wszystkich wykładach algorytmów i do rozwiązania jakich problemów mogłyby się przydać konstruktorowi mobilnego robota?
36. Które spośród omawianych na wszystkich wykładach algorytmów i do rozwiązania jakich problemów mogłyby się przydać twórcy programu grającego w grę planszową?

About this document ...

Uczenie się maszyn: wykład 15
Ćwiczenia

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation wyklad15.tex

The translation was initiated by Pawel Cichosz on 2004-03-01