How to identify if a problem is a good candidate for applying machine learning? Specifically, I am talking about supervised learning. It seems that a problem is a good candidate for applying ML if:


*

*We have fairly high-accuracy ground-truth labels in our dataset. The dataset is randomly sampled from the underlying distribution and uniformly labelled. 

*The distribution from which the data is sampled stays relatively constant; the model will be applied to data sampled from the same distribution. In other words, the function we are trying to learn stays constant.

*The output we are trying to learn is actually a function of the inputs we are given.

*The effective number of independent samples in our dataset is high enough for the levels of noise in the dataset (sources of noise are noise in the inputs, noise in the labels, covariate shifts) and for the complexity of the relationships we are trying to model.

*The metric we would like our model to optimize is quantifiable.


Would that be accurate? Should anything be added to this list or changed in it?
 A: Prof. Yaser Abu-Mostafa talks briefly about this in his Caltech course on machine learning during the first lecture. He identifies 3 essential points you have to consider before considering applying machine learning to your problem:
1st. a pattern exists
In order to be able to use your features for predicting anything there has to be some relationship between those features and the thing you are predicting.
An example of this might be trying to predict the persons height by using data about what he ate yesterday. There is probably no relation between these two so machine learning wouldn't apply.
2nd. the pattern cannot be written down mathematically
If you can solve the relation between input variables and prediction using a mathematical formula then there is no need to apply machine learning.
Example of this point might be using machine learning in trying to predict the odds in a game of roulette. You can do that by calculating all the probabilities using equations from probability theory. The calculated odds would be exact and machine learning would only produce less reliable solutions.
3rd. you have data
Machine learning tries to estimate parameters based on examples. And without data you cannot start using machine learning.
Example of this might be trying to predict who will win a war by using various data about political climate, technology each side has, the spending on military, etc. If you had data for a lot of wars you might be able to do this. But since wars are pretty rare and there is no way to produce more of it on demand - machine learning will not work.

These are the main requirements - the essence of machine learning.
Briefly the examples in the question:
1) We have fairly high-accuracy ground-truth labels in our dataset.
This seems highly subjective and context dependant. Consider predicting the age of death for a person, when the data you have only has "a best guess" from their doctor. The data would be very noisy, but if we can reduce the unknown factor by 5% or so after applying machine learning - it might be worth while: the algorithm would be as good as the guess by professional.
2) The distribution from which the data is sampled stays relatively constant.
This is not a hard requirement. There is a sub area of machine learning that tries to deal with problems like these, called Concept Drift
3) The output we are trying to learn is actually a function of the inputs we are given.
This is same as the 1st one mentioned by prof. Abu-Mostafa. That the "Pattern Exists".
4) The effective number of independent samples in our dataset is high enough for the levels of noise in the dataset.
This is very relevant but at the same time subjective, just like the 1st point mentioned in the question. For some problems improvement of a few percent might be considered good enough.
5) The metric we would like our model to optimize is quantifiable.
Not sure if I understand this one. From the comments it seems it is talking about comparison of different solutions in order to select the better one. I cannot quickly think of a scenario where this would not be satisfied. Unless the practitioner doesn't really have a clear goal in mind.
A: I would consider updating #5, as quantifiable metrics are not necessarily easy to optimize. For instance, directly optimizing 0-1 loss is NP-hard. So #5 could instead say:


*The metric we would like our model to optimize is quantifiable and is feasibly solvable (or has an appropriate surrogate).


Other than that, your list looks pretty good to me. I wish more people would sit down and have this conversation before applying machine learning to a problem!
A: 1-5 are ideal, but I do not believe are 100% required. Some will rightfully cringe at that sentence. The most important thing to remember is the "no free lunch theorem", which reminds us that ML is based on theories, hypotheses, and/or assumptions at every stage of the pipeline. We can only define whether ML will help us in our task if we assume that some set of input features are independent of our target (dependent variable). I won't make this an essay (nvm), so I'll comment on each item and add a few to your list. My answer is written as a discussion, not do's and don'ts. Please at least upvote if you find it helpful. (Disclaimer: All notes below were written with supervised ML in mind).
1) We must have some assumed ground truth, but we cannot always quantify accuracy of our labels. The labels may reflect perception and opinion (e.g. data came from human input) or unexplainable randomness from nature. Random and balanced sampling is preferred for fair experimental setup, but not required to use ML. Some algorithms can handle minority labels (e.g. by adding weights), although most will do poorly if you do not reasonably balance (up/down sample) the data. Some algorithms (e.g. Breiman's Random Forest and the derivative Extra Trees) are designed to be robust against unexplained variance and others (Logistic Regression and Naive Bayes) are designed to be probabilistic. 
2) In easier problems, the distribution of input/output will remain constant. In many hard problems, it is not. Image, audio, text and time series are great examples. Stock market predictions are heavily influenced by recent data and are not likely to respect the global distribution. That doesn't mean we can't make good predictions. e.g. Amazon stock has grown slightly faster than linear over the last 5 years and it will probably continue this rate of growth for a long while.  
3) Ideally, the target will completely depend on the input. For example, Y = f(x) = 2x+1. In reality, we are modeling something like Y = f(x,z) = 2x+1 + g(z), where z represents independent signals (just think of this as features if you are not sure what this means) that would explain the error of our model, but are not available and may only exist in theory (e.g. a person's thought process at an instance of time caused an action that effected the result of the target, i.e. string theory). It might be more correct to say that the input must have some correlation to the output and we will assume that the output is a function of the input.
4) Yes, good description. Simpler, we just need "enough" data to make a reasonable prediction. How much is enough? It could actually be five samples for all we know. If we create a learning curve and see that the performance meets our objective when we have N samples and is not much better with N+M samples, that is enough. There are many scenarios where we would like more data and it would make significant improvements in the result, but it's too expensive to either collect or to process. So in this case, the number of samples is also reflected by cost, even if that means our data science objective becomes extremely difficult. So the requirement comes down whether the output can be inferred from the input to some degree and we will assume that there is enough data because we want a system that quickly, cheaply, automatically and consistently does inference.
5) Yes and @schem is also right. The output must be somewhat measurable against our desired outcome, otherwise how do we optimize and know how well did we did? "Measurable" does not have to mean a numeric loss function by the way. I could make a loss function with fuzzy metrics that are ordinal, but not numeric, for example my not-fun-to-use  loss function outputs "the estimate is [too cold, cold, just right, hot, too hot]" or [good, ok, bad]. That is why I mean "somewhat measurable".
Added items:
6, 7, 8, ...)
Ideally, the cost (time, money, compute, ...) of building a ML solution and using it should be significantly less than humans or programming an explicit solution. The value to be achieved by deploying ML should improve quality, consistency or cost. You should read about the four V's (http://www.ibmbigdatahub.com/infographic/extracting-business-value-4-vs-big-data) and the absurd followup, the 42 V's (https://www.elderresearch.com/blog/42-v-of-big-data), which also has many good points related to this discussion. 
I'll edit this later as I remember what else I wanted to write. If this question is just for you, then I recommend reading a bit from the "Data Mining" book by Witten, Frank and Hall. It gives great discussion on this topic. If you will be making training material, giving a presentation or similar communications, I recommend simplifying this list a lot for a new to ML audience. A creative data scientist will deal with what they have, invent solutions (e.g. build logical simulations of the problem when you have too little data to directly use ML and use the available real data to validate the simulation exercise) and break the rules. Our assumptions, our satisfaction with experimental results and 5-8 govern whether ML was appropriate. The quality of the data is not super high importance * (grain of salt) if you remember the law of "garbage in, garbage out".
