text:
\subsubsection*{Acknowledgements}

This research was supported by DARPA (PPAML program, contract number
FA8750-14-2-0004), IARPA (under research contract 2015-15061000003), the Office
of Naval Research (under research contract N000141310333), the Army Research
Office (under agreement number W911NF-13-1-0212), and gifts from Analog Devices
and Google.

\section{Proof of optimizing a CMI query}
\label{appx:proof-optimizing-cmi}

\begin{proof}[Proof of Lemma~\ref{lemma:crosscat-cmi-sparse}]
\renewcommand{\qedsymbol}{}
We use the product-sum property of the logarithm (line 3) and linearity of
expectation (line 4) to show that CrossCat's variable partition $\bm\gamma$
induces a factorization of a CMI query.
\begin{flalign*}
&\mathcal{I}_{\mathcal{G}}\left(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}|\hat{\bm{x}}_\mathcal{C}\right)
= \mathbb{E}\left[
    \log \left(
      \frac{p_{\G}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}|\hat{\bm{x}}_\mathcal{C})}
        {p_{\G}(\bm{x}_\mathcal{A}|\hat{\bm{x}}_\mathcal{C})p_{\G}(\bm{x}_\mathcal{B}|\hat{\bm{x}}_\mathcal{C})}
    \right)
  \right]\\
&= \mathbb{E}\left[
    \log \left(
      \prod_{\mathcal{V}\in\bm\gamma}
        \frac{
          p_{\G_\mathcal{V}}(\bm{x}_{\mathcal{A}\cap\mathcal{V}}, \bm{x}_{\mathcal{B}\cap\mathcal{V}} | \hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}})}
          {p_{\G_\mathcal{V}}(\bm{x}_{\mathcal{A}\cap\mathcal{V}}|\hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}})
            p_{\G_\mathcal{V}}(\bm{x}_{\mathcal{B}\cap\mathcal{V}}|\hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}})}
    \right)
  \right]\\
&= \mathbb{E}\left[
    \sum_{\mathcal{V}\in\bm\gamma}
       \log \left(
        \frac{
          p_{\G_\mathcal{V}}(\bm{x}_{\mathcal{A}\cap\mathcal{V}}, \bm{x}_{\mathcal{B}\cap\mathcal{V}} | \hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}})}
          {p_{\G_\mathcal{V}}(\bm{x}_{\mathcal{A}\cap\mathcal{V}}|\hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}})
            p_{\G_\mathcal{V}}(\bm{x}_{\mathcal{B}\cap\mathcal{V}}|\hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}})}
    \right)
  \right]\\
&= \sum_{\mathcal{V}\in\bm\gamma}
    \mathbb{E}\left[
      \log \left(
        \frac{
          p_{\G_\mathcal{V}}(\bm{x}_{\mathcal{A}\cap\mathcal{V}}, \bm{x}_{\mathcal{B}\cap\mathcal{V}} | \hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}})}
          {p_{\G_\mathcal{V}}(\bm{x}_{\mathcal{A}\cap\mathcal{V}}|\hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}})
            p_{\G_\mathcal{V}}(\bm{x}_{\mathcal{B}\cap\mathcal{V}}|\hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}})}
      \right)
    \right]\\
&= \sum_{\mathcal{V}\in\bm\gamma}
  \mathcal{I}_{\mathcal{G}_\mathcal{V}} \left(
    \bm{x}_{\mathcal{A}\cap\mathcal{V}}{:}\bm{x}_{\mathcal{B}\cap\mathcal{V}}|
    \hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}}
  \right).
\end{flalign*}
\end{proof}

\vspace{-3cm}

\section{Experimental methods for dependence detection baselines}
\label{appx:experimental-methods}

In this section we outline the methodology used to produce the pairwise $R^2$
and HSIC heatmaps shown in Figures~\ref{subfig:heatmap-pearson-bonferroni} and
\ref{subfig:heatmap-hsic}.
To detect the strength of linear correlation (for $R^2$) and perform a marginal
independence test (for HSIC) given variables $x_i$ and $x_j$ in the Gapminder
dataset, all records in which at least one of these two variables is missing
were dropped.
If the total number of remaining observations was less than three, the null
hypothesis of independence was not rejected due to degeneracy of these methods
at very small sample sizes.
Hypothesis tests were performed at the $\alpha=0.05$ significance level.
To account for multiple testing (a total of $\binom{320}{2}=51040$), a standard
Bonferroni correction was applied to ensure a family-wise error rate of at most
$\alpha$.

We used an open source MATLAB implementation for HSIC (function
\url{hsicTestBoot} from
\url{http://gatsby.ucl.ac.uk/~gretton/indepTestFiles/indep.htm}).
1000 permutations were used to approximate the null distribution, and kernel
sizes were determined using median distances from the dataset.
From Figure~\ref{subfig:heatmap-hsic}, HSIC detects a large number of
statistically significant dependencies.
Figures~\ref{fig:hsic-spurious} and \ref{fig:hsic-common-sense} report spurious
relationships reported as dependent by HSIC but have a low dependence
probability of less than 0.15 according to posterior CMI (Eq~\ref{eq:depprob}),
and common-sense relationships reported as independent HSIC but have a
high dependence probability.

\begin{figure}[H]
\centering
\tiny\bf
\caption{\footnotesize Spurious relationships detected as dependent by HSIC
($p\ll 10^{-6}$) but probably independent
($\mathbb{P}[\mathcal{I}_\mathcal{G}(x_i{:}x_j)>0]<0.15)$ by the MI upper bound.}
\label{fig:hsic-spurious}
\begin{tabular*}{\linewidth}{ll}
variable A & variable B  \\ \midrule
body mass index (men) & privately owned forest (\%) \\
energy use (per capita) & 50+ yrs sex ratio \\
homicide (15-29) & inflation  (annual \%) \\
children out of primary school & male above 60 (\%) \\
income share (fourth 20\%) & suicide rate age 45-59 \\
personal computers & arms exports (US\$) \\
billionaires (per 1M) & mobile subscription (per 100) \\
residential elec. consumption & smear-positive detection (\%) \\
coal consumption (per capita) & age at 1st marriage (women) \\
coal consumption (per capita) & dead kids per woman \\
underweight children & murder (per 100K) \\
female 0-4 years (\%) &  15+ literacy rate (\%) \\
broadband subscribers (\%) & dots new case detection (\%) \\
crude oil prod. (per capita) & TB incidence (per 100K) \\
dependency ratio & people living with hiv  \\ \bottomrule
\end{tabular*}

\includegraphics[width=.9\linewidth]{resources/scatter-spurious-hsic.pdf}

\rule{\linewidth}{1px}
\medskip

\caption{\footnotesize Common-sense relationships detected as independent by
HSIC ($p\ll 10^{-6}$), but probably dependent
($\mathbb{P}[\mathcal{I}_\mathcal{G}(x_i{:}x_j)>0]>0.85)$ by the MI upper bound.}
\label{fig:hsic-common-sense}

\begin{tabular*}{\linewidth}{ll}
variable A & variable B  \\ \midrule
motor vehicles per 1k & pop urban agglomerations (\%) \\
car mortality (per 100K) & road incidents 45-59 \\
wood removal (cubic m.) & primary forest land (ha)\\
forest products total (US\$) & primary forest land (ha) \\
15-24 yrs sex ratio & 50+ yrs sex ratio \\
gdp per working hr (US\$) & urban population (\%) \\
dots pop. coverage (\%) & dots new case detection (\%) \\
total 15-24 unemp. (\%) & long term unemp. (\%) \\
female self-employed (\%) & female service workers (\%)  \\
female agricult. workers (\%) & total industry workers (\%) \\
female industry workers (\%) & male industry workers (\%) \\
road incidents age 60+ & road incidents age 15-29 \\
suicide rate age 15-29 & suicide rate age 60+ \\ \bottomrule
\end{tabular*}

\includegraphics[width=.9\linewidth]{resources/scatter-common-sense-hsic.pdf}

\end{figure}

\input{figures/marks}

\section{Applications to macroeconomic indicators of global poverty,
education, and health}
\label{sec:applications}

\input{figures/gapminder}

This section illustrates the efficacy of the proposed approach on a sparse
database from an ongoing collaboration with the Bill \& Melinda Gates
Foundation.%
\footnote{A further application, to a \mbox{real-world} dataset of mathematics
exam scores, is shown in Appendix~\ref{appx:applications-marks}.}
The Gapminder data set is an extensive longitudinal dataset of $\sim$320 global
developmental indicators for 200 countries spanning over 5 centuries
\cite{rosling2008}.
These include variables from a broad set of categories such as education,
health, trade, poverty, population growth, and mortality rates.
We experiment with a cross-sectional slice of the data from 2002.
Figure~\ref{subfig:heatmap-pearson-bonferroni} shows the pairwise $R^2$
correlation values between all variables; each row and column in the heatmap is
an indicator in the dataset, and the color of a cell is the raw value of $R^2$
(between 0 and 1).
Figure~\ref{subfig:heatmap-hsic} shows pairwise binary hypothesis tests of
independence using HSIC \cite{gretton2005}, which detects a dense set of
dependencies including many spurious relationships %
(Appendix~\ref{appx:experimental-methods}).
For both methods, statistically insignificant relationships ($\alpha=0.05$ with
Bonferroni correction for multiple testing) are shown as 0.
Figure~\ref{subfig:heatmap-dependence-probability} shows an upper bound on the
pairwise probability that the MI of two variables exceeds zero (also a value
between 0 and 1).
These entries are estimated using Eq~\eqref{eq:depprob} (bypassing Monte Carlo
estimation) using $H{=}100$ samples of CrossCat.
Note that the metric $\mathbb{P}[\mathcal{I}_\mathcal{G}(x_i{:}x_j)>0]$ in
\mbox{Figure~\ref{subfig:heatmap-dependence-probability}} only indicates the
\textit{existence} of a predictive relationship between $x_i$ and $x_j$; it
does not quantify either the strength or directionality of the relationship.

It is instructive to compare the dependencies detected by $R^2$ and
\textsc{\small CrossCat-Cmi}.
Table \ref{tab:r2-cmi-spurious} shows pairs of variables that are spuriously
reported as dependent according to correlation; scatter plots reveal they are
either (i) are sparsely observed or (ii) exhibit high correlation due to large
outliers.
Table \ref{tab:r2-cmi-common-sense} shows common-sense relationships between
pairs of variables that \textsc{\small{CrossCat-CMI}} detects but $R^2$ does
not; scatter plots reveal they are either (i) non-linearly related, (ii)
roughly linear with heteroskedastic noise, or (iii) pairwise independent but
dependent given a third variable.
Recall that CrossCat is a product of DPMMs; practically meaningful
conditions for weak and strong consistency of Dirichlet location-scale mixtures
have been established by \cite{ghosal1999,tokdar2006}.
This supports the intuition that CrossCat can detect a broad class of predictive
relationships that simpler parametric models miss.

Figure~\ref{fig:gapminder-trade} focuses on a group of four ``trade''-related
variables in the Gapminder dataset detected as probably dependent: ``net trade
balance'', ``total goods traded'', ``exports of goods and services'', and
``imports of goods and services''.
$R^2$ fails to detect a statistically significant dependence
between ``net trade balance'' and the other variables, due to weak linear
correlations and heteroskedastic noise as
shown in the scatter plots (Figure~\ref{fig:trade-scatter}).
From economics, these four variables are causally related by the graphical model
in Figure~\ref{fig:trade-graph}, where the value of a node is a noisy addition
or subtraction of the values of its parents.
Figure~\ref{fig:trade-joint-cmi} illustrates that CrossCat recovers predictive
relationships between these variables: conditioning on ``exports''{=}150 and
``balance''{=}30 (a low probability event according to the left subplot) centers
the posterior predictive distribution of ``imports'' around 120, and decouples
it from ``total goods''.
The posterior CMI curves of ``imports'' and ``total goods'', with and without
the conditions on ``exports'' and ``balance'', formalize this decoupling (right
subplot of Figure~\ref{fig:trade-joint-cmi}).

\section{Drawing Bayesian inferences about conditional mutual information}
\label{sec:bayesian-cmi}

Let $\bm{x}=(x_1,x_2,\dots,x_D)$ denote a $D$-dimensional random vector, whose
\mbox{sub-vectors} we denote $\bm{x}_\mathcal{A} = \set{x_i: i \in \mathcal{A}}$ with joint
probability density $p_{\G}(\bm{x}_\mathcal{A})$.
The symbol $\mathcal{G}$ refers to an arbitrary specification for the ``generative''
process of $\bm{x}$, and parameterizes all its joint and conditional densities.
The \textit{mutual information} (MI) of the variables $\bm{x}_\mathcal{A}$ and $\bm{x}_\mathcal{B}$
(under generative process $\mathcal{G}$) is defined in the usual way \cite{cover2012}:
\begin{align}
&\mathcal{I}_\mathcal{G}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}) =
  \mathop\mathbb{E}_{(\bm{x}_\mathcal{A},\bm{x}_\mathcal{B})}
    \left[ \log \left(
      \frac{p_{\G}(\bm{x}_\mathcal{A},\bm{x}_\mathcal{B})}
      {p_{\G}(\bm{x}_\mathcal{A})p_{\G}(\bm{x}_\mathcal{B})}
    \right)
  \right].
\label{eq:def-mi}
\end{align}
The mutual information can be interpreted as the KL-divergence from
the product of marginals $p_{\G}(\bm{x}_\mathcal{A})p_{\G}(\bm{x}_\mathcal{B})$ to the joint
distribution $p_{\G}(\bm{x}_\mathcal{A},\bm{x}_\mathcal{B})$, and is a well-established measure
for both the existence and strength of dependence between $\bm{x}_\mathcal{A}$
and $\bm{x}_\mathcal{B}$ (Section~\ref{subsec:extracting-cmi}).
Given an observation of the variables $\set{\bm{x}_\mathcal{C}{=}\hat{\bm{x}}_\mathcal{C}}$, the
\textit{conditional mutual information} (CMI) of $\bm{x}_\mathcal{A}$ and $\bm{x}_\mathcal{B}$ given
$\set{\bm{x}_\mathcal{C}{=}\hat{\bm{x}}_\mathcal{C}}$ is defined analogously:
\begin{multline}
\mathcal{I}_{\mathcal{G}}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}|\bm{x}_\mathcal{C}{=}\hat{\bm{x}}_\mathcal{C}) = \\
\mathop\mathbb{E}_{(\bm{x}_\mathcal{A},\bm{x}_\mathcal{B})|\hat{\bm{x}}_\mathcal{C}}
    \left[ \log \left(
      \frac{p_{\G}(\bm{x}_\mathcal{A},\bm{x}_\mathcal{B}|\hat{\bm{x}}_\mathcal{C})}
      {p_{\G}(\bm{x}_\mathcal{A}|\hat{\bm{x}}_\mathcal{C})p_{\G}(\bm{x}_\mathcal{B}|\hat{\bm{x}}_\mathcal{C})}
    \right)
  \right].
\label{eq:def-cmi}
\end{multline}
Estimating the mutual information between the variables of $\bm{x}$ given a dataset
of observations $\mathscr{D}$ remains an open problem in the literature.
Various parametric and non-parametric methods for estimating MI
exist \cite{moddemeijer1989,moon1995,kraskov2004}; see \cite{paninski2003} for
a comprehensive review.
Traditional approaches typically construct a point estimate
$\hat\mathcal{I}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B})$ (and possible confidence intervals) assuming a
``true value'' of $\mathcal{I}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B})$.
In this paper, we instead take a non-parametric Bayesian approach, where the
mutual information itself is a derived random variable; a similar interpretation
was recently developed in independent work \cite{kunihama2016}.
The randomness of mutual information arises from treating the data generating
process and parameters $\mathcal{G}$ as a random variable, whose prior distribution we
denote $\pi$.
Composing $\mathcal{G}$ with the function $h: \hat\mathcal{G}
\mapsto \mathcal{I}_{\hat\mathcal{G}}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B})$ induces the derived random variable
$h(\mathcal{G}) \equiv \mathcal{I}_{\mathcal{G}}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B})$.
The distribution of the MI can thus be expressed as an expectation under
distribution $\pi$:
\begin{align}
\mathbb{P} \left[ \mathcal{I}_{\mathcal{G}}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}) \in S \right]
&= \int \mathbb{I} \left[ \mathcal{I}_{\hat\mathcal{G}} (\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}) \in S \right]
  \pi(d\hat\mathcal{G}) \notag\\
&= \mathop\mathbb{E}_{\hat\mathcal{G}\sim\pi} \left[
    \mathbb{I} \left[ \mathcal{I}_{\hat\mathcal{G}} (\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}) \in S \right]
  \right].
\label{eq:mi-posterior}
\end{align}
Given a dataset $\mathscr{D}$, we define the posterior distribution of the mutual
information, $\mathbb{P}\left[\mathcal{I}_{\mathcal{G}}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}) \in S |\mathscr{D}\right]$ as
the expectation in Eq~\eqref{eq:mi-posterior} under the posterior
$\pi(\cdot|\mathscr{D})$.
We define the distribution over conditional mutual information
$\mathbb{P} \left[ \mathcal{I}_{\mathcal{G}}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}|\hat{\bm{x}}_\mathcal{C}) \in S \right]$
analogously to Eq~\eqref{eq:mi-posterior}, substituting the CMI
\eqref{eq:def-cmi} inside the expectation.

\subsection{Estimating CMI with generative population models}
\label{subsec:estimating-cmi}

Monte Carlo estimates of CMI can be formed for models expressed as
\textit{generative population models} \cite{mansinghka2015,saad2016}, a
probabilistic programming formalism for characterizing the data generating
process of an infinite array of realizations of random vector
$\bm{x}=(x_1,x_2,\dots,x_D)$.
Listing~\ref{lst:gpm-interface} summarizes elements of the GPM interface.
\begin{algorithm}[H]
\small
\floatname{algorithm}{Listing}
\caption{GPM interface for simulating from and assessing the density of
conditional and marginal distributions of a random vector $\bm{x}$.}
\label{lst:gpm-interface}
\textsc{Simulate}(%
  $\mathcal{G}$,
  query: $\mathcal{Q}{=}\set{q_j}$,
  condition: $\hat{\bm{x}}_\mathcal{E}{=}\set{\hat{x}_{e_j}}$)

\quad Return a sample $\mathbf{s} \sim p_{\G}(\bm{x}_\mathcal{Q}|\hat{\bm{x}}_\mathcal{E}, \mathscr{D}).$

\medskip

\textsc{LogPdf}(%
  $\mathcal{G}$,
  query: $\hat{\bm{x}}_\mathcal{Q}{=}\set{\hat{x}_{q_j}}$,
  condition: $\hat{\bm{x}}_\mathcal{E}{=}\set{\hat{x}_{e_j}}$)

\quad Return the joint log density $p_\mathcal{G}(\hat{\bm{x}}_\mathcal{Q}|\hat{\bm{x}}_\mathcal{E},\mathscr{D})$
\end{algorithm}
\vspace{-.5cm}
These two interface procedures can be combined to derive a simple Monte Carlo
estimator for the CMI \eqref{eq:def-cmi}, shown in Algorithm~\ref{alg:gpm-cmi}.
\begin{subalgorithms}
\small
\captionof{algorithm}{\textsc{Gpm-Cmi}}
\label{alg:gpm-cmi}
\begin{algorithmic}[1]
\Require{%
  GPM $\mathcal{G}$; query $\mathcal{A}$, $\mathcal{B}$; condition $\hat{\bm{x}}_\mathcal{C}$; accuracy $T$}
\Ensure Monte Carlo estimate of
  $\mathcal{I}_\mathcal{G}\left(
    \bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}|\bm{x}_\mathcal{C}{=}\hat{\bm{x}}_\mathcal{C}
  \right)$
\For{$t=1,\dots,T$}
  \State $(\hat{\bm{x}}_\mathcal{A}, \hat{\bm{x}}_\mathcal{B})
    \gets \textsc{Simulate}(%
      \mathcal{G}, \mathcal{A}\cup\mathcal{B}, \hat{\bm{x}}_\mathcal{C})$
  \State $m^t_{\mathcal{A}\cup\mathcal{B}} \gets \textsc{LogPdf}(%
      \mathcal{G},\hat{\bm{x}}_{\mathcal{A}\cup\mathcal{B}}, \hat{\bm{x}}_\mathcal{C})$
  \State $m^t_\mathcal{A} \gets \textsc{LogPdf}(%
      \hat{\bm{x}}_\mathcal{A}, \hat{\bm{x}}_\mathcal{C})$
  \State $m^t_\mathcal{B} \gets \textsc{LogPdf}(%
      \hat{\bm{x}}_\mathcal{B}, \hat{\bm{x}}_\mathcal{C})$
\EndFor
\State \Return $\frac{1}{T}\sum_{t=1}^T\left(
    m^t_{\mathcal{A}\cup\mathcal{B}} - (m^t_\mathcal{A} + m^t_\mathcal{B})
  \right)$
\end{algorithmic}
\hrule
\end{subalgorithms}
While \textsc{\small Gpm-Cmi} is an unbiased and consistent estimator applicable
to any probabilistic model implemented as a GPM, its quality in detecting
dependencies is tied to the ability of $\mathcal{G}$ to capture patterns from the dataset
$\mathscr{D}$; this paper uses baseline non-parametric GPMs built using CrossCat
(Section~\ref{sec:gpms}).

\subsection{Extracting conditional independence relationships from CMI
estimates}
\label{subsec:extracting-cmi}

An estimator for the CMI can be used to discover several forms of independence
relations of interest.
\paragraph{Marginal Independence} It is straightforward to see that $(\bm{x}_\mathcal{A}
\perp\!\!\!\perp_{\mathcal{G}} \bm{x}_\mathcal{B})$ if and only if $\mathcal{I}_{\mathcal{G}}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}) = 0$.

\paragraph{Context-Specific Independence} If the event
$\set{\bm{x}_\mathcal{C}{=}\hat{\bm{x}}_\mathcal{C}}$ decouples $\bm{x}_\mathcal{A}$ and $\bm{x}_\mathcal{B}$, then
they are said to be independent ``in the context'' of $\hat{\bm{x}}_\mathcal{C}$, denoted
$(\bm{x}_\mathcal{A} \perp\!\!\!\perp_\mathcal{G} \bm{x}_\mathcal{B} | \set{\bm{x}_\mathcal{C}{=}\hat{\bm{x}}_\mathcal{C}})$ \cite{boutilier1996}.
This condition is equivalent to the CMI from \eqref{eq:def-cmi} equaling zero.
Thus by estimating CMI, we are able to detect finer-grained independencies
than can be detected by analyzing the graph structure of a learned Bayesian
network \cite{shachter1998}.

\paragraph{Conditional Independence}
If context-specific independence holds for all possible observation sets
$\set{\bm{x}_\mathcal{C}{=}\hat{\bm{x}}_\mathcal{C}}$, then $\bm{x}_\mathcal{A}$ and $\bm{x}_\mathcal{B}$ are
\textit{conditionally independent} given $\bm{x}_\mathcal{C}$, denoted
$(\bm{x}_\mathcal{A} \perp\!\!\!\perp_\mathcal{G} \bm{x}_\mathcal{B} | \bm{x}_\mathcal{C})$.
By the non-negativity of CMI, conditional independence implies the
CMI of $\bm{x}_\mathcal{A}$ and $\bm{x}_\mathcal{B}$, marginalizing out $\bm{x}_\mathcal{C}$, is zero:
\begin{align}
\mathcal{I}_\mathcal{G}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}|\bm{x}_\mathcal{C}) =
  \mathop\mathbb{E}_{\hat{\bm{x}}_\mathcal{C}}\left[
    \mathcal{I}_\mathcal{G}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}|\bm{x}_\mathcal{C}=\hat{\bm{x}}_\mathcal{C})
  \right] = 0.
\label{eq:def-cmi-marginal}
\end{align}
Figure~\ref{fig:vstruct-common} illustrates different CMI queries which are used
to discover these three types of dependencies in various data generators;
Figure~\ref{fig:bql} shows CMI queries expressed in the Bayesian
Query Language.

\section{Discussion}
\label{discussion}

This paper has shown it is possible to detect predictive relationships
by integrating probabilistic programming, information theory,
and non-parametric Bayes.
Users specify a broad class of conditional mutual information queries using a
simple SQL-like language, which are answered using a scalable pipeline based on
approximate Bayesian inference.
The underlying approach applies to arbitrary generative population models,
including parametric models and other classes of probabilistic programs
\cite{saad2016}; this work has focused on exploiting the sparsity of CrossCat
model structures to improve scalability for exploratory analysis.
With this foundation, one may extend the technique to domains such as
causal structure learning. The CMI estimator can be used as a
\mbox{conditional-independence} test in a structure discovery algorithm such as
PC \cite{sprites2000}.
It is also possible to use learned CMI probabilities as part of a prior over
directed acyclic graphs in the Bayesian setting.
This paper has focused on detection and preliminary assessment of predictive
relationships; confirmatory analysis and descriptive summarization are left for
future work, and will require an assessment of the robustness of joint density
estimation when random sampling assumptions are violated.
Moreover, new algorithmic insights will be needed to scale the technique to
efficiently detect pairwise dependencies in very high-dimensional databases with
tens of thousands of variables.

\section{Application to a database of mathematics marks}
\label{appx:applications-marks}

\begin{subtable}[b]{.34\linewidth}
\tiny\bf
\setlength{\tabcolsep}{.6em}
\begin{tabular*}{\linewidth}{|llll@{\extracolsep{\fill}}l|}
\hline
\textbf{mech}
    & \textbf{vectors}
    & \textbf{algebra}
    & \textbf{analysis}
    & \textbf{stats} \\
\hline
77 & 82 & 67 & 67 & 81 \\
23 & 38 & 36 & 48 & 15 \\
63 & 78 & 80 & 70 & 81 \\
55 & 72 & 63 & 70 & 68 \\
\dots & \dots & \dots & \dots & \dots \\
\hline
\end{tabular*}
\captionsetup{width=.9\linewidth}
\subcaption{Database of mathematics marks for 88 students, where rows are
students and columns are exam scores.}
\label{subfig:marks-dataset}
\end{subtable}\hspace{.1cm}%
\begin{subtable}[b]{.34\linewidth}
\tiny\bf
\begin{tabular*}{\linewidth}{|l|@{\extracolsep{\fill}}lllll|}
\hline
\textbf{}
    & \textbf{M}
    & \textbf{V}
    & \textbf{G}
    & \textbf{L}
    & \textbf{S} \\
\hline
\textbf{M} & 1.00  & 0.33  & 0.23 & \red{0.00} & \red{0.03} \\
\textbf{V} & 0.33  & 1.00  & 0.28 & \red{0.08}  & \red{0.02} \\
\textbf{G} & 0.23  & 0.28  & 1.00 & 0.43  & 0.36 \\
\textbf{L} & \red{0.00} & \red{0.08}  & 0.43 & 1.00  & 0.26 \\
\textbf{S} & \red{0.02}  & \red{0.02}  & 0.36 & 0.26  & 1.00 \\ \hline
\end{tabular*}
\captionsetup{width=.95\linewidth}
\subcaption{Partial correlation matrix; red entries indicate statistically
significant conditional independences.}
\label{subfig:marks-pcorr}
\end{subtable}\hspace{.2cm}%
\begin{subfigure}[b]{.3\linewidth}
\begin{tikzpicture}
\coordinate (vectors-cord);
\coordinate[above = .55cm of vectors-cord] (mechanics-cord);
\coordinate[above right = .275cm and 1.5cm of vectors-cord] (algebra-cord);
\coordinate[right = 3cm of vectors-cord] (statistics-cord);
\coordinate[above right = .55cm and 3cm of vectors-cord] (analysis-cord);

\node[circle, draw] (vectors-node) at (vectors-cord) {};
\node[circle, draw] (mechanics-node) at (mechanics-cord) {};
\node[circle, draw] (algebra-node) at (algebra-cord) {};
\node[circle, draw] (statistics-node) at (statistics-cord) {};
\node[circle, draw] (analysis-node) at (analysis-cord) {};

\node[
    below = .1cm of vectors-cord,
    align = center,
] (vectors-text) {
    \tiny\bf vectors (V)
};

\node[
    above = .1cm of mechanics-cord,
    align = center,
] (mechanics-text) {
    \tiny\bf mechanics (M)
};

\node[
    below = .1cm of algebra-cord,
    align = center,
] (algebra-text) {
    \tiny\bf algebra (G)
};

\node[
    below = .1cm of statistics-cord,
    align = center,
] (statistics-text) {
    \tiny\bf statistics (S)
};

\node[
    above = .1cm of analysis-cord,
    align = center,
] (analysis-text) {
    \tiny\bf analysis (L)
};

\draw[-] (vectors-node) -- (mechanics-node);
\draw[-] (algebra-node) -- (vectors-node);
\draw[-] (algebra-node) -- (mechanics-node);
\draw[-] (algebra-node) -- (analysis-node);
\draw[-] (algebra-node) -- (statistics-node);
\draw[-] (statistics-node) -- (analysis-node);

\end{tikzpicture}
\subcaption{Undirected (Gaussian) graphical model implied by the partial
correlation matrix.}
\label{subfig:marks-graphical}
\end{subfigure}

\begin{subfigure}[b]{.45\linewidth}
\includegraphics[width=\linewidth]{resources/pdf_vectors_algebra.pdf}
\captionsetup{width=.95\linewidth}
\subcaption{Histograms from the raw dataset (top); and predictive
distributions from CrossCat (bottom).}
\label{subfig:pdf-vectors-algebra}
\end{subfigure}%
\begin{subfigure}[b]{.55\linewidth}
\includegraphics[width=\linewidth]{resources/cmi_vectors_analysis_algebra.pdf}
\captionsetup{width=.95\linewidth}
\subcaption{Posterior distribution of CMI(\texttt{vectors},  \texttt{analysis})
given various conditions of \texttt{algebra} show context-specific
dependence.}
\label{subfig:cmi-vectors-analysis-algebra}
\end{subfigure}

\caption{Using posterior CMI distributions to discover \textit{context-specific}
predictive relationships in the mathematics marks dataset
\cite{mardia1980,whittaker1990,edwards2012} which are missed by partial
correlations.
\textbf{\subref{subfig:marks-dataset}}
The database contains scores of 88 students on five mathematics exams:
\texttt{mechanics}, \texttt{vectors}, \texttt{algebra},
\texttt{analysis}, and \texttt{statistics}.
\textbf{\subref{subfig:marks-pcorr}} Modeling the variables as jointly Gaussian
and computing the partial correlation matrix indicates that (\texttt{mechanics},
\texttt{vectors}) are together conditionally independent of (\texttt{analysis},
\texttt{statistics}), given \texttt{algebra}.
\textbf{\subref{subfig:marks-graphical}} A Gaussian graphical model which
expresses the conditional independences relationships is formed by removing
edges whose incident nodes have statistically-significant partial correlations
of zero. The graph suggests that when predicting the \texttt{vectors} score for
a student whose \texttt{algebra} score is known, further conditioning on the
\texttt{analysis} score provides no additional information. We will critique
this finding, by showing that the predictive strength of \texttt{analysis} on
\texttt{vectors} given \texttt{algebra} varies, depending on the conditioning
value of \texttt{algebra}.
\textbf{\subref{subfig:pdf-vectors-algebra}} The left panel shows that when
\texttt{algebra} = 50, conditioning on \texttt{analysis} = 70 appears to have
little effect on the prediction for \texttt{vectors}. The right panel shows that
when \texttt{algebra} = 60, however, conditioning on \texttt{analysis} = 70
results in a sizeable shift of the posterior mean of \texttt{vectors} from 52 to
just under 70. This shift is consistent with the top right histogram, where
knowing that \texttt{analysis} = 70 eliminates all the \texttt{vectors} scores
in the heavy left tail.
\textbf{\subref{subfig:cmi-vectors-analysis-algebra}}
We formalize this ``context-specific'' dependence by computing the distribution
of the CMI of \texttt{vectors} and \texttt{analysis} under two conditions:
\texttt{algebra} = 50 (green curve), and \texttt{algebra} = 60 (red curve).
The red curve places great probability on higher values of mutual information
than the green curve, which explains the shift in predictive density from
\subref{subfig:pdf-vectors-algebra}. Finally, we observe that the CMI is
weakest when \textit{marginalizing} over all values of \texttt{algebra} (blue
curve), which explains why the partial correlation of \texttt{vectors} and
\texttt{analysis}, which only considers marginal relationships, is near zero.}
\label{fig:marks}
\end{figure*}

\section{Building generative population models for CMI estimation with
non-parametric Bayes}
\label{sec:gpms}

\input{figures/vstruct-common}

\input{figures/bql}

Our approach to estimating the CMI requires a prior $\pi$ and model class $\mathcal{G}$
which is flexible enough to emulate an arbitrary joint distribution over $\bm{x}$,
and tractable enough to implement Algorithm~\ref{alg:gpm-cmi} for
its arbitrary \mbox{sub-vectors}.
We begin with a Dirichlet process mixture model (DPMM) \cite{gorur2010}.
Letting $L_d$ denote the likelihood for variable $d$, $V_d$ a prior over the
parameters of $L_d$, and $\bm\lambda_d$ the hyperparameters of $V_d$, the
generative process for $N$ observations
$\mathscr{D}{=}\set{\bm{x}_{[i,1:D]}:1 \le i \le N}$ is:
\vspace{-0.1cm}
\begin{flalign*}
&\underline{\textsc{\small DPMM-Prior}}\\
& \alpha \sim \textsc{\small Gamma}(1,1)
  && \\
& \bm{z} = (z_1,\dots,z_N) \sim \textsc{\small CRP}(\cdot|\alpha)
  && \\
& \bm\phi_{[d,k]} \sim V_d(\cdot|\bm\lambda_d)
  && d \in [D], k\in\textsc{\small Unique}(\bm{z})\\
& x_{[i,d]} \sim L_d(\cdot|\bm\phi_{[d,z_i]})
  && i \in [N],d \in [D]
\end{flalign*}
We refer to \cite{escobar1995,jain2012} for algorithms for posterior inference,
and assume we have a posterior sample $\hat\mathcal{G}=(\alpha,\bm{z}_{[1:N]},\set{\bm\phi_d})$
of all parameters in the DPMM.
To compute the CMI of an arbitrary query pattern
$\mathcal{I}_{\hat\mathcal{G}}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}|\bm{x}_\mathcal{C}{=}\hat{\bm{x}}_\mathcal{C})$ using
Algorithm~\ref{alg:gpm-cmi}, we need implementations of \textsc{\small Simulate}
and \textsc{\small LogPdf} for $\hat\mathcal{G}$.
These two procedures are summarized in Algorithms~\ref{alg:dpmix-simulate},
\ref{alg:dpmix-logpdf}.
\begin{subalgorithms}
\small
\captionof{algorithm}{\textsc{\small DPMM-Simulate}}
\label{alg:dpmix-simulate}
\begin{algorithmic}[1]
\Require DPMM $\mathcal{G}$; target $\mathcal{A}$; condition $\hat{\bm{x}}_\mathcal{C}$
\Ensure joint sample $\hat{\bm{x}}_\mathcal{A} \sim p_{\G}(\cdot|\hat{\bm{x}}_\mathcal{C})$
\State $(l_i)_{i=1}^{K+1} \gets
  \textsc{DPMM-Cluster-Posterior}(\mathcal{G},\hat{\bm{x}}_\mathcal{C})$
\State $z_{N+1} \sim \textsc{Categorical}(l_1,\dots,l_{K+1})$
\For{$a \in \mathcal{A}$}
  \State $\hat{x}_a \sim L_a(\cdot|\bm\phi_{[a,z_{N+1}]})$
  \label{algline:dpmix-simulate-likelihood}
\EndFor
\State \Return $\hat{\bm{x}}_\mathcal{A}$
\end{algorithmic}
\vspace{-.3cm}

\captionof{algorithm}{\textsc{\small DPMM-LogPdf}}
\label{alg:dpmix-logpdf}
\begin{algorithmic}[1]
\Require DPMM $\mathcal{G}$; target $\hat{\bm{x}}_\mathcal{A}$; condition $\hat{\bm{x}}_\mathcal{C}$
\Ensure log density $p_{\G}(\hat{\bm{x}}_\mathcal{A}|\hat{\bm{x}}_\mathcal{C})$
\State $(l_i)_{i=1}^{K+1} \gets
  \textsc{DPMM-Cluster-Posterior}(\mathcal{G}, \hat{\bm{x}}_\mathcal{C})$
\For{$k = 1,\dots,K+1$}
  \State $t_k \gets
    \prod_{a\in\mathcal{A}}L_a(\hat{x}_a|\bm\phi_{[a,k]})$
    \label{algline:dpmix-logpdf-likelihood}
\EndFor
\State \Return
  $\log\left(\sum_{k=1}^{K+1}\left(t_{k}l_{k}\right)\right)$
\end{algorithmic}
\vspace{-.3cm}
\captionof{algorithm}{\textsc{\small DPMM-Cluster-Posterior}}
\label{alg:dpmix-cluster-posterior}
\begin{algorithmic}[1]
\Require DPMM $\mathcal{G}$; condition $\hat{\bm{x}}_\mathcal{C}$;
\Ensure $\set{p_{\G}(z_{N+1}=k):1\le{k}\le\max(\bm{z}_{1:N})+1}$
\State $K \gets \max(\bm{z}_{1:N})$
\For{$k=1,\dots,K+1$}
  \State $n_k \gets \begin{cases}
    |\set{\bm{x}_i\in\mathscr{D}: z_i=k}| & \text{if } k\le K\\
    \alpha & \text{if } k = K+1
    \end{cases}$
  \State $l_k \gets
    \left(
      \prod_{c\in\mathcal{C}}L_c(\hat{x}_c|\bm\phi_{[c,k]})
    \right)n_k$
\EndFor
\State \Return $(l_1,\dots,l_{K+1}) / \sum_{k=1}^{K+1}(l_k)$
\end{algorithmic}
\hrule
\end{subalgorithms}

The subroutine \textsc{\small DPMM-Cluster-Posterior} is used for
sampling (in \textsc{\small DPMM-Simulate}) and marginalizing over (in
\textsc{\small DPMM-LogPdf}) the non-parametric mixture components.
Moreover, if $L_d$ and $V_d$ form a conjugate likelihood-prior pair, then
invocations of $L_d(\hat{x}_d|\bm\phi_{[d,k]})$ in
Algorithms \ref{alg:dpmix-simulate}:\ref{algline:dpmix-simulate-likelihood} and
\ref{alg:dpmix-logpdf}:\ref{algline:dpmix-logpdf-likelihood} can be
\mbox{Rao-Blackwellized} by conditioning on the sufficient statistics of data
in cluster $k$, thus marginalizing out $\bm\phi_{[d,k]}$ \cite{robert2005}.
This optimization is important in practice, since analytical marginalization can
be obtained in closed-form for several likelihoods in the exponential family
\cite{fink1997}.
Finally, to approximate the posterior distribution over CMI in
\eqref{eq:def-cmi}, it suffices to aggregate
$\textsc{\small DPMM-Cmi}$ from a set of posterior samples
$\set{\hat\mathcal{G}_1,\dots,\hat\mathcal{G}_H} \sim^\textrm{iid} \pi(\cdot|\mathscr{D})$.
Figure~\ref{fig:vstruct-common} shows posterior CMI distributions from the DPMM
successfully recovering the marginal and conditional independencies in two
canonical Bayesian networks.

\subsection{Inducing sparse dependencies using the CrossCat prior}

The multivariate DPMM makes the restrictive assumption that all variables
$\bm{x}=(x_1,\dots,x_D)$ are (structurally) marginally dependent, where their joint
distribution fully factorizes conditioned on the mixture assignment $z$.
In high-dimensional datasets, imposing full structural dependence among all
variables is too conservative.
Moreover, while the Monte Carlo error of
\mbox{Algorithm~\ref{alg:gpm-cmi}} does not scale with the dimensionality $D$,
its runtime scales linearly for the DPMM, and so estimating the CMI is
likely to be prohibitively expensive.
We relax these constraints by using CrossCat \cite{mansinghka2016}, a structure
learning prior which induces sparsity over the dependencies between the
variables of $\bm{x}$.
In particular, CrossCat posits a factorization of $\bm{x}$ according to a
\textit{variable partition} $\bm\gamma = \set{\mathcal{V}_1,\dots,\mathcal{V}_{|\bm\gamma|}}$,
where $\mathcal{V}_i \subseteq [D]$.
For $i\ne j$, all variables in block $\mathcal{V}_i$ are mutually (marginally and
conditionally) independent of all variables in $\mathcal{V}_j$.
The factorization of $\bm{x}$ given the variable partition $\bm\gamma$ is therefore
given by:
\begin{align}
p_{\G}(\bm{x} |\mathscr{D}) &= \prod_{\mathcal{V} \in \bm\gamma} p_{\G_\mathcal{V}}(\bm{x}_\mathcal{V}|\mathscr{D}_\mathcal{V}).
\label{eq:cc-factorization}
\end{align}
Within block $\mathcal{V}$, the variables $\bm{x}_\mathcal{V} = \set{x_d: d\in \mathcal{V}}$ are
distributed according to a multivariate DPMM; subscripts with $\mathcal{V}$ (such as
$\mathcal{G}_\mathcal{V}$) now index a set of \mbox{block-specific} DPMM parameters.
The joint predictive density $p_{\G_\mathcal{V}}$ is given by %
Algorithm~\ref{alg:dpmix-logpdf}:
\vspace{-.1cm}
\begin{align}
p_{\G_\mathcal{V}}(\bm{x}_\mathcal{V} | \mathscr{D}) =
  \sum_{k=1}^{K_V+1} \left(
    \frac{n_{[\mathcal{V},k]}\prod\limits_{d\in \mathcal{V}} p_{\G_\mathcal{V}}(x_d|\bm\phi_{[d,k]})}
    {\sum_{k'}n_{[\mathcal{V},k']}}
  \right). \label{eq:cc-dpmm}
\end{align}
The CrossCat generative process for $N$ observations
$\mathscr{D}{=}\set{\bm{x}_{[i,1:D]}:1\le i \le N}$ is summarized below.
\begin{align*}
&\underline{\textsc{\small CrossCat-Prior}}\\
& \alpha' \sim \textsc{\small Gamma}(1,1)
  && \\
& \bm{v} = (v_1,\dots,v_D) \sim \textsc{\small CRP}(\cdot|\alpha')
  && \\
& \mathcal{V}_k \gets \set{i \in [D]: v_i = k}
  && k\in\textsc{\small Unique}(\bm{v})\\
& \set{x_{[i,\mathcal{V}_k]}}_{i=1}^{N} \sim \textsc{\small DPMM-Prior}
  && k\in\textsc{\small Unique}(\bm{v})
\end{align*}
We refer to \cite{mansinghka2016,obermeyer2014} for algorithms for posterior
inference in CrossCat, and assume we have a set of approximate samples
$\set{\hat\mathcal{G}_i: 1\le i \le H}$ of all latent CrossCat parameters from the posterior
$\pi(\cdot|\mathscr{D})$.

\subsection{Optimizing a CMI query}
The following lemma shows how CrossCat induces sparsity for a multivariate CMI
query.
\begin{lemma}
Let $\mathcal{G}$ be a posterior sample from CrossCat, whose full joint distribution is
given by \eqref{eq:cc-factorization} and \eqref{eq:cc-dpmm}. Then, for all
$\mathcal{A},\mathcal{B}, \mathcal{C} \subseteq [D]$,
\begin{align*}
\mathcal{I}_\mathcal{G} \left( \bm{x}_\mathcal{A} : \bm{x}_\mathcal{B} \mid \hat{\bm{x}}_\mathcal{C} \right) =
  \sum_{\mathcal{V}\in\bm\gamma}
    \mathcal{I}_{\mathcal{G}_\mathcal{V}}(
      \bm{x}_{\mathcal{A}\cap\mathcal{V}} : \bm{x}_{\mathcal{B}\cap\mathcal{V}} \mid \hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}}
    ),
\end{align*}
where $\mathcal{I}_{\mathcal{G}_\mathcal{V}}
  (\bm{x}_{\mathcal{A}\cap{\mathcal{V}}} : \varnothing | \hat{\bm{x}}_{\mathcal{C}\cap\mathcal{V}} )\equiv 0$.
\label{lemma:crosscat-cmi-sparse}
\end{lemma}
\vspace{-.3cm}
\begin{proof}
\renewcommand{\qedsymbol}{}
Refer to Appendix~\ref{appx:proof-optimizing-cmi}.
\end{proof}

\input{figures/runtime}

\vspace{-.3cm}
An immediate consequence of Lemma~\ref{lemma:crosscat-cmi-sparse} is that
structure discovery in CrossCat allows us to optimize Monte Carlo estimation of
$\mathcal{I}_\mathcal{G}(\bm{x}_\mathcal{A}:\bm{x}_\mathcal{B}|\bm{x}_\mathcal{C}=\hat{\bm{x}}_\mathcal{C})$ by ignoring all target and
condition variables which are not in the same block $\mathcal{V}$, as shown in
Algorithm~\ref{alg:crosscat-cmi} and Figure~\ref{fig:runtime}.
\vspace{-.2cm}
\begin{subalgorithms}
\small
\captionof{algorithm}{\textsc{\small CrossCat-Cmi}}
\label{alg:crosscat-cmi}
\begin{algorithmic}[1]
\algrenewcommand\algorithmicindent{.5em}%
\Require{%
  CrossCat $\mathcal{G}$; query $\mathcal{A}$, $\mathcal{B}$; condition $\hat{\bm{x}}_\mathcal{C}$; acc. $T$}
\Ensure Monte Carlo estimate of $\mathcal{I}_\mathcal{G}(\bm{x}_\mathcal{A}{:}\bm{x}_\mathcal{B}|\bm{x}_\mathcal{C}{=}\hat{\bm{x}}_\mathcal{C})$
\For{$\mathcal{V} \in \bm\gamma$}
  \If{ $\mathcal{A}\cap\mathcal{V} \;\; \textsc{\small and } \;\; \mathcal{B}\cap\mathcal{V}}$
    \State $i_\mathcal{V} \gets $\textsc{Gpm-Cmi}(%
      $\mathcal{G}_\mathcal{V}$,
      $\mathcal{A} \cap \mathcal{V}$,
      $\mathcal{B} \cap \mathcal{V}$,
      $\hat{\bm{x}}_{\mathcal{C}{\cap}{\mathcal{V}}}$,
      $T$)
  \Else
    \State $i_\mathcal{V} \gets 0$
  \EndIf
\EndFor
\State \Return $\sum_{\mathcal{V}\in\bm\gamma}i_\mathcal{V}$
\end{algorithmic}
\end{subalgorithms}

\subsection{Upper bounding the pairwise dependence probability}
\label{sub:crosscat-fast}

In exploratory data analysis, we are often interested in detecting pairwise
predictive relationships between variables $(x_i, x_j)$.
Using the formalism from Eq \eqref{eq:mi-posterior}, we can compute the
probability that their MI is non-zero: $\mathbb{P}\left[\mathcal{I}_{\mathcal{G}}(x_i:x_j) >
0\right]$.
This quantity can be upper-bounded by the posterior probability that $x_i$
and $x_j$ have the same assignments $v_i$ and $v_j$ in the CrossCat variable
partition $\bm\gamma$:
\begin{align}
&\mathbb{P} \left[ \mathcal{I}_{\mathcal{G}}(x_i : x_j) > 0 \right] && \notag \\
&=\mathbb{P} \left[ \mathcal{I}_{\mathcal{G}}(x_i : x_j) > 0\mid\set{\mathcal{G}:v_i=v_j} \right]
  \mathbb{P}\left[ \set{\mathcal{G}:v_i=v_j} \right] \notag &&\\
&\;\; +
    \mathbb{P}\left[ \mathcal{I}_{\mathcal{G}}(x_i:x_j) > 0\mid \set{\mathcal{G}:v_i\ne v_j} \right]
    \mathbb{P}\left[ \set{\mathcal{G}:v_i\ne v_j} \right] \notag &&\\
&= \mathbb{P}\left[ \mathcal{I}_{\mathcal{G}}(x_i : x_j) > 0\mid \set{\mathcal{G}:v_i=v_j} \right]
  \mathbb{P}\left[ \set{\mathcal{G}:v_i=v_j} \right] \notag &&\\
&<\mathbb{P} \left[ \set{\mathcal{G}:v_i=v_j} \right]
  \approx \frac{1}{H} \sum_{h=1}^H
    \mathbb{I}[\hat\mathcal{G}_h: \hat{v}_{[h,i]} = \hat{v}_{[h,j]}], \label{eq:depprob}
\end{align}
where Lemma~\ref{lemma:crosscat-cmi-sparse} has been used to set the addend in
line 3 to zero.
Also note that the summand in \eqref{eq:depprob} can be computed in $O(1)$ for
CrossCat sample $\hat\mathcal{G}_h$.
When dependencies among the $D$ variables are sparse such that many pairs
$(x_i,x_j)$ have MI upper bounded by 0, the number of invocations of
Algorithm~\ref{alg:crosscat-cmi} required to compute pairwise MI values is $\ll
O(D^2)$.
A comparison of upper bounding MI versus exact MI estimation with Monte Carlo is
shown in Figure~\ref{fig:depprob}.

\input{figures/depprob}

\section{Introduction}
\label{sec:introduction}

Sparse databases with hundreds of variables are commonplace.
In these settings, it can be both statistically and computationally challenging
to detect predictive relationships between variables \cite{data2013}.
First, the data may be incomplete and require cleaning and imputation before
pairwise statistics can be calculated.
Second, parametric modeling assumptions that underlie standard hypothesis
testing techniques may not be appropriate due to nonlinear, multivariate, and/or
heteroskedastic relationships.
Third, as the number of variables grows, it becomes harder to detect true
relationships while suppressing false positives.
Many approaches have been proposed (see \cite[Table 1]{lopez2013} for a
summary), but they each exhibit limitations in practice.
For example, some only apply to fully-observed real-valued data, and most do not
produce probabilistically coherent measures of uncertainty.
This paper proposes an approach to dependence detection that combines
probabilistic programming, information theory, and non-parametric Bayes.
The end-to-end approach is summarized in Figure~\ref{fig:workflow}.
Queries about the conditional mutual information (CMI) between variables of
interest are expressed using the Bayesian Query Language \cite{mansinghka2015},
an SQL-like probabilistic programming language.
Approximate inference with CrossCat \cite{mansinghka2016} produces an ensemble
of joint probability models, which are analyzed for structural (in)dependencies.
For model structures in which dependence cannot be ruled out, the CMI is
estimated via Monte Carlo integration.

In principle, this approach has significant advantages.
First, the method is scalable to high-dimensional data: it can be used for
exploratory analysis without requiring expensive CMI estimation for all pairs of
variables.
Second, it applies to heterogeneously typed, incomplete datasets with minimal
\mbox{pre-processing} \cite{mansinghka2016}.
Third, the non-parametric Bayesian joint density estimator used to form CMI
estimates can model a broad class of data patterns, without overfitting to
highly irregular data.
This paper shows that the proposed approach is effective on a
\mbox{real-world} database with hundreds of variables and a missing data
rate of $\sim$35\%, detecting common-sense predictive relationships that are
missed by baseline methods while suppressing spurious relationships that
baselines purport to detect.

\section{Related Work}
\label{sec:related}
\vspace{-0.1in}

There is broad acknowledgment that new techniques for dependency detection
beyond linear correlation are required.
Existing approaches for conditional independence testing include the use of
kernel methods
\cite{bach2002,fukumizu2007,zhang2011,sejdinovic2013}, copula functions
\cite{bouezmarni2012,poczos2012,lopez2013}, and characteristic functions
\cite{Su2007}, many of which capture non-linear and multivariate predictive
relationships.
Unlike these methods, however, our approach represents dependence in terms of
conditional mutual information and  is not embedded in a frequentist decision-
theoretic framework.
Our quantity of interest is a full posterior distribution over CMI, as opposed to
a $p$-value to identify when the null hypothesis CMI{=}0 cannot be rejected.
Dependence detection is much less studied in the Bayesian literature;
\cite{holmes2016} use a Polya tree prior to compute a Bayes Factor for the
relative evidence of dependence versus independence.
Their method is used only to quantify evidence for the existence, but not assess
the strength, of a predictive relationship.
The most similar approach to this work was proposed independently in recent work
by \cite{kunihama2016}, who compute a distribution over CMI by estimating the
joint density using an encompassing non-parametric Bayesian prior.
However, the differences are significant.
First, the Monte Carlo estimator in \cite{kunihama2016} is based on resampling
empirical data.
However, real-world databases may be too sparse for resampling data to yield
good estimates, especially for queries given unlikely constraints.
Instead, we use a Monte Carlo estimator by simulating the predictive
distribution.
Second, the prior in \cite{kunihama2016} is a standard Dirichlet process mixture
model, whereas this paper proposes a sparsity-inducing CrossCat prior, which
permits optimized computations for upper bounds of posterior probabilities as
well as simplifying CMI queries with multivariate conditions.

\subsubsection*{References}%
   \markboth{\MakeUppercase{\refname}}{\MakeUppercase{\refname}}%
}%

\begin{document}

\runningtitle{Detecting Dependencies in Sparse, Multivariate Databases}
\runningauthor{Saad and Mansinghka}

\twocolumn[
  \aistatstitle{Detecting Dependencies in Sparse, Multivariate Databases
  Using Probabilistic Programming and Non-parametric Bayes}

  \aistatsauthor{%
    Feras Saad \And
    Vikash Mansinghka}

  \aistatsaddress{%
    Probabilistic Computing Project\\
    Massachusetts Institute of Technology \And
    Probabilistic Computing Project\\
    Massachusetts Institute of Technology}
]

\input{abstract}

\input{introduction}

\input{bayesian-cmi}

\input{gpms}

\input{applications}

\input{related}

\input{discussion}

\clearpage

\input{acknowledgements}


text:
European Acoustics Association in the Republic of Ireland.
The Association of Acoustic Consultants of Ireland (AACI) is the European Acoustics Association's (EAA's) membership society for the Republic of Ireland, since late December 2020. This further strengthens and aligns the Republic of Ireland's involvement with our European partners, allowing for the continued development of acoustics and acoustic research within the Republic. With the UK's departure from the EU, the AACI Committee see the associate EAA membership as a strategic opportunity to progress the objectives of both the AACI and EAA within the Republic of Ireland and Europe.
The AACI seek to promote the objectives of the European Acoustics Association to promote and spread the science of acoustics, its technologies and applications throughout Europe and the entire world. The EAA seek to interface with associations whose activities are related to acoustics, in order to promote the development and progress of acoustics in its different aspects and applications.
While the AACI have strong industry-based links, it is proposed that the AACI will further strengthen links with Universities and Technical Institutes to ensure that acoustic research with the Republic of Ireland is closely aligned with the AACI and EAA.
The Committee of the AACI are delighted to embrace the objectives of the European Acoustics Association and are proud to be their membership society in the Republic of Ireland.
Acoustic Research within the Republic of Ireland
Irish Centre for Research in Applied Geoscience
IBM -SMART BAY/MARINE INSTITUTE Project
Reducing aircraft noise Trinity College Dublin

redpajama_set_name: RedPajamaCommonCrawl


So here goes... i queried the use of my electric consumption as i was constantly topping up and felt like the money i was putting in had grown legs and was running away. I looked into complaints and put a complaint it and asked for an analysis to be done on my smart meter. I wasn't expecting the results i received. According to thr paperwork thry sent me i have consumed £8337.00 in electric over thr space of 12 months. This is for a 2 bedroomed house with just myself and my child living here. I asked if i was lighting up wembley stadium in this pricr aswell. No one seems to know whats happening and i am being told that they think theres a fault with the meter and will be changing it.. in 6 weeks time.. meanwhile i have to keep watching my money grow legs and run!!. Its beeb nearly 20 days since i first put in complaint and still not been dealt with no more than day 1. Keep getting told different stories and the staff do not have a clue what they are actually doing. I am now looking into taking legal action against thid company.. so if you dont want to end up in a similar situation i would..Avoid this company like the plague!! Oh i am once again at this moment trying to get through to this company on the phone.. been listening to the same music now for 36 mins and still no ones picked phone up!!


text:
Celebrities speak out on AIDS vaccine
By AP (Associated Press),
"By all rights, I shouldn't be here today," he told delegates attending the Washington conference this week.
But people, including strangers, showed him compassion as he battled drug addiction and came to terms with his sexuality, he said.
He's now been sober for 22 years and has a loving partner and son.
He said people with AIDS deserve the same compassion and dignity he received when he "hit rock bottom".
John, who set up a foundation to fight the disease, said prevention, treatment, research


Want to Know More About Cheap Reading Glasses Near Chicago IL?
There are many types of reader glasses you can purchase in Chicago including cheap reading glasses. In case you are new to needing eyeglasses for reading or working close-up, then you will probably need a pair of men's or women's reading glasses. Once you have experienced readers, you might be searching for a product a tad more specific to your application in Illinois.
As we age, our eyes have greater difficulty focusing properly on different distances, a condition known as presbyopia. Bifocals help those who have trouble with far- and near-sightedness with lenses that have two different optical powers – one for distance, one for close up work.
Safeguarding your eyes while outdoors is very important and is especially important if you read a book or newspaper in the sunlight. There are reader sunglasses that you may buy that will protect your eyes from the glare off of pages. These are likewise available in many trendy looks to make sure that you can enjoy the latest novel at the shore without sacrificing your fashion sense.
Bifocal reader sunglasses are also easily available in many designs and color options. These have the double advantage of enabling you to read in the sun and enjoy the scenery without changing to normal sunglasses.
Magnetic readers, also known as Clics, come apart at the bridge and magnetically rejoin at the bridge. They have a built-in glasses keeper that enables them to hang around your neck for convenience. Clics are the solution to always having your reading glasses nearby even though you might not have have a place to put them in.
When space is at a premium, folding readers are the solution. These compact folding reader glasses fit in a small evening bag or pocket and are handy options that generally come with a mini carrying case that fits almost any place.
Also named trifocals, progressive reading glasses have several strengths all within one pair. These have no lines and allow the wearer to see clearly no matter if they are carrying out close work, intermediate range work or need to see clearly far away.
Readers may be purchased at most any cost range from $1 to hundreds of dollars for designer reading glasses. In case you are only starting to need reading glasses, your eye physician may advise you to buy cheap readers until your eyesight deteriorates to the point where you need customized reading glasses.
The shortcomings of cheap readers are that the frames are typically not cool and trendy, both lenses have the identical correction and the optical center of the lenses isn't specifically tailored to your eyes. Should you get headaches, nausea or notice considerable eye strain, it is recommended that you check with your eye health specialist to determine if you might need to transition to a custom prescription pair of readers.
Reading glasses specifically developed for computer monitors are called computer glasses. Computer screens release blue light which can be harmful to your eyes just like UV rays can. If you work in front of computer screens throughout the day, or you are worried about the side effects of blue light on your children's eyes, you should get these types of "blue blockers". Either prescription or non-prescription computer readers come with basic anti-reflective lenses to minimize eye strain and give 100% UV shielding.
An additional option is to get glasses with photochromic lenses that also shield from blue light and UV light. This kind of lense darkens automatically and can be utilized like reader sunglasses. These kinds of glasses are custom-made.
The best men's reading glasses and the best women's reading glasses in Chicago, IL are the ones that provide you the clear eyesight you seek with none of the downsides. Headaches, eye fatigue and blurry vision are indicators that you don't have the right glasses to do the job correctly. Take your time selecting your Cheap Reading Glasses and you will find the best solution to better reading vision.


Gondi Palace in downtown Florence was built for the Gondi Marquis, in ca. 1490 by the architect preferred by Lorenzo di Medici; Giuliano da Sangallo. The palace is a classic example of urban architecture of the high Renaissance in Florence. Among its important decorative elements are frescos on the second floor by Matteo Bonechi dated 1711. The Alcova, painted in the occasion of a marriage, was cleaned and consolidated, revealing a vibrant palette and use of gold leaf on the rich stucco decoration by Ciceri.


You wanna know what's super satisfying?
Finally beating a mission in a video game that your younger self couldn't.
With my PS2, I got myself a copy of Need for Speed: Hot Pursuit 2. While I love this game in general, there was always one mission that annoyed me to no end: the UK vs. US shootout at Desert Heat between the Aston Martin V12 Vanquish and Ford Mustang SVT Cobra R. Me being the Bond fan I am, I always picked the Vanquish.
However, due to the Desert Heat circuit's challenging semi-open-world map full of boulders and shortcuts out of nowhere, I could never quite beat that map for some reason. I would always end up losing and had to ask friends or relatives to do it for me just for the sake of proceeding. For a long, long time I vowed many a curse on that track.
Not tonight. Tonight I beat that fucker.
And I did it in a Tungsten Silver Vanquish. My prize was a Z8 as well.


Enjoy high productivity levels and amazing performance with the efficient Dell Inspiron 15 3567 B566109WIN9 Laptop. The All-in-one laptop ensures all your official and recreational needs and necessities are taken care of to give you optimum performance levels. The Superfast and powerful Processor ensures you can multitask between various applications and websites at one go and enjoy a smooth and vibrant computing experience. Feel the future with the Dell Inspiron 15 B566109WIN9 Laptop and feel the power of the Intel-driven chipset in your day to day work and enjoy lag-free awesome gaming.
The stylish and unique design of the Dell Inspiron 15 3567 B566109WIN9 Laptop grabs the attention of all tech savvy people. Finished with specially engineered material that provides this awesome gadget with strength and finesse. The Dell Inspiron 15 3567 B566109WIN9 Laptop has a sleek design that imparts efficiency, performance along with no extra weight for you to carry. The sleek gadget can be carried easily to work and other places like a coffee shop and operated. The slim bezel and light body compacts performance into one unit built to give you smooth performance with minimum occupancy of space and weight.
The Dell Inspiron 15 3567 B566109WIN9 Laptop has been designed to give you uninterrupted performance with the latest cutting edge technology incorporated into a powerful compact laptop. The powerful processor and the RAM gives you lag-free toggling between applications and games while the RAM space allows you to use the Laptop at full function. The Dell Inspiron 15 3567 B566109WIN9 Laptop has been integrated to give high performance with HD games and the large screen size delivers the full media content of websites, social media and videos for official and casual use.


The disc marks the first VH album in 14 years, and the first with David Lee Roth since 1984.
"Tattoo" has its roots in the band's unreleased mid-1970's song, "Down in Flames," as the two share the chugging riff and verse parts, with fresh lyrics added by Roth.
Van Halen: New album title revealed?
Grammys mystery no-show band revealed?
Van Halen still divided into two camps?
Van Halen cancel 2012 European tour plans?


text:
Published on Intellectual Takeout (https://www.intellectualtakeout.org) | Tom Mullen | July 9, 2018
The Supreme Court Has Destroyed the Principle of the "Consent of the Governed"
As Americans celebrated the 242nd anniversary of their secession from Great Britain, references to the Declaration of Independence ratified on July 4, 1776 were many. But while the left reminded us "all men are created equal" and the right reminded us that all inalienable rights come from our Creator, far too little attention was paid to another phrase in Jefferson's famous preamble: "deriving their just powers from the consent of the governed." Judging from the way most Americans talk, almost no one remembers how that consent is supposedly obtained.
Hint: It isn't from voting, but that's what most Americans seem to believe. According to this narrative, representatives are elected democratically, and by casting one's vote, one consents to whatever legislation the representatives who win the election choose to pass, or whatever executive actions the elected president chooses to take. In the aftermath of Obamacare's passage, surrogates for President Obama often justified that new federal endeavor with the quip, "That's why we have elections." Conservatives employ the same reasoning when their candidates win.
That raises the question: Why did the framers bother with Sections 8, 9 and 10 in Article I, Sections 2, 3 and 4 in Article II, or Sections 2 and 3 of Article III? Why did they include Article V at all?
The answer is that the aforementioned sections define the list of powers the people were consenting to, all others being reserved to the states or the people, while Article V was provided as the one and only means for the people to consent to any new powers. Put another way, any power exercised by the federal government that is not among those delegated in the Constitution is power exercised without the consent of the governed.
So, determining what the federal government should do is not "why we have elections." Elections merely decide who will exercise powers already granted.
Even this standard for establishing consent of the governed requires an extremely elastic interpretation of the word "consent." In the end, ratification of the Constitution itself and subsequent amendments were just another series of majority votes, each posing all the dangers to individual rights that any democratic process poses. That makes legislating without meeting even this low standard for consent even more egregious.
The word "unconstitutional" tends to obscure what's really going on when the black robed high priests in Washington retire to deliberate on some new constitutional challenge. It's such a stuffy, academic-sounding word that well-meaning people probably honestly believe it's better left to the finest legal minds to determine. But what judicial review really purports to do is determine if anyone ever consented to the power being exercised by the law or executive action in question. And if the power is not listed in the original Constitution or a subsequent amendment, the answer is "no."
That means that when the Supreme Court ruled as "constitutional" Social Security, Medicare, federal drug laws and myriad other federal legislation, it was ruling that the ratifying conventions of 1787-90 consented to the federal government having those powers right from the beginning.
That seems ludicrous, doesn't it?
The Constitution is not written in a dead foreign language or legalese. It's written in plain English, in a manner "We the People" can understand. It doesn't take the finest legal minds in the country to determine which powers are granted and which are not. It's all there in black and white. In fact, because it's so unambiguously written, the court has had to rule constitutional most of what the federal government does outside of the military under the power granted in the Commerce Clause, which was originally proposed and ratified mainly in reaction to states erecting their own tariffs.
The assertion that by granting the federal government the power to regulate interstate commerce, 18th-century Americans were consenting to allow the federal government to force them to participate in a federal pension program, monopolize all health insurance for people over 65 years of age, prohibit possession or ingestion of certain plants, and even to mandate how much water Americans could have in their toilet bowls, is absurd. With few exceptions, the history of judicial review is the history of an unelected group of judges lending legitimacy and legal sanction to the federal government seizing vast new powers without the consent of the governed.
Prior to Donald Trump's election, this writer heard from many conservatives and libertarians that they would vote for Trump solely based on their fear that Hillary Clinton could appoint replacements for several aging SCOTUS judges. Many believed the ancient right to bear arms could be lost based solely on this. Two years into Trump's term, with one appointment confirmed and Anthony Kennedy retiring from the Court, liberals now decry the imminent threat to "reproductive rights," gay marriage and other progressive pillars. Their rhetoric and actions are becoming increasingly violent.
Surely, the founders never intended for the election of one man or woman to so profoundly change the legal framework of the entire nation, one way or another. This is the fruit of violating not only a set of rules spelled out in the Constitution, but for violating the fundamental principle that underpins the entire document: that the federal government will exercise no power not delegated to it, i.e., without the consent of the governed.
Strict constructionists since Jefferson have argued even judicial review itself is a power nowhere delegated to the federal government. That's one of the very few powers upon which there is room for argument on both sides. But whether the power was granted or not, history clearly shows it has been used to undermine one of the most important principles of the American republic.
Here's a useful rule of thumb. If it takes nine judges dozens of pages of legalese to explain how the Constitution grants a power in question to the federal government, then we should assume the power isn't there. If there is any question at all, an amendment to the Constitution should be offered to determine if the people really do consent. That goes for all previous rulings by SCOTUS on constitutionality. If we really believe in consent of the governed, why not be sure?
Most of what the federal government currently does wouldn't pass the test. That probably scares the heck out of a lot of people, but it really shouldn't. It would simply allow blue states to govern themselves in much bluer fashion and red states to do so in much redder fashion. That's by no means a perfect solution, but it would be highly preferable to the imminent civil unrest—or worse—Americans currently face as a result of letting the federal government do whatever it wants.
This article was originally published on FEE.org. Read the original article [1].
[Image Credit: Collection of the Supreme Court of the United States]
Source URL: https://www.intellectualtakeout.org/article/supreme-court-has-destroyed-principle-consent-governed
[1] https://fee.org/articles/the-supreme-court-has-destroyed-the-principle-of-the-consent-of-the-governed/


text:
Q: Plotting spectral signature of training data from a supervised classification in GEE I need to plot the spectral signature of training data in each of the 8 classes of the supervised classification script I wrote in GEE.
The variable 'training_points' is made of sample points I selected in GEE interface and I merged them using:
var Training_Points = Water.merge(Residential).merge(Agricultural).merge(Arbusti).merge(BoschiMisti).merge(Latifoglie).merge(Conifere).merge(BareSoil);

The variable 'input 'is an imagecollection as:
var input = ee.Image(mean_Summer_IC);

Then I used these two variables in the script below:
//Create training data
var train = input.sampleRegions({
  collection: Training_Points,
  properties: ['land_class'],
  scale: 10,
  tileScale: 2
});

var BANDS = input.bandNames()
var numBands = BANDS.length()
var bandsWithClass = BANDS.add('land_class')
var classIndex = bandsWithClass.indexOf('land_class')

// Use .combine() to get a reducer capable of
// computing multiple stats on the input
var combinedReducer = ee.Reducer.mean().combine({
  reducer2: ee.Reducer.stdDev(),
  sharedInputs: true})

// Use .repeat() to get a reducer for each band
// We then use .group() to get stats by class
var repeatedReducer = combinedReducer.repeat(numBands).group(classIndex)

var Training_PointsStats = train.reduceColumns({
    selectors: BANDS.add('land_class'),
    reducer: repeatedReducer,
})

// Result is a dictionary, we do some post-processing to
// extract the results
var groups = ee.List(Training_PointsStats.get('groups'))

var classNames = ee.List(['Water','Residential', 'Agricultural', 'Arbusti', 'BoschiMisti', 'Latifoglie', 'Conifere', 'BareSoil'])

var fc = ee.FeatureCollection(groups.map(function(item) {
  // Extract the means
  var values = ee.Dictionary(item).get('mean')
  var groupNumber = ee.Dictionary(item).get('group')
  var properties = ee.Dictionary.fromLists(BANDS, values)
  var withClass = properties.set('class', classNames.get(groupNumber))
  return ee.Feature(null, withClass)
}))

// Chart spectral signatures of training data
var options = {
  title: 'Average Spectral Signatures',
  hAxis: {title: 'Bands'},
  vAxis: {title: 'Reflectance',
    viewWindowMode:'explicit',
    viewWindow: {
        max:0.6,
        min:0
    }},
  lineWidth: 1,
  pointSize: 4,
  series: {
    0: {color: '105af0'},
    1: {color: 'dc350a'},
    2: {color: 'caa712'},
    3: {color: 'b9ffa4'},
    4: {color: '369b47'},
    5: {color: '21ff2d'},
    6: {color: '275b25'},
    7: {color: 'f7e084'},
}};

// Default band names don't sort propertly
// Instead, we can give a dictionary with
// labels for each band in the X-Axis
var bandDescriptions = {
  'B2': 'B2/Blue',
  'B3': 'B3/Green',
  'B4': 'B4/Red',
  'B5': 'B5/Red Edge 1',
  'B6': 'B5/Red Edge 2  ',
  'B7': 'B7/Red Edge 3  ',
  'B8': 'B8/NIR',
  'B8A': 'B8A/Red Edge 4    ',
  'B11': 'B11/SWIR-1',
  'B12': 'B12/SWIR-2'
}

// Create the chart and set options.
var chart = ui.Chart.feature.byProperty({
  features: fc,
  xProperties: bandDescriptions,
  seriesProperty: 'class'
})
.setChartType('ScatterChart')
.setOptions(options);

print(chart)

var classChart = function(land_class, label, color) {
  var options = {
  title: 'Spectral Signatures for ' + label + ' Class',
  hAxis: {title: 'Bands'},
  vAxis: {title: 'Reflectance',
    viewWindowMode:'explicit',
    viewWindow: {
        max:0.6,
        min:0
    }},
  lineWidth: 1,
  pointSize: 4,
  };

  var fc = train.filter(ee.Filter.eq('land_class', land_class))
  var chart = ui.Chart.feature.byProperty({
  features: fc,
  xProperties: bandDescriptions,
  })
.setChartType('ScatterChart')
.setOptions(options);

print(chart)
}
classChart(0, 'Water')
classChart(1, 'Residential')
classChart(2, 'Agricultural')
classChart(3, 'Arbusti')
classChart(4, 'BoschiMisti')
classChart(5, 'Latifoglie')
classChart(6, 'Conifere')
classChart(7, 'BareSoil')

and I keep receiving errors:

Cannot read properties of undefined (reading 'properties')
List.get:List index must be between 0 and 7, or -8 and -1.  Found 8.

the series is indeed set from 0 to 7 so I cannot understand why I keep getting this error.
The link to the whole script is here starting from Line 647:
https://code.earthengine.google.com/d613222ee468a9afa8abf917b95844ac?accept_repo=users%2Fessepratico%2FPratico_et_al_RemoteSensing_2021

A: I solved the error by adding these lines to the script:
Training_Points = Training_Points.remap({
  lookupIn: [1, 2, 3, 4, 5, 6, 7, 8],
  lookupOut:[0, 1, 2, 3, 4, 5, 6, 7],
  columnName: 'land_class'
})

redpajama_set_name: RedPajamaStackExchange


text:
Title: The New Zealand Wars: A History of the Maori Campaigns and the Pioneering Period: Volume II: The Hauhau Wars, 1864–72
Author: James Cowan, F.R.G.S.
Publication details: R. E. Owen, 1956, Wellington
Part of: New Zealand Wars (1845–1872)
This text is the subject of:
Letter from James Cowan to Horace Fildes, 16 December 1922
Letter from James Cowan to Horace Fildes, 14 June 1922
The New Zealand Wars: A History of the Maori Campaigns and the Pioneering Period: Volume II: The Hauhau Wars, (1864–72)
THE SIEGE OF TE TEKO
Intelligence had now reached Major Mair that the principal body of the Hauhaus had taken up a position at Te Teko, some twenty-five miles inland, where they had entrenched themselves strongly on the Rangitaiki River. The war-canoes were manned and the force was moved up against the strong current, and presently sat down in front of Te Teko and considered the strength of the enemy. The position occupied by the Hauhaus was a large pa, with the usual firing-trenches and a stout double line of palisading, abutting on the steep west (left) bank of the Rangitaiki, a mile and a half above the large settlement Kokohinau. page 99
From a drawing by Major-General Gordon Robley, in "Illustrated London News."]
Matata Pa after its Capture by the Arawa, 1865
In the background is the niu, the Hauhau mast of worship, with a carved rupe, or dove, on the truck.
The lines of the fortification can still be traced in a grass paddock about 200 yards in rear of the present hotel and store at the small township of Te Teko, on the main road from Rotorua to Whakatane.
On reconnoitring the Hauhau stronghold Mair saw that it was not practicable to take it by assault, and he therefore decided to approach it by sap. He had closely observed the military engineers' methods in the sap at Orakau in the previous year, and proceeded to apply them to the reduction of Te Teko. His examination of the pa showed that the position had been very skilfully fortified. The main palisade, the kiri-tangata, stood about 10 feet high, composed of split totara timbers set closely together, and practicably unassailable by a storming-party. The main gateway in the fort faced west. At the rear there was a well-designed covered way to the water, cut obliquely down the bank of the river, here about 20 feet high. It was excavated out of the bank, and it sides were reinforced with strong totara posts; it was roofed over with slabs, which were then covered with earth. There was also a small palisaded dockyard for the canoes at the page 100 foot of the river-bank connected with the river gate. The position of the Hauhaus was made doubly strong by the support of a small pa, called Pa-harakeke, erected on the opposite bank of the river, within close range of Te Teko. The garrison of Te Teko totalled about one hundred and seventy men and youths; with them were a large number of women and children. Mair's force, drawn from the principal tribes of the Arawa, and including some of the Ngati-Tuwharetoa from Taupo, was between four hundred and five hundred strong.
In approaching the pa by sap Major Mair profited by what he had seen at Orakau—and, indeed, improved upon it. He observed that an old river-bed of the Rangitaiki, considerably higher than its present channel, described a great arc westward of the pa, curving round from south to north and meeting the river again some hundreds of yards below the enemy's position. This depression he selected as his base of attack. Five lines of sap were opened on the eastern brink of the old river-course (now marked by a grove of tall eucalyptus). Each sap was allotted to a tribe or large hapu, and the rivalry thus engendered produced intense competition in the trench-digging. The most southerly line of sap was given to Ngati-Pikiao, the strongest section of the Arawa engaged; and, although it was somewhat longer than the other trenches, it reached the palisades first. It was carried in a zigzag course in a line between Mount Edgecumbe and the south-west bastion of the pa. After commencing this sap Mair set his men to work on a trench parallel with the front face of the pa and about 100 yards distant from it. This parallel served as a base communication trench, and from it four other saps were opened out at varying distances.
The several lines of approach by sap were allotted to the tribes in this order, beginning with the southernmost trench directed towards the south-west angle: (1) Ngati-Pikiao, Ngati-Uenukukukopako, and Ngati-Tarawhai (of Maketu, Rotoiti, and Rotorua); (2) Ngati-Whakaue, of Ohinemutu, Rotorua; (3) Ngati-Rangiteaorere and some of Ngati-Uenukukukopako (Rotorua); (4) Ngati-Rangiwewehi (of Awahou, Rotorua); (5) Ngati-Tuwharetoa (from Taupo) and Tuhourangi (Te Wairoa, Tarawera). A large number of Ngati-Rangitihi were incorporated with the various trench-parties.
As these saps were advanced towards the stockade, demiparallels about 10 feet in length were opened out at short distances apart, on either side alternately, and marksmen took post there to cover the work of the trench-diggers. The main communication trench was also filled with musketeers. The head of each sap was just wide enough for one digger; three or four would be behind him deepening it to about 4 feet, while the rest of the page 101 people were engaged in keeping down the Hauhaus' fire from the pa. Women as well as men toiled and fought. Among the Ngati-Uenukukopako hapu who joined with Ngati-Pikiao in driving the southern sap diagonally towards the pa was Heni te Kiri-karamu (Heni Pore). When she was not digging she was firing in one of the covering-parties. Another dauntless wahine was Ana Pene, from Te Ngae, Rotorua. She was conspicuous for her fearlessness in exposing herself to fire and urging the warriors on. "While the saps were being dug," narrates Heni, "each tribe and hapu striving furiously to be the first to reach the foot of the palisade, Ana Pene and several of the other Arawa women climbed on to the roofs of the whares built on the level ground outside the trench-lines, and loudly encouraged their men by chanting battle-songs and urging them to be strong and brave. High above all the noises of the battlefield we heard the penetrating voice of Ana Pene. When the firing was hottest she stood on top of a hut, heedless of the Hauhau bullets, shouting 'Riria, e te iwi, riria!' ('Fight on, O tribe, fight on!') and similar inspiring calls that heartened us all up and gave more vigour to the diggers' arms. Ana's husband and two brothers were among the fighters."
Another exciting scene was a daredevil demonstration made one day by an Arawa named Hakawa. This man, a tall tattooed old fellow from Ohinemutu, came to Mair and asked for some yards of white calico. (This material was used for making bands, which all the Arawa wore about their brows to distinguish them from the Hauhaus when in action.) The commander gave him 4 yards of the stuff. Hakawa stripped naked, painted himself all over with kokowai (red ochre mixed with shark-oil), tied the white calico round his head, leaving the great part of it streaming out behind him, and completed his alarming outfit by sticking turkey-feathers in the turban band all round his head. Then, painted like a Red Indian, he rushed out to the open and went dashing at the top of his speed up and down in front of the pa, within close range, leaping from side to side, shouting words of insult at the enemy, and uttering short sharp yells or thrusting his tongue out in derision and defiance. Bounding furiously from side to side, he went the length of the pa-front several times, his calico head-streamer flying behind him like a pennant. Hundreds of shots were fired at him under the foot of the outer stockade by the astonished Hauhaus in their trench, but he escaped untouched. Major Mair, hearing the cheering and laughing and the great fusilade from the pa, went out to discover the cause of the uproar, and with difficulty recalled Hakawa, who was hugely enjoying himself. When Mair demanded the meaning of the remarkable exhibition the old warrior explained, with an amusing. page 102 naïveté, that his object was to induce the enemy to waste all their ammunition firing at him, so that the Arawa presently would be able to storm the place. He was surprised when Major Mair vetoed his spectacular tactics. Mere crazy bravado as it seemed, however, Mair privately recognized it as a really brave bit of self-sacrifice. Hakawa used to declare afterwards that the rebels wasted three hundred cartridges on him.
It became necessary to silence Pa-harakeke, the small fort on the opposite bank of the Rangitaiki, whose garrison kept up a harassing fire on the sappers approaching the angles of the main stronghold. Major Mair called for volunteers for the task, and a party of about twenty of the best fighters of Ngati-Pikiao crossed the river—several in a small canoe which Mair had captured, and the rest by swimming, using one hand to swim and carrying their loaded rifles, muzzles down, in the other, gripped half-way up the barrel to keep the charges dry. Three of the warriors—Te Pokiha, Mita te Rangi-tuakoha, and another man—on reaching the western bank under the pa, went up and demanded the surrender of the place, wishing to obtain peaceable possession of it if possible in order to avoid the necessity of shooting several of their kinsmen who were among the garrison. Maraki, a connection of the Ngati-Pikiao chiefs, was in charge of the pa. He and his companions surrendered. Freed from the annoying fire across the river, Mair's sappers pushed on more rapidly. When the fifth sap had passed the north angle of the pa (the end nearest the present road) Major Mair worked down the bank and towards the covered way which led to the river and succeeded in cutting off the garrison from their water-supply.
The sappers of Ngati-Pikiao, being the most numerous clan, were the first to carry their trench close up to the stockade. They were within a few feet of the south-west flanking salient, and prepared for the assault. Strong ropes of flax were plaited, and stones of 4 lb. or 5 lb. weight were made fast to them, with the intention of throwing them over the palisades and hauling down sections of the fence by united pulls. In the other saps the men were working away furiously, while the covering-parties continued their heavy fire on the stockade. The defenders of the fort were now running short of ammunition, and they were troubled also by the difficulty of obtaining water.
All was ready for the assault when Te Pokiha (Major Fox, the principal fighting chief of Ngati-Pikiao) called out to the garrison from the head of the sap, "Where are the Tawera?" He wished to give that hapu a last chance to escape the slaughter. "Come out, Te Tawera, that you may be saved!" The effect exceeded Pokiha's expectations. A white flag was displayed, and the whole garrison surrendered.
Major Mair ordered the Hauhaus to file out and lay down their arms. As they came out of the gateway one by one, headed by their dejected chiefs, their heads bowed in humiliation, the Arawa sprang up from their works, hapu by hapu, and leaped into the action of a furious war-dance, with choruses of tremendous volume. Ngati-Pikiao and their related hapus chanted, as they danced, the ancient battle-song beginning "Koia ano te peruperu," accompanying their tremendous rhythmic shouting with appropriate action, raising their guns, held horizontally in front of them, up above their heads and down again, in time to the words. Then they chanted, in another measure, the famous old war-song "Kia kutia, au au!" The Taupo men, with the Tuhourangi, burst into their great battle-song. "Uhi mai e waero," to the action of a leaping performance in which they jumped in perfect time high off the ground, their legs doubled under them like birds on the wing, facing this way and then that, with their guns gripped by the barrel, uplifted at arm's length. Then the tribes united in one grand war-song of triumph, delivered with terrific leap and stamp, in front of their silent captives.
Several of the Hauhau garrison had been killed in the three days siege, but the Arawa lost no men. Major Mair had a narrow escape. Towards the end of the fighting he was in the head of the Ngati-Pikiao trench, within 5 yards of the outer palisade, when a man fired at him from the trench inside the main stockade. The bullet probably struck a post of the pekerangi (the outer stockade) and was thereby given a jagged edge, for in its course it was momentarily entangled in Mair's long beard and tore some of his whiskers out by the roots. The shock and the excruciating pain caused Mair to imagine at first that part of his jaw had been carried away.
The prisoners were escorted down to the Arawa headquarters camp at Matata, where another war-dance of victory celebrated their arrival, and then Major Mair marched about a score of the principal offenders to Opotiki for trial by court-martial. Among the men captured was Horomona (Solomon), one of the Paimarire prophets from Taranaki, the chief instigator of the murder of Mr. Fulloon. He was a venerable man with long snow-white hair and beard, a mystic and sage of the ancient type. Horomona was born at Moturoa, the present site of New Plymouth. Other Hauhaus captured included the chief Te Hura, and Kirimangu and the boy Penetito who had been concerned in the death of Fulloon. Heni Pore described a lively incident which followed the arrival of captors and prisoners at Matata. When the force marched into the headquarters pa, Te Hura was attacked by the Arawa chieftainess Puhou, of Maketu, whose nephew Tamarangi had been killed at Mana-Whakatane, opposite Te page 104 Matapihi, in the swamp skirmishing. Puhou, in a furious state of rage and grief, declared that she would have revenge for her young relative's death. Clothed only in a waist mat and armed with a whalebone patu, she rushed up to the captured chief Te Hura as he sat on the marae. She caught him by the hair, violently rated him, and would have killed him with the sharp-edged club had she not been prevented forcibly. Te Hura said not a word, and made not a move all the time, says an eye-witness; he sat there like a statue.
The Arawa expeditionary force followed up their success by scouring the Hauhau country in the Whakatane Valley and looting horses and other property and foraging for food. They returned along the Orini Stream to Matata with canoe-loads of potatoes, kumara, and taro. The Ngati-Rangitihi clan and a section of Tuhourangi and Ngati-Tarawhai occupied Matata, which was given them for their military services, and Ngati-Pikiao and the other hapus marched home to Maketu and Rotorua.
The trial of the principal captured Hauhaus took place in Auckland, and on the 17th May, 1866, five of the prisoners—Horomona the prophet, Mikaere Kirimangu, Mokomoko, Heremita Kahupaea, and Hakaraia te Ruwhi—were executed in Mount Eden Prison. Young Penetito and Hekara, who had been sentenced to death, were reprieved on account of their youth, and later were pardoned. Penetito in 1922 was living at Te Teko. He served under Captain Preece in the last campaign (1871–72).
Te Uhi, a Whakatane chief with a reputation as a worker of witchcraft, was one of those who surrendered to the European force at Opotiki. For his complicity in the cutting-off of the "Kate" and the killing of Fulloon and the crew he was sentenced to imprisonment. Te Uhi died at Opotiki in 1886; he imagined he was makutu'd, or bewitched, by a more powerful tohunga, and his fears killed him.
The southern trench at Te Teko, which was the longest, is the best marked of all the lines of sap to-day. In spite of repeated ploughings it is easily traceable in a line from the south-west bastion of the pa towards the volcanic peak of Mount Edgecumbe, which dominates the landscape. A large blue-gum tree is growing in the older war-sap, about 60 yards from the pa. The south-west flanking bastion towards which this trench was directed is the most distinct section of the pa-lines. The line of the main communication trench in the grove of eucalyptus, and two of the other four lines of sap dug towards the stockades, are also still traceable on exploring the ground.
Captain Preece in the early "seventies" occupied Te Teko as a military post with his No. 2 Company of the Arawa Flying Column, and built a redoubt.
Mr. F. Burt, who for many years farmed the Matapihi Block, with the pa on it, in the low-lying Matata country, writes as follows on the subject of the fortified places in the great Rangitaiki Swamp: "I have inquired of the natives and they state that Te Matapihi and Oheu are the places to which the Hauhaus went after the Battle of Kaokaoroa. The brother of Wharepapa (of the Tawera Tribe) was killed at Oheu. He was shot by Major Mair as he stood up on the parapet of Oheu pa. Major Mair was at a spot called Rangatai. Tamarangi climbed up a peach-tree at Mana-Whakatane, opposite Matapihi (westerly), and was shot from the pa; the distance would be half a mile at least. These Maoris must have had some 'go' in them in the old days. From Matapihi to Tiepataua they had a good solid road made. One part ran through the swamp, which was fairly deep, starting from the pa, across to Mana-Whakatane. They had a road made across, and a bridge near the end to let the water through; the piles are there now, totara and puriri. I cut a piece off to see what it was like, and the timber is as good as the day it was put there. Evidently they made the foundation of the road with large pumice blocks and then put earth on top (there is even now a great quantity of pumice boulders round about these parts), but how they carted the earth I do not know. This part of the road is about half a mile long; it is now fairly dry on account of the dredge-cut the Government put up to tap the Awakaponga Stream. I have found the remains of guns and revolvers on Matapihi. The natives tell me when they were spearing eels near the Kohika Lake they came across the remains of an old pa, so there was evidently one between Oheu and the Kohika. Omeheu Island is about three or four miles from the Rangatai, and I should say it must have been a great stronghold in the old days, as it is (or was) entirely surrounded by swamp."


text:
Could Arjen Robben get one last shot with Netherlands at Euro 2020?
By Michel Nasrallah
In October 2017, Arjen Robben decided to retire from international football after his country missed out again on a second consecutive major tournament. Fourteen years of being the main man of the "Orange Eleven" ended in a tragic, unexpected and heartbreaking way. Netherlands watched the World Cup at home, vowed to be back and Ronald Koeman took over. Robben ruled out any chance of returning to Oranje earlier in 2018 after the new manager had a talk with him in Munich. At the end of last season, and after countless injuries during his career, most of which were serious and resulted in lengthy spells, the Dutch speedster decided to hang up his boots for good.
Also Read: Two Stripes: Why Johan Cruyff played the 1974 World Cup with a two striped Adidas kit
However, so much can happen in a year. Due to COVID-19, Euro 2020 has been postponed and the Glassman has decided to come out of retirement and intends to play for his childhood club FC Groningen. "Arjen has indicated himself that he has stopped at Oranje," said Koeman. "As long as that doesn't change, there isn't really anything to talk about." While Koeman's intention behind the words are not clear, he will be letting Robben have the final say.
Under Koeman, new look Oranje have done well so far. They topped a Nations League group by beating the last two World Champions and made it all the way to the Final, and qualified easily to Euro 2020. That success in no way is an indication that Koeman will rely on youth and therefore will have no place for Robben next summer.
One of the mistakes that most coaches make is looking at short tournaments (Euro or World Cup) the same way they look at Champions League or a National League. In short tournaments, one cannot bank on a promising talent who might have a bright future. Developing talents is taken care of at the club level but in National Teams, you only need players who can make a difference or add something to the group. The international scene is no place to learn. In a Euro championship or a World Cup, a team does not play every week for 9 months. It can play up to 7 matches in just a month or it can be all over in less than a week. The perception of the coach should be totally different and hence, the choice of the players.
During the Nations League and the European qualifiers, and specifically against top teams, Koeman has always called up a squad of 30 or more players at first, eventually reducing it to 23. He will stick to the exact same method in May 2021 when he names the squad that would look to secure a second title in their history. These 23 players are divided as into 3 goalkeepers, 8 defenders and 6 midfielders, paving the way for just 6 wingers/forwards.
Based on an analysis of all the matches Netherlands have played in the past 2 years, the most forwards who earned playing time when fit were Depay, Promes, Bergwijn and Babel. Koeman will surely have faith in these players as it proves to be an international football culture to head into a tournament with the players who helped the most during its qualifiers. Luuk De Jong didn't play much but he was always called up and preferred over Weghorst.
Also Read: Denied promotion despite being 25 points ahead, Stowmarket Town FC look forward to the future
Koeman is no longer starting with these types of forwards, but needs just one to complete the 23 man squad. He will look for someone who would provide an aerial threat and advantage when the team is dominating the final third of the opponent desperately searching for a goal, and playing long balls in the final minutes instead of building up from behind. It worked just fine with Luuk twice – against Germany in the Nations league second leg and against N. Ireland in Rotterdam. His place looks secure. One more place remains up for grabs and Arjen Robben, if fit, will compete with Malen, Kluivert, Danjuma, Dilrosun, Berghuis, Stengs and Boadu. It has to be noted that any injury for any of the starters will slightly increase Robben's chances of a comeback.
Robben's skills are no secret to anyone. Speed, dribbling, cutting inside, a deadly left foot and accurate crosses are just a few things he bring to the team. However, it takes hunger to win and the right mindset to still be on the same pedestal. After being the main Orange player who could alter the outcome of a match on his own in a moment of pure brilliance for so many years and single-handedly taking the Dutch to the third place at the 2014 World Cup, it is unlikely that Robben would settle with the way he retired from international duty. A careful dissection of his on-pitch character throughout the years would assure anyone that the injury prone winger is gutted, and if fit, will grab on to that one last chance for glory.
One might think that a footballer's skills remain intact if he changes shirts. While that is logically correct, his efficiency may not necessarily be at the same level that it once was. The psychological factors that affect a player's performance are being studied more deeply. Fitness, it is often said, is now 50% physical and 50% mental. Mentality plays an equally important role as the physical.
Also Read: The road ahead for Timothy Fosu-Mensah
How many football players today understand what it really means to play in national colours or give their National Team more than their club? That is a long debate that could only be launched on a case-by-case basis. To put it into perspective, the greatest Dutch icon of all times Johan Cruyff played just one World Cup for his country, whereas another Dutch legend, the 1992 FIFA world player of the year and the 3 times Ballon D'Or winner Marco Van Basten, scored his last goal for his country at a major tournament at the age of 24.
Another Ballon D'Or winner, a star and the captain of his generation, Ruud Gullit, walked out of the Dutch pre-tournament training camp and never played for his country ever again just before the 1994 World Cup that was already missing Van Basten. A dispute with coach Dick Advocaat about playing on the right wing or in a more central position led to a reckless and absurd decision that he regretted 19 years later on a Dutch TV program. "I don't feel Dutch," said one of the most decorated Dutch players and one of Europe's best midfielders, Clarence Seedorf, before announcing that he won't take part at Euro 2008 despite being selected by Van Basten.
Also Read: Road to Nowhere: Why success at U17 World Cup means so little
It is best not to engage in controversial debates of comparing players from different generations, but the pride and honor that a player feels when wearing a the national shirt are easily detected. Arjen Robben certainly embodies the spirit of playing for his country more than the four legends mentioned above. Robben holding back his tears during the National Anthem in his last match against Sweden meant a lot for Dutch fans who are used to seeing similar behaviour and emotions from Dutch players when they are playing their last match for the club.
He was hit by misfortune during the last friendly against Hungary in the build-up to the 2010 World Cup. A hamstring tear was threatening his participation. They won this friendly 6-1 but the mood in the camp and the whole country was anything but happy. Robben literally made the medically impossible to regain fitness in time and travel with the squad to South Africa. A TV report following his recovery process showed an emotional Robben trying again, unsuccessfully this time, to hold back his tears. The rest is history.
Ever since he came on as a substitute in the 73rd minute in the third group stage match against Cameroon and all the way to the final, he was lethal and decisive. It is worth noting that few weeks later, Bayern Munich stated that medical tests confirmed that his injury had not been properly healed and that he would miss at least two months. He missed more than that. Bayern Munich and the Dutch Football federation went to court over this.
What can he offer?
In a UEFA European Championship with 24 teams, at least 8 teams have equal chances of lifting the trophy. Netherlands are, this time, among these eight. Very small details in modern football decide the outcome of the game. Any coach will surely emphasise on this, but it is only up to the player to carry out the execution. Koeman will need an experienced player who has mastered this and someone that has played for so many years at the highest level for both club and country.
Also Read: Dutch Vs Deutsch: An inherent difference between Performance & Achievement
Arjen Robben doesn't need to start every game but he would certainly be required to step in at crucial moments. A perfect cross, a well taken corner or penalty, one dribble that can shake a solid defensive block, the courage and confidence to shoot from long distance, drawing a foul that would probably earn a free kick or cause a booking for the opponent, exchanging the right words with the referee and so on, are all the trivial details that make the difference between qualifying for the next round or going back home. One cannot expect an exquisite and flawless execution of these by Stengs, Dilrosun or Kluivert. A fit Robben is the final piece of the puzzle for this new-look-Oranje. His role can be vital on and off the field. His participation is key to a better ambience, better expectations and better results. He would not care about the shirt number or the captain's armband, he's too old and too professional for that.
At one point or another, Koeman has to make the call. The final decision will not only depend on the coach's perception and philosophy, but also his ego since Robben denied the chance two years ago. If the end goal is the same, the process shouldn't be hard, and not taking part in the qualifiers shouldn't be an obstacle. Alfio Basile doesn't regret calling up Diego Maradona for the 1994 World Cup and Raymond Domenech certainly does not bemoan tempting Zinedine Zidane to come out of retirement for the 2006 World Cup. Both Maradona and Zidane didn't have 'unfinished business' with their National teams at that moment, but Arjen Robben certainly does.
Related Items:Euro, FC Groningen, featured, International, Netherlands, Robben, World Cup
The road ahead for Timothy Fosu Mensah