(57)【特許請求の範囲】
【請求項１】
施策に対して観測される効果が時間の経過とともに変化する場合における当該施策を決定する施策決定システムであって、
観測された効果に基づいて、乗算的に累積する当該効果を最大化するように、前記施策の実施比率を最適化する最適化部と、
最適化された実施比率および観測された効果に基づいて、各施策の信頼度を計算する信頼度計算部と、
前記信頼度がより高い施策を決定する施策決定部と、
決定された施策による効果を観測する観測部とを備え、
前記最適化部は、観測された効果に基づいて、過去の実施比率を更新し、
前記信頼度計算部は、更新された実施比率に基づいて前記各施策の信頼度を更新する
ことを特徴とする施策決定システム。
【請求項２】
最適化部は、オンライン凸最適化に基づいて実施比率を最適化し、
信頼度計算部は、エキスパートアルゴリズムに基づいて各施策の信頼度を計算する
請求項１記載の施策決定システム。
【請求項３】
最適化部は、オンライン凸最適化に基づいて実施比率を最適化し、
信頼度計算部は、バンデッドアルゴリズムに基づいて各施策の信頼度を計算する
請求項１記載の施策決定システム。
【請求項４】
最適化部は、観測された各資産の利率に基づいて、投資先への投資比率を最適化し、
信頼度計算部は、最適化された投資比率および観測された各資産の利率に基づいて、各投資先の信頼度を計算し、
施策決定部は、信頼度がより高い投資先への投資を施策として決定する
請求項１から請求項３のうちのいずれか１項に記載の施策決定システム。
【請求項５】
最適化部は、乗算的に累積する効果を、対数で表される加算的な効果に変形し、前記対数で表される効果を最大化するように施策の実施比率を最適化し、
信頼度計算部は、前記対数で表される効果に基づいて、各施策の信頼度を計算する
請求項１から請求項４のうちのいずれか１項に記載の施策決定システム。
【請求項６】
施策に対して観測される効果が時間の経過とともに変化する場合における当該施策を決定する施策決定方法であって、
コンピュータが、観測された効果に基づいて、乗算的に累積する当該効果を最大化するように、前記施策の実施比率を最適化し、
前記コンピュータが、最適化された実施比率および観測された効果に基づいて、各施策の信頼度を計算し、
前記コンピュータが、前記信頼度がより高い施策を決定し、
前記コンピュータが、決定された施策による効果を観測し、
前記コンピュータが、観測された効果に基づいて、過去の実施比率を更新し、
前記コンピュータが、更新された実施比率に基づいて、前記各施策の信頼度を更新し、
更新された実施比率および信頼度を用いて施策の決定が逐次繰り返される
ことを特徴とする施策決定方法。
【請求項７】
コンピュータが、オンライン凸最適化に基づいて実施比率を最適化し、
前記コンピュータが、エキスパートアルゴリズムに基づいて各施策の信頼度を計算する
請求項６記載の施策決定方法。
【請求項８】
コンピュータが、オンライン凸最適化に基づいて実施比率を最適化し、
前記コンピュータが、バンデッドアルゴリズムに基づいて各施策の信頼度を計算する
請求項６記載の施策決定方法。
【請求項９】
施策に対して観測される効果が時間の経過とともに変化する場合における当該施策を決定するコンピュータに適用される施策決定プログラムであって、
前記コンピュータに、
観測された効果に基づいて、乗算的に累積する当該効果を最大化するように、前記施策の実施比率を最適化する最適化処理、
最適化された実施比率および観測された効果に基づいて、各施策の信頼度を計算する信頼度計算処理、
前記信頼度がより高い施策を決定する施策決定処理、および、
決定された施策による効果を観測する観測処理を実行させ、
前記最適化処理で、観測された効果に基づいて、過去の実施比率を更新させ、
前記信頼度計算処理で、更新された実施比率に基づいて前記各施策の信頼度を更新させる
ための施策決定プログラム。
【請求項１０】
コンピュータに、
最適化処理で、オンライン凸最適化に基づいて実施比率を最適化させ、
信頼度計算処理で、エキスパートアルゴリズムに基づいて各施策の信頼度を計算させる
請求項９記載の施策決定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、逐次的に施策を決定する施策決定システム、施策決定方法および施策決定プログラムに関する。
【背景技術】
【０００２】
効果が不確定な施策を逐次的に繰り返し、最終的な報酬を最大化したい状況が存在する。そこで、最適な施策を逐次的に決定することで、報酬を最大化しようとする逐次的意思決定方法が各種提案されている。【０００３】
例えば、逐次的意思決定方法の一例として、エキスパートアルゴリズム（prediction with expert algorithm）が知られている。エキスパートアルゴリズムでは、数人の予測エキスパートが存在し、どのエキスパートを信用できるかは不明であるが、全てのエキスパートの予測結果は確認可能な状況を想定する。ここで、逐次的に出題される予測問題に対して、どのエキスパートを信用すべきかを逐次的に決定し、予測結果との誤差から、次に選択すべきエキスパートをさらに決定する。【０００４】
また、特許文献１には、逐次的意思決定方法の他の例として、多腕バンディット問題（バンデッドアルゴリズム）が記載されている。多腕バンディット問題は、事前に当たり易さが不明な複数のスロットマシンに対し、当たり易いスロットマシンを探す探索と、当たるスロットマシンを優先する活用とのトレードオフを考慮しながら適当な順番で逐次試行するような問題の総称である。多腕バンディット問題の考え方は、例えば、実際に広告を出してみないと効果が分からないＷｅｂ広告配信の最適化でも用いられている。【０００５】
また、このような問題に対して最適化を行う方法も各種提案されている。オンライン最適化は、各時刻ｔにおける利益関数ｆｔ（ｘ）の値が大きくなるように各時刻での戦略ｘｔを決定する方法である。なお、戦略ｘｔを決定する時点では、利益関数ｆｔは未知である。すなわち、オンライン最適化では、各時刻における戦略ｘｔを決定し、利益関数ｆｔを観測する処理が逐次的に繰り返される。ここで、繰り返しの回数をＴとすると、評価指標は、以下の式１で表される。なお、利益関数ｆｔへの仮定（凸性など）のもとで、有効なアルゴリズムが既知である。【０００６】
【数１】
0006977878.tif 000002
【０００７】
また、ケリー基準（Kelly’s criterion ）が、投資の分野において最適な投資比率を表す基準として知られており、投資先が一つで、利益の確率分布が単純で既知のときには計算可能であるとされている。なお、投資先が複数で確率分布が複雑な場合に対しても、最適性の指標は定義可能であるが、最適な投資比率を計算する効率的なアルゴリズムは知られていない。【０００８】
また、特許文献２には、将来発生することが予想される事象を、変化する現実の状況に対応して推定することでユーザの意志決定を支援する意思決定支援システムが記載されている。特許文献２に記載されたシステムでは、インターネット等を介して取得される情報を分析し、その結果に応じて事象因果関係モデルを逐次更新し、ユーザが意志決定を行う場面において、最新情報に基づく事象の予測結果を提供する。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特表２０１５−５１３１５４号公報
【特許文献２】特開２０１６−２０６９１４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述するエキスパートアルゴリズムでは、選択したエキスパートの予測結果と最適なエキスパートの予測結果との誤差が評価指標になることから、評価指標は加算的に算出される累積誤差になる。また、上述する多腕バンデッド問題も、利益が加算的に増加するモデルである。【００１１】
一方、施策の効果が時刻変化する状況において、施策の効果が加算的ではなく乗算的に利益に影響する場合がある。例えば、投資において、単位期間ごとに投資先の比率を決定して、将来（例えば、１０年後）の利益を最大化しようとする場合、施策（投資先）の効果（投資におけるリターン倍率）は、乗算的に利益に影響する。また、例えば、マーケティングにおいて、効果的なキャンペーンを探索しながら効率化し、顧客の数を最大化するような問題は、キャンペーンによる顧客間の広がり（口コミ等による広がり）を考慮すると、やはり乗算的に利益に影響する問題と言える。【００１２】
このような問題を一般化すると、意思決定（施策の決定）と、その結果の観測（施策の効果の観測）が複数回繰り返され、施策の効果が乗算的に観測される問題と言える。【００１３】
しかし、このような施策の効果が乗算的に利益に影響するような場合、一般的な方法で単純に期待値（平均値）を最大化しようとしても、最適化した結果が不合理になってしまう可能性がある。以下、具体例を挙げて、最適化した結果が不合理になる状況を説明する。【００１４】
今、二つの投資先Ａおよび投資先Ｂに投資をする状況を考える。投資先Ａについては、確率５０％で利益が１．３倍になり、確率５０％で利益が０．９倍になるとする。一方、投資先Ｂについては、確率５０％で利益が２．０倍になり、確率５０％で利益が０．４倍になるとする。平均利率を考えると、投資先Ａの平均利率は１．１倍であり、投資先Ｂの平均利率は、１．２倍である。平均利率で比較すると、投資先Ｂの方が優れているとも考えられる。【００１５】
一方、各投資先に全額投資し続ける状況を想定する。例えば、投資先Ｂに１００回投資し続けた場合、資産は０に収束する。すなわち、１００回の投資のうち、約５０回、利益が２．０倍になったとしても、約５０回、利益が０．４倍になるため、２．０５０×０．４５０＝（２．０×０．４）５０＝０．８５０≒０である。一方、投資先Ｂに１００回投資し続けた場合、資産は増加すると考えられる。すなわち、１００回の投資のうち、約５０回、利益が１．３倍になり、約５０回、利益が０．９倍になるため、１．３５０×０．９５０＝（１．３×０．９）５０＝１．１７５０≒２５００である。【００１６】
このように、期待値を評価指標とした場合、投資先Ｂへの投資が優れているとも考えられるが、現実的な感覚では、投資先Ａへの投資が優れているとも言える。したがって、単に期待値（平均値）を最大化する方法では、効果の結果が現実的に破綻してしまう可能性もある。【００１７】
特許文献２には、事象因果関係モデルを逐次更新して予測することは記載されているが、その具体的内容は開示されておらず、施策の効果が乗算的に利益に影響するような状況も想定されていない。【００１８】
そこで、本発明は、逐次実行される施策の効果が乗算的に影響するような状況において、最適化した結果が不合理になる状況を回避して、効果を最大化するような施策を決定できる施策決定システム、施策決定方法および施策決定プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
本発明による施策決定システムは、施策に対して観測される効果が時間の経過とともに変化する場合における、その施策を決定する施策決定システムであって、観測された効果に基づいて、乗算的に累積する効果を最大化するように、施策の実施比率を最適化する最適化部と、最適化された実施比率および観測された効果に基づいて、各施策の信頼度を計算する信頼度計算部と、信頼度がより高い施策を決定する施策決定部と、決定された施策による効果を観測する観測部とを備え、最適化部が、観測された効果に基づいて、過去の実施比率を更新し、信頼度計算部が、更新された実施比率に基づいて各施策の信頼度を更新することを特徴とする。【００２０】
本発明による施策決定方法は、施策に対して観測される効果が時間の経過とともに変化する場合におけるその施策を決定する施策決定方法であって、コンピュータが、観測された効果に基づいて、乗算的に累積するその効果を最大化するように、施策の実施比率を最適化し、コンピュータが、最適化された実施比率および観測された効果に基づいて、各施策の信頼度を計算し、コンピュータが、信頼度がより高い施策を決定し、コンピュータが、決定された施策による効果を観測し、コンピュータが、観測された効果に基づいて、過去の実施比率を更新し、コンピュータが、更新された実施比率に基づいて、各施策の信頼度を更新し、更新された実施比率および信頼度を用いて施策の決定が逐次繰り返されることを特徴とする。
【００２１】
本発明による施策決定プログラムは、施策に対して観測される効果が時間の経過とともに変化する場合における、その施策を決定するコンピュータに適用される施策決定プログラムであって、コンピュータに、観測された効果に基づいて、乗算的に累積する効果を最大化するように、施策の実施比率を最適化する最適化処理、最適化された実施比率および観測された効果に基づいて、各施策の信頼度を計算する信頼度計算処理、信頼度がより高い施策を決定する施策決定処理、および、決定された施策による効果を観測する観測処理を実行させ、最適化処理で、観測された効果に基づいて、過去の実施比率を更新させ、信頼度計算処理で、更新された実施比率に基づいて各施策の信頼度を更新させることを特徴とする。
【発明の効果】
【００２２】
本発明によれば、逐次実行される施策の効果が乗算的に影響するような状況において、最適化した結果が不合理になる状況を回避して、効果を最大化するような施策を決定できる。
【図面の簡単な説明】
【００２３】
【図１】本発明による施策決定システムの一実施形態を示すブロック図である。
【図２】施策決定処理の例を示す説明図である。
【図３】施策決定システムの動作例を示すフローチャートである。
【図４】タイプＡの場合に信頼度および実施比率を算出する処理の例を示すフローチャートである。
【図５】タイプＢの場合に信頼度および実施比率を算出する処理の例を示すフローチャートである。
【図６】本発明による施策決定システムの概要を示すブロック図である。
【図７】少なくとも１つの実施形態に係るコンピュータの構成を示す概略ブロック図である。
【発明を実施するための形態】
【００２４】
以下、本発明の実施形態を図面を参照して説明する。
【００２５】
図１は、本発明による施策決定システムの一実施形態を示すブロック図である。また、図２は、本発明で想定する施策決定処理の例を示す説明図である。本発明では、複数の施策の中から実行する施策を逐次決定し、決定した施策または決定した施策を含む全ての施策の効果を結果として観測する処理を繰り返す。また、以下の説明では、候補となる施策の数をｄで表わし、意思決定の回数をＴで表わす。
【００２６】
以下の説明では、施策の具体例として、複数の資産（投資先）への投資を想定する。このとき、観測される施策の効果が利率に相当する。この場合、ｄは、投資先の数を表し、Ｔはラウンド数（投資を繰り返す数）に相当する。
【００２７】
図２のフローチャートにおいて、まず、各ラウンドで、単一の資産（投資先）および投資比率が決定され、投資が行われる（ステップＳ１１）。例えば、投資比率をｘｔ＝（ｘｔ１，…，ｘｔｄ）∈［０，１］ｄと表わし、ｘｔｉが、ｉ番目の投資先への投資比率を表すとすると、ｘｔｉのいずれか１つがｘｔｉ≦１であり、それ以外は０である。
【００２８】
その後、各投資先に投資した場合の利率ｒｔ＝（ｒｔ１，…，ｒｔｄ）∈（−１，∞）ｄが観測される（ステップＳ１２）。なお、以下の説明では、全ての投資先の利率ｒｔが観測できる場合（以下、タイプＡと記すこともある。）と、投資した投資先の利率ｒｔのみ観測できる場合（以下、タイプＢと記すこともある。）について説明する。ここで、ｒｔｉは、ｉ番目の投資先の利率に対応する。
【００２９】
タイプＡが想定される状況の一例として、株式への投資を行う状況が考えられる。例えば、毎週月曜朝に、先週一週間の各株式の株価変動を観測し、自身の株式保有率を変更するような状況である。また、タイプＢが想定される状況の一例として、Ｗｅｂ広告の配置に対する効果や、ある研究への投資に対する効果などが挙げられる。
【００３０】
以下、ラウンド数Ｔを満たすまで、ステップＳ１１およびステップＳ１２の処理が繰り返される。
【００３１】
このように、施策の候補が複数存在する場合、施策を実施することで効果が観測されることになるが、これらの観測結果をすべて踏まえたうえで更なる施策の決定を繰り返すとすると、考慮すべき要素が膨大になるため、人手での実現は不可能である。そこで、以下に示す本発明の施策決定方法をコンピュータに実行させることで、現実的な時間で逐次施策を決定することが可能になる。
【００３２】
図１は、本実施形態の施策決定システムの構成例を示すブロック図である。本実施形態の施策決定システム１００は、入力部１０と、記憶部２０と、計算部３０と、出力部４０とを備えている。本実施形態では、施策に対する効果が時間の経過とともに変化する状況を想定する。例えば、投資の場面では、ある投資先ｉｔへの投資を施策として考えた場合、効果である利率ｒは、時間とともに変化する情報である。
【００３３】
入力部１０は、観測された効果を入力する。入力部１０は、例えば、ｔ回目までに観測された投資の効果として、利率ｒｔを入力する。ここで、入力部１０は、観測された効果を入力することから、決定された施策に基づいて実施した場合の効果を観測する観測部と言うことができる。
【００３４】
記憶部２０は、観測された投資の効果を記憶する。記憶部２０は、例えば、入力部１０に入力された効果を逐次記憶する。また、記憶部２０は、後述する計算部３０が算出した最適な実施比率ｘ（投資比率）および各施策（投資先への投資）の信頼度ｐを記憶してもよい。記憶部２０は、例えば、磁気ディスク等により実現される。
【００３５】
計算部３０は、初期化部３１と、最適化部３２と、信頼度計算部３３と、施策決定部３４とを含む。
【００３６】
初期化部３１は、後述する処理で用いられる最適な投資比率ｘ＝（ｘ１，ｘ２，…ｘｄ）および各資産（投資先）の信頼度ｐ＝（ｐ１，ｐ２，…ｐｄ）等を初期化する。各ｘｉ（０≦ｘｉ≦１）は、ｉ番目の資産に投資する場合の最適な投資比率（保有資産に対する割合）に対応する。また、各ｐｉ（０≦ｐｉ≦１）は、ｉ番目の資産（投資先）の信頼度に対応する確率ベクトル（ただし、ｐ１＋ｐ２＋…＋ｐｄ＝１）であり、各ラウンドにおいて確率ｐｉでｉ番目の資産が選択されることを示す。結果として、最も大きいｐｉに対応する資産（投資先）ｉが優先的に選択されることになる。
【００３７】
最適化部３２は、観測された効果に基づいて、乗算的に累積する効果を最大化するように、施策の実施比率を最適化する。具体的には、最適化部３２は、観測された各資産の過去の利率ｒに基づいて、乗算的に累積する効果を最大化するように、ある投資先ｉｔへの最適な投資比率ｘを計算する。
【００３８】
ここで、乗算的に累積する効果は、最終的な資産をＡＴとすると、以下に例示する式２のように表わすことができる。
【００３９】
【数２】
0006977878.tif 000003
【００４０】
ただし、上述するように、単純にＡＴの期待値を最大化しようとすると、最適化の結果が不合理な可能性（破綻してしまう可能性）も存在する。そこで、このような不合理の可能性を排除するため、ＡＴの対数ｌｏｇＡＴを最大化することを考える。すなわち、上記に例示する式２を、以下に例示する式３のように変形する。
【００４１】
【数３】
0006977878.tif 000004
【００４２】
ｌｏｇＡＴの期待値の方が、ＡＴの期待値よりも合理的な指標と言える。以下、その理由について、上述する二つの投資先Ａおよび投資先Ｂに投資をする状況を例に説明する。今、（Ｘｔ）Ｔｔ＝１＝（（Ｘｔ（１），Ｘｔ（２）））Ｔｔ＝１がベルヌーイ確率変数であり、Ｐｒｏｂ［Ｘｔ（１）＝１．３］＝Ｐｒｏｂ［Ｘｔ（１）＝０．９］＝１／２、および、Ｐｒｏｂ［Ｘｔ（２）＝２．０］＝Ｐｒｏｂ［Ｘｔ（１）＝０．５］＝１／２であるとする。また、ＸｔとＸｔ´は、ｔ≠ｔ´の独立した確率変数であるとする。ここで、Ｘｔ（１）とＸｔ（２）とが独立であるとは想定していない。
【００４３】
ここで、それぞれの最終的な資産ＡＴ（１）および資産ＡＴ（２）を、以下の式４および式５のように定義する。
【００４４】
【数４】
0006977878.tif 000005
【００４５】
期待値Ｅ［Ｘｔ（１）］＝１．１であり、期待値Ｅ［Ｘｔ（２）］＝１．２であるから、最終的な資産の期待値Ｅ［ＡＴ（１）］＝１．１Ｔ＜Ｅ［ＡＴ（２）］＝１．２Ｔである。これは、期待値に基づいて決定する場合、ＡＴ（１）よりもＡＴ（２）のほうが好ましいことを意味する。しかし、それぞれの確率を考慮すると、ｌｉｍＴ→∞ＡＴ（１）＝∞、ｌｉｍＴ→∞ＡＴ（２）＝０であることを示すことができる。
【００４６】
実際、以下に例示する式６が、独立同分布の確率変数の積である場合、以下に例示する式７が得られる。なお、式７における最後の等号は、大数の法則から得られる。
【００４７】
【数５】
0006977878.tif 000006
【００４８】
上記の式７に、上記の式４および式５を適用すると、以下に示す式８が得られる。
【００４９】
【数６】
0006977878.tif 000007
【００５０】
一般的に、上記に示す式４および式５が、独立同分布の確率変数の積である場合、以下の式９を満たす場合に限り、Ｅ［ｌｏｇＸ１（１）］＞Ｅ［ｌｏｇＸ１（２）］である。
【００５１】
【数７】
0006977878.tif 000008
【００５２】
以上の内容は、乗算的な（報酬の）モデルにおいて、高確率で発生するイベントに注目した場合、報酬の対数を比較することが合理的であることを示唆している。
【００５３】
このように、最適化部３２が、より合理的な指標を用いて最適化することで、より適切な施策を決定できる。また、上述するように乗算的に累積する効果を最大化しようとする際、最適化の対象を加算的なモデルに帰着させることで、一般的な最適化の手法を用いることも可能になる。
【００５４】
最適化部３２は、上述する加算的なモデルに対し、例えば、オンライン凸最適化を用いて、最適な投資比率ｘを算出してもよい。なお、オンライン凸最適化の方法は広く知られているため、ここでは詳細な説明は省略する。
【００５５】
そして、最適化部３２は、算出した投資比率で過去の投資比率を更新する。すなわち、最適化部３２は、観測された効果（例えば、利率ｒ）に基づいて、過去の実施比率（例えば、投資比率ｘ）を更新する。
【００５６】
信頼度計算部３３は、最適化された実施比率および観測された効果に基づいて、各施策の信頼度を計算する。具体的には、信頼度計算部３３は、投資比率ｘおよび各資産の過去の利率ｒに基づいて、各投資先ｉｔの信頼度ｐを算出する。なお、最適化部３２と同様、信頼度計算部３３は、信頼度を計算する際、単純な効果（期待値）を用いずに、対数（具体的には、式３におけるｌｏｇＡＴ）を指標として用いる。すなわち、信頼度計算部３３は、対数で表される効果に基づいて、各施策の信頼度を計算する。
【００５７】
信頼度計算部３３が信頼度を算出する方法は、観測できる効果の範囲に応じて、それぞれ定められる。具体的には、信頼度計算部３３は、全ての施策に対する効果が観測できる場合（すなわち、タイプＡの場合）と、実施した施策に対する効果のみ観測できる場合（すなわち、タイプＢの場合）とで、信頼度を算出する方法を選択してもよい。
【００５８】
全ての施策に対する効果が観測できる場合（すなわち、タイプＡの場合）、信頼度計算部３３は、エキスパートアルゴリズムに基づいて信頼度を算出してもよい。また、決定した施策に対する効果のみ観測できる場合（すなわち、タイプＢの場合）、信頼度計算部３３は、バンデッドアルゴリズムに基づいて信頼度を算出してもよい。
【００５９】
そして、信頼度計算部３３は、計算された信頼度で各施策の信頼度を更新する。すなわち、信頼度計算部３３は、逐次更新される実施比率（例えば、投資比率ｘ）に基づいて、各投資先の信頼度ｐを更新する。
【００６０】
施策決定部３４は、信頼度がより高い施策を決定する。具体的には、施策決定部３４は、信頼度ｐがより高い投資先ｉｔを決定する。
【００６１】
出力部４０は、決定した施策の内容を出力する。出力部４０は、例えば、ｔ＋１回目の施策の内容として、投資先ｉｔ＋１および投資比率ｘｔ＋１を出力する。
【００６２】
入力部１０と、計算部３０（より具体的には、初期化部３１と、最適化部３２と、信頼度計算部３３と、施策決定部３４）と、出力部４０とは、プログラム（施策決定プログラム）に従って動作するコンピュータのプロセッサ（例えば、ＣＰＵ（Central Processing Unit ）、ＧＰＵ（Graphics Processing Unit）、ＦＰＧＡ（field-programmable gate array ））によって実現される。
【００６３】
例えば、プログラムは、記憶部２０に記憶され、プロセッサは、そのプログラムを読み込み、プログラムに従って、入力部１０、計算部３０（より具体的には、初期化部３１と、最適化部３２と、信頼度計算部３３と、施策決定部３４）および出力部４０として動作してもよい。また、施策決定システムの機能がＳａａＳ（Software as a Service ）形式で提供されてもよい。
【００６４】
初期化部３１と、最適化部３２と、信頼度計算部３３と、施策決定部３４とは、それぞれが専用のハードウェアで実現されていてもよい。また、各装置の各構成要素の一部又は全部は、汎用または専用の回路（circuitry ）、プロセッサ等やこれらの組合せによって実現されもよい。これらは、単一のチップによって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい。各装置の各構成要素の一部又は全部は、上述した回路等とプログラムとの組合せによって実現されてもよい。
【００６５】
また、施策決定システムの各構成要素の一部又は全部が複数の情報処理装置や回路等により実現される場合には、複数の情報処理装置や回路等は、集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。
【００６６】
次に、本実施形態の施策決定システムの動作を説明する。図３は、本実施形態の施策決定システムの動作例を示すフローチャートである。初期化部３１は、施策の数をカウントする値ｔを１に初期化する（ステップＳ２１）。また、初期化部３１は、実施比率ｘおよび信頼度ｐを初期化する（ステップＳ２２）。施策決定部３４は、信頼度を示す確率ｐに基づいて施策ｉｔを決定する（ステップＳ２３）。なお、初期状態では、信頼度ｐの値は不定のため、任意の施策ｉｔが決定されればよい。そして、出力部４０は、決定された施策ｉｔおよび対応する実施比率ｘｉｔを出力する（ステップＳ２４）。
【００６７】
入力部１０は、施策の効果ｒｔを観測し、入力する（ステップＳ２５）。最適化部３２は、観測された効果に基づいて施策の実施比率を最適化し、過去の実施比率ｘを更新する（ステップＳ２６）。また、信頼度計算部３３は、最適化された実施比率ｘおよび観測された効果ｒｔに基づいて各施策の信頼度を計算し、各施策の信頼度を更新する（ステップＳ２７）。
【００６８】
初期化部３１は、ｔの値を１増加させるように更新する（ステップＳ２８）。ｔの値が意思決定の回数Ｔ以上でない場合（ステップＳ２９におけるＮｏ）、ステップＳ２３以降の処理が繰り返される。一方、ｔの値がＴ以上の場合（ステップＳ２９におけるＹｅｓ）、処理を終了する。
【００６９】
次に、信頼度および実施比率を算出する方法を、タイプごとに具体的に説明する。説明の便宜上、まず、いくつかの表記を定義する。［ｄ］を少なくともｄの正の整数の集合、すなわち、［ｄ］＝｛１，２，…，ｄ｝とする。また、ｆｔｉ：［０，１］→Ｒを、以下の式１０のように定義する。ここで、Ｃ１は、Ｃ１＞−１を満たす定数である。
【００７０】
ｆｔｉ（ｘ）＝ｌｏｇ（１＋ｒｔｉｘ）−ｌｏｇ（１＋Ｃ１）  （式１０）
【００７１】
さらに、Ｃ２≧Ｃ１、ｒｔｉ∈［Ｃ１，Ｃ２］およびＣ１≦０と想定すると、ｘ∈［０，１］について、以下に示す式１１が成り立つ。
【００７２】
【数８】
0006977878.tif 000009
【００７３】
さらに、全てのｔ∈［Ｔ］およびｉ∈［ｄ］について、以下に示す式１２および式１３を定義する。これらの値が、ｘの更新に用いられる。
【００７４】
【数９】
0006977878.tif 000010
【００７５】
さらに、値ｈｔｉは、以下に示す式１４の上限であるとする。
【００７６】
【数１０】
0006977878.tif 000011
【００７７】
ここで、ｈｔｉはｆｔｉ（ｘ）の二次導関数の境界を示す。具体的には、全てのｘ∈［０，１］について、以下に示す式１５を満たす。
【００７８】
【数１１】
0006977878.tif 000012
【００７９】
式１５は、以下に示す式１６の内容を示す。式１６における不等号が、重要な役割を果たす。
【００８０】
【数１２】
0006977878.tif 000013
【００８１】
また、ｉ＊およびｘ＊をＴ回の試行における最適戦略を表すとする。すなわち、この最適戦略は、以下の式１７のように表すことができる。
【００８２】
【数１３】
0006977878.tif 000014
【００８３】
ここで、全てのｔ∈［Ｔ］に対し、Ｆｔ＊＝ｆｔｉ＊（ｘ＊）を定義する。また、全てのｔ∈［Ｔ］およびｉ∈［ｄ］に対し、Ｆｔｉ＝ｆｔｉ（ｘｔｉ）を定義する。このとき、リグレット（後悔）は、以下に示す式１８で表すことができる。式１８におけるｉｔおよびｘｔが処理における出力を表す。
【００８４】
【数１４】
0006977878.tif 000015
【００８５】
まず、タイプＡの場合について説明する。タイプＡは、オンライン凸最適化に基づいて最適な実施比率ｘを計算し、エキスパートアルゴリズムに基づいて各施策の信頼度ｐを算出する方法である。図４は、タイプＡの場合に信頼度および実施比率を算出する処理の例を示すフローチャートである。初期化部３１は、ｗ１＝［ｗ１１…ｗ１ｄ］Ｔ＝１（全ての要素が１のベクトル）、ｘ１＝［ｘ１１…ｘ１ｄ］Ｔ＝０（全ての要素が０のベクトル）に初期化する（ステップＳ３１）。
【００８６】
信頼度計算部３３は、信頼度ｐｔを、ｐｔ＝ｗｔ／||ｗｔ||１に設定する（ステップＳ３２）。施策決定部３４は、確率ベクトルｐｔに基づいて無作為に施策ｉｔを選択する（ステップＳ３３）。出力部４０は、施策ｉｔおよびｘｔ＝ｘｔｉｔを出力し、入力部１０は、全ての施策に対する効果ｒｔｉを観測する（ステップＳ３４）。
【００８７】
最適化部３２は、ｗｔを更新する（ステップＳ３５）。具体的には、最適化部３２は、ｗｔ＋１をｉについてｗｔ＋１，ｉ＝ｗｔｉｅｘｐ（ηＦｔｉ）に設定する。なお、ηは、正のパラメータである。また、最適化部３２は、ｘｔを更新する（ステップＳ３６）。具体的には、最適化部３２は、ｘｔ＋１を以下に示す式１９で算出される値に設定する。
【００８８】
式１９において、π［０，１］（・）は、［０，１］への射影を表す。すなわち、π［０，１］（ｙ）について、ｙ＜０に対してπ［０，１］（ｙ）＝０であり、０≦ｙ≦１に対してπ［０，１］（ｙ）＝ｙであり、ｙ＞１に対して、π［０，１］（ｙ）＝１である。また、式１９におけるＢは、正のパラメータである。
【００８９】
【数１５】
0006977878.tif 000016
【００９０】
以降、試行回数がＴになるまで、ステップＳ３２からステップＳ３６の処理が繰り返される。
【００９１】
次に、タイプＢの場合について説明する。タイプＢは、オンライン凸最適化に基づいて最適な実施比率ｘを計算し、バンデッドアルゴリズムに基づいて各施策の信頼度ｐを算出する方法である。図５は、タイプＢの場合に信頼度および実施比率を算出する処理の例を示すフローチャートである。タイプＢの処理において、以下の式２０に示すようなｇｔｉおよびｈｔｉに対するバイアスのない推定器ｇ＾ｔｉおよびｈ＾ｔｉを設定する（ただし、＾は、上付きハットを示す）。
【００９２】
【数１６】
0006977878.tif 000017
【００９３】
タイプＡの場合と同様に、初期化部３１は、ｗ１＝［ｗ１１…ｗ１ｄ］Ｔ＝１（全ての要素が１のベクトル）、ｘ１＝［ｘ１１…ｘ１ｄ］Ｔ＝０（全ての要素が０のベクトル）に初期化する（ステップＳ４１）。信頼度計算部３３は、信頼度ｐｔを、以下に示す式２１のように設定する（ステップＳ４２）
【００９４】
【数１７】
0006977878.tif 000018
【００９５】
施策決定部３４は、確率ベクトルｐｔに基づいて無作為に施策ｉｔを選択する（ステップＳ４３）。出力部４０は、施策ｉｔおよびｘｔ＝ｘｔｉｔを出力し、入力部１０は、選択された施策に対する効果ｒｔｉｔのみを観測する（ステップＳ４４）。
【００９６】
最適化部３２は、ｗｔを更新する（ステップＳ４５）。具体的には、最適化部３２は、ｗｔについて、ｗｔ＋１，ｉｔ＝ｗｔｉｔｅｘｐ（ηＦｔｉｔ／ｐｔｉｔ）に設定し、ｉ≠ｉｔに対してｗｔ＋１，ｉ＝ｗｔｉに設定する。また、最適化部３２は、ｘｔを更新する（ステップＳ４６）。具体的には、最適化部３２は、ｘｔ＋１を以下に示す式２２で算出される値に設定する。
【００９７】
【数１８】
0006977878.tif 000019
【００９８】
以降、試行回数がＴになるまで、ステップＳ４２からステップＳ４６の処理が繰り返される。
【００９９】
以上のように、本実施形態では、最適化部３２が、観測された効果に基づいて、乗算的に累積する効果を最大化するように、施策の実施比率を最適化し、信頼度計算部３３が、最適化された実施比率および観測された効果に基づいて、各施策の信頼度を計算する。また、施策決定部３４が、信頼度がより高い施策を決定し、入力部１０が、決定された施策による効果を観測する。さらに、最適化部３２が、観測された効果に基づいて、過去の実施比率を更新し、信頼度計算部３３が、更新された実施比率に基づいて各施策の信頼度を更新する。この投資比率および信頼度が観測される効果に基づいて逐次更新され、施策が決定される。よって、逐次実行される施策の効果が乗算的に影響するような状況において、最適化した結果が不合理になる状況を回避して、効果を最大化するような施策を決定できる。
【０１００】
次に、本発明の概要を説明する。図６は、本発明による施策決定システムの概要を示すブロック図である。本発明による施策決定システムは、施策（例えば、ある投資先ｉｔへの投資）に対して観測される効果（例えば、利率ｒ）が時間の経過とともに変化する場合における、その施策を決定する施策決定システム８０（例えば、施策決定システム１００）である。
【０１０１】
施策決定システム８０は、観測された効果（例えば、各投資先の利率ｒ）に基づいて、乗算的に累積する効果を最大化するように、施策（例えば、ある投資先ｉｔへの投資）の実施比率（例えば、投資比率ｘ）を最適化する最適化部８１（例えば、最適化部３２）と、最適化された実施比率および観測された効果に基づいて、各施策（例えば、投資する投資先ｉｔ）の信頼度（例えば、信頼度ｐ）を計算する信頼度計算部８２（例えば、信頼度計算部３３）と、信頼度がより高い施策（例えば、投資先ｉｔ）を決定する施策決定部８３（例えば、施策決定部３４）と、決定された施策による効果を観測する観測部８４（例えば、入力部１０）とを備えている。
【０１０２】
そして、最適化部８１は、観測された効果に基づいて、過去の実施比率を更新し、信頼度計算部８２は、更新された実施比率に基づいて各施策の信頼度を更新する。
【０１０３】
そのような構成により、逐次実行される施策の効果が乗算的に影響するような状況において、最適化した結果が不合理になる状況を回避して、効果を最大化するような施策を決定できる。
【０１０４】
具体的には、最適化部８１は、オンライン凸最適化に基づいて実施比率を最適化し、信頼度計算部８２は、エキスパートアルゴリズムに基づいて各施策の信頼度を計算してもよい。そのような構成によれば、全ての施策に対する効果が観測できる場合（例えば、タイプＡの場合）、各施策の最適な実施比率および信頼度を算出できる。
【０１０５】
他にも、最適化部８１は、オンライン凸最適化に基づいて実施比率を最適化し、信頼度計算部８２は、バンデッドアルゴリズムに基づいて各施策の信頼度を計算してもよい。そのような構成によれば、決定した施策に対する効果のみ観測できる場合（例えば、タイプＢの場合）、各施策の最適な実施比率および信頼度を算出できる。
【０１０６】
具体的な態様として、最適化部８１は、観測された各資産の利率に基づいて、投資先への投資比率を最適化し、信頼度計算部８２は、最適化された投資比率および観測された各資産の利率に基づいて、各投資先の信頼度を計算し、施策決定部８３は、信頼度がより高い投資先への投資を施策として決定してもよい。
【０１０７】
また、最適化部８１は、乗算的に累積する効果を、対数で表される加算的な効果に変形し（例えば、上記式３のように変形し）、対数で表される効果を最大化するように施策の実施比率を最適化し、信頼度計算部８２は、対数で表される効果に基づいて、各施策の信頼度を計算してもよい。
【０１０８】
図７は、少なくとも１つの実施形態に係るコンピュータの構成を示す概略ブロック図である。コンピュータ１０００は、プロセッサ１００１、主記憶装置１００２、補助記憶装置１００３、インタフェース１００４を備える。
【０１０９】
上述の施策決定システムは、コンピュータ１０００に実装される。そして、上述した各処理部の動作は、プログラム（施策決定プログラム）の形式で補助記憶装置１００３に記憶されている。プロセッサ１００１は、プログラムを補助記憶装置１００３から読み出して主記憶装置１００２に展開し、当該プログラムに従って上記処理を実行する。
【０１１０】
なお、少なくとも１つの実施形態において、補助記憶装置１００３は、一時的でない有形の媒体の一例である。一時的でない有形の媒体の他の例としては、インタフェース１００４を介して接続される磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ（Compact Disc Read-only memory ）、ＤＶＤ−ＲＯＭ（Read-only memory）、半導体メモリ等が挙げられる。また、このプログラムが通信回線によってコンピュータ１０００に配信される場合、配信を受けたコンピュータ１０００が当該プログラムを主記憶装置１００２に展開し、上記処理を実行しても良い。
【０１１１】
また、当該プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、当該プログラムは、前述した機能を補助記憶装置１００３に既に記憶されている他のプログラムとの組み合わせで実現するもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０１１２】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１１３】
（付記１）施策に対して観測される効果が時間の経過とともに変化する場合における当該施策を決定する施策決定システムであって、観測された効果に基づいて、乗算的に累積する当該効果を最大化するように、前記施策の実施比率を最適化する最適化部と、最適化された実施比率および観測された効果に基づいて、各施策の信頼度を計算する信頼度計算部と、前記信頼度がより高い施策を決定する施策決定部と、決定された施策による効果を観測する観測部とを備え、前記最適化部は、観測された効果に基づいて、過去の実施比率を更新し、前記信頼度計算部は、更新された実施比率に基づいて前記各施策の信頼度を更新することを特徴とする施策決定システム。
【０１１４】
（付記２）最適化部は、オンライン凸最適化に基づいて実施比率を最適化し、信頼度計算部は、エキスパートアルゴリズムに基づいて各施策の信頼度を計算する付記１記載の施策決定システム。
【０１１５】
（付記３）最適化部は、オンライン凸最適化に基づいて実施比率を最適化し、信頼度計算部は、バンデッドアルゴリズムに基づいて各施策の信頼度を計算する付記１記載の施策決定システム。
【０１１６】
（付記４）最適化部は、観測された各資産の利率に基づいて、投資先への投資比率を最適化し、信頼度計算部は、最適化された投資比率および観測された各資産の利率に基づいて、各投資先の信頼度を計算し、施策決定部は、信頼度がより高い投資先への投資を施策として決定する付記１から付記３のうちのいずれか１つに記載の施策決定システム。
【０１１７】
（付記５）最適化部は、乗算的に累積する効果を、対数で表される加算的な効果に変形し、前記対数で表される効果を最大化するように施策の実施比率を最適化し、信頼度計算部は、前記対数で表される効果に基づいて、各施策の信頼度を計算する付記１から付記４のうちのいずれか１項に記載の施策決定システム。
【０１１８】
（付記６）施策に対して観測される効果が時間の経過とともに変化する場合における当該施策を決定する施策決定方法であって、観測された効果に基づいて、乗算的に累積する当該効果を最大化するように、前記施策の実施比率を最適化し、最適化された実施比率および観測された効果に基づいて、各施策の信頼度を計算し、前記信頼度がより高い施策を決定し、決定された施策による効果を観測し、観測された効果に基づいて、過去の実施比率を更新し、更新された実施比率に基づいて、前記各施策の信頼度を更新し、更新された実施比率および信頼度を用いて施策の決定が逐次繰り返されることを特徴とする施策決定方法。
【０１１９】
（付記７）オンライン凸最適化に基づいて実施比率を最適化し、エキスパートアルゴリズムに基づいて各施策の信頼度を計算する付記６記載の施策決定方法。
【０１２０】
（付記８）オンライン凸最適化に基づいて実施比率を最適化し、バンデッドアルゴリズムに基づいて各施策の信頼度を計算する付記６記載の施策決定方法。
【０１２１】
（付記９）施策に対して観測される効果が時間の経過とともに変化する場合における当該施策を決定するコンピュータに適用される施策決定プログラムであって、前記コンピュータに、観測された効果に基づいて、乗算的に累積する当該効果を最大化するように、前記施策の実施比率を最適化する最適化処理、最適化された実施比率および観測された効果に基づいて、各施策の信頼度を計算する信頼度計算処理、前記信頼度がより高い施策を決定する施策決定処理、および、決定された施策による効果を観測する観測処理を実行させ、前記最適化処理で、観測された効果に基づいて、過去の実施比率を更新させ、前記信頼度計算処理で、更新された実施比率に基づいて前記各施策の信頼度を更新させるための施策決定プログラム。
【０１２２】
（付記１０）コンピュータに、最適化処理で、オンライン凸最適化に基づいて実施比率を最適化させ、信頼度計算処理で、エキスパートアルゴリズムに基づいて各施策の信頼度を計算させる付記９記載の施策決定プログラム。
【０１２３】
（付記１１）コンピュータに、最適化処理で、オンライン凸最適化に基づいて実施比率を最適化させ、信頼度計算処理で、バンデッドアルゴリズムに基づいて各施策の信頼度を計算させる付記９記載の施策決定プログラム。
【符号の説明】
【０１２４】
１０  入力部
２０  記憶部
３０  計算部
３１  初期化部 
３２  最適化部
３３  信頼度計算部
３４  施策決定部
４０  出力部
【図１】
0006977878.tif 000020
【図２】
0006977878.tif 000021
【図３】
0006977878.tif 000022
【図４】
0006977878.tif 000023
【図５】
0006977878.tif 000024
【図６】
0006977878.tif 000025
【図７】
0006977878.tif 000026