2011年3月30日,星期三

减少过滤树:Perl实现

最近我一直在用以下方法解决多分类问题 誓言 用一个 机器学习减少。理想情况下,我将使用广东11选五开奖号码查提供的减少API在C中对此进行编程。在实践中,广东11选五开奖号码查不断变化。因此,为了隔离自己,我一直将广东11选五开奖号码查视为我通过IPC与之通信的黑匣子。这种方法有一个缺点:我估计如果在广东11选五开奖号码查内实施减少(基于top的输出),我的总吞吐量至少会大4倍。希望John和他们的工作人员将在不久的将来提供稳定的广东11选五开奖号码查减少API。

同时,尽管有点麻烦,但我在这里提出的减少仍然是切实可行的。另外,有时只是看到某种实现可以使这些概念具体化,所以我想在此介绍一下简化的概念。

策略

起点是 过滤树减少 成本敏感的多类分类对重要性加权二元分类的解释。在这种减少中,类别标签被安排为三月疯狂风格的比赛,获胜者扮演获胜者,直到一个类别标签获得胜利:这就是最终的预测。当两个类别标签``相互竞争''时,真正发生的是重要性加权分类器根据关联实例特征$ x $决定谁获胜。

实际上,我使用的是一种特殊的过滤树 评分过滤树。在这里,重要性加权分类器被限制为\ [
\ Psi _ {\ nu}(x)= 1_ {f(x; \ lambda)> f (x; \phi)}.
\]这里的$ \ lambda $和$ \ phi $是两个“互相比赛”的类别标签,以查看谁在锦标赛中晋级。该方程式表示的是:
  1. 有一个函数$ f $,它告诉每个类标签实例具有$ x $的性能。
  2. 更好的类别标签总是胜过其他类别标签。
这意味着根据$ f $,比赛的获胜者是最好的球队。这使得$ f $看起来像是一个得分函数(就像从argmax回归中获得的一样),并且基本上可以在测试时忽略锦标赛的结构。在火车上使用比赛是至关重要的,但是对于在嘈杂的问题(即低后悔)上获得良好的表现至关重要。

实施

我假设我们正在尝试在$ | K | $标签之间进行分类,这些标签由整数$ \ {1,\ ldots,| K | \} $表示。我还将假设输入格式与广东11选五开奖号码查的本机输入格式非常相似,但是使用的是成本向量而不是标签。 \ [
c_1,\ ldots,c_ {| K |} \; \ textrm {importance} \; \ textrm {tag} | \ textrm {namespace} \; \ textrm {功能} \ ldots
\]因此,例如3类问题输入行可能看起来像\ [
0.7,0.2,1.3 \; 0.6 \; \ textrm {idiocracy} | \ textrm {items} \; \ textrm {hotlatte} \; | \ textrm {desires} \; \ textrm {i} \; \ textrm {like} \; \ textrm {money}
\]最好的选择(最低的费用)是2。

测试时间
应用模型比训练模型更容易理解,所以我将从这里开始。在perl中,我将其转换为一组广东11选五开奖号码查输入行,其中每行对应于特定的类标签$ n $,\ [
\; \ textrm {tag} | \ textrm {namespace} n \; \ textrm {功能} \ ldots
\]本质上,成本向量和重要性权重被去除(因为现在没有学习发生),标记被去除(我将单独处理),并且每个命名空间都附加了类标签。由于广东11选五开奖号码查使用第一个字母来标识名称空间,因此对名称空间进行操作的选项(例如-q,-ignore)将继续按预期运行。因此,例如继续上面的示例,我们将生成三行\ [
| \ textrm {items} 1 \; \ textrm {hotlatte} \; | \ textrm {desires} 1 \; \ textrm {i} \; \ textrm {like} \; \ textrm {money} \; | \ _1 \; ķ
\] \ [
| \ textrm {items} 2 \; \ textrm {hotlatte} \; | \ textrm {desires} 2 \ ;; \ textrm {i} \; \ textrm {like} \; \ textrm {money} \; | \ _2 \; ķ
\] \ [
| \ textrm {items} 3 \; \ textrm {hotlatte} \; | \ textrm {desires} 3 \; \ textrm {i} \; \ textrm {like} \; \ textrm {money} \; | \ _3 \; ķ
\]这些行中的每行都输入到广东11选五开奖号码查,并且具有最低广东11选五开奖号码查输出的类别标签被选为比赛的获胜者。命名空间_中的最后一个功能$ k $提供了常量功能的类标签本地化版本,广东11选五开奖号码查在每个示例中默默提供了该功能。

火车时间
在火车上,我基本上是参加比赛的:但是由于我知道实际的花费,所以我根据谁``应该赢了''来更新分类器。更新的重要性权重由刚刚参加比赛的两个团队之间的成本绝对差值确定。因此,对于两个类别标签$ i $和$ j $,将有一个训练输入馈入形式为\ [
1 \; \ omega \; \ textrm {tag} | \ textrm {namespace $ i $:1} \; \ textrm {功能} \ ldots | \ textrm {namespace $ j $:-1} \; \ textrm {功能} \ ldots | \ textrm {\ _ $ i $:-1} \; k \; | \ textrm {\ _ $ j $:-1} \; ķ
\]其中$ \ omega = \ textrm {重要性} * \ mbox {abs}(c_i-c_j)$,即,原始重要性权重由实际成本中的绝对差来衡量。在这里,我利用了在名称空间上提供权重的功能,该权重乘以名称空间中所有功能的权重。 (广东11选五开奖号码查始终提供的那种讨厌的常量功能呢?它仍然存在并且实际上不应该。正确的处理方法是修补广东11选五开奖号码查以接受不提供常量功能的选项。但是我想呈现一些适用于未修补的广东11选五开奖号码查的内容,因此我改为输入另一项训练输入,并将所有取反,以使恒定特征保持接近零。)

当一支球队赢了一场比赛,他们本不应该赢,他们仍然在锦标赛中前进。直观地,分类器需要从比赛中先前犯的错误中恢复过来,所以这是正确的做法。

少了什么东西
以下是我要改进的一些内容:
  1. 在广东11选五开奖号码查内部实现,而不是通过IPC在外部实现。
  2. 在实现中,我根据特定的班级手动设计比赛。自动构建锦标赛会更好。
  3. 有一种简洁的方法来指定稀疏成本向量会很好。例如,当所有错误同样严重时,所需要做的就是正确标签的标识。
  4. 上述策略不适用于铰链损耗,我也不知道为什么(它似乎适用于平方损耗和逻辑损耗)。可能是我在某个地方犯了一个错误。买者自负!

编码

有两部分:
  • 誓言.pm:这封装了与广东11选五开奖号码查的通信。您将需要它来使其正常工作,但主要是无聊的Unix IPC东西。
    • 检测底层vw未能成功启动不是很好(例如,由于尝试加载不存在的模型)。但是,由于挂起,您会注意到这一点。
  • 过滤树:归约实现实际存在的perl脚本。您可以调用它来开始。通常,它与vw本身采用相同的参数,只是将它们传递出去,但有一些例外:
    1. 您必须从标准输入读取数据。我可以截取--data参数并模拟它们,但是我不知道。
    2. 由于前面的语句,您不能使用--passes参数。
    3. 我确实截取了-p参数(用于输出预测),并在归约级别上对此进行了仿真。

您从过滤树看到的输出看起来像来自大众的输出,但事实并非如此。它实际上来自perl脚本,并且被设计为类似于针对多类情况进行适当修改的vw输出。

这是一个示例调用:
% zcat traindata.gz | head -1000 | ./filter-tree --adaptive -l 1 -b 22 --loss_function logistic -f model.users.b22  
average    since       example  example    current  current  current
loss       last        counter   weight      label  predict features
1.000000   1.000000          1      1.0     1.0000   0.0000       16
0.500000   0.000000          2      2.0     1.0000   1.0000       15
0.500000   0.500000          4      4.0     2.0000   1.0000       20
0.375000   0.250000          8      8.0     2.0000   2.0000       19
0.562500   0.750000         16     16.0     5.0000   2.0000       23
0.437500   0.312500         32     32.0     0.0000   1.0000       14
0.281250   0.125000         64     64.0     1.0000   1.0000       16
0.312500   0.343750        128    128.0     0.0000   1.0000       16
0.347656   0.382812        256    256.0     1.0000   1.0000       13
0.322266   0.296875        512    512.0     1.0000   1.0000       20

finished run
number of examples = 1000
weighted examples sum = 1000
average cost-sensitive loss = 0.287
average classification loss = 0.287
best constant for cost-sensitive = 1
best constant cost-sensitive loss = 0.542
best constant for classification = 1
best constant classification loss = 0.542
minimum possible loss = 0.000
confusion matrix
15      1       0       1       0       1       0
77      416     53      23      5       0       1
14      41      281     56      8       3       2
0       0       0       1       0       1       0
0       0       0       0       0       0       0
0       0       0       0       0       0       0
0       0       0       0       0       0       0
-p参数输出制表符分隔的一组列。第一列是预测的类标签,接下来的$ | K | $列是每个类标签的评分函数值,最后一列是实例标签。

通常,源代码(最好)是最好的文档。

过滤树

#! /usr/bin/env perl

use warnings;
use strict;

use 誓言;

$SIG{INT} = sub { die "caught SIGINT"; };

# if this looks stupid it is: these used to be actual class names,
# but i didn't want to release code with the actual class labels that i'm using
use constant {
  ZERO => 0,
  ONE => 1,
  TWO => 2,
  THREE => 3,
  FOUR => 4,
  FIVE => 5,
  SIX => 6, 
};

sub argmin (@)
{
  my (@list) = @_;
  my $argmin = 0;

  foreach my $x (1 .. $#list)
    {
      if ($list[$x] < $list[$argmin])
        {
          $argmin = $x;
        }
    }

  return $argmin;
}

sub tweak_line ($$)
{
  my ($suffix, $rest) = @_;

  $rest =~ s/\|(\S*)/\|${1}${suffix}/g;

  return $rest;
}

sub train_node ($$$$$$$$$)
{
  my ($m, $la, $lb, $pa, $pb, $ca, $cb, $i, $rest) = @_;

  my $argmin = ($ca < $cb) ? -1 : 1;
  my $absdiff = abs ($ca - $cb);

  if ($absdiff > 0)
    {
      chomp $rest;
      my $w = $i * $absdiff;

      my $plusone = 1;
      my $minusone = -1;
      my $chirp = (rand () < 0.5) ? 1 : -1;

      $argmin *= $chirp;
      $plusone *= $chirp;
      $minusone *= $chirp;

      $m->send ("$argmin $w",
                tweak_line ("${la}:$plusone", " |$rest |_ k"),
                tweak_line ("${lb}:$minusone", " |$rest |_ k\n"))->recv ()
      or die "广东11选五开奖号码查 failed to respond";

      $argmin *= -1;
      $plusone *= -1;
      $minusone *= -1;

      $m->send ("$argmin $w",
                tweak_line ("${la}:$plusone", " |$rest |_ k"),
                tweak_line ("${lb}:$minusone", " |$rest |_ k\n"))->recv ()
      or die "广东11选五开奖号码查 failed to respond";
   }

  return $pa - $pb;
}

sub print_update ($$$$$$$$)
{
  my ($total_loss, $since_last, $delta_weight, $example_counter, 
      $example_weight, $current_label, $current_predict, 
      $current_features) = @_;

  printf STDERR "%-10.6f %-10.6f %8lld %8.1f   %s %8.4f %8lu\n",
         $example_weight > 0 ? $total_loss / $example_weight : -1,
         $delta_weight > 0 ? $since_last / $delta_weight : -1,
         $example_counter,
         $example_weight,
         defined ($current_label) ? sprintf ("%8.4f", $current_label) 
                                  : " unknown",
         $current_predict,
         $current_features;
}

#---------------------------------------------------------------------
#                                main                                 
#---------------------------------------------------------------------

srand 69;

my @my_argv;
my $pred_fh;

while (@ARGV)
  {
    my $arg = shift @ARGV;
    last if $arg eq '--';

    if ($arg eq "-p")
      {
        my $pred_file = shift @ARGV or die "-p argument missing";
        $pred_fh = new IO::File $pred_file, "w" or die "$pred_file: $!";
      }
    else
      {
        push @my_argv, $arg;
      }
  }

my $model = new 誓言 join " ", @my_argv;

print STDERR <<EOD;
average    since       example  example    current  current  current
loss       last        counter   weight      label  predict features
EOD

my $total_loss = 0;
my $since_last = 0;
my $example_counter = 0;
my $example_weight = 0;
my $delta_weight = 0;
my $dump_interval = 1;
my @best_constant_loss = map { 0 } (ZERO .. SIX);
my @best_constant_classification_loss = map { 0 } (ZERO .. SIX);
my $minimum_possible_loss = 0;
my $classification_loss = 0;
my $mismatch = 0;
my %confusion;

while (defined ($_ = <>))
  {
    my ($preline, $rest) = split /\|/, $_, 2;

    die "bad preline $preline" 
      unless $preline =~ /^([\d\.]+)?\s+([\d\.]+\s+)?(\S+)?$/;

    my $label = $1;
    my $importance = $2 ? $2 : 1;
    my $tag = $3;

    my ($actual_tag, @costs) = split /,/, $tag;

    die "bad tag $tag" unless @costs == 0 || @costs == 8;

    my @scores = 
      map { my $s = $model->send (tweak_line ($_, " |$rest |_ k"))->recv ();
            chomp $s;
            $s
          } (ZERO .. SIX);
    my $current_prediction = argmin @scores;

    if (@costs == 8)
      {
        # it turned out better for my problem to combine classes 6 and 7.
        # costs are already inverted and subtracted from 1, so, 
        # have to subtract 1 when doing this
        
        my $class_seven = pop @costs;
        $costs[SIX] += $class_seven - 1;

        # zero level

        my $zero_one = train_node ($model,
                                   ZERO,
                                   ONE,
                                   $scores[ZERO],
                                   $scores[ONE],
                                   $costs[ZERO],
                                   $costs[ONE],
                                   $importance,
                                   $rest) <= 0
                       ? ZERO : ONE;

        my $two_three = train_node ($model,
                                    TWO,
                                    THREE,
                                    $scores[TWO],
                                    $scores[THREE],
                                    $costs[TWO],
                                    $costs[THREE],
                                    $importance,
                                    $rest) <= 0
                        ? TWO : THREE;

        my $four_five = train_node ($model,
                                    FOUR,
                                    FIVE,
                                    $scores[FOUR],
                                    $scores[FIVE],
                                    $costs[FOUR],
                                    $costs[FIVE],
                                    $importance,
                                    $rest) <= 0
                        ? FOUR : FIVE;

        # SIX gets a pass

        # first level: (zero_one vs. two_three), (four_five vs. SIX)

        my $fleft = train_node ($model,
                                $zero_one,
                                $two_three,
                                $scores[$zero_one],
                                $scores[$two_three],
                                $costs[$zero_one],
                                $costs[$two_three],
                                $importance,
                                $rest) <= 0
                    ? $zero_one : $two_three;

        my $fright = train_node ($model,
                                 $four_five,
                                 SIX,
                                 $scores[$four_five],
                                 $scores[SIX],
                                 $costs[$four_five],
                                 $costs[SIX],
                                 $importance,
                                 $rest) <= 0
                     ? $four_five : SIX;

        # second level: fleft vs. fright

        my $root = train_node ($model,
                               $fleft,
                               $fright,
                               $scores[$fleft],
                               $scores[$fright],
                               $costs[$fleft],
                               $costs[$fright],
                               $importance,
                               $rest) <= 0
                   ? $fleft : $fright;

        $total_loss += $importance * $costs[$root];
        $since_last += $importance * $costs[$root];
        $example_weight += $importance;
        $delta_weight += $importance;

        my $best_prediction = argmin @costs;

        foreach my $c (ZERO .. SIX)
          {
            $best_constant_loss[$c] += $importance * $costs[$c];
            if ($c != $best_prediction)
              {
                $best_constant_classification_loss[$c] += $importance;
              }
          }

        $minimum_possible_loss += $importance * $costs[$best_prediction];
        $classification_loss += ($current_prediction == $best_prediction) ? 0 : 1;
        ++$confusion{"$current_prediction:$best_prediction"};

        ++$mismatch if $root ne $current_prediction;
      }

    print $pred_fh (join "\t", $current_prediction, @scores, $actual_tag), "\n"
      if defined $pred_fh;

    ++$example_counter;
    if ($example_counter >= $dump_interval)
      {
        my @features = split /\s+/, $rest;         # TODO: not really

        print_update ($total_loss, 
                      $since_last,
                      $delta_weight,
                      $example_counter,
                      $example_weight,
                      (@costs) ? (argmin @costs) : undef,
                      $current_prediction,
                      scalar @features);

        $dump_interval *= 2;
        $since_last = 0;
        $delta_weight = 0;
      }
  }

my $average_loss = sprintf "%.3f", $example_weight > 0 ? $total_loss / $example_weight : -1;

my $best_constant = argmin @best_constant_loss;
my $best_constant_average_loss = sprintf "%.3f", $example_weight > 0 ? $best_constant_loss[$best_constant] / $example_weight : -1;

my $best_constant_classification = argmin @best_constant_classification_loss;
my $best_constant_classification_average_loss = sprintf "%.3f", $example_weight > 0 ? $best_constant_classification_loss[$best_constant_classification] / $example_weight : -1;

my $minimum_possible_average_loss = sprintf "%.3f", $example_weight > 0 ? $minimum_possible_loss / $example_weight : -1;

my $classification_average_loss = sprintf "%.3f", $example_weight > 0 ? $classification_loss / $example_weight : -1;

print <<EOD;

finished run
number of examples = $example_counter
weighted examples sum = $example_weight
average cost-sensitive loss = $average_loss
average classification loss = $classification_average_loss
best constant for cost-sensitive = $best_constant
best constant cost-sensitive loss = $best_constant_average_loss
best constant for classification = $best_constant_classification
best constant classification loss = $best_constant_classification_average_loss
minimum possible loss = $minimum_possible_average_loss
confusion matrix
EOD
#train/test mismatch = $mismatch

foreach my $pred (ZERO .. SIX)
  {
    print join "\t", map { $confusion{"$pred:$_"} || 0 } (ZERO .. SIX);
    print "\n";
  }

誓言.pm

# 誓言.pm

package 誓言;

use warnings;
use strict;

use POSIX qw (tmpnam mkfifo);
use IO::File;
use IO::Pipe;
use IO::Poll;

sub new ($$)
{
  my $class = shift;
  my $args = shift;

  my $pred_pipename = tmpnam () or die $!;
  my $pred_pipe = mkfifo ($pred_pipename, 0700) or die $!;
  my $pred_fd = POSIX::open ($pred_pipename, 
                             &POSIX::O_RDONLY | 
                             &POSIX::O_NONBLOCK | 
                             &POSIX::O_NOCTTY) or die $!;
  my $pred_fh = new IO::Handle;
  $pred_fh->fdopen ($pred_fd, "r") or die $!;
  POSIX::fcntl ($pred_fh, 
                &POSIX::F_SETFL, 
                POSIX::fcntl ($pred_fh, &POSIX::F_GETFL, 0) & ~&POSIX::O_NONBLOCK);

  my $data_fh = new IO::Pipe or die $!;
  open my $oldout, ">&STDOUT" or die "Can't dup STDOUT: $!";
  eval
    {
      open STDOUT, ">", "/dev/null" or die "Can't redirect STDOUT: $!";
      eval
        {
          open my $olderr, ">&STDERR" or die "Can't dup STDERR: $!";
          eval
            {
              open STDERR, ">", "/dev/null" or die "Can't redirect STDERR: $!";
              $data_fh->writer ("vw $args -p $pred_pipename --quiet") or die $!;
              $data_fh->autoflush (1);
            };
          open STDERR, ">&", $olderr or die "Can't restore STDERR: $!";
          die $@ if $@;
        };
      open STDOUT, ">&", $oldout or die "Can't restore STDOUT: $!";
      die $@ if $@;
    };
  die $@ if $@;

  my $poll = new IO::Poll;
  $poll->mask ($data_fh => POLLOUT);
  $poll->poll ();
  $poll->remove ($data_fh);
  $poll->mask ($pred_fh => POLLIN);

  my $self = { data_fh => $data_fh,
               pred_fh => $pred_fh,
               pred_file => $pred_pipename,
               poll => $poll,
               args => $args };

  bless $self, $class;
  return $self;
}

sub send ($@)
{
  my $self = shift;

  $self->{'data_fh'}->print (@_);

  return $self;
}

sub recv ($)
{
  my $self = shift;

  $self->{'poll'}->poll ();
  return $self->{'pred_fh'}->getline ();
}

sub DESTROY
{
  my $self = shift;

  $self->{'data_fh'}->close ();
  $self->{'pred_fh'}->close ();
  unlink $self->{'pred_file'};
}

1;

2条评论:

  1. 从结构上来说,这非常酷,而且非常接近我的想象。对于大众内部版本,我希望可以有更大的加速,因为您可以避免重新解析功能,这是一个巨大的胜利。 UAI条件概率树纸给人以内部降低可能实现的各种速度的感觉。也许在邮件列表中指出?

    回复删除
  2. 对于历史记录...经过进一步检查,感觉好像可以将一个评分函数设置为零(就像在多项式logit中一样),并且使用修改过的perl脚本进行的某些实验在执行此操作时表现出基本相同的性能。

    回复删除