31.03.2016

1

Cap.2 - Aplicaţii ale IA:

Sisteme bazate pe reguliSistemele inteligente în economie

Conf.dr. D.Păvăloaia

MS SIA an 1

2015-2016

3/31/2016 1

Cuprins

1. Sisteme bazate pe reguli - SBR(RBS), Sisteme Expert, Motoare de reguli.

Concepte de bază (expert, raţionament, inferenţă, exemple de reguli, FC +

BC, etc) şi repere evolutive

2. Arhitectura SE şi MR. Asemănări, diferenţe şi exemple (de reguli)

3. Avantaje şi dezavantaje ale utilizării SBR

3/31/2016 2

31.03.2016

2

1.Sisteme bazate pe reguli• Cele mai numeroase SI

• Cele mai influente

• Cunoscute anterior ca SE

• Exemple:

• Limbaje de programare: LISP, CLIPS

• ES Shells: Exsys, Corvid

• RBS:

• For Java: Jess, Drools

• Others: OPS5

• Familia Web Rule languages

• In special RuleML si SWRL

• Interoperabilitatea regulilor

3/31/2016 3

SBR – definiţie, scop şi caracteristici

• Multitudine de definiţii

• Scop primordial (ca al SE) = emuleze comportamentul expertului uman prin

înmagazinarea expertizei acestuia

• Ce este un expert, ce este expertiza

• Ce este o regulă de producție

• Strategiile Forward chaining şi Backward chaining

3/31/2016 4

31.03.2016

3

Expertiza este o cunoaştere intensivă, specifică domeniului problemei, achiziţionată prin

instruire, citire sau experienţă îndelungată.

Următoarele tipuri de cunoaştere se includ în expertiză:

1) fapte despre domeniul problemei;

2) teorii din domeniul problemei;

3) reguli şi proceduri privind domeniul problemei;

4) reguli sau euristici despre ce trebuie făcut într-o situaţie problematică dată, pentru

soluţionarea problemei;

5) strategii globale despre soluţionarea tipurilor de probleme;

6) metacunoaştere.

Concepte de bază ale SE/SBR

3/31/2016 5

3/31/2016 6

Definitii Web pentru noţiunea de EXPERTIZĂ:

Specialized domain knowledge, skills, tricks, shortcuts and rule-of-thumb that

provide an ability to rapidly ad effectively solve problems in the problem

domain: www.expertise2go.com/webesie/tutorials/ESGloss.htm

A capability of a person to perform an operation in a limited domain with

exceptional results when compared to others capable of performing the same

operation. Expertise may depend on abstractions, such as individual mental

models, rather than on knowledge alone: amglossary.allenpress.com

Expertise is the property of a person (expert) or of a system which delivers a

desired result such as rapid, pertinent information:

en.wikipedia.org/Expertise

http://encyclopedia.laborlawtalk.com/Expertise

31.03.2016

4

Experţii - dificil de definit (persoane cu mai multe niveluri sau grade de expertiză).

Cât de multă expertiză -> a fi considerat expert? Expert = Kworker|Tworker??

Expertiza umană include o gamă largă de activităţi ale expertului şi anume:

1) recunoaşterea şi formularea problemei;

2) rezolvarea problemei cu exactitate şi rapiditate;

3) explicarea soluţiei;

4) învăţarea din experienţă;

5) restructurarea cunoaşterii;

6) fragmentarea regulilor;

7) determinarea relevanţei;

8) conştiinţa limitelor sale.

Concepte de bază ale SE/SBR. Experţii

3/31/2016 7

3/31/2016 8

Definitii pentru expert:

1) Persoana care dispune de cunoastere sau competenta intr-un domeniu

2) Persona recunoscuta pentru cunoasterea si judecatile sale, care îi confera

autoritate publica. Expertul dispune de o experienta indelungata, intensa,

practica sau educatie intr-un domeniu particular

4) Persoana recunoscuta de catre un grup profesional sau o societate

profesionala prin certificare

5) O persoana cu calificare sau cunoastere superioara intr-un domeniu particular

Sursa:definitii Web in engleza,

www.cogsci.princeton.edu/cgi-bin/webwn , en.wikipedia.org/wiki/Expert ,

www.normataylor.com/glosary.html

31.03.2016

5

• procesul de inferenţă

• trăsătură unică, majoră a SE

• abilitatea de a raţiona

• efectuată de motor de inferenţe.

Concepte de bază ale SE/SBR.

Inferenţierea

3/31/2016 9

3/31/2016 10

Definitii Web pentru Inferentiere:

1) A judgment based on reasoning rather than on direct or explicit statement. A

conclusion based on facts or circumstances.

www.tnellen.com/cyberenl/lit_terms/2terms.html

2) The process of drawing a conclusion from given evidence. To reach a decision by

reasoning www.dssresources.com/glossary1999.html

3) The process of reasoning whereby one statement (the conclusion) is derived from

one or more other statements (the premises)

www.filosofia.net/materiales/rec/glosaen.htm

4) New knowledge inferred from existing facts

www.expertise2go.com/tutorials/ESGloss.htm

5) A conclusion drawn from data

mdk12.org/mspp/vsc/mathematics/bygrade/glossary.shtml

31.03.2016

6

Exemple de SE/SBR

• Limbaje de programare: LISP, CLIPS

• ES Shells: Exsys, Corvid

• SBR:

• For Java: Jess, Drools

• Others: OPS5

• Familia Web Rule languages

• In special RuleML si SWRL

• Interoperabilitatea regulilor

3/31/2016 11

Limbaje de programare: LISP, CLIPS

• LISP = limbaj de programare funcțional cu un lung istoric

• Inițial = model de calcul -> a devenit limbajul cel mai folosit în app IA (1970-1980).

• Denumirea provine de la "LISt Processing".

• Specificat inițial în 1958, Lisp este cel de-al doilea ca vechime limbaj de programare de nivel înalt (Fortran - primul)

• Precum Fortran, Lisp a evoluat comparativ cu forma inițială, existând de-a lungul vremii o serie de dialecte

• Cele mai răspândite dialecte Lisp sunt Common Lisp și Scheme.

3/31/2016 12

31.03.2016

7

• CLIPS - C Language Integrated Production System

• Destinat dezvoltării SE, creat de NASA în anii 1980

• Sintaxa și numele au fost inspirate de OPS(Charles Forgy)

• CLIPS – cel mai utilizat pentru dezv SE (rapid, eficient, este gratuit și incorporează un LPOO denumit COOL)

• CLIPS este scris în C, foarte asemănător Lisp

• Descendenţii CLIPS: Jess, ECLiPSe, Haley Eclipse, FuzzyCLIPS

Limbaje de programare: LISP, CLIPS

3/31/2016 13

Exemplu de regulă:

în LISP în CLIPS

3/31/2016 14

31.03.2016

8

E.S. Shells: Exsys, Corvid

• ES Shells -> for nonprogrammers.

• Exsys(1983)-versiuni: Exsys(MSDos), Exsys 16, Exsys Developer, Corvid (2001) Web

• Instrument foarte longeviv(33ani), utilizat în multe domenii(economie, cercetare,

militar, industrial, turism, divertisment, aeronautic, domeniul public. Exemple:

http://www.exsys.com/demomain.html

• Folosit ca metodă de predare în universităţi şi licee

3/31/2016 15

Constructorul de reguli în Corvid(Logic block)

3/31/2016 16

31.03.2016

9

Blocul de comandă în Corvid (Command block)

1. Backward chaining 2. Forward chaining

3/31/2016 17

Jess

http://herzberg.ca.sandia.gov/jess/index.shtml

• Motor de reguli Java

• Developed by Ernest Friedman-Hill at Sandia National Laboratories in Livermore, CA

• Permite efectuarea de raționament folosind cunoașterea furnizată prin intermediul regulilor declarative

• Folosește algoritm Rete (pattern matching)

• Permite Backward chaining

• Free for academic purpose

SBR. Jess, Drools(Java); OPS5 (Others)

3/31/2016 18

31.03.2016

10

Drools

http://www.drools.org/

• platformă de integrare a logicii afacerii (BLiP) sau Motor de reguli(Rule engine)

• dezvoltat de JBoss şi Red Hat Inc.

• extinde şi implementează algoritmul Rete (optimizare Pattern matching).

• este o colecţie de instrumente ce permite separarea nivelului datelor de nivelul logic al proceselor afacerii.

• este format din 2 părţi principale: Authoring şi Runtime.

• Authoring: procesul de autorizare presupune crearea fişierelor care conţin reguli (fişiere .DRL).

• Runtime: Implică crearea memoriei de lucru şi specificarea activării acesteia.

3/31/2016 19

Drools. Termeni frecvent folosiţi

• Faptele (date asupra cărora acţionează regulile). În perspectiva Java, faptele sunt POJO (Plain Old Java Object).

• Sesiune (de cunoaştere) - knowledge Session este componenta principală care declanşează regulie. O sesiune de cunoaştere este creată din baza de cunoştinţe.

• Pentru ca motorul de reguli să poată lucra, faptele sunt inserate în sesiune. Atunci când se îndeplineşte o condiţie, regula care o conţine se declanşează.

• O sesiune este de 2 tipuri:

• Stateless Knowledge Session

• Stateful Knowledge Session

3/31/2016 20

31.03.2016

11

• Stateless Knowledge Session. Exemple:• Validare

• Eligibilitatea unei persoane pentru obţinerea unei ipoteci

• Calcul

• Calculul unei ipoteci.

• Direcţionare şi filtrare

• Filtrarea mesajelor primite şi gruparea lor în foldere.

• Trimiterea mesajelor primite către o destinaţie

• Stateful Knowledge Session. Exemple:• Monitorizare

• Monitorizarea bursei de valori şi analiză în vederea realizării unei achiziţii semi-automate.

• Diagnostic

• Depistarea fraudelor, diagnostic medical.

• Logistică

Drools. Termeni frecvent folosiţi

3/31/2016 21

• Funcţii în reguli

• Funcţiile reprezintă o alternativă a claselor, în unele situaţii. De exemplu,

function double calculateSquare (double value) {

return value * value;

}

• Salience este un aspect important în sintaxa regulilor(rezolvare a conflictelor ).

• Salience ->definirea ordinii în care vor fi executate regulile. Salience are un atribut, care preia orice expresie ce returnează un număr de tip int. Strategia de rezolvare a conflictelor va executa prima dată regula care are salience-ul cel mai mare.

salience ($account.balance * 5)

• Valoarea implicită a lui salience este 0.

Drools. Termeni frecvent folosiţi

3/31/2016 22

31.03.2016

12

Familia Web Rule languages: RuleML

• RuleML Initiative - August 2000 Pacific Rim International Conference on

Artificial Intelligence.

• RuleML Initiative dezvolta limbaje bazate pe reguli deschise XML/RDF

• Aceasta permite schimbul de reguli intre diferite sisteme, inclusiv componete

software distribuite pe Web si sisteme client-server eterogene

• Limbajul RuleML – sintaxa XML pentru reprezentarea cunostintelor sub forma

de reguli

• Integrarea cu ontologii: sistemul de reguli trebuie sa deriveze/utilizeze

cunostinte din ontologie

3/31/2016 24

RuleML• Reguli de inferenta/derivare

<imp> <_head> conc </_head>

<_body> <and> prem1 ... premN </and> </_body>

</imp >

implementate prin

<rule> <_body> <and> prem1 ... premN </and> </_body>

<_head> <assert> conc </assert> </_head>

</rule>

• Fapte

<atom> <_head> conc </_head> </atom>

implementate prin

<imp> <_head> conc </_head>

<_body> <and> </and> </_body> </imp> 3/31/2016 25

31.03.2016

13

Exemplu OPS5WME

(literalize student nume plasat_in sex_stud)

(literalize camera numar capacitate

libere sex_cam ocupanti)

(vector-attribute ocupanti)

camera 111 4 2 F (Maria Elena)time tag

(make camera ^numar 112 ^capacitate 4 ^libere 4

^sex_cam nil ^ocupanti nil)

(make student ^nume Mihai ^plasat_in nil ^sex-stud M)

26

3/31/2016 26

Cuprins

1. Sisteme bazate pe reguli - SBR(RBS), Sisteme Expert, Motoare de reguli.

Concepte de bază (expert, raţionament, inferenţă, exemple de reguli, FC +

BC, etc) şi repere evolutive

2. Arhitectura SE şi MR. Concept, istoric, asemănări, diferenţe şi componente

3. Avantaje şi dezavantaje ale utilizării SBR

3/31/2016 31

31.03.2016

14

2.Arhitectura SE şi MR. Concept, istoric, asemănări, diferenţe şi componente

SE - definiţii

• Numeroase. În esenţă, SE:

• Simulează comportamentul expertului uman în procesul de rezolvare a

problemelor complexe

• Utilizate în domenii restrânse, bine structurate unde cunoaşterea poate fi

formalizată

3/31/2016 32

Istoricul apariției SE

• Early AI (1956-late 1960s): așteptări prea mari , urmate de dezamăgiri și deziluzii. Eforturile timpurii au fost prea ambițioase, încercând să soluționeze probleme prea complexe.

• Early 1970s: constiezarea faptului că ar fi mai bine să se concentreze pe domenii specifice, cu probleme restrânse– primele reuşite pentru IA:

• DENDRAL (Buchanan et al, 1969) – un SE pentru analiza compoziţiei chimice (destinatepentru studierea compoziţiei solului de pe Marte)

• MYCIN (Feigenbaum et al, 1972) – sistem pentru diagnosticarea bolilor infecțioase ale sângelui. Utilizarea factorilor de certitudine pentru manipularea incertitudinii

• PROSPECTOR (Duda et al, 1979) – Analiza geologică a rocilor și a mineralelor. Folosirea metodelor Bayesiene (gestiunea incertitudinii)

3/31/2016 33

31.03.2016

15

Arhitectura unui SE

3/31/2016 34

Componentele SE: Interfaţa utilizator

3/31/2016 35

31.03.2016

16

Componentele SE: Baza de cunoştinţe

3/31/2016 36

Componentele SE: Editorul bazei de cunoştinţe

3/31/2016 37

31.03.2016

17

Componentele SE: Motorul de inferență

3/31/2016 38

Componentele SE: Motorul de inferență ->

interpretor și planificator

3/31/2016 39

31.03.2016

18

La nivelul planificatorului, selectarea regulii care se aplică la un moment dat foloseşte una din următoarele strategii :

• Selectarea regulii celei mai specializate (X =numărul maxim de condiţii –specializată vs. Y=caracter general)

• Selectarea regulii celei mai productive. (X=numărul maxim de consecinţe, “mai mult înseamnă mai bine „)

• Selectarea euristică. (regula care conduce baza de fapte cât mai aproape de starea dorită)

• Selectarea pe baza încrederii. (Principiul utilizării factorilor de certitudine – Confidencefactor)

Componentele SE: Motorul de inferență ->planificator

3/31/2016 40

Strategii de control a raţionamentului în

SE/SBR

• Forward Chaining - înlănţuire înainte

• Backward Chaining - înlănţuire înapoi

3/31/2016 41

31.03.2016

19

Strategii de control a raţionamentului în SE/SBR

Forward Chaining

3/31/2016 42

Strategii de control a raţionamentului în SE/SBR

Backward Chaining

3/31/2016 43

31.03.2016

20

Strategii de control a raţionamentului în SE/SBR

şi strategiile de căutare

• FC – data driven

• BC – goal driven

• Drools: FC, BC, Hybrid Chaining

• Strategii de căutare: în adâncime, de tip Backtracking, în lăţime,

bidirecţională, etc

3/31/2016 44

MEMORIEDE LUCRU

Fapte dinamice

BAZA DE CUNOSTINTE

Reguli Fapte

Date de activare

MOTOR DEINFERENTA

Selectie reguliReguli selectate

Actiuni(Concluzii)

Date

Reprezentare

Control

Intrari

(date de caz)

Iesiri

(Raspunsuri)si fapte

Arhitectura unui SBR/MR

3/31/2016 45

31.03.2016

21

Regula de producţie

• Metodă procedurală

• Este cea mai folosită metodă de dezvoltare a SE/SBR

• F.eficace -> reprezentarea recomandărilor, directivelor sau strategiilor

• Are două părţi care stabilesc o relaţie ce reprezintă scopul regulii:

• partea de IF (LHS) şi

• partea de THEN (RHS)

3/31/2016 46

DACĂ(IF)

condiţie1 •

condiţie2 •

....

ATUNCI(THEN)

concluzie1 •

concluzie2 •

....

ALTFEL(ELSE)

concluzie3 •

concluzie4 •

.....

Regula de producţie. Sintaxa generală

antecedente sau premise

acțiune sau consecință

• operator logic

3/31/2016 47

31.03.2016

22

R1: IF numărul de zile <5

THEN efectuaţi livrarea în 24 ore

R2: IF persoana are salariu

THEN persoana este salariat

R3: IF persoana este salariat

AND persoana are un venit diferit de salariu

THEN venitul trebuie declarat

R4: IF persoana nu are salariu

OR persoana nu are pensie

OR persoana nu are alt venit minim stabilit

THEN persoana este şomer

Regula de producţie. Exemple

3/31/2016 48

Quizz: formaţi regulile de producţie pentru

exemplul din tabel (Analiza lichidităţii)

3/31/2016 49

31.03.2016

23

Tipologia regulilor are în vedere marea varietate a formelor cunoaşterii de reprezentat astfel:

• Reguli de cauzalitate

• Reguli de recomandare

• Reguli directivă

• Reguli strategice

• Reguli euristice

• Reguli cu variabile

• Reguli cu factori de certitudine (0-1, -1 – 1, 0-10).

Regula de producţie. Tipologie

3/31/2016 50

Exemple de reguli cu factori de certitudine

R11: daca componenta-meniu = curcan

atunci culoare-vin = rosie 0.7

else culoare-vin = alba 0.2

R12: daca componenta-meniu = peste

atunci culoare-vin = alba

R13: daca sos-meniu = sos-alb

atunci culoare-vin = alba 0.6

R14: daca componenta-meniu = porc

atunci culoare-vin = rosie 0.9

51

R21: daca sos-meniu = sos-alb

atunci tip-vin = sec 0.8

else tip-vin = demisec 0.6

R22: daca sos-meniu = sos-tomat

atunci tip-vin = dulce 0.8

else tip-vin = demisec 0.5

R23: daca sos-meniu = necunoscut

atunci tip-vin = demisec 0.5

R24: daca componenta-meniu = curcan

atunci tip-vin = dulce 0.6

else tip-vin = demisec 0.4 3/31/2016 51

31.03.2016

24

Avantajele utilizării SBR

• Programarea declarativă – reguli de producție

• Separarea nivelului datelor de nivelul logic

• Viteză şi scalabilitate

• Centralizarea cunoaşterii

3/31/2016 52

Limitele SBR

• cunoaşterea (expertiza) nu este întotdeauna uşor disponibilă;

• experţii au cunoştinţe limitate legate de utilizarea tehnologiei;

• lipsa încrederii utilizatorilor finali este uneori o barieră în plus în calea folosirii SBR;

• mulţi experţi nu dispun de mijloace independente pentru controlul situaţiilor când

concluziile lor nu sunt rezonabile;

• vocabularul utilizat de către experţi este strict delimitat şi adesea dificil de înţeles de către

dezvoltatori;

• transferul expertizei este încă un subiect delicat, datorită bazei legale şi percepţiei multor

persoane. 3/31/2016 53

31.03.2016

25

Bibliografie

• Michael Negnevitsky, Artificial Intelligence: A Guide toIntelligent Systems, 3rd edition (2011), Addison Wesley

• Joseph C. Giarratano, Gary D. Riley, Expert Systems: Principles and Programming, 4 edition (2004), Course Technology

• Michael Bali, Drools Jbos Rules 5.x Developers Guide(2013), PACKT Publishing

• Andone, I., Robert J. Mockler, Dorothy G. Dologite, Alexandru Al. Tugui, Dezvoltarea sistemelor inteligente în economie: metodologie și studii de caz, Ed. Economica, Bucuresti 2001

3/31/2016 54

3/31/2016 55