OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Distributed Computation of MIS and Generalized MIS in Linear Hypergraphs
Venue: arXiv cs.DC 2018
Year: 2018

Given a graph, a maximal independent set (MIS) is a maximal subset of pairwise non-adjacent vertices. Finding an MIS is a fundamental problem in distributed computing. Although the problem is extensively studied and well understood in simple graphs, our knowledge is still quite limited when solving it in hypergraphs, especially in the distributed CONGEST model. In this paper, we focus on linear hypergraphs---a class of hypergraphs in which any two hyperedges overlap on at most one node. We first present a randomized algorithm for computing an MIS in linear hypergraphs. It has poly-logarithmic runtime and it works in the CONGEST model. The algorithm uses a network decomposition to achieve fast parallel processing. Within each cluster of the decomposition, we run a distributed variant of a parallel hypergraph MIS algorithm by Luczak and Szymanska. We then propose the concept of a generalized maximal independent set (GMIS) as an extension to the classical MIS in hypergraphs. More specifically, in a GMIS, for each hyperedge $e$ in a hypergraph $\mathcal{H}$, we associate an integer threshold $t_e$ in the range $[1, |e|-1]$, and the goal is to find a maximal subset $\mathcal{I}$ of vertices that do not violate any threshold constraints: $\forall e \in E(\mathcal{H}), |e \cap \mathcal{I}| \leq t_e$. We hope that GMIS might capture a broader class of real-world problems than MIS; we also believe that GMIS is an interesting and challenging symmetry breaking problem on its own. Our second upper bound result is a distributed algorithm for computing a GMIS in linear hypergraphs, subject to the constraint that the maximum hyperedge size is bounded by some constant. Again, the algorithm has poly-logarithmic runtime and it works in the CONGEST model. It is obtained by generalizing our previous (linear) hypergraph MIS algorithm.
A Collision-Free Path Planning Algorithm for Unmanned Aerial Vehicle Delivery
Venue: arXiv cs.SY 2018
Year: 2018

Path planning is important for the autonomy of Unmanned Aerial Vehicle (UAV), especially for scheduling UAV delivery. However, the operating environment of UAVs is usually uncertain and dynamic. Without proper planning, collisions may happen where multiple UAVs are congested. Besides, there may also be temporary no-fly zone setup by authorities that makes airspace unusable. Thus, proper pre-departure planning that avoids such places is needed. In this paper, we formulate this problem into a Constraint Satisfaction Problem to find a collision-free shortest path on a dynamic graph. We propose a collision-free path planning algorithm that is based on A* algorithm. The main novelty is that we invent a heuristic function that also considers waiting time. We later show that, with added waiting penalty, the proposed algorithm is optimal because the heuristic is admissible. Implementation of this algorithm simulates UAV delivery using Singapore's airspace structure. Our simulation exhibits desirable runtime performance. Using the proposed algorithm, the percentage of collision-free routes decreases as number of requests per unit area increases, and this percentage drops significantly at boundary value. Our empirical analysis could aid the decision-making of no-fly zone policy and infrastructure of UAV delivery.
Anchor Cascade for Efficient Face Detection
Venue: arXiv cs.CV 2018
Year: 2018

Face detection is essential to facial analysis tasks such as facial reenactment and face recognition. Both cascade face detectors and anchor-based face detectors have translated shining demos into practice and received intensive attention from the community. However, cascade face detectors often suffer from a low detection accuracy, while anchor-based face detectors rely heavily on very large networks pre-trained on large scale image classification datasets such as ImageNet [1], which is not computationally efficient for both training and deployment. In this paper, we devise an efficient anchor-based cascade framework called anchor cascade. To improve the detection accuracy by exploring contextual information, we further propose a context pyramid maxout mechanism for anchor cascade. As a result, anchor cascade can train very efficient face detection models with a high detection accuracy. Specifically, comparing with a popular CNN-based cascade face detector MTCNN [2], our anchor cascade face detector greatly improves the detection accuracy, e.g., from 0.9435 to 0.9704 at 1k false positives on FDDB, while it still runs in comparable speed. Experimental results on two widely used face detection benchmarks, FDDB and WIDER FACE, demonstrate the effectiveness of the proposed framework.
Dispersion Bound for the Wyner-Ahlswede-Körner Network via Reverse Hypercontractivity on Types
Venue: arXiv cs.IT 2018
Year: 2018

This paper introduces a new converse machinery for a challenging class of distributed source-type problems (e.g.\ distributed source coding, common randomness generation, or hypothesis testing with communication constraints), through the example of the Wyner-Ahlswede-Körner network. Using the functional-entropic duality and the reverse hypercontractivity of the transposition semigroup, we lower bound the error probability for each joint type. Then by averaging the error probability over types, we lower bound the $c$-dispersion (which characterizes the second-order behavior of the weighted sum of the rates of the two compressors when a nonvanishing error probability is small) as the variance of the gradient of $\inf_{P_{U|X}}\{cH(Y|U)+I(U;X)\}$ with respect to $Q_{XY}$, the per-letter side information and source distribution. In comparison, using standard achievability arguments based on the method of types, we upper-bound the $c$-dispersion as the variance of $c\imath_{Y|U}(Y|U)+\imath_{U;X}(U;X)$, which improves the existing upper bounds but has a gap to the aforementioned lower bound.
Machine Learning in Compiler Optimisation
Venue: arXiv cs.PL 2018
Year: 2018

In the last decade, machine learning based compilation has moved from an an obscure research niche to a mainstream activity. In this article, we describe the relationship between machine learning and compiler optimisation and introduce the main concepts of features, models, training and deployment. We then provide a comprehensive survey and provide a road map for the wide variety of different research areas. We conclude with a discussion on open issues in the area and potential research directions. This paper provides both an accessible introduction to the fast moving area of machine learning based compilation and a detailed bibliography of its main achievements.
RowClone: Accelerating Data Movement and Initialization Using DRAM
Venue: arXiv cs.AR 2018
Year: 2018

In existing systems, to perform any bulk data movement operation (copy or initialization), the data has to first be read into the on-chip processor, all the way into the L1 cache, and the result of the operation must be written back to main memory. This is despite the fact that these operations do not involve any actual computation. RowClone exploits the organization and operation of commodity DRAM to perform these operations completely inside DRAM using two mechanisms. The first mechanism, Fast Parallel Mode, copies data between two rows inside the same DRAM subarray by issuing back-to-back activate commands to the source and the destination row. The second mechanism, Pipelined Serial Mode, transfers cache lines between two banks using the shared internal bus. RowClone significantly reduces the raw latency and energy consumption of bulk data copy and initialization. This reduction directly translates to improvement in performance and energy efficiency of systems running copy or initialization-intensive workloads
Efficient Utility-Driven Self-Healing Employing Adaptation Rules for Large Dynamic Architectures
Venue: arXiv cs.SE 2018
Year: 2018

Self-adaptation can be realized in various ways. Rule-based approaches prescribe the adaptation to be executed if the system or environment satisfy certain conditions and result in scalable solutions, however, with often only satisfying adaptation decisions. In contrast, utility-driven approaches determine optimal adaptation decisions by using an often costly optimization step, which typically does not scale well for larger problems. We propose a rule-based and utility-driven approach that achieves the beneficial properties of each of these directions such that the adaptation decisions are optimal while the computation remains scalable since an expensive optimization step can be avoided. The approach can be used for the architecture-based self-healing of large software systems. We define the utility for large dynamic architectures of such systems based on patterns capturing issues the self-healing must address and we use patternbased adaptation rules to resolve the issues. Defining the utility as well as the adaptation rules pattern-based allows us to compute the impact of each rule application on the overall utility and to realize an incremental and efficient utility-driven self-healing. We demonstrate the efficiency and optimality of our scheme in comparative experiments with a static rule-based scheme as a baseline and a utility-driven approach using a constraint solver.
Anonymous Heterogeneous Distributed Detection: Optimal Decision Rules, Error Exponents, and the Price of Anonymity
Venue: arXiv cs.IT 2018
Year: 2018

We explore the fundamental limits of heterogeneous distributed detection in an anonymous sensor network with n sensors and a single fusion center. The fusion center collects the single observation from each of the n sensors to detect a binary parameter. The sensors are clustered into multiple groups, and different groups follow different distributions under a given hypothesis. The key challenge for the fusion center is the anonymity of sensors - although it knows the exact number of sensors and the distribution of observations in each group, it does not know which group each sensor belongs to. It is hence natural to consider it as a composite hypothesis testing problem. First, we propose an optimal test called mixture likelihood ratio test based on the ratio of the uniform mixture of all distributions under one hypothesis to that under the other. Optimality is shown by first arguing that symmetric tests are optimal, which do not depend on the order of observations across the sensors, and then proving that the mixture likelihood ratio test is optimal among all symmetric tests. Second, we focus on the Neyman-Pearson setting and characterize the error exponent of the worst-case type-II error probability as n tends to infinity, assuming the number of sensors in each group is proportional to n. Finally, we generalize our result to find the collection of all achievable type-I and type-II error exponents, where the boundary of the region can be obtained by solving a convex program. Our results elucidate the price of anonymity in heterogeneous distributed detection, and can be extended to M-ary hypothesis testing with heterogeneous observations generated according to hidden latent variables. The results are also applied to distributed detection under Byzantine attacks, which hints that the conventional approach based on simple hypothesis testing might be too pessimistic.
Neural Cache: Bit-Serial In-Cache Acceleration of Deep Neural Networks
Venue: arXiv cs.AR 2018
Year: 2018

This paper presents the Neural Cache architecture, which re-purposes cache structures to transform them into massively parallel compute units capable of running inferences for Deep Neural Networks. Techniques to do in-situ arithmetic in SRAM arrays, create efficient data mapping and reducing data movement are proposed. The Neural Cache architecture is capable of fully executing convolutional, fully connected, and pooling layers in-cache. The proposed architecture also supports quantization in-cache. Our experimental results show that the proposed architecture can improve inference latency by 18.3x over state-of-art multi-core CPU (Xeon E5), 7.7x over server class GPU (Titan Xp), for Inception v3 model. Neural Cache improves inference throughput by 12.4x over CPU (2.2x over GPU), while reducing power consumption by 50% over CPU (53% over GPU).
DReAM: Dynamic Reconfigurable Architecture Modeling (full paper)
Venue: arXiv cs.FL 2018
Year: 2018

Modern systems evolve in unpredictable environments and have to continuously adapt their behavior to changing conditions. The "DReAM" (Dynamic Reconfigurable Architecture Modeling) framework, has been designed for modeling reconfigurable dynamic systems. It provides a rule-based language, inspired from Interaction Logic, which is expressive and easy to use encompassing all aspects of dynamicity including parametric multi-modal coordination with creation/deletion of components as well as mobility. Additionally, it allows the description of both endogenous/modular and exogenous/centralized coordination styles and sound transformations from one style to the other. The DReAM framework is implemented in the form of a Java API bundled with an execution engine. It allows to develop runnable systems combining the expressiveness of the rule-based notation together with the flexibility of this widespread programming language.
When Names Are Not Commonly Known: Epistemic Logic with Assignments
Venue: arXiv cs.AI 2018
Year: 2018

In standard epistemic logic, agent names are usually assumed to be common knowledge implicitly. This is unreasonable for various applications. Inspired by term modal logic and assignment operators in dynamic logic, we introduce a lightweight modal predicate logic where names can be non-rigid. The language can handle various de dicto and de re distinctions in a natural way. The main technical result is a complete axiomatisation of this logic over S5 models.
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
Venue: arXiv cs.CC 2018
Year: 2018

We study the 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph $G=(V,E)$, an alphabet set $Σ$ and, for each $\{u, v\}\in E$, a constraint $C_{uv} \subseteq Σ\timesΣ$, the goal is to find an assignment $σ: V \to Σ$ that satisfies as many constraints as possible, where a constraint $C_{uv}$ is satisfied if $(σ(u),σ(v))\in C_{uv}$. While the approximability of 2-CSPs is quite well understood when $|Σ|$ is constant, many problems are still open when $|Σ|$ becomes super constant. One such problem is whether it is hard to approximate 2-CSPs to within a polynomial factor of $|Σ| |V|$. Bellare et al. (1993) suggested that the answer to this question might be positive. Alas, despite efforts to resolve this conjecture, it remains open to this day. In this work, we separate $|V|$ and $|Σ|$ and ask a related but weaker question: is it hard to approximate 2-CSPs to within a polynomial factor of $|V|$ (while $|Σ|$ may be super-polynomial in $|V|$)? Assuming the exponential time hypothesis (ETH), we answer this question positively by showing that no polynomial time algorithm can approximate 2-CSPs to within a factor of $|V|^{1 - o(1)}$. Note that our ratio is almost linear, which is almost optimal as a trivial algorithm gives a $|V|$-approximation for 2-CSPs. Thanks to a known reduction, our result implies an ETH-hardness of approximating Directed Steiner Network with ratio $k^{1/4 - o(1)}$ where $k$ is the number of demand pairs. The ratio is roughly the square root of the best known ratio achieved by polynomial time algorithms (Chekuri et al., 2011; Feldman et al., 2012). Additionally, under Gap-ETH, our reduction for 2-CSPs not only rules out polynomial time algorithms, but also FPT algorithms parameterized by $|V|$. Similar statement applies for DSN parameterized by $k$.
Improv Chat: Second Response Generation for Chatbot
Venue: arXiv cs.CL 2018
Year: 2018

Existing research on response generation for chatbot focuses on \textbf{First Response Generation} which aims to teach the chatbot to say the first response (e.g. a sentence) appropriate to the conversation context (e.g. the user's query). In this paper, we introduce a new task \textbf{Second Response Generation}, termed as Improv chat, which aims to teach the chatbot to say the second response after saying the first response with respect the conversation context, so as to lighten the burden on the user to keep the conversation going. Specifically, we propose a general learning based framework and develop a retrieval based system which can generate the second responses with the users' query and the chatbot's first response as input. We present the approach to building the conversation corpus for Improv chat from public forums and social networks, as well as the neural networks based models for response matching and ranking. We include the preliminary experiments and results in this paper. This work could be further advanced with better deep matching models for retrieval base systems or generative models for generation based systems as well as extensive evaluations in real-life applications.
Multi-View Semantic Labeling of 3D Point Clouds for Automated Plant Phenotyping
Venue: arXiv cs.CV 2018
Year: 2018

Semantic labeling of 3D point clouds is important for the derivation of 3D models from real world scenarios in several economic fields such as building industry, facility management, town planning or heritage conservation. In contrast to these most common applications, we describe in this study the semantic labeling of 3D point clouds derived from plant organs by high-precision scanning. Our approach is optimized for the task of plant phenotyping with its very specific challenges and is employing a deep learning framework. Thereby, we report important experiences concerning detailed parameter initialization and optimization techniques. By evaluating our approach with challenging datasets we achieve state-of-the-art results without difficult and time consuming feature engineering as being necessary in traditional approaches to semantic labeling.
Exploiting Location Information to Enhance Throughput in Downlink V2I Systems
Venue: arXiv cs.IT 2018
Year: 2018

Vehicle-to-Infrastructure (V2I) technology, combined with millimeter wave (mmW) networks, may support high data rates for vehicular communication and therefore provides a whole new set of services. However, in dense urban environment, pedestrians or buildings cause strong blockage to the narrow beams at mmW, severely deteriorating the transmission rate. In this work, we model the downlink mmW V2I system as a simple erasure broadcast channel where the erasure (blockage) event is considered as the state of the channel. While state feedback can be obtained through protocols such as Automatic Repeat reQuest (ARQ), we also assume that the current state can be estimated through the location information shared by the communication peers. We evaluate, through an information-theoretic approach, the achievable downlink rate in such a system. Despite its highly theoretical nature, our result sheds light on how much the location information can contribute to improve the downlink date rate, e.g., as a function of the mobility (velocity) of the vehicles.
An Adaptive Population Size Differential Evolution with Novel Mutation Strategy for Constrained Optimization
Venue: arXiv cs.NE 2018
Year: 2018

Differential evolution (DE) has competitive performance on constrained optimization problems (COPs), which targets at searching for global optimal solution without violating the constraints. Generally, researchers pay more attention on avoiding violating the constraints than better objective function value. To achieve the aim of searching the feasible solutions accurately, an adaptive population size method and an adaptive mutation strategy are proposed in the paper. The adaptive population method is similar to a state switch which controls the exploring state and exploiting state according to the situation of feasible solution search. The novel mutation strategy is designed to enhance the effect of status switch based on adaptive population size, which is useful to reduce the constraint violations. Moreover, a mechanism based on multipopulation competition and a more precise method of constraint control are adopted in the proposed algorithm. The proposed differential evolution algorithm, APDE-NS, is evaluated on the benchmark problems from CEC2017 constrained real parameter optimization. The experimental results show the effectiveness of the proposed method is competitive compared to other state-of-the-art algorithms.
Retinal Vessel Segmentation Based on Conditional Deep Convolutional Generative Adversarial Networks
Venue: arXiv cs.CV 2018
Year: 2018

The segmentation of retinal vessels is of significance for doctors to diagnose the fundus diseases. However, existing methods have various problems in the segmentation of the retinal vessels, such as insufficient segmentation of retinal vessels, weak anti-noise interference ability, and sensitivity to lesions, etc. Aiming to the shortcomings of existed methods, this paper proposes the use of conditional deep convolutional generative adversarial networks to segment the retinal vessels. We mainly improve the network structure of the generator. The introduction of the residual module at the convolutional layer for residual learning makes the network structure sensitive to changes in the output, as to better adjust the weight of the generator. In order to reduce the number of parameters and calculations, using a small convolution to halve the number of channels in the input signature before using a large convolution kernel. By used skip connection to connect the output of the convolutional layer with the output of the deconvolution layer to avoid low-level information sharing. By verifying the method on the DRIVE and STARE datasets, the segmentation accuracy rate is 96.08% and 97.71%, the sensitivity reaches 82.74% and 85.34% respectively, and the F-measure reaches 82.08% and 85.02% respectively. The sensitivity is 4.82% and 2.4% higher than that of R2U-Net.
Iteratively Trained Interactive Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Deep learning requires large amounts of training data to be effective. For the task of object segmentation, manually labeling data is very expensive, and hence interactive methods are needed. Following recent approaches, we develop an interactive object segmentation system which uses user input in the form of clicks as the input to a convolutional network. While previous methods use heuristic click sampling strategies to emulate user clicks during training, we propose a new iterative training strategy. During training, we iteratively add clicks based on the errors of the currently predicted segmentation. We show that our iterative training strategy together with additional improvements to the network architecture results in improved results over the state-of-the-art.