Uczenie maszynowe (nucchine learning) obejmuje problematykę konstruowania programów komputerowych potrafiących pozyskiwać, na podstawie wprowadzonej informacji, nową wiedzę lub poprawiać wiedzę już posiadaną (Michalewicz 1996). W ostatnich latach zaobserwować można szczególnie intensywny rozwój tej dziedziny i to zarówno w sferze badań podstawowych, jak i zastosowań. Algorytmy uczenia maszynowego są podstawowymi metodami inżynierii wiedzy, systemów doradczych, eksploracji danych, inteligentnych systemów wyszukiwania i filtrowania informacji, przetwarzania obrazów i języka naturalnego, robotyki, a od niedawna również bioinformatyki. Jako dziedzina interdyscyplinarna uczenie maszynowe opiera się na koncepcjach i rezultatach m.in. statystyki, sztucznej inteligencji, filozofii; teorii informacji, biologii, psychologii, teorii decyzji, teorii złożoności obliczeniowej oraz informatyki.
Jedną z żywo rozwijających się metod uczenia maszynowego jest wnioskowanie gramatyczne (grammar induction), które podejmuje problematykę uczenia języka (a precyzyjniej gramatyki lub równoważnego automatu) na podstawie przykładowych zdań. Od algorytmu uczącego oczekuje się generalizacji polegającej na umiejętności generacji i akceptacji zdań wychodzących poza zbiór uczący. Problem indukcji gramatyki jest zdefiniowany przez:
?    klasę indukowanego języka,
? dostępność danych uczących, które mogą należeć do języka (przykłady pozytywne), do języka nie należą (przykłady negatywne) lub też dostarczają dodatkowych informacji,
?    wreszcie przez rozmiar danych uczących.
Zgodnie z twierdzeniem Golda (1967) niemożliwa jest indukcja dowolnego języka z hierarchii Chomsky'ego jedynie na podstawie przykładów poprawnych, a uzupełnienie zbioru uczącego o zdania negatywne pozwoliło dotychczas na znalezienie efektywnych, tj. działających w czasie wielomianowym; algorytmów uczących jedynie dla wyrażeń regularnych i równoważnych im automatów skończonych (deterministic finite automaton, DFA).

Wstęp

1. Wnioskowanie gramatyczne
1.1. Wprowadzenie
1.2. Obszary zastosowań
1.3. Wybrane pojęcia z teorii automatów i języków
1.4. Paradygmaty uczenia
1.4.1. Identyfikacja w granicy
1.4.2. Model PAC
1.4.3. Minimalna długość kodu
1.4.4. Uczenie się na podstawie zapytań
1.5. Indukcja gramatyk bezkontekstowych
1.5.1. Indukcja na podstawie tekstu
1.5.2. Indukcja z danych strukturalnych
1.5.3. Indukcja podklas gramatyk bezkontekstowych
1.5.4. Indukcja alternatywnych reprezentacji gramatyk bezkontekstowych
1.5.5. Indukcja stochastycznych gramatyk bez kontekstowych
1.5.6. Indukcja z zastosowaniem metod sztucznej inteligencji
1.5.7. Algorytm CYK

2. Metody ewolucyjne
2.1. Programowanie ewolucyjne
2.2. Strategie ewolucyjne
2.3. Algorytmy genetyczne
2.4. Programowanie genetyczne

3. Uczący się system klasyfikujący
3.1. Architektura
3.2. Klasyfikacja
3.2.1. Kryterium zasięgu chromosomu
3.2.2. Kryterium miary użyteczności klasyfikatora
3.2.3. Kryterium metody reprezentacji klasyfikatora
3.2.4. Kryterium mechanizmu stosowanego w module odkrywczym
3.2.5. Kryterium pamięci systemu
3.3. Wybrane modele
3.3.1. LCS
3.3.2. ZCS
3.3.3. XCS
3.3.4. ACS
3.4. Zastosowania

4. Model GCS
4.1. Zadanie klasyfikacji
4.2. Werbalny opis modelu
4.3. Klasyfikator
4.3.1. Definicja
4.3.2. Płodność
4.3.3. Przystosowanie
4.4. Gramatyka
4.5. Architektura
4.6. Pokrycie
4.7. Ścisk
4.S. Algorytm genetyczny
4.8.1. Schemat działania
4.5.2. Metody selekcji
4.5.3. Operatory genetyczne
4.9. Korekcja
4.10. Parametry
4.11. Algorytmiczny opis modelu
4,11.1. Główna pętla programu
4.11.2. Indukcja gramatyki
4.11-3. Parsowanie zdania
4.11.4. Ścisk
4.11.5. Operatory pokrycia
4.11.6. Algorytm genetyczny
4.11.7. Korekcja
4.12. Opis programu GCS

5. Badania symulacyjne modelu GCS
5.1. Estymatory symulacji
5.1.1. Dokładność indukcji
5.1.2. Koszt indukcji
5.1.3. Dokładność generalizacji
5.2. Zbiory uczące
5.2.1. Wyrażenia regularne
5.2.2. Języki bezkontekstowe
5.2.3. Gramatyka dziecięca
5.2.4. Korpusy językowe
5.3. Indukcja wybranych języków regularnych
5.4. Indukcja wybranych języków bezkontekstowych
5.5. Indukcja języka naturalnego
5.6. Badanie symulacyjne
5.6.1. Metody selekcji
5.6.2. Selekcja turniejowa
5.6.3. Ścisk
5.6.4. Operatory pokrycia
5.6.5. Liczba początkowych produkcji nieterminalnych
5.6.6. Wielkość elity
5.6.7 Krzyżowanie i mutacja
5.6.8. Inwersja
5.6.9. Liczba symboli nieterminalnych
5.6.10. Płodność
5.6.11. Wagi funkcji dopasowania produkcji

6. Zastosowanie modelu GCS w genomice
6.1. Rozpoznawanie sekwencji telomerowej
6.1.1. Preliminaria biologiczne
6.1.2. Indukcja gramatyki ?telomerowej"
6.2. Poszukiwanie regionów promotorowych
6.2.1. Preliminaria biologiczne
6.2.2. Indukcja gramatyki ?promotorowej"

7. Podsumowanie
Załącznik A
Załącznik B
Załącznik C
Bibliografia
Skorowidz
Spis rysunków
Spis tabel
Streszczenie w języku angielskim

Contents

Preface

1. Grammatical inference
1.1. Introduction
1.2. Areas of applications
1.3. Selected concepts in automata theory and formal languages
1.4. Learning paradigms
1.4.1. Identification in the limit
1.4.2. PAC Model
1.4.3. Minimum description length
1.4.4. Query learning
1.5. Context-free grammar induction
1.5.1. Induction from text
1.5.2. Induction from structural data
1.5.3. Induction of subclasses of context-free grammars
1.5.4. Induction of alternative conceptions of context-free grammars
1.5.5. Stochastic context-free grammar induction
1.5.6. Induction with AI methods
1.5.7. CYK algorithm

2. Evolutionary methods
2.1. Evolutionary programming
2.2. Evolutionary strategies
2.3. Genetic algorithms
2.4. Genetic programming

3. Learning classifier system
3.1. Architecture
3.2. Classification
3.2.1. Chromosome scope criterion
3.2.2. Classifier fitness criterion
3.2.3. Classifier representation criterion
3.2.4. Classifier discovery criterion
3.2.5. System memory criterion
3.3. Selected models
3.3.1. LCS
3.3.2. ZCS
3.3.3. XCS
3.3.4. ACS
3.4. Applications

4. GCS model
4.1. Classification task
4.2. Verbal description of model
4.3. Classifier
4.3.1. Definition
4.3.2. Fertility
4.3.3. Fitness
4.4. Grammar
4.5. Architecture
4.6. Covering
4.7. Crowding
4.8. Genetic algorithm
4.8.1. Working scheme
4.8.2. Selection methods
4.8.3. Genetic operators
4.9. Correction
4.10. Parameters
4.11. Algorithmic description of GCS model
4.11.1. Main loop of program
4.11.2. Grammar induction
4.11.3. Sentence parsing
4.11.4. Crowding
4.11.5. Covering operators
4.11.6. Genetic algorithm
4.11.7. Correction
4.12. GCS program description

5. Computer simulation of GCS model
5.1. Estimators of computer simulation
5.1.1. Induction accuracy
5.1.2. Induction cost
5.1.3. Generalization accuracy
5.2. Learning sets
5.2.1. Regular expression
5.2.2. Context-free languages
5.2.3. Toy grammar
5.2.4. Corpora
5.3. Induction of selected regular expressions
5.4. Induction of selected context-free languages
5.5. Natural language induction
5.6. Computer simulation
5.6.1. Selection methods
5.6.2. Tournament selection
5.6.3. Crowding
5.6.4. Covering operators
5.6.5. Number of initial nonterminal productions
5.6.6. Elite size
5.6.7. Crossover and mutation
5.6.8. Inversion
5.6.9. Number of nonterminal symbols
5.6.10. Fertility
5.6.1 1. Weights of production's fitness function

6. Applications of GCS model in genomic
6.1. Recognition of telomer sequences
6.1.1. Biological preliminaries
6.1.2. Telomer grammar induction
6.2. Recognition of promoter sequences
6.2.1. Biological preliminaries
6.2.2. Promoter grammar induction

7. Summary
Appendix A
Appendix B
Appendix C
Bibliography
Subject index
List of figures
List of tables
Summary in English