Abstract
Ensemble learning has been widely employed by mobile applications, ranging from environmental sensing to activity recognitions. One of the fundamental issue in ensemble learning is the trade-off between classification accuracy and computational costs, which is the goal of ensemble pruning. During crowdsourcing, the centralized aggregator releases ensemble learning models to a large number of mobile participants for task evaluation or as the crowdsourcing learning results, while different participants may seek for different levels of the accuracy-cost trade-off. However, most of existing ensemble pruning approaches consider only one identical level of such trade-off. In this study, we present an efficient ensemble pruning framework for personalized accuracy-cost trade-offs via multi-objective optimization. Specifically, for the commonly used linear-combination style of the trade-off, we provide an objective-mixture optimization to further reduce the number of ensemble candidates. Experimental results show that our framework is highly efficient for personalized ensemble pruning, and achieves much better pruning performance with objective-mixture optimization when compared to state-of-art approaches.
Introduction
Ensemble learning—combining multiple models like Decision Trees or SVMs—is a powerful way to boost accuracy in mobile applications like activity recognition or fall detection. However, running an entire "forest" of models is expensive for mobile devices with limited battery life and processing power. Ensemble pruning addresses this by selecting a subset of the best models.
Traditionally, pruning is a "one-size-fits-all" approach where a server selects a single trade-off level between accuracy and cost. However, in mobile crowdsourcing, users are diverse: one may prioritize accuracy while another, with low battery, may require a lean model. Running separate optimizations for every user is computationally prohibitive for servers handling thousands of participants. This paper introduces a framework to tailor models for mobile users efficiently.
System Framework and Methodology
The proposed framework moves away from single-objective optimization toward Bi-objective Pareto Optimization. The core idea is that a single multi-objective optimization run can serve as a "menu" for thousands of users.
- The Pareto Frontier: Instead of finding one model, the framework identifies a set of "non-dominated" models (the Pareto set). These represent optimal points where accuracy cannot be improved without increasing cost.
- Personalized Selection: The server calculates this Pareto set once. For each user $u_i$, it performs a quick search ($O(n \log n)$) to find the specific model $S_i$ that matches the user's requested trade-off parameter $\alpha_i$.
- Objective-Mixture Optimization (OMF): This key innovation "tweaks" the objectives to focus specifically on the range of trade-offs actually requested by the current pool of users. By ignoring extreme models that no participant would use, the algorithm concentrates its search power on useful candidates.
Experimental Evaluation
The framework was evaluated using a Human Activity Recognition (HAR) dataset (4,944 examples, 6 activity classes) with a pool of 20 CART classifiers generated via Bagging.
Key Results
The researchers compared their Objective-Mixture (OMF) approach against a basic bi-objective framework (BF) and a state-of-the-art non-personalized approach (PEPs) run multiple times.
- Efficiency: As shown in Figure 4(a), while traditional approaches (PEPs) see costs rise linearly with the number of participants, the OMF framework's processing time remains nearly constant. OMF reduced running time by approximately 40% compared to the basic framework.
- Effectiveness: In terms of "combined loss" (penalizing both error and cost), the OMF framework achieved a 50% improvement over PEPs, as seen in Figure 4(b).
- Scalability: The framework's complexity scales efficiently ($O(poly(m) + n \log n)$), making it ideal for large-scale crowdsourcing environments.
Conclusion and Future Work
This study demonstrates that personalized ensemble pruning can be achieved efficiently through multi-objective optimization. By leveraging the Pareto frontier, a single server can support diverse user needs without linear increases in computation. Future research may explore non-linear user preferences and dynamic environments where user trade-off requirements change in real-time, such as during rapid battery depletion.
Summary updated