論文の概要: Almost Tight Approximation Algorithms for Explainable Clustering
- arxiv url: http://arxiv.org/abs/2107.00774v1
- Date: Thu, 1 Jul 2021 23:49:23 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-05 12:43:51.678339
- Title: Almost Tight Approximation Algorithms for Explainable Clustering
- Title（参考訳）: 説明可能なクラスタリングのための近似近似アルゴリズム
- Authors: Hossein Esfandiari, Vahab Mirrokni, Shyam Narayanan
- Abstract要約: 本稿では,Dasguptaらによって提案された最近の説明可能なクラスタリングの枠組みについて考察する。
具体的には、$k$-meansと$k$-mediansの問題に焦点をあて、ほぼ上と下の境界を提供する。
- 参考スコア（独自算出の注目度）: 16.22135057266913
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, due to an increasing interest for transparency in artificial
intelligence, several methods of explainable machine learning have been
developed with the simultaneous goal of accuracy and interpretability by
humans. In this paper, we study a recent framework of explainable clustering
first suggested by Dasgupta et al.~\cite{dasgupta2020explainable}.
Specifically, we focus on the $k$-means and $k$-medians problems and provide
nearly tight upper and lower bounds.
First, we provide an $O(\log k \log \log k)$-approximation algorithm for
explainable $k$-medians, improving on the best known algorithm of
$O(k)$~\cite{dasgupta2020explainable} and nearly matching the known
$\Omega(\log k)$ lower bound~\cite{dasgupta2020explainable}. In addition, in
low-dimensional spaces $d \ll \log k$, we show that our algorithm also provides
an $O(d \log^2 d)$-approximate solution for explainable $k$-medians. This
improves over the best known bound of $O(d \log k)$ for low
dimensions~\cite{laber2021explainable}, and is a constant for constant
dimensional spaces. To complement this, we show a nearly matching $\Omega(d)$
lower bound. Next, we study the $k$-means problem in this context and provide
an $O(k \log k)$-approximation algorithm for explainable $k$-means, improving
over the $O(k^2)$ bound of Dasgupta et al. and the $O(d k \log k)$ bound of
\cite{laber2021explainable}. To complement this we provide an almost tight
$\Omega(k)$ lower bound, improving over the $\Omega(\log k)$ lower bound of
Dasgupta et al. All our algorithms run in near linear time in the number of
points and the dimension.
- Abstract（参考訳）: 近年、人工知能の透明性への関心が高まっているため、人間の正確性と解釈可能性を同時に目標とした説明可能な機械学習手法がいくつか開発されている。
本稿では,Dasgupta et al.~\cite{dasgupta2020explainable} が提案した最近のクラスタリングの枠組みについて述べる。
具体的には、$k$-meansと$k$-mediansの問題に焦点をあて、ほぼ上と下の境界を提供する。
まず、$O(\log k \log \log k)$-approximation algorithm for explainable $k$-medians, improve on the best known algorithm of $O(k)$~\cite{dasgupta2020explainable} and almost matching the known $Omega(\log k)$ lower bound~\cite{dasgupta2020explainable}。
さらに、低次元空間における $d \ll \log k$ において、このアルゴリズムは、説明可能な $k$-medians に対して $o(d \log^2 d)$-approximate solution を提供する。
これは、低次元~\cite{laber2021explainable} に対する$O(d \log k)$の最もよく知られた境界よりも改善され、定数次元空間に対する定数である。
これを補完するために、ほぼ一致する$\Omega(d)$lowboundを示す。
次に、この文脈で$k$-means問題を研究し、説明可能な$k$-meansに対する$o(k \log k)$近似アルゴリズムを提供し、dasgupta と al の$o(k^2)$バウンドよりも改善する。
and the $o(d k \log k)$ bound of \cite{laber2021explainable}。
これを補うために、ほぼ厳密な$\Omega(k)$low boundを提供し、$\Omega(\log k)$ lower bound of Dasgupta et al よりも改善する。
全てのアルゴリズムは、点数と次元においてほぼ線形時間で実行される。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - A Nearly Tight Analysis of Greedy k-means++ [1.452875650827562]
k$-means++アルゴリズムは期待して$Theta(log k)$近似解を返すことが知られている。
我々は、greedy $k$-means++アルゴリズムに対して、ほぼ一致する下界と上界を示す。
論文 参考訳（メタデータ） (2022-07-16T13:49:07Z) - Near-optimal Algorithms for Explainable k-Medians and k-Means [12.68470213641421]
Dasgupta, Frost, Moshkovitz, Rashtchian (ICML 2020) が導入した$k$-medians と $k$-means の問題を考える。
私たちのゴールは、データを$kクラスタに分割し、$k-mediansや$k-meansの目的を最小化する、最適な決定ツリーを見つけることです。
論文 参考訳（メタデータ） (2021-07-02T02:07:12Z) - Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。
k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。
我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-30T15:49:41Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Adapting $k$-means algorithms for outliers [1.9290392443571387]
我々は、$k$-means問題に対して、複数の単純なサンプリングベースのアルゴリズムを、外れ値を持つ設定に適応する方法を示す。
我々のアルゴリズムは、目的関数に対して$O(varepsilon)$-approximationを行いながら、$(varepsilon)z$outliersを出力する。
論文 参考訳（メタデータ） (2020-07-02T14:14:33Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。