OpenRaiser/Intern-Atlas huggingface dataset:
On the Equivalence of Causal Models
Venue: arXiv cs.AI 2013
Year: 2013

Scientists often use directed acyclic graphs (days) to model the qualitative structure of causal theories, allowing the parameters to be estimated from observational data. Two causal models are equivalent if there is no experiment which could distinguish one from the other. A canonical representation for causal models is presented which yields an efficient graphical criterion for deciding equivalence, and provides a theoretical basis for extracting causal structures from empirical data. This representation is then extended to the more general case of an embedded causal model, that is, a dag in which only a subset of the variables are observable. The canonical representation presented here yields an efficient algorithm for determining when two embedded causal models reflect the same dependency information. This algorithm leads to a model theoretic definition of causation in terms of statistical dependencies.
Optimal Decomposition of Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, optimum decomposition of belief networks is discussed. Some methods of decomposition are examined and a new method - the method of Minimum Total Number of States (MTNS) - is proposed. The problem of optimum belief network decomposition under our framework, as under all the other frameworks, is shown to be NP-hard. According to the computational complexity analysis, an algorithm of belief network decomposition is proposed in (Wee, 1990a) based on simulated annealing.
Combination of Evidence Using the Principle of Minimum Information Gain
Venue: arXiv cs.AI 2013
Year: 2013

One of the most important aspects in any treatment of uncertain information is the rule of combination for updating the degrees of uncertainty. The theory of belief functions uses the Dempster rule to combine two belief functions defined by independent bodies of evidence. However, with limited dependency information about the accumulated belief the Dempster rule may lead to unsatisfactory results. The present study suggests a method to determine the accumulated belief based on the premise that the information gain from the combination process should be minimum. This method provides a mechanism that is equivalent to the Bayes rule when all the conditional probabilities are available and to the Dempster rule when the normalization constant is equal to one. The proposed principle of minimum information gain is shown to be equivalent to the maximum entropy formalism, a special case of the principle of minimum cross-entropy. The application of this principle results in a monotonic increase in belief with accumulation of consistent evidence. The suggested approach may provide a more reasonable criterion for identifying conflicts among various bodies of evidence.
An Empirical Analysis of Likelihood-Weighting Simulation on a Large, Multiply-Connected Belief Network
Venue: arXiv cs.AI 2013
Year: 2013

We analyzed the convergence properties of likelihood- weighting algorithms on a two-level, multiply connected, belief-network representation of the QMR knowledge base of internal medicine. Specifically, on two difficult diagnostic cases, we examined the effects of Markov blanket scoring, importance sampling, demonstrating that the Markov blanket scoring and self-importance sampling significantly improve the convergence of the simulation on our model.
Parameterized Verification of Asynchronous Shared-Memory Systems
Venue: arXiv cs.LO 2013
Year: 2013

We characterize the complexity of the safety verification problem for parameterized systems consisting of a leader process and arbitrarily many anonymous and identical contributors. Processes communicate through a shared, bounded-value register. While each operation on the register is atomic, there is no synchronization primitive to execute a sequence of operations atomically. We analyze the complexity of the safety verification problem when processes are modeled by finite-state machines, pushdown machines, and Turing machines. The problem is coNP-complete when all processes are finite-state machines, and is PSPACE-complete when they are pushdown machines. The complexity remains coNP-complete when each Turing machine is allowed boundedly many interactions with the register. Our proofs use combinatorial characterizations of computations in the model, and in case of pushdown-systems, some language-theoretic constructions of independent interest.
Efficient Distance Metric Learning by Adaptive Sampling and Mini-Batch Stochastic Gradient Descent (SGD)
Venue: arXiv cs.LG 2013
Year: 2013

Distance metric learning (DML) is an important task that has found applications in many domains. The high computational cost of DML arises from the large number of variables to be determined and the constraint that a distance metric has to be a positive semi-definite (PSD) matrix. Although stochastic gradient descent (SGD) has been successfully applied to improve the efficiency of DML, it can still be computationally expensive because in order to ensure that the solution is a PSD matrix, it has to, at every iteration, project the updated distance metric onto the PSD cone, an expensive operation. We address this challenge by developing two strategies within SGD, i.e. mini-batch and adaptive sampling, to effectively reduce the number of updates (i.e., projections onto the PSD cone) in SGD. We also develop hybrid approaches that combine the strength of adaptive sampling with that of mini-batch online learning techniques to further improve the computational efficiency of SGD for DML. We prove the theoretical guarantees for both adaptive sampling and mini-batch based approaches for DML. We also conduct an extensive empirical study to verify the effectiveness of the proposed algorithms for DML.
Shadow Detection: A Survey and Comparative Evaluation of Recent Methods
Venue: arXiv cs.CV 2013
Year: 2013

This paper presents a survey and a comparative evaluation of recent techniques for moving cast shadow detection. We identify shadow removal as a critical step for improving object detection and tracking. The survey covers methods published during the last decade, and places them in a feature-based taxonomy comprised of four categories: chromacity, physical, geometry and textures. A selection of prominent methods across the categories is compared in terms of quantitative performance measures (shadow detection and discrimination rates, colour desaturation) as well as qualitative observations. Furthermore, we propose the use of tracking performance as an unbiased approach for determining the practical usefulness of shadow detection methods. The evaluation indicates that all shadow detection approaches make different contributions and all have individual strength and weaknesses. Out of the selected methods, the geometry-based technique has strict assumptions and is not generalisable to various environments, but it is a straightforward choice when the objects of interest are easy to model and their shadows have different orientation. The chromacity based method is the fastest to implement and run, but it is sensitive to noise and less effective in low saturated scenes. The physical method improves upon the accuracy of the chromacity method by adapting to local shadow models, but fails when the spectral properties of the objects are similar to that of the background. The small-region texture based method is especially robust for pixels whose neighbourhood is textured, but may take longer to implement and is the most computationally expensive. The large-region texture based method produces the most accurate results, but has a significant computational load due to its multiple processing steps.
A Review on P2P Video Streaming
Venue: arXiv cs.NI 2013
Year: 2013

The main objective of this article is to provide an overview of P2P based Video-on-Demand and live streaming services. The article starts with an introduction to media streaming and its simplified architecture. Various solutions offering video streaming in the context of widespread usage of Internet are discussed. This is followed by a short introduction to P2P networks and its applications. A broad discussion on various P2P streaming schemes and P2P streaming applications are the main focus of this chapter. Finally, the security issues and solutions for P2P video streaming are discussed briefly.
On the complexity of strong Nash equilibrium: Hard-to-solve instances and smoothed complexity
Venue: arXiv cs.GT 2013
Year: 2013

The computational characterization of game-theoretic solution concepts is a central topic in artificial intelligence, with the aim of developing computationally efficient tools for finding optimal ways to behave in strategic interactions. The central solution concept in game theory is Nash equilibrium (NE). However, it fails to capture the possibility that agents can form coalitions (even in the 2-agent case). Strong Nash equilibrium (SNE) refines NE to this setting. It is known that finding an SNE is NP-complete when the number of agents is constant. This hardness is solely due to the existence of mixed-strategy SNEs, given that the problem of enumerating all pure-strategy SNEs is trivially in P. Our central result is that, in order for a game to have at least one non-pure-strategy SNE, the agents' payoffs restricted to the agents' supports must, in the case of 2 agents, lie on the same line, and, in the case of n agents, lie on an (n - 1)-dimensional hyperplane. Leveraging this result, we provide two contributions. First, we develop worst-case instances for support-enumeration algorithms. These instances have only one SNE and the support size can be chosen to be of any size-in particular, arbitrarily large. Second, we prove that, unlike NE, finding an SNE is in smoothed polynomial time: generic game instances (i.e., all instances except knife-edge cases) have only pure-strategy SNEs.
Fast SVM training using approximate extreme points
Venue: arXiv cs.LG 2013
Year: 2013

Applications of non-linear kernel Support Vector Machines (SVMs) to large datasets is seriously hampered by its excessive training time. We propose a modification, called the approximate extreme points support vector machine (AESVM), that is aimed at overcoming this burden. Our approach relies on conducting the SVM optimization over a carefully selected subset, called the representative set, of the training dataset. We present analytical results that indicate the similarity of AESVM and SVM solutions. A linear time algorithm based on convex hulls and extreme points is used to compute the representative set in kernel space. Extensive computational experiments on nine datasets compared AESVM to LIBSVM \citep{LIBSVM}, CVM \citep{Tsang05}, BVM \citep{Tsang07}, LASVM \citep{Bordes05}, $\text{SVM}^{\text{perf}}$ \citep{Joachims09}, and the random features method \citep{rahimi07}. Our AESVM implementation was found to train much faster than the other methods, while its classification accuracy was similar to that of LIBSVM in all cases. In particular, for a seizure detection dataset, AESVM training was almost $10^3$ times faster than LIBSVM and LASVM and more than forty times faster than CVM and BVM. Additionally, AESVM also gave competitively fast classification times.
Positive and Negative Explanations of Uncertain Reasoning in the Framework of Possibility Theory
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents an approach for developing the explanation capabilities of rule-based expert systems managing imprecise and uncertain knowledge. The treatment of uncertainty takes place in the framework of possibility theory where the available information concerning the value of a logical or numerical variable is represented by a possibility distribution which restricts its more or less possible values. We first discuss different kinds of queries asking for explanations before focusing on the two following types : i) how, a particular possibility distribution is obtained (emphasizing the main reasons only) ; ii) why in a computed possibility distribution, a particular value has received a possibility degree which is so high, so low or so contrary to the expectation. The approach is based on the exploitation of equations in max-min algebra. This formalism includes the limit case of certain and precise information.
d-Separation: From Theorems to Algorithms
Venue: arXiv cs.AI 2013
Year: 2013

An efficient algorithm is developed that identifies all independencies implied by the topology of a Bayesian network. Its correctness and maximality stems from the soundness and completeness of d-separation with respect to probability theory. The algorithm runs in time O (l E l) where E is the number of edges in the network.
The Relationship between Knowledge, Belief and Certainty
Venue: arXiv cs.AI 2013
Year: 2013

We consider the relation between knowledge and certainty, where a fact is known if it is true at all worlds an agent considers possible and is certain if it holds with probability 1. We identify certainty with probabilistic belief. We show that if we assume one fixed probability assignment, then the logic KD45, which has been identified as perhaps the most appropriate for belief, provides a complete axiomatization for reasoning about certainty. Just as an agent may believe a fact although phi is false, he may be certain that a fact phi, is true although phi is false. However, it is easy to see that an agent can have such false (probabilistic) beliefs only at a set of worlds of probability 0. If we restrict attention to structures where all worlds have positive probability, then S5 provides a complete axiomatization. If we consider a more general setting, where there might be a different probability assignment at each world, then by placing appropriate conditions on the support of the probability function (the set of worlds which have non-zero probability), we can capture many other well-known modal logics, such as T and S4. Finally, we consider which axioms characterize structures satisfying Miller's principle.
Hierarchical Evidence Accumulation in the Pseiki System and Experiments in Model-Driven Mobile Robot Navigation
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we will review the process of evidence accumulation in the PSEIKI system for expectation-driven interpretation of images of 3-D scenes. Expectations are presented to PSEIKI as a geometrical hierarchy of abstractions. PSEIKI's job is then to construct abstraction hierarchies in the perceived image taking cues from the abstraction hierarchies in the expectations. The Dempster-Shafer formalism is used for associating belief values with the different possible labels for the constructed abstractions in the perceived image. This system has been used successfully for autonomous navigation of a mobile robot in indoor environments.
A Logical Interpretation of Dempster-Shafer Theory, with Application to Visual Recognition
Venue: arXiv cs.AI 2013
Year: 2013

We formulate Dempster Shafer Belief functions in terms of Propositional Logic using the implicit notion of provability underlying Dempster Shafer Theory. Given a set of propositional clauses, assigning weights to certain propositional literals enables the Belief functions to be explicitly computed using Network Reliability techniques. Also, the logical procedure corresponding to updating Belief functions using Dempster's Rule of Combination is shown. This analysis formalizes the implementation of Belief functions within an Assumption-based Truth Maintenance System (ATMS). We describe the extension of an ATMS-based visual recognition system, VICTORS, with this logical formulation of Dempster Shafer theory. Without Dempster Shafer theory, VICTORS computes all possible visual interpretations (i.e. all logical models) without determining the best interpretation(s). Incorporating Dempster Shafer theory enables optimal visual interpretations to be computed and a logical semantics to be maintained.
Efficient Parallel Estimation for Markov Random Fields
Venue: arXiv cs.AI 2013
Year: 2013

We present a new, deterministic, distributed MAP estimation algorithm for Markov Random Fields called Local Highest Confidence First (Local HCF). The algorithm has been applied to segmentation problems in computer vision and its performance compared with stochastic algorithms. The experiments show that Local HCF finds better estimates than stochastic algorithms with much less computation.
Generalization Bounds for Domain Adaptation
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we provide a new framework to obtain the generalization bounds of the learning process for domain adaptation, and then apply the derived bounds to analyze the asymptotical convergence of the learning process. Without loss of generality, we consider two kinds of representative domain adaptation: one is with multiple sources and the other is combining source and target data. In particular, we use the integral probability metric to measure the difference between two domains. For either kind of domain adaptation, we develop a related Hoeffding-type deviation inequality and a symmetrization inequality to achieve the corresponding generalization bound based on the uniform entropy number. We also generalized the classical McDiarmid's inequality to a more general setting where independent random variables can take values from different domains. By using this inequality, we then obtain generalization bounds based on the Rademacher complexity. Afterwards, we analyze the asymptotic convergence and the rate of convergence of the learning process for such kind of domain adaptation. Meanwhile, we discuss the factors that affect the asymptotic behavior of the learning process and the numerical experiments support our theoretical findings as well.
Mathematical modeling of thermal stabilization of vertical wells on high performance computing systems
Venue: arXiv cs.CE 2013
Year: 2013

Temperature stabilization of oil and gas wells is used to ensure stability and prevent deformation of a subgrade estuary zone. In this work, we consider the numerical simulation of thermal stabilization using vertical seasonal freezing columns. A mathematical model of such problems is described by a time-dependent temperature equation with phase transitions from water to ice. The resulting equation is a standard nonlinear parabolic equation. Numerical implementation is based on the finite element method using the package Fenics. After standard purely implicit approximation in time and simple linearization, we obtain a system of linear algebraic equations. Because the size of freezing columns are substantially less than the size of the modeled area, we obtain mesh refinement near columns. Due to this, we get a large system of equations which are solved using high performance computing systems.
Pattern-Based Constraint Satisfaction and Logic Puzzles
Venue: arXiv cs.AI 2013
Year: 2013

Pattern-Based Constraint Satisfaction and Logic Puzzles develops a pure logic, pattern-based perspective of solving the finite Constraint Satisfaction Problem (CSP), with emphasis on finding the "simplest" solution. Different ways of reasoning with the constraints are formalised by various families of "resolution rules", each of them carrying its own notion of simplicity. A large part of the book illustrates the power of the approach by applying it to various popular logic puzzles. It provides a unified view of how to model and solve them, even though they involve very different types of constraints: obvious symmetric ones in Sudoku, non-symmetric but transitive ones (inequalities) in Futoshiki, topological and geometric ones in Map colouring, Numbrix and Hidato, and even much more complex non-binary arithmetic ones in Kakuro (or Cross Sums). It also shows that the most familiar techniques for these puzzles can indeed be understood as mere application-specific presentations of the general rules. Sudoku is used as the main example throughout the book, making it also an advanced level sequel to "The Hidden Logic of Sudoku" (another book by the same author), with: many examples of relationships among different rules and of exceptional situations; comparisons of the resolution potential of various families of rules; detailed statistics of puzzles hardness; analysis of extreme instances.
Semantic Tagging on Historical Maps
Venue: arXiv cs.DL 2013
Year: 2013

Tags assigned by users to shared content can be ambiguous. As a possible solution, we propose semantic tagging as a collaborative process in which a user selects and associates Web resources drawn from a knowledge context. We applied this general technique in the specific context of online historical maps and allowed users to annotate and tag them. To study the effects of semantic tagging on tag production, the types and categories of obtained tags, and user task load, we conducted an in-lab within-subject experiment with 24 participants who annotated and tagged two distinct maps. We found that the semantic tagging implementation does not affect these parameters, while providing tagging relationships to well-defined concept definitions. Compared to label-based tagging, our technique also gathers positive and negative tagging relationships. We believe that our findings carry implications for designers who want to adopt semantic tagging in other contexts and systems on the Web.
Trust Estimation in Peer-to-Peer Network Using BLUE
Venue: arXiv cs.NI 2013
Year: 2013

In peer-to-peer networks, free riding is a major problem. Reputation management systems can be used to overcome this problem. Reputation estimation methods generally do not consider the uncertainties in the inputs. We propose a reputation estimation method using BLUE (Best Linear Unbiased estimator) estimator that consider uncertainties in the input variables.
Bug Classification: Feature Extraction and Comparison of Event Model using Naïve Bayes Approach
Venue: arXiv cs.SE 2013
Year: 2013

In software industries, individuals at different levels from customer to an engineer apply diverse mechanisms to detect to which class a particular bug should be allocated. Sometimes while a simple search in Internet might help, in many other cases a lot of effort is spent in analyzing the bug report to classify the bug. So there is a great need of a structured mining algorithm - where given a crash log, the existing bug database could be mined to find out the class to which the bug should be allocated. This would involve Mining patterns and applying different classification algorithms. This paper focuses on the feature extraction, noise reduction in data and classification of network bugs using probabilistic Naïve Bayes approach. Different event models like Bernoulli and Multinomial are applied on the extracted features. When new, unseen bugs are given as input to the algorithms, the performance comparison of different algorithms is done on the basis of accuracy and recall parameters.
Short Message Noisy Network Coding with a Decode-Forward Option
Venue: arXiv cs.IT 2013
Year: 2013

Short message noisy network coding (SNNC) differs from long message noisy network coding (LNNC) in that one transmits many short messages in blocks rather than using one long message with repetitive encoding. Several properties of SNNC are developed. First, SNNC with backward decoding achieves the same rates as SNNC with offset encoding and sliding window decoding for memoryless networks where each node transmits a multicast message. The rates are the same as LNNC with joint decoding. Second, SNNC enables early decoding if the channel quality happens to be good. This leads to mixed strategies that unify the advantages of decode-forward and noisy network coding. Third, the best decoders sometimes treat other nodes' signals as noise and an iterative method is given to find the set of nodes that a given node should treat as noise sources.
Note: interpreting iterative methods convergence with diffusion point of view
Venue: arXiv cs.NA 2013
Year: 2013

In this paper, we explain the convergence speed of different iteration schemes with the fluid diffusion view when solving a linear fixed point problem. This interpretation allows one to better understand why power iteration or Jacobi iteration may converge faster or slower than Gauss-Seidel iteration.