Fugu-MT 論文翻訳(概要): Sets Clustering

論文の概要: Sets Clustering

arxiv url: http://arxiv.org/abs/2003.04135v1
Date: Mon, 9 Mar 2020 13:30:30 GMT
ステータス: 処理完了
システム内更新日: 2022-12-25 08:07:20.352874
Title: Sets Clustering
Title（参考訳）: setクラスタリング
Authors: Ibrahim Jubran and Murad Tukan and Alaa Maalouf and Dan Feldman
Abstract要約: 我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。オープンソースコードと文書分類および施設位置の実験結果も提供される。
参考スコア（独自算出の注目度）: 25.358415142404752
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The input to the \emph{sets-$k$-means} problem is an integer $k\geq 1$ and a set $\mathcal{P}=\{P_1,\cdots,P_n\}$ of sets in $\mathbb{R}^d$. The goal is to compute a set $C$ of $k$ centers (points) in $\mathbb{R}^d$ that minimizes the sum $\sum_{P\in \mathcal{P}} \min_{p\in P, c\in C}\left\| p-c \right\|^2$ of squared distances to these sets. An \emph{$\varepsilon$-core-set} for this problem is a weighted subset of $\mathcal{P}$ that approximates this sum up to $1\pm\varepsilon$ factor, for \emph{every} set $C$ of $k$ centers in $\mathbb{R}^d$. We prove that such a core-set of $O(\log^2{n})$ sets always exists, and can be computed in $O(n\log{n})$ time, for every input $\mathcal{P}$ and every fixed $d,k\geq 1$ and $\varepsilon \in (0,1)$. The result easily generalized for any metric space, distances to the power of $z>0$, and M-estimators that handle outliers. Applying an inefficient but optimal algorithm on this coreset allows us to obtain the first PTAS ($1+\varepsilon$ approximation) for the sets-$k$-means problem that takes time near linear in $n$. This is the first result even for sets-mean on the plane ($k=1$, $d=2$). Open source code and experimental results for document classification and facility locations are also provided.
Abstract（参考訳）: emph{sets-$k$-means}問題への入力は整数 $k\geq 1$ であり、$\mathcal{p}=\{p_1,\cdots,p_n\}$ of set in $\mathbb{r}^d$ である。目標は、$\sum_{p\in \mathcal{p}} \min_{p\in p, c\in c}\left\| p-c \right\|^2$ of squared distances to these set である。この問題に対する \emph{$\varepsilon$-core-set} は$\mathcal{P}$ の重み付き部分集合であり、$\mathbb{R}^d$ における$k$の集合に対して$1\pm\varepsilon$ factor に近似する。このような $o(\log^2{n})$ のコア集合は常に存在し、すべての入力 $\mathcal{p}$ と固定 $d,k\geq 1$ と $\varepsilon \in (0,1)$ に対して $o(n\log{n})$ time で計算できる。結果は、任意の距離空間、$z>0$ のパワーへの距離、および外れ値を扱う M-推定器に対して容易に一般化される。このコアセットに非効率だが最適なアルゴリズムを適用することで、n$で線形に近い時間を要する集合-k$-平均問題に対する最初のptas ($1+\varepsilon$ approximation) が得られる。これは平面上の集合平均 (k=1$, $d=2$) に対しても最初の結果である。オープンソースコードと文書分類および施設位置の実験結果も提供される。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文参考訳（メタデータ） (2024-10-07T19:47:13Z)
Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文参考訳（メタデータ） (2024-06-07T08:26:31Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Bicriteria Approximation Algorithms for Priority Matroid Median [1.7188280334580193]
我々は、プライオリティを$k$-Median問題に一般化する、プライオリティ・マトロイド・メディア問題を考える。目標は、mathcalF ff_iの$sum_iを最小化するために、サブセット$S subseteq MathcalF$を選択することである。
論文参考訳（メタデータ） (2022-10-04T20:19:55Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文参考訳（メタデータ） (2022-02-10T16:10:41Z)
Fair Representation Clustering with Several Protected Classes [13.53362222844008]
我々は、各クラスタが異なるグループから個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。我々は、$O(log k)$-approximationアルゴリズムを示し、$nO(ell)$で実行します。
論文参考訳（メタデータ） (2022-02-03T03:45:45Z)
Approximate Maximum Halfspace Discrepancy [6.35821487778241]
範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
論文参考訳（メタデータ） (2021-06-25T19:14:45Z)
FPT Approximation for Socially Fair Clustering [0.38073142980733]
距離関数 $d(.,.)$ を持つ距離空間 $mathcalX$ において点の集合 $P$ が与えられる。社会的に公正な$k$-median問題の目標は、すべてのグループに対する最大平均コストを最小限に抑える、セットの$CサブセットF$ of $k$センターを見つけることである。本研究では、社会的に公正な$k$-medianと$k$-meansに対する$(5+varepsilon)$と$(33+varepsilon)$近似アルゴリズムを設計する。
論文参考訳（メタデータ） (2021-06-12T11:53:18Z)
Optimal Coreset for Gaussian Kernel Density Estimation [0.8376091455761259]
点集合 $Psubset mathbbRd$ が与えられたとき、$P$ の核密度推定は [ overlinemathcalG_P(x) = frac1left|Pright|sum_pin Pe-leftlVert x-p rightrVert2 ] for any $xinmathbbRd$ と定義される。我々は、小さなサブセット$Q$ of $P を構築する方法を研究する。
論文参考訳（メタデータ） (2020-07-15T22:58:50Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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