Willump: Optimizing Feature Computation in ML Inference
0 likes447 views
Systems for performing ML inference are increasingly important, but are far slower than they could be because they use techniques designed for conventional data serving workloads, neglecting the statistical nature of ML inference. As an alternative, this talk presents Willump, an optimizer for ML inference.
More Related Content
What's hot (20)
Similar to Willump: Optimizing Feature Computation in ML Inference (20)
More from Databricks (20)
Recently uploaded (20)
Willump: Optimizing Feature Computation in ML Inference
- 1. Willump: A Statistically-Aware End-to-end Optimizer for ML Inference Peter Kraft, Daniel Kang, Deepak Narayanan, Shoumik Palkar, Peter Bailis, Matei Zaharia Stanford University
- 2. Problem: ML Inference ● Often performance-critical. ● Recent focus on tools for ML prediction serving. 2
- 3. A Common Bottleneck: Feature Computation 3 ● Many applications bottlenecked by feature computation. ● Pipeline of transformations computes numerical features from data for model. Receive Raw Data Compute Features Predict With Model
- 4. A Common Bottleneck: Feature Computation 4 ● Feature computation is bottleneck when models are inexpensive—boosted trees, not DNNs. ● Common on tabular/structured data!
- 5. A Common Bottleneck: Feature Computation Source: Pretzel (OSDI ‘18) Feature computation takes >99% of the time! Production Microsoft sentiment analysis pipeline Model run time 5
- 6. Current State-of-the-art ● Apply traditional serving optimizations, e.g. caching (Clipper), compiler optimizations (Pretzel). ● Neglect unique statistical properties of ML apps. 6
- 7. Statistical Properties of ML Amenability to approximation 7
- 8. Statistical Properties of ML Amenability to approximation 8 Easy input: Definitely not a dog. Hard input: Maybe a dog?
- 9. Statistical Properties of ML Amenability to approximation Existing Systems: Use Expensive Model for Both 9 Easy input: Definitely not a dog. Hard input: Maybe a dog?
- 10. Statistical Properties of ML Amenability to approximation Statistically-Aware Systems: Use cheap model on bucket, expensive model on cat. 10 Easy input: Definitely not a dog. Hard input: Maybe a dog?
- 11. Statistical Properties of ML ● Model is often part of a bigger app (e.g. top-K query) 11
- 12. Statistical Properties of ML ● Model is often part of a bigger app (e.g. top-K query) 12 Artist Score Rank Beatles 9.7 1 Bruce Springsteen 9.5 2 … … … Justin Bieber 5.6 999 Nickelback 4.1 1000 Problem: Return top 10 artists.
- 13. Statistical Properties of ML ● Model is often part of a bigger app (e.g. top-K query) 13 Artist Score Rank Beatles 9.7 1 Bruce Springsteen 9.5 2 … … … Justin Bieber 5.6 999 Nickelback 4.1 1000 Use expensive model for everything! Existing Systems
- 14. Statistical Properties of ML ● Model is often part of a bigger app (e.g. top-K query) 14 Artist Score Rank Beatles 9.7 1 Bruce Springsteen 9.5 2 … … … Justin Bieber 5.6 999 Nickelback 4.1 1000 High-value: Rank precisely, return. Low-value: Approximate, discard. Statistically-aware Systems
- 15. Prior Work: Statistically-Aware Optimizations ● Statistically-aware optimizations exist in literature. ● Always application-specific and custom-built. ● Never automatic! 15 Source: Cheng et al. (DLRS’ 16), Kang et al. (VLDB ‘17)
- 16. ML Inference Dilemna ● ML inference systems: ○ Easy to use. ○ Slow. ● Statistically-aware systems: ○ Fast ○ Require a lot of work to implement. 16
- 17. Can an ML inference system be fast and easy to use? 17
- 18. Willump: Overview ● Statistically-aware optimizer for ML Inference. ● Targets feature computation! ● Automatic model-agnostic statistically-aware opts. ● 10x throughput+latency improvements. 18
- 19. Outline 19 ● System Overview ● Optimization 1: End-to-end Cascades ● Optimization 2: Top-K Query Approximation ● Evaluation
- 20. Willump: Goals ● Automatically maximize performance of ML inference applications whose performance bottleneck is feature computation 20
- 21. def pipeline(x1, x2): input = lib.transform(x1, x2) preds = model.predict(input) return preds System Overview Input Pipeline
- 22. def pipeline(x1, x2): input = lib.transform(x1, x2) preds = model.predict(input) return preds Willump Optimization Infer Transformation Graph System Overview Input Pipeline
- 23. 23 def pipeline(x1, x2): input = lib.transform(x1, x2) preds = model.predict(input) return preds Willump Optimization Infer Transformation Graph Statistically-Aware Optimizations: 1. End-To-End Cascades 2. Top-K Query Approximation System Overview Input Pipeline
- 24. 24 def pipeline(x1, x2): input = lib.transform(x1, x2) preds = model.predict(input) return preds Willump Optimization Infer Transformation Graph Compiler Optimizations (Weld—Palkar et al. VLDB ‘18) System Overview Input Pipeline Statistically-Aware Optimizations: 1. End-To-End Cascades 2. Top-K Query Approximation
- 25. 25 def pipeline(x1, x2): input = lib.transform(x1, x2) preds = model.predict(input) return preds Willump Optimization Infer Transformation Graph Compiler Optimizations (Weld—Palkar et al. VLDB ‘18) def willump_pipeline(x1, x2): preds = compiled_code(x1, x2) return preds Optimized Pipeline System Overview Input Pipeline Statistically-Aware Optimizations: 1. End-To-End Cascades 2. Top-K Query Approximation
- 26. Outline 26 ● System Overview ● Optimization 1: End-to-end Cascades ● Optimization 2: Top-K Query Approximation ● Evaluation
- 27. Background: Model Cascades ● Classify “easy” inputs with cheap model. ● Cascade to expensive model for “hard” inputs. 27 Easy input: Definitely not a dog. Hard input: Maybe a dog?
- 28. Background: Model Cascades ● Used for image classification, object detection. ● Existing systems application-specific and custom-built. 28 Source: Viola-Jones (CVPR’ 01), Kang et al. (VLDB ‘17)
- 29. Our Optimization: End-to-end cascades ● Compute only some features for “easy” data inputs; cascade to computing all for “hard” inputs. ● Automatic and model-agnostic, unlike prior work. ○ Estimates for runtime performance & accuracy of a feature set ○ Efficient search process for tuning parameters 29
- 30. End-to-end Cascades: Original Model Compute All Features Model Prediction
- 31. Cascades Optimization End-to-end Cascades: Approximate Model Compute All Features Model Prediction Compute Selected Features Approximate Model Prediction
- 32. Cascades Optimization End-to-end Cascades: Confidence Compute All Features Model Prediction Compute Selected Features Approximate Model Prediction Confidence > Threshold Yes
- 33. Cascades Optimization End-to-end Cascades: Final Pipeline Compute All Features Model Prediction Compute Selected Features Compute Remaining Features Approximate Model Prediction Original Model Confidence > Threshold Yes No
- 34. End-to-end Cascades: Constructing Cascades 34 ● Construct cascades during model training. ● Need model training set and an accuracy target.
- 35. End-to-end Cascades: Selecting Features Compute Selected Features Compute Remaining Features Approximate Model Prediction Original Model Confidence > Threshold Yes No Key question: Select which features?
- 36. End-to-end Cascades: Selecting Features 36 ● Goal: Select features that minimize expected query time given accuracy target.
- 37. End-to-end Cascades: Selecting Features Compute Selected Features Compute Remaining Features Approximate Model Prediction Original Model Confidence > Threshold Yes No Two possibilities for a query: Can approximate or not. Can approximate query. Can’t approximate query.
- 38. End-to-end Cascades: Selecting Features Compute Selected Features (S) Approximate Model Prediction Confidence > Threshold YesP(Yes) = P(approx) cost(𝑆) min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹)
- 39. End-to-end Cascades: Selecting Features Compute Selected Features (S) Compute Remaining Features Approximate Model Prediction Original Model Confidence > Threshold No P(No) = P(~approx) min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) cost(𝐹)
- 40. End-to-end Cascades: Selecting Features Compute Selected Features (S) Compute Remaining Features Approximate Model Prediction Original Model Confidence > Threshold Yes NoP(Yes) = P(approx) P(No) = P(~approx) cost(𝑆) min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) cost(𝐹)
- 41. End-to-end Cascades: Selecting Features 41 ● Goal: Select feature set S that minimizes query time: min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹)
- 42. End-to-end Cascades: Selecting Features 42 ● Goal: Select feature set S that minimizes query time: min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Approach: ○ Choose several potential values of cost(𝑺). ○ Find best feature set with each cost(S). ○ Train model & find cascade threshold for each set. ○ Pick best overall.
- 43. End-to-end Cascades: Selecting Features 43 ● Goal: Select feature set S that minimizes query time: min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Approach: ○ Choose several potential values of cost(𝑆). ○ Find best feature set with each cost(S). ○ Train model & find cascade threshold for each set. ○ Pick best overall.
- 44. End-to-end Cascades: Selecting Features 44 ● Goal: Select feature set S that minimizes query time: min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Approach: ○ Choose several potential values of cost(𝑆). ○ Find best feature set with each cost(S). ○ Train model & find cascade threshold for each set. ○ Pick best overall.
- 45. End-to-end Cascades: Selecting Features 45 ● Goal: Select feature set S that minimizes query time: min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Approach: ○ Choose several potential values of cost(𝑆). ○ Find best feature set with each cost(S). ○ Train model & find cascade threshold for each set. ○ Pick best overall.
- 46. End-to-end Cascades: Selecting Features 46 ● Goal: Select feature set S that minimizes query time: min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Approach: ○ Choose several potential values of cost(𝑺). ○ Find best feature set with each cost(S). ○ Train model & find cascade threshold for each set. ○ Pick best overall.
- 47. End-to-end Cascades: Selecting Features 47 ● Goal: Select feature set S that minimizes query time: min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Approach: ○ Choose several potential values of cost(𝑆). ○ Find best feature set with each cost(S). ○ Train model & find cascade threshold for each set. ○ Pick best overall.
- 48. End-to-end Cascades: Selecting Features 48 ● Subgoal: Find S minimizing query time if 𝑐𝑜𝑠𝑡 𝑆 = 𝑐 𝑚𝑎𝑥. min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹)
- 49. End-to-end Cascades: Selecting Features 49 ● Subgoal: Find S minimizing query time if 𝑐𝑜𝑠𝑡 𝑆 = 𝑐 𝑚𝑎𝑥. min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Solution: ○ Find S maximizing approximate model accuracy.
- 50. End-to-end Cascades: Selecting Features 50 ● Subgoal: Find S minimizing query time if 𝑐𝑜𝑠𝑡 𝑆 = 𝑐 𝑚𝑎𝑥. min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Solution: ○ Find S maximizing approximate model accuracy. ○ Problem: Computing accuracy expensive.
- 51. End-to-end Cascades: Selecting Features 51 ● Subgoal: Find S minimizing query time if 𝑐𝑜𝑠𝑡 𝑆 = 𝑐 𝑚𝑎𝑥. min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Solution: ○ Find S maximizing approximate model accuracy. ○ Problem: Computing accuracy expensive. ○ Solution: Estimate accuracy via permutation importance -> knapsack problem.
- 52. End-to-end Cascades: Selecting Features 52 ● Goal: Select feature set S that minimizes query time: min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Approach: ○ Choose several potential values of cost(𝑆). ○ Find best feature set with each cost(S). ○ Train model & find cascade threshold for each set. ○ Pick best overall.
- 53. End-to-end Cascades: Selecting Features 53 ● Subgoal: Train model & find cascade threshold for S. min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Solution: ○ Compute empirically on held-out data.
- 54. End-to-end Cascades: Selecting Features 54 ● Subgoal: Train model & find cascade threshold for S. min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Solution: ○ Compute empirically on held-out data. ○ Train approximate model from S.
- 55. End-to-end Cascades: Selecting Features 55 ● Subgoal: Train model & find cascade threshold for S. min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Solution: ○ Compute empirically on held-out data. ○ Train approximate model from S. ○ Predict held-out set, determine cascade threshold empirically using accuracy target.
- 56. End-to-end Cascades: Selecting Features 56 ● Goal: Select feature set S that minimizes query time: min 𝑆 𝑃(approx)cost(𝑆) + 𝑃(~approx)cost(𝐹) ● Approach: ○ Choose several potential values of cost(𝑆). ○ Find best feature set with each cost(S). ○ Train model & find cascade threshold for each set. ○ Pick best overall.
- 57. End-to-end Cascades: Results 57 ● Speedups of up to 5x without statistically significant accuracy loss. ● Full evaluation at end of talk!
- 58. Outline 58 ● System Overview ● Optimization 1: End-to-end Cascades ● Optimization 2: Top-K Query Approximation ● Evaluation
- 59. Top-K Approximation: Query Overview ● Top-K problem: Rank K highest-scoring items of a dataset. ● Top-K example: Find 10 artists a user would like most (recommender system). 59
- 60. Top-K Approximation: Asymmetry 60 ● High-value items must be predicted, ranked precisely. ● Low-value items need only be identified as low value. Artist Score Rank Beatles 9.7 1 Bruce Springsteen 9.5 2 … … … Justin Bieber 5.6 999 Nickelback 4.1 1000 High-value: Rank precisely, return. Low-value: Approximate, discard.
- 61. Top-K Approximation: How it Works ● Use approximate model to identify and discard low- value items. ● Rank high-value items with powerful model. 61
- 62. Top-K Approximation: Prior Work ● Existing systems have similar ideas. ● However, we automatically generate approximate models for any ML application—prior systems don’t. ● Similar challenges as in cascades. 62 Source: Cheng et al. (DLRS ‘16)
- 63. Top-K Approximation: Automatic Tuning ● Automatically selects features, tunes parameters to maximize performance given accuracy target. ● Works similarly to cascades. ● See paper for details! 63
- 64. Top-K Approximation: Results 64 ● Speedups of up to 10x for top-K queries. ● Full eval at end of talk!
- 65. Outline 65 ● System Overview ● Optimization 1: End-to-end Cascades ● Optimization 2: Top-K Query Approximation ● Evaluation
- 66. Willump Evaluation: Benchmarks ● Benchmarks curated from top-performing entries to data science competitions (e.g. Kaggle, WSDM, CIKM). ● Three benchmarks in presentation (more in paper): ○ Music (music recommendation– queries remotely stored precomputed features) ○ Purchase (predict next purchase, tabular AutoML features) ○ Toxic (toxic comment detection – computes string features) 66
- 67. End-to-End Cascades Evaluation: Throughput 67 15x 1.6x1x1x 2.4x 3.2x
- 68. 68 End-to-End Cascades Evaluation: Latency
- 69. Top-K Query Approximation Evaluation 69 4.0x 1x 2.7x 1x 3.2x 30x
- 70. Statistical nature of ML enables new optimizations: Willump applies them automatically for 10x speedups. github.com/stanford-futuredata/Willump Summary Summary