Колмогоровская сложность и ее применение в машинном обучении

Представляемые в данной статье материалы носят, главным образом, обзорный ха-
рактер. Целью работы работы является достаточно полное представление возмож-
ностей математического аппарата алгоритмической сложности и случайности для
применения в машинном обучении. Тем не менее, в статье содержатся и новые ре-
зультаты: теоремы о точных компрессорах и декомпрессорах, подход к определению
момента остановки процедуры обучения на основе сложностного аналога правила
Байеса и другие.