論文の概要: Adaptive Data Depth via Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2211.03985v1
- Date: Tue, 8 Nov 2022 03:44:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-09 17:14:17.264221
- Title: Adaptive Data Depth via Multi-Armed Bandits
- Title（参考訳）: マルチアーマッドバンドによる適応データ深さ
- Authors: Tavor Z. Baharav, Tze Leung Lai
- Abstract要約: 我々は適応的なデータ深度に対するインスタンス適応アルゴリズムを開発した。
我々は,水深の有望な概念として出現した citetliu 1990notion によって開発されたsimplicial depth に注目した。
我々は、$O(nd)$から$tildeO(nd-(d-1)alpha/2)$に設定したデータセットの最も深い点を特定する複雑さを減らすことができることを示した。
- 参考スコア（独自算出の注目度）: 6.29475963948119
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Data depth, introduced by Tukey (1975), is an important tool in data science,
robust statistics, and computational geometry. One chief barrier to its broader
practical utility is that many common measures of depth are computationally
intensive, requiring on the order of $n^d$ operations to exactly compute the
depth of a single point within a data set of $n$ points in $d$-dimensional
space. Often however, we are not directly interested in the absolute depths of
the points, but rather in their \textit{relative ordering}. For example, we may
want to find the most central point in a data set (a generalized median), or to
identify and remove all outliers (points on the fringe of the data set with low
depth). With this observation, we develop a novel and instance-adaptive
algorithm for adaptive data depth computation by reducing the problem of
exactly computing $n$ depths to an $n$-armed stochastic multi-armed bandit
problem which we can efficiently solve. We focus our exposition on simplicial
depth, developed by \citet{liu1990notion}, which has emerged as a promising
notion of depth due to its interpretability and asymptotic properties. We
provide general instance-dependent theoretical guarantees for our proposed
algorithms, which readily extend to many other common measures of data depth
including majority depth, Oja depth, and likelihood depth. When specialized to
the case where the gaps in the data follow a power law distribution with
parameter $\alpha<2$, we show that we can reduce the complexity of identifying
the deepest point in the data set (the simplicial median) from $O(n^d)$ to
$\tilde{O}(n^{d-(d-1)\alpha/2})$, where $\tilde{O}$ suppresses logarithmic
factors. We corroborate our theoretical results with numerical experiments on
synthetic data, showing the practical utility of our proposed methods.
- Abstract（参考訳）: tukey (1975) によって導入されたデータ深さは、データサイエンス、ロバスト統計学、計算幾何学において重要なツールである。
より広範な実用性に対する大きな障壁は、深度に関する多くの一般的な測度が計算集約的であり、$d$次元空間における$n$点のデータセット内の単一の点の深さを正確に計算するために$n^d$演算の順序に依存することである。
しかし、多くの場合、点の絶対的な深さに直接関心はなく、むしろそれらの \textit{relative order} に関心を持つ。
例えば、データセットの最も中央にある点(一般的な中央値)を見つけたり、すべての外れ値(低い深さのデータセットのフリンジ上の点)を識別して削除したりしたいかもしれません。
そこで本研究では,$n$deepsを$n$の確率的マルチアームバンディット問題に正確に計算することで,適応的なデータ深度計算のための新しい,インスタンス適応型アルゴリズムを開発した。
我々は,その解釈可能性や漸近的性質から,深度を期待できる概念として現われてきた \citet{liu 1990notion} によって開発されたsimplicial depth に焦点をあてる。
提案手法では,大域的深さ,oja深さ,ラピッド深さなど,データ深さの他の多くの一般的な尺度に容易に拡張できる。
データ内のギャップがパラメータ$\alpha<2$のパワーロー分布に従う場合に特化した場合、データセットの最も深い点(単純な中央値)を特定する複雑さを、$o(n^d)$から$\tilde{o}(n^{d-(d-1)\alpha/2})$に削減できることを示し、ここで$\tilde{o}$は対数因子を抑制する。
提案手法の実用性を示すため, 合成データに関する数値実験により理論的結果を相関させる。
関連論文リスト
- Private Geometric Median [10.359525525715421]
データセットの幾何中央値(GM)を計算するための差分プライベート(DP)アルゴリズムについて検討する。
我々の主な貢献は、データポイントの有効直径でスケールする過剰なエラー保証を備えたプライベートGMのタスクのためのDPアルゴリズムのペアである。
論文 参考訳（メタデータ） (2024-06-11T16:13:09Z) - Bayesian Inference with Deep Weakly Nonlinear Networks [57.95116787699412]
我々は,完全連結ニューラルネットワークによるベイズ推定が解けることを示す物理レベルの厳密さを示す。
我々はモデルエビデンスを計算し、任意の温度で1/N$で任意の順序に後続する手法を提供する。
論文 参考訳（メタデータ） (2024-05-26T17:08:04Z) - Fast kernel half-space depth for data with non-convex supports [5.725360029813277]
我々は、分布の多モード性に取り組むために、祝福された半空間深さを延長する。
提案した深さは、半空間の深さよりも数桁高速な多様体勾配を用いて計算することができる。
数値シミュレーションや, 実データにおける異常検出, 均一性試験などの応用により, 深度特性を実証した。
論文 参考訳（メタデータ） (2023-12-21T18:55:22Z) - On the quality of randomized approximations of Tukey's depth [0.0]
タキー深度は多変量データの集中度を広く測定する尺度である。
タキーの深さの正確な近似を高次元で計算することは困難である。
ランダム化アルゴリズムは最大深さ1/2$と0に近い深さを正確に近似することを示した。
論文 参考訳（メタデータ） (2023-09-11T17:52:28Z) - Effective Minkowski Dimension of Deep Nonparametric Regression: Function
Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。
本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文 参考訳（メタデータ） (2023-06-26T17:13:31Z) - 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) - Eikonal depth: an optimal control approach to statistical depths [0.7614628596146599]
本稿では,制御理論と固有方程式に基づく,グローバルに定義された新しいタイプの統計深度を提案する。
この深さは解釈や計算が容易で、マルチモーダルな振る舞いを表現的に捉え、非ユークリッド的なデータに自然に拡張する。
論文 参考訳（メタデータ） (2022-01-14T01:57:48Z) - Depth Completion using Plane-Residual Representation [84.63079529738924]
深度情報を最も近い深度平面ラベル$p$と残値$r$で解釈する新しい方法を紹介し,これをPlane-Residual (PR)表現と呼ぶ。
PR表現で深度情報を解釈し,それに対応する深度補完網を用いて,高速な計算により深度補完性能を向上させることができた。
論文 参考訳（メタデータ） (2021-04-15T10:17:53Z) - Efficient Depth Completion Using Learned Bases [94.0808155168311]
深度補正のための新しい大域的幾何制約を提案する。
低次元部分空間上によく配置される深さ写像を仮定することにより、高密度深度写像は全解像度の主深度基底の重み付け和で近似することができる。
論文 参考訳（メタデータ） (2020-12-02T11:57:37Z) - Balanced Depth Completion between Dense Depth Inference and Sparse Range
Measurements via KISS-GP [14.158132769768578]
密集した正確な深度マップを推定することは、自動運転とロボット工学にとって重要な要件である。
近年のディープラーニングの進歩により、単一の画像から全解像度での深度推定が可能になった。
この驚くべき結果にもかかわらず、多くのディープラーニングベースの単眼深度推定アルゴリズムは、その精度をメーターレベルの推定誤差に保たない。
論文 参考訳（メタデータ） (2020-08-12T08:07:55Z) - Single Image Depth Estimation Trained via Depth from Defocus Cues [105.67073923825842]
単一のRGB画像から深度を推定することはコンピュータビジョンの基本的な課題である。
この作業では、異なる視点ではなく、フォーカスキューからの奥行きに依存しています。
我々は,KITTIとMake3Dデータセットの教師あり手法と同等な結果を提示し,教師なし学習手法より優れていることを示す。
論文 参考訳（メタデータ） (2020-01-14T20:22:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。