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.
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:
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.
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
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.
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.
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.
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.
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.
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.
4.2. The TMS-CD Decision Process
strength(P) = (a * evidence(P)) + (b * importance(P))
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
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
4.3. The TMS-CD Algorithm
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
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
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