# Classification accuracy of a Random Multi-label Classifier

What is the exact accuracy of a random classifier which has n labels (say 1000) where k labels (say 50) are true? Can I say the accuracy of a random classifier has an upper bound of k/n?

-Edit-

I am interested in a numerical figure or an upper bound for a random classifier (for example the accuracy of a classifier randomly picking 50 classes out of 1000 where some 50 classes are correct). Sorry if my previous question is not fully understood.

I'll assume you want accuracy as @AlexanderRoiatchki defined it (see also CV.SE), and want exactly $$k$$ distinct labels, both true and predicted.

Letting $$X$$ denote the random variable of the number of correct labels for an instance, we have that $$\mathbb{P}(X=x) = \binom{k}{x} \binom{n-k}{k-x} / \binom{n}{k}$$ (choose the correct labels and the incorrect ones separately). The accuracy score from a given instance is $$\frac{|T_i \cap P_i| }{ |T_i \cup P_i| } = \frac{ X}{2k-X}.$$

So the expected value of the accuracy is $$\mathbb{E}\left[\frac{X}{2k-X}\right] = \frac{1}{\binom{n}{k}} \sum_{x=0}^k \frac {x \binom{k}{x} \binom{n-k}{k-x}} {2k-x}.$$ That doesn't seem to have a nice closed form. When $$k\ll \sqrt{n}$$, this seems to be roughly $$k/2n$$, but I've made a big assumption about the non-dominating terms of the summation being negligible.

In the specific case you mentioned, $$k=50, n=1000$$, I get 0.0259.

Edit, in response to comment: if you want to define accuracy as just $$X/k$$, then the expected accuracy of the random classifier simplifies nicely to $$k/n$$:

\begin{align*} \frac{1}{\binom{n}{k}} \sum_{x=0}^k \frac{x}{k} \binom{k}{x} \binom{n-k}{k-x} &= \frac{1}{k\binom{n}{k}} \left( k \binom{n-1}{k-1} \right) & \text{combinatorial identity*} \\ &= \frac{ (n-1)! / [(k-1)! (n-k)!] }{ n! / [k! (n-k)!] } & \text{just expand coefficients}\\ &= \frac{k}{n} & \text{simplify factorials} \end{align*}

(* I can't help but elaborate. In the current context, this is the number of choices with $$X=x$$ with the additional decoration of a special correct label (one of the $$x$$). To get the RHS then, pick the decorated label first ($$k$$), then choose the remaining labels without regard to how many are correct ($$\binom{n-1}{k-1}$$). )

• Thanks a lot @ben :D I am taking the accuracy as X/ k as I always select top 50 probable values. Anyway got the answer to the question, thanks a lot again :D Commented Dec 1, 2019 at 19:50
• the expected value should be divided by the nCk, shouldn't it? Commented Dec 1, 2019 at 19:52
• @Wenuka, thanks, of course I missed the nCk; I'll edit it in. Also, with accuracy defined as just X/k things do simplify nicely, so I'll add that. Commented Dec 2, 2019 at 3:27

In the context of a multi-label classifier (that is, having potentially more than one label per data point) we can have a prediction which is either fully correct, partially correct or fully incorrect. To account for this, the following accuracy metric has been proposed: $$\text{Accuracy} = \frac{1}{n}\sum_{i=1}^n\frac{|T_i \cap P_i|}{|T_i\cup P_i|},$$ where $$n$$ is the sample size, $$|\cdot|$$ denotes the number of elements of a set, $$T_i$$ is the set of true labels and $$P_i$$ is the set of predicted labels for an item of the sample.

For instance, let's say the $$i$$-th item has actual labels $$A, B, C$$ and $$D$$ (that is $$T_i = \{A, B, C, D\}$$, but your classifier predicts labels $$B, D$$ and $$E$$ (that is $$P_i =\{B, D, E\}$$), then you'd get $$\frac{|T_i\cap P_i|}{|T_i\cup P_i|}=\frac{|\{B,D\}|}{|\{A,B,C,D,E\}|}=\frac{2}{5}.$$ To get the accuracy for the entire training set, you calculate this for each instance $$i=1,\dots, n$$ and you average it out.

You can also have a look at the evaluation metrics section of the article in Wikipedia about multi-label classifiers: https://en.wikipedia.org/wiki/Multi-label_classification#Statistics_and_evaluation_metrics

• Thank you @alexander :D However can you help me with "how to obtain a numerical figure" or at least an upper bound for a "random classifier" (a classifier just randomly picking classes)? Commented Nov 25, 2019 at 10:21