We reminisce and discuss applications of algorithmic probability to a wide range of problems in artificial intelligence, philosophy and technological society. We propose that Solomonoff has effectively axiomatized the field of artificial intelligence, therefore establishing it as a rigorous scientific discipline. We also relate to our own work in incremental machine learning and philosophy of complexity.

In automatic summarization, centrality-as-relevance means that the most important content of an information source, or a collection of information sources, corresponds to the most central passages, considering a representation where such notion makes sense (graph, spatial, etc.). We assess the main paradigms, and introduce a new centrality-based relevance model for automatic summarization that relies on the use of support sets to better estimate the relevant content. Geometric proximity is used to compute semantic relatedness. Centrality (relevance) is determined by considering the whole input source (and not only local information), and by taking into account the existence of minor topics or lateral subjects in the information sources to be summarized. The method consists in creating, for each passage of the input source, a support set consisting only of the most semantically related passages. Then, the determination of the most relevant content is achieved by selecting the passages that occur in the largest number of support sets. This model produces extractive summaries that are generic, and language- and domain-independent. Thorough automatic evaluation shows that the method achieves state-of-the-art performance, both in written text, and automatically transcribed speech summarization, including when compared to considerably more complex approaches.

Support vector machines have attracted much attention in theoretical and in applied statistics. Main topics of recent interest are consistency, learning rates and robustness. In this article, it is shown that support vector machines are qualitatively robust. Since support vector machines can be represented by a functional on the set of all probability measures, qualitative robustness is proven by showing that this functional is continuous with respect to the topology generated by weak convergence of probability measures. Combined with the existence and uniqueness of support vector machines, our results show that support vector machines are the solutions of a well-posed mathematical problem in Hadamard's sense.

We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing: recovering a sparse vector from a few of its Fourier coefficients. We show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP). This implies that M can be recovered from a fixed ("universal") set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error. A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm. Our proof uses Dudley's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.

The ViewGen model of belief ascription assumes that each agent involved in a conversation has a belief space which includes models of what other parties to the conversation believe. The distinctive notion is that a basic procedure, called belief ascription, allows belief spaces to be amalgamated so as to model the updating and augmentation of belief environments. In this paper we extend the ViewGen model to a more general account of reference phenomena, in particular by the notion of a reachable ascription set (RAS) that links intensional objects across belief environments so as to locate the most heuristically plausible referent at a given point in a conversation. The key notion is the location and attachment of entities that may be under different descriptions, the consequent updating of the system's beliefs about other agents by default, and the role in that process of a speaker's and hearer's protocols that ensure that the choice is the appropriate one. An important characteristic of this model is that each communicator considers nothing beyond his own belief space. A conclusion we shall draw is that traditional binary distinctions in this area (like de dicto/de re and attributive/referential) neither classify the examples effectively nor do they assist in locating referents, whereas the single procedure we suggest does both. We also suggest ways in which this analysis can also illuminate other traditional distinctions such as referential and attributive use. The description here is not on an implemented system with results but a theoretical tool to be implemented within an established dialogue platform (such as Wilks et al. 2011).

A critical prerequisite for human-level cognitive systems is having a rich conceptual understanding of the world. We describe a system that learns conceptual knowledge by deep understanding of WordNet glosses. While WordNet is often criticized for having a too fine-grained approach to word senses, the set of glosses do generally capture useful knowledge about the world and encode a substantial knowledge base about everyday concepts. Unlike previous approaches that have built ontologies of atomic concepts from the provided WordNet hierarchies, we construct complex concepts compositionally using description logic and perform reasoning to derive the best classification of knowledge. We view this work as simultaneously accomplishing two goals: building a rich semantic lexicon useful for natural language processing, and building a knowledge base that encodes common-sense knowledge.

Local consistency properties and algorithms for enforcing them are central to the success of Constraint Processing. Recently, we have demonstrated the importance of higher levels of consistency and the effectiveness of their algorithms for solving difficult problems (Karakashian et al. 2010; Woodward et al. 2011). In this paper, we introduce two reformulation techniques for improving the effectiveness of our algorithm for the relational consistency property R (*, m ) C (Karakashian et al. 2010). Both techniques exploit a tree decomposition of the constraint network of a Constraint Satisfaction Problem (CSP), which is a tree embedding of the network. Our first reformulation technique exploits the structure of the decomposition tree and the state of the backtrack search to omit unnecessary steps from our algorithm and improve its performance. Our second contribution is new relational consistency property called T-R (*, m, z ) C that is strictly stronger than R (*, m ) C. This property is achieved by modifying the structure of the constraint network and adding new redundant constraints to the CSP at the intersection of two vertices of the tree decomposition (Rollon and Dechter 2010). We demonstrate the advantages of the proposed two reformulations for finding all the solutions of a CSP using the technique known as Backtracking with Tree Decomposition (BTD) (Jegou and Terrioux 2003).

We explore a symmetry-based reformulation technique which can speed up optimal pathfinding on undirected uniform-cost grid maps by over 30 times. Our offline approach decomposes grid maps into a set of empty rectangles, removing from each all interior nodes and possibly some from along the perimeter. We then add macro-edges between selected pairs of remaining perimeter nodes to facilitate provably optimal traversal through each rectangle. To further speed up search, we also develop a novel online pruning technique. Our algorithm is fast, memory efficient and retains both optimality and completeness during search.

In this paper we describe a reformulation strategy for solving multi-dimensional Constraint Satisfaction Problems (CSPs). This strategy operates by iteratively considering, in isolation, each one of the unidimensional constraints in the problem. It exploits the approximate symmetries identified on the domain values in order to enforce the selected constraint on the simplified problem. This paper uses the game of SET, a combinatorial card game, to motivate and illustrate our strategy. We propose a multi-dimensional constraint model for SET, and describe a basic constraint solver for finding all solutions of an instance of the game. Then, we introduce an algorithm that implements our reformulation strategy, and show that it yields a dramatic reduction of the search effort. Our approach sheds a new light on the dynamic reformulation of CSPs, leading the way to new strategies for effective problem solving. We use the game of SET as a toy problem to illustrate our strategy and explain its operation. We believe that our approach is applicable to more complex domains of scientific and industrial importance, and deserves thorough investigations in the future.

Suppose an agent builds a policy that satisfactorily solves a decision problem; suppose further that some aspects of this policy are abstracted and used as starting point in a new, different decision problem. How can the agent accrue the benefits of the abstract policy in the new concrete problem? In this paper we propose a framework for simultaneous reinforcement learning, where the abstract policy helps start up the policy for the concrete problem, and both policies are refined through exploration. We report experiments that demonstrate that our framework is effective in speeding up policy construction for practical problems.