arXiv:2411.05943cs.AIcs.CL2024-11被引 9

用代数电路复杂度量化AI的算法泛化能力,填补理论空白。

Quantifying artificial intelligence through algorithmic generalization

  • 基于计算复杂度理论,用代数电路建模算法推理难度。
  • 可生成任意多样本,适配数据密集型AI模型测试。
  • 为评估AI算法泛化提供可量化的科学框架,适合研究者参考。

人工智能系统的快速发展带来了对其科学量化的需求。尽管其在多个领域表现流畅,但在需要算法推理的任务上仍显不足,而可解释与可靠的技术对此至关重要。尽管学术界涌现大量推理评测基准,却缺乏量化算法推理的理论框架。本文采用计算复杂度理论中的代数电路复杂度框架,将算法泛化能力通过代数表达式进行量化。代数电路复杂度研究以电路模型表示代数表达式,是分析算法计算复杂性的自然工具。该方法通过定义解决问题的计算需求来构建评测基准。此外,代数电路是通用数学对象,可为指定电路生成任意数量样本,使其成为当今数据驱动模型的理想实验环境。本文提出应用代数电路复杂度工具,形式化算法泛化科学,并探讨其在人工智能研究中成功应用的关键挑战。

原文摘要 · Abstract (English)

The rapid development of artificial intelligence (AI) systems has created an urgent need for their scientific quantification. While their fluency across a variety of domains is impressive, AI systems fall short on tests requiring algorithmic reasoning -- a glaring limitation given the necessity for interpretable and reliable technology. Despite a surge of reasoning benchmarks emerging from the academic community, no theoretical framework exists to quantify algorithmic reasoning in AI systems. Here, we adopt a framework from computational complexity theory to quantify algorithmic generalization using algebraic expressions: algebraic circuit complexity. Algebraic circuit complexity theory -- the study of algebraic expressions as circuit models -- is a natural framework to study the complexity of algorithmic computation. Algebraic circuit complexity enables the study of generalization by defining benchmarks in terms of the computational requirements to solve a problem. Moreover, algebraic circuits are generic mathematical objects; an arbitrarily large number of samples can be generated for a specified circuit, making it an ideal experimental sandbox for the data-hungry models that are used today. In this Perspective, we adopt tools from algebraic circuit complexity, apply them to formalize a science of algorithmic generalization, and address key challenges for its successful application to AI science.

算法推理泛化能力复杂度理论量化评估

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。