狠狠撸

【 WWW2012 勉強会】

Session 30: Information Extraction

担当：塚原裕史（デンソーアイティーラボラトリ）

論文リスト

? "Micropinion Generation: An Unsupervised Approach to Generating
Ultra-Concise Summaries of Opinions",
? Kavita Ganesan, ChengXiang Zhai, Evelyne Viegas
? 要旨 :
? 人が読んで分かる要約文生成
? タグ付けや教師データを必要としない

? "A Flexible Large Scale Topic Modeling Package using Variational
Inference in MapReduce",
? Ke Zhai, Jordan Boyd-Graber, Nima Asadi, Mohamad Alkhouja
? 要旨 :
? MapReduce 形式による変分ベイズ法を用いた LDA 計算法
? Callapsed Gibbs Sampling よりもスケールアウトできる

2 Session 30: Information Extraction 担当：塚原裕史（デンソーＩＴラボ
ラトリ）

Paper 1
"Micropinion Generation: An Unsupervised Approach to Generating Ultra-Concise Summaries of Opinions", 　
Kavita Ganesan et. al.

?モチベーション
? ブログやニュース記事として、多くの評判情報が集まっており、
これらの評判を文章として段階的に要約し、内容を理解できるよ
うにしたい。

? “micropinion” と呼ぶ

? これまでの評判情報要約では、元の文章とは異なる構造化された
簡潔な情報に変換されていたので、上記のようなことができなか
った：

? 単純な極性判別：　“ positive” or “negative”
? カテゴリごとの評価値 : 　 buttery life: 1 star, screen: 3.5 star etc.
? Key words or phrases extraction ：　 buttery, life, screen, short, clear, etc.

ラトリ）

Paper 1

?Micropinion の事例 ( 制約： less than 10 words)

? MP3 Player Y: (8 words)
? Very short battery life. Big and clear screen.

? Restaurant X: (9 words)
? Good service. Delicious soup dishes. Very noisy at nights.

?ポイント
? 可読な文への要約
? 最大単語数を設定可能

ラトリ）

Paper 1

?方法
? フレーズの代表性と可読性の指標を設計し、それらの和を最大化
するフレーズ（単語の組合せ）の組みを検索する。（最適化問題
）

?代表性
? フレーズ内の各単語のローカル相互情報量の平均値
? ローカル相互情報量：　コンテキストウインドウ内での補正相互情報量の
平均値
? 補正相互情報量：　コンテキストウインドウ内で共起し易い単語間で値が
大きくなるように、ヒューリスティックな補正を入れたもの。
? 通常の相互情報量では、頻出しない単語間で値が大きくなり、代表性という観点
では問題がある。
?可読性
? N-gram 言語モデルによる対数尤度の平均値
5
? Microsoft の trigram 言語モデル使用担当：塚原裕史（デンソーＩＴラボ
Session 30: Information Extraction
ラトリ）

Paper 1

?最適化手順
? １．シードとなるバイグラム生成
? ２． N グラム候補生成
? ３．候補 N グラムから候補フレーズ生成
? ４． Depth-first search による Micropinion 決定
フレーズ m スコア
w1 w2 w4 w8 S rep ( m ) + S read ( m )

候補Ｎグラム w1 w2 w4 w5 w6 w8

シードバイグラム w1 w2 w3 w4 w5 w6 w7 w8

ラトリ）

Paper 1

?評価
? データセット
? CNET における製品レビューデータ
? 定量的評価指標
? ROUGE
? 定性的評価指標
? Gramaticality
? Non-redundancy
? Informativeness
? ベースライン ( 従来手法 )
? TF-IDF ベース
? KEA
? Opinosis

ラトリ）

Paper 1

?結論
? 主要な提案：
? 代表性と可読性に基づく最適化問題による定式化
? 上記最適化問題の高速な近似解探索手法を提案

? 主要な性質：
? 従来手法にくらべて、可読性の高い要約文を生成できる

? モデル的に有利な点：
? 教師なし学習　→　低コスト
? 計算量が小さい　→　高速
? 形態素解析や構文解析不要　→　多言語への拡張性

ラトリ）

Paper 2
"A Flexible Large Scale Topic Modeling Package using Variational Inference in MapReduce", 　
Ke Zhai et. al.

? モチベーション
? LDA の計算手法として Collapsed Gibbs Sampling が良く使われている
? 実装が簡単
? Collapsed Gibbs Sampling は、並列化してもパフォーマンスが出ない
? ノード全体で共有する状態があるため（実際には定期的に同期を取りながら計算）
? 明確な収束判定基準がない

? Collapsed Gibbs Sampling での計算
? (#topics in a document) * (#words in a topic across all documents)

この部分で同期が必要となり並列化の効率に影響

ラトリ）

Paper 2
Ke Zhai et. al.

? 方法
? 変分ベイズ法による LDA 計算を MapReduce の形式へ並列化

? 変分ベイズ法における反復更新処理
φ v(,d ) ∝ Eq [ β v ,k ]e Ψ ( γ k )
k

文書ごとの処理 Map
V
γ d ,k = α k + ∑ φ v(,d )
k
v =1

λv ,k = η v ,k + ∑ ( wv( d )φv(.dk ) )
C
文書全体での処理 Reduce
d =1

α new = α old ? H ?1 ( α old ) g ( α old ) モデル全体の制御 Driver

ラトリ）

Paper 2
Ke Zhai et. al.

? MapReduce での処理の流れ
Hyperparameters
Mapper (α k , λv ,k ) t → (α k , λv ,k ) t +1

文書

d (γ d ,k ) ?
?
? K ??
, φ v(,d ) → ? γ d , k , φ v(,d ) , Ψ ( γ d , k ) ? Ψ ? ∑ γ d , k ? ?
?
Reducer
t
? k =1 ? ?t +1
k k
?

(η , {φ }) ? ? K ??
C

v ,k
(d )
→ ? λv ,k , ∑ Ψ (γ d ,k ) ? Ψ? ∑ γ d ,k ? ?
? ?
t
? k =1 ? ?t +1
v ,k
? d =1

(γ ) ? ? K ?? Driver
d d ,k , φ v(,d ) → ? γ d , k , φ v(,d ) , Ψ ( γ d , k ) ? Ψ ? ∑ γ d , k ? ?
k t
?
?
k
? k =1
?
? ?t +1

(η , {φ })
v ,k
(d )
v ,k t
?
?
?
C

d =1
? K
? k =1
??
→ ? λv ,k , ∑ Ψ (γ d ,k ) ? Ψ? ∑ γ d ,k ? ?
?
? ?t +1
(α k ) t → (α k ) t +1
d (γ d ,k ) ? ? K ??
? ?
t
? k =1 ? ?t +1
k k
?

(η , {φ }) ? ? K ??
C

v ,k
(d )
→ ? λv ,k , ∑ Ψ (γ d ,k ) ? Ψ? ∑ γ d ,k ? ?
? ?
t
? k =1 ? ?t +1
v ,k
? d =1

Test Convergence
d (γ ) ?
?
? K ??
?
(Likelihood Computation)
d ,k t
? k =1 ? ?t +1
k k
?

partitioner

ラトリ）

Paper 2
Ke Zhai et. al.

? 結論
? 従来実装 (Mahout) に比べて、処理速度?事後分布の近似精度の
両面で、非常に良く改善されている。
（論文から引用）
事
L = Eq [ log( p ( D Z ) p ( Z Θ ) ) ] ? Eq [ log q( Z ) ] 後
分
布
変分ベイズでは、この量を最大化するへ
の
下
限
学習時間

? Remark
? Collapsed Gibbs Sampling の並列化に関しては Mallet というラ
イブラリがあるが、それとの比較がないので、変分ベイズ法の方
が本当に良いと言って良いのか、実際にどれくらいの差があるの
か気になる。

ラトリ）

狠狠撸

Information extraction 1

Recommended

More Related Content

What's hot (20)

Viewers also liked (20)

Similar to Information extraction 1 (20)

Information extraction 1