Principal component analysis (PCA) is widely used for dimensionality reduction, with well-documented merits in various applications involving high-dimensional data, including computer vision, preference measurement, and bioinformatics. In this context, the fresh look advocated here permeates benefits from variable selection and compressive sampling, to robustify PCA against outliers. A least-trimmed squares estimator of a low-rank bilinear factor analysis model is shown closely related to that obtained from an $\ell_0$-(pseudo)norm-regularized criterion encouraging sparsity in a matrix explicitly modeling the outliers. This connection suggests robust PCA schemes based on convex relaxation, which lead naturally to a family of robust estimators encompassing Huber's optimal M-class as a special case. Outliers are identified by tuning a regularization parameter, which amounts to controlling sparsity of the outlier matrix along the whole robustification path of (group) least-absolute shrinkage and selection operator (Lasso) solutions. Beyond its neat ties to robust statistics, the developed outlier-aware PCA framework is versatile to accommodate novel and scalable algorithms to: i) track the low-rank signal subspace robustly, as new data are acquired in real time; and ii) determine principal components robustly in (possibly) infinite-dimensional feature spaces. Synthetic and real data tests corroborate the effectiveness of the proposed robust PCA schemes, when used to identify aberrant responses in personality assessment surveys, as well as unveil communities in social networks, and intruders from video surveillance data.

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.

Structure learning in random fields has attracted considerable attention due to its difficulty and importance in areas such as remote sensing, computational biology, natural language processing, protein networks, and social network analysis. We consider the problem of estimating the probabilistic graph structure associated with a Gaussian Markov Random Field (GMRF), the Ising model and the Potts model, by extending previous work on $l_1$ regularized neighborhood estimation to include the elastic net $l_1+l_2$ penalty. Additionally, we show numerical evidence that the edge density plays a role in the graph recovery process. Finally, we introduce a novel method for augmenting neighborhood estimation by leveraging pair-wise neighborhood union estimates.

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).

Lane changing can increase or impede the flow of vehicular traffic, depending on traffic density and the lane-changing strategies used by individual drivers. We implement and extend the Nagel-Schreckenberg (N-S) traffic model as an agent-based model to investigate lane-changing behavior on a multi-lane roadway, with the goal of determining which lane changing strategies result in the greatest overall traffic flow. We show that in heavier traffic, an aggressive lane changing policy may be beneficial for overall traffic flow.

We propose a novel method for combined Routing and Wave-length Assignment (RWA) in optical networks by reformulation to an equivalent Pseudo-Boolean Satisfiability (PB-SAT) problem. We introduce edge observability variables to represent whether an edge is on the optimal route, combined with either a simple or a hierarchical SAT encoding to select a wavelength for that edge only when the edge is on the route. This translation exponentially reduces the size of the solution space, making it independent of the number of wavelengths per link. We present experimental results for routing instances with up to 3,000 nodes, 15,000 edges, and 2,048 wavelengths per edge, and achieve at least 8 orders of magnitude speedup relative to a previous PB-SAT encoding by Aloul et al., such that the speedup is increasing with the number of nodes and edges in the network, and the number of wavelengths per edge. A portfolio of 4 parallel strategies, each based on the new approach and a different hierarchical encoding, resulted in additional speedup of up to 6 times, and reduced the variability of the run times for large networks.

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.

This paper investigates spatiotemporal interpolation methods for the application of air pollution assessment. The air pollutant of interest in this paper is fine particulate matter PM2.5. The choice of the time scale is investigated when applying the shape function-based method. It is found that the measurement scale of the time dimension has an impact on the interpolation results. Based upon the comparison between the accuracies of interpolation results, the most effective time scale out of four experimental ones was selected for performing the PM2.5 interpolation. The paper also evaluates the population exposure to the ambient air pollution of PM2.5 at the county-level in the contiguous U.S. in 2009. The interpolated county-level PM2.5 has been linked to 2009 population data and the population with a risky PM2.5 exposure has been estimated. The risky PM2.5 exposure means the PM2.5 concentration exceeding the National Ambient Air Quality Standards. The geographic distribution of the counties with a risky PM2.5 exposure is visualized. This work is essential to understanding the associations between ambient air pollution exposure and population health outcomes.

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.