例示操作に基づく半構造データ抽出規則の効率的な学習

DEWS2008 C7-5
例示操作に基づく半構造データ抽出規則の効率的な学習
筒井 淳平†
金田 悠作†
有村 博紀†
† 北海道大学大学院情報科学研究科
〒 060-0814 札幌市北区北 14 条西 9 丁目
E-mail: †{tsutsui,y-kaneta,arim}@ist.hokudai.ac.jp
あらまし 本稿では，半構造データからの情報抽出を考察し，情報抽出規則学習の形式的モデルを導入する．主結果と
して，k 項木パターン抽出規則の族に対して，未知の k 項木パターン抽出規則を，O(m) 個の正例だけから，O(mn) 時
間で正確に学習するアルゴリズムを与える．さらに，学習アルゴリズムを情報抽出ブラウザ TANE 上に実装し，ウェ
ブ上で情報抽出実験を行う．
キーワード
半構造データ，ウェブからの情報抽出，k 項木パターン，XML
Junpei TSUTSUI† , Yusaku KANETA† , and Hiroki ARIMURA†
† Graduate School of Information Science and Technology, Hokkaido University
N14 W9, Sapporo 060-0814, Japan
E-mail: †{tsutsui,y-kaneta,arim}@ist.hokudai.ac.jp
Abstract In this paper, we prenset an efficient learning algorithm that identifies all unknown k-ary tree patterns
in polynomial time using polynomially many positive examples in the query learning framework of Angluin. The
algoirithm uses the techniques of skelton trees and least general generalization and efficient in practice as well as in
theory. We also developed an information extraction browser TANE based on the algorithm and ran experiments
on the Web.
Key words semi-structured data, information extraction, k-ary tree pattern, XML
1. ま え が き
ウェブからの情報抽出（Information Extraction from Web）
の時点までにうけとった最大の例のサイズである．さらに，学
習アルゴリズムを開発中の情報抽出ブラウザ TANE に組み込
み，実際のウェブ上で情報抽出実験を行った．学習によって一
は，インターネット上に散在するウェブページから所望の情報
部の例示情報から残りの情報を推測することで，利用者の与え
を抽出する技術である．
る情報が少なくてすむと期待できる．
本稿では，半構造データに対する情報抽出規則の例からの学
一般に，自由なタグ付けを許す木パターンのクラスに対して
習を考察する．特に，頂点の k 項組を抽出する k 項木パターン
は，能動的にプログラムが発する所属性質問を使わず，受動的
を用いた抽出規則の学習にとりくむ．従来の XPath [19] をター
に利用者から与えられる例だけから，未知パターンを学習する
ゲットとした情報抽出は単項抽出規則に限られていたが，近年，
ことはきわめて難しいことが，著者らを含む計算学習理論分野
XQuery 等 [21] の明示的な変数と，制御構造をもち，構造出力
の研究からわかってきた [3], [5], [15], [16]．実際に，パターン
が可能な半構造データ問合せ言語の発展を背景として，この種
照合だけで出力を行わないブール問合せの場合でさえ，例だけ
の多項抽出規則が最近注目を集めている．
からの学習は非常に難しい．そこで，本稿では情報抽出の自然
初めに，k 項抽出規則のクラスに対して，Angluin [4] の質問
なプロトコルを利用して，パターン照合情報の一部を抽出対象
学習モデルを拡張して，情報抽出規則学習の形式的モデルを導
の k 頂点組として利用者が教えることで，問題がむしろ易しく
入する．次に，k 項木パターン抽出規則のクラス Tk を導入す
なることを明らかにしている．
る．k 項木パターン抽出規則は，高々k 個の葉をもつ順序木で，
本稿の構成は次のとおりである．2 節で学習モデルに関する
すべての葉が抽出対象のマーカーをもつ．本稿の主結果として，
準備を行い，3 節で k 項木パターンのクラスを導入する．4 節
クラス Tk に対して，未知の k 項木パターン抽出規則 P ∈ Tk
で正例から k 項木パターン抽出規則を学習する多項式時間学習
を，O(m) 個の正例だけから，O(mn) 時間で正確に学習するア
アルゴリズムを与え，その学習可能性を調べる．5 節で情報抽
ルゴリズムを与える．ここに m は P の頂点数であり，n はそ
出ブラウザ TANE への組み込みについて述べ，6 節でまとめる．
—1—
Pattern tree P
Data tree T
/HTML[1]/ … / DIV[
A ∆ B = (A \ B) ∪ (B \ A) で表す．
2. 1 木構造データと抽出規則
2. 1. 1 ラベル付き順序木
x
2
]
z2
本稿では，半構造データの形式的なモデルとして，ラベル付
6
き順序木 [2] を用いる．L = {`, `0 , `1 , . . .} をラベルの有限集合
/TABLE[1]
z1
き集合（部分集合の全体）を表す．集合 A と B の対称差を，
1
3
z3
4
5
8
7
12
10
9
11
とし，dom を頂点の可算集合とする．各ラベルは，HTML や
XML のタグ名に対応する．以後，L は固定されているものとし
て省略する．順序木は子供の集合に順序が付けられた木である．
図 1 k 項木パターンとデータ木．ここでは k = 3 の場合の例．根と，
葉，分岐頂点以外は省略している．
形式的には，L 上のラベル付き順序木（または順序木）を次の
5 項組 T = (V, E, B, lab, root) で定義する．T0 = (V, E, root)
は root を 根と す る 根 付 き 木 で あ る ．V ⊂
=dom は 節 点 集 合を
1. 1 関 連 研 究
半構造データからの情報抽出に関して，Kushmerick [10] は，
ウェブからの情報抽出を例からの抽出ルールの学習問題として
定式化した．文字列を用いたさまざまな抽出規則の族に対して
その学習可能性を明らかにし，情報抽出の研究に大きな影響を
与えた．
木データを対象とした研究として，Sakamoto et al. [13], [14]
は，木構造上の抽出パスパターンの学習を用いた自動抽出アル
ゴリズム TreeWrapper を与えた．木データ上のパターンの学習
問題の計算量については，文献 [5] は可変長ワイルドカードを含
んだ木パターンの等価性質問と所属性質問から多項式時間学習
可能であることを示した．文献 [15] は，XSLT のような再帰呼
び出しをもつ木データの書き換え言語を扱い，非常に単純な部
分族に対しても，例からの学習が計算困難であることと，一方
で，利用者が変換過程に関する「ヒント」を与えることで，例
とヒントから多項式時間学習可能になることを示した．Ito and
Tanaka [8] は，パスパターンの学習を核技術として，彼らの分
散 Intelligent Pad と呼ばれるフレームワークの上でウェブ上
の情報連携技術を提案している．Gottlob ら [6] と Koch [9] は
半構造データ向けの情報抽出のための視覚言語システムを提案
しているが，学習は用いていない．
以上の結果は，本質的に単項抽出規則の学習を扱っており，多
項抽出規則の学習に関する結果はそれほど多くない．Morishima
ら [12] は，本稿と同様の質問学習の枠組みで，木データ変換
問合せ言語である XQuery の部分族の等価性質問と所属性質問
を用いた学習アルゴリズムを与えている．彼らの目標族は，完
全な木構造と，変数の結合を含む制約条件，静的に与えられた
制御構造を含むが，一方で，任意の DFA を学習可能な与えら
れた正負例に加えて所属性質問を用いた強力なアルゴリズムを
用いており，ここで議論している受動的な例，しかも正例のみ
からの効率よい学習とは異なる問題を扱っている．Fujima et
al. [7] は，パスベースの抽出規則を用いた多項質問を議論して
いる．
2. 準
2
表し，E ⊂
=V は有向辺の集合，すなわち，親子関係を表す．
2
lab : V → L はラベル関数を表し，二項関係 B ⊂
=V は T にお
ける兄弟関係を表す．
文脈から明らかなとき，T における V および E, B, lab, root
を，それぞれ VT および ET , BT , labT , rootT で表す．T のサイ
ズを，節点数 |T | = |V | と定義する．節点 v ∈ V の深さを，根
節点 root から v への経路に含まれる辺の数と定義する．頂点
v を根とする T の部分木（v の子孫すべての集合が定める誘導
部分グラフ）を, T /v で表す．以後，T で L 上のラベル付き順
序木の族を表す．
T を順序木とする．T 上の子孫関係AT を，(v, w) ∈ AT と
なるのは，w が v の子孫であるときと定義する．T 上の文書順
序(document order) <
=doc を，v <
=doc w となるのは，T の前置
順巡回で v が w より早く出現することと定義する．T の従兄
2
弟関係(cousin relation) CT ⊂
=(VT ) を，(v, w) ∈ CT となるの
は，v と w の共通先祖となるある頂点 u が存在して，文書順で
v<
=doc w となるときと定義する．
2. 2 k 項抽出規則
ここで，木構造データに対する抽出規則の一般的な定義を与
える．順序木の頂点全体の領域を dom とおく．データ木D とは
L 上の任意の順序木である．
正整数を k とおく．ラベル付き順序木上の k 項抽出規則 (k-ary
extraction rule) とは，入力として与えられたデータ木 D ∈ T
に対して，その頂点の k 項組の集合 X (D) = { (v1i , . . . , vki ) ∈
VTk | i ∈ N } を返す任意の関数 X : T → P(domk ) である．こ
こで，X (D) を抽出結果集合（または結果集合）と呼び，各 k
項組 (v1 , . . . , vk ) ∈ X (D) を抽出規則 X の抽出結果と呼ぶ．
2. 3 抽出規則の質問学習
本節では，Angluin の質問学習モデル [4] を拡張して，木デー
タからの抽出規則の学習モデルを与える．C と H (C ⊂
=H) を，
それぞれ，学習対象となる抽出規則の族（目標空間）と，仮説
として用いる抽出規則の族（仮説空間）とする．
次の補題から，k 項抽出規則 X を，関数 X : T → domk と考
える代わりに，二項関係 X = { (D, ~v ) ∈ T × domk | ~v ∈ X (D) }
備
N = {0, 1, 2, . . .} で非負整数全体の集合を表す．集合 A に
対して，A∗ でその反射的推移的閉包を表し，P(A) でそのべ
と考えて良いことがわかる．
［補題 1］ X = X∗ であるのは，(∀D ∈ T ) X (D) = X∗ (D) が
成立するとき，かつそのときのみである．
以後，文脈から明らかである限り，関数 X と関係 X を同一
—2—
いう証拠がでるまでは，利用者が X による抽出を行い続ける
ことに対応する．所属性質問は，抽出例を示し，これが実際に
正しいかどうかを利用者に尋ねることになる．実際，多項式時
間予測学習（所属性質問を用いた—）は，多項式時間計算可能
な任意の仮説空間を用いた多項式時間質問学習（所属性質問を
用いた—）と等価であることが知られている [11]．
z2
z1
z3
3. 木パターンに基づく抽出規則の族
3. 1 木パターンの族
L 上の木パターンは，L 上の任意の順序木 T ∈ T である．T
のサイズをその頂点数 |T | = |VT | と定義する．
単純ステップは，` ∈ L ∪ {∗} である．ここに，∗ 6∈ L は，任
意のタグにマッチするワイルドカードである．ステップ上の照
図2
自動抽出における例示の与え方
視する．もし X = X∗ ならば，規則 X と X∗ ∈ H は概念とし
て等価であるという．
例（example）は，組 e = (D, ~v ) ∈ T × domk である．例 e
は，e ∈ X∗ のとき，正例（positive example）であるといい，
e 6∈ X∗ のとき，負例（negative example）であるという．
引数抽出規則 X∗ ∈ C を未知の k 項抽出規則とする．
等価性質問（equivalence query）EQU IV (X ) は，任意の抽
出規則 X ∈ H を受け取り，X∗ = X ならば “yes” を返す．こ
のときには，学習は正しく終了している．それ以外の場合は，
X の任意の反例（counter example）を返す．ここで，反例と
は，X と X∗ の対称差の要素 (D, ~
x) ∈ X∗ ∆ X である．すなわ
ち，X では抽出されるが X∗ では抽出されないか，その逆で，
X∗ では抽出されるが X では抽出されない例をいう．
所属性質問（membership query）M EM B(D, ~v ) は，任意の
例 e = (D, ~v ) を受け取り，もし e ∈ X∗ (すなわち，~v ∈ X∗ (D))
ならば “yes” を返し，そうでないならば “no” を返す．
［例 1］ 図 2 に自動抽出における例示の与え方を示している．
学習アルゴリズム（learning algorithm）は，未知の抽出規
則 X∗ ∈ C に対して，等価性質問または所属性質問を行い，最
終的に抽出規則 X ∈ H を出力して停止するアルゴリズム A で
ある．族 C が A によって，仮説空間 H を用いて多項式時間厳
密学習可能（polynomial time exact learnable） [4] であると
は，任意の未知規則 X∗ に対して，A が任意の時点 t で，未知
仮説のサイズ m = ||X∗ || とそれまでに受け取った例のサイズ
の総和 n = |e1 | + . . . + |et | の多項式時間で動き，A が停止し
たとき，X ≡ X∗ が成立することをいう．
上記の定義で，A が学習において等価性質問のみを用いる場
合に，族 C が例から多項式時間学習可能であるという．A の
学習において等価性質問のみを用いて，さらに与えられる反例
が常に正例であることが保障される場合に，族 C が正例から
多項式時間学習可能（polynomial time exact learnable from
positive examples）であるという．
質問学習は，オンライン学習 [11] と密接な関係があることが
合関係 ¹ を，任意のラベル ` ∈ L に対して，` ¹ ` かつ ` ¹ ∗,
∗ ¹ ∗ が成立する二項関係と定義する．
木パターン T からデータ木 D へのマッチング関数は，以下
の条件を満たす関数 ϕ : VT → VD である：
•
(i) ϕ は単射である．
•
(ii) ϕ は子孫関係を保存する，すなわち，
∀(v, w) [ (v, w) ∈ ET ⇒ (ϕ(v), ϕ(w)) ∈ ED ].
•
(iii)ϕ は兄弟関係を保存する，すなわち，
∀(v, w) [ (v, w) ∈ BT ⇒ (ϕ(v), ϕ(w)) ∈ BD ].
•
(iv)ϕ はラベルの照合を保存する，すなわち，
∀v [ labT (v) ¹ labD (ϕ(v)) ].
•
(v) ϕ は根を保存する，すなわち，
ϕ(rootT ) = rootD である．
T から D へのマッチング関数の全体を M(T, D) で表す．パ
ターン T とデータ木 D に対して，T から D へのマッチング
関数 ϕ が存在するとき，T が D に (ϕ で) 出現すると定義し，
T ¹ D と書く．
3. 2 k 項木パターンが定める抽出規則
本節では，k 項抽出規則の有用な部分族として，k 項木パ
ターンの族を導入する．正整数 k >
= 0 に対して，k 項順序木
パターン（k-ary tree pattern）は，組 P = (T, ~
x) である．こ
こに，T ∈ T は，ちょうど k 個の葉をもつ木パターンである．
~
x = (x1 , . . . , xk ) ∈ VTk は T の葉の k 項組であり，P の抽出頂
点ベクトルと呼ぶ．~
x の葉は左から右に並んでいると仮定する．
Tk で k 項木パターンの族を表す．
k 項木パターン P = (S, ~x), Q = (T, ~
y ) に対して，照合関係
¹ を次のように定義する：P ¹ Q であるのは，ϕ(~x) = ~
y を満
たすある照合写像 M(S, T ) が存在することと同値である．
データ木 D ∈ T に対して，k 項木パターン P = (T, ~
x) によ
る抽出結果集合XP (D)⊂
=VD を，D の頂点の k 項組の集合
XP (D) = { ϕ(~
x) ∈ VDk | ϕ ∈ M(T, D) }
と定義する．ここに，ϕ ∈ M(T, D) は T を D に照合するパ
ターン照合関数であり，ϕ(~
x) = (ϕ(x1 ), . . . , ϕ(xk )) ∈ XP (D)
は ϕ による抽出頂点ベクトル ~
x の像である．
わかっている．等価性質問は，現在の仮説 X が間違っていると
—3—
手続き LearnTreeRule:
手続き FindSkeltonTree:
入力: 未知の k 引数抽出規則 X∗ に対する等価性質問オラクル.
入力: (D = (VD , ED , labD , rootD ), ~
v = (v1 , . . . , vk )).
出力: X∗ と等価な k 引数抽出規則 X∗ .
出力: 骨格木 (S, ~
v ).
1: (T, ~
x) := (⊥, (x1 , . . . , xk );
1: VS := D における ~
v の先祖頂点すべての集合;
2: X := X(T,~
x) ;
2: S := D(VS ), D の VS に関する誘導部分木のコピー;
3: while EQU IV (X ) = no do
3: return (S, ~
v );
4:
反例 (D, ~
x) を受け取る.
5:
if (D, ~v ) ∈ (X∗ − X ) then //(D, ~v ) は正反例
6:
(S, ~v ) := FindSkeltonTree(D, ~v ) で k-骨格木を求める．
7:
(T, ~
x) := GenenralizeSkeltonTree((T, ~
x)(S, ~v )) で仮説
図 4 骨格木の計算
/TD[2]
x
を一般化する．
8:
9:
10:
z1
/HTML[1]/…/TABLE[1]/TR[2]
X := X(T,~x)
z2
z3
else //(D, ~v ) は負反例
何もしない．//ここには到達しない．
z1
/HTML[1]/…/TABLE[1]/TR[4]
11: end while
/TD[2]
x
12: return (T, ~
x);
z3
図 3 学習アルゴリズムの概要
図5
4. 学習アルゴリズム
z2
骨格木の例．
化であるとは，Q ¹ Pi (i = 1, 2) が成立することをいう．Q が
4. 1 学習アルゴリズムの概要
P1 と P2 の ¹ に関する最小共通汎化であるとは，P1 と P2 の
図 3 に，提案の学習アルゴリズム LearnTreeRule の概要を示
任意の共通汎化 Q0 ∈ Tk に対して，Q ¹ Q0 が成立することを
す．X∗ を定める未知の木パターン規則を P∗ = (T∗ , ~
x) とおく．
いう．k 項木パターンの集合 S ⊂
=Tk に対して，¹ に関する S の
X∗ = XP∗ である．ここで，⊥ は X⊥ = ∅ となる特別な k 項木
パターンである．
4. 2 骨格木の計算
所属性質問を用いずに学習を達成するための鍵の一つが，与
えられた抽出例からの骨格木の計算である．
データ木 D ∈ T の ~v に関する骨格木は，D の誘導部分木で
あり，条件 ~v ∈ X∗ (M ) を満たし，順序木の包含関係において
極小なものである．
最小汎化を同様に定義することができる．
［補題 6］ 任意の k 項木パターン P, Q ∈ Tk に対して，もし
P ¹ Q ならば，XP ⊃
=XQ である．
［補題 7］ Pi = (Ti , ~vi ) ∈ Tk (i = 1, 2) に対して，Q = P1 ⊕P2
は，¹ に関する P1 と P2 の最小共通汎化である．
4. 4 アルゴリズムの正当性と計算量
二項演算 ⊕ は，可換性と結合性を満たす．上の補題 7 を用い
て，⊕S は，¹ に関する S の最小共通汎化であることが示せる．
［補題 2］ S を ~v に関する D の骨格木とする．このとき，S は
［定理 8］ E = { Ei = (Di , ~vi ) | i = 1, . . . , n } を例集合とす
T∗ と同じ頂点数をもつ．さらに，f (T ) = S かつ f (~
x) = ~v と
る．スケルトンの集合 S = { Skelton(Di , ~vi ) | i = 1, . . . , n } に
なる同形写像 f : VT → VS が一意に存在する．
対して，その最小汎化を P∗ = ⊕P ∈S P と仮定する．ここで，k
もし f (T1 ) = T2 かつ f (~v1 ) = ~v2 となる同形写像 f : VT1 →
VT2 が存在するならば，(T1 , ~v1 ) ≡ (T2 , ~v2 ) と書く．
［補題 3］ 任意の ~v ∈ X∗ (D) に対して，~v に関する D の骨格
木は一意に定まる．これを Skelton(D, ~v ) と書く．
［補題 4］ 図 4 の 手 続 き FindSkeltonTree は ，骨 格 木
Skelton(D, ~v ) を O(|S|) 時間で見つける．
［例 2］ 図 5 に，骨格木の例を示す．これらの木は，図 2 の例
で，HTML ページから演示によって与えた例に本節の手続き
を適用して得たものである．注意として，この図では根および，
葉，分岐頂点のみを示し，他の頂点は省略している．
4. 3 木パターンの一般化
手続き GenenralizeSkeltonTree((T1 , ~v1 ), (T2 , ~v2 )) が計算する
k 項木パターンを (T1 , ~v1 ) ⊕ (T2 , ~v2 ) で表す．
［補題 5］ もし (T1 , ~v1 ) ≡ (T2 , ~v2 ) ならば，i = 1, 2 に対して
(T1 , ~v1 ) ⊕ (T2 , ~v2 ) ≡ (Ti , ~vi ) である．
二つの k 項木パターン Pi = (Ti , ~vi ) ∈ Tk (i = 1, 2) に対し
て，k 項木パターン Q ∈ Tk が P1 と P2 の ¹ に関する共通汎
k
変数木パターンの族を考えたとき，XP∗ ⊂
=T × dom は E を部
分集合として含む，集合の包含関係で最小な k 項木パターン抽
出規則である．
図 3 の学習アルゴリズム LearnTreeRule の正当性と計算時間
を考察しよう．
ここで，３行目から１１行目の WHILE ループの実行回数に
関する帰納法を用いて，現在の仮説 P = (T, ~
x) に対して，次
のことを示すことができる：
•
(i) XP は未知仮説 X∗ の部分集合である．これは，仮説
の更新が最小汎化によって行われることによる．
•
(ii) したがって，３行目の反例 (D, ~x) は常に正反例で
ある．
•
(iii) 正反例 E = (D, ~x) は，現在の仮説が定義する抽出規
則 XP に含まれない．よって，６行目と７行目で，E = (D, ~
x)
をと P = (T, ~
x) の共通汎化を求めると，得られた木パターン
P 0 = (T 0 , ~x0 ) は以前の仮説 P = (T, ~x) よりも ¹ に関して 真に
一般的である．
—4—
手続き GenenralizeSkeltonTree:
z1
/HTML[1]/…/TABLE[1]/TR[2]
/TD[2]
入力: (T, ~
x), (S, ~v ).
x
出力: (U, ~
z ).
仮定: ハッシュ関数 φ : dom×dom → dom.
z3
1: f (T ) = S かつ f (~
x) = ~v となる同形写像 f : VT → VS を求
z1
/HTML[1]/…/TABLE[1]/TR[4]
める．
/TD[2]
2: foreach v ∈ VT do
3:
新しい頂点 w := φ(v, f (v)) を生成する;
4:
VU := VU ∪ {w};
5:
lab(w) := v ⊕ f (v);
z2
x
z2
z3
6: endfor
7: foreach (v, w) ∈ ET do
8:
EU := EU ∪ {(φ(v, f (v)), φ(w, f (w)))};
/HTML[1]/…/TABLE[1]/TR[
z1
]
/TD[2]
9: endfor
x
z2
10: (z1 , . . . , zk ) := (φ(x1 , v1 ), . . . , φ(xk , vk ));
z3
11: return (U, ~
z = (z1 , . . . , zk ));
図 6 木パターンの最小汎化
•
•
図7
最小共通汎化によるパターンの生成
(iv) P 0 のサイズは P よりも一つ以上小さい．
terns) は DNF に対して，予測可能性保存 (PPC) 還元で多項式
(v) また，仮説 P のサイズは常に非負である．
時間予測困難であることが知られている．~v に出現しない葉頂
初期仮説，⊥ は X⊥ = ∅ となる特別な最小の k 項木パターン
点を許すとき，容易に正則パターンの評価問題を，Tk0 の順序木
なので，上記の (i) はみたされる．帰納法の仮定が成立するな
パターンの評価問題に PPC 還元できるので定理が示せる． 2
らば，骨格木と最小汎化の性質から，上記の (i)–(iv) が満たさ
選言標準形論理式 (DNF) の正負例からの多項式時間予測可
れる．最終的に (v) より，アルゴリズムが高々未知仮説のサイ
能性は，計算学習理論分野のよく知られた未解決問題である．
ズ N = |T∗ | 回の WHILE ループの実行で停止することがわか
また，多項式時間質問学習可能性は多項式時間予測可能性を意
る．各ループでは，反例と仮説のサイズの和程度の時間しか要
味するので，すべての葉頂点の情報を利用できない場合は学習
しないので，次の主定理が示せる．
がかなり難しくなることがわかる．
［定理 9］ k 項木パターンの族 Tk と 1-1 照合関数の族に対し
では，所属性質問を用いることでどこまで学習可能だろうか？
て，図 3 の学習アルゴリズム LearnTreeRule は，未知の k 項木
0 項木パターンは，木データへのブール問合せに対応する（注 1）．
パターン T∗ を O(m) 回の等価性質問を用いて，m と n の多項
この学習問題は，[5] でパス変数を含まない場合に対応する．そ
式時間で同定する．ここに，m = |T∗ | は未知仮説のサイズで
こで，[5] の技法により所属性質問を用いてスケルトンを求める
あり，n は現時点で受け取った例の最大サイズである．さらに，
ことができ，補題 5 を用いてステップの学習を扱うことで，次
アルゴリズムは，正反例しか受け取らずに学習を行う．
が示せる．
系として，上記のアルゴリズムをオンライン予測学習に用い
［定理 11］ 0 項順序木パターン抽出規則の族 T0 は，1-1 照合
たときには，過剰一般化をせず，正例だけから未知仮説を正し
関数の族に関して，等価性質問と所属性質問から多項式時間質
く同定することが保障される．この場合，[11] より質問数の上
問学習可能である．
限は誤予測数の上限になる．
4. 5 学習の困難性
定理 9 では，族 Tk を所属性質問を使わず，正例だけから効
率よい学習を行った．では，このアプローチはどの程度一般化
できるだろうか？
k 項木パターン抽出規則 (T, ~v ) ∈ T × domk の族において，
4. 6 抽出結果の出力
学習した k 項木パターン P = (T, ~v ) を用いた抽出は次のよ
うに行う．最も直接的な方法は，解集合 XP (D) に含まれる頂
点の k 項組を順に出力することである．
もう一つの方法は，問合せ言語 XQuery [21] のように P に適
当な制御構造を別に与えて，XP (D) の頂点組を構造的に出力
抽出頂点ベクトル ~v に出現しない葉頂点を限りなく許すような
することである．根および，葉，分岐頂点を実頂点と呼び，ほ
拡張された族 Tk0 を部分 k 項木パターン抽出規則の族と呼ぼう．
かを仮想頂点と呼ぶ．
このとき，族
Tk0
の順序木パターンの学習に関して次の定理が
示せる．
（ 1 ） P から，実頂点のみを残し，仮想頂点は省略して，根
付き木を作る．省略した頂点（すべて鎖頂点）のラベルは，連
［定理 10］ 部分 k 項順序木パターン抽出規則の族 Tk0 の 1-1 照
合関数の族に関する正負例から多項式時間予測は，DNF の正
結してラベルの文字列として，実頂点間の辺に関連付ける．
（ 2 ） P に対応するプログラム [[P ]] を次のように構成する．
負例からの多項式時間予測と同程度に困難である．
（注 1）：0 項木パターン (T, ()) に対して，解集合 XP (D) は，T が D に出現
[証明]
正則文字列パターン (regular patterns/VLDC pat-
すれば true = {()} であり，それ以外なら false = ∅ であるので，ブール値を
返す問合せとみなせる．
—5—
(2.a) P が葉のとき：頂点 y がもつテキストを y.text で表す．
z1
手続き [[P ]](x : node):
z2
x
1: foreach y in x/α do
2:
print y.text
z3
3: endfor
z1
(2.b) それ以外のとき：P の根のラベル文字列を α で，直下
z2
x
の部分木が Q1 , . . . , Qm とする．
z3
手続き [[P ]](x : node):
1: print <tag y>
2: foreach y in x/α do
3:
call [[Q1 ]](y);
4:
···
5:
call [[Qm ]](y);
図 8 自動抽出における抽出結果の出力
5. 2 TANE のスクリプト言語
本節では，ウェブからの情報抽出のための簡単な記述言語
6: endfor
7: print </tag y>
TANE スクリプトを与える．TANE スクリプトは，ウェブ上の
サイトを訪問し，抽出を行う情報抽出アルゴリズムの動作を記
上記の出力方法は完全な木照合を実現しているわけではない
ため，一部の抽出頂点が照合しない場合に，その部分が欠けた
出力が得られることがある （注 2）．そこで実装では，木パターン
照合を実現するように解チェックを入れている．
5. 実
装
著者らが開発している情報抽出ブラウザ TANE [17], [18] に，
前節の k 項木パターンに基づく情報抽出規則の学習を実装し，
情報抽出実験を行った．
5. 1 情報抽出ブラウザ TANE の概要
TANE はウェブブラウザの機能を拡張したソフトウェアであ
る．通常のウェブブラウザと同様に，TANE の利用者は，アド
レス窓による明示的な URL の指定や，表示されたウェブペー
ジ上のリンクからのジャンプ，GoBack ボタンや GoForward ボ
タンの利用などを用いて，自由にウェブページを訪問・閲覧す
ることができる．さらに，マウスポインタの右クリックを用い
た指定で HTML 要素を複数箇所選択し，それらの HTML テ
キストを抽出できる．
TANE は，特殊な機能として，上記の手作業によるウェブ
ページ巡回と HTML テキスト抽出の演示を，TANE スクリプ
トと呼ぶ簡単なプログラムとして記録する自動記録機能と，そ
れを再現する自動抽出機能を持つ．これだけでは，一度利用者
が行った作業をそのまま再現することしかできない．
そこで，TANE では例からの学習を用いて，演示記録から一
般的な抽出スクリプトを生成する機能を持つ．利用者が行った
複数の抽出作業の記録から，一般的な作業を行う TANE スクリ
プトを生成する学習が可能である．
述する簡単な言語である．
TANE 命令は，次のいずれかである．
•
ページ直接移動命令：hGoPage, urli および, hGoBacki,
hGoForwardi. それぞれ順に，url への移動および，直前に訪問
したページへのジャンプ，直後のページへのジャンプを行う．
•
リンク移動命令 hFollow, αi. 現在のサイトにおいて，根
から単純パス α による照合で到達可能な頂点を訪問し，それが
指すリンク先へ移動する．
•
要素選択命令 hSelect, βi. 現在のサイトに k-引数木パ
ターン β = (T, ~v ) を適用し，得られた抽出結果集合 XP (D) に
含まれる HTML 要素のすべての組を抽出する．
TANE スクリプトは，ページ直接移動命令で始まる TANE
命令の長さ有限列 S = (cmd1 , . . . , cmdm ) である（図 9），各
cmd は時点 1 <
=i<
= n で実行する TANE 命令である．スクリ
プトは各時点 i = 1, . . . , m にしたがって，命令 cmdi が先頭か
ら順に実行される．もしパターン照合を含む非決定的な命令に
出会ったら，TANE は照合結果のすべての頂点に対して，非決
定的に計算を分岐し，時点 i + 1 以降の計算を継続する．
5. 3 TANE の学習機構と抽出機構
ウェブ上のサイトの訪問と実際の抽出は，TANE スクリプト
として自動記録される．この演示記録から，出発サイトから始ま
り，直線的にページ移動とリンク選択を繰り返し，最終的に情報
抽出を行う目的サイトに到達して，選択を行う同じ長さ n >
=0
<
の複数のスクリプト S k = (Cmdk1 , . . . , Cmdkn ) (1 <
k
= = m)
が切り出される．
ス ク リ プ ト は ，各 時 点 1 <
= n 毎 に ，一 般 化 演 算
= i <
k
Ti = ⊕k Cmdi を行われて一般度の高いスクリプトに変換
される．このとき，ページ移動命令は単にコピーされる．リン
ク移動命令は引数の単純パスを一般化する．選択命令は，4. 節
の学習アルゴリズムを用いて，引数の k 引数木パターンを順序
¹ で一般化して得られたパターンを新たな引数に用いる．
（注 2）：XQuery においても照合条件を入れないと同じ問題がおきる．
最後に学習で得られた一般化スクリプトを用いて，出発サイ
—6—
1
2
3
4
GoPage
Follow
Follow
Select
:
:
:
:
http://www.google.co.jp/sarch?q=dblp
/HTML[1]/BODY[1]/DIV[5]/H2[1]/A[1]
/HTML[1]/BODY[1]/P[6]/A[2]
/HTML[1]/BODY[1]/P[1]/TABLE[1]/TBODY[1]/TR[2]
/TD[1]
/TD[2]
/TD[3]
4 GoBack
5 Follow : /HTML[1]/BODY[1]/P[4]/A[4]/
6 Select : /HTML[1]/BODY[1]/P[1]/TABLE[1]/TBODY[1]/TR[4]
/TD[1]
/TD[2]
/TD[3]
図 9 TANE スクリプトの例
トから初めて，目的ページを探索し，構築した k 引数木パター
ンを用いて，頂点の k 項組の抽出を行う．
5. 4 実
験
実装した TANE を用いて，図 2 に示したウェブページ上で
の情報抽出作業の例示をもとに，自動抽出実験を行った．ま
ず例示から，図 9 の TANE スクリプトを得た．次に図 5 では，
TANE スクリプトから複数の例を取り出して骨格木を得た．図
7 では，これらの骨格木を最小共通汎化で一般化して k 引数木
パターンを構築し，最終的に図 8 で抽出結果を出力した．
6. お わ り に
本稿では，k 項木パターンに基づく抽出規則の学習問題を考
察し，正例だけから未知規則を同定する効率よい質問学習アル
ゴリズムを与えた．さらに，学習アルゴリズムを開発中の情報
抽出ブラウザに組み込み，実際のウェブで実験を行った．
本稿では最も単純な場合を考察したが，今後の課題として，
抽出言語のさまざまな拡張と制限について，k 項木パターンの
[8] K. Ito, Y. Tanaka, Web Application Wrapping by Demonstration, Proc. EJC’03, 266-281, 2003.
[9] C. Koch, A Visual Query Language for Complex-Value
Databases CoRR abs/cs/0602006, 2006.
[10] N. Kushmerick, Wrapper induction: Efficiency and expressiveness, Artif. Intell., 118(1-2), 15–68, 2000.
[11] N. Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm, Machine Learning 2(4), 285–318, 1987.
[12] A. Morishima, H. Kitagawa, A. Matsumoto, A Machine
Learning Approach to Rapid Development of XML Mapping Queries, Proc. IEEE ICDE’04, 276-287, 2004.
[13] 村上，坂本，有村，有川, html からのテキストの自動切り出し
アルゴリズムと実装, 情報処理学会論文誌：数理モデル化と応用，
42(SIG 14) (TOM 5), 39-49,2001.
[14] H. Sakamoto, Y. Murakami, H. Arimura, S. Arikawa, Extracting partial structures from html documents, Proc. 14th Int’l FLAIRS Conference, 264-268, AAAI Press, 2001.
[15] H. Sakamoto, H. Arimura, S. Arikawa, Identification of Tree
Translation Rules from Examples, Proc. ICGI 2000, LNCS
1891, 241–255, 2000.
[16] Learning Elementary Formal Systems with Queries, Hiroshi
Sakamoto, Kouichi Hirata, and Hiroki Arimura, Theoretical
Computer Science, 298(1), 21-50, 2003.
[17] 筒井, 金田, 有村, 半構造マイニングを用いた Web からの柔軟
な情報抽出, 第 66 回人工知能基礎問題研究会，人工知能学会,
SIG-FPAI-66, 2007.
[18] 筒井, 伊藤, 有村, リンク情報と構造情報を用いた HTML 群
からのテキスト自動切り出しアルゴリズムの実装, 第 18 回
DEWS2007，2007.
[19] W3C, XML Path Language (XPath) Version 1.0, W3C Rec.,
1999. http://www.w3.org/TR/xpath
[20] W3C, Document Object Model (DOM), DOM Level 3 Core,
2004. http://www.w3.org/DOM/
[21] W3C, XQuery 1.0: An XML Query Language, W3C
Rec. 23, 2007. http://www.w3.org/TR/xquery/
学習可能性を明らかにして，十分な表現力をもち，効率よく学
習できる部分族を同定することが課題である．また，4. 6 節で
は，XQuery 風の出力プログラムを与えたが，出力の制御構造
自体の学習も興味深い課題である．
謝辞
北海道大学の伊藤公人先生，九州工業大学の坂本比呂志先生
には，半構造マイニングとウェブからの情報抽出について有用
な議論をいただきました．ここに，謝意を表します．
文
献
[1] S. Abiteboul, P. Buneman, D. Suciu, Data on the Web,
Morgan Kaufmann, 2000.
[2] Aho, A. V., Hopcroft, J. E., Ullman, J. D., Data Structures
and Algorithms, Addison-Wesley, 1983.
[3] T. R. Amoth, P. Cull, P. Tadepalli, On Exact Learning
of Unordered Tree Patterns, Machine Learning 44(3): 211243, 2001.
[4] D. Angluin, Queries and Concept Learning, Machine Learning 2(4), 319-342, 1987.
[5] H. Arimura, H. Sakamoto, S. Arikawa, Efficient Learning
of Semi-structured Data from Queries, Proc. the 12th Int’l.
Conf. Algorithmic Learning Theory (ALT’01), LNAI2225,
315-331, 2001.
[6] R. Baumgartner, M. Ceresna, G. Gottlob, M. Herzog,
V. Zigo, Web Information Acquisition with Lixto Suite,
ICDE 2003, 747–749, 2003.
[7] J. Fujima, A. Lunzer, K. Hornbak, Y. Tanaka, Clip, connect, clone: combining application elements to build custom
interfaces for information access, Proc. UIST 2004, 175-184,
2004.
—7—