TL;DR
This paper introduces a novel testing framework designed to tackle the challenge of ensuring the quality and dependability of machine learning (ML) applications, particularly those that lack a clear "ground truth" for evaluation. By developing a suite of tools for data generation, model/ranking comparison, and detailed tracing, the authors successfully identified bugs in three distinct implementations of an ML ranking algorithm, demonstrating the framework's practical utility.
What Problem Does This Paper Address?
The core problem this paper addresses is the difficulty in testing and debugging machine learning (ML) applications, especially those that operate in domains where the "correct" answer isn't readily available. This is particularly true for "non-testable programs" in software engineering, a category that encompasses many ML systems. The authors focus on ML ranking applications, where the goal is to order data points based on predicted positive or negative labels. Unlike traditional software, where a test oracle can verify correctness, ML ranking outputs are hard to validate directly. This lack of a reliable oracle makes it challenging to detect subtle bugs and ensure the dependability of these systems, which is crucial when they are deployed in high-stakes real-world scenarios like predicting electrical feeder failures.
Methods
The paper presents a comprehensive testing framework built around several key components:
- Test Data Set Generator: A tool to create synthetic data sets with controlled properties. This allows for systematic testing of specific scenarios, such as repeating values, missing values, and categorical attributes, which are common in real-world data but difficult to isolate and test with naturally occurring datasets.
- Model and Ranking Comparison Tools: Utilities to compare the outputs of different ML implementations. This includes comparing the generated "models" (the learned rules) and the final "rankings." The tools go beyond simple diffing by enumerating differences in rounds, sort attributes, and directions, and also provide metrics like AUC, Manhattan distance, and normalized Spearman Footrule Distance for rankings.
- Tracing Options: Runtime options integrated into the ML implementations to capture intermittent values and intermediate states during the algorithm's execution. This detailed tracing is crucial for debugging, allowing researchers to pinpoint exactly where differences in models or rankings arise, such as issues in sorting logic or AUC calculations.
The framework was applied to three implementations of the "MartiRank" algorithm, a supervised ML ranking algorithm. The testing approach involved:
- Comparison Testing: Evaluating if different implementations produced identical models and rankings.
- Regression Testing: Ensuring that new revisions of an implementation did not introduce new bugs.
- Disabling Optimizations: Initially disabling any "optimization" options in the ML algorithms to ensure consistent, deterministic behavior for baseline testing.
Datasets
The paper utilized a combination of datasets:
- Manually Constructed Data Sets: Small, controlled datasets designed to produce a "perfect" ranking, where all positive examples were at the top. These were used for initial, fine-grained testing.
- Automatically Generated Data Sets: Larger datasets generated by the framework's data generation tool. These datasets allowed for testing various equivalence classes and boundary conditions, including:
- Varying percentages of failures (positive-labeled examples).
- N numerical attributes with options for repeating values and missing values (0-100%).
- K categorical attributes with specified distributions and missing value percentages.
- Real-World Data Sets: Data from an electrical distribution feeder failure prediction system (as illustrated in Figure 1). These datasets contained categorical data, missing values, and repeating values.
Key Insights and Ideas
- The "Pseudo-Oracle" Approach: The framework leverages the idea of using multiple implementations of the same algorithm as "pseudo-oracles" for each other. When implementations agree, it increases confidence; when they disagree, it signals a potential bug. This is particularly valuable when a true oracle is absent.
- Importance of Controlled Data Generation: The ability to generate synthetic data with specific properties (repeating values, missing values, categorical attributes) was critical for systematically uncovering bugs that might not appear in naturally occurring datasets.
- Debugging Beyond Model Comparison: While comparing models is a good starting point, the framework's tracing capabilities were essential for understanding why models differed. This detailed insight into the algorithm's internal workings was key to convincing developers of the existence of bugs.
- Algorithm Ambiguity vs. Implementation Bugs: The research highlighted instances where the MartiRank algorithm itself was underspecified (e.g., how to handle non-failures when filling segments, or the stability of sorting with ties). This revealed that implementation decisions, even if not strictly violating the algorithm's formal definition, could lead to inconsistent behavior and required careful consideration.
- The "Actionable" Nature of ML Models: The paper touches upon the idea that some ML models, like MartiRank, can be "actionable," meaning it's clear which input attributes contributed most to the ranking. This suggests that testing should not only focus on correctness but also on interpretability.
Key Results
- Bug Discovery: The testing framework successfully identified bugs in all three MartiRank implementations (PerlMarti, CMarti, and FastCMarti). These included:
- CMarti experiencing segmentation faults due to an optimization option being incorrectly called.
- PerlMarti and FastCMarti initially not always choosing an attribute to sort on in the first round, deviating from a more robust approach.
- FastCMarti's sorting stability issues, where it relied on the original data order rather than the previous round's sorted order for ties.
- FastCMarti's different segmentation logic for handling non-failures.
- CMarti and PerlMarti exhibiting randomization issues with missing values.
- PerlMarti having a bug related to global variable usage in AUC calculation when handling categorical data.
- Framework Utility: The framework proved instrumental in creating test cases, executing them, and analyzing the results. The data generation tool was found to be reliable, and the model comparison tool offered significant advantages over simple diffing. The trace analysis tool was particularly effective in pinpointing bugs and convincing developers.
- Consistency Achieved: After bug fixes and adjustments, CMarti and PerlMarti were able to produce identical models and rankings across various test cases, demonstrating the framework's effectiveness in achieving consistency. FastCMarti was excluded from later comparisons due to fundamental differences in its approach to sorting stability.
Limitations and Future Work
- Limitations:
- The framework's trace analysis tool is heavily dependent on the specific "rounds and segments" concept of the MartiRank algorithm and would require re-targeting for other algorithms.
- The paper acknowledges that while the framework can help determine if results are "better" (e.g., higher AUC), it cannot definitively prove that the code is "correct" in all cases, especially when the algorithm itself is underspecified.
- The current focus is on the "ML Engine" and does not fully encompass the testing of complete ML applications integrated into larger systems.
- Future Work:
- Enhanced Data Generation: Extend the framework to generate arbitrarily large data sets that can definitively produce "perfect" rankings, and to create datasets that exhibit correlations between attributes and labels, mirroring real-world data.
- Complete Application Testing: Expand the framework to test entire ML applications, including components like decision support systems and real-time prediction pipelines.
- Broader Applicability: Make the framework useful for a wider community of ML researchers and engineers, facilitating the testing of various ML algorithms beyond MartiRank.
Summary updated