Jonas Fischer (Research Leader)

Low-dimensional embeddings (LDEs) of high-dimensional data are ubiquitous in
science and engineering. They allow us to quickly understand the main
properties of the data, identify outliers and processing errors, and inform the
next steps of data analysis. As such, LDEs have to be faithful to the original
high-dimensional data, i.e., they should represent the relationships that are
encoded in the data, both at a local as well as global scale. The current
generation of LDE approaches focus on reconstructing local distances between
any pair of samples correctly, often out-performing traditional approaches
aiming at all distances. For these approaches, global relationships are,
however, usually strongly distorted, often argued to be an inherent trade-off
between local and global structure learning for embeddings. We suggest a new
perspective on LDE learning, reconstructing angles between data points. We show
that this approach, Mercat, yields good reconstruction across a diverse set of
experiments and metrics, and preserve structures well across all scales.
Compared to existing work, our approach also has a simple formulation,
facilitating future theoretical analysis and algorithmic improvements.

Low-dimensional embeddings and visualizations are an indispensable tool for
analysis of high-dimensional data. State-of-the-art methods, such as tSNE and
UMAP, excel in unveiling local structures hidden in high-dimensional data and
are therefore routinely applied in standard analysis pipelines in biology. We
show, however, that these methods fail to reconstruct local properties, such as
relative differences in densities (Fig. 1) and that apparent differences in
cluster size can arise from computational artifact caused by differing sample
sizes (Fig. 2). Providing a theoretical analysis of this issue, we then suggest
dtSNE, which approximately conserves local densities. In an extensive study on
synthetic benchmark and real world data comparing against five state-of-the-art
methods, we empirically show that dtSNE provides similar global reconstruction,
but yields much more accurate depictions of local distances and relative
densities.

State-of-the-art NLP methods achieve human-like performance on many tasks,
but make errors nevertheless. Characterizing these errors in easily
interpretable terms gives insight into whether a classifier is prone to making
systematic errors, but also gives a way to act and improve the classifier. We
propose to discover those patterns of tokens that distinguish correct and
erroneous predictions as to obtain global and interpretable descriptions for
arbitrary NLP classifiers. We formulate the problem of finding a succinct and
non-redundant set of such patterns in terms of the Minimum Description Length
principle. Through an extensive set of experiments, we show that our method,
Premise, performs well in practice. Unlike existing solutions, it recovers
ground truth, even on highly imbalanced data over large vocabularies. In VQA
and NER case studies, we confirm that it gives clear and actionable insight
into the systematic errors made by NLP classifiers.

In this thesis we explore pattern mining and deep learning. Often seen as orthogonal, 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 efficiently discover succinct and non-redundant sets of patterns that provide insight into data beyond conjunctive statements. We leverage the interpretability 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, proposing a neural network that directly encodes discrete patterns, which allows us to apply pattern mining at a scale orders of magnitude larger than previously possible. Large neural networks are, however, exceedingly expensive to train for which ‘lottery tickets’ – small, well-trainable sub-networks in randomly 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.

The strong lottery ticket hypothesis holds the promise that pruning randomly
initialized deep neural networks could offer a computationally efficient
alternative to deep learning with stochastic gradient descent. Common parameter
initialization schemes and existence proofs, however, are focused on networks
with zero biases, thus foregoing the potential universal approximation property
of pruning. To fill this gap, we extend multiple initialization schemes and
existence proofs to non-zero biases, including explicit 'looks-linear'
approaches for ReLU activation functions. These do not only enable truly
orthogonal parameter initialization but also reduce potential pruning errors.
In experiments on standard benchmark data sets, we further highlight the
practical benefits of non-zero bias initialization schemes, and present
theoretically inspired extensions for state-of-the-art strong lottery ticket
pruning.

State-of-the-art deep learning methods achieve human-like performance on many
tasks, but make errors nevertheless. Characterizing these errors in easily
interpretable terms gives insight into whether a model is prone to making
systematic errors, but also gives a way to act and improve the model. In this
paper we propose a method that allows us to do so for arbitrary classifiers by
mining a small set of patterns that together succinctly describe the input data
that is partitioned according to correctness of prediction. We show this is an
instance of the more general label description problem, which we formulate in
terms of the Minimum Description Length principle. To discover good pattern
sets we propose the efficient and hyperparameter-free Premise algorithm, which
through an extensive set of experiments we show on both synthetic and
real-world data performs very well in practice; unlike existing solutions it
ably recovers ground truth patterns, even on highly imbalanced data over many
unique items, or where patterns are only weakly associated to labels. Through
two real-world case studies we confirm that Premise gives clear and actionable
insight into the systematic errors made by modern NLP classifiers.

Low-dimensional embedding techniques such as tSNE and UMAP allow visualizing
high-dimensional data and therewith facilitate the discovery of interesting
structure. Although they are widely used, they visualize data as is, rather
than in light of the background knowledge we have about the data. What we
already know, however, strongly determines what is novel and hence interesting.
In this paper we propose two methods for factoring out prior knowledge in the
form of distance matrices from low-dimensional embeddings. To factor out prior
knowledge from tSNE embeddings, we propose JEDI that adapts the tSNE objective
in a principled way using Jensen-Shannon divergence. To factor out prior
knowledge from any downstream embedding approach, we propose CONFETTI, in which
we directly operate on the input distance matrices. Extensive experiments on
both synthetic and real world data show that both methods work well, providing
embeddings that exhibit meaningful structure that would otherwise remain
hidden.

Federated learning allows multiple parties to collaboratively train a joint
model without sharing local data. This enables applications of machine learning
in settings of inherently distributed, undisclosable data such as in the
medical domain. In practice, joint training is usually achieved by aggregating
local models, for which local training objectives have to be in expectation
similar to the joint (global) objective. Often, however, local datasets are so
small that local objectives differ greatly from the global objective, resulting
in federated learning to fail. We propose a novel approach that intertwines
model aggregations with permutations of local models. The permutations expose
each local model to a daisy chain of local datasets resulting in more efficient
training in data-sparse domains. This enables training on extremely small local
datasets, such as patient data across hospitals, while retaining the training
efficiency and privacy benefits of federated learning.

Estimating mutual information (MI) between two continuous random variables
$X$ and $Y$ allows to capture non-linear dependencies between them,
non-parametrically. As such, MI estimation lies at the core of many data
science applications. Yet, robustly estimating MI for high-dimensional $X$ and
$Y$ is still an open research question.
In this paper, we formulate this problem through the lens of manifold
learning. That is, we leverage the common assumption that the information of
$X$ and $Y$ is captured by a low-dimensional manifold embedded in the observed
high-dimensional space and transfer it to MI estimation. As an extension to
state-of-the-art $k$NN estimators, we propose to determine the $k$-nearest
neighbours via geodesic distances on this manifold rather than form the ambient
space, which allows us to estimate MI even in the high-dimensional setting. An
empirical evaluation of our method, G-KSG, against the state-of-the-art shows
that it yields good estimations of the MI in classical benchmark, and manifold
tasks, even for high dimensional datasets, which none of the existing methods
can provide.