OpenRaiser/Intern-Atlas huggingface dataset:
Precise but Natural Specification for Robot Tasks
Venue: arXiv cs.RO 2018
Year: 2018

We present Flipper, a natural language interface for describing high-level task specifications for robots that are compiled into robot actions. Flipper starts with a formal core language for task planning that allows expressing rich temporal specifications and uses a semantic parser to provide a natural language interface. Flipper provides immediate visual feedback by executing an automatically constructed plan of the task in a graphical user interface. This allows the user to resolve potentially ambiguous interpretations. Flipper extends itself via naturalization: its users can add definitions for utterances, from which Flipper induces new rules and adds them to the core language, gradually growing a more and more natural task specification language. Flipper improves the naturalization by generalizing the definition provided by users. Unlike other task-specification systems, Flipper enables natural language interactions while maintaining the expressive power and formal precision of a programming language. We show through an initial user study that natural language interactions and generalization can considerably ease the description of tasks. Moreover, over time, users employ more and more concepts outside of the initial core language. Such extensions are available to the Flipper community, and users can use concepts that others have defined.
On stochastic imitation dynamics in large-scale networks
Venue: arXiv cs.SY 2018
Year: 2018

We consider a broad class of stochastic imitation dynamics over networks, encompassing several well known learning models such as the replicator dynamics. In the considered models, players have no global information about the game structure: they only know their own current utility and the one of neighbor players contacted through pairwise interactions in a network. In response to this information, players update their state according to some stochastic rules. For potential population games and complete interaction networks, we prove convergence and long-lasting permanence close to the evolutionary stable strategies of the game. These results refine and extend the ones known for deterministic imitation dynamics as they account for new emerging behaviors including meta-stability of the equilibria. Finally, we discuss extensions of our results beyond the fully mixed case, studying imitation dynamics where agents interact on complex communication networks.
State tracking of linear ensembles via optimal mass transport
Venue: arXiv cs.SY 2018
Year: 2018

We consider the problems of tracking an ensemble of indistinguishable agents with linear dynamics based only on output measurements. In this setting, the dynamics of the agents can be modeled by distribution flows in the state space and the measurements correspond to distributions in the output space. In this paper we formulate the corresponding state estimation problem using optimal mass transport theory with prior linear dynamics, and the optimal solution gives an estimate of the state trajectories of the ensemble. For general distributions of systems this can be formulated as a convex optimization problem which is computationally feasible with when the number of state dimensions is low. In the case where the marginal distributions are Gaussian, the problem is reformulated as a semidefinite programming and can be efficiently solved for tracking systems with a large number of states.
A Gold Standard for Emotion Annotation in Stack Overflow
Venue: arXiv cs.SE 2018
Year: 2018

Software developers experience and share a wide range of emotions throughout a rich ecosystem of communication channels. A recent trend that has emerged in empirical software engineering studies is leveraging sentiment analysis of developers' communication traces. We release a dataset of 4,800 questions, answers, and comments from Stack Overflow, manually annotated for emotions. Our dataset contributes to the building of a shared corpus of annotated resources to support research on emotion awareness in software development.
Comparison of various image fusion methods for impervious surface classification from VNREDSat-1
Venue: arXiv cs.CV 2018
Year: 2018

Impervious surface is an important indicator for urban development monitoring. Accurate urban impervious surfaces mapping with VNREDSat-1 remains challenging due to their spectral diversity not captured by individual PAN image. In this artical, five multi-resolution image fusion techniques were compared for classification task of urban impervious surface. The result shows that for VNREDSat-1 dataset, UNB and Wavelet tranform methods are the best techniques reserving spatial and spectral information of original MS image, respectively. However, the UNB technique gives best results when it comes to impervious surface classification especially in the case of shadow area included in non-impervious surface group.
Pathways to Fragmentation:User Flows and Web Distribution Infrastructures
Venue: arXiv cs.CY 2018
Year: 2018

This study analyzes how web audiences flow across online digital features. We construct a directed network of user flows based on sequential user clickstreams for all popular websites (n=1761), using traffic data obtained from a panel of a million web users in the United States. We analyze these data to identify constellations of websites that are frequently browsed together in temporal sequences, both by similar user groups in different browsing sessions as well as by disparate users. Our analyses thus render visible previously hidden online collectives and generate insight into the varied roles that curatorial infrastructures may play in shaping audience fragmentation on the web.
Learning SMaLL Predictors
Venue: arXiv cs.LG 2018
Year: 2018

We present a new machine learning technique for training small resource-constrained predictors. Our algorithm, the Sparse Multiprototype Linear Learner (SMaLL), is inspired by the classic machine learning problem of learning $k$-DNF Boolean formulae. We present a formal derivation of our algorithm and demonstrate the benefits of our approach with a detailed empirical study.
Game Theoretic Analysis of Road User Safety Scenarios Involving Autonomous Vehicles
Venue: arXiv cs.GT 2018
Year: 2018

Interactions between pedestrians, bikers, and human-driven vehicles have been a major concern in traffic safety over the years. The upcoming age of autonomous vehicles will further raise major problems on whether self-driving cars can accurately avoid accidents; on the other hand, usability issues arise on whether human-driven cars and pedestrians can dominate the road at the expense of the autonomous vehicles which will be programmed to avoid accidents. This paper proposes some game theoretical models applied to related traffic scenarios. In the first two games the reciprocal influence between a pedestrian and a vehicle (either autonomous or not) is analyzed, while the third game investigates the intersection of two vehicles, possibly autonomous. The games have been simulated in order to demonstrate the theoretical analysis and the predicted behaviors. These investigations can shed new lights on how novel urban traffic regulations could be required to allow for a better interaction of vehicles and a general improved management of traffic and communication vehicular networks.
Securing Untrusted Full-Duplex Relay Channels in the Presence of Multiple External Cluster-Based Eavesdroppers
Venue: arXiv cs.IT 2018
Year: 2018

This letter investigates the physical layer security in a wireless cooperative network where communication is assisted by a full-duplex (FD) untrusted relay in the presence of multiple external eavesdroppers. A cluster-based colluding eavesdropping setting is considered, where illegitimate nodes with common interests are grouped in a cluster. In order to confuse the different eavesdropping clusters, we consider artificial-noise-aided beamforming at the source node. Moreover, FD relay jamming is adopted to improve the system's security. To maintain secure communications against the untrusted relay node, a FD destination jamming scheme is adopted. Our proposed scheme is designed based on the channel state information of the legitimate nodes only. Numerical results show that the optimal power allocation factor between data and artificial noise depends on the total number of antennas of the different colluding eavesdropping clusters.
Estimating network structure from unreliable measurements
Venue: arXiv cs.SI 2018
Year: 2018

Most empirical studies of networks assume that the network data we are given represent a complete and accurate picture of the nodes and edges in the system of interest, but in real-world situations this is rarely the case. More often the data only specify the network structure imperfectly -- like data in essentially every other area of empirical science, network data are prone to measurement error and noise. At the same time, the data may be richer than simple network measurements, incorporating multiple measurements, weights, lengths or strengths of edges, node or edge labels, or annotations of various kinds. Here we develop a general method for making estimates of network structure and properties using any form of network data, simple or complex, when the data are unreliable, and give example applications to a selection of social and biological networks.
Efficient Mendler-Style Lambda-Encodings in Cedille
Venue: arXiv cs.PL 2018
Year: 2018

It is common to model inductive datatypes as least fixed points of functors. We show that within the Cedille type theory we can relax functoriality constraints and generically derive an induction principle for Mendler-style lambda-encoded inductive datatypes, which arise as least fixed points of covariant schemes where the morphism lifting is defined only on identities. Additionally, we implement a destructor for these lambda-encodings that runs in constant-time. As a result, we can define lambda-encoded natural numbers with an induction principle and a constant-time predecessor function so that the normal form of a numeral requires only linear space. The paper also includes several more advanced examples.
Submodular maximization with uncertain knapsack capacity
Venue: arXiv cs.DS 2018
Year: 2018

We consider the maximization problem of monotone submodular functions under an uncertain knapsack constraint. Specifically, the problem is discussed in the situation that the knapsack capacity is not given explicitly and can be accessed only through an oracle that answers whether or not the current solution is feasible when an item is added to the solution. Assuming that cancellation of the last item is allowed when it overflows the knapsack capacity, we discuss the robustness ratios of adaptive policies for this problem, which are the worst case ratios of the objective values achieved by the output solutions to the optimal objective values. We present a randomized policy of robustness ratio $(1-1/e)/2$, and a deterministic policy of robustness ratio $2(1-1/e)/21$. We also consider a universal policy that chooses items following a precomputed sequence. We present a randomized universal policy of robustness ratio $(1-1/\sqrt[4]{e})/2$. When the cancellation is not allowed, no randomized adaptive policy achieves a constant robustness ratio. Because of this hardness, we assume that a probability distribution of the knapsack capacity is given, and consider computing a sequence of items that maximizes the expected objective value. We present a polynomial-time randomized algorithm of approximation ratio $(1-1/\sqrt[4]{e})/4-ε$ for any small constant $ε>0$.
Single module identifiability in linear dynamic networks
Venue: arXiv cs.SY 2018
Year: 2018

A recent development in data-driven modelling addresses the problem of identifying dynamic models of interconnected systems, represented as linear dynamic networks. For these networks the notion network identifiability has been introduced recently, which reflects the property that different network models can be distinguished from each other. Network identifiability is extended to cover the uniqueness of a single module in the network model. Conditions for single module identifiability are derived and formulated in terms of path-based topological properties of the network models.
GPSP: Graph Partition and Space Projection based Approach for Heterogeneous Network Embedding
Venue: arXiv cs.SI 2018
Year: 2018

In this paper, we propose GPSP, a novel Graph Partition and Space Projection based approach, to learn the representation of a heterogeneous network that consists of multiple types of nodes and links. Concretely, we first partition the heterogeneous network into homogeneous and bipartite subnetworks. Then, the projective relations hidden in bipartite subnetworks are extracted by learning the projective embedding vectors. Finally, we concatenate the projective vectors from bipartite subnetworks with the ones learned from homogeneous subnetworks to form the final representation of the heterogeneous network. Extensive experiments are conducted on a real-life dataset. The results demonstrate that GPSP outperforms the state-of-the-art baselines in two key network mining tasks: node classification and clustering.
Successive Wyner-Ziv Coding for the Binary CEO Problem under Log-Loss
Venue: arXiv cs.IT 2018
Year: 2018

An $l$-link binary CEO problem is considered in this paper. We present a practical encoding and decoding scheme for this problem employing the graph-based codes. A successive coding scheme is proposed for converting an $l$-link binary CEO problem to the $(2l-1)$ single binary Wyner-Ziv (WZ) problems. By using the compound LDGM-LDPC codes, the theoretical bound of each binary WZ is asymptotically achievable. Our proposed decoder successively decodes the received data by employing the well-known Sum-Product (SP) algorithm and leverages them to reconstruct the source. The sum-rate distortion performance of our proposed coding scheme is compared with the theoretical bounds under the logarithmic loss (log-loss) criterion.
Borel Kernels and their Approximation, Categorically
Venue: arXiv cs.LO 2018
Year: 2018

This paper introduces a categorical framework to study the exact and approximate semantics of probabilistic programs. We construct a dagger symmetric monoidal category of Borel kernels where the dagger-structure is given by Bayesian inversion. We show functorial bridges between this category and categories of Banach lattices which formalize the move from kernel-based semantics to predicate transformer (backward) or state transformer (forward) semantics. These bridges are related by natural transformations, and we show in particular that the Radon-Nikodym and Riesz representation theorems - two pillars of probability theory - define natural transformations. With the mathematical infrastructure in place, we present a generic and endogenous approach to approximating kernels on standard Borel spaces which exploits the involutive structure of our category of kernels. The approximation can be formulated in several equivalent ways by using the functorial bridges and natural transformations described above. Finally, we show that for sensible discretization schemes, every Borel kernel can be approximated by kernels on finite spaces, and that these approximations converge for a natural choice of topology. We illustrate the theory by showing two examples of how approximation can effectively be used in practice: Bayesian inference and the Kleene star operation of ProbNetKAT.
Synthesizing Power and Area Efficient Image Processing Pipelines on FPGAs using Customized Bit-widths
Venue: arXiv cs.AR 2018
Year: 2018

High-level synthesis (HLS) has received significant attention in recent years, improving programmability for FPGAs. PolyMage is a domain-specific language (DSL) for image processing pipelines that also has a HLS backend to translate the input DSL into an equivalent circuit that can be synthesized on FPGAs, while leveraging an HLS suite. The data at each stage of a pipeline is stored using a fixed-point data type (alpha,beta) where alpha and beta denote the number of integral and fractional bits. The power and area savings while performing arithmetic operations on fixed-point data type is known to be significant over using floating point. In this paper, we first propose an interval-arithmetic based range analysis (alpha-analysis) algorithm to estimate the number of bits required to store the integral part of the data at each stage of an image processing pipeline. The analysis algorithm uses the homogeneity of pixel signals at each stage to cluster them and perform a combined range analysis. Secondly, we propose a software architecture for easily deploying any kind of interval/affine arithmetic based range analyses in the DSL compiler. Thirdly, we propose a new range analysis technique using Satisfiability Modulo Theory (SMT) solvers, and show that the range estimates obtained through it are very close to the lower bounds obtained through profile-driven analysis.We evaluated our bitwidth analysis algorithms on four image processing benchmarks listed in the order of increasing complexity: Unsharp Mask, Down-Up Sampling, Harris Corner Detection and Horn-Schunck Optical Flow. For example, on Optical Flow, the interval analysis based approach showed an 1.4x and 1.14x improvement on area and power metrics over floating-point representation respectively; whereas the SMT solver based approach showed 2.49x and 1.58x improvement on area and power metrics when compared to interval analysis.
Joint User Association, Power Control and Scheduling in Multi-Cell 5G Networks
Venue: arXiv cs.NI 2018
Year: 2018

-The focus of this paper is targeted towards multi-cell 5G networks which are composed of HPNs (High Power Node) such as evolved NodeBs (HPNs) that control signaling and system broadcasting information and of simplified LPNs (Low Power Node) co-existing in the same operating area and sharing the scare radio resources. Consequently, greater emphasis is given to Inter-Cell Interference Coordination (ICIC) based on multi-resource management techniques that take in particular user association into account. Beside user association to HPNs, this paper takes also power control and scheduling into consideration. This addressed problem is remained largely unsolved, mainly due to its non-convex nature that makes the global optimal solution difficult to obtain. We address the user association challenge according to the two broadly adopted approaches in wireless networks: the network-centric approach where user association is allocated efficiently in a centralized fashion; and the user-centric approach where distributed allocation prevails for reduced complexity. The scheduling and HPNs power allocation are solved in a centralized fashion, in order to reach an optimal solution of the joint optimization problem.
Single cell and multi-cell performance analysis of OFDM index modulation
Venue: arXiv cs.IT 2018
Year: 2018

This paper addresses the achievable rate of single cell and sum rate of multi-cell orthogonal frequency division multiplexing (OFDM) index modulation (IM). The single cell achievable rate of OFDM-IM with Gaussian input is calculated using a multi-ary symmetric channel. Then, the cumulative distribution function (CDF) of multi-cell OFDM-IM is investigated by stochastic geometry. Furthermore, it is proved in this paper that the probability density function (PDF) of noise plus intercell-interference (ICI) in multi-cell OFDM-IM with quadrature amplitude modulation (QAM) follows a mixture of Gaussians (MoG) distribution. Next, parameters of the MoG distribution are estimated using a simplified expectation maximization (EM) algorithm. Upper bound of sum rates of multi-cell OFDM-IM is derived. Furthermore, analytic and simulated results are compared and discussed.
Some binary BCH codes with length $n=2^m+1$
Venue: arXiv cs.IT 2018
Year: 2018

Under research for near sixty years, Bose-$\!$Ray-$\!$Chaudhuri-$\!$Hocquenghem(BCH) codes have played increasingly important roles in many applications such as communication systems, data storage and information security. However, the dimension and minimum distance of BCH codes are seldom solved until now because of their intractable characteristics. The objective of this paper is to study the dimensions of some BCH codes of length $n=2^m+1$ with $m=2t+1$, $4t+2$, $8t+4$ and $m\geq 10$. Some new techniques are employed to investigate coset leaders modulo $n$. For each type of $m$ above, the first five largest coset leaders modulo $n$ are determined, the dimension of some BCH codes of length $n$ with designed distance $δ>2^{\lceil \frac{m}{2} \rceil}$ is presented. These new techniques and results may be helpful to study other families of cyclic codes over finite fields.
A Deep Learning Algorithm for One-step Contour Aware Nuclei Segmentation of Histopathological Images
Venue: arXiv cs.CV 2018
Year: 2018

This paper addresses the task of nuclei segmentation in high-resolution histopathological images. We propose an auto- matic end-to-end deep neural network algorithm for segmenta- tion of individual nuclei. A nucleus-boundary model is introduced to predict nuclei and their boundaries simultaneously using a fully convolutional neural network. Given a color normalized image, the model directly outputs an estimated nuclei map and a boundary map. A simple, fast and parameter-free post-processing procedure is performed on the estimated nuclei map to produce the final segmented nuclei. An overlapped patch extraction and assembling method is also designed for seamless prediction of nuclei in large whole-slide images. We also show the effectiveness of data augmentation methods for nuclei segmentation task. Our experiments showed our method outperforms prior state-of-the- art methods. Moreover, it is efficient that one 1000X1000 image can be segmented in less than 5 seconds. This makes it possible to precisely segment the whole-slide image in acceptable time
Back to the Future: The Case for Reversible Computing
Venue: arXiv cs.ET 2018
Year: 2018

There is one, and only one way, consistent with fundamental physics, that the efficiency of general digital computation can continue increasing indefinitely, and that is to apply the principles of reversible computing. We need to begin intensive development work on this technology soon if we want to maintain advances in computing and the attendant economic growth. NOTE: This paper is an extended author's preprint of the feature article titled "Throwing Computing Into Reverse" (print) or "The Future of Computing Depends on Making it Reversible" (online), published by IEEE Spectrum in Aug.-Sep. 2017. This preprint is based on the original draft manuscript that the author submitted to Spectrum, prior to IEEE edits and feedback from external readers.
The emergent algebraic structure of RNNs and embeddings in NLP
Venue: arXiv cs.CL 2018
Year: 2018

We examine the algebraic and geometric properties of a uni-directional GRU and word embeddings trained end-to-end on a text classification task. A hyperparameter search over word embedding dimension, GRU hidden dimension, and a linear combination of the GRU outputs is performed. We conclude that words naturally embed themselves in a Lie group and that RNNs form a nonlinear representation of the group. Appealing to these results, we propose a novel class of recurrent-like neural networks and a word embedding scheme.