OpenRaiser/Intern-Atlas huggingface dataset:
The Electric Two-echelon Vehicle Routing Problem
Venue: arXiv cs.DS 2018
Year: 2018

Two-echelon distribution systems are attractive from an economical standpoint and help to keep large vehicles out of city centers. Large trucks can be used to deliver goods to intermediate facilities in accessible locations, whereas smaller vehicles allow to reach the final customers. Due to their reduced size and emissions, companies consider using an electric fleet of terrestrian or aerial vehicles for last mile deliveries. Route planning in multi-tier logistics leads to notoriously difficult problems. This difficulty is accrued in the presence of an electric fleet, since each vehicle operates on a smaller range, and may require visits to charging stations. To study these challenges, we introduce the Electric Two-echelon Vehicle Routing Problem as a prototypical problem. We propose a large neighbourhood search metaheuristic as well as an exact mathematical programming algorithm, which uses decomposition techniques to enumerate promising first-level solutions, in conjunction with bounding functions and route enumeration for the second-level routes. These algorithms produce optimal or near-optimal solutions for the problem, and allow us to evaluate the impact of several defining features of optimized battery-powered distribution networks. We created representative E2EVRP benchmark instances to simulate realistic metropolitan areas. In particular, we observe that the detour miles due to recharging decrease proportionally to $1/ρ^x$ with $x \approx 5/4$ as a function of the charging stations density $ρ$; e.g., in a scenario where the density of charging stations is doubled, recharging detours are reduced by 58\%. Finally, we evaluate the trade-off between battery capacity and detour miles. This estimate is critical for strategic fleet-acquisition decisions, in a context where large batteries are generally more costly and less environment-friendly.
Hate Speech Detection: A Solved Problem? The Challenging Case of Long Tail on Twitter
Venue: arXiv cs.CL 2018
Year: 2018

In recent years, the increasing propagation of hate speech on social media and the urgent need for effective counter-measures have drawn significant investment from governments, companies, and researchers. A large number of methods have been developed for automated hate speech detection online. This aims to classify textual content into non-hate or hate speech, in which case the method may also identify the targeting characteristics (i.e., types of hate, such as race, and religion) in the hate speech. However, we notice significant difference between the performance of the two (i.e., non-hate v.s. hate). In this work, we argue for a focus on the latter problem for practical reasons. We show that it is a much more challenging task, as our analysis of the language in the typical datasets shows that hate speech lacks unique, discriminative features and therefore is found in the 'long tail' in a dataset that is difficult to discover. We then propose Deep Neural Network structures serving as feature extractors that are particularly effective for capturing the semantics of hate speech. Our methods are evaluated on the largest collection of hate speech datasets based on Twitter, and are shown to be able to outperform the best performing method by up to 5 percentage points in macro-average F1, or 8 percentage points in the more challenging case of identifying hateful content.
Automating Reading Comprehension by Generating Question and Answer Pairs
Venue: arXiv cs.CL 2018
Year: 2018

Neural network-based methods represent the state-of-the-art in question generation from text. Existing work focuses on generating only questions from text without concerning itself with answer generation. Moreover, our analysis shows that handling rare words and generating the most appropriate question given a candidate answer are still challenges facing existing approaches. We present a novel two-stage process to generate question-answer pairs from the text. For the first stage, we present alternatives for encoding the span of the pivotal answer in the sentence using Pointer Networks. In our second stage, we employ sequence to sequence models for question generation, enhanced with rich linguistic features. Finally, global attention and answer encoding are used for generating the question most relevant to the answer. We motivate and linguistically analyze the role of each component in our framework and consider compositions of these. This analysis is supported by extensive experimental evaluations. Using standard evaluation metrics as well as human evaluations, our experimental results validate the significant improvement in the quality of questions generated by our framework over the state-of-the-art. The technique presented here represents another step towards more automated reading comprehension assessment. We also present a live system \footnote{Demo of the system is available at \url{https://www.cse.iitb.ac.in/~vishwajeet/autoqg.html}.} to demonstrate the effectiveness of our approach.
Syntax-Aware Language Modeling with Recurrent Neural Networks
Venue: arXiv cs.CL 2018
Year: 2018

Neural language models (LMs) are typically trained using only lexical features, such as surface forms of words. In this paper, we argue this deprives the LM of crucial syntactic signals that can be detected at high confidence using existing parsers. We present a simple but highly effective approach for training neural LMs using both lexical and syntactic information, and a novel approach for applying such LMs to unparsed text using sequential Monte Carlo sampling. In experiments on a range of corpora and corpus sizes, we show our approach consistently outperforms standard lexical LMs in character-level language modeling; on the other hand, for word-level models the models are on a par with standard language models. These results indicate potential for expanding LMs beyond lexical surface features to higher-level NLP features for character-level models.
Geometric and LP-based heuristics for the quadratic travelling salesman problem
Venue: arXiv cs.DM 2018
Year: 2018

A generalization of the classical TSP is the so-called quadratic travelling salesman problem (QTSP), in which a cost coefficient is associated with the transition in every vertex, i.e. with every pair of edges traversed in succession. In this paper we consider two geometrically motivated special cases of the QTSP known from the literature, namely the angular-metric TSP, where transition costs correspond to turning angles in every vertex, and the angular-distance-metric TSP, where a linear combination of turning angles and Euclidean distances is considered. At first we introduce a wide range of heuristic approaches, motivated by the typical geometric structure of optimal solutions. In particular, we exploit lens-shaped neighborhoods of edges and a decomposition of the graph into layers of convex hulls, which are then merged into a tour by a greedy-type procedure or by utilizing an ILP model. Secondly, we consider an ILP model for a standard linearization of QTSP and compute fractional solutions of a relaxation. By rounding we obtain a collection of subtours, paths and isolated points, which are combined into a tour by various strategies, all of them involving auxiliary ILP models. Finally, different improvement heuristics are proposed, most notably a matheuristic which locally reoptimizes the solution for rectangular sectors of the given point set by an ILP approach. Extensive computational experiments for benchmark instances from the literature and extensions thereof illustrate the Pareto-efficient frontier of algorithms in a (running time, objective value)-space. It turns out that our new methods clearly dominate the previously published heuristics.
Local Kernels that Approximate Bayesian Regularization and Proximal Operators
Venue: arXiv cs.CV 2018
Year: 2018

In this work, we broadly connect kernel-based filtering (e.g. approaches such as the bilateral filters and nonlocal means, but also many more) with general variational formulations of Bayesian regularized least squares, and the related concept of proximal operators. The latter set of variational/Bayesian/proximal formulations often result in optimization problems that do not have closed-form solutions, and therefore typically require global iterative solutions. Our main contribution here is to establish how one can approximate the solution of the resulting global optimization problems with use of locally adaptive filters with specific kernels. Our results are valid for small regularization strength but the approach is powerful enough to be useful for a wide range of applications because we expose how to derive a "kernelized" solution to these problems that approximates the global solution in one-shot, using only local operations. As another side benefit in the reverse direction, given a local data-adaptive filter constructed with a particular choice of kernel, we enable the interpretation of such filters in the variational/Bayesian/proximal framework.
Integrated Optimization of Partitioning, Scheduling and Floorplanning for Partially Dynamically Reconfigurable Systems
Venue: arXiv cs.AR 2018
Year: 2018

Confronted with the challenge of high performance for applications and the restriction of hardware resources for field-programmable gate arrays (FPGAs), partial dynamic reconfiguration (PDR) technology is anticipated to accelerate the reconfiguration process and alleviate the device shortage. In this paper, we propose an integrated optimization framework for task partitioning, scheduling and floorplanning on partially dynamically reconfigurable FPGAs. The partitions, schedule, and floorplan of the tasks are represented by the partitioned sequence triple P-ST (PS,QS,RS), where (PS,QS) is a hybrid nested sequence pair (HNSP) for representing the spatial and temporal partitions, as well as the floorplan, and RS is the partitioned dynamic configuration order of the tasks. The floorplanning and scheduling of task modules can be computed from the partitioned sequence triple P-ST in O(n^2) time. To integrate the exploration of the scheduling and floorplanning design space, we use a simulated annealing-based search engine and elaborate a perturbation method, where a randomly chosen task module is removed from the partition sequence triple and then inserted back into a proper position selected from all the (n+1)^3 possible combinations of partitions, schedule and floorplan. The experimental results demonstrate the efficiency and effectiveness of the proposed framework.
Multi-Agent Submodular Optimization
Venue: arXiv cs.DS 2018
Year: 2018

Recent years have seen many algorithmic advances in the area of submodular optimization: (SO) $\min/\max~f(S): S \in \mathcal{F}$, where $\mathcal{F}$ is a given family of feasible sets over a ground set $V$ and $f:2^V \rightarrow \mathbb{R}$ is submodular. This progress has been coupled with a wealth of new applications for these models. Our focus is on a more general class of \emph{multi-agent submodular optimization} (MASO) which was introduced by Goel et al. in the minimization setting: $\min \sum_i f_i(S_i): S_1 \uplus S_2 \uplus \cdots \uplus S_k \in \mathcal{F}$. Here we use $\uplus$ to denote disjoint union and hence this model is attractive where resources are being allocated across $k$ agents, each with its own submodular cost function $f_i()$. In this paper we explore the extent to which the approximability of the multi-agent problems are linked to their single-agent {\em primitives}, referred to informally as the {\em multi-agent gap}. We present different reductions that transform a multi-agent problem into a single-agent one. For maximization we show that (MASO) admits an $O(α)$-approximation whenever (SO) admits an $α$-approximation over the multilinear formulation, and thus substantially expanding the family of tractable models. We also discuss several family classes (such as spanning trees, matroids, and $p$-systems) that have a provable multi-agent gap of 1. In the minimization setting we show that (MASO) has an $O(α\cdot \min \{k, \log^2 (n)\})$-approximation whenever (SO) admits an $α$-approximation over the convex formulation. In addition, we discuss the class of "bounded blocker" families where there is a provably tight O$(\log n)$ gap between (MASO) and (SO).
Towards a Multi-array Architecture for Accelerating Large-scale Matrix Multiplication on FPGAs
Venue: arXiv cs.AR 2018
Year: 2018

Large-scale floating-point matrix multiplication is a fundamental kernel in many scientific and engineering applications. Most existing work only focus on accelerating matrix multiplication on FPGA by adopting a linear systolic array. This paper towards the extension of this architecture by proposing a scalable and highly configurable multi-array architecture. In addition, we propose a work-stealing scheme to ensure the equality in the workload partition among multiple linear arrays. Furthermore, an analytical model is developed to determine the optimal design parameters. Experiments on a real-life convolutional neural network (CNN) show that we can obtain the optimal extension of the linear array architecture.
Efficient FPGA Implementation of Conjugate Gradient Methods for Laplacian System using HLS
Venue: arXiv cs.DC 2018
Year: 2018

In this paper, we study FPGA based pipelined and superscalar design of two variants of conjugate gradient methods for solving Laplacian equation on a discrete grid; the first version corresponds to the original conjugate gradient algorithm, and the second version corresponds to a slightly modified version of the same. In conjugate gradient method to solve partial differential equations, matrix vector operations are required in each iteration; these operations can be implemented as 5 point stencil operations on the grid without explicitely constructing the matrix. We show that a pipelined and superscalar design using high level synthesis written in C language leads to a significant reduction in latencies for both methods. When comparing these two, we show that the later has roughly two times lower latency than the former given the same degree of superscalarity. These reductions in latencies for the newer variant of CG is due to parallel implementations of stencil operation on subdomains of the grid, and dut to overlap of these stencil operations with dot product operations. In a superscalar design, domain needs to be partitioned, and boundary data needs to be copied, which requires padding. In 1D partition, the padding latency increases as the number of partitions increase. For a streaming data flow model, we propose a novel traversal of the grid for 2D domain decomposition that leads to 2 times reduction in latency cost involved with padding compared to 1D partitions. Our implementation is roughly 10 times faster than software implementation for linear system of dimension $10000 \times 10000.$
Parallel FPGA Router using Sub-Gradient method and Steiner tree
Venue: arXiv cs.DC 2018
Year: 2018

In the FPGA (Field Programmable Gate Arrays) design flow, one of the most time-consuming step is the routing of nets. Therefore, there is a need to accelerate it. In a recent paper by Hoo et. al., the authors have developed a Linear Programming based framework that parallelizes this routing process to achieve significant speedups (the algorithm is termed as ParaLaR). However, this approach has certain weaknesses. Namely, the constraints violation by the solution and a local minima that could be improved. We address these two issues here. In our paper, we use this framework and solve it using the Primal-Dual sub-gradient method that better exploits the problem properties. We also propose a better way to update the size of the step taken by this iterative algorithm. We perform experiments on a set of standard benchmarks, where we show that our algorithm outperforms the standard existing algorithms (VPR and ParaLaR). We achieve up to 22% improvement in the constraints violation and the standard metric of the minimum channel width when compared with ParaLaR (which is same as in VPR). We achieve about 20% savings in another standard metric of the total wire length (when compared with VPR), which is the same as for ParaLaR. Hence, our algorithm achieves minimum value for all the three parameters. Also, the critical path delay for our algorithm is almost same as compared to VPR and ParaLaR. We achieve relative speedups of 3 times when we run a parallel version of our algorithm using 4 threads.
A Simple Algorithm for Estimating Distribution Parameters from $n$-Dimensional Randomized Binary Responses
Venue: arXiv cs.CR 2018
Year: 2018

Randomized response is attractive for privacy preserving data collection because the provided privacy can be quantified by means such as differential privacy. However, recovering and analyzing statistics involving multiple dependent randomized binary attributes can be difficult, posing a significant barrier to use. In this work, we address this problem by identifying and analyzing a family of response randomizers that change each binary attribute independently with the same probability. Modes of Google's Rappor randomizer as well as applications of two well-known classical randomized response methods, Warner's original method and Simmons' unrelated question method, belong to this family. We show that randomizers in this family transform multinomial distribution parameters by an iterated Kronecker product of an invertible and bisymmetric $2 \times 2$ matrix. This allows us to present a simple and efficient algorithm for obtaining unbiased maximum likelihood parameter estimates for $k$-way marginals from randomized responses and provide theoretical bounds on the statistical efficiency achieved. We also describe the efficiency - differential privacy tradeoff. Importantly, both randomization of responses and the estimation algorithm are simple to implement, an aspect critical to technologies for privacy protection and security.
On Trade in Bilateral Oligopolies with Altruistic and Spiteful Agents
Venue: arXiv cs.GT 2018
Year: 2018

This paper studies the effects of altruism and spitefulness in a two-sided market in which agents behave strategically and trade according to the Shapley-Shubik mechanism. By assuming that altruistic agents have concerns for others on the opposite side of the market, it shows that agents always find advantageous to trade. However, they prefer to stay out of the market and consume their endowments when there are altruistic agents who have concerns for the welfare of those on the same side of the market, or when there are spiteful agents. These non-trade situations occur either because the necessary first-order conditions for optimality are violated or because agents' payoff functions are not concave.
Learning Local Distortion Visibility From Image Quality Data-sets
Venue: arXiv cs.MM 2018
Year: 2018

Accurate prediction of local distortion visibility thresholds is critical in many image and video processing applications. Existing methods require an accurate modeling of the human visual system, and are derived through pshycophysical experiments with simple, artificial stimuli. These approaches, however, are difficult to generalize to natural images with complex types of distortion. In this paper, we explore a different perspective, and we investigate whether it is possible to learn local distortion visibility from image quality scores. We propose a convolutional neural network based optimization framework to infer local detection thresholds in a distorted image. Our model is trained on multiple quality datasets, and the results are correlated with empirical visibility thresholds collected on complex stimuli in a recent study. Our results are comparable to state-of-the-art mathematical models that were trained on phsycovisual data directly. This suggests that it is possible to predict psychophysical phenomena from visibility information embedded in image quality scores.
Cache-Assisted Broadcast-Relay Wireless Networks: A Delivery-Time Cache-Memory Tradeoff
Venue: arXiv cs.IT 2018
Year: 2018

An emerging trend of next generation communication systems is to provide network edges with additional capabilities such as storage resources in the form of caches to reduce file delivery latency. To investigate this aspect, we study the fundamental limits of a cache-aided broadcast-relay wireless network consisting of one central base station, $M$ cache-equipped transceivers and $K$ receivers from a latency-centric perspective. We use the normalized delivery time (NDT) to capture the per-bit latency for the worst-case file request pattern, normalized with respect to a reference interference-free system with unlimited transceiver cache capabilities. The objective is to design the schemes for cache placement and file delivery in order to minimize the NDT. To this end, we establish a novel converse and two types of achievability schemes applicable to both time-variant and invariant channels. The first scheme is a general one-shot scheme for any $M$ and $K$ that synergistically exploits both multicasting (coded) caching and distributed zero-forcing opportunities. We show that the proposed one-shot scheme (i) attains gains attributed to both individual and collective transceiver caches (ii) is NDT-optimal for various parameter settings, particularly at higher cache sizes. The second scheme, on the other hand, designs beamformers to facilitate both subspace interference alignment and zero-forcing at lower cache sizes. Exploiting both schemes, we are able to characterize for various special cases of $M$ and $K$ which satisfy $K+M\leq 4$ the optimal tradeoff between cache storage and latency. The tradeoff illustrates that the NDT is the preferred choice to capture the latency of a system rather than the commonly used sum degrees-of-freedom (DoF). In fact, our optimal tradeoff refutes the popular belief that increasing cache sizes translates to increasing the achievable sum DoF.
Experience Recommendation for Long Term Safe Learning-based Model Predictive Control in Changing Operating Conditions
Venue: arXiv cs.RO 2018
Year: 2018

Learning has propelled the cutting edge of performance in robotic control to new heights, allowing robots to operate with high performance in conditions that were previously unimaginable. The majority of the work, however, assumes that the unknown parts are static or slowly changing. This limits them to static or slowly changing environments. However, in the real world, a robot may experience various unknown conditions. This paper presents a method to extend an existing single mode GP-based safe learning controller to learn an increasing number of non-linear models for the robot dynamics. We show that this approach enables a robot to re-use past experience from a large number of previously visited operating conditions, and to safely adapt when a new and distinct operating condition is encountered. This allows the robot to achieve safety and high performance in an large number of operating conditions that do not have to be specified ahead of time. Our approach runs independently from the controller, imposing no additional computation time on the control loop regardless of the number of previous operating conditions considered. We demonstrate the effectiveness of our approach in experiment on a 900\,kg ground robot with both physical and artificial changes to its dynamics. All of our experiments are conducted using vision for localization.