Learning Real and Boolean Functions: When Is Deep Better Than Shallow
We describe computational tasks - especially in vision - that correspond to compositional/hierarchical functions. While the universal approximation property holds both for hierarchical and shallow networks, we prove that deep (hierarchical) networks can approximate the class of compositional functio...
| Main Authors: | , , |
|---|---|
| Format: | Technical Report |
| Language: | en_US |
| Published: |
Center for Brains, Minds and Machines (CBMM), arXiv
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/101635 |
| _version_ | 1826195467443109888 |
|---|---|
| author | Mhaskar, Hrushikesh Liao, Qianli Poggio, Tomaso |
| author_facet | Mhaskar, Hrushikesh Liao, Qianli Poggio, Tomaso |
| author_sort | Mhaskar, Hrushikesh |
| collection | MIT |
| description | We describe computational tasks - especially in vision - that correspond to compositional/hierarchical functions. While the universal approximation property holds both for hierarchical and shallow networks, we prove that deep (hierarchical) networks can approximate the class of compositional functions with the same accuracy as shallow networks but with exponentially lower VC-dimension as well as the number of training parameters. This leads to the question of approximation by sparse polynomials (in the number of independent parameters) and, as a consequence, by deep networks. We also discuss connections between our results and learnability of sparse Boolean functions, settling an old conjecture by Bengio. |
| first_indexed | 2024-09-23T10:13:08Z |
| format | Technical Report |
| id | mit-1721.1/101635 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:13:08Z |
| publishDate | 2016 |
| publisher | Center for Brains, Minds and Machines (CBMM), arXiv |
| record_format | dspace |
| spelling | mit-1721.1/1016352019-04-10T10:50:58Z Learning Real and Boolean Functions: When Is Deep Better Than Shallow Mhaskar, Hrushikesh Liao, Qianli Poggio, Tomaso computational tasks Computer vision Hierarchy We describe computational tasks - especially in vision - that correspond to compositional/hierarchical functions. While the universal approximation property holds both for hierarchical and shallow networks, we prove that deep (hierarchical) networks can approximate the class of compositional functions with the same accuracy as shallow networks but with exponentially lower VC-dimension as well as the number of training parameters. This leads to the question of approximation by sparse polynomials (in the number of independent parameters) and, as a consequence, by deep networks. We also discuss connections between our results and learnability of sparse Boolean functions, settling an old conjecture by Bengio. This work was supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award CCF 1231216. HNM was supported in part by ARO Grant W911NF-15-1-0385. 2016-03-08T17:13:57Z 2016-03-08T17:13:57Z 2016-03-08 Technical Report Working Paper Other http://hdl.handle.net/1721.1/101635 arXiv:1603.00988 en_US CBMM Memo Series;045 Attribution-NonCommercial-ShareAlike 3.0 United States http://creativecommons.org/licenses/by-nc-sa/3.0/us/ application/pdf Center for Brains, Minds and Machines (CBMM), arXiv |
| spellingShingle | computational tasks Computer vision Hierarchy Mhaskar, Hrushikesh Liao, Qianli Poggio, Tomaso Learning Real and Boolean Functions: When Is Deep Better Than Shallow |
| title | Learning Real and Boolean Functions: When Is Deep Better Than Shallow |
| title_full | Learning Real and Boolean Functions: When Is Deep Better Than Shallow |
| title_fullStr | Learning Real and Boolean Functions: When Is Deep Better Than Shallow |
| title_full_unstemmed | Learning Real and Boolean Functions: When Is Deep Better Than Shallow |
| title_short | Learning Real and Boolean Functions: When Is Deep Better Than Shallow |
| title_sort | learning real and boolean functions when is deep better than shallow |
| topic | computational tasks Computer vision Hierarchy |
| url | http://hdl.handle.net/1721.1/101635 |
| work_keys_str_mv | AT mhaskarhrushikesh learningrealandbooleanfunctionswhenisdeepbetterthanshallow AT liaoqianli learningrealandbooleanfunctionswhenisdeepbetterthanshallow AT poggiotomaso learningrealandbooleanfunctionswhenisdeepbetterthanshallow |