Under consideration for publication in Theory and Practice of Logic Programming

1

Products of Weighted Logic Programs∗

arXiv:1006.3035v1 [cs.AI] 15 Jun 2010

SHAY B. COHEN, ROBERT J. SIMMONS, and NOAH A. SMITH
School of Computer Science
Carnegie Mellon University
E-mail: {scohen,rjsimmon,nasmith}@cs.cmu.edu
submitted 1 January 2003; revised 1 January 2003; accepted 1 January 2003

Abstract
Weighted logic programming, a generalization of bottom-up logic programming, is a wellsuited framework for specifying dynamic programming algorithms. In this setting, proofs
correspond to the algorithm’s output space, such as a path through a graph or a grammatical derivation, and are given a real-valued score (often interpreted as a probability)
that depends on the real weights of the base axioms used in the proof. The desired output is a function over all possible proofs, such as a sum of scores or an optimal score.
We describe the PRODUCT transformation, which can merge two weighted logic programs
into a new one. The resulting program optimizes a product of proof scores from the original programs, constituting a scoring function known in machine learning as a “product of
experts.” Through the addition of intuitive constraining side conditions, we show that several important dynamic programming algorithms can be derived by applying PRODUCT to
weighted logic programs corresponding to simpler weighted logic programs. In addition,
we show how the computation of Kullback-Leibler divergence, an information-theoretic
measure, can be interpreted using PRODUCT.
KEYWORDS: weighted logic programming, program transformations, natural language
processing

1 Introduction
Weighted logic programming is a technique that can be used to declaratively specify
dynamic programming algorithms in a number of fields such as natural language
processing (Manning and Schütze 1999) and computational biology (Durbin et al.
1998). Weighted logic programming is a generalization of bottom-up logic programming where each proof is assigned a score (or weight) that is a function of the scores
of the axioms used in the proof. When these scores are interpreted as probabilities,
then the solution to a whole weighted logic program can be interpreted in terms of
probabilistic reasoning about unknowns, implying that the weighted logic program
implements probabilistic inference.1
∗ To appear in Theory and Practice of Logic Programming (TPLP).
1 The word inference has a distinct meaning in logic programming (e.g. “inference rule,” “valid inference”), and so we will attempt to avoid confusion by using the probabilistic modifier whenever
we are talking about probabilistic reasoning about unknowns.

2

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

Even though weighted logic programming is not limited to probabilistic inference,
it is worth detailing their relationship. Let I, A, and P be random variables, where
the values of I and A are known and the value of P is not known. Often there is a
correspondence where
• I corresponds to a conditional “input,” encoded as axioms, known to be true;
• A corresponds to a set of axioms known to be true; and
• P corresponds to a deductive proof of the goal theorem using the axioms.
In the setting of weighted logic programming, there may be many different proofs of
the goal given the set of axioms. We must therefore distinguish the weighted logic
program from the “world” we are reasoning about in which these many different
proofs of the goal correspond to different, mutually exclusive events, each of which
has some probability of occurring. Weighted logic programming implements probabilistic inference over the value of the proof random variable P given the values of
A and I: the weighted logic program implies a probability distribution p(P | A, I),
and it can be used to compute different useful quantities related to the distribution.
Previous work on weighted logic programming has shown that certain families of
probabilistic models lend themselves extremely well to weighted logic programming
as an inference mechanism. In general, weighted logic programming deals with
probability distributions over objects with combinatorial structure—paths through
graphs, grammatical derivations, and sequence alignments—that are quite useful
in computer science applications.
In principle, one can think about combining such distributions with each other,
creating distributions over even more complex structures that are related. This
paper is about a natural extension to weighted logic programming as probabilistic
inference over structures: combining weighted logic programs to perform inference
over two or more structures. We describe a program transformation, PRODUCT, that
implements joint probabilistic inference via weighted logic programming over two
structured variables P1 and P2 , when (a) each of the two separate structures can be
independently reasoned about using weighted logic programming, and (b) the joint
model factors into a product of two distributions p(P1 | A1 , I1 ) and p(P2 | A2 , I2 ).2
As a program transformation on traditional logic programs, PRODUCT is not novel;
it has existed as a compiler transformation for over a decade (Pettorossi and Proietti 1994; Pettorossi 1999). As a way of describing joint probabilistic inference in
weighted logic programming, the transformation has been intuitively exploited in
designing algorithms for specific applications, but has not, to our knowledge, been
generalized. The contribution of this paper is a general, intuitive, formal setting for
dynamic programming algorithms that process two or more conceptually distinct
objects. Indeed, we show that many important dynamic programming algorithms
can be derived using simpler “factor” programs and the PRODUCT transformation
together with side conditions that capture the relationship between the structures.
The paper is organized as follows. In §2 we give an overview of weighted logic
2

In the language of probability, this means that P1 and P2 are conditionally independent given
A1 , A2 , I1 , and I2 .

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).3

reachable(Q)

:-

initial(Q).

(1)

reachable(Q)

:-

reachable(P), edge(P, Q).

(2)

Fig. 1. A simple bottom-up logic program for graph reachability.

a

b

c

d

initial(a)
edge(a, c)
edge(a, d)
edge(b, b)
edge(c, a)

=
=
=
=
=

t
t
t
t
t

edge(c, d)
edge(d, b)
edge(d, c)
edge(d, d)

=
=
=
=

t
t
t
t

Fig. 2. A directed graph and the corresponding initial database.

programming. In §3 we describe products of experts, a concept from machine learning that elucidates the kinds of probabilistic models amenable to our framework. In
§4 we describe the PRODUCT transformation. In §5 we give show how several wellknown algorithms can be derived using the PRODUCT transformation applied to
simpler algorithms. §6 presents some variations on the PRODUCT transformation. In
§7 we show how to use the PRODUCT transformation and a specially designed semiring to calculate important information theoretic quantities related to probability
distributions over proofs.

2 Weighted Logic Programming
To motivate weighted logic programming, we begin with a logic program for singlesource connectivity on a directed graph, shown in Figure 1. In the usual bottomup interpretation of this program, an initial database (i.e., set of axioms) would
describe the edge relation and one (or more) starting vertices as axioms of the form
initial(a) for some a. Repeated forward inference can then be applied on the
rules in Figure 1 to find the least database closed under those rules. However, in
traditional logic programming this program can only be understood as a program
calculating connectivity over a graph.
Weighted logic programming generalizes traditional logic programming. In traditional logic programming, a proof is a tree of valid (deductive) inferences from
axioms, and a valid atomic proposition is one that has at least one proof. In weighted
logic programming we generalize this notion: axioms, proofs, and atomic propositions are said to “have values” rather than just “be valid.” Traditional logic programs can be understood as weighted logic programs with Boolean values: axioms
all have the value “true,” as do all valid propositions. The single-source connectivity
program would describe the graph in Figure 2 by assigning t as the value of all the
existing edges and the proposition initial(a).

4

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith
2.1 Non-Boolean Programs

With weighted logic programming, the axioms and propositions can be understood
as having non-Boolean values. In Figure 3, each axiom of the form edge(X, Y) is
given a value corresponding to the cost associated with that edge in the graph, and
the axiom initial(a) is given the value 0. If we take the value or “score” of a
proof to be the the sum of the values the axioms at its leaves and take the value of
a proposition to be the minimum score over all possible proofs, then the program
from Figure 1 gives a declarative specification of the single-source shortest path
problem. Multiple uses of an axiom in a proof are meaningful: if a proof includes
the edge(d, d) axiom once, it corresponds to a single traversal of the loop from d
to d and adds a cost of 2, and if a proof includes the axiom twice, it corresponds
to two distinct traversals and adds a cost of 4.
We replace the connectives :- (disjunction) and , (conjunction) with min = and +,
respectively, and interpret the WLP over the non-negative numbers. With a specific
execution model, the result is Dijkstra’s single-source shortest-path algorithm.

8

a

b
9

20

6

4
16

c
15

d
2

initial(a)
edge(a, c)
edge(a, d)
edge(b, b)
edge(c, a)

=
=
=
=
=

0
4
20
8
9

edge(c, d)
edge(d, b)
edge(d, c)
edge(d, d)

=
=
=
=

15
6
16
2

Fig. 3. A cost graph and the corresponding initial database.

In addition to the cost-minimization interpretation in Figure 3, we can interpret
weights on edges as probabilities and restate the problem in terms of probability
maximization. In Figure 4, the outgoing edges from each vertex sum to at most 1.
If we assign the missing 0.1 probability from vertex b to a “stopping” event—either
implicitly or explicitly by modifying the axioms—then each vertex’s outgoing edges
sum to exactly one and the graph can be seen as a Markov model or probabilistic finite-state network over which random walks are well-defined. If we replace
the connectives :- (disjunction) and , (conjunction) with max = and ×, then the
value of reachable(X) for any X is the probability of the most likely path from
a to X. For instance, reachable(a) ends up with the value 1, and reachable(b)
ends up with value 0.16, corresponding to the path a → d → b, whose weight is
(value of initial(a) × value of edge(a, d) × value of edge(d, b)).
If we keep the initial database from Figure 4 but change our operators from max =
and × to += and ×, the result is a program for summing over the probabilities
of all distinct paths that start in a and lead to X, for each vertex X. This quantity
is known as the “path sum” (Tarjan 1981). The path sum for reachable(b), for

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).5

0.9

a
0.2
0.6

c

0.8

0.3
0.4

b
0.2

d
0.5

initial(a)
edge(a, c)
edge(a, d)
edge(b, b)
edge(c, a)

=
=
=
=
=

1
0.2
0.8
0.9
0.6

edge(c, d)
edge(d, b)
edge(d, c)
edge(d, d)

=
=
=
=

0.4
0.2
0.3
0.5

Fig. 4. A probabilistic graph and the corresponding initial database. With stopping
probabilities made explicit, this would encode a Markov model.
reachable(Q)

⊕=

initial(Q).

(3)

reachable(Q)

⊕=

reachable(P) ⊗ edge(P, Q).

(4)

Fig. 5. The logic program from Figure 1, rewritten to emphasize that it is generalized to an arbitrary semiring.

instance, is 10—this is not a probability, but rather an infinite sum of probabilities
of many paths, some of which are prefixes of each other.3
These three related weighted logic programs are useful generalizations of the
reachability logic program in Figure 1. Figure 5 gives a generic representation of
all four algorithms in the Dyna language (Eisner et al. 2005). The key difference
among them is the semiring in which we interpret the weights. An algebraic semiring
consists of five elements hK, ⊕, ⊗, 0, 1i, where K is a domain closed under ⊕ and ⊗,
⊕ is a binary, associative, commutative operator, ⊗ is a binary, associative operator
that distributes over ⊕, 0 ∈ K is the ⊕-identity, and 1 ∈ K is the ⊗-identity.
We require, following Goodman (1999), that the semirings we use be complete.
Complete semirings are semirings with the additional property that they are closed
under finite products and infinite sums—in our running example, this corresponds
to the idea that there may be infinitely many paths through a graph, all with finite
length. Complete semirings also have the property that infinite sums behave like
finite ones—they are associative and commutative, and the multiplicative operator
distributes over them.
In our running example, reachability uses the Boolean semiring h{t, f}, ∨, ∧, f, ti,
single-source shortest path uses hR≥0 ∪ {∞}, min, +, ∞, 0i, the most-probable-path

3

Clearly “10” is not a meaningful probability, but that is a result of the loop from b to b with
probability 0.9—in fact, one informal way of looking at the result is simply to observe that
10 = 1 + 0.9 + (0.9)2 + (0.9)3 + . . ., corresponding to proofs of reachable(b) that include
edge(b, b) zero, one, two, three, . . . times. If we added an axiom edge(b, final) with weight 0.1
representing the 10% probability of stopping at any step in state b, then the path sum for
reachable(final) would be 10 × 0.1 = 1, which is a reasonable probability that corresponds
to the fact that a graph traversal can be arbitrarily long but has a 100% chance of eventually
reaching b and then stopping.

6

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

variant uses h[0, 1], max, ×, 0, 1i, and the probabilistic path-sum variant uses the
so-called “real” semiring hR≥0 ∪ {∞}, +, ×, 0, 1i.
Weighted logic programming developed primarily within the computational linguistics community. Building upon the observations of Shieber, Schabes, and Pereira
(1995) and Sikkel (1997) that many parsing algorithms for nondeterministic grammars could be represented as deductive logic programs, Goodman (1999) showed
that the structure of the parsing algorithms was amenable to interpretation on
a number of semirings. McAllester (1999) additionally showed that this representation facilitates reasoning about asymptotic complexity. Other developments include a connection between weighted logic programs and hypergraphs (Klein and
Manning 2004), optimal A∗ search for maximizing programs (Felzenszwalb and
McAllester 2007), semiring-general agenda-based implementations (Eisner et al.
2005), improved k-best algorithms (Huang and Chiang 2005), and program transformations to improve efficiency (Eisner and Blatz 2007).
2.2 Formal Definition
Eisner and Blatz (2007) describe the semantics of weighted logic programs in detail;
we summarize their discussion in this section and point the reader to that paper
for further detail. A weighted logic program is a set of Horn equations describing
a set of declarative, usually recursive equations over an abstract semiring. Horn
equations, which we will refer to by the shorter and more traditional term rules,
take the form
consequent(U) ⊕= antecedent1 (W1 ) ⊗ · · · ⊗ antecedentn (Wn ).
Here U and the Wi are sequences of terms which include free variables. If the
variables in U are a subset of the variables in W1 . . . Wn for every rule, then the
program is range restricted or fully grounded.
We can also give rules side conditions. Side conditions are additional constraints
that are added to a rule to remove certain proofs from consideration. For example,
side conditions could allow us to modify rule 4 in Figure 5 to disallow self-loops
and only allow traversal of an edge when there was another edge in the opposite
direction:
reachable(Q) ⊕= reachable(P) ⊗ edge(P, Q) if edge(Q, P) ∧ Q 6= P.

(5)

Side conditions do not change the value of any individual proof, they only filter out
any proof that does not satisfy the side conditions. In this paper, we use mostly side
conditions that enforce equality between variables. For a more thorough treatment
of side conditions see Goodman (1999) or Eisner and Blatz (2007).
A weighted logic program is specified on an arbitrary semiring, and can be interpreted in any semiring hK, ⊕, ⊗, 0, 1i as previously described. The meaning of
a weighted logic program is determined by the rules together with a set of fully
grounded axioms (or facts in the Prolog setting). Each axiom is assigned a value
from the set K that is interpreted as a weight or score.
A common idiom in weighted logic programming is to specify the query as a

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).7
distinguished predicate goal that takes no arguments. A computationally uninteresting (because are no intermediate computation steps) but otherwise legitimate
way to present a weighted logic program is as a single rule of the form
goal ⊕= axiom1 (W1 ) ⊗ · · · ⊗ axiomn (Wn ).
In this degenerate case, each distinct way of satisfying the premises using axioms in
the database would correspond to a distinct proof of goal. The score of each proof
would be given by the semiring-product of the scores of the axioms, and the value
of goal would be determined by the semiring-sum of the scores of all the proofs.
In the general case, the value of the proposition/theorem goal is a semiring-sum
over all of its proofs, starting from the axioms, where the value of any single proof
is the semiring-product of the axioms involved. This is effectively encoded using
the inference rules as a sum of products of sums of products of ... sums of products, exploiting distributivity and shared substructure for efficiency. This inherent
notion of shared substructure means that weighted logic programming can give
straightforward declarative specifications for problems that are typically solved by
dynamic programming. The Dyna programming language implements a particular
dynamic programming strategy for implementing these declarative specifications
(Eisner et al. 2005), though the agenda algorithm that it implements may potentially have significantly different behavior, in terms of time and space complexity,
than other dynamic programming algorithms that meet the same specification.
In many practical applications, as in our reachability example in §2.1, values are
interpreted as probabilities to be maximized or summed or costs to be minimized.

3 Weighted Logic Programs and Probabilistic Reasoning
In this section, we will return focus to the probabilistic interpretation of weighted
logic programs that we first described in the introduction. In §3.1 we will describe in more detail how the results of weighted logic programs are interpreted
as probabilities—readers with a background in statistics and machine learning can
probably skip or skim this section. In §3.2, we will introduce the notion of a product
of experts that motivates the PRODUCT transformation.
Our running example for this section is a probabilistic finite-state automaton

0.5, 0

a

0.3, 1
0.2, 0

0.2, 0

b
d

0.8, 1
1.0, 1

c

initial(a)
final(c)
arc(a, b, 0)
arc(a, b, 1)
arc(a, d, 0)
arc(b, c, 0)
arc(b, c, 1)
arc(d, c, 1)

=
=
=
=
=
=
=
=

Fig. 6. A probabilistic FSA and the corresponding initial database.

1
1
0.5
0.3
0.2
0.2
0.8
1.0

8

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

goal

⊕=

path(Q) ⊗ final(Q).

(6)

path(Q)

⊕=

initial(Q).

(7)

path(Q)

⊕=

path(P) ⊗ arc(P, Q, A).

(8)

Fig. 7. The weighted logic program for weighted FSA reachability.
goal

⊕=

path(Q, I) ⊗ final(Q) ⊗ length(I).

path(Q, 0)

⊕=

initial(Q).

(10)

path(Q, I)

⊕=

path(P, I − 1) ⊗ arc(P, Q, A) ⊗ string(I, A).

(11)

(9)

Fig. 8. The weighted logic program for weighted FSA recognition.

over the alphabet {0, 1}, shown in Figure 6. The most probable path through the
graph is the one that recognizes the string “01” by going through states a, b, and c,
and that the probability of this path is 0.4. Other than the labels on the edges, this
is the same setup used in the graph-reachability example from Figure 4. The edge
predicate from the previous section is now called arc and has been augmented to
carry a third argument representing an output character.

3.1 The Probabilistic Interpretation of Weighted Logic Programming
Recall from the introduction that, in the context of weighted logic programming,
we have random variables I, A, and P , where
• I corresponds to a set of conditional “input” axioms known to be true;
• A corresponds to a set of axioms known to be true; and
• P corresponds to a deductive proof of the goal theorem using the axioms.
In this case, I corresponds to one of the various possible sentences recognized by
the FSA (i.e., 00, 01, 10, and 11). A corresponds to a particular directed graph
with weighted edges, encoded by a set of axioms. P corresponds to an individual
proof/path through the graph. In Figure 7, which is the straightforward adaptation
of the reachability program in Figure 5 to labeled edges, the value of goal in the
most-probable-path semiring is maxproof p(P = proof , I = sentence | A = graph)—
the value of the most probable path emitting any possible sentence I.
In order to talk about the input sentences I, we first add a set of axioms that describe I. If we are interested in the sentence “01” we would add axioms string(1, 0),
string(2, 1), and length(2), whereas if we were interested in the sentence “hey” we
would add axioms string(1, h), string(2, e), string(3, y), and length(3). These
axioms are all given the value 1 (the multiplicative unit of the semiring), and so they
could equivalently be treated as side conditions. With these new axioms, we modify

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).9
Figure 7 to obtain Figure 8, a weighted logic program that limits the proofs/paths
to the ones which represent recognition of the input string I.4
Now, Figure 8 interpreted over the most-probable-path semiring does allow us
to find the proof that, given the edge weights and a specific sentence, maximizes
p(P = proof | I = sentence, A = graph). It does not, however, give us p(P = proof |
I = sentence, A = graph), but rather p(P = proof , I = sentence | A = graph), the
joint probability of a path and a sentence given the weights on the edges.
Concretely, in our running example there are five possible proofs of goal in
Figure 7 whose probabilities sum to 1, but there are only two parses that also
recognize the string “01,” which are a0 b1 c with weight 0.4 and a0 d1 c with weight
0.2—the route through b is twice as likely. The value of goal in Figure 8 interpreted
in the most-probable-path semiring would be 0.4 (the joint probability of obtaining
the proof a0 b1 c and of recognizing the string “01”) not 0.6 (the probability of the
proof a0 b1 c given the sentence “01”). In other words, we have: p(P = a0 b1 c, I =
01 | A = Fig. 6) = 0.4, p(P = a0 d1 c, I = 01 | A = Fig. 6) = 0.2, p(P = a0 b1 c | I =
01, A = Fig. 6) = 0.6.
The solution for correctly discovering the conditional probability lies in the fact
that the joint and conditional probabilities are related in the following way:
p(P | A, I) =

p(P, I | A)
p(I | A)

This, combined with the knowledge that the marginal probability p(I | A) is the result of evaluating Figure 8 over the path-sum semiring (i.e., hR≥0 ∪{∞}, +, ×, 0, 1i),
allows us to correctly calculate not only the most probable proof P of a given
sentence but also the probability of that proof given the sentence. The marginal
probability in our running example is 0.6, and 0.4/0.6 = 0.6, which is the desired
result.
To restate this in a way that is more notationally consistent with other work in
machine learning, we first take the weighted axioms A as implicit. Then, instead of
proofs P we talk about values y for a random variable Y drawn out of a domain
Y (the space of possible structures, which in our setting corresponds to the space
of possible proofs), and instead of inputs I we talk about values x for a random
variable X drawn out of a domain X (the space of all possible inputs).
Then, to predict the most likely observed value for y, denoted ŷ, we have the
following formula:
ŷ = argmax p(Y = y | X = x) = argmax
y∈Y

y∈Y

p(Y = y, X = x)
p(X = x)

(12)

Because p(X = x) does not depend on y, if we only want to know ŷ it suffices to
find the y that maximizes p(Y = y, X = x) (which was written as p(P = proof , I =

4

Rule 11 in this figure uses “I − 1” in a premise: we assume that our formalism includes natural
numbers that support increment/decrement operations, and our simple uses can be understood
as syntactic shorthand either for structured terms (z, s(z), etc.) or for the use of primitive side
conditions such as inc(I, I0 ).

10

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

sentence | A = axioms) above). One way to do this is to execute a weighted logic
program in the most-probable-path semiring.
3.2 Products of Experts
Of recent interest are probability models p that take a factored form, for example:
p(Y = y | X = x) ∝ p1 (Y = y | X = x) × · · · × pn (Y = y | X = x)

(13)

where ∝ signifies “proportional to” and suppresses the means by which the probability distribution is renormalized to sum to one. This kind of model is called a
product of experts (Hinton 2002). Intuitively, the probability of an event under p
can only be relatively large if “all the experts concur,” i.e., if the probability is large
under each of the pi . Any single expert can make an event arbitrarily unlikely (even
impossible) by giving it very low probability, and the solution to Equation 12 for
a product of experts model will be the y ∈ Y (here, a proof) least objectionable to
all experts.
The attraction of such probability distributions is that they modularize complex
systems (Klein and Manning 2003; Liang et al. 2008). They can also offer computational advantages when solving Equation 12 (Chiang 2007). Further, the expert
factors can often be trained (i.e., estimated from data) separately, speeding up expensive but powerful machine learning methods (Smith and Smith 2004; Sutton
and McCallum 2005; Smith et al. 2005; Cohen and Smith 2007).
To the best of our knowledge, there has been no attempt to formalize the following
intuitive idea about products of experts: algorithms for reasoning about mutually
constrained product proof values should resemble the individual algorithms for each
of the two separate “factor” proofs’ values. Our formalization is intended to aid in
algorithm development as new kinds of complex random variables are coupled, with
a key practical advantage: the expert factors are known because they fundamentally
underlie the main algorithm. Indeed, we call our algorithms “products” because
they are derived from “factors,” analogous to the product of expert probability
models that are derived from factor expert probability models.
To relate this observation to the running example from this section, imagine we
created two copies of Figure 8 which operated over the same sentence (as described
by string and length predicates) but which had different predicates and axioms
goal1 , path1 , final1 , initial1 , and arc1 (and likewise goal2 , path2 , etc.). Consider a combined goal predicate goal1•2 defined by the rule
goal1•2

⊕=

goal1 ⊗ goal2 .

(14)

Now we have two experts (goal1 and goal2 ), and we literally take the (semiring)
product of them, but this is still not quite the “product of experts,” because the
proofs of the goals are allowed to be independent. In other words, what we have is
the following:
p(Y1 = y1 , Y2 = y2 | X = x) ∝ p1 (Y1 = y1 | X = x) × p2 (Y2 = y2 | X = x).
The PRODUCT transformation is a meaning-preserving transformation on weighted

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
11
logic programs that exposes the joint structure in such a way that—depending on
our domain-specific understanding of what it means for the two proofs y1 and y2 to
match—allows us to add constraints that result in a weighted logic program that
forces the structures to match, as required by the specification in Equation 13.
4 Products of Weighted Logic Programs
In this section, we will motivate products of weighted logic programs in the context of the running example of generalized graph reachability. We will then define
the PRODUCT transformation precisely and describe the process of specifying new
algorithms as constrained versions of product programs.
The PRODUCT transformation can be seen as an instance of the tupling program
transformation combined with an unfold/fold transformation (Pettorossi and Proietti 1994; Pettorossi 1999) that preserves the meaning of programs. However, we
are interested in this transformation not for reasons of efficiency, but because it has
the effect of exposing the shared structure of the two individual programs in such
a way that, by the manual addition of constraints, we can force the two original
programs to optimize over the same structures, thereby implementing optimization
over the product of experts as described in the previous section. The addition of
constraints requires an understanding of the problem at hand, as we show in §5 by
presenting a number of examples.
4.1 The Product of Graph Reachability Experts
Figure 9 defines two experts, copies of the graph-reachability program from Figure 5.
We are interested in a new predicate reachable1•2 (Q1 , Q2 ), which for any particular
Q1 and Q2 should be equal to the product of reachable1 (Q1 ) and reachable2 (Q2 ).
Just as we did in our thought experiment with goal1•2 in the previous section, we
could define the predicate by adding the following rule to the program in Figure 9:
reachable1•2 (Q1 , Q2 ) ⊕= reachable1 (Q1 ) ⊗ reachable2 (Q2 ).
This program is a bit simplistic, however; it merely describes calculating the experts
independently and then combining them at the end.
The predicate reachable1•2 can alternatively be calculated by adding the following four rules to Figure 9:
reachable1•2 (Q1 , Q2 )
reachable1•2 (Q1 , Q2 )
reachable1•2 (Q1 , Q2 )
reachable1•2 (Q1 , Q2 )

⊕=
⊕=
⊕=
⊕=

initial1 (Q1 ) ⊗ initial2 (Q2 ).
initial1 (Q1 ) ⊗ reachable2 (P2 ) ⊗ edge2 (P2 , Q2 ).
reachable1 (P1 ) ⊗ edge1 (P1 , Q1 ) ⊗ initial2 (Q2 ).
reachable1 (P1 ) ⊗ edge1 (P1 , Q1 ) ⊗
reachable2 (P2 ) ⊗ edge2 (P2 , Q2 ).

This step is described as an unfold by Pettorossi (1999). This unfold can then
be followed by a fold: because reachable1•2 (Q1 , Q2 ) was defined above to be the
product of reachable1 (Q1 ) and reachable2 (Q2 ), we can replace each instance of
the two premises reachable1 (Q1 ) and reachable2 (Q2 ) with the single premise
reachable1•2 (Q1 , Q2 ).

12

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

reachable1 (Q1 )

⊕=

initial1 (Q1 ).

(15)

reachable1 (Q1 )

⊕=

reachable1 (P1 ) ⊗ edge1 (P1 , Q1 ).

(16)

reachable2 (Q2 )

⊕=

initial2 (Q2 ).

(17)

reachable2 (Q2 )

⊕=

reachable2 (P2 ) ⊗ edge2 (P2 , Q2 ).

(18)

Fig. 9. Two identical experts for generalized graph reachability, duplicates of the
program in Figure 5.
reachable1•2 (Q1 , Q2 )

⊕=

initial1 (Q1 ) ⊗ initial2 (Q2 ).

(19)

reachable1•2 (Q1 , Q2 )

⊕=

reachable2 (P2 ) ⊗ edge2 (P2 , Q2 ) ⊗ initial1 (Q1 ).

(20)
(21)

reachable1•2 (Q1 , Q2 )

⊕=

reachable1 (P1 ) ⊗ edge1 (P1 , Q1 ) ⊗ initial2 (Q2 ).

reachable1•2 (Q1 , Q2 )

⊕=

reachable1•2 (P1 , P2 ) ⊗ edge1 (P1 , Q1 ) ⊗ edge2 (P2 , Q2 ). (22)

Fig. 10. Four rules that, in addition to the rules in Figure 9, give the product of
the two experts defined by the reachable1 and reachable2 predicates.

The new rules that result from this replacement can be seen in Figure 10.

4.2 The PRODUCT Transformation
The PRODUCT program transformation is shown in Figure 11. For each desired
product of experts, where one expert, the predicate p, is defined by n rules and the
other expert q by m rules, the transformation defines the product of experts for
p•q with n × m new rules, the cross product of inference rules from the first and
second experts. The value of a coupled proposition p•q in P 0 will be equal to the
semiring product of p’s value and q’s value in P (or, equivalently, in P 0 ).
Note that lines 6–8 are nondeterministic under certain circumstances, because if
the antecedent of the combined program is a(X) ⊗ a(Y) ⊗ b(Z) and the algorithm is
computing the product of a and b, then the resulting antecedent could be either
a•b(X, Z) ⊗ a(Y) or a•b(Y, Z) ⊗ a(X). This nondeterminism usually does not arise,
and when it does, as in §5.2, there is usually an obvious preference.
The PRODUCT transformation is essentially meaning preserving: if the program
0
P is the result of the PRODUCT transformation on P, then the following is true:
• Any ground instance p(X) that is given a value in P is given the same value in
P 0 . This is immediately apparent because the program P 0 is stratified: none
of the new rules are ever used to compute values of the form p(X), so their
value is identical to their value in P.
• Any ground instance p•q(X, Y) in P 0 has the same value as p(X) ⊗ q(Y).
This is the result of the following theorem:

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
13
Input: A logic program P and a set S of pairs of predicates (p, q).
Output: A program P 0 that extends P, additionally computing the product predicate
p•q for every pair (p, q) ∈ S in the input.
1: P 0 ← P
2: for all pairs (p, q) in S do
3:
for all rules in P, of the form p(W) ⊕= A1 ⊗ · · · ⊗ An do
4:
for all rules in P, of the form q(X) ⊕= B1 ⊗ · · · ⊗ Bm do
5:
let r ← [p•q(W, X) ⊕= A1 ⊗ · · · ⊗ An ⊗ B1 ⊗ · · · ⊗ Bm ]
6:
for all pairs (s(Y), t(Z)) of antecedents in r such that (s, t) ∈ S do
7:
remove the antecedents s(Y) and t(Z) from r
8:
insert the antecedent s•t(Y, Z) into r
9:
end for
10:
add r to P 0
11:
end for
12:
end for
13: end for
14: return P 0

Fig. 11. Algorithmic specification of the PRODUCT transformation.

Theorem 1
Let P be a weighted logic program over a set of predicates R, and let S be a set of
pairs of predicates from P. Then after applying PRODUCT on (P, S), resulting in a
new program P 0 , for every (p, q) ∈ S, the value p•q(X, Y) in P 0 is p(X) ⊗ q(Y).
Proof:
By distributivity of the semiring, we know that p(X) ⊗ q(Y) is the sum:
M
v(t) ⊗ v(r) where t and r range over proofs of p(X) and q(Y) respectively, with
t,r

their values being v(t) and v(r). This implies that we need to show that there is a
bijection between the set A of proofs for p•q(X, Y) in P 0 and the set B of pairs
of proofs for p(X) and q(Y) such that for every s ∈ A and (t, r) ∈ B we have
v(s) = v(t) ⊗ v(r).
Using structural induction over the proofs, we first show that every pair of proofs
(t, r) ∈ B has a corresponding proof s ∈ A with the needed value. In the base case,
where the proofs t and r include a single step, the correspondence follows trivially.
Let (t, r) ∈ B. Without loss of generality, we will assume that both t and r contain
more than a single step in their proofs. In the last step of its proof, t used a rule of
the form
p(X) ⊕= a1 (X1 ) ⊗ · · · ⊗ an (Xn )

(23)

and r used a rule in its last step of the form
q(Y) ⊕= b1 (Y1 ) ⊗ · · · ⊗ bm (Ym )

(24)

Let ti be the subproofs of ai (Xi ) and let rj be subproofs of bj (Yj ). It follows that
PRODUCT creates from those two rules a single inference rule of the form:
p•q(X, Y) ⊕= c1 (W1 ) ⊗ · · · ⊗ cp (Wp )

(25)

14

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

reachable1•2 (Q1 , Q2 )

⊕=

initial1 (Q1 ) ⊗ initial2 (Q2 ).

reachable1•2 (Q1 , Q2 )

⊕=

reachable1•2 (P1 , P2 ) ⊗ edge1 (P1 , Q1 ) ⊗ edge2 (P2 , Q2 ). (27)

(26)

Fig. 12. By removing all but these two rules from the product of experts in Figure 10, we constrain both paths to have the same number of steps.
reachable1•2 (Q1 , Q2 ) ⊕= initial1 (Q1 ) ⊗ initial2 (Q2 ) if Q1 = Q2 .

(28)

reachable1•2 (Q1 , Q2 ) ⊕= reachable1•2 (P1 , P2 ) ⊗ edge1 (P1 , Q1 ) ⊗ edge2 (P2 , Q2 ) if Q1 = Q2 .

Fig. 13. By further constraining the program in Figure 12 to demand that Q1 = Q2
at all points, we constrain both paths to be identical.
reachable1•2 (Q)

⊕=

initial1 (Q) ⊗ initial2 (Q).

(29)

reachable1•2 (Q)

⊕=

reachable1•2 (P) ⊗ edge1 (P, Q) ⊗ edge2 (P, Q).

(30)

Fig. 14. We can simplify Figure 13 by internalizing the side condition and giving
reachable1•2 only one argument.

where ci (Wi ) is either ak (Yk ) for some k, or bl (Yl ) for some k, or ak • b` (Xk , Y` )
for some k, `.
We resolve each case as following:
1. If ci (Wi ) = ak (Yk ) then we set si = tk .
2. If ci (Wi ) = bk (Yk ) then we set si = rk .
3. If ci (Wi ) = ak • b` (Xk , Y` ) then according to the induction hypothesis, we
have a proof for ak • b` (Xk , Y` ) such that its value is v(tk ) ⊗ v(r` ). We set si
to be that proof.
Since we have shown there is a proof for each antecedent of p • q(X, Y), we have
shown that there is a proof for p • q(X, Y). That its value is indeed p(X) ⊗ q(Y)
is concluded trivially from the induction steps.
The reverse direction for constructing the bijection is similar, again using structural induction over proofs.

4.3 From PRODUCT to a Product of Experts
The output of the PRODUCT transformation is a starting point for describing dynamic programming algorithms that perform two actions—traversing a graph, scanning a string, parsing a sentence—at the same time and in a coordinated fashion.
Exactly what “coordinated fashion” means depends on the problem, and answering
that question determines how the problem is constrained.
If we return to the running example of generalized graph reachability, the program as written has eight rules, four from Figure 9 and four from Figure 10. Two

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
15
examples of constrained product programs are given in Figures 12–14. In the first
example in Figure 12, the only change is that all but two rules have been removed
from the program in Figures 9 and 10. Whereas in the original product program
reachable1•2 (Q1 , Q2 ) corresponded to the product of the weight of the best path
from the initial state of graph one to Q1 and the weight of the best path from the
initial state of graph two to Q2 , the new program computes the best paths from
the two origins to the two destinations with the additional requirement that the
paths be the same length—the rules that were deleted allowed for the possibility of
a prefix on one path or the other.
If our intent is for the two paths to not only have the same length but to visit
exactly the same sequence of vertices, then we can further constrain the program
to only define reachable1•2 (Q1 , Q2 ) where Q1 = Q2 , as shown in Figure 13. After
adding this side condition, it is no longer necessary for reachable1•2 to have two
arguments that are always the same, so we can simply further as shown in Figure 14.
For simplicity’s sake, we will usually collapse arguments that have been forced by
equality constraints to agree.
The choice of paired predicates S is important for the final weighted logic program that PRODUCT returns and it also limits the way we can add constraints
to derive a new weighted logic program. Future research might consider a machine
learning setting for automatically deriving S from data, to minimize some cost (e.g.,
observed runtime). When PRODUCT is applied on two copies of the same weighted
logic program (concatenated together to a single program), a natural schema for
selecting paired predicates arises, in which we pair a predicate from one program
with the same predicate from the other program. This “natural” pairing leads to
the derivation of several useful, known algorithms, to which we turn in §5.

5 Examples
In this section, we give several examples of constructing weighted logic programs
as constrained products of simpler weighted logic programs.

5.1 Finite-State Algorithms
We have already encountered weighted finite-state automata (WSFAs) in §3.1. Like
WFSAs, weighted finite-state transducers (WFSTs) are a generalization of the
graph-reachability problem: in WFSAs the edges are augmented with a symbol and
represented as arc(P, Q, A), whereas in WFSTs edges are augmented with a pair of
input-output symbols and represented as arc(P, Q, A, B). Weighted finite-state machines are widely used in speech and language processing (Mohri 1997; Pereira and
Riley 1997). They are used to compactly encode many competing string hypotheses,
for example in speech recognition, translation, and morphological (word-structure)
disambiguation. Many sequence labeling and segmentation methods can also be
seen as weighted finite-state models.

16

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

goal1•2

⊕=

path1•2 (Q1 , Q1 ) ⊗ final1 (Q2 ) ⊗ final2 (Q2 ).

(31)

path1•2 (Q1 , Q2 )

⊕=

initial1 (Q1 ) ⊗ initial2 (Q2 ).

(32)

path1•2 (Q1 , Q2 )

⊕=

path1•2 (P1 , P2 ) ⊗ arc1 (P1 , Q1 , A1 ) ⊗ arc2 (P2 , Q2 , A2 ) if A1 = A2 . (33)

Fig. 15. The constrained product of two of the WFSA experts described in Figure 7.
goal

⊕=

path(Q) ⊗ final(Q).

(34)

path(Q)

⊕=

initial(Q).

(35)

path(Q)

⊕=

path(P) ⊗ arc(P, Q, A, B).

(36)

Fig. 16. The weighted logic program describing weighted finite-state transducers.
goal1•2 ⊕= path1•2 (Q1 , Q2 ) ⊗ final1 (Q1 ) ⊗ final2 (Q2 ).
path1•2 (Q1 , Q2 ) ⊕= initial1 (Q1 ) ⊗ initial2 (Q2 ).

(37)
(38)

path1•2 (Q1 , Q2 ) ⊕= path1•2 (P1 , P2 ) ⊗ arc1 (P1 , Q1 , A1 , B1 ) ⊗ arc2 (P2 , Q2 , A2 , B2 ) if B1 = A2 .

Fig. 17. The composition of two weighted finite-state transducers can be derived
by constraining the product of two weighted finite-state transducers.

Weighted finite-state automata. Our starting point for weighted finite-state automata will be the weighted logic program for WFSAs described in Figure 7, which
is usually interpreted as a probabilistic automaton in the most-probable-path semiring (i.e., h[0, 1], max, ×, 0, 1i). If the PRODUCT of that algorithm with itself is taken,
we can follow a series of steps similar to the ones described in §4.3. First, we remove
rules that would allow the two WFSAs to consider different prefixes, and then we
add a constraint to rule 33 that requires the two paths’ symbols to be identical. The
result is a WFSA describing the (weighted) intersection of the two WFSAs. The
intersection of two WFSAs is itself a WFSA, though it is a WFSA where states are
described by two terms—Q1 and Q2 in path1•2 (Q1 , Q2 )—instead of a single term.
Weighted intersection generalizes intersection and has a number of uses. For
instance, consider an FSA that is “probabilistic” but that only accepts the single
string “01” because the transitions are all deterministic and have probability 1:

0 1.0, 0

1

1.0, 1

2

If we consider the program in Figure 15 with axioms describing the above FSA and
the probabilistic FSA given in Figure 6, then the resulting program is functionally
equivalent to the weighted logic program in Figure 8 describing a WFSA specialized
to a particular string. Alternatively, if we consider the program in Figure 15 with
axioms describing the probabilistic FSA in Figure 6 and the following single-state

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
17
probabilistic FSA, the result will be a probabilistic FSA biased towards edges with
the “1” symbol and against edges with the “0” symbol.
0.1, 0

s

0.9, 1

Both of the above examples can be understood as instances of the product of
experts pattern discussed in §3.2. In the first case, the additional expert eliminates
certain possibilities by assigning zero probability to them, and in the second case
the additional expert merely modifies probabilities by preferring the symbol “1” to
the symbol “0.”
Weighted finite-state transducers. Suppose we take the PRODUCT transformation of
the WFST recognition algorithm in Figure 16 with itself and constrain the result
by removing all but the three interesting rules (as before) and requiring that B1
(the “output” along the first edge) always be equal to A2 (the “input” along the
second edge). The result is shown in Figure 17; this is the recognition algorithm
for the WFST resulting from composition of two WFSTs. Composition permits
small, understandable components to be cascaded and optionally compiled, forming
complex but efficient models of string transduction (Pereira and Riley 1997).

5.2 Context-Free Parsing
Parsing natural languages is a difficult, central problem in computational linguistics
(Manning and Schütze 1999). Consider the sentence “Alice saw Bob with binoculars.” One analysis (the most likely in the real world) is that Alice had the binoculars
and saw Bob through them. Another is that Bob had the binoculars, and Alice saw
the binocular-endowed Bob. Figure 18 shows syntactic parses into noun phrases
(NP), verb phrases (VP), etc., corresponding to these two meanings. It also shows
some of the axioms that could be used to describe a context-free grammar describing English sentences in Chomsky normal form (Hopcroft and Ullman 1979).5 A
proof corresponds to a derivation of the given sentence in a context-free grammar,
i.e., a parse tree.
Shieber et al. (1995) show that parsing with CFGs can be formalized as a logic
program, and in Goodman (1999) this framework is extended to the weighted case.
If weights are interpreted as probabilities, then the h[0, 1], max, ×, 0, 1i semiring
interpretation finds the probability of the parse with maximum probability and the
hR≥0 ∪ {∞}, +, ×, 0, 1i semiring interpretation finds the total weight of all parse
trees (a measure of the “total grammatically” of a sentence). In Figure 19, we give
the specification of the weighted CKY algorithm (Cocke and Schwartz 1970; Kasami

5

Chomsky normal form (CNF) means that the rules in the grammar are either binary with two
nonterminals or unary with a terminal. We do not allow  rules, which in general are allowed
in CNF grammars.

18

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith
S
NP

VP

NP → Alice
NP → Bob
P → with
...
S → NP VP
VP → V NP
PP → P NP
NP → NP PP
...

PP

VP
P

V NP

NP

Alice saw Bob with binoculars

V
NP
VP

NP

P

NP

PP

NP

S

unary(np, “Alice”)
unary(np, “Bob”)
unary(p, “with”)
...
binary(s, np, vp)
binary(vp, v, np)
binary(pp, p, np)
binary(np, np, pp)
...

Fig. 18. An ambiguous sentence that can be parsed two ways in English (left),
some of the Chomsky normal form rules for English grammar (center), and the
corresponding axioms (right). There would also need to be five axioms of the form
string(1, “Alice”), string(2, “saw”), etc.

goal1

⊕=

start1 (S) ⊗ length(N) ⊗ c1 (S, 0, N).

c1 (X, I − 1, I)

⊕=

unary1 (X, W) ⊗ string(I, W).

(40)

c1 (X, I, K)

⊕=

binary1 (X, Y, Z) ⊗ c1 (Y, I, J) ⊗ c1 (Z, J, K).

(41)

(39)

Fig. 19. A weighted logic program for parsing weighted context-free grammars.

1965; Younger 1967), which is a dynamic programming algorithm for parsing using
a context-free grammar in Chomsky normal form.6
Figure 19 suggestively has a subscript attached to all but the length and string
inputs. In our description of the product of experts framework in §3.2, the axioms
length and string correspond to the conditional input sentence I. The unconstrained result of the PRODUCT transformation on the combination of the rules in
Figure 19 and a second copy that has “2” subscripts is given in Figure 20. Under the most-probable-path probabilistic interpretation, the value of goal1•2 is the
probability of the given string being generated twice, once by each of the two probabilistic grammars, in each case by the most probable tree in that grammar. By
constraining Figure 20, we get the more interesting program in Figure 21 that adds
the additional requirement that the two parse trees in the two different grammars
have the same structure. In particular, in all cases the constraints I1 = I2 , J1 = J2 ,
K1 = K2 , N1 = N2 are added, so that instead of writing c1•2 (X1 , I1 , J1 , X2 , I2 , J2 ) we
just write c1•2 (X1 , X2 , I, J).
Lexicalized CFG parsing. An interesting variant of the previous rule involves lexicalized grammars, which are motivated in Figure 22. Instead of describing a gram6

Strictly speaking, the CKY parsing algorithm corresponds to a naı̈ve bottom-up evaluation
strategy for this program.

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
19

goal1•2

⊕=

length(N1 ) ⊗ length(N2 ) ⊗

c1•2 (X1 , I1 − 1, I1 , X2 , I2 − 1, I2 )

⊕=

c1•2 (X1 , I1 − 1, I1 , X2 , I2 , K2 )

⊕=

unary1 (X1 , W1 ) ⊗ string(I1 , W1 ) ⊗

c1•2 (X1 , I1 , K1 , X2 , I2 − 1, I2 )

⊕=

unary2 (X2 , W1 ) ⊗ string(I2 , W2 ) ⊗

c1•2 (X1 , I1 , K1 , X2 , I2 , K2 )

⊕=

binary1 (X1 , Y1 , Z1 ) ⊗ binary2 (X2 , Y2 , Z2 ) ⊗

(42)

start1 (S1 ) ⊗ start2 (S2 ) ⊗ c1•2 (S1 , 0, N1 , S2 , 0, N2 ).
unary1 (X1 , W1 ) ⊗ string(I1 , W1 ) ⊗

(43)

unary2 (X2 , W2 ) ⊗ string(I2 , W2 ).
(44)

binary2 (X2 , Y2 , Z2 ) ⊗ c2 (Y2 , I2 , J2 ) ⊗ c2 (Z2 , J2 , K2 ).
(45)

binary1 (X1 , Y1 , Z1 ) ⊗ c1 (Y1 , I1 , J1 ) ⊗ c1 (Z1 , J1 , K1 ).
(46)

c1•2 (Y1 , I1 , J1 , Y2 , I2 , J2 ) ⊗ c1•2 (Z1 , J1 , K1 , Z2 , K2 , J2 ).

Fig. 20. The result of the PRODUCT transformation on two copies of Figure 19.
goal1•2

⊕=

length(N) ⊗ start1 (S1 ) ⊗ start2 (S2 ) ⊗ c1•2 (S1 , S2 , 0, N) (47)

c1•2 (X1 , X2 , I − 1, I)

⊕=

unary1 (X1 , W) ⊗ unary2 (X2 , W) ⊗ string(I, W).

(48)

c1•2 (X1 , X2 , I, K)

⊕=

binary1 (X1 , Y1 , Z1 ) ⊗ binary2 (X2 , Y2 , Z2 ) ⊗

(49)

c1•2 (Y1 , Y2 , I, J) ⊗ c1•2 (Z1 , Z2 , J, K).

Fig. 21. The program in Figure 20 constrained to require internally-identical trees.
S
NP

saw

VP
PP

VP
V NP

P

NP

Alice saw Bob with binoculars

NP → Alice
P → with
S → NP VP
VP → V NP

S-saw

saw

Alice
saw
saw

Bob

VP-saw

NP-Alice

with
with binoculars

Alice saw Bob with binoculars

Alice → Alice
with → with
saw → Alice saw
saw → saw Bob

VP-saw
V-saw

NP-Bob

PP-with
P-with

NP-binoculars

Alice saw Bob with binoculars

NP-Alice → Alice
P-with → with
S-saw → NP-Alice VP-saw
VP-saw → V-saw NP-Bob

Fig. 22. On the left, the grammar previously shown. In the middle, a context-free
dependency grammar, whose derivations can be seen as parse trees (above) or a
set of dependencies (below). On the right, a lexicalized grammar. Sample rules are
given for each grammar.

mar using nonterminals denoting phrases (e.g., NP and VP), which is called a
constituent-structure grammar we can define a (context-free) dependency grammar
(Gaifman 1965) that encodes the syntax of a sentence in terms of parent-child relationships between words. In the case of the example of Figure 22, the arrows
below the sentence in the middle establish “saw” as the root of the sentence; the
word “saw” has three children (arguments and modifiers), one of which is the word
“with,” which in turn has the child “binoculars.”

20

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

A simple kind of dependency grammar is a Chomsky normal form CFG where the
nonterminal set is equivalent to the set of terminal symbols (so that the terminal
“with” corresponds to a unique nonterminal with, and so on) and where all rules
have the form P → P C, P → C P, and W → w (where P is the “parent” word,
C is the “child” word that is dependent on the parent, and W is the nonterminal
version of terminal word w).
If we encode the constituent-structure grammar in the unary1 and binary1 relations and encode a dependency grammar in the unary2 and binary2 relations,
then the product is a lexicalized grammar, like the third example from Figure 22.
In particular, it describes a lexicalized context-free grammar with a product of experts probability model (Klein and Manning 2003), because the weight given to
any production A-X → B-X C-Y is the semiring-product of the weight given to
the production A → B C and the weight given to the dependency based production X → X Y. This was an important distinction for Klein and Manning—they
were interested in factored lexicalized grammars that Figure 21 can describe. These
are only a small (but interesting) subset of all possible lexicalized grammars. Standard lexicalized CFGs assign weights directly to grammar productions of the form
A-X → B-X C-Y, not indirectly (as we do) by assigning weights to a constituentstructure and a dependency grammar. We will return to this point in §6.2 when
we consider the “axiom generalization” pattern that allows us to describe general
lexicalized CKY parsing (Eisner 1997; Eisner and Satta 1999).

Nondeterminism and rule binarization. The result of the PRODUCT transformation
shown in Figure 20 was the first time the nondeterminism inherent in lines 6-8 of the
description of the PRODUCT transformation (Figure 11) has come into play. Because
there were two c1 premises and two c2 premises, they could have been merged
in more than one way. For example, the following would have been a potential
alternative to rule 46:
c1•2 (X1 , I1 , K1 , X2 , I2 , K2 )

⊕=

binary1 (X1 , Y1 , Z1 ) ⊗ binary2 (X2 , Y2 , Z2 ) ⊗

(50)

c1•2 (Y1 , I1 , J1 , Z2 , K2 , J2 ) ⊗ c1•2 (Z1 , J1 , K1 , Y2 , I2 , J2 ).

However, this would have broken the correspondence between I1 and I2 and made
it impossible to constrain the resulting program as we did. An alternative to CKY
is the binarized variant of CKY where rule 41 is split into two rules by introducing
a new, temporary predicate (rules 51 and 52):
temp1 (X, Y, J, K)

⊕=

binary1 (X, Y, Z) ⊗ c1 (Z, J, K).

(51)

c1 (X, I, K)

⊕=

c1 (Y, I, J) ⊗ temp1 (X, Y, J, K).

(52)

In this variant, the nondeterministic choice in the PRODUCT transformation disappears. The choice that we made in pairing was consistent with the choice that is
forced in the binarized CKY program.

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
21

goal

⊕=

targetlength(M) ⊗ predict(EM−1 , EM , M + 1).

predict(EJ−1 , EJ , J + 1)

⊕=

predict(EJ−2 , EJ−1 , J) ⊗ trigram(EJ−2 , EJ−1 , EJ ). (54)

(53)

Fig. 23. A weighted logic program giving a trigram prediction model for a language,
which can be generalized to an n-gram model for any n.
goal
0

⊕=

sourcelength(N) ⊗ trans(N, []).
0

(55)

trans(I , Es)

⊕=

trans(I, []) ⊗ phrase(I, I , EJ :: Es).

(56)

trans(I0 , Es)

⊕=

trans(I0 , EJ :: Es).

(57)

Fig. 24. A weighted logic program that describes monotone decoding—translating a
phrase at a time of the input language into the output language without reordering.
goal

⊕=

sourcelength(N) ⊗ targetlength(M) ⊗

(58)

pr•tr(N, M, EM−1 , EM , M + 1).
pr•tr(I0 , J + 1, EJ−1 , EJ , Es)

⊕=

pr•tr(I, J, EJ−2 , EJ−1 , []) ⊗

(59)

trigram(EJ−2 , EJ−1 , EJ ) ⊗ phrase(I, I0 , EJ :: Es).
pr•tr(I0 , J + 1, EJ−1 , EJ , Es)

⊕=

pr•tr(I0 , J, EJ−2 , EJ−1 , EJ :: Es) ⊗

(60)

trigram(EJ−2 , EJ−1 , EJ ).

Fig. 25. Phrase translation as the constrained product of Figures 23 and 24.

5.3 Translation Algorithms
Another example of two probabilistic models that play the role of experts arises in
translation of sentences from one natural language to another. We will summarize
how the PRODUCT transformation was applied to a simple form of phrase-to-phrase
translation (Koehn et al. 2003) by Lopez (2009).
Lopez (2009) suggested a deductive view of algorithms for machine translation,
similar to the view of parsing given in Shieber et al. (1995). Lopez used the PRODUCT transformation to derive an algorithm for phrase translation from two different
factor programs, one which attempts to enforce fluency (a measure of the grammaticality of a sentence) in the translated sentence and one which attempts to
enforce adequacy (a measure of how much of the meaning of an original sentence is
preserved in the translation.)
If fluency is a measure of the grammaticality of a sentence, then it would seem
that the CKY algorithm for parsing context-free grammars would be a candidate.
While such models have been used in translation (Charniak et al. 2003), Lopez’s
example uses a simpler notion of fluency based on an n-gram language model (Manning and Schütze 1999, Chapter 6). An n-gram model assigns the probability of a
sentence to be the product of probabilities of each word following the (n − 1)-word

22

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

sequence immediately preceding it. As a concrete example, let us say that n = 3
(called a “trigram” model) and work with the program in Figure 23. If we were estimating our trigram model based on the relative frequencies of sequences in Shakespeare’s Othello, we would note that the phrase “if it” appears eight times in the
text. Three of these are from the sequence “if it be” and one is from the sequence
“if it prove,” so the axiom trigram(“if”, “it”, “be”) should have a probability
that is three times the probability given to trigram(“if”, “it”, “prove”). If we
then stared the program with the initial sentence fragment predict(“if”, “it”, 3),
we could derive predict(“it”, “be”, 4) with the aforementioned axiom and then
predict(“be”, “demanded”, 5) with the axiom trigram(“it”, “be”, “demanded”), a
sequence occurring once in the text. The result so far is a sequence “if it be demanded” that does not appear in Othello, but which perhaps sounds like it could
(which is an informal way of describing the criterion for fluency).
The weighted logic program Lopez uses to enforce adequacy is the “monotone
decoding” logic program presented in Figure 24. The program is slightly contrived
in order to interact with the PRODUCT transformation correctly. The atomic proposition trans(I, Es) refers to a particular point, I, in the source-language string
and a list Es of unprocessed words in the target language.7 Each deduction consumes a single word (EJ ) in the target language—indeed, this is the only function of
rule 57. When there are no words to remove, then either the entire source-language
string has been translated (rule 55), or else progress can continue by translating
some chunk of the source-language sentence starting from position I and ending
at position I0 as the non-empty list of target-language words EJ :: Es and applying
rule 56. This translation of a sequence of the source-language words is captured
by the premise phrase(I, I0 , Es), corresponding to the source subsequence from
position I to position I0 being translated as Es (a target-language phrase). The
meaning of phrase could be defined by a set of axioms or by a rule. In the latter case, if we enumerate all the substrings Ds in the source-language sentence as
axioms substr(I, I0 , Ds) and provide axioms ptranslate(Ds, Es) describing sourcelanguage to target-language phrase translation, then phrase(I, I0 , Es) may be defined by the following rule:
phrase(I, I0 , Es) ⊕= substr(I, I0 , Ds) ⊗ ptranslate(Ds, Es).

(61)

Note that substr might be provided as an axiom, or derived from axioms encoding
the source sentence through another inference rule.
Figure 25 displays Lopez’s phrase translation program by constraining the product of the n-gram model and monotone decoding programs. Lopez describes this for
any n, but for simplicity we continue using a trigram model (n = 3). The combined
predicate simultaneously tracks a position in the source-language sentence I and
the target-language sentence J. The word EJ that was discarded at each step in
Figure 24 is given relevance by the trigram model. The combination of these two
programs uses the monotone decoding program’s capabilities to make sure that the
7

We use a standard syntactic shorthand for lists; “[]” can be read as the constant nil and “E :: Es”
can be read as cons(E, Es).

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
23
phrase-by-phrase meaning of the source-language string D1 . . . DN is preserved in
the destination language string E1 . . . EM (adequacy) while simultaneously using
the trigram model’s capabilities to ensure that the result is a plausible sentence in
the destination language (fluency).
Our presentation of machine translation algorithms through the PRODUCT transformation is simplistic. Lopez (2009) discusses more powerful translation algorithms
that permit, for example, reordering of phrases.

6 Variations on PRODUCT
Up to this point, we have viewed our use of the PRODUCT transformation as one that
solves a problem of joint optimization: we take two logic programs that describe
structures (such as strings, paths, or trees), relate them to one another by adding
constraints, and then optimize over the two original structures simultaneously (one
instance of this is when we use weighted logic programming to describe a product
of experts.) This is a useful pattern, but it is not the only interesting use of the
fold/unfold transformation underlying the PRODUCT transformation. In this section
we consider two other variants: in the first we only optimize over one of the two
structures and fix the other one, and in the second we take the output of PRODUCT as
describing not joint optimization over two simple structures but over one complex
structure.

6.1 Fixing One of the Factor Structures
The usual use of the PRODUCT transformation is to joint optimization on two structures, but general side conditions can be used to take the additional step of fixing
one of the two structures and having the weighted logic program perform optimization on the other structure, subject to constraints imposed through the pairing.
In the setting where we consider weights to be probabilities, this is useful for
solving certain probabilistic inference problems. Using the path-sum semiring (i.e.,
hR≥0 ∪ {∞}, +, ×, 0, 1i), the result is a program calculating the marginalized quanP
tity p(x) =
y p(x, y) (where x corresponds to one program’s proof and y to
the other program’s proof). This is a useful quantity in learning; for example,
the expectation-maximization (EM) algorithm (Dempster et al. 1977) for optimizing the marginalized log-likelihood of observed structures requires calculating sufficient statistics which are based on marginal quantities. Using the mostprobable-path semiring (i.e., h[0, 1], max, ×, 0, 1i), the result is a program for solving
argmaxy p(y | x)—that is, for finding the most probable y given the fixed x.
The transformation of the constrained result of the PRODUCT transformation to a
program with one proof fixed is essentially mechanical. We consider the example of
lexicalized parsing from Figure 22. We take the constituent-structure parse as the
structure we want to fix in order optimize over the possible matching parses from the
dependency grammar. The shape of the constituent-structure parse tree can be represented by a series of new axioms that mirror the structure of the c1 (X, I, J) pred-

24

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

path1•2 (Q1 , Q2 )

⊕=

initial1•2 (Q1 , Q2 ).

(63)

path1•2 (Q1 , Q2 )

⊕=

path1•2 (P1 , P2 ) ⊗ arc1•2 (P1 , P2 , Q1 , Q2 , A1 , A2 ).

(64)

Fig. 26. Weighted finite-state transducers as the product of two weighted finitestate machines.
1
3

2
b

ax

x

a

y

4
5

(1,3)

z

ay

bx

(2,3)
(1,4)
(1,5)

by

az

(2,4)
(2,5)

bz

Fig. 27. A finite-state transducer that can be expressed as the PRODUCT of two
finite-state automata.

icate defining the constituent-structure grammar: proof1 (s, 0, 5), proof1 (np, 0, 1),
proof1 (vp, 1, 5), proof1 (vp, 1, 3), proof1 (pp, 3, 5), and so on.
Then we take the constrained PRODUCT of CKY that we used to describe lexicalized parsing (Figure 21) and, wherever there was a conclusion derived from c1 , we
add a matching side condition that references proof1 . The critical rule (49) ends
up looking like this:
c1•2 (X1 , X2 , I, K)

⊕=

binary1 (X1 , Y1 , Z1 ) ⊗ binary2 (X2 , Y2 , Z2 ) ⊗

(62)

c1•2 (Y1 , Y2 , I, J) ⊗ c1•2 (Z1 , Z2 , J, K) if proof1 (X1 , I, K).

The effect of this additional constraint is to disqualify any proof that does not match
the constituent-structure grammar which we have fixed and encoded as proof1
axioms. The idea of partially constraining CFG derivations with some bracketing
structure was explored by Pereira and Schabes (1992).

6.2 Axiom Generalization
Axiom generalization is another way of manipulating products of weighted logic
programs in a way that reveals the simple structures underlying a complex structure. Figure 26, which is intended to describe a weighted finite-state transducer, is
close to the weighted logic program in Figure 15 that describes the intersection of
two finite-state machines, but there are two differences. First, we have not forced
the two symbols to be the same; instead, we wish to interpret A1 from the first
expert as the transducer’s input symbol and A2 as the transducer’s output symbol.
Second, we have merged initial1 (Q1 ) ⊗ initial2 (Q2 ) to the single product predicate initial1•2 (Q1 , Q2 ), and likewise for arc. As a first approximation, we can just

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
25
define arc1•2 (and, similarly, initial1•2 ) by a single rule of this form:
arc1•2 (P1 , P2 , Q1 , Q2 , A1 , A2 ) ⊕= arc1 (P1 , Q1 , A1 ) ⊗ arc2 (P2 , Q2 , A2 )

(65)

An example is given in Figure 27. Two finite-state machines, one with two states
(a and b) and one with three states (x, y, and z), are shown—we are working over
the Boolean semiring, so each arc in the figure corresponds to a true-valued arc
axiom. The PRODUCT of these two experts in the manner of Figure 26 is a single
finite-state transducer with six states.
However, we can only describe a certain subset of finite-state transducers as
the direct product of finite-state machines in this way. If we consider all possible
Boolean-valued finite-state transducers with two symbols and one state, we have
16 possible transducers, but only 10 that can be “factored” as two independent
finite-state machines, such as these three:
0

0
1

(0,1)

1

1

(1,1)

0

0

(0,1)

1

1

(0,0)
(1,0)

(1,1)
(0,1)

Six others, like the NOT transducer that outputs 1 given the input 0 and outputs 0
given the input 1, cannot be represented as the product of two FSMs.
In many settings, limiting ourselves to the “factorable” finite-state transducers (or
lexicalized grammars) can have conceptual or computational advantages. When this
does not suffice, we can perform axiom generalization, which amounts to removing
the requirement of Eq. 65 that the value of atomic propositions of the form arc1•2
be the product of an atomic proposition of the form arc1 and an atomic proposition
of the form arc2 . If we directly define axioms of the form arc1•2 , we can describe
transducers in their full generality.
This represents a new way of thinking about the PRODUCT transformation. Thus
far, we have considered the result of the PRODUCT transformation as a way of
describing programs that work over two different structures. Axiom generalization
suggests that we can consider the PRODUCT transformation as a way of taking
two programs that work over individual structures and deriving a new program
that works over a single more complicated structure that, in special cases, can be
factored into two different structures. This is particularly relevant in the area of
lexicalized grammars and parsing where the general, more complicated structure is
what came first and the factored models which we have considered thus far arose
later as special cases.
Parsing algorithms and the PRODUCT transformation. Many parsing algorithms can
be derived by using the PRODUCT transformation as a way of deriving programs that
do not neatly factor into two parts. Lexicalized parsing is a simple example; Figure 28 derives a lexicalized parser by performing axiom generalization on Figure 21.
The grammar production “P-with → with” can be represented by including the axiom unary1•2 (p, “with”), and the binary production S-saw → NP-Alice VP-saw
can be represented by the axiom binary1•2 (s, “saw”, np, “alice”, vp, “saw”).
Synchronous grammars are another instance in which the axiom generalization

26

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

goal1•2 ⊕= length(N) ⊗ start(S) ⊗ c1•2 (S, W, 0, N).
c1•2 (X, W, I − 1, I) ⊕= unary1•2 (X, W) ⊗ string(I, W).

(66)
(67)

c1•2 (X, W, I, K) ⊕= binary1•2 (X, W, Y, W1 , Z, W2 ) ⊗ c1•2 (Y, W1 , I, J) ⊗ c1•2 (Z, W2 , J, K).(68)

Fig. 28. A algorithm for CKY over a general lexicalized grammar derived from
Figure 21 by axiom generalization.

goal

⊕=

length(N) ⊗ start(S) ⊗ c(S, 0, N).

(69)

c(X, I, I)

⊕=

unary(X, ) ⊗ pos(I).

(70)

c(X, I − 1, I)

⊕=

unary(X, W) ⊗ string(I, W).

(71)

c(X, I, K)

⊕=

binary(X, Y, Z) ⊗ c(Y, I, J) ⊗ c(Z, J, K).

(72)

Fig. 29. A variant of CKY that handles grammar productions of the form X → .
goal1•2 ⊕= length1 (M) ⊗ length2 (N) ⊗ start1•2 (S) ⊗

(73)

c1•2 (S, 0, N, 0, M).
c1•2 (X, I − 1, I, J, J) ⊕= unary1•2 (X, W1 , ) ⊗ string1 (I, W1 ) ⊗ pos2 (J).

(74)

c1•2 (X, I, I, J − 1, J) ⊕= unary1•2 (X, , W2 ) ⊗ pos1 (I) ⊗ string2 (J, W2 ).

(75)

c1•2 (X, I − 1, I, J − 1, J) ⊕= unary1•2 (X, W1 , W2 ) ⊗ string1 (I, W1 ) ⊗ string2 (J, W2 ).(76)
c1•2 (X1 , I1 , K1 , I2 , K2 ) ⊕= binary1•2 (X, Y, Z) ⊗

(77)

c1•2 (Y, I1 , J1 , I2 , J2 ) ⊗ c1•2 (Z, J1 , K1 , J2 , K2 ).

Fig. 30. A simple transduction grammar derived from Figure 29.
c1•2 (X1 , I1 , K1 , I2 , K2 ) ⊕= inversion1•2 (X, Y, Z) ⊗

(78)

c1•2 (Y, I1 , J1 , J2 , K2 ) ⊗ c1•2 (Z, J1 , K1 , I2 , J2 ).

Fig. 31. By adding to Figure 30 these rule corresponding to the other way that
the c1 and c2 antecedents may be merged in the PRODUCT transformation, we can
describe an inversion transduction grammar.

view is interesting. A synchronous grammar can be thought of as parsing two different sentences in two different languages with two different grammars using a single
parse tree. For example, if X → YZ is a grammar production in one language and
A → BC is a grammar production in another language, then X-A → Y-B Z-C is
a possible grammar production in the synchronous grammar.
A transduction grammar (Wu 1997), is a synchronous grammar which generates
two isomorphic derivations with a trivial alignment between the nodes of those two
derivations. We can describe a parser for a transduction grammar with the program

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
27
in Figure 30. Synchronous grammars need to be able to deal with situations in which
a word in one language does not appear in the matching sentence in the other
language; this is done by starting from the enriched CKY program in Figure 29
that can handle grammar productions of the form X → .
In practice, transduction grammars do a bad job of aligning two sentences in
different natural languages that are translations of each other, because it is often the
case that two parts of a pair of sentences need to be in opposite positions relative to
one another—in language one, the verb phrase might precede a prepositional phrase,
and in language two, the corresponding verb phrase might follow the corresponding
prepositional phrase. An inversion transduction grammar describes an alternate
form of grammar production, which Wu (1997) writes as X → hYZi. This grammar
production declares that if A1 and A2 simultaneously parse as Y in languages one
and two (respectively) and B1 and B2 simultaneously parse as Z in languages one
and two (respectively), then A1 B1 and B2 A2 simultaneously parse as Z.
Somewhat surprisingly, this inversion production rule can be described using the
alternate allowable way of merging the premises when the PRODUCT transformation
is performed on two copies of the CKY algorithm, as discussed in §5.2 (see rule 50).
By adding this alternate form as given in Figure 31, we can describe the algorithm
for parsing with inversion transduction grammars described by Wu (1997).
7 The Entropy Semiring and Kullback-Leibler Divergence
An important construct in information theory and machine learning is the KullbackLeibler (KL) divergence (Kullback and Leibler 1951). KL divergence is a function
of two probability distributions over the same event space. It measures their dissimilarity, though it is not, strictly speaking, a distance (it is not symmetric). For
two distributions p and q for random variable X ranging over events x ∈ X , KL
divergence is defined as
X
p(X = x)
(79)
KL(pkq) =
p(X = x) log
q(X = x)
x∈X
X
X
=
p(X = x) log p(X = x) −
p(X = x) log q(X = x) (80)
x∈X

|

x∈X

{z

−H(p)

}|

{z

CE(pkq)

}

where H(p) denotes the Shannon entropy of the distribution p (Shannon 1948), a
measure of uncertainty, and CE(pkq) denotes the cross-entropy between p and q.8
A full discussion of these information-theoretic quantities is out of scope for this
paper; we note that they are widely used in statistical machine learning (Koller
8

In brief, the Shannon entropy of distribution p is the expected number of bits required to send
a message drawn according to p under an optimal coding scheme. Cross-entropy is the average
number of bits required to encode a message in the optimal coding scheme for q when messages
are actually distributed according to p. Hence KL(pkq) = CE(pkq)−H(p) is the average number
of extra bits required when the true distribution of messages is p but the coding scheme is based
on q. Note that KL(pkp) = 0. If there is an event x ∈ X such that p(x) > 0 and q(x) = 0, then
KL(pkq) = +∞.

28

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

and Friedman 2009). In this section, we first show how the entropy of p(P ), with
P ranging over proofs of goal (the axioms corresponding to random variables A
and I are suppressed here, for clarity), can be calculated using a weighted logic
program, following Hwa (2004). We then describe a generalization of a result of
Cortes et al. (2006) to show how to use PRODUCT to produce a weighted logic
program for calculating the KL divergence between the two distributions induced
by the WLPs.
7.1 Generalized Entropy Semiring
The domain of the generalized entropy semiring is (R ∪ {+∞, −∞})3 . The multiplication and addition operations are defined as follows:
hx1 , y1 , z1 i ⊕ hx2 , y2 , z2 i = hx1 + x2 , y1 + y2 , z1 + z2 i

(81)

hx1 , y1 , z1 i ⊗ hx2 , y2 , z2 i = hx1 x2 , x1 y2 + x2 y1 , z1 z2 i

(82)

These operations have the required closure, associativity, and commutativity
properties previously discussed for semirings. See Cortes et al. (2006) for a proof
which can be extended trivially to our generalized semiring.
Suppose we have a weighted logic program such that the path-sum (in the hR≥0 ∪
{∞}, +, ×, 0, 1i semiring) is 1 (i.e., the value of the goal theorem is 1). If we map
the weights of all axioms in the original program to new values in the generalized
entropy semiring, we can use the new semiring to calculate the Shannon entropy of
the distribution over proofs of goal:
X
−
p(P = proof ) log p(P = proof )
(83)
proof

where x ranges over proofs of goal. The mapping is simply w 7→ hw, −w log w, 0i.
(The third element of the semiring value is not needed here.) If we solve the new
weighted logic program and achieve value hw0 , h0 , 0i for the goal theorem, then
under our assumption that w0 = 1 (the value of goal in the original program in the
real semiring), h0 is the entropy of the distribution over the proof random variable
(given the axioms and goal). The formal result is given as a corollary in §7.2.
This semiring can be used, for example, with the CKY algorithm from Figure 19. It makes the derivation of the tree entropy for context-free grammars (i.e.,
the entropy over the context-free derivations for an ambiguous string) automatic,
and obviates the design of a specific algorithm for computing the tree entropy for
probabilistic context-free grammars, as described in Hwa (2004). With the CKY
algorithm, a proof proof in Eq. 83 represents a derivation in the grammar. Similarly, a weighted logic program describing a finite-state transducer (Figure 16) can
be used to compute the entropy of hidden sequences for hidden Markov models as
described by Hernando et al. (2005).
We now relax the assumption that the sum of all proof scores is 1. Suppose that
the value of the goal theorem in the generalized entropy semiring is (w0 , h0 , 0),
with w0 6= 1. In this case, h0 is not the entropy of a proper probability distribution.

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
29
We can renormalize the scores of the proofs, u(proof ), by dividing by w0 , treating
them as a proper conditional distribution (conditioning on the truth of the goal
u(proof )
theorem); then the entropy of this conditional distribution,
, is
w0
X u(proof )
u(proof )
log
(84)
−
w0
w0
proof


1  X
= 0 −
u(proof )(log u(proof ) − log w0 )
w
proof


X
1  0
1
h0
= 0 h + (log w0 )
u(proof ) = 0 (h0 + w0 log w0 ) = 0 + log w0
w
w
w
proof

Therefore, whenever we can use weighted logic programming (in the real semiring)
to calculate sums of proof scores, we can use the generalized entropy semiring to
find the Shannon entropy of the (possibly renormalized) distribution over proofs.
The renormalization uses w0 and h0 , two quantities that are calculated directly
when we use the generalized entropy semiring.

7.2 KL Divergence Between Proof Distributions and PRODUCT
Cortes et al. (2006) showed how to compute the KL divergence (also called relative
entropy) between two distributions over strings defined by probabilistic FSA, using
a construct similar to our generalized entropy semiring. We generalize that result
to KL divergence over two proof distributions p(P ) and q(P ) given by a weighted
logic program P. We assume in this discussion that the set of axioms with non-zero
weights are identical under p and under q; the general setting where this does not
hold is correctly handled, using a log 0 = −∞ and 0 log a = 0 for all a > 0.
We abuse notation slightly and use p and q to denote the values of axioms,
theorems, and proofs in the real semiring weighted logic programs used to calculate
the sum of proof-scores for goal under axioms weighted according to p and q. Let
Proofs(t) denote the set of logical proofs of a theorem t, and for x ∈ Proofs(t), let
p(t)—respectively, q(t)—denote the score of the proof x:
X
p(t) =
p(x)
(85)
x∈Proofs(t)

q(t)

X

=

q(x)

(86)

x∈Proofs(t)

(87)
We seek the KL divergence:
KL(pkq) =

X
x∈Proofs(goal)

p(x) log

p(x)
q(x)

(88)

In order to accomplish this calculation, we will first map the weights of axioms

30

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

under p and q into the generalized entropy semiring as follows, for any axiom a:
hp(a), q(a)i 7→ hp(a), p(a) log q(a), q(a)i

(89)

For a theorem t, let
X

R(t) =

p(x) log q(x)

(90)

x∈Proofs(t)

Theorem 2
Solving P in the generalized entropy semiring with weights defined as above results
in goal having value hp(goal), R(goal), q(goal)i.
Proof: We will treat the weighted logic program as a set of equations with all lefthand-side variables grounded. We will use upper-case to refer to free variables (e.g.,
Z = hZ1 , . . .i) and lower-case to refer to grounded values (e.g., z = hz1 , . . .i). The
range of values that variables Z can get is denoted by Rng(Z). The weighted logic
program can be seen as a set of equations:
M
M
c(w) =
ai (w0 , z) ⊗ bi (w00 , z) (91)
[c(w) ⊕= ai (w0 ,Z)⊗bi (w00 ,Z)]∈P,w0 ⊆w,w00 ⊆w z∈Rng(Z)

(Note that any of w, w0 , w00 , and z may be empty.)
We now show that the value achieved for c(w) when solving in the semiring is
X
hp(c(w)),
p(x) log q(x), q(c(w))i
(92)
x∈Proofs(c(w))

where Proofs(c(w)) denotes the set of proofs for c(w). We will show that the
solution of Equations 91 is the value in Equation 92 for c(w).
For the first and third coordinates, this equality follows naturally because of the
definition of the generalized entropy semiring: the first and third coordinates are
equivalent to the non-negative real semiring used for summing over proof scores
under the two value assignments p and q, respectively.
Consider a particular ⊕-addend to the value of c(w),
ai (w0 , z) ⊗ bi (w00 , z)

(93)

0

0

0

= hp(ai (w , z)), R(ai (w , z)), q(ai (w , z))i
⊗ hp(bi (w00 , z)), R(bi (w00 , z)), q(bi (w00 , z))i
* p(a (w0 , z))p(b (w00 , z)),
i

=

i

p(ai (w0 , z))R(bi (w00 , z)) + p(bi (w00 , z))R(ai (w0 , z)),
q(ai (w0 , z)))q(bi (w00 , z))

(94)
+
(95)

Consider the second coordinate.
p(ai (w0 , z))R(bi (w00 , z)) + p(bi (w00 , z))R(ai (w0 , z))


X
p(x) log q(x)
= p(ai (w0 , z))
x∈Proofs(bi (w00 ,z))

(96)

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
31


X
+ p(bi (w00 , z))
p(x0 ) log q(x0 )
(97)
x0 ∈Proofs(ai (w0 ,z))


=


X

X

p(x0 )


x0 ∈Proofs(ai (w0 ,z))

p(x) log q(x)

x∈Proofs(bi (w00 ,z))




X

+

p(x)

x∈Proofs(bi (w00 ,z))

=

X
x∈Proofs(bi

X

(98)

x0 ∈Proofs(ai (w0 ,z))

X
(w00 ,z))

p(x0 ) log q(x0 )

p(x)p(x0 ) log(q(x)q(x0 ))

(99)

x0 ∈Proofs(ai (w0 ,z))

Embedding the above in a ⊕-summation over z and a ⊕-summation over inference
rule instantiations gives a ⊕-summation over proofs of c(w),
X
p(x) log q(x)
(100)
x∈Proofs(c(w))

which is R(c(w)) as desired.

Denote by (p̄, R̄, q̄) the value for goal in the generalized entropy semiring as
discussed above, i.e., p̄ = p(goal), R̄ = R(goal), and q̄ = q(goal). If we wish to
renormalize p by p̄ and q by q̄ to give proper distributions over proofs of goal (given
axioms and goal), then


1 1
R̄
CE
p q =
− log q̄
(101)
p̄ q̄
p̄
Noting that −H(p) = CE(pkp),


1 1
p q = CE(pkp) − CE(pkq)
KL
p̄ q̄

(102)

we can solve for the KL divergence of two (possibly renormalized) distributions
p and q using the above results. Alternatively, if the generalized KL divergence
between unnormalized distributions is preferred (O’Sullivan 1998), note that (in
the notation of the above):


X
p(x)
p(x) log
− p(x) + q(x) = R̄ − p̄ + q̄
(103)
q(x)
x∈Proofs(goal)

Cortes et al. describe how to compute KL divergence between two probabilistic
finite-state automata with a single path per string (“unambiguous” automata).
The authors make use of finite-state intersection (discussed above in §5.1). This
suggests an analogous interpretation of the PRODUCT transformation for computing
KL divergence between two weighted logic programs.
Let P and Q be two instances of a weighted logic program, with possibly different
different axiom weights. Assume we set the values of the axioms of P (ranging over
a) to be hp(a), 0, 1i, and for Q we set them to h1, log q(a), q(a)i. If we take a PRODUCT of P and Q, using the “natural” pairing, then we end up with a program that
computes hp(goal), R(goal), q(goal)i in the generalized entropy semiring, where

32

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

goal

⊕=

path(P, Q) ⊗ final(Q).

path(null, Q)

⊕=

initial(Q).

(105)

path(P0 , Q)

⊕=

path(P, P0 ) ⊗ biarc(P, P0 , Q, A, B).

(106)

(104)

Fig. 32. Weighted finite-state transducer where arriving at a certain state depends
on the last two states. null serves as a place-holder for the non-state prior to the
initial state.
goal1•2 ⊕= path1•2 (P, Q) ⊗ final1 (Q) ⊗ final2 (Q).
path1•2 (null, Q) ⊕= initial1 (Q) ⊗ initial2 (Q).
path1•2 (P0 , Q) ⊕= path1•2 (P, P0 ) ⊗ arc1 (P0 , Q, A, B) ⊗ biarc2 (P, P0 , Q, A, B)

(107)
(108)
(109)

Fig. 33. The PRODUCT program of Figure 16 with Figure 32, with constraints that
match proofs according to states and emissions sequences.

R(·) is specified in Eq. 90. These quantities can be used to compute KL divergence
as specified in Eq. 102. This is a direct result of Theorem 2.
7.3 KL Divergence and Projections
We can use PRODUCT to calculate KL divergence between proof distributions even
when P and Q are not two instances of the same program. We consider cases where
the proofs of P and the proofs of Q have a shared semantics, that is, each proof of
either P or Q maps to an event in some “interpretation space.”
As an example, consider the WLP in Figure 16 describing a weighted finite-state
transducer. In a more general formulation, where each state depends on the previous
N states visited, rather than just the single most recent state. This modification is
reflected in Figure 32 for N = 2. The axiom biarc(P0 , Q, P, A, B) is to be interpreted
as: “if the last two states were Q and P0 , transfer to state P while reading symbol
A and emitting the symbol B.” Since the two programs have different axioms, the
spaces of their respective proofs are different. However, both programs have identical
semantics to a proof: a proof (in either program) corresponds to a sequence of states
that the transducers go through together with the reading of a symbol and the
emission of another symbol.
Running PRODUCT on the WFST in Figure 16 (we call it P) and the WFST in
Figure 32 (we call it Q) with a particular pairing and constraints (such that the
paths are identical) yields the program in Figure 33. If we let the axioms a in P
have the values hp(a), 0, 1i and the axioms a in Q the values h1, log q(a), q(a)i, then
the resulting PRODUCT program in Figure 33, as implied by Theorem 2, calculates
the KL divergence between two distributions over the set of state paths: one which
is defined using a finite-state transducer with N = 1 and the other with N = 2.
We now generalize this idea for two different programs P and Q. We assume

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
33
that PRODUCT is applied in such a way that axioms from P are paired only with
axioms from Q, and vice versa. Further, each proof in the PRODUCT program must
decompose into exactly one proof in P and one proof in Q.9 For a proof in the
PRODUCT program, y, we define πP (y) (πQ (y)) to be the projection of y to a proof
in P (Q). The “projection” of a proof is a separation of the proof which uses coupled
theorems and axioms into theorems and axioms of only one of the programs. For
example, projecting a proof y in the product program in Figure 33 yields two proofs:
πP (y) describes a sequence of transitions through the transducer with N = 1 and
πQ (y) describes a sequence of transitions through the transducer with N = 2; yet
both proofs correspond to the same sequence of states.
In the generalized entropy semiring, we set the values of the axioms of P to
be hp(a), 0, 1i, and for Q we set them to h1, log q(a), q(a)i. The PRODUCT program
computes hp(goal1 ), R(goal1·2 ), q(goal2 )i. This time, the summation in R(goal1·2 )
is over proofs which are implicitly paired:
R(goal1·2 )

=

X

p(πP (y)) log q(πQ (y))

(110)

y∈Proofs(goal1·2 )

The quantities p(goal1 ), R(goal1·2 ), and q(goal2 ) can be used as before to compute the KL divergence between the distributions over the shared “interpretation
space” of the proofs in the two programs. This technique is only correct when interpretations are in a one-to-one correspondence with the proofs in P and with the
proofs in Q, and PRODUCT is applied so that equivalently-interpretable proofs in
the two programs are paired.
We note that in the general case, the problem of computing KL divergence between two arbitrary distributions is hard. For example, with Markov networks, there
are restrictions, which resemble the restrictions we pose, of clique decomposition
(Koller and Friedman 2009).

8 Conclusion
We have described a framework for dynamic programming algorithms whose solutions correspond to proof values in two constrained weighted logic programs. Our
framework includes a program transformation, PRODUCT, which combines the two
weighted logic programs that compute over two structures into a single weighted
logic program for a joint proof. Appropriate constraints, encoded intuitively as variable unification or side conditions in the weighted logic program, are then added
manually. The framework naturally captures and permits generalization of many
existing algorithms. We have shown how variations on the the program transformation enable to include a larger set of algorithms as the result of the program
transformation. We have concluded by showing how the program transformation

9

Note that these constraints are satisfied in the case of two identical programs with the “natural”
pairing, as in §7.2.

34

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

can be used to interpret the computation of Kullback-Leibler divergence for two
weighted logic programs which are defined over an identical interpretation space.
Acknowledgments
The authors acknowledge helpful comments from the two anonymous reviewers, Jason Eisner, Rebecca Hwa, Adam Lopez, Alberto Pettorossi, Frank Pfenning, Sylvia
Rebholz and David Smith. This research was supported by an NSF graduate fellowship to the second author and NSF grant IIS-0713265 and an IBM faculty award
to the third author.
References
Charniak, E., Knight, K., and Yamada, K. 2003. Syntax-based language models for
machine translation. In Proc. of MT Summit.
Chiang, D. 2007. Hierarchical phrase-based translation. Computational Linguistics 32, 2,
201–228.
Cocke, J. and Schwartz, J. T. 1970. Programming languages and their compilers:
Preliminary notes. Tech. rep., Courant Institute of Mathematical Sciences, New York
University.
Cohen, S. B. and Smith, N. A. 2007. Joint morphological and syntactic disambiguation.
In Proc. of EMNLP-CoNLL.
Cortes, C., Mohri, M., Rastogi, A., and Riley, M. D. 2006. Efficient computation of
the relative entropy of probabilistic automata. LATIN 2006: Theoretical Informatics,
323–336.
Dempster, A., Laird, N., and Rubin, D. 1977. Maximum likelihood estimation from
incomplete data via the EM algorithm. Journal of the Royal Statistical Society B 39,
1–38.
Durbin, R., Eddy, S., Krogh, A., and Mitchison, G. 1998. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.
Eisner, J. 1997. Bilexical grammars and a cubic-time probabilistic parser. In Proc. of
IWPT.
Eisner, J. and Blatz, J. 2007. Program transformations for optimization of parsing
algorithms and other weighted logic programs. In Proc. of Formal Grammar.
Eisner, J., Goldlust, E., and Smith, N. A. 2005. Compiling Comp Ling: Practical
weighted dynamic programming and the Dyna language. In Proc. of HLT-EMNLP.
Eisner, J. and Satta, G. 1999. Efficient parsing for bilexical context-free grammars and
head automaton grammars. In Proc. of ACL.
Felzenszwalb, P. F. and McAllester, D. 2007. The generalized A∗ architecture.
Journal of Artificial Intelligence Research 29, 153–190.
Gaifman, H. 1965. Dependency systems and phrase-structure systems. Information and
Control 8.
Goodman, J. 1999. Semiring parsing. Computational Linguistics 25, 4, 573–605.
Hernando, D., Crespi, V., and Cybenko, G. 2005. Efficient computation of the hidden Markov model entropy for a given observation sequence. IEEE Transactions on
Information Theory 51, 7, 2681–2685.
Hinton, G. E. 2002. Training products of experts by minimizing contrastive divergence.
Neural Computation 14, 1771–1800.

Products of Weighted Logic ProgramsTo appear in Theory and Practice of Logic Programming (TPLP).
35
Hopcroft, J. E. and Ullman, J. D. 1979. Introduction to Automata Theory, Languages,
and Computation. Addison-Wesley.
Huang, L. and Chiang, D. 2005. Better k-best parsing. In Proc. of IWPT.
Hwa, R. 2004. Sample selection for statistical parsing. Computational Linguistics 30, 3.
Kasami, T. 1965. An efficient recognition and syntax-analysis algorithm for context-free
languages. Tech. Rep. AFCRL-65-758, Air Force Cambridge Research Lab.
Klein, D. and Manning, C. D. 2003. Fast exact inference with a factored model for
natural language parsing. In Advances in NIPS 15.
Klein, D. and Manning, C. D. 2004. Parsing and hypergraphs. New developments in
parsing technology, 351–372.
Koehn, P., Och, F. J., and Marcu, D. 2003. Statistical phrase-based translation. In
Proc. of HLT-NAACL. 127–133.
Koller, D. and Friedman, N. 2009. Probabilistic Graphical Models: Principles and
Techniques. The MIT Press.
Kullback, S. and Leibler, R. A. 1951. On information and sufficiency. Annals of
Mathematical Statistics 22, 79–86.
Liang, P., Klein, D., and Jordan, M. 2008. Agreement-based learning. In Advances in
Neural Information Processing Systems 20, J. Platt, D. Koller, Y. Singer, and S. Roweis,
Eds. MIT Press, Cambridge, MA, 913–920.
Lopez, A. 2009. Translation as weighted deduction. In Proc. of EACL.
Manning, C. and Schütze, H. 1999. Foundations of Statistical Natural Language Processing. MIT Press.
McAllester, D. 1999. On the complexity analysis of static analyses. In Proc. of Static
Analysis Symposium.
Mohri, M. 1997. Finite-state transducers in language and speech processing. Computational Linguistics 23, 2, 269–311.
O’Sullivan, J. A. 1998. Alternating minimization algorithms: from Blahut-Armijo to
Expectation-Maximization. In Codes, Curves, and Signals: Common Threads in Communications, A. Vardy, Ed. Kluwer, 173–192.
Pereira, F. C. N. and Riley, M. D. 1997. Speech recognition by composition of
weighted finite automata. In Finite-State Language Processing, E. Roche and Y. Schabes, Eds. MIT Press, 431–453.
Pereira, F. C. N. and Schabes, Y. 1992. Inside-outside reestimation from partially
bracketed corpora. In Proc. of ACL. 128–135.
Pettorossi, A. 1999. Synthesis and transformation of logic programs using unfold/fold
proofs. The Journal of Logic Programming 41, 2-3 (December), 197–230.
Pettorossi, A. and Proietti, M. 1994. Transformation of logic programs: Foundations
and techniques. J. Log. Program. 19, 261–320.
Shannon, C. 1948. A mathematical theory of communication. Bell System Technical
Journal 27, 379–423.
Shieber, S. M., Schabes, Y., and Pereira, F. C. N. 1995. Principles and implementation of deductive parsing. Journal of Logic Programming 24, 1–2, 3–36.
Sikkel, K. 1997. Parsing Schemata. Springer-Verlag.
Smith, A., Cohn, T., and Osborne, M. 2005. Logarithmic opinion pools for conditional
random fields. In Proc. of ACL.
Smith, D. A. and Smith, N. A. 2004. Bilingual parsing with factored estimation: Using
English to parse Korean. In Proc. of EMNLP.
Sutton, C. and McCallum, A. 2005. Piecewise training of undirected models. In Proc.
of UAI.

36

Shay B. Cohen, Robert J. Simmons, and Noah A. Smith

Tarjan, R. E. 1981. A unified approach to path problems. Journal of the ACM 28, 3,
577–93.
Wu, D. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel
corpora. Computational Linguistics 23, 3, 377–404.
Younger, D. H. 1967. Recognition and parsing of context-free languages in time n3 .
Information and Control 10, 2.

