Skip to main content
Journal cover image

Randomised restarted search in ILP

Publication ,  Conference
Železný, F; Srinivasan, A; Page, CD
Published in: Machine Learning
September 1, 2006

Recent statistical performance studies of search algorithms in difficult combinatorial problems have demonstrated the benefits of randomising and restarting the search procedure. Specifically, it has been found that if the search cost distribution of the non-restarted randomised search exhibits a slower-than-exponential decay (that is, a "heavy tail"), restarts can reduce the search cost expectation. We report on an empirical study of randomised restarted search in ILP. Our experiments conducted on a high-performance distributed computing platform provide an extensive statistical performance sample of five search algorithms operating on two principally different classes of ILP problems, one represented by an artificially generated graph problem and the other by three traditional classification benchmarks (mutagenicity, carcinogenicity, finite element mesh design). The sample allows us to (1) estimate the conditional expected value of the search cost (measured by the total number of clauses explored) given the minimum clause score required and a "cutoff" value (the number of clauses examined before the search is restarted), (2) estimate the conditional expected clause score given the cutoff value and the invested search cost, and (3) compare the performance of randomised restarted search strategies to a deterministic non-restarted search. Our findings indicate striking similarities across the five search algorithms and the four domains, in terms of the basic trends of both the statistics (1) and (2). Also, we observe that the cutoff value is critical for the performance of the search algorithm, and using its optimal value in a randomised restarted search may decrease the mean search cost (by several orders of magnitude) or increase the mean achieved score significantly with respect to that obtained with a deterministic non-restarted search.

Duke Scholars

Published In

Machine Learning

DOI

EISSN

1573-0565

ISSN

0885-6125

Publication Date

September 1, 2006

Volume

64

Issue

1-3

Start / End Page

183 / 208

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 1702 Cognitive Sciences
  • 0806 Information Systems
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Železný, F., Srinivasan, A., & Page, C. D. (2006). Randomised restarted search in ILP. In Machine Learning (Vol. 64, pp. 183–208). https://doi.org/10.1007/s10994-006-7733-9
Železný, F., A. Srinivasan, and C. D. Page. “Randomised restarted search in ILP.” In Machine Learning, 64:183–208, 2006. https://doi.org/10.1007/s10994-006-7733-9.
Železný F, Srinivasan A, Page CD. Randomised restarted search in ILP. In: Machine Learning. 2006. p. 183–208.
Železný, F., et al. “Randomised restarted search in ILP.” Machine Learning, vol. 64, no. 1–3, 2006, pp. 183–208. Scopus, doi:10.1007/s10994-006-7733-9.
Železný F, Srinivasan A, Page CD. Randomised restarted search in ILP. Machine Learning. 2006. p. 183–208.
Journal cover image

Published In

Machine Learning

DOI

EISSN

1573-0565

ISSN

0885-6125

Publication Date

September 1, 2006

Volume

64

Issue

1-3

Start / End Page

183 / 208

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 1702 Cognitive Sciences
  • 0806 Information Systems
  • 0801 Artificial Intelligence and Image Processing