OpenRaiser/Intern-Atlas huggingface dataset:
Impact of E-Scooters on Pedestrian Safety: A Field Study Using Pedestrian Crowd-Sensing
Venue: arXiv cs.CY 2020
Year: 2020

The popularity and proliferation of electric scooters (e-scooters) as a micromobility solution in our cities and urban communities has been rapidly rising. Rent-by-the-minute pricing and a healthy competition between micromobility service providers is also benefiting riders with low trip costs. However, an unprepared urban infrastructure, combined with uncertain operation policies and poor regulation enforcement, has resulted in e-scooter riders encroaching public spaces meant for pedestrians, thus causing significant safety concerns both for themselves and the pedestrians. As a consequence, it has become critical to understand the current state of pedestrian safety in our urban communities vis-à-vis e-scooter services, identify factors that impact pedestrian safety due to such services, and determine how to support pedestrian safety going forward. Unfortunately, to date there have been no realistic, data-driven efforts within the research community that address these issues. In this work, we conduct a field study to empirically investigate crowd-sensed encounter data between e-scooters and pedestrian participants on two urban university campuses over a three-month period. We also analyze encounter statistics and mobility trends that could identify potentially unsafe spatio-temporal zones for pedestrians. This first-of-its-kind work provides a preliminary blueprint on how crowd-sensed micromobility data can enable safety-related studies in urban communities.
HOTVis: Higher-Order Time-Aware Visualisation of Dynamic Graphs
Venue: arXiv cs.SI 2020
Year: 2020

Network visualisation techniques are important tools for the exploratory analysis of complex systems. While these methods are regularly applied to visualise data on complex networks, we increasingly have access to time series data that can be modelled as temporal networks or dynamic graphs. In dynamic graphs, the temporal ordering of time-stamped edges determines the causal topology of a system, i.e., which nodes can, directly and indirectly, influence each other via a so-called causal path. This causal topology is crucial to understand dynamical processes, assess the role of nodes, or detect clusters. However, we lack graph drawing techniques that incorporate this information into static visualisations. Addressing this gap, we present a novel dynamic graph visualisation algorithm that utilises higher-order graphical models of causal paths in time series data to compute time-aware static graph visualisations. These visualisations combine the simplicity and interpretability of static graphs with a time-aware layout algorithm that highlights patterns in the causal topology that result from the temporal dynamics of edges.
Covert Computation in Self-Assembled Circuits
Venue: arXiv cs.ET 2020
Year: 2020

Traditionally, computation within self-assembly models is hard to conceal because the self-assembly process generates a crystalline assembly whose computational history is inherently part of the structure itself. With no way to remove information from the computation, this computational model offers a unique problem: how can computational input and computation be hidden while still computing and reporting the final output? Designing such systems is inherently motivated by privacy concerns in biomedical computing and applications in cryptography. In this paper we propose the problem of performing ``covert computation'' within tile self-assembly that seeks to design self-assembly systems that ``conceal'' both the input and computational history of performed computations. We achieve these results within the growth-only restricted abstract Tile Assembly Model (aTAM) with positive and negative interactions. We show that general-case covert computation is possible by implementing a set of basic covert logic gates capable of simulating any circuit (functionally complete). To further motivate the study of covert computation, we apply our new framework to resolve an outstanding complexity question; we use our covert circuitry to show that the unique assembly verification problem within the growth-only aTAM with negative interactions is coNP-complete.
Contact Skill Imitation Learning for Robot-Independent Assembly Programming
Venue: arXiv cs.RO 2020
Year: 2020

Robotic automation is a key driver for the advancement of technology. The skills of human workers, however, are difficult to program and seem currently unmatched by technical systems. In this work we present a data-driven approach to extract and learn robot-independent contact skills from human demonstrations in simulation environments, using a Long Short Term Memory (LSTM) network. Our model learns to generate error-correcting sequences of forces and torques in task space from object-relative motion, which industrial robots carry out through a Cartesian force control scheme on the real setup. This scheme uses forward dynamics computation of a virtually conditioned twin of the manipulator to solve the inverse kinematics problem. We evaluate our methods with an assembly experiment, in which our algorithm handles part tilting and jamming in order to succeed. The results show that the skill is robust towards localization uncertainty in task space and across different joint configurations of the robot. With our approach, non-experts can easily program force-sensitive assembly tasks in a robot-independent way.
SPOCC: Scalable POssibilistic Classifier Combination -- toward robust aggregation of classifiers
Venue: arXiv cs.LG 2020
Year: 2020

We investigate a problem in which each member of a group of learners is trained separately to solve the same classification task. Each learner has access to a training dataset (possibly with overlap across learners) but each trained classifier can be evaluated on a validation dataset. We propose a new approach to aggregate the learner predictions in the possibility theory framework. For each classifier prediction, we build a possibility distribution assessing how likely the classifier prediction is correct using frequentist probabilities estimated on the validation set. The possibility distributions are aggregated using an adaptive t-norm that can accommodate dependency and poor accuracy of the classifier predictions. We prove that the proposed approach possesses a number of desirable classifier combination robustness properties.
The Runtime of the Compact Genetic Algorithm on Jump Functions
Venue: arXiv cs.NE 2020
Year: 2020

In the first and so far only mathematical runtime analysis of an estimation-of-distribution algorithm (EDA) on a multimodal problem, Hasenöhrl and Sutton (GECCO 2018) showed for any $k = o(n)$ that the compact genetic algorithm (cGA) with any hypothetical population size $μ= Ω(ne^{4k} + n^{3.5+\varepsilon})$ with high probability finds the optimum of the $n$-dimensional jump function with jump size $k$ in time $O(μn^{1.5} \log n)$. We significantly improve this result for small jump sizes $k \le \frac 1 {20} \ln n -1$. In this case, already for $μ= Ω(\sqrt n \log n) \cap \text{poly}(n)$ the runtime of the cGA with high probability is only $O(μ\sqrt n)$. For the smallest admissible values of $μ$, our result gives a runtime of $O(n \log n)$, whereas the previous one only shows $O(n^{5+\varepsilon})$. Since it is known that the cGA with high probability needs at least $Ω(μ\sqrt n)$ iterations to optimize the unimodal OneMx function, our result shows that the cGA in contrast to most classic evolutionary algorithms here is able to cross moderate-sized valleys of low fitness at no extra cost. For large $k$, we show that the exponential (in $k$) runtime guarantee of Hasenöhrl and Sutton is tight and cannot be improved, also not by using a smaller hypothetical population size. We prove that any choice of the hypothetical population size leads to a runtime that, with high probability, is at least exponential in the jump size $k$. This result might be the first non-trivial exponential lower bound for EDAs that holds for arbitrary parameter settings.
Align, Mask and Select: A Simple Method for Incorporating Commonsense Knowledge into Language Representation Models
Venue: arXiv cs.CL 2020
Year: 2020

The state-of-the-art pre-trained language representation models, such as Bidirectional Encoder Representations from Transformers (BERT), rarely incorporate commonsense knowledge or other knowledge explicitly. We propose a pre-training approach for incorporating commonsense knowledge into language representation models. We construct a commonsense-related multi-choice question answering dataset for pre-training a neural language representation model. The dataset is created automatically by our proposed "align, mask, and select" (AMS) method. We also investigate different pre-training tasks. Experimental results demonstrate that pre-training models using the proposed approach followed by fine-tuning achieve significant improvements over previous state-of-the-art models on two commonsense-related benchmarks, including CommonsenseQA and Winograd Schema Challenge. We also observe that fine-tuned models after the proposed pre-training approach maintain comparable performance on other NLP tasks, such as sentence classification and natural language inference tasks, compared to the original BERT models. These results verify that the proposed approach, while significantly improving commonsense-related NLP tasks, does not degrade the general language representation capabilities.
Tale of tails using rule augmented sequence labeling for event extraction
Venue: arXiv cs.IR 2020
Year: 2020

The problem of event extraction is a relatively difficult task for low resource languages due to the non-availability of sufficient annotated data. Moreover, the task becomes complex for tail (rarely occurring) labels wherein extremely less data is available. In this paper, we present a new dataset (InDEE-2019) in the disaster domain for multiple Indic languages, collected from news websites. Using this dataset, we evaluate several rule-based mechanisms to augment deep learning based models. We formulate our problem of event extraction as a sequence labeling task and perform extensive experiments to study and understand the effectiveness of different approaches. We further show that tail labels can be easily incorporated by creating new rules without the requirement of large annotated data.
Feature Interaction-aware Graph Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Inspired by the immense success of deep learning, graph neural networks (GNNs) are widely used to learn powerful node representations and have demonstrated promising performance on different graph learning tasks. However, most real-world graphs often come with high-dimensional and sparse node features, rendering the learned node representations from existing GNN architectures less expressive. In this paper, we propose \textit{Feature Interaction-aware Graph Neural Networks (FI-GNNs)}, a plug-and-play GNN framework for learning node representations encoded with informative feature interactions. Specifically, the proposed framework is able to highlight informative feature interactions in a personalized manner and further learn highly expressive node representations on feature-sparse graphs. Extensive experiments on various datasets demonstrate the superior capability of FI-GNNs for graph learning tasks.
A Novel Privacy-Preserving Deep Learning Scheme without Using Cryptography Component
Venue: arXiv cs.CR 2020
Year: 2020

Recently, deep learning, which uses Deep Neural Networks (DNN), plays an important role in many fields. A secure neural network model with a secure training/inference scheme is indispensable to many applications. To accomplish such a task usually needs one of the entities (the customer or the service provider) to provide private information (customer's data or the model) to the other. Without a secure scheme and the mutual trust between the service providers and their customers, it will be an impossible mission. In this paper, we propose a novel privacy-preserving deep learning model and a secure training/inference scheme to protect the input, the output, and the model in the application of the neural network. We utilize the innate properties of a deep neural network to design a secure mechanism without using any complicated cryptography component. The security analysis shows our proposed scheme is secure and the experimental results also demonstrate that our method is very efficient and suitable for real applications.
Deep High-Resolution Representation Learning for Visual Recognition
Venue: arXiv cs.CV 2020
Year: 2020

High-resolution representations are essential for position-sensitive vision problems, such as human pose estimation, semantic segmentation, and object detection. Existing state-of-the-art frameworks first encode the input image as a low-resolution representation through a subnetwork that is formed by connecting high-to-low resolution convolutions \emph{in series} (e.g., ResNet, VGGNet), and then recover the high-resolution representation from the encoded low-resolution representation. Instead, our proposed network, named as High-Resolution Network (HRNet), maintains high-resolution representations through the whole process. There are two key characteristics: (i) Connect the high-to-low resolution convolution streams \emph{in parallel}; (ii) Repeatedly exchange the information across resolutions. The benefit is that the resulting representation is semantically richer and spatially more precise. We show the superiority of the proposed HRNet in a wide range of applications, including human pose estimation, semantic segmentation, and object detection, suggesting that the HRNet is a stronger backbone for computer vision problems. All the codes are available at~{\url{https://github.com/HRNet}}.
Genetic Algorithm for the 0/1 Multidimensional Knapsack Problem
Venue: arXiv cs.NE 2020
Year: 2020

The 0/1 multidimensional knapsack problem is the 0/1 knapsack problem with m constraints which makes it difficult to solve using traditional methods like dynamic programming or branch and bound algorithms. We present a genetic algorithm for the multidimensional knapsack problem with Java and C++ code that is able to solve publicly available instances in a very short computational duration. Our algorithm uses iteratively computed Lagrangian multipliers as constraint weights to augment the greedy algorithm for the multidimensional knapsack problem and uses that information in a greedy crossover in a genetic algorithm. The algorithm uses several other hyperparameters which can be set in the code to control convergence. Our algorithm improves upon the algorithm by Chu and Beasley in that it converges to optimum or near optimum solutions much faster.
Hebbian Graph Embeddings
Venue: arXiv cs.LG 2020
Year: 2020

Representation learning has recently been successfully used to create vector representations of entities in language learning, recommender systems and in similarity learning. Graph embeddings exploit the locality structure of a graph and generate embeddings for nodes which could be words in a language, products of a retail website; and the nodes are connected based on a context window. In this paper, we consider graph embeddings with an error-free associative learning update rule, which models the embedding vector of node as a non-convex Gaussian mixture of the embeddings of the nodes in its immediate vicinity with some constant variance that is reduced as iterations progress. It is very easy to parallelize our algorithm without any form of shared memory, which makes it possible to use it on very large graphs with a much higher dimensionality of the embeddings. We study the efficacy of proposed method on several benchmark data sets and favorably compare with state of the art methods. Further, proposed method is applied to generate relevant recommendations for a large retailer.
Revealed Preferences for Matching with Contracts
Venue: arXiv cs.GT 2020
Year: 2020

Many-to-many matching with contracts is studied in the framework of revealed preferences. All preferences are described by choice functions that satisfy natural conditions. Under a no-externality assumption individual preferences can be aggregated into a single choice function expressing a collective preference. In this framework, a two-sided matching problem may be described as an agreement problem between two parties: the two parties must find a stable agreement, i.e., a set of contracts from which no party will want to take away any contract and to which the two parties cannot agree to add any contract. On such stable agreements each party's preference relation is a partial order and the two parties have inverse preferences. An algorithm is presented that generalizes algorithms previously proposed in less general situations. This algorithm provides a stable agreement that is preferred to all stable agreements by one of the parties and therefore less preferred than all stable agreements by the other party. The number of steps of the algorithm is linear in the size of the set of contracts, i.e., polynomial in the size of the problem. The algorithm provides a proof that stable agreements form a lattice under the two inverse preference relations. Under additional assumptions on the role of money in preferences, agreement problems can describe general two-sided markets in which goods are exchanged for money. Stable agreements provide a solution concept, including prices, that is more general than competitive equilibria. They satisfy an almost one price law for identical items.
Bi-Homomorphic Lattice-Based PRFs and Unidirectional Updatable Encryption
Venue: arXiv cs.CR 2020
Year: 2020

We define a pseudorandom function (PRF) $F: \mathcal{K} \times \mathcal{X} \rightarrow \mathcal{Y}$ to be bi-homomorphic when it is fully Key homomorphic and partially Input Homomorphic (KIH), i.e., given $F(k_1, x_1)$ and $F(k_2, x_2)$, there is an efficient algorithm to compute $F(k_1 \oplus k_2, x_1 \ominus x_2)$, where $\oplus$ and $\ominus$ are (binary) group operations. The homomorphism on the input is restricted to a fixed subset of the input bits, i.e., $\ominus$ operates on some pre-decided $m$-out-of-$n$ bits, where $|x_1| = |x_2| = n$, and the remaining $n-m$ bits are identical in both inputs. In addition, the output length, $\ell$, of the operator $\ominus$ is not fixed and is defined as $n \leq \ell \leq 2n$, hence leading to Homomorphically induced Variable input Length (HVL) as $n \leq |x_1 \ominus x_2| \leq 2n$. We present a learning with errors (LWE) based construction for a HVL-KIH-PRF family. Our construction is inspired by the key homomorphic PRF construction due to Banerjee and Peikert (Crypto 2014). An updatable encryption scheme allows rotations of the encryption key, i.e., moving existing ciphertexts from old to new key. These updates are carried out via \emph{update tokens}, which can be used by an untrusted party since the update procedure does not involve decryption of the ciphertext. We use our novel PRF family to construct an updatable encryption scheme, named QPC-UE-UU, which is quantum-safe, post-compromise secure and supports unidirectional ciphertext updates, i.e., the update tokens can be used to perform ciphertext updates but they cannot be used to undo already completed updates. Our PRF family also leads to the first left/right key homomorphic constrained-PRF family with HVL.
Integration of Blockchain and Cloud of Things: Architecture, Applications and Challenges
Venue: arXiv cs.CR 2020
Year: 2020

The blockchain technology is taking the world by storm. Blockchain with its decentralized, transparent and secure nature has emerged as a disruptive technology for the next generation of numerous industrial applications. One of them is Cloud of Things enabled by the combination of cloud computing and Internet of Things. In this context, blockchain provides innovative solutions to address challenges in Cloud of Things in terms of decentralization, data privacy and network security, while Cloud of Things offer elasticity and scalability functionalities to improve the efficiency of blockchain operations. Therefore, a novel paradigm of blockchain and Cloud of Things integration, called BCoT, has been widely regarded as a promising enabler for a wide range of application scenarios. In this paper, we present a state-of-the-art review on the BCoT integration to provide general readers with an overview of the BCoT in various aspects, including background knowledge, motivation, and integrated architecture. Particularly, we also provide an in-depth survey of BCoT applications in different use-case domains such as smart healthcare, smart city, smart transportation and smart industry. Then, we review the recent BCoT developments with the emerging blockchain and cloud platforms, services, and research projects. Finally, some important research challenges and future directions are highlighted to spur further research in this promising area.
Generator evaluator-selector net for panoptic image segmentation and splitting unfamiliar objects into parts
Venue: arXiv cs.CV 2020
Year: 2020

In machine learning and other fields, suggesting a good solution to a problem is usually a harder task than evaluating the quality of such a solution. This asymmetry is the basis for a large number of selection oriented methods that use a generator system to guess a set of solutions and an evaluator system to rank and select the best solutions. This work examines the use of this approach to the problem of panoptic image segmentation and class agnostic parts segmentation. The generator/evaluator approach for this case consists of two independent convolutional neural nets: a generator net that suggests variety segments corresponding to objects, stuff and parts regions in the image, and an evaluator net that chooses the best segments to be merged into the segmentation map. The result is a trial and error evolutionary approach in which a generator that guesses segments with low average accuracy, but with wide variability, can still produce good results when coupled with an accurate evaluator. The generator consists of a Pointer net that receives an image and a point in the image, and predicts the region of the segment containing the point. Generating and evaluating each segment separately is essential in this case since it demands exponentially fewer guesses compared to a system that guesses and evaluates the full segmentation map in each try. The classification of the selected segments is done by an independent region-specific classification net. This allows the segmentation to be class agnostic and hence, capable of segmenting unfamiliar categories that were not part of the training set. The method was examined on the COCO Panoptic segmentation benchmark and gave results comparable to those of the basic semantic segmentation and Mask-RCNN methods. In addition, the system was used for the task of splitting objects of unseen classes (that did not appear in the training set) into parts.
Dynamics-aware Embeddings
Venue: arXiv cs.LG 2020
Year: 2020

In this paper we consider self-supervised representation learning to improve sample efficiency in reinforcement learning (RL). We propose a forward prediction objective for simultaneously learning embeddings of states and action sequences. These embeddings capture the structure of the environment's dynamics, enabling efficient policy learning. We demonstrate that our action embeddings alone improve the sample efficiency and peak performance of model-free RL on control from low-dimensional states. By combining state and action embeddings, we achieve efficient learning of high-quality policies on goal-conditioned continuous control from pixel observations in only 1-2 million environment steps.