ML-Blitz: Análise das tarefas da primeira pré-eliminatória

Portanto, precisamos construir uma aproximação por partes de uma função conhecida. Se o parâmetro $$$c$ conhecido, em seguida, encontre os parâmetros $$$a$ e $$$b$ simples o suficiente. Você pode escrever soluções matematicamente como soluções para os problemas de otimização correspondentes. Parâmetro $$$a$ É a magnitude das previsões do coto decisivo para esses objetos $$$(x_i, y_i)$ amostra de treinamento para a qual $$$x_i <c$ . Da mesma forma $$$b$ A magnitude das previsões nesses objetos $$$(x_i, y_i)$ amostra de treinamento para a qual $$$x_i \ ge c$ .

Introduzimos a notação para os subconjuntos correspondentes do conjunto de treinamento: $$$L (c)$ É um subconjunto de objetos à esquerda de um ponto $$$c$ , $$$R (c)$ - o subconjunto de objetos à direita do ponto $$$c$ .

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

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

Então o valor ideal $$$a$ será igual à média aritmética das respostas no conjunto $$$L (c)$ e o valor ideal $$$b$ - respectivamente, a média aritmética das respostas no conjunto $$$R (c)$ .

Então agora está claro como encontrar os parâmetros $$$a$ e $$$b$ com um parâmetro conhecido $$$c$ . Resta entender como encontrar o valor ideal do parâmetro $$$c$ .

A primeira coisa a notar: parâmetro $$$c$ pode assumir valores reais, mas muitas partições diferentes são finitas. Amostra de aprendizagem de $$$n$ objetos podem ser quebrados não mais do que $$$n + 1$ caminhos para as partes "esquerda" e "direita". Na realidade, pode haver ainda menos partições desse tipo: por exemplo, para alguns objetos, os valores dos atributos podem coincidir. Além disso, as partições são equivalentes para nós, nas quais todos os objetos no conjunto de treinamento estão à esquerda ou à direita.

Para obter todas as partições possíveis, você pode classificar os objetos do conjunto de treinamento por atributo não decrescente:

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

Agora está claro que os valores de parâmetros potencialmente interessantes $$$c$ São as quantidades

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

Agora está claro o que precisa ser feito para obter uma solução. É necessário classificar todos os valores de parâmetros potencialmente interessantes $$$c$ , para cada um deles determinar as quantidades correspondentes $$$a$ e $$$b$ , bem como o valor da perda funcional. Então você precisa selecionar um conjunto de parâmetros correspondentes ao mínimo dos valores funcionais da perda.

Tudo o que resta é a questão de como tornar essa solução eficaz. A implementação direta do algoritmo descrito levará à complexidade quadrática do algoritmo, o que é inaceitável.

Para efetivar os cálculos, lembre-se de que para encontrar os parâmetros $$$a$ e $$$b$ é necessário apenas calcular os valores médios no conjunto. Quando você adiciona outro elemento ao conjunto (ou após remover um elemento do conjunto), o valor médio pode ser efetivamente calculado para tempo constante se você não armazenar a média em si, mas separadamente a soma dos valores e seu número separadamente. A situação é semelhante à soma dos desvios ao quadrado. Para calculá-lo, de acordo com a fórmula conhecida para calcular a variação , é possível armazenar separadamente a soma das quantidades e a soma dos quadrados das quantidades. Além disso, você pode usar qualquer método de cálculo online . Eu já escrevi sobre isso em um hub

Na implementação, usarei o método Wellford, como Gosto mais do que cálculos usando fórmulas "padrão". Além disso, não usarei o numpy e nenhuma outra biblioteca para demonstrar que o conhecimento das construções elementares da linguagem python é suficiente para obter uma solução.

Portanto, precisamos ser capazes de calcular incrementalmente a média e a soma dos desvios ao quadrado. Para fazer isso, descrevemos duas 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) 

Agora precisamos de uma aula para armazenar e processar o conjunto de treinamento. Primeiro, descrevemos seus campos e 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() 

Simultaneamente com a entrada de dados, formamos imediatamente a estrutura SumSquaredErrorsCalculator para todos os objetos na seleção. Depois de carregar a amostra inteira, classificamos por valores de atributo não decrescentes.

Agora, o mais interessante: o método para encontrar os valores ideais dos parâmetros.

Vamos começar com a inicialização. No estado inicial, todos os objetos estão na subamostra correta. Então o parâmetro $$$a$ pode ser igual a qualquer coisa, parâmetro $$$b$ igual à resposta média em toda a amostra e o parâmetro $$$c$ de modo que todos os objetos na seleção estejam à direita dele.

Além disso, inicializamos as variáveis left e right - elas armazenam estatísticas para as subamostras esquerda e direita, respectivamente.

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

Agora vamos ao algoritmo incremental. Processaremos os elementos de seleção um de cada vez. Cada elemento é transferido para o subconjunto esquerdo. Então você precisa verificar se a partição correspondente realmente existe - ou seja, o valor da característica é diferente do valor da característica do próximo 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 

Agora resta apenas compor o código para obter uma solução:

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

Observo que a solução apresentada em python é realmente aceita pelo sistema, mas chega ao limite superior no tempo da solução: os maiores testes requerem cerca de 800 milissegundos para serem executados. Obviamente, o uso de bibliotecas adicionais pode obter um desempenho muito mais impressionante.

Portanto, eu também implementei o algoritmo proposto em C ++ . Essa solução passou no pior dos casos 60 milissegundos em um dos testes.

Expanda os colchetes, ignorando as variáveis ​​aleatórias:

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

Agora temos o problema de regressão linear multidimensional sem um coeficiente livre. As características deste problema são as quantidades $$$\ sin ^ 2 (x)$ , $$$\ ln ^ 2 (x)$ , $$$\ sin (x) \ cdot \ ln (x)$ , $$$x ^ 2$ .

Como a dependência funcional não implica um coeficiente livre e todos os componentes aleatórios têm média zero, pode-se esperar que o coeficiente livre seja praticamente zero ao treinar o modelo. No entanto, vale a pena verificar isso antes de enviar a solução.

Ao resolver o problema da regressão linear multidimensional, alguns coeficientes serão encontrados com recursos modificados. De fato, a seguinte representação será encontrada para a função $$$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$$

Depois disso, você pode encontrar os coeficientes $$$a$ , $$$b$ , $$$c$ :

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

Além disso, vale a pena verificar que $$$2 \ cdot a \ cdot b \ aproximadamente t_3$

Para começar, você deve ler os dados e formar os sinais:

 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) 

Agora é necessário resolver o problema da regressão linear multidimensional. Existem várias maneiras de fazer isso - desde ferramentas como Weka e funções da biblioteca sklearn até minha própria implementação . No entanto, nesse caso, eu queria obter uma solução "fechada": um script que resolva completamente o problema. Portanto, eu usei o 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 

Nesse caso, verificou-se que o coeficiente livre é -0.0007 e o erro no cálculo $$$t_3$ foi de 0,00135. Assim, a solução encontrada é completamente consistente.

A linha final com os coeficientes:

 3.14172883822 2.71842889253 3.999957864335599 

Substituindo-o como a resposta para o problema, obtemos o merecido OK!

Desde o valor requerido $$$F_1$ - as medidas não são muito grandes, com certeza algum método bastante simples será adequado para resolver o problema. Então, tentei apenas executar o CatBoost nos fatores fornecidos e depois binarizar suas previsões.

Para o CatBoost funcionar, você precisa fornecer dois arquivos: treinamento e teste, além de descrições de coluna. A descrição das colunas é fácil de compilar: as duas primeiras colunas são o texto da solicitação e o carimbo de data / hora, é mais fácil ignorá-las. A última coluna é a resposta. Portanto, obtemos a seguinte descrição das colunas :

 0 Auxiliary 1 Auxiliary 8 Target 

Como o arquivo de teste não contém respostas e, portanto, a última coluna, adicionamos essa coluna simplesmente preenchendo-a com zeros. Eu uso o habitual awk para isso:

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

Agora você pode treinar o CatBoostL

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

Depois disso, as previsões estarão no arquivo output.tsv . No entanto, essas serão previsões materiais que ainda precisam ser binarizadas.

Vamos prosseguir com o fato de que a parcela de exemplos positivos nas amostras de treinamento e teste coincide. Na amostra de treinamento, cerca de 3/4 de todas as consultas contêm cliques em documentos recentes. Portanto, selecionamos o limite de classificação para que aproximadamente 3/4 de todas as solicitações da amostra de teste apresentem previsões positivas. Por exemplo, para um limite de 0,04, existem 178925 de 200.000.

Portanto, formamos o arquivo de solução da seguinte maneira:

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

Aqui foi necessário pular a primeira linha, porque O CatBoost escreve seus próprios nomes de coluna nele.

O arquivo solution.tsv assim obtido é enviado ao sistema de verificação e recebe um OK legítimo como um veredicto.

Como você sabe, existe uma grande variedade de métodos para selecionar características.

Por exemplo, você pode usar algum método pronto. Digamos que tentei executar a seleção de recursos no Weka e, depois de um pequeno ajuste nos parâmetros, consegui obter 1,8 pontos nesta tarefa.

Além disso, tenho meu próprio script para selecionar recursos. Esse script implementa uma estratégia gananciosa: exatamente um fator é adicionado à amostra de cada vez, de forma que a adição da melhor maneira afete a estimativa do controle móvel do algoritmo. No entanto, no contexto do concurso, a execução de um script levará muito tempo ou um grande cluster de computação.

No entanto, ao usar florestas cruciais com regularização (incluindo o CatBoost), também existe um método extremamente rápido para selecionar características: você deve selecionar os fatores que costumam ser usados ​​no modelo. O algoritmo CatBoost possui um modo interno para avaliar a influência de fatores nas previsões do modelo, e nós o usaremos.

Primeiro você precisa treinar o modelo:

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

Em seguida, execute uma avaliação de recurso:

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

A importância das características será gravada no arquivo feature_strength.tsv . Na primeira coluna, o significado dos sinais será registrado, na segunda - seus nomes. O arquivo é classificado imediatamente pela importância crescente dos recursos.

 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 

Resta apenas receber as primeiras dezenas de sinais e formar uma resposta. Além disso, faz sentido usar o menor número possível de recursos - como você sabe, a complexidade dos modelos afeta negativamente sua capacidade de generalização.

Digamos, se você selecionar os 50 principais sinais, em um teste público você poderá obter 3,6 pontos; se você escolher o top 40, o top 30 ou o top 20, receberá exatamente 4 pontos. Portanto, escolhi os 20 principais sinais como solução - essa solução recebeu 4 pontos em um conjunto de testes fechado.

Vale a pena notar, no final, que o método considerado de seleção de recursos não é ideal em todas as situações. Frequentemente, os recursos "prejudiciais" têm um efeito significativo na magnitude da previsão do modelo, mas ao mesmo tempo pioram a capacidade de generalização dos algoritmos. Portanto, em cada tarefa, quando surgir o problema de selecionar recursos, vale a pena verificar várias abordagens conhecidas ao pesquisador de uma só vez e escolher a melhor.

Além disso, você precisa se lembrar de outras maneiras de reduzir a dimensão do espaço do recurso - por exemplo, há uma grande variedade de métodos para extrair recursos .