OpenRaiser/Intern-Atlas huggingface dataset:
System Performance with varying L1 Instruction and Data Cache Sizes: An Empirical Analysis
Venue: arXiv cs.PF 2019
Year: 2019

In this project, we investigate the fluctuations in performance caused by changing the Instruction (I-cache) size and the Data (D-cache) size in the L1 cache. We employ the Gem5 framework to simulate a system with varying specifications on a single host machine. We utilize the FreqMine benchmark available under the PARSEC suite as the workload program to benchmark our simulated system. The Out-order CPU (O3) with Ruby memory model was simulated in a Full-System X86 environment with Linux OS. The chosen metrics deal with Hit Rate, Misses, Memory Latency, Instruction Rate, and Bus Traffic within the system. Performance observed by varying L1 size within a certain range of values was used to compute Confidence Interval based statistics for relevant metrics. Our expectations, corresponding experimental observations, and discrepancies are also discussed in this report.
Methods for Predicting Behavior of Elephant Flows in Data Center Networks
Venue: arXiv cs.NI 2019
Year: 2019

Several Traffic Engineering (TE) techniques based on SDN (Software-defined networking) proposed to resolve flow competitions for network resources. However, there is no comprehensive study on the probability distribution of their throughput. Moreover, there is no study on predicting the future of elephant flows. To address these issues, we propose a new stochastic performance evaluation model to estimate the loss rate of two state-of-art flow scheduling algorithms including Equalcost multi-path routing (ECMP), Hedera besides a flow congestion control algorithm which is Data Center TCP (DCTCP). Although these algorithms have theoretical and practical benefits, their effectiveness has not been statistically investigated and analyzed in conserving the elephant flows. Therefore, we conducted extensive experiments on the fat-tree data center network to examine the efficiency of the algorithms under different network circumstances based on Monte Carlo risk analysis. The results show that Hedera is still risky to be used to handle the elephant flows due to its unstable throughput achieved under stochastic network congestion. On the other hand, DCTCP found suffering under high load scenarios. These outcomes might apply to all data center applications, in particular, the applications that demand high stability and productivity.
The problem with DDPG: understanding failures in deterministic environments with sparse rewards
Venue: arXiv cs.LG 2019
Year: 2019

In environments with continuous state and action spaces, state-of-the-art actor-critic reinforcement learning algorithms can solve very complex problems, yet can also fail in environments that seem trivial, but the reason for such failures is still poorly understood. In this paper, we contribute a formal explanation of these failures in the particular case of sparse reward and deterministic environments. First, using a very elementary control problem, we illustrate that the learning process can get stuck into a fixed point corresponding to a poor solution. Then, generalizing from the studied example, we provide a detailed analysis of the underlying mechanisms which results in a new understanding of one of the convergence regimes of these algorithms. The resulting perspective casts a new light on already existing solutions to the issues we have highlighted, and suggests other potential approaches.
Multi-Level Network for High-Speed Multi-Person Pose Estimation
Venue: arXiv cs.CV 2019
Year: 2019

In multi-person pose estimation, the left/right joint type discrimination is always a hard problem because of the similar appearance. Traditionally, we solve this problem by stacking multiple refinement modules to increase network's receptive fields and capture more global context, which can also increase a great amount of computation. In this paper, we propose a Multi-level Network (MLN) that learns to aggregate features from lower-level (left/right information), upper-level (localization information), joint-limb level (complementary information) and global-level (context) information for discrimination of joint type. Through feature reuse and its intra-relation, MLN can attain comparable performance to other conventional methods while runtime speed retains at 42.2 FPS.
Join Query Optimization with Deep Reinforcement Learning Algorithms
Venue: arXiv cs.DB 2019
Year: 2019

Join query optimization is a complex task and is central to the performance of query processing. In fact it belongs to the class of NP-hard problems. Traditional query optimizers use dynamic programming (DP) methods combined with a set of rules and restrictions to avoid exhaustive enumeration of all possible join orders. However, DP methods are very resource intensive. Moreover, given simplifying assumptions of attribute independence, traditional query optimizers rely on erroneous cost estimations, which can lead to suboptimal query plans. Recent success of deep reinforcement learning (DRL) creates new opportunities for the field of query optimization to tackle the above-mentioned problems. In this paper, we present our DRL-based Fully Observed Optimizer (FOOP) which is a generic query optimization framework that enables plugging in different machine learning algorithms. The main idea of FOOP is to use a data-adaptive learning query optimizer that avoids exhaustive enumerations of join orders and is thus significantly faster than traditional approaches based on dynamic programming. In particular, we evaluate various DRL-algorithms and show that Proximal Policy Optimization significantly outperforms Q-learning based algorithms. Finally we demonstrate how ensemble learning techniques combined with DRL can further improve the query optimizer.
Doc2Vec on the PubMed corpus: study of a new approach to generate related articles
Venue: arXiv cs.CL 2019
Year: 2019

PubMed is the biggest and most used bibliographic database worldwide, hosting more than 26M biomedical publications. One of its useful features is the "similar articles" section, allowing the end-user to find scientific articles linked to the consulted document in term of context. The aim of this study is to analyze whether it is possible to replace the statistic model PubMed Related Articles (pmra) with a document embedding method. Doc2Vec algorithm was used to train models allowing to vectorize documents. Six of its parameters were optimised by following a grid-search strategy to train more than 1,900 models. Parameters combination leading to the best accuracy was used to train models on abstracts from the PubMed database. Four evaluations tasks were defined to determine what does or does not influence the proximity between documents for both Doc2Vec and pmra. The two different Doc2Vec architectures have different abilities to link documents about a common context. The terminological indexing, words and stems contents of linked documents are highly similar between pmra and Doc2Vec PV-DBOW architecture. These algorithms are also more likely to bring closer documents having a similar size. In contrary, the manual evaluation shows much better results for the pmra algorithm. While the pmra algorithm links documents by explicitly using terminological indexing in its formula, Doc2Vec does not need a prior indexing. It can infer relations between documents sharing a similar indexing, without any knowledge about them, particularly regarding the PV-DBOW architecture. In contrary, the human evaluation, without any clear agreement between evaluators, implies future studies to better understand this difference between PV-DBOW and pmra algorithm.
Device-Free User Authentication, Activity Classification and Tracking using Passive Wi-Fi Sensing: A Deep Learning Based Approach
Venue: arXiv cs.LG 2019
Year: 2019

Privacy issues related to video camera feeds have led to a growing need for suitable alternatives that provide functionalities such as user authentication, activity classification and tracking in a noninvasive manner. Existing infrastructure makes Wi-Fi a possible candidate, yet, utilizing traditional signal processing methods to extract information necessary to fully characterize an event by sensing weak ambient Wi-Fi signals is deemed to be challenging. This paper introduces a novel end to-end deep learning framework that simultaneously predicts the identity, activity and the location of a user to create user profiles similar to the information provided through a video camera. The system is fully autonomous and requires zero user intervention unlike systems that require user-initiated initialization, or a user held transmitting device to facilitate the prediction. The system can also predict the trajectory of the user by predicting the location of a user over consecutive time steps. The performance of the system is evaluated through experiments.
Faster Algorithms for Parametric Global Minimum Cut Problems
Venue: arXiv cs.DS 2019
Year: 2019

The parametric global minimum cut problem concerns a graph $G = (V,E)$ where the cost of each edge is an affine function of a parameter $μ\in \mathbb{R}^d$ for some fixed dimension $d$. We consider the problems of finding the next breakpoint in a given direction, and finding a parameter value with maximum minimum cut value. We develop strongly polynomial algorithms for these problems that are faster than a naive application of Megiddo's parametric search technique. Our results indicate that the next breakpoint problem is easier than the max value problem.
Lifelong Spectral Clustering
Venue: arXiv cs.LG 2019
Year: 2019

In the past decades, spectral clustering (SC) has become one of the most effective clustering algorithms. However, most previous studies focus on spectral clustering tasks with a fixed task set, which cannot incorporate with a new spectral clustering task without accessing to previously learned tasks. In this paper, we aim to explore the problem of spectral clustering in a lifelong machine learning framework, i.e., Lifelong Spectral Clustering (L2SC). Its goal is to efficiently learn a model for a new spectral clustering task by selectively transferring previously accumulated experience from knowledge library. Specifically, the knowledge library of L2SC contains two components: 1) orthogonal basis library: capturing latent cluster centers among the clusters in each pair of tasks; 2) feature embedding library: embedding the feature manifold information shared among multiple related tasks. As a new spectral clustering task arrives, L2SC firstly transfers knowledge from both basis library and feature library to obtain encoding matrix, and further redefines the library base over time to maximize performance across all the clustering tasks. Meanwhile, a general online update formulation is derived to alternatively update the basis library and feature library. Finally, the empirical experiments on several real-world benchmark datasets demonstrate that our L2SC model can effectively improve the clustering performance when comparing with other state-of-the-art spectral clustering algorithms.
A Secure and Robust Scheme for Sharing Confidential Information in IoT Systems
Venue: arXiv cs.CR 2019
Year: 2019

In Internet of Things (IoT) systems with security demands, there is often a need to distribute sensitive information (such as encryption keys, digital signatures, or login credentials, etc.) among the devices, so that it can be retrieved for confidential purposes at a later moment. However, this information cannot be entrusted to any one device, since the failure of that device or an attack on it will jeopardize the security of the entire network. Even if the information is divided among devices, there is still the danger that an attacker can compromise a group of devices and expose the sensitive information. In this work, we design and implement a secure and robust scheme to enable the distribution of sensitive information in IoT networks. The proposed approach has two important properties: (1) it uses Threshold Secret Sharing (TSS) to split the information into pieces distributed among all devices in the system - and so the information can only be retrieved collaboratively by groups of devices; and (2) it ensures the privacy and integrity of the information, even when attackers hijack a large number of devices and use them in concert - specifically, all the compromised devices can be identified, the confidentiality of information is kept, and authenticity of the secret can be guaranteed.
Taking a Stance on Fake News: Towards Automatic Disinformation Assessment via Deep Bidirectional Transformer Language Models for Stance Detection
Venue: arXiv cs.CL 2019
Year: 2019

The exponential rise of social media and digital news in the past decade has had the unfortunate consequence of escalating what the United Nations has called a global topic of concern: the growing prevalence of disinformation. Given the complexity and time-consuming nature of combating disinformation through human assessment, one is motivated to explore harnessing AI solutions to automatically assess news articles for the presence of disinformation. A valuable first step towards automatic identification of disinformation is stance detection, where given a claim and a news article, the aim is to predict if the article agrees, disagrees, takes no position, or is unrelated to the claim. Existing approaches in literature have largely relied on hand-engineered features or shallow learned representations (e.g., word embeddings) to encode the claim-article pairs, which can limit the level of representational expressiveness needed to tackle the high complexity of disinformation identification. In this work, we explore the notion of harnessing large-scale deep bidirectional transformer language models for encoding claim-article pairs in an effort to construct state-of-the-art stance detection geared for identifying disinformation. Taking advantage of bidirectional cross-attention between claim-article pairs via pair encoding with self-attention, we construct a large-scale language model for stance detection by performing transfer learning on a RoBERTa deep bidirectional transformer language model, and were able to achieve state-of-the-art performance (weighted accuracy of 90.01%) on the Fake News Challenge Stage 1 (FNC-I) benchmark. These promising results serve as motivation for harnessing such large-scale language models as powerful building blocks for creating effective AI solutions to combat disinformation.
LucidDream: Controlled Temporally-Consistent DeepDream on Videos
Venue: arXiv cs.CV 2019
Year: 2019

In this work, we aim to propose a set of techniques to improve the controllability and aesthetic appeal when DeepDream, which uses a pre-trained neural network to modify images by hallucinating objects into them, is applied to videos. In particular, we demonstrate a simple modification that improves control over the class of object that DeepDream is induced to hallucinate. We also show that the flickering artifacts which frequently appear when DeepDream is applied on videos can be mitigated by the use of an additional temporal consistency loss term.
AdapNet: Adaptability Decomposing Encoder-Decoder Network for Weakly Supervised Action Recognition and Localization
Venue: arXiv cs.CV 2019
Year: 2019

The point process is a solid framework to model sequential data, such as videos, by exploring the underlying relevance. As a challenging problem for high-level video understanding, weakly supervised action recognition and localization in untrimmed videos has attracted intensive research attention. Knowledge transfer by leveraging the publicly available trimmed videos as external guidance is a promising attempt to make up for the coarse-grained video-level annotation and improve the generalization performance. However, unconstrained knowledge transfer may bring about irrelevant noise and jeopardize the learning model. This paper proposes a novel adaptability decomposing encoder-decoder network to transfer reliable knowledge between trimmed and untrimmed videos for action recognition and localization via bidirectional point process modeling, given only video-level annotations. By decomposing the original features into domain-adaptable and domain-specific ones based on their adaptability, trimmed-untrimmed knowledge transfer can be safely confined within a more coherent subspace. An encoder-decoder based structure is carefully designed and jointly optimized to facilitate effective action classification and temporal localization. Extensive experiments are conducted on two benchmark datasets (i.e., THUMOS14 and ActivityNet1.3), and experimental results clearly corroborate the efficacy of our method.
Measuring similarity between two mixture trees using mixture distance metric and algorithms
Venue: arXiv cs.DS 2019
Year: 2019

Ancestral mixture model, proposed by Chen and Lindsay (2006), is an important model to build a hierarchical tree from high dimensional binary sequences. Mixture trees created from ancestral mixture models involve in the inferred evolutionary relationships among various biological species. Moreover, it contains the information of time when the species mutates. Tree comparison metric, an essential issue in bioinformatics, is to measure the similarity between trees. However, to our knowledge, the approach to the comparison between two mixture trees is still under development. In this paper, we propose a new metric, named mixture distance metric, to measure the similarity of two mixture trees. It uniquely considers the factor of evolutionary times between trees. In addition, we also further develop two algorithms to compute the mixture distance between two mixture trees. One requires O(n^2) and the other requires O(nh) computation time with O(n) preprocessing time, where n denotes the number of leaves in the two mixture trees, and h denotes the minimum height of these two trees.
A tale of two toolkits, report the second: bake off redux. Chapter 1. dictionary based classifiers
Venue: arXiv cs.LG 2019
Year: 2019

Time series classification (TSC) is the problem of learning labels from time dependent data. One class of algorithms is derived from a bag of words approach. A window is run along a series, the subseries is shortened and discretised to form a word, then features are formed from the histogram of frequency of occurrence of words. We call this type of approach to TSC dictionary based classification. We compare four dictionary based algorithms in the context of a wider project to update the great time series classification bakeoff, a comparative study published in 2017. We experimentally characterise the algorithms in terms of predictive performance, time complexity and space complexity. We find that we can improve on the previous best in terms of accuracy, but this comes at the cost of time and space. Alternatively, the same performance can be achieved with far less cost. We review the relative merits of the four algorithms before suggesting a path to possible improvement.
Zero-shot Chinese Discourse Dependency Parsing via Cross-lingual Mapping
Venue: arXiv cs.CL 2019
Year: 2019

Due to the absence of labeled data, discourse parsing still remains challenging in some languages. In this paper, we present a simple and efficient method to conduct zero-shot Chinese text-level dependency parsing by leveraging English discourse labeled data and parsing techniques. We first construct the Chinese-English mapping from the level of sentence and elementary discourse unit (EDU), and then exploit the parsing results of the corresponding English translations to obtain the discourse trees for the Chinese text. This method can automatically conduct Chinese discourse parsing, with no need of a large scale of Chinese labeled data.
Scheduling with Non-Renewable Resources: Minimizing the Sum of Completion Times
Venue: arXiv cs.DS 2019
Year: 2019

The paper considers single-machine scheduling problems with a non-renewable resource. In this setting, we are given a set jobs, each of which is characterized by a processing time, a weight, and the job also has some resource requirement. At fixed points in time, a certain amount of the resource is made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that at any time their resource requirement does not exceed the available amounts of resources. The objective that we consider here is the minimization of the sum of weighted completion times. We give polynomial approximation algorithms and complexity results for single scheduling machine problems. In particular, we show strong NP-hardness of the case of unit resource requirements and weights ($1|rm=1,a_j=1|\sum C_j$), thus answering an open question of Györgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a $3/2$-approximation for the same problem. We give simple constant factor approximations and a more complicated PTAS for the case of $0$ processing times ($1|rm=1,p_j=0|\sum w_jC_j$). We close the paper by proposing a new variant of the problem in which the resource arrival times are unknown. A $4$-approximation is presented for this variant, together with an $(4-\varepsilon)$-inapproximability result.
Multi-label Classification for Automatic Tag Prediction in the Context of Programming Challenges
Venue: arXiv cs.LG 2019
Year: 2019

One of the best ways for developers to test and improve their skills in a fun and challenging way are programming challenges, offered by a plethora of websites. For the inexperienced ones, some of the problems might appear too challenging, requiring some suggestions to implement a solution. On the other hand, tagging problems can be a tedious task for problem creators. In this paper, we focus on automating the task of tagging a programming challenge description using machine and deep learning methods. We observe that the deep learning methods implemented outperform well-known IR approaches such as tf-idf, thus providing a starting point for further research on the task.
PointRGCN: Graph Convolution Networks for 3D Vehicles Detection Refinement
Venue: arXiv cs.CV 2019
Year: 2019

In autonomous driving pipelines, perception modules provide a visual understanding of the surrounding road scene. Among the perception tasks, vehicle detection is of paramount importance for a safe driving as it identifies the position of other agents sharing the road. In our work, we propose PointRGCN: a graph-based 3D object detection pipeline based on graph convolutional networks (GCNs) which operates exclusively on 3D LiDAR point clouds. To perform more accurate 3D object detection, we leverage a graph representation that performs proposal feature and context aggregation. We integrate residual GCNs in a two-stage 3D object detection pipeline, where 3D object proposals are refined using a novel graph representation. In particular, R-GCN is a residual GCN that classifies and regresses 3D proposals, and C-GCN is a contextual GCN that further refines proposals by sharing contextual information between multiple proposals. We integrate our refinement modules into a novel 3D detection pipeline, PointRGCN, and achieve state-of-the-art performance on the easy difficulty for the bird eye view detection task.
An adaptive algorithm for quantum circuit simulation
Venue: arXiv cs.CC 2019
Year: 2019

Efficient simulation of quantum computers is essential for the development and validation of near-term quantum devices and the research on quantum algorithms. Up to date, two main approaches to simulation were in use, based on either full state or single amplitude evaluation. We propose an algorithm that efficiently interpolates between these two possibilities. Our approach elucidates the connection between quantum circuit simulation and partial evaluation of expressions in tensor algebra.