DSM módszer

A JSM módszer a hipotézisek  automatikus generálásának módszere . Formalizál egy sémát egy elfogadható és megbízható következtetéshez, amelyet JSM érvelésnek neveznek.

A JSM érvelés a kognitív eljárások szintézise: indukció , analógia és abdukció . A JSM módszert a tárgyterületre vonatkozó ismeretek formalizálásának automatizált felépítésének eszközeként hozták létre az úgynevezett kvázi-axiomatikus elméletek (QAT) segítségével.

Történelem

A hipotézisek automatikus generálására szolgáló JSM módszert W. K. Finn javasolta a hetvenes évek végén. A módszer neve a híres angol filozófus, logikus és közgazdász, John Stuart Mill kezdőbetűi , akinek "egy józan természettudós módszerei" részben formalizálódnak a JSM-módszerben.

Történelmileg a DSM-rendszereket használó feladatok első példája a struktúra-aktivitás típusú oksági minták azonosítása a farmakológiában . 1997-1998 - ban számos számítógépes kísérletet végeztek , amelyek célja egy olyan intelligens rendszer létrehozásának lehetőségének felmérése volt, amely lehetővé teszi annak meghatározását, hogy mekkora a kockázata annak, hogy egy betegnél kiújul az agyalapi mirigy adenoma eltávolítása után. A kvantitatív DSM módszer alapján egy kísérleti rendszert dolgoztak ki az agyalapi mirigy adenoma kiújulásának előrejelzésére, melynek munkaneve HTRD (Hypophisis tumor relapse diagnosztika). Emellett a JSM rendszereket sikeresen alkalmazzák a műszaki diagnosztika problémáiban és a szociológiai viselkedés meghatározóinak vizsgálatában.

Jelenleg a VINITI RAS -ban és az Orosz Állami Humanitárius Egyetem Matematika, Logika és Intelligens Rendszerek Tanszékén fejlesztik a DSM rendszereket V. K. Finn irányításával.

A módszer leírása

A JSM metódus három típusú entitásokkal működik: a tárgyterület objektumaival, ezen objektumok tulajdonságaival és a tulajdonságok lehetséges okaival.

Feltételezzük, hogy az objektumok szerkezettel rendelkeznek, és az objektumok tulajdonságainak okai ennek a szerkezetnek a töredékei.

Példa:

A tárgy egy növényi levél. Az objektum tulajdonsága zöld. A tulajdonság oka a klorofill.

Bemenetként a JSM metódus a vizsgált objektumok egy meghatározott halmazát és információkat kap a szerkezetükről, bizonyos tulajdonságok meglétéről vagy hiányáról, valamint bizonyos esetekben az objektumok szerkezete és tulajdonságai közötti kapcsolatról. Ezenkívül számos célszolgáltatás létezik, amelyek mindegyike az eredeti objektumkészletet négy nem átfedő részhalmazra osztja:

A JSM módszer alkalmazásának eredménye kétféle hipotézis:

A JSM metódus lépése

Tekintsük a JSM módszer egyik lépését a legegyszerűbb formájában.

Létezik egy P: O→ függvény , amely minden o objektumra leképezi az o objektumban előforduló töredékek (szerkezeti elemek) egy részhalmazát.

Vezessünk be egy F: O×P→V függvényt, amely a kiindulási helyzetet reprezentálja.

Az F függvény mátrixként ábrázolható:

Ha f ij = , akkor azt mondjuk, hogy az (o i , p j ) párra az F ( o i , p j ) függvény alulhatározott . A JSM módszer feladata a kiinduló mátrix kiegészítése hipotézisek felállítása segítségével .

Az első típusú szabályok

Alkossunk hipotézist a tulajdonságok lehetséges okairól. Ennek eredményeként a H függvényt kapjuk : C×P→V.

  • H(c, p) = +1  - c lehetséges oka a p tulajdonság vagy a (+)-hipotézis jelenlétének;
  • H(c, p) = −1  - c lehetséges oka a p tulajdonság hiányának vagy a (-)-hipotézisnek;
  • H(c, p) = 0  - érvek szólnak mind amellett, hogy c az oka a p tulajdonság jelenlétének, mind pedig amellett, hogy c az oka ennek a tulajdonságnak vagy (+)-hipotézisnek (ellentmondásos hipotézis);
  • H(c, p) =  - nem ismert, hogy c a p jelenlétének oka vagy ennek a tulajdonságnak az oka.

A H függvény értékeit minden párhoz (c, p) a valószínű következtetés szabályai alapján találjuk meg. Ezeket a szabályokat az első típusú szabályoknak nevezzük. A rövidítés: PIR 1 (Plusible Inference Rules). Az első típusú szabályok egy olyan függvénynek tekinthetők, amely az F mátrixot használja a H mátrix megszerzésére, azaz
H = PIR 1 (F) .

Legyen p valamilyen tulajdonság.
Az o objektum:

  • egy pozitív példa vagy (+)-példa p-re az eredeti F mátrixhoz képest, ha F(o, p) = +1 ,
  • negatív példa vagy (-)-példa p-re az eredeti F mátrixhoz képest, ha F(o, p) = −1 ,
  • egy ellentmondásos példa vagy egy (0)-példa p-re az eredeti F mátrixhoz képest, ha F(o, p) = 0 .

Jelölje F + [p], F - [p], F 0 [p] az összes pozitív, negatív és ellentmondó példát p-re F-re vonatkozóan.

Az objektumtulajdonságok meglétének/hiányának lehetséges okaiként a C [1] töredékhalmaz részhalmazait vesszük figyelembe . Egy C' ⊆ C halmaz teljesíti p (+)-feltételét F-hez képest, ha létezik Ω ⊆ F + [p] , így:

  1. , azaz minden Ω objektum tartalmazza a C' halmaz összes töredékét, és nincsenek további töredékek, amelyek mindegyikhez tartoznak ;
  2. Ω legalább két elemet tartalmaz.

A (-)- és (0)-feltételek hasonlóak.

Jelölje M + (F, c, p) azt a tényt, hogy c teljesíti p-re vonatkozó (+)-feltételt F vonatkozásában. M - (F, c, p)
révén  az a tény, hogy c teljesíti p (-)-feltételét F-re vonatkozóan. M 0 (F, c, p) révén  az a tény, hogy c teljesíti p (0)-feltételét F-re vonatkozóan.

Most definiáljuk a H [2] függvényt . Tegyük fel:

Más szavakkal, a C i ⊆C töredékek halmazát újradefiniáljuk

  • a p tulajdonság jelenlétének lehetséges oka, ha két vagy több (+)-példába, legfeljebb egy (-)-példába és legfeljebb egy (0)-példába van ágyazva;
  • a p tulajdonság hiányának lehetséges oka, ha két vagy több (-)-példába, legfeljebb egy (+)-példába és legfeljebb egy (0)-példába van ágyazva.
A második típusú szabályok

A lehetséges okokra vonatkozó hipotézisek mátrixát felhasználva hipotéziseket lehet alkotni a p tulajdonság meglétéről vagy hiányáról az O -ból származó azon objektumok esetében, amelyekről kezdetben nem volt ismert, hogy rendelkeznek-e ezzel a tulajdonsággal vagy sem, vagyis azokra az o O -kra. amelyre F(o, p ) = .

Ennek eredményeként az F' függvényt kapjuk : O×P→V. F'(o, p) = F(o, p), ha F(o, p) ≠ . Ha F(o, p) = , akkor F'(o, p) tetszőleges értéket vehet fel V -ből :

  • F'(o, p) = +1  - o valószínűleg p tulajdonsággal rendelkezik,
  • F'(o, p) = −1  - o nem rendelkezik p tulajdonsággal,
  • F'(o, p) = 0  - érvek szólnak mellette és ellene is, hogy az o objektum p tulajdonsággal rendelkezik,
  • F'(o, p) =  — nem lehetett kitölteni az eredeti F mátrix celláját.

Az F' függvény értékeit a valószínű következtetés szabályai segítségével találjuk meg. Ezeket a szabályokat a második típusú szabályoknak nevezzük. Rövidített jelölés - PIR 2 . A második típusú szabályok az F és H mátrixok függvényében tekinthetők az F' mátrixhoz, azaz F' = PIR 2 (F, H) .

Legyen o tárgy, p tulajdonság. Azt fogjuk mondani, hogy az o objektum kielégít

  • (+)-feltétel p-re H-hoz képest (vagyis lehet p tulajdonsága), ha létezik olyan c C , hogy c⊆o és H(c, p) = +1.
  • (-)-feltétel p-re H-re vonatkozóan (vagyis nem lehet p tulajdonsága), ha létezik olyan c C , hogy c⊆o és H(c, p) = −1.
  • (0)-feltétel p-re H-hoz képest (vagyis vannak érvek mellette és ellene is, hogy o-nak p tulajdonsága van), ha létezik c C úgy, hogy c⊆o és H(c, p) = 0.

+ ( H , o, p), - (H, o, p), 0 (H, o, p) -val azt a tényt jelöljük, hogy a p tulajdonsághoz tartozó o objektum H vonatkozásában teljesíti a (+)-feltételt, (-) -feltétel, illetve 0-feltétel. Tegyük fel: F'(o, p) = F(o, p), ha F(o, p) ≠ ; másképp

Az első típusú szabályokat (indukciós eljárás) és a második típusú szabályokat (analógiás eljárás) következetesen alkalmazzák mindaddig, amíg munkájuk eredményeként legalább egy új hipotézis nem keletkezik, azaz az első típusú szabályok alkalmazása nem vezet az objektumok tulajdonságainak lehetséges okaira vonatkozó hipotézisek mátrixának változása, a második típusú szabályok alkalmazása pedig a p tulajdonság objektumokban való lehetséges jelenlétére vagy hiányára vonatkozó hipotézismátrix megváltoztatása. Ebben az esetben a lépésszám az érvelés elfogadhatóságának mutatója.

Az oksági teljesség feltételének ellenőrzése

A JSM módszer munkájának következő lépése az oksági teljesség feltételének ellenőrzése. Ennek a feltételnek az igazolását abdukciós érvelésként értelmezzük - a feltétel akkor teljesül, ha a kapott hipotézisek megmagyarázzák a kiindulási adatokat, vagyis ha az objektumok tulajdonságainak lehetséges okaira vonatkozó hipotézisek, amelyeket a tárgyi szabályok alkalmazása eredményeként kaptunk. az első típus, meg tudja magyarázni a p tulajdonság meglétét vagy hiányát azokban az objektumokban, amelyekről kezdetben (az indukciós és analógiás eljárások alkalmazása előtt) ismert, hogy rendelkeznek p tulajdonsággal vagy nem.

A feltétel ellenőrzésének célja annak megállapítása, hogy a módszer eredményeként kapott hipotézisek elfogadhatók-e. Ha az ok-okozati teljesség feltétele nem teljesül, módosítani kell az alkalmazott kognitív technikát (például az objektumok szerkezetének más kódolási módját) vagy az objektumok bemeneti halmazát (szabály szerint a halmaz kibővül). ).

Példa

Próbáljuk meg a JSM módszerrel megválaszolni a következő kérdést: milyen tulajdonságokkal kell rendelkeznie egy nemtriviális szimmetriájú konvex négyszögnek , hogy le tudjon írni egy kört körülötte , vagy fordítva, lehetetlen volt kört leírni.

Tekintsük a következő tartományobjektum-készletet:

Ezekhez az objektumokhoz a következő C szerkezeti töredékkészletet választjuk:

  • c 1  a szimmetria középpontja,
  • c 2  - a szimmetriatengely ,
  • c 3  - van egy szimmetriatengely, ami egy átló ,
  • c 4 - van egy szimmetriatengely, amely nem átlós,
  • c 5  - pontosan egy 180°-os elforgatás önmagába fordítja az ábrát,
  • c 6 - a szimmetriacsoport rendje egyenlő kettővel,
  • c 7 - van egy pár szemközti derékszög ,
  • c 8  - nincs derékszög,
  • c 9  - nincs szimmetriatengely, vagy bármely szimmetriatengely átlós.

a céljellemzők halmaza ebben az esetben csak egy jellemzőből áll:

  • p - leírhatja a kört.

Mutassuk be a kiindulási adatokat táblázat formájában:

p c 1 c 2 c 3 c 4 5 -től 6 -tól 7 -től 8 -tól 9 -től
o 1 (négyzet) + + + + + - - + - -
o 2 (téglalap) + + - + + - + - -
o 3 (gyémánt) - + + + - + - - + +
o 4 (párhuzamos) - + - - - + + - + +
o 5 (egyenlő szárú trapéz) + - + - + - + - + -
o 6 (deltoid) - - + + - - + - + +
o 7 (téglalap alakú deltoid) + - + + - - + + - +

Jellemezzük az egyes objektumokat az objektum szerkezeti összetevőinek halmazával:

  • o 1 (négyzet) {s 1 , s 2 , s 3 , s 4 , s 7 };
  • o 2 (téglalap) {s 1 , s 2 , s 4 , s 5 , s 7 };
  • o 3 (gyémánt) {s 1 , s 2 , s 3 , s 5 , s 8 , s 9 };
  • o 4 (parallelogramma) {s 1 , s 5 , s 6 , s 8 , s 9 };
  • o 5 (egyenlő szárú trapéz) {s 2 , s 4 , s 6 , s 8 };
  • o 6 (deltoid) {s 2 , s 3 , s 6 , s 8 , s 9 };
  • o 7 (téglalap alakú deltoid) {s 2 , s 3 , s 6 , s 7 , s 9 }.

Esetünkben a p céltulajdonságra pozitív példák az o 1 , o 5 és o 7 objektumok , negatív példák az o 3 , o 4 és o 6 . Van még egy ( )-példa - o 2 .

Feladatunk az, hogy elfogadható érveléssel megtudjuk, hogy a ( )-példák rendelkeznek-e p céltulajdonsággal vagy sem.

Az első típusú szabályok alkalmazása

Itt a p tulajdonság objektumokban való jelenlétének/hiányának lehetséges okaiként a C szerkezeti töredékek halmazának néhány nem üres részhalmazát fogjuk figyelembe venni. A (+)-feltételt a halmazok teljesítik:

  • C 1 = {с 2 , с 4 }: Ω = {o 1 , o 5 };
  • C 2 = {с 2 , с 3 , с 7 }: Ω = {o 1 , o 7 };
  • C 3 = {с 2 }: Ω = {o 1 , o 5 , o 7 };
  • C 4 = {с 2 , с 6 }: Ω = {o 5 , o 7 }.

A (-)-feltételt a halmazok teljesítik:

  • C 5 = {с 1 , с 5 , с 8 , с 9 }: Ω = {o 3 , o 4 };
  • C 6 = {с 2 , с 3 , с 8 , с 9 }: Ω = {o 3 , o 6 };
  • C 7 = {с 8 , с 9 }: Ω = {o 3 , o 4 , o 6 };
  • C 8 = {с 6 , с 8 , с 9 }: Ω = {o 4 , o 6 };

Most azt kell kideríteni, hogy a talált halmazok lehetséges okai-e a p céltulajdonság meglétének vagy hiányának az objektumokban, vagyis meg kell határozni ehhez a lépéshez a H függvényt. Amint azt korábban említettük, ennek a függvénynek a meghatározására vonatkozó szabályok a választott stratégiától függően eltérő formájúak lehetnek - ellenpéldák tiltásával vagy anélkül.

A C i C halmaz ki lesz terjesztve mint

  • a p tulajdonság jelenlétének lehetséges oka, ha C i teljesíti p (+)-feltételét , azaz két vagy több (+)-példában részhalmazként van beágyazva, és nincs beágyazva egyikbe sem (beágyazott no egynél több) (- )-példa;
  • a p tulajdonság hiányának lehetséges oka , C i teljesíti a p (-)-feltételét , vagyis két vagy több (-)-példában részhalmazként van beágyazva, és nincs beágyazva egyikbe sem (be van ágyazva). legfeljebb egy) (+) -példa;
  • ellentmondásos hipotézis, ha létezik egy (+)-példa és egy (-)-példa is, amelybe C i be van ágyazva .

Adatainkat elemezve két lehetséges okot kapunk a p tulajdonság jelenlétére :

  • C 1 = {с 2 , с 4 } és
  • C 2 \u003d {c 2 , c 3 , c 7 }.

A C 4 = {с 2 , с 6 } töredékhalmaz stratégiától függően (+)-hipotézissé vagy ellentmondásos hipotézissé válik.

Minden halmaz, amely kielégíti p (-)-feltételét, további definíció szerint lehetséges oka a p tulajdonság hiányának .

vagyis

  • H (C 1 , p) = +1 ,
  • H (C 2 , p) \u003d +1 ,
  • H (C 5 , p) = -1 ,
  • H (C 6 , p) = -1 ,
  • H (C 7 , p) = -1 ,
  • H (C 8 , p) = -1 ,
  • H (C 4 , p) = +1' vagy H (C 4 , p) = 0 a választott stratégiától függően.

A második típusú szabályok alkalmazása

A -példák meghatározásához az előző lépésben kapott (+)- és (-)-hipotéziseket használjuk . Esetünkben csak egy ilyen példa van: o 2 {s 1 , s 2 , s 4 , s 5 , s 7 }.

Tartalmazza a p tulajdonság jelenlétének egyik lehetséges okát (C 1 = {с 2 , с 4 }), és nem tartalmaz semmilyen lehetséges okot a p tulajdonság hiányára , ezért a stratégiában az ellen- tiltással. példák esetén az o 2 -t újradefiniáljuk (+)- példaként [3] .

Az n-edik lépésben kapott példahalmazra ismét az első, majd a második típusú szabályokat alkalmazzuk. Ez a folyamat mindaddig folytatódik, amíg az összes -example definícióra nem kerül.

Az oksági teljesség tesztelése

Az ok-okozati teljesség ellenőrzése, mint korábban említettük, abduktív érvelés segítségével történik. Az ok-okozati teljesség feltétele akkor teljesül, ha a p céltulajdonság jelenlétének legalább egy lehetséges oka be van ágyazva minden forrás (+)-példába , és legalább egy lehetséges oka annak hiányának minden (-)-példába. .

Esetünkben minden kezdeti pozitív és negatív példa magyarázatra kerül.

Eredmény

Így a következő elfogadható (és valójában érvényes) elegendő feltételeket kaptuk egy nemtriviális szimmetriájú konvex négyszög körül írható körhöz :

  1. van egy szimmetriatengely, amely nem átlós,
  2. van egy átlós szimmetriatengely, és egyben van egy ellentétes derékszög pár.

Lásd még

Jegyzetek

  1. Ebben az esetben a (+)-, (-) és (0)-feltételt kielégítő halmazok meghatározásához meg kell találni a töredékek összes lehetséges nem üres metszetét a (+)- halmazhoz. , (-)- és (0)- példák. Egy adott halmaz összes metszetének (hasonlóságának) megtalálása külön kombinatorikus feladat, amelyre számos algoritmus ismert, amelyek közül a leghatékonyabb a Norris-algoritmus .
  2. A H függvény a stratégiától függően eltérően definiálható (ellenpéldák tiltásával vagy anélkül).
  3. Egy óvatosabb, ellenpéldák tilalma nélküli stratégiájában megjegyezzük, hogy ezen kívül még egy ellentmondásos hipotézis is beágyazódik, ezért o 1 -et (nyilván o 2 -re gondolunk !) definiáljuk újra (0)- példa.

Irodalom

  • Hipotézisek automatikus generálása intelligens rendszerekben. Összeg. E. S. Pankratova, V. K. Finn. — M.: LIBROKOM, 2009. — 528 p.
  • JSM-módszer a hipotézisek automatikus generálására: logikai és episztemológiai alapok. Összeg. O. M. Anshakov, E. F. Fabrikantova. — M.: LIBROKOM, 2009. — 432 p.
  • Finn V.K. A plauzibilis érvelés többértékű logikával történő formalizálásának lehetőségéről Vsesoyuzn. symp. a tudomány logikájáról és módszertanáról. - Kijev: Naukova Dumka, 1976. - S. 82-83.
  • Finn V.K. A plauzibilis érvelés géporientált formalizálásáról F. Bacon stílusában – D.S. Mill // Szemiotika és informatika. - 1983. - Kiadás. 20. - S. 35-101.
  • Anshakov OM, Finn VK, Skvortsov DP A plauzibilis érvelés formalizálásával kapcsolatos sokértékű logikák axiomatizálásáról // Studia Logica. 1989. évf. 48. No. 4. P. 423-447.
  • Anshakov O. M., Skvortsov D. P., Finn V. K. A JSM-módszer néhány változatának deduktív utánzásáról hipotézisek automatikus generálására // Szemiotika és informatika.- 1993.- Vol. 33.- S. 164-233.
  • Finn VK A JSM módszer, mint adatbányászati ​​eszköz jellemzőiről // NTI. Ser. 2. - 2001. - 5. sz. - S. 1-4.
  • Vinogradov DV Aszimmetrikus JSM-módszer a kontextus figyelembevételével // Ötödik nemzeti konferencia nemzetközi részvétellel. Mesterséges intelligencia-96. - Kazany: 1996. - KII-96: Szo. tudományos tr.: 3 kötetben - Kazan: Assoc. művészetek. hírszerzés, 1996.
  • Anshakov O. M., Skvortsov D. P., Finn V. K. A JSM módszer logikai felépítéséről a hipotézisek automatikus generálására // Dokl. Szovjetunió Tudományos Akadémia, 320. kötet, 6. szám - 1991. - S. 1331-1334.
  • Kuznetsov S. O. A JSM módszer predikátumai a Galois levelezési nyelven // Tudományos és műszaki információk (NTI), Ser. 2, 2006, 12. szám, 12-16.
  • Kuznetsov S. O. JSM-módszer, mint az automatikus tanulás rendszere // Itogi nauki i tekhniki, Ser. Informatika, 1991, 15. évf., S.17-54.

Linkek