If "age > 60" and "patient has previously had a heart attack", then do not perform surgery, the risk of negative outcome is 60%

Example from the field of scoring

If "home phone is listed on the form" and "salary > $2000" and "loan amount < $5000" then the loan can be issued, default risk is 5%

1. Selection of rule family for finding regularities
2. Rule generation
3. Rule regularity selection

Regularity is a highly informative, interpretable, single-class classifier with rejections.

1. Threshold condition (decision stump):
$$R(x) = [f_j(x) \leq {\color{orange}a_j}] \text{ or } [{\color{orange}a_j} \leq f_j(x) \leq {\color{orange}b_j}]$$
2. Conjunction of threshold conditions:
$$R(x) = \bigwedge\limits_{j \in {\color{orange}J}} [{\color{orange}a_j} \leq f_j(x) \leq {\color{orange}b_j}]$$

4. Half-plane — linear threshold function:
$$R(x) = \left[\sum\limits_{j \in {\color{orange}J}} {\color{orange}w_j} f_j(x) \geq {\color{orange}w_0}\right]$$
5. Sphere — proximity threshold function:
$$R(x) = [(\rho(x, {\color{orange}x_0}) \leq {\color{orange}w_0}]$$
6. AVE — algorithms for calculating estimates [Yu. I. Zhuravlev, 1971]:
$$\rho(x, {\color{orange}x_0}) = \max\limits_{j \in {\color{orange}J}} {\color{orange}w_j} |f_j(x) - f_j({\color{orange}x_0})|$$

Input: Training sample $X^\ell$

Output: Set of rules $Z$

1. Initial set of rules $Z$
2. repeat
• $Z^\prime :=$ set of local modifications of the rules $R \in Z$
• remove overly similar rules from $Z \cup Z^\prime$
• $Z :=$ most informative rules from $Z \cup Z^\prime$
3. until the rules keep improving
4. return $Z$

• Genetic (evolutionary) algorithms
• Guided Local Search (GLS) — adjusting penalties during the search process
• Branch and bound method — discarding areas that definitely do not contain optimal solutions

Example. Family of conjunctions of threshold conditions:

$$ R(x) = \bigwedge\limits_{j \in {\color{orange}J}} [{\color{orange}a_j} \leq f_j(x) \leq {\color{orange}b_j}]$$

Local modifications of a conjunctive rule:

• varying one of the thresholds ${\color{orange}a_j}$ or ${\color{orange}b_j}$
• varying both thresholds ${\color{orange}a_j}$ and ${\color{orange}b_j}$ simultaneously
• adding feature ${\color{orange}f_j}$ to ${\color{orange}J}$ with variation of thresholds ${\color{orange} a_j, b_j}$
• removing feature ${\color{orange}f_j}$ from ${\color{orange}J}$

• When removing a feature (pruning), informativeness is usually evaluated on a control sample (hold-out)
• The same methods are suitable for optimizing the set ${\color{orange}J}$ as for feature selection

• Entropy information gain criterion:

$ \text{IGain}(p, n) = h\left(\frac{P}{\ell} \right) - \frac{p+n}{\ell} h\left(\frac{p}{p+n} \right) - \frac{\ell-p-n}{\ell} h\left(\frac{P-p}{\ell-p-n} \right) \to \max $

$ h(q) = -q \log_2 q - (1-q) \log_2 (1 - q)$ — entropy of “two-class distribution”

• Gini Impurity:

$\text{IGini}(p, n) = \text{IGain}(p, n)$ when $h(q) = 4q(1 - q)$

• Boosting a criterion [Cohen, Singer, 1999]:
$$\sqrt{p} - \sqrt{n} \to \max$$

• Normalized boosting criterion:
$$\sqrt{\frac{p}{P}} - \sqrt{\frac{n}{N}} \to \max$$

• Weighted Voting (linear classifier with weights $w_{yt}$):

$a(x) = \arg\max_{y \in Y} \sum_{t=1}^{T} w_{yt} R_{yt}(x)$

• Simple Voting (majority committee):

$a(x) = \arg\max_{y \in Y} \frac{1}{T_y}\sum_{t=1}^{T_y} R_{yt}(x)$

• Decision List (seniority committee), \(c_t \in Y \):

Answer: Mean Accuracy

1. FUNCTION TreeGrowing($U \subseteq X_\ell$) $\mapsto$ root of a tree $v$
2. if StopCriteria($U$) then
   return a new leaf $v$, taking $y_v$ := Major*($U$)
3. find the most profitable feature for branching the tree:

   $f_v = \arg\max\limits_{f \in F}$ Gain($f, U$)

4. if Gain ($f_v$, $U$) < $G_0$ then
   return a new leaf $v$, taking $y_v$ := Major($U$)
5. create a new internal node $v$ with the function $f_v$
6. for all $k \in D_v$ $U_k = \{x \in U: f_v(x) = k\}, S_v(k)$ := TreeGrowing($U_k$)
7. return $v$

Majority rule: Major($U$) := $\arg\max P(y|U)$

During Training

• If \(f_v(x_i)\) is undefined \(\Rightarrow\ x_i\) is excluded from \(U\) for \(\text{Gain}(f_v, U)\)
• \(q_{vk} = \frac{|U_k|}{|U|}\) — probability estimate of the \(k\)-th branch, \(v \in V_{\text{internal}}\)
• \(P(y|x, v) = \frac{1}{|U|} \sum\limits_{x_i \in U}[y_i = y]\) for all \(v \in V_{\text{leaf}}\)

During Classification

• If \(f_v(x)\) is undefined \(\Rightarrow\) take the distribution proportionally from the child
\[s = S_v(f_v(x)): P(y|x, v) = P(y|x, s)\]
• If \(f_v(x)\) is undefined \(\Rightarrow\) proportional distribution: \[P(y|x, v) = \sum\limits_{k \in D_v} q_{vk} P(y | x, S_v(k)))\]
• Final decision — the most probable class: \(a(x) = \arg\max\limits_{y \in Y} P(y|x, v_0)\)

Advantages:

• Interpretability and simplicity of classification
• Flexibility: the set \(F\) can be varied
• Handles heterogeneous data and data with missing values
• Linear complexity in relation to the length of the sample: \(O(|F|h\ell)\)
• There are no classification refusals

Disadvantages:

• Greedy strategy overcomplicates the tree structure leading to severe overfitting
• Sample fragmentation: the further \(v\) from the root, the less statistical reliability in the choice of \(f_v, y_v\)
• High sensitivity to noise, composition of the sample, and the informativeness criterion

Tree Pruning

\(X^q\) — Independent validation set, \(q \approx 0.5\ell\)

1. for all \(v \in V_{\text{internal}}\)
2. \(X_v^q :=\) subset of instances \(X^q\) that reach \(v\)
3. if \(X_v^q = \emptyset\) then return a new leaf \(v\), with \(y_v := \text{Major}(U)\)
4. Count the number of misclassifications for \(X_v^q\) classified in different ways:
• \(\ \ \text{Err}(v)\) — by the subtree rooted at \(v\)
• \(\ \ \text{Err}_k(v)\) — by the subtree \(S_v(k)\), for \(k \in D_v\)
• \(\ \ \text{Err}_c(v)\) — by class \(c \in Y\)
5. Depending on which is minimal:
• Keep the subtree \(v\)
• Replace the subtree \(v\) with the child \(S_v(k)\)
• Replace the subtree \(v\) with a leaf, with \(y_v := \arg\min\limits_{c \in Y} \text{Err}_c(v)\)

Let \( U \) be the set of objects \( x_i \) that reach vertex \( v \)

Uncertainty measure — mean squared error:

\[ \Phi(U) = \min_{y \in Y} \frac{1}{|U|} \sum\limits_{x_i \in U} (y - y_i)^2 \]

The value \( y_v \) in the terminal vertex \( v \) is the LSE solution:

\[ y_v = \frac{1}{|U|} \sum\limits_{x_i \in U} y_i \]

Regression tree \( a(x) \) is a piecewise constant function.

As \(\alpha\) increases, the tree is progressively simplified. Moreover, the sequence of nested trees is unique. From this sequence, the tree with the minimum error on the test sample (Hold-Out) is selected.

For the case of classification, a similar pruning strategy is used, but with the Gini criterion.

Purpose: to reduce the enumeration of predicates of the form \([{\color{orange}\alpha} \leq f(x) \leq {\color{orange}\beta}]\)

Given: a set of real-valued feature vectors \(f(x_i), x_i \in X^l\)

Find: the best (in any sense) division of the feature value range into a relatively small number of zones:

• \(\zeta_0(x) = [f(x) < d_1]\)
• \(\zeta_s(x) = [d_s \leq f(x) < d_{s+1}], s = 1, \dots, r-1\)
• \(\zeta_r(x) = [d_r \leq f(x)]\)

• Greedy Information Maximization by Merging
• Division into Equally Powered Subsamples
• Partitioning by a Uniform Grid of "Convenient" Values
• Combining Several Partitions — for Example, Uniform and Median

• Basic requirements for logical regularities:
  
  • interpretability
  • informative
  • diversity
• Advantages of decision trees:
  
  • interpretability
  • mixed types of data allowed
  • capability to bypass missing data
  • Drawbacks of decision trees:
  • overfitting
  • fragmentation
  • instability to noise, composition of the sample, criteria
• Ways to eliminate these drawbacks:
  
  • pruning
  • regularization
  • ensembles (forests) of trees — coming soon!