[Boost-bugs] [Boost C++ Libraries] #12688: Boost..Accumulators test/median.cpp testing method is flawed

Subject: [Boost-bugs] [Boost C++ Libraries] #12688: Boost..Accumulators test/median.cpp testing method is flawed
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2016-12-14 12:25:18

#12688: Boost..Accumulators test/median.cpp testing method is flawed
-------------------------------------------------+-------------------------
 Reporter:  A. Sinan Unur <sinan@…>              |      Owner:
     Type:  Bugs                                 |  eric_niebler
Milestone:  To Be Determined                     |     Status:  new
  Version:  Boost 1.62.0                         |  Component:  accumulator
 Keywords:  testing, median, algorithm,          |   Severity:  Problem
  accumulator                                    |
-------------------------------------------------+-------------------------
 I am going to stick with Stats terminology, because I get confused. I am
 going to use the word ''sample'' to mean a collection of data points or
 draws or observations, not a single one.

 1. In the test, you generate a sample of 100,000 observations from N(1,1),
 and check if the medians computed by the implementations are close enough
 to the true population median of 1.

 That is flawed: The algorithms are for calculating the median of the set
 of numbers you have. Therefore, the medians they produce should be
 compared to the actual median of the sample you just generated. The median
 of that sample can be obtained by storing the draws in a `vector` and
 getting the exact median from that.

 This is not hard to do. I am not, however, submitting a pull request to do
 that because I am not convinced this approach is the right way to test the
 algorithms.

 2. In the case of P^2^, the original paper contains a worked-out example
 by the authors using 20 observations. They show exactly what the algorithm
 should produce at each step. Your implementation does not match those
 steps.

 The following short program demonstrates this:

 {{{
 #include <algorithm>
 #include <iostream>
 #include <string>
 #include <utility>
 #include <vector>
 #include <boost/accumulators/accumulators.hpp>
 #include <boost/accumulators/statistics/stats.hpp>
 #include <boost/accumulators/statistics/median.hpp>

 namespace bacc = boost::accumulators;

 int main(void)
 {
     bacc::accumulator_set<double,
         bacc::stats<bacc::tag::median(bacc::with_p_square_quantile)> >
 acc;

     // See http://www.cse.wustl.edu/~jain/papers/psqr.htm


     // First five observations
     acc(0.02);
     acc(0.5);
     acc(0.74);
     acc(3.39);
     acc(0.83);

     const std::vector<std::pair<double, double> > jain_chlamtac {
         { 22.37, 0.74 },
         { 10.15, 0.74 },
         { 15.43, 2.18 },
         { 38.62, 4.75 },
         { 15.92, 4.75 },
         { 34.60, 9.28 },
         { 10.28, 9.28 },
         {  1.47, 9.28 },
         {  0.40, 9.28 },
         {  0.05, 6.30 },
         { 11.39, 6.30 },
         {  0.27, 6.30 },
         {  0.42, 6.30 },
         {  0.09, 4.44 },
         { 11.37, 4.44 },
     };

     for (auto p: jain_chlamtac)
     {
         acc(p.first);
         std::cout << "calculated= " << bacc::median(acc)
             << "\texpected= " << p.second << '\n';
     }

     return 0;
 }
 }}}

 This produces

 {{{
 calculated= 0.74        expected= 0.74
 calculated= 0.74        expected= 0.74
 calculated= 2.06167     expected= 2.18
 calculated= 4.55176     expected= 4.75
 calculated= 4.55176     expected= 4.75
 calculated= 9.15196     expected= 9.28
 calculated= 9.15196     expected= 9.28
 calculated= 9.15196     expected= 9.28
 calculated= 9.15196     expected= 9.28
 calculated= 6.17976     expected= 6.3
 calculated= 6.17976     expected= 6.3
 calculated= 6.17976     expected= 6.3
 calculated= 6.17976     expected= 6.3
 calculated= 4.24624     expected= 4.44
 calculated= 4.24624     expected= 4.44
 }}}

 More a more detailed exposition, see my blog post
 https://www.nu42.com/2016/12/cpp-boost-median-test.html


 This is the first time I am looking at Boost.Accumulators and I haven't
 figured out everything yet, so I do not have a fix (and I can't promise I
 am going to have a fix soon), but I thought I would get the ball rolling.
 Maybe the issue will be more transparent to you.

 To summarize:

 1. The implementations should be tested against cases where we know what
 they are supposed to do.

 2. It looks like there is a problem in the implementation of the P^2^
 algorithm.

 HTH,

 -- Sinan

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/12688>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.