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-11-28-1] では連結によって記述長差分に影響を受ける2-gram についてのみ、
記述長差分を再計算する、とした。
けれども、もっと詳しく見れば、
記述長差分を構成する項のうち、影響を受ける項だけを更新することもできるはず。
そこで、差分の差分のようなものを定式化することにより、
コーパス長差分の更新が定数時間で行えるのでは？
CD の連結に際して、AB連結によるコーパス長差分がどれだけ変化するかを考える。
A=C, A=D, B=C, B=D の場合は、影響範囲がAB以外に関する符号化の部分全体に及び、
変化の計算と再計算の手間があまり変わらないので、普通に再計算する。
そうでない場合、つまり AB と CD の全ての単語が相異なるときは、
一定の数の項しか影響を受けないので、その部分に関する増減を式で与えれば、
そのような AB のコーパス長差分の更新は一定の時間で行える。
/usr/X11R6/share/cursors/xorg-x11/
以下にあるディレクトリの名前が、カーソルのテーマの名前。
たとえば whiteglass というテーマを使いたいときは、
~/.Xdefaults
に
Xcursor.theme: whiteglass
と書く。
カーソルの大きさも
Xcursor.size: 30
のように設定できる。
（半透明カーソルで大きめにすると見やすいと思う）
システム全体に適用するには
/usr/X11R6/share/cursors/xorg-x11/default/index.theme
に
[Icon Theme]
Inherits=whiteglass
apt のパッケージには競合するパッケージの組がいくつかある。
そのひとつが、印刷システムの lprng と cups。
cups をインストールしているときに、lprng に依存するドライバを手動で
dkpg -i hl5070liblpr.deb
のような感じでインストールしようとすると、
インストールが失敗し、さらにアンインストールもできない状態になり、
apt の依存関係解決自体が動かなくなる。
対処：
/var/lib/dpkg/available
/var/lib/dpkg/status
/var/lib/aptitude/pkgstates
をエディタで編集し、該当エントリを削除する。
/var/cache/apt/pkgcache.bin
/var/cache/apt/srcpkgcache.bin
を削除（または移動）して、
apt-get update
aptitude update
表題：言語モデル性能の改善を目指した最小記述長原理にもとづく単語分割
概要：
自然言語処理において、統計的言語モデルは音声認識、機械翻訳など幅広い応用に用いられている基礎的手法のひとつである。統計的言語モデルは、文を単語列として見たとき、ある単語の出現確率をその単語の前に現れる単語を条件とする条件つき確率として与える。
言語モデルの性能は、クロスエントロピー、すなわち、学習に用いた単語列と独立なある単語列に対して与えられる確率の高さ、もしくはパープレキシティ、すなわち、単語列の場合の数の期待値の低さにより計られる。
一般に言語モデルの構築にあたっては、言語学的単位の単語を基準として、対象データを分割することが多い。辞書ベースの分割方法では、その言語の専門家が用意した辞書を用いる。教師あり機械学習に基づく分割方法でも、専門家によって与えられた分割を目標にして学習が行われることが多い。しかし、言語モデル構築を目的とする場合、単語の単位は言語学的単位にしばられる必然性はなく、対象領域やスタイルに適応した単位の言語モデルによって性能があげられることが報告されている。
本研究では、言語モデル性能の最大化を目的とする、言語知識を用いない単語分割法を提案する。この方法では、まず、学習データを可能な最小の単位である文字に分割する。そうしてできたセグメント列を、辞書の構築とともに組織化していく。組織化は、連続して出現するある2セグメントを連結することを1ステップとしている。連結候補の選択の基準として最小記述長原理を採用し、記述長を与える符号化としては、1重マルコフ性近似と辞書の構築に基づく符号化を採用する。また、各ステップにおいて、前のステップの分割によって得られる候補のうち、基準に対してもっとも好ましい連結を即座に実行するという貪欲な探索手法を採用する。
提案されている単語分割手法による言語モデルは、XXのデータにおける実験において、既存の単語単位言語モデルと superword 言語モデルを上回る性能を示した。
計算時間の低減、現実的なスケールのデータに対する性能評価、2重マルコフ性への拡張、探索範囲のN-bestへの拡大が今後の課題である。
Statistical language models are fundamental methods in a number of applications of natural language prosessing, such as speech recognition and statistical machine translation.
Performance of a statistical language model can be measured with Cross Entropy, the probability given to a sentence that is independent of its learning data, or Perplexity, the mean number of branches of probable sentences.
In construction of N-gram models, word as a linguistic unit is commonly used to segment a sentence. However, it is reported that language models whose segmentation units are adapted to the target domain or style outperformed word-based models.
In this research, as a framework that gives the segmentation that enables to maximize the performance of the language model on it while avoiding overfitting, we propose a method based on the Minimum Description Length that encodes the learning data with a coding on a constructed dictionary and approximation of 1st order markov property.
A language model constructed with the proposed method outperformed existing word-based language models and other adapted language models in an experiment in XX data set.
Future work should be done to decrease computing time, to evaluate perfomance in more realistic sclae data, to extend the model to 2nd order markov property and to enhance the search range to N-best.
「上回る性能」を示すといいな、と。
手法について、もっとくわしく書こう。（一番重要）
パープレキシティとかエントロピーとかの説明がおかしいかも。
１重マルコフ性とかいういい方も、それでいいかよく考えよう。
現在の実装↓
データ：
{
本体文字列の連結リスト
単語1〜4gramの出現頻度を保持するハッシュ
}
for(;;) {
1) 連結した場合の記述長変化分が最小の候補を求める：
{
foreach [ 連結候補 <- 単語 2-gramのすべての種類 ] {
1.1) 連結した場合の記述長変化分の計算：
{
連結候補 AB の連結される出現に関連する変化分（定数個）
AB の連結されない出現に関連する変化分（定数個）
foreach [ その他の単語 <- A,B 以外の単語すべて ] {
その他の単語の出現に関連する変化分
}
}
}
}
1.2) 最小の候補の記述長変化が正なら、手続き全体を終了
2) 連結による本体文字列（連結リストとして表現されている）の更新：
{
foreach (大きさ2の窓で本体文字列を走査して単語 2-gramの出現を調べる) {
2単語が連結対象なら、つなげる
}
}
3) 頻度情報の更新
{
foreach (大きさ4の窓で本体文字列を走査して単語 2-gramの出現を調べる) {
1,2,3,4-gram の出現頻度を数える
}
}
}
1) は大雑把に見て 単語 2-gram の種類数 x 単語 1-gram の種類数に比例する計算時間。（だいたい、単語1-gramの種類数の３乗ともいえる）
2), 3) は本体文字列の長さに比例。
本体文字列を長くしていったときに、
単語 1-gram の種類数の3乗は（連結による新単語を考慮しても）本体文字列の長さよりは鈍い増加になると思われる。
（語彙数は延べ語数よりも増加が遅い）
が、いまのところ、本体文字列は小さめでやっているので、
1) の方が 2), 3) よりも大きくなっている。
本体文字列を大きくした場合、1) の計算時間は 2) よりも小さくなるはずだが、絶対量に減る訳ではないので、とりあえず 1) に関する高速化を行う。
（なお、Suffix Tree, Suffix Vector を用いた高速化は、2), 3) の部分の高速化）
まず、データとして、
単語 2-gram をキーとし、それを連結した場合のコーパス長変化分を値としてもつハッシュを用意する。
このハッシュを連結に際して更新の必要な部分のみ、更新していく。
ループの最後に、
4) コーパス長変化分の更新
foreach [ 連結候補 <- 連結により記述長に影響を受ける2-gram ] {
4.1) 連結した場合のコーパス長変化分の再計算：
...
}
を加え、
foreach [ 連結候補 <- 単語 2-gramのすべての種類 ] {
1.1) 連結した場合の記述長変化分の計算：
...
}
を、
foreach [ 連結候補 <- 単語 2-gramのすべての種類 ] {
1.1) 連結した場合の辞書長変化分の再計算：
... ~~~~
}
にする。
「影響を受ける2-gram」は、連結される出現に付近２単語以内に現れる単語を少なくとも１つ含む 2-gram。
これは 2) か 3) の走査のときに同時に調べておける。
これにより 1) は 単語 1-gram の種類数 に比例する計算時間で済み、
4) も、影響を受ける候補の数がだいたい 連結される 2-gram の出現頻度 x 単語 1-gram の種類数 程度なので、
連結の頻度 x 単語 1-gram の種類数の2乗 程度になる。
影響を受ける2-gram は全2-gramに含まれるので、コーパス長計算回数の絶対数は、確実に減る。
計算時間の改善の見通しとしては、よくて、10分の1に抑えられる、くらいか？
結局、1.1)、4.1) が定数時間でできなくなったということが痛い。
定式化をいまいちど見直して、
あと、他の高速化ポイントとしては、
3) の頻度情報の更新は全部操作しなくてもできる、というところがある。
2) に関しては、任意の2-gramから、その全ての出現を引けるハッシュを持っておけば、
全部走査しなくてもできるが…
A,B の連結を行うまえとあとで、
A,B の連結により影響を受けない（記述長計算にかかわる範囲での文字列の連結状態が変わらない）差分の再計算をしないようにする。
こうしたことが必要になったのは、記憶のない符号化に比べて計算時間が増えたため。
だいたい、辞書エントリの個数を掛けたくらいの時間がかかる。
（開始時で、1000倍〜3000倍。徐々に悪化する）
現状：
各bigramに関して、1ステップごとに、その時点で連結したら記述長がどれだけ変わるかを、そのつど計算している。
改良後：
各bigramに関して、連結したら記述長がどれだけ変わるかを常に保持する。
連結のたびに、その情報を（必要があれば）更新する。
１つ前、２つ前、３つ前、１つ後からそれぞれ影響を受ける項がある。
#(CDAB)=0, #(DAB)=0, #(AC)=0 ... ならば、
CDの連結に際して、ABの連結による差分が影響を受けない。
そうでなければ再計算する。
そういえば [2005-09-02-1] も、木のノードに、
記述長変化分の情報を保持していた。
記憶のない符号化の場合も（実装はしていなかったが）
差分の更新は連結された文字のみでよいので簡単。
<http://kanaya.aist-nara.ac.jp/Zope/member/nishio/japanese>
WindowIterator[2005-11-25-1] があった。
配列上でウィンドウをずらしながらある処理をしたい
Python と Java のコード例と、時間測定。
Java だったら、WindowIterator は List を（作って）繰り返す Iterator にするよりも、
Iterator を繰り返す Iterator にした方がいいのは確かだなあ。
いま（JDK 5.0）なら、Iterable を返す Iterator になるか…
複数文字列を含む区間をひとまとめに符号化するときに、重複なしで数える必要がある。
（つまり連結対象文字の連結される出現）
たとえば、コーパス AAAA 上で AA を連結するとき。
コーパスの左端から順に連結していくことを想定すると、
通常の（重複あり）頻度＝3を、 連結対象となる符号化区間の数としてはならない。
符号化区間はたがいに重複してはいけないから（おなじ部分を2回符号化することになる）
そのほかの確率の計算で用いる頻度は、すべて重複ありでよい。
2回符号化してはいけない、ということに関連して、
ABの連結のときと同じ計算を B=A のときにしてしまうと、
A に関する符号化と B=A に関する符号化が重複するのにも注意。
[2005-11-08-6]の方法。
1文字の符号長を固定にしていたのは、辞書の符号長の差分の計算を、
辞書エントリの数に依存せずに計算するため。
いま考えている記憶のある符号化では、コーパスの符号長を計算するときに辞書エントリ全体を走査するので、
辞書内での文字の出現頻度のカウントも同時にやってしまえる。
<http://perldesignpatterns.com/?LambdaClosure>
Perl のレキシカル変数で lazy evaluation
レキシカル変数は関数呼び出しのたび生成され、それを参照するスコープが消滅するまで残る。
do {
my $head = sub {};
sub add_link {
my $link = shift;
my $next = $head;
$head = sub { $next->(@_); $link->(@_) };
}
sub run_links {
$head->(@_);
}
};
add_link sub{print "> @_\n"};
add_link sub{print "< @_\n"};
run_links('hello', 'world');
とやると、
> hello world
< hello world
と出る。
引数が格納される配列 @_ はレキシカルじゃないので、
関数ごとに独立している。（内側の関数から、外側の関数の@_は見えない）
（だから引数をまるごと渡して処理を委譲するときに、引数が長すぎると遅い…）
これは関数呼び出しだけを lazy に評価しているけれど、
tie を活用すれば変数参照も lazy にできるような気が。
int wsize = 2;
WindowIterator<Integer> it = new WindowIterator<Integer>(new Integer[] {10,20,30,40,50}, wsize);
while ( it.hasNext() ) {
foreach ( int x : it.next() ) {
System.out.println(x + " ");
}
}
// 10 20 \n 20 30 \n 30 40 \n 40 50 \n と表示される
連結リストでも配列でも効率的に動くようにするには、どう実装する？
List.subList() が返す部分リストは、コピーじゃなくて参照らしいけれど、
あんまり早くないような……
<http://acm.pku.edu.cn/JudgeOnline/>
千以上のプログラミングコンテスト。
<http://hosho.ees.hokudai.ac.jp/~shasegaw/presen_howto/index.html>
植物生態学的プレゼン。
表題スライドは
フォントサイズは40ポイント程度と大きくし印象を強くする。
さらに、可能なかぎり研究材料の綺麗で象徴となるような写真を配置したい。
「導入が大事」↓
導入部分がプレゼン全体に占める比率はかなり高い。
発表では「何をして」「どんな結果を得たのか」を述べることが大切である。
しかし、これら2つだけではほとんどの聴衆は納得しないはずだ。
「なぜそれをしたのか」、「どこが面白いのか」を導入部分ではしっかりと説明して聴衆が納得できるようにしたい。
Perl で行編集可能な CUI プログラムを作るときに使うモジュール。
おまけ：これがインストールされていると perl -d のデバッガが行編集可能になる。
<http://perldoc.jp/docs/modules/Storable-2.05/Storable.pod>
Perl でシリアライズ。
配列やハッシュの中のリファレンスを勝手にたどって保存してくれるので便利。
sagrep で索引データを格納するのに使っている。
書き込んだときと違うバージョンの Storable では読み込めない。
（バージョンアップでの互換性の保証がない）
ふつうの Suffix Tree は、文字列のランダムアクセス性を仮定している。
でも、いま考えている選択的アルファベット拡大（文字の連結によるアルファベットへの新文字追加）を
行うには、配列よりも連結リストの方が都合がいい。
連結リストではランダムアクセスはできない。
ランダムアクセスが必要になるのは、構築時、
枝のスキップや分岐ノードの作成を行うとき。
枝のスキップは、存在すると分かっている部分文字列に関して、マッチングをせずに、
ただ先のノードに進むこと。
これに関しては、枝の長さを別に保持しておけばよい。
分岐ノードの作成のときには、
「枝のラベルの開始位置から3文字目」のような形で分岐位置を指定する。
ランダムアクセス可能ならば、その位置が即座に分かるが、
連結リストの場合は、３つめの要素へのポインタは、実際に３つたどらないと分からない。
最悪計算時間は枝の最大長のオーダー。
ただし、ふつうは枝はあまり長くない。
長い枝は、（文脈によって区別される）ながいユニークな部分文字列にあたる。
- Krisztian Monostori さんの博士論文[2005-11-02-1]が原典
- suffix tree を格納する形式のひとつ
他の形式： suffix tree は木なので、一般的な木の格納形式が使える
suffix tree 特有の冗長性を利用した、より効率的な格納形式がありえる
- ほかにも冗長性を利用した格納形式はある（DAG とか）が、いまのところ実用上領域最小なのが Suffix Vector
- 冗長性：同型な部分木が多い
+ABC+--DEF
+--GHI
↑のような部分木があったとき、+BC+--DEF +--GHI
+C+--DEF +--GHI
[2005-11-18-1] の検索は sagrep で行った。
ディレクトリ pyxis:/home/data/documents/suffix_array
で、
sagrep "尼崎公害訴訟" yomiuri-2000 | ./get_context.pl
とやろうとしたら、yomiuri-2000 を作ったときと Perl のバージョンが違っていて動かなかったので、
sagrep_mksary -o yomiuri-2000 /home/data/documents/Yomiuri/sgml/2000
として作りなおし
sagrep "尼崎公害訴訟" yomiuri-2000 | ./get_context.pl
構築
sagrep_mksary -o yomiuri-2000 /home/data/documents/Yomiuri/sgml/2000
には10分くらいかかった。
<http://staff.aist.go.jp/y.motomura/>
ベイジアンネットに関するセミナー資料など
じかに \footnote と付けても表示されない。
\begin{tabular}{|c|c|c|}
1.234 \footnotemark& 1234 & 111 \\
\end{tabular}
\footnotetext{概算値}
1-gram 確率にもとづく文字あたり（＝全体での）エントロピー最小化の分割は、
2-gram, 3-gram での単語あたりエントロピーの低減には役に立たなさそう。
[2005-11-16-1]の
1-gram で最適なら、2-gram でもある程度よくなるのでは？
という考えが間違っていたということ。
ということで、記憶のある符号化に切替え、
2-gram 確率にもとづく文字あたりエントロピー最小化の分割を目指す。
記憶のある符号化での、符号長の変化をできるだけ局所的に求めるには、
すくなくとも連結対象が2回つづけて現れているという、
4単語連接の出現頻度、ほかに3単語、2単語、1単語の出現頻度を知る必要がある。
また、記憶のない場合と違い、辞書の大きさにすら依存しない記述長変化分の計算は無理な気がする。
新聞記事を集めたコーパスには「長く重複する部分文字列」が現れることがある。
同じ日に別の紙面で同じことがらを取り上げるとき、文章のコピー、引用が行われているようだ。
「尼崎公害訴訟」で毎日新聞1月31日を検索した例。
前後がまったく同じものがいくつかある。
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131271.txt:159: -31</DATE>n<TEXT>n 尼崎公害訴訟では、自動車排ガスに含まれる
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131202.txt:179: -31</DATE>n<TEXT>n 尼崎公害訴訟の神戸地裁判決は、道路公害に
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131264.txt:187: -31</DATE>n<TEXT>n 尼崎公害訴訟の神戸地裁判決は、道路公害に
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131273.txt:68: /SECTION>n<HEADLINE>尼崎公害訴訟 「一日も早く健康改善を」
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131278.txt:68: /SECTION>n<HEADLINE>尼崎公害訴訟 原告団長の松光子さん、勝訴
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131254.txt:68: /SECTION>n<HEADLINE>尼崎公害訴訟 国・公団が敗訴 初の差し止
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131276.txt:68: /SECTION>n<HEADLINE>尼崎公害訴訟 勝訴の垂れ幕に歓声 神戸
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131274.txt:68: /SECTION>n<HEADLINE>尼崎公害訴訟 勝利集会に３５０人 兵庫
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131266.txt:68: /SECTION>n<HEADLINE>尼崎公害訴訟 談話 その１ 【大阪】</HE
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131269.txt:68: /SECTION>n<HEADLINE>尼崎公害訴訟 談話 その２止 【大阪】 /mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131271.txt:68: /SECTION>n<HEADLINE>尼崎公害訴訟 排ガスだけの規制は限界 【
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131267.txt:68: /SECTION>n<HEADLINE>尼崎公害訴訟判決理由（要旨） 【大阪】 /mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131264.txt:76: >n<HEADLINE>［解説］尼崎公害訴訟 「強い違法性」指弾 求めら
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131266.txt:220: 中尾英夫・尼崎公害訴訟弁護団長 公害被害の因果関係
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131264.txt:1971: ◆尼崎公害訴訟の争点◆
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131267.txt:181: ３１日言い渡された「尼崎公害訴訟」の判決理由要旨は次の通り。
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131231.txt:124: う建設省、環境庁----尼崎公害訴訟・原告勝訴</HEADLINE>n<DATE>
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131202.txt:1524: が成立し、決着した。尼崎公害訴訟も関係者は今後、和解の可能性
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131264.txt:1516: が成立し、決着した。尼崎公害訴訟も関係者は今後、和解の可能性
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131186.txt:452: の差し止めを求めた「尼崎公害訴訟」の判決が３１日午前、神戸地
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131254.txt:387: の差し止めを求めた「尼崎公害訴訟」の判決が３１日午前、神戸地
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131202.txt:108: の新たな対策迫る----尼崎公害訴訟・神戸地裁判決</HEADLINE>n<D
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131186.txt:4941: 写真説明 尼崎公害訴訟で原告完全勝訴の判決に喜ぶ原
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131186.txt:3767: 換点に----中尾英夫・尼崎公害訴訟弁護団長n 公害被害の因果関
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131254.txt:4178: 写真説明 尼崎公害訴訟判決で「完全勝訴」と喜ぶ原告
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131254.txt:3660: 控訴するな 松光子・尼崎公害訴訟原告団長 n 差し止
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131244.txt:348: 策を問い続けてきた「尼崎公害訴訟」。国と阪神道路公団の責任を
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131278.txt:299: 策を問い続けてきた「尼崎公害訴訟」。国と阪神道路公団の責任を
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131244.txt:108: 身削って闘った」----尼崎公害訴訟、患者・原告「勝訴」</HEADLI
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131186.txt:3475: 訴断念を----松光子・尼崎公害訴訟原告団長n 差し止めを認めた
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131202.txt:2008: ◇尼崎公害訴訟の争点n ◇原告n ◆汚染と疾
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131186.txt:114: 排出差し止め命令----尼崎公害訴訟、神戸地裁が初判断</HEADLINE
/mnt/datastorage/documents/Mainichi/sgml/00/01/JA-000131231.txt:350: 「尼崎公害訴訟」判決が道路公害訴訟で初めて
新聞記事の言語モデルを1日分の記事から作ってみたが、
かなり性能が悪い。
同じ学習データを茶筌で分割したものから作った言語モデルと比べても、かなり悪い。
まず、学習データが少なすぎるので、意味のある比較はできない、というのがある。
MDLの方法は、学習データが少ないと知っている単語が少ないし、
学習データに最適なものを探すので、どうしても過学習におちいる危険性がある。
別の点として、新聞のような豊富な語彙を背景にしたデータよりも、
特定の分野に関する内容で、特定のスタイル（講演など）の「言語」を対象としたほうが、
MDLの方法にとって有利になるような気がする。
拡大されたSuffix Tree は文字単位ではなく単語単位のSuffix Treeとなり、
枝は「単語」でラベルづけされる。
単語は文字列なので、
ノードからノードに枝をたどるときには、
単語数で長さ 1 の枝でも、その文字数分のマッチが必要になる。
このため、単語単位 Suffix Tree での部分文字列（部分単語列）マッチでは、
１つの枝のラベルの先頭単語の文字数分の文字マッチが必要になる。
ふつうのSuffix Tree では、１つの枝のラベルの先頭文字のマッチだけで、
これに関しては定数時間。
言語モデルの性能向上という枠組で考えると……
単語単位の統計的言語モデルというものがある
↓
よい統計的言語モデルは、「ただしい文」に高い確率を割り当て「ただしくない文」に低い確率を割り当てる
↓
単語の単位のとりかたにより、統計的言語モデルの性能は変わりうる
（よく使われるフレーズは1単語の方がよい
P(w_{i-1}=わかり|w_{i-2}=?) x |P(w_i=やすい| w_{i-1}=わかり) より、
P(w_i=わかりやすい|w_{i-1}=?) の方が確率が高い）
↓
現在つかわれている単語の単位は、言語学的単位がベース
（事前に与えられる辞書を使う方法も、タグづけテキストからの学習の方法も）
言語モデルの性能を最大にする保証はない
↓
言語モデルの性能指標：クロスエントロピー[2005-11-13-1]が安定して低いほどよい
（ngramモデルでは、ngram確率の連積が高いことに相当）
↓
とりあえず、1gramでのクロスエントロピーを（closedで）最適化しよう
↓
全域最適は困難なので、単語辞書＝文字辞書の状態から、局所最適な連結を繰り返す探索をしよう
（探索が greedy）
↓ 中間報告会の時点で、ここ
局所最適＆辞書（と頻度情報）の更新を高速に見つけられるようにしよう
↓
更新を局所的に済ませるためには、suffix tree が都合がいい
（枝の付け替えとか、部分木の消去などを行うことに相当[2005-11-01-1]）
↓
ただし、suffix tree での局所的な更新は可能だが、わりと無駄が大きい
↓
suffix tree の表現のひとつ、suffix vector がこのような目的に適した表現のようだ
↓ いまこのへん
suffix vector で表現された辞書＋頻度情報を、連結に関して更新する方法を導く
（問題は、本体文字列を連結リストで表現することが可能かどうか…）
↓
局所最適が高速に求められるようになったので、N-best 探索 も視野に入れられる
↓
1-gram 確率にもとづくclosedなエントロピーに関しては、実用上最適の単語単位が得られる
↓
2-gram 以上の確率にもとづくエントロピーに関しては、また別の話
でも 1-gram で最適なら、2-gram でもある程度よくなるのでは？
[2005-10-26] の実例。
###### 11998 #####
11998 血 病 -0.194656672504451 11906
# size += -0.194656672504451 bits on joint of 血 病
###### 11999 #####
11999 白 血病 -17.2073810573173 11907
# size += -17.2073810573173 bits on joint of 白 血病
[2005-10-26] では、符号長を一時的に増やす連結でも、
先のことを含めると符号長を減らしているような場合を考えていたが、
そこまでいかなくても、greedy な評価では符号長減少への貢献が正しく計れていないという例。
n ベスト探索などがやはり必要らしい。
<http://www.iccs.informatics.ed.ac.uk/~osborne/msc-projects/siriwan.pdf>
過去の研究のレビューがしっかりしてる。
<http://citeseer.ist.psu.edu/646630.html>
MDL 基準のDNA分割
@misc{ szpankowski-optimal, author = "Wojciech Szpankowski and Wenhui Ren and Lukasz Szpankowski", title = "An Optimal DNA Segmentation Based on the MDL Principle", url = "citeseer.ist.psu.edu/szpankowski03optimal.html" }
<http://www.cis.hut.fi/morphochallenge2005/>
教師なし形態素分割のコンペ。
<http://www.pascal-network.org/>
パターン認識とか。
To recover from speech recognition errors in spoken document retrieval
[2005-09-13-2]のときは、あくまで教師あり学習での分割と考えていたが、
データ構造などは利用できるかも。
「PPM*」の方法は、単語分割を「文字列→区切り列」のラベルづけ問題として解いている。
文字単位 3-gram モデルを用いた例がまず述べられ、
次に言語モデルをPPM*に変えた本論となっている。
PPM* では、文脈に対する文字の出現確率が基本的にすべての文脈に対して格納されており、
確率計算のときには文脈長を動的に選択する。[2005-09-13-2]
そのときに使う「文脈トライ」は、
コーパスに対する（広義の）接尾辞木であり、
枝の圧縮はないが、葉ノードのラベルが必ず接尾辞であることを利用して、
そこだけ文字ラベルでなく、コーパスの接尾辞開始位置へのポインタを置く。
…結局、接尾辞木と同じだから、更新の手間も同じくらい、か。
<http://ge.nii.ac.jp/>
論文、書籍、科研費研究成果などをまとめて検索できる。（対象は日本語）
が、論文検索だけ使えない。
一時的なメンテナンスか、もしかして登録必要？
訓練データに出現しない文字が実データに現れたら。
単語 n-gram 確率（訓練データが「単語」を生成するn-1重マルコフモデルで生成されたと仮定したときの確率）を最尤推定で求める場合、
訓練データに出現する n-gram（n単語の連接）に対しては、
いつも確率が0ではない。
が、実データで訓練データにないn-gramが現れたとき、
この言語モデルはそのn-gramに確率 0 を与える。
一般に n が大きいほど、確率0のケースが増える。
（たとえば n が訓練データの長さなら、訓練データと少しでも異なる実データには確率0を与える）
これを防ぐために、訓練データにないn-gram に対しても、
類似性などの尺度を使って、
訓練データにあるn-gramの確率から「分け与える」ことが行われる。
1-gram 確率の場合はその必要が起こることは少ないが、
訓練データにない単語が現れた場合はやはり必要になる。
文字単位 1-gram モデルでは、
訓練データにない文字が現れた場合、その必要が起こる。
言語処理学会の「自然言語処理」1999年 Volume 6 Number 2 より（1999年1月発行）。
文字集合と「2回以上出現した全部分文字列」の集合の和を、superword の集合と定義し、
全superwordを等確率とする初期状態から始まる前向き後向きアルゴリズムによって確率分布を学習し
対象文字列を、最左最長一致（＋高頻度？）によりsuperword列として認識し確率を与える。
その確率は、（基本的には）unigram で与える。
まず、
教師なし（→ ドメイン適応コストの軽減、人間基準の単語認定への依存回避）
観点が同じ。
タグつきコーパスは
質的量的にすぐれたコーパスの入手が困難
形態素解析システムを利用した方法は
特定タスクに対して高い性能を得るためには辞書をチューニングする必要
形態素解析システムは機能語が短めに分割する傾向があり、n-gramモデルの性能を最大にする単位を与えるとはいえない
（一部編集）
MDL最小化貪欲的自己組織化アルゴリズムも、
構築される辞書が superword集合のようなものなので、類似した手法といえる。
両者の違いは
1. superword集合の中身
森の方法では superword を「全部分文字列」としているため、
明らかに不要な長大な文字列までがsuperword集合に入れられる。
これは計算量を増やし、訓練データへの過度な適応が起こるため有害であり、
森の方法でもこの点に対応するため、
superword の最大長を制限するとともに、superword bigram や 文字 3gram との混合モデルを作っている。
MDLの方法ではそのような無駄な superword はそもそも持っていない（と思う）
2. n-gram 言語モデルとしての一般性
森の方法は、直接的に n-gram 言語モデルを与えており、
前向き後向きアルゴリズムによる学習によって、あらゆる n に対する n-gram 確率が学習される。
MDLの方法は（いまのところ）直接的に与えられるのは 1gram と 2gramだけで、
スムージングもされていない。
スムージングや3gram以上が欲しい場合は、できた superword 辞書を使って、
あらためてコーパスから ngram 確率を学習する必要がある。
（たぶん大したデメリットではない）
言語モデルの性能評価に用いる指標。
言語モデルが持つ「言語」の複雑さを表すもので、
あたえられた対象文字列に対応する「単語列」の場合の数の期待値（？）を表す。
（候補が多くても、確率が高いのがそのうちの少数であれば、パープレキシティは低い）
よく使われるのは単語あたりのパープレキシティ。
これは、文脈が与えられたときに候補となりうる単語の数の期待値を表す。
Corpus を「単語」の列とするとき、
P(Corpus) = \prod_{w_i \in Corpus} P(w_i| w_i の文脈)
クロスエントロピー（学習された確率分布 P が Corpusに与える情報量）の単語あたりの値は、
H(Corpus) = \frac{ -log P(Corpus) }{ len(Corpus) }
PP = 2^{ H(Corpus) }
= { 2^{ log P(Corpus) } }^{ -1/len(Corpus) }
= {P(Corpus)}^{-1/len(Corpus)}
len を Corpus ののべ文字数とすると文字単位パープレキシティになる。
のべ単語数とすると、文字単位パープレキシティ。
#! /usr/bin/perl -w
use strict;
use encoding 'euc-jp';
use open ':encoding(euc-jp)';
use open ':std';
while ( <> ) {
s/[\x{0000}-\x{00FF}]//g;
print;
}
改行もASCIIなのに注意。<http://compling.ai.uiuc.edu/rws/newindex/publications.html#tutorials>
チュートリアル Corpus-Based Methods in Chinese Morphology など。
単語の定義に関する議論の紹介、
中国語の形態論の概説、
<http://rchi.raskincenter.org/index.php?title=Home>
The Humane Interface の実装: Archy
<http://www.cs.cmu.edu/~aberger/maxent.html>
最大エントロピー法のチュートリアルA Brief Maxent Tutorialなど。
2000年以前で最新とはいいがたいが、わかりやすい。
ひらがなと漢字の出現確率が違いすぎるのが、連結が不均一になる原因の気がする。
単語辞書の符号化のとき、文字出現確率を用いた最適符号にすべきかも。
漢字はひらがなより符号長が長いので、
辞書での統合（統合により連結前の単語が辞書からなくなる）
が起こる連結の動機付けが強くなる。
<http://www.matsumoto.nuem.nagoya-u.ac.jp/eguchi/index.html#Acro>
Acrobat Reader で表示できるのに印刷できないという問題。
postscript に変換してみると、ghostview がエラーを吐く。
よく分からないが、指定されているフォント（HeiseiMaruGo-W4）が見つからない、ということらしい。
[2005-10-27]でも書き換えた
/usr/share/ghostscript/7.07/lib/CIDFnmap
あたりを見ると、たしかにそのフォントは定義されていないらしい。
てきとうに
/HeiseiMaruGo-W4 (ipag.ttf);
と追加すると、動いた。
<http://hunch.net/>
機械学習の理論に関するブログ。
Computational Complexityのブログとか、
Quantum Algorithmsのブログも。
15GB のファイル log に対して、
grep -v "^## " log | fgrep -v "[[[" > extracted
のような grep をかけたら、2日経っても終わらない。
やりたかったのは、先頭が '## ' でも '[[[' でもない行を抜き出すこと。
そういう行はファイル全体（数千万行？）のうち、数千行くらい。
原因の推測：
- grep のバッファリングが強すぎて、パイプしたときに渋滞現象
- -v オプション（マッチ、非マッチの反転）がなんか遅い気が
- 単純に正規表現マッチングが遅い
「行頭固定文字列マッチのgrep」↓を使ったら10分で終わった。
#! /usr/bin/perl
use strict;
use warnings;
use Getopt::Long;
my $inverse = 0;
GetOptions('v|inverse' => \$inverse);
my $pattern = shift @ARGV;
if ( !$pattern ) {
print "usage: grep_head PATTERN [-v] FILES ...\n";
exit;
}
if ( !$inverse ) {
while ( <> ) {
print if index($_, $pattern) == 0;
}
} else {
while ( <> ) {
print if index($_, $pattern) != 0;
}
}
Node のカウンタが static なのはどうもまずい。(シリアライズがめんどう）
SuffixTree のインスタンスフィールドにして…
VisualizationViewer
は Serializable だからグラフの保存[2005-11-03]は簡単……かと思いきや、
どうもスーパークラスの JPanel がSerializable なだけで、実装はされていないらしい。
faqにも、コード募集中と書かれている。
Serialized Form (JUNG 1.7.1 API)
を見ると、VisualizationViewer をシリアライズするには 10 以上のクラスをSerializableにする必要がある。
たぶん、難しくはないはず……
ただ Serializable とつけると、デフォルトのシリアライズ：
非 transient のインスタンスフィールドが、再帰的にたどられてシリアライズされる。
static フィールドで何か計算しているとかいうときには、デフォルトでは保存されないのに注意。
<http://d.hatena.ne.jp/amt/20051007/acroread7>
mozplugger の acroread の呼び出しかたが古くて動かないのを修正。
application/pdf: pdf: PDF file
application/x-pdf: pdf: PDF file
text/pdf: pdf: PDF file
text/x-pdf: pdf: PDF file
# repeat swallow(documentShell) fill: acroread -geometry +9000+9000 +useF$
repeat noisy swallow(acroread) fill: acroread -openInNewWindow "$file"
ChangeLog の特定カテゴリのエントリに"p:"の印を付けるプログラム。
#! /usr/bin/perl
use strict;
use warnings;
use Getopt::Long;
my @priv_categories;
GetOptions('private=s@' => \@priv_categories);
print STDERR "privatizing ", map("[$_]",@priv_categories), " ...\n";
my %priv_table;
@priv_table{@priv_categories} = map 1, (1 .. scalar @priv_categories);
foreach my $line (<>) {
my $priv = 0;
if ( $line =~ m/^\s*\*\s*([^\[]+)(.*)\s*:\s*$/ ) { # match to a title line
my($title, $cat) = ($1, $2);
my @categories = ($cat =~ m/\[(.*?)\]/g);
foreach (@categories ) {
$priv = 1, last if $priv_table{$_};
}
if ( $priv ) {
print "\t* p:$title ".
join('',map "[$_]", @categories).
":\n";
next;
}
}
print $line;
}
User’s Guide to the Beamer Class, Version 3.01
が、長いが丁寧で参考になる。
ただし、対象バージョンがPortageで入るbeamerより新しく、機能がまだなかったりする。
コンパイルは通常どおりでよい。
スライドのPDF生成は
dvipdf presen.dvi
handout の生成はちょっとややこしい。
流れは、スライドのサイズ（カードサイズ？）から A4 への引きのばし、さらに複数ページの結合、という順序。
まずLaTeXのソースで
\documentclass[handout]{beamer}
として、アニメーションを停止。
dvips -P pdf -ta4 $1.dvi psnup -1 -W128mm -H96mm -pa4 $1.ps $1.0.ps psnup -6 -l $1.0.ps $1.1.ps pstops "1:0@.95(6mm,0mm)" $1.1.ps > $1.ps大きな紙に印刷し、
<http://www.matome.jp/>
blog の検索。
Google Blog Searchの方がいいかな。
英語だけど、運営プログラムが共通なせいか日本語もよく引っかかる。
ある単語区切りを消したときのDL減少分が大きいほど”結合強度”が弱く、
減少分が小さいほど結合強度が強いといえるのでは。
長さ n のランダムな2進列があります。
0の数と1の数が分かっているものとします。
また 00、01、10、11の数も分かっています。
ただし 00 と 11 の数は、重複ありで数えたものです。
これらから、00 または 11 の重複無しでの数を求められますか？
証明、または反証してください。
反証した場合:
00、01、10、11 の出現確率が分かっているものとします。
00 または 11 の重複なしでの数の期待値を求められますか？
Gusfield, "Algorithms on Strings, Trees and Sequences" 7.7.節より。
suffix tree の方で、枝を結んでしまえばいい、ということ。
索引（部分文字列を入力してその出現位置を得る）としての機能は失われるが、
出現回数はわかる。
Kriszti'an Monostori et al., Suffix vector: space- and time-efficient alternative to suffix trees
ACM掲載の論文。短くまとめられているが、わかりにくい。
同氏の博士論文
ドキュメント集合から部分一致チャンクを見つけ出す、というシステム。
その一部として、Suffix Vector を開発した。
Suffix Vector について：
Suffix Tree には、同一の部分木が多くある、という構造上の冗長性がある。
その冗長性をなくすことにより、使用領域を削減しようというアイデア。
suffx link で結ばれたノード同士が、そのような共通部分木を持っている。
<http://eclipsewiki.net/eclipse/?FrontPage>
統合開発環境 Eclipse の日本語 Wiki。
プラグインの紹介など。
TeXlipse homepageとか便利そう。
Eclipse 3.1.1 非ネイティブランゲージ版では、
日本語版の「ヘルプ -> ソフトウェア更新 -> 更新マネージャ」が
「Help -> Software Update -> Find and Install」にあたるらしい。
Ukkonen のアルゴリズムで付加される Suffix Link を利用する。
Suffix Link は下層から上層のノードに向かう枝であり、
元のノードと先のノードには、
「根から元のノードまでのラベルの先頭を取り除くと、根から先のノードまでのラベルになる」
という関係がある。
また、元のノードは葉でないノードである。
連結対象の2文字を根からたどる。
0.
連結によってインデックスの更新が必要になる。
（連結が起こった出現よりあとのインデックスは、1減る）
本体文字列を配列でなく連結リストで管理し、インデックスの代わりにポインタでラベルづけを行っていれば、
更新操作は局所的に行える。
つまり、いま見ているノード（ラベルAB）以下にある葉に対応する位置の出現を求めて、
連結リストノードの連結を行う。
このために、連結リストは双方向である必要がある。
1.
2文字(AB)のあいだにノードがない場合、文字 A のあとに続く文字がひとつ（つまり B）しかないということ。
この場合、木の枝の付け変えはないので、以下のうち 2.1 だけを行う。
2.0. 統合される枝の付け替え
2文字の間にノードがある場合、連結を行って、連結後の文字 AB というラベルのあたらしい枝を根から作る。
（以降、ラベル X をもつノードのことを、ノードX と呼ぶ）
これによりノードA から出る枝はひとつ減り、ノードA 以上の頻度もそれに応じて減少する。
2.1. 統合されてなくなる部分木の消去
2.0.で追加されたノード AB から、Suffix Link をたどる。
その先のノード（ノード B）の部分木から、元のノード（ノード AB）の部分木を”引き算”する。
形式的に言うと、元のノードよりしたにある葉と同じラベルを持つ、先のノードの下にある葉を除去する。
（ここでいうラベルには、元のノード／先のノードより上は含まない）
そのために、上から順に、枝の先頭文字により部分木を区別し、
同じ先頭文字を持つ互いの部分木以下の葉の数が同じなら、先の方で部分木を除去する。
＃ この部分で計算量が……
2.2. 統合される枝の付け替えの波及
統合が起こったノード A に向かう Suffix Link すべてについて、
その Link を逆行し、2.0 で行ったのと同じ枝の付け変えを行う。
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