Laboratorul 5 - Potrivirea Modelelor - PDF

Inteligență artificială Laboratorul 5 Potrivirea modelelor 1. Obiective Potrivirea modelelor este echivalentă cu utilizarea unor instrucțiuni condiționale mai avansate și mai flexibile. Reprezintă verificarea unei secvențe de sim...

Inteligență artificială Laboratorul 5 Potrivirea modelelor 1. Obiective Potrivirea modelelor este echivalentă cu utilizarea unor instrucțiuni condiționale mai avansate și mai flexibile. Reprezintă verificarea unei secvențe de simboluri pentru a determina dacă conține anumite elemente într-o anumită ordine, adică un model. În acest laborator, vom prezenta modalitatea de lucru cu un algoritm de potrivire a modelelor care poate aplica eficient reguli sau modele multiple pentru o mulțime de obiecte sau fapte dintr-o bază de cunoștințe. 2. Potrivirea modelelor cu switch – when Potrivirea modelelor (pattern matching) reprezintă verificarea unei secvențe de simboluri pentru a determina dacă conține anumite elemente într-o anumită ordine, adică un model. O potrivire poate reprezenta și deconstrucția secvenței în părțile sale constitutive, de exemplu identificarea primului element al unei liste și restul listei, elementele distincte ale unei tuple etc. La un nivel simplificat, potrivirea modelelor este asemănătoare unei instrucțiuni switch, însă este mai puternică. Începând cu versiunea 7, C# permite, pe lângă instrucțiunea switch clasică și testarea unor condiții suplimentare cu instrucțiunea when. Pentru a prezenta sintaxa unei astfel de expresii, să considerăm un exemplu simplu, în care se identifică un județ pe baza indicativului de pe plăcuța de înmatriculare: public static string Judet1(string cod) { switch (cod) { case "IS": return "Iasi"; case "SV": return "Suceava"; case "B": return "Bucuresti"; default: return "Alt judet"; } } public static string Judet2(string cod) { var d = new Dictionary { { "IS", "Iasi" }, { "SV", "Suceava" }, { "B", "Bucuresti" } }; 1 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html  switch (cod) { case string c when d.ContainsKey(c): // c ia valoarea lui cod return d[c]; case string c when c.Length != 2: return "Cod invalid"; default: return "Alt judet"; } } public static void Ex1() { WriteLine(Judet1("IS")); // Iasi WriteLine(Judet1("VS")); // Alt judet WriteLine(Judet1("Arad")); // Alt judet WriteLine(Judet2("IS")); // Iasi WriteLine(Judet2("VS")); // Alt judet WriteLine(Judet2("Arad")); // Cod invalid } 3. Potrivirea modelelor cu algoritmul Rete 3.1. Algoritmul Rete și limbajul CLIPS În cele ce urmează, vom prezenta niște scenarii de potrivire a modelelor mai puternice. Deoarece acestea nu sunt incluse în platforma.NET, vom folosi facilitățile din biblioteca FunCs. Aceste metode de potrivire a modelelor se bazează pe algoritmul Rete, implementat de CLIPS, un instrument pentru crearea sistemelor expert, dezvoltat de Software Technology Branch, NASA Lyndon B. Johnson Space Center, cu scopul facilitării realizării de programe care modelează cunoașterea și experiența umană. CLIPS este un acronim pentru C Language Integrated Production System. Rete este un algoritm de potrivire a modelelor pentru implementarea sistemelor bazate pe reguli. Algoritmul a fost dezvoltat pentru a aplica eficient multe reguli sau modele la multe obiecte sau fapte dintr-o bază de cunoștințe. Permite, de asemenea, găsirea unor soluții multiple pentru astfel de probleme. 3.2. Fapte și variabile Faptele cu care vom lucra sunt constituite din zero sau mai multe câmpuri separate de spații, de exemplu: "1 2 3", "abc efg", "a 1.4 15 -6 alte cuvinte". Elementele a căror valoare dorim să o determinăm prin potrivirea modelelor sunt echivalente variabilelor și se notează cu un semn de întrebare pus înaintea numelui, de exemplu: ?varsta, ?loc_nastere, ?specie. Aceste variabile lor lua valoarea unui singur câmp dintr-un fapt. 2 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html  Dacă dorim ca o variabilă să poată conține orice număr de câmpuri (zero, unu sau mai multe), numele acesteia trebuie precedat și de simbolul dolar, de exemplu: $?text. Uneori, dorim să identificăm unul sau mai multe câmpuri dintr-un fapt, dar nu ne interesează valorile lor specifice. În această situație se folosesc variabile libere, notate cu ? sau $? și fără un nume de variabilă. Să presupunem că avem un fapt care reprezintă numele unei persoane, compus din numele de familie, inițiala tatălui și unul sau mai multe prenume și că dorim să aflăm numele de familie. Faptele pot fi de tipul: "Ionescu T. George" sau "Popescu S. Andrei Sebastian". Potrivirea se face cu modelul "?nume $?", unde variabila nume va lua valorile Ionescu, respectiv Popescu. Dacă dorim să identificăm primul prenume al unei persoane, vom folosi modelul "? ? ?prenume $?", unde variabila prenume va lua valorile George, respectiv Andrei. Dacă se folosesc în același timp două variabile libere multi-câmp, rezultatele pot fi multiple. De exemplu, cu faptul "1 2 3" și modelul "$? ?x $?", variabila x va lua trei valori: 1, 2, respectiv 3, deoarece prima variabilă liberă poate înlocui zero sau mai multe câmpuri, iar a doua poate și ea înlocui zero sau mai multe câmpuri. În acest caz, numărul de soluții va fi egal cu numărul de câmpuri din fapt. 4. Potrivirea modelelor pe liste Operațiile pe care le-am prezentat mai sus pot fi aplicate pe colecții de tip IEnumerable în C#, cu ajutorul bibliotecii FunCs. Mai jos se prezintă câteva exemple de utilizare: private static void MatchList() { var list = "[ 1 2 3 4 5 6 7 8 9 10 ]".ToStringEnumF(); list.MatchF("?head ? $?rest ? ?last", out var head, out var rest, out var last); WriteLine($"{head} - {rest} - {last}"); // 1 - 3 4 5 6 7 8 - 10 list.MatchF("?x $? ?y", out Dictionary matches); WriteLine($"{matches["?x"]} {matches["?y"]}"); // 1 10 list.MatchF("?x ?y $?w ?z", out var x, out var y, out var w, out var z); WriteLine($"{x} - {y} - {w} - {z}"); // 1 - 2 - 3 4 5 6 7 8 9 - 10 } Un alt exemplu este determinarea combinărilor de n elemente luate câte k. Pentru soluții multiple, se instanțiază un obiect de tip ExpertMatchF, iar rezultatele multiple sunt disponibile într-o listă de dicționare, câte un dicționar pentru fiecare soluție. Valoarea fiecărei variabile dintr-un dicționar se poate regăsi folosind numele acesteia: public static void Combinations() { var em = new ExpertMatchF("1 2 3 4 5"); // "[" și "]" nu sunt necesare aici var patterns = new List { "$? ?x $? ?y $?" }; // combinări de 5 luate câte 2 em.Match(patterns, out var matchList); // out List matchList) foreach (var m in matchList) WriteLine($"{m["?x"]} - {m["?y"]}"); 3 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html  // 1 - 2 // 1 - 3 // 1 - 4 // 1 - 5 // 2 - 3 // 2 - 4 // 2 - 5 // 3 - 4 // 3 - 5 // 4 - 5 } Întrucât listele sunt unele dintre cele mai folosite structuri de date în programarea funcțională, potrivirea modelor pentru liste este de asemenea foarte des întâlnită, mai ales în contextul funcțiilor recursive. De obicei, se identifică primul element din listă (head) și lista de elemente următoare (tail). În FunCs, această facilitate este implementată pentru tipul IEnumerable generic. Celelalte tipuri de potrivire de modele se pot utiliza doar pentru colecții de tip string. Exemplul următor prezintă o funcție care calculează recursiv suma elementelor dintr-o listă: private static int MySum(IEnumerable list) { if (list.Count() == 0) return 0; list.MatchHeadTailF(out int head, out var tail); return head + MySum(tail); } public static void MySumTest() { var list = "[ 1 2 3 4 5 ]".ToIntEnumF(); int sum = MySum(list); // 15 } Exemplul următor prezintă o funcție care aplică altă funcție f, primită ca parametru, asupra tuturor elementelor dintr-o listă. Funcția aceasta este echivalentă de fapt cu funcția Map: private static IEnumerable MyMap(this IEnumerable list, Func f) { if (list.Count() == 0) return "[]".ToIntEnumF(); // o listă goală, fără elemente list.MatchHeadTailF(out int head, out var tail); return tail.MyMap(f).Prepend(f(head)); } public static void MyMapTest() { var list = "[ 3 6 2 ]".ToIntEnumF(); var list2 = list.MyMap(n => n * n); // [ 9 36 4 ] var list3 = list.MyMap(n => -n); // [ -3 -6 -2 ] } 4 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html  4. Potrivirea modelelor generală 4.1. Utilizarea multiplă a unei variabile O proprietate foarte utilă si importantă pe care o au variabilele este aceea că pot fi folosite în mai multe modele, însă o variabilă are o singură valoare, indiferent în câte modele apare. Fie următorul exemplu, în care avem o bază de fapte cu relațiile de rudenie între mai multe persoane: (father Christopher Arthur) // Christopher este tatăl lui Arthur (father Christopher Victoria)... (mother Penelope Arthur) (mother Penelope Victoria)... Să determinăm ce persoane sunt părinții aceluiași copil. Se observă că variabilele corespund exact locului din listă unde se află un anumit nume. De exemplu, pentru perechea de fapte: (father Marco Sophia) (mother Lucia Sophia) folosind variabilele ?f pentru tată (father), ?m pentru mamă (mother) și ?c pentru copil (child), ?f va fi Marco, ?m va fi Lucia și ?c va fi Sophia. Legarea celor două fapte se face prin utilizarea aceleiași variabile ?c, care trebuie să ia același nume, în acest caz Sophia. În același mod, regula descoperă și celelalte perechi de fapte father și mother, care au același copil. public static void Parents() { // încărcarea faptelor din fișier var sr = new StreamReader("kinship.csv"); var lines = sr.ReadToEnd().Split("\r\n".ToCharArray(), StringSplitOptions.RemoveEmptyEntries); sr.Close(); var em = new ExpertMatchF(lines.ToList()); // găsirea mamei unui anumit copil în fapte de tip: // mother Penelope Arthur string child = "Arthur"; em.MatchVar($"mother ?m {child}", out var mother); WriteLine(mother); // Penelope // găsirea părinților aceluiași copil var patterns = new List { "father ?f ?c", "mother ?m ?c" }; 5 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html  em.Match(patterns, out var matches); foreach (var m in matches) WriteLine($"Father {m["?f"]}, mother {m["?m"]}, child {m["?c"]}"); // Father Marco, mother Lucia, child Sophia // Father Marco, mother Lucia, child Alfonso // Father Pierro, mother Francesca, child Angela // Father Pierro, mother Francesca, child Marco // Father Roberto, mother Maria, child Lucia // Father Roberto, mother Maria, child Emilio // Father James, mother Victoria, child Charlotte // Father James, mother Victoria, child Colin // Father Andrew, mother Christine, child Jennifer // Father Andrew, mother Christine, child James // Father Christopher, mother Penelope, child Victoria // Father Christopher, mother Penelope, child Arthur } 4.2. Constrângeri Limbajul CLIPS, al cărui motor de inferență este încapsulat în biblioteca FunCS, permite și specificarea unor constrângeri asupra valorilor variabilelor din modele. Constrângerile sunt implementate ca funcții predicative în format prefix, operatorul fiind plasat în fața operanzilor. Dintre aceste funcții, menționăm: and, or, not, eq (egal), neq (diferit) pentru valori generale și = (egal), (diferit), = pentru valori numerice. Pentru exemplul anterior, să determinăm acum ce persoane sunt bunic și nepot: public static void GrandParents() { // încărcarea faptelor din fișier... var em = new ExpertMatchF(lines.ToList()); var patterns = new List { "father ?g ?p", "?r ?p ?c" // ?r este o relație asupra căreia se va aplica o constrângere: să fie de tip father sau mother }; var constraint = "(or (eq ?r father) (eq ?r mother))"; em.Match(patterns, constraint, out var matches); foreach (var m in matches) WriteLine($"Grandfather {m["?g"]}, {m["?r"]} {m["?p"]}, child {m["?c"]}"); // Grandfather Roberto, mother Lucia, child Sophia // Grandfather Roberto, mother Lucia, child Alfonso // Grandfather Christopher, mother Victoria, child Charlotte // Grandfather Christopher, mother Victoria, child Colin // Grandfather Pierro, father Marco, child Sophia // Grandfather Pierro, father Marco, child Alfonso // Grandfather Andrew, father James, child Charlotte // Grandfather Andrew, father James, child Colin } 6 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html  Tot un mecanism de constrângeri poate fi folosit împreună cu soluțiile multiple pentru a determina permutările elementelor unei liste: public static void Permutations() { var facts = new List { "1", "2", "3" }; var em = new ExpertMatchF(facts); var patterns = new List { "?o1", "?o2", "?o3" }; var constraint = "(and (neq ?o1 ?o2) (neq ?o1 ?o3) (neq ?o2 ?o3))"; em.Match(patterns, constraint, out var matches); foreach (var m in matches) WriteLine($"{m["?o1"]} - {m["?o2"]} - {m["?o3"]}"); // 3 - 2 - 1 // 3 - 1 - 2 // 1 - 3 - 2 // 2 - 3 - 1 // 1 - 2 - 3 // 2 - 1 - 3 } Un alt exemplu în care avem soluții multiple și constrângeri este problema damelor, care constă în așezarea pe tabla de șah a unui număr de dame, fără ca acestea să intre în conflict. Nu vom putea avea deci două dame pe aceeași linie, coloană sau diagonală. Constrângerile generale sunt: linie1  linie 2  coloana1  coloana 2  linie  linie  coloana  coloana  1 2 1 2 Constrângerile pot include și funcții matematice elementare. Aici, pentru determinarea valorii absolute vom utiliza funcția abs. De exemplu, în CLIPS, (abs (- 3 7)) returnează 4. public static void MatchQueens4() { var em = new ExpertMatchF("n 1 2 3 4"); var patterns = new List { "n $? ?row $?", "n $? ?col $?" }; var queens = new List(); em.Match(patterns, out var matchList); foreach (var m in matchList) queens.Add($"queen {m["?row"]} {m["?col"]}"); em = new ExpertMatchF(queens); patterns = new List { "queen 1 ?c1", 7 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html  "queen 2 ?c2", "queen 3 ?c3", "queen 4 ?c4" }; var constraints = "(and " + "(neq (abs (- ?c1 ?c2)) 1)" + "(neq (abs (- ?c1 ?c3)) 2)" + "(neq (abs (- ?c1 ?c4)) 3)" + "(neq (abs (- ?c2 ?c3)) 1)" + "(neq (abs (- ?c2 ?c4)) 2)" + "(neq (abs (- ?c3 ?c4)) 1)" + "(neq ?c1 ?c2)" + "(neq ?c1 ?c3)" + "(neq ?c1 ?c4)" + "(neq ?c2 ?c3)" + "(neq ?c2 ?c4)" + "(neq ?c3 ?c4)" + ")"; em.Match(patterns, constraints, out matchList); foreach (var m in matchList) WriteLine($"{m["?c1"]} {m["?c2"]} {m["?c3"]} {m["?c4"]}"); // 2 4 1 3 // 3 1 4 2 } După cum se poate vedea urmărind rezultatele programului de mai sus, presupunând că prima damă se află pe linia 1, a doua pe linia 2 ș.a.m.d., există două soluții: Dama 1: linia 1 coloana 2 Dama 2: linia 2 coloana 4 Dama 3: linia 3 coloana 1 Dama 4: linia 4 coloana 3 Dama 1: linia 1 coloana 3 Dama 2: linia 2 coloana 1 Dama 3: linia 3 coloana 4 Dama 4: linia 4 coloana 2 5. Sisteme expert Sistemele expert sunt programe concepute pentru a raționa în scopul rezolvării problemelor pentru care în mod obișnuit se cere o expertiză umană considerabilă. Un sistem expert încorporează o bază de cunoștințe sau fapte și un motor de inferență utilizat pentru soluționarea problemelor. Cunoașterea într-un sistem expert este organizată într-o manieră care separă cunoștințele despre domeniul problemei de alte tipuri de cunoștințe, precum cele despre algoritmii de căutare pentru rezolvarea problemelor specifice și cele despre interacțiunea cu utilizatorul. Sistemele expert înmagazinează cunoștințe specializate, introduse de experți. De cele mai multe ori, baza de cunoștințe este foarte mare, de aceea este foarte importantă modalitatea de 8 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html  reprezentare a cunoașterii. Baza de cunoștințe a sistemului trebuie separată de program, care la rândul său trebuie să fie cât mai stabil. În cele ce urmează, vom prezenta un exemplu de sistem expert bazat pe arbori de decizie, care realizează clasificarea mișcărilor unui punct material. Sunt luate în considerare doar cele mai importante caracteristici ale mișcării: vectorul viteză și vectorul accelerație. În funcție de valorile acestora se realizează o clasificare primară a mișcării. Deși arborele de decizie reprezentat mai jos nu este foarte mare, odată cu introducerea altor parametri, dimensiunile acestuia pot crește foarte mult. 6. Aplicații 6.1. Realizați un program care afișează numerele de la 1 la 20. Pentru multiplii de 3, afișați Fizz în loc de număr, pentru multiplii de 5, afișați Buzz, iar pentru multiplii atât de 3 cât și de 5, afișați FizzBuzz. Folosiți metoda bazată pe instrucțiuni switch cu when. Exemplu: 1 Fizz 11 16 2 7 Fizz 17 Fizz 8 13 Fizz 4 Fizz 14 19 Buzz Buzz FizzBuzz Buzz 9 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html  6.2. Fie următorul arbore genealogic. Să se afișeze verii unei anumite persoane date. Liviu Vlad Maria Nelu Oana Mircea Dan Paul Radu Sorin Indicații: Urmărind arborele, putem vedea că verii lui x au același bunic ca și x, dar părinți diferiți. Se dă următoarea funcție, care trebuie completată: public static void Problem2() { var facts = new List { "parent Liviu children Vlad Maria Nelu", "parent Vlad children [de completat]", [de completat] }; var em = new ExpertMatchF(facts); string searchFor = "Sorin"; // se caută verii lui Sorin var patterns = new List { [de completat] }; string constraint = [de completat]; Write($"Verii lui {searchFor} sunt: "); em.Match(patterns, constraint, out var matches); foreach (var m in matches) Write($"{m["?c"]} "); WriteLine(); } Exemplu: Verii lui Sorin sunt: Oana Mircea Dan 6.3. Realizați un sistem expert bazat pe un arbore de decizie generic, reprezentând raționamentul pentru rezolvarea unei anumite probleme. Problema va fi rezolvată interactiv, prin întrebări adresate utilizatorului. Se pleacă din rădăcina arborelui și apoi, în funcție de răspunsurile date, se coboară în arbore până se atinge o frunză, corespunzătoare unei concluzii (soluții). 10 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html  Pentru fiecare nod neterminal, se definesc următoarele caracteristici:  O întrebare de al cărei răspuns depinde alegerea următorului nod;  O listă de răspunsuri acceptabile;  O mulțime de reguli care determină nodul următor, în funcție de un anumit răspuns. În acest scop, se utilizează fapte de tipul: regulă întrebare răspunsuri concluzie Se dă următoarea bază de cunoștințe, inclusă în fișierul viteza.kbf, care definește un arbore de decizie pentru a determina tipul de mișcare al unui punct material: Fișierul viteza.kbf root n11 question n11 Viteza isi pastreaza directia? answers n11 da nu nu_stiu rule when n11 if nu then n21 rule when n11 if da then n22 rule when n11 if nu_stiu then n23 conclusion n23 Informatii insuficiente. question n21 Modulul vectorului viteza este constant? answers n21 da nu rule when n21 if nu then n31 rule when n21 if da then n32 conclusion n31 Miscare curbilinie neuniforma. conclusion n32 Miscare curbilinie uniforma. question n22 Vectorul acceleratie este nul? answers n22 da nu rule when n22 if nu then n33 rule when n22 if da then n34 conclusion n34 Miscare rectilinie uniforma. question n33 Acceleratie constanta? answers n33 da nu rule when n33 if nu then n41 rule when n33 if da then n42 conclusion n41 Miscare rectilinie neuniforma. question n42 Acceleratie pozitiva? answers n42 da nu rule when n42 if nu then n51 rule when n42 if da then n52 conclusion n51 Miscare rectilinie uniform incetinita. conclusion n52 Miscare rectilinie uniform accelerata. 11 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html  De exemplu, pentru nodul rădăcină (notat n11) vom avea următoarele fapte: question n11 Viteza isi pastreaza directia? answers n11 da nu nu_stiu rule when n11 if nu then n21 // răspuns = if, nod următor = then rule when n11 if da then n22 rule when n11 if nu_stiu then n23 Trebuie subliniat faptul că programul este independent de arborele de decizie pe care lucrează. Același program poate fi aplicat pentru alte probleme fără modificări suplimentare. Exemplu: Viteza isi pastreaza directia? (da/nu/nu_stiu): da Vectorul acceleratie este nul? (da/nu): nu Acceleratie constanta? (da/nu): da Acceleratie pozitiva? (da/nu): nu Miscare rectilinie uniform incetinita. Indicații: Se dau următoarele funcții, care trebuie completate: public static void Problem3 () { var facts = ReadFromFile("viteza.kbf"); var em = new ExpertMatchF(facts); // root n11 em.MatchVar("root ?r", out string currentNode); while (true) // până când se ajunge la o concluzie { // conclusion n51 Miscare rectilinie uniform incetinita. em.MatchVar($"conclusion {currentNode} $?c", out string conclusion); if (conclusion != "") { WriteLine(conclusion); break; } // se găsește întrebarea din nodul curent // se găsesc răspunsurile permise din nodul curent // se afișează întrebarea, se citește și se validează răspunsul utilizatorului // se găsește regula corespunzătoare răspunsului dat și se trece la următorul nod în arbore, // adică se actualizează variabila currentNode } } private static List ReadFromFile(string fileName) { var sr = new StreamReader(fileName); var lines = sr.ReadToEnd().Split("\r\n".ToCharArray(), StringSplitOptions.RemoveEmptyEntries); sr.Close(); return lines.ToList(); } 12 Florin Leon, Inteligenta artificiala - Laborator, http://florinleon.byethost24.com/lab_ia.html