Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
EN11 9 11 913 134 11 9 11 913 134 41 3 1 3 412 12 1 3 12 1 3 8 127 5 7 56 68 8 7 5 7 56 6813 2 14 13 2 1410 10 13 2 14 13 2 1410 10
E se volessimo anche minimizzare il numero di mosse? Sarebbe sufficiente fornire una quinta regola al SF: "Detta S una soluzione, trova la soluzione S' tale che lunghezza (S') < lunghezza (S)". Tale regola formalizza il concetto, che noi evidentemente consideriamo importante, di lunghezza minima. Da notare che ogni sequenza di mosse non è altro che un vettore: N-O-S-O-S-E etc., e ci interessa quello di lunghezza minima. Va detto anche che questo sistema nella sua forma basilare non è decidibile, dal momento che i cammini sono in numero infinito. Il numero degli stati è finito, ma la macchina passerà probabilmente più volte per delle configurazioni uguali e quindi potrebbe almeno in via teorica non raggiungere mai la soluzione. La non decidibilità è poi garantita quando lo.
spazio degli stati è infi-nito. Come detto, si sopperisce alla non decidibilità di un sistema ponendo un limite massimo alla ricerca. Ricordiamo che per produrre un funzionamento utile, ogni SF dovrebbe godere di 3 proprietà: coerenza, completezza e decidibilità. UNA TECNICA DI RAPPRESENTAZIONE ALTERNATIVA: PER RIDUZIONE A SOTTOPROBLEMI. In questa tecnica, rappresentiamo un problema e la sua decomposizione in sottoproblemi. In particolare, viene descritto il modo in cui le soluzioni dei sottoproblemi contribuiscono a determinare la soluzione del problema padre. Un esempio classico di rappresentazione per riduzione a sottoproblemi è la ricorsione: un problema viene rappresentato in termini dello stesso problema, posto in una forma più semplice. Così si ha ad esempio per il fattoriale: n! = n*(n-1)! . Non rappresentiamo più gli stati, ma suddividiamo il problema in problemi più semplici; se questi ultimi sono dello stessotipo del problema origine, parliamo di ricorsione. In ogni ca-so, dobbiamo correlare l'ottenimento della soluzione del problema grande a quello dei sottoproble-mi. Questa rappresentazione è meno intuitiva e più sofisticata della SSR. Un esempio: gli scacchi. Le macchine odierne che giocano a scacchi utilizzano una rappresentazione per riduzione a sottoproblemi, o al massimo una rappresentazione mista, piuttosto che una SSR. Perché diciamo questo? Se volessimo realizzare una rappresentazione SSR di una partita a scacchi, dovremo formalizzare i concetti (problem formalization): scacchiera, pezzi e loro dislocazione iniziale, movimenti possibili, pezzi mangiati, partita vinta o patta. Abbiamo dato l'informazione minima grazie alla quale il sistema è teoricamente in grado di ricavare le sequenze di mosse che portano a dare scacco matto al re avversario (supponiamo per semplicità che la macchina giochi contro sé stessa). Ciò deveperò avvenire attraverso una ricerca esaustiva nello spazio degli stati: per ogni mossa, la macchina considera tutte le possibili repliche; quindi, tutte le possibili repliche ad ogni replica, e via dicendo. C'è la necessità di avere una memoria praticamente infinita, dato che pur imponendo un limite al 'look ahead', diciamo di una ventina di mosse (dalla configurazione attuale ipotizza le repliche dell'avversario, poi tutte le repliche per ogni replica, e così via per 20 mosse) il numero di combinazioni da memorizzare è inconcepibilmente grande (si dice che le combinazioni 'esplodono'). I migliori giocatori umani di scacchi hanno un look-ahead di 20 e anche più mosse, ma essi implicitamente 'potano' l'albero degli stati considerando solo le repliche più probabili sulla base dell'esperienza, della logica e della conoscenza dell'avversario, e sono costretti a tale 'potatura'.
oltre che dai limiti della loro memoria, anche dal fatto che generalmente è imposto un tempo massimo entro il quale rispondere alla mossa avversaria. L'albero che essi creano nella loro mente viene cioè visitato più in profondità che in ampiezza. È ovvio che nel caso del gioco degli scacchi, se vogliamo che la macchina sia competitiva, la conoscenza di base non è sufficiente: dobbiamo arricchirla con la strategia di gioco. La si potrebbe acquisire (e questo è proprio ciò che avviene in pratica) intervistando scacchisti particolarmente bravi e formalizzando le loro tecniche di gioco. La strategia consiste in generale nel porsi un certo numero di sotto-obiettivi che tengono conto fra l'altro del valore dei pezzi (es.: ridurre il numero dei pedoni avversari, attaccare le torri, proteggere il re etc.), invece di considerare tutte le possibili alternative. Infine, avremo ottenuto una macchina che, avendo recepito la conoscenza dell'esperto.è in grado di giocare la suo stesso livello strategico. Ciò permette anche di considerare un numero di combinazioni significativamente minore del caso discusso prima. Infatti, la macchina non prenderà in esame tutte le possibili repliche ad ogni mossa, ma solo quelle significative dal punto di vista della strategia. Per conseguenza, più conoscenza diamo alla macchina, meno quest’ultima deve lavorare durante il processo inferenziale. In questo consiste appunto la rappresentazione per riduzione a sottoproblemi (PR). Mentre in una rappresentazione SSR il blocco control strategy si limiterebbe a produrre tutti gli stati ricavabili applicando le varie mosse alla configurazione attuale, e lo stesso con gli stati così ottenuti, in una rappresentazione PR selezionerebbe solo un ristretto numero di alternative sulla base delle strategie di gioco delle quali la macchina è stata informata. Anche il dynamic database ne risulterà avvantaggiato,
perché si riduce sensibilmente il quantitativo di stati da memorizzare. Quindi, il problema generale di vincere la partita a scacchi si ridimensiona in un ri-stretto numero di sotto-problemi cui corrispondono uno o pochi sotto-obiettivi, e ciascun sotto-problema può essere risolto nella rappresentazione SSR o a sua volta ridotto a sottoproblemi più semplici. Così facendo stiamo apportando una modifica concettuale notevole al procedimento di risoluzione: ci allontaniamo sempre più dalla ‘conoscenza zero’ (minima, quella della SSR) e cominciamo a travasare sempre maggiore conoscenza dall’esterno. All’estremità opposta di questo procedimento abbiamo infatti l’algoritmo: fissata la configurazione iniziale, un algoritmo dice in maniera deterministica quale mossa successiva effettuare in conseguenza di ogni configurazione possibile. A questa situazione corrisponde la conoscenza massima del problema. Abbiamo quindi due
estremi opposti: SSR (stato iniziale e finale, regole) ed algorit-mo; in mezzo c'è la rappresentazione per riduzione a sottoproblemi. Più conoscenza aggiungiamo, più ci avviciniamo ad un algoritmo risolutivo, tanto meno lavora la macchina e tanto più impegnativo è il lavoro del programmatore. Da notare che maggiori sono le prestazioni del calcolatore, più è realistico ed opportuno adottare una rappresentazione a conoscenza minima, altrimenti, con elaboratori dai modesti dati di targa, la soluzione algoritmica diventa l'unica strada percorribile. Ma non è solo questione di tecnologia. C'è un numero non irrilevante di situazioni nelle quali la conoscenza algoritmica è scarsa o nulla, o troppo complessa da gestire (ad esempio: riconoscimento vocale o di caratteri) e quindi non rimane che rifarsi alle tecniche di AI. Non sempre quindi quelle tecniche che si affidano interamente alla macchina.Costituiscono solo una alternativa elegante e veloce ai tradizionali algoritmi, ma per certi problemi di rilevanza pratica rappresentano l'unica alternativa possibile. Altro esempio: integrazione simbolica. La tecnica SSR è la più semplice da implementare: formalizzeremo il problema definendo il legame tra funzione e sua primitiva e introducendo le regole di base del calcolo analitico (differenziazione, derivazione). Partendo dalle regole di derivazione, e definito il concetto di primitiva (per una funzione f, è quella funzione g tale che g' = f), avremo precisato tutto ciò che occorre per risolvere il problema dell'integrazione simbolica. La ricerca esaustiva tuttavia darebbe luogo a tempi di calcolo esasperanti. È qui che entra in gioco la conoscenza PR. In pratica, si ricorre alle famose regole di integrazione (per sostituzione, per parti, formule ricorrenti) che consentono di individuare determinati passi intermedi nella risoluzione dell'integrale.
Ciò equivale ad arricchire il sistema mediante la conoscenza delle strategie applicabili; da notare che ciò riduce il tempo di elaborazione, ma dal punto di vista concettuale non aggiunge nessuna informazione sul problema dell'integrazione.
Volendo applicare lo schema iniziale diremo che:
- il database contiene lo stato di avanzamento dell'integrazione (l'attuale passo intermedio di integrazione);
- la formalizzazione del problema contiene le regole di integrazione, che si uniscono a quelle del calcolo analitico;
- il sistema di controllo analizza il database e decide se è applicabile una delle regole di integrazione; in caso affermativo, determina i nuovi sottoproblemi di integrazione da risolvere.
Un altro esempio ci permetterà di sottolineare meglio la differenza fra le due rappresentazioni di SF finora viste: il problema del COMMESSO VIAGGIATORE. Una rete via Bria completamente connessa collega fra di loro delle città (5).
nell'implementazione di un algoritmo efficiente per risolvere il problema del percorso minimo. L'approccio AI con la rappresentazione SSR si concentra invece sulla modellazione del problema utilizzando una struttura dati adatta e sull'utilizzo di tecniche di intelligenza artificiale per trovare una soluzione approssimata o ottimale.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
