OpenRaiser/Intern-Atlas huggingface dataset:
Real-Time Constrained Trajectory Planning and Vehicle Control for Proactive Autonomous Driving With Road Users
Venue: arXiv cs.SY 2019
Year: 2019

For motion planning and control of autonomous vehicles to be proactive and safe, pedestrians' and other road users' motions must be considered. In this paper, we present a vehicle motion planning and control framework, based on Model Predictive Control, accounting for moving obstacles. Measured pedestrian states are fed into a prediction layer which translates each pedestrians' predicted motion into constraints for the MPC problem. Simulations and experimental validation were performed with simulated crossing pedestrians to show the performance of the framework. Experimental results show that the controller is stable even under significant input delays, while still maintaining very low computational times. In addition, real pedestrian data was used to further validate the developed framework in simulations.
A New Frontier for Pull-Based Graph Processing
Venue: arXiv cs.DC 2019
Year: 2019

The trade-off between pull-based and push-based graph processing engines is well-understood. On one hand, pull-based engines can achieve higher throughput because their workloads are read-dominant, rather than write-dominant, and can proceed without synchronization between threads. On the other hand, push-based engines are much better able to take advantage of the frontier optimization, which leverages the fact that often only a small subset of the graph needs to be accessed to complete an iteration of a graph processing application. Hybrid engines attempt to overcome this trade-off by dynamically switching between push and pull, but there are two key disadvantages with this approach. First, applications must be implemented twice (once for push and once for pull), and second, processing throughput is reduced for iterations that run with push. We propose a radically different solution: rebuild the frontier optimization entirely such that it is well-suited for a pull-based engine. In doing so, we remove the only advantage that a push-based engine had over a pull-based engine, making it possible to eliminate the push-based engine entirely. We introduce Wedge, a pull-only graph processing framework that transforms the traditional source-oriented vertex-based frontier into a pull-friendly format called the Wedge Frontier. The transformation itself is expensive even when parallelized, so we introduce two key optimizations to make it practical. First, we perform the transformation only when the resulting Wedge Frontier is sufficiently sparse. Second, we coarsen the granularity of the representation of elements in the Wedge Frontier. These optimizations respectively improve Wedge's performance by up to 5x and 2x, enabling it to outperform Grazelle, Ligra, and GraphMat respectively by up to 2.8x, 4.9x, and 185.5x.
Hierarchical Routing Mixture of Experts
Venue: arXiv cs.LG 2019
Year: 2019

In regression tasks the distribution of the data is often too complex to be fitted by a single model. In contrast, partition-based models are developed where data is divided and fitted by local models. These models partition the input space and do not leverage the input-output dependency of multimodal-distributed data, and strong local models are needed to make good predictions. Addressing these problems, we propose a binary tree-structured hierarchical routing mixture of experts (HRME) model that has classifiers as non-leaf node experts and simple regression models as leaf node experts. The classifier nodes jointly soft-partition the input-output space based on the natural separateness of multimodal data. This enables simple leaf experts to be effective for prediction. Further, we develop a probabilistic framework for the HRME model, and propose a recursive Expectation-Maximization (EM) based algorithm to learn both the tree structure and the expert models. Experiments on a collection of regression tasks validate the effectiveness of our method compared to a variety of other regression models.
Safe Policy Synthesis in Multi-Agent POMDPs via Discrete-Time Barrier Functions
Venue: arXiv cs.RO 2019
Year: 2019

A multi-agent partially observable Markov decision process (MPOMDP) is a modeling paradigm used for high-level planning of heterogeneous autonomous agents subject to uncertainty and partial observation. Despite their modeling efficiency, MPOMDPs have not received significant attention in safety-critical settings. In this paper, we use barrier functions to design policies for MPOMDPs that ensure safety. Notably, our method does not rely on discretization of the belief space, or finite memory. To this end, we formulate sufficient and necessary conditions for the safety of a given set based on discrete-time barrier functions (DTBFs) and we demonstrate that our formulation also allows for Boolean compositions of DTBFs for representing more complicated safe sets. We show that the proposed method can be implemented online by a sequence of one-step greedy algorithms as a standalone safe controller or as a safety-filter given a nominal planning policy. We illustrate the efficiency of the proposed methodology based on DTBFs using a high-fidelity simulation of heterogeneous robots.
Diversity-Promoting Deep Reinforcement Learning for Interactive Recommendation
Venue: arXiv cs.IR 2019
Year: 2019

Interactive recommendation that models the explicit interactions between users and the recommender system has attracted a lot of research attentions in recent years. Most previous interactive recommendation systems only focus on optimizing recommendation accuracy while overlooking other important aspects of recommendation quality, such as the diversity of recommendation results. In this paper, we propose a novel recommendation model, named \underline{D}iversity-promoting \underline{D}eep \underline{R}einforcement \underline{L}earning (D$^2$RL), which encourages the diversity of recommendation results in interaction recommendations. More specifically, we adopt a Determinantal Point Process (DPP) model to generate diverse, while relevant item recommendations. A personalized DPP kernel matrix is maintained for each user, which is constructed from two parts: a fixed similarity matrix capturing item-item similarity, and the relevance of items dynamically learnt through an actor-critic reinforcement learning framework. We performed extensive offline experiments as well as simulated online experiments with real world datasets to demonstrate the effectiveness of the proposed model.
Minimizing Age in Gateway Based Update Systems
Venue: arXiv cs.IT 2019
Year: 2019

We consider a network of status updating sensors whose updates are collected and sent to a monitor by a gateway. The monitor desires as fresh as possible updates from the network of sensors. The gateway may either poll a sensor for its status update or it may transmit collected sensor updates to the monitor. We derive the average age at the monitor for such a setting. We observe that increasing the frequency of transmissions to the monitor has the upside of resetting sensor age at the monitor to smaller values. However, it increases the length of time that elapses before a sensor is polled again. This motivates our investigation of policies that fix the number of sensors s the gateway polls before transmitting to the monitor. For any s, we show that when sensor transmission times to the gateway are independent and identically distributed (iid), for independent but possibly non-identical transmission times to the monitor, it is optimal to poll a sensor with the maximum age at the gateway first. Also, under simplifying assumptions, the optimal value of s increases as the square root of the number of sensors. For non-identical sensor transmission times, we consider a policy that polls a sensor such that the resulting average change in age is minimized. We compare our policy proposals with other policies, over a wide selection of transmission time distributions.
Trends on Computer Security: Cryptography, User Authentication, Denial of Service and Intrusion Detection
Venue: arXiv cs.CR 2019
Year: 2019

The new generation of security threats has been promoted by digital currencies and real-time applications, where all users develop new ways to communicate on the Internet. Security has evolved in the need of privacy and anonymity for all users and his portable devices. New technologies in every field prove that users need security features integrated into their communication applications, parallel systems for mobile devices, internet, and identity management. This review presents the key concepts of the main areas in computer security and how it has evolved in the last years. This work focuses on cryptography, user authentication, denial of service attacks, intrusion detection and firewalls.
BotGraph: Web Bot Detection Based on Sitemap
Venue: arXiv cs.CR 2019
Year: 2019

The web bots have been blamed for consuming large amount of Internet traffic and undermining the interest of the scraped sites for years. Traditional bot detection studies focus mainly on signature-based solution, but advanced bots usually forge their identities to bypass such detection. With increasing cloud migration, cloud providers provide new opportunities for an effective bot detection based on big data to solve this issue. In this paper, we present a behavior-based bot detection scheme called BotGraph that combines sitemap and convolutional neural network (CNN) to detect inner behavior of bots. Experimental results show that BotGraph achieves ~95% recall and precision on 35-day production data traces from different customers including the Bing search engine and several sites.
A compact high order Alternating Direction Implicit method for three-dimensional acoustic wave equation with variable coefficient
Venue: arXiv cs.NA 2019
Year: 2019

Efficient and accurate numerical simulation of seismic wave propagation is important in various Geophysical applications such as seismic full waveform inversion (FWI) problem. However, due to the large size of the physical domain and requirement on low numerical dispersion, many existing numerical methods are inefficient for numerical modelling of seismic wave propagation in a heterogeneous media. Despite the great efforts that have been devoted during the past decades, it still remains a challenging task in the development of efficient and accurate finite difference method for the multi-dimensional acoustic wave equation with variable velocity. In this paper, we proposed a Padé approximation based finite difference scheme for solving the acoustic wave equation in three-dimensional heterogeneous media. The new method is obtained by combining the Padé approximation and a novel algebraic manipulation. The efficiency of the new algorithm is further improved through the Alternative Directional Implicit (ADI) method. The stability of the new algorithm has been theoretically proved by the energy method. The new method is conditionally stable with a better Courant - Friedrichs - Lewy condition (CFL) condition, which has been verified numerically. Extensive numerical examples have been solved, which demonstrated that the new method is accurate, efficient and stable.
Identifying Experts in Software Libraries and Frameworks among GitHub Users
Venue: arXiv cs.SE 2019
Year: 2019

Software development increasingly depends on libraries and frameworks to increase productivity and reduce time-to-market. Despite this fact, we still lack techniques to assess developers expertise in widely popular libraries and frameworks. In this paper, we evaluate the performance of unsupervised (based on clustering) and supervised machine learning classifiers (Random Forest and SVM) to identify experts in three popular JavaScript libraries: facebook/react, mongodb/node-mongodb, and socketio/socket.io. First, we collect 13 features about developers activity on GitHub projects, including commits on source code files that depend on these libraries. We also build a ground truth including the expertise of 575 developers on the studied libraries, as self-reported by them in a survey. Based on our findings, we document the challenges of using machine learning classifiers to predict expertise in software libraries, using features extracted from GitHub. Then, we propose a method to identify library experts based on clustering feature data from GitHub; by triangulating the results of this method with information available on Linkedin profiles, we show that it is able to recommend dozens of GitHub users with evidences of being experts in the studied JavaScript libraries. We also provide a public dataset with the expertise of 575 developers on the studied libraries.
Debiasing Community Detection: The Importance of Lowly-Connected Nodes
Venue: arXiv cs.SI 2019
Year: 2019

Community detection is an important task in social network analysis, allowing us to identify and understand the communities within the social structures. However, many community detection approaches either fail to assign low degree (or lowly-connected) users to communities, or assign them to trivially small communities that prevent them from being included in analysis. In this work, we investigate how excluding these users can bias analysis results. We then introduce an approach that is more inclusive for lowly-connected users by incorporating them into larger groups. Experiments show that our approach outperforms the existing state-of-the-art in terms of F1 and Jaccard similarity scores while reducing the bias towards low-degree users.
Interactive segmentation of medical images through fully convolutional neural networks
Venue: arXiv cs.CV 2019
Year: 2019

Image segmentation plays an essential role in medicine for both diagnostic and interventional tasks. Segmentation approaches are either manual, semi-automated or fully-automated. Manual segmentation offers full control over the quality of the results, but is tedious, time consuming and prone to operator bias. Fully automated methods require no human effort, but often deliver sub-optimal results without providing users with the means to make corrections. Semi-automated approaches keep users in control of the results by providing means for interaction, but the main challenge is to offer a good trade-off between precision and required interaction. In this paper we present a deep learning (DL) based semi-automated segmentation approach that aims to be a "smart" interactive tool for region of interest delineation in medical images. We demonstrate its use for segmenting multiple organs on computed tomography (CT) of the abdomen. Our approach solves some of the most pressing clinical challenges: (i) it requires only one to a few user clicks to deliver excellent 2D segmentations in a fast and reliable fashion; (ii) it can generalize to previously unseen structures and "corner cases"; (iii) it delivers results that can be corrected quickly in a smart and intuitive way up to an arbitrary degree of precision chosen by the user and (iv) ensures high accuracy. We present our approach and compare it to other techniques and previous work to show the advantages brought by our method.
Deep Neural Networks Improve Radiologists' Performance in Breast Cancer Screening
Venue: arXiv cs.LG 2019
Year: 2019

We present a deep convolutional neural network for breast cancer screening exam classification, trained and evaluated on over 200,000 exams (over 1,000,000 images). Our network achieves an AUC of 0.895 in predicting whether there is a cancer in the breast, when tested on the screening population. We attribute the high accuracy of our model to a two-stage training procedure, which allows us to use a very high-capacity patch-level network to learn from pixel-level labels alongside a network learning from macroscopic breast-level labels. To validate our model, we conducted a reader study with 14 readers, each reading 720 screening mammogram exams, and find our model to be as accurate as experienced radiologists when presented with the same data. Finally, we show that a hybrid model, averaging probability of malignancy predicted by a radiologist with a prediction of our neural network, is more accurate than either of the two separately. To better understand our results, we conduct a thorough analysis of our network's performance on different subpopulations of the screening population, model design, training procedure, errors, and properties of its internal representations.
On Extracting Data from Tables that are Encoded using HTML
Venue: arXiv cs.IR 2019
Year: 2019

Tables are a common means to display data in human-friendly formats. Many authors have worked on proposals to extract those data back since this has many interesting applications. In this article, we summarise and compare many of the proposals to extract data from tables that are encoded using HTML and have been published between $2000$ and $2018$. We first present a vocabulary that homogenises the terminology used in this field; next, we use it to summarise the proposals; finally, we compare them side by side. Our analysis highlights several challenges to which no proposal provides a conclusive solution and a few more that have not been addressed sufficiently; simply put, no proposal provides a complete solution to the problem, which seems to suggest that this research field shall keep active in the near future. We have also realised that there is no consensus regarding the datasets and the methods used to evaluate the proposals, which hampers comparing the experimental results.
Inequalities related to some types of entropies and divergences
Venue: arXiv cs.IT 2019
Year: 2019

The aim of this paper is to discuss new results concerning some kinds of parametric extended entropies and divergences. As a result of our studies for mathematical properties on entropy and divergence, we give new bounds for the Tsallis quasilinear entropy and divergence by applying the Hermite-Hadamard inequality. We also give bounds for biparametrical extended entropies and divergences which have been given in \cite{7}. In addition, we study $(r,q)$-quasilinear entropies and divergences as alternative biparametrical extended entropy and divergence, and then we give bounds for them. Finally we obtain inequalities for an extended Lin's divergence and some characterizations of Fermi-Dirac entropy and Bose-Einstein entropy.
Walking with Confidence: Safety Regulation for Full Order Biped Models
Venue: arXiv cs.RO 2019
Year: 2019

Safety guarantees are valuable in the control of walking robots, as falling can be both dangerous and costly. Unfortunately, set-based tools for generating safety guarantees (such as sums-of-squares optimization) are typically restricted to simplified, low-dimensional models of walking robots. For more complex models, methods based on hybrid zero dynamics can ensure the local stability of a pre-specified limit cycle, but provide limited guarantees. This paper combines the benefits of both approaches by using sums-of-squares optimization on a hybrid zero dynamics manifold to generate a guaranteed safe set for a 10-dimensional walking robot model. Along with this set, this paper describes how to generate a controller that maintains safety by modifying the manifold parameters when on the edge of the safe set. The proposed approach, which is applied to a bipedal Rabbit model, provides a roadmap for applying sums-of-squares verification techniques to high dimensional systems. This opens the door for a broad set of tools that can generate safety guarantees and regulating controllers for complex walking robot models.
On Computing the Number of Short Cycles in Bipartite Graphs Using the Spectrum of the Directed Edge Matrix
Venue: arXiv cs.IT 2019
Year: 2019

Counting short cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. There are two computational approaches to count short cycles (with length smaller than $2g$, where $g$ is the girth of the graph) in bipartite graphs. The first approach is applicable to a general (irregular) bipartite graph, and uses the spectrum $\{η_i\}$ of the directed edge matrix of the graph to compute the multiplicity $N_k$ of $k$-cycles with $k < 2g$ through the simple equation $N_k = \sum_i η_i^k/(2k)$. This approach has a computational complexity $\mathcal{O}(|E|^3)$, where $|E|$ is number of edges in the graph. The second approach is only applicable to bi-regular bipartite graphs, and uses the spectrum $\{λ_i\}$ of the adjacency matrix (graph spectrum) and the degree sequences of the graph to compute $N_k$. The complexity of this approach is $\mathcal{O}(|V|^3)$, where $|V|$ is number of nodes in the graph. This complexity is less than that of the first approach, but the equations involved in the computations of the second approach are very tedious, particularly for $k \geq g+6$. In this paper, we establish an analytical relationship between the two spectra $\{η_i\}$ and $\{λ_i\}$ for bi-regular bipartite graphs. Through this relationship, the former spectrum can be derived from the latter through simple equations. This allows the computation of $N_k$ using $N_k = \sum_i η_i^k/(2k)$ but with a complexity of $\mathcal{O}(|V|^3)$ rather than $\mathcal{O}(|E|^3)$.
Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue
Venue: arXiv cs.GT 2019
Year: 2019

We study combinatorial auctions with interdependent valuations. In such settings, each agent $i$ has a private signal $s_i$ that captures her private information, and the valuation function of every agent depends on the entire signal profile, ${\bf s}=(s_1,\ldots,s_n)$. The literature in economics shows that the interdependent model gives rise to strong impossibility results, and identifies assumptions under which optimal solutions can be attained. The computer science literature provides approximation results for simple single-parameter settings (mostly single item auctions, or matroid feasibility constraints). Both bodies of literature focus largely on valuations satisfying a technical condition termed {\em single crossing} (or variants thereof). We consider the class of {\em submodular over signals} (SOS) valuations (without imposing any single-crossing type assumption), and provide the first welfare approximation guarantees for multi-dimensional combinatorial auctions, achieved by universally ex-post IC-IR mechanisms. Our main results are: $(i)$ 4-approximation for any single-parameter downward-closed setting with single-dimensional signals and SOS valuations; $(ii)$ 4-approximation for any combinatorial auction with multi-dimensional signals and {\em separable}-SOS valuations; and $(iii)$ $(k+3)$- and $(2\log(k)+4)$-approximation for any combinatorial auction with single-dimensional signals, with $k$-sized signal space, for SOS and strong-SOS valuations, respectively. All of our results extend to a parameterized version of SOS, $d$-SOS, while losing a factor that depends on $d$.