論文の概要: Explainable Clustering Beyond Worst-Case Guarantees

• arxiv url: http://arxiv.org/abs/2411.01576v2
• Date: Thu, 07 Aug 2025 14:56:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-08 23:24:00.895322
• Title: Explainable Clustering Beyond Worst-Case Guarantees
• Title（参考訳）: 最悪の保証以上の説明可能なクラスタリング
• Authors: Maximilian Fleissner, Maedeh Zarvandi, Debarghya Ghoshdastidar,
• Abstract要約: Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) による説明可能なクラスタリング問題について検討した。 説明可能なクラスタリングの目標は、軸に沿った決定木に$K$のリーフと最小のクラスタリングコスト(すべてのリーフがクラスタである)を適合させることだ。
• 参考スコア（独自算出の注目度）: 5.65604054654671
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the explainable clustering problem first posed by Moshkovitz, Dasgupta, Rashtchian, and Frost (ICML 2020). The goal of explainable clustering is to fit an axis-aligned decision tree with $K$ leaves and minimal clustering cost (where every leaf is a cluster). The fundamental theoretical question in this line of work is the \textit{price of explainability}, defined as the ratio between the clustering cost of the tree and the optimal cost. Numerous papers have provided worst-case guarantees on this quantity. For $K$-medians, it has recently been shown that the worst-case price of explainability is $\Theta(\log K)$. While this settles the matter from a data-agnostic point of view, two important questions remain unanswered: Are tighter guarantees possible for well-clustered data? And can we trust decision trees to recover underlying cluster structures? In this paper, we place ourselves in a statistical setting of mixture models to answer both questions. We prove that better guarantees are indeed feasible for well-clustered data. Our algorithm takes as input a mixture model and constructs a tree in data-independent time. We then extend our analysis to kernel clustering, deriving new guarantees that significantly improve over existing worst-case bounds.
• Abstract（参考訳）: まず,Moshkovitz,Dasgupta,Rashtchian,Frost (ICML 2020。 説明可能なクラスタリングの目標は、軸に沿った決定木に$K$のリーフと最小のクラスタリングコスト(すべてのリーフがクラスタである)を適合させることだ。 この研究の基本的な理論的問題は、ツリーのクラスタリングコストと最適なコストの比として定義される「説明可能性のtextit{price}」である。 多くの論文が、この量について最悪のケースを保証している。 K$-mediansの場合、説明可能性の最悪の価格は$\Theta(\log K)$である。 データに依存しない観点から、この問題は解決するが、2つの重要な疑問は未解決のままである。 そして、下層のクラスタ構造を回復するために決定木を信頼できますか? 本稿では,双方の質問に答えるために,混合モデルの統計的設定に自分自身を配置する。 私たちは、十分にクラスタ化されたデータに対して、より良い保証が実際に実現可能であることを証明しています。 筆者らのアルゴリズムは混合モデルを入力として,データに依存しない時間に木を構築する。 その後、分析をカーネルクラスタリングに拡張し、既存の最悪のバウンダリを大幅に改善する新たな保証を導き出します。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Generalization Performance of Ensemble Clustering: From Theory to Algorithm [57.176040163699554]
  本稿では,アンサンブルクラスタリングにおける一般化誤差,過剰リスク,一貫性に着目した。 有限クラスタリングに様々な重みを割り当てることで、経験的平均クラスタリングと期待値との誤差を最小化する。 我々は、新しいアンサンブルクラスタリングアルゴリズムを開発するために、我々の理論をインスタンス化する。
  論文  参考訳（メタデータ） (2025-06-01T09:34:52Z)
• IsoSEL: Isometric Structural Entropy Learning for Deep Graph Clustering in Hyperbolic Space [57.036143666293334]
  グラフクラスタリングは、機械学習における長年のトピックである。 本稿では,K を含まない深層グラフクラスタリングという,現実の非均衡を考慮した問題について検討する。 深層グラフクラスタリングのための新しいIsoSELフレームワークを提案する。このフレームワークでは、双曲空間のローレンツモデルにおける分割木を学習するための双曲型ニューラルネットワークを設計する。
  論文  参考訳（メタデータ） (2025-04-14T08:21:41Z)
• Learning Decision Trees as Amortized Structure Inference [59.65621207449269]
  本稿では,予測決定木アンサンブルを学習するためのハイブリッドアモータイズされた構造推論手法を提案する。 提案手法であるDT-GFNは,標準分類ベンチマークにおける最先端決定木やディープラーニング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-03-10T07:05:07Z)
• Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
  我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。 近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。 非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
  論文  参考訳（メタデータ） (2024-10-31T15:56:50Z)
• Estimating Causal Effects from Learned Causal Networks [56.14597641617531]
  本稿では、離散可観測変数に対する因果影響クエリに応答する代替パラダイムを提案する。 観測データから直接因果ベイズネットワークとその共起潜伏変数を学習する。 本手法は, 推定手法よりも有効であることを示す。
  論文  参考訳（メタデータ） (2024-08-26T08:39:09Z)
• A Unified Approach to Extract Interpretable Rules from Tree Ensembles via Integer Programming [2.1408617023874443]
  ツリーアンサンブルは非常に人気のある機械学習モデルであり、教師付き分類と回帰タスクの有効性で知られている。 我々の研究は、訓練された木アンサンブルから最適化されたルールのリストを抽出することを目的としており、ユーザーは完全なモデルの予測力をほとんど保持する凝縮された解釈可能なモデルを提供する。 我々の広範な計算実験は,木アンサンブルに対する予測性能と忠実度の観点から,本手法が他のルール抽出法と競合することを示す統計的に有意な証拠を提供する。
  論文  参考訳（メタデータ） (2024-06-30T22:33:47Z)
• Learning accurate and interpretable decision trees [27.203303726977616]
  我々は、同じドメインから繰り返しデータにアクセスして決定木学習アルゴリズムを設計するためのアプローチを開発する。 本研究では,ベイズ決定木学習における事前パラメータのチューニングの複雑さについて検討し,その結果を決定木回帰に拡張する。 また、学習した決定木の解釈可能性について検討し、決定木を用いた説明可能性と精度のトレードオフを最適化するためのデータ駆動型アプローチを提案する。
  論文  参考訳（メタデータ） (2024-05-24T20:10:10Z)
• Forecasting with Hyper-Trees [50.72190208487953]
  Hyper-Treesは時系列モデルのパラメータを学習するために設計されている。 対象とする時系列モデルのパラメータを特徴に関連付けることで、Hyper-Treesはパラメータ非定常性の問題にも対処する。 この新しいアプローチでは、木はまず入力特徴から情報表現を生成し、浅いネットワークはターゲットモデルパラメータにマップする。
  論文  参考訳（メタデータ） (2024-05-13T15:22:15Z)
• Unboxing Tree Ensembles for interpretability: a hierarchical visualization tool and a multivariate optimal re-built tree [0.34530027457862006]
  我々は,木組モデルの解釈可能な表現を開発し,その振る舞いに関する貴重な洞察を提供する。 提案モデルは,木組決定関数を近似した浅い解釈可能な木を得るのに有効である。
  論文  参考訳（メタデータ） (2023-02-15T10:43:31Z)
• Interpretations Steered Network Pruning via Amortized Inferred Saliency Maps [85.49020931411825]
  限られたリソースを持つエッジデバイスにこれらのモデルをデプロイするには、畳み込みニューラルネットワーク(CNN)圧縮が不可欠である。 本稿では,新しい視点からチャネルプルーニング問題に対処するために,モデルの解釈を活用して,プルーニング過程を解析する手法を提案する。 本研究では,実時間スムーズなスムーズなスムーズなスムーズなマスク予測を行うセレクタモデルを導入することで,この問題に対処する。
  論文  参考訳（メタデータ） (2022-09-07T01:12:11Z)
• How to Find a Good Explanation for Clustering? [7.951746797489421]
  Moshkovitz氏、Dasgupta氏、Rashtchian氏、Frost氏(ICML 2020)は、説明可能な$k$-meansと$k$-medianクラスタリングのエレガントなモデルを提案した。 説明可能なクラスタリングに関する2つの自然なアルゴリズム的問題について検討する。 厳密なアルゴリズム分析では、入力サイズ、データの寸法、外乱数、クラスタ数、近似比といったパラメータが、説明可能なクラスタリングの計算複雑性に与える影響について光を当てています。
  論文  参考訳（メタデータ） (2021-12-13T11:48:38Z)
• Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
  我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。 我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
  論文  参考訳（メタデータ） (2021-10-27T10:45:21Z)
• A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds [9.546094657606178]
  本研究では,異なる回帰モデルに対する決定木の一般化性能について検討する。 これにより、アルゴリズムが新しいデータに一般化するために(あるいは作らない)仮定する帰納的バイアスが引き起こされる。 スパース加法モデルに適合する大規模な決定木アルゴリズムに対して、シャープな2乗誤差一般化を低い境界で証明する。
  論文  参考訳（メタデータ） (2021-10-18T21:22:40Z)
• Near-Optimal Explainable $k$-Means for All Dimensions [13.673697350508965]
  k$-meansのコストは最大$k1 - 2/dmathrmpoly(dlog k)$である。 改良された$k1 - 2/dmathrmpolylog(k)$で、$k,dge 2$から$k$のポリ対数係数までのすべての選択に最適であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T16:59:03Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• Dive into Decision Trees and Forests: A Theoretical Demonstration [0.0]
  決定木は"divide-and-conquer"の戦略を使用して、入力機能とラベル間の依存性に関する複雑な問題を小さなものに分割します。 近年, 計算広告, 推薦システム, 情報検索などの性能が大幅に向上している。
  論文  参考訳（メタデータ） (2021-01-20T16:47:59Z)
• On the price of explainability for some clustering problems [1.52292571922932]
  我々は,決定木を用いて説明可能性を実現する自然モデルに対して,上下境界を提供する。 k$-means と $k$-medians の問題に対して、上限は [moshkovitz et.] によって得られる問題を改善する。 低次元のための al, ICML 20]。 もう1つの貢献は、$k$-means問題に対する説明可能なクラスタリングを構築するための単純で効率的なアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-05T15:08:25Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。 我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。 MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
  論文  参考訳（メタデータ） (2020-12-29T18:05:05Z)
• Handling Missing Data in Decision Trees: A Probabilistic Approach [41.259097100704324]
  確率論的アプローチを採り、決定木で欠落したデータを扱う問題に対処する。 我々は, トラクタブル密度推定器を用いて, モデルの「予測予測」を計算する。 学習時には「予測予測損失」を最小限に抑えて学習済みの樹木の微調整パラメーターを微調整する。
  論文  参考訳（メタデータ） (2020-06-29T19:54:54Z)
• ExKMC: Expanding Explainable $k$-Means Clustering [19.702066333512548]
  説明可能性と精度のトレードオフに着目し,$k$-meansクラスタリングのアルゴリズムについて検討した。 我々は、新しい説明可能な$k$-meansクラスタリングアルゴリズム、ExKMCを開発し、$k' geq k$を加算し、$k'$の葉を持つ決定木を出力する。 ExKMCは、標準的な決定木法と説明可能なクラスタリングのための他のアルゴリズムの両方を上回る、低コストのクラスタリングを生成する。
  論文  参考訳（メタデータ） (2020-06-03T17:14:55Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Linguistically Driven Graph Capsule Network for Visual Question Reasoning [153.76012414126643]
  我々は「言語的に駆動されるグラフカプセルネットワーク」と呼ばれる階層的構成推論モデルを提案する。 具体的には,各カプセルを最下層に結合させ,元の質問に1つの単語を埋め込んだ言語的埋め込みを視覚的証拠で橋渡しする。 CLEVRデータセット、CLEVR合成生成テスト、およびFinalQAデータセットの実験は、我々のエンドツーエンドモデルの有効性と構成一般化能力を示す。
  論文  参考訳（メタデータ） (2020-03-23T03:34:25Z)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。 一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。 我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-02-28T04:21:53Z)

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

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