Measuring Information Leakage in
Non-stochastic Brute-Force Guessing

Ni Ding, Member, IEEE, Farhad Farokhi, Senior Member, IEEE
An earlier version of the results were presented in 2020 IEEE Information Theory Workshop (ITW 2020), which was held virtually in 2021 [1].
N. Ding is with School of Computing and Information Systems, the University of Melbourne. The work of Ni Ding is funded by the Doreen Thomas Postdoctoral Fellowship at the University of Melbourne.
F. Farokhi is with the Department of Electrical and Electronic Engineering, the University of Melbourne. When working on this paper, F. Farokhi was also affiliated with CSIRO's Data61. The work of F. Farokhi is, in part, funded by the Faculty of Engineering and Information Technology at the University of Melbourne.

This paper proposes an operational measure of non-stochastic information leakage to formalize privacy against a brute-force guessing adversary.

The information is measured by non-probabilistic uncertainty of uncertain variables, the non-stochastic counterparts of random variables.

For $X$ that is related to released data $Y$, the non-stochastic brute-force leakage is measured by the complexity of exhaustively checking all the possibilities of the private attribute $U$ of $X$ by an adversary. The complexity refers to the number of trials to successfully guess $U$.

Maximizing this leakage over all possible private attributes $U$ gives rise to the maximal (i.e., worst-case) non-stochastic brute-force guessing leakage. This is proved to be fully determined by the minimal non-stochastic uncertainty of $X$ given $Y$, which also determines the worst-case attribute $U$ indicating the highest privacy risk if $Y$ is disclosed.

The maximal non-stochastic brute-force guessing leakage is shown to be proportional to the non-stochastic identifiability of $X$ given $Y$ and upper bounds the existing maximin information. The latter quantifies the information leakage when an adversary must perfectly guess $U$ in one-shot via $Y$.

Experiments are used to demonstrate the tradeoff between the maximal non-stochastic brute-force guessing leakage and the data utility (measured by the maximum quantization error) and to illustrate the relationship between maximin information and stochastic one-shot maximal leakage.

§ INTRODUCTION

There is no doubt that data privacy and security is more important than ever.

With increasing frequency and volume of data sharing activities, people (e.g., individuals, businesses, and government entities) are becoming more concerned about confidentiality of personal information and whether it can be inferred and maliciously used for discrimination or unfair decision making.

Cyber-security also faces new threats stemming from advances in data mining, machine learning, and big data analytic. These threats are exacerbated by seemingly unlimited computational resources and capabilities of adversaries, multi-party side information attacks, unpredictable uses of large collections of data, and  non-intuitive private information leakage [2, 3].

To address these challenges, there is an urgent need to better understand privacy risk of data disclosure measured by private information leakage.

Although it is hard to reach an unanimous agreement on the definition of data privacy and leakage [2, 4], fundamental requirements of an operational measure of information leakage were listed in [5]; see Appendix <ref> for the exact axioms. The requirements not only point out that (R1) the measure should objectively quantify difficulty level of inferring private information but also highlights requiring minimum assumptions (R2) and accordance with intuition (R4). We believe that these requirements have not been fully addressed previously and should be revisited in the face of new challenges.

Data regulation, processing, or sanitation schemes must be applied before releasing private data and so the privacy metric is usually defined under some generic assumptions about the adversary, e.g., an adversarial model that describes the attacker's computational capability, targeted sensitive attribute, and side information [4].

However, in complex cross-sectional multi-purpose data-sharing environments, it is hard to predict the adversary's behavior in advance. Therefore, (R2) suggests minimizing the assumption about the adversary so that the privacy measure can be generally applied.

In this sense, instead of one-shot malicious estimation as assumed in most existing studies, e.g., [5, 6],

we propose considering an adversary with unlimited computational power, who is capable of exhaustively guessing the private data and testing it. This motivates the brute-force guessing framework of this paper.

Another existing assumption is that the inference is statistical and the side information refers to statistical prior belief. However, privacy leakage can also be non-probabilistic.

For instance, in algorithmic information theory,

the adversary's uncertainty, i.e., the difficulty in protecting a sensitive attribute, can be described by features independent of probability distribution, e.g., the size of the alphabet and the concurrence of two distinct values.

In [7], it is elaborated that a non-stochastic framework is more desirable for small datasets using which we can only empirically determine the presence of a variable instead of its relative frequency. In other cases, particularly adversarial scenarios, uncertainty may not be described by a priori known stochastic assumptions and must be treated as
bounded unknown variables without statistical assumptions [8, 9]. Also, un-truthfulness in randomized privacy-preserving reports [10, 11] and complications in financial auditing and fraud detection [12, 13] can motivate non-stochastic privacy-preserving techniques. These motivate the need to investigate information leakage in non-stochastic frameworks and to develop noiseless policies for privacy preservation by minimizing non-stochastic information leakage.

Noting catastrophic consequences of high-risk privacy breaches, a privacy measure should not undervalue the severity of security and privacy breaches, as stated in (R4), to guarantee the strength of protection schemes.

Therefore, worst-case infringements should be identified.

For example, the differential privacy [14] identifies the largest statistical distance between two individuals' data, i.e., the easiest pair that can be distinguished in the disclosed data set. The measures proposed in [6, 15] quantify the worst-case information leakage when an adversary tries to infer any sensitive parameter from the disclosed data. In this paper, we consider the worst-case adversarial behaviours from the perspectives of brute-force attacks (unlimited computational capabilities) and non-stochastic information leakage (not needing statistical assumptions).

Contributions: In this paper, we propose a measure of information leakage in a non-stochastic guessing framework.

Assume that $X$ is the data to be released to the public after privacy-aware sanitation or processing. The processed data is  $Y$, which will be eventually released to the public. We consider a brute-force guessing setup in which an adversary is assumed to have unlimited computational resources that can exhaustively guessing the sensitive attribute $U$ of $X$, i.e., checking all the possibilities of $U$ that are compatible with its observations to find out the actual realization, by access to $Y$.

This is similar to the interpretation of [5] for password guessing or side-channel attacks on cipher systems in which an adversary can repeatedly check all the possible combinations in the disclosed data.

But, the inference is assumed to be non-probabilistic, for which we use uncertain variables, the non-stochastic counterparts of random variables introduced in [16], to quantify the information leakage.

1) Considering the case when the adversary is inferring an attribute $U$ of $X$, we propose the non-stochastic brute-force guessing leakage as the ratio of the worst-case number of guesses for the adversary in the presence of the output $Y$ and in the absence of it. This definition is consistent with the stochastic brute-force guessing leakage [17] with the exception of avoiding distributions or statistics.

2) Relaxing the assumption that the adversary targets a specific attribute $U$, i.e., considering when we are not aware of the adversary's intentions, we propose the maximal leakage as the worst-case (i.e., the largest) non-stochastic brute-force guessing leakage over all attributes $U$.
The exact value of this maximal leakage is shown to be fully determined by the conditional uncertainty of $X$ given $Y$.

The derived maximal leakage measure satisfies not only the requirements (R1), (R2) and (R4), but also axiomatic properties in (R3): post-processing inequality, independence property, and additivity; see Appendix <ref> for these axioms.

We demonstrate by an example that, for given $X$ and $Y$, the worst-case sensitive attribute $U$ that incurs the maximal non-stochastic brute-force guessing leakage is determined by the minimal uncertainty of $X$ conditioned on $Y$, defined by conditional ranges of uncertain variables [16].

3) We explore the relationship between the maximal non-stochastic brute-force guessing leakage and the existing measures of information leakage in the literature. First, maximal non-stochastic leakage is proportional to the non-stochastic identifiability of $X$ via the observation of $Y$. Second, the maximin information [16] is shown to measure the worst-case brute-force guessing leakage over all $U$ such that the adversary must always correctly guess the attribute in the first guess via the observation $Y$. Therefore, the maximin information is upper bounded by the maximal non-stochastic brute-force guessing leakage. Recently, it was shown that the maximin information captures the entropy of common uncertain variable (the largest uncertain variable that can be directly computed using $X$ and $Y$) and is thus useful for understanding private information in perfect privacy [18]. Third, we perform experiments on a real-world dataset to observe the privacy-utility tradeoff, where it is shown that the maximal stochastic (one-shot) guessing leakage in [5] is no greater than the maximin information, which is further upper bounded by the maximal non-stochastic brute-force guessing leakage.

The rest of the paper is organized as follows. We present preliminary material on uncertain variables and non-stochastic information theory in Section <ref>.

In Section <ref>, we measure information leakage from a specific sensitive attribute $U$ to the output $Y$ and use it as the privacy measure when we are aware of adversary's intentions.

We extend this notion to when we are not aware of the adversary's intentions by defining and computing maximal non-stochastic brute-force guessing leakage, the relationship of which to the non-stochastic identifiability is studied in Section <ref>.

We compare the brute-force notion of non-stochastic information leakage with one-shot guessing measures, such as maximin information and stochastic maximal leakage in Section <ref>. Finally, we show experimental results on a heart disease dataset in Section <ref> and conclude the paper in Section <ref>.

§ UNCERTAIN VARIABLES

We borrow the following definitions of non-stochastic information in [16]. Consider uncertainty set $\Omega$. An uncertain variable, uv in short, is a mapping on $\Omega$. For example, for uv $X:\Omega\rightarrow\mathbb{X}$, $X(\omega)$ is the realization of uv $X$ corresponding to uncertainty $\omega\in \Omega$. For any two uvs $X$
and $Y$, the set $\range{X,Y}:=\{(X(\omega), Y(\omega)):
\omega\in\Omega \}\subseteq \range{X}\times \range{Y}$ is their joint range. For uv $X$, $\range{X}:=\{X(\omega):\omega\in\Omega \}$ denotes its marginal range.

The conditional range of uv $X$, conditioned on realizations of uv $Y$ belonging to the set $\mathcal{Y}$, is $\range{X|Y(\omega)\in \mathcal{Y}}:=\{X(\omega):\exists \omega\in\Omega  \mbox{ such that } Y(\omega)\in\mathcal{Y}\} \subseteq \range{X}.$ If $\mathcal{Y}=\{y\}$ is a singleton,  $\range{X|Y(\omega)\in \{y\}}=\range{X|Y(\omega)\in \mathcal{Y}}$ is replaced with $\range{X|Y(\omega)=y}$ or $\range{X|y}$ when it is clear from the context. For any two uvs $X$ and $Y$, we define the notation  $\range{Y|X}:=\{\range{Y|X(\omega)=x},\forall x\in\range{X}\}$. We sometimes refer to $\range{Y|X}$ as a non-stochastic channel as $\range{Y|X}$ fully characterizes the non-stochastic communication channel from $X$ to $Y$. In this paper, we only deal with discrete uvs possessing finite[Extension to countably infinite sets is straightforward with extra care when manipulating extended real numbers (i.e., infinity).] ranges.

Uvs $X_1$ and $X_2$ are unrelated if $\range{X_1|X_2(\omega)=x_2}=\range{X_1}$ for all $x_2\in\range{X_2}$ and vice versa.  Similarly, $X_1$ and $X_2$ are conditionally unrelated given $Y$ if $\range{X_1|X_2(\omega)=x_2,Y(\omega)=y}=\range{X_1|Y(\omega)=y}$ for all $ (x_2,y)\in\range{X_2,Y}$. Uvs $X_i$, $i=1,\dots,n$, are unrelated if $\range{X_1,\dots,X_n}= \range{X_1}\times \cdots \times \range{X_n}$ and conditionally unrelated given $Y$ if $\range{X_1,\dots,X_n|Y(\omega)=y} =\range{X_1|Y(\omega)=y}\times \cdots \times \range{X_n|Y(\omega)=y}$ for all $y\in\range{Y}$. Uvs $X$, $Y$, and $Z$ form a Markov (uncertainty) chain, denoted by $X-Y-{Z}$, if $X$ and $Z$ are unrelated conditioned on $Y$, that is, $\range{X|Z(\omega)=z,Y(\omega)=y} =\range{X|Y(\omega)=y}$ for all $(z,y)\in\range{Z,Y}.$ Note that, by symmetry of the definition of unrelated uvs, $X-Y-Z$ forms a Markov chain if and only if $Z-Y-X$ forms a Markov chain. We say $X_1-X_2-\cdots-X_n$ forms a Markov chain if $X_i-X_j-X_\ell$ forms a Markov chain for any $1\leq i {<} j {<} \ell\leq n$.

Non-stochastic entropy of uncertain variable $X$ is defined as $H_0(X):=\log(|\range{X}|).$ This is often described as the Hartley entropy [19, 16], which coincides with the Rényi entropy of order $0$ for discrete variables [20, 21].

Conditional (or relative) entropy of uv $X$ given $Y$ is given by
$H_0(X|Y):=\max_{y\in\range{Y}}\log(|\range{X|Y(\omega)=y}|)$. This is the Arimoto-Rényi conditional entropy of order $0$ [20, 22]. Based on this, we can define $I_0(X;Y):=H_0(X)-H_0(X|Y)$. This is equivalent to the $0$-mutual information [20, 23].

We end this section by presenting the definition of maximin information from non-stochastic information theory [16]. Consider uvs $X$ and $Y$. Any $x,x'\in\range{X}$ are $\range{X|Y}$-overlap connected if there exists a finite sequence of conditional ranges $\{\range{X|Y(\omega)=y_i}\}_{i=1}^n$ such that $x\in\range{X|Y(\omega)=y_1}$, $x'\in\range{X|Y(\omega)=y_n}$, and $\range{X|Y(\omega)=y_i}\cap \range{X|Y(\omega)=y_{i+1}}\neq \emptyset$ for all $i=1,\dots,n-1$. We say $\mathcal{A}\subseteq\range{X}$ is $\range{X|Y}$-overlap connected if all $x,x'\in\mathcal{A}$ are $\range{X|Y}$-overlap connected. Further, $\mathcal{A},\mathcal{B}\subseteq\range{X}$ are $\range{X|Y}$-overlap isolated if there does not exist $x\in\mathcal{A},x'\in\mathcal{B}$ such that $x,x'$ are $\range{X|Y}$-overlap connected.  An $\range{X|Y}$-overlap partition is a partition of $\range{X}$ such that  each member set is $\range{X|Y}$-overlap connected and any two member sets are $\range{X|Y}$-overlap isolated. There always exists a unique $\range{X|Y}$-overlap partition [16], which is denoted by $\range{X|Y}_\star$. The maximin information is $I_\star(X;Y):=\log(|\range{X|Y}_\star|).$
In [16], it is proved that  $|\range{X|Y}_\star|=|\range{Y|X}_\star|$ and thus $I_\star(X;Y)=I_\star(Y;X)$. The overlap partition captures common uv [24], an extension of common random variable [25] to uvs. This relationship explains the relationship between entropy of the common uv, which is equal to the maximin information, and the zero-error capacity [25, 16].

§ INFORMATION LEAKAGE IN BRUTE-FORCE GUESSING

Consider uv $X$ containing sensitive data $U$, which is interpreted as some attribute or feature of $X$ that is computable by some function $g:\range{X}\rightarrow\range{U}$, i.e., $U=g\circ X$. Note that, by construction, $|\range{U}|\leq |\range{X}|$. Let $Y$ be an observable uv that depends on $X$, e.g., $X$ and $Y$ are the input and output, respectively, of a (privacy-preserving) channel.[The conditional range $\range{Y|X}$ characterizes this channel, which can also be regarded as a non-stochastic privacy-preserving scheme.] These uvs forms a Markov chain $U-X-Y$. An adversary wants to guess $U$ correctly given $Y$. For instance, consider an example in which $X$ captures weight and height of an individual, and $U$ denotes body mass index. In such an example, insurance agencies might be interested in deducing the body mass index of an individual (due to its correlation with heart disease) based on publicly released data $Y$ while they do not have any particular interest in learning an individual's height and weight separately.

We assume that the adversary can guess the value of $U$ in a brute-force trial-and-error manner. That is, the adversary chooses a distinct element $u\in\range{U}$ each time and tests[We assume that the adversary has access to an oracle that can determine whether $U(\omega)$ is equal to $u$ (for a given $u\in\range{U}$) or not.] whether the actual value $U(\omega)$ equals $u$. The adversary repeats this procedure until the answer is `yes'. We consider the number of trials before the successful guess. Without observations of $Y$, the adversary should try at most $|\range{U}|$ times. However, with access to observation $Y(\omega)=y \in \range{Y}$, the actual value of $U(\omega)$ lies in the conditional range $\range{U|Y(\omega)=y}$ and therefore the maximum number of trials is $|\range{U|Y(\omega)=y}|$. Since the number of trials is proportional to the inference cost/effort of the adversary, the ratio $|\range{U}|/|\range{U|Y(\omega)=y}|$ captures the reduction in the adversary's maximum cost for guessing $U$ upon the observation $\range{U|Y(\omega)=y}$. This coincides with the definition of the information gain $\log(|\range{U}|/|\range{U|Y(\omega)=y}|)$ in [26], where $\log(|\range{U|Y(\omega)=y}|)$ denotes the `combinatorial' conditional entropy. The adversary's reduction in guessing cost can be interpreted as the information gained about uv $U$ from the observation $Y(\omega)=y$.

Note that the measure $\log(|\range{U}|/|\range{U|Y(\omega)=y}|)$ is also consistent with the stochastic brute-force guessing leakage $H_G(U) - \mathbb{E}_{Y}[H_G(U|Y(\omega)=y)]$
proposed in <cit.> for rvs $U$ and $X$. This measure is based on the guessing entropy[The guessing entropy $H_G(U)$ denotes the minimum average number of trials for guessing the realization of $U$. This results from the optimal brute-force guessing strategy of the adversary to pick $u_i\in \range{U}$, i.e., the element in $\range{U}$ with the $i$-th largest probability $\mathbb{P}\{U(\omega)=u_i\}$, at the $i$-th trial [27]. ] in [27] defined as $H_G(U):= \sum_{i=1}^{|\range{U}|} i \mathbb{P}\{U(\omega)=u_i\}$, where $(u_i)_{i=1}^{|\range{U}|}$ are such that $\mathbb{P}\{U(\omega)=u_1\} \geq \mathbb{P}\{U(\omega)=u_2\} \geq \dotsc \geq \mathbb{P}\{U(\omega)=u_{|\range{U}|}\}$.
Similarly, the conditional guessing entropy is $H_{G}(U | Y(\omega)=y) = \sum_{i=1}^{|\range{U|Y(\omega)=y}|} i \mathbb{P}\{U(\omega)=\tilde{u}_i|Y(\omega)=y\}$ for each $y \in \range{Y}$, where $(\tilde{u}_i)_{i=1}^{|\range{U|Y(\omega)=y}|}$ are such that $\mathbb{P}\{U(\omega)=\tilde{u}_1|Y(\omega)=y\} \geq \mathbb{P}\{U(\omega)=\tilde{u}_2|Y(\omega)=y\} \geq \dotsc \geq \mathbb{P}\{U(\omega)=\tilde{u}_{|\range{U|Y(\omega)=y}|}|Y(\omega)=y\}$. When there is no $\sigma$-field or probability measure over $\range{U}$, $H_{G}(U)$ and $H_G(U|Y(\omega)=y)$ reduce to the prior guessing cost $\log(|\range{U}|)$ and posterior guessing cost $\log(|\range{U|Y(\omega)=y}|)$, respectively, by replacing the expectation with the worst-case. To quantify the non-stochastic brute-force guessing leakage, we consider the difference between $\log(|\range{U}|)$ and the minimum guessing cost $\min_{y \in \range{Y}}\log(|\range{U|Y(\omega)=y}|)$ as follows.

For a given uv $U$, the non-stochastic leakage from $U$ to $Y$ is

\begin{align*}
\Leak(U\rightarrow Y)=&\log
\left(\frac{|\range{U}|}{\displaystyle\min_{y\in \range{Y}} |\range{U|Y(\omega)=y}|} \right)
\\
\max_{y\in \range{Y}} \log
\left(\frac{|\range{U}|}{|\range{U|Y(\omega)=y}|} \right).
\end{align*}

The measure $\Leak(U \rightarrow Y)$ quantifies the maximum reduction in the guessing cost of the adversary after observing $Y$, which indicates the most information gained by the adversary in the sense of [26]. This measure has been previously used as the non-stochastic information leakage in [28, 7] for privacy analysis, e.g., in the case of $k$-anonymity [28]. Hence, this definition provides an operative meaning to the non-stochastic information leakage and can be used as its interpretation for privacy analysis.

In the following proposition, we show that non-stochastic leakage satisfies the data-processing inequality. This implies that, for a given uv $X$ and a specified attribute $U$ of $X$, the leakage is non-increasing along cascading channels $\range{Y|X}$ and $\range{Z|Y}$. This is in line with axiom (R3.a) of an operational notion of information leakage in [5]. This is an important requirement as it shows that a curator does not need to worry about an increased risk incurred by any post processing after releasing outputs.

If Markov chain $U-X-Y-Z$ holds, $\Leak(U\rightarrow Z)\leq \Leak(U\rightarrow Y)$.

Note that

\begin{align*}
\range{U|Z(\omega)=z}
&=\bigcup_{y\in\range{Y}} \range{U|Z(\omega)=z,Y(\omega)=y}\\
&=\bigcup_{y\in\range{Y}:(y,z)\in\range{Y,Z}} \range{U|Y(\omega)=y},
\end{align*}

where the last equality follows from that $U-Y-Z$ is  a Markov chain, i.e., $U$ and $Z$ are unrelated given $Y$.
Notice that $y\in\range{Y}$ and $(y,z)\in\range{Y,Z}$ implies that $y\in\range{Y|Z(\omega)=z}$. As a result,

\begin{align} \label{eqn:proof:1}
\range{U|Z(\omega)=z}
&=\bigcup_{y\in\range{Y|Z(\omega)=z}} \range{U|Y(\omega)=y}.
\end{align}

Let $z^* \in \argmin_{z\in\range{Z}} |\range{U|Z(\omega)=z}|$. For any $y^*\in\range{Y|Z(\omega)=z^*}$, $\range{U|Y(\omega)=y^*} \subseteq \range{U|Z(\omega)=z^*} $ because of (<ref>). Hence,

\begin{align*}
\min_{y\in\range{Y}} |\range{U|Y(\omega)=y}|
&\leq |\range{U|Y(\omega)=y^*}|\\
&\leq |\range{U|Z(\omega)=z^*}|\\
\end{align*}

which, because of the monotonicity of the logarithm, gives rise to the inequality $\Leak(U\rightarrow Z)\leq \Leak(U\rightarrow Y)$.

The following result shows that the non-stochastic brute-force guessing leakage is a measure of relatedness between two uvs. In fact, the leakage is equal to zero if two uvs are unrelated. Evidently, the most private case arises from ensuring that $X$ and $Y$ are unrelated. In this case, the realizations of $Y$ do not provide any useful information about $X$ or its derivatives, e.g., $U$.  This is again in line with axiom (R3.b) of an operational notion of information leakage [5].

$ \Leak(U\rightarrow Y)\geq 0$ with equality if $X$ and $Y$ are unrelated.

The inequality follows from that $\range{U|Y(\omega)=y}\subseteq \range{U}$ and, as a a result, $|\range{U}|/|\range{U|Y(\omega)=y}|\geq 1$. If $X$ and $Y$ are unrelated, $U$ and $Y$ are unrelated too. Therefore, $\range{U|Y(\omega)=y}=\range{U}$. This shows that $\Leak(U\rightarrow Y)=0$.

For the Markov chain $U-X-Y$, the measure $\Leak(U \rightarrow Y)$ can be used to quantify the non-stochastic brute-force guessing leakage if we know attribute $U$ of $X$ that is targeted by the adversary. However, there are some real-world situations that we do not know a priori the intention of the adversary, i.e., the attribute $U$ of $X$ that the adversary is trying to infer. In some cases, more than one user may observe $Y$ and each user might be interested in guessing/estimating a different attribute of $X$. In these situations, it is required to consider the brute-force guessing leakage $\Leak(U \rightarrow Y)$ when the attribute $U$ varies. Therefore, we need to define a maximal non-stochastic guessing leakage. This is in-line with axiom (R2) in [5]. We consider such situations in the next section.

The maximal non-stochastic leakage from $X$ to $Y$ is defined as

\begin{align}\label{eqn:maximal_leakage}
\LeakS(X\rightarrow Y)=&\sup_{U \colon U-X-Y}\Leak(U\rightarrow Y),
\end{align}

where the supremum is taken over all functions $g:\range{X}\rightarrow\range{U}$ with $\range{U}$ containing finite arbitrary alphabets.

Now, we can show that maximal non-stochastic leakage admits axiom (R3) in the axiomatic approach to operational information leakage in [5]. That is, maximal non-stochastic leakage satisfies data processing inequality (post processing does not increase leakage), independence property (statistically independent outputs result in zero leakage), and additivity.

The following holds:

a) $\LeakS(X\rightarrow Y)\geq 0$;

b) $\LeakS(X\rightarrow Y)=0$ if and only if $X$ is unrelated to $Y$;

c) $\LeakS(X\rightarrow Y)\leq H_0(X)$ with the equality if $Y = X$;

$\LeakS(X\rightarrow Z)\leq \LeakS(X\rightarrow Y)$ if Markov chain $X-Y-Z$ holds;

e) If $(X_i,Y_i)$, $\forall i$, are unrelated, i.e., $(X_i,Y_i)$ and $(X_{i'},Y_{i'})$ are unrelated $\forall i\neq i'$, then $\LeakS((X_1,\dots,X_n)\rightarrow (Y_1,\dots,Y_n))
=\sum_{i=1}^n\Leak(X_i\rightarrow Y_i)$.

Now, we are ready to present a formula for computing the maximal non-stochastic leakage. This is done in the next proposition.

$\LeakS(X\rightarrow Y)=\log(|\range{X}| - \min_{y\in\range{Y}} |\range{X|Y(\omega)=y}| + 1)$.

The proofs of Propositions <ref> and <ref> are in Appendix <ref> and <ref>, respectively.

In Appendix <ref>, The function $g$ in (<ref>) constructs the most vulnerable attribute $U$ of uv $X$, which is determined by any ${y^* \in }\argmin_{y\in\range{Y}}|\range{X|Y(\omega)=y}|$.

The following example shows that the maximal non-stochastic brute-force guessing leakage is incurred when the function $g$ is highly corrected with the mapping $\range{Y|X}$.

[Majority Vote]
Let uncertain variable $X_i:\Omega\rightarrow\range{X_i}=\{0\text{-``no/disagree''},1\text{-``yes/agree''}\}$ denotes the vote of individual $i$. Assume that there are (finite) $n \in \mathbb{N}$ voters. Denote $X(\omega) = (X_i(\omega) \colon i \in \Set{1,\dotsc,n})$ the voting result. Let $Y(\omega)=\mathfrak{q}(X(\omega))$ be the majority vote function such that

\begin{equation}  \label{eq:MajorVote}
\mathfrak{q}(x) = \begin{cases} 0, & \displaystyle \sum_{i= 1}^n x_i < \frac{n}{2}, \\ 1, & \displaystyle \sum_{i= 1}^n x_i \geq \frac{n}{2}, \end{cases}
\end{equation}

for $x = (x_i \colon i \in \Set{1,\dotsc,n}) \in \Set{0,1}^n$.

Consider the following two attributes $U$.

In this example, we have set the base of logarithm to $2$.

Let $U=X_i$, i.e., the adversary is interested in an individual's vote. It can be seen that

\begin{align*}
\range{U|Y(\omega)=0}
\{0\}, & n=1, \\
\{0\}, & n=2, \\
\{0,1\}, & n\geq 3,
\end{cases}\\
\range{U|Y(\omega)=1}
\{0\}, & n=1, \\
\{0,1\}, & n=2, \\
\{0,1\}, & n\geq 3.
\end{cases}
\end{align*}

\begin{align}
\Leak(U\rightarrow Y)=& \nonumber
\log_2\hspace{-.02in}
\left(\frac{|\range{U}|}{\displaystyle\min_{y\in \range{Y}} |\range{U|Y(\omega)=y}|} \right)\\
\begin{cases}
1, & n=1, \\
1, & n=2, \\
0, & n\geq 3.
\end{cases}\label{eq:USingle}
\end{align}

The information leakage about the vote of each individual is zero if there are more than three voters. This is practically why democracy with secrete/confidential ballot is privacy preserving [29].

Let $U = X$, i.e., the adversary is interested in figuring out all the votes. We have

\begin{align*}
&=\left|\left\{ x \in \Set{0,1}^n \colon \sum_{i = 1}^{n} x_i < \frac{n}{2} \right\}\right| \\
&= \sum_{k=0}^{n_0} {n \choose k}, \\
&= \left|\left\{ x \in \Set{0,1}^n \colon \sum_{i = 1}^{n} x_i \geq \frac{n}{2} \right\}\right| \\
&=\sum_{k=n_0+1}^{n} {n \choose k}.
\end{align*}

\begin{align*}
= \left\lceil  \frac{n}{2} \right\rceil - 1 =
\begin{cases}
\displaystyle \frac{n-1}{2}, & n\mbox{ is odd},\\
\displaystyle \frac{n}{2}-1, & n\mbox{ is even}.
\end{cases}
\end{align*}

Then, $|\range{X|Y(\omega)=0}| - |\range{X|Y(\omega)=1}|<0$ if $n$ is odd and $|\range{X|Y(\omega)=0}| - |\range{X|Y(\omega)=1}|=0$ if $n$ is even.

\begin{align}
\Leak(U\rightarrow Y) &= \Leak(X\rightarrow Y)  \nonumber \\
&= \log_2 \left(\frac{|\range{X}|}{\min_{y\in \{0,1\}} |\range{X|Y(\omega)=y}|} \right) \nonumber \\
&= \log_2 \left(\frac{2^n}{ |\range{X|Y(\omega)=0}|} \right) \nonumber \\
&= n-\log_2 \left(\sum_{k=0}^{n_0} {n \choose k}\right). \label{eq:UAll}
\end{align}

For odd $n$, <cit.> implies that

\begin{align*}
\sum_{k=0}^{n_0} {n \choose k}=\sum_{k=0}^{n_0} {2n_0+1 \choose k}=2^{2n_0},
\end{align*}

and as a result $\Leak(U\rightarrow Y)=n-2n_0=1.$
For even $n$,

\begin{align*}
\sum_{k=0}^{n_0} {n \choose k}
&=\sum_{k=0}^{n_0} {2n_0+2 \choose k}\\
& \geq \sum_{k=0}^{n_0} {2n_0+1 \choose k}\\
& =2^{2n_0},
\end{align*}

and thus $\Leak(U\rightarrow Y)\leq n-2n_0=2.$ These derivations show that $\Leak(U\rightarrow Y) \in [0,2]$.

That is, $\Leak(U\rightarrow Y)$ is independent of $n$, even if $|\range{U}| = 2^n$ exponentially grows with $n$.

However, if we do not know the privacy-intrusive adversary' intention, i.e., which attribute $U$ is targeted, we should prepare for the worst-case privacy leakage.

To see the most vulnerable attribute, we follow (<ref>) to construct function

\begin{equation} \label{eq:HPF}
\begin{cases}
u^*, & x \in \range{X|Y(\omega)=0},\\
x, & x \in \range{X|Y(\omega)=1}.
\end{cases}
\end{equation}

The maximal (worst-case) non-stochastic brute-force leakage

\begin{align*}
\LeakS(X\rightarrow Y) &= \log_2 (|\range{X}| -\range{X|Y(\omega) = 0} + 1)\\
&= \log_2 \Big( 2^n - \sum_{k=0}^{n_o} {n \choose k} + 1 \Big)\\
&= \log_2 (|\range{X | Y(\omega)=1}| + 1),
\end{align*}

which is increasing in $n$.

Note that $g$ in (<ref>) is equivalent with the exact voting results only when no less than half of the users vote “yes/agree”.

This function is highly related to $\mathfrak{q}$, the majority vote function that determines $\range{Y|X}$, and therefore generates the most vulnerable attribute of $X$.

Here, $g$ is only related to but is not exactly $\range{Y|X}$. We will show in Section <ref> that the attribute determined exactly by $\mathfrak{q}$ maximizes another worst-case non-stochastic guessing leakage, the maximin information.

Fig. <ref> shows the non-stochastic brute-force guessing leakage $\Leak(U \rightarrow Y)$ for $U$ being an individual's vote and all votes, and the maximal non-stochastic brute-force leakage $\LeakS(X \rightarrow Y)$  versus the number of voters. Evidently, the most destructive malicious inference is not exhaustively guessing all individuals' votes, but inferring an uncertainty that is highly related to the majority voting results.

The non-stochastic brute-force guessing leakage $\Leak(U \rightarrow Y)$ and the maximal non-stochastic brute-force guessing leakage $\LeakS(X \rightarrow Y)$ vs. the number of voters $n$ in the majority vote in Example <ref>. Two cases for $U$ in $\Leak(U \rightarrow Y)$ are considered. First, $U = X_i$ when the adversary tries to exhaustively guessing user $i$'s vote. Then, $U = X = (X_i \colon i \in \Set{1,\dotsc, n})$ when the adversary tries to exhaustively guess all votes.

$\LeakS(X\rightarrow Y)$ is not symmetric in general. In most cases, $\LeakS(X\rightarrow Y) \neq \LeakS(Y\rightarrow X)$. For example, for uvs $X$ and $Y$ with joint range $\range{X,Y}=\{(x_1,y_1),(x_2,y_1),(x_3,y_2)\}$, we have  $\LeakS(X\rightarrow Y)=\log(3)\neq \log(2)=\LeakS(Y\rightarrow X)$.

Most of the existing information leakage measures are asymmetric, e.g., the (stochastic) maximal leakage (Sibson mutual information) [5], $\alpha$-leakage [6],  [31].

That is, the quantity of information depends on the direction of the data flow.

§ NON-STOCHASTIC IDENTIFIABILITY

We define non-stochastic identifiability by requiring that the ratio of the cardinality of the set of compatible realization of uv $X$ with access to the measurements of uv $Y$ over the cardinality of the set of compatible realization of uv $X$ without this auxiliary information is lower bounded by an exponential of the privacy budget. This implies that access to the realizations of $Y$ does not significantly reduce the cardinality of the set of possibilities that must be tested for guessing the realization of $X$.

This definition is consistent with stochastic identifiability in <cit.>, <cit.> and <cit.>, which require that the posterior distribution (instead of the conditional range) to remain similar with and without access to the measurements.
For attribute $U$, the prior range $\range{U}$ and posterior range $\range{U|Y}$ denote the adversary's uncertainty about $U$ before and after observing $Y$, respectively, and their logarithmic difference captures non-probabilistic identifiability.

For $\epsilon > 0$, a mapping $\mathfrak{M}$ that generates $Y=\mathfrak{M}\circ X$ is $\epsilon$-identifiable on attribute $U$ if

\begin{align} \label{eq:NSInd}
\Leak(U \rightarrow Y) = \log \left(\frac{\range{U}}{\min_{y \in \range{Y}}\range{U | Y(\omega) = y}}\right) \leq \epsilon,
\end{align}

for all $y \in \range{Y}$.

In this definition, (<ref>) ensures $\log ({\range{U}}/{\range{U | Y(\omega) = y}}) \leq \epsilon, \forall y \in \range{Y}$, which corresponds to the membership privacy $\log({p(u|y)}/{p(u)}) \leq \epsilon, \forall u, y$ in <cit.> for the probability space.

As in stochastic notions of privacy, we refer to $\epsilon$ in the non-stochastic identifiability as the privacy budget, i.e., by decreasing $\epsilon$, we ensure a higher level of privacy (cf., differential privacy [35] and identifiability [32]). This is intuitively because, by decreasing the privacy budget, the size of the set $\range{U|Y(\omega)=y}$ increases and thus guessing the actual realization of uv $U$ becomes harder.

§.§ Identifiability and $\Leak(X \rightarrow Y)$

Identifiability is closely related the maximal non-stochastic brute-force guessing leakage.

It can be seen from the corresponding definitions that  $\Leak(X \rightarrow Y)$ and $\Leak_* (X \rightarrow Y)$ are both decreasing functions of $\min_{y \in \range{Y}}  \range{X | Y(\omega) = y}$. Also, for the natural logarithm, they can express in terms of each other by

\begin{equation} \label{eq:LeakLeakS}
e^{\LeakS(X \rightarrow Y)}  + |\range{X}| e^{-\Leak(X \rightarrow Y)} = |\range{X}| + 1.
\end{equation}

Therefore, $\LeakS(X \rightarrow Y)$ is increasing in $\Leak(X \rightarrow Y)$ and vice versa; see
more on this relationship in Appendix <ref>. Thus, imposing a budge on either measure necessarily bounds the other.

For any $\epsilon$-identifiable mapping $\mathfrak{M}$, $\LeakS(X\rightarrow Y)\leq \log(|\range{X}|(1-e^{-\epsilon}) + 1)$.

The proof follows from (<ref>) that
$\LeakS(X\rightarrow Y)
=\log(|\range{X}| - \min_{y\in\range{Y}} |\range{X|Y(\omega)=y}| + 1)
\leq \log(|\range{X}|(1-e^{-\epsilon}) + 1)$.

Corollary <ref> shows that, as expected, the maximal non-stochastic brute-force guessing leakage $\LeakS(X\rightarrow Y)$ goes to zero as the privacy budget approaches zero. By increasing the privacy budget $\epsilon$, however, we increase the bound on the maximal non-stochastic brute-force guessing leakage $\LeakS(X\rightarrow Y)$ and therefore more private information could be potentially leaked.

§ BRUTE-FORCE TO ONE-SHOT GUESS

In the previous sections, we considered a brute-force guessing adversary that can potentially check all the possibilities of the private information in $\range{U|Y(\omega)=y}$ that are compatible with the available outputs $Y(\omega)=y$ of the channel $\range{Y|X}$ to find the actual private realization. In this section, we restrict ourselves to one-shot guesses. We first analyze the non-stochastic case and its relationship with the non-stochastic brute-force guessing.

§.§ Non-Stochastic One-Shot Guessing

Let us consider an adversary with only a single opportunity for guessing the private realization of uv $U$ by observing the realization of uv $Y$. For instance, consider the problem of guessing a person's password based on side-channel information (e.g., inter-keystroke delay as in [5]) while the system locks immediately after one wrong guess. Therefore, the adversary is interested in finding the largest amount of information that can be deduced correctly with one guess. This happens when $|\range{U|Y(\omega)=1}|=1$ for all $y\in\range{Y}$. In the following proposition, we show that the maximum information is the largest amount of information can be leaked to such an adversary. We further relate this notion of leakage to maximal non-stochastic leakage with brute-force guessing.

For uvs $X$ and $Y$,

\begin{align*}
\hspace{-.1in}
\sup_{
\scriptsize
\begin{array}{c}
\scriptsize U\colon U-X-Y, \\
\scriptsize |\range{U|Y(\omega)=y}|=1, \\
\forall y\in\range{Y}
\end{array}
\hspace{-.1in}\Leak(U\rightarrow Y)
\leq
\LeakS(X\rightarrow Y),
\end{align*}

where the supremum is taken over  all $g:\range{X}\rightarrow\range{U}$ such that $|\{g(x) \colon x \in \range{X | Y(\omega)=y}\}| =  |\range{U|Y(\omega)=y}|=1$.

The second inequality trivially follows from that increasing the search domain of the supremum operator results in a larger value. Therefore, we only focus on the first inequality. Note that $|\range{U|Y(\omega)=y}|=1$ implies that there exists $f$ such that $U=f(Y)$. Therefore, $U=f(Y)=g(X)$. Following Lemma 1 in [25], we know that there exists a function $h$ such that $U=h(X\wedge Y)$, where $X\wedge Y$ is the common variable in the sense of [25] defined for uncertain variables (instead of random variables) following the approach of [24]. Therefore,
$\Leak(U\rightarrow Y)=H_0(U)\leq H_0(X\wedge Y)=I_\star(X;Y).$
Since this inequality holds for all $U$ such that $\range{U|Y(\omega)=y}=1$, we get

\begin{align*}
\sup_{
\scriptsize
\begin{array}{c}
\scriptsize U\colon U-X-Y, \\
\scriptsize |\range{U|Y(\omega)=y}|=1, \\
\forall y\in\range{Y}
\end{array}
}\Leak(U\rightarrow Y)\leq
\end{align*}

On the other hand, for $U^* = X \wedge Y$,

\begin{align*}
\sup_{
\scriptsize
\begin{array}{c}
\scriptsize U\colon U-X-Y, \\
\scriptsize |\range{U|Y(\omega)=y}|=1, \\
\forall y\in\range{Y}
\end{array}
}\hspace{-.2in}\Leak(U\rightarrow Y)
\geq \Leak(U^*\rightarrow Y)=I_\star(X;Y).
\end{align*}

Combining these inequalities concludes the proof.

It was recently proved that the maximin information $I_\star(X;Y)$ is equal to the entropy of the common uncertain variable between uvs $X$ and $Y$ [18]. Common uncertain variable is defined similar to common random variable in [25] and is the largest uncertain variable that can be directly computed using both $X$ and $Y$. The “largest” uncertain variable refers to that any other uncertain variable that can be directly computed using both $X$ and $Y$ can also be written in terms of the common uncertain variable. The definition of common uncertain variable paved the way to define perfect privacy [18]. Given this relationship, Proposition <ref> demonstrates the relationship between common uncertain variable and non-stochastic one-shot guessing.

[Majority Vote (Cont.)]
For the majority voting function in Example <ref>, the maximin information is

\begin{align}
&\range{U_\star|X(\omega) = x}  \nonumber \\
& \ = \argmax_{U} \Big\{ \Leak(U \rightarrow Y) \colon U-X-Y, \range{U|Y(\omega)=y}=1 \Big\} \nonumber\\
& \ = \begin{cases}
\Set{a} & x \in \range{X | Y(\omega) = 0}\\
\Set{b} & x \in \range{X |Y(\omega)= 1}
\end{cases} \label{eq:IStarEx}
\end{align}

This is exactly the majority vote function $\mathfrak{q}$ in (<ref>). Therefore, an adversary can perfectly estimate $U^*$ by observing $Y$. This is however not a privacy breach as $Y$ is already disclosed. Also, (<ref>) is independent of $n$ and thus the maximin information is $I_\star(X;Y) = \log_2 (2)  = 1$ for all $n \in \mathbb{N}$. See Fig. <ref>.

Following Proposition <ref> and [16], the zero-error capacity of any memoryless uncertain channel satisfies $C_0=\sup_{\range{X}\subseteq\mathbb{X}}I_\star (X;Y)\leq  \sup_{\range{X}\subseteq\mathbb{X}} \LeakS(X\rightarrow Y).$

Therefore, based on Corollary <ref>, the zero-error capacity of any memoryless $\epsilon$-identifiable channel is upper bounded by $\log(|\mathbb{X}|(1-2^{-\epsilon}) + 1)$, where $|\mathbb{X}|$ is the number of the input alphabets.

This constraints dynamical systems that can be estimated or stabilized through privacy-preserving communication channels [16, 36].

In the next subsection, we consider one-shot guessing in the stochastic sense of [5] and investigate its relationship with the maximal non-stochastic leakage with brute-force guessing.

§.§ Maximal Stochastic Leakage

We can recreate the stochastic framework for information leakage in [5] by endowing all the uncertain variables in this paper with a measure.

For jointly distributed rvs $X$ and $Y$, the maximal stochastic leakage from $X$ to $Y$ is given by

\begin{align*}
\widetilde{\LeakS}(X&\rightarrow Y)\\
\sup_{U\colon U-X-Y} \log\left( \frac{\displaystyle\mathbb{E}\left\{\max_{u \in \range{U}} \mathbb{P}\{U=u|Y=y\}\right\}}{\displaystyle\max_{u\in\range{U}}\mathbb{P}\{U=u\}}\right),
\end{align*}

where supremum is taken over all random variables (rvs) $U$ taking values in finite arbitrary alphabets. It was shown in [5] that

\begin{align*}
\widetilde{\LeakS}(X\rightarrow Y)
&=I_{\infty} (X;Y),
\end{align*}

where $I_{\infty}$ is the Sibson mutual information $I_{\alpha}$ in the order $\alpha \rightarrow \infty$ [37, 23]. Note the fact that $\{x\colon \mathbb{P}\{X=x\}>0\} = \range{X}$.

0.7     0.7
The privacy-utility tradeoff: The maximal non-stochastic brute-force guessing leakage $\LeakS(X \rightarrow \hat{Y})$ (left) and maximin information $I_\star(X;\hat{Y})$ (right) versus the maximal distortion between $Y$ and $\hat{Y}$. The plots are obtained for the experiment in Section <ref> on the heart disease dataset from the UCI machine learning repository [38]. Here, $\hat{Y}$ denotes the quantized $Y$ by (<ref>), where the step size $\delta$ varies between $1$ a and $50$. The maximum distortion refers to the largest $\ell_1$ distance between the actual value $y$ and the centroid $\hat{c}(y)$.

It is shown in <cit.> that the worst-case maximal stochastic leakage occurs when the probability becomes deterministic:

\begin{align*}
\sup_{p(y|x)} \widetilde{\LeakS}(X\rightarrow Y)
& =  \min \Set{ H_0(X), H_0(Y)} \\
& = \min \Set{ |\range{X}|, |\range{Y}| }
\end{align*}

In non-stochastic case, we have
$ \sup_{\range{Y|X}} \LeakS (X \rightarrow Y) = H_0(X) $
$ \sup_{\range{Y|X}}I_\star(X;Y) = \min \{ H_0(X), H_0(Y) \}$.

\begin{align}
\sup_{p(y|x)} \widetilde{\LeakS}(X\rightarrow Y)
&=  \sup_{\range{Y|X}}I_\star(X;Y) \nonumber  \\
&\leq \sup_{\range{Y|X}} \LeakS (X \rightarrow Y) . \label{eq:RelationLeak}
\end{align}

The equality holds when $\range{X} \leq \range{Y}$.

The privacy-utility tradeoff: The maximal stochastic leakage $\widetilde{\LeakS}(X\rightarrow Y)$ vs. the maximal distortion between $Y$ and $\hat{Y}$. The plots are obtained for the experiment in Section <ref> on the heart disease dataset from the UCI machine learning repository [38].

§ EXPERIMENT

In the the UCI machine learning repository [38], the heart disease dataset was created by the Hungarian Institute of Cardiology, Budapest. It records $293$ patients' data of $76$ attributes for the purpose of identifying the presence of heart disease.

We extract three attributes in this experiment. We use the column `age' for $X$ while considering two attributes for $Y$. First, we use $Y=$“resting blood pressure (in mm Hg)” and then switch to $Y=$“serum cholesterol (mg/dl)”.

Let $Y$ be quantized before being published.  Adopting a uniform quantizer $\hat{c}$ such that

\begin{equation}  \label{eq:Quantizer}
\hat{c}(y)  = \delta   \Big(  \Big\lfloor \frac{y}{\delta}  \Big\rfloor  + \frac{1}{2} \Big),
\end{equation}

where $\delta>0$ refers to the step size or resolution. The quantized $Y$ is denoted by $\hat{Y}$ with the range $\range{\hat{Y}} = \Set{\hat{c}(y) \colon y \in \range{Y} }$.

The maximum distortion $\max_{y \in \range{Y}}  |y-\hat{c}(y)|$, capturing the loss in data utility, grows with the step size $\delta$.

We observe private information leakage from $X$ to the quantized data $\hat{Y}$.
While varying $\delta$ from $1$ to  $50$, we can compute the maximal non-stochastic brute-force guessing leakage $\Leak( X \rightarrow \hat{Y})$ and the maximin information $I_\star(X;\hat{Y})$ for each value of $\delta$ and plot them as functions of the maximum distortion in Fig. <ref>.

A tradeoff between the privacy and data utility can be seen. Both $\Leak(X \rightarrow \hat{Y})$ and $I_\star(X ; \hat{Y})$  decrease as the maximum distortion increases, i.e., the released data $\hat{Y}$ is more private as the step size of the quantization increases.

As expected from Proposition <ref>, $\Leak(X \rightarrow \hat{Y})$ is greater than $I_\star(X ; \hat{Y})$.

In Fig. <ref>, we also plot the privacy-utility tradeoff between the maximal stochastic leakage $\widetilde{\LeakS}(X \rightarrow \hat{Y})$ and the  maximum distortion. As seen from (<ref>), $\widetilde{\LeakS}(X \rightarrow \hat{Y})$ is upper bounded by $I_\star(X ; \hat{Y})$.

Note, in this experiment, $I_\star(X ; \hat{Y}) \approx \min \Set{H_0(X), H_0(\hat{Y})}$.

§ CONCLUSIONS AND FUTURE WORK

We developed an interpretable notion of non-stochastic information leakage based on guessing in a non-stochastic framework. We considered brute-force guessing in which an adversary can potentially check all the possibilities of the private information that are compatible with the available outputs to find the actual private realization. The ratio of the worst-case number of guesses for the adversary in the presence of the output and in the absence of it captures the reduction in the adversary's guessing  complexity and is thus used as a measure of information leakage. We computed the maximal non-stochastic leakage over all sensitive attributes that could be targeted by the adversary and compared it with non-stochastic identifiability, maximin information, and stochastic maximal leakage.

One interesting finding in Example <ref> is that the maximal leakage is not incurred when the adversary tries to infer the exact value of $X$, but some function of $X$ that is highly related to the conditional range $\range{X|Y}$ and can be determined once $\range{Y|X}$ is fixed. An interesting question is whether this is the case in the stochastic setting and, if so, characterize the worst-case attribute, e.g., some expression in the form of (<ref>). In stochastic leakage studies in [5, 6], the worst-case leakage is shown to be determined by the randomization scheme. However, the worst-case attribute has not been identified.

It is also of interest to determine whether the maximal non-stochastic brute-force guessing leakage derived in this paper and $\alpha$-leakage proposed in [6] can be both formulated by Rényi measure. The order $\alpha$ in Rényi entropy varies from $0$ to $\infty$, where $\alpha = 0$ refers to a non-stochastic measure. But, the $\alpha$-leakage in [6] is only defined in $\alpha \in [1, \infty)$ based on the Arimoto mutual information. Recall that the Arimoto mutual information is defined in the whole range $\alpha \in [0,\infty)$. The question is how $\LeakS(X \rightarrow Y)$ relates to the case $(\alpha=)0$-leakage and whether the Arimoto mutual information also has a similar interpretation as in the information leakage in $\alpha \in [0,1)$.

Another direction for future research could be to extend this definition to a dynamic framework with continual observations. In this case, we get

\begin{align*}
\end{align*}

where $W_t$ and $V_t$ are mutually unrelated uvs. In this case, it would be interesting to understand the behaviour of $\LeakS((X_t: t\in\{1,\dots,k\}) \rightarrow (Y_t: t\in\{1,\dots,k\}))$ as a function of time and whether it can be written in recursive form. This enables us to understand private information leakage in time-varying environments.

§ FUNDAMENTAL PROPERTIES OF INFORMATION LEAKAGE

As outlined in [5], an operational measure of information leakage $\Leak(X \rightarrow Y)$ should hold the following basic properties:

* Cogent operational interpretation: The leakage measure should quantify the adversary's difficulty in inferring the private/sensitive data;

* Minimum assumption: Assumptions about the adversary should be minimized;

* Satisfying the axiomatic properties:

* data processing inequality: $\Leak(X \rightarrow Y) =\min \{\Leak(X \rightarrow Z), \Leak(Y \rightarrow Z)\}$ for any $X, Y, Z$ forming a Markov chain;

* independence: $\Leak(X \rightarrow Y) = 0$ if $X \perp Y$;

* additivity: $\Leak(X^n \rightarrow Y^n) = n \Leak(X \rightarrow Y)$ for independently and identically distributed $(X^n,Y ^n)$.

* Accordance with intuition: The measure should be able to identify the severity of the information leakage.

§ PROOF OF PROPOSITION <REF>

Proof of (a): Note that $\Leak(U \rightarrow Y)\geq 0$ for all $U$ such that $U-X-Y$ is a Markov chain; see Proposition <ref>.
Taking maximum of both sides of this inequality results in (a).

Proof of (b): According to Proposition <ref>, for unrelated $X$ and $Y$, $\Leak(U \rightarrow Y) = 0$ for all $U$ such that $U-X-Y$ is a Markov chain. Hence, $\LeakS(X \rightarrow Y) = 0$. Now, we prove the reverse. Assume that $\LeakS(X \rightarrow Y) = 0$. This implies that $\Leak(U \rightarrow Y) = 0$ for all $U$ such that $U-X-Y$ is a Markov chain. For the special case that $U = X$,

$\Leak(U \rightarrow Y)=\Leak(X \rightarrow Y)={\max_{y\in\range{Y}} \log (|\range{X}|/ |\range{X|Y(\omega)=y}|)} = 0$ and hence we must have $|\range{X|Y(\omega)=y}| = |\range{X}|$
for all $y\in\range{Y}$. Noting that $\range{X|Y(\omega)=y}\subseteq\range{X}$ and therefore $|\range{X|Y(\omega)=y}| = |\range{X}|$ implies that $\range{X|Y(\omega)=y}= \range{X}$. Hence, $X$ and $Y$ must be unrelated.

Proof of (c): Notice that we have $\Leak(U\rightarrow Y)=\max_{y\in \range{Y}} \log
\left(|\range{U}|/|\range{U|Y(\omega)=y}|\right)\leq \log(|\range{U}|)$ because $|\range{U|Y(\omega)=y}|\geq 1$. Further, we have $|\range{U}|\leq |\range{X}|$. Hence, $\Leak(U\rightarrow Y)\leq \log(|\range{X}|)=H_0(X)$ for all $U$. Taking maximum of left hand side of this inequality over all $U$ results in (c). For $Y=X$, $\Leak(U\rightarrow Y)={ \Leak(U\rightarrow X) =}\max_{x\in \range{X}} \log
\left(|\range{U}|/|\range{U|X(\omega)=x}|\right)$. Note that $\range{U|X(\omega)=x}=\{g(x)\}$ is a singleton and, as a result, $|\range{U|X(\omega)=x}|=1$. This implies that $\Leak(U\rightarrow Y)=|\range{U}|$. Further, $|\range{U}|\leq |\range{X}|$ with equality achieved if $U=X$. Thus,
$\LeakS(X\rightarrow Y)=\sup_{U\colon U-X-Y}\Leak(U\rightarrow Y)=H_0(X).$

Proof of (d): For $U$ that holds Markov Chain $U-X-Y-Z$, we have $\Leak(U\rightarrow Y) \geq \Leak(U\rightarrow Z)$. Taking maximum of both sides of this inequality results in (d).

Proof of (e): We have $\Leak((U_i)_{i=1}^n\rightarrow (Y_i)_{i=1}^n)=\sum_{i=1}^n \Leak(U_i\rightarrow Y_i)$ if $(U_i,X_i,Y_i)$, $\forall i$, are unrelated [39]. Note that, by definition, $(U_i,X_i,Y_i)$, $\forall i$, are unrelated if $(X_i,Y_i)$, $\forall i$, are unrelated. Taking maximum from both sides of this equality over $(U_i)_{i=1}^n$, such that $(U_i)_{i=1}^n-(X_i)_{i=1}^n-(Y_i)_{i=1}^n$ forms a Markov chain, proves (e).

§ PROOF OF PROPOSITION <REF>

We start by proving that $\LeakS(X\rightarrow Y)\leq \log(|\range{X}| - \min_{y\in\range{Y}} |\range{X|Y(\omega)=y}| + 1)$. To do so, we need to prove that, $\forall y\in\range{Y}$,

\begin{align}\label{eqn:middle_result}
|\range{X}| - |\range{U}| \geq |\range{X|Y(\omega)=y}| - |\range{U|Y(\omega)=y}|.
\end{align}

This is done by reductio ad absurdum. Assume that (<ref>) does not hold for all $y\in\range{Y}$. Therefore, there must exists $y\in\range{Y}$ such that

\begin{align} \label{eqn:reductio_ad_absurdum}
|\range{X}| - |\range{U}| < |\range{X|Y(\omega)=y}| - |\range{U|Y(\omega)=y}|,
\end{align}

Subtracting $|\range{U}\setminus \range{U|Y(\omega)=y}|$ from both sides of (<ref>) results in

\begin{align*}
|\range{X}| - |\range{U}|-|\range{U}&\setminus \range{U|Y(\omega)=y}| \\
<& |\range{X|Y(\omega)=y}| - |\range{U|Y(\omega)=y}|\\
&-|\range{U}\setminus \range{U|Y(\omega)=y}|\\
=& |\range{X|Y(\omega)=y}| - |\range{U}|,
\end{align*}

where the equality follows from that $|\range{U}|=|\range{U|Y(\omega)=y}|+|\range{U}\setminus \range{U|Y(\omega)=y}|$ because $(\range{U}\setminus \range{U|Y(\omega)=y})\cap \range{U|Y(\omega)=y}=\emptyset$ and $(\range{U}\setminus \range{U|Y(\omega)=y})\cup \range{U|Y(\omega)=y}=\range{U}$. Therefore, it must be that

\begin{align*}
|\range{X}|-|\range{U}\setminus \range{U|Y(\omega)=y}|< |\range{X|Y(\omega)=y}|.
\end{align*}

or equivalently

\begin{align*}
|\range{X}|- |\range{X|Y(\omega)=y}|<|\range{U}\setminus \range{U|Y(\omega)=y}|.
\end{align*}

Because $(\range{X}\setminus\range{X|Y(\omega)=y})\cap \range{X|Y(\omega)=y}=\emptyset$ and ${\range{X}=}(\range{X}\setminus\range{X|Y(\omega)=y})\cup \range{X|Y(\omega)=y}$, we have $|\range{X}|=|\range{X}\setminus\range{X|Y(\omega)=y}|+|\range{X|Y(\omega)=y}|$.

Therefore, it must be that

\begin{align} \label{eqn:middle_result:1}
|\range{X}\setminus\range{X|Y(\omega)=y}|<|\range{U}\setminus \range{U|Y(\omega)=y}|.
\end{align}

On the other hand, we have

\begin{equation}
\begin{aligned} \nonumber
&|\range{U}\setminus \range{U|Y(\omega)=y}| \\
& \qquad\quad = \big| \{g(x) \colon x \in \range{X} \} \setminus \{g(x) \colon x \in \range{X|Y(\omega)=y}\} \big| \\
& \qquad\quad  \leq \big| \{g(x) \colon x \in \range{X} \setminus \range{X|Y(\omega)=y} \} \big| \\
& \qquad\quad \leq \big| \range{X} \setminus \range{X|Y(\omega)=y} \big|,
\end{aligned}
\end{equation}

which contradicts (<ref>). Thus, (<ref>) must be valid for all $y\in\range{Y}$.

Using (<ref>), we get

\begin{equation} \nonumber
\begin{aligned}
\frac{|\range{U}|}{|\range{U|Y(\omega)=y}|}
%&\leq \frac{|\range{X}| - |\range{X|Y(\omega)=y}| + |\range{U|Y(\omega)=y}|}{|\range{U|Y(\omega)=y}|} \\
& \leq \frac{|\range{X}| - |\range{X|Y(\omega)=y}|}{|\range{U|Y(\omega)=y}|} + 1 \\
& \leq |\range{X}| - |\range{X|Y(\omega)=y}| + 1, \; \forall y\in\range{Y},
\end{aligned}
\end{equation}

where the last inequality holds because

\begin{align}
&=\left|\bigcup_{x\in\range{X|Y(\omega)=y}}\range{U|X(\omega)=x}\right|\geq 1.\label{eqn:proof:3}
\end{align}

Using $y^* \in \argmin_{y\in\range{Y}} |\range{U |Y(\omega)=y}|$, we get

\begin{align}
\Leak(U\rightarrow Y) &= \log\left( \frac{|\range{U}|}{|\range{U|Y(\omega)=y^*}|}\right)  \nonumber\\
& \leq \log (|\range{X}| - |\range{X|Y(\omega)=y^*}| + 1) \nonumber\\
& =\log (|\range{X}|\hspace{-.03in} -\hspace{-.03in} \min_{y\in\range{Y}}|\range{X|Y(\omega)=y}| + 1).\label{eq:LUBaux}
\end{align}

Since inequality (<ref>) holds for all $U$, we have the proved upper bound.

Now, we continue by proving the lower bound that $\LeakS(X\rightarrow Y)\geq \log(|\range{X}|-\min_{y\in\range{Y}}|\range{X|Y(\omega)=y}|+1)$. Select an arbitrary $y^*\in \argmin_{y\in\range{Y}}|\range{X|Y(\omega)=y}|$. Let us define two sets $\mathcal{X}_1:=\range{X|Y(\omega)=y^*}$ and $\mathcal{X}_2:=\range{X}\setminus\mathcal{X}_1$. Define

$g:\range{X}\rightarrow\range{U}$ with $\range{U}=\mathcal{X}_2\cup\{u^*\}$ as

\begin{align} \label{eq:WorstCaseAttri}
\begin{cases}
u^*, & x\in\mathcal{X}_1,\\
x, & x\in\mathcal{X}_2.
\end{cases}
\end{align}

Note that, by construction, $|\range{U|Y(\omega)=y^*}|=|\{u^*\}|=1$ and $|\range{U|Y(\omega)=y}|=|g(\range{X|Y(\omega)=y})|\geq 1$ for all $y\in\range{Y}\setminus\{y^*\}$. Hence, $\min_{y\in\range{Y}} |\range{U|Y(\omega)=y}|=1$. Therefore,

\begin{align*}
\LeakS(X\rightarrow Y)
&\geq \Leak(U\rightarrow Y)\\
&=\log\left( \frac{|\range{U}|}{ \displaystyle\min_{y \in \range{Y}} |\range{U|Y(\omega)=y}|}\right) \\
&=\log(|\range{X}\setminus \range{X|Y(\omega)=y^*}|+1)\\
\end{align*}

This concludes the proof.

§ $\LEAKS(X \RIGHTARROW Y)$ AND $\LEAK(X \RIGHTARROW Y )$

While Corollary <ref> shows that the maximal non-stochastic guessing leakage $\LeakS(X \rightarrow Y)$ is upper bounded by the privacy budget $\epsilon$ for the non-stochastic identifiability $\Leak(X \rightarrow Y)$, we can show the more general result that $\Leak(X \rightarrow Y)$ is monotonic in $\LeakS(X \rightarrow Y)$; see (<ref>).

For the Hungarian heart disease dataset used in Section <ref>, we can plot $\Leak(X \rightarrow Y)$ vs $\LeakS(X \rightarrow Y)$ for different quantization levels as in Fig. <ref>. The logarithm here is in base of $2$. The plot aligns with (<ref>), i.e.,  $\Leak(X \rightarrow Y) = \log_2 ({|\range{X}|}/{|\range{X}| + 1 - 2^{\LeakS(X \rightarrow Y)}})$. We can see that $\Leak(X \rightarrow Y)$ increases with $\LeakS(X \rightarrow Y)$.

The identifiability $\Leak(X \rightarrow Y)$ on $X$ as a function of the maximal non-stochastic brute-force guessing leakage $\LeakS(X \rightarrow Y)$ for the heart disease dataset  in the UCI machine learning repository [38]: $Y =$“blood pressure" and $Y = $“cholesterol".

[1]
F. Farokhi and N. Ding, “Measuring information leakage in non-stochastic
brute-force guessing,” in Proc. IEEE Inf. Theory Workshop, Riva del
Garda, Italy, 2021, pp. 1–5.

[2]
S. Yu, “Big privacy: Challenges and opportunities of privacy study in the age
of big data,” IEEE Access, vol. 4, pp. 2751–2763, Jun. 2016.

[3]
M. Jensen, “Challenges of privacy protection in big data analytics,” in
Proc. IEEE Int. Congress Big Data, Santa Clara, CA, 2013, pp.

[4]
I. Wagner and D. Eckhoff, “Technical privacy metrics: A systematic survey,”
ACM Comput. Surv., vol. 51, no. 3, pp. 1–38, Jun. 2018.

[5]
I. Issa, A. B. Wagner, and S. Kamath, “An operational approach to information
leakage,” IEEE Trans. Inf. Theory, vol. 66, no. 3, pp. 1625–1657,
Dec. 2020.

[6]
J. Liao, O. Kosut, L. Sankar, and F. P. Calmon, “A tunable measure for
information leakage,” in Proc. IEEE Int. Symp. Inf. Theory, Vail, CO,
2018, pp. 701–705.

[7]
N. Ding and F. Farokhi, “Developing non-stochastic privacy-preserving policies
using agglomerative clustering,” IEEE Trans. Inf. Forensics Secur.,
vol. 15, pp. 3911–3923, 2020.

[8]
S. Linsenmayer and F. Allgower, “Stabilization of networked control systems
with weakly hard real-time dropout description,” in Proc. IEEE 56th
Annu. Conf. Decis. Control, 2017, pp. 4765–4770.

[9]
A. Teixeira, D. Pérez, H. Sandberg, and K. H. Johansson, “Attack models
and scenarios for networked control systems,” in Proc. 1st Int. Conf.
High Confidence Networked Syst., 2012, pp. 55–64.

[10]
R. Bild, K. A. Kuhn, and F. Prasser, “SafePub: A truthful data anonymization
algorithm with strong privacy guarantees,” Proc. Priv. Enhancing
Technol., vol. 2018, no. 1, pp. 67–87, 2018.

[11]
G. Poulis, A. Gkoulalas-Divanis, G. Loukides, S. Skiadopoulos, and
C. Tryfonopoulos, “SECRETA: A tool for anonymizing relational, transaction
and RT-datasets,” in Medical Data Privacy Handbook,
A. Gkoulalas-Divanis and G. Loukides, Eds.1em plus 0.5em minus
0.4emSpringer International Publishing, 2015, pp. 83–109.

[12]
R. Bhaskar, A. Bhowmick, V. Goyal, S. Laxman, and A. Thakurta, “Noiseless
database privacy,” in Proc. Int. Conf. Theory Appl. Crypto. Inf.
Secur., 2011, pp. 215–232.

[13]
S. U. Nabar, B. Marthi, K. Kenthapadi, N. Mishra, and R. Motwani, “Towards
robustness in query auditing,” in Proc. 32nd Int. Conf. Very Large
Data Bases, 2006, pp. 151–162.

[14]
C. Dwork, “Differential privacy,” Encycl. Cryptography Secur., pp.
338–340, 2011.

[15]
Z. Li, T. J. Oechtering, and D. Gündüz, “Privacy against a hypothesis
testing adversary,” IEEE Trans. Inf. Forensics Secur., vol. 14,
no. 6, pp. 1567–1581, 2018.

[16]
G. N. Nair, “A nonstochastic information theory for communication and state
estimation,” IEEE Trans. Autom. Control, vol. 58, no. 6, pp.
1497–1510, 2013.

[17]
S. A. Osia, B. Rassouli, H. Haddadi, H. R. Rabiee, and
D. Gündüz, “Privacy against brute-force inference attacks,” in
Proc. IEEE Int. Symp. Inf. Theory, 2019, pp. 637–641.

[18]
F. Farokhi and G. Nair, “Non-stochastic private function evaluation,” in
Proc. IEEE Inf. Theory Workshop, Riva del Garda, Italy, 2021, pp.

[19]
R. V. L. Hartley, “Transmission of information,” Bell Syst. Technical
J., vol. 7, no. 3, pp. 535–563, 1928.

[20]
I. Sason and S. Verdú, “Arimoto–Rényi conditional entropy and
bayesian $m$-ary hypothesis testing,” IEEE Trans. Inf. Theory,
vol. 64, no. 1, pp. 4–25, 2017.

[21]
A. Rényi, “On measures of entropy and information,” in Proc. 4th
Berkeley Symp. Math. Stat. Probab., Vol. 1: Contrib. Theory Stat.1em
plus 0.5em minus 0.4emUniversity of California Press, 1961, pp.

[22]
S. Arimoto, “Information measures and capacity of order $\alpha$ for discrete
memoryless channels,” in Proc. 2nd Colloq. Top. Inf. Theory, vol. 16,
Keszthely, Hungary, 1977, p. 1975.

[23]
S. Verdú, “$\alpha$-mutual information,” in 2015 Information Theory
and Applications Workshop (ITA), 2015, pp. 1–6.

[24]
A. Mahajan, “On the relationship between maximin information and common
knowledge,” Dep. Electr. Comput. Eng., McGill University, Tech. Rep., 2014.
[Online]. Available:
<http://www.ece.mcgill.ca/ amahaj1/projects/information/preprint/maximin-information.pdf>

[25]
S. Wolf and J. Wultschleger, “Zero-error information and applications in
cryptography,” in Proc. IEEE Inf. Theory Workshop, 2004, pp. 1–6.

[26]
A. N. Kolmogorov and V. M. Tikhomirov, “$\varepsilon$-entropy and
$\varepsilon$-capacity of sets in function spaces,” Uspekhi
Matematicheskikh Nauk, vol. 14, no. 2, pp. 3–86, 1959, english translation
American Mathematical Society Translations, series 2, vol. 17, pp. 277–364.

[27]
J. L. Massey, “Guessing and entropy,” in Proc. IEEE Int. Symp. Inf.
Theory, Trondheim, Norway, Jun. 1994, p. 204.

[28]
F. Farokhi, “Development and analysis of deterministic privacy-preserving
policies using non-stochastic information theory,” IEEE Trans. Inf.
Forensics Secur., vol. 14, no. 10, pp. 2567–2576, 2019.

[29]
M. Bernhard, J. Benaloh, J. A. Halderman, R. L. Rivest, P. Y. Ryan, P. B.
Stark, V. Teague, P. L. Vora, and D. S. Wallach, “Public evidence from
secret ballots,” in Proc. Int. Jt Conf. Electron. Voting, 2017, pp.

[30]
R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A
Foundation for Computer Science, ser. A foundation for computer
science.1em plus 0.5em minus 0.4emBoston: Addison-Wesley, 1994.

[31]
I. Mironov, “Rényi differential privacy,” in Proc. IEEE 30th Comput.
Secur. Found. Symp., Santa Barbara, CA, 2017, pp. 263–275.

[32]
W. Wang, L. Ying, and J. Zhang, “On the relation between identifiability,
differential privacy, and mutual-information privacy,” IEEE Trans.
Inf. Theory, vol. 62, no. 9, pp. 5018–5029, 2016.

[33]
J. Lee and C. Clifton, “Differential identifiability,” in Proc. 18th
ACM SIGKDD Int. Conf. Knowl. Discovery Data Min., East Lansing, MI, 2012,
pp. 1041–1049.

[34]
N. Li, W. Qardaji, D. Su, Y. Wu, and W. Yang, “Membership privacy: A unifying
framework for privacy definitions,” in Proc. ACM SIGSAC Conf. Comput.
Commun. Secur., ser. CCS '13, Berlin, Germany, 2013, pp. 889–900.

[35]
C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to
sensitivity in private data analysis,” in Theory of Cryptography
Conference, 2006, pp. 265–284.

[36]
A. S. Matveev and A. V. Savkin, “Shannon zero error capacity in the problems
of state estimation and stabilization via noisy communication channels,”
Int. J. Control, vol. 80, no. 2, pp. 241–255, 2007.

[37]
R. Sibson, “Information radius,” Zeitschrift für
Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol. 14, no. 2, pp.
149–160, Jun. 1969.

[38]
A. Asuncion and D. Newman, “UCI machine learning repository,” 2007.
[Online]. Available: <https://archive.ics.uci.edu/ml/index.php>

[39]
F. Farokhi, “Noiseless privacy,” arXiv preprint arXiv:1910.13027,


11institutetext: Lockheed Martin, Advanced Technology Center, Sunnyvale CA
94089, USA 22institutetext: Parallax Advanced Research, Beavercreek OH 45431,
USA 22email<EMAIL_ADDRESS>
# Indecision Trees: Learning Argument-Based Reasoning under Quantified
Uncertainty

Jonathan S. Kent 11 David H. Ménager Ph.D 22

###### Abstract

Using Machine Learning systems in the real world can often be problematic,
with inexplicable black-box models, the assumed certainty of imperfect
measurements, or providing a single classification instead of a probability
distribution.

This paper introduces Indecision Trees, a modification to Decision Trees which
learn under uncertainty, can perform inference under uncertainty, provide a
robust distribution over the possible labels, and can be disassembled into a
set of logical arguments for use in other reasoning systems.

###### Keywords:

Machine Learning Decision Trees Probabilistic Logic Measurement Uncertainty.

##  1 Introduction

For many years, researchers and practitioners have designed and employed rule-
based classification systems. In contrast with other machine learning
classifiers, rule-based systems are useful, not only because of their
predictive power, but also because they often produce knowledge structures, or
rules, humans readily understand. Such rules are typically learned from
datasets which may contain a mixture of numeric and discrete features. Thus,
there is a large variety of different types of rule-based classification
systems. We cannot discuss each one in this paper, but we briefly desribe a
few of them here. For example, MLEM2 [4] discovers classification rules by
finding local coverings of concepts blocks which may be approximated by rough
sets. The AQ algorithm [2] learns rules from a set of examples and counter
examples. The system tries to learn discriminative rules that cover the
positive cases without covering the counter examples. Other rule learning
systems like FURIA [6] and RIPPER [3] learn fuzzy rules. Another approach
involves learning rules by inducing a decision tree structure. Several
algorithms for this exist for building these trees, like CART [1], and ID3
[9], but C4.5 [10] is most commonly used. More recently, there have been rule-
based systems which employ stochastic local search optimization techniques
like simulated annealing, iterated local search, and ant colony optimization
to learn rules [7, 8].

The systems we described are impressive in their own right, but one area that
deserves more attention in rule-based classification systems is handling
quantified measurement noise in the data. More mainstream machine learning
systems (i.e. Bayesian Networks and Neural Networks) have done a better job
handling quantified uncertainty, but measurement noise associated with sensor
readings still poses a significant challenge for rule induction algorithms.
Toward that end, we present a novel rule induction algorithm we call an
indecision tree capable of learning rules from quantified uncertainty from
numeric and discrete-valued features. Our proposed solution is a decision tree
that has been disassembled, reworking each step to operate under quantified
uncertainty, and then reassembled. Thus, in order to understand indecision
trees, we must first explain decision trees from the ground up.

The next section describes preliminaries of decision trees. Following this, we
cover indecision trees in detail. Then, we present our experimental
evaluations, discussing our design and results, before we conclude.

##  2 Decision Trees

idx | Height | Tail | Weight | Color | Breed
---|---|---|---|---|---
1 | 23 | 10 | 76 | Blond | Retriever
2 | 13 | 6 | 21 | Brown | Beagle
3 | 24 | 10 | 39 | Black | Collie
4 | 21 | 10 | 32 | Brown | Collie
5 | 16 | 12 | 23 | Brown | Beagle
6 | 19 | 11 | 65 | Brown | Retriever
7 | 22 | 10 | 42 | Brown | Collie
8 | 20 | 4 | 68 | Black | Retriever
9 | 15 | 9 | 24 | Brown | Beagle
10 | 22 | 7 | 72 | Blond | Retriever
Figure 1: An example dataset consisting of physical features of dogs, such as
their shoulder height and tail length in inches, weight in pounds, and fur
color, as well as a label representing the true breed of the dog.

Input: $\mathcal{D},b$, Should_Leaf, Update

Output: $\mathcal{N}$ $\triangleright$ Root Node

Function  _Node(_$\mathcal{D}_{q},b$_)_:

if  _Should_Leaf(_$b$_)_ then

$\mathcal{N}_{q}.leaf\longleftarrow\textrm{true}$

$\mathcal{N}_{q}.p\longleftarrow\\{\big{(}c_{i},p(c_{i})\big{)}|c_{i}\in\mathcal{D}_{q}$}

else

$\mathcal{N}_{q}.leaf\longleftarrow\textrm{false}$

$\mathcal{N}_{q}.C\longleftarrow C_{*}(\mathcal{D}_{q})$

$b\longleftarrow$ Update(_$b,\mathcal{D}_{q},\mathcal{N}_{q}.C$_)

$\mathcal{N}_{q}.left\\_child\longleftarrow$
Node(_$\mathcal{D}_{q\cup\\{C\\}},b$_)

$\mathcal{N}_{q}.right\\_child\longleftarrow$ Node(_$\mathcal{D}_{q\cup\\{\neg
C\\}}\;b$_)

end if

return($\mathcal{N}_{q}$)

$q\longleftarrow\emptyset$

$\mathcal{D}_{q}\longleftarrow\mathcal{D}$

$\mathcal{N}\longleftarrow$ Node(_$\mathcal{D}_{q},b$_)

Algorithm 1 Growing a Decision Tree

Input: $x_{k},\mathcal{N}$

Output: $P=\\{\big{(}c_{i},p(x_{k}\in c_{i})\big{)}\\}$ $\triangleright$ Class
Probabilities

Function  _Inference(_$x_{k},\mathcal{N}_{q}$_)_:

if  _$\mathcal{N}_{q}$.leaf_ then

return($\mathcal{N}_{q}.p$)

else

if  _$\mathcal{N}_{q}.C(x_{k})$_ then

return(Inference(_$x_{k},\mathcal{N}_{q}.$ left_child_))

else

return(Inference(_$x_{k},\mathcal{N}_{q}.$ right_child_))

end if

end if

$q\longleftarrow\emptyset$

$\mathcal{N}_{q}\longleftarrow\mathcal{N}$

$P\longleftarrow$ Inference(_$x_{k},\mathcal{N}_{q}$_)

Algorithm 2 Inference Using a Decision Tree

Input: $\mathcal{N}$, Condense

Output: $R=\\{r_{i}\\}$ $\triangleright$ Set of Rules

Function  _Get_Rules(_$\mathcal{N}_{q}$_)_:

if  _$\mathcal{N}_{q}$.leaf_ then

return($\\{($Condense $(q),\mathcal{N}_{q}.p)\\}$)

else

return(Get_Rules(_$\mathcal{N}_{q}.$ left_child_) $\cup$
Get_Rules(_$\mathcal{N}_{q}.$ right_child_))

end if

$q\longleftarrow\emptyset$

$\mathcal{N}_{q}\longleftarrow\mathcal{N}$

$R\longleftarrow$ Get_Rules(_$x_{k},\mathcal{N}_{q}$_)

Algorithm 3 Pulling Rules from a Decision Tree

In order to explain the algorithm used to create decision trees, we will use
the example of a dog breed classifier.

Decision trees work by repeatedly, greedily splitting the data according to
how much information is gained by doing so [11, 1, 5]. This information gain
can be measured with a couple different metrics, but for our purposes, we will
use entropy, from Information Theory [12].

###  2.1 Entropy

Entropy, essentially, is a measure of how long an average description has to
be to represent every element of a set of data. For example, if a dataset of
dogs contained only retrievers, you could immediately identify the breed of a
dog merely by knowing it belonged to the dataset, 0 extra information is
needed. But if the dataset was 50% retrievers and 50% collies, you would need
to be told which of the two possible breeds a given dog was, a single binary
piece of information, beyond just knowing it belonged to the dataset. Thus,
the entropy of the dataset is 1 bit.

However, if the dataset was, say, 70% retrievers and 30% collies, you have
more information than in the 50:50 case, because you know that a given dog
belonging to the dataset was more likely to be a retriever than a collie. The
full expression for the entropy of a dataset $\mathcal{D}$ captures this, by
defining entropy as the proportion of the dataset belonging to each class
$c_{i}$, times how many bits would be needed to split the dataset into equal
subsets the size of that class, summed over all the classes present:

$H(\mathcal{D})=\sum_{c_{i}\in\mathcal{D}}p(c_{i})\log_{2}\Big{(}\frac{1}{p(c_{i})}\Big{)}$

which can be simplified as

$H(\mathcal{D})=-\sum_{c_{i}\in\mathcal{D}}p(c_{i})\log_{2}\big{(}p(c_{i})\big{)}$

for computational purposes. For example, in the case of a 70:30 split as
described, this produces an entropy of approximately 0.881

###  2.2 Information Gain via Splitting with Clauses

Let’s start looking at the dataset in Figure 1. This dataset is composed of
40% retrievers, 30% beagles, and 30% collies, for an entropy of 1.571. This is
how much information we need to correctly label every element of the dataset.
But the features included can tell us this information, and we can make use of
them by asking questions about the features. For example, consider asking of
each dog ”Is this dog 20 inches or taller at the shoulder?”, and then sorting
the dogs based on the answer. Of the dogs for which the answer is ”Yes,” there
are 3 retrievers and 3 collies, and of the dogs for which the answer is ”No,”
there are 3 beagles and 1 retriever.

We can rephrase this question into a clause, $C_{\textrm{height}\geq
20}(x_{i})=$”The dog represented by $x_{i}$ is 20 inches or taller at the
shoulder,” and then divide the dogs based on whether $C$ is true or false,
i.e.

$\mathcal{D}_{C}$ | $=$ | $\\{$ | $x_{i}\in\mathcal{D}$ | $|$ | $C(x_{i})$ | $\\}$
---|---|---|---|---|---|---
$\mathcal{D}_{\neg C}$ | $=$ | $\\{$ | $x_{i}\in\mathcal{D}$ | $|$ | $\neg C(x_{i})$ | $\\}$

and then look at the entropy of the split data, getting
$H(\mathcal{D}_{C_{\textrm{height}\geq 20}})=1$ and $H(\mathcal{D}_{\neg
C_{\textrm{height}\geq 20}})=0.811$. By taking the weighted average of the
entropy, we get, on average, how much entropy remains in the dataset once
we’ve applied this clause, and by subtracting this entropy from the original,
we get the information gain of the clause itself;

$IG(\mathcal{D},C)=H(\mathcal{D})-\frac{|\mathcal{D}_{C}|\cdot
H(\mathcal{D}_{C})+|\mathcal{D}_{\neg C}|\cdot H(\mathcal{D}_{\neg
C})}{|\mathcal{D}|}$

which in this case is 0.646, the number of bits of information that the clause
$C_{\textrm{height}\geq 20}$ gives us.

###  2.3 Finding the Best Clause

Stating the best clause is as simple as

$C_{*}(\mathcal{D})=\arg\max_{C\in\mathcal{C}}IG(\mathcal{D},C)$

essentially, enumerating all possible clauses as $\mathcal{C}$, and then
trying all of them to see which one has the greatest information gain. The
question is how to enumerate clauses.

####  2.3.1 Discrete Feature Clauses

Each clause of a discrete feature is defined by some subset of the discrete
feature values. For example, consider the possible fur colors of the dogs:
black, blond, and brown. Each clause would take a form like
$C_{\textrm{fur}\in\textrm{\\{black\\}}}(x_{i})=$ ”The dog represented by
$x_{i}$ has black fur” or $C_{\textrm{fur}\in\textrm{\\{black,
blond\\}}}(x_{i})=$ ”The dog represented by $x_{i}$ has black or blond fur.”
For the $j^{\textrm{th}}$ discrete feature $f^{j}_{d}$, all the possible
clauses are enumerated with

$\mathcal{C}^{j}_{d}=\\{C_{f^{j}_{d}\in s}|s\in\mathcal{P}(f^{j}_{d})\\}$

but in practice, half of these clauses are ignored, as each clause has an
opposite clause that results in the same split, just backwards, e.g. ”The dog
represented by $x_{i}$ is blond” results in the same split as ”The dog
represented by $x_{i}$ is brown or black.” Once that’s done, all the possible
discrete clauses can be collected together,

$\mathcal{C}_{d}=\bigcup_{j}\mathcal{C}^{j}_{d}$

then it’s just a matter of enumerating the continuous clauses.

####  2.3.2 Continuous Feature Clauses

The enumeration of the discrete features relies on the power set of the
discrete features being finite, which requires that the set of discrete
features is finite. But continuous features are assumed to have an infinite
number of feature values, and furthermore that nearby feature values should
typically be grouped together anyway. Thus, instead of futilely trying to
enumerate every possible continuous clause, we will instead enumerate clauses
that can be represented by threshold values, such as $C_{\textrm{height}\geq
20}$, which was discussed earlier.

For the $j^{\textrm{th}}$ continuous feature $f^{j}_{c}$, while there are
infinite possible threshold values, most thresholds are either useless - being
above or below the maximum or minimum values, respectively - known suboptimal
- dividing two sequential elements which are from the same class - or
equivalent to other thresholds - making the same split in the training data as
another. So the set of thresholds we bother checking, $T^{j}$, is simply the
set of middles between any two values of $f^{j}_{d}$, provided that those two
values are sequential if you sorted the data based on that feature, and that
they belong to samples of different classes. For example, looking at heights:
the values 27 and 10 wouldn’t be checked as thresholds because they’re out of
range, 15.5 wouldn’t be checked because it separates two beagles, and 17
wouldn’t be checked because it would result in the same split as 17.5. The
threshold values that would be checked are 17.5, 20.5, 21.5, and 23.5. So the
clauses for the feature $f^{j}_{c}$ would be enumerated with

$\mathcal{C}^{j}_{c}=\\{C_{f^{j}_{c}\geq t}|t\in T^{j}\\}$

and then collected over all the features with

$\mathcal{C}_{c}=\bigcup_{j}\mathcal{C}^{j}_{c}$

at which point all the clauses to be checked have now been enumerated, and we
put the continuous and the discrete feature clause collections together with

$\mathcal{C}=\mathcal{C}_{d}\cup\mathcal{C}_{c}$

meaning that $C_{*}$ can now be found by iterating through and checking all
the information gains.

###  2.4 Growing the Decision Tree

Starting from the root node, the decision tree is grown recursively by
associating each node with the best clause to be found at that node based on
the current state of the dataset, and then passing the dataset subject to both
that clause and its negation to that node’s left and right children,
respectively. By holding onto some information regarding the state of the tree
over time, such as the current entropy of the subset of the dataset, facts
about the current best clause, or simply the current depth in the tree, the
algorithm can produce a leaf instead of another branch. This means simply
writing down the probability of each class as they currently stand, and
ceasing to branch. The algorithm for this is shown in Algorithm 1.

###  2.5 Using the Decision Tree

Once this is done, inferences on new samples can be pulled out using Algorithm
2. All this does is, starting at the root node, go to each child according to
whether or not the sample satisfies the clause at that node. Once it hits a
leaf node, it has found the probabilities that the tree outputs. To use this
for classification, simply choose the class with the highest associated
probability.

It also becomes possible to turn the decision tree into a set of logical
rules. This is because, for each leaf in the tree, there is exactly one way
for samples to reach it. If a leaf is represented by node $\mathcal{N}_{q}$,
where $q$ is a set of clauses $\\{C_{1},C_{2},C_{3},\dots,C_{n}\\}$, then a
rule can take the form of ”Satisfying all clauses in $q\implies$ inferred
class probabilities are $\mathcal{N}_{q}.p$,” with the added note that clauses
can be condensed according to their redundancy. For example, if one clause
takes the form ”Fur length is less than 10,” and another is ”Fur length is
less than 15,” the latter can simply be thrown out. Similarly would be clauses
like ”Fur color is brown,” and ”Fur color is blond or brown.”

With this established, we will now begin to explain indecision trees: how they
operate, their similarities to decision trees, and the modifications required
to grow and infer from them under uncertainty.

##  3 Indecision Trees

Indecision trees are a modified version of decision trees, to accommodate
quantified measurement uncertainty. Fundamentally, this works by considering
each subset of the data, not to actually contain any given data point, but
instead for each data point to have some probability of existing in each
subset. For example, if a dog is observed to have a height of 22 inches, with
an uncertainty of 2.5 inches representing the standard deviation of the
measurement, then rather than saying the dog is definitely shorter than 24
inches, we would say that the dog has a 79% chance of being shorter than 24
inches, because $p\big{(}h\sim\mathcal{N}(\mu=22,\sigma=2.5)<24\big{)}\approx
0.79$.

As a result, if that sample were subjected to the clause ”height is greater
than 24 inches,” rather than following one branch of the tree or the other,
both branches are following simultaneously, according to the probabilities of
the clause being satisfied or unsatisfied, and so on in turn. For example, the
79% associated with the dog being shorter than 24 inches might go to another
branch, with a clause like ”the dog is blond,” and at that branch the clause
might be satisfied 60% of the time and unsatisfied 40% of the time. By
assuming that the features are independent, this would split the 79% into 47%
and 32%, respectively, which would then each go to the next branches. At the
end, the sum of probabilities over all of the leaves will necessarily be 100%,
and by summing the probability of reaching each leaf times the probability of
being a given class once at that leaf, you receive the probability of the
sample belonging to that class. With this as the formulation, we can begin
implementing the modifications that turn a decision tree into an indecision
tree.

###  3.1 Entropy under Uncertainty

In order to calculate entropy under these conditions, we need to rework how we
approach the probability of each class appearing in an uncertain dataset
$\mathcal{D}^{u}$. We cannot calculate $p(c_{i})$ as being $p(x_{k}\in
c_{i}|x_{k}\in\mathcal{D}^{u})$ because it’s not as simple as
”$x_{k}\in\mathcal{D}^{u}$” anymore. Instead, we have to use a weighted sum,
with weights representing the probability of each sample appearing in the
uncertain dataset, with

$p(c_{i})=\frac{\sum_{x_{l}\in
c_{i}}p(x_{l}\in\mathcal{D}^{u})}{\sum_{x_{k}}p(x_{k}\in\mathcal{D}^{u})}$

at which point the new $p(c_{i})$ can be plugged into the original entropy
formula verbatim, using

$H(\mathcal{D}^{u})=-\sum_{c_{i}\in\mathcal{D}^{u}}p(c_{i})\log_{2}\big{(}p(c_{i})\big{)}$

###  3.2 Information Gain under Uncertainty

For this, we can look at the uncertain dataset in Figure 3.5. Similarly to the
dataset in Figure 1, it is composed of 40% retrievers, 30% beagles, and 30%
collies. Because no clauses have yet been applied to the dataset, the
probability of each sample appearing in the dataset as it exists is 100%, so
it has the same entropy as the certain dataset, 1.571.

We can then consider the same clause that was used in the certain case,
$C_{\textrm{height}\geq 20}$, and then produce two subsets associated with
this clause,

$\mathcal{D}^{u}_{C}$ | $|$ | $p(x_{i}\in\mathcal{D}^{u}_{C})$ | $=$ | $p\big{(}C(x_{i})\big{)}\cdot p(x_{i}\in\mathcal{D}^{u})$
---|---|---|---|---
$\mathcal{D}^{u}_{\neg C}$ | $|$ | $p(x_{i}\in\mathcal{D}^{u}_{\neg C})$ | $=$ | $p\big{(}\neg C(x_{i})\big{)}\cdot p(x_{i}\in\mathcal{D}^{u})$

which gives the following probabilities:

idx | $p(x_{i}\in\mathcal{D}^{u}_{C})$ | $p(x_{i}\in\mathcal{D}^{u}_{\neg C})$ | Breed
---|---|---|---
1 | 0.84 | 0.16 | Retriever
2 | 0 | 1 | Beagle
3 | 0.95 | 0.05 | Collie
4 | 0.69 | 0.31 | Collie
5 | 0 | 1 | Beagle
6 | 0.16 | 0.84 | Retriever
7 | 0.84 | 0.16 | Collie
8 | 0.5 | 0.5 | Retriever
9 | 0 | 1 | Beagle
10 | 0.79 | 0.21 | Retriever

allowing us to calculate the entropies for each dataset. Probabilistically,
$\mathcal{D}^{u}_{C_{\textrm{height}\geq 20}}$ contains approximately 2.29
retrievers, 0 beagles, and 2.48 collies, with an entropy of approximately
0.99. Similarly, $\mathcal{D}^{u}_{\neg C_{\textrm{height}\geq 20}}$ is
expected to contain 1.71 retrievers, 3 beagles, and 0.52 collies, with an
entropy of approximately 1.32. While these are relatively close to the numbers
in the discrete case, they are different enough that failing to account for
the uncertainty would yield a quite different result. We can then modify the
notion of cardinality by using the number of samples the dataset probably
contains,

$|\mathcal{D}^{u}_{C}|=\sum_{x_{i}}p(x_{i}\in\mathcal{D}^{u}_{C})$

to redo the information gain calculation

$IG(\mathcal{D}^{u},C)=H(\mathcal{D}^{u})-\frac{|\mathcal{D}^{u}_{C}|\cdot
H(\mathcal{D}^{u}_{C})+|\mathcal{D}^{u}_{\neg C}|\cdot H(\mathcal{D}^{u}_{\neg
C})}{|\mathcal{D}^{u}|}$

which here takes a value of 0.405. This is the information gained from
applying the clause $C_{\textrm{height}\geq 20}$ to the uncertain version of
the dataset.

###  3.3 Best Clause under Uncertainty

The exact same procedure can be used to enumerate clauses for indecision trees
as is used for decision trees. However, this is with one caveat; the
information gain of continuous clauses is a piecewise constant function of the
threshold value for decision trees, while it is continuous and differentiable
with respect to the threshold value for indecision trees. As a result, simply
guessing and checking will yield suboptimal results compared to a method of
gradient descent starting from a variety of positions. However, this procedure
would be computationally expensive when repeated ad nauseum in the enumeration
of all possible clauses, and so it will be left to future research.

###  3.4 Growing the Indecision Tree

The process of growing an indecision tree is the same as growing a decision
tree, with a switch from a certain to an uncertain dataset. The necessary
modifications are shown in Algorithm 4.

###  3.5 Using the Indecision Tree

While pulling the rules out of the indecision tree remains exactly the same as
pulling the rules out of a decision tree, performing inference with indecision
tree does require some modification in process. Rather than simply finding the
leaf node that contains the sample on which inference is being formed, every
single leaf node has to be checked, the probabilities of reaching those leaf
nodes multiplied by their class probabilities, and then returning the sum over
all of those values. The algorithm with these modifications in place can be
seen in Algorithm 5.

r——cc—cc—cc—ccc——l idx & Height Tail Weight Color Breed
$\mu$ $\sigma$ $\mu$ $\sigma$ $\mu$ $\sigma$ $p(\textrm{Blond})$
$p(\textrm{Brown})$ $p(\textrm{Black})$
1 23 3 10 1 76 7 0.9 0.1 0 Retriever
2 13 1.5 6 0.5 21 3 0.2 0.7 0.1 Beagle
3 24 2.5 10 0.5 39 4 0 0.4 0.6 Collie
4 21 2 10 1.5 32 4 0 0.7 0.3 Collie
5 16 1.5 12 1 23 2 0.1 0.8 0.1 Beagle
6 19 1 11 2 65 5 0.1 0.5 0.4 Retriever
7 22 2 10 0.5 42 6 0.5 0.3 0.2 Collie
8 20 2.5 4 0.5 68 6 0.2 0.2 0.6 Retriever
9 15 1.5 9 1 24 2 0.3 0.4 0.3 Beagle
10 22 2.5 7 0.5 72 8 0.6 0.1 0.3 Retriever

Figure 2: An example of an uncertain dataset, in which each feature value is
replaced with a distribution over its possible values. Rather than being given
the exact height of each dog, for example, we are given the mean and standard
deviation of the height of the dog, representing the measured value and the
quantified measurement uncertainty. For the fur colors, we are given the
probability of it being each color, representing a discrete distribution
rather than a discrete feature value,

Input: $\mathcal{D}^{u},b$, Should_Leaf, Update

Output: $\mathcal{N}$ $\triangleright$ Root Node

Function  _Node(_$\mathcal{D}^{u}_{q},b$_)_:

if  _Should_Leaf(_$b$_)_ then

$\mathcal{N}_{q}.leaf\longleftarrow\textrm{true}$

$\mathcal{N}_{q}.p\longleftarrow\\{\big{(}c_{i},p(c_{i})\big{)}|c_{i}\in\mathcal{D}^{u}_{q}$}

else

$\mathcal{N}_{q}.leaf\longleftarrow\textrm{false}$

$\mathcal{N}_{q}.C\longleftarrow C_{*}(\mathcal{D}^{u}_{q})$

$b\longleftarrow$ Update(_$b,\mathcal{D}^{u}_{q},\mathcal{N}_{q}.C$_)

$\mathcal{N}_{q}.left\\_child\longleftarrow$
Node(_$\mathcal{D}^{u}_{q\cup\\{C\\}},b$_)

$\mathcal{N}_{q}.right\\_child\longleftarrow$
Node(_$\mathcal{D}^{u}_{q\cup\\{\neg C\\}}\;b$_)

end if

return($\mathcal{N}_{q}$)

$q\longleftarrow\emptyset$

$\mathcal{D}^{u}_{q}\longleftarrow\mathcal{D}^{u}$

$\mathcal{N}\longleftarrow$ Node(_$\mathcal{D}^{u}_{q},b$_)

Algorithm 4 Growing an Indecision Tree

Input: $x_{k},\mathcal{N}$

Output: $P=\\{\big{(}c_{i},p(x_{k}\in c_{i})\big{)}\\}$ $\triangleright$ Class
Probabilities

Function  _Inference(_$x_{k},\mathcal{N}_{q}$_)_:

if  _$\mathcal{N}_{q}$.leaf_ then

return($\\{(c_{i},\mathcal{N}_{q}.p(c_{i})\cdot\prod_{C\in
q}p\big{(}C(x_{k})\big{)})\\}$)

else

$P_{l}\longleftarrow$ Inference(_$x_{k},\mathcal{N}_{q}.$ left_child_)

$P_{r}\longleftarrow$ Inference(_$x_{k},\mathcal{N}_{q}.$ right_child_)

return($\\{(c_{i},P_{l}(c_{i})+P_{r}(c_{i}))\\}$)

end if

$q\longleftarrow\emptyset$

$\mathcal{N}_{q}\longleftarrow\mathcal{N}$

$P\longleftarrow$ Inference(_$x_{k},\mathcal{N}_{q}$_)

Algorithm 5 Inference Using an Indecision Tree

##  4 Experimentation

###  4.1 Dataset

Publicly available datasets that include quantified uncertainty of the form
mentioned in this paper are rare, and so for the purposes of experimentation,
a synthetic dataset was created. This dataset consists of thirteen features,
with a three-way classification problem. Of the thirteen features, nine are
continuous, and four are discrete.

Of the nine continuous features, five were generated via the following
procedure: for each of the three classes, three five-dimensional centroid
vectors were randomly generated, for a total of nine centroids. When a sample
is selected to be from a given class, one of the centroid vectors associated
with the class is selected, and perturbed with random noise, the standard
deviations of which were also randomly selected, as well as those deviations
differing by feature. These features are then recorded using their observed
values as $\mu$, and their randomly pre-selected standard deviations as
$\sigma$. This produces behavior where features correlate based on classes,
which themselves cannot be simply represented as clusters. Of the remaining
four continuous features, two are simply copies of previous features, one is
the sum of two previous features, and one was generated without regard to the
class, thus being a source of pure noise.

Of the four discrete features, two were generated by the following procedure:
for each class, a probability was selected for each bin in a given feature,
differing by class. Ground truth bins for each sample were sampled according
to these probabilities. Each bin was then associated with a randomly generated
centroid vector in a five dimensional vector space, and probabilities per bin
were assigned according to the softmax of the negative distances to each of
the centroids after random noise was applied. This produces a valid discrete
distribution, which crucially will typically assign the highest probability to
the ground truth bin. One of the remaining discrete features was simply a copy
of a previous feature, and the other was random noise with no relationship to
the ground truth class.

A dataset consisting of 10,000 samples was generated according to these
procedures, of which 7,000 was used for training models, and 3,000 was used
for testing their resulting accuracies.

###  4.2 Experimental Results

The primary advance presented by this paper was the addition of handling
quantified uncertainty to decision trees to produce indecision trees. Thus,
the point of comparison to the indecision tree is to simply remove the
uncertainty from the dataset, and run the same training and inference
procedures on the same data. Here, the standard deviations were removed from
the continuous features, and the bin probabilities were replaced with a 1 for
the highest probability and a 0 for all others. Under these conditions, a
standard decision tree achieved $94.5\%$ accuracy, as compared to the
indecision tree’s $98.1\%$ accuracy. This is a 3.6 point increase in accuracy,
as well as a $65.5\%$ reduction in error.

##  5 Conclusions and Future Work

As seen in the experimental results, providing the uncertainties to the model
increased the amount of information that it had about the data, the
distributions aiding in the robustness of the inferences, and removing it lead
to an expected and reasonable decrease in the accuracy of the model. Thus were
the aims of developing this method validated, and we can now effectively
leverage the quantified uncertainty of measurements to aid in learning and
inference.

Future and presently ongoing work will involve adapting other algorithms like
MLNs and MLEM2 to work in this setting with quantified uncertainty, as well as
trying to learn lessons for applications to other classification problems.
Perhaps modifying neural networks to account for measurement uncertainty would
similarly increase their robustness and accuracy, as well as harden them
against adversarial methods.

## References

  * [1] Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification and regression trees. belmont, ca: Wadsworth. International Group 432, 151–166 (1984)
  * [2] Cervone, G., Franzese, P., Keesee, A.P.: Algorithm quasi-optimal (aq) learning. Wiley Interdisciplinary Reviews: Computational Statistics 2(2), 218–236 (2010)
  * [3] Cohen, W.W.: Learning to classify english text with ilp methods. Advances in inductive logic programming 32, 124–143 (1995)
  * [4] Grzymala-Busse, J.W., Rzasa, W.: A local version of the mlem2 algorithm for rule induction. Fundamenta Informaticae 100(1-4), 99–116 (2010)
  * [5] Hastie, T., Tibshirani, R., Friedman, J.H., Friedman, J.H.: The elements of statistical learning: data mining, inference, and prediction, vol. 2. Springer (2009)
  * [6] Hühn, J., Hüllermeier, E.: Furia: an algorithm for unordered fuzzy rule induction. Data Mining and Knowledge Discovery 19(3), 293–319 (2009)
  * [7] Jabbar, A.M.: Rule induction with iterated local search. International Journal of Intelligent Engineering and Systems 14(4), 289–298 (2021)
  * [8] Parpinelli, R.S., Lopes, H.S., Freitas, A.A.: Data mining with an ant colony optimization algorithm. IEEE transactions on evolutionary computation 6(4), 321–332 (2002)
  * [9] Quinlan, J.R.: Induction of decision trees. Machine learning 1(1), 81–106 (1986)
  * [10] Quinlan, J.: Program for machine learning. C4. 5 (1993)
  * [11] Ross Quinlan, J.: C4. 5: programs for machine learning. Mach. Learn 16(3), 235–240 (1993)
  * [12] Shannon, C.E.: A mathematical theory of communication. The Bell system technical journal 27(3), 379–423 (1948)