基于拓扑信息加速马尔科夫毯学习

Accelerating the Recovery of Markov Blanket Using Topology Information

目标变量的马尔科夫毯(MB)是用于预测其状态的最优特征子集。提出一种新的约束学习类MB推导算法FSMB,它遵循后向选择的搜索策略,并依赖条件独立(CI)测试删除任意结点对之间的伪连接。与传统约束学习类算法不同,FSMB能从已执行的CI测试推导出不同结点扮演d-分割(d-separation)结点的优先等级;而后基于该信息在未来优先执行条件集中包含高优先级结点的CI测试,从而更快速地判断并删除伪连接边。该策略可帮助快速缩小搜索空间,从而大大提升学习效率。基于仿真网络的实验研究显示,FSMB在计算效率上较经典的PCMB和IPC-MB有显著的提升,而学习效果相当;在面对较大网络结构时(比如100和200个结点),甚至比公认最快速的IAMB还节省近40%的计算量,但学习效果要远优于IAMB。基于16个UCI数据集和4个经典的分类模型的实验显示,基于FSMB输出的特征集合所训练模型的分类准确率普遍接近或高于基于原有特征全集训练所得模型。因此,FSMB是快速且有效的MB推导算法。

Markov blanket（MB） has been known as the optimal feature subset for prediction, and there exist fertile works to induce MB by local search since 1996. A novel one called FSMB was proposed which heavily relies on condi- tional independence（CI） test to determine the existence of connection between nodes, so it is kind of constraint-based learning as well. However,it differs from previous works by treating candidate CI tests unfairly. FSMB extracts critical d^separation topology information from conducted CI tests, and applies them to sort and perform those more likely to uncover independent relations with priority. Search space therefore is expected to shrink quickly in a more efficient man- ner. Experimental studies indicate that FSMB achieves tremendous improvement over state-obart works PCMB and IPC-MB in term of time efficiency, but with no sacrifice on learning quality. When given large networks（e, g. 100 and 200 nodes）, FSMB runs even more efficiently than IAMB which is recognized as the fastest algorithm by now, requiring up to 40~ fewer CI tests, and produces much higher quality of results. Experiments with UCI data sets and four classi- cal classification models indicate that the classification accuracy of the models trained on the output of FSMB are close to or exceed performance achieved by models trained on all features, hence FSMB is an effective feature subset selector.