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

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

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

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

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