Lisa Hellerstein

JAIR Journal 2021 Journal Article

A Tight Bound for Stochastic Submodular Cover

• Lisa Hellerstein
• Devorah Kletenik
• Srinivasan Parthasarathy

We show that the Adaptive Greedy algorithm of Golovin and Krause achieves an approximation bound of (ln(Q/η)+1) for Stochastic Submodular Cover: here Q is the “goal value” and η is the minimum gap between Q and any attainable utility value Q' 2. A bound of 56(ln(Q/η)+1) is implied by work of Im et al. Other bounds for the problem depend on quantities other than Q and η. Our bound restores the original bound claimed by Golovin and Krause, generalizing the well-known (ln m + 1) approximation bound on the greedy algorithm for the classical Set Cover problem, where m is the size of the ground set.

JAIR Journal 2018 Journal Article

Revisiting the Approximation Bound for Stochastic Submodular Cover

• Lisa Hellerstein
• Devorah Kletenik

Deshpande et al. presented a k(ln R + 1) approximation bound for Stochastic Submodular Cover, where k is the state set size, R is the maximum utility of a single item, and the utility function is integer-valued. This bound is similar to the ln Q/(eta+1) bound given by Golovin and Krause, whose analysis was recently found to have an error. Here Q >= R is the goal utility and eta is the minimum gap between Q and any attainable utility Q' < Q. We revisit the proof of the k(ln R + 1) bound of Deshpande et al., fill in the details of the proof of a key lemma, and prove two bounds for real-valued utility functions: k(ln R_1 + 1) and (ln R_E + 1). Here R_1 equals the maximum ratio between the largest increase in utility attainable from a single item, and the smallest non-zero increase attainable from that same item (in the same state). The quantity R_E equals the maximum ratio between the largest expected increase in utility from a single item, and the smallest non-zero expected increase in utility from that same item. Our bounds apply only to the stochastic setting with independent states.

SODA Conference 2014 Conference Paper

Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover

• Amol Deshpande
• Lisa Hellerstein
• Devorah Kletenik

We present approximation algorithms for two problems: Stochastic Boolean Function Evaluation (SBFE) and Stochastic Submodular Set Cover (SSSC). Our results for SBFE problems are obtained by reducing them to SSSC problems through the construction of appropriate utility functions. We give a new algorithm for the SSSC problem that we call Adaptive Dual Greedy. We use this algorithm to obtain a 3-approximation algorithm solving the SBFE problem for linear threshold formulas. We also get a 3-approximation algorithm for the closely related Stochastic Min-Knapsack problem, and a 2-approximation for a natural special case of that problem. In addition, we prove a new approximation bound for a previous algorithm for the SSSC problem, Adaptive Greedy. We consider an approach to approximating SBFE problems using existing techniques, which we call the Q -value approach. This approach easily yields a new result for evaluation of CDNF formulas, and we apply variants of it to simultaneous evaluation problems and a ranking problem. However, we show that the Q -value approach provably cannot be used to obtain a sublinear approximation factor for the SBFE problem for linear threshold formulas or read-once DNF.

JMLR Journal 2009 Journal Article

Exploiting Product Distributions to Identify Relevant Variables of Correlation Immune Functions

• Lisa Hellerstein
• Bernard Rosell
• Eric Bach
• Soumya Ray
• David Page

A Boolean function f is correlation immune if each input variable is independent of the output, under the uniform distribution on inputs. For example, the parity function is correlation immune. We consider the problem of identifying relevant variables of a correlation immune function, in the presence of irrelevant variables. We address this problem in two different contexts. First, we analyze Skewing, a heuristic method that was developed to improve the ability of greedy decision tree algorithms to identify relevant variables of correlation immune Boolean functions, given examples drawn from the uniform distribution (Page and Ray, 2003). We present theoretical results revealing both the capabilities and limitations of skewing. Second, we explore the problem of identifying relevant variables in the Product Distribution Choice (PDC) learning model, a model in which the learner can choose product distributions and obtain examples from them. We prove a lemma establishing a property of Boolean functions that may be of independent interest. Using this lemma, we give two new algorithms for finding relevant variables of correlation immune functions in the PDC model. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

TCS Journal 2007 Journal Article

On PAC learning algorithms for rich Boolean function classes

• Lisa Hellerstein
• Rocco A. Servedio

We give an overview of the fastest known algorithms for learning various expressive classes of Boolean functions in the Probably Approximately Correct (PAC) learning model. In addition to surveying previously known results, we use existing techniques to give the first known subexponential-time algorithms for PAC learning two natural and expressive classes of Boolean functions: sparse polynomial threshold functions over the Boolean cube { 0, 1 } n and sparse GF 2 polynomials over { 0, 1 } n.

ICML Conference 2005 Conference Paper

Why skewing works: learning difficult Boolean functions with greedy tree learners

• Bernard Rosell
• Lisa Hellerstein
• Soumya Ray
• David Page

STOC Conference 2002 Conference Paper

Exact learning of DNF formulas using DNF hypotheses

• Lisa Hellerstein
• Vijay Raghavan 0002

(MATH) We show the following: For any ε < 0, (log n) (3 + ε) -term DNF cannot be polynomial-query learned with membership and strongly proper equivalence queries. For any function f ( n ) ε o [box] (/frac √ n \over log n ) [end-box], m -term DNF formulas cannot be polynomial-query learned by a membership and equivalence query algorithm that uses m … f ( n )-term DNF formulas as hypotheses. Read-thrice DNF formulas are not learnable with membership and proper equivalence queries. log n -term DNF formulas can be polynomial-query learned with membership and proper equivalence queries. (This complements a result of Bshouty, Goldman, Hancock, and Matar stating that [box] √log n [end-box] -term DNF can be so learned in polynomial time . Using purely information theoretic techniques, these results extend and improve what is currently known. (For example, a weaker version of (a) was known only under a barely plausible complexity theoretic assumption, (b) was previously unknown, and (c) was known under the assumption P † NP.)

I&C Journal 1998 Journal Article

Conjunctions of Unate DNF Formulas: Learning and Structure

• Aaron Feigelson
• Lisa Hellerstein

A central topic in query learning is to determine which classes of Boolean formulas are efficiently learnable with membership and equivalence queries. We consider the class R k consisting of conjunctions ofkunate DNF formulas. This class generalizes the class ofk-clause CNF formulas and the class of unate DNF formulas, both of which are known to be learnable in polynomial time with membership and equivalence queries. We prove that R 2 can be properly learned with a polynomial number of polynomial-size membership and equivalence queries, but can be properly learned in polynomial time with such queries if and only if P=NP. Thus the barrier to properly learning R 2 with membership and equivalence queries is computational rather than informational. Few results of this type are known. In our proofs, we use recent results of Hellersteinet al. (1997, J. Assoc. Comput. Mach. 43(5), 840–862), characterizing the classes that are polynomial-query learnable, together with work of Bshouty on the monotone dimension of Boolean functions. We extend some of our results to R k and pose open questions on learning DNF formulas of small monotone dimension. We also prove structural results for R k. We construct, for any fixedk⩾2, a class of functionsfthat cannot be represented by any formula in R k, but which cannot be “easily” shown to have this property. More precisely, for any functionfonnvariables in the class, the value offon any polynomial-size set of points in its domain is not a witness thatfcannot be represented by a formula in R k. Our construction is based on BCH codes.

STOC Conference 1995 Conference Paper

How many queries are needed to learn?

• Lisa Hellerstein
• Krishnan Pillaipakkamnatt
• Vijay Raghavan 0002
• Dawn Wilkins

SODA Conference 1994 Conference Paper

Learning Binary Matroid Ports

• Lisa Hellerstein
• Collette R. Coullard

STOC Conference 1994 Conference Paper

On the power of finite automata with both nondeterministic and probabilistic states (preliminary version)

• Anne Condon
• Lisa Hellerstein
• Samuel Pottle
• Avi Wigderson

FOCS Conference 1994 Conference Paper

PAC Learning with Irrelevant Attributes

• Aditi Dhagat
• Lisa Hellerstein

We consider the problem of learning in the presence of irrelevant attributes in Valiant's PAC model (1984). In the PAC model, the goal of the learner is to produce an approximately correct hypothesis from random sample data. If the number of relevant attributes in the target function is small, it may be desirable to produce a hypothesis that also depends on only a small number of variables. Haussler (1988) previously considered the problem of learning monomials of a small number of variables. He showed that the greedy set cover approximation algorithm can be used as a polynomial-time Occam algorithm for learning monomials on r of n variables. A outputs a monomial on r(ln q+1) variables, where q is the number of negative examples in the sample. We extend this result by showing that there is a polynomial-time Occam algorithm for learning k-term DNF formulas depending on r of n variables that outputs a DNF formula depending on O(r/sup k/log/sup k/q) variables, where q is the number of negative examples in the sample. We also give a polynomial-time Occam algorithm for learning decision lists (sometimes called 1-decision lists) with k alternations. >

STOC Conference 1992 Conference Paper

Learning Arithmetic Read-Once Formulas

• Nader H. Bshouty
• Thomas R. Hancock
• Lisa Hellerstein

FOCS Conference 1992 Conference Paper

Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries

• Howard Aizenstein
• Lisa Hellerstein
• Leonard Pitt

A general technique is developed to obtain nonlearnability results in the model of exact learning from equivalence and membership queries. The technique is applied to show that, assuming NP not=co-NP, there does not exist a polynomial-time membership and equivalence query algorithm for exactly learning read-thrice DNF formulas-boolean formulas in disjunctive normal form where each variable appears at most three times. This result adds evidence to the conjecture that DNF is hard to learn in the membership and equivalence query model. >