Distribution-Specific Agnostic Boosting

Details Distribution-Specific Agnostic Boosting Distribution-Specific Agnostic Boosting

2009-09-16

arxiv.org/abs/0909.2927v1

Proceedings of Innovations in Computer Science (ICS), 2010, pp 241-250

Computer Science

Learning

Scientific paper

We consider the problem of boosting the accuracy of weak learning algorithms in the agnostic learning framework of Haussler (1992) and Kearns et al. (1992). Known algorithms for this problem (Ben-David et al., 2001; Gavinsky, 2002; Kalai et al., 2008) follow the same strategy as boosting algorithms in the PAC model: the weak learner is executed on the same target function but over different distributions on the domain. We demonstrate boosting algorithms for the agnostic learning framework that only modify the distribution on the labels of the points (or, equivalently, modify the target function). This allows boosting a distribution-specific weak agnostic learner to a strong agnostic learner with respect to the same distribution. When applied to the weak agnostic parity learning algorithm of Goldreich and Levin (1989) our algorithm yields a simple PAC learning algorithm for DNF and an agnostic learning algorithm for decision trees over the uniform distribution using membership queries. These results substantially simplify Jackson's famous DNF learning algorithm (1994) and the recent result of Gopalan et al. (2008). We also strengthen the connection to hard-core set constructions discovered by Klivans and Servedio (1999) by demonstrating that hard-core set constructions that achieve the optimal hard-core set size (given by Holenstein (2005) and Barak et al. (2009)) imply distribution-specific agnostic boosting algorithms. Conversely, our boosting algorithm gives a simple hard-core set construction with an (almost) optimal hard-core set size.

Affiliated with

Also associated with

No associations

Rating

Distribution-Specific Agnostic Boosting 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 Distribution-Specific Agnostic Boosting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distribution-Specific Agnostic Boosting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-582232