OpenRaiser/Intern-Atlas huggingface dataset:
Learning Mobile Robot Based on Adaptive Controlled Markov Chains
Venue: arXiv cs.RO 2015
Year: 2015

Herein we suggest a mobile robot-training algorithm that is based on the preference approximation of the decision taker who controls the robot, which in its turn is managed by the Markov chain. Setup of the model parameters is made on the basis of the data referring to the situations and decisions involving the decision taker. The model that adapts to the decision taker's preferences can be set up either a priori, during the process of the robot's normal operation, or during specially planned testing sessions. Basing on the simulation modelling data of the robot's operation process and on the decision taker's robot control we have set up the model parameters thus illustrating both working capacity of all algorithm components and adaptation effectiveness.
Network Structure and Resilience of Mafia Syndicates
Venue: arXiv cs.SI 2015
Year: 2015

In this paper we present the results of the study of Sicilian Mafia organization by using Social Network Analysis. The study investigates the network structure of a Mafia organization, describing its evolution and highlighting its plasticity to interventions targeting membership and its resilience to disruption caused by police operations. We analyze two different datasets about Mafia gangs built by examining different digital trails and judicial documents spanning a period of ten years: the former dataset includes the phone contacts among suspected individuals, the latter is constituted by the relationships among individuals actively involved in various criminal offenses. Our report illustrates the limits of traditional investigation methods like tapping: criminals high up in the organization hierarchy do not occupy the most central positions in the criminal network, and oftentimes do not appear in the reconstructed criminal network at all. However, we also suggest possible strategies of intervention, as we show that although criminal networks (i.e., the network encoding mobsters and crime relationships) are extremely resilient to different kind of attacks, contact networks (i.e., the network reporting suspects and reciprocated phone calls) are much more vulnerable and their analysis can yield extremely valuable insights.
Reinforcement Learning with Parameterized Actions
Venue: arXiv cs.AI 2015
Year: 2015

We introduce a model-free algorithm for learning in Markov decision processes with parameterized actions-discrete actions with continuous parameters. At each step the agent must select both which action to use and which parameters to use with that action. We introduce the Q-PAMDP algorithm for learning in these domains, show that it converges to a local optimum, and compare it to direct policy search in the goal-scoring and Platform domains.
Gravitational Clustering
Venue: arXiv cs.LG 2015
Year: 2015

The downfall of many supervised learning algorithms, such as neural networks, is the inherent need for a large amount of training data. Although there is a lot of buzz about big data, there is still the problem of doing classification from a small dataset. Other methods such as support vector machines, although capable of dealing with few samples, are inherently binary classifiers, and are in need of learning strategies such as One vs All in the case of multi-classification. In the presence of a large number of classes this can become problematic. In this paper we present, a novel approach to supervised learning through the method of clustering. Unlike traditional methods such as K-Means, Gravitational Clustering does not require the initial number of clusters, and automatically builds the clusters, individual samples can be arbitrarily weighted and it requires only few samples while staying resilient to over-fitting.
Extending Hybrid CSP with Probability and Stochasticity
Venue: arXiv cs.LO 2015
Year: 2015

Probabilistic and stochastic behavior are omnipresent in computer controlled systems, in particular, so-called safety-critical hybrid systems, because of fundamental properties of nature, uncertain environments, or simplifications to overcome complexity. Tightly intertwining discrete, continuous and stochastic dynamics complicates modelling, analysis and verification of stochastic hybrid systems (SHSs). In the literature, this issue has been extensively investigated, but unfortunately it still remains challenging as no promising general solutions are available yet. In this paper, we give our effort by proposing a general compositional approach for modelling and verification of SHSs. First, we extend Hybrid CSP (HCSP), a very expressive and process algebra-like formal modeling language for hybrid systems, by introducing probability and stochasticity to model SHSs, which is called stochastic HCSP (SHCSP). To this end, ordinary differential equations (ODEs) are generalized by stochastic differential equations (SDEs) and non-deterministic choice is replaced by probabilistic choice. Then, we extend Hybrid Hoare Logic (HHL) to specify and reason about SHCSP processes. We demonstrate our approach by an example from real-world.
Optimum Traffic Allocation in Bundled Energy Efficient Ethernet Links
Venue: arXiv cs.NI 2015
Year: 2015

The energy demands of Ethernet links have been an active focus of research in the recent years. This work has enabled a new generation of Energy Efficient Ethernet (EEE) interfaces able to adapt their power consumption to the actual traffic demands, thus yielding significant energy savings. With the energy consumption of single network connections being a solved problem, in this paper we focus on the energy demands of link aggregates that are commonly used to increase the capacity of a network connection. We build on known energy models of single EEE links to derive the energy demands of the whole aggregate as a function on how the traffic load is spread among its powered links. We then provide a practical method to share the load that minimizes overall energy consumption with controlled packet delay, and prove that it is valid for a wide range of EEE links. Finally, we validate our method with both synthetic and real traffic traces captured in Internet backbones.
Unsupervised Cross-Domain Recognition by Identifying Compact Joint Subspaces
Venue: arXiv cs.CV 2015
Year: 2015

This paper introduces a new method to solve the cross-domain recognition problem. Different from the traditional domain adaption methods which rely on a global domain shift for all classes between source and target domain, the proposed method is more flexible to capture individual class variations across domains. By adopting a natural and widely used assumption -- "the data samples from the same class should lay on a low-dimensional subspace, even if they come from different domains", the proposed method circumvents the limitation of the global domain shift, and solves the cross-domain recognition by finding the compact joint subspaces of source and target domain. Specifically, given labeled samples in source domain, we construct subspaces for each of the classes. Then we construct subspaces in the target domain, called anchor subspaces, by collecting unlabeled samples that are close to each other and highly likely all fall into the same class. The corresponding class label is then assigned by minimizing a cost function which reflects the overlap and topological structure consistency between subspaces across source and target domains, and within anchor subspaces, respectively.We further combine the anchor subspaces to corresponding source subspaces to construct the compact joint subspaces. Subsequently, one-vs-rest SVM classifiers are trained in the compact joint subspaces and applied to unlabeled data in the target domain. We evaluate the proposed method on two widely used datasets: object recognition dataset for computer vision tasks, and sentiment classification dataset for natural language processing tasks. Comparison results demonstrate that the proposed method outperforms the comparison methods on both datasets.
A Multi-cell MMSE Precoder for Massive MIMO Systems and New Large System Analysis
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, a new multi-cell MMSE precoder is proposed for massive MIMO systems. We consider a multi-cell network where each cell has $K$ users and $B$ orthogonal pilot sequences are available, with $B = βK$ and $β\ge 1$ being the pilot reuse factor over the network. In comparison with conventional single-cell precoding which only uses the $K$ intra-cell channel estimates, the proposed multi-cell MMSE precoder utilizes all $B$ channel directions that can be estimated locally at a base station, so that the transmission is designed spatially to suppress both parts of the inter-cell and intra-cell interference. To evaluate the performance, a large-scale approximation of the downlink SINR for the proposed multi-cell MMSE precoder is derived and the approximation is tight in the large-system limit. Power control for the pilot and payload, imperfect channel estimation and arbitrary pilot allocation are accounted for in our precoder. Numerical results show that the proposed multi-cell MMSE precoder achieves a significant sum spectral efficiency gain over the classical single-cell MMSE precoder and the gain increases as $K$ or $β$ grows. Compared with the recent M-ZF precoder, whose performance degrades drastically for a large $K$, our M-MMSE can always guarantee a high and stable performance. Moreover, the large-scale approximation is easy to compute and shown to be accurate even for small system dimensions.
Theoretical and Experimental Analyses of Tensor-Based Regression and Classification
Venue: arXiv cs.LG 2015
Year: 2015

We theoretically and experimentally investigate tensor-based regression and classification. Our focus is regularization with various tensor norms, including the overlapped trace norm, the latent trace norm, and the scaled latent trace norm. We first give dual optimization methods using the alternating direction method of multipliers, which is computationally efficient when the number of training samples is moderate. We then theoretically derive an excess risk bound for each tensor norm and clarify their behavior. Finally, we perform extensive experiments using simulated and real data and demonstrate the superiority of tensor-based learning methods over vector- and matrix-based learning methods.
Sparsification of Two-Variable Valued CSPs
Venue: arXiv cs.DS 2015
Year: 2015

A valued constraint satisfaction problem (VCSP) instance $(V,Π,w)$ is a set of variables $V$ with a set of constraints $Π$ weighted by $w$. Given a VCSP instance, we are interested in a re-weighted sub-instance $(V,Π'\subset Π,w')$ such that preserves the value of the given instance (under every assignment to the variables) within factor $1\pmε$. A well-studied special case is cut sparsification in graphs, which has found various applications. We show that a VCSP instance consisting of a single boolean predicate $P(x,y)$ (e.g., for cut, $P=\mbox{XOR}$) can be sparsified into $O(|V|/ε^2)$ constraints if and only if the number of inputs that satisfy $P$ is anything but one (i.e., $|P^{-1}(1)| \neq 1$). Furthermore, this sparsity bound is tight unless $P$ is a relatively trivial predicate. We conclude that also systems of 2SAT (or 2LIN) constraints can be sparsified.
Sistem Informasi Geografis Potensi Wilayah Kabupaten Banyuasin Berbasis Web
Venue: arXiv cs.CY 2015
Year: 2015

Development of information technology in the field of spatial data processing has helped many digital mapping. In the present study, the authors will empower geographic information systems (GIS) for geographic data processing potential Banyuasin district. The potential of the region are agriculture, farming, and industry. The method used to develop the GIS is the waterfall approach models. After conducting a series of activities starting from the analysis, requirements, system design, coding, testing, then obtained an information systems that can provide information about the geographical spread of the potential of web-based Banyuasin district with the help of ArcGIS. This system was built by using the waterfall model. The result is a GIS that provide location information potential of the region.
A Lyapunov Optimization Approach for Green Cellular Networks with Hybrid Energy Supplies
Venue: arXiv cs.IT 2015
Year: 2015

Powering cellular networks with renewable energy sources via energy harvesting (EH) has recently been proposed as a promising solution for green networking. However, with intermittent and random energy arrivals, it is challenging to provide satisfactory quality of service (QoS) in EH networks. To enjoy the greenness brought by EH while overcoming the instability of the renewable energy sources, hybrid energy supply (HES) networks that are powered by both EH and the electric grid have emerged as a new paradigm for green communications. In this paper, we will propose new design methodologies for HES green cellular networks with the help of Lyapunov optimization techniques. The network service cost, which addresses both the grid energy consumption and achievable QoS, is adopted as the performance metric, and it is optimized via base station assignment and power control (BAPC). Our main contribution is a low-complexity online algorithm to minimize the long-term average network service cost, namely, the Lyapunov optimization-based BAPC (LBAPC) algorithm. One main advantage of this algorithm is that the decisions depend only on the instantaneous side information without requiring distribution information of channels and EH processes. To determine the network operation, we only need to solve a deterministic per-time slot problem, for which an efficient inner-outer optimization algorithm is proposed. Moreover, the proposed algorithm is shown to be asymptotically optimal via rigorous analysis. Finally, sample simulation results are presented to verify the theoretical analysis as well as validate the effectiveness of the proposed algorithm.
Formalization of simplification for context-free grammars
Venue: arXiv cs.FL 2015
Year: 2015

Context-free grammar simplification is a subject of high importance in computer language processing technology as well as in formal language theory. This paper presents a formalization, using the Coq proof assistant, of the fact that general context-free grammars generate languages that can be also generated by simpler and equivalent context-free grammars. Namely, useless symbol elimination, inaccessible symbol elimination, unit rules elimination and empty rules elimination operations were described and proven correct with respect to the preservation of the language generated by the original grammar.
Experimentation Procedure for Offloaded Mini-Apps Executed on Cluster Architectures with Xeon Phi Accelerators
Venue: arXiv cs.DC 2015
Year: 2015

A heterogeneous cluster architecture is complex. It contains hundreds, or thousands of devices connected by a tiered communication system in order to solve a problem. As a heterogeneous system, these devices will have varying performance capabilities. To better understand the interactions which occur between the various devices during execution, an experimentation procedure has been devised to capture, store, and analyze important and meaningful data. The procedure consists of various tools, techniques, and methods for capturing relevant timing, power, and performance data for a typical execution. This procedure currently applies to architectures with Intel Xeon processors and Intel Xeon Phi accelerators. It has been applied to the Co-Design Molecular Dynamics mini-app, courtesy of the ExMatEx team. This work aims to provide end-users with a strategy for investigating codes executed on heterogeneous cluster architectures with Xeon Phi accelerators.
Unsupervised Spoken Term Detection with Spoken Queries by Multi-level Acoustic Patterns with Varying Model Granularity
Venue: arXiv cs.CL 2015
Year: 2015

This paper presents a new approach for unsupervised Spoken Term Detection with spoken queries using multiple sets of acoustic patterns automatically discovered from the target corpus. The different pattern HMM configurations(number of states per model, number of distinct models, number of Gaussians per state)form a three-dimensional model granularity space. Different sets of acoustic patterns automatically discovered on different points properly distributed over this three-dimensional space are complementary to one another, thus can jointly capture the characteristics of the spoken terms. By representing the spoken content and spoken query as sequences of acoustic patterns, a series of approaches for matching the pattern index sequences while considering the signal variations are developed. In this way, not only the on-line computation load can be reduced, but the signal distributions caused by different speakers and acoustic conditions can be reasonably taken care of. The results indicate that this approach significantly outperformed the unsupervised feature-based DTW baseline by 16.16\% in mean average precision on the TIMIT corpus.
Wikipedia Page View Reflects Web Search Trend
Venue: arXiv cs.SI 2015
Year: 2015

The frequency of a web search keyword generally reflects the degree of public interest in a particular subject matter. Search logs are therefore useful resources for trend analysis. However, access to search logs is typically restricted to search engine providers. In this paper, we investigate whether search frequency can be estimated from a different resource such as Wikipedia page views of open data. We found frequently searched keywords to have remarkably high correlations with Wikipedia page views. This suggests that Wikipedia page views can be an effective tool for determining popular global web search trends.
A Practical System for Guaranteed Access in the Presence of DDoS Attacks and Flash Crowds
Venue: arXiv cs.CR 2015
Year: 2015

With the growing incidents of flash crowds and sophisticated DDoS attacks mimicking benign traffic, it becomes challenging to protect Internet-based services solely by differentiating attack traffic from legitimate traffic. While fair-sharing schemes are commonly suggested as a defense when differentiation is difficult, they alone may suffer from highly variable or even unbounded waiting times. We propose RainCheck Filter (RCF), a lightweight primitive that guarantees bounded waiting time for clients despite server flooding without keeping per-client state on the server. RCF achieves strong waiting time guarantees by prioritizing clients based on how long the clients have waited-as if the server maintained a queue in which the clients lined up waiting for service. To avoid keeping state for every incoming client request, the server sends to the client a raincheck, a timestamped cryptographic token that not only informs the client to retry later but also serves as a proof of the client's priority level within the virtual queue. We prove that every client complying with RCF can access the server in bounded time, even under a flash crowd incident or a DDoS attack. Our large-scale simulations confirm that RCF provides a small and predictable maximum waiting time while existing schemes cannot. To demonstrate its deployability, we implement RCF as a Python module such that web developers can protect a critical server resource by adding only three lines of code.
Using Software Categories for the Development of Generative Software
Venue: arXiv cs.SE 2015
Year: 2015

In model-driven development (MDD) software emerges by systematically transforming abstract models to concrete source code. Ideally, performing those transformations is to a large extent the task of code generators. One approach for developing a new code generator is to write a reference implementation and separate it into handwritten and generatable code. Typically, the generator developer manually performs this separation a process that is often time-consuming, labor-intensive, difficult to maintain and may produce more code than necessary. Software categories provide a way for separating code into designated parts with defined dependencies, for example, "Business Logic" code that may not directly use "Technical" code. This paper presents an approach that uses the concept of software categories to semi-automatically determine candidates for generated code. The main idea is to iteratively derive the categories for uncategorized code from the dependencies of categorized code. The candidates for generated or handwritten code finally are code parts belonging to specific (previously defined) categories. This approach helps the generator developer in finding candidates for generated code more easily and systematically than searching by hand and is a step towards tool-supported development of generative software.
Iterative Matrix Inversion Based Low Complexity Detection in Large/Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

Linear detectors such as zero forcing (ZF) or minimum mean square error (MMSE) are imperative for large/massive MIMO systems for both the downlink and uplink scenarios. However these linear detectors require matrix inversion which is computationally expensive for such huge systems. In this paper, we assert that calculating an exact inverse is not necessary to find the ZF/MMSE solution and an approximate inverse would yield a similar performance. This is possible if the quantized solution calculated using the approximate inverse is same as the one calculated using the exact inverse. We quantify the amount of approximation that can be tolerated for this to happen. Motivated by this, we propose to use the existing iterative methods for obtaining low complexity approximate inverses. We show that, after a sufficient number of iterations, the inverse using iterative methods can provide a similar error performance. In addition, we also show that the advantage of using an approximate inverse is not limited to linear detectors but can be extended to non linear detectors such as sphere decoders (SD). An approximate inverse can be used for any SD that requires matrix inversion. We prove that application of approximate inverse leads to a smaller radius, which in turn reduces the search space leading to reduction in complexity. Numerical results corroborate our claim that using approximate matrix inversion reduces decoding complexity in large/massive MIMO systems with no loss in error performance.
Central Pattern Generators for the control of robotic systems
Venue: arXiv cs.RO 2015
Year: 2015

Bio-inspired control of motion is an active field of research with many applications in real world tasks. In the case of robotic systems that need to exhibit oscillatory behaviour (i.e. locomotion of snake-type or legged robots), Central Pattern Generators (CPGs) are among the most versatile solutions. These controllers are often based on loosely-coupled oscillators similar to those found in the neural circuits of many animal species, and can be more robust to uncertainty (i.e. external perturbations) than traditional control approaches. This project provides an overview of the state-of-the-art in the field of CPGs, and in particular their applications within robotic systems. The project also tackles the implementation of a CPG-based controller in a small 3D-printed hexapod.
Evolving TSP heuristics using Multi Expression Programming
Venue: arXiv cs.AI 2015
Year: 2015

Multi Expression Programming (MEP) is an evolutionary technique that may be used for solving computationally difficult problems. MEP uses a linear solution representation. Each MEP individual is a string encoding complex expressions (computer programs). A MEP individual may encode multiple solutions of the current problem. In this paper MEP is used for evolving a Traveling Salesman Problem (TSP) heuristic for graphs satisfying triangle inequality. Evolved MEP heuristic is compared with Nearest Neighbor Heuristic (NN) and Minimum Spanning Tree Heuristic (MST) on some difficult problems in TSPLIB. For most of the considered problems the evolved MEP heuristic outperforms NN and MST. The obtained algorithm was tested against some problems in TSPLIB. The results emphasizes that evolved MEP heuristic is a powerful tool for solving difficult TSP instances.