Увидел пост о конкурсе, когда прошло уже две недели после начала. Но задача показалась крайне увлекательной, и я не ошибся в этом, нырнув в решение с головой. Хочу поделиться решением на 80+% и своими впечатлениями в этом посте.
Всё моё участие прошло под вопросом «где взять ещё один процент?», но в ответ я чаще получал сотые доли процента или ничего. Итак, обо всём по порядку.
Писал на C++, поскольку JS совсем не знаю, а готовое решение переводил на JS с помощью коллеги.
Первое, что я попробовал — это блум-фильтр. Сократил словарь: привёл к нижнему регистру все слова, заменил все слова в словаре оканчивающиеся на 's на префикс, отвёл под блум фильтр 60 кб. В качестве хэш-функции выбрал линейный генератор h[i] = 115249 * (h[i-1] + w[i]) + 33391. В итоге точность получилась не очень высокая, порядка 60%, но с чего-то нужно начинать.
Второе. Добавил фильтрацию по редким сочетаниям символов: не содержит 6 гласных подряд, не содержит 6 согласных подряд. Если длина слова больше трёх, то не должно идти подряд три одинаковых буквы.
Третье. Посмотрел на соотношение слова/мусор в зависимости от длины и начал возвращать результат «мусор» на все тесты длиннее 13 символов.
Четвёртое. Мусор содержит большее количество слов с кавычкой. Новое правило: на всё, что содержит кавычку (не считая 's) говорить «не слово». После этого точность была в районе ~74%.
Пятое. Посчитал вероятности всех биграм и начал выбрасывать все слова, что имеют мало-вероятные биграмы. Посчитал частотность биграм для всех слов из словаря и начал считать вероятность того, что это слово или случайная последовательность байт. Использовал три значения на основе вероятностей биграм: их сумма; логарифм их произведения и сумма их корней. Построил графики в gnuplot, получились красивые картинки.
Очень обрадовался увиденным графикам, но в итоге это дало лишь 76.4% после ручной подгонки коэффициентов. Из недостатков: минус 1400 байт для блума.
Шестое. Построил графики по частоте букв, взял аналогично сумму/логарифм произведения. Качество улучшить не удалось, биграмы уже дали хорошую фильтрацию.
Седьмое. Заметил, что слова из треша генерируются неравномерно и повторов намного чаще. Добавил стоп-лист из топа (20 штук). Память пошла в ущерб блум-фильтру, но суммарная точность увеличилась на +0.1-0.2%. В этом месте я подумал, что потенциал блум фильтра ещё не до конца использовал.
Восьмое. Решил сохранять в блум-фильтр не слова, а только префиксы длинной 3-6. Их намного меньше из-за повторов и точность блум-фильтра сильно выросла. 77.8%. Решил, что можно хранить не стоп-лист треша, а сохранить это прямо в фильтр. Завёл целочисленный массив, на каждое слово добавлял 1, на каждый повторяющийся треш уменьшал на количество повторов, потом установил в фильтре только те биты, где было положительное число. Перестал устанавливать биты на те слова, которые не проходят проверку по частотности биграм или другие: освободилось место в блум-фильтре. Заодно поднял границу из п.3. Итого получил 79%+
Девятое. Попробовал считать триграмы. Для экономии памяти учитывал только первый и третий символ, построил частоты/графики аналогично пятому пункту. Точность подросла на 0.05%, но уменьшение размера фильтра на ещё 1500 символов вызывало закономерное уменьшение точности. В итоге отказался от этого пункта.
Десятое. Заметил, что вероятности биграм зависят от положения в слове. Наиболее явно это заметно для последних двух символов и для первых двух. Добавил соответствующие эвристики. А заодно «слово не заканчивается на Q». А вот идеи, позаимствованные из лингвистики и правил словообразования (ing форма, множественное число, и тд) дали только ухудшения.
Одиннадцатое. Много подгонял все константы в коде. Думаю, что правильнее было написать какое-то автоматизированное средство, но времени осталось уже мало. Итого взял размер блум-фильтра 502122 байт; в него ложил префиксы длинной 8 символов; а фильтровал по длине слова > 18. Получилось 80.5+%
Двенадцатое. Мусор, который не случайный, выглядит как слова с ошибкой. Поэтому появилась идея: добавить в тестируемое одну ошибку и проверить, получился ли совсем мусор или что-то похожее на слово? Собрал кучу статистики, провёл кучу экспериментов, но нулевой или отрицательный результат. Удалось ли кому-нибудь довести до ума такую проверку?
Тринадцатое. Обратил внимание на неравномерность не-слов. Они появляются либо слишком часто, либо лишь однажды (на выборке разумного размера). Начал сохранять все запросы и после 1.5млн проверять, было ли оно уже? Если раньше никогда не было — значит это мусор. Если раньше было более 5 — значит тоже мусор. Ну и заодно раз в 10 миллионов слов прорежал свой массив удаляя уникальные слова, чтобы память не закончилась. Итого на каждый миллион у меня получилось увеличение точности около 1%. Например, на выборке из 3 500 000 слов я получил 84%, а на 5 000 000 уже более 85%.
На этом время подошло к концу, начал дёргаться глаз каждый раз как я видел, что точность падает на 1-5 % вместо роста, да и действительно хороших идей не появилось. Интересно, возможно ли набрать 83-85% без 13го пункта? С каждой добытой десятой и сотой эти числа кажутся всё более реальным, но всё ещё далёкими. Такими же далёкими как 80% во второй день.
Итоговое решение лежит здесь: github.com/knst/word-classifier
Для JS нужно подготовить данные, после выполнения С++ программы сделать:
$ cat bigrams.bin bloom.bin > data && gzip data
Автор: knstqq
