C语言中梯度下降的数值不稳定性

Numerical instability of gradient descent in C

提问人:Niccolò Tiezzi 提问时间:6/11/2023 更新时间:6/11/2023 访问量:93

问:

我用最陡峭的下降方法编写了一个简单的梯度下降算法。

对于陡峭的下降,我的意思是将步长优化为最小化 f(x - lambda*grad(f)) 的步长,其中 lambda 是步长,结果是每个方向都与前一个方向正交。

问题是该程序似乎非常不稳定:它只在二次函数下工作得很好,但即使是像 x^4 + y^4 + z^4 这样的四次函数也不稳定,无论使用多少精度

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double l2_norm(double *x1, double *x2, int m);
void get_grad(double (*f)(double *x, int m), double *x, double *grad, int m);
void copy(double *a, double *b, int m);
void add(double *a, double *b, double lambda, int m);
double dFdLambda(double (*f)(double *x, int m), double *x, double *u, int m);
void descent(double (*f)(double *x, int m), double *x, double *u, int m);

void print_vec(double *x, int m){
    for(int i=0; i<m; i++){
        printf("%f\n", x[i]);
    }
    return;
}

double f_temp(double *x, int m){

    double f=0.;

    for(int i=0; i<m; i++){
        f += (x[i]-1)*(x[i]-1);
    }
    return f;
}

int main(){

    double x[] = {2., 2., 2.};
    double *grad;
    double *x_old;
    int m = 3;
    double e = 1.E-6;

    grad = malloc(m*sizeof(double));
    x_old = malloc(m*sizeof(double));
    
    while(l2_norm(x, x_old, m) > e){
        copy(x, x_old, m);
        get_grad(f_temp, x, grad, m);
        descent(f_temp, x, grad, m);
        print_vec(x, m);
    }

    printf("\n");
    print_vec(x, m);
    

    return 0;
}


double l2_norm(double *x1, double *x2, int m){

    double norm = 0;

    for(int i=0;i<m;i++){
        norm += pow(x1[i]-x2[i], 2);
    }

    norm = sqrt(norm);

    return norm;
}


void get_grad(double (*f)(double *x, int m), double *x, double *grad, int m){
    /*
    numerical gradient with simmetric method

    the actual gradient computed is -grad in order to be used in 
    gradient descent
    */
    double e = 1.E-6; // numerical precision
    double *x_forward;
    double *x_backward;
    x_forward = malloc(m*sizeof(double));
    x_backward = malloc(m*sizeof(double));
    
    for(int i=0;i<m; i++){
        x_forward[i] = x[i] + e;
        x_backward[i] = x[i] - e;    
        grad[i] = -(f(x_forward, m) - f(x_backward, m))/(2*e);
        x_forward[i] -= e;
        x_backward[i] += e;
    }
    free(x_forward);
    free(x_backward);
    return;
}


double dFdLambda(double (*f)(double *x, int m), double *x, double *u, int m){
    /*
    compute the total derivative dF/dLambda in the point x along
    the direction u
    */
    double e = 1.E-5;
    double *x_forward;
    double *x_backward;
    double der;

    x_forward = malloc(m*sizeof(double));
    x_backward = malloc(m*sizeof(double));
    copy(x, x_forward, m);
    copy(x, x_backward, m);
    add(x_forward, u, e, m);
    add(x_backward, u, -e, m);

    der = (f(x_forward, m) - f(x_backward, m))/(2*e);

    free(x_forward);
    free(x_backward);

    return der;
}


void copy(double *a, double *b, int m){
    //copies a into b
    for(int i=0; i<m; i++){
        b[i] = a[i];
    }
    return;
}


void add(double *a, double *b, double lambda, int m){
    /*
    adds lambda*b to a
    */
    for(int i=0; i<m; i++){
        a[i] += lambda*b[i];
    }
    return;
}


void descent(double (*f)(double *x, int m), double *x, double *u, int m){
    /*
    actual gradient descent starting from x going in direction u
    */
    double e = 1.E-5;
    double derA, derB, derC;
    double *x_start;
    double lambda, lambda_min, lambda_max;

    lambda = e;

    x_start = malloc(m*sizeof(double));
    copy(x, x_start, m);
    derA = dFdLambda(f, x, u, m);
    derC = derA;

    /*
    this while loop finds the interval in which the total derivatives df/dl
    changes sign i.e. the interval in which the solution of df/dl = 0
    will be searched with bisection method
    */
    while((derA*derC) >= 0.){
        copy(x_start, x, m);
        add(x, u, lambda, m);
        derC = dFdLambda(f, x, u, m);
        lambda *= 2.;
    }

    /*
    because lambda >= 0 the leftmost point of the interval is 0, the rightmost 
    the point found before after which the total derivatives changes sign
    */
    lambda_min = 0;
    lambda_max = lambda;
    lambda = 0.5*(lambda_min + lambda_max);

    while((fabs(lambda_max - lambda_min)) > e){
        copy(x_start, x, m);
        add(x, u, lambda_min, m);
        derA = dFdLambda(f, x, u, m);

        copy(x_start, x, m);
        add(x, u, lambda, m);
        derB = dFdLambda(f, x, u, m);

        if((derA*derB) > 0.){
            lambda_min = lambda;
        } 
        else if((derA*derB) < 0.){
            lambda_max = lambda;
        }
        else{
            lambda_min = lambda_max = lambda;
        }

        lambda = 0.5*(lambda_min + lambda_max);
    }

    copy(x_start, x, m);
    // the modified vector x will cointain the coordinates of the minumum
    add(x, u, lambda, m); 
    free(x_start);

    return;
}

输出是正确的f += (x[i]-1)*(x[i]-1)

1.000005
1.000005
1.000005
-1.499995
-1.499995
1.000005
1.000012
1.000012
1.000000
1.000000
1.000000
1.000000
1.000000
1.000000
1.000000

1.000000
1.000000
1.000000

但是使用甚至 pow() 函数和 2 次方,结果类似于(x[i]-1)*(x[i]-1)*(x[i]-1)*(x[i]-1)

1.000010
1.000010
1.000010
-1.499990
-1.499990
1.000010
1.000292
1.000292
1.000010
1.000292
1.000000
1.000010
1.000292
-1032674302637538115769421495899732814941072310657452010951926707678661836800.000000
-171980112174886070524247400874370796081962558827236065865505533642887865040896.000000
inf
inf
nan

inf
inf
nan

降低函数(变量)内部的数值精度似乎仅适用于简单的二次函数(不使用 pow() 函数),否则我会得到 null 或 inf 数字double e

c 精密 数值方法 梯度下降 科学计算

评论


答:

3赞 John Bollinger 6/11/2023 #1

当分配的对象的值不确定时,您在使用分配的对象时会遇到一些问题。第一个在:main

    x_old = malloc(m*sizeof(double));
    
    while(l2_norm(x, x_old, m) > e){

请注意,您正在使用数据点,而从未为其分配任何值。由于您总是希望至少进行一次迭代,因此将循环重构为 .x_oldwhiledo ... while

但是你还有更多可能更有影响力的东西:get_grad()

    x_forward = malloc(m*sizeof(double));
    x_backward = malloc(m*sizeof(double));
    
    for(int i=0;i<m; i++){
        x_forward[i] = x[i] + e;
        x_backward[i] = x[i] - e;    
        grad[i] = -(f(x_forward, m) - f(x_backward, m))/(2*e);
        x_forward[i] -= e;
        x_backward[i] += e;
    }

请注意,当这些值未定义时,您将开始使用分配时和分配后立即指向的数据。您最终会为所有已分配的元素赋值,但最初只为每个元素赋值 0。据推测,您希望在开始循环之前将数据复制到这些指向的空间中。正如目前所写的,如果没有这种复制,产生的行为是不确定的。绝对没有理由期望存储在 *grad 中的结果数据将是 x 处梯度的估计值。x_forwardx_backwardx

即使你可以依靠将分配的空间初始化为全零(它不会这样做,但确实如此),程序也会出错。特别是,该函数通常会在不同点计算假定梯度的每个分量。malloc()calloc()get_grad()

我能够相当接近地重现您的程序的错误输出。计算采用了类似的路径,在没有太多迭代后分化到 NaN。

修复这两个问题后,程序将生成以下输出:

1.000005
1.000005
1.000005
1.000000
1.000000
1.000000
1.000000
1.000000
1.000000

1.000000
1.000000
1.000000

更新

该程序在函数中也存在实现错误。它计算 f 在所选方向上的导数为dFdLambda()

    der = (f(x_forward, m) - f(x_backward, m))/(2*e);

,但该公式中的除数不正确,在某些情况下非常不正确。它应该是 和 之间的距离(L2 范数)。当我进行更正时,生成的程序也会收敛到四分形情况。x_forwardx_backward*


我想您可能仍然可以找到程序行为异常的输入函数。特别是,对于在局部最小值附近具有更陡峭梯度的函数以及振荡非常快的函数,您可能会遇到问题。对于在域的各个维度中具有明显各向异性的函数,以及具有非常大值的局部最小值的函数,您也可能会遇到问题。

解决@chux描述的问题将有助于解决其中的一些问题。一种更具适应性的方法来估计梯度和导数可能对其他一些方法有所帮助。

下降计算本身可以防止发散。例如,它可以验证 f 的值实际上确实减小,和/或每个下降步长 x 的变化可以通过各种方式被抑制或限制。

此外,我在数学上理解为什么估计函数的导数并使用它们沿所选方向搜索最小值,通过计算,您可能最好直接搜索最小值,使用函数的值而不是估计其导数。这肯定会减少像你观察到的那样出现背离的可能性,而且它的收敛特性总体上可能同样好或更好。descent()

然而,最终,数值程序受到它们使用的数字表示的约束,这些表示不可避免地具有有限的范围和精度(尽管如果您愿意,可以或多或少地任意选择特定限制)。这是数值规划的基本约束。


*虽然我实际上不确定为什么它会有所不同,因为该程序似乎只取决于导数的符号,而不是它的大小。

评论

0赞 Niccolò Tiezzi 6/11/2023
感谢您的建议,我使用 do...while 循环并在 get_grad() 函数的 for 循环之前实现 copy(x, x_forward, m) 和 copy(x, x_backward, m)(将增量修改为 x_forward[i] += e, x_backward[i] -= e 在梯度计算之前,x_forward[i] -= e, x_backward[i] += e 之后,但使用像 f += pow((x[i]-1) 这样的四分函数, 4)程序仍然不稳定
0赞 John Bollinger 6/11/2023
@NiccolòTiezzi,我发现了您程序中的另一个缺陷,并更新了此答案以对其进行讨论。我还对该计划的一般方法进行了一些更广泛的评论。
0赞 Niccolò Tiezzi 6/12/2023
非常感谢,更改方向导数的分母确实修复了四次函数的程序。我不指望它实际上可用于复杂的函数,因为我把它写成一个幼稚的实现来取乐(仅用于凸函数和平滑函数),但您的建议对于科学编程的进一步研究非常有用
1赞 chux - Reinstate Monica 6/11/2023 #2

除了@John布林带的好答案:

考虑另一种“亲密”测试

无论使用多少精度都不稳定

代码目前以线性方式比较值,但浮点值是以对数方式分布的 - 这就是为什么它们被称为浮点而不是点。他们应该得到一个测试,该测试使用根据参数的大小而变化的测试。否则,除非完全相等,否则所有大数对永远不会“大致相等”,并且所有小数对始终相等。

double e = 1.E-5;
...
// while((fabs(lambda_max - lambda_min)) > e){
while(!about_equal(lambda_max, lambda_min, e)) {

下面的候选者是说明性的,而不是优化的。如何最好地进行比较取决于OP目标的细节。about_equal()

bool about_equal(double a, double b, double relative_error) {
  double diff = fabs(a - b);
  double magnitude = fmax(fabs(a), fabs(b));
  return diff <= magnitude * relative_error;
}