DEIM Forum 2014 C3-2

検索・分析のための手順文章からの意味構造抽出前田 浩邦†

山肩

洋子†

森

信介††

† 京都大学情報学研究科 〒 606–8501 京都市左京区吉田本町†† 京都大学学術情報メデ ィアセンター 〒 606–8501 京都市左京区吉田本町
E-mail: ††forest@i.kyoto-u.ac.jp
あらましより賢い検索や分析を可能とするために、手順文章から意味構造を抽出する手法を提案する。具体的には、

手順文章としてレシピを題材とし 、手順を記述している文章に対して、単語分割、固有表現認識、文章解析を順に行う。単語分割と固有表現認識は、既存手法を用いることとし 、本論文では、意味構造の表現としてフローグラフ（ 無
閉路有向グラフ）を提案し 、単語に分割されレシピ固有表現タグが付与された文章をフローグラフに変換する文章解
析について述べる。
キーワード

手順文章, レシピ , 意味構造, 自然言語処理

1. は じ め に

レシピはもっとも需要がある手順書と考えられる。先行研究として、レシピテキストのフローグラフ化はより詳細なレシピテ

テキストを対象とする検索や分析においては、自然言語処理

キストの検索に有効であることが示されている [1]。さらに、レを用いてその精度や利便性を高めることが一般的である。しかシピテキストとその実施映像をそれぞれ解析して 2 つのフローしながら、実用になっている自然言語処理は、単語分割や読みグラフを生成し 、両者をマッチングすることによって、言語表

推定など 、系列予測に分類される処理がほとんどである。ウェ

現と映像領域の対を自動で獲得する研究が行われている [2]。

ブ ページなど のテキストの構造や内容を計算機が理解できれ本論文では、手順書をフローグラフに自動変換するための機ばより知的な検索や分析が可能となると考えられる。本論文で械学習に基づく手法を提案する。実験にはレシピとそのフロー

は、対象を手順書 (手続きを記述した文章) に限定し 、自動的にグラフ表現からなるコーパス [3] [4] を用いる。フローグラフの

文章全体の意味内容をフローグラフ表現に変換する手法を提案

頂点は、手順書中の重要語である。辺は重要語間の関係を表し 、する。

従来の自然言語処理においては係り受け関係、述語項構造、共従来の自然言語処理の研究は、様々な部分問題を設定し 、各々参照・照応に相当する関係である。初期のレシピの構造化の研を逐次的に組み合わせることにより言語処理を構築していた。

究 [5] では、フローグラフとして木が用いられている。しかし 、文章理解を目的として、形態素解析 (単語分割と品詞推定) 、係材料の分割などのように、手順書の手続きを表現するには、無り受け解析、述語項構造解析、共参照解析を逐次的に組み合わ

閉路有向グラフ (DAG; Directed Acyclic Graph) が必要であさる。本論文では、単語分割および重要語認識の結果を入力とる。上述のレシピフローグラフコーパスでは、内容表現としてし 、重要語間の関係を表すフローグラフを出力する方法を提案

最終生成物を根とする根つきの DAG が用いられている。

する。

フローグラフへ変換手法は、係り受け解析において使われて文章一般に対して内容表現の形式の良い定義を与えるのは非きた手法 [6] [7] の拡張である。本手法は、手順書内の重要語が常に難しく、本論文では検索や分析の需要があり利便性が高い

あらかじ め抽出されていると仮定する。その状態で 、重要語と考えられる手続き文書に限定する。手順書とは、物を作ったの間に辺を張り、フローグラフを出力する。本研究で扱う言語

り、決められた状態にするまでの一連の手続きを自然言語で記現象は、述語項構造、係り受け、共参照などを含んでいる。従述したものである。典型的な例は、取扱説明書や料理のレシピ

来は、各々を解析する処理を逐次的に組み合わせて処理を構築である。手順書は、複数のステップからなり、各ステップは複していたが 、本手法では、一度に処理を行い、フローグラフを数の文からなる。各文は、どの物体をどの動作に用いるかとい得る。機械学習に基づく提案手法の有効性を検証するために 、うことや、ある動作で得られる結果が後段のどの動作に使われルールに基づいたフローグラフの推定手法と比較する。さらに、るのかということを記述している。手順書を、その手続きの流

上述した言語現象の観点から本手法による推定結果を分析する。

れを示すフローグラフで表現することにより、物体と動作の間や、動作と動作の間の関係が明確になる。

2. 関 連 研 究

本研究では 、具体的に処理する手順書として料理のレシピ

図 1 に示すように、レシピテキストのフローグラフ化には単(以下単にレシピと呼ぶ) を採用する。レシピは、自然言語処理

語分割と固有表現認識が必要である。Mori ら [8] は、レシピテの観点からは、様々な言語現象を含んでおり興味深い解析対象

キストをフローグラフに変換することを目的とし 、変換のためである。応用の観点からは、多数のインターネットサイトがあに必要な言語処理を調理ド メインに適応させている。Mori ら

り、加えて書店でも大きなスペースが割り当てられているなど 、は、点予測と部分的にアノテーションされたコーパスを使うこ表1

固有表現の種類

タグ

意味

備考

F

食材

中間・最終生成物を含む

T

道具

調理道具や器など

D

継続時間

概数表現を含むQ

分量

概数表現を含む

Ac

調理者の動作 語幹のみ

Af

食材の動作

Sf

食材の状態

St

道具の状態

語幹のみ

誤差伝播が起きることにより、長い文に対する係り受け精度がグラフベースのアプローチよりも低くなる傾向がある。

3. レシピフローグラフ
図 1 レシピテキストのフローグラフへの変換の流れ

本節では 、レシピフローグ ラフコーパス [3] [4] におけるフとで、調理ド メインでの単語分割、固有表現認識、係り受け解

ローグラフの定義を概説する。

析の精度をそれぞれ上げている。ただし Mori らは個々の解析

3. 1 レシピとフローグラフ器の精度の向上を示しただけであり、レシピテキスト全体のフ

通常、レシピは以下の 3 つの部分から構成される。

ロー化には至っていない。

（ 1 ） タイトル

レシピテキストからフローグラフへの変換手法はいくつか提（ 2 ） 食材リスト (材料名および分量)案されている。Momouchi [9] は、人間が定義したバッカスナウ（ 3 ） 調理手順 (手順番号および手順説明文)

ア記法に基づいた、レシピなどを含む手続き文章全般の解析手

本稿で説明するフローグラフは、調理手順の部分の意味内容

法を提案している。Hamada ら [10] は、レシピテキストから木を表現する。レシピの例を図 2 に、この調理手順に対応するフに自動変換する手法を提案している。この手法では、まず人手ローグラフを図 3 にそれぞれ示す。

で素材、調味料、動作などの属性の入った辞書を構築しておく。

レシピで記述される手順には、依存関係があるものもあれば 、次に、レシピテキストに対して辞書との最大マッチングを行いないものもある。例えば 、調理者は、ニンジンを茹でる前にニ

ノード を取り出す。最後に、述語項構造に従ってノード 間に辺ンジンを切る必要があるが 、ニンジンを茹でる前にジャガ イモを張り、レシピテキストをグラフに変換する。Hamada らの研を切る必要はない。そこで、調理の手順を表現するために、フ究は先駆的ではあるが 、この手法は整形されたテキストに適用

ローグラフを用いる。ほとんど のレシピは木で表現できるが 、されることを前提としており、様々なスタイルの文章や表現に木で表現できないレシピも存在する。典型的な例は 、食材の対して頑健ではないという問題点がある。山肩ら [2] は 、レシ分割である。したがって、フローグラフは、無閉路有向グラフ

ピテキストを木に変換し 、レシピテキストと調理映像の対応付(DAG; Directed Acyclic Graph) である。

けをする手法を提案する。この対応付けにより、レシピテキス

フローグラフの頂点は、食材や道具、あるいは動作などに対トから調理映像を参照できるような調理コンテンツの構築が可応する。辺は、それらの関係を表す。一般の DAG とは異なり、能になる。第 1. 節でも述べたように、山肩らの木の生成手法はレシピフローグラフは根と呼ばれる特別の頂点がある。これ

規則に基づくものであり、頑健な解析は難しい。

は、料理の完成品に対応する。以下、頂点と辺についての説明

我々は係り受け解析の手法を使ってレシピ全体をグラフ化すを行う。

る。係り受け解析には大きく分けて 2 種類のアプ ローチがあ

3. 2 フローグラフの頂点

る。すなわち、グラフベースのアプローチ [11] [6] と遷移ベース

フローグラフの頂点は 、食材や動作を表す単語列からなる。

のアプローチ [7] [12] である。グラフベースのアプローチの代

通常、ある実態に対応する単語列を固有表現と呼ぶので 、本表的な手法は最大全域木 (MST; Maximum Spanning Tree) をコーパスにおいてもこれを踏襲する。表 1 に、固有表現の種類

用いるものである。MST は McDonald ら [6] によって文の係(クラス) を掲げる。この表からわかるように、通常の固有表現

り受け解析へ導入された。現在では係り受け解析の主要な手法と異なり、調理者や食材の動作を表す用言も含む。以下では 、の一つとして知られており [13] 、MST をベースにした応用も各固有表現クラスについて順に説明する。例の表記にあたっ

研究されている [14]。McDonald ら [13] は、これらグラフベーては、単語境界を空白で示し 、固有表現となる単語列をスラッ

スと遷移ベースの 2 つのアプローチを比較し 、全体的な精度は

シュ(//) で囲み、最後にクラスを示す記号を付加している。

ど ちらの手法も大差ないものの、様々な係り受けの場合の中で3. 2. 1 F: 食材

それぞれ精度が上がる場合と下がる場合があることを示した。

食材は 、材料リストに記載されているような材料名に加え

例えば 、McDonald らによると、遷移ベースのアプローチは 、て、「タネ」「生地」といった中間食材名や、料理の完成品を含図 2 レシピの例

図 3 図 2 のレシピから生成されたフローグラフ

表2

辺のラベル

ラベル

意味

subj

主語 (ガ格)d-obj

対象 (ヲ格)i-obj

方向 (ニ格)T-comp道具デF-comp

食材デ

F-eq

同一の食材

F-part-of

食材の一部

F-set

食材の集合

T-eq

同一の道具

T-part-of

道具の一部

A-eq

同一の動作

V-tm

動作を行う

other-mod その他の修飾語句

む。ただし修飾句は F に含めない。典型的な例は、以下の通り

場合があり、T とする。
例) /３ 分/D /レンジ /T を /し /Ac て から

3. 2. 3 D: 継続時間
加熱時間や冷却時間など 、加工の継続時間を示す。数字と単位のほか、それらに対する概数表現等も含める。
例) /１２ 〜 １５ 分/D 間 /煮込/Ac み ます例) /５ 分 くらい/D

3. 2. 4 Q: 分量

食材の量を指定する表現を分量とする。数字部分や単位に加えて、それらに対する概数表現等も含める。
例) /人参/F /３ 〜 ４ ｃｍ くらい/Q

3. 2. 5 Ac: 調理者の動作
調理者が主語となる用言で、主に他動詞である。表層表現のである。

比較により同一性を判定できるようにするために、活用語尾を例) 新しい /卵/F を /割/Ac っ て

3. 2. 2 T: 道具含めない。また、補助的動詞は含めない。
例) /切/Af っ た /ニンジン /F を鍋、蓋、包丁、コンロなど 、調理道具や器を道具とする。手や指などの調理者の身体の一部も道具のような振る舞いをする例) /沸騰 さ せ/Ac た ら3. 2. 6 Af: 食材の動作
食材が主語となる用言もある。その場合には、Af とする。範

















d-obj
例) /炒め/Ac −−−−→ /取り出/Ac

方向 (ニ格) は、食材を『食材 (F) 』に混ぜる場合や、食材を囲や判定の基準は Ac と同じである。

『 容器 (T) 』に入れる場合など 、主に調理動作と対象食材の行

3. 2. 7 Sf: 食材の様態用意された食材様態の初期状態を表す表現、並びに Ac や Afの影響で遷移する (した) 状態を表す表現を Sf とする。ただし 、き先を関係づける。たとえば「 /材料/F を /ボール /T に /入れ /Ac て」の場合は以下のようになる。


























d-obj
例) /材料/F −−−−→ /入れ /Ac

量の表現は Q である。

i-obj例) /ボール /T −−−→ /入れ /Ac例) /柔らか /Sf く /な/Af る
例) /色/Sf が /変わ /Af る

3. 3. 2 道具デ格 (T-comp)・食材デ格 (F-comp)
道具デ格は、『調理者の動作 (Ac) 』と、それを実行するのに例) /濃 い め/Sf の /調味 料/F使用される『道具 (T) 』を関連づける。たとえば「アルミホイ

3. 2. 8 St: 道具の様態

ルで覆い」という文は以下のようになる。

用意された道具様態の初期状態を表す表現、並びに Ac や Afの影響で遷移する (した) 状態を表す表現を St とする。
例) /強火/St の /フライパン /T で /炒め/Ac例) /オーブン /T を /１５０ 度/St に /予熱/Ac

















T-comp例) /アルミホイル /T −−−−−−→ /覆/Ac

また、『調理者の動作 (Ac) 』を実行する道具が食材である場合もある。これは食材デ格で指定する。たとえば 、「 /オリーブ
オイル /F で /焼/Ac き ます」という文は以下のようになる。

















F-comp−−−−−→ /焼/Ac例) /オリーブオイル /F −3. 3 レシピフローグラフの辺
前節で述べた固有表現について、文章中の固有表現間に以下

3. 3. 3 同一の食材 (F-eq)・食材の部分 (F-part-of)・食材のであげる 3 つのうちのいずれかの関係が認められる場合、それらの固有表現に対応する頂点の間に枝を張り、ラベルとしてその関係の種類を付与する。

集合 (F-set)
すでに登場した食材と同一の物体を指している固有表現を関連付けるためにいくつかのラベルを用意した。たとえば「１) 玉•述語項関係がある場合 (ゼロ照応も含む)•

ねぎを切ります、２) １) を炒めます」の場合、2 個目の「１) 」

同種の 2 つの固有表現の間に何らかの参照関係がある

は「手順１) 」の結果 (すなわち切った結果) と同一食材なので、場合•

手順１) の最後の動作を「同一の食材 (F-eq) 」とする。

2 つの動作の間に何らかの関係がある場合

ラベルの一覧を表 2 に掲げた。以下では 、これらを順に説明
する。

















F-eq
例) /切/Ac −−−→ /１)/F

以前に登場した食材の一部を指していると判断できる場合、

3. 3. 1 主語 (ガ 格, subj)・対象 (ヲ格, d-obj)・方向 (ニ格,i-obj)

たとえば「１) 玉ねぎの皮を剥いて」という文においては、「皮」
は「 玉ねぎ 」の一部であると考えられるため、「 皮」を「 玉ね

主語 (ガ格)・対象 (ヲ格)・方向 (ニ格) は、調理者の動作とその対象食材を関連付ける。
主語 (ガ格) は多くの場合、『食材 (F) 』と『食材の動作 (Af) 』
を関係づける。たとえば 、「 /水/F が /沸騰/Af したら」というぎ 」の『食材の一部 (F-part-of) 」に指定する。

















F-part-of例) /皮/F −−−−−−−→ /玉ねぎ /F以前に登場した食材の集合を指していると判断できる場合、
たとえば「１) 玉ねぎと人参を切ります。２) 野菜を炒めます」

文は次のような枝を生成する。









という文章では 、「 野菜」が「 玉ねぎと人参」を指していると









考えられるため、「野菜」の「食材の集合 (F-set) 」に「玉ねぎ 」

subj例) /水/F −−−→ /沸騰/Af

対象 (ヲ格) は、『調理者の動作 (Af) 』とその対象となる『食材 (F) 』とを関係づける。たとえば 、「 /チーズ /F を /おろ/Ac
しておいて」という文は次のような枝を生成する。




d-obj
例) /チーズ /F −−−−→ /おろ/Ac









それ以前の調理動作によって生成された食材を対象として調理動作を行う場合は、その対象食材が文中に表れていない場合がある。たとえば 、「玉葱を炒めたあと取り出す」とある場合、「 /取り出/Ac 」した対象の食材は、「 /玉葱/F を /炒め/Ac 」た
結果として生成された食材である。このように、ある動作の前の食材と後の食材を別のものとして区別し 、後の参照においては、ど ちらであるかを明示する。

と「人参」を指定する。

























F-set
例) /玉ねぎ /F −−−−→ /野菜/F
F-set/人参/F −−−−→ /野菜/F

3. 3. 4 同一の道具 (T-eq)・道具の一部 (T-part-of)
すでに登場した道具と同一の物体を指している単語同志を関連付ける。たとえば「蓋をして１０分煮込みます。蓋を外してさらに煮詰めます」の場合、蓋はど ちらも同一物体と考えられるので、以下のようにする。

















T-eq
例) /蓋/T −−−→ /蓋/T

表 3 フローグラフコーパスの 1 レシピあたりの諸元
出典

文数 レシピ固有表現数 (葉の数, 中間ノード 数)

単語数

無作為 (200 レシピ )6.51

36.34 ( 13.91,

22.43)

118.65 180.51

肉じゃが (66 レシピ )6.91

48.05 ( 22.12,

25.92)

132.95 198.70

以前に登場した道具の一部を指していると判断できる場合、
たとえば「圧力鍋で煮ます。１０分たったら蓋を外し 」の場合、「蓋」は「圧力鍋」の蓋であると考えられるため、「蓋」の『道具の一部 (T-part-of) 』に「圧力鍋」を指定する。

















T-part-of例) /圧力鍋/T −−−−−−−→ /蓋/T

文字数

ど 多様なレシピが含まれているため、レシピテキストの記述の偏りは少ない。

4. フローグラフの生成
この章では我々の提案するフローグラフの生成法を説明する。
我々の手法は、Mori ら [8] などの方法で、固有表現が抽出され3. 3. 5 同一の動作 (A-eq)

グラフの頂点がすでに得られていると仮定する。この状態で 、実際には一度しか行わない動作が 、文中では複数回記述され辺を生成した後にラベリングするという 2 段階の処理でフローる場合がある。たとえば「玉葱1 を みじん切り2 します。先ほどグラフである DAG を生成する。

切3った 玉葱4 を」の場合、後者の「切3 」は前者の「みじん切り2 」

フローグラフの辺の生成は 、MST を使用して木を生成したを指示しているにすぎず、実際には行わなくてよい。このよう後に、さらに有用な辺を追加するという方法を取る。通常 MSTな場合に、両固有表現を『同一の動作 (A-eq) 』によって関連づは係り受け解析に使われており、対象となるのは 1 文のみであけ、実際に行う動作と行わない動作を区別する。この例の場合る。今回我々は MST を使った解析を、1 文ではなく、複数のには、共参照も含めて以下のような部分グラフになる。

文からなるレシピテキスト全体に適用し 、グラフを生成する。


















































d-obj
例) /玉葱1 /F −−−−→ /みじん 切り2 /Ac
d-obj/玉葱4 /F −−−−→ /切3 /Ac

A-eq/みじん 切り2 /Ac −−−→ /切3 /Ac
F-eq/玉葱1 /F −−−→ /玉葱4 /F

第 2. 節で述べたように、MST は大きなグラフであっても遷移ベースのアプローチより頑健であるという特徴を持つ。我々は文章全体を解析するので、頂点の数は一般の係り受け解析の場合よりも多くなると考えられる。したがって、グラフの大きさに対して頑健なグラフベースのアプローチを採用する。

4. 1 MST による木の生成
MST による解析では 、辺のスコアの合計を最大化させるよ

上述の関係は『調理者の動作 (Ac) 』だけでなく、『食材の動作 (Af) 』にも発生する。たとえば『水を沸騰させる。沸騰したら…』の場合、以下のようになる。

うな木を解析結果として出力する。レシピテキストから抽出された頂点の集合を V = {v1 , v2 , . . . , v|V | } 、V より生成され









うる全域木全体の集合を G とする。さらに 、2 つの頂点 vi と









vj を受け取って実数値のスコアを返す関数 Score(vi , vj ) の存

A-eq
例) /沸騰 させ/Ac −−−→ /沸騰/Af在を仮定する。このスコア関数は 、vi を始点とし vj を終点と

3. 3. 6 動作を行うタイミング (V-tm)
動作を行うタイミングは調理を行う上で重要な指示情報であり、「○○したら」「○○するまで」「○○しないように」といった記述で表現される。たとえば「 煮立ってきたら灰汁を取り」の場合は以下のようにする。

















V-tm
例) /煮立/Af −−−−→ /取/Ac(vi ,vj )∈G

その他のすべての修飾関係はこの関係によって記述される。






























other-mod
例) /四つ切/Sf −−−−−−−−→ /する/Ac
other-mod
例) /45 分/D −−−−−−−−→ /焼/Ac

ありうる全ての辺のスコアリングをした状態で 、MST を使った木の生成は、辺のスコアの合計値を最大にするような全域木を求める問題として以下のように定式化する:
9
8
=
< X
Ĝ = argmax
Score(vi , vj ):;G∈G

3. 3. 7 その他の修飾語句 (other-mod)
たとえば次のようなものがある。

する有向辺を作る場合の尤度を表現している。このようにして

3. 4 コ ー パ ス
コ ーパ スの 統 計 情 報を 表 3 に 示す。Mori ら [3] は Cook-

この問題は Chu-Liu-Edmonds のアルゴ リズム [15] [16] を使えば解けることが知られている。
我々はスコア関数 Score(vi , vj ) を確率を使って次のように定義する。

Score(vi , vj ) =exp{Θ · f eat(vi , vj )}X
exp{Θ · f eat(vi , w)}(1)w∈V \{vi }pad（ 注 1 ）からレ シピ を ランダ ムに 選び 、上述の 基準に 沿って

ここで、V 2 = V × V であり、Θ はあらかじめ学習された高次アノテーションを人手で行いコーパスを構築している。これら

元の重みベクトルであり、f eat(vi , vj ) は辺を高次元の特徴空のランダムに選ばれたレシピにはお菓子や肉じゃがの作り方な間に写像する関数である。スコア関数は頂点 vi から頂点 vj に辺を張る時の確率を周囲の単語、品詞、読み、固有表現、固有（ 注 1）：http://cookpad.com/ 2014 年 2 月 10 日アクセス.

表現タグなどから計算する。

1: G ← V の最大全域木
2: A ← 無閉路のまま G に追加できる辺の系列
3: A を Score に従って値の大きな順番にソート
4: n ← 0
5: for (v, w) ∈ A do
6:
7:
8:
9:

if Score(v, w) > P enalty(n) thenG ← G + {(v, w)}n←n+1
end if

図 5 コーパスからの分布と指数分布の比較

10: end for
11: return G

図 4 DAG 生成のアルゴ リズム

つ多いかを取り、縦軸に、その数だけ辺が追加されたレシピの数を全レシピ数で割って正規化したグラフである。このグラフ

我々は 対数線形モデ ル [17] を 使い 、正し い 辺の スコアがで き るだ け 高 くな る よ うに 、パ ラ メー タ Θ を 学 習 す る 。

{(Vt , vt , wt )}Tt=1 を T イン スタン スの学習セットとする。ここで、Vt は頂点の集合、(vt , wt ) は正解の辺である。このような学習セットが与えられたとき、パラメータ推定は以下の尤度関数を最大化するように行う:
8
9
>
>
>
>
>
>
T <
=
X
exp(Θ · f eat(vt , wt )CXlog
− kΘk2>>2
exp(Θ · f eat(vt , w)) >
>
>
t=1 >
:
;
w∈Vt \{vt }今回我々は DAG を扱っているため、1 つの頂点から辺が 2本以上出る場合がある。すなわち、V を頂点の集合、v を始点とすると、w と w0 という 2 つ頂点が v の終点として学習デー

は、コーパスから推定した、辺の追加に対する尤度を表現する。
図 5 から、指数分布は辺の追加具合をよくモデリングしていることが分かる。さらに、辺の追加数の尤度に指数分布を使うことによって、いかなる辺の数に対してもその尤度を与えることができる。

ξ の最適な値は MST におけるスコア関数に依存する。具体的な値は、削除補間と同様の方法を用いて推定する。

4. 3 辺のラベリング
前節までの手法で辺を生成した後に、各辺にラベルを付けてフローグラフを出力する。我々は、辺のラベリングの問題を多クラス分類問題と見なし 、サポートベクタマシン (SVM) を使用してラベリング行う。すなわち、入力のグラフの各辺に対し 、辺の素性から最適な辺のラベルを選ぶ問題と設定する。

4. 4 素性

タに存在する可能性がある。このような場合、我々は (V, v, w)

MST でのスコア関数の計算と辺のラベリング時に使用すると (V, v, w0 ) の両方を学習インスタンスとして追加する。係り素性を説明する。ど ちらの場合であっても、素性は 2 つの頂点

受け解析のように木を扱っている場合は、終点が 2 つあるよう

vi と vj の間に辺を張った場合の特徴を高次元の特徴ベクトル

な始点は存在しない。

として表現する。

4. 2 DAG の生成

単独の素性は以下の通りである。

DAG の生成は、図 4 に示すように、MST を用いて木を生成•

符号を含めた固有表現間の距離 j − i

した後、無閉路のまま追加できる辺をさらに追加することで行•

vi と vj が同じ文にあるかう。図 4 において、Score は MST を求める時に使用する辺の•vi と vj が同じ手順にあるか

スコア関数であり、P enalty(n) は n 本目の辺を追加する場合•

各 vi と vj の表記、固有表現タグのペナルティを返す関数である。アルゴ リズムから分かるよう•

各 vi と vj の前後を含む 3 単語に 、辺のスコアがペナルティを超えた場合に辺は追加される。
ペナルティ関数によって辺の追加が制限されつつ、MST では拾えなかったスコアの高い辺を追加することができる。
我々はペナルティ関数として以下の式を用いる:

P enalty(n) =

ξ
λe−λn

右辺の分母はパラメータを λ とする指数分布であり、分子の ξはスケーリングパラメータである。
ペナルティ関数の一部に指数分布を使うのは 、木から DAGになるときの辺の追加具合が指数分布で表現できると考えられさらに組み合わせ素性を下に示す。

•

vi の固有表現タグ ∧ vj の固有表現タグ ∧ vi と vj の間に動作があるか ∧ vi と vj が同じ手順にあるか•

vi の固有表現タグ ∧ vj の固有表現タグ ∧ vi と vj の間に動作があるか ∧ vi と vj の間に助詞があるか•

vi の固有表現タグ ∧ vj の固有表現タグ ∧ vi と vj が同じ手順にあるか ∧ vi の直後の動作•

vi の固有表現タグ ∧ vj の固有表現タグ ∧ vi と vj の間の助詞•

vi の表記 ∧ vj の表記 ∧ vj の固有表現タグ ∧ vi と vj がるからである。我々は表 3 のコーパスを使って、フローグラフ

同じ手順にあるかの辺の数が 、フローグラフの部分木の辺の数よりもどれくらい

ここで、∧ は素性の連結を表す。

多いのかを計算した。図 5 は、横軸に、レシピフローグラフの辺が同じフローグラフから作られる部分木の辺の数よりもいく表 6 1 レシピあたりの辺のラベル数

表 4 フローグラフの生成実験の結果
手法

適合率

再現率 F 値

辺のラベル

ルールベース (ラベルなし )

75.9

69.4

72.5

subj

2.15

提案手法

(ラベルなし )

80.9

75.8

78.3

d-obj

15.67

提案手法

(ラベルあり)

72.4

67.8

70.0

i-obj

7.22

F-comp0.65

T-comp

1.32

F-eq

3.15

F-part-of

2.37

提案法の有効性を示すために我々はレシピテキストから DAG

F-set

0.15

を生成する実験を行った。この節では実験方法を説明し 、結果

T-eq

0.44

を評価する。

5. 評 価 実 験

数

T-part-of

0.39

5. 1 実 験 設 定

A-eq

0.53

実験には第 3. 節で説明したフローグラフコーパスを実験に

V-tm

1.06

other-mod

3.54

合計

38.62

使用した。以下の実験では、コーパスの固有表現をそのまま使用して、辺の生成を行った。すなわち、グラフにおけるノード
はすべて正解のノード である。また、実験は 10 分割交差検定
によって行った。
ベースラインとして、Hamada ら [10] のルールに基づく手法
を我々のフローグラフの定義に読み直して実験した。Hamada

はグラフの形状推定の精度を向上することが重要であると考えられる。
自然言語処理の観点から、各言語現象がどの程度解決できてらのグラフの設計は我々のそれとは異なっている。この手法を、いるかを明らかにするために、辺のラベルごとにラベル推定ま我々のグラフの定義で置き換えると 、食材や調理器具など ので行った場合の詳細な結果を表 5 に示す。この表において、文ノードから、それらの直後の動作ノードに辺を張るということ

内の列は辺の両頂点のレシピ固有表現が同一文内にある場合のになる。この手法では辺が左から右へ張られるので、DAG で再現率であり、文外はこれらが異なる文に出現している場合のはなく木が生成される。また、辺のラベリングを行っていない

再現率である。また、総合は文内と文外を合わせた場合の再現ため、このベースラインとの比較は辺の生成までである。

率である。

評価基準は適合率と再現率の調和平均である F 値を使用し 、

表 5 の subj 、d-obj 、i-obj は 、言語現象としては 、述語項構

これらの値を辺の数に対して計算した。解析器が出力した辺の造に分類される。文外 i-obj を除いて、これらの精度は高い。つ数を Nsys 、正解の辺の数を Nref 、解析器の出力した辺と正解

まり、調理動作や食材動作と対象および方向の関係が高い精度の辺の共通の部分の数を Nint と書くと、適合率、再現率およで推定できていることがわかる。ただし 、方向がゼロ代名詞にび F 値はそれぞれ以下のように計算される。

なって明示されていない場合は困難である。文外の subj の推定

Nint
Nsys
Nint
再現率 =
Nref
2Nint
F値=
(Nref + Nsys )適合率 =精度は非常に高いが 、これは、subj が「〜を煮ます。温まったら」などのように、高頻度の一定の表現パターンに対応するからと考えられる。
その一方で、F-eq 、T/F-part-of や A-eq などの共参照に対応
する辺の精度が著しく低いことが分かる。これは、コーパスの量が少ないためこれらの辺の学習が満足にできていないためであ5. 2 結果と考察

ると考えられる。表 6 に 1 レシピあたりの辺のラベル数を示す。

表 4 に、既存手法 (ルールベース; Hamada ら [10] の再実装)

表 6 から分かるように、1 レシピあたりの F-eq 、T/F-part-of 、および提案手法によるグラフ形状の推定の精度、さらに、提案

A-eq の数は 1 を下回っているものもあり、かなり少ないと言手法においてラベル推定を含めた場合の精度を示す。なお、既える。そこでこれらの精度を上げるには、調理ド メインの辞書存手法ではラベルなしのグラフを提案しているので、ルールにを構築して素性に含めるなどをする必要があると考えられる。

よるラベル推定は行っていない。グラフ形状の推定において、とくに F-eq は 、具体的な食材名とその食材が属する集合の関既存手法と提案手法を比べると、提案手法のほうが高い精度を係を記述しているため、上位と下位の関係を表す辺になってい

実現していることがわかる。この結果から、我々の手法の有効る。したがって、そのような関係を記述したオントロジー [18]性が確認できる。学習には 180 レシピが用いているが 、これをなどの外部知識を活用することで精度が上がると期待できる。

増量することは比較的容易であることを考えると、機械学習に基づく方法は有望であるといえる。表から、ラベルの推定を含

6. ま と め

めると F 値は少々10%程度下がっていることがわかる。正解の本論文では、手続き文章をフローグラフ化するという自然言

辺に対しては、90%程度の精度でラベル推定が行えていること

語処理の研究として、1 文を木に変換するという係り受け解析を意味する。これらのことを考え合わせると、さらなる改善にを応用し 、文章全体をグラフに変換する手法を提案した。今回

表 5 フローグラフの推定結果における言語現象ごとの再現率
現象

ラベル

述語項

subj

84.2 ( 309/ 367) 93.5 ( 58/

文内

文外

構造

d-obj

90.4 (2684/2970) 54.3 ( 89/ 164) 88.5 (2773/3134)

i-obj

72.9 ( 902/1238) 45.1 ( 93/ 206) 68.9 ( 995/1440)

F-comp78.1 ( 100/ 128)

0.0 (

0/

1) 77.5 ( 100/ 129)

T-comp78.5 ( 205/ 261)

0.0 (

0/

2) 77.9 ( 205/ 263)

小計

84.6 (4200/4964) 55.2 (240/ 435) 80.0 (4440/5399)

共参照, F-eq

8.1 (

照応

41.7 ( 125/ 300) 29.3 ( 51/ 174) 37.1 ( 176/ 474)

F-part-of

その他

9/ 111) 23.2 (102/ 519) 17.6 ( 111/ 630)

F-set

0.0 (

0/

13)

5.9 (

1/

17)

3.3 (

1/

T-eq

33.3 (

7/

21)

4.5 (

3/

66) 11.5 (

10/

87)

T-part-of

4.3 (

2/

47)

6.5 (

2/

31)

5.1 (

4/

78)

A-eq

0.0 (

0/

6)

1.0 (

1/

99)

1.0 (

1/ 105)小計

28.7 ( 143/ 498) 17.7 (160/ 906) 21.6 ( 303/1404)

V-tm

30)

49.5 ( 104/ 210)

0.0 (

0/

2) 49.1 ( 104/ 212)

other-mod 56.0 ( 385/ 687)

4.8 (

1/

21) 54.5 ( 386/ 708)

小計

54.5 ( 489/ 897)

4.3 (

1/

23) 53.3 ( 490/ 920)

合計

76.0 (4832/6359) 27.3 (401/1364) 67.8 (5233/7723)

はレシピテキストを変換の対象とした。従来研究とは異なり、変換して出力されるフローグラフは DAG である。この DAG[8]は、レシピテキストの固有表現をノード とし 、述語項構造、共参照などの関係を辺とする。我々の提案手法による DAG の生
成は 、MST を使って木を生成したあと、さらに有用とおもわ[9]

れる辺を追加するというものである。比較実験の結果、我々の手法は従来のルールによる木の生成よりも高い精度となった。
取扱説明書など 、様々な手続き文書を検討した結果、頂点や[10]辺のラベルは異なるものの、内容をフローグラフとして表現可能であることが分かっている。本論文で提案するレシピテキス
トのフローグラフへの変換手法は、同様の手続き文書にも適用可能である。提案手法は、調理レシピを含め様々な手順書の知[11]的な検索や分析の実現に有用である。
文合計62) 85.5 ( 367/ 429)

献[1] Liping Wang, Qing Li, Na Li, Guozhu Dong, and Yu Yang.
Substructure similarity measurement in chinese recipes. In
Proceedings of the 17th international conference on World
Wide Web, pp. 978–988, 2008.
[2] 山肩洋子, 角所考, 美濃導彦. 調理コンテンツの自動作成のためのレシピテキストと調理観測映像の対応付け . 電子情報通信学会
論文誌, Vol. J90-DII, No. 10, pp. 2817–2829, 2007.
[3] Shinsuke Mori, Hirokuni Maeta, Yoko Yamakata, and Tetsuro Sasada. Flow graph corpus from recipe texts. In Proceedings of the Nineth International Conference on Language Resources and Evaluation, 2014.
[4] 森信介, 山肩洋子, 笹田鉄郎, 前田浩邦. レシピテキストのためのフローグラフの定義. 情報処理学会研究報告, 第 NL214 巻,
2013.
[5] 三浦宏一, 高野求, 浜田玲子, 井手一郎, 坂井修一, 田中英彦. 料
理映像の構造解析による調理手順との対応付け . 電子情報通信学会論文誌, Vol. J86-DII, No. 11, pp. 1647–1656, 2003.
[6] Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan
Hajič. Non-projective dependency parsing using spanning
tree algorithms. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods
in Natural Language Processing, pp. 523–530, 2005.
[7] Joakim Nivre and Jens Nilsson. Pseudo-projective dependency parsing. In Proceedings of the 43rd Annual Meeting

[12]

[13]

[14]

[15]

[16]

[17]

[18]

of the Association for Computational Linguistics, pp. 99–
106, 2005.
Shinsuke Mori, Tetsuro Sasada, Yoko Yamakata, andKoichiro Yoshino. A machine learning approach to recipe
text processing. In Proceedings of Cooking with Computer
workshop, 2012.
Yoshio Momouchi. Control structures for actions in procedural texts and pt-chart. In Proceedings of the Eighth International Conference on Computational Linguistics, pp.
108–114, 1980.
Reiko Hamada, Ichiro Ide, Shuichi Sakai, and Hidehiko
Tanaka. Structural analysis of cooking preparation steps
in japanese. In Proceedings of the fifth international workshop on Information retrieval with Asian languages, No. 8
in IRAL ’00, pp. 157–164, 2000.
Ryan McDonald and Fernando Pereira. Online learning ofapproximate dependency parsing algorithms. In Proceedings of the Eleventh European Chapter of the Association
for Computational Linguistics, pp. 81–88, 2006.
Kenji Sagae and Alon Lavie. A best-first probabilistic shiftreduce parser. In Proceedings of the 21th International Conference on Computational Linguistics, 2006.
Ryan McDonald and Joakim Nivre. Analyzing and integrating dependency parsers. Computational Linguistics, Vol. 37,
No. 4, pp. 197–230, 2011.
Daniel Flannery, Yusuke Miyao, Graham Neubig, and Shinsuke Mori. A pointwise approach to training dependency
parsers from partially annotated corpora. Journal of Natural Language Processing, Vol. 19, No. 3, 2012.
Yoeng-Jin Chu and Tseng-Hong Liu. On the shortest arborescence of a directed graph. Science Sinica, Vol. 14, pp.
1396–1400, 1965.
Jack Edmonds. Optimum branchings. Journal Research of
the National Bureau of Standards, Vol. 71B, pp. 233–240,
1967.
Vincent J. Della Pietra Adam L. Berger, Stephen A.
Della Pietra. A maximum entropy approach to natural language processing. Computational Linguistics, Vol. 22, No. 1,
1996.
土居洋子, 辻田美穂, 難波英嗣, 竹澤寿幸, 角谷和俊. 料理レシピと特許データベースからの料理オントロジーの構築. 電子情報通信学会技術研究会報告, 2014.