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
Human Bodies Are Producing Two Billion Tons of CO2 a Year
A new study reveals that the amount of carbon dioxide produced by human metabolism has increased dramatically over three decades. The carbon dioxide produced by human bodies as they convert food into energy increased [...]
A Hidden DNA Mechanism Could Explain How 20% of Human Cancers Develop
Researchers have identified an unexpected molecular vulnerability in cancers carrying BAF mutations. Mutations found in roughly 20% of human cancers may promote tumor growth by changing how DNA is organized inside cells. Researchers have [...]
Ebola kills over 5,300 in fastest-growing outbreak on record
Africa’s latest Ebola outbreak has killed nearly 5,400 people, the vast majority of them in the Democratic Republic of Congo (DRC), according to the continent’s top health agency. Africa Centres for Disease Control and [...]
China makes early progress in using sound waves to stimulate damaged brains
Chinese researchers are testing whether focused ultrasound can help restore consciousness in patients with severe brain injuries, adding to a growing international effort to use sound waves to stimulate deep brain structures without surgery. [...]
Micro-drones fly through the body thanks to ultrasound
At the EPFL, micro-drones have been developed that can be moved without a motor or battery.No motors, no batteries, no electronics on board, just small cavities that convert sound waves into thrust: this is [...]
A Single Enzyme Could Hold the Key to Treating a Devastating Brain Disorder
Blocking an enzyme’s production restored brain growth and healthy behaviors in mice engineered to develop Angelman syndrome, pointing to a possible treatment target. Children with Angelman syndrome begin to show difficulties with thinking and [...]
Scientists Develop a Clever New Way To Kill Cancer Cells From the Inside
Scientists have developed an experimental strategy that exploits a chemical byproduct of cancer cells to produce anticancer drugs directly inside them. Scientists in Japan have developed an experimental method that uses a chemical produced [...]
Our books are available worldwide!
Online Sellers other than Amazon, Routledge, and IOPP Indigo Global Health Care Equivalency in the Age of Nanotechnology, Nanomedicine and Artifcial Intelligence Global Health Care Equivalency In The Age Of Nanotechnology, Nanomedicine And Artificial [...]
After only a short training, people in a coma managed to send targeted signals
Researchers have succeeded in communicating with brain-injured patients who are unconscious. They see enormous potential in this for future treatments. Patients who lie motionless in bed after a severe brain injury and do not [...]
MIT Scientists Reprogram Immune Cells Inside the Body To Destroy Cancer
Natural killer cells reprogrammed inside mice eliminated lymphoma tumors and helped damaged livers heal, though whether this approach could help people with cancer or autoimmune disease remains unknown. To make a cancer treatment from [...]
Melanoma mRNA Vaccine Shows Promise in Preventing Disease Recurrence
Key takeaways: Phase 3 trial finds personalized intismeran plus pembrolizumab may better prevent high-risk melanoma recurrence after surgery The trial enrolled 1,137 patients and builds on phase 2 results showing about half the recurrence [...]
Scientists Discover a Powerful New Weapon Against a Dangerous Gut Infection
The promise of an experimental treatment for C. difficile gut infections lies partly in the bacteria it leaves alive, according to early laboratory and mouse research. Broad-spectrum antibiotics can disrupt the gut’s microbial community, [...]
Your Bones May Hold a Hidden Clue to Blood Cancer Survival
For people with blood cancers called myelodysplastic syndromes, osteoporosis may hold an overlooked clue to survival, a three-year observational study suggests. In blood cancers that develop in the bone marrow, an important clue to [...]
Researchers Discover What Reading for Pleasure May Be Doing to Your Brain
Reading for pleasure may offer surprising benefits for the brain, with research linking the habit to better mental health, stronger cognitive abilities, and a lower risk of dementia. Reading for pleasure may do far [...]
Scientists Discover a Hidden Trigger That Keeps Inflammation Alive
Inflammation persists after proteins detach from immune receptors, revealing a potential target for autoimmune treatments. Since a Nobel Prize-winning discovery in the 1990s identified molecules called Toll-like Receptors as the guardians of the human [...]
A Virus Gives Itself Away the Moment It Attacks
Researchers have found the trigger behind a powerful bacterial defense against viruses. Viruses that prey on bacteria could become an increasingly important tool for treating bacterial infections, particularly as antibiotic resistance makes some infections [...]















