論文の概要: From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical
Clustering
- arxiv url: http://arxiv.org/abs/2010.00402v1
- Date: Thu, 1 Oct 2020 13:43:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-12 07:44:01.768334
- Title: From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical
Clustering
- Title（参考訳）: 木から継続的埋め込みとバックへ:双曲的階層クラスタリング
- Authors: Ines Chami, Albert Gu, Vaggos Chatziafratis and Christopher R\'e
- Abstract要約: 本稿では,Dasguptaの離散最適化問題に対して,証明可能な品質保証を用いた最初の連続緩和を提案する。
勾配勾配勾配の近似解でさえ、凝集性クラスタリングよりも優れた品質を有することを示す。
また、下流分類タスクにおけるエンドツーエンドトレーニングによるHypHCの柔軟性についても強調する。
- 参考スコア（独自算出の注目度）: 33.000371053304676
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Similarity-based Hierarchical Clustering (HC) is a classical unsupervised
machine learning algorithm that has traditionally been solved with heuristic
algorithms like Average-Linkage. Recently, Dasgupta reframed HC as a discrete
optimization problem by introducing a global cost function measuring the
quality of a given tree. In this work, we provide the first continuous
relaxation of Dasgupta's discrete optimization problem with provable quality
guarantees. The key idea of our method, HypHC, is showing a direct
correspondence from discrete trees to continuous representations (via the
hyperbolic embeddings of their leaf nodes) and back (via a decoding algorithm
that maps leaf embeddings to a dendrogram), allowing us to search the space of
discrete binary trees with continuous optimization. Building on analogies
between trees and hyperbolic space, we derive a continuous analogue for the
notion of lowest common ancestor, which leads to a continuous relaxation of
Dasgupta's discrete objective. We can show that after decoding, the global
minimizer of our continuous relaxation yields a discrete tree with a (1 +
epsilon)-factor approximation for Dasgupta's optimal tree, where epsilon can be
made arbitrarily small and controls optimization challenges. We experimentally
evaluate HypHC on a variety of HC benchmarks and find that even approximate
solutions found with gradient descent have superior clustering quality than
agglomerative heuristics or other gradient based algorithms. Finally, we
highlight the flexibility of HypHC using end-to-end training in a downstream
classification task.
- Abstract（参考訳）: 類似性に基づく階層クラスタリング(HC)は古典的な教師なし機械学習アルゴリズムであり、伝統的に平均リンクのようなヒューリスティックアルゴリズムで解決されてきた。
近年,大域的コスト関数を導入することにより,HCを離散最適化問題として再編成した。
そこで本研究では,dasguptaの離散最適化問題に対して,品質保証を施した最初の連続緩和を提案する。
この手法の重要なアイデアであるhyphcは、離散木から連続表現への直接対応(葉ノードの双曲埋め込みによる)とバック(葉埋め込みをデンドログラムにマッピングするデコードアルゴリズムによる)を示すことで、離散二分木の空間を連続最適化により探索することができる。
木と双曲空間の類似性に基づいて、我々は最小の共通祖先の概念の連続的な類似を導き、ダスグプタの離散的な目的を連続的に緩和する。
復号後、我々の連続緩和の大域的最小化はダスガプタの最適木に対する(1 + epsilon)-因子近似を持つ離散木を生じさせ、エプシロンは任意に小さくでき最適化の課題を制御できることを示すことができる。
我々は,HypHCを様々なHCベンチマークで実験的に評価し,勾配降下を伴う近似解であっても凝集ヒューリスティックスや他の勾配に基づくアルゴリズムよりもクラスタリング品質が優れていることを発見した。
最後に,下流分類タスクにおけるエンドツーエンドトレーニングを用いたhyphcの柔軟性を強調する。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Optimal estimation of Gaussian (poly)trees [25.02920605955238]
分布学習(KL距離)と構造学習(正確な回復)の両問題を考察する。
最初のアプローチはChow-Liuアルゴリズムに基づいており、最適な木構造分布を効率的に学習する。
第2のアプローチは、制約に基づく構造学習のための条件付き独立試験器として部分相関を用いたポリツリーに対するPCアルゴリズムの修正である。
論文 参考訳（メタデータ） (2024-02-09T12:58:36Z) - Sample-and-Bound for Non-Convex Optimization [18.30858789210194]
我々はモンテカルロのベンチマークに適応して効率を向上する非次元目的最適化のための新しいサンプリング手法を提案する。
提案する高次ベースラインおよび競合ベンチマークアルゴリズムを積極的に評価する。
論文 参考訳（メタデータ） (2024-01-09T20:45:47Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - EM's Convergence in Gaussian Latent Tree Models [22.987933817370305]
人口のログライクな独特な非自明な点は、その大域的な最大点であることを示す。
予測最大化アルゴリズムは、単一の潜在変数の場合に収束することが保証される。
論文 参考訳（メタデータ） (2022-11-21T23:12:58Z) - Discrete Tree Flows via Tree-Structured Permutations [5.929956715430168]
離散フローベースモデルは、離散関数の勾配が未定義あるいはゼロであるため、従来のディープラーニング手法では直接最適化できない。
提案手法は,決定木に基づく離散フローを開発することにより,計算負担を低減し,擬似勾配の必要性を解消することを目的としている。
論文 参考訳（メタデータ） (2022-07-04T23:11:04Z) - Tree ensemble kernels for Bayesian optimization with known constraints
over mixed-feature spaces [54.58348769621782]
木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。
ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。
我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
論文 参考訳（メタデータ） (2022-07-02T16:59:37Z) - CITS: Coherent Ising Tree Search Algorithm Towards Solving Combinatorial
Optimization Problems [0.0]
本稿では、マルコフ連鎖からSAに基づく奥行き制限木への探索空間の拡大による探索アルゴリズムを提案する。
それぞれのイテレーションにおいて、このアルゴリズムは、先を見据えて、木に沿って探索することで、実現可能な探索空間内で最高の準最適解を選択する」。
以上の結果から,IsingのNP最適化問題に対する高次木探索戦略は,より少ないエポックの範囲で解決可能であることが示唆された。
論文 参考訳（メタデータ） (2022-03-09T10:07:26Z) - Gradient Boosted Binary Histogram Ensemble for Large-scale Regression [60.16351608335641]
本研究では,2値ヒストグラム分割とアンサンブル学習に基づくテキストグラディエント2値ヒストグラムアンサンブル(GBBHE)と呼ばれる大規模回帰問題に対する勾配向上アルゴリズムを提案する。
実験では, 勾配向上回帰木 (GBRT) などの他の最先端アルゴリズムと比較して, GBBHEアルゴリズムは大規模データセット上での実行時間が少なく, 有望な性能を示す。
論文 参考訳（メタデータ） (2021-06-03T17:05:40Z) - Improved Branch and Bound for Neural Network Verification via Lagrangian
Decomposition [161.09660864941603]
ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。
活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。
BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
論文 参考訳（メタデータ） (2021-04-14T09:22:42Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳（メタデータ） (2020-07-24T17:06:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。