OpenRaiser/Intern-Atlas huggingface dataset:
lamBERT: Language and Action Learning Using Multimodal BERT
Venue: arXiv cs.LG 2020
Year: 2020

Recently, the bidirectional encoder representations from transformers (BERT) model has attracted much attention in the field of natural language processing, owing to its high performance in language understanding-related tasks. The BERT model learns language representation that can be adapted to various tasks via pre-training using a large corpus in an unsupervised manner. This study proposes the language and action learning using multimodal BERT (lamBERT) model that enables the learning of language and actions by 1) extending the BERT model to multimodal representation and 2) integrating it with reinforcement learning. To verify the proposed model, an experiment is conducted in a grid environment that requires language understanding for the agent to act properly. As a result, the lamBERT model obtained higher rewards in multitask settings and transfer settings when compared to other models, such as the convolutional neural network-based model and the lamBERT model without pre-training.
Non-maximal sensitivity to synchronism in periodic elementary cellular automata: exact asymptotic measures
Venue: arXiv cs.FL 2020
Year: 2020

In [11] and [13] the authors showed that elementary cellular automata rules 0, 3, 8, 12, 15, 28, 32, 34, 44, 51, 60, 128, 136, 140, 160, 162, 170, 200 and 204 (and their conjugation, reflection, reflected-conjugation) are not maximum sensitive to synchronism, i.e. they do not have a different dynamics for each (non-equivalent) block-sequential update schedule (defined as ordered partitions of cell positions). In this work we present exact measurements of the sensitivity to synchronism for these rules, as functions of the size. These exhibit a surprising variety of values and associated proof methods, such as the special pairs of rule 128, and the connection to the bissection of Lucas numbers of rule 8.
Online Information Search During COVID-19
Venue: arXiv cs.CY 2020
Year: 2020

Public information search data from sources such as Google Trends affords researchers a perspective on what society does not know, or what society wants to find out prompted by, or in response to, developments in societal communication and news media events. In times of crisis, online public information search thus offers a window into the most urgent concerns of, and demands by society. By extension, such data offers a window into upcoming, and currently pressing demands on businesses, policymakers and researchers. This research note aims to illustrate some of these themes with a visual-based overview of the current COVID-19 / Coronavirus crisis.
Slightly Improved Upper Bound on the Integrality Ratio for the $s-t$ Path TSP
Venue: arXiv cs.DS 2020
Year: 2020

In this paper we investigate the integrality ratio of the standard LP relaxation for the metric $s-t$ Path TSP. We make a near-optimal choice for an auxiliary function used in the analysis of Traub and Vygen which leads to an improved upper bound on the integrality ratio of 1.5273.
ESResNet: Environmental Sound Classification Based on Visual Domain Models
Venue: arXiv cs.CV 2020
Year: 2020

Environmental Sound Classification (ESC) is an active research area in the audio domain and has seen a lot of progress in the past years. However, many of the existing approaches achieve high accuracy by relying on domain-specific features and architectures, making it harder to benefit from advances in other fields (e.g., the image domain). Additionally, some of the past successes have been attributed to a discrepancy of how results are evaluated (i.e., on unofficial splits of the UrbanSound8K (US8K) dataset), distorting the overall progression of the field. The contribution of this paper is twofold. First, we present a model that is inherently compatible with mono and stereo sound inputs. Our model is based on simple log-power Short-Time Fourier Transform (STFT) spectrograms and combines them with several well-known approaches from the image domain (i.e., ResNet, Siamese-like networks and attention). We investigate the influence of cross-domain pre-training, architectural changes, and evaluate our model on standard datasets. We find that our model out-performs all previously known approaches in a fair comparison by achieving accuracies of 97.0 % (ESC-10), 91.5 % (ESC-50) and 84.2 % / 85.4 % (US8K mono / stereo). Second, we provide a comprehensive overview of the actual state of the field, by differentiating several previously reported results on the US8K dataset between official or unofficial splits. For better reproducibility, our code (including any re-implementations) is made available.
Optimal protocols for the most difficult repeated coordination games
Venue: arXiv cs.GT 2020
Year: 2020

This paper investigates repeated win-lose coordination games (WLC-games). We analyse which protocols are optimal for these games covering both the worst case and average case scenarios, i,e., optimizing the guaranteed and expected coordination times. We begin by analysing Choice Matching Games (CM-games) which are a simple yet fundamental type of WLC-games, where the goal of the players is to pick the same choice from a finite set of initially indistinguishable choices. We give a complete classification of optimal expected and guaranteed coordination times in two-player CM-games and show that the corresponding optimal protocols are unique in every case - except in the CM-game with four choices, which we analyse separately. Our results on CM-games are also essential for proving a more general result on the difficulty of all WLC-games: we provide a complete analysis of least upper bounds for optimal expected coordination times in all two-player WLC-games as a function of game size. We also show that CM-games can be seen as the most difficult games among all two-player WLC-games, as they turn out to have the greatest optimal expected coordination times.
Joint User Pairing and Association for Multicell NOMA: A Pointer Network-based Approach
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we investigate the joint user pairing and association problem for multicell non-orthogonal multiple access (NOMA) systems. We consider a scenario where the user equipments (UEs) are located in a multicell network equipped with multiple base stations. Each base station has multiple orthogonal physical resource blocks (PRBs). Each PRB can be allocated to a pair of UEs using NOMA. Each UE has the additional freedom to be served by any one of the base stations, which further increases the complexity of the joint user pairing and association algorithm design. Leveraging the recent success on using machine learning to solve numerical optimization problems, we formulate the joint user pairing and association problem as a combinatorial optimization problem. The solution is found using an emerging deep learning architecture called Pointer Network (PtrNet), which has a lower computational complexity compared to solutions based on iterative algorithms and has been proven to achieve near-optimal performance. The training phase of the PtrNet is based on deep reinforcement learning (DRL), and does not require the use of the optimal solution of the formulated problem as training labels. Simulation results show that the proposed joint user pairing and association scheme achieves near-optimal performance in terms of the aggregate data rate, and outperforms the random user pairing and association heuristic by up to 30%.
Faster Dynamic Matrix Inverse for Faster LPs
Venue: arXiv cs.DS 2020
Year: 2020

Motivated by recent Linear Programming solvers, we design dynamic data structures for maintaining the inverse of an $n\times n$ real matrix under $\textit{low-rank}$ updates, with polynomially faster amortized running time. Our data structure is based on a recursive application of the Woodbury-Morrison identity for implementing $\textit{cascading}$ low-rank updates, combined with recent sketching technology. Our techniques and amortized analysis of multi-level partial updates, may be of broader interest to dynamic matrix problems. This data structure leads to the fastest known LP solver for general (dense) linear programs, improving the running time of the recent algorithms of (Cohen et al.'19, Lee et al.'19, Brand'20) from $O^*(n^{2+ \max\{\frac{1}{6}, ω-2, \frac{1-α}{2}\}})$ to $O^*(n^{2+\max\{\frac{1}{18}, ω-2, \frac{1-α}{2}\}})$, where $ω$ and $α$ are the fast matrix multiplication exponent and its dual. Hence, under the common belief that $ω\approx 2$ and $α\approx 1$, our LP solver runs in $O^*(n^{2.055})$ time instead of $O^*(n^{2.16})$.
Multi-Objective Evolutionary approach for the Performance Improvement of Learners using Ensembling Feature selection and Discretization Technique on Medical data
Venue: arXiv cs.AI 2020
Year: 2020

Biomedical data is filled with continuous real values; these values in the feature set tend to create problems like underfitting, the curse of dimensionality and increase in misclassification rate because of higher variance. In response, pre-processing techniques on dataset minimizes the side effects and have shown success in maintaining the adequate accuracy. Feature selection and discretization are the two necessary preprocessing steps that were effectively employed to handle the data redundancies in the biomedical data. However, in the previous works, the absence of unified effort by integrating feature selection and discretization together in solving the data redundancy problem leads to the disjoint and fragmented field. This paper proposes a novel multi-objective based dimensionality reduction framework, which incorporates both discretization and feature reduction as an ensemble model for performing feature selection and discretization. Selection of optimal features and the categorization of discretized and non-discretized features from the feature subset is governed by the multi-objective genetic algorithm (NSGA-II). The two objective, minimizing the error rate during the feature selection and maximizing the information gain while discretization is considered as fitness criteria.
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
Venue: arXiv cs.DS 2020
Year: 2020

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to $(H_1,H_2)$-free graphs and a dichotomy for the latter problem restricted to $H$-free graphs. We find that there exists an infinite family of graphs $H$ such that Vertex Steiner Tree is polynomial-time solvable for $H$-free graphs, whereas there exist only two graphs $H$ for which this holds for Edge Steiner Tree. We also find that Edge Steiner Tree is polynomial-time solvable for $(H_1,H_2)$-free graphs if and only if the treewidth of the class of $(H_1,H_2)$-free graphs is bounded (subject to P $\neq$ NP). To obtain the latter result, we determine all pairs $(H_1,H_2)$ for which the class of $(H_1,H_2)$-free graphs has bounded treewidth.
Sieve: A Middleware Approach to Scalable Access Control for Database Management Systems
Venue: arXiv cs.DB 2020
Year: 2020

Current approaches of enforcing FGAC in Database Management Systems (DBMS) do not scale in scenarios when the number of policies are in the order of thousands. This paper identifies such a use case in the context of emerging smart spaces wherein systems may be required by legislation, such as Europe's GDPR and California's CCPA, to empower users to specify who may have access to their data and for what purposes. We present Sieve, a layered approach of implementing FGAC in existing database systems, that exploits a variety of it's features such as UDFs, index usage hints, query explain; to scale to large number of policies. Given a query, Sieve exploits it's context to filter the policies that need to be checked. Sieve also generates guarded expressions that saves on evaluation cost by grouping the policies and cuts the read cost by exploiting database indices. Our experimental results, on two DBMS and two different datasets, show that Sieve scales to large data sets and to large policy corpus thus supporting real-time access in applications including emerging smart environments.
Spatially Correlated Massive MIMO Relay Systems with Low-Resolution ADCs
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we investigate the massive MIMO relay system, where the relay station (RS) forwards the signals from multiple remote users to the base station (BS). Large-scale antenna arrays in conjunction with low-resolution analog-to-digital converters (ADCs) are equipped at the RS and the BS to guarantee the high spectral efficiency with low cost. Considering the ever-present spatial correlation at both the RS and the BS, we first study the canonical channel estimation process, from which a tractable equivalent form of the channel estimate is extracted for further analysis. Under these transmission impairments along with the ADC quantization imperfection, we derive the closed-form approximation of the achievable rate. Then the impacts of power scaling, spatial correlation level, and ADC resolution bits are revealed comprehensively to guide the practical system deployment and implementation. Numerical results are presented to verify the theoretical analysis in a straightforward way.
Entailment Checking in Separation Logic with Inductive Definitions is 2-EXPTIME hard
Venue: arXiv cs.LO 2020
Year: 2020

The entailment between separation logic formulae with inductive predicates, also known as symbolic heaps, has been shown to be decidable for a large class of inductive definitions. Recently, a 2-EXPTIME algorithm was proposed and an EXPTIME-hard bound was established; however no precise lower bound is known. In this paper, we show that deciding entailment between predicate atoms is 2-EXPTIME-hard. The proof is based on a reduction from the membership problem for exponential-space bounded alternating Turing machines.
A Robot by Any Other Frame: Framing and Behaviour Influence Mind Perception in Virtual but not Real-World Environments
Venue: arXiv cs.RO 2020
Year: 2020

Mind perception in robots has been an understudied construct in human-robot interaction (HRI) compared to similar concepts such as anthropomorphism and the intentional stance. In a series of three experiments, we identify two factors that could potentially influence mind perception and moral concern in robots: how the robot is introduced (framing), and how the robot acts (social behaviour). In the first two online experiments, we show that both framing and behaviour independently influence participants' mind perception. However, when we combined both variables in the following real-world experiment, these effects failed to replicate. We hence identify a third factor post-hoc: the online versus real-world nature of the interactions. After analysing potential confounds, we tentatively suggest that mind perception is harder to influence in real-world experiments, as manipulations are harder to isolate compared to virtual experiments, which only provide a slice of the interaction.
Diversity-Aware Weighted Majority Vote Classifier for Imbalanced Data
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we propose a diversity-aware ensemble learning based algorithm, referred to as DAMVI, to deal with imbalanced binary classification tasks. Specifically, after learning base classifiers, the algorithm i) increases the weights of positive examples (minority class) which are "hard" to classify with uniformly weighted base classifiers; and ii) then learns weights over base classifiers by optimizing the PAC-Bayesian C-Bound that takes into account the accuracy and diversity between the classifiers. We show efficiency of the proposed approach with respect to state-of-art models on predictive maintenance task, credit card fraud detection, webpage classification and medical applications.
Four Pages Are Indeed Necessary for Planar Graphs
Venue: arXiv cs.DS 2020
Year: 2020

An embedding of a graph in a book consists of a linear order of its vertices along the spine of the book and of an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. Accordingly, the book thickness of a class of graphs is the maximum book thickness over all its members. In this paper, we address a long-standing open problem regarding the exact book thickness of the class of planar graphs, which previously was known to be either three or four. We settle this problem by demonstrating planar graphs that require four pages in any of their book embeddings, thus establishing that the book thickness of the class of planar graphs is four.
Chaos-Based Multicarrier VLC Modulator With Compensation of LED Nonlinearity
Venue: arXiv cs.IT 2020
Year: 2020

The massive deployment of light-emitting diode (LED) lightning infrastructure has opened the opportunity to reuse it as visible light communication (VLC) to leverage the current RF spectrum crisis in indoor scenarios. One of the main problems in VLC is the limited dynamic range of LEDs and their nonlinear response, which may lead to a severe degradation in the communication, and more specifically in the bit error rate (BER). This is aggravated by the extensive usage of multicarrier multiplexing, based on optical orthogonal frequency division multiplexing (O-OFDM), characterized by a high peak-to-average power ratio. Here, we present a chaos-based coded modulation (CCM) setup specifically adapted to the LED nonlinearities. It replaces the usual modulation, while keeping the multicarrier O-OFDM structure unchanged. First, we obtain a semi-analytical bound for the bit error probability, taking into account the LED nonlinear response. The bound results particularly tight for the range of signal-to-noise ratio of interest. Then, we propose a method to design the modulator based on optimization techniques. The objective function is the semi-analytical bound, and the optimization is applied to a parameterization of the CCM conjugation function. This appropriately shapes the chaotic waveform and leads to BER improvements that outperform classical counterparts under ideal predistortion.
Video Face Manipulation Detection Through Ensemble of CNNs
Venue: arXiv cs.CV 2020
Year: 2020

In the last few years, several techniques for facial manipulation in videos have been successfully developed and made available to the masses (i.e., FaceSwap, deepfake, etc.). These methods enable anyone to easily edit faces in video sequences with incredibly realistic results and a very little effort. Despite the usefulness of these tools in many fields, if used maliciously, they can have a significantly bad impact on society (e.g., fake news spreading, cyber bullying through fake revenge porn). The ability of objectively detecting whether a face has been manipulated in a video sequence is then a task of utmost importance. In this paper, we tackle the problem of face manipulation detection in video sequences targeting modern facial manipulation techniques. In particular, we study the ensembling of different trained Convolutional Neural Network (CNN) models. In the proposed solution, different models are obtained starting from a base network (i.e., EfficientNetB4) making use of two different concepts: (i) attention layers; (ii) siamese training. We show that combining these networks leads to promising face manipulation detection results on two publicly available datasets with more than 119000 videos.
Covid Notions: Towards Formal Definitions -- and Documented Understanding -- of Privacy Goals and Claimed Protection in Proximity-Tracing Services
Venue: arXiv cs.CR 2020
Year: 2020

The recent SARS-CoV-2 pandemic gave rise to management approaches using mobile apps for contact tracing. The corresponding apps track individuals and their interactions, to facilitate alerting users of potential infections well before they become infectious themselves. Naive implementation obviously jeopardizes the privacy of health conditions, location, activities, and social interaction of its users. A number of protocol designs for colocation tracking have already been developed, most of which claim to function in a privacy preserving manner. However, despite claims such as "GDPR compliance", "anonymity", "pseudonymity" or other forms of "privacy", the authors of these designs usually neglect to precisely define what they (aim to) protect. We make a first step towards formally defining the privacy notions of proximity tracing services, especially with regards to the health, (co-)location, and social interaction of their users. We also give a high-level intuition of which protection the most prominent proposals can and cannot achieve. This initial overview indicates that all proposals include some centralized services, and none protects identity and (co-)locations of infected users perfectly from both other users and the service provider.
AuthCODE: A Privacy-preserving and Multi-device Continuous Authentication Architecture based on Machine and Deep Learning
Venue: arXiv cs.CR 2020
Year: 2020

The authentication field is evolving towards mechanisms able to keep users continuously authenticated without the necessity of remembering or possessing authentication credentials. While existing continuous authentication systems have demonstrated their suitability for single-device scenarios, the Internet of Things and next generation of mobile networks (5G) are enabling novel multi-device scenarios -- such as Smart Offices -- where continuous authentication is still an open challenge. The paper at hand, proposes an AI-based, privacy-preserving and multi-device continuous authentication architecture called AuthCODE. A realistic Smart Office scenario with several users, interacting with their mobile devices and personal computer, has been used to create a set of single- and multi-device behavioural datasets and validate AuthCODE. A pool of experiments with machine and deep learning classifiers measured the impact of time in authentication accuracy and improved the results of single-device approaches by considering multi-device behaviour profiles. The f1-score average reached for XGBoost on multi-device profiles based on 1-minute windows was 99.33%, while the best performance achieved for single devices was lower than 97.39%. The inclusion of temporal information in the form of vector sequences classified by a Long-Short Term Memory Network, allowed the identification of additional complex behaviour patterns associated to each user, resulting in an average f1-score of 99.02% on identification of long-term behaviours.