Sistemi basati sulla conoscenza - Ingegneria Elettrica ed Elettronica

Dipartimento di Ingegneria Elettrica ed Elettronica
Università degli Studi di Cagliari
Esempio
Seminario di Intelligenza Artificiale
A.A . 2013/2014
Docente: Giorgio Fumera
Sistemi basati sulla conoscenza
(Knowledge-based Systems)
Scrivere un programma in grado di guidare il protagonista
del gioco del Wumpus...
Esempio
2
Sistemi basati sulla conoscenza
●
Scrivere un programma in grado di dimostrare la
congettura di Goldbach (1742): dato un qualsiasi
numero pari p ≥ 4, esiste almeno una coppia di
numeri primi q e r (identici o meno) tali che:
q+r=p
●
3
Approccio seguito dagli esseri umani:
ragionamento logico
–
conoscenza esplicita (dichiarativa) su un problema
–
derivazione di nuova conoscenza attraverso il
ragionamento
Formalizzazione:
–
linguaggi per la rappresentazione della conoscenza
–
algoritmi d'inferenza
4
Logica e Intelligenza Artificiale:
applicazioni
●
●
●
Logica
Logica: studio delle condizioni di correttezza dei
ragionamenti
Dimostratori automatici di teoremi
●
Linguaggi di programmazione logica
(dichiarativi): Prolog
●
Sistemi esperti
●
5
ragionamento: insieme di proposizioni dichiarative:
premesse, conclusione
correttezza: se la conclusione non può essere falsa
quando tutte le premesse sono vere
dimostrazione: procedimento per la verifica della
correttezza
Esempio:
● Premesse:
Tutti gli uomini sono mortali, Socrate è un uomo
● Conclusione: Socrate è mortale
Logica
●
●
Logica formale
Proposizioni dichiarative: enunciati dotati di
significato, ai quali si possa attribuire un valore
di verità
Analizza la struttura dei ragionamenti. Esempio:
Premesse:
1) Se Socrate fosse un uomo, allora sarebbe mortale
2) Socrate è un uomo
Conclusione:
3) Socrate è mortale
Proposizioni semplici e composte. Es..
–
Socrate è un uomo
–
Due più due è uguale a quattro
–
Una partita di tennis si può vincere oppure perdere
–
Se la Terra fosse piatta, [allora] Colombo non
avrebbe scoperto l'America
6
Struttura:
Se U allora M
U
M
7
8
Linguaggi logici:
logica proposizionale
Logica classica
Sintassi:
●
●
Principio di determinatezza:
ogni proposizione ha un solo valore di verità
Principio di bivalenza:
esistono solo due valori di verità: vero e falso
Linguaggi logici:
logica proposizionale
proposizioni semplici: vere o false
–
proposizioni composte: vere o false, in base alla
definizione della semantica dei connettivi attraverso
tabella di verità; esempi:
●
P
Q
P∧Q
P
Q
P⇒Q
F
F
F
F
F
T
F
F
T
T
F
T
F
F
T
T
T
T
T
T
–
connettivi logici per formare proposizioni composte:
e, o (oppure), non, se...allora... (implicazione), ecc.
simboli: ∧, ∨, ¬, ⇒, ...
Socrate è un uomo: P
●
Socrate è mortale: Q
Se Socrate fosse un uomo, allora sarebbe mortale:
P⇒Q
10
In linguaggio naturale i connettivi logici possono assumere
significati diversi. Esempi:
–
F
proposizioni semplici: simboli (P, Q, R, ...)
Linguaggi logici e linguaggio
naturale
Semantica:
T
–
●
●
T
costanti logiche: Vero, Falso
Esempio:
9
F
–
●
●
11
Si allenò, e vinse la gara
"e" non indica solo il fatto che entrambi gli enunciati sono
veri, ma ha anche un significato temporale, o causale
In una partita a tennis si vince o si perde
"o" ha significato esclusivo, non inclusivo
Se 5 è dispari, allora Tokyo è la capitale del Giappone
Proposizione senza senso in linguaggio naturale, ma vera
se schematizzata con il conP
Q
P⇒Q
nettivo di implicazione ⇒
F
F
T
F
T
T
T
F
F
T
T
T
12
Correttezza dei ragionamenti
●
●
●
Definizione: un ragionamento è corretto se la conclusione
non può essere falsa quando tutte le premesse sono vere
Verifica: tabella di verità
Esempio: Premesse: P ⇒ Q, P, conclusione: Q
proposizioni semplici
●
Regole d'inferenza
premesse
Schemi di ragionamenti corretti, applicabili per la verifica della
correttezza di un ragionamento qualsiasi
Esempi:
●
conclusione
P
Q
P⇒Q
P
Q
F
F
T
F
F
F
T
T
F
T
T
F
F
T
F
T
T
T
T
T
●
●
Quindi questo ragionamento è corretto
Problema: complessità computazionale...
Eliminazione delle congiunzioni:
Premesse: P1 ∧ P2 ∧ ...∧ Pn, conclusione: P1, P2, ..., Pn
Introduzione delle disgiunzioni:
Premesse: P1, P2, ..., Pn, conclusione: P1 ∨ P2 ∨ ... ∨ Pn
Modus ponens:
Premesse: P ⇒ Q, P, conclusione: Q
13
14
Algoritmi d'inferenza
●
●
Consistono nell'applicazione sistematica di
regole d'inferenza per verificare (dimostrare) la
correttezza di un ragionamento
Due obiettivi principali:
–
–
verificare che una data conclusione segua da un
dato insieme di premesse (es.: dimostratori di
teoremi)
trovare tutte le conclusioni che seguono da un dato
insieme di premesse (es.: gioco del Wumpus,
sistemi esperti)
15
Logica proposizionale: limiti
●
●
●
Tutti gli uomini sono mortali; Socrate è un uomo;
Socrate è mortale. Schema: A; B; C
Tutti gli uomini sono mortali; Platone è un uomo;
Platone è mortale. Schema: A; D; E
Tutti i numeri divisibili per quattro sono pari; sedici è
divisibile per quattro; sedici è un numero pari.
Schema: F; G; H
Struttura comune, non rappresentabile in logica
proposizionale:
Tutto ciò che è P è anche Q; x è P; x è Q
16
Linguaggi logici:
logica dei predicati
●
●
●
●
Linguaggi logici:
logica dei predicati
Dominio del discorso: insieme di oggetti o individui
(cont.)
Termini costanti: simboli che indicano gli elementi del
dominio. Es.: Socrate, Platone, Sedici, Quattro
Predicati: proposizioni atomiche, vere o false, che
indicano proprietà degli elementi del dominio.
Es.: Uomo(Socrate), Mortale(Platone),
Pari(Sedici), Divisibile(Sedici, Quattro)
●
●
Connettivi: si applicano ai predicati per formare
proposizioni composte: ∧, ∨, ¬, ⇒, ⇔, ecc.
Es.: Pari(Quattro) ∧ Pari(Sedici)
Uomo(Socrate) ⇒ Mortale(Socrate)
(cont.)
Variabili: simboli che possono indicare qualsiasi
elemento del dominio, usati insieme ai quantificatori.
Es.: x, y, z
Quantificatori: costruzione di proposizioni atomiche
riguardanti un sottoinsieme del dominio.
–
universale: ∀
–
esistenziale: ∃
Es.: ∀x Mortale(x), ∃x Divisibile(x,Quattro)
17
18
Linguaggi logici:
logica dei predicati
Linguaggi logici:
logica dei predicati
Uso del quantificatore universale: esempio
Uso del quantificatore esistenziale: esempio
Tutti gli uomini sono mortali
Qualche uomo è intelligente
–
∀x Mortale(x): il significato è: "ogni elemento del
dominio è mortale", ed è corretto solo se ogni
elemento del dominio è un uomo
–
∃x Intelligente(x): il significato è "qualche elemento
del dominio è intelligente", ed è corretto solo se tutti
gli elementi del dominio sono uomini
–
∀x Uomo(x) ∧ Mortale(x): il significato è: "ogni
elemento del dominio è un uomo ed è mortale", ed
è corretto solo nelle stesse condizioni di sopra
–
∃x Uomo(x) ∧ Intelligente(x): è sempre corretta
–
∀x Uomo(x) ⇒ Mortale(x): è sempre corretta
19
20
Oltre la logica classica
●
Domani ci sarà una battaglia navale
–
●
Mario è alto, Questo problema è difficile
–
●
oggi è vero o falso...?
Sistemi esperti
logiche fuzzy
Congettura di Goldbach (1742): dato un
qualsiasi numero pari p ≥ 4, esiste almeno una
coppia di numeri primi q e r (identici o meno)
tali che q + r = p
–
non ancora dimostrata... in questo caso può
comunque essere considerata o vera o falsa?
21
22
Sistemi esperti
●
Sviluppati a partire dagli anni '70
●
Obiettivo:
●
–
codifica della conoscenza dichiarativa di esperti
umani in specifici domini applicativi, attraverso
regole della forma IF...THEN...
–
applicazione automatica delle regole a nuove
istanze ("fact") di un problema, riproducendo il processo di ragionamento eseguito da esperti umani
Applicazioni
●
●
●
●
●
Usati come sistemi di supporto alle decisioni
●
●
23
●
diagnosi medica
es.: NHS direct symptom checker:
http://www.nhsdirect.nhs.uk/CheckSymptoms
geologia, botanica
es.: classificazione di rocce e piante
help desk
finanza
strategie militari
ingegneria del software
videosorveglianza
...
24
Motore d'inferenza
(Inference Engine)
Architettura
User
Facts
(Working memory)
●
–
individuare le regole attive (quelle le cui condizioni
sono soddisfatte dai dati della working memory)
–
eseguire una delle regole attive (criteri di scelta:
meccanismi di risoluzione dei conflitti)
–
conclusione: quando nessuna regola è attiva
User Interface
Rules
(Rule memory)
Knowledge Base
Ciclo di esecuzione:
Inference Engine
Explanation Module
●
Le regole vengono definite in fase di progettazione dal
Knowledge Engineer, che le ricava dai Domain Expert
●
25
Esecuzione di una regola: inserimento,
modifica, o cancellazione di dati della working
memory
La soluzione del problema si troverà nella
working memory al termine dell'esecuzione
Software
26
CLIPS
●
CLIPS
●
http://clipsrules.sourceforge.net/
●
Jess
●
C Language Integrated Production System
●
Drools
●
1984, Johnson Space Center, NASA
●
...
●
Open source, gratuito
●
Integrazione con altri linguaggi (C, Python, ...)
●
Comprende:
27
–
linguaggio interpretato, funzionale (anche OO)
–
strutture dati e costrutti aggiuntivi per la definizione
di un sistema esperto
28

Download Report