Is it possible to classify or learn to estimate the minimum value in a table if the values are integer and represented 32 bits (and we can input all variables at the same moment, like in system on a chip (SoC))?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ I'm not sure what you're asking. To find the minimum in a list, you have to look at every element once, and the simple solution (a for loop scanning the table) is a theoretically optimal O(n). If you get to design circuitry that can read every input at once, you can get that down to O(1) time, though the cost in terms of silicon and complexity would be formidable. Or something like O(log n) pretty simply. In any case, I'm not sure what you're hoping for from a learning algorithm. Can you elaborate? $\endgroup$– deongCommented Dec 27, 2017 at 14:51
-
$\begingroup$ @mico why is that ? $\endgroup$– user3360879Commented Dec 27, 2017 at 14:54
-
$\begingroup$ @deong you absolutly right, but to answer your question i was looking for resolve a minimum search problem as a learning problem, and try to design a parallel solution just to figure out if any problem can be considered a learning problem $\endgroup$– user3360879Commented Dec 27, 2017 at 15:00
-
1$\begingroup$ I know there has been a lot of work on things like learning parallel sorting algorithms, for example. I've seen some work on genetic algorithms for that I know. That might provide you a starting place to jump off from. $\endgroup$– deongCommented Dec 28, 2017 at 16:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
There are several ways to take this question:
- can a learner ingest a table and give an exact minimum in less compute than the O(n) method?
- can a learner ingest a table and give an exact minimum in NOT less compute than the O(n) method?
- can a learner find patterns in tables and predict an approximate minimum in less compute than the O(n) method?
- can a learner find patterns in tables and predict an approximate minimum in NOT less compute than the O(n) method?
Answers:
- If there is no larger scale pattern then the best the classical learner is going to do would be the O(n) method; none of the current ones should beat it.
- It is possible to get the exact value with much more compute overhead. This is like using a backhoe to plant a carrot, you can do it, but its overkill.
- If the table has patterns that are matched to the learner, then it can beat the search. Think of a classification and regression tree model (CART), which can be reduced to a few if-then's and give an answer in O(1).
- Because of 3, if the pattern exists but the learner is slow like FFNN which is O(n^5) to predict, it can be slower and if done right might also be as good.
