OpenRaiser/Intern-Atlas huggingface dataset:
Pre-processing for Triangulation of Probabilistic Networks
Venue: arXiv cs.AI 2013
Year: 2013

The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations forprobabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.
Conditions Under Which Conditional Independence and Scoring Methods Lead to Identical Selection of Bayesian Network Models
Venue: arXiv cs.AI 2013
Year: 2013

It is often stated in papers tackling the task of inferring Bayesian network structures from data that there are these two distinct approaches: (i) Apply conditional independence tests when testing for the presence or otherwise of edges; (ii) Search the model space using a scoring metric. Here I argue that for complete data and a given node ordering this division is a myth, by showing that cross entropy methods for checking conditional independence are mathematically identical to methods based upon discriminating between models by their overall goodness-of-fit logarithmic scores.
Using Bayesian Networks to Identify the Causal Effect of Speeding in Individual Vehicle/Pedestrian Collisions
Venue: arXiv cs.AI 2013
Year: 2013

On roads showing significant violations of posted speed limits, one measure of the safety effect of speeding is the difference between the road's actual accident count and the count that would have occurred if the posted speed limit had been strictly obeyed. An estimate of this accident reduction can be had by computing the probability that speeding was a necessary condition for each of set of accidents. This is an instance of assessing individual probabilities of causation, which is generally not possible absent prior knowledge of causal structure. For traffic accidents such prior knowledge is often available and this paper illustrates how, for a commonly occurring class of vehicle/pedestrian accidents, approaches to uncertainty and causal analyses appearing in the accident reconstruction literature can be unified using Bayesian networks. Measured skidmarks, pedestrian throw distances, and pedestrian injury severity are treated as evidence, and using the Gibbs Sampling routine BUGS, the posterior probability distribution over exogenous variables, such as the vehicle's initial speed, location, and driver reaction time, is computed. This posterior distribution is then used to compute the "probability of necessity" for speeding.
Efficient Stepwise Selection in Decomposable Models
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we present an efficient way of performing stepwise selection in the class of decomposable models. The main contribution of the paper is a simple characterization of the edges that canbe added to a decomposable model while keeping the resulting model decomposable and an efficient algorithm for enumerating all such edges for a given model in essentially O(1) time per edge. We also discuss how backward selection can be performed efficiently using our data structures.We also analyze the complexity of the complete stepwise selection procedure, including the complexity of choosing which of the eligible dges to add to (or delete from) the current model, with the aim ofminimizing the Kullback-Leibler distance of the resulting model from the saturated model for the data.
A Comparison of Axiomatic Approaches to Qualitative Decision Making Using Possibility Theory
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we analyze two recent axiomatic approaches proposed by Dubois et al and by Giang and Shenoy to qualitative decision making where uncertainty is described by possibility theory. Both axiomtizations are inspired by von Neumann and Morgenstern's system of axioms for the case of probability theory. We show that our approach naturally unifies two axiomatic systems that correspond respectively to pessimistic and optimistic decision criteria proposed by Dubois et al. The simplifying unification is achieved by (i) replacing axioms that are supposed to reflect two informational attitudes (uncertainty aversion and uncertainty attraction) by an axiom that imposes order on set of standard lotteries and (ii) using a binary utility scale in which each utility level is represented by a pair of numbers.
A Clustering Approach to Solving Large Stochastic Matching Problems
Venue: arXiv cs.AI 2013
Year: 2013

In this work we focus on efficient heuristics for solving a class of stochastic planning problems that arise in a variety of business, investment, and industrial applications. The problem is best described in terms of future buy and sell contracts. By buying less reliable, but less expensive, buy (supply) contracts, a company or a trader can cover a position of more reliable and more expensive sell contracts. The goal is to maximize the expected net gain (profit) by constructing a dose to optimum portfolio out of the available buy and sell contracts. This stochastic planning problem can be formulated as a two-stage stochastic linear programming problem with recourse. However, this formalization leads to solutions that are exponential in the number of possible failure combinations. Thus, this approach is not feasible for large scale problems. In this work we investigate heuristic approximation techniques alleviating the efficiency problem. We primarily focus on the clustering approach and devise heuristics for finding clusterings leading to good approximations. We illustrate the quality and feasibility of the approach through experimental data.
Plausible reasoning from spatial observations
Venue: arXiv cs.AI 2013
Year: 2013

This article deals with plausible reasoning from incomplete knowledge about large-scale spatial properties. The availableinformation, consisting of a set of pointwise observations,is extrapolated to neighbour points. We make use of belief functions to represent the influence of the knowledge at a given point to another point; the quantitative strength of this influence decreases when the distance between both points increases. These influences arethen aggregated using a variant of Dempster's rule of combination which takes into account the relative dependence between observations.
Inference in Hybrid Networks: Theoretical Limits and Practical Algorithms
Venue: arXiv cs.AI 2013
Year: 2013

An important subclass of hybrid Bayesian networks are those that represent Conditional Linear Gaussian (CLG) distributions --- a distribution with a multivariate Gaussian component for each instantiation of the discrete variables. In this paper we explore the problem of inference in CLGs. We show that inference in CLGs can be significantly harder than inference in Bayes Nets. In particular, we prove that even if the CLG is restricted to an extremely simple structure of a polytree in which every continuous node has at most one discrete ancestor, the inference task is NP-hard.To deal with the often prohibitive computational cost of the exact inference algorithm for CLGs, we explore several approximate inference algorithms. These algorithms try to find a small subset of Gaussians which are a good approximation to the full mixture distribution. We consider two Monte Carlo approaches and a novel approach that enumerates mixture components in order of prior probability. We compare these methods on a variety of problems and show that our novel algorithm is very promising for large, hybrid diagnosis problems.
Probabilistic Logic Programming under Inheritance with Overriding
Venue: arXiv cs.AI 2013
Year: 2013

We present probabilistic logic programming under inheritance with overriding. This approach is based on new notions of entailment for reasoning with conditional constraints, which are obtained from the classical notion of logical entailment by adding the principle of inheritance with overriding. This is done by using recent approaches to probabilistic default reasoning with conditional constraints. We analyze the semantic properties of the new entailment relations. We also present algorithms for probabilistic logic programming under inheritance with overriding, and program transformations for an increased efficiency.
A Bayesian Multiresolution Independence Test for Continuous Variables
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we present a method ofcomputing the posterior probability ofconditional independence of two or morecontinuous variables from data,examined at several resolutions. Ourapproach is motivated by theobservation that the appearance ofcontinuous data varies widely atvarious resolutions, producing verydifferent independence estimatesbetween the variablesinvolved. Therefore, it is difficultto ascertain independence withoutexamining data at several carefullyselected resolutions. In our paper, weaccomplish this using the exactcomputation of the posteriorprobability of independence, calculatedanalytically given a resolution. Ateach examined resolution, we assume amultinomial distribution with Dirichletpriors for the discretized tableparameters, and compute the posteriorusing Bayesian integration. Acrossresolutions, we use a search procedureto approximate the Bayesian integral ofprobability over an exponential numberof possible histograms. Our methodgeneralizes to an arbitrary numbervariables in a straightforward manner.The test is suitable for Bayesiannetwork learning algorithms that useindependence tests to infer the networkstructure, in domains that contain anymix of continuous, ordinal andcategorical variables.
Quasi-SLCA based Keyword Query Processing over Probabilistic XML Data
Venue: arXiv cs.DB 2013
Year: 2013

The probabilistic threshold query is one of the most common queries in uncertain databases, where a result satisfying the query must be also with probability meeting the threshold requirement. In this paper, we investigate probabilistic threshold keyword queries (PrTKQ) over XML data, which is not studied before. We first introduce the notion of quasi-SLCA and use it to represent results for a PrTKQ with the consideration of possible world semantics. Then we design a probabilistic inverted (PI) index that can be used to quickly return the qualified answers and filter out the unqualified ones based on our proposed lower/upper bounds. After that, we propose two efficient and comparable algorithms: Baseline Algorithm and PI index-based Algorithm. To accelerate the performance of algorithms, we also utilize probability density function. An empirical study using real and synthetic data sets has verified the effectiveness and the efficiency of our approaches.
Determining token sequence mistakes in responses to questions with open text answer
Venue: arXiv cs.CL 2013
Year: 2013

When learning grammar of the new language, a teacher should routinely check student's exercises for grammatical correctness. The paper describes a method of automatically detecting and reporting grammar mistakes, regarding an order of tokens in the response. It could report extra tokens, missing tokens and misplaced tokens. The method is useful when teaching language, where order of tokens is important, which includes most formal languages and some natural ones (like English). The method was implemented in a question type plug-in CorrectWriting for the widely used learning manage system Moodle.
Operator Precedence ω-languages
Venue: arXiv cs.FL 2013
Year: 2013

ω-languages are becoming more and more relevant nowadays when most applications are 'ever-running'. Recent literature, mainly under the motivation of widening the application of model checking techniques, extended the analysis of these languages from the simple regular ones to various classes of languages with 'visible syntax structure', such as visibly pushdown languages (VPLs). Operator precedence languages (OPLs), instead, were originally defined to support deterministic parsing and, though seemingly unrelated, exhibit interesting relations with these classes of languages: OPLs strictly include VPLs, enjoy all relevant closure properties and have been characterized by a suitable automata family and a logic notation. In this paper we introduce operator precedence ω-languages (ωOPLs), investigating various acceptance criteria and their closure properties. Whereas some properties are natural extensions of those holding for regular languages, others required novel investigation techniques. Application-oriented examples show the gain in expressiveness and verifiability offered by ωOPLs w.r.t. smaller classes.
A New Distributed Localization Method for Sensor Networks
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the problem of determining the sensor locations in a large sensor network using relative distance (range) measurements only. Our work follows from a seminal paper by Khan et al. [1] where a distributed algorithm, known as DILOC, for sensor localization is given using the barycentric coordinate. A main limitation of the DILOC algorithm is that all sensor nodes must be inside the convex hull of the anchor nodes. In this paper, we consider a general sensor network without the convex hull assumption, which incurs challenges in determining the sign pattern of the barycentric coordinate. A criterion is developed to address this issue based on available distance measurements. Also, a new distributed algorithm is proposed to guarantee the asymptotic localization of all localizable sensor nodes.
Verification of Agent-Based Artifact Systems
Venue: arXiv cs.MA 2013
Year: 2013

Artifact systems are a novel paradigm for specifying and implementing business processes described in terms of interacting modules called artifacts. Artifacts consist of data and lifecycles, accounting respectively for the relational structure of the artifacts' states and their possible evolutions over time. In this paper we put forward artifact-centric multi-agent systems, a novel formalisation of artifact systems in the context of multi-agent systems operating on them. Differently from the usual process-based models of services, the semantics we give explicitly accounts for the data structures on which artifact systems are defined. We study the model checking problem for artifact-centric multi-agent systems against specifications written in a quantified version of temporal-epistemic logic expressing the knowledge of the agents in the exchange. We begin by noting that the problem is undecidable in general. We then identify two noteworthy restrictions, one syntactical and one semantical, that enable us to find bisimilar finite abstractions and therefore reduce the model checking problem to the instance on finite models. Under these assumptions we show that the model checking problem for these systems is EXPSPACE-complete. We then introduce artifact-centric programs, compact and declarative representations of the programs governing both the artifact system and the agents. We show that, while these in principle generate infinite-state systems, under natural conditions their verification problem can be solved on finite abstractions that can be effectively computed from the programs. Finally we exemplify the theoretical results of the paper through a mainstream procurement scenario from the artifact systems literature.
An Extended Weighted Partitioning Around Cluster Head Mechanism for Ad Hoc Network
Venue: arXiv cs.NI 2013
Year: 2013

The wireless network places vital role in the present day communication scenario. The ad hoc nature of wireless communication adds flavour to suit various real world applications. This improves the performance of the network tremendously while the clustering mechanism gets added to the ad hoc network. It has been found out that the existing WCA lacks in forming efficient clusters. Thus, this work proposes an Extended weighted partitioning around cluster head mechanism by considering W-PAC as a base to form clusters. The cluster members are configured with IPv6 address. This IPv6 clusters formed through W-PAC will be taken further for validation to determine the perfectness of clusters. The cluster formation and maintenance have been implemented in C++ as a programming language. The cluster validation has been carried out using OMNET++ simulator.
Adaptive Reduced-Rank Equalization Algorithms Based on Alternating Optimization Design Techniques for Multi-Antenna Systems
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents a novel adaptive reduced-rank {multi-input multi-output} (MIMO) equalization scheme and algorithms based on alternating optimization design techniques for MIMO spatial multiplexing systems. The proposed reduced-rank equalization structure consists of a joint iterative optimization of two equalization stages, namely, a transformation matrix that performs dimensionality reduction and a reduced-rank estimator that retrieves the desired transmitted symbol. The proposed reduced-rank architecture is incorporated into an equalization structure that allows both decision feedback and linear schemes for mitigating the inter-antenna and inter-symbol interference. We develop alternating least squares (LS) expressions for the design of the transformation matrix and the reduced-rank estimator along with computationally efficient alternating recursive least squares (RLS) adaptive estimation algorithms. We then present an algorithm for automatically adjusting the model order of the proposed scheme. An analysis of the LS algorithms is carried out along with sufficient conditions for convergence and a proof of convergence of the proposed algorithms to the reduced-rank Wiener filter. Simulations show that the proposed equalization algorithms outperform the existing reduced-rank and full-rank algorithms, while requiring a comparable computational cost.
Evaluating community structure in large network with random walks
Venue: arXiv cs.SI 2013
Year: 2013

Community structure is one of the most important properties of networks. Most community algorithms are not suitable for large networks because of their time consuming. In fact there are lots of networks with millons even billons of nodes. In such case, most algorithms running in time O(n2logn) or even larger are not practical. What we need are linear or approximately linear time algorithm. Rising in response to such needs, we propose a quick methods to evaluate community structure in networks and then put forward a local community algorithm with nearly linear time based on random walks. Using our community evaluating measure, we could find some difference results from measures used before, i.e., the Newman Modularity. Our algorithm are effective in small benchmark networks with small less accuracy than more complex algorithms but a great of advantage in time consuming for large networks, especially super large networks.
Microelectromechanical Resonators for Radio Frequency Communication Applications
Venue: arXiv cs.OH 2013
Year: 2013

Over the past few years, microelectromechanical system (MEMS) based on-chip resonators have shown significant potential for sensing and high frequency signal processing applications. This is due to their excellent features like small size, large frequency-quality factor product, low power consumption, low cost batch fabrication, and integrability with CMOS IC technology. Radio frequency communication circuits like reference oscillators, filters, and mixers based on such MEMS resonators can be utilized for meeting the increasing count of RF components likely to be demanded by the next generation multi-band/multi-mode wireless devices. MEMS resonators can provide a feasible alternative to the present day well established quartz crystal technology that is riddled with major drawbacks like relatively large size, high cost, and low compatibility with IC chips. This article presents a survey of the developments in this field of resonant MEMS structures with detailed enumeration on the various micromechanical resonator types, modes of vibration, equivalent mechanical and electrical models, materials and technologies used for fabrication, and the application of the resonators for implementing oscillators and filters. These are followed by a discussion on the challenges for RF MEMS technology in comparison to quartz crystal technology; like high precision, stability, reliability, need for hermetic packaging etc. which remain to be addressed for enabling the inclusion of micromechanical resonators into tomorrow's highly integrated communication systems.
A comparison of SVM and RVM for Document Classification
Venue: arXiv cs.IR 2013
Year: 2013

Document classification is a task of assigning a new unclassified document to one of the predefined set of classes. The content based document classification uses the content of the document with some weighting criteria to assign it to one of the predefined classes. It is a major task in library science, electronic document management systems and information sciences. This paper investigates document classification by using two different classification techniques (1) Support Vector Machine (SVM) and (2) Relevance Vector Machine (RVM). SVM is a supervised machine learning technique that can be used for classification task. In its basic form, SVM represents the instances of the data into space and tries to separate the distinct classes by a maximum possible wide gap (hyper plane) that separates the classes. On the other hand RVM uses probabilistic measure to define this separation space. RVM uses Bayesian inference to obtain succinct solution, thus RVM uses significantly fewer basis functions. Experimental studies on three standard text classification datasets reveal that although RVM takes more training time, its classification is much better as compared to SVM.
Generic System Verilog Universal Verification Methodology based Reusable Verification Environment for Efficient Verification of Image Signal Processing IPs/SoCs
Venue: arXiv cs.OH 2013
Year: 2013

In this paper,we present Generic System Verilog Universal Verification Methodology based Reusable Verification Environment for efficient verification of Image Signal Processing IP's/SoC's. With the tight schedules on all projects it is important to have a strong verification methodology which contributes to First Silicon Success. Deploy methodologies which enforce full functional coverage and verification of corner cases through pseudo random test scenarios is required. Also, standardization of verification flow is needed. Previously, inside imaging group of ST, Specman (e)/Verilog based Verification Environment for IP/Subsystem level verification and C/C++/Verilog based Directed Verification Environment for SoC Level Verification was used for Functional Verification. Different Verification Environments were used at IP level and SoC level. Different Verification/Validation Methodologies were used for SoC Verification across multiple sites. Verification teams were also looking for the ways how to catch bugs early in the design cycle? Thus, Generic System Verilog Universal Verification Methodology (UVM) based Reusable Verification Environment is required to avoid the problem of having so many methodologies and provides a standard unified solution which compiles on all tools. The main aim of development of this Generic and automatic verification environment is to develop an efficient and unified verification environment (at IP/Subsystem/SoC Level) which reuses the already developed Verification components and also sequences written at IP/Subsystem level can be reused at SoC Level both with Host BFM and actual Core using Incisive Software Extension (ISX) and Virtual Register Interface (VRI)/Verification Abstraction Layer (VAL) approaches. IP-XACT based tools are used for automatically configuring the environment for various imaging IPs/SoCs.