2
$\begingroup$

Just a high level question,

Given a human $H$ if you give them a question (and they have sufficient training), the more time you give them to work on the question (assuming all other needs are met and they are willing to work completely focused for you) the more likely they are to find an answer to it, or at least get a better solution/deeper understanding of it.

What sort of ML models reflect this? Some the classical ones such as Neural Networks, and SVMs all have a fixed amount of time for delivering an answer (after being trained), and sitting with these models and giving them several extra hours does nothing (only more training can improve them within what they are capable of doing).

On the other hand a lot of heuristic search algorithms (ex: Branch and Bound, Branch Cut) or even the ridiculous (build every string up to size K, treat as a computer program, see if it solves the problem better than before) share in common the fact that given more time, they on average will do better/give better results until they find an optimal.

Are there any standard ML algorithms, say for classification of C discrete classes in $\mathbb{R}^n$ that benefit directly from being given more time on a test set.

I ask this because suppose I gave a human a classification task on a very ambiguous datapoint. And just left them to it (for example classify $\sqrt{2}$ as irrational or rational), if I asked for an immediate answer, assuming only knowledge in algebra the answer may be completely random (the human hasn't encountered this fact yet). On the other hand if I said here is the problem you have three years to come back to me with an answer, it's quite possible, with enough of their toying and symbol shuffling that they come back with an answer and a definite proof.

Now I don't suspect there to be an algorithm to solve everything (except the obnoxious build every computer program in existence approach) but at least I would hope there exist models that are able to improve their guess arbitrarily with access to additional time.

$\endgroup$

2 Answers 2

1
$\begingroup$

Humans indeed do many classification tasks that can be modeled by machine learning classifiers (e.g. deciding on a color category from an r,g,b triplet, deciding on a phoneme from acoustic features).

IMHO your example, deciding on 'is sqrt(2) rational?', isn't one of those. You suggest that the human gain from time is due to '..toying and symbol shuffling'. This means that the 'algorithm' people use in this case (at least if they spend considerable time on this) isn't a comparison of the 'test-set' with a training-set like machine learning classifiers do but something more similar to Automated Theorem Proving. As far as I know, in ATP more time means better success rate since further potential solutions can be explored.

A related and even more extreme case is the task of playing chess, in which computers may gain much more than humans from being given additional time (assuming no effective memory limitation, the former can explore more and more of the game tree).

$\endgroup$
1
$\begingroup$

In general, any algorithm with less than ideal test-time complexity will fit the bill.

Consider k-nearest neighbors. As you increase $k$, the complexity at test-time goes up, so it will take more time, while the training is unaffected.

That said, increasing $k$ won't always improve performance, but neither will taking more time always help someone give a better answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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