OpenRaiser/Intern-Atlas huggingface dataset:
Loop Calculus and Belief Propagation for q-ary Alphabet: Loop Tower
Venue: arXiv cs.IT 2008
Year: 2008

Loop Calculus introduced in [Chertkov, Chernyak '06] constitutes a new theoretical tool that explicitly expresses the symbol Maximum-A-Posteriori (MAP) solution of a general statistical inference problem via a solution of the Belief Propagation (BP) equations. This finding brought a new significance to the BP concept, which in the past was thought of as just a loop-free approximation. In this paper we continue a discussion of the Loop Calculus. We introduce an invariant formulation which allows to generalize the Loop Calculus approach to a q-are alphabet.
The pitfalls of verifying floating-point computations
Venue: arXiv cs.PL 2008
Year: 2008

Current critical systems commonly use a lot of floating-point computations, and thus the testing or static analysis of programs containing floating-point operators has become a priority. However, correctly defining the semantics of common implementations of floating-point is tricky, because semantics may change with many factors beyond source-code level, such as choices made by compilers. We here give concrete examples of problems that can appear and solutions to implement in analysis software.
Estimation of the Rate-Distortion Function
Venue: arXiv cs.IT 2008
Year: 2008

Motivated by questions in lossy data compression and by theoretical considerations, we examine the problem of estimating the rate-distortion function of an unknown (not necessarily discrete-valued) source from empirical data. Our focus is the behavior of the so-called "plug-in" estimator, which is simply the rate-distortion function of the empirical distribution of the observed data. Sufficient conditions are given for its consistency, and examples are provided to demonstrate that in certain cases it fails to converge to the true rate-distortion function. The analysis of its performance is complicated by the fact that the rate-distortion function is not continuous in the source distribution; the underlying mathematical problem is closely related to the classical problem of establishing the consistency of maximum likelihood estimators. General consistency results are given for the plug-in estimator applied to a broad class of sources, including all stationary and ergodic ones. A more general class of estimation problems is also considered, arising in the context of lossy data compression when the allowed class of coding distributions is restricted; analogous results are developed for the plug-in estimator in that case. Finally, consistency theorems are formulated for modified (e.g., penalized) versions of the plug-in, and for estimating the optimal reproduction distribution.
The General Gaussian Multiple Access and Two-Way Wire-Tap Channels: Achievable Rates and Cooperative Jamming
Venue: arXiv cs.IT 2008
Year: 2008

The General Gaussian Multiple Access Wire-Tap Channel (GGMAC-WT) and the Gaussian Two-Way Wire-Tap Channel (GTW-WT) are considered. In the GGMAC-WT, multiple users communicate with an intended receiver in the presence of an eavesdropper who receives their signals through another GMAC. In the GTW-WT, two users communicate with each other over a common Gaussian channel, with an eavesdropper listening through a GMAC. A secrecy measure that is suitable for this multi-terminal environment is defined, and achievable secrecy rate regions are found for both channels. For both cases, the power allocations maximizing the achievable secrecy sum-rate are determined. It is seen that the optimum policy may prevent some terminals from transmission in order to preserve the secrecy of the system. Inspired by this construct, a new scheme, \ital{cooperative jamming}, is proposed, where users who are prevented from transmitting according to the secrecy sum-rate maximizing power allocation policy "jam" the eavesdropper, thereby helping the remaining users. This scheme is shown to increase the achievable secrecy sum-rate. Overall, our results show that in multiple-access scenarios, users can help each other to collectively achieve positive secrecy rates. In other words, cooperation among users can be invaluable for achieving secrecy for the system.
Slope One Predictors for Online Rating-Based Collaborative Filtering
Venue: arXiv cs.DB 2008
Year: 2008

Rating-based collaborative filtering is the process of predicting how a user would rate a given item from other user ratings. We propose three related slope one schemes with predictors of the form f(x) = x + b, which precompute the average difference between the ratings of one item and another for users who rated both. Slope one algorithms are easy to implement, efficient to query, reasonably accurate, and they support both online queries and dynamic updates, which makes them good candidates for real-world systems. The basic slope one scheme is suggested as a new reference scheme for collaborative filtering. By factoring in items that a user liked separately from items that a user disliked, we achieve results competitive with slower memory-based schemes over the standard benchmark EachMovie and Movielens data sets while better fulfilling the desiderata of CF applications.
Analysis of Steiner subtrees of Random Trees for Traceroute Algorithms
Venue: arXiv cs.NI 2008
Year: 2008

We consider in this paper the problem of discovering, via a traceroute algorithm, the topology of a network, whose graph is spanned by an infinite branching process. A subset of nodes is selected according to some criterion. As a measure of efficiency of the algorithm, the Steiner distance of the selected nodes, i.e. the size of the spanning sub-tree of these nodes, is investigated. For the selection of nodes, two criteria are considered: A node is randomly selected with a probability, which is either independent of the depth of the node (uniform model) or else in the depth biased model, is exponentially decaying with respect to its depth. The limiting behavior the size of the discovered subtree is investigated for both models.
A Comparison of Five Probabilistic View-Size Estimation Techniques in OLAP
Venue: arXiv cs.DB 2008
Year: 2008

A data warehouse cannot materialize all possible views, hence we must estimate quickly, accurately, and reliably the size of views to determine the best candidates for materialization. Many available techniques for view-size estimation make particular statistical assumptions and their error can be large. Comparatively, unassuming probabilistic techniques are slower, but they estimate accurately and reliability very large view sizes using little memory. We compare five unassuming hashing-based view-size estimation techniques including Stochastic Probabilistic Counting and LogLog Probabilistic Counting. Our experiments show that only Generalized Counting, Gibbons-Tirthapura, and Adaptive Counting provide universally tight estimates irrespective of the size of the view; of those, only Adaptive Counting remains constantly fast as we increase the memory budget.
Asynchronous Event-Driven Particle Algorithms
Venue: arXiv cs.OH 2008
Year: 2008

We present, in a unifying way, the main components of three asynchronous event-driven algorithms for simulating physical systems of interacting particles. The first example, hard-particle molecular dynamics, is well-known. We also present a recently-developed diffusion kinetic Monte Carlo algorithm, as well as a novel stochastic molecular-dynamics algorithm that builds on the Direct Simulation Monte Carlo. We explain how to effectively combine asynchronous event-driven with classical time-driven or with synchronous event-driven handling. Finally, we discuss some promises and challenges for event-driven simulation of realistic physical systems.
A theorem on the quantum evaluation of Weight Enumerators for a certain class of Cyclic Codes with a note on Cyclotomic cosets
Venue: arXiv cs.IT 2008
Year: 2008

This note is a stripped down version of a published paper on the Potts partition function, where we concentrate solely on the linear coding aspect of our approach. It is meant as a resource for people interested in coding theory but who do not know much of the mathematics involved and how quantum computation may provide a speed up in the computation of a very important quantity in coding theory. We provide a theorem on the quantum computation of the Weight Enumerator polynomial for a restricted family of cyclic codes. The complexity of obtaining an exact evaluation is $O(k^{2s}(\log q)^{2})$, where $s$ is a parameter which determines the class of cyclic codes in question, $q$ is the characteristic of the finite field over which the code is defined, and $k$ is the dimension of the code. We also provide an overview of cyclotomic cosets and discuss applications including how they can be used to speed up the computation of the weight enumerator polynomial (which is related to the Potts partition function). We also give an algorithm which returns the coset leaders and the size of each coset from the list $\{0,1,2,...,N-1\}$, whose time complexity is soft-O(N). This algorithm uses standard techniques but we include it as a resource for students. Note that cyclotomic cosets do not improve the asymptotic complexity of the computation of weight enumerators.
The use of the logarithm of the variate in the calculation of differential entropy among certain related statistical distributions
Venue: arXiv cs.IT 2009
Year: 2009

This paper demonstrates that basic statistics (mean, variance) of the logarithm of the variate itself can be used in the calculation of differential entropy among random variables known to be multiples and powers of a common underlying variate. For the same set of distributions, the variance of the differential self-information is shown also to be a function of statistics of the logarithmic variate. Then entropy and its "variance" can be estimated using only statistics of the logarithmic variate plus constants, without reference to the traditional parameters of the variate.
A Generalized Sampling Theorem for Frequency Localized Signals
Venue: arXiv cs.IT 2009
Year: 2009

A generalized sampling theorem for frequency localized signals is presented. The generalization in the proposed model of sampling is twofold: (1) It applies to various prefilters effecting a "soft" bandlimitation, (2) an approximate reconstruction from sample values rather than a perfect one is obtained (though the former might be "practically perfect" in many cases). For an arbitrary finite-energy signal the frequency localization is performed by a prefilter realizing a crosscorrelation with a function of prescribed properties. The range of the filter, the so-called localization space, is described in some detail. Regular sampling is applied and a reconstruction formula is given. For the reconstruction error a general error estimate is derived and connections between a critical sampling interval and notions of "soft bandwidth" for the prefilter are indicated. Examples based on the sinc-function, Gaussian functions and B-splines are discussed.
Universal Reinforcement Learning
Venue: arXiv cs.IT 2009
Year: 2009

We consider an agent interacting with an unmodeled environment. At each time, the agent makes an observation, takes an action, and incurs a cost. Its actions can influence future observations and costs. The goal is to minimize the long-term average cost. We propose a novel algorithm, known as the active LZ algorithm, for optimal control based on ideas from the Lempel-Ziv scheme for universal data compression and prediction. We establish that, under the active LZ algorithm, if there exists an integer $K$ such that the future is conditionally independent of the past given a window of $K$ consecutive actions and observations, then the average cost converges to the optimum. Experimental results involving the game of Rock-Paper-Scissors illustrate merits of the algorithm.
Design: One, but in different forms
Venue: arXiv cs.HC 2009
Year: 2009

This overview paper defends an augmented cognitively oriented generic-design hypothesis: there are both significant similarities between the design activities implemented in different situations and crucial differences between these and other cognitive activities; yet, characteristics of a design situation (related to the design process, the designers, and the artefact) introduce specificities in the corresponding cognitive activities and structures that are used, and in the resulting designs. We thus augment the classical generic-design hypothesis with that of different forms of designing. We review the data available in the cognitive design research literature and propose a series of candidates underlying such forms of design, outlining a number of directions requiring further elaboration.
A Generic Approach to Coalition Formation
Venue: arXiv cs.GT 2009
Year: 2009

We propose an abstract approach to coalition formation that focuses on simple merge and split rules transforming partitions of a group of players. We identify conditions under which every iteration of these rules yields a unique partition. The main conceptual tool is a specific notion of a stable partition. The results are parametrized by a preference relation between partitions of a group of players and naturally apply to coalitional TU-games, hedonic games and exchange economy games.
Log-concavity property of the error probability with application to local bounds for wireless communications
Venue: arXiv cs.IT 2009
Year: 2009

A clear understanding the behavior of the error probability (EP) as a function of signal-to-noise ratio (SNR) and other system parameters is fundamental for assessing the design of digital wireless communication systems.We propose an analytical framework based on the log-concavity property of the EP which we prove for a wide family of multidimensional modulation formats in the presence of Gaussian disturbances and fading. Based on this property, we construct a class of local bounds for the EP that improve known generic bounds in a given region of the SNR and are invertible, as well as easily tractable for further analysis. This concept is motivated by the fact that communication systems often operate with performance in a certain region of interest (ROI) and, thus, it may be advantageous to have tighter bounds within this region instead of generic bounds valid for all SNRs. We present a possible application of these local bounds, but their relevance is beyond the example made in this paper.
A new approach for scientific data dissemination in developing countries: a case of Indonesia
Venue: arXiv cs.CY 2009
Year: 2009

This short paper is intended as an additional progress report to share our experiences in Indonesia on collecting, integrating and disseminating both global and local scientific data across the country through the web technology. Our recent efforts are exerted on improving the local public access to global scientific data, and on the other hand encouraging the local scientific data to be more accessible for the global communities. We have maintained well-connected infrastructure and some web-based information management systems to realize such objectives. This paper is especially focused on introducing the ARSIP for mirroring global as well as sharing local scientific data, and the newly developed Indonesian Scientific Index for integrating local scientific data through an automated intelligent indexing system.
Valence extraction using EM selection and co-occurrence matrices
Venue: arXiv cs.CL 2009
Year: 2009

This paper discusses two new procedures for extracting verb valences from raw texts, with an application to the Polish language. The first novel technique, the EM selection algorithm, performs unsupervised disambiguation of valence frame forests, obtained by applying a non-probabilistic deep grammar parser and some post-processing to the text. The second new idea concerns filtering of incorrect frames detected in the parsed text and is motivated by an observation that verbs which take similar arguments tend to have similar frames. This phenomenon is described in terms of newly introduced co-occurrence matrices. Using co-occurrence matrices, we split filtering into two steps. The list of valid arguments is first determined for each verb, whereas the pattern according to which the arguments are combined into frames is computed in the following stage. Our best extracted dictionary reaches an $F$-score of 45%, compared to an $F$-score of 39% for the standard frame-based BHT filtering.
Opportunistic Relaying in Wireless Networks
Venue: arXiv cs.IT 2009
Year: 2009

Relay networks having $n$ source-to-destination pairs and $m$ half-duplex relays, all operating in the same frequency band in the presence of block fading, are analyzed. This setup has attracted significant attention and several relaying protocols have been reported in the literature. However, most of the proposed solutions require either centrally coordinated scheduling or detailed channel state information (CSI) at the transmitter side. Here, an opportunistic relaying scheme is proposed, which alleviates these limitations. The scheme entails a two-hop communication protocol, in which sources communicate with destinations only through half-duplex relays. The key idea is to schedule at each hop only a subset of nodes that can benefit from \emph{multiuser diversity}. To select the source and destination nodes for each hop, it requires only CSI at receivers (relays for the first hop, and destination nodes for the second hop) and an integer-value CSI feedback to the transmitters. For the case when $n$ is large and $m$ is fixed, it is shown that the proposed scheme achieves a system throughput of $m/2$ bits/s/Hz. In contrast, the information-theoretic upper bound of $(m/2)\log \log n$ bits/s/Hz is achievable only with more demanding CSI assumptions and cooperation between the relays. Furthermore, it is shown that, under the condition that the product of block duration and system bandwidth scales faster than $\log n$, the achievable throughput of the proposed scheme scales as $Θ({\log n})$. Notably, this is proven to be the optimal throughput scaling even if centralized scheduling is allowed, thus proving the optimality of the proposed scheme in the scaling law sense.
Disjointness is hard in the multi-party number on the forehead model
Venue: arXiv cs.CC 2009
Year: 2009

We show that disjointness requires randomized communication Omega(n^{1/(k+1)}/2^{2^k}) in the general k-party number-on-the-forehead model of complexity. The previous best lower bound for k >= 3 was log(n)/(k-1). Our results give a separation between nondeterministic and randomized multiparty number-on-the-forehead communication complexity for up to k=log log n - O(log log log n) many players. Also by a reduction of Beame, Pitassi, and Segerlind, these results imply subexponential lower bounds on the size of proofs needed to refute certain unsatisfiable CNFs in a broad class of proof systems, including tree-like Lovasz-Schrijver proofs.
Concave Programming Upper Bounds on the Capacity of 2-D Constraints
Venue: arXiv cs.IT 2009
Year: 2009

The capacity of 1-D constraints is given by the entropy of a corresponding stationary maxentropic Markov chain. Namely, the entropy is maximized over a set of probability distributions, which is defined by some linear requirements. In this paper, certain aspects of this characterization are extended to 2-D constraints. The result is a method for calculating an upper bound on the capacity of 2-D constraints. The key steps are: The maxentropic stationary probability distribution on square configurations is considered. A set of linear equalities and inequalities is derived from this stationarity. The result is a concave program, which can be easily solved numerically. Our method improves upon previous upper bounds for the capacity of the 2-D ``no independent bits'' constraint, as well as certain 2-D RLL constraints.
Hash Property and Coding Theorems for Sparse Matrices and Maximum-Likelihood Coding
Venue: arXiv cs.IT 2009
Year: 2009

The aim of this paper is to prove the achievability of several coding problems by using sparse matrices (the maximum column weight grows logarithmically in the block length) and maximal-likelihood (ML) coding. These problems are the Slepian-Wolf problem, the Gel'fand-Pinsker problem, the Wyner-Ziv problem, and the One-helps-one problem (source coding with partial side information at the decoder). To this end, the notion of a hash property for an ensemble of functions is introduced and it is proved that an ensemble of $q$-ary sparse matrices satisfies the hash property. Based on this property, it is proved that the rate of codes using sparse matrices and maximal-likelihood (ML) coding can achieve the optimal rate.
Subspace Pursuit for Compressive Sensing Signal Reconstruction
Venue: arXiv cs.NA 2009
Year: 2009

We propose a new method for reconstruction of sparse signals with and without noisy perturbations, termed the subspace pursuit algorithm. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques when applied to very sparse signals, and reconstruction accuracy of the same order as that of LP optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm can exactly reconstruct arbitrary sparse signals provided that the sensing matrix satisfies the restricted isometry property with a constant parameter. In the noisy setting and in the case that the signal is not exactly sparse, it can be shown that the mean squared error of the reconstruction is upper bounded by constant multiples of the measurement and signal perturbation energies.
Minimal weight expansions in Pisot bases
Venue: arXiv cs.DM 2009
Year: 2009

For applications to cryptography, it is important to represent numbers with a small number of non-zero digits (Hamming weight) or with small absolute sum of digits. The problem of finding representations with minimal weight has been solved for integer bases, e.g. by the non-adjacent form in base~2. In this paper, we consider numeration systems with respect to real bases $β$ which are Pisot numbers and prove that the expansions with minimal absolute sum of digits are recognizable by finite automata. When $β$ is the Golden Ratio, the Tribonacci number or the smallest Pisot number, we determine expansions with minimal number of digits $\pm1$ and give explicitely the finite automata recognizing all these expansions. The average weight is lower than for the non-adjacent form.
Reflective visualization and verbalization of unconscious preference
Venue: arXiv cs.AI 2009
Year: 2009

A new method is presented, that can help a person become aware of his or her unconscious preferences, and convey them to others in the form of verbal explanation. The method combines the concepts of reflection, visualization, and verbalization. The method was tested in an experiment where the unconscious preferences of the subjects for various artworks were investigated. In the experiment, two lessons were learned. The first is that it helps the subjects become aware of their unconscious preferences to verbalize weak preferences as compared with strong preferences through discussion over preference diagrams. The second is that it is effective to introduce an adjustable factor into visualization to adapt to the differences in the subjects and to foster their mutual understanding.
Support Vector Machine Classification with Indefinite Kernels
Venue: arXiv cs.LG 2009
Year: 2009

We propose a method for support vector machine classification using indefinite kernels. Instead of directly minimizing or stabilizing a nonconvex loss function, our algorithm simultaneously computes support vectors and a proxy kernel matrix used in forming the loss. This can be interpreted as a penalized kernel learning problem where indefinite kernel matrices are treated as a noisy observations of a true Mercer kernel. Our formulation keeps the problem convex and relatively large problems can be solved efficiently using the projected gradient or analytic center cutting plane methods. We compare the performance of our technique with other methods on several classic data sets.