Abstract
Machine Learning as a Service (MLaaS) platforms provide various APIs for multi-label classification tasks, yet their costs and performance vary significantly. We present FrugalMCT, a principled framework that adaptively selects and combines multiple MLaaS APIs to optimize for both accuracy and cost. By formulating the selection process as a Multiple Choice Knapsack Problem and employing an efficient online algorithm, FrugalMCT can reduce costs by over 90% while maintaining high accuracy, or improve accuracy by up to 8% within a fixed budget.
Introduction
The Machine Learning as a Service (MLaaS) market is expanding rapidly, offering powerful APIs for tasks such as image tagging, OCR, and entity recognition. However, these APIs are essentially "black boxes" with distinct pricing models and performance characteristics. For instance, one provider might excel at identifying household objects but struggle with outdoor scenes, while another may have the opposite strengths.
For users, the core challenge is determining which API—or combination of APIs—to use for specific data and budget constraints. While previous research like FrugalML addressed this for single-label classification, multi-label tasks present a "combinatorial explosion" of possible label sets. FrugalMCT addresses this by providing a scalable, efficient framework for multi-label API selection and combination.
The FrugalMCT Framework
FrugalMCT consists of four primary components designed to work together in an online setting:
- Base Service: Every query begins with a low-cost or free "base" service, typically an open-source model like SSD.
- Accuracy Predictor: Using features from the input and the base service's output, a regressor (e.g., Random Forest) estimates the potential accuracy of different API combinations for that specific input.
- Service Selector: This component treats API selection as a Multiple Choice Knapsack Problem (MCKP). It utilizes a threshold parameter ($p$) to balance accuracy against cost, ensuring the total budget is respected over time.
- Label Combiner: When multiple APIs are invoked, this component merges their predictions using a weighted sum and a confidence threshold to produce the final multi-label set.
Crucially, FrugalMCT’s computational complexity does not depend on the number of labels, allowing it to scale to tasks with thousands of possible outputs. As shown in the figure above (Example 1), the system can intelligently decide to rely solely on the cheap base service if the predicted accuracy is sufficient for the given input.
Evaluation and Key Results
The researchers evaluated FrugalMCT across three domains—Multi-label Image Classification (MIC), Scene Text Recognition (STR), and Named Entity Recognition (NER)—using nine datasets. The authors also released a massive benchmark dataset of nearly 300,000 samples annotated by various commercial APIs to facilitate future research.
Key Performance Metrics
- Massive Cost Savings: On datasets like PASCAL and MTWI, FrugalMCT achieved over 90% cost reduction while matching the accuracy of the best single commercial API.
- Superior Accuracy: When constrained to the same budget as the best single API, FrugalMCT improved accuracy by up to 8% (e.g., on the COCO dataset) by intelligently combining results.
- Operational Efficiency: The selection process is extremely fast, making it suitable for real-time applications, and the system requires only a few thousand labeled samples for training.
The performance graph in the figure above illustrates how FrugalMCT consistently outperforms individual APIs and the previous FrugalML baseline across various budget levels. Example 2 demonstrates the "complementary strengths" of different services, where FrugalMCT combines the base service with a specialized provider to achieve a more complete and accurate label set.
Conclusion
FrugalMCT provides a robust solution for navigating the complex MLaaS landscape for multi-label tasks. By leveraging the predictability of API success and the complementary strengths of different providers, it offers a way to maximize accuracy while strictly adhering to budget constraints. Future work will focus on handling open-vocabulary scenarios and making the system more robust to model drift in underlying MLaaS providers.
Summary updated