Abstract

Tree-matching problems arise in many computa-tional domains.  The literature provides several methods for creating correspondences between la-beled trees; however, by definition, tree-matching algorithms rigidly preserve ancestry. That is, once two nodes have been placed in correspondence,their descendants must be matched as well. We in-troduce flexible tree matching, which relaxes this rigid requirement in favor of a tunable formulation in which the role of hierarchy can be controlled.We show that flexible tree matching is strongly NP-complete, give a stochastic approximation al-gorithm for the problem, and demonstrate how structured prediction techniques can learn the al-gorithm’s parameters from a set of example match-ings. Finally, we present results from applying the method to tasks in Web design.