A Restarted Strategy for Efficient Subsumption Testing

• Autorzy: Kuželka O. , Železný F.
• Języki publikacji: EN

Abstrakty

EN

We study runtime distributions of subsumption testing. On graph data randomly sampled from two different generative models we observe a gradual growth of the tails of the distributions as a function of the problem instance location in the phase transition space. To avoid the heavy tails, we design a randomized restarted subsumption testing algorithm RESUMER2. The algorithm is complete in that it correctly decides both subsumption and non-subsumption in finite time. A basic restarted strategy is augmented by allowing certain communication between odd and even restarts without losing the exponential runtime distribution decay guarantee resulting from mutual independence of restart pairs. We empirically test RESUMER2 against the state-of-the-art subsumption algorithm Django on generated graph data as well as on the predictive toxicology challenge (PTC) data set. RESUMER2 performs comparably with Django for relatively small examples (tens to hundreds of literals), while for further growing example sizes, RESUMER2 becomes vastly superior.

Słowa kluczowe

EN

relational learning; graph mining; subsumption; homomorphism; Randomized Complete Algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 89, nr 1
• Strony: 95--109
• Opis fizyczny: bibliogr. 14 poz., tab., wykr.

Twórcy

autor

Kuželka O.

autor

Železný F.

• Intelligent Data Analysis Research Group Department of Cybernetics Czech Technical University in Prague, Prague, Czech Republic,

Bibliografia

• [1] Barabasi, A. L., Albert, R.: Emergence of scaling in random networks, Science, 286(5439), 1999, 509-512.
• [2] Bollobas, B.: Modern Graph Theory, Springer, 1998, ISBN 0387984887.
• [3] Chen, H., Gomes, C., Selman, B.: Formal Models of Heavy-Tailed Behavior in Combinatorial Search, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, Springer-Verlag, 2001.
• [4] Giordana, A., Saitta, L.: Phase Transitions in Relational Learning, Machine Learning, 41(2), 2000, 217-251.
• [5] Gomes, C. P., Fernández, C., Selman, B., Bessi`ere, C.: Statistical Regimes Across Constrainedness Regions, Constraints, 10(4), 2005, 317-337, ISSN 1383-7133.
• [6] Gomes, C. P., Selman, B., Crato, N., Kautz, H. A.: Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems, Journal of Automated Reasoning, 24(1/2), 2000, 67-100.
• [7] Helma, C., King, R. D., Kramer, S., Srinivasan, A.: The predictive toxicology challenge 2000-2001, Bioinformatics, 17(1), 2001, 107-108.
• [8] Kirkpatrick, S., Selman, B.: Critical behavior in the satisfiability of random Boolean expressions, Science, 264(5163), 27 May 1994, 1297-1301.
• [9] Maloberti, J., Sebag, M.: Fast Theta-Subsumption with Constraint Satisfaction Algorithms, Machine Learning, 55(2), 2004, 137-174, ISSN 0885-6125.
• [10] Sebag, M., Rouveirol, C.: Tractable Induction and Classification in First-Order Logic via Stochastic Matching, Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, Morgan Kaufmann, 1997.
• [11] Srinivasan, A.: A study of two sampling methods for analysing large datasets with ILP, Data Mining and Knowledge Discovery, 3(1), 1999, 95-123.
• [12] Walsh, T.: Search in a SmallWorld, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, Morgan Kaufmann, San Francisco, CA, USA, 1999, ISBN 1-55860-613-0.
• [13] Wu, H., van Beek, P.: Restart Strategies: Analysis and Simulation, Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, Springer, 2003, ISBN 3-540-20202-1.
• [14] Zelezny, F., Srinivasan, A., Page, D.: Randomised Restarted Search in ILP, Machine Learning, 64(1-2), 2006, 183-208.