mAP: reflesh

Assume that we want to estimate an unobserved population parameter ${\displaystyle \theta }$ on the basis of observations ${\displaystyle x}$. Let ${\displaystyle f}$ be the sampling distribution of ${\displaystyle x}$, so that ${\displaystyle f(x\mid \theta )}$ is the probability of ${\displaystyle x}$ when the underlying population parameter is ${\displaystyle \theta }$. Then the function:

${\displaystyle \theta \mapsto f(x\mid \theta )\!}$

is known as the likelihood function and the estimate:

${\displaystyle {\hat {\theta }}_{\mathrm {ML} }(x)={\underset {\theta }{\operatorname {arg\,max} }}\ f(x\mid \theta )\!}$

is the maximum likelihood estimate of ${\displaystyle \theta }$.

Now assume that a prior distribution ${\displaystyle g}$ over ${\displaystyle \theta }$ exists. This allows us to treat ${\displaystyle \theta }$ as a random variable as in Bayesian statistics. We can calculate the posterior distributionof ${\displaystyle \theta }$ using Bayes' theorem:

${\displaystyle \theta \mapsto f(\theta \mid x)={\frac {f(x\mid \theta )\,g(\theta )}{\displaystyle \int _{\Theta }f(x\mid \vartheta )\,g(\vartheta )\,d\vartheta }}\!}$

where ${\displaystyle g}$ is density function of ${\displaystyle \theta }$, ${\displaystyle \Theta }$ is the domain of ${\displaystyle g}$.

The method of maximum a posteriori estimation then estimates ${\displaystyle \theta }$ as the mode of the posterior distribution of this random variable:

${\displaystyle {\hat {\theta }}_{\mathrm {MAP} }(x)={\underset {\theta }{\operatorname {arg\,max} }}\ f(\theta \mid x)={\underset {\theta }{\operatorname {arg\,max} }}\ {\frac {f(x\mid \theta )\,g(\theta )}{\displaystyle \int _{\Theta }f(x\mid \vartheta )\,g(\vartheta )\,d\vartheta }}={\underset {\theta }{\operatorname {arg\,max} }}\ f(x\mid \theta )\,g(\theta ).\!}$

The denominator of the posterior distribution (so-called marginal likelihood) is always positive and does not depend on ${\displaystyle \theta }$ and therefore plays no role in the optimization. Observe that the MAP estimate of ${\displaystyle \theta }$ coincides with the ML estimate when the prior ${\displaystyle g}$ is uniform (that is, a constant function).

When the loss function is of the form

${\displaystyle L(\theta ,a)={\begin{cases}0,&{\text{if }}|a-\theta |<c,\\1,&{\text{otherwise}},\\\end{cases}}}$

Suppose you are answering the questions, if you are right you will get one point, otherwise zero.  If our returned result is
1, 0, 0, 1, 1, 1
So your AP calculation looks like this:   1/1, 0, 0, 2/4, 3/5, 4/6

The AP for above example is 0.6917

Average precision[edit]

Precision and recall are single-value metrics based on the whole list of documents returned by the system. For systems that return a ranked sequence of documents, it is desirable to also consider the order in which the returned documents are presented. By computing a precision and recall at every position in the ranked sequence of documents, one can plot a precision-recall curve, plotting precision ${\displaystyle p(r)}$ as a function of recall ${\displaystyle r}$. Average precision computes the average value of ${\displaystyle p(r)}$ over the interval from ${\displaystyle r=0}$ to ${\displaystyle r=1}$:^[9]

${\displaystyle \operatorname {AveP} =\int _{0}^{1}p(r)dr}$

That is the area under the precision-recall curve. This integral is in practice replaced with a finite sum over every position in the ranked sequence of documents:

${\displaystyle \operatorname {AveP} =\sum _{k=1}^{n}P(k)\Delta r(k)}$

where ${\displaystyle k}$ is the rank in the sequence of retrieved documents, ${\displaystyle n}$ is the number of retrieved documents, ${\displaystyle P(k)}$ is the precision at cut-off ${\displaystyle k}$ in the list, and ${\displaystyle \Delta r(k)}$ is the change in recall from items ${\displaystyle k-1}$ to ${\displaystyle k}$.^[9]

This finite sum is equivalent to:

${\displaystyle \operatorname {AveP} ={\frac {\sum _{k=1}^{n}(P(k)\times \operatorname {rel} (k))}{\mbox{number of relevant documents}}}\!}$

where ${\displaystyle \operatorname {rel} (k)}$ is an indicator function equaling 1 if the item at rank ${\displaystyle k}$ is a relevant document, zero otherwise.^[10] Note that the average is over all relevant documents and the relevant documents not retrieved get a precision score of zero.

Some authors choose to interpolate the ${\displaystyle p(r)}$ function to reduce the impact of "wiggles" in the curve.^[11][12] For example, the PASCAL Visual Object Classes challenge prior to 2010 (a benchmark for computer vision object detection, the evaluation metric changed after 2010 to effectively sample the curve at all unique recall values.) computes average precision by averaging the precision over a set of evenly spaced recall levels {0, 0.1, 0.2, ... 1.0}:^[11][12]

${\displaystyle \operatorname {AveP} ={\frac {1}{11}}\sum _{r\in \{0,0.1,\ldots ,1.0\}}p_{\operatorname {interp} }(r)}$

where ${\displaystyle p_{\operatorname {interp} }(r)}$ is an interpolated precision that takes the maximum precision over all recalls greater than ${\displaystyle r}$:

${\displaystyle p_{\operatorname {interp} }(r)=\operatorname {max} _{{\tilde {r}}:{\tilde {r}}\geq r}p({\tilde {r}})}$.

An alternative is to derive an analytical ${\displaystyle p(r)}$ function by assuming a particular parametric distribution for the underlying decision values. For example, a binormal precision-recall curve can be obtained by assuming decision values in both classes to follow a Gaussian distribution.^[13]

Mean average precision[edit]

Mean average precision for a set of queries is the mean of the average precision scores for each query.

${\displaystyle \operatorname {MAP} ={\frac {\sum _{q=1}^{Q}\operatorname {AveP(q)} }{Q}}\!}$

where Q is the number of queries.