Jaka jest absolutnie najlepsza teoretyczna bezstratna kompresja danych? - uczenie maszynowe, kompresja, sztuczna inteligencja

Zacząć z:

Załóżmy, że algorytm zajmuje skończoną przestrzeń. Załóżmy, że zasoby obliczeniowe są nieskończone.

Jaką formę miałby wynik takiej kompresjibrać? Moja intuicja podpowiada mi, że byłaby to jakaś forma algorytmu podobnego do pRNG z nieredukowalnym ziarnem, który daje początek skompresowanym danym. Czy może być coś jeszcze bardziej wydajnego?

A co jeśli założymy, że wszystkie zasoby są skończone. Czy problem idealnej kompresji równałby się problemowi doskonałego rozpoznawania wzorów? Jaką formę przyjąłby wynik takiej kompresji? Faktoryzacja do liczb pierwszych? Coś innego? Czy posiadanie takiego algorytmu oznaczałoby, że problem AI został złamany?

Jako pytanie poboczne, czy były udane próby wykorzystania uczenia maszynowego do kompresji danych?

Odpowiedzi:

Istnieje matematyczny dowód, że na twoje pytanie nie można odpowiedzieć w ogóle. Najlepsza możliwa kompresja nie jest obliczalna. Widzieć Złożoność Kołmogorowa.

Kompresja działa tylko wtedy, gdy dane można w jakiś sposób modelować w celu ujawnienia nadmiarowości.