ML-Blitz: analyse des tâches du premier tour de qualification

Donc, nous devons construire une approximation par morceaux d'une fonction connue. Si le paramètre $$$c$ connu puis trouver les paramètres $$$a$ et $$$b$ assez simple. Vous pouvez écrire des solutions mathématiquement comme solutions aux problèmes d'optimisation correspondants. Paramètre $$$a$ L'ampleur des prédictions du moignon décisif sur ces objets $$$(x_i, y_i)$ échantillon de formation pour lequel $$$x_i <c$ . De même $$$b$ L'ampleur des prédictions sur ces objets $$$(x_i, y_i)$ échantillon de formation pour lequel $$$x_i \ ge c$ .

Nous introduisons la notation pour les sous-ensembles correspondants de l'ensemble d'apprentissage: $$$L (c)$ Est un sous-ensemble d'objets à gauche d'un point $$$c$ , $$$R (c)$ - le sous-ensemble d'objets à droite du point $$$c$ .

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

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

Ensuite, la valeur optimale $$$a$ sera égal à la moyenne arithmétique des réponses de l'ensemble $$$L (c)$ et la valeur optimale $$$b$ - respectivement, la moyenne arithmétique des réponses dans l'ensemble $$$R (c)$ .

Alors maintenant, il est clair comment trouver les paramètres $$$a$ et $$$b$ avec un paramètre connu $$$c$ . Reste à comprendre comment trouver la valeur de paramètre optimale $$$c$ .

La première chose à remarquer: paramètre $$$c$ peut prendre n'importe quelle valeur réelle, mais de nombreuses partitions différentes sont finies. Échantillon d'apprentissage de $$$n$ les objets ne peuvent être cassés que $$$n + 1$ chemins vers les parties "gauche" et "droite". En réalité, il peut y avoir encore moins de telles partitions: par exemple, pour certains objets, les valeurs des attributs peuvent coïncider. De plus, les partitions sont équivalentes pour nous, dans lesquelles tous les objets du set de formation sont à gauche ou à droite.

Pour obtenir toutes les partitions possibles, vous pouvez trier les objets de l'ensemble d'apprentissage par attribut non décroissant:

$$ $$(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}$$

Maintenant, il est clair que les valeurs de paramètres potentiellement intéressantes $$$c$ Les quantités sont-elles

$$ $$\ 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}$$

Maintenant, il est clair ce qui doit être fait pour obtenir une solution. Il est nécessaire de trier toutes les valeurs de paramètres potentiellement intéressantes $$$c$ , déterminer pour chacun d'eux les quantités correspondantes $$$a$ et $$$b$ , ainsi que la valeur de la perte fonctionnelle. Ensuite, vous devez sélectionner un ensemble de paramètres correspondant au minimum des valeurs fonctionnelles de perte.

Il ne reste plus qu'à savoir comment rendre cette solution efficace. La mise en œuvre directe de l'algorithme décrit entraînera une complexité quadratique de l'algorithme, ce qui est inacceptable.

Pour rendre les calculs efficaces, n'oubliez pas que pour trouver les paramètres $$$a$ et $$$b$ il suffit de calculer les valeurs moyennes sur l'ensemble. Lorsque vous ajoutez un autre élément à l'ensemble (ou après avoir supprimé un élément de l'ensemble), la valeur moyenne peut être effectivement calculée pour un temps constant si vous stockez non pas la moyenne elle-même, mais séparément la somme des valeurs et leur nombre séparément. La situation est similaire avec la somme des écarts au carré. Pour le calculer, selon la formule bien connue de calcul de la variance , vous pouvez stocker séparément la somme des quantités et la somme des carrés des quantités. De plus, vous pouvez utiliser n'importe quelle méthode de calcul en ligne . Plus tôt, j'ai déjà écrit à ce sujet sur un hub

Dans la mise en œuvre, j'utiliserai la méthode Wellford, comme Je l'aime plus que les calculs utilisant des formules "standard". De plus, je n'utiliserai pas numpy ni aucune autre bibliothèque pour démontrer que la connaissance des constructions élémentaires du langage python est suffisante pour obtenir une solution.

Nous devons donc être en mesure de calculer progressivement la moyenne et la somme des écarts au carré. Pour ce faire, nous décrivons deux classes:

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) 

Maintenant, nous avons besoin d'une classe pour stocker et traiter l'ensemble de formation. Tout d'abord, nous décrivons ses champs et sa méthode de saisie:

 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() 

Simultanément à la saisie des données, nous formons immédiatement la structure SumSquaredErrorsCalculator pour tous les objets de la sélection. Après avoir chargé l'échantillon entier, nous le trions par valeurs d'attribut non décroissantes.

Maintenant, la chose la plus intéressante: la méthode pour trouver les valeurs optimales des paramètres.

Commençons par l'initialisation. Dans l'état initial, tous les objets sont dans le bon sous-échantillon. Ensuite, le paramètre $$$a$ peut être égal à n'importe quoi, paramètre $$$b$ égale à la réponse moyenne dans l'ensemble de l'échantillon, et le paramètre $$$c$ de sorte que tous les objets de la sélection se trouvent à sa droite.

De plus, nous initialisons les variables left et right - elles stockeront des statistiques pour les sous-échantillons gauche et droit, respectivement.

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

Passons maintenant à l'algorithme incrémental. Nous traiterons les éléments de sélection un par un. Chaque élément est transféré dans le sous-ensemble gauche. Ensuite, vous devez vérifier que la partition correspondante existe réellement - c'est-à-dire que la valeur de la caractéristique est différente de la valeur de la caractéristique de l'objet suivant.

 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 

Il ne reste plus qu'à composer le code pour obtenir une solution:

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

Je note que la solution présentée en python est bien acceptée par le système, mais elle arrive à la limite supérieure dans le temps de la solution: les plus gros tests nécessitent environ 800 millisecondes pour s'exécuter. Bien sûr, l'utilisation de bibliothèques supplémentaires peut atteindre des performances beaucoup plus impressionnantes.

Par conséquent, j'ai également implémenté l'algorithme proposé en C ++ . Cette solution a passé dans le pire des cas 60 millisecondes sur l'un des tests.

Développez les crochets, en ignorant les variables aléatoires:

$$ $$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$$

Nous avons maintenant le problème de régression linéaire multidimensionnelle sans coefficient libre. Les caractéristiques de ce problème sont les quantités $$$\ sin ^ 2 (x)$ , $$$\ ln ^ 2 (x)$ , $$$\ sin (x) \ cdot \ ln (x)$ , $$$x ^ 2$ .

Étant donné que la dépendance fonctionnelle n'implique pas de coefficient libre et que toutes les composantes aléatoires ont une moyenne nulle, on peut s'attendre à ce que le coefficient libre soit pratiquement nul lors de l'apprentissage du modèle. Cependant, cela vaut la peine de vérifier cela avant de soumettre la solution.

Lors de la résolution du problème de la régression linéaire multidimensionnelle, certains coefficients seront trouvés avec des caractéristiques modifiées. En fait, la représentation suivante sera trouvée pour la fonction $$$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$$

Après cela, vous pouvez trouver les coefficients $$$a$ , $$$b$ , $$$c$ :

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

En outre, il convient de vérifier que $$$2 \ cdot a \ cdot b \ environ t_3$

Pour commencer, vous devez lire les données et former les signes:

 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) 

Il est maintenant nécessaire de résoudre le problème de la régression linéaire multidimensionnelle. Il existe un grand nombre de façons de le faire - des outils comme les fonctions de bibliothèque Weka et sklearn à ma propre implémentation . Cependant, dans ce cas, je voulais obtenir une solution "fermée": un script qui résout complètement le problème. Par conséquent, j'ai utilisé 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 

Dans ce cas, il s'est avéré que le coefficient libre est de -0,0007, et l'erreur dans le calcul $$$t_3$ s'élevait à 0,00135. Ainsi, la solution trouvée est parfaitement cohérente.

La dernière ligne avec les coefficients:

 3.14172883822 2.71842889253 3.999957864335599 

En le substituant comme la réponse au problème, nous obtenons le OK bien mérité!

Puisque la valeur requise $$$F_1$ -les mesures ne sont pas trop grandes, c'est sûr qu'une méthode assez simple conviendra pour résoudre le problème. J'ai donc essayé d'exécuter CatBoost sur les facteurs fournis, puis de binariser ses prédictions.

Pour que CatBoost fonctionne, vous devez fournir deux fichiers: formation et test, ainsi que des descriptions de colonne. La description des colonnes est facile à compiler: les deux premières colonnes sont le texte de la demande et l'horodatage, il est plus facile de les ignorer. La dernière colonne est la réponse. Par conséquent, nous obtenons la description suivante des colonnes :

 0 Auxiliary 1 Auxiliary 8 Target 

Étant donné que le fichier de test ne contient pas de réponses et, par conséquent, la dernière colonne, nous ajoutons cette colonne en la remplissant simplement de zéros. J'utilise le awk habituel pour cela:

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

Vous pouvez maintenant former CatBoostL

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

Après cela, les prédictions seront dans le fichier output.tsv . Cependant, ce seront des prédictions importantes qui doivent encore être binarisées.

Nous partirons du fait que la part d'exemples positifs dans les échantillons de formation et de test coïncide. Dans l'exemple de formation, environ 3/4 de toutes les requêtes contiennent des clics sur des documents récents. Par conséquent, nous sélectionnons le seuil de classification de manière à ce qu'environ les 3/4 de toutes les demandes de l'échantillon test soient assorties de prédictions positives. Par exemple, pour un seuil de 0,04, il y a 178925 sur 200 000.

Par conséquent, nous formons le fichier de solution comme suit:

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

Ici, il fallait sauter la première ligne, car CatBoost y écrit ses propres noms de colonnes.

Le fichier solution.tsv ainsi obtenu est envoyé au système de vérification et reçoit un OK légitime comme verdict.

Comme vous le savez, il existe une grande variété de méthodes pour sélectionner les caractères.

Par exemple, vous pouvez utiliser une méthode prête à l'emploi. Disons que j'ai essayé d'exécuter la sélection des fonctionnalités dans Weka et après un peu de réglage des paramètres, j'ai réussi à obtenir 1,8 points dans cette tâche.

De plus, j'ai mon propre script pour sélectionner les fonctionnalités. Ce script implémente une stratégie gourmande: exactement un facteur est ajouté à l'échantillon à chaque fois, de sorte que l'ajouter de la meilleure façon affecte l' estimation du contrôle de déplacement pour l'algorithme. Cependant, dans le cadre du concours, l'exécution d'un tel script prendra soit trop de temps, soit un gros cluster informatique.

Cependant, lors de l'utilisation de forêts cruciales avec régularisation (y compris CatBoost), il existe également une méthode extrêmement rapide pour sélectionner les traits: vous devez sélectionner les facteurs qui sont souvent utilisés dans le modèle. L'algorithme CatBoost a un mode intégré pour évaluer l'influence des facteurs sur les prédictions du modèle, et nous allons l'utiliser.

Vous devez d'abord former le modèle:

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

Exécutez ensuite une évaluation des fonctionnalités:

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

L'importance des caractéristiques sera alors écrite dans le fichier feature_strength.tsv . Dans la première colonne, la signification des signes sera enregistrée, dans la seconde - leurs noms. Le fichier est immédiatement trié par importance non croissante des fonctionnalités.

 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 

Il ne reste plus qu'à prendre les quelques dizaines de premiers signes et à former une réponse. De plus, il est logique de prendre le moins de fonctionnalités possible - comme vous le savez, la complexité des modèles affecte négativement leur capacité de généralisation.

Disons que si vous sélectionnez les 50 premiers signes, sur un ensemble de test public, vous pourriez obtenir 3,6 points; si vous choisissez le top 40, le top 30 ou le top 20, vous obtenez exactement 4 points. Par conséquent, j'ai choisi les 20 premiers signes comme solution - cette solution a reçu 4 points sur une suite de tests fermée.

Il convient de noter au final que la méthode envisagée pour sélectionner les entités n'est pas optimale dans toutes les situations. Souvent, les caractéristiques «nocives» ont un effet significatif sur l’ampleur de la prédiction du modèle, mais en même temps aggravent la capacité de généralisation des algorithmes. Par conséquent, dans chaque tâche, lorsque le problème de sélection des fonctionnalités se pose, il convient de vérifier plusieurs approches connues du chercheur à la fois et de choisir la meilleure.

En outre, vous devez vous rappeler d'autres façons de réduire la dimension de l'espace d' entités - par exemple, il existe une grande variété de méthodes d' extraction d'entités .