OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Assumptions for Synthesis
Venue: arXiv cs.LO 2016
Year: 2016

Controller synthesis is the process of constructing a correct system automatically from its specification. This often requires assumptions about the behaviour of the environment. It is difficult for the designer to identify the assumptions that ensures the existence of a correct controller, and doing so manually can lead to assumptions that are stronger than necessary. As a consequence the generated controllers are suboptimal in terms of generality and robustness. In this work, given a specification, we identify the weakest assumptions that ensures the existence of a controller. We also consider two important classes of assumptions: the ones that can be ensured by the environment and assumptions that speaks only about inputs of the systems. We show that optimal assumptions correspond to strongly winning strategies, admissible strategies and remorsefree strategies respectively. Based on this correspondence, we propose an algorithm for computing optimal assumptions that can be ensured by the environment.
An Unbiased Data Collection and Content Exploitation/Exploration Strategy for Personalization
Venue: arXiv cs.IR 2016
Year: 2016

One of missions for personalization systems and recommender systems is to show content items according to users' personal interests. In order to achieve such goal, these systems are learning user interests over time and trying to present content items tailoring to user profiles. Recommending items according to users' preferences has been investigated extensively in the past few years, mainly thanks for the popularity of Netflix competition. In a real setting, users may be attracted by a subset of those items and interact with them, only leaving partial feedbacks to the system to learn in the next cycle, which leads to significant biases into systems and hence results in a situation where user engagement metrics cannot be improved over time. The problem is not just for one component of the system. The data collected from users is usually used in many different tasks, including learning ranking functions, building user profiles and constructing content classifiers. Once the data is biased, all these downstream use cases would be impacted as well. Therefore, it would be beneficial to gather unbiased data through user interactions. Traditionally, unbiased data collection is done through showing items uniformly sampling from the content pool. However, this simple scheme is not feasible as it risks user engagement metrics and it takes long time to gather user feedbacks. In this paper, we introduce a user-friendly unbiased data collection framework, by utilizing methods developed in the exploitation and exploration literature. We discuss how the framework is different from normal multi-armed bandit problems and why such method is needed. We layout a novel Thompson sampling for Bernoulli ranked-list to effectively balance user experiences and data collection. The proposed method is validated from a real bucket test and we show strong results comparing to old algorithms
Shannon Capacity of Signal Transduction for Multiple Independent Receptors
Venue: arXiv cs.IT 2016
Year: 2016

Cyclic adenosine monophosphate (cAMP) is considered a model system for signal transduction, the mechanism by which cells exchange chemical messages. Our previous work calculated the Shannon capacity of a single cAMP receptor; however, a typical cell may have thousands of receptors operating in parallel. In this paper, we calculate the capacity of a cAMP signal transduction system with an arbitrary number of independent, indistinguishable receptors. By leveraging prior results on feedback capacity for a single receptor, we show (somewhat unexpectedly) that the capacity is achieved by an IID input distribution, and that the capacity for n receptors is n times the capacity for a single receptor.
Toward a Science of Autonomy for Physical Systems: Construction
Venue: arXiv cs.CY 2016
Year: 2016

Today, ensuring and improving safety, productivity, quality, and sustainability in construction, operation, and maintenance of national civil infrastructure systems through advances in robotics and automation is a national imperative. By "national civil infrastructure" we refer to the 4.5M commercial buildings, 3.9M miles of public roads, 2M miles of oil and natural gas pipelines, 600K bridges, 190K cell phone towers, 120K miles of major railroads, 100K miles of levees, 84K dams, 50K miles of electrical power lines, 25K miles of commercially navigable waterways, and 5K public-use airports in the United States, all of which are critical to our national economy and society. By "ensuring and improving safety, productivity, quality, and sustainability" we mean to guarantee performance across the entire life cycle of civil infrastructure, from construction to operation and from maintenance to disposal. By "advances in robotics and automation" we mean innovative research and education that will provide tools for systematic and timely execution of construction, and also collection, analysis, visualization, and operational use of big data in built environments for project monitoring and control purposes. In the following, we discuss the current state of construction and operation of the national civil infrastructure systems in detail and present several opportunities for improvements through research and education on robotics and automation.
BoxLib with Tiling: An AMR Software Framework
Venue: arXiv cs.MS 2016
Year: 2016

In this paper we introduce a block-structured adaptive mesh refinement (AMR) software framework that incorporates tiling, a well-known loop transformation. Because the multiscale, multiphysics codes built in BoxLib are designed to solve complex systems at high resolution, performance on current and next generation architectures is essential. With the expectation of many more cores per node on next generation architectures, the ability to effectively utilize threads within a node is essential, and the current model for parallelization will not be sufficient. We describe a new version of BoxLib in which the tiling constructs are embedded so that BoxLib-based applications can easily realize expected performance gains without extra effort on the part of the application developer. We also discuss a path forward to enable future versions of BoxLib to take advantage of NUMA-aware optimizations using the TiDA portable library.
Distributed Cooperative Detection for Multi-Receiver Molecular Communication
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, a cooperative diffusion-based molecular communication system is considered where distributed receivers collaboratively determine a transmitter's signal. In this system, the receivers first make local hard decisions about the current transmitted bit and then report these decisions to a fusion center (FC). The FC combines the local hard decisions to make a global decision using an N-out-of-K fusion rule. Asymmetric and symmetric topologies are considered and for each topology, two reporting scenarios, namely, perfect reporting and noisy reporting, are addressed. Closed-form analytical expressions for the expected global error probability are derived for all considered topologies and scenarios. Numerical and simulation results show that system reliability can be greatly improved by combining the detection information of distributed receivers.
Matrix-Product Complementary dual Codes
Venue: arXiv cs.IT 2016
Year: 2016

Linear complementary dual codes (LCD) are linear codes satisfying $C\cap C^{\perp}=\{0\}$. Under suitable conditions, matrix-product codes that are complementary dual codes are characterized. We construct LCD codes using quasi-orthogonal matrices. Some asymptotic results are derived.
Approximate Agreement under Mobile Byzantine Faults
Venue: arXiv cs.DC 2016
Year: 2016

In this paper we address Approximate Agreement problem in the Mobile Byzantine faults model. Our contribution is threefold. First, we propose the the first mapping from the existing variants of Mobile Byzantine models to the Mixed-Mode faults model.This mapping further help us to prove the correctness of class MSR (Mean-Subsequence-Reduce) Approximate Agreement algorithms in the Mobile Byzantine fault model, and is of independent interest. Secondly, we prove lower bounds for solving Approximate Agreement under all existing Mobile Byzantine faults models. Interestingly, these lower bounds are different from the static bounds. Finally, we propose matching upper bounds. Our paper is the first to link the Mobile Byzantine Faults models and the Mixed-Mode Faults models, and we advocate that a similar approach can be adopted in order to prove the correctness of other classical distributed building blocks (e.g. agreement, clock synchronization, interactive consistency etc) under Mobile Byzantine Faults model.
Fundamental Limits of Coded Caching: Improved Delivery Rate-Cache Capacity Trade-off
Venue: arXiv cs.IT 2016
Year: 2016

A centralized coded caching system, consisting of a server delivering N popular files, each of size F bits, to K users through an error-free shared link, is considered. It is assumed that each user is equipped with a local cache memory with capacity MF bits, and contents can be proactively cached into these caches over a low traffic period; however, without the knowledge of the user demands. During the peak traffic period each user requests a single file from the server. The goal is to minimize the number of bits delivered by the server over the shared link, known as the delivery rate, over all user demand combinations. A novel coded caching scheme for the cache capacity of M= (N-1)/K is proposed. It is shown that the proposed scheme achieves a smaller delivery rate than the existing coded caching schemes in the literature when K > N >= 3. Furthermore, we argue that the delivery rate of the proposed scheme is within a constant multiplicative factor of 2 of the optimal delivery rate for cache capacities 1/K <= M <= (N-1)/K, when K > N >= 3.
Optimal Monotone Drawings of Trees
Venue: arXiv cs.DS 2016
Year: 2016

A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists abpath P_{uw} in G that is monotone in some direction l_{uw}. (Namely, the order of the orthogonal projections of the vertices of P_{uw} on l_{uw} is the same as the order they appear in P_{uw}.) The problem of finding monotone drawings for trees has been studied in several recent papers. The main focus is to reduce the size of the drawing. Currently, the smallest drawing size is O(n^{1.205}) x O(n^{1.205}). In this paper, we present an algorithm for constructing monotone drawings of trees on a grid of size at most 12n x 12n. The smaller drawing size is achieved by a new simple Path Draw algorithm, and a procedure that carefully assigns primitive vectors to the paths of the input tree T. We also show that there exists a tree T_0 such that any monotone drawing of T_0 must use a grid of size Omega(n) x Omega(n). So the size of our monotone drawing of trees is asymptotically optimal.
Predicting Lane Keeping Behavior of Visually Distracted Drivers Using Inverse Suboptimal Control
Venue: arXiv cs.SY 2016
Year: 2016

Driver distraction strongly contributes to crash-risk. Therefore, assistance systems that warn the driver if her distraction poses a hazard to road safety, promise a great safety benefit. Current approaches either seek to detect critical situations using environmental sensors or estimate a driver's attention state solely from her behavior. However, this neglects that driving situation, driver deficiencies and compensation strategies altogether determine the risk of an accident. This work proposes to use inverse suboptimal control to predict these aspects in visually distracted lane keeping. In contrast to other approaches, this allows a situation-dependent assessment of the risk posed by distraction. Real traffic data of seven drivers are used for evaluation of the predictive power of our approach. For comparison, a baseline was built using established behavior models. In the evaluation our method achieves a consistently lower prediction error over speed and track-topology variations. Additionally, our approach generalizes better to driving speeds unseen in training phase.
Multi-Source Multi-View Clustering via Discrepancy Penalty
Venue: arXiv cs.LG 2016
Year: 2016

With the advance of technology, entities can be observed in multiple views. Multiple views containing different types of features can be used for clustering. Although multi-view clustering has been successfully applied in many applications, the previous methods usually assume the complete instance mapping between different views. In many real-world applications, information can be gathered from multiple sources, while each source can contain multiple views, which are more cohesive for learning. The views under the same source are usually fully mapped, but they can be very heterogeneous. Moreover, the mappings between different sources are usually incomplete and partially observed, which makes it more difficult to integrate all the views across different sources. In this paper, we propose MMC (Multi-source Multi-view Clustering), which is a framework based on collective spectral clustering with a discrepancy penalty across sources, to tackle these challenges. MMC has several advantages compared with other existing methods. First, MMC can deal with incomplete mapping between sources. Second, it considers the disagreements between sources while treating views in the same source as a cohesive set. Third, MMC also tries to infer the instance similarities across sources to enhance the clustering performance. Extensive experiments conducted on real-world data demonstrate the effectiveness of the proposed approach.
Note on VCG vs. Price Raising for Matching Markets
Venue: arXiv cs.GT 2016
Year: 2016

In \cite{EK10} the use of VCG in matching markets is motivated by saying that in order to compute market clearing prices in a matching market, the auctioneer needs to know the true valuations of the bidders. Hence VCG and corresponding personalized prices are proposed as an incentive compatible mechanism. The same line of argument pops up in several lecture sheets and other documents related to courses based on Easley and Kleinberg's book, seeming to suggest that computing market clearing prices and corresponding assignments were \emph{not} incentive compatible. Main purpose of our note is to observe that, in contrast, assignments based on buyer optimal market clearing prices are indeed incentive compatible.
Note on Optimal Trees for Parallel Hash Functions
Venue: arXiv cs.DC 2016
Year: 2016

A recent work shows how we can optimize a tree based mode of operation for a rate 1 hash function. In particular, an algorithm and a theorem are presented for selecting a good tree topology in order to optimize both the running time and the number of processors at each step of the computation. Because this paper deals only with trees having their leaves at the same depth, the number of saved computing resources is perfectly optimal only for this category of trees. In this note, we address the more general case and describe a simple algorithm which, starting from such a tree topology, reworks it to further reduce the number of processors and the total amount of work done to hash a message.
Zero-Delay Joint Source-Channel Coding in the Presence of Interference Known at the Encoder
Venue: arXiv cs.IT 2016
Year: 2016

Zero-delay transmission of a Gaussian source over an additive white Gaussian noise (AWGN) channel is considered in the presence of an additive Gaussian interference signal. The mean squared error (MSE) distortion is minimized under an average power constraint assuming that the interference signal is known at the transmitter. Optimality of simple linear transmission does not hold in this setting due to the presence of the known interference signal. While the optimal encoder-decoder pair remains an open problem, various non-linear transmission schemes are proposed in this paper. In particular, interference concentration (ICO) and one-dimensional lattice (1DL) strategies, using both uniform and non-uniform quantization of the interference signal, are studied. It is shown that, in contrast to typical scalar quantization of Gaussian sources, a non-uniform quantizer, whose quantization intervals become smaller as we go further from zero, improves the performance. Given that the optimal decoder is the minimum MSE (MMSE) estimator, a necessary condition for the optimality of the encoder is derived, and the numerically optimized encoder (NOE) satisfying this condition is obtained. Based on the numerical results, it is shown that 1DL with non-uniform quantization performs closer (compared to the other schemes) to the numerically optimized encoder while requiring significantly lower complexity.
Invariant feature extraction from event based stimuli
Venue: arXiv cs.CV 2016
Year: 2016

We propose a novel architecture, the event-based GASSOM for learning and extracting invariant representations from event streams originating from neuromorphic vision sensors. The framework is inspired by feed-forward cortical models for visual processing. The model, which is based on the concepts of sparsity and temporal slowness, is able to learn feature extractors that resemble neurons in the primary visual cortex. Layers of units in the proposed model can be cascaded to learn feature extractors with different levels of complexity and selectivity. We explore the applicability of the framework on real world tasks by using the learned network for object recognition. The proposed model achieve higher classification accuracy compared to other state-of-the-art event based processing methods. Our results also demonstrate the generality and robustness of the method, as the recognizers for different data sets and different tasks all used the same set of learned feature detectors, which were trained on data collected independently of the testing data.
High-performance Semantic Segmentation Using Very Deep Fully Convolutional Networks
Venue: arXiv cs.CV 2016
Year: 2016

We propose a method for high-performance semantic image segmentation (or semantic pixel labelling) based on very deep residual networks, which achieves the state-of-the-art performance. A few design factors are carefully considered to this end. We make the following contributions. (i) First, we evaluate different variations of a fully convolutional residual network so as to find the best configuration, including the number of layers, the resolution of feature maps, and the size of field-of-view. Our experiments show that further enlarging the field-of-view and increasing the resolution of feature maps are typically beneficial, which however inevitably leads to a higher demand for GPU memories. To walk around the limitation, we propose a new method to simulate a high resolution network with a low resolution network, which can be applied during training and/or testing. (ii) Second, we propose an online bootstrapping method for training. We demonstrate that online bootstrapping is critically important for achieving good accuracy. (iii) Third we apply the traditional dropout to some of the residual blocks, which further improves the performance. (iv) Finally, our method achieves the currently best mean intersection-over-union 78.3\% on the PASCAL VOC 2012 dataset, as well as on the recent dataset Cityscapes.
Positive Definite Estimation of Large Covariance Matrix Using Generalized Nonconvex Penalties
Venue: arXiv cs.IT 2016
Year: 2016

This work addresses the issue of large covariance matrix estimation in high-dimensional statistical analysis. Recently, improved iterative algorithms with positive-definite guarantee have been developed. However, these algorithms cannot be directly extended to use a nonconvex penalty for sparsity inducing. Generally, a nonconvex penalty has the capability of ameliorating the bias problem of the popular convex lasso penalty, and thus is more advantageous. In this work, we propose a class of positive-definite covariance estimators using generalized nonconvex penalties. We develop a first-order algorithm based on the alternating direction method framework to solve the nonconvex optimization problem efficiently. The convergence of this algorithm has been proved. Further, the statistical properties of the new estimators have been analyzed for generalized nonconvex penalties. Moreover, extension of this algorithm to covariance estimation from sketched measurements has been considered. The performances of the new estimators have been demonstrated by both a simulation study and a gene clustering example for tumor tissues. Code for the proposed estimators is available at https://github.com/FWen/Nonconvex-PDLCE.git.
Signature Design of Sparsely Spread CDMA Based on Superposed Constellation Distance Analysis
Venue: arXiv cs.IT 2016
Year: 2016

Sparsely spread code division multiple access (SCDMA) is a non-orthogonal superposition coding scheme that permits a base station simultaneously communicates with multiple users over a common channel. The detection performance of an SCDMA system is mainly determined by its signature matrix, which should be sparse to guarantee large Euclidean distance for the equivalent signal constellation after spreading and superposition. Good signature matrices that perform well under both belief prorogation and the maximum likelihood detections are designed. The proposed design applies to several similar well-documented schemes, including trellis code multiple access (TCMA), low density spreading, and superposition modulation systems.
The STRANDS Project: Long-Term Autonomy in Everyday Environments
Venue: arXiv cs.RO 2016
Year: 2016

Thanks to the efforts of the robotics and autonomous systems community, robots are becoming ever more capable. There is also an increasing demand from end-users for autonomous service robots that can operate in real environments for extended periods. In the STRANDS project we are tackling this demand head-on by integrating state-of-the-art artificial intelligence and robotics research into mobile service robots, and deploying these systems for long-term installations in security and care environments. Over four deployments, our robots have been operational for a combined duration of 104 days autonomously performing end-user defined tasks, covering 116km in the process. In this article we describe the approach we have used to enable long-term autonomous operation in everyday environments, and how our robots are able to use their long run times to improve their own performance.
Integrating Know-How into the Linked Data Cloud
Venue: arXiv cs.AI 2016
Year: 2016

This paper presents the first framework for integrating procedural knowledge, or "know-how", into the Linked Data Cloud. Know-how available on the Web, such as step-by-step instructions, is largely unstructured and isolated from other sources of online knowledge. To overcome these limitations, we propose extending to procedural knowledge the benefits that Linked Data has already brought to representing, retrieving and reusing declarative knowledge. We describe a framework for representing generic know-how as Linked Data and for automatically acquiring this representation from existing resources on the Web. This system also allows the automatic generation of links between different know-how resources, and between those resources and other online knowledge bases, such as DBpedia. We discuss the results of applying this framework to a real-world scenario and we show how it outperforms existing manual community-driven integration efforts.