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 intelligenza 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 eseguano attività comunemente associate al pensiero umano come l’apprendimento, il processo decisionale, 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 modellazione in questo caso consiste nell’osservazione di pensieri, pulsioni, stimoli etc. di una persona in azione.
• Imaging cerebrale. Consiste nella mappatura, diretta o indiretta, della struttura 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 ottenere 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 religiosa, 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