Learning Markov Network Structure with Decision Trees
Learning Markov Network Structure with Decision Trees
复制标题
用决策树学习马尔可夫网络结构
DOI：
10.1109/icdm.2010.128
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Jesse Davis
中科院分区：
文献类型：
--
作者：
Daniel Lowd;Jesse Davis
传统的马尔可夫网络结构学习算法搜索全局有用的特征。然而，这些算法往往是缓慢的，容易找到局部最优，由于可能的结构的大空间。Ravikumar等人最近提出了另一种想法，即应用L1逻辑回归来学习每个变量的一组成对特征，然后将其组合成一个全局模型。本文提出了DTSL算法，它使用概率决策树作为局部模型。我们的方法有两个显著的优点：它更有效，并且能够发现捕获变量之间更复杂交互的特征。我们的方法也可以被看作是一种将依赖网络转换为一致概率模型的方法。在对13个数据集的广泛实证评估中，我们的算法获得了与三种标准结构学习算法相当的准确性，同时运行速度快1-4个数量级。
Traditional Markov network structure learning algorithms perform a search for globally useful features. However, these algorithms are often slow and prone to finding local optima due to the large space of possible structures. Ravikumar et al. recently proposed the alternative idea of applying L1 logistic regression to learn a set of pair wise features for each variable, which are then combined into a global model. This paper presents the DTSL algorithm, which uses probabilistic decision trees as the local model. Our approach has two significant advantages: it is more efficient, and it is able to discover features that capture more complex interactions among the variables. Our approach can also be seen as a method for converting a dependency network into a consistent probabilistic model. In an extensive empirical evaluation on 13 datasets, our algorithm obtains comparable accuracy to three standard structure learning algorithms while running 1-4 orders of magnitude faster.