2010年12月5日,星期日

成本敏感的最佳M的SFF树

约翰·兰福德 最近向我发送了一个有用的建议。
另一种方法是引入代表性的hack。假设我们将成对分类器定义为:$ w_ {left} x_ {left}-w_ {right} x_ {right} $。然后,过滤树的输出为$ \ underset {a} {\ operatorname {arg \,max \,}} w_a x_a $,其形式与回归相同。但是,我们以不同的方式训练事物,以实现较低的后悔$ \ ldots $
与该建议相关的探索方向很多。这是我的一些曲折。

SFF树:定义

我将此建议称为计分没收过滤器(SFF)树。类比是当使用评分功能定义线性排序以减少对分类的排名时。这是一个更精确的定义。
定义: SFF树
SFF树是 没收过滤树 $\Psi$ where 在 each internal node $\nu$ the importance-weighted classifier is of the form \[ \Psi_\nu (x) = 1_{f (x; \lambda) > f (x; \phi)}
\]其中$ \ lambda $和$ \ phi $是输入到$ \ nu $的两个类(分别是左和右子树的预测)。函数$ f $称为计分函数,并且在每个内部节点处都相同(但对于每个操作而言都不同)。

John的建议的妙处在于,可以在测试时通过$ h ^ \ Psi(x,\ omega)= \ underset {k \ in K \ setminus \ omega} {\ operatorname {arg \,max \,}} f(x; k)$看起来就像如何计算输出以进行回归归约。但是后悔的界限更好,因为训练的过程是不同的。

SFF树 平均约束CSMC

由于SFF树是没用的过滤树,因此 后悔 上的“没收过滤器”树 平均约束CSMC 问题成立,即\ [r_ {av}(h ^ \ Psi)\ leq(| K |-1)q(\ Psi),\]其中$ q(\ Psi)$是重要性加权二元遗憾引起的子问题。这与 回归遗憾 ,\ [r_ {av}(h_g)\ leq \ sqrt {2 | K | \ epsilon_ {L ^ 2}(g)},\]其中$ \ epsilon_ {L ^ 2}(g)$是基础回归问题的损失$ L ^ 2 $。

因此,一开始这似乎很神奇(即,可以将其视为获得更好的回归指标的一种方法),但是我将其理解为训练过程,将子问题预言集中在重要的问题上(例如,区分best和$ 2 ^ \ mathrm { nd} $每个实例的最佳操作),而忽略不存在的问题(例如,准确估计$(n-1)^ \ mathrm {th} $和$ n ^ \ mathrm {th} $最差的选择的值)。

在实践中,强制SFF树中的分类器基于评分函数可能会导致难以学习对诱导子问题的低遗憾解决方案。评分函数在所有内部节点上共享的事实是简化输出计算的关键,但与普通的没收树不同。在原始情况下,很容易设想通过$ \ log_2(| K |)$顺序遍历以从下到上的方式训练树,每次遍历定义内部节点的下一级别的训练数据,并且每次遍历在特定深度训练一组内部节点。但是,现在不同级别的分类器是交织在一起的。

我实际上不确定如何处理这个问题,并且直到尝试尝试时我才知道。凭直觉,如果我要在线上逐步更新热模型,我会尝试忽略依赖关系,而仅应用更新。动机是我每次更新都会进行微小的更改,所以我忽略的是``高阶微小''。当然,决策边界处的大量非线性有点令人不安(并且不是很小)。从冷开始但仍使用在线学习算法(针对脱机数据),我尝试从下到上的方式通过$ \ log_2(| K |)$,在一定深度前热启动整个树在下一个更高的深度训练任何内部节点。与普通情况不同,每次通过都会训练所有内部节点达到一定深度,而不仅仅是训练特定深度的内部节点。希望能奏效,但如果失败了,我会考虑使用softmax风格的方法来减轻决策边界的非线性,例如$ p(\ Psi_ \ nu = 1 | x)= 1 /(1 + e ^ {-\ beta(f(x; \ lambda)-f(x; \ psi))})$并将$ \ beta $退火为$ \ infty $。

SFF树 平均约束CSBM

平均约束CSBM 是在给定实例的情况下选择前$ m $个操作的问题。通过构造分类器列表$ \ {\ Psi_n | |,可以将其减少到受约束的平均CSMC。 n \ in [1,m] \} $每个都经过训练,以选择最佳动作,下一个最佳动作等。

所以这是一个有趣的事情:如果我们在分类器列表中设置$ \ Psi_n = \ Psi $,并且如果我们的平均约束CSMC分类器是SFF树,那么我们可以通过\ [h ^ \ Psi(x, \ omega)= \ underset {k \ in K \ setminus \ omega} {\ operatorname {arg \,max \,^ m}} f(x; k),\]在这里我用符号$ \ operatorname {arg \,max \,^ m} $代表选择前$ m $个元素。同样,这正是在测试时将采用基于回归约简的方法的方式。但是遗憾的界限还是不同的。当将平均约束CSBM减小为平均约束CSMC时, 后悔 是\ [r_ {csbm}(h ^ \ Psi)\ leq m \,q(\ Psi,m),\]其中$ q(\ Psi,m)$是对$ m $的平均成本敏感后悔平均约束CSMC子问题(这些问题又可以简化为重要性加权分类,从而保持对后悔的线性依赖)。相反,当简化为回归 后悔 是\ [r_ {csbm}(h_g)\ leq \ sqrt {2 \ min \ {m,| K | -m \}} \ sqrt {| K |} \ sqrt {\ epsilon_ {L ^ 2}(g)},\]其中$ \ epsilon_ {L ^ 2}(g)$是$ L ^ 2 $的损失关于潜在的回归问题。

因此,我们再次保证可以采用不同的训练程序来获得更好的回归值,但是子问题之间的依存关系也存在类似的问题,使训练画面复杂化。在将CSBM简化为CSMC的典型情况下,每个分类器将按顺序进行训练,并为下一个分类器定义训练输入分布。现在所有分类器都相同,因此需要一些技巧。

再说一次,我实际上不确定如何处理这个问题,直到尝试了一些事情,我才知道。凭直觉,我将再次尝试在线上逐步更新热模型,而忽略依赖关系。对于将离线模型应用于在线模型的冷启动,我将首先针对top-1问题,然后针对top-2问题进行培训,直到达到top- $ m $。有趣的是,如何看待我的两个直观过程的组成如何进行完整的冷启动:
  1. 对于$ n $ in $ [1,m] $
    1. 为$ l $ in $ [\ log_2(| K |),1] $
      1. 更新$ l ^ \ mathrm {th} $和更低级别的内部节点,以解决同时选择顶部$ n $动作的问题
      2. 更新$ l ^ \ mathrm {th} + 1 $和更高级别的内部节点,以解决选择前$(n-1)$个操作的问题。
总共$ m \ log_2(| K |)$通过了数据,这很合理。外循环用于减轻由$ \ Psi_n = \ Psi $创建的依赖关系,而内循环用于减轻在所有内部节点之间共享$ f $所创建的依赖关系。

现在,我想我应该在一些实际数据上尝试一下。

没意见:

发表评论