A Soft Version of Predicate Invention Based on Structured Sparsity

1 Introduction

In relational learning, predicate invention (PI) is a method in which new predicates are introduced into a logical theory. Most PI techniques simplify a logical theory by allowing a group of closely-related rules to be combined somehow, using the invented predicate.

Although not often, but practically PI may be viewed from a sparse structure learning perspective: early PI algorithms from the inductive logic programming community often leverage similar patterns from first-order logic representations, and then invent new predicates to compress the firstorder formulas to form compact theories. For example, in learning logical rules for the domain of family relations, one might have learned the following clauses:

daughter(X,Z), father(Z,Y) ⇒ sister(X,Y)

daughter(X,Z), mother(Z,Y) ⇒ sister(X,Y)

A PI system like CHAMP [Kijsirikul et al., 1992] would create a new predicate by combining these similar rules: e.g., it might invent a predicate "parent", along with an appropriate definition (as the disjunction of father and mother), and then compress the above clauses into 1 :

daughter(X,Z), parent(Z,Y) ⇒ sister(X,Y)

1 We use the predicate symbol "parent" for clarity-a real invented predicate would have a meaningless name, like invented16.

The difficulty with applying such PI invention methods is that they are somewhat prone to errors when data is noisy. Past approaches to PI have avoided these problems by some combination of clean data and computationallyintensive search 2 over structure space [Kemp et al., 2006; Kok and Domingos, 2007].

Intuitively, PI is motivated by the principle that parsimonious explanations of the data are likely generalize well. A similar bias towards parsimonious theories is made by methods such as Lasso [Tibshirani, 1996], which "sparsify" a model by pushing the weights for some features to zero. Sparsity-encouraging regularization methods are a common tool in analyzing complex, high-dimensional datasets, and have been useful in domains including text classification Forman [2003] and vision [Olshausen and Field, 1997; Wright et al., 2010]. Sparsity-encouraging regularization methods are often viewed as "softer" substitutes for feature selection.

It is natural to conjecture that sparse regularization might make PI more robust, by effectively removing "noisy" invented predicates. Notice, however, that an invented predicate P couples the performance of all rules that use P: in the example above, for instance, the performance of the parent rules are coupled to the performance of the sister rule that calls it. This suggests that structured sparsity methods such as the group Lasso [Friedman et al., 2010; Yuan and Lin, 2006] might be more useful for PI.

Further reflection suggests another connection between structured sparsity and PI. Consider the set of rules that would be simplified by an invented predicate. PI compresses a theory by replacing this set with a smaller one, thus reducing the number of parameters to learn. A structured sparsity regularizer that regularizes together the parameters for this set also reduces the number of parameters to learn, in a very analogous way. We call this soft version of predicate invention soft PI. Soft PI does not explicitly creating new symbols to compress the existing theory: instead, soft PI relies on modifying the learner, via a regularizer, to exploit the same commonalities.

In this paper, we explore the connections between PI and sparsity-encouraging regularizers. More specifically, we use the iterated structural gradient (ISG) approach [Wang et al.,

2 We note that structure search is especially expensive in probabilistic logics, where inference is generally non-trivial.

2014a] to identify potentially useful rules. We then apply CHAMP-like heuristics to identify groups of clauses that could be compressed with invented predicates. We compare "hard PI" methods, in which the invented predicates are actually introduced, with "soft PI", in which we impose a group Lasso penalty regularization term to learn parameters for a final set of clauses, with structured sparsity. We compare these approaches with non-structured sparse and non-sparse regularizers, as well as an alternative structured sparsity regularizer, namely a sparse graph Laplacian regularization exploits pair-wise relationships between rules.

Our approach is built on top of ProPPR [Wang et al., 2013], a new, scalable first-order probabilistic logic, which is fast enough to support probabilistic inference on large problems [Wang et al., 2014b]. The methods we explore here are highly scalable: when using a parallel stochastic gradient descent learner with lazy proximal structured sparsity updates, learning takes only a few minutes to process 20,000 examples against a 10,000-tuple database. We also scale the group Lasso approach to a version of the NELL [Carlson et al., 2010] KB with 100K facts, while achieving good performances on the "long tail" of inferences in the KB.

To summarize, our contributions are as follows. (1) We present a new freely available family relation dataset with more than 30,000 of facts for SRL research. This is analogous to a much smaller dataset introduced by Hinton [Hinton, 1986]. (2) We introduce an overlapping proximal group Lasso algorithm to regularize together related clauses. (3) We show that this soft version of PI can outperform strong PI-free baselines in the NELL KB completion task, and the familyrelation learning task.

2 Background on ProPPR

Below we will give an informal description of ProPPR, based on a small example. More formal descriptions can be found elsewhere [Wang et al., 2013].

ProPPR (for Programming with Personalized PageRank) is a stochastic extension of the logic programming language Prolog. A simple program in ProPPR is shown in Table 1. Roughly speaking, the upper-case tokens are variables, and the ":-" symbol means that the left-hand side (the head of a rule) is implied by the conjunction of conditions on the righthand size (the body). In addition to the rules shown, a ProPPR program would include a database of facts: in this example, facts would take the form handLabeled(page,label), hasWord(page,word), or linkedBy(page1,page2), representing labeled training data, a document-term matrix, and hyperlinks, respectively. The condition "true" in the last rule is "syntactic sugar" for an empty body.

In ProPPR, a user issues a query, such as "about(a,X)?", and the answer is a set of possible bindings for the free variables in the query (here there is just one such varable, "X"). To answer the query, ProPPR builds a proof graph. Each node in the graph is a list of conditions R1, . . . ,Rk that remain to prove, interpreted as a conjunction. To find the children of a node R1, . . . , Rk, you look for either

1. database facts that match R1, in which case the appropriate variables are bound, and R1 is removed from the list, or;
2. a rule A←B1, . . . ,Bm with a head A that matches R1, in which case again the appropriate variables are bound, and R1 is replaced with the body of the rule, resulting in the new list B1, . . . , Bm, R2, . . . , Rk.

In Prolog, this proof graph is constructed on-the-fly in a depth-first, left-to-right way, returning the first solution found, and backtracking, if requested, to find additional solutions. In ProPPR, however, we will define a stochastic process on the graph, which will generate a score for each node, and hence a score for each answer to the query. The stochastic process used in ProPPR is personalized PageRank [Page et al., 1998; Csalogny et al., 2005], also known as randomwalk-with-restart. Intuitively, this process upweights solution nodes that are reachable by many short proofs (i.e., short paths from the query node.) Formally, personalized PageRank is the fixed point of the iteration

where p[u] is the weight assigned to u, v0 is the seed (i.e., query) node, χv0 is a vector with χv0 [v0] = 1 and χv0 [u] = 0 for u ̸= v, and the parameter α is the reset probability. W is a matrix of transition probabilities, i.e., W[v, u] is the probability of transitioning from node u to a child node v:

Here Z is an appropriate normalizing constant, θ is the weight vector associated with the features φ[v,u] on edge [v, u]. The edge strength functions f used in this study are rectified linear united (ReLU) [Nair and Hinton, 2010] and the hyperbolic tangent function (tanh) [Glorot and Bengio, 2010].

Like Prolog, ProPPR's proof graph is also constructed on-the-fly, but rather than using depth-first search, we use PageRank-Nibble, a fast approximate technique for incrementally exploring a large graph from a an initial "seed" node [Andersen et al., 2008]. PageRank-Nibble takes a parameter ϵ and will return an approximation ˆp to the personalized PageRank vector p, such that each node's estimated probability is within ϵ of correct. ProPPR can be viewed as a scalable extension of stochastic logic programs[Muggleton, 1996; Cussens, 2001; Van Daele et al., 2014].

We close this background section with some final brief comments about ProPPR.

Scalability. ProPPR is currently limited in that it uses memory to store the fact databases, and the proof graphs constructed from them. ProPPR uses a special-purpose scheme based on sparse matrix representations to store facts which are triples, which allows it to accommodate databases with hundreds of millions of facts in tens of gigabytes.

With respect to run-time, ProPPR'S scalability is improved by the fast approximate inference scheme used, which is typically an order of magnitude faster than power iteration for moderate-sized problems [Wang et al., 2013], and much faster on larger problems. Experimentation and learning are also sped up because with PageRank-Nibble, each query is answered using a "small"-size O( 1 αϵ )-proof graph. Many operations required in learning and experimentation can thus be easily parallelized on a multi-core machine, by simply distributing different proof graphs to different threads.

Parameter learning. The personalized PageRank scores are defined by a transition probability matrix W. ProPPR allows "feature generators" to be attached to its rules, as indicated by the code after the hashtags in the example program: for instance, when matching the rule "sim(X,Y) :- links(X,Y)" to a condition such as "sim(a,X)" the two features "sim" and "link" are generated, and when matching the rule "linkedBy(X,Y,W) :- true" to the condition "linkedBy(a,c,sprinter)" the feature "by(sprinter)" is generated. Since edges in the proof graph correspond to rule matches, the edges can also be labeled by features, and a weighted combination of these features can be used to define a total weight for each edge, which finally can be normalized used to define the transition matrix W. Learning can be used to tune these weights to data; ProPPR's learning uses a parallelized SGD method, in which inference on different examples is performed in different threads, and weight updates are synchronized.

Structure learning. Prior work [Wang et al., 2014a] has studied the problem of learning a ProPPR theory, rather than simply tuning parameters in an existing theory, a process called structure learning. In particular, inspired by recent advances in inductive logic programming [Muggleton et al., 2014], Wang et al. [2014a] propose a scheme called the structural gradient which scores every rule in some (possibly large) user-defined space R of potential rules, and then adds high-scoring rules to a theory. In more detail, the space of potential rules R is defined by a "second-order abductive theory", which conceptually constructs proofs using all rules in R. The second-order theory is defined in such a way such that each parameter in the second-order theory corresponds to a rule in R, so the gradient of the parameter vector corresponds to a scoring scheme for the rules in R. The structure learning via parameter learning idea of ProPPR's structure learning method is broadly related to joint structure and parameter learning of Markov Logic Networks [Khot et al., 2011]. The iterated structural gradient method that incrementally refines the hypothesized structure space is also closely related to a learn-and-join algorithm for learning Markov Logic Networks [Khosravi et al., 2010].

3 Hard Predicate Invention

In previous work [Wang et al., 2014a] involving the structural gradient method, the space of rules R includes rules over a fixed set if predicate symbols that are known in advance. In some cases it is useful to invent new predicates and define them. For instance, in learning a definition of aunt using the pre-defined predicates mother, father, a systemmight include the rules:

aunt(X,Y) :- sister(X,Z),mother(Z,Y). aunt(X,Y) :- sister(X,Z),father(Z,Y).

A potentially more compact definition for aunt might be found by inventing the new predicate invented1 and defining it as the disjunction of mother and father. Constructing and defining new predicate symbols in this way is called predicate invention (PI).

Existing PI approaches involve creating new predicates based on similarities [Wogulis and Langley, 1989] and differences [Muggleton and Buntine, 1992] between learned rules. However, many PI systems are not robust enough to handle noisy data, as when incorrect predicates are invented, errors may eaily cascade. In this paper we evaluated several variations of a CHAMP-style analysis [Kijsirikul et al., 1992] to invent predicates based on sets of similar rules. We consider pairs of rules to be similar if they have the following format.

• R1 is "p(X,Y) :- q(X,Z),r(Z,Y)" and R2 is "p(X,Y) :- q(X,Z),s(Z,Y)", i.e., they are length-two chains that differ only in the last predicate of the RHS, or
• R1 is "p(X,Y) :- q(X,Y)" and R2 is "p(X,Y) :- s(X,Y)", i.e., they are length-one chains that differ only in the last predicate of the RHS, or
• R1 is "p(X,Y) :- q(Y,X)" and R2 is "p(X,Y) :- s(Y,X)", which is the inverse relation case.

In our preliminary experiments on learning family relations (detailed settings and quantitative results will be shown in Section 5.), the results that "hard PI" were produced as follows:

nephew(X,Y) :- invented1(Y,X). invented1(X,Y) :- uncle(X,Y). invented1(X,Y) :- aunt(X,Y). uncle,X,Y) :- invented2(Y,X). invented2(X,Y) :- nephew(X,Y). invented2(X,Y) :- niece(X,Y). aunt(X,Y) :- sister(X,Z),invented1(Z,Y). sister(X,Y) :- niece(X,Z),invented1(Z,Y). . . . brother(X,Y) :- invented1(X,Y).

uncle(X,Y) :- uncle(X,Z),invented1(Z,Y).

Although the majority of the compressed rules produced by hard PI are intuitively meaningful, the last two rules are not.

4 Structured Sparsity for Soft Predicate Invention

From the example in the previous section, we see that a drawback of hard predicate invention is that, given noisy inputs, incorrect clauses may be generated. In this section, we present a structured sparsity based alternative to hard PI: instead of creating new symbols, our approach groups similar concepts together, and exploit regularization-based structured sparsity technique to explore closely-related concepts and rules.

Element-Wise Regularization In this subsection, we briefly review past work on regularization techniques. Here we define the weight parameter vector w, and each weight element in w corresponds to a first-order logic clause candidate, according to prior work on structure learning using parameter learning for first-order logic [Wang et al., 2014a]. Note that ProPPR's default regularization term µ||w||22 , which is the Ridge estimator [Le Cessie and Van Houwelingen, 1992], will not be producing sparse estimates. The noisy estimates may not be ideal, since the incorrect first-order logic program may lead to more errors in the downstream applications. To solve this issue, we consider the following Lasso [Tibshirani, 1996] formulation, where objective function is:

Unlike the Ridge estimator, the above Lasso penalty will now produce sparse estimates, even though the objective function is now non-differentiable. To optimize the above function, we use a proximal operator: each weight component w is shrunk towards 0 by a shrinkage value σ,

where in our lazy L1 regularization update is

here, δ is the total number of accumulated regularization update, and β is the learning rate. We use a Lazy L1 update algorithm [Carpenter, 2008] for optimization. The main idea is that, the regularization updates for all features in each example are slow and unnecessary, and we can cache the regularization updates of relevant features, then update the accumulated regularization changes.

Structured Graph Laplacian Regularization One challenge associated with PI is that the reuse of invented predicates makes them hard to remove by simple element-wise regularizers. To better incorporate the dependencies among the features in each logic clause, we introduce a pair-wise graph Laplacian penalty [Belkin et al., 2006]:

Here, ζ is the regularization coefficient that controls the strength of the structured penalty, and A(p,q) is an adjacency matrix that indicates the pair-wise similarity among logic clauses, and the basic idea is to push similar logic clauses to have similar weights after learning. For example, consider the following clauses:

Since they share the same goal and the same first predicate on the right hand side (RHS), it make sense for them to have similar weights. To construct the sparse A matrix , we use a CHAMP-style analysis [Kijsirikul et al., 1992]: for all pairs of clauses that share the same goal and have |RHS| = 1 cases, we connect them in the adjacency graph. For all pairs of clauses that share the same goal and have |RHS| = 2 cases, if the first predicates on the RHS are the same, we connect the two clauses together in A. For instance, instead of inventing a hard predicate for "nephew or niece", we instead assign a weight value of 1 for this pair of rules in the affinity matrix A.

To implement this approach, we then define a degree matrix D to be the total number of connections for each entry in A, and the graph Laplacian to be L = D - A, which transforms the optimization into:

where ℓ is the loss. Like ridge regression, this regularizer is a quadratic penalty.

Sparse Laplacian Regularization To incorporate sparsity, we may also consider this alternative sparse Laplacian regularization formula:

where the sparsity-inducing L1 term was added.

Structured Sparsity via Group Lasso A problem with Laplacian regularization is that while it pushes similar pairs of clauses to have similar weights, it will not typically remove groups in incorrect related clauses by pushing their weights to zero. To solve this problem, we introduce a sparse group Lasso [Friedman et al., 2010; Yuan and Lin, 2006] formulation:

where L is the total number of feature groups, and wl is the parameter vector for the l-th group. This is now a structured sparsity learning problem, where we can introduce group sparsity. To generate the groups, we utilize the same A matrix in the Laplacian regularization: each row in A corresponds to a feature group, and different groups may have overlapping features. The benefit of using sparse group Lasso is that it will drive the weights for the entire group of features to zero if the group is not useful or noisy, which appears to be critical for soft PI. Again, we take the first-order derivatives of the group Lasso term, and use the same proximal operator algorithm to solve the sparse group Lasso optimization. We also consider a "group lasso" alternative of the above formulation when we remove the element-wise L1 term. Note that Nishino et al. [2014] is among the first to study a projected gradient approach for learning sparse parameters in relational parameter learning, but the problems of learning sparse structures and predicate invention are not discussed.

5 Experiments

In this section, we evaluate the effectiveness of the proposed approach on two datasets: a new, large family relation dataset 3 , which features the Kings and Queens of Europe, including Great Britain's royal family up to 1992; as well as the NELL subsets that include up to 100K grounded facts extracted from the Web. In particular, we focus on the task of structure learning for knowledge base completion [Wang et al., 2014a; Cropper and Muggleton, 2014], where the goal is to learn first-order logic program to reconstruct the KB, given only partially complete background database. For comprehensive empirical comparisons of ProPPR's structure learning scheme to the Markov Logic Networks' structure learning baseline, we refer the readers to prior work [Wang et al., 2014a].

3 This is motivated by Hinton's classic kinship dataset, which includes only two families, each with twelve individuals, and twelve binary relations between these individuals.

5.1 Learning Family Relations

We introduce a new dataset for research in SRL: the original dataset was created in 1992 by Denis R. Reid, including 3010 individuals and 1422 families of European royalty. We further parsed the genealogical data to extract six pairs of inter-related family relations: {uncle & aunt, sister & brother, daughter & son, father & mother, husband & wife, niece & nephew}. (Learning such pairs of relations has proven to be quite difficult for ProPPR structure-learning systems in past work [Wang et al., 2014a].) We use a temporal split to separate the train and test subsets. The training set includes 21,430 facts, while the test set contains 8,899 facts. In our KB completion experiment, we randomly delete 50% of the background facts for both the training and test sets respectively, and we use soft PI to complete the missing facts, and evaluate the effectiveness of our approach using Mean Average Precision (MAP), and Area Under the precision-recall Curve (AUC-PR). Throughout the experiments, the regularization coefficient µ for the L2 penalty was set to 0.00001, and µ for the L1 penalty was set to 0.00002. We repeat each experiment 3 times and report the averaged score and the standard deviation of the results. We also report the number of nonzero rules after learning, as well as the inference time on the test set. The McNemar test [McNemar, 1947] is used to test the statistical significance of various models.

Table 2 shows the MAP results for KB completion on the royal family dataset, using the non-iterated and iterated structural gradient variants [Wang et al., 2014a] respectively. We see that hard PI performs poorly, due to the error cascades. 4 Traditional element-wise non-sparse and sparse methods, namely, the Ridge and Lasso estimators, did help improving the test performance. The pair-wise graph Laplacian regularization also improves the performance. This is probably because by forcing similar logic clauses to learn similar weights, we are implicitly learning similarities among various clauses, and use them to find informative clauses that lead to better predictive results. We observe that for soft PI, the proposed sparse overlapping group Lasso method do have strong gain on this task: it outperforms all the competitive baselines by a large margin. In general, we also see the advantage of soft PI for inference with probabilistic logic programs- they tend to lead to better predictive performances than hard PI or no PI solutions. Our results also align with the findings in a prior study on empirical loss minimization with sparsityinducing regularization terms [Duchi and Singer, 2009]: both papers suggest that the compact parameter space with fewer non-zero weights may lead to better predictive results.

4 Hard PI here is the best of several PI techniques we experimented with. Details are omitted due to space.

5.2 Completing the NELLKB

Finally, as a larger-scale and more realistic task, we explore learning inference rules for the NELL knowledge base. The NELL (Never Ending Language Learning) research project is an effort to develop a never-ending learning system that operates 24 hours per day, for years, to continuously improve its ability to read (extract structured facts from) the web [Carlson et al., 2010]. NELL is given as input an ontology that defines hundreds of categories (e.g., person, beverage, athlete, sport) and two-place typed relations among these categories (e.g., athletePlaysSport(Athlete, Sport)), which it must learn to extract from the web. NELL is also provided a set of 10 to 20 positive seed examples of each such category and relation, along with a downloaded collection of 500 million web pages from the ClueWeb2009 corpus (Callan and Hoy, 2009) as unlabeled data, and access to 100,000 queries each day to Google's search engine. NELL uses a multi-strategy semisupervised multi-view learning method to iteratively grow the set of extracted "beliefs".

For experimental purposes, we construct a number of varying-sized versions of the KB using the following procedure. First, we construct a "knowledge graph", where the nodes are entities and the edges are the binary predicates from NELL. Then, we pick a seed entity s, and find the M entities that are ranked highest using a simple untyped random walk with restart over the full knowledge graph from seed s. Finally, we project the KB to just these M entities: i.e., we select all entities in this set, and all unary and binary relationships from the original KB that concern only these M entities. Here the seed entities are "Google" and "Baseball". We use the same datasets fromWang et al.[2014a], and compare with their ridge method. The summary of the dataset is shown in Table 3.

Inference on NELL's learned KB is challenging for two reasons. First, the learned KB is not only incomplete, but also noisy, since it is extracted imperfectly from the web. For example, a football team might be wrongly recognized as two separate entities, one with connections to its team members, and the other with a connection to its home stadium. Second, the inference problems are large.

The performance of soft PI via sparse group Lasso on these tasks is shown in Figure 1. Here we sort the list of answers by their PPR scores in the descending order, and the rank corresponds to the position in the list. Even though the data is noisy, we see that the overlapping sparse group Lasso learns large and useful theories-theories such that the highconfidence predictions do indeed correspond, in most cases, with facts actually in the NELL knowledge base. Comparing to the Ridge estimator, our proposed method is better at modeling the long-tail distribution of facts on all of the "Google" and "Baseball" subsets in the NELL KB. For conciseness, we do not show other baselines in the figures, but the elementwise and structured regularization models' results are consistent with the family dataset.

6 Conclusions

In this work, we investigate an alternative approach to hard predicate invention. Instead of explicitly inventing new predicates, our approach relies on structured regularization techniques to learning similar clauses that lead to the discovery of informative clauses and better predictive performances. In particular, we focus on a new, scalable logic called ProPPR. More specifically, we use an iterated structural gradient approach and CHAMP-style compression to induce the overlapping groups, and solve a group Lasso problem. To reduce the overhead in regularization, we propose a Lazy proximal update algorithm.

We also introduce a new royal family dataset 5 for research in statistical relational learning: it contains more than 30K of facts about royal families in Europe. On this dataset, we show that our proposed soft PI model improves over various hard PI and no PI baselines by a large margin. In addition to this, we demonstrate the scalability of our approach by performing sparse group Lasso experiments on the NELL dataset. By comparing to the non-sparse L2 regularization method, it is shown that our proposed sparse group Lasso method has better performances on modeling the long tail distribution of the NELL KB.

Acknowledgment

This work was sponsored in part by DARPA grant FA87501220342 to CMU and a Google Research Award.

5 http://www.cs.cmu.edu/˜yww/data/family data.zip