« 2006年08月 | メイン | 2006年10月 »
2006年09月24日
file upload script for sourcefourge.net
MeCab のリポジトリを sourceforge.jp から sourceforge.net に移行中です．sf.jp のときは，blog で紹介したスクリプトを使ってファイルの自動アップロードを行っていました． sf.net でも当然自動化したいところですが，手続きが sf.jp のそれと大幅に違います．
一番の違いがファイルを Anonymous FTP で事前にアップロードしておく必要があることです. Web上の手続きもほんのちょっと複雑になっています．
sf.net用のスクリプトの使い方は sf.jp 用に作ったものとまったく変わらず
% ./upload.pl -p mecab -n mecab-python -r 0.90 -f mecab-python-0.90.tar.gzのように使います．Net::FTP でファイルをアップロードし，プロジェクト名 (-p) パッケージ名 (-n) リリース (-r) にファイルをアップロードします．
早速 sf.jp にアップロードした30個ぐらいのリリースを順々に sf.net にコピーしています． 人手でやることを考えると恐ろしい...
#!/usr/bin/perl -w
use strict;
use warnings;
use Getopt::Std;
use WWW::Mechanize;
use Net::FTP;
use POSIX qw(strftime);
my %arg;
getopts("hu:P:p:r:n:f:",\%arg);
my $user = $arg{"u"} || $ENV{"USER"};
my $password = $arg{"P"} || "";
my $project_name = $arg{"p"};
my $package_name = $arg{"n"};
my $release_name = $arg{"r"};
my $file_name = $arg{"f"};
sub usage {
print "$0 -u user_name -P password -p project_name \n";
print " -n package_name -r release_name -f file_name\n";
exit;
}
usage () if ($arg{"h"} ||
!$project_name ||
!$package_name ||
!$release_name ||
!$file_name ||
! -f $file_name);
my $ftp = Net::FTP->new("upload.sourceforge.net", Debug => 1);
$ftp->login("anonymous",'anonymous@gmail.com');
$ftp->cwd("/incoming");
$ftp->binary();
$ftp->put("$file_name");
$ftp->quit;
sleep(20);
my $mech = new WWW::Mechanize(autocheck => 1);
print "logging in sourcefourge.net ...\n";
$mech->get("https://sourceforge.net/account/login.php");
$mech->form_number(2);
$mech->field('form_loginname' ,$user);
$mech->field('form_pw' ,$password);
$mech->click();
print "moving to projects/$project_name/admin ...\n";
$mech->get("/projects/$project_name/admin");
my @links = $mech->find_all_links(url_regex => qr[/project/admin/editpackages.php]);
my ($url, $title) = @{$links[0]};
print "moving to $url ...\n";
$mech->get($url);
my $str = $mech->content();
@links = $mech->find_all_links(url_regex => qr[newrelease.php]);
my $pid = -1;
while (1) {
if ($str =~ s/<input type="text" name="package_name" value="([^\"]+)"//) {
++$pid;
last if ($1 eq $package_name);
} else {
last;
}
}
($url, $title) = @{$links[$pid]};
print "moving $url\n";
print "uploading $file_name ...\n";
$mech->get($url);
$mech->form_number(4);
$mech->field('release_name', $release_name);
$mech->click();
$mech->form_number(5);
$mech->tick('file_list[]', $file_name);
$mech->click();
$mech->form_number(4);
$mech->field('release_date',
strftime("%Y-%m-%d", localtime((stat($file_name))[9])));
$mech->click();
print "done\n";
激しく長い.. orz
エラー処理は完全に無視していますが，今のところ動いています．当然ながらサイト変更にたいする頑健性は 0 です．
投稿者 taku : 18:21 | コメント (12) | トラックバック
Javascript でキャレットの位置を取得できる?
Ajax IME は Javascript を悪用しつつ強引にインラインかな漢字変換を実現しています．簡単そうに見えて以外とややこしいのが，変換候補の表示. textarea のキャレット(カーソル) のピクセル単位での位置をなんとかして取得してその位置に変換候補を 出す必要があります． ありがちな google suggest ような補完インタフェイスだと inputbox の真下に出せばいいので位置は完全にわかるのですが，textarea は簡単ではありません．
調べた限り，どうやら標準ではキャレットの位置を取得できないそうです． ただし IE だと以下の方法でピクセル単位での位置がわかります.
var caretPos = document.selection.createRange(); y = (caretPos.offsetTop + document.documentElement.scrollTop); x = (caretPos.offsetLeft + document.documentElement.scrollLeft)
Firefox では以下のようにキャレットの論理位置(何文字目か)と，フォント情報を用いて無理やり求めています．ugly すぎるし，完全ではないのでよくずれます．
obj = textarea;
startPos = 理論位置
var lines = obj.value.substring(0, startPos);
for (var i = 0; i < lines.length; ++i) {
if (lines.charCodeAt(i) == 10) { // \n
x = 0;
y += 1;
} else if (lines.charCodeAt(i) <= 177) { // ASCII
x += 1;
} else {
x += 2;
}
if (obj.scrollLeft == 0 && (y + 1) * fontWidth >= obj.scrollWidth) {
y += 1;
x = 2;
}
}
y = fontHeight * y;
x = fontWidth * x;
どなたか Firefox でキャレットの位置がわかるすばらしい方法をご存知ではないでしょうか?
投稿者 taku : 16:58 | コメント (19) | トラックバック
2006年09月21日
MIRAとstructured outputs
MIRAというアルゴリズムが統計的係り受けの学習でいい成績を叩き出しているようです． 係り受けに特化したアルゴリズムではなく，structured output ならほぼ何でもできる非常に汎用性の高いアルゴリズムのようです．詳細はこちら面白そうなので，ちょっと深追いしてみました．特徴をまとめると
- オンライン学習 - k-best解が得られるような decoder さえあれば動く - single-best でももちろん可能 - single best の場合は Collins voted perceptron に酷似 - single best の場合の inference は SMO と共通点があり，実際 max-margin parsing の特殊系になっている
などなど，面白い点がたくさんあります．
もともとは Ben Tasker の Max margin parsing の話からスタートしています．s(y,x) を構文木 y と入力 x から生成される素性ベクトルとします． w はパラメータベクトル. さらに Collins の notation Y = GEN(x) を x に対する可能な構文木の集合とします．このとき max margin parsing は以下の最適化問題を解きます.
min ||w||
s.t. for all i and y' \in GEN(x)
w [s(y_i,x_i) - s(y',x_i)] >= L(y_i, y')
L(y_i, y') は適当なロス関数で，通常は係り先が異なる単語の数を使うようです．この最適化は SVM の自然な拡張になっています.
MIRA はこれを出発点に，２つのおおきな近時を行います.
1. バッチ的に w を求めるのではなく，オンラインで更新していく.
つまり，すべての学習データをいっぺんに扱うのではなく，オンラインで１インスタンスづつ扱いながらパラメータを更新していきます．１つづつ処理するときには，以下の最適化問題を解きます．
min ||w - w'||
s.t. y' \in GEN(x_i)
w [s(y_i,x_i) - s(y',x_i)] >= L(y_i, y')
w' は以前のパラメータです．つまり，パラメータの変化をできるだけ小さくしつつ，解析エラーを少なくする更新則になっています．
2. GEN(x) を k-best で近時する
GEN(x) をまじめに導出することは，組み合わせ爆発がおきるので通常不可能です．そこで MIRA は k-best 解で近時を行います．k >= 3 の場合は実際に QP ソルバを動かす必要がありますが，k <= 2 の場合は解析的に最適な w を導出することができます.
さて，k = 1 つまり single-best MIRA はどういう形をしているのでしょうか. k = 1 のときは，1パラメータの双対問題になり非常に簡単に最適解が求まります．実際にやってみましょう.
ラグランジュの未定乗数を a とするとラグランジュアン Q とその変微分は
Q = 1/2 * ||w - w'||^2 - a * { w [s(y_i x_i) - s(y', x_i)] - L(y_i, y') }
dQ / dw = w - w' - a [s(y_i x_i) - s(y', x_i)] = 0
つまり w = w' + a [s(y_i x_i) - s(y', x_i)]
となります. w = w' + a * [s(y_i x_i) - s(y', x_i)] . a = 1 とすれば voted perceptron そのものじゃないですか!
この式をラグランジュアンに戻すと
Q = -1/2 a X*X' a - a [ L - w' * X ]
という形になります．X = [s(y_i x_i) - s(y', x_i)] としました．これは解析的に解けて
a_opt = max(0, [ L - w' * X ] / X * X')が解となります．(a >= 0 という KKT 条件から付随されるく)
この更新式の意味するところは，まだわかっていません．直感的に解釈が難しいのです．学習の初期段階では 分子 w' * X は小さい，もしくは負なので，より大きくパラメータが更新されます．一方分母 X * X' も学習の最初の段階では大きな値なので，結局分子と分母が相殺しあう形になっています. 簡単な実験をしてみたところ a に対するドラスティックな変更はあまりなく，実質は Collins voted perceptron とほとんど同じような印象を持ちました．
さて，清水さんは MIRA のアルゴリズムを別の視点から考察なさっています．論文が詳しいですが，Tasker の Max margin parsing に対して SMO を使うと，あら不思議 MIRA の更新則がそっくりそのまま再現されます． SMO は, 一番パラメータを変更するであろう 2つのインスタンスをヒューリスティックに選択し，その二つのパラメータを解析的に更新するアルゴリズムで．このとき二つのインスタンスとして，正解データと今のパラメータで argmax となるようなデータの2つを選択するようなヒューリスティックスを使うと MIRA の更新則になります． とても興味深いです．
ほかにも perceptron 系の亜流として Bayse points machine などあるようですが，それは追々．