The problem of ranking a set of objects given some measure of similarity is one of the most basic in machine learning. Recently Agarwal proposed a method based on techniques in semi-supervised learning utilizing the graph Laplacian. In this work we consider a novel application of this technique to ranking binary choice data and apply it specifically to ranking US Senators by their ideology.

This paper presents a multilayered architecture that enhances the capabilities of current QA systems and allows different types of complex questions or queries to be processed. The answers to these questions need to be gathered from factual information scattered throughout different documents. Specifically, we designed a specialized layer to process the different types of temporal questions. Complex temporal questions are first decomposed into simple questions, according to the temporal relations expressed in the original question. In the same way, the answers to the resulting simple questions are recomposed, fulfilling the temporal restrictions of the original complex question. A novel aspect of this approach resides in the decomposition which uses a minimal quantity of resources, with the final aim of obtaining a portable platform that is easily extensible to other languages. In this paper we also present a methodology for evaluation of the decomposition of the questions as well as the ability of the implemented temporal layer to perform at a multilingual level. The temporal layer was first performed for English, then evaluated and compared with: a) a general purpose QA system (F-measure 65.47% for QA plus English temporal layer vs. 38.01% for the general QA system), and b) a well-known QA system. Much better results were obtained for temporal questions with the multilayered system. This system was therefore extended to Spanish and very good results were again obtained in the evaluation (F-measure 40.36% for QA plus Spanish temporal layer vs. 22.94% for the general QA system).

We propose a number of techniques for obtaining a global ranking from data that may be incomplete and imbalanced -- characteristics almost universal to modern datasets coming from e-commerce and internet applications. We are primarily interested in score or rating-based cardinal data. From raw ranking data, we construct pairwise rankings, represented as edge flows on an appropriate graph. Our statistical ranking method uses the graph Helmholtzian, the graph theoretic analogue of the Helmholtz operator or vector Laplacian, in much the same way the graph Laplacian is an analogue of the Laplace operator or scalar Laplacian. We study the graph Helmholtzian using combinatorial Hodge theory: we show that every edge flow representing pairwise ranking can be resolved into two orthogonal components, a gradient flow that represents the L2-optimal global ranking and a divergence-free flow (cyclic) that measures the validity of the global ranking obtained -- if this is large, then the data does not have a meaningful global ranking. This divergence-free flow can be further decomposed orthogonally into a curl flow (locally cyclic) and a harmonic flow (locally acyclic but globally cyclic); these provides information on whether inconsistency arises locally or globally. An obvious advantage over the NP-hard Kemeny optimization is that discrete Hodge decomposition may be computed via a linear least squares regression. We also investigated the L1-projection of edge flows, showing that this is dual to correlation maximization over bounded divergence-free flows, and the L1-approximate sparse cyclic ranking, showing that this is dual to correlation maximization over bounded curl-free flows. We discuss relations with Kemeny optimization, Borda count, and Kendall-Smith consistency index from social choice theory and statistics.

We propose a family of statistical models for social network evolution over time, which represents an extension of Exponential Random Graph Models (ERGMs). Many of the methods for ERGMs are readily adapted for these models, including maximum likelihood estimation algorithms. We discuss models of this type and their properties, and give examples, as well as a demonstration of their use for hypothesis testing and classification. We believe our temporal ERG models represent a useful new framework for modeling time-evolving social networks, and rewiring networks from other domains such as gene regulation circuitry, and communication networks.

We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by paying certain voters to change their preferences a specified candidate can be made the elections winner? We study this problem for election systems as varied as scoring protocols and Dodgson voting, and in a variety of settings regarding homogeneous-vs.-nonhomogeneous electorate bribability, bounded-size-vs.-arbitrary-sized candidate sets, weighted-vs.-unweighted voters, and succinct-vs.-nonsuccinct input specification. We obtain both polynomial-time bribery algorithms and proofs of the intractability of bribery, and indeed our results show that the complexity of bribery is extremely sensitive to the setting. For example, we find settings in which bribery is NP-complete but manipulation (by voters) is in P, and we find settings in which bribing weighted voters is NP-complete but bribing voters with individual bribe thresholds is in P. For the broad class of elections (including plurality, Borda, k-approval, and veto) known as scoring protocols, we prove a dichotomy result for bribery of weighted voters: We find a simple-to-evaluate condition that classifies every case as either NP-complete or in P.

The Tokyo Metropolitan Government is the largest municipality in Japan and conducts building change identification work. Recently, Tokyo terminated its traditional visual identification work that has been in use for 20 years and shifted to a new automated system. This paper is intended to introduce the Fixed Assets Change Judgment (FACJ) system and its core tool, RealScape. RealScape automatically detects the changes in the height and color of buildings based on three-dimensional (3D) analysis of aerial photographs. It employs a unique pixel-by-pixel stereo processing method and enables the foot-level precision for each building. RealScape detects building changes more accurately than visual judgment operations by humans and reduces the labor costs to one third of the traditional approach and the required judgment duration to about two weeks per 100km2.

Many city governments are under pressure to optimize the utilization of their resources to respond to fire, rescue and medical emergencies. In this paper we describe a simulation-based optimization software called SOFER that learns from a history of emergency requests to optimize the placement of resources and response policies. We describe a two-level random-restart hill climbing approach that yields policies which perform better than the current practice, satisfy the usability constraints, and are sensitive to optimization metrics and population changes. Some of the policies learned by the system give insight into response practices that would otherwise be counterintuitive.

While the concept of learning by demonstration has been around for many years, recent advances in artificial intelligence technology have led to a resurgence of work in the field. We describe the development and application of learning by demonstration technology to support user creation of automated procedures for a rich collaborative planning environment that is in widespread use by the U.S. Army. User feedback and evaluation results show that the technology can be used effectively by the target user community and that it has tremendous potential for improving the speed and quality of performance for a range of critical tasks.

Spacecraft simulation is an integral part of NASA mission planning, real-time mission support, training, and systems engineering. Existing approaches that power these simulations cannot quickly react to the dynamic and complex behavior of the International Space Station (ISS). To address this problem, this paper introduces a unique and efficient method for continuously learning highly accurate models from real-time streaming sensor data, relying on an online learning approach. This approach revolutionizes NASA simulation techniques for space missions by providing models that quickly adapt to real-world feedback without human intervention. A novel regional sliding-window technique for online learning of simulation models is proposed that regionally maintains the most recent data. We also explore a knowledge fusion approach to reduce predictive error spikes when confronted with making predictions in situations that are quite different from training scenarios. We demonstrate substantial error reductions up to 74% in our experimental evaluation on the ISS Electrical Power System and discuss the early deployment of our software in the ISS Mission Control Center (MCC) for ground-based simulations.

Considerable progress has been made over the last 15 years on building adaptive control systems to assist pilots in flying damaged aircraft. Once a pilot has regained control of a damaged aircraft, the next problem is to determine the best site for an emergency landing.  In general, the decision depends on many factors including the actual control envelope of the aircraft, distance to the site, weather en route, characteristics of the approach path, characteristics of the runway or landing site, and emergency facilities at the site.  All of these influence the risk to the aircraft, to the passengers and crew, and to people and property on the ground.  We describe an emergency landing planner that takes these various factors into consideration and proposes possible routes and landing sites to the pilot, ordering them according to estimated risk.   We give an overview of the system architecture and input data, describe our modeling of risk, describe how we search the space of landing sites and routes, and give a preliminary performance assessment for characteristic emergency scenarios using the current research prototype.