We consider the problem of training probabilistic conditional random fields (CRFs) in the context of a task where performance is measured using a specific loss function. While maximum likelihood is the most common approach to training CRFs, it ignores the inherent structure of the task's loss function. We describe alternatives to maximum likelihood which take that loss into account. These include a novel adaptation of a loss upper bound from the structured SVMs literature to the CRF context, as well as a new loss-inspired KL divergence objective which relies on the probabilistic nature of CRFs. These loss-sensitive objectives are compared to maximum likelihood using ranking as a benchmark task. This comparison confirms the importance of incorporating loss information in the probabilistic training of CRFs, with the loss-inspired KL outperforming all other objectives.

Cancer kills millions of people each year. From an AI perspective, finding effective treatments for cancer is a high-dimensional search problem characterized by many molecularly distinct cancer subtypes, many potential targets and drug combinations, and a dearth of high quality data to connect molecular subtypes and treatments to responses. The broadening availability of molecular diagnostics and electronic medical records, presents both opportunities and challenges to apply AI techniques to personalize and improve cancer treatment. We discuss these in the context of Cancer Commons, a “rapid learning” community where patients, physicians, and researchers collect and analyze the molecular and clinical data from every cancer patient, and use these results to individualize therapies. Research opportunities include: adaptively-planning and executing individual treatment experiments across the whole patient population, inferring the causal mechanisms of tumors, predicting drug response in individuals, and generalizing these findings to new cases. The goal is to treat each patient in accord with the best available knowledge, and to continually update that knowledge to benefit subsequent patients. Achieving this goal is a worthy grand challenge for AI.

A common problem for companies with strong business growth is that it is hard to find enough experienced staff to support expansion needs. This problem is particular pronounced for operations planners and controllers who must be very highly knowledgeable and experienced with the business domain. This article is a case study of how one of the largest travel agencies in Hong Kong alleviated this problem by using AI to support decision-making and problem-solving so that their planners and controllers can work more effectively and efficiently to sustain business growth while maintaining consistent quality of service. AI is used in a mission critical fleet management system (FMS) that supports the scheduling and management of a fleet of luxury limousines for business travelers. The AI problem was modeled as a constraint satisfaction problem (CSP). The use of AI enabled the travel agency to sign up additional hotel partners, handle more orders and expand their fleet with their existing team of planners and controllers. Using modern web 2.0 architecture and proven AI technology, we were able to achieve low-risk implementation and deployment success with concrete and measurable business benefits.

A geoscientist would be faced with the situation shown on the right of the figure; his task is to deduce the situation shown at the left, along with the processes that were at work and the timeline involved. To accomplish this, a geoscientist first dates a set of rock samples from the present surface, then reasons backward to deduce what process affected the original landform. This is a difficult deduction: geological processes take place over an extremely long period of time, and evidence remaining today is scarce and noisy. Finally, experts in geological dating, like experts in any field, are only human, and can be biased in favor of one theory over another. In the face of these problems, experts form an exhaustive list of possible hypotheses and consider the evidence for and against each one--much like the AI concept of argumentation. Our system to automate this reasoning, Calvin, uses the same argumentation process as experts, comparing the strength of the evidence for and against a set of hypotheses before coming to a conclusion. We collected knowledge about how isotope dating experts reason through interviews with several dozen geoscientists.

Transfer learning aims to solve new learning problems by extracting and making use of the common knowledge found in related domains. A key element of transfer learning is to identify structured knowledge to enable the knowledge transfer. Structured knowledge comes in different forms, depending on the nature of the learning problem and characteristics of the domains. In this article, we describe three of our recent works on transfer learning in a progressively more sophisticated order of the structured knowledge being transferred. We show that optimization methods, and techniques inspired by the concerns of data reuse can be applied to extract and transfer deep structural knowledge between a variety of source and target problems. In our examples, this knowledge spans explicit data labels, model parameters, relations between data clusters and relational action descriptions. 

Constraint propagation is one of the basic forms of inference in many logic-based reasoning systems. In this paper, we investigate constraint propagation for first-order logic (FO), a suitable language to express a wide variety of constraints. We present an algorithm with polynomial-time data complexity for constraint propagation in the context of an FO theory and a finite structure. We show that constraint propagation in this manner can be represented by a datalog program and that the algorithm can be executed symbolically, i.e., independently of a structure. Next, we extend the algorithm to FO(ID), the extension of FO with inductive definitions. Finally, we discuss several applications.

The theoretical limits of 'lossy' data compression algorithms are considered. The complexity of an object as seen by a macroscopic observer is the size of the perceptual code which discards all information that can be lost without altering the perception of the specified observer. The complexity of this macroscopically observed state is the simplest description of any microstate comprising that macrostate. Inference and pattern recognition based on macrostate rather than microstate complexities will take advantage of the complexity of the macroscopic observer to ignore irrelevant noise.

Complexity analysis of planning is problematic. Even very simple planning languages are PSPACE-complete, yet cannot model many simple problems naturally. Many languages with much more powerful features are also PSPACE-complete. It is thus difficult to separate planning languages in a useful way and to get complexity figures that better reflect reality. This paper introduces new methods for complexity analysis of planning and similar combinatorial search problems, in order to achieve more precision and complexity separations than standard methods allow. Padding instances with the solution size yields a complexity measure that is immune to this factor and reveals other causes of hardness, that are otherwise hidden. Further combining this method with limited non-determinism improves the precision, making even finer separations possible. We demonstrate with examples how these methods can narrow the gap between theory and practice.

Sparse coding consists in representing signals as sparse linear combinations of atoms selected from a dictionary. We consider an extension of this framework where the atoms are further assumed to be embedded in a tree. This is achieved using a recently introduced tree-structured sparse regularization norm, which has proven useful in several applications. This norm leads to regularized problems that are difficult to optimize, and we propose in this paper efficient algorithms for solving them. More precisely, we show that the proximal operator associated with this norm is computable exactly via a dual approach that can be viewed as the composition of elementary proximal operators. Our procedure has a complexity linear, or close to linear, in the number of atoms, and allows the use of accelerated gradient techniques to solve the tree-structured sparse approximation problem at the same computational cost as traditional ones using the L1-norm. Our method is efficient and scales gracefully to millions of variables, which we illustrate in two types of applications: first, we consider fixed hierarchical dictionaries of wavelets to denoise natural images. Then, we apply our optimization tools in the context of dictionary learning, where learned dictionary elements naturally organize in a prespecified arborescent structure, leading to a better performance in reconstruction of natural image patches. When applied to text documents, our method learns hierarchies of topics, thus providing a competitive alternative to probabilistic topic models.

This paper presents a Bayesian approach to symbol and phase inference in a phase-unsynchronized digital receiver. It primarily extends [Quinn 2011] to the multi-symbol case, using the variational Bayes (VB) approximation to deal with the combinatorial complexity of the phase inference in this case. The work provides a fully Bayesian extension of the EM-based framework underlying current turbo-synchronization methods, since it induces a von Mises prior on the time-invariant phase parmeter. As a result, we achieve tractable iterative algorithms with improved robustness in low SNR regimes, compared to the current EM-based approaches. As a corollary to our analysis we also discover the importance of prior regularization in elegantly tackling the significant problem of phase ambiguity.