Pull to refresh

Comments 30

Результат ухудшился. Но ведь он должен был улучшиться!

Я тоже сначала попался на эту удочку, но дело в том, что алгоритм после этого помимо правильных слов (которые он находит в 100% случаев), находит множество неправильных.

Да и ужать оставшиеся 300000 слов в 64KiB, даже с trie patricia и gzip'ом не получится. У меня получилось ужать только чуть больше 100000 слов в отведенные рамки памяти. Да и то, все слова не превышали определенную длину.

Но за статью Спасибо, было интересно узнать, как эту задачу решали другие.
В отсутствие wtire-аккаунта, попытаюсь откомментировать тут, может примут…

За пару дней до окончания конкурса пришел к мысли об обучении на входящих данных.
Для эффективного обучения были нужны десятки миллионов слов, а у меня были только 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М слов в минуту.

Осталось дождаться решения организаторов по кол-ву запусков.
Я правильно понимаю, что ты запихал не результат сетки, а саму сетку, и она у тебя обучается в процессе работы программы? Если так, то это реально круто :)
«Сетка» скорее всего в виде массива с частотой, ключи в котором — хэши слов. Стат. метод работает только при истинности предпосылки о «редкости» неправильных слов. Если набор неправильных слов в тестовой выборке ограничить примерно тем же количеством, что и словарь правильных слов, то выигрыша от «дообучения» не будет.
Тогда остальные алгоритмы тоже сольют, у большинства false positive в разы больше false negative.

Сольют, но не настолько. Если я правильно понимаю, если ограничить словарь не-слов размером словаря слов, то к 5-6М анализ частот сольётся до уровня return true;

Все верно, результат будет в районе 50%. А насчет того что остальные сольют я уже не уверен. У них результаты по идее сильно измениться не должны.
Если написано адекватно то при невозможности обучения алгоритм отвечает «я не знаю». Он может так ответить и после 10 объявлений и после 10М.
Да, но к этому надо быть изначально готовым. Т.е. надо предположить, что тестовый генератор может изменится. А организаторы обещали его не менять. Вот только понять, что его дурят он сможет далеко не сразу.

Как достоверно определить невозможность обучения? Какой алгоритм использовать взамен?

Процент выдачи правильных начнет расти слишком быстро, быстрее чем на нормальных данных, это несложно отследить. А взамен использовать те же алгоритмы что и остальные: блюм и пр.

Тогда на неравномерных данных будет отключаться, даже если они норм.


Допустим первые 1000 (10, 10000) слов правильные. Или из первых 40000 каждое повторяется минимум четырежды.


Короче, лучше, но не панацея.

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

Да нет. Для любого алгоритма можно попасть на (или специально подобрать) плохие данные. И результативность в худшем случае — одна из метрик.

Я обсуждал только тот вариант, когда генератор выдает не-слова из какого-то определенного набора.

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

>Или из первых 40000 каждое повторяется минимум четырежды
Вы не поверите) Генератору слов в задаче далеко до идеального.
Например в первых 63к 'phy' встречается 10 раз. В 250к уже 32 раза. При среднем мат.ожидании 0,1 и 0,4 соот-но. Превышение на несколько порядков. И это не правильное слово.
С наскоку, как многие предлагают «словарик с каунтерами», получается ~80%.
Лечится подсчетом мат. ожидания топа выборки и его размера. Для правильных слов есть ограничение снизу\сверху. Снизу отсекаем неверные редкие, сверху отсекаем откровенные заскоки генератора. Пока топ слишком мал или слишком велик (но я заложил только снизу) никаких прогнозов не даем.
Если генератор переделать в режим 50\50 и установить ограничение на размер топа сверху то выборка никогда не обучится.

В идеальном рандоме это как раз вполне норм.


Я говорю о том, что для любого алгоритма есть "плохие" и "хорошие" входные данные. Для анализа слов плохие входные — это всякие опечатки похожие на нормальные слова, или суффикс от одного слова, приставленный к другому. Для анализа частот — просто определенный порядок слов и не-слов.


ИМХО, в отрыве от ограничений на генератор, первое лучше чем второе. Хотя в реальной жизни данные первого типа встречаются скорее всего чаще.

Дело не совсем в генераторе. Все дело в том, что на таких небольших длинах слов, кол-во не-слов крайне ограничено. Например для длины в 1 символ такое не-слово всего-то одно, это апостроф. Вот и получается, что генератор пытается генерировать не только одинаковое кол-во слов и не-слов, но и чтобы распределение по длинам слов было одинаковым. Т.е. выдали 20 однобуквенных слов, значит надо выдать и 20 однобуквенных не-слов, которое у нас всего одно. С двухбуквенными комбинациями такая же история, с трехбуквенными правда насколько я помню кол-во не-слов больше кол-ва слов, но генератор ведь тоже не все подряд генерит, а с разными степенями сходства с настоящими словами. Т.е. на маленьких длинах слов ему просто не хватает пространства для маневра.
Неизвестен результат работы каждой конкретной функции, каким образом сеть учится?
Словарь слов ограничен, а словарь не-слов — нет. Просто запоминает все входящие слова и те которые часто повторяются считает словами из словаря. И там нет никакой сети. Там десяток строк кода.

Жаль, что конкурс прошел мимо меня — узнал о нем только из первой части этой статьи.


Интересно, будут ли в ТОП10 действительно уникальные решения? Исходя из комментов под статьями о конкурсе, набор идей более-менее стандартен: суффиксы, блум-фильтр, нейросети, анализ частот.

Нейросетей там скорее всего не будет.

Но идея эта приходила в голову многим.

И не только эта ;) Don_Eric к примеру сыпал идеями как из рога изобилия, я про многие вещи даже не слышал.
Интересно а никто не пробовал вытащить часть словаря из ПИ? )))
И это тоже обсуждали. Но там очевидно что смещение каждого слова займет больше места чем сами слова.
Ну а если разбить словарь на куски и каждому куску искать смещение? По идее кусок встречается чаще чем все вместе.
Все равно выйдет дороже. В лучшем случае вы сконвертите словарь в смещения, которые в сумме займут столько же ), но попробуйте.
Ну я думаю вы правы, просто сама идея гениальна )
Sign up to leave a comment.