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
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
<http://www.furui.cs.titech.ac.jp/publication/2003/asj2003s_135.pdf>
Workshop on Algebraic Statistics and Computational Biology [bio][stat][net]:
<http://www.claymath.org/programs/cmiworkshops/ascb/>
代数幾何と 生物の Sequence Analysis ?
<http://watanabe-www.pi.titech.ac.jp/~swatanab/var-bay.pdf>
そもそも、N-gram でなく、適応的に文脈長を選ぶべきではないか(PPM*言語モデル?)
形態素/活用の単位の2-gram文脈の情報量は、それなりに一様(1-gram文脈では明らかに不足しているが)
3-gram と 2-gram はけっこう違う。
最小単位をなににするか?
・文字
・形態素
・?
形態素でないにしても、
読みが決定されている必要がある。
音声認識、同字語の曖昧性解消の点からも、読みは有用。
音響コンフュサビリティを考慮した単位の必要性:
1モーラしかない単語では、音響モデルで音素環境依存性3-phone
<http://winnie.kuis.kyoto-u.ac.jp/~yoshii/cpp.html>
後藤さんの共同研究者、吉井さんによる。
<http://homepage2.nifty.com/aito/>
Palmkit の作者であり、 w3m の作者でもある。
大変御世話になっています。
<http://lbc21.jp/temp/hokoku14/psn/K/kato_M.htm>
金野弘明・加藤正治・小坂哲夫・好田正紀・伊藤彰則:
「かな・漢字文字列を単位とした言語モデルの検討」
『電子情報通信学会技術研究報告』 SP2002-148, 1-6 (2002-12)
形態素でない言語モデルの単位の研究。
1文字を単位とする言語モデルと、
2文字を単位とする言語モデル。
階数は4。
2文字辞書の選択には、相互情報量か頻度を用いる。
先行論文でモデルが提案され、
ここには丁寧な実験結果が書かれている。
性能が悪くなるのは
<http://www.symbio.jst.go.jp/~nakadai/linguistic/>
辞書は形態素解析結果からスクリプトで生成。
言語モデルはpalmkitで、2-gramと逆向き3-gramを生成。
<http://plone.org/>
CMS とか Zope とか。
<http://citeseer.ist.psu.edu/mackay94hierarchical.html>
2-gram, 1-gram の線形補間式スムージングの根拠づけ。
Any rational predictive procnnedure can be made Bayesian.
..., the aim of this pare is to discover what implicit probabilistic model the above procedure can be related to.
<http://www.esat.kuleuven.ac.be/sista/natoasi/kulhavy.pdf>
<http://citeseer.ist.psu.edu/717851.html>
<http://citeseer.ist.psu.edu/zaragoza03bayesian.html>
ベイズ推定を用いる1-gram(トピック)言語モデル
... one of the best smoothing techniques used today in LMs is
Bayes-Smoothing or Dirichlet Smoothing [2006-02-21-4].
<http://www.wadsworth.org/resnres/bioinfo/tut1/>
<http://www.mas.ncl.ac.uk/~njnsm/seminars/seminars0405/abstracts/boys.pdf>
<http://en.wikipedia.org/wiki/List_of_important_publications_in_computer_science>
<http://phrontistery.info/numbers.html>
Greek prefixes:
mono-
di-
tri-
tetra-
penta-
hex-
hept-
oct-
ennea-
dec- deca-
Latin prefixes
uni-
bi- duo-
tri-
quadri- quart-
quinque- quint-
sex-
sept-
oct-
nonus- novem-
dec- deca-
<http://citeseer.ist.psu.edu/blei03latent.html>
ベイズ推定によるテキストモデル(長距離言語モデル)
<http://cog.brown.edu/~gruffydd/bayes.html>
大域言語モデル:どのような語彙が使われているか。ユニグラム。
近接言語モデル:どのような単語の連続が許されるか。バイグラム以上。
言語モデルの適応は、厳密には、トピックに対してなされるべき。
トピックは、入力データを知る前には分からない。
音声認識の場合で考えれば、対話が進むにつれ、トピックは変化する可能性がある。
トピック同定は、bag-of-words としての性質からなされる。
よく使われるフレーズを単語としてつなげておくことにより、
トピック同定が改善される。
単語連結は、同じトピックのデータ内での、単語出現頻度を使って推定される
パープレキシティを最小化するように決める。
トピック同定と単語連結を繰り返すことにより、大域的傾向で切替えられる混合近接言語モデルが作られる。
単語境界も、トピック境界も、
その都度決め打ちするか、
分布として保持するか。
perl -e'@a = <>; srand; print @a[map int rand()*scalar(@a), (1 .. 100)]'
perl -pe'tr/ A-Z/H-Z A-G/; $_'
perl -pe'tr/ A-Z/P-Z A-O/; $_'
perl -pe'tr/ A-Z/D-Z A-C/; $_'
#! /usr/bin/env perl # convert a long line to fixed-length lines by adding line breaks use strict; use warnings; use Getopt::Long; my $line_length = 60; GetOptions('line-length=i' => \$line_length); my @to_print = (); my $to_print_length = -1; my @lines = <>; chomp @lines; foreach ( split / /, join '', @lines ) { if ( $to_print_length + 1 + length $_ <= $line_length ) { push @to_print, $_; $to_print_length += 1 + length $_; } else { print "@to_print\n"; @to_print = $_; $to_print_length = length $_; } } print "@to_print\n";
#! /usr/bin/env perl use strict; use warnings; my @a=qw(ZERO ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE); my $s = ''; while ( <> ) { chomp; s|[0-9]+|join ' ', @a[split //, $&]|exg; tr/a-z/A-Z/; s/[^A-Z ]//g; $s .= "$_ "; } $s =~ s/\n/ /gm; $s =~ s/\s+/ /g; print "$s\n";
<http://www.cs.mu.oz.au/acl/P/P98/P98-1047.pdf>
multigram ベースの 2-gram モデル。
phrase ベースとの違いは、結合された単位の中の内部構造を保存し、あとで見ていること。
class モデルも同時に推定。
論文タイトルは、「統語構造と語彙構造の学習」
[2006-02-10]のようなこと。
短いコードで多くの処理を実行させることができる高級言語の各種機能
(いわゆる「強力な」機能)
は、どう使うべきなのか?
Java の場合、ライブラリとは Java API( java.lang, java.util, java.awt, ... )
機構とは、継承、アクセス制御、リフレクション、内部クラスなど。
車輪の再発明をするな。一度書かれたコードを二度と書くな。利用できるものは常に利用せよ。
開発の効率性を重視する。
ソースコードを最小にする。
同じ結果が得られるなら、もっとも楽な書き方を選ぶ。
エンジニア型プログラマ(ふつうのプログラマ)。
特定のライブラリや機構に依存したくない。
普遍性を重視する。自己完結性を重視する。
プログラムの総体を最小にする。
プログラミングの本質は、アルゴリズムの書き下し。
使用しているライブラリ、機構、コード自身の全てを含めて、もっとも単純になるように書く。
哲学者型プログラマ。
犠牲にするのはユーザビリティと実行性能の最適化。
使う言語はなんでもいい。
ライブラリも機構も、性能がよくなるなら使うし、悪くなるなら使わない。
実行時間を最小にする。
同じ結果が得られるなら、計算機をもっとも効率よく使えるように書く。
アスリート型プログラマ。
犠牲にするのはプログラミングのための労力。
使う言語は C、C++。
よいプログラミングとは、実行時性能のよいプログラムを作ること。
プログラムの分かりにくさは、コメントでフォローする。
ライブラリや機構の設計思想をよく知り、それにあった書き方を見つけてあげよう。
美しさを重視する。
同じ結果が得られるなら、もっともその言語らしい書き方、パターンを選ぶ。
芸術家型プログラマ。
犠牲にするのは言語間移植可能性。
使う言語は Java、Perl。
プログラミングとは、アルゴリズムを、ある言語の枠組の中でいかに表現するか。
プログラムの分かりにくさは、リファクタリングで解決。
哲学者と芸術家:
内面のパターンと、外面のパターン。
エンジニアとアスリート:
作る人の効率と使う人の効率。
アスリートと芸術家:
バイナリとソースコード。
性能と美しさ。
エンジニアと芸術家:
書く人のためにライブラリを使う。読む人のために機構を使う。
哲学者とアスリート:
アルゴリズムの能力と実行時性能。
<http://www.kmonos.net/alang/etc/ecmascript.php>
<http://hosho.ees.hokudai.ac.jp/~kubo/stat/2005/index.html>
<http://chasen.org/~daiti-m/paper/nl165pf.pdf>
スライドも。
トピック言語モデル、長距離言語モデルの最先端。
<http://www.isi.edu/natural-language/mt/aimag97.ps>
前半の概論が分かりやすいとのこと。
<http://www.isi.edu/~hdaume/>
Yet Another Haskell Tutorial
Why Not C?
Support Vector Machines for NLP
Bayes for NLPのチュートリアル、
テキストも作成中とか。
Bayesian Methods for NLP (summary) [nlp][stat][net]:
<http://nlpers.blogspot.com/2005/12/bayesian-methods-for-nlp-summary.html>
Bayesian と NLPer の会合。
論文なども少しだけど置かれている。
Leaving-one-out Perplexity の閉じた式の導出を含む。
ここでは、クラスベース言語モデルのための単語クラスタリングをやるのが目的。
あるクラスタリングがどれくらいよいかを評価するために、クラスベース言語モデルでの Leaving-one-out Perplexity を使っている。
その方法は、クラス=単語と考えれば、ほとんどそのまま、非クラスベース言語モデルでも使える。
1つだけ注意が必要なのは、単語のみに依存する項を(クラスタリングの評価には無関係なので)途中で消してしまっているところ。
それを消さずに、単語wのクラスをあたえる関数 G を G(w)=w とすれば、[2006-01-06-1]の Leaving-one-out Perplexity の式になる。
<http://www.cs.utoronto.ca/~ywteh/>
A Bayesian Interpretation of Interpolated Kneser-Ney.など。
Nonparametric Graphical Model とか。(よくわからない)
まわりを 1/10 消して、10/9 倍に拡大。
alias pstrim='pstops "1:0@1.111(-10.5mm,-14.65mm)"'
1/20 消して、20/19 倍
alias pstrim='pstops "1:0@1.0526(-5.25mm,-7.325mm)"'
<http://www.ee.columbia.edu/~stanchen/>
Smoothing 手法の概説と比較のレポートと Modified Kneser-Neyなど。
Absolute Discounting
P(w_i|w_{i-n+1}^{i-1})
= \cfraq{ \delta + c(w_{i-n+1}^{i-1}) }{ \delta + c(w_{i-n+1}^{i-2}) }
= \cfraq{ \delta + c(w_{i-n+1}^{i-1}) }{ \sum_w (\delta + c(w_{i-n+1}^{i-2} w)) }
= \cfraq{ \delta + c(w_{i-n+1}^{i-1}) }{ |V| \delta + c(w_{i-n+1}^{i-2}) }
where $V$ is the vocabulary
<http://www.cis.hut.fi/vsiivola/>
Growing an n-gram modelなど。
<http://en.wikipedia.org/wiki/Technological_singularity>
コンピュータの進化が加速度的に続いている → 人間の知性を越える臨界点が存在
→ 人間を越える知性は、さらに優れた知性を設計する
Good-Turing 法の Good も1965年に同じようなことをいっていたとか。
「単語 Unit, Phrase」の獲得と「同類語 Class」の獲得をいっしょにやってしまおうというアイディア。
単語とクラスは最初、どちらも文字(形態素でもよい)
単語の獲得のために、尤度変化を最大にする連接をくっつけることを繰り返す。
単語そのものの連接ではなくクラスの連接で尤度を評価し、
クラス同士をくっつける。
クラスの獲得のために、
Ries さんの方法では、当初、
単語の連結に際して、クラスも連結している。
のちの研究では、クラスは連結ではなく選択(主部、後ろのクラスを残す)にしたらしい。
Ries さんの方法の全体像:
まず、単語をクラスタリングする。
以降、単語の出現の代わりに、クラスの出現を数える。
全2-gramを列挙し、それを連結したときの全体の対数尤度の変化をテーブルに保持する。
対数尤度は、2-gramの出現頻度のみで決まる、場合わけのない簡単な式。
背景にはleaving-one-out(ある2-gramの出現の尤度を、その1出現をとりのぞいたコーパスから推定する)による尤度推定がある。
その変化量をあたえる式では、差分評価が困難な項は、ほとんどの場合変化がないとして無視する。
対数尤度がもっとも大きくなる連結を採用し、
対数尤度変化のテーブルを更新。
<http://citeseer.ist.psu.edu/galescu01bidirectional.html>
文字と音素の変換法。
たぶん音素的文字じゃないと使えない。
<http://citeseer.ist.psu.edu/tomokiyo98automatic.html>
結局、日本語でも Class-Phrase なのか、Phrase だけなのか?
モーラベースなので、Class を作る必要がないから、
たぶん Phrase だけだと思う。
<http://citeseer.ist.psu.edu/suhm94toward.html>
Ries さんの一連の Class-Phrase 言語モデルに関係する研究では、
・比較的小さな(それでもドイツ語で数万語レベル)の特定ドメインのコーパスで言語モデルをつくりたい
→小さなサンプルから母集団を推定するために、積極的なパターン抽出(クラスタリング)を行う
・書かれる単位としての単語と、意味を担う単位としての単語にはずれがある。
→連続する書記単語列を、語彙単語としてまとめる
Ries さんらは、最初に単語クラスタリングをしてから、
ボトムアップ式にフレーズまとめあげを行っている。
適切なチャンキングにより、適切なクラスタリングが促され、
クラスタリングによって確率推定のバックオフが提供されるという、
同時進行型の方法はないか?
<http://citeseer.ist.psu.edu/270515.html>
<http://citeseer.ist.psu.edu/577345.html>
n-gram の n を大きくしたとき、データ量もそれに応じて増やさない場合、精度向上につながらないことがある、
と明言している。
<http://citeseer.ist.psu.edu/734816.html>
Morphological Segmentation の新しい論文。
単語変形規則の探索か?
<http://doi.ieeecomputersociety.org/10.1109/34.476512>
[2006-01-24]の論文。
前半は、一般性の高い確率論で、事象の出現数同値類と Leaving-one-out による確率平滑化について。
後半は、言語モデリングにおける
Count equivalence class 出現数同値類
「頻度が同じ」という event(単語、単語クラス、…) のクラス。
C.e.c と cross-validation
C.e.c は訓練集合から作り、各クラスの確率推定は heldout集合から作る。
C.e.c と leaving-one-out
Leaving-one-out の概念と定式化↓
I.J.Good, "The population frequencies of species and the estimation of population parameters", Biometrica 40, 1953.
<http://citeseer.ist.psu.edu/471362.html>
クラスター(クラス)ベースの言語モデルについての概論を含む。
・基本的に、手法はクラスタリング
・「出現頻度が同じ」という簡易なクラスタリングもある
Predictive Clustering
P(w_i|w_{i-2} w_{i-1}) = P(c_i|w_{i-2} w_{i-1}) P(c_i|w_{i-2} w_{i-1})
w_1 w_2
w_1 w_2
c_3
w_1 w_2 w_3
c_3
w_1 w_2 w_3
c_3 c_4
Conditional Clustering
P(w_i|w_{i-2} w_{i-1}) = P(w_i|c_{i-2} c_{i-1})
w_1 w_2
w_1 w_2
c_1 c_2
w_1 w_2 w_3
c_1 c_2
w_1 w_2 w_3
c_1 c_2 c_3
クラス 2-gramから次の単語を予測。次の単語のクラスは自動的に決まる。
Combined Clustering
P(w_i|w_{i-2} w_{i-1}) = P(c_i|c_{i-2} c_{i-1}) P(w_i|c_{i-2} c_{i-1} c_i)
w_1 w_2
w_1 w_2
c_1 c_2
w_1 w_2
c_1 c_2 c_3
w_1 w_2 w_3
c_1 c_2 c_3
クラス 2-gram から次の単語のクラスを予測。クラス 3-gram から次の単語を予測する。
<http://www.ped.fas.harvard.edu/people/faculty/publications_nowak/RS04.pdf>
言語伝播とリミットサイクル。
ある人から別の人へ、文法が伝わる度合を表すモデルを設定している。
スムージングと、テストセット評価による言語モデル構築?
けっこう被引用数が多い。
引用先で解説されていたり?
<http://citeseer.ist.psu.edu/giuliani01unsupervised.html>
イタリア語。
ニュースの音響言語モデルと旅行対話音声から、旅行対話の音響、言語モデルを作る。
<http://portal.acm.org/citation.cfm?id=569061>
離散状態の Cellular Automata(CA) から、連続状態の Coupled Map Lattice(CML) へ。
CML をGPUに実装したという話。
単語同定の必要性(問題設定)に関する議論が必要。
言語モデル構築のためには、単語同定は必ずしも必要ではなく、
文字単位で構築することは可能。
ただ、計算の容易な固定長N-gramでは、精度と性能を両立するNが見付かる見込みが薄い。
→ 「一定の長さの列」により「一定の情報量を持つ」「最小の」単位=「単語」の必要性
このような問題に対して、日本語においては
・(形態素解析の上の、辞書拡充による言語モデル)…人手が強く介在
・文字列上の、superword言語モデル
などが提案されている。
人手が介在しない単語同定による、音声認識精度向上の報告はない。(要調査)
一方、英語などの空白区切り言語でも、
phrase 発見問題、phrase 単位の言語モデルの研究がなされている。
ex.) goint_to, and_so_on
あと、ベースを文字にするか形態素にするかの議論。
形態素解析には誤りが含まれること、辞書のない分野にも適応させたいことから、
文字ベースを採用。
ただし、手法としては、文字=形態素なアルファベットを想定すれば、
文字ベースの中に形態素ベースは含まれる。
(形態素は品詞情報が付いた文字)
問題設定の範囲外↓
上記のような「言語モデルのための単語」と似て非なる「単語」に関して。
言語学的単語:
1、母語話者が認定したものが単語 → 教師あり学習、品詞つき辞書
2、まとまった単位として再現性、交換可能性 → 文字列頻度の変化点を境界とするアイディア
「単語分割」関連研究の整理。
候補がたくさんあるなかで、どの単語を割り当てるべきか?という問題としての単語分割
→ 最長一致、尤度最大基準(EM)、品詞接続確率
言語モデル適応手法の中での位置づけ。
・クラスター言語モデルは、少ないデータから小さな言語モデルを作るもの。
単語としては出現するが、単語 n-gram が 0 頻度という問題に対処している。
・キャッシュベース言語モデル?
<http://www.google.com/search?q=nlp&hl=ja&lr=&start=0&sa=N>
最大勢力:Neuro-Linguistic Programming
ex. NLPインスティテュート
あとは色々
NLP Non Linear Programming
The Assoc. for Natural Language Processing Home Page Natural Language Processing
The Natural Law Party of the United States of America
<http://jamesthornton.com/cf/>
via
アルゴリズムマニアの日記
どうも、SUSE (もしかしたら Fedora Code も?)だとデフォルトが utf-8 になっていて、
eucjp を想定しているプログラムがこけたりする。
デフォルト文字コードは、環境変数で指定する:
export RUBYOPT="-Kn"
<http://en.wikipedia.org/wiki/Machine_learning>
<http://hawaii.aist-nara.ac.jp/~shige-o/pukiwiki/index.php?FrontPage>
ベイズ統計ファンサイト。
掲示板から派生する議論がけっこう盛り上がっている。
高校でのプログラミング教育に関する話題で、
手で触れる感触,ただのテキストで書かれた論理が結果を生み出すさま,を観察するのが大事だと感じます.自分が世界を支配している感触というのでしょうか.
<http://www.neurosci.aist.go.jp/~akaho/ibis/index.html>
<http://citeseer.ist.psu.edu/neal98view.html>
EM アルゴリズム。
1997年の長めの論文。EM の高速化手法。
The EM Algorithm -- an Old Folk-song Sung to a Fast New Tune
<http://cnx.rice.edu/content/col10204/latest/>
確率課程入門。
<http://people.csail.mit.edu/alanqi/>
Bayesian Conditional Random Fields
<http://citeseer.ist.psu.edu/mitarai00compressed.html>
圧縮されたデータ上でのパターンマッチング。
階層、非階層の辞書式圧縮の展開法の統一的な枠組も。
<http://citeseer.ist.psu.edu/nevill-manning97identifying.html>
文脈自由文法形式での圧縮。
連続する2つの非終端記号の連続が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