Solution of classification problems via computational geometry methods

Si descrivono due importanti problemi che, pur nascendo in contesti applicativi diversi, presentano notevoli analogie: trovare la sfera piu' piccola che contiene un dato insieme di punti (Minimal Enclosing Ball), e trovare una superficie di separazione tra due insiemi di punti appartenenti a due diverse classi (classificazione binaria). Entrambi possono essere riformulati come problemi di ottimizzazione non lineari con vincoli, il cui duale e' un problema di programmazione quadratica. Ed entrambi sono caratterizzati dal fatto che solo una parte, solitamente molto piccola, dei punti assegnati e' rilevante per la soluzione: il cosiddetto "coreset", nel contesto MEB, o i "support vectors" nei problemi di classificazione. Sulla base di queste analogie si descrivono i metodi CVM (Core Vector Machines) per risolvere problemi di classificazione binaria, riportando i risultati sperimentali ottenuti.