Multilabel Classification - increasing the confidence
It's hard to say without knowing the data.

Often times the classes are imbalanced. This could cause your problems.
So let's say that the "features are right" for 5% of your data and they belong to class $A$. You would expect the 5% to be classified correctly as $A$ almost all the time. But what about the remaining 95% in class $B$? The classifier learns that it would be often correct if the sample is classified as $B$. This leads to a low classification rate for class $A$.

You can tackle this by setting different miss-classification costs for the classes. Often you multiply the error rate by these costs to scale them accordingly. Some classifiers let you set this during training.

The standard case would be as follows:

$$C = \left( \begin{matrix}
0 &amp; 1  \\
1 &amp; 0  \\
\end{matrix} \right)$$

Meaning that correct classification (diagonal) is not punished and miss-classifying $A$ as $B$ and vice versa is punished in the same way. However, this assumes uniformly distributed classes. To account for the case explained above, you may set it the following way:

$$C = \left( \begin{matrix}
0 &amp; 0.05  \\
0.95 &amp; 0  \\
\end{matrix} \right)$$

Here i set it as the inverse of the class distribution. However, you may try different settings.