Discretized-vapnik-chervonenkis dimension for analyzing complexity of real function classes

Zhang, C; Bian, W; Tao, D; Lin, W

Discretized-vapnik-chervonenkis dimension for analyzing complexity of real function classes

Zhang, C Bian, W Tao, D

Lin, W

Permalink

Publication Type:: Journal Article
Citation:: IEEE Transactions on Neural Networks and Learning Systems, 2012, 23 (9), pp. 1461 - 1472
Issue Date:: 2012-12-01

Closed Access

	Filename	Description	Size
	2012001452OK.pdf		348.97 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, C	en_US
dc.contributor.author	Bian, W	en_US
dc.contributor.author	Tao, D https://orcid.org/0000-0001-7225-5449	en_US
dc.contributor.author	Lin, W	en_US
dc.date.issued	2012-12-01	en_US
dc.identifier.citation	IEEE Transactions on Neural Networks and Learning Systems, 2012, 23 (9), pp. 1461 - 1472	en_US
dc.identifier.issn	2162-237X	en_US
dc.identifier.uri	http://hdl.handle.net/10453/22857
dc.description.abstract	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. © 2012 IEEE.	en_US
dc.relation.ispartof	IEEE Transactions on Neural Networks and Learning Systems	en_US
dc.relation.isbasedon	10.1109/TNNLS.2012.2204773	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Discretized-vapnik-chervonenkis dimension for analyzing complexity of real function classes	en_US
dc.type	Journal Article
utslib.citation.volume	9	en_US
utslib.citation.volume	23	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.issue	9	en_US
pubs.publication-status	Published	en_US
pubs.volume	23	en_US

Abstract:

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. © 2012 IEEE.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/22857