  Most structure inference methods either rely on exhaustive search or are
purely data-driven. Exhaustive search robustly infers the structure of
arbitrarily complex data, but it is slow. Data-driven methods allow efficient
inference, but do not generalize when test data have more complex structures
than training data. In this paper, we propose a hybrid inference algorithm, the
Neurally-Guided Structure Inference (NG-SI), keeping the advantages of both
search-based and data-driven methods. The key idea of NG-SI is to use a neural
network to guide the hierarchical, layer-wise search over the compositional
space of structures. We evaluate our algorithm on two representative structure
inference tasks: probabilistic matrix decomposition and symbolic program
parsing. It outperforms data-driven and search-based alternatives on both
tasks.
