Remarkable success has been achieved in the last few years on some limited machine reading comprehension (MRC) tasks.However, it is still difficult to interpret the predictions of existing MRC models.In this paper, we focus on extracting evidence sentences that can explain or support the answers of multiplechoice MRC tasks, where the majority of answer options cannot be directly extracted from reference documents.Due to the lack of ground truth evidence sentence labels in most cases, we apply distant supervision to generate imperfect labels and then use them to train an evidence sentence extractor.To denoise the noisy labels, we apply a recently proposed deep probabilistic logic learning framework to incorporate both sentence-level and cross-sentence linguistic indicators for indirect supervision.We feed the extracted evidence sentences into existing MRC models and evaluate the end-to-end performance on three challenging multiplechoice MRC datasets: MultiRC, RACE, and DREAM, achieving comparable or better performance than the same models that take as input the full reference document.To the best of our knowledge, this is the first work extracting evidence sentences for multiple-choice MRC.

We have constructed a new "Who-did-What" dataset of over 200,000 fill-in-the-gap (cloze) multiple choice reading comprehension problems constructed from the LDC English Gigaword newswire corpus.The WDW dataset has a variety of novel features.First, in contrast with the CNN and Daily Mail datasets (Hermann et al., 2015) we avoid using article summaries for question formation.Instead, each problem is formed from two independent articles -an article given as the passage to be read and a separate article on the same events used to form the question.Second, we avoid anonymization -each choice is a person named entity.Third, the problems have been filtered to remove a fraction that are easily solved by simple baselines, while remaining 84% solvable by humans.We report performance benchmarks of standard systems and propose the WDW dataset as a challenge task for the community.1

We consider the problem of computing optical flow in monocular video taken from a moving vehicle. In this setting, the vast majority of image flow is due to the vehicle's ego-motion. We propose to take advantage of this fact and estimate flow along the epipolar lines of the egomotion. Towards this goal, we derive a slanted-plane MRF model which explicitly reasons about the ordering of planes and their physical validity at junctions. Furthermore, we present a bottom-up grouping algorithm which produces over-segmentations that respect flow boundaries. We demonstrate the effectiveness of our approach in the challenging KITTI flow benchmark [11] achieving half the error of the best competing general flow algorithm and one third of the error of the best epipolar flow algorithm.

This paper presents a robust stereo-vision-based drivable road detection and tracking system that was designed to navigate an intelligent vehicle through challenging traffic scenarios and increment road safety in such scenarios with advanced driver-assistance systems (ADAS). This system is based on a formulation of stereo with homography as a maximum a posteriori (MAP) problem in a Markov random held (MRF). Under this formulation, we develop an alternating optimization algorithm that alternates between computing the binary labeling for road/nonroad classification and learning the optimal parameters from the current input stereo pair itself. Furthermore, online extrinsic camera parameter reestimation and automatic MRF parameter tuning are performed to enhance the robustness and accuracy of the proposed system. In the experiments, the system was tested on our experimental intelligent vehicles under various real challenging scenarios. The results have substantiated the effectiveness and the robustness of the proposed system with respect to various challenging road scenarios such as heterogeneous road materials/textures, heavy shadows, changing illumination and weather conditions, and dynamic vehicle movements.

This paper proposes a novel method for multivehicle detection and tracking using a vehicle-mounted monocular camera. In the proposed method, the features of vehicles are learned as a deformable object model through the combination of a latent support vector machine (LSVM) and histograms of oriented gradients (HOGs). The detection algorithm combines both global and local features of the vehicle as a deformable object model. Detected vehicles are tracked through a particle filter, which estimates the particles' likelihood by using a detection scores map and template compatibility for both root and parts of the vehicle while considering the deformation cost caused by the movement of vehicle parts. Tracking likelihoods are iteratively used as a priori probability to generate vehicle hypothesis regions and update the detection threshold to reduce false negatives of the algorithm presented before. Extensive experiments in urban scenarios showed that the proposed method can achieve an average vehicle detection rate of 97% and an average vehicle-tracking rate of 86% with a false positive rate of less than 0.26%.

We describe a new approach for phoneme recognition which aims at minimizing the phoneme error rate. Building on structured prediction techniques, we formulate the phoneme recognizer as a linear combination of feature functions. We state a PAC-Bayesian generalization bound, which gives an upper-bound on the expected phoneme error rate in terms of the empirical phoneme error rate. Our algorithm is derived by finding the gradient of the PAC-Bayesian bound and minimizing it by stochastic gradient descent. The resulting algorithm is iterative and easy to implement. Experiments on the TIMIT corpus show that our method achieves the lowest phoneme error rate compared to other discriminative and generative models with the same expressive power.

Many roads made for land vehicles are not totally planar and present uphill and downhill slopes that follow the environment topography. Moreover, the road appearance is often affected by a number of factors in challenging conditions. In this paper, we present an adaptive non-planar road detection and tracking approach which overcomes these difficulties by a piecewise planar road model as well as a Markov Random Field (MRF)-based alternating optimization using belief propagation (BP) on segmented images and a hard conditional Expectation Maximization (EM) algorithm to achieve adaptability and optimality. The proposed framework incorporates image evidence, geometry information, and temporal support such that the graph we build and the well-defined energy minimization formulation can exploit the essence of the roads that is invariant in challenging environments. Experimental results in various real challenging traffic scenes show the effectiveness of the proposed approach.

We explore discriminative training of HMM parameters that directly minimizes the expected error rate. In discriminative training one is interested in training a system to minimize a desired error function, like word error rate, phone error rate, or frame error rate. We review a recent method (McAllester, Hazan and Keshet, 2010), which introduces an analytic expression for the gradient of the expected error-rate. The analytic expression leads to a perceptron-like update rule, which is adapted here for training of HMMs in an online fashion. While the proposed method can work with any type of the error function used in speech recognition, we evaluated it on phoneme recognition of TIMIT, when the desired error function used for training was frame error rate. Except for the case of GMM with a single mixture per state, the proposed update rule provides lower error rates, both in terms of frame error rate and phone error rate, than other approaches, including MCE and large margin. Index Terms: hidden Markov models, online learning, direct error minimization, discriminative training, automatic speech recognition, minimum phone error, minimum frame error 1.

This paper proposes a method for on road detecting and tracking of multi vehicles at nighttime in urban environment. The features of vehicles including root and part filters are learned as a weighted deformable object model through the combination of a latent support vector machine (LSVM) and histograms of oriented gradients (HOG). Detected vehicles are tracked through a particle filter which estimates near optimum likelihoods by calculating the maximum HOG features compatibility for both root and parts of the tracked vehicles. Tracking likelihoods are iteratively used as a priori probability to generate vehicle hypothesis regions. Extensive experiments with close range IR camera in urban scenarios showed that the efficiency of the proposed method for detecting and tracking of multi vehicles at night time.

Comprehensive situational awareness is paramount to the effectiveness of proprietary navigational and higher-level functions of intelligent vehicles. In this paper, we address a graph-based approach for 2D road representation of 3D point clouds with respect to the road topography. We employ the gradient cues of the road geometry to construct a Markov Random Filed (MRF) and implement an efficient belief propagation (BP) algorithm to classify the road environment into four categories, i.e. the reachable region, the drivable region, the obstacle region and the unknown region. The proposed approach can overcome a wide variety of practical challenges, such as sloped terrains, rough road surfaces, rolling/pitching of the host vehicle, etc., and represent the road environment accurately as well as robustly. Experimental results in typical but challenging environments have substantiated that the proposed approach is more sensitive and reliable than the conventional vertical displacements analysis and show superior performance against other local classifiers.

This paper proposes an embedded real time method for detecting and tracking of multiobjects including vehicles, pedestrians, motorbikes and bicycles in urban environment. The features of different objects are learned as a deformable object model through the combination of a latent support vector machine (LSVM) and histograms of oriented gradients (HOG). Laser depth data have been used as a priori to generate objects hypothesis regions and estimate HOG feature pyramid level to reduce the detection time of previously presented algorithm. Detected objects are tracked through a particle filter which fuses the observations from laser map and sequential images. We use the accurate laser data for state predication and use image HOG information for likelihood calculation. The likelihood finds the maximum HOG feature compatibility for both root and parts of the tracked objects to increase tracking accuracy for deformable objects such as pedestrians in crowded scenes. Extensive experiments with urban scenarios showed that the proposed method can improve the detection and tracking in urban environment.

Compositional models provide an elegant formalism for representing the visual appearance of highly variable objects. While such models are appealing from a theoretical point of view, it has been difficult to demonstrate that they lead to performance advantages on challenging datasets. Here we develop a grammar model for person detection and show that it outperforms previous high-performance systems on the PASCAL benchmark. Our model represents people using a hierarchy of deformable parts, variable structure and an explicit model of occlusion for partially visible objects. To train the model, we introduce a new discriminative framework for learning structured prediction models from weakly-labeled data.

We consider latent structural versions of probit loss and ramp loss. We show that these surrogate loss functions are consistent in the strong sense that for any feature map (finite or infinite dimensional) they yield predictors approaching the infimum task loss achievable by any linear predictor over the given features. We also give finite sample generalization bounds (convergence rates) for these loss functions. These bounds suggest that probit loss converges more rapidly. However, ramp loss is more easily optimized and may ultimately be more practical.

We describe a general method for building cascade classifiers from part-based deformable models such as pictorial structures. We focus primarily on the case of star-structured models and show how a simple algorithm based on partial hypothesis pruning can speed up object detection by more than one order of magnitude without sacrificing detection accuracy. In our algorithm, partial hypotheses are pruned with a sequence of thresholds. In analogy to probably approximately correct (PAC) learning, we introduce the notion of probably approximately admissible (PAA) thresholds. Such thresholds provide theoretical guarantees on the performance of the cascade method and can be computed from a small sample of positive examples. Finally, we outline a cascade detection algorithm for a general class of models defined by a grammar formalism. This class includes not only tree-structured pictorial structures but also richer models that can represent each part recursively as a mixture of other parts.

Real-time lane detection and localization is one of the key issues for many intelligent transportation systems. In this paper, we present a lane detection and tracking approach designed to work in challenging environments where lane boundaries may be low-contrast and changeful with noise due to a number of factors such as wear, type, lighting and weather conditions, etc. In the method, a sophisticated cascade lane feature detector is applied to cope with challenging environments at the very beginning of the detection and a weighted graph is subsequently constructed by integrating intensity as well as geometry cues, reflecting the confidence of each pixel as a lane feature. In order to deal with complex road geometry, we employ Catmull-Rom splines to represent lane boundaries and the left and right lane boundaries are estimated separately in a tracking process using particle filter based on the weighted graph. In the proposed framework, unlike most of previous methods we lay a strong emphasis on accurate and effective lane feature detection since the challenges happen in the very first step of lane detection, and accurately detected lane features can be expected to reduce the complexity and difficulty, as well as improve the accuracy of lane detection in the following steps.

This paper presents a vision-based approach with unsupervised learning for robust, accurate and stable detection of the drivable road to deal with autonomous driving in changing environments. This approach is based on a formulation of stereo with homography as a Maximum A Posteriori (MAP) problem in a Markov Random Field (MRF). Under this formulation, we develop an alternating optimization algorithm that alternates between computing the binary labeling and learning the optimal parameters from the stereo pair itself. The labeling is optimized by minimizing a well-defined energy function that consists of matching energy, smoothness energy and tracking energy. The parameters, including nine homography parameters and four MRF parameters, are learned online by applying a hard Expectation Maximization (EM) algorithm to maximize conditional likelihood. The proposed automatic parameter tuning procedure not only improves the accuracy of road detection but also makes the approach adaptive to changing environments without any a priori knowledge of the road. Experimental results show the optimality as well as adaptability of the proposed approach on a wide variety of challenging roads with changing environments.

This paper proposes a novel method for vehicle detection and tracking using a vehicle-mounted monocular camera. In this method, features of vehicles are learned as a deformable object model through the combination of a latent support vector machine (LSVM) and histograms of oriented gradients (HOG). The vehicle detector uses both global and local features as the deformable object model. Detected vehicles are tracked by using a particle filter with integrated likelihoods, such as the probability of vehicles estimated from the deformable object model and the intensity correlation between different picture frames. Tracking likelihoods are iteratively used as the a priori probability for the next frame. The experimental results showed that the proposed method can achieve an average vehicle detection rate of 98% and an average vehicle tracking rate of 87% with a false positive rate of less than 0.3%.

In discriminative machine learning one is interested in training a system to optimize a certain desired measure of performance, or loss. In binary classification one typically tries to minimizes the error rate. But in structured prediction each task often has its own measure of performance such as the BLEU score in machine translation or the intersection-over-union score in PASCAL segmentation. The most common approaches to structured prediction, structural SVMs and CRFs, do not minimize the task loss: the former minimizes a surrogate loss with no guarantees for task loss and the latter minimizes log loss independent of task loss. The main contribution of this paper is a theorem stating that a certain perceptron-like learning rule, involving features vectors derived from loss-adjusted inference, directly corresponds to the gradient of task loss. We give empirical results on phonetic alignment of a standard test set from the TIMIT corpus, which surpasses all previously reported results on this problem.

We describe an object detection system based on mixtures of multiscale deformable part models. Our system is able to represent highly variable object classes and achieves state-of-the-art results in the PASCAL object detection challenges. While deformable part models have become quite popular, their value had not been demonstrated on difficult benchmarks such as the PASCAL data sets. Our system relies on new methods for discriminative training with partially labeled data. We combine a margin-sensitive approach for data-mining hard negative examples with a formalism we call latent SVM. A latent SVM is a reformulation of MI--SVM in terms of latent variables. A latent SVM is semiconvex, and the training problem becomes convex once latent information is specified for the positive examples. This leads to an iterative training algorithm that alternates between fixing latent values for positive examples and optimizing the latent SVM objective function.

We demonstrate unsupervised learning of a stereo vision model involving monocular depth cues (shape from texture cues). We formulate a conditional probability model defining the probability of the right image given the left. This conditional model does not model a probability distribution over images. Maximizing conditional liklihood rather than joint liklihood is similar using a CRF (Conditional Random Field, [6]) rather than an MRF (joint Markov Random Field). The most closely related earlier work seems to be that of Zhang and Seitz [8] who give a method for adapting five parameters of a stereo vision model. In contrast we train highly parameterized monocular depth cues. Also, we avoid the need for independence assumptions through the use of contrastive divergence training — a general method for optimizing CRFs [4]. There is also related work by Saxena et al. on supervised learning of highly parameterized monocular depth cues [1, 2]. Unlike Saxena et al. we train monocular depth cues as part of unsupervised training of a stereo algorithm. Other related work includes that of Scharstein and Pal [7] and Kong and Tao [5] who perform supervised training of stereo algorithms using general CRF methods. We focus on histogram of oriented gradient (HOG) features as a (texture) surface orientation cue. As a surface is tilted away from the camera the edges in the direction of the tilt become foreshortened while the edges orthogonal to the tilt are not. The effect on the edge distribution is shown in the image below where the average HOG feature is shown for regions of tree trunk and forest floor. The cylindrical shape of the tree trunk is clearly indicated by the warping of the HOG feature.

Road detection is a crucial problem for intelligent vehicles and mobile robots. Most of the methods proposed nowadays only achieve reliable results in relatively well-arranged environments. In this paper, we proposed a stereovision-based road boundary detection method by combining homography estimation and MRF-based belief propagation to cope with challenging scenarios such as unstructured roads with unhomogeneous surfaces. In the method, each pixel in the reference image is firstly labeled as ¿road¿ or ¿non-road¿ by minimizing a well defined energy function that accounts for the planar road region. Subsequently, both of the road boundaries are generated using Catmull-Rom splines based on RANdom SAmple Consensus (RANSAC) algorithm with varying road structure models to help the intelligent vehicle understand the structure as well as safe range of current road. In the suggested framework, both intensity and geometry information of road scenarios are used to contain all the regions belonging to the planar road plane, and the left and right road boundaries are generated separately using a robust fitting algorithm to handle different road structures. Therefore, more accurate as well as robust detection of the road can be expected. Experimental results on a wide variety of typical but challenging scenarios have demonstrated the effectiveness of the proposed method.

This paper describes a discriminatively trained, multiscale, deformable part model for object detection. Our system achieves a two-fold improvement in average precision over the best performance in the 2006 PASCAL person detection challenge. It also outperforms the best results in the 2007 challenge in ten out of twenty categories. The system relies heavily on deformable parts. While deformable part models have become quite popular, their value had not been demonstrated on difficult benchmarks such as the PASCAL challenge. Our system also relies heavily on new methods for discriminative training. We combine a margin-sensitive approach for data mining hard negative examples with a formalism we call latent SVM. A latent SVM, like a hidden CRF, leads to a non-convex training problem. However, a latent SVM is semi-convex and the training problem becomes convex once latent information is specified for the positive examples. We believe that our training methods will eventually make possible the effective use of more latent information such as hierarchical (grammar) models and models involving latent three dimensional pose.

LetXandYbe finite nonempty sets and(X,Y) a pair of random variables taking values inX?Y. We consider communication protocols between two parties,AliceandBob, for generatingXandY.Aliceis provided anx?Xgenerated according to the distribution ofX, and is required to send a message toBobin order to enable him to generatey?Y, whose distribution is the same as that ofY|X=x. Both parties have access to a shared random string generated in advance. LetT[X:Y] be the minimum (over all protocols) of the expected number of bitsAliceneeds to transmit to achieve this. We show that I[X:Y] ? T[X:Y] ? I [X:Y] + 2 log2(I[X:Y]+ O(1). We also consider the worst case communication required for this problem, where we seek to minimize the average number of bitsAlicemust transmit for the worst casex?X. We show that the communication required in this case is related to the capacityC(E) of the channelE, derived from(X,Y) , that mapsx?Xto the distribution ofY|X=x. We also show that the required communicationT(E) satisfiesC(E) ?T(E) ?C(E) + 2 log2(C(E)+1) +O(1). Using the first result, we derive a direct-sum theorem in communication complexity that substantially improves the previous such result shown by Jain, Radhakrishnan, and Sen [In Proc. 30th International Colloquium of Automata, Languages and Programming (ICALP), ser. Lecture Notes in Computer Science, vol. 2719. 2003, pp. 300-315]. These results are obtained by employing a rejection sampling procedure that relates the relative entropy between two distributions to the communication complexity of generating one distribution from the other.

We consider the problem of computing a lightest derivation of a global structure using a set of weighted rules. A large variety of inference problems in AI can be formulated in this framework. We generalize A* search and heuristics derived from abstractions to a broad class of lightest derivation problems. We also describe a new algorithm that searches for lightest derivations using a hierarchy of abstractions. Our generalization of A* gives a new algorithm for searching AND/OR graphs in a bottom-up fashion. We discuss how the algorithms described here provide a general architecture for addressing the pipeline problem --- the problem of passing information back and forth between various stages of processing in a perceptual system. We consider examples in computer vision and natural language processing. We apply the hierarchical search algorithm to the problem of estimating the boundaries of convex objects in grayscale images and compare it to other search methods. A second set of experiments demonstrate the use of a new compositional model for finding salient curves in images.

Even in statically typed languages it is useful to have certain invariants checked dynamically. Findler and Felleisen gave an algorithm for dynamically checking expressive higher-order types called contracts. They did not, however, give a semantics of contracts. The lack of a semantics makes it impossible to define and prove soundness and completeness of the checking algorithm. (Given a semantics, a sound checker never reports violations that do not exist under that semantics; a complete checker is – in principle – able to find violations when violations exist.) Ideally, a semantics should capture what programmers intuitively feel is the meaning of a contract or otherwise clearly point out where intuition does not match reality. In this paper we give an interpretation of contracts for which we prove the Findler-Felleisen algorithm sound and (under reasonable assumptions) complete. While our semantics mostly matches intuition, it also exposes a problem with predicate contracts where an arguably more intuitive interpretation than ours would render the checking algorithm unsound. In our semantics we have to make use of a notion of safety (which we define in the paper) to avoid unsoundness. We are able to eliminate the “leakage” of safety into the semantics by changing the language, replacing the original version of unrestricted predicate contracts with a restricted form. The corresponding loss in expressive power can be recovered by making safety explicit as a contract. This can be done either in ad-hoc fashion or by including general recursive contracts . The addition of recursive contracts has far-reaching implications, deeply affecting the formulation of our model and requiring different techniques for proving soundness.

Even in statically typed languages it is useful to have certain invariants checked dynamically. Findler and Felleisen gave an algorithm for dynamically checking expressive higher-order types called contracts. If we postulate soundness (in the sense that whenever a term is accused of violating its contract it really does fail to satisfy it), then their algorithm implies a semantics for contracts. Unfortunately, the implicit nature of the resulting model makes it rather unwieldy.In this paper we demonstrate that a direct approach yields essentially the same semantics without having to refer to contract-checking in its definition. The so-defined model largely coincides with intuition, but it does expose some peculiarities in its interpretation of predicate contracts where a notion of safety (which we define in the paper) "leaks" into the semantics of Findler and Felleisen's original unrestricted predicate contracts.This counter-intuitive aspect of the semantics can be avoided by changing the language, replacing unrestricted predicate contracts with a restricted version. The corresponding loss in expressive power can be recovered by also providing a way of explicitly expressing safety as a contract-either in ad-hoc fashion or, e.g., by including general recursive contracts.

We consider the problem of structured classification, where the task is to predict a label y from an input x, and y has meaningful internal struc- ture. Our framework includes supervised training of Markov random fields and weighted context-free grammars as special cases. We describe an algorithm that solves the large-margin optimization problem defined in [12], using an exponential-family (Gibbs distribution) representation of structured objects. The algorithm is efficient—even in cases where the number of labels y is exponential in size—provided that certain expecta- tions under Gibbs distributions can be calculated efficiently. The method for structured labels relies on a more general result, specifically the ap- plication of exponentiated gradient updates [7, 8] to quadratic programs.

Auctions are becoming an increasingly popular method for transacting business, especially over the Internet. This article presents a general approach to building autonomous bidding agents to bid in multiple simultaneous auctions for interacting goods. A core component of our approach learns a model of the empirical price dynamics based on past data and uses the model to analytically calculate, to the greatest extent possible, optimal bids. We introduce a new and general boosting-based algorithm for conditional density estimation problems of this kind, i.e., supervised learning problems in which the goal is to estimate the entire conditional distribution of the real-valued label. This approach is fully implemented as ATTac-2001, a top-scoring agent in the second Trading Agent Competition (TAC-01). We present experiments demonstrating the effectiveness of our boosting-based price predictor relative to several reasonable alternatives.

This paper gives distribution-free concentration inequalities for the miss- ing mass and the error rate of histogram rules. Negative association meth- ods can be used to reduce these concentration problems to concentration questions about independent sums. Although the sums are independent, they are highly heterogeneous. Such highly heterogeneous independent sums cannot be analyzed using standard concentration inequalities such as Hoeffding’s inequality, the Angluin-Valiant bound, Bernstein’s in- equality, Bennett’s inequality, or McDiarmid’s theorem.

This paper argues that for many algorithms, and static analysis algorithms in particular, bottom-up logic program presentations are clearer and simpler to analyze, for both correctness andcomplexity, than classical pseudo-code presentations. The main technical contribution consists of two theorems which allow, in many cases, the asymptotic running time of a bottom-up logic program to be determined by inspection. It is well known that a datalog program runs inO(nk) time wherekis the largest number of free variables in any single rule. The theorems given here are significantly more refined. A variety of algorithms are presented and analyzed as examples.

We consider the concept of alocalset of inference rules. A local rule set can be automatically transformed into a rule set for which bottom-up evaluation terminates in polynomial time. The local-rule-set transformation gives polynomial-time evaluation strategies for a large variety of rule sets that cannot be given terminating evaluation strategies by any other known automatic technique. This article discusses three new results. First, it is shown that every polynomial-time predicate can be defined by an (unstratified) local rule set. Second, a new machine-recognizable subclass of the local rule sets is identified. Finally, we show that locality, as a property of rule sets, is undecidable in general.

The rule-based bootstrapping introduced by Yarowsky, and its co- training variant by Blum and Mitchell, have met with considerable em- pirical success. Earlier work on the theory of co-training has been only loosely related to empirically useful co-training algorithms. Here we give a new PAC-style bound on generalization error which justifies both the use of confidences — partial rules and partial labeling of the unlabeled data — and the use of an agreement-based objective function as sug- gested by Collins and Singer. Our bounds apply to the multiclass case, i.e., where instances are to be assigned one of

The proofs of "traditional" proof carrying code (PCC) are type-specialized in the sense that they require axioms about a specific type system. In contrast, the proofs of foundational PCC explicitly define all required types and explicitly prove all the required properties of those types assuming only a fixed foundation of mathematics such as higher-order logic. Foundational PCC is both more flexible and more secure than type-specialized PCC.For foundational PCC we need semantic models of type systems on von Neumann machines. Previous models have been either too weak (lacking general recursive types and first-class function-pointers), too complex (requiring machine-checkable proofs of large bodies of computability theory), or not obviously applicable to von Neumann machines. Our new model is strong, simple, and works either in λ-calculus or on Pentiums.

The web contains a large quantity of unstructured information. In many cases, it is possible to heuristically extract structured information, but the resulting databases are "soft": they contain inconsistencies and duplication, and lack unique, consistently-used object identifiers. Examples include large bibliographic databases harvested from raw scientific papers or databases constructed by merging heterogeneous "hard" databases. Here we formally model a soft database as a noisy version of some unknown hard database. We then consider the hardening problem, i.e., the problem of inferring the most likely underlying hard database given a particular soft database. A key feature of our approach is that hardening is global --- many sources of evidence for a given hard fact are taken into account. We formulate hardening as an optimization problem and give a nontrivial nearly linear time algorithm for finding a local optimum. Categories and Subject Descriptors H.4.m [Information Systems]: M...

Both probabilistic context-free grammars (PCFGs) and shift-reduce probabilistic pushdown automata (PPDAs) have been used for language modeling and maximum likelihood parsing. We investigate the precise relationship between these two formalisms, showing that, while they define the same classes of probabilistic languages, they appear to impose different inductive biases.

PAC-Bayesian learning methods combine the informative priors of Bayesian methods with distribution-free PAC guarantees. Building on earlier methods for PAC-Bayesian model selection, this paper presents a method for PAC-Bayesian model averaging. The main result is a bound on generalization error of an arbitrary weighted mixture of concepts that depends on the empirical error of that mixture and the KLdivergence of the mixture from the prior. A simple characterization is also given for the error bound achieved by the optimal weighting. 1

This paper gives PAC guarantees for "Bayesian" algorithms --- algorithms that optimize risk minimization expressions involving a prior probability and a likelihood for the training data. PAC-Bayesian algorithms are motivated by a desire to provide an informative prior encoding information about the expected experimental setting but still having PAC performance guarantees over all IID settings. The PACBayesian theorems given here apply to an arbitrary prior measure on an arbitrary concept space. These theorems provide an alternative to the use of VC dimension in proving PAC bounds for parameterized concepts. 1 INTRODUCTION Much of modern learning theory can be divided into two seemingly separate areas --- Bayesian inference and PAC learning. Both areas study learning algorithms which take as input training data and produce as output a concept or model which can then be tested on test data. In both areas learning algorithms are associated with correctness theorems. PAC correct...

The Horn /spl mu/-calculus is a logic programming language allowing arbitrary nesting of least and greatest fixed points. The Horn /spl mu/-programs can naturally express safety and liveness properties for reactive systems. We extend the set-based analysis of classical logic programs by mapping arbitrary /spl mu/-programs into "uniform" /spl mu/-programs. Our two main results are that uniform /spl mu/-programs express regular sets of trees and that emptiness for uniform /spl mu/-programs is EXPTIME-complete. Hence we have a nontrivial decidable relaxation for the Horn /spl mu/-calculus. In a different reading, the results express a kind of robustness of the notion of regularity: alternating Rabin tree automata preserve the same expressiveness and algorithmic complexity if we extend them with pushdown transition rules (in the same way Buchi extended word automata to canonical systems).

We define a general notion of set-based analysis --- any language whose operational semantics is defined by environment evaluation has a well defined set-based abstraction. This general definition covers both Aiken and Wimmers' type system and Heintze' set-based analysis. Aiken and Wimmers give a nondeterministic exponential time algorithm for their analysis. Heintze gives an O(n3) procedure. We show that this discrepancy is due to the complexity of the case statements analyzed. For polymorphic programs with deep patterns in case statements (as in the Aiken-Wimmers language) we show that the problem of determining type-safety under set-based abstraction is complete for deterministic exponential time. The problem remains complete for deterministic exponential time for programs without let (monovariant programs). However, for monovariant programs in which all patterns in case statements are shallow, as in the Heintze language, type-safety under set-based abstraction is decidable in cubic time. We give five additional theorems which (nearly exhaustively) characterize the time complexity of set-based analysis as a function of the complexity of case statements.

We prove that certain data-flow and control-flow problems are 2NPDA-complete. This means that these problems are in the class 2NPDA and that they are hard for that class. The fact that they are in 2NPDA demonstrates the richness of the class. The fact that they are hard for 2NPDA can be interpreted as evidence they can not be solved in sub-cubic time-the cubic time decision procedure for an arbitrary 2NPDA problem has not been improved since its discovery in 1968.

We present a linear-time algorithm for bounded-type programs that builds a directed graph whose transitive closure gives exactly the results of the standard (cubic-time) Control-Flow Analysis (CFA) algorithm. Our algorithm can be used to list all functions calls from all call sites in (optimal) quadratic time. More importantly, it can be used to give linear-time algorithms for CFA-consuming applications such as:• effects analysis: find the side-effecting expressions in a program.• k-limited CFA: for each call-site, list the functions if there are only a few of them (≤ k) and otherwise output "many".• called-once analysis: identify all functions called from only one call-site.

We investigate set constraints over set expressions with Tarskian functional and relational operations. Unlike the Herbrand constructor symbols used in recent set constraint formalisms, the meaning of a Tarskian function symbol is interpreted in an arbitrary first order structure. We show that satisfiability of Tarskian set constraints is decidable in nondeterministic doubly exponential time. We also give complexity results and open problems for various extensions of the language.

It is well known that complete logical inference is computationally intractable. However, I take the position here that inference is a principle tool in improving efficiency in a wide variety of computations. My case for the pragmatic value of inference is based on technical results concerning bottom up logic programming. The basic intuition behind the value of inference involves the notion of "obvious consequence". In many domains there is a class of questions which can be answered quickly. Pragmatically one is interested in constructing systems that can answer a useful class of questions quickly. Bottom up logic programming provides a flexible paradigm for doing this. I give one particularly startling result which states that a simple syntactic restriction on logic programs yields a simple programming language in which one can define all and only polynominal time decision procedures.

A procedure is given for recognizing sets of inference rules that generate polynomial time decidable inference relations. The procedure can automatically recognize the tractability of the inference rules underlying congruence closure. The recognition of tractability for that particular rule set constitutes mechanical verification of a theorem originally proved independently by Kozen and Shostak. The procedure is algorithmic, rather than heuristic, and the class of automatically recognizable tractable rule sets can be precisely characterized. A series of examples of rule sets whose tractability is nontrivial, yet machine recognizable, is also given. The technical framework developed here is viewed as a first step toward a general theory of tractable inference relations.

A new polynomial time decidable fragment of first order logic is identified, and a general method for using polynomial time inference procedures in knowledge representation systems is presented. The results shown in this paper indicate that a nonstandard “taxonomic” syntax is essential in constructing natural and powerful polynomial time inference procedures. The central role of taxonomic syntax in the polynomial time inference procedures provides technical support for the often-expressed intuition that knowledge is better represented in terms of taxonomic relationships than classical first order formulas. To use the procedures in a knowledge representation system, a “Socratic proof system” is defined, which is complete for first order inference and which can be used as a semi-automated interface to a first order knowledge base.

In this paper we establish new expressiveness results for indeterminate datatlow primitives. We consider split primitives with three differing fairness assumptions and show that they are strictly inequivalent in expressive power. We also show that the ability to announce internal choices enhances the expressive power of two of the primitives. These results are proved using a very crude notion of observation and thus apply in any reasonable theory of process equivalence.

Expressiveness results for indeterminate data flow primitives are established. Choice primitives with three differing fairness assumptions are considered, and it is shown that they are strictly inequivalent in expressive power. It is also shown that the ability to announce choices enhances the expressive power of two of the primitives. These results are proved using a very crude semantics and will thus apply in any reasonable theory of process equivalence.>

A new procedure is presented for growing min-max game trees. In large games, such as chess, decisions must be based on incomplete search trees. The new tree-growth procedure is based on “conspiracy numbers” as a measure of the accuracy of the root minimax value of an incomplete tree. Conspiracy numbers measure the number of leaf nodes whose value must change in order to change the minimax root value by a given amount. Trees are grown in a way that maximizes the conspiracy required to change the root value. The trees grown by this procedure are often deep and narrow. However, if all static values in a game are the same, this new procedure reduces to d-ply search with α-β pruning. Unlike B∗ search, nonuniform growth is achieved without any modification of the static-board evaluator.

We extend the notion of class so that any Boolean combinations of classes is also a class. Boolean classes allow greater precision and conciseness in naming the class of objects governed a particular method. A class can be viewed as a predicate which is either true or false of any given object. Unlike predicates however classes have an inheritance hierarchy which is known at compile time. Boolean classes extend the notion of class, making classes more like predicates, while preserving the compile time computable inheritance hierarchy.