Comments 30
Результат ухудшился. Но ведь он должен был улучшиться!
Я тоже сначала попался на эту удочку, но дело в том, что алгоритм после этого помимо правильных слов (которые он находит в 100% случаев), находит множество неправильных.
Да и ужать оставшиеся 300000 слов в 64KiB, даже с trie patricia и gzip'ом не получится. У меня получилось ужать только чуть больше 100000 слов в отведенные рамки памяти. Да и то, все слова не превышали определенную длину.
Но за статью Спасибо, было интересно узнать, как эту задачу решали другие.
За пару дней до окончания конкурса пришел к мысли об обучении на входящих данных.
Для эффективного обучения были нужны десятки миллионов слов, а у меня были только 6,5M, что бы не ждать выкачивания сделал генератор
if (rand(1) < 0.5) {return rand(0, 10000)} else {return rand(10000, 40000)}
Сначала понял что можно обучить базу до 99,98%. Не поверив в счастье несколько раз перечитал условия конкурса и решил рискнуть.
Основная проблема в проседании на старте, для нивелирования необученности поставил алгоритмы эвристика+обучение последовательно. Эвристика дает 75% (тут у меня был самый популярный вариант суффиксы + двойки\тройки), поэтому после обучения базы до этого процента она отключается что бы не мешать.
Результат: i.imgur.com/IK3LCZ6.png
На графике прогон имеющихся 6,5М слов 5 раз по кругу, поэтому мат.ожидание неправильных x5 от нормального и обучение прошло некорректно. Как результат асимптота в районе 91% На корректных данных к 20М получается 95%, 100М дают 99,9%.
Для эффективного использования памяти база очищается от слов с низким мат. ожиданием, потребление памяти растет до 1,2Gb к 10М и стабилизируется на этом уровне. Скорость работы порядка 1М слов в минуту.
Осталось дождаться решения организаторов по кол-ву запусков.
Сольют, но не настолько. Если я правильно понимаю, если ограничить словарь не-слов размером словаря слов, то к 5-6М анализ частот сольётся до уровня return true;
Как достоверно определить невозможность обучения? Какой алгоритм использовать взамен?
Тогда на неравномерных данных будет отключаться, даже если они норм.
Допустим первые 1000 (10, 10000) слов правильные. Или из первых 40000 каждое повторяется минимум четырежды.
Короче, лучше, но не панацея.
Да нет. Для любого алгоритма можно попасть на (или специально подобрать) плохие данные. И результативность в худшем случае — одна из метрик.
Вы не поверите) Генератору слов в задаче далеко до идеального.
Например в первых 63к 'phy' встречается 10 раз. В 250к уже 32 раза. При среднем мат.ожидании 0,1 и 0,4 соот-но. Превышение на несколько порядков. И это не правильное слово.
С наскоку, как многие предлагают «словарик с каунтерами», получается ~80%.
Лечится подсчетом мат. ожидания топа выборки и его размера. Для правильных слов есть ограничение снизу\сверху. Снизу отсекаем неверные редкие, сверху отсекаем откровенные заскоки генератора. Пока топ слишком мал или слишком велик (но я заложил только снизу) никаких прогнозов не даем.
Если генератор переделать в режим 50\50 и установить ограничение на размер топа сверху то выборка никогда не обучится.
В идеальном рандоме это как раз вполне норм.
Я говорю о том, что для любого алгоритма есть "плохие" и "хорошие" входные данные. Для анализа слов плохие входные — это всякие опечатки похожие на нормальные слова, или суффикс от одного слова, приставленный к другому. Для анализа частот — просто определенный порядок слов и не-слов.
ИМХО, в отрыве от ограничений на генератор, первое лучше чем второе. Хотя в реальной жизни данные первого типа встречаются скорее всего чаще.
Жаль, что конкурс прошел мимо меня — узнал о нем только из первой части этой статьи.
Интересно, будут ли в ТОП10 действительно уникальные решения? Исходя из комментов под статьями о конкурсе, набор идей более-менее стандартен: суффиксы, блум-фильтр, нейросети, анализ частот.
Но идея эта приходила в голову многим.
Отпуск по-программистски, или как я не поучаствовал в конкурсе по программированию на JS. Часть вторая