Конкурс по программированию на JS: Классификатор слов (о ходе тестирования)
Прежде всего, мы приносим всем участникам конкурса по программированию извинения за задержку с результатами. Сегодня мы публикуем все присланные решения и официальные скрипты для генерации тестов и тестирования, а также рассказываем, как идут дела с проверкой решений.
Английская версия этого поста размещена на GitHub.
Протестировать 312 решений
Большое спасибо всем участникам! Мы получили 603 решения от 312 участников. Поскольку мы принимаем к тестированию самое последнее из присланных в срок решений, то протестировать надо 312 решений. Это был неожиданный результат. Надеюсь, это немного объясняет, почему это занимает так много времени.
Мы опубликовали все принятые к тестированию решения в директории submissions на GitHub. Имя каждой поддиректории — это уникальный идентификатор решения; если Вы присылали нам решение, то получили автоматическое письмо с подтверждением, в котором содержится этот идентификатор. Имена или псевдонимы авторов решений будут опубликованы вместе с окончательными результатами.
В каждой директории содержится файл solution.js (собственно конкурсное решение) и, если он есть, файл данных data или data.gz (если он сжат с помощью gzip). Эта раскладка соответствует тому, что ожидают официальные скрипты тестирования. В поддиректории src содержатся исходники, которые автор прислал в дополнительном архиве. Скрипты тестирования не обращают на них внимания.
Разумеется, внести изменения в своё решение уже невозможно. Однако можно прислать нам те или иные дополнительные файлы, которые Вы хотели бы опубликовать в директории src, но не включили в архив с исходниками, например, файл README. Это не повлияет на результат тестирования, но если мы сможем лучше понять решение, это может увеличить Ваши шансы на получение специального приза за оригинальность. Если хотите прислать дополнительные файлы, напишите нам письмо.
Генератор тестов
Как обещали, мы публикуем генератор тестов. Это интерфейс командной строки к тому же модулю, который мы применяли в веб-сервисе для генерации тестов. Для одних и тех же начальных значений генератора псевдослучайных чисел этот генератор гарантированно выдаёт те же самые результаты, что и веб-сервис. Опция --help выдаёт инструкцию.
При запуске генератор анализирует словарь и строит марковские модели различных порядков (поэтому инициализация генератора занимает значительное время). Затем он использует генератор псевдослучайных чисел для генерации тестовых наборов. С вероятностью ½ выбирается случайное слово из словаря, а в остальных случаях — для генерации используется случайно выбранная из 9 моделей: это цепи Маркова порядков от 1 до 8 и генератор белого шума. Чем выше порядок марковской модели, тем более похожи её результаты на английские слова. Если случайно получилось слово, присутствующее в словаре, оно отбрасывается, и генерируется новое. Поскольку такое чаще происходит с моделями высоких порядков, в тестах не-слова, сгенерированные этими моделями, встречаются несколько реже, чем сгенерированные моделями низких порядков. Если Вас интересуют подробности, рекомендуем прочесть исходники генератора.
Для серьёзного тестирования необходимо большое число блоков по 100 слов. Для их генерации мы используем текстовую строку («seed string») для инициализации мастер-последовательности псевдослучайных чисел, из которой берутся номера блоков. Из одной строки всегда получается одна и та же последовательность блоков, которую можно продолжать неограниченно.
Через несколько дней веб-версия генератора тестов будет отключена. Пожалуйста, пользуйтесь вместо неё генератором, который выдаст точно такие же результаты у Вас на компьютере.
«Боевая» тестовая система
Для массового тестирования решений мы разработали новую, более мощную и гибкую тестовую систему. Опция --help выдаёт инструкцию.
Новая тестовая система функционально эквивалентна старой, то есть для одних и тех же тестов и тестируемых программ обе системы выдадут одинаковые результаты. Вот отличительные особенности новой системы:
- Несколько решений могут тестироваться параллельно. Для этого их надо перечислить в командной строке одно за другим. (Как для первого скрипта, надо указывать имена директорий с решениями, а не пути к файлам.)
- Решения запускаются в отдельных процессах, которые получают от главного процесса слова и отправляют обратно ответы.
- Вместо чтения тысяч JSON-файлов с тестами, новая система генерирует тесты на лету с помощью генератора на основе строки для инициализации мастер-последовательности. Это полностью детерминировано и воспроизводимо.
- Новая система подсчитывает гораздо больше статистики, чем один только процент правильных ответов. В ходе тестирования она регулярно обновляет эту статистику на консоли. Возможна также запись результатов тестирования в машиночитаемый JSON-файл.
- По желанию, тестовая программа может перезапускать и переинициализировать решение всякий раз, когда в тесте встретился повтор (слово, которое уже встречалось). Это позволяет изолировать и измерить эффект от обучения в ходе тестирования, которое осуществляют некоторые решения.
- Можно выбрать «опасный» режим, при котором решение загружается как обычный модуль Node.js, без «песочницы». Его можно (с осторожностью) использовать, если возникли подозрения, что Node.js VM вносит искажения в работу решения.
Вот что означает статистика, отображаемая на экране во время тестирования. Верхняя строка: Total — общее число проверенных слов, W — число слов, NW — число не-слов, NW[0]…NW[8] — число не-слов, произведённых каждой из моделей: 0 означает генератор белого шума, а 1–8 — цепи Маркова соответствующих порядков. Для каждого решения: Correct — процент правильных ответов (это именно то, что определяет место в итоговом зачёте), F- — процент ложноотрицательных результатов, F+ — процент ложноположительных результатов, F+[0]…F+[8] — процент ложноположительных результатов для каждой модели в отдельности, ms/100w — среднее время обработки одного блока в миллисекундах. Если решение перезапускается при появлении дубликатов, то слева от его имени показывается (R). В машиночитаемом JSON-файле с результатами содержится вся та же информация в интуитивно понятном формате.
Официальная последовательность тестов
Мы открыли Твиттер @ladygaga:-) и взяли оттуда первый твит, появившийся после дедлайна. Текст этого твита стал официальной строкой инициализации последовательности. Для генерации официальной последовательности тестов Вы можете указать следующую опцию для скриптов generate.js и test2.js:
--text 'Lady Gaga has accompanied Mario Andretti in a two-seater race car at #Indy500 today!'
(Дополнение: к сожалению, этот твит уже удалили. Остался только этот ретвит. Поскольку тестирование уже запущено, строку инициализации не меняем.)
Начало последовательности (номера блоков) такое: 416943456, 1130928813, 1690493249, 1560679505, 1146154276, 403245362, 1509995579, 2138666856, 1841363379, 1083285606.
Число блоков и самообучение
Сначала мы прогнали все решения на совсем небольшом числе блоков, чтобы узнать, у каких решений есть шансы оказаться в лидерах. Затем мы взяли 8 подающих надежды решений и запустили их на очень большом числе блоков. При нескольких различных строках инициализации первые три строки рейтинга стабилизировались в пределах первых 1 500 блоков: дальнейшее увеличение числа блоков хоть и уточняло доли процента, но не меняло взаимного расположения лидеров. Мы решили тестировать все решения на 10 000 блоков (это миллион слов).
Некоторые решения применяют оригинальный подход: они запоминают все слова, которые предъявляет им тестовая система. Поскольку слов в словаре меньше 700 000, а разнообразие псевдослучайных не-слов гораздо шире, то слово, встретившееся дважды, с большей вероятностью является словом, чем не-словом. У решений, пользующихся этим явлением, точность результатов со временем возрастает. Теоретически, при неограниченном росте числа блоков, такое решение может показать сколь угодно высокий результат.
Это интересная идея, но для конкурса это проблема, поскольку теоретически на достаточно большом наборе тестов такое решение может обойти любые необучающиеся решения. Это не только сделало бы этот нехитрый приём «волшебной палочкой», побеждающей всё остальное, но и создало бы для жюри проблему выбора между несколькими обучающимися решениями. Если бы эта идея возникла у нас до начала конкурса, мы могли бы легко решить проблему, указав, что тестовая система может перезапустить решение в любой момент в ходе тестирования. Однако мы в явном виде обещали, что инициализация произойдёт только один раз.
Мы решили остановиться на цифре в 10 000 блоков и прогнать каждое решение как с перезапусками, так и без, чтобы отдельно измерить эффект обучения. Результаты необучающихся решений за это время вполне успевают стабилизироваться. Обучение действительно улучшает результат некоторых решений (пока что мы видим одно решение, попавшее в десятку лучших именно благодаря обучению). Конечно, обучающиеся решения показали бы ещё более высокие результаты на большем числе блоков, но это было бы несправедливо по отношению тем участникам, чьи программы показывают высокую точность распознавания сразу после инициализации.
Вкратце: мы позволяем обучающимся решениям обучаться, но не используем такие огромные количества блоков, на которых эффект обучения становится решающим.
Статус
В данный момент некоторые решения всё ещё проходят тестирование.
Мы не указали в условии задачи каких-либо требований к производительности программ. Если бы мы указывали ограничения, пришлось бы точно описывать железо и операционную систему, запускать решения по множеству раз для точного измерения, решать проблемы с искажениями, вносимыми «песочницей». От проблем измерения производительности хотелось уйти. Вследствие этого некоторые из решений, которые мы получили, работают очень медленно.
Тестирование некоторых из решений до сих пор не окончено. Самые медленные из них, похоже, нам придётся остановить досрочно и использовать результаты частичного прогона тестов. На данный момент ни одно из таких решений в десятку лучших не попадает. Кроме того, по меньшей мере одно решение зависло. Мы разберёмся, вносит ли эту проблему «песочница», или это баг в самом решении.
Через несколько дней, когда закончится тестирование медленных решений, мы опубликуем результаты. Уже сейчас Вы можете узнать свой собственный результат, не дожидаясь публикации всей таблицы. Воспользуйтесь для этого новой тестовой системой и указанной выше официальной строкой инициализации. Задайте 10 000 блоков, и Вы получите в точности тот же результат, что и мы (если только Ваше решение не использует Math.random — в этом случае результаты будут слегка различаться). Пока что лучший результат, который мы видели на 10 000 блоках — 83.67%.
Спасибо за терпение. Оставайтесь с нами!
