論文の概要: Online AUC Optimization for Sparse High-Dimensional Datasets

• arxiv url: http://arxiv.org/abs/2009.10867v1
• Date: Wed, 23 Sep 2020 00:50:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-15 15:08:31.177297
• Title: Online AUC Optimization for Sparse High-Dimensional Datasets
• Title（参考訳）: スパース高次元データセットのオンラインAUC最適化
• Authors: Baojian Zhou, Yiming Ying, Steven Skiena
• Abstract要約: エリア・アンダー・オブ・ザ・ROC曲線(AUC)は、不均衡な分類のための広く使われている性能指標である。 現在のオンラインAUC最適化アルゴリズムは、イテレーションあたりのコストが$mathcalO(d)$である。 本稿では,新しいアルゴリズムである textscFTRL-AUC を提案する。
• 参考スコア（独自算出の注目度）: 32.77252579365118
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Area Under the ROC Curve (AUC) is a widely used performance measure for imbalanced classification arising from many application domains where high-dimensional sparse data is abundant. In such cases, each $d$ dimensional sample has only $k$ non-zero features with $k \ll d$, and data arrives sequentially in a streaming form. Current online AUC optimization algorithms have high per-iteration cost $\mathcal{O}(d)$ and usually produce non-sparse solutions in general, and hence are not suitable for handling the data challenge mentioned above. In this paper, we aim to directly optimize the AUC score for high-dimensional sparse datasets under online learning setting and propose a new algorithm, \textsc{FTRL-AUC}. Our proposed algorithm can process data in an online fashion with a much cheaper per-iteration cost $\mathcal{O}(k)$, making it amenable for high-dimensional sparse streaming data analysis. Our new algorithmic design critically depends on a novel reformulation of the U-statistics AUC objective function as the empirical saddle point reformulation, and the innovative introduction of the "lazy update" rule so that the per-iteration complexity is dramatically reduced from $\mathcal{O}(d)$ to $\mathcal{O}(k)$. Furthermore, \textsc{FTRL-AUC} can inherently capture sparsity more effectively by applying a generalized Follow-The-Regularized-Leader (FTRL) framework. Experiments on real-world datasets demonstrate that \textsc{FTRL-AUC} significantly improves both run time and model sparsity while achieving competitive AUC scores compared with the state-of-the-art methods. Comparison with the online learning method for logistic loss demonstrates that \textsc{FTRL-AUC} achieves higher AUC scores especially when datasets are imbalanced.
• Abstract（参考訳）: ROC曲線下の領域(AUC)は、高次元スパースデータが豊富に存在する多くのアプリケーションドメインから生じる不均衡な分類のための広く使われている性能指標である。 そのような場合、各$d$ 次元のサンプルは、$k \ll d$ で 0 でない機能しか持たず、データはストリーミング形式で順次到着する。 現在のオンラインAUC最適化アルゴリズムは、高コストの$\mathcal{O}(d)$で、一般に非スパース解を生成するため、上記のデータチャレンジを扱うには適していない。 本稿では,オンライン学習環境下での高次元スパースデータセットのAUCスコアを直接最適化し,新しいアルゴリズムである「textsc{FTRL-AUC}」を提案する。 提案手法は,より安価な1文あたり$\mathcal{o}(k)$でオンライン形式でデータを処理でき,高次元のスパースストリーミングデータ解析に適している。 我々の新しいアルゴリズム設計は、経験的サドル点再構成としてのU-統計 AUC の目的関数の新たな再構成と、「遅延更新」規則の革新的導入に大きく依存し、各項目の複雑性が$\mathcal{O}(d)$から$\mathcal{O}(k)$に劇的に減少する。 さらに、一般化されたFollow-The-Regularized-Leader (FTRL) フレームワークを適用することで、より効果的に空間をキャプチャできる。 実世界のデータセットの実験では、‘textsc{FTRL-AUC} は実行時間とモデル間隔の両方を著しく改善し、最先端の手法と比較して競合的なAUCスコアを達成する。 対ロジスティック損失のオンライン学習法との比較により,データセットが不均衡な場合, \textsc{FTRL-AUC} がより高い AUC スコアを達成することが示された。

関連論文リスト

• DRAUC: An Instance-wise Distributionally Robust AUC Optimization Framework [133.26230331320963]
  ROC曲線のエリア(AUC)は、長い尾の分類のシナリオにおいて広く用いられている指標である。 本研究では,分散ロバストAUC(DRAUC)のインスタンスワイドサロゲート損失を提案し,その上に最適化フレームワークを構築した。
  論文  参考訳（メタデータ） (2023-11-06T12:15:57Z)
• Does it pay to optimize AUC? [17.54773029913898]
  本稿では,より効率的なアルゴリズムであるAUC-optを提案し,$mathbbR2$で証明可能な最適なAUC線形分類器を求める。 実験によると、AUC-optは、$mathbbR2$で17から40、$mathbbR3$50 t-SNEトレーニングデータセットで4から42に大幅に改善されている。
  論文  参考訳（メタデータ） (2023-06-02T13:28:53Z)
• AUC Optimization from Multiple Unlabeled Datasets [14.318887072787938]
  U$m$-AUCは、U$m$データを多ラベルAUC最適化問題に変換するAUC最適化手法である。 提案したU$m$-AUCは理論的および実験的に有効であることを示す。
  論文  参考訳（メタデータ） (2023-05-25T06:43:42Z)
• Provably Efficient Neural Offline Reinforcement Learning via Perturbed Rewards [33.88533898709351]
  VIPeRは、ランダム化された値関数のアイデアと悲観主義の原理を一致させる。 オフラインデータを複数回摂動することで、暗黙的に悲観性を得る。 ニューラルネットワーク関数近似を用いた一般的なマルコフ決定過程(MDP)において、証明可能かつ計算的に効率的である。
  論文  参考訳（メタデータ） (2023-02-24T17:52:12Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。 最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。 提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
  論文  参考訳（メタデータ） (2022-06-14T08:14:14Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。 近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。 提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
  論文  参考訳（メタデータ） (2022-03-03T03:46:18Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Stochastic Hard Thresholding Algorithms for AUC Maximization [49.00683387735522]
  分散分類におけるAUCのためのハードしきい値決定アルゴリズムを開発した。 提案アルゴリズムの有効性と有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-04T16:49:29Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)

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

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