In this note, we investigate connections between supervised classification and (Generalized) Nash equilibrium problems (NEP & GNEP). For the specific case of support vector machines (SVM), we exploit the geometric properties of class separation in the dual space to formulate a non-cooperative game. NEP and Generalized NEP formulations are proposed for both binary and multi-class SVM problems.
Accepté le :
DOI : 10.1051/ro/2016024
Mots-clés : Supervised classification, support vector machine, multi-class SVM, Nash equilibrium, generalized Nash equilibrium, game theory
@article{RO_2017__51_2_329_0,
author = {Couellan, Nicolas},
title = {A note on supervised classification and {Nash-equilibrium} problems},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {329--341},
publisher = {EDP-Sciences},
volume = {51},
number = {2},
year = {2017},
doi = {10.1051/ro/2016024},
mrnumber = {3619707},
zbl = {1364.68321},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2016024/}
}
TY - JOUR AU - Couellan, Nicolas TI - A note on supervised classification and Nash-equilibrium problems JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2017 SP - 329 EP - 341 VL - 51 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2016024/ DO - 10.1051/ro/2016024 LA - en ID - RO_2017__51_2_329_0 ER -
%0 Journal Article %A Couellan, Nicolas %T A note on supervised classification and Nash-equilibrium problems %J RAIRO - Operations Research - Recherche Opérationnelle %D 2017 %P 329-341 %V 51 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2016024/ %R 10.1051/ro/2016024 %G en %F RO_2017__51_2_329_0
Couellan, Nicolas. A note on supervised classification and Nash-equilibrium problems. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 2, pp. 329-341. doi : 10.1051/ro/2016024. http://www.numdam.org/articles/10.1051/ro/2016024/
S. Abe, Support Vector Machines for Pattern Classification. Advances in Pattern Recognition, 2nd edition. Springer, London, UK (2010). | MR | Zbl
K. Bennett and E. Bredensteiner, Geometry in Learning, in Geometry at Work, edited by C. Gorini. Mathematical Association of America, Washington D.C. (2000) 132–145. | MR
K. Bennett and E. Bredensteiner, Duality and Geometry in SVMs, In Proc. of 17th International Conference on Machine Learning, edited by P. Langley. San Francisco (2000) 65–72.
, , and , Self Adaptive Support Vector Machine: A Multi-Agent Optimization Perspective. Expert Syst. Appl. 42 (2015) 4284–4298. | DOI
and , Generalized Nash Equilibrium Problems. Annals OR 175 (2010) 177–211. | DOI | MR | Zbl
J. Fürnkranz, Machine Learning in Games: A Survey, in Machines that Learn to Play Games. Nova Science Publishers (2001) 11–59.
and , Formalization of Multi-level games. Int. Game Theory Rev. 6 (2004) 195–221. | DOI | MR | Zbl
and , The class imbalance problem: A systematic study. Intel. Data Anal. 6 (2002) 429–449. | DOI | Zbl
and , A Game Theoretical Approach to Clustering of Ad-Hoc and Sensor Networks. Telecomm. Systems 47 (2011) 81–93. | DOI
D.G. Luenberger, Optimization by Vector Space Methods, 1st edition. John Wiley & Sons, Inc., New York, USA (1997) | MR
A. Neyman and S. Sorin (eds.), Stochastic Games and Applications, Proc. of the NATO Advanced Study Institute, Stony Brook, New York, USA, 1999, Series: Nato Science Series C: (closed), Vol. 570 (2003) | MR | Zbl
and , Game Theory and Decision Theory in Multi-Agent Systems. Autonomous Agents and Multi-Agent Systems 5 (2002) 243–254. | DOI
M. Petrovskiy, A Game Theory Approach to Pairwise Classification with Support Vector Machines. Proc. of the 2004 International Conference on Machine Learning and Application. ICMLAs, IEEE Computer Society (2004) 115–122.
B. Schölkopf and A. Smola, Learning with Kernels. MIT, Cambridge (2002).
S. Sra, S. Nowozin and S.J. Wright, Optimization for Machine Learning. MIT Press, Cambridge (2011).
, Mining with Rarity: A Unifying Framework. ACM SIGKDD Explorations Newsletter 6 (2004) 7–19. | DOI
G. Weiss, A modern Approach to Distributed Artifical Intelligence. Intelligent Robotics & Autonomous Agents Series, MIT Press, Cambridge (2000).
J. Weston and C. Watkins, Support Vector Machines for Multi-Class Pattern Recognition. Proc. of ESANN’1999, Bruges, Belgium (1999) 219–224.
Cité par Sources :
