Oblique Split Algorithm

1. General Framework and Notation

1.1 Data and Parameter Definitions

• \(X \in \mathbb{R}^{N \times d}\): Feature matrix

• \(\mathbf{y} \in \{0,1,\ldots,K-1\}^N\) or \(\mathbb{R}^N\): Target variable (categorical for classification, continuous for regression)

• \(\mathbf{w} \in \mathbb{R}^d\): Optimization parameters defining the split hyperplane

• \(\boldsymbol{\omega} \in \mathbb{R}^N\): Sample weights

• \(\gamma\): Scaling parameter for the sigmoid function (controls the sharpness of the split)

• \(\epsilon\): Small constant for numerical stability

1.2 Basic Computations

For each sample \(i\):

\[ z_i = \mathbf{x}_i^\top\mathbf{w} \]

• Computes the projection of each sample onto the direction vector \(\mathbf{w}\)

\[ p_i = \sigma(\gamma z_i) = \frac{1}{1 + e^{-\gamma z_i}} \]

• Transforms the projection into a probability of belonging to the left child node

• Smoothed version of a hard split, allowing gradient-based optimization

1.3 Optimal Threshold Selection

After obtaining optimal weights \(\mathbf{w}\), we select the threshold \(t\) that minimizes the impurity measure:

\[ t^* = \arg\min_t \text{Impurity}(\{z_i \leq t\}) \]

where Impurity is either Gini impurity for classification or MSE for regression. In implementation, this threshold is chosen by an exact scan over the sorted projected values \(\{z_i\}_{i=1}^N\) after the weight optimization step.

2. Binary Classification

2.1 Soft Decision Tree Approach

Left Node	Right Node
\(S_L = \sum_{i=1}^N \omega_i p_i + \epsilon\)	\(S_R = \sum_{i=1}^N \omega_i(1-p_i) + \epsilon\)
\(M_L = \sum_{i=1}^N \omega_i p_i y_i\)	\(M_R = \sum_{i=1}^N \omega_i(1-p_i)y_i\)
\(P_{L1} = \frac{M_L}{S_L}\)	\(P_{R1} = \frac{M_R}{S_R}\)

These statistics track the weighted distribution of samples and their labels in each child node.

The optimization objective is to minimize:

\[ \mathcal{L}_{\text{Gini}}(\mathbf{w}) = S_L P_{L1}(1-P_{L1}) + S_R P_{R1}(1-P_{R1}) \]

The optimization requires computing several gradients:

1. Basic probability gradient:

\[ \frac{\partial p_i}{\partial z_i} = \gamma p_i(1-p_i) \]

2. Node sum gradients:

\[ \frac{\partial S_L}{\partial \mathbf{w}} = \sum_{i=1}^N \omega_i\frac{\partial p_i}{\partial z_i}\mathbf{x}_i \]

\[ \frac{\partial M_L}{\partial \mathbf{w}} = \sum_{i=1}^N \omega_i y_i\frac{\partial p_i}{\partial z_i}\mathbf{x}_i \]

3. Class probability gradient:

\[ \frac{\partial P_{L1}}{\partial \mathbf{w}} = \frac{S_L\frac{\partial M_L}{\partial \mathbf{w}} - M_L\frac{\partial S_L}{\partial \mathbf{w}}}{S_L^2} \]

4. Final gradient:

\[ \frac{\partial \mathcal{L}_{\text{Gini}}}{\partial \mathbf{w}} = \frac{\partial S_L}{\partial \mathbf{w}}P_{L1}(1-P_{L1}) + S_L\frac{\partial P_{L1}}{\partial \mathbf{w}}(1-2P_{L1}) + \frac{\partial S_R}{\partial \mathbf{w}}P_{R1}(1-P_{R1}) + S_R\frac{\partial P_{R1}}{\partial \mathbf{w}}(1-2P_{R1}) \]

2.2 Linear Classification Approach

This approach treats the split as a linear classification problem.

\[ \mathcal{L}_{\text{BCE}}(\mathbf{w}) = -\frac{1}{\sum_{i=1}^N \omega_i}\sum_{i=1}^N \omega_i[y_i\log(\sigma(\mathbf{x}_i^\top\mathbf{w})) + (1-y_i)\log(1-\sigma(\mathbf{x}_i^\top\mathbf{w}))] \]

\[ \frac{\partial \mathcal{L}_{\text{BCE}}}{\partial \mathbf{w}} = \frac{1}{\sum_{i=1}^N \omega_i}\mathbf{X}^\top(\boldsymbol{\omega} \odot (\sigma(\mathbf{X}\mathbf{w}) - \mathbf{y})) \]

3. Multiclass Classification

3.1 Soft Decision Tree Approach

Left Node	Right Node
\(C_{L,k} = \sum_{i:y_i=k} \omega_i p_i\)	\(C_{R,k} = \sum_{i:y_i=k} \omega_i(1-p_i)\)
\(S_L = \sum_{k=0}^{K-1} C_{L,k} + \epsilon\)	\(S_R = \sum_{k=0}^{K-1} C_{R,k} + \epsilon\)
\(P_{L,k} = \frac{C_{L,k}}{S_L}\)	\(P_{R,k} = \frac{C_{R,k}}{S_R}\)

These statistics track the weighted distribution of samples for each class in the child nodes.

The optimization objective is to minimize:

\[ \mathcal{L}_{\text{MultiGini}}(\mathbf{w}) = S_L \sum_{k=0}^{K-1} P_{L,k}(1-P_{L,k}) + S_R \sum_{k=0}^{K-1} P_{R,k}(1-P_{R,k}) \]

The optimization requires computing several gradients:

1. Basic probability gradient:

\[ \frac{\partial p_i}{\partial z_i} = \gamma p_i(1-p_i) \]

2. Total soft mass gradient:

\[ \frac{\partial S_L}{\partial \mathbf{w}} = \sum_{i=1}^N \omega_i\frac{\partial p_i}{\partial z_i}\mathbf{x}_i \]

3. Final gradient.

Define

\[ v_i = 2\,\omega_i\frac{\partial p_i}{\partial z_i}\left(P_{R,y_i} - P_{L,y_i}\right) \]

Then

\[ \frac{\partial \mathcal{L}_{\text{MultiGini}}}{\partial \mathbf{w}} = \mathbf{X}^\top \mathbf{v} + \frac{\partial S_L}{\partial \mathbf{w}} \left( \sum_{k=0}^{K-1} P_{R,k}(1-P_{R,k}) - \sum_{k=0}^{K-1} P_{L,k}(1-P_{L,k}) \right) \]

3.2 One-vs-Rest Approach

For \(K\) classes, we train \(K\) binary classifiers where for each classifier \(k\):

• Class \(k\) samples are labeled as 1

• All other class samples are labeled as 0

The final decision is made by selecting the class whose model gives the minimum loss:

\[ k^* = \arg\min_k \mathcal{L}_k(\mathbf{w}_k) \]

4. Regression

4.1 Soft Decision Tree Approach

Left Node	Right Node
\(S_L = \sum_{i=1}^N \omega_i p_i + \epsilon\)	\(S_R = \sum_{i=1}^N \omega_i(1-p_i) + \epsilon\)
\(M_L = \sum_{i=1}^N \omega_i p_i y_i\)	\(M_R = \sum_{i=1}^N \omega_i(1-p_i)y_i\)
\(m_L = \frac{M_L}{S_L}\)	\(m_R = \frac{M_R}{S_R}\)

These statistics track the weighted sum and mean of target values in each child node.

The optimization objective is to minimize:

\[ \mathcal{L}_{\text{MSE}}(\mathbf{w}) = \frac{1}{\sum_{i=1}^N \omega_i}\sum_{i=1}^N \omega_i[p_i(y_i-m_L)^2 + (1-p_i)(y_i-m_R)^2] \]

The optimization requires computing several gradients:

1. Node mean gradients:

\[ \frac{\partial m_L}{\partial \mathbf{w}} = \frac{S_L\frac{\partial M_L}{\partial \mathbf{w}} - M_L\frac{\partial S_L}{\partial \mathbf{w}}}{S_L^2} \]

\[ \frac{\partial m_R}{\partial \mathbf{w}} = \frac{S_R\frac{\partial M_R}{\partial \mathbf{w}} - M_R\frac{\partial S_R}{\partial \mathbf{w}}}{S_R^2} \]

2. Final gradient:

\[\begin{split} \begin{aligned} \frac{\partial \mathcal{L}_{\text{MSE}}}{\partial \mathbf{w}} = & \frac{1}{\sum_{i=1}^N \omega_i}\sum_{i=1}^N \omega_i\left[\frac{\partial p_i}{\partial \mathbf{w}}(y_i-m_L)^2 - \frac{\partial p_i}{\partial \mathbf{w}}(y_i-m_R)^2 + \right. \\ & \left. p_i\frac{\partial m_L}{\partial \mathbf{w}}(-2)(y_i-m_L) + (1-p_i)\frac{\partial m_R}{\partial \mathbf{w}}(-2)(y_i-m_R)\right] \end{aligned} \end{split}\]

4.2 Linear Regression Approach

\[ \mathcal{L}_{\text{LinReg}}(\mathbf{w}) = \frac{1}{2\sum_{i=1}^N \omega_i}\sum_{i=1}^N \omega_i(y_i - \mathbf{x}_i^\top\mathbf{w})^2 \]

\[ \frac{\partial \mathcal{L}_{\text{LinReg}}}{\partial \mathbf{w}} = -\frac{1}{\sum_{i=1}^N \omega_i}\mathbf{X}^\top(\boldsymbol{\omega} \odot (\mathbf{y} - \mathbf{X}\mathbf{w})) \]

5. L-BFGS Optimization

The optimization process uses a custom unconstrained L-BFGS implementation to solve:

\[ \min_{\mathbf{w}} \mathcal{L}(\mathbf{w}) \]

Key elements of the optimization process:

1. Objective Function:

   • Minimizes the loss function (Gini impurity or MSE)

2. Stopping Criteria:

   • Stops when maximum iterations (maxiter) is reached

   • Stops when the infinity norm of the gradient falls below a small tolerance

   • Stops when relative improvement falls below threshold:

     \[ \frac{\mathcal{L}(\mathbf{w}_{t-1}) - \mathcal{L}(\mathbf{w}_t)}{\mathcal{L}(\mathbf{w}_{t-1})} \leq \text{relative\_change} \]

3. Solution Normalization:

   • Final weights are normalized:

     \[ \mathbf{w} \leftarrow \frac{\mathbf{w}}{\max(|\mathbf{w}|)} \]