2009-07-23

wanderlust で GMail 風、新着レス順にソート

emacs

~/.wl に追加しておくと、 Summary モード -> "S" の候補に "reply-date" が出る。
これを選んでやると Summary が GMail 風にソートされる。
http://gist.github.com/153020

(defun wl-summary-overview-entity-compare-by-reply-date (a b)
  "Compare entity X and Y by latest date of replies."
  (flet ((string-max2
          (x y)
          (cond ((string< x y) y)
                ('t x)))
         (elmo-entity-to-number
          (x)
          (elt (cdr x) 0))
         (thread-number-get-date
          (x)
          (timezone-make-date-sortable (elmo-msgdb-overview-entity-get-date (elmo-message-entity wl-summary-buffer-elmo-folder x))))
         (thread-get-family
          (x)
          (cons x (wl-thread-entity-get-descendant (wl-thread-get-entity x))))
         (max-reply-date
          (x)
          (cond ((eq 'nil x)
                 'nil)
                ((eq 'nil (cdr x))
                 (thread-number-get-date (car x)))
                ('t
                 (string-max2 (thread-number-get-date (car x))
                              (max-reply-date (cdr x)))))))
    (string<
     (max-reply-date (thread-get-family (elmo-entity-to-number a)))
     (max-reply-date (thread-get-family (elmo-entity-to-number b))))))
(add-to-list 'wl-summary-sort-specs 'reply-date)

2009-04-15

CRFでない最大エントロピー法をgibbs sampling で解く

prfr learning

Finkel+2005, Incorporating non-local information into Information Extraction Systems by Gibbs sampling

最大エントロピーモデル
・素性値の経験分布での期待値とモデルによる期待値が一致するという制約
・制約から対数線形モデルを導出
・尤度関数の線形重みに対する勾配は閉じた式で書ける
正則化項を加える場合も、普通は微分可能なものを選ぶ（L1正則化なんか微分できない部分があるので一工夫が必要）
・勾配には、モデルによる素性値の期待値が含まれる
モデルが複雑な場合（例:CRF）、期待値の計算の効率化が必要（DPなど）←ポイント！

最大エントロピーモデルのパラメータ推定
・尤度（＋正則化項）の最大化
・勾配を使った近似解法
上記の勾配を使って、尤度を大きくするような方向に重みを調整していく
← 期待値計算が遅いと、線形で遅くなる
最大エントロピーモデルによる推論
・重みが分かっている状態で可能な候補を列挙、モデル確率が高い候補を選択
CRFではここでもDPで効率的な計算が可能
最大値をとる候補である必要はなくて、期待値でもいい ← ポイント！

Gibbs sampling
・複雑なグラフィカルモデル上の確率変数の期待値を出すための近似解法。

CRFなどのDPによる期待値計算が可能なグラフィカルモデル上での最大エントロピー法とは異なり、
非局所の依存関係を入れたグラフィカルモデルでは、期待値計算が難しい。
（単純にありえる依存関係組を列挙すると膨大になる）
そこで期待値計算を厳密にやるのを諦めて、gibbs sampling で近似する。

CIKM-8 Charles Elkan's tutorial of "Log-linear models and conditional random fields"
スライドと予稿で解説。
gibbs sampling にも触れている。

2009-04-11

Kernel Averaged Perceptron の話

learning

要約すると、
カーネルパーセプトロンを使うくらいならサポートベクターマシンを使ったほうがいい
という話。

以下、パーセプトロンとかカーネルとか基本的なところばかり書きます。

＜パーセプトロン＞
正負ラベルを予測する二値分類を行うパーセプトロンの場合、以下のアルゴリズムで訓練する。
・以下を、重みが収束するまで繰り返す
　1. サンプル（正解ラベル付き）をランダムにとってくる
　2. 現在の重みとサンプルの内積をとって、その符号（つまり予測されたラベル）が正しければ 1. へ
　3. 重み = 重み - あるべき符号 * サンプル
推論（符号が未知のサンプルに対するラベルの予測）のときも、2. と同様に重みとの内積の結果の符号をとって返す。

パーセプトロンはオンラインで使える。
つまり、サンプルが次々と追加される場合でも、順序がランダム（変な偏りがない）と仮定できるなら、上記のアルゴリズムをそのまま適用してよい。

＜平均化 (averaged)パーセプトロン＞
[2009-03-09-1] 参照。
大雑把には、
・パーセプトロンの重みは、訓練データの線形和
・averaged perceptron の重みは、パーセプトロンの訓練中の過去の重みを平均化したもの
・つまりaveraged perceptron の重みは線形和の線形和 → 単純に計算すると2乗が出てくるけど、有限の線形和の線形和は線形和で書ける
という話。
パーセプトロンの弱点である重みの不安定性（入力順序への依存性）を緩和できているということになっていて、
経験的にも確かにそんな感じ。
計算時間を（実質上）増やさない実装ができるので、
最近パーセプトロンで分類やランキングをするといえば、
ほとんどこれになっている。
NLTKなどに入っている実装もこれ。
原典は Y Freund, RE Schapire Machine learning, 1999 "Large margin classification using the perceptron algorithm".

＜カーネル＞
カーネルは通常、内積の一般化の形をしている。
内積は同じ軸の量同士の符号が似ているほど大きくなる。
内積の代わりにカーネルを使うことによって、異なる軸の量同士の相関をはかることができる。
たとえば多項式カーネルでは、内積の代わりに、内積のN乗をする（Nは固定）。
(x y + a)^N

たとえば3次元のベクトルに対する2次の多項式カーネルを書き下すと、
(x1y1 + x2y2 + x3y3 + 1) ^ 2
= x1y1^2 + x1y1x2y2 + x1y1x3y3 + a x1y1 +
x2y2x1y1 + x2y2^2 + x2y2x3y3 + a x2y2 +
x3y3x1y1 + x3y3x2y2 + x3y3^2 + a x3y3

このようになる。
異なる次元 (たとえば第2項は1次元目と2次元目）の比較が入っていることがポイント。
（ここでは二値分類、つまり値が正か負かだけに注目するので、2つの数の掛け算は2つの数の類似度の一種として扱える）

また、 a != 0 の多項式カーネルは内積そのものに相当する項を持っていること、その項の係数が a であることから、多項式カーネルの符号は、a が大きいほど内積そのものに近づくことが分かる。
逆に a = 0 を選ぶと、内積が入らなくなるので、過学習しやすいかもしれない。

＜カーネルパーセプトロン＞
原典は averaged perceptron と同じく
Y Freund, RE Schapire Machine learning, 1999 "Large margin classification using the perceptron algorithm".
averaged perceptron に出てくる内積を全部カーネルに置き換える。
ただし、非カーネルの平均化パーセプトロンとは違って、カーネルの線形和は線形和で書けないので
誤分類をしたとき、重みに足し算をする代わりに、あとで足せるように係数とどのサンプルだったかを覚えておく。
予測をするときになって、覚えておいたサンプルとのカーネルを計算する。

カーネルを使うと分類精度は少し上がるんだけど、
訓練の途中で誤分類するほど予測が遅くなるというのが欠点。
サンプル数が多い場合はメモリも気になってくる。

パーセプトロンは訓練と推論が同じ予測モジュールによっているので、
訓練も推論もおなじように遅くなる。

そこへいくと、ハードマージンのサポートベクターマシン (SVM) は覚えておくサンプルの数が極端に少ない（実数ベクトルなら2個だったりする）いので、速い。
ソフトマージンであっても、SVMの方が体感的には圧倒的に速い（ただし、独自実装のカーネルパーセプトロンとtinysvmの比較）。

ということで、
せっかくカーネルパーセプトロンを実装したのに遅くて残念（というか早く気づけ）という話でした。

＜今後の課題＞
可能なアプローチとしては
1. キャッシュを使う
2. カーネルを使わず組み合わせ素性（など）で事前に展開する
3. 覚えるサンプルを選択して数を減らす

とりあえず 1. をやってみたけど、
・キャッシュの実装が悪いと効かない（当たり前）
・収束が速い（けれども訓練データに実質的な重複があったりしてサンプルが多い）ときに効かない。これはNLPでよくある。

2. は実用的にはありだと思う。
ただし、カーネルを使うのをあきらめるというのに等しい。

3. は研究方面ですでにいくつか手法が出ている。
Projectron など。
特に、テスト時の計算時間を短くできるのが魅力的。
ただいかんせん線形でしか効かない＆ドラスティックに減らすと性能が落ちるのが明らかなので、決定的な高速化手法ではない。

＜補遺＞
名前は Averaged Kernel Perceptron （平均化カーネルパーセプトロン）という方がいいかもしれない。
↓はそう言っている。
http://alias-i.com/lingpipe/docs/api/com/aliasi/classify/PerceptronClassifier.html
上記のドキュメントは lingpipe の javadoc ですが、アルゴリズムの説明が書かれています。
実装したいときには、論文読むよりわかりやすいかも。

Maybe I missed something but I don't understand why he/she and others say that Kernel Perceptrons is faster than SVMs ...
http://blog.so8848.com/2008/04/26046.html

2009-03-19

Javaで実装された形態素解析器 GoSen

nlp mima

GoSen がよさげなので使ってみる。

プロジェクトホームページ（オリジナルは到達不能）
http://web.archive.org/web/20071224025014/http://itadaki.org/wiki/index.php/GoSen

GoSen is a comprehensive rewrite and upgrade of Sen, a pure Java LGPL morphological analysis library for Japanese which in turn was based on MeCab.
GoSen is at present a de facto fork of Sen. It would be extremely useful if the work performed to create GoSen could be folded back into the base Sen project; unfortunately, the original authors of Sen seem to be uncontactable at the present time.

Sen の作者も到達不能。

ソースは sourceforge で生きている。
http://itadaki.svn.sourceforge.net/viewvc/itadaki/GoSen/

git-svn clone https://itadaki.svn.sourceforge.net/svnroot/itadaki/GoSen GoSen

とりあえずプロジェクトルートで

ant

辞書のダウンロード＆コンパイル

cd testdata/dictionary/; ant

プロジェクトルートでGUI起動

java -cp $CLASSPATH:bin:gosen-1.0beta.jar examples.ReadingProcessorDemo testdata/dictionary/dictionary.xml

javadoc もある。

ant javadoc

gcj-1.5 だと

[javadoc] java.lang.RuntimeException: Only he following values are currently supported for option -source: 1.2, 1.3, 1.4.

このようなエラーがでたので、 build.xml の source="1.5" というアトリビュートを削除して生成。

via
http://d.hatena.ne.jp/gnarl/20080912/1221189985
http://pc11.2ch.net/test/read.cgi/tech/1106606281/

(2009-04-16T22:40:30+0900)
Senからのクラスの読み替えなど
http://hide-t.vox.com/library/post/gosen.html

使っている人
http://tf0054.blogspot.com/2009/04/java-gosen.html

2009-03-03

英語の単語を原形に戻す WordNet-based lemmatizer

prfr nlp ruby

nltk の実装を移植する。
http://nltk.googlecode.com/svn/trunk/doc/api/nltk.corpus.reader.wordnet-pysrc.html#WordNetCorpusReader.morphy

使う情報:

WordNet の ${WNHOME}/dict/*.exc 不規則変化
WordNet の ${WNHOME}/dict/index.* 語基
品詞ごとの接尾辞ルール（上記ソースにべたがきされている）

#! /usr/bin/env ruby
# -*- coding: utf-8; mode: ruby -*-

# port from nltk.corpus.reader.wordnet.morphy
# http://nltk.googlecode.com/svn/trunk/doc/api/nltk.corpus.reader.wordnet-pysrc.html#WordNetCorpusReader.morphy

require 'stringio'

class String
  def endwith(s)
    self =~ /#{s}$/
  end
end
class Lemmatizer
  MORPHOLOGICAL_SUBSTITUTIONS = {
    :noun => [['s', ''], ['ses', 's'], ['ves', 'f'], ['xes', 'x'],
                ['zes', 'z'], ['ches', 'ch'], ['shes', 'sh'],
               ['men', 'man'], ['ies', 'y']],
    :verb => [['s', ''], ['ies', 'y'], ['es', 'e'], ['es', ''],
               ['ed', 'e'], ['ed', ''], ['ing', 'e'], ['ing', '']],
 
    :adj =>  [['er', ''], ['est', ''], ['er', 'e'], ['est', 'e']],
    :adv =>  []}
  
  def initialize(files=nil)
    @wordlists = {}
    @exceptions = {}
    MORPHOLOGICAL_SUBSTITUTIONS.keys.each do |x|
      @wordlists[x] = {}
      @exceptions[x] = {}
    end
    if files then
      files.each_pair do |pos,pair|
        load_wordnet_files(pos, pair[0], pair[1])
      end
    end
  end
  def open_file(*args)
    if args[0].is_a? IO or args[0].is_a? StringIO then
      yield args[0]
    else
      File.open(*args) do |io|
        yield io
      end
    end
  end
  def load_wordnet_files(pos, list, exc)
    open_file(list) do |io|
      io.each_line do |line|
        w = line.split(/\s+/)[0]
        @wordlists[pos][w] = w  # TODO: @wordlists and @exceptions can be merged
      end
    end
    open_file(exc) do |io|
      io.each_line do |line|
        w,s = line.split(/\s+/)
        # TODO: the ordering [w][pos] might give better performance
        @exceptions[pos][w] ||= []
        @exceptions[pos][w] << s
      end
    end
  end
  def lemma(form,pos)
    each_lemma(form,pos) do |x|
      return x
    end
    return form
  end
  def _each_substitutions(form,pos)
    if lemma = @wordlists[pos][form] then # check whether form is in wordlist
      yield lemma
    end
    MORPHOLOGICAL_SUBSTITUTIONS[pos].each do |entry|
      old,new = *entry
      if form.endwith(old)
        _each_substitutions(form[0,form.length-old.length]+new,pos) do|x|
          yield x
        end
      end
    end
  end
  def each_lemma(form, pos)
    if lemma = @exceptions[pos][form] then # check illegular inflections
      lemma.each{|x |yield x}
    end
    if pos == :noun and form.endwith('ful') # special fix for -ful nouns
      each_lemma(form[0,form.length-3], pos) do |x|
        yield x+'ful'
      end
    else
      _each_substitutions(form,pos) do|x|
        yield x
      end
    end
  end
end

(2009-03-08T19:33:14+0900)
上記 nltk の実装は pywordnet から来ており、元々は wordnet が使っているアルゴリズムを移植したもの。
${WNHOME}/lib/morph.c
タイムスタンプによると、十年以上変わっていないらしい。

Revision 1.1 91/09/25 15:39:47

2009-03-01

ruby 1.9 test/unit/ui/console/testrunner のバグ

ruby

現在の ubuntu 8.10 でインストールできる ruby1.9 は test/unit がうまく動かない。
（バージョン：ruby 1.9.0 (2008-06-20 revision 17482)）
具体的にはこういうエラーが出る。

/usr/lib/ruby/1.9.0/test/unit/ui/console/testrunner.rb:94:in `sub!': can't modify frozen string (RuntimeError)

回避するためには、新しいバージョンの ruby を使うか、test/unit の該当個所を修正する。
前者のやりかただと、 ruby 1.9.1p0 (2009-02-13 revision 22266) なら問題ない。
後者のやりかただと、下記のように test_started メソッドを修正すればいい。

93,95c93,94
<             $program_name = $0
<             alias $0 $program_name
<             $PROGRAM_NAME += "\0#{name}"
---
>>
            $0 += "\0#{name}"
            $0.sub!(/\0.*\z/, '')
<<

2009-02-27

論文や学術雑誌での欧文略語

research

ISSN によるリスト（英語、フランス語、ドイツ語をはじめとして多くのヨーロッパ言語をふくむ）
http://www.issn.org/2-22661-LTWA-online.php

JSTによる日本語の学術情報流通のための指針：雑誌名
http://sist-jst.jp/handbook/sist05_2007/main.htm

JSTによる日本語の学術情報流通のための指針：機関名
http://sist-jst.jp/handbook/sist06_2007/main.htm