Researchers from the University of Copenhagen have become the first in the world to mathematically prove that, beyond simple problems, it is impossible to develop algorithms for AI that will always be stable.
ChatGPT and similar machine learning-based technologies are on the rise. However, even the most advanced algorithms face limitations. Researchers from the University of Copenhagen have made a groundbreaking discovery, mathematically demonstrating that, beyond basic problems, it's impossible to develop AI algorithms that are always stable. This research could pave the way for improved testing protocols for algorithms, highlighting the inherent differences between machine processing and human intelligence.
The scientific article describing the result has been approved for publication at one of the leading international conferences on theoretical computer science.
Machines interpret medical scanning images more accurately than doctors, translate foreign languages, and may soon be able to drive cars more safely than humans. However, even the best algorithms do have weaknesses. A research team at the Department of Computer Science, University of Copenhagen, tries to reveal them.
Take an automated vehicle reading a road sign as an example. If someone has placed a sticker on the sign, this will not distract a human driver. But a machine may easily be put off because the sign is now different from the ones it was trained on.
"We would like algorithms to be stable in the sense, that if the input is changed slightly the output will remain almost the same. Real life involves all kinds of noise which humans are used to ignore, while machines can get confused," says Professor Amir Yehudayoff, heading the group.
A language for discussing weaknesses
As the first in the world, the group together with researchers from other countries has proven mathematically that apart from simple problems it is not possible to create algorithms for Machine Learning that will always be stable. The scientific article describing the result was approved for publication at one of the leading international conferences on theoretical computer science, Foundations of Computer Science (FOCS).
"I would like to note that we have not worked directly on automated car applications. Still, this seems like a problem too complex for algorithms to always be stable," says Amir Yehudayoff, adding that this does not necessarily imply major consequences in relation to the development of automated cars:
"If the algorithm only errs under a few very rare circumstances this may well be acceptable. But if it does so under a large collection of circumstances, it is bad news."
The scientific article cannot be applied by the industry to identify bugs in its algorithms. This wasn't the intention, the professor explains:
"We are developing a language for discussing the weaknesses in Machine Learning algorithms. This may lead to the development of guidelines that describe how algorithms should be tested. And in the long run, this may again lead to the development of better and more stable algorithms."
From intuition to mathematics
A possible application could be for testing algorithms for the protection of digital privacy.
"Some companies might claim to have developed an absolutely secure solution for privacy protection. Firstly, our methodology might help to establish that the solution cannot be absolutely secure. Secondly, it will be able to pinpoint points of weakness," says Amir Yehudayoff.
First and foremost, though, the scientific article contributes to theory. Especially the mathematical content is groundbreaking, he adds: "We understand intuitively, that a stable algorithm should work almost as well as before when exposed to a small amount of input noise. Just like the road sign with a sticker on it. But as theoretical computer scientists, we need a firm definition. We must be able to describe the problem in the language of mathematics. Exactly how much noise must the algorithm be able to withstand, and how close to the original output should the output be if we are to accept the algorithm to be stable? This is what we have suggested an answer to."
Important to keep limitations in mind
The scientific article has received large interest from colleagues in the theoretical computer science world, but not from the tech industry. Not yet at least.
"You should always expect some delay between a new theoretical development and interest from people working in applications," says Amir Yehudayoff while adding smilingly: "And some theoretical developments will remain unnoticed forever."
However, he does not see that happening in this case: "Machine Learning continues to progress rapidly, and it is important to remember that even solutions which are very successful in the real world still do have limitations. The machines may sometimes seem to be able to think but after all, they do not possess human intelligence. This is important to keep in mind."
Reference: "Replicability and Stability in Learning" by Zachary Chase, Shay Moran and Amir Yehudayoff, 2023, Foundations of Computer Science (FOCS) conference.
DOI: 10.48550/arXiv.2304.03757
News
Scientists Uncover Hidden Blood Pattern in Long COVID
Researchers found persistent microclot and NET structures in Long COVID blood that may explain long-lasting symptoms. Researchers examining Long COVID have identified a structural connection between circulating microclots and neutrophil extracellular traps (NETs). The [...]
This Cellular Trick Helps Cancer Spread, but Could Also Stop It
Groups of normal cbiells can sense far into their surroundings, helping explain cancer cell migration. Understanding this ability could lead to new ways to limit tumor spread. The tale of the princess and the [...]
New mRNA therapy targets drug-resistant pneumonia
Bacteria that multiply on surfaces are a major headache in health care when they gain a foothold on, for example, implants or in catheters. Researchers at Chalmers University of Technology in Sweden have found [...]
Current Heart Health Guidelines Are Failing To Catch a Deadly Genetic Killer
New research reveals that standard screening misses most people with a common inherited cholesterol disorder. A Mayo Clinic study reports that current genetic screening guidelines overlook most people who have familial hypercholesterolemia, an inherited disorder that [...]
Scientists Identify the Evolutionary “Purpose” of Consciousness
Summary: Researchers at Ruhr University Bochum explore why consciousness evolved and why different species developed it in distinct ways. By comparing humans with birds, they show that complex awareness may arise through different neural architectures yet [...]
Novel mRNA therapy curbs antibiotic-resistant infections in preclinical lung models
Researchers at the Icahn School of Medicine at Mount Sinai and collaborators have reported early success with a novel mRNA-based therapy designed to combat antibiotic-resistant bacteria. The findings, published in Nature Biotechnology, show that in [...]
New skin-permeable polymer delivers insulin without needles
A breakthrough zwitterionic polymer slips through the skin’s toughest barriers, carrying insulin deep into tissue and normalizing blood sugar, offering patients a painless alternative to daily injections. A recent study published in the journal Nature examines [...]
Multifunctional Nanogels: A Breakthrough in Antibacterial Strategies
Antibiotic resistance is a growing concern - from human health to crop survival. A new study successfully uses nanogels to target and almost entirely inhibit the bacteria P. Aeruginosa. Recently published in Angewandte Chemie, the study [...]
Nanoflowers rejuvenate old and damaged human cells by replacing their mitochondria
Biomedical researchers at Texas A&M University may have discovered a way to stop or even reverse the decline of cellular energy production—a finding that could have revolutionary effects across medicine. Dr. Akhilesh K. Gaharwar [...]
The Stunning New Push to Protect the Invisible 99% of Life
Scientists worldwide have joined forces to build the first-ever roadmap for conserving Earth’s vast invisible majority—microbes. Their new IUCN Specialist Group reframes conservation by elevating microbial life to the same urgency as plants and [...]
Scientists Find a Way to Help the Brain Clear Alzheimer’s Plaques Naturally
Scientists have discovered that the brain may have a built-in way to fight Alzheimer’s. By activating a protein called Sox9, researchers were able to switch on star-shaped brain cells known as astrocytes and turn them into [...]
Vision can be rebooted in adults with amblyopia, study suggests
Temporarily anesthetizing the retina briefly reverts the activity of the visual system to that observed in early development and enables growth of responses to the amblyopic eye, new research shows. In the common vision [...]
Ultrasound-activated Nanoparticles Kill Liver Cancer and Activate Immune System
A new ultrasound-guided nanotherapy wipes out liver tumors while training the immune system to keep them from coming back. The study, published in Nano Today, introduces a biodegradable nanoparticle system that combines sonodynamic therapy and cell [...]
Magnetic nanoparticles that successfully navigate complex blood vessels may be ready for clinical trials
Every year, 12 million people worldwide suffer a stroke; many die or are permanently impaired. Currently, drugs are administered to dissolve the thrombus that blocks the blood vessel. These drugs spread throughout the entire [...]
Reviving Exhausted T Cells Sparks Powerful Cancer Tumor Elimination
Scientists have discovered how tumors secretly drain the energy from T cells—the immune system’s main cancer fighters—and how blocking that process can bring them back to life. The team found that cancer cells use [...]
Very low LDL-cholesterol correlates to fewer heart problems after stroke
Brigham and Women's Hospital's TIMI Study Group reports that in patients with prior ischemic stroke, very low achieved LDL-cholesterol correlated with fewer major adverse cardiovascular events and fewer recurrent strokes, without an apparent increase [...]
