Intelligenza Artificiale

2020/2021

INTELLIGENZA ARTIFICIALE – APPUNTI

CORSO LAUREA MAGISTRALE – CLOUD COMPUTING 1

Sommario

1. Agenti Intelligenti ................................................................................................................................ 6

1.1. Razionalità ........................................................................................................................................ 7

1.2. PEAS ................................................................................................................................................ 7

1.3. Ambiente .......................................................................................................................................... 7

1.4. Tipologie di agente ........................................................................................................................... 9

1.4.1. Agenti capaci di apprendere (estensione dei precedenti) ........................................................... 9

1.4.2. Rappresentare gli stati ..............................................................................................................10

2. Risolvere i problemi con la ricerca ......................................................................................................10

2.1. Agenti risolutori di problemi ...........................................................................................................10

2.2. Tipi di problemi ...........................................................................................................................11

2.3. Problemi di ricerca (a stato singolo o multiplo) ..........................................................................12

2.3.1. Algoritmi di ricerca ..............................................................................................................12

2.3.2. Dimostrazione di teoremi....................................................................................................12

2.4. Strategie di ricerca .....................................................................................................................12

2.4.1. Valutazione di una strategia ................................................................................................13

2.5. Ricerca non informata ................................................................................................................13

2.5.1. Ricerca in ampiezza .............................................................................................................13

2.5.2. Ricerca di costo uniforme ....................................................................................................14

2.5.3. Ricerca in profondità ...........................................................................................................14

2.5.4. Ricerca in profondità limitata (DL) ......................................................................................14

2.5.5. Ricerca con approfondimento iterativo (ID) ........................................................................15

2.5.6. Ricerca bidirezionale ...........................................................................................................15

2.5.7. Confronto delle strategie ....................................................................................................16

2.6. Ricerca Informata .......................................................................................................................16

2.6.1. Best-first search ..................................................................................................................16

2.6.3. Algoritmo A* .......................................................................................................................17

2.6.4. Beam search ........................................................................................................................18

2.6.5. A* con approfondimento iterativo (IDA*) ...........................................................................18

2.6.6. Best-first ricorsivo ...............................................................................................................18

2.6.7. A* con memoria limitata .....................................................................................................18

2.7. Funzioni euristiche ......................................................................................................................18

2.7.1. Misurare il potere euristico .................................................................................................19

2.7.2. Definire un’euristica ............................................................................................................19

3. Oltre la ricerca ....................................................................................................................................19

1.1. Ricerca locale ..............................................................................................................................19

2

1.1.1. Hill-climbing (ricerca in salita) ..............................................................................................20

1.1.2. Simulated annealing (tempra simulata) ...............................................................................21

1.1.3. Ricerca local beam ..............................................................................................................22

1.1.4. Algoritmi genetici ................................................................................................................22

1.2. Ricerca con azioni non deterministiche.......................................................................................24

1.2.1. Alberi AND-OR ....................................................................................................................25

1.4. Ricerca Online .............................................................................................................................28

1.4.1. Online DFS ...........................................................................................................................28

1.4.2. Ricerca locale online ...........................................................................................................29

2. Ricerca con avversari ..........................................................................................................................29

2.1. Decisioni ottime ..........................................................................................................................30

2.1.1. Minimax ..............................................................................................................................30

2.2. Tecniche di ottimizzazione della ricerca ......................................................................................31

2.2.1. Potatura Alfa-beta ..............................................................................................................31

2.2.2. Euristiche per approssimare l’utilità di uno stato ................................................................32

2.3. Estensione a giochi più complessi (stocastici) .............................................................................33

2.3.1. Minimax con nodi possibilità (chance) ................................................................................33

3. PROBLEMA DEL SODDISFACIMENTO DI VINCOLI (CSP) .......................................................................34

3.1. Algoritmo di propagazione di vincoli (inferenza) ........................................................................35

3.2. Algoritmi di ricerca .....................................................................................................................36

3.3. Alternanza di ricerca ed inferenza ..............................................................................................36

5.3.2. MAC (Maintaining Arc Consistency)..........................................................................................37

3.4. Ricerca locale ..............................................................................................................................37

3.4.1. CSP con miglioramento iterativo .........................................................................................37

3.4.2. Sotto problemi indipendenti ...............................................................................................37

4. AGENTI LOGICI ....................................................................................................................................39

4.1. Agenti basati sulla conoscenza ...................................................................................................39

4.2. Logica generale ...........................................................................................................................40

4.3. Logica Proposizionale (Booleana) ...............................................................................................40

4.4. Equivalenza, validità, soddisfacibilità .........................................................................................42

4.4.1. Equivalenza logica ...............................................................................................................42

4.4.2. Validità ................................................................................................................................42

4.4.3. Soddisfacibilità ....................................................................................................................42

4.5. Regole di inferenza .....................................................................................................................42

4.6. Dimostrazione dei teoremi .........................................................................................................42

4.6.2. Forward/backward chaining ...............................................................................................45

3

4.7. Model Checking ..........................................................................................................................46

4.7.1. DPLL ....................................................................................................................................47

4.7.2. WalkSAT ..............................................................................................................................47

5. LOGICA DEL PRIMO ORDINE ...............................................................................................................48

5.1. Sintassi e semantica ....................................................................................................................48

5.2. Ingegneria della conoscenza .......................................................................................................49

5.3. Inferenza nella logica del primo ordine .......................................................................................49

5.3.1. Unificazione ........................................................................................................................50

5.3.2. Forward Chaining ................................................................................................................50

5.3.3. Backward chaining ..............................................................................................................51

5.3.4. La programmazione logica ..................................................................................................52

5.3.5. Risoluzione ..........................................................................................................................53

6. RAPPRESENTAZIONE DELLA CONOSCENZA .........................................................................................54

6.1. Ingegneria ontologica .................................................................................................................54

6.2. Categorie ed oggetti....................................................................................................................55

6.3. Sistemi di ragionamento per categorie .......................................................................................55

6.3.1. Reti semantiche ..................................................................................................................55

6.3.2. Logiche descrittive ..............................................................................................................55

7. CONOSCENZA INCERTA E RAGIONAMENTO .......................................................................................56

7.1. Incertezza....................................................................................................................................56

7.2. Probabilità ..................................................................................................................................56

7.3. Sintassi e semantica ....................................................................................................................56

7.4. Inferenza .....................................................................................................................................57

7.5. Indipendenza e regola di Bayes...................................................................................................58

8. RAGIONAMENTO PROBABILISTICO ....................................................................................................58

8.1. Reti Bayesiane ............................................................................................................................58

8.2. Inferenza su reti bayesiane .........................................................................................................59

8.2.1. Algoritmo esatto .................................................................................................................59

8.2.2. Campionamento da una Rete vuota ....................................................................................59

8.2.3. Campionamento con Rigetto - basato su evidenze ..............................................................60

8.2.4. Pesatura di Verosimiglianza ................................................................................................60

8.2.5. MCMC, MonteCarlo x Markov Chains .................................................................................61

9. APPRENDIMENTO TRAMITE OSSERVAZIONE ......................................................................................61

9.1. Agenti di apprendimento ............................................................................................................61

9.2. Apprendimento induttivo ...........................................................................................................62

9.3. Apprendimento tramite alberi di decisione ................................................................................62

4

9.4. Valutare le prestazioni di apprendimento ..................................................................................63

9.5. Apprendimento statistico ...........................................................................................................63

9.5.1. Apprendimento bayesiano ..................................................................................................63

9.5.2. Approssimazione MAP ........................................................................................................63

9.5.3. Modelli bayesiani Naive ......................................................................................................64

9.5.4. Apprendimento con variabili nascoste ................................................................................64

9.5.5. Apprendimento basato sulle istanze ...................................................................................64

9.6. Apprendimento per rinforzo .......................................................................................................64

9.6.1. Problemi di decisione di Markov .........................................................................................65

9.6.2. Apprendimento per rinforzo passivo...................................................................................65

9.6.3. Apprendimento per rinforzo attivo .....................................................................................66

10. NATURAL LANGUAGE PROCESSING (NLP) .......................................................................................66

10.1. Language Modeling .................................................................................................................69

10.1.1. N-gram ................................................................................................................................69

10.2. Text Classification ...................................................................................................................70

10.2.1. Naive Bayes .........................................................................................................................71

10.3. Valutare performance classificatore di testo ..........................................................................72

10.4. Sentiment Analysis..................................................................................................................72

10.5. Logistic Regression ..................................................................................................................73

10.5.1. Binary Classification in Logistic Regression .........................................................................73

10.5.2. Naive Bayes vs Regression ..................................................................................................74

10.5.3. Multinomial Logistic regression ..........................................................................................74

10.6. Vector Semantics ...................................................................................................................75

10.6.1. Word Embedding ................................................................................................................75

10.7. POS (Part-of-speech) Tagging ..................................................................................................75

10.7.2. Classification Learning .........................................................................................................76

10.7.3. Hidden Markov Model ........................................................................................................76

10.7.4. Algoritmo di Viterbi.............................................................................................................78

10.7.5. Valutazione dei tag .............................................................................................................78

5

INTELLIGENZA ARTIFICIALE

INTRODUZIONE

- Agire come gli