# Efficient algorithm for finding linear combination of piecewise functions

While porting an algorithm, I having a bit of a problem with finding an efficient algorithm for finding a linear combination of piecewise functions. The procedure is described in the Table 3 of the appendix of the SIRUS algorithm by Bénard et al. (https://proceedings.mlr.press/v130/benard21a.html).

The problem is defined as follows. Given the following rules

rule number if then else
1 MMAX < 32000 61 408
2 MMAX ≥ 32000 408 61
3 MMIN < 8000 62 386
4 MMIN ≥ 8000 386 62
5 CACH < 64 56 334
6 CACH ≥ 64 334 56
7 MMAX ≥ 32000 & CACH ≥ 64 517 67
8 CHMIN < 8 50 312
9 CHMIN ≥ 8 312 50
10 MYCT < 50 335 58
11 MYCT ≥ 50 58 335
12 MMAX ≥ 32000 & CACH < 64 192 102
13 MMAX < 32000 & CHMIN ≥ 8 157 100
14* MMAX ≥ 32000 & CHMIN ≥ 12 554 73
15 MMAX ≥ 32000 & CHMIN < 12 252 96
16 MMIN ≥ 8000 & CHMIN ≥ 12 586 76
17 MMIN ≥ 8000 & CHMIN < 12 236 94

Then, according to the authors of the paper, rule 12, 15 and 17 are linearly dependent on other rules. Specifically, for rule 12, there exist 3 real numbers, $$\alpha_1$$, $$\alpha_5$$, and $$\alpha_7$$ such that for all $$x \in \mathbb{R}^p$$ (all datapoints; $$p$$ is the number of features in the dataset)

$$g_{12}(x) = \alpha_1 g_{1}(x) + \alpha_5 g_{5}(x) + \alpha_7 g_{7}(x)$$

where $$g_5(x)$$ denotes the rule outcome of rule 5 for datapoint $$x$$. For example, if the datapoint $$x$$ satisfies CACH < 64, then the outcome is 56, and otherwise it is 334. That rule 15 and 17 are linearly dependent on other rules should follow from similar reasoning.

My question now is, what would be an efficient algorithm to find these linearly dependent rules? Further assumptions are that the number of rules is somewhere in between 1k to 100k and that the number of constraints is at most two, so A and A & B are possible but A & B & C is not.

Footnote by rule 14: There is a typo in the paper for rule 14 as I learned by the author of the paper via email. It should read MMAX ≥ 32000 instead of MMAX < 32000. I've fixed it in the table here and verified that the table is now correct according to the algorithm described below.

• Are you familiar with linear programming? your question is equivalent to finding redundant (linearly dependent) constraints in a linear program. The answer to this post points out an answer: math.stackexchange.com/questions/1408467/… Jul 5, 2022 at 17:43
• Notice that the then and else values are irrelevant and can be normalized to $0$ and $1$.
– user16034
Jul 6, 2022 at 7:21
• @YvesDaoust, almost, but not quite. You can't necessarily normalize to 0 and 1 -- you only can if there is a combination of rules that sums to something equivalent to "True then ... else ...". You can multiply every rule by a constant, but you can't necessarily add a constant (unless there is a combination of the form I just mentioned).
– D.W.
Jul 6, 2022 at 15:01
• @D.W.: you are right, my bad.
– user16034
Jul 6, 2022 at 15:06

Conceptually, I suggest an approach like this:

• For each rule $$r$$:

• Check whether it is linearly dependent on the preceding rules. If it is, output the linear dependence and remove $$r$$ from the set of rules.

To help us do this, we can note that a rule whose condition is of the form A && B can only depend on rules that use some combination of A, !A, B, and/or !B, as well as certain other special combinations of rules indicated below.

First, find all sums of rules that are equivalent to a rule with a single clause. Every such sum must be a sum of two rules $$g_1,g_2$$, where $$g_1$$ is "A && B then $$c_1$$ else $$c_2$$" and $$g_2$$ is "A && !B then $$c_3$$ else $$c_4$$"; then the sum $$(c_4-c_3) g_1 + (c_2-c_1) g_2$$ will be equivalent to the derived rule "A then $$c_2 c_4 - c_1 c_3$$ else $$2c_2 c_4 - c_2 c_3 - c_1 c_4$$". Add these derived rules to the set of rules.

Second, find all sums of rules that are equivalent to a rule with no clauses. Every such sum must be a sum of two rules $$g_1,g_2$$ (possibly derived, possibly original), where $$g_1$$ is "A then $$c_1$$ else $$c_2$$" and $$g_2$$ is "!A then $$c_3$$ else $$c_4$$"; then the sum $$(c_3-c_4) g_1 + (c_1-c_2) g_2$$ is equivalent to the derived rule "True then $$c_1 c_3 - c_2 c_4$$". Add these derived rules to the set of rules. Actually, we only need one. (And assuming there is at least one, we only need one derived rule "A then .. else ..." per possible clause A.)

To check whether a rule $$r$$ is linearly dependent on the preceding rules, we only need to consider rules whose clauses are a subset of the clauses of $$r$$ and/or their negations. For instance, if $$r$$ is "A && B then ... else ...", we only need to consider rules (including both original ones that precede $$r$$, and derived rules) whose conditions are A && B, A && !B, !A && B, !A && !B, A, !A, B, !B, or True.

Now we need a way to tell whether $$r$$ is linearly dependent on those rules. We can do that with linear algebra. Let $$x_1,x_2,x_3,x_4$$ be four values for the variables, where $$x_1$$ satisfies A && B, $$x_2$$ satisfies A && !B, $$x_3$$ satisfies !A && B, and $$x_4$$ satisfies !A && !B. We can map each rule $$g_i$$ to the 4-vector $$v_i=(g_i(x_1),g_i(x_2),g_i(x_3),g_i(x_4))$$. Now rule $$r$$ is linearly dependent on those other rules iff its 4-vector is linearly dependent on the corresponding 4-vectors. That can in turn be tested using linear algebra, e.g., Gaussian elimination on a matrix whose rows are the 4-vectors for those other rules.

This should be very efficient, even for 100K rules.

• This answer is brilliant. I would probably have never come up with this. I've implemented the algorithm for the rules described above (github.com/rikhuijzer/StableTrees.jl). It correctly solves the rules in 133 μs.
– RikH
Jul 6, 2022 at 15:21
• @RikH, thank you for implementing this and sharing how it worked out!
– D.W.
Jul 6, 2022 at 15:28