DEIM Forum 2016 G6-5

ページの階層構造に基づく具体度・詳細度を考慮した手順情報の検索
下野 普也†

山本 岳洋††

田中 克己††† 京都大学工学部情報学科 〒 606–8501 京都府京都市左京区吉田本町†† 京都大学大学院情報学研究科 〒 606–8501 京都府京都市左京区吉田本町
E-mail: †{shimono,tyamamot,tanaka}@dl.kuis.kyoto-u.ac.jp
あらまし 「ギターを上達する」「ダイエットする」「美味しいトーストを焼く」といった行動をとりたいと思った際，その行動を達成するための手順や方法を検索することがしばしば必要になる．このような手順や方法の検索を本研究
ではハウツー検索と呼ぶ．現在のハウツー検索は，通常の検索エンジンを用いて行うことができるが，検索結果として得られた手順ページの具体度が揃っていないという問題がある．本研究では，手順ページの情報源である wikiHowを対象として，手順ページの具体度を計算する手法を提案する．提案手法では，手順ページの具体度を，複数のステップと呼ばれるサブ手順の具体度から求める．その際に，ステップ間の詳細化関係という関係を導入し，詳細化関係と具体度を再帰的に求める手法を提案する．実験の結果，詳細化関係を再帰的に求めることで，詳細化関係の精度は，F値で 0.188 となり，また，詳細関係の精度向上に合わせて，具体度による手順ページランキングの精度も 0.84 に向上
した．
キーワード
ザの知識に依存すると考えられる．しかし，既存のランキ

1. は じ め にングはこうした手順ページの具体性を考慮していないため，

Web 検索エンジンが発達するにつれて，ある目的を達成する

検索結果にこれらの異なるユーザ向けのページが混在してための方法や手順を検索することが広く行われるようになっており，ユーザが欲しい手順ページを手に入れるに苦労するきている．本研究では，このような方法や手順のことを記述しことが多い．

た Web ページを手順ページ，その構成要素をステップと呼び，•あるステップのより詳細なステップの検索が困難な点: 例

手順ページの検索をハウツー検索と呼ぶ．ハウツー検索の例とえば，「コードの練習方法」というステップを閲覧している

して，「ギターを上達する方法を探す」「ダイエットする方法を探時に，そのステップの記述が曖昧であると「F コードの練す」「美味しいトーストを焼くための手順を探す」などがあげら習方法」や「コードの簡単な覚え方」といった，さらに詳れる．中村らが 2006 年に行った，1,000 人を対象とした Web

細な情報が欲しくなるときがある．しかし，現状ではユー検索の目的を調査したアンケートによると，1,000 人中 575 人

ザはこうしたより詳細なステップを得るためには，その都が「方法・手段」を探すためによく Web 検索を利用すると回度検索する必要がある．さらに，こうした詳細なステップ

答している [?]．また，近年では wikiHow（注 1） や nanapi（注 2） には手順ページの一部に記載されていることもりあり，手順代表される，手順ページをまとめたウェブサイトも登場し利用ページのタイトルからでは発見が難しい場合がある．

されている．このように，ハウツー検索は人々にとって重要な検索の一つとなっていると考えられる．

前者の問題点を解決するため，本研究では手順ページの具体性に着目し，手順ページの具体度を計算する手法を提案する．

しかし，一般的なウェブ検索と異なり，現状のハウツー検索

手順ページの具体性とは，「その情報だけを見て，ユーザが具体においては，いくつか問題点が存在すると考えている．たとえ的に何をすればよいかがわかるか」を表しており，これを表す

ば，人々が自由に手順ページをまとめて公開できる wikiHow で尺度を本研究では具体度と定義する．具体度が高い手順ページ

は，ユーザは検索クエリを投入することでクエリと関連度の高は，そのページを見れば何をすればわかるが，ある事柄に特化

い手順ページが検索結果として得られるが，以下に挙げる問題

したページが多く，予備知識がないとこれを理解することがで点が存在する．

きない事もあり，専門的であると言える．逆に具体度が低い手•

検索結果の具体性が揃っていない点: 例えば，ギターの上

順ページは，そのページだけを見ても具体的に何をすればよい達に関する手順ページには，「ギターの練習方法」のような，かはわからないが，物事の全体を見渡したりするのに有用であ

曖昧なステップしか含まれていないものもあれば，「ギターる場合が多く，ある事柄に関して知識を有さない初心者向けでソロの音の取り方」のような，具体的な手順ページも存在あると言える．

する．どのような手順ページをユーザが求めるかは，ユー

具体度による手順ページのランキングが可能となれば，ユー
ザの知識に合わせて，ユーザが求める具体度の手順ページを検（注 1）：http://www.wikihow.com/（注 2）：https://nanapi.jp/

索することが容易になると考えられる．
また，後者の問題点を解決するため，ステップ間の詳細化関係を推定する手法を提案する．具体度の低いステップに対して，されることが多いことに着目し，手順ページをそこで記述されそれに含まれる情報が他の手順ページ中の複数のステップにるステップの系列として表現している．本研究で扱う wikiHow

よって，より詳細な説明が為されている場合がある．このようにおいても，1 つのページがステップと呼ばれる複数の手順でな手順ページの部分集合は，元のステップを詳細化していると記述されており，我々も野本らと同様に，手順ページは複数の定義し，この手順間の関係を詳細化関係と呼ぶ．手順間の詳細ステップで構成されると考える．さらに，湯本らは手順ページ

化関係を求めることで，より具体的な情報をユーザに提示するを階層化する手法を提案している [?]．湯本らは「肉じゃがの作ことが可能である．

り方」といったレシピに関する情報を手順ページとみなし，手本研究では，手順ページの具体度およびステップ間の詳細化

順ページの詳しさに着目し，同じ事柄について記述している手関係を求めるため，両者を相互再帰的に求める手法を提案する．

順ページを階層構造化している．本研究と湯本らの研究は，手本研究では，手順ページの具体度とステップ間の詳細化関係は順ページの階層化に着目するという点で目的が同じである．一

互いに依存していると考える．手順ページの具体度はそこに含方で，湯本らの研究は手順ページと手順ページ間の関係に対しまれるステップの具体度によって決まる．ここで，ある具体的て階層関係を発見しているのに対して，我々は手順ページに含なステップを詳細化しているステップ集合は，元のステップよまれるステップと，別の手順ページに出現するステップ集合間

りも高い具体度を持つと考えられる．また，あるステップ集合の関係に対して，詳細化関係を求めているという点で彼らの研が別のステップを詳細化するためには，そのステップ集合は詳究とは異なる．

細化されるステップよりも具体度は高い必要がある．このようまた，今回は手順情報の知識源を対象として研究を行うが，に，具体度と詳細化関係は互いに依存しており，両者を再帰的

Web 上から手順情報を抽出する研究も活発に行われている．湯に計算することで，精度良く両者を計算することができると考本らは，手順表現や経過表現およびページの構造を用いて手順えられる．

情報の掲載部分を抽出する手法を提案している [?]．さらに同氏

提案手法はまず，与えられた手順ページ集合から，手順間のは，手順情報を動作と対象のペアでモデル化し，文末表現に注

粗い詳細化関係を求める．具体的には，ステップ間の順序関係

目して手順を説明する文のみを抽出しそれらの文に対して，動とテキストの類似性のみに基づき，再現率を重視した詳細化関作と対象を抽出する手法も提案している [?]．

係を求める．次に，得られた詳細化関係を基に，ステップ間の北口らは，Web 上でのハウツー検索を支援するためのクエリ

詳細化関係を表した詳細化関係グラフを作成し，グラフの深さ

変換手法を提案している [?]．北口らは，「ゴルフ 上達」のようを基準とするスコア付与アルゴリズムを適用することでステッな，名詞と動作で表されるクエリを対象にし，「スライス 修正」

プの具体度を求める．その後，得られたステップの具体度を基や「レッスン 受講」のようなより具体的なクエリを Web 検索に，詳細化関係グラフ中の不要なエッジを発見し，エッジを除

結果から抽出する．また，Yamamoto らは検索連動型広告を用去することで詳細化関係グラフを修正し，再度ステップの具体

いて，与えられたクエリのサブタスクを表すクエリをクエリの度を求める．このプロセスを繰り返しグラフを修正していく

クラスタリングによって求める手法を提案している [?]．こうしことで，各ステップの具体度および詳細化関係を得ることがでた研究は，ハウツー検索におけるクエリを対象とした研究であきる．

り，我々の研究はハウツー検索における文書を扱った研究であ提案手法により，「ギターの上達」に関する wikiHow 中の 16るといえる．ハウツー検索における文書のランキングを扱ったページ，304 ステップに対して詳細化関係と手順ページの具体度研究として，加藤らの研究がある [?]．加藤らは，Web 検索エを求めたところ，詳細化関係の精度は，最大で F 値が 0.188 とンジンを用いた手順ページの検索を対象にし，タスクの汎化となり，その時の手順ページの具体度によるランキングは nDCG

特化関係を利用することでより適合する文書を上位にランキン

で 0.84 となった．また，これらの評価値は，両者とも粗い詳細グする手法を提案している．タスクの汎化と特化関係をランキ化関係から求めた評価値よりも高くなっており，提案手法によングに用いる加藤らの考え方は，本研究におけるステップ間のる詳細化関係の精度の向上と，精度の良い詳細化関係を抽出す

類似度を考える際に有用となると考えられる．

れば良い具体度が求まることが確認された．

また，グラフの深さに応じて具体度を計算する方法には田中

本稿の構成は以下の通りである．2 節ではハウツー検索に関らの手法があげられる [?]．田中らは，Web ページの具体度をする研究について述べる．3 節では，本研究で求める具体度と評価するにあたって，WordNet において下位語が多く存在す

詳細化関係について述べ，両者の関係を整理する．4 節では提る語は曖昧であるという尺度を設けていた．これは本研究にお案手法について詳細に述べる．5 節で，実験と評価について述ける具体度の低いステップの判定基準と類似している．さらにべる．6 節で，まとめと今後の課題について述べる．

クエリから is-a 関係の木を作成し，ノード間の関係を考慮して

2. 関 連 研 究

検索意図を階層的に分類する Yin らの手法とも類似する [?]．
その他にも，リンクされる頻度を考慮するという点では関

近年，さまざまな研究者がハウツー検索に関連した研究を連研究に白川らの研究が挙げられる [?]．白川らは，Wikipedia

行っている．野中らは，手順ページを見やすさでランキングす

データ上でリンクされる頻度を考慮することによって異義語のる手法を提案している [?]．野中らは，Web 上に存在する，ある判定を行うという手法を提案しており，この手法は湯本らの手方法を説明するページは，各手順をまとめたリスト形式で記述

順ページ階層化 [?] でも応用されている．

いる」と記述する．例えば，si =“ギターのコード練習” に対して，ステップ集合 Sj = {“F コードの練習”, “G コードの練習”}
は，Sj は si を詳細化していると言える．
この詳細化関係を手順ページ集合から抽出することができれば，例えばユーザが “ギターのコード練習” に関するステップ
を閲覧しているときに，システムが自動的に “F コードの練習”と “G コードの練習” に関するステップを推薦することが可能となる．
また，詳細化関係にあるステップ集合は要素のステップ同士が類似していると考えられる．さらに，互いに類似するステッ
図 1 手順ページとステップの関係

プは同一手順ページ中では散在せずに，連続して偏在していると考えられるため，あるステップは，他の手順ページ中の連続したステップの集合により詳細化されている，と定義する．

3. 概 念 説 明
3. 1 ステップと手順ページ
まず本研究で扱う手順ページとステップについて説明する．
手順情報はそれ自体が手順のリストで構成されていると考えられる [?]．そこで本研究では，ある目的を達成するための一連の行動をまとめた文書を手順ページと呼び．手順ページに含まれる，1 つ 1 つの手順のことをステップと呼ぶ．本研究では，手順ページはそのページに含まれるステップの集合として表される (図??)．このような構造を持つ文書は，レシピやハウツー情報を扱ったサイトに多く存在し，本研究が対象とする wikiHow
も同様の構造を持っている．
またステップは手順の概略を表した「タイトル」と，手順の内容を記述した「本文」，を含む要素で構成されていることが多い．本研究で扱う wikiHow についても，ステップはタイト
ルと本文から構成され，ステップ間の類似度を計算する際に用いられる．

3. 2 具 体 度
本研究では，具体度とは，あるステップや手順ページに対して付与される，その情報がどれだけ具体的かを表したスコアと定義する．ここで，あるステップまた手順ページが具体的であるとは，「その情報だけを見て，ユーザが具体的にどのような行動を取れば良いかがわかる」として定義される．たとえば，ギターの上達に関するステップとして，“ギターのコード練習”というステップと “C コードの練習” というステップがあった
場合，後者のステップの方が，ユーザは具体的に何をすれば良いのか分かる場合が多く，従って，高い具体度となると考えられる．
また，本研究では，手順ページの具体度は，そこに含まれるステップの具体度によって定まると考える．従って，ある手順
ページ di の具体度を求めるためには，手順ページに含まれる
各ステップ sij ∈ di の具体度を求めれば良い．

3. 3 詳細化関係あるステップ si と，あるステップ集合 Sj = {sj1 , . . . sjk } が与えられたとき，ステップ si で記述されている方法の一部もし
くは全てが，ステップ集合 Sj でより詳細に記述されているとき，「si と Sj は詳細化関係にある」と定義し，「Sj は si を詳細化して

3. 4 具体度と詳細化関係の相互依存性
具体度と詳細化関係を求めるため，本研究ではそれぞれ以下の様な仮定をおいた．

•

具体度が高いステップは，具体的なステップから多く詳細化されている•あるステップ集合 Sj がステップ si を詳細化するとき，Sj
中の各ステップ sjl ∈ Sj は si よりも具体的である．

前者の仮定は，ステップの具体度を求めるためにはステップ間の詳細化関係を，また，後者の仮定は，ステップ間の詳細化関係を求めるためにはステップの具体度を必要としていることを表している．従って，本研究では具体度と詳細化関係を再帰的に求める手法を提案する．

4. 提 案 手 法
本研究では，具体度と詳細化関係を再帰的に計算する手法を提案する．まず，提案手法の流れについて説明し，その後詳細について述べる．

4. 1 提案手法の概要
提案手法の基本的な考え方は，まず，詳細化関係集合を簡潔な手法で求め，その後得られた詳細化関係に基づき各ステップの具体度を計算することで，はじめに得た詳細化関係から不要なものを削除するという考えである．これは，ステップの具体度を，詳細関係を利用せずに直接求めることは困難であるが，詳細関係集合は具体度を直接用いなくとも，テキスト間の類似度を利用することである程度の精度で求めることができるのではないかという考えに基づいている．
しかし，単なるテキスト類似度だけでは，どちらがより具体的なステップかが分からないため，本来詳細化関係ではないス
テップ間についても，詳細化関係であると判定してしまう可能性がある．つまり，ステップ間のテキスト類似度を用いること
で，再現率は高いが適合率の低い詳細化関係集合を得ることができる．このようにして求めた精度の低い詳細化関係集合を用いて，各ステップの具体度を計算することで，本来詳細化関係と判定すべきではない関係が発見することができ，適合率を向上することができると考えられる．
提案手法では以下のような流れに従い具体度と詳細化関係を求める．

（ 1 ） システムは手順ページ集合 D = {d1 , d2 , . . . , dn } を受け取る．ここで，n はシステムに入力される手順ページ数を表す．
（ 2 ） すべての手順ページ di ∈ D に含まれる各ステップ s について，詳細化関係集合を発見する．全てのステップ s ∈ S
について得られた詳細化関係集合をマージすることで，詳細化関係集合 R0 = {r1 , . . . rm } を得る．ここで，S は手順ページ集合 D に含まれる全ステップ集合，m は得られた詳細化関係の数を表す．
図 2 シード手順の発見（ 3 ） 得られた詳細化関係集合 R0 に基づき，詳細化関係木集合
0

0

0

R
T R = {tR
1 , . . . tn } を構築し，この木に基づき，各ステッ

プ s の仮具体度 Cs0 (s) を計算する．
（ 4 ） ステップの仮具体度を基に，各詳細化関係 ri ∈ R0 の詳
00

細度 M R (ri ) を求める．minri ∈R0 M R (ri ) が閾値以下なら，詳細化関係集合 R0 から ri を除去することで R1 を得
1る．更新された詳細化関係 R1 から構築された木 T R を元る．具体的には，ある単語 ti のステップ sj における出現回数
を n( i, j)，ステップ sj 中におけるすべての単語の出現回数の∑和を k nk,j ，入力手順ページ集合に含まれる総ステップ集合
を S ，S 中の単語 ti を含むステップを Sti と置くと，ステップ

sj における単語 ti の tf-idf 値 tfidf i,j は以下の式で定義される．

に，再び各ステップの具体度を計算する．

tfidf i,j = tf i,j · idf i
ni,jtf i,j = ∑k nk,j（ 5 ） 3. 4. を削除するべき詳細化関係 ri が無くなるまで繰り返
し実行することで，詳細化関係集合 R∗ を得る．
∗

（ 6 ） R∗ から構築された詳細化関係木集合 T R から，各ステッ

idf i = log

プ s の具体度 Cs∗ を求める．
（ 7 ） 各ステップの具体度 Cs∗ に基づき，手順ページ d ∈ D の具
体度 C d (d) を計算する．

|S||s : s ∋ ti |いま，ステップ si と sj の類似度を上記の tf-idf 値を用いたコサ
イン類似度で定義すると，sim(si , sj ) >= θ1 となる時，si は sj の以降，それぞれの工程について詳しく述べる．

シード手順であると言う (図??)．また，sim(si , sj ) = sim(sj , si )4. 2 シード手順の発見であるため，si が sj のシード手順であるならば，同時に sj は

システムは手順ページ集合 D を受け取ったのち，まず，各ス

si のシード手順である．

テップ s に対して詳細化関係集合を発見する．しかし，詳細化

si のシード手順は si を含まない全手順ページに対して，0 個

関係は手順と手順集合の関係であるため，全ての手順集合に対以上存在する．つまり，si のシード手順が，ある手順ページ d

して可能な詳細化関係を列挙し，一つ一つテキスト類似度に基中に複数個存在する場合もある．

づいて正しい詳細化関係であるかを判定することは計算量の点

4. 3 詳細化手順集合の発見

で効率が悪い．そこで，本研究では，シード手順という考えを本節では，詳細化ステップ集合 Sdetail の発見方法について述

導入し，あるステップに対してシード手順をまず求め，そこかべる．

ら詳細化関係集合を求める．

??節で述べた詳細化関係の定義より，Sdetail の要素はシードある詳細化される手順 sdetailed を詳細化するステップ集合

手順 sseed の前後に存在している．そこで，sseed の前後のス

Sdetail があるとき，Sdetail は同じ手順ページ中に連続して出現

テップ s′seed を 1 つ 1 つ取り出して， Sdetial に含まれるかを判している．従って，あるステップ sdetailed に対して，非常に類定する基準については以下の 2 点があげられる．

似するステップ sj が存在するとき，sj の前後のステップがも•し sdetailed や sj と類似していれば，それらは sdetailed を詳細

s′seed が Sdetail に追加されると sdetailed に含まれる単語の被覆度が大きくなる

s′seed と Sdetail が類似している化していると考えられる．このように，まずステップ sdetailed•と非常に類似するステップを求め，それを基に詳細関係を発見

以上 2 件の要件のどちらかを満たす時，s′seed ∈ Sdetail とする．

することで，計算量を削減することができると考えられる．こ

これを実際に求めるアルゴリズムを以下で定義する．

のとき，ステップ sj を sdetailed のシード手順 sseed と呼ぶ．

まず被覆度について形式化する．ステップ si に含まれる「名シード手順 sseed の発見するために，詳細元となるステップ

詞」「動詞」「形容詞 (最上級)」の集合を Ti とすると，s1 が s2

sdetailed との類似度を用いる．類似度には tf-idf 値によるコサの単語をどれだけ被覆しているかは，以下の式で表される．

イン類似度を利用する．本研究では，ステップの tf-idf 値を計算する際に，ステップ中に出現する名詞，動詞，形容詞の最上級形を用いた．名詞だけではなく，動詞と形容詞の最上級形を用いた理由は，ステップは動作を表すため動詞が重要であるこ

cover(s1 , s2 ) =ま た ス テップ 集 合 S = {s1 . . . sn } 中 の 単 語 集 合 TS =T1 ∪ T2 ∪ . . . Tn が s2 の単語をどれだけ被覆しているかは，と，wikiHow においては “at least” や “lowest” といった，手順の性質を表すのに最上級形がよく用いられているためであT1 ∩ T2
T2

cover(S, s2 ) =TS ∩ T2
TS図 3 詳細化関係の発見と書ける．
したがって，s′seed を Sdetail に追加することで増加する被覆′とおくと，次度は，s′seed 追加後の詳細化ステップ集合を Sdetail式で表される．

δcover(s′seed , Sdetail ) =′, sdetailed )cover(Sdetail−1
cover(Sdetail , sdetailed )この被覆度と，??節で定義した類似度を用いて，詳細化ス
図 4 詳細化ステップ集合の範囲が重なっている場合のマージ例

テップ集合を求めるアルゴリズムを以下に示す．
（ 1 ） sseed を Sdetail とし，sm = sM = sseed とする（ 2 ） δcover(sM +1 , Sdetail ) >= θ2 または sim(sM , sM +1 ) >= θ3 を満たすとき，sM +1 を Sdetail の要素とし，sM = sM +1 に更新する．これを前式を満たす限り繰り返す（ 3 ） δcover(sm−1 , Sdetail ) >= θ2 または sim(sm , sm−1 ) >= θ3 を満たすとき，sm−1 を Sdetail の要素とし，sm = sm−1 に更新する．これを前式を満たす限り繰り返す（ 4 ） sm =| sM ならば，ri = (sseed , Sdetail ) とする．

(4) は，詳細化は複数のステップにより行われるべきで，単一のステップによる詳細化は提案手法では詳細化と定義せず棄却することを意味する．
図??に詳細化関係の例を示す．
これで基本的な詳細化ステップ集合の求め方は終わりだが，ある手順のシード手順が同手順ページ中に複数存在する場合を考える．
仮定によれば，ある手順を詳細化するステップは連続して存在しているので，同手順ページ中に複数の詳細化ステップが存在することは仮定に反する．そこで，以下では複数詳細化ス

図5

詳細化ステップ集合の範囲が重なっていない場合のマージ例

テップをマージする方法を提案する．同手順ページに複数の詳
細化ステップが存在する場合，以下の 2 パターンが考えられるのでそれぞれについてマージの方法を述べる．

•

詳細化ステップ集合の範囲が重なっている場合: 詳細化ス
テップ集合をすべて正しいものとし，要素の和集合を新たな詳細化ステップ集合とする．このマージ方法の実際の例を図??に示す．

•

詳細化ステップ集合の範囲が重なっていない場合: 詳細化
ステップ集合は 1 つ以外間違っているとし，各シード手順と詳細元の類似度を比較する．最も高いものを正しい詳細
化集合とし，それ以外を棄却する．このマージ方法の実際の例を図??に示す．
これを定式化すると次のようになる．

0000（ 1 ） sjk の di 中における詳細化関係を Rjk= {ri1, ri2. . . rin}0とし．rip中の詳細化ステップ集合を Sp0 とおく．

（ 2 ） Sp0 に含まれるステップの index の最小・最大を spm ，spM と
する．
0
0
0
（ 3 ） Rjk
中から 2 つの詳細化関係 ri1, ri2
を取り出す．
2
2
1
2
1
1
2
（ 4 ） s1m <= sM , sm <= sM または sm <= sM ), sm <= sM を満たす
0
0
時，ri1
, ri2
を棄却し，新たな詳細化関係 rx0 を作成する．

（ 5 ） sxm = min(s1m , s2m ), sxM = max(s1M , s2M ) となるように Sx0にステップを格納する．またシード手順と詳細元手順の類
似度は高い方を設定する．
（ 6 ） 4 で定義した条件式を満たすものが存在する限り，3 から 5の作業を繰り返す0（ 7 ） Rjkの要素が 2 つ以上ある場合，シード手順と詳細元手順

の類似度が最も高い詳細化関係以外を棄却する．
以上の作業により，ある手順の詳細化関係ステップ集合は，
手順ページ毎に必ず 1 また 0 個となるように設定できた．

4. 4 仮具体度の計算
前節の手法により，与えられた手順ページ集合から詳細化関係集合 R0 を得ることができた．しかし，これらはテキスト類

図 6 詳細化関係木集合の例

似度のみに基づいて得られており，本来は詳細化関係ではないものも多く含むと考えられる．そこで，詳細化関係集合をもと詳細化するとき，Sj は si よりも具体的であると考えられる．

に各ステップの仮具体度を計算し，詳細化関係内の手順間の具

そこで，仮具体度を用いて，R0 中の各詳細化関係 ri = (si , Sj )体度をみることで，得られた詳細化関係が正しいかどうかを評に対して，詳細化先のステップ集合 Sj が詳細化元のステップ

価する．

si よりもどの程度具体的か計算する尺度として，詳細度 Mr0i

ステップの具体度を求めるにあたり，本研究では以下の仮定を以下の式で定義する．

∑

をおいた．

•

Mr0i =

具体度が高いステップに詳細化されているステップほど具体度が高い
上記の仮定に基づいてステップの具体度を求めるため，本研

究では以下のアルゴリズムに従って各ステップの具体度を計算

0s∈Sj Cs

Cs0i

詳細度 Mr0i は詳細化先の各ステップの具体度が詳細化元のス
テップの具体度よりも大きいほど高い値をとる．
全ての詳細化関係 r ∈ Ri0 に対して詳細度 Mr0i を計算し，最する．
（ 1 ） 空の詳細化関係木集合 T 0 = ϕ を用意する．

も低い詳細度（すなわち，minri ∈R Mr0i ）が閾値 θ4 を下回って（ 2 ） 全てのステップ si ∈ S に対して，以下を実行する．

いれば，その詳細化関係を詳細化関係集合 R0 から削除し R1（ a ） ステップ si を根とし，詳細化関係集合 R0 中に，si がを得る．得られた R1 を元に，??節および本節で述べた手法を

詳細化元，sj が詳細化先となっているような詳細化関閾値 θ4 を下回る詳細化関係がなくなるまで繰り返し適用して係があれば，sj を si の子とする詳細化関係木 t0i を作いくことで，詳細化関係集合 R∗ を得ることができる．最後に，成する．また，sj に対しても同様のことを行い，sj をR∗ に基づいて各ステップ si の具体度 Cs∗i を求めることで，詳

詳細化元，sk が詳細化先となるような詳細化関係があ

細化関係集合とステップの具体度を求めることができる．

れば，sk を sj の子として ti に追加する．この手続き

4. 6 手順ページの具体度の計算を幅優先で再帰的に行うことで木にステップを追加し最後に，得られたステップの具体度に基づいて，手順ページていく．この時，閉路あるいは子が複数の親を持つよの具体度を計算する．本研究では，手順ページ d の具体度 Cd

うなエッジが木に追加される場合は，そのエッジを削

を，d 中に含まれる各ステップの具体度の平均値として求めた．

除する．これは，手続きを幅優先で行うことで決定的

具体的には，手順ページ d の具体度 Cd は，d 中の具体度が定に行うことができる．

義されているステップ集合 Sd とそのステップ数 nd を用いて

（ b ） 得られた詳細化関係木 t0i を T 0 に追加する．

Cd =（ 3 ） 全ての木 tl ∈ T 0 の各ノード s に対して，根を 1 とするそ

1 ∑ ∗
Cs
nd s∈Sdのノードの深さを求める．
（ 4 ） 各ノードに付与された深さの平均値をそのノード (ステッとして計算する．なお，本手法は手順ページ中のどのステッププ) の仮具体度する．すなわち，ある木 tl 中のあるノードに対しても詳細化関係がないような手順ページに関しては，具si の深さを di,l とすると，ステップ si の仮具体度 Cs0i は，∑
Cs0i = k1 t0 ∈T 0 di,l として求められる．ここで，k はス

体度を計算することができない．そうした手順ページに対する具体度の計算は今後の課題である．

l

テップ si を含む木の数を表す．

5. 実

験

たとえば，上記のアルゴリズムを図??で表す詳細化関係集合に対して適用すると，この図のステップ i の仮具体度は，

Cs0i = (2 + 1)/2 = 1.5 と計算される．このように，上記アルゴ

本節では，本研究で行った実験の概要とその結果について述べる．

リズムは，詳細化されているステップを詳細化しているステッ5. 1 実 験 設 定

プに対して，より高い具体度を付与することができる．

提案手法の有効性を検証するため，「ギターの上達」に関する

4. 5 不要な詳細化関係の削除

wikiHow 中の 16 手順ページを人手で用意した．16 ページ中に前節の手法により，詳細化関係集合中に出現する全ステップ

存在する総ステップ数は 304 個であった．まず，用意した手順に対して仮具体度が求まった．本節では，得られた仮具体度にページ集合を対象に，著者らが人手で詳細化関係を用意した．

基づいて，現在得られている詳細化関係集合から不要な詳細化

また，手順ページの具体度をそれぞれ 5 段階で評価した．なお，関係を発見し削除する手法について述べる．

今回用意した 16 手順ページ中に存在した詳細化関係は 31 個で??節で述べたように，あるステップ集合 Sj がステップ si をあった．

単 語 の 抽 出 お よ び 品 詞 推 定 に は ，Natural Language

Toolkit（注 3） を 用 い た ．ま た??節 で 用 い た 閾 値 は そ れ ぞ れ ，
θ1 = 0.2, θ2 = 0.2, θ3 = 0.25 と設定し，??節で用いた θ4には閾値を設定せず，すべての詳細化関係が削除されるまでの，
詳細化関係の精度と手順ページの具体度によるランキング精度を検証した．

5. 2 評 価 尺 度得られた詳細化関係の精度評価には以下の尺度を用いた．

•

再現率: システムが抽出した詳細化関係集合において，正解のステップ集合の要素を 1 つでも含んでいる Sdetail の
数を x，人手で用意した全詳細化関係の数を y として，次式で再現率 R を定義した．

R=

x
y

図7

不要な詳細化関係の削除による再現率・適合率・F 値の変遷

これは，詳細化関係にあるステップ集合を推薦する際，手法が取得した詳細化ステップ集合と正解のステップ集合が完全に一致していなくても要素が 1 つでも一致していれば実用上の問題はないという考えに基づいている．

•

適 合 率:

ま ず，シ ス テ ム が 抽 出 し た あ る 詳 細 化 関 係

ri = (sdetailed , Sdetail ) に対する適合率 scoreri を定義す
る．いま，z を Sdetail 中の sdetailed に対する正解詳細化関係ステップ数とするとき，scoreri をscoreri =z|Sdetail |として求める．システムが抽出した詳細化関係集合 R に対する適合率 P を，以下の式で計算する．
∑
ri ∈R scoreri
P =|R|
この適合率は，上記で述べた再現率とトレードオフの関係•

5. 3 実 験 結 果
まず，詳細化関係の精度について述べる．図??は具体度に基になっている．

づく不要な詳細化関係の削除を行うことで，システムが抽出しF 値: 適合率 P と再現率 R の両者を考慮した評価値とした詳細化関係の精度がどのように変化したのかを表す図である．

て，F 値を用いた．F 値は以下の式で定義される．

図中の x 軸は横軸は詳細化関係を削除した回数，また，y 軸の

2P R
F =
R+P
次に，具体度に基づく手順ページのランキングには以下の評
価指標を用いた．

•

図 8 具体度に基づく手順ページランキングの精度

赤線は再現率，青線は適合率，黒線は F 値を表している．図??
では詳細化関係が 0 個になるまでの変遷を表している．図??の左端の再現率を見ると，??節，??節の手法で取得した詳細化関係の再現率は 0.4 程度であることが確認できる．また，不要な

nDCG: 具 体 度 の 評 価 に は nDCG（normalized Discounted Cumulative Gain）を用いて行う．手順ページ
di の前項で定めた 5 段階評価値を G[i] とし，提案手法が算出した具体度の高い順番にランキングされた手順ページ
系列 D′ = [d′1 , d′2 . . . d′n ] に対して，DCG は次のように計

∑n

算される．

DCG =

i=1 G[i]log2 (i + 1)

詳細化関係を削除していくことで，適合率が上昇していることも分かる．不要な詳細化関係を削除することで，再現率も減少してしまうものの，詳細関係の削除を行っていくことで F 値も向上していることが分かる．
次に具体度に基づく手順ページのランキングの評価結果を図??に示す．図中の x 軸は詳細化関係を削除した回数．y 軸は

nDCG を表す．図??より，詳細化関係の削除を行うことで，ラ

これに対して，理想的な順番 (実際に具体度の高い順番)

ンキングの精度が向上していることが分かる．具体的には，詳に並べたときの DCG の値を iDCG として iDCG で DCG

細化関係を始めて抽出した際（x 軸の左端）の nDCG が 0.77を正規化した値なのに対して，詳細化関係の F 値が最大となった削除回数時のDCG
nDCG =
iDCG
を評価値として手順ページの具体度を評価する．

ランキングは，0.84 であることが分かる．このことは，精度の高い詳細化関係を抽出することで，手順ページの具体度の推定精度も向上するということを示唆している．

（注 3）：http://www.nltk.org/

5. 4 考察

削除の最適な閾値の設定方法について取り組む予定である．

最後に，今回の実験から得られた結果について考察を行う．

謝辞 本研究の一部は，文科省科研費基盤 (A)「多元的検索

図??にあるように，詳細化関係の削除により詳細化関係の抽出要求に対応できるオンラインデータマイニング検索方式の研精度は向上しているものの，その精度は最大でも F 値で 0.188

究」（15H01718，研究代表者：田中克己）によるものです．こと高い精度とは言えない結果となった．提案手法の性質上，不こに記して謝意を表します．

要な詳細化関係の削除により再現率はが向上することはないた
め，??節，??節で詳細化関係を取得する手法を改善する必要がある．改善の方法として挙げられるのは，ステップ間の類似度判定の手法である．本研究における提案手法では，ハウツー検索であるということを考慮して，通常の検索とは違い，名詞だ
けでなく行動に関わる動詞なども注目して類似度を計算した．
しかし，より高精度に詳細化関係を抽出するためには，品詞だ
けではない情報を利用して類似度を計算する必要があると考えられる．
また，本研究の実験では，詳細化関係の削除を停止する閾値
を設定せずに，実験結果の評価を行った．しかし，実際に本提案手法をシステムに適用するためには，具体的な閾値を設定する必要がある．そのためには正解データのみではなく，多くの学習データからこの値を上手く設定する必要がある．
不要な詳細化関係の削除による，具体度に基づく手順ページのランキングは一定の効果を示すことができたと考えている．
例えば「ギターの練習方法」という手順ページは具体度が低い
ことが予想されるが，類似度だけでは詳細化されるステップもするステップも多く持ってしまうため，削除を行う前では 3 位にランキングされていた．しかし，詳細化関係の削除を行うことで，F 値が最大となった時点では 13 位にランキングされ，ランキングの精度が向上したということが分かった．さらに「ギター譜の読み方」といったページ具体度の高いページも提案手法によりランキングが 9 位から 1 位に向上したことも確認できた．一方で，「ギターのスケールの学び方」という具体度が高い
ページが F 値最大の時点で最下位にランキングされることもあった．この手順ページは，F 値が最大値になる直前までは上位にランキングされており，削除回数が 170 前後で nDCG の値が急激に落ちているのはこれが原因だと考えられる．このように，間違った削除を行ってしまうタイミング見極めるためにも，閾値の設定は必要であると考えられる．

6. まとめと今後の課題
本研究では，ハウツー検索のための手順ページの具体度およびステップ間の詳細化関係を求める手法を提案した．提案手法
では，ステップの具体度と詳細化関係が互いに依存していることに注目し，再帰的なアルゴリズムを用いることで，それぞれを求める．最終的にステップの具体度を元に手順ページの具体度を求めることで，手順ページの具体度を求める．実験結果か
ら，提案手法による詳細化関係の削除により，具体度に基づく
手順ページのランキング精度が向上することを確認できた．一方で，詳細化関係の抽出精度は高いとはいえず，さらなる改善が必要であることも分かった．
今後は，詳細化関係の取得アルゴリズムを改良し，取得出来る詳細化関係の再現率を向上させる手法や，不要な詳細化関係