Discretized-Vapnik-Chervonenkis dimension for analyzing complexity of real function classes
In this paper, we introduce the discretized-Vapnik-Chervonenkis (VC) dimension for studying the complexity of a real function class, and then analyze properties of real function classes and neural networks. We first prove that a countable traversal set is enough to achieve the VC dimension for a rea...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/99545 http://hdl.handle.net/10220/13524 |
| _version_ | 1811676396233162752 |
|---|---|
| author | Zhang, Chao Bian, Wei Tao, Dacheng Lin, Weisi |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Zhang, Chao Bian, Wei Tao, Dacheng Lin, Weisi |
| author_sort | Zhang, Chao |
| collection | NTU |
| description | In this paper, we introduce the discretized-Vapnik-Chervonenkis (VC) dimension for studying the complexity of a real function class, and then analyze properties of real function classes and neural networks. We first prove that a countable traversal set is enough to achieve the VC dimension for a real function class, whereas its classical definition states that the traversal set is the output range of the function class. Based on this result, we propose the discretized-VC dimension defined by using a countable traversal set consisting of rational numbers in the range of a real function class. By using the discretized-VC dimension, we show that if a real function class has a finite VC dimension, only a finite traversal set is needed to achieve the VC dimension. We then point out that the real function classes, which have the infinite VC dimension, can be grouped into two categories: TYPE-A and TYPE-B. Subsequently, based on the obtained results, we discuss the relationship between the VC dimension of an indicator-output network and that of the real-output network, when both networks have the same structure except for the output activation functions. Finally, we present the risk bound based on the discretized-VC dimension for a real function class that has infinite VC dimension and is of TYPE-A. We prove that, with such a function class, the empirical risk minimization (ERM) principle for the function class is still consistent with overwhelming probability. This is a development of the existing knowledge that the ERM learning is consistent if and only if the function class has a finite VC dimension. |
| first_indexed | 2024-10-01T02:20:48Z |
| format | Journal Article |
| id | ntu-10356/99545 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:20:48Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/995452020-05-28T07:17:32Z Discretized-Vapnik-Chervonenkis dimension for analyzing complexity of real function classes Zhang, Chao Bian, Wei Tao, Dacheng Lin, Weisi School of Computer Engineering DRNTU::Engineering::Computer science and engineering In this paper, we introduce the discretized-Vapnik-Chervonenkis (VC) dimension for studying the complexity of a real function class, and then analyze properties of real function classes and neural networks. We first prove that a countable traversal set is enough to achieve the VC dimension for a real function class, whereas its classical definition states that the traversal set is the output range of the function class. Based on this result, we propose the discretized-VC dimension defined by using a countable traversal set consisting of rational numbers in the range of a real function class. By using the discretized-VC dimension, we show that if a real function class has a finite VC dimension, only a finite traversal set is needed to achieve the VC dimension. We then point out that the real function classes, which have the infinite VC dimension, can be grouped into two categories: TYPE-A and TYPE-B. Subsequently, based on the obtained results, we discuss the relationship between the VC dimension of an indicator-output network and that of the real-output network, when both networks have the same structure except for the output activation functions. Finally, we present the risk bound based on the discretized-VC dimension for a real function class that has infinite VC dimension and is of TYPE-A. We prove that, with such a function class, the empirical risk minimization (ERM) principle for the function class is still consistent with overwhelming probability. This is a development of the existing knowledge that the ERM learning is consistent if and only if the function class has a finite VC dimension. 2013-09-19T01:25:57Z 2019-12-06T20:08:34Z 2013-09-19T01:25:57Z 2019-12-06T20:08:34Z 2012 2012 Journal Article Zhang, C., Bian, W., Tao, D., & Lin, W. (2012). Discretized-Vapnik-Chervonenkis dimension for analyzing complexity of real function classes. IEEE transactions on neural networks and learning systems, 23(9), 1461-1472. 2162-237X https://hdl.handle.net/10356/99545 http://hdl.handle.net/10220/13524 10.1109/TNNLS.2012.2204773 en IEEE transactions on neural networks and learning systems © 2012 IEEE |
| spellingShingle | DRNTU::Engineering::Computer science and engineering Zhang, Chao Bian, Wei Tao, Dacheng Lin, Weisi Discretized-Vapnik-Chervonenkis dimension for analyzing complexity of real function classes |
| title | Discretized-Vapnik-Chervonenkis dimension for analyzing complexity of real function classes |
| title_full | Discretized-Vapnik-Chervonenkis dimension for analyzing complexity of real function classes |
| title_fullStr | Discretized-Vapnik-Chervonenkis dimension for analyzing complexity of real function classes |
| title_full_unstemmed | Discretized-Vapnik-Chervonenkis dimension for analyzing complexity of real function classes |
| title_short | Discretized-Vapnik-Chervonenkis dimension for analyzing complexity of real function classes |
| title_sort | discretized vapnik chervonenkis dimension for analyzing complexity of real function classes |
| topic | DRNTU::Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/99545 http://hdl.handle.net/10220/13524 |
| work_keys_str_mv | AT zhangchao discretizedvapnikchervonenkisdimensionforanalyzingcomplexityofrealfunctionclasses AT bianwei discretizedvapnikchervonenkisdimensionforanalyzingcomplexityofrealfunctionclasses AT taodacheng discretizedvapnikchervonenkisdimensionforanalyzingcomplexityofrealfunctionclasses AT linweisi discretizedvapnikchervonenkisdimensionforanalyzingcomplexityofrealfunctionclasses |