dtrees_rs/algorithms/optimal/rules/
discrepancy.rs

1use crate::algorithms::optimal::rules::core::Reason;
2use crate::algorithms::optimal::rules::helpers::{Monotonic, StepStrategy};
3use crate::algorithms::optimal::rules::{Rule, RuleContext, RuleResult, RuleState};
4
5/// Limited discrepancy search (LDS-DL8.5).
6///
7/// Features are ranked by the heuristic at each node, and taking the feature
8/// of rank `i` costs a discrepancy of `i`. A pass explores only the paths
9/// whose total discrepancy is within the budget; relaxing the rule raises the
10/// budget, following its [`StepStrategy`], until it covers the whole space.
11///
12/// Kiossou, Schaus, Nijssen and Houndji, *Time Constrained DL8.5 Using
13/// Limited Discrepancy Search* (ECML PKDD 2022).
14pub struct DiscrepancyRule {
15    limit: usize,
16    budget: usize,
17    increment: Box<dyn StepStrategy>,
18    priority: u8,
19    delay: u8,
20    state: RuleState,
21    relaxable: bool,
22}
23
24impl Default for DiscrepancyRule {
25    fn default() -> Self {
26        Self {
27            limit: usize::MAX,
28            budget: 0,
29            increment: Box::new(Monotonic::new(1)),
30            priority: 100,
31            delay: 0,
32            state: RuleState::Disabled,
33            relaxable: true,
34        }
35    }
36}
37
38impl DiscrepancyRule {
39    /// A rule whose budget grows following `increment`, up to `limit`.
40    pub fn new(limit: usize, increment: Box<dyn StepStrategy>) -> Self {
41        Self {
42            limit,
43            budget: 0,
44            increment,
45            priority: 100,
46            delay: 0,
47            state: RuleState::Disabled,
48            relaxable: true,
49        }
50    }
51
52    /// Sets the evaluation priority.
53    pub fn with_priority(mut self, priority: u8) -> Self {
54        self.priority = priority;
55        self
56    }
57
58    /// Sets the number of passes before the rule takes effect.
59    pub fn with_delay(mut self, delay: u8) -> Self {
60        self.delay = delay;
61        self
62    }
63
64    /// Sets the budget of the first pass.
65    pub fn with_budget(mut self, budget: usize) -> Self {
66        self.budget = budget;
67        self
68    }
69
70    /// Lowers the limit to the largest discrepancy a tree of
71    /// `remaining_depth` levels over `nb_candidates` features can have.
72    pub fn update_to_true_limit(&mut self, nb_candidates: usize, remaining_depth: usize) {
73        let mut max_discrepancy = nb_candidates;
74        for i in 1..remaining_depth {
75            max_discrepancy += nb_candidates.saturating_sub(i);
76        }
77        self.limit = self.limit.min(max_discrepancy);
78    }
79}
80
81impl Rule for DiscrepancyRule {
82    fn evaluate(&self, context: &RuleContext) -> RuleResult {
83        if context.discrepancy > self.budget {
84            RuleResult::stop_with_bound(f64::INFINITY, Reason::RuleReason)
85        } else {
86            RuleResult::continue_search()
87        }
88    }
89
90    fn priority(&self) -> u8 {
91        self.priority
92    }
93
94    fn description(&self) -> String {
95        "Discrepancy rule".to_string()
96    }
97
98    fn state(&self) -> RuleState {
99        self.state
100    }
101
102    fn activate(&mut self) {
103        self.state = RuleState::Active
104    }
105
106    fn deactivate(&mut self) {
107        self.state = RuleState::Disabled
108    }
109
110    fn relax(&mut self) {
111        if !self.is_active() {
112            return;
113        }
114        if self.is_relaxable() && self.budget >= self.limit {
115            self.deactivate();
116            return;
117        }
118        self.budget = self.increment.next();
119        if self.budget >= self.limit {
120            self.budget = self.limit;
121        }
122    }
123
124    fn is_relaxable(&self) -> bool {
125        self.relaxable
126    }
127
128    fn delay(&self) -> u8 {
129        self.delay
130    }
131
132    fn as_any(&self) -> &dyn std::any::Any {
133        self
134    }
135
136    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
137        self
138    }
139}
dtrees_rs/algorithms/optimal/rules/discrepancy.rs

dtrees_rs/algorithms/optimal/rules/
discrepancy.rs
