Appunti di Fondamenti di Intelligenza artificiale

Fondamenti di Intelligenza Artificiale

Cosimo Botticelli

2021

Contents

1 Introduzione 4

1.1 Intelligenza Artificiale: Perché? . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.1 Obiettivi di apprendimento . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Definizione di Intelligenza Artificiale . . . . . . . . . . . . . . . . . . . . . 6

1.2.1 Pensare umanamente . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.2 Pensare razionalmente . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2.3 Agire Umanamente . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2.4 Agire Razionalmente . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3 Agenti Intelligenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.1 Come si comporta un Agente Intelligente . . . . . . . . . . . . . . . 9

1.3.2 Valutare un Agente Intelligente . . . . . . . . . . . . . . . . . . . . 10

1.4 Ambienti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4.1 Formulazione P.E.A.S. . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5 Struttura degli agenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.6 Agenti davvero intelligenti . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.6.1 Agenti reattivi semplici . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.6.2 Agenti reattivi basati su Modello . . . . . . . . . . . . . . . . . . . 12

1.6.3 Agenti basati su Obiettivi . . . . . . . . . . . . . . . . . . . . . . . 13

1.6.4 Agenti basati sull’utilità . . . . . . . . . . . . . . . . . . . . . . . . 13

1.6.5 Agenti capaci di apprendere . . . . . . . . . . . . . . . . . . . . . . 13

2 Ricerca 14

2.1 Risoluzione di problemi con la ricerca . . . . . . . . . . . . . . . . . . . . . 15

2.1.1 Agenti risolutori di problemi . . . . . . . . . . . . . . . . . . . . . . 15

2.1.2 La Ricerca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.1.3 Problemi ben definiti e soluzioni . . . . . . . . . . . . . . . . . . . . 16

2.2 Ricerca non informata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2.1 Valutare un algoritmo di ricerca . . . . . . . . . . . . . . . . . . . . 17

2.2.2 Strategie di ricerca non informata . . . . . . . . . . . . . . . . . . . 18

2.3 Ricerca Informata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.1 Ricerca best-first greedy . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3.2 Ricerca A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3.3 Beam Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.4 Iterative Deepening A* (IDA*) . . . . . . . . . . . . . . . . . . . . 21

1

2.3.5 Ricerca best-first iterativa . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.6 Simplified Memory Bounded A* (SMA*) . . . . . . . . . . . . . . . 22

2.3.7 La lezione da apprendere . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4 Algoritmi di Ricerca Locale . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.4.1 L’algoritmo Hill-Climbing . . . . . . . . . . . . . . . . . . . . . . . 24

2.4.2 Algoritmo Simulated Annealing . . . . . . . . . . . . . . . . . . . . 24

2.4.3 Algoritmo Local Beam . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4.4 Local Beam Stocastica . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.5 Algoritmi Genetici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.5.1 Teoria dell’Evoluzione e Ottimizzazione . . . . . . . . . . . . . . . . 26

2.5.2 Algoritmi Genetici . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.5.3 Punti di forza. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.5.4 Ammissibilità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.5.5 Criteri di arresto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.5.6 Inizializzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.5.7 Vincoli popolazione . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.6 Algoritmi Genetici Multi-Obiettivo . . . . . . . . . . . . . . . . . . . . . . 31

2.6.1 Dominanza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.6.2 Struttura del fronte di Pareto . . . . . . . . . . . . . . . . . . . . . 32

2.6.3 Risoluzione tramite Hill Climbing . . . . . . . . . . . . . . . . . . . 33

2.6.4 Risoluzione tramite Algoritmi Genetici . . . . . . . . . . . . . . . . 33

2.6.5 Algoritmi Genetici: Conclusioni . . . . . . . . . . . . . . . . . . . . 34

2.7 Ricerca con Avversari: Teoria dei Giochi . . . . . . . . . . . . . . . . . . . 36

2.7.1 Ambienti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.7.2 Una definizione più formale . . . . . . . . . . . . . . . . . . . . . . 36

2.7.3 Decisioni Ottime . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.7.4 Nash e il Dilemma del Prigioniero . . . . . . . . . . . . . . . . . . . 37

2.7.5 Decisioni ottime, valori e decisioni minmax . . . . . . . . . . . . . . 38

2.7.6 Algoritmo Minmax con potatura Alfa-Beta . . . . . . . . . . . . . . 38

2.7.7 Ulteriori miglioramenti . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.7.8 Giochi stocastici . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.7.9 Giochi parzialmente osservabili . . . . . . . . . . . . . . . . . . . . 40

3 Apprendimento 41

3.1 Teoria dell’Apprendimento: Agenti capaci di apprendere . . . . . . . . . . 42

3.1.1 Errore, Bias e Varianza . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.2 Dati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.2.1 Tipologie di dati . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.3 Data Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.3.1 Data Cleaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.3.2 Feature scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.3.3 Feature selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.3.4 Data balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.4 Classificazione e Classificatori . . . . . . . . . . . . . . . . . . . . . . . . . 46

2

3.4.1 Naive Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.4.2 Alberi decisionali . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.4.3 Training Set e Test Set . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.4.4 Metriche di valutazione . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.5 Regressione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.5.1 Regressione lineare singola . . . . . . . . . . . . . . . . . . . . . . . 49

3.5.2 Regressione lineare multipla . . . . . . . . . . . . . . . . . . . . . . 49

3.6 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.6.1 Misure di similarità . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.6.2 Algoritmi per problemi di raggruppamento . . . . . . . . . . . . . . 51

3.6.3 Valutazione dei risultati dei problemi di raggruppamento . . . . . . 52

3

Chapter 1

Introduzione 4

”Any sufficiently advanced technology is indistinguishable

from magic.” – Arthur C. Clarke

1.1 Intelligenza Artificiale: Perché?

Nonostante talvolta possa effettivamente sembrare magia, soprattutto quando prendiamo

in considerazione tecnologie moderne come reti neurali e machine learning, e strumenti

come assistenti vocali e Google Maps, l’intelligenza artificiale, alla base, altro non è che

una specifica tipologia di algoritmi, seppur con una particolare filosofia dietro.

Il motivo per cui oggi è cosı̀ pervasiva e per cui cosı̀ tanti investimenti vanno nei

suoi confronti è che è capace di risolvere problemi altresı̀ molto complessi, e talvolta

sostituire gli umani in alcuni compiti. Tuttavia questi algoritmi non sono autonomi,

e hanno comunque bisogno di un buon progettista per funzionare a dovere. Possiamo

motivare l’hype dietro questa tecnologia con cinque punti:

1. Ottimizzazione di risorse.

2. Necessità di velocizzare l’apprendimento nell’esecuzione di task.

3. Risoluzione di problemi umanamente complessi.

4. Marketing.

5. Curiosità.

1.1.1 Obiettivi di apprendimento

Questo corso si divide in due macroargomenti, che hanno tuttavia alla base il semplice

concetto di agente intelligente.

I due macroargomenti e i loro relativi sottoargomenti sono:

• Risoluzione di problemi con la ricerca:

– Strategie di ricerca informata e non-informata.

– Ricerca locale, ottimizzazione.

– Ricerca con avversari.

• Risoluzione di problemi tramite l’apprendimento:

– Teoria dell’apprendimento.

– Apprendimento supervisionato.

– Apprendimento non supervisionato.

5

1.2 Definizione di Intelligenza Artificiale

Per migliaia di anni siamo stati, come specie umana, affascinati dalla nostra stessa intel-

ligenza e abbiamo cercato di comprenderla.

L’intelligenza artificiale fa un ulteriore passo e cerca di costruire entità intelligenti.

La definizione di Intelligenza Artificiale non è banale, e infatti ce ne sono diverse e

composte da vari aspetti. Noi definiamo quattro caratteristiche che un Agente deve avere

per essere definito Intelligente.

1. Pensare umanamente. Far sı̀ che i computer pensino ed eseguono attività co-

munemente associate al pensiero umano come l’apprendimento, il processo deci-

sionale, etc.

2. Pensare razionalmente. Lo studio dei processi di calcolo che rendono possibile

percepire, ragionare, etc.

3. Agire umanamente. L’arte di creare macchine che eseguono azioni che, quando

eseguite da esseri umani, richiedono intelligenza, o comunque a cui, al momento, le

persone sono più brave.

4. Agire razionalmente. Forse aspetto più importante, riguarda un comportamento

intelligente e dotato di criterio.

Andiamo a vedere più nello specifico i vari aspetti.

1.2.1 Pensare umanamente

Quando diciamo che un determinato programma ragiona come un essere umano, dobbiamo

innanzitutto determinare come noi pensiamo, e capire cioè i meccanismi interni del cervello

umano. Abbiamo tre modi per modellare questi meccanismi interni:

• Introspezione. Atto della coscienza che consiste nell’osservazione diretta e nell’analisi

dell’interiorità rappresentata da pensieri, pulsioni, desideri etc. La modellazione, in

questo caso, consiste nel catturare ”al volo” i nostri pensieri mentre scorrono.

• Sperimentazione psicologica. È la branca della psicologia che tenta di applicare

il metodo sperimentale all’indagine dei processi cognitivi del cervello. La model-

lazione in questo caso consiste nell’osservazione di pensieri, pulsioni, stimoli etc. di

una persona in azione.

• Imaging celebrale. Consiste nella mappatura, diretta o indiretta, della strut-

tura e delle funzioni del sistema nervoso. La modellazione in questo caso consiste

nell’osservazione del cervello in azione, cosı̀ da poterne intuire i meccanismi nervosi

interni e trarne conclusioni. 6

C’è ora da specificare l’importanza, all’interno dello studio dell’intelligenza artificiale,

della psicologia e delle neuroscienze: la prima si chiede come agiscono e pensano

esseri umani ed animali, mentre le neuroscienze si pongono domande sui meccanismi che

permettono l’elaborazione di informazioni da parte del cervello.

Secondo Craik, un Agente Intelligente possiede tre requisiti fondamentali:

1. Lo stimolo esterno deve essere tradotto in una rappresentazione interna.

2. Tale rappresentazione interna deve essere manipolata da processi cognitivi per ot-

tenere nuove rappresentazioni interne.

3. Tali nuove rappresentazioni devono a loro volta essere trasformate in azioni.

“Se l’organismo porta nella sua testa un ‘modello in scala’ della realtà

esterna e delle proprie possibili azioni sarà in grado di provare varie

alternative, decidere quali di esse sia la migliore, reagire a situazioni

future prima che si manifestino, utilizzare la conoscenza di eventi passati

per gestire quelli presenti e futuri, e sotto ogni aspetto reagire in modo

molto più ricco, affidabile e competente alle emergenze che si troverà a

fronteggiare.” – K. J. W. Craik

Questa è probabilmente la miglior definizione di Intelligenza Artificiale che mai avremo,

nonostante sia stata formulata quasi un secolo fa.

Un altro importante contributo di Craik fu quello di fondare le scienze cognitive, che

ad oggi ci danno importanti indizi sul funzionamento del sistema nervoso e in particolare

del cervello. Sappiamo che alla base del pensiero ci sono i neuroni, che comunicano fra

loro tramite punti di congiunzione detti sinapsi, e che oltre a collegamenti immediati

possono anche cambiare permanentemente la loro struttura, dando cosı̀ quella che ad oggi

riteniamo essere la base dell’apprendimento.

Un’altra importante nozione è la potenza del cervello. Con le conoscenze odierne

sappiamo che, nonostante gli enormi progressi tecnologici che abbiamo fatto, un cervello

umano ha una capacità di memorizzazione e velocità di computazione maggiore rispetto

agli odierni supercomputer. Ovviamente il raggiungimento di questa soglia non vuol dire

automaticamente la nascita della coscienza artificiale, in quanto è inutile per un computer

17

eseguire 10 operazioni al secondo se queste operazioni non sono ben finalizzate allo scopo

di pensare e agire razionalmente. 7

1.2.2 Pensare razionalmente

Pensare razionalmente vuol dire usare in maniera corretta la logica. Si ritiene che suddetta

disciplina abbia avuto origine con i sillogismi aristotelici, ossia i primi tentativi di

codificare formalmente il pensiero corretto.

Questo col tempo è sfociato nel logicismo. Questa disciplina sostiene che è necessario

partire da enunciati logici per costruire sistemi intelligenti e razionali. Tuttavia sorgono

due importanti problemi:

1. Non è facile esprimere una conoscenza non formale (ossia il mondo reale, dominato

anche da un certo grado di caos e soggettività) in termini formali.

2. Ancora più importante, è diverso definire un enunciato in maniera logica ed agire

in maniera da soddisfare quella condizione. Per esempio leggere un buon libro

riguardante l’Intelligenza Artificiale non equivale automaticamente al superamento

del relativo esame.

Con un approccio del genere, anche problemi con poche centinaia di variabili possono

risultare impossibili da risolvere, in quanto potrebbero saturare completamente le risorse

computazionali disponibili. Abbiamo pertanto bisogno di una maniera per navigare queste

infinite possibilità senza necessariamente esplorarle tutte. Questa rappresenta una sfida

aperta nel campo dell’Intelligenza Artificiale.

1.2.3 Agire Umanamente

Un modo per verificare l’agire umano di una macchina potrebbe essere il test di Turing,

conosciuto anche come the Imitation Game.

Turing ebbe numerose critiche, di natura più o meno sensata, durante la sua vita

riguardo questo test.

Al contrario di molte critiche di natura filosofica e regligiosa, una limitazione piuttosto

concreta venne proposta da Kurt Gödel. È proprio il teorema di Gödel a dimostrare

che in qualsiasi sistema logico sufficientemente potente si possono formulare proposizioni

che non è possibile provare nè tantomeno smentire, all’interno del sistema, derivando cosı̀

una possibilità di incoerenza all’interno dello stesso sistema logico.

Lo stesso Turing ottenne risultati simili. Tuttavia, vale la pena sottolineare che le

stesse limitazioni sottolineate dal teorema di Gödel potrebbero valere anche per l’intelletto

umano. Non esiste, ad oggi, nessuna dimostrazione a proposito.

1.2.4 Agire Razionalmente

Questo è forse il più importante dei quattro punti. Un agente per essere tale deve fare

qualcosa, e quindi gli algoritmi, per definizione, sono agenti. Da un Agente Intelligente

tuttavia si richiede qualcosa in più, ossia che egli sia capace di agire autonomamente,

imparare dal passato per migliorare nel futuro.

8

Un agente razionale agisce in maniera da ottenere il miglior risultato possibile, ma che

in situazioni di incertezza riesce comunque a prendere una decisione in base al miglior

risultato atteso basandosi sulle sue conoscenze pregresse.

Quest’ultimo punto in particolare va in contrasto con la logica classica in quanto

prende in considerazione un certo grado di caos e approssimazione. L’agire razionalmente

include i tre punti precedenti nonché l’idea aggiuntiva di adattarsi al contesto, facendo

la scelta migliore fra le disponibili basandosi sulla conoscenza pregressa.

1.3 Agenti Intelligenti

Un agente è qualsiasi cosa possa essere vista come un sistema che percepisce l’ambiente

in cui si trova tramite dei sensori ed agisce su di esso tramite degli attuatori.

Figure 1.1: Rappresentazione di un agente relativamente all’ambiente in cui si trova.

1.3.1 Come si comporta un Agente Intelligente

Due importanti definizioni che ci servono per capire cosa è un agente intelligente e come

si comporta:

1. Percezione: Insieme degli input percettivi in un dato istante.

2. Sequenza percettiva: Storia completa di tutto ciò che l’agente ha percepito nella

sua esistenza.

La scelta di un’azione da parte di un agente può essere determinata da ciò che ha

percepito (ma non necessariamente lo sarà) ma sicuramente non può essere determinata

da ciò che non ha percepito. Questa è un’importante differenza fra un umano e un agente

9

software, in quanto l’umano può comportarsi in modo imprevedibile, facendo cose non

necessariamente collegate allo storico delle sue percezioni (pensiamo a una persona che

agisce da ubriaca).

Se volessimo dirla in termini prettamente matematici, allora il comportamento di

un agente è descritto da una funzione agente, che descrive la corrispondenza fra una

qualsiasi sequenza percettiva e una specifica azione. Da un punto di vista pratico la

funzione agente è implementata tramite uno specifico programma agente.

Questa relazione potrebbe essere per esempio espressa tramite una tabella. Riusciamo

con non troppe difficoltà a intuire che anche con pochi parametri, questa tabella potrebbe

raggiungere d