Inne Podej�cie Do Uzasadnienia I Reprezentacji

Rozwi�zywanie problem�w zwi�zanych z satysfakcj� z ogranicze�

Opr�cz metod wnioskowania opartych na sieciach logicznych lub semantycznych zbadano kilka innych technik. W tej sekcji opiszemy klas� problem�w zwanych problemami z ograniczeniami (lub problemami z przypisaniem) i metodami ich rozwi�zywania. W tych problemach mamy zestaw obiekt�w, kt�rym nale�y przypisa� warto�ci spe�niaj�ce zestaw ogranicze�. Widzieli�my ju� jeden przyk�ad problemu z przypisaniem - przypisywania etykiet do linii na obrazie. W tym problemie ograniczenie polega na tym, �e ka�dej linii na obrazie mo�na przypisa� jedn� i tylko jedn� etykiet�. Ograniczenia mo�na wyrazi� w postaci relacji z bazami danych, wzor�w logicznych, r�wna� lub nier�wno�ci. Dlatego problemy zwi�zane z satysfakcj� z ogranicze� pojawiaj� si� naturalnie w wielu ustawieniach, w tym w harmonogramie, symulacji, wizji komputerowej i robotyce. (Arkusz kalkulacyjny jest na przyk�ad prostym systemem spe�niania ogranicze�.) Na szcz�cie istniej� pewne og�lne metody rozwi�zywania tych problem�w, kt�re s� niezale�ne od aplikacji. Zilustruj� jedn� z takich metod ma�ym przyk�adem. Rozwa� problem z umieszczeniem czterech kr�lowych na szachownicy 4 x 4 w taki spos�b, aby �adna kr�lowa nie mog�a z�apa� �adnej innej. W problemie Four-Queens mamy cztery obiekty, c₁; c₂, c₃ i c₄, reprezentuj�ce odpowiednio kolumny od 1 do 4, w kt�rych mo�na umie�ci� kr�low�. Ka�dy z tych obiekt�w mo�e mie� jedn� z czterech warto�ci 1, 2, 3 lub 4, odpowiadaj�cych numerom wierszy. Na przyk�ad, gdy c3 ma warto�� 2, kr�lowa jest umieszczana w drugim rz�dzie trzeciej kolumny.

Problem Four-Queens ogranicza warto�ci tych zmiennych

Na przyk�ad, je�li c₁ ma warto�� 1, c₂ nie mo�e mie� warto�ci 1 lub 2; c₃ nie mo�e mie� warto�ci 1 lub 3; oraz c₄ nie mo�e mie� warto�ci 1 lub 4. Wi�zy s� reprezentowane jako wykres zwany wykresem ogranicze�. Ka�dy w�ze� na tym wykresie jest oznaczony nazw� obiektu wraz z zestawem wszystkich warto�ci tego obiektu. Powietrze w�z��w jest po��czone �ukiem (kraw�dzi�, kt�ra ma kierunek), je�li mo�liwe warto�ci obiektu na ko�cu �uku s� ograniczone przez dowoln� z warto�ci obiektu na szczycie �uku. Przyk�ad takiego wykresu dla problemu Czterech Kr�lowych pokazano poni�ej

W tym problemie ka�dy obiekt ogranicza wszystkie pozosta�e, wi�c wszystkie w�z�y maj� �uki do wszystkich pozosta�ych w�z��w. (Aby to nie by�o za�miecone, reprezentuj� dwa r�ne �uki za pomoc� jednej linii ze strza�kami na ka�dym ko�cu). Zaczynamy od przypisania warto�ci do jednego z obiekt�w. To przypisanie jest warto�ci� "pr�bn�" i pocz�tkiem procesu wyszukiwania. Je�li to nie zadzia�a, b�dziemy musieli cofn�� si� i wypr�bowa� inn� warto��. Za��my, �e zaczynamy od przypisania warto�ci 2 do obiektu c₁ (odpowiadaj�cego umieszczeniu kr�lowej w kolumnie 1, wiersz 2). Teraz iteracyjnie badamy wszystkie �uki na rycsunku i eliminujemy dowoln� warto�� obiektu na ogonie �uku, kt�ry jest niesp�jny (zgodnie z wi�zi) ze wszystkimi warto�ciami na pocz�tku �uku. Proces ten, zwany propagacj� ogranicze�, zatrzymuje si�, gdy nie mo�na ju� wyeliminowa� �adnych warto�ci. Kilka pierwszych krok�w tego procesu mo�e wygl�da� nast�puj�co:

1. Najpierw sp�jrz na �uk od c2 do c1: Mo�emy wyeliminowa� c₂ = 1, c₂ = 2 i c₂ = 3, poniewa� ka�da z tych warto�ci jest niezgodna z warto�ciami (jest tylko jedna) c₁.

2. Nast�pnie sp�jrz na �uk od c₃ do c₁: Mo�emy wyeliminowa� c₁ = 2 i c₁ = 4.

3. Nast�pnie sp�jrz na �uk od c₄ do c₁: Mo�emy wyeliminowa� c₁ = 2.

Wyeliminowanie niekt�rych warto�ci, tak jak w�a�nie to zrobili�my, czyni jeszcze wi�cej warto�ci podatnymi na eliminacj�. Ponowne odwiedziny �uk�w w celu ponownego sprawdzenia sp�jno�ci ujawni�, kt�re z nich. Mo�na powiedzie�, �e eliminacja warto�ci "propaguje" si� na wykresie ogranicze�. Kontynuacja procesu propagacji eliminuje wszystkie warto�ci opr�cz jednej warto�ci dla ka�dego w�z�a. W tym momencie wszystkie �uki s� sp�jne i nie mo�na ju� wyeliminowa� �adnych warto�ci. Wykres pokazany na rysunku poni�ej pokazuje, jak mo�e przebiega� proces, zaczynaj�c od warto�ci pozosta�ych po wykonaniu trzech wymienionych kroki.

W tym przypadku propagacja ogranicze� rozwi�za�a problem (bior�c pod uwag�, �e zacz�li�my od c₁ = 2, zgadywanka). Umieszczenie czterech kr�lowych pokazano tu

Ten proces radzenia sobie z problemami zwi�zanymi z satysfakcj� z ogranicze� jest oparty na AC-3 (skr�t od Arc Consistency Algorytm nr 3), algorytmie zaproponowanym przez Alana K. Mackwortha, profesora na University of British Columbia . Mackworth kontynuowa� prace nad problemami zwi�zanymi z ograniczeniami i ich zastosowaniami w robotyce i kontroli agent�w. (Zaproponowa� r�wnie� i zbudowa� pierwsze roboty do gry w pi�k� no�n�).` Zaproponowano r�ne rozszerzenia i ulepszenia AC-3. Zosta�o to dobrze opisane w ksi��ce Riny Dechter (kt�ra wnios�a znacz�cy wk�ad w sam� eld�) oraz w rozdziale pi�tym tekstu Russella i Norviga. Artyku� Vipina Kumara analizuje ca�� dziedzin�. Firmy komercyjne, takie jak ILOG (przejmowane przez IBM), rutynowo u�ywaj� j�zyk�w programowania z ograniczeniami w aplikacjach obejmuj�cych planowanie i symulacj�. Przyk�ad Four-Queens, kt�rego u�y�em do zilustrowania propagacji ogranicze�, znalaz� rozwi�zanie bez wyszukiwania (poniewa� zacz��em od wyboru c₁= 2). Gdybym jednak pocz�tkowo wybra� c₁ = 1, propagacja ogranicze� wyeliminowa�aby wszystkie warto�ci we wszystkich w�z�ach, wskazuj�c, �e nie ma rozwi�zania problemu Czterech Kr�lowych z kr�low� w kolumnie 1, wiersz 1. (You s� zaproszeni do sprawdzenia tego.) Dokonanie tego wyboru i stwierdzenie, �e nie ma wtedy rozwi�zania, wymaga�oby wy�szego poziomu procesu wyszukiwania, aby cofn�� si�, aby wypr�bowa� inn� warto��. Mo�liwe jest r�wnie�, �e selekcja pr�bna, po kt�rej nast�pi propagacja ogranicze�, pozostawi�aby nierozwi�zane warto�ci niekt�rych obiekt�w. W takim przypadku nale�a�oby dokona� wyboru warto�ci jednego z tych obiekt�w, po czym nast�pi�aby wi�ksza propagacja ogranicze�, mo�liwe cofanie si� itd. Zatem rozwi�zanie problem�w zwi�zanych z satysfakcj� z ogranicze� zwykle wymaga przeszukiwania, a kilka procedur cofania zosta�o zaproponowanych i wykorzystanych.

Rozwi�zywanie problem�w za pomoc� logiki zda�

Wa�nym szczeg�lnym przypadkiem reprezentacji i rozumowania wiedzy logicznej jest przypadek, w kt�rym �adna z formu� logicznych nie zawiera zmiennych. Chocia� ten przypadek nie m�g� mie� formu� takich jak (∀x) [Man (x) ⊃ Mortal (x)], m�g� mie� formu�y takie jak [Man (Socrates) ⊃ Mortal (Socrates)] i [Man (Plato) ⊃ Mortal ( Plato)] i tak dalej. Poniewa� nie ma zmiennych, ten szczeg�lny przypadek jest zasadniczo taki sam jak logika zda�. Wynika to z tego, �e wyra�enia takie jak Cz�owiek (Sokrates) i �miertelny (Sokrates), ilekro� wyst�puj� w bazie wiedzy, mo�na zast�pi� twierdzeniami, takimi jak P014 i Q234, kt�re nie maj� wewn�trznej struktury, a zatem s� ca�kowicie niezwi�zane. Wad� ograniczania si� do logiki zda� jest to, �e musieliby�my mie� mo�liwie bardzo du�� liczb� formu� obejmuj�cych wszystkie byty, o kt�rych chcemy rozmawia� {zamiast u�ywa� tylko pojedynczych formu� ze zmiennymi obejmuj�cymi je wszystkie. Zalet� kompensuj�c� jest jednak to, �e opracowano niezwykle silne metody rozumowania z bardzo du�� liczb� formu� zda�. Zilustruj� dzia�anie tych metod za pomoc� prostej logicznej �amig��wki. zak�adaj�, �e w�r�d zaproszonych na przyj�cie s� trzy raczej k�opotliwe osoby Ann, Bill i Charlie. Przyjaciel, kt�ry zdaje sobie spraw� z dynamiki spo�ecznej w�r�d tych os�b, informuje gospodyni�, �e przynajmniej jeden z tych go�ci na pewno b�dzie uczestniczy�, ale je�li Ann we�mie udzia�, Bill nie we�mie udzia�u, a je�li Bill we�mie udzia�, Charlie nie we�mie udzia�u, a je�li Charlie we�mie udzia� Ann nie. Czy na podstawie tych informacji gospodyni mo�e dowiedzie� si�, kto mo�e wzi�� udzia�? Gdyby by�a logikiem, mog�aby przekszta�ci� informacje o swojej przyjaci�ce w nast�puj�cy zestaw formu� w logice zda� (gdzie A oznacza "Ann jest nadchodzi "i tak dalej):

A ∨ B∨ C;
¬ A ∨ ¬ B;
¬PNE;
¬ C ∨ ¬ A:

Przypomnij sobie z mojego wcze�niejszego u�ycia formu� logicznych, �e "¬" oznacza "nie" i �e "∨" oznacza "lub". Formu�y takie jak te, kt�re sk�adaj� si� ze zda� (lub ich negacji) po��czonych znakami "lub", nazywane s� "klauzulami". Poszczeg�lne pozycje same w sobie nazywane s� "zmiennymi", poniewa� ich warto�ci prawdy nie zosta�y jeszcze przypisane. Aby rozwi�za� sw�j problem, nasza gospodyni musi dowiedzie� si�, jak przypisa� warto�ci prawdy (T lub F) do trzech zda� A, B i C, tak aby wszystkie klauzule maj� warto�� T (poniewa� pochodz� z twierdze� uznanych za prawdziwe). Je�li klauzula ma warto�� T, logik powiedzia�by, �e jest "satysfakcjonuj�ce" . Na przyk�ad, je�li A ma warto�� T, co oznacza, �e Ann nadchodzi, pierwsza klauzula by�aby spe�niona (bez wzgl�du na warto�ci B i C ). Logicy i informatycy wymy�lili sposoby rozwi�zania tego problemu , czy istnieje przypisanie warto�ci prawdy do zmiennych w zestawie klauzul, tak aby wszystkie klauzule by�y spe�nione i jakie mog� by� te warto�ci. Trudno�� polega na tym, �e problem okre�lania zdolno�ci satis, zwany "problemem SAT", jest NP-zupe�ny, co oznacza, �e w najgorszym przypadku czas potrzebny wszystkim znanym algorytmom na rozwi�zywanie problem�w SAT ro�nie wyk�adniczo wraz z rozmiarem problem. Oczywi�cie problem, z kt�rym boryka si� nasza gospodyni, nie jest du�ym problemem i nie mia�aby trudno�ci z jej rozwi�zaniem, po prostu wypr�bowuj�c (tylko) osiem mo�liwych sposob�w przypisania warto�ci prawdy A, B i C, aby odkry�, kt�ry z tych o�miu ( je�li w og�le) spe�nia wszystkie jej klauzule. Ale wiele problem�w obliczeniowych zakodowanych jako zestawy klauzul mo�e obejmowa� setki tysi�cy klauzul zawieraj�cych tysi�ce zmiennych. Takie problemy by�yby trudne do rozwi�zania w przypadku metody pr�b i b��d�w. Na szcz�cie opracowano bardziej wydajne metody, kt�re rzeczywi�cie s� w stanie rozwi�za� bardzo du�e problemy. W rzeczywisto�ci Bart Selman, jeden z wynalazc�w niekt�rych z tych bardziej wydajnych metod, m�wi: "&helli. obecne solwery mog� rozwi�za� instancje za pomoc� jednego lub wi�cej zmiennych i kilku milion�w klauzul". Co wi�cej, twierdzi, �e nie jest to "wynik szybszego sprz�tu … to w rzeczywisto�ci 95% wynik lepszych algorytm�w. Nadal mamy do czynienia z problemem NP-zupe�no�ci i wyk�adnicz� przestrzeni� wyszukiwania. Zatem ulepszenia sprz�towe bez pomys�y algorytmiczne nie maj� zbyt du�ego wp�ywu ". Istniej� dwa g��wne typy metod rozwi�zywania problem�w SAT. Jedna klasa sk�ada si� z tak zwanych metod systematycznych, a druga klasa zawiera tak zwane lokalne metody wyszukiwania. W rzeczywisto�ci niekt�re z najlepszych solver�w wykorzystuj� techniki z obu tych dw�ch metod.

Metody systematyczne

Wi�kszo�� metod systematycznych opiera si� na procedurze zwanej algorytmem DPLL i jej r�nymi ulepszeniami. (Algorytm DPLL wywodzi si� z wcze�niejszego algorytmu, algorytmu DP, zaproponowanego przez Martina Davisa i Hilary Putnam.) Algorytm DPLL dzia�a poprzez przeszukanie drzewa mo�liwych sposob�w przypisania warto�ci prawdy do zmiennych. W ka�dym w�le drzewa wyszukiwania do zmiennej przypisywana jest warto�� T wzd�u� jednej ga��zi i warto�� F wzd�u� innej ga��zi. Te przypisania konwertuj� zestaw klauzul w w�le na nowe zestawy w dw�ch nast�pnych w�z�ach za pomoc� nast�puj�cego procesu uproszczenia:

1. W ka�dej klauzuli zast�p zmienn� w�a�nie przypisan� przez T lub F, w zale�no�ci od branej ga��zi.
2. Wyeliminuj te klauzule, kt�re zawieraj� T lub a: F. (Te klauzule s� jest ju� spe�niony przez to zadanie).
3. Wyeliminuj dowolne: litery T lub F. ze wszystkich klauzul, w kt�rych si� pojawiaj�. (Dla zestaw klauzul, kt�re maj� by� spe�nione, przynajmniej jedna z pozosta�ych zmiennych w tych klauzulach musi mie� warto�� T.)
4. Dla ka�dej klauzuli, kt�ra zawiera tylko jedn� zmienn�, ustaw t� zmienn� na warto��, kt�ra spe�ni t� klauzul� i kontynuuj uproszczenie, je�li to mo�liwe.
DPLL ko�czy si�, gdy wyst�pi jeden lub drugi z nast�puj�cych warunk�w:

i. Je�li uzyskany zestaw klauzul jest pusty, DPLL zani�a, po ustaleniu, �e oryginalny zestaw klauzul jest satysfakcjonuj�cy i �e przypisane dot�d warto�ci prawdy spe�niaj� te klauzule.
ii. Je�li kt�rakolwiek z klauzul pojawiaj�cych si� wzd�u� ga��zi drzewa jest pusta (to znaczy, �e nie ma ju� zmiennych, aby spr�bowa� j� spe�ni�), to DPLL ustali�o, �e oryginalny zestaw klauzul jest niezgodny z prawd�, �e zosta�y przydzielone do tej pory wzd�u� tej ga��zi. W takim przypadku wyszukiwanie jest kontynuowane wzd�u� innej ga��zi drzewa, je�li nadal istniej� zmienne z nieprzypisanymi warto�ciami prawdy. Je�li nie, DPLL posiada ustalono, �e oryginalny zestaw klauzul nie jest satysfakcjonuj�cy.

Jako przyk�ad przyjrzyjmy si� drzewu, kt�re by�oby zwi�zane z moim problemem "kto przyjdzie na obiad". Na rysunku pokazano cz�� drzewa wyszukiwania, kt�ra zosta�aby stworzona przez przypisanie warto�ci prawdy (w kolejno�ci A, B i C) i uproszczenie.

Jedn� interesuj�c� rzecz�, na kt�r� nale�y zwr�ci� uwag� w tym przyk�adzie, jest to, �e w zale�no�ci od kolejno�ci wyszukiwania, DPLL mo�e (i zwykle robi) zako�czy� dzia�anie, zanim wszystkie ga��zie drzewa wyszukiwania zostan� zbadane. Szansa na szybkie zako�czenie jest zwi�kszona przez wykonanie dog��bnego (zamiast szerokiego) wyszukiwania. DPLL osi�ga wysok� wydajno�� i szybko��, wykorzystuj�c to, co informatycy nazywaj� "rekurencyjnym wyszukiwaniem wstecznym". Dalsze udoskonalenia DPLL zaowocowa�y znacznie szybszymi i pot�nymi globalnymi metodami rozwi�zywania problem�w SAT. Ulepszenia te polegaj� na zwi�kszeniu "inteligencji" cofania si� poprzez zastosowanie mechanizm�w zwanych "uczeniem si� klauzul" i wykorzystanie niekt�rych strategii stosowanych przez lokalne metody wyszukiwania. Witryna internetowa jednego z tych program�w, o nazwie zChaff, twierdzi \ Mamy historie sukces�w w u�ywaniu zChaff do rozwi�zywania problem�w z ponad milionem zmiennych i 10 milionami klauzul. (Oczywi�cie nie mo�e rozwi�za� ka�dego takiego problemu!) "

Lokalne metody wyszukiwania

Lokalne metody wyszukiwania dzia�aj� poprzez wykonanie wyszukiwania podczas wspinania si� na wzg�rze, wprowadzaj�c sekwencj� pojedynczych modyfikacji zestawu losowo wybranych pocz�tkowych warto�ci prawdy dla wszystkich klauzul. W przypadku problem�w SAT ka�dy mo�liwy zestaw warto�ci prawdy odpowiada po�o�eniu w krajobrazie, a liczba spe�nionych klauzul (dla tego zestawu warto�ci prawdy) odpowiada wysoko�ci lub wysoko�ci odpowiedniego po�o�enia. Najwy�sza lokalizacja w krajobrazie (kt�rej mo�e by� wi�cej ni� jedna) odpowiada maksymalnej liczbie klauzul, kt�re mo�na spe�ni� (kt�re by�yby wszystkie, gdyby zbi�r klauzul by� wystarczaj�cy). W 1992 r. Bart Selman (1959 {; ryc. 27.6), Hector Levesque i David Mitchell (1957 {; ryc. 27.6) wprowadzili metod� atakowania problem�w SAT o nazwie GSAT.10 (\ G "oznacza chciwo��, a my Zobacz�, dlaczego w komentarzu.) GSAT i jego r�ne rozszerzenia, takie jak WALKSAT, zosta�y z powodzeniem zastosowane do problem�w z a� 200 000 zmiennych. GSAT przeprowadza lokalne poszukiwania wspinaczkowe po krajobrazie warto�ci prawdy. W formie konspektu, oto jak to dzia�a. Zaczyna si� od losowego przypisania warto�ci prawdy i ocenia, ile klauzul spe�nia to przypisanie. Je�li to zaspokajajac je wszystkie, proces ko�czy si� rozwi�zaniem. W przeciwnym razie zmienia kolejno warto�� prawdy ka�dego zdania. Wybiera odwr�cenie, kt�re powoduje najwi�kszy ("najbardziej zach�anny") wzrost liczby klauzul spe�nianych, a wyszukiwanie lokalne jest kontynuowane na podstawie nowego zestawu warto�ci prawdy (z warto�ci� odwr�con�). Cz�sto zdarza si�, �e �aden pojedynczy adres IP nie mo�e zwi�kszy� liczby spe�nionych klauzul. Mimo to zwykle s� to klapki, kt�re przynajmniej utrzymuj� t� liczb�. W takim przypadku GSAT wybiera jeden z nich (losowo) i robi odpowiedni krok na osi�gni�tym "p�askowy�u", maj�c nadziej�, �e mo�e p�niej wznowi� wspinaczk� pod g�r�. Lub mo�e by� tak, �e wszystkie mo�liwe kroki podj�te w krajobrazie b�d� z g�rki. (W jednym artykule opisuj�cym te lokalne techniki stwierdzono, �e taki wynik "prawie nigdy nie wyst�puje".) W tym rzadkim przypadku GSAT z pewno�ci� osi�gn�� najwy�szy mo�liwy poziom i osi�gn�� "lokalne maksimum". W niekt�rych aplikacjach przypisanie warto�ci prawdy, kt�ra nie spe�nia wszystkich klauzul, mo�e by� przydatne i dopuszczalne, ale je�li nie, GSAT mo�na "zrestartowa�" przy u�yciu innego zestawu losowych przypisa� prawdy z nadziej�, �e wi�kszy lokalny maksimum mo�na uzyska� w nowym trawersie. W ka�dym razie GSAT nak�ada ograniczenia na liczb� przewr�ce� , �e pr�buje, aby nie w�drowa� bez ko�ca po p�askowy�u. Poniewa� problem SAT og�lnie jest NP-zupe�ny, mo�liwe jest znalezienie problem�w, dla kt�rych metody lokalne (lub dowolne metody) zaj�yby wyk�adniczy czas, ale autorzy GSAT twierdz�, �e takie problemy "wydaj� si� niezwykle rzadkie, i nie wyst�puj� naturalnie w aplikacjach, kt�re zbadali�my. " Oto, w jaki spos�b GSAT mo�e rozwi�za� nasz problem "kto przyjdzie na obiad", kt�rego zdania s� powtarzane tutaj:

A∨ B ∨ C;
¬ A ∨¬ B;
¬PNE;
¬ C ∨ ¬A:

Wybiera losowy zestaw warto�ci prawdy, powiedzmy T dla A, T dla B i T dla C. Ten zestaw spe�nia tylko jedn� klauzul�, mianowicie A ∨ B ∨ C. Gdyby GSAT mia� odwr�ci� dowoln� z warto�ci prawdy (od T do F), trzy klauzule by�yby spe�nione - wszystkie du�e kroki "pod g�r�". Za��my, �e GSAT decyduje si� na zmian� warto�ci A, co skutkuje spe�nieniem pierwszej, drugiej i ostatniej klauzuli. Zmiana warto�ci B lub C powoduje, �e wszystkie cztery klauzule s� spe�nione - ka�dy krok w g�r� do rozwi�zania. Za��my, �e tak przewraca warto�� B. W takim przypadku GSAT znalaz�by jedno rozwi�zanie, a mianowicie F dla A, F dla B i T dla C. (Logicznie sk�onny czytelnik zauwa�y�by, �e w rzeczywisto�ci istniej� trzy rozwi�zania, odpowiadaj�ce jednemu z trzej zaproszeni s� jedynymi uczestnikami w�r�d nich. Oczywi�cie gospodyni nie by�aby w stanie zdecydowa� mi�dzy tymi trzema, ale przynajmniej wiedzia�aby, ile miejsc usi�� przy jej stole.) Nic dziwnego, �e GSAT znalaz�o rozwi�zanie za ten ma�y problem. W rzeczywisto�ci w przypadku du�ych losowo generowanych problem�w, gdy liczba zmiennych (A, B i C) jest znacznie mniejsza ni� liczba klauzul, prawdopodobnie istnieje wiele satysfakcjonuj�cych przypisa� prawdy i GSAT (a tak�e innych metod ) prawdopodobnie znalaz�oby rozwi�zanie. Jednak gdy liczba zmiennych jest znacznie wi�ksza ni� liczba klauzul, prawdopodobnie nie ma w og�le �adnych rozwi�za�. Jednym z wa�nych rozszerze� GSAT jest WALKSAT (czasem nazywany WSAT), w kt�rym zamiast zawsze zmienia� warto�� prawdy tej propozycji, prowadz�c do najwi�kszego wzrostu liczby spe�nionych klauzul, czasami dokonuje si� losowego wyboru. Dodanie niewielkiej ilo�ci losowo�ci pomaga unikn�� utkni�cia w lokalnych maksimach krajobrazu. Por�wnuj�c globalne i lokalne metody wyszukiwania, Bart Selman twierdzi: "Lokalne metody wyszukiwania s� nadal konkurencyjne w wielu domenach, ale ... poniewa� metody DPLL s� mniej wra�liwe na kodowanie roblem, s� one obecnie cz�ciej wykorzystywane do rozwi�zywania problem�w strukturalnych [takich jak sprz�t i weryfikacja oprogramowania]. " M�wi jednak, �e u�ycie losowo�ci i ponowne uruchomienie w DPLL… [wprowadza niekt�re] niesystematyczne aspekty wyszukiwania lokalnego do DPLL.

Zastosowania solver�w SAT

Kilka wa�nych problem�w mo�na zakodowa� jako problemy SAT. Na przyk�ad Henry Kautz i Bart Selman wykazali, �e wygenerowanie planu dzia�a� mo�na wyrazi� jako problem SAT. SATPLAN i Blackbox to dwa systemy, kt�re koduj� zadania planowania jako problemy SAT, a nast�pnie wykorzystuj� solwery SAT do tworzenia plan�w. SATPLAN zaczyna si� od specjalnie opracowanych formu� logicznych opisuj�cych efekty dzia�a�, a Blackbox zaczyna si� od regu� planowania STRIPS. (Przypomnicie sobie system automatycznego planowania STRIPS, kt�ry opisa�em w rozdziale 12.1.3.) Wed�ug Bart Selman, solwery SAT pracuj�ce na logistyce. Na przyk�ad problemy z planowaniem mog� stworzy� optymalne plany oko�o 500 krok�w w ci�gu kilku minut. Ostatnie wersje system�w planowania opartych na SAT zdoby�y pierwsze miejsca w dwuletnich Mi�dzynarodowych Konkursach Planowania. Skuteczne solwery SAT zosta�y r�wnie� zastosowane do problem�w z weryfikacj� program�w i obwod�w cyfrowych oraz w genomice. Blisko spokrewniony temat obejmuje tak zwane "binarne schematy decyzyjne"(BDD) u�ywane w weryfikacji projekt�w uk�ad�w logicznych.

Reprezentowanie tekstu jako wektor�w

Poprzednio opisa�em systemy odpowiadaj�ce na pytania, w kt�rych pytanie jest konwertowane na posta� zarz�dzaln� obliczeniowo (by� mo�e na formu�� logiczn�), kt�ra jest nast�pnie u�ywana do przeszukiwania komputerowej bazy danych (by� mo�e bazy wiedzy o formu�ach logicznych). Prawdopodobnie najbardziej znane przyk�ady odpowiedzi na pytania maj� dzi� miejsce w wyszukiwarkach internetowych. Osoba AI o przekonaniu logika mo�e mie� nadziej�, �e ostatecznie tekst na stronach internetowych mo�e by� reprezentowany jako logiczne formu�y i �e zapytanie mo�e by� reprezentowane jako logiczna formu�a, na kt�r� nale�y odpowiedzie� (udowodni�) na podstawie formu� w jednej (lub wi�cej) z tych sieci strony. Istniej� pewne pocz�tkowe pr�by odpowiedzi w ten spos�b na zapytania w j�zyku angielskim, ale wi�kszo�� wyszukiwarek internetowych stosuje prostsze i bardziej skuteczne techniki. Dam og�lny obraz dzia�ania niekt�rych z nich. Konwertuj� tekst w dokumentach i zapytaniach na wektory i por�wnuj� wektor zapyta� z konkurencyjnymi wektorami dokument�w. Najpierw opowiem kilka rzeczy o wektorach, a nast�pnie opisz�, jak tekst mo�e by� reprezentowany jako wektor. (Przypomnicie wam moje wcze�niejsze dyskusje na temat zastosowania wektor�w w rozpoznawaniu wzor�w.) W matematyce wektor jest wielko�ci� o wielko�ci i kierunku. Na przyk�ad w przestrzeni tr�jwymiarowej jeden przedstawia wektor jako strza�k� wyci�gni�t� z pocz�tku tej przestrzeni do punktu w tej przestrzeni. Strza�ka wskazuje kierunek wektora, a d�ugo�� strza�ki jest wielko�ci� wektora. Poniewa� punkt okre�la wektor (istnieje tylko jeden spos�b na narysowanie strza�ki od pocz�tku do punktu), s�owa "punkt" i "wektor" s� cz�sto u�ywane synonimicznie. Ka�d� uporz�dkowan� list� number mo�na traktowa� jako wsp�rz�dne punktu, a zatem jako elementy wektora. Na przyk�ad lista (7; 4; 3; 20) to wektor, jeden w przestrzeni czterowymiarowej. Mo�na mie� wektory o wielu wymiarach; wektory u�ywane do reprezentowania dokument�w mog� mie� tysi�ce wymiar�w. D�ugo�� wektora jest pierwiastkiem kwadratowym sumy kwadrat�w wszystkich sk�adnik�w wektora. (W przypadku wektor�w dwuwymiarowych obliczenie to jest po prostu zastosowaniem twierdzenia Pitagorasa, a mianowicie kwadrat d�ugo�ci przeciwprostok�tnej tr�jk�ta prostok�tnego jest sum� kwadrat�w jego bok�w.) Na przyk�ad d�ugo�� wektora (7; 4; 3; 20) s 21,77. Mo�na zmierzy� podobie�stwo mi�dzy dwoma wektorami albo przez obliczenie odleg�o�ci mi�dzy ich punktami ko�cowymi (by� mo�e dostosowanymi w celu uwzgl�dnienia ich d�ugo�ci) lub przez "niewielko��" k�ta mi�dzy ich dwoma kierunkami - im mniejszy k�t, tym bardziej podobne s� wektory. W metodzie k�towej wykonuje si� nast�puj�ce obliczenia podobie�stwa: Pomn� ka�dy sk�adnik jednego z wektor�w przez odpowiedni sk�adnik drugiego wektora, a nast�pnie dodaj wszystkie te produkty. Nast�pnie podziel t� sum� przez iloczyn d�ugo�ci ka�dego wektora. Liczba ko�cowa, kt�r� nazwiemy S dla podobie�stwa, mo�e wynosi� co najwy�ej 1, gdy dwa wektory s� dok�adnie wyr�wnane (to znaczy skierowane w tym samym kierunku). Jest 0, gdy dwa wektory s� prostopad�e do ka�dego inne i jest ujemny, gdy wskazuj� w przeciwnych kierunkach. Im bardziej wektory s� podobne, tym bli�sze jest ich obliczenie S. (Czytelnicy zaznajomieni z trygonometri� rozpoznaj� to obliczenie jako cosinus k�ta mi�dzy dwoma wektorami.) Na przyk�ad warto�� S dla wektor�w (7; 4; 3; 20) i (7; 0; 2; 15) mo�na obliczy� jako (49 + 6 + 300) = (21:77 16: 67) = 0: 978, warto�� wskazuj�ca, �e te dwa wektory s� do�� podobne. Jak przekonwertowa� tekst na wektor? Ludzie, kt�rzy brali udzia� w komputerowym wyszukiwaniu dokument�w (tak zwane wyszukiwanie informacji), opracowali metod�. Najpierw wybiera si� uporz�dkowan� list� termin�w (s��w lub fraz) dla zestawu dokument�w reprezentowanych przez wektory. Je�li dokumenty dotycz� sztucznej inteligencji, odpowiednie by�oby kilkaset termin�w, w tym "wyszukiwanie", "heurystyka", "wizja komputerowa" i tak dalej. Je�li wszystkie dokumenty s� w j�zyku angielskim i mog� dotyczy� czegokolwiek, mog� istnie� setki tysi�cy termin�w (w zasadzie wszystkie s�owa w j�zyku angielskim). Zazwyczaj wybranymi terminami s� s�owa kluczowe, tak �e "komputer", "komputery" i "komputer" by�yby obj�te terminem "komputer". (Trzeba uwa�a� na tego rodzaju po��czenie, zwane "wywi�zywaniem si�", aby unikn�� zast�pienia "przep�ywu" terminem "kwiat" itp.) R�wnie� dlatego, �e s�owa takie jak "i", "je�li" i "dlatego" i tak wi�c rzadko dotycz� tre�ci dokumentu, te s�owa nie s� u�ywane jako terminy. Nast�pnie w procesie reprezentowania dokumentu jako wektora liczone s� wszystkie wyst�pienia ka�dego z tych termin�w w dokumencie. Lista tych numer�w wyst�pienia jest nast�pnie sk�adana (w tej samej kolejno�ci co lista termin�w), a ta lista jest wektorow� reprezentacj� dokumentu. Na przyk�ad, je�li termin "wyszukiwanie" w og�le nie wyst�puje w reprezentowanym dokumencie, je�li termin "heurystyczny" wyst�puje siedem razy, a termin "wizja komputerowa" wyst�puje trzy razy, w�wczas lista b�dzie, powiedzmy,

(0; 0; 0; 0; 0; 7; 0; 0; 3; 0; 0;:: :);

gdzie podkre�lone liczby oznaczaj�, ile razy terminy, o kt�rych wspomnia�em, wyst�puj� w tym dokumencie. Oczywi�cie mo�e by� wiele, wiele zer, poniewa� wiele termin�w z wybranej listy termin�w mo�e w og�le nie wyst�powa� w dokumencie, a mo�e by� o wiele wi�cej niezerowych liczb odpowiadaj�cych liczbie przypadk�w, gdy inne terminy wyst�puj� w tym dokumencie . Za��my teraz, �e interesuje nas pytanie "Jakich heurystyk u�ywa si� w wizji komputerowej?" i prze�lij to zapytanie do wyszukiwarki internetowej. Je�li za�o�ymy, �e w zapytaniu (i dokumentach) zastosowano jakie� przetwarzanie wst�pne, aby zmieni� s�owa na ich "p�dy", reprezentacja wektorowa naszego zapytania by�aby

(0; 0; 0; 0; 0; 1; 0; 0; 1; 0; 0;:: :)

Podobie�stwo S mi�dzy naszym zapytaniem a dokumentem, kt�ry w�a�nie rozwa�ali�my, wynosi 10 podzielone przez iloczyn d�ugo�ci dw�ch wektor�w. Warto�� ta zosta�aby por�wnana z warto�ciami podobie�stwa z innymi dokumentami w celu ustalenia, kt�re dokumenty s� najbardziej podobne i dlatego nale�y je pobra� w odpowiedzi na nasze zapytanie. Wszystko to brzmi do�� prosto, ale chocia� podstawowa idea jest prosta, potrzeba kilku opracowa� (i zosta�y one dodane), aby wyszukiwanie dokument�w i internetowe witryny internetowe oparte na tym pomy�le by�y praktyczne i przydatne. Po pierwsze, liczba termin�w w dokumencie jest zazwyczaj dostosowywana w celu uwzgl�dnienia d�ugo�ci tekstu w tym dokumencie. Poniewa� d�u�sze dokumenty mog� zawiera� wzgl�dnie wi�cej wyst�pie� danego terminu, liczba dla danego terminu jest obliczana jako procent ca�kowitej liczby wszystkich termin�w w dokumencie. Po drugie, poniewa� dany termin mo�e by� do�� powszechny w�r�d wszystkich przeszukiwanych dokument�w (a zatem niezbyt przydatny do dyskryminacji), liczba ta jest zmniejszana o czynnik, kt�ry zale�y od og�lnej cz�stotliwo�ci tego terminu w�r�d tych dokument�w. Bardziej wyrafinowane programy pobieraj�ce wykorzystuj� r�wnie� r�ne metody statystyczne do obliczania prawdopodobie�stwa trafno�ci dokumentu w zapytaniu. Innowacja wymy�lona przez Google klasyfikuje witryny internetowe wed�ug szacunk�w zwi�zanych z ich popularno�ci� lub "centralno�ci�". Coraz cz�ciej metody "uczenia maszynowego" (niekt�re z nich zostan� opisane w nast�pnym rozdziale) s� r�wnie� wykorzystywane do poprawy wydajno�ci system�w wyszukiwania i, oczywi�cie, wydajno�� wymaga odpowiednich schemat�w indeksowania i korzystania z wielu tysi�cy komputer�w.

Utajona analiza semantyczna

Niekt�rzy badacze sugeruj�, �e reprezentowanie tekstu jako wektor�w oddaje "znaczenie" tekstu. Jak to mo�liwe, gdy reprezentacje wektorowe s� obliczane tylko na podstawie tego, jak cz�sto r�ne terminy wyst�puj� w dokumentach, a wcale nie w kolejno�ci, w jakiej wyst�puj� te terminy? (W ko�cu znaczenie s�owa "Pies gryzie cz�owieka" jest zupe�nie inne ni� s�owo "Cz�owiek gryzie psa".) Thomas K. Landauer (1932 {: ryc. 27.7) i jego koledzy, najpierw w jego Cognitive Science Research Group w Bell Communications Badania (potomek Bell Laboratories) w po�owie lat 80., a p�niej na University of Colorado, zaproponowa�y oparty na wektorze schemat przechwytywania znaczenia, kt�ry nazywaj� Latent Semantic Analysis (LSA). My�l�, �e potrafi� wyja�ni� podstawowe pomys� bez u�ycia ca�ej matematyki wymaganej przez pe�ny opis. Tutaj, w pomniejszonym przyk�adzie, w zasadzie dzia�a metoda LSA. Za��my, �e mamy do�� d�ugi dokument lub inny materia� tekstowy na okre�lony temat. Dzielimy si� materia� na sekcje, zwane "pasa�ami", o d�ugo�ci oko�o 100 termin�w. Zak�adaj�c, �e s�ownictwo materia�u jest przechwycone przez 1000 termin�w (kt�re mog� sk�ada� si� z pojedynczych s��w lub kombinacji s��w), w�wczas ka�dy z tych fragment�w jest reprezentowany przez wektor 1000-wymiarowy. ( Liczby termin�w stosowane przy konstruowaniu tych wektor�w s� korygowane metodami podobnymi do tych, kt�re ju� wyja�ni�em.) Za��my, �e mamy 100 takich wektor�w. Wizualizacja 1000-wymiarowej przestrzeni, w kt�rej osadzone s� nasze wektory, jest trudna (naprawd� niemo�liwa), ale by� mo�e mo�na sobie przynajmniej wyobrazi�, �e jaka� ni�sza "podprzestrze�" zawiera wszystkie lub wi�kszo�� wektor�w. Pomocne mo�e by� rozwa�enie tr�jwymiarowego przyk�adu pokazanego poni�ej

Na schemacie pokazao pi�� punkt�w le��cych na p�aszczy�nie (przestrze� dwuwymiarowa) w przestrzeni tr�jwymiarowej. Przestrze� dwuwymiarowa jest podprzestrzeni� przestrzeni tr�jwymiarowej. W tej dwuwymiarowej przestrzeni punkty te mo�na przedstawi� za pomoc� wektor�w dwuwymiarowych zamiast wektor�w tr�jwymiarowych. Stosuj�c r�ne z�o�one techniki matematyczne, mo�liwe jest skonstruowanie przestrzeni o ni�szych wymiarach, kt�ra odpowiednio "zawiera" 100 wektor�w (by� mo�e powiedzmy, o przestrzeni 50-wymiarowej). LSA stosuje metody oparte na technice zwanej "Singular Value Decomposition" (SVD), kt�rej szczeg�y nie musz� nas tutaj dotyczy�. Oczywi�cie reprezentacja tych wektor�w w 50 wymiarach b�dzie inna ni� w 1000 wymiarach. Wiele termin�w zwi�zanych z wymiarami w wi�kszej przestrzeni zostaje po��czonych w nowe komponenty w mniejszej przestrzeni. Co wi�cej, wed�ug Landauera i wsp�pracownik�w, to w�a�nie to po��czenie pozwala na wydobycie ukrytego og�lnego znaczenia z oddzielnych fragment�w dokumentu. Jak to wyja�niaj� przyk�ad procesu, "… gdyby�my zmienili wpis w dowolnej kom�rce orygina�u, warto�ci w rekonstrukcji ze zmniejszonymi wymiarami mog� by� zmienione wsz�dzie; jest to matematyczny sens, w kt�rym LSA dokonuje wnioskowania lub indukcji".Przekszta�canie wektor�w w te z mniejsz� liczb� sk�adnik�w zasadniczo ��czy ze sob� wiele termin�w wyst�puj�cych (i nie wyst�puj�cych) w oryginalnych pasa�ach, z kt�rych pochodz� wektory. To po��czenie mo�e by� pomy�lany jako stworzenie "koncepcji" wy�szego poziomu w oparciu o powi�zane terminy. Wyra�enie dokumentu tekstowego w kategoriach tych poj�� (to znaczy w odniesieniu do wektor�w o zmniejszonym wymiarze) wydoby�o, zdaniem ludzi z LSA, zasadnicze " znaczenie "dokumentu. Wektory o zmniejszonym wymiarze mog� ��czy� ze sob� terminy z r�nych sekcji tekstu, je�li wyst�puj� w fragmentach maj�cych podobne znaczenie, nawet je�li nigdy nie wyst�puj� w tym samym fragmencie. Proces LSA umo�liwia obliczenie podobie�stwa mi�dzy dowolnymi dwoma fragmentami dokumentu, powiedzmy przez obliczenie wielko�ci k�ta mi�dzy dwoma odpowiadaj�cymi wektorami o zmniejszonych wymiarach. Wraz z procesem reprezentowania przej�� przez wektory o zmniejszonym wymiarze, metoda LSA wytwarza r�wnie� reprezentacj� ka�dego terminu w ca�ym zestawie termin�w przez wektor maj�cy ten sam zmniejszony wymiar. Korzystaj�c z tej reprezentacji, mo�na r�wnie� obliczy� podobie�stwo mi�dzy dwoma terminami, a tak�e podobie�stwo mi�dzy terminem a fragmentem. Wreszcie sam dokument mo�e by� reprezentowany jako wektor sk�adaj�cy si� ze �redniej jego wektor�w przej�cia. Po takim przedstawieniu mo�na obliczy� podobie�stwo mi�dzy dokumentami. Ten krok jest wykorzystywany w jednej z aplikacji LSA o nazwie "Latent Semantic Indexing" (LSI). Podano, �e metoda LSI oferuje pewne ulepszenia w por�wnaniu ze standardowymi metodami wyszukiwania (chocia� kwestia ta jest nadal kontrowersyjna). LSA by�a u�ywana w kilku ustawienia, w tym eseje oceniaj�ce napisane przez osoby przyst�puj�ce do egzaminu wst�pnego na uczelni�, pomoc uczniom w nauce pisania, pomoc w diagnozowaniu schizofrenii na podstawie werbalizacji pacjent�w oraz tworzenie streszcze� s��w kluczowych. Ponadto, s�u�y do na�ladowania niekt�rych ludzi umiej�tno�ci, takie jak punktacja, a tak�e �rednia liczba os�b zdaj�cych test na synonimowej cz�ci TOEFL (TEst of English as a Foreign ETS Language) i osi�ganie zaliczenia na egzaminie wielokrotnego wyboru przy u�yciu wektor�w z analizy LSA wprowadzaj�cej podr�cznik psychologii Czytelnik mo�e sprzeciwi� si�, �e system LSA do oceniania esej�w mo�e zosta� udaremniony przez kogo�, kto napisa� du�� liczb� odpowiednich s��w w przypadkowej kolejno�ci, bez wyra�ania jakichkolwiek sp�jnych my�li. Landauer odpiera ten zarzut, m�wi�c, �e trudno by�oby "zdoby� dobre s�owa bez napisania dobrego eseju ... Pr�bowali�my pisa� z�e eseje i uzyska� dobre oceny, a czasem mo�emy to zrobi�, je�li naprawd� znamy materia� c�. Naj�atwiejszym sposobem oszukiwania tego systemu jest ci�kie studiowanie, znajomo�� materia�u i napisanie dobrego eseju. " W 1998 r. Landauer i wsp�pracownicy utworzyli Technologie analizy wiedzy (KAT) w celu opracowania aplikacji edukacyjnych LSA. KAT zosta� przej�ty przez Pearson Education w 2004 roku i sprzedaje produkty edukacyjne oparte na LSA produkty takie jak Pearson Knowledge Technologies (PKT). Niekt�rzy badacze zwr�cili uwag�, �e g��wn� si�� metod LSA jest redukcja wymiar�w wektorowych i �e istnieje kilka innych metod (niekt�re z nich s� prostsze ni� te stosowane w LSA) w celu zmniejszenia wymiar�w. W rzeczywisto�ci, w jednym z pierwszych artyku��w na temat LSA, Landauer i Susan Dumais opisuj� analog LSA oparty na sieci neuronowej. Probabilistyczne rozszerzenie Latent Semantic Indexing zosta�o zaproponowane i przetestowane przez Thomasa Hofmanna. Bardziej og�lny model probabilistyczny opracowali David Blei, Andrew Ng i Michael Jordan. Wszelkiego rodzaju modele probabilistyczne zacz�y odgrywa� bardzo znacz�c� rol� w sztucznej inteligencji od p�nych lat 80.

Historia Sztucznej InteligencjiArtificial Intelligence Experts

Inne Podej�cie Do Uzasadnienia I Reprezentacji