大規模な技術動物園を持ち、外部からの金銭的投資なしで複雑な製品を単独で作成およびサポートすることは、面倒で退屈なビジネスです。 そのため、興味深いタスクでコンテストについて学び、 私たちはメガレントにいます 私は自分のために「創造的な休暇」を手配し、しばらくの間、新しいバージョンの作業から気を散らすことを考えました。
タスクはJSでプログラムを書くことで、英語の単語の辞書から単語があるかどうかを判断します。 それは単純に思えますが、タスクを明らかに不可能にする制限がいくつかあります。
-単語は、英語の正しい単語だけでなく、提供されている60万単語以上の辞書にある単語と見なされます。
-プログラムの実行時には辞書がなく、ダウンロードできません。また、データを含むプログラムのサイズは64Kを超えないようにしてください。 外部ライブラリも接続できませんが、データファイルはアーカイブできます。
これらの条件により、明確な回答の代わりに、結果は辞書に単語が存在する可能性が最も高いかどうかを判断することだけになります。
結果に不満があるため、ソリューションを送信しなかったとすぐに言わなければなりません（少なくとも80％をもたらすソリューションで、120-130Kにしか適合できず、64Kのサイズを超えることなく最大70％を絞りました）。
それでも、私はこの経験が非常に興味深く、記事に値すると考えています。 猫の下には、SQL、JS、Python、ニューラルネットワークがたくさんあり、ホスティングのCPUパフォーマンスに関する悲しい真実もあります。
賞のパンとして、数キロバックスとインタビューへの招待がありました。 数千立方 彼らは家計を邪魔することはないが、天気はあまり変わらず、私は積極的な就職活動も行っていない（確かに、断ることができないような提案があるかもしれない）。 それにもかかわらず、タスク自体が私を「引っ掛けた」ので、私は参加するために1週間を確保することにしました。
コンテスト発表記事のコメントと記事自体で、決定するときにニューラルネットワークを使用するのが適切であることがわかったので、結果を確認するnodejsのライブラリを探しています。または、少なくとも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のトリプルが見つかりました。
同様のリクエストにより、トリプルとフォースの母音と子音が得られます。 4つの母音が少なすぎ、子音が多すぎます。 この時点で、膨大な量のテストデータがすでに蓄積されています。 分析のために、ホスティング上のmongaからローカルSQLに転送する必要があります。
Pythonで、100万語のファイルを含むプレーンテキストに簡単にアップロードします。
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（一括コピープログラム）は、MSSQLとの間で大量のデータを高速でロード/アンロードするためのMicrosoftのコンソールユーティリティです。 特に、特別な「一括ログ」ロギングモードを有効にしないと、データのロードがトランザクションログに反映されないため、非常に高速に動作します。 たとえば、私からの60Mワードは数分でテキストファイルから読み込まれました。 使用例：
bcp tmpdata in result1_0.txt -S localhost -d test -U sa -PP@ssw0rd -f bcp.fmt
指定されたbcp.fmtは、ソースデータ形式の説明を含むファイルで、フィールドとセパレーターのタイプを示します。 指定しない場合、ユーティリティ自体が質問し、将来使用するためにそのようなファイルを作成することを提案します。
66Mの誤った単語については、単純なフィルターによってそれらの単語がいくつ削除されるかをチェックします。
長さ：
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文字のオフセットで追加します。
テスト配列を確認します。 100万ごとに、次のようにふるいにかけられます。
長さ：121576
不足しているペア：37903
欠落しているトリプル：162205
最初のペアの欠落：453
最初の3つの行方不明：13905
2番目のペアの欠落：0
2番目のトリプルがない：6276
3番目のトリプルがない：40114
最後のペアの欠落：594
最後のトリプルがない：6844
最後から2番目のペアの欠落：0
最後から2番目のトリプルがない：6844
最後から2番目のトリプルがない：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であり、それらに加えて、最初から3つ、最後からなどがあることを思い出させてください。
ビットマスクを使用してトリプルのエンドツーエンドのディレクトリを作成することにしました。各ビットは、この組み合わせが単語内で発生しない場所を担当します。 この場合、最初のビットは組み合わせがまったく発生しないことを意味します。これにより、後続のすべてのビットを示す必要がなくなり、スペースを節約できます。
また、予測可能な文字と数字の交替により、セパレータを破棄して再度保存することができます。 したがって、データは次のようになります。
'aa1eaa64oaa106など...
たとえば、「 'aa1」は、「' aa」の組み合わせがまったく発生しないことを意味し、「eaa64」は、「eaa」が最後から3番目の文字になれないことを意味します。 なぜなら このデータセットに加えて、他のデータセットも予想されるため、セミコロンでそれらを分離することが決定されました。
ダウンロードコードは次のようになります。
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％ これは、テストページでの正しい単語と間違った単語の分布がほぼ同じであるという事実だけが原因です。 最初の失望。
ニューラルネットワークのトピックに戻ります。 基本的に、それらはバイナリの入出力データでしか動作できないことを学びます。 最良の場合、シグモイド関数を使用するアルゴリズムは、入力でゼロと1の間の値を取ります。
試してみたいのですが、このために入力データを含むテーブルを準備する必要があります。 最初の考えは、すべての単語が綴られる入力データのセットを供給することでした。
セットのサイズを小さくするために、アルファベットの文字のシリアル番号に対応する5ビットのセットとして各文字を表示することにしました。
このようなデータセットを作成するクエリは次のようになります。
-- , - 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ライブラリを試します-結果は満足できません。 入力データの数千のエントリを持つテストモデルでは、すべてが問題ありませんが、少なくとも5文字の単語の実際のセットをフィードしようとすると、すべてが悪くなります。 トレーニングには時間がかかり、精度はありません。 たぶん問題は隠れ層の数かもしれませんが、10、100、さらには1000を試しました。おそらく、「料理できない」だけなのですが、今までのところ、学習の反復には多くの（少なくとも数万）、大量のデータがあれば、ネットワークが学習する前に競争は終了します。
ホスティングを使用するアイデアがあります。 しかし、判明したように、ホスティングでのCPUの実際のパフォーマンスに関する真実は、ここでも残念なことに私を待っていました。 Azureで数十の仮想マシンを単純に上げて並列トレーニングを実行していますが、D2 V2シリーズのAzureサーバーでのトレーニングは、私のi7-4770の20倍遅い（目で見る）ことがわかります。 どちらの場合も、1つのコアが関与し、GPUは使用されませんでした。 Azureに何か問題があると思います。flops.ruにサーバーがあることを覚えています。そこで試してみました-結果は同じです。 悲しい結論：何らかの理由で、i7を搭載した専用サーバーのプロセッサーは、仮想マシンよりも数倍（私の場合は1桁）高速になります。 20Mレコードのトレーニングを何十万回も繰り返すことはできないことを理解しています。ニューラルネットワークを拒否します。
ニューラルネットワークに加えて、他のマイニングメカニズムもあることを思い出します。 たとえば、決定木や関係検索アルゴリズム。 それらを試してみると、単語の長さ、母音の数、子音、単語内の同一文字の数をデータセットに追加します。 これを行うには、上記の長い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決定ツリーがどのようなものかを示しています。
一見、有望です。 この図は、アルゴリズムの主な要因が長さであり、たとえば、読み込まれた856253バリアントの19文字以上の単語のうち、2079だけが正しいことを示しています。 そして、これらのオプションの中で、順番に、単語の文字「K」の数が影響を与えた主な要因でした。 一方では、情報は興味深いものであり、他方では、それは私たちの仕事にとって役に立たない。 最後に、「離散」ではなく「連続」の予測属性のタイプを指定した場合に何が起こるかを調べるなど、このアルゴリズムでさらにいくつかの実験を行いました。 この場合、興味深い結果が得られます：
ご覧のとおり、ノードには次の式があります。
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文字。
ここにある！ 私はついに魔法の公式を手に入れてうれしかった！ しかし、そこにありました。 これらの式の検証に合格しませんでした。
私はこれと、 第2部で読むためのさらなる実験（およびさらに多くの実験）について検討することを提案します。