• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Algorithmic Statistics: Normal Objects and Universal Models
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
May 25, 2026
HSE Scientists Train Neural Network to 'Hear' Faults in Electric Motors
Researchers at the AI and Digital Science Institute of the HSE Faculty of Computer Science have developed a new method—the Signature-Guided Data Augmentation (SGDA) framework—that achieves 99% accuracy in motor fault detection and 86% accuracy in fault classification. The application of this approach can reduce industrial equipment repair costs, minimise downtime, and improve production safety. The study results have been published in Engineering Applications of Artificial Intelligence.
May 25, 2026
'The Humanities Serve as a Conscience'
Maria Mizernaia studies Soviet literature and the history of book publishing. In this interview for the HSE Young Scientists project, she discusses plans to publish a novel about besieged Leningrad, AI-provoked reflections on what it means to be human, and how novels can help satisfy our dopamine hunger.
May 25, 2026
Is It Possible to Predict a Citys Life Based on the Shape of Its Neighbourhoods?
Is it possible to predict, based on the configuration of streets and buildings, where a café will open or where traffic congestion will occur? Participants in the Spatial Analysis and Modelling of Urban Processes research and study group use open data and machine learning to identify universal patterns. Alexander Sheludkov and Eduard Somov discuss the purpose of comparing cities, the need for new forms of urban statistics, and how open data is transforming approaches to urban studies.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Algorithmic Statistics: Normal Objects and Universal Models

P. 280–293.
Milovanov A.

In algorithmic statistics quality of a statistical hypothesis (a model) P for a data x is measured by two parameters: Kolmogorov complexity of the hypothesis and the probability P(x). A class of models SijSij that are the best at this point of view, were discovered. However these models are too abstract. To restrict the class of hypotheses for a data, Vereshchaginintroduced a notion of a strong model for it. An object is called normal if it can be explained by using strong models not worse than without this restriction. In this paper we show that there are “many types” of normal strings. Our second result states that there is a normal object x such that all models SijSij are not strong for x. Our last result states that every best fit strong model for a normal object is again a normal object.

Language: English
DOI
Text on another site
Keywords: algorithmic statisticsminimum description lengthdenoisingAlgorithmic sufficient statisticsstochastic objects
Publication based on the results of:
Теоретическая информатика (2016)

In book

Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings
Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings
Vol. 9691: Lecture Notes in Computer Science. , Switzerland: Springer, 2016.
Similar publications
Kolmogorov’s Last Discovery? (Kolmogorov and Algorithmic Statistics)
Semenov A., Shen A., Vereshchagin N., Theory of Probability and its Applications, USA 2024 Vol. 68 No. 4 P. 582–606
The definition of descriptional complexity of finite objects suggested by Kolmogorov and other authors in the mid-1960s is now well known. In addition, Kolmogorov pointed out some approaches to a more fine-grained classification of finite objects, such as the resource-bounded complexity (1965), structure function (1974), and the notion of $(\alpha,\beta)$-stochasticity (1981). Later it turned out ...
Added: January 16, 2025
Real-time Streaming Wave-U-Net with Temporal Convolutions for Multichannel Speech Enhancement
Sokolov A., / Series Computer Science "arxiv.org". 2021.
In this paper we describe our work that we have done to participate in Task1 of ConferencingSpeech2021 challenge. This task set a goal to develop the solution for multi-channel speech enhancement in a real-time manner. We propose a novel system for streaming speech enhancement. We employ Wave-U-Net architecture with temporal convolutions in encoder and decoder. ...
Added: September 26, 2021
Algorithmic Statistics: Forty Years Later.
Shen A., Vereshchagin N., , in: Computability and Complexity.: Berlin: Springer, 2017. P. 669–737.
Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some statistical models are better than others. After this notion of a "good model" is introduced, a natural question arises: it is possible that for some piece of data there ...
Added: October 26, 2018
On Algorithmic Statistics for Space-bounded Algorithms
Milovanov A., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 833–848
Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we ...
Added: October 17, 2018
Algorithmic Statistics and Prediction for Polynomial Time-Bounded Algorithms
Milovanov A., , in: Sailing Routes in the World of Computation.: Springer, 2018. P. 287–296.
Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice as is because Kolmogorov complexity is not computable. In recent years resource-bounded ...
Added: September 4, 2018
Fast Approximate Energy Minimization with Label Costs
Delong A., Osokin A., Isack H. et al., International Journal of Computer Vision 2012 Vol. 96 No. 1 P. 1–27
The α-expansion algorithm has had a significant impact in computer vision due to its generality, effectiveness, and speed. It is commonly used to minimize energies that involve unary, pairwise, and specialized higher-order terms. Our main algorithmic contribution is an extension of α-expansion that also optimizes “label costs” with well-characterized optimality bounds. Label costs penalize a solution based ...
Added: October 18, 2017
On Algorithmic Statistics for Space-Bounded Algorithms
Milovanov A., , in: Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017)Vol. 10304.: Luxemburg: Springer, 2017. P. 232–244.
Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice because Kolmogorov complexity is not computable. In this paper we develop algorithmic ...
Added: October 15, 2017
Algorithmic Statistics: Forty Years Later.
Vereshchagin N., Shen A., Lecture Notes in Computer Science 2017 Vol. 10010 P. 669–737
Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some statistical models are better than others. After this notion of a "good model" is introduced, a natural question arises: it is possible that for some piece of data there ...
Added: February 13, 2017
Algorithmic Minimal Sufficient Statistics: a New Approach
Vereshchagin N., Theory of Computing Systems 2016 Vol. 58 No. 3 P. 463–481
We introduce the notion of a strong sufficient statistic for a given data string. We show that strong sufficient statistics have better properties than just sufficient statistics. We prove that there are “strange” data strings, whose minimal strong sufficient statistic have much larger complexity than the minimal sufficient statistic. ...
Added: February 7, 2017
Algorithmic Statistics, Prediction and Machine Learning
Milovanov A., , in: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) Leibniz International Proceedings in Informatics (LIPIcs).: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2016. Ch. 54 P. 1–13.
Algorithmic statistics considers the following problem: given a binary string x (e.g., some experimental data), find a “good” explanation of this data. It uses algorithmic information theory to define formally what is a good explanation. In this paper we extend this framework in two directions. First, the explanations are not only interesting in themselves but also used for prediction: we want to ...
Added: June 27, 2016
Some Properties of Antistochastic Strings
Milovanov A., , in: Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015Vol. 9139.: Springer, 2015. P. 339–349.
Antistochastic strings are those strings that do not have any reasonable statistical explanation. We establish the follow property of such strings: every antistochastic string x is “holographic” in the sense that it can be restored by a short program from any of its part whose length equals the Kolmogorov complexity of x. Further we will ...
Added: June 27, 2016
Some Properties of Antistochastic Strings
Milovanov A., Theory of Computing Systems 2017 Vol. 61 No. 2 P. 521–535
Algorithmic statistics is a part of algorithmic information theory (Kolmogorov complexity theory) that studies the following task: given a finite object x (say, a binary string), find an `explanation' for it, i.e., a simple finite set that contains x and where x is a `typical element'. Both notions (`simple' and `typical') are defined in terms ...
Added: June 27, 2016
A combinatorial formula for affine Hall–Littlewood functions via a weighted Brion theorem
Feigin B. L., Makhlin I., Selecta Mathematica, New Series 2016 Vol. 22 No. 3 P. 1703–1747
We present a new combinatorial formula for Hall–Littlewood functions associated with the affine root system of type (Formula presented.), i.e., corresponding to the affine Lie algebra (Formula presented.). Our formula has the form of a sum over the elements of a basis constructed by Feigin, Jimbo, Loktev, Miwa and Mukhin in the corresponding irreducible representation. ...
Added: May 4, 2016
Sophistication vs Logical Depth
Antunes L., Bauwens B. F., Souto A. et al., Theory of Computing Systems 2017 Vol. 60 No. 2 P. 280–298
Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable function that defines a two-part description for the string that is shortest within some precision; the second can be defined as the minimal computation time of a program ...
Added: May 4, 2016
Algorithmic Statistics Revisited
Vereshchagin N., Shen A., , in: Measures of Complexity. Festschrift for Alexey Chervonenkis.: Springer, 2015. P. 235–252.
A survey of main results in algorithmic statistics ...
Added: March 3, 2016
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit