Random forest decisions get formal explanations: compile the forest into circuits, then compute complete reasons and shortest flips in linear time
Synopsis
A random forest's majority-vote decision can now be compiled into class formulas in circuit form and then into tractable decision graphs, so the complete reason and general reason for a decision are computed in time linear in the graph size. Previously, converting a forest into a symbolic encoding and querying a SAT or MAX-SAT solver produced encodings full of auxiliary variables that do not correspond to class formulas, so complete reasons were not directly available. On datasets from UCI and the Penn Machine Learning Benchmarks, the compiled NNF circuits are smaller than existing ADD and ORD decision graphs on most datasets, and the largest compilation took 323.9 seconds.
Interpretation
A random forest classifier can be compiled into a set of circuits, each directly encoding the instances in one class, which supplies operable class formulas for later formal explanation. Earlier practice converted a forest into a symbolic encoding and queried a SAT or MAX-SAT solver, usually for a single explanation; those encodings carry many auxiliary variables, do not correspond to class formulas, and so cannot directly yield complete and general reasons. On datasets from UCI and the Penn Machine Learning Benchmarks, the generated NNF circuits are larger than the ADDs on four simple datasets, three of them binary, and much smaller than the ADDs on all other datasets, hence also smaller than the ORD decision graphs; compiling any considered classifier took at most 7.11 seconds.
Once class formulas are represented as decision graphs satisfying the weak test-once property, the complete reason and general reason for a decision are computed in time linear in the decision-graph size. Existing methods that compile a forest into decision graphs allow class formulas to be extracted as circuits, but the extracted circuits are not tractable and cannot yield complete and general reasons in linear time this way. Under the same number of features, classes, test instances and maximum depth, up to 100 test instances were explained per dataset, and classifiers with at least 50 trees were compiled for 12 of 19 datasets.
With complete and general reasons in hand, all sufficient reasons, necessary reasons and contrastive explanations of a decision can be enumerated, and the decision's robustness plus all shortest ways to flip it can be computed. A necessary reason only guarantees that at least one violation flips the decision, not that every violation does; general necessary reasons supply that stronger guarantee. Average robustness was very low across all tested datasets, with decisions flippable by changing fewer than two features on average, and for 17 of 19 datasets each decision had fewer than 10 shortest general necessary reasons.
Perspective
The demonstrated scope is datasets from the UCI Machine Learning Repository and the Penn Machine Learning Benchmarks, with random forests learned by WEKA, 85% of instances used for training and 15% for testing, and up to 100 test instances explained per dataset; compilation and explanation enumeration ran as a single-machine Python implementation.
In multi-class random forests an instance may belong to several classes at once; such instances were found in under 1% of cases and were assigned to the highest-ranked class with the most votes. The algorithm that conjoins and disjoins weak test-once decision graphs currently has no useful complexity bound and is assessed empirically only.
