論文の概要: On Efficient Low Distortion Ultrametric Embedding
- arxiv url: http://arxiv.org/abs/2008.06700v1
- Date: Sat, 15 Aug 2020 11:06:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-28 21:16:26.891204
- Title: On Efficient Low Distortion Ultrametric Embedding
- Title（参考訳）: 効率的低歪み超計量埋め込みについて
- Authors: Vincent Cohen-Addad, Karthik C. S., and Guillaume Lagarde
- Abstract要約: データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
- 参考スコア（独自算出の注目度）: 18.227854382422112
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A classic problem in unsupervised learning and data analysis is to find
simpler and easy-to-visualize representations of the data that preserve its
essential properties. A widely-used method to preserve the underlying
hierarchical structure of the data while reducing its complexity is to find an
embedding of the data into a tree or an ultrametric. The most popular
algorithms for this task are the classic linkage algorithms (single, average,
or complete). However, these methods on a data set of $n$ points in
$\Omega(\log n)$ dimensions exhibit a quite prohibitive running time of
$\Theta(n^2)$.
In this paper, we provide a new algorithm which takes as input a set of
points $P$ in $\mathbb{R}^d$, and for every $c\ge 1$, runs in time
$n^{1+\frac{\rho}{c^2}}$ (for some universal constant $\rho>1$) to output an
ultrametric $\Delta$ such that for any two points $u,v$ in $P$, we have
$\Delta(u,v)$ is within a multiplicative factor of $5c$ to the distance between
$u$ and $v$ in the "best" ultrametric representation of $P$. Here, the best
ultrametric is the ultrametric $\tilde\Delta$ that minimizes the maximum
distance distortion with respect to the $\ell_2$ distance, namely that
minimizes $\underset{u,v \in P}{\max}\ \frac{\tilde\Delta(u,v)}{\|u-v\|_2}$.
We complement the above result by showing that under popular complexity
theoretic assumptions, for every constant $\varepsilon>0$, no algorithm with
running time $n^{2-\varepsilon}$ can distinguish between inputs in
$\ell_\infty$-metric that admit isometric embedding and those that incur a
distortion of $\frac{3}{2}$.
Finally, we present empirical evaluation on classic machine learning datasets
and show that the output of our algorithm is comparable to the output of the
linkage algorithms while achieving a much faster running time.
- Abstract（参考訳）: 教師なし学習とデータ分析の古典的な問題は、その本質的な性質を保存するデータの表現をシンプルで簡単に視覚化できることである。
データの基盤となる階層構造を保存し、その複雑さを減らし、広く使われている方法は、データの木への埋め込みを見つけることである。
このタスクの最も一般的なアルゴリズムは、古典的なリンクアルゴリズム(シングル、平均、または完全)である。
しかしながら、$\omega(\log n)$次元のデータセット上のこれらのメソッドは、$\theta(n^2)$という非常に禁止的な実行時間を示す。
本稿では,$\mathbb{r}^d$ の点のセットを入力とし,$c\ge 1$ ごとに $n^{1+\frac{\rho}{c^2}}$ (ある普遍定数 $\rho>1$) を入力して超メトリック $\delta$ を出力し,任意の 2 点 $u,v$ in $p$ に対して$\delta(u,v)$ を$c$ から$v$ までの乗算係数に設定するアルゴリズムを提案する。
ここで、最高の超測度は、$\ell_2$距離に関する最大距離歪みを最小限に抑えるウルトラメトリック $\tilde\Delta$、すなわち$\underset{u,v \in P}{\max}\ \frac{\tilde\Delta(u,v)}{\|u-v\|_2}$である。
上記の結果を補うために、一般的な複雑性理論の仮定の下で、すべての定数 $\varepsilon>0$ に対して、実行時間 $n^{2-\varepsilon}$ を持つアルゴリズムは、等尺埋め込みを許容する$\ell_\infty$-metric の入力と $\frac{3}{2}$ の歪みを生じさせるものとを区別できないことを示す。
最後に,従来の機械学習データセットに対する経験的評価を行い,アルゴリズムの出力がリンクアルゴリズムの出力に匹敵し,より高速な実行時間を実現していることを示す。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and
Minimizing the Maximum of Smooth Functions [44.655316553524855]
我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。
それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
論文 参考訳（メタデータ） (2023-11-17T22:07:18Z) - Online Robust Mean Estimation [37.746091744197656]
オンライン環境における高次元ロバスト平均推定問題について検討する。
このモデルでは、オンラインロバスト平均推定の主な2つの結果が証明されている。
論文 参考訳（メタデータ） (2023-10-24T15:28:43Z) - Dynamic algorithms for k-center on graphs [3.568439282784197]
エッジ更新を行う動的グラフ上での$k$-center問題に対する最初の効率的なアルゴリズムを提供する。
完全に動的な$(2+epsilon)$-approximationアルゴリズムを$k$-center問題に対して提案する。
論文 参考訳（メタデータ） (2023-07-28T13:50:57Z) - A faster and simpler algorithm for learning shallow networks [10.595936992218856]
ラベル付き例から、$k$ReLUアクティベーションの線形結合を学習する、よく研究された問題を再考する。
ここでは、アルゴリズムのよりシンプルなワンステージバージョンが十分であることを示し、そのランタイムは、わずか$(d/varepsilon)O(k2)$である。
論文 参考訳（メタデータ） (2023-07-24T03:04:10Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。
重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-02T05:26:10Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。