Causality Networks
  While correlation measures are used to discern statistical relationships
between observed variables in almost all branches of data-driven scientific
inquiry, what we are really interested in is the existence of causal
dependence. Designing an efficient causality test, that may be carried out in
the absence of restrictive pre-suppositions on the underlying dynamical
structure of the data at hand, is non-trivial. Nevertheless, ability to
computationally infer statistical prima facie evidence of causal dependence may
yield a far more discriminative tool for data analysis compared to the
calculation of simple correlations. In the present work, we present a new
non-parametric test of Granger causality for quantized or symbolic data streams
generated by ergodic stationary sources. In contrast to state-of-art binary
tests, our approach makes precise and computes the degree of causal dependence
between data streams, without making any restrictive assumptions, linearity or
otherwise. Additionally, without any a priori imposition of specific dynamical
structure, we infer explicit generative models of causal cross-dependence,
which may be then used for prediction. These explicit models are represented as
generalized probabilistic automata, referred to crossed automata, and are shown
to be sufficient to capture a fairly general class of causal dependence. The
proposed algorithms are computationally efficient in the PAC sense; $i.e.$, we
find good models of cross-dependence with high probability, with polynomial
run-times and sample complexities. The theoretical results are applied to
weekly search-frequency data from Google Trends API for a chosen set of
socially "charged" keywords. The causality network inferred from this dataset
reveals, quite expectedly, the causal importance of certain keywords. It is
also illustrated that correlation analysis fails to gather such insight.
