ITRULE Algorithm:

The ITRULE-algorithm [41, pp. 306-308] takes an overall database relation (with discrete dimensions) as input and generates a set of the K most informative rules according to the J-measure. K is a user-defined parameter.

The algorithm starts out with rules that have first order conditions, i.e. $\mathcal{X}$consists only of one (variable, value)-pair ( $\mathcal{X}=\{(X_1,x_1)\}$ ). It finds K rules, calculates their J-measures, and places these rules in an ordered list. The smallest J-measure defines the ``running minimum J_min''. Then the J-measure of new solution-set candidates is compared with J_min. Better rules are inserted and J_min is updated. Before continuing the evaluation of first-order rules, it is decided for each rule whether further specialization, meaning adding (variable, value)-pairs to the precondition, is worthwhile.

In particular, we can calculate an upper bound for the information content of a specialization (see [41] for derivation) :

$$J_s = \max \left\{ f(\vec{x})\cdot f(y\vert\vec{x})\cdot log_... ...vert\vec{x}))\cdot log_2\left(\frac{1}{1-f(y)}\right) \right\}$$

If the J_s bound is less than J_min, then specialization cannot possibly find a candidate for the solution-set and we back-up the search from this rule. Also if the transition probability $f(y\vert\vec{x}) = 1$ (or = 0) then we cannot increase the information content by specializing, as we need to offset the decrease in simplicity by an increase of goodness-of-fit (which is already maximal). In all other cases we continue to specialize in order to find a better more specialized rule.

The problem of this algorithm is its computational complexity. Let $d_1,d_2,\ldots,d_n$ be the dimensions of the overall relation. Denote k_i := |dom(d_i)|, $\; i=1,\ldots,n$ as the number of values in the domain of variable d_i. Then $k=k_1+k_2+\ldots+k_n$ is the number of rule conclusions, k² is the approximate number of first-order rules (2k² if we separate transition probabilities close to 1 and 0). For all these rules rules J-measures and bounds need to be computed, which can be many if the database is wide and therefore k large. Furthermore a much greater number of specializations of these rules need to be evaluated. We presume that this together is in the order of O(kⁿ).

The use of value hierarchies (Coarsening, Refinement) is an important feature and needs to be considered in further implementations of this algorithm, so far hierarchies are not supported.

A number of other variations are considerable for this algorithm. Instead of specifying the number K the user could define a minimum information content J_min. Other constraints on variables and values could be user-defined. See also the paragraph `Discussion' for using rule inference in a user-guided manner.