OpenRaiser/Intern-Atlas huggingface dataset:
Network Engineering for Complex Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

Like any large system development effort, the construction of a complex belief network model requires systems engineering to manage the design and construction process. We propose a rapid prototyping approach to network engineering. We describe criteria for identifying network modules and the use of "stubs" to represent not-yet-constructed modules. We propose an object oriented representation for belief networks which captures the semantics of the problem in addition to conditional independencies and probabilities. Methods for evaluating complex belief network models are discussed. The ideas are illustrated with examples from a large belief network construction problem in the military intelligence domain.
Probabilistic Disjunctive Logic Programming
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we propose a framework for combining Disjunctive Logic Programming and Poole's Probabilistic Horn Abduction. We use the concept of hypothesis to specify the probability structure. We consider the case in which probabilistic information is not available. Instead of using probability intervals, we allow for the specification of the probabilities of disjunctions. Because minimal models are used as characteristic models in disjunctive logic programming, we apply the principle of indifference on the set of minimal models to derive default probability values. We define the concepts of explanation and partial explanation of a formula, and use them to determine the default probability distribution(s) induced by a program. An algorithm for calculating the default probability of a goal is presented.
Identifying Independencies in Causal Graphs with Feedback
Venue: arXiv cs.AI 2013
Year: 2013

We show that the d -separation criterion constitutes a valid test for conditional independence relationships that are induced by feedback systems involving discrete variables.
Optimal Monte Carlo Estimation of Belief Network Inference
Venue: arXiv cs.AI 2013
Year: 2013

We present two Monte Carlo sampling algorithms for probabilistic inference that guarantee polynomial-time convergence for a larger class of network than current sampling algorithms provide. These new methods are variants of the known likelihood weighting algorithm. We use of recent advances in the theory of optimal stopping rules for Monte Carlo simulation to obtain an inference approximation with relative error epsilon and a small failure probability delta. We present an empirical evaluation of the algorithms which demonstrates their improved performance.
A Discovery Algorithm for Directed Cyclic Graphs
Venue: arXiv cs.AI 2013
Year: 2013

Directed acyclic graphs have been used fruitfully to represent causal strucures (Pearl 1988). However, in the social sciences and elsewhere models are often used which correspond both causally and statistically to directed graphs with directed cycles (Spirtes 1995). Pearl (1993) discussed predicting the effects of intervention in models of this kind, so-called linear non-recursive structural equation models. This raises the question of whether it is possible to make inferences about causal structure with cycles, form sample data. In particular do there exist general, informative, feasible and reliable precedures for inferring causal structure from conditional independence relations among variables in a sample generated by an unknown causal structure? In this paper I present a discovery algorithm that is correct in the large sample limit, given commonly (but often implicitly) made plausible assumptions, and which provides information about the existence or non-existence of causal pathways from one variable to another. The algorithm is polynomial on sparse graphs.
Global Optimal Solutions to General Sensor Network Localization Problem
Venue: arXiv cs.CC 2013
Year: 2013

Sensor network localization problem is to determine the position of the sensor nodes in a network given pairwise distance measurements. Such problem can be formulated as a polynomial minimization via the least squares method. This paper presents a canonical duality theory for solving this challenging problem. It is shown that the nonconvex minimization problem can be reformulated as a concave maximization dual problem over a convex set in a symmetrical matrix space, and hence can be solved efficiently by combining a general (linear or quadratic) perturbation technique with existing optimization techniques. Applications are illustrated by solving some relatively large-scale problems. Our results show that the general sensor network localization problem is not NP-hard unless its canonical dual problem has no solution.
Thompson Sampling in Switching Environments with Bayesian Online Change Point Detection
Venue: arXiv cs.LG 2013
Year: 2013

Thompson Sampling has recently been shown to be optimal in the Bernoulli Multi-Armed Bandit setting[Kaufmann et al., 2012]. This bandit problem assumes stationary distributions for the rewards. It is often unrealistic to model the real world as a stationary distribution. In this paper we derive and evaluate algorithms using Thompson Sampling for a Switching Multi-Armed Bandit Problem. We propose a Thompson Sampling strategy equipped with a Bayesian change point mechanism to tackle this problem. We develop algorithms for a variety of cases with constant switching rate: when switching occurs all arms change (Global Switching), switching occurs independently for each arm (Per-Arm Switching), when the switching rate is known and when it must be inferred from data. This leads to a family of algorithms we collectively term Change-Point Thompson Sampling (CTS). We show empirical results of the algorithm in 4 artificial environments, and 2 derived from real world data; news click-through[Yahoo!, 2011] and foreign exchange data[Dukascopy, 2012], comparing them to some other bandit algorithms. In real world data CTS is the most effective.
Upper bounds for Newton's method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata
Venue: arXiv cs.LO 2013
Year: 2013

A central computational problem for analyzing and model checking various classes of infinite-state recursive probabilistic systems (including quasi-birth-death processes, multi-type branching processes, stochastic context-free grammars, probabilistic pushdown automata and recursive Markov chains) is the computation of {\em termination probabilities}, and computing these probabilities in turn boils down to computing the {\em least fixed point} (LFP) solution of a corresponding {\em monotone polynomial system} (MPS) of equations, denoted x=P(x). It was shown by Etessami & Yannakakis that a decomposed variant of Newton's method converges monotonically to the LFP solution for any MPS that has a non-negative solution. Subsequently, Esparza, Kiefer, & Luttenberger obtained upper bounds on the convergence rate of Newton's method for certain classes of MPSs. More recently, better upper bounds have been obtained for special classes of MPSs. However, prior to this paper, for arbitrary (not necessarily strongly-connected) MPSs, no upper bounds at all were known on the convergence rate of Newton's method as a function of the encoding size |P| of the input MPS, x=P(x). In this paper we provide worst-case upper bounds, as a function of both the input encoding size |P|, and epsilon > 0, on the number of iterations required for decomposed Newton's method (even with rounding) to converge within additive error epsilon > 0 of q^*, for any MPS with LFP solution q^*. Our upper bounds are essentially optimal in terms of several important parameters. Using our upper bounds, and building on prior work, we obtain the first P-time algorithm (in the standard Turing model of computation) for quantitative model checking, to within desired precision, of discrete-time QBDs and (equivalently) probabilistic 1-counter automata, with respect to any (fixed) omega-regular or LTL property.
Effective System for Pregnant Women using Mobile GIS
Venue: arXiv cs.CY 2013
Year: 2013

World Health Organization showed at one year about 287 000 women died most of them during and following pregnancy and childbirth in Africa and south Asia. This paper suggests mHealth system for serving pregnant women, that proposed system is first an effective mHealth system works base on mobile GIS to select adjacent care centre or hospital maternity on Google map at online registration for woman pregnant, that is done when the pregnant woman will send SMS via GPRS network contains her ID and coordinates (Longitude and Latitude) the server when receive it will search database support that system and using the same infrastructure for help the pregnant women at her location (home, market, etc) in emergency cases when the woman send SMS contains her coordinates for succoring. Implement the proposed pregnant women system shows more effective from view of cost than other systems because it works in economic (SMS) mode and from view of serve the system can easy and rapidly manage when achieving locally registration, succoring in emergency cases, change the review date of pregnant woman, as well as different types of advising. Keywords Pregnant Women, mHealth System, General Packet Radio Service (GPRS); Mobile GIS; Short Message Service (SMS), Global Position System (GPS).
An Enhanced Spectral Efficiency Chaos-Based Symbolic Dynamics Transceiver Design
Venue: arXiv cs.IT 2013
Year: 2013

Chaotic synchronization performs poorly in noisy environments, with the main drawback being that the coherent receiver cannot be implemented in realistic communication channels. In this paper, we focus our study on a promising communication system based on chaotic symbolic dynamics. Such modulation shows a high synchronization quality, without the need for a complex chaotic synchronization mechanism. Our study mainly concerns an improvement of the bandwidth efficiency of the chaotic modulator. A new chaotic map is proposed to achieve this goal, and a receiver based on the maximum likelihood algorithm is designed to estimate the transmitted symbols. The performance of the proposed system is analyzed and discussed.
Quantum Entanglement in Concept Combinations
Venue: arXiv cs.AI 2013
Year: 2013

Research in the application of quantum structures to cognitive science confirms that these structures quite systematically appear in the dynamics of concepts and their combinations and quantum-based models faithfully represent experimental data of situations where classical approaches are problematical. In this paper, we analyze the data we collected in an experiment on a specific conceptual combination, showing that Bell's inequalities are violated in the experiment. We present a new refined entanglement scheme to model these data within standard quantum theory rules, where 'entangled measurements and entangled evolutions' occur, in addition to the expected 'entangled states', and present a full quantum representation in complex Hilbert space of the data. This stronger form of entanglement in measurements and evolutions might have relevant applications in the foundations of quantum theory, as well as in the interpretation of nonlocality tests. It could indeed explain some non-negligible 'anomalies' identified in EPR-Bell experiments.
Power Strip Packing of Malleable Demands in Smart Grid
Venue: arXiv cs.DS 2013
Year: 2013

We consider a problem of supplying electricity to a set of $\mathcal{N}$ customers in a smart-grid framework. Each customer requires a certain amount of electrical energy which has to be supplied during the time interval $[0,1]$. We assume that each demand has to be supplied without interruption, with possible duration between $\ell$ and $r$, which are given system parameters ($\ell\le r$). At each moment of time, the power of the grid is the sum of all the consumption rates for the demands being supplied at that moment. Our goal is to find an assignment that minimizes the {\it power peak} - maximal power over $[0,1]$ - while satisfying all the demands. To do this first we find the lower bound of optimal power peak. We show that the problem depends on whether or not the pair $\ell, r$ belongs to a "good" region $\mathcal{G}$. If it does - then an optimal assignment almost perfectly "fills" the rectangle $time \times power = [0,1] \times [0, A]$ with $A$ being the sum of all the energy demands - thus achieving an optimal power peak $A$. Conversely, if $\ell, r$ do not belong to $\mathcal{G}$, we identify the lower bound $\bar{A} >A$ on the optimal value of power peak and introduce a simple linear time algorithm that almost perfectly arranges all the demands in a rectangle $[0, A /\bar{A}] \times [0, \bar{A}]$ and show that it is asymptotically optimal.
Enhanced secure key exchange systems based on the Johnson-noise scheme
Venue: arXiv cs.CR 2013
Year: 2013

We introduce seven new versions of the Kirchhoff-Law-Johnson-(like)-Noise (KLJN) classical physical secure key exchange scheme and a new transient protocol for practically-perfect security. While these practical improvements offer progressively enhanced security and/or speed for the non-ideal conditions, the fundamental physical laws providing the security remain the same. In the "intelligent" KLJN (iKLJN) scheme, Alice and Bob utilize the fact that they exactly know not only their own resistor value but also the stochastic time function of their own noise, which they generate before feeding it into the loop. In the "multiple" KLJN (MKLJN) system, Alice and Bob have publicly known identical sets of different resistors with a proper, publicly known truth table about the bit-interpretation of their combination. In the "keyed" KLJN (KKLJN) system, by using secure communication with a formerly shared key, Alice and Bob share a proper time-dependent truth table for the bit-interpretation of the resistor situation for each secure bit exchange step during generating the next key. The remaining four KLJN schemes are the combinations of the above protocols to synergically enhance the security properties. These are: the "intelligent-multiple" (iMKLJN), the "intelligent-keyed" (iKKLJN), the "keyed-multiple" (KMKLJN) and the "intelligent-keyed-multiple" (iKMKLJN) KLJN key exchange systems. Finally, we introduce a new transient-protocol offering practically-perfect security without privacy amplification, which is not needed at practical applications but it is shown for the sake of ongoing discussions.
The Sensemaking-Coevolution-Implementation Theory of Software Design
Venue: arXiv cs.SE 2013
Year: 2013

Understanding software design practice is critical to understanding modern information systems development. New developments in empirical software engineering, information systems design science and the interdisciplinary design literature combined with recent advances in process theory and testability have created a situation ripe for innovation. Consequently, this paper utilizes these breakthroughs to formulate a process theory of software design practice: Sensemaking-Coevolution-Implementation Theory explains how complex software systems are created by collocated software development teams in organizations. It posits that an independent agent (design team) creates a software system by alternating between three activities: organizing their perceptions about the context, mutually refining their understandings of the context and design space, and manifesting their understanding of the design space in a technological artifact. This theory development paper defines and illustrates Sensemaking-Coevolution-Implementation Theory, grounds its concepts and relationships in existing literature, conceptually evaluates the theory and situates it in the broader context of information systems development.
Repair-Optimal MDS Array Codes over GF(2)
Venue: arXiv cs.IT 2013
Year: 2013

Maximum-distance separable (MDS) array codes with high rate and an optimal repair property were introduced recently. These codes could be applied in distributed storage systems, where they minimize the communication and disk access required for the recovery of failed nodes. However, the encoding and decoding algorithms of the proposed codes use arithmetic over finite fields of order greater than 2, which could result in a complex implementation. In this work, we present a construction of 2-parity MDS array codes, that allow for optimal repair of a failed information node using XOR operations only. The reduction of the field order is achieved by allowing more parity bits to be updated when a single information bit is being changed by the user.
Post-buckling Solutions of Hyper-elastic Beam by Canonical Dual Finite Element Method
Venue: arXiv cs.CE 2013
Year: 2013

Post buckling problem of a large deformed beam is analyzed using canonical dual finite element method (CD-FEM). The feature of this method is to choose correctly the canonical dual stress so that the original non-convex potential energy functional is reformulated in a mixed complementary energy form with both displacement and stress fields, and a pure complementary energy is explicitly formulated in finite dimensional space. Based on the canonical duality theory and the associated triality theorem, a primal-dual algorithm is proposed, which can be used to find all possible solutions of this nonconvex post-buckling problem. Numerical results show that the global maximum of the pure-complementary energy leads to a stable buckled configuration of the beam. While the local extrema of the pure-complementary energy present unstable deformation states, especially. We discovered that the unstable buckled state is very sensitive to the number of total elements and the external loads. Theoretical results are verified through numerical examples and some interesting phenomena in post-bifurcation of this large deformed beam are observed.
The Failure Probability of Random Linear Network Coding for Networks
Venue: arXiv cs.IT 2013
Year: 2013

In practice, since many communication networks are huge in scale, or complicated in structure, or even dynamic, the predesigned linear network codes based on the network topology is impossible even if the topological structure is known. Therefore, random linear network coding has been proposed as an acceptable coding technique for the case that the network topology cannot be utilized completely. Motivated by the fact that different network topological information can be obtained for different practical applications, we study the performance analysis of random linear network coding by analyzing some failure probabilities depending on these different topological information of networks. We obtain some tight or asymptotically tight upper bounds on these failure probabilities and indicate the worst cases for these bounds, i.e., the networks meeting the upper bounds with equality. In addition, if the more topological information of the network is utilized, the better upper bounds are obtained. On the other hand, we also discuss the lower bounds on the failure probabilities.
Data Placement and Replica Selection for Improving Co-location in Distributed Environments
Venue: arXiv cs.DB 2013
Year: 2013

Increasing need for large-scale data analytics in a number of application domains has led to a dramatic rise in the number of distributed data management systems, both parallel relational databases, and systems that support alternative frameworks like MapReduce. There is thus an increasing contention on scarce data center resources like network bandwidth; further, the energy requirements for powering the computing equipment are also growing dramatically. As we show empirically, increasing the execution parallelism by spreading out data across a large number of machines may achieve the intended goal of decreasing query latencies, but in most cases, may increase the total resource and energy consumption significantly. For many analytical workloads, however, minimizing query latencies is often not critical; in such scenarios, we argue that we should instead focus on minimizing the average query span, i.e., the average number of machines that are involved in processing of a query, through colocation of data items that are frequently accessed together. In this work, we exploit the fact that most distributed environments need to use replication for fault tolerance, and we devise workload-driven replica selection and placement algorithms that attempt to minimize the average query span. We model a historical query workload trace as a hypergraph over a set of data items, and formulate and analyze the problem of replica placement by drawing connections to several well-studied graph theoretic concepts. We develop a series of algorithms to decide which data items to replicate, and where to place the replicas. We show effectiveness of our proposed approach by presenting results on a collection of synthetic and real workloads. Our experiments show that careful data placement and replication can dramatically reduce the average query spans resulting in significant reductions in the resource consumption.
Reduction in Packet Delay Through the use of Common Buffer over Distributed Buffer in the Routing Node of NOC Architecture
Venue: arXiv cs.AR 2013
Year: 2013

Performance evaluation of the routing node in terms of latency is the characteristics of an efficient design of Buffer in input module. It is intended to study and quantify the behavior of the single packet array design in relation to the multiple packet array design. The utilization efficiency of the packet buffer array improves when a common buffer is used instead of individual buffers in each input port. First Poissons Queuing model was prepared to manifest the differences in packet delays. The queuing model can be classified as (M/M/1), (32/FIFO). Arrival rate has been assumed to be Poisson distributed with a mean arrival rate of 10 x 1000000. The service rate is assumed to be exponentially distributed with a mean service rate of 10.05 x 1000000. It has been observed that latency in Common Buffer improved by 46 percent over its distributed buffer. A Simulink model later simulated on MATLAB to calculate the improvement in packet delay. It has been observed that the delay improved by approximately 40 percent through the use of a common buffer. A verilog RTL for both common and shared buffer has been prepared and later synthesized using Design Compiler of SYNOPSYS. In distributed buffer, arrival of data packet could be delayed by 2 or 4 clock cycles which lead to latency improvement either by 17 percent or 34 percent in a common buffer
A Robust AFPTAS for Online Bin Packing with Polynomial Migration
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we develop general LP and ILP techniques to find an approximate solution with improved objective value close to an existing solution. The task of improving an approximate solution is closely related to a classical theorem of Cook et al. in the sensitivity analysis for LPs and ILPs. This result is often applied in designing robust algorithms for online problems. We apply our new techniques to the online bin packing problem, where it is allowed to reassign a certain number of items, measured by the migration factor. The migration factor is defined by the total size of reassigned items divided by the size of the arriving item. We obtain a robust asymptotic fully polynomial time approximation scheme (AFPTAS) for the online bin packing problem with migration factor bounded by a polynomial in $\frac{1}ε$. This answers an open question stated by Epstein and Levin in the affirmative. As a byproduct we prove an approximate variant of the sensitivity theorem by Cook at el. for linear programs.