💅🏽 🕗 👨🏽‍🍳 ML-Blitz: análisis de las tareas de la primera ronda de clasificación ⭕️ 👨‍👩‍👧‍👧 👩🏾‍🤝‍👩🏼

El 23 de junio de 2018, se llevó a cabo la final del ML-Blitz, un concurso de aprendizaje automático organizado por Yandex. Anteriormente lo anunciamos en Habré y le dijimos qué aproximadamente las tareas pueden cumplir en una competencia real.

Ahora queremos compartir con ustedes el análisis de las tareas de una de las rondas de calificación: la primera. Dos participantes lograron resolver todos los problemas de esta competencia; 57 participantes resolvieron al menos una tarea, y 110 completaron al menos un intento de aprobar la tarea.

Aunque el autor de estas líneas participó en la elaboración de las tareas de la competencia, fue en la primera calificación que sus tareas no participaron. Así que escribo este análisis desde la perspectiva de un concursante que vio por primera vez las condiciones y quiso obtener tantos puntos como sea posible lo más rápido posible.

El lenguaje de programación más popular entre los concursantes era python, por lo que también utilicé este lenguaje en todos los casos en que era necesario escribir código.

Todas mis soluciones están disponibles en GitHub.

Problema A. Tocón decisivo

Desafío
Solución Python
Solución C ++

Tocón decisivo es una de las funciones decisivas más simples en el aprendizaje automático. Esta es una función constante por partes definida de la siguiente manera:

f (x) = \ left \ {\ begin {array} {ll} a, & \ quad x <c \\ b, & \ quad x \ ge c \ end {array} \ right. $

$f (x) = \ left \ {\ begin {array} {ll} a, & \ quad x <c \\ b, & \ quad x \ ge c \ end {array} \ right. $$

En este problema, fue necesario construir un tocón de decisión óptimo para la muestra de entrenamiento. Es decir, de acuerdo con pares de números dados $(x_1, y_1), \ ldots, (x_n, y_n)$ , fue necesario determinar los valores óptimos de los parámetros del muñón decisivo para optimizar los valores de la pérdida cuadrática funcional

Q (f, x, y) = s u m_{i = 1}^{n} (f (x_{i}) - y_{i})^{2}

$Q (f, x, y) = \ sum_ {i = 1} ^ {n} (f (x_i) - y_i) ^ 2$

Era necesario derivar los valores óptimos como respuesta $a, b, c$ .

Solución

Por lo tanto, necesitamos construir una aproximación suave por partes de una función conocida. Si el parámetro $c$ conocido entonces encontrar los parámetros $a$ y $b$ lo suficientemente simple Puede escribir soluciones matemáticamente como soluciones a los problemas de optimización correspondientes. Parámetro $a$ Es la magnitud de las predicciones del tocón decisivo en esos objetos. $(x_i, y_i)$ muestra de entrenamiento para la cual $x_i <c$ . De manera similar $b$ Es la magnitud de las predicciones en esos objetos. $(x_i, y_i)$ muestra de entrenamiento para la cual $x_i \ ge c$ .

Introducimos la notación para los subconjuntos correspondientes del conjunto de entrenamiento: $L (c)$ Es un subconjunto de objetos a la izquierda de un punto. $c$ , $R (c)$ - el subconjunto de objetos a la derecha del punto $c$ .

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

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

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

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

Entonces el valor óptimo $a$ será igual a la media aritmética de las respuestas en el conjunto $L (c)$ y el valor óptimo $b$ - respectivamente, la media aritmética de las respuestas en el conjunto $R (c)$ .

Se puede justificar de la siguiente manera

a = a r g m i n_{t i n m a t h b b R} s u m_{(x_{i}, y_{i}) i n L (c)} (t - y_{i})^{2}

$a = \ arg \ min_ {t \ in \ mathbb {R}} {\ sum _ {(x_i, y_i) \ in L (c)} (t - y_i) ^ 2}$

b = a r g m i n_{t i n m a t h b b R} s u m_{(x_{i}, y_{i}) i n R (c)} (t - y_{i})^{2}

$b = \ arg \ min_ {t \ in \ mathbb {R}} {\ sum _ {(x_i, y_i) \ in R (c)} (t - y_i) ^ 2}$

Es bien sabido que la respuesta en tales problemas de optimización es la media aritmética:

a = f r a c s u m_{(x_{i}, y_{i}) e n L (c)} y_{i} | L (c) |

$a = \ frac {\ sum _ {(x_i, y_i) \ en L (c)} y_i} {| L (c) |}$

b = f r a c s u m_{(x_{i}, y_{i}) e n R (c)} y_{i} | L (c) |

$b = \ frac {\ sum _ {(x_i, y_i) \ en R (c)} y_i} {| L (c) |}$

Esto es bastante fácil de probar. Tome la derivada parcial de la pérdida funcional con respecto al valor de predicción:

f r a c p a r t i a l p a r t i a l t s u m_{y e n Y} (t - y)^{2} = 2 c d o t s u m_{y e n Y} (t - y) = 2 c d o t | Y | c d o t t - 2 c d o t s u m_{y e n Y} y

$\ frac {\ partial} {\ partial t} \ sum_ {y \ en Y} {(t - y) ^ 2} = 2 \ cdot \ sum_ {y \ en Y} {(t - y)} = 2 \ cdot | Y | \ cdot t - 2 \ cdot \ sum_ {y \ en Y} {y}$

Después de igualar la derivada a cero, obtenemos

t = f r a c 1 | Y | s u m_{y e n Y} y

$t = \ frac {1} {| Y |} \ sum_ {y \ en Y} y$

Igualar la derivada a cero en este caso es correcto, porque la función optimizada es una función convexa , y para las funciones convexas, los puntos del extremo local están garantizados como puntos del extremo global.

Así que ahora está claro cómo encontrar los parámetros $a$ y $b$ con un parámetro conocido $c$ . Queda por entender cómo encontrar el valor óptimo del parámetro. $c$ .

Lo primero que debe notar: parámetro $c$ puede tomar cualquier valor real, pero muchas particiones diferentes son finitas. Muestra de aprendizaje de $n$ los objetos no pueden romperse más de $n + 1$ maneras de las partes "izquierda" y "derecha". En realidad, puede haber incluso menos particiones de este tipo: por ejemplo, para algunos objetos, los valores de los atributos pueden coincidir. Además, las particiones son equivalentes para nosotros, en las que todos los objetos del conjunto de entrenamiento están a la izquierda o a la derecha.

Para obtener todas las particiones posibles, puede ordenar los objetos del conjunto de entrenamiento por atributo no decreciente:

(x_{i_{1}}, y_{i_{1}}), l d o t s (x_{i_{n}}, y_{i_{n}})

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

x_{i_{1}} l e x_{i_{2}} l e l d o t s l e x_{i_{n}}

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

Ahora está claro que los valores de parámetros potencialmente interesantes $c$ Son las cantidades

f r a c x_{i_{1}} + x_{i_{2}} 2, f r a c x_{i_{2}} + x_{i_{3}} 2, l d o t s, f r a c x_{i_{n - 1}} + x_{i_{n}} 2

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

Ahora está claro lo que hay que hacer para obtener una solución. Es necesario ordenar todos los valores de parámetros potencialmente interesantes $c$ , para cada uno de ellos determinar las cantidades correspondientes $a$ y $b$ , así como el valor de la pérdida funcional. Luego, debe seleccionar un conjunto de parámetros que correspondan al mínimo de los valores funcionales de pérdida.

Todo lo que queda es la cuestión de cómo hacer que esta solución sea efectiva. La implementación directa del algoritmo descrito conducirá a una complejidad cuadrática del algoritmo, lo cual es inaceptable.

Para que los cálculos sean efectivos, recuerde que para encontrar los parámetros $a$ y $b$ solo es necesario calcular los valores promedio sobre el conjunto. Cuando agrega el siguiente elemento al conjunto (o después de eliminar el elemento del conjunto), el valor promedio se puede calcular efectivamente para un tiempo constante si no almacena el promedio en sí, sino por separado la suma de los valores y su número por separado. La situación es similar con la suma de las desviaciones al cuadrado. Para calcularlo, de acuerdo con la conocida fórmula para calcular la varianza , puede almacenar por separado la suma de las cantidades y la suma de los cuadrados de las cantidades. Además, puede usar cualquier método de cálculo en línea . Anteriormente ya escribí sobre eso en un centro

Implementación

En la implementación, usaré el método Wellford, como Me gusta más que los cálculos con fórmulas "estándar". Además, no usaré numpy y ninguna otra biblioteca para demostrar que el conocimiento de las construcciones elementales del lenguaje python es suficiente para obtener una solución.

Entonces, necesitamos poder calcular incrementalmente el promedio y la suma de las desviaciones al cuadrado. Para hacer esto, describimos dos clases:

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)

Ahora necesitamos una clase para almacenar y procesar el conjunto de entrenamiento. Primero, describimos sus campos y método de entrada:

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

Simultáneamente con la entrada de datos, formamos inmediatamente la estructura SumSquaredErrorsCalculator para todos los objetos de la selección. Después de cargar toda la muestra, la ordenamos por valores de atributo no decrecientes.

Ahora lo más interesante: el método para encontrar los valores óptimos de los parámetros.

Comencemos con la inicialización. En el estado inicial, todos los objetos están en la submuestra correcta. Entonces el parámetro $a$ puede ser igual a cualquier cosa, parámetro $b$ igual a la respuesta promedio en toda la muestra, y el parámetro $c$ de modo que todos los objetos en la selección estén a la derecha de la misma.

Además, inicializamos las variables left y right : almacenarán estadísticas para las submuestras izquierda y derecha, respectivamente.

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

Ahora pasemos al algoritmo incremental. Procesaremos los elementos de selección uno a la vez. Cada elemento se transfiere al subconjunto izquierdo. Luego, debe verificar que la partición correspondiente realmente existe, es decir, el valor de la característica es diferente del valor de la característica del siguiente objeto.

 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

Ahora solo queda componer el código para obtener una solución:

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

Observo que la solución presentada en Python es efectivamente aceptada por el sistema, pero llega al límite superior en el tiempo de la solución: las pruebas más grandes requieren aproximadamente 800 milisegundos para ejecutarse. Por supuesto, el uso de bibliotecas adicionales puede lograr un rendimiento mucho más impresionante.

Por lo tanto, también implementé el algoritmo propuesto en C ++ . Esta solución pasó en el peor de los casos 60 milisegundos en una de las pruebas.

Problema B. Recuperación de coeficientes.

Desafío
Solución Python usando sklearn

Necesito restaurar la configuración $a$ , $b$ , $c$ las funciones $f$ tener un conjunto de parejas famosas $(x_1, f (x_1)),$ $\ ldots,$ $(x_n, f (x_n))$ y sabiendo que los valores de la función están determinados por la siguiente fórmula:

f (x) = B i g ((a + v a r e p s i l o n_{a}) s i n x + (b + v a r e p s i l o n_{b}) l n x B i g)^{2} + (c + v a r e p s i l o n_{c}) x^{2}

$f (x) = \ Big ((a + \ varepsilon_a) \ sin x + (b + \ varepsilon_b) \ ln x \ Big) ^ 2 + (c + \ varepsilon_c) x ^ 2$

Solución

Expanda los corchetes, ignorando las variables aleatorias:

f (x) = a^{2} c d o t s i n^{2} (x) + b^{2} c d o t l n^{2} (x) + 2 a b c d o t s i n (x) c d o t l n (x) + c c d o t x^{2}

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

Ahora tenemos el problema de regresión lineal multidimensional sin un coeficiente libre. Las características de este problema son las cantidades. $\ sin ^ 2 (x)$ , $\ ln ^ 2 (x)$ , $\ sin (x) \ cdot \ ln (x)$ , $x ^ 2$ .

Como la dependencia funcional no implica un coeficiente libre, y todos los componentes aleatorios tienen una media cero, se puede esperar que el coeficiente libre sea prácticamente cero cuando se entrena el modelo. Sin embargo, vale la pena verificar esto antes de enviar la solución.

Al resolver el problema de la regresión lineal multidimensional, se encontrarán algunos coeficientes con características modificadas. De hecho, se encontrará la siguiente representación para la función $f$ :

f (x) = t_{1} c d o t s i n^{2} (x) + t_{2} c d o t l n^{2} (x) + t_{3} c d o t s i n (x) c d o t l n (x) + t_{4} c d o t x^{2} $

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

Después de eso, puedes encontrar los coeficientes $a$ , $b$ , $c$ :

a = s q r t (t_{1}), b = s q r t (t_{2}), c = t_{4}

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

Además, vale la pena verificar que $2 \ cdot a \ cdot b \ aprox t_3$

Implementación

Para empezar, debe leer los datos y formar los signos:

 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)

Ahora es necesario resolver el problema de la regresión lineal multidimensional. Hay una gran cantidad de formas de hacerlo, desde herramientas como Weka y funciones de biblioteca sklearn hasta mi propia implementación . Sin embargo, en este caso, quería obtener una solución "cerrada": un script que resuelva completamente el problema. Por lo tanto, solía 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

En este caso, resultó que el coeficiente libre es -0,0007, y el error en el cálculo $t_3$ ascendió a 0.00135. Por lo tanto, la solución encontrada es completamente consistente.

La línea final con los coeficientes:

 3.14172883822 2.71842889253 3.999957864335599

Sustituyéndolo como la respuesta al problema, ¡obtenemos el bien merecido OK!

Tarea C. Detector de frescura

Desafío
Script para obtener una solución usando CatBoost

En este problema, se requería construir un nuevo detector de consultas, con una muestra preparada con los valores de los factores y los valores de la función objetivo. Cada línea del archivo de entrada describió una solicitud. Los factores fueron la frecuencia de las tareas de esta solicitud en el pasado: durante la última hora, dos horas, seis horas, 12, 24, 72 horas. La función objetivo es binaria: si se hizo un clic en un documento nuevo, es uno, de lo contrario es cero.

Se requería mostrar cero o uno para cada línea del archivo de prueba, dependiendo de la predicción. También se requiere para obtener un kit de prueba $F_1$ -medida superior a 0,25.

Solución

Desde el valor requerido $F_1$ -las medidas no son demasiado grandes, seguramente un método bastante simple será adecuado para resolver el problema. Así que intenté simplemente ejecutar CatBoost en los factores proporcionados y luego binarizar sus predicciones.

Para que CatBoost funcione, debe proporcionar dos archivos: capacitación y prueba, así como descripciones de columna. La descripción de las columnas es fácil de compilar: las dos primeras columnas son el texto de solicitud y la marca de tiempo, es más fácil ignorarlas. La última columna es la respuesta. Por lo tanto, obtenemos la siguiente descripción de las columnas :

 0 Auxiliary 1 Auxiliary 8 Target

Como el archivo de prueba no contiene respuestas y, por lo tanto, la última columna, agregamos esta columna simplemente llenándola con ceros. Yo uso el awk habitual para esto:

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

Ahora puedes entrenar a CatBoostL

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

Después de eso, las predicciones estarán en el archivo output.tsv . Sin embargo, estas serán predicciones materiales que aún deben ser binarizadas.

Procederemos del hecho de que la proporción de ejemplos positivos en las muestras de entrenamiento y prueba coincide. En la muestra de capacitación, aproximadamente 3/4 de todas las consultas contienen clics en documentos recientes. Por lo tanto, seleccionamos el umbral de clasificación para que aproximadamente 3/4 de todas las solicitudes de la muestra de prueba tengan predicciones positivas. Por ejemplo, para un umbral de 0.04, hay 178925 de 200,000.

Por lo tanto, formamos el archivo de solución de la siguiente manera:

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

Aquí fue necesario omitir la primera línea, porque CatBoost escribe sus propios nombres de columna en él.

El archivo solution.tsv así obtenido se envía al sistema de verificación y recibe un OK legítimo como veredicto.

Tarea D. Selección de características

Desafío
Script para obtener la solución

En esta tarea, se les pidió a los participantes que seleccionaran no más de 50 características de las 500 disponibles para que el algoritmo CatBoost demostrara la mejor calidad posible en la muestra de prueba.

Solución

Como saben, existe una amplia variedad de métodos para seleccionar rasgos.

Por ejemplo, puede usar algún método listo para usar. Digamos que intenté ejecutar la selección de funciones en Weka y después de un pequeño ajuste de los parámetros logré obtener 1.8 puntos en esta tarea.

Además, tengo mi propio script para seleccionar características. Este script implementa una estrategia codiciosa: se agrega exactamente un factor a la muestra cada vez, de modo que agregarlo de la mejor manera afecta la estimación del control de movimiento para el algoritmo. Sin embargo, en el contexto del concurso, ejecutar un script de este tipo requerirá demasiado tiempo o un gran clúster informático.

Sin embargo, cuando se utilizan bosques cruciales con regularización (que incluye CatBoost), también hay un método extremadamente rápido para seleccionar rasgos: debe seleccionar los factores que se usan con frecuencia en el modelo. El algoritmo CatBoost tiene un modo incorporado para evaluar la influencia de los factores en las predicciones del modelo, y lo utilizaremos.

Primero necesitas entrenar al modelo:

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

Luego ejecute una evaluación de características:

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

La importancia de las características se escribirá en el archivo feature_strength.tsv . En la primera columna, se registrará la importancia de los signos, en la segunda, sus nombres. El archivo se ordena inmediatamente por la importancia no creciente de las características.

 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

Solo queda tomar las primeras docenas de signos y formar una respuesta. Además, tiene sentido tomar la menor cantidad de funciones posible, como saben, la complejidad de los modelos afecta negativamente su capacidad de generalización.

Digamos que si selecciona los 50 signos principales, en un conjunto de prueba pública podría obtener 3.6 puntos; Si eliges los 40 mejores, los 30 mejores o los 20 mejores, obtienes exactamente 4 puntos. Por lo tanto, elegí los 20 signos principales como solución: esta solución recibió 4 puntos en un conjunto de pruebas cerrado.

Vale la pena señalar al final que el método considerado de selección de características no es óptimo en todas las situaciones. A menudo, las características "perjudiciales" tienen un efecto significativo en la magnitud de la predicción del modelo, pero al mismo tiempo empeoran la capacidad de generalización de los algoritmos. Por lo tanto, en cada tarea, cuando surge el problema de seleccionar características, vale la pena verificar varios enfoques conocidos por el investigador a la vez y elegir el mejor.

Además, debe recordar otras formas de reducir la dimensión del espacio de características; por ejemplo, existe una amplia variedad de métodos para extraer características .

ML-Blitz: análisis de las tareas de la primera ronda de clasificación

Problema A. Tocón decisivo

Problema B. Recuperación de coeficientes.

Tarea C. Detector de frescura

Tarea D. Selección de características

More articles: