Then it is necessary to break the symmetry and choose a single test for the root
node. If, for example,ais chosen, the second rule must, in effect, be repeated
twice in the tree, as shown in Figure 3.2. This is known as the replicated subtree
problem.
The replicated subtree problem is sufficiently important that it is worth
looking at a couple more examples. The diagram on the left of Figure 3.3 shows
an exclusive-orfunction for which the output is aifx= 1 or y= 1 but not both.
To make this into a tree, you have to split on one attribute first, leading to a
structure like the one shown in the center. In contrast, rules can faithfully reflect
the true symmetry of the problem with respect to the attributes, as shown on
the right.66 CHAPTER 3| OUTPUT: KNOWLEDGE REPRESENTATION
a
b
y
c
n
x
y
c
n
d
y n
x
y n
d
y n
x
y n
Figure 3.2Decision tree for a simple disjunction.