Как стать автором
Обновить

Конкурс по программированию на JS: Классификатор слов (окончательные результаты)

Время на прочтение 1 мин
Количество просмотров 9K
Всего голосов 14: ↑14 и ↓0 +14
Комментарии 21

Комментарии 21

Я сделал небольшую визуализацию результатов, посмотреть можно тут: https://antelle.github.io/hola-challenge-words-charts/
Отдельно там есть статистика по обучающиеся решениям по 50M слов.

Очень интересно. Чем строили графики? Я собираюсь сделать официальное сравнение обучающихся решений, и надо выбрать, чем строить графики.

Highcharts. Данные для обучающихся решений получил официальным скриптом для тестирования, остальные загружаются с ваших результатов, выложенных на github в json. Три решения у меня упали на 30..40M, два стали постепенно деградировать (интересно, на чём остановится, у меня терпения не хватило), одно продолжает приближаться к 95..96%.

Я протестировал на миллионе блоков, до конца дожило только одно решение. Сырые данные тоже будут.

5748c99463905b3a11d97cdb? Кажется, только в нём прекращается обучение.

Это мое решение, надеюсь оно выделиться хоть тем, что переживет анлим. тестинг ;)
5747c9f463905b3a11d97c3a
И тут не повезло. Хотя странно что мое решение не прошло миллион блоков. Я дома его проверял на 2х на вашей тестовой системе и все было ок. Скорее всего это связано с утечками памяти в Node JS. Потому что после 20 миллионов слов я вообще перестаю как-либо расходовать память (так чтобы ее не смог очистить GC по крайней мере).
Должен сказать, что в тестовой системе (test2.js) возможны утечки памяти.
На примере моего решения с обучением:
В дефолтном режиме примерно на 140К блоков падает.
В unsafe режиме на 1М блоков все нормально.

Хотя стоит заметить, что оригинальный тестовый скрипт (из дополнения к конкурсу) не падал как минимум на 200К тестовых блоках.
Потестируем в unsafe.
>два стали постепенно деградировать (интересно, на чём остановится, у меня терпения не хватило)
На 500M тестов, с леди-гагавским семенем, 134986 слов имеют частоту появления равной или выше мат. ожидания корректного слова.
Все обучения работают основываясь на нижней границе мат. ожидания (редко — не слово), но верхнюю (слишком часто — тоже не слово) учитывают немногие. Обучение только по нижней границе выделит 630404-134986 корректных слов и сойдется к 78,5%.
Это все в теории, на 500М я только частотность слов смотрел, не запуская реальных алгоритмов.
Обманываю. С такой базой будет угадано 50*0,785=39,25% слов и 50% неслов, что дает 89,25%. Если я снова ничего не путаю.

Раз уж у вас первое место, может напишите историю успеха?

https://github.com/hola/challenge_word_classifier/blob/master/submissions/5747452a63905b3a11d97c13/src/README.md
Наилучшая лицензия.
Конкурс был интересным и увлекательным. Победителям — заслуженные поздравления, организаторам — большое спасибо.
Д/З — работа над ошибками и изучение решений в ожидании следующего конкурса :)
Кто-нибудь пробовал делать НКА с урезанием самых редко использованных состояний? Этот вариант вообще потенциально возможен?
Я пробовал автоматы, делал префиксное дерево, потом склеил одинаковые ветки деревьев, получив DAFSA/DAWG. В каждом узле завёл четыре счётчика и прогнал 10 млн тестовых слов, инкрементируя счётчики попадания проверяемого слова в узел (два счётчик «да» и «нет» для правильных слов и два для неправильных). Потом пытался сериализовал дерево, вырезав из него длинные промежуточные ветки без ветвлений (заменяя, по-сути, в длинных неветвящихся словах серединку на .* в терминах regexp), а также «редкие» полные ветки по счётчикам. Ещё для критериев обрезки в каждом узле хранилось число, равное количеству байт в сериализованном виде данного узла и всех его дочерних.

Как я ни пытался сериализовывать это дерево в 64 КиБ, как ни резал, выйти за 70% никак не удавалось (даже за 65%). Была попытка генетическим алгоритмом вырастить самых эффективных «обрезаторов» деревьев (схождение получилось ооооочень медленное, переписывать оптимальнее и кластеризовывать не решился, не факт, что результат лучше 70% вообще был достижим, а комментаторы уже хвастались взятием рубежа в 80%).

Потому за пару дней до окончания конкурса бросил возиться с деревом и накатал решение «как у всех» — фильтр Блума, в который закидываются предобработанные слова, предобработка заключалась в выкидывании редких классов слов. У меня классифицируется по длине (выбрасываются слова короче 5 и длиннее 13 букв), по наличию редких букв в первых пяти и последней позициях (каждая позиция независима). Замену последовательностей букв на номера частых сочетаний букв уже не успел реализовать. Ну и выбор вместо пяти первых позиций каких-нибудь других тоже не успел проверить, я просто добавлял позиции по порядку, пока это хоть чуть-чуть улучшало предсказательную силу. Итог — 74% и 73 место.
>Нам нужно ещё немного времени, чтобы определиться с тем, кто получит специальные призы.
Не сочитет за дерзость, но много ли еще времени необходимо?
А отдельный пост еще планируется?
Да-да, извините за задержку.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий