OpenRaiser/Intern-Atlas huggingface dataset:
Continuous Value Function Approximation for Sequential Bidding Policies
Venue: arXiv cs.AI 2013
Year: 2013

Market-based mechanisms such as auctions are being studied as an appropriate means for resource allocation in distributed and mulitagent decision problems. When agents value resources in combination rather than in isolation, they must often deliberate about appropriate bidding strategies for a sequence of auctions offering resources of interest. We briefly describe a discrete dynamic programming model for constructing appropriate bidding policies for resources exhibiting both complementarities and substitutability. We then introduce a continuous approximation of this model, assuming that money (or the numeraire good) is infinitely divisible. Though this has the potential to reduce the computational cost of computing policies, value functions in the transformed problem do not have a convenient closed form representation. We develop {em grid-based} approximation for such value functions, representing value functions using piecewise linear approximations. We show that these methods can offer significant computational savings with relatively small cost in solution quality.
Discovering the Hidden Structure of Complex Dynamic Systems
Venue: arXiv cs.AI 2013
Year: 2013

Dynamic Bayesian networks provide a compact and natural representation for complex dynamic systems. However, in many cases, there is no expert available from whom a model can be elicited. Learning provides an alternative approach for constructing models of dynamic systems. In this paper, we address some of the crucial computational aspects of learning the structure of dynamic systems, particularly those where some relevant variables are partially observed or even entirely unknown. Our approach is based on the Structural Expectation Maximization (SEM) algorithm. The main computational cost of the SEM algorithm is the gathering of expected sufficient statistics. We propose a novel approximation scheme that allows these sufficient statistics to be computed efficiently. We also investigate the fundamental problem of discovering the existence of hidden variables without exhaustive and expensive search. Our approach is based on the observation that, in dynamic systems, ignoring a hidden variable typically results in a violation of the Markov property. Thus, our algorithm searches for such violations in the data, and introduces hidden variables to explain them. We provide empirical results showing that the algorithm is able to learn the dynamics of complex systems in a computationally tractable way.
Hybrid Probabilistic Programs: Algorithms and Complexity
Venue: arXiv cs.AI 2013
Year: 2013

Hybrid Probabilistic Programs (HPPs) are logic programs that allow the programmer to explicitly encode his knowledge of the dependencies between events being described in the program. In this paper, we classify HPPs into three classes called HPP_1,HPP_2 and HPP_r,r>= 3. For these classes, we provide three types of results for HPPs. First, we develop algorithms to compute the set of all ground consequences of an HPP. Then we provide algorithms and complexity results for the problems of entailment ("Given an HPP P and a query Q as input, is Q a logical consequence of P?") and consistency ("Given an HPP P as input, is P consistent?"). Our results provide a fine characterization of when polynomial algorithms exist for the above problems, and when these problems become intractable.
Data Analysis with Bayesian Networks: A Bootstrap Approach
Venue: arXiv cs.LG 2013
Year: 2013

In recent years there has been significant progress in algorithms and methods for inducing Bayesian networks from data. However, in complex data analysis problems, we need to go beyond being satisfied with inducing networks with high scores. We need to provide confidence measures on features of these networks: Is the existence of an edge between two nodes warranted? Is the Markov blanket of a given node robust? Can we say something about the ordering of the variables? We should be able to address these questions, even when the amount of data is not enough to induce a high scoring network. In this paper we propose Efron's Bootstrap as a computationally efficient approach for answering these questions. In addition, we propose to use these confidence measures to induce better structures from the data, and to detect the presence of latent variables.
A General Algorithm for Approximate Inference and its Application to Hybrid Bayes Nets
Venue: arXiv cs.AI 2013
Year: 2013

The clique tree algorithm is the standard method for doing inference in Bayesian networks. It works by manipulating clique potentials - distributions over the variables in a clique. While this approach works well for many networks, it is limited by the need to maintain an exact representation of the clique potentials. This paper presents a new unified approach that combines approximate inference and the clique tree algorithm, thereby circumventing this limitation. Many known approximate inference algorithms can be viewed as instances of this approach. The algorithm essentially does clique tree propagation, using approximate inference to estimate the densities in each clique. In many settings, the computation of the approximate clique potential can be done easily using statistical importance sampling. Iterations are used to gradually improve the quality of the estimation.
My Brain is Full: When More Memory Helps
Venue: arXiv cs.AI 2013
Year: 2013

We consider the problem of finding good finite-horizon policies for POMDPs under the expected reward metric. The policies considered are {em free finite-memory policies with limited memory}; a policy is a mapping from the space of observation-memory pairs to the space of action-memeory pairs (the policy updates the memory as it goes), and the number of possible memory states is a parameter of the input to the policy-finding algorithms. The algorithms considered here are preliminary implementations of three search heuristics: local search, simulated annealing, and genetic algorithms. We compare their outcomes to each other and to the optimal policies for each instance. We compare run times of each policy and of a dynamic programming algorithm for POMDPs developed by Hansen that iteratively improves a finite-state controller --- the previous state of the art for finite memory policies. The value of the best policy can only improve as the amount of memory increases, up to the amount needed for an optimal finite-memory policy. Our most surprising finding is that more memory helps in another way: given more memory than is needed for an optimal policy, the algorithms are more likely to converge to optimal-valued policies.
Learning Finite-State Controllers for Partially Observable Environments
Venue: arXiv cs.AI 2013
Year: 2013

Reactive (memoryless) policies are sufficient in completely observable Markov decision processes (MDPs), but some kind of memory is usually necessary for optimal control of a partially observable MDP. Policies with finite memory can be represented as finite-state automata. In this paper, we extend Baird and Moore's VAPS algorithm to the problem of learning general finite-state automata. Because it performs stochastic gradient descent, this algorithm can be shown to converge to a locally optimal finite-state controller. We provide the details of the algorithm and then consider the question of under what conditions stochastic gradient descent will outperform exact gradient descent. We conclude with empirical results comparing the performance of stochastic and exact gradient descent, and showing the ability of our algorithm to extract the useful information contained in the sequence of past observations to compensate for the lack of observability at each time-step.
Loopy Belief Propagation for Approximate Inference: An Empirical Study
Venue: arXiv cs.AI 2013
Year: 2013

Recently, researchers have demonstrated that loopy belief propagation - the use of Pearls polytree algorithm IN a Bayesian network WITH loops OF error- correcting codes.The most dramatic instance OF this IS the near Shannon - limit performance OF Turbo Codes codes whose decoding algorithm IS equivalent TO loopy belief propagation IN a chain - structured Bayesian network. IN this paper we ask : IS there something special about the error - correcting code context, OR does loopy propagation WORK AS an approximate inference schemeIN a more general setting? We compare the marginals computed using loopy propagation TO the exact ones IN four Bayesian network architectures, including two real - world networks : ALARM AND QMR.We find that the loopy beliefs often converge AND WHEN they do, they give a good approximation TO the correct marginals.However,ON the QMR network, the loopy beliefs oscillated AND had no obvious relationship TO the correct posteriors. We present SOME initial investigations INTO the cause OF these oscillations, AND show that SOME simple methods OF preventing them lead TO the wrong results.
Learning Bayesian Networks from Incomplete Data with Stochastic Search Algorithms
Venue: arXiv cs.AI 2013
Year: 2013

This paper describes stochastic search approaches, including a new stochastic algorithm and an adaptive mutation operator, for learning Bayesian networks from incomplete data. This problem is characterized by a huge solution space with a highly multimodal landscape. State-of-the-art approaches all involve using deterministic approaches such as the expectation-maximization algorithm. These approaches are guaranteed to find local maxima, but do not explore the landscape for other modes. Our approach evolves structure and the missing data. We compare our stochastic algorithms and show they all produce accurate results.
Accelerating EM: An Empirical Study
Venue: arXiv cs.LG 2013
Year: 2013

Many applications require that we learn the parameters of a model from data. EM is a method used to learn the parameters of probabilistic models for which the data for some of the variables in the models is either missing or hidden. There are instances in which this method is slow to converge. Therefore, several accelerations have been proposed to improve the method. None of the proposed acceleration methods are theoretically dominant and experimental comparisons are lacking. In this paper, we present the different proposed accelerations and try to compare them experimentally. From the results of the experiments, we argue that some acceleration of EM is always possible, but that which acceleration is superior depends on properties of the problem.
Bayesian Networks for Dependability Analysis: an Application to Digital Control Reliability
Venue: arXiv cs.AI 2013
Year: 2013

Bayesian Networks (BN) provide robust probabilistic methods of reasoning under uncertainty, but despite their formal grounds are strictly based on the notion of conditional dependence, not much attention has been paid so far to their use in dependability analysis. The aim of this paper is to propose BN as a suitable tool for dependability analysis, by challenging the formalism with basic issues arising in dependability tasks. We will discuss how both modeling and analysis issues can be naturally dealt with by BN. Moreover, we will show how some limitations intrinsic to combinatorial dependability methods such as Fault Trees can be overcome using BN. This will be pursued through the study of a real-world example concerning the reliability analysis of a redundant digital Programmable Logic Controller (PLC) with majority voting 2:3
A Possibilistic Model for Qualitative Sequential Decision Problems under Uncertainty in Partially Observable Environments
Venue: arXiv cs.AI 2013
Year: 2013

In this article we propose a qualitative (ordinal) counterpart for the Partially Observable Markov Decision Processes model (POMDP) in which the uncertainty, as well as the preferences of the agent, are modeled by possibility distributions. This qualitative counterpart of the POMDP model relies on a possibilistic theory of decision under uncertainty, recently developed. One advantage of such a qualitative framework is its ability to escape from the classical obstacle of stochastic POMDPs, in which even with a finite state space, the obtained belief state space of the POMDP is infinite. Instead, in the possibilistic framework even if exponentially larger than the state space, the belief state space remains finite.
How to Elicit Many Probabilities
Venue: arXiv cs.AI 2013
Year: 2013

In building Bayesian belief networks, the elicitation of all probabilities required can be a major obstacle. We learned the extent of this often-cited observation in the construction of the probabilistic part of a complex influence diagram in the field of cancer treatment. Based upon our negative experiences with existing methods, we designed a new method for probability elicitation from domain experts. The method combines various ideas, among which are the ideas of transcribing probabilities and of using a scale with both numerical and verbal anchors for marking assessments. In the construction of the probabilistic part of our influence diagram, the method proved to allow for the elicitation of many probabilities in little time.
Mutual Redundancies in Inter-human Communication Systems: Steps Towards a Calculus of Processing Meaning
Venue: arXiv cs.DL 2013
Year: 2013

The study of inter-human communication requires a more complex framework than Shannon's (1948) mathematical theory of communication because "information" is defined in the latter case as meaningless uncertainty. Assuming that meaning cannot be communicated, we extend Shannon's theory by defining mutual redundancy as a positional counterpart of the relational communication of information. Mutual redundancy indicates the surplus of meanings that can be provided to the exchanges in reflexive communications. The information is redundant because based on "pure sets," that is, without subtraction of mutual information in the overlaps. We show that in the three-dimensional case (e.g., of a Triple Helix of university-industry-government relations), mutual redundancy is equal to mutual information (Rxyz = Txyz); but when the dimensionality is even, the sign is different. We generalize to the measurement in N dimensions and proceed to the interpretation. Using Luhmann's social-systems theory and/or Giddens' structuration theory, mutual redundancy can be provided with an interpretation in the sociological case: different meaning-processing structures code and decode with other algorithms. A surplus of ("absent") options can then be generated that add to the redundancy. Luhmann's "functional (sub)systems" of expectations or Giddens' "rule-resource sets" are positioned mutually, but coupled operationally in events or "instantiated" in actions. Shannon-type information is generated by the mediation, but the "structures" are (re-)positioned towards one another as sets of (potentially counterfactual) expectations. The structural differences among the coding and decoding algorithms provide a source of additional options in reflexive and anticipatory communications.
On Wiener Phase Noise Channels at High Signal-to-Noise Ratio
Venue: arXiv cs.IT 2013
Year: 2013

Consider a waveform channel where the transmitted signal is corrupted by Wiener phase noise and additive white Gaussian noise (AWGN). A discrete-time channel model that takes into account the effect of filtering on the phase noise is developed. The model is based on a multi-sample receiver which, at high Signal-to-Noise Ratio (SNR), achieves a rate that grows logarithmically with the SNR if the number of samples per symbol grows with the square-root of the SNR. Moreover, the pre-log factor is at least 1/2 in this case.
An asymmetric primitive based on the Bivariate Function Hard Problem
Venue: arXiv cs.CR 2013
Year: 2013

The Bivariate Function Hard Problem (BFHP) has been in existence implicitly in almost all number theoretic based cryptosystems. This work defines the BFHP in a more general setting and produces an efficient asymmetric cryptosystem. The cryptosystem has a complexity order of O(n^2) for both encryption and decryption.
Outer Bound of the Capacity Region for Identification via Multiple Access Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we consider the identification (ID) via multiple access channels (MACs). In the general MAC the ID capacity region includes the ordinary transmission (TR) capacity region. In this paper we discuss the converse coding theorem. We estimate two types of error probabilities of identification for rates outside capacity region, deriving some function which serves as a lower bound of the sum of two error probabilities of identification. This function has a property that it tends to zero as $n\to \infty$ for noisy channels satisfying the strong converse property. Using this property, we establish that the transmission capacity region is equal to the ID capacity for the MAC satisfying the strong converse property. To derive the result we introduce a new resolvability problem on the output from the MAC. We further develop a new method of converting the direct coding theorem for the above MAC resolvability problem into the converse coding theorem for the ID via MACs.
Repair for Distributed Storage Systems with Erasure Channels
Venue: arXiv cs.IT 2013
Year: 2013

We study the repair problem of distributed storage systems in erasure networks where the packets transmitted from surviving nodes to the new node might be lost. The fundamental storage-bandwidth tradeoff is calculated by multicasting analysis in erasure networks. The optimal tradeoff bound can be asymptotically achieved when the number of transmission (packets) goes to infinity. For a limited number of transmission, we study the probability of successful regenerating. Then, we investigate two approaches of increasing the probability of successful regenerating, namely, by connecting more surviving nodes or by increasing the storage space of nodes. Using more nodes may pose larger delay and in certain situation it might not be possible to connect to more nodes too. We show that in addition to reducing repair bandwidth, increasing storage space can also increase reliability for repair.
Coded Splitting Tree Protocols
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents a novel approach to multiple access control called coded splitting tree protocol. The approach builds on the known tree splitting protocols, code structure and successive interference cancellation (SIC). Several instances of the tree splitting protocol are initiated, each instance is terminated prematurely and subsequently iterated. The combined set of leaves from all the tree instances can then be viewed as a graph code, which is decodable using belief propagation. The main design problem is determining the order of splitting, which enables successful decoding as early as possible. Evaluations show that the proposed protocol provides considerable gains over the standard tree splitting protocol applying SIC. The improvement comes at the expense of an increased feedback and receiver complexity.
Femtocell Architectures with Spectrum Sharing for Cellular Radio Networks
Venue: arXiv cs.NI 2013
Year: 2013

Femtocells are an emerging technology aimed at providing gains to both network operators and end-users. These gains come at a cost of increased interference, specifically the cross network interference between the macrocell and femtocell networks. This interference is one of the main performance limiting factors in allowing an underlaid femtocell network to share the spectrum with the cellular network. To manage this interference, we first propose a femtocell architecture that orthog- onally partitions the network bandwidth between the macrocell and femtocell networks. This scheme eliminates the cross network interference thus giving the femtocells more freedom over their use of the spectrum. Specifically, no interference constraint is imposed by the cellular network allowing femto users to transmit at a constant power on randomly selected channels. Although simple, this scheme is enough to give gains up to 200% in sum rate. We then propose a second architecture where both networks share the bandwidth simultaneously. A femtocell power control scheme that relies on minimal coordination with the macrocell base station is used in conjunction with an interference sensing channel assignment mechanism. These two schemes together yield sum rate gains up to 200%. We then develop a technique for macro users to join a nearby femtocell and share a common chan- nel with a femtocell user through the use of successive interfer- ence cancellation. By adding this mechanism to the power control and channel assignment schemes, we show sum rate gains over 300% and up to 90% power savings for macrocell users.
Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
Venue: arXiv cs.DS 2013
Year: 2013

Cutwidth of a digraph is a width measure introduced by Chudnovsky, Fradkin, and Seymour [4] in connection with development of a structural theory for tournaments, or more generally, for semi-complete digraphs. In this paper we provide an algorithm with running time 2^{O(\sqrt{k log k})} * n^{O(1)} that tests whether the cutwidth of a given n-vertex semi-complete digraph is at most k, improving upon the currently fastest algorithm of the second author [18] that works in 2^{O(k)} * n^2 time. As a byproduct, we obtain a new algorithm for Feedback Arc Set in tournaments (FAST) with running time 2^{c\sqrt{k}} * n^{O(1)}, where c = 2π/ \sqrt(3)*\ln(2) <= 5.24, that is simpler than the algorithms of Feige [9] and of Karpinski and Schudy[16], both also working in 2^{O(\sqrt{k})} * n^{O(1)} time. Our techniques can be applied also to other layout problems on semi-complete digraphs. We show that the Optimal Linear Arrangement problem, a close relative of Feedback Arc Set, can be solved in 2^{O(k^{1/3} \sqrt{\log k})} * n^{O(1)} time, where k is the target cost of the ordering.
Merging Uncertain Knowledge Bases in a Possibilistic Logic Framework
Venue: arXiv cs.AI 2013
Year: 2013

This paper addresses the problem of merging uncertain information in the framework of possibilistic logic. It presents several syntactic combination rules to merge possibilistic knowledge bases, provided by different sources, into a new possibilistic knowledge base. These combination rules are first described at the meta-level outside the language of possibilistic logic. Next, an extension of possibilistic logic, where the combination rules are inside the language, is proposed. A proof system in a sequent form, which is sound and complete with respect to the possibilistic logic semantics, is given.
A Hybrid Algorithm to Compute Marginal and Joint Beliefs in Bayesian Networks and Its Complexity
Venue: arXiv cs.AI 2013
Year: 2013

There exist two general forms of exact algorithms for updating probabilities in Bayesian Networks. The first approach involves using a structure, usually a clique tree, and performing local message based calculation to extract the belief in each variable. The second general class of algorithm involves the use of non-serial dynamic programming techniques to extract the belief in some desired group of variables. In this paper we present a hybrid algorithm based on the latter approach yet possessing the ability to retrieve the belief in all single variables. The technique is advantageous in that it saves a NP-hard computation step over using one algorithm of each type. Furthermore, this technique re-enforces a conjecture of Jensen and Jensen [JJ94] in that it still requires a single NP-hard step to set up the structure on which inference is performed, as we show by confirming Li and D'Ambrosio's [LD94] conjectured NP-hardness of OFP.