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

Bridging algorithmic information theory and Machine Learning: Clustering, density estimation, Kolmogorov complexity-based kernels, and kernel learning in unsupervised learning

引用

PHYSICA D-NONLINEAR PHENOMENA 2025年 476卷

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

Machine Learning (ML) and algorithmic information theory (AIT) offer distinct yet complementary approaches to understanding and addressing complexity. This paper investigates the synergy between these disciplines in two directions: AIT for Kernel Methods and Kernel Methods for AIT. In the former, we explore how AIT concepts inspire the design of kernels that integrate principles like relative Kolmogorov complexity and normalized compression distance (NCD). We propose a novel clustering method utilizing the Minimum Description Length principle, implemented via K-means and Kernel Mean Embedding (KME). Additionally, we apply the Loss Rank Principle (LoRP) to learn optimal kernel parameters in the context of Kernel Density Estimation (KDE), thereby extending the applicability of AIT-inspired techniques to flexible, nonparametric models. In the latter, we show how kernel methods can be used to approximate measures such as NCD and algorithmic Mutual information (AMI), providing new tools for compression-based analysis. Furthermore, we demonstrate that the Hilbert-Schmidt Independence Criterion (HSIC) approximates AMI, offering a robust theoretical foundation for clustering and other dependence-measurement tasks. Building on our previous work introducing Sparse Kernel Flows from an AIT perspective, we extend these ideas to unsupervised learning, enhancing the theoretical robustness and interpretability of ML algorithms. Our results demonstrate that kernel methods are not only versatile tools for ML but also crucial for bridging AIT and ML, enabling more principled approaches to unsupervised learning tasks.

关键词： Machine learning algorithmic information theory Clustering Density estimation Kernel methods Kolmogorov complexity-based reproducing kernels Learning kernels from data Minimum Description Length principle (MDL) Compression Similarity The Loss Rank Principle (loRP) algorithmic Mutual information (AMI) Normalized information Distance (NID) Normalized Compression Distance (NCD) Hilbert-Schmidt Independence Criterion (HSIC)

来源：评论

学校读者我要写书评

暂无评论

Automatic Summarization of Changes in Biological Image Sequences Using algorithmic information theory

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2009年第8期31卷 1386-1403页

作者： Cohen, Andrew R. Bjornsson, Christopher S. Temple, Sally Banker, Gary Roysam, Badrinath Univ Wisconsin Milwaukee WI 53201 USA Rensselaer Polytech Inst Troy NY 12180 USA New York Neural Stem Cell Inst Rensselaer NY 12144 USA Oregon Hlth & Sci Univ Portland OR 97239 USA

An algorithmic information-theoretic method is presented for object-level summarization of meaningful changes in image sequences. Object extraction and tracking data are represented as an attributed tracking graph (ATG). Time courses of object states are compared using an adaptive information distance measure, aided by a closed-form multidimensional quantization. The notion of meaningful summarization is captured by using the gap statistic to estimate the randomness deficiency from algorithmic statistics. The summary is the clustering result and feature subset that maximize the gap statistic. This approach was validated on four bioimaging applications: 1) It was applied to a synthetic data set containing two populations of cells differing in the rate of growth, for which it correctly identified the two populations and the single feature out of 23 that separated them;2) it was applied to 59 movies of three types of neuroprosthetic devices being inserted in the brain tissue at three speeds each, for which it correctly identified insertion speed as the primary factor affecting tissue strain;3) when applied to movies of cultured neural progenitor cells, it correctly distinguished neurons from progenitors without requiring the use of a fixative stain;and 4) when analyzing intracellular molecular transport in cultured neurons undergoing axon specification, it automatically confirmed the role of kinesins in axon specification.

关键词： Image sequence analysis algorithmic information theory algorithmic statistics information distance gap statistic clustering

来源：评论

学校读者我要写书评

暂无评论

Understanding how replication processes can maintain systems away from equilibrium using algorithmic information theory

引用

BIOSYSTEMS 2016年 140卷 8-22页

作者： Devine, Sean D. Victoria Univ Wellington Victoria Management Sch POB 600 Wellington 6140 New Zealand

Replication can be envisaged as a computational process that is able to generate and maintain order far-from-equilibrium. Replication processes, can self-regulate, as the drive to replicate can counter degradation processes that impact on a system. The capability of replicated structures to access high quality energy and eject disorder allows Landauer's principle, in conjunction with algorithmic information theory, to quantify the entropy requirements to maintain a system far-from-equilibrium. Using Landauer's principle, where destabilising processes, operating under the second law of thermodynamics, change the information content or the algorithmic entropy of a system by Delta H bits, replication processes can access order, eject disorder, and counter the change without outside interventions. Both diversity in replicated structures, and the coupling of different replicated systems, increase the ability of the system (or systems) to self-regulate in a changing environment as adaptation processes select those structures that use resources more efficiently. At the level of the structure, as selection processes minimise the information loss, the irreversibility is minimised. While each structure that emerges can be said to be more entropically efficient, as such replicating structures proliferate, the dissipation of the system as a whole is higher than would be the case for inert or simpler structures. While a detailed application to most real systems would be difficult, the approach may well be useful in understanding incremental changes to real systems and provide broad descriptions of system behaviour. (C) 2016 The Author. Published by Elsevier Ireland Ltd.

关键词： Organization in complex systems Dynamics of evolution Replication algorithmic information theory algorithmic entropy

来源：评论

学校读者我要写书评

暂无评论

The application of algorithmic information theory to noisy patterned strings

引用

COMPLEXITY 2006年第2期12卷 52-58页

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

Although algorithmic information theory provides a measure of the information content of string of characters, problems of noise and noncomputability emerge. However, if pattern in a noisy string is recognized by reference to a set of similar strings, this article shows that a compressed algorithmic description of a noisy string is possible and illustrates this with some simple examples. The article also shows that algorithmic information theory can quantify the information in complex organized systems where pattern is nested within pattern. (c) 2006 Wiley Periodicals, Inc.

关键词： complexity algorithmic information theory algorithmic entropy pattern

来源：评论

学校读者我要写书评

暂无评论

Robustness of Statistical Mechanical Interpretation of algorithmic information theory

Robustness of Statistical Mechanical Interpretation of Algor...

引用

IEEE information theory Workshop (ITW)

作者： Tadaki, Kohtaro Chuo Univ Res & Dev Initiat Bunkyo Ku Tokyo 1128551 Japan

ISBN: (纸本)9781457704376

The statistical mechanical interpretation of algorithmic information theory (AIT, for short) was introduced and developed in our former work [K. Tadaki, Local Proceedings of CiE 2008, pp. 425-434, 2008], where we introduced the thermodynamic quantities into AIT. In this paper, we reveal a certain sort of the robustness of statistical mechanical interpretation of AIT. The thermodynamic quantities in AIT are originally defined based on the set of all programs, i.e., all halting inputs, for an optimal prefix-free machine, which is a universal decoding algorithm used to define the notion of program-size complexity. We show that we can recover the original properties of the thermodynamic quantities in AIT if we replace all programs by all minimal-size programs in the definitions of the thermodynamic quantities in AIT. The results of this paper illustrate the generality and validity of the statistical mechanical interpretation of AIT.

关键词： Complexity theory Conferences Entropy Heating information theory Temperature distribution Thermodynamics algorithmic information theory decoding information theory optimal prefix free machine program size complexity statistical mechanical interpretation s

来源：评论

学校读者我要写书评

暂无评论

C. elegans Locomotion Analysis using algorithmic information theory 37

<i>C</i>. <i>elegans</i> Locomotion Analysis using Algorithm...

引用

37th Annual International Conference of the IEEE-Engineering-in-Medicine-and-Biology-Society (EMBC)

作者： Skandari, Roghieh Le Bihan, Nicolas Manton, Jonathan H. Univ Melbourne Dept Elect & Elect Engn Melbourne Vic 3010 Australia

ISBN: (纸本)9781424492701

This article investigates the use of algorithmic information theory to analyse C. elegans datasets. The ability of complexity measures to detect similarity in animals' behaviours is demonstrated and their strengths are compared to methods such as histograms. Introduced quantities are illustrated on a couple of real two-dimensional C. elegans datasets to investigate the thermotaxis and chemotaxis behaviours.

关键词： elegans Locomotion Analysis algorithmic information theory real two-dimensional information theory Caenorhabditis elegans Thermotaxis histograms Locomotion Spouses Dataset

来源：评论

学校读者我要写书评

暂无评论

Automatic summarization of changes in image sequences using algorithmic information theory

Automatic summarization of changes in image sequences using ...

引用

5th IEEE International Symposium on Biomedical Imaging

作者： Cohen, Andrew R. Bjornsson, Christopher Chen, Ying Banker, Gary Ladi, Ena Robey, Ellen Temple, Sally Roysam, Badrinath Rensselaer Polytech Inst Troy NY 12180 USA Oregon Hlth & Sci Univ Portland 97239 OR USA Univ Calif Berkeley Berkeley CA 94720 USA Albany Med Coll Ctr Neuropharmacol & Neurosci Albany NY 12208 USA

ISBN: (纸本)9781424420025

An algorithmic information theoretic method is presented for object-level summarization of meaningful changes in image sequences. Object extraction and tracking data are represented as an attributed tracking graph (ATG), whose connected subgraphs are compared using an adaptive information distance measure, aided by a closed-form multi-dimensional quantization. The summary is the clustering result and feature subset that maximize the gap statistic. The notion of meaningful summarization is captured by using the gap statistic to estimate the randomness deficiency from algorithmic statistics. When applied to movies of cultured neural progenitor cells, it correctly distinguished neurons from progenitors without requiring the use of a fixative stain. When analyzing intra-cellular molecular transport in cultured neurons undergoing axon specification, it automatically confirmed the role of kinesins in axon specification. Finally, it was able to differentiate wild type from genetically modified thymocyte cells.

关键词： algorithmic information theory algorithmic statistics information distance gap statistic clustering

来源：评论

学校读者我要写书评

暂无评论

A circuit complexity formulation of algorithmic information theory

引用

PHYSICA D-NONLINEAR PHENOMENA 2023年 456卷

作者： Wyeth, Cole Sturtivant, Carl Univ Minnesota Dept Math 100 Church St SE Minneapolis MN 55455 USA Univ Minnesota Dept Comp Sci & Engn 100 Church St SE Minneapolis MN 55455 USA

Inspired by Solomonoff's theory of inductive inference (Solomonoff, 1964), we propose a prior based on circuit complexity. There are several advantages to this approach. First, it relies on a complexity measure that does not depend on the choice of Universal Turing machine (UTM). There is one universal definition for Boolean circuits involving a universal operation (e.g. NAND) with simple conversions to alternative definitions (with AND, OR, and NOT). Second, there is no analogue of the halting problem. The output value of a circuit can be calculated recursively by computer in time proportional to the number of gates, while a short program may run for a very long time. Our prior assumes that a Boolean function (or equivalently, Boolean string of fixed length) is generated by some Bayesian mixture of circuits. This model is appropriate for learning Boolean functions from partial information, a problem often encountered within machine learning as "binary classification."We argue that an inductive bias towards simple explanations as measured by circuit complexity is appropriate for this problem.

关键词： Solomonoff induction Kolmogorov complexity algorithmic information theory Circuit complexity Sequence prediction Boolean functions

来源：评论

学校读者我要写书评

暂无评论

Loop Closure Detection By algorithmic information theory: Implemented On Range And Camera Image Data

引用

IEEE TRANSACTIONS ON CYBERNETICS 2014年第10期44卷 1938-1949页

作者： Ravari, Alireza Norouzzadeh Taghirad, Hamid D. KN Toosi Univ Technol Tehran 19697 Iran

sIn this paper the problem of loop closing from depth or camera image information in an unknown environment is investigated. A sparse model is constructed from a parametric dictionary for every range or camera image as mobile robot observations. In contrast to high-dimensional feature-based representations, in this model, the dimension of the sensor measurements' representations is reduced. Considering the loop closure detection as a clustering problem in high-dimensional space, little attention has been paid to the curse of dimensionality in the existing state-of-the-art algorithms. In this paper, a representation is developed from a sparse model of images, with a lower dimension than original sensor observations. Exploiting the algorithmic information theory, the representation is developed such that it has the geometrically transformation invariant property in the sense of Kolmogorov complexity. A universal normalized metric is used for comparison of complexity based representations of image models. Finally, a distinctive property of normalized compression distance is exploited for detecting similar places and rejecting incorrect loop closure candidates. Experimental results show efficiency and accuracy of the proposed method in comparison to the state-of-the-art algorithms and some recently proposed methods.

关键词： algorithmic information theory loop closure mobile robot range image

来源：评论

学校读者我要写书评

暂无评论

The Entropy Economy and the Kolmogorov Learning Cycle: Leveraging the intersection of Machine Learning and algorithmic information theory to jointly optimize energy and learning

引用

PHYSICA D-NONLINEAR PHENOMENA 2024年 461卷

作者： Evans, Scott C. Shah, Tapan Huang, Hao Ekanayake, Sachini Piyoni GE Vernova Adv Res Ctr Niskayuna NY 12309 USA

We augment the Kolmogorov Structure Function with energy cost and drive the concept of "Additive AI" where Machine Learning Models are created by traversing the Kolmogorov Structure function from low model complexity to high while seeking models achieving the Kolmogorov Minimum Sufficient Statistic with least energy cost. In this way, the intersection of algorithmic information theory (AIT) with Machine Learning (ML) can enable optimization of the "Entropy Economy," where the precious resource of entropy flow is managed to jointly optimize computation, energy, and learning. In this paper we lay out the Kolmogorov Learning Cycle as a framework for this joint optimization and demonstrate the energy efficient machine learning algorithm Least Energy Usage Network (LEAN) as an example of how restraining complexity can reduce learning energy cost while maintaining performance. We motivate further directions for optimizing how AI models can be optimally learned and discuss additional opportunities to optimize where and when AI and machine learning models can be created to maximize learning while minimizing energy (and subsequently carbon costs) through the intersection of AIT and ML.

关键词： Kolmogorov complexity Kolmogorov structure function Machine learning Entropy Economy algorithmic information theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：