Lo scopo di questo paragrafo è descrivere alcune tecniche di classi cazione binaria e multiclasse che utilizzano metodi per il calcolo degli autovalori come nucleo computazionale e determinare il loro ruolo nell'ambito dei modelli matematici per l'apprendimento.
Descriveremo un modello per l'apprendimento che rappresenta una ge- neralizzazione della classi cazione binaria delle SVM che abbiamo visto nel paragrafo (2.3).
Dato l'insieme test Sm = (xi, yi)i=1m , con xi ∈ Rn, yi ∈ R de niscano una
funzione di tipo Kernel K(t, s) de nito positivo, come ad esempio il Kernel di Mercer:
K(x, xT) = e−kx−xT k22σ2 (2.60)
Allora possiamo introdurre la funzione:
f (x) =
m
X
i=1
dove c ∈ Rm è soluzione di
(mγI + K)c = y (2.62)
con I matrice identità e K è la matrice de nita positiva con elementi ki,j =
K(xi, xj). Vediamo brevemente cos'è la costante γ. Il condizionamento del
nostro problema è buono se my è grande: infatti (mγI + K) ha gli stessi autovalori di K traslati di mγ, allora se questata quantità tende all'in nito il rapporto |λmax|
|λmin| (che è la sensibilità delle soluzioni alle variazioni dei da-
ti) tende ad 1. Però in questo caso diventa di cile trattare numericamente una matrice che ha elementi sulla diagonale con molti ordini di grandezza di dierenza rispetto agli altri. Il nostro problema diventa quindi mal posto e abbiamo bisogno di un metodo di sempli cazione per poterlo risolvere. Uti- lizzando la regolarizzazione di Tikonov ricaviamo la costante γ che abbiamo inserito in (2.62). Questa funzione è tale che f(xi) = yi e per un certo x 6= xi
fornisce un valore y che dipende dall'insieme test (xi, yi)mi=1.
L'algoritmo descritto può essere derivato dal metodo di regolarizzazione di Tikonov, partendo dalla ricerca della funzione f che minimizza:
1
m
X
i=1
m(f (xi) − yi)2 (2.63)
e aggiungendo un termine che assicuri che il problema sia ben posto secondo Hadamar (cioè che esista una soluzione unica e che la funzione che ai dati associa la soluzione sia continua):
1
m
X
i=1
m(f (xi) − yi)2+ γkf k2. (2.64)
Nel caso in cui y sia binario e si usi la funzione di perdita: V (f(x, y)) = (f (x) − y)2, si ottiene una PSVM, come abbiamo visto nel paragrafo psvm;
se si usa V (f(x, y)) = (1 − yf(x))+ si ottiene la stessa classi cazione delle
SVM, come nel paragrafo svm.
Mangasarian ha mostrato come ricondurre il problema di classi cazione binaria:
min
ω,γ6=0
kAω − γk
kBω − γk, (2.65)
problema agli autovalori generalizzato. infatti, posto: G = [A − e]T[A − e], H = [B − e]T[B − e], z = [ωT γ]T, l'equazione (2.65) diventa: min z∈Rm zTGz zTHz, (2.66)
quoziente di Raleigh del problema agli autovalori generalizzato Gx = λHx. Detti zmin = [ω1 γ1] e zmax = [ωm γm] gli autovalori di minimo e massimo
modulo rispettivamente, ne segue che ciascun punto di A dista da xTω
1−γ1 =
0meno che da xTω
m− γm = 0e , allo stesso modo, ciascun punto di B dista
da xTω
m− γm = 0 meno che da xTω1− γ1 = 0.
Questi iperpiani che abbiamo trovato sono tra loro incidenti e quindi molto diversi da quelli paralleli che si ottengono mediante le SVM. Gli studi fatti per problemi non separabili continuano ad essere validi ed è possibile dedurne la formulazione nel caso degli autovalori.
Prima di concludere vogliamo raccontare brevemente i passi in avanti fatti dalla ne degli anni novanta per implementare algoritmi in grado di calcolare in maniera e ciente gli autovettori corrispondenti ad autovalori estremali di una matrice M simmetrica, sparsa e di grandi dimensioni. Uno di questi è basato sul metodo proposto da Lanczor, che utilizza una proiezione su sottospazi di Krylov, cioè generati dai vettori che si ottengono dalla iterazioni del metodo delle potenze:
K(M, v) =span{v, Mv, . . . , Mk−1v}.
In questo sottospazio l'operatore assume forma tridiagonale:
T = α1 β1 β2 α2 ... ... ... ... ... ... βk−1 βk−1 αk
Si può dimostrare che, al crescere di k, gli autovalori di T costituiscono approssimazioni per difetto sempre migliori degli autovalori estremali della
matrice M. Poiché T è tridiagonale e di dimensione molto minore di M, è possibile risolvere problemi di grandi dimensioni in maniera accurata e veloce. Questo è uno dei metodi più soddisfacenti per la soluzione di questo tipo di problemi, soprattutto nel caso hermitiano.
Al ne di ottenere potenze di calcolo su cienti per risolvere grandi pro- blemi in un tempo limitato, è necessario utilizzare multiprocessori a memoria distribuita, come ad esempio i cluster di PC.
L'algoritmo di Lanczos, nella sua formulazione originaria, non si presta ad una e ciente implementazione su tali calcolatori. Per tale motivo è pos- sibile prendere in considerazione una versione a blocchi, che utilizza s vettori alla volta per eettuare le proiezioni; esiste quindi un algoritmo parallelo per queste architetture. Esso è basato su una distribuzione dei dati tra i proces- sori di tipo block-column wrap arround, che consiste, nel caso di una matrice, nell'assegnare blocchi di colonne di ugual dimensione a ciascun processore, in maniera ciclica. Questa decomposizione dei dati risulta la più conforme alla topologia sottostante. Grazie a questa distribuzione è possibile eettuare una parallelizzazione e ciente di alcune operazioni dell'algebra lineare nu- merica di base: il prodotto di due matrici dense, di una matrice sparsa per una matrice densa e la fattorizzazione QR di una matrice.
I risultati mostrano le potenzialità dell'approccio proposto per la paral- lelizzazione dell'algoritmo di Lanczos. Inoltre a partire da tali risultati è stata presentata una riorganizzazione di questo algoritmo a blocchi che, su architetture a memoria distribuita di tipo cluster, raggiunge prestazioni più elevate dell'algoritmo originale. Infatti è possibile dimostrare che una diret- ta parallelizzazione del classico algoritmo di Lanczos a blocchi presenta una perdita di e cienza quando la sparsità della matrice diminuisce.
Il fatto che un problema sia ben posto nel senso di Hadamar non di- ce nulla relativamente all'eetto sulle soluzioni delle variazione nei dati. Il poter determinare una formulazione del problema in cui la funzione che ai dati associa le soluzioni sia lipschitziana, con costante di Lipschitz picco- la, assicura una minore sensibilità del problema e una sua miglior soluzione mediante strumenti di calcolo. A prima vista, le formulazioni mediante pro- blemi agli autovalori hanno il vantaggio che il condizionamento del calcolo degli autovettori dipende dalla distanza del relativo autovalore dal resto del- lo spettro e poiché si è interessati agli autovalori estremali, esistono tecniche che permettono di migliorare tale caratteristica.
Bibliogra a
[1] Aleksandrow P.S., Combinatorial Topology. Graylock Press, Albany, N.Y., 1960.
[2] Astorino A. e Guadioso M., Polyhedral Separability thtough Successi- ve LP . Journal of Optimization Theory and Applications, vol. 112(2) (2002), pp. 265-293.
[3] Astorino A. e Guadioso M., Spherical separation and kernel transformations for classi cation problems.
[4] Banach S., Sur les lignes recti ables et les surfaces dont l'aire est nie. Fundam. Math., Vol.7, 1925, pp.225-237.
[5] Bazaraa M.S., A Theorem of the Alternative with Applications to Con- vex Programming: Optimality, Duality, and Stability. Jou.of Mathem. Analysis and Appls., Vol.41, 1973, pp.701-715.
[6] Bennett K.P., Combining Support Vector and Mathematical Program- ming Methds for Induction. Advances in Kernel Methods-Support Vec- tor Machines, Schoelkopf A., Burges C., Smola A., MIT press (1999), pp. 307-326.
[7] Bennett K.P. e Mangasarian O.L., Robust linear programming discri- mination of two linearly inseparable sets. Optimization Methods and Software, vol. 1 (1992), pp. 23-34.
[8] Bennett K.P. e Mangasarian O.L., Bilineare Separation of Two Sets in n-Space. Computational Optimization and Applications, vol. 2 (1993), pp. 202-227.
[9] Bigi G. e Pappalardo M., Regularity Conditions for the Li- near Separation of Sets. Jou.Optimiz.Th.Appls., Vol.99, No.2,1998, pp.533-540.
[10] Bradley P.S. e Mangasarian O.L., Feature Selection via Concave Mini- mization and Support Vector Machines. Machine Learning Proceeding of the Fifteenth International Conference, Shavlik, San Francisco (1998), pp. 82-90.
[11] Bradley P.S., Mangasarian O.L. e Street W.N., Clustering via Concave Minimization. Advances in Neural Information Processing Systems, vol. 9 (1997), pp. 368-374.
[12] Bradley P.S., Mangasarian O.L. e Street W.N., Feature Selection via Mathematical Programming. Journal on Computing, vol. 10 (1998), pp. 209-217.
[13] Braglia M., Bevilacqua M., Frosolini M e Montanari R., Failure Rate Prediction with Arti cial Neural Networks. (2004).
[14] Castellani G. e Giannessi F., Decomposition of Mathematical Pro- grams by means of Theorems of the Alternative for Linear and Nonli- near Systems. Proceedings of the 9th Inter. Symposium on Mathema- tical Programming, Hungarian Academy of Sciences, Budapest, 1979, pp.423-439.
[15] Craven B.D., Gwinner G. and Jeyakumar V., Nonconvex Theorems of the Alternative and Minimization. Optimization, Vol.18, No.2, 1987, pp.151-163.
[16] Craven B.D. and Koliha J.J., Generalizations of Farkas Theorem. SIAM Jou. Mathem. Analysis, Vol.8, No.6, 1977, pp.983-997.
[17] Craven B.D. and Mond B., Transposition theorems for cone-convex functions. SIAM Jou.Appl.Mathem., Vol.24, No.4, 1973, pp.603-612. [18] Dax A. and Sreedharan V.P., Theorems of the Alternative and Duality.
Jou. Optimiz. Th. Appls., Vol.94, No.3, 1997, pp.561-590.
[19] Dinh The Luc, Theorems of the Alternative and their applications in Multiobjective Optimization. Acta Math.Hungarica, Vol.45, No.3-4, 1985, pp.311-320.
[20] Farkas J., Über die Theorie der einfachen Ungleichungen. Jou. Reine Angew. Mathem., Vol. 124, 1902, pp.1-27.
[21] Ferrero O., Theorems of the Alternative for Set-Valued Functions in In nite-Dimensional Spaces. Optimization, Vol.20, No.2, 1989, pp.167- 175.
[22] Fung G. e Mangasarian O.L. Proximal Support Vector Machines Classi ers, Computer Sciences Department, University of Wisconsin. [23] Giannessi F., Constrained Optimizated and Image Space Analysis. Vol
1, cap. 4.
[24] Giannessi F., Theorems of the Alternative, Quadratic programs, and Complementarity Problems. pp.151-186.
[25] Giannessi F., Theorems of the Alternative and Optimality Conditions. Tech. Report No.83, Dept. of Mathem., Univ.of Pisa, Sect. of Optimiza- tion, 1982, pp.1-30. Published with the same title in Jou. Optimiz. Th. Appls., Vol.42, No. 3, 1984, pp.331-365.
[26] Giannessi F., Theorems of the Alternative for multifunctions with ap- plications to Optimization. Necessary conditions. Tech. Paper No.131, Optimiz. Series, Dept. of Mathem., Univ. of Pisa, Pisa, Italy, 1986, pp.1-127.
[27] Giannessi F., Theorems of the Alternative for Multifunctions with Ap- plications to Optimization: General Results. Jou.Optimiz.Th.Appls., Vol. 55, No.2, 1987, pp.233256.
[28] Giannessi F., Theorems of the Alternative and Optimization. Vol.V, pp.437-444.
[29] Golikov A.I. and Evtushenko Yu.G., Theorems of the Alternative and their Applications in Numerical Methods. Computational Mathematics and Mathematical Physics, Vol.43, No.3, 2003, pp.338-358.
[30] [19] Gordan P., Über die Au õsungen linearer Gleichungen mit reelen Coe cienten. Mathematishe Annalen, Vol.6, 1873, pp.23-28.
[31] Grippo L. Sciandrone M., Metodi di Ottimizzazione per le Reti Neurali. Scuola CIRO 2002, Agnetis A., Di Pillo G., (2002).
[32] Guarracino M., Sui metodi di classi cazione nei modelli matematici per l'apprendimento. 2004
[33] Hahn H., Über lineare Gleichungen in lineare Räumen. Jou.Mathem., Vol.157, 1927, pp.214-229.
[34] Heinecke G. e Oettli W., A Nonlinear Theorem of the Alternative without Regularity Assumption. Jou.of Mathem.Analysis and Appls., Vol.146, No.2, 1990, pp.580-590.
[35] Illés T, e Kassay G., Farkas Type Theorems for Generalized Con- vexities. Report No.94-23 of Tech.Univ.Delft, Fac.of Tech.Mathem.and Informatics, 1994, pp.1-12.
[36] Jeyakumar V., Convexlike Alternative Theorems and Mathematical Programming. Optimization, Vol.16, No.5, 1895, pp.643-652.
[37] Jeyakumar V., A generalization of a minimax theorem of Fan via a theorem of the alternative. Jou. of Optimiz. Theory and Appls., Vol.48, No.3, 1986, pp.525-533.
[38] Jeyakumar V., A General Farkas Lemma and Characterization of Optimality for a Nonsmooth Program involving Convex Processes. Jou.Optimiz.Th.Appls., Vol.55, No.3, 1987, pp.449-461.
[39] Lehmann R. and Oettli W., The Theorem of the Alternative: Key-Theorem, and the Vector Maximum Problem. Mathematical Programming, Vol.8, 1975, pp.332-344.
[40] Li Z., A Theorem of the Alternative and its Applications to the Op- timization of Set-Valued Maps. Jou.Optimiz.Th.Appls., Vol.100, No.2, 1999, pp.365-375.
[41] MacLinden L., Duality Theorems and Theorems of the Alternative. Proc.of Annals of Mathem.Soc., Vol.53, 1975, pp.172-175.
[42] Mangasarian O.L., A stable Theorem of the Alternative: an extension of the Gordan Theorem. Linear Algebra and its Appls., Vol.41, 1981, pp.209-223.
[43] Mangasarian O.L., Linear and Nonlinear Separation of Patterns by Linear Programming. Operations Research, Vol.13, 1965, pp.444-452.
[44] Mangasarian O.L., Mathematical Programming in Data Minning. Data Minning and Knowledge Discovery, Vol.1 (1997), pp.183-201.
[45] Mangasarian O.L., Nonlinear Programming. McGraw-Hill, New York 1969.
[46] Martinez-Legaz J.E. e Seeger A., Yuan's Alternative Theo- rem and the Maximization of the Minimum Eigenvalue Function. Jou.Optimiz.Th.Appls., Vol.82, No.1, 1994, pp.159-167.
[47] Mastroeni G. e Pappalardo M., Separation and regularity in the Image Space. In New Trends in Mathematical Programming, Series in Applied Optimization, Vol.13, Kluwer, Dordrecht, 1998, pp.181-190.
[48] Mastroeni G. e Pellegrini L., Linear separation for G-semidierentiable problems. Proceedings of the Conference Convessitá e Calcolo Pa- rallelo (Convexity and Parallel Computation). G.Giorgi and F.Rossi Eds., Publisher Univ.of Verona, Via dell'Artigliere,19-Verona-Italy, 1997, pp.187-203.
[49] Mazzoleni P., Some generalizations of the Theorem of the Alternative for functions and multifunctions. Proc.of the Dept.of Applied Mathem. of University of Venice, Vol.XIX, 1982, 39-51.
[50] Motzkin T.S., Beiträge zur Theorie der Linearen Ungleichungen. Inaugural Diss. Basel, Jerusalem, 1936.
[51] Nehse von R., Some General Separation Theorems. Mathem.Nachr., 1978, pp.319-327.
[52] Oettli W., A new version of th Hahn-Banach Theorem. Proc.of the Int.Congress on Mathematical Programming, April 1981 (Rio de Janeiro), North-Holland, 1984, pp.289-295.
[53] Prager W., Optimal arrangement of the beams of a rectangular grillage. In Problemi attuali di Meccanica teorica e applicata (Present problems of theorical and applied Mechanics), Proceedings of the Int.Confenence in Memory of M.Panetti, Published by Academy of Sciences of Turin, Turin, 1977, pp.239-249.
[54] Rosenblatt F., Principles of Neurodynamics: Preceptrons and Theory of Brain Mechanism. Spartan Books, Washington 1962.
[55] Shawe-Taylor J., Cristianini N., Support Vector Machines and other kernel-based learning methods. Cambridge University Press, 2000 [56] Simons S., Variational Inequalities via the Hahn-Banach Theorem.
Archiv der Mathematik, Vol.31, Fasc.5, 1978, pp.482-490.
[57] Simons S., Minimax and Variational Inequalities. Are they of Fixed- Point or Hahn-Banach type?. In Game Theory and Mathematical Economics, O.Moeschin and D.Pallaschke Eds., North-Holland, 1981, pp.379-387.
[58] Slater M.L., A Note on Motzkin's Transposition Theorem. Econometrica, Vol.19, 1951, pp.185-186.
[59] Stiemke E., Über positive Lösungen homogener linearer Gleichungen. Mathematische Annalen, Vol.76, 1915, pp.340-342.
[60] Tricomi F.G., Integral Equations. Interscience, 1957.
[61] Yang X.M., Alternative Theorems and Optimality Conditions with weakened convexity. OPSEARCH, Vol.29, No.2, 1992, pp.125-135. [62] [44] Yang X.M., Yang X.Q. and Chen G.-Y., Theorems of the Alter-
native and optimization with Set-Valued Maps. Jou.Optimiz.Th.Appls., Vol.107, No.3, 2000, pp.627-640.
[63] Vapnik V.N., The NAture of Statistical Learning Theory. Springer- Verlag, New York 1995.
[64] Zalinescu C., A generalization of the Farkas Lemma and Applications to Convex Programming. Jou.Mathem.Analysis Appls., Vol.66, No.3, 1978, pp.651-678.
[65] Zalmai G.J., A transposition Theorem with Applications to Con- strained Optimal Control Problems. Optimization, Vol.20,No 3, Academic-Verlag, Berlin, 1989, pp.265-279.