В агонистических попытках увеличить процент в последний день конкурса наконец-то решился на «крайность» — попробовать отфильтровывать непроизносимые сочетания согласных. Поиск в гугле не дал каких-либо универсальных алгоритмов, которые можно было бы применить, а те, которые имеются, слишком сложны в реализации (и для понимания, и в размере реализации тоже).
После нескольких проб остановился на анализе статистики подобных сочетаний для верных слов и фильтрации всего остального — этот способ намного короче, чем пытаться анализировать последовательность согласных на сложность произношения, т.к. в словаре оказалось неожиданно много сложновыговариваемых сочетаний.
И такой фильтр даже работает, но итоговый результат получается хуже из-за того, что реализация занимает место и приходится жертвовать чем-то другим. Если бы генератор генерировал больше случайных последовательность букв, возможно этот вариант бы и сработал, а так слишком много «не-слов» практически не отличиются от «слов», что делает подобную проверку бесполезной (в моём случае).
Думаю, что 81% достижим, и даже 82%, но, имхо, по поводу 85% сомневаюсь, слишком тяжело идут улучшения после 80% — приходится бороться за каждые 0,01%. А в последние два-три дня вообще практически никаких улучшений — любые попытки что-либо изменить только ухудшают результат, и иногда довольно сильно, приходится откатываться к предыдущему решению. Скорее всего я достиг, как говорят, «локального максимума», чтобы поискать горку повыше, нужно спустить пониже и искать другой путь, однако времени на это уже нет, да и идеи уже все перепробовал.
По поводу комментариев в статье — соглашусь, это кладезь идей и информации о решениях, вот только выбрать правильный подход сложно, и нужно время, чтобы выбранный подход довести до ума
Именно так из-за ограниченности словаря и неограниченности генерируемых не-слов — повторы слов будут встречаться намного чаще, поэтому выгоднее 1% в словах, чем 1% в не-словах. К сожалению, 99% для слов будет давать слишком много false-positive для не-слов — генератор слишком правдоподобные слова отдаёт.
Спасибо и Вам за подробные комментарии и идеи — очень интересно читать размышления и выводы по разным методам. Я тоже пробовал делать несколькими способами, и описывал частично результаты тут в комментариях. А сдаваться не стоит — у меня локальные тесты неверные был прорыв почти в 3% в тот же день, как я описал, что неделю застрял на 26%.
Получил письмо, и, думаю, оно будет интересно и другим участникам, как и мой ответ:
Если у вас получилось добиться результата > 80% рад за вас. Но не получилось бы так, что вы вводите в заблуждение всех остальных участников, отбивая мотивацию попробовать что-то ещё сделать в последние пару дней.
Смотрите в чем дело. Если вы используете любой алгоритм обучения, та же нейронная сеть к примеру, то вы используете ограниченное кол-во неправильных слов. Все вы просто не сможете выкачать из тесткейсов, их огромное множество и формируются они случайно. Я к тому, что набор тесткейсов на котором организаторы будут тестировать будет выбран случайно, и ваша достигнутая вероятность сохранится лишь тем больше чем больше тесткейсов совпадет в вашей выборке и выборке организаторов.
Вы пробовали закачать случайные 10000 (к примеру) тесткейсов те которые вы точно не использовали при обучении и каков был результат? Сделать это 2-3 раза?
Если >80% могу вас заранее поздравить с тем что вы точно будете в топе и бороться за призы. А вот если нет, тогда вы вводите в заблуждение остальных! И тогда надо бы ваш комментарий подредактировать, чтобы не отнимать мотивацию у остальных.
На мой взгляд такая вероятность которую вы обозначали не достижима по 2 причинам:
1. ограниченный размер решения в 64К
2. неограниченное число искажений слов (причем отличаются большинство неправильных слов от слова в словаре минимально)
По моему мнению, большинству участников интересно узнать, каких результатов добились остальные. Если разница небольшая, то это огромный стимул, а если разница большая — значит у него тесты неправильные :)
И если кто-то не выкладывает свои результаты из боязни дать другим стимул, то мне интересно увидеть кто каких результатов добился. Давать точные цифры нет смысла, т.к. каждый использует собственный способ оценки и блоки, на которых прогоняется решение локально и будет прогоняться организаторами — разные, а значит результат будет в любом случае отличаться от опубликованного.
Со своей стороны если я у кого-то увижу огромный результат, то я попытаюсь добиться такого же или хотя бы приблизиться к нему. И, к тому же, всегда существует вероятность того, что где-то в тестах у участника была ошибка (т.к. это не официальная таблица результатов), так что опускать руки рано.
В моём случае я действительно оценивал локально по относительно небольшой выборке — 23К блоков. После письма мне самому стало интересно насколько результат будет отличаться, если использовать другие сеты с блоками, поэтому я скачал ещё 2 сета по 10К блоков и протестировал своё решение только на них. По сравнению с предыдущим тестированием результат колеблется в пределах 0,1%.
О, товарищ! Ещё есть время до пятницы, может удастся преодолеть порог и в 81%. Правда, чтобы добраться от 79 до 80 ушло 5 дней, а чем дальше — тем сложнее даются каждые 0.01%
Судя по описанию конкурса можно получить спец призы за интересные и оригинальные решения на усмотрение организаторов конкурса. По мне очень даже справедливо. К тому же место в первой десятке тоже довольно сильно тешит ЧСВ :)
Так что одно слово вполне попадается несколько раз на миллионе-то замеров
Судя по test[ word ] = wordsIndex[ word ] || false одно и то же слово несколько раз попасться не может, в отличие от блоков по 100 слов. Думаю, что Object.keys( test ).length не выдаст 1,000,000.
Мне нет смысла настаивать на верности или неверности данного способа тестирования, но обратить внимание на этот момент стоит, просто, чтобы быть в курсе возможных расхождений с результатами тестирования блоков по 100 слов.
А вот брать среднее между результатами по выборкам разных размеров действительно нельзя — нужно суммировать число правильных ответов и делить на общее число замеров.
Я в начале так и делал, но если грубо взять словарь в 10 правильных слов и 100 неправильных (приближённо к реальности), при этом и там и там будет угадываться 10 слов, то в моём случае будет (100% + 10%) / 2 = 55%, а в случае общего замера будет ((10 + 10) / 110) * 100 = 18.2%, что неверно.
Объяснение же разницы уникальных и неуникальных слов довольно простое — всё зависит от количества false-negative для верных слов, т.к. повторяются именно они в связи с ограниченностью количества по сравнению с не-словами, коих невероятное множество. При 1-2% false-negative результат по сравнинею с проверкой блоков по 100 слов будет лучше, а вот при большем количестве false-negative результат будет хуже в связи с тем, что многие повторяющиеся правильные слова будут считаться неверными.
Данный подход не совсем верный, насколько я понимаю из кода. У меня самого почти такой же подход — есть два файла — словарь всех слов и чуть больший словарь «не-слов», по которым я прогоняю тесты, затем складываю проценты от обеих проверок, делю на 2 и вывожу как среднее. Т.е. у меня это выглядит примерно так:
Test correct words - 99.7636%
Test incorrect words - 52.0787%
Average correctness - 75.9212%
Данный подход хорош на первый взгляд, но он может давать довольно ощутимую разницу до ±1% за счёт того, что все слова для проверки уникальны, а в итоговом варианте часто будут встречаться дубликаты слов. Сам столкнулся с этим, и в моих случаях чаще было, когда дубликаты ухудшали результат, чем улучшали. Поэтому я предпочитаю делать быстрый прогон на предмет улучшений используя два словаря (от него и отталкиваюсь), но итоговый процент всё же прогоняю на тестовых блоках по 100 слов (он точнее, но проверка намного дольше из-за большого кол-ва файлов).
Практика показывает, что сбалансированные бинарные данные для блум фильтра сжимаются очень плохо — всего на 3-4%. Больший показатель сжатия говорит о том, что фильтр недостаточно эффективен: если много бит установлено — будет много ложно-положительных ответов, если много бит не установлено — размер фильтра выбран слишком большой и его можно спокойно уменьшить в большинстве случаев (либо увеличить количество хеш-функций чтобы повысить точность).
ИМХО, 75% вполне реально, а вот > 80% — вызывает сомнения. После 70-72% идёт борьба с самим собой за каждые 0.2-0.3%.
Пробовал создать псевдо-нейронную однослойную сеть, которая бы собирала статистику по словам с помощью регулярок, но тут проблема в «обучении» — простешая проверка положения букв в слове генерирует порядка нескольких тысяч «нейронов» помноженное на 630.404 верных слов дают очень долгое время прогона. Более сложные регулярки дадут ещё большее количество вариаций «нейронов» и затраченного времени на обучение. После обучения необходимо сохранить результат работы для дальнейшей обработки, фильтрации и выделения наиболее значимых «нейронов», т.к. весь результат обучения вместе с кодом поместить в 64Кб нереально.
Для себя я сделал вывод, что экспериментирование и обучение подобной сети требует от нескольких дней до пары недель фул-тайм без каких-либо гарантий того, что результат будет удовлетворительным.
Эх, очередная цель опровергнута. Может у кого-то всё же получится совершить чудо — упаковать весь словарь в 100Кб или добиться >= 80% :)
Я уже неделю как застрял на 76%, всё пытаюсь выжать очередные 0.2-0.5% в надежде как-нибудь добраться и до 80%, но пока тщетно. Правда теперь я уже не уверен насколько мои проценты «честны», прочитав комментарии выше по ошибке проверки точности алгоритма.
После нескольких проб остановился на анализе статистики подобных сочетаний для верных слов и фильтрации всего остального — этот способ намного короче, чем пытаться анализировать последовательность согласных на сложность произношения, т.к. в словаре оказалось неожиданно много сложновыговариваемых сочетаний.
И такой фильтр даже работает, но итоговый результат получается хуже из-за того, что реализация занимает место и приходится жертвовать чем-то другим. Если бы генератор генерировал больше случайных последовательность букв, возможно этот вариант бы и сработал, а так слишком много «не-слов» практически не отличиются от «слов», что делает подобную проверку бесполезной (в моём случае).
По поводу комментариев в статье — соглашусь, это кладезь идей и информации о решениях, вот только выбрать правильный подход сложно, и нужно время, чтобы выбранный подход довести до ума
локальные тесты неверныебыл прорыв почти в 3% в тот же день, как я описал, что неделю застрял на 26%.По моему мнению, большинству участников интересно узнать, каких результатов добились остальные. Если разница небольшая, то это огромный стимул, а если разница большая — значит у него тесты неправильные :)
И если кто-то не выкладывает свои результаты из боязни дать другим стимул, то мне интересно увидеть кто каких результатов добился. Давать точные цифры нет смысла, т.к. каждый использует собственный способ оценки и блоки, на которых прогоняется решение локально и будет прогоняться организаторами — разные, а значит результат будет в любом случае отличаться от опубликованного.
Со своей стороны если я у кого-то увижу огромный результат, то я попытаюсь добиться такого же или хотя бы приблизиться к нему. И, к тому же, всегда существует вероятность того, что где-то в тестах у участника была ошибка (т.к. это не официальная таблица результатов), так что опускать руки рано.
В моём случае я действительно оценивал локально по относительно небольшой выборке — 23К блоков. После письма мне самому стало интересно насколько результат будет отличаться, если использовать другие сеты с блоками, поэтому я скачал ещё 2 сета по 10К блоков и протестировал своё решение только на них. По сравнению с предыдущим тестированием результат колеблется в пределах 0,1%.
Судя по
test[ word ] = wordsIndex[ word ] || falseодно и то же слово несколько раз попасться не может, в отличие от блоков по 100 слов. Думаю, чтоObject.keys( test ).lengthне выдаст 1,000,000.Мне нет смысла настаивать на верности или неверности данного способа тестирования, но обратить внимание на этот момент стоит, просто, чтобы быть в курсе возможных расхождений с результатами тестирования блоков по 100 слов.
Я в начале так и делал, но если грубо взять словарь в 10 правильных слов и 100 неправильных (приближённо к реальности), при этом и там и там будет угадываться 10 слов, то в моём случае будет (100% + 10%) / 2 = 55%, а в случае общего замера будет ((10 + 10) / 110) * 100 = 18.2%, что неверно.
Объяснение же разницы уникальных и неуникальных слов довольно простое — всё зависит от количества false-negative для верных слов, т.к. повторяются именно они в связи с ограниченностью количества по сравнению с не-словами, коих невероятное множество. При 1-2% false-negative результат по сравнинею с проверкой блоков по 100 слов будет лучше, а вот при большем количестве false-negative результат будет хуже в связи с тем, что многие повторяющиеся правильные слова будут считаться неверными.
Test correct words - 99.7636%
Test incorrect words - 52.0787%
Average correctness - 75.9212%
Данный подход хорош на первый взгляд, но он может давать довольно ощутимую разницу до ±1% за счёт того, что все слова для проверки уникальны, а в итоговом варианте часто будут встречаться дубликаты слов. Сам столкнулся с этим, и в моих случаях чаще было, когда дубликаты ухудшали результат, чем улучшали. Поэтому я предпочитаю делать быстрый прогон на предмет улучшений используя два словаря (от него и отталкиваюсь), но итоговый процент всё же прогоняю на тестовых блоках по 100 слов (он точнее, но проверка намного дольше из-за большого кол-ва файлов).
с самим собойза каждые 0.2-0.3%.Пробовал создать псевдо-нейронную однослойную сеть, которая бы собирала статистику по словам с помощью регулярок, но тут проблема в «обучении» — простешая проверка положения букв в слове генерирует порядка нескольких тысяч «нейронов» помноженное на 630.404 верных слов дают очень долгое время прогона. Более сложные регулярки дадут ещё большее количество вариаций «нейронов» и затраченного времени на обучение. После обучения необходимо сохранить результат работы для дальнейшей обработки, фильтрации и выделения наиболее значимых «нейронов», т.к. весь результат обучения вместе с кодом поместить в 64Кб нереально.
Для себя я сделал вывод, что экспериментирование и обучение подобной сети требует от нескольких дней до пары недель фул-тайм без каких-либо гарантий того, что результат будет удовлетворительным.
Я уже неделю как застрял на 76%, всё пытаюсь выжать очередные 0.2-0.5% в надежде как-нибудь добраться и до 80%, но пока тщетно. Правда теперь я уже не уверен насколько мои проценты «честны», прочитав комментарии выше по ошибке проверки точности алгоритма.