Foresighted tree configuration games in resource constrained distributed stream mining sensors

Hyunggon Park, Deepak S. Turaga, Olivier Verscheure, Mihaela Van Der Schaar

Research output: Contribution to journalArticlepeer-review


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 languageEnglish
Pages (from-to)497-513
Number of pages17
JournalAd Hoc Networks
Issue number4
StatePublished - Jun 2011


  • Binary classifier trees
  • Coalitions for distributed classifiers
  • Myopic and foresighted strategies
  • Resource constrained stream mining sensors
  • Tree configuration games


Dive into the research topics of 'Foresighted tree configuration games in resource constrained distributed stream mining sensors'. Together they form a unique fingerprint.

Cite this