La dimensió Vapnik-Chervonenkis (VC) és una mesura de la capacitat d'un conjunt d'hipòtesis per adaptar-se a diferents conjunts de dades. Va ser introduït per Vladimir Vapnik i Alexey Chervonenkis a la dècada de 1970 i s'ha convertit en un concepte fonamental en la teoria de l'aprenentatge estadístic. La dimensió VC és una mesura de la complexitat d'un model, que ens pot ajudar a entendre fins a quin punt pot adaptar-se a diferents conjunts de dades.
La dimensió VC d'un conjunt d'hipòtesis H és el nombre més gran de punts que pot ser trencat per H. Un conjunt d'hipòtesis H trenca un conjunt de punts S si, per a cada etiquetatge possible dels punts de S, existeix una hipòtesi en H que classifica correctament els punts. En altres paraules, un conjunt d'hipòtesis trenca un conjunt de punts si pot adaptar-se a qualsevol etiqueta possible d'aquests punts.
Límits de VC - Dimensió
La dimensió VC proporciona límits superiors i inferiors del nombre d'exemples d'entrenament necessaris per aconseguir un nivell determinat de precisió. El límit superior del nombre d'exemples d'entrenament és logarítmic a la dimensió VC, mentre que el límit inferior és lineal.
Aplicacions de VC – Dimensió
La dimensió VC té una àmplia gamma d'aplicacions aprenentatge automàtic i estadístiques. Per exemple, s'utilitza per analitzar la complexitat de les xarxes neuronals, les màquines vectorials de suport i els arbres de decisió. La dimensió VC també es pot utilitzar per dissenyar nous algorismes d'aprenentatge que siguin robusts al soroll i que es puguin generalitzar bé a dades no vistes.
La dimensió VC es pot estendre a escenaris d'aprenentatge més complexos, com ara la classificació multiclasse i la regressió. El concepte de dimensió VC també es pot aplicar a altres àrees de la informàtica, com ara la geometria computacional i la teoria de grafs.
Implementació de codi per a VC – Dimensió
La dimensió VC és un concepte teòric que no es pot calcular directament a partir de dades. Tanmateix, podem estimar la dimensió VC per a un conjunt d'hipòtesis donat comptant el nombre de punts que el conjunt pot trencar. A Python, podem implementar una funció que calcula la dimensió VC d'un conjunt d'hipòtesis donat mitjançant aquest enfocament.
La funció pren un conjunt d'hipòtesis com a entrada i calcula la dimensió VC utilitzant l'enfocament de força bruta de comprovar totes les combinacions possibles de punts i etiquetes. Utilitza el mòdul itertools per generar totes les combinacions possibles de punts i etiquetes i després comprova si el conjunt d'hipòtesis pot trencar cada combinació. La funció retorna la dimensió VC estimada del conjunt d'hipòtesis.
Il·lustrem l'ús d'aquesta funció amb alguns exemples:
Exemple 1:
Suposem que tenim un conjunt d'hipòtesis que consta de totes les funcions lineals de la forma f(x) = ax + b, on a i b són nombres reals. Podem definir aquest conjunt d'hipòtesis a Python de la següent manera:
Python
import> itertools> > > def> vc_dimension(hypothesis_set):> >'''> >Estimates the VC dimension of a hypothesis set using the brute-force approach.> >'''> >n>=> 4> >while> True>:> >points>=> [(i, j)>for> i>in> range>(n)>for> j>in> range>(>2>)]> >shattered_sets>=> 0> >for> combination>in> itertools.combinations(points, n):> >is_shattered>=> True> >for> labeling>in> itertools.product([>0>,>1>], repeat>=>n):> >hypotheses>=> [hypothesis_set(point)>for> point>in> combination]> >if> set>(hypotheses) !>=> set>(labeling):> >is_shattered>=> False> >break> >if> is_shattered:> >shattered_sets>+>=> 1> >else>:> >break> >if> not> is_shattered:> >break> >n>+>=> 1> >return> n>->1> if> shattered_sets>=>=> 2>*>*>n>else> n>->2> > > # Example 1: linear function hypothesis set> def> linear_function(point):> >x, y>=> point> >return> int>(y>>=> x)> > > print>(vc_dimension(linear_function))> |
>
>
Sortida:
2>
A l'exemple 1, la funció linear_function implementa un conjunt d'hipòtesis de funció lineal simple que retorna 1 si la coordenada y del punt d'entrada és major o igual a la coordenada x, i 0 en cas contrari. La funció vc_dimension s'utilitza llavors per estimar la dimensió VC d'aquest conjunt d'hipòtesis, que és 2.
Exemple 2:
Suposem que tenim un conjunt d'hipòtesis que consta de totes les funcions quadràtiques de la forma f(x) = ax2+ bx + c, on a, b i c són nombres reals. Això ho podem definir hipòtesi establert a Python de la següent manera:
Python
import> itertools> > > def> vc_dimension(hypothesis_set):> >'''> >Estimates the VC dimension of a hypothesis set using the brute-force approach.> >'''> >n>=> 5> >while> True>:> >points>=> [(i, j)>for> i>in> range>(n)>for> j>in> range>(>2>)]> >shattered_sets>=> 0> >for> combination>in> itertools.combinations(points, n):> >is_shattered>=> True> >for> labeling>in> itertools.product([>0>,>1>], repeat>=>n):> >hypotheses>=> [hypothesis_set(point)>for> point>in> combination]> >if> set>(hypotheses) !>=> set>(labeling):> >is_shattered>=> False> >break> >if> is_shattered:> >shattered_sets>+>=> 1> >else>:> >break> >if> not> is_shattered:> >break> >n>+>=> 1> >return> n>->1> if> shattered_sets>=>=> 2>*>*>n>else> n>->2> > > # Example 2: quadratic function hypothesis set> def> quadratic_function(point):> >x, y>=> point> >return> int>(y>>=> x>*>*>2>)> > > print>(vc_dimension(quadratic_function))> |
gzip per a Linux
>
>
Sortida:
3>
A l'exemple 2, la funció quadratic_function implementa un conjunt d'hipòtesis de funció quadràtica més complex que retorna 1 si la coordenada y del punt d'entrada és major o igual que el quadrat de la coordenada x, i 0 en cas contrari. La funció vc_dimension s'utilitza llavors per estimar la dimensió VC d'aquest conjunt d'hipòtesis, que és 3.
Conclusió
La dimensió VC és un concepte fonamental en la teoria de l'aprenentatge estadístic que mesura la complexitat d'un conjunt d'hipòtesis. Proporciona límits superiors i inferiors del nombre d'exemples d'entrenament necessaris per aconseguir un nivell determinat de precisió. A Python, podem estimar la dimensió VC d'un conjunt d'hipòtesis donat mitjançant un enfocament de força bruta que verifica totes les combinacions possibles de punts i etiquetes. La dimensió VC té una àmplia gamma d'aplicacions en aprenentatge automàtic i estadístiques i es pot estendre a escenaris d'aprenentatge més complexos.