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.
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.
18954
Approximation algorithms for the covering Steiner problem
The covering Steiner problem is a generalization of both the k-MST and the group Steiner problems: given an edge-weighted graph, with subsets of vertices called the groups, and a nonnegative integer value (called the requirement) for each group, the problem is to find a minimum-weight tree spanning at least the required number of vertices of every group. When all requirements are equal to 1, this becomes the group Steiner problem, while if there is only one group which contains all vertices of the graph the problem reduces to k-MST with k equal to the requirement of this unique group. We discuss two different (but equivalent) linear relaxations of the problem for the case when the given graph is a tree and construct polylogarithmic approximation algorithms based on randomized LP rounding of these relaxations. By using a probabilistic approximation of general metrics by tree metrics due to Bartal, our algorithms also solve the covering Steiner problem on general graphs with a further polylogarithmic worsening in the approximation ratio.
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.
14773410
Algorithmic aspects of capacity in wireless networks
This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs {(si,ti)}, what is the maximum throughput capacity of the network, i.e. the rate at which data from the sources to their corresponding destinations can be transferred in the network? (ii) Can network protocols be designed that jointly route the packets and schedule transmissions at rates close to the maximum throughput capacity? Much of the earlier work focused on random instances and proved analytical lower and upper bounds on the maximum throughput capacity. Here, in contrast, we consider arbitrary wireless networks. Further, we study the algorithmic aspects of the above questions: the goal is to design provably good algorithms for arbitrary instances. We develop analytical performance evaluation models and distributed algorithms for routing and scheduling which incorporate fairness, energy and dilation (path-length) requirements and provide a unified framework for utilizing the network close to its maximum throughput capacity.Motivated by certain popular wireless protocols used in practice, we also explore "shortest-path like" path selection strategies which maximize the network throughput. The theoretical results naturally suggest an interesting class of congestion aware link metrics which can be directly plugged into several existing routing protocols such as AODV, DSR, etc. We complement the theoretical analysis with extensive simulations. The results indicate that routes obtained using our congestion aware link metrics consistently yield higher throughput than hop-count based shortest path metrics.
2418753
Computing with very weak random sources
For any fixed /spl epsiv/>0, we show how to simulate RP algorithms in time n/sup O(log n/) using the output of a /spl delta/-source with min-entropy R(/spl epsiv/). Such a weak random source is asked once for R(/spl epsiv/) bits; it outputs an R-bit string such that any string has probability at most 2/sup -R/(/spl epsiv//). If /spl epsiv/>1-1/(k+1), our BPP simulations take time n/sup O(log(k/ n)) (log/sup (k/) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy R/sup /spl Omega/(1/), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson.<<ETX>>
42237174
On the Complexity of Distributed Network Decomposition
In this paper, we improve the bounds for computing a network decomposition distributively and deterministically. Our algorithm computes an (n?(n),n?(n))-decomposition innO(?(n))time, whereformula. As a corollary we obtain improved deterministic bounds for distributively computing several graph structures such as maximal independent sets and ?-vertex colorings. We also show that the class of graphs G whose maximum degree isnO(?(n))where ?(n)=1/log lognis complete for the task of computing a near-optimal decomposition, i.e., a (logn, logn)-decomposition, in polylog(n) time. This is a corollary of a more general characterization, which pinpoints the weak points of existing network decomposition algorithms. Completeness is to be intended in the following sense: if we have an algorithmAthat computes a near-optimal decomposition in polylog(n) time for graphs inG, then we can compute a near-optimal decomposition in polylog(n) time for all graphs.