Learning the Structure of Sum-Product NetworksLearning the Structure of Sum-Product NetworksGens, Robert and Domingos, Pedro M.2013

Paper summaryopenreviewThis papers proposes a technique for learning the structure of SPNs by recursively splitting the data set along instances and dimensions. The data set is split by dimensions if the set of variables can be partitioned into independent subsets. Otherwise, it is split by instances. This paper improves upon previous work of Dennis and Ventura (NIPS 2012) by splitting on both instances and variables in a manner that fits in elegantly with the simplified recursive definition of SPNs used in the paper. The algorithm guarantees a locally optimal structure, if an independence oracle is available. Results show that the model is comparable to other graphical model learning approaches in terms of log probs but massively outperforms them wins in terms of time.
The proposed algorithm is a novel application of using simple clustering and mutual independence finding methods to SPN structure learning. The paper is well written and explains SPNs and the structure learning algorithm clearly.
Pros:
- The authors do a thorough evaluation on a large number of data sets.
- Significant gains in conditional log probs (though, as pointed out in the paper, this might be in part due to exact inference in SPN compared to lower-bounds in other models).
- Much faster inference at the cost of slightly worse log probs.
Cons:
- The algorithm makes hard decisions to split the data recursively. This makes portions of the data set completely inaccessible to each other after each recursion step. This might make the model very sensitive to any sub-optimal splits made early on.
- Weak or higher-order relationships among variables that are not captured by the independence checker may be lost.
- The algorithm can only learn SPNs where product nodes have disjoint scopes.

This papers proposes a technique for learning the structure of SPNs by recursively splitting the data set along instances and dimensions. The data set is split by dimensions if the set of variables can be partitioned into independent subsets. Otherwise, it is split by instances. This paper improves upon previous work of Dennis and Ventura (NIPS 2012) by splitting on both instances and variables in a manner that fits in elegantly with the simplified recursive definition of SPNs used in the paper. The algorithm guarantees a locally optimal structure, if an independence oracle is available. Results show that the model is comparable to other graphical model learning approaches in terms of log probs but massively outperforms them wins in terms of time.
The proposed algorithm is a novel application of using simple clustering and mutual independence finding methods to SPN structure learning. The paper is well written and explains SPNs and the structure learning algorithm clearly.
Pros:
- The authors do a thorough evaluation on a large number of data sets.
- Significant gains in conditional log probs (though, as pointed out in the paper, this might be in part due to exact inference in SPN compared to lower-bounds in other models).
- Much faster inference at the cost of slightly worse log probs.
Cons:
- The algorithm makes hard decisions to split the data recursively. This makes portions of the data set completely inaccessible to each other after each recursion step. This might make the model very sensitive to any sub-optimal splits made early on.
- Weak or higher-order relationships among variables that are not captured by the independence checker may be lost.
- The algorithm can only learn SPNs where product nodes have disjoint scopes.