Dombi József University of Szeged Department of Informatics
[email protected]
• Előadásom során rámutatok a logikai rendszerhez való ragaszkodás korlátaira.
• Megmutatom, hogy az új létrejött paradigmák (neurális tanulás, döntési fa készítés, klaszterezés) hogyan kezelhetők egységesen.
• Az előadásban választ próbálunk adni arra a kérdésre is, hogy milyen a gépi intelligencia matematikája.
Logikus döntés • Matematikai logikát használja
• Racionális döntés: • Racionális(?)
Kétértékű logika
• Ítéletkalkulus • „és” • „vagy” • „tagadás” (negáció),
• implikáció, következtetés
• Elsőrendű logika • mindig • van olyan • függvény…
Görögök Arisztotelész, Diodórosz Kronosz
• Diodórosz Kronosz • antik megarai filozófiai iskolához tartozott, • i.e. 4. század második felében tevékenykedett. • A görög logika egyik kiemelkedő alakja volt • megalkotta a nagy hatást kiváltó győzedelmes argumentumot, • kidolgozott egy saját értelmezést, amellyel elsőként mutatott rá a modális és a temporális logika kapcsolatára.
A győzedelmes érv • Az argumentum a következő három kijelentés ellentmondásosságát fogalmazza meg: • (A) Minden, ami elmúlt és igaz, szükségszerű. • (B) A lehetségest nem követi a lehetetlen. • (C) Az, ami nem igaz és nem is lesz igaz, lehetséges.
A győzedelmes érv • A három premissza modális logikai kifejezéseket temporális fogalmakkal határoz meg, ezzel megalkotva a modalitások temporális modelljét. • Egyes vélemények szerint az argumentum azért kapta a győzedelmes elnevezést, mert logikailag legyőzhetetlen. • Más értelmezésben a győzedelmes az érv tartalmára, a szükségszerűség mindent elsöprő voltára utal.
• Modális logika: kijelentések különböző „módjainak” tanulmányozására vezették be (eredetileg filozófusok). Ilyen módok: „esetleg”, „mindig”, „szükségszerűen”, „valamikor biztosan”
• Temporális logikák: a modális logikák egy formális rendszerét képezik arra, hogy kijelentések igazságának időbeli (sorrendiségi) változását vizsgálhassuk. http://www.cid.com.ro/ksimon/svv/vv_kurzus8.pdf
Logikák • Temporális logika • Modális logika (szükségszerű, lehetséges) • Nem monoton logika (Calvo) • Többértékű logika
• Nem monoton logika: egy következtetést egy későbbi következtetés eredménye vagy egy újabb ismeret érvényteleníthet bizonyított állítások száma csökkenhet Következtetések levonása/ visszavonása • ellentmondó ismeretek • vélemény változhat • elhisszük, ha az ellenkezőjéről nincs tudomásunk "jelenlegi ismereteim szerint" "tudomásom szerint„ madár(x) repül(x)
pingvin(x) madár(x) pingvin(Totyi) repül(Totyi) pingvin(x) repül(x) repül(Totyi)
Mesterséges intelligencia és logika • Automatikus tételbizonyítás (rezolúció)
• Prolog nyelv
• Szakértői rendszerek
Mire képes a prolog? A tények halmazával megadott kis világban kérdéseket tehetünk fel arról.
• "Igaz-e, hogy Pál órát tart?” • A válasz erre Igen.
• "Igaz-e, hogy Pál tanfolyamot tart?” • a válasz természetesen Nem.
Mária órát tart. János tanfolyamot tart. Pál órát tart.
• "Ki tart órát?” • A válasz most: János, Mária, Pál azért, mert ezek a személyek elégítik ki a tart relációt az óra objektummal.
• Tény: Mária az áruházban beverte a fejét és vérzett.
• Automatikus következtetés: Mária aznap magával vitte a fejét.*
*(a számítógép nem tudja, hogy ha valahova elmegyünk, minden testrészünket magunkkal visszük).
• Tény: Ha van egy dollárom akkor vásárolhatok.
• Automatikus következtetés:
A kóla 1 dollár, a chips 1 dollár. Van egy dollárom. Következtetés: Vettem egy chipset ÉS egy kólát.
• Komplexitás
• Tudásbázis
• Ténybázis
• Faktoriális: 100! összes esete (Strirling formula)
• ha a Föld összes lakosa 1/100 sec alatt számol ki egy útvonalat akkor 10 millió évig tart az összes eset átnézése.
• Japán V. generációs számítógép technológiai kudarca
• Megmentési kísérletek • Heurisztikák • Metavezérlések
• Újabb kudarcok
• Logikai mindennapi használata: • Lekérdezéseklisták készítése • SQL lekérdezési nyelv
• Lekérdezés logikai változásának értéke: • Diszkrét eset: x ϵ A, x ϵ A • Folytonos eset: x ϵ [a,b], x
[a, b]
Egy adott tér kijelölése: hiper téglatestek egyesítése
• Objektumok jellemzése, kategorizálása • SQL-ben megfogalmazott • Feltételeknek eleget tevő objektumok.
• Tudás átadás: logikai kifejezés átadás
Tudás leírás és logika
• Pontosság: • Versus szabályok száma
• Következmény: tapasztalati tudás logikai alapú leírása korlátozott (mondd el és tudni fogom lehetetlensége!)
• Gépi intelligencia követelménye:
• „Hiper” tér tartományok hatékony leírása, „kezelése” (módosítása, átalakítása)
Racionális döntés • Racionalitás: optimalitás
• Lineáris és nem lineáris optimalizálás
• Korlátozó feltételek
• Célfüggvény(ek)
Gyakorlati alkalmazás • Konzervgyár: • Borsó, kukorica, uborka, bab, káposzta, cékla
• Minimális, maximális mennyiségek • Korlátozó feltételek (munkaerő, energia, raktározás) • Optimalizálás (profit) • Eredmény: borsó: 0, uborka: 0, bab: max, káposzta: max, cékla: max 40%-a.
• Optimalizálás: • Szélsőérték ! • Megvalósítás lehetetlensége
• Kiút: Több célfüggvény • Optimalizálás helyett „kompromisszumos” megoldás
• Optimalizálás helyett kielégítő megoldás
• Kapacitás kérdése
• Időigény (logikai formula keresés)
• memóriaigény
Többértékű és folytonos logika
Többértékű logika Többértékű logika: A többértékű logikák olyan logikai szemantikák, ahol kettőnél több igazságérték létezik. • Az igazságértékek számossága alapján megkülönböztethetünk 3-értékű (Lukasiewicz, Kleene), • 3-nál több értékű (post többértékű rendszere), • vagy végtelen (fuzzy logika)
lehetséges értéket tartalmazó logikákat.
Többértékű logika • 3, 4 értékű logika • folytonos logika
• Fuzzy logika (nagyon, többé-kevésbé) • Possibilistic
• Intuitionistic • Bipolar
• Fuzzy type-2 • „Lukasiewicz”
Miért van ilyen sokféle logika? • Boole azonosságok (kétértékű eset)
• Nincs olyan többértékű logika, ami eleget tenne az összes Boole azonosságnak!
• Boole azonosságok részhalmaza
Fuzzy • A fuzzy logika gondolatát először Lotfi A. Zadeh (University of California at Berkely)
vetette fel 1965-ben. 1973-ban az ötleteire alapozva bevezette a nyelvi változókat (melyek azonosak egy változó leképezésével egy fuzzy halmazra). További kutatások következtek; az első ipari alkalmazás egy cementégető-kemence Dániában, 1975-ben kezdett működni. • A fuzzy rendszereket az elmúlt időszakban nagyfokú érdektelenség kísérte, mivel alapvetően a mesterséges intelligenciával társították és így kevésbé volt fontos az ipari vállalatok számára.
Fuzzy • Az elmosódott halmazok logikája (angolul: fuzzy logic) a többértékű logikai szemantikák egyike. Tulajdonképpen fuzzy logika név alatt egy egész elméletcsaládról beszélhetünk, melynek sokrétű alkalmazásai vannak elsősorban az informatikában, de alkalmazásra talált a nyelvtudományi és logikai szemantikában, a matematikai logikában és a valószínűségelméletben is. • A tágabb értelemben vett fuzzy logika alapját képezi a fuzzy számítógépes rendszereknek, melyek szemben a szokványos rendszerekkel, nem csak igen és nem (illetve ki és be, vagy 1 és 0) értékekkel dolgoznak, hanem közbülső „valóságértékekkel” is, mint például 0,5 (féligmeddig), 0,2 (kicsit), 0,8 (eléggé)… Ezáltal az „életlen” (fuzzy) meghatározások (mint például az előbbiek) matematikailag kezelhetővé válnak. • Manapság a fuzzy logika illetve a fuzzy-control, tehát a fuzzy logikán alapuló irányítás, elsősorban gépek és robotok, háztartási készülékek irányításában talál alkalmazásra.
Folytonos logika negáció
Negáció Definíció: n(x) negáció akkor és csakis akkor, ha eleget tesz a következő feltételeknek:
n : 0,1 0,1
• n(x) folytonos • A peremfeltételek n(0) 1 és n(1) 0 • Monotonitás:
n( x) n( y) x y
• Involutivitás:
n(n( x)) x
esetén
Negáció Egyéb tulajdonságok: - * a negáció fix pontja, ahol n( )
- A döntési érték: -
ha
x
akkor
n( x ) 0
-
ha
x
akkor
n( x ) 0
Negáció - Az ábrán negációs függvények láthatók, különböző - * és értékekkel:
Negációk, ahol
és
Folytonos logika aggregatív operátor
Aggregatív operátorok - definíció Az aggregatív operátor egy szigorúan növekvő a : 0,12 0,1 függvény a következő tulajdonságokkal:
• A peremfeltételek
0,12 \ 0,1, 1,0 a0,0 0 és
• Asszociativitás:
a( x, a( y, z )) a(a( x, y), z )
• Folytonos
a1,1 1
• Létezik szigorú negáció n, ami a( x, y) na(n( x), n( y))
(önDeMorgan)
Aggregáció Vizsgáljuk a következő objektumhalmazokat (O1 , O2 ,..., On )
Jellemezzünk minden ( xi , xi ,..., xi ) 1
2
m
xi (0,1) elem
tulajdonságait egy m számmal, ahol a( x1 ,..., xn ) és i = 1,…,n.
Így az alábbi módon jelölt aggregatív operátor
C ,1 Oi | a( xi1 , xi2 ,..., xim ) ,
döntési szintre
C , 2 Oi | a( xi1 , xi2 ,..., xim ) n( ) .
Aggregáció Ezután helyettesítsünk minden tulajdonságot az
ellentétével, n( xi ) -vel (a következőkben ez lesz az j
elem tagadása)
és vigyük véghez az osztályozást a következő szinten:
O | a(n( x ),..., n( x
C ,1 Oi | a(n( xi1 ),..., n( xim )) , C ,2
i
i1
im
)) n( ) .
Aggregatív operátorok Definíció: (helyes döntéshozás) A helyes döntéshozás feltétele
C ,1 C , 2
, C , 2 C ,1 .
Tétel: Szükséges és elégséges feltétele az aggregatív operátoroknak, hogy elégítsék ki a megfelelő döntési formulát, amire
a( x, y) nan( x), n( y) -nek teljesülnie kell.
• Aggregatív operátor tulajdonságai • x, y < ν*
a(x, y) ≤ min(x, y)
• x, y > ν*
a(x, y) ≥ max(x, y)
• x < ν* y
min(x, y) ≤ a(x, y) ≤ max(x, y)
• a(x, ν* ) = x • a(0, 0)= 0, • a(x, n(x))= ν*
a(1, 1)=1
Aggregáció
Aggregatív operátor területei
•
Fölfújó függvény
Fölfújó függvény tagsági függvény helyett Válasszunk egy gyakran használt kifejezést, mint például az “öreg”. Ugyanez a példa található Zadeh cikkében. Feltételezzük, hogy az „öreg” kifejezés csak a kor függvénye, és nem foglalkozunk azzal, hogy a legtöbb poláris kifejezés szövegkörnyezet-függő, tehát egy öreg professzor más értelmezési tartományban található, mint egy öregdiák. A klasszikus logikában ki kell jelölnünk egy határvonalat, esetünkben legyen ez 63 év (a=63). Ha valaki idősebb, mint 63 év, az öreg emberek osztályába sorolható, egyébként nem.
Fölfújó függvény tagsági függvény helyett Leírhatjuk egyenlőtlenségként, karakterisztikus függvény használatával 1 a ( x) 0
if
ax
if
ax
A a<x kifejezés ekvivalens 0 < x-a -val, tehát a fenti alak átírható: 1 ( x a) 0
if 0 x a if 0 x a
Fölfújó függvény tagsági függvény helyett Általában az egyenlőtlenség bal oldalán lehet bármilyen g(x) függvény 1 ( g ( x)) 0
if 0 g ( x) if 0 g ( x)
A rugalmas koncepcióban bevezetjük a fölfújó függvényt. A következő jelölést fogjuk használni: ( x) truth(0 x)
x R.
Általánosíthatjuk a következő módon: ( g ( x)) truth0 g ( x)
x Rn.
A fölfújó függvény általános alakja Kezdjük az aggregációs koncepcióval. A súlyozott aggregatív operátor n wi aw ( x1 , x2 ,..., xn ) f f ( xi ) i 1 1
Ahol az xi értékek fölfújó értékek és f a
generátorfüggvénye a xi (ti ) logikai operátornak. Intuitíve az aggregáció az értékek súlyozott átlaga n
t wi ti . i 1
A következő tétel adja meg a (ti ) pontos definícióját.
Fölfújó függvény •
a( ) ( x) f 1 e ( x a )
P ( ) ( x, y ) f 1 e ( x y )
igazság( y x)
R
Fuzzy • A japánoknak nem voltak ilyen előítéleteik. A fuzzy rendszerekre irányuló ipari fejlesztések motorjai, Seiji Yasunobu és Miyamoto a Hitachinál 1985-ben szimulációs eljárásokkal bebizonyították a fuzzy elven működő irányító rendszer előnyeit a Sendai vasútvonalnál. • Javaslataikat támogatták és fuzzy rendszereket alkalmaztak a gyorsulás, fékezés és a megállás irányítási feladatainak megoldására amikor a járatot 1987-ben beindították.
A feladatok soha nem tapasztalt térbeli és időbeli komplexitása Hogyan vezetünk csúcsforgalomban? Sok elemű, nagyon összetett rendszer. Meg lehet oldani klasszikus vagy mesterséges intelligencia-beli módszerekkel?
Szeretnénk olyan GÉPEK-et építeni, amelyek szintén képesek rá.
Az autónk állapota, az időjárás, üzemanyag takarékosság, időnyerés, stb..
Köszönöm a figyelmet!