Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
I understand how to test programs that are either right or wrong. But what if permissible some inaccuracy? How to distinguish a bug in the implementation of bad classifier? Naive solution (baseline)? But it seems that it will help to find the only really bad solution. I think you understand what I mean.
What are the ways of testing programs without the correct output?
For a known algorithm you can try testing against a reference implementation. Testing the implementation of a new algorithm is a tricky problem. If you have the resources you could develop 2 independent cleanroom implementations and test them against each other. A good option here is to develop a pedagogical implementation in a high level declarative language which is closer to the mathematical description & makes it easier to justify the correctness logically and a performance optimized implementation. Apart from the obvious benefits of having implementations optimized for these purposes, there is an additional benefit that by making the implementations more different, you increase the confidence in their correctness if they agree.
The other alternative is to construct toy training sets which exploit particular properties of your algorithm that allow you to prove what result the algorithm should produce without running the algorithm.
If your algorithm has randomized or otherwise nondeterministic algorithms you may also want to ensure that you are using the same types of random generator with the same seed, although good algorithms should have only a very small dependance on this.
That's what test sets are for! You need training data with examples xand corresponding labels y to begin with. Now instead of using everything for training, take a subset of the data, leave it out of training, and check the quality of the generated predictions y' with respect to the proper labels x. See http://en.wikipedia.org/wiki/Cross-validation_(statistics) for more details.
OK you're asking for testing "without the correct output", but it's hard for me to imagine how you want to train a machine learning classifier without any training data in the first place. That's why I think the trick of using your training data for that purpose is worth mentioning.
How well your findings on the test set correlate on the true accuracy on your unlabelled data of course is another question, but you can e.g. do multiple rounds of cross-validation (see Wikipedia link for specific patterns like $k$-fold or leave-one-out), or make sure that the distribution of your unknown data is similar to the training data (if it's not, you might have a problem anyway).
UPDATE To see if your implementation of a specific machine learning algorithm is correct, one way would be to find a paper describing its performance on an openly available dataset, and see if your implementation yields the same results. I've once tried this and got exactly the same performance figures (as in, the same number down to the third digit).
If your algorithm is based on some kind of probabilistic model, then you can simulate data from this model, apply your algorithm, and see if you get the correct values.
For example, if you wanted to test out a Normal mixture clustering EM algorithm, then simulate data from a mixture of normals and try and use your EM algorithm to correctly identify the true clusters & parameters.
I use this approach (simulate data from the truth and try to recover the paramters used for simulation) for my MCMC projects when I don't trust convergence diagnostics.
As @DanielMahler points out, this process is only reliable when your algorithm is unbiased, which will often not be the case. Biased algorithms won't recover the true parameters as easily as unbiased ones.
