論文の概要: A Revenue Function for Comparison-Based Hierarchical Clustering
- arxiv url: http://arxiv.org/abs/2211.16459v2
- Date: Sun, 2 Apr 2023 13:09:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-05 00:03:03.924441
- Title: A Revenue Function for Comparison-Based Hierarchical Clustering
- Title（参考訳）: 比較階層クラスタリングのための収益関数
- Authors: Aishik Mandal, Micha\"el Perrot, Debarghya Ghoshdastidar
- Abstract要約: 比較のみを用いて,デンドログラムの良さを測定できる新たな収益関数を提案する。
この関数は、ペアの類似性を用いた階層的クラスタリングにおけるDasguptaのコストと密接に関連していることを示す。
理論的には,提案した収益関数を用いて,三重項比較の少ない潜在階層をおよそ復元できるかどうかというオープンな問題を解く。
- 参考スコア（独自算出の注目度）: 5.683072566711975
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Comparison-based learning addresses the problem of learning when, instead of
explicit features or pairwise similarities, one only has access to comparisons
of the form: \emph{Object $A$ is more similar to $B$ than to $C$.} Recently, it
has been shown that, in Hierarchical Clustering, single and complete linkage
can be directly implemented using only such comparisons while several
algorithms have been proposed to emulate the behaviour of average linkage.
Hence, finding hierarchies (or dendrograms) using only comparisons is a well
understood problem. However, evaluating their meaningfulness when no
ground-truth nor explicit similarities are available remains an open question.
In this paper, we bridge this gap by proposing a new revenue function that
allows one to measure the goodness of dendrograms using only comparisons. We
show that this function is closely related to Dasgupta's cost for hierarchical
clustering that uses pairwise similarities. On the theoretical side, we use the
proposed revenue function to resolve the open problem of whether one can
approximately recover a latent hierarchy using few triplet comparisons. On the
practical side, we present principled algorithms for comparison-based
hierarchical clustering based on the maximisation of the revenue and we
empirically compare them with existing methods.
- Abstract（参考訳）: 比較ベースの学習は、明示的な特徴やペアの類似性の代わりに、形式の比較へのアクセスしかできない場合に、学習の問題に対処する。
近年,階層クラスタリングでは,そのような比較のみを用いて単一リンクと完全リンクを直接実装でき,平均リンクの挙動をエミュレートするアルゴリズムがいくつか提案されている。
したがって、比較のみを用いて階層(あるいはデンドログラム)を見つけることはよく理解された問題である。
しかし、根拠や明示的な類似性がない場合の有意義性の評価は未解決の問題である。
本稿では,このギャップを,比較のみを用いてデンドログラムの良さを計測できる新たな収益関数を提案することによって埋める。
この関数は,ペアワイズ類似性を用いた階層的クラスタリングにおけるdasguptaのコストと密接に関連していることを示す。
理論的には,提案した収益関数を用いて,三重項比較の少ない潜在階層をおよそ復元できるかどうかというオープンな問題を解く。
実用面では,収益の最大化に基づく比較ベース階層クラスタリングの原則アルゴリズムを提案し,既存の手法と実証的に比較する。
関連論文リスト
- Learnable Pillar-based Re-ranking for Image-Text Retrieval [119.9979224297237]
画像テキスト検索は、モダリティギャップを埋め、意味的類似性に基づいてモダリティコンテンツを検索することを目的としている。
一般的なポストプロセッシング手法であるリグレードは, 単一モダリティ検索タスクにおいて, 隣り合う関係を捕捉する優位性を明らかにしている。
本稿では,画像テキスト検索のための新しい学習可能な柱型リグレードパラダイムを提案する。
論文 参考訳（メタデータ） (2023-04-25T04:33:27Z) - Ranking from Pairwise Comparisons in General Graphs and Graphs with
Locality [3.1219977244201056]
本稿では,古典的Bradley-Terry-Luceモデル(BTL)のペア比較によるランキング問題について検討する。
十分に多くのサンプルを用いて,Cram'er-Rao の下界と一致するエントリワイズ推定誤差が得られることを示す。
我々は、最も広いサンプルを持つ体制においても、同様の保証を確実に達成できる分割対コンカマーのアルゴリズムについて検討する。
論文 参考訳（メタデータ） (2023-04-13T21:14:30Z) - Efficient computation of rankings from pairwise comparisons [0.0]
我々は、同じ結果を返すが、はるかに高速な代替かつ同様の単純なイテレーションについて記述する。
本稿では,このアルゴリズムをサンプルデータセットに適用し,その収束性に関する多くの結果を導出する。
論文 参考訳（メタデータ） (2022-06-30T19:39:09Z) - Decreasing Annotation Burden of Pairwise Comparisons with
Human-in-the-Loop Sorting: Application in Medical Image Artifact Rating [3.5314411880556063]
ペア比較によるランキングでは、順序分類よりも信頼性が向上している。
本稿では,定量的な測定値によってランク付けに必要なペアワイズ比較数を減少させる手法を提案する。
論文 参考訳（メタデータ） (2022-02-10T04:02:45Z) - Deep Hierarchy in Bandits [51.22833900944146]
行動の報酬は、しばしば相関する。
統計的効率を最大化するためには,これらの相関を学習に活用することが重要である。
平均作用報酬の相関が階層的ベイズモデルで表されるこの問題のバンディット変法を定式化する。
論文 参考訳（メタデータ） (2022-02-03T08:15:53Z) - Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise
Comparisons [85.5955376526419]
ランキングアグリゲーション問題では、各項目を比較する際に、様々な精度レベルが示される。
本稿では,ノイズのあるペアワイズ比較によってアイテムのランクを推定する,除去に基づくアクティブサンプリング戦略を提案する。
提案アルゴリズムは,商品の真のランキングを高い確率で返却できることを示す。
論文 参考訳（メタデータ） (2021-10-08T13:51:55Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - How to Design Robust Algorithms using Noisy Comparison Oracle [12.353002222958605]
メトリクスに基づく比較操作は、様々なクラスタリング技術の研究に基本的である。
本稿では,最接近探索,最接近探索,最接近探索など様々な問題について検討する。
k中心クラスタリングと凝集階層クラスタリングのためのロバストなアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-05-12T16:58:09Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - Near-Optimal Comparison Based Clustering [7.930242839366938]
提案手法は, ほぼ最適な比較数を用いて, 植え付けクラスタリングを復元できることを示す。
理論的知見を実証的に検証し,実データ上での手法の良好な振る舞いを実証する。
論文 参考訳（メタデータ） (2020-10-08T12:03:13Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。