OpenRaiser/Intern-Atlas huggingface dataset:
On the $\mathbb{F}_2$-linear relations of Mersenne Twister pseudorandom number generators
Venue: arXiv cs.NA 2013
Year: 2013

Sequence generators obtained by linear recursions over the two-element field $\mathbb{F}_2$, i.e., $\mathbb{F}_2$-linear generators, are widely used as pseudorandom number generators. For example, the Mersenne Twister MT19937 is one of the most successful applications. An advantage of such generators is that we can assess them quickly by using theoretical criteria, such as the dimension of equidistribution with $v$-bit accuracy. To compute these dimensions, several polynomial-time lattice reduction algorithms have been proposed in the case of $\mathbb{F}_2$-linear generators. In this paper, in order to assess non-random bit patterns in dimensions that are higher than the dimension of equidistribution with $v$-bit accuracy,we focus on the relationship between points in the Couture--L'Ecuyer dual lattices and $\mathbb{F}_2$-linear relations on the most significant $v$ bits of output sequences, and consider a new figure of merit $N_v$ based on the minimum weight of $\mathbb{F}_2$-linear relations whose degrees are minimal for $v$. Next, we numerically show that MT19937 has low-weight $\mathbb{F}_2$-linear relations in dimensions higher than 623, and show that some output vectors with specific lags are rejected or have small $p$-values in the birthday spacings tests. We also report that some variants of Mersenne Twister, such as WELL generators, are significantly improved from the perspective of $N_v$.
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
Venue: arXiv cs.DS 2013
Year: 2013

Let ϕ(G) be the minimum conductance of an undirected graph G, and let 0=λ_1 <= λ_2 <=... <= λ_n <= 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k >= 2, ϕ(G) = O(k) λ_2 / \sqrt{λ_k}, and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any k. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if λ_k$ is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.
Systems of MDS codes from units and idempotents
Venue: arXiv cs.IT 2013
Year: 2013

Algebraic systems are constructed from which series of maximum distance separable (mds) codes are derived. The methods use unit and idempotent schemes.
When is tit-for-tat unbeatable?
Venue: arXiv cs.GT 2013
Year: 2013

We characterize the class of symmetric two-player games in which tit-for-tat cannot be beaten even by very sophisticated opponents in a repeated game. It turns out to be the class of exact potential games. More generally, there is a class of simple imitation rules that includes tit-for-tat but also imitate-the-best and imitate-if-better. Every decision rule in this class is essentially unbeatable in exact potential games. Our results apply to many interesting games including all symmetric 2x2 games, and standard examples of Cournot duopoly, price competition, public goods games, common pool resource games, and minimum effort coordination games.
Computing sum of sources over an arbitrary multiple access channel
Venue: arXiv cs.IT 2013
Year: 2013

The problem of computing sum of sources over a multiple access channel (MAC) is considered. Building on the technique of linear computation coding (LCC) proposed by Nazer and Gastpar [2007], we employ the ensemble of nested coset codes to derive a new set of sufficient conditions for computing the sum of sources over an \textit{arbitrary} MAC. The optimality of nested coset codes [Padakandla, Pradhan 2011] enables this technique outperform LCC even for linear MAC with a structural match. Examples of nonadditive MAC for which the technique proposed herein outperforms separation and systematic based computation are also presented. Finally, this technique is enhanced by incorporating separation based strategy, leading to a new set of sufficient conditions for computing the sum over a MAC.
Video Tester -- A multiple-metric framework for video quality assessment over IP networks
Venue: arXiv cs.MM 2013
Year: 2013

This paper presents an extensible and reusable framework which addresses the problem of video quality assessment over IP networks. The proposed tool (referred to as Video-Tester) supports raw uncompressed video encoding and decoding. It also includes different video over IP transmission methods (i.e.: RTP over UDP unicast and multicast, as well as RTP over TCP). In addition, it is furnished with a rich set of offline analysis capabilities. Video-Tester analysis includes QoS and bitstream parameters estimation (i.e.: bandwidth, packet inter-arrival time, jitter and loss rate, as well as GOP size and I-frame loss rate). Our design facilitates the integration of virtually any existing video quality metric thanks to the adopted Python-based modular approach. Video-Tester currently provides PSNR, SSIM, ITU-T G.1070 video quality metric, DIV and PSNR-based MOS estimations. In order to promote its use and extension, Video-Tester is open and publicly available.
On the Current Measurement Practices in Agile Software Development
Venue: arXiv cs.SE 2013
Year: 2013

Agile software development (ASD) methods were introduced as a reaction to traditional software development methods. Principles of these methods are different from traditional methods and so there are some different processes and activities in agile methods comparing to traditional methods. Thus ASD methods require different measurement practices comparing to traditional methods. Agile teams often do their projects in the simplest and most effective way so, measurement practices in agile methods are more important than traditional methods, because lack of appropriate and effective measurement practices, will increase risk of project. The aims of this paper are investigation on current measurement practices in ASD methods, collecting them together in one study and also reviewing agile version of Common Software Measurement International Consortium (COSMIC) publication.
Immersive VR Visualizations by VFIVE. Part 2: Applications
Venue: arXiv cs.GR 2013
Year: 2013

VFIVE is a scientific visualization application for CAVE-type immersive virtual reality systems. The source codes are freely available. VFIVE is used as a research tool in various VR systems. It also lays the groundwork for developments of new visualization software for CAVEs. In this paper, we pick up five CAVE systems in four different institutions in Japan. Applications of VFIVE in each CAVE system are summarized. Special emphases will be placed on scientific and technical achievements made possible by VFIVE.
Polar Codes For Broadcast Channels
Venue: arXiv cs.IT 2013
Year: 2013

Polar codes are introduced for discrete memoryless broadcast channels. For $m$-user deterministic broadcast channels, polarization is applied to map uniformly random message bits from $m$ independent messages to one codeword while satisfying broadcast constraints. The polarization-based codes achieve rates on the boundary of the private-message capacity region. For two-user noisy broadcast channels, polar implementations are presented for two information-theoretic schemes: i) Cover's superposition codes; ii) Marton's codes. Due to the structure of polarization, constraints on the auxiliary and channel-input distributions are identified to ensure proper alignment of polarization indices in the multi-user setting. The codes achieve rates on the capacity boundary of a few classes of broadcast channels (e.g., binary-input stochastically degraded). The complexity of encoding and decoding is $O(n*log n)$ where $n$ is the block length. In addition, polar code sequences obtain a stretched-exponential decay of $O(2^{-n^β})$ of the average block error probability where $0 < β< 0.5$.
Reuse, Temporal Dynamics, Interest Sharing, and Collaboration in Social Tagging Systems
Venue: arXiv cs.IR 2013
Year: 2013

User-generated content is shaping the dynamics of the World Wide Web. Indeed, an increasingly large number of systems provide mechanisms to support the growing demand for content creation, sharing, and management. Tagging systems are a particular class of these systems where users share and collaboratively annotate content such as photos and URLs. This collaborative behavior and the pool of user-generated metadata create opportunities to improve existing systems and to design new mechanisms. However, to realize this potential, it is necessary to understand the usage characteristics of current systems. This work addresses this issue characterizing three tagging systems (CiteULike, Connotea and del.icio.us) while focusing on three aspects: i) the patterns of information (tags and items) production; ii) the temporal dynamics of users' tag vocabularies; and, iii) the social aspects of tagging systems.
Generalizing Bounds on the Minimum Distance of Cyclic Codes Using Cyclic Product Codes
Venue: arXiv cs.IT 2013
Year: 2013

Two generalizations of the Hartmann--Tzeng (HT) bound on the minimum distance of q-ary cyclic codes are proposed. The first one is proven by embedding the given cyclic code into a cyclic product code. Furthermore, we show that unique decoding up to this bound is always possible and outline a quadratic-time syndrome-based error decoding algorithm. The second bound is stronger and the proof is more involved. Our technique of embedding the code into a cyclic product code can be applied to other bounds, too and therefore generalizes them.
Lovász's Theta Function, Rényi's Divergence and the Sphere-Packing Bound
Venue: arXiv cs.IT 2013
Year: 2013

Lovász's bound to the capacity of a graph and the the sphere-packing bound to the probability of error in channel coding are given a unified presentation as information radii of the Csiszár type using the R{é}nyi divergence in the classical-quantum setting. This brings together two results in coding theory that are usually considered as being of a very different nature, one being a "combinatorial" result and the other being "probabilistic". In the context of quantum information theory, this difference disappears.
Capacity Optimization through Sensing Threshold Adaptation for Cognitive Radio Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we propose the capacity optimization over sensing threshold for sensing-based cognitive radio networks. The objective function of the proposed optimization is to maximize the capacity at the secondary user subject to the constraints on the transmit power and the sensing threshold in order to protect the primary user. The defined optimization problem is a convex optimization over the transmit power and the sensing threshold where the concavity on sensing threshold is proved. The problem is solved by using Lagrange duality decomposition method in conjunction with a subgradient iterative algorithm and the numerical results show that the proposed optimization can lead to significant capacity maximization for the secondary user as long as the primary user can afford.
Random Access and Source-Channel Coding Error Exponents for Multiple Access Channels
Venue: arXiv cs.IT 2013
Year: 2013

A new universal coding/decoding scheme for random access with collision detection is given in the case of two senders. The result is used to give an achievable joint source-channel coding error exponent for multiple access channels in the case of independent sources. This exponent is improved in a modified model that admits error free 0 rate communication between the senders.
Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP
Venue: arXiv cs.DB 2013
Year: 2013

Ontology-based data access is concerned with querying incomplete data sources in the presence of domain-specific knowledge provided by an ontology. A central notion in this setting is that of an ontology-mediated query, which is a database query coupled with an ontology. In this paper, we study several classes of ontology-mediated queries, where the database queries are given as some form of conjunctive query and the ontologies are formulated in description logics or other relevant fragments of first-order logic, such as the guarded fragment and the unary-negation fragment. The contributions of the paper are three-fold. First, we characterize the expressive power of ontology-mediated queries in terms of fragments of disjunctive datalog. Second, we establish intimate connections between ontology-mediated queries and constraint satisfaction problems (CSPs) and their logical generalization, MMSNP formulas. Third, we exploit these connections to obtain new results regarding (i) first-order rewritability and datalog-rewritability of ontology-mediated queries, (ii) P/NP dichotomies for ontology-mediated queries, and (iii) the query containment problem for ontology-mediated queries.
SINR-based k-coverage probability in cellular networks with arbitrary shadowing
Venue: arXiv cs.NI 2013
Year: 2013

We give numerically tractable, explicit integral expressions for the distribution of the signal-to-interference-and-noise-ratio (SINR) experienced by a typical user in the down-link channel from the k-th strongest base stations of a cellular network modelled by Poisson point process on the plane. Our signal propagation-loss model comprises of a power-law path-loss function with arbitrarily distributed shadowing, independent across all base stations, with and without Rayleigh fading. Our results are valid in the whole domain of SINR, in particular for SINR<1, where one observes multiple coverage. In this latter aspect our paper complements previous studies reported in [Dhillon et al. JSAC 2012].
Inferring Parameters and Structure of Latent Variable Models by Variational Bayes
Venue: arXiv cs.LG 2013
Year: 2013

Current methods for learning graphical models with latent variables and a fixed structure estimate optimal values for the model parameters. Whereas this approach usually produces overfitting and suboptimal generalization performance, carrying out the Bayesian program of computing the full posterior distributions over the parameters remains a difficult problem. Moreover, learning the structure of models with latent variables, for which the Bayesian approach is crucial, is yet a harder problem. In this paper I present the Variational Bayes framework, which provides a solution to these problems. This approach approximates full posterior distributions over model parameters and structures, as well as latent variables, in an analytical manner without resorting to sampling methods. Unlike in the Laplace approximation, these posteriors are generally non-Gaussian and no Hessian needs to be computed. The resulting algorithm generalizes the standard Expectation Maximization algorithm, and its convergence is guaranteed. I demonstrate that this algorithm can be applied to a large class of models in several domains, including unsupervised clustering and blind source separation.
Artificial Decision Making Under Uncertainty in Intelligent Buildings
Venue: arXiv cs.AI 2013
Year: 2013

Our hypothesis is that by equipping certain agents in a multi-agent system controlling an intelligent building with automated decision support, two important factors will be increased. The first is energy saving in the building. The second is customer value---how the people in the building experience the effects of the actions of the agents. We give evidence for the truth of this hypothesis through experimental findings related to tools for artificial decision making. A number of assumptions related to agent control, through monitoring and delegation of tasks to other kinds of agents, of rooms at a test site are relaxed. Each assumption controls at least one uncertainty that complicates considerably the procedures for selecting actions part of each such agent. We show that in realistic decision situations, room-controlling agents can make bounded rational decisions even under dynamic real-time constraints. This result can be, and has been, generalized to other domains with even harsher time constraints.
Assessing the value of a candidate. Comparing belief function and possibility theories
Venue: arXiv cs.AI 2013
Year: 2013

The problem of assessing the value of a candidate is viewed here as a multiple combination problem. On the one hand a candidate can be evaluated according to different criteria, and on the other hand several experts are supposed to assess the value of candidates according to each criterion. Criteria are not equally important, experts are not equally competent or reliable. Moreover levels of satisfaction of criteria, or levels of confidence are only assumed to take their values in qualitative scales which are just linearly ordered. The problem is discussed within two frameworks, the transferable belief model and the qualitative possibility theory. They respectively offer a quantitative and a qualitative setting for handling the problem, providing thus a way to compare the nature of the underlying assumptions.
Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm
Venue: arXiv cs.LG 2013
Year: 2013

Learning Bayesian networks is often cast as an optimization problem, where the computational task is to find a structure that maximizes a statistically motivated score. By and large, existing learning tools address this optimization problem using standard heuristic search techniques. Since the search space is extremely large, such search procedures can spend most of the time examining candidates that are extremely unreasonable. This problem becomes critical when we deal with data sets that are large either in the number of instances, or the number of attributes. In this paper, we introduce an algorithm that achieves faster learning by restricting the search space. This iterative algorithm restricts the parents of each variable to belong to a small subset of candidates. We then search for a network that satisfies these constraints. The learned network is then used for selecting better candidates for the next iteration. We evaluate this algorithm both on synthetic and real-life data. Our results show that it is significantly faster than alternative search procedures without loss of quality in the learned structures.
Faithful Approximations of Belief Functions
Venue: arXiv cs.AI 2013
Year: 2013

A conceptual foundation for approximation of belief functions is proposed and investigated. It is based on the requirements of consistency and closeness. An optimal approximation is studied. Unfortunately, the computation of the optimal approximation turns out to be intractable. Hence, various heuristic methods are proposed and experimantally evaluated both in terms of their accuracy and in terms of the speed of computation. These methods are compared to the earlier proposed approximations of belief functions.
Probabilistic Latent Semantic Analysis
Venue: arXiv cs.LG 2013
Year: 2013

Probabilistic Latent Semantic Analysis is a novel statistical technique for the analysis of two-mode and co-occurrence data, which has applications in information retrieval and filtering, natural language processing, machine learning from text, and in related areas. Compared to standard Latent Semantic Analysis which stems from linear algebra and performs a Singular Value Decomposition of co-occurrence tables, the proposed method is based on a mixture decomposition derived from a latent class model. This results in a more principled approach which has a solid foundation in statistics. In order to avoid overfitting, we propose a widely applicable generalization of maximum likelihood model fitting by tempered EM. Our approach yields substantial and consistent improvements over Latent Semantic Analysis in a number of experiments.
Lazy Evaluation of Symmetric Bayesian Decision Problems
Venue: arXiv cs.AI 2013
Year: 2013

Solving symmetric Bayesian decision problems is a computationally intensive task to perform regardless of the algorithm used. In this paper we propose a method for improving the efficiency of algorithms for solving Bayesian decision problems. The method is based on the principle of lazy evaluation - a principle recently shown to improve the efficiency of inference in Bayesian networks. The basic idea is to maintain decompositions of potentials and to postpone computations for as long as possible. The efficiency improvements obtained with the lazy evaluation based method is emphasized through examples. Finally, the lazy evaluation based method is compared with the hugin and valuation-based systems architectures for solving symmetric Bayesian decision problems.
Bayes Nets in Educational Assessment: Where Do the Numbers Come From?
Venue: arXiv cs.AI 2013
Year: 2013

As observations and student models become complex, educational assessments that exploit advances in technology and cognitive psychology can outstrip familiar testing models and analytic methods. Within the Portal conceptual framework for assessment design, Bayesian inference networks (BINs) record beliefs about students' knowledge and skills, in light of what they say and do. Joining evidence model BIN fragments- which contain observable variables and pointers to student model variables - to the student model allows one to update belief about knowledge and skills as observations arrive. Markov Chain Monte Carlo (MCMC) techniques can estimate the required conditional probabilities from empirical data, supplemented by expert judgment or substantive theory. Details for the special cases of item response theory (IRT) and multivariate latent class modeling are given, with a numerical example of the latter.
Welldefined Decision Scenarios
Venue: arXiv cs.AI 2013
Year: 2013

Influence diagrams serve as a powerful tool for modelling symmetric decision problems. When solving an influence diagram we determine a set of strategies for the decisions involved. A strategy for a decision variable is in principle a function over its past. However, some of the past may be irrelevant for the decision, and for computational reasons it is important not to deal with redundant variables in the strategies. We show that current methods (e.g. the "Decision Bayes-ball" algorithm by Shachter UAI98) do not determine the relevant past, and we present a complete algorithm. Actually, this paper takes a more general outset: When formulating a decision scenario as an influence diagram, a linear temporal ordering of the decisions variables is required. This constraint ensures that the decision scenario is welldefined. However, the structure of a decision scenario often yields certain decisions conditionally independent, and it is therefore unnecessary to impose a linear temporal ordering on the decisions. In this paper we deal with partial influence diagrams i.e. influence diagrams with only a partial temporal ordering specified. We present a set of conditions which are necessary and sufficient to ensure that a partial influence diagram is welldefined. These conditions are used as a basis for the construction of an algorithm for determining whether or not a partial influence diagram is welldefined.