Symbolic Learning for Improving the Performance of Transversal-Computation Algorithms

Abstract

Using the hypergraphs as the central data structure in dynamic discrete association problems is a common practice. The computation of minimal transversals (i.e., the family of all minimal hitting sets) in those hypergraphs is a well-studied task associated with a large number of practical applications. However, both the dynamic nature of the problems and the non-polynomial behavior of all currently known algorithms for that task justify the search for performance optimizations that allow transversal-computation algorithms to consistently handle the potentially large problems while optimizing the use of computational resources. This scenario has been extensively studied from the perspective of the hypergraph, rough set, and testor theories, but this paper presents the first glimpse into a symbolic learning approach. We present a symbolic learning strategy, for the class of transversal-computation algorithms, designed to guide and optimize the search process. Since the proposed strategy is based on the background knowledge about the search space and not on a specific search technique, it can be adapted to a wide variety of algorithms. We present the learning strategy as well as its adaptation into two representative transversal-computation algorithms. The comparative experimental results reveal its computational behavior on different problem families.

Keywords

• Symbolic learning
• learning strategy
• transversal hypergraph
• minimal hitting set