InfoSpiders
Un ambiente di informazione distribuita come Internet è un
buon esempio della complessità che ci aspettiamo da un sistema
simile alla vita. La grande diffusione del Web e della posta
elettronica ha creato una serie di problemi nella ricerca delle
informazioni, che i ricercatori di Intelligenza Artificiale hanno
affrontato con discreto successo tramite tecniche basate su
agenti che automatizzano operazioni tediose e facilitano la
ricerca. Tuttavia c’è ancora bisogno di tools che si
adattino sia alle preferenze dell’utente sia ai cambiamenti
dell’ambiente. I principi della Vita Artificiale possono
essere usati per creare degli agenti localizzati e autonomi. Un
agente localizzato è un agente il cui comportamento è
strettamente correlato con un ambiente esterno. L’ambiente
non può essere previsto con certezza dall’agente sia perché
ha una natura dinamica, che cambia nello spazio e nel tempo,
sia perché l’agente percepisce tramite “apparati
sensori” che possono essere imprecisi, rumorosi, incompleti
o inaffidabili. Un agente autonomo è un sistema che esegue,
per conto dell’utente, alcune operazioni la cui soluzione
non è specificata a priori. L’agente deve autonomamente
fare delle scelte in base al contesto, quindi deve imparare
alcune regolarità dell’ambiente e adattare il suo
comportamento in modo da eseguire le sue operazioni con successo.
Questo modo di agire è in tutto simile a quello degli esseri
viventi e rappresenta l’obiettivo desiderabile per una
futura generazione di agenti autonomi, intelligenti, distribuiti,
adattivi e artificiali.
Prima di descrivere il funzionamento degli agenti chiamati
infospider parliamo brevemente del funzionamento dei motori di
ricerca e degli agenti basati sull’Intelligenza Artificiale
e vediamo i loro limiti.
Motori di Ricerca
I motori di ricerca sono lo strumento più usato per trovare
informazioni nel Web. Il loro funzionamento consiste nel
processare una collezione di documenti una volta per tutte,
producendo un indice e permettendo l’accesso ai documenti
attraverso un gran numero di domande (queries) che accedono allo
stesso indice. L’indice è sostanzialmente un file che mappa
ogni parola nella collezione e gli associa un insieme di
documenti che contengono quella parola. La limitazione di questo
approccio è che si assume che la collezione sia statica mentre
il Web è altamente dinamico, in quanto ogni giorno migliaia di
documenti vengono aggiunti, modificati, cancellati o spostati. Il
risultato è che gli indici sono incompleti (cioè non contengono
tutte le pagine del Web) e inesatti (ad esempio contengono link a
documenti rimossi o spostati).Gli indici dei motori di ricerca
devono essere aggiornati manualmente visitando periodicamente le
pagine. Un recente studio ha mostrato che solo il 34% delle
pagine è inserito nei principali motori di ricerca, mentre una
parte consistente (il 5%) dei link si riferisce a pagine rimosse.
Information Agent
Gli agenti autonomi o intelligenti sono considerati da molti
uno strumento utile per diminuire l’interazione uomo-computer
necessaria a causa del crescente numero di documenti disponibili
online. La maggior parte di loro tuttavia soffre di una comune
limitazione: fanno affidamento sui motori di ricerca. Infatti
molti di essi non fanno altro che sottoporre queries
contemporaneamente a molti motori di ricerca, perciò essi non
superano i limiti di questi ultimi, ma utilizzandone più di uno
simultaneamente possono migliorare i risultati di una ricerca.
Questa tecnica è chiamata metasearch e viene usata ad esempio in
alcuni siti che usano agenti per cercare home page (Ahoy) o
articoli (CiteSeer, Web Find). Un altro tipo di agenti assiste l’utente
durante la navigazione ad esempio memorizzando le preferenze dell’utente
e suggerendogli in tempo reale quale link seguire tra le pagine
vicine. Tuttavia questi agenti hanno bisogno della supervisione
dell’utente perciò non operano in maniera autonoma.
InfoSpiders
Vediamo ora come un approccio ispirato alla Vita Artificiale
che può superare i limiti delle tecniche che abbiamo descritto
sopra. Innanzitutto diciamo che vengono utilizzati agenti,
chiamati InfoSpiders, che sono autonomi, online, localizzati e
personal browser e che il problema viene diviso in sottoproblemi
più semplici. L’idea è quella di utilizzare una
popolazione di siffatti agenti (a ognuno dei quali è associato
un semplice sottoproblema) che “vivono” navigando
online tra i documenti, prendendo decisioni autonome su quale
link seguire e adattando la propria strategia al contesto dell’ambiente
e alle preferenze dell’utente. Ad ogni documento è
associata, in base alla sua rilevanza rispetto al problema, una
certa energia, che rappresenta il “cibo” necessario
agli InfoSpiders per sopravvivere. Infine sia ogni singolo agente
sia la popolazione devono evolversi. Una parte importante del
sistema è l’uso del feedback di rilevanza da parte dell’utente:
questo può cioè stimare la rilevanza di alcuni dei documenti
visitati dagli InfoSpiders in quel momento e la sua stima
influenza il comportamento degli agenti in quanto cambia la
distribuzione dell’energia nell’ambiente.
Vediamo ora l’algoritmo usato dagli InfoSpiders:
Algoritmo:
Inizializza p0 agenti, ognuno con energia E=T/2
While ci sono agenti vivi:
1. scegli un link dal documento corrente
2. vai al nuovo documento D
3. Ea <- Ea – c(D) + e(D)
4. Q-learn con segnale di rinforzo e(d)
5. Selezione:
if (Ea>=T)
a’<- muta(ricombina(clone(a)))
Ea’<-Ea/2
Ea<-Ea/2
else if (Ea<=0)
Uccidi(a)
End
End
Processa l’opzionale
feedback di rilevanza dell’utente
End
L’utente deve inizialmente fornire un insieme di parole
chiave e una lista punti di inizio, sotto forma di file bookmark.
Questa lista può essere facilmente ottenuta consultando un
motore di ricerca. Ogni agente viene posizionato in uno dei
documenti della lista di partenza e gli viene dato un
comportamento casuale (che dipende dalla rappresentazione dell’agente)
e una riserva iniziale di energia.
Nel passo (1), un agente stima la rilevanza dei
documenti vicini (cioè quelli raggiungibili tramite un hyperlink
dal documento corrente) analizzando il testo del documento
dove è attualmente situato. In base alla stima appena
eseguita, nel passo (2) l’agente si muove scegliendo uno dei
link dal documento corrente. Nel passo (3) l’energia dell’agente
viene aggiornata: se infatti visita documenti che sono ritenuti
interessanti viene ricompensato con energia. L’energia è
necessaria all’agente per vivere, cioè per continuare a
navigare e cercare documenti, e se l’agente la esaurisce
muore. La funzione e() viene usata da un agente per valutare la
rilevanza dei documenti.
Ci sono due “sorgenti” di energia nel sistema. Se un
documento D è stato precedentemente visitato e stimato dall’utente,
la stima dell’utente è usata per calcolare e(D) che può
essere maggiore o minore di zero. Se invece un documento non è
stato ancora visitato la sua rilevanza deve essere stimata per
calcolare e(D). Se D è stato precedentemente visitato, ma non
stimato, e(D)=0 perché questa risorsa è stata consumata. Questo
meccanismo è implementato tramite una cache che velocizza il
processo minimizzando il trasferimento di documenti duplicati.
Per muoversi tra i documenti gli agenti devono pagare un costo c()
in termini di energia. Il costo può essere calcolato in base
alle risorse usate, alla lentezza nel caricare un documento, alla
grandezza del documento. Potremmo anche considerare per semplicità
certo costo costante per visitare un documento online e un costo
più piccolo per accedere alla cache. In questo modo
comportamenti costanti come andare avanti e indietro tra due
documenti vengono scoraggiati. (4)L’agente si adatta durante
la sua vita secondo una tecnica chiamata Q-Learning che è un
processo adattativo che gli permette di modificare il suo
comportamento in base alle esperienze precedenti imparando a
predire quali sono i migliori link da seguire.
Nel passo (5) l’agente può essere ucciso oppure essere
selezionato per la riproduzione. Nel secondo caso i figli vengono
ricombinati usando due tipi di crossover: nel crossover locale
un agente può essere ricombinato solo con un altro che si
trova nello stesso documento, se ce n’è; nel panmictic
crossover un agente può essere ricombinato con un qualsiasi
altro della popolazione e in questo caso la selezione avviene a
caso. I figli vengono poi mutati in modo da fornire le variazioni
necessarie per l’evoluzione.
Infine l’utente manda al sistema il feedback di rilevanza.
Questo processo è opzionale e può avvenire senza interazioni
dirette con gli agenti. L’utente può stimare ogni documento
D stimato con un feedback F(D) che può essere –1 , 0 , 1 .
Tutte le parole nel documento vengono stimate automaticamente
attraverso l’aggiornamento di una “feedback list”
delle parole incontrate. A ogni parola, k, nella lista è
associato un numero intero wk che è inizializzato a zero e
aggiornato ogni volta che il documento viene stimato dall’utente:
qualunque k appartenente a D: wk<- wk + F(D).
Architettura
di un agente
Rappresentazione
adattativa di un agente
Selezione
dell'azione
Stima
e feedback di rilevanza
Riproduzione