OpenRaiser/Intern-Atlas huggingface dataset:
On the Impact of Device and Behavioral Heterogeneity in Federated Learning
Venue: arXiv cs.LG 2021
Year: 2021

Federated learning (FL) is becoming a popular paradigm for collaborative learning over distributed, private datasets owned by non-trusting entities. FL has seen successful deployment in production environments, and it has been adopted in services such as virtual keyboards, auto-completion, item recommendation, and several IoT applications. However, FL comes with the challenge of performing training over largely heterogeneous datasets, devices, and networks that are out of the control of the centralized FL server. Motivated by this inherent setting, we make a first step towards characterizing the impact of device and behavioral heterogeneity on the trained model. We conduct an extensive empirical study spanning close to 1.5K unique configurations on five popular FL benchmarks. Our analysis shows that these sources of heterogeneity have a major impact on both model performance and fairness, thus sheds light on the importance of considering heterogeneity in FL system design.
CHARET: Character-centered Approach to Emotion Tracking in Stories
Venue: arXiv cs.HC 2021
Year: 2021

Autonomous agents that can engage in social interactions witha human is the ultimate goal of a myriad of applications. A keychallenge in the design of these applications is to define the socialbehavior of the agent, which requires extensive content creation.In this research, we explore how we can leverage current state-of-the-art tools to make inferences about the emotional state ofa character in a story as events unfold, in a coherent way. Wepropose a character role-labelling approach to emotion tracking thataccounts for the semantics of emotions. We show that by identifyingactors and objects of events and considering the emotional stateof the characters, we can achieve better performance in this task,when compared to end-to-end approaches.
A proof of concept study for machine learning application to stenosis detection
Venue: arXiv cs.LG 2021
Year: 2021

This proof of concept (PoC) assesses the ability of machine learning (ML) classifiers to predict the presence of a stenosis in a three vessel arterial system consisting of the abdominal aorta bifurcating into the two common iliacs. A virtual patient database (VPD) is created using one-dimensional pulse wave propagation model of haemodynamics. Four different machine learning (ML) methods are used to train and test a series of classifiers -- both binary and multiclass -- to distinguish between healthy and unhealthy virtual patients (VPs) using different combinations of pressure and flow-rate measurements. It is found that the ML classifiers achieve specificities larger than 80% and sensitivities ranging from 50-75%. The most balanced classifier also achieves an area under the receiver operative characteristic curve of 0.75, outperforming approximately 20 methods used in clinical practice, and thus placing the method as moderately accurate. Other important observations from this study are that: i) few measurements can provide similar classification accuracies compared to the case when more/all the measurements are used; ii) some measurements are more informative than others for classification; and iii) a modification of standard methods can result in detection of not only the presence of stenosis, but also the stenosed vessel.
RMS-Net: Regression and Masking for Soccer Event Spotting
Venue: arXiv cs.CV 2021
Year: 2021

The recently proposed action spotting task consists in finding the exact timestamp in which an event occurs. This task fits particularly well for soccer videos, where events correspond to salient actions strictly defined by soccer rules (a goal occurs when the ball crosses the goal line). In this paper, we devise a lightweight and modular network for action spotting, which can simultaneously predict the event label and its temporal offset using the same underlying features. We enrich our model with two training strategies: the first one for data balancing and uniform sampling, the second for masking ambiguous frames and keeping the most discriminative visual cues. When tested on the SoccerNet dataset and using standard features, our full proposal exceeds the current state of the art by 3 Average-mAP points. Additionally, it reaches a gain of more than 10 Average-mAP points on the test set when fine-tuned in combination with a strong 2D backbone.
A closer look at temporal variability in dynamic online learning
Venue: arXiv cs.LG 2021
Year: 2021

This work focuses on the setting of dynamic regret in the context of online learning with full information. In particular, we analyze regret bounds with respect to the temporal variability of the loss functions. By assuming that the sequence of loss functions does not vary much with time, we show that it is possible to incur improved regret bounds compared to existing results. The key to our approach is to use the loss function (and not its gradient) during the optimization process. Building on recent advances in the analysis of Implicit algorithms, we propose an adaptation of the Implicit version of Online Mirror Descent to the dynamic setting. Our proposed algorithm is adaptive not only to the temporal variability of the loss functions, but also to the path length of the sequence of comparators when an upper bound is known. Furthermore, our analysis reveals that our results are tight and cannot be improved without further assumptions. Next, we show how our algorithm can be applied to the setting of learning with expert advice or to settings with composite loss functions. Finally, when an upper bound to the path-length is not fixed beforehand we show how to combine a greedy strategy with existing strongly-adaptive algorithms to compete optimally against different sequences of comparators simultaneously.
Polynomial time algorithms in invariant theory for torus actions
Venue: arXiv cs.DS 2021
Year: 2021

An action of a group on a vector space partitions the latter into a set of orbits. We consider three natural and useful algorithmic "isomorphism" or "classification" problems, namely, orbit equality, orbit closure intersection, and orbit closure containment. These capture and relate to a variety of problems within mathematics, physics and computer science, optimization and statistics. These orbit problems extend the more basic null cone problem, whose algorithmic complexity has seen significant progress in recent years. In this paper, we initiate a study of these problems by focusing on the actions of commutative groups (namely, tori). We explain how this setting is motivated from questions in algebraic complexity, and is still rich enough to capture interesting combinatorial algorithmic problems. While the structural theory of commutative actions is well understood, no general efficient algorithms were known for the aforementioned problems. Our main results are polynomial time algorithms for all three problems. We also show how to efficiently find separating invariants for orbits, and how to compute systems of generating rational invariants for these actions (in contrast, for polynomial invariants the latter is known to be hard). Our techniques are based on a combination of fundamental results in invariant theory, linear programming, and algorithmic lattice theory.
Local Access to Random Walks
Venue: arXiv cs.DS 2021
Year: 2021

For a graph $G$ on $n$ vertices, naively sampling the position of a random walk of at time $t$ requires work $Ω(t)$. We desire local access algorithms supporting $\text{position}(G,s,t)$ queries, which return the position of a random walk from some start vertex $s$ at time $t$, where the joint distribution of returned positions is $1/\text{poly}(n)$ close to the uniform distribution over such walks in $\ell_1$ distance. We first give an algorithm for local access to walks on undirected regular graphs with $\widetilde{O}(\frac{1}{1-λ}\sqrt{n})$ runtime per query, where $λ$ is the second-largest eigenvalue in absolute value. Since random $d$-regular graphs are expanders with high probability, this gives an $\widetilde{O}(\sqrt{n})$ algorithm for $G(n,d)$, which improves on the naive method for small numbers of queries. We then prove that no that algorithm with sub-constant error given probe access to random $d$-regular graphs can have runtime better than $Ω(\sqrt{n}/\log(n))$ per query in expectation, obtaining a nearly matching lower bound. We further show an $Ω(n^{1/4})$ runtime per query lower bound even with an oblivious adversary (i.e. when the query sequence is fixed in advance). We then show that for families of graphs with additional group theoretic structure, dramatically better results can be achieved. We give local access to walks on small-degree abelian Cayley graphs, including cycles and hypercubes, with runtime $\text{polylog}(n)$ per query. This also allows for efficient local access to walks on $\text{polylog}$ degree expanders. We extend our results to graphs constructed using the tensor product (giving local access to walks on degree $n^ε$ graphs for any $ε\in (0,1]$) and Cartesian product.
Timely Transmissions Using Optimized Variable Length Coding
Venue: arXiv cs.IT 2021
Year: 2021

A status updating system is considered in which a variable length code is used to transmit messages to a receiver over a noisy channel. The goal is to optimize the codewords lengths such that successfully-decoded messages are timely. That is, such that the age-of-information (AoI) at the receiver is minimized. A hybrid ARQ (HARQ) scheme is employed, in which variable-length incremental redundancy (IR) bits are added to the originally-transmitted codeword until decoding is successful. With each decoding attempt, a non-zero processing delay is incurred. The optimal codewords lengths are analytically derived utilizing a sequential differential optimization (SDO) framework. The framework is general in that it only requires knowledge of an analytical expression of the positive feedback (ACK) probability as a function of the codeword length.
Efficient Learning with Arbitrary Covariate Shift
Venue: arXiv cs.LG 2021
Year: 2021

We give an efficient algorithm for learning a binary function in a given class C of bounded VC dimension, with training data distributed according to P and test data according to Q, where P and Q may be arbitrary distributions over X. This is the generic form of what is called covariate shift, which is impossible in general as arbitrary P and Q may not even overlap. However, recently guarantees were given in a model called PQ-learning (Goldwasser et al., 2020) where the learner has: (a) access to unlabeled test examples from Q (in addition to labeled samples from P, i.e., semi-supervised learning); and (b) the option to reject any example and abstain from classifying it (i.e., selective classification). The algorithm of Goldwasser et al. (2020) requires an (agnostic) noise tolerant learner for C. The present work gives a polynomial-time PQ-learning algorithm that uses an oracle to a "reliable" learner for C, where reliable learning (Kalai et al., 2012) is a model of learning with one-sided noise. Furthermore, our reduction is optimal in the sense that we show the equivalence of reliable and PQ learning.
Certified Robustness to Programmable Transformations in LSTMs
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural networks for natural language processing are fragile in the face of adversarial examples -- small input perturbations, like synonym substitution or word duplication, which cause a neural network to change its prediction. We present an approach to certifying the robustness of LSTMs (and extensions of LSTMs) and training models that can be efficiently certified. Our approach can certify robustness to intractably large perturbation spaces defined programmatically in a language of string transformations. Our evaluation shows that (1) our approach can train models that are more robust to combinations of string transformations than those produced using existing techniques; (2) our approach can show high certification accuracy of the resulting models.
NeuralNDCG: Direct Optimisation of a Ranking Metric via Differentiable Relaxation of Sorting
Venue: arXiv cs.IR 2021
Year: 2021

Learning to Rank (LTR) algorithms are usually evaluated using Information Retrieval metrics like Normalised Discounted Cumulative Gain (NDCG) or Mean Average Precision. As these metrics rely on sorting predicted items' scores (and thus, on items' ranks), their derivatives are either undefined or zero everywhere. This makes them unsuitable for gradient-based optimisation, which is the usual method of learning appropriate scoring functions. Commonly used LTR loss functions are only loosely related to the evaluation metrics, causing a mismatch between the optimisation objective and the evaluation criterion. In this paper, we address this mismatch by proposing NeuralNDCG, a novel differentiable approximation to NDCG. Since NDCG relies on the non-differentiable sorting operator, we obtain NeuralNDCG by relaxing that operator using NeuralSort, a differentiable approximation of sorting. As a result, we obtain a new ranking loss function which is an arbitrarily accurate approximation to the evaluation metric, thus closing the gap between the training and the evaluation of LTR models. We introduce two variants of the proposed loss function. Finally, the empirical evaluation shows that our proposed method outperforms previous work aimed at direct optimisation of NDCG and is competitive with the state-of-the-art methods.
A Comparison of Deep-Learning Methods for Analysing and Predicting Business Processes
Venue: arXiv cs.LG 2021
Year: 2021

Deep-learning models such as Convolutional Neural Networks (CNN) and Long Short-Term Memory (LSTM) have been successfully used for process-mining tasks. They have achieved better performance for different predictive tasks than traditional approaches. We extend the existing body of research by testing four different variants of Graph Neural Networks (GNN) and a fully connected Multi-layer Perceptron (MLP) with dropout for the tasks of predicting the nature and timestamp of the next process activity. In contrast to existing studies, we evaluate our models' performance at different stages of a process, determined by quartiles of the number of events and normalized quarters of the case duration. This provides new insights into the performance of a prediction model, as they behave differently at different stages of a business-process. Interestingly, our experiments show that the simple MLP often outperforms more sophisticated deep-learning models in both prediction tasks. We argue that care needs to be taken when applying automated process-prediction techniques at different stages of a process. We further argue that researchers should reflect their results with strong baselines methods like simple MLPs.
"From What I see, this makes sense": Seeing meaning in algorithmic results
Venue: arXiv cs.HC 2021
Year: 2021

In this workshop paper, we use an empirical example from our ongoing fieldwork, to showcase the complexity and situatedness of the process of making sense of algorithmic results; i.e. how to evaluate, validate, and contextualize algorithmic outputs. So far, in our research work, we have focused on such sense-making processes in data analytic learning environments such as classrooms and training workshops. Multiple moments in our fieldwork suggest that meaning, in data analytics, is constructed through an iterative and reflexive dialogue between data, code, assumptions, prior knowledge, and algorithmic results. A data analytic result is nothing short of a sociotechnical accomplishment - one in which it is extremely difficult, if not at times impossible, to clearly distinguish between 'human' and 'technical' forms of data analytic work. We conclude this paper with a set of questions that we would like to explore further in this workshop.
Meta Back-translation
Venue: arXiv cs.CL 2021
Year: 2021

Back-translation is an effective strategy to improve the performance of Neural Machine Translation~(NMT) by generating pseudo-parallel data. However, several recent works have found that better translation quality of the pseudo-parallel data does not necessarily lead to better final translation models, while lower-quality but more diverse data often yields stronger results. In this paper, we propose a novel method to generate pseudo-parallel data from a pre-trained back-translation model. Our method is a meta-learning algorithm which adapts a pre-trained back-translation model so that the pseudo-parallel data it generates would train a forward-translation model to do well on a validation set. In our evaluations in both the standard datasets WMT En-De'14 and WMT En-Fr'14, as well as a multilingual translation setting, our method leads to significant improvements over strong baselines. Our code will be made available.
Self-Supervised Features Improve Open-World Learning
Venue: arXiv cs.CV 2021
Year: 2021

This paper identifies the flaws in existing open-world learning approaches and attempts to provide a complete picture in the form of \textbf{True Open-World Learning}. We accomplish this by proposing a comprehensive generalize-able open-world learning protocol capable of evaluating various components of open-world learning in an operational setting. We argue that in true open-world learning, the underlying feature representation should be learned in a self-supervised manner. Under this self-supervised feature representation, we introduce the problem of detecting unknowns as samples belonging to Out-of-Label space. We differentiate between Out-of-Label space detection and the conventional Out-of-Distribution detection depending upon whether the unknowns being detected belong to the native-world (same as feature representation) or a new-world, respectively. Our unifying open-world learning framework combines three individual research dimensions, which typically have been explored independently, i.e., Incremental Learning, Out-of-Distribution detection and Open-World Learning. Starting from a self-supervised feature space, an open-world learner has the ability to adapt and specialize its feature space to the classes in each incremental phase and hence perform better without incurring any significant overhead, as demonstrated by our experimental results. The incremental learning component of our pipeline provides the new state-of-the-art on established ImageNet-100 protocol. We also demonstrate the adaptability of our approach by showing how it can work as a plug-in with any of the self-supervised feature representation methods.
Unified Shapley Framework to Explain Prediction Drift
Venue: arXiv cs.LG 2021
Year: 2021

Predictions are the currency of a machine learning model, and to understand the model's behavior over segments of a dataset, or over time, is an important problem in machine learning research and practice. There currently is no systematic framework to understand this drift in prediction distributions over time or between two semantically meaningful slices of data, in terms of the input features and points. We propose GroupShapley and GroupIG (Integrated Gradients), as axiomatically justified methods to tackle this problem. In doing so, we re-frame all current feature/data importance measures based on the Shapley value as essentially problems of distributional comparisons, and unify them under a common umbrella. We axiomatize certain desirable properties of distributional difference, and study the implications of choosing them empirically.
SK-Tree: a systematic malware detection algorithm on streaming trees via the signature kernel
Venue: arXiv cs.CR 2021
Year: 2021

The development of machine learning algorithms in the cyber security domain has been impeded by the complex, hierarchical, sequential and multimodal nature of the data involved. In this paper we introduce the notion of a streaming tree as a generic data structure encompassing a large portion of real-world cyber security data. Starting from host-based event logs we represent computer processes as streaming trees that evolve in continuous time. Leveraging the properties of the signature kernel, a machine learning tool that recently emerged as a leading technology for learning with complex sequences of data, we develop the SK-Tree algorithm. SK-Tree is a supervised learning method for systematic malware detection on streaming trees that is robust to irregular sampling and high dimensionality of the underlying streams. We demonstrate the effectiveness of SK-Tree to detect malicious events on a portion of the publicly available DARPA OpTC dataset, achieving an AUROC score of 98%.
MITNet: GAN Enhanced Magnetic Induction Tomography Based on Complex CNN
Venue: arXiv cs.CV 2021
Year: 2021

Magnetic induction tomography (MIT) is an efficient solution for long-term brain disease monitoring, which focuses on reconstructing bio-impedance distribution inside the human brain using non-intrusive electromagnetic fields. However, high-quality brain image reconstruction remains challenging since reconstructing images from the measured weak signals is a highly non-linear and ill-conditioned problem. In this work, we propose a generative adversarial network (GAN) enhanced MIT technique, named MITNet, based on a complex convolutional neural network (CNN). The experimental results on the real-world dataset validate the performance of our technique, which outperforms the state-of-art method by 25.27%.
Darboux-Frame-Based Parametrization for a Spin-Rolling Sphere on a Plane: A Nonlinear Transformation of Underactuated System to Fully-Actuated Model
Venue: arXiv cs.RO 2021
Year: 2021

This paper presents a new kinematic model based on the Darboux frame for motion control and planning. In this work, we show that an underactuated model of a spin-rolling sphere on a plane with five states and three inputs can be transformed into a fully-actuated one by a given Darboux frame transformation. This nonlinear state transformation establishes a geometric model that is different from conventional state-space ones. First, a kinematic model of the Darboux frame at the contact point of the rolling sphere is established. Next, we propose a virtual surface that is trapped between the sphere and the contact plane. This virtual surface is used for generating arc-length-based inputs for controlling the contact trajectories on the sphere and the plane. Finally, we discuss the controllability of this new model. In the future, we will design a geometric path planning method for the proposed kinematic model.
Compilation of mathematical expressions in Kotlin
Venue: arXiv cs.SE 2021
Year: 2021

Interpreting mathematical expressions at runtime is a standard task in scientific software engineering. There are different approaches to this problem from creating an embedded domain-specific language (eDSL) with its own parser and interpreter specifically for that task, to using a full-fledged embedded compiler. This article is dedicated to a middle-ground solution implemented in the KMath library, which uses the Kotlin object builder DSL and its own algebraic abstractions to generate an AST for mathematical operations. This AST is then compiled just-in-time to generate JVM bytecode. A similar approach is tested on other Kotlin platforms, where its performance is compared across a variety of supported platforms.