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

    Сегодня мы публикуем окончательные результаты конкурса по программированию и награждаем победителей.

    По случайности, все трое призёров предпочли участвовать под псевдонимами. Мне кажется, с такими результатами им нечего стесняться. Если вы хотите представиться в комментариях, милости просим!

    Итак, призовые места заняли:
    1. Antelle — 83.67% правильных ответов. Приз 3000 USD.
    2. SHB — 83.11% правильных ответов. Приз 2000 USD.
    3. chianti — 83.00% правильных ответов. Приз 1000 USD.

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

    Полную таблицу результатов смотрите в английской версии на GitHub.
    Hola
    47,00
    Компания
    Поделиться публикацией

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

      +3

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

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

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

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

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

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

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

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

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

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

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

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое