前の月 / 次の月 / 最新

~matubara/ChangeLog / 2005-09移動しました

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

2008 : 01 02 03 04 05 06 07 08 09 10 11 12
2007 : 01 02 03 04 05 06 07 08 09 10 11 12
2006 : 01 02 03 04 05 06 07 08 09 10 11 12
2005 : 01 02 03 04 05 06 07 08 09 10 11 12

2005-09-29 Thu

Emacs [linux][emacs][net]

<http://www002.upp.so-net.ne.jp/mamewo/emacs.html>
Emacs を使い易くする設定いろいろ。

Emacs の shell で日本語表示 日本語入力 [linux][emacs]

(add-hook 'shell-mode-hook
  '(lambda ()
     (set-buffer-process-coding-system 'euc-jp 'euc-jp)))

Howstuffworks "How DNA Evidence Works" [bio][net]

<http://science.howstuffworks.com/dna-evidence.htm/printable>
DNA鑑定で2つのDNAシークェンスの持ち主が同一であるかどうかの根拠というのは、
基本的には、シークェンスを母集団としてサンプリングして検定する、
という感じらしい。(ほとんど読んでいない)

2005-09-28 Wed

Conditional Random Fields [nlp][net]

<http://www.inference.phy.cam.ac.uk/hmw26/crf/>
CRFに関係する論文、ソフトウェアのまとめサイト。
CRF は構造型データのラベルづけの確率モデル。

2005-09-26 Mon

Language Evolution and Computation Research Unit [lx][net]

<http://www.ling.ed.ac.uk/lec/research.html>

Evolving Communication through the Inference of Meaning. Andrew Smith (2003)

など、博士論文が置いてある。

2005-09-24 Sat

輪講 Argamon et al.のMDL変化分定式化への指摘 [segmentation]

p に関する再分割において、
コーパス中の新morph p の部分による符号長増加分は、

|V_p| / N

として、p がそれ以前にmorphとして存在していないことを仮定している。
つまり、同一の接頭辞が2回とりだされること想定していない。

改良:
増加 -log(P^(p)); P^(p)=B(p)/(N+B(p)) のみだったのを
減少 log(P(p)); P(p)=C(p)/N と、
増加 -log(P^(p)); P^(p)=(C(p)+B(p))/(N+B(p)) とする。

いずれにしろ(辞書・コーパスの他の大部分によらず) p にのみ依存する表現。

ヒンディー語の世界にようこそ [lx][hindi][net]

<http://www.aa.tufs.ac.jp/~kmach/>

ここでは、主に南アジアおよびヒンディー語に関する研究成果と
それを応用したコンテンツを公開しています。

デーヴァーナーガリー文字の書き方とか。

2005-09-23 Fri

三項演算子の正しい書き方ってあるのだろうか [javascript][programming][net]

<http://la.ma.la/blog/diary_200509220220.htm>

Test.Builder.globalScope = 
 (typeof JSAN    != 'undefined') ? JSAN.globalScope :
 (typeof window  != 'undefined') ? window :
 (typeof _global != 'undefined') ? _global :
 null;
三項演算子は(すくなくともJavaScriptでは)右結合。
条件式に括弧を付け、if文ぽく書くと読みやすい、という意見。

2005-09-20 Tue

大量のファイルを効率的にコピー [linux][howto]

tar c FROM/ | (cd TO/ && tar x)
FROM/* を、TO/FROM/* にコピー。

2005-09-17 Sat

projects/segment/segnaive/Segment.java [segmentation][java]

Java は仮想メモリを使えない?
現在のプログラムでは3Mバイトのデータを扱えない。(途中でメモリが足りずに Error 終了)
まあ、仮に使えたとしても使いものにならない速度の気がする。
節約のため、Bigramの過去の履歴を放棄しなければならない。
みたい場合もあるので、簡単にOn/Offできればいいんだけれど。

2005-09-15 Thu

Java プログラム中からVMの設定を変更する [java]

[2005-09-03]……のはたぶん無理。
メモリ使用量を見るのは、java.lang.Runtime.なんとか。

報告会での指摘のまとめ [segmentation]

Creutzの確率モデルによる単語分割のアルゴリズムについて:
探索には接尾辞配列などの効率的なデータ構造を使うのではないか。
ArgamonらのMDL原理の手法について:
データ構造を見極めること。
両者について、一応実装の可能性を探る。
同時に、パープレキシティ基準による単語片併合の実験を続ける。

パープレキシティの対数をとったものは、エントロピーに等しい。
→ 対数パープレキシティとエントロピーのグラフは、2軸にする必要がない。
というか、エントロピーはユニグラム確率に対するものだけではない、ということ。
対数パープレキシティは、エントロピーの別名と考えてもよい。
ということで、パープレキシティとエントロピーの混在には注意する。
特に、今回はunigramエントロピーと、対数trigramパープレキシティを併記したので混乱を招く。

2005-09-13 Tue

PPM*言語モデルによるパープレキシティ [segmentation]

パープレキシティ:
ある言語モデルのもとで、対象テキスト(単語列、文字列)が生成される確率の逆数の、
単語(文字)あたりの平均。
たとえば、w1,w2,w3,w4 という単語列に対して
perplexity = ( P(w4|w1w2w3) P(w3|w1w2) P(w2|w1) P(w1) ) ^ (-1/4)
n 乗根を嫌って、
log perplexity = -1/4*( log P(w4| ) + log P(w3| ) + log P(w2| ) + log P(w1) )
もよく使われる。
言語モデルがbigram言語モデルであるときは、
perplexity = ( P(w4|w3) P(w3|w2) P(w2|w1) P(w1) ) ^ (-1/4)

PPM*言語モデル:
確率推定の際に、可変長の文脈(その文字より前の接頭辞の接尾辞)を用いる。
文脈となりうるコーパスの部分文字列の集合を保持する、文脈トライを用いる。
文脈トライは、各ノードまでの部分文字列の頻度をノードに保持する、接尾辞トライである。
ただし、頻度1となったノード以降は、頻度1がコーパスの最後まで続くため、以降をコーパスの中へのポインタとして縮約する。

PPM言語モデルである文字列中の文字が生成される確率は、それまでの文脈のうちに決定性文脈が存在する場合とそうでない場合で
異なる計算がなされる。

決定性文脈とは、それまでの文脈の次の文字が、コーパスでは1種類しかないような文脈である。
言い替えれば、ある文脈が決定性文脈ならば、それまでの文脈がコーパスに存在していなければならず、なおかつ、
コーパスで2種類以上の文字を導いていてはならない。
決定性文脈が存在する文字については、最小の決定性文脈が与える確率を採用する。

ここで、その文字が文脈から導かれている文字と異なっている場合どうするか?
エスケープ確率という考え方を導入する。Method Cにおいて、ある文脈での文字とエスケープの確率は、
その文脈での各文字の頻度(文字の確率に対応)と文字種の数(エスケープの確率に対応)の比率により計算する。
文脈からその文字が導かれていない場合、エスケープ確率と、1つ小さい文脈でのその文字の確率の積を、求める確率とする。

決定性文脈が存在しない場合、対象文字(位置)に対する、コーパスに存在する最長の文脈での確率を採用する。

Referrer (Inside): [2005-11-13-5]

PPM*言語モデルを用いた日本語単語分割 (北2000) [segmentation]

2005-09-12 Mon

接続確率最小法による教師なし単語分割 (飯塚2000) [segmentation]

文字列 C[i-n .. i] が”単語”であるなら、(つまり C[i] が単語の終わりなら)、
C[i-n .. i-1] から C[i] を高い確率で予想できるのに対し、
C[i-n+1 .. i] から C[i+1] を低い確率でしか予想できない。
すなわち、
P( C[i] | C[i-n .. i-1] ) > P( C[i+1] | C[i-n+1 .. i] )

これを発展させて、位置 i の直後で分割が起きる<=>

JavaScript -- The Definitive Guide [net]

<http://www.unix.org.ua/orelly/web/jscript/index.html>
O'Reilly の本。

2005-09-11 Sun

Suffix Array を用いた日本語単語分割 (伊東1999) [string][segmentation]

基本的には、対象文字列の区間と一致している事例データの区間を見つけ、
そこでの分割を真似する、という方法。
対象文字列中の各位置からの部分文字列のうち、事例文字列に現れ、
かつ長さ極大の部分文字列に対する事例での分割を類似度の重みつきで採用する。
ここで類似度はその部分文字列の長さそのものとする。
たとえば、対象文字列での現在位置からの部分文字列がabcd..で、
事例としてabxx(++ )、abcdxxx(+--- )の2つがあったとする
(+はその位置の直後で分割があることを示す)
正なら分割することを示す各位置に対するスコアを
0 (a): 2 + 4
1 (b): 2 + -4
2 (c): -4
3 (d): -4
と求める。

最長一致部分文字列の選択には接尾辞配列を利用する。
現在位置の文字から順に、その文字の接尾辞配列上での出現位置を2分探索していき、
見付からなくなった直前が最長一致である。

もっとも単純には、この照合を、対象文字列中の位置0から順にすべての位置にたいして行う。

2005-09-09 Fri

Collection & Copy [net]

<http://d.hatena.ne.jp/brazil/>
JavaScript関係。ドキュメントの翻訳など。

2005-09-06 Tue

Ukkonen の線形時間での接尾辞木構築アルゴリズムの実装 [java][algorithm]

データ構造は
http://www.dogma.net/markn/articles/suffixt/stree.cpp
を参考にした。
ノードと枝ラベルの先頭文字から、枝を引くことができる連想配列。

初期化:1文字の接尾辞木
根と、1つのノード、それらの間の枝。
根のsuffix linkは自分自身に。葉はnull。

1文字追加
前回、追加されずに枝の途中で終わった新規ノード(implicit nodeとして作られたノード)
と同じ開始インデックスの接尾辞から追加する。
(それ以前のは、葉ノードをともなう追加で、内部ノードが追加された場合でもsuffix linkが付けられている)
最初は、根からたどる。
ノードからたどれる枝がなかった場合、新しく葉ノードと枝を作り、分岐させる。
ノードからたどれる枝の途中の位置で、追加したい接尾辞が終わっていた場合、なにもしない。
追加したい接尾辞

2005-09-04 Sun

Map<T> ではまった [java]

Map<T> や Set<T> を使う場合、クラスTは、
hashCode(), equals(Object o) をオーバーライドしている必要がある。
equals()について2つのオブジェクトが等しいなら、両者のhashCode() が一致する。

ジェネリックを使っていても、equals(T t)は決して呼び出されないのに注意。
そのようにオーバーライドしていると、等しいはずのものが(Objectクラスのequals()によって)等しくない、と判定されてしまう。

2005-09-03 Sat

LLDN - プログラム [programming][net]

<http://ll.jus.or.jp/2005/details/program/>
Light weight Language のスペシャリストの会合。
言語の特徴の解説や、おもしろいデモなどの資料へのリンクあり。

Ukkonen's algorithm to construct Suffix Tree [string][algorithm]

概念
対象文字列の最後尾に1文字増えたとき、接尾辞木を更新する。
ただし、ここでの接尾辞木は終端文字を含まず、葉以外のノードで接尾辞が終わることもあるような木である。
対象文字列にxが追加されたとき、それまでの任意の接尾辞aをaxに変えることがこのアルゴリズムの目的。
1. aが葉で終わる接尾辞のとき …… 葉の終端枝にxを追加するだけ
2a. aが葉ではなく、xで始まる枝が出ていない分岐ノードで終わるとき …… x の枝を追加する
2b. aが枝の途中で終わるとき …… ノードを作り、それまでの枝の続きとxの枝を追加する
3. それ以外、すなわちaがxで始まる枝を持つノードで終わるとき … なにもしない

Argamon et al のデータ構造 [segmentation]

データ構造 Main Suffix TrieとReversed Prefix Trieは、
それぞれ、全ての単語に関する接尾辞木である、一般化接尾辞木の構築アルゴリズムを真似た、
trieだと思われる。

一般化接尾辞木(Generalized Suffix Tree)とは、複数の文字列に対する接尾辞木を併合したもの。
その構築法は、GusfieldのAlgorithms on Stringsに書かれている。
Ukkonenの接尾辞木構築アルゴリズムに基づくもの。

Topic #7 -- Tries and suffix trees [algorithm][string][net]

<http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic7/>

trie(トライ)とは、k分位置木 (k-ary position tree)
で、辞書(連想配列)へのアクセスを効率化するためのデータ構造である。
辞書は、ある文字列がその辞書に入っているかどうかを調べる機能を持つ。
文字列のアルファベットは定数個とし、文字列には端記号が付けられているものとする。

非コンパクトtrie
枝のラベルがすべて1文字。
調べたい文字列の文字に対応する枝を、先頭文字から順にたどり、葉に行き着けば辞書にその文字列がある、ということ。
連想配列の場合、葉に、その文字列に対応するデータがある。
実装には、各ノードにアルファベットの大きさのポインタの配列を置く方法と、
配列ではなく連結リストでポインタを保持する方法がある。

コンパクトtrie
非コンパクトtrieにおいて、葉の直前の、分岐のないノードを削除したもの。
調べたい文字列の文字の枝をたどり、葉に行き着いたとき、
葉に格納されている文字列(文字列の残りでもよい)と調べたい文字列を比較し、一致すればその文字列がある、ということ。

PATRICIA[2005-09-03-1]
コンパクトtrieにおいて、分岐のないノードを統合したもの。
枝につくラベルは1文字以上になる。
通常、サイズ2のアルファベットで構成し(サイズがそれ以上ならサイズ2のアルファベットに符号化し)、
ノードに文字列中での分岐位置を格納し、枝には文字をラベル付けする。
調べたい文字列に対応する葉に行き着く方法:
ノードに書かれた位置の文字に対応する枝に進む。
葉に着いたら、そこに格納された文字列と調べたい文字列を比較し、一致すれば「ある」ということ。

suffix trie
ある文字列に対するすべての接尾辞を格納する辞書である、
非コンパクトtrie、または、コンパクトtrie、PATRICIA。
特に、PATRICIA、つまり、全ての分岐のないノードを統合したものを、Suffix Treeという。

Referrer (Inside): [2005-09-03-1]
Referrer (Inside): [2005-09-15-2]

2005-09-02 Fri

Shlomo Argamon et al, Efficient Unsupervised Recursive Word Segmentation Using Minimum Description Length [segmentation]

単語中の形態素を発見するアルゴリズム。

形態素辞書と、単語の集合で初期化する。
辞書とそれによって符号化したコーパスの記述長をもっともよく減らす
接頭辞形態素を見つけ、それを辞書に追加する。
記述長を減らす接頭辞が存在しなくなれば終了。

接頭辞を形態素辞書に追加したときに記述長がどれだけ増えるかを、
局所的に計算可能にして、効率化している。

辞書のデータ構造は2重のtrieと、
各接頭辞の局所記述長の増分による順序付のヒープ。

各ノードに至るまでの枝が、接頭辞を表す Main Suffix Trie と、
すべての単語の文字列を逆転させて構成した、
各ノードに至るまでの枝が、接尾辞を表す Reversed Suffix Trie を併用。

RSTのノードから、MSTの対応接尾辞で終わるノードへのポインタがある。
(1対多)

trie の初期化にはよく知られたアルゴリズム(Gusfield 1997のAlgorithms on Strings

Referrer (Inside): [2005-11-27-2] [2005-09-03-4]

2005-09-01 Thu

自然言語的データに対する接尾辞配列の構築 [string][segmentation][algorithm]

接尾辞配列を直接構築する方法のほとんどは、
全部をソートせず、一部分だけをソートし、
残りは接尾辞同士の関係から順序を決める、というものが多いようだ。
直接構築でないのは、いったん接尾辞木を作る方法。

また、自然言語データは、長い部分一致箇所がある
ことが多い(引用など)ので、一般的なソートの性能が悪くなりやすい。
これを解決する目的で作られたアルゴリズムもある。

- リコーの伊東さんによる、二段階ソート法
まず、接尾辞を最初の1文字でソートする。(バケットソート)
最初の1文字によって分けられた区間が出来る。
これらの区間内のソートができれば、接尾辞配列が完成する。
2文字目と1文字目が、辞書式順序にしたがっている場合は、そのまま

長い部分一致長により性能が悪化するので、
それを防いだ発展型のアルゴリズムが、
実用上、高速といわれているみたい。

- Larsson, Sadakane法


- Skew algorithm
mod 3で1、2になる部分について、

2008 : 01 02 03 04 05 06 07 08 09 10 11 12
2007 : 01 02 03 04 05 06 07 08 09 10 11 12
2006 : 01 02 03 04 05 06 07 08 09 10 11 12
2005 : 01 02 03 04 05 06 07 08 09 10 11 12

最終更新時間: 2009-02-01 00:57

Powered by chalow
inserted by FC2 system