Tilde

We consider three different ways in which TILDE can be run in its ILPROLOG implementation:

1. No packs: the normal implementation of TILDE as described by [5], where queries are generated one by one and each is evaluated on all relevant examples. Since queries are represented as terms, each evaluation of a query involves a meta-call in Prolog.
2. Disjoint execution of packs: a query pack is executed in which all queries in the pack are put beside one another; i.e., common parts are not shared by the queries. The computational redundancy in executing such a pack is the same as that in executing all queries one after another; the main difference is that in this case all queries are compiled.
3. Packed execution of packs: a compiled query pack is executed where queries share as much as possible.

The most interesting information is obtained by comparing (a) the actual query evaluation time in settings 2 and 3: this gives a view of the efficiency gain obtained by the removal of redundant computation itself (we will abbreviate this as exec in the tables); and (b) the total execution time in settings 1 and 3: this provides an indication of how much is gained by implementing packs in an ILP system, taking all other effects into account (re-implementation of the computation of heuristics via a bit matrix, use of compiled queries instead of meta-calls, etc.), or in other words: what the net effect of the whole re-implementation is (indicated as net in the tables).

In a first experiment we used Bongard problems, varying (1) the size of the data sets; (2) the complexity of the target hypothesis; and (3) TILDE's lookahead parameter. The complexity of the target hypothesis can be small, medium, or none. In the latter case the examples are random, which causes TILDE to grow ever larger trees in an attempt to find a good hypothesis; the size of the final tree then typically depends on the size of the data set. The lookahead parameter is used to control the number of levels the pack contains; with lookahead $n$, packs of depth $n+1$ are generated.

Table 1 gives an overview of results for the Bongard problems. The total induction time is reported, as well as (for pack-based execution mechanisms) the time needed for pack compilation and pack execution. Note that the total time includes not only pack compilation and execution, but also all other computations not directly related to packs (e.g., the computation of heuristics from the bitmatrix). The results can be interpreted as follows.

Table 1: Timings of TILDE runs on the Bongard data sets. $LA$ = lookahead setting; $bf$ = maximum branching factor. Reported times (in seconds) are the total time needed to build a tree, and the time spent on compilation respectively execution of packs.

LA	$bf$	original	disjoint			packed			speedup
			total	comp	exec	total	comp	exec	net	exec
Simple target hypothesis
1007 examples
0	16	0.74	0.62	0.14	0.13	0.49	0.05	0.07	1.51	1.86
1	24	2.44	1.64	0.35	0.45	1.09	0.14	0.11	2.24	4.09
2	18	7.49	4.07	0.8	1.57	2.15	0.27	0.16	3.48	9.81
3	21	29.9	16.52	3.65	7.26	7.18	1.26	0.28	4.17	25.9
2473 examples
0	16	1.82	1.43	0.17	0.34	1.13	0.07	0.16	1.61	2.13
1	24	5.72	3.34	0.34	1.17	2.24	0.11	0.3	2.55	3.9
2	18	17.2	8.45	0.78	3.95	4.4	0.27	0.39	3.92	10.1
3	21	69.8	33.0	3.57	17.5	13.7	1.13	0.69	5.11	25.4
4981 examples
0	19	3.69	2.72	0.29	0.67	2.16	0.12	0.32	1.71	2.09
1	24	11.4	6.22	0.35	2.41	4.17	0.13	0.63	2.74	3.83
2	18	34.7	16.0	0.74	8.14	8.24	0.25	0.88	4.21	9.25
3	21	142	62.4	3.61	36.5	24.9	1.09	1.45	5.69	25.1
Medium complexity target hypothesis
1031 examples
0	19	1.01	0.93	0.29	0.18	0.66	0.11	0.07	1.53	2.57
1	21	3.26	2.8	0.98	0.56	1.66	0.35	0.14	1.96	4
2	15	6.36	3.47	0.68	1.22	1.95	0.25	0.15	3.26	8.13
3	18	27.2	14.6	3.75	5.75	6.71	1.20	0.27	4.06	21.3
2520 examples
0	22	3.16	2.82	0.89	0.62	1.91	0.3	0.24	1.65	2.58
1	24	8.38	5.88	1.5	1.86	3.3	0.44	0.41	2.54	4.54
2	27	38.5	29.8	13.14	9.52	10.3	2.44	0.6	3.73	15.9
3	18	124	58.02	10.3	28.6	23.9	3.00	1.11	5.21	25.7
5058 examples
0	25	6.35	5.41	1.47	1.3	3.73	0.56	0.53	1.70	2.45
1	24	18.14	12.98	3.2	4.15	7.5	0.93	0.91	2.42	4.56
2	27	119	93.2	38.1	31.0	35.3	9.09	1.7	3.36	18.2
3	27	384	275	108	89.1	106	25.9	2.83	3.62	31.5
No target hypothesis
1194 examples
0	28	4.74	6.65	3.34	0.94	3.93	0.98	0.20	1.21	4.70
1	24	16.32	21.29	10.97	2.24	11.65	3.41	0.31	1.40	7.23
2	24	87.5	130	82.3	13.8	54.7	20.4	0.57	1.60	24.1
3	30	373	519	316	61.1	220	74.9	1.34	1.70	45.6
2986 examples
0	31	12.7	16.5	7.04	2.68	9.8	2.16	0.56	1.30	4.79
1	36	65.1	83.7	42.9	10.7	42.47	11.2	1.14	1.53	9.39
2	33	430	606	396	84	211.3	82.58	2.57	2.03	32.6
3	33	1934	2592	1610	375	946	332	6.58	2.04	57.0
6013 examples
0	31	25.3	30.3	11.8	5.53	18.3	3.53	1.27	1.38	4.35
1	39	154	198	91.2	33.4	99.9	22.0	3.13	1.54	10.7
2	39	1185	1733	1076	358	504	197	9	2.35	39.8
3	42	4256	6932	4441	1091	2006	695	14.5	2.12	75.4

First of all, the table shows that significant speedups can be obtained by using the pack mechanism; net speedups of over a factor 5.5 are obtained, while the execution itself is up to 75 times faster compared to disjoint execution.

A further observation is that for more complex target hypotheses greater speedups are obtained. This can be explained by the broom-like form of the packs in TILDE. Complex target hypotheses correspond to deep trees, and refinement of a node at a lower level of such a tree yields a pack with a long clause before the branching, which in accordance with our previous analysis should yield a speedup closer to the branching factor $b$ in the case of lookahead 0 (and more generally, closer to $b^{l+1}$ for lookahead $l$, although the latter is much harder to achieve). Note that the maximum branching factor occurring in each pack is included in the table in column $bf$.

Finally, deeper packs also yield higher speedups, and this effect is larger for more complex theories. This is understandable considering the following. Let us call the clause that is being refined $c$. With lookahead $l$, conjunctions of $l+1$ literals are added to the clause. In some cases the first of these $l+1$ literals may fail immediately, which causes this branch of the pack to have almost no execution time, while cutting away $b^l$ queries. Remember that according to our analysis, the speedup can in the limit approximate $b^l$ if the complexity of clause $c$ dominates over the complexity of the rest of the pack; such ``early failing branches'' in the pack cause the actual situation to approximate closer this ideal case.

We have also run experiments on the Mutagenesis data set (Table 2), both in a regression and a classification setting. Here, query packs are much larger than for the Bongard data set (there is a higher branching factor); with a lookahead of 2 the largest packs had over 20000 queries. For these large packs a significant amount of time is spent compiling the pack, but even then clear net speedups are obtained.⁵ A comparison of execution times turned out infeasible because in the disjoint execution setting the pack structures consumed too much memory.

Table 2: Timings of TILDE runs for Mutagenesis. A $-$ in the table indicates that that run ended prematurely.

LA	original	disjoint			packed			speedup ratio
		total	comp	exec	total	comp	exec	net	exec
Regression, 230 examples
0	31.5	52.9	1.96	25.5	45.5	1.02	19.25	0.69	1.33
1	194.99	248	55.9	109	107	12.6	16.6	1.82	6.53
2	2193	-	-	-	891	192	32.0	2.46	-
Classification, 230 examples
0	27.6	27.3	1.83	4.71	25.4	1.13	3.42	1.09	1.38
1	38.02	40.3	7.55	9.09	30.6	3.11	3.65	1.24	2.49
2	638	-	-	-	149	74.3	6.16	4.2	-