Convex Structure Learning in Log-Linear Models: Beyond Pairwise Potentials
Mark Schmidt, Kevin P. Murphy · 2010
Previous work has examined structure learning in log-linear models with `1-regularization, largely focusing on the case of pairwise potentials. In this work we con-sider the case of models with potentials of arbitrary order, but that satisfy a hierarchi-cal constraint. We enforce the hierarchical constraint using group `1-regularization with overlapping groups. An active set method that enforces hierarchical inclusion allows us to tractably consider the exponential num-ber of higher-order potentials. We use a spectral projected gradient method as a sub-routine for solving the overlapping group `1-regularization problem, and make use of a sparse version of Dykstra’s algorithm to com-pute the projection. Our experiments indi-cate that this model gives equal or better test set likelihood compared to previous models. 1