OpenRaiser/Intern-Atlas huggingface dataset:
Information Sources on a Bratteli diagram
Venue: arXiv cs.IT 2016
Year: 2016

A Bratteli diagram is a type of graph in which the vertices are split into finite subsets occupying an infinite sequence of levels, starting with a bottom level and moving to successively higher levels along edges connecting consecutive levels. An information source on a Bratteli diagram consists of a sequence of PMFs on the vertex sets at each level that are compatible under edge transport. By imposing a regularity condition on the Bratteli diagram, we obtain various results for its information sources including ergodic and entropy rate decomposition theorems, a Shannon-Mcmillan-Breiman theorem, and lossless and lossy source coding theorems. Proof methodology exploits the Vershik transformation on the path space of a Bratteli diagram. Some results for finite alphabet stationary sequential information sources are seen to be a special case of the results of this paper.
A Comparative Evaluation of Approximate Probabilistic Simulation and Deep Neural Networks as Accounts of Human Physical Scene Understanding
Venue: arXiv cs.AI 2016
Year: 2016

Humans demonstrate remarkable abilities to predict physical events in complex scenes. Two classes of models for physical scene understanding have recently been proposed: "Intuitive Physics Engines", or IPEs, which posit that people make predictions by running approximate probabilistic simulations in causal mental models similar in nature to video-game physics engines, and memory-based models, which make judgments based on analogies to stored experiences of previously encountered scenes and physical outcomes. Versions of the latter have recently been instantiated in convolutional neural network (CNN) architectures. Here we report four experiments that, to our knowledge, are the first rigorous comparisons of simulation-based and CNN-based models, where both approaches are concretely instantiated in algorithms that can run on raw image inputs and produce as outputs physical judgments such as whether a stack of blocks will fall. Both approaches can achieve super-human accuracy levels and can quantitatively predict human judgments to a similar degree, but only the simulation-based models generalize to novel situations in ways that people do, and are qualitatively consistent with systematic perceptual illusions and judgment asymmetries that people show.
Automatic Handover Control for Distributed Load Balancing in Mobile Communication Network
Venue: arXiv cs.NI 2016
Year: 2016

This paper explains the enhancement of handover processes in GSM networks by using Load balancing algorithms (Round Robin), comparing the results with the real system to determine the improvement percentage.
The lifecycle of provenance metadata and its associated challenges and opportunities
Venue: arXiv cs.DB 2016
Year: 2016

This chapter outlines some of the challenges and opportunities associated with adopting provenance principles and standards in a variety of disciplines, including data publication and reuse, and information sciences.
Latency Optimization for Resource Allocation in Cloud Computing System
Venue: arXiv cs.DC 2016
Year: 2016

Recent studies in different fields of science caused emergence of needs for high performance computing systems like Cloud. A critical issue in design and implementation of such systems is resource allocation which is directly affected by internal and external factors like the number of nodes, geographical distance and communication latencies. Many optimizations took place in resource allocation methods in order to achieve better performance by concentrating on computing, network and energy resources. Communication latencies as a limitation of network resources have always been playing an important role in parallel processing (especially in fine-grained programs). In this paper, we are going to have a survey on the resource allocation issue in Cloud and then do an optimization on common resource allocation method based on the latencies of communications. Due to it, we added a table to Resource Agent (entity that allocates resources to the applicants) to hold the history of previous allocations. Then, a probability matrix was constructed for allocation of resources partially based on the history of latencies. Response time was considered as a metric for evaluation of proposed method. Results indicated the better response time, especially by increasing the number of tasks. Besides, the proposed method is inherently capable for detecting the unavailable resources through measuring the communication latencies. It assists other issues in cloud systems like migration, resource replication and fault tolerance.
Data mining : past present and future - a typical survey on data streams
Venue: arXiv cs.DB 2016
Year: 2016

Data Stream Mining is one of the area gaining lot of practical significance and is progressing at a brisk pace with new methods, methodologies and findings in various applications related to medicine, computer science, bioinformatics and stock market prediction, weather forecast, text, audio and video processing to name a few. Data happens to be the key concern in data mining. With the huge online data generated from several sensors, Internet Relay Chats, Twitter, Face book, Online Bank or ATM Transactions, the concept of dynamically changing data is becoming a key challenge, what we call as data streams. In this paper, we give the algorithm for finding frequent patterns from data streams with a case study and identify the research issues in handling data streams.
Performance Comparison of CP-OFDM and OQAM-OFDM Based WiFi Systems
Venue: arXiv cs.IT 2016
Year: 2016

In this contribution, a direct comparison of the Offset-QAM-OFDM (OQAM-OFDM) and the Cyclic Prefix OFDM (CP-OFDM) scheme is given for an 802.11a based system. Therefore, the chosen algorithms and choices of design are described and evaluated as a whole system in terms of bit and frame error rate (BER/FER) performance as well as spectral efficiency and complexity in the presence of multipath propagation for different modulation orders. The results show that the OQAM-OFDM scheme exhibits similar BER and FER performance at a 24% higher spectral efficiency and achievable throughput at the cost of an up to five times increased computational complexity.
A Fast Lightweight Time-Series Store for IoT Data
Venue: arXiv cs.DB 2016
Year: 2016

With the advent of the Internet-of-Things (IoT), handling large volumes of time-series data has become a growing concern. Data, generated from millions of Internet-connected sensors, will drive new IoT applications and services. A key requirement is the ability to aggregate, preprocess, index, store and analyze data with minimal latency so that time-to-insight can be reduced. In the future, we expect real-time data collection and analysis to be performed both on small devices (e.g., in hubs and appliances) as well in server-based infrastructure. The ability to localize sensitive data to the home, and thus preserve privacy, is a key driver for small-device deployment. In this paper, we present an efficient architecture for time-series data management that provides a high data ingestion rate, while still being sufficiently lightweight that it can be deployed in embedded environments or small virtual machines. Our solution strives to minimize overhead and explores what can be done without complex indexing schemes that typically, for performance reasons, must be held in main memory. We combine a simple in-memory hierarchical index, log-structured store and in-flight sort, with a high-performance data pipeline architecture that is optimized for multicore platforms. We show that our solution is able to handle streaming insertions at over 4 million records per second (on a single x86 server) while still retaining SQL query performance better than or comparable to existing RDBMS.
The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games
Venue: arXiv cs.GT 2016
Year: 2016

We introduce a unifying model to study the impact of worst-case latency deviations in non-atomic selfish routing games. In our model, latencies are subject to (bounded) deviations which are taken into account by the players. The quality deterioration caused by such deviations is assessed by the $\textit{Deviation Ratio}$, i.e., the worst-case ratio of the cost of a Nash flow with respect to deviated latencies and the cost of a Nash flow with respect to the unaltered latencies. This notion is inspired by the $\textit{Price of Risk Aversion}$ recently studied by Nikolova and Stier-Moses. Here we generalize their model and results. In particular, we derive tight bounds on the Deviation Ratio for multi-commodity instances with a common source and arbitrary non-negative and non-decreasing latency functions. These bounds exhibit a linear dependency on the size of the network (besides other parameters). In contrast, we show that for general multi-commodity networks an exponential dependency is inevitable. We also improve recent smoothness results to bound the Price of Risk Aversion.
Derived-term Automata for Extended Weighted Rational Expressions
Venue: arXiv cs.FL 2016
Year: 2016

We present an algorithm to build an automaton from a rational expression. This approach introduces support for extended weighted expressions. Inspired by derived-term based algorithms, its core relies on a different construct, rational expansions. We introduce an inductive algorithm to compute the expansion of an expression from which the automaton follows. This algorithm is independent of the size of the alphabet, and actually even supports infinite alphabets. It can easily be accommodated to generate deterministic (weighted) automata. These constructs are implemented in Vcsn, a free-software platform dedicated to weighted automata and rational expressions.
Rank and select: Another lesson learned
Venue: arXiv cs.DS 2016
Year: 2016

Rank and select queries on bitmaps are essential building bricks of many compressed data structures, including text indexes, membership and range supporting spatial data structures, compressed graphs, and more. Theoretically considered yet in 1980s, these primitives have also been a subject of vivid research concerning their practical incarnations in the last decade. We present a few novel rank/select variants, focusing mostly on speed, obtaining competitive space-time results in the compressed setting. Our findings can be summarized as follows: $(i)$ no single rank/select solution works best on any kind of data (ours are optimized for concatenated bit arrays obtained from wavelet trees for real text datasets), $(ii)$ it pays to efficiently handle blocks consisting of all 0 or all 1 bits, $(iii)$ compressed select does not have to be significantly slower than compressed rank at a comparable memory use.
AVEC 2016 - Depression, Mood, and Emotion Recognition Workshop and Challenge
Venue: arXiv cs.CV 2016
Year: 2016

The Audio/Visual Emotion Challenge and Workshop (AVEC 2016) "Depression, Mood and Emotion" will be the sixth competition event aimed at comparison of multimedia processing and machine learning methods for automatic audio, visual and physiological depression and emotion analysis, with all participants competing under strictly the same conditions. The goal of the Challenge is to provide a common benchmark test set for multi-modal information processing and to bring together the depression and emotion recognition communities, as well as the audio, video and physiological processing communities, to compare the relative merits of the various approaches to depression and emotion recognition under well-defined and strictly comparable conditions and establish to what extent fusion of the approaches is possible and beneficial. This paper presents the challenge guidelines, the common data used, and the performance of the baseline system on the two tasks.
Biobjective Performance Assessment with the COCO Platform
Venue: arXiv cs.NE 2016
Year: 2016

This document details the rationales behind assessing the performance of numerical black-box optimizers on multi-objective problems within the COCO platform and in particular on the biobjective test suite bbob-biobj. The evaluation is based on a hypervolume of all non-dominated solutions in the archive of candidate solutions and measures the runtime until the hypervolume value succeeds prescribed target values.
Rank Ordered Autoencoders
Venue: arXiv cs.LG 2016
Year: 2016

A new method for the unsupervised learning of sparse representations using autoencoders is proposed and implemented by ordering the output of the hidden units by their activation value and progressively reconstructing the input in this order. This can be done efficiently in parallel with the use of cumulative sums and sorting only slightly increasing the computational costs. Minimizing the difference of this progressive reconstruction with respect to the input can be seen as minimizing the number of active output units required for the reconstruction of the input. The model thus learns to reconstruct optimally using the least number of active output units. This leads to high sparsity without the need for extra hyperparameters, the amount of sparsity is instead implicitly learned by minimizing this progressive reconstruction error. Results of the trained model are given for patches of the CIFAR10 dataset, showing rapid convergence of features and extremely sparse output activations while maintaining a minimal reconstruction error and showing extreme robustness to overfitting. Additionally the reconstruction as function of number of active units is presented which shows the autoencoder learns a rank order code over the input where the highest ranked units correspond to the highest decrease in reconstruction error.
Adversarial Diversity and Hard Positive Generation
Venue: arXiv cs.CV 2016
Year: 2016

State-of-the-art deep neural networks suffer from a fundamental problem - they misclassify adversarial examples formed by applying small perturbations to inputs. In this paper, we present a new psychometric perceptual adversarial similarity score (PASS) measure for quantifying adversarial images, introduce the notion of hard positive generation, and use a diverse set of adversarial perturbations - not just the closest ones - for data augmentation. We introduce a novel hot/cold approach for adversarial example generation, which provides multiple possible adversarial perturbations for every single image. The perturbations generated by our novel approach often correspond to semantically meaningful image structures, and allow greater flexibility to scale perturbation-amplitudes, which yields an increased diversity of adversarial images. We present adversarial images on several network topologies and datasets, including LeNet on the MNIST dataset, and GoogLeNet and ResidualNet on the ImageNet dataset. Finally, we demonstrate on LeNet and GoogLeNet that fine-tuning with a diverse set of hard positives improves the robustness of these networks compared to training with prior methods of generating adversarial images.
Non-Gaussian SLAP: Simultaneous Localization and Planning Under Non-Gaussian Uncertainty in Static and Dynamic Environments
Venue: arXiv cs.RO 2016
Year: 2016

Simultaneous Localization and Planning (SLAP) under process and measurement uncertainties is a challenge. It involves solving a stochastic control problem modeled as a Partially Observed Markov Decision Process (POMDP) in a general framework. For a convex environment, we propose an optimization-based open-loop optimal control problem coupled with receding horizon control strategy to plan for high quality trajectories along which the uncertainty of the state localization is reduced while the system reaches to a goal state with minimum control effort. In a static environment with non-convex state constraints, the optimization is modified by defining barrier functions to obtain collision-free paths while maintaining the previous goals. By initializing the optimization with trajectories in different homotopy classes and comparing the resultant costs, we improve the quality of the solution in the presence of action and measurement uncertainties. In dynamic environments with time-varying constraints such as moving obstacles or banned areas, the approach is extended to find collision-free trajectories. In this paper, the underlying spaces are continuous, and beliefs are non-Gaussian. Without obstacles, the optimization is a globally convex problem, while in the presence of obstacles it becomes locally convex. We demonstrate the performance of the method on different scenarios.
Routing with Congestion in Acyclic Digraphs
Venue: arXiv cs.DS 2016
Year: 2016

We study the version of the $k$-disjoint paths problem where $k$ demand pairs $(s_1,t_1)$, $\dots$, $(s_k,t_k)$ are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than $c$ paths. We show that on directed acyclic graphs the problem is solvable in time $n^{O(d)}$ if we allow congestion $k-d$ for $k$ paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time $f(k)n^{o(d/\log d)}$ for any computable function $f$.
Bridging Online and Offline Social Networks: Multiplex Analysis
Venue: arXiv cs.SI 2016
Year: 2016

We show that three basic actor characteristics, namely normalized reciprocity, three cycles, and triplets, can be expressed using an unified framework that is based on computing the similarity index between two sets associated with the actor: the set of her/his friends and the set of those considering her/him as a friend. These metrics are extended to multiplex networks and then computed for two friendship networks generated by collecting data from two groups of undergraduate students. We found that in offline communication strong and weak ties are (almost) equally presented, while in online communication weak ties are dominant. Moreover, weak ties are much less reciprocal than strong ties. However, across different layers of the multiplex network reciprocities are preserved, while triads (measured with normalized three cycles and triplets) are not significant.
Context Information Based Initial Cell Search for Millimeter Wave 5G Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

Millimeter wave (mmWave) communication is envisioned as a cornerstone to fulfill the data rate requirements for fifth generation (5G) cellular networks. In mmWave communication, beamforming is considered as a key technology to combat the high path-loss, and unlike in conventional microwave communication, beamforming may be necessary even during initial access/cell search. Among the proposed beamforming schemes for initial cell search, analog beamforming is a power efficient approach but suffers from its inherent search delay during initial access. In this work, we argue that analog beamforming can still be a viable choice when context information about mmWave base stations (BS) is available at the mobile station (MS). We then study how the performance of analog beamforming degrades in case of angular errors in the available context information. Finally, we present an analog beamforming receiver architecture that uses multiple arrays of Phase Shifters and a single RF chain to combat the effect of angular errors, showing that it can achieve the same performance as hybrid beamforming.
Rolex: Resilience-Oriented Language Extensions for Extreme-Scale Systems
Venue: arXiv cs.DC 2016
Year: 2016

Future exascale high-performance computing (HPC) systems will be constructed from VLSI devices that will be less reliable than those used today, and faults will become the norm, not the exception. This will pose significant problems for system designers and programmers, who for half-a-century have enjoyed an execution model that assumed correct behavior by the underlying computing system. The mean time to failure (MTTF) of the system scales inversely to the number of components in the system and therefore faults and resultant system level failures will increase, as systems scale in terms of the number of processor cores and memory modules used. However every error detected need not cause catastrophic failure. Many HPC applications are inherently fault resilient. Yet it is the application programmers who have this knowledge but lack mechanisms to convey it to the system. In this paper, we present new Resilience Oriented Language Extensions (Rolex) which facilitate the incorporation of fault resilience as an intrinsic property of the application code. We describe the syntax and semantics of the language extensions as well as the implementation of the supporting compiler infrastructure and runtime system. Our experiments show that an approach that leverages the programmer's insight to reason about the context and significance of faults to the application outcome significantly improves the probability that an application runs to a successful conclusion.
Markov Chain methods for the bipartite Boolean quadratic programming problem
Venue: arXiv cs.DS 2016
Year: 2016

We study the Bipartite Boolean Quadratic Programming Problem (BBQP) which is an extension of the well known Boolean Quadratic Programming Problem (BQP). Applications of the BBQP include mining discrete patterns from binary data, approximating matrices by rank-one binary matrices, computing the cut-norm of a matrix, and solving optimisation problems such as maximum weight biclique, bipartite maximum weight cut, maximum weight induced sub-graph of a bipartite graph, etc. For the BBQP, we first present several algorithmic components, specifically, hill climbers and mutations, and then show how to combine them in a high-performance metaheuristic. Instead of hand-tuning a standard metaheuristic to test the efficiency of the hybrid of the components, we chose to use an automated generation of a multi-component metaheuristic to save human time, and also improve objectivity in the analysis and comparisons of components. For this we designed a new metaheuristic schema which we call Conditional Markov Chain Search (CMCS). We show that CMCS is flexible enough to model several standard metaheuristics; this flexibility is controlled by multiple numeric parameters, and so is convenient for automated generation. We study the configurations revealed by our approach and show that the best of them outperforms the previous state-of-the-art BBQP algorithm by several orders of magnitude. In our experiments we use benchmark instances introduced in the preliminary version of this paper and described here, which have already become the de facto standard in the BBQP literature.
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
Venue: arXiv cs.CR 2016
Year: 2016

"Concentrated differential privacy" was recently introduced by Dwork and Rothblum as a relaxation of differential privacy, which permits sharper analyses of many privacy-preserving computations. We present an alternative formulation of the concept of concentrated differential privacy in terms of the Renyi divergence between the distributions obtained by running an algorithm on neighboring inputs. With this reformulation in hand, we prove sharper quantitative results, establish lower bounds, and raise a few new questions. We also unify this approach with approximate differential privacy by giving an appropriate definition of "approximate concentrated differential privacy."