0
$\begingroup$

I lack formal knowledge about statistics and got lost in the Wikipedia articles about the subject.

I have an algorithm that produces a solution for a problem. There might be several solutions possible. Not all solutions are equally good, and I am able to give score for each solution.

I want to be able to tell if the algorithm is good or not.

For each problem I can calculate bounds on the best and worst possible solution (only bounds, not exact values). I can also generate a random solutions for a problem, but not every random solution is a valid one (high chances for getting a valid one, though).

The data set I am going to use have problems of approximately the same difficulty.

Clearly I should use some statistical test, but which one? It seems that they require knowledge about the distribution and are more suitable for comparing algorithms.

Edit:

I do not want to add too much irrelevant specifics, so I will try to simplify.

I have an algorithm that solves a problem. for example, it finds a path between two nodes in a graph. The input is a graph. The output is a path.

Obviously, shorter paths are better than longer ones.

I want to know if my algorithm is good. I do not know exactly how to define "good", but that is where statistics can help me, is not it?

What I though about so far was to do the following:

  1. Run the algorithm on a set of problems (problem is a graph). The sizes of all these graphs are of the same order of magnitude.
  2. Find a random path (in my specific problem it is possible to do) for each graph, and do this many times.
  3. Compare the results of 1 and 2 to see if my algorithm is better than choosing a path at random.

Am I doing it right? How should I perform step 3?

$\endgroup$
6
  • 2
    $\begingroup$ I am having great difficulty following this. Can you describe the situation you are studying, the data you have, and the algorithms you are applying? $\endgroup$ – gung - Reinstate Monica Mar 10 '12 at 3:37
  • $\begingroup$ Are you interested in making some kind of inference about the distribution of solutions that you random solution generator produces? $\endgroup$ – user9437 Mar 10 '12 at 4:45
  • $\begingroup$ @gung See my edit. $\endgroup$ – Artium Mar 10 '12 at 22:32
  • $\begingroup$ @jlovegren No. I want to compare the random solution generator to my algorithm and see if mine is better. Also, a-priory I know nothing about the distribution. $\endgroup$ – Artium Mar 10 '12 at 22:32
  • 1
    $\begingroup$ Your answer to @jlovegren suggests that hypothesis testing may not be what you really need. I suspect that your algorithm is better than random & that that can be shown, but that it's not very impressive or meaningful. I will edit to change the tag to machine-learning, as I bet some of those folks will be able to help you. $\endgroup$ – gung - Reinstate Monica Mar 10 '12 at 22:48
1
$\begingroup$

The problem of finding shortest paths on graphs is well-studied.

I don't think it's too important to know whether or not your method is better than random because there are a number of well-studied algorithms that solve (some specific) graph traversal problems quite well.

I think the more relevant comparison is to ask wether your method is better (1) for some special graph, such as a planar or chromatic graph or (2) for graphs of a certain size or density or number of edges. Note that better can mean any number of things: lower working memory requirements, lower computational complexity, better worst-case behavior, better average behavior.

$\endgroup$

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.