OpenRaiser/Intern-Atlas huggingface dataset:
Compress and Control
Venue: arXiv cs.AI 2014
Year: 2014

This paper describes a new information-theoretic policy evaluation technique for reinforcement learning. This technique converts any compression or density model into a corresponding estimate of value. Under appropriate stationarity and ergodicity conditions, we show that the use of a sufficiently powerful model gives rise to a consistent value function estimator. We also study the behavior of this technique when applied to various Atari 2600 video games, where the use of suboptimal modeling techniques is unavoidable. We consider three fundamentally different models, all too limited to perfectly model the dynamics of the system. Remarkably, we find that our technique provides sufficiently accurate value estimates for effective on-policy control. We conclude with a suggestive study highlighting the potential of our technique to scale to large problems.
Agent-Based Model for Rural-Urban Migration: A Dynamic Consideration
Venue: arXiv cs.MA 2014
Year: 2014

This paper develops a dynamic agent-based model for rural-urban migration, based on the previous relevant works. The model conforms to the typical dynamic linear multi-agent systems model concerned extensively in systems science, in which the communication network is formulated as a digraph. Simulations reveal that consensus of certain variable could be harmful to the overall stability and should be avoided.
Using Volunteer Computing for Mounting SAT-based Cryptographic Attacks
Venue: arXiv cs.DC 2014
Year: 2014

In this paper we describe the volunteer computing project SAT@home, developed and maintained by us. This project is aimed at solving hard instances of the Boolean satisfiability problem (SAT). We believe that this project can be a useful tool for computational study of inversion problems of some cryptographic functions. In particular we describe a series of experiments performed in SAT@home on the cryptanalysis of the widely known keystream generator A5/1. In all experiments we analyzed one known burst (114 bits) of keystream produced by A5/1. Before the cryptanalysis itself there is a stage on which the partitioning of the original problem to a family of subproblems is carried out. Each of subproblems should be easy enough so that it could be solved in relatively small amount of time by volunteer's PC. We construct such partitioning using the special technique based on the Monte Carlo method and discrete optimization algorithms for special predictive functions. Besides this in the paper we describe the technique for reducing inversion problems of cryptographic functions to SAT.
Fairness and Social Welfare in Incentivizing Participatory Sensing
Venue: arXiv cs.GT 2014
Year: 2014

Participatory sensing has emerged recently as a promising approach to large-scale data collection. However, without incentives for users to regularly contribute good quality data, this method is unlikely to be viable in the long run. In this paper, we link incentive to users' demand for consuming compelling services, as an approach complementary to conventional credit or reputation based approaches. With this demand-based principle, we design two incentive schemes, Incentive with Demand Fairness (IDF) and Iterative Tank Filling (ITF), for maximizing fairness and social welfare, respectively. Our study shows that the IDF scheme is max-min fair and can score close to 1 on the Jain's fairness index, while the ITF scheme maximizes social welfare and achieves a unique Nash equilibrium which is also Pareto and globally optimal. We adopted a game theoretic approach to derive the optimal service demands. Furthermore, to address practical considerations, we use a stochastic programming technique to handle uncertainty that is often encountered in real life situations.
Solving Hamiltonian Cycle by an EPT Algorithm for a Non-sparse Parameter
Venue: arXiv cs.DS 2014
Year: 2014

Many hard graph problems, such as Hamiltonian Cycle, become FPT when parameterized by treewidth, a parameter that is bounded only on sparse graphs. When parameterized by the more general parameter clique-width, Hamiltonian Cycle becomes W[1]-hard, as shown by Fomin et al. [5]. Sæther and Telle address this problem in their paper [13] by introducing a new parameter, split-matching-width, which lies between treewidth and clique-width in terms of generality. They show that even though graphs of restricted split-matching-width might be dense, solving problems such as Hamiltonian Cycle can be done in FPT time. Recently, it was shown that Hamiltonian Cycle parameterized by treewidth is in EPT [1, 6], meaning it can be solved in $n^{O(1)} 2^{O(k)}$-time. In this paper, using tools from [6], we show that also parameterized by split-matching-width Hamiltonian Cycle is EPT. To the best of our knowledge, this is the first EPT algorithm for any "globally constrained" graph problem parameterized by a non-trivial and non-sparse structural parameter. To accomplish this, we also give an algorithm constructing a branch decomposition approximating the minimum split-matching-width to within a constant factor. Combined, these results show that the algorithms in [13] for Edge Dominating Set, Chromatic Number and Max Cut all can be improved. We also show that for Hamiltonian Cycle and Max Cut the resulting algorithms are asymptotically optimal under the Exponential Time Hypothesis.
Hardware-Amenable Structural Learning for Spike-based Pattern Classification using a Simple Model of Active Dendrites
Venue: arXiv cs.NE 2014
Year: 2014

This paper presents a spike-based model which employs neurons with functionally distinct dendritic compartments for classifying high dimensional binary patterns. The synaptic inputs arriving on each dendritic subunit are nonlinearly processed before being linearly integrated at the soma, giving the neuron a capacity to perform a large number of input-output mappings. The model utilizes sparse synaptic connectivity; where each synapse takes a binary value. The optimal connection pattern of a neuron is learned by using a simple hardware-friendly, margin enhancing learning algorithm inspired by the mechanism of structural plasticity in biological neurons. The learning algorithm groups correlated synaptic inputs on the same dendritic branch. Since the learning results in modified connection patterns, it can be incorporated into current event-based neuromorphic systems with little overhead. This work also presents a branch-specific spike-based version of this structural plasticity rule. The proposed model is evaluated on benchmark binary classification problems and its performance is compared against that achieved using Support Vector Machine (SVM) and Extreme Learning Machine (ELM) techniques. Our proposed method attains comparable performance while utilizing 10 to 50% less computational resources than the other reported techniques.
PSPACE-completeness of Bloxorz and of Games with 2-Buttons
Venue: arXiv cs.CC 2014
Year: 2014

Bloxorz is an online puzzle game where players move a 1 by 1 by 2 block by tilting it on a subset of the two dimensional grid. Bloxorz features switches that open and close trapdoors. The puzzle is to move the block from its initial position to an upright position on the destination square. We show that the problem of deciding whether a given Bloxorz level is solvable is PSPACE-complete and that this remains so even when all trapdoors are initially closed or all trapdoors are initially open. We also answer an open question of Viglietta, showing that 2-buttons are sufficient for PSPACE-hardness of general puzzle games. We also examine the hardness of some variants of Bloxorz, including variants where the block is a 1 by 1 by 1 cube, and variants with single-use tiles.
Reverse Engineering Point Clouds to Fit Tensor Product B-Spline Surfaces by Blending Local Fits
Venue: arXiv cs.GR 2014
Year: 2014

Being able to reverse engineer from point cloud data to obtain 3D models is important in modeling. As our main contribution, we present a new method to obtain a tensor product B-spline representation from point cloud data by fitting surfaces to appropriately segmented data. By blending multiple local fits our method is more efficient than existing techniques, with the ability to deal with more detail by efficiently introducing a high number of knots. Further point cloud data obtained by digitizing 3D data, typically presents many associated complications like noise and missing data. As our second contribution, we propose an end-to-end framework for smoothing, hole filling, parameterization, knot selection and B-spline fitting that addresses these issues, works robustly with large irregularly shaped data containing holes and is straightforward to implement.
Energy and SLA aware VM Scheduling
Venue: arXiv cs.DC 2014
Year: 2014

With the advancement of Cloud Computing over the past few years, there has been a massive shift from traditional data centers to cloud enabled data centers. The enterprises with cloud data centers are focusing their attention on energy savings through effective utilization of resources. In this work, we propose algorithms which try to minimize the energy consumption in the data center duly maintaining the SLA guarantees. The algorithms try to utilize least number of physical machines in the data center by dynamically rebalancing the physical machines based on their resource utilization. The algorithms also perform an optimal consolidation of virtual machines on a physical machine, minimizing SLA violations. In extensive simulation, our algorithms achieve savings of about 21% in terms of energy consumption and in terms of maintaining the SLAs, it performs 60% better than Single Threshold algorithm.
Particle Filtering for Attitude Estimation Using a Minimal Local-Error Representation: A Revisit
Venue: arXiv cs.RO 2014
Year: 2014

In this note, we have revisited the previously published paper "Particle Filtering for Attitude Estimation Using a Minimal Local-Error Representation". In the revisit, we point out that the quaternion particle filtering based on the local/global representation structure has not made full use of the advantage of the particle filtering in terms of accuracy and robustness. Moreover, a normalized quaternion determining procedure based on the minimum mean-square error approach has been investigated into the quaternion-based particle filtering to obtain the fiducial quaternion for the transformation between quaternion and modified Rodrigues parameter. The modification investigated in this note is expected to make the quaternion particle filtering based on the local/global representation structure more strict.
Threshold-based monitoring of cascading outages with PMU measurements of area angle
Venue: arXiv cs.SY 2014
Year: 2014

When power grids are heavily stressed with a bulk power transfer, it is useful to have a fast indication of the increased stress when multiple line outages occur. Reducing the bulk power transfer when the outages are severe could forestall further cascading of the outages. We show that synchrophasor measurements of voltage angles at all the area tie lines can be used to indicate the severity of multiple outages. These synchrophasor measurements are readily combined into an "area angle" that can quickly track the severity of multiple outages after they occur. We present a procedure to define thresholds for the area angle that relate to the maximum power that can be transferred through the area until a line limit is reached. Then in real time we would monitor the area angle and compare it to the thresholds when line outages occur to determine the urgency (or not) of actions to reduce the bulk transfer of power through the area. The procedure also identifies exceptional cases in which separate actions to resolve local power distribution problems are needed. We illustrate the thresholds and monitoring with the area angle across several states of Northwestern USA.
Throughput-Optimal Broadcast on Directed Acyclic Graphs
Venue: arXiv cs.NI 2014
Year: 2014

We study the problem of broadcasting packets in wireless networks. At each time slot, a network controller activates non-interfering links and forwards packets to all nodes at a common rate; the maximum rate is referred to as the broadcast capacity of the wireless network. Existing policies achieve the broadcast capacity by balancing traffic over a set of spanning trees, which are difficult to maintain in a large and time-varying wireless network. We propose a new dynamic algorithm that achieves the broadcast capacity when the underlying network topology is a directed acyclic graph (DAG). This algorithm utilizes local queue-length information, does not use any global topological structures such as spanning trees, and uses the idea of in-order packet delivery to all network nodes. Although the in-order packet delivery constraint leads to degraded throughput in cyclic graphs, we show that it is throughput optimal in DAGs and can be exploited to simplify the design and analysis of optimal algorithms. Our simulation results show that the proposed algorithm has superior delay performance as compared to tree-based approaches.
Improvised Apriori Algorithm using frequent pattern tree for real time applications in data mining
Venue: arXiv cs.DB 2014
Year: 2014

Apriori Algorithm is one of the most important algorithm which is used to extract frequent itemsets from large database and get the association rule for discovering the knowledge. It basically requires two important things: minimum support and minimum confidence. First, we check whether the items are greater than or equal to the minimum support and we find the frequent itemsets respectively. Secondly, the minimum confidence constraint is used to form association rules. Based on this algorithm, this paper indicates the limitation of the original Apriori algorithm of wasting time and space for scanning the whole database searching on the frequent itemsets, and present an improvement on Apriori.
$L_p$-stabilization of integrator chains subject to input saturation using Lyapunov-based homogeneous design
Venue: arXiv cs.SY 2014
Year: 2014

Consider the $n$-th integrator $\dot x=J_nx+σ(u)e_n$, where $x\in\mathbb{R}^n$, $u\in \mathbb{R}$, $J_n$ is the $n$-th Jordan block and $e_n=(0\ \cdots 0\ 1)^T\in\mathbb{R}^n$. We provide easily implementable state feedback laws $u=k(x)$ which not only render the closed-loop system globally asymptotically stable but also are finite-gain $L_p$-stabilizing with arbitrarily small gain. These $L_p$-stabilizing state feedbacks are built from homogeneous feedbacks appearing in finite-time stabilization of linear systems. We also provide additional $L_\infty$-stabilization results for the case of both internal and external disturbances of the $n$-th integrator, namely for the perturbed system $\dot x=J_nx+e_nσ(k(x)+d)+D$ where $d\in\mathbb{R}$ and $D\in\mathbb{R}^n$.
Synthetic Generation of Social Network Data With Endorsements
Venue: arXiv cs.SI 2014
Year: 2014

In many simulation studies involving networks there is the need to rely on a sample network to perform the simulation experiments. In many cases, real network data is not available due to privacy concerns. In that case we can recourse to synthetic data sets with similar properties to the real data. In this paper we discuss the problem of generating synthetic data sets for a certain kind of online social network, for simulation purposes. Some popular online social networks, such as LinkedIn and ResearchGate, allow user endorsements for specific skills. For each particular skill, the endorsements give rise to a directed subgraph of the corresponding network, where the nodes correspond to network members or users, and the arcs represent endorsement relations. Modelling these endorsement digraphs can be done by formulating an optimization problem, which is amenable to different heuristics. Our construction method consists of two stages: The first one simulates the growth of the network, and the second one solves the aforementioned optimization problem to construct the endorsements.
Community-based Immunization Strategies for Epidemic Control
Venue: arXiv cs.SI 2014
Year: 2014

Understanding the epidemic dynamics, and finding out efficient techniques to control it, is a challenging issue. A lot of research has been done on targeted immunization strategies, exploiting various global network topological properties. However, in practice, information about the global structure of the contact network may not be available. Therefore, immunization strategies that can deal with a limited knowledge of the network structure are required. In this paper, we propose targeted immunization strategies that require information only at the community level. Results of our investigations on the SIR epidemiological model, using a realistic synthetic benchmark with controlled community structure, show that the community structure plays an important role in the epidemic dynamics. An extensive comparative evaluation demonstrates that the proposed strategies are as efficient as the most influential global centrality based immunization strategies, despite the fact that they use a limited amount of information. Furthermore, they outperform alternative local strategies, which are agnostic about the network structure, and make decisions based on random walks.
Diversifying Sparsity Using Variational Determinantal Point Processes
Venue: arXiv cs.LG 2014
Year: 2014

We propose a novel diverse feature selection method based on determinantal point processes (DPPs). Our model enables one to flexibly define diversity based on the covariance of features (similar to orthogonal matching pursuit) or alternatively based on side information. We introduce our approach in the context of Bayesian sparse regression, employing a DPP as a variational approximation to the true spike and slab posterior distribution. We subsequently show how this variational DPP approximation generalizes and extends mean-field approximation, and can be learned efficiently by exploiting the fast sampling properties of DPPs. Our motivating application comes from bioinformatics, where we aim to identify a diverse set of genes whose expression profiles predict a tumor type where the diversity is defined with respect to a gene-gene interaction network. We also explore an application in spatial statistics. In both cases, we demonstrate that the proposed method yields significantly more diverse feature sets than classic sparse methods, without compromising accuracy.
A Convex Formulation for Spectral Shrunk Clustering
Venue: arXiv cs.LG 2014
Year: 2014

Spectral clustering is a fundamental technique in the field of data mining and information processing. Most existing spectral clustering algorithms integrate dimensionality reduction into the clustering process assisted by manifold learning in the original space. However, the manifold in reduced-dimensional subspace is likely to exhibit altered properties in contrast with the original space. Thus, applying manifold information obtained from the original space to the clustering process in a low-dimensional subspace is prone to inferior performance. Aiming to address this issue, we propose a novel convex algorithm that mines the manifold structure in the low-dimensional subspace. In addition, our unified learning process makes the manifold learning particularly tailored for the clustering. Compared with other related methods, the proposed algorithm results in more structured clustering result. To validate the efficacy of the proposed algorithm, we perform extensive experiments on several benchmark datasets in comparison with some state-of-the-art clustering approaches. The experimental results demonstrate that the proposed algorithm has quite promising clustering performance.
Distance's Quantification Algorithm in AODV Protocol
Venue: arXiv cs.NI 2014
Year: 2014

Mobility is one of the basic features that define an ad hoc network, an asset that leaves the field free for the nodes to move. The most important aspect of this kind of network turns into a great disadvantage when it comes to commercial applications, take as an example: the automotive networks that allow communication between a groups of vehicles. The ad hoc on-demand distance vector (AODV) routing protocol, designed for mobile ad hoc networks, has two main functions. First, it enables route establishment between a source and a destination node by initiating a route discovery process. Second, it maintains the active routes, which means finding alternative routes in a case of a link failure and deleting routes when they are no longer desired. In a highly mobile network those are demanding tasks to be performed efficiently and accurately. In this paper, we focused in the first point to enhance the local decision of each node in the network by the quantification of the mobility of their neighbours. Quantification is made around RSSI algorithm a well known distance estimation method.
On The Marriage of SPARQL and Keywords
Venue: arXiv cs.DB 2014
Year: 2014

Although SPARQL has been the predominant query language over RDF graphs, some query intentions cannot be well captured by only using SPARQL syntax. On the other hand, the keyword search enjoys widespread usage because of its intuitive way of specifying information needs but suffers from the problem of low precision. To maximize the advantages of both SPARQL and keyword search, we introduce a novel paradigm that combines both of them and propose a hybrid query (called an SK query) that integrates SPARQL and keyword search. In order to answer SK queries efficiently, a structural index is devised, based on a novel integrated query algorithm is proposed. We evaluate our method in large real RDF graphs and experiments demonstrate both effectiveness and efficiency of our method.
Effect of Receptor Density and Size on Signal Reception in Molecular Communication via Diffusion with an Absorbing Receiver
Venue: arXiv cs.ET 2014
Year: 2014

The performance of molecular communication is significantly impacted by the reception process of the messenger molecules. The receptors' size and density, however, have yet to be investigated. In this letter, we analyze the effect of receptor density and size on the signal reception of an absorbing receiver with receptors. The results show that, when the total receptor area is the same, better hitting probability is achieved by using a higher number of relatively small receptors. In addition, deploying receptors, which cover a small percentage of the receiver surface, is able to create an effective communication channel that has a detectable signal level.