Seminario Interdipartimentale di Algoritmica
 
 
 

ore 11 The dissymmetry theorem for trees
Prof. Prof. Pierre Leroux
Universitè du Quebec à Montreal

ore 12 Il Perceptrone al second'ordine
Prof. Nicolò Cesa-Bianchi,
DTI, Università di Milano

Dipartimento di Scienze dell'Informazione - DSI
via Salaria 113, III piano
Aula Seminari

Abstract (Leroux):
Informally, a species is a class of labelled combinatorial structures which is closed under relabelling isomorphisms. Natural operations are defined on species, corresponding to the associated generating functions. The dissymmetry theorem for trees expresses the species of trees in terms of rooted trees. There results a number of identities on the generating functions, for example Otter's formula which is used for the enumeration of unlabelled (free) trees. Generalizations are possible to other classes of tree-like structures: structured (binary, plane, ...) trees, cactus, 2-trees, etc.

This will be an introductory talk.

Abstract (Cesa-Bianchi): Recenti progressi nel campo della pattern classification, come l'impiego dei metodi basati sulle funzioni kernel, hanno portato alla ribalta un algoritmo classico come il Perceptrone di Rosenblatt, che e` ora in grado di offrire prestazioni paragonabili allo stato dell'arte in numerosi settori applicativi. In questo seminario presentiamo una nuova variante del Perceptrone in grado di sfruttare specifiche proprieta` spettrali dei dati. L'analisi di questa variante mostra che il numero di errori di classificazione commessi durante il training e` maggiorabile in funzione della distribuzione degli autovalori della matrice di correlazione empirica dei dati. Questo porta ad ottenere in determinate situazioni delle prestazioni significativamente migliori rispetto al Perceptrone classico, come mostriamo con alcuni semplici risultati sperimentali.

Lavoro in collaborazione con Alex Conconi e Claudio Gentile