ML-Blitz：第一轮资格赛的任务分析

因此，我们需要建立一个已知函数的分段平滑近似。 如果参数 $$$c$已知然后找到参数 $$$一$和 $$$b$很简单。 您可以在数学上写解决方案作为相应优化问题的解决方案。 参量 $$$一$这些物体上决定性树桩的预测幅度是多少 $$$（x_i，y_i）$训练样本 $$$x_i <c$。 相似地 $$$b$这些对象的预测幅度是多少 $$$（x_i，y_i）$训练样本 $$$x_i \ ge c$。

我们为训练集的相应子集引入表示法： $$$L（c）$是点左侧的对象的子集 $$$c$， $$$R（c）$-点右边的对象子集 $$$c$。

然后最优值 $$$一$将等于集合中答案的算术平均值 $$$L（c）$和最佳值 $$$b$-分别回答集合中的算术平均值 $$$R（c）$。

所以现在很清楚如何找到参数 $$$一$和 $$$b$具有已知参数 $$$c$。 有待了解如何找到最佳参数值 $$$c$。

首先要注意的是：参数 $$$c$可以采用任何实际值，但是许多不同的分区是有限的。 从中学习样本 $$$n$最多只能破坏物体 $$$n + 1$“左”和“右”部分的方式。 实际上，这样的分区可能更少：例如，对于某些对象，属性的值可能会重合。 此外，分区对我们来说是等效的，其中训练集中的所有对象都在左侧或右侧。

要获取所有可能的分区，您可以按非递减属性对训练集的对象进行排序：

现在很明显，潜在的有趣参数值 $$$c$是数量

现在很清楚需要做什么才能找到解决方案。 有必要对所有可能有趣的参数值进行排序 $$$c$，为它们各自确定相应的数量 $$$一$和 $$$b$，以及损失功能的价值。 然后，您需要选择一组与损耗函数值的最小值相对应的参数。

剩下的就是如何使该解决方案有效的问题。 所描述算法的直接实现将导致算法的二次复杂度，这是不可接受的。

为了使计算有效，请记住要找到参数 $$$一$和 $$$b$只需计算整个集合的平均值。 当您将下一个元素添加到集合中时（或从集合中删除元素后），如果您不存储平均值本身，而是分别存储值的总和及其数量，则可以在恒定时间内有效地计算平均值。 这种情况与偏差平方和之和相似。 要进行计算，可以根据众所周知的方差计算公式，分别存储数量之和和数量平方之和。 此外，您可以使用任何在线计算方法 。 之前我已经在集线器上写过

在实现中，我将使用Wellford方法 我不喜欢使用“标准”公式进行计算。 此外，我不会使用numpy和其他任何库来证明python语言的基本构造知识足以获得解决方案。

因此，我们需要能够递增地计算偏差的平均值和总和。 为此，我们描述了两个类：

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) 

现在我们需要一个类来存储和处理训练集。 首先，我们描述它的字段和输入法：

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

与数据输入同时，我们立即为所选内容中的所有对象形成SumSquaredErrorsCalculator结构。 加载整个样本后，我们按不减属性值对其进行排序。

现在最有趣的是：查找最佳参数值的方法。

让我们从初始化开始。 在初始状态下，所有对象都在正确的子样本中。 然后参数 $$$一$可以等于任何东西，参数 $$$b$等于整个样本的平均响应，参数 $$$c$这样所选内容中的所有对象都在其右侧。

另外，我们初始化right变量-它们将分别存储左右子样本的统计信息。

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

现在让我们继续进行增量算法。 我们将一次处理一个选择元素。 每个元素都转移到左子集。 然后，您需要验证相应分区是否确实存在-也就是说，特征值与下一个对象的特征值不同。

 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 

现在仅需编写代码即可获得解决方案：

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

我注意到，以python提出的解决方案确实已为系统所接受，但它涉及到解决方案时间的上限：最大的测试大约需要800毫秒才能执行。 当然，使用其他库可以实现更出色的性能。

因此，我也用C ++实现了所提出的算法 。 在最坏的情况下，此解决方案在其中一项测试上花费了60毫秒。

展开方括号，忽略随机变量：

现在我们有了没有自由系数的多维线性回归问题。 这个问题的特点是数量 $$$\ sin ^ 2（x）$， $$$\ ln ^ 2（x）$， $$$\ sin（x）\ cdot \ ln（x）$， $$$x ^ 2$。

由于功能依赖性并不意味着自由系数，并且所有随机分量的均值均为零，因此可以预期，训练模型时，自由系数实际上为零。 但是，值得在提交解决方案之前对此进行检查。

解决多维线性回归问题时，会发现某些系数具有经过修改的特征。 实际上，将为该函数找到以下表示形式 $$$f$：

之后，您可以找到系数 $$$一$， $$$b$， $$$c$：

另外，值得检查一下 $$$2 \ cdot a \ cdot b \大约t_3$

首先，您应该阅读数据并形成标志：

 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) 

现在有必要解决多维线性回归问题。 有很多方法可以做到这一点-从Weka和sklearn库函数之类的工具到我自己的实现 。 但是，在这种情况下，我想获得一个“封闭式”解决方案：一个可以完全解决问题的脚本。 因此，我使用了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 

在这种情况下，发现自由系数为-0.0007，并且计算误差 $$$t_3$总计为0.00135。 因此，找到的解决方案是完全一致的。

最后一行系数：

 3.14172883822 2.71842889253 3.999957864335599 

将其替换为问题的答案，我们得到了当之无愧的OK！

既然需要值 $$$F_1$-度量值不会太大，请确保某些相当简单的方法将适合解决该问题。 因此，我尝试仅在提供的因素上运行CatBoost ，然后将其预测二值化。

为了使CatBoost正常工作，您需要提供两个文件：培训和测试以及列说明。 列的说明易于编译：前两列是请求文本和时间戳，更容易忽略它们。 最后一列是答案。 因此，我们得到以下各列的描述 ：

 0 Auxiliary 1 Auxiliary 8 Target 

由于测试文件不包含答案，因此不包含最后一列，因此我们通过简单地用零填充来添加此列。 我为此使用通常的awk：

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

现在您可以训练CatBoostL

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

之后，预测将在文件output.tsv 。 但是，这些将是仍然需要二值化的重大预测。

我们将从这样一个事实出发，即在训练样本和测试样本中阳性样本所占的比例是一致的。 在训练样本中，所有查询中约3/4包含对最近文档的点击。 因此，我们选择分类阈值，以使来自测试样本的所有请求中的大约3/4具有肯定的预测。 例如，对于0.04的阈值，有178925个200,000。

因此，我们形成以下解决方案文件：

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

在这里有必要跳过第一行，因为 CatBoost将自己的列名称写入其中。

如此获得的solution.tsv文件将发送到验证系统，并接收合法的OK作为结论。

如您所知，选择特征有多种方法。

例如，您可以使用一些现成的方法。 假设我尝试在Weka中运行特征选择，并且在对参数进行了一些微调之后，我在该任务中获得了1.8分。

另外，我有自己的脚本来选择功能。 该脚本实现了一种贪婪策略：每次都将一个因子恰好添加到样本中，从而以最佳方式将其添加会影响算法运动控制的估计 。 但是，在竞赛的背景下，运行这样的脚本将花费太多时间或庞大的计算集群。

但是，当使用具有正则化功能的关键森林（包括CatBoost）时，还有一种选择特征的极快方法：您必须选择模型中经常使用的因子。 CatBoost算法具有一个内置模式，用于评估因素对模型预测的影响，我们将使用它。

首先，您需要训练模型：

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

然后运行功能评估：

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

然后，特征的重要性将被写入feature_strength.tsv文件。 在第一列中，符号的含义将被记录，在第二列中-它们的名称将被记录。 该文件将立即按功能的重要性递增顺序进行排序。

 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 

剩下的只是采取最初的几十个迹象并形成答案。 此外，尽可能少地使用功能是有意义的-如您所知，模型的复杂性会对它们的泛化能力产生负面影响。

假设您选择了前50个标志，那么在公开测试集上您将获得3.6分； 如果您选择前40名，前30名或前20名，您将获得4分。 因此，我选择了前20个标志作为解决方案-该解决方案在封闭测试套件中获得4分。

最后值得一提的是，考虑到的特征选择方法并非在所有情况下都是最优的。 通常，“有害”功能会对模型的预测幅度产生重大影响，但同时也会恶化算法的泛化能力。 因此，在每个任务中，当出现选择特征的问题时，有必要立即检查研究人员已知的几种方法并选择最佳方法。

此外，您需要记住其他减少特征空间尺寸的方法-例如，有多种提取特征的方法。