Seminaria w Instytucie Podstaw Informatyki PAN

Streszczenie (autorskie):

Przedstawimy elementy teorii kompresji i predykcji uniwersalnej dla procesów stacjonarnych. Rozpoczniemy od prostych przykładów procesów Markowa i ogólniejszych definicji procesów stacjonarnych i ergodycznych. Opowiemy o twierdzeniach Birkhoffa i Azumy, o nierównościach Krafta i Pinskera. Przedyskutujemy parametry procesu takie jak intensywność entropii i nieprzewidywalność. Wytłumaczymy, czemu minimalizacja krosentropii prowadzi do minimalizacji stopy błędu. Skonstruujemy także przykładową uniwersalną miarę prawdopodobieństwa PPM (Prediction by Partial Matching) indukującą kod i predyktor uniwersalny. Wspomnimy o problemie efektywizacji i losowości algorytmicznej. Nie będziemy stronić od wzorów, ale postaramy się przedstawiać intuicje, nie zamiatając pod dywan ograniczeń rozpatrywanej teorii.