論文の概要: Ranking a set of objects: a graph based least-square approach

• arxiv url: http://arxiv.org/abs/2002.11590v1
• Date: Wed, 26 Feb 2020 16:19:09 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-28 15:55:24.453273
• Title: Ranking a set of objects: a graph based least-square approach
• Title（参考訳）: オブジェクトの集合をランク付けする:グラフベースの最小二乗アプローチ
• Authors: Evgenia Christoforou, Alessandro Nordio, Alberto Tarable, Emilio Leonardi
• Abstract要約: 同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
• 参考スコア（独自算出の注目度）: 70.7866286425868
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We assume that objects are endowed with intrinsic qualities and that the probability with which an object is preferred to another depends only on the difference between the qualities of the two competitors. We propose a class of non-adaptive ranking algorithms that rely on a least-squares optimization criterion for the estimation of qualities. Such algorithms are shown to be asymptotically optimal (i.e., they require $O(\frac{N}{\epsilon^2}\log \frac{N}{\delta})$ comparisons to be $(\epsilon, \delta)$-PAC). Numerical results show that our schemes are very efficient also in many non-asymptotic scenarios exhibiting a performance similar to the maximum-likelihood algorithm. Moreover, we show how they can be extended to adaptive schemes and test them on real-world datasets.
• Abstract（参考訳）: 同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 対象物には本質的な性質が与えられており、対象物が他者に好まれる確率は、2つの競合物の質の違いにのみ依存していると仮定する。 品質推定のための最小二乗最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。 このようなアルゴリズムは漸近的に最適であることが示される(つまり、$O(\frac{N}{\epsilon^2}\log \frac{N}{\delta})$比較は$(\epsilon, \delta)$-PAC)。 数値計算の結果,提案手法は最大化アルゴリズムに類似した性能を示す多くの非漸近的シナリオにおいても非常に効率的であることがわかった。 さらに,それらを適応スキームに拡張し,実世界のデータセット上でテストする方法を示す。

関連論文リスト

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Sorting with Predictions [1.7042264000899532]
  学習強化アルゴリズムのレンズをソートする根本的な問題について検討する。 我々は,$O(sum_i log eta_i)$の正確な比較だけで,新しい,シンプルなアルゴリズムを設計する。 比較複雑性は, 検証された誤差測度に対して理論的に最適であることを示す。
  論文  参考訳（メタデータ） (2023-11-01T18:00:03Z)
• Subset-Based Instance Optimality in Private Estimation [23.173651165908282]
  我々は、幅広いデータセット特性を推定する際に、インスタンス最適性の概念を実現するプライベートアルゴリズムを構築する方法を示す。 提案アルゴリズムは,分布的な仮定の下で,既存のアルゴリズムの性能を同時に一致または超過する。
  論文  参考訳（メタデータ） (2023-03-01T18:49:10Z)
• Rank-based Non-dominated Sorting [0.0]
  我々は、高額な支配比較を避けるために、ソート安定性と順序情報を利用した非支配的なソート手法であるランクソートを導入する。 2つのアルゴリズム的変種が提案されている: 1つはRandOrdinal (RO) で、支配性を決定するために順序付き階数比較(英語版)(ordinal rank comparisons)を用いており、O(N) 空間を必要とする。 NSGA2アルゴリズムと合成ベンチマークを用いた実験シミュレーションにおいて,提案手法の有効性を他の手法と比較した。
  論文  参考訳（メタデータ） (2022-03-25T13:59:42Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  ランキングアグリゲーション問題では、各項目を比較する際に、様々な精度レベルが示される。 本稿では,ノイズのあるペアワイズ比較によってアイテムのランクを推定する,除去に基づくアクティブサンプリング戦略を提案する。 提案アルゴリズムは,商品の真のランキングを高い確率で返却できることを示す。
  論文  参考訳（メタデータ） (2021-10-08T13:51:55Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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