論文の概要: (1+1) Genetic Programming With Functionally Complete Instruction Sets
Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error
- arxiv url: http://arxiv.org/abs/2303.07455v1
- Date: Mon, 13 Mar 2023 20:24:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-15 17:31:22.805341
- Title: (1+1) Genetic Programming With Functionally Complete Instruction Sets
Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error
- Title（参考訳）: (1+1)機能的完全命令セットによる遺伝的プログラミングは、任意小誤差によるブール接続と解離を回避できる
- Authors: Benjamin Doerr, Andrei Lissovoi, Pietro S. Oliveto
- Abstract要約: GPシステムは、必要最小限のコンポーネントが備わっている場合、$n$変数の結合を進化させることができる。
GPシステムは、$O(ell n log2 n)$, $ell geq が受理木の大きさの極限であるような予想において、正確なターゲット関数を進化させることができることを示す。
- 参考スコア（独自算出の注目度）: 16.075339182916128
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently it has been proven that simple GP systems can efficiently evolve a
conjunction of $n$ variables if they are equipped with the minimal required
components. In this paper, we make a considerable step forward by analysing the
behaviour and performance of a GP system for evolving a Boolean conjunction or
disjunction of $n$ variables using a complete function set that allows the
expression of any Boolean function of up to $n$ variables. First we rigorously
prove that a GP system using the complete truth table to evaluate the program
quality, and equipped with both the AND and OR operators and positive literals,
evolves the exact target function in $O(\ell n \log^2 n)$ iterations in
expectation, where $\ell \geq n$ is a limit on the size of any accepted tree.
Additionally, we show that when a polynomial sample of possible inputs is used
to evaluate the solution quality, conjunctions or disjunctions with any
polynomially small generalisation error can be evolved with probability $1 -
O(\log^2(n)/n)$. The latter result also holds if GP uses AND, OR and positive
and negated literals, thus has the power to express any Boolean function of $n$
distinct variables. To prove our results we introduce a super-multiplicative
drift theorem that gives significantly stronger runtime bounds when the
expected progress is only slightly super-linear in the distance from the
optimum.
- Abstract（参考訳）: 近年,必要最小限の部品を装備すれば,単純なGPシステムは$n$変数の結合を効率的に進化させることができることが証明されている。
本稿では,最大$n$変数のブール関数の表現を可能にする完全関数集合を用いて,ブール結合や$n$変数の解離を進化させるGPシステムの挙動と性能を分析することにより,かなり前進する。
まず、プログラムの品質を評価するのに完全真理表を使い、そしてandおよびor演算子と正のリテラルの両方を備えたgpシステムが、期待値の$o(\ell n \log^2 n)$の正確な目標関数を進化させ、ここで$\ell \geq n$は任意の許容される木の大きさの制限である。
さらに, 可能な入力の多項式サンプルを用いて解の質を評価する場合, 任意の多項式的最小一般化誤差を伴う結合あるいは接続を確率1o(\log^2(n)/n)$で発展させることができることを示した。
後者の結果はまた、GPが AND, OR and positive and negated literals を使用していれば、$n$の異なる変数のブール関数を表現することができる。
この結果を証明するために, 最適からの距離において, 期待される進行がわずかに超線形である場合, ランタイム境界が大幅に強くなる超乗算ドリフト定理を導入する。
関連論文リスト
- Quantum computational complexity of matrix functions [2.7488316163114823]
2つの原始問題の計算複雑性について検討する。
単項関数、チェビシェフ関数、時間発展関数、逆関数の4つの関数を考える。
論文 参考訳（メタデータ） (2024-10-17T18:00:03Z) - Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
分解硬度(d硬度)の概念を導入する。
d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
論文 参考訳（メタデータ） (2023-12-16T12:44:36Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Computing the Newton-step faster than Hessian accumulation [8.147652597876862]
関数の計算グラフを考えると、この境界は$O(mtau3)$に縮めることができ、$tau, m$はグラフのツリー分解の幅と大きさである。
提案アルゴリズムは,LQRに基づく非線形最適制御法を一般化し,ヘシアンが高密度である場合においても,反復複雑度において非自明なゲインを提供する。
論文 参考訳（メタデータ） (2021-08-02T11:22:08Z) - Lockout: Sparse Regularization of Neural Networks [0.0]
パラメータ $w$ の値に制約 $P(w)leq t$ を置き、精度を向上させるために正規化を適用する。
我々は、任意の微分可能関数$f$と損失$L$に対してそのようなすべての解を提供する高速アルゴリズムと、各パラメータの絶対値の単調関数である任意の制約$P$を提案する。
論文 参考訳（メタデータ） (2021-07-15T07:17:20Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。
我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。
我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
論文 参考訳（メタデータ） (2020-10-16T08:10:02Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文 参考訳（メタデータ） (2020-02-23T22:51:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。