"""Post-hoc gain calibration of the hierarchical softmax output.
A hierarchical softmax classifier reads its class probability off a binary
tree. At node h on the path of class k, the network output Z_h gives the branch
probability P_h = Phi(s_h * G_h * Z_h), where Phi is the standard normal CDF,
s_h = +1 or -1 is the branch sign and G_h is a readout gain. The class
probability is the product of P_h over the path.
A network trained with a small observation noise is accurate but
overconfident. This module keeps the trained network fixed and treats each
gain G_h as a Gaussian random variable. It updates the gains on a held-out
split with an approximate Bayesian update, using the observation "the branch
of the true class was taken" with the Bernoulli variance mu_P (1 - mu_P).
The mean and the variance of P_h use Gaussian moment matching of the product
G_h * Z_h. The covariance of G_h and P_h is var_G * d mu_P / d mu_G (Stein's
lemma applied to the moment-matched mean), which agrees with Monte Carlo
better than the covariance of a joint Gaussian approximation of (G_h, G_h Z_h).
The update is therefore a scalar recursion per node that needs the
forward-pass means and variances only. Neither the training loop nor the
C++/CUDA backend is involved.
The fixed readout of the library is this model with G_h = 3 and no gain
uncertainty, so the default prior (mean 3) starts from the fixed readout.
When the number of classes is not a power of two, the tree has missing
leaves. The predictive class probabilities are then normalized over the
classes, while the calibration update uses each node of the path of the true
class on its own, so its objective differs slightly from the normalized
predictive.
Typical use::
calibrator = HSMGainCalibrator(num_classes=10, sharing="level")
calibrator.calibrate(mu_val, var_val, labels_val)
prob, prob_var = calibrator.class_probabilities(mu_test, var_test)
"""
import math
from concurrent.futures import ThreadPoolExecutor
from typing import Optional, Sequence, Tuple
import numpy as np
from pytagi.tagi_utils import Utils
[docs]
_SQRT2 = math.sqrt(2.0)
[docs]
_INV_SQRT_2PI = 1.0 / math.sqrt(2.0 * math.pi)
_GAUSS_LEGENDRE_NODES, _GAUSS_LEGENDRE_WEIGHTS = (
np.polynomial.legendre.leggauss(8)
)
# numpy has no erfc. scipy is not a dependency of pytagi, so it is used only
# when it is installed (about 50 times faster than the fallback on large
# arrays).
try:
from scipy.special import erfc as _erfc
except ImportError: # pragma: no cover
[docs]
_erfc = np.vectorize(math.erfc, otypes=[np.float64])
# Number of array elements processed at once when computing node moments.
[docs]
_CHUNK_ELEMENTS = 1 << 18
# Gain updates evaluated together only when at least this many are independent.
[docs]
def _normal_cdf(x: np.ndarray) -> np.ndarray:
return 0.5 * _erfc(-np.asarray(x, dtype=np.float64) / _SQRT2)
[docs]
def _normal_pdf(x: np.ndarray) -> np.ndarray:
return _INV_SQRT_2PI * np.exp(-0.5 * np.asarray(x, dtype=np.float64) ** 2)
[docs]
def _phi_variance(a: np.ndarray, var: np.ndarray) -> np.ndarray:
"""Variance of Phi(X) for a Gaussian X with variance ``var``.
``a`` is the standardized mean mu_X / sqrt(1 + var). The variance is the
integral of exp(-a^2 (1 + t^2) / 2) / (1 + t^2) over t in [b, 1], divided by
pi, with b = 1 / sqrt(1 + 2 var). It is evaluated with an 8-point
Gauss-Legendre rule, which stays positive and avoids the cancellation of
the closed form with Owen's T function for small ``var``.
"""
b = 1.0 / np.sqrt(1.0 + 2.0 * var)
half = 0.5 * (1.0 - b)
mid = 0.5 * (1.0 + b)
exponent = -0.5 * a * a
total = np.zeros_like(a)
for node, weight in zip(_GAUSS_LEGENDRE_NODES, _GAUSS_LEGENDRE_WEIGHTS):
one_plus_t2 = 1.0 + np.square(mid + half * node)
total += weight * np.exp(exponent * one_plus_t2) / one_plus_t2
return (half / math.pi) * total
[docs]
def _branch_mean_var(mu_z, var_z, mu_gain, var_gain, with_variance=False):
"""Means of both branches, Phi(a) and Phi(-a), and the variance of
Phi(G * Z): the part of ``_branch_moments`` that prediction needs.
The smaller of the two means is evaluated directly, so a branch
probability in the far tail does not round to zero as 1 - Phi(a) would.
:return: ``(mu_plus, mu_minus, var)``; ``var`` is None unless
``with_variance``.
"""
var_s = var_gain * var_z + var_gain * mu_z**2 + mu_gain**2 * var_z
a = mu_gain * mu_z / np.sqrt(1.0 + var_s)
var_p = _phi_variance(a, var_s) if with_variance else None
tail = _normal_cdf(-np.abs(a))
positive = a >= 0.0
mu_plus = np.where(positive, 1.0 - tail, tail)
mu_minus = np.where(positive, tail, 1.0 - tail)
return mu_plus, mu_minus, var_p
[docs]
def _branch_moments(
mu_z, var_z, mu_gain, var_gain, sign, with_variance: bool = False
):
"""Moments of the branch probability P = Phi(sign * G * Z).
G and Z are independent Gaussians. The mean and the variance of P replace
the product S = G * Z by a Gaussian with its exact mean and variance,
which is exact when either G or Z is deterministic. The covariance is
var_G * d mu_P / d mu_G, from Stein's lemma.
:return: The mean of P, the covariance of G and P, and the variance of P
(None unless ``with_variance``).
"""
mu_s = mu_gain * mu_z
var_s = var_gain * var_z + var_gain * mu_z**2 + mu_gain**2 * var_z
one_plus_var_s = 1.0 + var_s
a = sign * mu_s / np.sqrt(one_plus_var_s)
mu_p = _normal_cdf(a)
cov_gain_p = (
sign
* var_gain
* mu_z
* (one_plus_var_s - mu_gain**2 * var_z)
/ one_plus_var_s**1.5
* _normal_pdf(a)
)
var_p = _phi_variance(a, var_s) if with_variance else None
return mu_p, cov_gain_p, var_p
[docs]
class HSMGainCalibrator:
"""Gaussian readout gains for the hierarchical softmax.
The branch probability Phi(s * G * Z) has its mean and variance from
Gaussian moment matching of G * Z, and its covariance with G from Stein's
lemma (see the module documentation).
:param num_classes: The number of classes.
:type num_classes: int
:param sharing: ``"node"`` for one gain per tree node, ``"level"`` for one
gain per tree level, or ``"global"`` for a single gain.
:type sharing: str
:param mu_gain_init: Prior mean of the gains. The default 3 is the gain of
the fixed readout (``Utils.obs_to_label_prob``), so the prior is "no
change from the fixed readout".
:type mu_gain_init: float
:param sigma_gain_init: Prior standard deviation of the gains.
:type sigma_gain_init: float
:param min_mu_gain: Lower bound of the gain mean. A negative gain would swap
the two branches of a node.
:type min_mu_gain: float
:param eps: The branch probability is clipped to [eps, 1 - eps] before the
update to keep the Bernoulli variance positive.
:type eps: float
"""
def __init__(
self,
num_classes: int,
sharing: str = "level",
mu_gain_init: float = 3.0,
sigma_gain_init: float = 1.0,
min_mu_gain: float = 1e-3,
eps: float = 1e-6,
):
if sharing not in ("node", "level", "global"):
raise ValueError(
f"sharing must be 'node', 'level' or 'global', got {sharing!r}"
)
hrc = Utils().get_hierarchical_softmax(num_classes)
self.num_classes = num_classes
self.num_levels = int(hrc.num_obs)
self.num_units = int(hrc.len)
self.min_mu_gain = min_mu_gain
self.eps = eps
# Row k lists the signs and the output units on the path of class k.
# The library numbers output units from 1.
shape = (num_classes, self.num_levels)
self._signs = np.asarray(hrc.obs, dtype=np.float64).reshape(shape)
self._path_units = (
np.asarray(hrc.idx, dtype=np.int64).reshape(shape) - 1
)
if sharing == "node":
unit_to_gain = np.arange(self.num_units)
elif sharing == "level":
unit_to_gain = np.zeros(self.num_units, dtype=np.int64)
for level in range(self.num_levels):
unit_to_gain[self._path_units[:, level]] = level
else:
unit_to_gain = np.zeros(self.num_units, dtype=np.int64)
self._unit_to_gain = unit_to_gain
self._path_gains = unit_to_gain[self._path_units]
self._build_tree()
num_gains = int(unit_to_gain.max()) + 1
self._var_gain_init = sigma_gain_init**2
self.mu_gain = np.full(num_gains, mu_gain_init, dtype=np.float64)
self.var_gain = np.full(
num_gains, self._var_gain_init, dtype=np.float64
)
@property
[docs]
def sigma_gain(self) -> np.ndarray:
"""Standard deviation of the gains."""
return np.sqrt(self.var_gain)
[docs]
def _build_tree(self) -> None:
"""Derive the tree from the class paths.
``_levels`` lists, for every level below the root, the units on it with
their parent and the branch taken from the parent. This gives the
probability of every path prefix with one pass over the units instead
of one pass over the (class, level) pairs. ``_ragged`` describes the
units whose subtree is missing some class, the only ones that make the
class probabilities sum to less than one.
"""
units, signs = self._path_units, self._signs
num_levels = self.num_levels
self._root = int(units[0, 0])
self._levels = []
for level in range(1, num_levels):
child, first = np.unique(units[:, level], return_index=True)
self._levels.append(
(child, units[first, level - 1], signs[first, level - 1] > 0.0)
)
leaf = -2
child_of = np.full((self.num_units, 2), -1, dtype=np.int64)
for level in range(num_levels):
below = units[:, level + 1] if level + 1 < num_levels else leaf
child_of[units[:, level], (signs[:, level] < 0.0).astype(int)] = (
below
)
complete = np.zeros(self.num_units, dtype=bool)
groups = []
for level in range(num_levels - 1, -1, -1):
nodes = np.unique(units[:, level])
full = np.ones(nodes.shape[0], dtype=bool)
for branch in range(2):
child = child_of[nodes, branch]
full &= (child == leaf) | (
(child >= 0) & complete[np.maximum(child, 0)]
)
complete[nodes] = full
groups.append(nodes[~full])
self._root_complete = bool(complete[self._root])
# Incomplete units, deepest level first, with the position of each
# child in the dynamic program (see ``_subtree_mass``).
self._ragged_units = np.concatenate(groups)
num_ragged = self._ragged_units.shape[0]
position = np.full(self.num_units, -1, dtype=np.int64)
position[self._ragged_units] = np.arange(num_ragged)
def code_of(child):
"""Column of a child subtree in the table of ``_subtree_mass``."""
known = np.maximum(child, 0)
code = np.where(child == -1, num_ragged, position[known])
whole = (child == leaf) | ((child >= 0) & complete[known])
return np.where(whole, num_ragged + 1, code)
self._ragged_groups = []
start = 0
for nodes in groups:
self._ragged_groups.append(
(
start,
start + nodes.shape[0],
code_of(child_of[nodes, 0]),
code_of(child_of[nodes, 1]),
)
)
start += nodes.shape[0]
self._root_position = int(position[self._root])
# Subtree on the other side of the path of class k at each level.
other = (signs > 0.0).astype(int)
self._sibling_codes = code_of(child_of[units, other])
[docs]
def calibrate(
self,
mu_z: np.ndarray,
var_z: np.ndarray,
labels: Sequence[int],
batch_size: int = 4096,
reset_variance: bool = True,
) -> None:
"""Update the gains with one pass over a held-out split.
Use data that was not used to train the network.
The samples are processed in order, as a sequence of Bayesian updates.
Inside a mini-batch, updates of different gains do not depend on each
other, so they are evaluated together with array operations. The result
does not depend on ``batch_size``.
:param mu_z: Output means of the network, shape (N, len) or flat.
:type mu_z: np.ndarray
:param var_z: Output variances of the network, same shape.
:type var_z: np.ndarray
:param labels: The true class of each of the N samples, integers in
[0, num_classes).
:type labels: Sequence[int]
:param batch_size: Samples gathered at a time. Only the units on the
path of the label are read, so float32 outputs are not copied.
:type batch_size: int
:param reset_variance: Reset the gain variance to the prior first. Pass
False to stream a split through several calls.
:type reset_variance: bool
:raises ValueError: If the shapes or the labels are invalid, or if an
output read on the path of a label is not finite or has a
negative variance.
"""
mu_z = np.asarray(mu_z).reshape(-1, self.num_units)
var_z = np.asarray(var_z).reshape(-1, self.num_units)
if var_z.shape != mu_z.shape:
raise ValueError(
f"var_z has shape {var_z.shape}, mu_z has shape {mu_z.shape}"
)
labels = self._check_labels(labels, mu_z.shape[0])
if reset_variance:
self.var_gain[:] = self._var_gain_init
for start in range(0, labels.shape[0], batch_size):
stop = start + batch_size
self._update_batch(
mu_z[start:stop], var_z[start:stop], labels[start:stop]
)
[docs]
def _check_labels(self, labels, num_rows: int) -> np.ndarray:
"""Labels as an int64 array of length ``num_rows`` in range."""
labels = np.asarray(labels).reshape(-1)
if labels.shape[0] != num_rows:
raise ValueError(
f"{num_rows} output rows for {labels.shape[0]} labels"
)
if labels.dtype.kind not in "iu":
if labels.dtype.kind != "f" or not np.all(
np.isfinite(labels) & (labels == np.round(labels))
):
raise ValueError("labels must be integers")
labels = labels.astype(np.int64)
if labels.size and (
labels.min() < 0 or labels.max() >= self.num_classes
):
raise ValueError(
f"labels must be in [0, {self.num_classes}), got"
f" [{labels.min()}, {labels.max()}]"
)
return labels
[docs]
def _update_batch(self, mu_z, var_z, labels) -> None:
units = self._path_units[labels]
rows = np.arange(labels.shape[0])[:, None]
mu_path = mu_z[rows, units].astype(np.float64).reshape(-1)
var_path = var_z[rows, units].astype(np.float64).reshape(-1)
if not (np.all(np.isfinite(mu_path)) and np.all(np.isfinite(var_path))):
raise ValueError("non-finite network outputs")
if np.any(var_path < 0.0):
raise ValueError("negative output variances")
sign = self._signs[labels].reshape(-1)
gain = self._path_gains[labels].reshape(-1)
# Update number r of a gain is evaluated in round r. The entries are
# in sample order, so the order of the updates of each gain is kept.
by_gain = np.argsort(gain, kind="stable")
gain_sorted = gain[by_gain]
first = np.flatnonzero(np.r_[True, gain_sorted[1:] != gain_sorted[:-1]])
group = np.cumsum(np.r_[False, gain_sorted[1:] != gain_sorted[:-1]])
rank = np.empty_like(by_gain)
rank[by_gain] = np.arange(by_gain.shape[0]) - first[group]
order = np.argsort(rank, kind="stable")
bounds = np.r_[0, np.cumsum(np.bincount(rank))]
mu_path, var_path = mu_path[order], var_path[order]
sign, gain = sign[order], gain[order]
for lo, hi in zip(bounds[:-1], bounds[1:]):
if hi - lo >= _MIN_VECTOR_WIDTH:
self._update_gains(
gain[lo:hi], mu_path[lo:hi], var_path[lo:hi], sign[lo:hi]
)
else:
for g, mz, vz, s in zip(
gain[lo:hi].tolist(),
mu_path[lo:hi].tolist(),
var_path[lo:hi].tolist(),
sign[lo:hi].tolist(),
):
self._update_gain_scalar(g, mz, vz, s)
[docs]
def _update_gains(self, gain, mu_z, var_z, sign) -> None:
"""Bayesian update of distinct gains, one observation each."""
mu_gain, var_gain = self.mu_gain[gain], self.var_gain[gain]
mu_p, cov_gain_p, _ = _branch_moments(
mu_z, var_z, mu_gain, var_gain, sign
)
mu_p = np.clip(mu_p, self.eps, 1.0 - self.eps)
var_obs = mu_p * (1.0 - mu_p)
# The observation is 1: the branch of the true class was taken.
mu_post = mu_gain + cov_gain_p / mu_p
var_post = var_gain - cov_gain_p**2 / var_obs
self.mu_gain[gain] = np.maximum(mu_post, self.min_mu_gain)
self.var_gain[gain] = np.maximum(var_post, 0.0)
[docs]
def _update_gain_scalar(self, gain, mu_z, var_z, sign) -> None:
"""Same as ``_update_gains`` for one gain, without numpy overhead."""
mu_gain, var_gain = float(self.mu_gain[gain]), float(
self.var_gain[gain]
)
var_s = var_gain * var_z + var_gain * mu_z**2 + mu_gain**2 * var_z
one_plus_var_s = 1.0 + var_s
root = math.sqrt(one_plus_var_s)
a = sign * mu_gain * mu_z / root
mu_p = 0.5 * math.erfc(-a / _SQRT2)
cov_gain_p = (
sign
* var_gain
* mu_z
* (one_plus_var_s - mu_gain**2 * var_z)
/ (one_plus_var_s * root)
* _INV_SQRT_2PI
* math.exp(-0.5 * a * a)
)
mu_p = min(max(mu_p, self.eps), 1.0 - self.eps)
var_obs = mu_p * (1.0 - mu_p)
self.mu_gain[gain] = max(mu_gain + cov_gain_p / mu_p, self.min_mu_gain)
self.var_gain[gain] = max(var_gain - cov_gain_p**2 / var_obs, 0.0)
[docs]
def class_probabilities(
self,
mu_z: np.ndarray,
var_z: np.ndarray,
compute_var: bool = True,
classes: Optional[Sequence[int]] = None,
num_threads: int = 1,
) -> Tuple[np.ndarray, Optional[np.ndarray]]:
"""Class probabilities computed with the calibrated gains.
The probabilities sum to one when every leaf of the tree is a class.
Otherwise (for example when the number of classes is not a power of
two) they are normalized over the classes: p_k = u_k / M, where u_k
is the product over the path of class k and M the sum over the
classes. The variance treats the tree nodes as independent. For
normalized probabilities it is the first-order delta method,
(var(u_k) - 2 p_k cov(u_k, M) + p_k^2 var(M)) / E[M]^2, which keeps
the covariance of u_k with M (the plain var(u_k) / E[M]^2
overestimates the variance of the most probable classes).
With a large tree, ask only for the classes you need: the cost is then
proportional to the number of requested classes instead of the size of
the tree for the paths, and to the number of incomplete subtrees for
the normalization. See also ``label_probabilities`` and
``top_k_probabilities``.
:param mu_z: Output means of the network, shape (N, len) or (len,).
:type mu_z: np.ndarray
:param var_z: Output variances of the network, same shape.
:type var_z: np.ndarray
:param compute_var: Also return the variance of the class probability.
:type compute_var: bool
:param classes: Classes to return, shape (C,) for all samples or (N, C)
for one list per sample. Default: all classes.
:type classes: Sequence[int]
:param num_threads: Threads that process blocks of rows in parallel.
The result does not depend on it.
:type num_threads: int
:return: The mean and the variance of the class probabilities, each of
shape (N, num_classes) or (N, C). The variance is None if
``compute_var`` is False.
:rtype: tuple
"""
mu_z = np.asarray(mu_z).reshape(-1, self.num_units)
var_z = np.asarray(var_z).reshape(-1, self.num_units)
num_rows = mu_z.shape[0]
if classes is not None:
classes = np.asarray(classes, dtype=np.int64)
if (
classes.min(initial=0) < 0
or classes.max(initial=0) >= self.num_classes
):
raise ValueError("classes out of range")
classes = np.broadcast_to(
(
classes.reshape(-1, classes.shape[-1])
if classes.ndim > 1
else classes[None, :]
),
(num_rows, classes.shape[-1]),
)
width = (
self.num_units
if classes is None
else classes.shape[1] * self.num_levels
)
step = max(1, _CHUNK_ELEMENTS // max(width, 1))
num_out = self.num_classes if classes is None else classes.shape[1]
mu_class = np.empty((num_rows, num_out))
var_class = np.empty((num_rows, num_out)) if compute_var else None
def run(lo):
sl = slice(lo, lo + step)
if classes is None:
out = self._all_classes(mu_z[sl], var_z[sl], compute_var)
else:
out = self._some_classes(
mu_z[sl], var_z[sl], classes[sl], compute_var
)
mu_class[sl] = out[0]
if compute_var:
var_class[sl] = out[1]
starts = range(0, num_rows, step)
if num_threads > 1:
with ThreadPoolExecutor(num_threads) as pool:
list(pool.map(run, starts))
else:
for lo in starts:
run(lo)
return mu_class, var_class
[docs]
def label_probabilities(
self,
mu_z: np.ndarray,
var_z: np.ndarray,
labels: Sequence[int],
compute_var: bool = False,
) -> Tuple[np.ndarray, Optional[np.ndarray]]:
"""Probability of the given class of each sample, shape (N,).
This is what the negative log-likelihood needs. It does not build the
(N, num_classes) matrix. Same values as ``class_probabilities``.
:raises ValueError: If ``labels`` are not N integers in
[0, num_classes).
"""
mu_z = np.asarray(mu_z).reshape(-1, self.num_units)
labels = self._check_labels(labels, mu_z.shape[0]).reshape(-1, 1)
mu_class, var_class = self.class_probabilities(
mu_z, var_z, compute_var, classes=labels
)
return mu_class[:, 0], None if var_class is None else var_class[:, 0]
[docs]
def top_k_probabilities(
self,
mu_z: np.ndarray,
var_z: np.ndarray,
k: int,
num_threads: int = 1,
) -> Tuple[np.ndarray, np.ndarray]:
"""The ``k`` most probable classes of each sample.
The result is exact. The full matrix is built a few rows at a time and
not kept.
:param k: Number of classes to return, 1 <= k <= num_classes.
:type k: int
:param num_threads: Passed to ``class_probabilities``.
:type num_threads: int
:return: The probabilities (N, k) in decreasing order and the class
indices (N, k).
"""
if not 1 <= k <= self.num_classes:
raise ValueError(f"k must be in [1, {self.num_classes}], got {k}")
mu_z = np.asarray(mu_z).reshape(-1, self.num_units)
var_z = np.asarray(var_z).reshape(-1, self.num_units)
# Each call gets one block of rows per thread.
step = max(1, _CHUNK_ELEMENTS // max(self.num_units, 1))
step *= max(1, num_threads)
top_prob = np.empty((mu_z.shape[0], k))
top_class = np.empty((mu_z.shape[0], k), dtype=np.int64)
for lo in range(0, mu_z.shape[0], step):
prob, _ = self.class_probabilities(
mu_z[lo : lo + step],
var_z[lo : lo + step],
compute_var=False,
num_threads=num_threads,
)
part = np.argpartition(-prob, k - 1, axis=1)[:, :k]
part_prob = np.take_along_axis(prob, part, axis=1)
rank = np.argsort(-part_prob, axis=1)
top_class[lo : lo + step] = np.take_along_axis(part, rank, axis=1)
top_prob[lo : lo + step] = np.take_along_axis(
part_prob, rank, axis=1
)
return top_prob, top_class
[docs]
def _all_classes(self, mu_z, var_z, compute_var):
"""All classes: path products by one pass over the tree units."""
mu_z = mu_z.astype(np.float64, copy=False)
var_z = var_z.astype(np.float64, copy=False)
gain = self._unit_to_gain
mu_p, mu_q, var_p = _branch_mean_var(
mu_z, var_z, self.mu_gain[gain], self.var_gain[gain], compute_var
)
prefix = np.zeros_like(mu_p) # product of the branch means above a unit
prefix[:, self._root] = 1.0
if compute_var:
prefix_sq_var = np.zeros_like(mu_p) # product of var + mean^2
prefix_sq = np.zeros_like(mu_p) # product of mean^2
prefix_sq_var[:, self._root] = 1.0
prefix_sq[:, self._root] = 1.0
for child, parent, positive in self._levels:
branch = np.where(positive, mu_p[:, parent], mu_q[:, parent])
prefix[:, child] = prefix[:, parent] * branch
if compute_var:
prefix_sq_var[:, child] = prefix_sq_var[:, parent] * (
var_p[:, parent] + branch**2
)
prefix_sq[:, child] = prefix_sq[:, parent] * branch**2
last = self._path_units[:, -1]
branch = np.where(
self._signs[:, -1] > 0.0, mu_p[:, last], mu_q[:, last]
)
mu_class = prefix[:, last] * branch
var_class = None
if compute_var:
var_class = (
prefix_sq_var[:, last] * (var_p[:, last] + branch**2)
- prefix_sq[:, last] * branch**2
)
if self._root_complete:
return mu_class, var_class
if not compute_var:
return mu_class / mu_class.sum(axis=-1, keepdims=True), None
positive = self._signs > 0.0
units = self._path_units
mu_path = np.where(positive, mu_p[:, units], mu_q[:, units])
mu_other = np.where(positive, mu_q[:, units], mu_p[:, units])
return self._normalize(
mu_z,
var_z,
mu_class,
var_class,
mu_path,
mu_other,
var_p[:, units],
self._sibling_codes,
)
[docs]
def _some_classes(self, mu_z, var_z, classes, compute_var):
"""Requested classes only: gather the units on their paths."""
units = self._path_units[classes] # (N, C, levels)
rows = np.arange(mu_z.shape[0])[:, None, None]
gain = self._path_gains[classes]
mu_p, mu_q, var_p = _branch_mean_var(
mu_z[rows, units].astype(np.float64),
var_z[rows, units].astype(np.float64),
self.mu_gain[gain],
self.var_gain[gain],
compute_var,
)
positive = self._signs[classes] > 0.0
mu_path = np.where(positive, mu_p, mu_q)
mu_class = np.prod(mu_path, axis=-1)
var_class = None
if compute_var:
var_class = np.prod(var_p + mu_path**2, axis=-1) - np.prod(
mu_path**2, axis=-1
)
if self._root_complete:
return mu_class, var_class
if not compute_var:
mass = self._subtree_mass(mu_z, var_z)[0]
return mu_class / mass[:, None], None
return self._normalize(
mu_z,
var_z,
mu_class,
var_class,
mu_path,
np.where(positive, mu_q, mu_p),
var_p,
self._sibling_codes[classes],
)
[docs]
def _normalize(
self, mu_z, var_z, mu_u, var_u, mu_path, mu_other, var_path, siblings
):
"""Normalized probabilities p_k = u_k / M and their variance.
The variance is the first-order delta method,
(var(u_k) - 2 p_k cov(u_k, M) + p_k^2 var(M)) / E[M]^2, with the nodes
independent. cov(u_k, M) = E[u_k M] - E[u_k] E[M], and E[u_k M] is a
recursion up the path of class k: at a node where the path takes the
branch B, E[B^2] E[u M] of the child on the path plus E[B B'] E[u]
E[M] of the two children, where B' = 1 - B is the other branch.
``mu_path``, ``mu_other`` and ``var_path`` have shape (..., levels);
``siblings`` gives the column of the other child subtree of each node
in the table of ``_subtree_mass``.
"""
mass, mass_table, second = self._subtree_mass(mu_z, var_z, True)
rows = np.arange(mu_z.shape[0]).reshape((-1,) + (1,) * siblings.ndim)
if siblings.ndim == 3: # one list of classes per row
rows = rows[..., 0]
sibling_mass = mass_table[rows, siblings]
product = np.ones_like(mu_u) # E[u] below the current node
joint = np.ones_like(mu_u) # E[u M] below the current node
for level in range(self.num_levels - 1, -1, -1):
mean = mu_path[..., level]
var = var_path[..., level]
joint = (var + mean**2) * joint + (
mean * mu_other[..., level] - var
) * product * sibling_mass[..., level]
product = product * mean
mass = mass[:, None]
prob = mu_u / mass
cov = joint - mu_u * mass
var_mass = second[:, None] - mass**2
var = (var_u - 2.0 * prob * cov + prob**2 * var_mass) / mass**2
return prob, np.maximum(var, 0.0)
[docs]
def _subtree_mass(self, mu_z, var_z, second_moment=False):
"""Sum M of the class probabilities, without visiting every class.
Subtrees that contain all their classes sum to one. The sum of an
incomplete subtree is P * (sum of the + subtree) + (1 - P) * (sum of
the - subtree), evaluated from the deepest level up, with 1 - P
computed as Phi(-a).
:return: E[M] (N,); with ``second_moment``, also the table of E[M] of
every incomplete subtree (followed by the columns 0 and 1 for a
missing and a complete subtree) and E[M^2] (N,).
"""
units = self._ragged_units
gain = self._unit_to_gain[units]
mu_p, mu_q, var_p = _branch_mean_var(
mu_z[:, units].astype(np.float64),
var_z[:, units].astype(np.float64),
self.mu_gain[gain],
self.var_gain[gain],
second_moment,
)
total = np.empty((mu_z.shape[0], units.shape[0] + 2))
total[:, -2] = 0.0
total[:, -1] = 1.0
if second_moment:
square = total.copy()
for start, stop, plus, minus in self._ragged_groups:
p, q = mu_p[:, start:stop], mu_q[:, start:stop]
total[:, start:stop] = p * total[:, plus] + q * total[:, minus]
if second_moment:
var = var_p[:, start:stop]
square[:, start:stop] = (
(var + p**2) * square[:, plus]
+ 2.0 * (p * q - var) * total[:, plus] * total[:, minus]
+ (var + q**2) * square[:, minus]
)
root = self._root_position
if not second_moment:
return total[:, root], None, None
return total[:, root], total, square[:, root]