检索结果-内蒙古大学图书馆

A Generalized Characterization of algorithmic probability

THEORY OF COMPUTING SYSTEMS 2017年第4期61卷 1337-1352页

作者： Sterkenburg, Tom F. Ctr Wiskunde & Informat Algorithms & Complex Grp Amsterdam Netherlands Univ Groningen Fac Philosophy Groningen Netherlands

An a priori semimeasure (also known as "algorithmic probability" or "the Solomonoff prior" in the context of inductive inference) is defined as the transformation, by a given universal monotone Turing machine, of the uniform measure on the infinite strings. It is shown in this paper that the class of a priori semimeasures can equivalently be defined as the class of transformations, by all compatible universal monotone Turing machines, of any continuous computable measure in place of the uniform measure. Some consideration is given to possible implications for the association of algorithmic probability with certain foundational principles of statistics.

关键词： algorithmic probability A priori semimeasure Semicomputable semimeasures Monotone turing machines Principle of indifference Occam's razor

来源：评论

学校读者我要写书评

暂无评论

Stationary algorithmic probability

引用

THEORETICAL COMPUTER SCIENCE 2010年第1期411卷 113-130页

作者： Mueller, Markus Tech Univ Berlin Inst Math D-10623 Berlin Germany

Kolmogorov complexity and algorithmic probability are defined only up to an additive resp. multiplicative constant, since their actual values depend on the choice of the universal reference computer. In this paper, we analyze a natural approach to eliminate this machine-dependence. Our method is to assign algorithmic probabilities to the different computers themselves, based oil the idea that "unnatural" computers should be hard to emulate. Therefore, we study the Markov process of universal Computers randomly emulating each other. The corresponding stationary distribution, if it existed, would give a natural and machine-independent probability measure on the computers, and also oil the binary strings. Unfortunately, we show that no stationary distribution exists on the set of all computers;thus, this method cannot eliminate machine-dependence. Moreover, we show that the reason for failure has a clear and interesting physical interpretation, suggesting that every other conceivable attempt to get rid of those additive constants must fail in principle, too. However, we show that restricting to some subclass of computers might help to get rid of some amount of machine-dependence in some situations, and the resulting stationary Computer and string probabilities have beautiful properties. (C) 2009 Elsevier B.V. All rights reserved.

关键词： algorithmic probability Kolmogorov complexity Markov chain Emulation Emulation complexity

来源：评论

学校读者我要写书评

暂无评论

The Semimeasure Property of algorithmic probability - "Feature" or "Bug"?

The Semimeasure Property of Algorithmic Probability - "Featu...

引用

Ray Solomonoff 85th Memorial Conference

作者： Campbell, Douglas Univ Canterbury Philosophy Programme Christchurch 8041 New Zealand

ISBN: (纸本)9783642449581;9783642449574

An unknown process is generating a sequence of symbols, drawn from an alphabet, A. Given an initial segment of the sequence, how can one predict the next symbol? Ray Solomonoff's theory of inductive reasoning rests on the idea that a useful estimate of a sequence's true probability of being outputted by the unknown process is provided by its algorithmic probability (its probability of being outputted by a species of probabilistic Turing machine). However algorithmic probability is a "semimeasure": i.e., the sum, over all x is an element of A, of the conditional algorithmic probabilities of the next symbol being x, may be less than 1. Solomonoff thought that algorithmic probability must be normalized, to eradicate this semimeasure property, before it can yield acceptable probability estimates. This paper argues, to the contrary, that the semimeasure property contributes substantially, in its own right, to the power of an algorithmic-probability-based theory of induction, and that normalization is unnecessary.

关键词： algorithmic probability sequence prediction inductive reasoning Solomonoff induction Solomonoff normalization semimeasure convergence theorem

来源：评论

学校读者我要写书评

暂无评论

Practical algorithmic probability: An Image Inpainting Example

Practical Algorithmic Probability: An Image Inpainting Examp...

引用

6th International Conference on Machine Vision (ICMV)

作者： Potapov, Alexey Scherbakov, Oleg Zhdanov, Innokentii Natl Res Univ Informat Technol St Petersburg Russia

ISBN: (纸本)9780819499967

Possibility of practical application of algorithmic probability is analyzed on an example of image inpainting problem that precisely corresponds to the prediction problem. Such consideration is fruitful both for the theory of universal prediction and practical image inpaiting methods. Efficient application of algorithmic probability implies that its computation is essentially optimized for some specific data representation In this paper, we considered one image representation, namely spectral representation, for which an image inpainting algorithm is proposed based on the spectrum entropy criterion. This algorithm showed promising results in spite of very simple representation The same approach can be used for introducing ALP-based criterion for more powerful image representations.

关键词： algorithmic probability image inpainting spectrum entropy

来源：评论

学校读者我要写书评

暂无评论

On the Application of algorithmic probability to Autoregressive Models

On the Application of Algorithmic Probability to Autoregress...

引用

Ray Solomonoff 85th Memorial Conference

作者： Solomonoff, Ray J. Saleeby, Elias G. Alfaisal Univ Riyadh Saudi Arabia

ISBN: (纸本)9783642449581;9783642449574

Typically, the first step in carrying out predictions is to develop an inductive model. In many instances, the best model is used, and it is often selected based on certain relevant criteria that may possibly ignore some of the model uncertainties. The Bayesian approach to model selection uses a weighted average of a class of models thereby overcoming some of the uncertainties associated with selecting the best model. This approach is referred to in the literature as the Bayesian Model Averaging (BMA) approach. It turns out that this approach has significant overlap with the theory of algorithmic probability (ALP) developed by R. J. Solomonoff in the early 1960s. The purpose of this article is to first highlight this connection by applying ALP to a set of nested stationary autoregressive time series models, and to give an algorithm to compute "relative weights" of models. This reveals, although empirically, a model weight that can be compared with the Schwarz Bayesian Selection criterion (BIC or SIC). We then develop an elementary algorithm of the Monte Carlo type to evaluate multidimensional integrals over stability domains, and use it to compute what we call the "trimmed weights".

关键词： algorithmic probability predictive probability model weights information criteria autoregressive time series Monte Carlo method

来源：评论

学校读者我要写书评

暂无评论

Simplicity bias, algorithmic probability, and the random logistic map

引用

PHYSICA D-NONLINEAR PHENOMENA 2024年 463卷

作者： Hamzi, Boumediene Dingle, Kamaludin Caltech Dept Comp & Math Sci Pasadena CA 91125 USA Alan Turing Inst London England Gulf Univ Sci & Technol Ctr Appl Math & Bioinformat Dept Math & Nat Sci Mubarak Al Abdullah Kuwait

Simplicity bias is an intriguing phenomenon prevalent in various input-output maps, characterized by a preference for simpler, more regular, or symmetric outputs. Notably, these maps typically feature high- probability outputs with simple patterns, whereas complex patterns are exponentially less probable. This bias has been extensively examined and attributed to principles derived from algorithmic information theory and algorithmic probability. In a significant advancement, it has been demonstrated that the renowned logistic map x(k+1) = mu x(k)(1 - x(k)), a staple in dynamical systems theory, and other one-dimensional maps exhibit simplicity bias when conceptualized as input-output systems. Building upon this work, our research delves into the manifestations of simplicity bias within the random logistic map, specifically focusing on scenarios involving additive noise. This investigation is driven by the overarching goal of formulating a comprehensive theory for the prediction and analysis of time series. Our primary contributions are multifaceted. We discover that simplicity bias is observable in the random logistic map for specific ranges of mu and noise magnitudes. Additionally, we find that this bias persists even with the introduction of small measurement noise, though it diminishes as noise levels increase. Our studies also revisit the phenomenon of noise-induced chaos, particularly when mu = 3.83, revealing its characteristics through complexity-probability plots. Intriguingly, we employ the logistic map to illustrate a paradoxical aspect of data analysis: more data adhering to a consistent trend can occasionally lead to reduced confidence in extrapolation predictions, challenging conventional wisdom. We propose that adopting a probability-complexity perspective in analyzing dynamical systems could significantly enrich statistical learning theories related to series prediction and analysis. This approach not only facilitates a deeper understanding of simplici

关键词： Random dynamical systems algorithmic probability Simplicity bias Time series Machine learning

来源：评论

学校读者我要写书评

暂无评论

Multiclass classification utilising an estimated algorithmic probability prior

引用

PHYSICA D-NONLINEAR PHENOMENA 2023年 448卷

作者： Dingle, Kamaludin Batlle, Pau Owhadi, Houman CALTECH Dept Comp & Math Sci Pasadena CA 91125 USA Gulf Univ Sci & Technol Ctr Appl Math & Bioinformat Dept Math & Nat Sci Hawally Kuwait

Methods of pattern recognition and machine learning are applied extensively in science, technology, and society. Hence, any advances in related theory may translate into large-scale impact. Here we explore how algorithmic information theory, especially algorithmic probability, may aid in a machine learning task. We study a multiclass supervised classification problem, namely learning the RNA molecule sequence-to-shape map, where the different possible shapes are taken to be the classes. The primary motivation for this work is a proof of concept example, where a concrete, well-motivated machine learning task can be aided by approximations to algorithmic probability. Our approach is based on directly estimating the class (i.e., shape) probabilities from shape complexities, and using the estimated probabilities as a prior in a Gaussian process learning problem. Naturally, with a large amount of training data, the prior has no significant influence on classification accuracy, but in the very small training data regime, we show that using the prior can substantially improve classification accuracy. To our knowledge, this work is one of the first to demonstrate how algorithmic probability can aid in a concrete, real-world, machine learning problem.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Machine learning Multiclass classification Gaussian processes algorithmic probability RNA

来源：评论

学校读者我要写书评

暂无评论

Predicting phenotype transition probabilities via conditional algorithmic probability approximations

引用

JOURNAL OF THE ROYAL SOCIETY INTERFACE 2022年第197期19卷 20220694-20220694页

作者： Dingle, Kamaludin Novev, Javor K. Ahnert, Sebastian E. Louis, Ard A. Univ Cambridge Dept Chem Engn & Biotechnol Cambridge CB2 1TN Cambs England CALTECH Dept Comp & Math Sci Pasadena CA 91125 USA Gulf Univ Sci & Technol Ctr Appl Math & Bioinformat CAMB Dept Math & Nat Sci Mubarak Al Abdullah 32093 Kuwait Univ Oxford Rudolf Peierls Ctr Theoret Phys Dept Phys Oxford OX1 2JD Oxon England

Unravelling the structure of genotype-phenotype (GP) maps is an important problem in biology. Recently, arguments inspired by algorithmic information theory (AIT) and Kolmogorov complexity have been invoked to uncover simplicity bias in GP maps, an exponentially decaying upper bound in phenotype probability with the increasing phenotype description] complexity. This means that phenotypes with many genotypes assigned via the GP map must be simple, while complex phenotypes must have few genotypes assigned. Here, we use similar arguments to bound the probability P(x -> y) that phenotype x, upon random genetic mutation, transitions to phenotype y. The bound is P(x -> y) less than or similar to 2(-a (K) over tilde (y vertical bar x)-b), where (K) over tilde (y vertical bar x) is the estimated conditional complexity of y given x, quantifying how much extra information is required to make y given access to x. This upper bound is related to the conditional form of algorithmic probability from AIT. We demonstrate the practical applicability of our derived bound by predicting phenotype transition probabilities (and other related quantities) in simulations of RNA and protein secondary structures. Our work contributes to a general mathematical understanding of GP maps and may facilitate the prediction of transition probabilities directly from examining phenotype themselves, without utilizing detailed knowledge of the GP map.

关键词： genotype-phenotype maps evolution complexity algorithmic probability

来源：评论

学校读者我要写书评

暂无评论

The probability of "undefined" (non-converging) output in generating the universal probability distribution

引用

INFORMATION PROCESSING LETTERS 2008年第6期106卷 238-240页

作者： Solomonoff, Ray J. Univ London Comp Learning Res Ctr London WC1E 7HU England IDSIA CH-6928 Manno Lugano Switzerland

In order to generate a universal probability distribution to extrapolate a binary string x of length i, we feed random bits into a universal device, M. When we find an input string that gives an output matching x, we continue the successful input with random bits until M produces a zero or one as output. The relative probabilities of these two continuations can give a normalized prediction for the probability of the symbol following x. There is, however, a probability, Pi+l (u) that the continued random input string will not generate any output for the (i + l)th symbol. We will show E-mu Sigma(n)(i=l) P-i((u)) <= k(mu) ln 2. Here E-mu is the expected value with respect to mu, the probability distribution that created x. k(mu) is the Kolmogorov complexity of mu with respect to M. n is any positive integer. Usually we do not know mu and so we do not know k(mu). However, if mu is the uniform distribution, we can usually find a good upper bound for k(mu). Published by Elsevier B.V.

关键词： algorithmic probability analysis of algorithms halting problem incomputable Kolmogorov complexity normalization theory of computation Turing machine universal probability distribution universal Turing machine

来源：评论

学校读者我要写书评

暂无评论

Ray Solomonoff and the New probability

Ray Solomonoff and the New Probability

引用

Ray Solomonoff 85th Memorial Conference

作者： Solomonoff, Grace Oxbridge Res Cambridge MA 02140 USA

ISBN: (纸本)9783642449581;9783642449574

This is the story of Ray Solomonoff's Life and Times. He was there at Dartmouth in 1956 when Artificial Intelligence was first given its name, and took part in the major events during this unique era right up to his death in 2009. His invention in 1960 of algorithmic probability, with its multiple descriptions of data, led to better ways of handling data and prediction for machine learning. The theorems that are part of his discovery lie at the heart of algorithmic Information Theory. Ray championed probability in AI during the decades it was unpopular and lived to see a renaissance in systems that learn and reason using probability. The story of his life is the story of a great adventure.

关键词： Solomonoff Artificial Intelligence algorithmic probability algorithmic Information Theory Inductive Inference Kolmogorov Complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：