Мы приносим глубочайшие извинения за длинную задержку при подготовке этого поста. Сегодня мы публикуем анализ самообучающихся решений, присланных на конкурс по программированию, и вручаем два специальных приза.

Английская версия этой записи — на GitHub.

Итак, 9 из присланных решений оказались самообучающимися. Идея самообучения такова: поскольку все слова выбираются из конечного словаря, а не-слова генерируются случайно, то всякая строка, которая была представлена тестируемой программе повторно, с большей вероятностью окажется словом, чем не-словом. При достаточно продолжительном тестировании большинство слов из словаря успеют повториться, тогда как для не-слов случайные повторения встречаются гораздо реже.

Чтобы пронаблюдать поведение самообучающихся решений, мы протестировали их на 1 000 000 блоков. Тестировать на таком количестве блоков все решения было бы нереально, но эти девять оказались достаточно быстрыми.

На графике ниже показана зависимость процента правильных ответов от числа обработанных блоков. Обратите внимание, что горизонтальная шкала — логарифмическая.



Некоторым решениям при тестировании на очень большом числе блоков не хватило памяти, поэтому их линии прерываются, не дойдя до отметки в миллион блоков.

На следующем графике показан не накопительный процент правильных ответов (средний за всё время работы), а только за последние 10 000 блоков в каждой точке. Здесь лучше видно, как решение ведёт себя после определённого объёма обучения.


Ниже — графики частоты ложноотрицательных и ложноположительных результатов, соответственно. Здесь тоже учитывается поведение на последних 10 000 блоках, а не накопительное от начала работы.



Обратите внимание, что результаты у некоторых решений при продолжительном обучении начинают несколько ухудшаться. Очевидно, это происходит из-за того, что некоторые не-слова тоже случайно повторяются, и алгоритм принимает их за слова. На последнем графике видно, что растут именно ложноположительные результаты.

На специальной странице на GitHub можно найти подробные результаты исследования на 1 000 000 блоков.

На основании проведённого исследования мы решили наградить специальными призами по 400 USD участников под псевдонимами rd.nvkz и AndSDev. Их решения достигли высочайших показателей — 93.99% и 93.65% соответственно. Кроме того, их поведение не ухудшается при продолжительном обучении, а у первого из них — даже продолжает улучшаться. Наши поздравления!

Следите за блогом компании Hola! Будут новые конкурсы.