Sistemi Intelligenti

Sistemi Intelligenti 2022

Contents

1 Introduzione 6

1.1 Turing Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Strong e Weak AI 7

3 Agenti e ambienti 7

3.1 Caratteristiche dell'ambiente . . . . . . . . . . . . . . . . . . . 8

4 Non-AI software 9

5 AI software 9

6 Automazione vs autonomia 10

7 Razionalità di un agente 11

8 Quali classi di problemi si prestano ad essere risolti dall'AI? 12

9 Risoluzione automatica di problemi 12

9.1 Obiettivi e ricerca . . . . . . . . . . . . . . . . . . . . . . . . . 13

9.2 Definizione formale di un problema . . . . . . . . . . . . . . . 14

9.3 Metodi di ricerca non informati - Blind Search . . . . . . . . . 14

9.3.1 Grafo di ricerca . . . . . . . . . . . . . . . . . . . . . . 15

9.4 Nodi creati e nodi esplorati . . . . . . . . . . . . . . . . . . . 16

9.5 Criteri di valutazione delle strategie . . . . . . . . . . . . . . . 16

9.6 Lista delle strategie . . . . . . . . . . . . . . . . . . . . . . . . 17

9.7 Ricerca in ampiezza . . . . . . . . . . . . . . . . . . . . . . . . 17

9.7.1 Valutazione della ricerca in ampiezza . . . . . . . . . . 17

9.8 Ricerca a costo uniforme . . . . . . . . . . . . . . . . . . . . . 18

9.8.1 Valutazione dell'algoritmo di ricerca a costo uniforme . 18

9.9 Ricerca in profondità senza backtracking . . . . . . . . . . . . 19

9.10 Ricerca in profondità con Backtracking . . . . . . . . . . . . . 19

9.10.1 Valutazione della ricerca in profondità . . . . . . . . . 19

9.11 Variante: Ricerca a profondità limitata . . . . . . . . . . . . . 20

9.11.1 Potenziali problemi . . . . . . . . . . . . . . . . . . . 20

9.12 Iterative Deepening . . . . . . . . . . . . . . . . . . . . . . . 20

9.12.1 Valutazione dell'iterative deepening . . . . . . . . . . . 21

9.13 Ricerca bidirezionale . . . . . . . . . . . . . . . . . . . . . . 21

9.13.1 Valutazione della Ricerca bidirezionale . . . . . . . . . 22

10 Metodi di ricerca informati 22

10.1 Ricerca Greedy (avara) . . . . . . . . . . . . . . . . . . . . . . 23

10.1.1 Problemi . . . . . . . . . . . . . . . . . . . . . . . . . . 23

10.2 A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

10.2.1 Pseudocodice di A* . . . . . . . . . . . . . . . . . . . 24

10.3 Ottimalità di A* per gli alberi . . . . . . . . . . . . . . . . . . 25

10.3.1 Dimostrazione . . . . . . . . . . . . . . . . . . . . . . . 25

10.4 Ottimalità di A* per i grafi . . . . . . . . . . . . . . . . . . . 27

10.4.1 Considerazioni su A* . . . . . . . . . . . . . . . . . . 28

10.4.2 Considerazioni sull'euristica . . . . . . . . . . . . . . . . 28

10.5 Euristiche monotone ed ammissibili . . . . . . . . . . . . . . . 29

10.6 Funzioni euristiche . . . . . . . . . . . . . . . . . . . . . . . . 29

10.6.1 Valutazione della bontà di un'euristica . . . . . . . . . 29

11 Strategie di ricerca con avversario 31

11.1 Differenze con la ricerca informata e con la ricerca blind . . . 32

11.2 Possibili approcci . . . . . . . . . . . . . . . . . . . . . . . . . 32

11.3 Costruzione delle strategie . . . . . . . . . . . . . . . . . . . . 33

11.3.1 Funzione di valutazione valoreMinimax(n) . . . . . . . 34

11.3.2 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . 35

11.3.3 Valutazione dell'algoritmo . . . . . . . . . . . . . . . . 36

11.4 Minimax con Potatura Alfa-Beta . . . . . . . . . . . . . . . . 36

11.4.1 Algoritmo Alfa-Beta . . . . . . . . . . . . . . . . . . . 37

11.4.2 Confronto fra alpha-beta pruning e minimax . . . . . . 38

11.4.3 Uso di alfa-beta pruning nei contesti real time . . . . . 39

12 Constraint Satisfaction Problems 41

12.1 CSP e problemi di ricerca . . . . . . . . . . . . . . . . . . . . 41

12.1.1 Domini delle variabili . . . . . . . . . . . . . . . . . . . 42

12.1.2 Arità dei vincoli . . . . . . . . . . . . . . . . . . . . . . 42

12.1.3 Vincoli vs Criteri di preferenza . . . . . . . . . . . . . 42

12.2 Blind search: brute force . . . . . . . . . . . . . . . . . . . . . 43

12.2.1 Generate and Test . . . . . . . . . . . . . . . . . . . . 43

12.2.2 Importanza della rappresentazione di un problema . . . 43

12.2.3 Ricerca in profondità con backtracking . . . . . . . . . 43

12.2.4 Ricerca con backtracking - Osservazioni . . . . . . . . . 44

12.2.5 Euristiche di scelta della variabile . . . . . . . . . . . . 45

12.3 Rendere informata la ricerca . . . . . . . . . . . . . . . . . . . 45

12.4 Tecniche e Proprietà per la propagazione di informazioni . . . 46

12.4.1 Forward Checking . . . . . . . . . . . . . . . . . . . . . 47

12.4.2 Node consistency . . . . . . . . . . . . . . . . . . . . . 47

12.4.3 Arc consistency . . . . . . . . . . . . . . . . . . . . . . 47

12.5 ARC-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

12.6 Commenti su Arc Consistency . . . . . . . . . . . . . . . . . . 49

12.7 Path Consistency . . . . . . . . . . . . . . . . . . . . . . . . . 49

12.8 Generalizzazione: k-consistency . . . . . . . . . . . . . . . . . 50

12.8.1 Vincoli Speciali . . . . . . . . . . . . . . . . . . . . . . 51

12.9 Migliorare ulteriormente il Backtracking . . . . . . . . . . . . 52

12.9.1 Costruzione di un conflict set . . . . . . . . . . . . . . 53

12.9.2 Algoritmo Backjump . . . . . . . . . . . . . . . . . . . 53

13 Rappresentazione della Conoscenza 54

13.1 Programmazione di agenti basati sulla conoscenza . . . . . . . 55

13.2 Applicazione di meccanismi automatici sulla KB . . . . . . . . 55

13.3 Logica proposizionale . . . . . . . . . . . . . . . . . . . . . . . 58

13.3.1 Grammatica . . . . . . . . . . . . . . . . . . . . . . . . 58

13.4 Background Knowledge come formule logiche . . . . . . . . . . 58

13.5 Come dimostrare la conseguenza logica . . . . . . . . . . . . . 59

13.5.1 Theorem Proving . . . . . . . . . . . . . . . . . . . . . 60

13.6 Formulazione come problema di ricerca nello spazio degli stati 62

13.7 Regola di risoluzione . . . . . . . . . . . . . . . . . . . . . . . 62

13.8 Clausole di Horn . . . . . . . . . . . . . . . . . . . . . . . . . 64

13.8.1 Forward Chaining . . . . . . . . . . . . . . . . . . . . . 64

13.8.2 Backward chaining . . . . . . . . . . . . . . . . . . . . 65

14 Logica del primo ordine 66

14.1 Enumerazione dei modelli e conseguenza logica . . . . . . . . . 70

14.2 Termini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

14.3 Formule atomiche . . . . . . . . . . . . . . . . . . . . . . . . . 71

14.4 Quantificatori . . . . . . . . . . . . . . . . . . . . . . . . . . 71

14.5 DataBase semantics . . . . . . . . . . . . . . . . . . . . . . . . 72

14.6 Interrogazione di KB in FOL . . . . . . . . . . . . . . . . . . . 73

14.6.1 Sostituzione . . . . . . . . . . . . . . . . . . . . . . . . 73

14.7 Ragionamento automatico in FOL . . . . . . . . . . . . . . . . 73

14.8 Proposizionalizzazione . . . . . . . . . . . . . . . . . . . . . . 74

14.8.1 Confronto fra IU e IE . . . . . . . . . . . . . . . . . . . 75

14.8.2 Problema delle funzioni . . . . . . . . . . . . . . . . . . 75

14.9 Guidare la scelta della sostituzione . . . . . . . . . . . . . . . 76

14.10 Modus Ponens Generalizzato . . . . . . . . . . . . . . . . . . . 76

14.11 Unificazione . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

15 Clausole di Horn in FOL 78

15.1 Forward Chaining in FOL . . . . . . . . . . . . . . . . . . . . 78

15.1.1 Proprietà del Forward Chaining . . . . . . . . . . . . . 78

15.2 Backward Chaining in FOL . . . . . . . . . . . . . . . . . . . 78

15.2.1 Valutazione del Backward Chaining . . . . . . . . . . . 79

16 Lifting di Risoluzione e Refutazione 79

16.1 Valutazione della risoluzione . . . . . . . . . . . . . . . . . . . 80

17 Costruire una KB in FOL - Knowledge Engineering 81

17.1 Concettualizzazione . . . . . . . . . . . . . . . . . . . . . . . . 81

17.2 T-box e A-box . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

18 Uso delle ontologie 83

18.1 Semantic Web . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

18.2 RDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

18.3 Costruzione di un'ontologia . . . . . . . . . . . . . . . . . . . 83

18.4 OWL 2 - Web Ontology Language . . . . . . . . . . . . . . . . 84

18.4.1 Semantica diretta . . . . . . . . . . . . . . . . . . . . . 84

18.4.2 Semantica basata su RDF . . . . . . . . . . . . . . . . 84

18.5 Modelli di conoscenza in OWL . . . . . . . . . . . . . . . . . . 84

18.6 Matching di ontologie . . . . . . . . . . . . . . . . . . . . . . . 85

18.6.1 Relazioni fra ontologie . . . . . . . . . . . . . . . . . . 85

18.7 OWL2 e DB . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

19 Rappresentazione delle azioni 86

19.1 Situation Calculus . . . . . . . . . . . . . . . . . . . . . . . . 86

19.2 Assiomi di Applicabilità . . . . . . . . . . . . . . . . . . . . . 87

19.3 Assiomi di Effetto . . . . . . . . . . . . . . . . . . . . . . . . 88

19.4 Inferenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

19.5 Frame Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 88

20 Agenti 89

20.1 Caratterizzazione dell'ambiente . . . . . . . . . . . . . . . . . 91

20.2 Architetture degli agenti . . . . . . . . . . . . . . . . . . . . . 92

20.3 Agenti reattivi semplici . . . . . . . . . . . . . . . . . . . . . . 92

20.4 Agenti basati su modello . . . . . . . . . . . . . . . . . . . . . 93

20.5 Agenti basati su obiettivi . . . . . . . . . . . . . . . . . . . . . 94

20.6 Agenti basati sull'utilità . . . . . . . . . . . . . . . . . . . . . 95

20.7 Agenti che apprendono . . . . . . . . . . . . . . . . . . . . . . 95

20.8 Multi-agent Systems . . . . . . . . . . . . . . . . . . . . . . . 95

21 Classificazione 96

21.1 Matrice di confusione . . . . . . . . . . . . . . . . . . . . . . . 97

21.2 Omogeneità dei Test Set . . . . . . . . . . . . . . . . . . . . . . 98

21.3 Alberi Decisionali . . . . . . . . . . . . . . . . . . . . . . . . . 99

21.4 Costruzione di un albero decisionale - Algoritmo di Hunt . . . 99

21.5 Valutazione di un modello . . . . . . . . . . . . . . . . . . . . 103

21.5.1 Valutazioni fatte su test set: . . . . . . . . . . . . . . . 103

21.5.2 Confronto fra modelli diversi . . . . . . . . . . . . . . . 103

22 Classificatori a Regole 104

22.1 Calcolo della qualità di una regola . . . . . . . . . . . . . . . . 104

22.2 Produzione delle regole . . . . . . . . . . . . . . . . . . . . . . 105

22.2.1 Sequential Covering . . . . . . . . . . . . . . . . . . . . 105

22.3 Learn one rule . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

22.4 Lazy Learners . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

22.4.1 Calcolo della classe con KNN . . . . . . . . . . . . . . 107

23 Reti Neurali 108

23.1 Perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

23.2 Apprendimento . . . . . . . . . . . . . . . . . . . . . . . . . . 108

23.3 Reti Neurali . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

23.4 Multi-Layer Perceptron . . . . . . . . . . . . . . . . . . . . . . 109

23.5 Apprendimento per le Reti Neurali . . . . . . . . . . . . . . . 110

23.6 Backpropagation . . . . . . . . . . . . . . . . . . . . . . . . . 111

23.6.1 Caso con un solo neurone di output . . . . . . . . . . . 111

23.7 Neuroni Hidden . . . . . . . . . . . . . . . . . . . . . . . . . . 111

1 Introduzione

Fino agli anni '50, tutto ciò che riguardava l'intelligenza artificiale era relativo a speculazioni filosofico-etiche, in quanto la tecnologia non permetteva, neanche oggi siamo in grado di produrre un AI forte, di sperimentare direttamente sulle macchine.

Ci si domanda su quali siano i requisiti per poter definire un agente artificiale intelligente.

Una macchina può "pensare" ed essere considerata intelligente?

• Turing Test

1.1 Turing Test

Ha come scopo quello di capire se un computer sia intelligente o meno.

Il test è articolato come segue: abbiamo una prima persona detta interlocutore, posta di fronte ad un muro/tenda. Non può dunque vedere cosa si cela dietro di esso/essa.

Dall'altro lato della tenda, abbiamo rispettivamente un computer, di cui dobbiamo stabilire l'intelligenza, ed un'altra persona.

L'interlocutore può comunicare con l'altro lato della tenda solo testualmente.

La macchina viene definita intelligente nel momento in cui l'interlocutore non è in grado di distinguere una risposta fornita dalla macchina da una risposta fornita dalla persona.

Questo test è sufficiente per definire la macchina come intelligente?

In altre parole, il fatto che di fronte agli stessi input una macchina ed un uomo producano gli stessi output, significa che entrambi capiscono cosa stanno facendo?

In questo caso stiamo facendo combaciare l'intelligenza con la comprensione. Possiamo facilmente smentire il fatto che il computer capisca cosa stia facendo, usando lo stesso scenario del Test di Turing, ma al posto del computer mettiamo una persona che non parla la lingua con cui sono scritti i testi a cui risponde, ma ha ricevuto istruzioni su come rispondere agli stimoli.

La persona non comprende il linguaggio, ma si comporta esattamente come una macchina di Turing.

Il Test di Turing non è un valido metro di intelligenza.

2 Strong e Weak AI

• Strong AI: è possibile riprodurre l'intelligenza umana? Si tratta dello studio del pensiero e del comportamento umano, scienze cognitive.
• Weak AI: è possibile trovare dei modi per risolvere dei problemi che, se risolti da esseri umani, richiederebbero intelligenza? Task-oriented: si tratta dello studio del pensiero e del comportamento razionale.

Si tratta di strumenti in grado di affrontare un singolo problema alla volta, e lo fanno come lo farebbe una persona, senza cercare di essere una persona.

Sono orientati alla risoluzione di problemi, ma sono in grado di risolvere un solo problema. Non sono intelligenti in senso lato, a tutto tondo.

3 Agenti e ambienti

Il binomio agente-ambiente è un binomio imprescindibile: l'agente ha senso solo se considerato in un ambiente, e l'ambiente è tale poiché composto da agenti.

Agente: astrazione che rappresenta un qualsiasi sistema che percepisce il proprio ambiente tramite i sensori ed agisce su di esso tramite i suoi attuatori.

L'iterazione base di un agente è la seguente:

Percepisce → Delibera → Agisce

A seconda dei sensori ed attuatori di un agente, posso avere un binomio agente-ambiente più o meno funzionale.

Per deliberare intendiamo il processo interno di un agente tramite il quale stabilisce l'azione da compiere.

L'agente può essere dotato di fisico oppure essere solo software, non è prerogativa necessaria la fisicità. L'azione svolta dall'agente può anche non modificare l'ambiente in cui si trova. Può anche non compiere azioni.

3.1 Caratteristiche dell'ambiente

• Osservabilità: può essere parziale o totale, in base al fatto che i sensori dell'agente diano accesso a tutti gli aspetti dell'ambiente rilevanti per la deliberazione, o meno.
• Deterministico/Stocastico, in base al fatto che lo stato successivo sia determinato, o meno. Stocastico: applicando più volte la stessa azione nelle stesse circostanze, ottengo risultati diversi.
• Episodico/Sequenziale. Episodico: l'esperienza degli agenti è divisa in episodi atomici, ovvero una singola percezione seguita da una singola azione. Sequenziale: Attività composta da più passi, ognuna delle quali influenzerà le successive.
• Statico/Dinamico: in base al fatto che l'ambiente non cambi mentre l'agente pensa, o meno.
• Discreto/Continuo: possono essere discreti o continui gli stati, tempo, percezioni e azioni.
• Singolo agente/Multiagente: in base al fatto che nell'ambiente sia presente uno o più agenti.

N.B.: Vi è una connessione fra il fatto che un ambiente sia parzialmente osservabile ed il fatto che sia stocastico. Spesso viene visto come stocastico un ambiente che è parzialmente osservabile perché non si ha la percezione di quegli aspetti che renderebbero deterministico il mondo.

4 Non-AI software

• Risolve un singolo compito.
• Tipicamente strutturato come una sequenza di passi: scrivo un algoritmo che risolva uno specifico problema.
• Esplico come si facciano le cose.

5 AI software

• Separa una descrizione dichiarativa da un programma generale.
• Lo stesso programma è applicato a diverse descrizioni per risolvere problemi diversi.
• Viene esplicato il cosa, fornendo una descrizione del mondo.
• Non viene scritto come si risolva un problema. Viene dato lo stato iniziale, e l'obiettivo che deve essere raggiunto. Chiediamo al software di trovare una soluzione, partendo da un risolutore generale di problemi.

Dato: sono i numeri forniti dai sensori, sono grezzi e non correlati fra loro.

Informazione: Pezzo di conoscenza utile estratto dall'elaborazione dei dati. È ciò che il dato rappresenta.

Conoscenza: è ciò che ottengo dalle informazioni, correlandole fra loro tramite delle relazioni. Per elaborare delle informazioni è necessario rappresentarle.

Percezione: ricezione dei dati e processamento che permette di estrarre informazioni da dei dati.

6 Automazione vs autonomia

Automazione: Non-AI sono sistemi automatici, guidati da algoritmi. Consiste nella codifica di una sequenza di passi eseguibili da un sistema, senza che sia necessario l'intervento umano.

Autonomia: dare ad un agente artificiale un compito, aspettandosi che lo risolva senza fornirgli un algoritmo risolutivo. Sarà compito dell'agente stesso ricercare una soluzione. Si trova su un piano di astrazione molto più a