OpenRaiser/Intern-Atlas huggingface dataset:
Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets: Collinearity Testing and Related Problems
Venue: arXiv cs.CG 2020
Year: 2020

We present subquadratic algorithms, in the algebraic decision-tree model of computation, for detecting whether there exists a triple of points, belonging to three respective sets $A$, $B$, and $C$ of points in the plane, that satisfy a certain polynomial equation or two equations. The best known instance of such a problem is testing for the existence of a collinear triple of points in $A\times B\times C$, a classical 3SUM-hard problem that has so far defied any attempt to obtain a subquadratic solution, whether in the (uniform) real RAM model, or in the algebraic decision-tree model. While we are still unable to solve this problem, in full generality, in subquadratic time, we obtain such a solution, in the algebraic decision-tree model, that uses only roughly $O(n^{28/15})$ constant-degree polynomial sign tests, for the special case where two of the sets lie on two respective one-dimensional curves and the third is placed arbitrarily in the plane. Our technique is fairly general, and applies to many other problems where we seek a triple that satisfies a single polynomial equation, e.g., determining whether $A\times B\times C$ contains a triple spanning a unit-area triangle. This result extends recent work by Barba \etal~(2017) and by Chan (2018), where all three sets $A$,~$B$, and~$C$ are assumed to be one-dimensional. As a second application of our technique, we again have three $n$-point sets $A$, $B$, and $C$ in the plane, and we want to determine whether there exists a triple $(a,b,c) \in A\times B\times C$ that simultaneously satisfies two independent real polynomial equations. For example, this is the setup when testing for collinearity in the complex plane, when each of the sets $A$, $B$, $C$ lies on some constant-degree algebraic curve. We show that problems of this kind can be solved with roughly $O(n^{24/13})$ constant-degree polynomial sign tests.
Covering the Relational Join
Venue: arXiv cs.DB 2020
Year: 2020

In this paper, we initiate a theoretical study of what we call the join covering problem. We are given a natural join query instance $Q$ on $n$ attributes and $m$ relations $(R_i)_{i \in [m]}$. Let $J_{Q} = \ \Join_{i=1}^m R_i$ denote the join output of $Q$. In addition to $Q$, we are given a parameter $Δ: 1\le Δ\le n$ and our goal is to compute the smallest subset $\mathcal{T}_{Q, Δ} \subseteq J_{Q}$ such that every tuple in $J_{Q}$ is within Hamming distance $Δ- 1$ from some tuple in $\mathcal{T}_{Q, Δ}$. The join covering problem captures both computing the natural join from database theory and constructing a covering code with covering radius $Δ- 1$ from coding theory, as special cases. We consider the combinatorial version of the join covering problem, where our goal is to determine the worst-case $|\mathcal{T}_{Q, Δ}|$ in terms of the structure of $Q$ and value of $Δ$. One obvious approach to upper bound $|\mathcal{T}_{Q, Δ}|$ is to exploit a distance property (of Hamming distance) from coding theory and combine it with the worst-case bounds on output size of natural joins (AGM bound hereon) due to Atserias, Grohe and Marx [SIAM J. of Computing'13]. Somewhat surprisingly, this approach is not tight even for the case when the input relations have arity at most two. Instead, we show that using the polymatroid degree-based bound of Abo Khamis, Ngo and Suciu [PODS'17] in place of the AGM bound gives us a tight bound (up to constant factors) on the $|\mathcal{T}_{Q, Δ}|$ for the arity two case. We prove lower bounds for $|\mathcal{T}_{Q, Δ}|$ using well-known classes of error-correcting codes e.g, Reed-Solomon codes. We can extend our results for the arity two case to general arity with a polynomial gap between our upper and lower bounds.
Distributed Reinforcement Learning for Cooperative Multi-Robot Object Manipulation
Venue: arXiv cs.RO 2020
Year: 2020

We consider solving a cooperative multi-robot object manipulation task using reinforcement learning (RL). We propose two distributed multi-agent RL approaches: distributed approximate RL (DA-RL), where each agent applies Q-learning with individual reward functions; and game-theoretic RL (GT-RL), where the agents update their Q-values based on the Nash equilibrium of a bimatrix Q-value game. We validate the proposed approaches in the setting of cooperative object manipulation with two simulated robot arms. Although we focus on a small system of two agents in this paper, both DA-RL and GT-RL apply to general multi-agent systems, and are expected to scale well to large systems.
Towards Time-Aware Context-Aware Deep Trust Prediction in Online Social Networks
Venue: arXiv cs.SI 2020
Year: 2020

Trust can be defined as a measure to determine which source of information is reliable and with whom we should share or from whom we should accept information. There are several applications for trust in Online Social Networks (OSNs), including social spammer detection, fake news detection, retweet behaviour detection and recommender systems. Trust prediction is the process of predicting a new trust relation between two users who are not currently connected. In applications of trust, trust relations among users need to be predicted. This process faces many challenges, such as the sparsity of user-specified trust relations, the context-awareness of trust and changes in trust values over time. In this dissertation, we analyse the state-of-the-art in pair-wise trust prediction models in OSNs. We discuss three main challenges in this domain and present novel trust prediction approaches to address them. We first focus on proposing a low-rank representation of users that incorporates users' personality traits as additional information. Then, we propose a set of context-aware trust prediction models. Finally, by considering the time-dependency of trust relations, we propose a dynamic deep trust prediction approach. We design and implement five pair-wise trust prediction approaches and evaluate them with real-world datasets collected from OSNs. The experimental results demonstrate the effectiveness of our approaches compared to other state-of-the-art pair-wise trust prediction models.
Appearance Fusion of Multiple Cues for Video Co-localization
Venue: arXiv cs.CV 2020
Year: 2020

This work addresses the joint object discovery problem in videos while utilizing multiple object-related cues. In contrast to the usual spatial fusion approach, a novel appearance fusion approach is presented here. Specifically, this paper proposes an effective fusion process of different GMMs derived from multiple cues into one GMM. Much the same as any fusion strategy, this approach also needs some guidance. The proposed method relies on reliability and consensus phenomenon for guidance. As a case study, we pursue the "video co-localization" object discovery problem to propose our methodology. Our experiments on YouTube Objects and YouTube Co-localization datasets demonstrate that the proposed method of appearance fusion undoubtedly has an advantage over both the spatial fusion strategy and the current state-of-the-art video co-localization methods.
A Quantum Vocal Theory of Sound
Venue: arXiv cs.SD 2020
Year: 2020

Concepts and formalism from acoustics are often used to exemplify quantum mechanics. Conversely, quantum mechanics could be used to achieve a new perspective on acoustics, as shown by Gabor studies. Here, we focus in particular on the study of human voice, considered as a probe to investigate the world of sounds. We present a theoretical framework that is based on observables of vocal production, and on some measurement apparati that can be used both for analysis and synthesis. In analogy to the description of spin states of a particle, the quantum-mechanical formalism is used to describe the relations between the fundamental states associated with phonetic labels such as phonation, turbulence, and supraglottal myoelastic vibrations. The intermingling of these states, and their temporal evolution, can still be interpreted in the Fourier/Gabor plane, and effective extractors can be implemented. The bases for a Quantum Vocal Theory of Sound, with implications in sound analysis and design, are presented.
Adaptive Informative Path Planning with Multimodal Sensing
Venue: arXiv cs.AI 2020
Year: 2020

Adaptive Informative Path Planning (AIPP) problems model an agent tasked with obtaining information subject to resource constraints in unknown, partially observable environments. Existing work on AIPP has focused on representing observations about the world as a result of agent movement. We formulate the more general setting where the agent may choose between different sensors at the cost of some energy, in addition to traversing the environment to gather information. We call this problem AIPPMS (MS for Multimodal Sensing). AIPPMS requires reasoning jointly about the effects of sensing and movement in terms of both energy expended and information gained. We frame AIPPMS as a Partially Observable Markov Decision Process (POMDP) and solve it with online planning. Our approach is based on the Partially Observable Monte Carlo Planning framework with modifications to ensure constraint feasibility and a heuristic rollout policy tailored for AIPPMS. We evaluate our method on two domains: a simulated search-and-rescue scenario and a challenging extension to the classic RockSample problem. We find that our approach outperforms a classic AIPP algorithm that is modified for AIPPMS, as well as online planning using a random rollout policy.
Smarter Parking: Using AI to Identify Parking Inefficiencies in Vancouver
Venue: arXiv cs.CY 2020
Year: 2020

On-street parking is convenient, but has many disadvantages: on-street spots come at the expense of other road uses such as traffic lanes, transit lanes, bike lanes, or parklets; drivers looking for parking contribute substantially to traffic congestion and hence to greenhouse gas emissions; safety is reduced both due to the fact that drivers looking for spots are more distracted than other road users and that people exiting parked cars pose a risk to cyclists. These social costs may not be worth paying when off-street parking lots are nearby and have surplus capacity. To see where this might be true in downtown Vancouver, we used artificial intelligence techniques to estimate the amount of time it would take drivers to both park on and off street for destinations throughout the city. For on-street parking, we developed (1) a deep-learning model of block-by-block parking availability based on data from parking meters and audits and (2) a computational simulation of drivers searching for an on-street spot. For off-street parking, we developed a computational simulation of the time it would take drivers drive from their original destination to the nearest city-owned off-street lot and then to queue for a spot based on traffic and lot occupancy data. Finally, in both cases we also computed the time it would take the driver to walk from their parking spot to their original destination. We compared these time estimates for destinations in each block of Vancouver's downtown core and each hour of the day. We found many areas where off street would actually save drivers time over searching the streets for a spot, and many more where the time cost for parking off street was small. The identification of such areas provides an opportunity for the city to repurpose valuable curbside space for community-friendly uses more in line with its transportation goals.
Mission-Aware Spatio-Temporal Deep Learning Model for UAS Instantaneous Density Prediction
Venue: arXiv cs.CV 2020
Year: 2020

The number of daily sUAS operations in uncontrolled low altitude airspace is expected to reach into the millions in a few years. Therefore, UAS density prediction has become an emerging and challenging problem. In this paper, a deep learning-based UAS instantaneous density prediction model is presented. The model takes two types of data as input: 1) the historical density generated from the historical data, and 2) the future sUAS mission information. The architecture of our model contains four components: Historical Density Formulation module, UAS Mission Translation module, Mission Feature Extraction module, and Density Map Projection module. The training and testing data are generated by a python based simulator which is inspired by the multi-agent air traffic resource usage simulator (MATRUS) framework. The quality of prediction is measured by the correlation score and the Area Under the Receiver Operating Characteristics (AUROC) between the predicted value and simulated value. The experimental results demonstrate outstanding performance of the deep learning-based UAS density predictor. Compared to the baseline models, for simplified traffic scenario where no-fly zones and safe distance among sUASs are not considered, our model improves the prediction accuracy by more than 15.2% and its correlation score reaches 0.947. In a more realistic scenario, where the no-fly zone avoidance and the safe distance among sUASs are maintained using A* routing algorithm, our model can still achieve 0.823 correlation score. Meanwhile, the AUROC can reach 0.951 for the hot spot prediction.
Deep Synthetic Minority Over-Sampling Technique
Venue: arXiv cs.LG 2020
Year: 2020

Synthetic Minority Over-sampling Technique (SMOTE) is the most popular over-sampling method. However, its random nature makes the synthesized data and even imbalanced classification results unstable. It means that in case of running SMOTE n different times, n different synthesized in-stances are obtained with n different classification results. To address this problem, we adapt the SMOTE idea in deep learning architecture. In this method, a deep neural network regression model is used to train the inputs and outputs of traditional SMOTE. Inputs of the proposed deep regression model are two randomly chosen data points which are concatenated to form a double size vector. The outputs of this model are corresponding randomly interpolated data points between two randomly chosen vectors with original dimension. The experimental results show that, Deep SMOTE can outperform traditional SMOTE in terms of precision, F1 score and Area Under Curve (AUC) in majority of test cases.
Prior Knowledge Driven Label Embedding for Slot Filling in Natural Language Understanding
Venue: arXiv cs.CL 2020
Year: 2020

Traditional slot filling in natural language understanding (NLU) predicts a one-hot vector for each word. This form of label representation lacks semantic correlation modelling, which leads to severe data sparsity problem, especially when adapting an NLU model to a new domain. To address this issue, a novel label embedding based slot filling framework is proposed in this paper. Here, distributed label embedding is constructed for each slot using prior knowledge. Three encoding methods are investigated to incorporate different kinds of prior knowledge about slots: atomic concepts, slot descriptions, and slot exemplars. The proposed label embeddings tend to share text patterns and reuses data with different slot labels. This makes it useful for adaptive NLU with limited data. Also, since label embedding is independent of NLU model, it is compatible with almost all deep learning based slot filling models. The proposed approaches are evaluated on three datasets. Experiments on single domain and domain adaptation tasks show that label embedding achieves significant performance improvement over traditional one-hot label representation as well as advanced zero-shot approaches.
An Efficient Software-Hardware Design Framework for Spiking Neural Network Systems
Venue: arXiv cs.NE 2020
Year: 2020

Spiking Neural Network (SNN) is the third generation of Neural Network (NN) mimicking the natural behavior of the brain. By processing based on binary input/output, SNNs offer lower complexity, higher density and lower power consumption. This work presents an efficient software-hardware design framework for developing SNN systems in hardware. In addition, a design of low-cost neurosynaptic core is presented based on packet-switching communication approach. The evaluation results show that the ANN to SNN conversion method with the size 784:1200:1200:10 performs 99% accuracy for MNIST while the unsupervised STDP archives 89% with the size 784:400 with recurrent connections. The design of 256-neurons and 65k synapses is also implemented in ASIC 45nm technology with an area cost of 0.205 $m m^2$.
Monocular visual-inertial SLAM algorithm combined with wheel speed anomaly detection
Venue: arXiv cs.RO 2020
Year: 2020

To address the weak observability of monocular visual-inertial odometers on ground-based mobile robots, this paper proposes a monocular inertial SLAM algorithm combined with wheel speed anomaly detection. The algorithm uses a wheel speed odometer pre-integration method to add the wheel speed measurement to the least-squares problem in a tightly coupled manner. For abnormal motion situations, such as skidding and abduction, this paper adopts the Mecanum mobile chassis control method, based on torque control. This method uses the motion constraint error to estimate the reliability of the wheel speed measurement. At the same time, in order to prevent incorrect chassis speed measurements from negatively influencing robot pose estimation, this paper uses three methods to detect abnormal chassis movement and analyze chassis movement status in real time. When the chassis movement is determined to be abnormal, the wheel odometer pre-integration measurement of the current frame is removed from the state estimation equation, thereby ensuring the accuracy and robustness of the state estimation. Experimental results show that the accuracy and robustness of the method in this paper are better than those of a monocular visual-inertial odometer.
A Comprehensive Survey on Moving Networks
Venue: arXiv cs.NI 2020
Year: 2020

The unprecedented increase in the demand for mobile data, fuelled by new emerging applications such as HD video streaming and heightened online activities has caused massive strain on the existing cellular networks. As a solution, the 5G technology has been introduced to improve network performance through various innovative features such as mmWave spectrum and HetNets. In essence, HetNets include several small cells underlaid within macro-cell to serve densely populated regions. Recently, a mobile layer of HetNet has been under consideration by the researchers and is often referred to as moving networks. Moving networks comprise of mobile cells that are primarily introduced to improve QoS for commuting users inside public transport because the QoS is deteriorated due to vehicular penetration losses. Furthermore, the users inside fast moving public transport also exert excessive load on the core network due to large group handovers. To this end, mobile cells will play a crucial role in reducing overall handover count and will help in alleviating these problems by decoupling in-vehicle users from the core network. To date, remarkable research results have been achieved by the research community in addressing challenges linked to moving networks. However, to the best of our knowledge, a discussion on moving networks in a holistic way is missing in the current literature. To fill the gap, in this paper, we comprehensively survey moving networks. We cover the technological aspects and their applications in the futuristic applications. We also discuss the use-cases and value additions that moving networks may bring to future cellular architecture and identify the challenges associated with them. Based on the identified challenges we discuss the future research directions.
The Computational Complexity of Evil Hangman
Venue: arXiv cs.CC 2020
Year: 2020

The game of Hangman is a classical asymmetric two player game in which one player, the setter, chooses a secret word from a language, that the other player, the guesser, tries to discover through single letter matching queries, answered by all occurrences of this letter if any. In the Evil Hangman variant, the setter can change the secret word during the game, as long as the new choice is consistent with the information already given to the guesser. We show that a greedy strategy for Evil Hangman can perform arbitrarily far from optimal, and most importantly, that playing optimally as an Evil Hangman setter is computationally difficult. The latter result holds even assuming perfect knowledge of the language, for several classes of languages, ranging from Finite to Turing Computable. The proofs are based on reductions to Dominating Set on 3-regular graphs and to the Membership problem, combinatorial problems already known to be computationally hard.
Architectural Resilience to Foreground-and-Background Adversarial Noise
Venue: arXiv cs.CV 2020
Year: 2020

Adversarial attacks in the form of imperceptible perturbations of normal images have been extensively studied, and for every new defense methodology created, multiple adversarial attacks are found to counteract it. In particular, a popular style of attack, exemplified in recent years by DeepFool and Carlini-Wagner, relies solely on white-box scenarios in which full access to the predictive model and its weights are required. In this work, we instead propose distinct model-agnostic benchmark perturbations of images in order to investigate the resilience and robustness of different network architectures. Results empirically determine that increasing depth within most types of Convolutional Neural Networks typically improves model resilience towards general attacks, with improvement steadily decreasing as the model becomes deeper. Additionally, we find that a notable difference in adversarial robustness exists between residual architectures with skip connections and non-residual architectures of similar complexity. Our findings provide direction for future understanding of residual connections and depth on network robustness.
Absolute Shapley Value
Venue: arXiv cs.LG 2020
Year: 2020

Shapley value is a concept in cooperative game theory for measuring the contribution of each participant, which was named in honor of Lloyd Shapley. Shapley value has been recently applied in data marketplaces for compensation allocation based on their contribution to the models. Shapley value is the only value division scheme used for compensation allocation that meets three desirable criteria: group rationality, fairness, and additivity. In cooperative game theory, the marginal contribution of each contributor to each coalition is a nonnegative value. However, in machine learning model training, the marginal contribution of each contributor (data tuple) to each coalition (a set of data tuples) can be a negative value, i.e., the accuracy of the model trained by a dataset with an additional data tuple can be lower than the accuracy of the model trained by the dataset only. In this paper, we investigate the problem of how to handle the negative marginal contribution when computing Shapley value. We explore three philosophies: 1) taking the original value (Original Shapley Value); 2) taking the larger of the original value and zero (Zero Shapley Value); and 3) taking the absolute value of the original value (Absolute Shapley Value). Experiments on Iris dataset demonstrate that the definition of Absolute Shapley Value significantly outperforms the other two definitions in terms of evaluating data importance (the contribution of each data tuple to the trained model).