mod_C

Ministero dell'Universita' e della Ricerca scientifica e tecnologica

Programmi di ricerca cofinanziati - Modello C
Rendiconto di unita' di ricerca - ANNO 1997
prot. 9701091751_023

1. Area Scientifico Disciplinare principale 01: Scienze matematiche

2. Coordinatore Scientifico del programma di ricerca

3. Titolo del programma di ricerca

ANALISI NUMERICA: METODI E SOFTWARE MATEMATICO

4. Responsabile Scientifico dell'Unità di ricerca

5. Titolo del programma dell'unità di ricerca

Studio e confronto di metodi di programmazione quadratica per le Support Vector Machine

6. Settore principale del Programma di Ricerca: A04A - Analisi numerica

7. Finanziamenti assegnati all'unità di ricerca

8. Obiettivo della ricerca eseguita

Sviluppo di metodi efficienti basati sulla teoria delle Support Vector Machines per risolvere problemi di classificazione e di approssimazione in presenza di molti dati e confronti con altre tecniche esistenti.

9. Descrizione della Ricerca eseguita e dei risultati ottenuti

La ricerca eseguita nell'ambito di questo progetto ha riguardato lo studio di proprieta' teoriche, l'implementazione di metodi per il calcolo e applicazioni di Support Vector Machine. Una Support Vector Machine e' un metodo per determinare la superficie di separazione di un insieme di punti appartenenti a due classi differenti basato sulla soluzione di un problema di programmazione quadratica con vincoli lineari la cui dimensionalita' e' pari al numero dei punti (e che pertanto puo' essere o diventare molto elevata). Questa superficie e' identificata a partire da un sottoinsieme dei punti in questione (i support vector, ovvero i punti per i quali i vincoli del problema sono attivi) e viene utilizzata per determinare la classe di appartenenza di punti nuovi per i quali la classe non sia nota a priori. 

Le idee principali alla base delle Support Vector Machine sono estendibili anche al caso di regressione o stima di funzioni. In questo caso i support vector sono il sottoinsieme dei punti disponibili effettivamente utilizzati per stimare il valore della funzione in nuovi punti. 

STUDIO DELLE PROPRIETA' TEORICHE 

Per quanto riguarda le proprieta' teoriche si e' studiata la dipendenza del numero di Support Vector dalla dimensione dello spazio del problema e dal numero dei dati [1]. Questo studio ha consentito una migliore comprensione della struttura della soluzione relativa al problema del calcolo dei Support Vector e una caratterizzazione della dipendenza della superficie di separazione dal parametro di regolarizzazione. 

IMPLEMENTAZIONE DI METODI 

Sono stati sviluppati e confrontati diversi metodi per il calcolo delle Support Vector Machines [2]. In particolare sono stati messi a punto metodi in grado di affrontare e risolvere problemi di ottimizzazione con piu' di 10000 dati. L'idea alla base dei metodi e' quella di sfruttare la decomponibilita' del problema originale in sottoproblemi di dimensioni piu' piccola e nel raggiungimento della soluzione finale attraverso iterazioni. E' in via di completamento un lavoro sviluppato in collaborazione con l'Unita' di Modena (Dott. Luca Zanni) in cui queste tecniche sono confrontate con metodi sviluppati indipendentemente dall'Unita' di Modena per il calcolo dei Support Vector. Questi secondi metodi sembrano essere caratterizzati da una notevole stabilita' numerica e potrebbero consentire per certe scelte della funzione "kernel" una riduzione dei tempi di calcolo molto interessante. 

APPLICAZIONI 

Le Support Vector Machine sono state applicate nel caso della pattern recognition a problemi di identificazione di particelle (nel campo della Fisica delle Alte Energie), di riconoscimento di oggetti e di eventi dinamici (nel campo della Visione Artificiale) e, piu' recentemente e in collaborazione con il gruppo del Prof. T. Poggio del MIT, di riconoscimento di diverse forme tumorali (nel campo della Bioinformatica). Nel caso della regressione di funzioni, le Support Vector Machine sono state applicate al problema della stima automatica del peso di pesci di acqua dolce a partire da una serie di misure relative alla forma dei pesci stessi. 

Nel caso dell'identificazione di particelle si e' proceduto dapprima alla validazione e al confronto di tecniche classiche di pattern recognition [3]. Queste tecniche includono i "nearest neighbor", le reti neurali e tecniche basate sul principio della maximum likelihood. E' in fase di completamento un lavoro nel quale queste tecniche vengono confrontate con le Support Vector Machine su due problemi di identificazione di particelle al variare del numero di particelle osservate e in funzione dei vari parametri messi in gioco dalle SVM (tra i quali vale la pena di menzionare il parametro di regolarizzazione e la scelta della funzione "kernel") [4]. 

Nel caso del riconoscimento di oggetti si e' messo a punto un sistema in grado di effettuare il riconoscimento di oggetti 3D basato su collezioni di immagini bidimensionali e senza una conoscenza diretta della forma 3D degli oggetti stessi [5]. Questo sistema si e' rivelato molto efficace e in grado di funzionare a partire da un numero ridotto di esempii [6]. 

Nel caso del riconoscimento di eventi dinamici si e' invece sviluppato un sistema basato sull'acquisizione e l'analisi di sequenze di immagini da telecamera fissa di scene di interni [7,8]. Il sistema estrae e classifica automaticamente da una sequenza di immagini gli eventi dinamici osservati, tipicamente corrispondenti a movimenti di persone. Nella fase di apprendimento la classe degli eventi osservati e' nota al sistema, nella fase di validazione, invece, la classe e' determinata automaticamente. Le Support Vector Machine sono utilizzate sia nella fase di costruzione della rappresentazione degli eventi (fase nella quale vengono utilizzate SVM per regressione) sia nella fase di classificazione vera e propria. 

L'applicazione delle SVM per regressione e' stata rivolta al campo della stima automatica del peso di pesci a partire da misure di forma [9]. Questo problema, di grande rilevanza per gli allevamenti di pesci di acqua dolce, ha portato allo sviluppo di SVM capaci di autovalutare la propria efficacia nel valutare il peso a partire da una serie di campioni per i quali il peso sia noto. 

BIBLIOGRAFIA 

[1] M. Pontil and A. Verri 
Properties of Support Vector Machines 
Neural Computation Vol 10, 977-996 (1998) 

[2] M. Ponitl, S. Rogai and A. Verri 
Support Vector Machines: a Large Scale QP 
In High Performance Algorithms and Software in Nonlinear Optimization (R. De Leone et al. eds) 315-336 (Kluwer Academic Publishers, 1998) 

[3] M. Pallavicini, C. Patrignani, M. Pontil and A. Verri 
The Nearest-Neighbor Technique for Particle Identification 
Nucl. Instr. and Meth. A Vol 405, 133-138 (1998) 

[4] N. Barabino, M. Pallavicini, A. Petrolini, M. Pontil and A. Verri 
Support Vector Machines vs. Multi-Layer Perceptrons in Particle Identification 
Eur. Symp. Artif. Neural Networks, Bruges, 257-262 (1999) 

[5] M. Pontil, S. Rogai and A. Verri 
Recognizing 3-D Objects with Linear Support Vector Machines 
Proc. 5th Eur. Conf. Comput. Vis., Friburg, LNCS 1407: 469-483 (1998) 

[6] M. Pontil and A. Verri 
Support Vector Machines for 3-D Object Recognition 
IEEE Trans. Patt. Anal. Machine Intell. Vol. 20, 637-646 (1998) 

[7] M. Pittore, M. Campani, and A. Verri 
Learning to Recognize Visual Dynamic Events from Examples 
To appear in Int. J. Comput. Vis. (2000) 

[8] M. Pittore, C. Basso and A. Verri 
Representing and Recognizing Visual Dynamic Events with Support Vector Machines 
Int. Conf. Image Anal. and Proc. (1999) 

[9] F. Odone, E. Trucco and A. Verri 
Visual Learning of Weight from Shape Using Support Vector Machines 
Proc. British Machine Vis. Conf., Southampton, 469-477 (1998)

10. Pubblicazioni

11. Prodotti della Ricerca eseguita

La ricerca eseguita ha portato allo sviluppo e all'implementazione di metodi per il calcolo dei support vector in presenza di grandi quantita' di dati sia nel caso di pattern recognition sia nel caso di regressione di funzioni. 

Sono stati anche sviluppati e implementati versioni prototipali di sistemi di elaborazione di immagini in grado di apprendere da esempi eventi dinamici quali movimenti di persone in ambienti interni e gesti.

12. Componenti dell'Unità di ricerca che hanno effettivamente partecipato alla ricerca
Personale docente

Altro personale

Personale a contratto

13. Note relative ai componenti (p.12)

14. Risorse umane complessivamente ed effettivamente impegnate

15. Dati complessivi relativi al programma

16. Tabella delle spese sostenute: cifre spese, rimaste da pagare o impegnate(*)
(*) Da Impegnare LIMITATAMENTE a Pubblicazioni e Partecipazioni a Convegni e Congressi SOLAMENTE se inerenti i risultati della Ricerca cofinanziata per i quali si richiedera' successiva rendicontazione

Si ricorda che ogni variazione rispetto al Programma Iniziale sulla composizione delle Unità Operative e sulla diversa utilizzazione dei Fondi, doveva essere comunicata al Dipartimento Affari Economici come da nota n. 1709 del 22.7.98.

(per la copia da depositare presso l’Ateneo e per l’assenso alla diffusione via Internet delle informazioni riguardanti i programmi finanziati legge del 31.12.96 n° 675 sulla "Tutela dei dati personali")