contree/common/
mod.rs

1mod budget_schedule;
2mod loss;
3mod outcome;
4
5pub use budget_schedule::{Budget, BudgetSchedule, PassReport, ScheduleBounds, ScheduleKind};
6pub use loss::{Leaf, LeafLoss, Loss, LossInput, Skipping};
7pub use outcome::{FitOutcome, SearchError, SearchStatus};
8
9use serde::{Deserialize, Serialize};
10use std::fmt;
11use std::str::FromStr;
12
13/// Which candidate threshold the search evaluates next inside an interval of
14/// candidates.
15#[derive(Default, Copy, Debug, Clone, PartialOrd, PartialEq, Eq, Serialize, Deserialize)]
16#[serde(rename_all = "lowercase")]
17pub enum PointSelector {
18    /// The middle candidate, which bisects the interval. The default.
19    #[default]
20    Mid,
21    /// Candidates are tried one at a time instead of by bisection, in Gini
22    /// order when the heuristic is on. The anytime search limits how many are
23    /// tried with its split budget.
24    First,
25    /// A uniformly random candidate.
26    Random,
27}
28
29impl PointSelector {
30    /// The spelling used on the command line and in the Python API.
31    pub const fn as_str(self) -> &'static str {
32        match self {
33            Self::Mid => "mid",
34            Self::First => "first",
35            Self::Random => "random",
36        }
37    }
38
39    /// Every selector, in declaration order.
40    pub const ALL: [Self; 3] = [Self::Mid, Self::First, Self::Random];
41}
42
43impl fmt::Display for PointSelector {
44    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
45        f.write_str(self.as_str())
46    }
47}
48
49impl FromStr for PointSelector {
50    type Err = String;
51
52    fn from_str(s: &str) -> Result<Self, Self::Err> {
53        match s.trim().to_ascii_lowercase().as_str() {
54            "mid" => Ok(Self::Mid),
55            "first" => Ok(Self::First),
56            "random" => Ok(Self::Random),
57            other => Err(format!(
58                "unknown split selection strategy `{other}` (expected one of: mid, first, random)"
59            )),
60        }
61    }
62}
63
64/// The cost of a tree: the sum of the costs of its leaves. For the built-in
65/// loss, the number of misclassified instances.
66pub type Cost = f64;
67
68/// Settings of a search, and the per-node state derived from them.
69#[derive(Copy, Clone, Debug)]
70pub struct SearchConfig {
71    /// Maximum depth of the tree (remaining depth, below the root).
72    pub max_depth: usize,
73    /// Minimum number of instances in each leaf.
74    pub min_sup: usize,
75    /// Time limit in seconds.
76    pub max_time: f64,
77    /// Error gap tolerated with respect to the optimum; 0 for an exact search.
78    pub max_gap: Cost,
79    /// Initial upper bound on the error.
80    pub max_error: Cost,
81    /// The smallest difference between two different costs: 1 for
82    /// misclassification, whose costs are whole numbers, 0 for a custom loss.
83    /// A search that finds no tree within a bound `ub` then proves the cost
84    /// is at least `ub + cost_step`.
85    pub cost_step: Cost,
86    /// Whether thresholds are skipped; see [`Skipping`].
87    pub skipping: Skipping,
88    /// Whether this configuration is the root's.
89    pub is_root: bool,
90    /// Order features and thresholds by Gini impurity.
91    pub use_heuristic: bool,
92    /// Use the specialised solver for depth-2 subtrees.
93    pub fast_d2: bool,
94    /// How thresholds are picked inside an interval.
95    pub point_selector: PointSelector,
96    /// Number of passes run so far (anytime search).
97    pub nb_runs: usize,
98    /// Discrepancy used on the path to this node (anytime search).
99    pub discrepancy: usize,
100    /// Discrepancy budget of the current pass (anytime search).
101    pub budget: usize,
102}
103
104impl SearchConfig {
105    /// A root configuration with the given settings.
106    #[allow(clippy::too_many_arguments)]
107    pub fn new(
108        min_sup: usize,
109        max_depth: usize,
110        max_time: f64,
111        max_gap: Cost,
112        max_error: Cost,
113        use_heuristic: bool,
114        fast_d2: bool,
115        split_strategy: PointSelector,
116    ) -> Self {
117        Self {
118            max_depth,
119            min_sup,
120            max_time,
121            max_gap,
122            max_error,
123            cost_step: 1.0,
124            skipping: Skipping::Auto,
125            is_root: true,
126            use_heuristic,
127            fast_d2,
128            point_selector: split_strategy,
129            nb_runs: 0,
130            discrepancy: 0,
131            budget: 0,
132        }
133    }
134
135    /// The cost step for a loss: misclassification costs are counts of
136    /// instances, so whole numbers. A custom loss's costs may be any number,
137    /// so there is no smallest difference between two of them.
138    pub fn cost_step_for(loss: &Loss) -> Cost {
139        if loss.is_misclassification() {
140            1.0
141        } else {
142            0.0
143        }
144    }
145
146    /// The configuration of the first child searched: one level shallower,
147    /// with part of the gap.
148    pub fn derive_left(&self) -> Self {
149        let mut left_config = *self;
150        left_config.max_depth -= 1;
151        left_config.is_root = false;
152        left_config.max_gap = ((self.max_gap - (self.max_gap / 2.0).ceil()) / 2.0).floor();
153        left_config
154    }
155
156    /// The configuration of the second child searched, given the gap already
157    /// handed to the first.
158    pub fn derive_right(&self, left_gap: Cost) -> Self {
159        let mut right_config = *self;
160        right_config.max_depth -= 1;
161        right_config.is_root = false;
162        right_config.max_gap = (self.max_gap - (self.max_gap / 2.0).ceil() - left_gap).max(0.0);
163        right_config
164    }
165}
166
167/// Counters collected during a search.
168#[derive(Copy, Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
169pub struct Statistics {
170    /// Number of cached subproblems.
171    pub cache_size: usize,
172    /// Subproblems answered from the cache.
173    pub cache_hits: usize,
174    /// Calls to the general search.
175    pub general_solver_call: usize,
176    /// Calls to the depth-2 solver.
177    pub specialized_solver_call: usize,
178    /// Number of training instances.
179    pub num_samples: usize,
180    /// Number of features.
181    pub num_features: usize,
182    /// Training cost of the best tree.
183    pub error: Cost,
184    /// Moves of instances in the depth-2 scan that broke the assumption
185    /// threshold skipping makes about the loss. Only counted when skipping
186    /// is forced on for a custom loss; see [`Skipping`].
187    pub skipping_violations: usize,
188    /// Search time in seconds.
189    pub duration: f64,
190}
191
192/// `(misclassifications, majority class)` of a leaf with the given class
193/// counts. Ties go to the highest class index.
194pub fn classification_error(classes_support: &[usize]) -> (Cost, usize) {
195    let mut max_idx = 0;
196    let mut max_value = 0;
197    let mut total = 0;
198    for (idx, &value) in classes_support.iter().enumerate() {
199        total += value;
200        if value >= max_value {
201            max_value = value;
202            max_idx = idx;
203        }
204    }
205    ((total - max_value) as Cost, max_idx)
206}
contree/common/mod.rs

contree/common/
mod.rs
