OpenRaiser/Intern-Atlas huggingface dataset:
Elements of Game Theory - Part I: Foundations, acts and mechanisms
Venue: arXiv cs.GT 2015
Year: 2015

In this paper, a gentle introduction to Game Theory is presented in the form of basic concepts and examples. Minimax and Nash's theorem are introduced as the formal definitions for optimal strategies and equilibria in zero-sum and nonzero-sum games. Several elements of cooperative gaming, coalitions, voting ensembles, voting power and collective efficiency are described in brief. Analytical (matrix) and extended (tree-graph) forms of game representation is illustrated as the basic tools for identifying optimal strategies and "solutions" in games of any kind. Next, a typology of four standard nonzero-sum games is investigated, analyzing the Nash equilibria and the optimal strategies in each case. Signaling, stance and third-party intermediates are described as very important properties when analyzing strategic moves, while credibility and reputation is described as crucial factors when signaling promises or threats. Utility is introduced as a generalization of typical cost/gain functions and it is used to explain the incentives of irrational players under the scope of "rational irrationality". Finally, a brief reference is presented for several other more advanced concepts of gaming, including emergence of cooperation, evolutionary stable strategies, two-level games, metagames, hypergames and the Harsanyi transformation.
Deep Convolutional Networks on Graph-Structured Data
Venue: arXiv cs.LG 2015
Year: 2015

Deep Learning's recent successes have mostly relied on Convolutional Networks, which exploit fundamental statistical properties of images, sounds and video data: the local stationarity and multi-scale compositional structure, that allows expressing long range interactions in terms of shorter, localized interactions. However, there exist other important examples, such as text documents or bioinformatic data, that may lack some or all of these strong statistical regularities. In this paper we consider the general question of how to construct deep architectures with small learning complexity on general non-Euclidean domains, which are typically unknown and need to be estimated from the data. In particular, we develop an extension of Spectral Networks which incorporates a Graph Estimation procedure, that we test on large-scale classification problems, matching or improving over Dropout Networks with far less parameters to estimate.
CFORB: Circular FREAK-ORB Visual Odometry
Venue: arXiv cs.CV 2015
Year: 2015

We present a novel Visual Odometry algorithm entitled Circular FREAK-ORB (CFORB). This algorithm detects features using the well-known ORB algorithm [12] and computes feature descriptors using the FREAK algorithm [14]. CFORB is invariant to both rotation and scale changes, and is suitable for use in environments with uneven terrain. Two visual geometric constraints have been utilized in order to remove invalid feature descriptor matches. These constraints have not previously been utilized in a Visual Odometry algorithm. A variation to circular matching [16] has also been implemented. This allows features to be matched between images without having to be dependent upon the epipolar constraint. This algorithm has been run on the KITTI benchmark dataset and achieves a competitive average translational error of $3.73 \%$ and average rotational error of $0.0107 deg/m$. CFORB has also been run in an indoor environment and achieved an average translational error of $3.70 \%$. After running CFORB in a highly textured environment with an approximately uniform feature spread across the images, the algorithm achieves an average translational error of $2.4 \%$ and an average rotational error of $0.009 deg/m$.
Deep Denoising Auto-encoder for Statistical Speech Synthesis
Venue: arXiv cs.SD 2015
Year: 2015

This paper proposes a deep denoising auto-encoder technique to extract better acoustic features for speech synthesis. The technique allows us to automatically extract low-dimensional features from high dimensional spectral features in a non-linear, data-driven, unsupervised way. We compared the new stochastic feature extractor with conventional mel-cepstral analysis in analysis-by-synthesis and text-to-speech experiments. Our results confirm that the proposed method increases the quality of synthetic speech in both experiments.
Non-dominating sequences of vectors using only resets and increments
Venue: arXiv cs.DM 2015
Year: 2015

We consider a variant of Dickson lemma, where each entry of a vector can be reseted or incremented by 1 in respect to the previous one. We give an example of non dominating sequence of length $2^{2^{θ(n)}}$. It perfectly match the previously known upperbound.
Why Bother With Syntax?
Venue: arXiv cs.AI 2015
Year: 2015

This short note discusses the role of syntax vs. semantics and the interplay between logic, philosophy, and language in computer science and game theory.
Knowledge representation and processing methods in Semantic Web
Venue: arXiv cs.SE 2015
Year: 2015

The goal is to take a closer look at progress of knowledge engineering in the field of Semantic Web. Along with theory of Knowledge Representation (KR) and knowledge processing methods such as Description Logic (DL), reasoning mechanisms and ontology modelling languages (OWL, RDF, RDFS), the thesis shows the practical usage of the mentioned approaches in building systems driven by ontologies. A working prototype of ontology-driven application, written in Java, has been developed within the scope of this thesis. The system main assumption is an attempt to integrate database and ontology approach, for storing and inferring desired information about domain of traffic dangers. For the needs of the system, domain model of traffic danger concept has been also designed.
Best of both worlds? Simultaneous evaluation of researchers and their works
Venue: arXiv cs.DL 2015
Year: 2015

This paper explores a dual score system that simultaneously evaluates the relative importance of researchers and their works. It is a modification of the CITEX algorithm recently described in Pal and Ruj (2015). Using available publication data for $m$ author keywords (as a proxy for researchers) and $n$ papers it is possible to construct a $m \times n$ author-paper feature matrix. This is further combined with citation data to construct a HITS-like algorithm that iteratively satisfies two criteria: first, \emph{a good author is cited by good authors}, and second, \emph{a good paper is cited by good authors}. Following Pal and Ruj, the resulting algorithm produces an author eigenscore and a paper eigenscore. The algorithm is tested on 213,530 citable publications listed under Thomson ISI's "\emph{Information Science \& Library Science}" JCR category from 1980--2012.
Real time unsupervised learning of visual stimuli in neuromorphic VLSI systems
Venue: arXiv cs.NE 2015
Year: 2015

Neuromorphic chips embody computational principles operating in the nervous system, into microelectronic devices. In this domain it is important to identify computational primitives that theory and experiments suggest as generic and reusable cognitive elements. One such element is provided by attractor dynamics in recurrent networks. Point attractors are equilibrium states of the dynamics (up to fluctuations), determined by the synaptic structure of the network; a `basin' of attraction comprises all initial states leading to a given attractor upon relaxation, hence making attractor dynamics suitable to implement robust associative memory. The initial network state is dictated by the stimulus, and relaxation to the attractor state implements the retrieval of the corresponding memorized prototypical pattern. In a previous work we demonstrated that a neuromorphic recurrent network of spiking neurons and suitably chosen, fixed synapses supports attractor dynamics. Here we focus on learning: activating on-chip synaptic plasticity and using a theory-driven strategy for choosing network parameters, we show that autonomous learning, following repeated presentation of simple visual stimuli, shapes a synaptic connectivity supporting stimulus-selective attractors. Associative memory develops on chip as the result of the coupled stimulus-driven neural activity and ensuing synaptic dynamics, with no artificial separation between learning and retrieval phases.
Parallel Programming Model for the Epiphany Many-Core Coprocessor Using Threaded MPI
Venue: arXiv cs.DC 2015
Year: 2015

The Adapteva Epiphany many-core architecture comprises a 2D tiled mesh Network-on-Chip (NoC) of low-power RISC cores with minimal uncore functionality. It offers high computational energy efficiency for both integer and floating point calculations as well as parallel scalability. Yet despite the interesting architectural features, a compelling programming model has not been presented to date. This paper demonstrates an efficient parallel programming model for the Epiphany architecture based on the Message Passing Interface (MPI) standard. Using MPI exploits the similarities between the Epiphany architecture and a conventional parallel distributed cluster of serial cores. Our approach enables MPI codes to execute on the RISC array processor with little modification and achieve high performance. We report benchmark results for the threaded MPI implementation of four algorithms (dense matrix-matrix multiplication, N-body particle interaction, a five-point 2D stencil update, and 2D FFT) and highlight the importance of fast inter-core communication for the architecture.
Drawing the Horton Set in an Integer Grid of Minimum Size
Venue: arXiv cs.CG 2015
Year: 2015

In 1978 Erd\H os asked if every sufficiently large set of points in general position in the plane contains the vertices of a convex $k$-gon, with the additional property that no other point of the set lies in its interior. Shortly after, Horton provided a construction---which is now called the Horton set---with no such $7$-gon. In this paper we show that the Horton set of $n$ points can be realized with integer coordinates of absolute value at most $\frac{1}{2} n^{\frac{1}{2} \log (n/2)}$. We also show that any set of points with integer coordinates combinatorially equivalent (with the same order type) to the Horton set, contains a point with a coordinate of absolute value at least $c \cdot n^{\frac{1}{24}\log (n/2)}$, where $c$ is a positive constant.
Decentralized Energy Allocation for Wireless Networks with Renewable Energy Powered Base Stations
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, a green wireless communication system in which base stations are powered by renewable energy sources is considered. This system consists of a capacity-constrained renewable power supplier (RPS) and a base station (BS) that faces a predictable random connection demand from mobile user equipments (UEs). In this model, the BS powered via a combination of a renewable power source and the conventional electric grid, seeks to specify the renewable power inventory policy, i.e., the power storage level. On the other hand, the RPS must strategically choose the energy amount that is supplied to the BS. An M/M/1 make-to-stock queuing model is proposed to investigate the decentralized decisions when the two parties optimize their individual costs in a noncooperative manner. The problem is formulated as a noncooperative game whose Nash equilibrium (NE) strategies are characterized in order to identify the causes of inefficiency in the decentralized operation. A set of simple linear contracts are introduced to coordinate the system so as to achieve an optimal system performance. The proposed approach is then extended to a setting with one monopolistic RPS and N BSs that are privately informed of their optimal energy inventory levels. In this scenario, we show that the widely-used proportional allocation mechanism is no longer socially optimal. In order to make the BSs truthfully report their energy demand, an incentive compatible (IC) mechanism is proposed for our model.
Asynchronous processing of Coq documents: from the kernel up to the user interface
Venue: arXiv cs.LO 2015
Year: 2015

The work described in this paper improves the reactivity of the Coq system by completely redesigning the way it processes a formal document. By subdividing such work into independent tasks the system can give precedence to the ones of immediate interest for the user and postpones the others. On the user side, a modern interface based on the PIDE middleware aggregates and present in a consistent way the output of the prover. Finally postponed tasks are processed exploiting modern, parallel, hardware to offer better scalability.
A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem
Venue: arXiv cs.DS 2015
Year: 2015

The clustered planarity problem (c-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cd-tree data structure and give a new characterization of c-planarity. It leads to efficient algorithms for c-planarity testing in the following cases. (i) Every cluster and every co-cluster (complement of a cluster) has at most two connected components. (ii) Every cluster has at most five outgoing edges. Moreover, the cd-tree reveals interesting connections between c-planarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to c-planarity, on the other hand it provides a new perspective on previous results.
Destructive nodes in multi-agent controllability
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, several necessary and sufficient graphical conditions are derived for the controllability of multi-agent systems by taking advantage of the proposed concept of controllability destructive nodes. A key step of arriving at this result is the establishment of a relationship between topology structures of the controllability destructive nodes and a specific eigenvector of the Laplacian matrix. The results on double, triple and quadruple controllability destructive nodes constitute a novel approach to study the controllability. In particular, the approach is applied to the graph consisting of five nodes to get a complete graphical characterization of controllability.
A CEGAR-like Approach for Cost LTL Bounds
Venue: arXiv cs.LO 2015
Year: 2015

Qualitative formal verification, that seeks boolean answers about the behavior of a system, is often insufficient for practical purposes. Observing quantitative information is of interest, e.g. for the proper calibration of a battery or a real-time scheduler. Historically, the focus has been on quantities in a continuous domain, but recent years showed a renewed interest for discrete quantitative domains. Cost Linear Temporal Logic (CLTL) is a quantitative extension of classical LTL. It integrates into a nice theory developed in the past few years that extends the qualitative setting, with counterparts in terms of logics, automata and algebraic structure. We propose a practical usage of this logics for model-checking purposes. A CLTL formula defines a function from infinite words to integers. Finding the bounds of such a function over a given set of words can be seen as an extension of LTL universal and existential model-checking. We propose a CEGAR-like algorithm to find these bounds by relying on classical LTL model-checking, and use Büchi automata with counters to implement it. This method constitutes a first step towards the practical use of such a discrete quantitative logic.
Automated Assignment of Backbone NMR Data using Artificial Intelligence
Venue: arXiv cs.AI 2015
Year: 2015

Nuclear magnetic resonance (NMR) spectroscopy is a powerful method for the investigation of three-dimensional structures of biological molecules such as proteins. Determining a protein structure is essential for understanding its function and alterations in function which lead to disease. One of the major challenges of the post-genomic era is to obtain structural and functional information on the many unknown proteins encoded by thousands of newly identified genes. The goal of this research is to design an algorithm capable of automating the analysis of backbone protein NMR data by implementing AI strategies such as greedy and A* search.
Delayed Offloading using Cloud Cooperated Millimeter Wave Gates
Venue: arXiv cs.NI 2015
Year: 2015

Increasing wireless cellular networks capacity is one of the major challenges for the coming years, especially if we consider the annual doubling of mobile user traffic. Towards that and thanks to the fact that a significant amount of mobile data is indeed delay tolerable, in this paper, we suggest embedding the delayed offloading of some user traffic to be a part of future wireless cellular networks. To accomplish this, user delayed files will be offloaded using ultra-high speed Millimeter Wave (Mm-W) Gates. The Mm-W Gate, which will be distributed inside the Macro basestation (BS) area, consists of number of Mm-W Access Points (APs) controlled by a local coordinator installed inside the Gate. To effectively manage the delayed offloading mechanism, utilizing the concept of User/Control (U/C) data splitting, the Gates coordinators and the Macro BS are connected to the Cloud Radio Access Network (C-RAN) through optical fiber links. Also, files offloading organizer software is used by the User Equipment (UE). A novel weighted proportional fairness (WPF) user scheduling algorithm is proposed to maximize the Gate Offloading Efficiency (GOFE) with maintaining long term fairness among the different mobility users pass through the Gate. If the Gate is properly designed and the files delay deadlines are properly set; near 100% GOFE with average reduction of 99.7% in UE energy consumption can be obtained, in time the user just passes through the Gate.
CO2 Forest: Improved Random Forest by Continuous Optimization of Oblique Splits
Venue: arXiv cs.LG 2015
Year: 2015

We propose a novel algorithm for optimizing multivariate linear threshold functions as split functions of decision trees to create improved Random Forest classifiers. Standard tree induction methods resort to sampling and exhaustive search to find good univariate split functions. In contrast, our method computes a linear combination of the features at each node, and optimizes the parameters of the linear combination (oblique) split functions by adopting a variant of latent variable SVM formulation. We develop a convex-concave upper bound on the classification loss for a one-level decision tree, and optimize the bound by stochastic gradient descent at each internal node of the tree. Forests of up to 1000 Continuously Optimized Oblique (CO2) decision trees are created, which significantly outperform Random Forest with univariate splits and previous techniques for constructing oblique trees. Experimental results are reported on multi-class classification benchmarks and on Labeled Faces in the Wild (LFW) dataset.
Big Step Greedy Algorithm for Maximum Coverage Problem
Venue: arXiv cs.DS 2015
Year: 2015

This paper proposes a greedy heuristic named as Big step greedy heuristic and investigates the application of Big step greedy heuristic for maximum k-coverage problem. Greedy algorithms construct the solution in multiple steps, the classical greedy algorithm for maximum k-coverage problem, in each step selects one set that contains the greatest number of uncovered elements. The Big step greedy heuristic, in each step selects p (1 <= p <= k) sets such that the union of selected p sets contains the greatest number of uncovered elements by evaluating all possible p-combinations of given sets. When p=k Big step greedy algorithm behaves like exact algorithm that computes optimal solution by evaluating all possible k-combinations of given sets. When p=1 it behaves like the classical greedy algorithm.
Trivergence of Probability Distributions, at glance
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we introduce the intuitive notion of trivergence of probability distributions (TPD). This notion allow us to calculate the similarity among triplets of objects. For this computation, we can use the well known measures of probability divergences like Kullback-Leibler and Jensen-Shannon. Divergence measures may be used in Information Retrieval tasks as Automatic Text Summarization, Text Classification, among many others.
On Modeling Heterogeneous Wireless Networks Using Non-Poisson Point Processes
Venue: arXiv cs.IT 2015
Year: 2015

Future wireless networks are required to support 1000 times higher data rate, than the current LTE standard. In order to meet the ever increasing demand, it is inevitable that, future wireless networks will have to develop seamless interconnection between multiple technologies. A manifestation of this idea is the collaboration among different types of network tiers such as macro and small cells, leading to the so-called heterogeneous networks (HetNets). Researchers have used stochastic geometry to analyze such networks and understand their real potential. Unsurprisingly, it has been revealed that interference has a detrimental effect on performance, especially if not modeled properly. Interference can be correlated in space and/or time, which has been overlooked in the past. For instance, it is normally assumed that the nodes are located completely independent of each other and follow a homogeneous Poisson point process (PPP), which is not necessarily true in real networks since the node locations are spatially dependent. In addition, the interference correlation created by correlated stochastic processes has mostly been ignored. To this end, we take a different approach in modeling the interference where we use non-PPP, as well as we study the impact of spatial and temporal correlation on the performance of HetNets. To illustrate the impact of correlation on performance, we consider three case studies from real-life scenarios. Specifically, we use massive multiple-input multiple-output (MIMO) to understand the impact of spatial correlation; we use the random medium access protocol to examine the temporal correlation; and we use cooperative relay networks to illustrate the spatial-temporal correlation. We present several numerical examples through which we demonstrate the impact of various correlation types on the performance of HetNets.
On the Converse of Talagrand's Influence Inequality
Venue: arXiv cs.DM 2015
Year: 2015

In 1994, Talagrand showed a generalization of the celebrated KKL theorem. In this work, we prove that the converse of this generalization also holds. Namely, for any sequence of numbers $0<a_1,a_2,\ldots,a_n\le 1$ such that $\sum_{j=1}^n a_j/(1-\log a_j)\ge C$ for some constant $C>0$, it is possible to find a roughly balanced Boolean function $f$ such that $\textrm{Inf}_j[f] < a_j$ for every $1 \le j \le n$.
LOADng Routing Protocol Evaluation for Bidirectional Data flow in AMI Mesh Networks
Venue: arXiv cs.NI 2015
Year: 2015

This research work denotes a novel evaluation of LOADng the routing protocol for Wireless Sensor Network. The LOADng protocol implementation is a part of ITU-T G.9903 recommendation based on the framework of the LLN On-demand Ad hoc Distance-vector Routing Protocol - Next Generation (LOADng) proposed by IETF specified by the IETF Internet-Draft draft-clausen-lln-loadng-11 and currently still in its design phase. LOADng is a reactive on demand distance vector routing protocol derived from AODV the Ad hoc On-demand distance vector protocol proposed by IETF. This work was motivated by the need for a novel protocol implementation for smart metering applications providing better performance and less complexity than RPL the Routing Protocol for Low power and lossy networks and adapted to (LLNs) requirements and constraints. Our implementation was successfully integrated into the communication layer of Contiki OS the Wireless Sensor Network operating system and evaluated through extensive simulations for AMI Mesh Networks.