(57)【要約】【課題】計算コストを抑えて、組合せバンディット問題における、部分集合を選択する行動を決定することができる。【解決手段】サンプリング部Ｍ０３が、要素集合のうちの制約を満たす部分集合の集合である集合族を保持するＺＤＤと、後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、集合族に含まれる部分集合をサンプリングする。出力部Ｍ０１が、サンプリングされた部分集合を選択する行動を実行したときに観測されるコストを取得する。共起確率計算部Ｍ０４が、後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、要素のペア毎に、現時刻において要素のペアが共起する共起確率を計算する。主装置部Ｍ０２が、現時刻の共起確率と、取得されたコストとに基づいて、現時刻の各要素の損失を計算し、現時刻の各要素の重みと、現時刻の各要素の損失とに基づいて、次の時刻の各要素の重みを計算する。上記の各処理を、各時刻について繰り返す。【選択図】図５
2019003405.tif 000002
【特許請求の範囲】
【請求項１】
要素集合のうちの予め定められた制約を満たす部分集合の集合である集合族の入力を受け付ける入力部と、
前記入力部により入力を受け付けた前記集合族を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)であって、１つの根ノード及び２つの終端ノードを含むノード集合、並びに、枝集合により有向グラフとして定義されるゼロサプレス型二分決定グラフと、現時刻の各要素の重みとに基づいて、各ノードに対し、０−枝を辿って到達するノードの後ろ向き重みＢと、１−枝を辿って到達するノードの後ろ向き重みＢと、前記ノードが表す要素の重みとから得られる後ろ向き重みＢを計算し、
前記ゼロサプレス型二分決定グラフと、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、前記集合族に含まれる部分集合をサンプリングするサンプリング部と、
前記サンプリング部によってサンプリングされた部分集合を選択する行動を実行したときに観測されるコストを取得する出力部と、
前記ゼロサプレス型二分決定グラフと、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、前記要素のペア毎に、現時刻において前記要素のペアが共起する共起確率を計算する共起確率計算部と、
前記ゼロサプレス型二分決定グラフと、前記共起確率計算部によって計算された現時刻の共起確率と、前記出力部によって取得されたコストとに基づいて、現時刻の各要素の損失を計算し、現時刻の各要素の重みと、現時刻の各要素の損失とに基づいて、次の時刻の各要素の重みを計算する主装置部と、
を含み、
各時刻について、前記サンプリング部による選択、前記出力部により取得、前記共起確率計算部による計算、及び前記主装置部による計算を繰り返す
行動決定装置。
【請求項２】
前記共起確率計算部は、
前記ゼロサプレス型二分決定グラフと、現時刻の各要素の重みとに基づいて、各ノードに対し、前記ノードの前向き重みＦから得られる、０−枝を辿って到達するノードの前向き重みＦと、前記ノードの前向き重みＦ、及び前記ノードが表す要素の重みから得られる、１−枝を辿って到達するノードの前向き重みＦを計算し、
前記ゼロサプレス型二分決定グラフと、現時刻の各要素の重みと、各ノードに対する後ろ向き重みＢとに基づいて、各ノードに対し、前記ノードと前記ノードが表す要素とが共起する後ろ向き共起重みＣを計算し、各ノードに対し、前記ノードが表す要素とは異なる前記要素毎に、０−枝を辿って到達するノード及び前記要素の後ろ向き共起重みＣと、１−枝を辿って到達するノード及び前記要素の後ろ向き共起重みＣと、前記ノードが表す要素の重みとから得られる前記ノード及び前記要素の後ろ向き共起重みＣを計算し、
前記ゼロサプレス型二分決定グラフと、現時刻の各要素の重みと、各ノードに対する後ろ向き重みＢと、各ノードに対する前向き重みＦと、各ノードに対する前記要素毎の後ろ向き共起重みＣとに基づいて、前記要素のペア毎に、現時刻において前記要素のペアが共起する共起確率を計算する請求項１記載の行動決定装置。
【請求項３】
前記要素集合は、頂点集合及び辺集合で表されるネットワークにおける前記辺集合であり、
前記制約は、前記ネットワークにおける特定の二頂点ｓｔａｒｔ，ｇｏａｌを結ぶパスであるという制約である請求項１又は２記載の行動決定装置。
【請求項４】
前記主装置部は、更に、前記入力部により入力を受け付けた前記集合族を保持するゼロサプレス型二分決定グラフを構築する請求項１〜請求項３の何れか１項記載の行動決定装置。
【請求項５】
入力部が、要素集合のうちの予め定められた制約を満たす部分集合の集合である集合族の入力を受け付け、
サンプリング部が、前記入力部により入力を受け付けた前記集合族を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)であって、１つの根ノード及び２つの終端ノードを含むノード集合、並びに、枝集合により有向グラフとして定義されるゼロサプレス型二分決定グラフと、現時刻の各要素の重みとに基づいて、各ノードに対し、０−枝を辿って到達するノードの後ろ向き重みＢと、１−枝を辿って到達するノードの後ろ向き重みＢと、前記ノードが表す要素の重みとから得られる後ろ向き重みＢを計算し、
前記ゼロサプレス型二分決定グラフと、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、前記集合族に含まれる部分集合をサンプリングし、
出力部が、前記サンプリング部によってサンプリングされた部分集合を選択する行動を実行したときに観測されるコストを取得し、
共起確率計算部が、前記ゼロサプレス型二分決定グラフと、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、前記要素のペア毎に、現時刻において前記要素のペアが共起する共起確率を計算し、
主装置部が、前記ゼロサプレス型二分決定グラフと、前記共起確率計算部によって計算された現時刻の共起確率と、前記出力部によって取得されたコストとに基づいて、現時刻の各要素の損失を計算し、現時刻の各要素の重みと、現時刻の各要素の損失とに基づいて、次の時刻の各要素の重みを計算することを含み、
各時刻について、前記サンプリング部による選択、前記出力部により取得、前記共起確率計算部による計算、及び前記主装置部による計算を繰り返す
行動決定方法。
【請求項６】
前記共起確率計算部が計算することでは、
前記ゼロサプレス型二分決定グラフと、現時刻の各要素の重みとに基づいて、各ノードに対し、前記ノードの前向き重みＦから得られる、０−枝を辿って到達するノードの前向き重みＦと、前記ノードの前向き重みＦ、及び前記ノードが表す要素の重みから得られる、１−枝を辿って到達するノードの前向き重みＦを計算し、
前記ゼロサプレス型二分決定グラフと、現時刻の各要素の重みと、各ノードに対する後ろ向き重みＢとに基づいて、各ノードに対し、前記ノードと前記ノードが表す要素とが共起する後ろ向き共起重みＣを計算し、各ノードに対し、前記ノードが表す要素とは異なる前記要素毎に、０−枝を辿って到達するノード及び前記要素の後ろ向き共起重みＣと、１−枝を辿って到達するノード及び前記要素の後ろ向き共起重みＣと、前記ノードが表す要素の重みとから得られる前記ノード及び前記要素の後ろ向き共起重みＣを計算し、
前記ゼロサプレス型二分決定グラフと、現時刻の各要素の重みと、各ノードに対する後ろ向き重みＢと、各ノードに対する前向き重みＦと、各ノードに対する前記要素毎の後ろ向き共起重みＣとに基づいて、前記要素のペア毎に、現時刻において前記要素のペアが共起する共起確率を計算する請求項５記載の行動決定方法。
【請求項７】
前記要素集合は、頂点集合及び辺集合で表されるネットワークにおける前記辺集合であり、
前記制約は、前記ネットワークにおける特定の二頂点ｓｔａｒｔ，ｇｏａｌを結ぶパスであるという制約である請求項５又は６記載の行動決定方法。
【請求項８】
コンピュータを、請求項１〜請求項４の何れか１項記載の行動決定装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、行動決定装置、方法、及びプログラムに係り、特に、要素集合のうちの制約を満たす部分集合の集合である集合族から、部分集合を選択する行動を決定するための行動決定装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
組合せバンディット問題は、「ある集合と制約が与えられたもとで、限られた観測情報に基づいて制約を満たす部分集合を繰り返し選び、最終的な損失の合計を最小化する」という文脈で頻繁に現れる問題である。問題設定の詳細は後述のとおりである。
【０００３】
このような問題の一例として、あるネットワーク上の端末から別の端末へのデータ転送が繰り返し行われる時に、経由するサーバーをデータ転送のたびに適切に選ぶことで、転送にかかる合計時間を最小化する問題が挙げられる。但し、データを転送するたびに観測できる情報は、端末間でのデータ転送にかかった時間のみであるとする。このような問題設定においては、各サーバー間の通信の混雑度合いは時々刻々と不規則に変化するため、損失（すなわち各サーバー間での通信にかかる時間）が確率分布に従うという仮定を置かずに考える必要がある。この問題は、辺ごとのコストが時刻に応じて変化するグラフの上で、各時刻でコストが最小となるようなstartからgoalへの経路（パス）を探す問題として表現できる。簡単な場合の問題設定の概略図を図１から図３に示す。図１は、与えられたネットワークの例であり、startからgoalへのデータ転送を行う。また、経由可能なサーバーを繋ぐ回線が辺で表されており、1,...,5（図１の各辺の太字の数字）でラベル付されている。図２、図３はそれぞれ時刻t=1、2における送信コストを表す図であり、各辺の数字が、その辺を経由してデータを送るのにかかる時間を表す。従って、この場合はt=1では辺1、4を通り、t=2では辺2、3、4を通ってデータを送信することで、最適な累積送信コストを達成できる（太い辺が、各時刻における最適な送信経路を表す）。このような状況下でt = 1, 2,...と繰り返しパスを選ぶ際に、累積送信コストができるだけ小さくなるパスの選び方を決定する問題は、各時刻において、startとgoalを結ぶパスになるという制約のもとで、辺集合から適切な部分集合を逐次選択し、累積損失を最小化する問題となっている。すなわち、この問題はパス制約下での組合せバンディット問題として見ることができる。
【０００４】
上記のような逐次的にパスを選択する問題に対しては、非特許文献１のような計算技術が提案されており、より一般的な問題である組合せバンディット問題に対しては、非特許文献２のような計算技術が提案されている。上記の計算技術はいずれも、後述のリグレットや擬リグレットと呼ばれる評価指標が小さくなるように、各時刻での選択を行うことを目的としたものである。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】A. Gyorgy, T. Linder, G. Lugosi, and G. Ottucsak. The on-line shortest path problem under partial monitoring. Journal of Machine Learning Research, 8(Oct):2369-2403, 2007.
【非特許文献２】N. Cesa-Bianchi, and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404-1422, 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
組合せバンディット問題に対しては、上述のような計算技術が知られているが、それぞれ以下のような課題を抱えている。まず、非特許文献１の逐次的なパスの選択技術は、適用できるグラフが有向非巡回なグラフに限られている。一方で、現実に存在するネットワークなどをグラフで表現した場合、有向非巡回なグラフになるとは限らないため、非特許文献１の技術を適用できない問題も現実には多く存在する。また、非特許文献２の組合せバンディット問題に対する計算方法は、選択可能な部分集合（例えば、グラフ上の全てのパスの集合）の数に比例して、計算コストが増大するという課題を抱えている。例えば、グラフ上でパスを逐次的に選択する問題の場合、選択可能なパスの総数はもとのグラフのサイズに対して指数的に増加し得るため、上記の計算法を実世界におけるネットワーク等に適用することは現実的には不可能である。このような計算量における困難さのため、非特許文献２のような組合せバンディット問題に対する既存研究において、提案された計算法を実装し、現実に存在するようなネットワークに適用した結果を示したものは存在しない。
【０００７】
本発明は、上記問題点を解決するために成されたものであり、計算コストを抑えて、組合せバンディット問題における、部分集合を選択する行動を決定することができる行動決定装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、本発明に係る行動決定装置は、要素集合のうちの予め定められた制約を満たす部分集合の集合である集合族の入力を受け付ける入力部と、前記入力部により入力を受け付けた前記集合族を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)であって、１つの根ノード及び２つの終端ノードを含むノード集合、並びに、枝集合により有向グラフとして定義されるゼロサプレス型二分決定グラフと、現時刻の各要素の重みとに基づいて、各ノードに対し、０−枝を辿って到達するノードの後ろ向き重みＢと、１−枝を辿って到達するノードの後ろ向き重みＢと、前記ノードが表す要素の重みとから得られる後ろ向き重みＢを計算し、前記ゼロサプレス型二分決定グラフと、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、前記集合族に含まれる部分集合をサンプリングするサンプリング部と、前記サンプリング部によってサンプリングされた部分集合を選択する行動を実行したときに観測されるコストを取得する出力部と、前記ゼロサプレス型二分決定グラフと、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、前記要素のペア毎に、現時刻において前記要素のペアが共起する共起確率を計算する共起確率計算部と、前記ゼロサプレス型二分決定グラフと、前記共起確率計算部によって計算された現時刻の共起確率と、前記出力部によって取得されたコストとに基づいて、現時刻の各要素の損失を計算し、現時刻の各要素の重みと、現時刻の各要素の損失とに基づいて、次の時刻の各要素の重みを計算する主装置部と、を含み、各時刻について、前記サンプリング部による選択、前記出力部により取得、前記共起確率計算部による計算、及び前記主装置部による計算を繰り返す。
【０００９】
本発明に係る行動決定方法は、入力部が、要素集合のうちの予め定められた制約を満たす部分集合の集合である集合族の入力を受け付け、サンプリング部が、前記入力部により入力を受け付けた前記集合族を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)であって、１つの根ノード及び２つの終端ノードを含むノード集合、並びに、枝集合により有向グラフとして定義されるゼロサプレス型二分決定グラフと、現時刻の各要素の重みとに基づいて、各ノードに対し、０−枝を辿って到達するノードの後ろ向き重みＢと、１−枝を辿って到達するノードの後ろ向き重みＢと、前記ノードが表す要素の重みとから得られる後ろ向き重みＢを計算し、前記ゼロサプレス型二分決定グラフと、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、前記集合族に含まれる部分集合をサンプリングし、出力部が、前記サンプリング部によってサンプリングされた部分集合を選択する行動を実行したときに観測されるコストを取得し、共起確率計算部が、前記ゼロサプレス型二分決定グラフと、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、前記要素のペア毎に、現時刻において前記要素のペアが共起する共起確率を計算し、主装置部が、前記ゼロサプレス型二分決定グラフと、前記共起確率計算部によって計算された現時刻の共起確率と、前記出力部によって取得されたコストとに基づいて、現時刻の各要素の損失を計算し、現時刻の各要素の重みと、現時刻の各要素の損失とに基づいて、次の時刻の各要素の重みを計算することを含み、各時刻について、前記サンプリング部による選択、前記出力部により取得、前記共起確率計算部による計算、及び前記主装置部による計算を繰り返す。
【００１０】
本発明に係るプログラムは、コンピュータを、上記発明に係る行動決定装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１１】
本発明の行動決定装置、方法、及びプログラムによれば、要素集合のうちの予め定められた制約を満たす部分集合の集合である集合族を保持するゼロサプレス型二分決定グラフと、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、前記集合族に含まれる部分集合をサンプリングし、サンプリングされた部分集合を選択する行動を実行したときに観測されるコストを取得し、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、前記要素のペア毎に、現時刻において前記要素のペアが共起する共起確率を計算し、現時刻の共起確率と、取得されたコストとに基づいて、現時刻の各要素の損失を計算し、現時刻の各要素の重みと、現時刻の各要素の損失とに基づいて、次の時刻の各要素の重みを計算することを、各時刻について繰り返すことにより、計算コストを抑えて、組合せバンディット問題における、部分集合を選択する行動を決定することができる、という効果が得られる。
【図面の簡単な説明】
【００１２】
【図１】ネットワークの一例を示す図である。
【図２】ｔ＝１におけるネットワークのコストの一例を示す図である。
【図３】ｔ＝２におけるネットワークのコストの一例を示す図である。
【図４】ＺＤＤの一例を示す図である。
【図５】本発明の実施の形態に係る行動決定装置の構成を示すブロック図である。
【図６】本発明の実施の形態に係る行動決定装置における入力手続きの処理ルーチンを示すフローチャートである。
【図７】本発明の実施の形態に係る行動決定装置におけるｔ＝１の行動決定処理ルーチンを示すフローチャートである。
【図８】本発明の実施の形態に係る行動決定装置におけるｔ＝２以降の行動決定処理ルーチンを示すフローチャートである。
【図９】後ろ向き重みBを計算する手続きを説明したAlgorithmの一例を示す図である。
【図１０】前向き重みFを計算する手続きを説明したAlgorithmの一例を示す図である。
【図１１】部分集合をサンプリングする手続きを説明したAlgorithmの一例を示す図である。
【図１２】共起後ろ向き共起重みCを計算する手続きを説明したAlgorithmの一例を示す図である。
【図１３】共起確率Pi,jを計算する手続きを説明したAlgorithmの一例を示す図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１４】
＜本発明の実施の形態に係る概要＞
まず、本発明の実施の形態における概要を説明する。
【００１５】
本発明の実施の形態では、既存技術を適用できないような規模の組合せバンディット問題に対し、既存技術と同等のリグレットや擬リグレットを達成する選択を可能とする計算技術を用いる。既存技術の問題点は、計算時間が制約を満たす集合のサイズに比例してしまうために、膨大な計算コストを必要とするところにある。そこで本発明の実施の形態では、制約を満たす集合を簡潔に保持することのできるゼロサプレス型二分決定グラフ（ZDD）を用いる。ZDDは、多様な制約に対し、その制約を満たす集合族を有向非巡回なグラフとして圧縮して保持するデータ構造である。このZDDを用いることで、もとの制約を満たす集合の上での組合せバンディット問題は、ZDD上でパスを繰り返し計算する問題に帰着することができる。ZDDの構築法としては非特許文献３のような方法が知られており、本発明の実施の形態でもこの方法を用いる。
【００１６】
[非特許文献３] J. Kawahara, T. Inoue, H. Iwasaki, and S. Minato. Frontier-based search for enumerating all constrained subgraphs with compressed representation. Technical report, TCS-TR-A-14-76, Hokkaido University, 2014.
【００１７】
この方法によってZDDを効率的に構築できる選択肢の集合（集合族）
2019003405.tif 000003
の具体例としては、（有向非巡回とは限らない）グラフ上の制約によって
2019003405.tif 000004
が記述される場合であれば、以下のいずれかの制約によって記述される
2019003405.tif 000005
が挙げられる。
【００１８】
・特定の二頂点start、goal を結ぶパスであるという制約（ハミルトンパスも可）
・サイクル（閉路）であるという制約（ハミルトン閉路も可）
・木であるという制約（全域木も可）
・森であるという制約
・連結であるという制約
・クリーク（部分完全グラフ）であるという制約
【００１９】
なお、上記の制約に限定されるものではなく、ＺＤＤに使用される制約であれば、他の制約であってもよい。
【００２０】
また、上記の制約とは独立に「辺の数が一定数以上（または一定数以下）である」という制約を追加して得られる選択肢の集合（集合族）
2019003405.tif 000006
に対しても非特許文献３の方法によって効率的にZDDを構築できる。具体例としては、あるグラフとその上の特定の二頂点startからgoal が与えられた時に、
2019003405.tif 000007
が「startからgoalへのパスで、辺の数が5本以下のものの集合」のように記述される場合、非特許文献３の方法でZDDを効率的に構築できる。実用上、上記のような様々な問題においてZDDのサイズはもとの制約を満たす部分集合の総数に比べて十分小さくなるため、本発明の実施の形態の技術は、非特許文献２のような既存技術よりも少ない計算コストで、組合せバンディット問題を扱うことができる。また、ZDDは様々な組合せ的制約に対して構築することができるため、非特許文献１を適用できないような様々な問題を扱うことができる。具体的には非特許文献１が有効非巡回なグラフの上での逐次的なパスの計算にしか適用できないのに対し、本発明の実施の形態における手法は、上記のようなZDDを構築可能な制約によって与えられる選択肢の集合に対し適用可能である。また、パス以外の組合せ的構造（例えば、グラフ上の部分木や閉路など）を計算するような問題に対しても、本発明の実施の形態における手法を適用することができる。
【００２１】
＜本発明の実施の形態に係る手法の原理＞
次に、本発明の実施の形態における手法の原理を説明する。
【００２２】
2019003405.tif 000008
とし、ある要素の集合E = [d] と、その上での実行可能な部分集合の集合である集合族
2019003405.tif 000009
2019003405.tif 000010
が与えられたとする（但し、K は実行可能な行動の総数であり、2EはEの冪集合である）。今、プレイヤーと敵対者が存在する状況を考える。時刻t＝1，...，Tごとに、敵対者は損失ベクトル
2019003405.tif 000011
をプレイヤーに知られないように決定する。但し、
2019003405.tif 000012
は
2019003405.tif 000013
が各t∈[T] において成り立つように設定される。次にプレイヤーは一つの部分集合
2019003405.tif 000014
を、時刻tでのプレイヤーの行動として選択する。任意の
2019003405.tif 000015
に対し、ベクトル
2019003405.tif 000016
をXの指示ベクトルとして定義する。すなわち、
2019003405.tif 000017
の第j成分は、j∈Xであれば1であり、そうでなければ0となる。さらに、
2019003405.tif 000018
を
2019003405.tif 000019
のユークリッドノルムの値とし、
2019003405.tif 000020
と定義する。各時刻t において、プレイヤーは部分集合Xtを選択したことによるスカラー値のコスト
2019003405.tif 000021
のみを観測することができる。この時、プレイヤーの累積損失
2019003405.tif 000022
が出来るだけ小さくなるように、プレイヤーが各時刻の部分集合
2019003405.tif 000023
を選択するための手続きを考える問題を、組合せバンディット問題（より正確には、敵対的組合せバンディット問題）と呼ぶ。例えば、Eがネットワーク上の辺集合、
2019003405.tif 000024
が送信者から受信者への可能なパスの集合であった場合、データを繰り返し転送する際の累積送信時間を最小化する問題は、組合せバンディット問題として定式化できる。
【００２３】
組合せバンディット問題に対する計算技術の評価指標としては、以下のリグレットR(T)や擬リグレット
2019003405.tif 000025
が用いられる。
【００２４】
【数１】
2019003405.tif 000026
【００２５】
但し、擬リグレットの定義における期待値は、プレイヤーが部分集合Xtを選択する際の手続きとして乱択アルゴリズムを用いた場合のランダム性についてのものである。プレイヤーが選択を繰り返すにつれて、一般にリグレットや擬リグレットは増加する。その増加度合いをTに対して線形以下の値（√Tなど）に抑えることが、組合せバンディット問題に対する計算技術の目的であり、より増加度合いが抑えられているほど、優れた計算法となる。
【００２６】
本発明の実施の形態では、リグレットや擬リグレットを抑えつつ、効率的に各時刻の部分集合の選択を計算するための手法を用いる。この装置は実数αを入力として持ち、α=3を入力とすれば、高い確率でT2／3に比例するリグレットを達成し、α=2を入力とすることで√T に比例する擬リグレットを達成する。
【００２７】
まず、本発明の実施の形態で用いるZDDの性質について説明する。可能な部分集合の集合である集合族
2019003405.tif 000027
が与えられた時、それらを保持するためのZDDは頂点集合V = {0，1，2，...，|V|-１}と有向枝集合A⊆V×Vからなる非巡回有向グラフ
2019003405.tif 000028
として定義される。また、V はトポロジカル順序によって順序づけられている。すなわち、(u，v)∈ A という有向枝があるならば、必ずu > v が成り立つように半順序がつけられている。
【００２８】
2019003405.tif 000029
はただ一つの根r = ｜V｜−１∈Vと二つの終端0，1∈Vを持つ（各終端を1-終端、0-終端と呼ぶ）。終端以外の頂点v∈Vはlv∈Eによってラベルづけされており、v∈V＼｛0，1｝からは0-枝、1-枝と呼ばれる二本の枝が出ている。また、ラベルはv > u ⇒lv < lu が全てのu，v ∈V について成り立つように付けられている。以下では、b ∈｛0，1｝に対し、v∈V＼｛0，1｝から出るb-枝をav,bと書き、v∈V＼｛0，1｝からb-枝を辿って到達する頂点をcv、bと書く。
【００２９】
任意の二頂点v，u ∈ V に対し、
2019003405.tif 000030
を
2019003405.tif 000031
上のvからu への有向パスの集合とし、その中の要素、すなわちパスを成す有向枝集合を
2019003405.tif 000032
と書く。また、
2019003405.tif 000033
が与えられた時に、Eの部分集合X(R) を
2019003405.tif 000034
と定義する。すなわち、X(R)はZDD上のパスRをたどる際に、1-枝の根のラベルを追加していくことで得られる集合である。このとき
2019003405.tif 000035
は
【００３０】
【数２】
2019003405.tif 000036
・・・（１）
【００３１】
を満たす。すなわち、ZDD
2019003405.tif 000037
は
2019003405.tif 000038
をrから1-終端への有向パスの集合として保持する。
【００３２】
図１のすべてのstart からgoal へのパスの集合
2019003405.tif 000039
を保持するZDD
2019003405.tif 000040
を図４に示す。図４のZDDにおいて、実線、破線の枝がそれぞれ1-枝、0-枝を表し、各ノードv∈V＼｛0，1｝にはvのラベルlv ∈Eが太字の数字で記されている。四角で囲まれた終端点がそれぞれ0-終端、1-終端である。まず、図１におけるパスの集合
2019003405.tif 000041
は、
2019003405.tif 000042
の４本のパスからなる。一方、ZDD 上での根から1-終端へのパスも４本存在し、X(R) の定義に従えば
2019003405.tif 000043
である。したがって、式(1) の関係が確かに成立している。
【００３３】
次に、装置の説明のための用語を導入する。d×d行列U、Qt、Ptを、後述のフローで定義される行列とし、これらの行列を共起確率行列と呼ぶ。それに伴って、この行列を計算する後述の装置を、共起確率計算部と呼ぶ。またλをUの最小非ゼロ固有値とし、
2019003405.tif 000044
を各時刻t に対して定義されるパラメータとする（これらのパラメータはそれぞれ、探索レート、学習レートとしばしば呼ばれる）。
【００３４】
＜本発明の実施の形態に係る行動決定装置の構成＞
次に、本発明の実施の形態に係る行動決定装置の構成について説明する。図５に示すように、本発明の実施の形態に係る行動決定装置１００は、ＣＰＵと、ＲＡＭと、後述する行動決定処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この行動決定装置１００は、機能的には図５に示すように入力部Ｍ００と、出力部Ｍ０１と、主装置部Ｍ０２と、サンプリング部Ｍ０３と、共起確率計算部Ｍ０４とを備えている。
【００３５】
入力部Ｍ００は、要素集合のうちの予め定められた制約を満たす部分集合の集合である集合族の入力を受け付ける。具体的には、入力部Ｍ００は、装置起動時に、パラメータと、制約を満たす部分集合の集合である集合族
2019003405.tif 000045
とを行動決定装置１００への入力として受け取り、主装置部Ｍ０２に伝達する。この時、
2019003405.tif 000046
は冪集合2Eの部分集合である集合族
2019003405.tif 000047
として陽な形式で受け取るか、あるいは、あるネットワークが与えられた上での「start からgoal へのパスを成す辺部分集合」のような、制約を表現した記述として受け取っても良い。その場合、
2019003405.tif 000048
を保持するZDD
2019003405.tif 000049
を、主装置部Ｍ０２において上記非特許文献３のような手法で構築する。または、すでに外部で構築されたZDD
2019003405.tif 000050
自体を入力として受け取ってもよく、その場合は主装置部Ｍ０２でのZDDの構築は不要となる。
【００３６】
出力部Ｍ０１は、サンプリング部Ｍ０３によってサンプリングされた部分集合を選択する行動を実行したときに観測されるコストを取得する。具体的には、出力部Ｍ０１は、各時刻tにおいて選択された部分集合
2019003405.tif 000051
を出力し、その部分集合を選択する行動を実行して観測されたコスト
2019003405.tif 000052
を主装置部Ｍ０２に伝える。この装置全体における出力は、出力部Ｍ０１で各時刻t∈ [T] において逐次的に出力される部分集合Xtである。
【００３７】
主装置部Ｍ０２は、ＺＤＤと、共起確率計算部Ｍ０４によって計算された現時刻の共起確率と、出力部Ｍ０１によって取得されたコストとに基づいて、現時刻の各要素の損失を計算し、現時刻の各要素の重みと、現時刻の各要素の損失とに基づいて、次の時刻の各要素の重みを計算する。
【００３８】
具体的には、主装置部Ｍ０２は、集合族
2019003405.tif 000053
の入力がZDDの形式でなかった場合のZDD
2019003405.tif 000054
の構築、パラメータγt、ηtの計算、重みベクトル
2019003405.tif 000055
の計算を行う。
【００３９】
サンプリング部Ｍ０３は、ＺＤＤと、現時刻の各要素の重みとに基づいて、各ノードに対し、０−枝を辿って到達するノードの後ろ向き重みＢと、１−枝を辿って到達するノードの後ろ向き重みＢと、当該ノードが表す要素の重みとから得られる後ろ向き重みＢを計算し、ＺＤＤと、各ノードに対して計算された後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、集合族に含まれる部分集合Xtをサンプリングし、Xtを出力部Ｍ０１と主装置部Ｍ０２に伝える。
【００４０】
共起確率計算部Ｍ０４は、ＺＤＤと、各ノードに対して計算された後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、要素のペア毎に、現時刻において要素のペアが共起する共起確率を計算する。
【００４１】
具体的には、共起確率計算部Ｍ０４は、ＺＤＤと、現時刻の各要素の重みとに基づいて、各ノードに対し、当該ノードの前向き重みＦから得られる、０−枝を辿って到達するノードの前向き重みＦと、当該ノードの前向き重みＦ、及び当該ノードが表す要素の重みから得られる、１−枝を辿って到達するノードの前向き重みＦを計算する。また、共起確率計算部Ｍ０４は、ＺＤＤと、現時刻の各要素の重みと、各ノードに対する後ろ向き重みＢとに基づいて、各ノードに対し、当該ノードと当該ノードが表す要素とが共起する後ろ向き共起重みＣを計算し、各ノードに対し、当該ノードが表す要素とは異なる要素毎に、０−枝を辿って到達するノード及び当該要素の後ろ向き共起重みＣと、１−枝を辿って到達するノード及び当該要素の後ろ向き共起重みＣと、当該ノードが表す要素の重みとから得られる当該ノード及び当該要素の後ろ向き共起重みＣを計算する。また、共起確率計算部Ｍ０４は、ＺＤＤと、現時刻の各要素の重みと、各ノードに対する後ろ向き重みＢと、各ノードに対する前向き重みＦと、各ノードに対する要素毎の後ろ向き共起重みＣとに基づいて、要素のペア毎に、現時刻において当該要素のペアが共起する共起確率を計算し、共起確率行列Ptを、主装置部Ｍ０２に伝える。
【００４２】
また、行動決定装置１００は、各時刻について、サンプリング部Ｍ０３、出力部Ｍ０１、共起確率計算部Ｍ０４、及び主装置部Ｍ０２の各処理を繰り返すことにより、各時刻ｔの部分集合Xtを出力する。
【００４３】
＜本発明の実施の形態に係る行動決定装置の作用＞
次に、本発明の実施の形態に係る行動決定装置１００の作用について説明する。まず、図６に示すように、ステップＳ００で、行動決定装置１００が動作を開始した際の入力を入力部Ｍ００で受け取る。受け取る入力はαと
2019003405.tif 000056
であり、これらは主装置部Ｍ０２に伝達される。
【００４４】
次に、行動決定装置１００上で実行される行動決定処理ルーチンを図７、図８のフローチャートを用いて説明する。行動決定処理ルーチンは時刻t=1，2，...，Tに対して繰り返し動作するものであるが、t=1において後述のAlgorithm1によって計算される後ろ向き重みBと、共起確率計算部Ｍ０４で計算される共起確率行列Uは、t=2以降でも使用するため、これらの値はt=1での処理の中で保存する必要がある。したがって、t=1での行動決定処理ルーチンとt=2以降の行動決定処理ルーチンは異なるものとなる。
【００４５】
次に、t=1での行動決定処理ルーチンを、図７を用いて説明する。
【００４６】
ステップＳ０１では、アルゴリズムを開始した際に必要な初期化を主装置部Ｍ０２で行う。具体的には、入力部Ｍ００から受け取った集合族
2019003405.tif 000057
がZDDの形式でなかった場合のZDD
2019003405.tif 000058
の構築を行い、サンプリング部Ｍ０３と共起確率計算部Ｍ０４に
2019003405.tif 000059
を伝達、保存する。さらに、各要素の重みを表す重みベクトル
2019003405.tif 000060
を生成し、行動決定装置１００の入力として受け取ったαを用いてγ1の計算を行う。この時、αの値は主装置部Ｍ０２に保存し、以降のγt、ηtの計算に用いる。
【００４７】
ステップＳ０２では、サンプリング部Ｍ０３が主装置部Ｍ０２から各要素の重みを表す重みベクトル
2019003405.tif 000061
を受け取り、Algorithm 1 を用いてt = 1 での後ろ向き重みBを計算し、サンプリング部Ｍ０３に保存しておく。また、Bは後ろ向き重み共起確率計算部Ｍ０４にも伝える。以下、t=1の場合の後ろ向き重みであることを明記するために、
2019003405.tif 000062
という記法を用いる。
【００４８】
ステップＳ０３では、サンプリング部Ｍ０３で
2019003405.tif 000063
をAlgorithm 3に入力してサンプリングを行い、得られた部分集合の選択
2019003405.tif 000064
を出力部Ｍ０１と主装置部Ｍ０２に伝える。
【００４９】
ステップＳ０４では、出力部Ｍ０１で部分集合X1を出力し、部分集合X1を選択する行動を実行した結果として観測されるコスト
2019003405.tif 000065
を取得し、主装置部Ｍ０２に伝達、保存する。
【００５０】
ステップＳ０５では共起確率行列Uの計算を行う。このステップでは、まず共起確率計算部Ｍ０４は主装置部Ｍ０２から各要素の重みを表す重みベクトル
2019003405.tif 000066
を受け取り、Algorithm2を用いて前向き重みFを計算する。さらに、サンプリング部Ｍ０３から受け取った
2019003405.tif 000067
をAlgorithm 4に入力して後ろ向き共起重みCを計算する。最後にAlgorithm 5に
2019003405.tif 000068
を入力することで、全ての
2019003405.tif 000069
の組に対して共起確率Pi、jを計算し、共起確率Pi、jをi、j成分にもつ共起確率行列Uを得る。この行列Uは主装置部Ｍ０２に転送される他、共起確率計算部Ｍ０４にも保存される。
【００５１】
ステップＳ０６では、主装置部Ｍ０２で次時刻についての各要素の重みを表す重みベクトル
2019003405.tif 000070
を計算する。具体的な手順としては、まずベクトル
2019003405.tif 000071
を計算する。但し、Ｕ+はＵの擬似逆行列である。次に、行列Ｕの最小固有値λを計算し、それを用いて、η1、η2を計算する。この時、λの値は主装置部Ｍ０２に保存し、ｔ≧２以降もηtが計算できるようにしておく。次に、各i ∈ Eに対し、要素iの重み
2019003405.tif 000072
を計算し、
2019003405.tif 000073
を第i成分に持つ重みベクトルを
2019003405.tif 000074
とする。但し、
2019003405.tif 000075
は
2019003405.tif 000076
の第i成分である。以上で、ｔ＝１における行動決定処理ルーチンが終了する。
【００５２】
次に時刻t (t≧2)における行動決定処理ルーチンを、図８を用いて説明する。ここで、各要素の重みを表す重みベクトル
2019003405.tif 000077
は時刻ｔ−１において主装置部Ｍ０２で計算されている。加えて、主装置部Ｍ０２にはα、λの値が保存されているため、任意の自然数tに対しγt、ηtの計算が可能である。また、サンプリング部Ｍ０３と共起確率計算部Ｍ０４はZDD
2019003405.tif 000078
をすでに保持している。さらに、サンプリング部Ｍ０３にはt=1での後ろ向き重み
2019003405.tif 000079
も保存されており、共起確率計算部Ｍ０４には共起確率行列Ｕが保存されている。
【００５３】
ステップＳ１１では、主装置部Ｍ０２でγtの計算を行う。
【００５４】
ステップＳ１２では、サンプリング部Ｍ０３が主装置部Ｍ０２から
2019003405.tif 000080
を受け取り、
2019003405.tif 000081
を入力とするAlgorithm 1 を用いて後ろ向き重みBを計算する。BはステップＳ１３においてサンプリング部Ｍ０３で用いる他、ステップＳ１５において共起確率計算部Ｍ０４で用いられるため、Bは共起確率計算部Ｍ０４にも転送しておく。ステップＳ１３では、以下の（１）、（２）のいずれかを行うことで部分集合Xtのサンプリングを行う。
【００５５】
（１）確率１−γtで、Algorithm 3 に
2019003405.tif 000082
を入力し、部分集合Xtをサンプリングする。
【００５６】
（２） 確率γtで、Algorithm 3 に
2019003405.tif 000083
を入力し、部分集合Xtをサンプリングする。
【００５７】
サンプリングで得られた部分集合
2019003405.tif 000084
は出力部Ｍ０１と主装置部Ｍ０２に伝える。
【００５８】
ステップＳ１４では、出力部Ｍ０１で部分集合Xtを出力し、部分集合Xtを選択する行動を実行した結果として観測されるコスト
2019003405.tif 000085
を取得し、主装置部Ｍ０２に伝達、保存する。
【００５９】
ステップＳ１５では共起確率行列Ptの計算を行う。このステップでは、まず共起確率計算部Ｍ０４は主装置部Ｍ０２から
2019003405.tif 000086
を受け取り、Algorithm 2を用いて前向き重みFを計算する。さらに、サンプリング部Ｍ０３から受け取った
2019003405.tif 000087
をAlgorithm 4 に入力して後ろ向き共起重みCを計算する。最後にAlgorithm5に
2019003405.tif 000088
を入力することで、全てのi，j∈ [d] の組に対して共起確率Pi,jを計算し、共起確率Pi,jをi、j成分にもつ共起確率行列を得る。この行列をQtと書く。このQtとt=1で保存されたUを用いることで、共起確率行列Ptを
2019003405.tif 000089
として得る。この行列Ptは主装置部Ｍ０２に転送される。
【００６０】
ステップＳ１６では、主装置部Ｍ０２で、次時刻についての重みベクトル
2019003405.tif 000090
を計算する。具体的な手順としては、まず、各要素の損失を表すベクトル
2019003405.tif 000091
を計算する（Pt+はPtの擬似逆行列）。次に、ηt、ηt+1を計算し、各i ∈ E に対し、要素iの重み
2019003405.tif 000092
を求め、
2019003405.tif 000093
を第i成分に持つ重みベクトルを
2019003405.tif 000094
とする。但し、要素iの損失
2019003405.tif 000095
は、ベクトル
2019003405.tif 000096
の第i成分である。
【００６１】
以上で、時刻tにおける行動決定処理ルーチンが終了し、ｔ＜Ｔであれば、続けて時刻t+1での処理が開始される。
【００６２】
＜Algorithmの処理内容＞
最後に、Algorithm 1-5の処理内容を説明する。これらは全て、数学的な手続きを記述したものである。Algorithm1，3は、サンプリング部Ｍ０３で部分集合Xtをサンプルするためのものである。本実施の形態では、部分集合Xtをサンプルするための手法として、ZDDの根ノードrから1-終端へのランダムウォークをAlgorithm3によって行う。すなわち、ZDDという有効非巡回なグラフの枝a∈Aを、各頂点v∈Vごとに定義された確率分布に従って辿る。このランダムウォークを行う際の頂点ごとの確率分布を計算するために、Algorithm 1 で計算される後ろ向き重み
2019003405.tif 000097
を用いる。Algorithm2，4，5は、共起確率計算部Ｍ０４で共起確率行列を計算するためのものである。共起確率行列は、各i、j成分が共起確率Pi,jで定義されるものであるため、Algorithm5によって各ｉ，j∈[d]の組に対して共起確率Pi,jの計算ができれば、共起確率行列が得られる。そのためには、Algorithm5の入力として、後ろ向き重みBに加え、前向き重み
2019003405.tif 000098
と後ろ向き共起重み
2019003405.tif 000099
が必要となる。これらの計算をそれぞれAlgorithm2，4で行っている。
【００６３】
次に、Algorithm 1-5の具体的な処理内容を説明する。
【００６４】
Algorithm 1では、図９に示すように、まず、１−終端ノードに対し、後ろ向き重みＢを１とし、その他のノードに対し、後ろ向き重みＢを０とする。そして、各ノードに対し、０−枝を辿って到達するノードの後ろ向き重みＢと、１−枝を辿って到達するノードの後ろ向き重みＢと、当該ノードが表す要素の重みとから得られる後ろ向き重みＢを計算する。
【００６５】
Algorithm 2では、図１０に示すように、まず、根ノードに対し、前向き重みＦを１とし、その他のノードに対し、前向き重みＦを０とする。そして、各ノードに対し、当該ノードの前向き重みＦを用いて、０−枝を辿って到達するノードの前向き重みＦを更新し、当該ノードの前向き重みＦ、及び当該ノードが表す要素の重みを用いて、１−枝を辿って到達するノードの前向き重みＦを更新する。これにより、各ノードの前向き重みＦを計算する。
【００６６】
Algorithm 3では、図１１に示すように、各ノードに対して、当該ノードの後ろ向き重みＢと、１−枝を辿って到達するノードの後ろ向き重みＢと、当該ノードが表す要素の重みを用いて、当該ノードが表す要素を選択する確率ｐを計算し、確率ｐに従って、当該ノードが表す要素を選択する。これにより、部分集合をサンプリングする。
【００６７】
Algorithm 4では、図１２に示すように、まず、各ノードに対し、０−枝を辿って到達するノードの後ろ向き重みＢと、当該ノードが表す要素の重みを用いて、当該ノードと当該ノードが表す要素とが共起する後ろ向き共起重みＣを計算する。そして、各ノードに対し、ノードが表す要素とは異なる要素毎に、０−枝を辿って到達するノード及び当該要素の後ろ向き共起重みＣと、１−枝を辿って到達するノード及び当該要素の後ろ向き共起重みＣと、当該ノードが表す要素の重みとを用いて、当該ノード及び当該要素の後ろ向き共起重みＣを計算する。
【００６８】
Algorithm 5では、図１３に示すように、各ノードに対し、当該ノードが表す要素同士からなるペアについての共起確率を、根ノードの後ろ向き重みＢと、１−枝を辿って到達するノードの後ろ向き重みＢと、当該ノードの前向き重みＦと、当該ノードが表す要素の重みとを用いて計算する。また、当該ノードが表す要素と、他の要素とのペアについて、当該ノードが表す要素同士からなるペアについての共起確率Ｐを、根ノードの後ろ向き重みＢと、１−枝を辿って到達するノード及び当該他の要素の後ろ向き共起重みＣと、当該ノードの前向き重みＦと、当該ノードが表す要素の重みとを用いて、確率ｐを計算し、当該ペアが共起する共起確率に確率ｐを加算する。
【００６９】
これにより、要素のペア毎に、現時刻において当該ペアが共起する共起確率を計算する。
【００７０】
以上説明したように、本発明の実施の形態に係る行動決定装置によれば、要素集合のうちの予め定められた制約を満たす部分集合の集合である集合族を保持するゼロサプレス型二分決定グラフと、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、集合族に含まれる部分集合をサンプリングし、サンプリングされた部分集合を選択する行動を実行したときに観測されるコストを取得し、各ノードに対して計算された前記後ろ向き重みＢと、現時刻の各要素の重みとに基づいて、前記要素のペア毎に、現時刻において前記要素のペアが共起する共起確率を計算し、現時刻の共起確率と、取得されたコストとに基づいて、現時刻の各要素の損失を計算し、現時刻の各要素の重みと、現時刻の各要素の損失とに基づいて、次の時刻の各要素の重みを計算することを、各時刻について繰り返すことにより、計算コストを抑えて、組合せバンディット問題における、部分集合を選択する行動を各時刻について決定することができる。
【００７１】
また、組合せ制約下での意思決定問題（組合せバンディット問題）に対し、リグレットや擬リグレットが抑えられるような行動の選択を行うことが可能となる。この性質を持つ既存の計算技術は膨大な計算コストが必要となるため、実装を伴った研究結果は今まで知られていなかった。本発明の実施の形態における計算技術は、ZDDを用いて効率的に実装することができるため、選択肢の集合が、上述したようなZDDを効率的に構築できる制約によって記述されるならば、既存技術が適用できないようなサイズの組合せバンディット問題に対して、本実施の形態の技術は効率的に動作する。その一例として、ネットワーク上で繰り返しデータ送信を送信する際に、累積送信時間ができるだけ短くなるように、経由するサーバーを適応的に選択することが可能となる。
【００７２】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【００７３】
１００ 行動決定装置
Ｍ００ 入力部
Ｍ０１ 出力部
Ｍ０２ 主装置部
Ｍ０３ サンプリング部
Ｍ０４ 共起確率計算部
【図１】
2019003405.tif 000100
【図２】
2019003405.tif 000101
【図３】
2019003405.tif 000102
【図４】
2019003405.tif 000103
【図５】
2019003405.tif 000104
【図６】
2019003405.tif 000105
【図７】
2019003405.tif 000106
【図８】
2019003405.tif 000107
【図９】
2019003405.tif 000108
【図１０】
2019003405.tif 000109
【図１１】
2019003405.tif 000110
【図１２】
2019003405.tif 000111
【図１３】
2019003405.tif 000112