Podręcznik

1. Standardy multimedialne

1.14. Sztuczna inteligencja

Sztuczna inteligencja kojarzona jest z maszyną myślącą, czyli są to metody, algorytmy, urządzenia posiadające (skutecznie naśladujące) funkcje ludzkiego umysłu. Inaczej, sztuczna inteligencja jest nauką o maszynach wykonujących zadania, które wymagają inteligencji, gdy są rozwiązywane przez człowieka.

Sztuczna inteligencja (artificial intelligence -- AI) to dział informatyki, którego przedmiotem jest badanie reguł rządzących inteligentnymi zachowaniami człowieka, tworzenie formalnych modeli tych zachowań i — w konsekwencji — realizacja narzędzi komputerowych (za pomocą algorytmów, procedur, oprogramowania, rozwiązań sprzętowych) symulujących, naśladujących lub wspomagających te zachowania.

SI ma powiązania z psychologią, medycyną, fizjologią, bioniką, cybernetyką, teorią gier, modelowaniem matematycznym i in., czerpiąc pojęcia, metody i rezultaty oraz ubogacając poprzez oferowanie własnych pojęć i aparatu badawczego, metod obiektywizacji i formalizacji wiedzy. Przykładowe, wykorzystywane metody i narzędzia to -- w warstwie konceptualnej -- języki programowania (głównie Lisp i Prolog), języki systemów eksperckich (CLIPS, jego rozszerzenia -- np. Jess, Flops, OPS5, Smalltalk), środowiskowe programy ułatwiające implementacje systemów (Pro Genesis, KEE, Loops, Level 5 Object, Aion Execution System), systemy szkieletowe (ExSys, DecisionPro, PC-Shell, G2, XpertRule), zintegrowany pakiet oprogramowania narzędziowego (np. SPHINX), algorytmy wyszukiwania informacji, poszukiwania rozwiązań problemów złożonych, dopasowywania wzorców i in., systemy wspomagania rozpoznania, decyzji, schematy i procedury działań zaradczych, przewidywania, ostrzegania, planowania, sterowania, zaś w warstwie materialnej -- komputery o specjalnej architekturze, urządzenia komunikowania się z komputerem (interfejsy, różne technologie interakcji), inteligentne roboty itp.

Komputerowe realizacje SI wykorzystuje się konkretniej do rozpoznawania kształtów (np. pisma, elementów obrazów), dźwięków (np. mowy), do gry (np. w szachy, strategicznych), dowodzenia twierdzeń, wyszukiwania informacji, analizy wyników eksperymentalnych, w celu komponowania muzyki, tłumaczenia testów, formułowania ekspertyz (ocen, opinii), sterowania, monitorowania, śledzenia obiektów, robotów i procesów technologicznych, do sugerowania prostych diagnoz lekarskich, w koncepcji inteligentnego domu, zarządzania sprzętem, aktualizacji informacji i zasobów wiedzy, klasyfikacji zagadnień, problemów itp.

Jednoznaczna definicja systemów SI jest trudna, a granice płynne. Ogólnie są to systemy bazujące na wiedzy i doświadczeniu, wykorzystujące bardziej jakościową wiedzę niż modele matematyczne, charakteryzujące się symbolicznym wnioskowaniem, chociaż z biegiem lat w coraz większym stopniu wykorzystujące metody numeryczne. Algorytmy odwołują się coraz częściej do sprawdzonych heurystyk, poszukując wręcz najbardziej korzystnych uproszczeń w sytuacji zastanej. Tworzone systemy informacyjne (maszyny) mają zdolność uczenia się, pozyskiwania wiedzy, głębokiej adaptacyjności oraz autonomiczności.

Wśród fundamentalnych obszarów SI wyróżnia się przede wszystkim reprezentację wiedzy, systemy ekspertowe, sieci neuronowe, algorytmy genetyczne, szerzej -- ewolucyjne, kognitywistykę, teorię gier, przetwarzanie języka, rozumienie mowy, widzenie komputerowe, uczenie maszyn, logikę rozmytą, programowanie automatyczne i robotykę.

Zasadniczy podział zagadnień sztucznej inteligencji ogranicza się do:

silnej SI, dotyczącej systemów myślących, odwołującej się do osiągnięć kognitywistyki (tj. nauki zajmującej się badaniem, wyjaśnianiem i modelowaniem umysłu oraz procesów poznawczych, w tym percepcją, reprezentacją, emocjami, świadomością, pamięcią, rozumowaniem, mową, komunikacją itp.);
słabej SI, nazywanej inteligencją obliczeniową, soft computing, zajmującej się problemami szczegółowymi, o jasno zdefiniowanym celu oraz kryteriach wykorzystując logikę, teorie zbiorów, teorię automatów, probabilistykę i statystykę itp.; podstawowe metody to automatyczne wnioskowanie, transmutacje wiedzy, stosowanie heurystyk, algorytmy mrówkowe, maszynowe uczenie się (z nadzorem, bez nadzoru, odkrywanie asocjacji i wzorców sekwencji, boty (tj. narzędzia do przeszukiwania i pozyskiwania wiedzy, z mechanizmem decyzyjnym na bazie wcześniej zdobytej wiedzy) itd.

Aproksymacja i optymalizacja

Zadania rozwiązywane w ramach SI można przyporządkować dwóm postawowym kategoriom: zadania aproksymacji oraz zadania optymalizacji.

Aproksymacją nazywamy znajdowanie ciągłego modelu zjawiska, cechy czy sygnału za pomocą funkcji czy krzywej przechodzącej w pobliżu zadanego, ziarnistego (dyskretnego) zbioru punktów. Zwykle aproksymację rozumie się więc w kontekście funkcjonalnego opisu danej dziedziny. Jest to problem dobrania nieznanej funkcji (zespołu funkcji określonej klasy, kawałków funkcji, krzywej itp.) na podstawie ograniczonych informacji o danym procesie, tj. skończonej liczby wartości (często zmierzonych, a więc obarczonych błędem pomiaru) danej dziedziny. Inaczej, mamy więc do czynienia z zagadnieniem przybliżania (dopasowywania) danych data fitting).

Zadania aproksymacji (inaczej ekstrapolacji, rozpoznania) obejmują przede wszystkim

znajdowanie ukrytych zależności pomiędzy danymi,
przewidywanie (predykcja) zachowań obiektów, przebiegu zdarzeń, wyników własnych działań, prognozowanie trendów;
uogólnienia wiedzy (''skoro wszyscy sportowcy -- biegacze trenują przynajmniej pięć dni w tygodniu, to brak takiego treningu może oznaczać niebycie biegaczem'');
uzupełnianie fragmentów zniszczonych zdjęć, zwiększanie rozdzielczości obrazów cyfrowych w celu wyświetlenia na wysokiej jakości monitorze;
rozpoznanie (efekt klasyfikacji) nieznanych obiektów na podstawie znanych przykładów, np. rozpoznawanie obrazów, mowy, OCR;
sterowanie obiektami, modelowanie zachowań, naśladowanie, animacja.

Podstawowy schemat postępowania obejmuje wybór uzasadnionej klasy funkcji dobrze aproksymujących właściwości opisywanego zjawiska (jest to zasadniczy przedmiot rozważań teorii aproksymacji), a następnie procedurę (algorytm) dobierania konkretnej postaci funkcji odpowiadającej pomierzonym wartościom (to przede wszystkim obszar analizy i metod numerycznych). Użyteczna klasa funkcji aproksymujących to przede wszystkim funkcje względnie gładkie (gładkość to cecha sygnałów naturalnych), stanowiące zbiór możliwie zupełny (tj. kompletny, obejmujący opisem wszystkie możliwe przypadki) względem rozważanej grupy problemów. Korzystne jest przy tym, gdy są to funkcje łatwe w komputerowej obróbce (liczenie wartości, określanie pochodnych i całek itp.). Przykładem stosowanych klas aproksymacji opisów naturalnych zjawisk są funkcje wielomianowe, przedziałami wielomianowe, funkcje sklejane.

Formalnie, mając dane niektóre wartości nieznanej funkcji $f$ na $X$ , tj. ciąg przykładów (próbek) -- zbioru treningowego $(x_1, y_1), \ldots, (x_n, y_n)$ , chcemy zgadnąć wartości $f: X \rightarrow Y$ w innych punktach dziedziny, tj. w dowolnym $x_0 \in X$ . Szukana $f$ , dająca zgadywane $y_0=f(x_0)$ , wyznaczana jest przy określonych ograniczeniach, wynikających z przyjętego kryterium aproksymacji $f$ jest możliwie wiarygodnym uogólnieniem charakteryzującym dany problem, rodzajem modelu określonej cechy dziedziny.

Kryterium aproksymacji może mieć różną postać, zwykle jedną z poniższych

$\forall_{i=1,\dots,n} f(x_i)=y_i\ \ \text{(interpolacja)}$

(3.1)

$\forall_{i=1,\dots,n} |f(x_i)-y_i| < \epsilon$

(3.2)

gdzie $\epsilon$ jest maksymalnym dopuszczalnym błędem w punkcie

$\min_f \sum_{i=1}^n |f(x_i)-y_i|$

(3.3)

$\max_f \Pr(f(x_1),\ldots, f(x_n))$

(3.4)

gdzie $f$ rozumiana jest jako zmienna losowa, proces losowy lub pole losowe.

W przypadku obrazów, obok dwuwymiarowych funkcji przybliżających rozkład wartości jasności danej grupy pikseli, stosowany jest też opis konturów obiektów za pomocą krzywych $S$ konstruowanych w płaszczyźnie obrazów. Do najbardziej użytecznych klas krzywych aproksymujących należy zaliczyć parametryczne krzywe wielomianowe typu Beziera, Hermite'a czy też krzywe sklejane. W kryteriach aproksymacji, występuje euklidesowa metryka $\|S - (x_i,y_i)\|$ .

Znajdowanie optymalnych rozwiązań dla bardziej złożonych zagadnień aproksymacji, a takimi niewątpliwie jest większość przybliżeń realnych obiektów i cech obrazowych, nie jest zadaniem prostym. Wydaje się, że do dziś aktualne jest ogólne stwierdzenie P.J. Daviesa z 1965 roku, że jednym z najbardziej zaskakujących faktów teorii aproksymacji jest nieskuteczność najprostszych i najbardziej naturalnych rozwiązań. Nierzadko w użytecznych realiach ocieramy się o problemy NP-trudne.

Optymalizacja jest metodą poszukiwania wśród wielu alternatyw rozwiązania najlepszego (optymalnego), ocenianego według wiarygodnego, liczbowego kryterium jakości. Przykładowo, są to problemy minimalizacji funkcji kosztu poszukiwań, minimalizacji funkcji błędu względem rozwiązania wzorcowego, maksymalizacja wygranej (w grach logicznych) itp. W złożonych problemach często nie wystarcza jedno kryterium -- mówimy wtedy o optymalizacji wielokryterialnej, np. odwieczny problem maksymalizacji zysków przy minimalizacji kosztów czy też maksymalizacji jakości kompresowanego stratnie obrazu przy minimalizacji średniej bitowej jego reprezentacji. Dobór metody przetwarzania obrazów źródłowych, kiedy chcemy jednocześnie zredukować szum, wyostrzyć krawędzie i zachować oryginalne cechy tekstury jest też dobrym przykładem takiego zagadnienia.

Przez $X$ oznaczmy dowolny, skończony zbiór wszystkich możliwych rozwiązań problemu (tzw. przestrzeń stanów). Do oceny rozwiązań -- stanów wykorzystajmy rzeczywistą funkcję celu $f:\ X\rightarrow R$ . Zadaniem jest znaleźć takie $x_0 \in X$ według jednego z kryteriów

maksimum

$x_0=\arg \max_{x \in X} \{f(x)\}$

(3.5)

minimum

$x_0=\arg \min_{x \in X} \{f(x)\}$

(1.3)

Klasycznym przykładem zadań optymalizacji jest sortowanie, poszukiwanie wyjścia z labiryntu, poszukiwanie najkrótszej drogi dojścia do celu (np. problem komiwojażera), posunięcia giełdowe maksymalizujące zysk, zarządzanie pamięcią operacyjną czy dostępem do zasobów itp.

Realne problemy optymalizacji mają zwykle olbrzymią przestrzeń stanów, niepozwalającą zastosować trywialnych metod typu brute force jako praktycznego rozwiązania. W takich przypadkach poszukiwane są skuteczne heurystyki, pozwalające przeglądać przestrzeń stanów w rozsądnych wymiarach czasowych. Jeśli problem da się opisać analitycznie, co nie jest częste w realnych zjawiskach, zadanie optymalizacji sprowadza się do policzenia odpowiedniego ekstremum zadanej funkcji celu (lub funkcjonału). Wykorzystuje się wtedy zwykle układ równań uzyskany poprzez przyrównanie składowych gradientu funkcji celu do zera. Można też poszukiwać lokalnych ekstremów kierując się kierunkiem gradientu. Stosowany jest też losowy wybór rozwiązań według określonego scenariusza, np. w algorytmach ewolucyjnych.

Łatwo zauważyć, że zadanie optymalizacji może znaleźć zastosowanie w problemie aproksymacji, np. do wyszukania ze skończonego zbioru funkcji danej klasy rozwiązania dającego minimalny błąd przybliżenia danych według kryterium. Odwrotnie, aproksymację uproszczonych rozwiązań, jako pewnego rodzaju redukcję przestrzeni stanów można wykorzystać do rozwiązania problemu optymalizacji (np. w metodzie Newtona).