Comments 86
А можно получить ваши базу неправильных слов, раз уж вы проделали эту работу?
Да, только она сейчас неполная. Перед тем, как скармливать данные майнингу, я убрал из неё то, что отсекается описанными в этой статье простыми фильтрами. Сейчас в ней порядка 38М слов.
у меня дерево решений глубиной 7 с 250 узлами давало 65%
самые важные фичи: кол-во согласных, кол-во согласных подряд, позиция расположения ' с начала слова/с конца слова, буква после ', сумма букв, где каждая буква это ее частота появления в словаре
самые важные фичи: кол-во согласных, кол-во согласных подряд, позиция расположения ' с начала слова/с конца слова, буква после ', сумма букв, где каждая буква это ее частота появления в словаре
На каком объеме данных? Слова были уникальными, или так, как спарсили, так и передавали, включая повторы?
Первым делом нужно отсечь бессмысленное 's на конце слов и получим сокращение словаря до 490822. Затем можно отсечь все слова, содержащие апостроф — их всего несколько сотен (~350, false-negative 0,07%) против 100 тыс на 1 млн неверных слов (~10%), итого получаем словарь вообще без апострофов. Две простейшие регулярки дают офигенный профит.
Во второй части будет описание, как я уменьшил словарь до 390000 без потерь.
Наоборот — отбросить слова не содержащие 's на конце, но такие которые есть с 's на конце. Для себя решил, что мое решение вообще не должно давать false-negative.
Кусочек отчета теста одной из последних версий — http://dl2.joxi.net/drive/2016/05/28/0001/1653/99957/57/1518a62432.jpg
Кусочек отчета теста одной из последних версий — http://dl2.joxi.net/drive/2016/05/28/0001/1653/99957/57/1518a62432.jpg
Это моей было ключевой стратегией для уменьшения размера словаря – выделить слова, включающие в себя другие слова, и закодировать, сколько букв спереди или сзади можно отбросить для получения правильных слов.
Я пытался использовать стемер, но это не дало удовлетворительного результата. Слишком много слов которые не поддаются такой обработке и их приходилось либо игнорировать, либо добавлять в виде исключений.
Стемер мне тоже не помог. Сделал тупо серией sql-запросов. Сами запросы будут во второй части.
На самом деле результат стемера можно было бы сильно улучшить если сохранять правила стеминга которые не были вообще применены к словарю, и отдельно обрабатывать слова, которые дают в стемере исключительные результаты — скажем единственный уникальный корень из всего словаря или подпадают под единственное правило, но я понял, что у меня просто не хватит времени все это учесть и придумать как сжать.
Что ж, ждем вторую часть )
Что ж, ждем вторую часть )
кстати, если на Азуре, то дешевле и проще было проверять алгоритмы на Azure ML
Там легко заменяются сети на деревья, быстро настраиваются, автоматически находятся important features, tuning параметров…
Там легко заменяются сети на деревья, быстро настраиваются, автоматически находятся important features, tuning параметров…
SQL база у меня была локальная. Я хотел попробовать Azure ML, но споткнулся о существенную разницу в скорости выполнения запросов между азуровским и локальным SQL-серверами. В частности, создания таблицы с несуществующими четвёрками согласных, на азуре я так и не смог дождаться. Понимаю, что можно было поработать над оптимальностью запросов, но задача была другой.
Примерно такой код дает примерно 61% точности
var lh = [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1];
module.exports = {init:function() {
}, test:function(word) {
return !!lh[word.length];
}};
Проверил. Не даёт. На 1000 блоках 55.27%
1. 1000 блоков вообще ничто. Я начинаю чему-либо верить от 50k блоков
2. Это набросок, который потом ушёл под тюнинг на видеокарту, и там уже были совсем другие коэфициенты.
Перепосчитал
test 0-200k 61.98225%
crossvalidation 200k-400k 61.9829%
2. Это набросок, который потом ушёл под тюнинг на видеокарту, и там уже были совсем другие коэфициенты.
Перепосчитал
Решение
data.gz
solution.js
function c(a,l,h){return(a<l)?0:(a>h)?h-l:a-l};r=function(w){w=w.replace(/\'/g,'`');f1=c(w.length,3,32);return!!([0,0,0,1,1,1,1,1,1,1][f1])}
solution.js
var a;module.exports={init:function(b){a=eval(b.toString())},test:function(b){return a(b)}}
test 0-200k 61.98225%
crossvalidation 200k-400k 61.9829%
а как использовали видеокарту?
Было ~50 фич, которые переводили слово в некоторый диапазон.
1. Длина слова от 3 до 30
2. ASCII Код буквы на позиции от 0 до 20 (' преобразовывал в `)
3. Количество вхождений буквы a-z`
Для каждой фичи для 8M слов подсчитан результат и закэширован.
В начале есть дерево из 1 узла. Точность решения 50%
Дальше перебираются все возможные варианты как можно поделить этот узел на N узлов при помощи какой-то фичи.
Выбирается фича и узел которые имеют больше всего сумму abs(pos-neg) на всех узлах, которые образуются после разделения узла на много узлов.
А теперь всё тоже самое, только 8000 раз.
1. Длина слова от 3 до 30
2. ASCII Код буквы на позиции от 0 до 20 (' преобразовывал в `)
3. Количество вхождений буквы a-z`
Для каждой фичи для 8M слов подсчитан результат и закэширован.
В начале есть дерево из 1 узла. Точность решения 50%
Дальше перебираются все возможные варианты как можно поделить этот узел на N узлов при помощи какой-то фичи.
Выбирается фича и узел которые имеют больше всего сумму abs(pos-neg) на всех узлах, которые образуются после разделения узла на много узлов.
А теперь всё тоже самое, только 8000 раз.
Прошел практически через все эти идеи. Но в итоге откинул решение с тройками.
Ну плюс еще пробовал не раз озвученный фильтр Блюма. Последней идей как сделать его сильно меньше была попытка повысить изотропность добавляющихся в него слов путем их разбивки, но не по количству букв, а с помощью split по букве.
Сначала отбирал слова содержащие в середине наиболее частую в середине слова букву (e), затем среди оставшихся проделывал тоже самое (i) и так далее.
После резал слова по этим символам, так что слов delimiter превращалось в 0d, 1limit, _r (числа перед частями означали их порядок, а _ означал последний блок слова). Список букв разделителей добавляемые в данные однозначно задавал разбиение. В данном случае было например понятно что слово надо бить по e, так как она идет в списке раньше чем i.
Следующей идеей была рекурсивная разбивка, где ei напримерм означало что слово необходимо разделить так: 00d, 10l, 11m, 12t, _0r. Полученные строки добавлял в блюм. Разбиение глубже не помогало ((
В сочетании с несуществующеми парами, практически полностью повторяющими ваше решение и еще одной штукой которую назвал consonantsSignature удалось выжать ~71%.
Так же пытался бить слова на кластеры и хранить данные для каждого кластера отдельно. В чстности ластерами были длины, символы разбиений и более сложные механизмы.
Диапазон слов от 5 до 9 символов назвал изотропным провалом — именно тут мне не удалось добиться приемлемого решения. Ну да логично — там сосредоточено огромное количество слов.
Но это все.
Решение не отправил.
Ну плюс еще пробовал не раз озвученный фильтр Блюма. Последней идей как сделать его сильно меньше была попытка повысить изотропность добавляющихся в него слов путем их разбивки, но не по количству букв, а с помощью split по букве.
Сначала отбирал слова содержащие в середине наиболее частую в середине слова букву (e), затем среди оставшихся проделывал тоже самое (i) и так далее.
После резал слова по этим символам, так что слов delimiter превращалось в 0d, 1limit, _r (числа перед частями означали их порядок, а _ означал последний блок слова). Список букв разделителей добавляемые в данные однозначно задавал разбиение. В данном случае было например понятно что слово надо бить по e, так как она идет в списке раньше чем i.
Следующей идеей была рекурсивная разбивка, где ei напримерм означало что слово необходимо разделить так: 00d, 10l, 11m, 12t, _0r. Полученные строки добавлял в блюм. Разбиение глубже не помогало ((
В сочетании с несуществующеми парами, практически полностью повторяющими ваше решение и еще одной штукой которую назвал consonantsSignature удалось выжать ~71%.
Так же пытался бить слова на кластеры и хранить данные для каждого кластера отдельно. В чстности ластерами были длины, символы разбиений и более сложные механизмы.
Диапазон слов от 5 до 9 символов назвал изотропным провалом — именно тут мне не удалось добиться приемлемого решения. Ну да логично — там сосредоточено огромное количество слов.
Но это все.
Решение не отправил.
Уменьшение словаря до 390К, карта "соседских" двоек и троек, блум и ещё что-то читайте через неделю.
Я пробовал разные алгоритмы фонетического сжатия.
Лучше всего себя показал Porter + Nysiis
Примерная точность 73-75% на миллионе тестовых пар при размере словаря в 130 000 слов.
— Наивный Байес по букве + её позиции давал порядка 63% причем размер финального словаря ужатым получался порядка 10kb
Лучше всего НБ работал на двух буквах + позиции(порядка %73), но результат не вмещался в 63kb
(Естественно тренировка и проверка велась на разных датасетах)
— Еще была идея попробовать разобрать работу генератора через (hidden markov model).
Т.к. генератор можно, по идее, считать марковским процессом. (Не пробовал).
Но я рассуждал так. Если генератор это функция от словаря то ловить, в принципе, там нечего кроме возможных искажений в распределениях.
— Еще была идея отсекать гарантировано не слова по энтропии. (Порог отсечения подобрать бинарным поиском).
— Дальше были идеи как все это ужать через DAWG, Bloom фильтр или count min sketch(для подсчета статистики по каждому ужатому корню). Но, честно говоря, выдохся. Все равно >80% точности было добится не реально.
Решение не отправил.
Лучше всего себя показал Porter + Nysiis
Примерная точность 73-75% на миллионе тестовых пар при размере словаря в 130 000 слов.
— Наивный Байес по букве + её позиции давал порядка 63% причем размер финального словаря ужатым получался порядка 10kb
Лучше всего НБ работал на двух буквах + позиции(порядка %73), но результат не вмещался в 63kb
(Естественно тренировка и проверка велась на разных датасетах)
— Еще была идея попробовать разобрать работу генератора через (hidden markov model).
Т.к. генератор можно, по идее, считать марковским процессом. (Не пробовал).
Но я рассуждал так. Если генератор это функция от словаря то ловить, в принципе, там нечего кроме возможных искажений в распределениях.
— Еще была идея отсекать гарантировано не слова по энтропии. (Порог отсечения подобрать бинарным поиском).
— Дальше были идеи как все это ужать через DAWG, Bloom фильтр или count min sketch(для подсчета статистики по каждому ужатому корню). Но, честно говоря, выдохся. Все равно >80% точности было добится не реально.
Решение не отправил.
Забегая вперёд этой части статьи, скажу, что я пришел к выводу, что из-за того, что большая часть неправильных слов — псевдонеправильные(слова, не поддающиеся отсечению по правилам), единственный вариант решения- формальными правилами уменьшить словарь настолько, насколько это возможно, скормить его блуму или аналогу(если есть), а затем перед проверкой на блуме на входе по редким комбинациям отсекать "мусор".
Как сделать 80%:
Убираем из слов все окончания 's, потом делаем
porter2+bloom+gzip
Профит.
Убираем из слов все окончания 's, потом делаем
porter2+bloom+gzip
Профит.
У меня лучше получилось сжать lzma, даже с учетом 6кб кода на распаковку, я все равно выигрывал порядка +2кб. Т.е. блум фильтр закодированный посимвольно (по 8 бит на символ) в среднем занимал порядка 80 кило. Гзип жал его где-то до 60-62, а lzma до 55-56. Код на распаковку правда при этом также приходилось жать через штатный gzip, т.е. происходила двойная архивация, но оно все равно того стоит.
Можно еще набрутфорсить такие seed значения хэш функций, чтобы было больше коллизий на том же наборе данных. В полтора-два раза размер фильтров может уменьшить.
Я, правда, не успел попробовать блум фильтры. Тут уже кому повезло с чего начать.
Я, правда, не успел попробовать блум фильтры. Тут уже кому повезло с чего начать.
Согласен. Если бы я сразу с него начал, то не было бы этой статьи :-).
На самом деле перебор сидов дает небольшой выигрыш для каждого конкретного варианта, но все равно перебирать пришлось, да. Я перебирал не только сиды но и сами хеш функции, у меня их было 13 штук.
Это получается один блум фильтр на все? А по пути perfect hashing алгоритмов не пробовали, т.е. поделить все на бакеты, в каждом поменьше хэш функций и легче брутфорсить?
Я пробовал разные варианты. Пробовал разбить все слова на группы по их длине и для каждой группы подобрать отдельные блюм фильтры, очевидно что идея потерпела фиаско, поскольку, как я теперь это четко вижу, длина слова не является каким-либо определяющим фактором для его «содержимого». Т.е. полученные группы не обладали какими-либо характерно различимыми признаками. Про «perfect hashing» никогда не слышал. Пробовал в качестве хеша брать не какие-то абстрактные хешилки, а привязанные к структуре слова, которые преобразовывают по принципам гласн/согласн или пары/тройки самых частых заменяли на одни и те же фиксированные значения при расчете хеша всего слова, тут тоже не добился ничего значительного. В итоге остановился на одном единственном блюме для всего, как основе.
А как у Вас получилось сохранить блум в <64k? У меня минимально рабочий с 80% на 390K словаря занимал минимум 120K.
У меня через блум прогонялось около 280к слов, при этом размер фильтра был в районе 500 килобит. Но это среднее, в процессе перебора были разные варианты.
Так а получилось в результате их ужать в <64?
Да, конечно, я ужал его в 55 килобайт. Остальные 10 кило занял код опять же в сжатом виде.
А, забыл совсем уточнить, у меня блюм не по целым словам, а по нграммам. Т.е. я ему скармливал только нграммы длинной 7 букв (причем нграммы не перекрываются, а идут одна за другой плотно, подобрал такую схему перебором), а перед каждой добавлял ее порядковый номер. Т.е. я существенно уменьшил размер входных данных с 280 килослов.
Точно уже не помню, но после Портера и 's остаётся порядка 300к слов. Для достижения 80% коэффициент ошибки для блума должен быть 0.6 кажется… Короче я подобрал такой размер блума чтобы оно после архивации влезало в лимит, на тестах было 78-79 процентов.
Товарищ по работе сделал больше 81%, но он дополнительно вырезал длинные слова, в остальном алгоритм тот же
Товарищ по работе сделал больше 81%, но он дополнительно вырезал длинные слова, в остальном алгоритм тот же
Не могу понять, как в node.js можно сохранить массив, после фильтра Блума в файл в виде битовой последовательности. Или только вариант сохранять в виде строки, а потом обратно переделывать в массив? Я в javascript имел дело с клиентской частью только, поэтому этот вопрос не понятен. Если переделывать в строку, то получается слишком большой размер файла…
var bits = массив с фильтром
var buf = new Buffer(Object.keys(bits).length*4)
var j=0
for(var i in bits){
buf.writeInt32LE(bits[i],i*4)
}
fs.writeFileSync('test1.txt',s,{encoding:"ascii"});Но на самом деле так места занимает больше из-за того, что бинарные данные почти не сжимаются.
Данные ведь можно сжимать с помощью штатного gzip. Правда бинарные данные в виде строки он жмет плохо, лучше жмет данные в виде unsigned32int, когда каждые 32 бита переведены в десятичное число, а еще лучше если все восьмерки битов закодировать в символы по их коду. И скорее всего есть еще удачные варианты, но я до них не дошел.
Без знания того, как генерируются тестовые наборы, невозможно выбрать оптимальный алгоритм.
Код ниже даёт 92% точности на 80М слов, без особой оптимизации
var dic=[];
var avg=1;
function test(w){
var h=2166136261;
for (var i=0;i
var dic=[];
var avg=1;
function test(w){
var h=2166136261;
for (var i=0;i
Код зарезался, но я представляю что там )
Закрыто серверной цензурой.
В превью было нормально, тогда так:
http://pastebin.com/i6YeDJxn
http://pastebin.com/i6YeDJxn
У меня он дал 43%.
На скаченных данных? Я на скаченных проверял.
Да. В любом случае, если он это действительно делает, то Вы победите в этом конкурсе.
я уже не знаю кто победит, каждый день что-то новое
а еще есть англоязычные участники…
а еще есть англоязычные участники…
Видимо зависит от числа слов на котором остановятся организаторы.
На большом числе слов безусловно победят самообучающиеся или гибридные варианты.
На большом числе слов безусловно победят самообучающиеся или гибридные варианты.
Да, все алгоритмы на статистике подобного рода дадут результат близкий к 100% при бесконечном числе блоков. Для данного алгоритма у меня получилось около 98.5% на 1.6 миллиарде слов.
Теперь и я могу начинать кусать локти, потому что искусственно ограничил свой алгоритм, прерывая сбор статистики на 20 миллионах слов )
Интересно, что будут делать организаторы, если таких решений будет много? Ведь у всех будет близко к 100%
Кстати, вышеприведенный алгоритм не совершенен, и при достаточно долгом тестировании он сломается, поскольку значения в массиве dic начнут переполняться. Т.е. нельзя сказать, что данный алгоритм достаточно надёжен. Правда раньше начнут переполняться переменные и в тестирующем скрипте ;) А еще раньше наступит конец света.
Теперь и я могу начинать кусать локти, потому что искусственно ограничил свой алгоритм, прерывая сбор статистики на 20 миллионах слов )
Интересно, что будут делать организаторы, если таких решений будет много? Ведь у всех будет близко к 100%
Кстати, вышеприведенный алгоритм не совершенен, и при достаточно долгом тестировании он сломается, поскольку значения в массиве dic начнут переполняться. Т.е. нельзя сказать, что данный алгоритм достаточно надёжен. Правда раньше начнут переполняться переменные и в тестирующем скрипте ;) А еще раньше наступит конец света.
думаю организаторы поступят как обещали — запустят все алгоритмы на одинаковое кол-во блоков (минимум 1000, но хотя б 10,000), и проверят только топ х алгоритмов на большее кол-во блоков
поправка: обещали запустить одинаковое кол-во блоков для всех участников
Начнём с 1000 блоков, а потом видно будет.
Такое, какое потребуется, чтобы увидеть уверенную разницу между лидерами.
Когда решим, сколько нужно для лучших, прогоним на этом количестве всех.
Думаю, при определенных условиях, такой порядок тестирования мог бы дать шанс алгоритмам, не воссоздающим словарь по дубликатам. Всё зависит от порога, на котором будет отчетливо видна разница между лидерами.
или получится бесконечная рекурсия, которая будет стремится к 100% :)
Это был бы весьма забавный исход. Но, на мой взгляд, отчетливая дифференциация всё же будет, из-за различий в эффективности предварительного фильтра.
Всё больше склоняюсь к мысли, что организаторы не ожидали подобного подхода в реализации, иначе, постарались бы его исключить на этапе постановки задачи. А теперь им остается лишь максимально придерживаться первоначальных условий конкурса.
Всё больше склоняюсь к мысли, что организаторы не ожидали подобного подхода в реализации, иначе, постарались бы его исключить на этапе постановки задачи. А теперь им остается лишь максимально придерживаться первоначальных условий конкурса.
Он дает 92% на моей выборке из 400 килоблоков.
Как я понимаю это решение.
Ясно, что генерированных разных «неслов» гораздо больше, чем реальных слов из словаря.
Поэтому шанс встретить еще раз уже встреченное ранее реальное слово гораздо выше, чем шанс встретить еще раз придуманное слово.
Просто берем от каждого слова хэш и записываем по нему в таблицу количество раз, сколько мы его встретили.
Так же еще ведем подсчет среднего.
Ответ на тест: если значение по хэшу выше среднего, то говорим «да», иначе – «нет».
Минус решения: нужна огромная выборка. Сейчас у меня выборка примерно 200к слов, а точность 52.5%, но она растет и гипотетически приближается к 100%.
Мне кажется, это решение получит приз за оригинальность, но не получит главный приз. Потому что оно фактически не выполняет свою функцию сразу из коробки. На небольших произвольный выборках результат всегда будет плохим.
Ясно, что генерированных разных «неслов» гораздо больше, чем реальных слов из словаря.
Поэтому шанс встретить еще раз уже встреченное ранее реальное слово гораздо выше, чем шанс встретить еще раз придуманное слово.
Просто берем от каждого слова хэш и записываем по нему в таблицу количество раз, сколько мы его встретили.
Так же еще ведем подсчет среднего.
Ответ на тест: если значение по хэшу выше среднего, то говорим «да», иначе – «нет».
Минус решения: нужна огромная выборка. Сейчас у меня выборка примерно 200к слов, а точность 52.5%, но она растет и гипотетически приближается к 100%.
Мне кажется, это решение получит приз за оригинальность, но не получит главный приз. Потому что оно фактически не выполняет свою функцию сразу из коробки. На небольших произвольный выборках результат всегда будет плохим.
Да, тогда уже можно взять и LRU/LFU по размеру словаря и даже в несколько ступеней по префиксам разной длинны, например. Будет быстрее стремиться к 100%. И у кого быстрее, тот и выиграет.
Если вы отправляли это решение, то поздравляю, меня вы точно обойдете! У меня та же самая логика, но она бsла наложена на основной алгоритм в последний день и я совсем не успел ее довести до ума, а ведь в принципе нет никаких ограничений достичь 100%, при этом не выходя по памяти за 1GB. Я был доволен и тем, что дошел до 90%, которые сегодня, после того как я скачал правильную выборку (а не собранную на коленке в последний час) превратились даже в меньшую цифру.
Не отправлял. Код появился после того, как прочитал ваши сообщения в ветке конкурса, чтобы проверить вашу идею. И мне кажется, что организаторы не рассчитывали на решения такого типа.
Кстати, вышеприведенный алгоритм не совершенен, и при достаточно долгом тестировании он сломается, поскольку значения в массиве dic начнут переполняться. Т.е. нельзя сказать, что данный алгоритм достаточно надёжен.Это просто proof of concept, в теме конкурса обсуждают подход, а кода нет (я там писать не могу, кстати).
Расскажу тут в комментариях про 82.05%
* от слов отрезаются самые частые окончания 's, s, ing; слова с апострофом считаются ложными
* основной алгоритм похож на фильтр Блума:
для каждого слова считается хеш-функция, по получившемуся индексу в чанке устанавливается единичный бит;
размер чанка подобран так, что после прохода по словарю остаётся приблизительно 15 нулевых битов;
позиции этих нулевых битов сохраняются в файл;
дальше происходит заполнение нового чанка с новой хеш-функцией, всего таких хеш-фунций около 3000;
при тестировании слова происходит проверка, не попала ли хеш-функция слова на один из этих нулевых битов
* дополнительно используются эвристики для отсечения ложноположительных срабатываний, подсчёт подряд идущих согласных и т.п. (+4% правильных ответов)
* стоит уделить внимание изменяемой хеш-функции, небольшие изменение в мутаторе хеш-функции дали прирост +3%
* для улучшения сжатия файла (~+7% к степени сжатия), сохраняются только расстояния между нулевыми битами, старшие байты, которые имеют схожие значения рядом с нулём, перенесены в отдельную часть файла (сделано с расчётом на gzip, для других архиваторов такая предварительная обработка может навредить)
* от слов отрезаются самые частые окончания 's, s, ing; слова с апострофом считаются ложными
* основной алгоритм похож на фильтр Блума:
для каждого слова считается хеш-функция, по получившемуся индексу в чанке устанавливается единичный бит;
размер чанка подобран так, что после прохода по словарю остаётся приблизительно 15 нулевых битов;
позиции этих нулевых битов сохраняются в файл;
дальше происходит заполнение нового чанка с новой хеш-функцией, всего таких хеш-фунций около 3000;
при тестировании слова происходит проверка, не попала ли хеш-функция слова на один из этих нулевых битов
* дополнительно используются эвристики для отсечения ложноположительных срабатываний, подсчёт подряд идущих согласных и т.п. (+4% правильных ответов)
* стоит уделить внимание изменяемой хеш-функции, небольшие изменение в мутаторе хеш-функции дали прирост +3%
* для улучшения сжатия файла (~+7% к степени сжатия), сохраняются только расстояния между нулевыми битами, старшие байты, которые имеют схожие значения рядом с нулём, перенесены в отдельную часть файла (сделано с расчётом на gzip, для других архиваторов такая предварительная обработка может навредить)
Вообще надо было заменять группы окончаний и суффиксов на отдельные символы, а не просто отрезать их. Но идея пришла слишком поздно.
Поразительно! Прям как у меня. Тока у меня попроще. Намного проще ну и результат 79% Не удалось дойти до 80+% Перепробовал кучу всего. Даже начал нейронные сети но, что то меня остановило и я перешел обратно к эвристикам + нечто типа блюма. Эвристики устроены таким образом, что почти все хорошие слова — проходят проверку, плохие отсекаются. Далее есть битовая таблица 65536*8 =524288 бит. И те кто прошел проверки (порядка 280тыс), вычисляется хеш, отрезается по модулю длинной массива и ставится один единственный бит. Получается бит на одно слово. Но не все так идеально — и плохие слова совпадали с хорошими(из-за модуля). Далее я вынес все параметры алгоритма и дал им некий порог и запустил проверку всех возможных комбинаций параметров — составив в итоге список самых лучших подборок параметров. Параметры нашлись, но возникла другая проблема — данные не ужимались ) И код не влазил. Пришлось из кода выкинуть часть и максимум его оптимизировать и уменьшить сами данные, что не очень сильно повлияло на результат.
Тоже расскажу про свои 81.5%:
1) От слов отрезаются префиксы и суффиксы.
2) Несколькими эвристиками отрезаются «неслова» (больше 14 букв, много гласных/согасных подряд/в_конце_слова, апостроф в слове)
3) Немного модифицированный bloom: вместо добавления в фильтр битов hash1(word) и hash2(word) добавляются hash1(word.substring(0,6)) и hash2(word.substring(0,9)), что дало сокращение false positives и примерно +1% к результату
4) За полчаса до дедлайна осознал, что bloom filter тоже можно «обучать» удаляя из него биты с false_positives больше positives. «В полубессознательном состоянии» до дедлайна удалось выжать из этой идеи +0.5%. Уже после дедлайна это обучение дало почти 83%
1) От слов отрезаются префиксы и суффиксы.
2) Несколькими эвристиками отрезаются «неслова» (больше 14 букв, много гласных/согасных подряд/в_конце_слова, апостроф в слове)
3) Немного модифицированный bloom: вместо добавления в фильтр битов hash1(word) и hash2(word) добавляются hash1(word.substring(0,6)) и hash2(word.substring(0,9)), что дало сокращение false positives и примерно +1% к результату
4) За полчаса до дедлайна осознал, что bloom filter тоже можно «обучать» удаляя из него биты с false_positives больше positives. «В полубессознательном состоянии» до дедлайна удалось выжать из этой идеи +0.5%. Уже после дедлайна это обучение дало почти 83%
Закину и про свое решение в 81%
В основе алгоритма фильтр блума.
Но не по целым словам, а по нграммам: слово разбивается на части по фиксированному шаблону и эти части уже заносятся в фильтр.
Само решение результат перебора, который перебирал seed для хеш функции, сами хеш функции, размеры фильтра, параметры для разбивки на нграммы и списки частых суффиксов и префиксов, и пр. После чего выбиралось лучшее решение, которое после сжатия вместе с кодом влезало бы в 65536 байт.
Особенности:
-код решения вынесен в доп. данные и сжат gzip'ом, основной код в файле просто запускает его через eval
-битовый массив блума переводится в символьное представление (по 8 бит на символ) (такое представление жмется лучше всего)
-также символьное представление блума дополнительно сжимается по алгоритму LZMA (даже с учетом размера кода на распаковку мы остаемся в выигрыше примерно на 2 кб по сравнению с gzip сжатием)
Эвристики:
-удаляем из слов частые суффиксы и префиксы (как перед обучением, так и перед тестированием)
-все что по длине меньше 3 считаем за true
-все что по длине больше 17 считаем за false
-все слова, в которых есть апостроф, кроме тех которые заканчиваются на 's, считаем за false
-проверка на редкие пары символов (142 пары)
В последний день перед отправкой я понял, что могу использовать накопленную статистику. Попробовав разные варианты остановился на том, который дает 90% (а по правде 86% как потом оказалось) на большой выборке, побоялся за переполнение по памяти и ограничил сбор статистики на 20 миллионах слов, хотя эта проблема решается на раз-два, но был уже вечер и я затупил.
В основе алгоритма фильтр блума.
Но не по целым словам, а по нграммам: слово разбивается на части по фиксированному шаблону и эти части уже заносятся в фильтр.
Само решение результат перебора, который перебирал seed для хеш функции, сами хеш функции, размеры фильтра, параметры для разбивки на нграммы и списки частых суффиксов и префиксов, и пр. После чего выбиралось лучшее решение, которое после сжатия вместе с кодом влезало бы в 65536 байт.
Особенности:
-код решения вынесен в доп. данные и сжат gzip'ом, основной код в файле просто запускает его через eval
-битовый массив блума переводится в символьное представление (по 8 бит на символ) (такое представление жмется лучше всего)
-также символьное представление блума дополнительно сжимается по алгоритму LZMA (даже с учетом размера кода на распаковку мы остаемся в выигрыше примерно на 2 кб по сравнению с gzip сжатием)
Эвристики:
-удаляем из слов частые суффиксы и префиксы (как перед обучением, так и перед тестированием)
-все что по длине меньше 3 считаем за true
-все что по длине больше 17 считаем за false
-все слова, в которых есть апостроф, кроме тех которые заканчиваются на 's, считаем за false
-проверка на редкие пары символов (142 пары)
В последний день перед отправкой я понял, что могу использовать накопленную статистику. Попробовав разные варианты остановился на том, который дает 90% (а по правде 86% как потом оказалось) на большой выборке, побоялся за переполнение по памяти и ограничил сбор статистики на 20 миллионах слов, хотя эта проблема решается на раз-два, но был уже вечер и я затупил.
В общем и целом все как у всех, но не сделал очевидной вещи — фильтрации битов. Также есть неочевидная для меня вещь которую реализовал Antelle: вместо удаления суффиксов-префиксов, надо было заменять их на другие из группы. Но у него и результат 83,5%.
У меня было бы еще меньше 81% если бы я не сэкономил несколько килобайт сжав блюм не гзипом, а lzma.
У меня было бы еще меньше 81% если бы я не сэкономил несколько килобайт сжав блюм не гзипом, а lzma.
Кстати, если кто-то хочет новый challenge, то предлагают 100,000$:
Didi открывает конкурс машинного обучения с главным призом в $100,000
Didi открывает конкурс машинного обучения с главным призом в $100,000
Первый алгоритм простенькая эвристика на двойках и четверках с учетом позиции. Словарь 40kb gzip, выдает 75%.
Второй — обучение на входящих словах. В комментариях к основной задаче это называют читерством, но все условия задачи соблюдаются.
Первый нужен что бы не было провала до 50% пока второй не обучился. После 630040*6 слов первый алгоритм отключается т.к. начинает тянуть вниз, этот момент явно выражен на графике.
Результат: i.imgur.com/IK3LCZ6.png
У меня было только 6,2кк слов из генератора, я их прогнал 5 раз по кругу. Поэтому мат.ожидание неправильных слов было x5 от нормального и обучение прошло некорректно. Асимптота в районе 91%.
Для тестов написал простой генератор if (rand(1) < 0.5) {return rand(0, 10000)} else {return rand(10000, 40000)} Тут мощность набора некорректных в 3 раза больше мощности корректных. В словах из генератора она начинается с 5 и растет до бесконечности.
На 20кк тестов получилось 95% точность, в обученной базе 604030 слов, из них 99,8% правильные.
У обучения есть очистка базы, удаляющая слова с низким мат. ожиданием, поэтому память не превышает 1,5Gb независимо от кол-ва тестов, хоть миллиард.
Скорость работы получилось разогнать до миллион тестов в минуту на corei5.
Осталось дождаться решения организаторов по кол-ву запусков.
Второй — обучение на входящих словах. В комментариях к основной задаче это называют читерством, но все условия задачи соблюдаются.
Первый нужен что бы не было провала до 50% пока второй не обучился. После 630040*6 слов первый алгоритм отключается т.к. начинает тянуть вниз, этот момент явно выражен на графике.
Результат: i.imgur.com/IK3LCZ6.png
У меня было только 6,2кк слов из генератора, я их прогнал 5 раз по кругу. Поэтому мат.ожидание неправильных слов было x5 от нормального и обучение прошло некорректно. Асимптота в районе 91%.
Для тестов написал простой генератор if (rand(1) < 0.5) {return rand(0, 10000)} else {return rand(10000, 40000)} Тут мощность набора некорректных в 3 раза больше мощности корректных. В словах из генератора она начинается с 5 и растет до бесконечности.
На 20кк тестов получилось 95% точность, в обученной базе 604030 слов, из них 99,8% правильные.
У обучения есть очистка базы, удаляющая слова с низким мат. ожиданием, поэтому память не превышает 1,5Gb независимо от кол-ва тестов, хоть миллиард.
Скорость работы получилось разогнать до миллион тестов в минуту на corei5.
Осталось дождаться решения организаторов по кол-ву запусков.
Sign up to leave a comment.
Отпуск по-программистски, или как я не поучаствовал в конкурсе по программированию на JS. Часть первая