* [36] I. Hasuo, “Generic weakest precondition semantics from monads enriched with order,” in _Proc. CMCS_ , ser. LNCS, M. Bonsangue, Ed., vol. 8446\. Springer, 2014, pp. 10–32.
  * [37] D. Kifer and B.-R. Lin, “Towards an axiomatization of statistical privacy and utility,” 2010, Penn State Technical report: CSE-10-002.
  * [38] M. Erwig and S. Kollmansberger, “Probabilistic functional programming in Haskell,” _Journal of Functional Programming_ , vol. 16, pp. 21–34, 2006\.
  * [39] D. Blackwell, “The comparison of experiments,” in _Proc. 2nd Berkely Symp. Mathematical Statistics and Probability_. Univ. Califormia Press, 1951, pp. 93–102.
  * [40] M. Bačák and J. M. Browein, “On difference convexity of locally Lipschitz functions,” _Optimization: A Journal of Math Prog and Oper Research_ , vol. 60, no. 8-9, pp. 961–978, 2011.
  * [41] L. H. Loomis and S. Sternberg, _Advanced Calculus_. Jones and Bartlett Publishers, 1990.

##  Appendix A Summary of notations

These entries list in first-use order the points at which notation is
introduced during the exposition: a detailed explanation of each is given
there.

| $-^{\dagger}$ |  Kleisli extension p.1
---|---|---
|  $f.x$ vs. $f(x)$ |  Function application is “.”, i.e. a dot. p.1.3
| ${\cal X}{\mathbin{\rightarrowtriangle}}{\cal Y}$ |  Type of a matrix. p.1.3
|  $C_{x,y},C_{-,y}$ etc. |  Elements of vectors and matrixes by index; whole rows/columns. p.1.3
| $\stackrel{{\scriptstyle\raisebox{-1.5pt}[0.0pt][0.0pt]{$\rightarrowtriangle$}}}{{{\cal X}}}$ |  Type of vector. p.1.3
| $(\mathbin{\cdot})$ |  Matrix multiplication: vectors automatically taken as row- or column- for conformity. p.1.3
|  $(:)$ vs. $(\in)$ |  Declaration vs. property. p.1.3
| u.c. Roman letter |  Matrices: $C$ for channels; $M$ for transformers; $H$ for HMM’s p.2.1
| ${\cal X}$ |  Finite set of states. p.2.1
| ${\cal Y}$ |  Finite set of observations. p.2.1
| l.c. Greek letter |  Vectors, usually distributions over ${\cal X}$: $\pi$ for priors; $\rho$ for posteriors; $\delta$ for others. p.2.1
| $\textrm{$\footnotesize\Sigma$}()$ |  Weight (sum of elements) of vector or matrix. p.1
| $\pi{\rhd}C$ |  Channel applied to prior. p.2
| $\lfloor-\rfloor$ |  Normalisation of distribution. p.3
| _similar_ |  wrt. columns of joint matrix. p.2.3
|  $y_{1,2}$ vs. $y_{1},y_{2}$ |  Former abbreviates latter. p.4
| ${\mathbb{D}}$ |  Discrete-distribution type constructor, a functor. p.2.3
| ${\mathbb{D}}^{2}$ |  Distribution-of-distributions. p.2.3
| hyper |  Abbreviation of “hyper-distribution”. p.2.3
| inner |  Element of a hyper’s base type. p.2.3
| outer |  Distribution of a hyper over its inners. p.2.3
| $[\\![\cdot]\\!]$ |  Semantic function for HMM’s. p.2.4
| $\underline{{\mathbb{D}}}$ |  Sub-distribution. p.4
| $\underline{{\mathbb{D}}^{2}}$ |  Sub-hyper. p.4
| $x{\mathbin{{}_{p}\kern-0.45003pt\oplus}}x^{\prime}$ |  The two-point distribution “$x$ with probability $p$ and $x^{\prime}$ with probability $1{-}p$”. p.5
| $[\cdot]$ |  Point distribution. p.5
| $\underline{[-]}$ |  Sub-point distribution. p.6
| $\lceil\delta\rceil$ |  The support of a distribution. p.9
| ${\sf avg}$ |  Average (of hyper); multiply in monad. p.10
| $\Delta$ |  Upper-case Greek for hypers. p.10
| channel |  The emission part of an HMM-step. p.1
| markov |  The transition part of an HMM-step. p.1
| $(C{;}M),(C{;}),({;}M)$ |  One-step HMM defined by channel and markov. p.11
| ${\sf nc}$ |  Channel that releases no information. p.3.3
| ${\sf id}$ |  Identity (Markov) transform. p.3.4
| @ |  Notation for specific hyper-distributions p.2
| $({;})$ |  Sequential composition of HMM’s. p.4.1
| $(\cdot{\parallel}\cdot)$ |  Parallel composition of channels. p.4.1.2
| ${\mathbb{D}}f$ |  Push-forward of $f$. p.13
| $(\ref{)}$ |  Refinement relation between hypers. p.17
| $\underline{\Delta}$ |  A distribution of hypers. p.17
| ${\cal E}_{\delta}\,f$ |  Expected value. p.19
| $\Pi,\mu,\eta$ |  Giry/Lawvere functor etc. p.7
| $\cal B$ |  Metric-monad functor. p.7
| $d_{K}$ |  Kantorovich metric. p.7
| $d_{1}$ |  Discrete metric. p.7
| $({\mathbin{{}_{p}\kern-0.45003pt+}})$ |  Weighted sum of distributions. p.22
| ${\mathbb{H}}{\cal X}$ |  Abstract HMM’s on ${\cal X}$. p.24
|  ${\mathbb{U}}{\cal X}$, UM’s |  Uncertainty measures on ${\cal X}$. p.26
| $\textrm{wp}.h$ |  Uncertainty transformer (determined by $h$.) p.28
| ${\mathbb{T}}$ |  The type of uncertainty transformers p.31
| $\mathbf{1}$ |  The everywhere-one function. p.3
| $U_{l}$ |  Uncertainty measure defined by loss-function $l$. p.35
| $H_{{\times}\kern-1.25998pt{\cal Z}}$ |  Dalenius $\cal Z$-extension (of HMM $H$). p.12
| $(\mathbin{\circ})$ |  Functional composition. p.B.1
| ${\mathbb{C}}{\cal X}$ |  Continuous functions from ${\mathbb{D}}{\cal X}$ to ${\mathbb{R}}$. p.38
| $\|\cdot{-}\cdot\|_{\infty}$ |  Uniform metric on ${\mathbb{U}}{\cal X}$ and ${\mathbb{C}}{\cal X}$. p.38
| $(\lambda\cdots)$ |  Lambda abstraction. p.42
| $l{\lhd}\pi$ |  $\pi$-skewed loss function. p.45

##  Appendix B Characterisation of pure channels and pure markovs [§4.1]

###  B.1. Pure abstract markovs

Since a pure markov reveals nothing, a pure abstract markov
$h{{:}\,}{\mathbb{H}}{\cal X}$ should produce only point hypers, i.e. have for
all $\pi{{:}\,}{\mathbb{D}}{\cal X}$ that $h.\pi=[\rho]$ for some $\rho$
(depending on $\pi$).

From that we can deduce that for any pure abstract markov $h$ the effect of
${\sf avg}\mathbin{\circ}h$ (on some $\pi$) is matrix multiplication by some
$M$ (independent of $\pi$). That is, for any $0{\leq}p{\leq}1$ we have

$({\sf
avg}\mathbin{\circ}h).(\pi_{1}{\mathbin{{}_{p}\kern-0.50003pt+}}\pi_{2})\hskip
10.00002pt=\hskip 10.00002pt({\sf
avg}\mathbin{\circ}h).\pi_{1}\,{\mathbin{{}_{p}\kern-0.50003pt+}}\,({\sf
avg}\mathbin{\circ}h).\pi_{2}~{},$ (11)

which property characterises matrix multiplication. This is because
$h.(\pi_{1}{\mathbin{{}_{p}\kern-0.50003pt+}}\pi_{2}){=}[\rho]$ and
$h.\pi_{1,2}{=}[\rho_{1,2}]$ resp. for some $\rho,\rho_{1,2}$, together with
Lem. 23, gives

$[\rho_{1}]{\mathbin{{}_{p}\kern-0.50003pt+}}[\rho_{2}]\hskip
10.00002pt\ref{}{1em}[\rho]~{},$

and the only way that can hold is if
$\rho=\rho_{1}{\mathbin{{}_{p}\kern-0.50003pt+}}\rho_{2}$, which is precisely
the claim made at (11) just above.

###  B.2. Pure abstract channels

A pure channel is one that releases information about the distribution on
${\cal X}$ but does not change it: one can think of the transformation part as
the identity matrix. Thus (11) above suggests that we should have that ${\sf
avg}\mathbin{\circ}h$ is the identity for a pure channel, i.e. that ${\sf
avg}.(h.\pi){=}\pi$. This is necessary, but turns out not to be sufficient: we
explore a fuller characterisation of channels later (§J).

##  Appendix C Equivalent presentations of refinement: Lem. 18 [§6]

Lem. 18 concerned two definitions of uncertainty refinement, showing them to
be equivalent: one was formulated for joint distributions (defined at (6)
within the lemma), suitable for discrete reasoning; and the other was
formulated for hypers (Def. 17), suitable for extension to more general
reasoning (e.g. proper measures). We sketch the proof of that equivalence in
§D immediately below.

In this section however we present an example, two hypers $\Delta_{S,I}$ shown
to satisfy $\Delta_{S}{\ref{}}\Delta_{I}$ in both presentations (Def. 17, Lem.
18), with an explanation of how to move from one presentation to the other.

As in (2) of §3.4, we use the following notation for discrete distributions
where specific values in the support are named: we write

$\begin{array}[]{l@{\,}l@{\,}l}x_{1}&@&p_{1}\\\ x_{2}&@&p_{2}\\\
\lx@intercol\textit{etc...}\hfil\lx@intercol\end{array}$ (12)

If these are laid out horizontally, we enclose them in double set-brackets
$\\{\\!\\{\cdots\\}\\!\\}$ separated by commas: thus
$\\{\\!\\{H@\nicefrac{{2}}{{3}},T@\nicefrac{{1}}{{3}}\\}\\!\\}$ describes a
coin twice as likely to give heads as tails. If the double brackets are used
without probabilities (and thus also without $@$’s) then the intended
distribution is uniform, so that $\\{\\!\\{H,T\\}\\!\\}$ describes a fair
coin; a convenient special case of that is $\\{\\!\\{H\\}\\!\\}$ for the point
distribution on $H$, the coin that gives heads every time. 191919In the
semantic space we write $[x]$ for that: here we are syntactic.

Let ${\cal X}$ be the set $\\{H,T\\}$ of coin-flip results. We choose our two
hypers as follows, presenting them as at (12):

$\begin{array}[]{rcl}\Delta_{S}&=&\left[\begin{array}[]{l@{\hspace{1em}}l@{\,}l}H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T\hfil\hskip
10.00002pt&@&\nicefrac{{1}}{{2}}\\\
H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T\hfil\hskip
<EMAIL_ADDRESS>\Delta_{I}&=&\left[\begin{array}[]{l@{\hspace{1em}}l@{\,}l}H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T\hfil\hskip
10.00002pt&@&\nicefrac{{1}}{{3}}\\\
H{\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}T\hfil\hskip
10.00002pt&@&\nicefrac{{1}}{{3}}\\\
H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T\hfil\hskip
<EMAIL_ADDRESS>
The first hyper $\Delta_{S}$ represents choosing fairly between two biased
coins and having the chosen one secretly flipped: we know which coin was
flipped, but we are not allowed to see the outcome of the flip. In
$\Delta_{I}$ however we choose fairly between _three_ coins: the two biased
coins from before, and a fair one. Again the chosen one is secretly flipped;
again we are not allowed to see the outcome.

We argue that in any reasonable measure of secrecy, it should in the second
case $\Delta_{I}$ be harder to guess which of $H,T$ resulted from the flip
than in the first case $\Delta_{S}$. And it is precisely that non-specific “in
_any_ reasonable measure” that uncertainty refinement
$\Delta_{S}{\ref{}}\Delta_{I}$ attempts to capture. 202020Furthermore, the
powerful “Coriaceous” completeness property (Lem. 27) shows the dual result:
if some $\Delta_{S},\Delta_{I}$ are _not_ in the refinement relation, that is
$\Delta_{S}{\mathrel{\not\sqsubseteq}}\Delta_{I}$, then there is _guaranteed_
to be a uncertainty measure wrt. to which $\Delta_{I}$ is _not_ more secure
than $\Delta_{S}$.

In this case, and informally speaking, $\Delta_{I}$ is more secure than
$\Delta_{S}$ because there is now a third possible case that acts as a linear
combination of the existing two. That is, some of the separation between the
inners $H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T$ and
$H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T$ in the support
of $\Delta_{S}$ has been merged together to become a single inner
$H{\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}T$ in the support
of $\Delta_{I}$ — and what makes the observer more uncertain is that he
doesn’t know how to pull that single inner apart again.

Two (reduced) joint matrices $J_{S,I}$ that give $\Delta_{S,I}$ resp. are

$\begin{array}[]{rcl}J_{S}&=&\begin{array}[]{r@{\hspace{2em}}cc}\hskip
20.00003pt&a&b\\\\[1.99997pt] H{:}\hskip
20.00003pt&\makebox[0.0pt]{\raisebox{-5.0pt}[0.0pt][0.0pt]{$\left(\rule{0.0pt}{15.00002pt}\right.\hskip
6.99997pt$}}\nicefrac{{1}}{{3}}&\nicefrac{{1}}{{6}}\makebox[0.0pt]{\raisebox{-5.09995pt}[0.0pt][0.0pt]{$\hskip
8.99994pt\left.\rule{0.0pt}{15.00002pt}\right)$}}\\\ T{:}\hskip
20.00003pt&\nicefrac{{1}}{{6}}&\nicefrac{{1}}{{3}}\end{array}\\\\[17.22217pt]
J_{I}&=&\begin{array}[]{r@{\hspace{2em}}ccc}\hskip
20.00003pt&c&d&e\\\\[1.99997pt] H{:}\hskip
20.00003pt&\makebox[0.0pt]{\raisebox{-5.0pt}[0.0pt][0.0pt]{$\left(\rule{0.0pt}{15.00002pt}\right.\hskip
6.99997pt$}}\nicefrac{{2}}{{9}}&\nicefrac{{1}}{{6}}&\nicefrac{{1}}{{6}}\makebox[0.0pt]{\raisebox{-5.09995pt}[0.0pt][0.0pt]{$\hskip
8.99994pt\left.\rule{0.0pt}{15.00002pt}\right)$}}\\\ T{:}\hskip
20.00003pt&\nicefrac{{1}}{{9}}&\nicefrac{{1}}{{6}}&\nicefrac{{2}}{{9}}\end{array}\end{array}$

where the observation spaces are ${\cal Y}_{S}{=}\\{a,b\\}$ and ${\cal
Y}_{I}{=}\\{c,d,e\\}$ respectively. (the column names are arbitrary.) Now the
refinement matrix that establishes (according to Lem. 18) that
$\Delta_{S}{\ref{}}\Delta_{I}$ is $R{{:}\,}{\cal
Y}_{S}{\mathbin{\rightarrowtriangle}}{\cal Y}_{I}$ given by

$\begin{array}[]{rcl}R&=&\begin{array}[]{r@{\hspace{2em}}ccc}\hskip
20.00003pt&c&d&e\\\\[1.99997pt] a{:}\hskip
20.00003pt&\makebox[0.0pt]{\raisebox{-5.0pt}[0.0pt][0.0pt]{$\left(\rule{0.0pt}{15.00002pt}\right.\hskip
6.99997pt$}}\nicefrac{{2}}{{3}}&\nicefrac{{1}}{{3}}&0\makebox[0.0pt]{\raisebox{-5.09995pt}[0.0pt][0.0pt]{$\hskip
15.00002pt\left.\rule{0.0pt}{15.00002pt}\right)$}}\\\ b{:}\hskip
20.00003pt&0&\nicefrac{{1}}{{3}}&\nicefrac{{2}}{{3}}\end{array}\end{array}$

which, read columnwise, says in its column $c$ that to make Column $c$ of
$J_{I}$ you take $\nicefrac{{2}}{{3}}$ of Column $a$ of $J_{S}$ and none of
Column $b$ of $J_{S}$. The middle column $d$ of $R$ is where the actual
refinement lies, that Column $d$ of $J_{I}$ is made by adding
$\nicefrac{{1}}{{6}}$ of each of Columns $a,b$ of $J_{S}$ together. This is
where $J_{I}$ (equiv. $\Delta_{I}$) reveals less than $J_{S}$ (equiv.
$\Delta_{S}$) does about the distribution on ${\cal X}{=}\\{H,T\\}$. And, as
the lemma suggests, we indeed have $J_{S}{\mathbin{\cdot}}R=J_{I}$.

The alternative, more abstract presentation of this is in terms of Def. 17,
i.e. where the $\underline{\Delta}$ we are looking for, that establishes
$\Delta_{S}{\ref{}}\Delta_{I}$ at the hyper-level directly, can be given as
(the denotation of) a joint distribution $J{{:}\,}{\mathbb{D}}{\cal
X}{\mathbin{\rightarrowtriangle}}{\cal Y}_{I}$ itself: we will have
$\underline{\Delta}{:=}\,[\\![J]\\!]$ which, because $J$’s source type is
${\mathbb{D}}{\cal X}$, will have type ${\mathbb{D}}^{2}({\mathbb{D}}{\cal
X})={\mathbb{D}}^{3}{\cal X}$ as we expect from $[\\![\cdot]\\!]$. The rows of
$J$ will be labelled by the support of $\Delta_{S}$, i.e. it will have only
two rows so that we have

$\begin{array}[]{rcl}J&=&\begin{array}[]{r@{\hspace{2em}}ccc}\hskip
20.00003pt&c&d&e\\\\[1.99997pt]
H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T:\hskip
20.00003pt&\makebox[0.0pt]{\raisebox{-5.0pt}[0.0pt][0.0pt]{$\left(\rule{0.0pt}{15.00002pt}\right.\hskip
6.99997pt$}}\nicefrac{{1}}{{3}}&\nicefrac{{1}}{{6}}&0\makebox[0.0pt]{\raisebox{-5.09995pt}[0.0pt][0.0pt]{$\hskip
15.00002pt\left.\rule{0.0pt}{15.00002pt}\right)$}}\\\
H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T:\hskip
20.00003pt&0&\nicefrac{{1}}{{6}}&\nicefrac{{1}}{{3}}\end{array}~{}.\end{array}$
(13)

If on the other hand we were to write $\underline{\Delta}{=}[\\![J]\\!]$ as a
hyper directly (performing the various normalisations etc.) we would have

$\begin{array}[]{rcl}\underline{\Delta}&=&\left[\begin{array}[]{l@{\hspace{1em}}l@{\,}l}[~{}H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T~{}]\hfil\hskip
10.00002pt&@&\nicefrac{{1}}{{3}}\\\
(H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T){\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}(H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T)\hfil\hskip
10.00002pt&@&\nicefrac{{1}}{{3}}\\\
[~{}H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T~{}]\hfil\hskip
10.00002pt&@&\nicefrac{{1}}{{3}}\end{array}\right]\end{array}~{},$

with each inner here corresponding to a row of (13).

Now ${\sf avg}.\underline{\Delta}$ is given by the calculation

|
<EMAIL_ADDRESS>+&(H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T){\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}(H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T){\times}\nicefrac{{1}}{{3}}\\\
+&[~{}H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T~{}]{\times}\nicefrac{{1}}{{3}}\end{array}$
---|---
$=$ |  $\begin{array}[t]{@{}llll}H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T){\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}(H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T)\end{array}$
$=$ |<EMAIL_ADDRESS>

This can also be seen (indeed is easier to see) if we simply take the left-
marginal of $J$, for which you add the columns together: you get

$\begin{array}[]{rcl}\begin{array}[]{r@{\hspace{2em}}c}\hskip
20.00003pt&c{+}d{+}e\\\ \hskip 20.00003pt&=1\\\\[6.00006pt]
H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T:\hskip
20.00003pt&\makebox[0.0pt]{\raisebox{-5.0pt}[0.0pt][0.0pt]{$\left(\rule{0.0pt}{15.00002pt}\right.\hskip
6.99997pt$}}\nicefrac{{1}}{{2}}\makebox[0.0pt]{\raisebox{-5.09995pt}[0.0pt][0.0pt]{$\hskip
15.00002pt\left.\rule{0.0pt}{15.00002pt}\right)$}}\\\
H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T:\hskip
20.00003pt&\nicefrac{{1}}{{2}}\end{array}\end{array}~{},$

which is again $\Delta_{S}$.

For the other direction we obtain $({\mathbb{D}}{\sf avg}).\underline{\Delta}$
by ${\sf avg}$’ing each inner of $\underline{\Delta}$ while preserving the
(outer) probabilities. 212121Recall that the inners of $\underline{\Delta}$
are themselves hypers, which is why they can be ${\sf avg}$’d. That gives

$({\mathbb{D}}{\sf avg}).\underline{\Delta}\hskip 10.00002pt=\hskip
10.00002pt\left[\begin{array}[]{l@{\hspace{1em}}l@{\,}l}H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T\hfil\hskip
10.00002pt&@&\nicefrac{{1}}{{3}}\\\
H{\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}T\hfil\hskip
10.00002pt&@&\nicefrac{{1}}{{3}}\\\
H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T\hfil\hskip
10.00002pt&@&\nicefrac{{1}}{{3}}\end{array}\right]~{},$

because

$\displaystyle{\sf
avg}.[~{}H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T~{}]$
$\displaystyle=$ $\displaystyle
H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T$
$\displaystyle{\sf
avg}.(H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T){\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}(H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T)$
$\displaystyle=$ $\displaystyle
H{\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}T$
$\displaystyle{\sf
avg}.[~{}H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T~{}]$
$\displaystyle=$ $\displaystyle
H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T$

And so that the remaining question is “How do we get such a
$\underline{\Delta}$ from a given $R$? ”

Remember that the support of $\Delta_{S}$ is
$\\{H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T,H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T\\}$.
Make a distribution $\pi_{S}$ by mapping those (inner) distributions of
$\Delta_{S}$ onto the labels in ${\cal Y}_{S}$ associated uniquely with them
in $J_{S}$. (The association is unique because $J_{S}$ is reduced.) That gives
us that $\pi_{S}$ is of type ${\mathbb{D}}{\cal Y}_{S}$ and has value
$a{\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}b$.

Now form the joint-distribution matrix $\pi_{S}{\rhd}R$, i.e.

$\begin{array}[]{rcc}a{:}&\makebox[0.0pt]{\raisebox{-5.0pt}[0.0pt][0.0pt]{$\left(\rule{0.0pt}{15.00002pt}\right.\hskip
6.99997pt$}}\nicefrac{{1}}{{2}}\makebox[0.0pt]{\raisebox{-5.09995pt}[0.0pt][0.0pt]{$\hskip
15.00002pt\left.\rule{0.0pt}{15.00002pt}\right)$}}\\\
b{:}&\nicefrac{{1}}{{2}}\end{array}\hskip 10.00002pt{\rhd}\hskip
6.99997pt\raisebox{6.00006pt}{$\begin{array}[]{ccc}c&d&e\\\\[3.00003pt]
\makebox[0.0pt]{\raisebox{-5.0pt}[0.0pt][0.0pt]{$\left(\rule{0.0pt}{15.00002pt}\right.\hskip
6.99997pt$}}\nicefrac{{2}}{{3}}&\nicefrac{{2}}{{3}}&0\makebox[0.0pt]{\raisebox{-5.09995pt}[0.0pt][0.0pt]{$\hskip
15.00002pt\left.\rule{0.0pt}{15.00002pt}\right)$}}\\\
0&\nicefrac{{1}}{{3}}&\nicefrac{{2}}{{3}}\end{array}$}\hskip
6.99997pt=\raisebox{6.00006pt}{$\begin{array}[]{rccc}&c&d&e\\\\[1.99997pt]
a{:}&\makebox[0.0pt]{\raisebox{-5.0pt}[0.0pt][0.0pt]{$\left(\rule{0.0pt}{15.00002pt}\right.\hskip
6.99997pt$}}\nicefrac{{1}}{{3}}&\nicefrac{{1}}{{6}}&0\makebox[0.0pt]{\raisebox{-5.09995pt}[0.0pt][0.0pt]{$\hskip
15.00002pt\left.\rule{0.0pt}{15.00002pt}\right)$}}\\\
b{:}&0&\nicefrac{{1}}{{6}}&\nicefrac{{1}}{{3}}\end{array}$}$

which (like $R$ itself) is of type ${\cal
Y}_{S}{\mathbin{\rightarrowtriangle}}{\cal Y}_{I}$. (But note that $R$ is a
channel matrix, whereas $\pi_{S}{\rhd}R$ is a joint-distribution matrix.)

Now use the relabelling in the reverse direction on the rows of the joint
distribution above (as “new row-labels” at right above) to get a matrix with
the same contents but now of type ${\mathbb{D}}{\cal
X}{\mathbin{\rightarrowtriangle}}{\cal Y}_{I}$. It is

$\begin{array}[]{r@{\hspace{2em}}ccc}\hskip 20.00003pt&c&d&e\\\\[1.99997pt]
H{\mathbin{{}_{\nicefrac{{2}}{{3}}}\kern-0.50003pt\oplus}}T:\hskip
20.00003pt&\makebox[0.0pt]{\raisebox{-5.0pt}[0.0pt][0.0pt]{$\left(\rule{0.0pt}{15.00002pt}\right.\hskip
6.99997pt$}}\nicefrac{{1}}{{3}}&\nicefrac{{1}}{{6}}&0\makebox[0.0pt]{\raisebox{-5.09995pt}[0.0pt][0.0pt]{$\hskip
15.00002pt\left.\rule{0.0pt}{15.00002pt}\right)$}}\\\
H{\mathbin{{}_{\nicefrac{{1}}{{3}}}\kern-0.50003pt\oplus}}T:\hskip
20.00003pt&0&\nicefrac{{1}}{{6}}&\nicefrac{{1}}{{3}}\end{array}$

which is exactly the $J$ we had at (13) above, and as above we get
$\underline{\Delta}$ via $\underline{\Delta}{=}[\\![J]\\!]$.

Thus in this example we have illustrated how one might move between the two
equivalent definitions of refinement. Each one has a witness: in the hyper-
formulation it is the distribution on hypers $\underline{\Delta}$; and in the
matrix formulation is is a post-processing “refinement matrix” $R$. The sketch
proof (§D) shows how to obtain each from the other in general.

##  Appendix D Monadic vs. matrix presentations of refinement [§6]

In §C we gave an example of the two equivalent presentations of refinement;
here we give a proof (sketch) that it can always be done.

Lemma 18: Refinement of joint-distribution matrices Let $J_{S}{{:}\,}{\cal
X}^{\prime}{\mathbin{\rightarrowtriangle}}{\cal Y}_{S}$ and $J_{I}{{:}\,}{\cal
X}^{\prime}{\mathbin{\rightarrowtriangle}}{\cal Y}_{I}$ be joint-distribution
matrices, both of them _reduced_ in the sense of Def. 7, such that
$[\\![J_{S,I}]\\!]{=}\Delta_{S,I}$ resp. In this section only we use ${\cal
X}^{\prime}$ as a reminder that the _input_ side of these $J$’s, their row-
indices, is actually the _output_ side of the HMM’s from which they are
derived, i.e. that $J_{x^{\prime},y}=\sum_{x}H_{x,y,x^{\prime}}$ as in Def.
12.

We prove the equivalence

$\Delta_{S}\ref{\Delta}_{I}\hskip 10.00002pt\textrm{iff}\hskip
10.00002ptJ_{S}\mathbin{\cdot}R=J_{I}\textrm{\quad for some $R$}$

where $R$ is a stochastic _refinement matrix_ of type ${\cal
Y}_{S}{\mathbin{\rightarrowtriangle}}{\cal Y}_{I}$ (i.e. such that $\sum
R_{y,-}=1$ for each $y{{:}\,}{\cal Y}_{S}$).

Proof. First we note that for any reduced joint distribution matrix
$J{{:}\,}{\cal Z}{\mathbin{\rightarrowtriangle}}{\cal Z}^{\prime}$ there is a
one-one correspondence between $J$’s column labels, i.e. elements of ${\cal
Z}^{\prime}$, and the support of the hyper $\Delta{=}[\\![J]\\!]$ that $J$
defines: it is the function $j{{:}\,}{\cal
Z}^{\prime}\stackrel{{\scriptstyle\mbox{\rm\scriptsize
1-1}}}{{\longleftrightarrow}}\lceil\Delta\rceil$ from Def. 7, injective into
${\mathbb{D}}{\cal Z}$ because $J$ is reduced. We write
$(\stackrel{{\scriptstyle\mbox{\rm\scriptsize 1-1}}}{{\longleftrightarrow}})$
to emphasise our one-one use of it below.

$R$ makes $\underline{\Delta}$: We show first that for $J_{S,I},\Delta_{S,I}$
and $R$ as above we can construct a suitable $\underline{\Delta}$. Let the
relabelling associated with $J_{S}$ be
$j_{S}{{:}\,}Y_{S}\stackrel{{\scriptstyle\mbox{\rm\scriptsize
1-1}}}{{\longleftrightarrow}}\lceil\Delta_{S}\rceil$. Relabel $\Delta_{S}$ so
that it is a distribution of support ${\mathbb{D}}Y_{S}$, so that we can use
Def. 7 to define $\underline{\Delta}{:=}\,[\\![\Delta_{S}{\rhd}R]\\!]$, noting
that the types of (relabelled) $\Delta_{S}{\in}{\mathbb{D}}{\cal Y}_{S}$ and
of $R{\in}{\cal Y}_{S}{\mathbin{\rightarrowtriangle}}{\cal Y}_{I}$ are
precisely what Def. 7 requires to produce a result of type
${\mathbb{D}}^{2}{\cal Y}_{S}$. Now relabel this (back again) to make an
element of ${\mathbb{D}}^{2}\lceil\Delta_{S}\rceil$, that is of
${\mathbb{D}}^{3}{\cal X}$ because
$\lceil\Delta_{S}\rceil{\subseteq}{\mathbb{D}}{\cal X}$.

We have $\Delta_{S}{=}{\sf avg}.\underline{\Delta}$ immediately, from the
remark following Def. 8.

For $({\mathbb{D}}{\sf avg}).\underline{\Delta}{=}\Delta_{I}$ we first
calculate

|  $\begin{array}[t]{@{}llll}({\mathbb{D}}{\sf
avg}).[\\![\Delta_{S}{\rhd}R]\\!]\end{array}$
---|---
$=$ |  $\begin{array}[t]{@{}llll}[\\![M{\mathbin{\cdot}}(\Delta_{S}{\rhd}R)]\\!]~{},\\\ \quad\textrm{where $M_{x,\rho}{:=}\,\rho.x$ for $x{{:}\,}{\cal X}$ and $\rho{{:}\,}\lceil\Delta_{S}\rceil$.}\end{array}$ “Set ${\cal D}{:=}\,\lceil\Delta_{S}\rceil$ in Lem. 37 below”

Now for arbitrary $x{{:}\,}{\cal X}$ and $y_{I}{{:}\,}{\cal Y}_{I}$ we
continue

|
$\begin{array}[t]{@{}llll}(M{\mathbin{\cdot}}(\Delta_{S}{\rhd}R))_{x,y_{I}}\end{array}$
---|---
$=$ |  $\begin{array}[t]{@{}llll}\sum_{\rho{{:}\,}{\cal D}}M_{x,\rho}\,(\Delta_{S})_{\rho}\,R_{\rho,y_{I}}\end{array}$
$=$ |  $\begin{array}[t]{@{}llll}\sum_{\rho{{:}\,}\lceil\Delta_{S}\rceil}\rho.x\,(\Delta_{S})_{\rho}\,R_{\rho,y_{I}}\end{array}$ “Defn. $M$; ${\cal D}{=}\lceil\Delta_{S}\rceil$”
$=$ |  $\begin{array}[t]{@{}llll}\sum_{y_{S}{{:}\,}{\cal Y}_{S}}(J_{S})_{x,y_{S}}\,R_{\rho,y_{I}}\end{array}$ “$\lceil\Delta_{S}\rceil{=}{\cal Y}_{S}$; $\Delta_{S}{=}[\\![J_{S}]\\!]$”
$=$ |  $\begin{array}[t]{@{}llll}J_{I}~{},\end{array}$ “$J_{I}{=}J_{S}{\mathbin{\cdot}}R$”

whence $({\mathbb{D}}{\sf avg}).\underline{\Delta}=[\\![J_{I}]\\!]=\Delta_{I}$
as required.

$\underline{\Delta}$ makes $R$: To show that from $\underline{\Delta}$ we can
construct a suitable $R$, we do similar calculations to the above, but in the
reverse direction. $\Box$

######  Lemma 37.

Technical lemma Let ${\cal D}{\subseteq}{\mathbb{D}}{\cal X}$ be some finite
set of distributions on ${\cal X}$, and let $J{{:}\,}{\cal
D}{\mathbin{\rightarrowtriangle}}{\cal Y}$ be a joint-distribution matrix
between (those) _distributions_ on ${\cal X}$ and some observation space
${\cal Y}$. Then ${\mathbb{D}}{\sf
avg}.[\\![J]\\!]=[\\![M{\mathbin{\cdot}}J]\\!]$, where $M{{:}\,}{\cal
X}{\mathbin{\rightarrowtriangle}}{\cal D}$ is defined
$M_{x,\delta}{:=}\,\delta.x$ for $x{{:}\,}{\cal X}$ and $\delta{{:}\,}{\cal
D}$.

Proof. Let us match inners (and associated weight) of
$[\\![M{\mathbin{\cdot}}J]\\!]$ with that of ${\mathbb{D}}{\sf
avg}.[\\![J]\\!]$. These are finitely supported distributions so the following
sums are all finite.

Let $y{{:}\,}{\cal Y}$. On the one hand, the $y$-inner $\delta$ of
$[\\![M{\mathbin{\cdot}}J]\\!]$ satisfies, for every $x{{:}\,}{\cal X}$,

$\delta.x=\frac{(M\mathbin{\cdot}J)_{x,y}}{\sum_{x}(M\mathbin{\cdot}J)_{x,y}}=\frac{\sum_{\rho}M_{x,\rho}J_{\rho,y}}{\sum_{x}\sum_{\rho}M_{x,\rho}J_{\rho,y}}=\frac{\sum_{\rho}\rho.xJ_{\rho,y}}{\sum_{\rho}J_{\rho,y}}$

and this inner has weight $\sum_{\rho}J_{\rho,y}$.

On the other hand, the $y$-inner $\Delta$ of $[\\![J]\\!]$ satisfies, for
every $\rho$,

$\Delta.\rho=\frac{J_{\rho,y}}{\sum_{\rho}J_{\rho,y}}~{}.$

This inner has weight $\sum_{\rho}J_{\rho,y}$. Applying the ${\sf avg}$, we
get

${\sf
avg}.\Delta.x=\sum_{\rho}\rho.x\Delta.\rho=\frac{\sum_{\rho}\rho.xJ_{\rho,y}}{\sum_{\rho}J_{\rho,y}}$

Since ${\mathbb{D}}{\sf avg}$ simply distributes through the inners of
$[\\![J]\\!]$, we deduce that ${\mathbb{D}}{\sf avg}.[\\![J]\\!]$ has the
exact same inners as $[\\![M\mathbin{\cdot}J]\\!]$ with the exact same
weights. That is, the two discrete hyper-distributions are equal. $\Box$

##  Appendix E Properties of the refinement order $(\ref{)}$

###  E.1. Abstract HMM’s are $(\ref{)}$-monotonic

[§8.1]
Super-linearity (Lem. 23) is equivalently $(\ref{)}$-monotonicity of the
Kleisli-extension $h^{\dagger}$ of any $h{{:}\,}{\mathbb{H}}{\cal X}$; that
is, it is equivalent to the more general
$\Delta_{1}{\ref{}}\Delta_{2}\Rightarrow
h^{\dagger}.\Delta_{1}\ref{h}^{\dagger}.\Delta_{2}$. Assuming
$(\ref{)}$-monotonicity and recalling that $[\cdot]$ is the point
distribution, we have trivially the inequality
$[\pi_{1}]{\mathbin{{}_{p}\kern-0.50003pt+}}[\pi_{2}]\ref{[missing]}{\pi_{1}{\mathbin{{}_{p}\kern-0.50003pt+}}\pi_{2}}$
and so

|
$\begin{array}[t]{@{}llll}h.\pi_{1}\,{\mathbin{{}_{p}\kern-0.50003pt+}}\,h.\pi_{2}\end{array}$
---|---
$=$ |  $\begin{array}[t]{@{}llll}h^{\dagger}.[\pi_{1}]\,{\mathbin{{}_{p}\kern-0.50003pt+}}\,h^{\dagger}.[\pi_{2}]\end{array}$ “defn. $h^{\dagger}$”
$=$ |  $\begin{array}[t]{@{}llll}h^{\dagger}.([\pi_{1}]{\mathbin{{}_{p}\kern-0.50003pt+}}[\pi_{2}])\end{array}$ “$h^{\dagger}$ linear”
|
<EMAIL_ADDRESS>“$[\pi_{1}]{\mathbin{{}_{p}\kern-0.45003pt+}}[\pi_{1}]\ref{[missing]}{\pi_{1}{\mathbin{{}_{p}\kern-0.45003pt+}}\pi_{2}}$;
assumption that $h^{\dagger}$ is monotonic”
$=$ |  $\begin{array}[t]{@{}llll}h.(\pi_{1}{\mathbin{{}_{p}\kern-0.50003pt+}}\pi_{2})~{}.\end{array}$ “defn. $h^{\dagger}$”

For the other direction (sketch), in the discrete case we note that a proof of
$\Delta_{1}{\ref{}}\Delta_{2}$ can be broken down into a succession of column-
merges (in the matrix representation), each of them being of the form “replace
$[\pi_{1}]{\mathbin{{}_{p}\kern-0.50003pt+}}[\pi_{2}]$ by
$[\pi_{1}{\mathbin{{}_{p}\kern-0.50003pt+}}\pi_{2}]$”.

###  E.2. Composition of abstract HMM’s respects the refinement order

[§8.1] We show that sequential composition of abstract HMM’s respects the
refinement order $(\ref{)}$ on both sides, i.e. that for
$h,h_{1,2}{{:}\,}{\mathbb{H}}{\cal X}$ we have both

$\displaystyle h_{1}\ref{h}\hskip 10.00002pt\Rightarrow\hskip
10.00002pth_{1};h_{2}\ref{h};h_{2}$ (14) and $\displaystyle h_{2}\ref{h}\hskip
10.00002pt\Rightarrow\hskip 10.00002pth_{1};h_{2}\ref{h}_{1};h~{}.$ (15)

Although this can be argued directly in terms of abstract HMM’s, it is easier
if we use the UM’s defined later (§9). For (14) we have

|  $\begin{array}[t]{@{}llll}h_{1}\ref{h}\end{array}$
---|---
iff |<EMAIL_ADDRESS>“§E.3 just below”
implies |  $\begin{array}[t]{@{}llll}{}\\\ \textrm{wp}.h_{1}\mathbin{\circ}\textrm{wp}.h_{2}~{}\leq~{}\textrm{wp}.h\mathbin{\circ}\textrm{wp}.h_{2}\end{array}$
iff |  $\begin{array}[t]{@{}llll}\textrm{wp}.(h_{1};h_{2})\leq\textrm{wp}.(h_{1};h)\end{array}$ “Cor. 34 in §H”
iff |  $\begin{array}[t]{@{}llll}h_{1};h_{2}\ref{h}_{1};h~{}.\end{array}$ “§E.3”

And for (15) we have

|  $\begin{array}[t]{@{}llll}h_{2}\ref{h}\end{array}$
---|---
iff |<EMAIL_ADDRESS>“§E.3 just below”
implies |  $\begin{array}[t]{@{}llll}{}\\\ \textrm{wp}.h_{1}\mathbin{\circ}\textrm{wp}.h_{2}~{}\leq~{}\textrm{wp}.h_{1}\mathbin{\circ}\textrm{wp}.h\end{array}$ “$\textrm{wp}.h_{1}$ is $(\leq)$-monotonic, Lem. 30(2)”
iff |  $\begin{array}[t]{@{}llll}\textrm{wp}.(h_{1};h_{2})\leq\textrm{wp}.(h_{1};h)\end{array}$ “Cor. 34 in §H”
iff |  $\begin{array}[t]{@{}llll}h_{1};h_{2}\ref{h}_{1};h~{}.\end{array}$ “§E.3”

###  E.3. Refinement of transformers

[§9.4] Here we prove the correspondence between the forwards- and the
backwards manifestations of refinement $(\ref{)}$, i.e. that we have

$h_{1}\ref{h}_{2}\hskip 10.00002pt\textrm{iff}\hskip
10.00002pt\textrm{wp}.h_{1}\leq\textrm{wp}.h_{2}~{},$

where on the rhs we have extended $(\leq)$ pointwise, i.e. meaning
$\textrm{wp}.h_{1}.u.\pi\leq\textrm{wp}.h_{1}.u.\pi$ for all
$u{{:}\,}{\mathbb{U}}{\cal X}$ and $\pi{{:}\,}{\mathbb{D}}{\cal X}$. We reason

|  $\begin{array}[t]{@{}llll}h_{1}\ref{h}_{2}\end{array}$
---|---
iff |  $\begin{array}[t]{@{}ll}{}\\\ h_{1}.\pi\ref{h}_{2}.\pi\textrm{\quad for all $\pi{{:}\,}{\mathbb{D}}{\cal X}$}\end{array}$ “pointwise extension $(\ref{)}$”
iff |  $\begin{array}[t]{@{}ll}{}\\\ {\cal E}_{h_{1}.\pi}\,u\leq{\cal E}_{h_{2}.\pi}\,u\quad\begin{tabular}[t]{l}for all $\pi{{:}\,}{\mathbb{D}}{\cal X}$ and all $u{{:}\,}{\mathbb{U}}{\cal X}$\end{tabular}\end{array}$ “Lem. 27, soundness and completeness”
iff |  $\begin{array}[t]{@{}ll}{}\\\ \textrm{wp}.h_{1}.u.\pi\leq\textrm{wp}.h_{2}.u.\pi\quad\begin{tabular}[t]{l}for all $\pi{{:}\,}{\mathbb{D}}{\cal X}$\\\ and for all $u{{:}\,}{\mathbb{U}}{\cal X}$\end{tabular}\end{array}$ “defn. $\textrm{wp}.()$”
iff |<EMAIL_ADDRESS>“pointwise extension”

###  E.4. Composition respects transformer refinement

[§9.4] For $t_{1,2}{{:}\,}{\mathbb{U}}{\cal X}$ we have defined
$t_{1}{\ref{}}t_{2}$ to be simply that $t_{1}.u{\leq}t_{2}.u$ for all
$u{{:}\,}{\mathbb{U}}{\cal X}$. Here we show that functional composition of
transformers respects that refinement order $(\ref{)}$ on both sides, i.e.
that for $t,t_{1,2}{{:}\,}{\mathbb{T}}{\cal X}$ we have both
$t_{1}{\ref{}}t\Rightarrow
t_{1}{\mathbin{\circ}}t_{2}\ref{t}{\mathbin{\circ}}t_{2}$ and
$t_{2}\ref{t}\Rightarrow
t_{1}{\mathbin{\circ}}t_{2}\ref{t}_{1}{\mathbin{\circ}}t$.

In fact it is trivial from the property (imposed by ${\mathbb{T}}{\cal X}$)
that transformers are $(\leq)$-monotonic, that is Lem. 30(2).

###  E.5. Soundness and completeness: Lem. 27

[§9] We mention soundness and completeness in this paper because it provides
an important justification for our definition and use of the general
uncertainty measures and, in particular, their transformers.

The soundness part of Lem. 27 is related to the Data-Processing Inequality,
the DPI [13] , which concerns two channels $C{{:}\,}{\cal
X}{\mathbin{\rightarrowtriangle}}{\cal Y}$ and $R{{:}\,}{\cal
Y}{\mathbin{\rightarrowtriangle}}{\cal Z}$. (Note that the channel $R$ here
takes the _observations_ ${\cal Y}$ of Channel $C$ as its input. Our HMM’s do
not take observations as input.)

Informally stated, the _cascade_ of $C$ and $R$ is the channel given by the
matrix multiplication $C{\mathbin{\cdot}}R$, and the DPI states that the
information leakage from $C{\mathbin{\cdot}}R$ cannot be more than the leakage
from $C$ alone: adding another child to the game “Chinese Whispers” cannot
make the eventual output less ridiculous.

We call this _soundness_ because it states that a no-less-secure hyper wrt.
our uncertainty refinement order indeed cannot be less uncertain when tested
with _any_ uncertainty measure. This result is proved in in [6, 8].

The completeness part of Lem. 27 is related to the “Coriaceous Conjecture”
partially proved in [8], which became the Coriaceous Property (CP) in [6] when
its proof, for channels, was presented in complete form based on McIver’s
earlier, complete proof in [4] for hypers. 222222Geoffrey Smith has since told
us that it follows from a result of Blackwell [39]. In [6] terms, the CP is
that if there _is no_ $R$ such that $C_{1}{\mathbin{\cdot}}R{=}C_{2}$ then
there is a “gain function” (for us here, a loss function, which determines a
special form of uncertainty measure in our terms) that is witness to the non-
existence of such an $R$. The importance of the CP for quantitative
information-flow security was explained in [8], and it was proved there to
hold for many interesting special cases of $C_{1,2}$. But not for all of them.

The CP was proved to extend beyond the discrete case, to proper measure
spaces, in [5].

##  Appendix F Proof of Lem. 29 [§9.2]

This technical lemma assures the well definedness of our dual space: we have
defined our uncertainty measures ${\mathbb{U}}{\cal X}$ as functions in
${\mathbb{D}}{\cal X}{\mathbin{\rightarrow}}{\mathbb{R}}^{\geq}$ with certain
properties; and we have stated that $\textrm{wp}.h.u$ is also an uncertainty
measure. Thus we must show that $\textrm{wp}.h.u\in{\mathbb{D}}{\cal
X}{\mathbin{\rightarrow}}{\mathbb{R}}^{\geq}$ and that it satisfies the
properties for membership of ${\mathbb{U}}{\cal X}$.

Lemma 29: Well-definedness of Def. 28 If $h{{:}\,}{\mathbb{H}}{\cal X}$ is an
abstract HMM and $u{{:}\,}{\mathbb{U}}{\cal X}$ is a UM, then
$\textrm{wp}.h.u$ is in ${\mathbb{U}}{\cal X}$.

Proof. Since $h{\in}{\mathbb{H}}{\cal X}$, we have $h{{:}\,}{\mathbb{D}}{\cal
X}{\mathbin{\rightarrow}}{\mathbb{D}}^{2}{\cal X}$ satisfying Lems. 21,23. We
must show for any $u{{:}\,}{\mathbb{U}}{\cal X}$ and
$\delta{{:}\,}{\mathbb{D}}{\cal X}$ that $\delta{\mapsto}{\cal
E}_{h.\delta}\,u$ is in ${\mathbb{U}}{\cal X}$, i.e. that it is in
${\mathbb{D}}{\cal X}\mathbin{\rightarrow}{\mathbb{R}}^{\geq}$, is concave and
is continuous (Def. 26).

Membership of $\delta{\mapsto}{\cal E}_{h.\delta}\,u$ in ${\mathbb{D}}{\cal
X}\mathbin{\rightarrow}{\mathbb{R}}^{\geq}$ is trivial.

For concavity: Because $u{\in}{\mathbb{U}}{\cal X}$ we know it is itself
concave; and we have that $h$ satisfies the properties in Def. 24. We now
reason

|
$\begin{array}[t]{@{}llll}\textrm{wp}.h.u.(\pi_{1}~{}{\mathbin{{}_{p}\kern-0.50003pt+}}~{}\pi_{2})\end{array}$
---|---
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{h.(\pi_{1}{\mathbin{{}_{p}\kern-0.35002pt+}}\pi_{2})}\,u\end{array}$ “Def. 28”
$\geq$ |  $\begin{array}[t]{@{}ll}{}\\\ {}\\\ {\cal E}_{(h.\pi_{1}){\mathbin{{}_{p}\kern-0.35002pt+}}(h.\pi_{2})}\,u\end{array}$ “ Def. 24, hence $(h.\pi_{1}){\mathbin{{}_{p}\kern-0.45003pt+}}(h.\pi_{2})\ref{h}.(\pi_{1}{\mathbin{{}_{p}\kern-0.45003pt+}}\pi_{2})$ $u$ concave, hence Lem. 20 (non-strict) applies ”
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{h.\pi_{1}}\,u~{}~{}{\mathbin{{}_{p}\kern-0.50003pt+}}~{}~{}{\cal E}_{h.\pi_{2}}\,u\end{array}$ “${\cal E}\,$ is linear”
$=$ |  $\begin{array}[t]{@{}llll}\textrm{wp}.h.u.\pi_{1}~{}{\mathbin{{}_{p}\kern-0.50003pt+}}~{}\textrm{wp}.h.u.\pi_{2}~{},\end{array}$ “Def. 28”

as required.

For continuity: We must show that $\textrm{wp}.h.u$ is continuous, given that
both $u,h$ are themselves continuous. Because $h$ itself is continuous, we
need only show that in general the function $\Delta{\mapsto}{\cal
E}_{\Delta}\,u$ is continuous wrt. Kantorovich on the left, in $\Delta$ for
fixed continuous $u$. This follows from the fact that ${\mathbb{D}}{\cal X}$
is a compact metric space so that the Kantorovich metric metrizes the weak
topology on ${\mathbb{D}}^{2}{\cal X}$. That is, ${\cal E}_{\Delta_{n}}\,u$
converges to ${\cal E}_{\Delta}\,u$ for every continuous function
$u{{:}\,}{\mathbb{D}}{\cal X}{\to}{\mathbb{R}}^{\geq}$ iff $\Delta_{n}$
converges to $\Delta$ wrt. Kantorovich metric. $\Box$

##  Appendix G Extension of transformers [§9.4]

The core ingredient in the proof of this theorem is the Riesz Representation
Theorem for linear functionals (linear maps from a normed vector space to
${\mathbb{R}}$). A difficulty however originates from the fact that the
representation theorem is stated on the space of all continuous functions
${\mathbb{C}}{\cal X}$ (defined below), but our linear function $t$ is defined
only from the subspace ${\mathbb{U}}{\cal X}$ to itself.

######  Definition 38.

Space of continuous functions We define ${\mathbb{C}}{\cal X}$ to be the set
of all _continuous functions_ from ${\mathbb{D}}{\cal X}$ (with the
Kantorovich metric) to ${\mathbb{R}}$ (with the ordinary metric). This set is
endowed with the _uniform metric_ $\|\cdot{-}\cdot\|_{\infty}$, defined

$\|u_{1}{-}u_{2}\|_{\infty}\hskip 10.00002pt{:=}\,\hskip
10.00002pt\sup_{\delta{{:}\,}{\mathbb{D}}{\cal X}}|u_{1}.\delta-
u_{2}.\delta|~{},$ (16)

that turns ${\mathbb{C}}{\cal X}$ into a complete metric space. $\Box$

Yet ${\mathbb{U}}{\cal X}$ is a sub-metric space of ${\mathbb{C}}{\cal X}$
under the uniform metric $\|\cdot{-}\cdot\|_{\infty}$. More importantly, we
prove that the vector space generated by ${\mathbb{U}}{\cal X}$ is dense in
${\mathbb{C}}{\cal X}$. (See Lem. 39 and Fig. 7.) This is essential to ensure
that if $t$ extends to a continuous linear function over ${\mathbb{C}}{\cal
X}$, then such an extension is necessarily unique. We will show in Thm. 41
that such an extension always exists.

Every continuous piecewise-linear function can be expressed as the sum of
finitely many convex and concave functions using the construction shown in
this figure. This provides a geometrical view of the Concave Density Lem. 39.
By summing up concave and convex functions, we get non concave (resp. convex)
functions. In fact, the density theorem shows that any arbitrarily shaped
function can be approximated using finite sums and products of scaled concave
functions. Figure 7. The sum of convex (red, upper) and concave (blue, lower)
functions gives a zig-zag (black, middle).

######  Lemma 39.

Concave density The vector space generated by ${\mathbb{U}}{\cal X}$ is dense
in ${\mathbb{C}}{\cal X}$ wrt. $\|\cdot{-}\cdot\|_{\infty}$.

Proof. This result essentially follows from [40, Pro. 2.2]. We give the proof
here for completeness.

Let ${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ be the set of functions
that can be written as the difference of two positive concave functions from
${\mathbb{D}}{\cal X}$ to ${\mathbb{R}}$. Then ${\left\langle{\mathbb{U}}{\cal
X}\right\rangle}$ coincides with the real vector space generated by
${\mathbb{U}}{\cal X}$ (by grouping positively and negatively weighted
components). Equivalently, every function in ${\left\langle{\mathbb{U}}{\cal
X}\right\rangle}$ is the difference of two positive continuous convex
functions: if $f=u_{1}-u_{2}$ for $u_{1,2}{{:}\,}{\mathbb{U}}{\cal X}$, then

$f=(-u_{2}-c)-(-u_{1}-c)$

where $c=\min(\inf_{\delta{{:}\,}{\mathbb{D}}{\cal
X}}-u_{1}.\delta,\inf_{\delta{{:}\,}{\mathbb{D}}{\cal X}}-u_{2}.\delta)$. The
constant $c$ is finite because ${\mathbb{D}}{\cal X}$ is compact. The
functions $-u_{1,2}-c$ are positive, continuous and convex functions.

Now let us apply the Stone-Weierstrass Density Theorem [25, Thm. 5] on
${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ which is a subset of
${\mathbb{C}}{\cal X}$.

To do that we need first to show that ${\left\langle{\mathbb{U}}{\cal
X}\right\rangle}$ is an algebra (i.e. has a zero and unit, is closed under
scalar multiplication and addition and pointwise multiplication of $f$’s). In
addition ${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ must “vanish
nowhere” on ${\mathbb{D}}{\cal X}$ and “separate points”. (See below for
explanations of those properties.)

${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ is an algebra: Since
${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ is a vector space, the
constant functions $\mathbf{0},\mathbf{1}$ (identically $0$ and $1$ resp.) and
the functions $cf,f+g$ are in ${\left\langle{\mathbb{U}}{\cal
X}\right\rangle}$ for every $c{{:}\,}{\mathbb{R}}$ and
$f,g{{:}\,}{\left\langle{\mathbb{U}}{\cal X}\right\rangle}$.

Let $f,g{{:}\,}{\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ be such that
$f=u_{1}{-}u_{2}$ and $g=v_{1}{-}v_{2}$ where $u_{1,2},v_{1,2}$ are positive
continuous convex functions. Notice that

$f^{2}\hskip 10.00002pt=\hskip
10.00002pt2(u_{1}^{2}+u_{2}^{2})-(u_{1}+u_{2})^{2}$

where $u_{1,2}^{2}$ and $(u_{1}{+}u_{2})^{2}$ are positive convex functions
(because the square of a non-negative convex function is convex). That is, we
have $f^{2}\in{\left\langle{\mathbb{U}}{\cal X}\right\rangle}$. Now

$fg\hskip 10.00002pt=\hskip 10.00002pt(f+g)^{2}-(f^{2}+g^{2})$

and thus $fg{\in}{\left\langle{\mathbb{U}}{\cal X}\right\rangle}$, because we
have just shown that all of ${(f+g)^{2}},f^{2},g^{2}$ are in
${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$.

${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ vanishes nowhere: We must
show that for each $\delta{{:}\,}{\mathbb{D}}{\cal X}$ there is some
$f{{:}\,}{\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ such that
$f\delta\neq 0$. But this is immediate since $\mathbf{1}.\delta\neq 0$ for
every $\delta{{:}\,}{\mathbb{D}}{\cal X}$ and
$\mathbf{1}{\in}{\left\langle{\mathbb{U}}{\cal X}\right\rangle}$.

${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ separates points: We must
show that for every pair $\delta\neq\delta^{\prime}$ there is some
$f\in{\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ such that $f.\delta\neq
f.\delta^{\prime}$. We argue as follows.

Given $\delta{{:}\,}{\mathbb{D}}{\cal X}$ (fixed) and define
$f^{\delta}.\delta^{\prime}{{:=}\,}d_{K}(\delta^{\prime},\delta)$ for
$\delta^{\prime}{{:}\,}{\mathbb{D}}{\cal X}$. Observe that for
$\delta^{\prime}\neq\delta$ we have that
$0=f^{\delta}.\delta<d_{K}(\delta^{\prime},\delta)=f^{\delta}.\delta^{\prime}$.
Thus it suffices to show that $f^{\delta}{\in}{\left\langle{\mathbb{U}}{\cal
X}\right\rangle}$, and we continue as follows.

For every $\delta_{1,2}{{:}\,}{\mathbb{D}}{\cal X}$, we have

|
$\begin{array}[t]{@{}llll}f^{\delta}.(\delta_{1}{\mathbin{{}_{p}\kern-0.50003pt+}}\delta_{2})\end{array}$
---|---
$=$ |  $\begin{array}[t]{@{}llll}d_{K}((\delta_{1}{\mathbin{{}_{p}\kern-0.50003pt+}}\delta_{2}),\delta)\end{array}$ “$d_{K}$ is Kantorovich distance; Definition of $f^{\delta}$”
$\leq$ |  $\begin{array}[t]{@{}llll}d_{K}(\delta_{1},\delta){\mathbin{{}_{p}\kern-0.50003pt+}}d_{K}(\delta_{2},\delta)\end{array}$ “$d_{K}(\delta^{\prime},\delta)$ is convex, for fixed $\delta$”
$=$ |<EMAIL_ADDRESS>“Definition of $f^{\delta}$”

That is $\mathbf{1}-f^{\delta}\in{\mathbb{U}}{\cal X}$ and thus
${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ separates points.

By the Stone-Weierstrass Theorem [25, Thm. 5], we have
${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ is dense in
${\mathbb{C}}{\cal X}$. $\Box$

The extension of a transformer $t{{:}\,}{\mathbb{U}}{\cal
X}{\to}{\mathbb{U}}{\cal X}$ to a continuous linear function from
${\mathbb{C}}{\cal X}$ to itself is done in two stages. Firstly, $t$ is
extended _linearly_ to a continuous linear function
$t^{\prime}{{:}\,}{\left\langle{\mathbb{U}}{\cal
X}\right\rangle}{\to}{\mathbb{C}}{\cal X}$. This step is justified in Thm. 41.
Secondly, $t^{\prime}$ is extended _continuously_ to a continuous linear
function $\tilde{t}{{:}\,}{\mathbb{C}}{\cal X}{\to}{\mathbb{C}}{\cal X}$. This
step uses the density proven in Lem. 39 and is shown in Lem. 40 below.

######  Lemma 40.

Extension from ${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ to
${\mathbb{C}}{\cal X}$ Every continuous linear function $t$ from
${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ to ${\mathbb{C}}{\cal X}$
extends uniquely to a continuous linear function $\tilde{t}$ from
${\mathbb{C}}{\cal X}$ to itself.

Proof. This result follows from the Continuous Linear Extension Theorem [41,
Ch. 4 Thm. 10.1].

All we need to show is that the (Cauchy) completion of
${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$ is ${\mathbb{C}}{\cal X}$,
which follows from the fact that ${\left\langle{\mathbb{U}}{\cal
X}\right\rangle}$ is dense in ${\mathbb{C}}{\cal X}$ (Lem. 39) and that
${\mathbb{C}}{\cal X}$ is a complete normed vector space when endowed with the
uniform norm $\|f\|_{\infty}{{:=}\,}\|f{-}\mathbf{0}\|_{\infty}$. $\Box$

######  Theorem 41.

Extension from ${\mathbb{U}}{\cal X}$ to ${\mathbb{C}}{\cal X}$ Every
transformer extends uniquely to a positive continuous linear function from
${\mathbb{C}}{\cal X}$ to itself.

Proof. Let $t{{:}\,}{\mathbb{T}}{\cal X}$ be a transformer. It suffices to
prove that $t$ has a positive continuous extension $t^{\prime}$ on the sub-
vector space ${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$. If such a
$t^{\prime}$ exists then a unique extension $\tilde{t}{{:}\,}{\mathbb{C}}{\cal
X}{\mathbin{\rightarrow}}{\mathbb{C}}{\cal X}$, which is positive 232323For
the positiveness of the continuous extension, if $f$ is a positive continuous
function that is the uniform limit of a sequence of $f_{n}$’s in
${\left\langle{\mathbb{U}}{\cal X}\right\rangle}$, then the sequence of
positive continuous functions
$\max(\mathbf{0},f_{n}){\in}{\left\langle{\mathbb{U}}{\cal X}\right\rangle}$
also converges to $f$ wrt. the uniform metric. The reason is
$|f.\delta-\max(0,f_{n}.\delta)|\leq|f.\delta-f_{n}.\delta|$, for every
$\delta{{:}\,}{\mathbb{D}}{\cal X}$ and positive $f$. Thus $t.f$ has to be
positive. and continuous, can be deduced using Lem. 40.

Let $f{{:}\,}{\left\langle{\mathbb{U}}{\cal X}\right\rangle}$, there exists
$u_{1,2}\in{\mathbb{U}}{\cal X}$ such that $f{=}u_{1}{-}u_{2}$. We define
$t^{\prime}.f{=}t.u_{1}-t.u_{2}$.

$t^{\prime}$ is well-defined: We must show that $t^{\prime}.f$ is independent
of how $f$ is written as the difference of two uncertainty measures. Firstly,
notice that if $u_{1}{-}u_{2}\in{\mathbb{U}}{\cal X}$ for some
$u_{1,2}\in{\mathbb{U}}{\cal X}$ then $t.(u_{1}{-}u_{2})=t.u_{1}-t.u_{2}$.
Secondly, let $f=u_{1}-u_{2}=v_{1}-v_{2}$. Then
$(u_{1}+v_{2})-(u_{2}+v_{1})=\mathbf{0}$, which is in ${\mathbb{U}}{\cal X}$.
Therefore, we have $t.(u_{1}+v_{2})-t.(u_{2}+v_{1})=\mathbf{0}$, and that
implies $t.u_{1}-t.u_{2}=t.v_{1}-t.v_{2}$ by linearity of $t$.

$t^{\prime}$ is linear and unique: Linearity is clear and it implies
uniqueness of the extension $t^{\prime}$ over ${\left\langle{\mathbb{U}}{\cal
X}\right\rangle}$.

$t^{\prime}$ is $1$-Lipschitz: Let $f,g{{:}\,}{\left\langle{\mathbb{U}}{\cal
X}\right\rangle}$ be such that we have $f=u_{1}{-}u_{2}$ and
$g=v_{1}{-}v_{2}$. Then

|
<EMAIL_ADDRESS>
---|---
$=$ |  $\begin{array}[t]{@{}llll}\|(t.u_{1}-t.u_{2}){-}(t.v_{1}-t.v_{2})\|_{\infty}\end{array}$ “Definition of $t^{\prime}$”
$=$ |  $\begin{array}[t]{@{}llll}\|t.(u_{1}+v_{2}){-}t.(v_{1}+u_{2})\|_{\infty}\end{array}$ “$t$ is linear, $u_{i}+v_{j}{\in}{\mathbb{U}}{\cal X}$”
$\leq$ |  $\begin{array}[t]{@{}llll}\|(u_{1}+v_{2}){-}(v_{1}+u_{2})\|_{\infty}\end{array}$ “$t$ is $1$-Lipschitz”
$=$ |<EMAIL_ADDRESS>“Definition of $f,g$”

Therefore, $t^{\prime}$ is also continuous.

$t^{\prime}$ is positive: (i.e. it maps non-negative functions to non-negative
functions). This follows from monotonicity of $t$.

By Lem. 40, the extension $t^{\prime}$ further extends into a continuous
positive linear function $\tilde{t}{{:}\,}{\mathbb{C}}{\cal
X}{\mathbin{\rightarrow}}{\mathbb{C}}{\cal X}$ with $\tilde{t}.u=t.u$ for
every $u{{:}\,}{\mathbb{U}}{\cal X}$. $\Box$

##  Appendix H Proof of Cor. 34 [§9.4]

This proof is made easier by operating in a slightly more general space than
${\mathbb{H}}{\cal X}$, i.e. the measurable subset of ${\mathbb{D}}{\cal
X}{\mathbin{\rightarrow}}{\mathbb{D}}^{2}{\cal X}$, not taking advantage of
the stronger conditions that characterise ${\mathbb{H}}{\cal X}$ within it. In
this section only we write $\overline{\textrm{wp}}.$ for the function defined
as at Def. 28 but over the larger space.

######  Lemma 42.

Transformer composition For any (measurable) $h_{1,2}{{:}\,}{\mathbb{D}}{\cal
X}{\mathbin{\rightarrow}}{\mathbb{D}}^{2}{\cal X}$ we have that
$\overline{\textrm{wp}}.(h_{1};h_{2})=\overline{\textrm{wp}}.h_{1}{\mathbin{\circ}}\overline{\textrm{wp}}.h_{2}$.

Proof.

|
$\begin{array}[t]{@{}llll}\overline{\textrm{wp}}.(h_{1};h_{2}).u.\pi\end{array}$
---|---
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{(h_{1};h_{2}).\pi}\,u\end{array}$ “Def. 28 extended to $\overline{\textrm{wp}}.()$”
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{{\sf avg}.({\mathbb{D}}h_{2}.(h_{1}.\pi))}\,u\end{array}$ “$h_{1};h_{2}$ is Kleisli composition”
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{{\mathbb{D}}h_{2}.(h_{1}.\pi)}\,(\lambda{\Delta}\ \\!\mbox{\boldmath$\mathrel{\cdot}$}\ \\!{{\cal E}_{\Delta}\,u})\end{array}$ “${\cal E}_{{\sf avg}.\underline{\Delta}}\,u={\cal E}_{\underline{\Delta}}\,(\lambda{\Delta}\ \\!\mbox{\boldmath$\mathrel{\cdot}$}\ \\!{{\cal E}_{\Delta}\,u})$ from (${\dagger}$) below $\lambda$ is lambda-abstraction”
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{h_{1}.\pi}\,((\lambda{\Delta}\ \\!\mbox{\boldmath$\mathrel{\cdot}$}\ \\!{{\cal E}_{\Delta}\,u})\mathbin{\circ}h_{2})\end{array}$ “${\cal E}_{{\mathbb{D}}h_{2}.\Delta}\,F={\cal E}_{\Delta}\,(F{\mathbin{\circ}}h_{2})$ from (${\ddagger}$) below”
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{h_{1}.\pi}\,(\lambda{\pi^{\prime}}\ \\!\mbox{\boldmath$\mathrel{\cdot}$}\ \\!{((\lambda{\Delta}\ \\!\mbox{\boldmath$\mathrel{\cdot}$}\ \\!{{\cal E}_{\Delta}\,u})}\mathbin{\circ}h_{2}).\pi^{\prime})\end{array}$ “make $\pi^{\prime}$ explicit”
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{h_{1}.\pi}\,(\lambda{\pi^{\prime}}\ \\!\mbox{\boldmath$\mathrel{\cdot}$}\ \\!{{\cal E}_{h_{2}.\pi^{\prime}}\,u})\end{array}$ “$\Delta{:=}\,h_{2}.\pi^{\prime}$”
$=$ |  $\begin{array}[t]{@{}llll}\overline{\textrm{wp}}.h_{1}.(\lambda{\pi^{\prime}}\ \\!\mbox{\boldmath$\mathrel{\cdot}$}\ \\!{{\cal E}_{h_{2}.\pi^{\prime}}\,u}).\pi\end{array}$ “Def. 28”
$=$ |  $\begin{array}[t]{@{}llll}\overline{\textrm{wp}}.h_{1}.(\overline{\textrm{wp}}.h_{2}.u).\pi~{}.\end{array}$ “Def. 28”

The identities $({\dagger})$ and $({\ddagger})$ were proven by Giry ([2, Sec.
3 p.70]). In $({\ddagger})$, $F$ maps every hyper $\Delta$ to ${\cal
E}_{\Delta}\,u$. $\Box$

Remarkably, it is quite easy to show that $\textrm{wp}.()$ is an injection
over all of ${\mathbb{D}}{\cal X}{\mathbin{\rightarrow}}{\mathbb{D}}^{2}{\cal
X}$.

######  Lemma 43.

$\textrm{wp}.()$ is an injection on ${\mathbb{D}}{\cal
X}{\mathbin{\rightarrow}}{\mathbb{D}}^{2}{\cal X}$ If
$\textrm{wp}.h_{1}{=}\textrm{wp}.h_{2}$ for some (measurable)
$h_{1,2}{{:}\,}{\mathbb{D}}{\cal
X}{\mathbin{\rightarrow}}{\mathbb{D}}^{2}{\cal X}$, then $h_{1}{=}h_{2}$.

Proof. We reason

|  $\begin{array}[t]{@{}llll}h_{1}\neq h_{2}\end{array}$
---|---
$\Rightarrow$ |<EMAIL_ADDRESS>h_{2}.\pi\end{array}$ “for some $\pi{{:}\,}{\mathbb{D}}{\cal X}$”
$\Rightarrow$ |<EMAIL_ADDRESS>“wlog; $(\ref{)}$-antisymmetry from §6”
$\Rightarrow$ |  $\begin{array}[t]{@{}llll}{\cal E}_{h_{2}.\pi}\,u<{\cal E}_{h_{1}.\pi}\,u\end{array}$ “Lem. 27 completeness (_Coriaceous_),for some $u{{:}\,}{\mathbb{U}}{\cal X}$”
$\Leftrightarrow$ |<EMAIL_ADDRESS>“Def. 28”
$\Rightarrow$ |<EMAIL_ADDRESS>

$\Box$

Our next step is to use Thm. 33 to show that indeed
$h_{1};h_{2}{\in}{\mathbb{H}}{\cal X}$, so that $\overline{\textrm{wp}}.$ can
be replaced by $\textrm{wp}.()$ in Lem. 42 just above. We have

######  Lemma 44.

${\mathbb{H}}{\cal X}$ closed under composition For
$h_{1,2}{{:}\,}{\mathbb{H}}{\cal X}$ we have
$h_{1};h_{2}{\in}{\mathbb{H}}{\cal X}$.

Proof. If $h_{1,2}{{:}\,}{\mathbb{H}}{\cal X}$ then
$\textrm{wp}.h_{1,2}{\in}{\mathbb{T}}{\cal X}$ from Lems. 30,31; and since
those properties are closed under composition, we have that
$\textrm{wp}.h_{1}{\mathbin{\circ}}\textrm{wp}.h_{2}{\in}{\mathbb{T}}{\cal X}$
as well.

From Thm. 33 there is then a unique $h{{:}\,}{\mathbb{H}}{\cal X}$ such that
$\textrm{wp}.h=\textrm{wp}.h_{1}{\mathbin{\circ}}\textrm{wp}.h_{2}$; but
examination of Lem. 43 shows membership of ${\mathbb{H}}{\cal X}$ is not
necessary for that uniqueness: it applies to the whole of (measurable)
${\mathbb{D}}{\cal X}{\mathbin{\rightarrow}}{\mathbb{D}}^{2}{\cal X}$. That
is, there no other measurable $h$ in all of ${\mathbb{D}}{\cal
X}{\mathbin{\rightarrow}}{\mathbb{D}}^{2}{\cal X}$ such that
$\overline{\textrm{wp}}.h=t$.

From Lem. 42 we know that $\overline{\textrm{wp}}.(h_{1};h_{2})=t$, and so we
must have $h_{1};h_{2}=h\in{\mathbb{H}}{\cal X}$. $\Box$

Thus we can conclude

Corollary 34: Transformer composition For any $h_{1,2}{{:}\,}{\mathbb{H}}{\cal
X}$ we have that also $h_{1};h_{2}{\in}{\mathbb{H}}{\cal X}$, and furthermore
$\textrm{wp}.(h_{1};h_{2})=\textrm{wp}.h_{1}{\mathbin{\circ}}\textrm{wp}.h_{2}$.

Proof. Lemmas 42,44 just above. $\Box$

##  Appendix I Calculation of $\textrm{wp}.[\\![P]\\!]$ [§11.2]

In §11.2 a sample analysis was done on a very small program to show how, if
the post-uncertainty is fixed, a pre-uncertainty can be calculated once and
for all; and that then that pre-uncertainty can be used to investigate the
security implications of a number of different priors, without having to re-
analyse the program for each one.

Here we give the calculations for $\textrm{wp}.(\cdot)$ in §11.2. We note
below however that ideally the pre-uncertainty would be calculated by _source-
level_ reasoning; but that is not what we do here. (See also our “more
concrete aim” in §14 concerning source-level reasoning.)

Let $P$ be the program set out in Fig. 4 (and also Fig. 5 from §4.4). As usual
for weakest preconditions, we work from post- to pre-. Let $u$ be the UM from
§11.1, reflecting the circumstances of an attacker whose principal concern is
whether the two bits of xs are the same.

Beginning with the second statement, since with transformers we work from the
back towards the front, we expect informally that
$\textrm{wp}.[\\![\texttt{{xs}:=
{xs}${\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}$-{xs}}]\\!].u$
is just $u$ again — since the assignment does not affect
$\texttt{xs}[0]{=}\texttt{xs}[1]$, whichever branch is taken. Calculation
confirms that: for arbitrary $\pi$ we have

|  $\begin{array}[t]{@{}llll}\textrm{wp}.[\\![\texttt{{xs}:=
{xs}${\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}$-{xs}}]\\!].u.\pi\end{array}$
---|---
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{\mbox{\small$\begin{array}[]{r@{~}c@{~}l}[(~{}&(\pi_{00}{+}\pi_{11})/2,(\pi_{01}{+}\pi_{10})/2,\hfil~{}\\\ ~{}&(\pi_{10}{+}\pi_{01})/2,(\pi_{11}{+}\pi_{00})/2\hfil~{}&)]\end{array}$}}\,u\end{array}$ “semantics of xs:= xs${\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.45003pt\oplus}}$-xs”
$=$ |  $\begin{array}[t]{@{}llll}u.\begin{array}[t]{r@{~}c@{~}l}(~{}&(\pi_{00}{+}\pi_{11})/2,(\pi_{01}{+}\pi_{10})/2,\hfil~{}\\\ ~{}&(\pi_{10}{+}\pi_{01})/2,(\pi_{11}{+}\pi_{00})/2\hfil~{}&)\end{array}\end{array}$ “expectation over point hyper”
$=$ |  $\begin{array}[t]{@{}llll}&(\pi_{00}{+}\pi_{11})/2+(\pi_{11}{+}\pi_{00})/2\\\ \min&(\pi_{01}{+}\pi_{10})/2+(\pi_{10}{+}\pi_{01})/2\end{array}$ “definition $u$ from §11.2”
$=$ |  $\begin{array}[t]{@{}llll}(\pi_{00}{+}\pi_{11})~{}\min~{}(\pi_{01}{+}\pi_{10})\end{array}$
$=$ |  $\begin{array}[t]{@{}llll}u~{},\end{array}$ “definition $u$ again”

as we expected.

Continuing towards the front of the program we now calculate again for
arbitrary $\pi$, but from just above able to use the same $u$ that we started
with, that

|  $\begin{array}[t]{@{}llll}\textrm{wp}.[\\![\texttt{leak\
$\texttt{xs}[0]\,{\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.50003pt\oplus}}\,\texttt{xs}[1]$}]\\!].u.\pi\end{array}$
---|---
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{\mbox{\small$\begin{array}[]{r@{~}c@{~}l}~{}&(\pi_{00}/s_{0},\pi_{01}/2s_{0},\pi_{10}/2s_{0},0)\hfil~{}\\\ {\mathbin{{}_{s_{0}}\kern-0.45003pt\oplus}}~{}&(0,\pi_{01}/2s_{1},\pi_{10}/2s_{1},\pi_{11}/s_{1})\hfil~{}\\\ \end{array}$}}\,u\end{array}$ “ semantics of print $\texttt{xs}[0]\,{\mathbin{{}_{\nicefrac{{1}}{{2}}}\kern-0.45003pt\oplus}}\,\texttt{xs}[1]$ define $s_{0}{:=}\,\pi_{00}{+}(\pi_{01}{+}\pi_{10})/2$ $s_{1}{:=}\,(\pi_{01}{+}\pi_{10})/2+\pi_{11}$ ”
$=$ |  $\begin{array}[t]{@{}llll}&u.(\pi_{00}/s_{0},\pi_{01}/2s_{0},\pi_{10}/2s_{0},0)\\\ {\mathbin{{}_{s_{0}}\kern-0.50003pt\oplus}}&u.(0,\pi_{01}/2s_{1},\pi_{10}/2s_{1},\pi_{11}/s_{1})\end{array}$ “${\cal E}\,$ linear, applied to two-point hyper (Def. 5)”
$=$ |  $\begin{array}[t]{@{}llll}\pi_{00}\min(\pi_{01}{+}\pi_{10})/2+(\pi_{01}{+}\pi_{10})/2\min\pi_{11}~{},\end{array}$ “definition $u$ from previous calculation”

as claimed in §11.2.

We stress that calculating $\textrm{wp}.()$ this way for any but the smallest
programs is _not practical at all_. For a practical calculus, instead the
formulation of uncertainties as loss functions would be used to write them as
expressions at the source level, i.e. over program variables, and then using
formal manipulations in a quantitative program logic (extending e.g. [21,
22]).

The issue of source-level reasoning is discussed further in the conclusion
§14.

##  Appendix J Using loss functions to characterise pure channels

With uncertainty transformers, we can be more precise about the properties
satisfied by pure-(abstract) channel HMM’s specifically. As with markovs the
mechanism by which information is released is independent of the (probability)
values associated with the prior; in fact it only depends on the underlying
state value, that is ${\cal X}$. This property can be described neatly in
terms of a “multiplicative property” on transformers which, in addition,
provides a characterisation of transformers which correspond to channels. We
begin with a motivating example.

Take ${\cal X}{=}\\{0,1\\}$. It’s easy to construct an
$h{{:}\,}{\mathbb{H}}{\cal X}$ with the property that for all
$\pi{{:}\,}{\mathbb{D}}{\cal X}$ we have ${\sf avg}.(h.\pi)=\pi$, which is to
say that its markov is the identity, but it is still not a pure channel: we
simply “cheat” by using a different channel for each prior. Take for example
the $\pi$-indexed channels given by the matrix

$C^{\pi}\hskip 10.00002pt{:=}\,\hskip
10.00002pt\left(\begin{array}[]{cc}\pi_{0}&\pi_{1}\\\ 0&1\\\
\end{array}\right)~{}.$

The function defined $f.\pi{:=}\,[\\![\pi{\rhd}C^{\pi}]\\!]$ does not satisfy
$f{=}[\\![C{:}]\\!]$ for any _single_ fixed $C$, and this example provides the
insight for characterising pure channels: they have a simple multiplicative
property, which we express using loss functions as follows.

######  Definition 45.

Multiplicativity of transformers For loss-function
$l{{:}\,}I{\mathbin{\rightarrow}}{\cal
X}{\mathbin{\rightarrow}}{\mathbb{R}}^{\geq}$ and $\pi{{:}\,}{\mathbb{D}}{\cal
X}$ define a $\pi$-skewed loss function
$(l{\lhd}\pi).i.x{:=}\,l.i.x{\times}\pi.x$. We then say that transformer
$t{{:}\,}{\mathbb{T}}{\cal X}$ is _multiplicative_ if for any
$\pi_{1,2}{{:}\,}{\mathbb{D}}{\cal X}$ and loss function $l$ we have
$t.(U_{l{\lhd}\pi_{1}}).\pi_{2}=t.(U_{l{\lhd}\pi_{2}}).\pi_{1}$. 242424This
notation is by analogy with $\pi{\rhd}C$ that “multiplies $\pi$ in” from the
${\cal X}$ side of a matrix; in $C{\lhd}\pi$ the $\pi$ is multiplied in from
the other side. $\Box$

######  Lemma 46.

Channels are multiplicative Let $C{{:}\,}{\cal
X}{\mathbin{\rightarrowtriangle}}{\cal Y}$ be a channel matrix. Then
$\textrm{wp}.[\\![C{:}]\\!]$ is multiplicative.

Proof. This follows because the identity transformer is multiplicative, i.e.
$(U_{l{\lhd}\pi_{1}}).\pi_{2}=(U_{l{\lhd}\pi_{2}}).\pi_{1}$, and that
$\textrm{wp}.()$ applied to a pure channel maps any given loss function to a
sum of loss functions “scaled” by the columns. $\Box$

The following fact shows that this multiplicative property in fact
characterises channels.

######  Lemma 47.

Let $f{{:}\,}{\mathbb{D}}{\cal X}{\mathbin{\rightarrow}}{\mathbb{D}}^{2}{\cal
X}$ be such that $f.\pi$ has finite support for every
$\pi{{:}\,}{\mathbb{D}}{\cal X}$; assume it satisfies the pure-channel
property from §B.2; and assume that $\textrm{wp}.f$ is multiplicative as just
above. Then there is some set of observations ${\cal Y}$ and channel
$C{{:}\,}{\cal X}{\mathbin{\rightarrowtriangle}}{\cal Y}$ such that
$f=[\\![C{:}]\\!]$.

Proof. Let $N$ be the size of ${\cal X}$ and let $\upsilon$ be the uniform
distribution on ${\cal X}$. 252525It is _upsilon_ for “uniform”. Define
$\Delta{:=}\,f.\upsilon$ and let ${\cal Y}$ be the support of $\Delta$, a
finite set of distributions that will be used as column indices. Then define
$C{{:}\,}{\cal X}{\mathbin{\rightarrowtriangle}}{\cal Y}$ by

$C_{x,y}\hskip 10.00002pt{:=}\,\hskip 10.00002ptN\times\Delta.y.x~{},$

so that $f.\upsilon=\Delta=[\\![C{:}]\\!].\upsilon$. We now show that in fact
$f.\pi=[\\![C{:}]\\!].\pi$ for all $\pi{{:}\,}{\mathbb{D}}{\cal X}$.

We have for any loss function $l$ that

|  $\begin{array}[t]{@{}llll}{\cal E}_{f.\pi}\,U_{l}\end{array}$
---|---
$=$ |<EMAIL_ADDRESS>
$=$ |<EMAIL_ADDRESS>“define $l^{\prime}{:=}\,N{\times}l$”
$=$ |<EMAIL_ADDRESS>“assumption $\textrm{wp}.f$ multiplicative”
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{f.\upsilon}\,(U_{l^{\prime}{\lhd}\pi})\end{array}$
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{[\\![C{:}]\\!].\upsilon}\,(U_{l^{\prime}{\lhd}\pi})\end{array}$ “defn. $C$”
$=$ |  $\begin{array}[t]{@{}llll}{\cal E}_{[\\![C{:}]\\!].\pi}\,U_{l}~{},\end{array}$ “reverse steps above; $\textrm{wp}.[\\![C{:}]\\!]$ multiplicative”

so $f.\pi{=}[\\![C_{\Delta}{:}]\\!].\pi$ since hypers are determined by loss
functions [4, 6], thus $f{=}[\\![C_{\Delta}{:}]\\!]$ because $\pi$ was
arbitrary.

$\Box$


# Separated-Spectral-Distribution Estimation
Based on Bayesian Inference with Single RGB Camera

###### Abstract

In this paper, we propose a novel method for separately estimating spectral
distributions from images captured by a typical RGB camera. The proposed
method allows us to separately estimate a spectral distribution of
illumination, reflectance, or camera sensitivity, while recent hyperspectral
cameras are limited to capturing a joint spectral distribution from a scene.
In addition, the use of Bayesian inference makes it possible to take into
account prior information of both spectral distributions and image noise as
probability distributions. As a result, the proposed method can estimate
spectral distributions in a unified way, and it can enhance the robustness of
the estimation against noise, which conventional spectral-distribution
estimation methods cannot. The use of Bayesian inference also enables us to
obtain the confidence of estimation results. In an experiment, the proposed
method is shown not only to outperform conventional estimation methods in
terms of RMSE but also to be robust against noise.

Index Terms—  Bayesian inference, camera sensitivity, illumination,
reflectance, spectral distribution

000This work was supported by JSPS KAKENHI Grant Number JP18J20326.

##  1 Introduction

Spectral distributions of illumination, the reflectance of objects, and camera
sensitivity play an important role in color image processing. They decide the
color of pixel values in images captured by digital cameras. Spectral
distribution is a function of wavelengths and describes what wavelengths of
light are included in illumination, reflected by objects, or detected by
imaging sensors. Knowledge on spectral distributions is essential for many
computer vision tasks that use color information, such as hyperspectral
imaging [1, 2], color constancy [3, 4, 5, 6, 7, 8], color image enhancement
[9, 10, 11, 12], and intrinsic image decomposition [13, 14, 15, 16].

Spectral distributions are often measured with specialized devices.
Hyperspectral cameras are available for capturing a joint spectral
distribution of a scene, but the captured distribution is usually not
separated into illuminance, reflectance, and sensitivity. In addition, these
cameras require line scans to capture images. For separately measuring
reflectance or camera sensitivity, a monochromator that generates narrow-band
light and a spectrophotometer that measures the spectral power distribution of
this light are generally required. The requirement of specialized devices,
including hyperspectral cameras, has become a hurdle for estimating spectral
distributions because these devices are not easy to carry around and are high-
cost.

For this reason, methods of estimating spectral distributions with low-cost
equipment such as color checkers and commonly used digital cameras have been
proposed [17, 19, 18]. Although Han’s and Fu’s methods still require a
specialized color checker or additional light sources, Jiang’s method [19] can
effectively estimate camera spectral sensitivity by using only a typical color
checker and a camera. However, Jiang’s method is not available for estimating
reflectance because it uses an algorithm specifically designed for camera
sensitivity estimation to incorporate prior information of spectral
distributions [20]. The simple least-squares method can estimate illumination,
reflectance, or sensitivity, but this method suffers from noise in images.

Therefore, in this paper, we propose a novel method for separately estimating
a spectral distribution of illumination, reflectance, or camera sensitivity,
from an image of a color checker captured by a commonly used digital camera.
The use of Bayesian inference in the method makes it possible to take into
account prior information of both spectral distributions and image noise as
probability distributions. As a result, the proposed method enables us not
only to estimate spectral distributions in a unified way but also to improve
the robustness of the estimation against noise. In addition, we can obtain the
confidence of the estimation results.

We performed a numerical simulation to evaluate the performance of the
proposed method. The method was compared with a simple least-squares-based
method and Jiang’s camera-sensitivity estimation method. The experimental
results show that the proposed method outperformed the two conventional
methods in terms of the root mean squared error (RMSE) between each estimation
and the corresponding ground truth. The proposed method can also be used to
estimate both illumination and sensitivity as well as the least-squares method
can and is demonstrated to be more robust against noise than the least-squares
method.

##  2 Preliminary

In this section, we briefly summarize the imaging pipeline from spectral
distributions to the pixel values of typical digital cameras. After that, we
describe problems in estimating spectral distributions and clarify our aim.

###  2.1 Imaging pipeline

Under the assumption that objects have Lambertian reflectance, pixel values
captured by a digital camera can be calculated by using spectral distributions
of illumination, reflectance, and camera sensitivity (see Fig. 1).

Fig. 1: Imaging pipeline of digital camera

The mapping from spectral distributions into pixel values $x_{i,j,k}$ is
written as:

$x_{i,j,k}=\int_{\mathcal{D}}E_{i}(\lambda)R_{j}(\lambda)C_{k}(\lambda)d\lambda,$
(1)

where $\lambda$ means a wavelength of light, $\mathcal{D}$ is a set of
wavelengths of visible light, $E_{i}(\lambda)$ is the
$i\in\\{1,\cdots,I\\}$-th illumination, $R_{j}(\lambda)$ is the
$j\in\\{1,\cdots,J\\}$-th reflectance, and $C_{k}(\lambda)$ is the
$k\in\\{1,\cdots,K\\}$-th sensitivity. When we capture an image of a color
checker having $4\times 6$ patches by using a single RGB camera under
daylight, $I,J$, and $K$ are $1,24$, and $3$, respectively.

By sampling spectral distributions along the wavelength axis, eq. (1) can be
approximated by the following discrete form.

$x_{i,j,k}=\mathrm{tr}(\mathrm{diag}(\boldsymbol{e}_{i})\mathrm{diag}(\boldsymbol{r}_{j})\mathrm{diag}(\boldsymbol{c}_{k})),$
(2)

where $\boldsymbol{e}_{i},\boldsymbol{r}_{j}$, and $\boldsymbol{c}_{k}$ are
$N$-dimensional column vectors that denote sampled distributions of
$E_{i},R_{j}$, and $C_{k}$, respectively, and $N$ indicates the number of
discrete wavelengths.

###  2.2 Scenario

Our aim in this paper is to separately estimate a spectral distribution of
illumination, reflectance, or sensitivity [i.e.,
$E_{i}(\lambda),R_{j}(\lambda)$, or $C_{k}(\lambda)$] from pixel values
$x_{i,j,k}$ under the condition that the other two spectral distributions are
given. In contrast, a hyperspectral camera having a large number $K$ of
channels aims to capture a multiplied spectral distribution
$E_{i}(\lambda)R_{j}(\lambda)$ when the camera sensitivity $C_{k}(\lambda)$ is
given.

Let us consider a situation in which we want to estimate illumination
$\boldsymbol{e}_{i}$ from given reflectance $\boldsymbol{r}_{j}$, sensitivity
$\boldsymbol{c}_{k}$, and the corresponding pixel values $x_{i,j,k}$. In this
situation, the simplest way is to use least squares as

$\hat{\boldsymbol{e}}_{i}=\operatorname*{arg\,min}_{\boldsymbol{e}}\|\boldsymbol{x}_{i}-\boldsymbol{\mathrm{M}}_{\boldsymbol{r},\boldsymbol{{c}}}\boldsymbol{e}\|^{2},$
(3)

where $\hat{\boldsymbol{e}}_{i}$ is an estimation of $\boldsymbol{e}_{i}$.
Vector $\boldsymbol{x}_{i}$ is given as

$\boldsymbol{x}_{i}=(x_{i,1,1},x_{i,1,2},\cdots,x_{i,J,K}),$ (4)

and matrix $\boldsymbol{\mathrm{M}}_{\boldsymbol{r},\boldsymbol{c}}$ is
calculated by using the Hadamard product $\odot$ as

$\boldsymbol{\mathrm{M}}_{\boldsymbol{r},\boldsymbol{c}}=(\boldsymbol{r}_{1}\odot\boldsymbol{c}_{1},\boldsymbol{r}_{1}\odot\boldsymbol{c}_{2},\cdots,\boldsymbol{r}_{J}\odot\boldsymbol{c}_{K})^{\top}.$
(5)

Similarly to the case of illumination, the least-squares method can also
estimate reflectance or sensitivity. In practice, however, the direct
inversion in eq. (3) cannot reliably recover a spectral distribution because
it is quite sensitive to noise and the spectral reflectance of real-world
objects has low intrinsic dimensionality, as pointed out in [19].

To improve the estimation accuracy, research has been devoted to analyzing the
characteristics of spectral distributions and to incorporating these
characteristics as prior information in the estimation. Judd et al. analyzed
the spectral distributions of daylight and found that they can be written as
the sum of daylight’s mean spectral distribution and two other bases [20].
Jiang et al. proposed a camera-spectral-sensitivity estimation method using
prior information by which camera sensitivity can be approximated by using two
bases obtained by principal component analysis on a set of spectral
distributions of 28 camera sensitivities [19]. Jiang’s method works better
than the least-squares method. However, its dedicated algorithm for
incorporating prior information makes the method specialized only for camera
sensitivity estimation.

For this reason, we propose a novel spectral-distribution estimation method
based on Bayesian inference.

##  3 Proposed method

The proposed Bayesian-inference-based spectral-distribution estimation method
separately estimates the spectral distribution of illumination, reflectance,
or sensitivity from pixel values $x_{i,j,k}$. The method enables us to:

  * •

Estimate illumination, reflectance, or sensitivity separately in a unified
way,

  * •

Enhance the robustness of the estimation against noise by incorporating prior
information of noise as probability distributions, and

  * •

Obtain the confidence of estimation results as a precision matrix.

###  3.1 Estimating spectral distribution by Bayesian inference

Let us consider a situation in which illumination is estimated from given
reflectance, sensitivity, and pixel values. The goal of the estimation is to
calculate the posterior distribution of the
$p(\boldsymbol{e}_{i}|\mathrm{X},\mathrm{R},\mathrm{C})$ of
$\boldsymbol{e}_{i}$, where
$\mathrm{X}=\\{x_{i,j,k}\\},\mathrm{R}=\\{\boldsymbol{r}_{j}\\}$, and
$\mathrm{C}=\\{\boldsymbol{c}_{k}\\}$. To estimate
$p(\boldsymbol{e}_{i}|\mathrm{X},\mathrm{R},\mathrm{C})$, we assume a prior
probability distribution $p(\boldsymbol{e}_{i})$ of $\boldsymbol{e}_{i}$ and a
probability distribution
$p(x_{i,j,k}|\boldsymbol{e}_{i},\boldsymbol{r}_{j},\boldsymbol{c}_{k})$ of
$x_{i,j,k}$ (i.e., likelihood) as

$\displaystyle
p(\boldsymbol{e}_{i})=\mathcal{N}(\boldsymbol{e}_{i}|\boldsymbol{\mu}_{\boldsymbol{e}_{i}},\boldsymbol{\mathrm{\Lambda}}_{\boldsymbol{e}_{i}}^{-1}),$
(6) $\displaystyle
p(x_{i,j,k}|\boldsymbol{e}_{i},\boldsymbol{r}_{j},\boldsymbol{c}_{k})$
$\displaystyle=\mathcal{N}(x_{i,j,k}|\mathrm{tr}(\mathrm{diag}(\boldsymbol{e}_{i})\mathrm{diag}(\boldsymbol{r}_{j})\mathrm{diag}(\boldsymbol{c}_{k})),\beta^{-1}),$
(7)

respectively, where the mean vector $\boldsymbol{\mu}_{\boldsymbol{e}_{i}}$,
the precision matrix $\boldsymbol{\mathrm{\Lambda}}_{\boldsymbol{e}_{i}}$, and
the precision $\beta$ are hyperparameters. Equation (7) corresponds to an
image noise model.

On the basis of the Bayesian theorem,
$p(\boldsymbol{e}_{i}|\mathrm{X},\mathrm{R},\mathrm{C})$ is given by

$p(\boldsymbol{e}_{i}|\mathrm{X},\mathrm{R},\mathrm{C})\propto
p(\mathrm{X}|\boldsymbol{e}_{i},\mathrm{R},\mathrm{C})p(\boldsymbol{e}_{i}).$
(8)

Here,

$p(\mathrm{X}|\boldsymbol{e}_{i},\mathrm{R},\mathrm{C})=\prod_{j,k}p(x_{i,j,k}|\boldsymbol{e}_{i},\boldsymbol{r}_{j},\boldsymbol{c}_{k}).$
(9)

Taking the logarithm of
$p(\boldsymbol{e}_{i}|\mathrm{X},\mathrm{R},\mathrm{C})$, we obtain

$\displaystyle\ln{p(\boldsymbol{e}_{i}|\mathrm{X},\mathrm{R},\mathrm{C})}$
$\displaystyle=\ln{p(\mathrm{X}|\boldsymbol{e}_{i},\mathrm{R},\mathrm{C})}+\ln{p(\boldsymbol{e}_{i})}+\mathrm{const.}$
$\displaystyle=-\frac{1}{2}\boldsymbol{e}_{i}^{\top}\left(\boldsymbol{\mathrm{\Lambda}}_{\boldsymbol{e}_{i}}+\beta\sum_{j,k}\mathrm{diag}(\boldsymbol{s}_{j})\boldsymbol{c}_{k}\boldsymbol{c}_{k}^{\top}\mathrm{diag}(\boldsymbol{s}_{j})\right)\boldsymbol{e}_{i}$
$\displaystyle+\boldsymbol{e}_{i}^{\top}\left(\boldsymbol{\mathrm{\Lambda}}_{\boldsymbol{e}_{i}}\boldsymbol{\mu}_{\boldsymbol{e}_{i}}+\beta\sum_{j,k}x_{i,j,k}\mathrm{diag}(\boldsymbol{s}_{j})\boldsymbol{c}_{k}\right)$
$\displaystyle+\mathrm{const.}$ (10)

From eq. (10), it is confirmed that the posterior distribution
$p(\boldsymbol{e}_{i}|\mathrm{X},\mathrm{R},\mathrm{C})$ follows a Gaussian
distribution
$\mathcal{N}(\boldsymbol{e}_{i}|\hat{\boldsymbol{\mu}}_{\boldsymbol{e}_{i}},\hat{\boldsymbol{\mathrm{\Lambda}}}_{\boldsymbol{e}_{i}})$.
The mean $\hat{\boldsymbol{\mu}}_{\boldsymbol{e}_{i}}$ and precision
$\hat{\boldsymbol{\mathrm{\Lambda}}}_{\boldsymbol{e}_{i}}$ of the posterior
distribution are given as

$\displaystyle\hat{\boldsymbol{\mathrm{\Lambda}}}_{\boldsymbol{e}_{i}}$
$\displaystyle=\boldsymbol{\mathrm{\Lambda}}_{\boldsymbol{e}_{i}}-\beta\sum_{j,k}\mathrm{diag}(\boldsymbol{r}_{j})\boldsymbol{c}_{k}\boldsymbol{c}_{k}^{\top}\mathrm{diag}(\boldsymbol{r}_{j}),$
(11) $\displaystyle\hat{\boldsymbol{\mu}}_{\boldsymbol{e}_{i}}$
$\displaystyle=\hat{\boldsymbol{\mathrm{\Lambda}}}_{\boldsymbol{e}_{i}}\left(\Lambda_{\boldsymbol{e}_{i}}\boldsymbol{\mu}_{\boldsymbol{e}_{i}}+\beta\sum_{j,k}x_{i,j,k}\mathrm{diag}(\boldsymbol{r}_{j})\boldsymbol{c}_{k}\right).$
(12)

Similarly to the case of illumination, we can estimate the posterior
probability distribution
$p(\boldsymbol{r}_{j}|\mathrm{X},\mathrm{E},\mathrm{C})$ of reflectance from
illumination, sensitivity, and pixel values as

$\displaystyle\hat{\boldsymbol{\mathrm{\Lambda}}}_{\boldsymbol{r}_{j}}$
$\displaystyle=\boldsymbol{\mathrm{\Lambda}}_{\boldsymbol{r}_{j}}-\beta\sum_{k,i}\mathrm{diag}(\boldsymbol{c}_{k})\boldsymbol{e}_{i}\boldsymbol{e}_{i}^{\top}\mathrm{diag}(\boldsymbol{c}_{k}),$
(13) $\displaystyle\hat{\boldsymbol{\mu}}_{\boldsymbol{r}_{j}}$
$\displaystyle=\hat{\boldsymbol{\mathrm{\Lambda}}}_{\boldsymbol{r}_{j}}\left(\boldsymbol{\mathrm{\Lambda}}_{\boldsymbol{r}_{j}}\boldsymbol{\mu}_{\boldsymbol{r}_{j}}+\beta\sum_{k,i}x_{i,j,k}\mathrm{diag}(\boldsymbol{c}_{k})\boldsymbol{e}_{i}\right),$
(14)

or we can estimate the posterior probability distribution
$p(\boldsymbol{c}_{k}|\mathrm{X},\mathrm{E},\mathrm{R})$ of sensitivity from
illumination, reflectance, and pixel values as

$\displaystyle\hat{\boldsymbol{\mathrm{\Lambda}}}_{\boldsymbol{c}_{k}}$
$\displaystyle=\boldsymbol{\mathrm{\Lambda}}_{\boldsymbol{c}_{k}}-\beta\sum_{i,j}\mathrm{diag}(\boldsymbol{e}_{i})\boldsymbol{r}_{j}\boldsymbol{r}_{j}^{\top}\mathrm{diag}(\boldsymbol{e}_{i}),$
(15) $\displaystyle\hat{\boldsymbol{\mu}}_{\boldsymbol{c}_{k}}$
$\displaystyle=\hat{\boldsymbol{\mathrm{\Lambda}}}_{\boldsymbol{c}_{k}}\left(\boldsymbol{\mathrm{\Lambda}}_{\boldsymbol{c}_{k}}\boldsymbol{\mu}_{\boldsymbol{c}_{k}}+\beta\sum_{i,j}x_{i,j,k}\mathrm{diag}(\boldsymbol{e}_{i})\boldsymbol{r}_{j}\right).$
(16)

###  3.2 Incorporating prior information into estimation

Incorporating prior information of spectral distributions into the proposed
estimation method is simply done by modifying the mean and the precision
matrix for the prior distributions
$p(\boldsymbol{e}_{i}),p(\boldsymbol{r}_{j})$, and $p(\boldsymbol{c}_{k})$.
For example, we can use the mean spectral distribution
$\overline{\boldsymbol{e}}$ of daylight in [20] as

$\boldsymbol{\mu}_{\boldsymbol{e}_{i}}=\overline{\boldsymbol{e}}.$ (17)

In addition, the mean spectral distribution $\overline{\boldsymbol{c}}_{k}$ of
the $28$ RGB camera sensitivities in [20] can be utilized as

$\boldsymbol{\mu}_{\boldsymbol{c}_{k}}=\overline{\boldsymbol{c}}_{k}.$ (18)

Incorporating prior information of image noise into the proposed estimation
method is similarly done by modifying the mean and the precision for
$p(x_{i,j,k}|\boldsymbol{e}_{i},\boldsymbol{r}_{j},\boldsymbol{c}_{k})$.

###  3.3 Proposed procedure

The procedure for estimating illumination $\boldsymbol{e}_{i}$ by using the
proposed method is as follows

  1. 1.

Set hyperparameters for prior distributions in eqs. (6) and (7), where prior
information of illumination can be incorporated such as in eq. (17).

  2. 2.

Calculate the mean $\hat{\boldsymbol{\mu}}_{\boldsymbol{e}_{i}}$ and the
precision matrix $\hat{\boldsymbol{\mathrm{\Lambda}}}_{\boldsymbol{e}_{i}}$ of
the posterior distribution
$p(\boldsymbol{e}_{i}|\mathrm{X},\mathrm{R},\mathrm{C})$ in accordance with
eqs. (11) and (12) by using $\mathrm{X},\mathrm{R}$, and $\mathrm{C}$.

  3. 3.

Obtain an estimation by normalizing the mean
$\hat{\boldsymbol{\mu}}_{\boldsymbol{e}_{i}}$ as

$\hat{\boldsymbol{e}}_{i}=\frac{\hat{\boldsymbol{\mu}}_{\boldsymbol{e}_{i}}}{\underset{n}{\max}~{}e_{i,n}},$
(19)

where $e_{i,n}$ indicates the $n$-th element of $\boldsymbol{e}_{i}$.

Note that the calculated posterior distribution
$p(\boldsymbol{e}_{i}|\mathrm{X},\mathrm{R},\mathrm{C})$ can be used as the
prior distribution $p(\boldsymbol{e}_{i})$ for the next estimation. This
enables the estimation to be updated each time a new observation (i.e.,
captured image) is obtained. In addition,
$\hat{\boldsymbol{\mathrm{\Lambda}}}_{\boldsymbol{e}_{i}}$ can be considered
as the confidence of the estimation. Reflectance $\boldsymbol{r}_{j}$ and
sensitivity $\boldsymbol{c}_{k}$ can be estimated in the same way as for
illumination [see eqs. (11) to (16)].

##  4 Simulation

To confirm the effectiveness of the proposed method, we conducted a
simulation.

###  4.1 Simulation conditions

In this simulation, we calculated pixel values from the spectral distributions
shown in Fig. 2 in accordance with eq. (2), where the illumination was from
the spectral distribution of the CIE Standard Illuminant D65, the reflectance
was from a color checker manufactured by BabelColor [21], and the camera
sensitivity was that of the Nikon 5100 in [22]. In addition, we added Gaussian
noise with a mean of 0 and a standard deviation of $0.01$ into the calculated
pixel values $x_{i,j,k}$. Assuming a situation in which the illumination is
unknown, we estimated the illumination by using the reflectance, sensitivity,
and pixel values. Similarly to the illumination, we also estimated the
sensitivity from the illumination, reflectance, and pixel values. The
estimation accuracy of the proposed method was evaluated by using the well-
known root mean squared error (RMSE) between the estimation and the
corresponding ground truth.

(a) Illumination

(b) Reflectance

(c) Sensitivity

Fig. 2: Ground truth for spectral distribution

Although there are advanced spectral-distribution estimation methods such as
[17, 18], they require a specialized color checker or light source. For this
reason, we compared the proposed method with the least-squares method shown in
eq. (3) and with Jiang’s high-performance method that requires no special
equipment [19]. Here, we used Jiang’s method only for estimating sensitivity
since Jiang’s method is not designed for estimating illumination when
sensitivity is given.

###  4.2 Results

Figure 3 shows spectral distributions of the illumination estimated by using
the least-squares and proposed methods in the case where pixel values had no
noise. Both methods estimated the illumination well.

(a) Least squares

(b) Proposed

Fig. 3: Estimated illumination

Figure 4 shows spectral distributions of the sensitivity estimated by using
the three methods for the case that pixel values had no noise. As shown in
Fig. 4(4(a)), least squares provided an estimation that was not smooth even
under the noiseless case, but Jiang’s method and the proposed method provided
smooth distributions. This is because the number of available pixel values for
estimating sensitivity was less than that for estimating illumination, i.e.,
$I\times J<J\times K$ in this case.

(a) Least squares

(b) Jiang [19]

(c) Proposed

Fig. 4: Estimated sensitivity

RMSE scores for the three methods in the case of no noise and noise with the
standard deviation of $0.01$ are shown in Tables 1 and 2, respectively. From
the tables, it is confirmed that the proposed method and Jiang’s method were
robust against noise, but the least-squares method was not.

Table 1: RMSE scores (w/o noise)  | Least squares | Jiang [19] | Proposed
---|---|---|---
Illumination | 0.000 | — | 0.019
Sensitivity R | 0.041 | 0.064 | 0.043
Sensitivity G | 0.041 | 0.043 | 0.020
Sensitivity B | 0.019 | 0.034 | 0.040
|  |  |
Table 2: RMSE scores (w/ additive Gaussian noise having std. of 0.01)  | Least squares | Jiang [19] | Proposed
---|---|---|---
Illumination | 0.580 | — | 0.018
Sensitivity R | 0.149 | 0.064 | 0.043
Sensitivity G | 0.256 | 0.042 | 0.020
Sensitivity B | 0.168 | 0.034 | 0.040
|  |  |

For these reasons, the effectiveness of the proposed method was confirmed in
terms of RMSE. The proposed method was also demonstrated to be robust against
noise and to achieve accuracy comparable to Jiang’s recent effective method.
Furthermore, the proposed method can estimate illumination, reflectance, or
sensitivity in a unified way, while Jiang’s method is specialized only for
estimating sensitivity.

##  5 Conclusion

In this paper, we proposed a novel method for separately estimating a spectral
distribution of illumination, reflectance, or sensitivity from images of a
color checker captured by a single RGB camera. By using Bayesian inference in
the method, prior information of both spectral distributions and image noise
can be incorporated into the estimation. As a result, the method enables us
not only to estimate spectral distributions in a unified way but also to
improve the robustness of the estimation against noise. The method also has
other advantages of Bayesian inference, i.e., obtaining the confidence of
estimation. Experimental results showed that the proposed method can correctly
estimate spectral distributions even under a noisy condition.

In future work, we will extend the proposed method to estimate both
illumination and sensitivity at the same time from pixel values and
reflectance. Moreover, we will apply a more realistic noise model to the
proposed method.

## References

  * [1] J.-I. Park, M.-H. Lee, M. D. Grossberg, and S. K. Nayar, “Multispectral Imaging Using Multiplexed Illumination,” in _Proceedings of IEEE International Conference on Computer Vision_ , Oct. 2007, pp. 1–8.
  * [2] S. Tominaga, “Spectral imaging by a multichannel camera,” _Journal of Electronic Imaging_ , vol. 8, no. 4, p. 332, Oct. 1999.
  * [3] D. H. Brainard and W. T. Freeman, “Bayesian color constancy,” _Journal of the Optical Society of America A_ , vol. 14, no. 7, pp. 1393–1411, 1997.
  * [4] A. Gijsenij, T. Gevers, and J. van de Weijer, “Computational Color Constancy: Survey and Experiments,” _IEEE Transactions on Image Processing_ , vol. 20, no. 9, pp. 2475–2489, Sep. 2011.
  * [5] D. Cheng, B. Price, S. Cohen, and M. S. Brown, “Beyond White: Ground Truth Colors for Color Constancy Correction,” in _Proceedings of IEEE International Conference on Computer Vision_ , Dec. 2015, pp. 298–306.
  * [6] M. Afifi, B. Price, S. Cohen, and M. S. Brown, “When Color Constancy Goes Wrong: Correcting Improperly White-Balanced Images,” in _Proceedings of IEEE Conference on Computer Vision and Pattern Recognition_ , Jun. 2019, pp. 1535–1544.
  * [7] P. Das, A. S. Baslamisli, Y. Liu, S. Karaoglu, and T. Gevers, “Color Constancy by GANs: An Experimental Survey,” Dec. 2018. [Online]. Available: http://arxiv.org/abs/1812.03085
  * [8] M. Afifi and M. S. Brown, “Deep White-Balance Editing,” in _Proceedings of IEEE Conference on Computer Vision and Pattern Recognition_ , Jun. 2020, pp. 1394–1403.
  * [9] Y. Ueda, H. Misawa, T. Koga, N. Suetake, and E. Uchino, “Hue-Preserving Color Contrast Enhancement Method Without Gamut Problem by Using Histogram Specification,” in _Proceedings of IEEE International Conference on Image Processing_ , Oct. 2018, pp. 1123–1127.
  * [10] Y. Kinoshita and H. Kiya, “Automatic exposure compensation using an image segmentation method for single-image-based multi-exposure fusion,” _APSIPA Transactions on Signal and Information Processing_ , vol. 7, no. e22, Dec. 2018.
  * [11] Y. Kinoshita and H. Kiya, “Scene Segmentation-Based Luminance Adjustment for Multi-Exposure Image Fusion,” _IEEE Transactions on Image Processing_ , vol. 28, no. 8, pp. 4101–4116, Aug. 2019.
  * [12] Y. Kinoshita and H. Kiya, “Hue-Correction Scheme Based on Constant-Hue Plane for Deep-Learning-Based Color-Image Enhancement,” _IEEE Access_ , vol. 8, pp. 9540–9550, Jan. 2020.
  * [13] B. Cai, X. Xu, K. Guo, K. Jia, B. Hu, and D. Tao, “A Joint Intrinsic-Extrinsic Prior Model for Retinex,” in _Proceedings of IEEE International Conference on Computer Vision_ , Oct. 2017, pp. 4020–4029.
  * [14] Z. Li and N. Snavely, “Learning Intrinsic Image Decomposition from Watching the World,” in _Proceedings of IEEE Conference on Computer Vision and Pattern Recognition_ , Jun. 2018, pp. 9039–9048.
  * [15] Y. Liu, Y. Li, S. You, and F. Lu, “Unsupervised Learning for Intrinsic Image Decomposition from a Single Image,” in _Proceedings of IEEE Conference on Computer Vision and Pattern Recognition_ , Jun. 2020, pp. 3245–3254.
  * [16] K. Seo, Y. Kinoshita, and H. Kiya, “Deep Retinex Network for Estimating Illumination Colors with Self-Supervised Learning,” in _Proceedings of IEEE Global Conference on Life Sciences and Technologies_ , Mar. 2021, pp. 1–5.
  * [17] Shuai Han, Y. Matsushita, I. Sato, T. Okabe, and Y. Sato, “Camera spectral sensitivity estimation from a single image under unknown illumination by using fluorescence,” in _Proceedings of IEEE Conference on Computer Vision and Pattern Recognition_ , Jun. 2012, pp. 805–812.
  * [18] Y. Fu, A. Lam, I. Sato, T. Okabe, and Y. Sato, “Reflectance and Fluorescence Spectral Recovery via Actively Lit RGB Images,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 38, no. 7, pp. 1313–1326, Jul. 2016.
  * [19] J. Jiang, D. Liu, J. Gu, and S. Susstrunk, “What is the space of spectral sensitivity functions for digital color cameras?” in _Proceedings of IEEE Workshop on Applications of Computer Vision_ , Jan. 2013, pp. 168–179.
  * [20] D. B. Judd, D. L. MacAdam, G. Wyszecki, H. W. Budde, H. R. Condit, S. T. Henderson, and J. L. Simonds, “Spectral Distribution of Typical Daylight as a Function of Correlated Color Temperature,” _Journal of the Optical Society of America_ , vol. 54, no. 8, p. 1031, Aug. 1964.
  * [21] “BabelColor.” [Online]. Available: https://www.babelcolor.com/colorchecker-2.htm
  * [22] T. Mansencal, M. Mauderer, M. Parsons, N. Shaw, K. Wheatley, S. Cooper, J. D. Vandenberg, L. Canavan, K. Crowson, O. Lev, K. Leinweber, S. Sharma, T. J. Sobotka, D. Moritz, M. Pppp, C. Rane, P. Eswaramoorthy, J. Mertic, B. Pearlstine, M. Leonhardt, O. Niemitalo, M. Szymanski, M. Schambach, S. Huang, M. Wei, N. Joywardhan, O. Wagih, P. Redman, J. Goldstone, and S. Hill, “Colour 0.3.16,” [Online]. Available: https://doi.org/10.5281/zenodo.3757045#.X_zJFXCo-EY.mendeley