Document

Web 上の対訳テキストの
大規模高速抽出手法
*斎藤大吉田慎一郎田浦健次朗近山隆
東京大学
{std, s-yoshida, tau, chikayama}@logos.ic.i.u-tokyo.ac.jp
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
1
目的
Webから自動で対訳コーパスを生成
対訳テキスト：
English
意味内容は同一
異なる言語で記述
One thing was certain,
--it was the black kitten's
that the WHITE kitten had had
fault entirely.
nothing to do with it.
日本語
一つ確実なのは、
――もうなにもかも、
白い子ネコはなんの関係も
黒い子ネコのせいだったのです。
なかったということ。
テキストレベルの翻訳関係
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
2
対訳コーパス
言語処理分野の有用なリソース
統計的機械翻訳
対訳辞書構築
既存のコーパスでは不十分
言語
ジャンル
• 限定
• 例：英-仏
2007/03/23
• 政府公式文書
• ソフトウェアマニュアル
数
• 不十分
• 新たな構築も大変
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
3
Web上の対訳テキスト
Web上の対訳テキストを自動抽出
大量
多様な言語
低コスト
- 対訳テキストの自動判定手法
- 大量のテキストを扱う計算コスト
Web
2007/03/23
対訳候補抽出
対訳判定
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
4
発表の流れ
概要
関連研究
提案手法
対訳判定
判定数削減
実験・評価
まとめ
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
5
発表の流れ
概要
関連研究
提案手法
対訳判定
判定数削減
実験・評価
まとめ
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
6
STRAND [Resnik et al. 03]
URL マッチング
http://www.hostname.com/index.html.en
http://www.hostname.com/index.html.ja
1.
2.
3.
2007/03/23
Language-Specific Substrings[LSSs]を削除
(Japanese : ja, jp, jpn, euc, sjis,…)
LSSs を削除された URL でマッチング
マッチしたペアのみ詳細な比較
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
7
DOM Tree Alignment [Lei et al. 06]
HTML→DOM Tree
link
リンク構造を利用
“alt” タグ
リンク名
“English version”
“In English” …
link
Parallel link: 対訳テキスト中で”同じように”
リンクが張られているペア
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
8
発表の流れ
概要
関連研究
提案手法
対訳判定
判定数削減
実験・評価
まとめ
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
9
概要
Crawler
Web
…
…
…
…
対訳候補ペアの絞込み
対訳判定 [福島 06]
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
10
対訳判定 [福島 06]
低コストな対訳判定
HTML情報を利用しない
テキスト→意味ID→比較
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
11
意味ID変換
対訳辞書からグラフを構築
意味的に連結している
単語は同じID
Sense
Movie
意味ID数:
約10,000
[EDR電子化辞書]
2007/03/23
感覚
１
意味
２
Film
映画
Hobby
趣味
Taste
味
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
３
12
テキスト→数列変換
テキスト 955
辞書を使ってテキストを数列に変える。
…
辞書
1704
1704
…
数列
3173
955
3173
sort
(955, 1704, 3173)
+テキスト中の位置情報
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
13
対訳の評価
tscore (translation score)
T1:(106, 335, 455, 567, 1704, 3173, 7421)
T2:(335, 567, 567, 1704, 4014, 5449, 7421)
score= 3
24
1
0
tscore = 4/(7+7)
2007/03/23
tscore  score
# T1 # T 2
O(#T1# T 2)
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
14
tscore threshold
Fry Corpus[05 Fry]
F値
0.982
tscore threshold
0.102
Speed
200,000 pairs/sec
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
15
対訳候補ペアの絞り込み
対訳判定自体の計算コスト
Web上の対訳テキスト抽出の計算コスト
単純な全対全比較→コスト： O(n2 )
URL マッチング→フィルタが厳しすぎる
• JapaneseとEnglishでマッチング
• 90,000,000URL → 4,000ペア
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
16
計算コスト削減
Sample
→無駄な対訳判定を削減
前提：対訳関係にあるテキスト間の
特定のサンプルテキストとの距離は
同じくらい近い
距離の尺度(類似度) : tscore
距離的に近いテキストのみ判定
2007/03/23
English
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
日本語
17
計算コスト削減
流れ (n:テキスト数)
1.
2.
3.
4.
2007/03/23
サンプルテキストを選択 (<<n)
各テキストとサンプルの距離を計算
最も近いm個のサンプルに振分け
同じグループ内でのみ全対全比較
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
18
サンプル選択
サンプル数
正確さ (誤分類のリスク)
多
低コスト
計算コスト
サンプル選択方法
ランダム
k-means
2007/03/23
正確
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
少
サンプル数
19
k-meansによるサンプル選択
k=2
1. サンプル選択(k個)
2. テキスト振分け
3. グループ内で重心計算
•
k個の重心
4. 重心を使って再振分け
•
2007/03/23
繰り返しは１回のみ：計算コストのため
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
20
k-meansのtscore計算
Text1:(106, 335, 455, 567, 1704, 3173, 7421)
Text2:(335, 567, 567, 1704, 4014, 5449, 7421)
tscore = 4/(7+7)
normal
k-means
Text1:(106, 335, 455, 567, 1704, 3173, 7421)
Average1:((567, 0.2), (4014, 0.14), (7421, 0.5), …)
(0.2+0.5)/(7+7)
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
21
HTMLのデータ変換
1. 言語判定
English, SJIS, EUC-JP, UTF-8
2.
3.
4.
5.
2007/03/23
文字コード変換
HTMLタグ削除
形態素解析→名詞抽出
辞書照合
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
22
発表の流れ
概要
関連研究
提案手法
対訳判定
判定数削減
実験・評価
まとめ
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
23
実験概要
計算コストの評価
単純な全対全手法との計算コスト比較
精度と計算時間の評価
サンプル数による計算コストと正解率の変化
クラスタリングによる性能評価
k-means
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
24
実験環境
データ：Fry Corpus [Fry 05]
日英対訳ニュース記事のURLペア一覧
事前にHTMLを意味ID数列に変換
環境
CPU : Xeon 2.4GHz Dual
Memory : 2GB
OS : Linux (Debian)
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
25
計算コストの評価
Execution Time [sec]
Fry Corpus
200～6400ペア
通常の全対全比較
250
n^2
sampling( n 2 )
sampling( n )
200
150
100
50
0
ランダムサンプリング
(Top3)
0
1000
2000
3000
4000
# of pairs
5000
6000
テキスト数が増えるほど時間差大
サンプル数 n の方がコスト削減
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
26
400ペア
ランダムサンプリング
サンプル数増加で
• 誤分類率→増
• 実行時間→少
14
12
10
2.5
miss classification
ratio
execution time
2
8
1.5
6
1
4
0.5
2
0
0
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
# of samples
誤分類率と実行時間のトレードオフ
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
27
execution time [sec]
Fry Corpus
miss classification ratio [%]
精度と計算時間の評価
k-meansの評価
k-means による精度と実行時間の変化
Fry Corpus
1.
ランダムサンプリング (normal)
•
•
2.
3.
2007/03/23
tscore の Top3 に振分け
サンプル数は n
重心を求めて再び振分け (k-means)
誤分類率と判定時間を測定
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
28
k-meansの評価
miss
classification
200 normal
k-means
0.15
4
0.32
51
600
k-means
7
500
# of texts
誤分類減少
→偏り大
21
700
400 normal
calculation
time [sec]
0.54
200 k-means
200 normal
400 k-means
400 normal
1.18
400
300
200
100
0
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
29
発表の流れ
概要
関連研究
提案手法
対訳判定
判定数削減
実験・評価
まとめ
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
30
まとめ
Webからの対訳テキスト抽出
高速な対訳判定手法
対訳判定回数の削減手法
日英対訳コーパスを用いた評価
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
31
今後の課題
軽量なクラスタリング
リンク構造を考慮
実際のWebを対象
対訳の存在が確認されているもの
• ニュース記事
対訳が存在するか分からないもの
• Web Directory
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
32
2007/03/23
W2「大規模Web研究基盤上での自然言語処理・情報検索研究」
33

Download Report