OpenRaiser/Intern-Atlas huggingface dataset:
Lp : A Logic for Statistical Information
Venue: arXiv cs.AI 2013
Year: 2013

This extended abstract presents a logic, called Lp, that is capable of representing and reasoning with a wide variety of both qualitative and quantitative statistical information. The advantage of this logical formalism is that it offers a declarative representation of statistical knowledge; knowledge represented in this manner can be used for a variety of reasoning tasks. The logic differs from previous work in probability logics in that it uses a probability distribution over the domain of discourse, whereas most previous work (e.g., Nilsson [2], Scott et al. [3], Gaifinan [4], Fagin et al. [5]) has investigated the attachment of probabilities to the sentences of the logic (also, see Halpern [6] and Bacchus [7] for further discussion of the differences). The logic Lp possesses some further important features. First, Lp is a superset of first order logic, hence it can represent ordinary logical assertions. This means that Lp provides a mechanism for integrating statistical information and reasoning about uncertainty into systems based solely on logic. Second, Lp possesses transparent semantics, based on sets and probabilities of those sets. Hence, knowledge represented in Lp can be understood in terms of the simple primative concepts of sets and probabilities. And finally, the there is a sound proof theory that has wide coverage (the proof theory is complete for certain classes of models). The proof theory captures a sufficient range of valid inferences to subsume most previous probabilistic uncertainty reasoning systems. For example, the linear constraints like those generated by Nilsson's probabilistic entailment [2] can be generated by the proof theory, and the Bayesian inference underlying belief nets [8] can be performed. In addition, the proof theory integrates quantitative and qualitative reasoning as well as statistical and logical reasoning. In the next section we briefly examine previous work in probability logics, comparing it to Lp. Then we present some of the varieties of statistical information that Lp is capable of expressing. After this we present, briefly, the syntax, semantics, and proof theory of the logic. We conclude with a few examples of knowledge representation and reasoning in Lp, pointing out the advantages of the declarative representation offered by Lp. We close with a brief discussion of probabilities as degrees of belief, indicating how such probabilities can be generated from statistical knowledge encoded in Lp. The reader who is interested in a more complete treatment should consult Bacchus [7].
The Effects of Perfect and Sample Information on Fuzzy Utilities in Decision-Making
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we first consider a Bayesian framework and model the "utility function" in terms of fuzzy random variables. On the basis of this model, we define the "prior (fuzzy) expected utility" associated with each action, and the corresponding "posterior (fuzzy) expected utility given sample information from a random experiment". The aim of this paper is to analyze how sample information can affect the expected utility. In this way, by using some fuzzy preference relations, we conclude that sample information allows a decision maker to increase the expected utility on the average. The upper bound on the value of the expected utility is when the decision maker has perfect information. Applications of this work to the field of artificial intelligence are presented through two examples.
A Decision-Theoretic Model for Using Scientific Data
Venue: arXiv cs.AI 2013
Year: 2013

Many Artificial Intelligence systems depend on the agent's updating its beliefs about the world on the basis of experience. Experiments constitute one type of experience, so scientific methodology offers a natural environment for examining the issues attendant to using this class of evidence. This paper presents a framework which structures the process of using scientific data from research reports for the purpose of making decisions, using decision analysis as the basis for the structure and using medical research as the general scientific domain. The structure extends the basic influence diagram for updating belief in an object domain parameter of interest by expanding the parameter into four parts: those of the patient, the population, the study sample, and the effective study sample. The structure uses biases to perform the transformation of one parameter into another, so that, for instance, selection biases, in concert with the population parameter, yield the study sample parameter. The influence diagram structure provides decision theoretic justification for practices of good clinical research such as randomized assignment and blindfolding of care providers. The model covers most research designs used in medicine: case-control studies, cohort studies, and controlled clinical trials, and provides an architecture to separate clearly between statistical knowledge and domain knowledge. The proposed general model can be the basis for clinical epidemiological advisory systems, when coupled with heuristic pruning of irrelevant biases; of statistical workstations, when the computational machinery for calculation of posterior distributions is added; and of meta-analytic reviews, when multiple studies may impact on a single population parameter.
Simulation Approaches to General Probabilistic Inference on Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

A number of algorithms have been developed to solve probabilistic inference problems on belief networks. These algorithms can be divided into two main groups: exact techniques which exploit the conditional independence revealed when the graph structure is relatively sparse, and probabilistic sampling techniques which exploit the "conductance" of an embedded Markov chain when the conditional probabilities have non-extreme values. In this paper, we investigate a family of "forward" Monte Carlo sampling techniques similar to Logic Sampling [Henrion, 1988] which appear to perform well even in some multiply connected networks with extreme conditional probabilities, and thus would be generally applicable. We consider several enhancements which reduce the posterior variance using this approach and propose a framework and criteria for choosing when to use those enhancements.
Making Decisions with Belief Functions
Venue: arXiv cs.AI 2013
Year: 2013

A primary motivation for reasoning under uncertainty is to derive decisions in the face of inconclusive evidence. However, Shafer's theory of belief functions, which explicitly represents the underconstrained nature of many reasoning problems, lacks a formal procedure for making decisions. Clearly, when sufficient information is not available, no theory can prescribe actions without making additional assumptions. Faced with this situation, some assumption must be made if a clearly superior choice is to emerge. In this paper we offer a probabilistic interpretation of a simple assumption that disambiguates decision problems represented with belief functions. We prove that it yields expected values identical to those obtained by a probabilistic analysis that makes the same assumption. In addition, we show how the decision analysis methodology frequently employed in probabilistic reasoning can be extended for use with belief functions.
Directed Cycles in Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

The most difficult task in probabilistic reasoning may be handling directed cycles in belief networks. To the best knowledge of this author, there is no serious discussion of this problem at all in the literature of probabilistic reasoning so far.
Blind Men and the Elephant: Detecting Evolving Groups In Social News
Venue: arXiv cs.SI 2013
Year: 2013

We propose an automated and unsupervised methodology for a novel summarization of group behavior based on content preference. We show that graph theoretical community evolution (based on similarity of user preference for content) is effective in indexing these dynamics. Combined with text analysis that targets automatically-identified representative content for each community, our method produces a novel multi-layered representation of evolving group behavior. We demonstrate this methodology in the context of political discourse on a social news site with data that spans more than four years and find coexisting political leanings over extended periods and a disruptive external event that lead to a significant reorganization of existing patterns. Finally, where there exists no ground truth, we propose a new evaluation approach by using entropy measures as evidence of coherence along the evolution path of these groups. This methodology is valuable to designers and managers of online forums in need of granular analytics of user activity, as well as to researchers in social and political sciences who wish to extend their inquiries to large-scale data available on the web.
Improved Accuracy and Parallelism for MRRR-based Eigensolvers -- A Mixed Precision Approach
Venue: arXiv cs.NA 2013
Year: 2013

The real symmetric tridiagonal eigenproblem is of outstanding importance in numerical computations; it arises frequently as part of eigensolvers for standard and generalized dense Hermitian eigenproblems that are based on a reduction to tridiagonal form. For its solution, the algorithm of Multiple Relatively Robust Representations (MRRR) is among the fastest methods. Although fast, the solvers based on MRRR do not deliver the same accuracy as competing methods like Divide & Conquer or the QR algorithm. In this paper, we demonstrate that the use of mixed precisions leads to improved accuracy of MRRR-based eigensolvers with limited or no performance penalty. As a result, we obtain eigensolvers that are not only equally or more accurate than the best available methods, but also -in most circumstances- faster and more scalable than the competition.
One-Bit Quantization Design and Adaptive Methods for Compressed Sensing
Venue: arXiv cs.IT 2013
Year: 2013

There have been a number of studies on sparse signal recovery from one-bit quantized measurements. Nevertheless, little attention has been paid to the choice of the quantization thresholds and its impact on the signal recovery performance. This paper examines the problem of one-bit quantizer design for sparse signal recovery. Our analysis shows that the magnitude ambiguity that ever plagues conventional one-bit compressed sensing methods can be resolved, and an arbitrarily small reconstruction error can be achieved by setting the quantization thresholds close enough to the original data samples without being quantized. Note that unquantized data samples are unaccessible in practice. To overcome this difficulty, we propose an adaptive quantization method that adaptively adjusts the quantization thresholds in a way such that the thresholds converges to the optimal thresholds. Numerical results are illustrated to collaborate our theoretical results and the effectiveness of the proposed algorithm.
Constructing Low Star Discrepancy Point Sets with Genetic Algorithms
Venue: arXiv cs.NE 2013
Year: 2013

Geometric discrepancies are standard measures to quantify the irregularity of distributions. They are an important notion in numerical integration. One of the most important discrepancy notions is the so-called \emph{star discrepancy}. Roughly speaking, a point set of low star discrepancy value allows for a small approximation error in quasi-Monte Carlo integration. It is thus the most studied discrepancy notion. In this work we present a new algorithm to compute point sets of low star discrepancy. The two components of the algorithm (for the optimization and the evaluation, respectively) are based on evolutionary principles. Our algorithm clearly outperforms existing approaches. To the best of our knowledge, it is also the first algorithm which can be adapted easily to optimize inverse star discrepancies.
Scheduling Cutting Process for Large Paper Rolls
Venue: arXiv cs.OH 2013
Year: 2013

Paper cutting is a simple process of slicing large rolls of paper, jumbo-reels, into various sub-rolls with variable widths based on demands risen by customers. Since the variability is high due to collected various orders into a pool, the process turns to be production scheduling problem, which requires optimisation so as to minimise the final remaining amount of paper wasted. The problem holds characteristics similar one-dimensional bin-packing problem to some extends and differs with some respects. This paper introduces a modelling attempt as a scheduling problem with an integer programming approach for optimisation purposes. Then, a constructive heuristic algorithm revising one of well-known approaches, called Best-fit algorithm, is introduced to solve the problem. The illustrative examples provided shows the near optimum solution provided with very low complexity .
Temporal Analysis of Activity Patterns of Editors in Collaborative Mapping Project of OpenStreetMap
Venue: arXiv cs.CY 2013
Year: 2013

In the recent years Wikis have become an attractive platform for social studies of the human behaviour. Containing millions records of edits across the globe, collaborative systems such as Wikipedia have allowed researchers to gain a better understanding of editors participation and their activity patterns. However, contributions made to Geo-wikis_wiki-based collaborative mapping projects_ differ from systems such as Wikipedia in a fundamental way due to spatial dimension of the content that limits the contributors to a set of those who posses local knowledge about a specific area and therefore cross-platform studies and comparisons are required to build a comprehensive image of online open collaboration phenomena. In this work, we study the temporal behavioural pattern of OpenStreetMap editors, a successful example of geo-wiki, for two European capital cities. We categorise different type of temporal patterns and report on the historical trend within a period of 7 years of the project age. We also draw a comparison with the previously observed editing activity patterns of Wikipedia.
Binary Hypothesis Testing Game with Training Data
Venue: arXiv cs.IT 2013
Year: 2013

We introduce a game-theoretic framework to study the hypothesis testing problem, in the presence of an adversary aiming at preventing a correct decision. Specifically, the paper considers a scenario in which an analyst has to decide whether a test sequence has been drawn according to a probability mass function (pmf) P_X or not. In turn, the goal of the adversary is to take a sequence generated according to a different pmf and modify it in such a way to induce a decision error. P_X is known only through one or more training sequences. We derive the asymptotic equilibrium of the game under the assumption that the analyst relies only on first order statistics of the test sequence, and compute the asymptotic payoff of the game when the length of the test sequence tends to infinity. We introduce the concept of indistinguishability region, as the set of pmf's that can not be distinguished reliably from P_X in the presence of attacks. Two different scenarios are considered: in the first one the analyst and the adversary share the same training sequence, in the second scenario, they rely on independent sequences. The obtained results are compared to a version of the game in which the pmf P_X is perfectly known to the analyst and the adversary.
Object-Oriented Translation for Programmable Relational System (DRAFT)
Venue: arXiv cs.DB 2013
Year: 2013

The paper introduces the principles of object-oriented translation for target machine which provides executing the sequences of elementary operations on persistent data presented as a set of relations (programmable relational system). The language of this target machine bases on formal operations of relational data model. An approach is given to convert both the description of complex object-oriented data structures and operations on these data, into a description of relational structures and operations on them. The proposed approach makes possible to extend the target relational language with commands allowing data be described as a set of complex persistent objects of different classes. Object views are introduced which allow relational operations be applied to the data of complex objects. It is shown that any operation and method can be executed on any group of the objects without explicit and implicit iterators. Binding of both attributes and methods with their polymorphic implementations are discussed. Classes can be co-used with relations as scalar domains, in referential integrity constraints and in data query operations.
Process, Structure, and Modularity in Reasoning with Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

Computational mechanisms for uncertainty management must support interactive and incremental problem formulation, inference, hypothesis testing, and decision making. However, most current uncertainty inference systems concentrate primarily on inference, and provide no support for the larger issues. We present a computational approach to uncertainty management which provides direct support for the dynamic, incremental aspect of this task, while at the same time permitting direct representation of the structure of evidential relationships. At the same time, we show that this approach responds to the modularity concerns of Heckerman and Horvitz [Heck87]. This paper emphasizes examples of the capabilities of this approach. Another paper [D'Am89] details the representations and algorithms involved.
Bayesian Assessment of a Connectionist Model for Fault Detection
Venue: arXiv cs.AI 2013
Year: 2013

A previous paper [2] showed how to generate a linear discriminant network (LDN) that computes likely faults for a noisy fault detection problem by using a modification of the perceptron learning algorithm called the pocket algorithm. Here we compare the performance of this connectionist model with performance of the optimal Bayesian decision rule for the example that was previously described. We find that for this particular problem the connectionist model performs about 97% as well as the optimal Bayesian procedure. We then define a more general class of noisy single-pattern boolean (NSB) fault detection problems where each fault corresponds to a single :pattern of boolean instrument readings and instruments are independently noisy. This is equivalent to specifying that instrument readings are probabilistic but conditionally independent given any particular fault. We prove: 1. The optimal Bayesian decision rule for every NSB fault detection problem is representable by an LDN containing no intermediate nodes. (This slightly extends a result first published by Minsky & Selfridge.) 2. Given an NSB fault detection problem, then with arbitrarily high probability after sufficient iterations the pocket algorithm will generate an LDN that computes an optimal Bayesian decision rule for that problem. In practice we find that a reasonable number of iterations of the pocket algorithm produces a network with good, but not optimal, performance.
Probabilistic Semantics and Defaults
Venue: arXiv cs.AI 2013
Year: 2013

There is much interest in providing probabilistic semantics for defaults but most approaches seem to suffer from one of two problems: either they require numbers, a problem defaults were intended to avoid, or they generate peculiar side effects. Rather than provide semantics for defaults, we address the problem defaults were intended to solve: that of reasoning under uncertainty where numeric probability distributions are not available. We describe a non-numeric formalism called an inference graph based on standard probability theory, conditional independence and sentences of favouring where a favours b - favours(a, b) - p(a|b) > p(a). The formalism seems to handle the examples from the nonmonotonic literature. Most importantly, the sentences of our system can be verified by performing an appropriate experiment in the semantic domain.
Decision Making with Linear Constraints on Probabilities
Venue: arXiv cs.AI 2013
Year: 2013

Techniques for decision making with knowledge of linear constraints on condition probabilities are examined. These constraints arise naturally in many situations: upper and lower condition probabilities are known; an ordering among the probabilities is determined; marginal probabilities or bounds on such probabilities are known, e.g., data are available in the form of a probabilistic database (Cavallo and Pittarelli, 1987a); etc. Standard situations of decision making under risk and uncertainty may also be characterized by linear constraints. Each of these types of information may be represented by a convex polyhedron of numerically determinate condition probabilities. A uniform approach to decision making under risk, uncertainty, and partial uncertainty based on a generalized version of a criterion of Hurwicz is proposed, Methods for processing marginal probabilities to improve decision making using any of the criteria discussed are presented.
Blind Interference Suppression and Power Adjustment with Alternating Optimization for Cooperative DS-CDMA Networks
Venue: arXiv cs.IT 2013
Year: 2013

This work presents blind joint interference suppression and power allocation algorithms for DS-CDMA networks with multiple relays and decode and forward protocols. A scheme for joint allocation of power levels across the relays subject to group-based power constraints and the design of linear receivers for interference suppression is proposed. A code-constrained constant modulus (CCM) design for the receive filters and the power allocation vectors is devised along with a blind channel estimator. In order to solve the proposed optimization efficiently, an alternating optimization strategy is presented with recursive least squares (RLS)-type algorithms for estimating the parameters of the receiver, the power allocation and the channels. Simulations show that the proposed algorithms obtain significant gains in capacity and performance over existing schemes.
Approximation algorithms for Euler genus and related problems
Venue: arXiv cs.DS 2013
Year: 2013

The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by [Thomassen '89 & '93], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O(sqrt(n))-approximation [Chen, Kanchi, Kanevsky '97] is known even in bounded degree graphs. In this paper we give a polynomial-time algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus poly(g, log(n)). Combined with the upper bound from [Chen, Kanchi, Kanevsky '97], our result also implies a O(n^(1/2 - alpha))-approximation, for some constant alpha>0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a unified fashion, algorithms with approximation ratios of the form poly(OPT, log(n)) for several related problems on bounded degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion problems. Our algorithm and proof of correctness for the crossing number problem is simpler compared to the long and difficult proof in the recent breakthrough by [Chuzhoy 2011], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of form poly(OPT, log(n)). We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown.