ML-Blitz: analisis tugas babak kualifikasi pertama

Jadi, kita perlu membangun pendekatan piecewise-smooth dari fungsi yang diketahui. Jika parameternya $$$c$ diketahui kemudian cari parameternya $$$a$ dan $$$b$ cukup sederhana. Anda dapat menulis solusi secara matematis sebagai solusi untuk masalah optimasi yang sesuai. Parameter $$$a$ Apakah besarnya prediksi tunggul yang menentukan pada benda-benda itu $$$(x_i, y_i)$ sampel pelatihan yang $$$x_i <c$ . Begitu pula $$$b$ Apakah besarnya prediksi pada objek tersebut $$$(x_i, y_i)$ sampel pelatihan yang $$$x_i \ ge c$ .

Kami memperkenalkan notasi untuk himpunan bagian yang sesuai dari set pelatihan: $$$L (c)$ Merupakan himpunan bagian dari objek di sebelah kiri titik $$$c$ , $$$R (c)$ - subset objek di sebelah kanan titik $$$c$ .

$$ $$L (c) = \ {(x_i, y_i) | x_i <c \}$$

$$ $$R (c) = \ {(x_i, y_i) | x_i \ ge c \}$$

Maka nilai optimal $$$a$ akan sama dengan rata-rata aritmatika dari jawaban di set $$$L (c)$ , dan nilai optimal $$$b$ - masing-masing, rata-rata aritmatika dari jawaban di set $$$R (c)$ .

Jadi sekarang sudah jelas bagaimana menemukan parameter $$$a$ dan $$$b$ dengan parameter yang diketahui $$$c$ . Tetap memahami bagaimana menemukan nilai parameter yang optimal $$$c$ .

Hal pertama yang diperhatikan: parameter $$$c$ dapat mengambil nilai nyata apa pun, tetapi banyak partisi berbeda terbatas. Belajar sampel dari $$$n$ benda bisa dipatahkan tidak lebih dari $$$n + 1$ cara untuk bagian "kiri" dan "kanan". Pada kenyataannya, bahkan mungkin ada lebih sedikit partisi seperti itu: misalnya, untuk beberapa objek, nilai atribut mungkin bertepatan. Selain itu, partisi setara untuk kita, di mana semua objek di set pelatihan ada di sebelah kiri atau di sebelah kanan.

Untuk mendapatkan semua partisi yang mungkin, Anda bisa mengurutkan objek pelatihan yang ditetapkan oleh atribut yang tidak berkurang:

$$ $$(x_ {i_1}, y_ {i_1}), \ ldots (x_ {i_n}, y_ {i_n})$$

$$ $$x_ {i_1} \ le x_ {i_2} \ le \ ldots \ le x_ {i_n}$$

Sekarang jelas bahwa nilai parameter yang berpotensi menarik $$$c$ Apakah jumlahnya

$$ $$\ frac {x_ {i_1} + x_ {i_2}} {2}, \ frac {x_ {i_2} + x_ {i_3}} {2}, \ ldots, \ frac {x_ {i_ {n-1}} + x_ {i_n}} {2}$$

Sekarang jelas apa yang perlu dilakukan untuk mendapatkan solusi. Penting untuk memilah-milah semua nilai parameter yang berpotensi menarik $$$c$ , untuk masing-masing menentukan jumlah yang sesuai $$$a$ dan $$$b$ , serta nilai kerugian fungsional. Maka Anda perlu memilih satu set parameter yang sesuai dengan minimum nilai fungsional kerugian.

Yang tersisa hanyalah pertanyaan bagaimana membuat solusi ini efektif. Implementasi langsung dari algoritma yang dijelaskan akan mengarah pada kompleksitas kuadratik dari algoritma, yang tidak dapat diterima.

Untuk membuat perhitungan efektif, ingatlah untuk menemukan parameter $$$a$ dan $$$b$ hanya perlu menghitung nilai rata-rata selama set. Ketika Anda menambahkan elemen berikutnya ke set (atau setelah menghapus elemen dari set), nilai rata-rata dapat dihitung secara efektif untuk waktu yang konstan jika Anda tidak menyimpan rata-rata itu sendiri, tetapi secara terpisah jumlah nilai dan jumlahnya secara terpisah. Situasinya mirip dengan jumlah penyimpangan kuadrat. Untuk menghitungnya, sesuai dengan rumus terkenal untuk menghitung varians , Anda dapat secara terpisah menyimpan jumlah kuantitas dan jumlah kuadrat kuantitas. Selain itu, Anda dapat menggunakan metode perhitungan online apa pun. Sebelumnya saya sudah menulis tentang itu di hub

Dalam implementasinya, saya akan menggunakan metode Wellford, sebagai Saya lebih menyukainya daripada perhitungan menggunakan rumus "standar". Selain itu, saya tidak akan menggunakan numpy dan perpustakaan lain untuk menunjukkan bahwa pengetahuan tentang konstruksi dasar bahasa python sudah cukup untuk mendapatkan solusi.

Jadi, kita harus dapat secara bertahap menghitung rata-rata dan jumlah dari penyimpangan kuadrat. Untuk melakukan ini, kami menggambarkan dua kelas:

class MeanCalculator: def __init__(self): self.Count = 0. self.Mean = 0. def Add(self, value, weight = 1.): self.Count += weight self.Mean += weight * (value - self.Mean) / self.Count def Remove(self, value, weight = 1.): self.Add(value, -weight) class SumSquaredErrorsCalculator: def __init__(self): self.MeanCalculator = MeanCalculator() self.SSE = 0. def Add(self, value, weight = 1.): curDiff = value - self.MeanCalculator.Mean self.MeanCalculator.Add(value, weight) self.SSE += weight * curDiff * (value - self.MeanCalculator.Mean) def Remove(self, value, weight = 1.): self.Add(value, -weight) 

Sekarang kita membutuhkan kelas untuk menyimpan dan memproses set pelatihan. Pertama, kami menjelaskan bidang dan metode inputnya:

 class Instances: def __init__(self): self.Items = [] self.OverAllSSE = SumSquaredErrorsCalculator() def Read(self): fin = open('stump.in') for line in fin.readlines()[1:]: x, y = map(float, line.strip().split()) self.Items.append([x, y]) self.OverAllSSE.Add(y) self.Items.sort() 

Bersamaan dengan entri data, kami segera membentuk struktur SumSquaredErrorsCalculator untuk semua objek dalam pemilihan. Setelah memuat seluruh sampel, kami mengurutkannya dengan nilai atribut yang tidak berkurang.

Sekarang hal yang paling menarik: metode untuk menemukan nilai parameter yang optimal.

Mari kita mulai dengan inisialisasi. Pada kondisi awal, semua objek berada dalam subsampel yang tepat. Lalu parameternya $$$a$ bisa sama dengan apa saja, parameter $$$b$ sama dengan respons rata-rata di seluruh sampel, dan parameter $$$c$ sedemikian rupa sehingga semua objek dalam seleksi berada di sebelah kanannya.

Selain itu, kami menginisialisasi variabel left dan right - masing-masing akan menyimpan statistik untuk subsampel kiri dan kanan.

 left = SumSquaredErrorsCalculator() right = self.OverAllSSE bestA = 0 bestB = right.MeanCalculator.Mean bestC = self.Items[0][0] bestQ = right.SSE 

Sekarang mari kita beralih ke algoritma inkremental. Kami akan memproses elemen pemilihan satu per satu. Setiap elemen ditransfer ke subset kiri. Maka Anda perlu memverifikasi bahwa partisi yang sesuai benar-benar ada - yaitu, nilai karakteristik berbeda dari nilai karakteristik objek berikutnya.

 for i in range(len(self.Items) - 1): item = self.Items[i] nextItem = self.Items[i + 1] left.Add(item[1]) right.Remove(item[1]) if item[0] == nextItem[0]: continue a = left.MeanCalculator.Mean b = right.MeanCalculator.Mean c = (item[0] + nextItem[0]) / 2 q = left.SSE + right.SSE if q < bestQ: bestA = a bestB = b bestC = c bestQ = q 

Sekarang tinggal membuat kode untuk mendapatkan solusi:

 instances = Instances() instances.Read() a, b, c = instances.BestSplit() print >> open('stump.out', 'w'), a, b, c 

Saya perhatikan bahwa solusi yang disajikan dalam python memang diterima oleh sistem, tetapi ia datang ke batas atas pada saat solusi: tes terbesar membutuhkan sekitar 800 milidetik untuk dieksekusi. Tentu saja, menggunakan perpustakaan tambahan dapat mencapai kinerja yang jauh lebih mengesankan.

Oleh karena itu, saya juga mengimplementasikan algoritma yang diusulkan dalam C ++ . Solusi ini dihabiskan dalam kasus terburuk 60 milidetik pada salah satu tes.

Luaskan braket, dengan mengabaikan variabel acak:

$$ $$f (x) = a ^ 2 \ cdot \ sin ^ 2 (x) + b ^ 2 \ cdot \ ln ^ 2 (x) + 2ab \ cdot \ sin (x) \ cdot \ ln (x) + c \ cdot x ^ 2$$

Sekarang kita memiliki masalah regresi linier multidimensi tanpa koefisien bebas. Karakteristik dalam masalah ini adalah jumlah $$$\ sin ^ 2 (x)$ , $$$\ ln ^ 2 (x)$ , $$$\ sin (x) \ cdot \ ln (x)$ , $$$x ^ 2$ .

Karena ketergantungan fungsional tidak menyiratkan koefisien bebas, dan semua komponen acak memiliki rata-rata nol, dapat diharapkan bahwa koefisien bebas akan praktis nol ketika melatih model. Namun, ada baiknya memeriksa ini sebelum mengirimkan solusi.

Ketika memecahkan masalah regresi linear multidimensi, beberapa koefisien akan ditemukan dengan fitur yang dimodifikasi. Bahkan, representasi berikut akan ditemukan untuk fungsi tersebut $$$f$ :

$$ $$f (x) = t_1 \ cdot \ sin ^ 2 (x) + t_2 \ cdot \ ln ^ 2 (x) + t_3 \ cdot \ sin (x) \ cdot \ ln (x) + t_4 \ cdot x ^ 2$$

Setelah itu, Anda dapat menemukan koefisien $$$a$ , $$$b$ , $$$c$ :

$$ $$a = \ sqrt (t_1), b = \ sqrt (t_2), c = t_4$$

Selain itu, perlu diperiksa $$$2 \ cdot a \ cdot b \ approx t_3$

Untuk memulainya, Anda harus membaca data dan membentuk tanda:

 x = [] y = [] for line in open('data.txt'): xx, yy = map(float, line.strip().split()) x.append(xx) y.append(yy) features = [] for xx in x: curFeatures = [ math.sin(xx) ** 2, # a^2 math.log(xx) ** 2, # b^2 math.sin(xx) * math.log(xx), # 2ab xx ** 2 # c ] features.append(curFeatures) 

Sekarang perlu untuk menyelesaikan masalah regresi linier multidimensi. Ada banyak cara untuk melakukan ini - dari alat seperti Weka dan fungsi pustaka sklearn hingga implementasi saya sendiri . Namun, dalam hal ini, saya ingin mendapatkan solusi "tertutup": satu skrip yang sepenuhnya menyelesaikan masalah. Karena itu, saya menggunakan sklearn.

 linearModel = lm.LinearRegression() linearModel.fit(features, y) coeffs = linearModel.coef_ a = math.sqrt(coeffs[0]) b = math.sqrt(coeffs[1]) c = coeffs[3] print "free coeff: ", linearModel.intercept_ print "2ab error: ", coeffs[2] - 2 * a * b print a, b, c 

Dalam hal ini, ternyata koefisien bebasnya adalah -0.0007, dan kesalahan dalam perhitungan $$$t_3$ sebesar 0,00135. Dengan demikian, solusi yang ditemukan benar-benar konsisten.

Baris terakhir dengan koefisien:

 3.14172883822 2.71842889253 3.999957864335599 

Mengganti itu sebagai jawaban untuk masalah, kita mendapatkan OK yang memang layak!

Karena nilai yang diperlukan $$$F_1$ -Mengukur tidak terlalu besar, pasti beberapa metode yang cukup sederhana akan cocok untuk menyelesaikan masalah. Jadi saya mencoba menjalankan CatBoost pada faktor-faktor yang disediakan dan kemudian mem-binari prediksi-nya.

Agar CatBoost berfungsi, Anda perlu menyediakan dua file: pelatihan dan tes, serta deskripsi kolom. Deskripsi kolom mudah dikompilasi: dua kolom pertama adalah teks permintaan dan cap waktu, lebih mudah untuk mengabaikannya. Kolom terakhir adalah jawabannya. Oleh karena itu, kami mendapatkan uraian kolom berikut :

 0 Auxiliary 1 Auxiliary 8 Target 

Karena file tes tidak mengandung jawaban dan, oleh karena itu, kolom terakhir, kami menambahkan kolom ini hanya dengan mengisinya dengan nol. Saya menggunakan awk yang biasa untuk ini:

 awk -F "\t" -vOFS="\t" '{print $0, 0}' fr_test.tsv > fr_test.fixed 

Sekarang Anda dapat melatih CatBoostL

 catboost calc --input-path fr_test.fixed --cd fields.cd 

Setelah itu, prediksi akan berada di file output.tsv . Namun, ini akan menjadi prediksi material yang masih perlu dibubarkan.

Kami akan melanjutkan dari fakta bahwa bagian dari contoh positif dalam pelatihan dan sampel uji bertepatan. Dalam sampel pelatihan, sekitar 3/4 dari semua pertanyaan berisi klik pada dokumen terbaru. Oleh karena itu, kami memilih ambang klasifikasi sehingga sekitar 3/4 dari semua permintaan dari sampel uji dengan prediksi positif. Misalnya, untuk ambang 0,04, ada 178925 dari 200.000.

Oleh karena itu, kami membentuk file solusi sebagai berikut:

 awk -F "\t" -vOFS="\t" 'NR > 1 {if ($2 > 0.04) print 1; else print 0}' output.tsv > solution.tsv 

Di sini perlu untuk melewati baris pertama, karena CatBoost menulis nama kolomnya sendiri di dalamnya.

File solution.tsv yang diperoleh kemudian dikirim ke sistem verifikasi dan menerima OK yang sah sebagai vonis.

Seperti yang Anda ketahui, ada beragam metode untuk memilih fitur.

Misalnya, Anda dapat menggunakan beberapa metode yang sudah jadi. Katakanlah saya mencoba menjalankan pemilihan fitur di Weka dan setelah sedikit penyesuaian parameter saya berhasil mendapatkan 1,8 poin dalam tugas ini.

Selain itu, saya memiliki skrip sendiri untuk memilih fitur. Script ini menerapkan strategi serakah: tepatnya satu faktor ditambahkan ke sampel setiap kali, sehingga menambahkannya dengan cara terbaik memengaruhi estimasi kontrol bergerak untuk algoritma. Namun, dalam konteks kontes, untuk menjalankan skrip seperti itu akan memakan waktu terlalu lama atau cluster komputasi yang besar.

Namun, ketika menggunakan hutan penting dengan regularisasi (termasuk CatBoost), ada juga satu metode yang sangat cepat untuk memilih sifat: Anda harus memilih faktor-faktor yang sering digunakan dalam model. Algoritma CatBoost memiliki mode bawaan untuk menilai pengaruh faktor pada prediksi model, dan kami akan menggunakannya.

Pertama, Anda perlu melatih model:

 catboost fit --cd train.cd -f train.txt 

Kemudian jalankan penilaian fitur:

 catboost fstr --input-path train.txt --cd train.cd 

Pentingnya karakteristik kemudian akan ditulis ke file feature_strength.tsv . Di kolom pertama, signifikansi dari tanda-tanda akan dicatat, di kolom kedua - namanya. File tersebut segera disortir oleh pentingnya fitur yang tidak meningkat.

 head feature_strength.tsv 9.897213004 f193 9.669603844 f129 7.500907599 f292 5.903810044 f48 5.268100711 f337 2.508377813 f283 2.024904488 f111 1.933500313 f208 1.878848285 f345 1.652808387 f110 

Tetap hanya untuk mengambil beberapa lusin tanda pertama dan membentuk jawaban. Selain itu, masuk akal untuk mengambil fitur sesedikit mungkin - seperti yang Anda tahu, kompleksitas model secara negatif mempengaruhi kemampuan generalisasi mereka.

Katakanlah, jika Anda memilih 50 tanda teratas, maka pada set tes publik Anda bisa mendapatkan 3,6 poin; jika Anda memilih 40 besar, 30 besar atau 20 teratas, Anda mendapatkan 4 poin. Oleh karena itu, saya memilih 20 tanda teratas sebagai solusi - solusi ini menerima 4 poin pada test suite tertutup.

Perlu dicatat pada akhirnya bahwa metode pemilihan fitur yang dipertimbangkan tidak optimal dalam semua situasi. Seringkali, fitur "berbahaya" memiliki efek signifikan pada besarnya prediksi model, tetapi pada saat yang sama memperburuk kemampuan generalisasi dari algoritma. Oleh karena itu, dalam setiap tugas, ketika masalah memilih fitur muncul, ada baiknya memeriksa beberapa pendekatan yang diketahui peneliti sekaligus dan memilih yang terbaik.

Selain itu, Anda perlu mengingat cara-cara lain untuk mengurangi dimensi ruang fitur - misalnya, ada berbagai metode untuk mengekstraksi fitur .