Omówione zostaną związki między sztuczną inteligencją a zagadnieniami optymalizacji i aproksymacji. Pierwszą omówioną w ramach tego wykładu techniką wykorzystywaną w zadaniach z zakresu sztucznej inteligencji są sieci neuronowe.
Optymalizacja własnych działań to jedna z cech inteligencji (naturalnej i sztucznej). Wieokrotnie stykamy się z problemami, w których wśród wielu alternatyw szukamy najlepszego rozwiązania (ocenianego liczbowo). Kryterium może dotyczyć minimalizacji kosztu, minimalizacji funkcji błędu, maksymalizacji wygranej (gry logiczne) itp.
Formalnie: niech X - dowolny zbiór skończony (przestrzeń stanów), niech f:X->R - pewna rzeczywista funkcja na X (funkcja celu). Wówczas zadanie optymalizacyjne polega na znalezieniu punktu x0 ze zbioru X, takiego, że (w zależności od problemu):
W niektórych przypadkach problem od początku ma postać odpowiadającą powyższej definicji (np. "znaleźć maksimum funkcji f(x)=... na przedziale ..."). Czasem jednak ani przestrzeń stanów, ani funkcja celu nie są jawnie wymienione i wówczas należy znaleźć je samemu. Ważnym parametrem, sugerującym stopień trudności zadania, jest wielkość przestrzeni stanów - por. uwaga na końcu rozdziału.
Przykład: Posortować n nazwisk alfabetycznie (rosnąco).
Przestrzeń stanów: wszystkie możliwe ustawienia n nazwisk.
Wielkość przestrzeni stanów: n! (a nie n).
Przestrzeń stanów to zbiór wszystkich możliwych (również nieoptymalnych) rozwiązań problemu.
Funkcja celu: np. wartość 1 (sukces), jeśli porządek jest właściwy, lub 0 (porażka).
W bardziej złożonych problemach funkcja celu ma zwykle więcej wartości, niż 0 i 1.
Każde dyskretne i skończone zadanie optymalizacyjne można rozwiązać przez przejrzenie wszystkich możliwości (wszystkich elementów przestrzeni stanów). Oczywiście takie rozwiązanie jest czasem możliwe tylko w teorii; ze względu na ograniczenia sprzętowe nie jesteśmy w stanie przejrzeć w pełni np. 21000 możliwości i być może nigdy nie będziemy. Często jednak istnieją skuteczniejsze algorytmy (jak np. w przypadku sortowania).
Problemy kojarzone z terminem "sztuczna inteligencja" to często zadania aproksymacji (ekstrapolacji, predykcji), zgodnie ze schematem "mamy daną pewną dziedzinę i niektóre wartości nieznanej funkcji f, chcemy zgadnąć wartości f w innych punktach". Tak jest np. w przypadku przewidywania wyników własnych działań, wszelkiego rodzaju uogólnień wiedzy ("skoro wszystkie znane mi pingwiny mają dziób, to być może brak dzioba jest dowodem na niebycie pingwinem"), szukania ukrytych zależności w danych itp. Zakres zastosowań obejmuje wszelkiego rodzaju klasyfikację nieznanych obiektów na podstawie znanych przykładów (rozpoznawanie mowy, OCR, KDD, sterowanie, prognozowanie trendów itp.).
Formalnie: niech X - dowolny zbiór (przestrzeń stanów, uniwersum). Niech f:X->Y - pewna (nieznana) funkcja na X. Załóżmy, że mamy dany ciąg (x1, f(x1)), ... (xn, f(xn)) (dane treningowe, czyli znane przykłady). Zadanie aproksymacji polega tym, by (analizując i uogólniając znane przykłady) dla dowolnego punktu x0 ze zbioru X znaleźć wartość y taką, że (w zależności od problemu):
Przykład: Mamy zbiór obrazków binarnych 32x32 przedstawiających litery (pisane ręcznie). Chcemy rozpoznawać nowe, nieznane wcześniej przypadki (odczytywać nowe napisy). Przestrzeń stanów to wszystkie możliwe obrazki 32x32, więc wielkość przestrzeni stanów to 232*32. Przestrzeń stanów to zbiór wszystkich potencjalnych obiektów, jakie mogą pojawić się w zbiorze treningowym i później jako nowe obiekty.
Aproksymowana funkcja: pewna (teoretycznie istniejąca) funkcja przyporządkowująca każdemu możliwemu obrazkowi kod ASCII znaku, który jest na nim przedstawiony.
Nie ma prostych, "siłowych" rozwiązań problemu aproksymacji: jeżeli obiekt testowy x0 nie występował wśród znanych przykładów, musimy zastosować jakąś metodę uogólnienia tych przykładów - bez gwarancji, że trafimy na właściwą. Obiekt testowy może okazać się wyjątkiem, którego w ramach przyjętych założeń nie rozpoznamy prawidłowo.
Układ nerwowy człowieka od początku był naturalnym źródłem inspiracji dla badaczy sztucznej inteligencji. Stąd zainteresowanie neuronem - podstawową jednostką układu nerwowego. Działanie naturalnych neuronów polega (w znacznym uproszczeniu) na:
Podobne cechy miał mieć prosty model matematyczny, tzw. perceptron, opisany niżej. Historycznie celem prac nad sieciami neuronowymi było osiągnięcie zdolności uogólniania (aproksymacji) i uczenia się, właściwej mózgowi ludzkiemu (zgodnie z jedną z definicji sztucznej inteligencji). Obecnie większość zastosowań sztucznych sieci neuronowych koncentruje się na zadaniach znacznie mniej ambitnych, ale dzięki temu realistycznych - obecnie sieci neuronowe są od dłuższego czasu wykorzystywane komercyjnie w zadaniach sterowania urządzeniami, rozpoznawania obrazów czy pisma.
Perceptron - prosty model naturalnego neuronu - posiada wejścia (n zmiennych wejściowych x1,...,xn) przyjmujące wartości rzeczywiste lub binarne, będące odpowiednikiem dendrytów. Wejścia te albo są połączone z innymi perceptronami, albo stanowią wejścia (np. czujniki) całego układu. Wyjście w przypadku omawianego na tym wykładzie perceptronu stanowi pojedynczą wartość 0 lub 1.
Parametry wewnętrzne perceptronu to n wag połączeń w1,...,wn (liczb rzeczywistych), symulujących wagi synaps łączących naturalne neurony. Ostatnim parametrem jest wartość odchylenia b (ang. bias) odpowiadająca za nieliniowe przekształcenie wejść w wyjście.
Uwaga: pod pojęciem "perceptronu" lub "perceptronu wielowarstwowego" rozumie się też czasem sieć połączonych jednostek (neuronów).
Zasada działania
Do każdego i-tego wejścia perceptronu przypisana jest waga wi. Dla danych stanów wejściowych x1,...,xn liczymy sumę ważoną:
Jeżeli s jest większa lub równa 0, to ustawiamy wyjście y=1, zaś w przeciwnym przypadku ustawiamy y=0. Perceptron opisany jest więc jednoznacznie przez zbiór wag w1,...,wn oraz wartość odchylenia b. Schemat działania:
Widzimy, że gdy perceptron osiągnie pewien stan nasycenia (tzn. suma ważona wejść przekroczy wartość 0), wyjście skokowo zmienia swą wartość z 0 na 1. Pożądane działanie perceptronu osiągamy, dobierając właściwie wagi i wartość progową. Zobaczmy, jak można zasymulować działanie prostych bramek logicznych (wartości wag umieszczone są obok odpowiednich wejść):
Na następnym wykładzie poznamy bliżej uogólnienie pozwalające otrzymywać na wyjściu nie tylko wartość binarną 0 lub 1, ale też dowolne liczby rzeczywiste z przedziału [0,1]. Uogólnienie to polega na wprowadzeniu "łagodnego" progu (por. rysunek poniżej); nadal jednak zależność między wartościami wejść a wyjściem jest nieliniowa.
Zbiór możliwych stanów wejściowych perceptronu o n wejściach można utożsamiać z przestrzenią Rn, czyli w przypadku perceptronu o dwóch wejściach - z płaszczyzną. Zastanówmy się, gdzie na tej płaszczyźnie będą znajdowały się punkty zaklasyfikowane przez perceptron jako 0 i 1. Równanie perceptronu można potraktować jako równanie prostej oddzielającej (zw. prostą decyzyjną) (ogólnie: hiperpłaszczyzny w przestrzeni n-wymiarowej). Punkty leżące na obszarze, gdzie skieruje wektor normalny n klasyfikujemy jako 1, zaś pozostałe jako 0.
Równanie tej prostej wynika bezpośrednio ze wzoru perceptronu - por. rysunek obok. O położeniu prostej decydują wartości wag i wartość progowa.
Pojedynczy perceptron nie potrafi w związku z tym odróżniać zbiorów nieseparowalnych liniowo, tzn. takich, że między punktami z odpowiedzią pozytywną i negatywną nie da się poprowadzić prostej rozgraniczającej. Jednym z najprostszych przykładów takich zbiorów jest funkcja logiczna XOR (alternatywa wykluczająca). Jak widać na poniższych rysunkach, funkcje AND i OR dają zbiory separowalne liniowo, a więc możliwe do realizacji perceptronem (o czym przekonaliśmy się już w poprzednim rozdziale).
Odkrycie tych ograniczeń (1969) na wiele lat zahamowało rozwój sieci neuronowych. Oczywistym sposobem na ominięcie tych ograniczeń jest budowa bardziej złożonej struktury sieci, tzn. połączenie wielu perceptronów (już dwa wystarczają, by zrealizować XOR). Wtedy jednak znacznie trudniej jest taką sieć dostosować do naszych potrzeb. Dopiero opracowanie skutecznych sposobów uczenia sieci perceptronów, tzn. automatycznego doboru ich wag na podstawie listy przypadków pozytywnych i negatywnych, pozwoliło na szersze stosowanie sieci neuronowych w praktycznych, złożonych zadaniach decyzyjnych i aproksymacyjnych.
Omówiono dwa wybrane kierunki związane z zagadnieniami sztucznej inteligencji: problemy optymalizacji (dyskretnej) i problemy aproksymacji, rozumiane ogólnie jako problem ekstrakcji wiedzy z danych. Przykładem narzędzia przydatnego do drugiego z wymienionych celów są sieci neuronowe, które po wstępnej prezentacji na tym wykładzie zostaną szczegółowo omówione na następnych.
Zalecana literatura:
Szczegółowe definicje znajdują się w treści wykładu (słowa kluczowe zaznaczone są na czerwono).
dane treningowe - znane przykłady, na podstawie których próbujemy znaleźć zasadę ogólną
funkcja celu - optymalizowana funkcja rzeczywista
perceptron - prosty model naturalnego neuronu, jego działanie polega na ważonym sumowaniu sygnałów wejściowych i nieliniowym (np. progowym) przekształceniu ich w wartość wyjściową
przestrzeń stanów - zbiór wszystkich możliwych rozwiązań zadania, wśród których szukamy najlepszego
separowalność liniowa - cecha zbiorów w przestrzeni Rn oznaczająca, że istnieje prosta (płaszczyzna itp.) rozdzielająca dwa zbiory
wagi połączeń - parametry perceptronu, przez które mnożymy wartość sygnałów wejściowych
wartość progowa - parametr perceptronu wyznaczający granicę, powyżej której perceptron jest wzbudzony (tzn. ma na wyjściu wartość 1)
zadanie aproksymacji - zadanie polegające na odgadnięciu kształtu funkcji na podstawie zbioru jej przykładowych wartości
zadanie optymalizacji - zadanie polegające na szukaniu minimum lub maksimum pewnej funkcji
2.1. Dane jest zadanie optymalizacyjne: "Na szachownicy rozstawić jak największą liczbę skoczków w taki sposób, żeby jak najmniej z nich wzajemnie się biło". Jaka jest wielkość przestrzeni stanów?
2.2. Jaka jeszcze funkcja logiczna (poza XOR) nie jest realizowalna za pomocą perceptronu?