Loading...
Please wait, while we are loading the content...
Similar Documents
Universal ε-approximators for integrals
| Content Provider | Semantic Scholar |
|---|---|
| Author | Langberg, Michael Schulman, Leonard J. |
| Copyright Year | 2010 |
| Abstract | Let X be a space and F a family of 0, 1-valued functions on X. Vapnik and Chervonenkis showed that if F is "simple" (finite VC dimension), then for every probability measure μ on X and ε > 0 there is a finite set S such that for all f ε F, Σxεs f(x)/|S| = |f f(x)dμ(x)] ± ε. Think of S as a "universal ε-approximator" for integration in F. S can actually be obtained w.h.p. just by sampling a few points from μ. This is a mainstay of computational learning theory. It was later extended by other authors to families of bounded (e.g., [0, 1]-valued) real functions. In this work we establish similar "universal ε-approximators" for families of unbounded nonnegative real functions --- in particular, for the families over which one optimizes when performing data classification. (In this case the ε-approximation should be multiplicative.) Specifically, let F be the family of "k-median functions" (or k-means, etc.) on Rd with an arbitrary norm ϱ. That is, any set u1,..., uk ε Rd determines an f by f(x) = (mini ϱ(x - ui))α. (Here α ≥ 0.) Then for every measure μ on Rd there exists a set S of cardinality poly(k, d, 1/ε) and a measure v supported on S such that for every f ε F, Σxεs f(x)v(x) ε (1 ± ε) · (f f (x)dμ(x)). |
| Starting Page | 598 |
| Ending Page | 607 |
| Page Count | 10 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://people.eecs.berkeley.edu/~brecht/cs294docs/week2/10.Lanberg.pdf |
| Alternate Webpage(s) | https://www.openu.ac.il/home/mikel/papers/sampling_35_full.pdf |
| Alternate Webpage(s) | http://www.openu.ac.il/home/mikel/papers/sampling_35_full.pdf |
| Alternate Webpage(s) | http://www.siam.org/proceedings/soda/2010/SODA10_050_langbergm.pdf |
| Alternate Webpage(s) | http://www.eecs.berkeley.edu/~brecht/cs294docs/week2/10.Lanberg.pdf |
| Alternate Webpage(s) | http://authors.library.caltech.edu/72221/1/1%252E9781611973075%252E50.pdf |
| Alternate Webpage(s) | http://people.eecs.berkeley.edu/~brecht/cs294docs/week2/10.Lanberg.pdf |
| Alternate Webpage(s) | http://siam.org/proceedings/soda/2010/SODA10_050_langbergm.pdf |
| Journal | SODA '10 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
