Riassunto esame informatica I

Intelligenza artificiale

Esiste un’ampia classe di problemi di ragionamento che presentano caratteristiche comuni. Queste caratteristiche sono catturate ed astratte da sistemi detti production systems.

Production systems

• Collezione di stati: Uno stato è una situazione che può presentarsi nel dominio in esame. Esiste uno stato iniziale da cui il ragionamento (ricerca) comincia ed esiste uno stato desiderato cui si vuole arrivare, detto goal.
• Collezione di regole di produzione (o inferenziali): Una regola è un’operazione che può essere fatta nel mondo in esame allo scopo di modificarne lo stato corrente trasformandolo in un nuovo stato. Ogni regola può essere associata a precondizioni, cioè condizioni che devono essere verificate nello stato corrente affinché la regola sia applicabile.
• Strategia di controllo: È la logica che effettivamente risolve il problema. Ad ogni passo la strategia di controllo decide quale regola, tra quelle che hanno le precondizioni soddisfatte, attivare.

Problem space: È l’insieme di tutti i possibili stati in cui si può trovare il mondo. Concettualizzato come un grafo degli stati: i vertici corrispondono ad uno stato specifico. Un arco diretto da un vertice v ad un altro u indica che lo stato v può evolvere in u applicando una sola regola di produzione.

Anche il Prolog è un sistema di produzione: le sue regole, dette inferenziali, producono nuova conoscenza a partire dai fatti già noti.

Spesso i sistemi a regole di produzione sono detti sistemi esperti. L'idea è che le regole di produzione codificano la conoscenza di esperti umani, spesso acquisita con l’esperienza.

MYCIN: sistema esperto molto diffuso negli anni '70–'80, usato per diagnosticare infezioni del sangue e per suggerire i trattamenti necessari, usava circa 500 regole.

R1/XCON (anni '70) usato per configurare diversi modelli di computer, usava più di 2500 regole.

Limiti dei sistemi esperti

Definire le regole è difficile, non si ha garanzia di coprire il dominio di interesse; mantenimento della conoscenza; non imparano dall’esperienza.

Strategie di ricerca

Breadth-first

La strategia di controllo “esplora” il grafo degli stati al fine di trovare un cammino dallo stato iniziale al goal. Il risultato dell’esplorazione prende il nome di albero di ricerca. La strategia di controllo esplora in ampiezza (breadth-first) lo spazio degli stati (cioè il grafo): dallo stato corrente applica tutte le possibili regole, quindi passa allo stato “fratello”. La strategia è abbastanza furba da ricordarsi gli stati passati e quindi non li rigenera. Il goal è una foglia dell'albero.

Depth-first

Invece di espandere l’albero di ricerca in ampiezza, potremmo concentrarci su un cammino e approfondire quel cammino fino a quando arrivo alla soluzione oppure arrivo ad un vicolo cieco (non ci sono più regole applicabili). In questo caso torno all'ultimo punto di scelta ed esploro un nuovo cammino da lì in avanti (backtrack). Se il ramo che scelgo è infinito (cosa possibile in certi problemi), la ricerca non termina mai. Per evitare questo problema è necessario mantenere la lista dei nodi visitati.

Strategie informate: best-first

Esploriamo il grafo degli stati scegliendo di partire dallo stato che ci pare più promettente. Lo spazio di ricerca si divide in: stati già visitati (i cui figli sono stati generati applicando tutte le regole che soddisfano le precondizioni) e frontiera: stati ancora da visitare (espandere). La ricerca prosegue selezionando uno degli stati sulla frontiera: quello che ci pare più promettente secondo un determinato criterio, ovvero una funzione euristica. La funzione euristica applicata ad uno stato S stima quanto dista S dal goal, o in altri termini, quanto “costa” raggiungere il goal da S. La funzione euristica deve soddisfare almeno due condizioni: deve essere una stima ragionevole del costo reale e deve essere facile da calcolare. La ricerca best-first non garantisce di trovare la soluzione ottima, cioè quella di costo minimo.

Strategie informate: A*

Per trovare la soluzione ottima, la strategia di ricerca deve anche guardarsi alle spalle, ovvero tenere traccia del costo che è già stato speso per arrivare ad un determinato stato. A* è un algoritmo di ricerca informata la cui funzione euristica è costituita da due parti: f(n) = g(n) + h(n). h(n) è il costo per raggiungere il goal dallo stato n; g(n) è il costo già speso per raggiungere n dallo stato iniziale.

Rappresentazione delle informazioni

Unicode

Codifica immagini: immagine suddivisa da una griglia formata da linee a distanza costante; ogni quadrato derivante da tale suddivisione viene chiamato pixel; può essere codificato in binario con la convenzione che 0 rappresenta un pixel bianco e 1 rappresenta un pixel nero; i pixel si leggono da sinistra a destra, e dal basso verso l’alto; non sempre il contorno della figura coincide con le linee della griglia: digitalizzando un’immagine si ha sempre un’approssimazione dell’immagine stessa; per avere un’immagine più fedele aumentiamo la risoluzione, cioè il numero dei pixel; la rappresentazione di un’immagine mediante la codifica dei pixel viene chiamata codifica bitmap. Con un solo bit per pixel si possono codificare solo due colori (tipicamente bianco e nero), quindi per codificare più informazioni, dobbiamo usare più bit. Per associare una rappresentazione binaria a ogni possibile colore di un pixel si usa Truecolor.