Abstract
We consider the problem of optimizing stream mining applications that are constructed as tree topologies of classifiers and deployed on a set of resource constrained and distributed processing nodes (or sensors). The optimization involves selecting appropriate false-alarm detection tradeoffs (operating points) for each classifier to minimize an end-to-end misclassification penalty, while satisfying resource constraints. We design distributed solutions, by defining tree configuration games, where individual classifiers configure themselves to maximize an appropriate local utility. We define the local utility functions and determine the information that needs to be exchanged across classifiers in order to design the distributed solutions. We analytically show that there is a unique pure strategy Nash equilibrium in operating points, which guarantees convergence of the proposed approach. We develop both myopic strategy, where the utility is purely local to the current classifier, and foresighted strategy, where the utility includes impact of classifier's actions on successive classifiers. We analytically show that actions determined based on foresighted strategies improve the end-to-end performance of the classifier tree, by deriving an associated probability bound. We also investigate the impact of resource constraints on the classifier action selections for each strategy, and the corresponding application performance. We propose a learning-based approach, which enables each classifier to effectively adapt to the dynamic changes of resource constraints. We evaluate the performance of our solutions on an application for sports scene classification. We show that foresighted strategies result in better performance than myopic strategies in both resource unconstrained and resource constrained scenarios, and asymptotically approach the centralized optimal solution. We also show that the proposed distributed solutions outperform the centralized solution based on the Sequential Quadratic Programming on average in resource unconstrained scenarios.
| Original language | English |
|---|---|
| Pages (from-to) | 497-513 |
| Number of pages | 17 |
| Journal | Ad Hoc Networks |
| Volume | 9 |
| Issue number | 4 |
| DOIs | |
| State | Published - Jun 2011 |
Bibliographical note
Funding Information:Hyunggon Park received the B.S. degree in Electronics and Electrical Engineering from the Pohang University of Science and Technology (POSTECH), Pohang, Korea, in 2004, and the M.S. and Ph.D. degrees in Electrical Engineering from the University of California, Los Angeles (UCLA), in 2006 and 2008, respectively. Currently, he is an Assistant Professor at the Department of Electronics Engineering, Ewha Womans University, Seoul, Korea. His research interests are game theoretic approaches for distributed resource management (resource reciprocation and resource allocation) strategies for multiuser systems and multiuser transmission over wireless/wired/peer-to-peer (P2P) networks. In 2008, he was an intern at IBM T.J.Watson Research Center, Hawthorne, NY, and he was a Senior Researcher at the Signal Processing Laboratory (LTS4), Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland, in 2009–2010. Dr. Park was a recipient of the Graduate Study Abroad Scholarship from the Korea Science and Engineering Foundation during 2004–2006 and arecipient of the Electrical Engineering Department Fellowship at UCLA in 2008.
Funding Information:
Mihaela van der Schaar is Professor in the Electrical Engineering Department at University of California, Los Angeles. She received in 2004 the NSF Career Award, in 2005 the Best Paper Award from IEEE Transactionson Circuits and Systems for Video Technology, in 2006 the Okawa Foundation Award, in 2005, 2007 and 2008 the IBM Faculty Award, and in 2006 the Most Cited Paper Award from EURASIP: Image Communications journal. She was an associate editor for IEEE Transactions on Multimedia, Signal Processing Letters, Circuitsand Systems for Video Technology, Signal Processing Magazine etc. She holds 33 granted US patents and three ISO awards for hercontributions to the MPEG video compression and streaming international standardization activities. Her research interests are in multimedia communications, networking, processing and systems and, more recently, network economics and game theory. She is a Fellow of IEEE.
Funding Information:
This work was supported in part by the Ewha Womans University Research Grant of 2010 and in part by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology ( 2010-0009717 ). This work was performed while the first author was with IBM T.J. Watson Research Center, Hawthorne, NY, USA. The material in this paper was presented in part at the Thirty-Fourth IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Taipei, Taiwan, April 2009.
Keywords
- Binary classifier trees
- Coalitions for distributed classifiers
- Myopic and foresighted strategies
- Resource constrained stream mining sensors
- Tree configuration games