Systemy uczące się

Książka jest poświęcona metodom konstruowania uczących się programów komputerowych, zdolnych do poprawy swego działania na podstawie doświadczeń z przeszłości. Programy tego typu w zautomatyzowany sposób zdobywają wiedzę, którą wykorzystują do realizacji postawionych przed nimi zadań.
Autor przybliża czytelnikowi proces uczenia się systemów z algorytmicznego punktu widzenia. Wyjaśnia, na czym polega indukcyjne uczenie się. Przedstawia dwa główne podejścia do tego zagadnienia: indukcję drzew decyzyjnych i indukcję reguł decyzyjnych. Omawia probabilistyczne metody uczenia się, a także metody grupowania pojęciowego. Zajmuje się problemami przekształcania zbioru atrybutów. Przedstawia wybrane algorytmy uczenia się aproksymacji funkcji. Opisuje odkrywanie zależności w danych i uczenia się automatów i problem uczenia się systemów ze wzmocnieniem.
Wartość merytoryczną książki podnoszą liczne ćwiczenia, podzielone na tradycyjne, laboratoryjne i projektowe.

W Internecie, pod adresem http://www.ise.pw.edu.pl/~cichosz/SU , czytelnik znajdzie zbiór programów w języku Common Lisp, stanowiących implementację niektórych omówionych w książce algorytmów. Będzie mógł także skorzystać z odnośników do innych dostępnych w Sieci materiałów na temat systemów uczących się.

Spis treści

Przedmowa
Podziękowania
Wykaz ważniejszych oznaczeń

1 Uczenie się w ujęciu algorytmicznym

1.1 Znaczenie uczenia się
1.1.1 Definicja uczenia się
1.1.2 Programy uczące się
1.1.3 Przykłady maszynowego uczenia się
1.1.4 Motywacja do uczenia się
1.2 Rodzaje uczenia się
1.2.1 Taksonomia maszynowego uczenia się
1.2.2 Główne działy maszynowego uczenia się
1.3 Nauka o uczeniu się
1.3.1 Trzy nurty
1.3.2 Dziedziny pokrewne
1.4 Uczenie się w sztucznej inteligencji
1.4.1 Słaba i silna sztuczna inteligencja
1.4.2 Główne działy sztucznej inteligencji
1.4.3 Uczenie się wiedzy do wnioskowania
1.4.4 Uczenie się heurystyk
1.5 Uczenie się jako wnioskowanie
1.5.1 Typy wnioskowania
1.5.2 Transmutacje wiedzy
1.5.3 Uczenie się jako przeszukiwanie
1.6 Zastosowania systemów uczących się
1.7 Perspektywa filozoficzna
1.8 Podsumowanie
1.9 Uwagi historyczne i bibliograficzne
1.10 Ćwiczenia

2 Uczenie się indukcyjne

2.1 Wnioskowanie indukcyjne
2.2 Główne rodzaje indukcyjnego uczenia się
2.2.1 Uczenie się pojęć
2.2.2 Tworzenie pojęć
2.2.3 Uczenie się aproksymacji funkcji
2.2.4 Tryby uczenia się
2.2.5 Obciążenie indukcyjne
2.2.6 Inne odmiany indukcyjnego uczenia się
2.3 Algorytmiczna teoria indukcji
2.3.1 Szacowanie błędów hipotez
2.3.2 Model PAC
2.3.3 PAC-nauczalność
2.3.4 Wymagania dotyczące liczby przykładów
2.3.5 Wymiar Vapnika-Chervonenkisa
2.3.6 Brzytwa Ockhama
2.3.7 Model ograniczania liczby pomyłek
2.4 Uczenie się przestrzeni wersji
2.4.1 Częściowy porządek hipotez
2.4.2 Reprezentacja hipotez przez kompleksy
2.4.3 Reprezentacja przestrzeni wersji
2.4.4 Algorytm eliminacji kandydatów
2.4.5 Stosowanie przestrzeni wersji
2.4.6 Dobór przykładów trenujących
2.4.7 Obciążenie algorytmu CAE
2.5 Zagadnienia praktyczne
2.6 Zagadnienia implementacyjne
2.6.1 Reprezentacja informacji o atrybutach
2.6.2 Reprezentacja przykładów
2.7 Podsumowanie
2.8 Uwagi historyczne i bibliograficzne
2.9 Ćwiczenia

3 Indukcja drzew decyzyjnych

3.1 Drzewa decyzyjne jako hipotezy
3.1.1 Struktura drzewa
3.1.2 Notacja dla drzew decyzyjnych
3.1.3 Zalety i ograniczenia drzew decyzyjnych
3.2 Zstępujące konstruowanie drzewa
3.2.1 Kryterium stopu i ustalenie etykiety
3.2.2 Rodzaje testów
3.2.3 Kryterium wyboru testu
3.2.4 Kandydujące testy
3.3 Przycinanie drzewa
3.3.1 Schemat przycinania
3.3.2 Kryteria przycinania
3.3.3 Liście probabilistyczne
3.4 Złożoność obliczeniowa
3.5 Zagadnienia praktyczne
3.5.1 Duże zbiory przykładów
3.5.2 Atrybuty o wielu wartościach
3.5.3 Brakujące wartości atrybutów
3.5.4 Inkrementacyjne konstruowanie drzewa
3.6 Zagadnienia implementacyjne
3.6.1 Reprezentacja drzewa
3.6.2 Rekurencja
3.6.3 Przekazywanie argumentów
3.6.4 Ocena testów nierównościowych
3.7 Podsumowanie
3.8 Uwagi historyczne i bibliograficzne
3.9 Ćwiczenia

4 Indukcja reguł

4.1 Zbiory reguł jako hipotezy
4.1.1 Logiczne podstawy reprezentacji regułowej
4.1.2 Reprezentacja warunków
4.1.3 Zbiory reguł
4.1.4 Złożoność hipotez
4.2 Sekwencyjne pokrywanie
4.3 Algorytm AQ
4.3.1 Strategia przeszukiwania
4.3.2 Specjalizacja gwiazdy
4.3.3 Ocena kompleksów
4.3.4 Wybór ziaren
4.3.5 Wybór kategorii
4.4 Algorytm CN2
4.4.1 Strategia przeszukiwania
4.4.2 Ocena kompleksów
4.4.3 Wybór kategorii
4.5 Przycinanie zbiorów reguł
4.5.1 Schemat przycinania
4.5.2 Kryteria przycinania
4.6 Złożoność obliczeniowa
4.7 Zagadnienia praktyczne
4.7.1 Niepoprawne dane trenujące
4.7.2 Efektywna specjalizacja
4.7.3 Atrybuty porządkowe i ciągłe
4.7.4 Brakujące wartości atrybutów
4.7.5 Inkrementacyjna indukcja reguł
4.8 Zagadnienia implementacyjne
4.8.1 Reprezentacja kompleksów
4.8.2 Reprezentacja zbiorów kompleksów
4.9 Podsumowanie
4.10 Uwagi historyczne i bibliograficzne
4.11 Ćwiczenia

5 Metody probabilistyczne

5.1 Prawdopodobieństwo w sztucznej inteligencji
5.2 Twierdzenie Bayesa
5.3 Klasyfikacja bayesowska
5.3.1 Wybór hipotezy
5.3.2 Prawdopodobieństwo danych
5.3.3 Optymalny klasyfikator bayesowski
5.3.4 Klasyfikacja bayesowska w praktyce
5.3.5 Naiwny klasyfikator bayesowski
5.4 Sieci bayesowskie
5.4.1 Terminologia
5.4. Struktura i semantyka sieci
5.4.3 Wnioskowanie w sieciach bayesowskich
5.4.4 Indukcja sieci bayesowskich
5.5 Zasada minimalnej długości kodu
5.5.1 Prawdopodobieństwo a długość kodu
5.5.2 Indukcja jako kompresja danych
5.5.3 Kodowanie
5.5.4 Kodowanie danych
5.5.5 Stosowanie zasady minimalnej długości kodu
5.6 Zagadnienia praktyczne
5.6.1 Prawdopodobieństwa a priori
5.6.2 Atrybuty ciągłe
5.7 Zagadnienia implementacyjne
5.8 Podsumowanie
5.9 Uwagi historyczne i bibliograficzne
5.10 Ćwiczenia

6 Grupowanie pojęciowe

6.1 Grupowanie jako wiedza
6.1.1 Grupowanie według podobieństwa
6.1.2 Od grupowania do pojęć
6.2 Grupowanie za pomocą pokryć
6.2.1 Kompleksy jako reprezentacja grupowania
6.2.2 Wyznaczanie kompleksów opisujących kategorie
6.2.3 Ocena jakości grupowania
6.2.4 Liczba kategorii
6.2.5 Klasyfikowanie przykładów
6.3 Grupowanie probabilistyczne
6.3.1 Grupowanie pojęciowe jako przeszukiwanie
6.3.2 Funkcja oceny grupowania
6.3.3 Reprezentacja grupowania
6.3.4 Operatory
6.3.5 Strategia sterowania
6.3.6 Klasyfikowanie przykładów
6.4 Grupowanie z atrybutami ciągłymi
6.4.1 Algorytm CLUSTER/2 i atrybuty ciągłe
6.4.2 Algorytm COBWEB i atrybuty ciągłe
6.4.3 Grupowanie wyłącznie z atrybutami ciągłymi
6.5 Grupowanie jako kompresja danych
6.5.1 Kodowanie hipotez
6.5.2 Kodowanie danych
6.6 Zagadnienia praktyczne
6.6.1 Grupowanie w uczeniu się z nadzorem
6.6.2 Duże zbiory danych
6.7 Zagadnienia implementacyjne
6.8 Podsumowanie
6.9 Uwagi historyczne i bibliograficzne
6.10 Ćwiczenia

7 Przekształcanie atrybutów

7.1 Przestrzeń atrybutów a przestrzeń hipotez
7.1.1 Informacyjna zawartość atrybutów
7.1.2 Rola atrybutów w grupowaniu
7.1.3 Atrybuty a reprezentacja
7.1.4 Rodzaje przekształceń
7.2 Dyskretyzacja atrybutów ciągłych
7.2.1 Dyskretyzacja a agregacja atrybutów porządkowych
7.2.2 Korzyści z dyskretyzacji
7.2.3 Rodzaje dyskretyzacji
7.2.4 Przedziały i wartości progowe
7.2.5 Prymitywne metody dyskretyzacji
7.2.6 Dyskretyzacja zstępująca
7.2.7 Dyskretyzacja wstępująca
7.2.8 Dyskretyzacja jako kompresja danych
7.2.9 Dyskretyzacja bez nadzoru
7.2.10 Agregacja atrybutów porządkowych
7.3 Konstruktywna indukcja
7.3.1 Rodzaje konstruktywnej indukcji
7.3.2 Konstruktywna indukcja na podstawie danych
7.3.3 Konstruktywna indukcja na podstawie hipotez
7.4 Zagadnienia praktyczne
7.4.1 Celowość dyskretyzacji
7.4.2 Wybór metody dyskretyzacji
7.4.3 Liczba przedziałów dyskretyzacji
7.4.4 Atrybuty o nieznanej przeciwdziedzinie
7.4.5 Stosowanie konstruktywnej indukcji
7.5 Zagadnienia implementacyjne
7.5.1 Implementacja dyskretyzacji zstępującej
7.5.2 Implementacja dyskretyzacji wstępującej
7.6 Podsumowanie
7.7 Uwagi historyczne i bibliograficzne
7.8 Ćwiczenia

8 Uczenie się aproksymacji funkcji

8.1 Zadanie aproksymacji
8.1.1 Cechy przykładów
8.1.2 Aproksymowane odwzorowanie
8.1.3 Ocena hipotez
8.1.4 Tryby i szybkość uczenia się
8.1.5 Informacja trenująca
8.2 Rodzaje aproksymatorów
8.3 Metody parametryczne
8.3.1 Obliczanie wartości funkcji
8.3.2 Aktualizacja wartości funkcji
8.3.3 Aproksymator liniowy
8.3.4 Aproksymatory nieliniowe
8.3.5 Metody wykładniczo-gradientowe
8.3.6 Regresja
8.3.7 Atrybuty dyskretne
8.4 Rozszerzona reprezentacja
8.4.1 Rozszerzanie opisu przykładów
8.4.2 Reprezentacja randomizowana
8.4.3 Rozproszone przybliżone kodowanie
8.5 Metody pamięciowe
8.5.1 Pamięć i jej stosowanie
8.5.2 Najbliższy sąsiad
8.5.3 Lokalne średnie ważone
8.5.4 Lokalna regresja
8.6 Metody symboliczne
8.6.1 Hipotezy modelowania
8.6.2 Drzewa modelowania
8.7 Zagadnienia praktyczne
8.7.1 Dobór rozmiaru kroku
8.7.2 CMAC i nieograniczone przeciwdziedziny cech
8.7.3 Mieszane przestrzenie atrybutów
8.7.4 Ograniczona pamięć w metodach pamięciowych
8.8 Zagadnienia implementacyjne
8.8.1 Wagi w rozproszonych przybliżonych tablicach
8.8.2 Zapamiętywanie przykładów
8.9 Podsumowanie
8.10 Uwagi historyczne i bibliograficzne
8.11 Ćwiczenia

9 Indukcyjne programowanie logiczne

9.1 Reprezentacja wiedzy w rachunku predykatów
9.2 Uczenie się pojęć w rachunku predykatów
9.3 Sekwencyjne pokrywanie dla predykatów
9.3.1 Podstawowy schemat
9.3.2 Generowanie koniunkcji
9.3.3 Lokalne zbiory trenujące
9.3.4 Kryterium stopu
9.3.5 Wybór literałów
9.4 Odwracanie dedukcji
9.4.1 Wnioskowanie za pomocą zasady rezolucji
9.4.2 Odwrócona rezolucja
9.4.3 Uczenie się za pomocą odwróconej rezolucji
9.5 Zagadnienia praktyczne
9.5.1 Unikanie nadmiernego dopasowania
9.5.2 Niepoprawne dane trenujące
9.5.3 Pojęcia zdaniowe
9.6 Zagadnienia implementacyjne
9.6.1 Reprezentacja klauzul
9.6.2 Reprezentacja literałów
9.7 Podsumowanie
9.8 Uwagi historyczne i bibliograficzne
9.9 Ćwiczenia

10 Dokonywanie odkryć

10.1 Wiedza a dane
10.1.1 Zależności w danych jako wiedza
10.1.2 Zależności w relacyjnych bazach danych
10.1.3 Uczenie się jako odkrywanie wiedzy
10.2 Stosowanie algorytmów uczenia się
10.2.1 Duże zbiory danych
10.2.2 Liczne atrybuty
10.2.3 Liczne kategorie
10.2.4 Nierównomierny rozkład kategorii
10.2.5 Inkrementacyjna aktualizacja
10.2.6 Niekompletne dane
10.2.7 Niepoprawne dane
10.2.8 Metauczenie się
10.3 Odkrywanie asocjacji
10.3.1 Reguły asocjacyjne
10.3.2 Tablice kontyngencji
10.3.3 Wzorce w tablicach kontyngencji
10.3.4 Od wzorców do reguł asocjacyjnych
10.3.5 Poszukiwanie wzorców
10.3.6 Reguły asocjacyjne dla wielu atrybutów
10.4 Odkrywanie równań
10.4.1 Terminologia i notacja dla równań
10.4.2 Równania z dwiema zmiennymi
10.4.3 Równania z wieloma zmiennymi
10.5 Zagadnienia praktyczne
10.6 Zagadnienia implementacyjne
10.6.1 Struktury danych dla dużych zbiorów trenujących
10.7 Podsumowanie
10.8 Uwagi historyczne i bibliograficzne
10.9 Ćwiczenia

11 Uczenie się przez wyjaśnianie

11.1 Wiedza wrodzona w uczeniu się
11.1.1 Wykorzystanie wiedzy wrodzonej w indukcji
11.1.2 Uczenie się jako kompilacja wiedzy wrodzonej
11.1.3 Obciążenie w uczeniu się przez wyjaśnianie
11.2 Generalizacja na podstawie wyjaśnień
11.2.1 Sformułowanie zadania
11.2.2 Algorytm EBG
11.3 Usprawnianie rozwiązywania problemów
11.3.1 Rozwiązywanie problemów w sztucznej inteligencji
11.3.2 Rozwiązywanie problemów a planowanie
11.3.3 Uczenie się rozwiązywania problemów
11.4 Łączenie wyjaśniania i indukcji
11.4.1 Integracja indukcji i dedukcji
11.4.2 Dedukcyjna specjalizacja
11.5 Zagadnienia praktyczne
11.5.1 Niedoskonała teoria
11.5.2 Niepoprawne przykłady
11.5.3 Przykłady negatywne
11.6 Zagadnienia implementacyjne
11.7 Podsumowanie
11.8 Uwagi historyczne i bibliograficzne
11.9 Ćwiczenia

12 Uczenie się automatów

12.1 Automat jako model języka i środowiska
12.1.1 Automaty skończone
12.1.2 Perspektywa lingwistyczna
12.1.3 Perspektywa identyfikacji
12.1.4 Zadanie uczenia się automatów
12.2 Uczenie się na podstawie zapytań
12.2.1 Zapytania i odpowiedzi
12.2.2 Algorytm L*
12.2.3 Osłabianie informacji trenującej
12.3 Uczenie się na podstawie eksperymentów
12.3.1 Algorytmy sekwencji sprowadzających
12.3.2 Algorytm równoważności testów
12.4 Zagadnienia praktyczne
12.4.1 Niedeterminizm automatu docelowego
12.4.2 Usprawnianie testowania równoważności
12.5 Zagadnienia implementacyjne
12.5.1 Reprezentacja tablicy obserwacji
12.5.2 Reprezentacja zbiorów testów
12.6 Podsumowanie
12.7 Uwagi historyczne i bibliograficzne
12.8 Ćwiczenia

13 Uczenie się ze wzmocnieniem

13.1 Zadanie uczenia się ze wzmocnieniem
13.1.1 Uczenie się z wartościującym sprzężeniem zwrotnym
13.1.2 Scenariusz
13.1.3 Środowisko
13.1.4 Zadanie ucznia
13.1.5 Zadania epizodyczne
13.1.6 Tryby uczenia się
13.1.7 Specyfika uczenia się ze wzmocnieniem
13.2 Procesy decyzyjne Markowa
13.2.1 Własność Markowa
13.2.2 Strategie i funkcje wartości
13.2.3 Optymalność strategii
13.2.4 Problemy Markowa a uczenie się ze wzmocnieniem
13.3 Programowanie dynamiczne
13.3.1 Równania Bellmana
13.3.2 Wartościowanie strategii
13.3.3 Wyznaczanie strategii optymalnej
13.3.4 Programowanie dynamiczne a uczenie się
13.4 Uczenie się funkcji wartości
13.4.1 Algorytm TD
13.4.2 Zbieżność
13.5 Uczenie się strategii
13.5.1 Algorytm AHC
13.5.2 Algorytm Q-learning
13.5.3 Algorytm Sarsa
13.6 Wybór akcji
13.6.1 Strategie probabilistyczne
13.6.2 Strategie licznikowe
13.7 Reprezentacja funkcji
13.8 Przyspieszanie uczenia się: TD(? > 0)
13.8.1 Ślady aktywności
13.8.2 Dochody TD(?)
13.8.3 Uczenie się strategii
13.8.4 Rola i dobór ?
13.9 Uczenie się rozwiązywania problemów
13.9.1 Problem jako środowisko
13.9.2 Rozwiązanie jako strategia
13.9.3 Funkcja wartości jako heurystyka
13.10 Zagadnienia praktyczne
13.10.1 Ukryty stan
13.10.2 Aktywna percepcja
13.10.3 Uczenie się i planowanie
13.10.4 Hierarchiczne uczenie się
13.10.5 Wiedza wrodzona
13.11 Zagadnienia implementacyjne
13.11.1 Efektywne ślady aktywności
13.11.2 Eliminacja śladów aktywności
13.12 Podsumowanie
13.13 Uwagi historyczne i bibliograficzne
13.14 Ćwiczenia

14 Zakończenie

14.1 Od algorytmów do systemów
14.1.1 Etapy konstruowania systemu
14.2 Lista nieobecności
14.2.1 Sieci neuronowe
14.2.2 Algorytmy ewolucyjne
14.2.3 Zagadnienia szczegółowe
14.3 Kierunki badań
14.3.1 Wyzwania teoretyczne
14.3.2 Wyzwania koncepcyjne
14.3.3 Wyzwania praktyczne
14.4 Słowo końcowe
14.5 Podsumowanie
14.6 Uwagi historyczne i bibliograficzne
14.7 Ćwiczenia

A. Rozwiązania i wskazówki do ćwiczeń
A.1 Rozdział 1
A.2 Rozdział 2
A.3 Rozdział 3
A.4 Rozdział 4
A.5 Rozdział 5
A.6 Rozdział 6
A.7 Rozdział 7
A.8 Rozdział 8
A.9 Rozdział 9
A.10 Rozdział 10
A.11 Rozdział 11
A.12 Rozdział 12
A.13 Rozdział 13
A.14 Rozdział 14

B Podstawy teorii prawdopodobieństwa
B.1 Zdarzenia
B.2 Aksjomaty prawdopodobieństwa
B.3 Prawdopodobieństwo warunkowe
B.4 Zmienne losowe
B.4.1 Zmienne losowe dyskretne
B.4.2 Zmienne losowe ciągłe
B.5 Ważniejsze rozkłady prawdopodobieństwa

C Podstawy logiki predykatów
C.1 Składnia języka predykatów
C.2 Semantyka języka predykatów
C.3 Wnioskowanie w rachunku predykatów
C.4 Rachunek predykatów w uczeniu się

D Internetowa strona książki

Literatura
Skorowidz