Creating huge decision tree

I’m to write an event correlator. A fundamental part of the system will be a decision tree that recognizes the origin of the fault basing on recorded states and log files.

Often many accidents will differ with minor details and many decisions taken will be made basing on fuzzy, incomplete or unreliable data, but most of these decisions can be written down as binary logic functions.

Thing is, there will be a lot of them. I expect at least 100 nodes in the decision tree, and I may underestimate the value by an order of magnitude. And on top of that, as new, unexpected patterns emerge, unforseen failures happen leaving new traces, or with extension of the system new failure modes become viable, the decision tree will have to be maintained.

(and it won’t always be a pure tree structure – some faults of the same effect have two or more modes of appearance, some of these branching off into different modes, e.g. event A means failure X, event B means: check event C. If C is true, it’s also failure X, but if not, it’s failure Y. Although I can always normalize it into X1 and X2, which are technically identical but different from the tree point of view.) Also, the tree will be often fairly deeply nested so I’m afraid a simple series of nested if() will quickly slip out of control.

Now my question is, how to store / write / build that tree so that it could be compilable into something the machine can digest, but still maintainable for the developers?

Note this is for an embedded system, so heavyweight solutions like JBoss don’t really fit unless they appear only on the compiler side, and the final system runs a compiled ruleset in something much more machine friendly.

(the system is written in C++, it also makes extensive use of JSON, and will run on an ARM9 CPU if that’s of any help.)

Here is an idea for such a DSL. Say you have 6 input variables (your “events”). Lets assume those variables are binary (the idea can be generalized to non-binary variables). Now your DSL should contain statements like

(0|*|1|0|1|1) => Action_A()
(0|0|1|0|0|*) => Action_B()
(1|1|1|0|*|*) => Action_C()
default       => ActionDefault()

Each row contains a precondition (the part left to the =>), saying which input variable must have which value. The part right to the => is the action to be applied. A “*” means that the corresponding input variable can be either 0 or 1. The semantics can be compared to the pattern matching mechanics of awk, perl, or xslt.

How does this help you? Well, now you can do two things

write a simple validator which checks that all your preconditions are mutally exclusive. If you don’t want or need a “default” action, you can let this out and instead let your validator additionally check that you did not miss a case.
write a code generator which translates that DSL into C++ code, which may then look similar to this:
```
if(event_1==0 && event_3==1 && event_4==0 && event_5==1 && event_6==1)
    Action_A();
```

The validator will help you to keep things maintainable, and the generated C++ code should compile into something “machine friendly”, as you required.

If your input variables are not binary (100 nodes by a depth of 2-3 decisions is not possible just by binary inputs), you will have to extend that DSL, it should be straightforward how to accomplish that. For example, use (0,1,4|*|*) for a precondition (event_1==0 || event_1==1||event_1==4).

EDIT: if you have many input variables and the requirement to check only a few of them, this could be adapted by using “named parameters”, for example

    (var_1==[0,1,4]|var_3==0|var_25==[1-10]) => Action_A()

Of course, you could also code this directly in C++, which won’t become much longer, but the advantage of using a small, formal DSL is that now you have a chance to write a validator for this.

I am no C++ developer, but I think the rule declarations DSL can be implemented purely in C++.

First, there is a request object, containing all input parameters (e.g. as a map). This object can also cache an already checked conditions, rule check trace, and possibly some intermediate data.

class Request {
public:
    template<T> Value<T> get(Parameter<T>); // Returns the given parameter value.
    /* Returns a 3-state status for the given condition:
       - not checked yet
       - condition succeed
       - condition failed */
    ConditionCheckStatus getCheckStatus(Condition);
    void setCheckStatus(Condition, bool); // Caches the condition check status.
}

Such object should be constructed once per request and should be passed to a topmost rule.

A conditions can be expressed using a Condition class subclasses. The Condition checks whether it’s already evaluated. If not – then evaluates itself and caches the evaluation check status. To build a complex conditions it is good to override &, | and ! operators:

class Condition {
public:
    inline bool check(Request &request) {
        switch (request->getCheckStatus(this)) {
        case COND_SUCCESS:
            return true;
        case COND_FAILURE:
            return false;
        }
        bool result = this->checkCondition(request);
        request.setCheckStatus(this, result);
        return result;
    }
    inline Condition &operator & (Condition &other) {return *new AndCondition(*this, other)}
    inline Condition &operator | (Condition &other) {return *new OrCondition(*this, other)}
    inline Condition &operator ! () {return *new NotCondition(*this)}
protected:
    virtual bool checkCondition(Request &) = 0;
}

A concrete conditions can be declared as global constants and may be combined with logical operators to build a more complex ones.

The Parameter template can be used to access a Request parameters in a type-safe manner. A concrete parameters can be declared as global constants. Parameters can also override operators to construct Conditions like this:

// Declare a "counter" input parameter.
const Parameter<int> Counter;

// Construct a "more than once" condition.    
const Condition &MoreThanOnce = Counter > 1;

A ruleset can be declared using Rule objects (also declared as global constants).

const Rule FailIfMoreThanOnce(
    MoreThanOnce, /* The condition */
    Failure,      /* The rule invoked if condition succeed */
    OtherRule     /* The rule invoked if condition failed */);


// ... Other rule definitions

const Rule TopRule(SomeCondition1 | SomeCondition2, SomeRule1, SomeRule2);

A decision tree evaluation would look like this:

Request request;
// Fill the request.
bool result = TopRule.check(request);
// Handle the result.

Note that all Parameters, Conditions and Rules are stateless. The only mutable object is Request, which is constructed once per request and collects the evaluated data.

The rules, parameters and conditions may have a meaningful names, can be constructed using operators. There is almost none syntax overhead for their declaration. The even shorter declarations can be done using macros.

Filed under: softwareengineering - @ 00:32

Thẻ: data-structures, maintainability

Thiết kế website giá rẻ

Danh mục

Creating huge decision tree