Generative Structure Learning for Markov Logic Networks Based on Graph of Predicates

1 Introduction

Statistical Relational Learning (SRL) seeks to combine the power of both statistical learning and relational learning in order to deal with both uncertainty and complex relational structures, which are required by many real-world applications. A large and growing number of SRL approaches have been proposed, including PRISM [Sato and Kameya, 1997], Probabilistic Relational Models (PRM) [Friedman et al., 1999], Bayesian Logic Programs (BLP) [Kersting and De Raedt, 2007], Relational Dependency Networks (RDN) [Neville and Jensen, 2004], Relational Markov Models (RMM) [Anderson et al., 2002] and Markov Logic Networks (MLN) [Richardson and Domingos, 2006].

MLNs generalize both full First-Order Logic (FOL) and Markov networks (MN). A MLN consists of a set of weighted clauses, viewed as templates for the features of a MN. Learning a MLN can be decomposed into structure learning and weight learning. Structure learning leads to a set of first-order formulas while weights learning estimates the weight associated with each formula of a given structure. Early developed strategies focused on parameter learning, the underlying structure being provided. Such an approach is likely to lead to non optimal results when these clauses do not capture the essential dependencies in the domain. As a consequence, recent work on MLNs has focused on global learning methods that integrate the structure learning step. This integration however remain challenging, due to the very large search space. Consequently, only a few practical approaches have been proposed to date, among which the MSL [Kok and Domingos, 2005], BUSL [Mihalkova and Mooney, 2007], ILS [Biba et al., 2008b], LHL [Kok and Domingos, 2009], LSM [Kok and Domingos, 2010] and HGSM [Dinh et al., 2010b].

MLNs can be learned in generative (i.e. learning all predicates in the domain) and discriminative (i.e. learning a single target predicate) frameworks. In this paper we focus on generative learning, our contribution consisting in a new algorithm for the generative learning of the structure of a MLN. This algorithm first constructs a graph of predicates that synthesizes the paths existing in the training database. In other words, this graph highlights the binary associations of predicates that share constants. Building candidate clauses is thus made faster, as the algorithm focuses on paths that exist in the graph. Each path is transformed into a clause by means of a heuristic variabilization technique. The algorithm creates relevant clauses w.r.t. the graph, according to a progressive length (starting with clauses of length 2). Each clause is then evaluated for insertion in the final MLN.

The remainder of the paper is organized as follows. We first remind some background elements in Section 2. Then we describe our algorithm in Section 3. Experiments are presented in Section 4. Related work is briefly drawn in Section 5. Last, Section 6 concludes this paper.

2 Backgrounds

Let us recall here some basic notions of FOL, which will be used throughout this paper. We consider a function-free first order language composed of a set P of predicate symbols, a set C of constants and a set of variables. An atom is an expression p(t1, . . . , tk), where p is a predicate and ti are either variables or constants. A literal is either a positive or a negative atom; a ground literal (resp. variable literal) contains no variable (resp. only variables). A clause is a disjunction of literals. The length of a clause c, denoted by len(c), is the number of literals in c. Two ground literals (resp. variable literals) are said to be connected if they share at least one ground argument (one variable). A clause (resp. a ground clause) is connected when there is an ordering of its literals L1 ∨ . . . ∨ Lp, such that for each Lj , j = 2 . . . p, there exists a variable (a constant) occurring both in Lj and in Li, with i < j. A world is an assignment of truth value to all possible ground atoms. A database is a partial specification of a world; each atom in it is true, false or (implicitly) unknown. In this paper, we use the closed world assumption: if a ground atom is not in the database, it is assumed to be false.

A MLN is a set of weighted first-order formulas. Together with a set of constants, it defines a MN [Pearl, 1988] with one node per ground atom and one feature per ground formula. The weight of a feature is the weight of the corresponding first-order formula. The probability distribution over a possible world x specified by the ground MN is: P(X = x) = 1Z exp ∑i∈F ∑j∈Gi wigj(x) where Z is a normalization constant, F is the set of formulas, Gi and wi are respectively the set of groundings and weight of the i-th formula, and gj(x) = 1 if the j-th ground formula is true.

The Pseudo-Log-Likelihood (PLL) of x is logPw(X = x) = ∑nl=1 log Pw(Xl = xl|MBx(Xl)) where MBx(Xl) is the state of the Markov blanket of the ground atomXl, xl is the truth value of Xl in x. Generative approaches optimize the PLL using iterative scaling or a quasi-Newton optimization method such as the L-BFGS [Sha and Pereira, 2003].

The weighted PLL (WPLL) measure is log P ∗w (X = x) = ∑r∈R cr ∑gr k=1 logPw(Xr,k = xr,k|MBx(Xr,k)) where R is the set of predicates, gr is the number of groundings of predicate r, xr,k is the truth value of the k-th grounding of r, and cr = 1/gr [Kok and Domingos, 2005].

3 Generative Structure Learning Based on Graph of Predicates

In this section, we first introduce our definition of graph of predicates (GoP) and then describe how we use this graph to learn the structure of a MLN from a training dataset DB and an initial MLN (which can be empty).

3.1 Graph of Predicates

Let us consider here a set P of m predicates {p1, ..., pm}.

Definition 1 A template atom of a predicate p is an expression p(type1, ... , typen), where typei, 1 ≤ i ≤ n indicates the type of the i-th argument.

Definition 2 A link between two template atoms pi(ai1 , ..., aiq ) and pj(aj1 , ..., ajk ) is an ordered list of pairs of positions u and v such that the types of arguments at position u in pi and v in pj are identical. It is denoted by link(pi(ai1 , ..., aiq ), pj(aj1 , ..., ajk )) = 〈u v|...〉, where aiu = ajv , 1 ≤ u ≤ q, 1 ≤ v ≤ k.

The link between two predicates pi and pj, denoted by link(pi, pj), is the set of all possible links between their template atoms pi(ai1 , ..., aiq ) and pj (aj1 , ..., ajk ).

When two template atoms do not share any type, there exists no link between them.

Definition 3 A formula satisfying a link(pi(ai1 , ..., aiq ), pj(aj1 , ..., ajk )) = 〈si1 sj1| ...|sic sjc|〉 is a disjunction of literals pi(Vi1 , ..., Viq ) ∨ pj(Vj1 , ..., Vjk )) where Vt, t = i1, ..., iq, j1, ..., jk, are distinct variables except Visid = Vjsjd , 1 ≤ d ≤ c.

The definitions of link and formula satisfying a link are naturally extended to negation. For example, link(pi(ai1 , ..., aiq ), !pj(aj1 , . . . , ajk )) is the link between pi(ai1 , ..., aiq ) and pj(aj1 , ..., ajk ): link(pi, !pj) ≡ link(pi, pj ).

Example 4 We consider a domain consisting of two predicates AdvisedBy and Professor respectively with two template atoms AdvisedBy(person, person) and Professor(person). The argument (type) person appears at position 0 of Professor(person) and at positions 0 and 1 of AdvisedBy(person, person). Several possible links exist between them, as for instance 〈0 0〉 and 〈0 1〉, and a possible formula satisfying the latter one is Professor(A) ∨ AdvisedBy(B, A).

We also have link(AdvisedBy, AdvisedBy)= {〈0 0〉, 〈0 1〉, 〈1 0〉, 〈1 1〉, 〈0 0 | 1 0〉, 〈0 0 | 1 1〉, 〈0 1 | 1 0〉, 〈0 1 | 1 1〉}.

It must be noted that several links are not considered here. For example, the link 〈0 0 | 1 1〉 leads to a formula composed of two similar literals. The link 〈1 0 | 0 1〉 is similar to the link 〈0 1 | 1 0〉 because they are satisfied by similar formulas. The link 〈1 1 | 0 0〉 is also similar to the link 〈0 0 | 1 1〉. The same remark can be done for link(Professor, Professor) = 〈0 0〉, link(Professor, !Professor) = 〈0 0〉, ...

Definition 5 Let DB a database, P a set of m predicates {p1, ..., pm} occurring in DB, and D the domain (set of constants). An undirected graph of predicates (GoP) is a pair G=(V, E) composed of a set V of nodes (or vertices) together with a set E of edges, where:

1. A node vi ∈ V corresponds to a predicate pi or its negation, |V | = 2 × |P|
2. If there exists a link between two template atoms of predicates pi (or !pi) and pj (or !pj), then there exists an edge between the corresponding nodes vi and vj, and this edge is labelled by the link.

Figure 1 illustrates a GoP for the domain in Example 4.

3.2 Structure of Algorithm

Given as inputs a training dataset DB, a background MLN (possibly empty) and a positive integer maxLength, specifying the maximum length of clauses, we present an algorithm, called Generative Structure Learning based on a graph of Predicates (GSLP), to learn generatively a MLN structure. Algorithm 1 sketches main steps of GSLP.

The approaches developed in [Kok and Domingos, 2005], [Biba et al., 2008b] and [Huynh and Mooney, 2008] explore in an intensive way the space of clauses, generating a lot of useless candidate clauses, while the ones developed in [Mihalkova and Mooney, 2007], [Kok and Domingos, 2009] and [Dinh et al., 2010b]) search all paths of ground atoms in the database in order to reduce computation time. However, searching in this space is also computationally expensive. We aim at generating a set of interesting potential clauses based on three observations. First, associations amongst predicates constitute a smaller model space than clauses and can thus

Algorithm 1: GSLP(DB, MLN, maxLength)

• 1 Initialization: set of clauses CC = ∅, set of paths SP = ∅;
• 2 Add all unit clauses to the final MLN;
• // Creating a graph of predicates
• 3 Create graph G of predicates;
• 4 Reduce Edges of Graph (G, CC, SP) ; // Building a set of candidate clauses
• 5 for length=2 to maxLength do
• 6 CC ←CreateCandidateClauses(DB, G, SP, length);
• // Learning the final MLN
• 7 Eliminate several Candidate Clauses (CC) ;
• 8 Add Candidate Clauses into the MLN (CC, MLN) ;
• 9 Prune Clauses out of the MLN ;
• 10 Return(MLN);

be searched more efficiently [Kersting and De Raedt, 2007]. Second, it seems useless to consider connected clauses that do not correspond to any instance in the database. Third, we believe that the more useful a connected clause A1 ∨ ... ∨An is, the larger number of true ground atoms in the database it covers. In other words, relevant clauses are mostly the ones that are frequent enough in terms of true instances. It is obvious that if a connected formula is frequent, then its connected sub-formulas are also at least as frequent as it (similar remarks serve as the basis of many well known strategies for frequent pattern mining). We thus propose to generate candidate clauses, starting from binary ones (i.e. consisting of two connected atoms) then gradually extend them to get longer and better ones. The problem now is transformed into finding such a set of binary connected clauses Ai ∨ Aj from which the set of candidate clauses is gradually lengthened.

Before describing the algorithm in details, it is important to explain how a clause is evaluated. Traditional ILP methods use the number of true instances which is not suitable for uncertainty in MLN, while most methods for MLN use the WPLL, which sometimes miss clauses with good weights. We propose to evaluate a clause c based on its weight (c.weight) and gain (c.gain). These two values are computed according to a temporary MLN composed of the unit MLN plus c. The weights of this MLN are then learned to maximize the measure (i.e. WPLL). The weight of c is its weight in this temporary MLN. The gain of c is defined as: newMea - unitMea - penalty ∗ len(c), where newMea, unitMea are respectively the performance measure (WPLL) of the temporary MLN and of the unit MLN; penalty is a coefficient. It essentially corresponds to the improvement of the measure when adding c to the unit MLN. To estimate the interest of c, instead of using the number of true ground instances or only the WPLL, we use the product c.mf = |c.weight| ∗ c.gain. As a clause weight can be negative, we use absolute value (denoted by | |) to consider both positively and negatively weighted clauses. This is reasonable because in a MLN, c.weight implies how strong c is and c.gain describes how the measure is increased when adding c into the unit MLN. Nevertheless, this measure is no longer monotonous, contrary to the classical frequency measure.

In a MLN, a weight associated to a formula reflects how strong a constraint is: the higher the weight, the greater the difference in log probability between a world that satisfies the formula and one that does not, other things being equal. Concerning unit clauses (clauses of a single atom), the weights of these capture the marginal distribution of predicates, allowing longer clauses to focus on modeling predicate dependencies. For this reason, adding all unit clauses into the MLN is usually useful. This is also the first step of our algorithm and we call this first MLN the unit MLN (line 2).

Our clause-generation algorithm relies on a GoP in order to search clauses through the space of associations between predicates. For each predicate, we create two nodes (corresponding to the predicate itself and its negation), hence the graph has only 2 × |P| nodes, where |P| is the number of predicates in the domain. The number of edges incident to a node depends on the number of arguments of the corresponding predicate S and their type relations in the domain, but it is usually not too large. The search space of paths in GoP is then much smaller than the whole search space of paths of ground atoms, especially when considering a domain with a large number of predicates and when there exists a lot of shared-arguments between ground atoms.

Every edge e of GoP is created corresponding to a possible link between two nodes (line 3). We can see that e always corresponds to a binary clause bc satisfying its link (label). We do not consider clauses with no or a few true instances in the database, hence if the number of true instances of bc is less than or equal to a given threshold nti then e is discarded. Otherwise, bc is evaluated to compute its measure of frequency, bc.mf. In our method, only edges with a big "enough" measure of frequency will be considered, therefore if bc.mf is smaller than or equal to a given threshold mft, then e is also eliminated. The number of edges of GoP is thus remarkably reduced (line 4), leading to a more efficient search.

Next, the algorithm generates a set of candidate clauses based on this reduced graph (line 5-6). The idea is to lengthen successively every binary clause to generate longer ones such that the extended clauses improves the measure c.mf of frequency. A clause is considered as a candidate clause when it reaches a given maxLength, or when it does not lead to any longer and better clause (i.e. associated with an improved WPLL). We explain this in more details in Subsection 3.3.

Having got a set CC of candidate clauses, the algorithm next eliminates some clauses (line 7) before adding them into the MLN in turn (line 8). Finally, it prunes some clauses of the MLN (line 9). We present these steps in Subsection 3.4.

3.3 Building Candidate Clauses

As we have mentioned above, the algorithm extends step by step every binary clause. Let SP a set of similar-length paths and CC a set of candidate clauses. Initially, SP, CC respectively contain all 1-length paths and binary clauses: each pair of spi ∈ SP and cci ∈ CC corresponds to an edge ei of the reduced GoP, where spi is the label of ei and cci is the binary clause satisfying spi. For longer paths, we extend every k-length path pk = p1, ..., pk ∈ SP to get a longer (k+1)- length path pk1 = p1, ..., pk, pk+1 by finding an edge pk+1 connecting to at least a node in pk. It must be noted that by indexing the nodes of the graph we can find quickly the set of (k+1)-length paths, since for a node p in pk we only have to look for every edge pk+1 connecting p to its higher indexed nodes. In our algorithm, each path is variabilized to form only one clause (as explained in next paragraph). Assume that ck, ck+1 are respectively two variabilized clauses of pk and pk1. The clause ck+1 is evaluated to check whether ck+1.mf greater than ck.mf. If it is true, the path pk1 is stored into SP for the next iteration, otherwise it is no longer considered. If there exists no clause ck+1 extended from the path of ck such that ck+1.mf > ck.mf, the clause ck becomes a candidate clause stored into CC. At last iteration, all clauses corresponding to maxLength-length paths in SP are added into CC.

Let us consider now the process of variabilization. Most approaches variabilize a path of ground atoms by simply replacing constants by variables. We emphasize that, here, we produce clauses from paths in the reduced GoP, i.e. a list of edges containing only information of predicates and positions of shared arguments. There exists a lot of clauses satisfying this path, thus building all possible clauses is not reasonable: the more clauses generated, the more time spent to evaluate them and to learn the final MLN. We variabilize heuristically a path to generate only one connected clause. First, in order to reduce the number of distinct variables in the clause, we handle the predicates in the order of descending frequency in the path. For each predicate, we perform variabilization for shared variables first, and then for unshared ones. An argument of a predicate is variabilized by a new variable if its position does not appear in the link of any edge in the path.

Example 6 For example, variabilizing the path composed of two links !advisedBy 〈0 1〉 !advisedBy and !advisedBy 〈0 0〉 student generates the clause !advisedBy(A,B) ∨ !advisedBy(C,A) ∨ student(A). Conventionally, the link between student and advisedBy is applied to the first advisedBy.

3.4 Learning the final MLN

Weights are learned using the standard L-BFGS algorithm to maximize PLL. For inference, as in previous studies, we use MC-SAT [Richardson and Domingos, 2006]. However, the PLL parameters may lead to poor results when long chains of inference are required [Richardson and Domingos, 2006]. To overcome this issue, we sort candidate clauses in CC in the decreasing order of measure of frequency and then we eliminate some of them (line 7) using two criteria as follows:

• Sub-clause: remove every clause CC[j] when there exists a clause CC[i], i < j such that CC[i] and CC[j] have a sub-clause relation 1 . For example, in case len(CC[i]) < len(CC[j]) and there exists a sub-clause c of CC[j] and a variable replacement θ such that cθ ≡ CC[i], we have a subclause relation between CC[i] and CC[j].
• Clauses of same predicates: keep only one (with the maximum measure) of clauses composed of the same set of predicates. For example, we choose only one of the 2 clauses (student(A) ∨ advisedBy(A,B), student(A) ∨ advisedBy(B,A)) consisting of the two predicates student and advisedBy.

Clauses in CC are added into the MLN in turn. A candidate clause is put into the MLN as long as it leads to an improvement of the performance measure (i.e. WPLL) of the MLN learned before. As adding clauses into the MLN can influence the weight of formerly added clauses, once all candidate clauses have been considered, we try to prune some of the clauses from the MLN. We use a zero-mean on each weight in order to remove a set of clauses, whose weights are less than a given threshold mw, as long as their elimination causes an increase of the performance measure. This step is iterated until no clause can be removed any more.

1 See online appendix for more details http://www.univorleans.fr/lifo/Members/Dinh.Thang/

4 Experiments

GSLP is implemented over the Alchemy1 package. We perform experiments to estimate the performance of GSLP following two questions:

1. How does GSLP compare to the state of the art generative systems for MLN structure learning?
2. Can we compare GSLP to a state of the art discriminative structure learning system for specific predicates?

4.1 Systems, Datasets andMethodology

To answer question 1, we choose three state-of-the-art generative systems:

• LSM [Kok and Domingos, 2010]: This algorithm uses random walks to identify densely connected objects in data, groups them with their associated relations into a motif, and then constrains the search for clauses to occur within motifs.
• HGSM [Dinh et al., 2010b]: This algorithm heuristically builds a set of variable literals then finds dependent relations amongst them. Candidate clauses are created from sets of dependent variable literals.
• MBN [Khosravi et al., 2010]: This algorithm first learns a (parametrized) Bayes net from which to apply a standard moralization technique in order to produce a MLN.

For question 2, we choose the DMSP [Dinh et al., 2010a], a recent discriminative MLN structure learning system.

We used the three datasets IMDB, UW-CSE, CORA 2 that have been used to evaluate LSM, HGSM as well as DMSP. For each domain, we also performed a 5-fold cross-validation as in previous studies. Unfortunately, this approach is not feasible for the current setting of MBN [Khosravi et al., 2010]. To be able to compare to MBN, we used 2 subsample datasets (ML1, ML2) of the MovieLens database and 2 subsample datasets (MT1, MT2) of the Mutagenesis database 3 . For each of them, we learned the MLN on 2/3 random selected atoms and tested it on the remaining 1/3, as presented in [Khosravi et al., 2010]. Details of these datasets are reported in Table 2.

2 Publicly-available at http://alchemy.cs.washington.edu. IMDB describes a movie domain, UW-CSE describes an academic department, and CORA is a collection of citations of CS papers.

3 MovieLens is available at the UC Irvine machine learning repository and Mutagenesis is widely used in ILP research.

Performance was measured in terms of CLL and AUC (area under precision recall curve). The CLL of a ground atom is its log-probability given the MLN and the database, and directly measures the quality of the estimated probabilities. AUC curves are computed by varying the CLL threshold above which a ground atom is predicted true. AUC is insensitive to a large number of true negatives. For these two measures, reported values are averaged over all predicates. CLL and AUC have been used in most of recent studies of MLN learning and as in them, we used the standard MC-SAT inference algorithm to compute a probability for every grounding of the query predicate on the test fold. We used the package provided in [Davis and Goadrich, 2006] to compute AUC.

Parameters for LSM, HGSM and DMSP were respectively set as in the papers of Kok and Domingos [2010] and Dinh et al. [2010b; 2010a]. We learned clauses composed of at most 5 literals (maxLength = 5) for all systems and limit the number of similar predicates per clause to 3 in order to learn weights in a reasonable time. We set nti = 0, mft = 0, mw = 0.001, penalty = 0.001 for all domains. These parameters are chosen just to estimate the performance of GSLP; we did not optimize them for any dataset yet. We ran these experiments on a Dual-core AMD 2.4 GHz CPU - 4GB RAM machine.

4.2 Results

Table 3 reports the average CLLs, AUCs and runtimes on each dataset. Higher numbers indicate better performance and NA indicates that the system was not able to return a MLN, because of either crashing or timing out after 3 days running. For MBN, we used the values published in [Khosravi et al., 2010]. It must be noted that, our results do slightly differ from the ones in [Kok and Domingos, 2010], as i) we used the standard versions of IMDB and UW-CSE instead of the ones reduced by Kok for LHL and LSM, and ii) for CORA, we learned clauses with at most 5 predicates instead of 4. Besides, since we aim at comparing two generative learning systems, after learning the MLN structure using LSM, we only learned the weights once instead of relearning them for each predicate before performing inference.

For the largest dataset CORA, GSLP increases 16.9% on CLL, 10.5% on AUC compared to LSM and 37.9% on CLL, 16.4% on AUC compared to HGSM. It dominates MBN on CLL in the range of 20-30%. Improvement not only occurs on average values over test folds but also on most of average values over predicates in each test fold. Since CLL determines the quality of the probability output by the algorithms, GSLP improves the ability to predict correctly the query predicates given evidence. As AUC is insensitive to a large number of true negatives, GSLP enhances the ability to predict a few positives in data. GSLP runs much faster than HGSM, especially for CORA, but performs a bit slower than LSM. We can answer question 1 that GSLP performs better, on these datasets, than the state-of-the art systems in terms of both CLL and AUC. However at the predicate level, LSM, MBN sometimes achieve better values than GSLP. We provide the average CLLs, AUCs for every predicate and examples of clauses learned by GSLP in the online appendix.

Comparing GSLP to DMSP, we used DMSP to learn discriminatively MLN structure for predicates WorkedUnder (IMDB), Advisor (UW-CSE) and SameBib, SameTitle, SameAuthor, SameVenue (CORA). These predicates are often used in previous studies for MLN discriminative learning [Dinh et al., 2010a; Biba et al., 2008a]. Table 4 gives the average CLLs, AUCs on those predicates over all test folds for each dataset. The results show that GSLP produces much better AUCs than DMSP did while it loses a litte CLLs. Indeed, it is worst 5% on CLL on predicate SameTitle while the AUC is increased 18.32%. The improvement of AUC reaches at most 37.78% on predicate SameAuthor while the CLL is equal. GSLP gets better results than DMSP in terms of both CLL (1.87%) and AUC (16.96%) on the predicate SameVenue. GSLP is thus competitive to the discriminative system in terms of CLL and dominates it in terms of AUC.

5 RelatedWorks

Structure graphs have been widely used in SRL, including both directed graph models [Neville and Jensen, 2004; Friedman et al., 1999; Kersting and De Raedt, 2007] and undirected graph models [Anderson et al., 2002; Kok and Domingos, 2009]. Our graph of predicates (GoP) although different can be related to PRM [Friedman et al., 1999], which relies on a class dependency directed graph, where each node corresponds to an attribute of some class (or table in a relational database).

Concerning MLN structure learning, the idea to encode database information into a graph has been applied in LHL and LSM by Kok and Domingos [2009; 2010], where relational path-finding [Richards and Mooney, 1992] is used to find paths of ground atoms, then lift them into an undirected "lifted-graph". This latter, however, is very different from GoP; a node corresponds to a set of constants instead of a predicate (or its negation) and an edge corresponds to a predicate instead of a link between predicates. Based on this GoP, our method shows some advantages compared to LHL:

· Building GoP is only based on the types of predicate arguments, which is much faster than tracing all paths of ground atoms. The size (number of nodes and edges) of GoP is hence "fixed" while the one of lifted-graphs varies and depends mostly on the database.

· Negative and positive literals are handled in the same way and only good links are used to extend good candidates seeking for better ones. A path in GoP, holding information on predicates and positions of shared-arguments, is a general description of paths of ground atoms. LHL has to search for all paths of ground atoms, each one being variabilized to create all possible clauses by flipping sign of its literals. This, more or less, still leads to a whole graph-search. The search space in our method is thus greatly reduced compared to LHL.

6 Conclusion

We propose a new algorithm for generative MLN structure learning. Our first experiments show that it outperforms the state-of-the art approaches on some classical benchmarks. Nevertheless, beside these satisfying results, we have identified some points, which must be investigated further:

• Our algorithm works in a generate-and-test manner, runtime is thus mostly spent for evaluating clauses. A strategy to generate less clauses would improve performance.
• If we keep clauses built with the same predicates (Subsection 3.3), then we get better performance (in terms of WPLL). The balance between performance, tractability and runtime will be an interesting point to study.
• Based on the graph of predicates, GSLP should be able to handle more complex domains with more predicates and many associations between them. More experiments need to be conducted to verify this remark.

Acknowledgments

We would like to thank our reviewers for their valuable comments. This work was partly funded by R´egion Centre, France.