The predicates used for Inductive Logic Programming (ILP) systems are usually elusive and need to be hand-crafted in advance, which limits the generalization of the system when learning new rules without suficient background knowledge. Predicate Invention (PI) for ILP is the problem of discovering new concepts that describe hidden relationships in the domain. PI can mitigate the generalization problem for ILP by inferring new concepts, giving the system a better vocabulary to compose logic ruless. Although there are several PI approaches for symbolic ILP systems, PI for NeSy ILP systems that can handle visual input to learn logical rules using diferentiable reasoning is relatively unaddressed. To this end, we propose a neural-symbolic approach, NeSy- , to invent predicates from visual scenes for NeSy ILP systems based on clustering and extension of relational concepts. ( denotes the abbrivation of Predicate Invention). NeSy- processes visual scenes as input using deep neural networks for the visual perception and invents new concepts that support the task of classifying complex visual scenes. The invented concepts can be used by any NeSy ILP systems instead of hand-crafted background knowledge. Our experiments show that the PI model is capable of inventing high-level concepts and solving complex visual logic patterns more eficiently and accurately in the absence of explicit background knowledge. Moreover, the invented concepts are explainable and interpretable, while also providing competitive results with state-of-the-art NeSy ILP systems based on given knowledge.
Inductive Logic Programming (ILP) learns generalized logic programs from given data [
Const.
Basic Pred.
B.K.
Pred.
NeSy-ILP Object:O1/O2,Shape:Sphere/Cube;
Color:Blue/Pink/Green;
Direction:Left/Right/Front/Behind color/2/obj,color;shape/2/obj,shape;
dir/2/obj,obj b_sp(O1):-color(O1,B),shape(O1,Sp). g_sp(O1):-color(O1,G),shape(O1,Sp). g_cu(O1):-color(O1,G),shape(O1,Cu).
left_side/2/obj,obj right_side/2/obj,obj
NeSy-π is the concept of the blue sphere. In classical NeSy-ILP systems, this can be explained by a clause blue_sphere(X):-color(X, blue), shape(X, sphere) given as background knowledge. With PI systems, such concepts are learned from the basic predicates color(X, blue) and shape(X, sphere) by concatenation.
Recently, several neural-symbolic ILP frameworks have been proposed [
To this end, we propose Neural-Symbolic Predicate Invention (NeSy- ), a predicate invention pipeline that can invent relational concepts given visual scenes by using primitive predicates, reducing dependence on prior knowledge (see Fig. 1 for an example). NeSy- discovers predicates describing attributes of objects and their spatial relations in visual scenes, which is equivalent to summarizing the required knowledge from scenes. The NeSy- system (shown in Fig. 2) consists of two iterative steps: 1) evaluating clauses consisting of existing predicates and 2) inventing new predicates. To evaluate the existing predicates we propose two novel indicators of necessity and suficiency which are computed by mapping the examples to a 2D Euclidean space. Only the predicates satisfying the above properties are considered in the invention of Visual ILP problem positive negative : clause weights : loss function Invent new predicates
Eval
Invent
Minimize the classification loss
Invented inv_pred3(Orii1hnn,o((O(OO2O51,1,,O,XX3O)),2,,O,i5rn)h(:oO-02),,Xr)h,oi(nO(1O,3O,5X,)r,ho0). Pirnevd_picreadt3es 0.9: targetiiii(nnnnXvv(()__OO:pp41-rr,,eeXXdd))34,,ii((nnOO((12OO,,52OO,,24XX,,))OO,,35i,)nO.(5O)3,,X), inv_︙pred4(Ori1hn,o(O(O2O1,1,O,X5O))2,:,i-rnh(oO02),,Xr)h,oi(nO(1O,5O,5X,)rho0). inv︙_pred4 0.1: ︙targetici(nonX(l()OoO:1r4-,(,XOX)1),,,ipinin(n(OkO2)5,,,XsX)h),a,ipne((OO32,,Xc)u,be). new predicates. NeSy- can be integrated with existing NeSy-ILP systems providing them with a rich vocabulary to generate eficient solutions.
Overall, we make the following important contributions: (1) We propose NeSy- , a NeSy
predicate invention framework compatible with NeSy ILP systems. NeSy- extends NeSy ILP
systems by providing the capability to enrich their vocabularies by learning from data. (2) We
propose two criteria for evaluating clauses, which can then be used for predicate invention
tasks. (3) We develop 3D Kandinsky Patterns, which extends Kandisnky Patterns to the 3D
world, and it achieves faster generation than other environments, e.g. CLEVR [
Inductive Logic Programming. ILP problem is tuple (ℰ +, ℰ − , ℬ, ℒ), where ℰ + is a set of positive examples, ℰ − is a set of negative examples, ℬ is background knowledge, and ℒ is a language. We assume that the examples and background knowledge are ground atoms. The solution of an ILP problem is a set of definite clauses ℋ ⊆ ℒ that satisfies the following conditions: (1) ∀ ∈ ℰ +, ℋ ∪ ℬ |= and (2) ∀ ∈ ℰ − ℋ ∪ ℬ ̸|= . Typically the search algorithm starts with general clauses. If the current clauses are too general (strong), i.e., they entail too many negative examples, then the solver specifies (weakens) them incrementally. This weakening operation is called a refinement , which is one of the essential tools for ILP.
Ne-Sy Inductive Logic Programming. We address the ILP problem in visual scenes, which
is called visual ILP problem, where each example is given as an image with multiple objects [
Clause Evaluation. We evaluate each clause to in- 4: # Evaluate each set of clauses
vent new predicates. (Line 1–3) A set of clauses is 5: for pp ∈ ℘() do
initialized, and extended by generating new clauses 6: ness ← ness (p, )
by adding a body atom to each clause in using the 7: spuff ← suff (p, )
available predicates in ℒ. (Line 5–7) Promising predi- 8: end for
cates are those that can form a clause containing many 9: # Invent new predicates
positive examples but no negative examples. We de- 10: n*ess ← top_k (℘(), ness )
velop two evaluation metrics for clauses in NeSy-ILP 11: s*uff ← top_k (℘(), suff )
systems, which we call necessity and suficiency . Intu- 12: ℒ ← update(ℒ, n*ess , s*uff )
itively, necessary clauses are those that are those that 13: end while
are true in all positive examples, but they can also be 14: return ℒ,
true in negative examples. Suficient clauses are those
that are true in only some of positive examples, some
of positive examples maybe false, but they are always false in negative examples. To handle
complex visual scenes, NeSy- uses a diferentiable reasoning function for scenes from
complex visual patterns in ILP [
inv_pred4(O1,O2,O5). inv_pred4(O1,O2,O5):in(O1,X),in(O2,X),in(O5,X), rho(O1,O2,rho0),rho(O1,O5,rho3). perform classification as follows: (i) conversion of a positive or negative visual scene into a set of probabilistic atoms, (ii) diferentiable forward reasoning using weighted clauses and probabilistic atoms, and (iii) the reasoning result is used to predict the label of the visual scene.
Given set of clauses , we assume that each subset of defines a new predicate, i.e. we
consider p ∈ ℘() defining predicate p where ℘() is a powerset of . To eficiently evaluate
clauses, NeSy- maps each training pair (+, − ) ∈ , to a point in a 2D Euclidean scoring
space ( (+), (− )) ∈ [
) represents the score of positive example + , i.e., the probability that a positive example is classified as positive. (− ) represents the score of negative example − , i.e., the probability that a negative example is classified as positive. |+| and |− | represent the number of positive and negative images in the dataset, respectively. On the scoring space, the necessity of clauses p is measured as follows: The suficiency of clauses p is measured as:
p ness = ness (p, +) = 1
∑︁ |+| +∈+
p (+), p suff = suff (p, − ) = 1
∑︁ (1 − p (− )), |− | − ∈− (1) (2)
Predicate Invention. NeSy- invents new predicates by composing clauses to define new predicates using high scoring clauses in the two metrics. Given ℘() and their evaluation (a) Three Same (b) Two Pairs (c) Shape in Shape (d) Check Mark scores, ness and suff , top- sets of clauses for each score are selected from ℘(), i.e. n*ess = top_k (℘(), ness ) and s*uff = top_k (℘(), suff ). Let * = n*ess ∪ s*uff , i.e. * is a set of clause sets that have high scores in the metrics. New predicates are composed by taking disjunction of high-scored clauses to define them. Let {1, ..., } ∈ * , we compose the following clauses to define a new predicate: new ← body (1), . . . , new ← body (), where new is an atom using a new predicate and body () is body atoms of clause .
For example, assume the following clauses defining inv_pred1 and inv_pred2 are selected: inv_pred1(X):-in(O1, X), in(O2, X), color(O1, blue), color(O2, blue).
inv_pred2(X):-in(O1, X), in(O2, X), color(O1, red), color(O2, red). then NeSy- invents a new predicate by taking the disjunction of their bodies: inv_pred3(X):-in(O1, X), in(O2, X), color(O1, blue), color(O2, blue).
inv_pred3(X):-in(O1, X), in(O2, X), color(O1, red), color(O2, red). where inv_pred3 is an invented 1-ary predicate that can be interpreted as: “There is a pair of objects with the same color (blue or red) in the image.”. By iterating the steps evaluate and invent, NeSy- discovers new high-level relational concepts useful for classifying given visual scenes. The invented predicates are then fed into a NeSy ILP system to solve visual ILP problems.
We aim to answer the following questions: Q1: Does NeSy- invent predicates from complex
visual scenes for NeSy ILP systems, reducing required background knowledge? Q2: Is NeSy-
computationally eficient?
(A1. Predicate Invention) : We designed four visual scenes with diferent patterns for 2D
and 3D Kandinsky patterns, respectively. (see Fig. 4). Each pattern has at least two varieties.
For example, the pattern three same can be three same blue sphere, or three same pink cube, or
something similar. All the patterns that we designed cannot be simply described by one or few
given basic predicate, but need several long clauses. The results are compared with no predicate
invention equipped model ILP [
To solve such patterns, classical NeSy-ILP systems requires background knowledge and predicates to help the system reason about the final rules. For example, to solve pattern three same, NeSy-ILP can give the concept two_same(A, B) as background knowledge, then chains two_same(A, B) twice, i.e. three_same(A, B, C) : − two_same(A, B), two_same(B, C)., and two_same(A, B) is given as background knowledge described by other five BK predicates and five BK clauses as follows: two_same(A,B):-same_color_pair(A,B),same_shape_pair(A,B),in(A,X),in(B,X). same_shape_pair(A,B):-shape(A,sq),shape(B,sq),in(A,X),in(B,X). same_shape_pair(A,B):-shape(A,cir),shape(B,cir),in(A,X),in(B,X). same_color_pair(A,B):-color(A,red),color(B,red),in(A,X),in(B,X). same_color_pair(A,B):-color(A,blue),color(B,blue),in(A,X),in(B,X).
In NeSy- , such kind of background knowledge is not provided, but learned by the system. The concepts are invented as new predicates. We only give six kinds of basic predicates as background knowledge. They are: in/2/O, X: evaluate if the object O exists in the image X. shape/2/O, S: evaluate if the object O has shape S. color/2/O, C: evaluate if the object O has color C. phi/2/O1, O2, : evaluate if the object O2 is located in the direction of O1 as calculated in polar coordinate system. rho/2/O1, O2, : evaluate if the distance between object O2 and O1 is around (For more details, please check Appendix A). A possible solution of pattern three same from NeSy- can be learned as follows target(A,B):-in(O1,X),in(O2,X),inv_pred2(O1,O2). inv_pred1(O1,O2):-color(O1,blue),color(O2,blue),in(O1,X),in(O2,X). inv_pred1(O1,O2):-color(O1,red),color(O2,red),in(O1,X),in(O2,X). inv_pred2(O1,O2):-in(O1,X),in(O2,X),inv_pred1(O1,O2),shape(O1,cir),shape(O2,cir). inv_pred2(O1,O2):-in(O1,X),in(O2,X),inv_pred1(O1,O2),shape(O1,sq),shape(O2,sq). In this case, the predicate target(A, B) corresponds the concept two_same(A, B) and it takes five clauses to explain it, which are learned instead of given. The predicates inv_pred1(A, B) and inv_pred2(A, B) are invented predicates. The other three predicates (shape(A, Y), color(A, Z), in(A, X)) are given beforehand. For more examples, please check Appendix. A.
The result of the evaluation of each pattern is shown in Tab. 1. For each pattern, we give the system only basic predicates and see that our system can successfully invent new predicates for complex visual patterns, resulting in improved accuracy. For most of the patterns, NeSy- successfully finds the target rules by inventing new predicates and using them to describe the target patterns, while ILP can only use existing predicates to describe them and fails at finding the correct target clauses. However, since the variety of each pattern is controlled in a small scale (limited choice of colors, shapes and positions), it is possible to find the target clauses that describe the pattern comprehensively, which also explains the reason for the accuracy of 1.0. The pattern full house has many more varieties (3024 varieties for positive patterns). Therefore Dataset 2D KP 3D KP
Patterns Red Triangle
Two Pairs Full House Check Mark
Same
Two Pairs Shape of Shape
Check Mark # obj 2 4 4 5 3 4 4 5
5 8 8 5 5 5 4 4 3 4 8 3 3 3 2 2 has 64 PN pairs. and denote ILP system (without background knowledge) and NeSy- respectively. The brackets in last column represent the number of invented predicates used in the target clauses. it is impossible to consider every single case, which is very time consuming. Therefore, no predicate was generated to describe it comprehensively. Nevertheless, the PI module improves the accuracy up to 0.9, which proves that the invented predicates improve the accuracy in incomplete description. (A2. Computational Eficiency)
: The runtime of NeSy- depends mainly on the number of iterations needed to find the target clause. In each iteration, a predicate is added to each clause to obtain more complex rules. The higher the number of iterations, the more complex the rule becomes. Tab. 1 shows the time comparison of NeSy- with ILP (without background knowledge). Since the invented predicates entail the previously learned clauses, they are far more informative than the clauses learned by classical NeSy systems like ILP. Therefore, NeSy- is able to converge to the target clause faster, making it more eficient.
Inductive Logic Programming [
We proposed an approach for Neural-Symbolic Predicate Invention (NeSy- ). NeSy- is able to ifnd the new knowledge and summarize it as new predicates, thus it requires less background knowledge for reasoning. We show that our NeSy- model uses only basic neural predicates for finding target clauses, i.e., no further background knowledge is required. Compared to the NeSy-ILP system without PI module, our system provides significantly more accurate classifications. Extending NeSy- to more complex problems, e.g., with more objects in the scene, is an interesting avenue for future work. Developing an eficient prune strategy for ifnding longer clauses is another interesting direction. [13] A. Cropper, S. H. Muggleton, Metagol system, https://github.com/metagol/metagol, 2016.
URL: https://github.com/metagol/metagol. [14] A. Cropper, R. Morel, S. Muggleton, Learning higher-order logic programs, Mach. Learn.
109 (2019) 1289 – 1322. [15] A. Cropper, R. Morel, Learning programs by learning from failures, Mach. Learn. 110 (2021) 801–856. [16] H. Shindo, M. Nishino, A. Yamamoto, Diferentiable inductive logic programming for structured examples, in: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021, pp. 5034–5041. [17] I. Stahl, Predicate invention in ilp — an overview, in: P. B. Brazdil (Ed.), Machine Learning:
ECML-93, Springer Berlin Heidelberg, Berlin, Heidelberg, 1993, pp. 311–322. [18] D. Athakravi, K. Broda, A. Russo, Predicate Invention in Inductive Logic Programming, in: 2012 Imperial College Computing Student Workshop, volume 28 of OpenAccess Series in Informatics (OASIcs), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2012, pp. 15–21. [19] C. Hocquette, S. H. Muggleton, Complete bottom-up predicate invention in metainterpretive learning, in: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, (IJCAI), International Joint Conferences on Artificial Intelligence Organization, 2020, pp. 2312–2318. [20] S. Kok, P. M. Domingos, Statistical predicate invention, in: International Conference on
Machine Learning (ICML), 2007. [21] S. Kramer, Predicate invention : A comprehensive view 1, 2007. [22] A. Cropper, R. Morel, S. H. Muggleton, Learning higher-order programs through predicate invention, Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) (2020) 13655–13658. [23] A. Cropper, R. Morel, Predicate invention by learning from failures, arXiv
Preprint:2104.14426 (2021). [24] T. KAMINSKI, T. EITER, K. INOUE, Exploiting answer set programming with external sources for meta-interpretive learning, Theory and Practice of Logic Programming 18 (2018) 571–588. doi:10.1017/S1471068418000261.
?. ?1 ?/ ??* !"#$% ?0 ?+ ?, !"#$%&!#$'(#)
To represent the spatial relationships between two objects, we have developed two types of spatial neural predicates, i.e., rho(O1, O2, ) and phi(O1, O2, ), which are given as basic knowledge. They are used for new predicates invention in some patterns associated with spatial concepts. ℎ(1, 2, ) The neural predicate rho(O1, O2, ) describes the distance between object 1 and 2, where is the measure. Let denotes the length of image diagonal. Obviously, is the maximum possible distance between 1 and 2. To symbolize the distance between 1 and 2, we divide into parts and denote each part by , 1 ≤ ≤ (as shown in Fig. 5 right). For example, if = 4, then 1 = 0.25, 2 = 0.5, 3 = 0.75, 4 = 1.0 . The actual distance between two objects can be symbolized by 1, 2, 3 or 4. ℎ(1, 2, ) The predicate ℎ(1, 2, ) describes the direction of 2 with respect to 1. Based on the polar coordinate system, we consider the first argument 1 as the original point, then the direction of 2 is in the range [0, 360). We symbolize all directions with 1, ..., , where is a hyper-parameter. The actual direction can be classified to one of these symbols (as shown in Fig. 5).
(e) True (f) True (g) False (e) True (f) True (g) False (h) False (i) True (j) True (k) False (l) False (m) True (n) True (o) False (p) False (three same) kp(X):-in(O1,X),in(O2,X),in(O3,X),inv_pred100(O1,O2,O3),inv_pred451(O1,O2,O3). inv_pred451(O1,O2,O3):-in(O1,X),in(O2,X),in(O3,X),inv_pred2(O1,O2), inv_pred2(O1,O3),inv_pred2(O2,O3). inv_pred100(O1,O2,O3):-in(O1,X),in(O2,X),in(O3,X),shape(O1,cube), shape(O2,cube),shape(O3,cube). inv_pred100(O1,O2,O3):-in(O1,X),in(O2,X),in(O3,X),shape(O1,sphere), shape(O2,sphere),shape(O3,sphere). inv_pred2(O1,O2):-color(O1,blue),color(O2,blue),in(O1,X),in(O2,X). inv_pred2(O1,O2):-color(O1,green),color(O2,green),in(O1,X),in(O2,X). inv_pred2(O1,O2):-color(O1,pink),color(O2,pink),in(O1,X),in(O2,X). (shape in shape) kp(X):-in(O1,X),in(O2,X),in(O3,X),in(O4,X),inv_pred7(O1,O2,O3,O4), phi(O2,O4,phi2),rho(O1,O4,rho1). inv_pred7(O1,O2,O3,O4):-in(O1,X),in(O2,X),in(O3,X),in(O4,X),inv_pred1(O1,O2,O3), phi(O1,O4,phi3). inv_pred7(O1,O2,O3,O4):-in(O1,X),in(O2,X),in(O3,X),in(O4,X),inv_pred1(O1,O2,O3), shape(O1,sphere). inv_pred1(O1,O2,O3):-in(O1,X),in(O2,X),in(O3,X),rho(O2,O3,rho0). inv_pred1(O1,O2,O3):-in(O1,X),in(O2,X),in(O3,X),shape(O1,cube). (check mark) kp(X):-in(O1,X),in(O2,X),in(O3,X),in(O4,X),in(O5,X),inv_pred3(O2,O3,O4,O5), rho(O2,O5,rho0),rho(O3,O4,rho1). inv_pred3(O1,O2,O3,O5):-in(O1,X),in(O2,X),in(O3,X),in(O5,X),phi(O1,O2,phi2), phi(O2,O5,phi1). inv_pred3(O1,O2,O3,O5):-in(O1,X),in(O2,X),in(O3,X),in(O5,X),phi(O2,O5,phi1), phi(O3,O5,phi4).