Создание и поддержка в одиночку сложного продукта с большим зоопарком технологий и без финансовых вливаний со стороны — дело хлопотное и утомительное. Поэтому, узнав про конкурс с интересной задачей, мы в Мегаленте я подумал о том, чтобы устроить себе "творческий отпуск" и отвлечься ненадолго от работы над новой версией.
Задача состояла в том, чтобы написать программу на JS, которая будет определять, есть слово с словаре английских слов или нет. Вроде бы просто, но есть пара ограничений, делающих задачу заведомо невыполнимой:
– Словом считается не просто любое правильное слово английского языка, а именно слово, которое есть в предоставленном словаре из 600K+ слов.
– Словаря в момент исполнения программы нет, скачать его нельзя, а размер программы, включая данные, не должен превышать 64К. Внешние библиотеки подключать также нельзя, но файл данных может быть заархивирован.
Благодаря этим условиям вместо однозначного ответа результатом может быть только определение наибольшей вероятности присутствия слова в словаре.
Сразу скажу, что решение я так и не отправил из-за неудовлетворённостью результатом (решение, которое давало хотя бы 80%, я смог поместить только в 120-130К, а без превышения размера в 64К выжал максимум 70%).
Тем не менее опыт считаю достаточно интересным и достойным статьи. Под катом много SQL,JS,Python, нейронные сети, а также печальная правда о производительности CPU на хостинге.
В качестве призовых плюшек было несколько килобаксов и приглашение на собеседование. Пара-тройка тысяч у.е. в хозяйстве не помешают, но особой погоды не сделают, а в активном поиске работы я не нахожусь (хотя, наверняка, могут существовать такие предложения, от которых я не смог бы отказаться). Тем не менее сама задача меня "зацепила", и я решил выделить недельку на участие.
Так как в комментариях статьи-анонса конкурса да и в самой статье увидел, что при решении уместно использовать нейронные сети, ищу библиотеки для nodejs, на которой будет проверяться результат, или хотя бы для Python в надежде, что можно будет обучить сеть на Python, а потом сделать код прогноза на JS. Нахожу Brain, ConvNetJS,Synaptic,PyBrain,Scikit. Понимаю, что это достаточно сложно, у меня не хватает теоретических знаний и решаю пока попробовать без них.
Тем временем на всякий случай решаю запустить сбор неправильных слов. На нескольких серверах запускаю сбор неправильных слов в базу MongoDB.
import time
import requests
import random
from constants import *
from pymongo import *
client = MongoClient(MONGO_SERVER_IP, socketKeepAlive = True , socketTimeoutMS =30000)
db = client.challenge
words = db.words
wordcount = 0
while True:
page= random.randrange(0,600000000)
url="https://hola.org/challenges/word_classifier/testcase/"+str(page)
response=None
try:
try:
response = requests.get(url)
except:
time.sleep(5)
response = requests.get(url)
if response and response.content:
result=response.json()
if result and len(result):
for word in result:
try:
wordcount+=1
if not wordcount%1000:
print(word count)
if not result[word]
words.replace_one({"_id":word},{"_id":word)
except Exception as err:
time.sleep(1)
words.replace_one({"_id":word},{"_id":word)
except Exception as err:
print (err)Теперь хотелось бы посмотреть поближе на словарь. Чем лучше всего быстро анализировать большие объемы даных? Конечно же, SQL-запросами! Ставлю локально MSSQL, закачиваю word.txt в базу (визардом, без "изысков" – до bcp дойдём позже) и делаю первичный "визуальный" анализ данных:
Для начала смотрим количество слов:
select count(*) from words 661686
На всякий случай проверяем на дубликаты
select count(distinct word) from words 630404
Упс… В файле почему-то есть дубликаты. Переливаем данные без дубликатов:
select distinct word into #words from words
drop table words
select * into words from #words
drop table #words Создаём первичный ключ:
alter table words alter column word varchar(100) not null
alter table words add constraint pk_words primary key clustered (word) Оцениваем количество длинных слов:
select len(word),count(*) from words
where len(word) >20
group by len(word)
order by len(word)| Длина | Количество |
|---|---|
| 20 | 709 |
| 21 | 348 |
| 22 | 151 |
| 23 | 67 |
| 24 | 38 |
| 25 | 18 |
| 26 | 3 |
| 27 | 5 |
| 28 | 3 |
| 29 | 6 |
| 30 | 2 |
| 31 | 2 |
| 32 | 1 |
| 33 | 1 |
| 34 | 2 |
| 45 | 2 |
| 58 | 1 |
| 60 | 1 |
Видим, что слова длиннее 21 символа проще тупо перечислить и отсекать невошедшие в "белый список".
Сохраняем куда-нибудь список длинных слов и удаляем их из таблицы.
select * into longwords from words where len(word)>21
delete words where len(word)>21Начинаю фантазировать, как "в лоб" можно отсеять неправильные слова. Напомню, в приоритете использовать для этого минимум справочной информации.
Первое, что лежит на поверхности – пары и тройки символов, отсутствующие в словаре количество гласных/согласных в словах.
Создаю таблицы.
Гласные:
create table vowels (letter char(1))
insert into vowels
select 'a' union select 'e' union select 'i' union select 'o' union select 'u' union select 'y'Согласные:
create table consonants (letter char(1))
insert into consonants
select 'b' union select 'c' union select 'd' union select 'f' union select 'g' union select 'h' union select 'j' union select 'k' union select 'l' union select 'm' union select 'n' union select 'p' union select 'q' union select 'r' union select 's' union select 't' union select 'v' union select 'w' union select 'x' union select 'z'Вьюха для всех:
create view allchars as
select * from vowels union all
select * from consonants union all
select ''''Нахожу отсутствующие пары:
select v1.letter l1, v2.letter l2 into notexists2
from allchars v1 cross join allchars v2
where not exists (select * from words where word like '%'+v1.letter+v2.letter+'%')Найдено всего 14 пар.
Отсутствующие тройки:
select v1.letter l1, v2.letter l2,v3.letter l3 into notexists3 from allchars v1 cross join allchars v2 cross join allchars v3
where not exists (select * from words where word like '%'+v1.letter+v2.letter+v3.letter+'%')
Найдено 8114 троек.
Аналогичными запросами получаю тройки и четвёрки гласных и согласных. Четвёрок гласных оказывается слишком мало, согласных — слишком много. К этому времени набирается уже достаточно внушительный объем тестовых данных. Для анализа надо перенести с монги на хостинге на локальный SQL.
Делаю простую выгрузку на Python в обычный текст файлами по миллиону слов:
client = MongoClient(MONGO_SERVER_IP)
db = client.challenge
words = db.words
pages=range(0,16)
for page in pages:
f = open("result_"+str(page)+".txt","w")
insert=''
wordsresult=words.find({}).skip(page*1000000).limit(1000000+10)
i=0
for pword in wordsresult:
i+=1
if not i%50000:
print(i)
f.write(pword["_id"]+";")
f.close()Скачиваю файлы и загружаю через bcp. Bcp (Bulk Copy Program) — это консольная утилита от майкрософта для быстрой загрузки/выгрузки больших объемов данных в/из MSSQL. Работает реально быстро, особенно засчёт того, что без включения специального режима логгирования "bulk logged" загрузка данных не отражается в транзакшн логе. Например, 60М слов у меня загружались из текстового файла всего несколько минут. Пример использования:
bcp tmpdata in result1_0.txt -S localhost -d test -U sa -P P@ssw0rd -f bcp.fmtУказанный bcp.fmt — файл с описанием формата исходных данных, в котором указывается тип полей и разделители. Если его не указать, то утилита сама позададаёт вопросы и предложит создать такой файл для дальнейшего использования.
На 66М неправильных слов проверяем, сколько из них отсеются простыми фильтрами:
Длина:
delete learndata where len(word)>21Стало 55M
Пары:
delete learndata
where exists (select * from notexists2 where word like '%'+l1+l2+'%')Стало 46M
Тройки:
delete learndata
where exists (select * from notexists3 where word like '%'+l1+l2+l3+'%')Стало 44M
Вроде неплохо. Добавляю отсутствующие пары и тройки в начале слова, в конце слова и со смещением на 2-3 символа.
Проверяю на тестовом массиве. На каждом миллионе отсеивается примерно так:
Длина: 121576
Отсутствующие пары: 37903
Отсутствующие тройки: 162205
Отсутствующие первые пары: 453
Отсутствующие первые тройки: 13905
Отсутствующие вторые пары: 0
Отсутствующие вторые тройки: 6276
Отсутствующие третьи тройки: 40114
Отсутствующие последние пары: 594
Отсутствующие последние тройки: 6844
Отсутствующие предпоследние пары: 0
Отсутствующие предпоследние тройки: 6844
Отсутствующие предпредпоследние тройки: 4846
Для начала неплохо. Идём дальше.
Теперь надо оформить эти проверки в программу на Javascript и проверить "вживую" на nodejs.
Для этого делаю js-программу, которая будет загружать тестовые данные и вызывать конкурсный скрипт.
var fs =require('fs')
var contest = require('./contest.js');
var zlib= require('zlib');
var data = fs.readFileSync('data.txt.gz');
data = zlib.gunzipSync(data);
var testdata = JSON.parse(fs.readFileSync('test.txt'));
var total=0;
var right=0;
for (testword in testdata)
{
result=contest(testword,testdata[testword]);
total++;
if(testdata[testword]==(result!==null?result:true)right++
}
console.log(right/total)Дальше надо придумать, как сделать так, чтобы данные занимали как можно меньше места. Напомню, количество несуществующих троек около 8000, а кроме них есть ещё тройки сначала, с конца и т.д… Не хотелось бы, чтобы все 64К были съедены только этими справочниками.
Решаю сделать сквозной справочник троек с битовой маской, в которой каждый бит будет отвечать за то, в каком месте слова эта комбинация не встречается. При этом первый бит будет означать, что комбинация не встречается вообще, что сделает ненужным указание всех последующих битов и сэкономит еще немного места.
Также предсказуемое чередование букв и цифр позволяет отказаться от разделителей и опять же сэкономить. Таким образом данные будут выглядеть так:
'aa1eaa64oaa106 и т.д…
Для примера: "'aa1" означает, что комбинация "'aa" не может встречаться вообще, а "eaa64" означает, что "eaa" не может быть предпредпоследними тремя символами. Т.к. кроме этого набора данных предполагаются ещё и другие, решено разделять их между собой точкой с запятой.
Код для загрузки будеть выглядеть так:
for(var i=0;i<data.length;i++)
{
if(data[i]==59){chunk++;i++}
if (chunk==1)
{
word=String.fromCharCode(data[i])+String.fromCharCode(data[++i])+String.fromCharCode(data[++i]);
digit=String.fromCharCode(data[++i]);
while (data[++i]>47&&data[i]<58){
digit+=String.fromCharCode(data[i]);
}
notExistsMatrix3[word]=parseInt(digit);
i--;
}
else if (chunk==2){
word=String.fromCharCode(data[i])+String.fromCharCode(data[++i]);
digit=String.fromCharCode(data[++i]);
while (data[++i]>47&&data[i]<58){
digit+=String.fromCharCode(data[i]);
}
notExistsMatrix2[word]=parseInt(digit);
i--;
}
else if (chunk==3){
word="";
while (data[++i]!=59&&data[i]!=10){
word+=String.fromCharCode(data[i]);
}
longWords.push(word);i--;
}В данном случае предполагается, что в файле данных передадутся справочники с отсутствующими тройками, парами и длинными словами.
Код для проверки будет выглядеть так (пример для пар):
for (letters in notExistsMatrix2) {
if (word.indexOf(letters)>=0) {
if (notExistsMatrix2[letters] & 1){result=false;break;}
if (notExistsMatrix2[letters] & 2 && letters[0] == word[0] && letters[1] == word[1]){result = false;break;}
if (notExistsMatrix2[letters] & 4 && letters[0] == word[1] && letters[1] == word[2]){result = false;break;}
if (notExistsMatrix2[letters] & 8 && letters[0] == word[2] && letters[1] == word[3]){result = false;break;}
if (notExistsMatrix2[letters] & 16 && letters[0] == word[word.length - 2] && letters[1] == word[word.length - 1]){result =false;break;}
if (notExistsMatrix2[letters] & 32 && letters[0] == word[word.length - 3] && letters[1] == word[word.length - 2]){result =false;break;}
if (notExistsMatrix2[letters] & 64 && letters[0] == word[word.length - 4] && letters[1] == word[word.length - 3]){result =false;break;}
}
}Итак, в теории вроде всё красиво, пора запускать.
Запуск. 60%. И то только благодаря тому, что распределение правильных и неправильных слов в тестовых страницах примерно одинаковое. Первое разочарование.
Возвращаюсь к теме с нейронными сетями. Узнаю, что в основном они умеют работать только с двоичными входными и выходными данными. В лучшем случае алгоритмы, использующие функцию sigmoid, которые на вход принимают значения между нулём и единицей.
Хочу попробовать, но для этого надо подготовить таблицу с входными данными. Первой мыслью стало скормить набор входных данных, в котором будут указаны все слова по буквам.
Для уменьшения размера набора решаю отображать каждую букву как набор из пяти бит, соответствующий порядковому номеру буквы в алфавите.
Запрос для создания такого набора данных выглядит так:
--Столбец соответствует порядковому номеру символа в слове, значение - номеру буквы в алфавите
select word,1 as isValid,
case substring(word,1,1) when '''' then 27 when 'a' then 1 when 'b' then 2 when 'c' then 3 when 'd' then 4 when 'e' then 5 when 'f' then 6 when 'g' then 7 when 'h' then 8 when 'i' then 9 when 'j' then 10 when 'k' then 11 when 'l' then 12 when 'm' then 13 when 'n' then 14 when 'o' then 15 when 'p' then 16 when 'q' then 17 when 'r' then 18 when 's' then 19 when 't' then 20 when 'u' then 21 when 'v' then 22 when 'w' then 23 when 'x' then 24 when 'y' then 25 when 'z' then 26 else 0 end l1,
...
case substring(word,21,1) when '''' then 27 when 'a' then 1 when 'b' then 2 when 'c' then 3 when 'd' then 4 when 'e' then 5 when 'f' then 6 when 'g' then 7 when 'h' then 8 when 'i' then 9 when 'j' then 10 when 'k' then 11 when 'l' then 12 when 'm' then 13 when 'n' then 14 when 'o' then 15 when 'p' then 16 when 'q' then 17 when 'r' then 18 when 's' then 19 when 't' then 20 when 'u' then 21 when 'v' then 22 when 'w' then 23 when 'x' then 24 when 'y' then 25 when 'z' then 26 else 0 end l21
into formining
from words
union ALL
select word,0 as isValid,
case substring(word,1,1) when '''' then 27 when 'a' then 1 when 'b' then 2 when 'c' then 3 when 'd' then 4 when 'e' then 5 when 'f' then 6 when 'g' then 7 when 'h' then 8 when 'i' then 9 when 'j' then 10 when 'k' then 11 when 'l' then 12 when 'm' then 13 when 'n' then 14 when 'o' then 15 when 'p' then 16 when 'q' then 17 when 'r' then 18 when 's' then 19 when 't' then 20 when 'u' then 21 when 'v' then 22 when 'w' then 23 when 'x' then 24 when 'y' then 25 when 'z' then 26 end l1,
....
case substring(word,21,1) when '''' then 27 when 'a' then 1 when 'b' then 2 when 'c' then 3 when 'd' then 4 when 'e' then 5 when 'f' then 6 when 'g' then 7 when 'h' then 8 when 'i' then 9 when 'j' then 10 when 'k' then 11 when 'l' then 12 when 'm' then 13 when 'n' then 14 when 'o' then 15 when 'p' then 16 when 'q' then 17 when 'r' then 18 when 's' then 19 when 't' then 20 when 'u' then 21 when 'v' then 22 when 'w' then 23 when 'x' then 24 when 'y' then 25 when 'z' then 26 end l21
from wrongwordsПеревод в биты:
select
l1_1=IIF(l1&1=1,1,0),
l1_2=IIF(l1&2=2,1,0),
l1_3=IIF(l1&4=4,1,0),
l1_4=IIF(l1&8=8,1,0),
l1_5=IIF(l1&16=16,1,0),
...
l21_1=l21&1,
l21_2=IIF(l21&2=2,1,0),
l21_3=IIF(l21&4=4,1,0),
l21_4=IIF(l21&8=8,1,0),
l21_5=IIF(l21&16=16,1,0),
into formining1
from formining
where length>2Пытаюсь скормить этот набор данных нейронной сети.
Пробую brainjs, conventjs, synaptic, а также несколько библиотек на Python – результат не радует. На тестовых моделях с несколькими тысячами записями входных данных у них всё хорошо, но когда я пытаюсь скормить свой реальный набор хотя бы для слов из пяти символов – всё становится плохо. Обучение длится долго, точность никакая. Может, дело в количестве скрытых слоёв, но я пробовал и 10, и 100, и даже 1000. Скорее всего, я их просто "готовить не умею", но пока единственный вывод, к которому я пришел – итераций обучения нужно много (хотя бы десятки тысяч), а на большом количестве данных конкурс закончится раньше, чем сеть обучится.
Появляется идея задействовать хостинг. Но, как оказалось, правда о реальной производительности CPU на хостингах такова, что и тут меня ждал облом. Наивно поднимаю десяток виртуалок на Azure, чтобы запустить на них параллельное обучение, но вижу, что обучение на сервере Azure серии D2 V2 работает (на глаз) раз в двадцать медленнее, чем на моём домашнем i7-4770. В обоих случаях было задействовано одно ядро и не использовался GPU. Думаю, что что-то не так с Azure, вспоминаю, что у меня есть сервер на flops.ru, пробую там – результат тот же. Печальный вывод: почему-то процессор на любом выделенном сервере с i7 будет в разы (в моём конкретном случае на порядок) быстрее, чем на виртуалке. Понимаю, что обеспечить сотню тысяч итераций обучения на 20М записях я не смогу, отказываюсь от нейронной сети.
Вспоминаю, что кроме нейронных сетей бывают ещё и другие механизмы майнинга. Например, деревья принятия решений и алгоритмы поиска взаимосвязей. Решаю их попробовать и для этого добавить в набор данных длину слова, количество гласных, согласных, а также количество одинаковых букв в слове. Для этого в вышеуказанный длинный sql по созданию тестового набора данных добавляю строки:
--Длина
length=len(word),
--Согласные
len(replace(replace(replace(replace(replace(word,'a',''),'e',''),'i',''),'o',''),'u','')) consonants,
--Гласные
len(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(word,'b',''),'c',''),'d',''),'f',''),'g',''),'h',''),'j',''),'k',''),'l',''),'m',''),'n',''),'p',''),'q',''),'r',''),'s',''),'t',''),'v',''),'w',''),'x',''),'y',''),'z','')) vowels,
--Сколько раз буква встречается в слове
len(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(word,'''',''),'y',''),'b',''),'c',''),'d',''),'e',''),'f',''),'g',''),'h',''),'i',''),'j',''),'k',''),'l',''),'m',''),'n',''),'o',''),'p',''),'q',''),'r',''),'s',''),'t',''),'u',''),'v',''),'w',''),'x',''),'z','')) a,
...
len(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(word,'''',''),'a',''),'b',''),'c',''),'d',''),'e',''),'f',''),'g',''),'h',''),'i',''),'j',''),'k',''),'l',''),'m',''),'n',''),'o',''),'p',''),'q',''),'r',''),'s',''),'t',''),'u',''),'v',''),'w',''),'x',''),'y','')) z Скармливаю алгоритму построения дерева принятия решений от майкрософт.
Вот так выглядит дерево принятия решений MS DataMining:
На первый взгляд многообещающе. На рисунке видно, что основным фактором алгоритм определил длину и, например, среди слов длиной больше или равно 19 символам из загруженных 856253 вариантов всего 2079 было правильными. А среди этих вариантов, в свою очередь, влияющим главным фактором стало количество букв "К" в слове. С одной стороны, и информация интересная, а с другой – для нашей задачи бесполезная. Напоследок сделал ещё пару экспериментов с этим алгоритмом, в том числе посмотрел, что будет, если указать тип прогнозируемого атрибута "continuous" вместо "discrete". В этом случае получается интересный результат:
Как видим, у узла появилась формула:
l17 < 21 or >= 24 Existing Cases: 3290857 Missing Cases: 0 Is Valid = 0,007-0,005*(K-0,144)-0,005*(W-0,106)+0,002*(O-1,671)+0,0003*(l21-15,271)-0,004*(B-0,346)
То есть в данном случае это фактически утверждение, что для слов у которых 17-я буква не является 21, 22 и 23-й буквой алфавита, верятность правильности можно получить, заменив в формуле буквы их количеством в слове, а вместо l21 поставить алфавитный номер 21-й буквы слова.
Вот оно! Я обрадовался, что наконец-то получил волшебные формулы! Но не тут-то было. Проверку на соответствие действительности эти формулы не прошли.
Предлагаю на этом остановиться и про дальнейшие эксперименты (а их было ещё много) прочитать во второй части.
Комментарии (86)
Tiulkin
28.05.2016 07:48+1Да, только она сейчас неполная. Перед тем, как скармливать данные майнингу, я убрал из неё то, что отсекается описанными в этой статье простыми фильтрами. Сейчас в ней порядка 38М слов.
Don_Eric
28.05.2016 08:14+1у меня дерево решений глубиной 7 с 250 узлами давало 65%
самые важные фичи: кол-во согласных, кол-во согласных подряд, позиция расположения ' с начала слова/с конца слова, буква после ', сумма букв, где каждая буква это ее частота появления в словареTiulkin
28.05.2016 08:18+2На каком объеме данных? Слова были уникальными, или так, как спарсили, так и передавали, включая повторы?
Gromo
28.05.2016 09:42+2Первым делом нужно отсечь бессмысленное 's на конце слов и получим сокращение словаря до 490822. Затем можно отсечь все слова, содержащие апостроф — их всего несколько сотен (~350, false-negative 0,07%) против 100 тыс на 1 млн неверных слов (~10%), итого получаем словарь вообще без апострофов. Две простейшие регулярки дают офигенный профит.
Suntechnic
28.05.2016 12:22Наоборот — отбросить слова не содержащие 's на конце, но такие которые есть с 's на конце. Для себя решил, что мое решение вообще не должно давать false-negative.
Кусочек отчета теста одной из последних версий — http://dl2.joxi.net/drive/2016/05/28/0001/1653/99957/57/1518a62432.jpgTiulkin
28.05.2016 12:31Это моей было ключевой стратегией для уменьшения размера словаря – выделить слова, включающие в себя другие слова, и закодировать, сколько букв спереди или сзади можно отбросить для получения правильных слов.
Suntechnic
28.05.2016 12:33Я пытался использовать стемер, но это не дало удовлетворительного результата. Слишком много слов которые не поддаются такой обработке и их приходилось либо игнорировать, либо добавлять в виде исключений.
Tiulkin
28.05.2016 12:35Стемер мне тоже не помог. Сделал тупо серией sql-запросов. Сами запросы будут во второй части.
Suntechnic
28.05.2016 12:38На самом деле результат стемера можно было бы сильно улучшить если сохранять правила стеминга которые не были вообще применены к словарю, и отдельно обрабатывать слова, которые дают в стемере исключительные результаты — скажем единственный уникальный корень из всего словаря или подпадают под единственное правило, но я понял, что у меня просто не хватит времени все это учесть и придумать как сжать.
Что ж, ждем вторую часть )
Don_Eric
28.05.2016 08:19+1кстати, если на Азуре, то дешевле и проще было проверять алгоритмы на Azure ML
Там легко заменяются сети на деревья, быстро настраиваются, автоматически находятся important features, tuning параметров…Tiulkin
28.05.2016 08:29SQL база у меня была локальная. Я хотел попробовать Azure ML, но споткнулся о существенную разницу в скорости выполнения запросов между азуровским и локальным SQL-серверами. В частности, создания таблицы с несуществующими четвёрками согласных, на азуре я так и не смог дождаться. Понимаю, что можно было поработать над оптимальностью запросов, но задача была другой.
Don_Eric
28.05.2016 08:40да, вполне возможно. Я тоже все features искал на локальном компьютере (точнее в другом кластере), а в ML поднимал готовый вектор
Схема
Tiulkin
28.05.2016 08:46Я просто раньше с Azure ML не работал и не знаю что в нём есть и чего от него ожидать, поэтому пошел по более-менее понятному мне пути.
vird
28.05.2016 10:49+4Примерно такой код дает примерно 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]; }};Tiulkin
28.05.2016 10:56+1Проверил. Не даёт. На 1000 блоках 55.27%
vird
28.05.2016 11:24+31. 1000 блоков вообще ничто. Я начинаю чему-либо верить от 50k блоков
2. Это набросок, который потом ушёл под тюнинг на видеокарту, и там уже были совсем другие коэфициенты.
Перепосчитал
Решениеdata.gz
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)}}Don_Eric
29.05.2016 17:51а как использовали видеокарту?
vird
29.05.2016 19:45Было ~50 фич, которые переводили слово в некоторый диапазон.
1. Длина слова от 3 до 30
2. ASCII Код буквы на позиции от 0 до 20 (' преобразовывал в `)
3. Количество вхождений буквы a-z`
Для каждой фичи для 8M слов подсчитан результат и закэширован.
В начале есть дерево из 1 узла. Точность решения 50%
Дальше перебираются все возможные варианты как можно поделить этот узел на N узлов при помощи какой-то фичи.
Выбирается фича и узел которые имеют больше всего сумму abs(pos-neg) на всех узлах, которые образуются после разделения узла на много узлов.
А теперь всё тоже самое, только 8000 раз.
Suntechnic
28.05.2016 12:17Прошел практически через все эти идеи. Но в итоге откинул решение с тройками.
Ну плюс еще пробовал не раз озвученный фильтр Блюма. Последней идей как сделать его сильно меньше была попытка повысить изотропность добавляющихся в него слов путем их разбивки, но не по количству букв, а с помощью split по букве.
Сначала отбирал слова содержащие в середине наиболее частую в середине слова букву (e), затем среди оставшихся проделывал тоже самое (i) и так далее.
После резал слова по этим символам, так что слов delimiter превращалось в 0d, 1limit, _r (числа перед частями означали их порядок, а _ означал последний блок слова). Список букв разделителей добавляемые в данные однозначно задавал разбиение. В данном случае было например понятно что слово надо бить по e, так как она идет в списке раньше чем i.
Следующей идеей была рекурсивная разбивка, где ei напримерм означало что слово необходимо разделить так: 00d, 10l, 11m, 12t, _0r. Полученные строки добавлял в блюм. Разбиение глубже не помогало ((
В сочетании с несуществующеми парами, практически полностью повторяющими ваше решение и еще одной штукой которую назвал consonantsSignature удалось выжать ~71%.
Так же пытался бить слова на кластеры и хранить данные для каждого кластера отдельно. В чстности ластерами были длины, символы разбиений и более сложные механизмы.
Диапазон слов от 5 до 9 символов назвал изотропным провалом — именно тут мне не удалось добиться приемлемого решения. Ну да логично — там сосредоточено огромное количество слов.
Но это все.
Решение не отправил.
Tiulkin
28.05.2016 12:24Уменьшение словаря до 390К, карта "соседских" двоек и троек, блум и ещё что-то читайте через неделю.
mik222
28.05.2016 13:02+1Я пробовал разные алгоритмы фонетического сжатия.
Лучше всего себя показал Porter + Nysiis
Примерная точность 73-75% на миллионе тестовых пар при размере словаря в 130 000 слов.
— Наивный Байес по букве + её позиции давал порядка 63% причем размер финального словаря ужатым получался порядка 10kb
Лучше всего НБ работал на двух буквах + позиции(порядка %73), но результат не вмещался в 63kb
(Естественно тренировка и проверка велась на разных датасетах)
— Еще была идея попробовать разобрать работу генератора через (hidden markov model).
Т.к. генератор можно, по идее, считать марковским процессом. (Не пробовал).
Но я рассуждал так. Если генератор это функция от словаря то ловить, в принципе, там нечего кроме возможных искажений в распределениях.
— Еще была идея отсекать гарантировано не слова по энтропии. (Порог отсечения подобрать бинарным поиском).
— Дальше были идеи как все это ужать через DAWG, Bloom фильтр или count min sketch(для подсчета статистики по каждому ужатому корню). Но, честно говоря, выдохся. Все равно >80% точности было добится не реально.
Решение не отправил.mik222
28.05.2016 13:50+1Так-же изучал возможность использовать LSH хеши. Понял что ловить там нечего.
— В любом случае, даже если я и не поучавствовал я узнал много новых классных вещей.
Так-что не могу учитывать это время как потраченное зря.
Tiulkin
28.05.2016 13:03Забегая вперёд этой части статьи, скажу, что я пришел к выводу, что из-за того, что большая часть неправильных слов — псевдонеправильные(слова, не поддающиеся отсечению по правилам), единственный вариант решения- формальными правилами уменьшить словарь настолько, насколько это возможно, скормить его блуму или аналогу(если есть), а затем перед проверкой на блуме на входе по редким комбинациям отсекать "мусор".
xytop
28.05.2016 17:22Как сделать 80%:
Убираем из слов все окончания 's, потом делаем
porter2+bloom+gzip
Профит.
Zavtramen
28.05.2016 17:29У меня лучше получилось сжать lzma, даже с учетом 6кб кода на распаковку, я все равно выигрывал порядка +2кб. Т.е. блум фильтр закодированный посимвольно (по 8 бит на символ) в среднем занимал порядка 80 кило. Гзип жал его где-то до 60-62, а lzma до 55-56. Код на распаковку правда при этом также приходилось жать через штатный gzip, т.е. происходила двойная архивация, но оно все равно того стоит.
zzzcpan
28.05.2016 18:56Можно еще набрутфорсить такие seed значения хэш функций, чтобы было больше коллизий на том же наборе данных. В полтора-два раза размер фильтров может уменьшить.
Я, правда, не успел попробовать блум фильтры. Тут уже кому повезло с чего начать.Zavtramen
28.05.2016 19:20На самом деле перебор сидов дает небольшой выигрыш для каждого конкретного варианта, но все равно перебирать пришлось, да. Я перебирал не только сиды но и сами хеш функции, у меня их было 13 штук.
zzzcpan
28.05.2016 19:32Это получается один блум фильтр на все? А по пути perfect hashing алгоритмов не пробовали, т.е. поделить все на бакеты, в каждом поменьше хэш функций и легче брутфорсить?
Zavtramen
28.05.2016 19:38Я пробовал разные варианты. Пробовал разбить все слова на группы по их длине и для каждой группы подобрать отдельные блюм фильтры, очевидно что идея потерпела фиаско, поскольку, как я теперь это четко вижу, длина слова не является каким-либо определяющим фактором для его «содержимого». Т.е. полученные группы не обладали какими-либо характерно различимыми признаками. Про «perfect hashing» никогда не слышал. Пробовал в качестве хеша брать не какие-то абстрактные хешилки, а привязанные к структуре слова, которые преобразовывают по принципам гласн/согласн или пары/тройки самых частых заменяли на одни и те же фиксированные значения при расчете хеша всего слова, тут тоже не добился ничего значительного. В итоге остановился на одном единственном блюме для всего, как основе.
Tiulkin
28.05.2016 17:46А как у Вас получилось сохранить блум в <64k? У меня минимально рабочий с 80% на 390K словаря занимал минимум 120K.
Zavtramen
28.05.2016 17:53У меня через блум прогонялось около 280к слов, при этом размер фильтра был в районе 500 килобит. Но это среднее, в процессе перебора были разные варианты.
Tiulkin
28.05.2016 17:56Так а получилось в результате их ужать в <64?
Zavtramen
28.05.2016 19:21Да, конечно, я ужал его в 55 килобайт. Остальные 10 кило занял код опять же в сжатом виде.
Zavtramen
28.05.2016 19:23+1А, забыл совсем уточнить, у меня блюм не по целым словам, а по нграммам. Т.е. я ему скармливал только нграммы длинной 7 букв (причем нграммы не перекрываются, а идут одна за другой плотно, подобрал такую схему перебором), а перед каждой добавлял ее порядковый номер. Т.е. я существенно уменьшил размер входных данных с 280 килослов.
xytop
28.05.2016 18:05Точно уже не помню, но после Портера и 's остаётся порядка 300к слов. Для достижения 80% коэффициент ошибки для блума должен быть 0.6 кажется… Короче я подобрал такой размер блума чтобы оно после архивации влезало в лимит, на тестах было 78-79 процентов.
Товарищ по работе сделал больше 81%, но он дополнительно вырезал длинные слова, в остальном алгоритм тот же
besimpl
28.05.2016 17:27Не могу понять, как в node.js можно сохранить массив, после фильтра Блума в файл в виде битовой последовательности. Или только вариант сохранять в виде строки, а потом обратно переделывать в массив? Я в javascript имел дело с клиентской частью только, поэтому этот вопрос не понятен. Если переделывать в строку, то получается слишком большой размер файла…
Tiulkin
28.05.2016 17:31var 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"});
Но на самом деле так места занимает больше из-за того, что бинарные данные почти не сжимаются.
Zavtramen
28.05.2016 17:31Данные ведь можно сжимать с помощью штатного gzip. Правда бинарные данные в виде строки он жмет плохо, лучше жмет данные в виде unsigned32int, когда каждые 32 бита переведены в десятичное число, а еще лучше если все восьмерки битов закодировать в символы по их коду. И скорее всего есть еще удачные варианты, но я до них не дошел.
amaksr
28.05.2016 19:24Без знания того, как генерируются тестовые наборы, невозможно выбрать оптимальный алгоритм.
mynick
29.05.2016 00:56Код ниже даёт 92% точности на 80М слов, без особой оптимизации
var dic=[];
var avg=1;
function test(w){
var h=2166136261;
for (var i=0;iZavtramen
29.05.2016 01:06Код зарезался, но я представляю что там )
mynick
29.05.2016 07:27В превью было нормально, тогда так:
http://pastebin.com/i6YeDJxnTiulkin
29.05.2016 07:38У меня он дал 43%.
mynick
29.05.2016 07:43На скаченных данных? Я на скаченных проверял.
Tiulkin
29.05.2016 07:46Да. В любом случае, если он это действительно делает, то Вы победите в этом конкурсе.
Don_Eric
29.05.2016 08:29я уже не знаю кто победит, каждый день что-то новое
а еще есть англоязычные участники…alex3d
29.05.2016 09:16Видимо зависит от числа слов на котором остановятся организаторы.
На большом числе слов безусловно победят самообучающиеся или гибридные варианты.Zavtramen
29.05.2016 12:54+2Да, все алгоритмы на статистике подобного рода дадут результат близкий к 100% при бесконечном числе блоков. Для данного алгоритма у меня получилось около 98.5% на 1.6 миллиарде слов.
Теперь и я могу начинать кусать локти, потому что искусственно ограничил свой алгоритм, прерывая сбор статистики на 20 миллионах слов )
Интересно, что будут делать организаторы, если таких решений будет много? Ведь у всех будет близко к 100%
Кстати, вышеприведенный алгоритм не совершенен, и при достаточно долгом тестировании он сломается, поскольку значения в массиве dic начнут переполняться. Т.е. нельзя сказать, что данный алгоритм достаточно надёжен. Правда раньше начнут переполняться переменные и в тестирующем скрипте ;) А еще раньше наступит конец света.
Don_Eric
29.05.2016 14:09+1думаю организаторы поступят как обещали — запустят все алгоритмы на одинаковое кол-во блоков (минимум 1000, но хотя б 10,000), и проверят только топ х алгоритмов на большее кол-во блоков
Don_Eric
29.05.2016 15:19поправка: обещали запустить одинаковое кол-во блоков для всех участников
Начнём с 1000 блоков, а потом видно будет.
Такое, какое потребуется, чтобы увидеть уверенную разницу между лидерами.
Когда решим, сколько нужно для лучших, прогоним на этом количестве всех.
andy2002ua
29.05.2016 15:47Думаю, при определенных условиях, такой порядок тестирования мог бы дать шанс алгоритмам, не воссоздающим словарь по дубликатам. Всё зависит от порога, на котором будет отчетливо видна разница между лидерами.
Don_Eric
29.05.2016 16:48+1или получится бесконечная рекурсия, которая будет стремится к 100% :)
andy2002ua
29.05.2016 17:09Это был бы весьма забавный исход. Но, на мой взгляд, отчетливая дифференциация всё же будет, из-за различий в эффективности предварительного фильтра.
Всё больше склоняюсь к мысли, что организаторы не ожидали подобного подхода в реализации, иначе, постарались бы его исключить на этапе постановки задачи. А теперь им остается лишь максимально придерживаться первоначальных условий конкурса.
tirinox
29.05.2016 11:37Как я понимаю это решение.
Ясно, что генерированных разных «неслов» гораздо больше, чем реальных слов из словаря.
Поэтому шанс встретить еще раз уже встреченное ранее реальное слово гораздо выше, чем шанс встретить еще раз придуманное слово.
Просто берем от каждого слова хэш и записываем по нему в таблицу количество раз, сколько мы его встретили.
Так же еще ведем подсчет среднего.
Ответ на тест: если значение по хэшу выше среднего, то говорим «да», иначе – «нет».
Минус решения: нужна огромная выборка. Сейчас у меня выборка примерно 200к слов, а точность 52.5%, но она растет и гипотетически приближается к 100%.
Мне кажется, это решение получит приз за оригинальность, но не получит главный приз. Потому что оно фактически не выполняет свою функцию сразу из коробки. На небольших произвольный выборках результат всегда будет плохим.Zavtramen
29.05.2016 12:55+2Мне кажется, это решение получит приз за оригинальность
Не получит, таких решений уже как минимум три.
zzzcpan
29.05.2016 21:18Да, тогда уже можно взять и LRU/LFU по размеру словаря и даже в несколько ступеней по префиксам разной длинны, например. Будет быстрее стремиться к 100%. И у кого быстрее, тот и выиграет.
Zavtramen
29.05.2016 10:36Если вы отправляли это решение, то поздравляю, меня вы точно обойдете! У меня та же самая логика, но она бsла наложена на основной алгоритм в последний день и я совсем не успел ее довести до ума, а ведь в принципе нет никаких ограничений достичь 100%, при этом не выходя по памяти за 1GB. Я был доволен и тем, что дошел до 90%, которые сегодня, после того как я скачал правильную выборку (а не собранную на коленке в последний час) превратились даже в меньшую цифру.
mynick
29.05.2016 13:33+1Не отправлял. Код появился после того, как прочитал ваши сообщения в ветке конкурса, чтобы проверить вашу идею. И мне кажется, что организаторы не рассчитывали на решения такого типа.
Кстати, вышеприведенный алгоритм не совершенен, и при достаточно долгом тестировании он сломается, поскольку значения в массиве dic начнут переполняться. Т.е. нельзя сказать, что данный алгоритм достаточно надёжен.
Это просто proof of concept, в теме конкурса обсуждают подход, а кода нет (я там писать не могу, кстати).Zavtramen
29.05.2016 13:35Это просто proof of concept, в теме конкурса обсуждают подход, а кода нет (я там писать не могу, кстати).
Я же просто шутил ) и добавил «А еще раньше наступит конец света.»
Imp5
29.05.2016 09:40Расскажу тут в комментариях про 82.05%
* от слов отрезаются самые частые окончания 's, s, ing; слова с апострофом считаются ложными
* основной алгоритм похож на фильтр Блума:
для каждого слова считается хеш-функция, по получившемуся индексу в чанке устанавливается единичный бит;
размер чанка подобран так, что после прохода по словарю остаётся приблизительно 15 нулевых битов;
позиции этих нулевых битов сохраняются в файл;
дальше происходит заполнение нового чанка с новой хеш-функцией, всего таких хеш-фунций около 3000;
при тестировании слова происходит проверка, не попала ли хеш-функция слова на один из этих нулевых битов
* дополнительно используются эвристики для отсечения ложноположительных срабатываний, подсчёт подряд идущих согласных и т.п. (+4% правильных ответов)
* стоит уделить внимание изменяемой хеш-функции, небольшие изменение в мутаторе хеш-функции дали прирост +3%
* для улучшения сжатия файла (~+7% к степени сжатия), сохраняются только расстояния между нулевыми битами, старшие байты, которые имеют схожие значения рядом с нулём, перенесены в отдельную часть файла (сделано с расчётом на gzip, для других архиваторов такая предварительная обработка может навредить)
FlashManiac
29.05.2016 18:01+1Поразительно! Прям как у меня. Тока у меня попроще. Намного проще ну и результат 79% Не удалось дойти до 80+% Перепробовал кучу всего. Даже начал нейронные сети но, что то меня остановило и я перешел обратно к эвристикам + нечто типа блюма. Эвристики устроены таким образом, что почти все хорошие слова — проходят проверку, плохие отсекаются. Далее есть битовая таблица 65536*8 =524288 бит. И те кто прошел проверки (порядка 280тыс), вычисляется хеш, отрезается по модулю длинной массива и ставится один единственный бит. Получается бит на одно слово. Но не все так идеально — и плохие слова совпадали с хорошими(из-за модуля). Далее я вынес все параметры алгоритма и дал им некий порог и запустил проверку всех возможных комбинаций параметров — составив в итоге список самых лучших подборок параметров. Параметры нашлись, но возникла другая проблема — данные не ужимались ) И код не влазил. Пришлось из кода выкинуть часть и максимум его оптимизировать и уменьшить сами данные, что не очень сильно повлияло на результат.
Zavtramen
29.05.2016 18:45Я заметил что можно улучшить результат если для длины блюм фильтра выбирать простые числа. Т.е. при прочих равных при переборе простые числа побеждали. Связано с тем, что мы берем результаты работы хеш функции по модулю длины фильтра.
alex3d
29.05.2016 10:43Тоже расскажу про свои 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%
Zavtramen
29.05.2016 13:05+1Закину и про свое решение в 81%
В основе алгоритма фильтр блума.
Но не по целым словам, а по нграммам: слово разбивается на части по фиксированному шаблону и эти части уже заносятся в фильтр.
Само решение результат перебора, который перебирал seed для хеш функции, сами хеш функции, размеры фильтра, параметры для разбивки на нграммы и списки частых суффиксов и префиксов, и пр. После чего выбиралось лучшее решение, которое после сжатия вместе с кодом влезало бы в 65536 байт.
Особенности:
-код решения вынесен в доп. данные и сжат gzip'ом, основной код в файле просто запускает его через eval
-битовый массив блума переводится в символьное представление (по 8 бит на символ) (такое представление жмется лучше всего)
-также символьное представление блума дополнительно сжимается по алгоритму LZMA (даже с учетом размера кода на распаковку мы остаемся в выигрыше примерно на 2 кб по сравнению с gzip сжатием)
Эвристики:
-удаляем из слов частые суффиксы и префиксы (как перед обучением, так и перед тестированием)
-все что по длине меньше 3 считаем за true
-все что по длине больше 17 считаем за false
-все слова, в которых есть апостроф, кроме тех которые заканчиваются на 's, считаем за false
-проверка на редкие пары символов (142 пары)
В последний день перед отправкой я понял, что могу использовать накопленную статистику. Попробовав разные варианты остановился на том, который дает 90% (а по правде 86% как потом оказалось) на большой выборке, побоялся за переполнение по памяти и ограничил сбор статистики на 20 миллионах слов, хотя эта проблема решается на раз-два, но был уже вечер и я затупил.Zavtramen
29.05.2016 13:08В общем и целом все как у всех, но не сделал очевидной вещи — фильтрации битов. Также есть неочевидная для меня вещь которую реализовал Antelle: вместо удаления суффиксов-префиксов, надо было заменять их на другие из группы. Но у него и результат 83,5%.
У меня было бы еще меньше 81% если бы я не сэкономил несколько килобайт сжав блюм не гзипом, а lzma.
Don_Eric
29.05.2016 18:25+1Кстати, если кто-то хочет новый challenge, то предлагают 100,000$:
Didi открывает конкурс машинного обучения с главным призом в $100,000
rodgar
31.05.2016 12:34+1Первый алгоритм простенькая эвристика на двойках и четверках с учетом позиции. Словарь 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.
Осталось дождаться решения организаторов по кол-ву запусков.
mbait
А можно получить ваши базу неправильных слов, раз уж вы проделали эту работу?