Learning Disjunctions: Near-Optimal Trade-off between Mistakes and “I Don't Knows”
We develop polynomial-time online algorithms for learning disjunctions while trading off between the number of mistakes and the number of “I don't know” answers. In this model, we are given an online adversarial sequence of inputs for an unknown function of the form f(x1, x2,..., xn) = Viεs[sup...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86204 https://orcid.org/0000-0003-3803-5703 |