OpenRaiser/Intern-Atlas huggingface dataset:
On the Parallelization of Triangular Decomposition of Polynomial Systems
Venue: arXiv cs.SC 2019
Year: 2019

We discuss the parallelization of algorithms for solving polynomial systems symbolically by way of triangular decomposition. Algorithms for solving polynomial systems combine low-level routines for performing arithmetic operations on polynomials and high-level procedures which produce the different components (points, curves, surfaces) of the solution set. The latter "component-level" parallelization of triangular decompositions, our focus here, belongs to the class of dynamic irregular parallel applications. Possible speedup factors depend on geometrical properties of the solution set (number of components, their dimensions and degrees); these algorithms do not scale with the number of processors. In this paper we combine two different concurrency schemes, the fork-join model and producer-consumer patterns, to better capture opportunities for component-level parallelization. We report on our implementation with the publicly available BPAS library. Our experimentation with 340 systems yields promising results.
Training Detection-Range-Frugal Cooperative Collision Avoidance Models for Quadcopters via Neuroevolution
Venue: arXiv cs.NE 2019
Year: 2019

Cooperative autonomous approaches to avoiding collisions among small Unmanned Aerial Vehicles (UAVs) is central to safe integration of UAVs within the civilian airspace. One potential online cooperative approach is the concept of reciprocal actions, where both UAVs take pre-trained mutually coherent actions that do not require active online coordination (thereby avoiding the computational burden and risk associated with it). This paper presents a learning based approach to train such reciprocal maneuvers. Neuroevolution, which uses evolutionary algorithms to simultaneously optimize the topology and weights of neural networks, is used as the learning method -- which operates over a set of sample approach scenarios. Unlike most existing work (that minimize travel distance, energy or risk), the training process here focuses on the objective of minimizing the required detection range; this has important practical implications w.r.t. alleviating the dependency on sophisticated sensing and their reliability under various environments. A specialized design of experiments and line search is used to identify the minimum detection range for each sample scenarios. In order to allow an efficient training process, a classifier is used to discard actions (without simulating them) where the controller would fail. The model obtained via neuroevolution is observed to generalize well to (i.e., successful collision avoidance over) unseen approach scenarios.
Balancing spreads of influence in a social network
Venue: arXiv cs.SI 2019
Year: 2019

The personalization of our news consumption on social media has a tendency to reinforce our pre-existing beliefs instead of balancing our opinions. This finding is a concern for the health of our democracies which rely on an access to information providing diverse viewpoints. To tackle this issue from a computational perspective, Garimella et al. (NIPS'17) modeled the spread of these viewpoints, also called campaigns, using the well-known independent cascade model and studied an optimization problem that aims at balancing information exposure in a social network when two opposing campaigns propagate in the network. The objective in their $NP$-hard optimization problem is to maximize the number of people that are exposed to either both or none of the viewpoints. For two different settings, one corresponding to a model where campaigns spread in a correlated manner, and a second one, where the two campaigns spread in a heterogeneous manner, they provide constant ratio approximation algorithms. In this paper, we investigate a more general formulation of this problem. That is, we assume that $μ$ different campaigns propagate in a social network and we aim to maximize the number of people that are exposed to either $ν$ or none of the campaigns, where $μ\geν\ge2$. We provide dedicated approximation algorithms for both the correlated and heterogeneous settings. Interestingly, for the heterogeneous setting with $ν\ge 3$, we give a reduction leading to several approximation hardness results. Maybe most importantly, we obtain that the problem cannot be approximated within a factor of $n^{-g(n)}$ for any $g(n)=o(1)$ assuming Gap-ETH, denoting with $n$ the number of nodes in the social network. For $ν\ge 4$, there is no $n^{-ε}$-approximation algorithm if a certain class of one-way functions exists, where $ε> 0$ is a given constant which depends on $ν$.
Driver Behavior Analysis Using Lane Departure Detection Under Challenging Conditions
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we present a novel model to detect lane regions and extract lane departure events (changes and incursions) from challenging, lower-resolution videos recorded with mobile cameras. Our algorithm used a Mask-RCNN based lane detection model as pre-processor. Recently, deep learning-based models provide state-of-the-art technology for object detection combined with segmentation. Among the several deep learning architectures, convolutional neural networks (CNNs) outperformed other machine learning models, especially for region proposal and object detection tasks. Recent development in object detection has been driven by the success of region proposal methods and region-based CNNs (R-CNNs). Our algorithm utilizes lane segmentation mask for detection and Fix-lag Kalman filter for tracking, rather than the usual approach of detecting lane lines from single video frames. The algorithm permits detection of driver lane departures into left or right lanes from continuous lane detections. Preliminary results show promise for robust detection of lane departure events. The overall sensitivity for lane departure events on our custom test dataset is 81.81%.
Emotional Embeddings: Refining Word Embeddings to Capture Emotional Content of Words
Venue: arXiv cs.CL 2019
Year: 2019

Word embeddings are one of the most useful tools in any modern natural language processing expert's toolkit. They contain various types of information about each word which makes them the best way to represent the terms in any NLP task. But there are some types of information that cannot be learned by these models. Emotional information of words are one of those. In this paper, we present an approach to incorporate emotional information of words into these models. We accomplish this by adding a secondary training stage which uses an emotional lexicon and a psychological model of basic emotions. We show that fitting an emotional model into pre-trained word vectors can increase the performance of these models in emotional similarity metrics. Retrained models perform better than their original counterparts from 13% improvement for Word2Vec model, to 29% for GloVe vectors. This is the first such model presented in the literature, and although preliminary, these emotion sensitive models can open the way to increase performance in variety of emotion detection techniques.
Examining Structure of Word Embeddings with PCA
Venue: arXiv cs.CL 2019
Year: 2019

In this paper we compare structure of Czech word embeddings for English-Czech neural machine translation (NMT), word2vec and sentiment analysis. We show that although it is possible to successfully predict part of speech (POS) tags from word embeddings of word2vec and various translation models, not all of the embedding spaces show the same structure. The information about POS is present in word2vec embeddings, but the high degree of organization by POS in the NMT decoder suggests that this information is more important for machine translation and therefore the NMT model represents it in more direct way. Our method is based on correlation of principal component analysis (PCA) dimensions with categorical linguistic data. We also show that further examining histograms of classes along the principal component is important to understand the structure of representation of information in embeddings.
Decision-Making in Reinforcement Learning
Venue: arXiv cs.AI 2019
Year: 2019

In this research work, probabilistic decision-making approaches are studied, e.g. Bayesian and Boltzmann strategies, along with various deterministic exploration strategies, e.g. greedy, epsilon-Greedy and random approaches. In this research work, a comparative study has been done between probabilistic and deterministic decision-making approaches, the experiments are performed in OpenAI gym environment, solving Cart Pole problem. This research work discusses about the Bayesian approach to decision-making in deep reinforcement learning, and about dropout, how it can reduce the computational cost. All the exploration approaches are compared. It also discusses about the importance of exploration in deep reinforcement learning, and how improving exploration strategies may help in science and technology. This research work shows how probabilistic decision-making approaches are better in the long run as compared to the deterministic approaches. When there is uncertainty, Bayesian dropout approach proved to be better than all other approaches in this research work.
ArcticNet: A Deep Learning Solution to Classify Arctic Wetlands
Venue: arXiv cs.CV 2019
Year: 2019

Arctic environments are rapidly changing under the warming climate. Of particular interest are wetlands, a type of ecosystem that constitutes the most effective terrestrial long-term carbon store. As permafrost thaws, the carbon that was locked in these wetland soils for millennia becomes available for aerobic and anaerobic decomposition, which releases CO2 and CH4, respectively, back to the atmosphere.As CO2 and CH4 are potent greenhouse gases, this transfer of carbon from the land to the atmosphere further contributes to global warming, thereby increasing the rate of permafrost degradation in a positive feedback loop. Therefore, monitoring Arctic wetland health and dynamics is a key scientific task that is also of importance for policy. However, the identification and delineation of these important wetland ecosystems, remain incomplete and often inaccurate. Mapping the extent of Arctic wetlands remains a challenge for the scientific community. Conventional, coarser remote sensing methods are inadequate at distinguishing the diverse and micro-topographically complex non-vascular vegetation that characterize Arctic wetlands, presenting the need for better identification methods. To tackle this challenging problem, we constructed and annotated the first-of-its-kind Arctic Wetland Dataset (AWD). Based on that, we present ArcticNet, a deep neural network that exploits the multi-spectral, high-resolution imagery captured from nanosatellites (Planet Dove CubeSats) with additional DEM from the ArcticDEM project, to semantically label a Arctic study area into six types, in which three Arctic wetland functional types are included. We present multi-fold efforts to handle the arising challenges, including class imbalance, and the choice of fusion strategies. Preliminary results endorse the high promise of ArcticNet, achieving 93.12% in labelling a hold-out set of regions in our Arctic study area.
A Technique for Finding Optimal Program Launch Parameters Targeting Manycore Accelerators
Venue: arXiv cs.DC 2019
Year: 2019

In this paper, we present a new technique to dynamically determine the values of program parameters in order to optimize the performance of a multithreaded program P. To be precise, we describe a novel technique to statically build another program, say, R, that can dynamically determine the optimal values of program parameters to yield the best program performance for P given values for its data and hardware parameters. While this technique can be applied to parallel programs in general, we are particularly interested in programs targeting manycore accelerators. Our technique has successfully been employed for GPU kernels using the MWP-CWP performance model for CUDA.
Promotion of Answer Value Measurement with Domain Effects in Community Question Answering Systems
Venue: arXiv cs.CL 2019
Year: 2019

In the area of community question answering (CQA), answer selection and answer ranking are two tasks which are applied to help users quickly access valuable answers. Existing solutions mainly exploit the syntactic or semantic correlation between a question and its related answers (Q&A), where the multi-facet domain effects in CQA are still underexplored. In this paper, we propose a unified model, Enhanced Attentive Recurrent Neural Network (EARNN), for both answer selection and answer ranking tasks by taking full advantages of both Q&A semantics and multi-facet domain effects (i.e., topic effects and timeliness). Specifically, we develop a serialized LSTM to learn the unified representations of Q&A, where two attention mechanisms at either sentence-level or word-level are designed for capturing the deep effects of topics. Meanwhile, the emphasis of Q&A can be automatically distinguished. Furthermore, we design a time-sensitive ranking function to model the timeliness in CQA. To effectively train EARNN, a question-dependent pairwise learning strategy is also developed. Finally, we conduct extensive experiments on a real-world dataset from Quora. Experimental results validate the effectiveness and interpretability of our proposed EARNN model.
Patch Learning
Venue: arXiv cs.LG 2019
Year: 2019

There have been different strategies to improve the performance of a machine learning model, e.g., increasing the depth, width, and/or nonlinearity of the model, and using ensemble learning to aggregate multiple base/weak learners in parallel or in series. This paper proposes a novel strategy called patch learning (PL) for this problem. It consists of three steps: 1) train an initial global model using all training data; 2) identify from the initial global model the patches which contribute the most to the learning error, and train a (local) patch model for each such patch; and, 3) update the global model using training data that do not fall into any patch. To use a PL model, we first determine if the input falls into any patch. If yes, then the corresponding patch model is used to compute the output. Otherwise, the global model is used. We explain in detail how PL can be implemented using fuzzy systems. Five regression problems on 1D/2D/3D curve fitting, nonlinear system identification, and chaotic time-series prediction, verified its effectiveness. To our knowledge, the PL idea has not appeared in the literature before, and it opens up a promising new line of research in machine learning.
Enriching Ontology-based Data Access with Provenance (Extended Version)
Venue: arXiv cs.DB 2019
Year: 2019

Ontology-based data access (OBDA) is a popular paradigm for querying heterogeneous data sources by connecting them through mappings to an ontology. In OBDA, it is often difficult to reconstruct why a tuple occurs in the answer of a query. We address this challenge by enriching OBDA with provenance semirings, taking inspiration from database theory. In particular, we investigate the problems of (i) deciding whether a provenance annotated OBDA instance entails a provenance annotated conjunctive query, and (ii) computing a polynomial representing the provenance of a query entailed by a provenance annotated OBDA instance. Differently from pure databases, in our case these polynomials may be infinite. To regain finiteness, we consider idempotent semirings, and study the complexity in the case of DL-Lite ontologies. We implement Task (ii) in a state-of-the-art OBDA system and show the practical feasibility of the approach through an extensive evaluation against two popular benchmarks.
Closed-Form Analysis of Non-Linear Age-of-Information in Status Updates with an Energy Harvesting Transmitter
Venue: arXiv cs.IT 2019
Year: 2019

Timely status updates are crucial to enabling applications in massive Internet of Things (IoT). This paper measures the data-freshness performance of a status update system with an energy harvesting transmitter, considering the randomness in information generation, transmission and energy harvesting. The performance is evaluated by a non-linear function of age of information (AoI) that is defined as the time elapsed since the generation of the most up-to-date status information at the receiver. The system is formulated as two queues with status packet generation and energy arrivals both assumed to be Poisson processes. With negligible service time, both First-Come-First-Served (FCFS) and Last-Come-First-Served (LCFS) disciplines for arbitrary buffer and battery capacities are considered, and a method for calculating the average penalty with non-linear penalty functions is proposed. The average AoI, the average penalty under exponential penalty function, and AoI's threshold violation probability are obtained in closed form. When the service time is assumed to follow exponential distribution, matrix geometric method is used to obtain the average peak AoI. The results illustrate that under the FCFS discipline, the status update frequency needs to be carefully chosen according to the service rate and energy arrival rate in order to minimize the average penalty.
Probabilistic Top-k Dominating Query Monitoring over Multiple Uncertain IoT Data Streams in Edge Computing Environments
Venue: arXiv cs.DC 2019
Year: 2019

Extracting the valuable features and information in Big Data has become one of the important research issues in Data Science. In most Internet of Things (IoT) applications, the collected data are uncertain and imprecise due to sensor device variations or transmission errors. In addition, the sensing data may change as time evolves. We refer an uncertain data stream as a dataset that has velocity, veracity, and volume properties simultaneously. This paper employs the parallelism in edge computing environments to facilitate the top-k dominating query process over multiple uncertain IoT data streams. The challenges of this problem include how to quickly update the result for processing uncertainty and reduce the computation cost as well as provide highly accurate results. By referring to the related existing papers for certain data, we provide an effective probabilistic top-k dominating query process on uncertain data streams, which can be parallelized easily. After discussing the properties of the proposed approach, we validate our methods through the complexity analysis and extensive simulated experiments. In comparison with the existing works, the experimental results indicate that our method can improve almost 60% computation time, reduce nearly 20% communication cost between servers, and provide highly accurate results in most scenarios.
On the design of stabilizing cycles for switched linear systems
Venue: arXiv cs.SY 2019
Year: 2019

Given a family of systems, identifying stabilizing switching signals in terms of infinite walks constructed by concatenating cycles on the underlying directed graph of a switched system that satisfy certain conditions, is a well-known technique in the literature. This paper deals with a new {method to design} these cycles for stability of switched linear systems. We employ properties of the subsystem matrices and mild assumption on the admissible switches between the subsystems {for this purpose}. In contrast to prior works, {our construction of} stabilizing cycles does not involve design of Lyapunov-like functions and storage of sets of scalars in memory prior to the application of a cycle detection algorithm. As a result, {the} techniques {proposed in this paper} offer improved numerical tractability.
Adversarial Generation and Encoding of Nested Texts
Venue: arXiv cs.CL 2019
Year: 2019

In this paper we propose a new language model called AGENT, which stands for Adversarial Generation and Encoding of Nested Texts. AGENT is designed for encoding, generating and refining documents that consist of a long and coherent text, such as an entire book, provided they are hierarchically annotated (nested). i.e. divided into sentences, paragraphs and chapters. The core idea of our system is learning vector representations for each level of the text hierarchy (sentences, paragraphs, etc...), and train each such representation to perform 3 tasks: The task of reconstructing the sequence of vectors from a lower level that was used to create the representation, and generalized versions of the Masked Language Modeling (MLM) and "Next Sentence Prediction" tasks from BERT Devlin et al. [2018]. Additionally we present a new adversarial model for long text generation and suggest a way to improve the coherence of the generated text by traversing its vector representation tree.
COS960: A Chinese Word Similarity Dataset of 960 Word Pairs
Venue: arXiv cs.CL 2019
Year: 2019

Word similarity computation is a widely recognized task in the field of lexical semantics. Most proposed tasks test on similarity of word pairs of single morpheme, while few works focus on words of two morphemes or more morphemes. In this work, we propose COS960, a benchmark dataset with 960 pairs of Chinese wOrd Similarity, where all the words have two morphemes in three Part of Speech (POS) tags with their human annotated similarity rather than relatedness. We give a detailed description of dataset construction and annotation process, and test on a range of word embedding models. The dataset of this paper can be obtained from https://github.com/thunlp/COS960.
Parametric Shape Modeling and Skeleton Extraction with Radial Basis Functions using Similarity Domains Network
Venue: arXiv cs.CV 2019
Year: 2019

We demonstrate the use of similarity domains (SDs) for shape modeling and skeleton extraction. SDs are recently proposed and they can be utilized in a neural network framework to help us analyze shapes. SDs are modeled with radial basis functions with varying shape parameters in Similarity Domains Networks (SDNs). In this paper, we demonstrate how using SDN can first help us model a pixel-based image in terms of SDs and then demonstrate how those learned SDs can be used to extract the skeleton of a shape.
Hierarchical Video Frame Sequence Representation with Deep Convolutional Graph Network
Venue: arXiv cs.CV 2019
Year: 2019

High accuracy video label prediction (classification) models are attributed to large scale data. These data could be frame feature sequences extracted by a pre-trained convolutional-neural-network, which promote the efficiency for creating models. Unsupervised solutions such as feature average pooling, as a simple label-independent parameter-free based method, has limited ability to represent the video. While the supervised methods, like RNN, can greatly improve the recognition accuracy. However, the video length is usually long, and there are hierarchical relationships between frames across events in the video, the performance of RNN based models are decreased. In this paper, we proposes a novel video classification method based on a deep convolutional graph neural network(DCGN). The proposed method utilize the characteristics of the hierarchical structure of the video, and performed multi-level feature extraction on the video frame sequence through the graph network, obtained a video representation re ecting the event semantics hierarchically. We test our model on YouTube-8M Large-Scale Video Understanding dataset, and the result outperforms RNN based benchmarks.