193

Technical Papers

論 文

WWW における概念理解のためのナビゲーションプラニング
Navigation Planning to Guide Concept Understanding in the World Wide Web
山田 誠二 ∗1

大澤

Seiji Yamada

Yukio Ohsawa

幸生 ∗2∗ 1 東京工業大学大学院総合理工学研究科知能システム科学専攻

CISS, IGSSE, Tokyo Institute of Technology, Yokohama 226-0026, Japan.

∗ 2 筑波大学大学院経営システム科学専攻

Graduate School of Systems Management, University of Tsukuba, Otsuka, Bunkyo-ku 112-0012, Japan.

19YY 年 MM 月 DD 日 受理
Keywords: planning, concept understanding, the world wide web, information retrieval
SummaryThis paper describes a novel navigation planning method that generates a plan (a sequence of
Web pages) guiding concept understanding in the WWW. It also has the ability to generate operators
during planning from Web pages using keyword extraction methods. When a user wants to understanda concept, it is useful to browse for relevant Web pages in the WWW. However, in general, this task
is very hard because the user does not know where such Web pages are, and has to search for themin the vast WWW search space. Even with a search engine, this consumes the user’s energy. To deal
with this problem, we propose navigation planning to automatically generate a sequence of Web pages
by which a user systematically understand a target concept. First, with a planning framework, weformalize the browsing task in the WWW. Action is deﬁned as the understanding of a Web page, andan operator for a Web page consists of conditional/eﬀect knowledge. Unfortunately it is impossible toprepare operators for all the Web pages. Hence we develop a method to generate an operator from a
Web page by extracting condition/eﬀect terms with keyword extraction techniques. Then the wholeplanning procedure is describes. Finally we fully implement the navigation planning system and makeexperiments by comparing with methods using a search engine and link-tracing (like a Web robot). As
results, we found out navigation planning is a promising approach to assist the concept understanding
in the WWW.

有用なページを何らかの方法により探索する必要が生

1.

は

じ め

に

じる．また，ひとつの Web ページが目標概念を理解するために必要十分な情報を含んでいない場合も多く，その場合複数の有用な Web ページを探索する必要が

WWW の急速な広がりに伴い，インターネットを通ある．さらに，検索して得られた Web ページ中に新たしてアクセスできる情報は急激に増加している．このにユーザが知らない概念が含まれている場合も多々あような状況で，WWW にある有用な Web ページを見り，さらに再帰的に有用な Web ページの探索を繰り返ることにより “ある概念（目標概念と呼ぶ）を理解す

していかなければならない．このような作業は，現状る” という作業が，多くのユーザにより日常的に行わの WWW の技術では多くの時間を必要とするし，まれている．しかし，この作業においてユーザは，目標た試行錯誤を含むためユーザにとって大きな負荷とな概念を理解するために有用な Web ページが WWW 上る．また，この概念理解に有用な Web ページを探す作のどこにあるのかを知らない．よってユーザは，そのNov. 1999

WWW における概念理解のためのナビゲーションプラニング

1125

194
業は，検索エンジンや Web ロボット [Cheong 96] をるようにリンクが明示的に張られていない Web ペー

利用することにより部分的には効率化，自動化できるジも探索することが可能であり，目標概念の理解のたが，結局検索されたページを見てチェックするところはめに適切に制御される．

ユーザがやらねばならず，本質的な解決にはならない．

情 報 収 集 に お け る 学 習 シ ス テ ム と し て ，Shop-

本研究では，概念理解のために有用な Web ページの探索を人工知能におけるプラニングとして捉え，プラBot[Doorenbos 97] がある．ShopBot は，オンライ
ンショッピングの Web ページにおける商品の価格を記

ニングの枠組を適用することによりこの作業全体を自述したテキストのパターンを学習し，最も安い店を人動化することを目的とする．ここでプランとは，目標の系列である．このように，目標概念に対し，それを間よりも効率的に見つけることができる．また，WebWatcher[Joachims 97] と Letizia[Lieberman 95] は，ユーザが次に見たいであろう Web ページを予測して，概念を理解するためにユーザが見るべき Web ページ
理解するのに有用な Web ページの系列を生成するプ提示する．ユーザのブラウジングの履歴から，予測の学

ラニングを，ナビゲーションプラニング（navigation

習を行う．ただし，次のページを提示するだけであり，

planning）と呼ぶ．ナビゲーションプラニングでは，一つの Web ページを見て理解することをプラニングにおける一つの行為として捉え，その行為を U-オペレー

ナビゲーションプラニングのように系統立てた Web

タとして定義する．ただし，このような定義では，従ページ系列を生成／提示するわけではない．

2. ナビゲーションプラニング

来のプラニングのように事前に必要な U-オペレータ
をすべて用意しておくことは，世界中のすべての Web本研究でのナビゲーションとは，概念理解を誘導す

ページに対し予め U-オペレータを作っておくことにるためにユーザに有用な Web ページを提示すること対応するため，現実的に不可能である．よって，ナビを意味する．また，その有用な Web ページの系列をプ

ゲーションプラニングは，プラニング過程に必要に応ランとし，そのプランを自動生成することをナビゲー

じて，Web ページから U-オペレータを自動生成する．

ションプラニングと呼ぶ．

WWW における概念理解をプラニングとして扱った
点，プラニング中にオンラインで U-オペレータ生成をb ページをブラウズする手続きは，以下のようにまと行う点において，ナビゲーションプラニングは新規性めることができる．この手続きは，ユーザが停止するを有する．さらに，因果関係を扱うことにより，精度まで繰り返される．

の高い情報検索手法を実現できる．

Softbot[Etzioni 94] は，欲しい情報を集めるために必要なコマンドの系列を自動生成する完全な半順序プ
ラニングシステムである．また，Occam[Kwok 96] も，同様のプラニングをより効率よく行い，異種の情報源を扱えるプラナーである．Sage[Knoblock 95] は，分散した情報源において，プラニング，実行，再プラニ
ング，センシングを統合するために開発されたシステムである．これらの研究の目的は情報収集の手続きをプランとして自動生成することであり，そのプランはUNIX コマンドやデータベースの検索コマンドの系列として表現される．対照的に，ナビゲーションプラニ
ングの目的はユーザの概念理解を誘導するプランの生成であり，そのプランは，目標概念を理解するために

まず，ユーザが目標概念を理解するために有用な We-(1) 検索エンジンを使って，目標概念に関連のある
Web ページを検索する．
(2) 検索された Web ページのうち，役に立ちそうなページを見て理解する．

(3) その Web ページにおいて，未知の概念を目標概念として (1) にいく．
この手続きは，以下のような対応により，プラニン
グ [Fikes 71, Russell 95] として定式化できる．

• 行為（action）：Web ページに記述されている概念を理解する．

• 状態（state）：ユーザの知識状態．既知の概念を表す単語の集合により記述．

• 初期状態（initial state）：ユーザの初期の知識状態．

ユーザが見るべき Web ページの系列で表現される．

• 目標状態（goal state）：ユーザが理解したい目

Web ロボット [Cheong 96] も，検索エンジンの URL
データベース構築のために URL 情報を自動収集する．
しかし，Web ロボットはリンクの張られている Web

標概念．目標概念を表す単語の集合で記述．

ページ間を探索するに過ぎず，また目的に合った制御もされない．ナビゲーションプラニングでは，後述す

1126• オペレータ（operator）：Web ページを見て，知識を獲得するという行為を表す U-オペレータ UOp(URL) は，以下の要素からなる．
◦ ラベル：Web ページの URL でラベル付け.

人工知能学会誌

Vol.14 No.6

195
◦ 条件（condition）：その Web ページを理解するために必要な知識である条件知識 C =語にリンクが張られているわけでもない．よって，<A
HREF=URL> タグにより得られた条件語の絞り込みと，{c1 , · · ·, ci}．c はその要素の知識で条件語とリンクの張られていない条件語の候補抽出を後述する呼ばれる．

KeyGraph により行う．
〔 2 〕 効果語の抽出
Web ページのタイトルは，そのページを読むことに◦ 効果（eﬀect）：その Web ページを理解する
ことにより得られる知識である効果知識 E ={e1 , · · ·, ej }．e はその要素で効果語と呼ばよりユーザが獲得できる知識を表していることが多い．
よって，<TITLE> と</TITLE> の間の単語を効果語の候れる．
条件知識と効果知識は，個々の知識を表す単語の集補とするのは妥当であろう．同様に，見出しも，その合で記述される．以上のような定式化により，プラニ

節を読むことにより学習される知識を記述しているとングの枠組 [Fikes 71, Russell 95] をナビゲーションプ

考えられるため，<Hn> と</Hn> の間の単語も，効果語

ラニングに適用できる．

の候補とする．

ただし，ナビゲーションプラニングには従来のプラ
ニングでは扱われていない重要な問題がある．それは，前述のようにあらかじめ必要な U-オペレータを用意することが不可能なことである．よって，ナビゲーショ

3・2 KeyGraph によるキーワード抽出
U-オペレータの基本となる条件／効果知識を，HTM-

ンプラニングでは，必要になった時に逐次的に U-オペ

L ファイルのタグだけから生成するのは困難である．なぜなら，<A HREF> タグ間のすべての単語がそのページ

レータを自動生成する方法を採る．

の条件語であるとは限らないし，逆にすべての条件語に適切なリンクが張られているとも限らないからであ3.

Web ページからの U-オペレータ生成

る．よってナビゲーションプラニングでは，キーワード抽出法 KeyGraph を併用することによって条件／効Web ページから条件知識と効果知識を自動抽出することにより，U-オペレータを自動生成する方法について述べる．本研究では，条件語と効果語は Web ペー
ジに記述されていると仮定し，Web ページからいかに果知識を得ることにする．

KeyGraph [Osawa 98, 大澤 99] は，文書（本論文では Web ページ）の意味構造をテキストだけの情報から推定して，その構造を基に文書での主張のこめられた

それらを抽出するかを考える．

3・1 タグ構造による抽出
情報検索の分野において，様々なキーワード抽出法が提案されている [Salton 97]．そのほとんどは単語の出現頻度を用いるものであるが，構造化されたテキストの場合，その構造を利用したキーワード抽出が効果的である．Web ページは通常 HTML[Berners 95] という構造化された言語で記述されているので，本研究では条件／効果知識抽出のためにそのタグ構造（<TITLE>,<Hn>, <A HREF=...> ）を利用する．
〔 1 〕 条件語の抽出最初に考えられる条件語の候補は，他の Web ペー
ジにリンクされている単語，つまり<A HREF=URL> と</A> の間の単語である．Web ページの作者によりリンクされている単語は，その Web ページを理解するために重要であることが多い．
しかし残念ながら，リンクの張られた単語がすべて重要なわけではない．例えば，商用の Web ページな入力
• 入力ファイル（HTML ファイル，またはプレーンテキスト）とその URL
制御パラメータ• <TITLE>の重み: α, <Hn>の重み: β, <A HREF=URL>の
重み: γ• 条件語数: NC• 効果語数: NE
出力• U-オペレータ U-Op(URL) = (URL, 条件知識，効果知識)
手続き(1) KeyGraph により, 入力ファイルから条件語の候補の集合 CC と効果知識の候補 CE を抽出．これらの候補は，KeyGraph により決定される重み [0, 1] を持つ．
(2) <TITLE>と </TITLE>の 間の単語を重みを α として，
CE に追加.
(3) <Hn>と </Hn>の間の単語を重みを β として，CE に追加．
(4) CC 中の単語で，<A HREF=URL>と </A>の間に含まれる単語の重みを γ に変更．
(5) CC から重みが上位 NC 個の単語を条件知識として，CE から重みが上位 NE 個の単語を効果知識として取り出して，U-オペレータを生成．

ら，そのスポンサー企業の Web ページにたくさんリンクが張られている場合が多い．また，すべての条件

Nov. 1999

図 1 Ext-OP: U-オペレータ生成手続き

WWW における概念理解のためのナビゲーションプラニング

1127

196
単語をキーワードとして抽出する．KeyGraph の処理の流れは，まず対象文書 D 中で共起（同じ文に出現）精度を上げる効果がある．
ナビゲーションプラニングの停止条件（図 4の手続

することの多い単語の集まりを，文章の主張の基礎とき (2)）として，一般的な後向きプラニングと同様に，なる「土台」の概念とみなす．この土台は通常複数得

副目標が空になる状態を用いる方法が考えられる．しられることになる．その中の単語の集合を条件知識とかしナビゲーションプラニングの場合，この停止条件

する．次に，ここで得られた土台のうち複数の土台のの判定にはユーザの初期の知識状態を完全に記述して中の単語と共起する度合の高い単語を，いくつかの土おく必要があり，これは現実的には困難である．よっ

台を足場にして文章の主張を表わすキーワードと見なて，目標概念からのプランの深さがある制限に達した

す．これらのキーワードを集めて効果知識とする．以らプラニングを停止させるという停止条件を採る．

上で得られる単語は，条件らしさ・効果らしさを表わす実数値の重みと共に得ることができる．

また，状態ノードの評価においては，知識状態と副目標の差異をどの程度満たしているかという従来よく

なお，単語が複数の土台の中の単語と共起する度合など定義の詳細は [大澤 99] に譲る．

使われる評価に加え，副目標と U-オペレータの効果知
識のもつ重みを利用できる．よって，ナビゲーション[大澤 99] の実験で示されたように，KeyGraph により主張を表す単語（本論文の効果知識に当たる）として抽出されるキーワードの約 88%という多数がその文

プラニングでの関数 H は，下式のように定義される．



H=
+

書の主張点を表している．

KeyGraph の処理は高速に行なわれるが，もう一つ



満足された副目標の重み
副目標を満足した効果語の重み

我々は以上の手続きを実装し，ナビゲーションプラニ

の長所はコーパスを用いずに済む点である．これが長所であるというのは，TFIDF[Salton 83] のようにコー
目標状態

パスを用いるキーワード抽出法では通常，コーパスをある分野に限定してシステムに与えなければならない
上，WWW のように多くの Web ページが生成消滅す状態ノード1....

....

状態ノードn状態ノードnる環境ではコーパス情報を絶えず更新しなければならないからである．WWW 上の一般的なサイトの分野を明確に定義するのも，コーパスの膨大な情報を日々正状態ノード1

確に更新するのも実際には困難である．
ナビゲーションプラニングでは，条件知識と効果知

ビーム幅 b

識を KeyGraph とタグ情報の組み合わせによって抽出する．U-オペレータを生成するアルゴリズム Ext-OP

図2

後向きビーム探索の全体は，図 1のようになる．KeyGraph の併用により，タグ構造のないプレーンテキストの Web ページか状態ノード i の副目標
質問らも条件／効果知識の抽出が可能である．

検索エンジン

4.

プラニング手続き

関連Webページ

ナビゲーションプラニングのプラニング手続きにつ

ページ 1

....

ページ w

いて述べる．探索としては，目標状態から後向きのビー
ム探索 [Russell 95] を行う（図 2）．状態ノードの展開（図 3）では，検索エンジンを使った関連 Web ページ

Ext-OPによる
オペレータの生成の検索と，先の手続き Ext-OP を用いた U-オペレー
オペレータ 1

タ生成が行われる．

. . . オペレータ w

ナビゲーションプラニングの手続きを図 4に示す．付
加的な入力として，文脈語を用いている．文脈語は目

次の深さの状態ノード展開

標概念が属する領域を表し，同じ単語でも使われる領
域により意味が異なる場合に付加することで，探索の1128

人工知能学会誌

図 3 状態ノード i の展開

Vol.14 No.6

197
ングシステム N aviP lan を構築した．NaviPlan はの集合 S の 90 ページ全体での和集合を Σ(S) で表してPerl で記述されており，ユーザとのインタフェースとし評価する．ここでは，|Σ(E∪C)| = 825, |Σ(C)| = 494,て Web ブラウザを用いる．図 5に，目標概念が “concept formation”（概念形成）で，文脈語が “AI” の場
合の NaviPlan の出力プラン（深さ制限 l = 4）を示
す．Web ページ 1 は目標概念に直接結びつくものであり，概念形成について ILP （Inductive Logic Programming）を基にして説明されている．しかし，ILP
自体についての説明はページ 1 にはない．ILP については Web ページ 2〜4 のうち 3 で詳しく述べられ，4|Σ(E)| = 331, |Σ(Cr )| = 392, |Σ(Er )| = 243,
|Σ(Cr ∩ C)| = 367, |Σ(Er ∩ E)| = 228 という値を得た．これらの値から |Σ(Cr ∩ C)|/|Σ(C)| = 0.74 ,|Σ(Er ∩ E)|/|Σ(E)| = 0.68 となり，この二つの値がそれぞれ NaviPlan が条件語と効果語を得るときの精には関連する機械学習の論文アブストラクトが紹介さ|Σ(Er )|/|Σ(C ∪ E)| = 0.29 がそれぞれ真の条件語と度を意味する．
一方，Σ(C ∪ E) が得られた 825 語のキーワード
全 体である から，|Σ(Cr )|/|Σ(C ∪ E)| = 0.47 とれている．実際にユーザがこの出力からどのように目標概念を理解したかは 5・2 節で述べる．

4・1 枝刈りとキャッシング
NaviPlan は，図 4の 3cにおけるファイルの取り込みに時間がかかるため，深さ 4 程度のプランの生成にも30 分以上の時間を要する．よって，明かに無駄な状態
ノードの枝刈りと，一度得られた html ファイルを次に使うために保存しておくキャッシングの 2 つの方法により効率化を行っている．
枝刈りについては，URL のポインタや文献のリスト
だけからなるページ，極端に短いか長いページが図 4の 3(d)iiiで削除される．また，キャッシングでは図 4の 3cで一度得られた Web ページを残しておき，次に同じページが必要な時に再利用する．これらの処理により NaviPlan の効率化が可能になる．

5.

NaviPlan の実験による性能評価

5・1 U-オペレータ生成の精度
U-オペレータの精度は NaviPlan の性能に大きく影響する．まず予備実験として，得られる U-オペレータがどの程度条件知識と効果知識を正しく表しているかを評価した．実験方法は以下のとおりである．
まず， ある目標概念について得られたプラン中の１つの Web ページ Doc をとる．C と E をそれぞれ，Doc から NaviPlan により得られた条件知識と効果知識とする．また，Cr と Er をそれぞれ，E ∪ C 中に含まれる Doc の真の条件知識と真の効果知識とする．

C, E, Cr , Er を求める方法としては，まず 90 ペー
ジの Web ページをランダムに選んだ．次に被験者が各ページを読み，読んだ内容を考えて E ∪ C から Erと Cr に含まれると判断できる語の集合を選び，それぞれを Er と Cr とした．
この結果の集計を，一つの Web ページ Doc について
Nov. 1999

入力• 目標状態 （= 目標概念）G0 ：ユーザが理解したい概念を表す単語の集合．
• 文脈語 GC ：目標状態の背景領域を記述する単語の集合．
制御パラメータ• 初期状態 IS ：ユーザの初期の知識状態．
• 深さ制限 l：プランの最大長.
• Web ページの制限数 w：検索エンジンにより得られる関連 Web ページの最大数．
• ビーム探索の幅 b• 状態ノードの評価関数 H
出力• プラン P : U-オペレータ U-Op(URL) の系列．
手続き(1) N0 = [n0 ] = [(G0 , [ ])], i = 0 で初期化．
（Ni は，深さ i での状態ノード系列．状態ノードは，ni = (Gi , Pi )で記述される．ここで，Gi は副目標を表す単語の集合，）
プラン Pi は，U-オペレータ系列．
(2) もし i = l，または，Ni が空なら，プラン P を出力して終了．
(3) 以下の手続きを，Ni のすべてのノード n に対して適用して，Ni+1 = [ ] で初期化．
(a) 差異 D = G ∩ IS を抽出．
(b) 検索エンジンに D ∪ GC を検索語として入力
して，出力された上位 w 個の関連 Web ページのURL を得る．
(c) 得られた URL の http サーバとの TCP/IP 接
続により，その Web ページ（HTML ファイル，またはテキストファイル）を獲得．
(d) 得られた Web ページから，手続き Ext-OP を使って，U-オペレータを生成．そして，効果知識
E と n の副目標との交わりが空でない U-オペレー
タに対して，下の手続きを適用．
i. その U-オペレータの E を n の G から取り除いたものに，U-オペレータの C を追加することにより，G を得る．
ii. n のプラン P の先頭に，その U-オペレー
タを加えることにより，P  を得る．
iii. 新しい状態ノード (G , P  ) を Nn+1 に追加．このとき，枝刈りがされる．
(4) Nn+1 の各状態ノードにつき，評価関数 H による評価を行い，その上位 b 個のノードで，Nn+1 を更新．
(5) i = i + 1 として，(2) へ.

図 4 ナビゲーションプラニング手続き

WWW における概念理解のためのナビゲーションプラニング

1129

198
力して，各自が 2 つのシステムからそれぞれ 10 個のプランを得る∗2 ．本実験では，プラン長を 4 に固定した．また，NaviPlan と MetaCrawler の検索対は，同じものを含んでいない．

• MetaCrawler：検索対を検索語として MetaCrawler に入力する．出力された Web ページのリストから上位 4 ページを MetaCrawler
により得られたプランとする．このようなプランを 10 個得る．ただし，4 ページ未満しか出力されない場合は，その検索対は使わない．

• NaviPlan ：NaviPlan に検索対を入力していき，4 ステップのプランを 10 個得る．ただし，このときすべての検索対について，プランが得られるとは限らない．今回の実験では，プランが得られたのは，被験者の入力した検索
対全体のうち 6 割程度であった．
(2) 被験者は，各自 NaviPlan と MetaCrawler から得られたそれぞれ 10 個のプラン中の Web ペー
ジを上位から順に (NaviPlan の場合は図 4の深さの増す順に) 読んでいき，各プランについて下の

図 5 “Concept formation” のプラン

報告事項 (a)，(b) を筆記して報告する．

(a) 目標概念を理解するまでに読んだ Web
真の効果語の全キーワードに対する比率になる．よっ

ページ数．

て，もし各ページのキーワードを全くランダムに |C|(b) 目標概念をどういう意味に理解したか．

個と |E| 個のキーワードからなる二つの集合に分けてなお，被験者が作業中にページ中のリンクを辿っていたら，その中にはそれぞれ 0.47 と 0.29 だけの割合

他のページに移ることは禁じた．これは，リンクを辿

しか真の条件語と真の効果語が含まれなかったことにるということは検索エンジンの利用とも NaviPlan のなる．したがって上の結果は，われわれの U-オペレー

利用とも異なる別の作業であることを考慮し，その効タにおいて条件知識と効果知識という狙いに沿って分果を除いた両手法の効果だけを比較するためである．

類されたことを示している．

5・2 NaviPlan の性能評価
次に NaviPlan の性能を, 実際のシステム使用結果から評価した．NaviPlan でのノードの展開（図 3，図 4の 3b）における検索エンジンと以下の実験で比較に用いる検索エンジンとして，現在最も広範囲に検索可能な
検索エンジンの一つである MetaCrawler∗1 を用いた．
〔 1 〕 実験方法
われわれは，以下の要領で実験を行なった．人工知能に関連する研究に携わる修士課程から博士課程の学生と大学助手を均等に含む 10 人の被験者各自に次の操作をしてもらった．
脈語の対（検索対と呼ぶ）を考えてもらい，それらを以下のように NaviPlan と MetaCrawler に入1130を混ぜ合わせるタイプの，現時点で最も精度の高い検索エンジンの一つだからである．第二に，NaviPlan の手順は図 4の 3bのとおり，それぞれの深さで読むべき
Web ページの候補を検索エンジンで絞り，さらその中から適切な U-オペレータを持つ Web ページを選ぶ手順からなる．したがって，NaviPlan の性能は検索エンジンの性能とプラニングの効果で決まるものとなるから，NaviPlan と検索エンジンの性能差はプラニングの効果を表している．すなわち，両手法の明瞭な性能差さえ検出されればそれがプラニングの効果となるから，(1) 被験者に，計算機科学の分野から目標概念と文*1

また，MetaCrawler だけを比較対象とすることは，
2 つの理由から妥当であると筆者らは考えている．一
つは，MetaCrawler が各種の検索エンジンの出力結果*2したがって全部で各システムにつき 100 個のプランでの実験となるが，被験者が知らない概念を学習するのは高度で手間のかかるタスクであるから，あまり多くの検索条件
での実験は事実上できないため，妥当なプラン数と考える．

http://www.metacrawler.com/

人工知能学会誌

Vol.14 No.6

検索エンジンとして何を選んでも NaviPlan との間に本実験と同様の性能差が出ると考えられる．
この実験では NaviPlan のパラメータは，図 4の全体の手続きでは IS = [ ]，l = 4，w = 8，b = 4，図1の Ext-OP では α = 2，β = 1，γ = 1，NC = 6,
NE = 4 と設定した．一度のプラニングに要した時間
は，30 分 ∼1 時間であったが，そのほとんどは WWW
サーバとの通信による HTML ファイルの獲得に費された．深さ l が 4 よりも大きいプランを求める実験も行ったが，NaviPlan によりプランがほとんど得られなかったため以下では評価していない．
〔 2 〕 ユーザの理解とその効率の評価

Y:ユーザが理解できた目標概念の数

199
35
30

NaviPlanの
Y値累積

25

MetaCrawler
のY値累積

20

NaviPlanのY値

15

MetaCrawler
のY値

10
5
0

1

3

4

X:ユーザが読んだページ数

まず両手法について，被験者が正しい理解を示した場合の数（= 報告事項 (b) の内容が目標概念の意味を

2

図6

目標概念理解のために読んだページ数の比較．

正しく表している検索対の個数）を比較する．各シス
テムでプランの得られた 100 の検索対について比較した結果，NaviPlan では 32，MetaCrawler では 27 のきることである．これは上記の予想の通りであった．そ検索対について，被験者は正しい理解を示した．よっの結果，NaviPlan を用いる方が Y が X に対してが急て，NaviPlan の性能が，MetaCrawler を上回ってい峻に減少している．図示の通りこの差は顕著であるから，MetaCrawler による検索だけよりも NaviPlan にることがわかった．
しかし，この差はそれほど大きなものではない．実よるプラニングがユーザの効率的な理解を助ける効果

際，両手法にはそれぞれ長所と短所がある．すなわがあると結論づけることができる．

ち，MetaCrawler ではプラニングを行わない代わり〔 3 〕 NaviPlan におけるプラニングの効果に目標概念に直接関係する Web ページを多く出力す

図 6では，NaviPlan によるユーザの効率的な理解がるため，その中には被験者が理解しやすい解説のよう示せた反面，ユーザが複数ページを読み継ぐ例が少なな文書も含まれていることがある．プラニングを行ないのでプランの効果は把握できない．

うことによる NaviPlan の性能の優位は，この MetaCrawler の効果によって縮められたと考えられる．いわば，MetaCrawler が目標概念と関連はするがどういあろうか．MetaCrawler の場合，複数の出力ページ

では，ここで期待される「プランの効果」とは何ではいずれも目標概念と直接関係する．これらは，どのう関係にあるかは不明な Web ページを多数得るのにページも同じ目標概念の理解にユーザを導こうとする

対し，NaviPlan は目標概念と一定の関係にある（目標

並列な役割を果たすことになる．一方，NaviPlan がプ概念を効果語とする）Web ページのつながりを一つランとして出力する複数のページは，各ページが直前得る．

に読んだページの条件語を (効果語として含むことにそう考えると，NaviPlan は目標概念の理解という目より) 説明するように内容が直列につながる．このよ

的に絞り込んだ出力をするのだから，被験者は MetaCrawler よりも少ないページを読むだけで目標概念をうに直列につながった内容のページ集合を出力するの理解できると予想される．そこで，被験者が報告事項うにする狙いがある．したがって NaviPlan の利用は，は，ページを読むごとにユーザの理解が一段深まるよ(b) で正しい意味を報告した検索対の個数 Y とその累

MetaCrawler の並列なページを複数読むのよりも深い積を，報告事項 (a) での理解できたページ数 X につい

理解に到達しようとする作業と言える．

て集計したのが図 6である．

このことから，高度な目標概念（多くの基本的概念

まず，図 6で，NaviPlan により理解できた目標概念を理解しておかなければ理解できない専門用語など）の累積数が，1〜4 ページのすべてにおいてが Meta-を入力するユーザを理解に導くことが NaviPlan のプ

Crawler のそれを上回っている．よって，最初の 1〜
3 ページしか読めない場合でも，NaviPlan の有効性が示されている．また，図 6に見られる特徴として，
NaviPlan により，目標概念を少ないページ数で理解でラニングの効果として期待される．

Nov. 1999

そこで，ユーザが複数ページを読み継いだ少数の例で得られたプランがユーザにどのように働いたかを検討してみる．例えば，図 5では “concept formation” とい

WWW における概念理解のためのナビゲーションプラニング

1131

200
う目標概念を入力した被験者について見てみる．彼は，中の Web ページを読む毎に，目標概念理解に間接的

まず “concept formation” に直接関係する（プランのに役立つ新たな概念の理解が得られるはずであり，各一段目の）ページを読んだが，このページを理解する上ページがユーザの理解を増進させるので追加貢献率はでさらに深く理解する必要を強く感じた単語が “ILP”

大であろう．これに対し MetaCrawler のようなサーであった．この “ILP” は，第二段目（一段目のページ

チエンジンでは，出力ページが先述のように並列な関の条件語を効果語とするページ）の出力ページの U-オ係となり，各ページが直前までに読んだページの内容

ペレータで効果語として含まれており，実際ユーザはに加えて新たにユーザの理解を深めることが少なく追二段目以降のページを読むことによって “ILP” を理解

加貢献率は小となると予想される．よって，プラニン

した．これによって，被験者は，「“concept formation”

グの効果を追加貢献率から評価することができる．

とは概念を発見的に学習することを意味し，計算機が自

実際には，B = 1 の場合は，1 ページでユーザがほぼ動で行う concept formation の手法として機械学習の満足してしまい，その後に読んだページがより深い理

様々な技術がある」と理解した． 一方，MetaCrawler

解に役立ったかどうかユーザが明瞭に区別することがではユーザが”ILP” など機械学習の用語を理解せず，難しくなる．そこで，NaviPlan の出力の 1 ページだけ“concept formation” の理解には至らなかった．
図 6では NaviPlan の複数の出力ページが目標概念の理解に必要となったのは 9 つの入力に対してだけであったが，そのうち 8 つの場合この例のように NaviPlan のユーザが Web ページを読み継いで高度な単語を理解した．上の例の他にも目標概念が “KQML” のとき一段目のページで “KQML” を，二段目で “software agent”

では理解できないがプラン中の複数ページを読むと理0.65 となり，MetaCrawler での平均が 0.15 となったのに比べ大きな値となった．これで NaviPlan のプラなどの基礎概念を説明するプランが得られた．この結ニングの効果が立証できた．

解できた 22 通りの目標概念について，add を評価した．
比較のために，MetaCrawler についても NaviPlan と同じ 22 件について add を求めた．
その結果，追加貢献率 add は NaviPlan での平均が果，“communication” や “protocol” の意味を初期知以上をまとめると NaviPlan は，多くの目標概念を識として知っているユーザは「KQML は言語であり，ユーザに少ないページ数で理解させ，しかも高度な目

インテリジェントソフトウェアエージェント間でコミュ標概念も複数のページを効果的に繋いでユーザに深く

ニケーションをサポートするプロトコルである」と理理解させるツールであるという結論になる．

解することができた．
そこで次に，高度な目標概念を理解する上でのプラ

6. 検

討

課 題

ンの効果を定量的に確かめるために，計算機関連分野の研究者である大学教官が，学生では入力できないと

6・1 U-オペレータの精度思われる高度な目標概念を入力した．その結果，48 通

プラニングの視点から言えば，NaviPlan はプラニン

りの入力のうち 22 通り（全体の 46%で，図 6の 9%よ

グの過程でオペレータ自動生成するところに独創性がり多い）に対し，NaviPlan のプラン中の複数ページをあるが，より質の高いプランを得るためには，さらに読み継いでのみ目標概念が理解された．

が，複数ページを読まねばならないケースについてのU-オペレータの精度を向上する必要がある．この U-オ
ペレータの精度は，U-オペレータで用いたヒューリス
ティックに大きく依存している．例えば NaviPlan では
見出しのタグ<Hn> を利用して効果知識の抽出を行って

NaviPlan と MetaCrawler との優劣は比較できない．

いるが，見出し情報を用いて得られた効果知識が信頼

そこで新たに，ある目標概念に対する出力の追加貢献

できないことは [Osawa 98, 大澤 99] でも指摘されてい率という指標を設けてプランの効果を評価する．

る．このようなタグ構造についてのヒューリスティック

この結果は 1 ページだけよりも複数ページのプランが高度な理解にユーザを導くという効果を示している

追加貢献率とは，add = A/B で定義される指標でを再検討することは，NaviPlan の第一の課題である．

ある．ここで A は，直前までに読んだページで理解で深めるのに役立ったページの数 (理解に役立つページ

6・2 概念獲得という行為の因果律
ユーザの理解は，Web ページの著者にとっての条件が出なければ A = 0) であり，B はその目標概念に対から効果へと進むのかという疑問がある．ロボットのする出力のうち最終的に読んだページの数である．

行動のような物理的操作ではその因果律が明確である

きなかったことが新たに理解でき，目標概念の理解を

NaviPlan のプラニングに効果があるならば，プラン
1132

が，U-オペレータのように「概念獲得」という抽象的

人工知能学会誌

Vol.14 No.6

201
行為では必ずしもそうではない．例えば，行動に関す

ビゲーションプラニングを提案し，その実装システム

Sensing, and Replanning for Information Gathering, In
Proc. of IJCAI-95, pp. 1686–1693 (1995).
[Kwok 96] Kwok, C. T. and Weld, D. S.: Planning toGather Information, In Proc. of AAAI-96, pp. 32–39(1996).
[Lieberman 95] Lieberman, H.: Letizia: An Agent that
Sssists Web Browsing, in Proc. of IJCAI-95, pp. 924–
929 (1995).
[Osawa 98] Ohsawa,Y. et al.: KeyGraph : Automatic Indexing by Co-occurrence Graph Based on Building Construction Metaphor, In Proc. of IEEE Advanced Digital
Library Conference, pp. 12–18 (1998).
[大澤 99] 大澤幸生，Benson, N. E.，谷内田正彦：KeyGraph:
単語共起グラフの分割・統合によるキーワード抽出，電子通信
学会誌論文誌，Vol. J82-D-I, No. 2, pp. 391–400 (1999).
[Russell 95] Russell, S. and Norvig, P.: Artificial Intelligence –A Modern Approach–, Prentice-Hall (1995).
[Salton 97] Salton, G. and Buckley, C.: Term-Weighting
Approaches in Automatic Text Retrieval, in Readings inInformation Retrieval, pp. 323–328, Morgan Kaufmann(1997).
[Salton 83] Salton, G. and McGill, M. J.: Introduction toModern Information Retrieval, McGraw-Hill (1983).

NaviPlan を構築した．このシステムは，WWW 上で〔担当編集委員：××○○，査読者：○○××〕

る推論という方法論をロボット制御に応用する内容のWeb ページがあったとする．これを効果知識（ロボット制御）について日常考えている研究者が読んだ場合，逆に条件知識（行動に関する推論）について学ぶことが十分に考えられる．現在われわれは，条件知識と効果知識を区別しない U-オペレータを検討しているが，ともすればいたずらに探索空間を広げることにもなりかねない．この課題は，遷移前と遷移後の状態を分けない新たなプラニングの構築につながると考えている．

7.

ま

と

め

ユーザが理解したい目標概念を入力として，その概念理解に有用な Web ページを組織的に提示するナのユーザのブラウジングをプラニングの枠組で定式化
し，必要に応じて Web ページから U-オペレータを自

著

者

紹

介

動生成してプラニングを行い，有用な Web ページの系列をプランとして出力する．検索エンジンとの実験的な比較により NaviPlan の有用性を示した．
謝

辞本研究に関して，貴重な意見をいただいた安達淳先
生（学術情報センター) に感謝いたします．また，本研

山田 誠二（正会員）
1984 年大阪大学基礎工学部卒業．1989 年同大学

院博士課程修了．博士（工学）．同年大阪大学基礎
工学部助手．1991 年同大学産業科学研究所講師．
1996 年東京工業大学大学院総合理工学研究科助教
授，現在にいたる．工学博士．人工知能，特に，動的環境への適応，ロボット学習に興味をもつ．情報処理学会，日本ロボット学会，AAAI，IEEE 各
会員．
〈yamada@ymd.dis.titech.ac.jp 〉

究の一部は，人工知能育成財団研究助成金の支援を受けました．記して感謝いたします．最後に，NaviPlan の評価方法について大変有益なご意見をいただいた査読者の方に感謝いたします．

◇ 参

考

文 献 ◇

大澤 幸生（正会員）
1990 年東京大学工学部卒．1995 年同大学院博士課程修了．博士（工学）．大阪大学助手を経て現在筑波大学経営システム科学専攻助教授．AAAI，
IEEE，情報処理学会各会員．人工知能学会において 1994 年・1998 年 全国大会優秀論文賞, 1998年度 人工知能学会論文賞．
〈osawa@gssm.otsuka.tsukuba.ac.jp〉[Berners 95] Berners-Lee, T. and Connolly, D.: Hypertext
Markup Language – 2.0, RFC 1866 (1995).
[Cheong 96] Cheong, F.C.: Internet Agents: Spiders,
Wanderers, Brokers, and Bots , New Riders (1996).
[Doorenbos 97] Doorenbos, R. B., et al.: A Scalable
Comparison-Shopping Agent for the World-Wide Web,In Proc. of the 1st Int. Conf. on Autonomous Agent,
pp. 39–48 (1997).
[Etzioni 94] Etzioni, O. and Weld, D.: A SoftBot-basedInterface to the Internet, Communication of the ACM,
Vol.37 No.7, pp. 72–76 (1994).
[Fikes 71] Fikes, R. E. and Nilsson, N. J., STRIPS: A
New Approach to the Application of Theorem Proving
to Problem Solving, Artificial Intelligence, Vol. 2, pp.
189–208 (1971).
[Joachims 97] Joachims, T., et al.: WebWatcher: A Tour
Guide for the World Wide Web booktitle, In Proc. of
IJCAI-97, pp. 770–775 (1997).
[Knoblock 95] Knoblock, C. A.: Planning, Executing,Nov. 1999

WWW における概念理解のためのナビゲーションプラニング

1133