イジングマシンを用いた献立の表示順最適化
藤元彩花 (指導教員：工藤和恵)

1

はじめに

3

推薦サービスにおける推薦アイテムの表示順は, サー
ビスにおいて非常に重要なファクターである. 献立推薦サービスで表示順を決定する一つの方法としては,献立のスコアを定義して, そのスコアの降順に並べる,ということが挙げられる. しかし, この手法では, 特定の嗜好に偏った表示順で表示される恐れがある. このとき, ユーザは表示順下位のアイテムに興味がなくなってしまう可能性がある. これは, ユーザへの多様な推薦を阻害することに繋がるとも考えられる.
本研究では, イジングマシンを用いた献立推薦サー
ビスにおける献立の表示順をイジングマシンを用いて最適化することを目標とする. イジングマシンとは, 組み合わせ最適化問題の近似解を計算することに特化したコンピュータである. 問題を二値変数の二次多項式で表現することで, 目的関数を最小化するような解を得ることができる. スコアの良い献立は上位に, かつ,推薦される献立どうしの関係性を考慮し, 高い類似性がある献立どうしが隣り合うのを避けることで, 多様性を持った表示順を作成した.

2定式化

表示順最適化に使用する献立には, 以下の情報が含まれている.
・ 献立作成で出力されたハミルトニアン H0 の値
・ 献立のジャンル (和, 洋, 中華, 韓, エスニック)・ 献立に含まれる主菜のジャンル (肉, 魚, 野菜, 卵, その他)
・ 献立に含まれる主食のジャンル (ご飯, パン, 麺, その他)
・ 献立に含まれるレシピで使用される食材作成された複数の献立の表示順を作成するために, 二次割り当て問題と呼ばれる NP 困難な最適化問題に変換する. この最適化問題をイジングマシンで解けるようにするために, QUBO 形式のハミルトニアンで表現した. また, ハミルトニアンの立式には E-コマースサ
イトの商品の表示順最適化に関する先行研究 [4] を参考にした.
作成された献立の個数を N 個とし, 作成された献立
献立 1, 献立 2, ..., 献立 N を「献立の集合」と呼ぶ. 献立 i を表示順 j(j = 1, 2, ..., N ) に表示する時に 1, そうでない時に 0 をとる決定変数 xi,j を用いてハミルトニアンを以下のように設定する.

問題設定

本研究は, 献立推薦サービス作成プロジェクトで作成しているサービスの中に含まれる機能の一つである.
このサービスは, 主に二つの機能がある.
一つは, イジングマシンを用いて献立を作成する機能である. これは, ユーザからの好みの食材等を含む食材情報や献立の条件等の入力を受け取り, 入力した条件を満たすようなレシピの組合せ最適化問題として,イジングマシンを使用して 1 食分のレシピの集合を作成する機能である. レシピのデータは, 味の素株式会社による「レシピ大百科」[1] というレシピ情報サイトを, 食材のデータは, 文部科学省が出している「日本食品標準成分表」[2] を使用した. ここで作成された 1
食分のレシピの集合 (献立) は, 主に, 主食 1 個, 主菜0 − 1 個, 副菜 0 − 2 個, 汁物 0 − 1 個のレシピで構成されており, 入力した条件をできる限り満たしている
献立, 良い献立ほど目的関数であるハミルトニアン (以下, H0 ) の値が低くなる. また, イジングマシンは近似解を出力するため, 現実的な条件を入力することで複数の解を得ることができる.
もう一つは, イジングマシンを用いて献立の表示順を作成する機能である. 上記の献立作成で出力された複数の献立を, 良い献立は上位に, その上で, 多様性があるような表示順でサービスの結果を表示しているなら, ハミルトニアンの値が低くなるように立式した. この際に, 「良い献立」を「H0 の値が低い献立」, 加えて, 表示順における「多様性」を「隣り合う献立がさまざまな面で似ていないこと」, と定義した.
本研究では, この二つ目の機能について扱った.

H = H 1 + H2 + H3 + H 4(1)ハミルトニアンは, 大きく分けて 4 項で構成されている. 具体的な項の中身について説明する. ハイパーパラメータを α, β とおいた.

H1 = −NN ∑∑(N − j) (hmax − hi + li ) xi,j(2)i=1 j=1H2 =N ∑N ∑N ∑N∑(gi,i′ +αfi,i′ +pi,i′ +qi,i′ )dj,j ′ xi,j xi′ ,j ′i=1 i′ =1 j=1 j ′ =1(3)2(N)2NNN∑∑∑∑
H3 = β xi,j − 1 +xi,j − 1 
i=1j=1j=1i=1(4)H4 = −N ∑N∑(N − j)zi xi,j(5)i=1 j=1

式 (2) は H0 の値が低い献立を表示順上位に表示するように働くコスト項である. hi は, 献立 i の H0 の値, h max は献立の集合の中で一番大きい H0 の値を持
つ献立の H0 の値, li は献立 i に含まれるレシピ中に好きな食材が使用されているならば l, していないなら 0となる値である. 献立 i の H0 の値, hi が低い方が献立作成時のユーザの入力に沿った, つまり, ユーザにとっ1図 1: Amplify を使用して最適化した表示順て良い献立である. よって, 低い H0 の値を持つ, また好みの食材を含んだ献立の表示順が上位になるように働く項となっている.
式 (3) は献立同士の関係性を考慮することで表示順に多様性を生むように働くコスト項である. gi,i′ は献立 i と献立 i′ のジャンルが同じとき g, そうでない
とき 0 となる値, fi,i′ は献立 i と献立 i′ に含まれるレシピ内で使用されている食材によるコサイン類似度(0 < fi,i′ < 1), dj,j ′ は表示順 j と表示順 j ′ が隣り合っている, つまり j ′ = j + 1, もしくは j ′ = j − 1 となるとき 1, そうでないとき 0 ある. また, pi,i′ は, 献立
i と献立 i′ に含まれている主菜のカテゴリーが同じと
き p, そうでないとき 0 となる値, qi,i′ は献立 i と献立i′ に含まれている主食のカテゴリーが同じとき q, そうでないとき 0 となる値である. コサイン類似度は, 似ていると高くなる値である. 以上の 4 つの面で表示順が隣合うとペナルティとして (3) に加算されていくた
め, バラエティのある表示順を作成することに繋がる項になっている.
式 (4) は, one-hot 制約である. 献立 i には一つの表示順を割り当てる, かつ, 表示順 j には献立一つを割り当てる, という制約になっている. この制約を満たしている解を有効解とした.
式 (5) は, 直前の実行で表示されていない献立が表示順上位になるように働くコスト項である. zi は献立i が前 2 回の実行で表示されたことがあるとき 0, そうでないなら z となる値である. 献立に直前で表示されたことがあるレシピが含まれていないならば, 実行順上位であればあるほど (5) の値が小さくなる. これより, ユーザにとって新鮮な献立を表示順上位に推薦することが可能になる.
以上の 4 項の合計値 (1) が低いほど, 本研究で目指している表示順に近づくと考えられる. よって, イジングマシンを用いてこの値の最小値を求めることによって, 最適解を求める.

4

ハミルトニアン H0 の値の降順で並べた表示順と図1 を比較する. 降順での表示順では, 表示順が隣合わせでジャンルが同じ献立が 2 組, 主食のカテゴリーが同じ献立が 1 組, 主菜のカテゴリーが同じ献立が 5 組となる. また, 直近で表示されたことがない献立が 5 個あるのに対して, 上位 5 個の献立の中で直近で表示されたことがある献立が 3 個ある. 一方, 本研究で作成した表示順では, 全献立でジャンル, 主食のカテゴリーが同じものが隣り合わせになっていない. また, 主菜のカテゴリーが同じで隣り合っている献立の組は 3 組となった. 加えて, 上位 5 個の献立の中で直近で表示されたことがある献立は 1 個のみであることに加えて,好みの食材を含んだ献立が降順で並べた時よりも上位の表示順となっている.
以上より, 本研究で作成した献立表示順の方が多様性がある, ということが言える.

5

まとめ

本研究では, イジングマシンを用いた献立推薦サー
ビスにおける献立の表示順を最適化した. また, 本研究のハミルトニアンを応用して, 複数日の献立も作成することを今後行いたいと考えている.
謝辞 本研究は, 2022 年度未踏ターゲット事業の支援を受けています.

参考文献[1] AJINOMOTO Park, レシピ大百科（レシピ・料理）, https://park.ajinomoto.co.jp/recipe/(2022 年 8 月 29 日アクセス).
[2] 文 部 科 学 省, 日 本 食 品 標 準 成 分 表 2020 年
版（八訂）, https://www.mext.go.jp/a_menu/
syokuhinseibun/mext_01110.html (2022 年 8 月29 日アクセス).
[3] Fixstars, 量子アニーリングと共に進化するク
ラ ウ ド Fixstars Amplify, https://amplify.
fixstars.com/ (2022 年 8 月 29 日アクセス).

結果

上記のハミルトニアンを用いて, 計算を行なった. ソルバーは Fixstars Amplify AE [3] を用いた. 一例として, 10 個の献立の表示順を最適化した. また, 献立作成時に好みの食材として「＜魚類＞ （さけ・ます類） しろさけ 生」を入力した.
ハイパーパラメータは, α = 1, β = 60 とした. このとき, H1 = −29.170, H2 = 4.576, H3 = 0.00, H4 =−35.000, H = −59.595 となった.

[4] N. Nishimura, K. Tanahashi, K. Suganuma, M. J.
Miyama and M. Ohzeki, Item Listing Optimization for E-Commerce Websites Based on Diversity, Frontiers in Computer Science, 1, 2 (2019).

2