2 ms·
Point 8, the fast dismissal of Monte-Carlo method is a huge blunder. The point of Monte-Carlo method is that you can tradeoff accuracy for speed. The longer yo
by GistNoesis 2y ago
Point 8, the fast dismissal of Monte-Carlo method is a huge blunder.
The point of Monte-Carlo method is that you can tradeoff accuracy for speed. The longer you run your algorithm the more accurate you get.
But what's even more interesting is that we can often use the contrapositive : You can get shitty accurate result real fast.
Instead of exploring all paths, you explore only one path picked at random.
And that's where it shines : when you put it into the most imbricated loop of your algorithm.
For example when you want to learn a neural network which autoroute. Typically you would have the outerloop which is updating the neural network parameter, and the inner-loop which is computing a path through the graph.
When you use Monte-Carlo this inner-loop which control accuracy can be reduced to 1 iteration if everything is bias-less, you will have a slower outerloop due to higher variance but the machine learning should """theoretically""" learn.
This is what allows you to build policies which intuitively always pick the right decision. Like in chess or go, you have some monte-carlo tree search variant like alpha-go-zero or alpha-chess-zero or alpha-router-zero, where even without the search part, the giant cache (encoded by the neural network parameters), once trained, can compute your best guess path in one pass through your neural network aka constant time (with a constant which can easily trade memory for speed by augmenting the number of parameters or training for longer).
- ttyprintk 2y agoYet the author mentioned simulated annealing, so was probably not even trying a neural net, since SA does not compute a gradient.
- ttul 2y agoSimulated annealing has long been one of the classic metaheuristic methods applied to autorouting in circuit design. It was widely used in early research and some commercial tools because its probabilistic approach helps escape local minima in these NP‐hard problems. Today, while many modern autorouters in industry tend to favor faster or more specialized hybrid methods, simulated annealing remains a common benchmark in academic studies and research prototypes for routing and related tasks like floorplanning. Source: I once wrote a simulated annealer for VLSI wiring. It was cool.
- opwieurposiu 2y agoSimulated annealing works great for placing map labels. Lets say you have to label POI with flags, you do not want the flags to overlap and you can only place the labels NSEW of the POI. 1. Plop the labels down in random* directions. 2. Calculate the total overlap. 3. Randomly* move 10% of the labels. 4. Calculate the total overlap again, If the overlap is improved, keep your changes, If things got worse, then backtrack. 5. Sometimes you randomly keep changes that make things worse, this is the annealing part. This is how you escape local minima. * The randomness does not have to be 100%, you can try smartly avoiding nearest neighbors 2/3 of the time and then do a random move 1/3 of the time. If you always try and be smart you will tend get trapped in a local minima.
- ur-whale 2y ago> Point 8, the fast dismissal of Monte-Carlo method is a huge blunder. Yeah, I had the exact same reaction when I read the article. MC is the "keeping it real" algorithm, slow, but almost always dead simple to implement and that can be trusted with super high certainty to double-check that you've not completely wandered off in the weeds.
- bee_rider 2y agoWhich is sort of funny given the intuitive description of Monte Carlo—a random wander, possibly into the weeds.
- throwaway-blaze 2y agoI was this many days old when I learned the word "imbricated".
- GistNoesis 2y agoYeah you're right, I should have said nested (it is a valid Anglicism from French "imbriqué(es)" )
- burnished 2y agoNothing wrong with inadvertently teaching folk new words, it was an uncommon and welcome surprise for me