OpenRaiser/Intern-Atlas huggingface dataset:
Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Bandits
Venue: arXiv cs.LG 2014
Year: 2014

Motivated by applications in energy management, this paper presents the Multi-Armed Risk-Aware Bandit (MARAB) algorithm. With the goal of limiting the exploration of risky arms, MARAB takes as arm quality its conditional value at risk. When the user-supplied risk level goes to 0, the arm quality tends toward the essential infimum of the arm distribution density, and MARAB tends toward the MIN multi-armed bandit algorithm, aimed at the arm with maximal minimal value. As a first contribution, this paper presents a theoretical analysis of the MIN algorithm under mild assumptions, establishing its robustness comparatively to UCB. The analysis is supported by extensive experimental validation of MIN and MARAB compared to UCB and state-of-art risk-aware MAB algorithms on artificial and real-world problems.
Efficient random sampling of binary and unary-binary trees via holonomic equations
Venue: arXiv cs.DS 2014
Year: 2014

We present a new uniform random sampler for binary trees with $n$ internal nodes consuming $2n + Θ(\log(n)^2)$ random bits on average. This makes it quasi-optimal and out-performs the classical Remy algorithm. We also present a sampler for unary-binary trees with $n$ nodes taking $Θ(n)$ random bits on average. Both are the first linear-time algorithms to be optimal up to a constant.
Effective Slot Filling Based on Shallow Distant Supervision Methods
Venue: arXiv cs.CL 2014
Year: 2014

Spoken Language Systems at Saarland University (LSV) participated this year with 5 runs at the TAC KBP English slot filling track. Effective algorithms for all parts of the pipeline, from document retrieval to relation prediction and response post-processing, are bundled in a modular end-to-end relation extraction system called RelationFactory. The main run solely focuses on shallow techniques and achieved significant improvements over LSV's last year's system, while using the same training data and patterns. Improvements mainly have been obtained by a feature representation focusing on surface skip n-grams and improved scoring for extracted distant supervision patterns. Important factors for effective extraction are the training and tuning scheme for distant supervision classifiers, and the query expansion by a translation model based on Wikipedia links. In the TAC KBP 2013 English Slotfilling evaluation, the submitted main run of the LSV RelationFactory system achieved the top-ranked F1-score of 37.3%.
The Capacity of Three-Receiver AWGN Broadcast Channels with Receiver Message Side Information
Venue: arXiv cs.IT 2014
Year: 2014

This paper investigates the capacity region of three-receiver AWGN broadcast channels where the receivers (i) have private-message requests and (ii) know the messages requested by some other receivers as side information. We classify these channels based on their side information into eight groups, and construct different transmission schemes for the groups. For six groups, we characterize the capacity region, and show that it improves both the best known inner and outer bounds. For the remaining two groups, we improve the best known inner bound by using side information during channel decoding at the receivers.
Time series forecasting using neural networks
Venue: arXiv cs.NE 2014
Year: 2014

Recent studies have shown the classification and prediction power of the Neural Networks. It has been demonstrated that a NN can approximate any continuous function. Neural networks have been successfully used for forecasting of financial data series. The classical methods used for time series prediction like Box-Jenkins or ARIMA assumes that there is a linear relationship between inputs and outputs. Neural Networks have the advantage that can approximate nonlinear functions. In this paper we compared the performances of different feed forward and recurrent neural networks and training algorithms for predicting the exchange rate EUR/RON and USD/RON. We used data series with daily exchange rates starting from 2005 until 2013.
Reduced-complexity maximum-likelihood decoding for 3D MIMO code
Venue: arXiv cs.IT 2014
Year: 2014

The 3D MIMO code is a robust and efficient space-time coding scheme for the distributed MIMO broadcasting. However, it suffers from the high computational complexity if the optimal maximum-likelihood (ML) decoding is used. In this paper we first investigate the unique properties of the 3D MIMO code and consequently propose a simplified decoding algorithm without sacrificing the ML optimality. Analysis shows that the decoding complexity is reduced from O(M^8) to O(M^{4.5}) in quasi-static channels when M-ary square QAM constellation is used. Moreover, we propose an efficient implementation of the simplified ML decoder which achieves a much lower decoding time delay compared to the classical sphere decoder with Schnorr-Euchner enumeration.
The sum $2^{\mathit{KA}(x)-\mathit{KP}(x)}$ over all prefixes $x$ of some binary sequence can be infinite
Venue: arXiv cs.IT 2014
Year: 2014

We consider two quantities that measure complexity of binary strings: $\mathit{KA}(x)$ is defined as the minus logarithm of continuous a priori probability on the binary tree, and $\mathit{KP}(x)$ denotes prefix complexity of a binary string $x$. In this paper we answer a question posed by Joseph Miller and prove that there exists an infinite binary sequence $ω$ such that the sum of $2^{\mathit{KA}(x)-\mathit{KP}(x)}$ over all prefixes $x$ of $ω$ is infinite. Such a sequence can be chosen among characteristic sequences of computably enumerable sets.
Belief Revision in Structured Probabilistic Argumentation
Venue: arXiv cs.LO 2014
Year: 2014

In real-world applications, knowledge bases consisting of all the information at hand for a specific domain, along with the current state of affairs, are bound to contain contradictory data coming from different sources, as well as data with varying degrees of uncertainty attached. Likewise, an important aspect of the effort associated with maintaining knowledge bases is deciding what information is no longer useful; pieces of information (such as intelligence reports) may be outdated, may come from sources that have recently been discovered to be of low quality, or abundant evidence may be available that contradicts them. In this paper, we propose a probabilistic structured argumentation framework that arises from the extension of Presumptive Defeasible Logic Programming (PreDeLP) with probabilistic models, and argue that this formalism is capable of addressing the basic issues of handling contradictory and uncertain data. Then, to address the last issue, we focus on the study of non-prioritized belief revision operations over probabilistic PreDeLP programs. We propose a set of rationality postulates -- based on well-known ones developed for classical knowledge bases -- that characterize how such operations should behave, and study a class of operators along with theoretical relationships with the proposed postulates, including a representation theorem stating the equivalence between this class and the class of operators characterized by the postulates.
Multilevel Pricing Schemes in a Deregulated Wireless Network Market
Venue: arXiv cs.GT 2014
Year: 2014

Typically the cost of a product, a good or a service has many components. Those components come from different complex steps in the supply chain of the product from sourcing to distribution. This economic point of view also takes place in the determination of goods and services in wireless networks. Indeed, before transmitting customer data, a network operator has to lease some frequency range from a spectrum owner and also has to establish agreements with electricity suppliers. The goal of this paper is to compare two pricing schemes, namely a power-based and a flat rate, and give a possible explanation why flat rate pricing schemes are more common than power based pricing ones in a deregulated wireless market. We suggest a hierarchical game-theoretical model of a three level supply chain: the end users, the service provider and the spectrum owner. The end users intend to transmit data on a wireless network. The amount of traffic sent by the end users depends on the available frequency bandwidth as well as the price they have to pay for their transmission. A natural question arises for the service provider: how to design an efficient pricing scheme in order to maximize his profit. Moreover he has to take into account the lease charge he has to pay to the spectrum owner and how many frequency bandwidth to rent. The spectrum owner itself also looks for maximizing its profit and has to determine the lease price to the service provider. The equilibrium at each level of our supply chain model are established and several properties are investigated. In particular, in the case of a power-based pricing scheme, the service provider and the spectrum owner tend to share the gross provider profit. Whereas, considering the flat rate pricing scheme, if the end users are going to exploit the network intensively, then the tariffs of the suppliers (spectrum owner and service provider) explode.
Smart machines and the SP theory of intelligence
Venue: arXiv cs.AI 2014
Year: 2014

These notes describe how the "SP theory of intelligence", and its embodiment in the "SP machine", may help to realise cognitive computing, as described in the book "Smart Machines". In the SP system, information compression and a concept of "multiple alignment" are centre stage. The system is designed to integrate such things as unsupervised learning, pattern recognition, probabilistic reasoning, and more. It may help to overcome the problem of variety in big data, it may serve in pattern recognition and in the unsupervised learning of structure in data, and it may facilitate the management and transmission of big data. There is potential, via information compression, for substantial gains in computational efficiency, especially in the use of energy. The SP system may help to realise data-centric computing, perhaps via a development of Hebb's concept of a "cell assembly", or via the use of light or DNA for the processing of information. It has potential in the management of errors and uncertainty in data, in medical diagnosis, in processing streams of data, and in promoting adaptability in robots.
Energy-Efficient Communication over the Unsynchronized Gaussian Diamond Network
Venue: arXiv cs.IT 2014
Year: 2014

Communication networks are often designed and analyzed assuming tight synchronization among nodes. However, in applications that require communication in the energy-efficient regime of low signal-to-noise ratios, establishing tight synchronization among nodes in the network can result in a significant energy overhead. Motivated by a recent result showing that near-optimal energy efficiency can be achieved over the AWGN channel without requiring tight synchronization, we consider the question of whether the potential gains of cooperative communication can be achieved in the absence of synchronization. We focus on the symmetric Gaussian diamond network and establish that cooperative-communication gains are indeed feasible even with unsynchronized nodes. More precisely, we show that the capacity per unit energy of the unsynchronized symmetric Gaussian diamond network is within a constant factor of the capacity per unit energy of the corresponding synchronized network. To this end, we propose a distributed relaying scheme that does not require tight synchronization but nevertheless achieves most of the energy gains of coherent combining.
Generalized Proportional Allocation Mechanism Design for Unicast Service on the Internet
Venue: arXiv cs.GT 2014
Year: 2014

In this report we construct two mechanisms that fully implement social welfare maximising allocation in Nash equilibria for the case of a single infinitely divisible good subject to multiple inequality constraints. The first mechanism achieves weak budget balance, while the second is an extension of the first, and achieves strong budget balance. One important application of this mechanism is unicast service on the Internet where a network operator wishes to allocate rates among strategic users in such a way that maximise overall user satisfaction while respecting capacity constraints on every link in the network. The emphasis of this work is on full implementation, which means that all Nash equilibria of the induced game result in the optimal allocations of the centralized allocation problem.
Model-based Product Quality Evaluation with Multi-Criteria Decision Analysis
Venue: arXiv cs.SE 2014
Year: 2014

The ability to develop or evolve software or software-based systems/services with defined and guaranteed quality in a predictable way is becoming increasingly important. Essential - though not exclusive - prerequisites for this are the ability to model the relevant quality properties appropriately and the capability to perform reliable quality evaluations. Existing approaches for integrated quality modeling and evaluation are typically either narrowly focused or too generic and have proprietary ways for modeling and evaluating quality. This article sketches an ap- proach for modeling and evaluating quality properties in a uniform way, without losing the ability to build sufficiently detailed customized models for specific quality properties. The focus of this article is on the description of a multi-criteria aggregation mechanism that can be used for the evaluation. In addition, the underlying quality meta-model, an example application scenario, related work, initial application results, and an outlook on future research are presented.
Temporal Graph Traversals: Definitions, Algorithms, and Applications
Venue: arXiv cs.DS 2014
Year: 2014

A temporal graph is a graph in which connections between vertices are active at specific times, and such temporal information leads to completely new patterns and knowledge that are not present in a non-temporal graph. In this paper, we study traversal problems in a temporal graph. Graph traversals, such as DFS and BFS, are basic operations for processing and studying a graph. While both DFS and BFS are well-known simple concepts, it is non-trivial to adopt the same notions from a non-temporal graph to a temporal graph. We analyze the difficulties of defining temporal graph traversals and propose new definitions of DFS and BFS for a temporal graph. We investigate the properties of temporal DFS and BFS, and propose efficient algorithms with optimal complexity. In particular, we also study important applications of temporal DFS and BFS. We verify the efficiency and importance of our graph traversal algorithms in real world temporal graphs.
Multi-user Scheduling Schemes for Simultaneous Wireless Information and Power Transfer Over Fading Channels
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study downlink multi-user scheduling for a time-slotted system with simultaneous wireless information and power transfer. In particular, in each time slot, a single user is scheduled to receive information, while the remaining users opportunistically harvest the ambient radio frequency energy. We devise novel online scheduling schemes in which the tradeoff between the users' ergodic rates and their average amount of harvested energy can be controlled. In particular, we modify the well-known maximum signal-to-noise ratio (SNR) and maximum normalized-SNR (N-SNR) schedulers by scheduling the user whose SNR/N-SNR has a certain ascending order (selection order) rather than the maximum one. We refer to these new schemes as order-based SNR/N-SNR scheduling and show that the lower the selection order, the higher the average amount of harvested energy in the system at the expense of a reduced ergodic sum rate. The order-based N-SNR scheduling scheme provides proportional fairness among the users in terms of both the ergodic achievable rate and the average harvested energy. Furthermore, we propose an order-based equal throughput (ET) fair scheduler, which schedules the user having the minimum moving average throughput out of the users whose N-SNR orders fall into a given set of allowed orders. We show that this scheme provides the users with proportionally fair average harvested energies. In this context, we also derive feasibility conditions for achieving ET with the order-based ET scheduler. Using the theory of order statistics, the average per-user harvested energy and ergodic achievable rate of all proposed scheduling schemes are analyzed and obtained in closed form for independent and non-identically distributed Rayleigh, Ricean, Nakagami-m, and Weibull fading channels. Our closed-form analytical results are corroborated by simulations.
A review of security attacks and Intrusion Detection Schemes in Wireless Sensor Networks
Venue: arXiv cs.CR 2014
Year: 2014

Wireless Sensor Networks (WSNs) are currently used in different industrial and consumer applications, such as earth monitoring, health related applications, natural disaster prevention, and many other areas. Security is one of the major aspects of Wireless sensor networks due to the resource limitations of sensor nodes. However, these networks are facing several threats that affect their functioning and their life. In this paper we present security attacks in wireless sensor networks, and we focus on a review and analysis of the recent Intrusion Detection schemes in WSNs.
NoSQL Databases
Venue: arXiv cs.DB 2014
Year: 2014

In this document, I present the main notions of NoSQL databases and compare four selected products (Riak, MongoDB, Cassandra, Neo4J) according to their capabilities with respect to consistency, availability, and partition tolerance, as well as performance. I also propose a few criteria for selecting the right tool for the right situation.
Minimizing the Time of Detection of Large (Probably) Prime Numbers
Venue: arXiv cs.CR 2014
Year: 2014

In this paper we present the experimental results that more clearly than any theory suggest an answer to the question: when in detection of large (probably) prime numbers to apply, a very resource demanding, Miller-Rabin algorithm. Or, to put it another way, when the dividing by first several tens of prime numbers should be replaced by primality testing? As an innovation, the procedure above will be supplemented by considering the use of the well-known Goldbach's conjecture in the solving of this and some other important questions about the RSA cryptosystem, always guided by the motto "do not harm" - neither the security nor the time spent.
Emotional Responses in Artificial Agent-Based Systems: Reflexivity and Adaptation in Artificial Life
Venue: arXiv cs.AI 2014
Year: 2014

The current work addresses a virtual environment with self-replicating agents whose decisions are based on a form of "somatic computation" (soma - body) in which basic emotional responses, taken in parallelism to actual living organisms, are introduced as a way to provide the agents with greater reflexive abilities. The work provides a contribution to the field of Artificial Intelligence (AI) and Artificial Life (ALife) in connection to a neurobiology-based cognitive framework for artificial systems and virtual environments' simulations. The performance of the agents capable of emotional responses is compared with that of self-replicating automata, and the implications of research on emotions and AI, in connection to both virtual agents as well as robots, is addressed regarding possible future directions and applications.
Energy-aware Load Balancing Policies for the Cloud Ecosystem
Venue: arXiv cs.DC 2014
Year: 2014

The energy consumption of computer and communication systems does not scale linearly with the workload. A system uses a significant amount of energy even when idle or lightly loaded. A widely reported solution to resource management in large data centers is to concentrate the load on a subset of servers and, whenever possible, switch the rest of the servers to one of the possible sleep states. We propose a reformulation of the traditional concept of load balancing aiming to optimize the energy consumption of a large-scale system: {\it distribute the workload evenly to the smallest set of servers operating at an optimal energy level, while observing QoS constraints, such as the response time.} Our model applies to clustered systems; the model also requires that the demand for system resources to increase at a bounded rate in each reallocation interval. In this paper we report the VM migration costs for application scaling.
A scenario approach for non-convex control design
Venue: arXiv cs.SY 2014
Year: 2014

Randomized optimization is an established tool for control design with modulated robustness. While for uncertain convex programs there exist randomized approaches with efficient sampling, this is not the case for non-convex problems. Approaches based on statistical learning theory are applicable to non-convex problems, but they usually are conservative in terms of performance and require high sample complexity to achieve the desired probabilistic guarantees. In this paper, we derive a novel scenario approach for a wide class of random non-convex programs, with a sample complexity similar to that of uncertain convex programs and with probabilistic guarantees that hold not only for the optimal solution of the scenario program, but for all feasible solutions inside a set of a-priori chosen complexity. We also address measure-theoretic issues for uncertain convex and non-convex programs. Among the family of non-convex control- design problems that can be addressed via randomization, we apply our scenario approach to randomized Model Predictive Control for chance-constrained nonlinear control-affine systems.
Can Synergy in Triple-Helix Relations be Quantified? A Review of the Development of the Triple-Helix Indicator
Venue: arXiv cs.CY 2014
Year: 2014

Triple-Helix arrangements of bi- and trilateral relations can be considered as adaptive eco-systems. During the last decade, we have further developed a Triple-Helix indicator of synergy as reduction of uncertainty in niches that can be shaped among three or more distributions. Reduction of uncertainty can be generated in correlations among distributions of relations, but this (next-order) effect can be counterbalanced by uncertainty generated in the relations. We first explain the indicator, and then review possible results when this indicator is applied to (i) co-author networks of academic, industrial, and governmental authors and (ii) synergies in the distributions of firms over geographical addresses, technological classes, and industrial-size classes for a number of nations. Co-variation is then considered as a measure of relationship. The balance between globalizing and localizing dynamics can be quantified. Too much synergy locally can also be considered as lock-in. Tendencies are different for the globalizing knowledge dynamics versus locally retaining wealth from knowledge in industrial innovations.
Approximation Algorithm Project
Venue: arXiv cs.DS 2014
Year: 2014

This application for learning APPROXIMATION ALGORITHM has been designed in Java which will make user comfortable in learning the very complex subject "NP-Completeness" and the solution to NP-Complete problem using approximation algorithm.