OpenRaiser/Intern-Atlas huggingface dataset:
Approximation of Polyhedral Surface Uniformization
Venue: arXiv cs.CG 2013
Year: 2013

We present a constructive approach for approximating the conformal map (uniformization) of a polyhedral surface to a canonical domain in the plane. The main tool is a characterization of convex spaces of quasiconformal simplicial maps and their approximation properties. As far as we are aware, this is the first algorithm proved to approximate the uniformization of general polyhedral surfaces.
On AVCs with Quadratic Constraints
Venue: arXiv cs.IT 2013
Year: 2013

In this work we study an Arbitrarily Varying Channel (AVC) with quadratic power constraints on the transmitter and a so-called "oblivious" jammer (along with additional AWGN) under a maximum probability of error criterion, and no private randomness between the transmitter and the receiver. This is in contrast to similar AVC models under the average probability of error criterion considered in [1], and models wherein common randomness is allowed [2] -- these distinctions are important in some communication scenarios outlined below. We consider the regime where the jammer's power constraint is smaller than the transmitter's power constraint (in the other regime it is known no positive rate is possible). For this regime we show the existence of stochastic codes (with no common randomness between the transmitter and receiver) that enables reliable communication at the same rate as when the jammer is replaced with AWGN with the same power constraint. This matches known information-theoretic outer bounds. In addition to being a stronger result than that in [1] (enabling recovery of the results therein), our proof techniques are also somewhat more direct, and hence may be of independent interest.
Subspace Codes for Random Networks Based on Plücker Coordinates and Schubert Cells
Venue: arXiv cs.IT 2013
Year: 2013

The Plücker coordinate description of subspaces has been recently discussed in the context of constant dimension subspace codes for random networks, as well as the Schubert cell description of certain code parameters. In this paper this classical tool is used to reformulate some standard constructions of constant dimension codes so as to give a unified framework. A general method of constructing non-constant dimension subspace codes with respect to a given minimum subspace distance or minimum injection distance among subspaces is presented. These codes may be described as the union of constant dimension subspace codes restricted to selected Schubert cells. The selection of these Schubert cells is based on the subset distance of tuples corresponding to the Plücker coordinate matrices associated with the subspaces contained in the respective Schubert cells. In this context, it is shown that a recent construction of non-constant dimension Ferrers-diagram rank-metric subspace codes (Khaleghi and Kschischang) is subsumed in the present framework.
A Universal Probability Assignment for Prediction of Individual Sequences
Venue: arXiv cs.IT 2013
Year: 2013

Is it a good idea to use the frequency of events in the past, as a guide to their frequency in the future (as we all do anyway)? In this paper the question is attacked from the perspective of universal prediction of individual sequences. It is shown that there is a universal sequential probability assignment, such that for a large class loss functions (optimization goals), the predictor minimizing the expected loss under this probability, is a good universal predictor. The proposed probability assignment is based on randomly dithering the empirical frequencies of states in the past, and it is easy to show that randomization is essential. This yields a very simple universal prediction scheme which is similar to Follow-the-Perturbed-Leader (FPL) and works for a large class of loss functions, as well as a partial justification for using probabilistic assumptions.
Joint Design of Channel and Network Coding for Star Networks
Venue: arXiv cs.IT 2013
Year: 2013

Channel coding alone is not sufficient to reliably transmit a message of finite length $K$ from a source to one or more destinations as in, e.g., file transfer. To ensure that no data is lost, it must be combined with rateless erasure correcting schemes on a higher layer, such as a time-division multiple access (TDMA) system paired with automatic repeat request (ARQ) or random linear network coding (RLNC). We consider binary channel coding on a binary symmetric channel (BSC) and q-ary RLNC for erasure correction in a star network, where Y sources send messages to each other with the help of a central relay. In this scenario RLNC has been shown to have a throughput advantage over TDMA schemes as K and q tend to infinity. In this paper we focus on finite block lengths and compare the expected throughputs of RLNC and TDMA. For a total message length of K bits, which can be subdivided into blocks of smaller size prior to channel coding, we obtain the channel coding rate and the number of blocks that maximize the expected throughput of both RLNC and TDMA, and we find that TDMA is more throughput-efficient for small message lengths K and small q.
Structured Lattice Codes for 2 \times 2 \times 2 MIMO Interference Channel
Venue: arXiv cs.IT 2013
Year: 2013

We consider the 2\times 2\times 2 multiple-input multipleoutput interference channel where two source-destination pairs wish to communicate with the aid of two intermediate relays. In this paper, we propose a novel lattice strategy called Aligned Precoded Compute-and-Forward (PCoF). This scheme consists of two phases: 1) Using the CoF framework based on signal alignment we transform the Gaussian network into a deterministic finite field network. 2) Using linear precoding (over finite field) we eliminate the end-to-end interference in the finite field domain. Further, we exploit the algebraic structure of lattices to enhance the performance at finite SNR, such that beyond a degree of freedom result (also achievable by other means). We can also show that Aligned PCoF outperforms time sharing in a range of reasonably moderate SNR, with increasing gain as SNR increases.
Extendable MDL
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we show that combination of the minimum description length principle and a exchange-ability condition leads directly to the use of Jeffreys prior. This approach works in most cases even when Jeffreys prior cannot be normalized. Kraft's inequality links codes and distributions but a closer look at this inequality demonstrates that this link only makes sense when sequences are considered as prefixes of potential longer sequences. For technical reasons only results for exponential families are stated. Results on when Jeffreys prior can be normalized after conditioning on a initializing string are given. An exotic case where no initial string allow Jeffreys prior to be normalized is given and some way of handling such exotic cases are discussed.
On the precoder design of a wireless energy harvesting node in linear vector Gaussian channels with arbitrary input distribution
Venue: arXiv cs.IT 2013
Year: 2013

A Wireless Energy Harvesting Node (WEHN) operating in linear vector Gaussian channels with arbitrarily distributed input symbols is considered in this paper. The precoding strategy that maximizes the mutual information along N independent channel accesses is studied under non-causal knowledge of the channel state and harvested energy (commonly known as offline approach). It is shown that, at each channel use, the left singular vectors of the precoder are equal to the eigenvectors of the Gram channel matrix. Additionally, an expression that relates the optimal singular values of the precoder with the energy harvesting profile through the Minimum Mean-Square Error (MMSE) matrix is obtained. Then, the specific situation in which the right singular vectors of the precoder are set to the identity matrix is considered. In this scenario, the optimal offline power allocation, named Mercury Water-Flowing, is derived and an intuitive graphical representation is presented. Two optimal offline algorithms to compute the Mercury Water- Flowing solution are proposed and an exhaustive study of their computational complexity is performed. Moreover, an online algorithm is designed, which only uses causal knowledge of the harvested energy and channel state. Finally, the achieved mutual information is evaluated through simulation.
Perspectives on Balanced Sequences
Venue: arXiv cs.IT 2013
Year: 2013

We examine and compare several different classes of "balanced" block codes over q-ary alphabets, namely symbol-balanced (SB) codes, charge-balanced (CB) codes, and polarity-balanced (PB) codes. Known results on the maximum size and asymptotic minimal redundancy of SB and CB codes are reviewed. We then determine the maximum size and asymptotic minimal redundancy of PB codes and of codes which are both CB and PB. We also propose efficient Knuth-like encoders and decoders for all these types of balanced codes.
Secrecy in the 2-User Symmetric Deterministic Interference Channel with Transmitter Cooperation
Venue: arXiv cs.IT 2013
Year: 2013

This work presents novel achievable schemes for the 2-user symmetric linear deterministic interference channel with limited-rate transmitter cooperation and perfect secrecy constraints at the receivers. The proposed achievable scheme consists of a combination of interference cancelation, relaying of the other user's data bits, time sharing, and transmission of random bits, depending on the rate of the cooperative link and the relative strengths of the signal and the interference. The results show, for example, that the proposed scheme achieves the same rate as the capacity without the secrecy constraints, in the initial part of the weak interference regime. Also, sharing random bits through the cooperative link can achieve a higher secrecy rate compared to sharing data bits, in the very high interference regime. The results highlight the importance of limited transmitter cooperation in facilitating secure communications over 2-user interference channels.
Information Theoretic Cut-set Bounds on the Capacity of Poisson Wireless Networks
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents a stochastic geometry model for the investigation of fundamental information theoretic limitations in wireless networks. We derive a new unified multi-parameter cut-set bound on the capacity of networks of arbitrary Poisson node density, size, power and bandwidth, under fast fading in a rich scattering environment. In other words, we upper-bound the optimal performance in terms of total communication rate, under any scheme, that can be achieved between a subset of network nodes (defined by the cut) with all the remaining nodes. Additionally, we identify four different operating regimes, depending on the magnitude of the long-range and short-range signal to noise ratios. Thus, we confirm previously known scaling laws (e.g., in bandwidth and/or power limited wireless networks), and we extend them with specific bounds. Finally, we use our results to provide specific numerical examples.
Political Disaffection: a case study on the Italian Twitter community
Venue: arXiv cs.SI 2013
Year: 2013

In our work we analyse the political disaffection or "the subjective feeling of powerlessness, cynicism, and lack of confidence in the political process, politicians, and democratic institutions, but with no questioning of the political regime" by exploiting Twitter data through machine learning techniques. In order to validate the quality of the time-series generated by the Twitter data, we highlight the relations of these data with political disaffection as measured by means of public opinion surveys. Moreover, we show that important political news of Italian newspapers are often correlated with the highest peaks of the produced time-series.
A Temporal Bayesian Network for Diagnosis and Prediction
Venue: arXiv cs.AI 2013
Year: 2013

Diagnosis and prediction in some domains, like medical and industrial diagnosis, require a representation that combines uncertainty management and temporal reasoning. Based on the fact that in many cases there are few state changes in the temporal range of interest, we propose a novel representation called Temporal Nodes Bayesian Networks (TNBN). In a TNBN each node represents an event or state change of a variable, and an arc corresponds to a causal-temporal relationship. The temporal intervals can differ in number and size for each temporal node, so this allows multiple granularity. Our approach is contrasted with a dynamic Bayesian network for a simple medical example. An empirical evaluation is presented for a more complex problem, a subsystem of a fossil power plant, in which this approach is used for fault diagnosis and prediction with good results.
Causal Discovery from a Mixture of Experimental and Observational Data
Venue: arXiv cs.AI 2013
Year: 2013

This paper describes a Bayesian method for combining an arbitrary mixture of observational and experimental data in order to learn causal Bayesian networks. Observational data are passively observed. Experimental data, such as that produced by randomized controlled trials, result from the experimenter manipulating one or more variables (typically randomly) and observing the states of other variables. The paper presents a Bayesian method for learning the causal structure and parameters of the underlying causal process that is generating the data, given that (1) the data contains a mixture of observational and experimental case records, and (2) the causal process is modeled as a causal Bayesian network. This learning method was applied using as input various mixtures of experimental and observational data that were generated from the ALARM causal Bayesian network. In these experiments, the absolute and relative quantities of experimental and observational data were varied systematically. For each of these training datasets, the learning method was applied to predict the causal structure and to estimate the causal parameters that exist among randomly selected pairs of nodes in ALARM that are not confounded. The paper reports how these structure predictions and parameter estimates compare with the true causal structures and parameters as given by the ALARM network.
SPUDD: Stochastic Planning using Decision Diagrams
Venue: arXiv cs.AI 2013
Year: 2013

Markov decisions processes (MDPs) are becoming increasing popular as models of decision theoretic planning. While traditional dynamic programming methods perform well for problems with small state spaces, structured methods are needed for large problems. We propose and examine a value iteration algorithm for MDPs that uses algebraic decision diagrams(ADDs) to represent value functions and policies. An MDP is represented using Bayesian networks and ADDs and dynamic programming is applied directly to these ADDs. We demonstrate our method on large MDPs (up to 63 million states) and show that significant gains can be had when compared to tree-structured representations (with up to a thirty-fold reduction in the number of nodes required to represent optimal value functions).
Attention-Sensitive Alerting
Venue: arXiv cs.AI 2013
Year: 2013

We introduce utility-directed procedures for mediating the flow of potentially distracting alerts and communications to computer users. We present models and inference procedures that balance the context-sensitive costs of deferring alerts with the cost of interruption. We describe the challenge of reasoning about such costs under uncertainty via an analysis of user activity and the content of notifications. After introducing principles of attention-sensitive alerting, we focus on the problem of guiding alerts about email messages. We dwell on the problem of inferring the expected criticality of email and discuss work on the Priorities system, centering on prioritizing email by criticality and modulating the communication of notifications to users about the presence and nature of incoming email.
Bayesian Poker
Venue: arXiv cs.AI 2013
Year: 2013

Poker is ideal for testing automated reasoning under uncertainty. It introduces uncertainty both by physical randomization and by incomplete information about opponents hands.Another source OF uncertainty IS the limited information available TO construct psychological models OF opponents, their tendencies TO bluff, play conservatively, reveal weakness, etc. AND the relation BETWEEN their hand strengths AND betting behaviour. ALL OF these uncertainties must be assessed accurately AND combined effectively FOR ANY reasonable LEVEL OF skill IN the game TO be achieved, since good decision making IS highly sensitive TO those tasks.We describe our Bayesian Poker Program(BPP), which uses a Bayesian network TO model the programs poker hand, the opponents hand AND the opponents playing behaviour conditioned upon the hand, and betting curves which govern play given a probability of winning. The history of play with opponents is used to improve BPPs understanding OF their behaviour.We compare BPP experimentally WITH : a simple RULE - based system; a program which depends exclusively ON hand probabilities(i.e., without opponent modeling); AND WITH human players.BPP has shown itself TO be an effective player against ALL these opponents, barring the better humans.We also sketch out SOME likely ways OF improving play.
Expected Utility Networks
Venue: arXiv cs.GT 2013
Year: 2013

We introduce a new class of graphical representations, expected utility networks (EUNs), and discuss some of its properties and potential applications to artificial intelligence and economic theory. In EUNs not only probabilities, but also utilities enjoy a modular representation. EUNs are undirected graphs with two types of arc, representing probability and utility dependencies respectively. The representation of utilities is based on a novel notion of conditional utility independence, which we introduce and discuss in the context of other existing proposals. Just as probabilistic inference involves the computation of conditional probabilities, strategic inference involves the computation of conditional expected utilities for alternative plans of action. We define a new notion of conditional expected utility (EU) independence, and show that in EUNs node separation with respect to the probability and utility subgraphs implies conditional EU independence.
The Decision-Theoretic Interactive Video Advisor
Venue: arXiv cs.IR 2013
Year: 2013

The need to help people choose among large numbers of items and to filter through large amounts of information has led to a flood of research in construction of personal recommendation agents. One of the central issues in constructing such agents is the representation and elicitation of user preferences or interests. This topic has long been studied in Decision Theory, but surprisingly little work in the area of recommender systems has made use of formal decision-theoretic techniques. This paper describes DIVA, a decision-theoretic agent for recommending movies that contains a number of novel features. DIVA represents user preferences using pairwise comparisons among items, rather than numeric ratings. It uses a novel similarity measure based on the concept of the probability of conflict between two orderings of items. The system has a rich representation of preference, distinguishing between a user's general taste in movies and his immediate interests. It takes an incremental approach to preference elicitation in which the user can provide feedback if not satisfied with the recommendation list. We empirically evaluate the performance of the system using the EachMovie collaborative filtering database.
Inference Networks and the Evaluation of Evidence: Alternative Analyses
Venue: arXiv cs.AI 2013
Year: 2013

Inference networks have a variety of important uses and are constructed by persons having quite different standpoints. Discussed in this paper are three different but complementary methods for generating and analyzing probabilistic inference networks. The first method, though over eighty years old, is very useful for knowledge representation in the task of constructing probabilistic arguments. It is also useful as a heuristic device in generating new forms of evidence. The other two methods are formally equivalent ways for combining probabilities in the analysis of inference networks. The use of these three methods is illustrated in an analysis of a mass of evidence in a celebrated American law case.
Approximate Learning in Complex Dynamic Bayesian Networks
Venue: arXiv cs.LG 2013
Year: 2013

In this paper we extend the work of Smith and Papamichail (1999) and present fast approximate Bayesian algorithms for learning in complex scenarios where at any time frame, the relationships between explanatory state space variables can be described by a Bayesian network that evolve dynamically over time and the observations taken are not necessarily Gaussian. It uses recent developments in approximate Bayesian forecasting methods in combination with more familiar Gaussian propagation algorithms on junction trees. The procedure for learning state parameters from data is given explicitly for common sampling distributions and the methodology is illustrated through a real application. The efficiency of the dynamic approximation is explored by using the Hellinger divergence measure and theoretical bounds for the efficacy of such a procedure are discussed.
Practical Uses of Belief Functions
Venue: arXiv cs.AI 2013
Year: 2013

We present examples where the use of belief functions provided sound and elegant solutions to real life problems. These are essentially characterized by ?missing' information. The examples deal with 1) discriminant analysis using a learning set where classes are only partially known; 2) an information retrieval systems handling inter-documents relationships; 3) the combination of data from sensors competent on partially overlapping frames; 4) the determination of the number of sources in a multi-sensor environment by studying the inter-sensors contradiction. The purpose of the paper is to report on such applications where the use of belief functions provides a convenient tool to handle ?messy' data problems.
Energy-Efficient Spectrum Sharing in Relay-Assisted Cognitive Radio Systems
Venue: arXiv cs.IT 2013
Year: 2013

This work characterizes an important solution concept of a relevant spectrum game. Two energy-efficient sources communicating with their respective destination compete for an extra channel brought by a relay charging the used bandwidth through a pricing mechanism. This game is shown to possess a unique Nash bargaining solution, exploiting a time-sharing argument. This Pareto-efficient solution can be implemented by using a distributed optimization algorithm for which each transmitter uses a simple gradient-type algorithm and alternately updates its spectrum sharing policy. Typical numerical results show to what extent spectral efficiency can be improved in a system involving selfish energy-efficient sources.