线性分类器训练是 NP 难:Roth 论复杂度为何不挡 AI 路线程
Aaroth · x · 2026-09-14
Aaron Roth 线程的举例部分:机器学习里最简单的问题——训练最小化分类误差的线性分类器——本身是 NP 难的,甚至近似到能区分 51% 与 99% 准确率都做不到,因此更一般的问题只会更难。但这并未阻碍现实中几乎所有此类统计学习问题被有效解决,以此说明最坏情形复杂度不是判断可行性的好指南。
所属事件:宾大学者驳斥用复杂度理论否定 AI 可能性的论调(4 条相关)→
「漫话AGI」频道最新
- 机器人公司的囚徒困境：不用基础模型演示会输，用了护城河就被吸走 — ChongZzZhang · 2026-09-14
- 分析120万份博士论文：政府仍是前沿科技博士培养最大金主 — joshgans · 2026-09-14
- a16z Josh Elman：AI 压低建造成本，产品品味仍是稀缺品 — a16z · 2026-09-14
- 大厂高管公开承认 AI 失控情景的可能性 — emmanuelvivier · 2026-09-14
- OpenAI 宣称解决纳维-斯托克斯千年难题，数学家撰文反思 AI 做数学 — fortnow · 2026-09-14
- OpenAI 研究员：AI 圈那套文化其实源自伯克利而非硅谷 — jachiam0 · 2026-09-14