Metody Sztucznej Inteligencji Informacje O Przedmiocie Sztuczna

Transcript

Metody sztucznej inteligencji Politechnika Śląska Katedra Podstaw Konstrukcji Maszyn Rok akademicki 2007/08 Informacje o przedmiocie • Strona KPKM: http://kpkm.polsl.pl Informacje dydaktyczne/Semestr IV/ Metody Sztucznej Inteligencji/Strona przedmiotu (ZiIP) Hasło: msiziip36 • Kontakt: Anna Timofiejczuk [email protected] • Konsultacje (s. 458 Wydz. MT): – Poniedziałek – Czwartek Wykład 1 11:15 - 13:15 11:45 - 13:45 • Kolokwium zaliczeniowe: MSI-w1_2007/08_1 03.06.2008 MSI-w1_2007/08_2 Program wykładu 1. Historia sztucznej inteligencji i podstawowe pojęcia. Ujęcie z zastosowaniem inteligentnych agentów. Rozwiązywanie problemów przez przeszukiwanie. 2. Logika pierwszego rzędu. Wnioskowanie w logice pierwszego rzędu. 3. Sposoby reprezentacji wiedzy. Podstawy systemów ekspertowych. 4. Wnioskowanie w warunkach niepewności. Sieci przekonań (Bayesa). Wnioskowanie rozmyte. 5. Sieci neuronowe. Algorytmy genetyczne i ewolucyjne. 6. Inżynieria wiedzy i odkrywanie wiedzy. Rozpoznawanie obrazów. Podstawy robotyki. 7. Kolokwium. MSI-w1_2007/08_3 Sztuczna inteligencja (AI=Artificial Intelligence) Dziedzina wiedzy, która postawiła sobie za cel i przedmiot badań maszyny, które potrafiłyby rozwiązywać zadania, przy zachowaniu których człowiek korzysta ze swojej inteligencji (Marvin Minsky) A.M. Turing Computing Machinery and Intelligence Mind 49, 1950, s.433-460 MSI-w1_2007/08_5 Część I Historia Sztucznej Inteligencji i pojęcia podstawowe MSI-w1_2007/08_4 Dziedziny i zastosowania AI • Percepcja • rozumowanie logiczne • rozpoznawanie obrazów • rozumienie mowy • uczenie maszynowe • odkrywanie nowej wiedzy • Sztuczne sieci neuronowe • teoria gier • tłumaczenie tekstów • automatyczne dowodzenie twierdzeń • malowanie obrazów • pisanie poezji MSI-w1_2007/08_6 1 Inne definicje AI Ekscytująca próba uczynienia komputerów myślącymi maszynami z pamięcią, w pełnym i dosłownym sensie tego pojęcia (Haugeland, 1985) Automatyzacja działań, które łączymy z ludzkim myśleniem, jak: podejmowanie decyzji, myślenie, uczenie się, ... (Bellman, 1978) Sztuka tworzenia maszyn, które wykonują działania wymagające inteligencji wtedy, gdy są wykonywane przez człowieka (Kurzweil, 1990) Badanie, jak można umożliwić komputerom wykonywanie zadań, w których jak dotychczas ludzie są lepsi (Rich & Knigth, 1991) 4 kierunki rozwoju AI Badanie zdolności umysłowych z zastosowaniem modeli obliczeniowych (Charniak & Mc Dermott, 1985) Badanie algorytmów, które umożliwiają spostrzeganie, rozumowanie i działanie (Winston, 1992) Dziedzina badań, poszukująca wyjaśnienia i sposobu emulowania zachowań inteligentnych za pomocą pojęć dotyczących procesów obliczeniowych (Schalkoff, 1990) Dziedzina informatyki dotycząca automatyzacji inteligentnego zachowania (Luger & Stubblefield, 1993) MSI-w1_2007/08_7 Maszyna Turinga (1937) Systemy Systemy myślące w myślące sposób racjonalnie podobny do ludzi Systemy działające podobnie jak ludzie Systemy działające racjonalnie • Wiersze: – górny - procesy myślenia – dolny - sposób działania • Kolumny: – lewa - odnosi się do właściwości człowieka – prawa - określenia z zastosowaniem terminu „racjonalny” MSI-w1_2007/08_8 Test Turinga (1950) Maszyna Turinga nie jest obiektem fizycznym. Jest to abstrakcyjny schemat działania według zadanego algorytmu. Jego istotę oddaje angielskie określenie discrete-state machine, co odpowiada polskiemu terminowi maszyna stanów dyskretnych. Maszyna Turinga była odpowiedzią na problem liczb nieobliczalnych. Test Turinga jest wzorowany na grze „retro” w naśladownictwo (imitation game). W grze uczestniczyły cztery osoby: A (kobieta), B (mężczyzna), C (goniec) i D (sędzia). Zadaniem sędziego było odgadnąć kto jest kim na podstawie zadawanych pytań. Turing zastąpił A maszyną. Celem testu jest odgadnięcie tego czy sędzia rozmawia z maszyną czy człowiekiem. MSI-w1_2007/08_9 Test Turinga (1950) MSI-w1_2007/08_10 Warunki, aby komputer przeszedł test Turinga Test Turinga podaje: operacyjną definicję inteligencji Test określa: Zachowanie inteligentne maszyny na poziomie człowieka we wszystkich zadaniach poznawczych, wystarczających do porozumiewania się z człowiekiem, w taki sposób jak robi to człowiek. • przetwarzanie języka naturalnego (komunikacja z rozmówcą) • reprezentacja wiedzy • automatyczne wnioskowanie z wykorzystaniem zgromadzonych informacji: – do zadawania pytań – do wyciągania wniosków (konkluzji) • uczenie się, adaptacja do nowych okoliczności MSI-w1_2007/08_11 MSI-w1_2007/08_12 2 Naśladowanie myślenia człowieka (1) • przedmiot „modelowania poznawczego” • konieczna znajomość sposobu działania ludzkiego mózgu: – przez introspekcję – przez eksperymenty psychologiczne • Gdyby istniała precyzyjna teoria ludzkiego umysłu, byłoby możliwe opracowanie programu działającego zgodnie z tą teorią Naśladowanie myślenia człowieka (2) • Ujęcie z zastosowaniem praw rozumowania • Pierwowzór: sylogizm Arystotelesa (wzorzec struktur argumentowania, które dają zawsze poprawną konkluzję, pod warunkiem zastosowania poprawnych przesłanek) • Przykład: Sokrates jest człowiekiem; wszyscy ludzie są śmiertelni; dlatego Sokrates jest śmiertelny. MSI-w1_2007/08_13 MSI-w1_2007/08_14 Dwa główne ujęcia AI Ujęcie logicystyczne • Ujęcie logicystyczne bazujące na logice formalnej (będzie przedmiotem większej części wykładów) • Zbudowanie programu logicznego, działającego jak system inteligentny • Problemy: – nie jest łatwe ujęcie nieformalnej wiedzy w wyrażenia rachunku zdań i rach. Predykatów – rozwiązanie praktycznych problemów może wymagać niedostępnych mocy obliczeniowych • Ujęcie z zastosowaniem agentów (krótki opis zawarto w dalszej części wykładu) • Reprezentacja wiedzy i systemy rozumowania ściśle określone i łatwo zrozumiałe MSI-w1_2007/08_15 Ujęcie z zastosowaniem agentów • Działać racjonalnie = osiągnąć cel, gdy są dane przekonania • Agent: jednostka, która spostrzega i działa • Zalety: – ujęcie bardziej ogólne niż stosowanie „praw myślenia” – bardziej podatne na rozwój naukowy • Ograniczona racjonalność MSI-w1_2007/08_17 MSI-w1_2007/08_16 Sztuczna inteligencja Sztuczna inteligencja jest nauką kognitywną. Jest połączeniem wiedzy i metod z zakresu: - filozofii, - matematyki, - psychologii, - lingwistyki, - informatyki. MSI-w1_2007/08_18 3 Podstawy AI (1) Filozofia (428 pne. - obecnie) – Platon - pytanie o algorytm rozróżniania pojęć – Arystoteles - system sylogizmów – Leibnitz (materializm) 1646-1716 - mechaniczny układ do przeprowadzania operacji mentalnych – Hume (empirycyzm) - zasada indukcji – Russel (1872-1970) - logiczny pozytywizm: cała wiedza może być przedstawiona za pomocą teorii logicznych, połączonych ze zdaniami obserwacyjnymi (obserwacje dokonane za pomocą MSI-w1_2007/08_19 czujników) Podstawy AI (3) Psychologia (1879 - obecnie) • behawioryzm (istotne są obiektywne związki: bodziec-odpowiedź; wiedza, przekonania, cele i rozumowanie są nienaukowe) • psychologia poznania (cognitive psychology): Craik (1943) - podstawy agentów bazujących na wiedzy Podstawy AI (2) Matematyka (ok. 800 - obecnie) – al-Khowarazmi: wprowadził algorytm – Boole (1847): formalny język rozumowania logicznego – Frege (1879): logika 1. Rzędu – Tarski (1902-1983): teoria referencji (jak obiekty logiczne odnoszą się do obiektów świata) – Gödel (1931): twierdzenie o niezupełności (w każdym języku umożliwiającym opis własności liczb naturalnych istnieją zdania prawdziwe, które MSI-w1_2007/08_20 są nierozstrzygalne) Podstawy AI (4) • Informatyka (1940 - obecnie) - rozwój środowisk sprzętowych i programowych koniecznych do badań w zakresie AI • Lingwistyka (1957 - obecnie) - rozwój wspólnie z AI: – lingwistyka obliczeniowa – przetwarzanie języka naturalnego MSI-w1_2007/08_21 Historia (1933-1942) która zapoczątkowała AI – Konrad Zuse (1933) – maszyna wykorzystująca potencjał elektryczny – komputer zerowej generacji – John Atanasoft i Clifford Berry (1937-1942) – komputer ABC; zasada działania oparta na arytmetyce binarnej – Howard M. Aiken (1939-1944) – maszyna Mark I z przekaźników elektromagnetycznych. – John Mauchly i Presper Eckert (1940) – ENIAC (Electronic Numerical Integrator and Computer) – George Stibitz (1940) – The Complex Number Calculator; cztery podstawowe działania w systemie dwójkowym, – IMB (1942) – Selective Electronic Calculator MSI-w1_2007/08_23 MSI-w1_2007/08_22 Historia AI (1943-1956) Początki AI – Mc Culloch & Pitts (1943) - model sztucznego neuronu – Turing (1950) – test Turinga – Shannon, Turing (ok. 1950) - programy do gry w szachy – Minsky (1951) - pierwszy komputer neuronowy (3000 lamp + autopilot z B-24; 40 neuronów!!!) – Newell & Simon - LT=Logic Theorist (program komputerowy zdolny do myślenia nienumerycznego) MSI-w1_2007/08_24 4 Historia AI (1952-1969) dynamiczny rozwój Entuzjazm (1957) – Newell & Simon - GPS (General Problem Solver) - pierwszy program myślący „po ludzku” – McCarthy (1958) - LISP (LISt Processing) – Minsky (ok. 1963) - mikroświaty (np. świat klocków) – Rosenblatt (1962) - perceptron (sieć neuronów, która się uczy) • H. Simon: It is not my aim to surprise or shock you - but the simplest way I can summarize is to say that there are now in the world machines that think, that learn and that create. Moreover, their ability to do these things is going to increase rapidly until in a visible future - the range of problems they can handle will be coextensive with the range to which human mind has been applied. MSI-w1_2007/08_25 Historia AI (1966-1974) Dawka realizmu MSI-w1_2007/08_26 Historia AI (1969-1979) Nowe koncepcje • Programy początkowo nie zawierały wiedzy i działały stosując jedynie pewne manipulacje na tekstach (ELIZA) • Wiele problemów okazało się zbyt trudnych lub NP-zupełnych • Stwierdzono fundamentalne ograniczenia związane z podstawowymi strukturami AI (np. neuronów) • Wąskie dziedziny problemowe • Systemy doradcze – MYCIN: diagnostyka chorób krwi i płynu mózgowo-rdzeniowego (450 reguł, uwzględnienie niepewności i sprzecznych opinii ekspertów) – PROSPECTOR: wspomaganie prac wiertniczych – inne skuteczne wdrożenia • Minsky (1975): reprezentacja wiedzy - „ramy” MSI-w1_2007/08_27 Historia AI (1980-1988) AI staje się przemysłem MSI-w1_2007/08_28 Historia AI (1986-obecnie) • Komercyjny system doradczy R1 (Mc Dermott, 1982) • V generacja komputerów (Japonia, 1981) • Sprzedaż 2 mld $ w 1988 MSI-w1_2007/08_29 • Powrót sieci neuronowych • Algorytmy genetyczne i programy ewolucyjne • Systemy szkieletowe • Sieci przekonań • Inżynieria wiedzy • Uczenie maszynowe i odkrycia w bazach danych • ... MSI-w1_2007/08_30 5 Podsumowanie • Filozofia: myśl jest pod pewnym względem jak maszyna, która działa na wiedzy zakodowanej w określonym języku, • Matematyka: dostarczyła narzędzi do opisu procesu myślenia, • Psychologia: teoria, że ludzie i zwierzęta mogą być postrzegani jako maszyny przetwarzające informacje, • Technologia komputerowa: pozwala na implementację algorytmów, Część II Ujęcie AI z zastosowaniem agentów MSI-w1_2007/08_31 Inteligentny agent MSI-w1_2007/08_32 Inteligentny agent - przykłady • Agent postrzega swoje otoczenie poprzez sensory • Agent oddziałuje na otoczenie poprzez efektory • Człowiek: – sensory: oczy, uszy, nos, ... – Efektory: ręce, nogi, usta, ... • Robot: – sensory: kamera TV, czujniki IR, sonar, ... – Efektory: chwytaki, głośnik, wyświetlacz, ... • Agent programowy: – sensory i efektory: ciągi bitów MSI-w1_2007/08_33 Przykład idealnego racjonalnego agenta: SQRT w kalkulatorze MSI-w1_2007/08_34 Struktura inteligentnego agenta AGENT = ARCHITEKTURA + PROGRAM Środowisko, w którym można realizować program: • komputer 1-układowy • kamera • mikrofon • ... MSI-w1_2007/08_35 • Oprogramowanie umożliwiające realizację programu agenta (np. BIOS) Funkcja, realizująca odwzorowanie od percepcji do akcji MSI-w1_2007/08_36 6 Agent – typ I (działający na zasadzie odruchów) Przykłady Percepcje Symptomy, wyniki, odpowiedzi pacjenta Punkty (pixeSystem le) o zmienanalizy nej intensywobrazów satelitarnych ności, kolor Interaktywny Wpisywane nauczyciel słowa angielskiego Akcje Pytania, testy, terapie Cele Zdrowy pacjent, minimalne koszty Poprawna Drukuj kategoryzację kategoryzacja sceny Drukuj ćwiczenia, sugestie, poprawki Maksymalizuj ocenę studenta z testu Środowisko Pacjent, szpital AGENT Sensory Jaki jest świat w tej chwili ? Obrazy z orbitującego satelity Zbiór studentów Warunki - reguły działania Jakie działania trzeba wykonać? Efektory MSI-w1_2007/08_37 MSI-w1_2007/08_38 Agent – III Agent – typ II (ukierunkowany na cel) (działający na zasadzie odruchów ze stanem wewnętrznym) Jaki jest świat w tej chwili ? Co powoduje moje działanie ? Warunki - reguły działania Jakie działania trzeba wykonać? AGENT Efektory Sensory Stan Jak zmienia sie świat? Co powoduje moje działanie ? Cel AGENT Jaki jest świat w tej chwili ? Co się stanie jeżeli wykonam działanie A ? Jakie działania trzeba wykonać? Efektory MSI-w1_2007/08_39 Agent – typ 4 Jak zmienia sie świat? Użyteczność Sensory Jaki jest świat w tej chwili ? Co się stanie jeżeli wykonam działanie A ? Jak szczęśliwy będę w tym nowym stanie ? Jakie działania trzeba wykonać? AGENT Efektory Środowisko Co powoduje moje działanie ? MSI-w1_2007/08_40 Podsumowanie (ukierunkowany na użyteczność) Stan Środowisko Jak zmienia sie świat? Środowisko Sensory Stan Środowisko Typ agenta System diagnostyki medycznej MSI-w1_2007/08_41 • Agent • Agent inteligentny • Cztery typy agentów MSI-w1_2007/08_42 7 Kroki konieczne przy rozwiązaniu problemu Część III Rozwiązywanie problemów przez przeszukiwanie • Sformułowanie celu • Określenie reguł powodujących przejście pomiędzy poszczególnymi stanami • Sformułowanie problemu • Poszukiwanie rozwiązania • Wykonanie sekwencji działań będącej rozwiązaniem problemu MSI-w1_2007/08_43 Problem dobrze określony • • • • MSI-w1_2007/08_44 Przykład 1 (problem komiwojażera) Posiada stan początkowy Ma określony zbiór możliwych akcji Potrafi wykonać test osiągnięcia celu Ma sformułowany sposób wyboru rozwiązań bardziej preferowanych MSI-w1_2007/08_45 MSI-w1_2007/08_46 Przykład 3 (gra w szachy) Przykład 2 (Łamigłówka) MSI-w1_2007/08_47 MSI-w1_2007/08_48 8 Problem 5 (Misjonarze i kanibale) Przykład 4 (kryptoarytmetyka) • Stany: układanka w której niektóre litery zastąpiono cyframi • Operatory: zastąp wszystkie wystąpienia danej litery cyfrą jeszcze nie występującą w układance • Test celu: same cyfry, suma poprawna • Koszt ścieżki: 0 FORTY + TEN + TEN ----SIXTY • Stany: trzech misjonarzy, trzech kanibali, łódka (3,3,1) • Operatory: z jednego brzegu można zabrać: dwóch misjonarzy, dwóch kanibali, jednego kanibala i jednego misjonarza, jednego kanibala, jednego misjonarza, MSI-w1_2007/08_49 Problemy świata rzeczywistego • • • • • • MSI-w1_2007/08_50 Poszukiwanie rozwiązań • Polega na przeszukiwaniu przestrzeni stanów • Idea polega na odnalezieniu i rozszerzeniu zbioru sekwencji rozwiązań częściowych Znajdowanie drogi Problem komiwojażera Sterowanie robotem Świat klocków Teoria gier Harmonogramowanie MSI-w1_2007/08_51 Generowanie sekwencji działań • Zbadaj, czy stan wyjściowy nie jest docelowy • Wygeneruj nowy zbiór stanów, stosując operatory do bieżącego stanu („rozwijanie stanu”) • Wybierz, który stan należy rozwijać jako następny (określa to STRATEGIA PRZESZUKIWANIA) MSI-w1_2007/08_53 MSI-w1_2007/08_52 Drzewo przeszukiwania • węzeł przeszukiwania odpowiada danemu stanowi • liść drzewa odpowiada stanowi, który: – albo nie został jeszcze rozwinięty – albo w wyniku rozwinięcia daje pusty zbiór stanów MSI-w1_2007/08_54 9 Ogólny podział strategii przeszukiwania Sposoby przeszukiwania • Przeszukiwanie „ślepe” • Przeszukiwanie heurystyczne – z wykorzystaniem dodatkowej informacji MSI-w1_2007/08_55 Przeszukiwanie wszerz • • • • Wszerz (breadth-first search) Z jednolitym kosztem (uniform cost search) W głąb (depth-first search) O ograniczonej głębokości (depth-limited search) • Z iteracyjnym pogłębianiem (iterative deepening search) • Dwukierunkowe (bidirectional search) MSI-w1_2007/08_56 Przeszukiwanie z jednolitym kosztem MSI-w1_2007/08_57 MSI-w1_2007/08_58 Przeszukiwanie o ograniczonej głębokości Przeszukiwanie w głąb • Modyfikacja przeszukiwania w głąb (narzucenie ograniczenia na maksymalną głębokość ścieżki): – specjalny algorytm o ograniczonej głębokości szukania – zmodyfikowane operatory szukania MSI-w1_2007/08_59 MSI-w1_2007/08_60 10 Przeszukiwanie z iteracyjnym pogłębianiem MSI-w1_2007/08_61 Przeszukiwanie dwukierunkowe MSI-w1_2007/08_62 Podsumowanie • Problem składa się ze: stanu początkowego, operatorów, celu, przestrzeni stanów i ścieżek przeszukiwania • Problem dobrze określony • Poszukiwanie rozwiązań • Strategie przeszukiwania: wszerz, wszerz z jednolitym kosztem, w głąb, o ograniczonej głębokości, z iteracyjnym pogłębianiem, dwukierunkowe, ze spełnianiem ograniczeń MSI-w1_2007/08_63 11