Конкурс по программированию на 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 вносит искажения в работу решения. Разумеется, своему собственному решению Вы доверяете, поэтому всегда использовать --unsafe при его тестировании — хорошая идея для улучшения производительности.

    Вот что означает статистика, отображаемая на экране во время тестирования. Верхняя строка: 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%.

    Спасибо за терпение. Оставайтесь с нами!
    Hola
    47.21
    Company
    Share post

    Comments 103

      0
      Мы решили тестировать все решения на 10 000 блоков (это миллион слов).

      А счастье было так близко.
        +5
        Ну тут есть ещё и практический смысл: тестировать на значительно большем числе блоков пришлось бы очень долго.
          +2
          Я без претензий, организаторам все равно пришлось бы принять какое-то решение и остановиться на каком-либо кол-ве блоков. Что собственно и произошло.
          0
          Да, надо было добавить какие то ограничения, хотя бы количество блоков.
            +4
            Если бы мы заранее зафиксировали количество блоков, то могли бы столкнуться с ситуацией, когда решения лидеров показывают практически неразличимые результаты. Тогда тоже был бы скандал, требования выдать приз каждому, пересчитать по-новому, протесты и т.п.
              0
              А что если бы не было метода init был бы только test. И запускался бы скрипт каждый раз с нуля. Тогда было бы справедливее.
                +2
                Это длилось бы вечно, у меня в init, например, распаковка данных идет.
                  +2
                  Можно было бы и по-другому изменить правила. Но единственный способ всё предвидеть — провести конкурс, а дважды с одной задачей конкурс не проводят.
            +1
            У кого есть суперкомпьютер, помогите Hola посчитать)
              +2
              Мы считаем на AWS, просто некоторые решения работают очень долго. Одно решение может работать только на одном ядре, а ядер сильно быстрее 3 ГГц сейчас не бывает.
              0
              Рад, что у меня в результате стабильные 77% как и при моем тестировании до отправки решения :-) Пошел смотреть какой результат минимальный.
                0

                а можно ссылочку и на вашу работу? спасибо :)

                  0
                  https://github.com/hola/challenge_word_classifier/blob/master/submissions/57437474a6200f1877712208/src/index.js
                –1
                > Это не только сделало бы этот нехитрый приём «волшебной палочкой»
                Пробежавшись по 40 случайно выбранным решениям я увидел 2 обучения. Пусть я пропустил половину и их 4. Т.е. в районе 10%.
                Вы называете это «волшебной палочкой», в комментариях были высказывания в духе «читерство» и «легкий путь». Хотелось бы сказать что, во-первых, этот путь совсем не легкий и не лежит на поверхности. Иначе бы его применили не 10% участников, а значительно больше. Тот факт что организаторы сами этого не предусмотрели является дополнительным доводом «простоты» и «волшебности». До него действительно нужно додуматься, и, мне кажется, это чуть труднее чем взять предложенный в комментариях фильтр Блума, оказавшийся одним из лучших вариантов решения задачи. Во-вторых качественная имплементация обучения, опять же по моему мнению, ничуть не проще Блума. Таким образом, лично я не вижу никакой «волшебной палочки».

                > но и создало бы для жюри проблему выбора между несколькими обучающимися решениями
                В коментариях к своему решению я предлагл один из возможных вариантов решения этой проблемы: запускать обучающиеся алгоритмы по времени. Кто смог обработать большее кол-во слов за час и лучше на них обучится (а в обучении всегда есть сильный трейдофф скорость-память-качество), тот и лучший.

                Да, я с самого начала понимал что истинная задача конкурса — разработать лучшее, в том числе по занимаемой памяти, решение для задачи проверки орфографии пользовательского ввода в браузере. Но условия задачи формализуют ее в несколько другом аспекте, довольно далеком от реальной задачи. И обучение удовлетворяет *всем* формальным условиям задачи. Для полной честности, осталось признать что вы изменили условия задачи в пункте «столько тестов, сколько потребуется». Почему-то в тексте этой фразы нет.

                Напоследок хотелось бы вспомнить Джордано Бруно, пострадавшего лишь за то, что он изучил все имеющиеся факты и сделал непротиворечивое заявление. Но оно, на тот день, никого не интересовало.
                Спасибо за конкурс…
                  +3
                  Конечно же, можно было запускать с ограничением по времени или ещё как-то. Но всё это было бы изменением по сравнению с заявленными правилами конкурса.

                  > Для полной честности, осталось признать что вы изменили условия задачи в пункте «столько тестов, сколько потребуется».

                  Не понял, что Вы имеете в виду. Что конкретно мы изменили?
                    0
                    Я имел ввиду ваш комментарий
                    >вопрос к организаторам — а вы можете сказать какое будет минимальное кол-во блоков для тестирования?
                    >>Такое, какое потребуется, чтобы увидеть уверенную разницу между лидерами.
                    Я считаю что на 1М тестов уверенную разницу между лидерами увидеть нельзя. Более того, такое кол-во тестов даже не позволяет этих лидеров выявить. Руководствуясь описанными в посте посылами, можно было установить лимит на 1000 тестов, или на 10. Это точно так же не позволило бы ни выявить лидеров, ни выявить уверенную разницу между ними.
                    Не могли бы вы еще раз, для непонятливых, привести причины выбора именно 1М тестов, кроме уже описанной проблемы ограниченности ядер 3ГГц.
                      +3
                      Среди необучающихся программ стабилизация тройки лидеров произошла уже на 1 500 блоках. Дальнейшее увеличение объёмов уточняло лишь сотые доли процента, не меняя расстановки сил. Нет никаких оснований полагать, что далеко после 10 000 блоков произошло бы что-то неожиданное.
                        +3
                        >Нет никаких оснований полагать, что далеко после 10 000 блоков произошло бы что-то неожиданное.
                        Ну, например на 200 000 блоков мое решение бы показало 90%. Согласен, ничего неожиданного и вполне предсказуемо.

                        Еще можно было определить «параметр стабилизации: если за 1000 блоков результат улучшился менее 0,1% значит результат стабилен». Кажется даже никаких условий конкурса не меняем.

                        Хорошо, сойдемся на дискриминации по признаку применения обучения =)
                        В каком-нибудь параллельном мире ваша фраза могла бы выглядеть как
                        «Среди всех программ стабилизация тройки лидеров произошла уже на 150 000 блоках. Дальнейшее увеличение объёмов уточняло лишь сотые доли процента, не меняя расстановки сил.» Постараюсь найти мощности для проверки этого утверждения и время для написания статьи.
                        Еще раз: ваша мотивация понятна, претензий не имею. Небольшой укор за умершие от волнительного ожидания нервные клетки, но в целом за конкурс спасибо.
                          +1

                          а можно ссылочку на вашу работу. спасибо :)

                            +2
                            https://github.com/hola/challenge_word_classifier/tree/master/submissions/5747c9f463905b3a11d97c3a
                            Но вряд ли вы найдете там что-то интересное. Сплошное читерство и волшебствопалочничество. Примерно того же уровня, как если бы я придумал как скачать словарь из интернета. Хоть не дисквалифицировали, уже спасибо =)
                            Кстати, запрошенные 200 000 блоков мое решение обрабатывает менее чем за час. А в полную силу начинает работать только после 40 000 блоков. Немного утрируя, можно сказать что в озвученных условиях тестирования запускается только половина кода.
                              0
                              Многие решения работают быстро, и протестировать их на большом количестве блоков не было бы проблемой. Однако есть решения, работающие на порядки медленнее Вашего.
                                –2
                                Не удержусь промолчать в последний раз.

                                Вы в любом случае пришли к мысли
                                >Самые медленные из них, похоже, нам придётся остановить досрочно и использовать результаты частичного прогона тестов.
                                Теоретически, ничего не мешало сделать все тоже самое на гораздо большем кол-во блоков. Алгоритмы, не сумевшие обработать 100М слов за 2 недели между окончанием конкурса и объявлением результатов — извините, ваш результат по итогам частичной проверки. 100М за 2 недели это по 100 слов в секунду, полный неуд на мой взгляд. А если нужно проверить 3000 слов, скопированных в текстовое поле? Подождите 30 секунд, мы проверяем?

                                Кстати, если аудитория браузера составляет 50'000 ежедневных пользователей, и каждый из них пишет хотя бы 10 слов в день, то за год набирается 180М слов. Цифры то вполне из реального мира. Почему бы не делать проверку орфографии онлайн? Тот же хром иногда подчеркивает слово спустя секунды после написания, ничего критичного.
                                  +1
                                  Конечно, мы не обрабатывали слова две недели. Писали алгоритмы тестирования, отлаживали их, да и другой работой тоже приходится заниматься. Но несколько суток считается, да.
                                +1

                                Спасибо еще раз за ссылочку. Я думал это написать используя hidden markov model, но увы лень,проекты — не успел.


                                PS:


                                let parts = [], cnt = ~~(word.length  / window) + (word.length % window ? 1 : 0);

                                Любите вы изощренность :)

                                  0
                                  Прочитать свой код в воскресенье на свежую голову и понять всю глубину изощренности. Для всего остального есть master card.
                                  Жаль hexlet закрыл игры. Отличная была мерялка в извращенности против нодистов.
                                  0
                                  Почитал ваше решение. Правильно понимаю, вы не учитывали тот факт, что для 20-30к «не слов» вероятность обнаружения в тестовой выборке не ниже чем для «корректных слов»? Если не учитывает, то ваш алгоритм не сойдется никогда в 100%, максимум в 95%.
                                    0
                                    Я анализировал подобные выбросы генератора. Слова из одной, двух и трех букв встречаются аномально часто.
                                    Таких слов 27 + 27**2 + 27**3 = 20'439, из них вроде бы 12к неправильные.Думаю вы имеете ввиду именно их. Я просто перечислил все ложные двойки и настоящие тройки. В коде смотреть banned2 и allowed3 соот-но.
                                    Количество четверок уже сравнимо с количеством слов, 531'441 и их мат. ожидание не превышает мат. ожидания корректного слова.
                                    После 63 040 400 тестов база знает 99,9% корректных слов. Оставшиеся 0,01% превышения это абсолютно правильная дисперсия хорошего рандома: https://habrahabr.ru/company/hola/blog/282624/#comment_8878212
                                    В начале обучения мы точно допускаем ошибки, чистые 100% в любом случае не достижимы.
                                      0
                                      Не совсем. Я имел в виду, что вероятность встретить «не слова», такие как «under's» или «dising» примерно в 20 раз выше, чем встретить слово из словаря. И таких слов достаточно много. Например «blenesses» и «unreproof» встречаются также часто как и словарные слова. Видимо, это связано с природой марковского генератора.
                                      То есть, при таком подходе, после 60 млн тестов база будет включать определенный процент (по моим оценкам около 5%) ложноположительных слов.

                                        +3
                                        Я просто хотел обратить внимание на то, что в тестовых данных множество «не слов» имеет неравномерное распределение, что требуется учитывать, чтобы получить решение, которое сходится в 99%. Чтобы не быть голословным, я прогнал ваше решение через датасет в 110 млн тестовых слов. Предел для вашего решения — это 96-97% точности не зависимо от количества тестовых данных
                                        Графики тут

                                        Accuracy — это точность решения на заданном количестве данных
                                        MA 100K и MA 1M — это скользящее среднее для точности на 100тыс и 1 млн соответственно.

                                          0
                                          Да, забавная статистика. До такой особенности генератора я не добрался, у меня был датасет на 6М слов, все тесты сверх этого производились на локальном генераторе из предпослыки что больше сюрпризов в конкурсном генераторе нет.
                                          Вы как-то решали эту проблему? Все так же перечислением выбросов?
                                            0
                                            Нет, в опубликованном решении я не использовал обучения вообще. Это я постфактум анализировал статистику — пытался сделать обучающееся решение, которое бы сходилось в 99+%. В принципе, реализуемо, просто приходится в блюм-фильтре хранить 40-60 тыс популярных «не слов».

                                            В основном решении, у меня нет ничего особенно оригинального: стемминг, блюм-фильтр, триграммы. Описание моего решения тут.
                                      0
                                      А как был сгенерирован data-файлик?
                                        0
                                        В src есть все генерирующие скрипты.
                                          +1
                                          Что-то там парсер некого tranio.ru
                                            0
                                            Не тот файл оказывается прикрепил. Извините.
                                            В data.gz, помимо коротких слов на исключение (ветка обсуждения чуть выше) так же лежат популярные тройки\четверки с учетом позиции. Код их генерации большого интереса не представляет. Идея взята из алгоритма HmSearch http://www.cse.unsw.edu.au/~weiw/files/SSDBM13-HmSearch-Final.pdf Алгоритм разработан для быстрого поиска всех слов с заданным hamming distance от исходного. В нашем случае вырожденный случай hm=0. Результатв 75%, насколько я могу судить по некоторым запущенным мной реализациям, довольно близок к чистому портеру, так что баш на баш.
                                              0
                                              Если Вы прикрепили не тот архив с исходниками, то можно это исправить. Пришлите, пожалуйста, тот, который надо.
                          –5
                          Если б словарь почистили от чепухи всякой, которая английскими словами не является

                          toddite, synapsidan, ursid, cycadales, nebbishy, gypsophilous, cowfish, haboobs, archhead, impulsed, otiorhynchinae, twankies, olympio, besra, bankroll's, godsends, colymbidae, reefier, hobbie's, sagittid's, souldan, sap's, nevada, bushlike, hexastigm, baptizee, bonnibell, aldose, pilows, barkhan, redshank's, lucerne, baulkier, pocill, corday, unsaddle, waxbill, unbudged, horsehair, bamboula, parkward's, farnsworth's, zealotry, plumbed, khios's, millsboro's, otyak, enkernel, massif's, revkah…

                          то процент ошибки у всех уменьшился бы раза в два, потому что некоторых этих слов даже Google не знает. А то по условию конкурса вам нужна программа, которая отличает «слова английского языка», но победит программа, которая отличают «определенную херню, захардкоженную по пьяни».
                            +1
                            Словарик вполне официальный, в условиях была ссылка откуда он сформирован
                            https://github.com/hola/challenge_word_classifier/blob/master/blog/01-rules.md
                            For the purposes of this problem, we define an English word as a word from the list included here as words.txt. (If you're interested, it's the SCOWL “insane” dictionary with flattened diacritics.) Membership in the dictionary is case-insensitive. You have to write a program that can answer whether a given word is English.

                            http://wordlist.aspell.net/

                            В общем, там помимо академического английского еще и диалекты — американский, канадский, британский и т.д.
                              0
                              Проверил первое попавшееся слово из этого списка «cowfish»… оно есть:) en.wikipedia.org/wiki/Longhorn_cowfish Но вообще, по условиям, в словаре были и аббревиатуры. Поэтому, по-любому, надо было как-то рассчитывать на необычные слова.
                              0
                              придётся остановить досрочно и использовать результаты частичного прогона тестов


                              Посчитайте такие графики, они очень показательны. По характеру скользящего среднего и скорости затухания общего среднего можно примерно определить мат.ожидание и увидеть, вырастет оно или нет с увеличением блоков (если не учитывать накопления статистики, конечно, которое может быть включено после определённого предела).
                                +1
                                порадовали со 2 по 5 решения в submissions =))
                                abuse — https://github.com/hola/challenge_word_classifier/tree/master/submissions/5720eba193f2f29d3c9acbad
                                optimist — https://github.com/hola/challenge_word_classifier/tree/master/submissions/5720ebb893f2f29d3c9acbae
                                pessimist — https://github.com/hola/challenge_word_classifier/tree/master/submissions/5720ebd293f2f29d3c9acbaf
                                pofigist — https://github.com/hola/challenge_word_classifier/tree/master/submissions/5720ed5393f2f29d3c9acbb0
                                  0
                                  optimist, pessimist и pofigist мы сами заслали.

                                  А вообще десятки из присланных решений относятся к трём типам: return true, return false и return Math.random()<0.5.
                                    +1
                                    Жаль генератор редко выдаёт (или вообще не выдаёт) неправильные слова построенные как «правильное слово» + 's. Думаю это «просадило» бы многие решения.
                                      +1
                                      Не просадило бы. Решения просто не стали бы на это полагаться. Ведь условие было в том, что генератор не будет меняться ;)
                                        –1
                                        «Выкинуть» четверть словаря и считать это удачной оптимизацией? Явный прокол в тестировании по моему.
                                          +1
                                          Я лишь говорю о том, что в генератор это не заложили и участники этим воспользовались. Если бы заложили — не воспользовались бы, увидев повышение F+.
                                      0
                                      для повторяемости логичнее хэш считать SomeHash(str)
                                    0
                                    Поскольку слов в словаре меньше 700 000, а разнообразие псевдослучайных не-слов гораздо шире, то слово, встретившееся дважды, с большей вероятностью является словом, чем не-словом.
                                    Очень грубое описание решений подобного вида. Более 1/4 не-слов встречаются более 1 раза (на 20М тестов).

                                    Для того, чтобы заработало статистическое решение, 1М слов недостаточно.
                                    А еще можно грамотно объединить несколько решений, чтобы нивелировать «провал» статистики на малых объемах данных…

                                    В общем, на мой взгляд, называть это «нехитрым приёмом» несколько неоправданно…
                                      +2

                                      Чорд, галку gzip в форме не проставил.


                                      Судя по всему не я один


                                      $ file */data | grep gzip
                                      5745740063905b3a11d97bd5/data: gzip compressed data, was "data", last modified: Wed May 25 09:24:43 2016, from NTFS filesystem (NT)
                                      57466eb863905b3a11d97bed/data: gzip compressed data, was "data", last modified: Wed May 25 14:58:12 2016, max compression, from NTFS filesystem (NT)
                                      57469a9263905b3a11d97bf0/data: gzip compressed data, was "temp.json", last modified: Tue May 24 19:37:25 2016, max compression, from FAT filesystem (MS-DOS, OS/2, NT)
                                      57487c4363905b3a11d97c72/data: gzip compressed data, from FAT filesystem (MS-DOS, OS/2, NT)
                                      5748ab4963905b3a11d97caa/data: gzip compressed data, last modified: Fri May 27 20:00:37 2016, max compression, from Unix
                                      5748dda963905b3a11d97d06/data: gzip compressed data, from Unix
                                        0
                                        Спасибо, что обратили на это наше внимание. Эта галочка в форме — usability bug. В следующий раз в подобной ситуации будем смотреть на суффикс в имени закачиваемого файла.

                                        Для этих шести решений файл data будет переименован в data.gz, а результаты — пересчитаны.
                                          0

                                          Я бы сделал обязательную переключалку, в которой по умолчанию ничего не выбрано — тогда не забудут. Смотреть суффикс того что загружено очень-очень странно: в файле может и не быть .gz.

                                            0
                                            Тем не менее, во всех шести случаях, упомянутых выше, суффикс был.
                                              0

                                              Был, но он необязателен, всё равно кто-то не добавит, а установить переключалку — это намеренное действие, ошибка по невнимательности в нём невозможна. Кстати можно ещё magic проверять и показывать, gzip это или нет, убрав галку насовсем. Так можно ещё и ZIP отследить и показать wtf.

                                                0
                                                В следующий раз вообще подумаем над тем, как улучшить процесс отправки. Тут ещё было несколько таких, которые вообще забыли приложить файл данных, но тут уж медицина бессильна.
                                                  0

                                                  Тоже есть способ определить. Файл же у нас есть, экспорты в нём можно проверить. Хотя есть нюанс с поддержкой ES6 в браузере, но это тоже можно обойти. Нужен конкурс на минимизацию человеческих ошибок в форме.

                                                    0
                                                    Грузить автоматически присланный кем-то код, даже в песочнице, я как-то очкую. Зато здесь дали другой способ проверить: тестовый скрипт. Кто при наличии тестового скрипта поленился его запустить, тот уж сам виноват.
                                                      0

                                                      И правильно, потому что там будет
                                                      Buffer.prototype.toString = function() { eval("spawn(http.get())") } — кто-нибудь обязательно зальёт что-то весёлое. Я имел в виду распарсить в браузере и посмотреть, что там в экспортах. Можно даже require определить и показать ошибку, что чувак, так не договаривались.

                                                        +1
                                                        Это слишком сложно, а, значит, ненадёжно. Зато будем давать тестовые скрипты, — это хорошая практика, и будем сводить к минимуму те аспекты, которые тестовым скриптом проверить нельзя, вроде галочек в форме.
                                                          0
                                                          Например, скрипт сам может залить решение, которое прошло проверку.
                                            –2
                                            А вот это уже неправильно. В дополнение к задаче всех еще раз предупредили про эту галку. Давайте теперь еще и поправим пару решений, который не так экспортируют функции. Ну или которые работают с данными из файла как со строкой, а не с буфером. Я бы тоже хочет кое-что поправить в своем решении, можно?
                                              +1
                                              Выставление галочек не имеет ничего общего с умением программировать, а экспорты имеют. Кроме того, правильное заполнение формы — это единственное, что невозможно было проверить с помощью тестовой программы.
                                                0
                                                Тем не менее, это было одно из условий проведения конкурса.
                                                  +1
                                                  Кстати, в письме которое присылается в ответ на submission есть подтверждение того, что галка была проставлена. Внимательность в не меньшей степени относится к умению программировать. Но спорить на эту тему лучше не будем. Я неоднократно участвовал во всевозможных конкурсах по программированию. Никогда там не делали скидки на то, что кто-то неправильно указал имя входного файла с параметрами или, к примеру, ошибся в формате разделителя дробных чисел. Все были в равных условиях, даже несмотря на такие нелепые ошибки. Кстати, из-за подобных ошибок падают космические корабли, пусть даже это и «не имеет ничего общего с умением программировать».
                                                    0
                                                    Наверное, на тех конкурсах не было ситуации, когда участник узнаёт о неправильном формате в отправленном решении прямо перед оглашением результатов.
                                                      0
                                                      Именно так и бывало, решения отсылались в последние секунды и исправить что-либо было уже невозможно. Я говорю про ACM.
                                                      +2
                                                      > Кстати, в письме которое присылается в ответ на submission есть подтверждение того, что галка была проставлена.

                                                      Это Вы знаете только потому, что получили такое письмо. В отсутствие галочки нет и никакого указания на то, что её нет.

                                                      В общем, мы проводим конкурс интересных решений, а не «зоркий глаз». Впрочем, ни одно из решений, для которых мы сделали эту поправку, не претендует на призовое место.
                                                        0
                                                        Я всего лишь хочу объективного судейства. Ряд решений которые использовали статистические методы (в дополнение к остальным) вы принципиально зарезали, в том числе и мое. Хорошо, таким образом вы решили проблему тестирования, и этот момент я не собираюсь осуждать. Но теперь вы берете 6 решений и добавляете их в общий зачет, хотя они были отосланы не верно. Я сам не сторонник формализма (подразумеваю эту злосчастную галочку), но все же надо быть последовательными в своих решениях. Этих пустим, этих не пустим — так нельзя. И раз это конкурс «интересных решений», то нельзя не признать, что решения со статистикой весьма интересны, учитывая то, что и сами организаторы не задумывались о таком методе. Тем не менее их не пустили в зачет. Не вижу причин пускать в зачет решения которые были отосланы не верно.
                                                          +1
                                                          Все хорошие решения свелись к подбору коэффциентов для связки стем\блюм\портер. Что, кстати, предсказывали еще в первой теме.
                                                          Конкурса «интересных решений» не получилось.
                                                            +4
                                                            Мы их отметим как «вне конкурса», как это уже делалось раньше с решениями, присланными после дедлайна.
                                                              0
                                                              Спасибо, что услышали. И прошу участников тоже не обижаться, ничего личного, просто все должны быть в равных условиях.
                                                +1
                                                Протестил свое, 81.17%
                                                Tested 10000 of 10000 blocks
                                                
                                                   Total       W      NW   NW[0]   NW[1]   NW[2]   NW[3]   NW[4]   NW[5]   NW[6]   NW[7]   NW[8]
                                                   1000k  500672  499328   92206   69134   74631   78793   75506   56814   30604   14427    7213
                                                
                                                 Correct      F-      F+   F+[0]   F+[1]   F+[2]   F+[3]   F+[4]   F+[5]   F+[6]   F+[7]   F+[8] ms/100w
                                                
                                                    .
                                                  81.17%   8.54%  29.16%   2.45%  15.04%  18.55%  24.48%  38.76%  59.27%  72.12%  70.80%  63.51%       8

                                                Нормально. Не 83, но нормально :)
                                                  0
                                                  У меня почти столько же — 81.25% (5747e9eb63905b3a11d97c45)
                                                    +1
                                                    81.44
                                                    Tested 10000 of 10000 blocks
                                                    
                                                       Total       W      NW   NW[0]   NW[1]   NW[2]   NW[3]   NW[4]   NW[5]   NW[6]   NW[7]   NW[8]
                                                       1000k  500672  499328   92206   69134   74631   78793   75506   56814   30604   14427    7213
                                                    
                                                     Correct      F-      F+   F+[0]   F+[1]   F+[2]   F+[3]   F+[4]   F+[5]   F+[6]   F+[7]   F+[8] ms/100w
                                                    
                                                        submissions/5748dda963905b3a11d97d06/
                                                      81.44%   3.78%  33.38%   4.72%  21.86%  29.06%  33.77%  41.36%  54.37%  67.08%  74.49%  76.54%       9
                                                    

                                                      +1
                                                      Только из подробной статистики стало видно, на сколько мало я уделил внимания отсеиванию простых моделей.
                                                      82.11% (5745fc8163905b3a11d97be3)
                                                      Tested 10000 of 10000 blocks
                                                      
                                                         Total       W      NW   NW[0]   NW[1]   NW[2]   NW[3]   NW[4]   NW[5]   NW[6]   NW[7]   NW[8]
                                                         1000k  500672  499328   92206   69134   74631   78793   75506   56814   30604   14427    7213
                                                      
                                                       Correct      F-      F+   F+[0]   F+[1]   F+[2]   F+[3]   F+[4]   F+[5]   F+[6]   F+[7]   F+[8] ms/100w
                                                      
                                                          D:\projects\english_words\solution\
                                                        82.11%   2.36%  33.47%   4.58%  29.99%  39.08%  40.47%  41.37%  43.59%  46.77%  49.64%  50.02%      42
                                                      

                                                      +1
                                                      интересно, зная алгоритм генерации, насколько можно улучшить решение?
                                                      +6
                                                      Интересно было бы увидеть полную таблицу по всем 312 участникам.
                                                      А ещё интересней, своё место в этом рейтинге.
                                                        0

                                                        +1

                                                        +6
                                                        Возьму на себя смелость выложить результаты моего грубого тестирования, которые я получил самостоятельно проверкой submissions, которые вчера выложили организаторы. Результат, в общем, не претендует на достоверность и не гарантирует точности.

                                                        Результаты под, Осторожно, Спойлером!
                                                        N  SUBMISSION                  ACCURACY	
                                                        1  5747452a63905b3a11d97c13    83.67	
                                                        2  5748dc6363905b3a11d97d03    83.11	
                                                        3  57581ef1bb50d92eb4000001    83.03	
                                                        4  57483bab63905b3a11d97c5c    83.00	
                                                        5  57487e6a63905b3a11d97c73    82.16	
                                                        6  5748dc5763905b3a11d97d02    81.62	
                                                        7  5748a0a363905b3a11d97c96    81.59	
                                                        8  5745fc8163905b3a11d97be3    81.53 (*)
                                                        9  5748df1c63905b3a11d97d0f    81.51	
                                                        10 5748dda963905b3a11d97d06    81.44	
                                                        11 5748dded63905b3a11d97d0a    81.30	
                                                        12 5748c16c63905b3a11d97cd0    81.29	
                                                        13 5747e9eb63905b3a11d97c45    81.25	
                                                        14 5747dbba63905b3a11d97c3d    81.25	
                                                        15 5748a0fe63905b3a11d97c99    81.20	
                                                        16 574893e463905b3a11d97c85    81.20	
                                                        17 57485c0f63905b3a11d97c65    81.17	
                                                        18 574713ca63905b3a11d97c03    80.60 (*)
                                                        19 5735b994a6200f187771219a    80.41	
                                                        20 5746978e63905b3a11d97bee    80.19	
                                                        21 5748a78563905b3a11d97ca3    80.13	
                                                        


                                                        О методике моего грубого тестировании
                                                        Для предварительного тестирования я использовал собственный скрипт, который я прогнал на 312 решениях на выборке из 1000 слов. В результате:
                                                        • 5 решений тестировались очень медленно и вообще не выдали результата за 30 секунд на 1000 слов. Я эти решения прервал и далее не тестировал
                                                        • 5 решений тестировались отностительно медленно (более 10 секунд на 1000 слов), выдали не очень большие результаты. Далее я эти решения не тестировал
                                                        • 44 решений завершились ошибкой. Я их далее не тестировал не разбираясь с причинами
                                                        • 258 решений прошли предварительное тестирование, были перетестированы мной на 10 тыс слов. На основании 10К тестирования я выбрал топ решений, которые преодолели 80% рубеж на 10000 слов. Всего получилось 21 такое решение. После этого перетестировал топ 21 с помощью скрипта организаторов. Два таких решения (помечены звездочкой) тестировались медленно, и я прервал тестирование, а в качестве оценки точности данных решений использовал результат, полученный на 10К тестовых слов


                                                          0
                                                          топ5 — стем и блюм

                                                          6е место самообучающийся алгоритм (плюс стем и блюм)

                                                          3е место подало заявку последним

                                                            0
                                                            57581ef1bb50d92eb4000001 участвует вне конкурса и на приз не претендует.
                                                              +2
                                                              тогда разница в топ3 лидерах очень убедительна

                                                              кстати, интересен комментарий 7го места по поводу рекламы конкурса и мотивации
                                                              About the challenge promotion: I think the russian page which allow comments is a lot better for motivation than the english github page. I would probably have stopped a lot sooner if I didn't go to the russian page and used google translation on the comments to have an idea of what was achievable
                                                                0
                                                                Хотелось бы найти подобную англоязычную площадку для технарей.
                                                                  0

                                                                  reddit?

                                                                    0
                                                                    Да, хочу попробовать reddit в следующий раз.
                                                            –1
                                                            Я не вижу здесь своего решения, 5748c99463905b3a11d97cdb, оно на 10'000 блоков набирает около 80.71%
                                                            Также я не вижу чтобы между 2,3,4 позициями была заметна «стабилизация тройки лидеров». Вот серьезно, что покажет тестовая система если прогнать результаты первой четверки не на 10 тыс. блоках, а на 20, 30, 50? На 50 тысячах и мое решение уверенно набирает 83.85%.
                                                              0
                                                              5748dc5763905b3a11d97d02 решение утверждает что доходит до 84.7% на 20к блоков (и 87.7% на 50)
                                                                0
                                                                Я и не спорю. Полно решений лучше моего, но я то обсуждаю свое ;)
                                                                  0

                                                                  Забавно, что в 5748dc5763905b3a11d97d02 после 20M слов происходит "обучение обратно": график. Также есть ещё некоторые решения с обучением, в которых результат со временем ухудшается. Дособерётся статистика — выложу кликабельные графики.

                                                                  0
                                                                  У Вас на 10 000 блоках 79.06%.
                                                                    0
                                                                    Это если выключить обучение. С включенным 80.71 вроде. Мы же не перезапускаем решения когда тестируем на 10000 блоках?
                                                                      0
                                                                      Извините, Вы правы, 80.71%, не туда посмотрел.
                                                                    +2
                                                                    Будет отдельный пост о решениях с обучением, между ними проведём отдельное сравнение и, наверное, вручим автору лучшего из них спецприз.
                                                                      0
                                                                      Как я писал, моя таблица не предендует на полноту, достоверность и абсолютную точность. Ваше решения не прошло в топ 21, поскольку не набрало 80% при тестировании на 10К слов (детали моей методики тестирования описаны в предыдущем посте)
                                                                        0
                                                                        Я перепутал, 10К слов принял за 10К блоков. Извините, претензий не имею )
                                                                      +1
                                                                      Немалый труд проделан, спасибо за предварительный результат. Хоть и не попал в десятку, но 13 место из 312 тоже неплохо.
                                                                      +1
                                                                      Это в целом совпадает с теми результатами, которые у нас уже готовы.
                                                                        +1
                                                                        Я бы организаторам предложил сделать отдельный зачет для статистов, как минимум с 50К тестами. Или до тех пор, пока кто-нибудь не наберет 90%.

                                                                        На 50К уже успевает набраться необходимая статистика и подобные решения вполне могут уйти за 85% правильных ответов.
                                                                          +1
                                                                          Вероятно, поиск «кто первый достигнет 90%» будет интереснее. Потому как статические решения разные и встречаются локальные максимумы.
                                                                            +1
                                                                            Будет пост о решениях с обучением.
                                                                            0
                                                                            В скрипте generator.js есть такие строки:
                                                                            let item = this.data.get(prefix.slice(-this.order));
                                                                            if (!item)
                                                                            return this.prev(prefix);

                                                                            Насколько я смог понять — это либо баг либо какая то неточность: во первых this.prev — это объект марковской модели меньшего порядка из чего следует что его нельзя вызывать как функцию (или я что то не знаю про ES6 ?) Из чего сразу следует во вторых — это условие никогда не выполняется (this.data — генерируется примерно таким же кодом и в нем присутствуют все запрашиваемые ключи включая пустую строку) Поясните пожалуйста какая здесь задумывалась логика? Должна ли на этом месте все же вызываться модель меньшего порядка? Правильно ли что матрица частот повторений букв (this.data) содержит не только строки длины order но и меньшей длины включая пустую?
                                                                            PS: Сам в конкурсе не участвовал но читал статьи и стало интересно каким именно алгоритмом генерируются псевдо-слова.
                                                                              0
                                                                              Вы правы, это осталось от предыдущего варианта. Не заметил, потому что строка не выполняется. Всё, что связано с prev, можно убрать.
                                                                              0
                                                                              --text 'Lady Gaga has accompanied Mario Andretti in a two-seater race car at #Indy500 today!'

                                                                              у меня у одного не запускается с одинарными кавычками? )) с двойными работает…

                                                                              Only users with full accounts can post comments. Log in, please.