論文の概要: 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ビットマップ、ランダムプロジェクション、スケッチ、階層フィルタを仮定して統一する。 それは、ハッシュ関数工学ではなく、目撃者の重複によって支配される、類似性システムのための原則化された基盤を提供する。 この写本は公理、主再現性定理、明示的な定数を持つ完全証明、および多ビット符号化、重み付けされた証人、非集合表現を含む構成設計、制限、将来の拡張に関する詳細な議論を提示する。

関連論文リスト

• Bridging Functional and Representational Similarity via Usable Information [3.9189279162842854]
  テクスチャブルな情報のレンズを通して表現間の類似性を定量化する統一的な枠組みを提案する。 まず,機能的類似性に対処し,縫合性能と条件付き相互情報との正式なリンクを確立する。 第2に、表現的類似性について、特定の制約の下で使用可能な情報の推定器として、再構成に基づくメトリクスと標準ツールが機能することを証明する。
  論文  参考訳（メタデータ） (2026-01-29T11:30:55Z)
• Generalization and Completeness of Stochastic Local Search Algorithms [0.0]
  局所探索(SLS)アルゴリズムを一意な形式モデルに一般化する。 このモデルには、2つの重要な構成要素がある: できるだけ大きいように設計された共通構造と、できるだけ小さいことを意図したパラメトリック構造である。 SLSアルゴリズムのチューリング完全性を証明するために,本モデルを用いた。
  論文  参考訳（メタデータ） (2026-01-20T18:17:45Z)
• Similarity Field Theory: A Mathematical Framework for Intelligence [0.0]
  本稿では、実体間の類似性値の原則とその進化を定式化する数学的枠組みである「類似性場理論」を紹介する。 高いレベルでは、このフレームワークは、類似性に関する幾何学的な問題として、知性と解釈可能性を再設計する。 我々は、2つの定理を証明している: (i)非対称性は相互包含をブロックし、 (ii)安定性はアンカー座標または準位集合内の最終的な閉じ込めを必要とする。
  論文  参考訳（メタデータ） (2025-09-21T22:34:00Z)
• Loss-Complexity Landscape and Model Structure Functions [53.92822954974537]
  我々はコルモゴロフ構造関数 $h_x(alpha)$ を双対化するためのフレームワークを開発する。 情報理論構造と統計力学の数学的類似性を確立する。 構造関数と自由エネルギーの間のルジャンドル・フェンシェル双対性を明確に証明する。
  論文  参考訳（メタデータ） (2025-07-17T21:31:45Z)
• Generalized and Unified Equivalences between Hardness and Pseudoentropy [6.683376336762599]
  計算の一様モデルと非一様モデルの両方に対して、従来の結果を一般化し、強化する統一擬似エントロピー特性を証明した。 我々の特徴づけは、シャノンエントロピーとミンエントロピーの共通概念を特別な場合として含むエントロピーの概念の一般族である。
  論文  参考訳（メタデータ） (2025-07-08T13:27:03Z)
• 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)
• Cluster-Aware Similarity Diffusion for Instance Retrieval [64.40171728912702]
  拡散に基づく再ランク付け(diffusion-based re-level)は、隣り合うグラフで類似性の伝播を実行することで、インスタンスを検索する一般的な方法である。 本稿では,新しいクラスタ・アウェア類似性(CAS)拡散モデルを提案する。
  論文  参考訳（メタデータ） (2024-06-04T14:19:50Z)
• Prototype-based Aleatoric Uncertainty Quantification for Cross-modal Retrieval [139.21955930418815]
  クロスモーダル検索手法は、共通表現空間を共同学習することにより、視覚と言語モダリティの類似性関係を構築する。 しかし、この予測は、低品質なデータ、例えば、腐敗した画像、速いペースの動画、詳細でないテキストによって引き起こされるアレタリック不確実性のために、しばしば信頼性が低い。 本稿では, 原型に基づくAleatoric Uncertainity Quantification (PAU) フレームワークを提案する。
  論文  参考訳（メタデータ） (2023-09-29T09:41:19Z)
• Probing multipartite entanglement through persistent homology [6.107978190324034]
  永続的ホモロジーによる多部交絡の研究を提案する。 永続ホモロジーは トポロジカルデータ分析で 使われるツールです 永続バーコードはそのトポロジ的要約よりもきめ細かな情報を提供することを示す。
  論文  参考訳（メタデータ） (2023-07-14T17:24:33Z)
• DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
  本稿では,データセットからのインスタンスのバッチを進化状態にエンコードするエネルギー制約拡散モデルを提案する。 任意のインスタンス対間の対拡散強度に対する閉形式最適推定を示唆する厳密な理論を提供する。 各種タスクにおいて優れた性能を有する汎用エンコーダバックボーンとして,本モデルの適用性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-01-23T15:18:54Z)
• 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)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  本稿では,大規模なスパースネットワークのクラスにおいて,高い確率で完全クラスタリングを実現するスペクトルアルゴリズムを提案する。 本手法は,スペクトルクラスタリングによる一貫した潜在構造回復を保証する最初の方法である。
  論文  参考訳（メタデータ） (2022-05-17T01:41:06Z)
• Self-Supervised Learning Disentangled Group Representation as Feature [82.07737719232972]
  既存の自己監督学習(SSL)は、回転や着色などの単純な拡張機能のみを分解することを示す。 反復的分割に基づく不変リスク最小化(IP-IRM)を提案する。 我々は、IP-IRMが完全に不整合表現に収束し、様々なベンチマークでその効果を示すことを証明した。
  論文  参考訳（メタデータ） (2021-10-28T16:12:33Z)
• Instance Similarity Learning for Unsupervised Feature Representation [83.31011038813459]
  教師なし特徴表現のための例類似性学習(ISL)手法を提案する。 我々はGAN(Generative Adversarial Networks)を用いて、基礎となる特徴多様体をマイニングする。 画像分類実験は, 最先端手法と比較して, 提案手法の優位性を示した。
  論文  参考訳（メタデータ） (2021-08-05T16:42:06Z)
• CIMON: Towards High-quality Hash Codes [63.37321228830102]
  我々はtextbfComprehensive stextbfImilarity textbfMining と ctextbfOnsistency leartextbfNing (CIMON) という新しい手法を提案する。 まず、グローバルな洗練と類似度統計分布を用いて、信頼性とスムーズなガイダンスを得る。第二に、意味的整合性学習とコントラスト的整合性学習の両方を導入して、乱不変と差別的ハッシュコードの両方を導出する。
  論文  参考訳（メタデータ） (2020-10-15T14:47:14Z)

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

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