Chow and Liu [2] has shown that learning trees that maximize likelihood score given data can be done in polynomial time. A generalization of directed trees are polytrees. However, Dasgupta [3] has proved that learning maximum likelihood polytrees from data (and even approximation of the optimal result with a constant ratio) is NP-Hard. Therefore, researchers have focused on learning maximum likelihood polytrees with a constant number of roots. Gaspers et al. [5] have presented such an algorithm with complexity O(mn~(3k+4)) using matroid theory. We present a direct combinatorial algorithm with complexity O(mn~(3k+1)).
展开▼
