論文の概要: Optimal Decision Tree with Noisy Outcomes

• arxiv url: http://arxiv.org/abs/2312.15357v1
• Date: Sat, 23 Dec 2023 21:47:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-27 18:28:18.991010
• Title: Optimal Decision Tree with Noisy Outcomes
• Title（参考訳）: 雑音出力を持つ最適決定木
• Authors: Su Jia, Fatemeh Navidi, Viswanath Nagarajan, R. Ravi
• Abstract要約: プールベースのアクティブラーニングでは、学習者にラベルのないデータセットが与えられ、データポイントのラベルをクエリすることで未知の仮説を効率的に学習することを目的としている。 これは古典的最適決定木(ODT)問題として定式化できる: テストのセット、仮説のセット、各テストと仮説に対する結果が与えられた場合、我々の目標は、真の仮説を識別する低コストなテスト手順(すなわち決定木)を見つけることである。 本研究では,ODT問題の基本的変種について検討し,実験結果がうるさい場合,さらに一般的な場合であっても検討する。
• 参考スコア（独自算出の注目度）: 10.183589332901839
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In pool-based active learning, the learner is given an unlabeled data set and aims to efficiently learn the unknown hypothesis by querying the labels of the data points. This can be formulated as the classical Optimal Decision Tree (ODT) problem: Given a set of tests, a set of hypotheses, and an outcome for each pair of test and hypothesis, our objective is to find a low-cost testing procedure (i.e., decision tree) that identifies the true hypothesis. This optimization problem has been extensively studied under the assumption that each test generates a deterministic outcome. However, in numerous applications, for example, clinical trials, the outcomes may be uncertain, which renders the ideas from the deterministic setting invalid. In this work, we study a fundamental variant of the ODT problem in which some test outcomes are noisy, even in the more general case where the noise is persistent, i.e., repeating a test gives the same noisy output. Our approximation algorithms provide guarantees that are nearly best possible and hold for the general case of a large number of noisy outcomes per test or per hypothesis where the performance degrades continuously with this number. We numerically evaluated our algorithms for identifying toxic chemicals and learning linear classifiers, and observed that our algorithms have costs very close to the information-theoretic minimum.
• Abstract（参考訳）: プールベースのアクティブラーニングでは、学習者はラベルのないデータセットを与えられ、データポイントのラベルをクエリすることで未知の仮説を効率的に学習することを目指している。 これは古典的最適決定木(ODT)問題として定式化できる: 一連のテスト、一連の仮説、そしてそれぞれのテストと仮説に対する結果が与えられた場合、我々の目標は、真の仮説を識別する低コストなテスト手順(すなわち決定木)を見つけることである。 この最適化問題は、各テストが決定論的結果を生成するという仮定の下で広く研究されている。 しかし、多くの応用、例えば臨床試験において、結果は不確実であり、決定論的な設定から考えを無効にする。 本研究では,音が持続するより一般的な場合においても,ODT問題の基本的な変種について検討する。 我々の近似アルゴリズムは、この数で性能が連続的に低下するテストや仮説あたりのノイズの多い結果の一般的なケースに対して、ほぼ可能な限りの保証を提供する。 有害化学物質を同定し,線形分類器を学習するアルゴリズムを数値的に評価し,我々のアルゴリズムは情報理論の最小値に非常に近い費用がかかることを示した。

関連論文リスト

• Submodular Information Selection for Hypothesis Testing with Misclassification Penalties [3.3444620077119436]
  仮説テスト/分類タスクにおいて,情報ソースの最適サブセットを選択する問題について検討する。 異なる誤分類誤りに対する一様でない処理を可能にする誤分類ペナルティフレームワークを提案する。 我々は,この指標が準モジュラであることを示すとともに,両情報集合選択問題に対するグリーディアルゴリズムのほぼ最適保証を確立する。
  論文  参考訳（メタデータ） (2024-05-17T17:31:02Z)
• Globally-Optimal Greedy Experiment Selection for Active Sequential Estimation [1.1530723302736279]
  逐次的に収集したデータの実験を適応的に選択するアクティブシーケンシャル推定の問題について検討する。 目標は、より正確なモデル推定のための実験選択ルールを設計することである。 そこで本稿では,グリーディ実験の選択手法のクラスを提案し,最大可能性の統計的解析を行う。
  論文  参考訳（メタデータ） (2024-02-13T17:09:29Z)
• Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
  本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。 線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
  論文  参考訳（メタデータ） (2023-11-01T04:41:16Z)
• Optimizing the Noise in Self-Supervised Learning: from Importance Sampling to Noise-Contrastive Estimation [80.07065346699005]
  GAN(Generative Adversarial Networks)のように、最適な雑音分布はデータ分布に等しくなると広く想定されている。 我々は、この自己教師型タスクをエネルギーベースモデルの推定問題として基礎づけるノイズ・コントラスト推定に目を向ける。 本研究は, 最適雑音のサンプリングは困難であり, 効率性の向上は, データに匹敵する雑音分布を選択することに比べ, 緩やかに行うことができると結論付けた。
  論文  参考訳（メタデータ） (2023-01-23T19:57:58Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  この仮定から逸脱すると、実際により良い統計的推定結果が得られることが示される。 特に、最適な雑音分布は、データと異なり、また、別の家族からさえも異なる。
  論文  参考訳（メタデータ） (2022-03-02T13:59:20Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Statistical Hypothesis Testing for Class-Conditional Label Noise [3.6895394817068357]
  この作業は、機械学習の実践者に質問に答えるためのツールを提供することを目的としています。 特に,あるインスタンスラベル対のデータセットが,クラス条件ラベルノイズによって破損したかどうかを確認するための仮説テストを提案する。
  論文  参考訳（メタデータ） (2021-03-03T19:03:06Z)
• Test Score Algorithms for Budgeted Stochastic Utility Maximization [12.360522095604983]
  既存のスコアリング機構、すなわちレプリケーションテストスコアを拡張して、異種アイテムのコストとアイテムの値を統合する。 我々のアルゴリズムと近似は、テストスコアが特定の期待値のノイズ見積もりであると仮定する。 我々は,我々のアルゴリズムが,同じ近似保証を維持しながら,商品が同じ方法で到着する状況に適応できることを示す。
  論文  参考訳（メタデータ） (2020-12-30T15:28:41Z)
• Algorithms for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference [2.169755083801688]
  連続的な結果を持つ観測データから、堅牢な因果推論テストインスタンスを解くための勾配アルゴリズムを提案する。 実現可能性定式化の構造を生かして,ロバストなテスト問題を解決するのに効率的な欲望スキームを開発する。
  論文  参考訳（メタデータ） (2020-12-22T16:12:11Z)
• Cross-validation Confidence Intervals for Test Error [83.67415139421448]
  この研究は、クロスバリデーションのための中心極限定理と、学習アルゴリズムの弱い安定性条件下での分散の一貫した推定器を開発する。 結果は、一般的な1対1のクロスバリデーションの選択にとって、初めてのものだ。
  論文  参考訳（メタデータ） (2020-07-24T17:40:06Z)
• Bloom Origami Assays: Practical Group Testing [90.2899558237778]
  グループテストは、いくつかの魅力的なソリューションでよく研究されている問題である。 近年の生物学的研究は、従来の方法と相容れない新型コロナウイルスの実践的な制約を課している。 我々は,Bloomフィルタと信条伝搬を組み合わせた新しい手法を開発し,n(100以上)の大きい値に拡張し,良好な経験的結果を得る。
  論文  参考訳（メタデータ） (2020-07-21T19:31:41Z)

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

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