OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Dimensional Payment Plan in Fog Computing with Moral Hazard
Venue: arXiv cs.NI 2017
Year: 2017

Recently, the concept of fog computing which aims at providing time-sensitive data services has become popular. In this model, computation is performed at the edge of the network instead of sending vast amounts of data to the cloud. Thus, fog computing provides low latency, location awareness to end users, and improves quality-of-services (QoS). One key feature in this model is the designing of payment plan from network operator (NO) to fog nodes (FN) for the rental of their computing resources, such as computation capacity, spectrum, and transmission power. In this paper, we investigate the problem of how to design the efficient payment plan to maximize the NO's revenue while maintaining FN's incentive to cooperate through the moral hazard model in contract theory. We propose a multi-dimensional contract which considers the FNs' characteristics such as location, computation capacity, storage, transmission bandwidth, and etc. First, a contract which pays the FNs by evaluating the resources they have provided from multiple aspects is proposed. Then, the utility maximization problem of the NO is formulated. Furthermore, we use the numerical results to analyze the optimal payment plan, and compare the NO's utility under different payment plans.
Information Theoretic Limits for Linear Prediction with Graph-Structured Sparsity
Venue: arXiv cs.LG 2017
Year: 2017

We analyze the necessary number of samples for sparse vector recovery in a noisy linear prediction setup. This model includes problems such as linear regression and classification. We focus on structured graph models. In particular, we prove that sufficient number of samples for the weighted graph model proposed by Hegde and others is also necessary. We use the Fano's inequality on well constructed ensembles as our main tool in establishing information theoretic lower bounds.
Deep Region Hashing for Efficient Large-scale Instance Search from Images
Venue: arXiv cs.CV 2017
Year: 2017

Instance Search (INS) is a fundamental problem for many applications, while it is more challenging comparing to traditional image search since the relevancy is defined at the instance level. Existing works have demonstrated the success of many complex ensemble systems that are typically conducted by firstly generating object proposals, and then extracting handcrafted and/or CNN features of each proposal for matching. However, object bounding box proposals and feature extraction are often conducted in two separated steps, thus the effectiveness of these methods collapses. Also, due to the large amount of generated proposals, matching speed becomes the bottleneck that limits its application to large-scale datasets. To tackle these issues, in this paper we propose an effective and efficient Deep Region Hashing (DRH) approach for large-scale INS using an image patch as the query. Specifically, DRH is an end-to-end deep neural network which consists of object proposal, feature extraction, and hash code generation. DRH shares full-image convolutional feature map with the region proposal network, thus enabling nearly cost-free region proposals. Also, each high-dimensional, real-valued region features are mapped onto a low-dimensional, compact binary codes for the efficient object region level matching on large-scale dataset. Experimental results on four datasets show that our DRH can achieve even better performance than the state-of-the-arts in terms of MAP, while the efficiency is improved by nearly 100 times.
Simple approximate equilibria in games with many players
Venue: arXiv cs.GT 2017
Year: 2017

We consider $ε$-equilibria notions for constant value of $ε$ in $n$-player $m$-actions games where $m$ is a constant. We focus on the following question: What is the largest grid size over the mixed strategies such that $ε$-equilibrium is guaranteed to exist over this grid. For Nash equilibrium, we prove that constant grid size (that depends on $ε$ and $m$, but not on $n$) is sufficient to guarantee existence of weak approximate equilibrium. This result implies a polynomial (in the input) algorithm for weak approximate equilibrium. For approximate Nash equilibrium we introduce a closely related question and prove its \emph{equivalence} to the well-known Beck-Fiala conjecture from discrepancy theory. To the best of our knowledge this is the first result introduces a connection between game theory and discrepancy theory. For correlated equilibrium, we prove a $O(\frac{1}{\log n})$ lower-bound on the grid size, which matches the known upper bound of $Ω(\frac{1}{\log n})$. Our result implies an $Ω(\log n)$ lower bound on the rate of convergence of dynamics (any dynamic) to approximate correlated (and coarse correlated) equilibrium. Again, this lower bound matches the $O(\log n)$ upper bound that is achieved by regret minimizing algorithms.
Reinforced stochastic gradient descent for deep neural network learning
Venue: arXiv cs.LG 2017
Year: 2017

Stochastic gradient descent (SGD) is a standard optimization method to minimize a training error with respect to network parameters in modern neural network learning. However, it typically suffers from proliferation of saddle points in the high-dimensional parameter space. Therefore, it is highly desirable to design an efficient algorithm to escape from these saddle points and reach a parameter region of better generalization capabilities. Here, we propose a simple extension of SGD, namely reinforced SGD, which simply adds previous first-order gradients in a stochastic manner with a probability that increases with learning time. As verified in a simple synthetic dataset, this method significantly accelerates learning compared with the original SGD. Surprisingly, it dramatically reduces over-fitting effects, even compared with state-of-the-art adaptive learning algorithm---Adam. For a benchmark handwritten digits dataset, the learning performance is comparable to Adam, yet with an extra advantage of requiring one-fold less computer memory. The reinforced SGD is also compared with SGD with fixed or adaptive momentum parameter and Nesterov's momentum, which shows that the proposed framework is able to reach a similar generalization accuracy with less computational costs. Overall, our method introduces stochastic memory into gradients, which plays an important role in understanding how gradient-based training algorithms can work and its relationship with generalization abilities of deep networks.
Design Aspects of Multi-Soliton Pulses for Optical Fiber Transmission
Venue: arXiv cs.IT 2017
Year: 2017

We explain how to optimize the nonlinear spectrum of multi-soliton pulses by considering the practical constraints of transmitter, receiver, and lumped-amplified link. The optimization is applied for the experimental transmission of 2ns soliton pulses with independent on-off keying of 10 eigenvalues over 2000 km of NZ-DSF fiber spans.
Biomedical Data Warehouses
Venue: arXiv cs.DB 2017
Year: 2017

The aim of this article is to present an overview of the existing biomedical data warehouses and to discuss the issues and future trends in this area. We illustrate this topic by presenting the design of an innovative, complex data warehouse for personal, anticipative medicine.
Indices in XML Databases
Venue: arXiv cs.DB 2017
Year: 2017

With XML becoming a standard for business information representation and exchange, stor-ing, indexing, and querying XML documents have rapidly become major issues in database research. In this context, query processing and optimization are primordial, native-XML data-bases not being mature yet. Data structures such as indices, which help enhance performances substantially, are extensively researched, especially since XML data bear numerous specifici-ties with respect to relational data. In this paper, we survey state-of-the-art XML indices and discuss the main issues, tradeoffs and future trends in XML indexing. We also present an in-dex that we specifically designed for the particular architecture of XML data warehouses.
Efficient Medium Access Arbitration Among Interfering WBANs Using Latin Rectangles
Venue: arXiv cs.NI 2017
Year: 2017

The overlap of transmission ranges among multiple Wireless Body Area Networks (WBANs) is referred to as coexistence. The interference is most likely to affect the communication links and degrade the performance when sensors of different WBANs simultaneously transmit using the same channel. In this paper, we propose a distributed approach that adapts to the size of the network, i.e., the number of coexisting WBANs, and to the density of sensors forming each individual WBAN in order to minimize the impact of co-channel interference through dynamic channel hopping based on Latin rectangles. Furthermore, the proposed approach opts to reduce the overhead resulting from channel hopping, and lowers the transmission delay, and saves the power resource at both sensor- and WBAN-levels. Specifically, we propose two schemes for channel allocation and medium access scheduling to diminish the probability of inter-WBAN interference. The first scheme, namely, Distributed Interference Avoidance using Latin rectangles (DAIL), assigns channel and time-slot combination that reduces the probability of medium access collision. DAIL suits crowded areas, e.g., high density of coexisting WBANs, and involves overhead due to frequent channel hopping at the WBAN coordinator and sensors. The second scheme, namely, CHIM, takes advantage of the relatively lower density of collocated WBANs to save power by hopping among channels only when interference is detected at the level of the individual nodes. We present an analytical model that derives the collision probability and network throughput. The performance of DAIL and CHIM is further validated through simulations.
Design of Capacity Approaching Ensembles of LDPC Codes for Correlated Sources using EXIT Charts
Venue: arXiv cs.IT 2017
Year: 2017

This paper is concerned with the design of capacity approaching ensembles of Low-Densiy Parity-Check (LDPC) codes for correlated sources. We consider correlated binary sources where the data is encoded independently at each source through a systematic LDPC encoder and sent over two independent channels. At the receiver, a iterative joint decoder consisting of two component LDPC decoders is considered where the encoded bits at the output of each component decoder are used at the other decoder as the a priori information. We first provide asymptotic performance analysis using the concept of extrinsic information transfer (EXIT) charts. Compared to the conventional EXIT charts devised to analyze LDPC codes for point to point communication, the proposed EXIT charts have been completely modified to able to accommodate the systematic nature of the codes as well as the iterative behavior between the two component decoders. Then the developed modified EXIT charts are deployed to design ensembles for different levels of correlation. Our results show that as the average degree of the designed ensembles grow, the thresholds corresponding to the designed ensembles approach the capacity. In particular, for ensembles with average degree of around 9, the gap to capacity is reduced to about 0.2dB. Finite block length performance evaluation is also provided for the designed ensembles to verify the asymptotic results.
Design of PI Controller for Automatic Generation Control of Multi Area Interconnected Power System using Bacterial Foraging Optimization
Venue: arXiv cs.SY 2017
Year: 2017

The system comprises of three interconnected power system networks based on thermal, wind and hydro power generation. The load variation in any one of the network results in frequency deviation in all the connected systems.The PI controllers have been connected separately with each system for the frequency control and the gains (Kp and Ki) of all the controllers have been optimized along with frequency bias (Bi) and speed regulation parameter (Ri). The computationally intelligent techniques like bacterial foraging optimization (BFO) and particle swarm optimization (PSO) have been applied for the tuning of controller gains along with variable parameters Bi and Ri. The gradient descent (GD) based conventional method has also been applied for optimizing the parameters Kp, Ki,Bi and Ri.The frequency responses are obtained with all the methods. The performance index chosen is the integral square error (ISE). The settling time, peak overshoot and peak undershoot of all the frequency responses on applying three optimization techniques have been compared. It has been observed that the peak overshoot and peak undershoot significantly reduce with BFO technique followed by the PSO and GD techniques. While obtaining such optimum response the settling time is increased marginally with bacterial foraging technique due to large number of mathematical equations used for the computation in BFO. The comparison of frequency response using three techniques show the superiority of BFO over the PSO and GD techniques. The designing of the system and tuning of the parameters with three techniques has been done in MATLAB/SIMULINK environment.
Efficiently Summarising Event Sequences with Rich Interleaving Patterns
Venue: arXiv cs.AI 2017
Year: 2017

Discovering the key structure of a database is one of the main goals of data mining. In pattern set mining we do so by discovering a small set of patterns that together describe the data well. The richer the class of patterns we consider, and the more powerful our description language, the better we will be able to summarise the data. In this paper we propose \ourmethod, a novel greedy MDL-based method for summarising sequential data using rich patterns that are allowed to interleave. Experiments show \ourmethod is orders of magnitude faster than the state of the art, results in better models, as well as discovers meaningful semantics in the form patterns that identify multiple choices of values.
FM-Delta: Fault Management Packet Compression
Venue: arXiv cs.NI 2017
Year: 2017

Fault Management (FM) is a cardinal feature in communication networks. One of the most common FM approaches is to use periodic keepalive messages. Hence, switches and routers are required to transmit a large number of FM messages periodically, requiring a hardware-based packet generator that periodically transmits a set of messages that are stored in an expensive on-chip memory. With the rapid growth of carrier networks, and as 5G technologies emerge, the number of users and the traffic rates are expected to significantly increase over the next few years. Consequently, we expect the on-chip memories used for FM to become a costly component in switch and router chips. We introduce a novel approach in which FM messages are stored in compressed form in the on-chip memory, allowing to significantly reduce the memory size. We present FM-Delta, a simple hardware-friendly delta encoding algorithm that allows FM messages to be compressed by a factor of 2.6. We show that this compression ratio is very close to the results of the zlib compression library, which requires much higher implementation complexity.
Evaluating a sublinear-time algorithm for the Minimum Spanning Tree Weight problem
Venue: arXiv cs.DS 2017
Year: 2017

We present an implementation and an experimental evaluation of an algorithm that, given a connected graph G (represented by adjacency lists), estimates in sublinear time, with a relative error, the Minimum Spanning Tree Weight of G; the original algorithm has been presented in "Approximating the minimum spanning tree weight in sublinear time", by Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan (published with SIAM, DOI 10.1137/S0097539702403244). Since the theoretical performances have already been shown and demonstrated in the above-mentioned paper, our goal is, exclusively, to experimental evaluate the algorithm and at last to present the results. Initially we discuss about some theoretical aspects that arose while we were valuating the asymptotic complexity of our specific implementation. Some technical insights are then given on the implementation of the algorithm and on the dataset used in the test phase, hence to show how the experiment has been carried out even for reproducibility purposes; the results are then evaluated empirically and widely discussed, comparing these with the performances of the Prim algorithm and the Kruskal algorithm, launching several runs on a heterogeneous set of graphs and different theoretical models for them.
Camera-trap images segmentation using multi-layer robust principal component analysis
Venue: arXiv cs.CV 2017
Year: 2017

The segmentation of animals from camera-trap images is a difficult task. To illustrate, there are various challenges due to environmental conditions and hardware limitation in these images. We proposed a multi-layer robust principal component analysis (multi-layer RPCA) approach for background subtraction. Our method computes sparse and low-rank images from a weighted sum of descriptors, using color and texture features as case of study for camera-trap images segmentation. The segmentation algorithm is composed of histogram equalization or Gaussian filtering as pre-processing, and morphological filters with active contour as post-processing. The parameters of our multi-layer RPCA were optimized with an exhaustive search. The database consists of camera-trap images from the Colombian forest taken by the Instituto de Investigación de Recursos Biológicos Alexander von Humboldt. We analyzed the performance of our method in inherent and therefore challenging situations of camera-trap images. Furthermore, we compared our method with some state-of-the-art algorithms of background subtraction, where our multi-layer RPCA outperformed these other methods. Our multi-layer RPCA reached 76.17 and 69.97% of average fine-grained F-measure for color and infrared sequences, respectively. To our best knowledge, this paper is the first work proposing multi-layer RPCA and using it for camera-trap images segmentation.
The GangaWatch Mobile App to Enable Usage of Water Data in Every Day Decisions Integrating Historical and Real-time Sensing Data
Venue: arXiv cs.CY 2017
Year: 2017

We demonstrate a novel mobile application called GangaWatch that makes water pollution data usable and accessible focusing on one of the most polluted river basins in the world. It is intended to engage common public who want to see water condition and safe limits, and their relevance based on different purposes. The data is a combination of old data determined from lab tests on physical samples and new data from real time sensors collected from Ganga basin. The platform is open for contribution from others, the data is also available for reuse via public APIs, and it has already been used to derive new insights.
Feature Studies to Inform the Classification of Depressive Symptoms from Twitter Data for Population Health
Venue: arXiv cs.IR 2017
Year: 2017

The utility of Twitter data as a medium to support population-level mental health monitoring is not well understood. In an effort to better understand the predictive power of supervised machine learning classifiers and the influence of feature sets for efficiently classifying depression-related tweets on a large-scale, we conducted two feature study experiments. In the first experiment, we assessed the contribution of feature groups such as lexical information (e.g., unigrams) and emotions (e.g., strongly negative) using a feature ablation study. In the second experiment, we determined the percentile of top ranked features that produced the optimal classification performance by applying a three-step feature elimination approach. In the first experiment, we observed that lexical features are critical for identifying depressive symptoms, specifically for depressed mood (-35 points) and for disturbed sleep (-43 points). In the second experiment, we observed that the optimal F1-score performance of top ranked features in percentiles variably ranged across classes e.g., fatigue or loss of energy (5th percentile, 288 features) to depressed mood (55th percentile, 3,168 features) suggesting there is no consistent count of features for predicting depressive-related tweets. We conclude that simple lexical features and reduced feature sets can produce comparable results to larger feature sets.
Algorithmic decision making and the cost of fairness
Venue: arXiv cs.CY 2017
Year: 2017

Algorithms are now regularly used to decide whether defendants awaiting trial are too dangerous to be released back into the community. In some cases, black defendants are substantially more likely than white defendants to be incorrectly classified as high risk. To mitigate such disparities, several techniques recently have been proposed to achieve algorithmic fairness. Here we reformulate algorithmic fairness as constrained optimization: the objective is to maximize public safety while satisfying formal fairness constraints designed to reduce racial disparities. We show that for several past definitions of fairness, the optimal algorithms that result require detaining defendants above race-specific risk thresholds. We further show that the optimal unconstrained algorithm requires applying a single, uniform threshold to all defendants. The unconstrained algorithm thus maximizes public safety while also satisfying one important understanding of equality: that all individuals are held to the same standard, irrespective of race. Because the optimal constrained and unconstrained algorithms generally differ, there is tension between improving public safety and satisfying prevailing notions of algorithmic fairness. By examining data from Broward County, Florida, we show that this trade-off can be large in practice. We focus on algorithms for pretrial release decisions, but the principles we discuss apply to other domains, and also to human decision makers carrying out structured decision rules.
Exploiting PUF Models for Error Free Response Generation
Venue: arXiv cs.CR 2017
Year: 2017

Physical unclonable functions (PUF) extract secrets from randomness inherent in manufacturing processes. PUFs are utilized for basic cryptographic tasks such as authentication and key generation, and more recently, to realize key exchange and bit commitment requiring a large number of error free responses from a strong PUF. We propose an approach to eliminate the need to implement expensive on-chip error correction logic implementation and the associated helper data storage to reconcile naturally noisy PUF responses. In particular, we exploit a statistical model of an Arbiter PUF (APUF) constructed under the nominal operating condition during the challenge response enrollment phase by a trusted party to judiciously select challenges that yield error-free responses even across a wide operating conditions, specifically, a $ \pm 20\% $ supply voltage variation and a $ 40^{\crc} $ temperature variation. We validate our approach using measurements from two APUF datasets. Experimental results indicate that large number of error-free responses can be generated on demand under worst-case when PUF response error rate is up to 16.68\%.
Who With Whom And How?: Extracting Large Social Networks Using Search Engines
Venue: arXiv cs.SI 2017
Year: 2017

Social network analysis is leveraged in a variety of applications such as identifying influential entities, detecting communities with special interests, and determining the flow of information and innovations. However, existing approaches for extracting social networks from unstructured Web content do not scale well and are only feasible for small graphs. In this paper, we introduce novel methodologies for query-based search engine mining, enabling efficient extraction of social networks from large amounts of Web data. To this end, we use patterns in phrase queries for retrieving entity connections, and employ a bootstrapping approach for iteratively expanding the pattern set. Our experimental evaluation in different domains demonstrates that our algorithms provide high quality results and allow for scalable and efficient construction of social graphs.