論文の概要: Gaussian Database Alignment and Gaussian Planted Matching
- arxiv url: http://arxiv.org/abs/2307.02459v1
- Date: Wed, 5 Jul 2023 17:32:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-06 12:46:40.863503
- Title: Gaussian Database Alignment and Gaussian Planted Matching
- Title（参考訳）: ガウスデータベースアライメントとガウス植物マッチング
- Authors: Osman Emre Dai, Daniel Cullina, Negar Kiyavash
- Abstract要約: データベースアライメントは、グラフアライメント問題の変種である。
データベースアライメントと植木マッチングの両方に適用する結果を導出する。
その結果,緩和アルゴリズムのアライメントしきい値が最大値とほぼ一致していることが判明した。
- 参考スコア（独自算出の注目度）: 23.850273632117037
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Database alignment is a variant of the graph alignment problem: Given a pair
of anonymized databases containing separate yet correlated features for a set
of users, the problem is to identify the correspondence between the features
and align the anonymized user sets based on correlation alone. This closely
relates to planted matching, where given a bigraph with random weights, the
goal is to identify the underlying matching that generated the given weights.
We study an instance of the database alignment problem with multivariate
Gaussian features and derive results that apply both for database alignment and
for planted matching, demonstrating the connection between them. The
performance thresholds for database alignment converge to that for planted
matching when the dimensionality of the database features is \(\omega(\log
n)\), where \(n\) is the size of the alignment, and no individual feature is
too strong. The maximum likelihood algorithms for both planted matching and
database alignment take the form of a linear program and we study relaxations
to better understand the significance of various constraints under various
conditions and present achievability and converse bounds. Our results show that
the almost-exact alignment threshold for the relaxed algorithms coincide with
that of maximum likelihood, while there is a gap between the exact alignment
thresholds. Our analysis and results extend to the unbalanced case where one
user set is not fully covered by the alignment.
- Abstract（参考訳）: データベースアライメントは、グラフアライメント問題の変種である: ユーザ集合に対して、別々の相関のある特徴を含む匿名化されたデータベースの対が与えられた場合、問題は、特徴間の対応を識別し、相関のみに基づいて匿名化されたユーザ集合をアライメントすることである。
これは、ランダムな重みを持つグラフが与えられた場合、与えられた重みを生成する基礎となるマッチングを特定することが目的である。
本研究では,多変量ガウス特徴を用いたデータベースアライメント問題の事例について検討し,データベースアライメントと植木マッチングの両方に適用可能な結果を得た。
データベースアライメントのパフォーマンスしきい値は、データベースの特徴の次元が (\omega(\log n)\) であるときに植えられたマッチングに対して収束し、ここでは \(n\) はアライメントのサイズであり、個々の特徴が強すぎることはない。
組込みマッチングとデータベースアライメントの両方の最大確率アルゴリズムは線形プログラムの形式を採り、様々な条件下での様々な制約の意義をよりよく理解し、達成可能性および逆境界を示すために緩和について検討する。
その結果,緩和アルゴリズムのアライメント閾値は最大確率のアライメント閾値と一致し,正確なアライメントしきい値の間にはギャップがあることがわかった。
我々の分析と結果は、あるユーザーセットがアライメントによって完全にカバーされていない不均衡なケースにまで及んでいる。
関連論文リスト
- Semiparametric conformal prediction [79.6147286161434]
リスクに敏感なアプリケーションは、複数の、潜在的に相関したターゲット変数に対して、よく校正された予測セットを必要とする。
スコアをランダムなベクトルとして扱い、それらの連接関係構造を考慮した予測セットを構築することを目的とする。
実世界のレグレッション問題に対して,所望のカバレッジと競争効率について報告する。
論文 参考訳（メタデータ） (2024-11-04T14:29:02Z) - SEG:Seeds-Enhanced Iterative Refinement Graph Neural Network for Entity Alignment [13.487673375206276]
本稿では,マルチソースデータと反復的シード拡張を融合したソフトラベル伝搬フレームワークを提案する。
正試料間距離と負試料の差分処理を行う双方向重み付き共同損失関数を実装した。
提案手法は,既存の半教師付きアプローチよりも優れており,複数のデータセットにおいて優れた結果が得られた。
論文 参考訳（メタデータ） (2024-10-28T04:50:46Z) - Learnable Pillar-based Re-ranking for Image-Text Retrieval [119.9979224297237]
画像テキスト検索は、モダリティギャップを埋め、意味的類似性に基づいてモダリティコンテンツを検索することを目的としている。
一般的なポストプロセッシング手法であるリグレードは, 単一モダリティ検索タスクにおいて, 隣り合う関係を捕捉する優位性を明らかにしている。
本稿では,画像テキスト検索のための新しい学習可能な柱型リグレードパラダイムを提案する。
論文 参考訳（メタデータ） (2023-04-25T04:33:27Z) - PA-GM: Position-Aware Learning of Embedding Networks for Deep Graph
Matching [14.713628231555223]
本稿では,線形代入問題を高次元空間にマッピングできる新しいエンドツーエンドニューラルネットワークを提案する。
我々のモデルは、ノードの相対的な位置に対するアンカーセットを構成する。
そして、相対位置の尺度に基づいて、ターゲットノードと各アンカーノードの特徴情報を集約する。
論文 参考訳（メタデータ） (2023-01-05T06:54:21Z) - Deep Learning to Jointly Schema Match, Impute, and Transform Databases [19.200830026362425]
複数の原点からのデータを非マップで部分的に重複する機能で結合することは、堅牢で一般化可能なアルゴリズムを開発するための前提条件である。
我々はこの問題に対処する2つの新しい手順を策定する。
2つの電子健康記録データベースを用いた合成および実世界の実験において、我々のアルゴリズムは可変集合に適合する既存のベースラインよりも優れている。
論文 参考訳（メタデータ） (2022-06-22T21:25:59Z) - On the complexity of finding set repairs for data-graphs [2.519906683279153]
データ値を持つグラフデータベースのサブセットとスーパーセット修復の計算問題について検討する。
本稿では,Reg-GX表現の正のフラグメントに対して,サブセットタイムのアルゴリズムが適用可能であるのに対して,言語の完全な表現力は難解であることを示す。
論文 参考訳（メタデータ） (2022-06-15T13:01:26Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - Consensus-Guided Correspondence Denoising [67.35345850146393]
本稿では,地域間コンセンサス学習フレームワークと対応関係を異色化し,対応関係をロバストに識別する。
ローカル地域からグローバル地域への動的グラフから推定されるコンセンサススコアに基づいて,信頼度の高い候補を初期マッチングから蒸留する新しい「プルーニング」ブロックを導入した。
本手法は、堅牢なラインフィッティング、ワイドベースライン画像マッチング、画像ローカリゼーションベンチマークを顕著なマージンで上回る。
論文 参考訳（メタデータ） (2021-01-03T09:10:00Z) - Articulated Shape Matching Using Laplacian Eigenfunctions and
Unsupervised Point Registration [38.16866987817019]
スペクトルグラフ理論は、これらのグラフを低次元空間にマッピングし、それらの埋め込みを整列させることで形状と一致させることができる。
我々は、ラプラシア行列の固有関数の最適部分集合を選択することによって、2つの同値な$K$-次元の点集合の最良の整合を求める新しい定式化を導出する。
論文 参考訳（メタデータ） (2020-12-14T08:49:25Z) - Coordinated Reasoning for Cross-Lingual Knowledge Graph Alignment [74.0482641714311]
本稿では,2つのコーディネート推論手法,すなわち Easy-to-Hardデコード戦略とジョイントエンティティアライメントアルゴリズムを導入する。
我々のモデルは最先端の性能を実現し,提案手法は既存のベースラインを大幅に改善する。
論文 参考訳（メタデータ） (2020-01-23T18:41:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。