По случайности, все трое призёров предпочли участвовать под псевдонимами. Мне кажется, с такими результатами им нечего стесняться. Если вы хотите представиться в комментариях, милости просим!
Итак, призовые места заняли:
- Antelle — 83.67% правильных ответов. Приз 3000 USD.
- SHB — 83.11% правильных ответов. Приз 2000 USD.
- chianti — 83.00% правильных ответов. Приз 1000 USD.
Нам нужно ещё немного времени, чтобы определиться с тем, кто получит специальные призы. По меньшей мере один из них будет присуждён автору лучшего из самообучающихся решений, о чём будет написан отдельный пост.
Полную таблицу результатов смотрите в английской версии на GitHub.
Комментарии (18)
Gromo
20.06.2016 14:54+4Конкурс был интересным и увлекательным. Победителям — заслуженные поздравления, организаторам — большое спасибо.
Д/З — работа над ошибками и изучение решений в ожидании следующего конкурса :)
avallac
21.06.2016 11:23Кто-нибудь пробовал делать НКА с урезанием самых редко использованных состояний? Этот вариант вообще потенциально возможен?
napa3um
21.06.2016 12:15Я пробовал автоматы, делал префиксное дерево, потом склеил одинаковые ветки деревьев, получив DAFSA/DAWG. В каждом узле завёл четыре счётчика и прогнал 10 млн тестовых слов, инкрементируя счётчики попадания проверяемого слова в узел (два счётчик «да» и «нет» для правильных слов и два для неправильных). Потом пытался сериализовал дерево, вырезав из него длинные промежуточные ветки без ветвлений (заменяя, по-сути, в длинных неветвящихся словах серединку на .* в терминах regexp), а также «редкие» полные ветки по счётчикам. Ещё для критериев обрезки в каждом узле хранилось число, равное количеству байт в сериализованном виде данного узла и всех его дочерних.
Как я ни пытался сериализовывать это дерево в 64 КиБ, как ни резал, выйти за 70% никак не удавалось (даже за 65%). Была попытка генетическим алгоритмом вырастить самых эффективных «обрезаторов» деревьев (схождение получилось ооооочень медленное, переписывать оптимальнее и кластеризовывать не решился, не факт, что результат лучше 70% вообще был достижим, а комментаторы уже хвастались взятием рубежа в 80%).
Потому за пару дней до окончания конкурса бросил возиться с деревом и накатал решение «как у всех» — фильтр Блума, в который закидываются предобработанные слова, предобработка заключалась в выкидывании редких классов слов. У меня классифицируется по длине (выбрасываются слова короче 5 и длиннее 13 букв), по наличию редких букв в первых пяти и последней позициях (каждая позиция независима). Замену последовательностей букв на номера частых сочетаний букв уже не успел реализовать. Ну и выбор вместо пяти первых позиций каких-нибудь других тоже не успел проверить, я просто добавлял позиции по порядку, пока это хоть чуть-чуть улучшало предсказательную силу. Итог — 74% и 73 место.
Antelle
Я сделал небольшую визуализацию результатов, посмотреть можно тут: https://antelle.github.io/hola-challenge-words-charts/
Отдельно там есть статистика по обучающиеся решениям по 50M слов.
feldgendler
Очень интересно. Чем строили графики? Я собираюсь сделать официальное сравнение обучающихся решений, и надо выбрать, чем строить графики.
Antelle
Highcharts. Данные для обучающихся решений получил официальным скриптом для тестирования, остальные загружаются с ваших результатов, выложенных на github в json. Три решения у меня упали на 30..40M, два стали постепенно деградировать (интересно, на чём остановится, у меня терпения не хватило), одно продолжает приближаться к 95..96%.
feldgendler
Я протестировал на миллионе блоков, до конца дожило только одно решение. Сырые данные тоже будут.
Antelle
5748c99463905b3a11d97cdb? Кажется, только в нём прекращается обучение.
Zavtramen
Это мое решение, надеюсь оно выделиться хоть тем, что переживет анлим. тестинг ;)
feldgendler
5747c9f463905b3a11d97c3a
Zavtramen
И тут не повезло. Хотя странно что мое решение не прошло миллион блоков. Я дома его проверял на 2х на вашей тестовой системе и все было ок. Скорее всего это связано с утечками памяти в Node JS. Потому что после 20 миллионов слов я вообще перестаю как-либо расходовать память (так чтобы ее не смог очистить GC по крайней мере).
SabMakc
Должен сказать, что в тестовой системе (test2.js) возможны утечки памяти.
На примере моего решения с обучением:
В дефолтном режиме примерно на 140К блоков падает.
В unsafe режиме на 1М блоков все нормально.
Хотя стоит заметить, что оригинальный тестовый скрипт (из дополнения к конкурсу) не падал как минимум на 200К тестовых блоках.
feldgendler
Потестируем в unsafe.
rodgar
>два стали постепенно деградировать (интересно, на чём остановится, у меня терпения не хватило)
На 500M тестов, с леди-гагавским семенем, 134986 слов имеют частоту появления равной или выше мат. ожидания корректного слова.
Все обучения работают основываясь на нижней границе мат. ожидания (редко — не слово), но верхнюю (слишком часто — тоже не слово) учитывают немногие. Обучение только по нижней границе выделит 630404-134986 корректных слов и сойдется к 78,5%.
Это все в теории, на 500М я только частотность слов смотрел, не запуская реальных алгоритмов.
rodgar
Обманываю. С такой базой будет угадано 50*0,785=39,25% слов и 50% неслов, что дает 89,25%. Если я снова ничего не путаю.
Randl
Раз уж у вас первое место, может напишите историю успеха?
napa3um
https://github.com/hola/challenge_word_classifier/blob/master/submissions/5747452a63905b3a11d97c13/src/README.md
Inkstyle
Наилучшая лицензия.