Unit Testing with an Optimization Problem

Suppose I’m making an algorithm that identifies the subject of a picture. It could be anything that a computer doesn’t do that well, but I’m not expecting to get the right answer every time – 80% is fine. Suppose further, that the accuracy of the intermediate steps was also somewhat fuzzy. Is there a way to incorporate unit tests?

The option that immediately comes to mind is to add 1 to a tally and every time a ‘test’ passes, increment the tally. When that finishes, divide by the total and test ‘passes/tests > 0.8’, but that seems kludgey.

EDIT: Thank you all for your kind words and well-reasoned responses. My particular problem, while fuzzy, has nothing to do with pictures, and I’m currently getting about 80% pass. The short term value for me in a testing scheme would be knowing whether small adjustments were more globally beneficial or catastrophic. Long term testing value should be obvious.

As others have noted, TDD primarily focuses on unit-testing. However, that doesn’t mean that black-box integration testing shouldn’t be covered. Nor should it necessarily cover the same deterministic nature of a unit-test.

In terms of unit-testing

Assuming that nothing in your algorithm is random, it should be possible to write unit-tests for the components of your software that pass 100%. There should be no reason why you would need to reach an 80% mark.

However, these tests are specific to the implementation of the algorithm, by their very nature. With a given input you would always expect the same output. You describe the situation in which things will lead towards a match, and the situations in which they would move away from a match.

If the algorithm changes, you would expect at least some of the unit tests to change too.

In terms of black-box integration testing

It seems that there may be a requirement for a test along the lines of:

Given this set of x pictures I expect a positive match rate of 80%
I don’t care which have a positive match, just that the threshold is reached.

You would run each picture through, check if your algorithm gave you a match with the expected result or not. Keep a tally and score, as per your suggestion.

This test would describe the minimum functional requirements of the algorithm and would be entirely independent of the implementation.

So yes, this sounds like an entirely appropriate test and a measure of how successful the whole of the software was.

TDD is not a design technique.

While it can aid at producing an effective design (and validating the veracity of that design, and verifying that your software still works after refactoring), you still need to think about the structure of your programs and come up with some sort of algorithmic representation for the specific problems you are trying to solve.

You can’t just expect a solution to a non-trivial computing problem to emerge organically from red-green-refactor, especially if that problem involves heuristics. Naturally, if you have some idea about how the solution will emerge, you can model that idea with unit tests, but you can’t expect to get pearls from sand if you don’t even have a clam.

In any case, you can’t have a test that passes 80% of the time and call that a successful unit test. What you can have are five tests, four of which produce one result, and one of which produces the other, or a test that returns some metric (other than passes/fails) which you can assert to be 0.8. That provides your 80% ratio, while still maintaining “go, no-go” states.

Unless your code uses some randomized technique, it is deterministic, even if for a given input it is hard to specify or predict. So when we see a given input produce a given result, if we provide the same input we will see the same result again. This is true even for a learning algorithm or database application, where “the same input” means the same input being applied to the system in the same state.

If your algorithm does use a randomized technique, the usual approach is to turn off the random seed aspect of it for testing, so that tests always give the same “random” result. (We would not hard-code the seed, because the code would need to be changed and tested again every time we did testing, and so on).

So you should have a set of tests that are repeatable. For the same input to the same algorithm you should see the same result.

But you seem to be confusing the fuzzy nature of your algorithm with non-determinism. Even a fuzzy algorithm should give the same results from the exact same inputs.

A second issue seems to be that the algorithm is still being developed. This presents the same problem as regression testing any code under development. With simple changes to the code you should be able to predict the effect on the existing test cases. But because of the complexity of analyzing fuzzy logic code you may not be able to predict the precise result of the change. In this case, you could document each test with it’s result against each version of the codebase, and prepare modified tests that exploit the algorithm changes.

TDD usually talks about unit tests, which can be white-box tests. You are talking about a black-box integration test.

At some point you will have an actual algorithm. If working properly it will pass some inputs, and fail others. That’s what you test. Whether it gets 80% right will depend on the inputs you test. Whether the result is acceptable for the ultimate real-world inputs you encounter won’t be something your unit tests cover – though you could of course get a sample of real-world inputs and test those against the top level methods.

For this type of problems perhaps a inside-out approach to TDD can be most effective. Probably you need different deterministic parts to build your complete solution, you can build those part with “normal” TDD.

Also you can make some complete test of your algorithm using a predefined set of images, with this you can check if the results reach some threshold. With this you can verify this threshold with every change, the most difficult parts its perhaps to select the collections of images that represent the different possible scenarios in which your algorithm is supposed to give good results.

With this second test you cannot go step-by-step for designing and algorithm, are really useful for verifying purposes but not real useful for designing and algorithm. TDD is not a technique for designing algorithms like the classical sudoko example from Ron Jeffries (one of the original members of the Kent Beck C3 team that popularize the TDD technique).

In resume, you can use TDD to build and perhaps design some of the multiple small parts that your complete algorithm needs, and you can use simple test for verify behavior, but use TDD for build a complete algorithm is not “magic”, you need to study the different techniques for algorithms construction.

If your algorithm is going to “fail” 80% of the time, how do you know that it is working? Is this for the same image or that 80% of the images will not work with your algorithm? If it is the same image not working, how is it that you would know that it is not a problem in your algorithm?

TDD formalizes your coding process, in that you have test code that you use to verify that your code works as expected. When you are coding your algorithm, you execute it with some image to see what the results are, right? TDD would have you write something that will automate that process for you. This way, you don’t forget to run through a test case or get lazy and skip some because the “tests” get repetitive.

For your algorithm, the same image should end up with same results each time shouldn’t it? Or if you are using a random generator that is causing the non-determinism, the same image and same seed should result in the same results over and over again. You would also be able to provide an example of an image that would “fail” and as if it passes this is a sign of a bug in the algorithm.

Your tests are an automation of how you would verify that the program works as you intend it.

At a certain, level most programmers practice TDD. They just don’t write/program their tests so that others can use them.

Filed under: softwareengineering - @ 10:37

Thẻ: statistics, unit-testing

Thiết kế website giá rẻ

Danh mục

Unit Testing with an Optimization Problem