OpenRaiser/Intern-Atlas huggingface dataset:
Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
Venue: arXiv cs.AI 2012
Year: 2012

Inference for probabilistic graphical models is still very much a practical challenge in large domains. The commonly used and effective belief propagation (BP) algorithm and its generalizations often do not converge when applied to hard, real-life inference tasks. While it is widely recognized that the scheduling of messages in these algorithms may have significant consequences, this issue remains largely unexplored. In this work, we address the question of how to schedule messages for asynchronous propagation so that a fixed point is reached faster and more often. We first show that any reasonable asynchronous BP converges to a unique fixed point under conditions similar to those that guarantee convergence of synchronous BP. In addition, we show that the convergence rate of a simple round-robin schedule is at least as good as that of synchronous propagation. We then propose residual belief propagation (RBP), a novel, easy-to-implement, asynchronous propagation algorithm that schedules messages in an informed way, that pushes down a bound on the distance from the fixed point. Finally, we demonstrate the superiority of RBP over state-of-the-art methods for a variety of challenging synthetic and real-life problems: RBP converges significantly more often than other methods; and it significantly reduces running time until convergence, even when other methods converge.
From influence diagrams to multi-operator cluster DAGs
Venue: arXiv cs.AI 2012
Year: 2012

There exist several architectures to solve influence diagrams using local computations, such as the Shenoy-Shafer, the HUGIN, or the Lazy Propagation architectures. They all extend usual variable elimination algorithms thanks to the use of so-called 'potentials'. In this paper, we introduce a new architecture, called the Multi-operator Cluster DAG architecture, which can produce decompositions with an improved constrained induced-width, and therefore induce potentially exponential gains. Its principle is to benefit from the composite nature of influence diagrams, instead of using uniform potentials, in order to better analyze the problem structure.
An Efficient Optimal-Equilibrium Algorithm for Two-player Game Trees
Venue: arXiv cs.GT 2012
Year: 2012

Two-player complete-information game trees are perhaps the simplest possible setting for studying general-sum games and the computational problem of finding equilibria. These games admit a simple bottom-up algorithm for finding subgame perfect Nash equilibria efficiently. However, such an algorithm can fail to identify optimal equilibria, such as those that maximize social welfare. The reason is that, counterintuitively, probabilistic action choices are sometimes needed to achieve maximum payoffs. We provide a novel polynomial-time algorithm for this problem that explicitly reasons about stochastic decisions and demonstrate its use in an example card game.
Sequential Document Representations and Simplicial Curves
Venue: arXiv cs.IR 2012
Year: 2012

The popular bag of words assumption represents a document as a histogram of word occurrences. While computationally efficient, such a representation is unable to maintain any sequential information. We present a continuous and differentiable sequential document representation that goes beyond the bag of words assumption, and yet is efficient and effective. This representation employs smooth curves in the multinomial simplex to account for sequential information. We discuss the representation and its geometric properties and demonstrate its applicability for the task of text classification.
Bayesian Multicategory Support Vector Machines
Venue: arXiv cs.LG 2012
Year: 2012

We show that the multi-class support vector machine (MSVM) proposed by Lee et. al. (2004), can be viewed as a MAP estimation procedure under an appropriate probabilistic interpretation of the classifier. We also show that this interpretation can be extended to a hierarchical Bayesian architecture and to a fully-Bayesian inference procedure for multi-class classification based on data augmentation. We present empirical results that show that the advantages of the Bayesian formalism are obtained without a loss in classification accuracy.
A simple approach for finding the globally optimal Bayesian network structure
Venue: arXiv cs.AI 2012
Year: 2012

We study the problem of learning the best Bayesian network structure with respect to a decomposable score such as BDe, BIC or AIC. This problem is known to be NP-hard, which means that solving it becomes quickly infeasible as the number of variables increases. Nevertheless, in this paper we show that it is possible to learn the best Bayesian network structure with over 30 variables, which covers many practically interesting cases. Our algorithm is less complicated and more efficient than the techniques presented earlier. It can be easily parallelized, and offers a possibility for efficient exploration of the best networks consistent with different variable orderings. In the experimental part of the paper we compare the performance of the algorithm to the previous state-of-the-art algorithm. Free source-code and an online-demo can be found at http://b-course.hiit.fi/bene.
Practical Linear Value-approximation Techniques for First-order MDPs
Venue: arXiv cs.AI 2012
Year: 2012

Recent work on approximate linear programming (ALP) techniques for first-order Markov Decision Processes (FOMDPs) represents the value function linearly w.r.t. a set of first-order basis functions and uses linear programming techniques to determine suitable weights. This approach offers the advantage that it does not require simplification of the first-order value function, and allows one to solve FOMDPs independent of a specific domain instantiation. In this paper, we address several questions to enhance the applicability of this work: (1) Can we extend the first-order ALP framework to approximate policy iteration to address performance deficiencies of previous approaches? (2) Can we automatically generate basis functions and evaluate their impact on value function quality? (3) How can we decompose intractable problems with universally quantified rewards into tractable subproblems? We propose answers to these questions along with a number of novel optimizations and provide a comparative empirical evaluation on logistics problems from the ICAPS 2004 Probabilistic Planning Competition.
Single-Source Dilation-Bounded Minimum Spanning Trees
Venue: arXiv cs.CG 2012
Year: 2012

Given a set $S$ of points in the plane, a geometric network for $S$ is a graph $G$ with vertex set $S$ and straight edges. We consider a broadcasting situation, where one point $r \in S$ is a designated source. Given a dilation factor $δ$, we ask for a geometric network $G$ such that for every point $v \in S$ there is a path from $r$ to $v$ in $G$ of length at most $δ|rv|$, and such that the total edge length is minimized. We show that finding such a network of minimum total edge length is NP-hard, and give an approximation algorithm.
Implicit Density Estimation by Local Moment Matching to Sample from Auto-Encoders
Venue: arXiv cs.LG 2012
Year: 2012

Recent work suggests that some auto-encoder variants do a good job of capturing the local manifold structure of the unknown data generating density. This paper contributes to the mathematical understanding of this phenomenon and helps define better justified sampling algorithms for deep learning based on auto-encoder variants. We consider an MCMC where each step samples from a Gaussian whose mean and covariance matrix depend on the previous state, defines through its asymptotic distribution a target density. First, we show that good choices (in the sense of consistency) for these mean and covariance functions are the local expected value and local covariance under that target density. Then we show that an auto-encoder with a contractive penalty captures estimators of these local moments in its reconstruction function and its Jacobian. A contribution of this work is thus a novel alternative to maximum-likelihood density estimation, which we call local moment matching. It also justifies a recently proposed sampling algorithm for the Contractive Auto-Encoder and extends it to the Denoising Auto-Encoder.
A note on coloring line arrangements
Venue: arXiv cs.CG 2012
Year: 2012

We show that the lines of every arrangement of $n$ lines in the plane can be colored with $O(\sqrt{n/ \log n})$ colors such that no face of the arrangement is monochromatic. This improves a bound of Bose et al. \cite{BCC12} by a $Θ(\sqrt{\log n})$ factor. Any further improvement on this bound will improve the best known lower bound on the following problem of Erdős: Estimate the maximum number of points in general position within a set of $n$ points containing no four collinear points.
Real Time Discovery of Dense Clusters in Highly Dynamic Graphs: Identifying Real World Events in Highly Dynamic Environments
Venue: arXiv cs.DB 2012
Year: 2012

Due to their real time nature, microblog streams are a rich source of dynamic information, for example, about emerging events. Existing techniques for discovering such events from a microblog stream in real time (such as Twitter trending topics), have several lacunae when used for discovering emerging events; extant graph based event detection techniques are not practical in microblog settings due to their complexity; and conventional techniques, which have been developed for blogs, web-pages, etc., involving the use of keyword search, are only useful for finding information about known events. Hence, in this paper, we present techniques to discover events that are unraveling in microblog message streams in real time so that such events can be reported as soon as they occur. We model the problem as discovering dense clusters in highly dynamic graphs. Despite many recent advances in graph analysis, ours is the first technique to identify dense clusters in massive and highly dynamic graphs in real time. Given the characteristics of microblog streams, in order to find clusters without missing any events, we propose and exploit a novel graph property which we call short-cycle property. Our algorithms find these clusters efficiently in spite of rapid changes to the microblog streams. Further we present a novel ranking function to identify the important events. Besides proving the correctness of our algorithms we show their practical utility by evaluating them using real world microblog data. These demonstrate our technique's ability to discover, with high precision and recall, emerging events in high intensity data streams in real time. Many recent web applications create data which can be represented as massive dynamic graphs. Our technique can be easily extended to discover, in real time, interesting patterns in such graphs.
LogBase: A Scalable Log-structured Database System in the Cloud
Venue: arXiv cs.DB 2012
Year: 2012

Numerous applications such as financial transactions (e.g., stock trading) are write-heavy in nature. The shift from reads to writes in web applications has also been accelerating in recent years. Write-ahead-logging is a common approach for providing recovery capability while improving performance in most storage systems. However, the separation of log and application data incurs write overheads observed in write-heavy environments and hence adversely affects the write throughput and recovery time in the system. In this paper, we introduce LogBase - a scalable log-structured database system that adopts log-only storage for removing the write bottleneck and supporting fast system recovery. LogBase is designed to be dynamically deployed on commodity clusters to take advantage of elastic scaling property of cloud environments. LogBase provides in-memory multiversion indexes for supporting efficient access to data maintained in the log. LogBase also supports transactions that bundle read and write operations spanning across multiple records. We implemented the proposed system and compared it with HBase and a disk-based log-structured record-oriented system modeled after RAMCloud. The experimental results show that LogBase is able to provide sustained write throughput, efficient data access out of the cache, and effective system recovery.
Design and Implementation of Distributed Resource Management Mechanisms for Wireless Mesh Networks
Venue: arXiv cs.NI 2012
Year: 2012

In this paper we design and implement a resource management scheme based on cooperative association, where the STAs can share useful information in order to improve the performance of the association/handoff procedures. The cooperative association mechanism is inspired by the rapidly designed cooperative protocols in the field of wireless networks. Furthermore, we introduce a load balancing mechanism that operates in a cross-layer manner taking into account uplink and downlink channel conditions, routing performance and congestion control. The iterative heuristic algorithms that we propose, control the communication load of each mesh AP in a distributed manner. We evaluate the performance of our mechanisms through OPNET simulations and testbed experiments.
An Analysis of the CAVES Attestation Protocol using CPSA
Venue: arXiv cs.CR 2012
Year: 2012

This paper describes the CAVES attestation protocol and presents a tool-supported analysis showing that the runs of the protocol achieve stated goals. The goals are stated formally by annotating the protocol with logical formulas using the rely-guarantee method. The protocol analysis tool used is the Cryptographic Protocol Shape Analyzer.
On graph parameters guaranteeing fast Sandpile diffusion
Venue: arXiv cs.DM 2012
Year: 2012

The Abelian Sandpile Model is a discrete diffusion process defined on graphs (Dhar \cite{DD90}, Dhar et al. \cite{DD95}) which serves as the standard model of self-organized criticality. The transience class of a sandpile is defined as the maximum number of particles that can be added without making the system recurrent (\cite{BT05}). We demonstrate a class of sandpile which have polynomially bound transience classes by identifying key graph properties that play a role in the rapid diffusion process. These are the volume growth parameters, boundary regularity type properties and non-empty interior type constraints. This generalizes a previous result by Babai and Gorodezky (SODA 2007,\cite{LB07}), in which they establish polynomial bounds on $n \times n$ grid. Indeed the properties we show are based on ideas extracted from their proof as well as the continuous analogs in complex analysis. We conclude with a discussion on the notion of degeneracy and dimensions in graphs.
An Overview of the AAVSO's Information Technology Infrastructure From 1967 to 1997
Venue: arXiv cs.CY 2012
Year: 2012

Computer technology and data processing swept both society and the sciences like a wave in the latter half of the 20th century. We trace the AAVSO's usage of computational and data processing technology from its beginnings in 1967, through 1997. We focus on equipment, people, and the purpose such computational power was put to, and compare and contrast the organization's use of hardware and software with that of the wider industry.
Rate-splitting in the presence of multiple receivers
Venue: arXiv cs.IT 2012
Year: 2012

In the presence of multiple senders, one of the simplest decoding strategies that can be employed by a receiver is successive decoding. In a successive decoding strategy, the receiver decodes the messages one at a time using the knowledge of the previously decoded messages as side information. Recently, there have been two separate attempts to construct codes for the interference channel using successive decoding based on the idea of rate-splitting. In this note, we highlight a difficulty that arises when a rate-splitting codebook is to be decoded by multiple receivers. The main issue is that the rates of the split codebook are tightly coupled to the properties of the channel to the receiver, thus, rates chosen for one of the receivers may not be decodable for the other. We illustrate this issue by scrutinizing two recent arguments claiming to achieve the Han-Kobayashi rate region for the interference channel using rate-splitting and successive decoding.
Challenges of Upgrading a Virtual Appliance
Venue: arXiv cs.SE 2012
Year: 2012

A virtual appliance contains a target application, and the running environment necessary for running that application. Users run an appliance using a virtualization engine, freeing them from the need to make sure that the target application has access to all its dependencies. However, creating and managing a virtual appliance, versus a stand-alone application, requires special considerations. Upgrading a software system is a common requirement, and is more complicated when dealing with an appliance. This is because both the target application and the running environment must be upgraded, and there are often dependencies between these two components. In this paper we briefly discuss some important points to consider when upgrading an appliance. We then present a list of items that can help developers prevent problems during an upgrade effort.
Distributed Dynamic Inter-Cell Interference Management for Femtocell Networks Using Over-the-Air Single-Tone Signaling
Venue: arXiv cs.IT 2012
Year: 2012

Femtocell networks are promising for not only improving the coverage but also increasing the capacity of current cellular networks. The interference-limited reality in femtocell networks makes interference management (IM) the key to maintaining the quality of service and fairness in femtocell networks. Over-the-air signaling is one of the most effective means for fast distributed dynamic IM. However, the design of this type of signal is challenging. In this paper, we address the challenges and propose an effective solution, referred to as single-tone signaling (STS). The proposed STS scheme possesses many highly desirable properties, such as no dedicated resource requirement (no system overhead), no near-far effect, no inter-signal interference, and immunity to synchronization error. In addition, the proposed STS signal provides a means for high quality wideband channel estimation for the use of coordinated techniques, such as coordinated beamforming. Based on the proposed STS, two distributed dynamic IM schemes, ON/OFF power control and SLNR (signal-to-leakage-plus-noise-ratio)-based transmitter beam coordination, are proposed. Simulation results show significant performance improvement as a result of the use of STS-based IM schemes.
The Common Difference Between MIMO With Other Antennas
Venue: arXiv cs.NI 2012
Year: 2012

In past 802.11 systems there is a single Radio Frequency (RF) chain on the Wi-Fi device. Multiple antennas use the same hardware to process the radio signal. So only one antenna can transmit or receive at a time as all radio signals need to go through the single RF chain. In MIMO there can be a separate RF chain for each antenna allowing multiple RF chains to coexist. MIMO technology has attracted attention in wireless communications, because it offers significant increases in data throughput and link range without additional bandwidth or increased transmit power. It achieves this goal by spreading the same total transmit power over the antennas to achieve an array gain that improves the spectral efficiency (more bits per second per hertz of bandwidth) or to achieve a diversity gain that improves the link reliability. Multiple Input/Multiple Output (MIMO) is an area of intense development in the wireless industry because it delivers profound gains in range, throughput and reliability. As a result, manufacturers of wireless local area network (WLAN), wireless metropolitan area network (WMAN), and mobile phone equipment are embracing MIMO technology. In this paper we are interested to compare the MIMO Antenna functions with traditional Antenna functions. And we take an example of IRT for illustration.
On Rainbow Cycles and Paths
Venue: arXiv cs.DM 2012
Year: 2012

In a properly edge colored graph, a subgraph using every color at most once is called rainbow. In this thesis, we study rainbow cycles and paths in proper edge colorings of complete graphs, and we prove that in every proper edge coloring of K_n, there is a rainbow path on (3/4-o(1))n vertices, improving on the previously best bound of (2n+1)/3 from Gyarfas and Mhalla. Similarly, a k-rainbow path in a proper edge coloring of K_n is a path using no color more than k times. We prove that in every proper edge coloring of K_n, there is a k-rainbow path on (1-2/(k+1)!)n vertices.
Quantitative Information Flow as Safety and Liveness Hyperproperties
Venue: arXiv cs.CR 2012
Year: 2012

We employ Clarkson and Schneider's "hyperproperties" to classify various verification problems of quantitative information flow. The results of this paper unify and extend the previous results on the hardness of checking and inferring quantitative information flow. In particular, we identify a subclass of liveness hyperproperties, which we call "k-observable hyperproperties", that can be checked relative to a reachability oracle via self composition.
Performance Issues of Heterogeneous Hadoop Clusters in Cloud Computing
Venue: arXiv cs.DC 2012
Year: 2012

Nowadays most of the cloud applications process large amount of data to provide the desired results. Data volumes to be processed by cloud applications are growing much faster than computing power. This growth demands new strategies for processing and analyzing information. Dealing with large data volumes requires two things: 1) Inexpensive, reliable storage 2) New tools for analyzing unstructured and structured data. Hadoop is a powerful open source software platform that addresses both of these problems. The current Hadoop implementation assumes that computing nodes in a cluster are homogeneous in nature. Hadoop lacks performance in heterogeneous clusters where the nodes have different computing capacity. In this paper we address the issues that affect the performance of hadoop in heterogeneous clusters and also provided some guidelines on how to overcome these bottlenecks
Symbol Error Rate of Space-Time Network Coding in Nakagami-m Fading
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we analyze the symbol error rate (SER) of space-time network coding (STNC) in a distributed cooperative network over independent but not necessarily identically distributed (i.n.i.d.) Nakagami-$m$ fading channels. In this network, multiple sources communicate with a single destination with the assistance of multiple decode-and-forward (DF) relays. We first derive new exact closed-form expressions for the SER with $M$-ary phase shift-keying modulation ($M$-PSK) and $M$-ary quadrature amplitude modulation ($M$-QAM). We then derive new compact expressions for the asymptotic SER to offer valuable insights into the network behavior in the high signal-to-noise ratio (SNR) regime. Importantly, we demonstrate that STNC guarantees full diversity order, which is determined by the Nakagami-$m$ fading parameters of all the channels but independent of the number of sources. Based on the new expressions, we examine the impact of the number of relays, relay location, Nakagami-$m$ fading parameters, power allocation, and nonorthogonal codes on the SER.