Comments 21
Antelle смог набрать больше 83% без пункта 13
Хотелось бы посмотреть на его решение. Идея с заменой групп суффиксов-префиксов очень хороша. Остальное всё примерно тоже самое: надо было коэффициенты всё же не вручную крутить.
UFO just landed and posted this here
можно ваше решение отправить и получить бабки?
Есть готовые мат библиотеки для подбора вектора коэффициентов, минимизирующих функцию. В вашем случае что-нибудь из симплекс метода подошло бы Например, для .NET платная библиотека но 30 дней бесплатно.
Я не понимаю оптимизацию с суффиксами. Если например отрезать все 's или заменить, то елементарный тест с приписыванием 's ко всем правильным словам даст гору неправильных true. Или это просто подстройка под конкретный генератор, где 's встречается довольно редко?
Да, конечно это даст гору неправильных true.
Но благодаря уменьшению количества слов возрастает точность блум фильтра настолько, что он даёт настолько меньше ложно положительных срабатываний, что суммарная точность увеличивается.
Разумеется, это подстройка под конкретный генератор. Если бы генератор генерировал не-слова с идеальным распределением частот биграм, идеальными длинами соответствующими словарю, морфологически правильные и никогда не ошибался, генерируя больше повторов, чем случайная выборка из словаря — я бы тогда использовал другие методы.
Но также это подстройка под конкретный выданный словарь из 600к+ слов: в нём словоформы 's встречаются достаточно часто, но не так много слов, которые есть с суффиксом 's, но не существуют без этого суффикса.
Почти каждая использованная мной эвристика (кроме блум-фильтра в чистом виде на весь словарь) дала мне какое количество ложных срабатываний и истинных. И я её оставлял только в том случае, если точность росла. Иногда приходилось удалять какие-то эвристики, потому что появились более крутые или соотношение ложных/верных срабатываний становилось меньше текущей точности
Но благодаря уменьшению количества слов возрастает точность блум фильтра настолько, что он даёт настолько меньше ложно положительных срабатываний, что суммарная точность увеличивается.
Разумеется, это подстройка под конкретный генератор. Если бы генератор генерировал не-слова с идеальным распределением частот биграм, идеальными длинами соответствующими словарю, морфологически правильные и никогда не ошибался, генерируя больше повторов, чем случайная выборка из словаря — я бы тогда использовал другие методы.
Но также это подстройка под конкретный выданный словарь из 600к+ слов: в нём словоформы 's встречаются достаточно часто, но не так много слов, которые есть с суффиксом 's, но не существуют без этого суффикса.
Почти каждая использованная мной эвристика (кроме блум-фильтра в чистом виде на весь словарь) дала мне какое количество ложных срабатываний и истинных. И я её оставлял только в том случае, если точность росла. Иногда приходилось удалять какие-то эвристики, потому что появились более крутые или соотношение ложных/верных срабатываний становилось меньше текущей точности
Всё равно не понимаю. Оптимизируя 's можно выиграть ~140000 слов. Это теоретически улучшает фильтр на 0.07, т.е. 15% против 18.5%, итого 3.5% улучшения. НО остается ~490000 слов для которых НЕТ формы с 's, если взять их малую часть и тупо дописать 's то будет не выигрыш, а серьёзный проигрыш от такой оптимизации.
Откуда числа 15, 18.5 и 0.07?
Вот так вычисляется вероятность ложно положительных срабатываний:
При длине фильтра 500 000 бит и k = 1 это даёт примерно 63% для 500 000 слов против 72% для 630 000 слов. Разница существена.
Но если бы генератор треша был другой, то это улучшение могло бы стать ухудшением.
Вот так вычисляется вероятность ложно положительных срабатываний:
При длине фильтра 500 000 бит и k = 1 это даёт примерно 63% для 500 000 слов против 72% для 630 000 слов. Разница существена.
Но если бы генератор треша был другой, то это улучшение могло бы стать ухудшением.
Берём тест с 50% правильных и 50% неправильных слов. Соответственно false positive влияет только на половину, 50*0.7 и 50*0.63, т.е. получаем 65% и 68.5% правильных ответов. http://hur.st/bloomfilter?n=630000&p=0.7 И http://hur.st/bloomfilter?n=490000&p=0.63
Да, +4.5% итоговой точности. И это оказалось больше, чем потери из-за специфики генератора и словаря: я выиграл на этом 1-2%, а не 4.5, как хотелось бы. Даже если прирост составил бы 0.1% я бы использовал этот метод
Интересно, почему все пользуются блум-фильтром? Ведь Golomb-coded sets занимают меньше места.
Sign up to leave a comment.
Конкурс по классификации слов от Hola или «где взять ещё один процент?»