A Framework for Incorporating General Domain Knowledge into Latent Dirichlet Allocation Using First-Order Logic

1 Introduction

Building upon the success of Latent Dirichlet Allocation (LDA) [Blei et al., 2003], a large number of latent-topicmodel variants have been proposed for many application domains. Often, these variants are custom-built by incorporating external knowledge specific to the target domain, see e.g., [Wang et al., 2009; Gerrish and Blei, 2010]. However, deriving a "custom" latent topic model, along with an efficient inference scheme, requires machine-learning expertise not common among application domain experts. Furthermore, such effort must be duplicated whenever a new type of domain knowledge is to be used, preventing domain experts from taking full advantage of topic modeling approaches. Previous work has integrated word-level knowledge into topic models for both batch [Andrzejewski et al., 2009; Petterson et al., 2010] and interactive [Hu et al., 2011] settings, but these approaches do not incorporate constraints involving documents, topics, or general side information.

The main contribution of this paper is Fold·all (First-Order Logic latent Dirichlet ALLocation), a framework for incorporating general domain knowledge into LDA. A domain expert only needs to specify her domain knowledge as First-Order Logic (FOL) rules, and Fold·all will automatically incorporate them into LDA inference to produce topics shaped by Mark Craven University of Wisconsin-Madison craven@biostat.wisc.edu

Benjamin Recht

University of Wisconsin-Madison brecht@cs.wisc.edu

both the data and the rules. This approach enables domain experts to focus on high-level modeling goals instead of the low-level issues involved in creating a custom topic model. In fact, some previous topic model variants can be expressed within the Fold·all framework.

Internally, Fold·all converts the FOL rules into a Markov Random Field, and combines it with the LDA probabilistic model. As such, it can be viewed as an instance of a Hybrid Markov Logic Network (HMLN) [Wang and Domingos, 2008], which is itself a generalization of a Markov Logic Network (MLN) [Richardson and Domingos, 2006]. However, existing inference schemes developed for HMLNs and MLNs do not scale well for typical topic modeling applications. Another contribution of this paper is a scalable stochastic optimization algorithm for Fold·all, which is potentially useful for general MLN research, too.

2 The Fold·all Framework

We now briefly review the standard LDA model [Blei et al., 2003]. While we describe variables in terms of text (e.g., words and documents), note that both LDA and Fold·all are general and can be applied to non-text data as well. Let w = w1 . . .wN be a text corpus containing N tokens, with d = d1 . . . dN being the document indices of each word token and z = z1 . . . zN being the hidden topic assignments of each token. Each topic t = 1 . . . T is represented by a multinomial φt over a W-word-type vocabulary. The φ's have a Dirichlet prior with parameter β. Likewise, each document j = 1 . . . D is associated with a multinomial θj over topics, with another Dirichlet prior with parameter α. The generative model is P(w, z, φ, θ | α, β, d) ∝

where φzi (wi) is the wi-th element in vector φzi , and θdi (zi) is the zi-th element in vector θdi . One important goal of topic modeling is to estimate the topics φ given a corpus (w, d).

The key to our Fold·all framework is to allow domain knowledge, specified in FOL, to influence the values of the hidden topics z, indirectly influencing φ and θ. FOL provides a powerful and flexible way to specify domain knowledge. For example, an analyst working on a congressional debate corpus where each speech is a document may specify the rule

which states that for any word token wi = "taxes" that appears in a speech by a Republican, the corresponding latent topic should be zi = 77. We briefly review some FOL concepts [Domingos and Lowd, 2009] for Fold·all.

We define logical predicates for each of the standard LDA variables, letting Z(i, t) be true if the hidden topic zi = t, and false otherwise. Likewise, W(i, v) and D(i, j) are true if wi = v and di = j, respectively. In addition, Fold·all can incorporate other variables beyond those modeled by standard LDA. In our previous example, a domain expert defines a predicate Speaker(di,Rep), which is true if the speaker for document di is a member of the Republican political party. We use o to collectively denote these other observed variables and their corresponding logical predicate values.

The domain expert specifies her background knowledge in the form of a weighted FOL knowledge base using these predicates: KB = {(λ1, ψ1), . . . , (λL, ψL)}. The KB is in Conjunctive Normal Form, consisting of L pairs where each rule ψl is an FOL clause, and λl ≥ 0 is its weight which the domain expert sets to represent the importance of ψl. Thus, in general Fold·all treats such rules as soft preferences rather than hard constraints. The knowledge base KB is tied to our probabilistic model via its groundings. For each FOL rule ψl, let G(ψl) be the set of groundings, each mapping the free variables in ψl to specific values. For the "taxes" example above, G consists of all N propositional rules where i = 1 . . .N. For each grounding g ∈ G(ψl), we define an indicator function

For example, if w100 = "taxes", Speaker(d100,Rep) = true, and z100 = 88, then the grounding g = (W(100, taxes) ∧ Speaker(d100,Rep) ⇒Z(100, 77)) will have 1g(z, w, d, o) = 0 because of the mismatch in z100.

To combine the KB and LDA, we define a Markov Random Field over latent topic assignments z, topic-word multinomials φ, and document-topic multinomials θ, treating words w, documents d, and side information o as observed. Specifically, in this Markov Random Field the conditional probability P (z, φ, θ | α, β, w, d, o, KB) is proportional to

This Markov Random Field has two parts: the first term acts as a prior from the KB, and the remaining terms are identical to LDA (1). Each satisfied grounding of FOL rule ψl contributes exp(λl) to the potential function. Note in general, the first term couples all the elements of z, although the actual dependencies are determined by the particular form of the KB. The factor graph for the Fold·all Markov Random Field is shown in Figure 1, with a special "mega factor node" corresponding to the first term.

The first term in (3) is equivalent to a Markov Logic Network (MLN) [Richardson and Domingos, 2006]. The remaining terms in (3) involve continuous variables such as θ, φ. This combination has been proposed in the MLN community under the name of Hybrid Markov Logic Networks (HMLN) [Wang and Domingos, 2008], but to our knowledge previous HMLN research has not combined logic with LDA.

3 Scalable Inference in Fold·all

Since exact inference is intractable for both LDA and MLN models, it is unsurprising that Fold·all inference is difficult as well. In fact, the combination of logic and topic modeling components presents a unique scalability challenge which cannot be addressed by existing techniques.

We are interested in inferring the most likely φ and θ in Fold·all. However, as in standard LDA, the latent topic assignments z cannot be marginalized out. We instead aim to find the Maximum a Posteriori (MAP) estimate of (z, φ, θ) jointly. This can be formulated as maximizing the logarithm of the unnormalized probability (3):

This non-convex problem is particularly challenging due to the fact that the summations over groundings G(ψl) are combinatorial: on a corpus with length N, an FOL rule with k universally quantified variables will produce N k groundings. This explosion resulting from propositionalization is a well-known problem in the MLN community, and has been the subject of considerable research [Singla and Domingos, 2008; Kersting et al., 2009; Riedel, 2008; Huynh and Mooney, 2009]. For instance, one can usually greatly reduce the problem size by considering only nontrivial groundings [Shavlik and Natarajan, 2009]. As an example, the rule in (2) is trivially true for all indices i such that wi ̸= "taxes", and these indices can be excluded from computation. Unfortunately, even after this pre-processing, there may be an unacceptably large number of groundings. Furthermore, the inclusion of the LDA terms and the scale

Input: w, d, o, α, β, KB for Nouter iterations do set φ, θ with (5) (6) set z \ zKB with (7) for Ninner iterations do sample term f from (9) update zit's in f with (10) end set zi ∈ zKB with argmaxt zit end return (z, φ, θ)

of our domain prevent us from directly taking advantage of many techniques developed for MLNs. In what follows, we describe a stochastic gradient descent algorithm, Alternating Optimization with Mirror Descent, to find a local maximum of (4). This approach may also be applied to standard MLNs, although we leave that application as future work.

3.1 Alternating Optimization withMirror Descent

We propose Alternating Optimization with Mirror Descent (Mir) to optimize (4). The complete procedure is presented in Algorithm 1; it proceeds by alternating between optimizing the multinomial parameters (φ, θ) while holding z fixed, and vice versa. The optimal (φ, θ) for fixed z can be easily found in closed-form as the MAP estimate of the Dirichlet posterior:

where ntw is the number of times word w is assigned to topic t in topic assignments z. Similarly, njt is the number of times topic t is assigned to a word in document j.

Optimizing z while holding (φ, θ) fixed is more difficult. One can divide z into an "easy part" and a "difficult part." The easy part consists of all zi which only appear in trivial groundings, where a trivial grounding is defined as any grounding g such that the corresponding indicator function 1g is insensitive to the latent topic assignment z. For example, if the knowledge base consists of only one rule ψ1 = (∀i : W(i, apple) ⇒Z(i, 1)), then the majority of the zi's (those with wi ̸= apple) appear in groundings which are trivially true. These zi's only appear in the last term in (4). Consequently, the optimizer is simply

The difficult part of z consists of those zi appearing in nontrivial groundings, subsequently in the first term of (4). Denote this part zKB. We use stochastic gradient descent to optimize zKB. The key idea is to first relax (4) into a continuous optimization problem, and then randomly sample groundings from the knowledge base, such that each sampled grounding provides a stochastic gradient to the relaxed problem.

Here we describe a procedure for converting the logic grounding indicator 1g into a continuous polynomial over relaxed zit variables. Table 1 gives a simple step-by step example of this procedure; individual steps in the following text reference the corresponding steps in this example.

Step 1: Because we assume the knowledge base KB is in Conjunctive Normal Form, each non-trivial grounding g consists of a disjunction of Z(i, t) atoms (positive or negative), whose logical complement ¬g is therefore a conjunction of Z(i, t) atoms (each negated from the original grounding g).

Step 2: In order to standardize each grounding, let (·)+ be an operator which returns a logical formula equivalent to its argument where we replace all negated atoms ¬Z(i, t) with equivalent disjunctions over positive atoms Z(i, 1) ∨ . . . ∨ Z(i, t - 1) ∨ Z(i, t + 1) ∨ . . . ∨ Z(i, T), and eliminate any duplicate atoms. We now have (¬g)+, which is the logical complement of our original formula g expressed entirely in terms of non-negated literals.

Step 3: We convert this Boolean formula over logical predicates to a polynomial over binary variables. To do this, we replace each Z(i, t) with a binary indicator variable zit ∈ {0, 1} defined to be equal to 1 if Z(i, t) is true and 0 otherwise. Each conjunction ∧ is then replaced with multiplication ∗, and each disjunction ∨ is replaced with addition +. In this way, the conjunction of disjunctions ¬g is converted into a product of sums over binary zit variables.

Step 4: We now have a binary polynomial that is equivalent to ¬g, the negation of our original formula g. In order to remove this negation, we take the binary complement of this expression (i.e., 1 - x where x is the result of Step 3).

We now have a binary polynomial over zit that is exactly equivalent to our original logical formula g. We can formally express this result as

where gi is the set of atoms in g which involve index i. For example, if g = Z(0, 1) ∨ Z(0, 2) ∨ Z(1, 0), then g0 = {Z(0, 1), Z(0, 2)}. Note the observed variables w, d, o are no longer in (8) because g is a non-trivial grounding where the disjunction of w, d, o atoms is always false.

Step 5: With our polynomial representation in hand, we relax the binary variables zit ∈ {0, 1} to continuous values zit ∈ [0, 1], with the constraint ∑t zit = 1 for all i. Under this relaxation, Equation (8) takes on values in the interval [0, 1], which can be interpreted as the expectation of the original Boolean indicator function under a distribution where each relaxed zit represents the multinomial probability that Z(i, t) is true. We note that this function is non-convex due to bilinearity in zit.

Dropping terms that are constant w.r.t. zKB and reintroducing the LDA objective function terms yields the continuous optimization problem

This relaxation allows us to use gradient methods on (9). However a potentially huge number of groundings in ∪lG(ψl) may still render the full gradient impractical to compute. Critically, the next step is to use stochastic gradient descent for scalability, specifically the Entropic Mirror Descent Algorithm (EMDA) [Beck and Teboulle, 2003], of which the Exponentiated Gradient (EG) [Kivinen and Warmuth, 1997] algorithm is a special case. Unlike approaches [Collins et al., 2008] which randomly sample training examples to produce a stochastic approximation to the gradient, we randomly sample terms in (9). A term f is either the polynomial 1g(z) on a particular grounding g, or an LDA term ∑t zit logφt(wi)θdi (t) for some index i. We use a weighted sampling scheme. Let Λ be a length L + 1 weight vector, where Λl = λl|G(ψl)| for l = 1 . . . L, and the entry ΛL+1 = |zKB| represents the LDA part. To sample individual terms, we first choose one of the L + 1 entries according to weights Λ. If an FOL rule ψl is chosen, we then sample a grounding g ∈ G(ψl) uniformly. If the LDA part is chosen, we uniformly sample an index i from zKB. Once a term f is sampled, we take its gradient ∇f and perform a mirror descent update with step size η:

The process of sampling terms and taking gradient steps is then repeated for a prescribed number of iterations. Finally, we recover a hard zKB assignment by rounding each zi to argmaxt zit. The key advantage of this approach is that it requires only a means to sample groundings g for each rule ψl, and can avoid fully grounding the FOL rules. We now consider several alternatives to the Mir approach.

3.2 MaxWalkSAT

A simple alternative means of introducing logic into LDA is to perform standard LDA inference and then post-process the latent topic vector z in order to maximize the weight of satisfied ground logic clauses in the KB (i.e., optimize the MLN objective in (4) only). This can be done using a weighted satisfiability solver such as MaxWalkSAT (MWS) [Selman et al., 1995], a stochastic local search algorithm that selects an unsatisfied grounding and satisfies it by flipping the truth state of a single atom, repeating for Ninner iterations. Choosing which atom to flip is done either randomly (with probability p) or greedily w.r.t. the change ΔKB to the global weighted satisfaction objective function. We keep the best (highest satisfied weight) assignment z found, although the fact that MWS does not take the learned topics into account means that this may actually decrease the full objective (4).

3.3 Alternating Optimization withMWS+LDA

A more principled approach is to integrate the logic and LDA objectives. In Algorithm 1, we replace the zKB inner loop with MWS+LDA (M+L), a form of MWS modified to incorporate the LDA objective in the greedy selection criterion by selecting an atom according to Δ = ΔKB + ΔLDA, where ΔLDA is the change to the LDA objective. This aims to maximize the objective (4), balancing the gain from satisfying a logic clause and the gain of a topic assignment given the current φ and θ parameters. We initialize using standard LDA, and the inner MWS+LDA loop keeps the best zKB found with respect to both satisfied logic weight and the LDA objective.

3.4 Collapsed Gibbs Sampling

We also perform collapsed Gibbs sampling (CGS) with respect to the full Fold·all distribution (3). While Gibbs sampling is not aimed at maximizing the objective, the hope is that the sampler will explore high probability regions of the z space. The collapsed Gibbs sampler iteratively resamples zi at each corpus position i, with the probability of candidate topic assignment zi = t given by P(zi = t|z-i, w, d, o, KB, α, β) ∝

where each -i indicates that we exclude the word token at position i. Note that (11) is the product of the standard LDA collapsed Gibbs sampler [Griffiths and Steyvers, 2004] and the MLN Gibbs sampling equation [Richardson and Domingos, 2006]. We keep the sample which maximizes (4). This approach may suffer from poor mixing in the presence of highly weighted logic rules [Poon and Domingos, 2006].

4 Experiments

Our experiments evaluate the generalization of the Fold·all model by measuring whether learned topics reflect both corpus statistics and the user-defined logic rules when applied to unseen documents and associated logic rule groundings. Simultaneously, we evaluate the scalability of inference methods by applying Fold·all to datasets and KBs with large numbers of non-trivial groundings. Our experiments demonstrate that: i) Fold·all successfully incorporates logic into topic modeling, and ii) Mir is a scalable and effective inference method for Fold·all that works when other methods fail.

We conduct experiments on several datasets and corresponding KBs using the four Fold·all inference methods developed in Section 3 (Mir, MWS, M+L, and CGS). We also use two baseline methods which do not integrate topic modeling and logic: topic modeling alone (standard LDA inference with a collapsed Gibbs sampler), and logic alone (MAP inference with the Alchemy MLN software package [Kok et al., 2009]). These baselines use existing techniques to model the LDA and MLN components in isolation.

For each KB, all free variables are universally quantified and we set logic rule weights λ to make the scale of the logic contribution comparable to the LDA contribution in the objective function (4). Table 2 shows details such as the λ's used and the number of non-trivial groundings | ∪l G(ψl)|. We set (Nouter,Ninner) to (102 , 105 ) and run Gibbs samplers for 2,000 samples. The Mir inner loop (Algorithm 1) step size decays as ηm = √Ninner/√Ninner +m for inner iteration m. We initialize all Fold·all algorithms with the final collapsed Gibbs sample from standard LDA, and fix Dirichlet parameters to α = 50/T and β = 0.01. We now present example datasets and KBs along with qualitative assessments. Synthetic Cannot-Link (Synth): This small synthetic dataset demonstrates the ability of Fold·all to encode the Cannot-Link preference [Andrzejewski et al., 2009], which states that occurrences of a pair of words should not be assigned to the same topic. We encode Cannot-Link (A, B) as W(i, A) ∧ W(j, B) ⇒ ¬Z(i, t) ∨ ¬Z(j, t) (the opposite MustLink can be encoded similarly). Alchemy and Fold·all are able to enforce the KB, while standard LDA often does not. Comp.* newsgroups (Comp): This dataset consists of online posts made to comp.* news groups from 20 newsgroups. We consider a user wishing to construct two separate topics around the concepts hardware and software. Our KB encourages the recovery of these topics using {hardware, machine, memory, cpu} and {software, program, version, shareware} as seed words in two rules: W(i, hardware)∨. . .∨W(i, cpu) ⇒ Z(i, 0) and W(i, software) ∨ . . . ∨ W(i, shareware) ⇒ Z(i, 1). The topics found by Fold·all inference methods align with our intended concepts: Topic 0 tends to consist of hardwarerelated terms: {drive, disk, ide, bus, install}, while new Topic 1 terms are software-oriented: {code, image, data, analysis}. Congress (Con): This dataset consists of floor-debate transcripts from the United States House of Representatives [Thomas et al., 2006]. Each speech is labeled with the political party of the speaker: Speaker(d,Rep) or Speaker(d,Dem). The predicate HasWord(d,w) is true if word w appears in document d. We consider an analyst wishing to identity interesting political topics using a KB containing a seed word rule putting {chairman, yield, madam} in Topic 0, as well as two rules exploiting political party labels:

The first rule pulls uninteresting procedural words (e.g., "Mr. Chairman, I want to thank the gentlewoman for yielding...") into their own Topic 0. The other rules aim to discover interesting political topics associated with Rep on taxes and Dem on workers. As intended, Topic 0 pulls in other procedural words ({gentleman, thank, colleague}), improving the quality of the other topics. The special Rep taxes topics uncover interesting themes ({budget, billion, deficit, health, education, security, jobs, economy, growth}), as do the Demworkers topics ({pension, benefits, security, osha, safety, prices, gas}). This KB demonstrates how Fold·all can exploit side information to influence topic discovery.

Polarity (Pol): This dataset consists of positive and negative movie reviews [Pang and Lee, 2004]. We posit an expert analyst who wishes to study the difference between usage of the word "movie" versus the word "film" in these reviews, placing Cannot-Link rule between those two words. The size of the groundings is too large for all logic-based methods except Mir, which is able to discover topics obeying the KB which reveal subtle sentiment differences associated with the two words (e.g., the movie topic contains "bad", while the film topic contains "great"). Figure 2 shows word clouds 1 for a pair of Mir topics containing "film" or "movie" only.

Human Development Genes (HDG): This dataset consists of PubMed abstracts; the goal is to learn topics for six concepts formulated by an actual biologist interested in human development. The expert provided seed words for each concept, which were translated into FOL rules. For example, the Topic 2 seed words are {hematopoietic, blood, endothelium}. However, using seed rules alone yields concept topics which stray from basic biology, and are polluted by more clinical terms such as {pressure, hypertension} and {leukemia, acute, myeloid}. We therefore seed an additional disease Topic 7 and enforce that this topic not co-occur in the same sentence as our original development concept topic. Let s = s1, . . . , sN be a vector of sentence indices analogous to d, with logical predicate S(i, s) being true if si = s. Our exclusion rule for the concept Topic 2 is

In order to further encourage the recovery of developmentoriented topics, we also define a development Topic 8 with seed words {differentiation, . . ., develops}, and define an inclusion rule enforcing that our concept topics not be used within a sentence unless Topic 8 also occurs (similar to to the exclusion rule). This KB results in more "on-concept" topics, including new terms {epo, peripheral, erythroid} for Topic 2. While a full discussion is infeasible due to space constraints, blind relevance judgments by our biological collaborator confirm the effectiveness of Fold·all in discovering new terms related to the target concepts [Andrzejewski, 2010].

1 http://www.wordle.net

4.1 Generalization

We assess the quality of the learned topics φ by examining their generalization to unseen documents via cross validation. At training time, we perform inference with one of the six methods on the training documents and KB (if applicable) to estimate the topic-word multinomials φ. At test time, we hold φ fixed and perform LDA-style inference over z on the testing documents. Note the logic KB is not used during the test phase, allowing us to see whether the KB "generalizes" to the test corpus via the learned topics φ.

We measure such generalization by evaluating the joint logic and LDA objective (4) on the test documents. The results are presented in Table 2, where each cell contains the test set value of (4) averaged across folds. We collectively refer to Mir, M+L, CGS, and MWS as Fold·all inference methods because they consider both LDA and logic components of Fold·all, and the results show that they are indeed better at optimizing the joint logic and LDA objective (4) than topic modeling alone (LDA) or logic alone (Alchemy), and therefore better at integrating FOL into topic modeling.

We also directly examine the number of satisfied groundings on held-aside test documents for both Mir and LDA. Across all KBs and folds, the topics learned by Mir result in the satisfaction of as many, or more, test set groundings than the topics learned by standard LDA. For example, on the first test fold of Synth, inference with the standard LDA topics satisfies 1,040 the 1,600 non-trivial Cannot-Link groundings, while the topics learned using the KB (all Fold·all methods plus Alchemy) result in the satisfaction of all 1,600 groundings even though the KB is not used for test set inference. Similar results across all experiments demonstrate that the learned topics transfer KB influence to the new documents.

4.2 Scalability

We say that an experimental run fails (indicated by a "-" in Table 2) if it does not complete within 24 hours on a standard workstation with a 2.33 GHz processor and 16 GB of memory. For example, even though Pol is a relatively small corpus with a straightforward KB, the two free variables i and j cause the number of non-trivial groundings to grow O(N 2 ) with corpus length N. This causes the failure of Fold·all inference schemes which work directly with rule groundings (MWS, M+L, and CGS). By sampling groundings, Mir is able to learn topics across the range of datasets and KBs, even in the presence of exponentially many groundings. Mir inference completes in roughly 5 minutes on the full HDG corpus, consuming less than 5 GB memory.

5 Discussion

The Fold·all model can also reformulate some prior LDA extensions, although we stress that rule weights must be usersupplied, not learned. Furthermore, inference for a logicbased encoding may not be more efficient than a custom inference procedure tailored to the specific model.

Concept-Topic Model [Chemudugunta et al., 2008] ties special concept topics to specific concepts by constraining these special topics to only emit words from carefully chosen subsets of the vocabulary. The rule Z(i, t) ⇒ W(i, wc1) ∨ W(i, wc2) ∨ . . . ∨W(i, wcK) enforces that concept topic t only emits the words wc1, wc2, . . . , wcK.

Hidden Markov Topic Model [Gruber et al., 2007] enforces that the same topic be used for an entire sentence, allowing topic transitions only between sentences. Using our previously introduced sentence predicate S(i, s), we can express the intra-sentence topic consistency constraint as S(i, s)∧S(j, s)∧Z(i, t) ⇒ Z(j, t). The probabilities of intersentence topic transitions can be set by carefully choosing weights for rules of the form S(i, s)∧¬S(i+1, s)∧Z(i, t) ⇒ Z(i + 1, t′ ) for all transition pairs (t, t′ ).

ΔLDA [Andrzejewski et al., 2007], Discriminative LDA [Lacoste-Julien et al., 2008], Labeled LDA [Ramage et al., 2009] all allow the specification of special "restricted" topics which can be used only in specially labeled documents. The goal of this constraint is to encourage these special topics to capture interesting patterns associated with the document labels. If topic t should only be used in documents with label ℓ, we can encode this type of constraint as Z(i, t) ∧ D(i, d) ⇒ HasLabel(d, ℓ).

We have introduced Fold·all and given some simple examples of how it can incorporate domain knowledge into topic modeling. We have also provided a scalable inference solution Mir. Experimental results confirm that the influence of the user-defined KB generalizes to unseen documents, and that Mir enables inference when other approaches fail.

Future work could allow the formulation of relational inference problems in Fold·all by defining additional query atoms other than Z(i, t), as in general MLNs. For example, we could define unobserved predicate Citation(d, d′ ) to be true if document d cites document d′ . Another direction is to investigate the utility of Mir for general MLN MAP inference.

Acknowledgments

This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under Contract DE-AC52-07NA27344, with additional support from NSF IIS-0953219, AFOSR FA9550-09-1-0313, and NIH/NLM R01 LM07050. We would like to thank Ron Stewart for his participation in the HDG experiments.