言語モデル論めも

後半戦を適当にググった内容と考えたことのメモ。
全く授業を聞いてないので間違っていると思う。。

とりあえず

http://togetter.com/mt/carbon_twelve

N-gram

http://ja.wikipedia.org/wiki/全文検索#N-Gram
検索のインデックスを作る方法の１つ。
たぶん、vector<string> ss; for(int i = 0; i < (int)ss.size()-k; i++)でss.sub(i,k)をキーにしてインデックスを作る。
形態素解析をするのに比べ、精度も悪いし検索時速度も遅いしインデックスの量も多くなるが、言語に依存しないため実装は楽

Zipfの法則

http://ja.wikipedia.org/wiki/ジップの法則
k番目に多い要素が全体に占める割合は1/kに比例するという経験則らしい。

ロングテール

http://ja.wikipedia.org/wiki/ロングテール
全体に占める割合が少ない要素はたくさんあることを示している言葉だと思う。

スムージング

謎。統計データの凹凸をならすと式を推定しやすくなりそうなので、そのならす段階のこと？

ん？

なんかおかしい。 「言語モデル　スムージング」でググったら色々でてきた
http://unicorn.ike.tottori-u.ac.jp/2009/s062041/paper/graduation-thesis/node11.html
http://unicorn.ike.tottori-u.ac.jp/2009/s062041/paper/graduation-thesis/node17.html
http://unicorn.ike.tottori-u.ac.jp/2009/s062041/paper/graduation-thesis/node24.html
よくわからない。。とりあえず飛ばす。

統計的機械学習

http://www.r.dl.itc.u-tokyo.ac.jp/node/33
http://www.r.dl.itc.u-tokyo.ac.jp/~nakagawa/SML/index-SML.html
http://ja.wikipedia.org/wiki/機械学習
機械学習にはだいたい３種類ある

• 教師あり学習
• 教師なし学習
• 強化学習（またの名を半教師あり学習？）

特徴ベクトル

って何だろう。。
http://www.nal.ie.u-ryukyu.ac.jp/wiki/index.php?yono/Pythonで自然言語処理
この人は、

文書における特徴ベクトルは，多くの場合文書中の単語を要素，重みとして出現頻度やTF-IDFによって表現されます．

と書いているが。。

特徴空間, 決定境界

なにやら、パターン認識の話らしい。
とりあえず、この図で分かった気になる

線形分類器

http://ja.wikipedia.org/wiki/線形分類器
線形識別器とも。
決定境界を線形（平面）と仮定した時に、その境界を求めるアルゴリズム。

パーセプトロン

http://ja.wikipedia.org/wiki/パーセプトロン
http://d.hatena.ne.jp/AntiBayesian/20111125/1322202138
一般的な説明？としては、「ニューラルネットの一種。脳と視覚の機能をモデル化したものであり、パターン認識を行う」らしい。
線形分類器の１つ。適当に決めた境界を少しずつ改善していって境界を決めるアルゴリズム。
詳しくは、２つめのリンク参照。

ログ線形モデル

対数線形モデルとも（？）

• Y = a * b ^ Xみたいなモデルっぽい。

サポートベクトルマシン

http://ja.wikipedia.org/wiki/サポートベクターマシン
略してSVM。教師あり学習を用いる識別手法の一つ。めっちゃ強い。

隠れマルコフモデル

http://ja.wikipedia.org/wiki/隠れマルコフモデル
これはさすがに知ってる。

ビタビアルゴリズム

http://ja.wikipedia.org/wiki/ビタビアルゴリズム
隠れマルコフモデルのパラメータが既知で、観測された事象の列が与えられた時、状態（通常賽？シゴロ賽？）の遷移のうちもっとも尤もらしいものを推定するアルゴリズム。DP。

教師あり学習, 教師なし学習

http://ja.wikipedia.org/wiki/教師あり学習
http://ja.wikipedia.org/wiki/教師なし学習
なんとなく意味は分かる。

EMアルゴリズム

http://ja.wikipedia.org/wiki/EMアルゴリズム
よくわからない

前向き確率, 後ろ向き確率

http://anlp.jp/NLP_Portal/glossary/index.html

隠れマルコフモデル(HMM, hidden markov model)において，初期ノードからあるノードまでにある時系列データが生成される確率のことを前向き確率という．トレリス上を前向きに辿り動的計画法により順次求めることから前向きという名前が付いている．同様に，後向きに辿る後向き確率(backward probability)もある．隠れマルコフモデルのパラメータ推定アルゴリズム(Baum-Welchアルゴリズム)では，前向き/後向き確率両方を用いてパラメータ推定に必要な確率を計算する．

らしい。
関連: http://ja.wikipedia.org/wiki/バウム＝ウェルチアルゴリズム

自然言語処理

http://ja.wikipedia.org/wiki/自然言語処理

構文解析

http://ja.wikipedia.org/wiki/構文解析

文脈自由文法

http://ja.wikipedia.org/wiki/文脈自由文法
＼文脈自由文法／

CKY法

http://ja.wikipedia.org/wiki/CYK法
L*LF*S...

確率文脈自由文法

http://ja.wikipedia.org/wiki/確率文脈自由文法
各生成規則に確率があって、より尤もらしい構文解析が可能。になりそう

ビタビアルゴリズム

再び。CKYはboolのdpだけど、それを確率でやるとかだろうか

情報検索

http://ja.wikipedia.org/wiki/情報検索

転置インデックス

http://ja.wikipedia.org/wiki/転置インデックス
wikipediaの例がわかりやすい。何が転置なのかよくわからない

接尾辞配列

http://ja.wikipedia.org/wiki/接尾辞配列
suffix arrayとも。接尾辞の検索がO(n)で出来るようになる。前処理は普通にやるとO(nlogn)だけど、O(n)で出来るとか授業で言ってた。

ベクトル空間モデル

http://ja.wikipedia.org/wiki/ベクトル空間モデル
http://c-faculty.chuo-u.ac.jp/~saitotac/2003Gradu/matsuda/4no5.htm
読めば分かりそう。

リンク解析

たぶん、ページを頂点リンクを辺としたグラフを考えるんだろう
ぐぐってもノイズしかヒットしなくてうざい

ランク学習

http://www.slideshare.net/sleepy_yoshi/dsirnlp1
http://www.slideshare.net/tkng/confidence-weighted
PageRank的な話？あとで読む。

クラスタリング

http://ja.wikipedia.org/wiki/データ・クラスタリング
http://ja.wikipedia.org/wiki/ウォード法
http://ja.wikipedia.org/wiki/K平均法
クラスタリングの意味はなんとなく分かる。

---

Categoryノート