We consider a variation of the problem of combining expert opinions for the situation in which there is no ground truth to use for training. Even though we don't have labeled data, the goal of this work is quite different from an unsupervised learning problem in which the goal is to cluster the data into different groups. Our work is motivated by the application of segmenting a lung nodule in a computed tomography (CT) scan of the human chest. The lack of a gold standard of truth is a critical problem in medical imaging. A variety of experts, both human and computer algorithms, are available that can mark which voxels are part of a nodule. The question is, how to combine these expert opinions to estimate the unknown ground truth. We present the Veritas algorithm that predicts the underlying label using the knowledge in the expert opinions even without the benefit of any labeled data for training. We evaluate Veritas using artificial data and real CT images to which a synthetic nodule has been added, providing a known ground truth.

We define localized content-based image retrieval as a CBIR task where the user is only interested in a portion of the image, and the rest of the image is irrelevant. In this paper we present a localized CBIR system, Accio, that uses labeled images in conjunction with a multiple-instance learning algorithm to first identify the desired object and weight the features accordingly, and then to rank images in the database using a similarity measure that is based upon only the relevant portions of the image. A challenge for localized CBIR is how to represent the image to capture the content. We present and compare two novel image representations, which extend traditional segmentation-based and salient point-based techniques respectively, to capture content in a localized CBIR setting.

Image segmentation is a fundamental step in many computer vision applications. Generally, the choice of a segmentation algorithm, or parameterization of a given algorithm, is selected at the application level and fixed for all images within that application. Our goal is to create a stand-alone method to evaluate segmentation quality. Stand-alone methods have the advantage that they do not require a manually-segmented reference image for comparison, and can therefore be used for real-time evaluation. Current stand-alone evaluation methods often work well for some types of images, but poorly for others. We propose a meta-evaluation method in which any set of base evaluation methods are combined by a machine learning algorithm that coalesces their evaluations based on a learned weighting function, which depends upon the image to be segmented. The training data used by the machine learning algorithm can be labeled by a human, based on similarity to a human-generated reference segmentation, or based upon system-level performance. Experimental results demonstrate that our method performs better than the existing stand-alone segmentation evaluation methods.

Using prior knowledge about object(s) is greatly beneficial for accurate image segmentation. In this paper, we present an image segmentation method that performs segmentation using a set of user provided object templates. For the object templates, we call the salient points in the object the characteristic points of the object. Based on the correspondence between the salient points of an arbitrary image and the characteristic points of the objects, object templates are mapped onto the image as bit masks. All templates for the same object are combined to generate the final object/background segmentation. Experiments show that this method can create good segmentations.

There has been much work on applying multiple-instance (MI) learning to content-based image retrieval (CBIR) where the goal is to rank all images in a known repository using a small labeled data set. Most existing MI learning algorithms are non-transductive in that the images in the repository serve only as test data and are not used in the learning process. We present MISSL (Multiple-Instance Semi-Supervised Learning) that transforms any MI problem into an input for a graph-based single-instance semi-supervised learning method that encodes the MI aspects of the problem simultaneously working at both the bag and point levels. Unlike most prior MI learning algorithms, MISSL makes use of the unlabeled data.

We present Mi-Winnow, a new multiple-instance learning (MIL) algorithm that provides a new technique to convert MIL data into standard supervised data. In MIL each example is a collection (or bag) of d-dimensional points where each dimension corresponds to a feature. A label is provided for the bag, but not for the individual points within the bag. Mi-Winnow is different from existing multiple-instance learning algorithms in several key ways. First, Mi-Winnow allows each image to be converted into a bag in multiple ways to create training (and test) data that varies in both the number of dimensions per point, and in the kind of features used. Second, instead of learning a concept defined by a single point-and-scaling hypothesis, Mi-Winnow allows the underlying concept to be described by combining a set of separators learned by Winnow. For content-based image retrieval applications, such a generalized hypothesis is important since there may be different ways to recognize which images are of interest

Salient points are locations in an image where there is a significant variation with respect to a chosen image feature. Since the set of salient points in an image capture important local characteristics of that image, they can form the basis of a good image representation for content-based image retrieval (CBIR). The features for a salient point should represent the local characteristic of that point so that the similarity between features indicates the similarity between the salient points. Traditional uses of salient points for CBIR assign features to a salient point based on the image features of all pixels in a window around that point. However, since salient points are often on the boundary of objects, the features assigned to a salient point often involve pixels from different objects. In this paper, we propose a CBIR system that uses a novel salient point method that both reduces the number of salient points using a segmentation as a filter, and also improves the representation so that it is a more faithful representation of a single object (or portion of an object) that includes information about its surroundings. We also introduce an improved Expectation Maximization-Diverse Density (EM-DD) based multiple-instance learning algorithm. Experimental results show that our CBIR techniques improve retrieval performance by 5%-11% as compared with current methods.

For many machine learning applications it is important to develop algorithms that use both labeled and unlabeled data. We present democratic colearning in which multiple algorithms instead of multiple views enable learners to label data for each other. Our technique leverages off the fact that different learning algorithms have different inductive biases and that better predictions can be made by the voted majority. We also present democratic priority sampling, a new example selection method for active learning.

We present a new multiple-instance (MI) learning technique (EM(cid:173) DD) that combines EM with the diverse density (DD) algorithm. EM-DD is a general-purpose MI algorithm that can be applied with boolean or real-value labels and makes real-value predictions. On the boolean Musk benchmarks, the EM-DD algorithm without any tuning significantly outperforms all previous algorithms. EM-DD is relatively insensitive to the number of relevant attributes in the data set and scales up well to large bag sizes. Furthermore, EM(cid:173) DD provides a new framework for MI learning, in which the MI problem is converted to a single-instance setting by using EM to estimate the instance responsible for the label of the bag.

We study an on-line problem that is motivated by the networking problem of dynamically adjusting of acknowledgments in the Transmission Control Protocol (TCP). We provide a theoretical model for this problem in which the goal is to send acks at a time that minimize a linear combination of the cost for the number of acknowledgments sent and the cost for the additional latency introduced by delaying acknowledgments. To study the usefulness of applying packet arrival time prediction to this problem, we assume there is an oracle that provides the algorithm with the times of the next L arrivals, for some L ≥ 0. We give two different objective functions for measuring the cost of a solution, each with its own measure of latency cost. For each objective function we first give an O(n 2 ) -time dynamic programming algorithm for optimally solving the off-line problem. Then we describe an on-line algorithm that greedily acknowledges exactly when the cost for an acknowledgment is less than the latency cost incurred by not acknowledging. We show that for this algorithm there is a sequence of n packet arrivals for which it is Ω (***)-competitive for the first objective function, 2-competitive for the second function for L = 0, and 1-competitivefor the second function for L = 1. Next we present a second on-line algorithm which is a slight modification of the first, and we prove that it is 2-competitive for both objective functions for all L . We also give lower bounds on the competitive ratio for any deterministic on-line algorithm. These results show that for each objective function, at least one of our algorithms is optimal. Finally, we give some initial empirical results using arrival sequences from real network traffic where we compare the two methods used in TCP for acknowledgment delay with our two on-line algorithms. In all cases we examine performance with L = 0 and L = 1.

WQ study an on-line problem that is motivated by the networking problem of dynamically adjusting delays of acknowlcdgmcnts in the Transmission Control Protocol (TCP).The thcoroticnl problem we study is the following.There is a scqucnco of n packet arrival times .4= (or,. . ., an) and a look-nhoad coefficient L, The goal is to partition A into 1; subsequences orroe,. . ., a~: (where a subsequence end is deilncd by an acknowledgment) that minimizes a linear combination of the cost for the number of acknowledgments sent and the cost for the additional latency introduced by delaylng acknowledgments.At each arrival, an oracle provides the algorithm with the times of the next L arrivals.First we give an 0(n*) dynamic programming algorithm for optimally solving the off-line problem.Then we deacribc an on-line algorithm that greedily acknowledges exactly when the cost for an acknowledgment is less than the latency cost obtained by not acknowledging.We show that for this algorithm there ls a sequence of n packet arrivals for which it is S-l (fi) -competitive.Next we present a second on-line algorithm which is a slight modification of the first that we prove is 2-competitive.Let Copt be the cost of the optimal solution and let CA be the cost of the solution produced by algorithm A. We then show that for any on-line algorithm A with any constant look-ahead L, CA > SC+-c where c is a factor that can be made arbitrarily small with rcnpcct to Capt.Thus, in the worst case, our result for L = 0 IQ the hcst possible even for on-line algorithms that can use nny constant look-ahead.We then give some initial empirical results using arrival sequences from real network traffic where we compare the two methods used in TCP for acknowledgment delay with our two on-line algorithms.In all cases we examine performance mitli L = 0 and L = 1, Finally, we consider an alternate dcilnition for the latency cost in our objective function, *Supported in part by NSF NY1 Grant CC%9357707 with mntching funds provfdcd by WUTA.

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ℛ d for fixed d . More specifically, let 𝒯 be any set of s halfspaces. Let x =(x 1 , …, x d ) be an arbitrary point in ℛ d . With each t ∈ 𝒯 we associate a boolean indicator function I t (x) which is 1 if and only if x is in the halfspace t . The concept class, 𝒞 d s , that we study consists of all concepts formed by any Boolean function over I t1 , …, I ts for t i ∈ 𝒯. This class is much more general than any geometric concept class known to be PAC-learnable. Our results can be extended easily to learn efficiently any Boolean combination of a polynomial number of concepts selected from any concept class 𝒞 over ℛ d given that the VC-dimension of 𝒞 has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from 𝒞 consistent with a given set of labeled examples. We also present a statistical query version of our algorithm that can tolerate random classification noise. Finally we present a generalization of the standard ε-net result of Haussler and Welzl [1987] and apply it to give an alternative noise-tolerant algorithm for d = 2 based on geometric subdivisions.

We first present an algorithm that uses membership and equivalence queries to exactly identify a discretized geometric concept defined by the union of m axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. This algorithm receives at most md counterexamples and uses time and membership queries polynomial in m and log n for any constant d. Furthermore, all equivalence queries can be formulated as the union of O(md log m) axis-parallel boxes. Next, we show how to extend our algorithm to efficiently learn, from only equivalence queries, any discretized geometric concept generated from any number of halfspaces with any number of known (to the learner) slopes in a constant dimensional space. In particular, our algorithm exactly learns (from equivalence queries only) unions of discretized axis-parallel boxes in constant dimensional space in polynomial time. Furthermore, this equivalence query only algorithm can be modified to handle a polynomial number of lies in the counterexamples provided by the environment. Finally, we introduce a new complexity measure that better captures the complexity of the union of m boxes than simply the number of boxes and the dimension. Our new measure, $\sigma$, is the number of segments in the target, where a segment is a maximum portion of one of the sides of the target that lies entirely inside or entirely outside each of the other halfspaces defining the target. We present a modification of our first algorithm that uses time and queries polynomial in $\sigma$ and log n. In fact, the time and queries (both membership and equivalence) used by this single algorithm are polynomial for eitherm or d constant.

) Sally A. Goldman Dept. of Computer Science Washington University St. Louis, MO 63130-4899 [email protected] Stephen S. Kwek Dept. of Computer Science Washington University St. Louis, MO 63130-4899 [email protected] Stephen D. Scott Dept. of Computer Science Washington University St. Louis, MO 63130-4899 [email protected] Abstract We introduce the UAV learning model in which some of the attributes in the examples are unspecified. In our model, an example x is classified positive (resp., negative) if all possible assignments for the unspecified attributes result in a positive (resp., negative) classification. Otherwise the classification given to x is "?" (for unknown). Given an example x in which some attributes are unspecified, the oracle UAV-MQ responds with the classification of x. Given a hypothesis h, the oracle UAV-EQ returns an example x (that could have unspecified attributes) for which h(x) is incorrect. We show that any class learnable in the exact model using the...

Goldberg,Goldman, and Scott demonstrated how the problem of recognizing a landmark from a one-dimensional visual image can be mapped to that of learning a one-dimensional geometric pattern and gave a PAC algorithm to learn that class.We present an on-line agnostic learning algorithm for learning the class of one-dimensional geometric patterns.Since, when moving from the processed visual image to a one-dimensional pattern some key information is lost, we define a class of two-dimensional geometric patterns for which the important features from the visual image are incorporated in the geometric pattern, and show how to extend our agnostic learning algorithm to this class of two-dimensional patterns.Prnllissiofl lo InnLc digltnl!l~nrd copies ofall or p;m ofllli\ tll;~ir'r~i~l lb, penonnl or cl~wsroom wsc is ~I-mli'd w~tlwut I>c prob &d th;~r 111~ cop<\ arc IMM made or distribukd IOr profit or commcrc~~~l .~tl\x~lt;~gc.tile copyrlglit nolice.Ihe liilc oflhc pul~lic;llio~l and iLv J;kIc ;nppc;kr.:III~ llollcc jl: giwn that copyrighl is hy pmn~~on ofthe ,\c'kl.IIK '1'0 copy OLIIC~W~?.~'. 10 rrpuhlirh.10 posl 01) wvm or lo rtxilstrihulc IO 11~15.rqutrcs hpcClliC pemlission and/or Ibe ( 'OL.7' 97 Naslnille.Tcnncsec.USA Copyright I997 i\Ckl O-R9791 -89 I -(v97'7..$? 50

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over Rd for fixed d.

We introduce a new model for learning with membership queries in which queries near the boundary of a target concept may receive incorrect or "don't care" responses. In partial compensation, we assume the distribution of examples has zero probability mass on the boundary region. The motivation behind this model is that the reason for the incorrect (or "don't care") response is that these examples are extremely rare in practice. Thus, it does not matter how the learner classifies them. We present several positive results in this new model. We show how to learn the intersection of two halfspaces when membership queries near the boundary may be answered incorrectly. Our algorithm is an extension of an algorithmof Baum [6, 5] which learns intersections of two homogeneous halfspaces in the PAC-with-membership-queries model. We also describe algorithms for learning several subclasses of monotone DNF formulas. 1 Introduction In most of the theoretical work in concept learning it is assumed t...

We present several efficient parallel algorithms for PAC-learning geometric concepts in a constantdimensional space that are robust even against malicious misclassification noise of any rate less than 1/2.In particular we consider the class of geometric concepts defined by a polynomial number of (d -1)-dimensional hyperplanes against an arbitrary distributionwhere each hyperplane has a slope from a set of known slopes, and the class of geometric concepts defined by a polynomial number of (d -1)-dimensional hyperplanes (of unrestricted slopes) against a product distribution.Next we define a complexity measure of any set S of (d-1)-dimensional surfaces that we call the variant of S and prove that the class of geometric concepts defined by surfaces of polynomial variant can be efficiently learned in parallel under a product distribution (even under malicious misclassification noise).Finally, we describe how boosting techniques can be used so that our algorithms' dependence one and 6 does not depend on d.

One view of computational learning theory is that of a learner acquiring the knowledge of a teacher. We introduce a formal model of learning capturing the idea that teachers may have gaps in their knowledge. The goal of the learner is still to acquire the knowledge of the teacher, but now the learner must also identify the gaps. This is the notion of learning from a consistently ignorant teacher. We consider the impact of knowledge gaps on learning, for example, monotone DNF and d-dimensional boxes, and show that learning is still possible. Negatively, we show that knowledge gaps make learning conjunctions of Horn clauses as hard as learning DNF. We also present general results describing when known learning algorithms can be used to obtain learning algorithms using a consistently ignorant teacher.

Developing the ability to recognize a landmark from a visual image of a robot's current location is a fundamental problem in robotics. We consider the problem of PAC-learning the concept class of geometric patterns where the target geometric pattern is a configuration of k points in the real line. Each instance is a configuration of n points on the real line, where it is labeled according to whether or not it visually resembles the target pattern.

We present two algorithms that use membership and equivalence queries to exactly identify the concepts given by the union of s discretized axis-parallel boxes in d-dimensional discretized Euclidean space where there are n discrete values that each coordinate can have. The first algorithm receives at most sd counterexamples and uses time and membership queries polynomial in s and logn for any d constant. Further, all equivalence queries made can be formulated as the union of O(sdlogs) axis parallel boxes.

A number of efficient learning algorithms achieve exact identification of an unknown function from some class using membership and equivalence queries. Using a standard transformation such algorithms can easily be converted to on-line learning algorithms that use membership queries. Under such a transformation the number of equivalence queries made by the query algorithm directly corresponds to the number of mistakes made by the on-line algorithm. In this paper we consider several of the natural classes known to be learnable in this setting, and investigate the minimum number of equivalence queries with accompanying counterexamples (or equivalently the minimum number of mistakes in the on-line model) that can be made by a learning algorithm that makes a polynomial number of membership queries and uses polynomial computation time. We are able both to reduce the number of equivalence queries used by the previous algorithms and often to prove matching lower bounds. As an example, consider...

We introduce a formal model of teaching in which the teacher is tailored to a particular learner, yet the teaching protocol is designed so that no collusion is possible.Not surprisingly, such a model remedies the nonintuitive aspects of other models in which the teacher must successfully teach any consistent learner.We prove that any class that can be exactly identified by a polynomial-time algorithm with access to a very rich set of examplebased queries is teachable by a computationally unbounded teacher and a polynomial-time learner.In addition, we present other general results relating this model of teaching to various previous results.We also consider the problem of designing teacher/learner pairs in which both the teacher and learner are polynomial-time algorithms and describe teacher/learner pairs for the classes of decision lists and Horn sentences.

Abstract. In this paper we demonstrate how weighted majority voting with multiplicative weight updating can be applied to obtain robust algorithms for learning binary relations. We first present an algorithm that obtains a nearly optimal mistake bound but at the expense of using exponential computation to make each prediction. However, the time complexity of our algorithm is significantly reduced from that of previously known algorithms that have comparable mistake bounds. The second algorithm we present is a polynomial time algorithm with a non-optimal mistake bound. Again the mistake bound of our second algorithm is significantly better than previous bounds proven for polynomial time algorithms. A key contribution of our work is that we define a "non-pure " or noisy binary relation and then by exploiting the robustness of weighted majority voting with respect to noise, we show that both of our algorithms can learn non-pure relations. These provide the first algorithms that can learn non-pure binary relations.

In this paper a new technique is described for exactly identifying certain classes of read-once Boolean formulas. The method is based on sampling the input-output behavior of the target formula on a probability distribution that is determined by the fixed point of the formula’s amplification function (defined as the probability that a one is output by the formula when each input bit is one independently with probability p). By performing various statistical tests on easily sampled variants of the fixed-point distribution, it is possible to efficiently infer all structural information about any logarithmic-depth formula (with high probability). Results are applied to prove the existence of short universal identification sequences for large classes of formulas. Also described are extensions of these algorithms to handle high rates of noise, and to learn formulas of unbounded depth in Valiant’s model with respect to specific distributions.

The problem of learning a binary relation between two sets of objects or between a set and itself is studied. This paper represents a binary relation between a set of size n and a set of size m as an $n \times m$ matrix of bits whose $(i,j)$ entry is 1 if and only if the relation holds between the corresponding elements of the two sets. Polynomial prediction algorithms are presented for learning binary relations in an extended on-line learning model, where the examples are drawn by the learner, by a helpful teacher, by an adversary, or according to a uniform probability distribution on the instance space. The first part of this paper presents results for the case in which the matrix of the relation has at most k row types. It presents upper and lower bounds on the number of prediction mistakes any prediction algorithm makes when learning such a matrix under the extended on-line learning model. Furthermore, it describes a technique that simplifies the proof of expected mistake bounds against a randomly chosen query sequence. In the second part of this paper the problem of learning a binary relation that is a total order on a set is considered. A general technique using a fully polynomial randomized approximation scheme (fpras) to implement a randomized version of the halving algorithm is described. This technique is applied to the problem of learning a total order, through the use of an fpras for counting the number of extensions of a partial order, to obtain a polynomial prediction algorithm that with high probability makes at most $n\lg n + (\lg e)\lg n$ mistakes when an adversary selects the query sequence. The case in which a teacher or the learner selects the query sequence is also considered

We consider the problem of learning k-term DNF formulas using equivalence queries and incomplete membership queries as defined by Angluin and Slonim. We demonstrate that this model can be applied to non-monotone classes. Namely, we describe a polynomial-time algorithm that constructs a k-term DNF formula representationally equivalent to the target using incomplete membership queries and equivalence queries from the class of DNF formulas.

A technique for exactly identifying certain classes of read-once Boolean formulas is introduced. The method is based on sampling the input-output behavior of the target formula on a probability distribution which is determined by the fixed point of the formula's amplification function (defined as the probability that a 1 is output by the formula when each input bit is 1 independently with probability p). By performing various statistical tests on easily sampled variants of the fixed-point distribution, it is possible to infer efficiently all structural information about any logarithmic-depth target family (with high probability). The results are used to prove the existence of short universal identification sequences for large classes of formulas. Extensions of the algorithms to handle high rates of noise and to learn formulas of unbounded depth in L.G. Valiant's (1984) model with respect to specific distributions are described.>

The problem of designing polynomial prediction algorithms for learning binary relations is studied for an online model in which the instances are drawn by the learner, by a helpful teacher, by an adversary, or according to a probability distribution on the instance space. The relation is represented as an n*m binary matrix, and results are presented when the matrix is restricted to have at most k distinct row types, and when it is constrained by requiring that the predicate form a total order.>

ISIS IS an experimental system for graphically manlpulatmg a database The system 1s based on a simply specified high-level semantic data model It demonstrates the capablbtles of a workstation environment by mtegratmg three aspects of database programming m one graphical setting Namely, it permits database constructlon and modification, it allows browsing at the schema and data levels, and provides a graphical query language In all of these activities it maintains uniform graphlcal representations and consistent user mteractlon techniques