論文の概要: Pair-Matching: Links Prediction with Adaptive Queries
- arxiv url: http://arxiv.org/abs/1905.07342v3
- Date: Tue, 5 Mar 2024 17:45:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-10 19:40:16.673443
- Title: Pair-Matching: Links Prediction with Adaptive Queries
- Title（参考訳）: pair-matching: アダプティブクエリによるリンク予測
- Authors: Christophe Giraud and Yann Issartel and Luc Leh\'ericy and Matthieu
Lerasle
- Abstract要約: グラフが2つのコミュニティを持つブロックモデル(SBM)に従って生成される場合、サブ線形後悔が達成可能であることを示す。
この論文は, コミュニティの数が2より多い場合に, 最適後悔に関する予想によって締めくくられる。
- 参考スコア（独自算出の注目度）: 7.22341371511072
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The pair-matching problem appears in many applications where one wants to
discover good matches between pairs of entities or individuals. Formally, the
set of individuals is represented by the nodes of a graph where the edges,
unobserved at first, represent the good matches. The algorithm queries pairs of
nodes and observes the presence/absence of edges. Its goal is to discover as
many edges as possible with a fixed budget of queries. Pair-matching is a
particular instance of multi-armed bandit problem in which the arms are pairs
of individuals and the rewards are edges linking these pairs. This bandit
problem is non-standard though, as each arm can only be played once.
Given this last constraint, sublinear regret can be expected only if the
graph presents some underlying structure. This paper shows that sublinear
regret is achievable in the case where the graph is generated according to a
Stochastic Block Model (SBM) with two communities. Optimal regret bounds are
computed for this pair-matching problem. They exhibit a phase transition
related to the Kesten-Stigum threshold for community detection in SBM. The
pair-matching problem is considered in the case where each node is constrained
to be sampled less than a given amount of times. We show how optimal regret
rates depend on this constraint. The paper is concluded by a conjecture
regarding the optimal regret when the number of communities is larger than 2.
Contrary to the two communities case, we argue that a statistical-computational
gap would appear in this problem.
- Abstract（参考訳）: ペアマッチング問題は、エンティティのペアまたは個人間の良いマッチングを見つけようとする多くのアプリケーションで現れる。
形式的には、個人の集合はグラフのノードで表され、エッジは最初は観測されていないが、良いマッチを表す。
アルゴリズムはノードのペアをクエリし、エッジの有無を観察する。
その目標は、クエリの固定された予算で可能な限り多くのエッジを見つけることだ。
ペアマッチングは、腕が個人のペアであり、報酬がこれらのペアをつなぐエッジであるマルチアームのバンディット問題の特定の例である。
このバンディット問題は、各アームが1回しかプレイできないため、非標準である。
この最後の制約を考えると、グラフが基底構造を示す場合にのみ、部分線型後悔が期待できる。
本稿では,2つのコミュニティを持つ確率ブロックモデル(SBM)に基づいてグラフが生成される場合に,サブ線形後悔が達成可能であることを示す。
このペアマッチング問題に対して、最適後悔境界が計算される。
彼らはSBMにおけるコミュニティ検出のためのKesten-Stigumしきい値に関連する相転移を示す。
ペアマッチング問題は、各ノードが与えられた時間未満のサンプリングを制限されている場合に考慮される。
この制約がいかに最適な後悔率に依存するかを示す。
本論文は,コミュニティ数が2以上である場合の後悔の最適性に関する推測によって結論づける。
2つのコミュニティのケースとは対照的に,この問題には統計計算のギャップが現れるだろう。
関連論文リスト
- Graph Feedback Bandits with Similar Arms [9.701475722399646]
グラフフィードバックを用いたマルチアームバンディット問題について検討する。
UCBに基づく2つのアルゴリズムを導入する: D-UCBは問題非依存の後悔上界、C-UCBは問題依存の上界である。
論文 参考訳（メタデータ） (2024-05-18T04:20:14Z) - Community Detection in the Multi-View Stochastic Block Model [47.43048484980115]
本稿では,無神論的な観点から,複数の潜在的相関グラフ上でのコミュニティ検出の問題について考察する。
我々はまず,同じノードの集合上で相関グラフを生成するために設計された多視点情報ブロックモデル (MVSBM) と呼ばれるランダムグラフモデルを考案した。
論文 参考訳（メタデータ） (2024-01-17T13:39:38Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - Efficient Algorithms for Exact Graph Matching on Correlated Stochastic
Block Models with Constant Correlation [7.914348940034351]
本稿では,グラフとコミュニティ構造をマッチングする効率的なアルゴリズムを提案する。
我々のアルゴリズムは2つの相関ブロックモデル間の正確なマッチングを実現する最初の低次時間アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-31T09:06:50Z) - 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) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳（メタデータ） (2021-06-18T15:01:01Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。