算法信息论
概述
算法信息论（Algorithmic Information Theory, AIT）将信息论与计算理论结合，用程序长度（而非概率分布）来度量信息的复杂性，是信息论的第四大支柱。
关键内容
三大独立发源
| 人物 |
年份 |
贡献 |
| Solomonoff |
1960/1964 |
Solomonoff先验</td>
</tr>
<tr>
<td>[[安德烈·柯尔莫哥洛夫</td>
<td>Kolmogorov |
1965 |
| Chaitin |
1966 |
Kolmogorov 1965 年论文早 5 年）。
核心概念
- 柯尔莫哥洛夫复杂性 K(x)：产生字符串 x 的最短程序长度
- 算法概率 M(x)：所有能输出 x 的程序的概率之和
- 算法随机性：如果 K(x) ≈ |x|，则 x 是算法随机的（不可压缩）
- Chaitin 常数 Ω：随机程序停机的概率，不可计算的超越数
与 Shannon 信息论的对比
|
Shannon 信息论 |
算法信息论 |
| 信息度量 |
基于概率分布的熵 H(X) |
基于程序长度的复杂性 K(x) |
| 适用对象 |
随机信源（统计集合） |
单个字符串（个体对象） |
| 先验知识 |
需要知道概率分布 |
不需要任何分布假设 |
| 可计算性 |
完全可计算 |
不可计算 |
与 AI 的关系
- AIXI 模型：Hutter (2000) 将 Solomonoff 归纳与 Bellman 最优控制结合，提出理论上最优的通用 AI 模型
- MDL 原理：Rissanen (1978) 的最小描述长度是 Solomonoff 思想的可计算近似
- LLM：大语言模型可视为 Solomonoff 归纳的一种可计算近似
来源
- raw/books/信息论/08_solomonoff_1964_formal_theory_of_inductive_inference.md — Solomonoff (1964) 深度解析
相关
|