OpenRaiser/Intern-Atlas huggingface dataset:
A Version of Geiringer-like Theorem for Decision Making in the Environments with Randomness and Incomplete Information
Venue: arXiv cs.AI 2011
Year: 2011

Purpose: In recent years Monte-Carlo sampling methods, such as Monte Carlo tree search, have achieved tremendous success in model free reinforcement learning. A combination of the so called upper confidence bounds policy to preserve the "exploration vs. exploitation" balance to select actions for sample evaluations together with massive computing power to store and to update dynamically a rather large pre-evaluated game tree lead to the development of software that has beaten the top human player in the game of Go on a 9 by 9 board. Much effort in the current research is devoted to widening the range of applicability of the Monte-Carlo sampling methodology to partially observable Markov decision processes with non-immediate payoffs. The main challenge introduced by randomness and incomplete information is to deal with the action evaluation at the chance nodes due to drastic differences in the possible payoffs the same action could lead to. The aim of this article is to establish a version of a theorem that originated from population genetics and has been later adopted in evolutionary computation theory that will lead to novel Monte-Carlo sampling algorithms that provably increase the AI potential. Due to space limitations the actual algorithms themselves will be presented in the sequel papers, however, the current paper provides a solid mathematical foundation for the development of such algorithms and explains why they are so promising.
Implementing an Automatic Differentiator in ACL2
Venue: arXiv cs.SC 2011
Year: 2011

The foundational theory of differentiation was developed as part of the original release of ACL2(r). In work reported at the last ACL2 Workshop, we presented theorems justifying the usual differentiation rules, including the chain rule and the derivative of inverse functions. However, the process of applying these theorems to formalize the derivative of a particular function is completely manual. More recently, we developed a macro and supporting functions that can automate this process. This macro uses the ACL2 table facility to keep track of functions and their derivatives, and it also interacts with the macro that introduces inverse functions in ACL2(r), so that their derivatives can also be automated. In this paper, we present the implementation of this macro and related functions.
Formal Verification of an Iterative Low-Power x86 Floating-Point Multiplier with Redundant Feedback
Venue: arXiv cs.LO 2011
Year: 2011

We present the formal verification of a low-power x86 floating-point multiplier. The multiplier operates iteratively and feeds back intermediate results in redundant representation. It supports x87 and SSE instructions in various precisions and can block the issuing of new instructions. The design has been optimized for low-power operation and has not been constrained by the formal verification effort. Additional improvements for the implementation were identified through formal verification. The formal verification of the design also incorporates the implementation of clock-gating and control logic. The core of the verification effort was based on ACL2 theorem proving. Additionally, model checking has been used to verify some properties of the floating-point scheduler that are relevant for the correct operation of the unit.
Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model Technical Report
Venue: arXiv cs.SI 2011
Year: 2011

In many real-world situations, different and often opposite opinions, innovations, or products are competing with one another for their social influence in a networked society. In this paper, we study competitive influence propagation in social networks under the competitive linear threshold (CLT) model, an extension to the classic linear threshold model. Under the CLT model, we focus on the problem that one entity tries to block the influence propagation of its competing entity as much as possible by strategically selecting a number of seed nodes that could initiate its own influence propagation. We call this problem the influence blocking maximization (IBM) problem. We prove that the objective function of IBM in the CLT model is submodular, and thus a greedy algorithm could achieve 1-1/e approximation ratio. However, the greedy algorithm requires Monte-Carlo simulations of competitive influence propagation, which makes the algorithm not efficient. We design an efficient algorithm CLDAG, which utilizes the properties of the CLT model, to address this issue. We conduct extensive simulations of CLDAG, the greedy algorithm, and other baseline algorithms on real-world and synthetic datasets. Our results show that CLDAG is able to provide best accuracy in par with the greedy algorithm and often better than other algorithms, while it is two orders of magnitude faster than the greedy algorithm.
The Similarity between Stochastic Kronecker and Chung-Lu Graph Models
Venue: arXiv cs.SI 2011
Year: 2011

The analysis of massive graphs is now becoming a very important part of science and industrial research. This has led to the construction of a large variety of graph models, each with their own advantages. The Stochastic Kronecker Graph (SKG) model has been chosen by the Graph500 steering committee to create supercomputer benchmarks for graph algorithms. The major reasons for this are its easy parallelization and ability to mirror real data. Although SKG is easy to implement, there is little understanding of the properties and behavior of this model. We show that the parallel variant of the edge-configuration model given by Chung and Lu (referred to as CL) is notably similar to the SKG model. The graph properties of an SKG are extremely close to those of a CL graph generated with the appropriate parameters. Indeed, the final probability matrix used by SKG is almost identical to that of a CL model. This implies that the graph distribution represented by SKG is almost the same as that given by a CL model. We also show that when it comes to fitting real data, CL performs as well as SKG based on empirical studies of graph properties. CL has the added benefit of a trivially simple fitting procedure and exactly matching the degree distribution. Our results suggest that users of the SKG model should consider the CL model because of its similar properties, simpler structure, and ability to fit a wider range of degree distributions. At the very least, CL is a good control model to compare against.
On Noisy Network Coding for a Gaussian Relay Chain Network with Correlated Noises
Venue: arXiv cs.IT 2011
Year: 2011

Noisy network coding, which elegantly combines the conventional compress-and-forward relaying strategy and ideas from network coding, has recently drawn much attention for its simplicity and optimality in achieving to within constant gap of the capacity of the multisource multicast Gaussian network. The constant-gap result, however, applies only to Gaussian relay networks with independent noises. This paper investigates the application of noisy network coding to networks with correlated noises. By focusing on a four-node Gaussian relay chain network with a particular noise correlation structure, it is shown that noisy network coding can no longer achieve to within constant gap to capacity with the choice of Gaussian inputs and Gaussian quantization. The cut-set bound of the relay chain network in this particular case, however, can be achieved to within half a bit by a simple concatenation of a correlation-aware noisy network coding strategy and a decode-and-forward scheme.
Joint Channel-Network Coding Strategies for Networks with Low Complexity Relays
Venue: arXiv cs.IT 2011
Year: 2011

We investigate joint network and channel coding schemes for networks when relay nodes are not capable of performing channel coding operations. Rather, channel encoding is performed at the source node while channel decoding is done only at the destination nodes. We examine three different decoding strategies: independent network-then-channel decoding, serial network and channel decoding, and joint network and channel decoding. Furthermore, we describe how to implement such joint network and channel decoding using iteratively decodable error correction codes. Using simple networks as a model, we derive achievable rate regions and use simulations to demonstrate the effectiveness of the three decoders.
Results on the Redundancy of Universal Compression for Finite-Length Sequences
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we investigate the redundancy of universal coding schemes on smooth parametric sources in the finite-length regime. We derive an upper bound on the probability of the event that a sequence of length $n$, chosen using Jeffreys' prior from the family of parametric sources with $d$ unknown parameters, is compressed with a redundancy smaller than $(1-ε)\frac{d}{2}\log n$ for any $ε>0$. Our results also confirm that for large enough $n$ and $d$, the average minimax redundancy provides a good estimate for the redundancy of most sources. Our result may be used to evaluate the performance of universal source coding schemes on finite-length sequences. Additionally, we precisely characterize the minimax redundancy for two--stage codes. We demonstrate that the two--stage assumption incurs a negligible redundancy especially when the number of source parameters is large. Finally, we show that the redundancy is significant in the compression of small sequences.
On a property of the $n$-dimensional cube
Venue: arXiv cs.DM 2011
Year: 2011

We show that in any subset of the vertices of $n$-dimensional cube that contains at least $2^{n-1}+1$ vertices ($n\geq 4$), there are four vertices that induce a claw, or there are eight vertices that induce the cycle of length eight.
Deciding of HMM parameters based on number of critical points for gesture recognition from motion capture data
Venue: arXiv cs.LG 2011
Year: 2011

This paper presents a method of choosing number of states of a HMM based on number of critical points of the motion capture data. The choice of Hidden Markov Models(HMM) parameters is crucial for recognizer's performance as it is the first step of the training and cannot be corrected automatically within HMM. In this article we define predictor of number of states based on number of critical points of the sequence and test its effectiveness against sample data.
A novel sampling theorem on the sphere
Venue: arXiv cs.IT 2011
Year: 2011

We develop a novel sampling theorem on the sphere and corresponding fast algorithms by associating the sphere with the torus through a periodic extension. The fundamental property of any sampling theorem is the number of samples required to represent a band-limited signal. To represent exactly a signal on the sphere band-limited at L, all sampling theorems on the sphere require O(L^2) samples. However, our sampling theorem requires less than half the number of samples of other equiangular sampling theorems on the sphere and an asymptotically identical, but smaller, number of samples than the Gauss-Legendre sampling theorem. The complexity of our algorithms scale as O(L^3), however, the continual use of fast Fourier transforms reduces the constant prefactor associated with the asymptotic scaling considerably, resulting in algorithms that are fast. Furthermore, we do not require any precomputation and our algorithms apply to both scalar and spin functions on the sphere without any change in computational complexity or computation time. We make our implementation of these algorithms available publicly and perform numerical experiments demonstrating their speed and accuracy up to very high band-limits. Finally, we highlight the advantages of our sampling theorem in the context of potential applications, notably in the field of compressive sampling.
Backdoors to Satisfaction
Venue: arXiv cs.DS 2011
Year: 2011

A backdoor set is a set of variables of a propositional formula such that fixing the truth values of the variables in the backdoor set moves the formula into some polynomial-time decidable class. If we know a small backdoor set we can reduce the question of whether the given formula is satisfiable to the same question for one or several easy formulas that belong to the tractable class under consideration. In this survey we review parameterized complexity results for problems that arise in the context of backdoor sets, such as the problem of finding a backdoor set of size at most k, parameterized by k. We also discuss recent results on backdoor sets for problems that are beyond NP.
Key Generation Using External Source Excitation: Capacity, Reliability, and Secrecy Exponent
Venue: arXiv cs.IT 2011
Year: 2011

We study the fundamental limits to secret key generation from an excited distributed source (EDS). In an EDS a pair of terminals observe dependent sources of randomness excited by a pre-arranged signal. We first determine the secret key capacity for such systems with one-way public messaging. We then characterize a tradeoff between the secret key rate and exponential bounds on the probability of key agreement failure and on the secrecy of the key generated. We find that there is a fundamental tradeoff between reliability and secrecy. We then explore this framework within the context of reciprocal wireless channels. In this setting, the users transmit pre-arranged excitation signals to each other. When the fading is Rayleigh, the observations of the users are jointly Gaussian sources. We show that an on-off excitation signal with an SNR-dependent duty cycle achieves the secret key capacity of this system. Furthermore, we characterize a fundamental metric -- minimum energy per key bit for reliable key generation -- and show that in contrast to conventional AWGN channels, there is a non-zero threshold SNR that achieves the minimum energy per key bit. The capacity achieving on-off excitation signal achieves the minimum energy per key bit at any SNR below the threshold. Finally, we build off our error exponent results to investigate the energy required to generate a key using a finite block length. Again we find that on-off excitation signals yield an improvement when compared to constant excitation signals. In addition to Rayleigh fading, we analyze the performance of a system based on binary channel phase quantization.
Multilingual Schema Matching for Wikipedia Infoboxes
Venue: arXiv cs.DB 2011
Year: 2011

Recent research has taken advantage of Wikipedia's multilingualism as a resource for cross-language information retrieval and machine translation, as well as proposed techniques for enriching its cross-language structure. The availability of documents in multiple languages also opens up new opportunities for querying structured Wikipedia content, and in particular, to enable answers that straddle different languages. As a step towards supporting such queries, in this paper, we propose a method for identifying mappings between attributes from infoboxes that come from pages in different languages. Our approach finds mappings in a completely automated fashion. Because it does not require training data, it is scalable: not only can it be used to find mappings between many language pairs, but it is also effective for languages that are under-represented and lack sufficient training samples. Another important benefit of our approach is that it does not depend on syntactic similarity between attribute names, and thus, it can be applied to language pairs that have distinct morphologies. We have performed an extensive experimental evaluation using a corpus consisting of pages in Portuguese, Vietnamese, and English. The results show that not only does our approach obtain high precision and recall, but it also outperforms state-of-the-art techniques. We also present a case study which demonstrates that the multilingual mappings we derive lead to substantial improvements in answer quality and coverage for structured queries over Wikipedia content.
FPGA implementation of short critical path CORDIC-based approximation of the eight-point DCT
Venue: arXiv cs.AR 2011
Year: 2011

This paper presents an efficient approach for multiplierless implementation for eight-point DCT approximation, which based on coordinate rotation digital computer (CORDIC) algorithm. The main design objective is to make critical path of corresponding circuits shorter and reduce the combinational delay of proposed scheme.
Multi-Terminal Source Coding With Action Dependent Side Information
Venue: arXiv cs.IT 2011
Year: 2011

We consider multi-terminal source coding with a single encoder and multiple decoders where either the encoder or the decoders can take cost constrained actions which affect the quality of the side information present at the decoders. For the scenario where decoders take actions, we characterize the rate-cost trade-off region for lossless source coding, and give an achievability scheme for lossy source coding for two decoders which is optimum for a variety of special cases of interest. For the case where the encoder takes actions, we characterize the rate-cost trade-off for a class of lossless source coding scenarios with multiple decoders. Finally, we also consider extensions to other multi-terminal source coding settings with actions, and characterize the rate -distortion-cost tradeoff for a case of successive refinement with actions.
Individual and Domain Adaptation in Sentence Planning for Dialogue
Venue: arXiv cs.CL 2011
Year: 2011

One of the biggest challenges in the development and deployment of spoken dialogue systems is the design of the spoken language generation module. This challenge arises from the need for the generator to adapt to many features of the dialogue domain, user population, and dialogue context. A promising approach is trainable generation, which uses general-purpose linguistic knowledge that is automatically adapted to the features of interest, such as the application domain, individual user, or user group. In this paper we present and evaluate a trainable sentence planner for providing restaurant information in the MATCH dialogue system. We show that trainable sentence planning can produce complex information presentations whose quality is comparable to the output of a template-based generator tuned to this domain. We also show that our method easily supports adapting the sentence planner to individuals, and that the individualized sentence planners generally perform better than models trained and tested on a population of individuals. Previous work has documented and utilized individual preferences for content selection, but to our knowledge, these results provide the first demonstration of individual preferences for sentence planning operations, affecting the content order, discourse structure and sentence structure of system responses. Finally, we evaluate the contribution of different feature sets, and show that, in our application, n-gram features often do as well as features based on higher-level linguistic representations.
Conjunctive Query Answering for the Description Logic SHIQ
Venue: arXiv cs.AI 2011
Year: 2011

Conjunctive queries play an important role as an expressive query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, conjunctive query answering over DL knowledge bases is only poorly understood if transitive roles are admitted in the query. In this paper, we consider unions of conjunctive queries over knowledge bases formulated in the prominent DL SHIQ and allow transitive roles in both the query and the knowledge base. We show decidability of query answering in this setting and establish two tight complexity bounds: regarding combined complexity, we prove that there is a deterministic algorithm for query answering that needs time single exponential in the size of the KB and double exponential in the size of the query, which is optimal. Regarding data complexity, we prove containment in co-NP.
Extended RDF as a Semantic Foundation of Rule Markup Languages
Venue: arXiv cs.AI 2011
Year: 2011

Ontologies and automated reasoning are the building blocks of the Semantic Web initiative. Derivation rules can be included in an ontology to define derived concepts, based on base concepts. For example, rules allow to define the extension of a class or property, based on a complex relation between the extensions of the same or other classes and properties. On the other hand, the inclusion of negative information both in the form of negation-as-failure and explicit negative information is also needed to enable various forms of reasoning. In this paper, we extend RDF graphs with weak and strong negation, as well as derivation rules. The ERDF stable model semantics of the extended framework (Extended RDF) is defined, extending RDF(S) semantics. A distinctive feature of our theory, which is based on Partial Logic, is that both truth and falsity extensions of properties and classes are considered, allowing for truth value gaps. Our framework supports both closed-world and open-world reasoning through the explicit representation of the particular closed-world assumptions and the ERDF ontological categories of total properties and total classes.
Optimal and Approximate Q-value Functions for Decentralized POMDPs
Venue: arXiv cs.AI 2011
Year: 2011

Decision-theoretic planning is a popular approach to sequential decision making problems, because it treats uncertainty in sensing and acting in a principled way. In single-agent frameworks like MDPs and POMDPs, planning can be carried out by resorting to Q-value functions: an optimal Q-value function Q* is computed in a recursive manner by dynamic programming, and then an optimal policy is extracted from Q*. In this paper we study whether similar Q-value functions can be defined for decentralized POMDP models (Dec-POMDPs), and how policies can be extracted from such value functions. We define two forms of the optimal Q-value function for Dec-POMDPs: one that gives a normative description as the Q-value function of an optimal pure joint policy and another one that is sequentially rational and thus gives a recipe for computation. This computation, however, is infeasible for all but the smallest problems. Therefore, we analyze various approximate Q-value functions that allow for efficient computation. We describe how they relate, and we prove that they all provide an upper bound to the optimal Q-value function Q*. Finally, unifying some previous approaches for solving Dec-POMDPs, we describe a family of algorithms for extracting policies from such Q-value functions, and perform an experimental evaluation on existing test problems, including a new firefighting benchmark problem.