Test how much randomness is in the dataset Given a labeled dataset, is there a way to quantify what percentage of the labels can be explained through the features?
(I guess I'm trying to see what is the best theoretical performance get be obtained using a machine learning model)

EDIT: For example, given the iris dataset, is it possible to tell what the highest possible classification accuracy is achievable? If a model classifies 80% of the test dataset correctly, is there a way to tell if further model improvements are possible?
 A: I agree that it will be a very useful thing to know beforehand while tackling a problem. For example, this would enable one to stop trying too hard after the learned model has already achieved the theoretical score.
However, such bounds may not be easy to find. Let's consider only those classifiers which given the same input at any different time give the same output. Normal ANNs, Logistic Classifier, SVMs all follow this rule and this is not really constraining the space of classifiers in any way. Further, say that the train data was actually the same as the test data. In such a case, the theoretical performance will be getting all the points right ($1.0$ accuracy) if all the points had at least one feature value different and some number smaller than $1.0$ if there were multiple points with the same coordinates (feature values) but belonging to different classes (possessing different labels). In most cases, if the test data and train data are the same, it would be possible to get an accuracy score of $\approx 1.0$ and that would be the theoretical bound
Like in most cases, however, if the test data is different from train data (but of course, the distribution is the same), depending on the distribution from which the training data was drawn, it might be possible to give a worst-case estimate of the accuracy. Consider the following example. Let us assume that a Neural Network is being used to train and is able to achieve a score of $1.0$ accuracy on the training data.

Say the training size was $11$ and is represented by green points and a test size of $5$ is being chosen. Assume that points from all the 16 grids are equally likely to be picked. So the probability of a point lying in a particular grid is $\frac{1}{16}$. Note that the colors do not represent classes, but the data distribution of two-dimensional features. Clearly, the data is not sufficiently manifested in the training data, something that should ideally not occur.
Worst case analysis
All 5 points in the test data lie in the red region and the Neural Network gets it wrong. The accuracy, in that case, will be $0.0$.
Expected Analysis
The probability of a point being in the red region is given by, $ \frac{Number\_ of\_ red}{Number\_ of\_ green} = \frac{5}{16}$. Thus the accuracy would be $1-\frac{5}{16}$, which his $\approx 0.68$
But to even make such an analysis, we need an access to the underlying probability distribution (without the labels nevertheless). But if we already have access to the underlying probability distribution, why classify? I hope the circularity is evident here.
As a few comments have pointed out, this is a hard problem in general, and intuitively it can be seen that it should be no easier than trying to learn the best classifier itself.
A: It is not possible, because there is (usually) no way to know what is the noise in your dataset. Dataset, noise (measurement errors) included, is your ground truth.
Even if your dataset was not noisy, it could be incomplete. Some important features might be missing. The distribution of data in a dataset might be different than in reality, too.
Having said that, it is worth to mention the classic bias-variance tradeoff concept. Getting familiar with this enables better understanding of what are the components of model error: https://theclevermachine.wordpress.com/2013/04/21/model-selection-underfitting-overfitting-and-the-bias-variance-tradeoff/
