Английская версия этого поста размещена на 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%.Спасибо за терпение. Оставайтесь с нами!
Комментарии (103)
4p4
08.06.2016 19:57+1У кого есть суперкомпьютер, помогите Hola посчитать)
feldgendler
08.06.2016 19:59+2Мы считаем на AWS, просто некоторые решения работают очень долго. Одно решение может работать только на одном ядре, а ядер сильно быстрее 3 ГГц сейчас не бывает.
KingOfNothing
08.06.2016 20:09Рад, что у меня в результате стабильные 77% как и при моем тестировании до отправки решения :-) Пошел смотреть какой результат минимальный.
mr47
08.06.2016 21:20а можно ссылочку и на вашу работу? спасибо :)
KingOfNothing
08.06.2016 22:23https://github.com/hola/challenge_word_classifier/blob/master/submissions/57437474a6200f1877712208/src/index.js
rodgar
08.06.2016 20:22-1> Это не только сделало бы этот нехитрый приём «волшебной палочкой»
Пробежавшись по 40 случайно выбранным решениям я увидел 2 обучения. Пусть я пропустил половину и их 4. Т.е. в районе 10%.
Вы называете это «волшебной палочкой», в комментариях были высказывания в духе «читерство» и «легкий путь». Хотелось бы сказать что, во-первых, этот путь совсем не легкий и не лежит на поверхности. Иначе бы его применили не 10% участников, а значительно больше. Тот факт что организаторы сами этого не предусмотрели является дополнительным доводом «простоты» и «волшебности». До него действительно нужно додуматься, и, мне кажется, это чуть труднее чем взять предложенный в комментариях фильтр Блума, оказавшийся одним из лучших вариантов решения задачи. Во-вторых качественная имплементация обучения, опять же по моему мнению, ничуть не проще Блума. Таким образом, лично я не вижу никакой «волшебной палочки».
> но и создало бы для жюри проблему выбора между несколькими обучающимися решениями
В коментариях к своему решению я предлагл один из возможных вариантов решения этой проблемы: запускать обучающиеся алгоритмы по времени. Кто смог обработать большее кол-во слов за час и лучше на них обучится (а в обучении всегда есть сильный трейдофф скорость-память-качество), тот и лучший.
Да, я с самого начала понимал что истинная задача конкурса — разработать лучшее, в том числе по занимаемой памяти, решение для задачи проверки орфографии пользовательского ввода в браузере. Но условия задачи формализуют ее в несколько другом аспекте, довольно далеком от реальной задачи. И обучение удовлетворяет *всем* формальным условиям задачи. Для полной честности, осталось признать что вы изменили условия задачи в пункте «столько тестов, сколько потребуется». Почему-то в тексте этой фразы нет.
Напоследок хотелось бы вспомнить Джордано Бруно, пострадавшего лишь за то, что он изучил все имеющиеся факты и сделал непротиворечивое заявление. Но оно, на тот день, никого не интересовало.
Спасибо за конкурс…feldgendler
08.06.2016 20:25+3Конечно же, можно было запускать с ограничением по времени или ещё как-то. Но всё это было бы изменением по сравнению с заявленными правилами конкурса.
> Для полной честности, осталось признать что вы изменили условия задачи в пункте «столько тестов, сколько потребуется».
Не понял, что Вы имеете в виду. Что конкретно мы изменили?rodgar
08.06.2016 20:38Я имел ввиду ваш комментарий
>вопрос к организаторам — а вы можете сказать какое будет минимальное кол-во блоков для тестирования?
>>Такое, какое потребуется, чтобы увидеть уверенную разницу между лидерами.
Я считаю что на 1М тестов уверенную разницу между лидерами увидеть нельзя. Более того, такое кол-во тестов даже не позволяет этих лидеров выявить. Руководствуясь описанными в посте посылами, можно было установить лимит на 1000 тестов, или на 10. Это точно так же не позволило бы ни выявить лидеров, ни выявить уверенную разницу между ними.
Не могли бы вы еще раз, для непонятливых, привести причины выбора именно 1М тестов, кроме уже описанной проблемы ограниченности ядер 3ГГц.feldgendler
08.06.2016 20:59+3Среди необучающихся программ стабилизация тройки лидеров произошла уже на 1 500 блоках. Дальнейшее увеличение объёмов уточняло лишь сотые доли процента, не меняя расстановки сил. Нет никаких оснований полагать, что далеко после 10 000 блоков произошло бы что-то неожиданное.
rodgar
08.06.2016 21:09+3>Нет никаких оснований полагать, что далеко после 10 000 блоков произошло бы что-то неожиданное.
Ну, например на 200 000 блоков мое решение бы показало 90%. Согласен, ничего неожиданного и вполне предсказуемо.
Еще можно было определить «параметр стабилизации: если за 1000 блоков результат улучшился менее 0,1% значит результат стабилен». Кажется даже никаких условий конкурса не меняем.
Хорошо, сойдемся на дискриминации по признаку применения обучения =)
В каком-нибудь параллельном мире ваша фраза могла бы выглядеть как
«Среди всех программ стабилизация тройки лидеров произошла уже на 150 000 блоках. Дальнейшее увеличение объёмов уточняло лишь сотые доли процента, не меняя расстановки сил.» Постараюсь найти мощности для проверки этого утверждения и время для написания статьи.
Еще раз: ваша мотивация понятна, претензий не имею. Небольшой укор за умершие от волнительного ожидания нервные клетки, но в целом за конкурс спасибо.mr47
08.06.2016 21:20+1а можно ссылочку на вашу работу. спасибо :)
rodgar
08.06.2016 21:42+2https://github.com/hola/challenge_word_classifier/tree/master/submissions/5747c9f463905b3a11d97c3a
Но вряд ли вы найдете там что-то интересное. Сплошное читерство и волшебствопалочничество. Примерно того же уровня, как если бы я придумал как скачать словарь из интернета. Хоть не дисквалифицировали, уже спасибо =)
Кстати, запрошенные 200 000 блоков мое решение обрабатывает менее чем за час. А в полную силу начинает работать только после 40 000 блоков. Немного утрируя, можно сказать что в озвученных условиях тестирования запускается только половина кода.feldgendler
08.06.2016 22:17Многие решения работают быстро, и протестировать их на большом количестве блоков не было бы проблемой. Однако есть решения, работающие на порядки медленнее Вашего.
rodgar
08.06.2016 23:13-2Не удержусь промолчать в последний раз.
Вы в любом случае пришли к мысли
>Самые медленные из них, похоже, нам придётся остановить досрочно и использовать результаты частичного прогона тестов.
Теоретически, ничего не мешало сделать все тоже самое на гораздо большем кол-во блоков. Алгоритмы, не сумевшие обработать 100М слов за 2 недели между окончанием конкурса и объявлением результатов — извините, ваш результат по итогам частичной проверки. 100М за 2 недели это по 100 слов в секунду, полный неуд на мой взгляд. А если нужно проверить 3000 слов, скопированных в текстовое поле? Подождите 30 секунд, мы проверяем?
Кстати, если аудитория браузера составляет 50'000 ежедневных пользователей, и каждый из них пишет хотя бы 10 слов в день, то за год набирается 180М слов. Цифры то вполне из реального мира. Почему бы не делать проверку орфографии онлайн? Тот же хром иногда подчеркивает слово спустя секунды после написания, ничего критичного.feldgendler
08.06.2016 23:18+1Конечно, мы не обрабатывали слова две недели. Писали алгоритмы тестирования, отлаживали их, да и другой работой тоже приходится заниматься. Но несколько суток считается, да.
mr47
08.06.2016 22:21+1Спасибо еще раз за ссылочку. Я думал это написать используя hidden markov model, но увы
лень,проекты— не успел.
PS:
let parts = [], cnt = ~~(word.length / window) + (word.length % window ? 1 : 0);
Любите вы изощренность :)
rodgar
08.06.2016 22:31Прочитать свой код в воскресенье на свежую голову и понять всю глубину изощренности. Для всего остального есть master card.
Жаль hexlet закрыл игры. Отличная была мерялка в извращенности против нодистов.
chianti
08.06.2016 23:18Почитал ваше решение. Правильно понимаю, вы не учитывали тот факт, что для 20-30к «не слов» вероятность обнаружения в тестовой выборке не ниже чем для «корректных слов»? Если не учитывает, то ваш алгоритм не сойдется никогда в 100%, максимум в 95%.
rodgar
08.06.2016 23:39Я анализировал подобные выбросы генератора. Слова из одной, двух и трех букв встречаются аномально часто.
Таких слов 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% в любом случае не достижимы.chianti
09.06.2016 00:09Не совсем. Я имел в виду, что вероятность встретить «не слова», такие как «under's» или «dising» примерно в 20 раз выше, чем встретить слово из словаря. И таких слов достаточно много. Например «blenesses» и «unreproof» встречаются также часто как и словарные слова. Видимо, это связано с природой марковского генератора.
То есть, при таком подходе, после 60 млн тестов база будет включать определенный процент (по моим оценкам около 5%) ложноположительных слов.
chianti
09.06.2016 10:20+3Я просто хотел обратить внимание на то, что в тестовых данных множество «не слов» имеет неравномерное распределение, что требуется учитывать, чтобы получить решение, которое сходится в 99%. Чтобы не быть голословным, я прогнал ваше решение через датасет в 110 млн тестовых слов. Предел для вашего решения — это 96-97% точности не зависимо от количества тестовых данных
Графики тут
Accuracy — это точность решения на заданном количестве данных
MA 100K и MA 1M — это скользящее среднее для точности на 100тыс и 1 млн соответственно.
rodgar
09.06.2016 10:26Да, забавная статистика. До такой особенности генератора я не добрался, у меня был датасет на 6М слов, все тесты сверх этого производились на локальном генераторе из предпослыки что больше сюрпризов в конкурсном генераторе нет.
Вы как-то решали эту проблему? Все так же перечислением выбросов?chianti
09.06.2016 10:59Нет, в опубликованном решении я не использовал обучения вообще. Это я постфактум анализировал статистику — пытался сделать обучающееся решение, которое бы сходилось в 99+%. В принципе, реализуемо, просто приходится в блюм-фильтре хранить 40-60 тыс популярных «не слов».
В основном решении, у меня нет ничего особенно оригинального: стемминг, блюм-фильтр, триграммы. Описание моего решения тут.
guyfawkes
09.06.2016 00:27А как был сгенерирован data-файлик?
rodgar
09.06.2016 10:27В src есть все генерирующие скрипты.
guyfawkes
09.06.2016 12:45+1Что-то там парсер некого tranio.ru
rodgar
09.06.2016 12:56Не тот файл оказывается прикрепил. Извините.
В data.gz, помимо коротких слов на исключение (ветка обсуждения чуть выше) так же лежат популярные тройки\четверки с учетом позиции. Код их генерации большого интереса не представляет. Идея взята из алгоритма HmSearch http://www.cse.unsw.edu.au/~weiw/files/SSDBM13-HmSearch-Final.pdf Алгоритм разработан для быстрого поиска всех слов с заданным hamming distance от исходного. В нашем случае вырожденный случай hm=0. Результатв 75%, насколько я могу судить по некоторым запущенным мной реализациям, довольно близок к чистому портеру, так что баш на баш.feldgendler
09.06.2016 13:30Если Вы прикрепили не тот архив с исходниками, то можно это исправить. Пришлите, пожалуйста, тот, который надо.
Nakilon
08.06.2016 21:28-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 не знает. А то по условию конкурса вам нужна программа, которая отличает «слова английского языка», но победит программа, которая отличают «определенную херню, захардкоженную по пьяни».CWN
08.06.2016 21:41+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/
В общем, там помимо академического английского еще и диалекты — американский, канадский, британский и т.д.
TiesP
09.06.2016 13:29Проверил первое попавшееся слово из этого списка «cowfish»… оно есть:) en.wikipedia.org/wiki/Longhorn_cowfish Но вообще, по условиям, в словаре были и аббревиатуры. Поэтому, по-любому, надо было как-то рассчитывать на необычные слова.
Antelle
08.06.2016 21:31придётся остановить досрочно и использовать результаты частичного прогона тестов
Посчитайте такие графики, они очень показательны. По характеру скользящего среднего и скорости затухания общего среднего можно примерно определить мат.ожидание и увидеть, вырастет оно или нет с увеличением блоков (если не учитывать накопления статистики, конечно, которое может быть включено после определённого предела).
CWN
08.06.2016 22:03+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/5720ed5393f2f29d3c9acbb0feldgendler
08.06.2016 22:16optimist, pessimist и pofigist мы сами заслали.
А вообще десятки из присланных решений относятся к трём типам: return true, return false и return Math.random()<0.5.
slavap
09.06.2016 00:58+1Жаль генератор редко выдаёт (или вообще не выдаёт) неправильные слова построенные как «правильное слово» + 's. Думаю это «просадило» бы многие решения.
Zavtramen
09.06.2016 01:16+1Не просадило бы. Решения просто не стали бы на это полагаться. Ведь условие было в том, что генератор не будет меняться ;)
slavap
09.06.2016 01:36-1«Выкинуть» четверть словаря и считать это удачной оптимизацией? Явный прокол в тестировании по моему.
Zavtramen
09.06.2016 01:39+1Я лишь говорю о том, что в генератор это не заложили и участники этим воспользовались. Если бы заложили — не воспользовались бы, увидев повышение F+.
SabMakc
08.06.2016 23:11Поскольку слов в словаре меньше 700 000, а разнообразие псевдослучайных не-слов гораздо шире, то слово, встретившееся дважды, с большей вероятностью является словом, чем не-словом.
Очень грубое описание решений подобного вида. Более 1/4 не-слов встречаются более 1 раза (на 20М тестов).
Для того, чтобы заработало статистическое решение, 1М слов недостаточно.
А еще можно грамотно объединить несколько решений, чтобы нивелировать «провал» статистики на малых объемах данных…
В общем, на мой взгляд, называть это «нехитрым приёмом» несколько неоправданно…
alex3d
09.06.2016 00:13+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 Unixfeldgendler
09.06.2016 02:33Спасибо, что обратили на это наше внимание. Эта галочка в форме — usability bug. В следующий раз в подобной ситуации будем смотреть на суффикс в имени закачиваемого файла.
Для этих шести решений файлdataбудет переименован вdata.gz, а результаты — пересчитаны.Antelle
09.06.2016 09:29Я бы сделал обязательную переключалку, в которой по умолчанию ничего не выбрано — тогда не забудут. Смотреть суффикс того что загружено очень-очень странно: в файле может и не быть .gz.
feldgendler
09.06.2016 10:55Тем не менее, во всех шести случаях, упомянутых выше, суффикс был.
Antelle
09.06.2016 10:58Был, но он необязателен, всё равно кто-то не добавит, а установить переключалку — это намеренное действие, ошибка по невнимательности в нём невозможна. Кстати можно ещё magic проверять и показывать, gzip это или нет, убрав галку насовсем. Так можно ещё и ZIP отследить и показать wtf.
feldgendler
09.06.2016 11:03В следующий раз вообще подумаем над тем, как улучшить процесс отправки. Тут ещё было несколько таких, которые вообще забыли приложить файл данных, но тут уж медицина бессильна.
Antelle
09.06.2016 11:08Тоже есть способ определить. Файл же у нас есть, экспорты в нём можно проверить. Хотя есть нюанс с поддержкой ES6 в браузере, но это тоже можно обойти. Нужен конкурс на минимизацию человеческих ошибок в форме.
feldgendler
09.06.2016 11:29Грузить автоматически присланный кем-то код, даже в песочнице, я как-то очкую. Зато здесь дали другой способ проверить: тестовый скрипт. Кто при наличии тестового скрипта поленился его запустить, тот уж сам виноват.
Antelle
09.06.2016 11:36И правильно, потому что там будет
Buffer.prototype.toString = function() { eval("spawn(http.get())") }— кто-нибудь обязательно зальёт что-то весёлое. Я имел в виду распарсить в браузере и посмотреть, что там в экспортах. Можно даже require определить и показать ошибку, что чувак, так не договаривались.feldgendler
09.06.2016 11:41+1Это слишком сложно, а, значит, ненадёжно. Зато будем давать тестовые скрипты, — это хорошая практика, и будем сводить к минимуму те аспекты, которые тестовым скриптом проверить нельзя, вроде галочек в форме.
Zavtramen
09.06.2016 09:39-2А вот это уже неправильно. В дополнение к задаче всех еще раз предупредили про эту галку. Давайте теперь еще и поправим пару решений, который не так экспортируют функции. Ну или которые работают с данными из файла как со строкой, а не с буфером. Я бы тоже хочет кое-что поправить в своем решении, можно?
feldgendler
09.06.2016 09:52+1Выставление галочек не имеет ничего общего с умением программировать, а экспорты имеют. Кроме того, правильное заполнение формы — это единственное, что невозможно было проверить с помощью тестовой программы.
Zavtramen
09.06.2016 10:03+1Кстати, в письме которое присылается в ответ на submission есть подтверждение того, что галка была проставлена. Внимательность в не меньшей степени относится к умению программировать. Но спорить на эту тему лучше не будем. Я неоднократно участвовал во всевозможных конкурсах по программированию. Никогда там не делали скидки на то, что кто-то неправильно указал имя входного файла с параметрами или, к примеру, ошибся в формате разделителя дробных чисел. Все были в равных условиях, даже несмотря на такие нелепые ошибки. Кстати, из-за подобных ошибок падают космические корабли, пусть даже это и «не имеет ничего общего с умением программировать».
Imp5
09.06.2016 10:39Наверное, на тех конкурсах не было ситуации, когда участник узнаёт о неправильном формате в отправленном решении прямо перед оглашением результатов.
Zavtramen
09.06.2016 12:07Именно так и бывало, решения отсылались в последние секунды и исправить что-либо было уже невозможно. Я говорю про ACM.
feldgendler
09.06.2016 10:52+2> Кстати, в письме которое присылается в ответ на submission есть подтверждение того, что галка была проставлена.
Это Вы знаете только потому, что получили такое письмо. В отсутствие галочки нет и никакого указания на то, что её нет.
В общем, мы проводим конкурс интересных решений, а не «зоркий глаз». Впрочем, ни одно из решений, для которых мы сделали эту поправку, не претендует на призовое место.Zavtramen
09.06.2016 11:57Я всего лишь хочу объективного судейства. Ряд решений которые использовали статистические методы (в дополнение к остальным) вы принципиально зарезали, в том числе и мое. Хорошо, таким образом вы решили проблему тестирования, и этот момент я не собираюсь осуждать. Но теперь вы берете 6 решений и добавляете их в общий зачет, хотя они были отосланы не верно. Я сам не сторонник формализма (подразумеваю эту злосчастную галочку), но все же надо быть последовательными в своих решениях. Этих пустим, этих не пустим — так нельзя. И раз это конкурс «интересных решений», то нельзя не признать, что решения со статистикой весьма интересны, учитывая то, что и сами организаторы не задумывались о таком методе. Тем не менее их не пустили в зачет. Не вижу причин пускать в зачет решения которые были отосланы не верно.
rodgar
09.06.2016 12:14+1Все хорошие решения свелись к подбору коэффциентов для связки стем\блюм\портер. Что, кстати, предсказывали еще в первой теме.
Конкурса «интересных решений» не получилось.
feldgendler
09.06.2016 12:28+4Мы их отметим как «вне конкурса», как это уже делалось раньше с решениями, присланными после дедлайна.
Zavtramen
09.06.2016 12:33Спасибо, что услышали. И прошу участников тоже не обижаться, ничего личного, просто все должны быть в равных условиях.
deNULL
09.06.2016 00:35+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% 8alex3d
09.06.2016 08:58+181.44Tested 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% 9Imp5
09.06.2016 09:32+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% 42chianti
09.06.2016 16:09+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
Don_Eric
09.06.2016 17:03топ5 — стем и блюм
6е место самообучающийся алгоритм (плюс стем и блюм)
3е место подало заявку последним
feldgendler
09.06.2016 17:0657581ef1bb50d92eb4000001 участвует вне конкурса и на приз не претендует.
Don_Eric
09.06.2016 17:13+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
feldgendler
09.06.2016 17:20Хотелось бы найти подобную англоязычную площадку для технарей.
Zavtramen
09.06.2016 17:09-1Я не вижу здесь своего решения, 5748c99463905b3a11d97cdb, оно на 10'000 блоков набирает около 80.71%
Также я не вижу чтобы между 2,3,4 позициями была заметна «стабилизация тройки лидеров». Вот серьезно, что покажет тестовая система если прогнать результаты первой четверки не на 10 тыс. блоках, а на 20, 30, 50? На 50 тысячах и мое решение уверенно набирает 83.85%.Don_Eric
09.06.2016 17:165748dc5763905b3a11d97d02 решение утверждает что доходит до 84.7% на 20к блоков (и 87.7% на 50)
feldgendler
09.06.2016 17:19У Вас на 10 000 блоках 79.06%.
Zavtramen
09.06.2016 17:57Это если выключить обучение. С включенным 80.71 вроде. Мы же не перезапускаем решения когда тестируем на 10000 блоках?
feldgendler
09.06.2016 17:22+2Будет отдельный пост о решениях с обучением, между ними проведём отдельное сравнение и, наверное, вручим автору лучшего из них спецприз.
chianti
09.06.2016 21:01Как я писал, моя таблица не предендует на полноту, достоверность и абсолютную точность. Ваше решения не прошло в топ 21, поскольку не набрало 80% при тестировании на 10К слов (детали моей методики тестирования описаны в предыдущем посте)
Gromo
09.06.2016 20:22+1Немалый труд проделан, спасибо за предварительный результат. Хоть и не попал в десятку, но 13 место из 312 тоже неплохо.
SabMakc
09.06.2016 17:22+1Я бы организаторам предложил сделать отдельный зачет для статистов, как минимум с 50К тестами. Или до тех пор, пока кто-нибудь не наберет 90%.
На 50К уже успевает набраться необходимая статистика и подобные решения вполне могут уйти за 85% правильных ответов.SabMakc
09.06.2016 17:47+1Вероятно, поиск «кто первый достигнет 90%» будет интереснее. Потому как статические решения разные и встречаются локальные максимумы.
Arlekcangp
10.06.2016 10:50В скрипте 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: Сам в конкурсе не участвовал но читал статьи и стало интересно каким именно алгоритмом генерируются псевдо-слова.feldgendler
10.06.2016 10:53Вы правы, это осталось от предыдущего варианта. Не заметил, потому что строка не выполняется. Всё, что связано с prev, можно убрать.
alerkesi
15.06.2016 22:16--text 'Lady Gaga has accompanied Mario Andretti in a two-seater race car at #Indy500 today!'
у меня у одного не запускается с одинарными кавычками? )) с двойными работает…
Zavtramen
А счастье было так близко.
feldgendler
Ну тут есть ещё и практический смысл: тестировать на значительно большем числе блоков пришлось бы очень долго.
Zavtramen
Я без претензий, организаторам все равно пришлось бы принять какое-то решение и остановиться на каком-либо кол-ве блоков. Что собственно и произошло.
FlashManiac
Да, надо было добавить какие то ограничения, хотя бы количество блоков.
feldgendler
Если бы мы заранее зафиксировали количество блоков, то могли бы столкнуться с ситуацией, когда решения лидеров показывают практически неразличимые результаты. Тогда тоже был бы скандал, требования выдать приз каждому, пересчитать по-новому, протесты и т.п.
FlashManiac
А что если бы не было метода init был бы только test. И запускался бы скрипт каждый раз с нуля. Тогда было бы справедливее.
Zavtramen
Это длилось бы вечно, у меня в init, например, распаковка данных идет.
feldgendler
Можно было бы и по-другому изменить правила. Но единственный способ всё предвидеть — провести конкурс, а дважды с одной задачей конкурс не проводят.