Mathematics

This page formalizes the main mathematical ideas used in kfc-procedure.

---

1. Bregman divergence

A Bregman divergence is generated by a strictly convex differentiable function:

\[ \phi : \mathcal{X} \rightarrow \mathbb{R}. \]

For two points \(x, y \in \mathcal{X}\), the Bregman divergence is:

\[ D_\phi(x, y) = \phi(x) - \phi(y) - \langle \nabla \phi(y), x - y \rangle. \]

Variable definitions

Symbol	Meaning
\(x\)	input sample
\(y\)	reference point or centroid
\(\phi\)	strictly convex generator
\(\nabla \phi(y)\)	gradient of generator at \(y\)
\(D_\phi(x, y)\)	divergence from \(x\) to \(y\)

Important property

A Bregman divergence is not necessarily symmetric. Usually, \(D_\phi(x, y) \neq D_\phi(y, x)\).

---

2. Bregman K-Means objective

Given samples:

\[ X = \{x_1, x_2, \ldots, x_n\}, \quad x_i \in \mathbb{R}^d, \]

and centroids:

\[ \mu_1, \mu_2, \ldots, \mu_K, \]

Bregman K-Means minimizes:

\[ \min_{c_1, \ldots, c_n, \mu_1, \ldots, \mu_K} \sum_{i=1}^{n} D_\phi(x_i, \mu_{c_i}), \]

where:

\[ c_i \in \{1, 2, \ldots, K\}. \]

The assignment step is:

\[ c_i = \arg\min_{k \in \{1, \ldots, K\}} D_\phi(x_i, \mu_k). \]

The centroid update used in the implementation is the arithmetic mean:

\[ \mu_k = \frac{1}{|C_k|} \sum_{i : c_i = k} x_i. \]

Intuition

The assignment step asks: "Which centroid is closest under this divergence?" The update step moves each centroid to the average of the samples assigned to it.

---

3. Supported divergences

Squared Euclidean divergence

Generator:

\[ \phi(x) = \sum_{j=1}^{d} x_j^2. \]

Gradient:

\[ \nabla \phi(x) = 2x. \]

Divergence:

\[ D(x, y) = \|x-y\|_2^2. \]

Domain:

\[ x \in \mathbb{R}^d. \]

Use this as the default for general numerical data.

---

Generalized Kullback-Leibler divergence

Generator:

\[ \phi(x) = \sum_{j=1}^{d} x_j \log(x_j). \]

Gradient:

\[ \nabla \phi(x) = \log(x) + 1. \]

Divergence:

\[ D(x, y) = \sum_{j=1}^{d} \left[ x_j \log\left(\frac{x_j}{y_j}\right) - (x_j - y_j) \right]. \]

Domain:

\[ x_j > 0 \quad \forall j. \]

Use this for strictly positive count-like or intensity-like features.

---

Itakura-Saito divergence

Generator:

\[ \phi(x) = -\sum_{j=1}^{d} \log(x_j). \]

Gradient:

\[ \nabla \phi(x) = -\frac{1}{x}. \]

Divergence:

\[ D(x, y) = \sum_{j=1}^{d} \left[ \frac{x_j}{y_j} - \log\left(\frac{x_j}{y_j}\right) - 1 \right]. \]

Domain:

\[ x_j > 0 \quad \forall j. \]

This divergence is scale-sensitive and useful for positive-valued data.

---

Logistic divergence

Generator:

\[ \phi(x) = \sum_{j=1}^{d} \left[ x_j \log(x_j) + (1-x_j)\log(1-x_j) \right]. \]

Gradient:

\[ \nabla \phi(x) = \log(x) - \log(1-x). \]

Divergence:

\[ D(x, y) = \sum_{j=1}^{d} \left[ x_j \log\left(\frac{x_j}{y_j}\right) + (1-x_j)\log\left(\frac{1-x_j}{1-y_j}\right) \right]. \]

Domain:

\[ 0 < x_j < 1 \quad \forall j. \]

Use this for probability-like features bounded between 0 and 1.

---

4. KFCProcedure formulation

Let there be \(m\) divergences:

\[ \mathcal{D} = \{D_{\phi_1}, D_{\phi_2}, \ldots, D_{\phi_m}\}. \]

For each divergence \(D_{\phi_j}\), K-step learns a clustering function:

\[ h_j(x) \in \{1, 2, \ldots, K\}. \]

For each divergence \(j\) and cluster \(k\), F-step fits a local predictor:

\[ f_{j,k} : \mathbb{R}^d \rightarrow \mathcal{Y}. \]

For a new sample \(x\), the divergence-specific prediction is:

\[ p_j(x) = f_{j,h_j(x)}(x). \]

The prediction vector is:

\[ p(x) = [p_1(x), p_2(x), \ldots, p_m(x)]^\top. \]

The C-step combiner learns or applies:

\[ g : \mathbb{R}^m \rightarrow \mathcal{Y}. \]

Final prediction:

\[ \hat{y} = g(p(x)). \]

---

5. Regression combiners

Mean combiner

\[ \hat{y}_i = \frac{1}{m} \sum_{j=1}^{m} P_{ij}, \]

where \(P \in \mathbb{R}^{n \times m}\) is the prediction matrix.

---

Weighted mean combiner

The weighted combiner fits a linear model:

\[ \hat{y} = P w + b. \]

When fit_intercept=False, this becomes:

\[ \hat{y} = P w. \]

The ordinary least squares objective is:

\[ \min_w \|y - Pw\|_2^2. \]

---

Stacking regressor

A meta-regressor \(g_\theta\) is trained on the prediction matrix:

\[ \min_\theta \mathcal{L}(y, g_\theta(P)). \]

The default meta-model is linear regression.

---

6. Classification combiners

Majority vote

For prediction row \(P_i = [P_{i1}, \ldots, P_{im}]\), the majority vote prediction is:

\[ \hat{y}_i = \operatorname{mode}(P_{i1}, P_{i2}, \ldots, P_{im}). \]

Stacking classifier

The default stacking classifier uses logistic regression as a meta-classifier:

\[ \hat{y}_i = \arg\max_c \Pr(y_i=c \mid P_i). \]

---

7. COBRA mathematical formulation

Let \(r_1, \ldots, r_q\) be base estimators. The prediction-space representation of a sample \(x\) is:

\[ z(x) = [r_1(x), r_2(x), \ldots, r_q(x)]^\top. \]

For a test sample \(x\), COBRA compares \(z(x)\) with calibration prediction vectors \(z(x_l)\).

Distance:

\[ \delta_i(x) = d(z(x), z(x_i^{(l)})). \]

Kernel weight:

\[ w_i(x) = \kappa(\lambda \delta_i(x)), \]

where:

Symbol	Meaning
\(\kappa\)	kernel function
\(\lambda\)	bandwidth or scaling parameter
\(x_i^{(l)}\)	calibration sample
\(y_i^{(l)}\)	calibration target

Regression prediction:

\[ \hat{y}(x) = \frac{\sum_{i=1}^{n_l} w_i(x)y_i^{(l)}} {\sum_{i=1}^{n_l} w_i(x) + \epsilon}. \]

The bandwidth is selected by minimizing cross-validation loss:

\[ \lambda^* = \arg\min_{\lambda} \frac{1}{V} \sum_{v=1}^{V} \mathcal{L}\left(y_{val}^{(v)}, \hat{y}_{\lambda}^{(v)}\right). \]

---

8. MixCOBRA formulation

MixCOBRA combines input-space and prediction-space distances.

Input-space distance:

\[ D_X(x, x_i^{(l)}). \]

Prediction-space distance:

\[ D_Z(z(x), z(x_i^{(l)})). \]

Two-parameter mixing:

\[ D_{mix}(x, x_i^{(l)}) = \alpha D_X(x, x_i^{(l)}) + \beta D_Z(z(x), z(x_i^{(l)})). \]

The optimized parameters are:

\[ (\alpha^*, \beta^*) = \arg\min_{\alpha, \beta} \text{CVLoss}(\alpha, \beta). \]

One-parameter mode concatenates normalized input and prediction features and optimizes a single bandwidth-like parameter.

---

9. Loss functions in COBRA core

The COBRA core supports several losses:

Loss	Formula
MSE	\(\frac{1}{n}\sum_i (y_i - \hat{y}_i)^2\)
MAE	$\frac{1}{n}\sum_i
Huber	quadratic for small errors, linear for large errors
Quantile	\(\max(\tau e, (\tau-1)e)\) where \(e=y-\hat{y}\)
Log loss	cross-entropy for probabilistic classification
Hinge	\(\max(0, 1-y\hat{y})\)

---

10. Kernel functions in COBRA core

Kernel functions convert distances into weights.

Kernel	Weight form
radial, gaussian, rbf	\(\exp(-D)\)
exponential	\(\exp(-D^p)\)
cauchy	\(\frac{1}{1+D}\)
reverse_cosh	\(\frac{1}{\cosh(D)^p}\)
epanechnikov	\(1-D\) if \(D<1\), else 0
triangular	$1-
biweight	\((1-D)^2\) if \(D<1\), else 0
triweight	\((1-D)^3\) if \(D<1\), else 0
cobra	indicator \(\mathbb{1}[D < \tau]\)

Implementation detail

The code often applies a kernel adapter before the kernel. For example, the one-parameter adapter transforms a distance matrix as bandwidth * D.