OpenRaiser/Intern-Atlas huggingface dataset:
Anytime Motion Planning on Large Dense Roadmaps with Expensive Edge Evaluations
Venue: arXiv cs.RO 2017
Year: 2017

We propose an algorithmic framework for efficient anytime motion planning on large dense geometric roadmaps, in domains where collision checks and therefore edge evaluations are computationally expensive. A large dense roadmap (graph) can typically ensure the existence of high quality solutions for most motion-planning problems, but the size of the roadmap, particularly in high-dimensional spaces, makes existing search-based planning algorithms computationally expensive. We deal with the challenges of expensive search and collision checking in two ways. First, we frame the problem of anytime motion planning on roadmaps as searching for the shortest path over a sequence of subgraphs of the entire roadmap graph, generated by some densification strategy. This lets us achieve bounded sub-optimality with bounded worst-case planning effort. Second, for searching each subgraph, we develop an anytime planning algorithm which uses a belief model to compute the collision probability of unknown configurations and searches for paths that are Pareto-optimal in path length and collision probability. This algorithm is efficient with respect to collision checks as it searches for successively shorter paths. We theoretically analyze both our ideas and evaluate them individually on high-dimensional motion-planning problems. Finally, we apply both of these ideas together in our algorithmic framework for anytime motion planning, and show that it outperforms BIT* on high-dimensional hypercube problems.
Going Further with Point Pair Features
Venue: arXiv cs.CV 2017
Year: 2017

Point Pair Features is a widely used method to detect 3D objects in point clouds, however they are prone to fail in presence of sensor noise and background clutter. We introduce novel sampling and voting schemes that significantly reduces the influence of clutter and sensor noise. Our experiments show that with our improvements, PPFs become competitive against state-of-the-art methods as it outperforms them on several objects from challenging benchmarks, at a low computational cost.
Mathematics of Isogeny Based Cryptography
Venue: arXiv cs.CR 2017
Year: 2017

These lectures notes were written for a summer school on Mathematics for post-quantum cryptography in Thiès, Senegal. They try to provide a guide for Masters' students to get through the vast literature on elliptic curves, without getting lost on their way to learning isogeny based cryptography. They are by no means a reference text on the theory of elliptic curves, nor on cryptography; students are encouraged to complement these notes with some of the books recommended in the bibliography. The presentation is divided in three parts, roughly corresponding to the three lectures given. In an effort to keep the reader interested, each part alternates between the fundamental theory of elliptic curves, and applications in cryptography. We often prefer to have the main ideas flow smoothly, rather than having a rigorous presentation as one would have in a more classical book. The reader will excuse us for the inaccuracies and the omissions.
Fine Grained Knowledge Transfer for Personalized Task-oriented Dialogue Systems
Venue: arXiv cs.CL 2017
Year: 2017

Training a personalized dialogue system requires a lot of data, and the data collected for a single user is usually insufficient. One common practice for this problem is to share training dialogues between different users and train multiple sequence-to-sequence dialogue models together with transfer learning. However, current sequence-to-sequence transfer learning models operate on the entire sentence, which might cause negative transfer if different personal information from different users is mixed up. We propose a personalized decoder model to transfer finer granularity phrase-level knowledge between different users while keeping personal preferences of each user intact. A novel personal control gate is introduced, enabling the personalized decoder to switch between generating personalized phrases and shared phrases. The proposed personalized decoder model can be easily combined with various deep models and can be trained with reinforcement learning. Real-world experimental results demonstrate that the phrase-level personalized decoder improves the BLEU over multiple sentence-level transfer baseline models by as much as 7.5%.
Truncated Polynomial Expansion Downlink Precoders and Uplink Detectors for Massive MIMO
Venue: arXiv cs.IT 2017
Year: 2017

In TDD reciprocity-based massive MIMO it is essential to be able to compute the downlink precoding matrix over all OFDM resource blocks within a small fraction of the uplink-downlink slot duration. Early implementation of massive MIMO are limited to the simple Conjugate Beamforming (ConjBF) precoding method, because of such computation latency limitation. However, it has been widely demonstrated by theoretical analysis and system simulation that Regularized Zero-Forcing (RZF) precoding is generally much more effective than ConjBF for a large but practical number of transmit antennas. In order to recover a significant fraction of the gap between ConjBF and RZF and yet meeting the very strict computation latency constraints, truncated polynomial expansion (TPE) methods have been proposed. In this paper we present a novel TPE method that outperforms all previously proposed methods in the general non-symmetric case of users with arbitrary antenna correlation. In addition, the proposed method is significantly simpler and more flexible than previously proposed methods based on deterministic equivalents and free probability in large random matrix theory. We consider power allocation with our TPE approach, and show that classical system optimization problems such as min-sum power and max-min rate can be easily solved. Furthermore, we provide a detailed computation latency analysis specifically targeted to a highly parallel FPGA hardware architecture.
Deep Residual Text Detection Network for Scene Text
Venue: arXiv cs.CV 2017
Year: 2017

Scene text detection is a challenging problem in computer vision. In this paper, we propose a novel text detection network based on prevalent object detection frameworks. In order to obtain stronger semantic feature, we adopt ResNet as feature extraction layers and exploit multi-level feature by combining hierarchical convolutional networks. A vertical proposal mechanism is utilized to avoid proposal classification, while regression layer remains working to improve localization accuracy. Our approach evaluated on ICDAR2013 dataset achieves F-measure of 0.91, which outperforms previous state-of-the-art results in scene text detection.
Latent Constrained Correlation Filter
Venue: arXiv cs.CV 2017
Year: 2017

Correlation filters are special classifiers designed for shift-invariant object recognition, which are robust to pattern distortions. The recent literature shows that combining a set of sub-filters trained based on a single or a small group of images obtains the best performance. The idea is equivalent to estimating variable distribution based on the data sampling (bagging), which can be interpreted as finding solutions (variable distribution approximation) directly from sampled data space. However, this methodology fails to account for the variations existed in the data. In this paper, we introduce an intermediate step -- solution sampling -- after the data sampling step to form a subspace, in which an optimal solution can be estimated. More specifically, we propose a new method, named latent constrained correlation filters (LCCF), by mapping the correlation filters to a given latent subspace, and develop a new learning framework in the latent subspace that embeds distribution-related constraints into the original problem. To solve the optimization problem, we introduce a subspace based alternating direction method of multipliers (SADMM), which is proven to converge at the saddle point. Our approach is successfully applied to three different tasks, including eye localization, car detection and object tracking. Extensive experiments demonstrate that LCCF outperforms the state-of-the-art methods. The source code will be publicly available. https://github.com/bczhangbczhang/.
Practical Scalability for Stackelberg Security Games
Venue: arXiv cs.GT 2017
Year: 2017

Stackelberg Security Games (SSGs) have been adopted widely for modeling adversarial interactions. With increasing size of the applications of SSGs, scalability of equilibrium computation is an important research problem. While prior research has made progress with regards to scalability, many real world problems cannot be solved satisfactorily yet as per current requirements; these include the deployed federal air marshals (FAMS) application and the threat screening (TSG) problem at airports. Further, these problem domains are inherently limited by NP hardness shown in prior literature. We initiate a principled study of approximations in zero-sum SSGs. Our contribution includes the following: (1) a unified model of SSGs called adversarial randomized allocation (ARA) games that allows studying most SSGs in one model, (2) hardness of approximation results for zero-sum ARA, as well as for the sub-problem of allocating federal air marshal (FAMS) and threat screening problem (TSG) at airports, (3) an approximation framework for zero-sum ARA with provable approximation guarantees and (4) experiments demonstrating the significant scalability of up to 1000x improvement in runtime with an acceptable 5% solution quality loss.
Robust Kullback-Leibler Divergence and Universal Hypothesis Testing for Continuous Distributions
Venue: arXiv cs.IT 2017
Year: 2017

Universal hypothesis testing refers to the problem of deciding whether samples come from a nominal distribution or an unknown distribution that is different from the nominal distribution. Hoeffding's test, whose test statistic is equivalent to the empirical Kullback-Leibler divergence (KLD), is known to be asymptotically optimal for distributions defined on finite alphabets. With continuous observations, however, the discontinuity of the KLD in the distribution functions results in significant complications for universal hypothesis testing. This paper introduces a robust version of the classical KLD, defined as the KLD from a distribution to the L'evy ball of a known distribution. This robust KLD is shown to be continuous in the underlying distribution function with respect to the weak convergence. The continuity property enables the development of a universal hypothesis test for continuous observations that is shown to be asymptotically optimal for continuous distributions in the same sense as that of the Hoeffding's test for discrete distributions.
On the ERM Principle with Networked Data
Venue: arXiv cs.LG 2017
Year: 2017

Networked data, in which every training example involves two objects and may share some common objects with others, is used in many machine learning tasks such as learning to rank and link prediction. A challenge of learning from networked examples is that target values are not known for some pairs of objects. In this case, neither the classical i.i.d.\ assumption nor techniques based on complete U-statistics can be used. Most existing theoretical results of this problem only deal with the classical empirical risk minimization (ERM) principle that always weights every example equally, but this strategy leads to unsatisfactory bounds. We consider general weighted ERM and show new universal risk bounds for this problem. These new bounds naturally define an optimization problem which leads to appropriate weights for networked examples. Though this optimization problem is not convex in general, we devise a new fully polynomial-time approximation scheme (FPTAS) to solve it.
A machine learning approach for efficient uncertainty quantification using multiscale methods
Venue: arXiv cs.LG 2017
Year: 2017

Several multiscale methods account for sub-grid scale features using coarse scale basis functions. For example, in the Multiscale Finite Volume method the coarse scale basis functions are obtained by solving a set of local problems over dual-grid cells. We introduce a data-driven approach for the estimation of these coarse scale basis functions. Specifically, we employ a neural network predictor fitted using a set of solution samples from which it learns to generate subsequent basis functions at a lower computational cost than solving the local problems. The computational advantage of this approach is realized for uncertainty quantification tasks where a large number of realizations has to be evaluated. We attribute the ability to learn these basis functions to the modularity of the local problems and the redundancy of the permeability patches between samples. The proposed method is evaluated on elliptic problems yielding very promising results.
Extremely Large Minibatch SGD: Training ResNet-50 on ImageNet in 15 Minutes
Venue: arXiv cs.DC 2017
Year: 2017

We demonstrate that training ResNet-50 on ImageNet for 90 epochs can be achieved in 15 minutes with 1024 Tesla P100 GPUs. This was made possible by using a large minibatch size of 32k. To maintain accuracy with this large minibatch size, we employed several techniques such as RMSprop warm-up, batch normalization without moving averages, and a slow-start learning rate schedule. This paper also describes the details of the hardware and software of the system used to achieve the above performance.
A Refutation of Guinea's "Understanding SAT is in P"
Venue: arXiv cs.CC 2017
Year: 2017

In this work, we summarize and critique the paper "Understanding SAT is in P" by Alejandro Sánchez Guinea [arXiv:1504.00337]. The paper claims to present a polynomial-time solution for the NP-complete language 3-SAT. We show that Guinea's algorithm is flawed and does not prove 3-SAT is in P.
Faithful to the Original: Fact Aware Neural Abstractive Summarization
Venue: arXiv cs.IR 2017
Year: 2017

Unlike extractive summarization, abstractive summarization has to fuse different parts of the source text, which inclines to create fake facts. Our preliminary study reveals nearly 30% of the outputs from a state-of-the-art neural summarization system suffer from this problem. While previous abstractive summarization approaches usually focus on the improvement of informativeness, we argue that faithfulness is also a vital prerequisite for a practical abstractive summarization system. To avoid generating fake facts in a summary, we leverage open information extraction and dependency parse technologies to extract actual fact descriptions from the source text. The dual-attention sequence-to-sequence framework is then proposed to force the generation conditioned on both the source text and the extracted fact descriptions. Experiments on the Gigaword benchmark dataset demonstrate that our model can greatly reduce fake summaries by 80%. Notably, the fact descriptions also bring significant improvement on informativeness since they often condense the meaning of the source text.
Constraint Solving via Fractional Edge Covers
Venue: arXiv cs.DS 2017
Year: 2017

Many important combinatorial problems can be modeled as constraint satisfaction problems. Hence identifying polynomial-time solvable classes of constraint satisfaction problems has received a lot of attention. In this paper, we are interested in structural properties that can make the problem tractable. So far, the largest structural class that is known to be polynomial-time solvable is the class of bounded hypertree width instances introduced by Gottlob et al. Here we identify a new class of polynomial-time solvable instances: those having bounded fractional edge cover number. Combining hypertree width and fractional edge cover number, we then introduce the notion of fractional hypertree width. We prove that constraint satisfaction problems with bounded fractional hypertree width can be solved in polynomial time (provided that a the tree decomposition is given in the input). Together with a recent approximation algorithm for finding such decompositions by Marx, it follows that bounded fractional hypertree width is now the most general known structural property that guarantees polynomial-time solvability.
A Supervised Learning Concept for Reducing User Interaction in Passenger Cars
Venue: arXiv cs.SY 2017
Year: 2017

In this article an automation system for human-machine-interfaces (HMI) for setpoint adjustment using supervised learning is presented. We use HMIs of multi-modal thermal conditioning systems in passenger cars as example for a complex setpoint selection system. The goal is the reduction of interaction complexity up to full automation. The approach is not limited to climate control applications but can be extended to other setpoint-based HMIs.
Linking Types for Multi-Language Software: Have Your Cake and Eat It Too
Venue: arXiv cs.PL 2017
Year: 2017

Software developers compose systems from components written in many different languages. A business-logic component may be written in Java or OCaml, a resource-intensive component in C or Rust, and a high-assurance component in Coq. In this multi-language world, program execution sends values from one linguistic context to another. This boundary-crossing exposes values to contexts with unforeseen behavior---that is, behavior that could not arise in the source language of the value. For example, a Rust function may end up being applied in an ML context that violates the memory usage policy enforced by Rust's type system. This leads to the question of how developers ought to reason about code in such a multi-language world where behavior inexpressible in one language is easily realized in another. This paper proposes the novel idea of linking types to address the problem of reasoning about single-language components in a multi-lingual setting. Specifically, linking types allow programmers to annotate where in a program they can link with components inexpressible in their unadulterated language. This enables developers to reason about (behavioral) equality using only their own language and the annotations, even though their code may be linked with code written in a language with more expressive power.
Beyond the Hype: On Using Blockchains in Trust Management for Authentication
Venue: arXiv cs.CR 2017
Year: 2017

Trust Management (TM) systems for authentication are vital to the security of online interactions, which are ubiquitous in our everyday lives. Various systems, like the Web PKI (X.509) and PGP's Web of Trust are used to manage trust in this setting. In recent years, blockchain technology has been introduced as a panacea to our security problems, including that of authentication, without sufficient reasoning, as to its merits.In this work, we investigate the merits of using open distributed ledgers (ODLs), such as the one implemented by blockchain technology, for securing TM systems for authentication. We formally model such systems, and explore how blockchain can help mitigate attacks against them. After formal argumentation, we conclude that in the context of Trust Management for authentication, blockchain technology, and ODLs in general, can offer considerable advantages compared to previous approaches. Our analysis is, to the best of our knowledge, the first to formally model and argue about the security of TM systems for authentication, based on blockchain technology. To achieve this result, we first provide an abstract model for TM systems for authentication. Then, we show how this model can be conceptually encoded in a blockchain, by expressing it as a series of state transitions. As a next step, we examine five prevalent attacks on TM systems, and provide evidence that blockchain-based solutions can be beneficial to the security of such systems, by mitigating, or completely negating such attacks.
Provably efficient neural network representation for image classification
Venue: arXiv cs.LG 2017
Year: 2017

The state-of-the-art approaches for image classification are based on neural networks. Mathematically, the task of classifying images is equivalent to finding the function that maps an image to the label it is associated with. To rigorously establish the success of neural network methods, we should first prove that the function has an efficient neural network representation, and then design provably efficient training algorithms to find such a representation. Here, we achieve the first goal based on a set of assumptions about the patterns in the images. The validity of these assumptions is very intuitive in many image classification problems, including but not limited to, recognizing handwritten digits.
The effect of website attributes and mental involvement online impulse purchases
Venue: arXiv cs.CY 2017
Year: 2017

This research aimed at investigating the impact of website features and involvement on immediate online shopping. The research is applied in terms of type and it is causative in terms of methodology. The statistical population consisted of all citizens of Tabriz, who have purchased clothes online at least once and 260 individuals were chosen randomly and the questionnaires were collected according to this sample size. The data were collected by questionnaire. For analysis of the data, software SPSS and for test of the model hypotheses, SEM was used by confirmatory factor analysis. The results showed that the website benefit-oriented features have a positive impact on immediate online shopping and website benefit-oriented features have no significant impact on immediate online shopping.
Bypass Fraud Detection: Artificial Intelligence Approach
Venue: arXiv cs.CY 2017
Year: 2017

Telecom companies are severely damaged by bypass fraud or SIM boxing. However, there is a shortage of published research to tackle this problem. The traditional method of Test Call Generating is easily overcome by fraudsters and the need for more sophisticated ways is inevitable. In this work, we are developing intelligent algorithms that mine a huge amount of mobile operator's data and detect the SIMs that are used to bypass international calls. This method will make it hard for fraudsters to generate revenue and hinder their work. Also by reducing fraudulent activities, quality of service can be increased as well as customer satisfaction. Our technique has been evaluated and tested on real world mobile operator data, and proved to be very efficient.
Attention-based Information Fusion using Multi-Encoder-Decoder Recurrent Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

With the rising number of interconnected devices and sensors, modeling distributed sensor networks is of increasing interest. Recurrent neural networks (RNN) are considered particularly well suited for modeling sensory and streaming data. When predicting future behavior, incorporating information from neighboring sensor stations is often beneficial. We propose a new RNN based architecture for context specific information fusion across multiple spatially distributed sensor stations. Hereby, latent representations of multiple local models, each modeling one sensor station, are jointed and weighted, according to their importance for the prediction. The particular importance is assessed depending on the current context using a separate attention function. We demonstrate the effectiveness of our model on three different real-world sensor network datasets.