論文の概要: Pareto-optimal clustering with the primal deterministic information
bottleneck
- arxiv url: http://arxiv.org/abs/2204.02489v1
- Date: Tue, 5 Apr 2022 21:08:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-07 14:19:13.329797
- Title: Pareto-optimal clustering with the primal deterministic information
bottleneck
- Title（参考訳）: 主決定論的情報ボトルネックを用いたパレート最適クラスタリング
- Authors: Andrew K. Tan and Max Tegmark and Isaac L. Chuang
- Abstract要約: 本稿では,損失圧縮の定式化に焦点をあてる。
我々は、以前研究された双対対対よりもはるかにリッチなフロンティアで結果を示す。
アルゴリズムを用いて、3つの異なるタスクのDIBフロンティアをマッピングする。
- 参考スコア（独自算出の注目度）: 2.6411634335546887
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: At the heart of both lossy compression and clustering is a trade-off between
the fidelity and size of the learned representation. Our goal is to map out and
study the Pareto frontier that quantifies this trade-off. We focus on the
Deterministic Information Bottleneck (DIB) formulation of lossy compression,
which can be interpreted as a clustering problem. To this end, we introduce the
{\it primal} DIB problem, which we show results in a much richer frontier than
its previously studied dual counterpart. We present an algorithm for mapping
out the Pareto frontier of the primal DIB trade-off that is also applicable to
most other two-objective clustering problems. We study general properties of
the Pareto frontier, and give both analytic and numerical evidence for
logarithmic sparsity of the frontier in general. We provide evidence that our
algorithm has polynomial scaling despite the super-exponential search space;
and additionally propose a modification to the algorithm that can be used where
sampling noise is expected to be significant. Finally, we use our algorithm to
map the DIB frontier of three different tasks: compressing the English
alphabet, extracting informative color classes from natural images, and
compressing a group theory inspired dataset, revealing interesting features of
frontier, and demonstrating how the structure of the frontier can be used for
model selection with a focus on points previously hidden by the cloak of the
convex hull.
- Abstract（参考訳）: 損失のある圧縮とクラスタリングの両方の中心は、学習された表現の忠実度とサイズの間のトレードオフである。
私たちの目標は、このトレードオフを定量化するParetoフロンティアをマップアウトし、研究することにあります。
本稿では,クラスタ化問題として解釈可能な,損失圧縮のための決定論的情報ボトルネック(dib)の定式化に注目する。
この目的のために、我々は、以前に研究された双対問題よりもはるかにリッチなフロンティアの結果を示す、 {\it primal} DIB問題を導入する。
本稿では,他の2目的クラスタリング問題にも適用可能なプライマルdibトレードオフのparetoフロンティアをマッピングするアルゴリズムを提案する。
我々は,パレートフロンティアの一般特性を調査し,フロンティアの対数的スパース性に関する解析的および数値的証拠を与える。
超指数探索空間にも拘わらず,本アルゴリズムが多項式スケーリングを持つことを示すとともに,サンプリングノイズが重要と期待される場合に使用できるアルゴリズムの修正を提案する。
最後に、我々のアルゴリズムを用いて、3つの異なるタスクのDIBフロンティアをマッピングする: 英語アルファベットを圧縮し、自然画像から情報的カラークラスを抽出し、グループ理論にインスパイアされたデータセットを圧縮し、フロンティアの興味深い特徴を明らかにする。
関連論文リスト
- Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
乱れのないデータから歪んだ表現を学習することは、機械学習における根本的な課題である。
本稿では,2次最適輸送に基づく非交叉表現学習手法を提案する。
提案手法の有効性を4つの標準ベンチマークで示す。
論文 参考訳（メタデータ） (2024-07-10T16:51:32Z) - A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。
ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。
パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
論文 参考訳（メタデータ） (2022-05-24T00:03:25Z) - Quantum Motif Clustering [0.0]
モチーフクラスタリング(モチーフクラスタリング)と呼ばれる高次パターンに基づいて,グラフをクラスタリングするための3つの量子アルゴリズムを提案する。
一つはGroverサーチの簡単な応用で、もうひとつは量子近似計数を使い、もうひとつは様々な設定で、最も高速な古典的アルゴリズムよりも、平方根のようなスピードアップが得られる。
論文 参考訳（メタデータ） (2021-11-25T19:00:01Z) - Clustering by Maximizing Mutual Information Across Views [62.21716612888669]
本稿では,共同表現学習とクラスタリングを組み合わせた画像クラスタリングのための新しいフレームワークを提案する。
提案手法は,様々な画像データセットにおける最先端の単一ステージクラスタリング手法よりも優れていた。
論文 参考訳（メタデータ） (2021-07-24T15:36:49Z) - Spatial-spectral Hyperspectral Image Classification via Multiple Random
Anchor Graphs Ensemble Learning [88.60285937702304]
本稿では,複数のランダムアンカーグラフアンサンブル学習(RAGE)を用いた空間スペクトルHSI分類手法を提案する。
まず、各選択されたバンドのより記述的な特徴を抽出し、局所的な構造と領域の微妙な変化を保存するローカルバイナリパターンを採用する。
次に,アンカーグラフの構成に適応隣接代入を導入し,計算複雑性を低減した。
論文 参考訳（メタデータ） (2021-03-25T09:31:41Z) - Contour Integration using Graph-Cut and Non-Classical Receptive Field [4.935491924643742]
本稿では,他のアルゴリズムのエッジセグメントから画像の輪郭を検出する新しい手法を提案する。
提案したエネルギー関数は、テクスチャノイズを抑制するのに役立つ一次視覚野の周囲変調にインスパイアされている。
論文 参考訳（メタデータ） (2020-10-27T19:07:13Z) - On spectral algorithms for community detection in stochastic blockmodel
graphs with vertex covariates [6.029067308095145]
本稿では,ブロックモデルグラフにおける頂点クラスタリングのための2つのモデルベースアルゴリズムの比較解析を行う。
2つ目のアルゴリズムは,基礎となるブロック構造を明らかにする利点があることを示す。
本研究は,グラフのブロック構造に影響を及ぼす観測因子と観測されていない因子を区別することの重要性を強調した。
論文 参考訳（メタデータ） (2020-07-04T18:22:22Z) - Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
重複する部分グラフを多数必要とせず,完全に学習可能なクラスタリングフレームワークを提案する。
提案手法はクラスタリングの精度を大幅に向上させ,その上で訓練した認識モデルの性能を向上させるが,既存の教師付き手法に比べて桁違いに効率的である。
論文 参考訳（メタデータ） (2020-04-01T13:39:37Z) - GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
我々は,最も困難なブラックボックス設定の1つにおいて,逆例を生成するためのフレームワークを提案する。
我々のフレームワークは、ディープネットワークの決定境界は通常、データサンプルの近傍で小さな平均曲率を持つという観察に基づいている。
論文 参考訳（メタデータ） (2020-03-13T20:03:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。