OpenRaiser/Intern-Atlas huggingface dataset:
Demonstration-Guided Deep Reinforcement Learning of Control Policies for Dexterous Human-Robot Interaction
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we propose a method for training control policies for human-robot interactions such as handshakes or hand claps via Deep Reinforcement Learning. The policy controls a humanoid Shadow Dexterous Hand, attached to a robot arm. We propose a parameterizable multi-objective reward function that allows learning of a variety of interactions without changing the reward structure. The parameters of the reward function are estimated directly from motion capture data of human-human interactions in order to produce policies that are perceived as being natural and human-like by observers. We evaluate our method on three significantly different hand interactions: handshake, hand clap and finger touch. We provide detailed analysis of the proposed reward function and the resulting policies and conduct a large-scale user study, indicating that our policy produces natural looking motions.
Identifying Emotions from Walking using Affective and Deep Features
Venue: arXiv cs.CV 2020
Year: 2020

We present a new data-driven model and algorithm to identify the perceived emotions of individuals based on their walking styles. Given an RGB video of an individual walking, we extract his/her walking gait in the form of a series of 3D poses. Our goal is to exploit the gait features to classify the emotional state of the human into one of four emotions: happy, sad, angry, or neutral. Our perceived emotion recognition approach uses deep features learned via LSTM on labeled emotion datasets. Furthermore, we combine these features with affective features computed from gaits using posture and movement cues. These features are classified using a Random Forest Classifier. We show that our mapping between the combined feature space and the perceived emotional state provides 80.07% accuracy in identifying the perceived emotions. In addition to classifying discrete categories of emotions, our algorithm also predicts the values of perceived valence and arousal from gaits. We also present an EWalk (Emotion Walk) dataset that consists of videos of walking individuals with gaits and labeled emotions. To the best of our knowledge, this is the first gait-based model to identify perceived emotions from videos of walking individuals.
Rényi Fair Inference
Venue: arXiv cs.LG 2020
Year: 2020

Machine learning algorithms have been increasingly deployed in critical automated decision-making systems that directly affect human lives. When these algorithms are only trained to minimize the training/test error, they could suffer from systematic discrimination against individuals based on their sensitive attributes such as gender or race. Recently, there has been a surge in machine learning society to develop algorithms for fair machine learning. In particular, many adversarial learning procedures have been proposed to impose fairness. Unfortunately, these algorithms either can only impose fairness up to first-order dependence between the variables, or they lack computational convergence guarantees. In this paper, we use Rényi correlation as a measure of fairness of machine learning models and develop a general training framework to impose fairness. In particular, we propose a min-max formulation which balances the accuracy and fairness when solved to optimality. For the case of discrete sensitive attributes, we suggest an iterative algorithm with theoretical convergence guarantee for solving the proposed min-max problem. Our algorithm and analysis are then specialized to fair classification and the fair clustering problem under disparate impact doctrine. Finally, the performance of the proposed Rényi fair inference framework is evaluated on Adult and Bank datasets.
Extending de Bruijn sequences to larger alphabets
Venue: arXiv cs.DM 2020
Year: 2020

A de Bruijn sequence of order n over a k-symbol alphabet is a circular sequence where each length-n sequence occurs exactly once. We present a way of extending de Bruijn sequences by adding a new symbol to the alphabet: the extension is performed by embedding a given de Bruijn sequence into another one of the same order, but over the alphabet with one more symbol, while ensuring that there are no long runs without the new symbol. Our solution is based on auxiliary graphs derived from the de Bruijn graph and solving a problem of maximum flow.
Parallel Performance of Molecular Dynamics Trajectory Analysis
Venue: arXiv cs.DC 2020
Year: 2020

The performance of biomolecular molecular dynamics simulations has steadily increased on modern high performance computing resources but acceleration of the analysis of the output trajectories has lagged behind so that analyzing simulations is becoming a bottleneck. To close this gap, we studied the performance of parallel trajectory analysis with MPI and the Python MDAnalysis library on three different XSEDE supercomputers where trajectories were read from a Lustre parallel file system. Strong scaling performance was impeded by stragglers, MPI processes that were slower than the typical process. Stragglers were less prevalent for compute-bound workloads, thus pointing to file reading as a bottleneck for scaling. However, a more complicated picture emerged in which both the computation and the data ingestion exhibited close to ideal strong scaling behavior whereas stragglers were primarily caused by either large MPI communication costs or long times to open the single shared trajectory file. We improved overall strong scaling performance by either subfiling (splitting the trajectory into separate files) or MPI-IO with Parallel HDF5 trajectory files. The parallel HDF5 approach resulted in near ideal strong scaling on up to 384 cores (16 nodes), thus reducing trajectory analysis times by two orders of magnitude compared to the serial approach.
The Ramanujan Machine: Automatically Generated Conjectures on Fundamental Constants
Venue: arXiv cs.LG 2020
Year: 2020

Fundamental mathematical constants like $e$ and $π$ are ubiquitous in diverse fields of science, from abstract mathematics to physics, biology and chemistry. For centuries, new formulas relating fundamental constants have been scarce and usually discovered sporadically. Here we propose a novel and systematic approach that leverages algorithms for deriving mathematical formulas for fundamental constants and help reveal their underlying structure. Our algorithms find dozens of well-known as well as previously unknown continued fraction representations of $π$, $e$, Catalan's constant, and values of the Riemann zeta function. Two example conjectures found by our algorithm and so far unproven are: \begin{equation*} \frac{24}{π^2} = 2 + 7\cdot 0\cdot 1+ \frac{8\cdot1^4}{2 + 7\cdot 1\cdot 2 + \frac{8\cdot2^4}{2 + 7\cdot 2\cdot 3 + \frac{8\cdot3^4}{2 + 7\cdot 3\cdot 4 + \frac{8\cdot4^4}{..}}}} \quad\quad,\quad\quad \frac{8}{7 ζ(3)} = 1\cdot 1 - \frac{1^6}{3\cdot 7 - \frac{2^6}{5\cdot 19 - \frac{3^6}{7\cdot 37 - \frac{4^6}{..}}}} \end{equation*} We present two algorithms that proved useful in finding conjectures: a Meet-In-The-Middle (MITM) algorithm and a Gradient Descent (GD) tailored to the recurrent structure of continued fractions. Both algorithms are based on matching numerical values and thus they conjecture formulas without providing proofs and without requiring prior knowledge on any underlying mathematical structure. This approach is especially attractive for constants for which no mathematical structure is known, as it reverses the conventional approach of sequential logic in formal proofs. Instead, our work supports a different approach for research: algorithms utilizing numerical data to unveil mathematical structures, thus trying to play the role of intuition of great mathematicians of the past, providing leads to new mathematical research.
Proper-walk connection number of graphs
Venue: arXiv cs.DM 2020
Year: 2020

This paper studies the problem of proper-walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly coloured walk between every pair of vertices of the graph i.e. a walk that does not use consecutively two edges of the same colour. The problem was already solved on several classes of graphs but still open in the general case. We establish that the problem can always be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with $k$ colours for every possible value of $k$.
Fully-Asynchronous Fully-Implicit Variable-Order Variable-Timestep Simulation of Neural Networks
Venue: arXiv cs.DC 2020
Year: 2020

State-of-the-art simulations of detailed neural models follow the Bulk Synchronous Parallel execution model. Execution is divided in equidistant communication intervals, equivalent to the shortest synaptic delay in the network. Neurons stepping is performed independently, with collective communication guiding synchronization and exchange of synaptic events. The interpolation step size is fixed and chosen based on some prior knowledge of the fastest possible dynamics in the system. However, simulations driven by stiff dynamics or a wide range of time scales - such as multiscale simulations of neural networks - struggle with fixed step interpolation methods, yielding excessive computation of intervals of quasi-constant activity, inaccurate interpolation of periods of high volatility solution, and being incapable of handling unknown or distinct time constants. A common alternative is the usage of adaptive stepping methods, however they have been deemed inefficient in parallel executions due to computational load imbalance at the synchronization barriers that characterize the BSP execution model. We introduce a distributed fully-asynchronous execution model that removes global synchronization, allowing for longer variable timestep interpolations. Asynchronicity is provided by active point-to-point communication notifying neurons' time advancement to synaptic connectivities. Time stepping is driven by scheduled neuron advancements based on synaptic delays across neurons, yielding an "exhaustive yet not speculative" adaptive-step execution. Execution benchmarks on 64 Cray XE6 compute nodes demonstrate a reduced number of interpolation steps, higher numerical accuracy and lower time to solution, compared to state-of-the-art methods. Efficiency is shown to be activity-dependent, with scaling of the algorithm demonstrated on a simulation of a laboratory experiment.
Space-Efficient Vertex Separators for Treewidth
Venue: arXiv cs.DS 2020
Year: 2020

For $n$-vertex graphs with treewidth $k = O(n^{1/2-ε})$ and an arbitrary $ε>0$, we present a word-RAM algorithm to compute vertex separators using only $O(n)$ bits of working memory. As an application of our algorithm, we give an $O(1)$-approximation algorithm for tree decomposition. Our algorithm computes a tree decomposition in $c^k n (\log \log n) \log^* n$ time using $O(n)$ bits for some constant $c > 0$. We finally use the tree decomposition obtained by our algorithm to solve Vertex Cover, Independent Set, Dominating Set, MaxCut and $q$-Coloring by using $O(n)$ bits as long as the treewidth of the graph is smaller than $c' \log n$ for some problem dependent constant $0 < c' < 1$.
Binary expression of ancestors in the Collatz graph
Venue: arXiv cs.DM 2020
Year: 2020

The Collatz graph is a directed graph with natural number nodes and where there is an edge from node $x$ to node $T(x)=T_0(x)=x/2$ if $x$ is even, or to node $T(x)=T_1(x)=\frac{3x+1}{2}$ if $x$ is odd. Studying the Collatz graph in binary reveals complex message passing behaviors based on carry propagation which seem to capture the essential dynamics and complexity of the Collatz process. We study the set $\mathcal{E} \text{Pred}_k(x)$ that contains the binary expression of any ancestor $y$ that reaches $x$ with a limited budget of $k$ applications of $T_1$. The set $\mathcal{E} \text{Pred}_k(x)$ is known to be regular, Shallit and Wilson [EATCS 1992]. In this paper, we find that the geometry of the Collatz graph naturally leads to the construction of a regular expression, $\texttt{reg}_k(x)$, which defines $\mathcal{E} \text{Pred}_k(x)$. Our construction, is exponential in $k$ which improves upon the doubly exponentially construction of Shallit and Wilson. Furthermore, our result generalises Colussi's work on the $x = 1$ case [TCS 2011] to any natural number $x$, and gives mathematical and algorithmic tools for further exploration of the Collatz graph in binary.
Private Authentication with Physical Identifiers Through Broadcast Channel Measurements
Venue: arXiv cs.IT 2020
Year: 2020

A basic model for key agreement with biometric or physical identifiers is extended to include measurements of a hidden source through a general broadcast channel (BC). An inner bound for strong secrecy, maximum key rate, and minimum privacy-leakage and database-storage rates is proposed. The inner bound is shown to be tight for physically-degraded and less-noisy BCs.
On the list decodability of Rank Metric codes
Venue: arXiv cs.IT 2020
Year: 2020

Let $k,n,m \in \mathbb{Z}^+$ integers such that $k\leq n \leq m$, let $\mathrm{G}_{n,k}\in \mathbb{F}_{q^m}^n$ be a Delsarte-Gabidulin code. Wachter-Zeh proven that codes belonging to this family cannot be efficiently list decoded for any radius $τ$, providing $τ$ is large enough. This achievement essentially relies on proving a lower bound for the list size of some specific words in $\mathbb{F}_{q^m}^n \setminus \mathrm{G}_{n,k}$. In 2016, Raviv and Wachter-Zeh improved this bound in a special case, i.e. when $n\mid m$. As a consequence, they were able to detect infinite families of Delsarte-Gabidulin codes that cannot be efficiently list decoded at all. In this article we determine similar lower bounds for Maximum Rank Distance codes belonging to a wider class of examples, containing Generalized Gabidulin codes, Generalized Twisted Gabidulin codes, and examples recently described by the first author and Yue Zhou. By exploiting arguments suchlike those used in the above mentioned papers, when $n\mid m$, we also show infinite families of generalized Gabidulin codes that cannot be list decoded efficiently at any radius greater than or equal to $\left\lfloor \frac{d-1}2 \right\rfloor+1$, where $d$ is its minimum distance. Nonetheless, in all other examples belonging to above mentioned class, we detect infinite families that cannot be list decoded efficiently at any radius greater than or equal to $\left\lfloor \frac{d-1}2 \right\rfloor+2$, where $d$ is its minimum distance. Finally, relying on the properties of a set of subspace trinomials recently presented by McGuire and Mueller, we are able to prove that any rank metric code of $\mathbb{F}_{q^m}^n$ of order $q^{kn}$ with $n$ dividing $m$, such that $4n-3$ is a square in $\mathbb{Z}$ and containing $\mathrm{G}_{n,2}$, is not efficiently list decodable at some values of the radius $τ$.
Voting-Based Multi-Agent Reinforcement Learning for Intelligent IoT
Venue: arXiv cs.LG 2020
Year: 2020

The recent success of single-agent reinforcement learning (RL) in Internet of things (IoT) systems motivates the study of multi-agent reinforcement learning (MARL), which is more challenging but more useful in large-scale IoT. In this paper, we consider a voting-based MARL problem, in which the agents vote to make group decisions and the goal is to maximize the globally averaged returns. To this end, we formulate the MARL problem based on the linear programming form of the policy optimization problem and propose a distributed primal-dual algorithm to obtain the optimal solution. We also propose a voting mechanism through which the distributed learning achieves the same sublinear convergence rate as centralized learning. In other words, the distributed decision making does not slow down the process of achieving global consensus on optimality. Lastly, we verify the convergence of our proposed algorithm with numerical simulations and conduct case studies in practical multi-agent IoT systems.
VELC: A New Variational AutoEncoder Based Model for Time Series Anomaly Detection
Venue: arXiv cs.LG 2020
Year: 2020

Anomaly detection is a classical but worthwhile problem, and many deep learning-based anomaly detection algorithms have been proposed, which can usually achieve better detection results than traditional methods. In view of reconstruct ability of the model and the calculation of anomaly score, this paper proposes a time series anomaly detection method based on Variational AutoEncoder model(VAE) with re-Encoder and Latent Constraint network(VELC). In order to modify reconstruct ability of the model to prevent it from reconstructing abnormal samples well, we add a constraint network in the latent space of the VAE to force it generate new latent variables that are similar with that of training samples. To be able to calculate anomaly score in two feature spaces, we train a re-encoder to transform the generated data to a new latent space. For better handling the time series, we use the LSTM as the encoder and decoder part of the VAE framework. Experimental results of several benchmarks show that our method outperforms state-of-the-art anomaly detection methods.
Solving Partial Assignment Problems using Random Clique Complexes
Venue: arXiv cs.LG 2020
Year: 2020

We present an alternate formulation of the partial assignment problem as matching random clique complexes, that are higher-order analogues of random graphs, designed to provide a set of invariants that better detect higher-order structure. The proposed method creates random clique adjacency matrices for each k-skeleton of the random clique complexes and matches them, taking into account each point as the affine combination of its geometric neighbourhood. We justify our solution theoretically, by analyzing the runtime and storage complexity of our algorithm along with the asymptotic behaviour of the quadratic assignment problem (QAP) that is associated with the underlying random clique adjacency matrices. Experiments on both synthetic and real-world datasets, containing severe occlusions and distortions, provide insight into the accuracy, efficiency, and robustness of our approach. We outperform diverse matching algorithms by a significant margin.
Circular Pattern Matching with $k$ Mismatches
Venue: arXiv cs.DS 2020
Year: 2020

The $k$-mismatch problem consists in computing the Hamming distance between a pattern $P$ of length $m$ and every length-$m$ substring of a text $T$ of length $n$, if this distance is no more than $k$. In many real-world applications, any cyclic rotation of $P$ is a relevant pattern, and thus one is interested in computing the minimal distance of every length-$m$ substring of $T$ and any cyclic rotation of $P$. This is the circular pattern matching with $k$ mismatches ($k$-CPM) problem. A multitude of papers have been devoted to solving this problem but, to the best of our knowledge, only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for the $k$-CPM problem. Specifically, we show an $O(nk)$-time algorithm and an $O(n+\frac{n}{m}\,k^4)$-time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the $k$-mismatch problem [Bringmann et al., SODA 2019]. A preliminary version of this work appeared at FCT 2019. In this version we improve the time complexity of the main algorithm from $O(n+\frac{n}{m}\,k^5)$ to $O(n+\frac{n}{m}\,k^4)$.
Dimensional Reweighting Graph Convolutional Networks
Venue: arXiv cs.LG 2020
Year: 2020

Graph Convolution Networks (GCNs) are becoming more and more popular for learning node representations on graphs. Though there exist various developments on sampling and aggregation to accelerate the training process and improve the performances, limited works focus on dealing with the dimensional information imbalance of node representations. To bridge the gap, we propose a method named Dimensional reweighting Graph Convolution Network (DrGCN). We theoretically prove that our DrGCN can guarantee to improve the stability of GCNs via mean field theory. Our dimensional reweighting method is very flexible and can be easily combined with most sampling and aggregation techniques for GCNs. Experimental results demonstrate its superior performances on several challenging transductive and inductive node classification benchmark datasets. Our DrGCN also outperforms existing models on an industrial-sized Alibaba recommendation dataset.
On Explaining Machine Learning Models by Evolving Crucial and Compact Features
Venue: arXiv cs.NE 2020
Year: 2020

Feature construction can substantially improve the accuracy of Machine Learning (ML) algorithms. Genetic Programming (GP) has been proven to be effective at this task by evolving non-linear combinations of input features. GP additionally has the potential to improve ML explainability since explicit expressions are evolved. Yet, in most GP works the complexity of evolved features is not explicitly bound or minimized though this is arguably key for explainability. In this article, we assess to what extent GP still performs favorably at feature construction when constructing features that are (1) Of small-enough number, to enable visualization of the behavior of the ML model; (2) Of small-enough size, to enable interpretability of the features themselves; (3) Of sufficient informative power, to retain or even improve the performance of the ML algorithm. We consider a simple feature construction scheme using three different GP algorithms, as well as random search, to evolve features for five ML algorithms, including support vector machines and random forest. Our results on 21 datasets pertaining to classification and regression problems show that constructing only two compact features can be sufficient to rival the use of the entire original feature set. We further find that a modern GP algorithm, GP-GOMEA, performs best overall. These results, combined with examples that we provide of readable constructed features and of 2D visualizations of ML behavior, lead us to positively conclude that GP-based feature construction still works well when explicitly searching for compact features, making it extremely helpful to explain ML models.
A Comparative Analysis of Knowledge-Intensive and Data-Intensive Semantic Parsers
Venue: arXiv cs.CL 2020
Year: 2020

We present a phenomenon-oriented comparative analysis of the two dominant approaches in task-independent semantic parsing: classic, knowledge-intensive and neural, data-intensive models. To reflect state-of-the-art neural NLP technologies, we introduce a new target structure-centric parser that can produce semantic graphs much more accurately than previous data-driven parsers. We then show that, in spite of comparable performance overall, knowledge- and data-intensive models produce different types of errors, in a way that can be explained by their theoretical properties. This analysis leads to new directions for parser development.
News and the city: understanding online press consumption patterns through mobile data
Venue: arXiv cs.CY 2020
Year: 2020

The always increasing mobile connectivity affects every aspect of our daily lives, including how and when we keep ourselves informed and consult news media. By studying a DPI (deep packet inspection) dataset, provided by one of the major Chilean telecommunication companies, we investigate how different cohorts of the population of Santiago De Chile consume news media content through their smartphones. We find that some socio-demographic attributes are highly associated to specific news media consumption patterns. In particular, education and age play a significant role in shaping the consumers behaviour even in the digital context, in agreement with a large body of literature on off-line media distribution channels.