OpenRaiser/Intern-Atlas huggingface dataset:
Lexical Normalization for Code-switched Data and its Effect on POS-tagging
Venue: arXiv cs.CL 2021
Year: 2021

Lexical normalization, the translation of non-canonical data to standard language, has shown to improve the performance of manynatural language processing tasks on social media. Yet, using multiple languages in one utterance, also called code-switching (CS), is frequently overlooked by these normalization systems, despite its common use in social media. In this paper, we propose three normalization models specifically designed to handle code-switched data which we evaluate for two language pairs: Indonesian-English (Id-En) and Turkish-German (Tr-De). For the latter, we introduce novel normalization layers and their corresponding language ID and POS tags for the dataset, and evaluate the downstream effect of normalization on POS tagging. Results show that our CS-tailored normalization models outperform Id-En state of the art and Tr-De monolingual models, and lead to 5.4% relative performance increase for POS tagging as compared to unnormalized input.
Consistent Estimators for Learning to Defer to an Expert
Venue: arXiv cs.LG 2021
Year: 2021

Learning algorithms are often used in conjunction with expert decision makers in practical scenarios, however this fact is largely ignored when designing these algorithms. In this paper we explore how to learn predictors that can either predict or choose to defer the decision to a downstream expert. Given only samples of the expert's decisions, we give a procedure based on learning a classifier and a rejector and analyze it theoretically. Our approach is based on a novel reduction to cost sensitive learning where we give a consistent surrogate loss for cost sensitive learning that generalizes the cross entropy loss. We show the effectiveness of our approach on a variety of experimental tasks.
On a Class of Constrained Synchronization Problems in NP
Venue: arXiv cs.FL 2021
Year: 2021

The class of known constraint automata for which the constrained synchronization problem is in NP all admit a special form. In this work, we take a closer look at them. We characterize a wider class of constraint automata that give constrained synchronization problems in NP, which encompasses all known problems in NP. We call these automata polycyclic automata. The corresponding language class of polycyclic languages is introduced. We show various characterizations and closure properties for this new language class. We then give a criterion for NP-completeness and a criterion for polynomial time solvability for polycyclic constraint languages.
A quest for a fair schedule: The Young Physicists' Tournament
Venue: arXiv cs.AI 2021
Year: 2021

The Young Physicists Tournament is an established team-oriented scientific competition between high school students from 37 countries on 5 continents. The competition consists of scientific discussions called Fights. Three or four teams participate in each Fight, each of whom presents a problem while rotating the roles of Presenter, Opponent, Reviewer, and Observer among them. The rules of a few countries require that each team announce in advance 3 problems they will present at the national tournament. The task of the organizers is to choose the composition of Fights in such a way that each team presents each of its chosen problems exactly once and within a single Fight no problem is presented more than once. Besides formalizing these feasibility conditions, in this paper we formulate several additional fairness conditions for tournament schedules. We show that the fulfillment of some of them can be ensured by constructing suitable edge colorings in bipartite graphs. To find fair schedules, we propose integer linear programs and test them on real as well as randomly generated data.
dynoNet: a neural network architecture for learning dynamical systems
Venue: arXiv cs.LG 2021
Year: 2021

This paper introduces a network architecture, called dynoNet, utilizing linear dynamical operators as elementary building blocks. Owing to the dynamical nature of these blocks, dynoNet networks are tailored for sequence modeling and system identification purposes. The back-propagation behavior of the linear dynamical operator with respect to both its parameters and its input sequence is defined. This enables end-to-end training of structured networks containing linear dynamical operators and other differentiable units, exploiting existing deep learning software. Examples show the effectiveness of the proposed approach on well-known system identification benchmarks. Examples show the effectiveness of the proposed approach against well-known system identification benchmarks.
Meta-Model-Based Meta-Policy Optimization
Venue: arXiv cs.LG 2021
Year: 2021

Model-based meta-reinforcement learning (RL) methods have recently been shown to be a promising approach to improving the sample efficiency of RL in multi-task settings. However, the theoretical understanding of those methods is yet to be established, and there is currently no theoretical guarantee of their performance in a real-world environment. In this paper, we analyze the performance guarantee of model-based meta-RL methods by extending the theorems proposed by Janner et al. (2019). On the basis of our theoretical results, we propose Meta-Model-Based Meta-Policy Optimization (M3PO), a model-based meta-RL method with a performance guarantee. We demonstrate that M3PO outperforms existing meta-RL methods in continuous-control benchmarks.
Fuzzy c-Means Clustering for Persistence Diagrams
Venue: arXiv cs.LG 2021
Year: 2021

Persistence diagrams concisely represent the topology of a point cloud whilst having strong theoretical guarantees, but the question of how to best integrate this information into machine learning workflows remains open. In this paper we extend the ubiquitous Fuzzy c-Means (FCM) clustering algorithm to the space of persistence diagrams, enabling unsupervised learning that automatically captures the topological structure of data without the topological prior knowledge or additional processing of persistence diagrams that many other techniques require. We give theoretical convergence guarantees that correspond to the Euclidean case, and empirically demonstrate the capability of our algorithm to capture topological information via the fuzzy RAND index. We end with experiments on two datasets that utilise both the topological and fuzzy nature of our algorithm: pre-trained model selection in machine learning and lattices structures from materials science. As pre-trained models can perform well on multiple tasks, selecting the best model is a naturally fuzzy problem; we show that fuzzy clustering persistence diagrams allows for model selection using the topology of decision boundaries. In materials science, we classify transformed lattice structure datasets for the first time, whilst the probabilistic membership values let us rank candidate lattices in a scenario where further investigation requires expensive laboratory time and expertise.
Exploring the Potential of Low-bit Training of Convolutional Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

In this work, we propose a low-bit training framework for convolutional neural networks, which is built around a novel multi-level scaling (MLS) tensor format. Our framework focuses on reducing the energy consumption of convolution operations by quantizing all the convolution operands to low bit-width format. Specifically, we propose the MLS tensor format, in which the element-wise bit-width can be largely reduced. Then, we describe the dynamic quantization and the low-bit tensor convolution arithmetic to leverage the MLS tensor format efficiently. Experiments show that our framework achieves a superior trade-off between the accuracy and the bit-width than previous low-bit training frameworks. For training a variety of models on CIFAR-10, using 1-bit mantissa and 2-bit exponent is adequate to keep the accuracy loss within $1\%$. And on larger datasets like ImageNet, using 4-bit mantissa and 2-bit exponent is adequate to keep the accuracy loss within $1\%$. Through the energy consumption simulation of the computing units, we can estimate that training a variety of models with our framework could achieve $8.3\sim10.2\times$ and $1.9\sim2.3\times$ higher energy efficiency than training with full-precision and 8-bit floating-point arithmetic, respectively.
Foundations of regular coinduction
Venue: arXiv cs.LO 2021
Year: 2021

Inference systems are a widespread framework used to define possibly recursive predicates by means of inference rules. They allow both inductive and coinductive interpretations that are fairly well-studied. In this paper, we consider a middle way interpretation, called regular, which combines advantages of both approaches: it allows non-well-founded reasoning while being finite. We show that the natural proof-theoretic definition of the regular interpretation, based on regular trees, coincides with a rational fixed point. Then, we provide an equivalent inductive characterization, which leads to an algorithm which looks for a regular derivation of a judgment. Relying on these results, we define proof techniques for regular reasoning: the regular coinduction principle, to prove completeness, and an inductive technique to prove soundness, based on the inductive characterization of the regular interpretation. Finally, we show the regular approach can be smoothly extended to inference systems with corules, a recently introduced, generalised framework, which allows one to refine the coinductive interpretation, proving that also this flexible regular interpretation admits an equivalent inductive characterisation.
The Impact of COVID-19 on Flight Networks
Venue: arXiv cs.SI 2021
Year: 2021

As COVID-19 transmissions spread worldwide, governments have announced and enforced travel restrictions to prevent further infections. Such restrictions have a direct effect on the volume of international flights among these countries, resulting in extensive social and economic costs. To better understand the situation in a quantitative manner, we used the Opensky network data to clarify flight patterns and flight densities around the world and observe relationships between flight numbers with new infections, and with the economy (unemployment rate) in Barcelona. We found that the number of daily flights gradually decreased and suddenly dropped 64% during the second half of March in 2020 after the US and Europe enacted travel restrictions. We also observed a 51% decrease in the global flight network density decreased during this period. Regarding new COVID-19 cases, the world had an unexpected surge regardless of travel restrictions. Finally, the layoffs for temporary workers in the tourism and airplane business increased by 4.3 fold in the weeks following Spain's decision to close its borders.
TASM: A Tile-Based Storage Manager for Video Analytics
Venue: arXiv cs.DB 2021
Year: 2021

Modern video data management systems store videos as a single encoded file, which significantly limits possible storage level optimizations. We design, implement, and evaluate TASM, a new tile-based storage manager for video data. TASM uses a feature in modern video codecs called "tiles" that enables spatial random access into encoded videos. TASM physically tunes stored videos by optimizing their tile layouts given the video content and a query workload. Additionally, TASM dynamically tunes that layout in response to changes in the query workload or if the query workload and video contents are incrementally discovered. Finally, TASM also produces efficient initial tile layouts for newly ingested videos. We demonstrate that TASM can speed up subframe selection queries by an average of over 50% and up to 94%. TASM can also improve the throughput of the full scan phase of object detection queries by up to 2X.
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction
Venue: arXiv cs.LG 2021
Year: 2021

Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP), based on a single trajectory of Markovian samples induced by a behavior policy. Focusing on a $γ$-discounted MDP with state space $\mathcal{S}$ and action space $\mathcal{A}$, we demonstrate that the $\ell_{\infty}$-based sample complexity of classical asynchronous Q-learning --- namely, the number of samples needed to yield an entrywise $\varepsilon$-accurate estimate of the Q-function --- is at most on the order of $\frac{1}{μ_{\min}(1-γ)^5\varepsilon^2}+ \frac{t_{mix}}{μ_{\min}(1-γ)}$ up to some logarithmic factor, provided that a proper constant learning rate is adopted. Here, $t_{mix}$ and $μ_{\min}$ denote respectively the mixing time and the minimum state-action occupancy probability of the sample trajectory. The first term of this bound matches the sample complexity in the synchronous case with independent samples drawn from the stationary distribution of the trajectory. The second term reflects the cost taken for the empirical distribution of the Markovian trajectory to reach a steady state, which is incurred at the very beginning and becomes amortized as the algorithm runs. Encouragingly, the above bound improves upon the state-of-the-art result \cite{qu2020finite} by a factor of at least $|\mathcal{S}||\mathcal{A}|$ for all scenarios, and by a factor of at least $t_{mix}|\mathcal{S}||\mathcal{A}|$ for any sufficiently small accuracy level $\varepsilon$. Further, we demonstrate that the scaling on the effective horizon $\frac{1}{1-γ}$ can be improved by means of variance reduction.
Achieving High Throughput and Elasticity in a Larger-than-Memory Store
Venue: arXiv cs.DC 2021
Year: 2021

Millions of sensors, mobile applications and machines now generate billions of events. Specialized many-core key-value stores (KVSs) can ingest and index these events at high rates (over 100 Mops/s on one machine) if events are generated on the same machine; however, to be practical and cost-effective they must ingest events over the network and scale across cloud resources elastically. We present Shadowfax, a new distributed KVS based on FASTER, that transparently spans DRAM, SSDs, and cloud blob storage while serving 130 Mops/s/VM over commodity Azure VMs using conventional Linux TCP. Beyond high single-VM performance, Shadowfax uses a unique approach to distributed reconfiguration that avoids any server-side key ownership checks or cross-core coordination both during normal operation and migration. Hence, Shadowfax can shift load in 17 s to improve system throughput by 10 Mops/s with little disruption. Compared to the state-of-the-art, it has 8x better throughput (than Seastar+memcached) and avoids costly I/O to move cold data during migration. On 12 machines, Shadowfax retains its high throughput to perform 930 Mops/s, which, to the best of our knowledge, is the highest reported throughput for a distributed KVS used for large-scale data ingestion and indexing.
Sponge Examples: Energy-Latency Attacks on Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

The high energy costs of neural network training and inference led to the use of acceleration hardware such as GPUs and TPUs. While this enabled us to train large-scale neural networks in datacenters and deploy them on edge devices, the focus so far is on average-case performance. In this work, we introduce a novel threat vector against neural networks whose energy consumption or decision latency are critical. We show how adversaries can exploit carefully crafted $\boldsymbol{sponge}~\boldsymbol{examples}$, which are inputs designed to maximise energy consumption and latency. We mount two variants of this attack on established vision and language models, increasing energy consumption by a factor of 10 to 200. Our attacks can also be used to delay decisions where a network has critical real-time performance, such as in perception for autonomous vehicles. We demonstrate the portability of our malicious inputs across CPUs and a variety of hardware accelerator chips including GPUs, and an ASIC simulator. We conclude by proposing a defense strategy which mitigates our attack by shifting the analysis of energy consumption in hardware from an average-case to a worst-case perspective.
UFO-BLO: Unbiased First-Order Bilevel Optimization
Venue: arXiv cs.LG 2021
Year: 2021

Bilevel optimization (BLO) is a popular approach with many applications including hyperparameter optimization, neural architecture search, adversarial robustness and model-agnostic meta-learning. However, the approach suffers from time and memory complexity proportional to the length $r$ of its inner optimization loop, which has led to several modifications being proposed. One such modification is \textit{first-order} BLO (FO-BLO) which approximates outer-level gradients by zeroing out second derivative terms, yielding significant speed gains and requiring only constant memory as $r$ varies. Despite FO-BLO's popularity, there is a lack of theoretical understanding of its convergence properties. We make progress by demonstrating a rich family of examples where FO-BLO-based stochastic optimization does not converge to a stationary point of the BLO objective. We address this concern by proposing a new FO-BLO-based unbiased estimate of outer-level gradients, enabling us to theoretically guarantee this convergence, with no harm to memory and expected time complexity. Our findings are supported by experimental results on Omniglot and Mini-ImageNet, popular few-shot meta-learning benchmarks.
High-Dimensional Non-Parametric Density Estimation in Mixed Smooth Sobolev Spaces
Venue: arXiv cs.LG 2021
Year: 2021

Density estimation plays a key role in many tasks in machine learning, statistical inference, and visualization. The main bottleneck in high-dimensional density estimation is the prohibitive computational cost and the slow convergence rate. In this paper, we propose novel estimators for high-dimensional non-parametric density estimation called the adaptive hyperbolic cross density estimators, which enjoys nice convergence properties in the mixed smooth Sobolev spaces. As modifications of the usual Sobolev spaces, the mixed smooth Sobolev spaces are more suitable for describing high-dimensional density functions in some applications. We prove that, unlike other existing approaches, the proposed estimator does not suffer the curse of dimensionality under Integral Probability Metric, including Hölder Integral Probability Metric, where Total Variation Metric and Wasserstein Distance are special cases. Applications of the proposed estimators to generative adversarial networks (GANs) and goodness of fit test for high-dimensional data are discussed to illustrate the proposed estimator's good performance in high-dimensional problems. Numerical experiments are conducted and illustrate the efficiency of our proposed method.
Towards large-scale, automated, accurate detection of CCTV camera objects using computer vision. Applications and implications for privacy, safety, and cybersecurity. (Preprint)
Venue: arXiv cs.CV 2021
Year: 2021

In order to withstand the ever-increasing invasion of privacy by CCTV cameras and technologies, on par CCTV-aware solutions must exist that provide privacy, safety, and cybersecurity features. We argue that a first important step towards such CCTV-aware solutions must be a mapping system (e.g., Google Maps, OpenStreetMap) that provides both privacy and safety routing and navigation options. However, this in turn requires that the mapping system contains updated information on CCTV cameras' exact geo-location, coverage area, and possibly other meta-data (e.g., resolution, facial recognition features, operator). Such information is however missing from current mapping systems, and there are several ways to fix this. One solution is to perform CCTV camera detection on geo-location tagged images, e.g., street view imagery on various platforms, user images publicly posted in image sharing platforms such as Flickr. Unfortunately, to the best of our knowledge, there are no computer vision models for CCTV camera object detection as well as no mapping system that supports privacy and safety routing options. To close these gaps, with this paper we introduce CCTVCV -- the first and only computer vision MS COCO-compatible models that are able to accurately detect CCTV and video surveillance cameras in images and video frames. To this end, our best detectors were built using 8387 images that were manually reviewed and annotated to contain 10419 CCTV camera instances, and achieve an accuracy of up to 98.7%. Moreover, we build and evaluate multiple models, present a comprehensive comparison of their performance, and outline core challenges associated with such research.
An Attacker Modeling Framework for the Assessment of Cyber-Physical Systems Security
Venue: arXiv cs.CR 2021
Year: 2021

Characterizing attacker behavior with respect to Cyber-Physical Systems is important to assuring the security posture and resilience of these systems. Classical cyber vulnerability assessment approaches rely on the knowledge and experience of cyber-security experts to conduct security analyses and can be inconsistent where the experts' knowledge and experience are lacking. This paper proposes a flexible attacker modeling framework that aids in the security analysis process by simulating a diverse set of attacker behaviors to predict attack progression and provide consistent system vulnerability analysis. The model proposes an expanded architecture of vulnerability databases to maximize its effectiveness and consistency in detecting CPS vulnerabilities while being compatible with existing vulnerability databases. The model has the power to be implemented and simulated against an actual or virtual CPS. Execution of the attacker model is demonstrated against a simulated industrial control system architecture, resulting in a probabilistic prediction of attacker behavior.
Stable and Efficient Policy Evaluation
Venue: arXiv cs.LG 2021
Year: 2021

Policy evaluation algorithms are essential to reinforcement learning due to their ability to predict the performance of a policy. However, there are two long-standing issues lying in this prediction problem that need to be tackled: off-policy stability and on-policy efficiency. The conventional temporal difference (TD) algorithm is known to perform very well in the on-policy setting, yet is not off-policy stable. On the other hand, the gradient TD and emphatic TD algorithms are off-policy stable, but are not on-policy efficient. This paper introduces novel algorithms that are both off-policy stable and on-policy efficient by using the oblique projection method. The empirical experimental results on various domains validate the effectiveness of the proposed approach.
Probabilistic Timed Automata with One Clock and Initialised Clock-Dependent Probabilities
Venue: arXiv cs.LO 2021
Year: 2021

Clock-dependent probabilistic timed automata extend classical timed automata with discrete probabilistic choice, where the probabilities are allowed to depend on the exact values of the clocks. Previous work has shown that the quantitative reachability problem for clock-dependent probabilistic timed automata with at least three clocks is undecidable. In this paper, we consider the subclass of clock-dependent probabilistic timed automata that have one clock, that have clock dependencies described by affine functions, and that satisfy an initialisation condition requiring that, at some point between taking edges with non-trivial clock dependencies, the clock must have an integer value. We present an approach for solving in polynomial time quantitative and qualitative reachability problems of such one-clock initialised clock-dependent probabilistic timed automata. Our results are obtained by a transformation to interval Markov decision processes.