OpenRaiser/Intern-Atlas huggingface dataset:
Out-of-sample generalizations for supervised manifold learning for classification
Venue: arXiv cs.CV 2015
Year: 2015

Supervised manifold learning methods for data classification map data samples residing in a high-dimensional ambient space to a lower-dimensional domain in a structure-preserving way, while enhancing the separation between different classes in the learned embedding. Most nonlinear supervised manifold learning methods compute the embedding of the manifolds only at the initially available training points, while the generalization of the embedding to novel points, known as the out-of-sample extension problem in manifold learning, becomes especially important in classification applications. In this work, we propose a semi-supervised method for building an interpolation function that provides an out-of-sample extension for general supervised manifold learning algorithms studied in the context of classification. The proposed algorithm computes a radial basis function (RBF) interpolator that minimizes an objective function consisting of the total embedding error of unlabeled test samples, defined as their distance to the embeddings of the manifolds of their own class, as well as a regularization term that controls the smoothness of the interpolation function in a direction-dependent way. The class labels of test data and the interpolation function parameters are estimated jointly with a progressive procedure. Experimental results on face and object images demonstrate the potential of the proposed out-of-sample extension algorithm for the classification of manifold-modeled data sets.
A Distributed Message-Optimal Assignment on Rings
Venue: arXiv cs.DS 2015
Year: 2015

Consider a set of items and a set of $m$ colors, where each item is associated to one color. Consider also $n$ computational agents connected by a ring. Each agent holds a subset of the items and items of the same color can be held by different agents. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent only and (b) the number of different colors assigned to each agent is minimum. Since any color assignment requires the items be distributed according to it (e.g. all items of the same color are to be held by only one agent), we define the cost of a color assignment as the amount of items that need to be moved, given an initial allocation. We first show that any distributed algorithm for this problem requires a message complexity of $Ω(n\cdot m)$ and then we exhibit an optimal message complexity algorithm for synchronous rings that in polynomial time determines a color assignment with cost at most three times the optimal. We also discuss solutions for the asynchronous setting. Finally, we show how to get a better cost solution at the expenses of either the message or the time complexity.
Dear CAV, We Need to Talk About Reproducibility
Venue: arXiv cs.LO 2015
Year: 2015

How many times have you tried to re-implement a past CAV tool paper, and failed? Reliably reproducing published scientific discoveries has been acknowledged as a barrier to scientific progress for some time but there remains only a small subset of software available to support the specific needs of the research community (i.e. beyond generic tools such as source code repositories). In this paper we propose an infrastructure for enabling reproducibility in our community, by automating the build, unit testing and benchmarking of research software.
Structural Decompositions for Problems with Global Constraints
Venue: arXiv cs.AI 2015
Year: 2015

A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or implicitly, by special-purpose algorithms provided by a solver. Such implicitly represented constraints, known as global constraints, are widely used; indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. In recent years, a variety of restrictions on the structure of CSP instances have been shown to yield tractable classes of CSPs. However, most such restrictions fail to guarantee tractability for CSPs with global constraints. We therefore study the applicability of structural restrictions to instances with such constraints. We show that when the number of solutions to a CSP instance is bounded in key parts of the problem, structural restrictions can be used to derive new tractable classes. Furthermore, we show that this result extends to combinations of instances drawn from known tractable classes, as well as to CSP instances where constraints assign costs to satisfying assignments.
Nonlinear Model Predictive Control for Constrained Output Path Following
Venue: arXiv cs.SY 2015
Year: 2015

We consider the tracking of geometric paths in output spaces of nonlinear systems subject to input and state constraints without pre-specified timing requirements. Such problems are commonly referred to as constrained output path-following problems. Specifically, we propose a predictive control approach to constrained path-following problems with and without velocity assignments and provide sufficient convergence conditions based on terminal regions and end penalties. Furthermore, we analyze the geometric nature of constrained output path-following problems and thereby provide insight into the computation of suitable terminal control laws and terminal regions. We draw upon an example from robotics to illustrate our findings.
Kickstarting Choreographic Programming
Venue: arXiv cs.PL 2015
Year: 2015

We present an overview of some recent efforts aimed at the development of Choreographic Programming, a programming paradigm for the production of concurrent software that is guaranteed to be correct by construction from global descriptions of communication behaviour.
Sub-optimality of the Han--Kobayashi Achievable Region for Interference Channels
Venue: arXiv cs.IT 2015
Year: 2015

Han-Kobayashi achievable region is the best known inner bound for a general discrete memoryless interference channel. We show that the capacity region can be strictly larger than the Han-Kobayashi region for some channel realizations, and hence the strict sub-optimality of Han-Kobayashi achievable region.
An investigation into language complexity of World-of-Warcraft game-external texts
Venue: arXiv cs.CL 2015
Year: 2015

We present a language complexity analysis of World of Warcraft (WoW) community texts, which we compare to texts from a general corpus of web English. Results from several complexity types are presented, including lexical diversity, density, readability and syntactic complexity. The language of WoW texts is found to be comparable to the general corpus on some complexity measures, yet more specialized on other measures. Our findings can be used by educators willing to include game-related activities into school curricula.
Learning Reductions that Really Work
Venue: arXiv cs.LG 2015
Year: 2015

We provide a summary of the mathematical and computational techniques that have enabled learning reductions to effectively address a wide class of problems, and show that this approach to solving machine learning problems can be broadly useful.
New Multiple Insertion-Deletion Correcting Codes for Non-Binary Alphabets
Venue: arXiv cs.IT 2015
Year: 2015

We generalize Helberg's number-theoretic construction of multiple insertion-deletion correcting binary codes to non-binary alphabets and describe a linear decoding algorithm for correcting multiple deletions.
Weakly- and Semi-Supervised Learning of a DCNN for Semantic Image Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

Deep convolutional neural networks (DCNNs) trained on a large number of images with strong pixel-level annotations have recently significantly pushed the state-of-art in semantic image segmentation. We study the more challenging problem of learning DCNNs for semantic image segmentation from either (1) weakly annotated training data such as bounding boxes or image-level labels or (2) a combination of few strongly labeled and many weakly labeled images, sourced from one or multiple datasets. We develop Expectation-Maximization (EM) methods for semantic image segmentation model training under these weakly supervised and semi-supervised settings. Extensive experimental evaluation shows that the proposed techniques can learn models delivering competitive results on the challenging PASCAL VOC 2012 image segmentation benchmark, while requiring significantly less annotation effort. We share source code implementing the proposed system at https://bitbucket.org/deeplab/deeplab-public.
System Identification in Dynamical Sampling
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of spatiotemporal sampling in a discrete infinite dimensional spatially invariant evolutionary process $x^{(n)}=A^nx$ to recover an unknown convolution operator $A$ given by a filter $a \in \ell^1(\mathbb{Z})$ and an unknown initial state $x$ modeled as avector in $\ell^2(\mathbb{Z})$. Traditionally, under appropriate hypotheses, any $x$ can be recovered from its samples on $\mathbb{Z}$ and $A$ can be recovered by the classical techniques of deconvolution. In this paper, we will exploit the spatiotemporal correlation and propose a new spatiotemporal sampling scheme to recover $A$ and $x$ that allows to sample the evolving states $x,Ax, \cdots, A^{N-1}x$ on a sub-lattice of $\mathbb{Z}$, and thus achieve the spatiotemporal trade off. The spatiotemporal trade off is motivated by several industrial applications \cite{Lv09}. Specifically, we show that $\{x(m\mathbb{Z}), Ax(m\mathbb{Z}), \cdots, A^{N-1}x(m\mathbb{Z}): N \geq 2m\}$ contains enough information to recover a typical "low pass filter" $a$ and $x$ almost surely, in which we generalize the idea of the finite dimensional case in \cite{AK14}. In particular, we provide an algorithm based on a generalized Prony method for the case when both $a$ and $x$ are of finite impulse response and an upper bound of their support is known. We also perform the perturbation analysis based on the spectral properties of the operator $A$ and initial state $x$, and verify them by several numerical experiments. Finally, we provide several other numerical methods to stabilize the method and numerical example shows the improvement.
A HMAX with LLC for visual recognition
Venue: arXiv cs.CV 2015
Year: 2015

Today's high performance deep artificial neural networks (ANNs) rely heavily on parameter optimization, which is sequential in nature and even with a powerful GPU, would have taken weeks to train them up for solving challenging tasks [22]. HMAX [17] has demonstrated that a simple high performing network could be obtained without heavy optimization. In this paper, we had improved on the existing best HMAX neural network [12] in terms of structural simplicity and performance. Our design replaces the L1 minimization sparse coding (SC) with a locality-constrained linear coding (LLC) [20] which has a lower computational demand. We also put the simple orientation filter bank back into the front layer of the network replacing PCA. Our system's performance has improved over the existing architecture and reached 79.0% on the challenging Caltech-101 [7] dataset, which is state-of-the-art for ANNs (without transfer learning). From our empirical data, the main contributors to our system's performance include an introduction of partial signal whitening, a spot detector, and a spatial pyramid matching (SPM) [14] layer.
Opportunistic and Context-aware Affect Sensing on Smartphones: The Concept, Challenges and Opportunities
Venue: arXiv cs.HC 2015
Year: 2015

Opportunistic affect sensing offers unprecedented potential for capturing spontaneous affect ubiquitously, obviating biases inherent in the laboratory setting. Facial expression and voice are two major affective displays, however most affect sensing systems on smartphone avoid them due to extensive power requirement. Encouragingly, due to the recent advent of low-power DSP (Digital Signal Processing) co-processor and GPU (Graphics Processing Unit) technology, audio and video sensing are becoming more feasible. To properly evaluate opportunistically captured facial expression and voice, contextual information about the dynamic audio-visual stimuli needs to be inferred. This paper discusses recent advances of affect sensing on the smartphone and identifies the key barriers and potential solutions of implementing opportunistic and context-aware affect sensing on smartphone platforms.
An overview on automatic design of robot controllers for complex tasks
Venue: arXiv cs.RO 2015
Year: 2015

In this paper we will explore different available methodologies to automatically design controllers for tasks that spans many level of abstraction, where the gap between primitive behaviours and the task definition is high. A good understanding of your evolutionary setup is needed to choose the correct strategy with which to tackle complex tasks thus we'll first review the most used types of each element composing an evolutionary setup (controllers, objective functions, ect.) then we'll move the focus on the bootstrapping problem and on the different strategies used to overcome it.
Coalgebraic Tools for Bisimilarity and Decorated Trace Semantics
Venue: arXiv cs.LO 2015
Year: 2015

The modelling, specification and study of the semantics of concurrent reactive systems have been interesting research topics for many years now. The aim of this thesis is to exploit the strengths of the (co)algebraic framework in modelling reactive systems and reasoning on several types of associated semantics, in a uniform fashion. In particular, we are interested in handling notions of behavioural equivalence/preorder ranging from bisimilarity for systems that can be represented as non-deterministic coalgebras, to decorated trace semantics for labelled transition systems and probabilistic systems, and testing semantics for labelled transition systems with internal behaviour. Moreover, we aim at deriving a suite of corresponding verification algorithms suitable for implementation in automated tools.
On the Finite Length Scaling of Ternary Polar Codes
Venue: arXiv cs.IT 2015
Year: 2015

The polarization process of polar codes over a ternary alphabet is studied. Recently it has been shown that the scaling of the blocklength of polar codes with prime alphabet size scales polynomially with respect to the inverse of the gap between code rate and channel capacity. However, except for the binary case, the degree of the polynomial in the bound is extremely large. In this work, it is shown that a much lower degree polynomial can be computed numerically for the ternary case. Similar results are conjectured for the general case of prime alphabet size.
A Control-Theoretic Approach to Adaptive Video Streaming in Dense Wireless Networks
Venue: arXiv cs.NI 2015
Year: 2015

Recently, the way people consume video content has been undergoing a dramatic change. Plain TV sets, that have been the center of home entertainment for a long time, are losing grounds to Hybrid TV's, PC's, game consoles, and, more recently, mobile devices such as tablets and smartphones. The new predominant paradigm is: watch what I want, when I want, and where I want. The challenges of this shift are manifold. On the one hand, broadcast technologies such as DVB-T/C/S need to be extended or replaced by mechanisms supporting asynchronous viewing, such as IPTV and video streaming over best-effort networks, while remaining scalable to millions of users. On the other hand, the dramatic increase of wireless data traffic begins to stretch the capabilities of the existing wireless infrastructure to its limits. Finally, there is a challenge to video streaming technologies to cope with a high heterogeneity of end-user devices and dynamically changing network conditions, in particular in wireless and mobile networks. In the present work, our goal is to design an efficient system that supports a high number of unicast streaming sessions in a dense wireless access network. We address this goal by jointly considering the two problems of wireless transmission scheduling and video quality adaptation, using techniques inspired by the robustness and simplicity of Proportional-Integral-Derivative (PID) controllers. We show that the control-theoretic approach allows to efficiently utilize available wireless resources, providing high Quality of Experience (QoE) to a large number of users.
Adaptive Fault Tolerant Execution of Multi-Robot Missions using Behavior Trees
Venue: arXiv cs.RO 2015
Year: 2015

Multi-robot teams offer possibilities of improved performance and fault tolerance, compared to single robot solutions. In this paper, we show how to realize those possibilities when starting from a single robot system controlled by a Behavior Tree (BT). By extending the single robot BT to a multi-robot BT, we are able to combine the fault tolerant properties of the BT, in terms of built-in fallbacks, with the fault tolerance inherent in multi-robot approaches, in terms of a faulty robot being replaced by another one. Furthermore, we improve performance by identifying and taking advantage of the opportunities of parallel task execution, that are present in the single robot BT. Analyzing the proposed approach, we present results regarding how mission performance is affected by minor faults (a robot losing one capability) as well as major faults (a robot losing all its capabilities). Finally, a detailed example is provided to illustrate the approach.
Simple Executions of Snapshot Implementations
Venue: arXiv cs.DC 2015
Year: 2015

The well known snapshot primitive in concurrent programming allows for n-asynchronous processes to write values to an array of single-writer registers and, for each process, to take a snapshot of these registers. In this paper we provide a formulation of the well known linearizability condition for snapshot algorithms in terms of the existence of certain mathematical functions. In addition, we identify a simplifying property of snapshot implementations we call "schedule-based algorithms". This property is natural to assume in the sense that as far as we know, every published snapshot algorithm is schedule-based. Based on this, we prove that when dealing with schedule-based algorithms, it suffices to consider only a small class of very simple executions to prove or disprove correctness in terms of linearizability. We believe that the ideas developed in this paper may help to design automatic verification of snapshot algorithms. Since verifying linearizability was recently proved to be EXPSPACE-complete, focusing on unique objects (snapshot in our case) can potentially lead to designing restricted, but feasible verification methods.
Towards Realizability Checking of Contracts using Theories
Venue: arXiv cs.SE 2015
Year: 2015

Virtual integration techniques focus on building architectural models of systems that can be analyzed early in the design cycle to try to lower cost, reduce risk, and improve quality of complex embedded systems. Given appropriate architectural descriptions and compositional reasoning rules, these techniques can be used to prove important safety properties about the architecture prior to system construction. Such proofs build from "leaf-level" assume/guarantee component contracts through architectural layers towards top-level safety properties. The proofs are built upon the premise that each leaf-level component contract is realizable; i.e., it is possible to construct a component such that for any input allowed by the contract assumptions, there is some output value that the component can produce that satisfies the contract guarantees. Without engineering support it is all too easy to write leaf-level components that can't be realized. Realizability checking for propositional contracts has been well-studied for many years, both for component synthesis and checking correctness of temporal logic requirements. However, checking realizability for contracts involving infinite theories is still an open problem. In this paper, we describe a new approach for checking realizability of contracts involving theories and demonstrate its usefulness on several examples.
LaneQuest: An Accurate and Energy-Efficient Lane Detection System
Venue: arXiv cs.CY 2015
Year: 2015

Current outdoor localization techniques fail to provide the required accuracy for estimating the car's lane. In this paper, we present LaneQuest: a system that leverages the ubiquitous and low-energy inertial sensors available in commodity smart-phones to provide an accurate estimate of the car's current lane. LaneQuest leverages hints from the phone sensors about the surrounding environment to detect the car's lane. For example, a car making a right turn most probably will be in the right-most lane, a car passing by a pothole will be in a specific lane, and the car's angular velocity when driving through a curve reflects its lane. Our investigation shows that there are amble opportunities in the environment, i.e. lane "anchors", that provide cues about the car's lane. To handle the ambiguous location, sensors noise, and fuzzy lane anchors; LaneQuest employs a novel probabilistic lane estimation algorithm. Furthermore, it uses an unsupervised crowd-sourcing approach to learn the position and lane-span distribution of the different lane-level anchors. Our evaluation results from implementation on different android devices and 260Km driving traces by 13 drivers in different cities shows that LaneQuest can detect the different lane-level anchors with an average precision and recall of more than 90%. This leads to an accurate detection of the exact car's lane position 80% of the time, increasing to 89% of the time to within one lane. This comes with a low-energy footprint, allowing LaneQuest to be implemented on the energy-constrained mobile devices.
Multi-Sensor Scheduling for State Estimation with Event-Based, Stochastic Triggers
Venue: arXiv cs.IT 2015
Year: 2015

In networked systems, state estimation is hampered by communication limits. Past approaches, which consider scheduling sensors through deterministic event-triggers, reduce communication and maintain estimation quality. However, these approaches destroy the Gaussian property of the state, making it computationally intractable to obtain an exact minimum mean squared error estimate. We propose a stochastic event-triggered sensor schedule for state estimation which preserves the Gaussianity of the system, extending previous results from the single-sensor to the multi-sensor case.
PowerSpy: Location Tracking using Mobile Device Power Analysis
Venue: arXiv cs.CR 2015
Year: 2015

Modern mobile platforms like Android enable applications to read aggregate power usage on the phone. This information is considered harmless and reading it requires no user permission or notification. We show that by simply reading the phone's aggregate power consumption over a period of a few minutes an application can learn information about the user's location. Aggregate phone power consumption data is extremely noisy due to the multitude of components and applications that simultaneously consume power. Nevertheless, by using machine learning algorithms we are able to successfully infer the phone's location. We discuss several ways in which this privacy leak can be remedied.