OpenRaiser/Intern-Atlas huggingface dataset:
Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings
Venue: arXiv cs.DS 2020
Year: 2020

For a string $S$, a palindromic substring $S[i..j]$ is said to be a \emph{shortest unique palindromic substring} ($\mathit{SUPS}$) for an interval $[s, t]$ in $S$, if $S[i..j]$ occurs exactly once in $S$, the interval $[i, j]$ contains $[s, t]$, and every palindromic substring containing $[s, t]$ which is shorter than $S[i..j]$ occurs at least twice in $S$. In this paper, we study the problem of answering $\mathit{SUPS}$ queries on run-length encoded strings. We show how to preprocess a given run-length encoded string $\mathit{RLE}_{S}$ of size $m$ in $O(m)$ space and $O(m \log σ_{\mathit{RLE}_{S}} + m \sqrt{\log m / \log\log m})$ time so that all $\mathit{SUPSs}$ for any subsequent query interval can be answered in $O(\sqrt{\log m / \log\log m} + α)$ time, where $α$ is the number of outputs, and $σ_{\mathit{RLE}_{S}}$ is the number of distinct runs of $\mathit{RLE}_{S}$. Additionaly, we consider a variant of the SUPS problem where a query interval is also given in a run-length encoded form. For this variant of the problem, we present two alternative algorithms with faster queries. The first one answers queries in $O(\sqrt{\log\log m /\log\log\log m} + α)$ time and can be built in $O(m \log σ_{\mathit{RLE}_{S}} + m \sqrt{\log m / \log\log m})$ time, and the second one answers queries in $O(\log \log m + α)$ time and can be built in $O(m \log σ_{\mathit{RLE}_{S}})$ time. Both of these data structures require $O(m)$ space.
Multidimensional ground reaction forces and moments from wearable sensor accelerations via deep learning
Venue: arXiv cs.CV 2020
Year: 2020

Monitoring athlete internal workload exposure, including prevention of catastrophic non-contact knee injuries, relies on the existence of a custom early-warning detection system. This system must be able to estimate accurate, reliable, and valid musculoskeletal joint loads, for sporting maneuvers in near real-time and during match play. However, current methods are constrained to laboratory instrumentation, are labor and cost intensive, and require highly trained specialist knowledge, thereby limiting their ecological validity and wider deployment. An informative next step towards this goal would be a new method to obtain ground kinetics in the field. Here we show that kinematic data obtained from wearable sensor accelerometers, in lieu of embedded force platforms, can leverage recent supervised learning techniques to predict near real-time multidimensional ground reaction forces and moments (GRF/M). Competing convolutional neural network (CNN) deep learning models were trained using laboratory-derived stance phase GRF/M data and simulated sensor accelerations for running and sidestepping maneuvers derived from nearly half a million legacy motion trials. Then, predictions were made from each model driven by five sensor accelerations recorded during independent inter-laboratory data capture sessions. The proposed deep learning workbench achieved correlations to ground truth, by maximum discrete GRF component, of vertical Fz 0.97, anterior Fy 0.96 (both running), and lateral Fx 0.87 (sidestepping), with the strongest mean recorded across GRF components 0.89, and for GRM 0.65 (both sidestepping). These best-case correlations indicate the plausibility of the approach although the range of results was disappointing. The goal to accurately estimate near real-time on-field GRF/M will be improved by the lessons learned in this study [truncated].
Information Set Decoding in the Lee Metric with Applications to Cryptography
Venue: arXiv cs.CR 2020
Year: 2020

We convert Stern's information set decoding (ISD) algorithm to the ring $\mathbb{Z}/4 \mathbb{Z}$ equipped with the Lee metric. Moreover, we set up the general framework for a McEliece and a Niederreiter cryptosystem over this ring. The complexity of the ISD algorithm determines the minimum key size in these cryptosystems for a given security level. We show that using Lee metric codes can drastically decrease the key size, compared to Hamming metric codes. In the end we explain how our results can be generalized to other Galois rings $\mathbb{Z}/p^s\mathbb{Z}$.
What the Constant Velocity Model Can Teach Us About Pedestrian Motion Prediction
Venue: arXiv cs.CV 2020
Year: 2020

Pedestrian motion prediction is a fundamental task for autonomous robots and vehicles to operate safely. In recent years many complex approaches based on neural networks have been proposed to address this problem. In this work we show that - surprisingly - a simple Constant Velocity Model can outperform even state-of-the-art neural models. This indicates that either neural networks are not able to make use of the additional information they are provided with, or that this information is not as relevant as commonly believed. Therefore, we analyze how neural networks process their input and how it impacts their predictions. Our analysis reveals pitfalls in training neural networks for pedestrian motion prediction and clarifies false assumptions about the problem itself. In particular, neural networks implicitly learn environmental priors that negatively impact their generalization capability, the motion history of pedestrians is irrelevant and interactions are too complex to predict. Our work shows how neural networks for pedestrian motion prediction can be thoroughly evaluated and our results indicate which research directions for neural motion prediction are promising in future.
Capacity-Achieving Private Information Retrieval Codes from MDS-Coded Databases with Minimum Message Size
Venue: arXiv cs.IT 2020
Year: 2020

We consider constructing capacity-achieving linear codes with minimum message size for private information retrieval (PIR) from $N$ non-colluding databases, where each message is coded using maximum distance separable (MDS) codes, such that it can be recovered from accessing the contents of any $T$ databases. It is shown that the minimum message size (sometimes also referred to as the sub-packetization factor) is significantly, in fact exponentially, lower than previously believed. More precisely, when $K>T/\textbf{gcd}(N,T)$ where $K$ is the total number of messages in the system and $\textbf{gcd}(\cdot,\cdot)$ means the greatest common divisor, we establish, by providing both novel code constructions and a matching converse, the minimum message size as $\textbf{lcm}(N-T,T)$, where $\textbf{lcm}(\cdot,\cdot)$ means the least common multiple. On the other hand, when $K$ is small, we show that it is in fact possible to design codes with a message size even smaller than $\textbf{lcm}(N-T,T)$.
Modelling Graph Errors: Towards Robust Graph Signal Processing
Venue: arXiv cs.IT 2020
Year: 2020

The first step for any graph signal processing (GSP) procedure is to learn the graph signal representation, i.e., to capture the dependence structure of the data into an adjacency matrix. Indeed, the adjacency matrix is typically not known a priori and has to be learned. However, it is learned with errors. A little attention has been paid to modelling such errors in the adjacency matrix, and studying their effects on GSP methods. However, modelling errors in the adjacency matrix will enable both to study the graph error effects in GSP and to develop robust GSP algorithms. In this paper, we therefore introduce practically justifiable graph error models. We also study, both analytically when possible and numerically, the graph error effect on the performance of GSP methods in different types of problems such as filtering of graph signals and independent component analysis of graph signals (graph decorrelation).
Parallel Batch-Dynamic Graph Connectivity
Venue: arXiv cs.DS 2020
Year: 2020

In this paper, we study batch parallel algorithms for the dynamic connectivity problem, a fundamental problem that has received considerable attention in the sequential setting. The most well known sequential algorithm for dynamic connectivity is the elegant level-set algorithm of Holm, de Lichtenberg and Thorup (HDT), which achieves $O(\log^2 n)$ amortized time per edge insertion or deletion, and $O(\log n / \log\log n)$ time per query. We design a parallel batch-dynamic connectivity algorithm that is work-efficient with respect to the HDT algorithm for small batch sizes, and is asymptotically faster when the average batch size is sufficiently large. Given a sequence of batched updates, where $Δ$ is the average batch size of all deletions, our algorithm achieves $O(\log n \log(1 + n / Δ))$ expected amortized work per edge insertion and deletion and $O(\log^3 n)$ depth w.h.p. Our algorithm answers a batch of $k$ connectivity queries in $O(k \log(1 + n/k))$ expected work and $O(\log n)$ depth w.h.p. To the best of our knowledge, our algorithm is the first parallel batch-dynamic algorithm for connectivity.
Probabilistic logics based on Riesz spaces
Venue: arXiv cs.LO 2020
Year: 2020

We introduce a novel real-valued endogenous logic for expressing properties of probabilistic transition systems called Riesz modal logic. The design of the syntax and semantics of this logic is directly inspired by the theory of Riesz spaces, a mature field of mathematics at the intersection of universal algebra and functional analysis. By using powerful results from this theory, we develop the duality theory of the Riesz modal logic in the form of an algebra-to-coalgebra correspondence. This has a number of consequences including: a sound and complete axiomatization, the proof that the logic characterizes probabilistic bisimulation and other convenient results such as completion theorems. This work is intended to be the basis for subsequent research on extensions of Riesz modal logic with fixed-point operators.
A Survey on Graph Kernels
Venue: arXiv cs.LG 2020
Year: 2020

Graph kernels have become an established and widely-used technique for solving classification tasks on graphs. This survey gives a comprehensive overview of techniques for kernel-based graph classification developed in the past 15 years. We describe and categorize graph kernels based on properties inherent to their design, such as the nature of their extracted graph features, their method of computation and their applicability to problems in practice. In an extensive experimental evaluation, we study the classification accuracy of a large suite of graph kernels on established benchmarks as well as new datasets. We compare the performance of popular kernels with several baseline methods and study the effect of applying a Gaussian RBF kernel to the metric induced by a graph kernel. In doing so, we find that simple baselines become competitive after this transformation on some datasets. Moreover, we study the extent to which existing graph kernels agree in their predictions (and prediction errors) and obtain a data-driven categorization of kernels as result. Finally, based on our experimental results, we derive a practitioner's guide to kernel-based graph classification.
Privacy in trajectory micro-data publishing : a survey
Venue: arXiv cs.CR 2020
Year: 2020

We survey the literature on the privacy of trajectory micro-data, i.e., spatiotemporal information about the mobility of individuals, whose collection is becoming increasingly simple and frequent thanks to emerging information and communication technologies. The focus of our review is on privacy-preserving data publishing (PPDP), i.e., the publication of databases of trajectory micro-data that preserve the privacy of the monitored individuals. We classify and present the literature of attacks against trajectory micro-data, as well as solutions proposed to date for protecting databases from such attacks. This paper serves as an introductory reading on a critical subject in an era of growing awareness about privacy risks connected to digital services, and provides insights into open problems and future directions for research.
Towards 6G Networks: Use Cases and Technologies
Venue: arXiv cs.NI 2020
Year: 2020

Reliable data connectivity is vital for the ever increasingly intelligent, automated and ubiquitous digital world. Mobile networks are the data highways and, in a fully connected, intelligent digital world, will need to connect everything, from people to vehicles, sensors, data, cloud resources and even robotic agents. Fifth generation (5G) wireless networks (that are being currently deployed) offer significant advances beyond LTE, but may be unable to meet the full connectivity demands of the future digital society. Therefore, this article discusses technologies that will evolve wireless networks towards a sixth generation (6G), and that we consider as enablers for several potential 6G use cases. We provide a full-stack, system-level perspective on 6G scenarios and requirements, and select 6G technologies that can satisfy them either by improving the 5G design, or by introducing completely new communication paradigms.
Parallelizable global conformal parameterization of simply-connected surfaces via partial welding
Venue: arXiv cs.CG 2020
Year: 2020

Conformal surface parameterization is useful in graphics, imaging and visualization, with applications to texture mapping, atlas construction, registration, remeshing and so on. With the increasing capability in scanning and storing data, dense 3D surface meshes are common nowadays. While meshes with higher resolution better resemble smooth surfaces, they pose computational difficulties for the existing parameterization algorithms. In this work, we propose a novel parallelizable algorithm for computing the global conformal parameterization of simply-connected surfaces via partial welding maps. A given simply-connected surface is first partitioned into smaller subdomains. The local conformal parameterizations of all subdomains are then computed in parallel. The boundaries of the parameterized subdomains are subsequently integrated consistently using a novel technique called partial welding, which is developed based on conformal welding theory. Finally, by solving the Laplace equation for each subdomain using the updated boundary conditions, we obtain a global conformal parameterization of the given surface, with bijectivity guaranteed by quasi-conformal theory. By including additional shape constraints, our method can be easily extended to achieve disk conformal parameterization for simply-connected open surfaces and spherical conformal parameterization for genus-0 closed surfaces. Experimental results are presented to demonstrate the effectiveness of our proposed algorithm. When compared to the state-of-the-art conformal parameterization methods, our method achieves a significant improvement in both computational time and accuracy.
Elaboration Tolerant Representation of Markov Decision Process via Decision-Theoretic Extension of Probabilistic Action Language pBC+
Venue: arXiv cs.AI 2020
Year: 2020

We extend probabilistic action language pBC+ with the notion of utility as in decision theory. The semantics of the extended pBC+ can be defined as a shorthand notation for a decision-theoretic extension of the probabilistic answer set programming language LPMLN. Alternatively, the semantics of pBC+ can also be defined in terms of Markov Decision Process (MDP), which in turn allows for representing MDP in a succinct and elaboration tolerant way as well as to leverage an MDP solver to compute pBC+. The idea led to the design of the system pbcplus2mdp, which can find an optimal policy of a pBC+ action description using an MDP solver. This paper is under consideration in Theory and Practice of Logic Programming (TPLP).
Bayesian data analysis in empirical software engineering---The case of missing data
Venue: arXiv cs.SE 2020
Year: 2020

Bayesian data analysis (BDA) is today used by a multitude of research disciplines. These disciplines use BDA as a way to embrace uncertainty by using multilevel models and making use of all available information at hand. In this chapter, we first introduce the reader to BDA and then provide an example from empirical software engineering, where we also deal with a common issue in our field, i.e., missing data. The example we make use of presents the steps done when conducting state of the art statistical analysis. First, we need to understand the problem we want to solve. Second, we conduct causal analysis. Third, we analyze non-identifiability. Fourth, we conduct missing data analysis. Finally, we do a sensitivity analysis of priors. All this before we design our statistical model. Once we have a model, we present several diagnostics one can use to conduct sanity checks. We hope that through these examples, the reader will see the advantages of using BDA. This way, we hope Bayesian statistics will become more prevalent in our field, thus partly avoiding the reproducibility crisis we have seen in other disciplines.
Planning with Expectation Models
Venue: arXiv cs.LG 2020
Year: 2020

Distribution and sample models are two popular model choices in model-based reinforcement learning (MBRL). However, learning these models can be intractable, particularly when the state and action spaces are large. Expectation models, on the other hand, are relatively easier to learn due to their compactness and have also been widely used for deterministic environments. For stochastic environments, it is not obvious how expectation models can be used for planning as they only partially characterize a distribution. In this paper, we propose a sound way of using approximate expectation models for MBRL. In particular, we 1) show that planning with an expectation model is equivalent to planning with a distribution model if the state value function is linear in state features, 2) analyze two common parametrization choices for approximating the expectation: linear and non-linear expectation models, 3) propose a sound model-based policy evaluation algorithm and present its convergence results, and 4) empirically demonstrate the effectiveness of the proposed planning algorithm.
Performance Characterization of Relaying Using Backscatter Devices
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we examine the error performance of backscatter communication in the presence of ambient interference, where the backscatter device acts as a relay. Specifically, the performance comparison of amplify-and-forward (AF) and decode-and-forward (DF) backscatter relaying is considered for the first time. Considering energy-based detection for on-off keying (OOK) modulation, we derive the statistics of the received signal power, from which the detection thresholds and corresponding bit error rates (BER) are obtained analytically. For the DF scheme, we allow the source node to transmit continuous-wave signals during the relay-to-destination transmission phase to power the backscatter relay. Under a total power budget constraint at the source, we optimize the power allocation for the transmissions in the source-to-relay and relay-to-destination phases. Numerical analysis shows that the DF scheme with optimal power allocation performs similarly compared to the AF scheme, despite the added complexity of the decoding operation. On the other hand, the AF scheme significantly outperforms the DF scheme when the reflection coefficients at the backscatter device do not correspond to perfect OOK. These results provide valuable insights into the design and deployment of backscatter nodes with the goal of improving coverage.
Building an Efficient Intrusion Detection System Based on Feature Selection and Ensemble Classifier
Venue: arXiv cs.CR 2020
Year: 2020

Intrusion detection system (IDS) is one of extensively used techniques in a network topology to safeguard the integrity and availability of sensitive assets in the protected systems. Although many supervised and unsupervised learning approaches from the field of machine learning have been used to increase the efficacy of IDSs, it is still a problem for existing intrusion detection algorithms to achieve good performance. First, lots of redundant and irrelevant data in high-dimensional datasets interfere with the classification process of an IDS. Second, an individual classifier may not perform well in the detection of each type of attacks. Third, many models are built for stale datasets, making them less adaptable for novel attacks. Thus, we propose a new intrusion detection framework in this paper, and this framework is based on the feature selection and ensemble learning techniques. In the first step, a heuristic algorithm called CFS-BA is proposed for dimensionality reduction, which selects the optimal subset based on the correlation between features. Then, we introduce an ensemble approach that combines C4.5, Random Forest (RF), and Forest by Penalizing Attributes (Forest PA) algorithms. Finally, voting technique is used to combine the probability distributions of the base learners for attack recognition. The experimental results, using NSL-KDD, AWID, and CIC-IDS2017 datasets, reveal that the proposed CFS-BA-Ensemble method is able to exhibit better performance than other related and state of the art approaches under several metrics.
Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases
Venue: arXiv cs.DS 2020
Year: 2020

The six-vertex model in statistical physics is a weighted generalization of the ice model on $\mathbb{Z}^2$ (i.e., Eulerian orientations) and the zero-temperature three-state Potts model (i.e., proper three-colorings). The phase diagram of the model depicts its physical properties and suggests where local Markov chains will be efficient. In this paper, we analyze the mixing time of Glauber dynamics for the six-vertex model in the ordered phases. Specifically, we show that for all Boltzmann weights in the ferroelectric phase, there exist boundary conditions such that local Markov chains require exponential time to converge to equilibrium. This is the first rigorous result bounding the mixing time of Glauber dynamics in the ferroelectric phase. Our analysis demonstrates a fundamental connection between correlated random walks and the dynamics of intersecting lattice path models (or routings). We analyze the Glauber dynamics for the six-vertex model with free boundary conditions in the antiferroelectric phase and significantly extend the region for which local Markov chains are known to be slow mixing. This result relies on a Peierls argument and novel properties of weighted non-backtracking walks.
ICface: Interpretable and Controllable Face Reenactment Using GANs
Venue: arXiv cs.CV 2020
Year: 2020

This paper presents a generic face animator that is able to control the pose and expressions of a given face image. The animation is driven by human interpretable control signals consisting of head pose angles and the Action Unit (AU) values. The control information can be obtained from multiple sources including external driving videos and manual controls. Due to the interpretable nature of the driving signal, one can easily mix the information between multiple sources (e.g. pose from one image and expression from another) and apply selective post-production editing. The proposed face animator is implemented as a two-stage neural network model that is learned in a self-supervised manner using a large video collection. The proposed Interpretable and Controllable face reenactment network (ICface) is compared to the state-of-the-art neural network-based face animation techniques in multiple tasks. The results indicate that ICface produces better visual quality while being more versatile than most of the comparison methods. The introduced model could provide a lightweight and easy to use tool for a multitude of advanced image and video editing tasks.