Comments
Description
Transcript
基本情報技術者試験の正誤解答キーワードへの Wikipediaのリンク構造
福岡工業大学研究論集 Res. Bull. Fukuoka Inst. Tech., Vol.45 No.1（2012）1−8 1 基本情報技術者試験の正誤解答キーワードへの Wikipedia のリンク構造の関連度計算の応用 蔡 菅 （大学院情報工学専攻) 亮 一 海 徐 太（大和コンピューターサービス株式会社) 華（西南学院大学商学部経営学科) 燕（大学院情報工学専攻) Computing Semantic Relatedness between Right Answer and Distracters of Fundamental Information Technology Engineer Examination Based on the Link Structure of Wikipedia Shuai CAI (Graduate School of Computer Science and Engineering) Ryota SUGA (Daiwa Computer Service Co., Ltd.) Yihua SHI (Faculty of Commerce, Seinan Gakuin University) Haiyan XU (Graduate School of Computer Science and Engineering) Abstract With the spread of WWW, Wikipedia,a collaborative Web-based encyclopedia,has been published. In order to make use of the huge data ofWikipedia,we calculate semantic relatedness between right answer and distracters of33 selected questions of Fundamental Information Technology Engineer Examination based on the link structure of Wikipedia. With Wikipedia API and Google API we resolve the nonexistent pages and ambiguous pages problems. We also propose the method to differentiate the semantic relatedness between right answer and distracters in the same category. Calculations are carried out through Wikipedia API and MySQL database. Key words:Semantic relatedness, Wikipedia, Link structure, Relational database. ク構造を持っていることである。Wikipedia の持つリンク １. はじめに WWW の爆発的な普及に伴い，Wikipedia に代表される Web 事典が 開されてきた。Wikipedia は，Wiki を利用し 構造は，近年知識抽出のために研究者から注目を集めてお り，Wikipedia を用いた様々な研究が行われている ［１，３８，13-20］。概念間の関連度の測定において，概念の網羅 性を向上させることができ，自然言語処理における未知語 て構築された百科事典であり，文化，歴 ，科学，社会， の対応，同義語や多義語の判別など，これまでの自然言語 学問，自然，技術，地理などの幅広い 野の概念をカバー 処理手法における課題を意識せずに解析することができ している。Wikipedia では，Web ブラウザを通じて，他の ユーザと議論しながら自由に記事を編集することができる る。 ことが大きな特徴である。Wikipedia の記事数および精度 Wikipedia の 特 徴 を 利 用 し，わ れ わ れ は Wikipedia の データを用語の学習に活用する研究を行っている［９-12］ 。 は， 多くの専門家が集まって作成した百科事典 「Britannica」 ただし，Wikipedia データを e-Learning のための演習問題 と同等であると Nature誌の調査で報告されている［２］ 。 の自動出題に活用する研究を行っている際に，次のような 通常の電子事典の大きな違いは，多言語間のリンク，カテ 課題が浮き彫りになってきた。 ゴリリンク構造，リダイレクトリンクなどによる密なリン 基本情報技術者試験といった国家試験の資格問題にお いて，正解と誤選択肢間の関連度は Wikipedia を用い 平成24年５月７日受付 て計算可能であろうか。言い換えれば，計算可能な割 2 基本情報技術者試験の正誤解答キーワードへの Wikipedia のリンク構造の関連度計算の応用（蔡・菅・ ・徐) 合はどのぐらいであろうか。 は機械処理によって知識抽出を行う対象として注目されて 計算可能な部 に対して，さらに関連度の値はどのぐ いる。Wikipedia から知識抽出する際に有効な特徴を以下 に示す。 らいであろうか。どのような性質があるのか。 これらの課題を明らかにするために，われわれは，過去 １. 質の高いリアンカーテキスト の基本情報技術者試験の資格問題中のアルゴリズム関係と ２. コンテンツの網羅性 データベース関係の資格問題33問の正解と誤選択肢の99組 ３. 密なリンク構造 に対して，Wikipedia のリンク構造に基づく関連度の計算 手法の応用を行なった。９割以上の正解と誤選択肢間の関 ４. 多言語間のリンク 連度の計算ができており，Wikipedia のリンク構造に基づ ６. カテゴリリンク構造 く関連度の計算手法は一つの有効な方法である結果が得ら ７. リダイレクトリンク れている。具体的に，上記の結果は次の二つの問題を解決 2011年６月28日の段階で Wikipedia （日本語版）の記事数 したことによって得られている。 存在しないページ問題：資格問題中の「２ ５. URL による概念の一意性 は約121万記事である。この記事の記事間リンク数は，約 木」と 5454万であることが かっている。これは，１つの記事あ ， 「線形探索法」 と 「線形探索」， Wikipedia 中の「二 木」 「２ 探索法」と「二 探索」 ，「ネットワークモデル」 たり平 44.9のリンク数を持っている。これらのリンクは と「ネットワーク型データモデル」というような両者 サイト外へのリンクは含まれてない。これは，Wikipedia で の記述法の微妙な違いによって検索できないキーワー は閉じられた空間の中で密なリンク構造を持っており，リ ドが存在する。さらに， 「内部スキーマ」 ， 「論理スキー ンク構造を解析することで有用な情報を抽出できる可能性 マ」 ，「外部スキーマ」というようなページ名としては が高いことを示している。 サイト内に対するリンクのみをカウントしたものであり， 存在しないが，セッション名として存在するキーワー ドも存在する。われわれは，Wikipedia API と Google API を用い る こ と で 存 在 し な い ページ に 対 応 す る キーワードを見つけることにしている。 曖昧ページ問題：資格問題中の「LIFO」 ，「木構造」 ， 「キュー」などのキーワードが Wikipedia では多義性 があるため，曖昧さの回避が求められている。われわ れは「計算機科学」カテゴリに所属する候補を選択す ることで多義性のある曖昧ページ問題を解決してい る。 さらに，計算結果から同一カテゴリ内における誤選択肢 と正解間の関連度が同じという問題が存在することも判明 した。そのため，記事のリード部 （冒頭文）を重要文と 見做して解析する LSP 法も取り入れた LSPLch を提案し， 問題の解消を試みる。計算結果より差別化できたことを確 図１ Wikipedia カテゴリ構造の例 認している。 本論文は，次のように構成される。２章では，Wikipedia の特徴と関連研究について述べる。資格問題の正解と誤選 Wikipedia の特徴の１つとして言語間のリンクがある。 Wikipedia は2011年６月現在，日本語，英語，中国語，ドイ 択肢間の関連度の計算を行い，存在しないページや曖昧 ツ語など283言語で展開されている。次に，カテゴリリンク ページ問題の解決方法，解決後の結果と結果についての は，ある記事（概念）がどのようなカテゴリに属するかを 析は３章で報告する。４章は LSP 法を用いて同一カテゴリ 指定するためのリンクである。カテゴリには専用のページ の Lch 計算結果の問題点を解消する試みについて述べる。 （カテゴリページ）があり，カテゴリページはさらに別の ５章は全体のまとめである。 カテゴリページに属することが可能である。Wikipedia の カテゴリ構造は，図１示しているように実際にはネット ２. Wikipedia の特徴と関連研究 ワーク構造となっている。 2.1. Wikipedia リンク構造に基づく関連度計算 また，URL により語彙（概念）の一意性が確立されてい る点は，Wikipedia の大きな特徴の１つである。通常の辞書 では，１つの見出し語に対して複数の意味で詳細が書かれ Wikipedia（ウィキペディア）は，ウィキメディア財団が 運営するインターネット百科事典である。Wikipedia は，閲 覧によって情報を得るという活用以外に，研究者にとって ている。一方，Wikipedia では１つの URL に１つの記事 （概念）が割り当てられているため，多義性が URL によっ 基本情報技術者試験の正誤解答キーワードへの Wikipedia のリンク構造の関連度計算の応用（蔡・菅・ ・徐) て解決されている点が特徴である。一つのキーワードが二 3 つ以上の意味や物に用いられている場合，異なる用法を一 の意味を，Wikipedia の概念を基底とする高次元ベクトル で表す。これは，人間の認識に基づく明らかな概念を用い 覧している曖昧さ回避のためのページが表示され，利用者 ている。 に一番近い記事を選ばせることにしている。一方，リダイ 記事テキストを利用した手法では，言語によっては高度 レクトリンクは，ある記事が参照された際に別の記事へと な自然言語処理が必要であり，特に日本語では形態素解析 リダイレクトする機能を提供するリンクである。例えば， や構文解析などが精度に大きく影響するといった側面を 記 事「ワール ド ワ イ ド ウェブ」を 参 照 し た 場 合，記 事 持っている。また記事テキストの量は膨大であり，解析コ 「WorldWideWeb」へと自動的にリダイレクトされる。 Wikipedia に関する研究は，大きく２つの 野に 類で ストが非常に大きいという問題点がある。 きる。１つは，Wikipedia を社会現象として解明する研究で を利用する方法である。Wikipedia のカテゴリ構造は記事 ある。例えば，Wikipedia に参加する人の目的や行動を調査 （概念）を 類するための階層的構造であるが，カテゴリ し，社会現象として Wikipedia を解析するといった研究で リンクに基づく手法はカテゴリ構造において記事（概念） ある。もう一方の研究 間のパスの長さが短いほど関連度が高くなるという えに 間の関係性などの有用な情報を抽出し，アプリケーション 基づいている。主な研究として，Strubeらの WikiRelate! ［３］が挙げられる。Strubeらは，WordNet に用いられて に適用する研究がこの 野に 類される。Wikipedia を解 析して概念間関連度を測定する先行研究として，大きく きた関連度計算の手法が Wikipedia のカテゴリ構造に適 けると記事間リンクに基づく手法，記事内テキストに基づ ることを示した。WikiRelate!では，カテゴリ構造の解析手 法を２つに 類している。 野は，Wikipedia を言語リソースと して利用や 析をする研究である。例えば，記事（概念） く手法，カテゴリリンクに基づく手法がある。 ３つ目の関連度計算手法は，Wikipedia のカテゴリ構造 用できることを証明し，複数の条件によって精度が向上す Wiki データを利用するには，Wikipedia API による利用 方法と，ダンプされた Wikipedia のファイルをダウンロー ① カテゴリ構造における概念間のパスの長さに基づく手 ドして利用方法の二つの方法がある。本論文では，３章は ② カテゴリ構造における情報の共有度に基づく手法 法 前者の方法，４章は後者の方法というように二つの利用方 評価実験において最も精度が良かった手法であるカテゴ 法とも用いている。なお，４章は2011年６月28日にダンプ リ構造におけるパスの長さに基づいて関連度を測定する手 された Wikipedia 日本語版のファイルをダウンロードし 法 Lch を示す。 て利用している。 Lch 1， 2 ＝−log 2.2. Wikipedia リンク構造に基づく関連度計算 Wikipedia を概念間関連度に利用することは，2.1節にあ げ た よ う な 様々な 特 徴 に よ る 多 く の 利 点 が あ る。Wi- 1， 2 2 (1.1) c1と c2は計算対象の２つの記事（概念）であり，length （c1，c2） は c1と c2間のカテゴリ構造を介した最短経路 （図 ２）の長さであり，D はカテゴリ構造の全体の深さを表す。 kipedia を解析して概念間関連度を測定する先行研究とし て，大きく けると記事間リンクに基づく手法，記事内テ キストに基づく手法， カテゴリリンクに基づく手法がある。 １つ目の関連度計算手法は，リンクの構造を解析して関 連度計算を行うのが記事間リンクの解析手法である。Wikipedia の記事を概念として扱い，リンクは意味的な関係を 表す。Wikipedia 内部で概念同士が密なリンク構造を形成 しているため，リンク構造を解析することで概念間の関係 図２ 最短経路 性を抽出することが可能である。この特徴を生かし，リン クの構造を解析して関連度計算を行うのが記事間リンクに ３. 資格問題の正解と誤選択肢間の関連度計算 基づく解析手法である。 ２つ目の関連度計算手法は，テキスト内容を比較し，そ の類似度を利用する手法である。 テキストを用いた手法は， 本章では，基本情報技術者試験という国家試験の資格問 概念に関する記事内容が充実している場合に有効な手法で 題において，正解と誤選択肢間の関連度を Wikipedia のカ あり，一般にテキストに出現する単語が重複している頻度 テゴリ構造に基づく測定手法 Lch を用いた場合の関連度 が高いほど関連度が高くなるという 計算について述べる。 えに基づく手法であ る。Gabrilovich らの研究［１］では，単語やテキストの意 味を表現するための手法として，Explicit Semantic Analysis を提案している。ESA では，特定の単語またはテキスト 4 基本情報技術者試験の正誤解答キーワードへの Wikipedia のリンク構造の関連度計算の応用（蔡・菅・ ・徐) 3.1. 資格問題の正解と誤選択肢間の関連度計算 一様 布 ２項 布（△） 基本情報技術者試験の午前問題は，正解と３つの誤選択 一様 布 正規 布 肢による四択問題である。コンピュータ科学基礎，コン 一様 布 ポアソン 布 再帰的（再帰） リユーザブル（プロセス） 再帰的（再帰） リロケータブル 再帰的（再帰） リエントラント 前判定繰返し（△） 後判定繰返し（△） 前判定繰返し（△） 双岐選択 前判定繰返し（△） 多岐選択 キーワードに対する関連度計算を行った。アルゴリズム関 木構造（??） キュー（??） 係とデータベース関係のキーワード関係の問題を最大限選 木構造（??） スタック 択するという方針で選択された問題は合計33問である。 「ア 木構造（??） リスト構造 ルゴリズム」関係の主な正誤選択肢ペアを表１，「データ 線形リスト（連結リスト） ２ 木（△） ベース」関係の主な正誤選択肢ペアを表２に示す。 線形リスト（連結リスト） スタック 表１，表２に下線や「△」 ， 「??」 「#」記号で示されたよう に，関連度計算より前に次の問題に直面した。 線形リスト（連結リスト） 配列 配列 連結リスト １) ??」という記号でマークされた多義性のあるキーワー ドが存在することである。 「LIFO」など15個のキー 配列 循環連結リスト（△） 配列 重連結リスト（△） ピュータシステム，システム開発，システム運用，ネット ワーク技術，データベース技術，セキュリティ，標準化， 経営など，幅広い 野から出題される。問題の形式は計算 問題やキーワードに関する問題などがある。 われわれは，基本情報技術者試験の午前問題の過去問中 のキーワードに関する問題中のアルゴリズム関係とデータ ベース関係の問題を選び，資格問題の正解と誤選択肢の ワードがこの種類に属する。 ２) △」という記号でマークされた存在しないキーワード が存在することである。 「２ 木」などの44個のキー 注：下線：redirect された結果 △：存在しない ??：曖昧 ワードがこの種類に属する。 表２ 表１ アルゴリズム」関係の正誤選択肢ペア データベース」の関係の正誤選択肢ペア 正解 誤選択肢 階層モデル（△） 正解 誤選択肢 ２ 探索木 ヒープ E-R モデル（△） E-R モデル（△） ２ 探索木 AVL 木 Ｂ木 ネットワークモデル（△） E-R モデル（△） ボイス・コッド正規形（△） 階層モデル（△） FIFO LIFO（??） ボイス・コッド正規形（△） 関係モデル FIFO LILO LRU（Least Recently Used) ボイス・コッド正規形（△） ネットワークモデル（△） 内部スキーマ（△） 概念スキーマ（△） ２ 内部スキーマ（△） 外部スキーマ（△） スタック 内部スキーマ（△） サブスキーマ（△） キュー（??） ヒープ 射影（#） 結合（??） クイックソート 単純挿入ソート（△） 射影（#） 選択（??） クイックソート 単純選択ソート（△） 射影（#） 和（??） クイックソート 単純 換ソート（△） 結合（??） 射影（#） クイックソート 選択ソート 結合（??） 選択（??） クイックソート 挿入ソート 結合（??） 挿入（△） クイックソート バブルソート ハッシュ法（△） 線形探索法（△） ハッシュ法（△） ２ 探索法（△） ハッシュ法（△） 二 木 ヒープソート クイックソート ヒープソート シェルソート ヒープソート バブルソート ２ 探索木 FIFO キュー（??） キュー（??） 木（△） 関係モデル 注：△：存在しない ??：曖昧 #：注釈あるページ このため，われわれは，まず存在しないページ問題と曖 昧ページ問題の解決に着手することにしている。解決方法 と解決結果をそれぞれ次の二つの節で報告する。 基本情報技術者試験の正誤解答キーワードへの Wikipedia のリンク構造の関連度計算の応用（蔡・菅・ ・徐) 5 3.2. 存在しないページ問題の解決 ・ハッシュ法→コンシステントハッシュ法 GoogleAPI を用いて存在しないページ問題の解決を試 みた。表３と表４では，それぞれ表１と表２において 「△」 ・木構造→木構造（データ構造） 記号でマークされたキーワードの処理結果を示している。 ・結合→関係代数（結合） 存在しないページの一部の処理結果を次に示す。 処理結果を 析すると，資格問題のキーワードに対して， ・２ 木→二 木 ・キュー→キュー（コンピュータ） ・線形探索法→線形探索 Wikipedia に複数の候補が存在する場合は，資格問題の性 質より「計算機科学」という親ディレクトリ内の候補を選 ・２ 探索法→二 探索 ぶ方法で，適切に曖昧問題を処理することができた。 ・リスト構造→連結リスト ・循環連結リスト→連結リスト 表３と表４には存在しないページ問題と曖昧ページ問題 ・E-R モデル→実体関連モデル を処理後のキーワードに対して，Wikipedia API による Lch の計算結果を示している。括弧内は Lch をパーセン ・階層モデル→・階層型モデル テージに換算した結果を示している。なお，カテゴリ構造 ・前判定繰返し→ループ に閉路が存在する場合は，下から最初に出会った親を選択 ・内部スキーマ→スキーマ するという最短経路方法で処理している。 処理結果を 析すると， 資格問題のキーワードに対して， Wikipedia にページ（記事）として存在しない原因が次の二 つに けられる。 正解 誤選択肢 １) 用語の記述方法が異なる場合。上に示した処理結果中 ２ 探索木 ヒープ の最後の二つ以外は全部この種類に属する。「２」か ２ 探索木 ２ 探索木 AVL 木 Ｂ木 1.3424226808222(1) 「二」 ， 「法」や「型」という字を入るかどうかという FIFO スタック 1.3424226808222(1) FIFO LILO 0.74036268949424 (0.55151235156485) FIFO LRU（Least Recently Used） 0.74036268949424 (0.55151235156485) 細かい記述方法の違いがある。 ２) 詳細度が異なる場合。上に示した処理結果中の最後の 二つのキーワード，「前判定繰返し」 ， 「内部スキーマ」 表３ 表１に対する処理結果 は，ページ（記事）としては存在しないが， 「ループ」， 「スキーマ」というページ内のセッションとしては存 在している。すなわち，資格問題中のキーワードは Lch（％) 1.3424226808222(1) 1.3424226808222(1) キュー（コ ン 二 木 ピュータ） 1.3424226808222(1) キュー（コ ン スタック ピュータ） 1.3424226808222(1) キュー（コ ン ヒープ ピュータ） 1.3424226808222(1) クイックソート 挿入ソート 1.3424226808222(1) クイックソート 選択ソート 1.3424226808222(1) クイックソート 換ソート 1.3424226808222(1) テゴリによって判定することで処理している。例えば， クイックソート 選択ソート 1.3424226808222(1) 「LIFO」に対する候補は，次の二つである。 後入先出法：会計における LIFO クイックソート 挿入ソート 1.3424226808222(1) Wikipedia 中のページの名前のみでなく，セッション の名前として表れていることもある。 存在しないキーワード中，処理できなかったキーワード は，表３においては「多岐選択」 「双岐選択」の２つのみで あり，表４においては「挿入」の１つのみである。それぞ れ表３と表４において，太字で表示している。 3.3. 曖昧ページ問題の解決 多義性を持つキーワードに対しては，候補の所属するカ スタック：コンピュータにおける LIFO 前者の候補「後入先出法」の所属するカテゴリは， 「会計」 であり，後者の候補「スタック」の所属するカテゴリは， 「データ構造」 ，「データ型」である。われわれは基本情報 技術者試験という資格問題を対象にしているため，図１に 示しているように「計算機科学」という親カテゴリに属す る候補を選ぶことにした。具体的に，ここでは，後者の「ス タック」が選ばれることになる。 曖昧処理に関する一部の結果を，次に示す。 ・LIFO →スタック ・キュー→キュー（コンピュータ） クイックソート バブルソート 1.3424226808222(1) コンシステント 線型探索 ハッシュ法 1.3424226808222(1) コンシステント 二 探索 ハッシュ法 1.3424226808222(1) コンシステント 二 木 ハッシュ法 1.3424226808222(1) ヒープソート クイックソー 1.3424226808222(1) ト ヒープソート シェルソート 1.3424226808222(1) ヒープソート バブルソート 1.3424226808222(1) 一様 布 二項 布 1.3424226808222(1) 6 基本情報技術者試験の正誤解答キーワードへの Wikipedia のリンク構造の関連度計算の応用（蔡・菅・ ・徐) 一様 布 正規 布 1.3424226808222(1) ネットワーク リレーションの 型データモデ 1.3424226808222(1) 正規化 ル 一様 布 ポアソン 布 1.3424226808222(1) 再帰的（再帰） リユーザブル （プロセス） 0.74036268949424 (0.55151235156485) 再帰的（再帰） リロケータブ ル 1.3424226808222(1) 再帰的（再帰） リエントラン ト スキーマ（内部 スキーマ（外 1.3424226808222(1) スキーマ） 部スキーマ） 1.3424226808222(1) ループ（前判定 ループ（後判 繰返し） 定繰返し） スキーマ（内部 スキーマ（サ 1.3424226808222(1) スキーマ） ブスキーマ） 1.3424226808222(1) ループ（前判定 双岐選択 繰返し） ― ループ（前判定 多岐選択 繰返し） ― 木構造（データ キュー（コン 構造） ピュータ） スキーマ（内部 スキーマ（概 1.3424226808222(1) スキーマ） 念スキーマ） 射影 関係代数（結 0.64345267648619 合） (0.47932196444423) 射影 関係代数（選 0.64345267648619 択） (0.47932196444423) 射影 関係代数 （和) 0.64345267648619 (0.47932196444423) 1.3424226808222(1) 射影 木構造（データ スタック 構造） 関係代数（結 合） 0.64345267648619 (0.47932196444423) 1.3424226808222(1) 木構造（データ 連結リスト 構造） 関係代数（結 合） 関係代数（選 1.3424226808222(1) 択） 1.3424226808222(1) 挿入 線形リスト（連 二 結リスト） 関係代数（結 合） 1.3424226808222(1) 木 ― 線形リスト（連 スタック 結リスト） 1.3424226808222(1) 注：二重下線：曖昧処理，存在しないページ処理，または リダイレクトページ処理された結果 太字：処理できなかったキーワード 線形リスト（連 配列 結リスト） 1.3424226808222(1) 3.4. 結果 析 配列 連結リスト 1.3424226808222(1) 配列 連結リスト （循環連結リ スト） 1.3424226808222(1) 連結リスト （重連結リス ト） 1.3424226808222(1) 配列 パーセンテージ（％） に変換後の結果はほぼ１， つまり100％ らに 析を行うことにした。 １) FIFO と LILO ２) FIFO と LRU 表４ 表２に対する処理結果 誤選択肢 ベース」関係の資格問題の正誤選択肢間の関連度 Lch の ということが かる。100％でない次の各場合について，さ 注：二重下線：曖昧処理，存在しないページ処理，または リダイレクトページ処理された結果 太字：処理できなかったキーワード 正解 表３と表４に示された「アルゴリズム」関係と「データ ３) 再帰的とリユーザブル ４) 射影と結合，選択，和 最初の２つの場合は， 「FIFO」と「LILO」や「LRU」は 意味的の関連度は高くないが，記述上類似していることが かる。すなわち，資格問題では，意味的に近いキーワー Lch（％) ドのみを解答の誤選択肢に出題しているとは限らず，記述 階層型データ 実体関連モデル モデル 1.3424226808222(1) 上類似しているキーワードも出題していることがある。最 実体関連モデル 関係モデル 1.3424226808222(1) ネットワーク 実体関連モデル 型データモデ ル 1.3424226808222(1) リレーションの 階層型データ 正規化 モデル 1.3424226808222(1) リレーションの 関係モデル 正規化 1.3424226808222(1) 後の場合は， 「射影」 というキーワードで一意にページが決 められるが，そのページはここで必要とする「関係代数」 ページ中の「射影演算」ではないことに原因があることが 判明した。そのページにはる「関係代数」ページ中の「射 影演算」への注釈はあるが，われわれの処理はそれを処理 し切れてなかったことに原因がある。 まとめると，同一カテゴリに所属する二つのキーワード は，経路の長さによって，計算された Lch に違いはあるが， パーセンテージに換算した方がより意味が明確になる。た だし，いずれの記述方法にせよ，各資格問題の正解と同一 基本情報技術者試験の正誤解答キーワードへの Wikipedia のリンク構造の関連度計算の応用（蔡・菅・ ・徐) 7 カテゴリ内の３つの誤選択肢間の関連度はほぼ同じである 図３には，同じ「ソート」カテゴリに属する「クイック ことが判明した。自動出題の時には，与えられた正解に対 ソート」（正解）と， 「挿入ソート」 ， 「選択ソート」 ， 「バブ して，関連度の高い候補を誤選択肢にするので，同じカテ ルソート」 という３つの誤選択肢，「ヒープソート」 （正解） ゴリに属するキーワードの関連度の差別化という課題が浮 と，「クイックソート」， 「シェルソート」 。「バブルソート」 き彫りになった。 という３つの誤選択肢間の LSPLCh による計算結果を示 している。明らかに，同一カテゴリ内における各キーワー ４. カテゴリリンク間関連度計算による問題と改良法 ド間の差別化を図ることができた。 ただし，記事によってハイパーリンクの い方に差があ ３章に示しているように，同一カテゴリ内のページ（記 り，影響を受けやすいことがある。例えば，図３の計算結 事）の Lch 計算結果に差がない。一方，LSP 法とは，記事 果において，クイックソート（正解）と，「挿入ソート」， のリード部 （冒頭文）を重要文と見做して解析する手法 「選択ソート」， 「バブルソート」３つの誤選択肢との関連 である［３］ 。これは，Wikipedia の各記事において，リー 度の順が， ド部 が多くの場合に他の概念との明確な意味関係を定義 ① 選択ソート」 した文であることを利用した手法である。特に，Wikipedia ② バブルソート」 におけるリード部 は，ほかの概念に対する is-a 関係が豊 富に定義されていることが中山らの調査によって判明して ③ 挿入ソート」 いる。 バブルソートと同じ 換ソートの 類に属するので，①と われわれは，LSP 法を用いて同一カテゴリの Lch 計算結 果の問題点を解消することを試みるために，LSPLch 法を ②の順序が素直になるほどとはいきにくい。同じく「ヒー 提案している［９］ 。LSPLch 法では，LSP 法の え方を基 ソート」と③番の「クイックソート」の順序もなるほどと に Wikipedia の重要文を冒頭の概要部 と定め，重要文に はいきにくい。すなわち，LSPLch 法では同一カテゴリ内に 含まれるハイパーリンクを計算の対象概念とした。２つの おける各キーワード間の差別化をすることはできるが，記 概念（記事）Ａ，Ｂから以下に式（4.1）を示す。 事の質によって左右されることがある。 LSPLch＝ プソート」が正解の後者の問題の場合も，②番の「バブル ５. まとめ 概念Ａのハイパーリンク ＝ a ，a ，…a ，a 概念Ｂのハイパーリンク ＝ b ，b ，…b というようになっているが，正解のクイックソートは， ，b 1 1 1 ∑ Lch a ，B ＋ ∑Lch b，B 2 n m 本研究では，Wikipedia のリンク構造のカテゴリリンク に基づく概念間の関連度計算を，基本情報技術者試験の資 (4.1) 格問題中のアルゴリズム関係とデータベース関係の資格問 題33問に応用した。存在しないページ問題や曖昧ページ問 概念Ａのハイパーリンクは，概念Ａに関する説明用語で 題を処理した後は，９割以上の正誤解答のキーワード間の あると え，対象の概念Ｂと Lch 計算することで概念Ａと の関係性の指標を増やす目的がある。同じように，概念Ｂ 関連度の計算ができた。 Wikipedia のリンク構造に基づ く関連度の計算手法は，資格問題の正誤解答のキーワード のハイパーリンクも概念Ａに対して Lch 計算を行う。各リ 間の関連度において一つの有効な方法であることを確認で ンク数の平 をとり足し合わせ，最後に全体で割ることで きた。言い換えれば，正解のキーワードを決めれば，誤選 LSPLch の値とする。 択 肢 は Wikipedia に お い て 正 解 と 同 じ ディレ ク ト リ の キーワードか関連項目中のキーワードから選択すれば，実 用的な演習システムを構築できる結果が得られた。 なお，同一カテゴリに所属するページ（記事）の差別化 を図るため，LSP 法の えを基にした LSPLch 手法による 計算も行った。その結果，同一カテゴリ内の記事を差別化 することができた。ただし，関連度計算結果は記事の質に よって左右されることがある。今後の課題としては，同じ ページの異なるセッションに属するキーワード間の関連度 の処理などが上げられる。 参 文献 図３ LSPLch による計算結果 １) Gabrilovich, E., and Markovitch, S. : Computing 8 基本情報技術者試験の正誤解答キーワードへの Wikipedia のリンク構造の関連度計算の応用（蔡・菅・ ・徐) Semantic Relatedness Using Wikipedia based Explicit 15) 玉川 奨, 桜井 慎弥, 手島 拓也, 森田 武 , 和 Semantic Analysis., in Pros. of Inter. Joint Conf. on Artificial Intelligence(IICAI 2007),pp.1606-1611(2007) 泉 憲 明, 山 口 高 平：日 本 語 Wikipedia イ ン フォ ２) Giles, J. : Internet Encyclopedias Go Head to Head, Nature, Vol.438, pp. 900-901 (2005) Conf. of the Japanese Society for Artificial Intelligence (JSAI 2010), 2I3-NFC4-3（2010） ３) Strube, M., and Ponzetto, S. P.:WikiRelate!Comput- ボックスからのプロパティ自動抽出, the 24th Annual ing Semantic Relatedness Using Wikipedia, in Proc. of 16) 中山 浩太郎, 原 隆浩, 西尾 章治郎：Wikipedia マイニングによるシソーラス辞書の構築手法, 情処学論 the American Association for Artificial Intelligence (AAAI 2006), pp. 1419 -1424 (2006) 47(10), pp. 2917-2928（2006） 17) 中山 浩太郎, 原 隆浩, 西尾 章治郎：自然言語処 ４) Shuai Cai, Ryota Suga and Haiyan Xu : Path based 理とリンク構造解析を利用した Wikipedia からの Web Semantic Relatedness Comparison among Wikipedia オントロジ自動構築に関する一手法, 電子情報通信学会 Language Editions, 64 Record of Joint Conf. of Elec. and Elec. Eng. in Kyushu, 07-2A-07 (2011) 第19回データ工学ワークショップ, A3-2（2008） 18) 森 竜也, 増田 英孝, 清田 陽司：Wikipedia を活 用した言語間差異比較システムの提案, DEIM Forum ５) Torsten Zesch, Iryna Gurevych. : Analysis of the Wikipedia categorygraph for nlp applications,in Pros.of the Workshop TextGraphs-2 :Graph-Based Algorithms for Natural Language Processing at HLT-NAACL 2007, pp. 1-8 (2007) ６) 伊藤 雅弘：Wikipedia を用いた概念間の関連度測定 に関する研究, Osaka University Knowledge Archive (OUKA) (2011) ７) 新井 嘉章, 福原 知宏, 増田 英孝, 中川 裕志： Wikipedia の言語間リンクに関する 析, 第22回人工知 能学会 全大（JSAI 2008), 2D3-02（2008） ８) 新井 嘉章, 福原 知宏, 増田 英孝, 中川 裕志： Wikipedia を用いた多言語情報アクセスに関する研究： 言語間リンクの 析と応用, 第20回セマンティックウェ ブとオントロジー研究会,pp.SIG-SWO-A803-15（2009） ９) 菅 亮太, 徐 海燕：Wikipedia リンク構造の関連度 による用語抽出及び用語問題の自動生成, 火の国情報シ ンポジウム2012, B-4-4（2012） 10) 菅 亮太, 徐 海燕：Wikipedia カテゴリ構造の関連 度計算による用語抽出および演習システムへの適用, 平 23九州連大, 07-2A-07（2011） 11) 菅 亮太, 徐 海燕：Wikipedia のリンクを活用した 用語問題に関する演習システムの構築, 平23信学 全 大, ISS-273（2011） 12) 菅 亮太, 徐 海燕：Wikipedia を利用した用語問題 に関する演習システムの構築, 平22九州連大, 08-2A -11（2010） 13) 鈴木 優, 吉川 正俊：Wikipedia におけるキーパー ソン抽出による信頼度算出精度および速度の改善, 第21 回セマンティックウェブとオントロジー研究会（第２回 Wikipedia ワーク ショップ）（ SIG-SWO), A901-01 （2009） 14) 杉原 大悟, 増市 博, 梅基 宏, 鷹合 基行：Wikipedia カテゴリ階層構造の固有名詞 類実験における 効果, 情報処理学会研究報告. 情報学基礎研究会報告 2009(2), pp. 57-64（2009） 2010, A5-5（2010） 19) 舟生 日出男, 穐山 雅 , 平嶋 宗：問題解決プロ セスを利用した選択問題の誤選択肢および解説の自動生 成, 2010.3.1, 信 学 誌 D, Vol. J93-D, No.3, pp. 292-302（2010） 20) 山崎 由佳, 井 崇, 熊坂 賢次：Wikipedia にお ける編集者の活動 析, 第21回セマンティックウェブと オントロジー研 究 会（第 ２ 回 Wikipedia ワーク ショッ プ） （SIG-SWO), A901-01（2009）