Multi-class Bayesian network classifiers get compilable explanations: 492 of 554 benchmark problems solved, up from 166
Synopsis
Explanations for multi-class Bayesian network classifiers were previously limited by a binary-class assumption and by compilation into ordered binary decision diagrams. A new algorithm arranges features on a feature tree embedded in a jointree and stops enumerating once a partial feature instantiation already decides the class, emitting an OR-decomposable NNF circuit on which complete and general reasons can be computed in linear time. On 554 benchmark problems it completed 492, against 166 for the prior algorithm.
Interpretation
The class formulas of multi-class Bayesian network classifiers can now be compiled into a circuit suited to computing explanations, rather than being restricted to two output classes. The prior compilation algorithm assumed a classifier with two output classes and compiled class formulas into ordered binary decision diagrams. On 554 benchmark problems the new algorithm completed 492 and the prior algorithm completed 166, with a 4-hour limit per problem.
Compilation recurses along a feature tree embedded in a jointree and stops enumerating as soon as the remaining features can no longer change the decision. A feature tree is a connected sub-tree of a jointree, and an edge whose separator holds neither the target nor any feature splits the features so that one part alone can decide the class. Experiments used the win95pts, cpcs54, andes, tcc4e and emdec6g networks, and on four hard andes problems the compiled circuit sizes were comparable to the prior algorithm.
The output circuit is OR-decomposable, meaning its disjuncts share no variables, so complete and general reasons can be computed in linear time. The prior algorithm's ordered binary decision diagrams correspond to the AND-decomposable form and need conversion to yield an OR-decomposable circuit of equal size. In a three-class disease-type Bayesian network example, the circuit yielded complete reasons, general reasons, and a contrastive explanation for why the diagnosis is not type 0.
Perspective
The demonstrated scope is 554 compilation problems over five discrete Bayesian networks with a 4-hour limit per problem, plus one three-class disease-diagnosis network used to illustrate explanation generation; the five networks all have binary targets, and the multi-class case appears only in the example network.
The prior algorithm cannot handle multi-class classifiers, so no runtime comparison exists in the multi-class setting; a systematic circuit-size comparison was also hard to collect because the prior algorithm takes very long on the harder problems.
