Post on 12-Jan-2016
description
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
Sistemas de Soporte a la Decisión
GIRONA
2002
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
Sistemes Experts
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Sistemes Experts
Definició:
Són Sistemes Basats en el Coneixement que resolen
problemes molt especialitzats i complexes, pels que es
confia habitualment en experts humans, per a la seva
resolució, en un domini concret
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Per què van sorgir els SE?
Necessitats econòmiques
Disposar d’experts altament qualificats és car i no sempre possible
Eines econòmiques d’aprenentatge per a altres experts/no experts
Preservació del coneixement dels experts
Necessitats d’eficiència computacional Els mètodes generals de resolució de problemes són força
ineficients (mètodes febles)
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Coneixement expert
DADES + ALGORISME = PROGRAMA
CONEIXEMENT + INFERÈNCIA = SE
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Classificació dels SE segons les tasques [Hayes-Roth et al., 1983] (1)
Sistemes d’InterpretacióInterpretació Inferir descripcions de situacions, a partir d’observacions
/ dades
Sistemes de PrediccióPredicció Inferir conseqüències versemblants a partir de situacions
o successos
Sistemes de DiagnòsticDiagnòstic Inferir les falles del sistema a partir de símptomes
Sistemes de DissenyDisseny Desenvolupar configuracions d’objectes que satisfan
certes restriccions
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Classificació dels SE segons les tasques [Hayes-Roth et al., 1983] (2)
Sistemes de PlanificacióPlanificació Generar seqüències d’accions per a conseguir certs
objectius
Sistemes de MonitoritzacióMonitorització Estudiar el comportament d’un sistema al llarg del temps
Sistemes de Correció /ReparacióCorreció /Reparació Generar solucions per a les falles d’un sistema
Sistemes de ControlControl Estudiar i governar el comportament d’un sistema
dinàmic
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Fases de l’enginyeria del coneixement (1)
PROVA
IDENTIFICACIÓ
CONCEPTUALITZACIÓ
FORMALITZACIÓ
IMPLEMENTACIÓ
REQUERIMENTS
CONCEPTES
ESTRUCTURA
REGLES
REFORMULACIÓ
REDISSENY
REFINAMENT
[Buchanan et al., 1983]
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
IDENTIFICACIÓ
Viabilitat de la construcció del SE
Cercar les fonts de coneixement (experts, llibres, etc.)
Determinar les dades necessàries per a resoldre el problema
Determinar els objectius (solucions) i els criteris que determinen la solució
Fases de l’enginyeria del coneixement (2)
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Fases de l’enginyeria del coneixement (3)
CONCEPTUALITZACIÓ
Detallar els elements bàsics per a caracteritzar el domini (fets rellevants) i les seves relacions.
Distingir les evidències, les hipòtesis i les accions a realitzar
Detallar les diferents hipòtesis/objectius
Descomposar el problema en subproblemes
Caracteritzar els blocs de raonament i el flux de raonament
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Fases de l’enginyeria del coneixement (4)
FORMALITZACIÓ
Determinar els esquemes de raonament necessaris:
• Classificació / diagnosi / planificació temporal / estructures causals / disseny espaial / configuració
Identificar l’espai de cerca i el tipus de cerca
Identificar la metodologia de la resolució:
• classificació heurística / resolució constructiva / hipòtesi i prova jeràrquica
Analitzar la inexactitud (incertesa, imprecisió o incompletitud) i la completesa
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Fases de l’enginyeria del coneixement (5)
IMPLEMENTACIÓ Representació i implementació del coneixement
• Definició de la base de fets• Estructura modular de la base de coneixements• Definició de les regles d’inferència dels mòduls
Decisions sobre el control de la resolució (metaconeixement)
• Definició de les meta-regles associades als mòduls
PROVA Determinar amb el/s expert/s un conjunt de casos de prova
Avaluar el funcionament del sistema (prototipus)• Correctesa? / Completesa? / Inexactitud? / Credibilitat i
explicacions?
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Arquitectura d’unSistema Expert
U S E R
U S E R I N T E R F A C E
K N O W L E D G E A C Q U I S I T I O N
K N O W L E D G E E N G I N E E R I N T E R F A C E
K N O W L E D G E E N G I N E E R E X P E R T S
D A T A B A S E
K N O W L E D G E B A S E
I N F E R E N C E E N G I N E S / R E A S O N I N G
M E T A - R E A S O N I N G S T R A T E G I E S
E X P L A N A T I O N M O D U L E
S E N S O R S / A C T U A T O R S I N T E R F A C E
S E N S O R S /
A C T U A T O R S E X E C U T I O N C O N T R O L U N I T
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Base de Coneixements (1)
Coneixement del domini + coneixement heurístic
Tipus de coneixement:
Coneixement Factual
Coneixement Condicional
Coneixement Relacional
Objectes i característiques
Condicions i deduccions
Relacions temporals, causalsi conceptuals
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Base de Coneixements (2)
Sistemes de regles d’inferència/Sistemes de Producció: Els més habituals i els primers
Representacions estructurades
Representacions mixtes: Regles + Representacions estructurades
Per a descriure el domini
Xarxes semàntiques/Frames
Per a modelitzar objectes i relacions
Abans-de
Tipus de
Part_de
Mètodes de Representació del Coneixement
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Base de Coneixements (3)
Organització del coneixement sobre el domini i sobre el procés de resolució
Regles d’inferència
SI <Condicions> LLAVORS <Accions>
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Base de coneixements (4)
Cadascuna de les regles pot incorporar:
<Indentificador-regla>
<Condicions o premisses>• Proposicions• Predicats d’ordre 1
<Certesa de la regla>
<Accions o conclusions>• Noves deduccions• Accions• Càlculs
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Base de coneixements (5)
Exemples
(RDECP03 (R08007 Concentració-fanf-decp-alta No Neutropènia No Purga-fang-decp Associades-dermatologia ectima-gangrenosum 0.8 molt-possible Netejar-canonada Pseudomones . . . ) . . . )
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Motors d’inferències
Motor d’inferències Mòdul de raonament
Motor d’inferències
Intèrpret de regles + Estratègia de control
Deduir nous fets, executar accions per aresoldre el problema plantejat, a partir d’unconjunt inicial de fets i d’un cert coneixement,amb la interacció de l’usuari.
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Cicle general d’un motor d’inferències
DeteccióDetecció: Obtenció del conjunt de regles aplicables
Formació del conjunt de conflictes
SeleccióSelecció: Selecció de la regla a aplicar
Resolució de conflictes
AplicacióAplicació: Aplicació de la regla seleccionada
Inferència
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Cicle general: Detecció
Construcció del conjunt de regles candidates a ser aplicades
Les regles seran candidates o no depenent de l’estratègia de control
L’intèrpret de regles fa els càlculs i les instanciacions necessàries que siguin possibles en cada estat de resolució del problema.
Una regla es pot utilizar amb vàries instanciacions (CP1)
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Cicle general: Selecció
Selecció de la millor regla d’entre les obtingudes en el pas anterior
La selecció dependrà de l’estratègia de resolució de conflictes emprada pel motor d’inferències.
Criteris més utilizats (sovint es combinen varis criteris) :• La més/menys utilitzada
• La més específica/més general
• La més informativa dóna un major número de fets desconeguts
• La regla amb un grau de certesa més alt
• La primera regla en ordre
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Cicle general: Aplicació
L’intèrpret de regles executa la regla seleccionada
modificant l’estat de la base de fets amb noves
deduccions, càlculs, accions i/o nous subojectius
Propagació de les instanciacions (en CP1)
Si s’escau, propagació de la certesa de les premisses
cap a les conclusions, mijançant les diferents
connectives lògiques
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Fi del cicle
El cicle acaba quan ja no hi ha cap més regla aplicable, o bé quan es troba la conclusió desitjada
Depenent del problema i de l’estratègia de control pot ser que la cadena de raonament quedi tallada
Cal reconsiderar passos anteriors
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Motors d’Inferència: estratègies (I)
Motors Deductius/Encadenament progressiu
Encadenament cap endavant forward chaining
Estratègia dirigida per les dades data driven
Evidències, símptomes, dades conclusions i/o hipòtesis
A B C H
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Motors d’Inferència: estratègies (II)
Motors Inductius/Encadenament regressiu
Encadenament cap enrera backward chaining
Estratègia dirigida pels objectius goal driven
Conclusions i/o hipòtesis Evidències, símptomes, dades
A B C H
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap endavant
Basat en el modus ponens:
A, AB |- B
És un mètode deductiu segons la lògica clàsica
Resolució del problema: Cerca des de l’estat inicial fins el
final (l’objectiu), passant pels estats intermitjos que marquen
les cadenes d’inferència que es deriven de l’aplicació de les
regles
Partir de les evidències/simptomes/dades i deduir tot el es
pugi
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap endavant. Funcionament
La base de fets s’inicialitza amb el conjunt de fets coneguts
Obtenir les conseqüències derivables del conjunt de fets:
Seleccionar les regles aplicables. Les que tenen els antecedents coneguts (ie són a la base de fets) o bé són preguntables.
Afegir les noves conclusions/valors a la base de fets
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap endavant. Pro’s i contres
Problemes No focalitza en l’objectiu: La estratègia de resolució
de conflictes es crítica Explosió combinatoria: Degut a les possibles
instanciacions dels predicats de les premisses (CP1)
Avantatges Facilita la formalització del coneixement
El modus ponens és força intuitiu
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap endavant. Exemple
Base de conèixements Base de fets Objectiu
R1: A B C D A G??R2: A E F G ER3: B C D H BR4: E CR5: A H FR6: A C H
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap endavant. Exemple
1: A, E, B2: A, E, B, C(R4)
A,E,B,C,D A,E,B,C,H
R1 R6
3:
R3 R6
A,E,B,C,D,H A,E,B,C,D,H
R5 R6
A,E,B,C,D,H,F A,E,B,C,D,H
A,E,B,C,D,H,F,G! A,E,B,C,D,H,F ....
R1 R5
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap enrera
Es un mètode inductiumètode inductiu: trenca el sentit de la deducció:
• B, AB ¬ |- A
Està guiat per un objectiu: Hipòtesi que es vol validar. Reconstruir la cadena de raonament en ordre invers
Cada pas implica nous subobjectius o subhipòtesis que s’han de validar
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap enrera. Funcionament
Inicialitzar la base de fets amb un conjunt inicial de fets
Inicialitzar el conjunt d’hipòtesis o objectius a verificar
Mentre hi hagi hipòtesis per a validar fer Validar una hipòtesi de la llista
Fmentre
Validar l’hipòtesi consisteix en: si ja ho està treure-la de la llista
• Comprovar si ja està verificada en la BF sino usar la BC i la BF per a validarla
Seleccionar una regla
Afegir les premisses de la regla com nous subojectius a validar en lloc de la hipòtesi
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap enrera. Avantatges
La resolució del problema està millor dirigida. Només es considera el necessari per a la resolució del problema
El procés de resolució consisteix en l’exploració d’un graf i/o
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap enrera. Exemple (I)
Base de conèixements Base de fets Objectiu
R1: A B C A H??R2: C D BR3: E F G R4: A ER5: D GR6: A G H
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap enrera. Exemple (II)
H
R6 A
GH
R6 A
G
E
F
DR5
R3 H
R6 A
G
E
F
DR5
R3
R4A
H A G
G E F
G A F
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap enrera. Exemple (III)
H
R6A
G
E
F
DR5
R3
R4A
Suposem que F és preguntable
NO
G A F = NO
S´ha de tornar enrera i reconsideraraltres opcions
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap enrera. Exemple (IV)
H
A
G D
R6
R5
G H
H
A
G D
R6
R5C
D C
R2
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Encadenament cap enrera. Exemple (V)
H
A
G D
R6
R5C
C A B
R2A
B
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Avantatges dels SE
Adequats en dominis poc estructurats
Eficaços en tasques de diagnosi i classificació
Capacitat d’autoexplicació
Facilitat de comunicació amb l’usuari
Permet extensions fàcilment (raonament aproximat)
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Inconvenients dels SE
Fragilitat
Dificultat amb el control del raonament
Baixa reusabilitat de les B.C.
Són incapaços d’aprendre
Problemàtica de l’adquisició del coneixement
Problemàtica de la validació
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Història dels SE (1)
Els més antics 1965
DENDRAL (1965-1970) Interpretació d’espectografia de masses i ressonàncies
magnètiques de molècules orgàniques
META-DENDRAL (1970) Construcció de regles heurístiques a partir de dades
MACSYMA Manipulació de fórmules algebraiques
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Història dels SE (2)
MYCIN (1972-1976) Diagnosi d’enfermetats infeccioses a la sang 400 regles Raonament amb incertesa
EMYCIN (1980) Exporta el sistema de control de MYCIN Primer entorn de SE (shell)
HEARSAY-II (1975) Interpretació del LN (hear + say) 1000 paraules
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Història dels SE (3)
PROSPECTOR (1977) Prospeccions mineres Un altre mètode de raonament amb incertesa
R1/XCON (1980) Configuració d’entorns computacionals DEC, 200.000 regles
INTERNIST (1982) Diagnosi en medicina interna 500.000 - 1.000.000 regles
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
CENTAUR (1983) Diagnosi d’infeccions pulmonars Regles i prototipus
MOLE (1986) Shell de SE per a classificació
TEST (1987) Troubleshooting Expert System Tool Diagnosi / classificació
VT (1988) Vertical Transportation Disseny de sistemes elevadors
Història dels SE (4)
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Metaconeixement / Metaraonament
MetaconeixementMetaconeixement coneixement sobre el (propi) coneixement
Control sobre com i quan aplicar el coneixement
Metaconeixement implícit• Estratègia de resolució de conflictes (criteris)• En els primers Sistemes Experts : Premisses artificials
per a controlar l’aplicabilitat de les regles (ie repeat o !)
Metaconeixement explícit• Introdució de les meta-regles (Davis, 1980) : Regles
que actuen sobre les regles• Separació entre control i coneixements• Mecanisme de raonament unificat: Motor d’inferències
utilizat per les regles i les meta-regles• Concepte d’estratègia: Ordenació del elements
necessaris per a la resolució
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Meta-regles
Meta-reglaMeta-regla: unitat de control sobre el coneixement
Tipus de meta-regles. Meta-regles sobre regles
• Inhibir / desinhibir regles
Meta-regles sobre mòduls• Tipus de cerca en els mòduls (endavant, enrera)• Nivell de tall en la certesa mínima de les regles• Subsumpció de regles
Meta-regles sobre estratègies• Estratègia: conjunt ordenat de mòduls a ser tractats• Excepcions
Meta-regles sobre plans d’actuació• Quina estratègia s’aplica primer quan n’hi ha més d’una
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
(MR-DECP01 OK-BOMBA 1.0 (INHIBIR-REGLES RDECP005 RDECP006 RDECP007 RDECP008 RDECP009 RDECP019 RDECP020))
(MR-PRINC TÉ-FEBRE 1.0 (MOTOR-ENRERA GRIP))
(MR-ESTR01 CLASSE1 POSSIBLE (MÒDULS-A-TRACTAR C1))
(MR-03024 SIDA POSSIBLE (MÒDULS-A-TRACTAR BACTERIANA-ATÍPICA PNEUMOCISTIS-CARINI TBC CITOMEGALOVIRUS CRIPTOCOC NOCARDIA ASPERGILLUS PNEUMOCOC ENTEROBACTÈRIES)) (MR-02012 EDAT < 14 SEGUR (PARAR-SISTEMA))
Meta-regles: exemples
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
Raonament Basat en Casos(Case-Based Reasoning, CBR)
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Raonament Basat en Casos (I)
Perquè va sorgir el CBR?
Problema: Moltes vegades les dificultats en construïr Sistemes Experts provenen de intentar expressar la experiència en regles.
Habitualment és molt difícil per a un expert en una matèria el procés d’abstracció necessari per a crear regles genèriques a partir de sucessos especifics del passat.
Experiència
REGLES
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Experiència
Raonament Basat en Casos (II)
La solució del CBR:
Utilitzar la experiència (episodis passats) en el procés de raonament (raonament per analogíaraonament per analogía).
No fa falta traducció.
Experiència
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Raonament Basat en Casos (III)
Una definició:
“.... transferring knowledge from past problem
solving episodes to new problems that share
significant aspects with corresponding past
experience and using the transferred knowledge
to construct solutions to new problems.”
(Carbonell, 1986)
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
CBRCBR: Una metodologia per resoldre problemes adaptant les solucions de problemes anteriors que siguin similars.
Utilitza casoscasos com una memoria episódica (Case Case LibraryLibrary).
Raonament Basat en Casos (IV)
Solució
Problema
Nova Solució
Nou Problema
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Raonament Basat en Casos (V)
Un cascas és un conjunt de camps
identificador del cas
derivació del cas
descripció del problema
diagnòstic del problema
solució al problema
evaluació de la solució (èxit/fracàs)
mesura d’utilitat
altra informació rellevant
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Raonament Basat en Casos (VI)
newcase
retrievedcases
bestcase
adaptedsolution
evaluatedsolution
(fail/success)
Retrieve
Adapt Eval
Learncase
to store
CASELIBRARY
DOMAINKNOWLEDGE
El cicle del CBR:
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Raonament Basat en Casos (VII)
Recuperació o RetrieveRetrieve (I): Recuperació de casos és més difícil que la recuperació
(consulta) en BD.• Recuperació en BD = “matching” exacte• Recuperació en CBR = “matching” parcial (similitud)
Similitud:• es calcula entre descripcions de casos,• sol esser una funció d’evaluació heurística o distància,• pot esser dependent del domini.
un exemple:• descripció del cas = conjunt d’atributs
• mesura de similitud =
La Recuperació ha d’intentar maximitzar la similitud entre el cas actual i el(s) cas(os) recuperat(s).
n
kjkikkji CCdistatrwCCdist
1
),(_),(
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Raonament Basat en Casos (VIII)
Recuperació o RetrieveRetrieve (II): La eficiència del procés de recuperació depén fortament
de la organització de la Case Library dues aproximacions:
La estructura de la Case Lib. i la representació del cas facilita la recuperació dels casos rellevants i la seva comparació amb el problema en curs
Memòries planes
• Fàcils de gestionar• Lentes a la recuperació• Sempre troba el millor
Memòries jeràrquiques
• Difícils de gestionar• Ràpides a la recuperació• Cerca heurística
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Raonament Basat en Casos (IX)
Adaptació o AdaptAdapt: Quan el cas seleccionat de la Case Lib. no concorda
perfectament amb el nou cas, la solució antiga ha d’esser adaptada poer obtenir la nova solució.
Estratègies:
• adaptació nul·la
• adaptació estructural
– mètodes de substitució
– mètodes de transformació
– adaptació ad-hoc (special-purpose)
• adaptació derivacional
La adaptació és un procés altament depenent del domini.
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Raonament Basat en Casos (X)
Evaluació o EvalEval: Calificar la qualitat de la solució.
Tres formes de fer-ho:• Executar la solució en el mon real • Preguntar a un expert humà• Fer una simulació (laboratori, computeritzada, etc…)
Aprenentatge o LearnLearn:
Aprenentatge per observacions (conj. de casos inicials)
Aprenentatge per experiència
• Aprenentatge dels èxits• Aprenentatge del fracàs
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Quan utilitzar CBR?
Quan existeix un gran volum de dades històriques
Quan els experts parlen sobre el seu domini mitjançant exemples
Quan la experience és tan valuosa com el coneixement dels “llibres de text”
Quan els problemes no son entesos completament (models de domini dèbils, poc coneixement sobre el domini)
Hi ha masses excepcions a les regles
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Aplicacions del CBR
Diagnòsi de fallades en màquines
Diagnòsi de xarxes de computadors
Diagnòsi mèdica
Anàlisi de crèdits
Predicció de diposits geològics
Planificació de Batalles
Classificació dels missatges Telex d’un banc
Reconeixement de la parla
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Avantatges del CBR
Fàcilitat en extreure el coneixement de l’expert per crear la base de casos
Facilitat per fer un procés d’aprenentatge automàtic
El raonador va millorant el seu comportament amb el temps
Pot tractar fàcilment els casos excepcionals
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Inconvenients del CBR
No sempre la estructura de la Llibreria de Casos permet a un humà extreure coneixement
Les funcions d’adaptació s’han de crear per a cada domini
No pot raonar sobre allò que mai ha passat
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
Combinant regles i casos
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Regles VS. Casos
Expressen coneixement genèric
Difícil aprendre noves regles i mantenir la consistència
Coneixement estàtic No aprenentatge
Difícil d’extreure el coneixement de l’expert per crear la Base de Regles
Rendiment sempre és el mateix
Expressen coneixement específic (episòdic)
Fàcil aprendre nous casos, integrant-los a la llibreria
Coneixement dinàmic Aprenentatge
Relatívament fàcil d’extreure el coneixement de l’expert per crear la Base de Casos
Rendiment s’incrementa amb el temps
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
Com combinar-ho?
Engegar tots dos sistemes alhora Les regles diuen que s’ha de fer normalment Els casos recorden experìencies pasades (positives o
negatives) Problema: Què fer quan es contradiuen?
Extracció de coneixement genèric a partir de coneixement específic
Quan es té un conjunt de casos amb similars solucions, es pot generalitzar el coneixement en forma de regla i incorporar-ho a la Base de Regles
• Aprenentatge segur de regles
DAI-DEPURDAI-DEPUR
Sis
tem
as
de
So
po
rte
a la
De
cis
ión
J. Vázquez & KEMLg. IA-LSI, UPC. jvazquez@lsi.upc.es
SE + CBR:
DAI-DEPUR
3 layers3 layers