Конкурс по класифікації слів від Hola або «де взяти ще один відсоток?»

Побачив пост про конкурс, коли минуло вже два тижні після початку. Але завдання здалася дуже захоплюючою, і я не помилився в цьому, пірнувши в рішення з головою. Хочу поділитися рішенням на 80+% і своїми враженнями в цьому пості.

Все моє участь пройшло під питанням «де взяти ще один відсоток?», але у відповідь я частіше отримував соті частки відсотка або нічого. Отже, про все по порядку.

Писав на C++, оскільки JS зовсім не знаю, а готове рішення перекладав на JS за допомогою колеги.

Перше, що я спробував — це блум-фільтр. Скоротив словник: призвів до нижнього регістру всі слова, замінив всі слова в словнику закінчуються на 's на префікс, відвів під блум фільтр 60 кб. В якості хеш-функції вибрав лінійний генератор h[i] = 115249 * (h[i-1] + w[i]) + 33391. В результаті точність вийшла не дуже висока, близько 60%, але з чогось потрібно починати.

Друге. Додав фільтрацію за рідкісним поєднанням символів: не містить 6 голосних підряд, не містить 6 приголосних підряд. Якщо довжина слова більше трьох, то не повинно йти підряд три однакові літери.

Третє. Подивився на співвідношення слова/сміття в залежності від довжини і почав повертати результат «сміття» на всі тести довший 13 символів.

Четверте. Сміття містить більше кількість слів з лапкою. Нове правило: все, що містить лапки (не рахуючи 's) говорити «не слово». Після цього точність була в районі ~74%.

П'яте. Порахував ймовірності всіх биграм і почав викидати всі слова, що мають мало-ймовірні биграмы. Порахував частотність биграм для всіх слів зі словника і почав вважати ймовірність того, що це слово або випадкова послідовність байт. Використовував три значення на основі ймовірностей биграм: їх сума; логарифм їх твори та сума їх коренів. Побудував графіки в gnuplot, вийшли гарні картинки.

image

Дуже зрадів побаченим графіками, але в підсумку це дало лише 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/hola/challenge_word_classifier

Для JS потрібно підготувати дані, після виконання С++ програми зробити:

$ cat bigrams.bin bloom.bin > data && gzip data

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.