A Note on Support Vector Machines Degeneracy
When training Support Vector Machines (SVMs) over non-separable data sets, one sets the threshold $b$ using any dual cost coefficient that is strictly between the bounds of $0$ and $C$. We show that there exist SVM training problems with dual optimal solutions with all coefficients at bounds,...
| Main Authors: | , , |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/7291 |
| _version_ | 1826215016154529792 |
|---|---|
| author | Rifkin, Ryan Pontil, Massimiliano Verri, Alessandro |
| author_facet | Rifkin, Ryan Pontil, Massimiliano Verri, Alessandro |
| author_sort | Rifkin, Ryan |
| collection | MIT |
| description | When training Support Vector Machines (SVMs) over non-separable data sets, one sets the threshold $b$ using any dual cost coefficient that is strictly between the bounds of $0$ and $C$. We show that there exist SVM training problems with dual optimal solutions with all coefficients at bounds, but that all such problems are degenerate in the sense that the "optimal separating hyperplane" is given by ${f w} = {f 0}$, and the resulting (degenerate) SVM will classify all future points identically (to the class that supplies more training data). We also derive necessary and sufficient conditions on the input data for this to occur. Finally, we show that an SVM training problem can always be made degenerate by the addition of a single data point belonging to a certain unboundedspolyhedron, which we characterize in terms of its extreme points and rays. |
| first_indexed | 2024-09-23T16:15:31Z |
| id | mit-1721.1/7291 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:15:31Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/72912019-04-15T00:40:29Z A Note on Support Vector Machines Degeneracy Rifkin, Ryan Pontil, Massimiliano Verri, Alessandro AI MIT Artificial Intelligence Support Vector Machines Scale Sensitive Loss Function Statistical Learning Theory. When training Support Vector Machines (SVMs) over non-separable data sets, one sets the threshold $b$ using any dual cost coefficient that is strictly between the bounds of $0$ and $C$. We show that there exist SVM training problems with dual optimal solutions with all coefficients at bounds, but that all such problems are degenerate in the sense that the "optimal separating hyperplane" is given by ${f w} = {f 0}$, and the resulting (degenerate) SVM will classify all future points identically (to the class that supplies more training data). We also derive necessary and sufficient conditions on the input data for this to occur. Finally, we show that an SVM training problem can always be made degenerate by the addition of a single data point belonging to a certain unboundedspolyhedron, which we characterize in terms of its extreme points and rays. 2004-10-22T20:17:55Z 2004-10-22T20:17:55Z 1999-08-11 AIM-1661 CBCL-177 http://hdl.handle.net/1721.1/7291 en_US AIM-1661 CBCL-177 10 p. 1117769 bytes 262084 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | AI MIT Artificial Intelligence Support Vector Machines Scale Sensitive Loss Function Statistical Learning Theory. Rifkin, Ryan Pontil, Massimiliano Verri, Alessandro A Note on Support Vector Machines Degeneracy |
| title | A Note on Support Vector Machines Degeneracy |
| title_full | A Note on Support Vector Machines Degeneracy |
| title_fullStr | A Note on Support Vector Machines Degeneracy |
| title_full_unstemmed | A Note on Support Vector Machines Degeneracy |
| title_short | A Note on Support Vector Machines Degeneracy |
| title_sort | note on support vector machines degeneracy |
| topic | AI MIT Artificial Intelligence Support Vector Machines Scale Sensitive Loss Function Statistical Learning Theory. |
| url | http://hdl.handle.net/1721.1/7291 |
| work_keys_str_mv | AT rifkinryan anoteonsupportvectormachinesdegeneracy AT pontilmassimiliano anoteonsupportvectormachinesdegeneracy AT verrialessandro anoteonsupportvectormachinesdegeneracy AT rifkinryan noteonsupportvectormachinesdegeneracy AT pontilmassimiliano noteonsupportvectormachinesdegeneracy AT verrialessandro noteonsupportvectormachinesdegeneracy |