~/.wl に追加しておくと、 Summary モード -> "S" の候補に "reply-date" が出る。
これを選んでやると Summary が GMail 風にソートされる。
(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)
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 にも触れている。
要約すると、
カーネルパーセプトロンを使うくらいならサポートベクターマシンを使ったほうがいい
という話。
以下、パーセプトロンとかカーネルとか基本的なところばかり書きます。
＜パーセプトロン＞
正負ラベルを予測する二値分類を行うパーセプトロンの場合、以下のアルゴリズムで訓練する。
・以下を、重みが収束するまで繰り返す
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 ...
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
nltk の実装を移植する。
使う情報:
#! /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
