On Learning Thresholds of Parities and Unions of Rectangles in Random Walk Models

Details On Learning Thresholds of Parities and Unions of Rectangles in Random Walk Models On Learning Thresholds of Parities and Unions of Rectangles in Random Walk Models

2006-05-11

arxiv.org/abs/cs/0605048v1

Computer Science

Learning

Scientific paper

In a recent breakthrough, [Bshouty et al., 2005] obtained the first passive-learning algorithm for DNFs under the uniform distribution. They showed that DNFs are learnable in the Random Walk and Noise Sensitivity models. We extend their results in several directions. We first show that thresholds of parities, a natural class encompassing DNFs, cannot be learned efficiently in the Noise Sensitivity model using only statistical queries. In contrast, we show that a cyclic version of the Random Walk model allows to learn efficiently polynomially weighted thresholds of parities. We also extend the algorithm of Bshouty et al. to the case of Unions of Rectangles, a natural generalization of DNFs to $\{0,...,b-1\}^n$.

Affiliated with

Also associated with

No associations

Rating

On Learning Thresholds of Parities and Unions of Rectangles in Random Walk Models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Learning Thresholds of Parities and Unions of Rectangles in Random Walk Models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Learning Thresholds of Parities and Unions of Rectangles in Random Walk Models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-469483