Comments 21
UFO just landed and posted this here
Очень интересно. Чем строили графики? Я собираюсь сделать официальное сравнение обучающихся решений, и надо выбрать, чем строить графики.
UFO just landed and posted this here
Я протестировал на миллионе блоков, до конца дожило только одно решение. Сырые данные тоже будут.
UFO just landed and posted this here
Это мое решение, надеюсь оно выделиться хоть тем, что переживет анлим. тестинг ;)
5747c9f463905b3a11d97c3a
И тут не повезло. Хотя странно что мое решение не прошло миллион блоков. Я дома его проверял на 2х на вашей тестовой системе и все было ок. Скорее всего это связано с утечками памяти в Node JS. Потому что после 20 миллионов слов я вообще перестаю как-либо расходовать память (так чтобы ее не смог очистить GC по крайней мере).
Должен сказать, что в тестовой системе (test2.js) возможны утечки памяти.
На примере моего решения с обучением:
В дефолтном режиме примерно на 140К блоков падает.
В unsafe режиме на 1М блоков все нормально.
Хотя стоит заметить, что оригинальный тестовый скрипт (из дополнения к конкурсу) не падал как минимум на 200К тестовых блоках.
На примере моего решения с обучением:
В дефолтном режиме примерно на 140К блоков падает.
В unsafe режиме на 1М блоков все нормально.
Хотя стоит заметить, что оригинальный тестовый скрипт (из дополнения к конкурсу) не падал как минимум на 200К тестовых блоках.
>два стали постепенно деградировать (интересно, на чём остановится, у меня терпения не хватило)
На 500M тестов, с леди-гагавским семенем, 134986 слов имеют частоту появления равной или выше мат. ожидания корректного слова.
Все обучения работают основываясь на нижней границе мат. ожидания (редко — не слово), но верхнюю (слишком часто — тоже не слово) учитывают немногие. Обучение только по нижней границе выделит 630404-134986 корректных слов и сойдется к 78,5%.
Это все в теории, на 500М я только частотность слов смотрел, не запуская реальных алгоритмов.
На 500M тестов, с леди-гагавским семенем, 134986 слов имеют частоту появления равной или выше мат. ожидания корректного слова.
Все обучения работают основываясь на нижней границе мат. ожидания (редко — не слово), но верхнюю (слишком часто — тоже не слово) учитывают немногие. Обучение только по нижней границе выделит 630404-134986 корректных слов и сойдется к 78,5%.
Это все в теории, на 500М я только частотность слов смотрел, не запуская реальных алгоритмов.
Раз уж у вас первое место, может напишите историю успеха?
Конкурс был интересным и увлекательным. Победителям — заслуженные поздравления, организаторам — большое спасибо.
Д/З — работа над ошибками и изучение решений в ожидании следующего конкурса :)
Д/З — работа над ошибками и изучение решений в ожидании следующего конкурса :)
Кто-нибудь пробовал делать НКА с урезанием самых редко использованных состояний? Этот вариант вообще потенциально возможен?
Я пробовал автоматы, делал префиксное дерево, потом склеил одинаковые ветки деревьев, получив DAFSA/DAWG. В каждом узле завёл четыре счётчика и прогнал 10 млн тестовых слов, инкрементируя счётчики попадания проверяемого слова в узел (два счётчик «да» и «нет» для правильных слов и два для неправильных). Потом пытался сериализовал дерево, вырезав из него длинные промежуточные ветки без ветвлений (заменяя, по-сути, в длинных неветвящихся словах серединку на .* в терминах regexp), а также «редкие» полные ветки по счётчикам. Ещё для критериев обрезки в каждом узле хранилось число, равное количеству байт в сериализованном виде данного узла и всех его дочерних.
Как я ни пытался сериализовывать это дерево в 64 КиБ, как ни резал, выйти за 70% никак не удавалось (даже за 65%). Была попытка генетическим алгоритмом вырастить самых эффективных «обрезаторов» деревьев (схождение получилось ооооочень медленное, переписывать оптимальнее и кластеризовывать не решился, не факт, что результат лучше 70% вообще был достижим, а комментаторы уже хвастались взятием рубежа в 80%).
Потому за пару дней до окончания конкурса бросил возиться с деревом и накатал решение «как у всех» — фильтр Блума, в который закидываются предобработанные слова, предобработка заключалась в выкидывании редких классов слов. У меня классифицируется по длине (выбрасываются слова короче 5 и длиннее 13 букв), по наличию редких букв в первых пяти и последней позициях (каждая позиция независима). Замену последовательностей букв на номера частых сочетаний букв уже не успел реализовать. Ну и выбор вместо пяти первых позиций каких-нибудь других тоже не успел проверить, я просто добавлял позиции по порядку, пока это хоть чуть-чуть улучшало предсказательную силу. Итог — 74% и 73 место.
Как я ни пытался сериализовывать это дерево в 64 КиБ, как ни резал, выйти за 70% никак не удавалось (даже за 65%). Была попытка генетическим алгоритмом вырастить самых эффективных «обрезаторов» деревьев (схождение получилось ооооочень медленное, переписывать оптимальнее и кластеризовывать не решился, не факт, что результат лучше 70% вообще был достижим, а комментаторы уже хвастались взятием рубежа в 80%).
Потому за пару дней до окончания конкурса бросил возиться с деревом и накатал решение «как у всех» — фильтр Блума, в который закидываются предобработанные слова, предобработка заключалась в выкидывании редких классов слов. У меня классифицируется по длине (выбрасываются слова короче 5 и длиннее 13 букв), по наличию редких букв в первых пяти и последней позициях (каждая позиция независима). Замену последовательностей букв на номера частых сочетаний букв уже не успел реализовать. Ну и выбор вместо пяти первых позиций каких-нибудь других тоже не успел проверить, я просто добавлял позиции по порядку, пока это хоть чуть-чуть улучшало предсказательную силу. Итог — 74% и 73 место.
>Нам нужно ещё немного времени, чтобы определиться с тем, кто получит специальные призы.
Не сочитет за дерзость, но много ли еще времени необходимо?
Не сочитет за дерзость, но много ли еще времени необходимо?
А отдельный пост еще планируется?
Sign up to leave a comment.
Конкурс по программированию на JS: Классификатор слов (окончательные результаты)