2006-10-19

Dissecting Rete - Intra-element condition tests in Rete/UL

The last few days have seen some debate about Rete and Rete/UL in particular. It's all Charles fault, he started it when he updated Wikipedias entry on the Rete Algorithm ;-)

You'll find the meat of it over at Peter's blog, in particular here. Peter goes on to analyse the Rete/UL approach in his entry on Limitations of EAV WME and then later on in the entry Exhaustive lookup.

I've already commented about the need for extra Joins in Rete/UL so I won't say anything about that here. However, the question of intra-element conditions remains.

Unfortunately Doorenbos is very vague in his description of intra-element conditions. In fact, he says next to nothing about them. Which has led me to believe that they aren't performed at all. The same end-result can be produced anyway, only, it requires a lot more join operations and more space (to store unneccessary tokens).

Let's look at one of the examples, this one is used in several places:


(find-stack-of-two-blocks-to-the-left-of-a-red-block
([x] ^on [y]) /* C1 */
([y] ^left-of [z]) /* C2 */
([z] ^color red) /* C3 */
-->
... RHS ... )
the Rete Network shown in Figure 2.2(b) on page 10 corresponds to this production. In the same illustration he shows how the 9 WMEs can be combined into a set of 3 WMEs that satisfy the LHS. What would happen if we change the production to:


(find-stack-of-two-blocks-to-the-left-of-a-red-block
([x] ^on [y]) /* C1 */
([y] ^left-of [z]) /* C2 */
([z] ^color red) /* C3 */
([z] ^size medium) /* C4 */
-->
... RHS ... )
let's also add 3 other WMEs:


w10 (B1 ^size large)
w11 (B2 ^size medium)
w12 (B3 ^size medium)
This would create another Beta Memory (matches for C1^C2^C3), a Join Node (join on values of [Z]) and an Alpha Memory (AM for C4).

In Forgy's description of Rete, C3 and C4 also represent an intra-element condition. To test it you would normally hook the constant tests together and only let WMEs proceed to the Alpha Memory if both tests evaluate to True.

In Rete/UL, things work a little differently. Alpha Nodes and Memories map one-to-one with conditions. This means, among other things, that the Alpha Memory for C4 will contain w11 and w12 even though w6 never made it to the Alpha Memory for C3 (since both w6 and w11 have id = B2 we "know" that w11 can never be used to construct a matching token but the Rete Network won't be able to "know" that until the join).

The Production Node will still have one token that matches all of the tests in the network (w1^w5^w9^w12). But what if we modify w12 to

w12 (B3 ^size large)
The Alpha Memory C4 will now only contain w11 and the last join (with w1^w5^w9) will fail. No token will be sent to the Production Node but most of the Alpha and Beta Memories remain unchanged (this is where the extra space requirement shows up).

In the example above there's only one intra-element condition. If we would have had five of them instead, and WMEs that passed four of the constant tests, we would have to perform four joins before we can conclude that none of the WMEs can be used to trigger the RHS.

Using intra-element conditions as Forgy describes reduces the number of tokens to store and therefore the number of joins to try. We would still have to test four times (in Alpha Nodes) before we can throw away the WMEs but constant tests are cheaper than joins so this will most probably have an effect on performance. How much of an effect? I have no idea. It would be interesting to test though.

All of this leads me to believe that Rete/UL is not meant to be used as a general purpose "object" based production system but that it rather works with little bits and pieces (as described in the paper) of facts. Trying to use it as if it was JBoss Rules or Jess will of course not give the best effect but if that's not what it was built for...

It's a pity that Doorenbos doesn't compare and contrast the Rete/UL implementation with the one that Forgy describes in his 1979 thesis, and in particular the effect it has on performance (in both space and time).

2 kommentarer:

woolfel sa...

It is a shame Doorenbos didn't do the comparison, but I can understand. Writing a thesis is hard enough, let alone doing a detail analysis for a Philosophy Phd. On page 11 and 17, Doorenbos says this:

page 11
Strictly speaking, in most versions of Rete, the alpha network performs not only constant tests but also intra-condition variable binding consistency tests, where one variable occurs more than once in a single condition; e.g., (<x> ^self <x>). Such tests are rare in Soar, so we will not discuss them extensively here.

page 17
The non-equality tests can be handled by the beta part of the network instead of the alpha part. Of course, it is possible for an implementation of Rete to perform some of the constant (or intra-condition) tests in the beta rather than the alpha network. This leaves the alpha network almost trivial, and turns out to not increase the complexity of the beta network much, if at all. However, it reduces the potential for these tests to be shared when different productions have a common condition. (This is the approach taken in the implementation used in this thesis.)

If I'm reading it correctly, Doorenbos is saying his paper uses betaNodes to do intra-condition (aka intra-element) tests.

Johan Lindberg sa...

Well, the only thing he does say about it is on page 56. It's not much but it's something:

Although the choice of notation for WMEs does not affect the representational power of the
system, it may affect the performance of certain parts of the Rete algorithm. In general, the
above transformations increase the number of WMEs needed to represent a given thing, and the number of conditions needed to test for it. After we apply these transformations, there will
often be many conditions in a production with the same variable in their id field; thus, many
variable binding consistency tests will be required with the id-attribute-value representation
that would not be required in the more complex representations. This means the beta part of the network will have to do more work. On the other hand, the alpha part of the network may have to do more work with the more complex representations than with the simple id-attribute-value representation. In the simple representation, a given WME can go into at most eight alpha memories, as discussed in Section 2.2.3 (assuming all intra-condition tests are for equality with constants). In the more complex representations, a WME may go into many more - e.g., a predicate with r arguments could go into up to 2r+1 alpha memories - so the
alpha network may no longer run as fast as it can with the id-attribute-value representation.


That last conclusion can of course be debated, but I guess it all comes down to what you're using the Production System for.