Tekst źródłowy strony Sztuczna inteligencja/SI Moduł 1 - O czym jest ten przedmiot

<!-- Wygenerowane przez tex2wikiu8.pl czas: wto lip 18 17:39:57 CEST 2006 -->

== Znaczenie inteligencji ==

Przegląd inteligentnych technik obliczeniowych należy rozpocząć od
ustalenia, co chcemy przez taki termin rozumieć. Jest jasne, że przez
techniki obliczeniowe rozumie się pewne metody lub grupy metod
rozwiązywania określonego rodzaju zadań, które mogą być użyte do
stworzenia programów komputerowych rozwiązujących takie zadania.
Można w uproszczeniu przyjąć, że technika obliczeniowa reprezentuje
ogólną metodę postępowania z zadaniami pewnego rodzaju, następnie
służy do opracowania konkretnego algorytmu, przeznaczonego do
rozwiązania konkretnego praktycznego zadania, a ten algorytm
zaimplementowany w wybranym języku programowania staje się programem
lub częścią programu. Jeśli teraz chcemy mówić o inteligentnych
technikach obliczeniowych, pozostaje nam rozważyć, czym jest
inteligencja oraz czy i w jakim zakresie ma sens ma mówienie o
inteligencji sztucznych systemów, takich jak programy komputerowe.

=== Naturalna inteligencja ===

Mówiąc w języku potocznym o człowieku, że jest inteligenty, możemy
opierać się na różnych łatwo obserwowalnych przesłankach, takich jak
oceny w szkole, osiągnięcia w pracy (umysłowej), sprawność w
rozwiązywaniu zadań matematycznych czy umiejętność wypowiadania się
bez błędów językowych. Próbując od tego typu przykładów przejść do
bardziej ogólnej intuicji dotyczącej potocznego rozumienia
inteligencji naturalnej, powiedzielibyśmy, że
<!-- begin{quote} -->
<table width="90%" align="center"><tr><td>
'''inteligencja jest zdolnością do (poprawnego, sprawnego itd.) rozwiązywania zadań intelektualnych, które zazwyczaj uchodzą za trudne.'''
</td></tr></table>
<!-- end{quote} -->
Bez wątpienia panujące przekonania na temat trudności zadań ulegają
nieustannym zmianom wraz z rozwojem cywilizacji i techniki, więc siłą
rzeczy odpowiednim przekształceniom może ulegać rozumienie
inteligencji. Są to jednak zmiany na tyle powolne, że nie stanowią
przeszkody w uznaniu sprawności w rozwiązywaniu trudnych zadań za
wystarczającą praktyczną i nieformalną definicję inteligencji.

Poważniejszym mankamentem tej definicji jest brak jasnych kryteriów,
według których zadania należałoby kwalifikować jako „intelektualne”.
Musimy się zadowolić tu dość prostym i mało precyzyjnym kryterium,
według którego chodzi o zadania wymagające wyłącznie lub przede
wszystkim aktywności umysłowej. W szczególności trudność zadania nie
może polegać na wymaganiu znacznej siły mięśni, znakomitej koordynacji
ruchów, świetnego refleksu lub rzadkiej sprawności manualnej, lecz na
wymaganiu odpowiednio sprawnego umysłu.

Powyższą definicję inteligencji, mimo różnych jej wad, a zwłaszcza
braku precyzji, bez większego trudu możemy stosować do ludzi. Jest
wówczas stosunkowo jasne, jakie zadania intelektualne można uznać za
wystarczająco trudne i jaki poziom sprawności w ich rozwiązywaniu jest
wystarczająco duży, aby człowieka nazwać inteligentnym. Możemy również
w podobny sposób wypowiadać sądy o inteligencji zwierząt (takich jak
pies czy małpa), stosując rzecz jasna odpowiednio złagodzone kryteria
jeśli chodzi o trudność zadań i sprawność ich rozwiązywania -
odpowiednie do naszego mniemania o typowym poziomie sprawności
umysłowej zwierząt danego gatunku, ukształtowanego przez własne
obserwacje i zasłyszane lub przeczytane relacje.

=== Sztuczna inteligencja ===

Mówiąc o sztucznej inteligencji rozszerzamy pojęcie inteligencji,
którego znaczenie w przybliżony sposób scharakteryzowaliśmy wyżej dla
systemów naturalnych (ludzi i zwierząt), na systemy sztuczne -
programy komputerowe. Chcemy zatem uznać za „inteligentne” takie
programy, które są w stanie z zadowalającą sprawnością rozwiązywać
trudne zadania. Ponieważ w naturalny sposób celem konstruowania takich
programów jest umożliwienie zautomatyzowania pewnych czynności
wykonywanych przez ludzi, interesować nas będzie

<!-- begin{quote} -->
<table width="90%" align="center"><tr><td>
'''sprawne rozwiązywanie zadań, które według powszechnej opinii wymagają inteligencji, jeśli są wykonywane przez człowieka.'''
</td></tr></table>
<!-- end{quote} -->

Chociaż definicja ta staje się jeszcze mniej precyzyjna i ścisła, niż
jej odpowiednik stosowany do inteligencji ludzi, jest prawdopodobnie
najlepszą dostępną ogólną i pełną charakterystyką zakresu
zainteresowań sztucznej inteligencji.  Zgodnie z nią, przedmiotem
sztucznej inteligencji jest konstruowanie systemów inteligentnych:
programów komputerowych zdolnych do wykonywania zadań, które od
człowieka wymagają inteligencji.

Próby bardziej precyzyjnego formułowania definicji systemów
inteligentnych prowadzą do kilku różnych koncepcji sztucznej
inteligencji. Można je opisać podając kryteria, jakie według nich
spełnia sztuczny system inteligentny. Może to być:
# system, który myśli jak człowiek,
# system, który myśli racjonalnie,
# system, który zachowuje się jak człowiek,
# system, który zachowuje się racjonalnie.

Pierwsze dwie koncepcje domagają się, aby system inteligentny
charakteryzował się zdolnością do myślenia. O ile nie ustalimy pewnego
mocno zawężonego technicznego sensu słowa „myślenie”, takie
przenoszą sformułowania przenoszą nas raczej na grunt filozofii i
psychologii niż informatyki. Koncepcje odwołujące się do zachowania
systemu jako podstawy do oceny jego inteligencji są znacznie bliższe
naszej technicznej perspektywie, przy czym w większości zastosowań
systemów inteligentnych chodzi raczej o zachowanie racjonalne (a więc
jak najlepsze wykonanie stojącego przed systemem zadania) niż
naśladowanie człowieka, w którego zachowaniu mogą występować motywacje
pozaracjonalne. Wobec tego będziemy się raczej koncentrować na różnych
rodzajach „zachowania racjonalnego”, które mogą być poddane
automatyzacji, tj. dla których można sformułować algorytm o
praktycznie akceptowalnej złożoności obliczeniowej.

== Zakres badań nad sztuczną inteligencją ==

Termin „sztuczna inteligencja” łączy się z wieloma kontrowersjami,
nieporozumieniami i mitami, które częściowo wynikają z jego zbyt
dosłownego interpretowania. Znaczna część prac dotyczących sztucznej
inteligencji  dotyczy konstruowania systemów przejawiających wybrane,
szczególne aspekty inteligentnego zachowania, a wyniki tych prac od
wielu lat znajdują praktyczne zastosowania w formie dojrzałych
technicznie rozwiązań. Osiągnięcia tego nurtu badań są niepodważalne i
nie budzą kontrowersji, choć w potocznym rozumieniu niekoniecznie są
one wiązane ze sztuczną inteligencją
<ref name="przypis1">Niekiedy żartobliwie mówi się, że trudne zadania uważa się za leżące w zakresie sztucznej inteligencji tak długo, jak długo nie są znane skuteczne i efektywne algorytmy ich rozwiązywania. Po znalezieniu takich algorytmów zadania te przestają być traktowane jako zadania sztucznej inteligencji. W ten sposób sztuczna inteligencja nigdy nie ma żadnych osiągnięć, gdyż odbiera jej się wszystko, co uda jej się rozwiązać.</ref>.
Tymczasem uwaga potoczna często bardziej koncentruje się na wizji
sztucznych inteligentnych istot, ukształtowanej przez fantastykę
naukową. Ponieważ większości racjonalnie myślących ludzi taka wizja
wydaje się co najmniej mocno odległa w czasie, dziedzinę sztucznej
inteligencji traktuje się niekiedy z niesprawiedliwą pogardą jako
zajmującą się mrzonkami lub szarlatanerią.

=== „Mocna” i „słaba” sztuczna inteligencja ===

Perspektywa, jaką będziemy przyjmować omawiając inteligentne techniki
obliczeniowe, jest zbieżna z tym, co nazywa się często „słabą”
sztuczną inteligencją. Określenie „słaba” nie ma tu charakteru
lekceważącego czy deprecjonującego, lecz wyraża raczej skromne i
pragmatyczne cele:

<!-- begin{quote} -->
<table width="90%" align="center"><tr><td>
'''rozwiązywanie „trudnych” zadań w sposób umożliwiający praktyczne zastosowania.'''
</td></tr></table>
<!-- end{quote} -->

Zadania te reprezentują tylko niektóre wybrane aspekty „zachowania
inteligentnego”, które mogą w znacznej mierze być rozważane
niezależnie. Systemy inteligentne z punktu widzenia „słabej”
sztucznej inteligencji to systemy rozwiązujące takie zadania i
wykorzystujące w tym celu odpowiednie inteligentne techniki
obliczeniowe.

Dla odmiany „mocna” sztuczna inteligencja stawia sobie ambitne cele
konstruowania systemów inteligentnych, którym można by przypisać

<!-- begin{quote} -->
<table width="90%" align="center"><tr><td>
'''zdolność do myślenia w sposób w pewnym stopniu dający się porównywać z myśleniem ludzkim.'''
</td></tr></table>
<!-- end{quote} -->

Jest to obszar zainteresowania bardziej filozofów umysłu niż
inżynierów. Od kilkudziesięciu lat toczy się zajmująca debata na temat
możliwości osiagnięcia celów „mocnej” sztucznej inteligencji, która
jednak w całości leży poza zakresem naszych zainteresować w ramach
tego kursu inteligentnych technik obliczeniowych. Gdyby przyjąć, że
skonstruowanie „systemu myślącego” w jakimkolwiek sensie jest
możliwe, niewykluczone, że wszystkie lub niektóre z omawianych przez
nas technik okazałyby się do realizacji tego celu przydatne, lecz
rozważania tego rodzaju nie będą nas tu zajmować.

=== Sztuczna inteligencja jako dyscyplina nauk technicznych ===

Sztuczna inteligencja w „słabym” rozumieniu może być traktowana jako
gałąź informatyki, kierująca się zasadniczo tymi samymi zasadami i
praktykami badawczymi co jej główny nurt, lecz wyróżniona przez
rodzaje zadań, których rozwiązywaniem się zajmuje. Jednocześnie te
zadania zbliżają ją do szeregu innych pokrewnych dyscyplin, takich jak
automatyczne sterowanie, robotyka czy statystyka. Ważnymi źródłami
inspiracji dla inteligentnych technik obliczeniowych są niektóre
osiągnięcia nauk nietechnicznych, takich jak biologia i psychologia.

== Zadania sztucznej inteligencji ==

Ograniczając się do sztucznej inteligencji w jej technicznym, a więc
„słabym” sensie, dokonamy teraz ogólnego przeglądu najważniejszych
rodzajów zadań, które są przedmiotem jej zainteresowania.

=== Przeszukiwanie ===

Wiele zadań praktycznych, dla których należy znaleźć rozwiązania
spełniające pewne ustalone kryteria i ograniczenia, można potraktować
jako konkretne przypadki ogólnego zadania przeszukiwania.
Przeszukiwana przestrzeń obejmuje potencjalne rozwiązania zadania
(także niekompletne, nie spełniające ograniczeń, niskiej jakości) i w
interesujących praktycznie przypadkach jest zbyt duża, aby przy użyciu
maksymalnych dostępnych obecnie i w wyobrażalnej przyszłości mocy
obliczeniowych rozważenie każdego jej elementu mogło być
przeprowadzone w akceptowalnym czasie. Inteligentne techniki
obliczeniowe opracowywane do przeszukiwania mają na celu

<!-- begin{quote} -->
<table width="90%" align="center"><tr><td>
'''znajdowanie zadowalających rozwiązań bez pełnego przeglądania wszytkich możliwości, a więc dokonanie niewyczerpującego przeszukiwania przestrzeni rozwiązań.'''
</td></tr></table>
<!-- end{quote} -->

Zadanie przeszukiwania przestrzeni formułuje się określając zbiór
stanów, z wyróżnionym stanem początkowym (od którego rozpoczyna się
przeszukiwanie) i zbiorem stanów końcowych (których osiągnięcie kończy
przeszukiwanie), oraz zbiór operatorów dostępnych w każdym stanie.
Zastosowanie operatora w stanie powoduje przejście do (zazwyczaj)
innego stanu (często mówi się, że generuje nowy stan).

Stan początkowy reprezentuje sytuację, od której rozpoczyna się
przeszukiwanie.  Stany niekońcowe reprezentują pośrednie etapy procesu
przeszukiwania (rozwiązania niepoprawne, niekompletne itp.). Operatory
pozwalają na poruszanie się w przestrzeni stanów.  Przeszukiwanie
przestrzeni jest więc

<!-- begin{quote} -->
<table width="90%" align="center"><tr><td>
'''procesem stosowania dostępnych operatorów do przemieszczania się między różnymi stanami w tej przestrzeni, tak aby ostatecznie trafić ze stanu początkowego do jednego ze stanów końcowych.'''
</td></tr></table>
<!-- end{quote} -->

Wynikiem przeszukiwania jest ciąg operatorów, których zastosowanie
przeprowadza nas ze stanu początkowego do stanu końcowego. Jest to
więc nie tyle samo rozwiązanie zadania, co raczej sposób jego
rozwiązania.  W niektórych zadaniach zadowala nas dowolne rozwiązanie,
a więc osiągnięcie jakiegokolwiek stanu końcowego w jakikolwiek
sposób.  Niekiedy poszczególne stany końcowe reprezentują rozwiązania
o niejednakowej jakości i wówczas zależy nam na znalezieniu w miarę
możliwości jak najlepszego. Niekiedy wreszcie ważne jest, aby sposób
dochodzenia do rozwiązania był jak najprostszy. Rozważa się wtedy
funkcję kosztu, która określa koszt zastosowania każdego operatora w
każdym stanie (w najprostszym przypadku zawsze jednakowy). Poszukiwany
jest taki ciąg operatorów prowadzący do stanu końcowego, który ma
minimalny łączny koszt.

=== Wnioskowanie ===

Wnioskowanie jest procesem przetwarzania wiedzy, w wyniku którego na
podstawie pewnego zbioru znanych stwierdzeń wyprowadza się nowe
stwierdzenia.  Wnioskowanie wykonywane przez człowieka może przebiegać
zarówno w sposób formalny, w którym wszystkie stwierdzenia zapisane są
w ustalonym precyzyjnym języku, wyprowadzanie nowych stwierdzeń rządzi
się ustalonymi precyzyjnie regułami, jak i nieformalny, w którym
stwierdzenia formułowane są w języku naturalnym, a wyprowadzanie
nowych stwierdzeń odbywa się ze znacznym udziałem intuicji. Rozważając
inteligentne techniki obliczeniowe do wnioskowania koncentrować się
będziemy na wnioskowaniu formalnym. Wymaga ono języka zapisu
stwierdzeń o dokładnie zdefiniowanej składni i semantyce oraz
mechanizmu wnioskowania opartego na precyzyjnych i jednoznacznych
regułach, które określają, jak na podstawie pewnego zbioru znanych
stwierdzeń uzyskać nowe stwierdzenie. Reguły takie są nazywane
regułami wnioskowania. Wówczas wnioskowanie jest

<!-- begin{quote} -->
<table width="90%" align="center"><tr><td>
'''procesem stosowania reguł wnioskowania w sposób skutecznie i efektywnie prowadzący do określonego celu wnioskowania, którym zazwyczaj jest uzyskania pewnego docelowego stwierdzenia.'''
</td></tr></table>
<!-- end{quote} -->

Stwierdzenia zapisane formalnie w języku logiki będziemy nazywać
formułami, a zbiór formuł znanych w procesie wnioskowania - bazą
wiedzy. Ciąg wykorzystanych formuł (i zastosowanych do nich reguł
wnioskowania) prowazący do formuły docelowej nazywany jest dowodem.
Zastosowanie pojedynczej reguły wnioskowania jest krokiem dowodu.

=== Uczenie się ===

Zdolność do uczenia się jest powszechnie uważana za jeden z
najważniejszych przejawów inteligencji. Przez uczenie się rozumiemy, w
najprostszym ujęciu, zdobywanie wiedzy lub umiejętności (a także
doskonalenie dotychczas posiadanej wiedzy lub umiejętności), na
podstawie wspomagających informacji, takich jak doświadczenia czy
przykłady. Rozważając sztuczne systemy uczące się będziemy przez
uczenie się rozumieć

<!-- begin{quote} -->
<table width="90%" align="center"><tr><td>
'''proces zmiany zachodzącej w systemie na podstawie doświadczeń, która prowadzi do poprawy jego jakości działania rozumianej jako sprawność rozwiązywania stojących przed systemem zadań.'''
</td></tr></table>
<!-- end{quote} -->
Wynik procesu uczenia się, czyli zdobytą wiedzę, nazywać będziemy
hipotezą. Zewnętrzną informację, na podstawie której następuje uczenie
się, nazywać będziemy informacją trenującą.

=== Przykłady zadań ===

Aby nadać powyższemu ogólnemu wprowadzeniu do zakresu zainteresowań
sztucznej inteligencji bardziej konkretny wymiar, przyjrzyjmy się
kilku charakterystycznym przykładom praktycznych zadań, które
zazwyczaj się do tego zakresu zalicza.

'''Układanie planu lekcji.''' Zadanie to polega na wygenerowaniu pewnej czteroargumentowej relacji
określonej na zbiorze nauczycieli, grup, sal i godzin zajęciowych, do
której należą wszystkie takie i tylko takie czwórki
<math>\langle n,g,s,t\rangle</math>,, że nauczyciel <math>n</math>, prowadzi zajęcia z grupą <math>g</math>, w sali
<math>s</math>, i w terminie <math>t</math>,. Trudność zadania wynika z konieczności
jednoczesnego spełnienia szeregu ograniczeń (brak konfliktów
jednoczesnych różnych zajęć tego samego nauczyciela, tej samej grupy,
w tej samej sali, dokładnie określona liczba godzin zajęć określonego
nauczyciela z określoną grupą, brak „okienek” dla grup, a w praktyce
także szereg innych ograniczeń związanych ze specyfiką procesu
dydaktycznego), a także osiągnięcia rozwiązania możliwie wysokiej
jakości ze względu na jedno lub więcej kryteriów (np. minimalna
liczba „okienek” dla nauczycieli, małe zróżnicowanie dziennej liczby
godzin zajęciowych każdej grupy w tygodniu itp.).

'''Gra w szachy.''' Szachy są najbardziej znanym przykładem gry, która jest wystarczająco
trudna, aby mistrzostwo w niej było uważane za niekwestionowany
przejaw wybitnej inteligencji. Zadanie wybierania ruchów w partii gry
dwuosobowej należy do kanonu tradycyjnych zadań sztucznej
inteligencji. Sukcesy, jakie udaje się osiągać najbardziej
wyrafinowanym programom w nietrywialnych grach (np. zbliżenie się do
poziomu gry mistrzów szachowych) budzą są bez wątpienia przykładem
udanego rozwiązania „intelekturalnego” zadania niezywkle trudnego
dla większości ludzi.

'''Dowodzenie twierdzeń.''' W zadaniu tym wymagamy generowania dowodów dla twierdzeń,
sformułowanych w pewnym ustalonym sformalizowanym języku (języku
logiki lub języku opartym na języku logiki), dotyczących pewnej
ustalonej dziedziny. Mogą to być twierdzenia z wybranego działu
matematyki (np. geometria, teoria liczb).

'''Sterowanie mobilnym robotem.''' Weźmy pod uwagę robota wyposażonego w pewną aparaturę do obserwacji
otoczenia (np. czujniki podczerwieni, ultradźwięków, kamera) oraz
układ motoryczny do poruszania się (np. kółka napędzane silnikami).
Przed takim robotem można stawiać szereg szczegółowych zadań,
wymagających od niego w szczególności umiejętności znajdowania drogi w
środowisku: przemieszczania się między pewnymi położeniami w możliwie
krótkim czasie, z ominięciem wszelkich przeszkód, takich jak ściany,
meble, ludzie czy inne roboty. Wymaga to podejmowania w czasie
rzeczywistym decyzji o kolejnych ruchach (kierunku jazdy, utrzymaniu
lub zmianie prędkości) na podstawie aktualnych obserwacji z czujników
albo kamery.

'''Diagnostyka medyczna.''' Lekarz stawiając diagnozę na temat jednostki chorobowej lub zalecając
terapię na podstawie wyników badań diagnostycznych opiera się swojej
wiedzy, która w znacznym stopniu wywodzi się z doświadczenia. Zadanie
wyprowadzenia z wielu różnorodnych jednostkowych przypadków ogólnych i
w znacznym stopniu niezawodnych reguł decyzyjnych jest bez wątpienia
trudne. Jeśli przyjmiemy, że dostępny jest zbiór danych wielu
przypadków pacjentów, dla których zapisane zostały wyniki badań oraz
zweryfikowana diagnoza bądź terapia wraz z oceną jej faktycznej
skuteczności, to można postawić zadanie automatycznego wygenerowania
na podstawie takich danych wiedzy (np. zapisanej w postaci reguł).
Wiedza taka mogłaby być używana przez prosty system wnioskujący do
wspomagania lekarza w diagnozowaniu (uzupełniając w ten sposób jego
własną wiedzę).

== Rozwiązywanie zadań jako przeszukiwanie ==

Scharakteryzowane zwięźle wyżej abstrakcyjne zadania sztucznej
inteligencji, a także ich liczne możliwe konkretyzacje, można do
pewnego stopnia traktować w ujednolicony sposób, jako pewne szczególne
odmiany pierwszego najbardziej ogólnego zadania przeszukiwania.

: '''Wnioskowanie'''  traktowalibyśmy jako przeszukiwanie przestrzeni możliwych sekwencji kroków wnioskowania w poszukiwaniu dowodu stwierdzenia docelowego.
: '''Uczenie się'''  można rozumieć jako przeszukiwanie przestrzeni możliwych hipotez w poszukiwaniu tej, która najlepiej odpowiada celom systemu i uzyskanej przez niego informacji trenującej.
: '''Planowanie'''  może być traktowane jako przeszukiwanie przestrzeni możliwych planów w poszukiwaniu takiego, który osiąga cel zadania.

Aby naszkicowana w tak ogólny sposób wspólna perspektywa patrzenia na
różne zadania była faktycznie użyteczna przy ich rozważaniu, musi być
oczywiście w znacznym stopniu uszczegółowiona przez dokładne
scharakteryzowanie przeszukiwanej przestrzeni, określenie stanów,
operatorów, stanów docelowych i ewentualnie funkcji kosztu. Będziemy
się tym zajmować w systematyczny kolejnych lekcjach. Obecnie
poprzestaniemy tylko na wstępnym szkicu, który uczyni propozycję
traktowania różnych zadań sztucznej inteligencji jako szczególnych
odmian zadania przeszukiwania nieco bardziej przekonującą.

=== Wnioskowanie jako przeszukiwanie ===

W typowym przypadku celem wnioskowania jest znalezienie ciągu formuł i
stosowanych kolejno reguł wnioskowania prowadzącego do formuły
docelowej. Taki ciąg stanowi rozwiązanie zadania wnioskowania, czyli
dowód. Możemy więc mówić, że wnioskowanie jest przeszukiwaniem
przestrzeni możliwych ciągów formuł i reguł wnioskowania
(potencjalnych dowodów) w celu znalezienia takiego, który prowadzi do
formuły docelowej (faktycznego dowodu). Taki punkt widzenia,
traktujący ciągi formuł jako stany, jest uzasadniony, lecz trudny do
bezpośredniego wykorzystania praktycznego. Bardziej owocna jest
perspektywa, zgodnie z którą jako aktualny stan traktujemy zbiór
formuł „znanych” systemowi wnioskującemu (zawartość bazy wiedzy), a
za stam końcowy uznajemy taki, w którym ten zbiór zawiera formułę
docelową. W każdym stanie dostępne są operatory polegające na
zastosowaniu do pewnej liczby formuł (najczęściej dwóch) z aktualnego
zbioru pewnej reguły wnioskowania, której efektem jest dodanie bazy
wiedzy kolejnej formuły.

=== Uczenie się jako przeszukiwanie ===

Aby nieco skonkretyzować koncepcję traktowania uczenia się jako formy
przeszukiwania, skupimy się na podstawowym, najbardziej znanym i
najczęściej stosowanym rodzaju uczenia się, jakim jest indukcyjne
uczenie się klasyfikacji. Informacja trenująca ma tam postać zbioru
przykładów, z których każdy opisany jest przez pewne właściwości,
nazywane atrybutami, oraz opatrzony etykietą przyporządkowującą go do
pewnej kategorii. Celem uczenia się jest znalezienie hipotezy
(reprezentowanej przez pewną strukturę danych), która umożliwiałaby
„odgadywanie” poprawnej kategorii dla każdego przykładu na podstawie
jego wartości atrybutów, także jeśli będzie to przykład spoza zbioru
trenującego.

Przestrzenią przeszukiwań jest przestrzeń możliwych hipotez, która w
praktyce jest wyznaczana przez przyjętą metodę reprezentacji hipotez
oraz przez zestaw atrybutów używanych do opisu przykładów. Możemy
sobie w szczególności wyobrazić, że hipoteza jest reprezentowana przez
zbiór reguł, które sprawdzając szereg warunków dotyczącyc wartości
atrybutów wyznaczają przypuszczalną kategorię przykładu. Zbiór
wszystkich możliwych do zapisania zbiorów reguł tej postaci jest
wówczas przeszukiwaną przestrzenią. Celem jest znalezienie takiego
zbioru reguł, który odpowiednio dobrze pasuje do zbioru trenującego (a
więc poprawnie klasyfikuje wszystkie lub znaczną większość zawartych w
nim przykładów) i jest przy tym możliwie prosty (a więc zawiera
możliwie mało reguł o jak najprostszych warunkach). Jedna z prostych
możliwych strategii przeszukiwania takiej przestrzeni polegałaby na
uznaniu pustego zbioru reguł za stan początkowy oraz rozważania w
każdym stanie operatorów polegających na dodaniu nowej reguły (o
trywialnym warunku, np. zawsze spełnionym) lub na modyfikacji
(np. uszczegółowieniu) warunku istniejącej reguły. Za stan końcowy
moglibyśmy uznać zbiór reguł, który wystarczająco dokładnie
klasyfikuje przykłady ze zbioru trenującego.

=== Trudne i łatwe zadania ===

Perspektywa, zgodnie z którą rozważane przez nas zadania sztucznej
inteligencji traktowane są jako szczególne warianty ogólnego zadania
przeszukiwania, umożliwia jednolitą charakterystykę trudności zadań.
Trudność zadania możemy utożsamić ze złożonością przeszukiwanej
przestrzeni. Nie będziemy obecnie formalizować pojęcia złożoności
przestrzeni, zadowalając się jego następującym intuicyjnym
rozumieniem: przestrzeń jest tym bardziej złożona, im większy jest
stosunek liczby wszystkich możliwych ścieżek prowadzących od stanu
początkowego do liczby tych ścieżek, które prowadzą do jednego ze
stanów końcowych. Rozmiar przeszukiwanej przestrzeni jest więc ważnym,
lecz nie jedynym czynnikiem wpływającym na jej złożoność. Ważny jest
również „współczynnik rozgałęziania”, który określa liczbę nowych
stanów generowanych w odwiedzanych przy przeszukiwaniu stanach przez
dostępne operatory. Zadanie jest trudne, jeśli w dużej przestrzeni
przeszukiwań tylko bardzo nieliczne ścieżki prowadzą do stanów
końcowych.

-----
<references/>