~matubara/ChangeLog / 2007-08 →移動しました

■ Xuerui Wang [people][net]

<http://www.cs.umass.edu/~xuerui/research.html>
data mining 系トピックモデリング

■ blogs nodalpoint wiki [bio][net]

<http://wiki.nodalpoint.org/blogs>

■ use utf8 より $KCODE='UTF8' のほうが速い [ruby][perl]

#! /usr/bin/env ruby
$KCODE='UTF8'
require 'moji'

DAKUON = Hash[*('ウヴカガキギクグケゲコゴサザシジスズセゼソゾタダチヂツヅテデトドハバヒビフブヘベホボ'.split //)]
HANDAK = Hash[*('ハパヒピフプヘペホポ'.split //)]
DAKUON_ORIGIN = DAKUON.keys.join
HANDAK_ORIGIN = HANDAK.keys.join
LATIN_ORIGIN0 = (0x01..0xFF).map{|x| x.chr}.join
LATIN_ORIGIN  = LATIN_ORIGIN0.sub(/\\/, '\\\\\\\\').sub(/-/, '\\-')
LATIN_ZENKAKU = Moji.han_to_zen(LATIN_ORIGIN0)
KATAKANA_ZENKAKU = 'ァィゥェォャュョッアイウエオカキクケコサシスセソタチツテトナニヌネノハヒフヘホマミムメモヤユヨラリルレロワヲン゛゜'
KATAKANA_HANKAKU = Moji.zen_to_han(KATAKANA_HANKAKU)

while gets
  $_.tr!(KATAKANA_HANKAKU, KATAKANA_ZENKAKU)
  $_.gsub! /[(#{DAKUON_ORIGIN})]゛/, "#{DAKUON[$1]}"
  $_.gsub! /[(#{HANDAK_ORIGIN})]゜/, "#{HANDAK[$1]}"
  $_.tr! ' ', '　'
  $_.tr!(LATIN_ORIGIN, LATIN_ZENKAKU)
  print $_
end

#! /usr/bin/env perl
use utf8;
use Readonly;
use Encode;
use Unicode::Japanese qw[unijp];
Readonly my %dakuon => map {$_} split //, 'ウヴカガキギクグケゲコゴサザシジスズセゼソゾタダチヂツヅテデトドハバヒビフブヘベホボ';
Readonly my %handakuon => map {$_} split //, 'ハパヒピフプヘペホポ';
Readonly my $dakuon_origin => join q{}, keys %dakuon;
Readonly my $handakuon_origin => join q{}, keys %handakuon;
Readonly my $keywordlist_encoding => q{utf-8};

while(<>){
  $_ = decode_utf8 $_;
  chomp;
  trr/ｧｨｩｪｫｬｭｮｯｱｲｳｴｵｶｷｸｹｺｻｼｽｾｿﾀﾁﾂﾃﾄﾅﾆﾇﾈﾉﾊﾋﾌﾍﾎﾏﾐﾑﾒﾓﾔﾕﾖﾗﾘﾙﾚﾛﾜｦﾝﾞﾟ/ァィゥェォャュョッアイウエオカキクケコサシスセソタチツテトナニヌネノハヒフヘホマミムメモヤユヨラリルレロワヲン゛゜/;
  s/([$dakuon_origin])゛/$dakuon{$1}/g;
  s/([$handakuon_origin])゜/$handakuon{$1}/g;
  tr/ \-~/　−〜/;
  tr[\x{01}-\x{FF}][\x{FEE1}-\x{FFDF}];
  print encode_utf8 $_;
  print "\n";
}

ruby 1.8.5 (2006-08-25)
perl, v5.8.8

ruby t.rb < <(head -n1000 x.txt) > /dev/null 0.20s user 0.00s system 82% cpu 0.251 total
perl t.pl < <(head -n1000 x.txt) > /dev/null 0.88s user 0.02s system 95% cpu 0.947 total

まとめ
- utf8フラグを立てたら負け
- オブジェクトを作ったら負け

■ tr, s のほうが Unicode Japanese より速い [perl]

#! /usr/bin/env perl

use utf8;
use Benchmark;
use Unicode::Japanese qw[unijp];
use Readonly;
use Encode;

Readonly my %dakuon => map {$_} split //, 'ウヴカガキギクグケゲコゴサザシジスズセゼソゾタダチヂツヅテデトドハバヒビフブヘベホボ';
Readonly my %handakuon => map {$_} split //, 'ハパヒピフプヘペホポ';
Readonly my $dakuon_origin => join q{}, keys %dakuon;
Readonly my $handakuon_origin => join q{}, keys %handakuon;
Readonly my $keywordlist_encoding => q{utf-8};

my $str = '今日はxxx@gmail.comにﾎﾟｽﾄしておいて！!!';
my %h = (
         'tr' => sub{
           my $x = shift || $_;
           $x =~ tr/ｧｨｩｪｫｬｭｮｯｱｲｳｴｵｶｷｸｹｺｻｼｽｾｿﾀﾁﾂﾃﾄﾅﾆﾇﾈﾉﾊﾋﾌﾍﾎﾏﾐﾑﾒﾓﾔﾕﾖﾗﾘﾙﾚﾛﾜｦﾝﾞﾟ/ァィゥェォャュョッアイウエオカキクケコサシスセソタチツテトナニヌネノハヒフヘホマミムメモヤユヨラリルレロワヲン゛゜/;
           $x =~ s/([$dakuon_origin])゛/$dakuon{$1}/g;
           $x =~ s/([$handakuon_origin])゜/$handakuon{$1}/g;

           $x =~ tr/ /　/;
           $x =~ tr[\x{01}-\x{FF}][\x{FEE1}-\x{FFDF}];
           return $x;
         },
         'uj' => sub{
           return unijp(shift || $_)->h2z->getu
          });

print encode_utf8 $h{tr}->($str). "\n";
print encode_utf8 $h{uj}->($str), "\n";

$_ = join '', <DATA>;
timethese(50000, \%h);
$_ = join '', <>;
timethese(5, \%h);

今日はｘｘｘ＠ｇｍａｉｌ．ｃｏｍにポストしておいて！！！
今日はｘｘｘ＠ｇｍａｉｌ．ｃｏｍにポストしておいて！！！
Benchmark: timing 50000 iterations of tr, uj...
        tr: 1 wallclock secs ( 0.64 usr + 0.00 sys = 0.64 CPU) @ 78125.00/s (n=50000)
        uj: 3 wallclock
secs ( 2.66 usr + 0.02 sys = 2.68 CPU) @ 18656.72/s (n=50000)

■ A Fully Bayesian Approach to Unsupervised Part-of-Speech Tagging [learn][net]

■ Unsupervised Language Model Adaptation Incorporating Named Entity Information [lm][net]

<http://acl.ldc.upenn.edu/P/P07/P07-1094.pdf>
文書を表す単語ベクトルを、named entity だけにして、
文書クラスタリングに基づく適応をやったという話。

■ Fast exact maximum likelihood estimation for mixture of language models [lm][ir]

<http://dx.doi.org/10.1145/1277741.1277948>
情報検索の一部（）で使われている、片方の分布が未知の混合ユニグラムモデルにおいて、
厳密かつ、線形時間な解法が得られた。

p, q を多項分布に従う確率変数、\alpha を実数とするとき、
r = \alpha p + (1-\alpha) q
（rはpとqの混合、または線形補完と呼ばれる）

r の標本値がたくさん
p の分布（パラメタ）
\alpha の値
がわかっているときに、q のパラメタ（多項分布の各項の重み）を求めるのが問題。

証明が面白い。
でも、正当性きちんと検証できるほど読み込めてはいない。

実用的なインパクトはあまりないと思うけれど、
安易な「EMで近似解」ではないアプローチとして、価値があると思う。

■ www.codeblog.org - CODE blog [programming][net]

<https://www.codeblog.org/>

■ The Xapian Project [ir][net]

<http://www.xapian.org/>

■ mecab/swig で形態素のオリジナルテキスト上での位置を得る [segmentation][nlp]

http://lists.sourceforge.jp/mailman/archives/mecab-users/2007-February/000231.html

MeCab の出力フォーマットもしくは C/C++ API を使えば、ある単語が
元のテキストの何バイト目から何バイト目に出現したか分かるので、
元のテキスト中にスペースがあったかどうか区別することができます。

なにも考えずに swig api にも追加。

mecab/swig/MeCab.i に追加：

 %extend mecab_node_t {
   int position_start(mecab_node_t *ref)
   {
      return (int)( self->surface - (ref->surface + ref->length - ref->rlength) );
   }

   int position_end(mecab_node_t *ref)
   {
      return (int)( self->surface - (ref->surface + ref->length - ref->rlength) + self->length );
   }
 }

仕様がださいですが、一応動きます。

standoff 風出力：

my $head;
for (my $m = $head= $c->parseToNode($sentence); $m; $m = $m->{next}) {
    printf("%d %d\Token %s\t%s\n", $m->position_start($head), $m->position_end($head), $m->{surface}, $m->{feature});
}

■ 未知語 [lm]

AABCDE、と6つの単語が出現するという事象の確率を求めることを考える。
簡単のために、モデルはスムージングも事前分布もない単語ユニグラムモデルとし、
訓練データでの分布も、同じ分布（A:B:C:D:E = 2:1:1:1:1）だとしよう。

モデル１はABCという３つの単語だけを知っていて、
残り２つを「未知語」同値類 <UNK> として扱う。
したがって、モデル1の下では、
P(A)=2/6, P(B)=P(C)=1/6, P(D)=P(E)=P(<UNK>)=2/6
これ以外のどんな単語にたいしても
P(単語)=P(<UNK>)=2/6
である。

モデル2はABという２つの単語だけを知っている。
モデル1と同様にして、
P(A)=2/6, P(B)=1/6, P(C)=P(D)=P(E)=P(<UNK>)=3/6

モデル3はAだけを知っているものとすると、
P(A)=2/6, P(B)=...=P(<UNK>)=4/6

これらのモデルを、ABCDEという単語列にたいする、
単語当たりのテストセットパープレキシティで評価してみると、
モデル1 (6/2 * 6/2 * 6/1 * 6/1 * 6/2 * 6/2)^(1/6) = 3.780
モデル2 (6/2 * 6/2 * 6/1 * 6/3 * 6/3 * 6/3)^(1/6) = 2.794
モデル3 (6/2 * 6/2 * 6/4 * 6/4 * 6/4 * 6/4)^(1/6) = 1.890
となって、モデル3がもっとも優れた手法だといえる。

……というのは当然嘘である。
どこに嘘があったのかといえば、
”単語当たりの”テストセットパープレキシティというのが嘘。
未知語は同値類であり、少なくとも１つ以上の単語を含んでいるから、
これを混ぜて、 単語当たりの、というのは間違い。
もっとも得票数が多いのが「その他」だったからといって、
「その他」が最大支持を得たとはいえないのと同じ。

じゃあ未知語を除けばいいのかというと、
モデル1 (6/2 * 6/2 * 6/1 * 6/1)^(1/4) = 4.24
モデル2 (6/2 * 6/2 * 6/1)^(1/3) = 3.77
モデル3 (6/2 * 6/2)^(1/2) = 3
となって、状況がよくなっているようには見えない。
こんどは単語の集合と単語を同列に扱うことは避けられたけど、
代わりに未知語でない単語、つまりモデルがよく知っている単語についてしか性能を見ていないので、
未知語が多いモデルほど優れているように見えてしまう。

結局、CとDを区別できるモデル1と、
区別できないモデル2,3を、直接比較することはできない。

これを解決するひとつの方法は、未知語の定義を一致させること。
http://www.stanford.edu/class/cs224n/faq.html#unk
未知語のもっとも多いモデル3にあわせるなら、
モデル1,2,3は同じ性能だという、評価になり、
もっとも少ないモデル1にあわせるなら、
モデル2と3はパープレキシティ無限大という評価になる。

実際には、未知語がおおいモデルに合わせるというのは、
モデルの能力を落としていることになってナンセンスなので、
後者の方法を取ることになる。

こうして一応、（パープレキシティがよい評価方法だと認めるなら）
モデルの比較ができるようになったけれど、
結局のところ、未知語という単語クラスと、単語を同列に扱っているという気持ち悪さは残る。

これを解決するもっとも正統派（だと思う）の方法は、
無限の語彙を生成する方法。たとえば
http://www.cog.brown.edu/~mj/papers/acl06-wordseg.pdf

未知語が少ない（言い替えれば、かなり大きな既知語のリストを持っている）
状況でやるのは、不適切、もしくは課題が大きいと思う。
既知語の情報をとりこもうと思うと、
上記の手法では、強く既知語に偏った prior を与えることになるけれど、
conjugate prior を守りながらそれを与えるのは困難。

■ Processing 1.0 (BETA) [ui][programming][net]

<http://processing.org/>
Yet another programming environment for education
http://processing.org/reference/libraries/