ML-Blitz: Analyse der Aufgaben der ersten Qualifikationsrunde

Wir müssen also eine stückweise glatte Approximation einer bekannten Funktion erstellen. Wenn der Parameter $$$c$ bekannt dann finden die Parameter $$$a$ und $$$b$ einfach genug. Sie können Lösungen mathematisch als Lösungen für die entsprechenden Optimierungsprobleme schreiben. Parameter $$$a$ Ist die Größe der Vorhersagen des entscheidenden Stumpfes bei diesen Objekten $$$(x_i, y_i)$ Trainingsmuster für die $$$x_i <c$ . Ähnlich $$$b$ Ist die Größe der Vorhersagen an diesen Objekten $$$(x_i, y_i)$ Trainingsmuster für die $$$x_i \ ge c$ .

Wir führen die Notation für die entsprechenden Teilmengen des Trainingssatzes ein: $$$L (c)$ Ist eine Teilmenge von Objekten links von einem Punkt $$$c$ , $$$R (c)$ - die Teilmenge der Objekte rechts vom Punkt $$$c$ .

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

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

Dann der optimale Wert $$$a$ wird gleich dem arithmetischen Mittel der Antworten in der Menge sein $$$L (c)$ und der optimale Wert $$$b$ - jeweils das arithmetische Mittel der Antworten in der Menge $$$R (c)$ .

Jetzt ist klar, wie die Parameter zu finden sind $$$a$ und $$$b$ mit einem bekannten Parameter $$$c$ . Es bleibt zu verstehen, wie der optimale Parameterwert gefunden wird $$$c$ .

Das erste, was zu beachten ist: Parameter $$$c$ kann beliebige reale Werte annehmen, aber viele verschiedene Partitionen sind endlich. Lernbeispiel von $$$n$ Objekte können nicht mehr als gebrochen werden $$$n + 1$ Wege zu den "linken" und "rechten" Teilen. In der Realität kann es noch weniger solcher Partitionen geben: Beispielsweise können bei einigen Objekten die Werte der Attribute übereinstimmen. Außerdem sind Partitionen für uns gleichwertig, bei denen sich alle Objekte im Trainingssatz links oder rechts befinden.

Um alle möglichen Partitionen zu erhalten, können Sie die Objekte des Trainingssatzes nach nicht abnehmendem Attribut sortieren:

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

Jetzt ist klar, dass die potenziell interessanten Parameterwerte $$$c$ Sind die Mengen

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

Jetzt ist klar, was getan werden muss, um eine Lösung zu finden. Es ist notwendig, alle potenziell interessanten Parameterwerte zu sortieren $$$c$ bestimmen für jeden von ihnen die entsprechenden Mengen $$$a$ und $$$b$ sowie den Wert der Verlustfunktion. Dann müssen Sie eine Reihe von Parametern auswählen, die dem Minimum der Verlustfunktionswerte entsprechen.

Es bleibt nur die Frage, wie diese Lösung effektiv gestaltet werden kann. Die direkte Implementierung des beschriebenen Algorithmus führt zu einer quadratischen Komplexität des Algorithmus, die nicht akzeptabel ist.

Denken Sie daran, die Parameter zu ermitteln, um die Berechnungen effektiv zu gestalten $$$a$ und $$$b$ Es ist nur erforderlich, die Durchschnittswerte über dem Satz zu berechnen. Wenn Sie der Menge ein weiteres Element hinzufügen (oder nachdem Sie ein Element aus der Menge entfernt haben), kann der Durchschnittswert für eine konstante Zeit effektiv berechnet werden, wenn Sie nicht den Durchschnitt selbst speichern, sondern die Summe der Werte und ihre Anzahl separat. Ähnlich verhält es sich mit der Summe der quadratischen Abweichungen. Um es zu berechnen, können Sie nach der bekannten Formel zur Berechnung der Varianz die Summe der Mengen und die Summe der Quadrate der Mengen getrennt speichern. Darüber hinaus können Sie eine beliebige Online-Berechnungsmethode verwenden . Ich habe schon früher auf einem Hub darüber geschrieben

In der Implementierung werde ich die Wellford-Methode verwenden, as Ich mag es mehr als Berechnungen mit "Standard" -Formeln. Außerdem werde ich numpy und keine anderen Bibliotheken verwenden, um zu demonstrieren, dass die Kenntnis der elementaren Konstruktionen der Python-Sprache ausreicht, um eine Lösung zu finden.

Wir müssen also in der Lage sein, den Durchschnitt und die Summe der quadratischen Abweichungen schrittweise zu berechnen. Dazu beschreiben wir zwei Klassen:

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) 

Jetzt brauchen wir eine Klasse, um das Trainingsset zu speichern und zu verarbeiten. Zunächst beschreiben wir die Felder und die Eingabemethode:

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

Gleichzeitig mit der Dateneingabe bilden wir sofort die SumSquaredErrorsCalculator-Struktur für alle Objekte in der Auswahl. Nachdem wir die gesamte Stichprobe geladen haben, sortieren wir sie nach nicht abnehmenden Attributwerten.

Nun das Interessanteste: die Methode zum Finden der optimalen Parameterwerte.

Beginnen wir mit der Initialisierung. Im Ausgangszustand befinden sich alle Objekte im richtigen Teilmuster. Dann der Parameter $$$a$ kann gleich sein, Parameter $$$b$ gleich der durchschnittlichen Antwort in der gesamten Stichprobe und dem Parameter $$$c$ so dass alle Objekte in der Auswahl rechts davon sind.

Außerdem initialisieren wir die left und die right Variable - sie speichern Statistiken für die linke bzw. rechte Unterprobe.

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

Kommen wir nun zum inkrementellen Algorithmus. Wir werden die Auswahlelemente einzeln verarbeiten. Jedes Element wird in die linke Teilmenge übertragen. Dann müssen Sie überprüfen, ob die entsprechende Partition tatsächlich vorhanden ist - das heißt, der Wert des Merkmals unterscheidet sich vom Wert des Merkmals des nächsten Objekts.

 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 

Jetzt muss nur noch der Code erstellt werden, um eine Lösung zu erhalten:

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

Ich stelle fest, dass die in Python vorgestellte Lösung zwar vom System akzeptiert wird, aber zum Zeitpunkt der Lösung an die obere Grenze gelangt: Die Ausführung der größten Tests dauert etwa 800 Millisekunden. Die Verwendung zusätzlicher Bibliotheken kann natürlich eine viel beeindruckendere Leistung erzielen.

Daher habe ich den vorgeschlagenen Algorithmus auch in C ++ implementiert . Diese Lösung verbrachte im schlimmsten Fall 60 Millisekunden mit einem der Tests.

Erweitern Sie die Klammern und ignorieren Sie die Zufallsvariablen:

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

Jetzt haben wir das mehrdimensionale lineare Regressionsproblem ohne freien Koeffizienten. Die Merkmale bei diesem Problem sind die Mengen $$$\ sin ^ 2 (x)$ , $$$\ ln ^ 2 (x)$ , $$$\ sin (x) \ cdot \ ln (x)$ , $$$x ^ 2$ .

Da die funktionale Abhängigkeit keinen freien Koeffizienten impliziert und alle zufälligen Komponenten einen Mittelwert von Null haben, kann erwartet werden, dass der freie Koeffizient beim Training des Modells praktisch Null ist. Es lohnt sich jedoch, dies zu überprüfen, bevor Sie die Lösung einreichen.

Bei der Lösung des Problems der mehrdimensionalen linearen Regression werden einige Koeffizienten mit modifizierten Merkmalen gefunden. Tatsächlich wird die folgende Darstellung für die Funktion gefunden $$$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$$

Danach können Sie die Koeffizienten finden $$$a$ , $$$b$ , $$$c$ ::

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

Darüber hinaus lohnt es sich, dies zu überprüfen $$$2 \ cdot a \ cdot b \ ca. t_3$

Zunächst sollten Sie die Daten lesen und die Zeichen bilden:

 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) 

Nun ist es notwendig, das Problem der mehrdimensionalen linearen Regression zu lösen. Es gibt eine Vielzahl von Möglichkeiten, dies zu tun - von Tools wie Weka und sklearn Bibliotheksfunktionen bis zu meiner eigenen Implementierung . In diesem Fall wollte ich jedoch eine "geschlossene" Lösung erhalten: ein Skript, das das Problem vollständig löst. Deshalb habe ich sklearn verwendet.

 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 

In diesem Fall stellte sich heraus, dass der freie Koeffizient -0.0007 und der Fehler in der Berechnung beträgt $$$t_3$ betrug 0,00135. Somit ist die gefundene Lösung vollständig konsistent.

Die letzte Zeile mit den Koeffizienten:

 3.14172883822 2.71842889253 3.999957864335599 

Wenn wir es als Antwort auf das Problem einsetzen, erhalten wir das wohlverdiente OK!

Da der gewünschte Wert $$$F_1$ -Maßnahmen sind nicht zu groß, sicher ist eine ziemlich einfache Methode zur Lösung des Problems geeignet. Also habe ich versucht, CatBoost nur mit den bereitgestellten Faktoren auszuführen und dann seine Vorhersagen zu binarisieren.

Damit CatBoost funktioniert, müssen Sie zwei Dateien bereitstellen: Training und Test sowie Spaltenbeschreibungen. Die Beschreibung der Spalten ist einfach zu kompilieren: Die ersten beiden Spalten sind der Anforderungstext und der Zeitstempel. Es ist einfacher, sie zu ignorieren. Die letzte Spalte ist die Antwort. Daher erhalten wir die folgende Beschreibung der Spalten :

 0 Auxiliary 1 Auxiliary 8 Target 

Da die Testdatei keine Antworten und damit die letzte Spalte enthält, fügen wir diese Spalte hinzu, indem wir sie einfach mit Nullen füllen. Ich benutze dafür das übliche awk:

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

Jetzt können Sie CatBoostL trainieren

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

Danach befinden sich die Vorhersagen in der Datei output.tsv . Dies sind jedoch wesentliche Vorhersagen, die noch binärisiert werden müssen.

Wir gehen davon aus, dass der Anteil positiver Beispiele in den Trainings- und Testmustern übereinstimmt. Im Schulungsbeispiel enthalten etwa 3/4 aller Abfragen Klicks auf aktuelle Dokumente. Daher wählen wir den Klassifizierungsschwellenwert so, dass ungefähr 3/4 aller Anforderungen aus der Testprobe positive Vorhersagen enthalten. Für einen Schwellenwert von 0,04 gibt es beispielsweise 178925 von 200.000.

Daher bilden wir die Lösungsdatei wie folgt:

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

Hier musste die erste Zeile übersprungen werden, weil CatBoost schreibt seine eigenen Spaltennamen hinein.

Die so erhaltene Datei solution.tsv wird an das Verifizierungssystem gesendet und erhält als Urteil ein legitimes OK.

Wie Sie wissen, gibt es eine Vielzahl von Methoden zur Auswahl von Merkmalen.

Sie können beispielsweise eine vorgefertigte Methode verwenden. Angenommen, ich habe versucht, die Funktionsauswahl in Weka auszuführen, und nach einigem Einstellen der Parameter gelang es mir, bei dieser Aufgabe 1,8 Punkte zu erzielen.

Außerdem habe ich ein eigenes Skript zur Auswahl von Funktionen. Dieses Skript implementiert eine gierige Strategie: Jedes Mal wird der Stichprobe genau ein Faktor hinzugefügt, sodass das bestmögliche Hinzufügen die Schätzung der Bewegungssteuerung für den Algorithmus beeinflusst. Im Rahmen des Wettbewerbs dauert das Ausführen eines solchen Skripts jedoch entweder zu lange oder ein großer Computercluster.

Wenn Sie jedoch wichtige Wälder mit Regularisierung verwenden (einschließlich CatBoost), gibt es auch eine extrem schnelle Methode zur Auswahl von Merkmalen: Sie müssen die Faktoren auswählen, die häufig im Modell verwendet werden. Der CatBoost-Algorithmus verfügt über einen integrierten Modus zur Bewertung des Einflusses von Faktoren auf Modellvorhersagen. Wir werden ihn verwenden.

Zuerst müssen Sie das Modell trainieren:

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

Führen Sie dann eine Funktionsbewertung durch:

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

Die Wichtigkeit der Merkmale wird dann in die Datei feature_strength.tsv . In der ersten Spalte wird die Bedeutung der Zeichen aufgezeichnet, in der zweiten Spalte ihre Namen. Die Datei wird sofort nach nicht zunehmender Bedeutung der Funktionen sortiert.

 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 

Es bleibt nur, die ersten paar Dutzend Zeichen zu nehmen und eine Antwort zu bilden. Darüber hinaus ist es sinnvoll, so wenig Funktionen wie möglich zu verwenden. Wie Sie wissen, wirkt sich die Komplexität der Modelle negativ auf ihre Generalisierungsfähigkeit aus.

Wenn Sie beispielsweise die 50 besten Zeichen auswählen, erhalten Sie bei einem öffentlichen Testsatz 3,6 Punkte. Wenn Sie die Top 40, Top 30 oder Top 20 wählen, erhalten Sie genau 4 Punkte. Daher habe ich die Top-20-Zeichen als Lösung ausgewählt - diese Lösung erhielt 4 Punkte in einer geschlossenen Testsuite.

Am Ende ist anzumerken, dass die betrachtete Methode zur Auswahl von Merkmalen nicht in allen Situationen optimal ist. Oft haben „schädliche“ Merkmale einen signifikanten Einfluss auf die Größe der Modellvorhersage, verschlechtern jedoch gleichzeitig die Generalisierungsfähigkeit der Algorithmen. Wenn das Problem der Auswahl von Merkmalen auftritt, lohnt es sich daher, bei jeder Aufgabe mehrere dem Forscher bekannte Ansätze gleichzeitig zu überprüfen und die besten auszuwählen.

Darüber hinaus müssen Sie sich andere Möglichkeiten merken, um die Dimension des Feature-Space zu verringern. Beispielsweise gibt es eine Vielzahl von Methoden zum Extrahieren von Features .