Metoda DSM

Metoda JSM este o metodă de generare automată a ipotezelor . Acesta formalizează o schemă pentru o concluzie plauzibilă și de încredere, numită raționament JSM.

Raționamentul JSM este o sinteză a procedurilor cognitive: inducție , analogie și abducție . Metoda JSM a fost creată ca mijloc de construcție automată a formalizării cunoștințelor despre domeniul de studiu prin intermediul așa-numitelor teorii cvasi-axiomatice (QAT).

Istorie

Metoda JSM pentru generarea automată a ipotezelor a fost propusă de W. K. Finn la sfârșitul anilor șaptezeci. Numele metodei este inițialele faimosului filosof, logician și economist englez John Stuart Mill , ale cărui „metode ale unui naturalist sănătos” sunt parțial formalizate în metoda JSM.

Din punct de vedere istoric, primul exemplu de sarcini pentru care au fost utilizate sistemele DSM este identificarea tiparelor cauzale de tip structură-activitate în farmacologie . În anii 1997-1998 , au fost efectuate o serie de experimente pe calculator , al căror scop a fost de a evalua posibilitatea creării unui sistem inteligent care să permită determinarea gradului de risc al unui pacient de a avea o recidivă a adenomului hipofizar după îndepărtarea acestuia. Pe baza metodei cantitative DSM a fost dezvoltat un sistem experimental de predicție a recidivei adenomului hipofizar, care poartă denumirea de lucru HTRD (Hypophisis tumor relapse diagnostics). În plus, sistemele JSM au fost utilizate cu succes în problemele de diagnosticare tehnică și în studiul determinanților comportamentului sociologic.

În prezent, sistemele DSM sunt dezvoltate la VINITI RAS și la Departamentul de matematică, logică și sisteme inteligente a Universității Umanitare de Stat din Rusia sub conducerea lui V.K. Finn.

Descrierea metodei

Metoda JSM operează cu entități de trei tipuri: obiecte din domeniul subiectului, proprietăți ale acestor obiecte și posibile cauze ale proprietăților.

Se presupune că obiectele au o structură , iar cauzele proprietăților obiectelor sunt fragmente ale acestei structuri.

Exemplu:

Obiectul este o frunză de plantă. Proprietatea obiectului este verde. Motivul proprietății este clorofila.

Ca intrare, metoda JSM primește un anumit set de obiecte studiate și informații despre structura lor, despre prezența sau absența anumitor proprietăți în ele și, de asemenea, în unele cazuri, despre relația dintre structura obiectelor și proprietățile lor. În plus, există o serie de caracteristici țintă, fiecare dintre acestea împarte setul original de obiecte în patru subseturi care nu se suprapun:

obiecte despre care se știe că au un anumit atribut,

obiecte despre care se știe că nu au acest atribut,

obiecte pentru care există argumente atât pro, cât și contra faptului că au un atribut dat,

obiecte despre care nu se știe dacă au acest atribut sau nu.

Rezultatul aplicării metodei JSM sunt ipoteze de două tipuri:

ipoteze despre relația dintre anumite fragmente structurale ale obiectelor studiate cu proprietățile pe care acestea le posedă,
ipoteze despre prezența sau absența trăsăturilor țintă în obiecte pentru care acest lucru a fost inițial necunoscut, formate pe baza unei relații stabilite între proprietățile obiectelor și componentele lor structurale.

Pasul metodei JSM

Luați în considerare un pas al metodei JSM în cea mai simplă formă.

O este un set de obiecte,
P este un set de proprietăți ale obiectului (trăsături țintă),
C este setul de cauze posibile ale proprietăților obiectului (elementele structurii obiectului),
V este setul de estimări. V = {+1, −1, 0, }. $\tau$

Există o funcție P: O→ $2^{C}$ care mapează la fiecare obiect o un subset de fragmente (elemente structurale) care apar în obiectul o.

Să introducem o funcție F: O×P→V reprezentând situația inițială.

F(o, p) = +1 — obiectul o este cunoscut ca având proprietatea p;
F(o, p) = −1 — se știe că obiectul o nu are proprietatea p;
F(o, p) = 0 - există argumente atât pro, cât și contra faptului că obiectul o are proprietatea p;
F(o, p)= $\tau$ — nu se știe dacă obiectul o are proprietatea p.

Funcția F poate fi reprezentată ca o matrice:

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

Dacă f ij = $\tau$ , atunci spunem că pentru perechea (o i , p j ) funcția F(o i , p j ) este subdeterminată. Sarcina metodei JSM este de a completa matricea inițială cu ajutorul formării de ipoteze .

Reguli de primul fel

Să formulăm ipoteze despre posibilele cauze ale proprietăților. Ca rezultat, obținem funcția H: C×P→V.

H(c, p) = +1 - c este un posibil motiv pentru prezența proprietății p sau a (+)-ipoteză;

H(c, p) = −1 - c este un posibil motiv pentru absența proprietății p sau a (-)-ipotezei;

H(c, p) = 0 - există argumente atât pentru faptul că c este motivul prezenței proprietății p, cât și pentru faptul că c este motivul absenței acestei proprietăți sau (+)-ipoteză (ipoteză contradictorie);

H(c, p) = $\tau$ - nu se știe dacă c este motivul prezenței lui p sau motivul absenței acestei proprietăți.

Valorile funcției H pentru fiecare pereche (c, p) sunt găsite folosind regulile de inferență plauzibilă. Aceste reguli se numesc reguli de primul fel. Abrevierea este PIR 1 (pentru Reguli de inferență plauzibilă). Regulile de primul fel pot fi privite ca o funcție care folosește matricea F pentru a obține matricea H, adică
H = PIR 1 (F) .

Fie p o proprietate.
Obiectul o este:

un exemplu pozitiv sau (+)-exemplu pentru p în raport cu matricea originală F dacă F(o, p) = +1 ,
exemplu negativ sau (-)-exemplu pentru p în raport cu matricea originală F dacă F(o, p) = −1 ,
un exemplu contradictoriu sau un (0)-exemplu pentru p în raport cu matricea originală F dacă F(o, p) = 0 .

Fie F + [p], F - [p], F 0 [p] să desemneze mulțimea tuturor exemplelor pozitive, negative și contradictorii pentru p în raport cu F, respectiv.

Ca posibile motive pentru prezența/absența proprietăților obiectului, sunt considerate submulțimi ale mulțimii de fragmente C [1] . O mulțime C' ⊆ C satisface condiția (+) pentru p față de F dacă există Ω ⊆ F + [p] astfel încât:

$C'=\bigcap _{o\in \Omega}P(o)$ , adică fiecare obiect din Ω conţine toate fragmentele din mulţimea C', şi nu există fragmente suplimentare aparţinând tuturor ; $P(o)$ $o\in \Omega$
Ω conține cel puțin două elemente.

Condițiile (-)- și (0) sunt similare.

Fie M + (F, c, p) să desemneze faptul că c satisface condiția (+) pentru p în raport cu F .
Prin M - (F, c, p) faptul că c satisface condiția (-) pentru p față de F .
Prin M 0 (F, c, p) faptul că c satisface condiția (0) pentru p față de F .

Acum să definim funcția H [2] . Sa punem:

$H(c,p)={\begin{cases}+1,&{\text{if}}M^{+}(F,c,p)\Și \lnu M^{-}(F ,c,p)\Și \lnu M^{0}(F,c,p),\\-1,&{\text{if}}M^{-}(F,c,p)\Și \ nu M^{+}(F,c,p)\Și \lnu M^{0}(F,c,p),\\\quad 0,&{\text{if))(M^{+} (F,c,p)\Și M^{-}(F,c,p))\lor M^{0}(F,c,p),\\\quad \tau ,&{\text{if }}\lnu M^{+}(F,c,p)\Și \lnu M^{-}(F,c,p)\Și \lnu M^{0}(F,c,p).\ sfârșit{cazuri}}$

Cu alte cuvinte, mulțimea fragmentelor C i ⊆C este redefinită ca

un posibil motiv pentru prezența proprietății p dacă este imbricată în două sau mai multe (+)-exemple, nu mai mult de un (-)-exemple) și nu mai mult de un (0)-exemple;
un posibil motiv pentru absența proprietății p dacă este imbricată în două sau mai multe (-)-exemple, cel mult un (+)-exemplu și cel mult un (0)-exemple.

Reguli de al doilea fel

Folosind matricea de ipoteze despre cauze posibile, se pot forma ipoteze despre prezenta sau absenta proprietatii p pentru acele obiecte din O pentru care nu se stie initial daca au aceasta proprietate sau nu, adica pentru acele o O pentru care F(o, p ) = . $\în$ $\tau$

Ca rezultat, obținem funcția F': O×P→V. F'(o, p) = F(o, p) dacă F(o, p) ≠ $\tau$ . Dacă F(o, p) = $\tau$ , atunci F'(o, p) poate lua orice valoare din V :

F'(o, p) = +1 - o are eventual proprietatea p,
F'(o, p) = −1 - o poate să nu aibă proprietatea p,
F'(o, p) = 0 - există argumente atât pro, cât și contra faptului că obiectul o are proprietatea p,
F'(o, p) = $\tau$ — nu a fost posibilă completarea celulei matricei originale F.

Valorile funcției F’ sunt găsite folosind regulile de inferență plauzibilă. Aceste reguli se numesc reguli de al doilea fel. Denumire prescurtată - PIR 2 . Regulile de al doilea fel pot fi privite ca o funcție folosind matricele F și H pentru a obține matricea F', adică F' = PIR 2 (F, H) .

Fie o un obiect, p o proprietate. Vom spune că obiectul o satisface

(+)-condiție pentru p față de H (adică are posibil proprietatea p) dacă există c C astfel încât c⊆o și H(c, p) = +1. $\în$
(-)-condiție pentru p față de H (adică poate să nu aibă proprietatea p) dacă există c C astfel încât c⊆o și H(c, p) = −1. $\în$
(0)-condiție pentru p față de H (adică există argumente atât pro, cât și împotriva că o are proprietatea p) dacă există c C astfel încât c⊆o și H(c, p) = 0. $\în$

Prin + (H, o, p), - (H, o, p), 0 (H, o, p) notăm faptul că obiectul o pentru proprietatea p față de H satisface condiția (+), (-) -condiție și, respectiv, condiție 0. Să punem: F'(o, p) = F(o, p) dacă F(o, p) ≠ ; in caz contrar $\Pi$ $\Pi$ $\Pi$ $\tau$

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

Regulile de primul fel (procedura de inducție) și regulile de al doilea fel (procedura de analogie) sunt aplicate în mod consecvent până când cel puțin o nouă ipoteză este generată ca urmare a muncii lor, adică aplicarea regulilor de primul fel duce la o modificare a matricei de ipoteze despre cauzele posibile ale proprietăților obiectelor, iar aplicarea regulilor de al doilea fel este modificarea matricei de ipoteze despre posibila prezență sau absență a proprietății p în obiecte. În acest caz, numărul pasului este un indicator al plauzibilității raționamentului.

Verificarea condiției de completitudine cauzală

Următorul pas în activitatea metodei JSM este verificarea condiției de completitudine cauzală. Verificarea acestei condiții este interpretată ca raționament prin răpire - condiția este îndeplinită dacă ipotezele rezultate explică datele inițiale, adică dacă ipotezele despre cauzele posibile ale proprietăților obiectelor, obținute ca urmare a aplicării regulilor de primul fel, poate explica prezența sau absența proprietății p în obiectele pentru care inițial (înainte de aplicarea procedeelor de inducție și analogie) se știe că au sau nu proprietatea p.

Scopul verificării condiției este de a determina dacă ipotezele obținute ca urmare a metodei pot fi acceptate. Dacă nu este îndeplinită condiția completității cauzale, este necesar să se schimbe tehnica cognitivă aplicată (de exemplu, să se aleagă un mod diferit de codificare a structurii obiectelor) sau setul de intrare de obiecte (de regulă, setul este extins). ).

Exemplu

Să încercăm, folosind metoda JSM, să răspundem la următoarea întrebare: ce proprietăți ar trebui să aibă un patrulater convex cu simetrie netrivială pentru a putea descrie un cerc în jurul lui , sau invers, era imposibil să descriem un cerc.

Luați în considerare următorul set de obiecte de domeniu:

o 1 - pătrat ,
o 2 este un dreptunghi ,
o 3 - romb ,
o 4 - paralelogram ,
o 5 - trapez isoscel ,
o 6 - deltoid ,
o 7 - deltoid dreptunghiular.

Pentru aceste obiecte, alegem următorul set de fragmente structurale C:

c 1 este centrul de simetrie,
c 2 - este axa de simetrie ,
c 3 - există o axă de simetrie, care este o diagonală ,
c 4 - există o axă de simetrie care nu este o diagonală,
c 5 - exact o rotație de 180⁰ transformă figura în sine,
c 6 -ordinea grupului de simetrie este egal cu doi,
c 7 - există o pereche de unghiuri drepte opuse ,
c 8 - fără unghi drept,
c 9 - nicio axă de simetrie sau orice axă de simetrie nu este o diagonală.

setul de caracteristici țintă în acest caz constă dintr-o singură caracteristică:

p - puteți descrie cercul.

Să prezentăm datele inițiale sub forma unui tabel:

	p	c 1	c 2	c 3	c 4	de la 5	de la 6	de la 7	de la 8	de la 9
o 1 (pătrat)	+	+	+	+	+	-	-	+	-	-
o 2 (dreptunghi)	$\tau$	+	+	-	+	+	-	+	-	-
o 3 (diamant)	-	+	+	+	-	+	-	-	+	+
o 4 (paralelogram)	-	+	-	-	-	+	+	-	+	+
o 5 (trapez isoscel)	+	-	+	-	+	-	+	-	+	-
o 6 (deltoid)	-	-	+	+	-	-	+	-	+	+
o 7 (deltoid dreptunghiular)	+	-	+	+	-	-	+	+	-	+

Să reprezentăm fiecare dintre obiectele printr-un set de componente structurale pe care le are acest obiect:

o 1 (pătrat) {s 1 , s 2 , s 3 , s 4 , s 7 };
o 2 (dreptunghi) {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 (paralelogram) {s 1 , s 5 , s 6 , s 8 , s 9 };
o 5 (trapez isoscel) {s 2 , s 4 , s 6 , s 8 };
o 6 (deltoid) {s 2 , s 3 , s 6 , s 8 , s 9 };
o 7 (deltoid dreptunghiular) {s 2 , s 3 , s 6 , s 7 , s 9 }.

În cazul nostru, exemple pozitive pentru proprietatea țintă p sunt obiectele o 1 , o 5 și o 7 , exemplele negative sunt o 3 , o 4 și o 6 . Există, de asemenea, un ( )-exemplu - o 2 . $\tau$

Sarcina noastră este să folosim un raționament plauzibil pentru a afla dacă exemplele ( ) au proprietatea țintă p sau nu. $\tau$

Aplicarea regulilor de primul fel

Aici, ca posibile motive pentru prezența/absența proprietății p în obiecte, vom considera câteva submulțimi nevide ale mulțimii fragmentelor structurale C. Condiția (+) este îndeplinită de mulțimile:

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 }.

Condiția (-) este îndeplinită de mulțimile:

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 };

Acum este necesar să aflăm dacă mulțimile găsite sunt motive posibile pentru prezența sau absența proprietății țintă p în obiecte, adică să se determine funcția H pentru acest pas. După cum am menționat mai devreme, regulile de definire a acestei funcții pot avea o formă diferită în funcție de strategia aleasă - cu sau fără interdicție de contra-exemple.

Mulțimea C i C va fi extinsă ca $\subseteq$

un posibil motiv pentru prezența proprietății p dacă C i satisface condiția (+) pentru p , adică este încorporat ca submulțime în două sau mai multe (+)-exemple și nu este încorporat în niciunul (încorporat în nici un mai mult de unul) (- )-exemplu;
un posibil motiv pentru absența proprietății p , C i satisface condiția (-) pentru p , adică este încorporat ca submulțime în două sau mai multe (-)-exemple și nu este încorporat în niciunul (este încorporat în nu mai mult de unul) (+) -exemplu;
o ipoteză contradictorie dacă există atât un (+)-exemplu cât și un (-)-exemplu în care C i este încorporat .

Analizând datele noastre, obținem două motive posibile pentru prezența proprietății p :

C 1 = {с 2 , с 4 } și
C 2 \u003d {c 2 , c 3 , c 7 }.

Mulțimea fragmentelor C 4 = {с 2 , с 6 } devine o (+)-ipoteză sau o ipoteză contradictorie, în funcție de strategie.

Toate mulțimile care îndeplinesc condiția (-) pentru p sunt definite în continuare ca posibile motive pentru absența proprietății p .

Acesta este,

H (C1 , p) = +1 ,
H (C 2 , p) \u003d +1 ,
H (C5 , p) = −1 ,
H (C 6 , p) = −1 ,
H (C 7 , p) = −1 ,
H ( C8 , p) = −1 ,
H (C4 , p) = +1' sau H (C4 , p) = 0 în funcţie de strategia aleasă.

Aplicarea regulilor de al doilea fel

Folosim ipotezele (+)- și (-) obținute la pasul anterior pentru a determina -exemple. În cazul nostru, există un singur astfel de exemplu: o 2 {s 1 , s 2 , s 4 , s 5 , s 7 }. $\tau$

Include un posibil motiv pentru prezența proprietății p (C 1 = {с 2 , с 4 }) și nu include niciun motiv posibil pentru absența proprietății p , prin urmare, în strategia cu interzicerea contra- exemple, redefinim o 2 ca (+)- exemplu [3] .

Setului de exemple obținute la a n-a etapă se aplică din nou regulile primului și apoi celui de-al doilea fel. Acest proces continuă până când toate exemplele sunt definite. $\tau$

Testarea completității cauzale

Verificarea completității cauzale se realizează, așa cum am menționat mai devreme, cu ajutorul raționamentului abductiv. Condiția de completitudine cauzală este îndeplinită dacă cel puțin un motiv posibil pentru prezența proprietății țintă p este încorporat în fiecare (+)-exemplu sursă și cel puțin un posibil motiv pentru absența acesteia este încorporat în fiecare (-)-exemplu. .

În cazul nostru, fiecare exemplu inițial pozitiv și negativ este explicat.

Rezultat

Astfel, am obținut următoarele condiții suficiente plauzibile (și de fapt, valide) pentru ca un cerc să fie descris în jurul unui patrulater convex cu simetrie netrivială :

există o axă de simetrie care nu este o diagonală,
există o axă diagonală de simetrie și, în același timp, există o pereche de unghiuri drepte opuse.

Vezi și

Sistem informatic inteligent
Sistem expert
Sistem informatic automat
Sistem inteligent hibrid
Sisteme inteligente în științe umaniste (Institutul de Lingvistică al Universității Umanitare de Stat din Rusia) - departament care dezvoltă metoda JSM

Note

↑ În acest caz, pentru a determina mulțimile care îndeplinesc condițiile (+)-, (-) și (0)-, este necesar să se găsească toate intersecțiile posibile nevide ale fragmentelor pentru mulțimea de (+)- , (-)- și (0)- exemple. Găsirea tuturor intersecțiilor (similarității) unei mulțimi date este o problemă combinatorie separată, pentru care sunt cunoscuți un număr de algoritmi, dintre care cel mai eficient este algoritmul Norris .
↑ Funcția H poate fi definită diferit în funcție de strategie (cu sau fără interzicerea contraexemplelor).
↑ Într-o strategie mai prudentă, fără interzicerea contraexemplelor, observăm că, pe lângă aceasta, este încorporată o ipoteză contradictorie și, prin urmare, redefinim o 1 (se pare că ne referim la o 2 !) ca un (0)- exemplu.

Literatură

Generarea automată de ipoteze în sisteme inteligente. Comp. E. S. Pankratova, V. K. Finn. — M.: LIBROKOM, 2009. — 528 p.
JSM-metoda de generare automată a ipotezelor: fundamente logice și epistemologice. Comp. O. M. Anshakov, E. F. Fabrikantova. — M.: LIBROKOM, 2009. — 432 p.
Finn V.K. Despre posibilitatea formalizării raționamentului plauzibil prin intermediul logicii multivalorice.Vsesoyuzn. simp. asupra logicii și metodologiei științei. - Kiev: Naukova Dumka, 1976. - S. 82-83.
Finn V.K. Despre formalizarea orientată pe mașină a raționamentului plauzibil în stilul lui F. Bacon — D.S. Mill // Semiotică și informatică. - 1983. - Emisiune. 20. - S. 35-101.
Anshakov OM, Finn VK, Skvortsov DP Despre axiomatizarea logicii cu mai multe valori asociate cu formalizarea raționamentului plauzibil // Studia Logica. 1989 Vol. 48. Nr 4. P. 423-447.
Anshakov O. M., Skvortsov D. P., Finn V. K. Despre imitarea deductivă a unor variante ale metodei JSM pentru generarea automată a ipotezelor // Semiotică și informatică.— 1993.— Vol. 33.- S. 164-233.
Finn VK Despre caracteristicile metodei JSM ca mijloc de extragere a datelor // NTI. Ser. 2. - 2001. - Nr 5. - S. 1-4.
Vinogradov DV Asymmetric JSM-metoda luând în considerare contextul // A cincea Conferință Națională cu Participare Internațională.Inteligenta Artificială-96. - Kazan: 1996. - KII-96: Sat. științific tr.: În 3 volume - Kazan: Conf. univ. artele. inteligență, 1996.
Anshakov O. M., Skvortsov D. P., Finn V. K. Despre construcția logică a metodei JSM pentru generarea automată a ipotezelor // Dokl. Academia de Științe a URSS, Volumul 320, Nr. 6. - 1991. - S. 1331-1334.
Kuznetsov S. O. Predicate ale metodei JSM în limbajul de corespondență Galois // Informații științifice și tehnice (NTI), Ser. 2, 2006, nr. 12, p. 12-16.
Kuznetsov S. O. JSM-metoda ca sistem de învățare automată // Itogi nauki i tekhniki, Ser. Informatică, 1991, Vol. 15, S.17-54.