Skip to main content

solow_preprocessing/
polynomial.rs

1//! [`PolynomialFeatures`] — expand a feature matrix into all monomials
2//! up to a given total degree.
3//!
4//! The column ordering matches `sklearn.preprocessing.PolynomialFeatures`
5//! and follows a **graded lexicographic** enumeration: first ascending
6//! total degree, then ascending lexicographic on the exponent vector.
7//!
8//! # Complexity
9//!
10//! For `d` input features and total degree `p`:
11//!
12//! * Output columns: `include_bias`: `C(d + p, p)`,
13//!   `interaction_only`: `Σ_{k=0..=p} C(d, k)`.
14//! * Time: `O(n · m)` where `m` is the output-column count.
15//! * Space: `O(m + n · m)` for the returned matrix.
16//!
17//! # Example
18//!
19//! Degree 3, `include_bias = true`, `interaction_only = false`, `d = 2`
20//! produces the columns
21//! `[1, x0, x1, x0², x0·x1, x1², x0³, x0²·x1, x0·x1², x1³]` — the same
22//! ordering scikit-learn returns.
23
24use ndarray::{Array2, ArrayView2};
25use solow_core::{Error, Result};
26
27/// Build the full monomial-index vector for the given configuration.
28///
29/// Each entry is the exponent vector (length `d`, sums to `≤ degree`).
30/// The vector is graded-lexicographic; the first entry is the all-zeros
31/// bias when `include_bias`.
32fn monomials(d: usize, degree: usize, include_bias: bool, interaction_only: bool) -> Vec<Vec<u32>> {
33    let mut out: Vec<Vec<u32>> = Vec::new();
34    for total in 0..=degree {
35        if total == 0 {
36            if include_bias {
37                out.push(vec![0u32; d]);
38            }
39            continue;
40        }
41        // Enumerate every compositions-of-`total`-into-`d`-nonnegative-parts.
42        let mut current = vec![0u32; d];
43        enumerate(d, total as u32, 0, &mut current, &mut out, interaction_only);
44    }
45    out
46}
47
48fn enumerate(
49    d: usize,
50    remaining: u32,
51    idx: usize,
52    current: &mut Vec<u32>,
53    out: &mut Vec<Vec<u32>>,
54    interaction_only: bool,
55) {
56    if idx == d - 1 {
57        current[idx] = remaining;
58        if !interaction_only || current.iter().all(|&e| e <= 1) {
59            out.push(current.clone());
60        }
61        current[idx] = 0;
62        return;
63    }
64    let cap = if interaction_only { 1 } else { remaining };
65    // Iterate the leading-variable exponent from high to low so the overall
66    // enumeration matches scikit-learn's graded-lexicographic order
67    // (`(2, 0), (1, 1), (0, 2)` at total degree 2 rather than the reverse).
68    for k in (0..=cap.min(remaining)).rev() {
69        current[idx] = k;
70        enumerate(d, remaining - k, idx + 1, current, out, interaction_only);
71    }
72    current[idx] = 0;
73}
74
75/// Polynomial-feature expansion.
76///
77/// See the [module docs](crate::polynomial) for the column ordering and
78/// complexity.
79#[derive(Clone, Debug, PartialEq)]
80pub struct PolynomialFeatures {
81    /// Total polynomial degree.
82    pub degree: usize,
83    /// If `true`, only produce monomials in which every exponent is `0`
84    /// or `1` (no `x_j²` etc.).
85    pub interaction_only: bool,
86    /// If `true`, prepend the all-ones bias column.
87    pub include_bias: bool,
88    /// Cached monomial exponents populated at `fit` time.
89    exponents: Option<Vec<Vec<u32>>>,
90}
91
92impl PolynomialFeatures {
93    /// New expansion at the given degree (`include_bias = true`,
94    /// `interaction_only = false`).
95    pub fn new(degree: usize) -> Self {
96        Self {
97            degree,
98            interaction_only: false,
99            include_bias: true,
100            exponents: None,
101        }
102    }
103
104    /// Set `interaction_only`.
105    pub fn interaction_only(mut self, flag: bool) -> Self {
106        self.interaction_only = flag;
107        self
108    }
109
110    /// Set `include_bias`.
111    pub fn include_bias(mut self, flag: bool) -> Self {
112        self.include_bias = flag;
113        self
114    }
115
116    /// Cache the monomial list.
117    pub fn fit(&mut self, x: ArrayView2<'_, f64>) -> Result<()> {
118        if x.ncols() == 0 {
119            return Err(Error::Value(
120                "PolynomialFeatures::fit: x must have at least one column".into(),
121            ));
122        }
123        self.exponents = Some(monomials(
124            x.ncols(),
125            self.degree,
126            self.include_bias,
127            self.interaction_only,
128        ));
129        Ok(())
130    }
131
132    /// Number of output columns for a `d`-column input.
133    pub fn output_columns(&self, d: usize) -> usize {
134        monomials(d, self.degree, self.include_bias, self.interaction_only).len()
135    }
136
137    /// Apply the expansion.
138    pub fn transform(&self, x: ArrayView2<'_, f64>) -> Result<Array2<f64>> {
139        let d = x.ncols();
140        let exps = monomials(d, self.degree, self.include_bias, self.interaction_only);
141        let m = exps.len();
142        let mut out = Array2::<f64>::zeros((x.nrows(), m));
143        for i in 0..x.nrows() {
144            for (k, exp) in exps.iter().enumerate() {
145                let mut acc = 1.0_f64;
146                for j in 0..d {
147                    let e = exp[j];
148                    if e == 0 {
149                        continue;
150                    }
151                    let v = x[[i, j]];
152                    // fast integer powers up to a small degree
153                    let mut p = 1.0;
154                    for _ in 0..e {
155                        p *= v;
156                    }
157                    acc *= p;
158                }
159                out[[i, k]] = acc;
160            }
161        }
162        Ok(out)
163    }
164
165    /// One-call fit + transform.
166    pub fn fit_transform(&self, x: ArrayView2<'_, f64>) -> Result<Array2<f64>> {
167        // Fit is stateless w.r.t. transform (the monomial list is
168        // recomputed) but we keep the sklearn signature.
169        let mut clone = self.clone();
170        clone.fit(x)?;
171        clone.transform(x)
172    }
173
174    /// Exponent vectors, one per output column.
175    ///
176    /// Returned only when `fit` has run; otherwise use
177    /// [`PolynomialFeatures::exponents_for`].
178    pub fn exponents(&self) -> Option<&[Vec<u32>]> {
179        self.exponents.as_deref()
180    }
181
182    /// Compute the exponent vectors for a `d`-column input without
183    /// consuming state.
184    pub fn exponents_for(&self, d: usize) -> Vec<Vec<u32>> {
185        monomials(d, self.degree, self.include_bias, self.interaction_only)
186    }
187}
188
189#[cfg(test)]
190mod tests {
191    use super::*;
192    use approx::assert_abs_diff_eq;
193    use ndarray::array;
194
195    #[test]
196    fn degree_2_matches_hand_derivation() {
197        let x = array![[2.0, 3.0]];
198        let poly = PolynomialFeatures::new(2).include_bias(true);
199        let out = poly.fit_transform(x.view()).unwrap();
200        // Columns: 1, x0, x1, x0², x0·x1, x1².
201        assert_eq!(out.dim(), (1, 6));
202        assert_abs_diff_eq!(out[[0, 0]], 1.0, epsilon = 1e-12);
203        assert_abs_diff_eq!(out[[0, 1]], 2.0, epsilon = 1e-12);
204        assert_abs_diff_eq!(out[[0, 2]], 3.0, epsilon = 1e-12);
205        assert_abs_diff_eq!(out[[0, 3]], 4.0, epsilon = 1e-12);
206        assert_abs_diff_eq!(out[[0, 4]], 6.0, epsilon = 1e-12);
207        assert_abs_diff_eq!(out[[0, 5]], 9.0, epsilon = 1e-12);
208    }
209
210    #[test]
211    fn interaction_only_drops_pure_powers() {
212        let x = array![[2.0, 3.0, 5.0]];
213        let poly = PolynomialFeatures::new(2)
214            .include_bias(false)
215            .interaction_only(true);
216        let out = poly.fit_transform(x.view()).unwrap();
217        // Columns: x0, x1, x2, x0·x1, x0·x2, x1·x2.
218        assert_eq!(out.dim(), (1, 6));
219        assert_abs_diff_eq!(out[[0, 3]], 6.0, epsilon = 1e-12); // x0·x1
220        assert_abs_diff_eq!(out[[0, 4]], 10.0, epsilon = 1e-12); // x0·x2
221        assert_abs_diff_eq!(out[[0, 5]], 15.0, epsilon = 1e-12); // x1·x2
222    }
223
224    #[test]
225    fn column_count_matches_binomial_identity() {
226        for d in 1..6 {
227            for degree in 0..5 {
228                let full = PolynomialFeatures::new(degree)
229                    .include_bias(true)
230                    .output_columns(d);
231                // C(d + p, p)
232                let expected: usize = (1..=degree).fold(1usize, |acc, k| acc * (d + k) / k);
233                assert_eq!(full, expected, "d = {d}, p = {degree}");
234            }
235        }
236    }
237}