論文の概要: Maintaining AUC and $H$-measure over time
- arxiv url: http://arxiv.org/abs/2112.06160v1
- Date: Sun, 12 Dec 2021 06:07:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-15 13:57:34.820611
- Title: Maintaining AUC and $H$-measure over time
- Title（参考訳）: AUC と $H$-measure を経時的に維持する
- Authors: Nikolaj Tatti
- Abstract要約: 本稿では,2つの尺度を維持するための3つのアルゴリズムについて検討する。
最初のアルゴリズムは、データポイントを$O(log n)$ timeで削除し、加えてROC曲線(AUC)の下の領域を維持する。
第二のアルゴリズムは、ROC曲線に基づく代替測度である$H$-measureを維持している。
- 参考スコア（独自算出の注目度）: 1.9188864062289428
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Measuring the performance of a classifier is a vital task in machine
learning. The running time of an algorithm that computes the measure plays a
very small role in an offline setting, for example, when the classifier is
being developed by a researcher. However, the running time becomes more crucial
if our goal is to monitor the performance of a classifier over time.
In this paper we study three algorithms for maintaining two measures. The
first algorithm maintains area under the ROC curve (AUC) under addition and
deletion of data points in $O(\log n)$ time. This is done by maintaining the
data points sorted in a self-balanced search tree. In addition, we augment the
search tree that allows us to query the ROC coordinates of a data point in
$O(\log n)$ time. In doing so we are able to maintain AUC in $O(\log n)$ time.
Our next two algorithms involve in maintaining $H$-measure, an alternative
measure based on the ROC curve. Computing the measure is a two-step process:
first we need to compute a convex hull of the ROC curve, followed by a sum over
the convex hull. We demonstrate that we can maintain the convex hull using a
minor modification of the classic convex hull maintenance algorithm. We then
show that under certain conditions, we can compute the $H$-measure exactly in
$O(\log^2 n)$ time, and if the conditions are not met, then we can estimate the
$H$-measure in $O((\log n + \epsilon^{-1})\log n)$ time. We show empirically
that our methods are significantly faster than the baselines.
- Abstract（参考訳）: 分類器のパフォーマンスを測定することは、機械学習において重要なタスクである。
測度を計算するアルゴリズムの実行時間は、例えば研究者によって分類器が開発されている場合、オフライン設定において非常に小さな役割を果たす。
しかし、時間とともに分類器のパフォーマンスを監視することが目的であれば、実行時間がより重要になります。
本稿では,2つの尺度を維持するための3つのアルゴリズムについて検討する。
最初のアルゴリズムは、データポイントを$O(\log n)$ timeで削除し、加えてROC曲線(AUC)の下で面積を維持する。
これは、セルフバランスの検索ツリーにソートされたデータポイントを維持することで行われる。
さらに、データポイントのROC座標を$O(\log n)$ timeでクエリできる検索ツリーも強化します。
そうすることで、AUCを$O(\log n)$ timeで維持できます。
次の2つのアルゴリズムは、ROC曲線に基づく代替測度である$H$-measureを維持することである。
測度を計算することは2段階のプロセスであり、まずはROC曲線の凸殻を計算し、次に凸殻の和を計算する必要がある。
我々は,古典的凸船体維持アルゴリズムを微修正して,凸船体を維持できることを実証した。
すると、ある条件下では、$H$- measureを$O(\log^2 n)$ timeで正確に計算でき、条件が満たされていない場合、$O((\log n + \epsilon^{-1})\log n)$ timeで$H$-measureを推定できる。
我々は,本手法がベースラインよりもはるかに高速であることを示す。
関連論文リスト
- Mini-Batch Kernel $k$-means [4.604003661048267]
私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。
実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
論文 参考訳（メタデータ） (2024-10-08T10:59:14Z) - Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means [4.271492285528115]
Euclidean $k$-medianと$k$-meansの問題、クラスタリングのタスクをモデル化する標準的な2つの方法に注目します。
本稿では,定数係数近似を計算するためのほぼ線形時間アルゴリズムを提案することにより,この問題にほぼ答える。
論文 参考訳（メタデータ） (2024-07-15T20:04:06Z) - A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。
我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文 参考訳（メタデータ） (2024-03-07T18:23:51Z) - 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) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。
階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。
提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
論文 参考訳（メタデータ） (2021-06-10T09:29:05Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。