OpenRaiser/Intern-Atlas huggingface dataset:
Learning based Methods for Code Runtime Complexity Prediction
Venue: arXiv cs.LG 2019
Year: 2019

Predicting the runtime complexity of a programming code is an arduous task. In fact, even for humans, it requires a subtle analysis and comprehensive knowledge of algorithms to predict time complexity with high fidelity, given any code. As per Turing's Halting problem proof, estimating code complexity is mathematically impossible. Nevertheless, an approximate solution to such a task can help developers to get real-time feedback for the efficiency of their code. In this work, we model this problem as a machine learning task and check its feasibility with thorough analysis. Due to the lack of any open source dataset for this task, we propose our own annotated dataset CoRCoD: Code Runtime Complexity Dataset, extracted from online judges. We establish baselines using two different approaches: feature engineering and code embeddings, to achieve state of the art results and compare their performances. Such solutions can be widely useful in potential applications like automatically grading coding assignments, IDE-integrated tools for static code analysis, and others.
NESSi: The Non-Equilibrium Systems Simulation package
Venue: arXiv cs.CE 2019
Year: 2019

The nonequilibrium dynamics of correlated many-particle systems is of interest in connection with pump-probe experiments on molecular systems and solids, as well as theoretical investigations of transport properties and relaxation processes. Nonequilibrium Green's functions are a powerful tool to study interaction effects in quantum many-particle systems out of equilibrium, and to extract physically relevant information for the interpretation of experiments. We present the open-source software package NESSi (The Non-Equilibrium Systems Simulation package) which allows to perform many-body dynamics simulations based on Green's functions on the L-shaped Kadanoff-Baym contour. NESSi contains the library libcntr which implements tools for basic operations on these nonequilibrium Green's functions, for constructing Feynman diagrams, and for the solution of integral and integro-differential equations involving contour Green's functions. The library employs a discretization of the Kadanoff-Baym contour into time $N$ points and a high-order implementation of integration routines. The total integrated error scales up to $\mathcal{O}(N^{-7})$, which is important since the numerical effort increases at least cubically with the simulation time. A distributed-memory parallelization over reciprocal space allows large-scale simulations of lattice systems. We provide a collection of example programs ranging from dynamics in simple two-level systems to problems relevant in contemporary condensed matter physics, including Hubbard clusters and Hubbard or Holstein lattice models. The libcntr library is the basis of a follow-up software package for nonequilibrium dynamical mean-field theory calculations based on strong-coupling perturbative impurity solvers.
Detect Toxic Content to Improve Online Conversations
Venue: arXiv cs.CL 2019
Year: 2019

Social media is filled with toxic content. The aim of this paper is to build a model that can detect insincere questions. We use the 'Quora Insincere Questions Classification' dataset for our analysis. The dataset is composed of sincere and insincere questions, with the majority of sincere questions. The dataset is processed and analyzed using Python and its libraries such as sklearn, numpy, pandas, keras etc. The dataset is converted to vector form using word embeddings such as GloVe, Wiki-news and TF-IDF. The imbalance in the dataset is handled by resampling techniques. We train and compare various machine learning and deep learning models to come up with the best results. Models discussed include SVM, Naive Bayes, GRU and LSTM.
Human-centric Metric for Accelerating Pathology Reports Annotation
Venue: arXiv cs.CL 2019
Year: 2019

Pathology reports contain useful information such as the main involved organ, diagnosis, etc. These information can be identified from the free text reports and used for large-scale statistical analysis or serve as annotation for other modalities such as pathology slides images. However, manual classification for a huge number of reports on multiple tasks is labor-intensive. In this paper, we have developed an automatic text classifier based on BERT and we propose a human-centric metric to evaluate the model. According to the model confidence, we identify low-confidence cases that require further expert annotation and high-confidence cases that are automatically classified. We report the percentage of low-confidence cases and the performance of automatically classified cases. On the high-confidence cases, the model achieves classification accuracy comparable to pathologists. This leads a potential of reducing 80% to 98% of the manual annotation workload.
A Holistic Natural Language Generation Framework for the Semantic Web
Venue: arXiv cs.CL 2019
Year: 2019

With the ever-growing generation of data for the Semantic Web comes an increasing demand for this data to be made available to non-semantic Web experts. One way of achieving this goal is to translate the languages of the Semantic Web into natural language. We present LD2NL, a framework for verbalizing the three key languages of the Semantic Web, i.e., RDF, OWL, and SPARQL. Our framework is based on a bottom-up approach to verbalization. We evaluated LD2NL in an open survey with 86 persons. Our results suggest that our framework can generate verbalizations that are close to natural languages and that can be easily understood by non-experts. Therewith, it enables non-domain experts to interpret Semantic Web data with more than 91\% of the accuracy of domain experts.
Mining Public Transit Ridership Flow and Origin-Destination Information from Wi-Fi and Bluetooth Sensing Data
Venue: arXiv cs.CY 2019
Year: 2019

Transit ridership flow and origin-destination (O-D) information is essential for enhancing transit network design, optimizing transit route and improving service. The effectiveness and preciseness of the traditional survey-based and smart card data-driven method for O-D information inference have multiple disadvantages due to the insufficient sample, the high time and energy cost, and the lack of inferring results validation. By considering the ubiquity of smart mobile devices in the world, several methods were developed for estimating the transit ridership flow from Wi-Fi and Bluetooth sensing data by filtering out the non-passenger MAC addresses based on the predefined thresholds. However, the accuracy of the filtering methods is still questionable for the indeterminate threshold values and the lack of quantitative results validation. By combining the consideration of the assumed overlapped feature space of passenger and non-passenger with the above concerns, a three steps data-driven method for estimating transit ridership flow and O-D information from Wi-Fi and Bluetooth sensing data is proposed in this paper. The observed ridership flow is used as ground truth for calculating the performance measurements. According to the results, the proposed approach outperformed all selected baseline models and existing filtering methods. The findings of this study can help to provide real-time and precise transit ridership flow and O-D information for supporting transit vehicle management and the quality of service enhancement.
Aerial Access and Backhaul in mmWave B5G Systems: Performance Dynamics and Optimization
Venue: arXiv cs.NI 2019
Year: 2019

The use of unmanned aerial vehicle (UAV)-based communication in millimeter-wave (mmWave) frequencies to provide on-demand radio access is a promising approach to improve capacity and coverage in beyond-5G (B5G) systems. There are several design aspects to be addressed when optimizing for the deployment of such UAV base stations. As traffic demand of mobile users varies across time and space, dynamic algorithms that correspondingly adjust the UAV locations are essential to maximize performance. In addition to careful tracking of spatio-temporal user/traffic activity, such optimization needs to account for realistic backhaul constraints. In this work, we first review the latest 3GPP activities behind integrated access and backhaul system design, support for UAV base stations, and mmWave radio relaying functionality. We then compare static and mobile UAV-based communication options under practical assumptions on the mmWave system layout, mobility and clusterization of users, antenna array geometry, and dynamic backhauling. We demonstrate that leveraging the UAV mobility to serve moving users may improve the overall system performance even in the presence of backhaul capacity limitations.
Real-time Funnel Generation for Restricted Motion Planning
Venue: arXiv cs.RO 2019
Year: 2019

In autonomous systems, a motion planner generates reference trajectories which are tracked by a low-level controller. For safe operation, the motion planner should account for inevitable controller tracking error when generating avoidance trajectories. In this article we present a method for generating provably safe tracking error bounds, while reducing over-conservatism that exists in existing methods. We achieve this goal by restricting possible behaviors for the motion planner. We provide an algebraic method based on sum-of-squares programming to define restrictions on the motion planner and find small bounds on the tracking error. We demonstrate our method on two case studies and show how we can integrate the method into already developed motion planning techniques. Results suggest that our method can provide acceptable tracking error wherein previous work were not applicable.
Improving Bidirectional Decoding with Dynamic Target Semantics in Neural Machine Translation
Venue: arXiv cs.CL 2019
Year: 2019

Generally, Neural Machine Translation models generate target words in a left-to-right (L2R) manner and fail to exploit any future (right) semantics information, which usually produces an unbalanced translation. Recent works attempt to utilize the right-to-left (R2L) decoder in bidirectional decoding to alleviate this problem. In this paper, we propose a novel \textbf{D}ynamic \textbf{I}nteraction \textbf{M}odule (\textbf{DIM}) to dynamically exploit target semantics from R2L translation for enhancing the L2R translation quality. Different from other bidirectional decoding approaches, DIM firstly extracts helpful target information through addressing and reading operations, then updates target semantics for tracking the interactive history. Additionally, we further introduce an \textbf{agreement regularization} term into the training objective to narrow the gap between L2R and R2L translations. Experimental results on NIST Chinese$\Rightarrow$English and WMT'16 English$\Rightarrow$Romanian translation tasks show that our system achieves significant improvements over baseline systems, which also reaches comparable results compared to the state-of-the-art Transformer model with much fewer parameters of it.
Knowing What, How and Why: A Near Complete Solution for Aspect-based Sentiment Analysis
Venue: arXiv cs.CL 2019
Year: 2019

Target-based sentiment analysis or aspect-based sentiment analysis (ABSA) refers to addressing various sentiment analysis tasks at a fine-grained level, which includes but is not limited to aspect extraction, aspect sentiment classification, and opinion extraction. There exist many solvers of the above individual subtasks or a combination of two subtasks, and they can work together to tell a complete story, i.e. the discussed aspect, the sentiment on it, and the cause of the sentiment. However, no previous ABSA research tried to provide a complete solution in one shot. In this paper, we introduce a new subtask under ABSA, named aspect sentiment triplet extraction (ASTE). Particularly, a solver of this task needs to extract triplets (What, How, Why) from the inputs, which show WHAT the targeted aspects are, HOW their sentiment polarities are and WHY they have such polarities (i.e. opinion reasons). For instance, one triplet from "Waiters are very friendly and the pasta is simply average" could be ('Waiters', positive, 'friendly'). We propose a two-stage framework to address this task. The first stage predicts what, how and why in a unified model, and then the second stage pairs up the predicted what (how) and why from the first stage to output triplets. In the experiments, our framework has set a benchmark performance in this novel triplet extraction task. Meanwhile, it outperforms a few strong baselines adapted from state-of-the-art related methods.
A Wait-Free Universal Construct for Large Objects
Venue: arXiv cs.DC 2019
Year: 2019

Concurrency has been a subject of study for more than 50 years. Still, many developers struggle to adapt their sequential code to be accessed concurrently. This need has pushed for generic solutions and specific concurrent data structures. Wait-free universal constructs are attractive as they can turn a sequential implementation of any object into an equivalent, yet concurrent and wait-free, implementation. While highly relevant from a research perspective, these techniques are of limited practical use when the underlying object or data structure is sizable. The copy operation can consume much of the CPU's resources and significantly degrade performance. To overcome this limitation, we have designed CX, a multi-instance-based wait-free universal construct that substantially reduces the amount of copy operations. The construct maintains a bounded number of instances of the object that can potentially be brought up to date. We applied CX to several sequential implementations of data structures, including STL implementations, and compared them with existing wait-free constructs. Our evaluation shows that CX performs significantly better in most experiments, and can even rival with hand-written lock-free and wait-free data structures, simultaneously providing wait-free progress, safe memory reclamation and high reader scalability.
Apprenticeship Learning via Frank-Wolfe
Venue: arXiv cs.LG 2019
Year: 2019

We consider the applications of the Frank-Wolfe (FW) algorithm for Apprenticeship Learning (AL). In this setting, we are given a Markov Decision Process (MDP) without an explicit reward function. Instead, we observe an expert that acts according to some policy, and the goal is to find a policy whose feature expectations are closest to those of the expert policy. We formulate this problem as finding the projection of the feature expectations of the expert on the feature expectations polytope -- the convex hull of the feature expectations of all the deterministic policies in the MDP. We show that this formulation is equivalent to the AL objective and that solving this problem using the FW algorithm is equivalent well-known Projection method of Abbeel and Ng (2004). This insight allows us to analyze AL with tools from convex optimization literature and derive tighter convergence bounds on AL. Specifically, we show that a variation of the FW method that is based on taking "away steps" achieves a linear rate of convergence when applied to AL and that a stochastic version of the FW algorithm can be used to avoid precise estimation of feature expectations. We also experimentally show that this version outperforms the FW baseline. To the best of our knowledge, this is the first work that shows linear convergence rates for AL.
One Pixel Image and RF Signal Based Split Learning for mmWave Received Power Prediction
Venue: arXiv cs.NI 2019
Year: 2019

Focusing on the received power prediction of millimeter-wave (mmWave) radio-frequency (RF) signals, we propose a multimodal split learning (SL) framework that integrates RF received signal powers and depth-images observed by physically separated entities. To improve its communication efficiency while preserving data privacy, we propose an SL neural network architecture that compresses the communication payload, i.e., images. Compared to a baseline solely utilizing RF signals, numerical results show that SL integrating only one pixel image with RF signals achieves higher prediction accuracy while maximizing both communication efficiency and privacy guarantees.
Dynamic HARQ with Guaranteed Delay
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, a dynamic-hybrid automatic repeat request (D-HARQ) scheme with guaranteed delay performance is proposed. As opposed to the conventional HARQ that the maximum number of re-transmissions, L, is fixed, in the proposed scheme packets can be retransmitted more times given that the previous packet was received with less than L re-transmissions. The dynamic of the proposed scheme is analyzed using the Markov model. For delay-sensitive applications, the proposed scheme shows superior performance in terms of packet error rate compared with the conventional HARQ and Fixed re-transmission schemes when the channel state information is not available at the transmitter. We further show that D-HARQ achieves a higher throughput compared with the conventional HARQ and fixed re-transmission schemes under the same reliability constraint.
Reversible Data Hiding in Encrypted Images based on Pixel Prediction and Bit-plane Compression
Venue: arXiv cs.MM 2019
Year: 2019

Reversible data hiding in encrypted images (RDHEI) receives growing attention because it protects the content of the original image while the embedded data can be accurately extracted and the original image can be reconstructed lossless. To make full use of the correlation of the adjacent pixels, this paper proposes an RDHEI scheme based on pixel prediction and bit-plane compression. Firstly, to vacate room for data embedding, the prediction error of the original image is calculated and used for bit-plane rearrangement and compression. Then, the image after vacating room is encrypted by a stream cipher. Finally, the additional data is embedded in the vacated room by multi-LSB substitution. Experimental results show that the embedding capacity of the proposed method outperforms the state-of-the-art methods.
Packing Trees into 1-planar Graphs
Venue: arXiv cs.CG 2019
Year: 2019

We introduce and study the 1-planar packing problem: Given $k$ graphs with $n$ vertices $G_1, \dots, G_k$, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each $G_i$ is a tree and $k=3$. We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1-planar packing, while two paths and a special type of caterpillar always have one. We then study 1-planar packings with few crossings and prove that three paths (resp. cycles) admit a 1-planar packing with at most seven (resp. fourteen) crossings. We finally show that a quadruple consisting of three paths and a perfect matching with $n \geq 12$ vertices admits a 1-planar packing, while such a packing does not exist if $n \leq 10$.
Downsampling and Transparent Coding for Blockchain
Venue: arXiv cs.CR 2019
Year: 2019

With the development of blockchain, the huge history data limits the scalability of the blockchain. This paper proposes to downsample these data to reduce the storage overhead of nodes. These nodes keep good independency, if downsampling follows the entropy of blockchain. Moreover, it demonstrates that the entire blockchain history can be efficiently recovered through the cooperative decoding of a group of nodes like fountain codes, if reserved data over these nodes obey the soliton distribution. However, these data on nodes are uncoded (transparent). Thus, the proposed algorithm not only keeps decentralization and security, but also has good scalability in independency and recovery.
Quinoa: a Q-function You Infer Normalized Over Actions
Venue: arXiv cs.LG 2019
Year: 2019

We present an algorithm for learning an approximate action-value soft Q-function in the relative entropy regularised reinforcement learning setting, for which an optimal improved policy can be recovered in closed form. We use recent advances in normalising flows for parametrising the policy together with a learned value-function; and show how this combination can be used to implicitly represent Q-values of an arbitrary policy in continuous action space. Using simple temporal difference learning on the Q-values then leads to a unified objective for policy and value learning. We show how this approach considerably simplifies standard Actor-Critic off-policy algorithms, removing the need for a policy optimisation step. We perform experiments on a range of established reinforcement learning benchmarks, demonstrating that our approach allows for complex, multimodal policy distributions in continuous action spaces, while keeping the process of sampling from the policy both fast and exact.
A Model for Spatial Outlier Detection Based on Weighted Neighborhood Relationship
Venue: arXiv cs.LG 2019
Year: 2019

Spatial outliers are used to discover inconsistent objects producing implicit, hidden, and interesting knowledge, which has an effective role in decision-making process. In this paper, we propose a model to redefine the spatial neighborhood relationship by considering weights of the most effective parameters of neighboring objects in a given spatial data set. The spatial parameters, which are taken into our consideration, are distance, cost, and number of direct connections between neighboring objects. This model is adaptable to be applied on polygonal objects. The proposed model is applied to a GIS system supporting literacy project in Fayoum governorate.
DLA: Dense-Layer-Analysis for Adversarial Example Detection
Venue: arXiv cs.CR 2019
Year: 2019

In recent years Deep Neural Networks (DNNs) have achieved remarkable results and even showed super-human capabilities in a broad range of domains. This led people to trust in DNNs' classifications and resulting actions even in security-sensitive environments like autonomous driving. Despite their impressive achievements, DNNs are known to be vulnerable to adversarial examples. Such inputs contain small perturbations to intentionally fool the attacked model. In this paper, we present a novel end-to-end framework to detect such attacks during classification without influencing the target model's performance. Inspired by recent research in neuron-coverage guided testing we show that dense layers of DNNs carry security-sensitive information. With a secondary DNN we analyze the activation patterns of the dense layers during classification runtime, which enables effective and real-time detection of adversarial examples. Our prototype implementation successfully detects adversarial examples in image, natural language, and audio processing. Thereby, we cover a variety of target DNNs, including Long Short Term Memory (LSTM) architectures. In addition, to effectively defend against state-of-the-art attacks, our approach generalizes between different sets of adversarial examples. Thus, our method most likely enables us to detect even future, yet unknown attacks. Finally, during white-box adaptive attacks, we show our method cannot be easily bypassed.