OpenRaiser/Intern-Atlas huggingface dataset:
On Separation Criterion and Recovery Algorithm for Chain Graphs
Venue: arXiv cs.AI 2013
Year: 2013

Chain graphs give a natural unifying point of view on Markov and Bayesian networks and enlarge the potential of graphical models for description of conditional independence structures. In the paper a direct graphical separation criterion for chain graphs, called c-separation, which generalizes the d-separation criterion for Bayesian networks is introduced (recalled). It is equivalent to the classic moralization criterion for chain graphs and complete in sense that for every chain graph there exists a probability distribution satisfying exactly conditional independencies derivable from the chain graph by the c-separation criterion. Every class of Markov equivalent chain graphs can be uniquely described by a natural representative, called the largest chain graph. A recovery algorithm, which on basis of the (conditional) dependency model induced by an unknown chain graph finds the corresponding largest chain graph, is presented.
Possible World Partition Sequences: A Unifying Framework for Uncertain Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

When we work with information from multiple sources, the formalism each employs to handle uncertainty may not be uniform. In order to be able to combine these knowledge bases of different formats, we need to first establish a common basis for characterizing and evaluating the different formalisms, and provide a semantics for the combined mechanism. A common framework can provide an infrastructure for building an integrated system, and is essential if we are to understand its behavior. We present a unifying framework based on an ordered partition of possible worlds called partition sequences, which corresponds to our intuitive notion of biasing towards certain possible scenarios when we are uncertain of the actual situation. We show that some of the existing formalisms, namely, default logic, autoepistemic logic, probabilistic conditioning and thresholding (generalized conditioning), and possibility theory can be incorporated into this general framework.
Critical Remarks on Single Link Search in Learning Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

In learning belief networks, the single link lookahead search is widely adopted to reduce the search space. We show that there exists a class of probabilistic domain models which displays a special pattern of dependency. We analyze the behavior of several learning algorithms using different scoring metrics such as the entropy, conditional independence, minimal description length and Bayesian metrics. We demonstrate that single link lookahead search procedures (employed in these algorithms) cannot learn these models correctly. Thus, when the underlying domain model actually belongs to this class, the use of a single link search procedure will result in learning of an incorrect model. This may lead to inference errors when the model is used. Our analysis suggests that if the prior knowledge about a domain does not rule out the possible existence of these models, a multi-link lookahead search or other heuristics should be used for the learning process.
On Zero Delay Source-Channel Coding
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we study the zero-delay source-channel coding problem, and specifically the problem of obtaining the vector transformations that optimally map between the m-dimensional source space and the k-dimensional channel space, under a given transmission power constraint and for the mean square error distortion. We first study the functional properties of this problem and show that the objective is concave in the source and noise densities and convex in the density of the input to the channel. We then derive the necessary conditions for optimality of the encoder and decoder mappings. A well known result in information theory pertains to the linearity of optimal encoding and decoding mappings in the scalar Gaussian source and channel setting, at all channel signal-to-noise ratios (CSNRs). In this paper, we study this result more generally, beyond the Gaussian source and channel, and derive the necessary and sufficient condition for linearity of optimal mappings, given a noise (or source) distribution, and a specified power constraint. We also prove that the Gaussian source-channel pair is unique in the sense that it is the only source-channel pair for which the optimal mappings are linear at more than one CSNR values. Moreover, we show the asymptotic linearity of optimal mappings for low CSNR if the channel is Gaussian regardless of the source and, at the other extreme, for high CSNR if the source is Gaussian, regardless of the channel. Our numerical results show strict improvement over prior methods. The numerical approach is extended to the scenario of source-channel coding with decoder side information. The resulting encoding mappings are shown to be continuous relatives of, and in fact subsume as special case, the Wyner-Ziv mappings encountered in digital distributed source coding systems.
Bio-inspired data mining: Treating malware signatures as biosequences
Venue: arXiv cs.LG 2013
Year: 2013

The application of machine learning to bioinformatics problems is well established. Less well understood is the application of bioinformatics techniques to machine learning and, in particular, the representation of non-biological data as biosequences. The aim of this paper is to explore the effects of giving amino acid representation to problematic machine learning data and to evaluate the benefits of supplementing traditional machine learning with bioinformatics tools and techniques. The signatures of 60 computer viruses and 60 computer worms were converted into amino acid representations and first multiply aligned separately to identify conserved regions across different families within each class (virus and worm). This was followed by a second alignment of all 120 aligned signatures together so that non-conserved regions were identified prior to input to a number of machine learning techniques. Differences in length between virus and worm signatures after the first alignment were resolved by the second alignment. Our first set of experiments indicates that representing computer malware signatures as amino acid sequences followed by alignment leads to greater classification and prediction accuracy. Our second set of experiments indicates that checking the results of data mining from artificial virus and worm data against known proteins can lead to generalizations being made from the domain of naturally occurring proteins to malware signatures. However, further work is needed to determine the advantages and disadvantages of different representations and sequence alignment methods for handling problematic machine learning data.
On Weak Dress Codes for Cloud Storage
Venue: arXiv cs.IT 2013
Year: 2013

In a distributed storage network, reliability and bandwidth optimization can be provided by regenerating codes. Recently table based regenerating codes viz. DRESS (Distributed Replication-based Exact Simple Storage) codes has been proposed which also optimizes the disk I/O. Dress codes consists of an outer MDS code with an inner fractional repetition (FR) code with replication degree $ρ$. Several constructions of FR codes based on regular graphs, resolvable designs and bipartite graphs are known. This paper presents a simple modular construction of FR codes. We also generalize the concept of FR codes to weak fractional repetition (WFR) codes where each node has different number of packets. We present a construction of WFR codes based on partial regular graph. Finally we present a simple generalized ring construction of both strong and weak fractional repetition codes.
Computing preimages of Boolean Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we present an algorithm to address the predecessor problem of feed-forward Boolean networks. We propose an probabilistic algorithm, which solves this problem in linear time with respect to the number of nodes in the network. Finally, we evaluate our algorithm for random Boolean networks and the regulatory network of Escherichia coli.
Improved upper and lower bound techniques for monotone switching networks for directed connectivity
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we analyze the monotone space of complexity of directed connectivity for a large class of input graphs $G$ using the switching network model. The upper and lower bounds we obtain are a significant generalization of previous results and the proofs involve several completely new techniques and ideas.
On the Communication Complexity of Approximate Nash Equilibria
Venue: arXiv cs.GT 2013
Year: 2013

We study the problem of computing approximate Nash equilibria of bimatrix games, in a setting where players initially know their own payoffs but not the payoffs of the other player. In order for a solution of reasonable quality to be found, some amount of communication needs to take place between the players. We are interested in algorithms where the communication is substantially less than the contents of a payoff matrix, for example logarithmic in the size of the matrix. When the communication is polylogarithmic in the number of strategies n, we show how to obtain epsilon-approximate Nash equilibria for epsilon approximately 0.438, and for well-supported approximate equilibria we obtain epsilon approximately 0.732. For one-way communication we show that epsilon=1/2 is achievable, but no constant improvement over 1/2 is possible, even with unlimited one-way communication. For well-supported equilibria, no value of epsilon less than 1 is achievable with one-way communication. When the players do not communicate at all, epsilon-Nash equilibria can be obtained for epsilon=3/4, and we also give a lower bound of slightly more than 1/2 on the lowest constant epsilon achievable.
Non-Bayesian Quickest Detection with Stochastic Sample Right Constraints
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we study the design and analysis of optimal detection scheme for sensors that are deployed to monitor the change in the environment and are powered by the energy harvested from the environment. In this type of applications, detection delay is of paramount importance. We model this problem as quickest change detection problem with a stochastic energy constraint. In particular, a wireless sensor powered by renewable energy takes observations from a random sequence, whose distribution will change at a certain unknown time. Such a change implies events of interest. The energy in the sensor is consumed by taking observations and is replenished randomly. The sensor cannot take observations if there is no energy left in the battery. Our goal is to design a power allocation scheme and a detection strategy to minimize the worst case detection delay, which is the difference between the time when an alarm is raised and the time when the change occurs. Two types of average run length (ARL) constraint, namely an algorithm level ARL constraint and an system level ARL constraint, are considered. We propose a low complexity scheme in which the energy allocation rule is to spend energy to take observations as long as the battery is not empty and the detection scheme is the Cumulative Sum test. We show that this scheme is optimal for the formulation with the algorithm level ARL constraint and is asymptotically optimal for the formulations with the system level ARL constraint.
A framework for automated PDE-constrained optimisation
Venue: arXiv cs.MS 2013
Year: 2013

A generic framework for the solution of PDE-constrained optimisation problems based on the FEniCS system is presented. Its main features are an intuitive mathematical interface, a high degree of automation, and an efficient implementation of the generated adjoint model. The framework is based upon the extension of a domain-specific language for variational problems to cleanly express complex optimisation problems in a compact, high-level syntax. For example, optimisation problems constrained by the time-dependent Navier-Stokes equations can be written in tens of lines of code. Based on this high-level representation, the framework derives the associated adjoint equations in the same domain-specific language, and uses the FEniCS code generation technology to emit parallel optimised low-level C++ code for the solution of the forward and adjoint systems. The functional and gradient information so computed is then passed to the optimisation algorithm to update the parameter values. This approach works both for steady-state as well as transient, and for linear as well as nonlinear governing PDEs and a wide range of functionals and control parameters. We demonstrate the applicability and efficiency of this approach on classical textbook optimisation problems and advanced examples.
k-d Darts: Sampling by k-Dimensional Flat Searches
Venue: arXiv cs.GR 2013
Year: 2013

We formalize the notion of sampling a function using k-d darts. A k-d dart is a set of independent, mutually orthogonal, k-dimensional subspaces called k-d flats. Each dart has d choose k flats, aligned with the coordinate axes for efficiency. We show that k-d darts are useful for exploring a function's properties, such as estimating its integral, or finding an exemplar above a threshold. We describe a recipe for converting an algorithm from point sampling to k-d dart sampling, assuming the function can be evaluated along a k-d flat. We demonstrate that k-d darts are more efficient than point-wise samples in high dimensions, depending on the characteristics of the sampling domain: e.g. the subregion of interest has small volume and evaluating the function along a flat is not too expensive. We present three concrete applications using line darts (1-d darts): relaxed maximal Poisson-disk sampling, high-quality rasterization of depth-of-field blur, and estimation of the probability of failure from a response surface for uncertainty quantification. In these applications, line darts achieve the same fidelity output as point darts in less time. We also demonstrate the accuracy of higher dimensional darts for a volume estimation problem. For Poisson-disk sampling, we use significantly less memory, enabling the generation of larger point clouds in higher dimensions.
Using Correlated Subset Structure for Compressive Sensing Recovery
Venue: arXiv cs.IT 2013
Year: 2013

Compressive sensing is a methodology for the reconstruction of sparse or compressible signals using far fewer samples than required by the Nyquist criterion. However, many of the results in compressive sensing concern random sampling matrices such as Gaussian and Bernoulli matrices. In common physically feasible signal acquisition and reconstruction scenarios such as super-resolution of images, the sensing matrix has a non-random structure with highly correlated columns. Here we present a compressive sensing recovery algorithm that exploits this correlation structure. We provide algorithmic justification as well as empirical comparisons.
Real-Time Power Balancing via Decentralized Coordinated Home Energy Scheduling
Venue: arXiv cs.SY 2013
Year: 2013

It is anticipated that an uncoordinated operation of individual home energy management (HEM) systems in a neighborhood would have a rebound effect on the aggregate demand profile. To address this issue, this paper proposes a coordinated home energy management (CoHEM) architecture in which distributed HEM units collaborate with each other in order to keep the demand and supply balanced in their neighborhood. Assuming the energy requests by customers are random in time, we formulate the proposed CoHEM design as a multi-stage stochastic optimization problem. We propose novel models to describe the deferrable appliance load (e.g., Plug-in (Hybrid) Electric Vehicles (PHEV)), and apply approximation and decomposition techniques to handle the considered design problem in a decentralized fashion. The developed decentralized CoHEM algorithm allow the customers to locally compute their scheduling solutions using domestic user information and with message exchange between their neighbors only. Extensive simulation results demonstrate that the proposed CoHEM architecture can effectively improve real-time power balancing. Extensions to joint power procurement and real-time CoHEM scheduling are also presented.
Clustering validity based on the most similarity
Venue: arXiv cs.LG 2013
Year: 2013

One basic requirement of many studies is the necessity of classifying data. Clustering is a proposed method for summarizing networks. Clustering methods can be divided into two categories named model-based approaches and algorithmic approaches. Since the most of clustering methods depend on their input parameters, it is important to evaluate the result of a clustering algorithm with its different input parameters, to choose the most appropriate one. There are several clustering validity techniques based on inner density and outer density of clusters that represent different metrics to choose the most appropriate clustering independent of the input parameters. According to dependency of previous methods on the input parameters, one challenge in facing with large systems, is to complete data incrementally that effects on the final choice of the most appropriate clustering. Those methods define the existence of high intensity in a cluster, and low intensity among different clusters as the measure of choosing the optimal clustering. This measure has a tremendous problem, not availing all data at the first stage. In this paper, we introduce an efficient measure in which maximum number of repetitions for various initial values occurs.
Distributed boundary tracking using alpha and Delaunay-Cech shapes
Venue: arXiv cs.CG 2013
Year: 2013

For a given point set $S$ in a plane, we develop a distributed algorithm to compute the $α-$shape of $S$. $α-$shapes are well known geometric objects which generalize the idea of a convex hull, and provide a good definition for the shape of $S$. We assume that the distances between pairs of points which are closer than a certain distance $r>0$ are provided, and we show constructively that this information is sufficient to compute the alpha shapes for a range of parameters, where the range depends on $r$. Such distributed algorithms are very useful in domains such as sensor networks, where each point represents a sensing node, the location of which is not necessarily known. We also introduce a new geometric object called the Delaunay-Čech shape, which is geometrically more appropriate than an $α-$shape for some cases, and show that it is topologically equivalent to $α-$shapes.
A solution concept for games with altruism and cooperation
Venue: arXiv cs.GT 2013
Year: 2013

Over the years, numerous experiments have been accumulated to show that cooperation is not casual and depends on the payoffs of the game. These findings suggest that humans have attitude to cooperation by nature and the same person may act more or less cooperatively depending on the particular payoffs. In other words, people do not act a priori as single agents, but they forecast how the game would be played if they formed coalitions and then they play according to their best forecast. In this paper we formalize this idea and we define a new solution concept for one-shot normal form games. We prove that this \emph{cooperative equilibrium} exists for all finite games and it explains a number of different experimental findings, such as (1) the rate of cooperation in the Prisoner's dilemma depends on the cost-benefit ratio; (2) the rate of cooperation in the Traveler's dilemma depends on the bonus/penalty; (3) the rate of cooperation in the Publig Goods game depends on the pro-capite marginal return and on the numbers of players; (4) the rate of cooperation in the Bertrand competition depends on the number of players; (5) players tend to be fair in the bargaining problem; (6) players tend to be fair in the Ultimatum game; (7) players tend to be altruist in the Dictator game; (8) offers in the Ultimatum game are larger than offers in the Dictator game.
Full-fledged Real-Time Indexing for Constant Size Alphabets
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet ofconstant size. Each new symbol can be prepended to $T$ in O(1) worst-case time. At any moment, we can report all occurrences of a pattern $P$ in the current text in $O(|P|+k)$ time, where $|P|$ is the length of $P$ and $k$ is the number of occurrences. This resolves, under assumption of constant-size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see \cite{AmirN08}).
Distributed Deterministic Broadcasting in Uniform-Power Ad Hoc Wireless Networks
Venue: arXiv cs.DC 2013
Year: 2013

Development of many futuristic technologies, such as MANET, VANET, iThings, nano-devices, depend on efficient distributed communication protocols in multi-hop ad hoc networks. A vast majority of research in this area focus on design heuristic protocols, and analyze their performance by simulations on networks generated randomly or obtained in practical measurements of some (usually small-size) wireless networks. %some library. Moreover, they often assume access to truly random sources, which is often not reasonable in case of wireless devices. In this work we use a formal framework to study the problem of broadcasting and its time complexity in any two dimensional Euclidean wireless network with uniform transmission powers. For the analysis, we consider two popular models of ad hoc networks based on the Signal-to-Interference-and-Noise Ratio (SINR): one with opportunistic links, and the other with randomly disturbed SINR. In the former model, we show that one of our algorithms accomplishes broadcasting in $O(D\log^2 n)$ rounds, where $n$ is the number of nodes and $D$ is the diameter of the network. If nodes know a priori the granularity $g$ of the network, i.e., the inverse of the maximum transmission range over the minimum distance between any two stations, a modification of this algorithm accomplishes broadcasting in $O(D\log g)$ rounds. Finally, we modify both algorithms to make them efficient in the latter model with randomly disturbed SINR, with only logarithmic growth of performance. Ours are the first provably efficient and well-scalable, under the two models, distributed deterministic solutions for the broadcast task.
Comprehensive Resource Measurement and Analysis for HPC Systems with TACC_Stats
Venue: arXiv cs.DC 2013
Year: 2013

High-performance computing (HPC) systems are a complex combination of software, processors, memory, networks, and storage systems characterized by frequent disruptive technological advances. Anomalous behavior has to be manually diagnosed and remedied with incomplete and sparse data. It also has been effort-intensive for users to assess the effectiveness with which they are using the available resources. The data available for system level analyses appear from multiple sources and in disparate formats (from Linux "sysstat" and accounting to scheduler/kernel logs). Sysstat does not resolve its measurements by job so that job-oriented analyses require individual measurements. There are many user-oriented performance instrumentation and profiling tools but they require extensive system knowledge, code changes and recompilation, and thus are not widely used. To address this issue, we develop TACC_Stats, a job-oriented and logically structured version of the conventional Linux "sysstat/sar" system-wide performance monitor. We use TACC_Stats-collected data from a supercomputer "Ranger" to demonstrate its effectiveness in two case studies.