OpenRaiser/Intern-Atlas huggingface dataset:
Convolutional Regression for Visual Tracking
Venue: arXiv cs.CV 2016
Year: 2016

Recently, discriminatively learned correlation filters (DCF) has drawn much attention in visual object tracking community. The success of DCF is potentially attributed to the fact that a large amount of samples are utilized to train the ridge regression model and predict the location of object. To solve the regression problem in an efficient way, these samples are all generated by circularly shifting from a search patch. However, these synthetic samples also induce some negative effects which weaken the robustness of DCF based trackers. In this paper, we propose a Convolutional Regression framework for visual tracking (CRT). Instead of learning the linear regression model in a closed form, we try to solve the regression problem by optimizing a one-channel-output convolution layer with Gradient Descent (GD). In particular, the receptive field size of the convolution layer is set to the size of object. Contrary to DCF, it is possible to incorporate all "real" samples clipped from the whole image. A critical issue of the GD approach is that most of the convolutional samples are negative and the contribution of positive samples will be suppressed. To address this problem, we propose a novel Automatic Hard Negative Mining method to eliminate easy negatives and enhance positives. Extensive experiments are conducted on a widely-used benchmark with 100 sequences. The results show that the proposed algorithm achieves outstanding performance and outperforms almost all the existing DCF based algorithms.
Byzantine Processors and Cuckoo Birds: Confining Maliciousness to the Outset
Venue: arXiv cs.DC 2016
Year: 2016

Are there Byzantine Animals? A Fooling Behavior is exhibited by the Cuckoo bird. It sneakily replaces some of the eggs of other species with its own. Lest the Cuckoo extinct itself by destroying its host, it self-limits its power: It does not replace too large a fraction of the eggs. Here, we show that any Byzantine Behavior that does not destroy the system it attacks, i.e. allows the system to solve an easy task like epsilon-agreement, then its maliciousness can be confined to be the exact replica of the Cuckoo bird behavior: Undetectably replace an input of a processor and let the processor behave correctly thereafter with respect to the new input. In doing so we reduce the study of Byzantine behavior to fail-stop (benign) behavior with the Cuckoo caveat of a fraction of the inputs replaced. We establish a complete correspondence between the Byzantine and the Benign, modulo different thresholds, and replaced inputs. This work is yet another step in a line of work unifying seemingly distinct distributed system models, dispelling the Myth that Distributed Computing is a plethora of distinct isolated models, each requiring its specialized tools and ideas in order to determine solvability of tasks. Thus, hereafter, Byzantine Computability questions can be reduced to questions in the benign failure setting. We also show that the known results about correlated faults in the asynchronous benign setting can be imported verbatim to the asynchronous Byzantine setting. Finally, as in the benign case in which we have the property that a processor can output once its faulty behavior stops for long enough, we show this can be done in a similar manner in the Byzantine case. This necessitated the generalization of Reliable Broadcast to what we term Recoverable Reliable Broadcast.
Efficient Web-based Data Imputation with Graph Model
Venue: arXiv cs.DB 2016
Year: 2016

A challenge for data imputation is the lack of knowledge. In this paper, we attempt to address this challenge by involving extra knowledge from web. To achieve high-performance web-based imputation, we use the dependency, i.e.FDs and CFDs, to impute as many as possible values automatically and fill in the other missing values with the minimal access of web, whose cost is relatively large. To make sufficient use of dependencies, We model the dependency set on the data as a graph and perform automatical imputation and keywords generation for web-based imputation based on such graph model. With the generated keywords, we design two algorithms to extract values for imputation from the search results. Extensive experimental results based on real-world data collections show that the proposed approach could impute missing values efficiently and effectively compared to existing approach.
Gray Box Identification of State-Space Models Using Difference of Convex Programming
Venue: arXiv cs.SY 2016
Year: 2016

Gray-box identification is prevalent in modeling physical and networked systems. However, due to the non-convex nature of the gray-box identification problem, good initial parameter estimates are crucial for a successful application. In this paper, a new identification method is proposed by exploiting the low-rank and structured Hankel matrix of impulse response. This identification problem is recasted into a difference-of-convex programming problem, which is then solved by the sequential convex programming approach with the associated initialization obtained by nuclear-norm optimization. The presented method aims to achieve the maximum impulse-response fitting while not requiring additional (non-convex) conditions to secure non-singularity of the similarity transformation relating the given state-space matrices to the gray-box parameterized ones. This overcomes a persistent shortcoming in a number of recent contributions on this topic, and the new method can be applied for the structured state-space realization even if the involved system parameters are unidentifiable. The method can be used both for directly estimating the gray-box parameters and for providing initial parameter estimates for further iterative search in a conventional gray-box identification setup.
Quantifying the Information Leak in Cache Attacks through Symbolic Execution
Venue: arXiv cs.CR 2016
Year: 2016

Cache timing attacks allow attackers to infer the properties of a secret execution by observing cache hits and misses. But how much information can actually leak through such attacks? For a given program, a cache model, and an input, our CHALICE framework leverages symbolic execution to compute the amount of information that can possibly leak through cache attacks. At the core of CHALICE is a novel approach to quantify information leak that can highlight critical cache side-channel leaks on arbitrary binary code. In our evaluation on real-world programs from OpenSSL and Linux GDK libraries, CHALICE effectively quantifies information leaks: For an AES-128 implementation on Linux, for instance, CHALICE finds that a cache attack can leak as much as 127 out of 128 bits of the encryption key.
Possibilistic semantics for a modal KD45 extension of Gödel fuzzy logic
Venue: arXiv cs.LO 2016
Year: 2016

In this paper we provide a simplified semantics for the logic KD45(G), i.e. the many-valued Gödel counterpart of the classical modal logic KD45. More precisely, we characterize KD45(G) as the set of valid formulae of the class of possibilistic Gödel Kripke Frames $\langle W,π\rangle$, where $W$ is a non-empty set of worlds and $π: W \longrightarrow [0, 1]$ is a normalized possibility distribution on $W$.
Detection Performance with Many Antennas Available for Bandwidth-Efficient Uplink Transmission in MU-MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

This paper is concerned with SC/FDE for bandwidth-efficient uplink block transmission, with QAM schemes, in a MU MIMO system. The number of BS receiver antennas is assumed to be large, but not necessarily much larger than the overall number of transmitter antennas jointly using the same time/frequency resource at MT. In this context, we consider several detection techniques and evaluate, in detail, the corresponding detection performances (discussed with the help of selected performance bounds), for a range of values regarding the number of available BS receiver antennas. From our performance results, we conclude that simple linear detection techniques, designed to avoid the need of complex matrix inversions, can lead to unacceptably high error floor levels. However, by combining the use of such simple linear detectors with an appropriate interference cancellation procedure - within an iterative DF technique -, a close approximation to the SIMO MFB performance can be achieved after a few iterations, even for 64-QAM schemes, when the number of BS antennas is, at least, five times higher than the number of antennas which are jointly used at the user terminals.
Intrinsic Geometric Information Transfer Learning on Multiple Graph-Structured Datasets
Venue: arXiv cs.NE 2016
Year: 2016

Graphs provide a powerful means for representing complex interactions between entities. Recently, deep learning approaches are emerging for representing and modeling graph-structured data, although the conventional deep learning methods (such as convolutional neural networks and recurrent neural networks) have mainly focused on grid-structured inputs (image and audio). Leveraged by the capability of representation learning, deep learning based techniques are reporting promising results for graph applications by detecting structural characteristics of graphs in an automated fashion. In this paper, we attempt to advance deep learning for graph-structured data by incorporating another component, transfer learning. By transferring the intrinsic geometric information learned in the source domain, our approach can help us to construct a model for a new but related task in the target domain without collecting new data and without training a new model from scratch. We thoroughly test our approach with large-scale real corpora and confirm the effectiveness of the proposed transfer learning framework for deep learning on graphs. According to our experiments, transfer learning is most effective when the source and target domains bear a high level of structural similarity in their graph representations.
Differentiable Genetic Programming
Venue: arXiv cs.NE 2016
Year: 2016

We introduce the use of high order automatic differentiation, implemented via the algebra of truncated Taylor polynomials, in genetic programming. Using the Cartesian Genetic Programming encoding we obtain a high-order Taylor representation of the program output that is then used to back-propagate errors during learning. The resulting machine learning framework is called differentiable Cartesian Genetic Programming (dCGP). In the context of symbolic regression, dCGP offers a new approach to the long unsolved problem of constant representation in GP expressions. On several problems of increasing complexity we find that dCGP is able to find the exact form of the symbolic expression as well as the constants values. We also demonstrate the use of dCGP to solve a large class of differential equations and to find prime integrals of dynamical systems, presenting, in both cases, results that confirm the efficacy of our approach.
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube
Venue: arXiv cs.DS 2016
Year: 2016

We study distributed protocols for finding all pairs of similar vectors in a large dataset. Our results pertain to a variety of discrete metrics, and we give concrete instantiations for Hamming distance. In particular, we give improved upper bounds on the overhead required for similarity defined by Hamming distance $r>1$ and prove a lower bound showing qualitative optimality of the overhead required for similarity over any Hamming distance $r$. Our main conceptual contribution is a connection between similarity search algorithms and certain graph-theoretic quantities. For our upper bounds, we exhibit a general method for designing one-round protocols using edge-isoperimetric shapes in similarity graphs. For our lower bounds, we define a new combinatorial optimization problem, which can be stated in purely graph-theoretic terms yet also captures the core of the analysis in previous theoretical work on distributed similarity joins. As one of our main technical results, we prove new bounds on distance correlations in subsets of the Hamming cube.
PixelVAE: A Latent Variable Model for Natural Images
Venue: arXiv cs.LG 2016
Year: 2016

Natural image modeling is a landmark challenge of unsupervised learning. Variational Autoencoders (VAEs) learn a useful latent representation and model global structure well but have difficulty capturing small details. PixelCNN models details very well, but lacks a latent code and is difficult to scale for capturing large structures. We present PixelVAE, a VAE model with an autoregressive decoder based on PixelCNN. Our model requires very few expensive autoregressive layers compared to PixelCNN and learns latent codes that are more compressed than a standard VAE while still capturing most non-trivial structure. Finally, we extend our model to a hierarchy of latent variables at different scales. Our model achieves state-of-the-art performance on binarized MNIST, competitive performance on 64x64 ImageNet, and high-quality samples on the LSUN bedrooms dataset.
Partitioning Strategies and Task Allocation for Target-tracking with Multiple Guards in Polygonal Environments
Venue: arXiv cs.RO 2016
Year: 2016

This paper presents an algorithm to deploy a team of {\it free} guards equipped with omni-directional cameras for tracking a bounded speed intruder inside a simply-connected polygonal environment. The proposed algorithm partitions the environment into smaller polygons, and assigns a guard to each partition so that the intruder is visible to at least one guard at all times. Based on the concept of {\it dynamic zones} introduced in this paper, we propose event-triggered strategies for the guards to track the intruder. We show that the number of guards deployed by the algorithm for tracking is strictly less than $\lfloor {\frac{n}{3}} \rfloor$ which is sufficient and sometimes necessary for coverage. We derive an upper bound on the speed of the mobile guard required for successful tracking which depends on the intruder's speed, the road map of the mobile guards, and geometry of the environment. Finally, we extend the aforementioned analysis to orthogonal polygons, and show that the upper bound on the number of guards deployed for tracking is strictly less than $\lfloor {\frac{n}{4}} \rfloor$ which is sufficient and sometimes necessary for the coverage problem.
A Way out of the Odyssey: Analyzing and Combining Recent Insights for LSTMs
Venue: arXiv cs.CL 2016
Year: 2016

LSTMs have become a basic building block for many deep NLP models. In recent years, many improvements and variations have been proposed for deep sequence models in general, and LSTMs in particular. We propose and analyze a series of augmentations and modifications to LSTM networks resulting in improved performance for text classification datasets. We observe compounding improvements on traditional LSTMs using Monte Carlo test-time model averaging, average pooling, and residual connections, along with four other suggested modifications. Our analysis provides a simple, reliable, and high quality baseline model.
Integrated Resource Management in Software Defined Networking, Caching and Computing
Venue: arXiv cs.NI 2016
Year: 2016

Recently, there are significant advances in the areas of networking, caching and computing. Nevertheless, these three important areas have traditionally been addressed separately in the existing research. In this paper, we present a novel framework that integrates networking, caching and computing in a systematic way and enables dynamic orchestration of these three resources to improve the end-to-end system performance and meet the requirements of different applications. Then, we consider the bandwidth, caching and computing resource allocation issue and formulate it as a joint caching/computing strategy and servers selection problem to minimize the combination cost of network usage and energy consumption in the framework. To minimize the combination cost of network usage and energy consumption in the framework, we formulate it as a joint caching/computing strategy and servers selection problem. In addition, we solve the joint caching/computing strategy and servers selection problem using an exhaustive-search algorithm. Simulation results show that our proposed framework significantly outperforms the traditional network without in-network caching/computing in terms of network usage and energy consumption.
S3Pool: Pooling with Stochastic Spatial Sampling
Venue: arXiv cs.LG 2016
Year: 2016

Feature pooling layers (e.g., max pooling) in convolutional neural networks (CNNs) serve the dual purpose of providing increasingly abstract representations as well as yielding computational savings in subsequent convolutional layers. We view the pooling operation in CNNs as a two-step procedure: first, a pooling window (e.g., $2\times 2$) slides over the feature map with stride one which leaves the spatial resolution intact, and second, downsampling is performed by selecting one pixel from each non-overlapping pooling window in an often uniform and deterministic (e.g., top-left) manner. Our starting point in this work is the observation that this regularly spaced downsampling arising from non-overlapping windows, although intuitive from a signal processing perspective (which has the goal of signal reconstruction), is not necessarily optimal for \emph{learning} (where the goal is to generalize). We study this aspect and propose a novel pooling strategy with stochastic spatial sampling (S3Pool), where the regular downsampling is replaced by a more general stochastic version. We observe that this general stochasticity acts as a strong regularizer, and can also be seen as doing implicit data augmentation by introducing distortions in the feature maps. We further introduce a mechanism to control the amount of distortion to suit different datasets and architectures. To demonstrate the effectiveness of the proposed approach, we perform extensive experiments on several popular image classification benchmarks, observing excellent improvements over baseline models. Experimental code is available at https://github.com/Shuangfei/s3pool.
The Effects of Relative Importance of User Constraints in Cloud of Things Resource Discovery: A Case Study
Venue: arXiv cs.AI 2016
Year: 2016

Over the last few years, the number of smart objects connected to the Internet has grown exponentially in comparison to the number of services and applications. The integration between Cloud Computing and Internet of Things, named as Cloud of Things, plays a key role in managing the connected things, their data and services. One of the main challenges in Cloud of Things is the resource discovery of the smart objects and their reuse in different contexts. Most of the existent work uses some kind of multi-criteria decision analysis algorithm to perform the resource discovery, but do not evaluate the impact that the user constraints has in the final solution. In this paper, we analyse the behaviour of the SAW, TOPSIS and VIKOR multi-objective decision analyses algorithms and the impact of user constraints on them. We evaluated the quality of the proposed solutions using the Pareto-optimality concept.
Variable Neighborhood Search Algorithms for the multi-depot dial-a-ride problem with heterogeneous vehicles and users
Venue: arXiv cs.DM 2016
Year: 2016

In this work, a study on Variable Neighborhood Search algorithms for multi-depot dial-a-ride problems is presented. In dial-a-ride problems patients need to be transported from pre-specified pickup locations to pre-specified delivery locations, under different considerations. The addressed problem presents several constraints and features, such as heterogeneous vehicles, distributed in different depots, and heterogeneous patients. The aim is of minimizing the total routing cost, while respecting time-window, ride-time, capacity and route duration constraints. The objective of the study is of determining the best algorithm configuration in terms of initial solution, neighborhood and local search procedures. At this aim, two different procedures for the computation of an initial solution, six different type of neighborhoods and five local search procedures, where only intra-route changes are made, have been considered and compared. We have also evaluated an "adjusting procedure" that aims to produce feasible solutions from infeasible solutions with small constraints violations. The different VNS algorithms have been tested on instances from literature as well as on random instances arising from a real-world healthcare application.
Expected values in percentile indicators
Venue: arXiv cs.DL 2016
Year: 2016

PP(top x%) is the proportion of papers of a unit (e.g. an institution or a group of researchers), which belongs to the x% most frequently cited papers in the corresponding fields and publication years. It has been proposed that x% of papers can be expected which belongs to the x% most frequently cited papers. In this Letter to the Editor we will present the results of an empirical test whether we can really have this expectation and how strong the deviations from the expected values are when many random samples are drawn from the database.
Deep Transfer Learning for Person Re-identification
Venue: arXiv cs.CV 2016
Year: 2016

Person re-identification (Re-ID) poses a unique challenge to deep learning: how to learn a deep model with millions of parameters on a small training set of few or no labels. In this paper, a number of deep transfer learning models are proposed to address the data sparsity problem. First, a deep network architecture is designed which differs from existing deep Re-ID models in that (a) it is more suitable for transferring representations learned from large image classification datasets, and (b) classification loss and verification loss are combined, each of which adopts a different dropout strategy. Second, a two-stepped fine-tuning strategy is developed to transfer knowledge from auxiliary datasets. Third, given an unlabelled Re-ID dataset, a novel unsupervised deep transfer learning model is developed based on co-training. The proposed models outperform the state-of-the-art deep Re-ID models by large margins: we achieve Rank-1 accuracy of 85.4\%, 83.7\% and 56.3\% on CUHK03, Market1501, and VIPeR respectively, whilst on VIPeR, our unsupervised model (45.1\%) beats most supervised models.
A new method to index and store spatio-temporal data
Venue: arXiv cs.DS 2016
Year: 2016

We propose a data structure that stores, in a compressed way, object trajectories, which at the same time, allow to efficiently response queries without the need to decompress the data. We use a data structure, called $k^{2}$-tree, to store the full position of all objects at regular time intervals. For storing the positions of objects between two time instants represented with $k^{2}$-trees, we only encode the relative movements. In order to save space, those relative moments are encoded with only one integer, instead of two (x,y)-coordinates. Moreover, the resulting integers are further compressed with a technique that allows us to manipulate those movements directly in compressed form. In this paper, we show an experimental evaluation of this structure, which shows important savings in space and good response times.
Approximating Wisdom of Crowds using K-RBMs
Venue: arXiv cs.LG 2016
Year: 2016

An important way to make large training sets is to gather noisy labels from crowds of non experts. We propose a method to aggregate noisy labels collected from a crowd of workers or annotators. Eliciting labels is important in tasks such as judging web search quality and rating products. Our method assumes that labels are generated by a probability distribution over items and labels. We formulate the method by drawing parallels between Gaussian Mixture Models (GMMs) and Restricted Boltzmann Machines (RBMs) and show that the problem of vote aggregation can be viewed as one of clustering. We use K-RBMs to perform clustering. We finally show some empirical evaluations over real datasets.