大量のWeb 文書からの対訳テキスト抽出手法

1
大量のWeb 文書からの
対訳テキスト抽出手法
*斎藤大
田浦健次朗
近山隆
東京大学
{std, tau, chikayama}@logos.ic.i.u-tokyo.ac.jp
JSSST ’07 : 情報爆発(3)
2015/10/1
2
JSSST ’07 : 情報爆発(3)
2015/10/1
対訳テキスト
対訳テキスト：
意味内容は同一
異なる言語で記述
対訳コーパス：
対訳テキストの集合
English
One thing was certain,
--it was the black kitten's
that the WHITE kitten had had
fault entirely.
nothing to do with it.
一つ確実なのは、
――もうなにもかも、
白い子ネコはなんの関係も
黒い子ネコのせいだったのです。
なかったということ。
自然言語レベルの翻訳関係
日本語
3
JSSST ’07 : 情報爆発(3)
2015/10/1
対訳コーパス
• 多言語処理分野の有用なリソース
▫ 統計的機械翻訳
▫ 対訳辞書構築
• 既存のコーパスに制限が存在
言語
英-仏
英-日
ジャンル
政府公式文書
ソフトウェアマニュアル
数
不十分
新規構築が困難
4
JSSST ’07 : 情報爆発(3)
2015/10/1
目的
Webから自動で対訳コーパスを生成
大量
多様な言語
Web
- 対訳テキストの自動判定手法 [06 福島]
- 大量のテキストの計算コスト削減手法
5
JSSST ’07 : 情報爆発(3)
発表の流れ
• 概要
• 関連研究
• 提案手法
▫ 対訳判定
▫ 判定数削減
• 実験・評価
• まとめ
2015/10/1
6
JSSST ’07 : 情報爆発(3)
発表の流れ
• 概要
• 関連研究
• 提案手法
▫ 対訳判定
▫ 判定数削減
• 実験・評価
• まとめ
2015/10/1
7
JSSST ’07 : 情報爆発(3)
2015/10/1
STRAND [Resnik et al. 03]
•
URL マッチング
http://www.hostname.com/index.html.en
http://www.hostname.com/index.html.ja
1. Language-Specific Substrings[LSSs]を削除
(Japanese : ja, jp, jpn, euc, sjis,…)
2. LSSs を削除された URL でマッチング
3. 文字列が一致したペアのみ詳細な比較
8
JSSST ’07 : 情報爆発(3)
2015/10/1
DOM Tree Alignment [Lei et al. 06]
• HTML→DOM Tree
link
• リンク構造を利用
▫ タグの“alt”
▫ リンク名
“English version”
“In English” …
link
• Parallel link: 対訳テキスト中で“同じように”
リンクが張られているペア
9
JSSST ’07 : 情報爆発(3)
2015/10/1
関連研究まとめ
• STRAND
○計算コストが低い
×取得可能な対訳が少ない
• DOM Tree Alignment
○一つの対訳発見で複数の対訳取得の可能性
×DOM Tree変換は計算コストが高い
10
JSSST ’07 : 情報爆発(3)
発表の流れ
• 概要
• 関連研究
• 提案手法
▫ 対訳判定
▫ 判定数削減
• 実験・評価
• まとめ
2015/10/1
11
JSSST ’07 : 情報爆発(3)
2015/10/1
概要
Crawler
Web
…
…
…
…
対訳候補ペアの絞込み
対訳判定 [福島 06]
12
JSSST ’07 : 情報爆発(3)
2015/10/1
対訳判定 [福島 06]
▫ 低コストな対訳判定
▫ HTML情報を利用しない
▫ テキスト名詞抽出→意味ID変換→比較
13
JSSST ’07 : 情報爆発(3)
2015/10/1
意味ID変換
• 対訳辞書からグラフを構築
▫ 意味的に連結している
単語は同じID
• 意味ID数:
約10,000
[EDR電子化辞書]
Sense
Movie
感覚
１
意味
２
Film
映画
Hobby
趣味
Taste
味
３
14
JSSST ’07 : 情報爆発(3)
2015/10/1
テキスト→意味ID列変換
テキスト 955
辞書を使ってテキストを数列に変える。
…
辞書
1704
1704
…
数列
3173
955
3173
sort
(955, 1704, 3173)
+テキスト中の位置情報
15
JSSST ’07 : 情報爆発(3)
2015/10/1
対訳の評価
• tscore (translation score)
T1:(106, 335, 455, 567, 1704, 3173, 7421)
T2:(335, 567, 567, 1704, 4014, 5449, 7421)
score= 4
12
0
3
tscore = 4/(7+7)
tscore  score
O(#T1# T 2)
# T1 # T 2
16
JSSST ’07 : 情報爆発(3)
tscore threshold
• Fry Corpus[05 Fry]
• tscore threshold
0.102
• F値
0.982
• Speed
200,000 pairs/sec
2015/10/1
17
JSSST ’07 : 情報爆発(3)
2015/10/1
対訳候補ペアの絞り込み
• 対訳判定自体の計算コスト
• Web上の対訳テキスト抽出の計算コスト
▫ 単純な全対全比較→コスト： O(n2 )
▫ URL マッチング→制限が強すぎる
 JapaneseとEnglishで
90,000,000URL → 4,000URLペア→ 1,000ペア
 jaやenが含まれない対訳も存在（ニュース記事等）
18
JSSST ’07 : 情報爆発(3)
2015/10/1
計算コスト削減
Sample
→無駄な対訳判定を削減
前提：対訳テキストは互いに似ているので
特定のサンプルテキストとの距離は
同程度となる
▫ 距離の尺度(類似度) : tscore
▫ 距離が近いテキストペアのみ判定
English
日本語
19
JSSST ’07 : 情報爆発(3)
2015/10/1
計算コスト削減
•
流れ
1.
2.
3.
4.
(n:テキスト数)
サンプル数によって
精度や計算時間が変化
サンプルテキストを選択 (<<n)
各テキストとサンプルの距離を計算
最も近いm個のサンプルに振り分け
同じグループ内でのみ全対全比較
①振り分け時間
②対訳判定時間
20
JSSST ’07 : 情報爆発(3)
2015/10/1
次元削減
• 意味ID数：約10,000 を削減することで高速化
▫ 振り分けにかかる時間を削減
• “有用”な意味IDを抽出
▫ LDA (Latent Dirichlet Allocation)を用いる
▫ トピック分類に役に立つ単語を抽出
21
JSSST ’07 : 情報爆発(3)
2015/10/1
LDA [Blei et.al. 03]
• 多重トピック文書のモデル化
▫ トピックが生成される確率
▫ (トピックから)単語が生成される確率
• 事前にトピック数を与える
• 変分ベイズを用いてパラメータ推定
• トピック毎に単語の出現確率が
数値として示される＝比較可能
22
JSSST ’07 : 情報爆発(3)
発表の流れ
• 概要
• 関連研究
• 提案手法
▫ 対訳判定
▫ 判定数削減
• 実験・評価
• まとめ
2015/10/1
23
JSSST ’07 : 情報爆発(3)
2015/10/1
実験概要
• 実験内容
▫ 単純な全対全手法との計算コスト比較
▫ サンプル数による正解率と計算コストの変化
▫ 意味ID数削減による振り分けコスト比較
• 実験環境
▫ データ：Fry Corpus [Fry 05]
 日英対訳ニュース記事のURLペア一覧
 事前にHTMLを意味ID列に変換
▫ 環境
 CPU : Xeon 2.4GHz Dual
 Memory : 2GB
 OS : Linux (Debian)
24
JSSST ’07 : 情報爆発(3)
2015/10/1
• Fry Corpus
▫ 200～6400ペア
• 全対全比較
Execution Time [sec]
計算コストの評価
ランダムサンプリング
(Top3)
n^2
sampling(√n/2)
sampling(√n)
# of pairs
テキスト数が増えるほど時間差大
サンプル数 n の方がコスト削減
25
JSSST ’07 : 情報爆発(3)
2015/10/1
精度と計算時間の評価
• ランダムサンプリング
▫ サンプル数増加すると
 誤分類率→増
 実行時間→少
miss classification ratio
execution time
# of samples
誤分類率と実行時間のトレードオフ
execution time [sec]
▫ 400ペア
miss classification ratio [%]
• Fry Corpus
26
JSSST ’07 : 情報爆発(3)
2015/10/1
次元削減の評価
• Fry 6400ペアに対してトピック数20でLDA
▫ 各トピックの分類に有用な意味IDを抽出
 Top20 : 152個 (/400個)
 Top50 : 350個(/1000個)
• 単語比較回数削減
▫ 200ペアの全対全比較
×4/9
normal
LDA50
比較回数
×1/4
LDA20
1.69 × 10^8 7.66 × 10^7 3.80 × 10^7
• 振り分け時の誤分類率と単語比較回数を測定
27
JSSST ’07 : 情報爆発(3)
2015/10/1
miss classification ratio[%]
次元削減の評価
normal
誤分類率を維持しつつ
計算コスト削減
振り分けの高速化
LDA50
LDA20
normal
# of samples
# of word comparison
normal
2/3
LDA50
lda50
1/2
LDA20
lda20
tscore
# of samples
28
JSSST ’07 : 情報爆発(3)
2015/10/1
実験まとめ
• 計算コストの評価
▫ サンプリングを行うことで計算コスト削減
• 精度と計算コストの評価
▫ サンプリングの精度と計算時間はトレードオフ
• 次元削減の評価
▫ 精度は維持したまま振り分け時の計算コスト削減
29
JSSST ’07 : 情報爆発(3)
発表の流れ
• 概要
• 関連研究
• 提案手法
▫ 対訳判定
▫ 判定数削減
• 実験・評価
• まとめ
2015/10/1
30
JSSST ’07 : 情報爆発(3)
まとめ
• Webからの対訳テキスト抽出
▫ 高速な対訳判定手法
▫ 対訳判定回数の削減手法
 サンプリング
 LDAを用いた次元削減
▫ 日英対訳コーパスを用いた評価
2015/10/1
31
JSSST ’07 : 情報爆発(3)
2015/10/1
今後の課題
• 並列化
• 軽量なクラスタリング
▫ サンプリングより精度の良い振り分け方法
• 実際のWebを対象
▫ ニュース記事
▫ Web Directory
32
JSSST ’07 : 情報爆発(3)
2015/10/1

Download Report