Uczenie się maszyn: wykład 1
Wprowadzenie

Paweł Cichosz

Date: Semestr zimowy 1997/98

Zawartość merytoryczna wykładu 1 jest dość ograniczona -- służy on przede wszystkiem wzajemnemu poznaniu się przez studentów i prowadzącego oraz daniu pewnego przybliżonego wybrażenia o tym, co czeka nas na kolejnych wykładach. W związku z tym niniejsze notatki mają charakter szczątkowy.

Sprawy organizacyjne

Część wykładu 1 poświęcona jest sprawom organizacyjnym -- tutaj wymienione są punkty programu.

1. Dane wykładowcy.
2. Lista studentów.
3. Zasady zaliczania: 2 kolokwia (40%), projekt (40%), praca domowa (15%), ogólny entuzjazm (5%).
4. Literatura.
5. Plan wykładów: dwie części.
6. Projekt: dwa warianty.
7. Strona WWW przedmiotu. Notatki do każdego wykładu.

Uczenie się i jego rodzaje

Definicja uczenia się

Proces poprawy jakości działania systemu według pewnego kryterium na podstawie doświadczeń z przeszłości. Doskonalenie zdolności do rozwiązywania pewnej klasy zadań na podstawie informacji uzyskanych na podstawie rozwiązania pewnej liczby zadań tej klasy. Zdobywanie wiedzy lub umiejętności, reprezentowanie jej wewnątrz systemu i stosowanie jej w wykonywaniu zadania.

Wiedza -- na ogół nie definiuje się lub definiuje się tylko w kontekście wybranej, specyficznej metody lub grupy metod uczenia się. Mówi się raczej o reprezentacji wiedzy.

Uczenie się a sztuczna inteligencja

Teoria i praktyka uczenia się maszyn -- głównie tzw. słaba AI.

Przykłady uczenia się

• Uczenie się (coraz lepszej) gry w warcaby.
• Uczenie się rozpoznawania chorób na podstawie symptomów.
• Uczenie się klasyfikowania tekstów do grup tematycznych na podstawie przykładów.
• Uczenie się aproksymowania nieznanej funkcji na podstawie próbek.
• Uczenie się kierowania samochodem na podstawie obserwacji i naśladowania instruktora.
• Uczenie się odnajdywania drogi w nieznanym środowisku.
• Uczenie się zależności funkcyjnych pomiędzy danymi obserwacyjnymi.

Wykład nie poda metody rozwiązania żadnego z tych problemów uczenia się, ale ukaże zestaw algorytmów, które odpowiednio rozszerzone i połączone z innymi algorytmami mogą być w tego typu problemach pomocne.

Motywacja dla uczenia się

• Dla naprawdę złożonych zadań trudno jest sformułować wprost gotowe programy dla ich rozwiązywania.
• Często zbiory dostępnych danych są zbyt duże i skomplikowane, aby można było wyszukiwać w nich zależności, klasyfikować obiekty itd. w sposób niezautomatyzowany.
• Złożone środowiska są trudne do opisu, często nie posiadają wystarczających modeli teoretycznych albo ich uzyskanie jest bardzo kosztowne.
• ,,Ręcznie'' zakodowane programy dla takich środowisk, nawet gdyby udało się je stworzyć, byłyby mało wiarygodne.
• Inteligentne systemy powinny być w maksymalnym stopniu autonomiczne, czyli zdolne do działania bez (zbyt dużej) ingerencji człowieka, co nie jest możliwe bez adaptacyjności, zdolności do przystosowywania się do zmieniających się środowisk i wymagań.

Taksonomia metod uczenia się

1. Wiedza deklaratywna a proceduralna (wiedza a umiejętność), ich zależności.
2. Sposób nabywania wiedzy: bezpośrednia implantacja, przez obserwację i odkrywanie (bez nadzoru), na podstawie przykładów (z nadzorem), uczenie się na podstawie zapytań, uczenie się ze wzmocnieniem.
3. Reprezentacja wiedzy: reguły, drzewa decyzyjne, klauzule logiki predykatów, grupowania (taksonomie), rozkłady prawdopodobieństwa, reprezentacje parametryczne, funkcje przejść automatów.

Główne działy

Główne działy uczenia się maszyn odzwierciedla plan wykładów. Brakuje ILP i paru bardziej szczegółowych zagadnień (uczenie się przez analogię, CBR, modele HMM). Pominięto sieci neuronowe, które są samodzielną dziedziną.

Terminologia i notacja dla indukcyjnego uczenia się

Ponieważ przez mniej więcej połowę semestru zajmować się będziemy teorią (krótko) oraz (znacznie dłużej) różnymi metodami indukcyjnego uczenia się pojęć na podstawie przykładów, poniżej znajduje się wykaz terminów i konwencji notacyjnych, jakie będą przy tym wykorzystywane. Po drodze na pewno trochę do tej listy trzeba będzie dodać.

• Dziedzina $X$: zbiór z którego mogą pochodzić przykłady.
• Przykład $x\in X$: pojedynczy element dziedziny.
• Atrybut: dowolna funkcja $a:X\mapsto A$. Przyjmuje się, że każdy przykład $x\in X$ opisany jest przez $n$ atrybutów $a_i:X\mapsto A_i$, $i=1,\dots,n$. Zbiór wartości atrybutów $a_1(x),\dots,a_n(x)$ stanowi pełny opis przykładu $x$.
• Typy atrybutów: nominalne (dyskretne bez relacji porządku), porządkowe (dyskretne z relacją porządku), ciągłe.
• Pojęcie (docelowe): pewna funkcja $c:X\mapsto\{0,1\}$. Równoważne alternatywne sformułowanie: podzbiór $X_c\subseteq X$. Czasem w praktyce uwzględnia się pojęcie wielokrotne: funkcja $c:X\mapsto C$, $\vert C\vert>2$. Wartość $c(x)$ nazywa się etykietą, klasą lub kategorią przykładu $x$.
• Przestrzeń (klasa) pojęć  $\mathbb{C}$: zbiór wszystkich pojęć dla danej dziedziny $X$. Przyjmując definicję pojęcia jako podzbioru mamy dla skończonej dziedziny $\mathbb{C}\subseteq 2^X$.
• Hipoteza: funkcja $h:X\mapsto\{0,1\}$, która jest konstruowanym przez ucznia przybliżeniem pojęcia docelowego $c$. W przypadku uczenia się pojęć wielokrotnych definicja odpowiednio się zmienia.
• Przestrzeń (klasa) hipotez  $\mathbb{H}$: zbiór wszystkich hipotez, które uczeń może skonstruować (zbiór ten zależy od sposobu reprezentacji hipotez przez ucznia i algorytmu uczenia się). Najlepiej jeśli $\mathbb{C}\subseteq\mathbb{H}$: wtedy mamy gwarancję, że $c\in\mathbb{H}$, czyli że uczeń może nauczyć się pojęcia docelowego. Niestety, w praktyce często $\mathbb{H}\subset\mathbb{C}$.
• Przykład etykietowany pojęcia $c$: para $\langle x,c(x)\rangle$, $x\in X$.
• Przykład negatywny pojęcia $c$: $x\in X$, $c(x)=0$.
• Przykład pozytywny pojęcia $c$: $x\in X$, $c(x)=1$.
• Klasa (kategoria) przykładów z dziedziny $x$: $C^i_c=\{x\in X\;\vert\;c(x)=i\}$.
• Zbiór trenujący dla uczenia się z nadzorem pojęcia $c$: $T_c=\{\langle x,c(x)\rangle\;\vert\;x\in T\subseteq X\}$. Dla prostoty, jeśli wiadomo o jakie pojęcie docelowe chodzi, czasem mówi się o $T$ jako o zbiorze trenującym, rozumiejąc, że etykiety są także dane.
• Zbiór trenujący dla uczenia się bez nadzoru: $T\subseteq X$.
• Błąd próbki hipotezy $h$ względem pojęcia $c$ dla zbioru przykładów $D$:
  $$e^c_D(h) = \frac{\sum_{x\in D}\delta(h(x),c(x))}{\vert D\vert},$$
  gdzie $\delta(h(x),c(x))$ ma wartość $1$ gdy $h(x)\neq c(x)$ i 0 gdy $h(x)=c(x)$.
• Reczywisty błąd hipotezy $h$ względem pojęcia $c$ dla rozkładu prawdopodobieństwa $\Omega$ na $X$:
  $$e^c_{\Omega}(h) = \mathrm{Pr}_{x\in\Omega}(h(x)\neq c(x)).$$
  Metody statystyczne pozwalają oszacować błąd rzeczywisty na podstawie błędu próbki.
• Problem indukcyjnego uczenia się z nadzorem: mając dany zbiór trenujący $T_c$ znaleźć hipotezę $h\in\mathbb{H}$, która jest najlepszym przybliżeniem pojęcia docelowego $c$ według pewnego kryterium. Kryterium to na ogół uwzględnia błąd próbki, ale nie ogranicza się do niego. W przypadku idealnym $(\forall x\in X)h(x)=c(x)$.
• Problem indukcyjnego uczenia się bez nadzoru: mając dany zbiór trenujący $T$ znaleźć hipotezę $h\in\mathbb{H}$, która daje najlepszą klasyfikację przykładów według pewnego kryterium.
• Indukcyjne obciążenie (inductive bias): preferencje ucznia do wyboru określonych hipotez, zespół wszystkich czynników, które w połączeniu ze zbiorem trenującym determinują (w sensie konsekwencji logicznej) wybór konkretnej hipotezy.
• Założenie indukcji: hipoteza wybrana jako najlepsza dla dostatecznie dużego zbioru trenującego jest dobra dla całej dziedziny.

Perspektywa filozoficzna

Problemy wiedzy i możliwości jej pozyskiwania zajmowały filozofów prawie od początku dziejów filozofii Zachodu. Poniżej wymieniam najbardziej znanych myślicieli, których myśl w jakiś sposób wydaje się z tymi problemami wiązać. Podsumowanie dorobku tych wybitnych postaci za pomocą jednego hasłowego zdania należy traktować ze sporym przymrużeniem oka (to jak kurs historii filozofii w 10 minut).

Sokrates:

uczenie się utożsamione z przypominaniem sobie wiedzy wrodzonej (anamneza). Pewne pokrewieństwo z uczeniem się na podstawie wyjaśnień, które polega na przetwarzaniu wiedzy wrodzonej do dogodnej postaci pod wpływem obserwowanych przykładów.

Platon:

realnie istniejące idee (pojęcia). Uczenie się nie polega na tworzeniu pojęć, lecz odkrywaniu (a właściwie przypominaniu sobie) istniejących odwiecznie pojęć.

Arystoteles:

istnieją tylko rzeczy jednostkowe, pojęcia ogólne powstają na drodze abstrakcji. Nie są one jednak arbitralne i pozbawione znaczenia, gdyż to co ogólne (wspólne) w rzeczach zawiera ich forma. Rozróżnienie dedukcji i indukcji.

Augustyn:

idee istnieją jako myśli Boga, który według nich stworzył rzeczy.

Abelard:

rozstrzygnięcie sporu o uniwersalia według którego nie istnieją one realnie, ale mają podstawę we wspólnej formie rzeczy obejmowanych przez nie.

Tomasz:

uniwersalia ante rem, in re, post rem.

Ockham:

brzytwa Ockhama wzywająca do tłumaczenia świata za pomocą najprostszych hipotez. Nominalizm (pojęcia ogólne to tylko część języka).

Kartezjusz:

idee wrodzone.

Hume:

empiryzm, idee proste powstają na podstawie wrażeń, idee złożone są ich konstrukcjami. Idee ogólne powstają przez połączenie idei konkretnych. Krytyka zasady przyczynowości, która w konsekwencji podważa prawomocość indukcji (ale akceptacja dla posługiwania się nią w praktyce).

Kant:

aprioryczne formy zmysłowości (czas, przestrzeń) i kategorie rozumu (m.in. substancja i przyczynowość) kształtują poznanie. Z perspektywy indukcyjnego uczenia się maszyn można na to patrzeć jako na bias, czyli czynnik determinujący wybór przez ucznia określonej hipotezy na podstawie dostępnych danych.

Mill:

kanony indukcji (zgodności, różnicy, reszt, zmian towarzyszących). Raczej chybione z punktu widzenia metodologii nauk przyrodniczych, lecz bliskie uczeniu się maszyn.

Avenarius:

zasada ekonomii myślenia wzywająca do konstrukcji pojęć i praw, które opisują świat w najprostszy sposób.

James:

pragmatyzm utożsamiający prawdę z długoterminową użytecznością (truth = cash value), co odpowiada w pewnym sensie założeniom uczenia się ze wzmocnieniem.

Koło wiedeńskie (m.im. Schlick, Carnap, Neurath):

zdania protokolarne jako podstawa wiedzy, weryfikowalność jako kryterium sensowności.

Russell:

podstawy współczesnej logiki matematycznej (także Frege, Whitehead). Odróżnienie formy gramatycznej zdań od ich formy logicznej.

Wittgenstein:

zwrócenie uwagi na rolę języka, który wyznacza granice myśleniu (język reprezentacji hipotez określa, czego można się nauczyć). Język logiki jako język uniwersalny (w pierwszym okresie). Względność i równoprawność języków (w drugim okresie).

Carnap:

problemy indukcji i prawdopodobieństwa wiedzy z niej pochodzącej.

Popper:

antyindukcjonizm w metodologii nauk, poznanie przez proponowanie śmiałych falsyfikowalnych hipotez i ich testowanie.

Literatura do wykładu

Książka Mitchella wymieniona jako pierwsza pozycja poniższego wykazu stanowi najlepsze źródło przystępnych informacji do sporej części (ale nie całości) materiału przedmiotu. Jednak wykład ani udostępniane notatki nie są bezpośrednio oparte na tej książce i pewne zagadnienia mogą być przedstawiane nieco inaczej. Podaną na drugim miejscu polską książeczkę polecam dlatego, że jest tam mowa o kilku interesujących nas zagadnieniach i jest ona raczej łatwo dostępna w bibliotekach, ale poziom merytoryczny i jakość prezentacji pozostawia pewne uczucie niedosytu. Pozycje z zakresu filozofii cytuję w większości z pamięci i nie ręczę za poprawność.

1. Mitchell, T. M. Machine Learning, McGraw-Hill, 1997.
2. Bolc, L., Zaremba, J. Wprowadzenie do uczenia się maszyn. Akademicka Oficyna Wydawnicza RM, 1992.
3. Carbonell, J. G., Michalski, R. S., Mitchell, T. M. An overview of machine learning. W: Michalski, R. S., Carbonell, J. G., Mitchell, T. M. (eds.), Machine Learning: An Artificial Intelligence Approach, Volume 1, Tioga (obecnie Morgan Kaufmann), 1983.
4. Tatarkiewicz, W. Historia filozofii. PWN, 1997.
5. Russell, B. Mądrość Zachodu. Penta, 1995.
6. Bocheński, J. M. Zarys historii filozofii. Philed, 1993.
7. Bocheński, J. M. Współczesne metody myślenia. W drodze, 1993.

About this document ...

Uczenie się maszyn: wykład 1
Wprowadzenie

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 wyklad1.tex

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