論文の概要: Test Score Algorithms for Budgeted Stochastic Utility Maximization
- arxiv url: http://arxiv.org/abs/2012.15194v1
- Date: Wed, 30 Dec 2020 15:28:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-18 05:53:04.750543
- Title: Test Score Algorithms for Budgeted Stochastic Utility Maximization
- Title（参考訳）: 確率的ユーティリティ最大化のためのテストスコアアルゴリズム
- Authors: Dabeen Lee, Milan Vojnovic, Se-Young Yun
- Abstract要約: 既存のスコアリング機構、すなわちレプリケーションテストスコアを拡張して、異種アイテムのコストとアイテムの値を統合する。
我々のアルゴリズムと近似は、テストスコアが特定の期待値のノイズ見積もりであると仮定する。
我々は,我々のアルゴリズムが,同じ近似保証を維持しながら,商品が同じ方法で到着する状況に適応できることを示す。
- 参考スコア（独自算出の注目度）: 12.360522095604983
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by recent developments in designing algorithms based on individual
item scores for solving utility maximization problems, we study the framework
of using test scores, defined as a statistic of observed individual item
performance data, for solving the budgeted stochastic utility maximization
problem. We extend an existing scoring mechanism, namely the replication test
scores, to incorporate heterogeneous item costs as well as item values. We show
that a natural greedy algorithm that selects items solely based on their
replication test scores outputs solutions within a constant factor of the
optimum for a broad class of utility functions. Our algorithms and
approximation guarantees assume that test scores are noisy estimates of certain
expected values with respect to marginal distributions of individual item
values, thus making our algorithms practical and extending previous work that
assumes noiseless estimates. Moreover, we show how our algorithm can be adapted
to the setting where items arrive in a streaming fashion while maintaining the
same approximation guarantee. We present numerical results, using synthetic
data and data sets from the Academia.StackExchange Q&A forum, which show that
our test score algorithm can achieve competitiveness, and in some cases better
performance than a benchmark algorithm that requires access to a value oracle
to evaluate function values.
- Abstract（参考訳）: 実用性最大化問題を解くための個別項目スコアに基づくアルゴリズム設計の最近の発展により、我々は、予算化された確率的実用性最大化問題の解法として、観測された個々の項目パフォーマンスデータの統計量として定義されたテストスコアを使用する枠組みを研究した。
既存のスコアリング機構、すなわちレプリケーションテストスコアを拡張して、異種アイテムのコストとアイテムの値を統合する。
そこで本研究では,複製テストのみに基づいてアイテムを選択する自然なグリージーアルゴリズムにより,幅広いユーティリティ関数に対して最適値の定数係数内の解を出力することを示す。
我々のアルゴリズムと近似保証は、テストスコアが個々のアイテム値の限界分布に関する特定の期待値のノイズ推定であると仮定し、我々のアルゴリズムを実用化し、ノイズのない見積もりを仮定する以前の作業を拡張します。
さらに,我々のアルゴリズムは,同じ近似保証を維持しつつ,ストリーミング形式で商品が到着する状況に適応できることを示す。
我々は,Academia.StackExchange Q&Aフォーラムの合成データとデータセットを用いて,我々のテストスコアアルゴリズムが競争性を達成できることを示し,場合によっては関数値を評価するために値オラクルへのアクセスを必要とするベンチマークアルゴリズムよりも優れた性能を示す。
関連論文リスト
- From Variability to Stability: Advancing RecSys Benchmarking Practices [3.3331198926331784]
本稿では,RecSysアルゴリズムの公平かつ堅牢な比較を容易にするため,新しいベンチマーク手法を提案する。
本研究で導入された2つを含む30ドルのオープンデータセットの多種多様なセットを利用することで、データセット特性がアルゴリズム性能に与える影響を批判的に検証する。
論文 参考訳（メタデータ） (2024-02-15T07:35:52Z) - Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes [9.321976218862542]
プールベースのアクティブラーニングでは、学習者にラベルのないデータセットが与えられ、データポイントのラベルをクエリすることで未知の仮説を効率的に学習することを目的としている。
これは古典的最適決定木(ODT)問題として定式化できる: テストのセット、仮説のセット、各テストと仮説に対する結果が与えられた場合、我々の目標は、真の仮説を識別する低コストなテスト手順(すなわち決定木)を見つけることである。
本研究では,ODT問題の基本的変種について検討し,実験結果がうるさい場合,さらに一般的な場合であっても検討する。
論文 参考訳（メタデータ） (2023-12-23T21:47:50Z) - Budgeted Classification with Rejection: An Evolutionary Method with
Multiple Objectives [0.0]
予算付きシーケンシャル分類器(BSC)プロセスは、部分的特徴取得と評価ステップのシーケンスを通じて入力を行う。
これにより、不要な特徴取得を防止するための入力の効率的な評価が可能になる。
本稿では,信頼度に基づく拒否オプション付き逐次分類器を構築するための問題固有遺伝的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-01T22:05:16Z) - Compactness Score: A Fast Filter Method for Unsupervised Feature
Selection [66.84571085643928]
本稿では,CSUFS (Compactness Score) と呼ばれる高速な教師なし特徴選択手法を提案する。
提案アルゴリズムは既存のアルゴリズムよりも正確で効率的である。
論文 参考訳（メタデータ） (2022-01-31T13:01:37Z) - Diversity Enhanced Active Learning with Strictly Proper Scoring Rules [4.81450893955064]
テキスト分類のための能動学習(AL)のための獲得関数について検討する。
我々は、期待損失削減法(ELR)を、ログ確率や負平均二乗誤差などの(厳密な)スコアの増加を推定するために変換する。
BEMPSを用いた平均二乗誤差とログ確率を用いることで、ロバストな取得関数が得られることを示す。
論文 参考訳（メタデータ） (2021-10-27T05:02:11Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Benchmarking Simulation-Based Inference [5.3898004059026325]
確率的モデリングの最近の進歩は、確率の数値的評価を必要としないシミュレーションに基づく推論アルゴリズムを多数もたらした。
推論タスクと適切なパフォーマンス指標を備えたベンチマークを,アルゴリズムの初期選択とともに提供する。
性能指標の選択は重要であり、最先端のアルゴリズムでさえ改善の余地があり、逐次推定によりサンプリング効率が向上することがわかった。
論文 参考訳（メタデータ） (2021-01-12T18:31:22Z) - Causal Feature Selection for Algorithmic Fairness [61.767399505764736]
データ管理の統合コンポーネントにおける公平性について検討する。
本稿では,データセットの公平性を保証する特徴のサブコレクションを同定する手法を提案する。
論文 参考訳（メタデータ） (2020-06-10T20:20:10Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。