Jeffrey C. Jackson

JMLR Journal 2014 Journal Article

New Results for Random Walk Learning

• Jeffrey C. Jackson
• Karl Wimmer

In a very strong positive result for passive learning algorithms, Bshouty et al. showed that DNF expressions are efficiently learnable in the uniform random walk model. It is natural to ask whether the more expressive class of thresholds of parities (TOP) can also be learned efficiently in this model, since both DNF and TOP are efficiently uniform-learnable from queries. However, the time bounds of the algorithms of Bshouty et al. are exponential for TOP. We present a new approach to weak parity learning that leads to quasi-efficient uniform random walk learnability of TOP. We also introduce a more general random walk model and give two positive results in this new model: DNF is efficiently learnable and juntas are efficiently agnostically learnable. [abs] [ pdf ][ bib ] &copy JMLR 2014. ( edit, beta )

I&C Journal 2003 Journal Article

Uniform-distribution attribute noise learnability

• Nader H. Bshouty
• Jeffrey C. Jackson
• Christino Tamon

We study the problem of PAC-learning Boolean functions with random attribute noise under the uniform distribution. We define a noisy distance measure for function classes and show that if this measure is small for a class C and an attribute noise distribution D then C is not learnable with respect to the uniform distribution in the presence of noise generated according to D. The noisy distance measure is then characterized in terms of Fourier properties of the function class. We use this characterization to show that the class of all parity functions is not learnable for any but very concentrated noise distributions D. On the other hand, we show that if C is learnable with respect to uniform using a standard Fourier-based learning technique, then C is learnable with time and sample complexity also determined by the noisy distance. In fact, we show that this style algorithm is nearly the best possible for learning in the presence of attribute noise. As an application of our results, we show how to extend such an algorithm for learning AC 0 so that it handles certain types of attribute noise with relatively little impact on the running time.

STOC Conference 2002 Conference Paper

Learnability beyond AC0

• Jeffrey C. Jackson
• Adam R. Klivans
• Rocco A. Servedio

FOCS Conference 1994 Conference Paper

An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution

• Jeffrey C. Jackson

We present a membership-query algorithm for efficiently learning DNF with respect to the uniform distribution. In fact, the algorithm properly learns the more general class of functions that are computable as a majority of polynomially-many parity functions. We also describe extensions of this algorithm for learning DNF over certain nonuniform distributions and from noisy examples as well as for learning a class of geometric concepts that generalizes DNF. The algorithm utilizes one of Freund's boosting techniques and relies on the fact that boosting does not require a completely distribution-independent weak learner. The boosted weak learner is a nonuniform extension of a Fourier-based algorithm due to Kushilevitz and Mansour (1991). >

STOC Conference 1994 Conference Paper

Weakly learning DNF and characterizing statistical query learning using Fourier analysis

• Avrim Blum
• Merrick L. Furst
• Jeffrey C. Jackson
• Michael J. Kearns
• Yishay Mansour
• Steven Rudich