Recent advances in machine learning and artificial intelligence are now being considered in safety-critical autonomous systems where software defects may cause severe harm to humans and the environment. Design organizations in these domains are currently unable to provide convincing arguments that their systems are safe to operate when machine learning algorithms are used to implement their software. In this paper, we present an efficient method to extract equivalence classes from decision trees and tree ensembles, and to formally verify that their input-output mappings comply with requirements. The idea is that, given that safety requirements can be traced to desirable properties on system input-output patterns, we can use positive verification outcomes in safety arguments. This paper presents the implementation of the method in the tool VoTE (Verifier of Tree Ensembles), and evaluates its scalability on two case studies presented in current literature. We demonstrate that our method is practical for tree ensembles trained on low-dimensional data with up to 25 decision trees and tree depths of up to 20. Our work also studies the limitations of the method with high-dimensional data and preliminarily investigates the trade-off between large number of trees and time taken for verification.
In our previous work @cite_17 , we verify safety-critical properties of random forests. Two techniques are presented, a fast but approximate technique which yields conservative output bounds, and a slower but precise technique employed when approximations are too conservative. In the precise technique, we partition the input space of decision trees into disjoint sets, explore all feasible path combinations amongst the trees, then compute equivalence classes of the entire random forest. Finally, these equivalence classes are checked against requirements. In this paper, we generalize our original method to other tree ensembles such as gradient boosting. We also improve our search strategy which we implement in a new tool, yielding a significant increase in performance.
@cite_17
2914920135
Recent advances in machine learning and artificial intelligence are now being applied in safety-critical autonomous systems where software defects may cause severe harm to humans and the environment. Design organizations in these domains are currently unable to provide convincing arguments that systems using complex software implemented using machine learning algorithms are safe and correct.