C语言 逻辑回归代码在生成约43,500个观察值时停止工作

u91tlkcl  于 2023-02-03  发布在  其他
关注(0)|答案(4)|浏览(118)

我在用C语言编写的逻辑回归代码中遇到了一些困难,虽然它似乎可以在较小的半随机数据集上工作,但它停止工作了(例如,分配属于类1的适当概率)在我传递43,500个观测的点附近(通过调整创建的观测的数目来确定。当创建代码中使用的150个特征时,我创建了前两个函数,作为观测值的函数,所以我不确定这是否是问题所在,尽管我使用了双精度,也许代码中的某个地方有溢出?
下面的代码应该是独立的;它将生成m= 50,000个观测值,其中包含n=150个要素。将m设置为小于43,500时,应返回“Percent class 1:0.250000”,设置为44,000或以上将返回“百分比类1:0.000000”,而不管max_iter(我们对m个观测进行采样的次数)被设置为多少。
如果类为0(前75%的观测),则第一个要素设置为1.0除以观测总数,否则设置为观测的索引除以观测总数。
第二个特征是指数除以观测总数。
所有其他特征都是随机的。
逻辑回归旨在使用随机梯度下降、随机选择观察指标、使用当前权重计算具有预测y的损失的梯度、以及利用梯度和学习率(eta)更新权重。
对Python和NumPy使用相同的初始化,即使超过50,000个观测值,我仍然可以得到正确的结果。

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

// Compute z = w * x + b
double dlc( int n, double *X, double *coef, double intercept )
{
    double y_pred = intercept;
    for (int i = 0; i < n; i++)
    {
        y_pred += X[i] * coef[i];
    }
    return y_pred;
}

// Compute y_hat = 1 / (1 + e^(-z))
double sigmoid( int n, double alpha, double *X, double *coef, double beta, double intercept )
{
    double y_pred;
    y_pred = dlc(n, X, coef, intercept);
    y_pred = 1.0 / (1.0 + exp(-y_pred));

    return y_pred;
}

// Stochastic gradient descent
void sgd( int m, int n, double *X, double *y, double *coef, double *intercept, double eta, int max_iter, int fit_intercept, int random_seed )
{
    double *gradient_coef, *X_i;
    double y_i, y_pred, resid;
    int idx;

    double gradient_intercept = 0.0, alpha = 1.0, beta = 1.0;

    X_i = (double *) malloc (n * sizeof(double));
    gradient_coef = (double *) malloc (n * sizeof(double));

    for ( int i = 0; i < n; i++ )
    {
        coef[i] = 0.0;
        gradient_coef[i] = 0.0;
    }
    *intercept = 0.0;

    srand(random_seed);
    
    for ( int epoch = 0; epoch < max_iter; epoch++ )
    {
        for ( int run = 0; run < m; run++ )
        {
            // Randomly sample an observation
            idx = rand() % m;
            for ( int i = 0; i < n; i++ )
            {
                X_i[i] = X[n*idx+i];
            }
            y_i = y[idx];
            // Compute y_hat
            y_pred = sigmoid( n, alpha, X_i, coef, beta, *intercept );
            resid = -(y_i - y_pred);
            // Compute gradients and adjust weights
            for (int i = 0; i < n; i++)
            {
                gradient_coef[i] = X_i[i] * resid;
                coef[i] -= eta * gradient_coef[i];
            }
            if ( fit_intercept == 1 )
            {
                *intercept -= eta * resid;
            }
        }
    }
}

int main(void)
{
    double *X, *y, *coef, *y_pred;
    double intercept;
    double eta = 0.05;
    double alpha = 1.0, beta = 1.0;
    long m = 50000;
    long n = 150;
    int max_iter = 20;

    long class_0 = (long)(3.0 / 4.0 * (double)m);
    double pct_class_1 = 0.0;

    clock_t test_start;
    clock_t test_end;
    double test_time;

    printf("Constructing variables...\n");
    X = (double *) malloc (m * n * sizeof(double));
    y = (double *) malloc (m * sizeof(double));
    y_pred = (double *) malloc (m * sizeof(double));
    coef = (double *) malloc (n * sizeof(double));

    // Initialize classes
    for (int i = 0; i < m; i++)
    {
        if (i < class_0)
        {
            y[i] = 0.0;
        }
        else
        {
            y[i] = 1.0;
        }
    }

    // Initialize observation features
    for (int i = 0; i < m; i++)
    {
        if (i < class_0)
        {
            X[n*i] = 1.0 / (double)m;
        }
        else
        {
            X[n*i] = (double)i / (double)m;
        }
        X[n*i + 1] = (double)i / (double)m;
        for (int j = 2; j < n; j++)
        {
            X[n*i + j] = (double)(rand() % 100) / 100.0;
        }
    }

    // Fit weights
    printf("Running SGD...\n");
    test_start = clock();
    sgd( m, n, X, y, coef, &intercept, eta, max_iter, 1, 42 );
    test_end = clock();
    test_time = (double)(test_end - test_start) / CLOCKS_PER_SEC;
    printf("Time taken: %f\n", test_time);

    // Compute y_hat and share of observations predicted as class 1
    printf("Making predictions...\n");
    for ( int i = 0; i < m; i++ )
    {
        y_pred[i] = sigmoid( n, alpha, &X[i*n], coef, beta, intercept );
    }

    printf("Printing results...\n");
    for ( int i = 0; i < m; i++ )
    {
        //printf("%f\n", y_pred[i]);
        if (y_pred[i] > 0.5)
        {
            pct_class_1 += 1.0;
        }
        // Troubleshooting print
        if (i < 10 || i > m - 10)
        {
            printf("%g\n", y_pred[i]);
        }
    }
    printf("Percent class 1: %f", pct_class_1 / (double)m);

    return 0;
}

作为参考,下面是我的(大概)等价Python代码,它在超过50,000次观察时返回正确的类百分比:

import numpy as np
import time

def sigmoid(x):
    return 1 / (1 + np.exp(-x))

class LogisticRegressor:
    def __init__(self, eta, init_runs, fit_intercept=True):
        self.eta = eta
        self.init_runs = init_runs
        self.fit_intercept = fit_intercept
    
    def fit(self, x, y):
        m, n = x.shape
        self.coef = np.zeros((n, 1))
        self.intercept = np.zeros((1, 1))
        
        for epoch in range(self.init_runs):
            for run in range(m):
                idx = np.random.randint(0, m)
                x_i = x[idx:idx+1, :]
                y_i = y[idx]
                y_pred_i = sigmoid(x_i.dot(self.coef) + self.intercept)
                gradient_w = -(x_i.T * (y_i - y_pred_i))
                self.coef -= self.eta * gradient_w
                if self.fit_intercept:
                    gradient_b = -(y_i - y_pred_i)
                    self.intercept -= self.eta * gradient_b
        
    def predict_proba(self, x):
        m, n = x.shape
        y_pred = np.ones((m, 2))
        y_pred[:,1:2] = sigmoid(x.dot(self.coef) + self.intercept)
        y_pred[:,0:1] -= y_pred[:,1:2]
        return y_pred
    
    def predict(self, x):
        return np.round(sigmoid(x.dot(self.coef) + self.intercept))
    

m = 50000
n = 150
class1 = int(3.0 / 4.0 * m)

X = np.random.rand(m, n)
y = np.zeros((m, 1))

for obs in range(m):
    if obs < class1:
        continue
    else:
        y[obs,0] = 1

for obs in range(m):
    if obs < class1:
        X[obs, 0] = 1.0 / float(m)
    else:
        X[obs, 0] = float(obs) / float(m)
    X[obs, 1] = float(obs) / float(m)

logit = LogisticRegressor(0.05, 20)
start_time = time.time()
logit.fit(X, y)
end_time = time.time()
print(round(end_time - start_time, 2))
y_pred = logit.predict(X)
print("Percent:", y_pred.sum() / len(y_pred))
w46czmvw

w46czmvw1#

问题就在这里:

// Randomly sample an observation
            idx = rand() % m;

......鉴于运算符的RAND_MAX为32767。由于所有0类观测都在末尾,这一情况更加严重。
所有样本都将从前32768个观测中抽取,当观测总数大于该值时,0类观测 * 在可抽样观测 * 中所占的比例小于0.25。当观测总数为43691个时,可抽样观测中没有0类观测。
作为第二个问题,如果m不能均匀地划分RAND_MAX + 1,则rand() % m不会产生完全均匀的分布,尽管这个问题的影响要微妙得多。

    • 底线**:你需要一个更好的随机数生成器。

至少,您可以考虑将两次rand()调用中的位组合起来,以生成一个范围足够大的整数,但您可能需要考虑使用第三方生成器,有几种可用的生成器。

11dmarpk

11dmarpk2#

注:OP报告“m= 50,000个观察结果,n=150个特征",所以这可能不是OP的问题,但我会在OP尝试更大的任务时留下这个答案作为参考。
潜在问题:

long溢出

long为32位且m*n > LONG_MAX(或如果m, n相同,则约为46,341)时,m * n * sizeof(double)有溢出的风险。
OP未报告
第一步是使用size_t数学执行乘法,其中我们在计算中至少多获得1位。

// m * n * sizeof(double)
sizeof(double) * m * n

然而,除非OP的size_t超过32位,否则我们仍然会遇到麻烦。
IAC,我建议使用size_t来调整数组大小和索引。
检查分配是否失败。

3duebb1j

3duebb1j3#

由于RAND_MAX可能是too small,并且数组索引应该使用size_t数学来完成,因此考虑使用帮助器函数来生成整个size_t范围上的随机索引。

// idx = rand() % m;
size_t idx = rand_size_t() % (size_t)m;

如果坚持使用标准的rand(),下面是一个帮助函数,可以根据需要扩展它的范围。
它使用了真实的漂亮的IMAX_BITS(m)

#include <assert.h>
#include <limits.h>
#include <stdint.h>
#include <stdlib.h>

// https://stackoverflow.com/a/4589384/2410359
/* Number of bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 2040 */
#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))

// Test that RAND_MAX is a power of 2 minus 1
_Static_assert((RAND_MAX & 1) && ((RAND_MAX/2 + 1) & (RAND_MAX/2)) == 0, "RAND_MAX is not a Mersenne number");

#define RAND_MAX_WIDTH (IMAX_BITS(RAND_MAX))
#define SIZE_MAX_WIDTH (IMAX_BITS(SIZE_MAX))

size_t rand_size_t(void) {
  size_t index = (size_t) rand();
  for (unsigned i = RAND_MAX_WIDTH; i < SIZE_MAX_WIDTH; i += RAND_MAX_WIDTH) {
      index <<= RAND_MAX_WIDTH;
      index ^= (size_t) rand();
  }
  return index;
}

进一步考虑可以用更高的uniform distribution替换rand_size_t() % (size_t)m

vxbzzdmp

vxbzzdmp4#

正如在其他地方所确定的,问题是由于实现的RAND_MAX值太小。
假设int为32位,则可以在代码中实现一个稍好的PRNG函数,例如以下来自C++的minstd_rand()函数的C实现:

#define MINSTD_RAND_MAX 2147483646

// Code assumes `int` is at least 32 bits wide.

static unsigned int minstd_seed = 1;

static void minstd_srand(unsigned int seed)
{
    seed %= 2147483647;
    // zero seed is bad!
    minstd_seed = seed ? seed : 1;
}

static int minstd_rand(void)
{
    minstd_seed = (unsigned long long)minstd_seed * 48271 % 2147483647;
    return (int)minstd_seed;
}

另一个问题是,当m不能除(unsigned int)RAND_MAX + 1时,rand() % m形式的表达式会产生一个有偏差的结果。下面是一个无偏差函数,它使用前面定义的minstd_rand()函数返回0到le之间的随机整数:

static int minstd_rand_max(int le)
{
    int r;

    if (le < 0)
    {
        r = le;
    }
    else if (le >= MINSTD_RAND_MAX)
    {
        r = minstd_rand();
    }
    else
    {
        int rm = MINSTD_RAND_MAX - le + MINSTD_RAND_MAX % (le + 1);

        while ((r = minstd_rand()) > rm)
        {
        }
        r /= (rm / (le + 1) + 1);
    }
    return r;
}

(实际上,它仍然有一个非常小的偏差,因为minstd_rand()永远不会返回0。)
例如,将rand() % 100替换为minstd_rand_max(99),将rand() % m替换为minstd_rand_max(m - 1),还将srand(random_seed)替换为minstd_srand(random_seed)

相关问题