arXiv:2508.14143cs.LGq-bio.NC2025-08被引 4

用拓扑结构建模分类计算,揭示边界几何与可复用性本质。

The Urysohn Machine: A Metric-Topological Model of Computation

  • 基于度量拓扑构建可重用的分类器库,显式处理边界与收缩过程。
  • 提出决策边界宽度与乌里松宽度两个几何度量,量化分类复杂度。
  • 适合研究几何深度学习、可解释模型与形式化计算理论的读者。

我们提出乌里松机器,一种面向分类计算的度量-拓扑模型,其中度量分离、边界结构与收缩过程均显式体现在计算状态中。其基本对象是乌里松三元组:支撑区域、目标划分及存储于可复用度量库中的分离分类器。模型基于有限单纯复形上的构造性乌里松实现定理,通过嵌套多面体区域的二进制阶梯构建分离器,并在边界上引入链层微积分:边界为循环,层级间壳层的边界由边界差给出。该构造导出两个相关复杂度度量:单个分类器边界的决策边界宽度,以及库或实现所表示的总边界质量(乌里松宽度)。我们证明了摊销分离定理:在明确边界足迹假设下,以精度近似宽度为w的边界,所需简单基三元组数量与宽度成正比,与分辨率成反比。此外,我们引入对比分离算子,其图割泛函能从采样度量数据一致估计决策边界宽度,而其拉普拉斯谱可验证类成分结构与导通性。最后,我们分析动态乌里松阶梯,证明四项保证:商坍缩下的可分性、已承诺边界的稳定性、收缩下的有界容量,以及商距离下的可扩展性。这些结果共同提供了一个度量-拓扑视角下的分类复杂性、摊销推理与组合复用理论,在保持经典可计算性的同时,揭示了符号描述隐藏的几何结构。

原文摘要 · Abstract (English)

We introduce the Urysohn Machine, an effective model of classification-oriented computation in which metric separation, frontier structure, and contraction are explicit parts of the computational state. Its basic object is a \emph{Urysohn Triple}: a support region, a target partition, and a separating classifier stored in a reusable Metric Library. The topological foundation is a constructive Urysohn Realization theorem for finite simplicial settings. It builds separators from dyadic ladders of nested polyhedral regions and equips their frontiers with a chain-level calculus: frontiers are cycles, and shells between levels have boundaries given by differences of frontiers. This construction yields two related complexity measures: decision-boundary width, the geometric measure of a single classifier's boundary, and Urysohn width, the total frontier mass represented by a library or realization. We prove an Amortized Separation Theorem showing that approximating a boundary of width to accuracy requires a number of simple basis triples proportional to boundary width and inversely proportional to resolution, under explicit boundary-footprint assumptions. We also introduce a contrastive separation operator whose graph-cut functional consistently estimates decision-boundary width from sampled metric data, while its Laplacian spectrum certifies class-component structure and conductance. Finally, we analyze the dynamic Urysohn ladder and prove four guarantees: separability under quotient collapse, stability of committed frontiers, bounded capacity under contraction, and scalability with quotient distance. Together, these results give a metric-topological account of classification complexity, amortized inference, and compositional reuse that preserves classical computability while exposing geometric structure hidden by purely symbolic descriptions.

拓扑计算分类模型几何深度学习

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