DSM-metoden

JSM-metoden är en metod för automatisk generering av hypoteser . Den formaliserar ett schema för en rimlig och tillförlitlig slutsats, kallad JSM-resonemang.

JSM-resonemang är en syntes av kognitiva procedurer: induktion , analogi och abduktion . JSM-metoden skapades som ett medel för automatiserad konstruktion av formalisering av kunskap om ämnesområdet med hjälp av de så kallade kvasi-axiomatiska teorierna (QAT).

Historik

JSM-metoden för att automatiskt generera hypoteser föreslogs av W. K. Finn i slutet av sjuttiotalet. Namnet på metoden är initialerna för den berömde engelske filosofen, logikern och ekonomen John Stuart Mill , vars "metoder för en sansad naturforskare" delvis formaliseras i JSM-metoden.

Historiskt sett är det första exemplet på uppgifter för vilka DSM-system användes identifieringen av kausala mönster av struktur-aktivitetstypen inom farmakologi . Under 1997-1998 genomfördes ett antal datorexperiment , vars syfte var att bedöma möjligheten att skapa ett intelligent system som skulle göra det möjligt att bestämma graden av risk för att en patient skulle få ett återfall av hypofysadenom efter avlägsnandet. Baserat på den kvantitativa DSM-metoden utvecklades ett experimentellt system för att förutsäga återfall av hypofysadenom som har arbetsnamnet HTRD (Hypophisis tumor relapse diagnostics). Dessutom har JSM-system framgångsrikt använts i problemen med teknisk diagnostik och i studiet av bestämningsfaktorerna för sociologiskt beteende.

För närvarande utvecklas DSM-system vid VINITI RAS och vid institutionen för matematik, logik och intelligenta system vid Russian State Humanitarian University under ledning av V.K. Finn.

Beskrivning av metoden

JSM-metoden fungerar med enheter av tre typer: objekt i ämnesområdet, egenskaper hos dessa objekt och möjliga orsaker till egenskaper.

Det antas att objekt har en struktur och orsakerna till objektens egenskaper är fragment av denna struktur.

Exempel:

Objektet är ett växtblad. Objektets egenskap är grön. Anledningen till fastigheten är klorofyll.

Som input får JSM-metoden en viss uppsättning studerade objekt och information om deras struktur, om förekomsten eller frånvaron av vissa egenskaper i dem, och även, i vissa fall, om förhållandet mellan objektens struktur och deras egenskaper. Dessutom finns det ett antal målfunktioner, som var och en delar upp den ursprungliga uppsättningen objekt i fyra icke-överlappande delmängder:

objekt som är kända för att ha ett givet attribut,

föremål om vilka det är känt att de inte har detta attribut,

objekt för vilka det finns argument både för och emot att de har en given egenskap,

föremål som det inte är känt om de har denna egenskap eller inte.

Resultatet av att tillämpa JSM-metoden är hypoteser av två typer:

hypoteser om förhållandet mellan vissa strukturella fragment av de studerade föremålen med de egenskaper som de besitter,
hypoteser om närvaron eller frånvaron av målegenskaper i objekt för vilka detta från början var okänt, bildade på basis av ett etablerat samband mellan objektens egenskaper och deras strukturella komponenter.

Steg av JSM-metoden

Betrakta ett steg av JSM-metoden i dess enklaste form.

O är en uppsättning objekt,
P är en uppsättning objektegenskaper (målfunktioner),
C är uppsättningen av möjliga orsaker till objektegenskaper (element i objektstrukturen),
V är uppsättningen av uppskattningar. V = {+1, −1, 0, }. $\tau$

Det finns en funktion P: O→ $2^{C}$ som mappar till varje objekt o en delmängd av fragment (strukturella element) som förekommer i objektet o.

Låt oss introducera en funktion F: O×P→V som representerar initialsituationen.

F(o, p) = +1 — objekt o är känt för att ha egenskapen p;
F(o, p) = −1 — det är känt att objektet o inte har egenskapen p;
F(o, p) = 0 - det finns argument både för och emot att objektet o har egenskapen p;
F(o, p)= $\tau$ — det är inte känt om objektet o har egenskapen p.

Funktionen F kan representeras som en matris:

${\begin{bmatrix}f_{11}&\cdots &f_{1j}\\\vdots &\ddots &\vdots \\f_{i1}&\cdots &f_{ij}\end{bmatrix))$

Om f ij = $\tau$ , då säger vi att för paret (o i , p j ) är funktionen F(o i , p j ) underbestämd. JSM-metodens uppgift är att komplettera den initiala matrisen med hjälp av hypotesbildningen .

Regler av det första slaget

Låt oss skapa hypoteser om de möjliga orsakerna till egenskaperna. Som ett resultat får vi funktionen H: C×P→V.

H(c, p) = +1 - c är en möjlig orsak till närvaron av egenskapen p eller en (+)-hypotes;

H(c, p) = −1 - c är en möjlig orsak till frånvaron av egenskap p eller en (-)-hypotes;

H(c, p) = 0 - det finns argument både för att c är orsaken till egenskapen p, och för att c är orsaken till frånvaron av denna egenskap eller (+)-hypotes (motsägelsefull hypotes);

H(c, p) = $\tau$ - det är inte känt om c är orsaken till närvaron av p eller orsaken till frånvaron av denna egenskap.

Värdena för funktionen H för varje par (c, p) hittas med hjälp av reglerna för rimlig slutledning. Dessa regler kallas regler av det första slaget. Förkortningen är PIR 1 (för Plausible Inference Rules). Regler av det första slaget kan ses som en funktion som använder matrisen F för att erhålla matrisen H, det vill säga
H = PIR 1 (F) .

Låt p vara någon egenskap.
Objektet o är:

ett positivt exempel eller (+)-exempel för p med avseende på den ursprungliga matrisen F om F(o, p) = +1 ,
negativt exempel eller (-)-exempel för p med avseende på den ursprungliga matrisen F om F(o, p) = −1 ,
ett motsägelsefullt exempel eller ett (0)-exempel för p med avseende på den ursprungliga matrisen F om F(o, p) = 0 .

Låt F + [p], F - [p], F 0 [p] beteckna mängden av alla positiva, negativa och motsägelsefulla exempel för p med avseende på F, respektive.

Som möjliga orsaker till närvaron/frånvaron av objektegenskaper betraktas delmängder av uppsättningen av fragment C [1] . En mängd C' ⊆ C uppfyller (+)-villkoret för p med avseende på F om det finns Ω ⊆ F + [p] så att:

$C'=\bigcap _{o\in \Omega }P(o)$ , det vill säga varje objekt från Ω innehåller alla fragment från mängden C', och det finns inga ytterligare fragment som tillhör alla ; $P(o)$ $o\in \Omega$
Ω innehåller minst två element.

(-)- och (0)-villkor är likartade.

Låt M + (F, c, p) beteckna det faktum att c uppfyller (+)-villkoret för p med avseende på F .
Genom M - (F, c, p) det faktum att c uppfyller (-)-villkoret för p med avseende på F .
Genom M 0 (F, c, p) det faktum att c uppfyller (0)-villkoret för p med avseende på F .

Låt oss nu definiera funktionen H [2] . Låt oss sätta:

$H(c,p)={\begin{cases}+1,&{\text{if}}M^{+}(F,c,p)\Och \linte M^{-}(F ,c,p)\Och \linte M^{0}(F,c,p),\\-1,&{\text{if}}M^{-}(F,c,p)\Och \ linte M^{+}(F,c,p)\Och \linte M^{0}(F,c,p),\\\quad 0,&{\text{if))(M^{+} (F,c,p)\Och M^{-}(F,c,p))\eller M^{0}(F,c,p),\\\quad \tau ,&{\text{if }}\linte M^{+}(F,c,p)\Och \linte M^{-}(F,c,p)\Och \linte M^{0}(F,c,p).\ slut{cases}}$

Med andra ord omdefinieras uppsättningen av fragment C i ⊆C som

en möjlig orsak till närvaron av egenskapen p om den är kapslad i två eller flera (+)-exempel, inte mer än ett (-)-exempel) och inte mer än ett (0)-exempel;
en möjlig orsak till frånvaron av egenskap p om den är kapslad i två eller flera (-)-exempel, högst ett (+)-exempel och högst ett (0)-exempel.

Regler av det andra slaget

Med hjälp av matrisen av hypoteser om möjliga orsaker är det möjligt att bilda hypoteser om närvaron eller frånvaron av egenskapen p för de objekt från O för vilka det från början inte var känt om de har denna egenskap eller inte, det vill säga för de o O för vilken F(o, p ) = . $\i$ $\tau$

Som ett resultat får vi funktionen F': O×P→V. F'(o, p) = F(o, p) om F(o, p) ≠ $\tau$ . Om F(o, p) = $\tau$ , så kan F'(o, p) ta vilket värde som helst från V :

F'(o, p) = +1 - o har möjligen egenskapen p,
F'(o, p) = −1 - o kanske inte har egenskapen p,
F'(o, p) = 0 - det finns argument både för och emot att objektet o har egenskapen p,
F'(o, p) = $\tau$ — det var inte möjligt att slutföra cellen i den ursprungliga matrisen F.

Värdena för funktionen F' hittas med hjälp av reglerna för rimlig slutledning. Dessa regler kallas regler av det andra slaget. Förkortad beteckning - PIR 2 . Regler av det andra slaget kan ses som en funktion som använder matriserna F och H för att erhålla matrisen F', det vill säga F' = PIR 2 (F, H) .

Låt o vara ett objekt, p en egenskap. Vi kommer att säga att objektet o uppfyller

(+)-villkor för p med avseende på H (det vill säga den har möjligen egenskap p) om det finns c C så att c⊆o och H(c, p) = +1. $\i$
(-)-villkor för p med avseende på H (det vill säga att det kanske inte har egenskapen p) om det finns c C så att c⊆o och H(c, p) = −1. $\i$
(0)-villkor för p med avseende på H (det vill säga det finns argument både för och emot att o har egenskapen p) om det finns c C så att c⊆o och H(c, p) = 0. $\i$

Med + (H, o, p), - (H, o, p), 0 (H, o, p) betecknar vi det faktum att objektet o för egenskapen p med avseende på H uppfyller (+)-villkoret, (-) -villkor respektive 0-villkor. Låt oss säga: F'(o, p) = F(o, p) om F(o, p) ≠ ; annat $\Pi$ $\Pi$ $\Pi$ $\tau$

$F'(o,p)={\begin{cases}+1,&{\text{if}}\Pi ^{+}(H,o,p)\Och \lnot \Pi ^{- }(H,o,p)\Och \linte \Pi ^{0}(H,o,p),\\-1,&{\text{if}}\Pi ^{-}(H,o, p)\Och \lnot \Pi ^{+}(H,o,p)\Och \lnot \Pi ^{0}((H,o,p),\\\quad 0,&{\text{if }}(\Pi ^{+}(H,o,p)\Och \Pi ^{-}(H,o,p))\lor \Pi ^{0}(H,o,p),\\ \quad \tau ,&{\text{if}}\lnot \Pi ^{+}(H,o,p)\Och \lnot \Pi ^{-}(H,o,p)\Och \lnot \ Pi ^{0}(H,o,p).\end{cases}}$

Regler av det första slaget (induktionsförfarande) och regler av det andra slaget (analogförfarande) tillämpas konsekvent tills minst en ny hypotes genereras som ett resultat av deras arbete, det vill säga tillämpningen av regler av det första slaget leder till att en förändring i matrisen av hypoteser om möjliga orsaker till objektens egenskaper, och tillämpningen av reglerna av det andra slaget är att ändra matrisen av hypoteser om möjlig närvaro eller frånvaro av egenskap p i objekt. I det här fallet är stegnumret en indikator på rimligheten i resonemang.

Verifiering av villkoret för orsaksfullständighet

Nästa steg i arbetet med JSM-metoden är att kontrollera tillståndet för orsaksfullständighet. Verifieringen av detta tillstånd tolkas som resonemang genom bortförande - villkoret är uppfyllt om de resulterande hypoteserna förklarar de initiala uppgifterna, det vill säga om hypoteserna om de möjliga orsakerna till objektens egenskaper, erhållna som ett resultat av att tillämpa reglerna för den första typen, kan förklara förekomsten eller frånvaron av egenskap p i objekt för vilka det initialt (innan man tillämpar procedurerna för induktion och analogi) är känt att de har eller inte har egenskapen p.

Syftet med att kontrollera tillståndet är att avgöra om de hypoteser som erhållits till följd av metoden kan accepteras. Om villkoret för orsaksfullständighet inte är uppfyllt, är det nödvändigt att ändra den tillämpade kognitiva tekniken (till exempel för att välja ett annat sätt att koda strukturen av objekt) eller inmatningsuppsättningen av objekt (som regel utökas uppsättningen ).

Exempel

Låt oss försöka, med hjälp av JSM-metoden, svara på följande fråga: vilka egenskaper ska en konvex fyrhörning med icke-trivial symmetri ha för att kunna beskriva en cirkel runt den , eller vice versa, det var omöjligt att beskriva en cirkel.

Tänk på följande uppsättning domänobjekt:

o 1 - kvadrat ,
o 2 är en rektangel ,
o 3 - romb ,
o 4 - parallellogram ,
o 5 - likbent trapets ,
o 6 - deltoid ,
o 7 - rektangulär deltoid.

För dessa objekt väljer vi följande uppsättning strukturella fragment C:

c 1 är symmetricentrum,
c 2 - är symmetriaxeln ,
c 3 - det finns en symmetriaxel, som är en diagonal ,
c 4 - det finns en symmetriaxel som inte är en diagonal,
c 5 - exakt ett varv med 180⁰ förvandlar figuren till sig själv,
c 6 -ordningen för symmetrigruppen är lika med två,
c 7 - det finns ett par motsatta räta vinklar ,
c 8 - ingen rät vinkel,
c 9 - ingen symmetriaxel eller någon symmetriaxel är en diagonal.

uppsättningen målfunktioner i det här fallet består av endast en funktion:

p - du kan beskriva cirkeln.

Låt oss presentera de initiala uppgifterna i form av en tabell:

	sid	c 1	c 2	c 3	c 4	från 5	från 6	från 7	från 8	från 9
o 1 (fyrkantig)	+	+	+	+	+	-	-	+	-	-
o 2 (rektangel)	$\tau$	+	+	-	+	+	-	+	-	-
o 3 (diamant)	-	+	+	+	-	+	-	-	+	+
o 4 (parallellogram)	-	+	-	-	-	+	+	-	+	+
o 5 (likbent trapets)	+	-	+	-	+	-	+	-	+	-
o 6 (deltoid)	-	-	+	+	-	-	+	-	+	+
o 7 (rektangulär deltoid)	+	-	+	+	-	-	+	+	-	+

Låt oss representera vart och ett av objekten med en uppsättning strukturella komponenter som detta objekt har:

o 1 (kvadrat) {s 1 , s 2 , s 3 , s 4 , s 7 };
o 2 (rektangel) {s 1 , s 2 , s 4 , s 5 , s 7 };
o 3 (diamant) {s 1 , s 2 , s 3 , s 5 , s 8 , s 9 };
o 4 (parallellogram) {s 1 , s 5 , s 6 , s 8 , s 9 };
o 5 (isosceles trapezium) {s 2 , s 4 , s 6 , s 8 };
o 6 (deltoid) {s 2 , s 3 , s 6 , s 8 , s 9 };
o 7 (rektangulär deltoid) {s 2 , s 3 , s 6 , s 7 , s 9 }.

I vårt fall är positiva exempel för målegenskapen p objekt o 1 , o 5 och o 7 , negativa exempel är o 3 , o 4 och o 6 . Det finns också ett ( )-exempel - o 2 . $\tau$

Vår uppgift är att använda rimliga resonemang för att ta reda på om ( )-exempel har målegenskapen p eller inte. $\tau$

Tillämpning av regler av det första slaget

Här, som möjliga orsaker till närvaron/frånvaron av egenskap p i objekt, kommer vi att överväga några icke-tomma delmängder av uppsättningen av strukturella fragment C. (+)-villkoret är uppfyllt av uppsättningarna:

C1 = {с2 , с4 } : Q = {oi , o5 } ;
C2 = {с2 , с3 , с7 } : Q = {oi , o7 } ;
C3 = {с2 } : Q = {oi , o5 , o7 } ;
C4 = {с2 , с6 } : Ω = { o5 , o7 } .

(-)-villkoret är uppfyllt av uppsättningarna:

C5 = {сi , с5 , с8 , с9 } : Q = { o3 , o4 } ;
C6 = {с2 , с3 , с8 , с9 } : Q = { o3 , o6 } ;
C7 = {с8 , с9 } : Q = { o3 , o4 , o6 } ;
C8 = {с6 , с8 , с9 } : Q = { o4 , o6 } ;

Nu är det nödvändigt att ta reda på om de hittade uppsättningarna är möjliga orsaker till närvaron eller frånvaron av målegenskapen p i objekt, det vill säga att bestämma funktionen H för detta steg. Som nämnts tidigare kan reglerna för att definiera denna funktion ha en annan form beroende på vald strategi - med eller utan förbud mot motexempel.

Uppsättningen C i C kommer att utökas som $\subseteq$

en möjlig orsak till närvaron av egenskapen p om C i uppfyller (+)-villkoret för p , det vill säga den är inbäddad som en delmängd i två eller flera (+)-exempel och inte är inbäddad i något (inbäddat i nr. mer än ett) (- )-exempel;
en möjlig orsak till frånvaron av egenskapen p , C i uppfyller (-)-villkoret för p , det vill säga den är inbäddad som en delmängd i två eller flera (-)-exempel och är inte inbäddad i någon (är inbäddad i inte mer än ett) (+) -exempel;
en motsägelsefull hypotes om det finns både ett (+)-exempel och ett (-)-exempel där C i är inbäddad .

När vi analyserar våra data får vi två möjliga orsaker till närvaron av p- egenskapen :

C1 = {с2 , с4 } och
C 2 \u003d {c 2 , c 3 , c 7 }.

Uppsättningen av fragment C 4 = {с 2 , с 6 } blir en (+)-hypotes eller en motsägelsefull hypotes, beroende på strategin.

Alla uppsättningar som uppfyller (-)-villkoret för p definieras vidare som möjliga orsaker till frånvaron av egenskap p .

Det är,

H (Ci , p) = +1 ,
H (C 2 , p) \u003d +1 ,
H (C5 , p) = -1 ,
H (C6 , p) = -1 ,
H (C7 , p) = -1 ,
H (C8 , p) = -1 ,
H (C4 , p) = +1' eller H (C4 , p) = 0 beroende på den valda strategin.

Tillämpning av regler av det andra slaget

Vi använder (+)- och (-)-hypoteserna som erhölls i föregående steg för att bestämma -exempel. I vårt fall finns det bara ett sådant exempel: o 2 {s 1 , s 2 , s 4 , s 5 , s 7 }. $\tau$

Den inkluderar en möjlig orsak till närvaron av egenskapen p (C 1 = {с 2 , с 4 }) och inkluderar inte någon möjlig orsak till frånvaron av egenskapen p , därför i strategin med förbud mot mot- exempel, omdefinierar vi o 2 som (+)- exempel [3] .

På uppsättningen exempel som erhölls i det n:e steget tillämpas återigen reglerna för den första och sedan den andra typen. Denna process fortsätter tills alla -exempel är definierade. $\tau$

Testning för orsaksfullständighet

Verifieringen av orsakens fullständighet utförs, som tidigare nämnts, med hjälp av abduktiva resonemang. Villkoret för orsaksfullständighet är uppfyllt om minst en möjlig orsak till närvaron av målegenskapen p är inbäddad i varje källa (+)-exempel , och minst en möjlig orsak till dess frånvaro är inbäddad i varje (-)-exempel .

I vårt fall förklaras varje initialt positivt och negativt exempel.

Resultat

Således har vi erhållit följande rimliga (och faktiskt giltiga) tillräckliga villkor för att en cirkel ska beskrivas runt en konvex fyrhörning med icke-trivial symmetri :

det finns en symmetriaxel som inte är en diagonal,
det finns en diagonal symmetriaxel, och samtidigt finns det ett par motsatta räta vinklar.

Se även

Intelligent informationssystem
Expertsystem
Automatiserat informationssystem
Hybrid intelligent system
Intelligenta system inom humaniora (Institute of Linguistics of the Russian State Humanitarian University) — avdelning som utvecklar JSM-metoden

Anteckningar

↑ I det här fallet, för att bestämma uppsättningarna som uppfyller (+)-, (-) och (0)-villkoren, krävs det att hitta alla möjliga icke-tomma skärningar av fragment för uppsättningen av (+)- , (-)- och (0)- exempel. Att hitta alla skärningspunkter (likhet) för en given mängd är ett separat kombinatoriskt problem, för vilket ett antal algoritmer är kända, varav den mest effektiva är Norris-algoritmen .
↑ Funktionen H kan definieras olika beroende på strategi (med eller utan förbud mot motexempel).
↑ I en mer försiktig strategi utan förbud mot motexempel, noterar vi att utöver detta finns en motsägelsefull hypotes inbäddad i den, och därför omdefinierar vi o 1 (uppenbarligen menar vi o 2 !) som en (0)- exempel.

Litteratur

Automatisk generering av hypoteser i intelligenta system. Comp. E. S. Pankratova, V. K. Finn. — M.: LIBROKOM, 2009. — 528 sid.
JSM-metod för automatisk generering av hypoteser: logiska och epistemologiska grunder. Comp. O. M. Anshakov, E. F. Fabrikantova. — M.: LIBROKOM, 2009. — 432 sid.
Finn V.K. Om möjligheten att formalisera rimliga resonemang med hjälp av flervärdiga logiker. Vsesoyuzn. symp. om vetenskapens logik och metodik. - Kiev: Naukova Dumka, 1976. - S. 82-83.
Finn V.K. Om maskinorienterad formalisering av rimliga resonemang i stil med F. Bacon — D.S. Mill // Semiotik och informatik. - 1983. - Utgåva. 20. - S. 35-101.
Anshakov OM, Finn VK, Skvortsov DP Om axiomatisering av många värderade logiker associerade med formalisering av rimliga resonemang // Studia Logica. 1989 vol. 48. Nr 4. P. 423-447.
Anshakov O. M., Skvortsov D. P., Finn V. K. Om deduktiv imitation av några varianter av JSM-metoden för automatisk generering av hypoteser // Semiotics and Informatics.— 1993.— Vol. 33.- S. 164-233.
Finn VK Om egenskaperna hos JSM-metoden som ett medel för datautvinning // NTI. Ser. 2. - 2001. - Nr 5. - S. 1-4.
Vinogradov DV Asymmetrisk JSM-metod med hänsyn till sammanhanget // Femte nationella konferensen med internationellt deltagande Artificiell intelligens-96. - Kazan: 1996. - KII-96: Lör. vetenskaplig tr.: I 3 volymer - Kazan: Assoc. konst. intelligens, 1996.
Anshakov O. M., Skvortsov D. P., Finn V. K. Om den logiska konstruktionen av JSM-metoden för automatisk generering av hypoteser // Dokl. USSR:s vetenskapsakademi, volym 320, nr 6. - 1991. - S. 1331-1334.
Kuznetsov S. O. Predikat för JSM-metoden på Galois korrespondensspråk // Scientific and Technical Information (NTI), Ser. 2, 2006, nr 12, s. 12-16.
Kuznetsov S. O. JSM-metod som ett system för automatisk inlärning // Itogi nauki i tekhniki, Ser. Informatics, 1991, volym 15, S.17-54.