OpenRaiser/Intern-Atlas huggingface dataset:
Query-points visibility constraint minimum link paths in simple polygons
Venue: arXiv cs.CG 2021
Year: 2021

We study the query version of constrained minimum link paths between two points inside a simple polygon $P$ with $n$ vertices such that there is at least one point on the path, visible from a query point. The method is based on partitioning $P$ into a number of faces of equal link distance from a point, called a link-based shortest path map (SPM). Initially, we solve this problem for two given points $s$, $t$ and a query point $q$. Then, the proposed solution is extended to a general case for three arbitrary query points $s$, $t$ and $q$. In the former, we propose an algorithm with $O(n)$ preprocessing time. Extending this approach for the latter case, we develop an algorithm with $O(n^3)$ preprocessing time. The link distance of a $q$-$visible$ path between $s$, $t$ as well as the path are provided in time $O(\log n)$ and $O(m+\log n)$, respectively, for the above two cases, where $m$ is the number of links.
NVTraverse: In NVRAM Data Structures, the Destination is More Important than the Journey
Venue: arXiv cs.DC 2021
Year: 2021

The recent availability of fast, dense, byte-addressable non-volatile memory has led to increasing interest in the problem of designing and specifying durable data structures that can recover from system crashes. However, designing durable concurrent data structures that are efficient and also satisfy a correctness criterion has proven to be very difficult, leading many algorithms to be inefficient or incorrect in a concurrent setting. In this paper, we present a general transformation that takes a lock-free data structure from a general class called traversal data structure (that we formally define) and automatically transforms it into an implementation of the data structure for the NVRAM setting that is provably durably linearizable and highly efficient. The transformation hinges on the observation that many data structure operations begin with a traversal phase that does not need to be persisted, and thus we only begin persisting when the traversal reaches its destination. We demonstrate the transformation's efficiency through extensive measurements on a system with Intel's recently released Optane DC persistent memory, showing that it can outperform competitors on many workloads.
Active recursive Bayesian inference using Rényi information measures
Venue: arXiv cs.LG 2021
Year: 2021

Recursive Bayesian inference (RBI) provides optimal Bayesian latent variable estimates in real-time settings with streaming noisy observations. Active RBI attempts to effectively select queries that lead to more informative observations to rapidly reduce uncertainty until a confident decision is made. However, typically the optimality objectives of inference and query mechanisms are not jointly selected. Furthermore, conventional active querying methods stagger due to misleading prior information. Motivated by information theoretic approaches, we propose an active RBI framework with unified inference and query selection steps through Renyi entropy and $α$-divergence. We also propose a new objective based on Renyi entropy and its changes called Momentum that encourages exploration for misleading prior cases. The proposed active RBI framework is applied to the trajectory of the posterior changes in the probability simplex that provides a coordinated active querying and decision making with specified confidence. Under certain assumptions, we analytically demonstrate that the proposed approach outperforms conventional methods such as mutual information by allowing the selections of unlikely events. We present empirical and experimental performance evaluations on two applications: restaurant recommendation and brain-computer interface (BCI) typing systems.
Evaluating Online Continual Learning with CALM
Venue: arXiv cs.CL 2021
Year: 2021

Online Continual Learning (OCL) studies learning over a continuous data stream without observing any single example more than once, a setting that is closer to the experience of humans and systems that must learn "on-the-wild". Yet, commonly available benchmarks are far from these real-world conditions, because they explicitly signal different tasks, lack latent similarity structure or assume temporal independence between different examples. Here, we propose a new benchmark for OCL based on language modelling in which input alternates between different languages and domains without any explicit delimitation. Additionally, we propose new metrics to study catastrophic forgetting in this setting and evaluate multiple baseline models based on compositions of experts. Finally, we introduce a simple gating technique that learns the latent similarities between different inputs, improving the performance of a Products of Experts model.
Field-mediated locomotor dynamics on highly deformable surfaces
Venue: arXiv cs.RO 2021
Year: 2021

In many systems motion occurs on deformed and deformable surfaces, setting up the possibility for dynamical interactions solely mediated by the coupling of the entities with their environment. Here we study the "two-body" dynamics of robot locomotion on a highly deformable spandex membrane in two scenarios: one in which a robot orbits a large central depression and the other where the two robots affect each other's motion solely through mutual environmental deformations. Inspired by the resemblance of the orbits of the single robot with those of general relativistic orbits around black holes, we recast the vehicle plus membrane dynamics in physical space into the geodesic motion of a "test particle" in a fiducial curved space-time and demonstrate how this framework facilitates understanding the observed dynamics. The two-robot problem also exhibits a resemblance with Einstein's general relativistic view of gravity, which in the words of Wheeler: "spacetime tells matter how to move; matter tells spacetime how to curve." We generalize this case the mapping to include a reciprocal coupling that translates into robotic curvature-based control schemes which modify interaction (promoting avoidance or aggregation) without long-range sensing. Our work provides a starting point for developing a mechanical analog gravity system as well as develops a framework that can provide insights into active matter in deformable environments and robot exploration in complex landscapes.
Capsule Networks -- A Probabilistic Perspective
Venue: arXiv cs.LG 2021
Year: 2021

'Capsule' models try to explicitly represent the poses of objects, enforcing a linear relationship between an object's pose and that of its constituent parts. This modelling assumption should lead to robustness to viewpoint changes since the sub-object/super-object relationships are invariant to the poses of the object. We describe a probabilistic generative model which encodes such capsule assumptions, clearly separating the generative parts of the model from the inference mechanisms. With a variational bound we explore the properties of the generative model independently of the approximate inference scheme, and gain insights into failures of the capsule assumptions and inference amortisation. We experimentally demonstrate the applicability of our unified objective, and demonstrate the use of test time optimisation to solve problems inherent to amortised inference in our model.
Locality Preserving Loss: Neighbors that Live together, Align together
Venue: arXiv cs.LG 2021
Year: 2021

We present a locality preserving loss (LPL) that improves the alignment between vector space embeddings while separating uncorrelated representations. Given two pretrained embedding manifolds, LPL optimizes a model to project an embedding and maintain its local neighborhood while aligning one manifold to another. This reduces the overall size of the dataset required to align the two in tasks such as cross-lingual word alignment. We show that the LPL-based alignment between input vector spaces acts as a regularizer, leading to better and consistent accuracy than the baseline, especially when the size of the training set is small. We demonstrate the effectiveness of LPL optimized alignment on semantic text similarity (STS), natural language inference (SNLI), multi-genre language inference (MNLI) and cross-lingual word alignment(CLA) showing consistent improvements, finding up to 16% improvement over our baseline in lower resource settings.
Multi-feature super-resolution network for cloth wrinkle synthesis
Venue: arXiv cs.GR 2021
Year: 2021

Existing physical cloth simulators suffer from expensive computation and difficulties in tuning mechanical parameters to get desired wrinkling behaviors. Data-driven methods provide an alternative solution. It typically synthesizes cloth animation at a much lower computational cost, and also creates wrinkling effects that highly resemble the much controllable training data. In this paper we propose a deep learning based method for synthesizing cloth animation with high resolution meshes. To do this we first create a dataset for training: a pair of low and high resolution meshes are simulated and their motions are synchronized. As a result the two meshes exhibit similar large-scale deformation but different small wrinkles. Each simulated mesh pair are then converted into a pair of low and high resolution "images" (a 2D array of samples), with each sample can be interpreted as any of three features: the displacement, the normal and the velocity. With these image pairs, we design a multi-feature super-resolution (MFSR) network that jointly train an upsampling synthesizer for the three features. The MFSR architecture consists of two key components: a sharing module that takes multiple features as input to learn low-level representations from corresponding super-resolution tasks simultaneously; and task-specific modules focusing on various high-level semantics. Frame-to-frame consistency is well maintained thanks to the proposed kinematics-based loss function. Our method achieves realistic results at high frame rates: 12-14 times faster than traditional physical simulation. We demonstrate the performance of our method with various experimental scenes, including a dressed character with sophisticated collisions.
Model-based actor-critic: GAN (model generator) + DRL (actor-critic) => AGI
Venue: arXiv cs.AI 2021
Year: 2021

Our effort is toward unifying GAN and DRL algorithms into a unifying AI model (AGI or general-purpose AI or artificial general intelligence which has general-purpose applications to: (A) offline learning (of stored data) like GAN in (un/semi-/fully-)SL setting such as big data analytics (mining) and visualization; (B) online learning (of real or simulated devices) like DRL in RL setting (with/out environment reward) such as (real or simulated) robotics and control; Our core proposal is adding an (generative/predictive) environment model to the actor-critic (model-free) architecture which results in a model-based actor-critic architecture with temporal-differencing (TD) error and an episodic memory. The proposed AI model is similar to (model-free) DDPG and therefore it's called model-based DDPG. To evaluate it, we compare it with (model-free) DDPG by applying them both to a variety (wide range) of independent simulated robotic and control task environments in OpenAI Gym and Unity Agents. Our initial limited experiments show that DRL and GAN in model-based actor-critic results in an incremental goal-driven intellignce required to solve each task with similar performance to (model-free) DDPG. Our future focus is to investigate the proposed AI model potential to: (A) unify DRL field inside AI by producing competitive performance compared to the best of model-based (PlaNet) and model-free (D4PG) approaches; (B) bridge the gap between AI and robotics communities by solving the important problem of reward engineering with learning the reward function by demonstration.
Towards Federated Learning With Byzantine-Robust Client Weighting
Venue: arXiv cs.LG 2021
Year: 2021

Federated Learning (FL) is a distributed machine learning paradigm where data is distributed among clients who collaboratively train a model in a computation process coordinated by a central server. By assigning a weight to each client based on the proportion of data instances it possesses, the rate of convergence to an accurate joint model can be greatly accelerated. Some previous works studied FL in a Byzantine setting, in which a fraction of the clients may send arbitrary or even malicious information regarding their model. However, these works either ignore the issue of data unbalancedness altogether or assume that client weights are apriori known to the server, whereas, in practice, it is likely that weights will be reported to the server by the clients themselves and therefore cannot be relied upon. We address this issue for the first time by proposing a practical weight-truncation-based preprocessing method and demonstrating empirically that it is able to strike a good balance between model quality and Byzantine robustness. We also establish analytically that our method can be applied to a randomly selected sample of client weights.
End-to-end Learning Improves Static Object Geo-localization in Monocular Video
Venue: arXiv cs.CV 2021
Year: 2021

Accurately estimating the position of static objects, such as traffic lights, from the moving camera of a self-driving car is a challenging problem. In this work, we present a system that improves the localization of static objects by jointly-optimizing the components of the system via learning. Our system is comprised of networks that perform: 1) 5DoF object pose estimation from a single image, 2) association of objects between pairs of frames, and 3) multi-object tracking to produce the final geo-localization of the static objects within the scene. We evaluate our approach using a publicly-available data set, focusing on traffic lights due to data availability. For each component, we compare against contemporary alternatives and show significantly-improved performance. We also show that the end-to-end system performance is further improved via joint-training of the constituent models.
Delay Sensitivity Classification of Cloud Gaming Content
Venue: arXiv cs.MM 2021
Year: 2021

Cloud Gaming is an emerging service that catches growing interest in the research community as well as industry. While the paradigm shift from a game execution on clients to streaming games from the cloud offers a variety of benefits, the new services also require a highly reliable and low latency network to achieve a satisfying Quality of Experience (QoE) for its users. Using a cloud gaming service with high latency would harm the interaction of the user with the game, leading to a decrease in playing performance and thus frustration of players. However, the negative effect of delay on gaming QoE depends strongly on the game content. At a certain level of delay, a slow-paced card game is typically not as delay sensitive as a shooting game. For optimal resource allocation and quality estimation, it is highly important for cloud providers, game developers, and network planners to consider the impact of the game content. This paper contributes to a better understanding of the delay impact on QoE for cloud gaming applications by identifying game characteristics influencing the delay perception of users. In addition, an expert evaluation methodology to quantify these characteristics, as well as a delay sensitivity classification based on a decision tree is presented. The ratings of 14 experts for the quantification indicated an excellent level of agreement which demonstrates the reliability of the proposed method. Additionally, the decision tree reached an accuracy of 86.6 % on determining the delay sensitivity classes which were derived from a large dataset of subjective input quality ratings during a series of experiments.
Relation Transformer Network
Venue: arXiv cs.CV 2021
Year: 2021

The extraction of a scene graph with objects as nodes and mutual relationships as edges is the basis for a deep understanding of image content. Despite recent advances, such as message passing and joint classification, the detection of visual relationships remains a challenging task due to sub-optimal exploration of the mutual interaction among the visual objects. In this work, we propose a novel transformer formulation for scene graph generation and relation prediction. We leverage the encoder-decoder architecture of the transformer for rich feature embedding of nodes and edges. Specifically, we model the node-to-node interaction with the self-attention of the transformer encoder and the edge-to-node interaction with the cross-attention of the transformer decoder. Further, we introduce a novel positional embedding suitable to handle edges in the decoder. Finally, our relation prediction module classifies the directed relation from the learned node and edge embedding. We name this architecture as Relation Transformer Network (RTN). On the Visual Genome and GQA dataset, we have achieved an overall mean of 4.85% and 3.1% point improvement in comparison with state-of-the-art methods. Our experiments show that Relation Transformer can efficiently model context across various datasets with small, medium, and large-scale relation classification.
Power Constrained Bandits
Venue: arXiv cs.LG 2021
Year: 2021

Contextual bandits often provide simple and effective personalization in decision making problems, making them popular tools to deliver personalized interventions in mobile health as well as other health applications. However, when bandits are deployed in the context of a scientific study -- e.g. a clinical trial to test if a mobile health intervention is effective -- the aim is not only to personalize for an individual, but also to determine, with sufficient statistical power, whether or not the system's intervention is effective. It is essential to assess the effectiveness of the intervention before broader deployment for better resource allocation. The two objectives are often deployed under different model assumptions, making it hard to determine how achieving the personalization and statistical power affect each other. In this work, we develop general meta-algorithms to modify existing algorithms such that sufficient power is guaranteed while still improving each user's well-being. We also demonstrate that our meta-algorithms are robust to various model mis-specifications possibly appearing in statistical studies, thus providing a valuable tool to study designers.
Minority Oversampling for Imbalanced Time Series Classification
Venue: arXiv cs.LG 2021
Year: 2021

Many important real-world applications involve time-series data with skewed distribution. Compared to conventional imbalance learning problems, the classification of imbalanced time-series data is more challenging due to high dimensionality and high inter-variable correlation. This paper proposes a structure preserving Oversampling method to combat the High-dimensional Imbalanced Time-series classification (OHIT). OHIT first leverages a density-ratio based shared nearest neighbor clustering algorithm to capture the modes of minority class in high-dimensional space. It then for each mode applies the shrinkage technique of large-dimensional covariance matrix to obtain accurate and reliable covariance structure. Finally, OHIT generates the structure-preserving synthetic samples based on multivariate Gaussian distribution by using the estimated covariance matrices. Experimental results on several publicly available time-series datasets (including unimodal and multimodal) demonstrate the superiority of OHIT against the state-of-the-art oversampling algorithms in terms of F1, G-mean, and AUC.
CrisisBench: Benchmarking Crisis-related Social Media Datasets for Humanitarian Information Processing
Venue: arXiv cs.SI 2021
Year: 2021

Time-critical analysis of social media streams is important for humanitarian organizations for planing rapid response during disasters. The \textit{crisis informatics} research community has developed several techniques and systems for processing and classifying big crisis-related data posted on social media. However, due to the dispersed nature of the datasets used in the literature (e.g., for training models), it is not possible to compare the results and measure the progress made towards building better models for crisis informatics tasks. In this work, we attempt to bridge this gap by combining various existing crisis-related datasets. We consolidate eight human-annotated datasets and provide 166.1k and 141.5k tweets for \textit{informativeness} and \textit{humanitarian} classification tasks, respectively. We believe that the consolidated dataset will help train more sophisticated models. Moreover, we provide benchmarks for both binary and multiclass classification tasks using several deep learning architecrures including, CNN, fastText, and transformers. We make the dataset and scripts available at: https://crisisnlp.qcri.org/crisis_datasets_benchmarks.html
On the Linguistic Capacity of Real-Time Counter Automata
Venue: arXiv cs.CL 2021
Year: 2021

Counter machines have achieved a newfound relevance to the field of natural language processing (NLP): recent work suggests some strong-performing recurrent neural networks utilize their memory as counters. Thus, one potential way to understand the success of these networks is to revisit the theory of counter computation. Therefore, we study the abilities of real-time counter machines as formal grammars, focusing on formal properties that are relevant for NLP models. We first show that several variants of the counter machine converge to express the same class of formal languages. We also prove that counter languages are closed under complement, union, intersection, and many other common set operations. Next, we show that counter machines cannot evaluate boolean expressions, even though they can weakly validate their syntax. This has implications for the interpretability and evaluation of neural network systems: successfully matching syntactic patterns does not guarantee that counter memory accurately encodes compositional semantics. Finally, we consider whether counter languages are semilinear. This work makes general contributions to the theory of formal languages that are of potential interest for understanding recurrent neural networks.
The Role of the Hercules Autonomous Vehicle During the COVID-19 Pandemic: An Autonomous Logistic Vehicle for Contactless Goods Transportation
Venue: arXiv cs.RO 2021
Year: 2021

Since early 2020, the coronavirus disease 2019 (COVID-19) has spread rapidly across the world. As at the date of writing this article, the disease has been globally reported in 223 countries and regions, infected over 108 million people and caused over 2.4 million deaths (https://covid19.who.int/, accessed on Feb. 17, 2021). Avoiding person-to-person transmission is an effective approach to control and prevent the pandemic. However, many daily activities, such as transporting goods in our daily life, inevitably involve person-to-person contact. Using an autonomous logistic vehicle to achieve contact-less goods transportation could alleviate this issue. For example, it can reduce the risk of virus transmission between the driver and customers. Moreover, many countries have imposed tough lockdown measures to reduce the virus transmission (e.g., retail, catering) during the pandemic, which causes inconveniences for human daily life. Autonomous vehicle can deliver the goods bought by humans, so that humans can get the goods without going out. These demands motivate us to develop an autonomous vehicle, named as Hercules, for contact-less goods transportation during the COVID-19 pandemic. The vehicle is evaluated through real-world delivering tasks under various traffic conditions.