DSM metode

JSM-metoden er en metode til automatisk generering af hypoteser . Det formaliserer et skema for en plausibel og pålidelig konklusion, kaldet JSM-ræsonnement.

JSM-ræsonnement er en syntese af kognitive procedurer: induktion , analogi og abduktion . JSM-metoden blev skabt som et middel til automatiseret konstruktion af formalisering af viden om fagområdet ved hjælp af de såkaldte kvasi-aksiomatiske teorier (QAT).

Historie

JSM-metoden til automatisk generering af hypoteser blev foreslået af W. K. Finn i slutningen af halvfjerdserne. Navnet på metoden er initialerne på den berømte engelske filosof, logiker og økonom John Stuart Mill , hvis "metoder for en sund naturforsker" er delvist formaliseret i JSM-metoden.

Historisk set er det første eksempel på opgaver, som DSM-systemer blev brugt til, identifikation af kausale mønstre af struktur-aktivitetstypen i farmakologi . I 1997-1998 blev der udført en række computerforsøg , hvis formål var at vurdere muligheden for at skabe et intelligent system , der ville gøre det muligt at bestemme graden af risiko for, at en patient får et recidiv af hypofyseadenom efter dets fjernelse. Med udgangspunkt i den kvantitative DSM-metode blev der udviklet et eksperimentelt system til at forudsige recidiv af hypofyseadenom, som har arbejdsnavnet HTRD (Hypophisis tumor relapse diagnostics). Derudover er JSM-systemer med succes blevet brugt i problemerne med teknisk diagnostik og i studiet af determinanter for sociologisk adfærd.

I øjeblikket udvikles DSM-systemer hos VINITI RAS og ved Institut for Matematik, Logik og Intelligente Systemer ved det russiske statslige humanitære universitet under ledelse af V.K. Finn.

Beskrivelse af metoden

JSM-metoden fungerer med entiteter af tre typer: objekter i emneområdet, egenskaber for disse objekter og mulige årsager til egenskaber.

Det antages, at objekter har en struktur, og årsagerne til genstandes egenskaber er fragmenter af denne struktur.

Eksempel:

Objektet er et planteblad. Objektets egenskab er grøn. Årsagen til ejendommen er klorofyl.

Som input modtager JSM-metoden et bestemt sæt af undersøgte objekter og information om deres struktur, om tilstedeværelsen eller fraværet af bestemte egenskaber i dem, og også, i nogle tilfælde, om forholdet mellem strukturen af objekter og deres egenskaber. Derudover er der en række målfunktioner, som hver opdeler det originale sæt af objekter i fire ikke-overlappende undersæt:

objekter, der vides at have en given egenskab,

genstande, om hvilke det vides, at de ikke har denne egenskab,

genstande, for hvilke der er argumenter både for og imod, at de har en given egenskab,

genstande, som det ikke vides, om de har denne egenskab eller ej.

Resultatet af at anvende JSM-metoden er hypoteser af to typer:

hypoteser om forholdet mellem visse strukturelle fragmenter af de undersøgte objekter og de egenskaber, de besidder,
hypoteser om tilstedeværelsen eller fraværet af måltræk i objekter, for hvilke dette oprindeligt var ukendt, dannet på grundlag af et etableret forhold mellem objekters egenskaber og deres strukturelle komponenter.

Trin af JSM-metoden

Overvej et trin af JSM-metoden i sin enkleste form.

O er et sæt af objekter,
P er et sæt af objektegenskaber (målegenskaber),
C er sættet af mulige årsager til objektegenskaber (elementer i objektstrukturen),
V er mængden af estimater. V = {+1, −1, 0, }. $\tau$

Der er en funktion P: O→ $2^{C}$ , der afbilder til hvert objekt o en delmængde af fragmenter (strukturelle elementer), der forekommer i objektet o.

Lad os introducere en funktion F: O×P→V , der repræsenterer startsituationen.

F(o, p) = +1 — objekt o vides at have egenskaben p;
F(o, p) = −1 — det er kendt, at objektet o ikke har egenskaben p;
F(o, p) = 0 - der er argumenter både for og imod, at objektet o har egenskaben p;
F(o, p)= $\tau$ — det vides ikke, om objektet o har egenskaben p.

Funktionen F kan repræsenteres som en matrix:

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

Hvis f ij = $\tau$ , så siger vi, at for parret (o i , p j ) er funktionen F(o i , p j ) underbestemt. JSM-metodens opgave er at færdiggøre den indledende matrix ved hjælp af hypotesedannelsen .

Regler af den første slags

Lad os danne hypoteser om de mulige årsager til egenskaberne. Som et resultat får vi funktionen H: C×P→V.

H(c, p) = +1 - c er en mulig årsag til tilstedeværelsen af egenskaben p eller en (+)-hypotese;

H(c, p) = −1 - c er en mulig årsag til fraværet af egenskaben p eller en (-)-hypotese;

H(c, p) = 0 - der er argumenter både for, at c er årsagen til tilstedeværelsen af egenskaben p, og for det faktum, at c er årsagen til fraværet af denne egenskab eller (+)-hypotese (modsigende hypotese);

H(c, p) = $\tau$ - det vides ikke, om c er årsagen til tilstedeværelsen af p eller årsagen til fraværet af denne egenskab.

Værdierne af funktionen H for hvert par (c, p) findes ved hjælp af reglerne for plausibel inferens. Disse regler kaldes regler af den første slags. Forkortelsen er PIR 1 (for Plausible Inference Rules). Regler af den første slags kan ses som en funktion, der bruger matricen F til at opnå matricen H, det vil sige
H = PIR 1 (F) .

Lad p være en egenskab.
Objektet o er:

et positivt eksempel eller (+)-eksempel for p i forhold til den oprindelige matrix F, hvis F(o, p) = +1 ,
negativt eksempel eller (-)-eksempel for p i forhold til den oprindelige matrix F, hvis F(o, p) = −1 ,
et modstridende eksempel eller et (0)-eksempel for p i forhold til den oprindelige matrix F, hvis F(o, p) = 0 .

Lad F + [p], F - [p], F 0 [p] betegne mængden af alle henholdsvis positive, negative og modstridende eksempler for p med hensyn til F.

Som mulige årsager til tilstedeværelsen/fraværet af objektegenskaber betragtes delmængder af sættet af fragmenter C [1] . Et sæt C' ⊆ C opfylder (+)-betingelsen for p i forhold til F, hvis der eksisterer Ω ⊆ F + [p] , således at:

$C'=\bigcap _{o\in \Omega }P(o)$ , det vil sige, at hvert objekt fra Ω indeholder alle fragmenter fra mængden C', og der er ingen yderligere fragmenter, der tilhører alle ; $P(o)$ $o\in \Omega$
Ω indeholder mindst to elementer.

(-)- og (0)-betingelser er ens.

Lad M + (F, c, p) angive, at c opfylder (+)-betingelsen for p i forhold til F .
Gennem M - (F, c, p) det faktum, at c opfylder (-)-betingelsen for p med hensyn til F .
Gennem M 0 (F, c, p) det faktum, at c opfylder (0)-betingelsen for p i forhold til F .

Lad os nu definere funktionen H [2] . Lad os sætte:

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

Med andre ord omdefineres sættet af fragmenter C i ⊆C som

en mulig årsag til tilstedeværelsen af egenskaben p, hvis den er indlejret i to eller flere (+)-eksempler, ikke mere end ét (-)-eksempel) og ikke mere end ét (0)-eksempel;
en mulig årsag til fraværet af egenskaben p, hvis den er indlejret i to eller flere (-)-eksempler, højst ét (+)-eksempel og højst ét (0)-eksempel.

Regler af anden art

Ved at bruge matrixen af hypoteser om mulige årsager er det muligt at danne hypoteser om tilstedeværelsen eller fraværet af egenskaben p for de objekter fra O , for hvilke det ikke oprindeligt var kendt, om de har denne egenskab eller ej, det vil sige for dem o O for hvilken F(o, p ) = . $\i$ $\tau$

Som et resultat får vi funktionen F': O×P→V. F'(o, p) = F(o, p) hvis F(o, p) ≠ $\tau$ . Hvis F(o, p) = $\tau$ , så kan F'(o, p) tage en hvilken som helst værdi fra V :

F'(o, p) = +1 - o har muligvis egenskaben p,
F'(o, p) = −1 - o har muligvis ikke egenskaben p,
F'(o, p) = 0 - der er argumenter både for og imod, at objektet o har egenskaben p,
F'(o, p) = $\tau$ — det var ikke muligt at færdiggøre cellen i den oprindelige matrix F.

Værdierne af funktionen F' findes ved hjælp af reglerne for plausibel inferens. Disse regler kaldes regler af den anden art. Forkortet betegnelse - PIR 2 . Regler af den anden art kan ses som en funktion, der bruger matricerne F og H til at opnå matricen F', det vil sige F' = PIR 2 (F, H) .

Lad o være et objekt, p en egenskab. Vi vil sige, at objektet o opfylder

(+)-betingelse for p i forhold til H (det vil sige, den har muligvis egenskaben p), hvis der eksisterer c C sådan, at c⊆o og H(c, p) = +1. $\i$
(-)-betingelse for p i forhold til H (det vil sige, at den ikke har egenskaben p), hvis der eksisterer c C sådan, at c⊆o og H(c, p) = −1. $\i$
(0)-betingelse for p med hensyn til H (dvs. der er argumenter både for og imod, at o har egenskaben p), hvis der eksisterer c C sådan, at c⊆o og H(c, p) = 0. $\i$

Med + (H, o, p), - (H, o, p), 0 (H, o, p) angiver vi det faktum, at objektet o for egenskaben p med hensyn til H opfylder (+)-betingelsen, henholdsvis (-) -tilstand og 0-tilstand. Lad os sige: F'(o, p) = F(o, p) hvis F(o, p) ≠ ; Ellers $\Pi$ $\Pi$ $\Pi$ $\tau$

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

Regler af den første art (induktionsprocedure) og regler af den anden art (analogiprocedure) anvendes konsekvent, indtil mindst én ny hypotese er genereret som et resultat af deres arbejde, det vil sige, at anvendelsen af regler af den første art fører til en ændring i hypotesematrixen om mulige årsager til objekters egenskaber, og anvendelsen af reglerne af den anden art er at ændre hypotesematrixen om mulig tilstedeværelse eller fravær af egenskaben p i objekter. I dette tilfælde er trinnummeret en indikator for ræsonnementets plausibilitet.

Verifikation af betingelsen om kausal fuldstændighed

Det næste trin i arbejdet med JSM-metoden er at kontrollere tilstanden af kausal fuldstændighed. Verifikationen af denne tilstand fortolkes som ræsonnement ved bortførelse - betingelsen er opfyldt, hvis de resulterende hypoteser forklarer de oprindelige data, det vil sige, hvis hypoteserne om de mulige årsager til objekters egenskaber, opnået som et resultat af anvendelse af reglerne i den første type, kan forklare tilstedeværelsen eller fraværet af egenskaben p i objekter, for hvilke det i første omgang (før anvendelse af procedurerne for induktion og analogi) er kendt, at de har eller ikke har egenskaben p.

Formålet med at kontrollere tilstanden er at afgøre, om de hypoteser, der er opnået som følge af metoden, kan accepteres. Hvis betingelsen om kausal fuldstændighed ikke er opfyldt, er det nødvendigt at ændre den anvendte kognitive teknik (for eksempel at vælge en anden måde at indkode objektstrukturen på) eller inputsættet af objekter (som regel udvides sættet ).

Eksempel

Lad os prøve, ved hjælp af JSM-metoden, at besvare følgende spørgsmål: hvilke egenskaber skal en konveks firkant med ikke-trivial symmetri have for at kunne beskrive en cirkel omkring den , eller omvendt, det var umuligt at beskrive en cirkel.

Overvej følgende sæt domæneobjekter:

o 1 - kvadrat ,
o 2 er et rektangel ,
o 3 - rombe ,
o 4 - parallelogram ,
o 5 - ligebenet trapez ,
o 6 - deltoid ,
o 7 - rektangulær deltoideus.

Til disse objekter vælger vi følgende sæt af strukturelle fragmenter C:

c 1 er symmetriens centrum,
c 2 - er symmetriaksen ,
c 3 - der er en symmetriakse, som er en diagonal ,
c 4 - der er en symmetriakse, der ikke er en diagonal,
c 5 - nøjagtig en omdrejning med 180⁰ gør figuren til sig selv,
c 6 -rækkefølgen af symmetrigruppen er lig med to,
c 7 - der er et par modsatte rette vinkler ,
c 8 - ingen ret vinkel,
c 9 - ingen symmetriakse eller nogen symmetriakse er en diagonal.

sættet af målfunktioner i dette tilfælde består kun af én funktion:

p - du kan beskrive cirklen.

Lad os præsentere de indledende data i form af en tabel:

	s	c 1	c 2	c 3	c 4	fra 5	fra 6	fra 7	fra 8	fra 9
o 1 (firkantet)	+	+	+	+	+	-	-	+	-	-
o 2 (rektangel)	$\tau$	+	+	-	+	+	-	+	-	-
o 3 (diamant)	-	+	+	+	-	+	-	-	+	+
o 4 (parallelogram)	-	+	-	-	-	+	+	-	+	+
o 5 (ligebenet trapez)	+	-	+	-	+	-	+	-	+	-
o 6 (deltoidea)	-	-	+	+	-	-	+	-	+	+
o 7 (rektangulær deltoid)	+	-	+	+	-	-	+	+	-	+

Lad os repræsentere hvert af objekterne ved et sæt af strukturelle komponenter, som dette objekt har:

o 1 (firkantet) {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 (parallelogram) {s 1 , s 5 , s 6 , s 8 , s 9 };
o 5 (ligebenet trapez) {s 2 , s 4 , s 6 , s 8 };
o 6 (deltoide) {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 vores tilfælde er positive eksempler for målegenskaben p objekter o 1 , o 5 og o 7 , negative eksempler er o 3 , o 4 og o 6 . Der er også et ( )-eksempel - o 2 . $\tau$

Vores opgave er at bruge plausible ræsonnementer til at finde ud af, om ( )-eksempler har målegenskaben p eller ej. $\tau$

Anvendelse af regler af den første art

Her vil vi som mulige årsager til tilstedeværelsen/fraværet af egenskaben p i objekter overveje nogle ikke-tomme delmængder af sættet af strukturelle fragmenter C. (+)-betingelsen er opfyldt af sættene:

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

(-)-betingelsen er opfyldt af sættene:

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

Nu er det nødvendigt at finde ud af, om de fundne sæt er mulige årsager til tilstedeværelsen eller fraværet af målegenskaben p i objekter, det vil sige at bestemme funktionen H for dette trin. Som tidligere nævnt kan reglerne for at definere denne funktion have en forskellig form afhængig af den valgte strategi - med eller uden forbud mod modeksempler.

Sættet C i C vil blive udvidet som $\subseteq$

en mulig årsag til tilstedeværelsen af egenskaben p , hvis C i opfylder (+)-betingelsen for p , dvs. den er indlejret som en delmængde i to eller flere (+)-eksempler og ikke er indlejret i nogen (indlejret i ingen mere end ét) (- )-eksempel;
en mulig årsag til fraværet af egenskaben p , C i opfylder (-)-betingelsen for p , dvs. den er indlejret som en delmængde i to eller flere (-)-eksempler og er ikke indlejret i nogen (er indlejret i ikke mere end ét) (+) -eksempel;
en modstridende hypotese, hvis der både eksisterer et (+)-eksempel og et (-)-eksempel, hvori C i er indlejret .

Ved at analysere vores data får vi to mulige årsager til tilstedeværelsen af p -ejendommen :

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

Sættet af fragmenter C 4 = {с 2 , с 6 } bliver en (+)-hypotese eller en modstridende hypotese, afhængig af strategien.

Alle sæt, der opfylder (-)-betingelsen for p , defineres yderligere som mulige årsager til fraværet af egenskab p .

Det er,

H (C1 , p) = +1 ,
H (C2 , 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 afhængig af den valgte strategi.

Anvendelse af regler af anden art

Vi bruger (+)- og (-)-hypoteserne opnået i det foregående trin til at bestemme -eksempler. I vores tilfælde er der kun et sådant eksempel: o 2 {s 1 , s 2 , s 4 , s 5 , s 7 }. $\tau$

Den inkluderer en mulig årsag til tilstedeværelsen af egenskaben p (C 1 = {с 2 , с 4 }) og inkluderer ikke nogen mulig årsag til fraværet af egenskaben p , derfor i strategien med forbud mod mod- eksempler, omdefinerer vi o 2 som (+)- eksempel [3] .

Til det sæt af eksempler, der blev opnået på det n'te trin, anvendes reglerne for den første og derefter den anden slags igen. Denne proces fortsætter, indtil alle -eksempler er defineret. $\tau$

Test af kausal fuldstændighed

Verifikationen af kausal fuldstændighed udføres, som tidligere nævnt, ved hjælp af abduktiv ræsonnement. Betingelsen for kausal fuldstændighed er opfyldt, hvis mindst én mulig årsag til tilstedeværelsen af målegenskaben p er indlejret i hvert kilde (+)-eksempel , og mindst én mulig årsag til dets fravær er indlejret i hvert (-)-eksempel .

I vores tilfælde er hvert indledende positive og negative eksempel forklaret.

Resultat

Således har vi opnået følgende plausible (og faktisk gyldige) tilstrækkelige betingelser til, at en cirkel kan beskrives omkring en konveks firkant med ikke-trivial symmetri :

der er en symmetriakse, der ikke er en diagonal,
der er en diagonal symmetriakse, og samtidig er der et par modsatte rette vinkler.

Se også

Intelligent informationssystem
Ekspertsystem
Automatiseret informationssystem
Hybrid intelligent system
Intelligente systemer i humaniora (Institute of Linguistics of the Russian State Humanitarian University) — afdeling, der udvikler JSM-metoden

Noter

↑ I dette tilfælde, for at bestemme de mængder, der opfylder (+)-, (-) og (0)-betingelserne, er det nødvendigt at finde alle mulige ikke-tomme skæringer af fragmenter for sættet af (+)- , (-)- og (0)- eksempler. At finde alle skæringspunkter (lighed) af et givet sæt er et separat kombinatorisk problem, for hvilket der kendes en række algoritmer, hvoraf den mest effektive er Norris-algoritmen .
↑ Funktionen H kan defineres forskelligt afhængigt af strategien (med eller uden forbud mod modeksempler).
↑ I en mere forsigtig strategi uden forbud mod modeksempler bemærker vi, at der udover dette er en modstridende hypotese indlejret i den, og derfor omdefinerer vi o 1 (tilsyneladende mener vi o 2 !) som en (0)- eksempel.

Litteratur

Automatisk generering af hypoteser i intelligente systemer. Comp. E. S. Pankratova, V. K. Finn. — M.: LIBROKOM, 2009. — 528 s.
JSM-metoden til automatisk generering af hypoteser: logiske og epistemologiske grundlag. Comp. O. M. Anshakov, E. F. Fabrikantova. — M.: LIBROKOM, 2009. — 432 s.
Finn V.K. Om muligheden for at formalisere plausible ræsonnementer ved hjælp af flerværdilogikker. Vsesoyuzn. symp. om videnskabens logik og metodologi. - Kiev: Naukova Dumka, 1976. - S. 82-83.
Finn V.K. Om maskinorienteret formalisering af plausible ræsonnementer i stil med F. Bacon — D.S. Mill // Semiotik og informatik. - 1983. - Udgave. 20. - S. 35-101.
Anshakov OM, Finn VK, Skvortsov DP Om aksiomatisering af mange værdsatte logikker forbundet med formalisering af plausible ræsonnementer // Studia Logica. 1989 bind. 48. nr. 4. S. 423-447.
Anshakov O. M., Skvortsov D. P., Finn V. K. Om deduktiv efterligning af nogle varianter af JSM-metoden til automatisk generering af hypoteser // Semiotics and Informatics.— 1993.— Vol. 33.- S. 164-233.
Finn VK Om funktionerne i JSM-metoden som et middel til datamining // NTI. Ser. 2. - 2001. - Nr. 5. - S. 1-4.
Vinogradov DV Asymmetrisk JSM-metode under hensyntagen til konteksten // Femte nationale konference med international deltagelse Kunstig intelligens-96. - Kazan: 1996. - KII-96: Lør. videnskabelig tr.: I 3 bind - Kazan: Assoc. kunst. efterretningstjeneste, 1996.
Anshakov O. M., Skvortsov D. P., Finn V. K. Om den logiske konstruktion af JSM-metoden til automatisk generering af hypoteser // Dokl. USSR's Videnskabsakademi, bind 320, nr. 6. - 1991. - S. 1331-1334.
Kuznetsov S. O. Prædikater for JSM-metoden i Galois korrespondancesprog // Scientific and Technical Information (NTI), Ser. 2, 2006, nr. 12, s. 12-16.
Kuznetsov S. O. JSM-metode som et system for automatisk læring // Itogi nauki i tekhniki, Ser. Informatik, 1991, bind 15, S.17-54.