OpenRaiser/Intern-Atlas huggingface dataset:
Joint Sensing and Power Allocation in Nonconvex Cognitive Radio Games: Quasi-Nash Equilibria
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we propose a novel class of Nash problems for Cognitive Radio (CR) networks composed of multiple primary users (PUs) and secondary users (SUs) wherein each SU (player) competes against the others to maximize his own opportunistic throughput by choosing jointly the sensing duration, the detection thresholds, and the vector power allocation over a multichannel link. In addition to power budget constraints, several (deterministic or probabilistic) interference constraints can be accommodated in the proposed general formulation, such as constraints on the maximum individual/aggregate (probabilistic) interference tolerable from the PUs. To keep the optimization as decentralized as possible, global interference constraints, when present, are imposed via pricing; the prices are thus additional variables to be optimized. The resulting players' optimization problems are nonconvex and there are price clearance conditions associated with the nonconvex global interference constraints to be satisfied by the equilibria of the game, which make the analysis of the proposed game a challenging task; none of classical results in the game theory literature can be successfully applied. To deal with the nonconvexity of the game, we introduce a relaxed equilibrium concept, the Quasi-Nash Equilibrium (QNE), and study its main properties, performance, and connection with local Nash equilibria. Quite interestingly, the proposed game theoretical formulations yield a considerable performance improvement with respect to current centralized and decentralized designs of CR systems, which validates the concept of QNE.
Building design in tropical climates. Elaboration of the ECODOM standard in the french tropical islands
Venue: arXiv cs.OH 2012
Year: 2012

This paper deals with the elaboration of global quality standards for natural and low energy cooling in french tropical island buildings. Electric load profiles of tropical islands in developed countries are characterised by morning, midday and evening peaks arising from all year round high power demand in the commercial and residential sectors, mostly due to air conditioning appliances and bad thermal conception of the building. In early 1995, a DSM pilot initiative has been launched in the french islands of Guadeloupe and Reunion through a partnership between the French Public Utility EDF, institutions involved in energy conservation, environment preservation (ADEME) and construction quality improvment, the University of Reunion Island and several other public and private partners (low cost housing institutions, architects, energy consultant, etc...) to set up a standard in the thermal conception of buildings in tropical climates. This has led to definition of optimized bioclimatic urban planning and architectural design, the use of passive cooling architectural components, natural ventilation and energy efficient systems. The impact of each technical solution on the thermal comfort within the building was evaluated with an airflow and thermal building simulation software (CODYRUN). These technical solutions have been edited in a pedagogical reference document and have been implemented in 300 new pilot dwelling projects through the year 1996 in Reunion Island and in Guadeloupe island. An experimental follow up is still in process in the first ECODOM dwellings for an experimental validation of the impact of the passive cooling solutions on the comfort of the occupants and to modify them if necessary.
Design of Intelligent Agents Based System for Commodity Market Simulation with JADE
Venue: arXiv cs.MA 2012
Year: 2012

A market of potato commodity for industry scale usage is engaging several types of actors. They are farmers, middlemen, and industries. A multi-agent system has been built to simulate these actors into agent entities, based on manually given parameters within a simulation scenario file. Each type of agents has its own fuzzy logic representing actual actors' knowledge, to be used to interpreting values and take appropriated decision of it while on simulation. The system will simulate market activities with programmed behaviors then produce the results as spreadsheet and chart graph files. These results consist of each agent's yearly finance and commodity data. The system will also predict each of next value from these outputs.
YAGI Antenna Design for Signal Phone Jammer
Venue: arXiv cs.OH 2012
Year: 2012

Mobile phone is one of the most widely used today in mobile communications. This technology is very useful for communication but this raises several problems in a situation where silence is required such as in libraries, places of worship, classrooms and others. Mobile phone jammer is a device that used to block the incoming signal to a mobile phone from the base station. If the mobile phone jammer is turned on then it can not form the incoming or outgoing calls even sms. In this research, we designed a Yagi antenna (900MHz) to expand the range of jamming because Yagi has a great gain. Results of impedance by gamma match are 50.16 Om. Obtained the value of VSWR Yagi is 1.46:1 and jamming distance that can be taken approximately 16 meters, It is different from the jamming distance of helical antenna on a mobile phone jammer itself is about 4 meters.
Speeding up shortest path algorithms
Venue: arXiv cs.DS 2012
Year: 2012

Given an arbitrary, non-negatively weighted, directed graph $G=(V,E)$ we present an algorithm that computes all pairs shortest paths in time $\mathcal{O}(m^* n + m \lg n + nT_ψ(m^*, n))$, where $m^*$ is the number of different edges contained in shortest paths and $T_ψ(m^*, n)$ is a running time of an algorithm to solve a single-source shortest path problem (SSSP). This is a substantial improvement over a trivial $n$ times application of $ψ$ that runs in $\mathcal{O}(nT_ψ(m,n))$. In our algorithm we use $ψ$ as a black box and hence any improvement on $ψ$ results also in improvement of our algorithm. Furthermore, a combination of our method, Johnson's reweighting technique and topological sorting results in an $\mathcal{O}(m^*n + m \lg n)$ all-pairs shortest path algorithm for arbitrarily-weighted directed acyclic graphs. In addition, we also point out a connection between the complexity of a certain sorting problem defined on shortest paths and SSSP.
Canonical Primal-Dual Method for Solving Non-convex Minimization Problems
Venue: arXiv cs.NA 2012
Year: 2012

A new primal-dual algorithm is presented for solving a class of non-convex minimization problems. This algorithm is based on canonical duality theory such that the original non-convex minimization problem is first reformulated as a convex-concave saddle point optimization problem, which is then solved by a quadratically perturbed primal-dual method. %It is proved that the popular SDP method is indeed a special case of the canonical duality theory. Numerical examples are illustrated. Comparing with the existing results, the proposed algorithm can achieve better performance.
Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable
Venue: arXiv cs.LO 2012
Year: 2012

We consider the quantifier alternation hierarchy within two-variable first-order logic FO^2[<,suc] over finite words with linear order and binary successor predicate. We give a single identity of omega-terms for each level of this hierarchy. This shows that it is decidable for a given regular language and a non-negative integer m, whether the language is definable by a formula in FO^2[<,suc] which has at most m quantifier alternations. We also consider the alternation hierarchy of unary temporal logic TL[X,F,Y,P] defined by the maximal number of nested negations. This hierarchy coincides with the FO^2[<,suc] alternation hierarchy.
A Frequency-Domain Encoding for Neuroevolution
Venue: arXiv cs.AI 2012
Year: 2012

Neuroevolution has yet to scale up to complex reinforcement learning tasks that require large networks. Networks with many inputs (e.g. raw video) imply a very high dimensional search space if encoded directly. Indirect methods use a more compact genotype representation that is transformed into networks of potentially arbitrary size. In this paper, we present an indirect method where networks are encoded by a set of Fourier coefficients which are transformed into network weight matrices via an inverse Fourier-type transform. Because there often exist network solutions whose weight matrices contain regularity (i.e. adjacent weights are correlated), the number of coefficients required to represent these networks in the frequency domain is much smaller than the number of weights (in the same way that natural images can be compressed by ignore high-frequency components). This "compressed" encoding is compared to the direct approach where search is conducted in the weight space on the high-dimensional octopus arm task. The results show that representing networks in the frequency domain can reduce the search-space dimensionality by as much as two orders of magnitude, both accelerating convergence and yielding more general solutions.
Outage Performance of AF-based Time Division Broadcasting Protocol in the Presence of Co-channel Interference
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we investigate the outage performance of time division broadcasting (TDBC) protocol in independent but non-identical Rayleigh flat-fading channels, where all nodes are interfered by a finite number of co-channel interferers. We assume that the relay operates in the amplified-and-forward mode. A tight lower bound as well as the asymptotic expression of the outage probability is obtained in closed-form. Through both theoretic analyses and simulation results, we show that the achievable diversity of TDBC protocol is zero in the interference-limited scenario. Moreover, we study the impacts of interference power, number of interferers and relay placement on the outage probability. Finally, the correctness of our analytic results is validated via computer simulations.
Merging Process Algebra and Action-based Computation Tree Logic
Venue: arXiv cs.LO 2012
Year: 2012

Process algebra and temporal logic are two popular paradigms for the specification, verification and systematic development of reactive and concurrent systems. These two approaches take different standpoint for looking at specifications and verifications, and offer complementary advantages. In order to mix algebraic and logic styles of specification in a uniform framework, the notion of a logic labelled transition system (LLTS) has been presented and explored by Luttgen and Vogler. This paper intends to propose a LLTS-oriented process calculus which, in addition to usual process-algebraic operators, involves logic connectives (conjunction and disjunction) and standard temporal operators (always and unless). This calculus preserves usual properties of these logic operators, allows one to freely mix operational and logic operators, and supports compositional reasoning. Moreover, the links between this calculus and Action-based Computation Tree Logic (ACTL) including characteristic formulae of process terms, characteristic processes of ACTL formulae and Galois connection are explored.
An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure
Venue: arXiv cs.DS 2012
Year: 2012

The paper presents an O^*(1.2312^n)-time and polynomial-space algorithm for the traveling salesman problem in an n-vertex graph with maximum degree 3. This improves the previous time bounds of O^*(1.251^n) by Iwama and Nakashima and O^*(1.260^n) by Eppstein. Our algorithm is a simple branch-and-search algorithm. The only branch rule is designed on a cut-circuit structure of a graph induced by unprocessed edges. To improve a time bound by a simple analysis on measure and conquer, we introduce an amortization scheme over the cut-circuit structure by defining the measure of an instance to be the sum of not only weights of vertices but also weights of connected components of the induced graph.
Training a Functional Link Neural Network Using an Artificial Bee Colony for Solving a Classification Problems
Venue: arXiv cs.NE 2012
Year: 2012

Artificial Neural Networks have emerged as an important tool for classification and have been widely used to classify a non-linear separable pattern. The most popular artificial neural networks model is a Multilayer Perceptron (MLP) as it is able to perform classification task with significant success. However due to the complexity of MLP structure and also problems such as local minima trapping, over fitting and weight interference have made neural network training difficult. Thus, the easy way to avoid these problems is to remove the hidden layers. This paper presents the ability of Functional Link Neural Network (FLNN) to overcome the complexity structure of MLP by using single layer architecture and propose an Artificial Bee Colony (ABC) optimization for training the FLNN. The proposed technique is expected to provide better learning scheme for a classifier in order to get more accurate classification result
The Geant4 Visualisation System - a multi-driver graphics system
Venue: arXiv cs.GR 2012
Year: 2012

From the beginning the Geant4 Visualisation System was designed to support several simultaneous graphics systems written to common abstract interfaces. Today it has matured into a powerful diagnostic and presentational tool. It comes with a library of models that may be added to the current scene and which include the representation of the Geant4 geometry hierarchy, simulated trajectories and user-written hits and digitisations. The workhorse is the OpenGL suite of drivers for X, Xm, Qt and Win32. There is an Open Inventor driver. Scenes can be exported in special graphics formats for offline viewing in the DAWN, VRML, HepRApp and gMocren browsers. PostScript can be generated through OpenGL, Open Inventor, DAWN and HepRApp. Geant4's own tracking algorithms are used by the Ray Tracer. Not all drivers support all features but all drivers bring added functionality of some sort. This paper describes the interfaces and details the individual drivers.
The ODD EVEN DELTA problem is #P-hard
Venue: arXiv cs.CC 2012
Year: 2012

Let G=(V,E) be a graph. Let k < |V| be an integer. Let O_k be the number of edge induced subgraphs of G having k vertices and an odd number of edges. Let E_k be the number of edge induced subgraphs of G having k vertices and an even number of edges. Let D_k = O_k - E_k. The ODD EVEN DELTA problem consists in computing D_k, given G and k. We show that such problem is #P-hard, even on 3-regular bipartite planar graphs.
Bethe Bounds and Approximating the Global Optimum
Venue: arXiv cs.LG 2012
Year: 2012

Inference in general Markov random fields (MRFs) is NP-hard, though identifying the maximum a posteriori (MAP) configuration of pairwise MRFs with submodular cost functions is efficiently solvable using graph cuts. Marginal inference, however, even for this restricted class, is in #P. We prove new formulations of derivatives of the Bethe free energy, provide bounds on the derivatives and bracket the locations of stationary points, introducing a new technique called Bethe bound propagation. Several results apply to pairwise models whether associative or not. Applying these to discretized pseudo-marginals in the associative case we present a polynomial time approximation scheme for global optimization provided the maximum degree is $O(\log n)$, and discuss several extensions.
Bounding Lossy Compression using Lossless Codes at Reduced Precision
Venue: arXiv cs.MM 2012
Year: 2012

An alternative approach to two-part 'critical compression' is presented. Whereas previous results were based on summing a lossless code at reduced precision with a lossy-compressed error or noise term, the present approach uses a similar lossless code at reduced precision to establish absolute bounds which constrain an arbitrary lossy data compression algorithm applied to the original data.
On the Construction of the Inclusion Boundary Neighbourhood for Markov Equivalence Classes of Bayesian Network Structures
Venue: arXiv cs.AI 2012
Year: 2012

The problem of learning Markov equivalence classes of Bayesian network structures may be solved by searching for the maximum of a scoring metric in a space of these classes. This paper deals with the definition and analysis of one such search space. We use a theoretically motivated neighbourhood, the inclusion boundary, and represent equivalence classes by essential graphs. We show that this search space is connected and that the score of the neighbours can be evaluated incrementally. We devise a practical way of building this neighbourhood for an essential graph that is purely graphical and does not explicitely refer to the underlying independences. We find that its size can be intractable, depending on the complexity of the essential graph of the equivalence class. The emphasis is put on the potential use of this space with greedy hill -climbing search
Planning under Continuous Time and Resource Uncertainty: A Challenge for AI
Venue: arXiv cs.AI 2012
Year: 2012

We outline a class of problems, typical of Mars rover operations, that are problematic for current methods of planning under uncertainty. The existing methods fail because they suffer from one or more of the following limitations: 1) they rely on very simple models of actions and time, 2) they assume that uncertainty is manifested in discrete action outcomes, 3) they are only practical for very small problems. For many real world problems, these assumptions fail to hold. In particular, when planning the activities for a Mars rover, none of the above assumptions is valid: 1) actions can be concurrent and have differing durations, 2) there is uncertainty concerning action durations and consumption of continuous resources like power, and 3) typical daily plans involve on the order of a hundred actions. This class of problems may be of particular interest to the UAI community because both classical and decision-theoretic planning techniques may be useful in solving it. We describe the rover problem, discuss previous work on planning under uncertainty, and present a detailed, but very small, example illustrating some of the difficulties of finding good plans.
An Information-Theoretic External Cluster-Validity Measure
Venue: arXiv cs.LG 2012
Year: 2012

In this paper we propose a measure of clustering quality or accuracy that is appropriate in situations where it is desirable to evaluate a clustering algorithm by somehow comparing the clusters it produces with ``ground truth' consisting of classes assigned to the patterns by manual means or some other means in whose veracity there is confidence. Such measures are refered to as ``external'. Our measure also has the characteristic of allowing clusterings with different numbers of clusters to be compared in a quantitative and principled way. Our evaluation scheme quantitatively measures how useful the cluster labels of the patterns are as predictors of their class labels. In cases where all clusterings to be compared have the same number of clusters, the measure is equivalent to the mutual information between the cluster labels and the class labels. In cases where the numbers of clusters are different, however, it computes the reduction in the number of bits that would be required to encode (compress) the class labels if both the encoder and decoder have free acccess to the cluster labels. To achieve this encoding the estimated conditional probabilities of the class labels given the cluster labels must also be encoded. These estimated probabilities can be seen as a model for the class labels and their associated code length as a model cost.
Dimension Correction for Hierarchical Latent Class Models
Venue: arXiv cs.LG 2012
Year: 2012

Model complexity is an important factor to consider when selecting among graphical models. When all variables are observed, the complexity of a model can be measured by its standard dimension, i.e. the number of independent parameters. When hidden variables are present, however, standard dimension might no longer be appropriate. One should instead use effective dimension (Geiger et al. 1996). This paper is concerned with the computation of effective dimension. First we present an upper bound on the effective dimension of a latent class (LC) model. This bound is tight and its computation is easy. We then consider a generalization of LC models called hierarchical latent class (HLC) models (Zhang 2002). We show that the effective dimension of an HLC model can be obtained from the effective dimensions of some related LC models. We also demonstrate empirically that using effective dimension in place of standard dimension improves the quality of models learned from data.
Expectation-Propogation for the Generative Aspect Model
Venue: arXiv cs.LG 2012
Year: 2012

The generative aspect model is an extension of the multinomial model for text that allows word probabilities to vary stochastically across documents. Previous results with aspect models have been promising, but hindered by the computational difficulty of carrying out inference and learning. This paper demonstrates that the simple variational methods of Blei et al (2001) can lead to inaccurate inferences and biased learning for the generative aspect model. We develop an alternative approach that leads to higher accuracy at comparable cost. An extension of Expectation-Propagation is used for inference and then embedded in an EM algorithm for learning. Experimental results are presented for both synthetic and real data sets.
Real-Time Inference with Large-Scale Temporal Bayes Nets
Venue: arXiv cs.AI 2012
Year: 2012

An increasing number of applications require real-time reasoning under uncertainty with streaming input. The temporal (dynamic) Bayes net formalism provides a powerful representational framework for such applications. However, existing exact inference algorithms for dynamic Bayes nets do not scale to the size of models required for real world applications which often contain hundreds or even thousands of variables for each time slice. In addition, existing algorithms were not developed with real-time processing in mind. We have developed a new computational approach to support real-time exact inference in large temporal Bayes nets. Our approach tackles scalability by recognizing that the complexity of the inference depends on the number of interface nodes between time slices and by exploiting the distinction between static and dynamic nodes in order to reduce the number of interface nodes and to factorize their joint probability distribution. We approach the real-time issue by organizing temporal Bayes nets into static representations, and then using the symbolic probabilistic inference algorithm to derive analytic expressions for the static representations. The parts of these expressions that do not change at each time step are pre-computed. The remaining parts are compiled into efficient procedural code so that the memory and CPU resources required by the inference are small and fixed.