Sally A. Goldman

ICML Conference 2006 Conference Paper

MISSL: multiple-instance semi-supervised learning

• Rouhollah Rahmani
• Sally A. Goldman

I&C Journal 2003 Journal Article

Learning from examples with unspecified attribute values

• Sally A. Goldman
• Stephen S. Kwek
• Stephen D. Scott

A challenging problem within machine learning is how to make good inferences from data sets in which pieces of information are missing. While it is valuable to have algorithms that perform well for specific domains, to gain a fundamental understanding of the problem, one needs a “theory” about how to learn with incomplete data. The important contribution of such a theory is not so much the specific algorithmic results, but rather that it provides good ways of thinking about the problem formally. In this paper we introduce the unspecified attribute value (UAV) learning model as a first step towards a theoretical framework for studying the problem of learning from incomplete data in the exact learning framework. In the UAV learning 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 of functions learnable in Angluin’s exact model using the MQ and EQ oracles is also learnable in the UAV model using the MQ and UAV-EQ oracles as long as the counterexamples provided by the UAV-EQ oracle have a logarithmic number of unspecified attributes. We also show that any class learnable in the exact model using the MQ and EQ oracles is also learnable in the UAV model using the UAV-MQ and UAV-EQ oracles as well as an oracle to evaluate a given boolean formula on an example with unspecified attributes. (For some hypothesis classes such as decision trees and unate formulas the evaluation can be done in polynomial time without an oracle.) We also study the learnability of a universal class of decision trees under the UAV model and of DNF formulas under a representation-dependent variation of the UAV model.

ICML Conference 2002 Conference Paper

Content-Based Image Retrieval Using Multiple-Instance Learning

• Qi Zhang
• Sally A. Goldman
• Wei Yu 0003
• Jason E. Fritts

JMLR Journal 2002 Journal Article

Multiple-Instance Learning of Real-Valued Data

• Daniel R. Dooly
• Qi Zhang
• Sally A. Goldman
• Robert A. Amar

The multiple-instance learning model has received much attention recently with a primary application area being that of drug activity prediction. Most prior work on multiple-instance learning has been for concept learning, yet for drug activity prediction, the label is a real-valued affinity measurement giving the binding strength. We present extensions of k -nearest neighbors ( k -NN), Citation- k NN, and the diverse density algorithm for the real-valued setting and study their performance on Boolean and real-valued data. We also provide a method for generating chemically realistic artificial data.

TCS Journal 2002 Journal Article

On learning unions of pattern languages and tree patterns in the mistake bound model

• Sally A. Goldman
• Stephen S. Kwek

We present efficient on-line algorithms for learning unions of a constant number of tree patterns, unions of a constant number of one-variable pattern languages, and unions of a constant number of pattern languages with fixed length substitutions. By fixed length substitutions we mean that each occurrence of variable x i must be substituted by terminal strings of fixed length l(x i ). We prove that if arbitrary unions of pattern languages with fixed length substitutions can be learned efficiently then DNFs are efficiently learnable in the mistake bound model. Since we use a reduction to Winnow, our algorithms are robust against attribute noise. Furthermore, they can be modified to handle concept drift. Also, our approach is quite general and we give results to learn a class that generalizes pattern languages.

ICML Conference 2001 Conference Paper

Multiple-Instance Learning of Real-Valued Data

• Robert A. Amar
• Daniel R. Dooly
• Sally A. Goldman
• Qi Zhang

ICML Conference 2000 Conference Paper

Enhancing Supervised Learning with Unlabeled Data

• Sally A. Goldman
• Yan Zhou

I&C Journal 1998 Journal Article

Noise-Tolerant Parallel Learning of Geometric Concepts

• Nader H. Bshouty
• Sally A. Goldman
• H.David Mathias

We present several efficient parallel algorithms for PAC-learning geometric concepts in a constant-dimensional space. The algorithms are robust even against malicious classification noise of any rate less than 1/2. We first give an efficient noise-tolerant parallel algorithm to PAC-learn the class of geometric concepts defined by a polynomial number of (d−1)-dimensional hyperplanes against an arbitrary distribution where each hyperplane has a slope from a set of known slopes. We then describe how boosting techniques can be used so that our algorithms' dependence onεandδdoes not depend ond. Next, we give an efficient noise-tolerant parallel algorithm to PAC-learn the class of geometric concepts defined by a polynomial number of (d−1)-dimensional hyperplanes (of unrestricted slopes) against a uniform distribution. We then show how to extend our algorithm to learn this class against any (unknown) product distribution. Next we define a complexity measure of any setSof (d−1)-dimensional surfaces that we call thevariantofSand 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 classification noise). Furthermore, we show that the VC-dimension of the class of geometric concepts defined by a single surface of variant one is ∞. Finally, we give an efficient, parallel, noise-tolerant algorithm to PAC-learn any 2-dimensional geometric concept defined by a setSof 1-dimensional surfaces of polynomial length under a uniform distribution.

STOC Conference 1998 Conference Paper

TCP Dynamic Acknowledgment Delay: Theory and Practice (Extended Abstract)

• Daniel R. Dooly
• Sally A. Goldman
• Stephen D. Scott 0001

ICML Conference 1996 Conference Paper

A Theoretical and Empirical Study of a Noise-Tolerant Algorithm to Learn Geormetric Patterns

• Sally A. Goldman
• Stephen D. Scott 0001

STOC Conference 1996 Conference Paper

Noise-Tolerant Distribution-Free Learning of General Geometric Concepts

• Nader H. Bshouty
• Sally A. Goldman
• H. David Mathias
• Subhash Suri
• Hisao Tamaki

FOCS Conference 1990 Conference Paper

Exact Identification of Circuits Using Fixed Points of Amplification Functions (Extended Abstract)

• Sally A. Goldman
• Michael J. Kearns
• Robert E. Schapire

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

FOCS Conference 1989 Conference Paper

Learning Binary Relations and Total Orders (Extended Abstract)

• Sally A. Goldman
• Ronald L. Rivest
• Robert E. Schapire

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

UAI Conference 1986 Conference Paper

A non-iterative maximum entropy algorithm

• Sally A. Goldman
• Ronald L. Rivest

We present a new algorithm for computing the maximum entropy probability distribution satisfying a set of constraints. Unlike preview approaches, our method is integrated with the planning of data collection and tabulation. We show how adding constraints and performing the associated additional tabulations can substantially speed up computation by replacing the usual iterative techniques with a non-iterative computation. We note, however, that the constraints added may contain significantly more variables than any of the original constraints so there may not be enough data to collect meaningful statistics. These extra constraints are shown to correspond to the intermediate tables in Cheeseman's method. Furthermore we prove that acyclic hypergraphs and decomposable models are equivalent, and discuss the similarities and differences between our algorithm and Spiegelhalter's algorithm. Finally, we compare our work to Kim and Pearl's work on singly-connected networks.