2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ OK, I used the cross-validation and received 80% accuracy. But how can I be sure that in the implementation of no small mistake? And if it is correct, you get 90%. $\endgroup$ – luckyi May 16 '14 at 21:20
  • $\begingroup$ See my update, there's not really a way to know on your dataset, but you might get lucky and find a reference how it should perform on a known dataset. $\endgroup$ – user979 May 17 '14 at 17:03
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thank you for answer. And what about not probabilistic models? KNN, neural networks and etc? Or if simulate data is not entirely trivial task(for example text classification). Any ideas? $\endgroup$ – luckyi May 16 '14 at 13:25
  • $\begingroup$ @luckyi for simpler algorithms like KNN you could probably create test cases in a straightforward way "by hand". The other suggestion for more complicated scenarios would be to try and replicate previous anlyses (either from intro texts/blogs or academic articles introducing the model). Of course this wouldb't apply when building your own unique algorithms $\endgroup$ – user44764 May 16 '14 at 16:37
  • $\begingroup$ This assumes that the learning algorithm is an unbiased estimator. High dimensional, sparse, noisy or long tailed data often favors biased/regularized algorithms, which are give better prediction on such data, but do not recover the original parameters accurately. $\endgroup$ – Daniel Mahler May 21 '14 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.