Flexible Tree Matching

Abstract

Tree-matching problems arise in many computational domains. The literature provides several methods for creating correspondences between labeled 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 introduce 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 algorithm for the problem, and demonstrate how structured prediction techniques can learn the algorithm's parameters from a set of example matchings. Finally, we present results from applying the method to tasks in Web design.