The problem of learning linear discriminant concepts can be solved by various mistake-driven update procedures, including the Winnow family of algorithms and the well-known Perceptron algorithm.In this paper we define the general class of quasi-additive algorithms, which includes Perceptron and Winnow as special cases.We give a single proof of convergence that covers much of this class, including both Perceptron and Winnow but also many novel algorithms.Our proof introduces a generic measure of progress that seems to capture much of when and how these algorithms converge.Using this measure, we develop a simple general technique for proving mistake bounds, which we apply to the new algorithms as well as existing algorithms.When applied to known algorithms, our technique "automatically" produces close variants of existing proofs (and we generally obtain the known bounds, to within constants)thus showing, in a certain sense, that these seemingly diverse results are fundamentally isomorphic.

We consider the problem of reconstructing the shape of an object from multiple images related by translations, when only small portions of the object can be observed in each image. Lindenbaum and Bruckstein (1988) have considered this problem in the specific case where the translating object is seen by small sensors, for application to the understanding of insect vision. Their solution is limited by the fact that its run time is exponential in the number of images and sensors. We show that the problem can be solved in time that is polynomial in the number of sensors, but is in fact NP complete when the number of images is unbounded. We therefore consider the special case of convex objects, which we can solve efficiently even when many images are used.

In any storage scheme, there is some trade-off between the space used (size of memory) and access time. However, the nature of this trade-off seems to depend on more than just what is being stored-it also depends the types of queries we consider. We justify this claim by considering a particular memory model and contrast recognition (membership queries) with associative recall. We show that the latter task can require exponentially larger memories even when identical information is stored.

An intelligent agent will often be uncertain about various properties of its environment, and when acting in that environment it will frequently need to quantify its uncertainty. For example, if the agent wishes to employ the expected-utility paradigm of decision theory to guide its actions, it will need to assign degrees of belief (subjective probabilities) to various assertions. Of course, these degrees of belief should not be arbitrary, but rather should be based on the information available to the agent. This paper describes one approach for inducing degrees of belief from very rich knowledge bases, that can include information about particular individuals, statistical correlations, physical laws, and default rules. We call our approach the random-worlds method. The method is based on the principle of indifference: it treats all of the worlds the agent considers possible as being equally likely. It is able to integrate qualitative default reasoning with quantitative probabilistic reasoning by providing a language in which both types of information can be easily expressed. Our results show that a number of desiderata that arise in direct inference (reasoning from statistical information to conclusions about individuals) and default reasoning follow directly from the semantics of random worlds. For example, random worlds captures important patterns of reasoning such as specificity, inheritance, indifference to irrelevant information, and default assumptions of independence. Furthermore, the expressive power of the language used and the intuitive semantics of random worlds allow the method to deal with problems that are beyond the scope of many other nondeductive reasoning systems.

Traditional databases commonly support efficient query and update procedures that operate in time which is sublinear in the size of the database. Our goal in this paper is to take a first step toward dynamic reasoning in probabilistic databases with comparable efficiency. We propose a dynamic data structure that supports efficient algorithms for updating and querying singly connected Bayesian networks. In the conventional algorithm, new evidence is absorbed in O(1) time and queries are processed in time O(N), where N is the size of the network. We propose an algorithm which, after a preprocessing phase, allows us to answer queries in time O(log N) at the expense of O(log N) time per evidence absorption. The usefulness of sub-linear processing time manifests itself in applications requiring (near) real-time response over large probabilistic databases. We briefly discuss a potential application of dynamic probabilistic reasoning in computational biology.

Abstract Motivated by problems that arise in computing degrees of belief , we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences φ and θ , we consider the structures with domain {1, …, N } that satisfy θ , and compute the fraction of them in which φ is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Liogon'kiĭ [24], if there is a non-unary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We extend this result to show that asymptotic conditional probabilities do not always exist for any reasonable notion of limit. Liogon'kiĭ also showed that the problem of deciding whether the limit exists is undecidable. We analyze the complexity of three problems with respect to this limit: deciding whether it is well-defined, whether it exists, and whether it lies in some nontrivial interval. Matching upper and lower bounds are given for all three problems, showing them to be highly undecidable.

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences $\varphi $ and $\theta $, we consider the structures with domain $\{ 1, \ldots ,N\} $ that satisfy $\theta $, and compute the fraction of them in which $\varphi $ is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Līogon’kī[Formula: see text] [Math. Notes Acad. USSR, 6(1969), pp. 856–861] and by Grove, Halpern, and Koller [Res. Rep. RJ 9564, IBM Almaden Research Center, San Jose, CA, 1993], in the general case, asymptotic conditional probabilities do not always exist, and most questions relating to this issue are highly undecidable. These results, however, all depend on the assumption that 9 can use a nonunary predicate symbol. Līogon’kī[Formula: see text] [Math. Notes Acad. USSR, 6 (1969), pp. 856–861] shows that if we condition on formulas $\theta $ involving unary predicate symbols only (but no equality or constant symbols), then the asymptotic conditional probability does exist and can be effectively computed. This is the case even if we place no corresponding restrictions on $\varphi $. We extend this result here to the case where 9 involves equality and constants. We show that the complexity of computing the limit depends on various factors, such as the depth of quantifier nesting, or whether the vocabulary is finite or infinite. We completely characterize the complexity of the problem in the different cases, and show related results for the associated approximation problem.

Modal epistemic logics for many agents sometimes ignore or simplify the distinction between the agents themselves, and the names these agents use when reasoning about each other. We consider problems motivated by practical computer science applications, and show that the simplest theories of naming are often inadequate. The issues we raise are related to some well-known philosophical concerns, such as indexical descriptions, de re knowledge, and the problem of referring to nonexistent objects. However, our emphasis is on epistemic logic as a descriptive tool for distributed systems and artificial intelligence applications, which leads to some nonstandard solutions. The main technical result of this paper is a first-order modal logic, specified both axiomatically and semantically (by a variant of possible-worlds semantics), that is expressive enough to cope with all the difficulties we discuss.

Given a knowledge base KB containing first-order and statistical facts, we consider a principled method, called the random-worlds method, for computing a degree of belief that some formula Phi holds given KB. If we are reasoning about a world or system consisting of N individuals, then we can consider all possible worlds, or first-order models, withdomain {1,...,N} that satisfy KB, and compute thefraction of them in which Phi is true. We define the degree of belief to be the asymptotic value of this fraction as N grows large. We show that when the vocabulary underlying Phi andKB uses constants and unary predicates only, we can naturally associate an entropy with each world. As N grows larger,there are many more worlds with higher entropy. Therefore, we can usea maximum-entropy computation to compute the degree of belief. This result is in a similar spirit to previous work in physics and artificial intelligence, but is far more general. Of equal interest to the result itself are the limitations on its scope. Most importantly, the restriction to unary predicates seems necessary. Although the random-worlds method makes sense in general, the connection to maximum entropy seems to disappear in the non-unary case. These observations suggest unexpected limitations to the applicability of maximum-entropy methods.

Modal epistemic logics for many agents often assume a fixed one-to-one correspondence between agents and the names for agents that occur in the language. This assumption restricts the applicability of any logic because it prohibits, for instance, anonymous agents, agents with many names, named groups of agents, and relative (indexical) reference. Here we examine the principles involved in such cases, and give simple propositional logics that are expressive enough to cope with them all.

Given a knowledge base theta containing first-order and statistical facts, a principled method, called the random-worlds method, for computing a degree of belief that some phi holds given theta is considered. If the domain has size N, then one can consider all possible worlds with domain (1, . . ., N) that satisfy theta and compute the fraction of them in which phi is true. The degree of belief is defined as the asymptotic value of this fraction as N grows large. It is shown that when the vocabulary underlying phi and theta uses constants and unary predicates only, one can in many cases use a maximum entropy computation to compute the degree of belief. Making precise exactly when a maximum entropy calculation can be used turns out to be subtle. The subtleties are explored, and sufficient conditions that cover many of the cases that occur in practice are provided.>

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order formulas. That is, given first-order formulas φ and θ, we consider the number of structures with domain {1,…,N} that satisfy θ, and compute the fraction of them in which φ is true. We then consider what happens to this probability of first-order formulas, except that now we are considering asymptotic conditional probabilities. Although work has been done on special cases of asymptotic conditional probabilities, no general theory has been developed. This is probably due in part to the fact that it has been known that, if there is a binary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We show that in this general case, almost all the questions one might want to ask (such as deciding whether the asymptotic probability exists) are highly undecidable. On the other hand, we show that the situation with unary predicates only is much better. If the vocabulary consists only of unary predicate and constant symbols, it is decidable whether the limit exists, and if it does, there is an effective algorithm for computing it. The complexity depends on two parameters: whether there is a fixed finite vocabulary or an infinite one, and whether there is a bound on the depth of quantifier nesting.