Was there a ML-backed algorithm that learnt to delete list instead of sorting it

Question

Here's a quote from an article which was discussed pretty heavily a while ago:

Well, it’s not unsorted: For example, there was an algorithm that was supposed to sort a list of numbers. Instead, it learned to delete the list, so that it was no longer technically unsorted.

While this sounds funny it seems to me suspicious that this happened at all - any sorting algorithm, though it can be mutable, for obvious reasons suppose to have the same amount of elements in sorted collection.

My question would be - does this really happens and if yes under what circumstances - when exactly, what language has been used, what kind of ML technique has been applied.

Answer 1

Your own article cites its source, which in similar form is a collection of "interesting" outcomes of machine learning experiments. The relevant portion is here:

when MIT Lincoln Labs evaluated GenProg on a buggy sorting program, researchers created tests that measured whether the numbers output by the sorting algorithm were in sorted order. However, rather than actually repairing the program (which sometimes failed to correctly sort), GenProg found an easier solution: it entirely short-circuited the buggy program, having it always return an empty list, exploiting the technicality that an empty list was scored as not being out of order

In turn, that collection cites multiple sources for this anecdote, the most closely related of which appears to be

Weimer W. Advances in Automated Program Repair and a Call to Arms. In: Search Based Software Engineering - 5th International Symposium, SSBSE 2013, St. Petersburg, Russia, August 24-26, 2013. Proceedings; 2013. p. 1–3.

This presentation was available in PDF form on GenProg's website. It indeed asserts largely the same information on slide 45: a sorting algorithm was requested, the algorithm was tested by "is the output sorted?", and the "fix" provided by GenProg was to always output an empty list since it was considered sorted. The author of that presentation is listed as one of the three primary collaborators developing GenProg, so it seems likely that he has sufficient expertise on the matter to know whether this happened, and to me it seems unlikely that he would make up an anecdote about his software giving undesirable results.

The Machine Learning algorithm used is called GenProg, designed for the technique of genetic programming. GenProg is written in OCaml according to its GitHub page, and is primarily used to debug C programs so that is likely the language which technically contained the Sort(List){ return new List;} implementation. It likely occurred sometime between the first publication about GenProg and the cited paper about GenProg, so between 2009 and 2013 according to GenProg's publications page.

With regards to "How could this happen?" I would recommend asking on a site more focused on the technicalities of machine learning such as ai.stackexchange.com or stats.stackexchange.com.

Answer 2

Kamil's answer answers the question correctly, but ends with a suggestion that you ask about why this happened on a different SE. This answer will explain how that outcome can easily be caused by a silly mistake.

---

This kind of machine learning algorithm is based on genetic algorithms, which use a fitness function to describe how good a result is. The algorithm chooses a set of input parameters, produces a result, and grades that result based on the fitness function. If the result has good fitness, it will try other similar things. The paper referenced by the collection of anecdotes describes its fitness function as follows:

The quality of a program variant is assessed using a fitness function. Our fitness function uses the test suite of the original program (i.e., the positive tests) and the negative tests which exercise the bug. The negative tests allow us to determine when a program variant has successfully repaired the bug, and the positive tests ensure that a variant has retained required program behavior.

The machine learning algorithm cannot be better than these tests; If the tests give bad results a high score, the machine learning algorithm will produce bad results. Machine learning only understands what its programmers taught it to understand.