We explore variants of belief state compression which is an intuitive, weak form of knowledge base size reduction. It di↵ers from previous approaches in at least three aspects. First, it takes its objects to be support-structured sets of unconstrained, rather than flat sets of syntactically-constrained, logical formulas. Second, classical notions of minimality and redundancy are replaced by weaker, resource-bounded alternatives based on the support structure. Third, in “lossy” variants of compression, the compressed knowledge base logically implies only a practically-relevant subset of the original knowledge base.
maintenance. One obvious, and long-recognized, such factor is the sheer size of
the knowledge base [
as is common, to construe formulas of L as representing (possible) beliefs of a cognitive agent. Henceforth, we refer to this agent as A.
Definition 1. A belief state is a triple S = hK, B, i where K ⇢ B ✓ K and : K ! 22B; , such that
1. 2 Cn(s), for every s 2 ( ); 2. /2 s, for every s 2 ( ); and 3. ( ) 6= ; , whenever 2 K B.
The size |S| of S is defined as |K| + P 2 K Ps2 ( ) |s|.
Intuitively, K is the set of all (explicit) beliefs of A and B is a distinguished subset of base beliefs. Members of B are those formulas which A came to believe by some means other than logical reasoning. Typically, they are formulas which result from sensory input or from communication with other agents. We often refer to members of B as hypotheses. Formulas in K B are believed only as a result of A’s doing some reasoning. Hence, provides, to each member of K a set of supports. Each support of a formula is a set of hypotheses that were used to derive .
Definition 2. Let S = hK, B, i be a belief state. A compression S0 of S is a belief state hK0, B0, 0i with 1. K0 ✓ K; 2. for every 3. |S0| < |S|.
2 K0, 0( ) ✓
( ); and
Definition 3. If S is a belief state and H ✓ L, we say that 2 K is supported by H in S if (i) 2 H or (ii) there is some s 2 ( ) with every 2 s supported by H in S. Hence, a compression S0 of S is lossless if every 2 B is supported by B0 in S, otherwise it is lossy. If S0 is lossless, then it is irredundant (respectively, minimal) if there is no lossless compression S00 of S with B00 ⇢ B0 (respectively, |S00| < |S0|).
A K-only compression of belief state S is a compression S0 with B0 = B and 0 = |K0 . Such compressions are clearly lossless. An extreme case of K-only compression is the compression SK0 = hB, B, Bi which only retains hypotheses and gives up all derived formulas. This compression operator can be eciently implemented (in time O(|S|)) and may result in significant size reduction if agent A is an introspective agent whose set of beliefs is dominated by inferred beliefs rather than beliefs with independent standing. This, of course, may come with a heavy price. For it is possible that beliefs in B are mostly useless and the given up derived beliefs are the interesting ones. Although, since SK0 is lossless, all retracted beliefs may be re-derived, this will still be on the expense of A’s (possibly valuable) time. 4
to follow of B-compression relies heavily on the notion of a base-support graph. Henceforth, let ⌃ (S) = [ ' 2 K (' ), where S is a belief state.
Definition 4. For a K0-compressed belief state S = hB, B, i, a base-support graph is a bipartite graph G(S) = (V1, V2, E), where – V1 = B – V2 = ⌃ (S) – for n1 2 V1 and n2 2 V2, 1. (n1, n2) 2 E if and only if n1 2 n2 2. (n2, n1) 2 E if and only if n2 2 (n1)
in V2 as support nodes (or just supports). Figure 1 is an example of the basesupport graph G(S), with S = h{1, 2, 3}, {1, 2, 3}, i where (1) = {{2}}, (2) = {{1}}, and (3) = {{1, 2}}. (Hyp nodes are circular and generically denoted by numerals while support nodes are rectangular and denoted by letters.)
Observation 1 Let G(S) = (V1, V2, E) be a base-support graph. 1. For every n 2 V2, deg (n) > 0 and deg+(n) > 0. 2. For every n1, n2 2 V2, if {n|(n, n1) 2 E} = {n|(n, n2) 2 E}, then n1 = n2. 3. E is asymmetric. (That is, if (n1, n2) 2 E, then (n2, n1) 2 / E.) 4.1
Trimming
piece of notation. If G = (V1, V2, E) is a base-support graph with N ✓ V1, then G N is the sub-graph of G induced by (V1 N ) [ (V2 { n 2 V2| if (n0, n) 2 E or (n, n0) 2 E, then n0 2 N }). Simply, G N is the sub-graph of G with N removed from V1 and with every support node that has edges only to nodes in N or edges only from nodes in N removed from V2 (to save the first clause of Observation
on algorithm GTrim (see Algorithm 1) which operates on a directed bipartite graph (V1, V2, E) with deg (n) 6= 0, for every n 2 V2. (Possibly a base-support graph.)
end return G Function GTrim(G): if there is n 2 V1 with deg+(n) = 0 and deg (n) 6= 0 then return GTrim (G { n})
the base-support graph of some K0-compressed belief state S and GTrim(G) = (V1, V2, E), then the trimming of S, denoted T r(S) is the structure hV1, V2, i, where, for every n1 2 V1 and every n2 2 V2 with (n2, n1) 2 E, n2 2 (n1). Corollary 1 If S is a K0-compressed belief state, then T r(S) is a belief state. Moreover, if S 6= T r(S), then T r(S) is a lossless compression of S.
Trimmed base-support graphs have an interesting property which we prove next. First, a piece of notation. For a graph G, we say that a path P in G ends (respectively, begins) with a cycle if P = n1, . . . , nk with ni = nk (respectively, ni = n1) for some 1 i < k (respectively, 1 < i k). In the sequel, a node n in graph G is G+-trapped (respectively, G -trapped) if (i) deg (n) = 0 (respectively, deg+(n) = 0) or (ii) n is on a path in G that ends (respectively, begins) with a cycle. If n is G+-trapped and G -trapped, then it is G-trapped. Proposition 1 If G = (V1, V2, E) is a directed bipartite graph with deg (n) 6= 0, for every n 2 V2, then GTrim(G) is a graph G0 = (V10, V20, E0) where every n 2 V 0 1 is G0+-trapped.
Proof. We prove the proposition by induction on |V1|.
Base Case. If |V1| = 0, then, trivially, no nodes satisfy the condition of the ifstatement and GTrim(G) = G. Hence, |V10| = 0 and the proposition trivially holds.
Induction Hypothesis. If G = (V1, V2, E) is a directed bipartite graph with |V1| = k, for some k 2 N, and deg (n) 6= 0, for every n 2 V2, then GTrim(G) is a graph G0 = (V10, V20, E0) where every n 2 V10 is G0+-trapped. Induction Step. Suppose that G = (V1, V2, E) is a directed bipartite graph with |V1| = k + 1 and deg (n) 6= 0, for every n 2 V2. We consider two cases. 1. There is a node n 2 V1 with deg 6= 0 and deg+ = 0. Thus, GTrim(G) = GTrim(G { n}) = G0. By construction, G { n} contains exactly k hyp nodes. Hence, by the induction hypothesis, every node in V10 is G0+trapped. 2. There is no node n 2 V1 with deg 6= 0 and deg+ = 0. Hence, GTrim(G) = G. Consider an arbitrary n 2 V1. If deg (n) = 0, then n is G+-trapped. Otherwise, deg (n) 6= 0 and deg+(n) 6= 0. Thus, there must be a path P that starts with n and on which every node n0 has deg (n0) 6= 0 and deg+(n0) 6= 0. Since G is finite, it follows by the pigeonhole principle that there is at least one node r which appears on P at least twice. Hence, the sub-path of P which ends with the second occurrence of r ends with a cycle. Consequently, n is G0+-trapped.
pression. In what follows, for a belief state S = hB, K, i, we refer to the set { 2 B| ( ) = {}} as max(B). Corollary 2 If S = hB, B, i is a K0-compressed belief state such that G(S) is acyclic, then T r(S) = hmax(B), max(B), |max(B)i which is a minimal compression of S.
start with a transformation of the base-support graph. In particular, if G is a base-support graph, then the reverse-trimming of G is given by RGTrim(G) = (GTrim(GR))R, where GR is the reverse of G (i.e., the graph resulting from reversing all edges of G). Similar to trimmed graphs, a reverse-trimmed graph has a distinctive structure: Every node in a reverse-trimmed graph is G0 -trapped.
Definition 5. Let G be the base-support graph of a K0-compressed and trimmed belief state S = hB, B, i and let RGTrim(G) = (V1, V2, E). The reverse-trimming of S, denoted RT r(S), is a triple hB0, B0, 0i where 1. B0 = V1 [ max(B); 2. 0 : B0 ! 22B0 ; is such that, for every 2 B0, 0( ) = {H|H is a smallest subset of B0 such that is supported by H in S}.4 Corollary 3 If S is a K0-compressed and trimmed belief state, then RT r(S) is a belief state. Further, if S 6= RT r(S), then RT r(S) is a lossless compression of S.
in G = RGTrim(GTrim(G(S))) is G-trapped. 4.2
Towards Minimal B-Compression
Definition 6. Let G(S) = (V1, V2, E) be a base-support graph of some K0compressed, trimmed, and reverse-trimmed belief state S and let N ✓ V1. The closure of N in G(S), N G⇤(S),5 is the largest set such that there is a sequence (Hi, Si), i = 1 . . . n for some n 2 N, where 4 Instead of constructing 0 this way, a less expensive, but less tight, construction may be given thus:
0( ) = {n2 [ max(B)|(n2, ) 2 E} 5 We drop the subscript if it is clear from the context. 2. Si = {s 2 V2|s ✓ Hi 1} 3. Hi = Hi 1 [ { h 2 V1|(s, h) 2 E for some s 2 Si}
– Instance: A base-support graph G(S) = (V1, V2, E) of some K0-compressed, trimmed, and reverse-trimmed belief state S.
– Question: What is a minimum set N ✓ V1 such that N ⇤ = V1?
This problem is formally identical to the optimization variants of the minimum
axiom-set problem [
Observation 2 Any cycle of a graph G has a chordless sub-cycle.
In the sequel, if G is a base-support graph, let C(G) = {N |N is the set of hyp nodes on a cycle in G}; similarly, let CH(G) = {N |N is the set of hyp nodes on a chordless cycle in G}. A hitting set of a family of sets F is a set H such that H \ S 6= {} for every S 2 F .
Lemma 1. Let G = (V1, V2, E) be a trimmed and reverse-trimmed base-support graph. If H is a hitting set of C(G), then H⇤ = V1.
then deg (n) = deg+(n) = 1, for every node n in G. Thus, by Definition 6, {n}⇤ = V1 for any node n 2 V1.
C(G), then H⇤ = V1.
Induction Step. Let G have k + 1 cycles. Pick a cycle C and a hyp n 2 C.
G2 = RGTrim(GTrim(G1)) = (V12, V22, E2). By Corollary 3, (V12 [ { n})⇤ =
induction hypothesis, H2⇤ = V12, for any hitting set H2 of C(G2). Thus, from Definition 6, it follows that (H2 [ { n})⇤ = V1. Since, C(G2) ⇢ C (G), then, for every hitting set H of C(G), there is some hitting set H2 of C(G2) such that (H2 [ { n}) ✓ H. Thus, H⇤ = V1.
Theorem 1. Let G = (V1, V2, E) be a trimmed and reverse-trimmed base-support graph. If H is a hitting set of CH(G), then H⇤ = V1.
Proof. By Observation 2, a hitting set of CH(G) is also a hitting set of C(G).
S = hK, B, i.
1. Construct the base-support graph G of the K0-compression of S.
2. Construct Gtr = RGTrim(GTrim(G)).
3. Construct CH(Gtr). (This is done using the algorithm of [
that N ⇤ = V1. Instead, the algorithm selects nodes from V1 which are known a
priori to satisfy the closure check. Of the above four steps, only the third takes
exponential time in the worst-case, which occurs if the graph has
exponentiallymany chordless cycles. Fortunately, such cases are not very common (cf. [
and the approximation made in the fourth step.
Tables 1 and 2 display some results, comparing three B-compression algorithms. The first is our approximation, chordless-cycles-based algorithm, the second is a brute-force breadth-first search (BFS), and the third is a composition of both in which we run BFS-compression on the result of the approximation algorithm. Note that the first algorithm results in compressions which, in general are neither minimal nor irredundant; the second is guaranteed to yield minimal compressions; and the third is guaranteed to result in irredundant, but possibly not minimal, compressions. Table 1 displays the average time taken by each algorithm on randomly generated base-support graphs with varying numbers of nodes. (Around fifty graphs for each size range.) For relatively small graphs with fewer than 20 nodes, BFS has the best run time; but for larger graphs the other two algorithms (especially the first, naturally) dominate. (MLE is a shorthand for “memory limit exceeded.”) Table 2 displays the average sizes of the compressions resulting from each algorithm (on the same set of graphs used in Table 1).
compression) and the approximation algorithm is the worst in this regard. The composition algorithm, however, provides what could be an interesting compromise since the compression sizes it produces are comparable to those provided by BFS.
it contracts members of B which are not very useful in a sense defined below. To define such an operator, we need to revise our notion of support and, hence, belief state; we enrich the support structure with information about the exact chain of reasoning used to derive a formula, not just the hypotheses underlying the derivation. For example, consider a belief state S = hK, B, i with B = {Q, Q ! P, P ! R, P ! T }, K = B [ { P, R, T }, and
used again in any derivations. Intuitively, P seems to be the most important formula in this example since it is used to derive both R and T . The presence of
of Q’s being a hypothesis; but it is P , together with the respective material implication, that was used in actually deriving R and T . It, thus, may be fine to forget Q in this belief state and to lift P to become a hypothesis. The definition of support in a belief state ( ) does not, however, provide sucient information to allow us to simulate such useful forgetfulness.
Definition 7. Let B ✓ K ✓ s = {C1, C2, ..., Cn} where:
2
K is a finite set – for 1 i n, Ci = h i1, . . . , i|Ci|i with ij (6= ) 2 K and i1 2 B; and – 2 Cn(si( )), for 1 i m with m = maxi{|Ci|} and si( ) = { | there are Cl, Cr such that Cl h i Cr 2 s and either |Cr| = i 1 or |Cr| < i 1 and |Cl| = 0}.6 6 Henceforth, we use to denote sequence concatenation.
the original, flat support and with two “integrity” conditions.7 Definition 8. A layered belief state is a triple S = hB, K, i with B ✓ K ✓ L and a function mapping each 2 K to a set of layered supports for such that for every 2 K if there is s 2 ( ) with a chain C such that C = Cl h i Cr 2 s and |Cl| 6= 0, then there is s0 2 ( ) with Cl 2 s0 and for every C0 2 s0 C0 h i Cr 2 s. The size |S| of S is defined as |K| + P 2 K Ps2 ( ) PC2 s |C|.
Definition 9. Let S = hK, B, i be a layered belief state. A compression S0 of S is a layered belief state hK0, B0, 0i with 1. K0 ✓ K; 2. for every 2 K0 and s0 in 0( ), there is some s in ( ) such that every chain C0 in s0 is a sux of some chain C in s; and 3. |S0| < |S|.
right or if it is interesting only because it was once used to derive some formulas that are the ones frequently involved in reasoning processes. This way we, intuitively, replace members of B by members of K B to retain the possibility of deriving interesting propositions. Of course, this is, generally, lossy since we retract unsupported, albeit insignificant, hypotheses.
A layered belief state representing the situation discussed in the above example will have the following support function.
Definition 10. Let S = hK, B, i be a layered belief state and let ↵ 2 formula 2 B is ↵ -disposable if |{s 2 ⌃ (S)|h i C 2 s}| = 0 or Q. A |{s 2 ⌃ (S)|h i 2 s}| |{s 2 ⌃ (S)|h i C 2 s}| < ↵
7 The layered support may be constructed from the flat support together with
information about the formulas directly used in derivations (akin to justification-based
reason maintenance systems [
– A tree in s is a set s0 ✓ s such that there is a chain r(s0) such that s0 = {C|C = Cl r(s0), for some Cl}. A tree s0 in s is an ↵ -disposable tree if there is some Cl r(s0) 2 s such that Cl ends with an ↵ -disposable formula. – D(S, ↵ ) = { 2 B| is ↵ -disposable}. – Base(S, ↵ ) = { 2 K B| ( ) contains an ↵ -disposable tree}. – R(S, ↵, s ) = {r(s0)|s0 is a maximal ↵ -disposable tree of s} [ { C|C 2 s is not in any ↵ -disposable tree}.
Definition 12. For a layered belief state S hK, B, i, the ↵ -cut of S, denoted cut(S, ↵ ), is a triple hK0 , B , 0 i, where
0 – K0 = K D . – B0 = B D [ Base(S, ↵ ). – 0 ( ) = {R(S, ↵, s )|s 2 ( ) and hi 2 /R (S, ↵, s )}.
Corollary 4 If S is a layered belief state and ↵ 2 Q, then cut(S, ↵ ) is a layered belief state. Further, if D(S, ↵ ) 6= {}, then cut(S, ↵ ) is a compression of S. 6
Belief state compression is a variant of knowledge base size reduction which does not put any syntactic constraints on the form of the knowledge base, but assumes a support-structured set of formulas akin to classical reason maintenance systems. We have explored various approaches to belief state compression. In particular, varieties of base compression which can sometimes be minimal have been pointed out, and an ecient, tight, but not necessarily minimal nor redundant, compression technique has been proposed. An example of a lossy compression which disposes of insignificant pieces of information has also been described.
tion algorithm. In particular, we have some preliminary results with iteratively applying the algorithm on its own output until a fixed-point is reached. The results are promising, and we conjecture that the method yields irredundant compressions. We save the proof and further experiments to future work.