CSE 250A

COMMENTS ON REPORTS FROM THE SECOND PROJECT

It is important that your abstract be as informative as possible about the concrete contributions of your paper.  Fifty words is too short.  State contributions in a positive way that says implicitly or explicitly why they are interesting.  Write "we show that RNovelty avoids stagnation on plateaus; this may explain why RNovelty is  successful" and not just "RNovelty does not fail because of stagnation."  But do not write "RNovelty succeeds because it avoids stagnation" unless you are sure this stronger claim is true.  Be very careful with words that make claims of causation such as "since," "because," and "results in." Similarly, "provides insight into" is a different and weaker claim than "explains."

Be sure that your claims are not true for trivial reasons.  Do not write "[the new method] is shown to have significantly better performance on problems that are difficult for WalkSat."  Almost by definition, these are the problems on which there is more room for improvement!  Can the new method do better on these without doing worse on others?

Given that the abstract summarizes the paper, it is not necessary to provide a similar summary in the Introduction, which can provide background and motivation instead.  There is usually no need for separate subsections entitled Background, Motivation, etc.  There is no need to repeat definitions that are elementary in a given research field, but it is important to define novel concepts very clearly and carefully.

Exercise: What is wrong with the following definition?

"A refutation proof consists of a set of variables S such that any possible assignment of truth values to the variables in S will allow the formula to be reduced to one which contains an empty clause, and thus is unsatisfiable."

Note that the issue is not just that the word "reduces" is not clarified.  More importantly, different levels of complexity or aggressiveness in what reductions are allowed lead to completely different meanings for the definition.  Note also that "minimal" and "minimum" are different.

Remember that in complexity theory, a problem is a set of problem instances.  The time complexity of any single instance is constant.  Calling an "instance" a "problem" is a category error.

In AI we often consider very restricted problems, for example the set of all n-queens instances.  In this case, the computational complexity of the problem depends on how much special knowledge we are allowed to build into an algorithm.  There do exist extremely fast specialized algorithms for n-queens.  However, these algorithms do not extend to a broad class of CSP instances.

Restricted sets of problem instances are important in AI because nature only presents an intelligent agent with instances from a constrained set.  There is no evolutionary pressure on agents to possess algorithms for solving general problems.

More knowledge is not always beneficial...Gigerenzer

When you present an algorithm, always describe it in the simplest possible way, using as much self-similarity as possible in the description. ...

In experimental research, it is not enough just to show that an algorithm performs better.  The most useful contributions explain why a new method is better, thus yielding insights that can lead to the design of even better methods in the future.  A major insight arising from several papers is:

For RNovelty, performance is best when p > 0.5, and then only its last two rules are relevant.  These rules are successful in preventing search from stagnating.  Therefore, other mechanisms to prevent stagnation like tabu lists would be counter-productive.  Indeed, the opposite of a tabu list is beneficial: a mechanism that restarts search near previous good assignments.