Computing the Mean Average Precision

Question

I've read this article about Mean Average Precision (MAP).

Now, in my C++ code I have an std::vector<std::string> queries, where queries[i] is the identifier of the i-th query.

In addition, I have a std::vector<std::vector<std::string> truePositives where truePositives[i][z] is the z-th true positive correspondent to the i-th query. Since the actual order in truePositives[i] isn't important, I could have used std::vector<std::set<std::string>>, but whatever...

Finally, I have a std::vector<std::string> topkTest where topkTest[j] is the j-th element in the top-k ranked list returned by the system for the given query, where k = min(data set size, 10k) (following the suggestion in this question).

Here you can find my code to compute the MAP. I post it here because there is no actual way to say if the returned result (the map value) is correct or not.

    float map = 0;
    for(size_t i=0; i<queries.size(); i++){
        std::vector<std::string> topkTest;
        //populate topkTest somehow using k
        float correct = 0;
        float ap = 0;
        for(size_t j=0; j<topkTest.size(); j++){
            //if topkTest[j] belongs to the true positives, increment the number of correct images
            if(std::find(truePositives.begin(), truePositives.end(), topkTest[j]) != queries.end())
                ap += ++correct / (j+1);
        map += ap / topkTest.size();
    }
    map /= queries.size(),

What do you think about this?

Answer 1

The equation for computing the mean average precision (MAP) is shown below:

$$ \text{MAP}(Q) = \frac{1}{\lvert Q \rvert} \sum_{j=1}^{\lvert Q \rvert}\frac{1}{m_j} \sum_{k=1}^{m_j} \text{Precision}(R_{jk}) $$

The inner summation is something that we need to focus on. The outer summation is simply an average over the queries of the inner sum. The inner summation calculates point-wise precision values at the recall points. A recall point is defined as a position in the ranked list which retrieves a relevant document. Note that this quantity is divided by the total number of relevant documents for the jth query denoted by \$m_j\$, which adds the recall factor in an otherwise precision oriented metric.

Coming back to your code, you should thus change the following line

map += ap / topkTest.size();

to

map += ap / truePositives.size();

The rest of the code is okay.

Answer 2

It's hard to review this snippet alone; reviews are easier if you present a complete compilable function, and ideally a full program including a main() to exercise the code. But I'll have a go.

Perform intermediate calculations in wider types

Because map is declared as float rather than double, we accumulate rounding errors much faster than we need to. I would write

double map;
//...
return static_cast<float>(map);

Separate computing the mean from computing the precisions

Computing a mean of values is a reusable operation we may well want to use elsewhere, so try not to entangle it with the calculation of "precision" values. It may well be worth writing a small class to accumulate a mean - see next item, and we probably want to write a small function to calculate the precision. A great benefit of this is that the two operations can be tested independently, making it easier to isolate and identify any bugs.

Improve the numerical stability

Although it seems intuitively obvious to calculate a mean value by summing all items and then dividing by the total, this isn't the most precise way to achieve it. It's actually more accurate to keep the running average and count of elements, rather than the total and count:

class Mean
{
    double mean = 0;
    unsigned long count = 0;
public:
    double insert(double value) {
        return mean += (value - mean) / ++count;
    }
}

(algorithm taken from Incremental calculation of weighted mean and variance by Tony Finch)

Optimise truePositives for search

We're calling std::find() in the inner loop; this performs a linear search of the vector. You've hinted in your description that you could use a sorted container such as std::set, and I strongly recommend you do so. I expect you'll see a measurable improvement in speed.