In this thesis we explore pattern mining and deep learning. Often seen
as or-thogonal, we show that these fields complement each other and
propose to combine them to gain from each other’s strengths. We, first,
show how to ef-ficiently discover succinct and non-redundant sets of
patterns that provide insight into data beyond conjunctive statements.
We leverage the interpreta-bility of such patterns to unveil how and
which information flows through neural networks, as well as what
characterizes their decisions. Conversely, we show how to combine
continuous optimization with pattern discovery, pro-posing a neural
network that directly encodes discrete patterns, which allows us to
apply pattern mining at a scale orders of magnitude larger than
previ-ously possible. Large neural networks are, however, exceedingly
expensive to train for which ‘lottery tickets’ – small, well-trainable
sub-networks in ran-domly initialized neural networks – offer a remedy.
We identify theoretical limitations of strong tickets and overcome them
by equipping these tickets with the property of universal approximation.
To analyze whether limitations in ticket sparsity are algorithmic or
fundamental, we propose a framework to plant and hide lottery tickets.
With novel ticket benchmarks we then conclude that the limitation is
likely algorithmic, encouraging further developments for which our
framework offers means to measure progress.