Refined Kolmogorov complexity of analog, evolving and stochastic recurrent neural networks

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F25%3A00637283" target="_blank" >RIV/67985807:_____/25:00637283 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.ins.2025.122104" target="_blank" >https://doi.org/10.1016/j.ins.2025.122104</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ins.2025.122104" target="_blank" >10.1016/j.ins.2025.122104</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Refined Kolmogorov complexity of analog, evolving and stochastic recurrent neural networks

Popis výsledku v původním jazyce

Kolmogorov complexity measures the compressibility of real numbers. We provide a refined characterization of the hypercomputational power of analog, evolving, and stochastic neural networks based on the Kolmogorov complexity of their real weights, evolving weights, and real probabilities, respectively. First, we retrieve the infinite hierarchy of complexity classes of analog networks, defined in terms of the Kolmogorov complexity of their real weights. This hierarchy lies between the complexity classes P and P/poly. Next, using a natural identification between real numbers and infinite sequences of bits, we generalize this result to evolving networks, obtaining a similar hierarchy of complexity classes within the same bounds. Finally, we extend these results to stochastic networks that employ real probabilities as randomness, deriving a new infinite hierarchy of complexity classes situated between BPP and BPP/log⁎. Beyond providing examples of such hierarchies, we describe a generic method for constructing them based on classes of functions of increasing complexity. As a practical application, we show that the predictive capabilities of recurrent neural networks are strongly impacted by the quantization applied to their weights. Overall, these results highlight the relationship between the computational power of neural networks and the intrinsic information contained by their parameters

Název v anglickém jazyce

Refined Kolmogorov complexity of analog, evolving and stochastic recurrent neural networks

Popis výsledku anglicky

Kolmogorov complexity measures the compressibility of real numbers. We provide a refined characterization of the hypercomputational power of analog, evolving, and stochastic neural networks based on the Kolmogorov complexity of their real weights, evolving weights, and real probabilities, respectively. First, we retrieve the infinite hierarchy of complexity classes of analog networks, defined in terms of the Kolmogorov complexity of their real weights. This hierarchy lies between the complexity classes P and P/poly. Next, using a natural identification between real numbers and infinite sequences of bits, we generalize this result to evolving networks, obtaining a similar hierarchy of complexity classes within the same bounds. Finally, we extend these results to stochastic networks that employ real probabilities as randomness, deriving a new infinite hierarchy of complexity classes situated between BPP and BPP/log⁎. Beyond providing examples of such hierarchies, we describe a generic method for constructing them based on classes of functions of increasing complexity. As a practical application, we show that the predictive capabilities of recurrent neural networks are strongly impacted by the quantization applied to their weights. Overall, these results highlight the relationship between the computational power of neural networks and the intrinsic information contained by their parameters

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Information Sciences

ISSN

0020-0255

e-ISSN

1872-6291

Svazek periodika

711

Číslo periodika v rámci svazku

September 2025

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

24

Strana od-do

122104

Kód UT WoS článku

001456228400001

EID výsledku v databázi Scopus

2-s2.0-105000540781