Відпустку программистски, або як я не взяв участь у конкурсі з програмування на PHP. Частина перша

Створення і підтримка в поодинці складного продукту з великим зоопарком технологій і без фінансових вливань з боку — справа клопітка і виснажлива. Тому, дізнавшись про конкурс з цікавим завданням, ми Мегаленте я подумав про те, щоб влаштувати собі "творча відпустка" і ненадовго відволіктися від роботи над новою версією.
image
Завдання полягало в тому, щоб написати програму на JS, яка буде визначати, чи є слово із словника англійських слів чи ні. Начебто просто, але є пара обмежень, які роблять завдання свідомо нездійсненною:
– Словом вважається не просто будь-яке правильне слово англійської мови, а саме слово, яке є в наданому словнику з 600K+ слів.
– Словника в момент виконання програми немає, завантажити його можна, а розмір програми, включаючи дані, не повинен перевищувати 64К. Зовнішні бібліотеки підключати також не можна, але файл даних може бути заархіваваний.
Завдяки цим умовам замість однозначної відповіді результатом може бути тільки визначення найбільшої ймовірності присутності слова у словнику.
Відразу скажу, що рішення я так і не відправив через незадоволеністю результатом (рішення, яке давало хоча б 80%, я зміг помістити тільки в 120-130К, а без перевищення розміру до 64К вичавив максимум 70%).
Тим не менше досвід вважаю досить цікавим і гідним статті. Під катом багато SQL,PHP,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 as Exception err:
time.sleep(1)
words.replace_one({"_id":word},{"_id":word)

except as Exception err:
print (err)

Тепер хотілося б подивитися ближче на словник. Чим краще всього швидко аналізувати великі обсяги даних? Звичайно ж, SQL-запитами! Ставлю локально MSSQL, закачую word.txt у базу (візардом, без "вишукувань" – до bcp дійдемо пізніше) і роблю первинний "візуальний" аналіз даних:
Для початку дивимося кількість слів:
select count(*) from words 

661686
На всякий випадок перевіряємо на дублікати
select count(distinct word) words from 

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 words from where len(word)>21
delete words where len(word)>21

Починаю фантазувати, як "в лоб" можна відсіяти неправильні слова. Нагадаю, в пріоритеті використовувати для цього мінімум довідкової інформації.
Перше, що лежить на поверхні – пари і трійки символів, яких немає у словнику кількість голосних/приголосних у словах.
Створюю таблиці.
Голосні:
create table vowels (letter char(1))
insert into vowels
select 'a' select 'e' select 'i' select 'o' select 'u' select 'y'

Приголосні:
create table consonants (letter char(1))
insert into consonants
select 'b' select 'c' select 'd' select 'f' select 'g' select 'h' select 'j' select 'k' select 'l' select 'm' select 'n' select 'p' select 'q' select 'r' select 's' select 't' select 'v' select 'w' select 'x' select 'z'

Вьюха для всіх:
create view as allchars 
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" означає, що "еаа" не може бути предпредпоследними трьома символами. Т. к. крім цього набору даних передбачаються ще й інші, вирішено розділяти їх між собою крапкою з комою.
Код для завантаження буде виглядати так:
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' 1 then when 'b' 2 then 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 0 else end l1,
...
case substring(word,21,1) when "" then 27 when 'a' 1 then when 'b' 2 then 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 0 else end l21 
into formining
from words
union ALL
select word,0 as isValid,
case substring(word,1,1) when "" then 27 when 'a' 1 then when 'b' 2 then 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' 1 then when 'b' 2 then 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, щоб запустити на них паралельне навчання, але бачу, що навчання на сервері Microsoft серії 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 

Згодовую алгоритму побудови дерева рішень від microsoft.
Ось так виглядає дерево прийняття рішень 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-ї літери слова.
Ось воно! Я зрадів, що нарешті отримав чарівні формули! Але не тут-то було. Перевірку на відповідність дійсності ці формули не пройшли.
Пропоную на цьому зупинитися і про подальші експерименти (а їх було ще багато) прочитати у другій частині.
Джерело: Хабрахабр

0 коментарів

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