連想構造を用いた情報収集・整理支援

Gathering and Reorganization of Information
Using Associative Structures
前田 晴美、 糀谷 和人、西田 豊明
Harumi Maeda, Kazuto Koujitani and Toyoaki Nishida

奈良先端科学技術大学院大学 情報科学研究科
Graduate School of Information Science, Nara Institute of Science and Technology
In this paper, we present a method to reorganize diverse information obtained from heterogeneous
information sources such as WWW pages.
resentation calledindexing.

The basic idea is the use of a plain information rep-associative structures which enable to link information chunks using associative

We have developed a system called CM-2 which helps users to gather and reorganize

information from existing information sources.

We describe the system's two major facilities; (a)information capture facility which allows users to gather information from heterogeneous information sources and generate CM-2 associative structures and (b) an information integration facility

anwhich helps users to reorganize information from the user's point of view We verify our approachby analyzing results of experiments.

1.

はじめに実験結果を示し、有効性について議論する。 6 節では関連研究と比較する。

世の中には情報が溢れている。特に WWW(WorldWide Web) 上では爆発的な勢いで情報が増加している。インターネット上の情報源から情報を収集するシステムは数多くあるが、収集した情報を個人の視点から整理できるシステムはこれまでにほとんどなかった。
本論文では、 WWW のページのような雑多で構造の不均質な情報源から情報を収集・整理する一つの手法を提案する。基本となるアイディアは構造の異なる情報をゆるやかに関連づけるための連想構造とよぶデータ構造を用いることである。連想構造を用いることにより、生データから情報を抽出し、個人の視点から整2.

連想構造

では情報の基本構成要素をユニットと呼ぶ。
ユ ニッ ト は CM-2 の 外部 の テ キ スト ファ イ ルや イ
メージ ファ イル を 表す 外 部 参照 デー タユ ニッ トと、CM-2 において情報を関連付けるための内部的な対象である概念ユニットに大別される。
これらのユニットは、連想構造によって関連付けられる。連 想構造 は key と呼ぶ いくつ かの ユニット とvalue と 呼 ぶ い く つ か の ユ ニッ ト の 間 に 定 義 さ れ、「key が与えられると value が想起される」というゆるやかな関連を表す。 key と value の間の連想関係は精密に定義されたのではなく、多分に主観的なものであることを許している。これは既存の情報の雑多性、多様性に対応することを狙ったものである。
本論文では CM-2 における連想構造を図 2のように記 述 す る。 図 2(a) は key 「奈 良」 が 与 え ら れ る とvalue 「奈良公園」「大仏」「鹿」が想起されることを示す。図 2(b) は key 「奈良」と「寺」から value 「東CM-2理することが簡単に行える。
我々は，連想構造を用いて情報を収集し，整理する過程を支援するシステム CM-2 を試作した． CM-2 では、 WWW の URL を入力として、個人の視点から情報を切り出し・構造化して提示することができる。
図 1に、 CM-2 に よ る 情 報 収 集・ 整 理 の 概 要 を 示す。図 1の WWW ページ例は、人工知能研究者 2 人のホームページの一部 [1], [2] である。直感的に明らかなように両者のページの情報の構造や表現方法は異なっている。 CM-2 では、これらのページから情報を抽出しての連想構造を生成し、得られた連想構造をヒューリス ティックス を用 いて統 合する。 利用者 が「研 究者」や「プロジェクト」などの視点を入力することにより、研究者毎やプロジェクト毎に情報を整理して提示を行なう。
本論文の以下の構成は次のとおり。 2 節では連想構造について述べる。 3、 4 節では情報収集・整理を支援する CM-2 の 2 つの機構について説明する。 5 節では大寺」 「法 隆寺」 「興 福寺」 が 想 起さ れ るこ と を示す。
連想構造には、特別な形態として、 IS-A 構造、辞書構造を定義することもできる。 IS-A 構造 (図 2(c)) においては、クラス、サブクラスなどを区別することなく、上位概念をクラス、下位概念をインスタンスと呼ぶ。 IS-A 構造は推論に使用される。辞書構造は、利用者の語彙を定義するもので、概念ユニット間の変換辞書として使用される。例えば、図 2(d) の辞書構造がある 場 合、 利 用 者 が 「奈 良 先 端 大」 と 入 力 す る と「NAIST」というユニットに変換が可能である.
1

WWWのページ連想構造

CM-2の出力
研究者毎のリスト

James F.Allenのホームページ

研究者
James F.Allen

写真James F. Allen
・プロジェクト: TRAINS
・大学: University of Rochester,
University of Toronto
・トピック: Reasoning About Plans,
Knowledge Representation andReasoning......

University of Toronto
University of Rochester
James F.Allen, URCS Faculty
MemberJames F.Allenb.1950.PhD.(1979) University ofToronto. Associate Professor...;University of Rochester.

TRAINS

Barbara Hayes-Roth

知的情報統合機構

情報キャプJames F.Allen＆Knolwege
チャ機構

James Allen:s research interests..
These areas of research are combinedin TRAINS project,......

Representaiotn and Reasoning
Reasoning About Plans

Barbara Hayes-Rothのホームページ

・e-mail: hayes-roth@cs.stanford.edu
・プロジェクト: Adaptive Intelligent
systems
・大学: University of Michigan
プロジェクト毎のリスト
プロジェクトBarbara Hayes-RothBarbara Hayes-Roth

E-mail Address:
Barbara Hayes-Roth:hayes-roth@cs.stanford.edu

Adaptive Intelligent Systems
・研究者: Barbara Hayes-Roth, DabidAsh, Lee Brownston, Phillipe
Morignot・e-mail: morignot@ksl.stanford.edu

hayes-roth@cs.stanford.edu

KSL Affiliation/Position:

CABINS
・研究者: Katia sycara

Barbara Hayes-RothSenior Research Scientist.

CAIT

Adaptive Intelligent Systems

Project Leader for
Adaptive Intelligent Systems
Project, ....

・研究者: Barbara Hayes-Roth
TRAINS
・研究者: James F. Allen

図 1: CM-2 による情報収集・整理の概要

(a)

(b)

(c)

(d)

step 1

奈良

奈良& 寺

東大寺

奈良先端大

step 2

奈良公園

東大寺
鹿大仏

法隆寺
興福寺

寺

NAIST

(IS-A)(辞書):Brill's

IS-A

情報キャプチャ機構

情報キャプチャ機構は、既存の雑多で構造の不均質な情報源から情報を取り込み、 CM-2 の連想構造を生成する.
WWW で使用される HTML は作者に情報の構造化を要求しないため、 HTML 文書から利用者にとって有用な情報を抽出する方法は自明ではない。我々は、形態素解析と HTML 構造解析を用いて名詞句主体のユニットと連想構造を生成してから、ドメイン知識を利用して重要なキーワードを抽出する方針とした。図 3に情報キャプチャ機構のアルゴリズムを示す。
step 3 で用いられるドメイン知識は、与えられたユstep 2

IS-AIS-A

図 3: 情報キャプチャ機構のアルゴリズム

URL

解析により HTML ファイル取得後、形態素解析を用いて、名詞句とそれに準じるものを概念ユニットとして抽出する。見出し表現 h1 ... /h1 に囲ま< > < >れる範囲から生成されたユニット「James F.Allen」、「URCS Faculty Member」 を key と し、 段 落 表 現
p ... pで囲まれる範囲から生成されたユニット

ニットの名前に含まれる文字列からクラスを推論する
簡単なヒューリスティックスを中心とする。

<> <>「Ph.D.」 「University of Toronto」 「University ofRochester」を value とする連想構造を生成する.
「James F.Allen」は「James」という英語名の単語

3.1 例
James Allen

HTMLHTML(:juman
Rule Based Tagger[3])HTML

図 2: 連想構造

3.

URLを解析して文書を取得する
形態素解析と構造解析を用いてユニットと連想構造を生成する
step 2.1 形態素解析 日本語、英語に基づく簡単な概念
抽出規則を用いて名詞句とそれに準拠するものを抽出し、ユニットを生成する
step 2.2の構造を解析して連想構造を生成する
step 3 ドメイン知識を用いて構造を生成し、ユニットと連想構造を修正する
step 3.1 ユニットからドメイン知識を用いて構造を抽出・生成する
step 3.2で生成 され たユニッ トか ら構造で連結されないものを削除し、連想構造を修正するのホームページの URL が与えられた場

合どのような処理が行われるのか説明する (図 4)。
2

URL http://www.cs.rochester.edu/u/james/

表 1: 知的情報統合機構の主要ヒューリスティックス

step1
HTML file<h1>James F.Allen, URCS Faculty Member </h1><p>b. 1950. Ph.D. (1979) University of Toronto.
...................; University of Rochester.

同名概念統合同名の概念ユニットを統合する

辞書参照概念統合

辞書構造を参照して概念ユニットを統合する

包含的連想生成ある概念ユニットの名前が他の概念ユ<p>James Allen's research interests.........................
These areas of research are combined in TRAINS Project,

ニットの名前に含まれている時、そのstep2
James F.Allen &URCS Faculty Member
Ph.D.
University of Toronto
University of Rochester

するJames F.Allen &URCS Faculty Member

文脈参照連想統合

people

利用者入力
項目1university(IS-A)
University of Rochester(IS-A)
James F.Allen(IS-A)
James F.Allenプロジェクト

項目2プロジェクト

universityプロジェクト

研究者
peopleproject(辞書)
TRAINS(辞書)
James F.Allen

projectを含むため「people」であると推論し、 IS-A 構造を生成 す る。 「University of Rochester」 「University ofToronto」 は 「university」 と い う 単 語 を 含 む た め「university」で あ る と 推 論 し、 IS-A 構 造 を 生 成 する。
生 成 さ れ た 連 想 構 造 の 中 に は 「URCS FacultyMember」 「Ph.D.」 に 関 連 す る IS-A 構 造 が な い ため、 こ れ ら を 削 除 す る。 ま た 「James F.Allen」 と「URCS Faculty Member」を key とする連想構造からこれらのユニットを削除・修正する。

研究者

研究者

TRAINS

図 4: 情報キャプチャ機構アルゴリズム動作例

4.

key が同じ時、連想構造を統合する

University of Toronto(IS-A)
TRAINS
project

University of Toronto
University of Rochester

ある連想構造と他の連想構造のresearch interests
areas of research
TRAINS

step3
James F.Allen

key として他の概念ユ
value とする連想構造を生成概念ユニットをニットをpeople(IS-A)(IS-A)
James F.Allen
TRAINS

TRAINS & 研究者
James F.Allen

図 5: 知的情報統合機構 (step2) アルゴリズム動作例

知的情報統合機構
る。「研究者」または「people」クラスのインスタンスであるユニットの中から、「TRAINS」と連想構造でつながりがあるユニット「James F.Allen」を value

知的情報統合機構は、与えられた視点から情報の切り出しと構造化を行う。基本的なアルゴリズムは、ヒューリスティックスを用いて CM-2 のユニットと連想構造を統合する step1 と、パス探索を用いて利用者の入力に応じて新しい連想構造を生成して結果を表示する step2 から構成される。

として、連想構造を生成する。このように生成された連想構造をリストとして表示する。
5.

step 1 で用いられるヒューリスティックスの中、主実験と考察
情報キャプチャ機構と知的情報統合機構の統合的な要なものを表 1に述べる。

実験を行なった。
人 工知能 研究者の ホームペー ジ 100URL を入力 して、利用者が項目を入力すると、図 1のような研究者毎リスト、プロジェクト毎リストを自動的に出力した。
生 成 さ れ た ユ ニッ ト は 764 個、 連 想 構 造 は 625個、 IS-A 構 造 は 755 個 で あ る。 情 報 キャ プ チャ のた め に 与 え た 知 識 は、 people、 project、 e-mail、

4.1 例

利用者が図 1のようなプロジェクトリストを出力したいとする。入力項目 1 「プロジェクト」、入力項目 2「研究者」を入力した場合の動作例を示す (図 5参照)。
「プロジェクト」または「project」クラスのインスタンスであるユニットの中から、「TRAINS」を最初の key とする。項目 2 「研究者」を 2 番目の key とす、 department、 laboratory、 topic、 な ど

university3

研究のように収集した情報を個人の視点から統合整理

表 2: 実験結果するところまでは研究が進められていない。

適合率

再現率

people93%85%

people以外のクラス

89%

83%

project

78%

82%

project以外のクラス

65%

69%

本研究は情報抽出の点から見ると、佐藤ら [9] の研究と関連する。この研究においては、あらかじめ抽出したい情報ターゲットを設定し、構造情報や必要な知識を与えて精度をあげるアプローチがとられている。本テスト1

研究では、利用者がドメイン知識がない場合や最初からほしい情報がわからない場合も考慮して、不要キーワードを取り込む可能性があるがどのようなドメインでも汎用的に取り込み可能な段階 (step2) と、ドメイン知識を与えてより有用な情報を取り込む段階 (step3) か

テスト2

正しく生成された連想構造のユニット数
適合率：× 100(%)
生成された連想構造のユニット数ら構成されるアプローチをとった。

正しく生成された連想構造のユニット数
再現率：× 100(%)
生成されるべき連想構造のユニット数77.

本論文では WWW に焦点を当て、既存の雑多で構造の不均質な情報を収集・整理する手法を提案した。基つのクラスに関して 288 個である。
people 毎 に 残 り の ク ラ ス を 統 合 す る テ ス ト 1、本となるアイディアは雑多な情報をゆるやかに関連づけるための連想構造とよぶデータ構造を用いることで毎に残りのクラスを統合するテスト 2 の結果を表 2に示す。
この結果は、形態素解析と HTML 構造解析及び簡単なドメイン知識を用いることにより、特別な自然言語処理を行なわなくても、 HTML 文書からの重要なキーワード抽出と視点変換がほぼ満足できる確度で行えることを示している。
project 毎は people 毎に比べると若干率が悪いが、これはもともとのページが people のページであり、project と他のクラスの間の直接的な連想関係がないためである。
この実験における誤りは以下のように分類される。
 step 2 における名詞句生成失敗によるユニットの 生 成 の 誤 り (例: プ ロ ジェ ク ト で あ る 概 念「How Things Work」は、「How」が副詞であるため名詞句とみなされず、ユニットが生成されなかった) step 3 における HTML 構造解析失敗による連想構造生成の誤り step 3 におけるドメイン知識不足による IS-A構造抽出の誤り
今後の課題を以下に述べる。 (1)step 2 において、
projectある。連想構造を用いることにより、既存の情報源から情報を抽出し、個人の視点から整理することが簡単に行なえる。我々は、連想構 造を用いて情報を収集し、整理する過程を支援するシステム CM-2 を試作した。 CM-2 では、 URL を入力として、個人の視点から情報を切り出し・構造化して提示することができる。 CM-2 の有効性を実験によって確かめた。

参考文献[1] http://www.cs.rochester.edu/u/james/[2] http://www-ksl.stanford.edu/people/bhr/index.html[3] Brill, E.: Some Advance in Transformation-Based Partof Speech Tagging, Proceedings of the Twelefth National
Conference on Arti cial Intelligence (AAAI-94), (1994).
[4] Levy, A. Y., Sagiv, Y. and Srivasava, D.: Towards ecient information gathering agents, Working Notes of theAAAI Spring Symposium on Software Agents , pp.64{70(1994).
[5] Armstrong, R., Freitag, D., Joachims, T. and Mitchell,T.: A learning apprentice for the World Wide Web,
Working Notes of the AAAI Spring Symposium on Information Gathering from Heterogeneous, Distributed Environments , pp.6{12 (1995).

[6] Balabanovi'c, M. and Shoham, Y.: Learning information retrieval agents: Experiments with automated webbrowsing, Working Notes of the AAAI Spring Symposium on Information Gathering from Heterogeneous,
Distributed Environments , pp.13{18 (1995).
[7] Li, W.: Knowledge Gathering and Matching in Heterogeneous Databases, Working Notes of the AAAI Spring
Symposium on Information Gathering from Heterogeneous, Distributed Environments , pp.116{121 (1995).
[8] Iwazume, M., Takeda, H., Nishida,T.: Ontology-basedapproach to information gathering and text categorization, Proceedings of International Symposium on Didital
Libraries, pp.186{193 (1995).
[9] 佐藤円, 佐藤理史, 篠田陽一.: 電子ニュースのダイジェスト自動生 成, 情 報 処 理 学 会 論 文 誌, Vol. 36, No. 10, pp.2371{2379(1995).

名詞 句生成 のた めのヒュー リスティッ クスを 導入 する。 (2) HTML 構 造 解 析 の 精 度 を 向 上 さ せ る。 (3)キャプチャ中に得た知識を IS-A 構造として情報キャプチャ機構に再利用できるしくみをつくる。 (4) 実験量をふやして検証する (クラス、 URL、他ドメインなど)。
6.

おわりに関連研究
本研究の関連研究として、インターネット上の異質な情報からの情報獲得の研究 [4],[5],[6], [7],[8] がある。
また、 WWW に関しては Yahoo をはじめとして、多くのサーチエンジンが広く実用化されている。これらは主に情報収集の手法に焦点があてられているが、本4