2014，TEVC( 六 ) _语义

图1：语义反向传播示例。黑色向量是每个程序节点(即对应子树的语义)上的实际语义。期望的语义(蓝色点状矢量)从根节点传播到蓝色节点n n n 。
表 I 中定义的函数针对所有剩余参数构成的特定上下文，在子树a a a 的根上执行单个指令关于其第k k k 个参数的反转。如果a a a 有两个或多个参数，的结果不仅取决于a a a 的输出，还取决于a a a 的其他参数(上下文)提供的值。例如，应用于图 1 所示的第一个适应度案例 ( case) 和程序的根节点，即( c 1 ? c 2 , 2 , o ) ( c_1-c_2 , 2 , o) (c1??c2?,2,o)，在c 1 = 1 c_1 = 1 c1?=1 和o = ? 2 o = - 2 o=?2 上运行。根据表 I 的第二行返回( 1 ? c 2 , 2 , ? 2 ) ( 1-c_2 , 2 , -2) (1?c2?,2,?2)，即c 1 ? o = 1 ? ( ? 2 ) = 3 c_1 - o = 1- ( - 2 ) = 3 c1??o=1?(?2)=3 。
表I：符号回归和布尔域实验中使用的( a , k , o ) ( a , k , o) (a,k,o)的定义。对于子树a a a (具有一个或两个返回c 1 c_1 c1? 和c 2 c_2 c2? 的子节点的指令节点)，在给定整个子树a a a 的期望值的情况下，由公式确定第一个(k = 1 k = 1 k=1 ,中心柱)和第二个(k = 2 k = 2 k=2 ,右列)参数的期望值。
对于这样的双射指令，求逆是无歧义的，即( a , k , o ) ( a , k , o) (a,k,o) 返回单个值。否则，在返回多个期望值时可能是模棱两可的。例如，为l o g ∣ ? ∣ log | · | log∣?∣ 返回两个值。周期函数可以通过无穷多种方式求逆，因此对于 sin 和 cos，我们将期望值的集合限制为两个任意选择的值。
另一种形式的歧义产生于无效代码。考虑程序c 1 × c 2 c_1 × c_2 c1?×c2?，其中c 2 = 0 c_2 = 0 c2?=0. 无论我们用什么代替c 1 c_1 c1?，程序的输出都不发生变化。如果期望输出等于零，则期望值集合包含所有实数。在这种情况下，返回特殊符号 ‘*’ 。
( a , k , o ) (a , k , o) (a,k,o) 返回一个空集，如果没有作为第k k k 个参数传递给a a a 的值可以使其返回o o o 。例如，指数函数不能产生负值。
在这两种情况下( () =∞ ∞ ∞ 或 {*})，进一步传播不能改变D i D_i Di? 的内容，所以 ION 停止对路径(算法 1 第 5 行)的遍历，算法进入下一个case 。最后，该算法将每个适应度情况下计算得到的期望值集合D i D_i Di? 聚集成一个元组，并返回该元组作为期望语义。
C.ofon
从技术上讲，语义反向传播只传播从目标(即语义空间中的某些点)得到的特定期望值。然而，得到的期望语义将成为单独搜索过程的子目标，使用我们在下一节中定义的搜索算子。该搜索过程将由与子目标的语义距离驱动。因此，理解与目标的语义距离和与子目标的语义距离之间的关系是至关重要的。
为了提供这种见解，我们考虑一个单变量符号回归问题的例子，其中适应度函数 (公式 2 ) 是欧氏距离。为了简单起见，我们只考虑两种case，并假设目标t = ( 0 , 0 ) t = ( 0,0 ) t=(0,0) 。与第 III-A 节一致，这里的语义空间是R 2 \Bbb{R}^2 R2，悬停在其上的适应度景观是一个三维的 “上下颠倒” 的欧氏锥，顶点在( 0 , 0 ) ( 0,0 ) (0,0) 点。这种景观在图 2 (a) 中呈现为热力图。该热力图中每个点的坐标对应一个假想程序在两种适应度情况下返回的输出( y 1 , y 2 ) ( y_1,y_2) (y1?,y2?)，点的颜色反映了程序的适应度。
现在我们将演示如何通过转换期望的输出，语义反向传播也隐式地转换整个适应度景观(即,不仅图 2 (a) 中的点,而且相应的适应度值) 。考虑程序后缀c o s cos cos 。对于图 2 (a) 中热图中的每一点( y 1 , y 2 ) ( y_1 , y_2) (y1?,y2?)，我们可以找到所有的点( y 1 ′ , y 2 ′ ) ∈ R 2 ( y^′_1 , y^′_2)∈\Bbb{R}^2 (y1′?,y2′?)∈R2 使得c o s ( y 1 ′ ) = y 1 cos(y^′_1) = y_1 cos(y1′?)=y1? 和c o s ( y 2 ′ ) = y 2 cos(y^′_2) = y_2 cos(y2′?)=y2?（即进行反转求解），并将它们标记为与( y 1 , y 2 ) (y_1 , y_2) (y1?,y2?) 相同的适应度(颜色) 。产生的热图，如图 2 (b) 所示，是由前缀为c o s cos cos 的程序所看到的转换后的景观。对于任意程序p p p，图 2 (b) 中点s ( p ) ∈ R 2 s(p)∈\Bbb{R}^2 s(p)∈R2的颜色反映了复合程序[ p c o s ] [p~ cos] [pcos] 的适合度。该景观有多个子目标(以十字架标记)，因为余弦是周期性的。