Channels¶

qif.channel

A channel \(C\) from \(\mathcal X = \{0,\ldots,n{-}1\}\) to \(\mathcal Y = \{0,\ldots,m{-}1\}\) is an \(n\times m\) numpy matrix with \(C_{x,y} = p(y|x)\): each row \(C_{x,-}\) is the distribution on observations \(y\) produced by the secret \(x\). Elements are double or rat, as for distributions.

For a prior \(\pi\), the joint matrix \(J = \pi\triangleright C\) is given by \(J_{x,y} = \pi_x C_{x,y}\); its column sums give the probability \(p(y)\) of each observation, and normalizing a column \(y\) with \(p(y)>0\) gives the posterior distribution \(p_{X|y}\).

Channel composition

Functions¶

normalize(C: ndarray) → ndarray¶: Returns C with each row divided by its sum, so that every row becomes a distribution.

identity(n_rows: int, type: TypeLike = def_type) → ndarray¶: The identity channel on n_rows secrets (the identity matrix), which reveals the secret completely.

no_interference(n_rows: int, n_cols: int = 1, type: TypeLike = def_type) → ndarray¶: A channel that leaks nothing: every row is the point distribution on observation \(0\) (the remaining n_cols\({-}1\) columns are zero).

randu(n_rows: int, n_cols: int = 0, type: TypeLike = def_type) → ndarray¶: A channel with each row chosen uniformly at random from the distributions on n_cols observations (n_cols = 0 means n_cols = n_rows).

deterministic(map: Callable[[int], int], n_rows: int, n_cols: int, type: TypeLike = def_type) → ndarray¶: The deterministic channel that maps each secret \(x\) to the observation map(x), that is \(C_{x,\mathrm{map}(x)} = 1\).

is_proper(C: ndarray, mrd: FloatOrRat = def_mrd) → bool¶: Whether C is a proper channel: every row is a distribution (non-negative, summing to \(1\) up to mrd).

assert_proper(C: ndarray) → None¶: Raises RuntimeError if C is not a proper channel (see is_proper()).

posterior(C: ndarray, pi: ndarray, col: int) → ndarray¶: The posterior distribution \(p_{X|y}\) on secrets after observing \(y\) = col, under prior pi. Requires \(p(y) > 0\).

posteriors(C: ndarray, pi: ndarray = array([])) → ndarray¶: All posterior distributions: a matrix of the same size as C whose column \(y\) is \(p_{X|y}\) (undefined for columns with \(p(y) = 0\)). If pi is not given the uniform prior is used.

hyper(C: ndarray, pi: ndarray) → Tuple[ndarray, ndarray]¶: The hyper-distribution \([\pi\triangleright C]\), as a pair (outer, inners): inners has one column per inner distribution, and outer[i] is the probability of inner i. Observations producing the same posterior are merged into a single inner.

reduced(C: ndarray) → ndarray¶: The reduced form of C: zero columns are removed and similar columns (multiples of each other) are merged. Two channels produce the same hyper on every prior iff their reduced forms are equal (up to the order of columns).

iterative_bayesian_update(C: ndarray, out: ndarray, start: ndarray = array([]), max_diff: FloatOrRat = 1e-06, max_iter: int = 0) → Tuple[ndarray, int]¶: Estimates the prior from an observed output distribution out, using the iterative Bayesian update (an instance of expectation–maximization). Starts from start (uniform if not given) and stops when the \(\ell_1\) distance between consecutive estimates is at most max_diff, or after max_iter iterations (0 means no limit). Returns (pi, iterations).

factorize(A: ndarray, B: ndarray, col_stoch: bool = False) → ndarray¶: Returns a channel \(X\) such that \(A = BX\), or an empty matrix if none exists. If col_stoch is true, \(X\) is required to be column-stochastic instead. Solved by linear programming (or a subgradient method for large double matrices).

left_factorize(A: ndarray, B: ndarray, col_stoch: bool = False) → ndarray¶: Returns a channel \(X\) such that \(A = XB\), or an empty matrix if none exists (see factorize()).

sum_column_min(C: ndarray) → FloatOrRat¶: The sum of the column minima \(\sum_y \min_x C_{x,y}\).

sample(C: ndarray, pi: ndarray) → Tuple[int, int]¶
sample(C: ndarray, pi: ndarray, n_samples: int) → ndarray: Draws a secret \(x\) from pi and then an observation \(y\) from \(C_{x,-}\). Returns the pair (x, y), or an n_samples\(\times 2\) array of independent samples.