dtrees_rs/algorithms/optimal/rules/
core.rs

1use serde::{Deserialize, Serialize};
2use std::fmt::{Debug, Display};
3
4/// Why the search stopped at a node.
5#[derive(Debug, Clone, Copy, Serialize, Deserialize, Default, Eq, PartialEq)]
6pub enum Reason {
7    /// The node was fully explored.
8    Done,
9    /// The time limit was reached.
10    TimeLimitReached,
11    /// The node's lower bound reaches its upper bound: no subtree can help.
12    LowerBoundConstrained,
13    /// The node is at the maximum depth and becomes a leaf.
14    MaxDepthReached,
15    /// The node has too few instances to be split.
16    NotEnoughSupport,
17    /// No feature can split the node.
18    NoCandidates,
19    /// The node has zero error as a leaf.
20    PureNode,
21    /// The node was solved by the depth-2 solver.
22    FromSpecializedAlgorithm,
23    /// A relaxable search rule cut the search; a later pass may go further.
24    RuleReason,
25    /// No reason recorded.
26    #[default]
27    None,
28}
29
30/// What a rule decided for a node.
31#[derive(Debug, Clone)]
32pub struct RuleResult {
33    /// Whether the search goes on below the node.
34    pub continue_search: bool,
35    /// A new upper bound to record on the node, if any.
36    pub modified_bound: Option<f64>,
37    /// Why the search stops, when it does.
38    pub reason: Reason,
39    /// Mark the node as solved optimally.
40    pub optimal: Option<bool>,
41    /// Turn the node into a leaf.
42    pub leaf: Option<bool>,
43}
44
45impl RuleResult {
46    /// Lets the search continue.
47    pub fn continue_search() -> Self {
48        Self {
49            continue_search: true,
50            modified_bound: None,
51            reason: Reason::None,
52            optimal: None,
53            leaf: None,
54        }
55    }
56
57    /// Stops the search at the node.
58    pub fn stop_search(reason: Reason) -> Self {
59        Self {
60            continue_search: false,
61            modified_bound: None,
62            reason,
63            optimal: None,
64            leaf: None,
65        }
66    }
67
68    /// Stops the search at the node and records `bound` as its upper bound.
69    pub fn stop_with_bound(bound: f64, reason: Reason) -> Self {
70        Self {
71            continue_search: false,
72            modified_bound: Some(bound),
73            reason,
74            optimal: None,
75            leaf: None,
76        }
77    }
78
79    /// Also marks the node as solved optimally.
80    pub fn optimal(mut self) -> Self {
81        self.optimal = Some(true);
82        self
83    }
84
85    /// Also turns the node into a leaf.
86    pub fn leaf(mut self) -> Self {
87        self.leaf = Some(true);
88        self
89    }
90
91    /// Replaces the reason.
92    pub fn with_reason(mut self, reason: Reason) -> Self {
93        self.reason = reason;
94        self
95    }
96}
97
98/// Whether a rule is applied.
99#[derive(Debug, Clone, Copy, PartialEq, Eq)]
100pub enum RuleState {
101    Active,
102    Relaxed,
103    Disabled,
104}
105
106impl Display for RuleState {
107    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
108        match self {
109            RuleState::Active => write!(f, "Active"),
110            RuleState::Relaxed => write!(f, "Relaxed"),
111            RuleState::Disabled => write!(f, "Disabled"),
112        }
113    }
114}
115
116/// What the rules know about the node being evaluated.
117#[derive(Debug)]
118pub struct RuleContext {
119    /// Depth of the node (the root is at 0).
120    pub depth: usize,
121    /// Error the subtree must beat to be of use to its parent.
122    pub upper_bound: f64,
123    /// Proven lower bound on the node's error.
124    pub node_lower_bound: f64,
125    /// Upper bound the node was last solved under (infinite if never).
126    pub node_upper_bound: f64,
127    /// The item (feature and branch) leading to the node.
128    pub item: usize,
129    /// Number of instances in the node.
130    pub support: usize,
131    /// Rank of the node's feature among its siblings.
132    pub position: usize,
133    /// Sum of the ranks along the path from the root.
134    pub discrepancy: usize,
135    /// Accumulated heuristic score lost along the path by not taking the
136    /// best-ranked feature.
137    pub gain: f64,
138    /// Best error found so far for the node.
139    pub error: f64,
140    /// Error of the node as a leaf.
141    pub leaf_error: f64,
142}
143
144impl Default for RuleContext {
145    fn default() -> Self {
146        Self {
147            depth: 0,
148            upper_bound: 0.0,
149            node_lower_bound: 0.0,
150            node_upper_bound: f64::INFINITY,
151            item: 0,
152            support: 0,
153            position: 0,
154            discrepancy: 0,
155            gain: 0.0,
156            error: f64::INFINITY,
157            leaf_error: f64::INFINITY,
158        }
159    }
160}
161
162impl RuleContext {
163    pub fn depth(&mut self, depth: usize) {
164        self.depth = depth;
165    }
166    pub fn upper_bound(&mut self, upper_bound: f64) {
167        self.upper_bound = upper_bound;
168    }
169
170    pub fn node_lower_bound(&mut self, node_lower_bound: f64) {
171        self.node_lower_bound = node_lower_bound;
172    }
173
174    pub fn node_upper_bound(&mut self, node_upper_bound: f64) {
175        self.node_upper_bound = node_upper_bound;
176    }
177
178    pub fn item(&mut self, item: usize) {
179        self.item = item;
180    }
181
182    pub fn support(&mut self, support: usize) {
183        self.support = support;
184    }
185
186    pub fn position(&mut self, position: usize) {
187        self.position = position;
188    }
189
190    pub fn gain(&mut self, gain: f64) {
191        self.gain = gain;
192    }
193
194    pub fn error(&mut self, error: f64) {
195        self.error = error;
196    }
197
198    pub fn leaf_error(&mut self, error: f64) {
199        self.leaf_error = error;
200    }
201
202    pub fn discrepancy(&mut self, discrepancy: usize) {
203        self.discrepancy = discrepancy;
204    }
205}
206
207/// A condition checked at every node of the search.
208pub trait Rule: std::any::Any + Send + Sync {
209    /// Decides whether the search continues below the node.
210    fn evaluate(&self, context: &RuleContext) -> RuleResult;
211
212    /// Rules with a higher priority are evaluated first.
213    fn priority(&self) -> u8;
214
215    /// A short human-readable name.
216    fn description(&self) -> String;
217
218    /// The current state of the rule.
219    fn state(&self) -> RuleState;
220
221    /// Whether the rule is applied.
222    fn is_active(&self) -> bool {
223        self.state() == RuleState::Active
224    }
225
226    /// Starts applying the rule; called before the first pass.
227    fn activate(&mut self) {}
228
229    /// Whether the rule restricts the search only temporarily. A search whose
230    /// pass was cut by a relaxable rule is not finished.
231    fn is_relaxable(&self) -> bool {
232        true
233    }
234
235    /// Stops applying the rule.
236    fn deactivate(&mut self) {}
237
238    /// Widens the rule's budget before the next pass, or deactivates it once
239    /// the budget is at its limit.
240    fn relax(&mut self) {}
241
242    /// Resets any internal state, such as a timer.
243    fn reset(&mut self) {}
244
245    /// Number of passes to wait before the rule takes effect.
246    fn delay(&self) -> u8 {
247        0
248    }
249
250    /// Upcast used by [`RuleManager::get_rule_mut`](super::RuleManager::get_rule_mut).
251    fn as_any(&self) -> &dyn std::any::Any;
252
253    /// Mutable upcast used by [`RuleManager::get_rule_mut`](super::RuleManager::get_rule_mut).
254    fn as_any_mut(&mut self) -> &mut dyn std::any::Any;
255}
dtrees_rs/algorithms/optimal/rules/core.rs

dtrees_rs/algorithms/optimal/rules/
core.rs
