2211677
Lattice-Search Runtime Distributions May Be Heavy-Tailed
Recent empirical studies show that runtime distributions of backtrack procedures for solving hard combinatorial problems often have intriguing properties. Unlike standard distributions (such as the normal), such distributions decay slower than exponentially and have "heavy tails". Procedures characterized by heavy-tailed runtime distributions exhibit large variability in efficiency, but a very straightforward method called rapid randomized restarts has been designed to essentially improve their average performance. We show on two experimental domains that heavy-tailed phenomena can be observed in ILP, namely in the search for a clause in the subsumption lattice. We also reformulate the technique of randomized rapid restarts to make it applicable in ILP and show that it can reduce the average search-time.
16914350
Biochemical Knowledge Discovery Using Inductive Logic Programming
Machine Learning algorithms are being increasingly used for knowledge discovery tasks. Approaches can be broadly divided by distinguishing discovery of procedural from that of declarative knowledge. Client requirements determine which of these is appropriate. This paper discusses an experimental application of machine learning in an area related to drug design. The bottleneck here is in finding appropriate constraints to reduce the large number of candidate molecules to be synthesised and tested. Such constraints can be viewed as declarative specifications of the structuralel ements necessary for high medicinal activity and low toxicity. The first-order representation used within Inductive Logic Programming (ILP) provides an appropriate description language for such constraints. Within this application area knowledge accreditation requires not only a demonstration of predictive accuracy but also, and crucially, a certification of novel insight into the structuralc hemistry. This paper describes an experiment in which the ILP system Progolw as used to obtain structural constraints associated with mutagenicity of molecules. In doing so Progol found a new indicator of mutagenicity within a subset of previously published data. This subset was already known not to be amenable to statistical regression, though its complement was adequately explained by a linear model. According to the combined accuracy/explanation criterion provided in this paper, on both subsets comparative trials show that Progol's structurally-oriented hypotheses are preferable to those of other machine learning algorithms.
18104124
A Note on Two Simple Transformations for Improving the Efficiency of an ILP System
Inductive Logic Programming (ILP) systems have had noteworthy successes in extracting comprehensible and accurate models for data drawn from a number of scientific and engineering domains. These results suggest that ILP methods could enhance the model-construction capabilities of software tools being developed for the emerging discipline of "knowledge discovery from databases." One significant concern in the use of ILP for this purpose is that of efficiency. The performance of modern ILP systems is principally affected by two issues: (1) they often have to search through very large numbers of possible rules (usually in the form of definite clauses); (2) they have to score each rule on the data (usually in the form of ground facts) to estimate "goodness". Stochastic and greedy approaches have been proposed to alleviate the complexity arising from each of these issues. While these techniques can result in order-of-magnitude improvements in the worst-case search complexity of an ILP system, they do so at the expense of exactness. As this may be unacceptable in some situations, we examine two methods that result in admissible transformations of clauses examined in a search. While the methods do not alter the size ofthe search space (that is, the number of clauses examined), they can alleviate the theorem-proving effort required to estimate goodness. The first transformation simply involves eliminating literals using a weak test for redundancy. The second involves partitioning the set of literals within a clause into groups that can be executed independently of each other. The efficacy ofthe se transformations are evaluated empirically on a number of well-known ILP datasets. The results suggest that for problems that require the use of highly nondeterminate predicates, the transformations can provide significant gains as the complexity of clauses sought increases.
1268789
Pharmacophore Discovery Using the Inductive Logic Programming System PROGOL
This paper presents a case study of a machine-aided knowledge discovery process within the general area of drug design. Within drug design, the particular problem of pharmacophore discovery is isolated, and the Inductive Logic Programming (ILP) system progol is applied to the problem of identifying potential pharmacophores for ACE inhibition. The case study reported in this paper supports four general lessons for machine learning and knowledge discovery, as well as more specific lessons for pharmacophore discovery, for Inductive Logic Programming, and for ACE inhibition. The general lessons for machine learning and knowledge discovery are as follows.1. An initial rediscovery step is a useful tool when approaching a new application domain.2. General machine learning heuristics may fail to match the details of an application domain, but it may be possible to successfully apply a heuristic-based algorithm in spite of the mismatch.3. A complete search for all plausible hypotheses can provide useful information to a user, although experimentation may be required to choose between competing hypotheses.4. A declarative knowledge representation facilitates the development and debugging of background knowledge in collaboration with a domain expert, as well as the communication of final results.
27782030
The Applicability to ILP of Results Concerning the Ordering of Binomial Populations
Results obtained in the 1950's on the ordering of k binomial populations are directly applicable to computing the size of data sample required to identify the best amongst k theories in an ILP search. The basic problem considered is that of selecting the best one of k (k ≥= 2) binomial populations on the basis of the observed frequency of 'success' on n observations. In the statistical formulation of the problem the experimenter specifies that he or she would like to guarantee that the probability of correct selection is at least P* (0 ≤ P* < 1) whenever the true difference between the best and second best population is at least d* (0 < d* ≤ 1). The principal result of interest is that for large values of k, the value of n required to meet any fixed specification (d*, P*) is approximately equal to some constant multiple of ln k. Depending on the k, d* and P* specified, this value of n can be substantially lower than that obtained within the corresponding PAC formulation. Applied to the search conducted by an ILP algorithm, the result guarantees with confidence level P*, that the true accuracy of the theory selected will be no more than d* below that of the best theory. In this paper, we review this basic result and test its predictions empirically. We also comment on the relevance to ILP of more recent work in the field.
12321308
Efficient gossip-based aggregate computation
Recently, there has been a growing interest in gossip-based protocols that employ randomized communication to ensure robust information dissemination. In this paper, we present a novel gossip-based scheme using which all the nodes in an n-node overlay network can compute the common aggregates of MIN, MAX, SUM, AVERAGE, and RANK of their values using O(n log log n) messages within O(log n log log n) rounds of communication. To the best of our knowledge, ours is the first result that shows how to compute these aggregates with high probability using only O(n log log n) messages. In contrast, the best known gossip-based algorithm for computing these aggregates requires O(nlog n) messages and O(log n) rounds. Thus, our algorithm allows system designers to trade off a small increase in round complexity with a significant reduction in message complexity. This can lead to dramatically lower network congestion and longer node lifetimes in wireless and sensor networks, where channel bandwidth and battery life are severely constrained.
9234553
Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems
Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on at mosta bits? Let 0≤a≤n–1. We show that any deterministic protocol, as well as any error-free quantum protocol (C* version), for this problem requires at least n–2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactlya bits. We also prove a lower bound of n/2–1 for error-free Q* quantum protocols. Our results are obtained by employing basic tools from combinatorics and calculus to lower-bound the ranks of the appropriate matrices.
38873931
Distributions on level-sets with applications to approximation algorithms
We consider a family of distributions on fixed-weight vectors in {0, 1}/sup t/; these distributions enjoy certain negative correlation properties and also satisfy pre-specified conditions on their marginal distributions. We show the existence of such families, and present a linear-time algorithm to sample from them. This yields improved approximation algorithms for the following problems: (a) low-congestion multi-path routing; (b) maximum coverage versions of set cover; (c) partial vertex cover problems for bounded-degree graphs; and (d) the Group Steiner Tree problem. For (a) and (b), the improvement is in the approximation ratio; for (c), we show how to speedup existing approximation algorithms while preserving the best-known approximation ratio; we also improve the approximation ratio for certain families of instances of unbounded degree. For (d), we derive an approximation algorithm whose approximation guarantee is at least as good as what is known; our algorithm is shown to have a better approximation guarantee for the worst known input families for existing algorithms.
17105049
Data-Driven Time-Parallelization in the AFM Simulation of Proteins
Molecular dynamics is a popular technique to simulate the behavior of physical systems, with resolution at the atomic scale. One of its limitations is that an enormous computational effort is required to simulate to realistic time spans. Conventional parallelization strategies have limited effectiveness in dealing with this difficulty. We recently introduced a more scalable approach to parallelization, where data from prior, related, simulations are used to parallelize a simulation in the time domain. We demonstrated its effectiveness in nano-mechanics simulations. In this paper, we develop our approach so that it can be used in a soft-matter application involving the atomic force microscopy simulation of proteins. We obtain an order of magnitude improvement in performance when we combine time parallelization with conventional parallelization. The significance of this work lies in demonstrating the promise of data-driven time parallelization in soft-matter applications, which are more challenging than the hard-matter applications considered earlier.
10702922
Improved Algorithms via Approximations of Probability Distributions
We present two techniques for constructing sample spaces that approximate probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor and Naor. We show how to efficiently combine this construction with the method of conditional probabilities to yield improved parallel algorithms for problems such as set discrepancy, finding large cuts in graphs, and finding large acyclic subgraphs. The second is a construction of small probability spaces approximating general independent distributions which are of smaller size than the constructions of Even, Goldreich, Luby, Nisan, and Veli?kovi?.