論文の概要: REWA: Witness-Overlap Theory -- Foundations for Composable Binary Similarity Systems

• arxiv url: http://arxiv.org/abs/2511.19998v1
• Date: Tue, 25 Nov 2025 07:04:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-26 17:37:04.324135
• Title: REWA: Witness-Overlap Theory -- Foundations for Composable Binary Similarity Systems
• Title（参考訳）: REWA: Witness-Overlap Theory -- Composable Binary similarity Systemsの基礎
• Authors: Nikit Phadke,
• Abstract要約: REWAは、目撃者のオーバーラップ構造に基づく類似性に関する一般的な理論を導入する。 概念間の類似性を単調な証人オーバーラップとして表すことができれば、コンパクトな符号化に還元できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: REWA introduces a general theory of similarity based on witness-overlap structures. We show that whenever similarity between concepts can be expressed as monotone witness overlap -- whether arising from graph neighborhoods, causal relations, temporal structure, topological features, symbolic patterns, or embedding-based neighborhoods -- it admits a reduction to compact encodings with provable ranking preservation guarantees. REWA systems consist of: (1) finite witness sets $W(v)$, (2) semi-random bit assignments generated from each witness, and (3) monotonicity of expected similarity in the overlap $Δ(u, v) = |W(u) \cap W(v)|$. We prove that under an overlap-gap condition on the final witness sets -- independent of how they were constructed -- top-$k$ rankings are preserved using $m = O(\log(|V|/δ))$ bits. The witness-set formulation is compositional: any sequence of structural, temporal, causal, topological, information-theoretic, or learned transformations can be combined into pipelines that terminate in discrete witness sets. The theory applies to the final witness overlap, enabling modular construction of similarity systems from reusable primitives. This yields a vast design space: millions of composable similarity definitions inherit logarithmic encoding complexity. REWA subsumes and unifies Bloom filters, minhash, LSH bitmaps, random projections, sketches, and hierarchical filters as special cases. It provides a principled foundation for similarity systems whose behavior is governed by witness overlap rather than hash-function engineering. This manuscript presents the axioms, the main reducibility theorem, complete proofs with explicit constants, and a detailed discussion of compositional design, limitations, and future extensions including multi-bit encodings, weighted witnesses, and non-set representations.
• Abstract（参考訳）: REWAは、目撃者のオーバーラップ構造に基づく類似性に関する一般的な理論を導入する。 グラフ近傍,因果関係,時間的構造,トポロジ的特徴,象徴的パターン,あるいは埋め込み型近傍から生じる概念間の類似性は,証明可能なランク維持保証を備えたコンパクトエンコーディングへの縮小を認める。 REWAシステム:(1)有限証人集合$W (v)$, (2) それぞれの証人から生成される半ランダムビット割り当てと(3) 重複する$Δ(u,)における期待類似性の単調性 v) = |W (u) キャップW (v)|$。 最終的な目撃者集合の重複ギャップ条件の下では、構築方法とは無関係に、トップ$k$ランキングは$m = O(\log(|V|/δ))$ bits で保存される。 構造的、時間的、因果的、位相的、情報理論的、あるいは学習的な変換の任意の列は、個別の証人集合で終了するパイプラインに結合することができる。 この理論は最後の目撃者の重複に当てはまり、再利用可能なプリミティブから類似システムのモジュラー構成を可能にする。 数百万の構成可能な類似性の定義が対数エンコーディングの複雑さを継承する。 REWAは特別なケースとしてブルームフィルタ、minhash、LSHビットマップ、ランダムプロジェクション、スケッチ、階層フィルタを仮定して統一する。 それは、ハッシュ関数工学ではなく、目撃者の重複によって支配される、類似性システムのための原則化された基盤を提供する。 この写本は公理、主再現性定理、明示的な定数を持つ完全証明、および多ビット符号化、重み付けされた証人、非集合表現を含む構成設計、制限、将来の拡張に関する詳細な議論を提示する。

関連論文リスト

• Similarity Field Theory: A Mathematical Framework for Intelligence [0.0]
  本稿では、実体間の類似性値の原則とその進化を定式化する数学的枠組みである「類似性場理論」を紹介する。 高いレベルでは、このフレームワークは、類似性に関する幾何学的な問題として、知性と解釈可能性を再設計する。 我々は、2つの定理を証明している: (i)非対称性は相互包含をブロックし、 (ii)安定性はアンカー座標または準位集合内の最終的な閉じ込めを必要とする。
  論文  参考訳（メタデータ） (2025-09-21T22:34:00Z)
• Structural Entropy Guided Probabilistic Coding [52.01765333755793]
  構造エントロピー誘導型確率的符号化モデルSEPCを提案する。 我々は、構造エントロピー正規化損失を提案することにより、潜在変数間の関係を最適化に組み込む。 分類タスクと回帰タスクの両方を含む12の自然言語理解タスクに対する実験結果は、SEPCの優れた性能を示す。
  論文  参考訳（メタデータ） (2024-12-12T00:37:53Z)
• Interaction Asymmetry: A General Principle for Learning Composable Abstractions [27.749478197803256]
  相互作用非対称性は、アンタングル化と合成一般化の両方を可能にすることを示す。 本稿では, フレキシブルトランスフォーマーをベースとしたVAEを用いて, デコーダの注意重みに対する新しい正規化器を提案する。
  論文  参考訳（メタデータ） (2024-11-12T13:33:26Z)
• Prototype-based Aleatoric Uncertainty Quantification for Cross-modal Retrieval [139.21955930418815]
  クロスモーダル検索手法は、共通表現空間を共同学習することにより、視覚と言語モダリティの類似性関係を構築する。 しかし、この予測は、低品質なデータ、例えば、腐敗した画像、速いペースの動画、詳細でないテキストによって引き起こされるアレタリック不確実性のために、しばしば信頼性が低い。 本稿では, 原型に基づくAleatoric Uncertainity Quantification (PAU) フレームワークを提案する。
  論文  参考訳（メタデータ） (2023-09-29T09:41:19Z)
• Unsupervised Learning of Equivariant Structure from Sequences [30.974508897223124]
  我々は,少なくとも3つの長さの時系列から対称性を学習するための教師なしのフレームワークを提案する。 当社のフレームワークでは,データセットの非絡み合い構造が副産物として自然に現れることを実証します。
  論文  参考訳（メタデータ） (2022-10-12T07:29:18Z)
• Generating Compressed Combinatory Proof Structures -- An Approach to Automated First-Order Theorem Proving [0.0]
  ここでは、自動一階述語証明に対する「証明構造としての組合せ項」のアプローチを紹介する。 このアプローチは、凝縮した分枝に根付いた証明構造の項ビューと接続法に基づいて構築される。
  論文  参考訳（メタデータ） (2022-09-26T11:23:17Z)
• Self-Supervised Learning Disentangled Group Representation as Feature [82.07737719232972]
  既存の自己監督学習(SSL)は、回転や着色などの単純な拡張機能のみを分解することを示す。 反復的分割に基づく不変リスク最小化(IP-IRM)を提案する。 我々は、IP-IRMが完全に不整合表現に収束し、様々なベンチマークでその効果を示すことを証明した。
  論文  参考訳（メタデータ） (2021-10-28T16:12:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。