4. Truth Maintenance with Cognitive Dissonance

The Truth Maintenance System using Cognitive Dissonance (TMS-CD) uses the concepts of Cognitive Dissonance Theory to decide which beliefs to keep in a belief set and which beliefs to throw out. Like other Truth Maintenance Systems, the TMS-CD is a system that is external to an inference engine that keeps track of which beliefs are valid inputs for the inference engine to use when deriving new beliefs.

4.1. The TMS-CD Structure

The TMS-CD is structured as a network of nodes. Each node represents a single belief in the belief set. A belief and its negation are each associated with their own distinct nodes. Each node is an 8-tuple of information describing the belief: . The belief is the belief that the belief node represents within the belief network. The status of a belief node indicates whether or not the belief is currently believed; a valid belief is believed, but an invalid belief is not. The status of a belief node can also be nil while the belief network is being updated. The evidence of a belief is the size of its set of valid parents, and the importance of a belief is the size of its set of valid children. The valid-parents of a belief are the set of pairs of valid beliefs that the belief can be directly inferred from. The invalid-parents are the set of pairs of beliefs that the belief can be directly inferred from, but one or both of the parent beliefs is invalid. The valid-children of a belief are the set of valid beliefs that can be inferred directly from the belief (when paired with other beliefs, whether they are valid or invalid). The invalid-children are the set of invalid beliefs that can be directly inferred from the belief.

We are assuming here that the inference engine only acts on two beliefs at a time to derive a new belief. It is possible that the TMS-CD could be acting on the belief set of an inference engine that uses more than two beliefs at a time to derive new ones. This would only affect the TMS-CD in that the valid parents and invalid parents of a belief would be sets of sets rather than sets of pairs. All beliefs in a parent set would have to be valid for that parent set to be a member of the valid parents. Otherwise, the parent set would be a member of the invalid parents. For simplicity of discussion, we will assume that new beliefs can only be derived from pairs of parent beliefs.

4.2. The TMS-CD Decision Process

In Doyle's [2] TMS, a belief is valid (currently believed) as long as its set of valid parents is not empty and it is not directly contradicted by another belief. If two contradictory beliefs are both believed at the same time, one of the assumptions they are based on is removed from the belief set and the consequences of that assumption are updated recursively. More detail on Doyle's truth maintenance process can be found in Section 2.2.

In the TMS-CD, a contradiction is resolved by removing one of the contradictory beliefs from the belief set and updating the belief network from the inside out instead of from the top down. The difficulty is deciding which belief should be removed. For the answer, we turn to Cognitive Dissonance Theory. Recall that, according to Cognitive Dissonance Theory, the amount of dissonance is a function of the importance and number of beliefs in conflict. In the TMS-CD, the importance of a belief is measured as the number of valid children that the belief directly supports. Only two beliefs can be in direct conflict at a time, so we turn to the number of beliefs that support each of the two conflicting beliefs. Thus, the evidence for a belief is measured as the number of pairs of valid parents that directly support it. Refer back to Section 3 for more details on Cognitive Dissonance Theory.

There are some who might argue that, rationally speaking, only the evidence should be considered during this comparison. Although this might be true, humans are not completely rational thinkers. Keep in mind that one of the goals of the TMS-CD is to imitate human cognition.

Based on the evidence and importance of each belief, we must carefully consider how to make a comparison. The simplest approach would be to assign each belief a strength that is the sum of the evidence and importance and discard the belief with the lesser strength. To make the comparison slightly more interesting, we can assign weights to evidence and importance. We will call the weight put on evidence a and the weight put on importance b. Thus, the strength of a belief P can be calculated as

strength(P) = (a * evidence(P)) + (b * importance(P))

By assigning different values of a and b, the TMS-CD can give the reasoning system various "personality styles". A more rational thinker would have a higher a value, while a less rational thinker would have a higher b value.

We are still left with the occasional difficulty of deciding between two beliefs of exactly the same strength. In this case, we suggest that the TMS-CD should not make this decision. Altering beliefs because of cognitive dissonance is supposed to be a subconscious process. Only when the dissonance between conflicting beliefs passes a threshold does the conflict enter conscious thought. The TMS-CD is meant to mimic the subconscious processes of cognitive dissonance. Therefore, in cases of very close strengths between beliefs, the problem should be resolved by some other means available to the reasoning system. Other possible means of resolving a conflict might include a more sophisticated decision-maker or postponing the decision until more information can be gathered. If the reasoning system does not have any other way to resolve a contradiction, then it might fall back on one of the methods for changing an assumption suggested by Doyle (see Section 2.2). As just stated, conflicts enter consciousness when the dissonance between beliefs passes a threshold. This threshold, which we will call d, can be incorporated into the decision-making process used by the TMS-CD. The following decision-making algorithm can be used to decide which of two conflicting beliefs, A and B, to remove from the belief set.

strength(A) = (a * evidence(A)) + (b * importance(A))
strength(B) = (a * evidence(B)) + (b * importance(B))
if |strength(A) - strength(B)| < d then
	invoke external decision process
else if strength(A) < strength(B) then
	remove A from belief set
else
	remove B from belief set

Like a and b, d can also vary between reasoning systems. A more cautious reasoner would have a higher d value, putting more effort into making the correct choice. A more impulsive reasoner would have a lower d value, relying more on "feelings" or "instincts" for a quick decision.

Even with a decision process such as this that takes into account the evidence and importance of beliefs, the TMS-CD contains more information that can be used. Recall that a belief and its negation are represented as separate nodes in the TMS-CD. This means that both the belief and its negation are associated with values of evidence and importance. When measuring the strength of a belief, it would be logical to incorporate the strength of the belief's negation into the calculation. The strength of a belief should decrease as the strength of its negation increases. To include the strength of a belief's negation in the calculation of the belief's strength, the evidence and importance of the negation are subtracted from the evidence and importance of the belief, respectively.

strength(A) = a(evidence(A) - evidence(~A)) + b(importance(A) - importance(~A))
strength(B) = a(evidence(B) - evidence(~B)) + b(importance(B) - importance(~B))
if |strength(A) - strength(B)| < d then
	invoke external decision process
else if strength(A) < strength(B) then
	remove A from belief set
else
	remove B from belief set

This is the complete decision process used by the TMS-CD. The following section describes how this decision process can be incorporated into an algorithm to traverse the belief network and update beliefs as new ones are added.

4.3. The TMS-CD Algorithm

The TMS-CD procedure takes four arguments: the set of initial assumptions that inferences will be made from (called A), the weight given to the evidence of beliefs (called a), the weight given to the importance of beliefs (called b), and the difference threshold used to determine when to invoke an external decision process (called d). The procedure begins by adding each of the initial assumptions to the belief network. Then the main loop begins. In the main loop, a new belief is inferred from the current belief set. A new belief node is created to store the belief if necessary, and the update-belief procedure is called to recursively update the beliefs in the network.

1	procedure TMS-CD(assumption-set A, a, b, d)
2		belief-network B = nil
3		for each assumption a in A do
4			n = new belief-node
5			belief(n) = a
6			status(n) = invalid
7			evidence(n) = 1
8			importance(n) = 0
9			valid-parents(n) = {assumed}
10			invalid-parents(n) = nil
11			valid-children(n) = nil
12			invalid-children(n) = nil
13			add n to B
14			update-belief(n, B, a, b, d)
15		end for
16		repeat
17			S = belief-set(B)
18			b = infer(S)
19			if b is represented by a belief-node in B then
20				add new justification to valid parents of b
21			else
22				n = new belief-node
23				belief(n) = b
24				status(n) = invalid
25				evidence(n) = 1
26				importance(n) = 0
27				valid-parents(n) = {justification for b}
28				invalid-parents(n) = nil
29				valid-children(n) = nil
30				invalid-children(n) = nil
31				add n to B
32			end if
33			update-belief(n, B, a, b, d)
34		end repeat
35	end TMS-CD

The update-belief procedure acts on a single belief. It is called when either a new belief is added to the belief network or the status of one of the belief's parents has changed. The status of the new belief is updated based on other changes in the belief network.

The update-belief procedure takes as arguments the belief node that is being updated, the belief network, and the values for a, b, and d. If the belief node is not already being updated by another call to update-belief or resolve-conflict, and if the negation of the belief is not represented by another belief in the network, then the belief can be updated here. If the status of the belief node changes, the belief node is moved to the appropriate child set of its parents and the appropriate parent set of its children. The resolve-conflict procedure is called on each of the belief node's affected parent pairs and the update-belief procedure is called recursively on each of the belief node's affected children.

1	procedure update-belief(belief-node n, belief-network B, a, b, d)
2		if status(n) = nil then
3			return
4		else if the negation of belief(n) is represented by some belief-node m in B then
5			resolve-conflict(n, m, a, b, d)
6			return
7		else
8			old-status = status(n)
9			if a * (size of valid-parents(n)) + b * (size of valid-children(n)) > 0 then
10				new-status = valid
11			else
12				new-status = invalid
13			n.status = nil
14			affected-parents = nil
15			affected-children = nil
16			if old-status = valid and new-status = invalid then
17				for each parent pair (p, q) in valid-parents(n) and invalid-parents(n) do
18					remove n from valid-children(p)
19					add n to invalid-children(p)
20					remove n from valid-children(q)
21					add n to invalid-children(q)
22					add (p, q) to affected-parents
23				end for
24				for each belief-node c in valid-children(n) and invalid-children(n) do
25					remove all parent pairs that include n from valid-parents(c)
26					add all parent pairs that include n to invalid-parents(c)
27					add c to affected-children
28				end for
29			else if old-status = invalid and new-status = valid then
30				for each parent pair (p, q) in valid-parents(n) and invalid-parents(n) do
31					remove n from invalid-children(p)
32					add n to valid-children(p)
33					remove n from invalid-children(q)
34					add n to valid-children(q)
35					add (p, q) to affected-parents
36				end for
37				for each belief-node c in valid-children(n) and invalid-children(n) do
38					if any parent pair in invalid-parents(c) includes n and another valid parent then
39						remove all parent pairs that include n and another valid parent from invalid-parents(c)
40						add these parent pairs to valid-parents(c)
41						add c to affected-children
42					end if
43				end for
44			end if
45			for each parent pair (p, q) in affected-parents do
46				resolve-conflict(p, q, B, a, b, d)
47			end for
48			for each belief-node c in affected-children do
49				update-belief(c, B, a, b, d)
50			end for
51			status(n) = new-status
52			return
53		end if
54	end update-belief

The resolve-conflict procedure acts on two conflicting beliefs that can not exist simultaneously in the belief set. Two beliefs are in conflict if they are either logical negations of each other or if they are both valid parents of an invalid child. The decision process described in Section 4.2 is used to decide which of the two beliefs will be in the belief set and which will be out.

The resolve-conflict procedure receives six arguments: the two beliefs in conflict, the belief network, and the values for a, b, and d. The strength of each belief is calculated and used to decide which belief to accept and which to reject. If the status of a belief node changes, the belief node is moved to the appropriate child set of its parents and the appropriate parent set of its children. The resolve-conflict procedure is called recursively on each of the belief nodes' affected parent pairs and the update-belief procedure is called on each of the belief nodes' affected children.

1	procedure resolve-conflict(belief-node a, belief-node b, belief-network B, a, b, d)
2		if the negation of belief(a) is represented by some node m in B then
3			strength(a) = a(evidence(a) - evidence(m)) + b(importance(a) - importance(m))
4		else
5			strength(a) = a(evidence(a)) + b(importance(a))
6		end if
7		if the negation of belief(b) is represented by some node n in B then
8			strength(b) = a(evidence(b) - evidence(n)) + b(importance(b) - importance(n))
9		else
10			strength(b) = a(evidence(b)) + b(importance(b))
11		end if
12		if |strength(a) - strength(b)| < d then
13			invoke external decision process to set rejected to a or b
14			accepted = belief-node that was not rejected
15		else if strength(a) < strength(b) then
16			rejected = a
17			accepted = b
18		else
19			rejected = b
20			accepted = a
21		end if
22		old-status(a) = status(a)
23		status(a) = nil
24		old-status(b) = status(b)
25		status(b) = nil
26		affected-parents = nil
27		affected-children = nil
28		if old-status(a) = valid and rejected = a then
29			for each parent pair (p, q) in valid-parents(a) and invalid-parents(a) do
30				remove a from valid-children(p)
31				add a to invalid-children(p)
32				remove a from valid-children(q)
33				add a to invalid-children(q)
34				add (p, q) to affected-parents
35			end for
36			for each belief-node c in valid-children(a) and invalid-children(a) do
37				remove all parent pairs that include a from valid-parents(c)
38				add all parent pairs that include a to invalid-parents(c)
39				add c to affected-children
40			end for
41		end if
42		if old-status(a) = invalid and accepted = a then
43			for each parent pair (p, q) in valid-parents(a) and invalid-parents(a) do
44				remove a from invalid-children(p)
45				add a to valid-children(p)
46				remove a from invalid-children(q)
47				add a to valid-children(q)
48				add (p, q) to affected-parents
49			end for
50			for each belief-node c in valid-children(a) and invalid-children(a) do
51				if any parent pair in invalid-parents(c) includes a and another valid parent then
52					remove all parent pairs that include a and another valid parent from invalid-parents(c)
53					add these parent pairs to valid-parents(c)
54					add c to affected-children
55				end if
56			end for
57		end if
58		if old-status(b) = valid and rejected = b then
59			for each parent pair (p, q) in valid-parents(b) and invalid-parents(b) do
60				remove b from valid-children(p)
61				add b to invalid-children(p)
62				remove b from valid-children(q)
63				add b to invalid-children(q)
64				add (p, q) to affected-parents
65			end for
66			for each belief-node c in valid-children(b) and invalid-children(b) do
67				remove all parent pairs that include b from valid-parents(c)
68				add all parent pairs that include b to invalid-parents(c)
69				add c to affected-children
70			end for
71		end if
72		if old-status(b) = invalid and accepted = b then
73			for each parent pair (p, q) in valid-parents(b) and invalid-parents(b) do
74				remove a from invalid-children(p)
75				add a to valid-children(p)
76				remove a from invalid-children(q)
77				add a to valid-children(q)
78				add (p, q) to affected-parents
79			end for
80			for each belief-node c in valid-children(b) and invalid-children(b) do
81				if any parent pair in invalid-parents(c) includes b and another valid parent then
82					remove all parent pairs that include b and another valid parent from invalid-parents(c)
83					add these parent pairs to valid-parents(c)
84					add c to affected-children
85				end if
86			end for
87		end if
88		for each parent pair (p, q) in affected-parents do
89			resolve-conflict(p, q, B, a, b, d)
90		end for
91		for each belief-node c in affected-children do
92			update-belief(c, B, a, b, d)
93		end for
94		status(accepted) = valid
95		status(rejected) = invalid
96		return
97	end resolve-conflict

Back | Home | Next