論文の概要: Active Cost-aware Labeling of Streaming Data
- arxiv url: http://arxiv.org/abs/2304.06808v2
- Date: Tue, 4 Jul 2023 22:09:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-06 22:38:57.858083
- Title: Active Cost-aware Labeling of Streaming Data
- Title(参考訳): ストリーミングデータのアクティブコストアウェアラベリング
- Authors: Ting Cai, Kirthevasan Kandasamy
- Abstract要約: 本研究では,アクティブな学習者がデータポイントのストリームに直面するストリーミングデータのラベル付けについて検討する。
まず、データ入力が$K$の離散分布の1つに属し、ラベリングコストと予測誤差をキャプチャする損失によってこの問題を定式化する際の設定について検討する。
ラベル付けコストが$B$の場合、不確実性が時間とコスト依存しきい値よりも大きい場合のラベル付けを選択するアルゴリズムは、最悪の$widetildeO(Bfrac1)上限を達成する。
- 参考スコア(独自算出の注目度): 11.501619634838312
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study actively labeling streaming data, where an active learner is faced
with a stream of data points and must carefully choose which of these points to
label via an expensive experiment. Such problems frequently arise in
applications such as healthcare and astronomy. We first study a setting when
the data's inputs belong to one of $K$ discrete distributions and formalize
this problem via a loss that captures the labeling cost and the prediction
error. When the labeling cost is $B$, our algorithm, which chooses to label a
point if the uncertainty is larger than a time and cost dependent threshold,
achieves a worst-case upper bound of $\widetilde{O}(B^{\frac{1}{3}}
K^{\frac{1}{3}} T^{\frac{2}{3}})$ on the loss after $T$ rounds. We also provide
a more nuanced upper bound which demonstrates that the algorithm can adapt to
the arrival pattern, and achieves better performance when the arrival pattern
is more favorable. We complement both upper bounds with matching lower bounds.
We next study this problem when the inputs belong to a continuous domain and
the output of the experiment is a smooth function with bounded RKHS norm. After
$T$ rounds in $d$ dimensions, we show that the loss is bounded by
$\widetilde{O}(B^{\frac{1}{d+3}} T^{\frac{d+2}{d+3}})$ in an RKHS with a
squared exponential kernel and by $\widetilde{O}(B^{\frac{1}{2d+3}}
T^{\frac{2d+2}{2d+3}})$ in an RKHS with a Mat\'ern kernel. Our empirical
evaluation demonstrates that our method outperforms other baselines in several
synthetic experiments and two real experiments in medicine and astronomy.
- Abstract(参考訳): アクティブな学習者がデータポイントのストリームに直面するストリーミングデータのラベル付けを積極的に研究し、高価な実験によってラベル付けするポイントを慎重に選択する必要がある。
このような問題は医療や天文学などの応用でしばしば発生する。
最初に、データの入力が$k$離散分布の1つに属する場合の設定を研究し、ラベリングコストと予測エラーをキャプチャするロスによってこの問題を形式化する。
ラベル付けコストが$B$の場合、我々のアルゴリズムは、不確実性が時間とコスト依存しきい値よりも大きい場合の値にラベルを付けることを選択し、$T$ラウンド後の損失に対して$\widetilde{O}(B^{\frac{1}{3}} K^{\frac{1}{3}} T^{\frac{2}{3}})$の最悪の上限を達成する。
また、よりニュアンスの高い上界を提供し、アルゴリズムが到着パターンに適応できることを示し、到着パターンがより有利な場合により良い性能を実現する。
両方の上界と一致する下界を補完する。
次に、入力が連続領域に属し、実験の出力が有界なRKHSノルムを持つ滑らかな関数である場合、この問題を研究する。
$d$次元での$T$のラウンドの後、損失は$\widetilde{O}(B^{\frac{1}{d+3}} T^{\frac{d+2}{d+3}})$と$\widetilde{O}(B^{\frac{1}{2d+3}} T^{\frac{2d+3}})$とMt\ernカーネルを持つRKHSで束縛されていることを示す。
本手法は,いくつかの合成実験および医学および天文学における2つの実実験において,他のベースラインよりも優れることを示す。
関連論文リスト
- Towards the Fundamental Limits of Knowledge Transfer over Finite Domains [8.575522204707957]
3つの段階の特権情報によって転送が促進されることを示す。
第一段階では、ハードラベルを持つサンプルのみが知られており、最大極大推定器はミニマックスレート$sqrt|mathcal Smathcal A|/n$に達する。
第3のレベルはさらに、サンプル入力毎に$mathcal A$のソフトラベル(完全ロジット)を学生に提供するので、学生は$|mathcal S|/n$ free of $を楽しむことができる。
論文 参考訳(メタデータ) (2023-10-11T19:30:08Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳(メタデータ) (2023-05-15T05:37:32Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳(メタデータ) (2022-05-23T17:59:18Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳(メタデータ) (2021-10-25T02:53:24Z) - Coresets for Classification -- Simplified and Strengthened [19.54307474041768]
損失関数の幅広いクラスを持つ線形分類器を訓練するための相対誤差コアセットを与える。
我々の構成は $tilde O(d cdot mu_y(X)2/epsilon2)$point, where $mu_y(X)$ は mathbbRn times d$ のデータ行列 $X と -1,1n$ のラベルベクトル $y の自然な複雑性測度である。
論文 参考訳(メタデータ) (2021-06-08T11:24:18Z) - Provable Robustness of Adversarial Training for Learning Halfspaces with
Noise [95.84614821570283]
ラベル雑音の存在下での敵対的ロバストなハーフスペースの特性を分析する。
我々の知る限りでは、これは敵の訓練がノイズの分類子を与えることを示す最初の研究である。
論文 参考訳(メタデータ) (2021-04-19T16:35:38Z) - Provably Breaking the Quadratic Error Compounding Barrier in Imitation
Learning, Optimally [58.463668865380946]
状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。
rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。
Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
論文 参考訳(メタデータ) (2021-02-25T15:50:19Z) - Online Robust Regression via SGD on the l1 loss [19.087335681007477]
ストリーミング方式でデータにアクセス可能なオンライン環境において、ロバストな線形回帰問題を考察する。
この研究で、$ell_O( 1 / (1 - eta)2 n )$損失の降下は、汚染された測定値に依存しない$tildeO( 1 / (1 - eta)2 n )$レートで真のパラメータベクトルに収束することを示した。
論文 参考訳(メタデータ) (2020-07-01T11:38:21Z) - Rates of Convergence for Laplacian Semi-Supervised Learning with Low
Labeling Rates [3.867363075280544]
グラフに基づくラプラシアン半教師付き学習を低ラベリングレートで研究する。
ラベルレートが非常に低い場合、ラプラシアン学習は縮退し、その解はラベル付き各データポイントのスパイクとほぼ一定となる。
論文 参考訳(メタデータ) (2020-06-04T10:46:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。