2011年3月30日,星期三

减少过滤树:Perl实现

最近我一直在用以下方法解决多分类问题 誓言 用一个 机器学习减少。理想情况下,我将使用vowpal提供的减少API在C中对此进行编程。在实践中,vowpal不断变化。因此,为了隔离自己,我一直将vowpal视为我通过IPC与之通信的黑匣子。这种方法有一个缺点:如果我在vowpal内实施减少(基于top的输出),我估计我的总吞吐量至少会大4倍。希望John和他们的工作人员将在不久的将来提供稳定的vowpal减少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 | \} $表示。我还将假设输入格式与vowpal的本机输入格式非常相似,但是使用的是成本向量而不是标签。 \ [
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中,我将其转换为一组vowpal输入行,其中每行对应于特定的类标签$ n $,\ [
\; \ textrm {tag} | \ textrm {namespace} n \; \ textrm {功能} \ ldots
\]本质上,成本向量和重要性权重被去除(因为现在没有学习发生),标记被去除(我将单独处理),并且每个命名空间都附加了类标签。由于vowpal使用第一个字母来标识名称空间,因此对名称空间进行操作的选项(例如-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 \; ķ
\]这些行中的每行都输入到vowpal,并且具有最低vowpal输出的类别标签被选为比赛的获胜者。命名空间_中的最后一个功能$ k $提供了常量功能的类标签本地化版本,vowpal在每个示例中默默提供了该功能。

火车时间
在火车上,我基本上是参加比赛的:但是由于我知道实际的花费,所以我根据谁``应该赢了''来更新分类器。更新的重要性权重由刚刚参加比赛的两个团队之间的成本绝对差值确定。因此,对于两个类别标签$ 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)$,即,原始重要性权重由实际成本中的绝对差来衡量。在这里,我利用了在名称空间上提供权重的功能,该权重乘以名称空间中所有功能的权重。 (vowpal始终提供的那种讨厌的常量功能呢?它仍然存在并且实际上不应该。正确的处理方法是修补vowpal以接受不提供常量功能的选项。但是我想呈现一些适用于未修补的vowpal的内容,因此我改为输入另一项训练输入,并将所有取反,以使恒定特征保持接近零。)

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

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

编码

有两部分:
  • 誓言.pm:这封装了与vowpal的通信。您将需要它来使其正常工作,但主要是无聊的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 "vowpal 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 "vowpal 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 和 7.
        # costs are already 在verted 和 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 真

        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;

2011年3月27日,星期日

关于利用Twitter社交图谱

最近,我忙于构建各种分类器,这些分类器采用Twitter资料并预测广告主感兴趣的属性:性别和种族。最初,我专注于将最新的推文作为功能的来源,并取得了一些成功。然后,我开始合并Twitter个人资料的其他部分,以改进分类器。


快速又脏

看起来有两个额外的信息来源立即很有希望:生物图谱和社会图谱。由于我正在使用由提供的稀疏逻辑回归 Vowpal兔子,我首先进行了尽可能幼稚的编码:我通过与标签之间的相互信息获取了前N个令牌,并名义上对它们进行了编码。要澄清的是,生物中的代币或多或少是您期望的。而社交图中的令牌是连接另一端上帐户的数字Twitter身份(我仅考虑遵循行为,而忽略了遵循行为)。应用于性别分类器的这种幼稚方法导致了生物令牌的一些改进,但对于社会令牌却基本上没有改进。

半监督

正如该博客上最近的主题一样,我所处的一个重要方面是未标记的配置文件比标记的配置文件大4个数量级。因此,我使用了大量的BIOS,使用LDA从它们中构建主题模型,然后将所得到的特征用作我监督的分类器的输入。我还使用了大量社交图边缘集,使用LDA从它们中建立主题模型,然后将所得特征用作我的监督分类器的输入。

令人惊讶的是,bios LDA功能没有比生物令牌的名义编码好得多。但是,社交图LDA功能的确比社交令牌的名义编码做得更好。

这是怎么回事?

因为社交图信息以LDA功能的形式有用,所以这表明名义编码的问题是样本复杂度和分类技术的某种组合(或更可能是:我在某个地方犯了错误)。虽然我对发生的事情不完全了解,但这一集促使我查看了社交图谱与生物图谱之间的统计数据。

因此,展示1是出现在生物或社交边缘集中的单个令牌的排名频率。这意味着什么:
  • 对于bio:如果您从串联在一起的所有bios中选择一个随机词(或等效地,从所有bios中抽取与单词数成正比的样本,然后在该bio中选择一个随机词),则这是第N个最常使用的概率令牌将是您选择的令牌。
  • 对于社交:如果您从所有“ A跟随B”关系的(有向)图中选择一个随机边(或等效地,从所有推特帐户中抽取与所跟随的帐户数量成比例的样本,然后选择一个随机帐户,该推特配置文件是之后),这是第N个最常关注的Twitter帐户将成为所选边沿关注的那个帐户的可能性。
毫无疑问,以这种方式进行采样时,您选择的是生物中出现频率最高的令牌,而不是跟踪频率最高的Twitter帐户。从这种角度来看,生物令牌比社交令牌具有更大的头部和更短的尾巴。所以我想,``啊哈,这就是问题所在,由于社会边缘集的繁重尾巴,名义编码遇到了样本复杂性问题''。

但是,我现在认为这是不正确的。考虑类似的展览2,但是排名和频率是根据帐户而不是代币。换一种说法:
  • 对于个人生物:如果您选择一个随机的Twitter帐户,则这是该帐户个人生物中的至少一个令牌将成为第N个最常出现的令牌的概率。
  • 对于社交用户:如果您选择一个随机的Twitter帐户,则这是该帐户遵循第N个最常关注的Twitter帐户的概率。
可以说上述采样过程对于名义编码策略而言更为重要:由于我在总配置文件中标注的比例很小(例如1000个配置文件中有1个配置文件),因此我的样本只能支持对超过一定速率的令牌进行名义推断 每个配置文件 (例如,每100个配置文件中有1个配置文件,因此我可以预期有10个与令牌的存在相关的标记样本)。因此,展示2:
以这种方式看,社交图的头更重要:换句话说,大约有100个单词可能对生物的名义编码有用,而大约有1000个推特帐户可能对社交图有用。社会边缘集的名义编码。从根本上来说,展览1与展览2的区别在于,大多数个人资料的追踪者数量都比其个人传记中的单词要多,因此对整个个人资料进行采样会产生更多的社会令牌(或者:展览1中的图归一化为1,展览2中的图归一化才不是)。

因此,现在我认为正在发生的事情是,在足够频繁的生物令牌中,有许多对性别具有决定性的含义:诸如“父亲”,“母亲”,“丈夫”和“妻子”等明显的词;但也不太明显,例如女性更有可能说“ b子”,而印尼男性则更有可能说“ saya”。同时,在Twitter上最受欢迎的一组帐户中,该帐户的追随者的性别偏爱相对不是很强。例如, 酷玩乐队 有很多追随者,但据我所知,男女追随酷玩乐队的可能性几乎相同。虽然 奥普拉 从直觉上来说,这听起来像是两极分化,而追随奥普拉的女性只有男性的两倍。与此相比:男人在其生物中使用“吮吸”一词的可能性是42倍,而女人在使用“女孩”一词的可能性是20倍。有一些受欢迎的Twitter帐户在性别两极分化方面相对比较极端(例如, 单身女人克里斯·布鲁萨德),但总的来说,人们在描述自己时说的关于性别的最普遍的说法比人们选择遵循的最常见的推特帐户更具吸引力(一旦考虑到最近的推文)。

因此,我的收获是:要真正利用社交图谱,就需要加强我的技术。这意味着:
  • 获取更多带标签的数据。在这里,积极的学习技巧对于防止我的机械特克账单爆炸是至关重要的。
  • 更广泛地利用未标记的社交图数据。这包括在社交图谱上尝试更多无监督的技术;但同时也要进行更明确的半监督技术(而不是:无监督,然后再进行监督)。

2011年3月23日,星期三

社会图谱上的LDA

在我的 以前的帖子 我指出我面临各种半监督的问题,并且我希望在社交图中利用LDA来构建特征表示,以提高我在各种分类任务上的性能。既然我已经真正做到了,我想我会分享一些结果。

图上的LDA

该策略是将社交图的每个顶点处的边集视为文档,然后将LDA应用于生成的文档语料库,类似于 张等等 由于我正在考虑Twitter的社交图谱,因此潜在因素可能代表兴趣或社区,但实际上我并不在乎,只要所得到的功能改善了我的监督分类器即可。

当LDA首次应用于Computer Vision时,它基本上未经修改就被首次应用 取得了一些成功。然后将生成模型调整到问题域以提高性能(例如,在Computer Vision的情况下,通过合并 空间结构)。这样做是出于非常实际的原因:当您应用标准生成模型时,您就可以利用他人的优化和正确实现!出于同样的原因,我在这里坚持使用原始的LDA,但是我发现有些方面并不完美。
  • 在有向社交图(例如Twitter)上,有两种边缘,类似于文档中存在的两种不同标记。 LDA只有一种令牌类型。可以通过在每个边缘前面加上“ +”或“-”指示方向来解决此问题。在实践中,我仅通过对输出边进行建模(即有人跟随的一组人)来回避此问题。
  • 一个边在边集中只能存在一次,而使用香草LDA,令牌可以在文本文档中多次出现。考虑到边缘发射概率之间的这种负相关性可能会改善结果。

广泛的社会话题

即使我实际上并不关心了解潜在因素,也可以用来娱乐博客。所以现在找乐子。我从Twitter用户的随机样本中对边缘集运行了10个主题的LDA模型,以便获得图形结构的广泛概述。以下是每个主题的十大最可能的Twitter帐户:
1Ugglytruth globovision LuisChataing juanes tusabiasque AlejandroSanz Calle13Oakly Shakira Erikadlv ChiguireBipolar ricky_martin BlackberryVzla miabuelasabia CiudadBizarra ElUniversal chavezcandanga luisfonsi ElChisteDelDia noticias24
2detikcom SoalCINTA sherinamunaf Metro_TV soalBOWBOW radityadika kompasdotcom TMCPoldaMetro IrfanBachdim10 ayatquran agnezmo pepatah AdrieSubono desta80s Cinema21 Fitrop vidialdiano ihatequotes sarseh
3RevRunWisdom NICKIMINAJ drakkardnoir TreySongz kanyewest chrisbrown iamdiddy myfabolouslife KevinHart4real LilTunechi KimKardashian MissKeriBaby 50cent RealWizKhalifa lilduval MsLaurenLondon BarackObama Ludacris Tyrese
4justinbieber radityadika Poconggg IrfanBachdim10 snaptu AdrieSubono MentionKe TheSalahGaul vidialdiano FaktanyaAdalah TweetRAMALAN soalBOWBOW unfollowr disneywords DamnItsTrue SoalCINTA sherinamunaf widikidiw PROMOTEforfor
5NICKIMINAJ KevinHart4real TreySongz RevRunWisdom RealWizKhalifa chrisbrown drakkardnoir Wale kanyewest lilduval Sexstrology myfabolouslife LilTunechi ZodiacFacts106andpark Ba​​rackObama Tyga FreakyFact KimKardashian
6ConanOBrien cnnbrk shitmydadsays BarackObama THE_REAL_SHAQ Theion jimmyfallon nytimes StephenAtHome BreakingNews mashable google BillGates rainnwilson twitter espn ochocinco TIME SarahKSilverman
7Ladygaga KimKardashian katyperry taylorswift13布兰妮斯皮尔斯PerltonHilton KhloeKardashian aplusk TheEllenShow KourtneyKardash rihanna jtimberlake justinbieber RyanSeacrest ParisHilton nicolerichie LaurenConrad selenagomez Pink
8iambdsami Z33kCare4women DONJAZZYMOHITS MriLL87WiLL chineyIee NICKIMINAJ MrStealYaBitch FreddyAmazin制片人Hitmann MI_Abaga DoucheMyCooch WomenLoveBrickz Uncharted_ WhyYouMadDoe MrsRoxxanne I_M_Ronnie B?
9Woodytalk vajiramedhi chocoopal PM_Abhisit js100radio kalamare Trevornoah GarethCliff suthichai Domepakornlam ploy_chermarn crishorwang paulataylor Noom_Kanchai jjetrin Khunnie0624 ThaksinLive DJFreshSA R​​adioblogger
10myfabolouslife IAMBIGO NICKIMINAJ GuessImLucky DroManoti GFBIVO90 Sexstrology FASTLANE_STUDDA PrettyboiSunny Ms_MAYbeLLine ZodiacFacts FlyLikeSpace RobbRF50PKF CLOUD9ACE Jimmy_Smacks LadieoloGistPKF TreySongz Prince_Japan
大致而言,我看到西班牙裔(主题1),亚洲(主题2),嘻哈(主题3),具有西方影响力的亚洲人(主题4),具有占星学影响力的嘻哈(主题5),新闻和喜剧(主题6) ,北美名人(主题7),嘻哈(主题8),亚洲(主题9)和嘻哈(主题10)。

是的,这些数据是在查理·希恩(Charlie Sheen)之前收集的 暴涨.

shitmydadsays是一个新闻网站

实际上,主题6确实令人着迷。也许最好将其称为“新闻速递之类”。毫无疑问,新闻兴趣和喜剧兴趣是相交的,但因果关系尚不清楚:是否需要观看新闻以了解笑话,还是需要通过笑话来避免在观看新闻后出现严重的沮丧情绪?

贾斯汀·贝伯的文化多义性

使用LDA分析文本时,针对多个主题具有较高发射概率的标记通常具有多种含义。在这里,我们看到Justinbieber对于主题4和7的发射概率很高,否则主题分别是亚洲和北美。一种解释是,贾斯汀比伯的吸引力跨越了两种文化。

2011年3月3日,星期四

享受闪电般快速LDA的另一个原因

在我目前的情况下,我面临着涉及大量未标记数据和少量标记数据的问题。这使我陷入 半监督学习 区。

一种流行的半监督技术是对未标记的数据使用非监督技术来学习数据表示,然后对较小的标记数据使用具有监督技术的结果数据表示。我正在查看Twitter数据,推文是文本(可以说是``非自然语言''),所以 LDA 是这里的自然选择,最近开发的 超快速实施Vowpal兔子 是德国人。

Twitter还是一个社交网络,但是以最直接的方式(名义上编码直接连接的身份)并入社交图信息类似于编码文本令牌的最直接的方式。当您有数以百万计的带有标签的示例时,它会很好用,但其他方面则很少,因此非常有用。

当您使用锤子时,一切看起来都像钉子,因此我想也许可以将与顶点关联的边集视为文档,然后对所有边集执行LDA。原来 这已经完成了 ,结果看起来合理。从我的角度来看,我不在乎潜在因素是社区还是兴趣(使用Twitter,可能两者兼而有之),只是最终的功能最终可以改善我的受监督学习者。

2011年3月2日,星期三

夏洛克·福尔摩斯

我看了飞行员剧集 粉红色的研究 BBC电视连续剧 夏洛克。这让我怀疑夏洛克·福尔摩斯在理论上是否可行。这不仅是一个幻想的问题:如果可以完成夏洛克·福尔摩斯的所作所为,但是人类在实践中做起来太困难了,那么最终我们可以制造出能够赋予警方夏洛克·福尔摩斯权力的机器。

从贝叶斯角度看,夏洛克·福尔摩斯公式包括大量的观察结果,对可能性的强烈假设以及为解决歧义而偶尔使用的先前假设。我的问题是,观察结果实际上是否包含Sherlock所说的那样多的信息,即,是否(错误地)错误地指定了可能性?

例如,在 粉红色的研究 夏洛克得出结论,根据手机电源插头附近的广泛刮擦声,手机的拥有者是惯常喝醉的:“只有惯常喝醉的人在晚上插入手机时始终会颤抖的手。”但是真的?如果我们要调查数百万部手机,选择电源插头周围有刮擦的手机,然后查看所产生的所有者中惯性醉酒的比例,那么相对于所有单元格中惯性醉酒的比例,我们会发现什么电话所有者?

无论如何,人类推理存在足够多的已知问题,例如 确认偏差,即使无法通过小观察获得正确的推断,未来的计算机化警察助理也可能会大大改善侦探工作。

另外,节目是 做得好。