ShapeCoder: Discovering Abstractions for Visual Programs from Unstructured Primitives

一句话总结

ShapeCoder 是首个能直接从”一堆无结构基元”表示的形状数据集里，自动同时发现（i）有用的抽象函数库和（ii）用这些抽象来紧凑解释每个形状的可视化程序的系统。

研究背景

• 领域现状：可视化程序（执行后产生视觉输出的表达式）是表示视觉数据的好方式——紧凑、可解释、可编辑。但程序好不好用取决于它的领域特定语言（DSL）里有哪些函数，一组”好”的抽象函数往往是找到良构程序的前提，而这些抽象通常要靠专家手工设计。
• 核心痛点：已有的抽象发现方法各有硬伤。DreamCoder 面向通用编程语言，抽象是纯结构性的，把实数当离散量处理，抓不住可视化程序里的参数关系；而且依赖”课程”（curriculum），要求部分输入任务在当前库下就容易解，否则可能什么都发现不了。ShapeMOD 虽为形状程序设计、能抓参数关系，但假设很强：需要命令式程序、已知所有合法的行重排序、以及层级语义分割标注，扩展性差。
• 本文 idea：在更弱的假设下发现抽象——不需要真值程序、不需要规范行序、不需要层级分解，输入只是每个形状的一组无序基元。为此需要两项能力：一个能推断”解释输入形状的程序”的识别网络，以及一套能在任意程序重排序上判断抽象何时可用的机制。

方法

整体框架沿用 DreamCoder 式的迭代循环，每一轮串起四个阶段，逐步往库 L 里加入能改善目标函数 F 的抽象。dream 阶段从库里采样合成场景训练识别网络；wake 阶段用该网络为数据集里的形状推断程序 P；proposal 阶段从 P 里挖候选抽象；integration 阶段借助 refactor 操作判断哪些候选真正加入库能降低 F，再把新库送入下一轮 dream。

flowchart LR
  D["形状数据集 D（无结构基元）"] --> Dream["Dream 阶段<br/>采样合成场景训练识别网络"]
  Dream --> Wake["Wake 阶段<br/>识别网络推断程序 P"]
  Wake --> Prop["Proposal 阶段<br/>产出候选抽象"]
  Prop --> Integ["Integration 阶段<br/>refactor + e-graph 决定是否入库"]
  Integ -->|"更新库 L 改善 F"| Dream

关键设计：

• 目标函数 F（压缩即一切）：F 在”程序复杂度”和”库复杂度”之间做权衡。程序复杂度按 Occam 剃刀用加权 token 数计，并加入几何误差项——若重建误差超过阈值则 F 返回 \(\infty\)；库复杂度用可自定义的函数权重 \(\omega\) 衡量（参数越多的函数越难入库）。整体写作： \[\mathcal{F}(L,P)=\frac{1}{\lvert P \rvert}\left(\sum_{p\in P}\left(\sum_{\tau\in T}\lambda_\tau\,\tau(p)\right)+\lambda_e\,\mathrm{err}(p,d)\right)+\sum_{f\in L}\omega(f)\]

• 能解子问题的识别网络（wake 的核心）：把整程序推断拆成”局部解”——网络是一个 Transformer 解码器，自回归地预测能重建输入基元一个子集的表达式。实数参数用简单分桶（四舍五入到两位小数后排序）映射成 token。wake 阶段迭代进行：让网络对当前场景采样大量表达式、按归一化代价挑最优的一个、移除它覆盖的基元，直到画布清空，最后用 Union 组合器把各表达式并起来。因为只需解子问题，即便数据集里没有”由易到难的课程”也能工作，这正是 DreamCoder 的软肋。dream 阶段则把多个函数各自采样的基元拼成复合场景，形成”一对多”的监督对来训练网络。

• proposal：把全局难题拆成局部聚类搜索：先从 P 里记录所有出现过的结构（限定为单个或成对的子表达式组合）及其参数化方式，过滤掉出现频率过低（<5%）的结构。然后反复采样”一个结构 + 一部分参数化”构成 cluster，在 cluster 上跑贪心搜索找一个能优化 F 的抽象。贪心搜索由一个评分函数引导，评分是 frequency（该抽象能正确重建 cluster 中实例的比例）与 gain（每次应用能去掉的参数数）之积；对每个参数槽，它会在”复用已有参数 / 赋静态值 / 定义新自由参数 / 各种参数关系表达式”中挑评分最高的填入。

• refactor + e-graph + 条件重写（判断抽象何时可用）：integration 要判断某个抽象能否套用到程序上，这是难搜索问题。ShapeCoder 把程序转成 e-graph（能紧凑表示大量等价程序的数据结构），用”语义重写”（DSL 的领域知识）和”抽象重写”（对应库里的抽象）不断扩张 e-graph，再从根 e-class 抽取最小代价的等价程序。关键创新是条件重写方案：抽象的应用往往既需结构匹配又需参数匹配（如 \(?c = ?a+?b\) 且 \(?d = ?b-?a\)）。朴素做法是把参数约束展开成 Add/Sub 等结构节点塞进 e-graph，参数一多就爆炸。条件重写改为先做结构匹配，只有当附加的参数检查（用动态维护的 e-class 到实值映射惰性比较，允许误差阈值）通过时才真正应用重写，从而避免 e-graph 体积爆炸，且单步和普通重写一样快。

实验结果

在 PartNet 的 Chair / Table / Storage 三类 3D 形状上（每类 400 个形状、每个转成无结构长方体集合、去掉层级与顺序信息），用目标函数 F 衡量不同方法发现的抽象库质量。ShapeCoder 相比起点显著压缩，也明显优于两个 ShapeMOD 变体：

类别	方法	F ↓	库大小 |L|	结构量 ↓	参数量 ↓
Chair	Input Prims（起点）	146.0	6	29	61
Chair	ShapeMOD+Wake	83.0	21	12	36
Chair	ShapeCoder	63.6	33	10	27
Table	Input Prims（起点）	125.0	6	25	51
Table	ShapeCoder	40.9	37	8	18
Storage	Input Prims（起点）	154.0	6	30	62
Storage	ShapeCoder	71.3	31	11	33

三类的 F 相对起点分别下降 56% / 67% / 53%。对比单程序化简方法 Szalinski，其固定重写规则只把 Chair 的 F 从 146 降到 131，而 ShapeCoder 达到 63.6。其他实验以文字补充：消融显示每个组件（抽象阶段、多轮迭代、dream+wake、语义重写、条件重写、偏好权重）都不可或缺，其中去掉条件重写后在 3 天预算内都跑不完一次抽象阶段；发现的抽象有泛化性，用后验推断（PHI）在留出验证集上 F 仅从 63.6（训练）升到 70.6；条件重写相对朴素方案在 32 参数表达式上把耗时从超时降到约 2.1 秒；下游应用中，用抽象重写的程序在参数扰动下更”保持在分布内”，训练出的生成模型 Frechet 距离从 17.1 降到 13.8（提升 19%）；即便在无监督长方体分解产生的噪声基元上，也能把 Chair 的 F 改善 61%（140→53.9）。

亮点与局限

• 亮点：
  • 首个直接从”无结构、无标注基元集合”联合发现抽象库与可视化程序的系统，输入假设远弱于 ShapeMOD（无需真值程序、行序、层级分割）。
  • 识别网络”解子问题”的设计摆脱了 DreamCoder 对课程的依赖，能处理更复杂输入。
  • 条件重写方案让 e-graph 能处理带复杂参数关系的抽象匹配而不爆炸，是把 e-graph 用到含参数关系可视化程序上的关键工程/算法贡献。
  • 发现的抽象既有结构模式又约束参数自由度，能泛化到未见形状，并对编辑、生成等下游任务有实证收益。
• 局限：
  • 冗余抽象：会发现多个解释同一概念的抽象（如 pedestal 底座与四腿底座），因为当前不”执行”程序去比较几何输出，下游使用时显得重复。作者设想用”条件/概率抽象”来统一。
  • e-graph 难以饱和：对复杂输入表达式，受限于 e-graph 对结合律-交换律约束的表达能力，在给定算力预算内常无法完全饱和，可能有有用的重写没被探索、抽象没被纳入库。

延伸思考

ShapeCoder 处在”程序合成 × 图形学”的交叉点：它把 DreamCoder 的库学习范式和 e-graph 的等价程序搜索缝合起来，专门攻克可视化程序里”参数关系”这个难点。值得追问的方向有几个：一是作者自己提到的概率/条件抽象——若能让一个”底座抽象”按离散开关展开成多种结构，就能天然消解冗余，也更贴合生成建模；二是把 Babble 式的 e-graph 反统一（anti-unification）提案机制迁移到这里”不展开参数算子”的 e-graph 形式上，可能让候选抽象的发现更系统而非靠聚类采样；三是它对无监督长方体分解噪声的鲁棒性提示了一条”从原始网格到可编辑程序表示”的自动化管线，若接上更强的基元分解或神经场表示，有望扩展到超出家具的更一般 3D 形状域。