Dimenzia Vapnik-Chervonenkis (VC) je mierou schopnosti súboru hypotéz prispôsobiť sa rôznym súborom údajov. Zaviedli ho Vladimir Vapnik a Alexey Chervonenkis v 70. rokoch minulého storočia a stal sa základným pojmom v teórii štatistického učenia. Dimenzia VC je mierou zložitosti modelu, ktorá nám môže pomôcť pochopiť, ako dobre sa zmestí do rôznych súborov údajov.
Dimenzia VC množiny hypotéz H je najväčší počet bodov, ktoré môže H rozbiť. Súbor hypotéz H rozbije množinu bodov S, ak pre každé možné označenie bodov v S existuje v H hypotéza, že správne klasifikuje body. Inými slovami, množina hypotéz rozbije množinu bodov, ak sa zmestí do akéhokoľvek možného označenia týchto bodov.
Hranice VC – dimenzia
Dimenzia VC poskytuje hornú aj dolnú hranicu počtu tréningových príkladov potrebných na dosiahnutie danej úrovne presnosti. Horná hranica počtu tréningových príkladov je logaritmická v dimenzii VC, zatiaľ čo dolná hranica je lineárna.
Aplikácie VC – Dimension
Dimenzia VC má širokú škálu aplikácií v strojové učenie a štatistiky. Používa sa napríklad na analýzu zložitosti neurónových sietí, podporných vektorových strojov a rozhodovacích stromov. Dimenzia VC sa môže použiť aj na navrhovanie nových algoritmov učenia, ktoré sú odolné voči šumu a dajú sa dobre zovšeobecniť na neviditeľné údaje.
Dimenzia VC môže byť rozšírená na zložitejšie vzdelávacie scenáre, ako je klasifikácia viacerých tried a regresia. Koncept dimenzie VC možno aplikovať aj na iné oblasti informatiky, ako je výpočtová geometria a teória grafov.
Implementácia kódu pre VC – dimenzia
Dimenzia VC je teoretický koncept, ktorý nemožno priamo vypočítať z údajov. Môžeme však odhadnúť dimenziu VC pre daný súbor hypotéz spočítaním počtu bodov, ktoré môže súbor rozbiť. V Pythone môžeme pomocou tohto prístupu implementovať funkciu, ktorá počíta VC dimenziu danej množiny hypotéz.
Funkcia berie množinu hypotéz ako svoj vstup a vypočítava dimenziu VC pomocou prístupu hrubej sily kontroly všetkých možných kombinácií bodov a označení. Používa modul itertools na generovanie všetkých možných kombinácií bodov a označení a potom kontroluje, či súbor hypotéz môže rozbiť každú kombináciu. Funkcia vráti odhadovanú dimenziu VC množiny hypotéz.
Ukážme si použitie tejto funkcie na niekoľkých príkladoch:
Príklad 1:
Predpokladajme, že máme množinu hypotéz, ktorá pozostáva zo všetkých lineárnych funkcií tvaru f(x) = ax + b, kde a a b sú reálne čísla. Túto sadu hypotéz môžeme definovať v Pythone takto:
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))> |
linuxové príkazy
>
>
Výkon:
2>
V príklade 1 funkcia linear_function implementuje jednoduchú množinu hypotéz lineárnej funkcie, ktorá vráti 1, ak je y-ová súradnica vstupného bodu väčšia alebo rovná súradnici x, a v opačnom prípade 0. Funkcia vc_dimension sa potom použije na odhad dimenzie VC tejto sady hypotéz, ktorá je 2.
Príklad 2:
Predpokladajme, že máme množinu hypotéz, ktorá pozostáva zo všetkých kvadratických funkcií tvaru f(x) = ax2+ bx + c, kde a, b a c sú reálne čísla. Môžeme to definovať hypotéza nastaviť v Pythone takto:
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))> |
>
>
Výkon:
parameter v shell skripte
3>
V príklade 2 funkcia quadratic_function implementuje komplexnejšiu množinu hypotéz kvadratickej funkcie, ktorá vráti 1, ak je y-ová súradnica vstupného bodu väčšia alebo rovná druhej mocnine x-ovej súradnice, a v opačnom prípade 0. Funkcia vc_dimension sa potom použije na odhad dimenzie VC tejto sady hypotéz, ktorá je 3.
Záver
Dimenzia VC je základným konceptom v teórii štatistického učenia, ktorý meria zložitosť súboru hypotéz. Poskytuje hornú aj dolnú hranicu počtu tréningových príkladov potrebných na dosiahnutie danej úrovne presnosti. V Pythone môžeme odhadnúť rozmer VC danej sady hypotéz pomocou prístupu hrubej sily, ktorý kontroluje všetky možné kombinácie bodov a označení. Dimenzia VC má širokú škálu aplikácií v oblasti strojového učenia a štatistiky a možno ju rozšíriť na zložitejšie scenáre učenia.