Epsilon entropi

Epsilon - entropi eller ε-entropi är en term som introducerats av A. N. Kolmogorov för att karakterisera klasser av funktioner. Den definierar ett mått på komplexiteten hos en funktion , det minsta antal tecken som krävs för att specificera en funktion med precision. $\varepsilon$

Introduktion till konceptet

Betrakta ett kompakt metriskt utrymme och definiera ett epsilon-nätverk i det , det vill säga en sådan ändlig (bestående av punkter) uppsättning att kulorna med radie centrerade på dessa punkter helt täcker allt . Sedan, för att specificera vilket element som helst med precision (det vill säga valet av en av nätverksnoderna), är ordningen på tecken ( bitar ) tillräcklig. $M$ $N(\varepsilon)$ $\varepsilon$ $M$ $M$ $\varepsilon$ $\log _{2}N(\varepsilon )$

För ett segment ökar värdet med minskande som , för en kvadrat som etc. Således bestämmer indikatorn dimensionen på Minkowski- uppsättningen . $M=[0,\;1]$ $N$ $\varepsilon$ $1/\varepsilon$ $1/{\varepsilon ^{2))$ $M$

I fallet med ett utrymme med jämna funktioner (på en kompakt kub i ett dimensionellt utrymme och med derivator som begränsas av en konstant upp till storleksordningen , så att detta utrymme är kompakt), är utrymmets dimension oändlig, men antalet av nätverkselement är ändlig, även om den växer snabbare än någon (negativ) effekt av . $M$ $n$ $sid$ $N(\varepsilon)$ $\varepsilon$

Kolmogorov bevisade att logaritmen för antalet poäng i ett minimalt -net växer i detta fall som . $N(\varepsilon)$ $\varepsilon$ ${\displaystyle (1/\varepsilon )^{n/p))$

Applikation

Införandet av begreppet epsilon-entropi gjorde det möjligt att förstå och lösa Hilberts 13:e problem .

Om funktionerna för variabler som deltar i superpositionen hade jämnhet , skulle det med deras hjälp vara möjligt att få ett nätverk för de representerade funktionerna, vars logaritm för antalet punkter skulle vara i storleksordningen . Om detta antal är mindre än det minsta möjliga för funktioner av jämnhetsvariabler , betyder det att den antagna representationen genom överlagringar av funktioner med så stor jämnhet är omöjlig. $k$ $sid$ ${\displaystyle (1/\varepsilon )^{k/p))$ $n$ $sid$

Sedan visade Kolmogorov att om jämnhet överges och alla kontinuerliga funktioner tillåts delta i överlagringen, så representeras varje kontinuerlig funktion av variabler av en överlagring av kontinuerliga funktioner med endast tre variabler, och efter det presenterade hans elev V.I. Arnold dem med superpositioner av kontinuerliga funktioner av två variabler. Som ett resultat innehöll Kolmogorovs sats en enda funktion av två variabler, summan, och alla de andra kontinuerliga funktionerna som utgör superpositionen som representerar alla kontinuerliga funktioner hos variabler var och en beror på endast en variabel. $n$ $n$