OpenRaiser/Intern-Atlas huggingface dataset:
From imprecise probability assessments to conditional probabilities with quasi additive classes of conditioning events
Venue: arXiv cs.AI 2012
Year: 2012

In this paper, starting from a generalized coherent (i.e. avoiding uniform loss) intervalvalued probability assessment on a finite family of conditional events, we construct conditional probabilities with quasi additive classes of conditioning events which are consistent with the given initial assessment. Quasi additivity assures coherence for the obtained conditional probabilities. In order to reach our goal we define a finite sequence of conditional probabilities by exploiting some theoretical results on g-coherence. In particular, we use solutions of a finite sequence of linear systems.
An Improved Admissible Heuristic for Learning Optimal Bayesian Networks
Venue: arXiv cs.AI 2012
Year: 2012

Recently two search algorithms, A* and breadth-first branch and bound (BFBnB), were developed based on a simple admissible heuristic for learning Bayesian network structures that optimize a scoring function. The heuristic represents a relaxation of the learning problem such that each variable chooses optimal parents independently. As a result, the heuristic may contain many directed cycles and result in a loose bound. This paper introduces an improved admissible heuristic that tries to avoid directed cycles within small groups of variables. A sparse representation is also introduced to store only the unique optimal parent choices. Empirical results show that the new techniques significantly improved the efficiency and scalability of A* and BFBnB on most of datasets tested in this paper.
Self-Confirming Price Prediction Strategies for Simultaneous One-Shot Auctions
Venue: arXiv cs.GT 2012
Year: 2012

Bidding in simultaneous auctions is challenging because an agent's value for a good in one auction may depend on the uncertain outcome of other auctions: the so-called exposure problem. Given the gap in understanding of general simultaneous auction games, previous works have tackled this problem with heuristic strategies that employ probabilistic price predictions. We define a concept of self-confirming prices, and show that within an independent private value model, Bayes-Nash equilibrium can be fully characterized as a profile of optimal price prediction strategies with self-confirming predictions. We exhibit practical procedures to compute approximately optimal bids given a probabilistic price prediction, and near self-confirming price predictions given a price-prediction strategy. An extensive empirical game-theoretic analysis demonstrates that self-confirming price prediction strategies are effective in simultaneous auction games with both complementary and substitutable preference structures.
Minimization of semilinear automata
Venue: arXiv cs.LO 2012
Year: 2012

We investigate finite deterministic automata in sets with non-homogeneous atoms: integers with successor. As there are uncount- ably many deterministic finite automata in this setting, we restrict our attention to automata with semilinear transition function. The main re- sults is a minimization procedure for semilinear automata. The proof is subtle and refers to decidability of existential Presburger arithmetic with divisibility predicates. Interestingly, the minimization is not obtained by the standard partition refinement procedure, and we demonstrate that this procedure does not necessarily terminate for semilinear automata.
From Regexes to Parsing Expression Grammars
Venue: arXiv cs.FL 2012
Year: 2012

Most scripting languages nowadays use regex pattern-matching libraries. These regex libraries borrow the syntax of regular expressions, but have an informal semantics that is different from the semantics of regular expressions, removing the commutativity of alternation and adding ad-hoc extensions that cannot be expressed by formalisms for efficient recognition of regular languages, such as deterministic finite automata. Parsing Expression Grammars are a formalism that can describe all deterministic context-free languages and has a simple computational model. In this paper, we present a formalization of regexes via transformation to Parsing Expression Grammars. The proposed transformation easily accommodates several of the common regex extensions, giving a formal meaning to them. It also provides a clear computational model that helps to estimate the efficiency of regex-based matchers, and a basis for specifying provably correct optimizations for them.
Predicting Group Evolution in the Social Network
Venue: arXiv cs.SI 2012
Year: 2012

Groups - social communities are important components of entire societies, analysed by means of the social network concept. Their immanent feature is continuous evolution over time. If we know how groups in the social network has evolved we can use this information and try to predict the next step in the given group evolution. In the paper, a new aproach for group evolution prediction is presented and examined. Experimental studies on four evolving social networks revealed that (i) the prediction based on the simple input features may be very accurate, (ii) some classifiers are more precise than the others and (iii) parameters of the group evolution extracion method significantly influence the prediction quality.
The Domino Effect in Decentralized Wireless Networks
Venue: arXiv cs.IT 2012
Year: 2012

Convergence of resource allocation algorithms is well covered in the literature as convergence to a steady state is important due to stability and performance. However, research is lacking when it comes to the propagation of change that occur in a network due to new nodes arriving or old nodes leaving or updating their allocation. As change can propagate through the network in a manner similar to how domino pieces falls, we call this propagation of change the domino effect. In this paper we investigate how change at one node can affect other nodes for a simple power control algorithm. We provide analytical results from a deterministic network as well as a Poisson distributed network through percolation theory and provide simulation results that highlight some aspects of the domino effect. The difficulty of mitigating this domino effect lies in the fact that to avoid it, one needs to have a margin of tolerance for changes in the network. However, a high margin leads to poor system performance in a steady-state and therefore one has to consider a trade-off between performance and propagation of change.
Adaptive Differential Feedback in Time-Varying Multiuser MIMO Channels
Venue: arXiv cs.IT 2012
Year: 2012

In the context of a time-varying multiuser multiple-input-multiple-output (MIMO) system, we design recursive least squares based adaptive predictors and differential quantizers to minimize the sum mean squared error of the overall system. Using the fact that the scalar entries of the left singular matrix of a Gaussian MIMO channel becomes almost Gaussian distributed even for a small number of transmit antennas, we perform adaptive differential quantization of the relevant singular matrix entries. Compared to the algorithms in the existing differential feedback literature, our proposed quantizer provides three advantages: first, the controller parameters are flexible enough to adapt themselves to different vehicle speeds; second, the model is backward adaptive i.e., the base station and receiver can agree upon the predictor and variance estimator coefficients without explicit exchange of the parameters; third, it can accurately model the system even when the correlation between two successive channel samples becomes as low as 0.05. Our simulation results show that our proposed method can reduce the required feedback by several kilobits per second for vehicle speeds up to 20 km/h (channel tracker) and 10 km/h (singular vector tracker). The proposed system also outperforms a fixed quantizer, with same feedback overhead, in terms of bit error rate up to 30 km/h.
Design & Simulation of 128x Interpolator Filter
Venue: arXiv cs.ET 2012
Year: 2012

This paper presents the design consideration and simulation of interpolator of OSR 128. The proposed structure uses the half band filers & Comb/Sinc filter. Experimental result shows that proposed interpolator achieves the design specification, and also has good noise rejection capabilities. The interpolator accepts the input at 44.1 kHz for applications like CD & DVD audio. The interpolation filter can be applied to the delta sigma DAC. The related work is done with the MATLAB & XILINX ISE simulators. The maximum operating frequency is achieved as 34.584 MHz.
Stuck in Traffic (SiT) Attacks: A Framework for Identifying Stealthy Attacks that Cause Traffic Congestion
Venue: arXiv cs.NI 2012
Year: 2012

Recent advances in wireless technologies have enabled many new applications in Intelligent Transportation Systems (ITS) such as collision avoidance, cooperative driving, congestion avoidance, and traffic optimization. Due to the vulnerable nature of wireless communication against interference and intentional jamming, ITS face new challenges to ensure the reliability and the safety of the overall system. In this paper, we expose a class of stealthy attacks -- Stuck in Traffic (SiT) attacks -- that aim to cause congestion by exploiting how drivers make decisions based on smart traffic signs. An attacker mounting a SiT attack solves a Markov Decision Process problem to find optimal/suboptimal attack policies in which he/she interferes with a well-chosen subset of signals that are based on the state of the system. We apply Approximate Policy Iteration (API) algorithms to derive potent attack policies. We evaluate their performance on a number of systems and compare them to other attack policies including random, myopic and DoS attack policies. The generated policies, albeit suboptimal, are shown to significantly outperform other attack policies as they maximize the expected cumulative reward from the standpoint of the attacker.
Downlink Coordinated Multi-Point with Overhead Modeling in Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2012
Year: 2012

Coordinated multi-point (CoMP) communication is attractive for heterogeneous cellular networks (HCNs) for interference reduction. However, previous approaches to CoMP face two major hurdles in HCNs. First, they usually ignore the inter-cell overhead messaging delay, although it results in an irreducible performance bound. Second, they consider the grid or Wyner model for base station locations, which is not appropriate for HCN BS locations which are numerous and haphazard. Even for conventional macrocell networks without overlaid small cells, SINR results are not tractable in the grid model nor accurate in the Wyner model. To overcome these hurdles, we develop a novel analytical framework which includes the impact of overhead delay for CoMP evaluation in HCNs. This framework can be used for a class of CoMP schemes without user data sharing. As an example, we apply it to downlink CoMP zero-forcing beamforming (ZFBF), and see significant divergence from previous work. For example, we show that CoMP ZFBF does not increase throughput when the overhead channel delay is larger than 60% of the channel coherence time. We also find that, in most cases, coordinating with only one other cell is nearly optimum for downlink CoMP ZFBF.
Design of English-Hindi Translation Memory for Efficient Translation
Venue: arXiv cs.CL 2012
Year: 2012

Developing parallel corpora is an important and a difficult activity for Machine Translation. This requires manual annotation by Human Translators. Translating same text again is a useless activity. There are tools available to implement this for European Languages, but no such tool is available for Indian Languages. In this paper we present a tool for Indian Languages which not only provides automatic translations of the previously available translation but also provides multiple translations, in cases where a sentence has multiple translations, in ranked list of suggestive translations for a sentence. Moreover this tool also lets translators have global and local saving options of their work, so that they may share it with others, which further lightens the task.
A single-item continuous double auction game
Venue: arXiv cs.GT 2012
Year: 2012

A double auction game with an infinite number of buyers and sellers is introduced. All sellers posses one unit of a good, all buyers desire to buy one unit. Each seller and each buyer has a private valuation of the good. The distribution of the valuations define supply and demand functions. One unit of the good is auctioned. At successive, discrete time instances, a player is randomly selected to make a bid (buyer) or an ask (seller). When the maximum of the bids becomes larger than the minimum of the asks, a transaction occurs and the auction is closed. The players have to choose the value of their bid or ask before the auction starts and use this value when they are selected. Assuming that the supply and demand functions are known, expected profits as functions of the strategies are derived, as well as expected transaction prices. It is shown that for linear supply and demand functions, there exists at most one Bayesian Nash equilibrium. Competitive behaviour is not an equilibrium of the game. For linear supply and demand functions, the sum of the expected profit of the sellers and the buyers is the same for the Bayesian Nash equilibrium and the market where players behave competitively. Connections are made with the ZI-C traders model and the $k$-double auction.
Online Learning in Decentralized Multiuser Resource Sharing Problems
Venue: arXiv cs.LG 2012
Year: 2012

In this paper, we consider the general scenario of resource sharing in a decentralized system when the resource rewards/qualities are time-varying and unknown to the users, and using the same resource by multiple users leads to reduced quality due to resource sharing. Firstly, we consider a user-independent reward model with no communication between the users, where a user gets feedback about the congestion level in the resource it uses. Secondly, we consider user-specific rewards and allow costly communication between the users. The users have a cooperative goal of achieving the highest system utility. There are multiple obstacles in achieving this goal such as the decentralized nature of the system, unknown resource qualities, communication, computation and switching costs. We propose distributed learning algorithms with logarithmic regret with respect to the optimal allocation. Our logarithmic regret result holds under both i.i.d. and Markovian reward models, as well as under communication, computation and switching costs.
Typed Answer Set Programming and Inverse Lambda Algorithms
Venue: arXiv cs.AI 2012
Year: 2012

Our broader goal is to automatically translate English sentences into formulas in appropriate knowledge representation languages as a step towards understanding and thus answering questions with respect to English text. Our focus in this paper is on the language of Answer Set Programming (ASP). Our approach to translate sentences to ASP rules is inspired by Montague's use of lambda calculus formulas as meaning of words and phrases. With ASP as the target language the meaning of words and phrases are ASP-lambda formulas. In an earlier work we illustrated our approach by manually developing a dictionary of words and their ASP-lambda formulas. However such an approach is not scalable. In this paper our focus is on two algorithms that allow one to construct ASP-lambda formulas in an inverse manner. In particular the two algorithms take as input two lambda-calculus expressions G and H and compute a lambda-calculus expression F such that F with input as G, denoted by F@G, is equal to H; and similarly G@F = H. We present correctness and complexity results about these algorithms. To do that we develop the notion of typed ASP-lambda calculus theories and their orders and use it in developing the completeness results. (To appear in Theory and Practice of Logic Programming.)
Optimal Linear Transceiver Designs for Cognitive Two-Way Relay Networks
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies a cooperative cognitive radio network where two primary users (PUs) exchange information with the help of a secondary user (SU) that is equipped with multiple antennas and in return, the SU superimposes its own messages along with the primary transmission. The fundamental problem in the considered network is the design of transmission strategies at the secondary node. It involves three basic elements: first, how to split the power for relaying the primary signals and for transmitting the secondary signals; second, what two-way relay strategy should be used to assist the bidirectional communication between the two PUs; third, how to jointly design the primary and secondary transmit precoders. This work aims to address this problem by proposing a transmission framework of maximizing the achievable rate of the SU while maintaining the rate requirements of the two PUs. Three well-known and practical two-way relay strategies are considered: amplify-and-forward (AF), bit level XOR based decode-and-forward (DF-XOR) and symbol level superposition coding based DF (DF-SUP). For each relay strategy, although the design problem is non-convex, we find the optimal solution by using certain transformation techniques and optimization tools such as semidefinite programming (SDP) and second-order cone programming (SOCP). Closed-form solutions are also obtained under certain conditions. Simulation results show that when the rate requirements of the two PUs are symmetric, by using the DF-XOR strategy and applying the proposed optimal precoding, the SU requires the least power for relaying and thus reserves the most power to transmit its own signal. In the asymmetric scenario, on the other hand, the DF-SUP strategy with the corresponding optimal precoding is the best.
Fast Routing Table Construction Using Small Messages
Venue: arXiv cs.DC 2012
Year: 2012

We describe a distributed randomized algorithm computing approximate distances and routes that approximate shortest paths. Let n denote the number of nodes in the graph, and let HD denote the hop diameter of the graph, i.e., the diameter of the graph when all edges are considered to have unit weight. Given 0 < eps <= 1/2, our algorithm runs in weak-O(n^(1/2 + eps) + HD) communication rounds using messages of O(log n) bits and guarantees a stretch of O(eps^(-1) log eps^(-1)) with high probability. This is the first distributed algorithm approximating weighted shortest paths that uses small messages and runs in weak-o(n) time (in graphs where HD in weak-o(n)). The time complexity nearly matches the lower bounds of weak-Omega(sqrt(n) + HD) in the small-messages model that hold for stateless routing (where routing decisions do not depend on the traversed path) as well as approximation of the weigthed diameter. Our scheme replaces the original identifiers of the nodes by labels of size O(log eps^(-1) log n). We show that no algorithm that keeps the original identifiers and runs for weak-o(n) rounds can achieve a polylogarithmic approximation ratio. Variations of our techniques yield a number of fast distributed approximation algorithms solving related problems using small messages. Specifically, we present algorithms that run in weak-O(n^(1/2 + eps) + HD) rounds for a given 0 < eps <= 1/2, and solve, with high probability, the following problems: - O(eps^(-1))-approximation for the Generalized Steiner Forest (the running time in this case has an additive weak-O(t^(1 + 2eps)) term, where t is the number of terminals); - O(eps^(-2))-approximation of weighted distances, using node labels of size O(eps^(-1) log n) and weak-O(n^(eps)) bits of memory per node; - O(eps^(-1))-approximation of the weighted diameter; - O(eps^(-3))-approximate shortest paths using the labels 1,...,n.
Robust Beamforming for Wireless Information and Power Transmission
Venue: arXiv cs.IT 2012
Year: 2012

In this letter, we study the robust beamforming problem for the multi-antenna wireless broadcasting system with simultaneous information and power transmission, under the assumption of imperfect channel state information (CSI) at the transmitter. Following the worst-case deterministic model, our objective is to maximize the worst-case harvested energy for the energy receiver while guaranteeing that the rate for the information receiver is above a threshold for all possible channel realizations. Such problem is nonconvex with infinite number of constraints. Using certain transformation techniques, we convert this problem into a relaxed semidefinite programming problem (SDP) which can be solved efficiently. We further show that the solution of the relaxed SDP problem is always rank-one. This indicates that the relaxation is tight and we can get the optimal solution for the original problem. Simulation results are presented to validate the effectiveness of the proposed algorithm.
Shared Information -- New Insights and Problems in Decomposing Information in Complex Systems
Venue: arXiv cs.IT 2012
Year: 2012

How can the information that a set ${X_{1},...,X_{n}}$ of random variables contains about another random variable $S$ be decomposed? To what extent do different subgroups provide the same, i.e. shared or redundant, information, carry unique information or interact for the emergence of synergistic information? Recently Williams and Beer proposed such a decomposition based on natural properties for shared information. While these properties fix the structure of the decomposition, they do not uniquely specify the values of the different terms. Therefore, we investigate additional properties such as strong symmetry and left monotonicity. We find that strong symmetry is incompatible with the properties proposed by Williams and Beer. Although left monotonicity is a very natural property for an information measure it is not fulfilled by any of the proposed measures. We also study a geometric framework for information decompositions and ask whether it is possible to represent shared information by a family of posterior distributions. Finally, we draw connections to the notions of shared knowledge and common knowledge in game theory. While many people believe that independent variables cannot share information, we show that in game theory independent agents can have shared knowledge, but not common knowledge. We conclude that intuition and heuristic arguments do not suffice when arguing about information.
GADT meet Subtyping
Venue: arXiv cs.PL 2012
Year: 2012

While generalized abstract datatypes (GADT) are now considered well-understood, adding them to a language with a notion of subtyping comes with a few surprises. What does it mean for a GADT parameter to be covariant? The answer turns out to be quite subtle. It involves fine-grained properties of the subtyping relation that raise interesting design questions. We allow variance annotations in GADT definitions, study their soundness, and present a sound and complete algorithm to check them. Our work may be applied to real-world ML-like languages with explicit subtyping such as OCaml, or to languages with general subtyping constraints.