2014，TEVC( 三 ) _语义

定义 1 语义映射 ( ) 是一个函数s ： P → S s：P→S s：P→S 将任意程序从P P P 映射到语义空间S S S，具有如下性质：
让我们总结一下由这个定义产生的语义的性质。首先，每个程序只有一个语义。其次，两个或多个程序可以具有相同的语义。第三，不同行为的程序 (即对一个或多个输入产生不同的输出) 具有不同的语义
语义空间S S S 列举了程序对于所有考虑的输入的所有可能行为。映射s s s 隐式地将程序划分为语义等价类，使得S S S 中的每个元素一一对应于程序产生的唯一输出组合。从这个意义上说，语义 () 在捕捉关于程序行为的全部信息上是完整的，当s ( p ) s(p) s(p) 已知时，不需要更多的判断p p p 的行为。
定义 1 没有说明语义是如何表示的。它可以是任何满足其中规定的条件的形式对象，包括形式语言理论中使用的指称语义或操作语义。注意，程序的代码(即一个符号序列)不能被认为是它的语义，除非语义映射是双射 (这是实践中从未有过的) 。
在本文中，我们采用GP中常见的约定，并假设一个编程任务是由有限个适应度案例 ( cases) 的训练样本指定的，每个case 是由程序输入和相应的期望程序输出组成的一对。然后，Acase 是I × O I × O I×O 中的一对。我们还假设I I I 只包含给定的cases 集合中的输入，符合机器学习中的样例学习范式，其中学习者无法访问其他(测试)示例。在这些假设下，我们可以更具体地定义语义：
补充： acase 是用来衡量 GP 性能的一系列问题之一。GP产生个体过程中通常会在发现一个解决方案在case 上得分高于某个阈值时，或者当经过一定的时间步长而没有发现这样的解决方案时得出结论。如某个节点的期望语义是 {-2, 0, 0}，这个期望语义即为case
定义 2 程序p p p 的语义s ( p ) s(p) s(p) 是在I I I 的所有输入上运行p p p 得到的来自O O O 的值的向量2：
其中l = ∣ I ∣ l = |I| l=∣I∣ 为cases 的数量
GP [23]、[16]、[13]、[18]、[7] 等早期语义研究中流行的这种语义表征符合定义 1.特别地，它在上述意义上是完备的：因为s ( p ) s(p) s(p) 明确列举了所有输入的程序行为，它允许我们通过简单地从向量中选择适当的元素，确定i n ∈ I in∈I in∈I 中任何元素的程序输出。
B.tasks
语义空间的性质，特别是其元素之间的关系，对于本文提出的方法至关重要。推动语义GP最近发展的关键点是，语义空间天生具有结构。这种结构是由编程任务本身施加给S S S 的，更具体地说是由衡量实际程序行为与期望程序行为之间差异的适应度函数施加的：
定义 3 给定一组程序P P P (由编程语言隐式定义)，一个编程任务 (Task 简称任务) 包含寻找一个最小化的程序p ∈ P p∈P p∈P
其中t ∈ S t∈S t∈S 是描述程序期望行为的目标语义(简称目标)，d ： S × S → R d：S × S→\Bbb{R} d：S×S→R 是一个度量，称为语义距离。对于一个f ( p ) = 0 f(p) = 0 f(p)=0 的程序p p p，我们称它解决了任务t t t 。
补充：s ( p ) s(p) s(p) 为将输入带入程序并映射的一组向量，产生的实际语义，t t t 为期望的目标语义
从现在开始，我们将术语"目标"和"编程任务"互换使用，因为在其他条件相同的情况下，目标唯一地标识了编程任务。
作为例子，我们考虑一类单变量符号回归任务，其中程序是单个实自变量的实值函数，即I ? R I \ \Bbb{R} I?R 和O ? R O \ \Bbb{R} O?R。任务由I × O I × O I×O 中的l = ∣ I ∣ l = | I | l=∣I∣ 适应案例 ( cases)( i n i , t i ) ( in_i , t_i) (ini?,ti?) 指定，其中i n i ∈ I in_i∈I ini?∈I 是程序输入，t i t_i ti? 定义相应的期望输出3 。程序p p p 的语义s ( p ) s(p) s(p) 是通过将p p p 应用于I I I 的元素而得到的l l l 个实数的向量。程序的最小适应度由程序语义与目标t t t 之间的欧氏距离或曼哈顿距离d d d 定义。