Glider from the game of Life, rising from the left




Topic: #machine-learning

Machine Learning Sorting


“An O(N) Sorting Algorithm: Machine Learning Sorting”
Hanqing Zhao and Yueban Luo, arXiv, May 11, 2018

The authors propose a new method for sorting a gigantic array of arbitrary values in linear time: Select a fixed number (say 1000) values from the array and sort them. Using these values as a training set, train a three-layer neural network to estimate the position in the sorted array that any given value will occupy. Set up an array of buckets equal in size to the original array. Feed each value in the array into the neural network and put it in the bucket corresponding to the network's prediction of the value's position in the sorted array. A linear-time amount of post-processing can now ensure that every value is in a bucket that is within a fixed distance of its position in the sorted array. Apply insertion sort on the almost-sorted values in the array of buckets to build the actual sorted array. Since insertion sort runs in linear time on almost-sorted arrays, the whole process, including the training of the neural network, takes linear time.

I wouldn't have thought of that one.

Next month in arXiv: Adversarial sorting examples.

#algorithms #machine-learning #connections

An Intelligibility Crisis in Machine Learning


A surprising amount of research in artificial intelligence, and particularly in the field of machine learning, is being carried out by people who don't understand what they are doing, and yielding software that behaves in ways that are impossible to explain or understand. As a result, much of the work is difficult or impossible to reproduce or confirm.

“AI Researchers Allege that Machine Learning Is Alchemy”
Matthew Hutson, Science, May 3, 2018

#artificial-intelligence #machine-learning #intelligibility-crisis

An Overview of Research on Adversarial Examples


A snapshot of the state of research on adversarial examples at the time of publication (February 2017). It's partial, but there are a lot of links that look useful.

“Attacking Machine Learning with Adversarial Examples”
Ian Goodfellow, Nicolas Papernot, Sandy Huang, Yan Duan, Pieter Abbeel, and Jack Clark, OpenAI, February 24, 2017

#adversarial-examples #machine-learning #black-box-deciders

Complex AI Decision-Making through Debates


In many contexts, it would be foolish to trust software decision systems that cannot explain or justify their decisions. However, the structure of neural networks seems to preclude explanations that use concepts and categories that are sufficiently high-level to be intelligible to human beings.

One approach to making black-box deciders more trustworthy is to make their training sets less noisy, so that they more accurately reflect the actual goals and interests of the human users of the system. In complex decision-making, one difficulty is that human beings are not very accurate in assessing complex situations and determining what the “right” solution should be.

Some anonymous researchers at Open AI propose to provide human trainers with two AI assistants, one to find the best justification for a decision and the other to challenge and rebut that justification. Before pronouncing on each training example, the human trainer listens to a debate between these two systems and decides which of them is right. The theory is that the AIs can dumb down their descriptions of the situation to the point where even a human being can judge it accurately.

“AI Safety via Debate”
Geoffrey Irving and Dario Amodei
OpenAI, May 3, 2018

One approach to aligning AI experts with human goals and preferences is to ask humans at training time which behaviors are safe and useful. While promising, this method requires humans to recognize good or bad behavior; in many situations an agent's behavior may be too complex for a human to understand, or the task itself may be hard to judge or demonstrate. Examples include environments with very large, non-visual observation spaces — for instance, an agent that acts in a computer security-related environment, or an agent that coordinates a large set of industrial robots.

How can we augment humans so that they can effectively supervise advanced AI systems? One way is to take advantage of the AI itself to help with the supervision, asking the AI (or a separate AI) to point out flaws in any proposed action. To achieve this, we reframe the learning problem as a game played between two agents, where the agents have an argument with each other and the human judges the exchange. Even if the agents have a more advanced understanding of the problem that the human, the human may be able to judge which agent has the better argument (similar to expert witnesses arguing to convince a jury). …

There are some fundamental limitations to the debate model that may require it to be improved or augmented with other methods. Debate does not attempt to address issues like adversarial examples or distributional shift — it is a way to get a training signal for complex goals, not a way to guarantee robustness of such goals.

It's sad that the designers and advocates of this method automatically frame it as a possible way to overcome some of the deficiencies of human trainers rather than as a way of overcoming the opacity and inexplicability of deep neural networks, which is one of the fundamental flaws of black-box deciders and a key reason that they can't be trusted in cases where explicability is crucial. To my mind, a debate between opposing AIs would be even more useful during testing and in real-world use than at the training stage. Such a debate might expose a valid high-level rationale for accepting or rejecting the output of a black-box decider, and also might reveal that no such rationale exists.

#black-box-deciders #artificial-intelligence #machine-learning

Inadequate Record-Keeping in Machine-Learning Research


It appears that many researchers in machine learning, including some who profess to be scientists, are not keeping proper records of their experiments. Even with the assistance of version-control systems, they often fail to write down which versions of code libraries they are using, where their data sets come from and what they contain, how they massaged and cleaned their data sets, and what tweaks they made to their algorithms and to the configuration and initialization of their networks.

They redesign their experiments on the fly, interrupt and restart them, cherry-pick results from various runs, and reuse partially trained neural networks as starting points for subsequent experiments without properly documenting the process.

As a result, machine learning as a discipline is now facing a devastating crisis: researchers cannot reproduce one another's experiments, or even their own, and so cannot confirm their results.

“The Machine Learning Reproducibility Crisis”
Pete Warden, Pete Warden's Blog, March 19, 2018

In many real-world cases, the research won't have made notes or remember exactly what she did, so even she won't be able to reproduce the model. Even if she can, the frameworks the model code depend[s] on can change over time, sometimes radically, so she'd need to also snapshot the whole system she was using to ensure that things work. I've found ML researchers to be incredibly generous with their time when I've contacted them for help reproducing model results, but it's often [a] months-long task even with assistance from the original author.

#machine-learning #reproducibility #scientific-method

Diminishing Returns from Deep Learning


An overview of the recent achievements, acknowledged limitations, and plausible extensions of multi-level neural networks suggests that this approach to artificial intelligence is nearly played out and must be supplemented by alternative approaches in order to make further progress.

In section 3, the author identifies ten “limits on the scope of deep learning,” including some that I would consider critical and ineradicable (see section 3.5, “Deep Learning Thus Far Is Not Sufficiently Transparent,” and section 3.9, “Deep Learning Thus Far Works Well as an Approximation, But Its Answers Often Cannot Be Fully Trusted”).

“Deep Learning: A Critical Appraisal”
Gary Marcus, arXiv, January 2018

The transparency issue, as yet unsolved, is a potential liability when using deep learning for problem domains like financial trades or medical diagnosis, in which human users might like to understand how a given system made a given decision. … Such opacity can also lead to serious issues of bias.

None of Marcus's proposals for supplementing machine learning addresses either the transparency problem or the problem posed by adversarial examples.

#machine-learning #black-box-deciders #neural-networks

Defenses against Adversarial Examples Fail


Several of the papers to be presented at this year's International Conference on Learning Representations propose strategies for blocking the construction of adversarial examples against machine-learning-based image-classification systems. The goal is to harden such systems enough to make them usable even in high-risk situations in which adversaries can select and control the inputs that the fully trained systems are expected to classify.

Once these post hoc defenses are incorporated into the systems, however, it is possible to devise more specialized attacks against them, resulting in new, even more robust adversarial examples:

“Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples”
Anish Athalye, Nicholas Carlini, and David Wagner, arXiv, February 1, 2018

That's the full paper. If it's tl;dr, there's a summary here, with a cat picture that even well-defended classifiers consider to be guacamole.

“Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples”
Anish Athalye, Nicholas Carlini, and David Wagner, GitHub, February 2, 2018

#adversarial-examples #image-classifiers #machine-learning

Hashtag index

This work is licensed under a Creative Commons Attribution-ShareAlike License.

Atom feed

John David Stone (

created June 1, 2014 · last revised December 10, 2018