OpenRaiser/Intern-Atlas huggingface dataset:
Simulate forest trees by integrating L-system and 3D CAD files
Venue: arXiv cs.RO 2020
Year: 2020

In this article, we propose a new approach for simulating trees, including their branches, sub-branches, and leaves. This approach combines the theory of biological development, mathematical models, and computer graphics, producing simulated trees and forest with full geometry. Specifically, we adopt the Lindenmayer process to simulate the branching pattern of trees and modify the available measurements and dimensions of 3D CAD developed object files to create natural looking sub-branches and leaves. Randomization has been added to the placement of all branches, sub branches and leaves. To simulate a forest, we adopt Inhomogeneous Poisson process to generate random locations of trees. Our approach can be used to create complex structured 3D virtual environment for the purpose of testing new sensors and training robotic algorithms. We look forward to applying this approach to test biosonar sensors that mimick bats' fly in the simulated environment.
On the Pilot Contamination Attack in Multi-Cell Multiuser Massive MIMO Networks
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we analyze pilot contamination (PC) attacks on a multi-cell massive multiple-input multiple-output (MIMO) network with correlated pilots. We obtain correlated pilots using a user capacity-achieving pilot sequence design. This design relies on an algorithm which designs correlated pilot sequences based on signal-to-interference-plus-noise ratio (SINR) requirements for all the legitimate users. The pilot design is capable of achieving the SINR requirements for all users even in the presence of PC. However, this design has some intrinsic limitations and vulnerabilities, such as a known pilot sequence and the non-zero cross-correlation among different pilot sequences. We reveal that such vulnerabilities may be exploited by an active attacker to increase PC in the network. Motivated by this, we analyze the correlated pilot design for vulnerabilities that can be exploited by an active attacker. Based on this analysis, we develop an effective active attack strategy in the massive MIMO network with correlated pilot sequences. Our examinations reveal that the user capacity region of the network is significantly reduced in the presence of the active attack. Importantly, the SINR requirements for the worst-affected users may not be satisfied even with an infinite number of antennas at the base station.
Dynamic Radar Network of UAVs: A Joint Navigation and Tracking Approach
Venue: arXiv cs.IT 2020
Year: 2020

Nowadays there is a growing research interest on the possibility of enriching small flying robots with autonomous sensing and online navigation capabilities. This will enable a large number of applications spanning from remote surveillance to logistics, smarter cities and emergency aid in hazardous environments. In this context, an emerging problem is to track unauthorized small unmanned aerial vehicles (UAVs) hiding behind buildings or concealing in large UAV networks. In contrast with current solutions mainly based on static and on-ground radars, this paper proposes the idea of a dynamic radar network of UAVs for real-time and high-accuracy tracking of malicious targets. To this end, we describe a solution for real-time navigation of UAVs to track a dynamic target using heterogeneously sensed information. Such information is shared by the UAVs with their neighbors via multi-hops, allowing tracking the target by a local Bayesian estimator running at each agent. Since not all the paths are equal in terms of information gathering point-of-view, the UAVs plan their own trajectory by minimizing the posterior covariance matrix of the target state under UAV kinematic and anti-collision constraints. Our results show how a dynamic network of radars attains better localization results compared to a fixed configuration and how the on-board sensor technology impacts the accuracy in tracking a target with different radar cross sections, especially in non line-of-sight (NLOS) situations.
Bi-Decoder Augmented Network for Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

Neural Machine Translation (NMT) has become a popular technology in recent years, and the encoder-decoder framework is the mainstream among all the methods. It's obvious that the quality of the semantic representations from encoding is very crucial and can significantly affect the performance of the model. However, existing unidirectional source-to-target architectures may hardly produce a language-independent representation of the text because they rely heavily on the specific relations of the given language pairs. To alleviate this problem, in this paper, we propose a novel Bi-Decoder Augmented Network (BiDAN) for the neural machine translation task. Besides the original decoder which generates the target language sequence, we add an auxiliary decoder to generate back the source language sequence at the training time. Since each decoder transforms the representations of the input text into its corresponding language, jointly training with two target ends can make the shared encoder has the potential to produce a language-independent semantic space. We conduct extensive experiments on several NMT benchmark datasets and the results demonstrate the effectiveness of our proposed approach.
Second-Order Asymptotics of Sequential Hypothesis Testing
Venue: arXiv cs.IT 2020
Year: 2020

We consider the classical sequential binary hypothesis testing problem in which there are two hypotheses governed respectively by distributions $P_0$ and $P_1$ and we would like to decide which hypothesis is true using a sequential test. It is known from the work of Wald and Wolfowitz that as the expectation of the length of the test grows, the optimal type-I and type-II error exponents approach the relative entropies $D(P_1\|P_0)$ and $D(P_0\|P_1)$. We refine this result by considering the optimal backoff---or second-order asymptotics---from the corner point of the achievable exponent region $(D(P_1\|P_0),D(P_0\|P_1))$ under two different constraints on the length of the test (or the sample size). First, we consider a probabilistic constraint in which the probability that the length of test exceeds a prescribed integer $n$ is less than a certain threshold $0<\varepsilon <1$. Second, the expectation of the sample size is bounded by $n$. In both cases, and under mild conditions, the second-order asymptotics is characterized exactly. Numerical examples are provided to illustrate our results.
A Feature-Driven Approach for Identifying Pathogenic Social Media Accounts
Venue: arXiv cs.SI 2020
Year: 2020

Over the past few years, we have observed different media outlets' attempts to shift public opinion by framing information to support a narrative that facilitate their goals. Malicious users referred to as "pathogenic social media" (PSM) accounts are more likely to amplify this phenomena by spreading misinformation to viral proportions. Understanding the spread of misinformation from account-level perspective is thus a pressing problem. In this work, we aim to present a feature-driven approach to detect PSM accounts in social media. Inspired by the literature, we set out to assess PSMs from three broad perspectives: (1) user-related information (e.g., user activity, profile characteristics), (2) source-related information (i.e., information linked via URLs shared by users) and (3) content-related information (e.g., tweets characteristics). For the user-related information, we investigate malicious signals using causality analysis (i.e., if user is frequently a cause of viral cascades) and profile characteristics (e.g., number of followers, etc.). For the source-related information, we explore various malicious properties linked to URLs (e.g., URL address, content of the associated website, etc.). Finally, for the content-related information, we examine attributes (e.g., number of hashtags, suspicious hashtags, etc.) from tweets posted by users. Experiments on real-world Twitter data from different countries demonstrate the effectiveness of the proposed approach in identifying PSM users.
Unsupervised Domain Adaptation for Mobile Semantic Segmentation based on Cycle Consistency and Feature Alignment
Venue: arXiv cs.CV 2020
Year: 2020

The supervised training of deep networks for semantic segmentation requires a huge amount of labeled real world data. To solve this issue, a commonly exploited workaround is to use synthetic data for training, but deep networks show a critical performance drop when analyzing data with slightly different statistical properties with respect to the training set. In this work, we propose a novel Unsupervised Domain Adaptation (UDA) strategy to address the domain shift issue between real world and synthetic representations. An adversarial model, based on the cycle consistency framework, performs the mapping between the synthetic and real domain. The data is then fed to a MobileNet-v2 architecture that performs the semantic segmentation task. An additional couple of discriminators, working at the feature level of the MobileNet-v2, allows to better align the features of the two domain distributions and to further improve the performance. Finally, the consistency of the semantic maps is exploited. After an initial supervised training on synthetic data, the whole UDA architecture is trained end-to-end considering all its components at once. Experimental results show how the proposed strategy is able to obtain impressive performance in adapting a segmentation network trained on synthetic data to real world scenarios. The usage of the lightweight MobileNet-v2 architecture allows its deployment on devices with limited computational resources as the ones employed in autonomous vehicles.
Wasserstein Distributionally Robust Motion Control for Collision Avoidance Using Conditional Value-at-Risk
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, a risk-aware motion control scheme is considered for mobile robots to avoid randomly moving obstacles when the true probability distribution of uncertainty is unknown. We propose a novel model predictive control (MPC) method for limiting the risk of unsafety even when the true distribution of the obstacles' movements deviates, within an ambiguity set, from the empirical distribution obtained using a limited amount of sample data. By choosing the ambiguity set as a statistical ball with its radius measured by the Wasserstein metric, we achieve a probabilistic guarantee of the out-of-sample risk, evaluated using new sample data generated independently of the training data. To resolve the infinite-dimensionality issue inherent in the distributionally robust MPC problem, we reformulate it as a finite-dimensional nonlinear program using modern distributionally robust optimization techniques based on the Kantorovich duality principle. To find a globally optimal solution in the case of affine dynamics and output equations, a spatial branch-and-bound algorithm is designed using McCormick relaxation. The performance of the proposed method is demonstrated and analyzed through simulation studies using a nonlinear car-like vehicle model and a linearized quadrotor model.
Fine-grained Image Classification and Retrieval by Combining Visual and Locally Pooled Textual Features
Venue: arXiv cs.CV 2020
Year: 2020

Text contained in an image carries high-level semantics that can be exploited to achieve richer image understanding. In particular, the mere presence of text provides strong guiding content that should be employed to tackle a diversity of computer vision tasks such as image retrieval, fine-grained classification, and visual question answering. In this paper, we address the problem of fine-grained classification and image retrieval by leveraging textual information along with visual cues to comprehend the existing intrinsic relation between the two modalities. The novelty of the proposed model consists of the usage of a PHOC descriptor to construct a bag of textual words along with a Fisher Vector Encoding that captures the morphology of text. This approach provides a stronger multimodal representation for this task and as our experiments demonstrate, it achieves state-of-the-art results on two different tasks, fine-grained classification and image retrieval.
On Equivalence and Cores for Incomplete Databases in Open and Closed Worlds
Venue: arXiv cs.DB 2020
Year: 2020

Data exchange heavily relies on the notion of incomplete database instances. Several semantics for such instances have been proposed and include open (OWA), closed (CWA), and open-closed (OCWA) world. For all these semantics important questions are: whether one incomplete instance semantically implies another; when two are semantically equivalent; and whether a smaller or smallest semantically equivalent instance exists. For OWA and CWA these questions are fully answered. For several variants of OCWA, however, they remain open. In this work we adress these questions for Closed Powerset semantics and the OCWA semantics of Libkin and Sirangelo, 2011. We define a new OCWA semantics, called OCWA*, in terms of homomorphic covers that subsumes both semantics, and characterize semantic implication and equivalence in terms of such covers. This characterization yields a guess-and-check algorithm to decide equivalence, and shows that the problem is NP-complete. For the minimization problem we show that for several common notions of minimality there is in general no unique minimal equivalent instance for Closed Powerset semantics, and consequently not for the more expressive OCWA* either. However, for Closed Powerset semantics we show that one can find, for any incomplete database, a unique finite set of its subinstances which are subinstances (up to renaming of nulls) of all instances semantically equivalent to the original incomplete one. We study properties of this set, and extend the analysis to OCWA*.
Simulation computation in grammar-compressed graphs
Venue: arXiv cs.DS 2020
Year: 2020

Like [1], we present an algorithm to compute the simulation of a query pattern in a graph of labeled nodes and unlabeled edges. However, our algorithm works on a compressed graph grammar, instead of on the original graph. The speed-up of our algorithm compared to the algorithm in [1] grows with the size of the graph and with the compression strength.
Distributed Learning in the Non-Convex World: From Batch to Streaming Data, and Beyond
Venue: arXiv cs.LG 2020
Year: 2020

Distributed learning has become a critical enabler of the massively connected world envisioned by many. This article discusses four key elements of scalable distributed processing and real-time intelligence --- problems, data, communication and computation. Our aim is to provide a fresh and unique perspective about how these elements should work together in an effective and coherent manner. In particular, we {provide a selective review} about the recent techniques developed for optimizing non-convex models (i.e., problem classes), processing batch and streaming data (i.e., data types), over the networks in a distributed manner (i.e., communication and computation paradigm). We describe the intuitions and connections behind a core set of popular distributed algorithms, emphasizing how to trade off between computation and communication costs. Practical issues and future research directions will also be discussed.
TableQnA: Answering List Intent Queries With Web Tables
Venue: arXiv cs.IR 2020
Year: 2020

The web contains a vast corpus of HTML tables. They can be used to provide direct answers to many web queries. We focus on answering two classes of queries with those tables: those seeking lists of entities (e.g., `cities in california') and those seeking superlative entities (e.g., `largest city in california'). The main challenge is to achieve high precision with significant coverage. Existing approaches train machine learning models to select the answer from the candidates; they rely on textual match features between the query and the content of the table along with features capturing table quality/importance. These features alone are inadequate for achieving the above goals. Our main insight is that we can improve precision by (i) first extracting intent (structured information) from the query for the above query classes and (ii) then performing structure-aware matching (instead of just textual matching) between the extracted intent and the candidates to select the answer. We model (i) as a sequence tagging task. We leverage state-of-the-art deep neural network models with word embeddings. The model requires large scale training data which is expensive to obtain via manual labeling; we therefore develop a novel method to automatically generate the training data. For (ii), we develop novel features to compute structure-aware match and train a machine learning model. Our experiments on real-life web search queries show that (i) our intent extractor for list and superlative intent queries has significantly higher precision and coverage compared with baseline approaches and (ii) our table answer selector significantly outperforms the state-of-the-art baseline approach. This technology has been used in production by Microsoft's Bing search engine since 2016.
Domain Adaption for Knowledge Tracing
Venue: arXiv cs.LG 2020
Year: 2020

With the rapid development of online education system, knowledge tracing which aims at predicting students' knowledge state is becoming a critical and fundamental task in personalized education. Traditionally, existing methods are domain-specified. However, there are a larger number of domains (e.g., subjects, schools) in the real world and the lacking of data in some domains, how to utilize the knowledge and information in other domains to help train a knowledge tracing model for target domains is increasingly important. We refer to this problem as domain adaptation for knowledge tracing (DAKT) which contains two aspects: (1) how to achieve great knowledge tracing performance in each domain. (2) how to transfer good performed knowledge tracing model between domains. To this end, in this paper, we propose a novel adaptable framework, namely adaptable knowledge tracing (AKT) to address the DAKT problem. Specifically, for the first aspect, we incorporate the educational characteristics (e.g., slip, guess, question texts) based on the deep knowledge tracing (DKT) to obtain a good performed knowledge tracing model. For the second aspect, we propose and adopt three domain adaptation processes. First, we pre-train an auto-encoder to select useful source instances for target model training. Second, we minimize the domain-specific knowledge state distribution discrepancy under maximum mean discrepancy (MMD) measurement to achieve domain adaptation. Third, we adopt fine-tuning to deal with the problem that the output dimension of source and target domain are different to make the model suitable for target domains. Extensive experimental results on two private datasets and seven public datasets clearly prove the effectiveness of AKT for great knowledge tracing performance and its superior transferable ability.
On the Convex Behavior of Deep Neural Networks in Relation to the Layers' Width
Venue: arXiv cs.LG 2020
Year: 2020

The Hessian of neural networks can be decomposed into a sum of two matrices: (i) the positive semidefinite generalized Gauss-Newton matrix G, and (ii) the matrix H containing negative eigenvalues. We observe that for wider networks, minimizing the loss with the gradient descent optimization maneuvers through surfaces of positive curvatures at the start and end of training, and close to zero curvatures in between. In other words, it seems that during crucial parts of the training process, the Hessian in wide networks is dominated by the component G. To explain this phenomenon, we show that when initialized using common methodologies, the gradients of over-parameterized networks are approximately orthogonal to H, such that the curvature of the loss surface is strictly positive in the direction of the gradient.
A Game-Theoretic Approach to a Task Delegation Problem
Venue: arXiv cs.GT 2020
Year: 2020

We study a setting in which a principal selects an agent to execute a collection of tasks according to a specified priority sequence. Agents, however, have their own individual priority sequences according to which they wish to execute the tasks. There is information asymmetry since each priority sequence is private knowledge for the individual agent. We design a mechanism for selecting the agent and incentivizing the selected agent to realize a priority sequence for executing the tasks that achieves socially optimal performance. Our proposed mechanism consists of two parts. First, the principal runs an auction to select an agent to allocate tasks to with minimum declared priority sequence misalignment. Then, the principal rewards the agent according to the realized priority sequence with which the tasks were performed. We show that the proposed mechanism is individually rational and incentive compatible. Further, it is also socially optimal for the case of linear cost of priority sequence modification for the agents.
EGGS: A Flexible Approach to Relational Modeling of Social Network Spam
Venue: arXiv cs.SI 2020
Year: 2020

Social networking websites face a constant barrage of spam, unwanted messages that distract, annoy, and even defraud honest users. These messages tend to be very short, making them difficult to identify in isolation. Furthermore, spammers disguise their messages to look legitimate, tricking users into clicking on links and tricking spam filters into tolerating their malicious behavior. Thus, some spam filters examine relational structure in the domain, such as connections among users and messages, to better identify deceptive content. However, even when it is used, relational structure is often exploited in an incomplete or ad hoc manner. In this paper, we present Extended Group-based Graphical models for Spam (EGGS), a general-purpose method for classifying spam in online social networks. Rather than labeling each message independently, we group related messages together when they have the same author, the same content, or other domain-specific connections. To reason about related messages, we combine two popular methods: stacked graphical learning (SGL) and probabilistic graphical models (PGM). Both methods capture the idea that messages are more likely to be spammy when related messages are also spammy, but they do so in different ways; SGL uses sequential classifier predictions and PGMs use probabilistic inference. We apply our method to four different social network domains. EGGS is more accurate than an independent model in most experimental settings, especially when the correct label is uncertain. For the PGM implementation, we compare Markov logic networks to probabilistic soft logic and find that both work well with neither one dominating, and the combination of SGL and PGMs usually performs better than either on its own.