Funkce růstu - Growth function

The růstová funkce, také nazývaný koeficient rozbití nebo tříštivé číslo, měří bohatství a nastavit rodinu. Používá se zejména v kontextu statistická teorie učení, kde měří složitost třídy hypotéz. Termín 'růstová funkce' vymysleli Vapnik a Chervonenkis ve své práci z roku 1968, kde také prokázali mnoho svých vlastností.^[1]Jedná se o základní koncept v strojové učení.^[2]^[3]

Definice

Definice sady rodin

Nechat ${ displaystyle H}$ být nastavit rodinu (sada sad) a ${ displaystyle C}$ sada. Jejich průsečík je definována jako následující rodina sad:

{ displaystyle H cap C: = {h cap C mid h v H }}

The velikost křižovatky (nazývané také index) z ${ displaystyle H}$ s ohledem na ${ displaystyle C}$ je ${ displaystyle | H cap C |}$ . Pokud sada ${ displaystyle C_ {m}}$ má ${ displaystyle m}$ prvků je index maximálně ${ displaystyle 2 ^ {m}}$ . Pokud je index přesně 2^m pak sada ${ displaystyle C}$ je prý rozbit ${ displaystyle H}$ , protože ${ displaystyle H cap C}$ obsahuje všechny podmnožiny ${ displaystyle C}$ , tj.:

{ displaystyle | H cap C | = 2 ^ {| C |},}

Funkce růstu měří velikost ${ displaystyle H cap C}$ jako funkce ${ displaystyle | C |}$ . Formálně:

{ displaystyle operatorname {růst} (H, m): = max _ {C: | C | = m} | H cap C |}

Definice třídy hypotéz

Ekvivalentně, pojďme ${ displaystyle H}$ být třídou hypotéz (soubor binárních funkcí) a ${ displaystyle C}$ sada s ${ displaystyle m}$ elementy. The omezení z ${ displaystyle H}$ na ${ displaystyle C}$ je sada binárních funkcí na ${ displaystyle C}$ z čehož lze odvodit ${ displaystyle H}$ :^[3]^:45

{ displaystyle H_ {C}: = {(h (x_ {1}), ldots, h (x_ {m})) mid h v H, x_ {i} v C }}

Funkce růstu měří velikost ${ displaystyle H_ {C}}$ jako funkce ${ displaystyle | C |}$ :^[3]^:49

{ displaystyle operatorname {růst} (H, m): = max _ {C: | C | = m} | H_ {C} |}

Příklady

1. Doména je skutečná čára ${ displaystyle mathbb {R}}$ . Set-rodina ${ displaystyle H}$ obsahuje všechny půlřádky (paprsky) z daného čísla do kladného nekonečna, tj. všechny sady formuláře ${ displaystyle {x> x_ {0} mid x in mathbb {R} }}$ pro některé ${ displaystyle x_ {0} in mathbb {R}}$ . Pro jakoukoli sadu ${ displaystyle C}$ z ${ displaystyle m}$ reálná čísla, průnik ${ displaystyle H cap C}$ obsahuje ${ displaystyle m + 1}$ sady: prázdná sada, sada obsahující největší prvek ${ displaystyle C}$ , sada obsahující dva největší prvky ${ displaystyle C}$ , a tak dále. Proto: ${ displaystyle operatorname {růst} (H, m) = m + 1}$ .^[1]^{:Př. 1} Totéž platí, zda ${ displaystyle H}$ obsahuje otevřené poloviční čáry, uzavřené poloviční čáry nebo obojí.

2. Doménou je segment ${ displaystyle [0,1]}$ . Set-rodina ${ displaystyle H}$ obsahuje všechny otevřené sady. Pro jakoukoli konečnou množinu ${ displaystyle C}$ z ${ displaystyle m}$ reálná čísla, průnik ${ displaystyle H cap C}$ obsahuje všechny možné podmnožiny ${ displaystyle C}$ . Existují ${ displaystyle 2 ^ {m}}$ takové podmnožiny, tak ${ displaystyle operatorname {růst} (H, m) = 2 ^ {m}}$ .^[1]^{:Př. 2.}

3. Doménou je euklidovský prostor ${ displaystyle mathbb {R} ^ {n}}$ . Set-rodina ${ displaystyle H}$ obsahuje všechny poloprostory formuláře: ${ displaystyle x cdot phi geq 1}$ , kde ${ displaystyle phi}$ je fixní vektor ${ displaystyle operatorname {růst} (H, m) = operatorname {Comp} (n, m)}$ , kde Comp je počet počet komponent v rozdělení n-rozměrného prostoru m hyperplany.^[1]^{:Př. 3.}

4. Doména je skutečná čára ${ displaystyle mathbb {R}}$ . Set-rodina ${ displaystyle H}$ obsahuje všechny skutečné intervaly, tj. všechny sady formuláře ${ displaystyle {x v [x_ {0}, x_ {1}] | x v mathbb {R} }}$ pro některé ${ displaystyle x_ {0}, x_ {1} in mathbb {R}}$ . Pro jakoukoli sadu ${ displaystyle C}$ z ${ displaystyle m}$ reálná čísla, průnik ${ displaystyle H cap C}$ obsahuje všechny běhy od 0 do ${ displaystyle m}$ po sobě jdoucí prvky ${ displaystyle C}$ . Počet takových běhů je ${ displaystyle {m + 1 vyberte 2} +1}$ , tak ${ displaystyle operatorname {růst} (H, m) = {m + 1 vyberte 2} +1}$ .

Polynomiální nebo exponenciální

Hlavní vlastnost, díky které je funkce růstu zajímavá, spočívá v tom, že může být buď polynomiální nebo exponenciální - nic mezi tím.

Toto je vlastnost velikosti křižovatky:^[1]^{:1. díl}

Pokud pro nějakou sadu ${ displaystyle C_ {m}}$ velikosti ${ displaystyle m}$ , a pro nějaké číslo ${ displaystyle n leq m}$ , ${ displaystyle | H cap C_ {m} | geq operatorname {Comp} (n, m)}$ -
pak existuje podmnožina ${ displaystyle C_ {n} subseteq C_ {m}}$ velikosti ${ displaystyle n}$ takhle ${ displaystyle | H cap C_ {n} | = 2 ^ {n}}$ .

To implikuje následující vlastnost funkce růstu.^[1]^:Čt.1Pro každou rodinu ${ displaystyle H}$ existují dva případy:

The exponenciální případ: ${ displaystyle operatorname {růst} (H, m) = 2 ^ {m}}$ identický.
The polynomiální případ: ${ displaystyle operatorname {růst} (H, m)}$ je zaměřen na ${ displaystyle operatorname {Comp} (n, m) leq m ^ {n} +1}$ , kde ${ displaystyle n}$ je nejmenší celé číslo, pro které ${ displaystyle operatorname {růst} (H, n) <2 ^ {n}}$ .

Další vlastnosti

Triviální horní mez

Pro každou konečnou ${ displaystyle H}$ :

{ displaystyle operatorname {růst} (H, m) leq | H |}

protože pro každého ${ displaystyle C}$ , počet prvků v ${ displaystyle H cap C}$ je nanejvýš ${ displaystyle | H |}$ . Proto je růstová funkce zajímavá hlavně tehdy, když ${ displaystyle H}$ je nekonečný.

Exponenciální horní mez

Pro jakékoli neprázdné ${ displaystyle H}$ :

{ displaystyle operatorname {růst} (H, m) leq 2 ^ {m}}

Tj. Růstová funkce má exponenciální horní mez.

Říkáme, že set-rodina ${ displaystyle H}$ rozbije se sada ${ displaystyle C}$ pokud jejich průnik obsahuje všechny možné podmnožiny ${ displaystyle C}$ , tj. ${ displaystyle H cap C = 2 ^ {C}}$ .Li ${ displaystyle H}$ rozbije se ${ displaystyle C}$ velikosti ${ displaystyle m}$ , pak ${ displaystyle operatorname {růst} (H, C) = 2 ^ {m}}$ , což je horní hranice.

Kartézská křižovatka

Definujte kartézský průnik dvou množinových rodin jako:

{ displaystyle H_ {1} bigotimes H_ {2}: = {h_ {1} cap h_ {2} mid h_ {1} v H_ {1}, h_ {2} v H_ {2} }}

.

Pak:^[2]^:57

{ displaystyle operatorname {Growth} (H_ {1} bigotimes H_ {2}, m) leq operatorname {Growth} (H_ {1}, m) cdot operatorname {Growth} (H_ {2}, m)}

svaz

Pro každé dvě sady rodin:^[2]^:58

{ displaystyle operatorname {Growth} (H_ {1} cup H_ {2}, m) leq operatorname {Growth} (H_ {1}, m) + operatorname {Growth} (H_ {2}, m )}

VC rozměr

The VC rozměr z ${ displaystyle H}$ je definována podle těchto dvou případů:

V polynomiální případ, ${ displaystyle operatorname {VCDim} (H) = n-1}$ = největší celé číslo ${ displaystyle d}$ pro který ${ displaystyle operatorname {růst} (H, d) = 2 ^ {d}}$ .
V exponenciální případ ${ displaystyle operatorname {VCDim} (H) = infty}$ .

Tak ${ displaystyle operatorname {VCDim} (H) geq d}$ pouze-li-li ${ displaystyle operatorname {růst} (H, d) = 2 ^ {d}}$ .

Růstovou funkci lze považovat za vylepšení konceptu dimenze VC. Dimenze VC nám pouze říká, zda ${ displaystyle operatorname {růst} (H, d)}$ je rovno nebo menší než ${ displaystyle 2 ^ {d}}$ , zatímco funkce růstu nám říká přesně jak ${ displaystyle operatorname {růst} (H, m)}$ změny v závislosti na ${ displaystyle m}$ .

Další souvislost mezi růstovou funkcí a dimenzí VC je dána Sauer – Shelahovo lemma:^[3]^:49

Li

{ displaystyle operatorname {VCDim} (H) = d}

, pak:

pro všechny

{ displaystyle m}

:

{ displaystyle operatorname {růst} (H, m) leq sum _ {i = 0} ^ {d} {m zvolit i}}

Zejména,

pro všechny

{ displaystyle m> d + 1}

:

{ displaystyle operatorname {růst} (H, m) leq (em / d) ^ {d} = O (m ^ {d})}

takže když je dimenze VC konečná, růstová funkce roste polynomiálně s

{ displaystyle m}

.

Tato horní hranice je pevná, tj. Pro všechny ${ displaystyle m> d}$ tady existuje ${ displaystyle H}$ s rozměrem VC ${ displaystyle d}$ takové, že:^[2]^:56

{ displaystyle operatorname {růst} (H, m) = součet _ {i = 0} ^ {d} {m zvolit i}}

Entropie

Zatímco růstová funkce souvisí s maximum velikost křižovatky entropie souvisí s průměrný velikost průniku:^[1]^:272–273

{ displaystyle operatorname {Entropy} (H, m) = E_ {| C_ {m} | = m} { big [} log _ {2} (| H cap C_ {m} |) { big ]}}

Velikost průniku má následující vlastnost. Pro každou rodinu ${ displaystyle H}$ :

{ displaystyle | H cap (C_ {1} cup C_ {2}) | leq | H cap C_ {1} | cdot | H cap C_ {2} |}

Proto:

{ displaystyle operatorname {Entropy} (H, m_ {1} + m_ {2}) leq operatorname {Entropy} (H, m_ {1}) + operatorname {Entropy} (H, m_ {2}) }

Navíc sekvence ${ displaystyle operatorname {Entropy} (H, m) / m}$ konverguje na konstantu ${ displaystyle c v [0,1]}$ když ${ displaystyle m to infty}$ .

Navíc náhodná proměnná ${ displaystyle log _ {2} {| H cap C_ {m} | / m}}$ je soustředěna blízko ${ displaystyle c}$ .

Aplikace v teorii pravděpodobnosti

Nechat ${ displaystyle Omega}$ být soubor, na kterém a míra pravděpodobnosti ${ displaystyle Pr}$ je definováno. Nechat ${ displaystyle H}$ být rodinou podmnožin ${ displaystyle Omega}$ skupina událostí.

Předpokládejme, že jsme vybrali sadu ${ displaystyle C_ {m}}$ který obsahuje ${ displaystyle m}$ prvky ${ displaystyle Omega}$ , kde je každý prvek náhodně vybrán podle míry pravděpodobnosti ${ displaystyle P}$ , nezávisle na ostatních (tj. s náhradami). Pro každou událost ${ displaystyle h v H}$ , porovnáváme následující dvě veličiny:

Jeho relativní frekvence v ${ displaystyle C_ {m}}$ , tj, ${ displaystyle | h cap C_ {m} | / m}$ ;
Jeho pravděpodobnost ${ displaystyle Pr [h]}$ .

Zajímá nás rozdíl, ${ displaystyle D (h, C_ {m}): = { big |} | h cap C_ {m} | / m- Pr [h] { big |}}$ . Tento rozdíl splňuje následující horní mez:

{ displaystyle Pr left [ forall h in H: D (h, C_ {m}) leq { sqrt {8 ( ln operatorname {Growth} (H, 2m) + ln (4 / delta)) přes m}} vpravo] ~~~~> ~~~~ 1- delta}

což odpovídá:^[1]^:Čt.2

{ displaystyle Pr { big [} for all h in H: D (h, C_ {m}) leq varepsilon { big]} ~~~~> ~~~~ 1-4 cdot operatorname {Growth} (H, 2m) cdot exp (- varepsilon ^ {2} cdot m / 8)}

Slovy: pravděpodobnost, že pro Všechno události v ${ displaystyle H}$ , relativní frekvence se blíží pravděpodobnosti, je dolní mezí výrazu, který závisí na růstové funkci ${ displaystyle H}$ .

Důsledkem toho je, že pokud je funkce růstu polynomiální ${ displaystyle m}$ (tj. nějaké existují ${ displaystyle n}$ takhle ${ displaystyle operatorname {růst} (H, m) leq m ^ {n} +1}$ ), pak se výše uvedená pravděpodobnost blíží 1 jako ${ displaystyle m to infty}$ . Tj. Rodina ${ displaystyle H}$ těší se jednotná konvergence v pravděpodobnosti.

Reference

^ ^A ^b ^C ^d ^E ^F ^G ^h Vapnik, V. N .; Chervonenkis, A. Ya. (1971). „O jednotné konvergenci relativních frekvencí událostí k jejich pravděpodobnostem“. Teorie pravděpodobnosti a její aplikace. 16 (2): 264. doi:10.1137/1116025.Toto je anglický překlad ruského článku B. Secklera: „O jednotné konvergenci relativních frekvencí událostí k jejich pravděpodobnostem“. Dokl. Akad. Nauk. 181 (4): 781. 1968.Překlad byl reprodukován jako:Vapnik, V. N .; Chervonenkis, A. Ya. (2015). „O jednotné konvergenci relativních frekvencí událostí k jejich pravděpodobnostem“. Míra složitosti. str. 11. doi:10.1007/978-3-319-21852-6_3. ISBN 978-3-319-21851-9.
^ ^A ^b ^C ^d Mohri, Mehryar; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Základy strojového učení. USA, Massachusetts: MIT Press. ISBN 9780262018258., zejména oddíl 3.2
^ ^A ^b ^C ^d Shalev-Shwartz, Shai; Ben-David, Shai (2014). Porozumění strojovému učení - od teorie po algoritmy. Cambridge University Press. ISBN 9781107057135.

[vc-1] A ^b ^C ^d ^E ^F ^G ^h Vapnik, V. N .; Chervonenkis, A. Ya. (1971). „O jednotné konvergenci relativních frekvencí událostí k jejich pravděpodobnostem“. Teorie pravděpodobnosti a její aplikace. 16 (2): 264. doi:10.1137/1116025.Toto je anglický překlad ruského článku B. Secklera: „O jednotné konvergenci relativních frekvencí událostí k jejich pravděpodobnostem“. Dokl. Akad. Nauk. 181 (4): 781. 1968.Překlad byl reprodukován jako:Vapnik, V. N .; Chervonenkis, A. Ya. (2015). „O jednotné konvergenci relativních frekvencí událostí k jejich pravděpodobnostem“. Míra složitosti. str. 11. doi:10.1007/978-3-319-21852-6_3. ISBN 978-3-319-21851-9.

[book12-2] A ^b ^C ^d Mohri, Mehryar; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Základy strojového učení. USA, Massachusetts: MIT Press. ISBN 9780262018258., zejména oddíl 3.2

[book14-3] A ^b ^C ^d Shalev-Shwartz, Shai; Ben-David, Shai (2014). Porozumění strojovému učení - od teorie po algoritmy. Cambridge University Press. ISBN 9781107057135.

[1]

[2]

[3]