LOGICA, KR e INTELLIGENZA ARTIFICIALE

Matteo Palmonari, Alessandro MoscaMatteo.palmonari;Alessandro.mosca@disco.unimib.it

DISCo - Università di Milano-Bicocca

Intelligenza e computazioneIntelligenza e computazione

► Diversi modelli di intelligenza... filosofia, psicologia... Diversi modelli di intelligenza... filosofia, psicologia... ► UnaUna tradizione... Intelligenza come tradizione... Intelligenza come calcolocalcolo..

►Approccio formale allo studio della mente Approccio formale allo studio della mente come manipolazione di simboli. Se come manipolazione di simboli. Se l’intelligenza è manipolare simboli, una l’intelligenza è manipolare simboli, una macchina può pensare? macchina può pensare? ►Un Agente Intelligente secondo questo Un Agente Intelligente secondo questo approccio ha una descrizione simbolica del approccio ha una descrizione simbolica del mondo e delle regole per “manipolare” questi mondo e delle regole per “manipolare” questi simboli.simboli.

Mente vs. Comportamento Mente vs. Comportamento vs. Fisiologia: vs. Fisiologia: funzionalismo cognitivista funzionalismo cognitivista vs comportamentismo e vs comportamentismo e fisiologiafisiologia

Che cos’è un calcolo? Che cos’è un calcolo? Alan Turing: una Alan Turing: una nozione formale di nozione formale di algoritmo: algoritmo: la Macchina di Turingla Macchina di Turing

Intelligenza Artificiale ... da Intelligenza Artificiale ... da questo punto di vistaquesto punto di vista

► Uno studio empirico delle attività cognitive umane (modelli psicologici computrazionali).

► Una ricerca sugli strumenti di rappresentazione. Linguaggi, tecniche e modelli computazionali KR (Rappresentazione della conoscenza).

► Una disciplina ingegneristica; svolgimento di compiti complesso sulla base di tali modelli.

Conoscenza, Rappresentazione Conoscenza, Rappresentazione e Ragionamentoe Ragionamento

► La conoscenza è connessa alla nozione di veritàLa conoscenza è connessa alla nozione di verità E.g. John sa(crede?) che oggi non piovaE.g. John sa(crede?) che oggi non piova

► Rappresentazione...Rappresentazione... ““representation is a relationship between two representation is a relationship between two

domains, where the first is meant to “stand for”, or domains, where the first is meant to “stand for”, or take place of the second. (...) Usually the first take place of the second. (...) Usually the first domain, the representor, is more conrete, domain, the representor, is more conrete, immediate, or accessible in some way of the second”immediate, or accessible in some way of the second”

Cioò che “sta per” sono i SIMBOLICioò che “sta per” sono i SIMBOLI► Ragionamento: manipolazione formale di Ragionamento: manipolazione formale di

simboli che rappresentano un insieme di simboli che rappresentano un insieme di proposizioni ritenute vere (rappresentazioni), proposizioni ritenute vere (rappresentazioni), affinchè vengano prodotte nuove affinchè vengano prodotte nuove rappresentazioni rappresentazioni

Una teoria della mente Una teoria della mente rappresentazionalerappresentazionale

► Le rappresentazioni sono di tipo simbolico.

The Phisical Symbolic System HypothesisA phisical symbolic system has necessary and sufficient instruments to perform general intelligent actions.

[Newell, Simon]

1. Simboli primitivi (atomi);2. Strutture complesse;3. Regole di Trasformazione dei simboli e delle strutture

complesse;4. Denotazione dei simboli.

... La disciplina della Rappresentazione della Conoscenza.

1) Queste strutture, viste da un osservatore esterno al sistema, possano essere interpretate come rappresentazione della conoscenza di cui il sistema dispone;

2) Indipendentemente da tale attribuzione semantica, tali strutture devono poter essere manipolabili formalmente, in modo da poter giocare un ruolo causale nel determinare il comportamento del sistema.

[The Knowledge Representation Hypothesis - Brian Smith,Prologue to “Reflection and Semantics in a Procedural Language”, 1982]

Il fine di un sistema di rappresentazione della conoscenza è individuare strutture simboliche e meccanismi di inferenza appropriati sia per rispondere a domande che per acquisire nuove informazioni, in accordo con la teoria della verità del linguaggio di rappresentazione sottostante.

[R. Brachman e H. Levesque, Readings in Knowledge Representation, 1985]

Ogni sistema “intelligente” deve incorporare un insieme di strutture tali che:

Perchè la Logica come sistema Perchè la Logica come sistema simbolico...simbolico...

1) La Logica è Formal (e quanto più generale possibile).

2) La Logica è Mathematical.

3) La Logica è Symbolic (sintassi, semantica).

4) La Logica ha un Calculus (corretto e completo).

... La Logica è Rappresentazione della Conoscenza.

La LogicaLa Logica

► SintassiSintassi formule corretteformule corrette manipolazione simbolicamanipolazione simbolica

► SemanticaSemantica Interpretazione dei simboli, concetto di veritàInterpretazione dei simboli, concetto di verità

► InferenzeInferenze Tautologie e conseguenze logiche (semantica)Tautologie e conseguenze logiche (semantica) Derivabilità (sintassi)Derivabilità (sintassi)

► Espressività:Espressività: Logica ProposizionaleLogica Proposizionale Logica PredicativaLogica Predicativa

Costituenti “logici” del linguaggio,

Costituenti “extra-logici” del linguaggio,

First Order Logic (FOL)First Order Logic (FOL)

Termini

Formule Atomiche

Formule ben formate

Alcune espressioniAlcune espressioni

1. Mario è un architetto oppure è un geometra.Se Mario fosse architetto, allora Mario sarebbe laureato.Mario non è laureato.Quindi: Mario è un geometra .

2. Giovanni Paolo II è siciliano.Tutti i siciliani sono giardinieri.Quindi: Giovanni Paolo II è giardiniere.

3. Tutti i cigni osservati sinora in Europa sono bianchi.Tutti i cigni osservati sinora in Nord America sono bianchi.Tutti i cigni osservati sinora in Sud America sono bianchi […]Non sono mai stati osservati cigni che non fossero bianchi.Quindi: Tutti i cigni sono bianchi.

4. L’assassino ha sporcato di fango il tappeto.Chiunque fosse entrato dal giradino avrebbe sporcato di fango il tappeto.Quindi: L’assassino è entrato dal giardino.

5. Gli uccelli, salvo eccezioni, sono in grado di volare.Titti è un uccello.Quindi: Titti è in grado di volare.

Alcune inferenzeAlcune inferenze

Scegliere un linguaggio:

• una sintassi

• una semantica

Problemi:

Espressività (cosa posso rappresentare?)

Reasoning (cosa ci faccio?)

Logica e modelli: cos’è un Logica e modelli: cos’è un modello?modello?

Logica come strumento di modellazione!

Qualche problema...Qualche problema...

Problemi con FOL e la Problemi con FOL e la programmazione logicaprogrammazione logica

► FOL è indecidibileFOL è indecidibile ► Esplosione Esplosione combinatoria combinatoria La complessità di una La complessità di una

dimostrazione cresce dimostrazione cresce esponenzialmente esponenzialmente rispetto alla lunghezza rispetto alla lunghezza della formuladella formula

Sottoinsiemi decidibili :Clausole di Horn - Prolog

Limiti di espressività

Euristiche, raffinamento degli algoritmi di ricerca

Logicisti vs. Anti-logicisti nell’IA Logicisti vs. Anti-logicisti nell’IA simbolicasimbolica

►Una lunga disputa: ’60 Una lunga disputa: ’60 ’80 ’80

►Approccio logicoApproccio logico: McCarthy, : McCarthy, McDermott, R.C. Moore, Reiter, McDermott, R.C. Moore, Reiter, KowalskyKowalsky

►Approcci anti-logici Approcci anti-logici : Minsky, Simon, : Minsky, Simon, NewellNewell

Anti-logicisti: considerazioni Anti-logicisti: considerazioni generali generali

► MinskyMinsky Il ragionamento logico non è abbastanza flessibile.Il ragionamento logico non è abbastanza flessibile. La Conoscenza non consiste in un insieme di proposizioni La Conoscenza non consiste in un insieme di proposizioni

atomiche atomiche più più un insieme di regole di inferenza: è molto più un insieme di regole di inferenza: è molto più strutturata.strutturata.

Un approccio Un approccio puramente dichiarativo puramente dichiarativo è discutibile: è discutibile: rilevanza delle descrizioni procedurali.rilevanza delle descrizioni procedurali.

► Shank e RiegerShank e Rieger““DimostrazioneDimostrazione” logica (concetto formale)” logica (concetto formale)

VsVsInferenzaInferenza come processo psicologico come processo psicologico

(magari scorretto, guidato da associazioni)(magari scorretto, guidato da associazioni)

Anti-logicisti: tre puntiAnti-logicisti: tre punti

► Concetti definitiConcetti definiti (logica (logica condizioni condizioni necessarie e/o sufficienti) necessarie e/o sufficienti) vsvs prototipi prototipi (oggetti normali con valori di defaut).(oggetti normali con valori di defaut).

► Le Le inferenze inferenze umane sono umane sono sistematicamente sistematicamente incorrette incorrette da un punto di da un punto di vista logico. Il ragionamento del senso vista logico. Il ragionamento del senso comune non segue regole logiche.comune non segue regole logiche.

► LaLa memoria memoria è strutturata in maniera più è strutturata in maniera più complessa che in teorie logiche (assiomi): complessa che in teorie logiche (assiomi): vicinanza semantica (e.g. Cometa/Natale).vicinanza semantica (e.g. Cometa/Natale).

Logicisti: tre puntiLogicisti: tre punti

► I formalismi per la rappresentazione della I formalismi per la rappresentazione della conoscenza (KR) necessitano di una conoscenza (KR) necessitano di una semantica semantica adeguataadeguata per garantire la per garantire la preservazione della correttezzapreservazione della correttezza (specialmente per programmi lunghi e (specialmente per programmi lunghi e

complessi).complessi).► Livello dell’espressioneLivello dell’espressione vsvs livello livello

dell’implementazionedell’implementazione[P. Hayes]. [P. Hayes]. Logica al livello dell’espressione: giustificazione Logica al livello dell’espressione: giustificazione

delle inferenze.delle inferenze.► Logiche per modellare il Logiche per modellare il ragionamento del ragionamento del

senso comunesenso comune.. Estendere e modificare la logica matematica.Estendere e modificare la logica matematica.

RiassumendoRiassumendo

►La Logica è estremamente generale e La Logica è estremamente generale e non necessita di assunzioni ontologiche non necessita di assunzioni ontologiche [Moore].[Moore].

►Rappresentazione in termini di Rappresentazione in termini di individui, relazioni e funzioni individui, relazioni e funzioni praticamente ogni dominio. praticamente ogni dominio.

Differenti risposteDifferenti risposte

Flessibilità

Incertezza

Incompletezzadelle informazioni

Approccipiù vicini

alla logica

classica

Approcci basati sull’analisi

numerica

Logiche Fuzzy e della probabilità,reti neurali e

algoritmi genetici

Approcci differenti:Elemento comune non monotonia

LOGICHE NON MONOTONE

Ragionamento del senso Ragionamento del senso comunecomune

► Inferenze sulla base di informazioni incompleteInferenze sulla base di informazioni incomplete Non abbiamo bisogno di conoscere tutti i dettagli di una Non abbiamo bisogno di conoscere tutti i dettagli di una

situazione per trarre ragionevolmente molte inferenzesituazione per trarre ragionevolmente molte inferenze► IncertezzaIncertezza

Queste inferenze posso non essere così certe come le Queste inferenze posso non essere così certe come le inferenze in matematicainferenze in matematica

► FlessibilitàFlessibilità La base di conoscenza cambia. Nuovi fatti sono La base di conoscenza cambia. Nuovi fatti sono

aggiunti aggiunti

La logica è classicamente monotona

Il ragionamento del senso comune è NONMONOTONO!

Bibliografia

[1] Stuart Russell, Peter Norvig, Artificial Intelligence. A modern Approach, Prentice Hall, New Jersey, 1995.

[2] Michael R. Genesereth, Nils J. Nilsson, Logical Foundations of Artificial Intelligence, Morgan Kaufmann Publishers Inc., California, 1987.

[3] Corrado Mangione e Silvio Bozzi, Storia della Logica. Da Boole ai giorni nostri, Garzanti, Milano, 1993.

[4] Maurizio Negri, Elementi di Logica, LED - Edizioni Universitarie di Lettere, Economia, Diritto, Milano, 1994.

[5] John McCarthy e Patrick J. Hayes, Some Philosophical Problems from the Standpoint of Artificial Intelligence, Computer Science Department, Stanford University,

Stanford, 1969.

[6] John McCarthy, Epistemological Problems of Artificial Intelligence, Computer Science Department, Stanford University, Stanford, 1977.

[7] Randall Davis, Howard Shrobe e Peter Szolovits, What is a Knowledge Representation?, Artificial Intelligence Laboratory and Laboratory for Computer Science at MIT, published by AI Magazine, 14(1):17-33, 1993.

[8] Robert Kowalski, The limitations of Logic, Department of Computing, Imperial College, London. An earlier version of this paper was presented at the Workshop on Knowledge Base Management System, Creta, Giugno 1985 [published by Springler Verlag].

[9] Frixione, M. (1994), Logica, Significato e Intelligenza Artificiale. - Milano: Francoangeli.

[10] J. Cheng, Logical Tool of Knowledge Engineering: Using Entailment Logic rather than Mathematical Logic, Depertment of Computer Science and Communication

Engineering, Kyushu University, Fukuoka, Japan, 1991.

NONMONOTONIC REASONING

[11] BREWKA, G. (1991), Nonmonotonic Reasoning: Logical Foundations of Commonsense. - Cambridge: Cambridge University Press.

[12] BREWKA, G., DIX, J. AND KONOLIGE, K. (1997), Non Monotonic Reasoning: An Overview. - Stanford: Center For The Study Of Language And Information.

[13] FISHER SERVI, G. (2001), Quando l'eccezione è la regola: le logiche non monotone. - Milano: McGraw-Hill.

[14] GABBAY, D.M., HOGGER, C.J. e ROBINSON, J.A. (a cura di) (1993 e 1994), Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. III: Non Monotonic and

Uncertain Reasoning. - Oxford.

Bibliografia (logiche non monotone)

La possibilità di costruire sistemi logici diversi mostra che la logica non è ristretta alla riproduzione dei fatti, ma è un libero prodotto dell’uomo come un’opera d’arte.

Jan Łukasiewicz