多类贝叶斯网络分类器也能编译解释了:554道题里完成数从166升到492
核心概要
多类贝叶斯网络分类器的决策解释此前受限于二分类假设,且只能编译成有序二元决策图。新算法借助嵌入联合树的特征树,在部分特征实例即可判定类别时提前停止枚举,直接输出或分解的NNF电路,使完整理由与一般理由可在该电路上线性时间计算。在554道基准题上,新算法完成492道,此前算法完成166道。
深度剖析
多类贝叶斯网络分类器的类别公式现在可以被编译成一种便于计算解释的电路,而不再局限于二分类输出。 此前的编译算法假定分类器只有两个输出类别,并把类别公式编译成有序二元决策图。 在554道基准题上,新算法完成492道,此前算法完成166道,每题限时4小时。
编译过程沿一棵嵌入联合树的特征树递归展开,一旦剩余特征不再影响判定就停止枚举。 特征树是联合树的连通子树,其边上不含目标与特征的分离集可以把特征分成两部分,使一部分特征实例单独就能判定类别。 实验使用win95pts、cpcs54、andes、tcc4e、emdec6g五个贝叶斯网络,其中andes的四个难题上电路规模与此前算法相当。
输出电路满足或分解性质,即每个析取支之间不共享变量,完整理由和一般理由因此可以在线性时间内算出。 此前算法输出的有序二元决策图对应与分解形式,需要再转换才能得到等大的或分解电路。 在疾病类型诊断的三类贝叶斯网络示例中,该电路给出了完整理由、一般理由以及针对“为何不是类型0”的对比解释。
启示与展望
演示范围是五个离散贝叶斯网络上的554道编译题,每题限时4小时,另有一个三类疾病诊断网络用于展示解释的生成;五个网络的目标变量均为二分类,多类情形只在示例网络中说明。
此前算法无法处理多类分类器,因此多类设定下没有与之对比的运行时间数据;电路规模的系统比较也因此前算法在较难问题上耗时过长而难以展开。
