Fugu-MT 論文翻訳(概要): Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables

論文の概要: Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables

arxiv url: http://arxiv.org/abs/2302.14420v2
Date: Mon, 1 Jan 2024 10:15:27 GMT
ステータス: 処理完了
システム内更新日: 2024-01-03 02:58:01.249900
Title: Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables
Title（参考訳）: 多値決定変数の分布推定アルゴリズム
Authors: Firas Ben Jedidia, Benjamin Doerr, Martin S. Krejca
Abstract要約: 我々は、遺伝的ドリフトの既知の定量的解析を、多値変数の分布推定アルゴリズムに拡張する。我々の研究は、バイナリEDAの理解が自然に多値設定にまで拡張されていることを示している。
参考スコア（独自算出の注目度）: 10.165640083594573
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The majority of research on estimation-of-distribution algorithms (EDAs) concentrates on pseudo-Boolean optimization and permutation problems, leaving the domain of EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems, mostly unexplored. To render this domain more accessible, we propose a natural way to extend the known univariate EDAs to this setting. Different from a naive reduction to the binary case, our approach avoids additional constraints. Since understanding genetic drift is crucial for an optimal parameter choice, we extend the known quantitative analysis of genetic drift to EDAs for multi-valued variables. Roughly speaking, when the variables take $r$ different values, the time for genetic drift to become significant is $r$ times shorter than in the binary case. Consequently, the update strength of the probabilistic model has to be chosen $r$ times lower now. To investigate how desired model updates take place in this framework, we undertake a mathematical runtime analysis on the $r$-valued \leadingones problem. We prove that with the right parameters, the multi-valued UMDA solves this problem efficiently in $O(r\ln(r)^2 n^2 \ln(n))$ function evaluations. This bound is nearly tight as our lower bound $\Omega(r\ln(r) n^2 \ln(n))$ shows. Overall, our work shows that our good understanding of binary EDAs naturally extends to the multi-valued setting, and it gives advice on how to set the main parameters of multi-values EDAs.
Abstract（参考訳）: 分布推定アルゴリズム (EDAs) の研究の大半は擬ブール最適化と置換問題に集中しており、決定変数が2つ以上の値を取ることができる問題に対してEDAの領域は残るが、ほとんど探索されていない置換問題ではない。このドメインをよりアクセスしやすいものにするために、既知の単変量EDAをこの設定に拡張する自然な方法を提案する。初歩的な二分法と異なり、我々のアプローチは追加の制約を避ける。遺伝的ドリフトの理解は最適なパラメータ選択に不可欠であるため、遺伝的ドリフトの既知の定量分析を多値変数のEDAに拡張する。大まかに言えば、変数が異なる値 r$ を取るとき、遺伝的ドリフトが重要になる時間は二項の場合よりも r$ 倍短い。そのため、確率モデルの更新強度は、現在$r$よりも低く選択する必要がある。本フレームワークでは,モデル更新がどの程度望ましいかを検討するために,$r$-valued \leadingones問題に関する数学的ランタイム解析を行う。適切なパラメータにより、マルチ値 umda はこの問題を $o(r\ln(r)^2 n^2 \ln(n))$ で効率的に解くことが証明される。この境界は、我々の下界 $\Omega(r\ln(r) n^2 \ln(n))$ が表すように、ほぼ密である。全体として、我々の研究はバイナリEDAの理解が自然に多値設定にまで拡張していることを示し、マルチ値EDAの主パラメータの設定方法についてアドバイスを与えます。

関連論文リスト

Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax [2.07180164747172]
一般化されたOneMax関数の最初のランタイム解析を提供する。 r-cGAはこのr値のOneMax問題を効率的に解くことを示す。実験の最後には、多値OneMax関数の別の変種が期待されるランタイムに関する予想を述べる。
論文参考訳（メタデータ） (2024-04-17T10:40:12Z)
Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文参考訳（メタデータ） (2023-10-02T08:15:52Z)
Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-02-21T00:17:24Z)
Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments [48.96971760679639]
マルコフ決定過程(MDP)の分散依存的後悔境界について検討する。環境の微細な分散特性を特徴付けるための2つの新しい環境規範を提案する。モデルに基づく手法では、MVPアルゴリズムの変種を設計する。特に、この境界は極小かつ決定論的 MDP に対して同時に最適である。
論文参考訳（メタデータ） (2023-01-31T06:54:06Z)
Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
論文参考訳（メタデータ） (2022-06-14T12:58:46Z)
An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
論文参考訳（メタデータ） (2022-05-17T15:28:46Z)
Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments [55.24895403089543]
ドメインの一般化は、限られた数のトレーニング環境からのデータで、目に見えないテスト環境でうまく機能することを目的としています。我々は,O(logd_s)$環境のみを見た後に一般化する予測器を高確率で生成することを保証する反復的特徴マッチングに基づく新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-06-18T04:39:19Z)
Distributionally Robust Optimization with Markovian Data [8.126833795693699]
本研究では,不確実な問題パラメータの確率分布が不明なプログラムについて検討する。本稿では,問題の目的関数と最適解を推定するために,データ駆動型分布法を提案する。
論文参考訳（メタデータ） (2021-06-12T10:59:02Z)
Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文参考訳（メタデータ） (2021-03-04T19:01:20Z)
Alternating Direction Method of Multipliers for Quantization [15.62692130672419]
量子化のための乗算器の交互方向法(texttADMM-Q$)アルゴリズムの性能について検討する。不正確な更新ルールを処理できる$texttADMM-Q$のいくつかのバリエーションを開発しています。提案手法の有効性を実証的に評価した。
論文参考訳（メタデータ） (2020-09-08T01:58:02Z)
The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis [9.853329403413701]
陰性な発見はUMDAのパラメータの不運な選択によって引き起こされることを示す。この結果から,UMDAは進化的アルゴリズムよりも局所最適に対処できることが示唆された。
論文参考訳（メタデータ） (2020-07-16T12:07:09Z)

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

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