OpenRaiser/Intern-Atlas huggingface dataset:
Exploiting Evidence-dependent Sensitivity Bounds
Venue: arXiv cs.AI 2012
Year: 2012

Studying the effects of one-way variation of any number of parameters on any number of output probabilities quickly becomes infeasible in practice, especially if various evidence profiles are to be taken into consideration. To provide for identifying the parameters that have a potentially large effect prior to actually performing the analysis, we need properties of sensitivity functions that are independent of the network under study, of the available evidence, or of both. In this paper, we study properties that depend upon just the probability of the entered evidence. We demonstrate that these properties provide for establishing an upper bound on the sensitivity value for a parameter; they further provide for establishing the region in which the vertex of the sensitivity function resides, thereby serving to identify parameters with a low sensitivity value that may still have a large impact on the probability of interest for relatively small parameter variations.
Exploiting Evidence in Probabilistic Inference
Venue: arXiv cs.AI 2012
Year: 2012

We define the notion of compiling a Bayesian network with evidence and provide a specific approach for evidence-based compilation, which makes use of logical processing. The approach is practical and advantageous in a number of application areas-including maximum likelihood estimation, sensitivity analysis, and MAP computations-and we provide specific empirical results in the domain of genetic linkage analysis. We also show that the approach is applicable for networks that do not contain determinism, and show that it empirically subsumes the performance of the quickscore algorithm when applied to noisy-or networks.
Efficient algorithm for estimation of qualitative expected utility in possibilistic case-based reasoning
Venue: arXiv cs.AI 2012
Year: 2012

We propose an efficient algorithm for estimation of possibility based qualitative expected utility. It is useful for decision making mechanisms where each possible decision is assigned a multi-attribute possibility distribution. The computational complexity of ordinary methods calculating the expected utility based on discretization is growing exponentially with the number of attributes, and may become infeasible with a high number of these attributes. We present series of theorems and lemmas proving the correctness of our algorithm that exibits a linear computational complexity. Our algorithm has been applied in the context of selecting the most prospective partners in multi-party multi-attribute negotiation, and can also be used in making decisions about potential offers during the negotiation as other similar problems.
Approximate Inference Algorithms for Hybrid Bayesian Networks with Discrete Constraints
Venue: arXiv cs.AI 2012
Year: 2012

In this paper, we consider Hybrid Mixed Networks (HMN) which are Hybrid Bayesian Networks that allow discrete deterministic information to be modeled explicitly in the form of constraints. We present two approximate inference algorithms for HMNs that integrate and adjust well known algorithmic principles such as Generalized Belief Propagation, Rao-Blackwellised Importance Sampling and Constraint Propagation to address the complexity of modeling and reasoning in HMNs. We demonstrate the performance of our approximate inference algorithms on randomly generated HMNs.
On the Number of Experiments Sufficient and in the Worst Case Necessary to Identify All Causal Relations Among N Variables
Venue: arXiv cs.AI 2012
Year: 2012

We show that if any number of variables are allowed to be simultaneously and independently randomized in any one experiment, log2(N) + 1 experiments are sufficient and in the worst case necessary to determine the causal relations among N >= 2 variables when no latent variables, no sample selection bias and no feedback cycles are present. For all K, 0 < K < 1/(2N) we provide an upper bound on the number experiments required to determine causal structure when each experiment simultaneously randomizes K variables. For large N, these bounds are significantly lower than the N - 1 bound required when each experiment randomizes at most one variable. For kmax < N/2, we show that (N/kmax-1)+N/(2kmax)log2(kmax) experiments aresufficient and in the worst case necessary. We over a conjecture as to the minimal number of experiments that are in the worst case sufficient to identify all causal relations among N observed variables that are a subset of the vertices of a DAG.
Learning about individuals from group statistics
Venue: arXiv cs.LG 2012
Year: 2012

We propose a new problem formulation which is similar to, but more informative than, the binary multiple-instance learning problem. In this setting, we are given groups of instances (described by feature vectors) along with estimates of the fraction of positively-labeled instances per group. The task is to learn an instance level classifier from this information. That is, we are trying to estimate the unknown binary labels of individuals from knowledge of group statistics. We propose a principled probabilistic model to solve this problem that accounts for uncertainty in the parameters and in the unknown individual labels. This model is trained with an efficient MCMC algorithm. Its performance is demonstrated on both synthetic and real-world data arising in general object recognition.
Self-Confirming Price Prediction for Bidding in Simultaneous Ascending Auctions
Venue: arXiv cs.GT 2012
Year: 2012

Simultaneous ascending auctions present agents with the exposure problem: bidding to acquire a bundle risks the possibility of obtaining an undesired subset of the goods. Auction theory provides little guidance for dealing with this problem. We present a new family of decisiontheoretic bidding strategies that use probabilistic predictions of final prices. We focus on selfconfirming price distribution predictions, which by definition turn out to be correct when all agents bid decision-theoretically based on them. Bidding based on these is provably not optimal in general, but our experimental evidence indicates the strategy can be quite effective compared to other known methods.
Expectation Maximization and Complex Duration Distributions for Continuous Time Bayesian Networks
Venue: arXiv cs.AI 2012
Year: 2012

Continuous time Bayesian networks (CTBNs) describe structured stochastic processes with finitely many states that evolve over continuous time. A CTBN is a directed (possibly cyclic) dependency graph over a set of variables, each of which represents a finite state continuous time Markov process whose transition model is a function of its parents. We address the problem of learning the parameters and structure of a CTBN from partially observed data. We show how to apply expectation maximization (EM) and structural expectation maximization (SEM) to CTBNs. The availability of the EM algorithm allows us to extend the representation of CTBNs to allow a much richer class of transition durations distributions, known as phase distributions. This class is a highly expressive semi-parametric representation, which can approximate any duration distribution arbitrarily closely. This extension to the CTBN framework addresses one of the main limitations of both CTBNs and DBNs - the restriction to exponentially / geometrically distributed duration. We present experimental results on a real data set of people's life spans, showing that our algorithm learns reasonable models - structure and parameters - from partially observed data, and, with the use of phase distributions, achieves better performance than DBNs.
The Relationship Between AND/OR Search and Variable Elimination
Venue: arXiv cs.AI 2012
Year: 2012

In this paper we compare search and inference in graphical models through the new framework of AND/OR search. Specifically, we compare Variable Elimination (VE) and memoryintensive AND/OR Search (AO) and place algorithms such as graph-based backjumping and no-good and good learning, as well as Recursive Conditioning [7] and Value Elimination [2] within the AND/OR search framework.
Piecewise Training for Undirected Models
Venue: arXiv cs.LG 2012
Year: 2012

For many large undirected models that arise in real-world applications, exact maximumlikelihood training is intractable, because it requires computing marginal distributions of the model. Conditional training is even more difficult, because the partition function depends not only on the parameters, but also on the observed input, requiring repeated inference over each training example. An appealing idea for such models is to independently train a local undirected classifier over each clique, afterwards combining the learned weights into a single global model. In this paper, we show that this piecewise method can be justified as minimizing a new family of upper bounds on the log partition function. On three natural-language data sets, piecewise training is more accurate than pseudolikelihood, and often performs comparably to global training using belief propagation.
Point-Based POMDP Algorithms: Improved Analysis and Implementation
Venue: arXiv cs.AI 2012
Year: 2012

Existing complexity bounds for point-based POMDP value iteration algorithms focus either on the curse of dimensionality or the curse of history. We derive a new bound that relies on both and uses the concept of discounted reachability; our conclusions may help guide future algorithm design. We also discuss recent improvements to our (point-based) heuristic search value iteration algorithm. Our new implementation calculates tighter initial bounds, avoids solving linear programs, and makes more effective use of sparsity.
Discovery of non-gaussian linear causal models using ICA
Venue: arXiv cs.LG 2012
Year: 2012

In recent years, several methods have been proposed for the discovery of causal structure from non-experimental data (Spirtes et al. 2000; Pearl 2000). Such methods make various assumptions on the data generating process to facilitate its identification from purely observational data. Continuing this line of research, we show how to discover the complete causal structure of continuous-valued data, under the assumptions that (a) the data generating process is linear, (b) there are no unobserved confounders, and (c) disturbance variables have non-gaussian distributions of non-zero variances. The solution relies on the use of the statistical method known as independent component analysis (ICA), and does not require any pre-specified time-ordering of the variables. We provide a complete Matlab package for performing this LiNGAM analysis (short for Linear Non-Gaussian Acyclic Model), and demonstrate the effectiveness of the method using artificially generated data.
Super-Mixed Multiple Attribute Group Decision Making Method Based on Hybrid Fuzzy Grey Relation Approach Degree
Venue: arXiv cs.AI 2012
Year: 2012

The feature of our method different from other fuzzy grey relation method for supermixed multiple attribute group decision-making is that all of the subjective and objective weights are obtained by interval grey number and that the group decisionmaking is performed based on the relative approach degree of grey TOPSIS, the relative approach degree of grey incidence and the relative membership degree of grey incidence using 4-dimensional Euclidean distance. The weighted Borda method is used to obtain final rank by using the results of four methods. An example shows the applicability of the proposed approach.
Design and Development of Low Cost Multi-Channel USB Data
Venue: arXiv cs.AR 2012
Year: 2012

This paper describes the design and development of low cost USB Data Acquisition System (DAS) for the measurement of physical parameters. Physical parameters such as temperature, humidity, light intensity etc., which are generally slowly varying signals are sensed by respective sensors or integrated sensors and converted into voltages. The DAS is designed using PIC18F4550 microcontroller, communicating with Personal Computer (PC) through USB (Universal Serial Bus). The designed DAS has been tested with the application program developed in Visual Basic, which allows online monitoring in graphical as well as numerical display.
A Generic Library for Stencil Computations
Venue: arXiv cs.MS 2012
Year: 2012

In this era of diverse and heterogeneous computer architectures, the programmability issues, such as productivity and portable efficiency, are crucial to software development and algorithm design. One way to approach the problem is to step away from traditional sequential programming languages and move toward domain specific programming environments to balance between expressivity and efficiency. In order to demonstrate this principle, we developed a domain specific C++ generic library for stencil computations, like PDE solvers. The library features high level constructs to specify computation and allows the development of parallel stencil computations with very limited effort. The high abstraction constructs (like do_all and do_reduce) make the program shorter and cleaner with increased contextual information for better performance exploitation. The results show good performance from Windows multicores, to HPC clusters and machines with accelerators, like GPUs.
A hybrid Hermitian general eigenvalue solver
Venue: arXiv cs.NA 2012
Year: 2012

The adoption of hybrid GPU-CPU nodes in traditional supercomputing platforms opens acceleration opportunities for electronic structure calculations in materials science and chemistry applications, where medium sized Hermitian generalized eigenvalue problems must be solved many times. The small size of the problems limits the scalability on a distributed memory system, hence they can benefit from the massive computational performance concentrated on a single node, hybrid GPU-CPU system. However, new algorithms that efficiently exploit heterogeneity and massive parallelism of not just GPUs, but of multi/many-core CPUs as well are required. Addressing these demands, we implemented a novel Hermitian general eigensolver algorithm. This algorithm is based on a standard eigenvalue solver, and existing algorithms can be used. The resulting eigensolvers are state-of-the-art in HPC, significantly outperforming existing libraries. We analyze their performance impact on applications of interest, when different fractions of eigenvectors are needed by the host electronic structure code.
Improved Bounds for Online Preemptive Matching
Venue: arXiv cs.DS 2012
Year: 2012

When designing a preemptive online algorithm for the maximum matching problem, we wish to maintain a valid matching M while edges of the underlying graph are presented one after the other. When presented with an edge e, the algorithm should decide whether to augment the matching M by adding e (in which case e may be removed later on) or to keep M in its current form without adding e (in which case e is lost for good). The objective is to eventually hold a matching M with maximum weight. The main contribution of this paper is to establish new lower and upper bounds on the competitive ratio achievable by preemptive online algorithms: 1. We provide a lower bound of 1+ln 2~1.693 on the competitive ratio of any randomized algorithm for the maximum cardinality matching problem, thus improving on the currently best known bound of e/(e-1)~1.581 due to Karp, Vazirani, and Vazirani [STOC'90]. 2. We devise a randomized algorithm that achieves an expected competitive ratio of 5.356 for maximum weight matching. This finding demonstrates the power of randomization in this context, showing how to beat the tight bound of 3 +2\sqrt{2}~5.828 for deterministic algorithms, obtained by combining the 5.828 upper bound of McGregor [APPROX'05] and the recent 5.828 lower bound of Varadaraja [ICALP'11].
Design, Evaluation and Analysis of Combinatorial Optimization Heuristic Algorithms
Venue: arXiv cs.DS 2012
Year: 2012

Combinatorial optimization is widely applied in a number of areas nowadays. Unfortunately, many combinatorial optimization problems are NP-hard which usually means that they are unsolvable in practice. However, it is often unnecessary to have an exact solution. In this case one may use heuristic approach to obtain a near-optimal solution in some reasonable time. We focus on two combinatorial optimization problems, namely the Generalized Traveling Salesman Problem and the Multidimensional Assignment Problem. The first problem is an important generalization of the Traveling Salesman Problem; the second one is a generalization of the Assignment Problem for an arbitrary number of dimensions. Both problems are NP-hard and have hosts of applications. In this work, we discuss different aspects of heuristics design and evaluation. A broad spectrum of related subjects, covered in this research, includes test bed generation and analysis, implementation and performance issues, local search neighborhoods and efficient exploration algorithms, metaheuristics design and population sizing in memetic algorithm. The most important results are obtained in the areas of local search and memetic algorithms for the considered problems. In both cases we have significantly advanced the existing knowledge on the local search neighborhoods and algorithms by systematizing and improving the previous results. We have proposed a number of efficient heuristics which dominate the existing algorithms in a wide range of time/quality requirements. Several new approaches, introduced in our memetic algorithms, make them the state-of-the-art metaheuristics for the corresponding problems. Population sizing is one of the most promising among these approaches; it is expected to be applicable to virtually any memetic algorithm.
Minimal Proof Search for Modal Logic K Model Checking
Venue: arXiv cs.AI 2012
Year: 2012

Most modal logics such as S5, LTL, or ATL are extensions of Modal Logic K. While the model checking problems for LTL and to a lesser extent ATL have been very active research areas for the past decades, the model checking problem for the more basic Multi-agent Modal Logic K (MMLK) has important applications as a formal framework for perfect information multi-player games on its own. We present Minimal Proof Search (MPS), an effort number based algorithm solving the model checking problem for MMLK. We prove two important properties for MPS beyond its correctness. The (dis)proof exhibited by MPS is of minimal cost for a general definition of cost, and MPS is an optimal algorithm for finding (dis)proofs of minimal cost. Optimality means that any comparable algorithm either needs to explore a bigger or equal state space than MPS, or is not guaranteed to find a (dis)proof of minimal cost on every input. As such, our work relates to A* and AO* in heuristic search, to Proof Number Search and DFPN+ in two-player games, and to counterexample minimization in software model checking.
Towards Tight Bounds for Local Broadcasting
Venue: arXiv cs.NI 2012
Year: 2012

We consider the local broadcasting problem in the SINR model, which is a basic primitive for gathering initial information among $n$ wireless nodes. Assuming that nodes can measure received power, we achieve an essentially optimal constant approximate algorithm (with a $\log^2 n$ additive term). This improves upon the previous best $O(\log n)$-approximate algorithm. Without power measurement, our algorithm achieves $O(\log n)$-approximation, matching the previous best result, but with a simpler approach that works under harsher conditions, such as arbitrary node failures. We give complementary lower bounds under reasonable assumptions.
Recoverability Analysis for Modified Compressive Sensing with Partially Known Support
Venue: arXiv cs.IT 2012
Year: 2012

The recently proposed modified-compressive sensing (modified-CS), which utilizes the partially known support as prior knowledge, significantly improves the performance of recovering sparse signals. However, modified-CS depends heavily on the reliability of the known support. An important problem, which must be studied further, is the recoverability of modified-CS when the known support contains a number of errors. In this letter, we analyze the recoverability of modified-CS in a stochastic framework. A sufficient and necessary condition is established for exact recovery of a sparse signal. Utilizing this condition, the recovery probability that reflects the recoverability of modified-CS can be computed explicitly for a sparse signal with \ell nonzero entries, even though the known support exists some errors. Simulation experiments have been carried out to validate our theoretical results.
Embedding of Virtual Network Requests over Static Wireless Multihop Networks
Venue: arXiv cs.NI 2012
Year: 2012

Network virtualization is a technology of running multiple heterogeneous network architecture on a shared substrate network. One of the crucial components in network virtualization is virtual network embedding, which provides a way to allocate physical network resources (CPU and link bandwidth) to virtual network requests. Despite significant research efforts on virtual network embedding in wired and cellular networks, little attention has been paid to that in wireless multi-hop networks, which is becoming more important due to its rapid growth and the need to share these networks among different business sectors and users. In this paper, we first study the root causes of new challenges of virtual network embedding in wireless multi-hop networks, and propose a new embedding algorithm that efficiently uses the resources of the physical substrate network. We examine our algorithm's performance through extensive simulations under various scenarios. Due to lack of competitive algorithms, we compare the proposed algorithm to five other algorithms, mainly borrowed from wired embedding or artificially made by us, partially with or without the key algorithmic ideas to assess their impacts.
Rule Based Expert System for Diagnosis of Neuromuscular Disorders
Venue: arXiv cs.CY 2012
Year: 2012

In this paper, we discuss the implementation of a rule based expert system for diagnosing neuromuscular diseases. The proposed system is implemented as a rule based expert system in JESS for the diagnosis of Cerebral Palsy, Multiple Sclerosis, Muscular Dystrophy and Parkinson's disease. In the system, the user is presented with a list of questionnaires about the symptoms of the patients based on which the disease of the patient is diagnosed and possible treatment is suggested. The system can aid and support the patients suffering from neuromuscular diseases to get an idea of their disease and possible treatment for the disease.
Understanding the Learners' Actions when using Mathematics Learning Tools
Venue: arXiv cs.CY 2012
Year: 2012

The use of computer-based mathematics tools is widespread in learning. Depending on the way that these tools assess the learner's solution paths, one can distinguish between automatic assessment tools and semi-automatic assessment tools. Automatic assessment tools directly provide all feedback necessary to the learners, while semi-automatic assessment tools involve the teachers as part the assessment process. They are provided with as much information as possible on the learners' interactions with the tool. How can the teachers know how the learning tools were used and which intermediate steps led to a solution? How can the teachers respond to a learner's question that arises while using a computer tool? Little is available to answer this beyond interacting directly with the computer and performing a few manipulations to understand the tools' state. This paper presents SMALA, a web-based logging architecture that addresses these problems by recording, analyzing and representing user actions. While respecting the learner's privacy, the SMALA architecture supports the teachers by offering fine-grained representations of the learners' activities as well as overviews of the progress of a classroom.