OpenRaiser/Intern-Atlas huggingface dataset:
The Packing While Traveling Problem
Venue: arXiv cs.DS 2017
Year: 2017

This paper introduces the Packing While Traveling problem as a new non-linear knapsack problem. Given are a set of cities that have a set of items of distinct profits and weights and a vehicle that may collect the items when visiting all the cities in a fixed order. Each selected item contributes its profit, but produces a transportation cost relative to its weight. The problem asks to find a subset of the items such that the total gain is maximized. We investigate constrained and unconstrained versions of the problem and show that both are NP-hard. We propose a pre-processing scheme that decreases the size of instances making them easier for computation. We provide lower and upper bounds based on mixed-integer programming (MIP) adopting the ideas of piecewise linear approximation. Furthermore, we introduce two exact approaches: one is based on MIP employing linearization technique, and another is a branch-infer-and-bound (BIB) hybrid approach that compounds the upper bound procedure with a constraint programming model strengthened with customized constraints. Our experimental results show the effectiveness of our exact and approximate solutions in terms of solution quality and computational time.
Partial covering arrays for data hiding and quantization
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of finding a set (partial covering array) $S$ of vertices of the Boolean $n$-cube having cardinality $2^{n-k}$ and intersecting with maximum number of $k$-dimensional faces. We prove that the ratio between the numbers of the $k$-faces containing elements of $S$ to $k$-faces is less than $1-\frac{1+o(1)}{\sqrt{2πk}}$ as $n\rightarrow\infty$ for sufficiently large $k$. The solution of the problem in the class of linear codes is found. Connections between this problem, cryptography and an efficiency of quantization are discussed.
How can one sample images with sampling rates close to the theoretical minimum?
Venue: arXiv cs.CV 2017
Year: 2017

A problem is addressed of minimization of the number of measurements needed for digital image acquisition and reconstruction with a given accuracy. A sampling theory based method of image sampling and reconstruction is suggested that allows to draw near the minimal rate of image sampling defined by the sampling theory. Presented and discussed are also results of experimental verification of the method and its possible applicability extensions.
BAMCloud: A Cloud Based Mobile Biometric Authentication Framework
Venue: arXiv cs.DC 2017
Year: 2017

With an exponential increase in number of users switching to mobile banking, various countries are adopting biometric solutions as security measures. The main reason for biometric technologies becoming more common in the everyday lives of consumers is because of the facility to easily capture biometric data in real time, using their mobile phones. Biometric technologies are providing the potential security framework to make banking more convenient and secure than it has ever been. At the same time, the exponential growth of enrollment in the biometric system produces massive amount of high dimensionality data that leads to degradation in the performance of the mobile banking systems. Therefore, in order to overcome the performance issues arising due to this data deluge, this paper aims to propose a distributed mobile biometric system based on a high performance cluster Cloud. High availability, better time efficiency and scalability are some of the added advantages of using the proposed system. In this paper a Cloud based mobile biometric authentication framework (BAMCloud) is proposed that uses dynamic signatures and performs authentication. It includes the steps involving data capture using any handheld mobile device, then storage, preprocessing and training the system in a distributed manner over Cloud. For this purpose we have implemented it using MapReduce on Hadoop platform and for training Levenberg-Marquardt backpropagation neural network has been used. Moreover, the methodology adopted is very novel as it achieves a speedup of 8.5x and a performance of 96.23%. Furthermore, the cost benefit analysis of the implemented system shows that the cost of implementation and execution of the system is lesser than the existing ones. The experiments demonstrate that the better performance is achieved by proposed framework as compared to the other methods used in the recent literature.
Interactive Communication for Data Exchange
Venue: arXiv cs.IT 2017
Year: 2017

Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange which increases the communication size in steps until the task is done. Next, we derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bound of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general sequence such as mixture of IID random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for the IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.
Orthogonal Echo State Networks and stochastic evaluations of likelihoods
Venue: arXiv cs.NE 2017
Year: 2017

We report about probabilistic likelihood estimates that are performed on time series using an echo state network with orthogonal recurrent connectivity. The results from tests using synthetic stochastic input time series with temporal inference indicate that the capability of the network to infer depends on the balance between input strength and recurrent activity. This balance has an influence on the network with regard to the quality of inference from the short term input history versus inference that accounts for influences that date back a long time. Sensitivity of such networks against noise and the finite accuracy of network states in the recurrent layer are investigated. In addition, a measure based on mutual information between the output time series and the reservoir is introduced. Finally, different types of recurrent connectivity are evaluated. Orthogonal matrices show the best results of all investigated connectivity types overall, but also in the way how the network performance scales with the size of the recurrent layer.
Rate Distortion for Lossy In-network Function Computation: Information Dissipation and Sequential Reverse Water-Filling
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of distributed lossy linear function computation in a tree network. We examine two cases: (i) data aggregation (only one sink node computes) and (ii) consensus (all nodes compute the same function). By quantifying the accumulation of information loss in distributed computing, we obtain fundamental limits on network computation rate as a function of incremental distortions (and hence incremental loss of information) along the edges of the network. The above characterization, based on quantifying distortion accumulation, offers an improvement over classical cut-set type techniques which are based on overall distortions instead of incremental distortions. This quantification of information loss qualitatively resembles information dissipation in cascaded channels [1]. Surprisingly, this accumulation effect of distortion happens even at infinite blocklength. Combining this observation with an inequality on the dominance of mean-square quantities over relative-entropy quantities, we obtain outer bounds on the rate distortion function that are tighter than classical cut-set bounds by a difference which can be arbitrarily large in both data aggregation and consensus. We also obtain inner bounds on the optimal rate using random Gaussian coding, which differ from the outer bounds by $\mathcal{O}(\sqrt{D})$, where $D$ is the overall distortion. The obtained inner and outer bounds can provide insights on rate (bit) allocations for both the data aggregation problem and the consensus problem. We show that for tree networks, the rate allocation results have a mathematical structure similar to classical reverse water-filling for parallel Gaussian sources.
Location Games on Networks: Existence and Efficiency of Equilibria
Venue: arXiv cs.GT 2017
Year: 2017

We consider a game where a finite number of retailers choose a location, given that their potential consumers are distributed on a network. Retailers do not compete on price but only on location, therefore each consumer shops at the closest store. We show that when the number of retailers is large enough, the game admits a pure Nash equilibrium and we construct it. We then compare the equilibrium cost borne by the consumers with the cost that could be achieved if the retailers followed the dictate of a benevolent planner. We perform this comparison in term of the price of anarchy, i.e., the ratio of the worst equilibrium cost and the optimal cost, and the price of stability, i.e., the ratio of the best equilibrium cost and the optimal cost. We show that, asymptotically in the number of retailers, these ratios are bounded by two and one, respectively.
Deep Learning For Smile Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Inspired by recent successes of deep learning in computer vision, we propose a novel application of deep convolutional neural networks to facial expression recognition, in particular smile recognition. A smile recognition test accuracy of 99.45% is achieved for the Denver Intensity of Spontaneous Facial Action (DISFA) database, significantly outperforming existing approaches based on hand-crafted features with accuracies ranging from 65.55% to 79.67%. The novelty of this approach includes a comprehensive model selection of the architecture parameters, allowing to find an appropriate architecture for each expression such as smile. This is feasible because all experiments were run on a Tesla K40c GPU, allowing a speedup of factor 10 over traditional computations on a CPU.
Linear Programming Bounds for Entanglement-Assisted Quantum Error-Correcting Codes by Split Weight Enumerators
Venue: arXiv cs.IT 2017
Year: 2017

Linear programming approaches have been applied to derive upper bounds on the size of classical codes and quantum codes. In this paper, we derive similar results for general quantum codes with entanglement assistance, including nonadditive codes, by considering a type of split weight enumerators. After deriving the MacWilliams identities for these split weight enumerators, we are able to prove algebraic linear programming bounds, such as the Singleton bound, the Hamming bound, and the first linear programming bound. In particular, we show that the first linear programming bound improves the Hamming bound when the relative distance is sufficiently large. On the other hand, we obtain additional constraints on the size of Pauli subgroups for quantum codes, which allow us to improve the linear programming bounds on the minimum distance of small quantum codes. In particular, we show that there is no [[27,15,5]] or [[28,14,6]] quantum stabilizer code. We also discuss the existence of some entanglement-assisted quantum stabilizer codes with maximal entanglement. As a result, the upper and lower bounds on the minimum distance of maximal-entanglement quantum stabilizer codes with length up to 20 are significantly improved.
Graph-based Predictable Feature Analysis
Venue: arXiv cs.LG 2017
Year: 2017

We propose graph-based predictable feature analysis (GPFA), a new method for unsupervised learning of predictable features from high-dimensional time series, where high predictability is understood very generically as low variance in the distribution of the next data point given the previous ones. We show how this measure of predictability can be understood in terms of graph embedding as well as how it relates to the information-theoretic measure of predictive information in special cases. We confirm the effectiveness of GPFA on different datasets, comparing it to three existing algorithms with similar objectives---namely slow feature analysis, forecastable component analysis, and predictable feature analysis---to which GPFA shows very competitive results.
Online Ski Rental for ON/OFF Scheduling of Energy Harvesting Base Stations
Venue: arXiv cs.IT 2017
Year: 2017

The co-existence of small cell base stations (SBSs) with conventional macrocell base station is a promising approach to boost the capacity and coverage of cellular networks. However, densifying the network with a viral deployment of SBSs can significantly increase energy consumption. To reduce the reliance on unsustainable energy sources, one can adopt self-powered SBSs that rely solely on energy harvesting. Due to the uncertainty of energy arrival and the finite capacity of energy storage systems, self-powered SBSs must smartly optimize their ON and OFF schedule. In this paper, the problem of ON/OFF scheduling of self-powered SBSs is studied, in the presence of energy harvesting uncertainty with the goal of minimizing the operational costs consisted of energy consumption and transmission delay of a network. For the original problem, we show an algorithm can solve the problem in the illustrative case. To reduce the complexity of the original problem, an approximation is proposed. To solve the approximated problem, a novel approach based on the ski rental framework, a powerful online optimization tool, is proposed. Using this approach, each SBS can effectively decide on its ON/OFF schedule autonomously, without any prior information on future energy arrivals. By using competitive analysis, a deterministic online algorithm (DOA) and a randomized online algorithm (ROA) are developed. ROA is shown to achieve the optimal competitive ratio in the approximation problem. Simulation results show that, compared to a baseline approach, the ROA can yield performance gains reaching up to 15.6% in terms of reduced total energy consumption of SBSs and up to 20.6% in terms of per-SBS network delay reduction. The results shed light on the fundamental aspects that impact the ON time of SBSs while demonstrating that the proposed ROA can reduce up to 69.9% the total cost compared to a baseline approach.
A double oracle approach for minmax regret optimization problems with interval data
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we provide a generic anytime lower bounding procedure for minmax regret optimization problems. We show that the lower bound obtained is always at least as accurate as the lower bound recently proposed by Chassein and Goerigk (2015). This lower bound can be viewed as the optimal value of a linear programming relaxation of a mixed integer programming formulation of minmax regret optimization, but the contribution of the paper is to compute this lower bound via a double oracle algorithm (McMahan et al., 2003) that we specify. The double oracle algorithm is designed by relying on a game theoretic view of robust optimization, similar to the one developed by Mastin et al. (2015), and it can be efficiently implemented for any minmax regret optimization problem whose standard version is "easy". We describe how to efficiently embed this lower bound in a branch and bound procedure. Finally, we apply our approach to the robust shortest path problem. Our numerical results show a significant gain in the computation times compared to previous approaches in the literature.
Recognition of Visually Perceived Compositional Human Actions by Multiple Spatio-Temporal Scales Recurrent Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

The current paper proposes a novel neural network model for recognizing visually perceived human actions. The proposed multiple spatio-temporal scales recurrent neural network (MSTRNN) model is derived by introducing multiple timescale recurrent dynamics to the conventional convolutional neural network model. One of the essential characteristics of the MSTRNN is that its architecture imposes both spatial and temporal constraints simultaneously on the neural activity which vary in multiple scales among different layers. As suggested by the principle of the upward and downward causation, it is assumed that the network can develop meaningful structures such as functional hierarchy by taking advantage of such constraints during the course of learning. To evaluate the characteristics of the model, the current study uses three types of human action video dataset consisting of different types of primitive actions and different levels of compositionality on them. The performance of the MSTRNN in testing with these dataset is compared with the ones by other representative deep learning models used in the field. The analysis of the internal representation obtained through the learning with the dataset clarifies what sorts of functional hierarchy can be developed by extracting the essential compositionality underlying the dataset.
ERBlox: Combining Matching Dependencies with Machine Learning for Entity Resolution
Venue: arXiv cs.DB 2017
Year: 2017

Entity resolution (ER), an important and common data cleaning problem, is about detecting data duplicate representations for the same external entities, and merging them into single representations. Relatively recently, declarative rules called "matching dependencies" (MDs) have been proposed for specifying similarity conditions under which attribute values in database records are merged. In this work we show the process and the benefits of integrating four components of ER: (a) Building a classifier for duplicate/non-duplicate record pairs built using machine learning (ML) techniques; (b) Use of MDs for supporting the blocking phase of ML; (c) Record merging on the basis of the classifier results; and (d) The use of the declarative language "LogiQL" -an extended form of Datalog supported by the "LogicBlox" platform- for all activities related to data processing, and the specification and enforcement of MDs.
Value Iteration Networks
Venue: arXiv cs.AI 2017
Year: 2017

We introduce the value iteration network (VIN): a fully differentiable neural network with a `planning module' embedded within. VINs can learn to plan, and are suitable for predicting outcomes that involve planning-based reasoning, such as policies for reinforcement learning. Key to our approach is a novel differentiable approximation of the value-iteration algorithm, which can be represented as a convolutional neural network, and trained end-to-end using standard backpropagation. We evaluate VIN based policies on discrete and continuous path-planning domains, and on a natural-language based search task. We show that by learning an explicit planning computation, VIN policies generalize better to new, unseen domains.
Medical Concept Representation Learning from Electronic Health Records and its Application on Heart Failure Prediction
Venue: arXiv cs.LG 2017
Year: 2017

Objective: To transform heterogeneous clinical data from electronic health records into clinically meaningful constructed features using data driven method that rely, in part, on temporal relations among data. Materials and Methods: The clinically meaningful representations of medical concepts and patients are the key for health analytic applications. Most of existing approaches directly construct features mapped to raw data (e.g., ICD or CPT codes), or utilize some ontology mapping such as SNOMED codes. However, none of the existing approaches leverage EHR data directly for learning such concept representation. We propose a new way to represent heterogeneous medical concepts (e.g., diagnoses, medications and procedures) based on co-occurrence patterns in longitudinal electronic health records. The intuition behind the method is to map medical concepts that are co-occuring closely in time to similar concept vectors so that their distance will be small. We also derive a simple method to construct patient vectors from the related medical concept vectors. Results: For qualitative evaluation, we study similar medical concepts across diagnosis, medication and procedure. In quantitative evaluation, our proposed representation significantly improves the predictive modeling performance for onset of heart failure (HF), where classification methods (e.g. logistic regression, neural network, support vector machine and K-nearest neighbors) achieve up to 23% improvement in area under the ROC curve (AUC) using this proposed representation. Conclusion: We proposed an effective method for patient and medical concept representation learning. The resulting representation can map relevant concepts together and also improves predictive modeling performance.
Measuring and Maximizing Influence via Random Walk in Social Activity Networks
Venue: arXiv cs.SI 2017
Year: 2017

With the popularity of OSNs, finding a set of most influential users (or nodes) so as to trigger the largest influence cascade is of significance. For example, companies may take advantage of the "word-of-mouth" effect to trigger a large cascade of purchases by offering free samples/discounts to those most influential users. This task is usually modeled as an influence maximization problem, and it has been widely studied in the past decade. However, considering that users in OSNs may participate in various kinds of online activities, e.g., giving ratings to products, joining discussion groups, etc., influence diffusion through online activities becomes even more significant. In this paper, we study the impact of online activities by formulating the influence maximization problem for social-activity networks (SANs) containing both users and online activities. To address the computation challenge, we define an influence centrality via random walks to measure influence, then use the Monte Carlo framework to efficiently estimate the centrality in SANs. Furthermore, we develop a greedy-based algorithm with two novel optimization techniques to find the most influential users. By conducting extensive experiments with real-world datasets, we show our approach is more efficient than the state-of-the-art algorithm IMM[17] when we needs to handle large amount of online activities.
Control-Flow Integrity: Precision, Security, and Performance
Venue: arXiv cs.CR 2017
Year: 2017

Memory corruption errors in C/C++ programs remain the most common source of security vulnerabilities in today's systems. Control-flow hijacking attacks exploit memory corruption vulnerabilities to divert program execution away from the intended control flow. Researchers have spent more than a decade studying and refining defenses based on Control-Flow Integrity (CFI), and this technique is now integrated into several production compilers. However, so far no study has systematically compared the various proposed CFI mechanisms, nor is there any protocol on how to compare such mechanisms. We compare a broad range of CFI mechanisms using a unified nomenclature based on (i) a qualitative discussion of the conceptual security guarantees, (ii) a quantitative security evaluation, and (iii) an empirical evaluation of their performance in the same test environment. For each mechanism, we evaluate (i) protected types of control-flow transfers, (ii) the precision of the protection for forward and backward edges. For open-source compiler-based implementations, we additionally evaluate (iii) the generated equivalence classes and target sets, and (iv) the runtime performance.