論文の概要: The working principles of model-based GAs fall within the PAC framework: A mathematical theory of problem decomposition
- arxiv url: http://arxiv.org/abs/2501.10777v1
- Date: Sat, 18 Jan 2025 14:18:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-22 14:24:59.992531
- Title: The working principles of model-based GAs fall within the PAC framework: A mathematical theory of problem decomposition
- Title（参考訳）: モデルベースGAの動作原理はPACフレームワークに該当する:問題分解の数学的理論
- Authors: Tian-Li Yu, Chi-Hsien Chang, Ying-ping Chen,
- Abstract要約: 本稿では,リンクの概念を記述するために,アルゴリズムに依存しない定義を提供する。
本論文は,結合度が制限された問題はすべて分解可能であることを証明し,連鎖学習を通じて適切な問題分解が可能であることを証明した。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: The concepts of linkage, building blocks, and problem decomposition have long existed in the genetic algorithm (GA) field and have guided the development of model-based GAs for decades. However, their definitions are usually vague, making it difficult to develop theoretical support. This paper provides an algorithm-independent definition to describe the concept of linkage. With this definition, the paper proves that any problems with a bounded degree of linkage are decomposable and that proper problem decomposition is possible via linkage learning. The way of decomposition given in this paper also offers a new perspective on nearly decomposable problems with bounded difficulty and building blocks from the theoretical aspect. Finally, this paper relates problem decomposition to PAC learning and proves that the global optima of these problems and the minimum decomposition blocks are PAC learnable under certain conditions.
- Abstract（参考訳）: リンク、ビルディングブロック、問題分解の概念は、長年にわたって遺伝的アルゴリズム(GA)分野に存在し、モデルベースGAの開発をガイドしてきた。
しかしながら、それらの定義は通常曖昧であり、理論的支援を開発するのが困難である。
本稿では,リンクの概念を記述するために,アルゴリズムに依存しない定義を提供する。
この定義により,有界リンクの問題はすべて分解可能であり,適切な問題分解はリンケージ学習によって可能であることを証明した。
また,本論文では,有界難解問題に対する解法と,理論的側面からのビルディングブロックの解法についても論じる。
最後に、問題分解とPAC学習を関連づけ、これらの問題の大域的最適性と最小分解ブロックが特定の条件下でPAC学習可能であることを証明した。
関連論文リスト
- Leveraging PAC-Bayes Theory and Gibbs Distributions for Generalization
Bounds with Complexity Measures [14.408127155170774]
我々は、分解されたPAC-Bayes境界の枠組みを活用し、任意の複雑性測度で瞬時化可能な一般一般化を導出する。
我々の境界は仮説と学習サンプルを共同で確率に立っており、これは複雑性を一般化ギャップに適応させることができる。
論文 参考訳（メタデータ） (2024-02-19T10:15:11Z) - Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
本稿では,ロボット推論と計画における連続的制約満足度問題(CCSP)の解法について紹介する。
対照的に、構成拡散連続制約解法(Diffusion-CCSP)は、CCSPに対する大域的な解を導出する。
論文 参考訳（メタデータ） (2023-09-02T15:20:36Z) - A Parameterized Theory of PAC Learning [19.686465068713467]
おそらく略正(PAC)学習は、サンプル複雑性理論の中核的な概念である。
我々は、パラメータ化複雑性の要素を組み込んだ最近のPAC学習結果に新たな光を当てることができるパラメータ化PAC学習の理論を開発した。
論文 参考訳（メタデータ） (2023-04-27T09:39:30Z) - Evolution is Still Good: Theoretical Analysis of Evolutionary Algorithms
on General Cover Problems [16.98107289469868]
いくつかの近似機構は本質的に多くの進化的アルゴリズムに埋め込まれているようである。
我々は、一般化された単純多目的進化アルゴリズムのための統合分析フレームワークを提案することにより、そのような関係を同定する。
論文 参考訳（メタデータ） (2022-10-03T01:25:53Z) - Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。
これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。
制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
論文 参考訳（メタデータ） (2022-08-23T18:56:05Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。
我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文 参考訳（メタデータ） (2021-10-12T02:21:30Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。
問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。
我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
論文 参考訳（メタデータ） (2020-06-18T17:18:02Z) - Probably Approximately Correct Constrained Learning [135.48447120228658]
我々は、ほぼ正しい学習フレームワーク(PAC)に基づく一般化理論を開発する。
PAC学習可能なクラスも制約のある学習者であるという意味では,学習者の導入は学習問題を難しくするものではないことを示す。
このソリューションの特性を分析し,制約付き学習が公平でロバストな分類における問題にどのように対処できるかを説明する。
論文 参考訳（メタデータ） (2020-06-09T19:59:29Z) - Polynomial-Time Exact MAP Inference on Discrete Models with Global
Dependencies [83.05591911173332]
ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。
本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
論文 参考訳（メタデータ） (2019-12-27T13:30:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。