Programming
Algorithms
Mathematics
Machine learning
Comments 9
0
Спасибо за статью, я внезапно осознал, что у меня-то тоже целая куча данных, а ошибку я никак не учитываю.
+1

Спасибо, хорошая статья, и напоминание про подобные грабли (на примере наивного подхода) не лишнее.


Сам такой подход люблю, особенно для сглаживающих цифровых фильтров (когда разрядов мало), но не знал названия.


Однако же попробуйте метод (для float) на последовательности из миллиона единиц, потом миллион двоек…
Ну или более реальный случай — миллион чисел, плавно растущих от 1 до 2.

0

Отличный пример, спасибо! Действительно, можно "сломать" метод, если разрядности не хватает для представления результата суммирования с нормированной разностью. В такой ситуации можно было бы использовать счётчик Кахана внутри метода Уэлфорда. Но я бы не стал рекомендовать такой способ в качестве стандартного, т.к. очень уж большие накладные расходы.


А какой метод используете вы в описанной ситуации?

0
счётчик Кахана

А что это за зверь, если не секрет? Гугл не помогает.
0
Сама эта тема оказалась настолько для меня интересной, что я потом даже диссертацию про это написал.

По ссылке ожидал увидеть PDF, но не 120-мегабайтный архив с чем-то, похожим на профиль браузера вместе с кешем. Это точно именно то, что вы имели в виду?

0
Не впечатлил что-то ваш Уэлфорд.
code
void perr(const std::string& type, double v, double u) {
  double abs_e = std::abs(v - u);
  std::cout << type << " abs: " << abs_e << " rel: " << abs_e / u << std::endl;
};

void test_m(const size_t n = 100000000, double from = 128, double step = 1) {
  double m = from + step * (n - 1) / (2 * n);
  MeanDummy m0;
  MeanKahan m1;
  MeanWelford m2;
  for (size_t i = 0; i < n; ++i) {
    double v = from + i * step / n;
    m0.add(v);
    m1.add(v);
    m2.add(v);
  }
  std::cout << "test mean\n";
  perr("Dummy", m0.mean(), m);
  perr("Kahan", m1.mean(), m);
  perr("Welford", m2.mean(), m);
}

void test_c(const size_t n = 100000000, double from0 = 128, double step0 = 3, double from1 = 32, double step1 = 2) {
  double c = step0 * step1 / 12 * (1 - 1.0/(n * n));
  CovariationDummy c0;
  CovariationKahan c1;
  CovariationWelford c2;
  CovariationWelford2 c3;
  CovariationWelfordKahan c4;
  for (size_t i = 0; i < n; ++i) {
    double v = from0 + i * step0 / n;
    double u = from1 + i * step1 / n;
    c0.add(v, u);
    c1.add(v, u);
    c2.add(v, u);
    c3.add(v, u);
    c4.add(v, u);
  }
  std::cout << "test covariation\n";
  perr("Dummy", c0.covariation(), c);
  perr("Kahan", c1.covariation(), c);
  perr("Welford", c2.covariation(), c);
  perr("Welford2", c3.covariation(), c);
  perr("WelfordKahan", c4.covariation(), c);
}


test mean
Dummy abs: 2.84217e-14 rel: 2.21181e-16
Kahan abs: 0 rel: 0
Welford abs: 3.96642e-07 rel: 3.0867e-09
test covariation
Dummy abs: 1.55029e-10 rel: 3.10059e-10
Kahan abs: 6.10456e-13 rel: 1.22091e-12
Welford abs: 1.18424e-07 rel: 2.36848e-07
Welford2 abs: 1.18424e-07 rel: 2.36848e-07
WelfordKahan abs: 0 rel: 0
Only those users with full accounts are able to leave comments. , please.