Expertní Systémy
Umělá inteligence
Věda, jejímž úkolem je naučit stroje, aby dělaly věci, které vyžadují inteligenci, jsou-li prováděny člověkem. Marvin Minsky
1950 Alan Turing: Computing Machinery and Intelligence. Mind 59, 1950, s.433-460
Turingův test: úkolem stroje je v komunikaci s experimentátorem předstírat, že je člověk.
od roku 1991 Loebnerova cena pro program, který nejlépe uspěje v redukované podobě Turingova testu www.loebner.net/Prizef/loebner-prize.html
Petr Berka, 2004
1
Expertní Systémy
ELIZA 1965, J. Weizenbaum, imitace chování psychiatra pacient: Ahoj. Eliza: AHOJ, JAK SE CÍTÍŠ ? pacient: Cítím se strašně. Eliza: CO TÍM PŘESNĚ MYSLÍŠ ? pacient: Jsem v depresi. Eliza: PROČ SI MYSLÍŠ, ŽE JSI V DEPRESI. pacient: Protože je mi smutno. Eliza: ŽIJEŠ S RODINOU ? pacient: Ne. Eliza: MÁŠ PŘÁTELE ? pacient: Celkem ne. Eliza: PROČ ? pacient: Nevím. Eliza: OPRAVDU NEVÍŠ NEBO SE JEN VYHÝBÁŠ ODPOVĚDI ? pacient: Dřív jsem přátele měl. Eliza: KDY ? pacient: Než jsem se oženil. Eliza: NEŘEKL JSI MI, ŽE SES OŽENIL. pacient: Už jsem se zase rozvedl. Eliza: POVĚZ MI O SVÉM ROZVODU. . . .
Petr Berka, 2004
2
Expertní Systémy
Směry umělé inteligence • psychologický • inženýrský
Oblasti • • • •
hraní her dokazování teorémů obecné řešení úloh percepce • řeč • vidění • porozumění přirozenému jazyku • tvorba expertních systémů • strojové učení
Etapy • 50.-60. léta: hledání univerzálního řešícího postupu • 70.-90. léta: otázka reprezentace znalostí • 90.- léta: učení a adaptace, komunikace
Klasická vs. nová umělá inteligence je pro inteligenci důležitá reprezentace znalostí a usuzování ?
Petr Berka, 2004
3
Expertní Systémy
Mezníky v historii AI rok 1943 1950 1956 1957
1958 1965
1968 1969 1970 1971 1973 1975 1976 1977 1978 1979 1981 1982 1983 1984
událost model neuronu; McCulloch, Pitts Turingův test; Turing Dartmouthská konference; Minsky, McCarthy, Simon, Newell Perceptron; Rosenblatt GPS (General Problem Solver); Newell, Simon, Shaw formální gramatiky; Chomsky LISP; McCarthy DENDRAL; Feigenbaum, Buchanan fuzzy logika; Zadeh rezoluční princip; Robinson sémantické sítě; Quillian SHRDLU; Winograd kniha Perceptrons; Minsky, Papert PROLOG; Colmerauer, Roussell HEARSAY I ; Lesser MYCIN; Shortliffe, Buchanan rámce; Minsky Dempster-Shaferova teorie; Dempster, Shafer PROSPECTOR; Duda, Hart OPS; Forgy R1/XCON; McDermott ReTe algoritmus; Forgy japonský projekt počítačů páté generace Hopfieldova neuronová síť; Hopfield KEE; IntelliCorp CyC; Lenat Petr Berka, 2004
4
Expertní Systémy
Meze klasické umělé inteligence Churchova teze: Použitelnost počítačů je omezena na ty činnosti, které lze přesně popsat v přirozeném resp. umělém jazyce (algoritmu).
Godelova věta o úplnosti: Formule je logicky platná v teorii T právě když je dokazatelná v teorii T.
Věta o rozhodnutelnosti: Pro každou formuli v teorii T lze algoritmicky rozhodnout, zda formule je nebo není dokazatelná.
• Výrokový počet je úplný a rozhodnutelný. • Predikátový počet je úplný ale nerozhodnutelný.
Petr Berka, 2004
5
Expertní Systémy
Práce se znalostmi
• polovina 70. let - expertní systémy v té době mělo získávání znalostí podobu transferu znalostí
• přelom 80. a 90. let - získávání znalostí jako modelování znalostí = tvorba přehledných a opakovaně použitelných modelů dané úlohy metodika CommonKADS
• současnost - ontologie = domluvená terminologie pro určitou aplikační oblast, která umožňuje sdílení znalostí z této oblasti: – generické ontologie - zachycují obecné zákonitosti platící napříč různými aplikačními oblastmi (projekt CyC, Lenat, 1990) – doménové ontologie - jejich předmětem je určitá specifická věcná oblast (Enterprise Ontology) projekt Semantic Web zaměřený na přidání sémantiky k webovým stránkám (v podobě metadat)
Petr Berka, 2004
6
Expertní Systémy
Práce s neurčitostí
• polovina 70. let - ad hoc přístupy v expertních systémech
• později - využití propracovaných teorií: – teorie pravděpodobnosti (17. století) - v umělé inteligenci např. bayesovské sítě, – fuzzy teorie – teorie možnosti (possibility theory)
• v současné umělé inteligenci oblast nazývaná soft computing = označení pro metody, které umožňují rychle nalézat řešení (byť ne zcela optimální) vágně a neúplně popsaných problémů (Zadeh, 1995): – fuzzy logika – neuronové sítě – genetické algoritmy – pravděpodobnostní metody – teorie chaosu Petr Berka, 2004
7
Expertní Systémy
Učení a adaptace • 50 a 60. léta - učení a adaptace v kybernetice (teorii řízení) v umělé inteligenci neuronové sítě • 80. léta - oblast strojového učení = vývoj algoritmů pro automatizované získáváné znalostí z dat (rozhodovací stromy a pravidla, neuronové sítě, genetické algoritmy, případové usuzování . . .) • 90. léta - dobývání znalostí z databází = netriviální extrakce implicitních, dříve neznámých a potenciálně užitečných informací z dat (Fayyad a kol. 1996) • v současnosti snahy vybavit učící se systémy rysy adaptivity: – inkrementální učení (průběžné doučování na základě nových dat), – učení a zapomínání (schopnost rozpoznat změnu konceptu a této změně se přizpůsobit), – integrace znalostí (schopnost kombinovat více zdrojů znalostí), – meta-učení (schopnost kombinovat více modelů znalostí v průběhu rozhodování), – revize znalostí (schopnost aktualizovat používané znalosti), – využívání analogií. Petr Berka, 2004
8
Expertní Systémy
Komunikace a kooperace • pol. 80. let – komunikace jako jeden z principů umělé inteligence (Minski, Society of Mind, 1986) – ”nová” umělá inteligence jako inteligence bez reprezentace znalostí a bez uvažování, vznikající ze vzájemné interakce jednoduchých, takzvaných reaktivních agentů (Brooks, 1991).
• v současné klasické” umělé inteligenci distribuovaná umělá inteligence a multiagentní systémy. Racionální agent (agent schopný se rozhodnout o následné akci co nejoptimálnějším způsobem) je charakterizován: – autonomností (schopnost nezávisle pracovat), – reaktivitou (schopnost průběžně reagovat na změny prostředí), – intencionalitou (schopnost uvažovat o svých dlouhodobých cílech), – sociální inteligencí (schopnost komunikovat s ostatními agenty).
Petr Berka, 2004
9
Expertní Systémy
Hanojská věž
zadání [111]
[112]
[113]
. . .
řešení [333]
Petr Berka, 2004
10
Expertní Systémy
Stavový prostor 1. 2. 3. 4.
množina stavů S = {s} množina přechodů mezi stavy Φ = {φ} počáteční stav s0 množina koncových stavů G = {g}
Petr Berka, 2004
11
Expertní Systémy
Prohledávání stavového prostoru
Nalezení cesty z počátečního stavu do některého z koncových stavů
1. slepé - úplné prohledávání nevyužívající žádné dodatečné informace • do šířky • do hloubky 2. heuristické - úplné nebo částečné prohledávání využívající hodnocení zvolené cesty, • paprskové (beam search) • gradientní (hill-climbing) • uspořádané (best-first) • A* 3. náhodné
Petr Berka, 2004
12
Expertní Systémy
Prohledávání do šířky
Při tomto způsobu prohledávání máme jistotu, že vždy nalezneme koncový stav, musíme ale projít značně velký počet uzlů (procházíme všechny uzly, které mají hloubku menší, než je hloubka koncového uzlu). Každý uzel v grafu navštívíme nejvýše jednou.
Petr Berka, 2004
13
Expertní Systémy
Algoritmus prohledávání do šířky NEROZVIN := poč. stav '
?
NEROZVIN + prázdný ? & -
$ %
?
přesuň první uzel z NEROZVIN (označ N) do ROZVIN ?
rozviň N, všechny následníky ulož do NEROZVIN na konec '
?
$
některý uzel + z NEROZVIN je cíl ? &
%
Petr Berka, 2004
14
Expertní Systémy
Prohledávání do hloubky
Tento způsob prohledávání může vést k cíli mnohem rychleji, než prohledávání do šířky (zvláště když se vydáme správným směrem), ale nemáme zaručeno (v případě nekonečné větve), že vždy nalezneme koncový stav. Na rozdíl od prohledávání do šířky můžeme některými uzly procházet vícekrát, neboť se často musíme navracet.
Petr Berka, 2004
15
Expertní Systémy
Algoritmus prohledávání do hloubky NEROZVIN := poč. stav '
?
NEROZVIN + prázdný ? & -
$ %
?
přesuň první uzel z NEROZVIN (označ N) do ROZVIN ?
rozviň N, všechny následníky ulož do NEROZVIN na začátek '
?
$
některý uzel + z NEROZVIN je cíl ? &
%
Petr Berka, 2004
16
Expertní Systémy
Paprskové prohledávání heuristické omezené prohledávání do šířky - heuristikou je odhad vzdálenosti ke koncovému stavu NEROZVIN := poč. stav '
+
?
NEROZVIN prázdný ? & -
$ %
?
přesuň všechny uzly z NEROZVIN (označ Ni ) do ROZVIN ?
rozviň Ni , všechny následníky ulož do NEROZVIN na konec ?
uspořádej NEROZVIN dle heuristiky ?
kromě prvních p odstraň z NEROZVIN všechny uzly '
?
$
některý uzel + z NEROZVIN je cíl ? &
%
Petr Berka, 2004
17
Expertní Systémy
Gradientní prohledávání úplné heuristické prohledávání do hloubky - heuristikou je odhad vzdálenosti ke koncovému stavu
NEROZVIN := poč. stav '
+
?
NEROZVIN prázdný ? & -
$ %
?
přesuň první uzel z NEROZVIN (označ N) do ROZVIN ?
rozviň N, všechny následníky uspořádej dle heuristiky a ulož do NEROZVIN na začátek '
?
$
některý uzel + z NEROZVIN je cíl ? &
%
Petr Berka, 2004
18
Expertní Systémy
Uspořádané prohledávání úplné heuristické prohledávání do hloubky - doplnění gradientního prohledávání o paměť
NEROZVIN := poč. stav '
+
?
NEROZVIN prázdný ? & -
$ %
?
přesuň první uzel z NEROZVIN (označ N ) do ROZVIN ?
rozviň N , všechny následníky ulož do NEROZVIN ?
uspořádej NEROZVIN dle heuristiky '
?
$
některý uzel + z NEROZVIN je cíl ? &
%
Petr Berka, 2004
19
Expertní Systémy
Algoritmus A* cena přechodu z počátečního stavu přes stav s do koncového stavu f (s) = g(s) + h(s) heuristika h(s) jako dolní odhad ceny přechodu z s do koncového stavu, pro h(s) = 0 provádí A* prohledávání do šířky NEROZVIN := poč. stav '
?
NEROZVIN + prázdný ? & -
$ %
?
přesuň první uzel z NEROZVIN (označ N ) do ROZVIN ?
rozviň N , všechny následníky N* ulož do NEROZVIN ?
je-li v NEROZVIN uzel N* s vyšší hodnotou g(N*) odstraň jej ?
uspořádej NEROZVIN dle funkce f '
?
$
některý uzel + z NEROZVIN je cíl ? &
%
Petr Berka, 2004
20
Expertní Systémy
Fuzzy množiny
Na rozdíl od “klasických” množin, kdy o každém objektu lze jednoznačně říci, zda je nebo není prvkem množiny (např. množina všech sudých čísel), je v případě fuzzy množin příslušnost k množině vyjádřena charakteristickou funkcí µ(x) ∈ [0, 1].
6
µ(x)
1
0
35
36
37
38
39
x-
Figure 1: Zvýšená teplota
Petr Berka, 2004
21
Expertní Systémy
LISP Programovací jazyk pro manipulaci se symbolickými výrazy (LISt Processor) vytvořený na přelomu padesátých a šedesátých let na MIT skupinou kolem J. McCarthyho. Data - S-výrazy: • atomy (nečíselné, číselné, T, NIL) • seznamy - jsou-li s1 , s2 S-výrazy, je i (s1 s2 ) S-výraz Funkce (f s1 s2 ... sn ) • (CONS s1 s2 ) - funkce, která ze dvou vstupních S-výrazů s1 a s2 vytvoří S-výraz (s1 s2 ) • (CAR s) - funkce, jejíž hodnotou je první prvek seznamu s • (CDR s) - funkce, jejíž hodnotou je zbytek seznamu po oddělení prvního prvku • (EQ s1 s2 ) - funkce, která testuje shodu svých argumentů. Je definována pouze pro atomy • (ATOM s) - funkce, která má hodnotu T , je-li S atom Nové funkce se definují pomocí funkčních výrazů (λ-výrazů) (LAM BDA(x1 x2 ... xn )e).
Petr Berka, 2004
22
Expertní Systémy
Hanojská věž - LISP (DEFUN HANOJ (LAMBDA (N) (PRESUN_VEZ N ’A ’B ’C) ))
(DEFUN PRESUN_VEZ (LAMBDA (K X Y Z) ((EQ K 0)) (PRESUN_VEZ (DIFFERENCE K 1) X Z Y) (TAH X Z) (PRESUN_VEZ (DIFFERENCE K 1) Y X Z) ))
(DEFUN TAH (LAMBDA (X Z) (PRIN1 "Presun disk z ") (PRIN1 X) (PRIN1 " na ") (PRIN1 Z))
Petr Berka, 2004
23
