OpenRaiser/Intern-Atlas huggingface dataset:
Adaptation to the Primary User CSI in Cognitive Radio Sensing and Access
Venue: arXiv cs.NI 2013
Year: 2013

In Cognitive Radio (CR) networks, multiple secondary network users (SUs) attempt to communicate over wide potential spectrum without causing significant interference to the Primary Users (PUs). A spectrum sensing algorithm is a critical component of any sensing strategy. Performance of conventional spectrum detection methods is severely limited when the average SNR of the fading channel between the PU transmitter and the SU sensor is low. Cooperative sensing and advanced detection techniques only partially remedy this problem. A key limitation of conventional approaches is that the sensing threshold is determined from the miss detection rate averaged over the fading distribution. In this paper, the threshold is adapted to the instantaneous PU-to-SU Channel State Information (CSI) under the prescribed collision probability constraint, and a novel sensing strategy design is proposed for overlay CR network where the instantaneous false alarm probability is incorporated into the belief update and the reward computation. It is demonstrated that the proposed sensing approach improves SU confidence, randomizes sensing decisions, and significantly improves SU network throughput while satisfying the collision probability constraint to the PUs in the low average PU-to-SU SNR region. Moreover, the proposed adaptive sensing strategy is robust to mismatched and correlated fading CSI and improves significantly on conventional cooperative sensing techniques. Finally, joint adaptation to PU channel gain and SU link CSI is explored to further improve CR throughput and reduce SU collisions.
Quality of Service in Wireless Cellular Networks Subject to Log-Normal Shadowing
Venue: arXiv cs.NI 2013
Year: 2013

Shadowing is believed to degrade the quality of service (QoS) in wireless cellular networks. Assuming log-normal shadowing, and studying mobile's path-loss with respect to the serving base station (BS) and the corresponding interference factor (the ratio of the sum of the path-gains form interfering BS's to the path-gain from the serving BS), which are two key ingredients of the analysis and design of the cellular networks, we discovered a more subtle reality. We observe, as commonly expected, that a strong variance of the shadowing increases the mean path-loss with respect to the serving BS, which in consequence, may compromise QoS. However, in some cases, an increase of the variance of the shadowing can significantly reduce the mean interference factor and, in consequence, improve some QoS metrics in interference limited systems, provided the handover policy selects the BS with the smallest path loss as the serving one. We exemplify this phenomenon, similar to stochastic resonance and related to the "single big jump principle" of the heavy-tailed log-nornal distribution, studying the blocking probability in regular, hexagonal networks in a semi-analytic manner, using a spatial version of the Erlang's loss formula combined with Kaufman-Roberts algorithm. More detailed probabilistic analysis explains that increasing variance of the log-normal shadowing amplifies the ratio between the strongest signal and all other signals thus reducing the interference. The above observations might shed new light, in particular on the design of indoor communication scenarios.
Timing in chemical reaction networks
Venue: arXiv cs.CC 2013
Year: 2013

Chemical reaction networks (CRNs) formally model chemistry in a well-mixed solution. CRNs are widely used to describe information processing occurring in natural cellular regulatory networks, and with upcoming advances in synthetic biology, CRNs are a promising programming language for the design of artificial molecular control circuitry. Due to a formal equivalence between CRNs and a model of distributed computing known as population protocols, results transfer readily between the two models. We show that if a CRN respects finite density (at most O(n) additional molecules can be produced from n initial molecules), then starting from any dense initial configuration (all molecular species initially present have initial count Omega(n), where n is the initial molecular count and volume), then every producible species is produced in constant time with high probability. This implies that no CRN obeying the stated constraints can function as a timer, able to produce a molecule, but doing so only after a time that is an unbounded function of the input size. This has consequences regarding an open question of Angluin, Aspnes, and Eisenstat concerning the ability of population protocols to perform fast, reliable leader election and to simulate arbitrary algorithms from a uniform initial state.
Competition Between Wireless Service Providers: Pricing, Equilibrium and Efficiency
Venue: arXiv cs.GT 2013
Year: 2013

As the communication network is in transition towards a commercial one controlled by service providers (SP), the present paper considers a pricing game in a communication market covered by several wireless access points sharing the same spectrum and analyzes two business models: monopoly (APs controlled by one SP) and oligopoly (APs controlled by different SPs). We use a Stackelberg game to model the problem: SPs are the leader(s) and end users are the followers. We prove, under certain conditions, the existence and uniqueness of Nash equilibrium for both models and derive their expressions. In order to compare the impact of different business models on social welfare and SPs' profits, we define two metrics: PoCS (price of competition on social welfare) and PoCP (price of competition on profits). For symmetric cross-AP interferences, the tight lower bound of PoCS is 3/4, and that of PoCP is 1.
Prioritizing Consumers in Smart Grid: Energy Management Using Game Theory
Venue: arXiv cs.GT 2013
Year: 2013

This paper explores an idea of demand-supply balance for smart grids in which consumers are expected to play a significant role. The main objective is to motivate the consumer, by maximizing their benefit both as a seller and a buyer, to trade their surplus energy with the grid so as to balance the demand at the peak hour. To that end, a Stackelberg game is proposed to capture the interactions between the grid and consumers, and it is shown analytically that optimal energy trading parameters that maximize customers utilities are obtained at the solution of the game. A novel distributed algorithm is proposed to reach the optimal solution of the game, and numerical examples are used to assess the properties and effectiveness of the proposed approach.
Analyzing Medium Access Techniques in Wireless Body Area Networks
Venue: arXiv cs.NI 2013
Year: 2013

This paper presents comparison of Access Techniques used in Medium Access Control (MAC) protocol for Wireless Body Area Networks (WBANs). Comparison is performed between Time Division Multiple Access (TDMA), Frequency Division Multiple Access (FDMA), Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA), Pure ALOHA and Slotted ALOHA (S-ALOHA). Performance metrics used for comparison are Throughput (T), Delay (D) and Offered Load (G). The main goal for comparison is to show which technique gives highest Throughput and lowest Delay with increase in Load. Energy efficiency is major issue in WBAN that is why there is need to know which technique performs best for energy conservation and also gives minimum delay. Simulations are performed for different scenarios and results are compared for all techniques. We suggest TDMA as best technique to be used in MAC protocol for WBANs due to its high throughput and minimum delay with increase in load. MATLAB is the tool that is used for simulation.
Exploiting Functional Dependencies in Qualitative Probabilistic Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

Functional dependencies restrict the potential interactions among variables connected in a probabilistic network. This restriction can be exploited in qualitative probabilistic reasoning by introducing deterministic variables and modifying the inference rules to produce stronger conclusions in the presence of functional relations. I describe how to accomplish these modifications in qualitative probabilistic networks by exhibiting the update procedures for graphical transformations involving probabilistic and deterministic variables and combinations. A simple example demonstrates that the augmented scheme can reduce qualitative ambiguity that would arise without the special treatment of functional dependency. Analysis of qualitative synergy reveals that new higher-order relations are required to reason effectively about synergistic interactions among deterministic variables.
Qualitative Propagation and Scenario-based Explanation of Probabilistic Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

Comprehensible explanations of probabilistic reasoning are a prerequisite for wider acceptance of Bayesian methods in expert systems and decision support systems. A study of human reasoning under uncertainty suggests two different strategies for explaining probabilistic reasoning: The first, qualitative belief propagation, traces the qualitative effect of evidence through a belief network from one variable to the next. This propagation algorithm is an alternative to the graph reduction algorithms of Wellman (1988) for inference in qualitative probabilistic networks. It is based on a qualitative analysis of intercausal reasoning, which is a generalization of Pearl's "explaining away", and an alternative to Wellman's definition of qualitative synergy. The other, Scenario-based reasoning, involves the generation of alternative causal "stories" accounting for the evidence. Comparing a few of the most probable scenarios provides an approximate way to explain the results of probabilistic reasoning. Both schemes employ causal as well as probabilistic knowledge. Probabilities may be presented as phrases and/or numbers. Users can control the style, abstraction and completeness of explanations.
Managing Uncertainty in Rule Based Cognitive Models
Venue: arXiv cs.AI 2013
Year: 2013

An experiment replicated and extended recent findings on psychologically realistic ways of modeling propagation of uncertainty in rule based reasoning. Within a single production rule, the antecedent evidence can be summarized by taking the maximum of disjunctively connected antecedents and the minimum of conjunctively connected antecedents. The maximum certainty factor attached to each of the rule's conclusions can be sealed down by multiplication with this summarized antecedent certainty. Heckerman's modified certainty factor technique can be used to combine certainties for common conclusions across production rules.
Integrating Probabilistic, Taxonomic and Causal Knowledge in Abductive Diagnosis
Venue: arXiv cs.AI 2013
Year: 2013

We propose an abductive diagnosis theory that integrates probabilistic, causal and taxonomic knowledge. Probabilistic knowledge allows us to select the most likely explanation; causal knowledge allows us to make reasonable independence assumptions; taxonomic knowledge allows causation to be modeled at different levels of detail, and allows observations be described in different levels of precision. Unlike most other approaches where a causal explanation is a hypothesis that one or more causative events occurred, we define an explanation of a set of observations to be an occurrence of a chain of causation events. These causation events constitute a scenario where all the observations are true. We show that the probabilities of the scenarios can be computed from the conditional probabilities of the causation events. Abductive reasoning is inherently complex even if only modest expressive power is allowed. However, our abduction algorithm is exponential only in the number of observations to be explained, and is polynomial in the size of the knowledge base. This contrasts with many other abduction procedures that are exponential in the size of the knowledge base.
Decision Making with Interval Influence Diagrams
Venue: arXiv cs.AI 2013
Year: 2013

In previous work (Fertig and Breese, 1989; Fertig and Breese, 1990) we defined a mechanism for performing probabilistic reasoning in influence diagrams using interval rather than point-valued probabilities. In this paper we extend these procedures to incorporate decision nodes and interval-valued value functions in the diagram. We derive the procedures for chance node removal (calculating expected value) and decision node removal (optimization) in influence diagrams where lower bounds on probabilities are stored at each chance node and interval bounds are stored on the value function associated with the diagram's value node. The output of the algorithm are a set of admissible alternatives for each decision variable and a set of bounds on expected value based on the imprecision in the input. The procedure can be viewed as an approximation to a full e-dimensional sensitivity analysis where n are the number of imprecise probability distributions in the input. We show the transformations are optimal and sound. The performance of the algorithm on an influence diagrams is investigated and compared to an exact algorithm.
Computation of Variances in Causal Networks
Venue: arXiv cs.AI 2013
Year: 2013

The causal (belief) network is a well-known graphical structure for representing independencies in a joint probability distribution. The exact methods and the approximation methods, which perform probabilistic inference in causal networks, often treat the conditional probabilities which are stored in the network as certain values. However, if one takes either a subjectivistic or a limiting frequency approach to probability, one can never be certain of probability values. An algorithm for probabilistic inference should not only be capable of reporting the inferred probabilities; it should also be capable of reporting the uncertainty in these probabilities relative to the uncertainty in the probabilities which are stored in the network. In section 2 of this paper a method is given for determining the prior variances of the probabilities of all the nodes. Section 3 contains an approximation method for determining the variances in inferred probabilities.
A Combination of Cutset Conditioning with Clique-Tree Propagation in the Pathfinder System
Venue: arXiv cs.AI 2013
Year: 2013

Cutset conditioning and clique-tree propagation are two popular methods for performing exact probabilistic inference in Bayesian belief networks. Cutset conditioning is based on decomposition of a subset of network nodes, whereas clique-tree propagation depends on aggregation of nodes. We describe a means to combine cutset conditioning and clique- tree propagation in an approach called aggregation after decomposition (AD). We discuss the application of the AD method in the Pathfinder system, a medical expert system that offers assistance with diagnosis in hematopathology.
Credibility Discounting in the Theory of Approximate Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

We are concerned with the problem of introducing credibility type information into reasoning systems. The concept of credibility allows us to discount information provided by agents. An important characteristic of this kind of procedure is that a complete lack of credibility rather than resulting in the negation of the information provided results in the nullification of the information provided. We suggest a representational scheme for credibility qualification in the theory of approximate reasoning. We discuss the concept of relative credibility. By this idea we mean to indicate situations in which the credibility of a piece of evidence is determined by its compatibility with higher priority evidence. This situation leads to structures very much in the spirit of nonmonotonic reasoning.
A New Approach to Updating Beliefs
Venue: arXiv cs.AI 2013
Year: 2013

We define a new notion of conditional belief, which plays the same role for Dempster-Shafer belief functions as conditional probability does for probability functions. Our definition is different from the standard definition given by Dempster, and avoids many of the well-known problems of that definition. Just as the conditional probability Pr (lB) is a probability function which is the result of conditioning on B being true, so too our conditional belief function Bel (lB) is a belief function which is the result of conditioning on B being true. We define the conditional belief as the lower envelope (that is, the inf) of a family of conditional probability functions, and provide a closed form expression for it. An alternate way of understanding our definition of conditional belief is provided by considering ideas from an earlier paper [Fagin and Halpern, 1989], where we connect belief functions with inner measures. In particular, we show here how to extend the definition of conditional probability to non measurable sets, in order to get notions of inner and outer conditional probabilities, which can be viewed as best approximations to the true conditional probability, given our lack of information. Our definition of conditional belief turns out to be an exact analogue of our definition of inner conditional probability.
Evidence Combination and Reasoning and Its Application to Real-World Problem-Solving
Venue: arXiv cs.AI 2013
Year: 2013

In this paper a new mathematical procedure is presented for combining different pieces of evidence which are represented in the interval form to reflect our knowledge about the truth of a hypothesis. Evidences may be correlated to each other (dependent evidences) or conflicting in supports (conflicting evidences). First, assuming independent evidences, we propose a methodology to construct combination rules which obey a set of essential properties. The method is based on a geometric model. We compare results obtained from Dempster-Shafer's rule and the proposed combination rules with both conflicting and non-conflicting data and show that the values generated by proposed combining rules are in tune with our intuition in both cases. Secondly, in the case that evidences are known to be dependent, we consider extensions of the rules derived for handling conflicting evidence. The performance of proposed rules are shown by different examples. The results show that the proposed rules reasonably make decision under dependent evidences
Amplitude-Based Approach to Evidence Accumulation
Venue: arXiv cs.AI 2013
Year: 2013

We point out the need to use probability amplitudes rather than probabilities to model evidence accumulation in decision processes involving real physical sensors. Optical information processing systems are given as typical examples of systems that naturally gather evidence in this manner. We derive a new, amplitude-based generalization of the Hough transform technique used for object recognition in machine vision. We argue that one should use complex Hough accumulators and square their magnitudes to get a proper probabilistic interpretation of the likelihood that an object is present. Finally, we suggest that probability amplitudes may have natural applications in connectionist models, as well as in formulating knowledge-based reasoning problems.
Finding Primitive Elements in Finite Fields of Small Characteristic
Venue: arXiv cs.DM 2013
Year: 2013

We describe a deterministic algorithm for finding a generating element of the multiplicative group of the finite field $\mathbb{F}_{p^n}$ where $p$ is a prime. In time polynomial in $p$ and $n$, the algorithm either outputs an element that is provably a generator or declares that it has failed in finding one. The algorithm relies on a relation generation technique in Joux's heuristically $L(1/4)$-method for discrete logarithm computation. Based on a heuristic assumption, the algorithm does succeed in finding a generator. For the special case when the order of $p$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ is small (that is $(\log_p(n))^{\mathcal{O}(1)}$), we present a modification with greater guarantee of success while making weaker heuristic assumptions.
Total Representations
Venue: arXiv cs.LO 2013
Year: 2013

Almost all representations considered in computable analysis are partial. We provide arguments in favor of total representations (by elements of the Baire space). Total representations make the well known analogy between numberings and representations closer, unify some terminology, simplify some technical details, suggest interesting open questions and new invariants of topological spaces relevant to computable analysis.
Lack of controllability of thermal systems with memory
Venue: arXiv cs.SY 2013
Year: 2013

Heat equations with memory of Gurtin-Pipkin type have controllability properties which strongly resemble those of the wave equation. Instead, recent counterexamples show that when the laplacian appears also out of the memory term, the control properties do not parallel those of the (memoryless) heat equation, in the sense that there are $L^2$-initial conditions which cannot be controlled to zero. The proof of this fact (presented in previous papers) consists in the construction of two quite special examples of systems with memory which cannot be controlled to zero. Here we prove that lack of controllability holds in general, for every systems with smooth memory kernel.
Homogeneous Weights of Matrix Product Codes over Finite Principal Ideal Rings
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, the homogeneous weights of matrix product codes over finite principal ideal rings are studied and a lower bound for the minimum homogeneous weights of such matrix product codes is obtained.
RITA: An Index-Tuning Advisor for Replicated Databases
Venue: arXiv cs.DB 2013
Year: 2013

Given a replicated database, a divergent design tunes the indexes in each replica differently in order to specialize it for a specific subset of the workload. This specialization brings significant performance gains compared to the common practice of having the same indexes in all replicas, but requires the development of new tuning tools for database administrators. In this paper we introduce RITA (Replication-aware Index Tuning Advisor), a novel divergent-tuning advisor that offers several essential features not found in existing tools: it generates robust divergent designs that allow the system to adapt gracefully to replica failures; it computes designs that spread the load evenly among specialized replicas, both during normal operation and when replicas fail; it monitors the workload online in order to detect changes that require a recomputation of the divergent design; and, it offers suggestions to elastically reconfigure the system (by adding/removing replicas or adding/dropping indexes) to respond to workload changes. The key technical innovation behind RITA is showing that the problem of selecting an optimal design can be formulated as a Binary Integer Program (BIP). The BIP has a relatively small number of variables, which makes it feasible to solve it efficiently using any off-the-shelf linear-optimization software. Experimental results demonstrate that RITA computes better divergent designs compared to existing tools, offers more features, and has fast execution times.
Information and Computation
Venue: arXiv cs.IT 2013
Year: 2013

In this chapter, concepts related to information and computation are reviewed in the context of human computation. A brief introduction to information theory and different types of computation is given. Two examples of human computation systems, online social networks and Wikipedia, are used to illustrate how these can be described and compared in terms of information and computation.