Già da qualche tempo, durante le ricerche svolte intorno al Support Vector Clustering, ho indagato al fine di trovare delle ottimizzazioni sempre più spinte per la risoluzione del problema di addestramento di una SVM. Questo mi ha fatto inizialmente incappare nelle LS-SVM

• bibtex | link
  J. A. K. Suykens, V. T. Gestel, D. J. Brabanter, and V. J. B. De Moor, Least Squares Support Vector Machines, Singapore: World Scientific Pub. Co., 2002.
  @book{lssvm, Address = {Singapore},
  Author = {J. A. K. Suykens and T. Van Gestel and J. De Brabanter and B. De Moor, J. Vandewalle},
  Date-Added = {2007-04-28 18:32:30 +0200},
  Date-Modified = {2007-05-19 19:14:24 +0200},
  Keywords = {svm, ls-svm},
  Publisher = {World Scientific Pub. Co.},
  Title = {Least Squares Support Vector Machines},
  Url = {http://www.worldscibooks.com/compsci/5089.html},
  Year = {2002},
  Bdsk-Url-1 = {http://www.worldscibooks.com/compsci/5089.html}
}

una riformulazione delle SVM che si libera dall’onere della risoluzione di un problema di programmazione quadratica per l’addestramento, sostituendolo con la risoluzione di un sistema KKT lineare.

Dopo il seminario tenuto dal prof. Alessandro Verri nella mia univesità, riguardo la Regolarizzazione e l’apprendimento statistico, la curiosità verso le SVM “più leggere” è aumentata. Ciò mi ha portato a scoprire almeno altre due varianti interessanti di SVM che si svincolano dal problema di programmazione quadratica: le Langrangian SVM e le Core Vector Machines

• bibtex | link
  O. L. Mangasarian and D. R. Musicant, "Lagrangian Support Vector Machine Classification," Data Mining Institute, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 00-06, 2000.
  @techreport{lagrangesvm00, Address = {Madison, Wisconsin},
  Author = {O. L. Mangasarian and David R. Musicant},
  Date-Added = {2007-05-26 17:01:04 +0200},
  Date-Modified = {2007-06-19 14:25:18 +0200},
  Institution = {Data Mining Institute, Computer Sciences Department, University of Wisconsin},
  Keywords = {svm, classification, lagrangian},
  Month = {June},
  Number = {00-06},
  Title = {Lagrangian Support Vector Machine Classification},
  Url = {ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/00-06.ps},
  Year = 2000, Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGBwpZJGFyY2hpdmVyWCR2ZXJzaW9uVCR0b3BYJG9iamVjdHNfEA9OU0tleWVkQXJjaGl2ZXISAAGGoNEICVRyb290gAGoCwwXGBkaHiVVJG51bGzTDQ4PEBMWWk5TLm9iamVjdHNXTlMua2V5c1YkY2xhc3OiERKABIAFohQVgAKAA4AHXHJlbGF0aXZlUGF0aFlhbGlhc0RhdGFfEFAuLi8uLi8uLi9QYXBlcnMvTWFuZ2FzYXJpYW4vTGFncmFuZ2lhbiBTdXBwb3J0IFZlY3RvciBNYWNoaW5lIENsYXNzaWZpY2F0aW9uLnBkZtIbDxwdV05TLmRhdGFPEQI8AAAAAAI8AAIAAAlEb2N1bWVudHMAAAAAAAAAAAAAAAAAAAAAAAC+zniuSCsAAAA3IqcfTGFncmFuZ2lhbiBTdXBwb3J0IFYjMzcyMjc0LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADcidMKdlKEAAAAAAAAAAAADAAMAAAkAAAAAAAAAAAAAAAAAAAAAC01hbmdhc2FyaWFuAAAQAAgAAL7OXI4AAAARAAgAAMKdeIEAAAABABQANyKnADcbgAAAsvIAABLGAAASrQACAFZEb2N1bWVudHM6bmVtbzpEb2N1bWVudHM6VW5pdmVyc2l0YTpQYXBlcnM6TWFuZ2FzYXJpYW46TGFncmFuZ2lhbiBTdXBwb3J0IFYjMzcyMjc0LnBkZgAOAGoANABMAGEAZwByAGEAbgBnAGkAYQBuACAAUwB1AHAAcABvAHIAdAAgAFYAZQBjAHQAbwByACAATQBhAGMAaABpAG4AZQAgAEMAbABhAHMAcwBpAGYAaQBjAGEAdABpAG8AbgAuAHAAZABmAA8AFAAJAEQAbwBjAHUAbQBlAG4AdABzABIAYi9uZW1vL0RvY3VtZW50cy9Vbml2ZXJzaXRhL1BhcGVycy9NYW5nYXNhcmlhbi9MYWdyYW5naWFuIFN1cHBvcnQgVmVjdG9yIE1hY2hpbmUgQ2xhc3NpZmljYXRpb24ucGRmABMAEi9Wb2×1bWVzL0RvY3VtZW50cwAVAAIAF///AACABtIfICEiWCRjbGFzc2VzWiRjbGFzc25hbWWjIiMkXU5TTXV0YWJsZURhdGFWTlNEYXRhWE5TT2JqZWN00h8gJieiJyRcTlNEaWN0aW9uYXJ5AAgAEQAbACQAKQAyAEQASQBMAFEAUwBcAGIAaQB0AHwAgwCGAIgAigCNAI8AkQCTAKAAqgD9AQIBCgNKA0wDUQNaA2UDaQN3A34DhwOMA48AAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADnA==},
  Bdsk-Url-1 = {ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/00-06.ps}
}

• bibtex | link
  I. W. Tsang, J. T. Kwok, and P. Cheung, "Core vector machines: Fast SVM training on very large data sets," Journal of Machine Learning Research, vol. 6, pp. 363-392, 2005.
  @article{cvm05,
  author = {Ivor W. Tsang and James T. Kwok and Pak-Ming Cheung},
  Date-Added = {2007-05-26 12:49:30 +0200},
  Date-Modified = {2007-06-23 08:23:02 +0200},
  Journal = {Journal of Machine Learning Research},
  Keywords = {SVM, CVM, MEB, SVDD},
  Pages = {363–392},
  Title = {Core vector machines: Fast SVM training on very large data sets},
  Url = {http://www.cs.ust.hk/%7Eivor/publication/tsang05a.pdf},
  Volume = {6},
  Year = {2005},
  Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGBwpZJGFyY2hpdmVyWCR2ZXJzaW9uVCR0b3BYJG9iamVjdHNfEA9OU0tleWVkQXJjaGl2ZXISAAGGoNEICVRyb290gAGoCwwXGBkaHiVVJG51bGzTDQ4PEBMWWk5TLm9iamVjdHNXTlMua2V5c1YkY2xhc3OiERKABIAFohQVgAKAA4AHXHJlbGF0aXZlUGF0aFlhbGlhc0RhdGFfEFguLi8uLi8uLi9QYXBlcnMvVHNhbmcvQ29yZSB2ZWN0b3IgbWFjaGluZXMgRmFzdCBTVk0gdHJhaW5pbmcgb24gdmVyeSBsYXJnZSBkYXRhIHNldHMucGRm0hsPHB1XTlMuZGF0YU8RAlQAAAAAAlQAAgAACURvY3VtZW50cwAAAAAAAAAAAAAAAAAAAAAAAL7OeK5IKwAAADctuR9Db3JlIHZlY3RvciBtYWNoaW5lcyMzMkY0MjEucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAMvQhwn3aZgAAAAAAAAAAAAMAAwAACQAAAAAAAAAAAAAAAAAAAAAFVHNhbmcAABAACAAAvs5cjgAAABEACAAAwn2+RgAAAAEAFAA3LbkANxuAAACy8gAAEsYAABKtAAIAUERvY3VtZW50czpuZW1vOkRvY3VtZW50czpVbml2ZXJzaXRhOlBhcGVyczpUc2FuZzpDb3JlIHZlY3RvciBtYWNoaW5lcyMzMkY0MjEucGRmAA4AhgBCAEMAbwByAGUAIAB2AGUAYwB0AG8AcgAgAG0AYQBjAGgAaQBuAGUAcwAgAEYAYQBzAHQAIABTAFYATQAgAHQAcgBhAGkAbgBpAG4AZwAgAG8AbgAgAHYAZQByAHkAIABsAGEAcgBnAGUAIABkAGEAdABhACAAcwBlAHQAcwAuAHAAZABmAA8AFAAJAEQAbwBjAHUAbQBlAG4AdABzABIAai9uZW1vL0RvY3VtZW50cy9Vbml2ZXJzaXRhL1BhcGVycy9Uc2FuZy9Db3JlIHZlY3RvciBtYWNoaW5lcyBGYXN0IFNWTSB0cmFpbmluZyBvbiB2ZXJ5IGxhcmdlIGRhdGEgc2V0cy5wZGYAEwASL1ZvbHVtZXMvRG9jdW1lbnRzABUAAgAX//8AAIAG0h8gISJYJGNsYXNzZXNaJGNsYXNzbmFtZaMiIyRdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3TSHyAmJ6InJFxOU0RpY3Rpb25hcnkACAARABsAJAApADIARABJAEwAUQBTAFwAYgBpAHQAfACDAIYAiACKAI0AjwCRAJMAoACqAQUBCgESA2oDbANxA3oDhQOJA5cDngOnA6wDrwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAO8},
  Bdsk-Url-1 = {http://www.cs.ust.hk/~ivor/publication/tsang05a.pdf}
}

Le seconde sembrano basarsi su algoritmi di approssimazione, ottenendo comunque degli ottimi risultati e soprattutto raggiungendo delle ottime prestazioni di training su “very large datasets”.