文献

J-GLOBAL ID：202102250714359334   整理番号：21A0444896

相関のあるPandoraボックス:学習と近似【JST・京大機械翻訳】

Pandora’s Box with Correlations: Learning and Approximation

著者 (5件)： Chawla Shuchi (University of Wisconsin - Madison,Department of Computer Sciences,Madison,WI,USA) ,  Gergatsouli Evangelia (University of Wisconsin - Madison,Department of Computer Sciences,Madison,WI,USA) ,  Teng Yifeng (University of Wisconsin - Madison,Department of Computer Sciences,Madison,WI,USA) ,  Tzamos Christos (University of Wisconsin - Madison,Department of Computer Sciences,Madison,WI,USA) ,  Zhang Ruimin (University of Wisconsin - Madison,Department of Computer Sciences,Madison,WI,USA)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2020  号： FOCS  ページ： 1214-1225  発行年： 2020年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： PandoraのBox問題とその拡張は,アルゴリズムがいくつかのコストで入力ランダム変数の瞬時化を得ることができる確率的入力で最適化問題を捕える。著者らの知る限り,このクラスの問題に関するすべての以前の研究は,入力における異なるランダム変数が独立して分布していると仮定する。そのように,多くの実世界の設定を捉えていない。本論文では,相関のあるPandoraのBox型問題に対する最初の近似アルゴリズムを提供した。著者らは,このアルゴリズムが入力に関する関節分布から引き出されるサンプルへのアクセスを有すると仮定した。これらの問題に対するアルゴリズムは,これまで見出された最良の解を停止し,返すときと同様に,ランダム変数をプローブする順序を決定しなければならない。一般に,最適アルゴリズムは,以前に観察されたインスタンス化に基づいて適応的に両方の決定を行う。このような完全適応(FA)戦略は,サンプルアクセスによる任意のサブ線形因子内で効率的に近似できない。従って,固定事前決定順序でランダム変数をプローブする部分適応(PA)戦略を近似するより単純な目的に焦点を当てたが,観察された瞬間化に基づいて停止する時を決定する。著者らは,多くの異なる実現可能性制約を考慮し,各ケースに対して最良のPA戦略に関して近似的に最適である簡単なPA戦略を提供した。提案アルゴリズムの全ては多項式サンプル複雑性を持つ。さらに,著者らの結果が一定の因子内で堅く,FA戦略の全電力を用いてもより良い要因が達成できないことを示した。Copyright 2021 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  多項式 ,  プローブ ,  *学習 ,  最適化問題 ,  電力 ,  最適化手法 ,  *近似法 ,  線形性
準シソーラス用語： *Pandora ,  近似アルゴリズム ,  ランダム変数 ,  複雑性 , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (4件)： 相関 ,  ボックス ,  学習 ,  近似