~matubara/ChangeLog / 2005-12 →移動しました

■ draft オプションがあるときだけ表示 [latex]

	
\newcommand\Draft[1]{
\ifdraft

{\hfill \bf ■---\texttt{DRAFT}--- #1 ---\texttt{DRAFT}---■ \hspace{-2em}}

\fi
}

\Draft{あとで図を}

のように使うと、

\documentclass[draft]

のときだけ表示される。

■ NFS上で、svk のロックがうまくいかない [linux]

debian の nfs-user-server はロックをサポートしていない。

.svk/local/locks/*.lock を削除すると、NFS経由でなくても、常にロックに失敗する。

■ Self-supervised Chinese Word Segmentation [segmentation]

汎用の教師なし単語分割では、EM アルゴリズムを使うのはけっこうメジャーらしい。
~~~~~~
ローカルには尤度最大の分割を与えることができる。

単語候補となりうる文字列を蓄えた辞書を使って、
期待値最大化。

まず辞書を収集してから、
分割を適用し、あいまいになる部分をPP最小基準で選択する。

■ いろんなプログラムが動的リンクに失敗する [gentoo][linux]

 error while loading shared libraries: libgcc_s.so.1: cannot open shared object file: No such file or directory

so ファイル、もしくは呼出元の実行ファイルが壊れたか、と思ったが、
よく考えると、見付からない、というのはパス情報が壊れているということ。

/etc/ld.so.cache
というバイナリファイルを正常なものと見比べてみると、
パス情報らしき部分が２つに分裂していて、何かおかしい。

Gentoo ではふつうは

env-update

でこのファイルを再構成するが、これも動かないので、

ldconfig

で元に戻った。

■ NTT-TUT ミーティングでの質問と意見 [segmentation]

- パープレキシティで評価しているが、その目的は？

→ 言語モデルの性能向上。（背景の説明が伝わらなかった）
   背景の説明が不十分。

- 言語モデルの性能は、具体的なシステムに組み込んでみないとわからない。

- パープレキシティ最小化ならば、もっと単純な方法がありそう。

  貪欲な選択はしかたないにしても、
  連結を繰り返すというアルゴリズムは、パープレキシティ最小化とは関係がない。

- 既存辞書の単語の組合せの範囲でやったほうが、応用範囲が広い。
  そのときも、差分評価という考え方で効率化できるのであれば、意味があるのでは。

→ 初期分割を形態素分割にして、細かすぎるところをつなげる、という方法もある

- マヤ語の解読に役に立てられないか。

→ 言語知識を用いない、という点では適用可能ではあるが…


あと、数式の変数の説明とか素っ飛ばしたので、即座に突っ込まれた。
しかも、ちゃんと応答できなかった。
0-gram ということと、式がああなっているということをちゃんと説明する必要があった。

新規性をもっと強調するべきだったかも。
言語モデル性能だけを基準にしていて、
辞書もルールも初期分布も使っていない。
（近似があるが）

■ 特別実験報告会での質問と意見 [segmentation]

梅村先生：
Viterbi アルゴリズムを使った岡野原さんの手法の情報をいただいた。

宇野先生：
過学習はなぜ、どんなとき起こるのか。
→ 極端な例として、全体が1単語

夏井先生：
オープンとクローズドで、なぜこれほど性能が違うのか。
→ データ不足と考えている

■ 岡野原大輔 『汎用的データにおける確率的言語モデルの抽出とその応用』 [segmentation][lm][algorithm]

非自然言語データの上で確率的言語モデルを構築し、圧縮する。
単語分割（WX法）とクラス推定を、教師なし学習により行う。

まず、単語の最大長 n を与えた上で、
suffix array の一致数（辞書順ソートでの隣接接尾辞の最長共通接頭辞の長さ）の切り替わりを見て、
単語候補集合を得る。
候補はすべて n 文字以内。

第一段階の分割として、
圧縮率に関して貪欲に単語候補を選び、対象データを単語に置き換えていく。
圧縮率は、文字単位0-gram（ようするに文字数）に対する単語1-gramのエントロピーの比としている。
これにより、単語候補集合を用いた最適符号化の荒い近似が得られる。
ここでの単語出現確率を、ほんとうの最適符号化での単語出現確率の近似として、
次の動的計画法の適用に用いる。

対象文字列中の位置 i までの最適な分割は、
位置 i-1 までの最適な分割の最後の半端分を含む単語候補のうち、最適な分割を与える単語を選んだもの。
として動的計画法を適用する。
このときの評価は第一段階の分割における出現確率をもちいた、エントロピーの合計値。

品詞クラスタリングに相当する Class Model については省略。

比較：
プレーンデータを教師なしで単語分割する、という点は共通で、
候補の評価に用いる圧縮率、エントロピーもしくはパープレキシティは本質的に同じ。

計算効率の点では、WX法がはるかに優れる。

最適性の近似精度に関しては、
WX 法では荒い近似からより精密な近似を行っていることから優れているように思われるが、
第一段の近似の精度がどれほど信頼できるかにかかっている。
提案手法の貪欲な連結による近似との比較は実験的になされるしかない。

自然言語の統計的言語モデル構築を目的とした場合、
提案手法は分割法、より正確には分割のための（連結の）手順と、そこから導かれる辞書を生成し、
実際の言語モデル構築は既存のN-gram言語モデルツールキットにまかせる。

WX法によって自然言語の統計的言語モデルを構築しようとすると、
圧縮後（言語モデル構築後）に与えられた新たな文字列に対する分割の計算は明らかでなく、
何らかの付加的作業が必要。
新たな文字列をコーパスに加えて再分割、というのがもっともナイーブだが、
計算効率のメリットは薄れる。

WX法では単語の最大長の制限が過学習の歯止めになっていると思われるが、
提案手法では辞書サイズが歯止めになっている。
これらの制限は、ヒューリスティックに過学習を防ぐものであり、
どちらが優れているかは明らかでない。

候補の評価に関して、
提案手法は 2-gram エントロピーによる評価が可能となったが、
WX 法では明らかではない。
ただし、最適性に対してどのように近似しているかが明示されているWX法の枠組で
2-gram への拡張が自明でないことは、
提案手法の 2-gram への拡張が
貪欲探索において近似の精度を著しく落としていることを示唆するように思われ、
これが性能悪化の原因になったのかもしれない。

WX法では、単語の最大長が制限されている。
これは計算の効率、より高次のモデルへの移行を考慮したものだが、
自然言語への適用ではあまり問題にならないと思う。

■ 確率推定用コーパスとパープレキシティ評価用コーパスを分ける [segmentation]

過学習を避ける方法。
推定用にはあって、評価用にはない、という N-gram ができることがあるので、
バックオフが必須。
あと、評価用のために過学習すると本末転倒なので、
交差検定のようなことをする必要があるかと。

■ pdf を縮小してタイル状に配置 [latex][presentation][howto]

pdfnup --nup 2x3 --delta "0 2cm" --frame true xxx.pdf

pdfnup は、pdfjam というパッケージにはいってる。

PDFファイルを生成する仮想プリンタ cups-pdf と組み合わせると、
けっこう柔軟に拡大縮小ができるっぽい。

■ Word Segmentation [lx]

言語、認知、発達心理学の方面：
単語の分節化としての Word Segmentation
音声系列を単語列として認識すること。
Word Boundary Identification

単語区切りのある言語、特に高度に屈折的な言語：
単語から形態素列への分割としての Word Segmentation
Morphological Segmentation

単語区切りのない言語、日本語、中国語、タイ語：
文に単語区切りを与える。
事実上、形態素区切りと同じ。
Sentence Segmentation

■ 連結対象を選ぶことと、連結をコーパス全体に適用すること [segmentation]

2単語の連結を基本操作としてえらび、
各ステップで連結を貪欲に行うことを選んだ時点で、
計算すべきことが 2 つできた。

連結の適用：
もっとも簡単なのは、コーパス全体を大きさ２の窓で走査して、連結を適用するもの。
ただし、コーパス全体がセグメントを要素とする連結リストでないと、効率的でない。

すべての 2-gram の出現位置を計算しておくと、
連結の適用自体は出現回数分のオーダーの時間となる。
出現位置の初回の計算はしょうがないからやるけれど、
次からは、変化分、追加分だけを更新する。
まず、連結された 2-gram のエントリは消す。
連結の適用とともに、連結されたセグメントの前後 A,B のどちらかを共有する 2-gram xA, By に関して、
もはや（ここでは）存在しない2-gram xA ,By の出現位置情報を削除する。
そして、xAB, ABy のエントリに（エントリがなければ作って）出現位置情報を追加する。
追加と削除の効率性から考えると、2-gram の出現位置のデータ構造は、
2-gram --> 位置 -> 定数
の2段階のハッシュがよさそう。

Suffix Tree を使う場合、出現するすべての部分文字列の出現位置は、
部分文字列の長さ分、木をたどった位置の部分木を 深さ優先探索して葉を訪問していけば分かる。
問題は連結に関して木を更新すること。
これについて、色々考えた結果[2005-11-22-1]、Suffix Vector で表現するとよさそう。
ハッシュほど効率はよくないかもしれないが、我慢する。
あるいは、単語深さ 2 のノードに、出現位置情報をキャッシュしておくという方法もある。
（木の中に、上述の出現位置のハッシュを持たせておくようなもの）
この情報は、木の更新とは別に更新する。
Suffix Tree の利点は、任意の n-gram の頻度をノードに保持しておけること。

連結対象として選ぶこと：
えらばれるのは、
その連結をコーパス全体に適用したら、コーパス全体のエントロピーがもっとも小さくなるような連結。
連結によるエントロピーの変化分は、最初は全候補について計算する。
ステップを移る（１つの連結が全体に適用される）ときに、
ある連結に関するエントロピーの変化分は、変わらないこともある（２つの連結がたがいに近くに現れない場合）
変わるのは、適用された連結を構成するセグメントのどちらかが含まれているような連結と、
（以下略）
変わる連結は、連結の適用と同時に、集合として記録しておく。

エントロピー差分が変化する場合というのは、式中の一定の数の項に変化が起きる場合と、
式の項の数自体に（大幅な）変化が起きる場合とがある。

前者は差分評価により、式全体の再計算なしに更新できる。
後者の場合は、いまのところ、再計算することにしているが、
よく考えると差分評価が可能かもしれない。

いずれにしても、エントロピー差分の式にはすくなくとも 4-gram までの頻度情報が必要になる。
ただ、ぜんぶの組合せが必要という訳ではなく、
1-gram, 2-gram についてはすべて、
3-gram については、ABA, ABB, AAB の形のもの、
4-gram については、ABAB の形のものが必要。
単語2-gram の数のオーダーの領域量で抑えられる。
が、領域量に関しては Suffix Tree の方が有利と思われる。

更新のあと、エントロピー変化分最小の候補をえらぶには、
エントロピー変化分の順で 2-gram を順序づけするヒープを作っておき、
なくなった 2-gram の削除、追加・変更された 2-gram の追加を行い、
そのあとでの最小要素を選べばいい。

ということで、ハッシュを用いた場合でも、Suffix Tree を用いた場合でも、
対象データの大きさに直接には依存しない計算時間、領域で実現が可能なはず。

■ 一時ファイルを作らずにプログラムの出力を diff [linux][howto]

diff <(foo) <(bar)

↓だいたい等価↑

foo > tmp1; bar > tmp2; diff tmp1 tmp2

ちなみに

echo <(foo) <(bar)

とすると、

/dev/fd/63 /dev/fd/62

のように表示され、プログラムの出力を読むためのファイルが作られていることが分かる。

■ R. セジウィック, "アルゴリズム 第2巻＝探索・文字列・計算幾何" [algorithm][book]

■ ハードコーディングせずに、バックスラッシュによるエスケープ文字 [perl]

perl -e 'print eval qq{"$ARGV[0]"};' "hoge\n"

で、hoge のあとに改行が表示される。
eval qq{"$ARGV[0]"} --> "hoge\n" をPerlプログラムとして評価 --> hoge のあとに改行があるという文字列

perl -e 'print "$ARGV[0]";' "hoge\n"
perl -e 'print $ARGV[0];' "hoge\n"

だと、hoge\n そのものが表示されるだけ。
hoge と \ と n という、ふつうの解釈。

perl -e 'print eval "$ARGV[0]"' "hoge\n"

はかなりおしいのだけど、
eval "$ARGV[0]" --> hoge\n をPerlプログラムとして評価 --> 構文エラー

ユーザー入力を eval するのは、ほんとうは危険。

■ Ravindra K.Ahuja, Thomas L. Magnanti and James B. Orlin, "Network Flows" [algorithm][book]

■ Suffix Tree から Sparse Suffix Tree への変換 [string][algorithm][segmentation]

Sparse Suffix Tree とは、Krisztian さんの論文[2005-11-02-1]で紹介されている、
単語単位 Suffix Tree のようなもの。
形式的には、文字列と文字列中でのすべての単語の開始位置（区切り記号の位置 -1）が与えられたとき、
単語の開始位置から始まる suffix のみを含む suffix tree。

単語辞書と文字単位 suffix tree が与えられたとき、
木を sparse suffix tree に変換するために、連結のアルゴリズムが使える。
単語辞書を長さ順にソートして、各単語内の先頭2文字から順に
[2005-11-01-1]の方法で連結に関する更新を繰り返していくと、
sparse suffix tree が得られる。

変換の最悪の計算時間は、辞書の合計長 x 単語出現頻度の最大値 か？
たぶんあまり頭のいい方法ではない。

sparse suffix tree は suffix tree と比べて、
matching statistics algorithm という文字列間の類似度判定を行う際に、
単語の途中から始まるsuffix を考慮しない点で効率がいい、とか書かれている。

■ 辞書の符号化を文字1-gramの符号化にする [segmentation]

辞書の符号化はいまのところ 0-gram（等しい長さ）の符号化。
これは効率の悪い符号化なので、より効率の良い符号化にすると、
辞書のエントリの増減による、全体の符号長の増減への影響が小さくなる。
とりあえず、辞書内文字単位 1-gram による符号化を予定。

■ 符号化のときの確率推定にも汎化を考慮する [segmentation]

2-gram エントロピー最小化の方法は、1-gram よりも少ない連結しかしない。
2-gram 確率を使うため、スパースネスが大きいのが原因だと思う。
データを増やすか、確率推定にスムージングを施す必要がある。

■ 特別実験報告会予稿（言語モデル最適化バージョン２） [segmentation]

表題：言語モデル性能指標を基準にした文分割 / Sentence Segmention based on Language Model Performance
概要：

自然言語処理において、統計的言語モデルは音声認識、機械翻訳など幅広い応用に用いられている基礎的手法のひとつである。統計的言語モデルは、文すなわち単語列において、ある単語の出現確率をその単語の前に現れる単語を条件とする条件つき確率として与える。

一般に言語モデルの構築にあたっては、文を分割する単位である「単語」は、言語学的単位としての単語を基準とすることが多い。たとえば、辞書に基づく分割方法ではその言語の専門家によって整備された辞書が用いられ、教師あり学習に基づく分割方法では母語話者の分割を教師として学習が行われることが多い。しかし、言語モデル構築のための分割の単位が言語学的な単語である必要性はなく、実際に、対象領域やスタイルに適応して分割を修正することによる、言語モデルの性能の向上が報告されている。本研究では、言語知識を用いず言語モデル性能指標のみを基準として分割を与える手法を提案し、言語モデル性能を向上させることを目指す。

言語モデル性能の指標として、その言語モデルが文脈に対して予測する文の場合の数の期待値である、パープレキシティがある。パープレキシティの対数は、言語モデルを単語列を出力する情報源とみたときのエントロピーであり、情報源符号化における理想的符号長である。

本研究では、パープレキシティ最小な分割を近似する、言語知識を用いない分割法を提案する。この方法では、まず、学習データを可能な最小の単位である文字に分割する。そうしてできたセグメント（区切られたひとまとまりの文字列）列を、辞書の構築とともに組織化していく。組織化は、連続して出現する2セグメントを連結することを1ステップとしている。連結候補の選択の基準として最小記述長原理を採用し、記述長を与える符号化としては、単純マルコフ性近似と辞書の構築に基づく符号化を採用する。

提案手法による言語モデル性能に改善の可能性を調べるため、比較的少量の講演音声の書き起こしデータを対象として、提案手法による言語モデルと既存の分割手法による言語モデルの性能を文字当たりパープレキシティによって比較したところ、既存の形態素解析システム茶筌による分割に対して構築された言語モデルは 26.410、提案されている分割法による言語モデルは 24.032 であり、提案手法は茶筌による分割に匹敵する性能を示した。また、学習に用いるデータの量を変化させて同様の実験を行い、提案手法は既存手法と比べて、データの増加に対してより大きな性能の向上が見られることを確認した。
計算時間の低減、現実的なスケールのデータに対する性能評価、音声認識などの応用での性能評価、2重マルコフ近似への拡張、探索範囲のN-bestへの拡大が今後の課題である。

Statistical language model is a fundamental method in a number of applications of natural language prosessing, such as speech recognition and statistical machine translation.
In construction of a language model, word as a linguistic unit is commonly used to segment a sentence. However, it is reported that higher performance of language models can be realized with segmentation methods adapted to the target domain or style.
Performance of a statistical language model can be measured with Perplexity, the mean number of probable choices in a context given by the model. Vieweing a language model as an information source, logarithm of Perplexity essentialy equivalent to entropy of the source.
In this research, we propose a segmentation method approximately minimizing the Perplexity based on the Minimum Description Length, which encodes the learning data with a coding based on a dictionary constructed in the process and approximation of 1st order markov property.
A language model constructed with the proposed method achieved comparable performance to a language model based on an existing dictionary-based segmentation method.
Future work should be carried out to reduce the computational time, to evaluate the perfomance in more realistic sclae data, to extend the model to 2nd order markov property and to enhance the search range to N-best.

■ 森 信介, 宅間 大介, 生コーパスからの単語 N-gram 確率の推定 [segmentation][net]

<http://www-lab25.kuee.kyoto-u.ac.jp/member/mori/research.html>

 2004年

   1. 生コーパスからの単語 N-gram 確率の推定(311[KB], PS)
  * 森 信介, 宅間 大介
  * 情報処理学会自然言語処理研究会 (2004)

■ 森信介, 単語リストと生コーパスによる確率的言語モデルの分野適応(言語の統計モデル) [segmentation][net]

<http://ci.nii.ac.jp/cinii/servlet/QuotDisp?USELANG=jp&DOCID=20006641851&DispFlg=2>

著者名 ： 森,信介
： MORI,Shinsuke
所属 ： 日本アイ・ビー・エム株式会社東京基礎研究所
： IBM Research, Tokyo Research Laboratory, IBM Japan, Ltd.
論文名 ： 単語リストと生コーパスによる確率的言語モデルの分野適応(言語の統計モデル)
： Language Model Adaptation with a Word List and a Raw Corpus
雑誌名 ： 電子情報通信学会技術研究報告. NLC, 言語理解とコミュニケーション
： IEICE technical report. Natural language understanding and models of communication
出版事項 ： 巻号 105(204) / ページ 69-75 / 出版年 20050716
出版者等 ： 電子情報通信学会

人手による分割支援のための手法。
修正が必要な箇所を自動的に見つける。

■ GETAによるファイル全文検索 [nlp][net]

<http://pitecan.com/GETA/>

■ 考察（予想） [segmentation]

- 2-gram 言語モデルの closed なパープレキシティはたしかに低い
- 2-gram 言語モデルの open なパープレキシティも低め
- 3-gram 言語モデルの closed/open パープレキシティは低くない
2-gram ヒットが増えた分、3-gram ヒットは減っている。

- 原理上、確率推定の信頼性が落ちる方向に向かっている
  データ量を増やしたとき、言語モデル性能が悪化する可能性も。