テキストマイニングのための基礎技術（前編）

テキストマイニングのための
基礎技術（前編）
北陸先端科学技術大学院大学
鶴岡慶雅
スケジュール
• １日目
10:00 – 12:00 データ構造、辞書、索引付け
12:00 – 13:00 昼食休憩
13:00 – 14:45 実習（検索エンジンの作成）
14:45 – 15:00 コーヒーブレイク
15:00 – 16:30 ベクトル空間モデル
資料
http://www.jaist.ac.jp/~tsuruoka/alaginseminar2010/
スケジュール
• ２日目
10:00 – 12:00 データマイニング入門、機械学習
12:00 – 13:00 昼食休憩
13:00 – 14:45 実習（クラスタリング、機械学習）
14:45 – 15:00 コーヒーブレイク
15:00 – 16:30 機械学習（続き）
資料
http://www.jaist.ac.jp/~tsuruoka/alaginseminar2010/
参考書
• Introduction to Information Retrieval
– Manning, Raghavan and Schütze
– Cambridge University Press. 2008.
– http://nlp.stanford.edu/IR-book/informationretrieval-book.html
• The Elements of Statistical Learning (2nd edition)
– Hastie, Tibshirani and Friedman
– Springer-Verlag. 2008
– http://www-stat.stanford.edu/~tibs/ElemStatLearn/
自己紹介
• 経歴
– 東京大学工学系研究科（工学博士）
– 東京大学理学部
• 科学技術振興機構研究員
– University of Manchester
• National Centre for Text Mining (NaCTeM)
– 北陸先端科学技術大学院大学
• 研究分野
– 自然言語処理
– テキストマイニング
– ゲームAI
激指（げきさし）
• コンピュータ将棋プログラム
• 2010年世界コンピュータ将棋選手権優勝（４度目）
• 機械学習を用いた探索制御、形勢判断
• レーティング：約3000点（プロ棋士レベル）
Windows XP/Vista/7
PlayStation2
PSP
ニンテンドーDS
デモ
• FACTA+
– 医学・生物学文献用の
情報検索システム
– 1700万文献
– 概念間の直接・間接的
な関係を検索
http://refine1-nactem.mc.man.ac.uk/facta/
デモ
• GENIA tagger
– 英語用の言語処理ツール
– Tokenization
– 品詞タグ付け
– 原型の出力
– 浅い構文解析
– 固有表現認識
http://www-tsujii.is.s.u-tokyo.ac.jp/GENIA/tagger/
テキスト処理のためのデータ構造
•
•
•
•
•
•
文書⇒数値列
ハッシュテーブル
辞書
Nグラム
転置インデックス
接尾辞配列
文字列から数値列へ
文書ID
文書
D0
Humpty Dumpty sat on a wall
D1
Humpty Dumpty had a great fall
D2
All the king's horses and all the king's men
D3
Couldn't put Humpty together again
• 文字列をそのまま扱うのは速度・メモリ効率が悪い
• 文字列を数値列に変換
入力を単語に分割（英語）
• Tokenization
Humpty Dumpy sat on a wall,
Humpty Dumpy sat on a wall ,
• ルールベースのスクリプト
– カンマ、ピリオド、括弧などを切り離す
– Tokenizer.sed
• http://www.cis.upenn.edu/~treebank/tokenizer.sed
入力を単語に分割（日本語）
• 単語分割
すももももももももものうち
すもももももももものうち
• 曖昧性が大きく英語よりもはるかに難しい
– 統計、機械学習を用いた手法が主流
– MeCab http://mecab.sourceforge.net/
– JUMAN http://www-lab25.kuee.kyoto-u.ac.jp/nl-resource/juman.html
単語列から数値列へ
文書ID
入力単語列
（tokenization済）
文書
D1
Humpty Dumpty sat on a wall
D2
Humpty Dumpty had a great fall
D3
All the king 's horses and all the king 's men
D4
Could n't put Humpty together again
文書ID
数値列
文書
D1
0 1 2 3 4 5
D2
0 1 6 4 7 8
D3
9 10 11 12 13 14 15 10 11 12 16
D4
17 18 19 0 20 21
単語と数値の対応表
Humpty Dumpty sat on a wall
Humpty Dumpty had a great fall
…
Humpty
0
Dumpty
1
sat
2
on
3
a
4
wall
5
had
6
great
7
fall
8
• 出現した単語列の辞書をつくる必要
• 単純に配列に格納すると、辞書引きのたびに
O(n) の計算量（n は辞書中の単語数）
連想配列
• 添え字に文字列を使える配列
例（Python)
dictionary.has_key(’Humpty’)
dictionary[’Humpty’] = 2
• 辞書引きの計算量
– O(1): ハッシュテーブルによる実装
– O(log n): 平衡2分探索木などによる実装
• 多くのプログラミング言語で標準装備
ハッシュテーブル（Hash Tables）
文字列
Humpty
数値（ハッシュ値）
261
int hash_function(string s)
h=0
for i = 0 to s.length
h = h * 101
適当な素数
h = h + s[i]
return h % hashtable.size
ハッシュテーブル
0
空き
:
:
260
空き
261
(Humpty, 0)
262
空き
:
:
1033
空き
• 文字列をハッシュ関数を用いて適当な数値に変換
• ハッシュテーブルのサイズで余りをとると、テーブル上での位
置が一意に決まる
• O(1) の計算量で辞書引きができる
ハッシュテーブル
• 衝突（collision）
– 違う文字列から同じハッシュ値が計算されてしま
うことがある
• チェイン法（chaining）
– エントリをリストへのポインターにして複数の要素
を保持する
• オープンアドレス法（open addressing）
– 空のエントリを探す
トライ木（Trie）
k
c
b
a
l
l
back
ball
t
bat
c
u
t
cut
• 前方一致検索が効率的に実行できる
• 実装：ダブル配列（double array）など
索引付け（indexing）
• 情報検索
– クエリーにマッチする文書を取得
• 基本操作：ある単語が出現する文書すべてを取得
• 文書を頭から単純にスキャンするのは、文書
量が増えると遅くなる
転置インデックス（inverted index）
• 単語ごとにそれが出現する文書IDのリスト
転置インデックス
単語
文書ID
文書
文書IDのリスト
Humpty
1, 2, 3
Dumpty
1, 2
sat
1
D1
Humpty Dumpty sat on a wall
on
1
D2
Humpty Dumpty had a great fall
a
1, 2
D3
All the king 's horses and all the king 's men
wall
1
D4
Could n't put Humpty together again
had
2
great
2
fall
2
:
:
全文検索
• 転置インデックスなどの単語ベースの索引付
けでは、全文検索ができない
• 全文検索
– クエリーの文字列が出現している場所をすべて
見つける
– 単語区切りの境界は関係なし
接尾辞配列（suffix array）
文書
abracadabra
Suffix Array
Suffix
Index
Index
0
abracadabra
1
bracadabra
2
racadabra
3
Suffix
10
a
7
abra
0
abracadabra
acadabra
3
acadabra
4
cadabra
5
adabra
5
adabra
8
bra
6
dabra
1
bracadabra
7
abra
4
cadabra
8
bra
6
dabra
9
ra
9
ra
10
a
2
racadabra
Suffixの辞書順
にソート
接尾辞配列（suffix array）
文書
abracadabra
Suffix Array
Index
10
a
7
abra
0
abracadabra
3
acadabra
5
adabra
8
bra
1
bracadabra
4
cadabra
2
6
dabra
3
9
ra
2
racadabra
文書中から ra が出現する位置
をすべて知りたい場合
Suffix Array 上で2分探索
Suffix
1
O(log n) で検索できる！
実習１検索エンジンの作成
•
•
•
•
•
ファイルから文書集合を読み込む
文書を単語列に変換
転置インデックスを作成
クエリー（単語）にマッチする文書を返す
余裕があれば全文検索も
ベクトル空間モデル
•
•
•
•
ベクトル空間モデル
tf-idf
類似度
再現率・適合率
ベクトル空間モデル
• 文書やクエリを高次元空間における点で表現
似てる文書
ベクトル空間モデル
• 単語の出現回数でベクトルを作ると
D1
Humpty Dumpty sat on a wall
d1 = (1, 1, 1, 1, 1, 1, 0, 0, 0)
単語 “Humpty” の出現回数
D2
Humpty Dumpty had a great fall
d2 = (1, 1, 0, 0, 1, 0, 1, 1, 1)
次元
単語
0
Humpty
1
Dumpty
2
sat
3
on
4
a
5
wall
6
had
7
great
8
fall
文書の類似度
• コサイン類似度（cosine similarity）
d1  d2
similarityD1, D2   cos  
d1 d2
– ベクトルが同じ方向を向いていれば１、直交してると０
例
D1
Humpty Dumpty sat on a wall
(1, 1, 1, 1, 1, 1, 0, 0, 0)
D2
Humpty Dumpty had a great fall
(1, 1, 0, 0, 1, 0, 1, 1, 1)
3
similarityD1, D2  
 0.5
6 6
参考
similarityD1, D4   0.167
tf-idf
• 単語の重み付け手法
– 頻度を直接用いた場合、機能語（a, the, on, to な
ど）の頻度に大きく影響される
– 意味的に重要な単語の重みを大きくしたい
重み
wd ,t  TFd, t  IDFt 
Term Frequency (TF)
TFd , t  
単語tの頻度
文書dの長さ
Inverse Document Frequency (IDF)
総文書数
IDFt   log
単語tを含む文書数
珍しい単語ほど重みが大きくなる
情報検索（information retrieval）
• クエリで取得したい情報を指定
クエリ
文書集合
性能評価
• 適合率（precision）
– 検索ノイズがどれだけ少ないか
• 再現率（recall）
– 検索漏れがどれだけ少ないか
• f-score
– 適合率と再現率の調和平均
性能評価
• 適合率（precision）
取得された関連文書数
P
取得された文書数
• 再現率（recall）
取得された関連文書数
R
関連文書数
• f-score
2
2PR
F

1 1 PR

P R
データマイニング入門
• クラスタリング
– 階層クラスタリング
– K-means クラスタリング
– スペクトラルクラスタリング
• 類似度・相関の計算
• 相関ルールの抽出
クラスタリング
• 似たようなサンプルをまとめあげる
– 階層的クラスタリング
– 非階層的クラスタリング
検索エンジン＋クラスタリング
http://clusty.com
階層的クラスタリング
• サンプル間に距離を定義
– 例ベクトル空間モデルによるコサイン類似度
• アルゴリズム
1. すべてのサンプルを個別のクラスタとして開始
2. もっとも近いクラスタ同士を統合し新たなクラス
タとする
3. すべてのクラスタが統合されるまで 2 に戻り繰り
返す
階層的クラスタリング
• 例
デンドログラム
（Dendrogram）
1
3
2
5
4
1
2
3
4
5
クラスタ間の距離の定義
最短距離法（single link）
重心法（centroid）
最長距離法（complete link）
群平均法（group-average）
階層的クラスタリング
• 計算量
– ナイーブに実装すると O(n3)
– 効率的な実装 O(n2 log n）
• サンプル数が多くなると大変
k-means法
• クラスタの重心
• 最小化 k
ci
d x, c  
i 1 xCi
2
i
• アルゴリズム
1. k個の代表点c1,…ckをランダムに選択
2. すべての点を代表点がもっとも近いクラスタに
割り当て
3. 各クラスタの重心を代表点にして２へ戻り繰り
返す
k-means法
• 実装が簡単
• 計算量が小さい
• クラスタ数 k をあらかじめ決めておく必要
• すべてのクラスタがほぼ同じサイズ
• 初期値のランダムな配置に依存
スペクトラルクラスタリング
spectral clustering
k-means
(Lee and Choi, 2004)
スペクトラルクラスタリング
• 準備
S  sij  類似度行列
di   j sij 頂点 i の次数（接続しているエッジの類似度の和）
D  diagd1 ,...,dn  次数行列
A
（サブ）グラフ A の頂点の数
vol A  iA di
グラフラプラシアン
• グラフラプラシアン（graph Laplacian）
正規化バージョン
~
L  I  D1S
L  DS
• 性質
N
N
N
i 1
i 1 i1
f T Lf   di fi 2   fi fi sii
1 N N
2
  sii  fi  fi 
2 i 1 i1
スペクトラルクラスタリング
• 入力：類似度行列 S, クラスタ数 k
1. グラフラプラシアンの固有ベクトルを固有値が
小さいものから k 個求める（最初のは無視）
2. それらの固有ベクトルを並べて行列 V を作成
3. 行列 V の個々の行を、k 次元空間上の位置と
みなし、頂点を空間上の点として配置
4. K-means アルゴリズムでそれらの点をクラスタリ
ング
スペクトラルクラスタリング
• グラフをサブグラフに分割
1 1
RatioCut A, B  cut A, B  
 A B
 1
1 

Ncut A, B  cut A, B

 vol A volB 
関連する概念・単語の抽出
• 糖尿病と関係が深い症状は？
文書ID
糖尿病
狭心症
痛み
疲労感
D1
1
1
1
0
D2
0
0
1
0
D3
1
1
1
0
狭心症
3
D4
1
1
1
1
痛み
4
D5
0
0
0
1
疲労感
2
D6
1
0
1
1
D7
0
0
1
0
D8
0
0
1
0
「糖尿病」との共起頻度
共起頻度
単に「痛み」がありふれた
単語だからでは？
Pointwise Mutual Information
• Pointwise Mutual Information (PMI)
P X , Y 
PMI  log 2
P X PY 
N  freq X , Y 
 log 2
freq X  freqY 
• 偶然共起するよりもどれだけ多く共起したか
– X と Y が独立なら PMI = 0
Pointwise Mutual Information
• 糖尿病と関係が深い症状は？
文書ID
糖尿病
狭心症
痛み
疲労感
D1
1
1
1
0
D2
0
0
0
0
D3
1
0
1
1
狭心症
0.74
D4
1
1
1
1
痛み
0.32
D5
0
0
1
1
疲労感
0.15
P(糖尿病) = 0.6
P(狭心症) = 0.4
P(痛み) = 0.8
P(疲労感) = 0.6
P(糖尿病, 狭心症) = 0.4
P(糖尿病, 痛み) = 0.6
P(糖尿病, 疲労感) = 0.4
「糖尿病」とのPMI
PMI
Symmetric Conditional Probability
• Symmetric Conditional Probability (SCP)
SCP  P X | Y PY | X 
freq X , Y  freq X , Y 

freqY  freq X 
freq X , Y 

freqY  freq X 
2
• 両方向の条件付確率の積
Symmetric Conditional Probability
• 糖尿病と関係が深い症状は？
文書ID
糖尿病
狭心症
痛み
疲労感
D1
1
1
1
0
D2
0
0
0
0
D3
1
0
1
1
狭心症
0.67
D4
1
1
1
1
痛み
0.75
D5
0
0
1
1
疲労感
0.44
P(糖尿病| 狭心症) = 1
P(糖尿病|痛み) = 0.75
P(糖尿病|疲労感) = 0.67
P(狭心症|糖尿病) = 0.67
P(痛み|糖尿病) = 1
P(疲労感|糖尿病) = 0.67
「糖尿病」とのSCP
SCP
相関ルール（Association Rule）の抽出
• パンとはちみつを買う人はバターも買う
Association Rule: {パン、はちみつ｝ ⇒ バター
履歴ID
パン
はちみつバター
牛乳
1
1
1
0
1
2
0
0
1
0
3
1
0
1
1
4
1
1
1
0
5
0
1
0
1
Association Rule の評価
• 相関ルール（Association Rule）
A B
• 支持度（support）
freqA, B
T A  B 
N
• 確信度（confidence）
freqA, B
C A  B 
freq A
• リフト（lift）
CA  B
freqA, B
LA  B 
N
T B
freqA freqB
テキスト処理のための機械学習
•
•
•
•
Naive Bayes モデル
平均化パーセプトロン
対数線形モデル、L1正則化
条件付確率場
教師付学習によるテキスト分類
• 学習データ
– 正解のラベルがついた事例（サンプル）の集合
文書ID
文書
正解カテゴリ
D1
Humpty Dumpty sat on a wall
好き（like)
D2
Humpty Dumpty had a great fall
好き（like）
D3
All the king's horses and all the king's men
嫌い（dislike）
D4
Couldn't put Humpty together again
嫌い（dislike）
• 未知の事例
文書
Humpty Dumpty hit a wall
正解カテゴリ
？
テキスト分類の応用
• テキスト分類
– 文書をトピックごとに整理する
– スパムメールのフィルタリング
– 製品レビューの自動判定（好意的かどうか）
– 文書のランキング
– etc.
Naive Bayes モデル
• Naive Bayes モデル
– 単純な確率的生成モデルを利用した分類器
Pros
• 確率値を出力
• 理論、実装が簡単
• 問題によっては高い分類精度
• 学習は非常に効率的
• 分類も高速
• 半教師付学習に簡単に拡張
可能
Cons
• 属性間の条件付独立性
を仮定
Bayes の定理
• Thomas Bayes (1702 – 1761)
P APB A
PA B 
PB
• 因果関係の順方向（確率的事象の生成方
向）のモデルを利用して、逆方向の確率を計
算することができる
Naive Bayes モデル
• 属性 a1, a2 ,...,an からなるサンプルの分類
cNB  argmax Pc j a1, a2 ,...,an 
cj
 argmax
cj

Pc j P a1 , a2 ,...,an c j
Pa1 , a2 ,...,an 

 argmax Pc j P a1, a2 ,...,an c j
cj
 
 argmax Pc j  P ai c j
cj
i


ベイズの定理
分母はクラスによらず
一定
属性の条件付独立性
Naive Bayes モデルによる分類
文書
正解カテゴリ
？
Humpty Dumpty hit a wall
 
cNB  argmax Pc j   P ai c j
5
c j like,dislike
i 1

 Pa

" Dumpty" c 
 argmax Pc j  P a1 " Humpty" c j
c j like,dislike
2
...

 P a5 " wall" c j
j

単語の条件付確率の推定
• データがスパースすぎて確率が推定できない
Pa2 " Dumpty" like
カテゴリ “like”の文書において
先頭から２番目の単語が “Dumpty” である確率
• 位置は無視
• add-one スムージング
freqwk , c j 1
freqwk , c j 1
P ai  wk c j 

freqwk , c j 1  freqw , c   Vocabulary


k
j
k
 k



学習
• 学習データから個々の確率値を推定
文書ID
文書
正解カテゴリ
D1
Humpty Dumpty sat on a wall
好き（like）
D2
Humpty Dumpty had a great fall
好き（like）
D3
All the king 's horses and all the king 's men
嫌い（dislike）
D4
Could n't put Humpty together again
嫌い（dislike）
2
Plike 
4
2
Pdislike 
4
2 1
PDumpty| like 
 0.088
12  22
0 1
PDumpty| dislike 
 0.026
17  22
Naive Bayes モデルの問題点
• 特徴間に条件付独立性を仮定している
• 実際には依存関係がある特徴を利用したい
場面が多い
例）単語の Unigram と Bigram
• 依存関係を気にせずに様々な特徴を使うこと
のできる機械学習モデルがほしい
Nグラム（n-gram）
• N個の単語（あるいは文字等）の並び
文書ID
文書
D1
Humpty Dumpty sat on a wall
D2
Humpty Dumpty had a great fall
D3
All the king's horses and all the king's men
D4
Couldn't put Humpty together again
Unigrams
Humpty
Dumpy
sat
on
a
:
Bigrams
Humpty Dumpty
Dumpty sat
sat on
on a
a wall
:
Trigrams
Humpty Dumpty sat
Dumpty sat on
sat on a
on a wall
：
パーセプトロン学習
• 学習とは、学習データを利用して、正例・負例
をうまく分離する平面を見つけること
パーセプトロン学習
• 学習データが線形分離可能であれば、学習
データを正しく分離する平面を見つけられる
線形モデル
• 線形モデルによる２値分類


yx  f wT x
 1, a  0
f a  
1, a  0
x
：サンプル
 x ：
w
特徴ベクトル
：重みベクトル
バイアス要素 0 x  1
重みベクトルと特徴ベクトルの内積をとって、それがゼロ以上
であれば +1 （正例と判定）、そうでなければ -1 （負例と判定）
を返す関数
パーセプトロン学習アルゴリズム
1. 重みベクトルを要素0で初期化
2. 学習データからランダムにサンプルを選択
3. 分類が間違っていたら以下の式で重みベク
トルを更新
w  w  x
 正例の場合
w  w x
 負例の場合
4. すべてのサンプルを正しく分類できるまで２
に戻り繰り返す
学習例 OR の学習
• 学習データ
1
 
 x2    0 
1
 
1
 
 x3    1 
 0
 
1
 
 x4   1
1
 
t1  1
t2  1
t3  1
t4  1
負例
正例
正例
正例
 1
 
 x1    0 
 0
 
Step 1
• x1
 0
 
w   0
 0
 
 1
 
 x1    0 
 0
 
t1  1
yx1   f 0 1  0  0  0  0
 f 0
1
不正解！
w  w x1 
 1
 
w  0 
0
 
Step 2
• x4
 1
 
w  0 
0
 
1
 
 x4   1
1
 
t4  1
yx3   f 11  0 1  0 1
 f 1
 1
不正解！
w  w  x4 
 0
 
w  1
1
 
Step 3
• x2
 0
 
w  1
1
 
1
 
 x2    0 
1
 
t2  1
yx2   f 0 1  1 0  11
 f 1
1
正解！
w w
 0
 
w  1
1
 
Step 4
• x3
 0
 
w  1
1
 
1
 
 x3    1 
 0
 
t3  1
yx3   f 0 1  11  1 0
 f 1
1
正解！
w w
 0
 
w  1
1
 
Step 5
• x1
 0
 
w  1
1
 
 1
 
 x1    0 
 0
 
t1  1
yx1   f 0 1  1 0  1 0
 f 0
1
不正解！
w  w x1 
 1
 
w  1 
1
 
分離平面
• 最終的な重みベクトル
 1
 
w  1 
1
 
分離平面
t
1
w  x  0
T
入力（特徴ベクトルの2番目、3番目の要素）を
それぞれ s, ｔとすると
1  s  t  0
s
1
なぜうまく学習できるのか？
• 正例の分類に失敗した場合


yx  f w  x
T
この部分の値が小さすぎた
w  w x
として重みベクトルを更新すると
w  x x  w x  x
T
T
もともとの値
2
必ず正
少なくとも同じサンプルに関しては間違いにくくなっている
平均化パーセプトロン
（Averaged Perceptron）
• 学習データが線形分離可能であるとは限らな
い ⇒ 収束しないかもしれない
• 過学習の危険性
• 平均化パーセプトロン
– 収束を待たない
– 重みベクトルは学習の開始から終了までの平均
をとったものを最終結果として出力する
平均化された重みベクトルの計算
• w の履歴をすべて保存しておく必要はない
w1  0
w 2  w1  u1
w3  w 2  u 2
w 4  w 3  u3
:
wT  wT 1  uT 1
求めたい平均
1 T
1 T 1
wt   T  t ut

T t 1
T t 1
1 T 1
 wT   tut
T t 1
和を１つのベクトルで
保持していけばよい
実習２機械学習
• Naive Bayes モデルによるテキスト分類器
• （平均化）パーセプトロンによる分類器
対数線形モデル
• 例品詞タグ付け
He
opened
it
Verb
素性（特徴量）
判定のための手がかり
単語が “opened”
最後の2文字が “ed”
最初の2文字が “op”
:
確率的に分類
• 品詞タグ： Noun もしくは Verb
scoreNoun
PNoun 
scoreNoun  scoreVerb
scoreVerb
PVerb 
scoreNoun  scoreVerb
確率的に分類
• 確率が素性の重みの掛け算で表されるとする
素性
He
opened
?
重み
suffix=ed & tag=Noun
2
suffix=ed & tag=Verb
7
prefix=op & tag=Noun
4
prefix=op & tag=Verb
3
it
2 4
PNoun 
 0.28
2 4  7 3
73
PVerb 
 0.72
2 4  7 3
尤度
• ３個の事例からなる学習データの尤度
She
closed
Noun
Verb
5 8
 0.57
5 8  6  5
65
PVerb 
 0.43
58  6  5
PNoun 
Features
Noun
23
 0.18
23  7  4
7 4
PVerb 
 0.82
23  7  4
PNoun 
Weight
:
it
:
suffix=ed & tag=Noun
2
suffix=ed & tag=Verb
7
prefix=cl & tag=Noun
3
prefix=cl & tag=Verb
4
:
:
1 9
 0.69
1 9  2  2
2 2
PVerb 
 0.31
1 9  2  2
PNoun 
likelihood  0.57 0.82 0.69
 0.32
尤度が大きくなるように素性の重みを
チューニングしたい
ちゃんと式で書くと
• 対数線形モデル
重み
素性関数
1


pw  y | x 
exp  wi fi x, y 
Z x   i



正規化 Z x   exp  wi fi x, y 
y
 i

• 素性関数
– 入力を特徴付ける
– 例
 1 if suffix of x is "ed" & y is Verb
f1234x, y   
 0 otherwise
対数線形モデルの学習
• 学習データの条件付対数尤度
log L  log  pw y j | x j 
j
  log pw y j | x j 
j
1


  log
exp  wi fi x j , y j 
Z x j   i
j



   wi fi x j , y j  log Z x j 
j  i

対数線形モデルの最尤推定
• 勾配
df gx df gx dgx

dx
dgx dx


 log L

   f k x j , y j 
log Z x j 
wk
wk
j 





   f k x j , y j 
log  exp  wi fi x j , y 
wk
j 
y
 i





1




   f k x j , y j 
exp  wi fi x j , y 


w


j 
 i

exp  wi fi x j , y  k y



y
 i






1

 

 f k x j , y exp  wi fi x j , y  
   f k x j , y j 


 y 
j 
 i
 


exp
w
f
x
,
y




i i
j


y
 i

対数線形モデルの最尤推定
• 勾配（続き）






exp  wi fi x j , y  

 log L


 i
 
   f k x j , y j   f k x j , y 


wk

 
j 
y



exp
w
f
x
,
y

 


i i
j

y
 i
 



   f k x j , y j   f k x j , y py | x j 
j 
y

素性の実際の
出現回数
現在のパラメータで確率的に分類した
ときの素性の出現回数の期待値
対数線形モデルの学習
• 尤度を最大にするパラメータを求める
–
–
–
–
勾配降下法
（擬似）ニュートン法
確率的勾配降下法
など
• 確率的勾配降下法は実装が簡単、収束も速い
勾配法
objective
w2
w1
正則化（regularization）
• 学習データに対するオーバーフィッティング
– 素性の重みにペナルティをかける
• L1 正則化
N


Lw  log p y j  | x j ; w  C wi
j 1
i
– ほとんどの素性の重みがゼロになる
– モデルサイズが小さい
– メモリ、ディスクスペースを節約
90
構造をもつ出力
• カテゴリ
例）テキスト分類
入力
解析器
• 系列
例）品詞タグ付け、固有表現認識、浅い構文解析
入力
解析器
• 木
例）構文解析、意味解析
.
入力
解析器
dictionary
ontology
text processing
raw
(unstructured)
text
part-of-speech
tagging
named entity
recognition
annotated
(structured)
text
syntactic
parsing
S
………………………....
... Secretion of TNF was
abolished by BHA in
PMA-stimulated U937
cells. ……………………
VP
VP
NP
PP
NP
NN
PP
PP
IN NN VBZ
VBN
IN NN IN
NP
JJ
NN NNS .
Secretion of TNF was abolished by BHA in PMA-stimulated U937 cells .
protein_molecule
organic_compound
negative regulation
cell_line
品詞タグ付け
（Part-Of-Speech Tagging）
Paul Krugman, a professor at Princeton University, was
NNP NNP , DT NN IN NNP
NNP , VBD
awarded the Nobel Prize in Economics on Monday.
VBN DT NNP NNP IN NNP IN NNP
• 個々の単語の品詞を解析
• 英語の品詞タグ例
NN: Noun
NNP: Proper noun
DT: Determiner
:
IN: Preposition
VBD: Verb, past tense
VBN: Verb, past participle
:
固有表現認識
（Named entity recognition）
We have shown that interleukin-1 (IL-1) and IL-2 control
protein protein protein
IL-2 receptor alpha (IL-2R alpha) gene transcription in
DNA
CD4-CD8-murine T lymphocyte precursors.
cell_line
• 固有表現カテゴリ例
•
•
•
•
Gene
Protein
Disease
etc.
構文解析
S
VP
NP
NP
VBN
QP
NN
VBD DT JJ
CD
CD
NNS
.
Estimated volume was a light 2.4 million ounces .
条件付確率場
（Conditional Random Fields）
• 系列を予測するための対数線形モデル
1
F n

P( y1...yn | x)  exp  i fi t, yt 1, yt , x
Z
 i 1 t 1

• 基本的には、分類のための対数線形モデルと同じ
• ただし、可能な出力の数が指数爆発するので少し
工夫が必要
条件付確率場
（Conditional Random Fields）
• 解決策
– 素性の形を限定
– 動的計画法（dynamic programming）を利用して計算量を
小さく抑える
• 使用可能な特徴（１次のモデルの場合）
– 品詞タグ
– 連続する品詞タグ
特徴量
• 特徴はノードとエッジ上に定義される
W0=He
&
Tag = Noun
He
has
opened
Noun
Noun
Noun
Noun
Verb
Tagleft = Noun
Verb
Verb
&
Verb
Tagright = Noun
it
Z(x) を単純に計算すると
Noun
Noun
Noun
Noun
Verb
Noun
Noun
Noun
Noun
Noun
Noun
Verb
Verb
Noun
Noun
Verb
Noun
Noun
Verb
Noun
Verb
Noun
Verb
Noun
Noun
Noun
Verb
Verb
Verb
Noun
Verb
Verb
Noun
Verb
Noun
Noun
Verb
Verb
Noun
Noun
Noun
Verb
Noun
Verb
Verb
Verb
Noun
Verb
Noun
Verb
Verb
Noun
Verb
Verb
Verb
Noun
Noun
Verb
Verb
Verb
Verb
Verb
Verb
Verb
動的計画法
• 計算の途中結果を再利用
He
has
opened
it
Noun
Noun
Noun
Noun
Verb
Verb
Verb
Verb
forward
動的計画法
• 計算の途中結果を再利用
He
has
opened
it
Noun
Noun
Noun
Noun
Verb
Verb
Verb
Verb
backward
動的計画法
• 周辺分布の計算
He
has
opened
it
Noun
Noun
Noun
Noun
Verb
Verb
Verb
Verb

Download Report