OpenRaiser/Intern-Atlas huggingface dataset:
Empirical Evaluation of a Thread-Safe Dynamic Range Min-Max Tree using HTM
Venue: arXiv cs.DC 2016
Year: 2016

Succinct trees, such as wavelet trees and those based on, for instance, range Min-Max trees (RMMTs), are a family of practical data structures that store information close to their information-theoretic space lower bound. These structures are often static; meaning that once they are built, nodes cannot be added, deleted or modified. This read-only property simplifies concurrency. However, newer versions of these data structures allow for a fair degree of dynamism. Parallel programming using Hardware Transactional Memory(HTM), has been available in mainstream microprocessors since a few years ago. One limitation of HTM is still on the size of each transaction. This is why HTM's use, for the moment, is limited to operations that involve few memory addresses that need to be updated atomically, or where the level of concurrency is low. We provide the first available implementation of a concurrent, dynamic RMMT based on HTM, and we compare empirically how well HTM performs compared to a naive implementation using locks. We have shown that because of the formal properties of RMMTs, HTM is a good fit for adding concurrency to otherwise slow lock-based alternatives. We have also shown that HTM performs better than locks when the number of write operations increase, making it a practical structure to use in several write-intensive contexts. This is, as far as we know, the only practical implementation of RMMTs thoroughly tested using HTM.
Distributed Iterative Learning Control for a Team of Quadrotors
Venue: arXiv cs.RO 2016
Year: 2016

The goal of this work is to enable a team of quadrotors to learn how to accurately track a desired trajectory while holding a given formation. We solve this problem in a distributed manner, where each vehicle has only access to the information of its neighbors. The desired trajectory is only available to one (or few) vehicles. We present a distributed iterative learning control (ILC) approach where each vehicle learns from the experience of its own and its neighbors' previous task repetitions, and adapts its feedforward input to improve performance. Existing algorithms are extended in theory to make them more applicable to real-world experiments. In particular, we prove stability for any causal learning function with gains chosen according to a simple scalar condition. Previous proofs were restricted to a specific learning function that only depends on the tracking error derivative (D-type ILC). Our extension provides more degrees of freedom in the ILC design and, as a result, better performance can be achieved. We also show that stability is not affected by a linear dynamic coupling between neighbors. This allows us to use an additional consensus feedback controller to compensate for non-repetitive disturbances. Experiments with two quadrotors attest the effectiveness of the proposed distributed multi-agent ILC approach. This is the first work to show distributed ILC in experiment.
Online Distributed Scheduling on a Fault-prone Parallel System
Venue: arXiv cs.DC 2016
Year: 2016

We consider a parallel system of $m$ identical machines prone to unpredictable crashes and restarts, trying to cope with the continuous arrival of tasks to be executed. Tasks have different computational requirements (i.e., processing time or size). The flow of tasks, their size, and the crash and restart of the machines are assumed to be controlled by an adversary. Then, we focus on the study of online distributed algorithms for the efficient scheduling of the tasks. We use competitive analysis, considering as efficiency metric the completed-load, i.e., the aggregated size of the completed tasks. We first present optimal completed-load competitiveness algorithms when the number of different task sizes that can be injected by the adversary is bounded. (It is known that, if it is not bounded, competitiveness is not achievable.) We first consider only two different task sizes, and then proceed to $k$ different ones, showing in both cases that the optimal completed-load competitiveness can be achieved. Then, we consider the possibility of having some form of resource augmentation, allowing the scheduling algorithm to run with a speedup $s \geq 1$. In this case, we show that the competitiveness of all work-conserving scheduling algorithms can be increased by using a large enough speedup.
Parameterized vertex deletion problems for hereditary graph classes with a block property
Venue: arXiv cs.DS 2016
Year: 2016

For a class of graphs $\mathcal{P}$, the Bounded $\mathcal{P}$-Block Vertex Deletion problem asks, given a graph $G$ on $n$ vertices and positive integers $k$ and $d$, whether there is a set $S$ of at most $k$ vertices such that each block of $G-S$ has at most $d$ vertices and is in $\mathcal{P}$. We show that when $\mathcal{P}$ satisfies a natural hereditary property and is recognizable in polynomial time, Bounded $\mathcal{P}$-Block Vertex Deletion can be solved in time $2^{O(k \log d)}n^{O(1)}$. When $\mathcal{P}$ contains all split graphs, we show that this running time is essentially optimal unless the Exponential Time Hypothesis fails. On the other hand, if $\mathcal{P}$ consists of only complete graphs, or only cycle graphs and $K_2$, then Bounded $\mathcal{P}$-Block Vertex Deletion admits a $c^{k}n^{O(1)}$-time algorithm for some constant $c$ independent of $d$. We also show that Bounded $\mathcal{P}$-Block Vertex Deletion admits a kernel with $O(k^2 d^7)$ vertices.
Model Comparison of a Data-Driven and a Physical Model for Simulating HVAC Systems
Venue: arXiv cs.SY 2016
Year: 2016

Commercial buildings are responsible for a large fraction of energy consumption in developed countries, and therefore are targets of energy efficiency programs. Motivated by the large inherent thermal inertia of buildings, the power consumption can be flexibly scheduled without compromising occupant comfort. This temporal flexibility offers opportunities for the provision of frequency regulation to support grid stability. To realize energy savings and frequency regulation, it is of prime importance to identify a realistic model for the temperature dynamics of a building. We identify a low- dimensional data-driven model and a high-dimensional physics- based model for different spatial granularities and temporal seasons based on a case study of an entire floor of Sutardja Dai Hall, an office building on the University of California, Berkeley campus. A comparison of these contrasting models shows that, despite the higher forecasting accuracy of the physics-based model, both models perform almost equally well for energy efficient control. We conclude that the data-driven model is more amenable to controller design due to its low complexity, and could serve as a substitution for highly complex physics- based models with an insignificant loss of prediction accuracy for many applications. On the other hand, our physics-based approach is more suitable for modeling buildings with finer spatial granularities.
A pairwise approach to simultaneous onset/offset detection for singing voice using correntropy
Venue: arXiv cs.SD 2016
Year: 2016

In this paper, we propose a novelmethod to search for precise locations of paired note onset and offset in a singing voice signal. In comparison with the existing onset detection algorithms,our approach differs in two key respects. First, we employ Correntropy, a generalized correlation function inspired from Reyni's entropy, as a detection function to capture the instantaneous flux while preserving insensitiveness to outliers. Next, a novel peak picking algorithm is specially designed for this detection function. By calculating the fitness of a pre-defined inverse hyperbolic kernel to a detection function, it is possible to find an onset and its corresponding offset simultaneously. Experimental results show that the proposed method achieves performance significantly better than or comparable to other state-of-the-art techniques for onset detection in singing voice.
Geometric Hitting Set for Segments of Few Orientations
Venue: arXiv cs.CG 2016
Year: 2016

We study several natural instances of the geometric hitting set problem for input consisting of sets of line segments (and rays, lines) having a small number of distinct slopes. These problems model path monitoring (e.g., on road networks) using the fewest sensors (the "hitting points"). We give approximation algorithms for cases including (i) lines of 3 slopes in the plane, (ii) vertical lines and horizontal segments, (iii) pairs of horizontal/vertical segments. We give hardness and hardness of approximation results for these problems. We prove that the hitting set problem for vertical lines and horizontal rays is polynomially solvable.
Modelling Temporal Information Using Discrete Fourier Transform for Video Classification
Venue: arXiv cs.CV 2016
Year: 2016

Recently, video classification attracts intensive research efforts. However, most existing works are based on framelevel visual features, which might fail to model the temporal information, e.g. characteristics accumulated along time. In order to capture video temporal information, we propose to analyse features in frequency domain transformed by discrete Fourier transform (DFT features). Frame-level features are firstly extract by a pre-trained deep convolutional neural network (CNN). Then, time domain features are transformed and interpolated into DFT features. CNN and DFT features are further encoded by using different pooling methods and fused for video classification. In this way, static image features extracted from a pre-trained deep CNN and temporal information represented by DFT features are jointly considered for video classification. We test our method for video emotion classification and action recognition. Experimental results demonstrate that combining DFT features can effectively capture temporal information and therefore improve the performance of both video emotion classification and action recognition. Our approach has achieved a state-of-the-art performance on the largest video emotion dataset (VideoEmotion-8 dataset) and competitive results on UCF-101.
Multidimensional Predicates for Prolog
Venue: arXiv cs.PL 2016
Year: 2016

In 2014, Ungar et al. proposed Korz, a new computational model for structuring adaptive (object-oriented) systems. Korz combines implicit parameters and multiple dispatch to structure the behavior of objects in a multidimensional space. Korz is a simple yet expressive model which does not require special programming techniques such as the Visitor or Strategy pattern to accommodate a system for emerging contextual requirements. We show how the ideas of Korz can be integrated in a Prolog system by extending its syntax and semantics with simple meta-programming techniques. We developed a library, called mdp (multidimensional predicates) which can be used to experiment with multidimensional Prolog systems. We highlight its benefits with numerous scenarios such as printing debugging information, memoization, object-oriented programming and adaptive GUIs. In particular, we point out that we can structure and extend Prolog programs with additional concerns in a clear and concise manner. We also demonstrate how Prolog's unique meta-programming capabilities allow for quick experimentation with syntactical and semantical enhancement of the new, multidimensional model. While there are many open concerns, such as efficiency and comprehensibility in the case of larger systems, we will see that we can use the leverage of mdp and Prolog to explore new horizons in the design of adaptive systems.
Appearance Harmonization for Single Image Shadow Removal
Venue: arXiv cs.CV 2016
Year: 2016

Shadows often create unwanted artifacts in photographs, and removing them can be very challenging. Previous shadow removal methods often produce de-shadowed regions that are visually inconsistent with the rest of the image. In this work we propose a fully automatic shadow region harmonization approach that improves the appearance compatibility of the de-shadowed region as typically produced by previous methods. It is based on a shadow-guided patch-based image synthesis approach that reconstructs the shadow region using patches sampled from non-shadowed regions. The result is then refined based on the reconstruction confidence to handle unique image patterns. Many shadow removal results and comparisons are show the effectiveness of our improvement. Quantitative evaluation on a benchmark dataset suggests that our automatic shadow harmonization approach effectively improves upon the state-of-the-art.
Deep Learning in Bioinformatics
Venue: arXiv cs.LG 2016
Year: 2016

In the era of big data, transformation of biomedical big data into valuable knowledge has been one of the most important challenges in bioinformatics. Deep learning has advanced rapidly since the early 2000s and now demonstrates state-of-the-art performance in various fields. Accordingly, application of deep learning in bioinformatics to gain insight from data has been emphasized in both academia and industry. Here, we review deep learning in bioinformatics, presenting examples of current research. To provide a useful and comprehensive perspective, we categorize research both by the bioinformatics domain (i.e., omics, biomedical imaging, biomedical signal processing) and deep learning architecture (i.e., deep neural networks, convolutional neural networks, recurrent neural networks, emergent architectures) and present brief descriptions of each study. Additionally, we discuss theoretical and practical issues of deep learning in bioinformatics and suggest future research directions. We believe that this review will provide valuable insights and serve as a starting point for researchers to apply deep learning approaches in their bioinformatics studies.
Remote Antenna Unit Selection Assisted Seamless Handover for High-Speed Railway Communications with Distributed Antennas
Venue: arXiv cs.NI 2016
Year: 2016

To attain seamless handover and reduce the han- dover failure probability for high-speed railway (HSR) com- munication systems, this paper proposes a remote antenna unit (RAU) selection assisted handover scheme where two antennas are installed on high speed train (HST) and distributed antenna system (DAS) cell architecture on ground is adopted. The RAU selection is used to provide high quality received signals for trains moving in DAS cells and the two HST antennas are employed on trains to realize seamless handover. Moreover, to efficiently evaluate the system performance, a new met- ric termed as handover occurrence probability is defined for describing the relation between handover occurrence position and handover failure probability. We then analyze the received signal strength, the handover trigger probability, the handover occurrence probability, the handover failure probability and the communication interruption probability. Numerical results are provided to compare our proposed scheme with the current existing ones. It is shown that our proposed scheme achieves better performances in terms of handover failure probability and communication interruption probability.
Energy-Aware Cooperative Wireless Networks with Multiple Cognitive Users
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we study and analyze cooperative cognitive radio networks with arbitrary number of secondary users (SUs). Each SU is considered a prospective relay for the primary user (PU) besides having its own data transmission demand. We consider a multi-packet transmission framework which allows multiple SUs to transmit simultaneously thanks to dirty-paper coding. We propose power allocation and scheduling policies that optimize the throughput for both PU and SU with minimum energy expenditure. The performance of the system is evaluated in terms of throughput and delay under different opportunistic relay selection policies. Towards this objective, we present a mathematical framework for deriving stability conditions for all queues in the system. Consequently, the throughput of both primary and secondary links is quantified. Furthermore, a moment generating function (MGF) approach is employed to derive a closed-form expression for the average delay encountered by the PU packets. Results reveal that we achieve better performance in terms of throughput and delay at lower energy cost as compared to equal power allocation schemes proposed earlier in literature. Extensive simulations are conducted to validate our theoretical findings.
Variational Autoencoders for Feature Detection of Magnetic Resonance Imaging Data
Venue: arXiv cs.LG 2016
Year: 2016

Independent component analysis (ICA), as an approach to the blind source-separation (BSS) problem, has become the de-facto standard in many medical imaging settings. Despite successes and a large ongoing research effort, the limitation of ICA to square linear transformations have not been overcome, so that general INFOMAX is still far from being realized. As an alternative, we present feature analysis in medical imaging as a problem solved by Helmholtz machines, which include dimensionality reduction and reconstruction of the raw data under the same objective, and which recently have overcome major difficulties in inference and learning with deep and nonlinear configurations. We demonstrate one approach to training Helmholtz machines, variational auto-encoders (VAE), as a viable approach toward feature extraction with magnetic resonance imaging (MRI) data.
A proof of security for a key-policy RS-ABE scheme
Venue: arXiv cs.CR 2016
Year: 2016

A revocable-storage attribute-based encryption (RS-ABE) scheme is an encryption scheme which extends attribute-based encryption by intro- ducing user revocation. A key-policy RS-ABE scheme links each key to an access structure. We propose a new key-policy RS-ABE scheme whose security we prove in term of indistinguishability under a chosen-plaintext attack (IND-CPA).
Implementation of a FPGA-Based Feature Detection and Networking System for Real-time Traffic Monitoring
Venue: arXiv cs.CV 2016
Year: 2016

With the growing demand of real-time traffic monitoring nowadays, software-based image processing can hardly meet the real-time data processing requirement due to the serial data processing nature. In this paper, the implementation of a hardware-based feature detection and networking system prototype for real-time traffic monitoring as well as data transmission is presented. The hardware architecture of the proposed system is mainly composed of three parts: data collection, feature detection, and data transmission. Overall, the presented prototype can tolerate a high data rate of about 60 frames per second. By integrating the feature detection and data transmission functions, the presented system can be further developed for various VANET application scenarios to improve road safety and traffic efficiency. For example, detection of vehicles that violate traffic rules, parking enforcement, etc.
A Self-Paced Regularization Framework for Multi-Label Learning
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we propose a novel multi-label learning framework, called Multi-Label Self-Paced Learning (MLSPL), in an attempt to incorporate the self-paced learning strategy into multi-label learning regime. In light of the benefits of adopting the easy-to-hard strategy proposed by self-paced learning, the devised MLSPL aims to learn multiple labels jointly by gradually including label learning tasks and instances into model training from the easy to the hard. We first introduce a self-paced function as a regularizer in the multi-label learning formulation, so as to simultaneously rank priorities of the label learning tasks and the instances in each learning iteration. Considering that different multi-label learning scenarios often need different self-paced schemes during optimization, we thus propose a general way to find the desired self-paced functions. Experimental results on three benchmark datasets suggest the state-of-the-art performance of our approach.
Doubly Random Parallel Stochastic Methods for Large Scale Learning
Venue: arXiv cs.LG 2016
Year: 2016

We consider learning problems over training sets in which both, the number of training examples and the dimension of the feature vectors, are large. To solve these problems we propose the random parallel stochastic algorithm (RAPSA). We call the algorithm random parallel because it utilizes multiple processors to operate in a randomly chosen subset of blocks of the feature vector. We call the algorithm parallel stochastic because processors choose elements of the training set randomly and independently. Algorithms that are parallel in either of these dimensions exist, but RAPSA is the first attempt at a methodology that is parallel in both, the selection of blocks and the selection of elements of the training set. In RAPSA, processors utilize the randomly chosen functions to compute the stochastic gradient component associated with a randomly chosen block. The technical contribution of this paper is to show that this minimally coordinated algorithm converges to the optimal classifier when the training objective is convex. In particular, we show that: (i) When using decreasing stepsizes, RAPSA converges almost surely over the random choice of blocks and functions. (ii) When using constant stepsizes, convergence is to a neighborhood of optimality with a rate that is linear in expectation. RAPSA is numerically evaluated on the MNIST digit recognition problem.
On The Capacity Of Noisy Computations
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents an analysis of the concept of capacity for noisy com- putations, i.e. functions implemented by unreliable or random devices. An information theoretic model of noisy computation of a perfect function f (measurable function between sequence spaces) thanks to an unreliable device (random channel) F is given: a noisy computation is a product fxF of channels. A model of reliable computation based on input encoding and output decoding is also proposed. These models extend those of noisy communication channel and of reliable communication through a noisy channel. The capacity of a noisy computation is defined and justified by a coding theorem and a converse. Under some constraints on the encoding process, capacity is the upper bound of input rates allowing reliable computation, i.e. decodability of noisy outputs into expected outputs. These results hold when the one-sided random processes under concern are asymptotic mean stationary (AMS) and ergodic. In addition, some characterizations of AMS and ergodic noisy computations are given based on stability properties of the perfect function f and of the random channel F. These results are derived from the more general framework of channel products. Finally, a way to apply the noisy and reliable computation models to cases where the perfect function f is defined according to a formal computational model is proposed.
A Report on Shape Deformation with a Stretching and Bending Energy
Venue: arXiv cs.GR 2016
Year: 2016

In this report we describe a mesh editing system that we implemented that uses a natural stretching and bending energy defined over smooth surfaces. As such, this energy behaves uniformly under various mesh resolutions. All of the elements of our approach already exist in the literature. We hope that our discussions of these energies helps to shed light on the behaviors of these methods and provides a unified discussion of these methods.