dit.algorithms
Various algorithms related to manipulating or measuring properties of distributions.
Classes
Base class that performs many methods related to optimizing auxiliary variables. |
|
Implement convex optimization. |
|
Implement non-convex optimization. |
|
Base class for performing optimizations. |
Functions
Compute the cumulative distribution function P(X <= x). |
|
Compute the n-th central moment E[(X - mu)^n]. |
|
Calculates the channel capacity from conditional distributions P(Y|X). |
|
Capacity of a channel whose inputs carry a cost, under an average budget. |
|
Compute the channel capacity from |
|
The commitment capacity of a discrete memoryless channel [WNI03]. |
|
Compute the Pearson correlation matrix for a joint distribution. |
|
Compute the covariance matrix for a joint distribution. |
|
Returns the degrees of freedom of a marginal model: the number of free parameters needed to specify the maximum entropy distribution consistent with the marginals in structure. |
|
Returns a new distribution with an expanded sample space. |
|
Compute E[f(X)] for an arbitrary callable f. |
|
Fit a convex combination of lifts of marginals of order at most |
|
Fit a \(k\)-mixture of product distributions to |
|
Returns a new distribution with the minimal sufficient statistics of each random variable in rvs about all the other variables. |
|
Returns a new distribution with the join inserted at index idx. |
|
Returns a new distribution with the meet inserted at index idx. |
|
Inserts the minimal sufficient statistic of rvs about about into dist at index idx. |
|
Return the maximum entropy distribution consistent with the marginals from dist specified in rvs, computed via Iterative Proportional Fitting. |
|
Compute the interquartile range (Q3 - Q1). |
|
Compute the kurtosis (4th standardised moment). |
|
Lift a marginal on coordinates |
|
Project |
|
Reverse-KL m-projection with symmetric \(P_\varepsilon\), taking \(\varepsilon \downarrow 0\) along |
|
Project |
|
Ladder of marginal-lift mixtures for orders \(0,\ldots,k_{\max}\). |
|
Return the marginal-constrained maximum entropy distributions. |
|
Return the maximum entropy distribution consistent with the marginals from dist specified in rvs. |
|
The maximal equivocation of a channel, |
|
Maximize a convex function over a polytope. |
|
Return the largest outcome in the support (per index). |
|
Compute the mean (expected value) of a distribution. |
|
Compute the median of a distribution. |
|
Build the linear design matrix for the order- |
|
Return the m-flat projection ladder \(Q^{(0)},\ldots,Q^{(k_{\max})}\). |
|
Downward-closed collection of index-tuples for an antichain dependency. |
|
Return the smallest outcome in the support (per index). |
|
Fit the mixture-of-products ladder \(Q^{(1)},\ldots,Q^{(k_{\max})}\). |
|
Compute the modes of a distribution. |
|
Construct the sigma algebra for the minimal sufficient statistic of rvs about about. |
|
The inputs of the non-redundant version of a channel [WNI03]. |
|
Run |
|
Compute the p-th percentile (0 <= p <= 100). |
|
Returns a new distribution with pruned sample space. |
|
Compute the q-quantile of a distribution (0 <= q <= 1). |
|
Compute the range (maximum - minimum) of the support per index. |
|
Sibson's capacity of order alpha, |
|
Compute the skewness (3rd standardised moment). |
|
The nominal spectral lower bound on the entanglement. |
|
Compute the standard deviation sqrt(Var(X)). |
|
Compute the n-th standardised moment E[((X - mu)/sigma)^n]. |
|
The 0/1 biadjacency matrix of the support graph of a pair. |
|
The singular values of the support graph's biadjacency matrix. |
|
Symmetric full-support smoothing \(P_\varepsilon = (1-\varepsilon)P + \varepsilon U\). |
|
Compute the variance Var(X) = E[(X - mu)^2]. |
Reference
- class BaseAuxVarOptimizer(dist, rvs=None, crvs=None)[source]
Bases:
BaseNonConvexOptimizerBase class that performs many methods related to optimizing auxiliary variables.
- construct_joint(x)[source]
Construct the joint distribution.
- Parameters:
x (np.ndarray) – An optimization vector.
- Returns:
joint – The joint distribution resulting from the distribution passed in and the optimization vector.
- Return type:
np.ndarray
- construct_full_joint(x)[source]
Construct the joint distribution.
- Parameters:
x (np.ndarray) – An optimization vector.
- Returns:
joint – The joint distribution resulting from the distribution passed in and the optimization vector.
- Return type:
np.ndarray
- construct_random_initial()[source]
Construct a random optimization vector.
- Returns:
x – A random optimization vector.
- Return type:
np.ndarray
- construct_uniform_initial()[source]
Construct a uniform optimization vector.
- Returns:
x – A uniform optimization vector.
- Return type:
np.ndarray
- construct_copy_initial()[source]
Construct a copy optimization vector.
- Returns:
x – A copy optimization vector.
- Return type:
np.ndarray
- construct_constant_initial()[source]
Construct a constant optimization vector.
- Returns:
x – A constant optimization vector.
- Return type:
np.ndarray
- construct_initial()
Construct a random optimization vector.
- Returns:
x – A random optimization vector.
- Return type:
np.ndarray
- construct_distribution(x=None, cutoff=1e-05)[source]
Construct the distribution.
- Parameters:
x (np.ndarray, None) – An optimization vector. If None, use self._optima.
cutoff (float) – Ignore probabilities smaller than this.
- Returns:
d – The original distribution, plus its auxiliary variables.
- Return type:
- class BaseConvexOptimizer(dist, rvs=None, crvs=None)[source]
Bases:
BaseOptimizerImplement convex optimization.
- class BaseNonConvexOptimizer(dist, rvs=None, crvs=None)[source]
Bases:
BaseOptimizerImplement non-convex optimization.
- class BaseOptimizer(dist, rvs=None, crvs=None)[source]
Bases:
objectBase class for performing optimizations.
- abstractmethod construct_initial()[source]
Select the default method of generating an initial condition.
- Returns:
x – An optimization vector.
- Return type:
np.ndarray
- construct_random_initial()[source]
Construct a random optimization vector.
- Returns:
x – A random optimization vector.
- Return type:
np.ndarray
- construct_uniform_initial()[source]
Construct a uniform optimization vector.
- Returns:
x – A uniform optimization vector.
- Return type:
np.ndarray
- optimize(x0=None, niter=None, maxiter=None, polish=1e-06, callback=False, rng=None)[source]
Perform the optimization.
- Parameters:
x0 (np.ndarray) – An initial optimization vector.
niter (int) – The number of optimization iterations to perform.
maxiter (int) – The number of steps for an optimization subroutine to perform.
polish (float) – The threshold for valid optimization elements. If 0, no polishing is performed.
callback (bool) – Whether to use a callback to track the performance of the optimization. Generally, this should be False as it adds some significant time to the optimization.
rng (np.random.Generator, int, None) – An optional random number generator used for all randomness in this optimization (random initial conditions and the basin-hopping step). When None (default), the global
np.randomstate is used, preserving backwards-compatible behavior. Supplying a per-task generator isolates parallel outer sweeps from one another.
- Returns:
result – The result of the optimization.
- Return type:
OptimizeResult
- cdf(dist)[source]
Compute the cumulative distribution function P(X <= x).
For a 1-D distribution, returns
(values, cumprobs)where values are the sorted unique outcomes and cumprobs are the corresponding cumulative probabilities.For a multi-dimensional distribution, returns a list of
(values, cumprobs)tuples, one per index (marginal CDF).- Parameters:
dist (Distribution)
- Returns:
result – For 1-D:
(values, cumprobs). For multi-D:[(values_0, cumprobs_0), …].- Return type:
- central_moment(dist, n)[source]
Compute the n-th central moment E[(X - mu)^n].
- Parameters:
dist (Distribution)
n (int) – Which moment to compute.
- Returns:
moments – The n-th central moment of each index of the outcomes.
- Return type:
ndarray
- channel_capacity(cdists, marginal=None, rtol=None, atol=None, maxiter=100000, method='accelerated', eliminate=False)[source]
Calculates the channel capacity from conditional distributions P(Y|X).
The capacity is computed with the Blahut-Arimoto algorithm [Ari72, Bla72], stopping once Blahut’s lower and upper bounds on the capacity agree to within tolerance, so the returned value is within
max(atol, rtol * C)bits of the true capacity. Weakly symmetric [CT06] and square nonsingular channels are solved in closed form when the closed form certifies.- Parameters:
cdists (list, ndarray, Distribution) – A list of conditional distributions, a 2D array where rows are inputs and columns are outputs, or a conditional Distribution such as p(Y|X).
marginal (distribution | None) – The marginal distribution P(X). If provided, P*(X) is returned as a distribution object. If None, P*(X) is returned as a numpy array.
rtol (float or None) – Relative tolerance on the capacity. Defaults to ditParams[‘rtol’].
atol (float or None) – Absolute tolerance on the capacity, in bits. Defaults to ditParams[‘atol’].
maxiter (int) – Maximum number of Blahut-Arimoto iterations. A
RuntimeWarningis raised if the bounds have not met by then.method ({'accelerated', 'ba'}) –
'ba'is the classic iteration;'accelerated'takes the stepr <- r exp(mu D)of [MD04] with the adaptivemu = D(r_k || r_{k-1}) / D(q_k || q_{k-1}), falling back to the classic step whenever the mutual information would decrease.eliminate (bool) – If True, iterate on a growing active set of inputs [Say00]. This helps when only a few of many inputs carry probability at capacity.
- Returns:
cc (float) – The channel capacity.
marginal_opt (distribution or ndarray) – The optimal marginal P*(X).
- channel_capacity_cost(cdists, cost, budget, rtol=None, atol=None, maxiter=100000, method='accelerated')[source]
Capacity of a channel whose inputs carry a cost, under an average budget.
Computes
C(B) = max { I[X : Y] : E[cost(X)] <= B }through Blahut’s Lagrangian form [Bla72]: for a multipliers >= 0the iteration maximizesI[X : Y] - s E[cost(X)](the offset divergencesD(P_x || q) - s cost(x)keep the bound-gap certificate), andC(B) = min_s max_p I - s (E[cost] - B). The multiplier is found by root-findingE[cost] = B.- Parameters:
cdists (list, ndarray, Distribution) – The channel, in any form accepted by
channel_capacity().cost (array_like) – The cost of each input, in the same order as the channel’s rows.
budget (float) – The maximum average cost.
rtol (float or None) – Relative tolerance. Defaults to ditParams[‘rtol’].
atol (float or None) – Absolute tolerance in bits. Defaults to ditParams[‘atol’].
maxiter (int) – Maximum Blahut-Arimoto iterations per value of the multiplier.
method ({'accelerated', 'ba'}) – As in
channel_capacity().
- Returns:
cc (float) – The cost-constrained capacity, in bits.
pmf (np.ndarray) – An input distribution achieving it. If the optimal input at the final multiplier is not unique its cost may differ slightly from
budget.s (float) – The Lagrange multiplier, in bits per unit cost; the slope of
C(B).0when the budget does not bind andinfwhen only the cheapest inputs are affordable.
- Raises:
ditException – If the budget is below the cheapest input’s cost.
- channel_capacity_joint(dist, input_, output, marginal=False)[source]
Compute the channel capacity from
input_tooutput.- Parameters:
dist (Distribution) – The joint distribution.
input (iterable) – The random variables that are the input of the channel.
output (iterable) – The random variables that are the output of the channel.
marginal (bool) – Whether to return the marginal distribution. Defaults to False.
- commitment_capacity(cdists, rtol=None, atol=None, maxiter=100000, redundancy_tol=1e-09)[source]
The commitment capacity of a discrete memoryless channel [WNI03].
This is the largest rate at which Alice can commit to a message through the channel: Bob learns almost nothing about it until she reveals it, and she cannot reveal a different message, except with vanishing probability. Unlimited noiseless two-way communication is allowed on the side. Winter, Nascimento and Imai show that it is the maximal equivocation of the channel once its redundant inputs are removed:
C_com = max_p H[X | Y], with p ranging over inputs of the non-redundant channel.
See
nonredundant_inputs()andmaximal_equivocation(). The commitment capacity is zero exactly when the output of the non-redundant channel determines its input; every other channel allows bit commitment. It is also a lower bound on the rate at which the channel allows coin tossing.- Parameters:
cdists (list, ndarray, Distribution) – The channel, in any form accepted by
channel_capacity().rtol (float or None) – Relative tolerance. Defaults to ditParams[‘rtol’].
atol (float or None) – Absolute tolerance in bits. Defaults to ditParams[‘atol’].
maxiter (int) – Maximum number of iterations. A
RuntimeWarningis raised if the bounds have not met by then.redundancy_tol (float) – Passed to
nonredundant_inputs()asatol. The commitment capacity is not continuous in the channel: inputs closer than this count as one. For instance, the binary symmetric channel’s commitment capacityH_b(p)tends to one bit asptends to1/2, but atp = 1/2its two inputs coincide and it is zero.
- Returns:
cc (float) – The commitment capacity, in bits.
pmf (np.ndarray) – An optimal input distribution. It is zero on redundant inputs.
- correlation(dist)[source]
Compute the Pearson correlation matrix for a joint distribution.
For a distribution over d random variables, returns a d x d matrix where entry (i, j) is Cor(Xi, Xj) = Cov(Xi, Xj) / (sigma_i * sigma_j).
- Parameters:
dist (Distribution)
- Returns:
cor
- Return type:
ndarray, shape (d, d)
- covariance(dist)[source]
Compute the covariance matrix for a joint distribution.
For a distribution over d random variables, returns a d x d matrix where entry (i, j) is Cov(Xi, Xj).
For a 1-D distribution the result is a 1x1 array containing the variance.
- Parameters:
dist (Distribution)
- Returns:
cov
- Return type:
ndarray, shape (d, d)
- degrees_of_freedom(dist, structure=None)[source]
Returns the degrees of freedom of a marginal model: the number of free parameters needed to specify the maximum entropy distribution consistent with the marginals in structure.
This is the “complexity” of a reconstructability-analysis model. It is the rank of the marginal constraint matrix (which includes the normalization constraint) minus one for that normalization constraint.
- Parameters:
dist (distribution) – The distribution defining the sample space and the marginal values.
structure (sequence, None) – A sequence whose elements are also sequences, each specifying a marginal (a “projection”) to constrain, e.g.
[[0, 1], [1, 2]]forAB:BC. If None, the independence model (each variable on its own) is used.
- Returns:
df – The degrees of freedom of the model.
- Return type:
Examples
>>> d = dit.uniform_distribution(3, 2) >>> dit.algorithms.degrees_of_freedom(d, [[0, 1], [2]]) 4 >>> dit.algorithms.degrees_of_freedom(d, [[0, 1], [1, 2]]) 5
- expanded_samplespace(d, alphabets=None, union=True)[source]
Returns a new distribution with an expanded sample space.
Expand the sample space so that it is the Cartesian product of the alphabets for each random variable.
- Parameters:
d (distribution) – The distribution used to create the pruned distribution.
alphabets (list) – A list of alphabets, with length equal to the outcome length in d. Each alphabet specifies the alphabet to be used for a single index random variable. The sample space of the new distribution will be the Cartesian product of these alphabets.
union (bool) – If True, then the alphabet for each random variable is unioned. The unioned alphabet is then used for each random variable.
- Returns:
ed – The distribution with an expanded sample space.
- Return type:
distribution
- expectation(dist, f=None)[source]
Compute E[f(X)] for an arbitrary callable f.
When f is
Nonethis is equivalent tomean().- Parameters:
dist (Distribution) – The distribution.
f (callable or None) – A function that maps an outcome to a numeric value (scalar or array). If
None, the identity function is used.
- Returns:
result – The expected value E[f(X)].
- Return type:
float or ndarray
- fit_marginal_lift_mixture(dist, order, mode='uniform', n_init=12, rng=0)[source]
Fit a convex combination of lifts of marginals of order at most
order.- Returns:
result – Keys
dist,labels,alpha,L2.- Return type:
- fit_mixture_of_products(dist, k, *, n_init=12, maxiter=200, tol=1e-10, rng=0)[source]
Fit a \(k\)-mixture of product distributions to
distby EM.- Parameters:
dist (Distribution) – Target joint.
k (int) – Number of mixture components.
n_init (int) – Random restarts and EM iteration cap.
maxiter (int) – Random restarts and EM iteration cap.
tol (float) – Log-likelihood convergence tolerance.
rng (np.random.Generator, int, None) – Source of randomness for the restarts.
- Returns:
result – Keys
dist(fittedDistribution),pi,conds,I_xv(\(I(X;V)\) under data-weighted responsibilities),H_v,loglik.- Return type:
- info_trim(dist, rvs=None)[source]
Returns a new distribution with the minimal sufficient statistics of each random variable in rvs about all the other variables.
- Parameters:
dist (Distribution) – The distribution contiaining the random variables from which the joint minimal sufficent statistic will be computed.
rvs (list) – A list of random variables to be compressed into minimal sufficient statistics.
- insert_join(dist, idx, rvs, support_only=False)[source]
Returns a new distribution with the join inserted at index idx.
The join of the random variables in rvs is constructed and then inserted into at index idx.
- Parameters:
dist (Distribution) – The distribution which defines the base sigma-algebra.
idx (int) – The index at which to insert the join. To append the join, set idx to be equal to -1 or dist.outcome_length().
rvs (list) – A list of lists. Each list specifies a random variable to be met with the other lists. Each random variable can defined as a series of unique indexes. Multiple random variables can use the same index. For example, [[0, 1], [1, 2]].
support_only (bool) – If True, only consider outcomes with non-zero probability.
- Returns:
d – The new distribution with the join at index idx.
- Return type:
- insert_meet(dist, idx, rvs, support_only=False)[source]
Returns a new distribution with the meet inserted at index idx.
The meet of the random variables in rvs is constructed and then inserted into at index idx.
- Parameters:
dist (Distribution) – The distribution which defines the base sigma-algebra.
idx (int) – The index at which to insert the meet. To append the meet, set idx to be equal to -1 or dist.outcome_length().
rvs (list) – A list of lists. Each list specifies a random variable to be met with the other lists. Each random variable can defined as a series of unique indexes. Multiple random variables can use the same index. For example, [[0,1],[1,2]].
support_only (bool) – If True, only consider outcomes with non-zero probability.
- Returns:
d – The new distribution with the meet at index idx.
- Return type:
- insert_mss(dist, idx, rvs, about=None)[source]
Inserts the minimal sufficient statistic of rvs about about into dist at index idx.
- Parameters:
dist (Distribution) – The distribution which defines the base sigma-algebra.
idx (int) – The location in the distribution to insert the minimal sufficient statistic.
rvs (list) – A list of random variables to be compressed into a minimal sufficient statistic.
about (list) – A list of random variables for which the minimal sufficient static will retain all information about.
- Returns:
d – The distribution dist modified to contain the minimal sufficient statistic.
- Return type:
Examples
>>> d = Xor() >>> print(insert_mss(d, -1, [0], [1, 2])) Class: Distribution Alphabet: ('0', '1') for all rvs Base: linear Outcome Class: str Outcome Length: 4 RV Names: None x p(x) 0000 0.25 0110 0.25 1011 0.25 1101 0.25
- ipf_dist(dist, rvs, tol=1e-10, maxiter=10000, sparse=True, return_status=False)[source]
Return the maximum entropy distribution consistent with the marginals from dist specified in rvs, computed via Iterative Proportional Fitting.
- Parameters:
dist (Distribution) – The distribution whose marginals should be matched.
rvs (list of lists) – The marginals from dist to constrain. Each inner list specifies a set of random variables (a marginal “projection”) to hold fixed, e.g.
[[0, 1], [1, 2]]for the structureAB:BC.tol (float) – The convergence tolerance. Iteration stops once the largest deviation of any constrained marginal from its target falls below tol.
maxiter (int) – The maximum number of IPF cycles to perform.
sparse (bool) – Whether the returned distribution should be sparse or dense.
return_status (bool) – If True, return a
(me, converged)tuple, where converged is True iff the final marginal deviation fell below tol within maxiter cycles. IPF converges only linearly on cyclic structures with induced structural zeros, so callers that need an exact answer should check this flag and fall back to a convex optimizer when it is False.
- Returns:
me (Distribution) – The maximum entropy distribution.
converged (bool) – Only returned when return_status is True (see above).
- iqr(dist)[source]
Compute the interquartile range (Q3 - Q1).
- Parameters:
dist (Distribution)
- Returns:
iqr
- Return type:
ndarray
- kurtosis(dist, excess=True)[source]
Compute the kurtosis (4th standardised moment).
- Parameters:
dist (Distribution)
excess (bool) – If
True(default), return excess kurtosis (subtract 3 so that a normal distribution has kurtosis 0). IfFalse, return the raw 4th standardised moment.
- Returns:
kurt
- Return type:
ndarray
- lift_marginal(outs, pmf, alph, S, mode='uniform')[source]
Lift a marginal on coordinates
Sto a full joint pmf.
- m_projection(dist, order, nrestarts=16, maxiter=3000, warm_start=None, criterion='reverse_kl', eps=None)[source]
Project
distonto the order-orderm-flat mixture family.- Parameters:
dist (Distribution) – The target distribution \(P\).
order (int) – Maximum ANOVA order kept in \(\mathcal{M}_{\mathrm{order}}\).
nrestarts (int) – Optimizer controls.
maxiter (int) – Optimizer controls.
warm_start (Distribution or None) – Optional warm start.
criterion ({'reverse_kl', 'forward_kl', 'jsd'}) – Projection objective.
eps (float or None) – For
reverse_kl, weight in \(P_\varepsilon=(1-\varepsilon)P+\varepsilon U\). Defaults to1e-8whenNone.
- Returns:
q
- Return type:
- m_projection_eps_limit(dist, subsets=None, order=None, eps_schedule=(0.0001, 1e-06, 1e-08), nrestarts=16, maxiter=3000, warm_start=None)[source]
Reverse-KL m-projection with symmetric \(P_\varepsilon\), taking \(\varepsilon \downarrow 0\) along
eps_schedule.
- m_projection_from_subsets(dist, subsets, nrestarts=16, maxiter=3000, warm_start=None, criterion='reverse_kl', eps=None)[source]
Project
distonto the m-flat family spanned bysubsets.
- marginal_lift_dists(dist, k_max=None, mode='uniform', n_init=12, rng=0)[source]
Ladder of marginal-lift mixtures for orders \(0,\ldots,k_{\max}\).
Order 0 is the uniform distribution. Order \(n\) includes the full joint as a block and recovers \(P\) exactly.
- marginal_maxent_dists(dist, k_max=None)[source]
Return the marginal-constrained maximum entropy distributions.
- maxent_dist(dist, rvs, x0=None, maxiter=1000, sparse=True, method='ipf')[source]
Return the maximum entropy distribution consistent with the marginals from dist specified in rvs.
- Parameters:
dist (Distribution) – The distributions whose marginals should be matched.
rvs (list of lists) – The marginals from dist to constrain.
x0 (np.ndarray) – Initial condition for the scipy optimizer. Ignored when method is ‘ipf’, which always starts from the uniform distribution.
maxiter (int) – The number of optimization iterations to perform. Used only by the scipy optimizer; IPF uses its own convergence tolerance.
sparse (bool) – Whether the returned distribution should be sparse or dense.
method (str) – The algorithm used to compute the maximum entropy distribution. ‘ipf’ (the default) uses Iterative Proportional Fitting, which is typically far faster than the convex optimizer. IPF converges only linearly on cyclic structures with induced structural zeros, so when it fails to converge within its iteration budget this falls back to the scipy optimizer to preserve accuracy. ‘scipy’ (also accepts ‘slsqp’) forces the scipy convex optimizer.
- Returns:
me – The maximum entropy distribution.
- Return type:
- maximal_equivocation(cdists, rtol=None, atol=None, maxiter=100000)[source]
The maximal equivocation of a channel,
max_p H[X | Y].The equivocation is concave in the input. For an input
rwith outputq = rP, its gradient isg_x = -log2 r(x) - D(P_x || q), and ther-average ofgisH[X | Y]. So every input certifiesH[X | Y] <= max_p H[X | Y] <= max_x g_x, and the iterationr(x) ∝ 2^(-D(P_x || q)), an alternating maximization in the style of Blahut-Arimoto, stops once the two bounds agree to withinmax(atol, rtol * value)bits. It never decreases the equivocation. Inputs whose output supports overlap are solved together, and separately from the others.This is the secrecy capacity of a wiretap channel [Wyn75a] whose legitimate receiver sees the input noiselessly and whose eavesdropper sees it through the channel. Unlike
commitment_capacity(), it counts redundant inputs.- Parameters:
cdists (list, ndarray, Distribution) – The channel, in any form accepted by
channel_capacity().rtol (float or None) – Relative tolerance. Defaults to ditParams[‘rtol’].
atol (float or None) – Absolute tolerance in bits. Defaults to ditParams[‘atol’].
maxiter (int) – Maximum number of iterations. A
RuntimeWarningis raised if the bounds have not met by then.
- Returns:
value (float) – The maximal equivocation, in bits.
pmf (np.ndarray) – An input distribution attaining it.
- maximize_convex_function(f, A_ineq, b_ineq, A_eq=None, b_eq=None)[source]
Maximize a convex function over a polytope. This function uses the fact that the maximum of a convex function over a polytope will be achieved at one of the extreme points of the polytope.
The maximization is done by taking a system of linear inequalities, using the pypoman library to create a list of extreme points, and then evaluating the objective function on each point.
- Parameters:
f (function) – Objective function to maximize
A_ineq (matrix) – Specifies inequalities matrix, should be num_inequalities x num_variables
b_ineq (array) – Specifies inequalities vector, should be num_inequalities long
A_eq (matrix) – Specifies equalities matrix, should be num_equalities x num_variables
b_eq (array) – Specifies equalities vector, should be num_equalities long
- Returns:
optimal_extreme_point (np.ndarray) – The extreme point at which the maximum is attained.
maximum_function_value (float) – The maximum value of
f.
- maximum(dist)[source]
Return the largest outcome in the support (per index).
- Parameters:
dist (Distribution)
- Returns:
maxs
- Return type:
ndarray
- mean(dist)[source]
Compute the mean (expected value) of a distribution.
- Parameters:
dist (Distribution)
- Returns:
means – The mean of each index of the outcomes.
- Return type:
ndarray
- median(dist)[source]
Compute the median of a distribution.
- Parameters:
dist (Distribution)
- Returns:
medians – The median of each index of the outcomes.
- Return type:
ndarray
- mflat_design_matrix(alphabets, order)[source]
Build the linear design matrix for the order-
orderm-flat family.Columns are indicator features \(1_{x_S = a}\) for every subset \(S\) with \(|S| \le\)
orderand every assignmentaon the corresponding alphabets. Any pmf in \(\mathcal{M}_{\mathrm{order}}\) is then \(q = A\theta\) for some coefficient vectorθ(subject to nonnegativity and normalization ofq).- Parameters:
alphabets (sequence of sequences) – The alphabet of each variable.
order (int) – Maximum interaction order kept in the additive pmf expansion.
- Returns:
A (np.ndarray, shape (n_outcomes, n_features)) – Design matrix over the Cartesian product of
alphabets.outcomes (list of tuple) – Row-aligned Cartesian outcomes.
- mflat_mprojection_dists(dist, k_max=None, nrestarts=16, maxiter=3000, criterion='reverse_kl', eps=None, eps_schedule=None)[source]
Return the m-flat projection ladder \(Q^{(0)},\ldots,Q^{(k_{\max})}\).
- mflat_subsets_from_dependency(dependency, index_map=None)[source]
Downward-closed collection of index-tuples for an antichain dependency.
For a node \(\pi\), the m-flat family is spanned by additive components on every nonempty \(S \subseteq T\) for some block \(T \in \pi\) (plus a constant).
- Parameters:
dependency (iterable of iterables) – Lattice node: an antichain of variable blocks (names or indices).
index_map (dict or None) – Map from block element → integer coordinate index. Defaults to identity.
- Returns:
subsets – Sorted index tuples, all nonempty.
- Return type:
- minimum(dist)[source]
Return the smallest outcome in the support (per index).
- Parameters:
dist (Distribution)
- Returns:
mins
- Return type:
ndarray
- mixture_of_products_dists(dist, k_max=None, *, n_init=12, maxiter=200, tol=1e-10, rng=0, early_stop=True, kl_tol=1e-08)[source]
Fit the mixture-of-products ladder \(Q^{(1)},\ldots,Q^{(k_{\max})}\).
- Parameters:
dist (Distribution)
k_max (int or None) – Maximum number of components. Default
min(8, |X|).n_init – Passed to
fit_mixture_of_products()(an integer seed is offset byk).maxiter – Passed to
fit_mixture_of_products()(an integer seed is offset byk).tol – Passed to
fit_mixture_of_products()(an integer seed is offset byk).rng – Passed to
fit_mixture_of_products()(an integer seed is offset byk).early_stop (bool) – If True, stop once \(D(P\Vert Q^{(k)}) <\)
kl_tol.kl_tol (float) – Forward-KL threshold for early stopping.
- Returns:
dists (list of Distribution) –
dists[k-1]is the MLE in \(\mathcal{F}_k\).meta (list of dict) – Per-
kdiagnostics (I_xv,H_v,loglik,pi,conds).
- mode(dist)[source]
Compute the modes of a distribution.
- Parameters:
dist (Distribution)
- Returns:
modes – A list of arrays, one for each index of the outcomes. Each array contains the modes of that index.
- Return type:
list of ndarray
- mss(dist, rvs, about=None, int_outcomes=True)[source]
- Parameters:
dist (Distribution) – The distribution which defines the base sigma-algebra.
rvs (list) – A list of random variables to be compressed into a minimal sufficient statistic.
about (list) – A list of random variables for which the minimal sufficient static will retain all information about.
int_outcomes (bool) – If True, then the outcomes of the minimal sufficient statistic are relabeled as integers instead of as the atoms of the induced sigma-algebra.
- Returns:
d – The distribution of the minimal sufficient statistic.
- Return type:
Examples
>>> d = Xor() >>> print(mss(d, [0], [1, 2])) Class: Distribution Alphabet: (0, 1) Base: linear x p(x) 0 0.5 1 0.5
- mss_sigalg(dist, rvs, about=None)[source]
Construct the sigma algebra for the minimal sufficient statistic of rvs about about.
- Parameters:
dist (Distribution) – The distribution which defines the base sigma-algebra.
rvs (list) – A list of random variables to be compressed into a minimal sufficient statistic.
about (list) – A list of random variables for which the minimal sufficient static will retain all information about.
- Returns:
mss_sa – The induced sigma-algebra of the minimal sufficient statistic.
- Return type:
frozenset of frozensets
Examples
>>> d = Xor() >>> mss_sigalg(d, [0], [1, 2]) frozenset({frozenset(), frozenset({'000', '011'}), frozenset({'101', '110'}), frozenset({'000', '011', '101', '110'})})
- nonredundant_inputs(cdists, atol=1e-09)[source]
The inputs of the non-redundant version of a channel [WNI03].
An input is redundant when its output distribution is a convex combination of the other inputs’ output distributions, since it can then be simulated by randomizing over them. Removing every redundant input leaves one input for each vertex of the convex hull of the output distributions. Of several inputs with the same output distribution, the first is kept.
Each input is tested with a linear program for the l1 distance from its output distribution to the convex hull of the others’, from the last input to the first and against the inputs still present.
- Parameters:
cdists (list, ndarray, Distribution) – The channel, in any form accepted by
channel_capacity().atol (float) – An input counts as redundant when its output distribution is within this l1 distance of the convex hull of the others’.
- Returns:
inputs – The indices of the remaining inputs, in increasing order.
- Return type:
np.ndarray
- parallel_sweep(func, items, *, base_seed=None)[source]
Run
func(item, rng)for each item in items, in parallel when safe.Each task gets its own
numpy.random.Generatorseeded deterministically (from base_seed, or a single draw from the globalnp.randomstate when base_seed is None) so that workers never race the global RNG and results are reproducible with respect to a seedednp.random. The serial and parallel paths consume the same per-task generators, so a sweep produces identical results regardless ofDIT_OPT_JOBS.Results are returned in input order, so
max/min/appendover them stay deterministic.- Parameters:
func (callable) – Called as
func(item, rng)whererngis aGenerator.items (iterable) – The independent work items.
base_seed (int, np.random.Generator, None) – Seed offset for the per-task generators. A Generator contributes one draw; if None, a seed is drawn once (serially) from the global
np.randomstate.
- Returns:
results –
[func(item, rng) for item in items]in input order.- Return type:
- percentile(dist, p)[source]
Compute the p-th percentile (0 <= p <= 100).
Equivalent to
quantile(dist, p / 100).- Parameters:
dist (Distribution)
p (float) – Percentile in [0, 100].
- Returns:
result
- Return type:
ndarray
- pruned_samplespace(d, sample_space=None)[source]
Returns a new distribution with pruned sample space.
The pruning is such that zero probability outcomes are removed.
- Parameters:
d (distribution) – The distribution used to create the pruned distribution.
sample_space (set) – A list of outcomes with zero probability that should be kept in the sample space. If None, then all outcomes with zero probability will be removed.
- Returns:
pd – The distribution with a pruned sample space.
- Return type:
distribution
- quantile(dist, q)[source]
Compute the q-quantile of a distribution (0 <= q <= 1).
Uses the “lower” interpolation method: returns the largest outcome x such that P(X <= x) <= q, averaging with the next outcome when P(X <= x) == q exactly (matching
median()behaviour).For multi-dimensional distributions, operates on the marginal of each index independently.
- Parameters:
dist (Distribution)
q (float) – Probability level in [0, 1].
- Returns:
quantiles
- Return type:
ndarray
- range_(dist)[source]
Compute the range (maximum - minimum) of the support per index.
(Named
range_to avoid shadowing the built-inrange.)- Parameters:
dist (Distribution)
- Returns:
r
- Return type:
ndarray
- sibson_capacity(cdists, order, rtol=None, atol=None, maxiter=100000)[source]
Sibson’s capacity of order alpha,
C_alpha = max_p I_alpha(X : Y).Sibson’s alpha-mutual information is
I_alpha(X : Y) = alpha / (alpha - 1) log2 sum_y (sum_x p(x) P(y|x)^alpha)^(1/alpha),
and its maximum over inputs equals the Rényi radius
min_q max_x D_alpha(P_x || q)[Csiszar95]. Every inputrtherefore gives the boundsI_alpha(r) <= C_alpha <= max_x D_alpha(P_x || q_r), whereq_ris Sibson’s optimal output forr. The iterationr <- r exp(mu D_alpha(P_x || q_r))withmu = max(1, alpha)reduces to Blahut-Arimoto atalpha = 1; the step is halved wheneverI_alphawould decrease, and the iteration stops once the bounds meet.- Parameters:
cdists (list, ndarray, Distribution) – The channel, in any form accepted by
channel_capacity().order (float) – The order
alpha > 0.1gives the Shannon capacity andnumpy.infthe maximal leakage capacitylog2 sum_y max_x P(y|x).rtol (float or None) – Relative tolerance. Defaults to ditParams[‘rtol’].
atol (float or None) – Absolute tolerance in bits. Defaults to ditParams[‘atol’].
maxiter (int) – Maximum number of iterations.
- Returns:
cc (float) – The capacity of order alpha, in bits.
pmf (np.ndarray) – An optimal input distribution.
- skewness(dist)[source]
Compute the skewness (3rd standardised moment).
Measures asymmetry of the distribution. Zero for symmetric distributions, positive for right-skewed, negative for left-skewed.
- Parameters:
dist (Distribution)
- Returns:
skew
- Return type:
ndarray
- spectral_entanglement_bound(dist, rvs=None, crvs=None)[source]
The nominal spectral lower bound on the entanglement.
Matveev & Romashchenko [MR26b] bound the entanglement of a pair uniform on its support from below by
\[E(X, Y) \geq \min\{ I[X{:}Y],\ 2\log(\lambda_1 / \lambda_2) \} - O(\log H[XY]),\]which is what certifies that expander-like supports are maximally non-extractable. This function returns the nominal term
min{I, 2 log(lambda_1 / lambda_2)}only.Warning
The suppressed
O(log H[XY])slop is not a formality; it dominates at small alphabets. The uniform distribution on an 8-cycle has entanglement about0.67bits against a nominal bound of1.00. Use this to compare pairs or to reason asymptotically, never as a pointwise certificate.- Parameters:
dist (Distribution) – The distribution of interest.
rvs (list of lists, None) – The two variables. If None, all variables of dist are used.
crvs (list, None) – Variables to condition on.
- Returns:
bound – The nominal bound, in bits. Infinite spectral gap (a support with only one nonzero singular value, i.e. a complete bipartite graph on each component) returns the mutual information.
- Return type:
- standard_deviation(dist)[source]
Compute the standard deviation sqrt(Var(X)).
- Parameters:
dist (Distribution)
- Returns:
std
- Return type:
ndarray
- standard_moment(dist, n)[source]
Compute the n-th standardised moment E[((X - mu)/sigma)^n].
- Parameters:
dist (Distribution)
n (int)
- Returns:
moments
- Return type:
ndarray
- support_biadjacency(dist, rvs=None, crvs=None)[source]
The 0/1 biadjacency matrix of the support graph of a pair.
- Parameters:
dist (Distribution) – The distribution of interest.
rvs (list of lists, None) – The two variables. If None, all variables of dist are used.
crvs (list, None) – Variables to condition on. Conditioning variables are folded into both sides, so the support graph is that of the coalesced pair.
- Returns:
matrix – The 0/1 matrix, with a one wherever the pair has positive probability.
- Return type:
np.ndarray
- support_singular_values(dist, rvs=None, crvs=None)[source]
The singular values of the support graph’s biadjacency matrix.
- Parameters:
dist (Distribution) – The distribution of interest.
rvs (list of lists, None) – The two variables. If None, all variables of dist are used.
crvs (list, None) – Variables to condition on.
- Returns:
sigmas – The singular values, in decreasing order.
- Return type:
np.ndarray
Examples
The Fano plane’s point-line incidence graph is biregular of degree three, so its top singular value is three:
>>> import numpy as np >>> from dit import Distribution >>> lines = ['012', '034', '056', '136', '145', '235', '246'] >>> outcomes = [(str(p), str(i)) for i, line in enumerate(lines) for p in line] >>> fano = Distribution(outcomes, [1 / 21] * 21) >>> float(np.round(support_singular_values(fano)[0], 10)) 3.0
- symmetric_smooth(dist, eps)[source]
Symmetric full-support smoothing \(P_\varepsilon = (1-\varepsilon)P + \varepsilon U\).
Here \(U\) is uniform on the Cartesian product of the alphabets. This preserves permutation symmetries of
dist(e.g. W).- Parameters:
dist (Distribution)
eps (float) – Mixture weight on the uniform. Must satisfy
0 <= eps < 1.eps=0returns a dense copy ofdist(still sparse ifdistis).
- Returns:
smoothed – Dense linear distribution on the Cartesian sample space.
- Return type:
- variance(dist)[source]
Compute the variance Var(X) = E[(X - mu)^2].
- Parameters:
dist (Distribution)
- Returns:
var – The variance of each index of the outcomes.
- Return type:
ndarray