言語処理学会 第21回年次大会 発表論文集 (2015年3月)

施設配置問題に基づく
同一料理のレシピ集合からの基本手順の抽出
瀧本 洋喜 ††

笹野 遼平 ‡

高村 大也 ‡奥村 学 ‡東京工業大学 総合理工学研究科, ‡ 東京工業大学 精密工学研究所

htakimoto@lr.pi.titech.ac.jp, {sasano, takamura, oku}@pi.titech.ac.jp1

はじめにら」のような，従属節に含まれる述語項構造は操作として扱わない．また，レシピ集合の基本手順とは，レWeb

上のレシピ投稿サイトには，多くのレシピが登録されている．2015 年 1 月時点でクックパッド1 には193万件，楽天レシピ2 には 92 万件のレシピが登録さ

シピのバリエーションに依らず出現する，料理を作成するための基礎的な手順であるとする．レシピ集合から基本手順を抽出する処理の概要を，図 1 に示す．

れており，これらのレシピを利用した種々の研究が行われている [1, 2, 3]．

基本手順を構成する基本操作は，元になったレシピ集合において，多くのレシピで類似した位置に出現す

これらのレシピ投稿サイトでは投稿ユーザそれぞれる操作だと考えられる．したがって，異なるレシピにが工夫を凝らした，同一料理の複数のレシピを入手で存在する二つの操作が同一の操作であるかを知るためきる．たとえば 2015 年 1 月現在，
「ハンバーグ」の検には，単純な操作間の関連度に加え，二つの操作がど索結果にはクックパッドでは 20784 件，楽天レシピでのレシピでどこに位置していたかを考慮することが重は 8245 件のレシピが該当する．それぞれのハンバー要であると考えられる．そこでまず，各レシピにおけグのレシピは，調理手順を一部簡略化した物であった

る出現位置を考慮したペアアライメントを行い，二つり，おろしポン酢のソースを使った物であったりと，のレシピ間の操作の対応付けを行う．ペアアライメン

異なる特徴を持ったレシピで，ユーザはこの大量のレトの詳細は 2.1 節で説明する．

シピの中から，自分の嗜好に合ったレシピを探すこと

次に，ペアアライメント結果を利用しながら，基本ができる．しかし，何千件ものレシピを全て比較し，操作の選択を行う．基本手順がレシピのバリエーショ

それぞれのレシピの特徴を掴むことは容易な作業ではンに依らず出現する手順であるならば，それを構成すない．

る基本操作もまた，多くのレシピに横断的に出現する

そこで本研究では，レシピは対象の料理の基本手と考えられる．つまり，選択されるべき基本操作とは，順と各レシピに特徴的な特徴手順によって構成されて多くのレシピの操作と高い関連度で対応付く操作であいると考え，レシピの特徴手順の特定に向けた第一段

る．この処理については 2.2 節で詳説する．

階の処理として，基本手順を抽出する手法を提案する．

選択された操作は，多くの場合違うレシピから選択

提案手法は，同一料理に対するレシピには多くのレシされるため，そのままでは順序を決定する事が出来なピに共通する手順が含まれるとの仮定に基づき，アラい．そこで，元のレシピ集合のアライメント結果に基イメントに基づいた施設配置問題を解くことにより，づき，操作の順序付けを行い，最終的な基本手順を生レシピ集合から基本手順の抽出を行う．

成する．順序付けの詳細は 2.3 節で説明する．

2

提案手法

2.1

操作の関連度によるペアアライメント

本研究ではレシピを，動詞とその動詞に係る語から{}なる述語項構造の集合 R = p1 , . . . , p|R| として考え対応付く操作のアライメントを行う．本研究では簡単

る．以下では一つの述語項構造を操作と呼ぶ．ただし，化のため，レシピ間で操作の対応付けが交差すること「お湯が湧いたらパスタを茹でる」の「お湯が湧いたはない，一つの操作は複数の操作と対応することはな

1 http://cookpad.com/
2 http://recipe.rakuten.co.jp/

レシピ集合に含まれたあらゆるレシピペアに対し，い，という二つの制約の下，式 (1) に示す目的関数を最大化するアライメントを二つのレシピ A と B の間

― 1092 ―Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

入力：レシピ集合

1. ペアアライメント

出力：基本手順2. 基本操作の選択

3. 操作の順序付け

図 1: レシピ集合から基本手順を抽出する処理のアライメントとした．式 (1) において，sim (pi , pj )病院や学校など，公共性の高い施設の配置を決定する

は操作 pi と pj の関連度を，RecipeA と RecipeB はレなどの問題に応用されている．

シピ A，B に含まれる操作集合を表している．

max.

この問題を今回の選択問題に置き換えると，なるべ∑1sim (pi , pj )|RecipeA | + |RecipeB | i,j

く少数の操作を選択することで，選択された操作が持(1)つ，他の操作との対応付きスコアの総和を最大化する問題として定式化できる．具体的には，高村ら [5] のpi ∈ RecipeA , pj ∈ RecipeB

施設配置問題による文章要約のモデル化を応用し，以また，本研究では操作間の関連度を式 (2) により計算する．ここで，vi は操作 pi に含まれる動詞，wi ={wi,1 , . . . , wi,k } は vi に係る k 個の語の集合である．

下のように定式化する．
∑max.
i,j eij zij

s.t.

それぞれを Mikolov ら [4] が提案した分散表現によってベクトル化し，動詞とそれ以外の語で個別に余弦類似度を計算し，二つを掛けあわせることで，操作間の関連度 sim (pi , pj ) を計算する．

sim(pi , pj )=cos(vi , vj )(∑1×max cos(wi,k , wj,l )l(k + l)k)∑+max cos(wi,k , wj,l )
(2)
l2.2

(3)

zij ≤ xi ;∑i xi ≤ K,∑i zij = 1;

∀i, j,∀j,(6)

zii = xi ;∀i,(7)xi ∈ {0, 1} ;∀i,(8)(5)zij ∈ {0, 1} ; ∀i, jeij

kaij

施設配置問題による基本操作選択(4)= aij × sim (si , sj ){1 : if si and sj are aligned=
0 :otherwise

(9)

(10)

(11)

この時 xi は操作 si が選択された場合 1，それ以外レシピ集合中の任意の二つのレシピの間で操作の対応付けが行われている場合に，他の多くの操作と高い関連度で対応付くような操作を冗長性無く取ってくることができれば，基本手順に必要な操作を選択することができると考えられる．この問題は，施設配置問題の一種だと考えることができる．広義の施設配置問題とは，施設の最適な配置を求める最適化問題の総称で，の場合は 0 となる変数，zij は操作 si によって sj が被覆されるか否かを示した変数である．eij は操作 siと sj の関連度であり，二つの操作が 2.1 節に示したアライメントにより対応付けられていれば関連度に 1を，対応付けられていなければ 0 を乗じて計算する．
すなわち，任意の二つの操作の対応付けを許すのではなく，ペアアライメントにおいて対応付いた操作だけを考慮する．

― 1093 ―Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

表 2: アライメント精度

2.1

図 2: アライメントに基づいた操作の並び順の推定

精度

再現率

F値

AER

0.359

0.577

0.435

0.395

節で説明した分散表現には gensim5 を用い，学習には 2012 年 7 月 5 日時点の楽天レシピの全調理手順データを単語分割した約 250 万文を使用した．

表 1: 実験に使用したカテゴリ一覧
オイル・塩系パスタ
チャーハン
リゾット・雑炊類
豚汁
シチュー
グラタン

ポテトサラダマドレーヌ
ハンバーグ
ロールキャベツ
コンソメスープ
チンジャオロース

3.2

アライメントの精度調査

アライメントの精度を調査するため，まず，表 1 に示すカテゴリそれぞれから無作為に 5 ペアを抽出し，6 を用い，5 人のアノテータにより人手で正解

Lancersのアライメントを付与した．続いて，2.1 節のアライ
2.3
2.2

メント結果と比較し，以下に示す，精度，再現率，F操作の順序付け

値，Alignment Error Rate (AER) により評価を行っ節に示した施設配置配置により選択される基本た．評価結果を表 2 に示す．

操作は，順序を持たない操作の集合であり，選択元のレシピも異なる場合が多いため，そのままでは順序を決定できない．そこで，元のレシピ集合のアライメン
ト結果に基づいて操作の並び順を決定し，順序を持った基本手順として扱えるようにする．

精度=

F値

=AER

=

図 2 にアライメントに基づいた並び順推定の例を示す．図 2 中の a-2 と b-2 が基本操作として選択された
場合，この二つは同じレシピに含まれる操作ではないので，これらの操作だけでは適切な順序が決定できない．しかし，b-2 が a-2 より前に出現する a-1 と対応付けられており，さらに，a-2 が b-2 より後に出現する b-3 と対応付けられていることを考慮することによ

(12)

(13)

(14)

A = システムの出力
S= 作業者 5 人中 4 人以上が一致して付与した正解

P= 作業者が 1 人でも付与した正解

3.3

り，a-2 は b-2 よりも後に順序付けられるべき操作である可能性が高いと推定できる．

|A ∩ P ||A ∩ S|, 再現率 =|A||S|
2 × 精度 × 再現率
精度 + 再現率|A ∩ P | + |A ∩ S||A| + |S|

基本手順生成手法の比較

続いて，生成された基本手順の良さを評価するため，表 1 に示すカテゴリそれぞれから無作為に 30 レシピ

本研究では，図 2 のようなアライメントに基づいたを抽出しテストセットとし，基本手順を生成した．ま並び順の推定を，選択された操作の全ペアに対して行た，比較対象として以下の二つの比較手法を用いた．

い，より多くの推定に合致するように操作の順序を決定する．

3

A 式 の値を常に として生成した手順
比較手法 B テストセット内の全てのレシピに対する比較手法

1式 (1) の平均値が最も高かったレシピ

実験

3.1

(11)

前者は提案手法における基本操作選択において，ペア実験設定

アライメント結果に依らず任意の二つの操作の対応付実験にはクックパッドのレシピの内，表 1 に示すカけを許したモデルになっている．また，評価は以下のテゴリに含まれるレシピをデータセットとして用いた．

三つの項目をそれぞれ四段階で評価した．

また，レシピを操作に分割するための述語項構造解析

重要操作の被覆度 元のレシピ集合の料理をつくるたには，KNP3 を使用した．この際，料理固有の表現にめに十分な操作が抽出されているか対応するため，難波らの公開する料理オントロジー4に含まれる単語を JUMAN の辞書に新たに登録した．

順序付けの妥当性 元のレシピ集合の料理を作るために操作が正しく並べられているか

3 http://nlp.ist.i.kyoto-u.ac.jp/index.php?KNP
4 http://www.ls.info.hiroshima-cu.ac.jp/cgi-

5 http://radimrehurek.com/gensim
6 http://www.lancers.jp/bin/cooking/wiki.cgi― 1094 ―Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

表 3: 生成手法による基本手順の良さの比較結果

表 4: 提案手法と比較手法 B/B' の比較結果

提案手法 比較手法 A 比較手法 B重要操作の被覆度
順序付けの妥当性
非標準手順の少なさ

3.23

3.37

3.27

2.82

2.60

3.38

2.63

2.55

3.35

平均長
平均長の半分

非標準手順の少なさ 元のレシピ集合の料理を作るた
めに標準でない操作が抽出されていないか

提案手法 比較手法 合計
39 (B)
1275 (B')
12の高い手順を抜き出したレシピ (比較手法 B') を生成し，これと提案手法を比較することにより評価した．
比較結果を表 4 に示す．比較のためレシピの長さをなお，平均値が最も高かったレシピ以外の二つの長さレシピ集合の平均長とし，同様の実験を行った場合の制約 K は，レシピ集合の平均操作長とした．

結果も示している．評価は 5 人のアノテータにより行

評価結果を表 3 に示す．重要操作の被覆度について

い，表中の数字は実験対象とした 12 カテゴリに対し，は手法間で差異は確認できなかったが，順序付けの妥

過半数の 3 人以上のアノテータが良いと答えたカテゴ

当性，および，非標準手順の少なさについては比較手リの数を表している．レシピの長さをレシピ集合の平法 B がもっとも高い評価となった．順序付けの妥当性均長とした場合，比較手法 B の方が良いと評価されたについては実際のレシピをそのまま使用している比較カテゴリは 9 カテゴリであったのに対し，レシピ集合

手法 B が高い評価となるのは妥当な結果であると考の平均長の半分とした場合は 5 カテゴリであった．こえられる．一方，非標準手順の少なさについては提案の結果から，提案手法は出力するレシピの長さの変化

手法でも比較手法 B と同程度の評価となることが期に対し比較的頑健であると考えられる．

待されたが，実際には比較手法 B の方が大幅に良い評価となった．この原因については，今後さらに調査を行う予定である．

4

おわりに

提案手法と比較手法 A の差異に着目すると，いず本研究では，レシピの特徴手順の特定に向けた第一れの実験においても表 3 に示した評価に大きな差は確段階の処理として，基本手順を抽出する手法を提案し認できないことから，生成された基本手順の良さは同た．同一料理のレシピには多くのレシピに共通する手程度であると考えられる．一方，提案手法において基順が含まれるとの仮定に基づき，まず，ペアアライメ

本手順生成の時間的ボトルネックとなる基本操作選択ントによりレシピ間の操作の対応付けを行い，続いて，の速度は，アライメントによる制約をかけた場合とかアライメント結果を利用し施設配置問題による基本操けない場合で大きく異なっており，提案手法の方が速作の選択と，選択された操作の順序付けを行うことで，度の面で優れていると言える．実際に，30 レシピを対基本手順の抽出を行った．今後の課題として，提案手象とした本稿の実験ではアライメントによる制約をか法を各レシピの特徴手順の特定に応用することで，特けることで 40 倍高速化しており，この差は対象のレ徴手順の抽出における提案手法の有用性の検証を行うシピの数が増えるにつれて大きくなると考えられる．

予定である．

続いて，提案手法と比較手法 B の差異について考える．比較手法 B と比べた場合の提案手法の特長の一つとして，出力するレシピの長さを自由に設定できるという点が挙げられる7 ．特に，スマートフォンやタブレット端末の普及に伴い，比較的小さな画面でレシピ等の情報を閲覧する需要は増えており，レシピの要点を短かくまとめたレシピ生成の需要は高まっていると考えられる．そこで，レシピの長さをレシピ集合の平均長の半分とした場合に提案手法により生成される基本手順を良さの評価を行った．比較対象として，上記の実験における比較手法 B で選択されたレシピから，レシピ長が同じになるようアラインメントスコア
7 比較手法 B についても，選択するレシピの長さに制限を設けることで，ある程度，レシピの長さを設定することが可能である．
しかし，実際には平均の半分以下の長さのレシピなどレシピ集合の平均長と比べ，長さが大きく異なるレシピの数は少数であった．

参考文献[1] 山肩洋子, 今堀慎治, 杉山祐一, 田中克己. レシピフローグラ
フを介したレシピ集合の要約と特徴抽出. 電子情報通信学会技術研究報告. DE, データ工学, Vol. 113, No. 214, pp. 4348,2013.
[2] 難波英嗣, 土居洋子, 辻田美穂. 複数料理レシピの自動要約. 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, Vol. 113, No. 338, pp. 3944, 2013.
[3] Shinsuke Mori, Hirokuni Maeta, Yoko Yamakata, and Tetsuro Sasada. Flow graph corpus from recipe texts. In Proc.
of LREC'14, pp. 23702377, 2014.
[4] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Je Dean. Distributed representations of words
and phrases and their compositionality. In Proc. ofNIPS'13, pp. 31113119, 2013.
[5] 高村大也, 奥村学. 施設配置問題による文書要約のモデル化. 人
工知能学会論文誌, Vol. 25, No. 1, pp. 174182, 2013.

― 1095 ―Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.