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

Bridging algorithmic information theory and Machine Learning: A new approach to kernel learning

PHYSICA D-NONLINEAR PHENOMENA 2024年 464卷

作者： Hamzi, Boumediene Hutter, Marcus Owhadi, Houman Caltech Dept Comp & Math Sci Pasadena CA USA Alan Turing Inst London England Gulf Univ Sci & Technol Dept Math Kuwait Kuwait Google DeepMind London England Australian Natl Univ Canberra Australia

Machine Learning (ML) and algorithmic information theory (AIT) look at Complexity from different points of view. We explore the interface between AIT and Kernel Methods (that are prevalent in ML) by adopting an AIT perspective on the problem of learning kernels from data, in kernel ridge regression, through the method of Sparse Kernel Flows. In particular, by looking at the differences and commonalities between Minimal Description Length (MDL) and Regularization in Machine Learning (RML), we prove that the method of Sparse Kernel Flows is the natural approach to adopt to learn kernels from data. This approach aligns naturally with the MDL principle, offering a more robust theoretical basis than the existing reliance on cross -validation. The study reveals that deriving Sparse Kernel Flows does not require a statistical approach;instead, one can directly engage with code -lengths and complexities, concepts central to AIT. Thereby, this approach opens the door to reformulating algorithms in machine learning using tools from AIT, with the aim of providing them a more solid theoretical foundation.

关键词： Machine Learning algorithmic information theory Regression Sparse Kernel Flows Minimum Description Length principle Compression

来源：评论

学校读者我要写书评

暂无评论

AN algorithmic information theory CHALLENGE TO INTELLIGENT DESIGN

引用

ZYGON 2014年第1期49卷 42-65页

作者： Devine, Sean Victoria Univ Wellington Sch Management Wellington 6140 New Zealand

William Dembski claims to have established a decision process to determine when highly unlikely events observed in the natural world are due to Intelligent Design. This article argues that, as no implementable randomness test is superior to a universal Martin-Lof test, this test should be used to replace Dembski's decision process. Furthermore, Dembski's decision process is flawed, as natural explanations are eliminated before chance. Dembski also introduces a fourth law of thermodynamics, his law of conservation of information, to argue that information cannot increase by natural processes. However, this article, using algorithmic information theory, shows that this law is no more than the second law of thermodynamics. The article concludes that any discussions on the possibilities of design interventions in nature should be articulated in terms of the algorithmic information theory approach to randomness and its robust decision process.

关键词： algorithmic entropy algorithmic information theory fourth law of thermodynamics Intelligent Design randomness test

来源：评论

学校读者我要写书评

暂无评论

An algorithmic information theory of consciousness

引用

NEUROSCIENCE OF CONSCIOUSNESS 2017年第1期3卷 nix019页

作者： Ruffini, Giulio Starlab Barcelona Avda Tibidabo 47bis Barcelona 08035 Spain Neuroelect Corp 210 Broadway Cambridge MA 02139 USA

Providing objective metrics of conscious state is of great interest across multiple research and clinical fields-from neurology to artificial intelligence. Here we approach this challenge by proposing plausible mechanisms for the phenomenon of structured experience. In earlier work, we argued that the experience we call reality is a mental construct derived from information compression. Here we show that algorithmic information theory provides a natural framework to study and quantify consciousness from neurophysiological or neuroimaging data, given the premise that the primary role of the brain is information processing. We take as an axiom that "there is consciousness" and focus on the requirements for structured experience: we hypothesize that the existence and use of compressive models by cognitive systems, e. g. in biological recurrent neural networks, enables and provides the structure to phenomenal experience. Self-awareness is seen to arise naturally (as part of a better model) in cognitive systems interacting bidirectionally with the external world. Furthermore, we argue that by running such models to track data, brains can give rise to apparently complex (entropic but hierarchically organized) data. We compare this theory, named KT for its basis on the mathematical theory of Kolmogorov complexity, to other information-centric theories of consciousness. We then describe methods to study the complexity of the brain's output streams or of brain state as correlates of conscious state: we review methods such as (i) probing the brain through its input streams (e. g. event-related potentials in oddball paradigms or mutual algorithmic information between world and brain), (ii) analyzing spontaneous brain state, (iii) perturbing the brain by non-invasive transcranial stimulation, and (iv) quantifying behavior (e. g. eye movements or body sway).

关键词： algorithmic information theory Kolmogorov complexity cellular automata neural networks complexity presence consciousness structured experience neural correlates of consciousness PCI LZW tCS tACS TMS EEG MEG fMRI AI

来源：评论

学校读者我要写书评

暂无评论

Debates: Does information theory Provide a New Paradigm for Earth Science? Sharper Predictions Using Occam's Digital Razor

引用

WATER RESOURCES RESEARCH 2020年第2期56卷 e2019WR026471-e2019WR026471页

作者： Weijs, Steven. V. Ruddell, Benjamin. L. Univ British Columbia Dept Civil Engn Vancouver BC Canada No Arizona Univ Sch Informat Comp & Cyber Syst Flagstaff AZ 86011 USA

Occam's Razor is a bedrock principle of science philosophy, stating that the simplest hypothesis (or model) is preferred, at any given level of model predictive performance. A modern restatement often attributed to Einstein explains, "Everything should be made as simple as possible, but not simpler." Using principles from (algorithmic) information theory, both model descriptive performance and model complexity can be quantified in bits. This quantification yields a Pareto-style trade-off between model complexity (length of the model program in bits) and model performance (information loss in bits, or the missing information, needed to describe the original observations). Model complexity and performance can be collapsed to one single measure of lossless model size, which, when minimized, leads to optimal model complexity versus loss trade-off for generalization and prediction. Our view puts both simple data-driven and complex physical-process-based models on a continuum, in the sense that both describe patterns in observed data in compressed form, with different degrees of generality, model complexity, and descriptive performance. information theory-based assessment of compression performance with fair and meaningful accounting for model complexity will enable us to best compare and combine the strengths of physics knowledge and data-driven modeling for a given problem, given the availability of data. "Suppose we draw a set of points on paper in a totally random manner" ..."I am saying it is possible to find a geometric line whose notation is constant and uniform, following a certain law, that will pass through all points, and in the sameorder they were drawn." ... "But if that law is strongly composed,the thing that conforms to it should be seen as irregular"Gottfried Wilhelm Leibniz, 1686: Discours de metaphysique V, VI (from French)

关键词： algorithmic information theory Occam's razor physically based modeling model complexity data compression data-driven modeling

来源：评论

学校读者我要写书评

暂无评论

Randomness, computability, and density

引用

SIAM JOURNAL ON COMPUTING 2002年第4期31卷 1169-1183页

作者： Downey, R Hirschfeldt, DR Nies, A Victoria Univ Wellington Sch Math & Comp Sci Wellington New Zealand Univ Chicago Dept Math Chicago IL 60637 USA

We study effectively given positive reals ( more specifically, computably enumerable reals) under a measure of relative randomness introduced by Solovay [ manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1975] and studied by Calude, Hertling, Khoussainov, and Wang [Theoret. Comput. Sci., 255 ( 2001), pp. 125 149], Calude [ Theoret. Comput. Sci., 271 ( 2002), pp. 3 14], Kucera and Slaman [SIAM J. Comput., 31 ( 2002), pp. 199 211], and Downey, Hirschfeldt, and LaForte [ Mathematical Foundations of Computer Science 2001, Springer-Verlag, Berlin, 2001, pp. 316 327], among others. This measure is called domination or Solovay reducibility and is defined by saying that alpha dominates beta if there are a constant c and a partial computable function phi such that for all positive rationals q < alpha we have phi(q) down arrow < beta and beta-phi(q) less than or equal to c(alpha-q). The intuition is that an approximating sequence for alpha generates one for beta whose rate of convergence is not much slower than that of the original sequence. It is not hard to show that if dominates, then the initial segment complexity of alpha is at least that of beta. In this paper we are concerned with structural properties of the degree structure generated by Solovay reducibility. We answer a natural question in this area of investigation by proving the density of the Solovay degrees. We also provide a new characterization of the random computably enumerable reals in terms of splittings in the Solovay degrees. Specifically, we show that the Solovay degrees of computably enumerable reals are dense, that any incomplete Solovay degree splits over any lesser degree, and that the join of any two incomplete Solovay degrees is incomplete, so that the complete Solovay degree does not split at all. The methodology is of some technical interest, since it includes a priority argument in which the injuries are themselves controlled by randomness considerations.

关键词： randomness computably enumerable reals algorithmic information theory Kolmogorov complexity Solovay reducibility

来源：评论

学校读者我要写书评

暂无评论

algorithmically independent sequences

引用

information AND COMPUTATION 2010年第3期208卷 292-308页

作者： Calude, Cristian S. Zimand, Marius Towson Univ Dept Comp & Informat Sci Baltimore MD 21204 USA Univ Auckland Dept Comp Sci Auckland 1 New Zealand

Two objects are independent if they do not affect each other Independence is well-understood in classical information theory, but less in algorithmic information theory. Working in the framework of algorithmic information theory, the paper proposes two types of independence for arbitrary infinite binary sequences and studies their properties. Our two proposed notions of independence have some of the Intuitive properties that one naturally expects. For example, for every sequence x, the set of sequences that are independent with x has measure one For both notions of independence we investigate to what extent pairs of independent sequences, can be effectively constructed via Turing reductions (from one or more input sequences) In this respect, we prove several impossibility results For example. it is shown that there is no effective way of producing from an arbitrary sequence with positive constructive Hausdorff dimension two sequences that are independent (even in the weaker type of independence) and have super-logarithmic complexity Finally, a few conjectures and open questions are discussed. (C) 2009 Elsevier Inc All rights reserved.

关键词： algorithmic information theory Independence Mutual information Randomness

来源：评论

学校读者我要写书评

暂无评论

Ergodic theorems for individual random sequences

引用

THEORETICAL COMPUTER SCIENCE 1998年第2期207卷 343-361页

作者： V'yugin, VV Russian Acad Sci Inst Informat Transmiss Problems Moscow 101447 Russia

In the framework of the Kolmogorov's approach to the substantiation of the probability theory and information theory on the base of the theory of algorithms we try to formulate probabilistic laws, i.e. statements of the form P{omega\A(omega)} = 1, where A(omega) is some formula, in "pointwise" form "if omega is random then A(omega) holds". Nevertheless, not all proofs of such laws can be directly translated into the algorithmic form. In [11] two examples have been distinguished - Birkhoff's [2] ergodic theorem and Shannon-McMillan-Breiman theorem of information theory [1]. In this paper an analysis of algorithmic effectiveness of these theorems is given. We prove that Birkhoff's ergodic theorem is indeed in some strong sense "nonconstrutive". At the same time the claim to formulate probabilistic laws for algorithmically random sequences is not so restrictive. We present the versions of these laws for individual random sequences. (C) 1998 Published by Elsevier Science B.V. All rights reserved.

关键词： individual random sequence Birkhoff's ergodic theorem Shannon-McMillan-Breiman theorem Kolmogorov complexity algorithmic information theory

来源：评论

学校读者我要写书评

暂无评论

Asymptotics of discrete MDL for online prediction

引用

IEEE TRANSACTIONS ON information theory 2005年第11期51卷 3780-3795页

作者： Poland, J Hutter, M Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido 0600814 Japan IDSIA CH-6928 Manno Lugan Switzerland

Minimum description length (MDL) is an important principle for t-induction and prediction, with strong relations to optimal Bayesian learning. This paper deals with learning processes which are independent and identically distributed (i.i.d.) by means of two-part MDL, where the underlying model class is countable. We consider the online learning framework, i.e., observations come in one by one, and the predictor is allowed to update its state of mind after each time step. We identify two ways of predicting by MDL for this setup, namely, a static and a dynamic one. (A third variant, hybrid MDL, will turn out inferior.) We will prove that under the only assumption that the data is generated by a distribution contained in the model class, the MDL predictions converge to the true values almost surely. This is accomplished by proving finite bounds on the quadratic, the Hellinger, and the Kullback-Leibler loss of the MDL learner, which are, however, exponentially worse than for Bayesian prediction. We demonstrate that these bounds are sharp, even for model classes containing only Bernoulli distributions. We show how these bounds imply regret bounds for arbitrary loss functions. Our results apply to a wide range of setups, namely, sequence prediction, pattern classification, regression, and universal induction in the sense of algorithmic information theory among others.

关键词： algorithmic information theory classification consistency discrete model class loss bounds minimum description length (MDL) regression sequence prediction stabilization universal induction

来源：评论

学校读者我要写书评

暂无评论

Improving NCD accuracy by combining document segmentation and document distortion

引用

KNOWLEDGE AND information SYSTEMS 2014年第1期41卷 223-245页

作者： Granados, Ana Martinez, Rafael Camacho, David de Borja Rodriguez, Francisco Univ Autonoma Madrid Dept Comp Sci Escuela Politecn Super Madrid Spain

Compression distances have been applied to a broad range of domains because of their parameter-free nature, wide applicability and leading efficacy. However, they have a characteristic that can be a drawback when applied under particular circumstances. Said drawback is that when they are used to compare two very different-sized objects, they do not consider them to be similar even if they are related by a substring relationship. This work focuses on addressing this issue when compression distances are used to calculate similarities between documents. The approach proposed in this paper consists of combining document segmentation and document distortion. On the one hand, it is proposed to use document segmentation to tackle the above mentioned drawback. On the other hand, it is proposed to use document distortion to help compression distances to obtain more reliable similarities. The results show that combining both techniques provides better results than not applying them or applying them separately. The said results are consistent across datasets of diverse nature.

关键词： algorithmic information theory Data compression information filtering Word removal Document representation

来源：评论

学校读者我要写书评

暂无评论

On Empirical Meaning of Randomness with Respect to Parametric Families of Probability Distributions

引用

theory OF COMPUTING SYSTEMS 2012年第2期50卷 296-312页

作者： V'yugin, Vladimir Russian Acad Sci Inst Informat Transmiss Problems Moscow 127994 Russia

We study the a priori semimeasure of sets of P(theta)-random infinite sequences, where P(theta) is a family of probability distributions depending on a real parameter theta. In the case when for a computable probability distribution P(theta) an effectively strictly consistent estimator exists, we show that Levin's a priory semimeasure of the set of all P(theta)-random sequences is positive if and only if the parameter theta is a computable real number. We show that the a priory semimeasure of the set U(theta)I(theta), where I(theta) is the set of all P(theta)-random sequences and the union is taken over all algorithmically non-random theta, is positive.

关键词： Martin-Lof random sequences A priory semimeasure Probabilistic machines Bernoully sequences Parametric families of probability distributions algorithmic information theory Turing degrees

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：