d x,f = tf x,j log df j

Ri ardo Pietru i

20/6/2006

Indi e

1 IntelligentWeb & Personalized Sear h 2

1.1 Information Overload. . . 2

1.2 Motori diri er a . . . 2

1.2.1 InvertedIndex . . . 3

1.2.2 Mat hingVe tor spa e model . . . 3

1.2.3 Google . . . 3

1.3 PersonalizedSear h . . . 3

1.3.1 GoogleAlerts . . . 3

1.3.2 Appro i . . . 4

2 Text Categorization 4 2.1 Algoritmodiapprendimento Ro hio . . . 4

2.2 Algoritmodiapprendimento Nearest-Neighbor. . . 5

2.3 Algoritmodiapprendimento Bayesiano . . . 5

2.4 Reti Neurali . . . 5

2.5 Valutare la ategorizzazione . . . 5

2.6 BeMoRe . . . 5

3 Fo used Crawling 6 3.1 Introduzione. . . 6

3.2 Analisi delWorld Wide Web. . . 6

3.2.1 HITS . . . 7

3.2.2 PageRank . . . 7

3.2.3 HyperInformation . . . 7

3.3 Fo usedCrawlers . . . 7

3.3.1 Chakrabarti's Fo usedCrawler . . . 7

3.3.2 IBM's Intelligent Crawler . . . 8

3.3.3 Agent-based Fo used Crawling . . . 8

3.4 Geneti -based Fo usedCrawling . . . 9

4 Computer Vision 9 4.1 Il problemadella segmentazione . . . 10

4.2 Appro io statisti o . . . 10

4.3 Appro io strutturale(o tramite des rizioni relazionali). . . 11

4.3.1 AttributedRelational Graph . . . 11

4.3.2 Synta ti Pattern Re ognition . . . 11

4.3.3 Uni azione MedianteGra . . . 11

4.4 Appro io mediante allineamento . . . 11

4.4.1 Template Mat hing. . . 12

4.4.2 L'algoritmo diHuttenlo here Ullman(1990) . . . 12

4.5 Appli azionedella Computer Visionalre uperodiimmaginida database visivi . . . 12

4.5.1 Template mat hingelasti o (deformabile) . . . 13

5 Clustering  Metri he e distanze 13 5.1 Data mining. . . 13

5.2 La distanza . . . 13

5.3 PartitioningMethod . . . 14

5.3.1 Apprendimento non supervisionato . . . 14

5.3.2 Apprendimento supervisionato . . . 14

6.1 Problemi diapprendimento Well-Posed . . . 14

6.1.1 Esempi diproblemiwell-posed . . . 14

6.2 Progettazione diunsistemadiapprendimento . . . 15

6.2.1 S elta della Training Experien e . . . 15

6.2.2 Case study: ilgio o della dama . . . 15

6.2.3 S hema diunsistemageneralediapprendimento . . . 16

6.3 Con eptLearning . . . 16

6.3.1 Denizioni . . . 16

6.3.2 Un esempio di on eptlearning . . . 17

6.3.3 Con ept Learning omeri er a inH . . . 17

6.3.4 Con ept Learning asSear h . . . 17

6.3.5 Algoritmo Find-S . . . 18

6.3.6 VersionSpa e . . . 18

7 Logi aFuzzy 18 7.1 Insiemi Fuzzy . . . 18

7.1.1 Operatorilogi i . . . 19

7.1.2 Impli azioni . . . 20

7.2 Relazioni . . . 20

7.2.1 Prodotto artesiano erelazioni . . . 20

7.2.2 Composizione . . . 21

7.3 Ragionamento fuzzy . . . 21

7.3.1 Regole . . . 21

7.3.2 Inferenze . . . 22

7.3.3 Appro iologi -based . . . 22

7.3.4 Appro iogeneralizzato . . . 23

7.3.5 Impieghi nei ontrolli. . . 23

7.4 Misure Fuzzy e Ragionamento on In ertezza . . . 23

7.4.1 Tipologiediignoranza . . . 23

7.4.2 Misure Fuzzy . . . 23

7.4.3 Misure diCredibilità-Plausibilità . . . 24

7.4.4 Misure diProbabilità. . . 25

7.5 Appli azioni alla roboti amobile . . . 25

7.5.1 Costruzione dimappe . . . 25

7.5.2 Mappe topology-based . . . 27

7.5.3 Lo alizzazione. . . 27

7.5.4 Obsta le avoidan e . . . 27

1 Intelligent Web & Personalized Sear h

1.1 Information Overload

La montagna di pubbli azioni s ienti he è in ostante aumento. Ma è tangibile la preo upazione di

impantanarsi nelle ri er he a ausa del res ente numero dipossibilispe ializzazioni. La di oltà non è

nella e essiva mole dipubbli azionimapiuttosto nella nostra abilitàdigestirle pro uamente.

Possibilesoluzione: personalizzarelaHuman-Computerintera tionltrandoeproponendosololerisorse

di uil'utente ha bisognoinun determinatomomento.

Lo statodell'arte dell'information lteringè ilseguente:

Pro esso BisognoInformativo Tipodi Sorgente

InformationFilteringIF Stabile Spe i o Dinami aNonStrutturata

InformationRetrieval-IR Dinami oSpe i o StabileNonStrutturata

DatabaseA ess Dinami oSpe i o StabileStrutturata

Exploration Vario Varia

IF vede il bisogno informativo stati o dell'utente o lentamente variabile. E' possibile pensare di

rappresentarlo internamente alsistema.

Lete ni hediUsermodeling onsentonodiidenti arele aratteristi he importantidiunutenteper

potergli fornire informazionipiùrilevanti.

1.2 Motori di ri er a

Imotoridiri er asonosistemi heutilizzano ri er henel ampodelIR.Il rawlersio upadivisitare

risorse (html,pdf,et .) inrete perilsu essivopro essamento. L'obiettivoèsalvareuna opiadell'intero

Web, e modi are la rappresentazione delle risorse in modo da eseguire le query molto velo emente

Gli indi i ipermettono ditrovarelekeyword diunaquerysenza analizzare ognivoltatutte lepagine.

Quello he iserveètrovarel'insiemedido umenti he ontengonounaopiùparole. Siusal'Inverted

Index, ovvero una lista ordinata di termini, on asso iate le informazioni relative ai do umenti in ui

ompaiono.

1.2.2 Mat hing Ve tor spa e model

Perindividuareido umenti hesoddisfano una querysipuò utilizzareil Boolean query pro essing.

Ma se i sono molti do umenti he soddisfano la query è di ile per l'utente individuare il migliore.

Allora sioperaunranking,ovverosiassegna un valore disimilaritàad ognido umento e sipropone una

lista ordinata. Un possibilemetodo perri avaretalesimilarità è utilizzareilVe tor spa e model:

•

^{la query e i do umenti vengono} rappresentati da vettori in uno spazio dove le dimensioni fanno riferimento alle keyword

•

^{lasimilarità èfunzione della similaritàtra vettori(e.g. prodottos alare odierenza)}

Come determinare i valori degli elementi dei vettori (weighting)? Possiamo pensare di rappresentare la

query e ido umenti ome un insieme diparole (rappresentazione bag of words) e asso iare il numero di

o orrenzetf (term frequen y) ad ognielemento del vettore.

Seprendiamosololafrequenzaris hiamodipesaretroppoitermini omuni herappresentanopo oun

do (avverbi,arti oli,et .). Allora possiamo determinare il peso di ogni termine

j

^{inun do umento}

x

ⁱⁿ

questomodo:

d _x,f = tf x,j · log  N df j



dove

N

^{èladimensione della ollezionepredenita e}

df _j

^{(do ument frequen y) è ilnumero dio orrenze}

del termine

j

all'interno della ollezione. Tale te ni a si hiama TFxIDF (term frequen y x inverse do ument frequen y).

Inne si ri ava la similarità Solitamente si utilizza la osine rule. Ad esempio, dati i termini

T j

^{, il}

vettore tridimensionale di esempio

v ₁ = 2T ₁ + 3T ₂ + 5T ₃

^{e un se ondo vettore analogo}

v ₂

^{, si al ola la}

similitudine attraverso il al olo del oseno dell'angolo tra due vettori. dove il prodotto s alare si nor-

malizza rispettoallalunghezza deivettori,inmododa renderelasimilaritàindipendentedalla lunghezza

(misurata onil numero termini distinti) deido umenti.

1.2.3 Google

L'ar hitettura diGoogle è osì organizzata:

1. l'URLServerinvia leurls da visitareai rawler

2. loStoreServer le ompatta(zlib RFC1950) ele memorizzanelRepositoy

3. l'Indexer per ogni pagina estrae una lista di hits (parole+pos+font+et ) he viene salvate nei

Barrels he ontengono un forward index (per ogni do la lista degli hits), e i link; le parole

vengonoinserite nel vo abolario Lexi on.

4. il Sorter real'inverted index

5. il Sear heresegue laquery

1.3 Personalized Sear h

Utilizzareunmodello degliinteressidell'utenteperrendereunari er apiùpre isaeaumentare ilnumero

dido umenti diinteresse. Nel99% dei asi esiste un modulodiUser Modeling he ontiene una rappre-

sentazione dei on etti di interesse per l'utente, on un erto input per ostruirlo e tenerlo aggiornato.

Come vantaggiaiuta a risolvereproblemi dipolisemia esinonimia, e puòfornire adattabilità.

1.3.1 GoogleAlerts

L'utentesuggeris eespli itamenteiterminidi uièinteressatoIlmotorelan iaperiodi amentelaquerysu

Newse/oWebeirisultativengonoinviativia email. Utileperbisogniinformativimolto stabili. Nessuna

adattività.

Esistono due possibili tipi didati:

User Data informazioni su aratteristi he personali dell'utente

Usage data informazionisulleinterazioni dell'utente

Per ostruire etenere aggiornatolo UserModel 'èbisogno diunfeedba kesterno.

Expli it (Relevan e) Feedba k l'utentesuggeris edo umenti/parole diinteresse

Impli it Feedba k ilsistemamonitorizza il omportamento dell'utente

Una te ni a orrelata alExpli itFeedba kè laQuery expansion: un sottoinsiemedi termini estratti dai

do umenti vengonoaggiuntialla query,in rementando(disolito) lapre isione deirisultati.

Gliuser prolepossonoessere sfruttati induemodi:

Partof retrievalpro ess il ranking è un pro esso uni ato. in ui gli user prole sono impiegati per il

punteggio dei ontenuti Web (piùvelo e, mauser modelsempli ati)

Re-ranking : gliuserprolevengonoimpiegatiinunse ondostep, dopo heilpunteggio èstato al olato

da un metodo nonpersonalizzabile (migliori risultati, mao orrerianalizzare tutti ido umenti)

Ipossibiliappro i disponibili:

Content-based invia ra ondazioni all'utente ( ome gli IRtradizionali)

Current Context si analizza il ontesto dell'utente, ome appli azioni aperte, do umenti visualiz-

zati, testoimmesso, et .

Sear h History La browsing/query history può disambiguare il termine Visa: se l'utente ultima-

mente ha er ato voliperunpaese straniero,Visa riguarderàpro edura puro rati he.

Ri h UserModels UM on rappresentazionipiù omplessedei needs(ad es.reti neurali)

Hypertextual Data Versioni personalizzate dialgoritmi he assegnanounrank alle pagine Web in

base allastruttura deilinks,e.g., PageRank, HITS.

Content Presentation organizzare la lista dei risultati in luster (gra i) ontenenti do umenti

ani a un erto topi (Vivisimo)

Collaborative-based al olalesimilarità ( ome Amazon)

Collaborative Approa h si suggeris ono do umenti he altri on gli stessi needs (query) hanno

selezionato inpassato

2 Text Categorization

La ategorizzazioneprendeininput: unades rizionediunaistanza,

x ∈ X

^,dove

X

^{è l'istanzalinguaggio}

o spazio dell'istanza, un numero ssato di ategorie

C = {c 1 , c ₂ , . . . c _n }

^{. In output: la ategoria di x:}

c(x) ∈ C

^,dove

c(x)

^{èuna funzione di} ategorizzazione he ha omedominio

X

^{e ome odominio}

C

^.

L'esempio di apprendimento è espresso on la oppia

< x, c(x) >

^{. Dato un insieme di esempi di}

apprendimento

D

^{,trovareuna ipotizzatafunzione di} ategorizzazione

h(x)

^{tale he:}

∀ < x, c(x) >∈ D : h(x) = c(x)

Il Text Categorizationassegna do umenti ad uninsieme ssato di ategorie. Una ategoria può essere

rappresentataattraverso (ad esempio) onil TF/IDF.

2.1 Algoritmo di apprendimento Ro hio

Usiamo lostandard diindi izzazione TF/IDF perrappresentare informa vettorialeido umenti ditesto

(normalizzati se ondo lafrequenzamassimadiun termine).

Per ogni ategoria, viene elaborato un vettore Prototipo dalla somma dei vettori di training nella

ategoria.

Assegnamo il do umento ditest alla ategoria ol vettore prototipo piùvi ino mediantela regola di

L'apprendimento siridu ealmododiimmagazzinarelerappresentazionidegliesempiditrainingin

D

^{. Il}

test dell'istanza

x

^:

•

^{elaboralasimilaritàtra}

x

^{e tutti gliesempi in}

D

^.

•

^{assegna ad}

x

^{la ategoriadelpiùsimile in}

D

^.

Quindi,a dierenza delRo hio, non si al olano espli itamenteiprototipi delle ategorie. Iprototipi

del Ro hiopossono avere problemi on ategorie disgiunte, mentre Nearest Neighbor tendead avere in

tal asoun omportamento migliore.

2.3 Algoritmo di apprendimento Bayesiano

Consistenell'apprenderee lassi aremedianteappro iprobabilisti i. IlteoremadiBayesgio aunruolo

riti o nell'apprendimento e lassi azione.

Sapendo he laprobabilità di

A

ondizionataa

B

^{èpari a:}

P (A|B) = P (A ∩ B) P(B)

il teorema di Bayes esprime laprobabilità ondizionatarispetto allospazio degli eventi

A ₁ , A ₂ , . . . , A _n

^:

P (A ₁ |B) = P (B|A ₁ )P (A ₁ )

P (B) = P (B|A ₁ )P (A ₁ ) P n

i=1 P (B|A i )P (A i )

Dati l'insieme delle ategorie

{c ₁ , c ₂ , . . . c n }

^{ed una} des rizione di un'istanza, determina il grado di appartenenzadi

E

^perogni

c _i

^.

P (E)

^puòesseredeterminatasolosele ategoriesono ompleteedisgiunte.

2.4 Reti Neurali

Unareteneuronale onsisteinunpooldisempli ipro essielementari he omuni anofralorospedendosi

segnaliattraversonumerose onnessionipesate. Unareteastratosingolo onsisteinunoopiùneuroni di

output, ognuno dei qualiè onnesso on un fattore peso

w _ij

^{atutti gliinput}

x _i

^{. Inquesta sempli erete}

(il neurone)può essereusatopersepararegli inputindue lassi. Ipesidella reteneuralesonomodi ati

durantelafase dilearning

Si utilizza un per ettrone per ogni ategoria Learning sui do umenti di training della sua ategoria.

Durante la fase di test, il per ettrone fornis e un valore VERO/FALSO sull'appartenenza del vettore

rappresentativo ildo umento alla ategoria.

2.5 Valutare la ategorizzazione

Esistono dueparametri a ettati dalla omunitàIR:

Pre ision l'abilità nelrestituirei do umenti he sonopiùrilevanti

Re all l'abilità nelrestituire tutti ido umentirilevanti nell'intero dominio

2.6 Be MoRe

BeMoRe (BestModelRetrieval) èuna nuova metodologia di lassi azione ditesti.

Ilprepro essingprevede diverse fasi:

Suddivisione in Token L'NLPNaturalLanguagePro essing onsistenell'analizzareunafraseinlinguag-

gionaturale,eseguireilparsingedappli arelostemming,noadestrarneinomieiverbi. Ilsistema,

mediante ildizionarioWordNet,assegna adognisigni ato un odi enumeri ounivo o. Dopoaver

eseguito gli algoritmi di word sense disambiguation, ad ogni nome della frase viene sostituito il

odi e delsigni ato he è risultatoesseremigliore.

Compressione prevededue fasi:

1. si appli a laTFxIDFper minimizzareilrumore

2. siappli a laEditDistan e per al olare lasomiglianzamorfologi a(suGoogleforse er avi:)

La dimensione dello spazio dei termini può ostituire un problema per hé gli algoritmi di learning non

s alano fa ilmente sugrandivaloridella dimensione. Seladimensioneèaltaspessosiveri ano fenomeni

diovertting. Abbiamo due s elte:

•

^{Riduzione lo ale(un insieme ditermini diversoper ias una ategoria)}

•

^{Riduzione globale(il setditermini è valido perqualunque ategoria)}

Alla ne dovremo trovarel'iperpiano separatore ottimo dell'insieme di training. Come formalizzare? In

due dimensioni, l'equazione della linea è data da:

w ₁ x + w ₂ y = b

^Se l'iperpiano separatore non esiste, ovvero se i dati non sono linearmente separabili per la presenza di rumore, si possono usare le Sla k

variables, he onsentonola lassi azionenon orrettadial uni punti,tenendo ontodelrumoreneidati

L'OnLine Hyperplane onsente la ri er a in rementale della soluzione ottima. Gli elementi positivi

e negativi sono rappresentati on pesi diversi. È una Loss fun tion a basso osto omputazionale La

onvergenza è garantita dall'estensione delteoremadiNoviko.

Ereditando al une aratteristi he matemati he delle SVM, il sistemasi avvale diun modulo dikernel

perrisolvereil problemadiseparabilità non lineare.S elta delkernel miglioreattraverso modelsele tion.

L'uso della funzione kernel onsente di al olare l'iperpiano di separazione senza bisogno di eettuare

espli itamente ilmapping in

F

3 Fo used Crawling

3.1 Introduzione

Ladinami itàeledimensionidelWebnon ipermettonodi ostruiregrandibasidiinformazioniaggiornate

suqualsiasiargomento (motoridiri er a) apa idisoddisfaree a ementeevelo ementequalsiasiquery.

I normali rawler terminano periodi amente l'esplorazione e ri omin iano da apoper tenere aggiornate

le opiedelle pagine Web.

Obiettivo: partendo da una serie dipagine di partenza, navigando attraverso i link, s egliere divolta

in volta iper orsi giudi ati migliori, ridu endo le risorse ne essarie ( pue network) per analizzare tutte

le pagine, evitando di seguire i per orsi he lo portano a pagine non ani alla nostra query. Vantaggi:

più overage sullerisorse diinteresse,piùfreshness neirisultati, e unmat hingpiùsosti ato.

Il Fo used (o Intelligent) Crawling può essere usato per ostruire indi i inversi su erti topi in alter-

nativa a

meta-sear hing interroga motoridiri er aesistenti

query-time rawling avviare rawlingsul Web adogni query

query-modi ation non si ostruis e unindi e masimodi alaquerye lasiinoltra amotori diri er a

diesistenza

Nella prati asidevestabilire l'ordine delle prossimepagineda visitare,inmodo da indirizzarel'esplora-

zione sempreverso iper orsipiùinteressantiInformazioni da sfruttare:

1. ontenuto pagine visitate

2. an ore testuali deilinknelle pagine

3. struttura deilinktra pagine

3.2 Analisi del World Wide Web

Le pagine Web diun erto topi in genere possiedono linkad altre dello stesso topi (Linkage o Topi al

Lo ality).

Nella Web So ial Network Analysis oltre al ontenuto testuale delle risorse si sfruttano an he le

informazioni ontenute negli hyper-links.

Isu essivialgoritmi posso essereusati perdiversi s opi:

•

^{re-ranking deirisultatidiun motorediri er ainbase alle}informazioni estratte dailinks

•

^{analizzare lastruttura e ladinami a delWeb}

•

indirizzare il rawlingdeimotori diri er averso lerisorse piùinteressanti (e.g. piùaltorank)

Un linkpuòessereletto omeunaindi azione diautorevolezza he hil'ha reato (autore dellapagina)

vuole dare alla pagina puntata. Sipotrebbe per iò pensare diaumentare l'importanza delle pagine on

molti linkentranti(ba k-link ount).

Ma osì ilimitiamoa onsideraresololapopolarità assolutadiunapaginasenzametterlainrelazione

on un ertoargomento e on laqualità della paginagenitore.

HITSsibasasullarelazionetrapagineautorevoli(authoritative pages)perun erto topi ,epagine he

puntanoamoltepagine autorevoli (hubs). Se moltepaginedigeo ities puntanoa java.sun. om, allorale

pagine digeo itiessono hub,mentre java.sun. om è una paginaautorevole.

Unapaginaèritenuta importante (altaauthority) seri evemoltilinkdapagineimportanti( onalta

hubness). Di onseguenza e pagine hubs hanno la aratteristi a di puntare a molte pagine importanti.

Hubness e authoritysono2 misure orrelate he vengono al olate una infunzionedell'altra:

authority(p) = X

q|q→p

hub(q)

hub(p) = X

q|p→q

authority(q)

L'insieme dipaginevieneordinato perauthority. Lehubs sonovalidipunti dipartenza per esplorazioni.

3.2.2 PageRank

Adognipaginasiassegnaunasingolamisura(rank)Unapaginahaaltorankseèaltoilrankdellepagine

he lapuntano:

rank(p) = (1 − d) ·

k

X

i=1

rank(p _i )

C(p i ) + d · 1 T

dove

C(p)

^{è ilnumero dilinkdentro lapagina}

p

^,

T

^{èil totale dipaginee}

d

^{è una ostante(0.1 ...0.15).}

Il rankpuò essere visto ome la probabilità he siselezioni lapagina

p

^{. La}

d

^{indi a la}probabilità he l'utente selezioniun'altrapagina.

3.2.3 HyperInformation

Unapaginaipertestualehaunvalore henondipendesolodalsuo ontenutotestuale,maan hedailinkivi

ontenuti. Sevi trovateinunapagina da uipotete raggiungernealtre paginedivsinteresse,lapaginaè

moltoimportante. Quandoo orrevalutareunapagina,si onsideraan helamisuradiHyperInformation

he tiene onto della presenza dei link:

Inf ormation(A) = T extInf o(A) + HyperInf o(A) HyperInf o(A) = F ¹ · T extInf o(B ₁ ) + F ² · T extInf o(B ₂ )

on

0 < F < 1

^{lafrazione della} informazione testualeraggiungibile.

3.3 Fo used Crawlers

3.3.1 Chakrabarti's Fo usedCrawler

Il Chakrabarti's Fo usedCrawler èun sistemadi rawling autonomo perlari er a dirisorse inerentiun

erto topi (rappresentato daun setdipagine inizialifornite dall'utente).

È omposto da 2sotto-sistemi:

Classier determina larilevanza deido umenti rispettoaltopi diinteresse

Sfrutta una tassonomia gerar hi a (Yahoo!) di ategorie

C

^per individuare gli argomenti he più interessano l'utente

1. L'utente suggeris elepagine diinteresse

2. Ilsistemaproponele ategorie

C ^∗ ⊂ C

^{piùani onalgoritmidimat hingtestuale(e.g. Ve tor}

spa e model)

3. L'utente eventualmente ranale ategorie(s egliendoquelle piùgenerali oparti olari)

4. Le lassi nalivengonomar ate ome good.

Duranteil rawling, ad ognipagina he sivisitavieneasso iata la ategoriapiùspe i a

c

^{. Seuno}

dei nodi neigenitori di

c

^{è mar ato ome good,allora la pagina non viene ignorata. Ad esempio,}

se mi interessano le GT, e se il rawler ha trovato una pagina sulla Maserati, la onsidero buona

omunqueper hé è ontenuta inGT.

Distiller identi a ilink he devono esserevisitati perprimidal rawler.

Sfrutta HITS per individuare le risorse più importanti. Periodi amente viene eseguito l'algoritmo

perindividuarelepaginere uperate onpiùalto hubs,dopodi hési estraggonoilinkivi ontenuti,

e siinseris ono nella odadelle risorse da visitaredel rawler.

3.3.2 IBM'sIntelligent Crawler

Si adatta alle risorse visitate durante il rawling stimando se una pagina è interessante per mezzo di

algoritmi dima hine learning. Non ne essita quindidel lassi atore on la gerar hia ome nel fo used

rawling

P (C)

^{èla prob he una paginasia diinteresse.}

E

^{sono ifatti he onos iamo} riguardanti le andidate urls (testo pagine he le puntano, urls, testo an ore, et ). Esempio: er hiamo pagine su Ba h. 0.3%

di pagine di interesse. Ma se la parola eshop ompare in una pagina he ha un link verso quella di

interesse,laprobabilità aumenta noal10%. La onos enza

E

^{puòaumentare laprob he una andidate}

url soddisil predi ato.

P(C|E) > P (C)

nell'esempio infattirisulta

0.1 > 0.003

3.3.3 Agent-based Fo used Crawling

Sistemi diri er aadattativi, he prendonospunto dalparadigmadiprogrammazione Ant System:

Come ries ono gli animali a trovare il ammino e a oordinarsi? Quando una formi a trova

ibo,las iadelletra e diferomonepermar areilper orso,inmodotale helealtreformi he

possano trovarlo.

Si ha un'ar hitettura reattiva formata da un numerosi ant-agent he vagano in ambiente di risor-

se ipertestuali. Ogni agente ha sempli i omportamenti di basso livello he reagis ono a ambiamenti

nell'ambiente. Le informazioni disponibili perun agente sono:

1. il risultatotralaquery dell'utente elarisorsa orrente

2. l'intensità deivalorisui ammini diferomone, orrispondenti ailinkus enti

L'ese uzionedel sistemasidividein i li:

1. inogni i lo gliagenti ompionouna sequenzadimosseda unarisorsa a un'altra

2. alla ne del i lo,ogni agente aggiorna letra e di feromone delper orsoeettuato omefunzione

dei punteggi pervenutisulle risorse.

3. ad ogninuovo i lo, vieneposizionatol'agente inuna delle risorse iniziali

4. seunatra iaesiste,l'agentede idediseguirla onunaprobabilitàfunzionedellarispettivaintensità

diferomone

5. senon esiste al unatra ia, l'agentesi muove asualmente

Se due per orsi portano a una pagina interessante, iprimi agenti he raggiungono quella pagina sono

gli uni i he hanno seguito ilper orsopiù orto,e quindisono iprimi arilas iare il feromone he attrae

gli agenti su essiviallo stesso per orso.

Il sistemamostradue forme diadattività:

1. ranamentidella queryutente durante l'ese uzione

2. alterazione del ontenuto delle risorse

3.4 Geneti -based Fo used Crawling

Una popolazione res ente di agenti intelligenti esploranoil Web guidati dalle query utente. Una popo-

lazionedi romosomi odi ati dauna parti olarestruttura datievolvono versouna soluzionepotenziale

attraverso un insieme di operatori generi i. I romosomi he arrivano più vi ini alla soluzione migliore

hanno maggiori probabilità divivere eriprodursi.

Los opoè diimitare l'esplorazioneumana on interazionebassa onulla.

Igenotipi(1)sonouninsieme di romosomi he determinanoil omportamento diri er adegli agenti.

È formato da:

•

^{un insieme diparole hiave}

K

inizializzate on itermini diquery.

•

^{unvettoredipesi}

W

^, orrispondentiall'informazionememorizzatainunareteneurale,utilizzataper giudi are qualiparole hiave nelprimo insieme dis rimanomeglio ido umentirilevanti all'utente

4 Computer Vision

La Visione Arti iale(o Computer Vision oPattern Re ognition) si o upa dell'analisie dell'interpreta-

zione delle immaginidigitali(perpermetteread un omputer di apire osastaguardando).

Le appli azioni prati he sonoil re uperod'immagini in database visivi (Image Retrieval) datala re-

s entediusionediar hivid'informazionees lusivamentevisiva(musei,ar hivifotogra i,e- ommer e...).

Visione appli ata alla roboti a. Sorveglianza automati a (tramite tele amere o altri dispositivi). Guida

automati a divei oli su strada. Visione industriale, medi a,aerea, ...

Al uni sotto ampi:

low-levelvision apartiredaun'immagine

I

^{vieneprodottaunase onda immagine}

M (I)

^datadall'appli- azione diltripuntuali e/o lo ali. Sitratta quindidiuna trasformazione dell'immagine.

medium-level vision estrazione di predeterminate aratteristi he dall'immagine. Dall'immagine

I

^{(o da}

M (I)

^{) sipassa adun insieme di} aratteristi he

F = {f ₁ , . . . , f _n }

high-level vision interpretazione dell'immagine(qualioggettisonopresentioqualirelazioni inter orrono

traessi)

La onos enzadel sistema generalmente è di tipo modellisti o (model based) oppure appresa attraverso

te ni he dima hine learning.

Iproblemi prin ipalinelri onos imento diimmagini:

Condizioni di illuminazione he produ ono una variazione nella distribuzione dell'intensità luminosa

della s ena.

Trasformazionigeometri he rigide dell'oggetto(in ordinedidi olta res ente):

1. roto-traslazioni e s alamenti in2D,

Rumore

Gap tipoparti olare dirumore onsistente nella man anza dielementinell'immagine.

O lusione

Segmentazione partizionamento deidati diinputinentita semanti he distinte(linee, regioni, oggetti).

Indexing eettuare una ri er ae iente inun atalogo dimodelli.

Identi azione ri onos erel'istanzadi unoggetto inun'immagine.

Oggetti non rigidi (forbi i, volti umani, ...). Il lorori onos imento è ompli atodalla possibilita heha

la loroforma divariare.

Classi azione ri onos erel'appartenenza aduna data lassediun oggetto inun'immagine.

4.1 Il problema della segmentazione

Col termine segmentazione in Computer Vision si intende un qualsiasi partizionamento dell'immagine

(o della sequenza video)ininsiemiomogeneirispetto aduna qual he aratteristi aper ettiva.

E importantesottolineare la trasversalita ditale denizione, ovveroil fatto he essa puo essere (edin

eetti è)appli ata avarilivelli dipro essamento.

Nella low-level vision, on segmentazione si intendono quei pro essi data-driven (dipendenti solo dai

dati) he permettono, ad esempio, dipartizionare un'immagine in base al olore o un video inbase alla

luminosita della s ena

In high-level vision, lasegmentazione e uno dei problemi nora insormontabili per un ri onos imento

eettivodegli oggettirappresentati inun'immagine poi hé ène essario he ilsistema apis a he isono

N

^{oggetti distinti. Un oggetto, in sostanza, e un on etto} semanti o e non una primitiva per ettiva ome il olore eil suori onos imento non puo hedipenderedaimodellidioggettiinmemoria(oltre he

dai datiininput).

Varistudi psi ologi i sembrano onfermare l'idea he, nelsistema visivoumano, il ri onos imento e la

segmentazione non sonofasinettamentedistinte. Lasegmentazione umanasembraessereunpro esso sia

data-driven he model-driven,in ui irisultatidiuna faseinuis ono sullafasesu essiva evi eversa.

Questo ampoean oraampiamenteinesplorato,siaalivellopsi ologi o(siri orda heiprimitentativi

in talsenso risalgonoalla teoriatedes a della Gestalt, negli anni'30), siaa livello omputazionale.

4.2 Appro io statisti o

Si s elgono una serie di

n

aratteristi he (features) dell'apparenza di un oggetto he siano fa ilmente misurabili. Ilri onos imentodi

O

^{( onvettore}

V (O)

^{) omeistanzadelmodello}

M

^{dipendedallafunzione:}

dist(V (O), V (M )

^.

Esempitipi i difeatures:

area dellagura ioe il numero deisuoi pixel.

ompattezza della regione denita omeil rapportotrail quadratodelperimetro el'area.

allungamento della regione denito omeilrapportotralalunghezzadella ordadilunghezza massima

e lalunghezza della ordaad essa perpendi olare.

minimo o massimo rettangolo (o ellissio er hio) in lusoo in ludentelagura.

Medial Axis Transform diuna gurapiana, hene restituis e uno s heletro.

Freeman Chain Code è possibilenumerare onvenzionalmente gli8(o 4) pixel onnanti olpixel

p

^on

valoriin

[0, 7]

^{e odi are on unastringa lasagoma diun oggetto.}

oe ientidell'espansione in seriedi Fourier ottenutiinterpretandolasagoma omefosseunafunzione

sinusoidale.

momenti digitali

entro digravità o entroide

Vantaggi e svantaggi:

- S arso poteredis riminante.

- Non permette he l'oggettod'interesse siao luso o in ontatto on altrioggettinella s ena.

4.3 Appro io strutturale (o tramite des rizioni relazionali)

Sis elgonounaseriediprimitive geometri he atomi he: segmenti,rettangoli, parallelepipedio gurepiu

omplesse, non ne essariamente regolari.

Unoggettoe des rittotramite la ombinazionedelle primitiveatomi he ottenuta medianterelazioni di

tipogeometri o, gerar hi o, ...

Vantaggi e svantaggi:

+ Permette una buona astrazione per hé sfrutta il potere des rittivo tipi o delle rappresentazioni

simboli he.

- Spessoha ostidiuni azione esponenziali.

- Le des rizioni solitamente non sono pre ise. Ad esempio una asa può essere rappresentata ome

una piramide sopra unparallelepipedo, maquestapiramide puòessere piùgrande,spostata,...

4.3.1 Attributed RelationalGraph

Una struttura dati frequentemente usata, nel aso dell'appro io relazionale, e il grafo, he permette di

asso iare ai nodi gli elementi atomi i della des rizione, e agli ar hi gli elementi della relazione (o delle

relazioni).

Ad esempio, attributi perinodipossono essere l'areao la ompattezza delle primitive geometri he ad

essi asso iate. ` Un attributo per una relazione del tipo

X

^{e sopra}

Y

^{potrebbe essere la misura della}

distanza fragli elementi atomi i

X

^e

Y

^{Siparla, intal aso,diAttributed Relational Graph.}

IlConne tion Graph, adesempio ha:

Primitive regionidell'immagine omogenee rispetto ailivellidigrigio

Uni a relazione adia enza traregioni

Attributidei nodi allungamento della regione

4.3.2 Synta ti Pattern Re ognition

L'idea, nonprivadiun erto fas ino, onsistenel onsiderare leimmagini ome fosserountesto dainter-

pretare, des rivendo i modelli diinterpretazione (pattern) mediante grammati he formali e utilizzando,

ome pro eduradimat hing, parser similia quelli usatiperl'interpretazione deilinguaggiformali.

Una hain ode puo esserevista ome unlinguaggio moltosempli e, ontenenteun'uni a stringa.

4.3.3 Uni azione Mediante Gra

Quando la struttura dati s elta per la rappresentazione di

M

^{e di}

I

^{e il grafo, il ammino} all'interno dell'alberodiuni azione orrisponde all'implementazione diun graph mat hing.

L'isomorsmotragrae un problemaNP.Piu interessante, inComputer Vision, sonoiproblemi di:

•

^{Isomorsmo trasottogra} (NP-Completo)

•

^{Isomorsmo inesatto, in ui la funzione}

f

^{e parziale e/o i vin oli sonosolo} parzialmente veri ati (NP).

4.4 Appro io mediante allineamento

Usa rappresentazionirealisti he sia dell'oggetto

O

^da ri onos ere he deimodelli

M

^{inmemoria. In fase}

di ri onos imento, formula una serie di ipotesi onsistenti in trasformazioni geometri he

T

^{da appli are}

ad unadelle duedes rizioni(solitamente

M

^{)pertentare difarla} allineare onl'altra. Alpasso

i

^-esimo

l'ipotesi

T _i

^{vieneveri atatramite misuredi}somiglianza (tipol'overlapping traipixel).

Il templatemat hingèilpiusempli ealgoritmodiallineamento. Esso onsistenelsovrapporreall'imma-

gine in input

I

^lasagoma

M

^da ri onos ere (modello 2D), traslando ed eventualmente ruotando

M

^ad

ogni iterazione.

Si tratta di una sempli azione dell'allineamento sempli e gia in ontrato, generalmente non onside-

rando, per motividie ienza, lapossibilita diruotare ilmodello erestringendosi atemplate onsagome

sempli i.

Eutilizzatoinal uni sistemi ommer ialiperinterpretazionidiimmaginiindustriali omedi he,nell'O-

CR, ...

La trasformata di Hough (1962) La Trasformata diHough (HT) e una forma più elegante (espesso

più e iente)ditemplate mat hing fattanello spazio deiparametri anzi hé nello spazio artesiano.

Supponiamo di avere un'immagine

I

^{digitale des ritta dalla funzione binaria}

f

^{on valori in}

{0.1}

^.

Supponiamo di er are inessalapresenza ditemplatedes rivibili tramitesempli iformuleanaliti he: ad

esempio delle rette.

Se ilpunto

p

⁽

p = (x, y)

^{) è tale he}

f (p) = 1

^{,alloratutte lerettipassantiper}

p

^devonosoddisfare:

y = mx + c

on

m

^e

c

^{variabili. Per ogni}

p

^{tale he}

f (p) = 1

^,l'algoritmo diHough in rementa diun'unità l'a umu- latore

H(m, c)

⁽

H(m, c) = H(m, c) + 1

^{), perogni}

c

^ed

m

^{tali he}

c = −mx + y

Finita la s ansione di

I

^{, i valori più alti in}

H

indi heranno le rette on un maggior numero di pixel allineati.

I parametri

c

^ed

m

^sono di ilmente limitabili, per io normalmente si adotta una parametrizzazione diversa perlerette. Unaretta

r

^{puo essereinfatti espressaan he mediantelaseguenteformula:}

ρ = cos θx + sin θy

dove

ρ

^e

θ

^sono, rispettivamente, ladistanzae l'angolo formatidalla retta perpendi olread

r

^epassante

perl'origine.

Trasformata di Hough Generalizzata Ballard(1979-1981) proposeuna generalizzazione del metodo di

Hough per trattare sagome qualsiasi,an henon regolari (Trasformata diHough Generalizzata oGHT).

Arun-time, perogni pixeldi

I

^{voto perlaposizione del entro dimassa.}

Sia l'HT he la GHT sono metodi molto promettenti usati in letteratura in tantissime appli azioni

diversee onnumerosissime varianti. Sonomoltorobustiarumore edo lusionimasonopo oadatti per

oggetti 3D. Infatti sono appro i viewer entered. Inoltre, risentono dei problemi generali dei metodi di

allineamento `(di oltaa trattaredeformazioni).

4.4.2 L'algoritmo diHuttenlo her e Ullman (1990)

L'algoritmo di allineamento 3Dproposto da Huttenlo her e Ullman parte dalla seguente onsiderazione

geometri a:

Dati tre punti non ollineari

m ₁

^,

m ₂

^ed

m ₃

appartenenti al modello, e le loro rispettive proiezioni sulpiano dell'immagine

p ₁

^,

p ₂

^e

p ₃

^,esistono esattamentedue trasformazioni (tra esse spe ulari) delmodello tridimensionale nell'immagine bidimensionale.

Ingeneralesitrattadiunappro iopre iso(nonsemprevelo e) hedabuonirisultatinell'identi azione.

Man a di apa ita astrattive ne essarieperla lassi azione.

4.5 Appli azione della Computer Vision al re upero di immagini da database visivi

Un tipi osistemadire uperodiimmaginitramite somiglianza diformapresuppone:

•

^{Una query bysket h: l'utentedisegna unasagoma} approssimativa di io he sta er ando neldata base di immagini

•

^{La ri er aneldatabaseavvienequinditramitete ni hediindexing,} identi azione e lassi azione simili aquelle viste peril asogenerale

•

^{L'output del sistema non si limita a dire osa e stato o non e stato} ri onos iuto, ma deve fornire una listadiimmagini ordinateper gradodisomiglianza on laquery.

Si ritrovano i loni lassi i, soprattutto quello statisti o e l'allineamento (gli appro i strutturali qui

sonomeno omuni). L'allineamento,generalmente, avvienetramitetrasformazionigeometri henonrigide

T

^{dello sket h inizialeperadattarlo omesefosse unelasti o alle silhouettedelle immaginiinmemoria.}

Le immagini vengono inserite nel data base del sistema nella forma ontenente solo gli edge. L'utente

disegnailsuosket husandountoolgra oelasagomanalevienerappresentata onunaspline odi ata

medianteisuoi punti di ontrollo:

P = (p ₁ , . . . , p n )

Se ilmat hing tralo sket h e l'immagine andidata e elevato, la pro eduratermina qui. Altrimenti, i

vari

p _i

^vengonoperturbati inmodo damodi are losket h ere-iterare ilgrado di orrelazione.

E possibile massimizzare il grado di mat hing tra lo sket h e l'immagine

M

^{tramite un algoritmo}

iterativo he modi a progressivamente i

p _i

^{nella direzione di res ita massima ottenuta derivando}

M

rispettoa

P

^{(te ni a delgradiente} as endente).

5 Clustering  Metri he e distanze

5.1 Data mining

Il data mining è il pro esso di analisi, svolto in modo semiautomati o, di una grande quantità di dati

grezzi al ne di s oprire il modello (pattern) he li governa, o una regola signi ativa, da ui ri avare

onos enze utiliappli abili alnostro ontesto operativo, omead esempio:

Previsioni identi ano relazioni etendenze neidati, aiutando a s oprirefenomeni dimer ato

Veri he servono a onvalidare les opertefatteinfase dianalisiper garantire de isioni orrette

Il Data Miningè larisposta te nologi a all'esigenza disaperanalizzare e ri avare onos enze

utili, dalle enormiquantità didati grezzi he si ra olgonoormai intutti i ontesti operativi

della nostra so ietà: estrazione delle informazioni impli ite.

Vengono utilizzati ometipi didati:

Matri e deidati (

n

^{oggetti on}

p

attributi):





x ₁₁ · · · x _1p

· · · · · · · · · x _n1 · · · x _np





Matri e didissimilarità dove

d(i, j)

^{è lamisuradi}dissimilarità traoggetti

i

^e

j

^{. Se}

d(i, j) = 0

^alloragli

oggettisono moltosimili. Ad esempio, ungio attolo on treoggetti:





0 · · · · · · d(2, 1) 0 · · · d(3, 1) d(3, 2) 0





Variabili numeri he,binarie, ategori henominali, ditipo misto

5.2 La distanza

Proprietà della distanza(dallamatri e didissimilarità):

d(a, b) ≥ 0

⁽¹⁾

d(a, b) = d(b, a)

⁽²⁾

d(a, a) = 0

⁽³⁾

d(a, b) ≥ 0

⁽⁴⁾

d(a, b) ≤ d(a, c) + d(c, b)

⁽⁵⁾

(6)

Permisurare similaritàtra oppie dioggettispesso siutilizza ladistanza diMINKOWSKI:

d(i, j) = ^q q

|x _i1 − x _j1 | ^q + . . . + |x ip − x jp | ^q

dove

q

^{è unintero positivo:}

•

^se

q = 1

^{siha ladistanzadiManhattan}

•

^se

q = 2

^{siha ladistanzaeu lidea}

Possiamo pesare levariabili,ottenendo una misuradidistanza pesata.

S opo: partizionare ildatabase

D

^{din oggettiinun insieme di}

k

^luster.

5.3.1 Apprendimento non supervisionato

K-MEANS

1. s egliamo

k = 3

^{e itresemiiniziali}

2. assegniamo ognire ord al luster on il entroide (o seme) piùvi ino

3. il passodue ha individuatonuovi luster. Ci al oliamoi entroidi(o semi) diquesti

La omplessità è

O(nktd)

^,dove:

n numero dioggetti

k numero di luster

t numero diiterazioni

d numero diattributi

K-MEDIOIDS (PAM)

5.3.2 Apprendimento supervisionato

Reti neurali (MLP) Una Multi-Layers Per eptron net (MLP) è ompostada una seriediper ettroni

organizzati on una struttura gerar hi a he può omprendere uno o più strati nas osti (hidden layer)

legati on la regola del feed-forward (un nodo dello strato

i

^{-esimo può essere ollegato solo ad un nodo}

dello strato

i + 1

^-esimo).

Il per ettrone è unsempli eneurone dotatodel ir uitotea her perl'apprendimento:

Quandousare lereti neuralineldatamining ?

Le reti neurali rappresentano una buona s elta in aso di lassi azioni e previsioni, quando è più

importante avere velo emente e bene irisultatidi unmodello henon sapere ome questofunziona.

Leretineuralinonfunzionanobenequandosihaa hefare on entinaiaomigliaiadivariabilidiinput.

Un grannumero diqueste aratteristi he rendepiù di ile il ompito dellarete diindividuarepattern e

la fase di training può prolungarsi nel tempo senza trovare una buona soluzione. In questo aso, le reti

neurali danno frutti migliori se ombinate on gli alberi de isionali: questi ultimi infatti selezionano le

variabilipiùimportanti, impiegate poiperil trainingdella rete

6 Ma hine Learning

6.1 Problemi di apprendimento Well-Posed

A omputer program is saidto learn from experien e

E

^{withrespe tto some lassof tasks}

T

and performan e measure

P

^{, ifits} performan e at tasks in

T

^{, as measured by}

P

^{, improves}

withexperien e

E

Con etti fondamentali:

Task

T

^{obiettivo del sistema(gio are adama)}

Experien e

E

^{insieme di}addestramento dal quale apprendere (partitegio ate) Performan emeasure

P

^{misuradella apa itàdieseguire iltask(# dipartitevinte)}

6.1.1 Esempidi problemi well-posed

Gio o della dama:

Task

T

^{gio area dama}

Experien e

E

^{partitegio ate ontro sestesso}

Performan emeasure

P

^{%dipartitevinte}

Task

T

ri onos ere e lassi are parole s ritte amanomemorizzate ome immagini Experien e

E

^{undatabase diparole s ritte amanoinsieme alla loro} lassi azione Performan emeasure

P

^%diparole orrettamente lassi ate

Robot he guida unautovei olo

Task

T

^{guidare un} autovei olosu una strada pubbli a Experien e

E

^{sequenzadiimmagini}

Performan emeasure

P

^{distanzaper orsa prima diunerrore}

6.2 Progettazione di un sistema di apprendimento

Gli obiettivigenerali sono:

•

^{Denireinmodopre isouna lassegeneralediproblemi hein ludono forme}interessantidiappren- dimento

•

^{Esplorare algoritmi he risolvono problemidi} apprendimento

•

Comprenderela strutturafondamentale diproblemi epro essidiapprendimento

6.2.1 S elta della Training Experien e

La TrainingExperien eè aratterizzata da:

Feedba k Dire t feedba k trainingexamples: insiemedi singole ongurazioni dellas a hiera insieme

alla mossa orrettaper ias unodiessi.

Indire t feedba k training examples: insieme di sequenze dimosse insieme airisultati nali delle

partite gio ate(èdi ile ri avare informazionisullabontà dellesingole mosse)

Controllo della sequenza ditrainingexamples

Distribuzione dei training examples: quanto rappresenta bene la distribuzione di esempi sui quali il

sistemaverrà misurato

Comeassunzione,ilsistemaapprende attraverso partite ontrosèstesso. Non ne essita diun external

trainer epossonoessere generatimolti trainingesempi

6.2.2 Case study: ilgio o della dama

Dastabilire:

1. Il tipo esatto di onos enzada apprendere

2. Una rappresentazione perla onos enzatarget

3. Un me anismodiapprendimento

La s elta della mossa è però di ile da apprendere per via deltipo diindire t experien e disponibile

al sistema. Nuova Target Fun tion

V

^{: mapping tra ogni stato ammesso della s a hiera e l'insieme dei}

numeri reali: punteggio più alto allo stato piùpromettente perl'esito della partita. Deniamo noi una

funzione (ri orsiva)

V (b)

^,dove

b

^{è lostato} s a hiera,

b ∈ B

^:

•

^Se

b

^{è uno statonale positivo}

V (b) = 100

•

^Se

b

^{è uno statonale negativo}

V (b) = −100

•

^Se

b

^{è uno statonale patta}

V (b) = 0

•

^Se

b

^{èunostato intermedio}

V (b) = V (b ^′ )

^essendo

b ^′

^{ilmigliorestatonale he puòessereraggiunto}

a partiredallo stato

b

^{e gio ando inmodo ottimono alla nedel gio o.}

E' pero una denizione nonoperazionale:

V

^{non può essere realmente omputata. Si di e denizione}

operazionaledi

V

^{una denizione he puòessere realmente utilizzata dalsistemaper valutarestatie}

selezionare legiustemosseinlimiti ditempo realisti i

Siapprossimalafunzione targetideale

V

^{on una funzione}

V ^∗

^:

• X ₁

^{: numero dipedineneresullas a hiera}

• X ₂

^{: numero dipedinebian he sullas a hiera}

• X ₃

^{: numero didame neresullas a hiera}

• X 4

^{: numero didame bian he sullas a hiera}

• X 5

^{: numero dipedineneremangiate dalbian o}

• X ₆

^{: numero dipedinebian he mangiate dalnero}

V ^∗ (b) = w 0 + w 1 x ₁ + w 2 x ₂ + w 3 x ₃ + w 4 x ₄ + w 5 x ₅ + w 6 x ₆

Esempio di training: oppiaordinata della forma

< b, V _train (b) >

^essendo

b

^{lostato della s a hiera e}

V _train (b)

^{il valoreasso iato adesso. Esempio ditraining:}

< 3, 0, 1, 0, 0, 0, +100 >

^{: ilbian o havinto.}

Gli esempi di training disponibili per l'apprendimento sono però di tipo indiretto: le informazioni

disponibili sonosolo vittoriaos ontta (quindi dine partita). Bisogna:

•

^{Costruire una pro edura he determini gli esempi di training a partire} dall'esperienza indiretta disponibileallearner

•

^{Modi are ipesi}

w

^{in modotale da} approssimarealmeglio lafunzionetarget

V

Si habisogno quindidi esempi he assegninoagli statidella s a hiera unpunteggio Perglistati naliè

fa ile mentre per gli stati intermedi? Poniamo il valore asso iato a ias uno stato intermedio uguale al

valore dello stato su essivo:

Bisognadeterminare ipesi

w

^{inmodo tale daadattare al massimo(best t)}l'algoritmo agliesempi di addestramento

< b, V _train (b) >

^{Regola Least Mean Squares (LMS): si denis e la migliore hypothesis o}

insieme dei pesi omequella/o he minimizzal'errore quadrati o

E

^{: (}

P (v train (b) − v ^∗ (b)) ²

⁾

Regola LMS per l'aggiornamento dei pesi w: Per ogni training example

< b, V train (b) >

^{Cal ola on i}

pesi attuali

V ^∗

^{. Aggiorna ias un peso}

w _i

^{on laregola}

w i = w i + η(v train (b) − v ^∗ (b))x i

dove

η

^{è una ostante}

(0, 1)

^{he moderalavelo ità di}aggiornamento deipesi

w

^.

6.2.3 S hemadiun sistema generale diapprendimento

Il progetto ompleto diunLearning System prevede:

modulo Performan e System è il modulo he gio a a dama utilizzando la

V ^∗

^{La sua} performan e migliora on ilnumero dipartite gio ate

modulo Criti prendeininput unapartitae produ e esempiditraining

modulo Generalizer implementa la LMS rule modi ando i pesi

w

(generalizza sempre di più l'ipotesi

V ^∗

⁾

modulo ExperimentGenerator prende in input la ipotesi

V ^∗

^{orrente e genera un nuovo problema da}

esplorare (una nuova partita)

6.3 Con ept Learning

6.3.1 Denizioni

Learning indurre funzionigenerali da esempiparti olari ditraining

Con ept learning a quisire ladenizione diuna ategoria generale datoun insieme diesempi positivie

negativi della ategoria stessa

Best Fit hypothesis determinarel'ipotesi

h

^{hemeglio siadatta agli esempiditraining}

General-to-Spe i introduzione nello spazio delle ipotesiHdiun ordinamento parziale

Find-s/Version Spa e studio dialgoritmi he onvergonoinH all'ipotesih orretta.

Nel Con eptLearning sitratta di

Inferenziare automati amente una funzioneLearning booleanaa partiredall'insieme deitrai-

ning examples

< input, output >

Adesempio,seilTargetCon eptèGiorniin uiilmioami oAldoprati ailsuosportd'a quapreferito,

datoun training setdiinput, il Con eptLearning portaad apprendere a predireil valore diEnjoySport

perungiorno arbitrario,sullabase degli attributi delgiorno stesso.

6.3.3 Con ept Learning ome ri er ainH

Perla rappresentazione della funzione ipotesi

h

^, nell'ipotesi sempli e, ogni ipotesih onsiste nell'unione deivin oli espressi negliattributi ammessi nella singolaistanza. Possibilerappresentazione:

•

^{Un vettore di 6} elementi/vin oli he spe i ano i valori dei 6 attributi Sky, AirTemp, Humidity, Wind,Watere Fore ast

•

^{Perogniattributo, l'ipotesipotrà ontenere iseguenti valori:}

 ?

→

^ognivalore dell'attributoè a ettabile

 Il valoretra quelli onsentiti

 0

→

^{nessunvalore per}quell'attributo

•

^{Se una istanza x soddisfa tutti i vin oli} dell'ipotesi h allora h lassi a x ome esempio positivo:

h(x) = 1

Es. di ipotesi h:

<?, Cold, High, ?, ?, ? >

^{. Aldo prati a lo sportsolo nei giorni freddi on umidità alta.}

Ipotesih piùgenerale

<?, ?, ?, ?, ?, ? >

^{: ognigiornoè buonoperfaresportd'a quaIpotesihpiùspe i a}

< 0, 0, 0, 0, 0, 0 >

^{: nessun giornoè buono perfaresport d'a qua}

Denizioni:

Insieme delle istanze X l'insieme di items sui quali il on etto è denito. (Insieme di tutti i possibili

giorni)

Target Con ept la funzione/ on ept he deve essere appresa. In generale può essere qualunque

funzione booleana denitasu X: : X->[0,1℄

Training ExamplesD : formato da n istanze

x ∈ X

^{insieme a n valori} orrispondenti (x): <x, (x)>.

Se (x)=1 siparla diesempipositivi mentre per (x)=0 siparla diesempinegativi

Insieme H insieme di tutte lepossibiliipotesih andidate alla determinazione dellafunzione target

Obiettivo determinare

h ∈ H

^{tale he}

h(x) = c(x)

^{pertutti gli}

x ∈ X

Dati:

Istanze X giorni possibili, ias uno dei quali des ritto dagli attributi: Sky (Sunny, Cloudy e Rainy),

AirTemp(Warm, Cold),...

Ipotesi H ias unaipotesih èdes ritta dall'unione divin oli sugliattributi 1,...,6 +<?>e <0>

Con etto Target C EnjoySport: X->0,1

Esempi ditraining D esempipositivie negativi della funzionetarget

Determinare una ipotesi

h ∈ H

^{tale he h(x)= (x)}

∀x ∈ X

^.

6.3.4 Con ept Learning as Sear h

Il on ept learning può essere visto ome il ompito ditrovarela funzione h attraverso una ri er a nello

spazio HObiettivodella ri er ainH:trovarelafunzioneh he meglioapprossimi suitraining examples

(best th). È ne essariodunquelo studiodialgoritmi e te ni he diri er a inH.

Siintrodu e nell'insiemeHunordinamento hefa ilitilari er adellafunzioneh. Ogniistanza lassi-

ata omepositivada

h ₁

^è lassi ata omepositivaan heda

h ₂

^{, ioè}

h ₂

^{piùgeneraledi}

h ₁

^. L'ordinamento è quindi dal più spe i o al più generale. L'ordinamento parziale

≥ g

^{proposto gode della proprietà di}

riessività,diantisimmetria edi transitività.

Consente lari er adell'ipotesipiùspe i a:

1. Inizializza halla ipotesipiùspe i a inH.

2. Perogni istanzapositiva ditraining xe perogniattributo on vin olo

a i

^{inh,seil vin olo}

a i

^non

è soddisfattoda xallorasostituis i

a _i

^{inh on ilvin olo piùgenerale}soddisfatto dax È quindipiùspe i a rispettoa tuttele ipotesifornite.

hdiFind-Sèiltarget on ept? Find-Snon igarantis e henonesistanoaltreipotesihinH onsistenti

on idati. Civorrebbe unalgoritmo he dessemaggiori informazioni sullospazioH eh. Per hè predilire

l'ipotesi piùspe i a? Quanto sono onsistenti gli esempi di training? Find-S può essere guidato male

dalrumore(ignorando esempinegativi). Vorremmounalgoritmo hetenesse ontodelrumore neidatiSe

esistono piùipotesih onsistenti on idati?

La risposta stanelVersionSpa eed altrialgoritmi.

6.3.6 Version Spa e

Una ipotesihè onsistente onuninsiemeditrainingexamplesDseesoloseh(x)= (x)perogniesempio

<x, (x)>inD.

Il versionspa eè il sottoinsiemediHformato da tutte leipotesih onsistenti inD

L'algoritmoList-Then-Eliminatefornis eilsetdiipotesi onsistente oniltrainingsetedappartenente

al trainingset.

Version Spa e: lo rappresentiamo on i suoi membri più generali e meno generali. Essi formano due

insiemidi onne,GedS(GeneraleSpe i ) hedelimitanoilversionspa edentrolospazioparzialmente

ordinato delle ipotesi.

AlgoritmodiapprendimentoCandidate-Elimination Cal olailVersionSpa e ontenentetutteleipotesi

di H he sono onsistenti on una sequenza osservata di esempi di training. Parte inizializzando il VS

all'insieme ditutte leipotesiinH,ossiainizializzando Ged S.

G ₀

^{{<?,?, ?,?, ?, ?>}}

S ₀

^{{<0, 0,0,0,0,}

0>} L'algoritmo ritornailVS ontenente tutte leipotesi onsistenti ongli esempi esolo quelle.

Converge all'ipotesi h orretta a patto he non i siano errori negli errori di training e esista in H

l'ipotesih. Può onvergere an he adun insieme vuoto.

7 Logi a Fuzzy

Le te ni he di ontrollo fuzzy sono oggi estensivamente utilizzate in molti settori; tra questi si itano

appare hiature di largo onsumo ome lavatri i e tele amere ma an he impianti di depurazione delle

a quee ambiautomati idivetture diprestigio. Allabasediquestoappro ioèingenerelarealizzazione

di un sistema di ontrollo he in orpora e emula, tramite regole, la onos enza di esperti del settore.

Altreappli azioni sviluppatere entementeriguardanoil trattamento didatisensoriali per l'estrazione di

informazioni inpresenza diforti in ertezze nonstrutturate.

Quandousareil ontrollointelligente fuzzy? Quandoitasksonobenposti,sihannomodelliadabilie

onos enzequantitative siutilizzanometodidi ontrollo lassi i. Vi eversa,quandoitasksono omplessi,

modelliin erti e unelevato osto della onos enza quantitativa siappli a inve e il ontrollo intelligente.

All'internoditales elta, sela onos enzaqualitativa èdisponibileedèutilesiusanometodi Rule based

o algoritmi i (fuzzy). Se inve e la onos enza qualitativa non è sfruttabile, si adottano appro i ad

apprendimento (Learning), omelereti neurali.

7.1 Insiemi Fuzzy

Un elemento

x

dell'insiemeuniversale

U

^puòappartenereomenoaduninsieme

A

^{. L'insieme}

A

^èdenito

dalla suaf n. aratteristi a:

µ _A : U → {0, 1}

⁽⁷⁾

µ A = A(x) =

( 1

^se

x ∈ A

0

^{altrimenti (8)}

Ho quindisolo valoridis reti: 0 o1.

proposizioni, al olandoil gradodiverità diun'aermazione. Se

U

^{èdis reto,si puòenumerareil fset.}

Ilproblemadiquestoappro ioèdeterminarequalèl'andamentogiusto dellafunzione. Las eltadella

funzione aratteristi a è legata infatti alla soggettività, all'arbitrarietà. La dierenza signi ativa della

logi a fuzzy rispetto alle altre logi he si può notare on il seguente esempio. Se la domanda è: C'è un

panino olsalameinfrigo? è larispostaha valore

0.5

^,selainterpretiamo ome:

probabilità signi a forse

misura signi a he 'èmezzo panino

fuzzy signi a he 'è qual osa (magaripane e salameseparati, oppure unpaninoalpros iutto, ...)

Oraelen hiamo i on ettidibasedegli insiemi fuzzy

A(x)

^:

supporto

x : A(x) > 0

altezza

max(A(x))

^{. Spesso sinormalizzaa 1.}

ardinalità

card(A(x)) = P A(x i )

^{. Valeper}

U

^{dis reto}

α

^{- uts}

A α = {x ∈ X : A(x) > α}

^{. È un on etto utile per des rivere i fuzzy set e per} omprendere al une proprietà. È un insieme risp. Nella denizione,

α

^{è variabile, e il valore}

A _α

^{potrà essere}

variinsiemi di

x

spezzati, tali per uilaproprietà vale.

7.1.1 Operatori logi i

Per introdurli usiamo un'appro io assiomati o: sono funzioni he soddisfano assiomi desiderabili.

Assiomi peril omplemento

c : [0, 1] → [0, 1]

^:

1. ondizioni al ontorno:

c(0) = 1

^,

c(1) = 0

2. monotona non de res ente:

a < b → c(a) ≥ c(b)

3.

c

^{èuna funzione ontinua (non} indispensabile) 4. funzione involutiva:

c(c(x)) = x

^(non indispensabile)

Assiomi perl'unione

u : [0, 1] × [0, 1] → [0, 1]

^{(altra notazione:}

∨

^):

1. ondizioni al ontorno:

u(0, 0) = 0

^;

u(0, 1) = u(1, 0) = u(1, 1) = 1

2.

u(a, b) = u(b, a)

3. se

a < a ^′

^e

b < b ^′

^,allora

u(a, b) < u(a ^′ , b ^′ )

4. proprietà distributiva:

u(u(a, b), c) = u(a, u(b, c))

5.

u

^{è unafunzione ontinua (non} indispensabile) 6. idempotenza:

u(a, a) = a

^(non indispensabile)

Assiomi perl'intersezione

i : [0, 1] × [0, 1] → [0, 1]

^{(altranotazione:}

∧

^):

1. ondizioni al ontorno:

i(1, 1) = 1

^;

i(0, 1) = i(1, 0) = i(0, 0) = 0

2.

i(a, b) = i(b, a)

3. se

a < a ^′

^e

b < b ^′

^,allora

i(a, b) < i(a ^′ , b ^′ )

4. proprietà distributiva:

i(i(a, b), c) = i(a, i(b, c))

5.

i

^{è unafunzione ontinua (non} indispensabile) 6. idempotenza:

i(a, a) = a

^(non indispensabile) Le forme piùimpiegate sono:

c(x) u(a, b) i(a, b)

^Nome

u

^ed

i

1 − x max(a, b) min(a, b)

^{MaxMin (MM)}

a + b − ab ab

^{PRod (PR)}

min(1, a + b) 1 − min(1, 2 − a − b)

^BS