Отпуск по-программистски, или как я не поучаствовал в конкурсе по программированию на JS. Часть первая

    Создание и поддержка в одиночку сложного продукта с большим зоопарком технологий и без финансовых вливаний со стороны — дело хлопотное и утомительное. Поэтому, узнав про конкурс с интересной задачей, мы в Мегаленте я подумал о том, чтобы устроить себе "творческий отпуск" и отвлечься ненадолго от работы над новой версией.


    image


    Задача состояла в том, чтобы написать программу на 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:


    image


    На первый взгляд многообещающе. На рисунке видно, что основным фактором алгоритм определил длину и, например, среди слов длиной больше или равно 19 символам из загруженных 856253 вариантов всего 2079 было правильными. А среди этих вариантов, в свою очередь, влияющим главным фактором стало количество букв "К" в слове. С одной стороны, и информация интересная, а с другой – для нашей задачи бесполезная. Напоследок сделал ещё пару экспериментов с этим алгоритмом, в том числе посмотрел, что будет, если указать тип прогнозируемого атрибута "continuous" вместо "discrete". В этом случае получается интересный результат:
    image
    Как видим, у узла появилась формула:
    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-й буквы слова.


    Вот оно! Я обрадовался, что наконец-то получил волшебные формулы! Но не тут-то было. Проверку на соответствие действительности эти формулы не прошли.


    Предлагаю на этом остановиться и про дальнейшие эксперименты (а их было ещё много) прочитать во второй части.

    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 86

      0

      А можно получить ваши базу неправильных слов, раз уж вы проделали эту работу?

        +1

        Да, только она сейчас неполная. Перед тем, как скармливать данные майнингу, я убрал из неё то, что отсекается описанными в этой статье простыми фильтрами. Сейчас в ней порядка 38М слов.

          +1
          у меня дерево решений глубиной 7 с 250 узлами давало 65%
          самые важные фичи: кол-во согласных, кол-во согласных подряд, позиция расположения ' с начала слова/с конца слова, буква после ', сумма букв, где каждая буква это ее частота появления в словаре
            +2

            На каком объеме данных? Слова были уникальными, или так, как спарсили, так и передавали, включая повторы?

              +2
              без повторов
              был словарь слов с 630404 словами, и не-слов примерно такого же размера
                +2

                Это мало, и это те же грабли, которые я опишу во второй части. Из-за того, что в реальных тестах много повторов, 65% на уникальных словах опустятся до 50%.

                  +2
                  я потом проверял результаты на 150,000 блоках — было очень стабильно
                    +2

                    Значит Вы учли что-то, чего не учёл я. Но вроде как, кроме количества согласных подряд, я скормил тот же набор данных.

              +2
              Первым делом нужно отсечь бессмысленное 's на конце слов и получим сокращение словаря до 490822. Затем можно отсечь все слова, содержащие апостроф — их всего несколько сотен (~350, false-negative 0,07%) против 100 тыс на 1 млн неверных слов (~10%), итого получаем словарь вообще без апострофов. Две простейшие регулярки дают офигенный профит.
                +1

                Во второй части будет описание, как я уменьшил словарь до 390000 без потерь.

                  +1
                  Упс, простите, поторопился :)
                  0
                  Наоборот — отбросить слова не содержащие 's на конце, но такие которые есть с 's на конце. Для себя решил, что мое решение вообще не должно давать false-negative.
                  Кусочек отчета теста одной из последних версий — http://dl2.joxi.net/drive/2016/05/28/0001/1653/99957/57/1518a62432.jpg
                    0

                    Это моей было ключевой стратегией для уменьшения размера словаря – выделить слова, включающие в себя другие слова, и закодировать, сколько букв спереди или сзади можно отбросить для получения правильных слов.

                      0
                      Я пытался использовать стемер, но это не дало удовлетворительного результата. Слишком много слов которые не поддаются такой обработке и их приходилось либо игнорировать, либо добавлять в виде исключений.
                        0

                        Стемер мне тоже не помог. Сделал тупо серией sql-запросов. Сами запросы будут во второй части.

                          0
                          На самом деле результат стемера можно было бы сильно улучшить если сохранять правила стеминга которые не были вообще применены к словарю, и отдельно обрабатывать слова, которые дают в стемере исключительные результаты — скажем единственный уникальный корень из всего словаря или подпадают под единственное правило, но я понял, что у меня просто не хватит времени все это учесть и придумать как сжать.
                          Что ж, ждем вторую часть )
                +1
                кстати, если на Азуре, то дешевле и проще было проверять алгоритмы на Azure ML
                Там легко заменяются сети на деревья, быстро настраиваются, автоматически находятся important features, tuning параметров…
                  0

                  SQL база у меня была локальная. Я хотел попробовать Azure ML, но споткнулся о существенную разницу в скорости выполнения запросов между азуровским и локальным SQL-серверами. В частности, создания таблицы с несуществующими четвёрками согласных, на азуре я так и не смог дождаться. Понимаю, что можно было поработать над оптимальностью запросов, но задача была другой.

                    0
                    да, вполне возможно. Я тоже все features искал на локальном компьютере (точнее в другом кластере), а в ML поднимал готовый вектор
                    Схема
                    image
                      0

                      Я просто раньше с Azure ML не работал и не знаю что в нём есть и чего от него ожидать, поэтому пошел по более-менее понятному мне пути.

                  +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];
                  }};
                  

                    +1

                    Проверил. Не даёт. На 1000 блоках 55.27%

                      +3
                      1. 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)}}
                      


                      test 0-200k 61.98225%
                      crossvalidation 200k-400k 61.9829%
                        0
                        а как использовали видеокарту?
                          0
                          Было ~50 фич, которые переводили слово в некоторый диапазон.
                          1. Длина слова от 3 до 30
                          2. ASCII Код буквы на позиции от 0 до 20 (' преобразовывал в `)
                          3. Количество вхождений буквы a-z`
                          Для каждой фичи для 8M слов подсчитан результат и закэширован.
                          В начале есть дерево из 1 узла. Точность решения 50%
                          Дальше перебираются все возможные варианты как можно поделить этот узел на N узлов при помощи какой-то фичи.
                          Выбирается фича и узел которые имеют больше всего сумму abs(pos-neg) на всех узлах, которые образуются после разделения узла на много узлов.
                          А теперь всё тоже самое, только 8000 раз.
                    0
                    Прошел практически через все эти идеи. Но в итоге откинул решение с тройками.
                    Ну плюс еще пробовал не раз озвученный фильтр Блюма. Последней идей как сделать его сильно меньше была попытка повысить изотропность добавляющихся в него слов путем их разбивки, но не по количству букв, а с помощью split по букве.
                    Сначала отбирал слова содержащие в середине наиболее частую в середине слова букву (e), затем среди оставшихся проделывал тоже самое (i) и так далее.
                    После резал слова по этим символам, так что слов delimiter превращалось в 0d, 1limit, _r (числа перед частями означали их порядок, а _ означал последний блок слова). Список букв разделителей добавляемые в данные однозначно задавал разбиение. В данном случае было например понятно что слово надо бить по e, так как она идет в списке раньше чем i.
                    Следующей идеей была рекурсивная разбивка, где ei напримерм означало что слово необходимо разделить так: 00d, 10l, 11m, 12t, _0r. Полученные строки добавлял в блюм. Разбиение глубже не помогало ((
                    В сочетании с несуществующеми парами, практически полностью повторяющими ваше решение и еще одной штукой которую назвал consonantsSignature удалось выжать ~71%.
                    Так же пытался бить слова на кластеры и хранить данные для каждого кластера отдельно. В чстности ластерами были длины, символы разбиений и более сложные механизмы.
                    Диапазон слов от 5 до 9 символов назвал изотропным провалом — именно тут мне не удалось добиться приемлемого решения. Ну да логично — там сосредоточено огромное количество слов.
                    Но это все.
                    Решение не отправил.
                      0

                      Уменьшение словаря до 390К, карта "соседских" двоек и троек, блум и ещё что-то читайте через неделю.

                        +1
                        Я пробовал разные алгоритмы фонетического сжатия.
                        Лучше всего себя показал Porter + Nysiis
                        Примерная точность 73-75% на миллионе тестовых пар при размере словаря в 130 000 слов.

                        — Наивный Байес по букве + её позиции давал порядка 63% причем размер финального словаря ужатым получался порядка 10kb
                        Лучше всего НБ работал на двух буквах + позиции(порядка %73), но результат не вмещался в 63kb
                        (Естественно тренировка и проверка велась на разных датасетах)

                        — Еще была идея попробовать разобрать работу генератора через (hidden markov model).
                        Т.к. генератор можно, по идее, считать марковским процессом. (Не пробовал).
                        Но я рассуждал так. Если генератор это функция от словаря то ловить, в принципе, там нечего кроме возможных искажений в распределениях.
                        — Еще была идея отсекать гарантировано не слова по энтропии. (Порог отсечения подобрать бинарным поиском).
                        — Дальше были идеи как все это ужать через DAWG, Bloom фильтр или count min sketch(для подсчета статистики по каждому ужатому корню). Но, честно говоря, выдохся. Все равно >80% точности было добится не реально.
                        Решение не отправил.
                          +1
                          Так-же изучал возможность использовать LSH хеши. Понял что ловить там нечего.
                          — В любом случае, даже если я и не поучавствовал я узнал много новых классных вещей.
                          Так-что не могу учитывать это время как потраченное зря.
                          0

                          Забегая вперёд этой части статьи, скажу, что я пришел к выводу, что из-за того, что большая часть неправильных слов — псевдонеправильные(слова, не поддающиеся отсечению по правилам), единственный вариант решения- формальными правилами уменьшить словарь настолько, насколько это возможно, скормить его блуму или аналогу(если есть), а затем перед проверкой на блуме на входе по редким комбинациям отсекать "мусор".

                            0
                            Как сделать 80%:
                            Убираем из слов все окончания 's, потом делаем
                            porter2+bloom+gzip
                            Профит.
                              0
                              У меня лучше получилось сжать lzma, даже с учетом 6кб кода на распаковку, я все равно выигрывал порядка +2кб. Т.е. блум фильтр закодированный посимвольно (по 8 бит на символ) в среднем занимал порядка 80 кило. Гзип жал его где-то до 60-62, а lzma до 55-56. Код на распаковку правда при этом также приходилось жать через штатный gzip, т.е. происходила двойная архивация, но оно все равно того стоит.
                                0
                                Можно еще набрутфорсить такие seed значения хэш функций, чтобы было больше коллизий на том же наборе данных. В полтора-два раза размер фильтров может уменьшить.

                                Я, правда, не успел попробовать блум фильтры. Тут уже кому повезло с чего начать.
                                  0

                                  Согласен. Если бы я сразу с него начал, то не было бы этой статьи :-).

                                    0
                                    На самом деле перебор сидов дает небольшой выигрыш для каждого конкретного варианта, но все равно перебирать пришлось, да. Я перебирал не только сиды но и сами хеш функции, у меня их было 13 штук.
                                      0
                                      Это получается один блум фильтр на все? А по пути perfect hashing алгоритмов не пробовали, т.е. поделить все на бакеты, в каждом поменьше хэш функций и легче брутфорсить?
                                        0
                                        Я пробовал разные варианты. Пробовал разбить все слова на группы по их длине и для каждой группы подобрать отдельные блюм фильтры, очевидно что идея потерпела фиаско, поскольку, как я теперь это четко вижу, длина слова не является каким-либо определяющим фактором для его «содержимого». Т.е. полученные группы не обладали какими-либо характерно различимыми признаками. Про «perfect hashing» никогда не слышал. Пробовал в качестве хеша брать не какие-то абстрактные хешилки, а привязанные к структуре слова, которые преобразовывают по принципам гласн/согласн или пары/тройки самых частых заменяли на одни и те же фиксированные значения при расчете хеша всего слова, тут тоже не добился ничего значительного. В итоге остановился на одном единственном блюме для всего, как основе.
                                  0

                                  А как у Вас получилось сохранить блум в <64k? У меня минимально рабочий с 80% на 390K словаря занимал минимум 120K.

                                    0
                                    У меня через блум прогонялось около 280к слов, при этом размер фильтра был в районе 500 килобит. Но это среднее, в процессе перебора были разные варианты.
                                      0

                                      Так а получилось в результате их ужать в <64?

                                        0
                                        Да, конечно, я ужал его в 55 килобайт. Остальные 10 кило занял код опять же в сжатом виде.
                                          +1
                                          А, забыл совсем уточнить, у меня блюм не по целым словам, а по нграммам. Т.е. я ему скармливал только нграммы длинной 7 букв (причем нграммы не перекрываются, а идут одна за другой плотно, подобрал такую схему перебором), а перед каждой добавлял ее порядковый номер. Т.е. я существенно уменьшил размер входных данных с 280 килослов.
                                        0
                                        Точно уже не помню, но после Портера и 's остаётся порядка 300к слов. Для достижения 80% коэффициент ошибки для блума должен быть 0.6 кажется… Короче я подобрал такой размер блума чтобы оно после архивации влезало в лимит, на тестах было 78-79 процентов.
                                        Товарищ по работе сделал больше 81%, но он дополнительно вырезал длинные слова, в остальном алгоритм тот же
                                      0
                                      Не могу понять, как в node.js можно сохранить массив, после фильтра Блума в файл в виде битовой последовательности. Или только вариант сохранять в виде строки, а потом обратно переделывать в массив? Я в javascript имел дело с клиентской частью только, поэтому этот вопрос не понятен. Если переделывать в строку, то получается слишком большой размер файла…
                                        0
                                         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"});

                                        Но на самом деле так места занимает больше из-за того, что бинарные данные почти не сжимаются.

                                          0
                                          Данные ведь можно сжимать с помощью штатного gzip. Правда бинарные данные в виде строки он жмет плохо, лучше жмет данные в виде unsigned32int, когда каждые 32 бита переведены в десятичное число, а еще лучше если все восьмерки битов закодировать в символы по их коду. И скорее всего есть еще удачные варианты, но я до них не дошел.
                                          0
                                          Без знания того, как генерируются тестовые наборы, невозможно выбрать оптимальный алгоритм.
                                            0
                                            Код ниже даёт 92% точности на 80М слов, без особой оптимизации
                                            var dic=[];
                                            var avg=1;
                                            function test(w){
                                            var h=2166136261;
                                            for (var i=0;i
                                              0
                                              Код зарезался, но я представляю что там )
                                                +1
                                                Закрыто серверной цензурой.
                                                  0
                                                  В превью было нормально, тогда так:
                                                  http://pastebin.com/i6YeDJxn
                                                    0

                                                    У меня он дал 43%.

                                                      0
                                                      На скаченных данных? Я на скаченных проверял.
                                                        0

                                                        Да. В любом случае, если он это действительно делает, то Вы победите в этом конкурсе.

                                                          0
                                                          я уже не знаю кто победит, каждый день что-то новое
                                                          а еще есть англоязычные участники…
                                                            0
                                                            Видимо зависит от числа слов на котором остановятся организаторы.
                                                            На большом числе слов безусловно победят самообучающиеся или гибридные варианты.
                                                              +2
                                                              Да, все алгоритмы на статистике подобного рода дадут результат близкий к 100% при бесконечном числе блоков. Для данного алгоритма у меня получилось около 98.5% на 1.6 миллиарде слов.
                                                              Теперь и я могу начинать кусать локти, потому что искусственно ограничил свой алгоритм, прерывая сбор статистики на 20 миллионах слов )
                                                              Интересно, что будут делать организаторы, если таких решений будет много? Ведь у всех будет близко к 100%
                                                              Кстати, вышеприведенный алгоритм не совершенен, и при достаточно долгом тестировании он сломается, поскольку значения в массиве dic начнут переполняться. Т.е. нельзя сказать, что данный алгоритм достаточно надёжен. Правда раньше начнут переполняться переменные и в тестирующем скрипте ;) А еще раньше наступит конец света.
                                                                +1
                                                                думаю организаторы поступят как обещали — запустят все алгоритмы на одинаковое кол-во блоков (минимум 1000, но хотя б 10,000), и проверят только топ х алгоритмов на большее кол-во блоков
                                                                  0
                                                                  поправка: обещали запустить одинаковое кол-во блоков для всех участников
                                                                  Начнём с 1000 блоков, а потом видно будет.
                                                                  Такое, какое потребуется, чтобы увидеть уверенную разницу между лидерами.
                                                                  Когда решим, сколько нужно для лучших, прогоним на этом количестве всех.
                                                                    0
                                                                    Думаю, при определенных условиях, такой порядок тестирования мог бы дать шанс алгоритмам, не воссоздающим словарь по дубликатам. Всё зависит от порога, на котором будет отчетливо видна разница между лидерами.
                                                                      +1
                                                                      или получится бесконечная рекурсия, которая будет стремится к 100% :)
                                                                        0
                                                                        Это был бы весьма забавный исход. Но, на мой взгляд, отчетливая дифференциация всё же будет, из-за различий в эффективности предварительного фильтра.

                                                                        Всё больше склоняюсь к мысли, что организаторы не ожидали подобного подхода в реализации, иначе, постарались бы его исключить на этапе постановки задачи. А теперь им остается лишь максимально придерживаться первоначальных условий конкурса.
                                                          0
                                                          Он дает 92% на моей выборке из 400 килоблоков.
                                                          0
                                                          Как я понимаю это решение.
                                                          Ясно, что генерированных разных «неслов» гораздо больше, чем реальных слов из словаря.
                                                          Поэтому шанс встретить еще раз уже встреченное ранее реальное слово гораздо выше, чем шанс встретить еще раз придуманное слово.
                                                          Просто берем от каждого слова хэш и записываем по нему в таблицу количество раз, сколько мы его встретили.
                                                          Так же еще ведем подсчет среднего.
                                                          Ответ на тест: если значение по хэшу выше среднего, то говорим «да», иначе – «нет».

                                                          Минус решения: нужна огромная выборка. Сейчас у меня выборка примерно 200к слов, а точность 52.5%, но она растет и гипотетически приближается к 100%.

                                                          Мне кажется, это решение получит приз за оригинальность, но не получит главный приз. Потому что оно фактически не выполняет свою функцию сразу из коробки. На небольших произвольный выборках результат всегда будет плохим.
                                                            +2
                                                            Мне кажется, это решение получит приз за оригинальность

                                                            Не получит, таких решений уже как минимум три.
                                                            0
                                                            Да, тогда уже можно взять и LRU/LFU по размеру словаря и даже в несколько ступеней по префиксам разной длинны, например. Будет быстрее стремиться к 100%. И у кого быстрее, тот и выиграет.
                                                          0
                                                          Если вы отправляли это решение, то поздравляю, меня вы точно обойдете! У меня та же самая логика, но она бsла наложена на основной алгоритм в последний день и я совсем не успел ее довести до ума, а ведь в принципе нет никаких ограничений достичь 100%, при этом не выходя по памяти за 1GB. Я был доволен и тем, что дошел до 90%, которые сегодня, после того как я скачал правильную выборку (а не собранную на коленке в последний час) превратились даже в меньшую цифру.
                                                            +1
                                                            Не отправлял. Код появился после того, как прочитал ваши сообщения в ветке конкурса, чтобы проверить вашу идею. И мне кажется, что организаторы не рассчитывали на решения такого типа.
                                                            Кстати, вышеприведенный алгоритм не совершенен, и при достаточно долгом тестировании он сломается, поскольку значения в массиве dic начнут переполняться. Т.е. нельзя сказать, что данный алгоритм достаточно надёжен.
                                                            Это просто proof of concept, в теме конкурса обсуждают подход, а кода нет (я там писать не могу, кстати).
                                                              0
                                                              Это просто proof of concept, в теме конкурса обсуждают подход, а кода нет (я там писать не могу, кстати).

                                                              Я же просто шутил ) и добавил «А еще раньше наступит конец света.»
                                                          0
                                                          Расскажу тут в комментариях про 82.05%

                                                          * от слов отрезаются самые частые окончания 's, s, ing; слова с апострофом считаются ложными
                                                          * основной алгоритм похож на фильтр Блума:
                                                          для каждого слова считается хеш-функция, по получившемуся индексу в чанке устанавливается единичный бит;
                                                          размер чанка подобран так, что после прохода по словарю остаётся приблизительно 15 нулевых битов;
                                                          позиции этих нулевых битов сохраняются в файл;
                                                          дальше происходит заполнение нового чанка с новой хеш-функцией, всего таких хеш-фунций около 3000;
                                                          при тестировании слова происходит проверка, не попала ли хеш-функция слова на один из этих нулевых битов

                                                          * дополнительно используются эвристики для отсечения ложноположительных срабатываний, подсчёт подряд идущих согласных и т.п. (+4% правильных ответов)
                                                          * стоит уделить внимание изменяемой хеш-функции, небольшие изменение в мутаторе хеш-функции дали прирост +3%
                                                          * для улучшения сжатия файла (~+7% к степени сжатия), сохраняются только расстояния между нулевыми битами, старшие байты, которые имеют схожие значения рядом с нулём, перенесены в отдельную часть файла (сделано с расчётом на gzip, для других архиваторов такая предварительная обработка может навредить)
                                                            0
                                                            Вообще надо было заменять группы окончаний и суффиксов на отдельные символы, а не просто отрезать их. Но идея пришла слишком поздно.
                                                              0
                                                              Слишком большой набор символов получился бы.
                                                                0
                                                                Antelle это помогло улучшить результат.
                                                              +1
                                                              Поразительно! Прям как у меня. Тока у меня попроще. Намного проще ну и результат 79% Не удалось дойти до 80+% Перепробовал кучу всего. Даже начал нейронные сети но, что то меня остановило и я перешел обратно к эвристикам + нечто типа блюма. Эвристики устроены таким образом, что почти все хорошие слова — проходят проверку, плохие отсекаются. Далее есть битовая таблица 65536*8 =524288 бит. И те кто прошел проверки (порядка 280тыс), вычисляется хеш, отрезается по модулю длинной массива и ставится один единственный бит. Получается бит на одно слово. Но не все так идеально — и плохие слова совпадали с хорошими(из-за модуля). Далее я вынес все параметры алгоритма и дал им некий порог и запустил проверку всех возможных комбинаций параметров — составив в итоге список самых лучших подборок параметров. Параметры нашлись, но возникла другая проблема — данные не ужимались ) И код не влазил. Пришлось из кода выкинуть часть и максимум его оптимизировать и уменьшить сами данные, что не очень сильно повлияло на результат.
                                                                0
                                                                Я заметил что можно улучшить результат если для длины блюм фильтра выбирать простые числа. Т.е. при прочих равных при переборе простые числа побеждали. Связано с тем, что мы берем результаты работы хеш функции по модулю длины фильтра.
                                                                  0
                                                                  Да, у меня было простое число 44101
                                                              0
                                                              Тоже расскажу про свои 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%
                                                                0
                                                                83% — это на другой выборке, не на которой проводилось обучение?
                                                                  0
                                                                  83% разумеется было на выборках которые не участвовали в обучении.
                                                                  На учебных выборках было под 84%.
                                                                    0
                                                                    Я к сожалению эту идею откинул сразу, решив что подстраиваюсь под выборку не-слов.
                                                                +1
                                                                Закину и про свое решение в 81%

                                                                В основе алгоритма фильтр блума.
                                                                Но не по целым словам, а по нграммам: слово разбивается на части по фиксированному шаблону и эти части уже заносятся в фильтр.
                                                                Само решение результат перебора, который перебирал seed для хеш функции, сами хеш функции, размеры фильтра, параметры для разбивки на нграммы и списки частых суффиксов и префиксов, и пр. После чего выбиралось лучшее решение, которое после сжатия вместе с кодом влезало бы в 65536 байт.

                                                                Особенности:
                                                                -код решения вынесен в доп. данные и сжат gzip'ом, основной код в файле просто запускает его через eval
                                                                -битовый массив блума переводится в символьное представление (по 8 бит на символ) (такое представление жмется лучше всего)
                                                                -также символьное представление блума дополнительно сжимается по алгоритму LZMA (даже с учетом размера кода на распаковку мы остаемся в выигрыше примерно на 2 кб по сравнению с gzip сжатием)

                                                                Эвристики:
                                                                -удаляем из слов частые суффиксы и префиксы (как перед обучением, так и перед тестированием)
                                                                -все что по длине меньше 3 считаем за true
                                                                -все что по длине больше 17 считаем за false
                                                                -все слова, в которых есть апостроф, кроме тех которые заканчиваются на 's, считаем за false
                                                                -проверка на редкие пары символов (142 пары)

                                                                В последний день перед отправкой я понял, что могу использовать накопленную статистику. Попробовав разные варианты остановился на том, который дает 90% (а по правде 86% как потом оказалось) на большой выборке, побоялся за переполнение по памяти и ограничил сбор статистики на 20 миллионах слов, хотя эта проблема решается на раз-два, но был уже вечер и я затупил.
                                                                  0
                                                                  В общем и целом все как у всех, но не сделал очевидной вещи — фильтрации битов. Также есть неочевидная для меня вещь которую реализовал Antelle: вместо удаления суффиксов-префиксов, надо было заменять их на другие из группы. Но у него и результат 83,5%.

                                                                  У меня было бы еще меньше 81% если бы я не сэкономил несколько килобайт сжав блюм не гзипом, а lzma.
                                                                  +1
                                                                  Кстати, если кто-то хочет новый challenge, то предлагают 100,000$:

                                                                  Didi открывает конкурс машинного обучения с главным призом в $100,000
                                                                    +2
                                                                    А работать-то когда? )
                                                                  +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.

                                                                  Осталось дождаться решения организаторов по кол-ву запусков.

                                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                  Самое читаемое