Can We Write Better Algorithms With Machine Learning? (quantamagazine.org) 19
Quanta magazine describes an "explosion of interest" in what they're calling algorithms with predictions, arguing that machine learning tools "have, in a real way, rejuvenated research into basic algorithms."
Machine learning and traditional algorithms are "two substantially different ways of computing, and algorithms with predictions is a way to bridge the two," said Piotr Indyk, a computer scientist at the Massachusetts Institute of Technology. "It's a way to combine these two quite different threads...." In the past few years, researchers have shown how to incorporate algorithms with predictions into scheduling algorithms, chip design and DNA-sequence searches.
In addition to performance gains, the field also advances an approach to computer science that's growing in popularity: making algorithms more efficient by designing them for typical uses.... By ignoring the worst-case scenarios, researchers can design algorithms tailored to the situations they'll likely encounter. For example, while databases currently treat all data equally, algorithms with predictions could lead to databases that structure their data storage based on their contents and uses....
[M]ost of these new structures only incorporate a single machine learning element. Tim Kraska, a computer scientist at MIT, imagines an entire system built up from several separate pieces, each of which relies on algorithms with predictions and whose interactions are regulated by prediction-enhanced components.
"Taking advantage of that will impact a lot of different areas," Kraska said.
In addition to performance gains, the field also advances an approach to computer science that's growing in popularity: making algorithms more efficient by designing them for typical uses.... By ignoring the worst-case scenarios, researchers can design algorithms tailored to the situations they'll likely encounter. For example, while databases currently treat all data equally, algorithms with predictions could lead to databases that structure their data storage based on their contents and uses....
[M]ost of these new structures only incorporate a single machine learning element. Tim Kraska, a computer scientist at MIT, imagines an entire system built up from several separate pieces, each of which relies on algorithms with predictions and whose interactions are regulated by prediction-enhanced components.
"Taking advantage of that will impact a lot of different areas," Kraska said.
A machine learning algorithm to learn... (Score:1)
... how to not use machine learning? Do your own homework assholes.
Old News (Score:1)
The article hurts my brain (Score:2)
Imagine you run your company’s IT department and you need to check if your employees are going to websites that pose a security risk. Naively, you might think you’ll need to check every site they visit against a blacklist of known sites.
Well yes, if I didn't know how to program, but somehow still thought about algorithms, I might hypothetically consider that a solution.
Nah (Score:2)
The article discusses someone using machine learning as a better heuristic for bloom filters. That is not exactly a basic algorithm.
Re: (Score:2)
Algorithms that could suggest a change, once per program, might not be so bad. Two would get annoying.
"You might want to consider a hash table instead of linear search in xyz.c line 123"
"That second p++ inside a printf has undefined behaviour"
Re: (Score:2)
That is not even at all related to what this article is about. It's trying to do something completely different.
Re: (Score:2)
Yes. Correct on both counts.
Re: (Score:2)
Of course, sometimes LINQ gives you a warning if your algorithm is too inefficient. It might be nice if it gave you an option to rewrite it automatically more efficiently.
Re: (Score:2)
This makes more sense and is a relief. I was worried about the utter failure going on here if they meant actual mathematical algorithms using the highly primitive machine learning AI that exists today. May as well have the machine learning decide if P=NP or not. If AI is good enough to come up with a better sort algorithm then that's about as far as you can go, intelligence wise :-)
Now, machine learning could optimize a traditional algorithm, but the algorithm complexity would stay the change. Highly op
It's limited (Score:2)
Danger Zone (Score:2)
By ignoring the worst-case scenarios, researchers can design algorithms tailored to the situations they'll likely encounter.
While this is a fine idea on paper, in practice if someone is not careful it can quickly lead to a dangerous scenario. For instance, maybe there’s a 10x average performance improvement to be had with our sorting algorithm if we allow for 100x worse performance in the “rare”, worst case scenario where the input list is in the reverse order. So, we use this new algorithm and declare the 10x better average performance a win.
Six months later, our company pisses off a script kiddie who uses a s
Absolutely (Score:3)
There are plenty of problems where we use heuristics. either the problem is NP complete, or the real time constraints of the application prevents us from using an optimal algorithm. In those cases, machine learning can really help.
I have a colleague exploring using reinforcement learning to schedule jobs on leadership class super computers. The basic scheduling problem is NP hard. And on top of that there are typically so many machines machines, and so many jobs in the queue that you can not afford any algorithm with super linear complexity when a scheduling event happens. Linear may actually already be too expensive you probably want sublinear.
But the problem is really complicated because you want to not waste resources, you want to keep job locality on the platform, you need to account for heterogeneous nodes. It's REALLY hard; so the current schedulers are doing the pretty basic things. Basic greedy algorithms are used. Though depending on machine state teh greedy could be real bad. Surely, RL can help do something better there, for instance design better greedy strategies or switch greedy strategies to avoid real bad cases.
We? (Score:2)
Can We Write Better Algorithms With Machine Learning?
Pretty sure using machine learning means they're writing the algorithms. Do we want Skynet? 'Cause this is how we get Skynet.
Sounds like dynamic programming (Score:2)
Like DP, a âoesmartâ algorithm like the one described that first uses a prepared (compressied) set of high likelihood matches, and then is followed by a slower pass of (uncompressed) naive search sounds pretty much like dynamic programming. The learning phase is not well described by the OP. Presumably there is some use of external information which produces new (or revised) choices to be integrated into the compressed set of choices, thereby improving future performance, adaptively and more opt
First Thing's First (Score:2)
- Pickup Truck
- Heavy Duty Trucks
- Urban Transport
- Full Autonomy
- Autonomous Ridesharing
Maybe Musk considers them complete, but I don't see them out in the world.