(57)【特許請求の範囲】
【請求項１】
第１の電極と第２の電極とによって挟まれた固体電解質中で金属イオンが電界の印加によって移動、金属原子としての析出及び再イオン化することを利用する複数の原子スイッチが並列接続され、
前記固体電解質が前記複数の原子スイッチ間で共有され、
前記金属イオンの析出が前記第１の電極上で行われるとともに、前記複数の前記原子スイッチの前記第１の電極上の前記金属原子の析出量の合計が一定であり、
各動作サイクルにおいて、前記複数の原子スイッチの前記第１の電極と前記第２の電極との間に当該動作サイクルにおける報酬量に基づく電圧が印加されることにより、前記固体電解質を介して前記金属原子が前記複数の原子スイッチの前記第１の電極間で移動し、
前記複数の前記第１の電極上の前記金属原子の析出量の大きな前記前記原子スイッチが次回の動作サイクルにおいて選択される
ＴＯＷアルゴリズムを実行する意思決定装置。
【請求項２】
前記第２の電極が前記複数の原子スイッチ間で共有されている、請求項１に記載の意思決定装置。
【請求項３】
前記金属イオンが銀イオン、１価の銅イオン、リチウムイオン、ナトリウムイオン、マグネシウムイオン、２価のニッケルイオン及び２価の鉄イオンからなる群から選択される、
請求項１または２に記載の意思決定装置。
【請求項４】
前記固体電解質が電子・イオン混合伝導体，純イオン伝導体及び高分子電解質から成る群から選択される、請求項１から３の何れかに記載の意思決定装置。
【請求項５】
前記第１及び第２の電極が白金からなる、請求項１から４の何れかに記載の意思決定装置。
【請求項６】
前記第１の電極上の前記金属原子の析出量は前記金属原子が前記第１の電極上に堆積している高さに基づいて表される、請求項１から５の何れかに記載の意思決定装置。
【請求項７】
前記高さは前記第１の電極と前記第２の電極との間に流れる電流として求められる、請求項６に記載の意思決定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は意思決定を行うために使用できる装置に関し、特に多本腕バンディット問題を解くための効率的なアルゴリズムとして知られているＴＯＷアルゴリズムに基づいた意思決定装置に関する。
【背景技術】
【０００２】
人間の知的能力の最も重要なものの一つに意思決定を挙げることができる。この意思決定を自動化する手法の一つとして、問題を多本腕バンディット問題（multi-armed bandit problem；ＭＡＢ）の形でモデル化し、このモデルにＭＡＢを解くためのアルゴリズム（ＭＡＢアルゴリズムと称する）を適用することによって、与えられた問題を解くことが提案されている。良く知られているように、ＭＡＢとはプレーヤーからは報酬確率を事前に知ることができないスロットマシンが複数台与えられている状況で、プレーヤーがプレイしながらできるだけ早くかつ正確に報酬確率が高いスロットマシンを選択するにはどうすればよいか、という問題である。現実世界の問題をＭＡＢで定式化して解くことの有用性は広く認識されており、人工知能（コンピュータ囲碁等）、情報通信（ウェブ広告、コグニティブ無線塔）、金融（ポートフォリオ等）、その他の多くの意思決定問題への応用が進められている。
【０００３】
ＭＡＢアルゴリズムは情報処理装置上でソフトウエアを使用して実装されるのが通常である。しかし、高速性が要求される実時間処理や小型化や低消費電力化が強く求められるある種の専用装置ではこのようなソフトウエアに依存した実装が不適切な場合がある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明はＴＯＷアルゴリズムに基づいてＭＡＢを解くための処理の少なくとも一部をハードウエア化した装置を提供することを課題とする。
【課題を解決するための手段】
【０００５】
本発明の一側面によれば、第１の電極と第２の電極とによって挟まれた固体電解質中で金属イオンが電界の印加によって移動、金属原子としての析出及び再イオン化することを利用する複数の原子スイッチが並列接続され、前記固体電解質が前記複数の原子スイッチ間で共有され、前記金属イオンの析出が前記第１の電極上で行われるとともに、前記複数の前記原子スイッチの前記第１の電極上の前記金属原子の析出量の合計が一定であり、各動作サイクルにおいて、前記複数の原子スイッチの前記第１の電極と前記第２の電極との間に当該動作サイクルにおける報酬量に基づく電圧が印加されることにより、前記固体電解質を介して前記金属原子が前記複数の原子スイッチの前記第１の電極間で移動し、前記複数の前記第１の電極上の前記金属原子の析出量の大きな前記前記原子スイッチが次回の動作サイクルにおいて選択される、ＴＯＷアルゴリズムを実行する意思決定装置が提供される。
ここで、前記第２の電極が前記複数の原子スイッチ間で共有されてよい。
また、前記金属イオンが銀イオン、１価の銅イオン、リチウムイオン、ナトリウムイオン、マグネシウムイオン、２価のニッケルイオン及び２価の鉄イオンからなる群から選択されてよい。
また、前記固体電解質が電子・イオン混合伝導体，純イオン伝導体及び高分子電解質から成る群から選択されてよい。
また、前記第１及び第２の電極が白金からなってよい。
また、前記第１の電極上の前記金属原子の析出量は前記金属原子が前記第１の電極上に堆積している高さに基づいて表されてよい。
また、前記高さは前記第１の電極と前記第２の電極との間に流れる電流として求められてよい。
【発明の効果】
【０００６】
本発明によれば、ＭＡＢを解く効率的なアルゴリズムであるＴＯＷアルゴリズムを実行する意思決定装置を原子スイッチで構成することができるので、意思決定装置を小型化、高速化することができる。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施例の無ギャップ型原子スイッチを使用した意思決定装置（ＡＳＤＭ）の概念的な構成及びその動作を示す図。意思決定装置は、時刻ｔにおいてスロットマシンＡ、Ｂのどちらでプレイするかを、電流Ｉｋ（ｋ∈｛Ａ，Ｂ｝、以下同様）が閾値θよりも大きいか否かで決める。
【図２】（ａ）ＡＤＳＭ中でのＴＯＷ（綱引き）動作を概念的に示す図。（ｂ）ＡＳＤＭの動作例を示す図であり、電圧Ｖｋと変位Ｘｋとの関係を示す。ここで、加算される電圧変化分ΔＶｋ（ｊ）は各プレイｊでの報酬Ｒｋ（ｊ）で決まる（Ｉｋ＞θとなるｋについて）。この図ではＡＳＤＭはスロットマシンをＡ、Ａ，Ａ、Ｂ、・・・の順で選択する。
【図３】（ａ）ＭＡＢの可解性を検討するために使用するランダムウォークモデルを示す図。ここで飛行距離（flight）はＲｋ（ｔ）−Ｋ。（ｂ）２つのランダムウィークの確率分布を示す図。
【図４】はカンニングアルゴリズムにおいて報酬の相対的に低いスロットマシンを選択する確率（Ｑ（Ｅ（Ｓ）／σ（Ｓ）））を示す図。
【図５】（ａ）Ｋに対するＡＳＤＭの１０００までのプレイのregret（実線）及びτｏｐｔ＝０．３の場合のＳＯＦＴＭＡＸのregret（破線）を示すグラフ。（ｂ）ＡＤＳＭ（実線）とＳＯＦＴＭＡＸ（破線）との性能の比較を示すグラフ。ここで、ＡＳＤＭについてはＫ０＝０．５５とし、ＳＯＦＴＭＡＸについてはτｏｐｔ＝０．３とした。点線はＫ０を持つＡＳＤＭの上界（式（４３））である。
【発明を実施するための形態】
【０００８】
自然界に目を向けると、生体系中での情報処理はその下層をなす物理的な特性と見事に結びついている（非特許文献１、２）。このことから、物理現象に基づいた新たなアナログ的情報処理の枠組みを確立できるという可能性が示唆される。
【０００９】
１０年程以前に、「原子スイッチ」と呼ばれる概念的に新しいスイッチングデバイスが提案された。この原子スイッチは固体電解質中での金属イオンの移動及び電気化学的反応に基づいている（非特許文献３）。この素子の抵抗状態は少数の金属イオン／原子の移動によって連続的に制御されるので、原子スイッチは物理現象に基づいたアナログコンピューティング素子であると見なすことができる。本願発明者は、体積保存則と言う物理的な制約を利用することで、原子スイッチに基づいて意思決定問題を効率的に解くことができるとの着想を得て、本発明をなすに至った。なお、以下では固体電解質中を移動する金属イオンが銀イオンであり、また電極材料を白金として説明するが、本発明で使用される金属イオン及び電極をこれらの物質に限定する意図はなく、原子スイッチの分野で使用される物質を適宜選択して使用することができる。例えば、金属イオンとしては銀イオン以外に１価の銅、リチウム、ナトリウム、２価のニッケル、マグネシウム、鉄等が使用できる。また、固体電解質としては無機材料と有機材料が使用可能である。使用可能な無機材料としてはＡｇ２Ｓ、Ｃｕ２Ｓなどの電子・イオン混合伝導体，ＡｇＩ、ＲｂＡｇ４Ｉ５などの純イオン伝導体、Ｔａ２Ｏ５、ＳｉＯ２、ＨｆＯ２などの金属酸化物等がある。一方、有機材料としてはリチウムイオンバッテリー等に使われる高分子電解質が使用可能である。具体的には，ポリエチレンオキシド（ＰＥＯ）、ポリビニルアルコール（ＰＶＡ）、ポリビニルピロリドン（ＰＶＰ）等の高分子に金属塩を溶解させたものが挙げられる。電極材料も白金に限定されるものではなく、不活性の、すなわち化学的に安定性の高い金属であれば使用可能である。
【００１０】
Ｍ台のスロットマシンが与えられ、これらのスロットマシンの各々は、それでプレイを行うことで、プレーヤーには未知である一定の確率密度関数（probability density function；ＰＤＦ）に基づいてコイン等の報酬を得ることができるとする。ここで、最も単純な状況として、２台のスロットマシンＡ、Ｂが夫々平均報酬がμＡ及びμＢである個別のＰＤＦに基づいて報酬を与える場合を考える。プレーヤーはプレイ毎にどちらのスロットマシンを使用するかの意思決定を行い、何回かのプレイを行ったことによる報酬の合計を最大化しようとする。ここで、最初のプレイを開始した以降の経験を参照することによって報酬の最大化のための最適戦略を可能な限り早くかつ正確に決定するためにＭＡＢを使用することができる。
【００１１】
意思決定アルゴリズムのための研究の歴史でＭＡＢを最初に説明したのは非特許文献４であるが、ＭＡＢの基本的な事項の研究はそれより以前に非特許文献５に述べられている。「Gittins index」と呼ばれる最適戦略は、報酬の分布がプレーヤーに既知であると仮定される限定的なクラスの問題についてのみ知られている（非特許文献６、７）。しかも、この種の限定的なクラスの問題でもGittins indexを実際に計算するのは多くの場合非常に困難なものとなる。非特許文献８、９で提案された別のアルゴリズムでは、スロットマシンから得られる報酬の合計の簡単な関数で表される。実際には、ＭＡＢを解くためのＵＣＢ１（upper confidence bound 1）アルゴリズムが多くの実際的な応用で世界的に使用されている（特許文献９）。ＭＡＢは数学上の問題として一般性を失うことなく定式化することができ、それ自体は多様な確率論的な現象に関連付けられる。実際、多様な分野における多くの応用分野の問題、例えば、コグニティブネットワーク（非特許文献１０、１１）等の通信分野、ウエブ上の広告（非特許文献１２）等の商業分野、コンピュータゲームに使用されるモンテカルロ木検索（非特許文献１３、１４））等の商業分野の問題はＭＡＢに帰着させることができる。
【００１２】
本願発明者は動的な形を利用した綱引き（tug-of-war；ＴＯＷ）アルゴリズムと呼ばれるＭＡＢの解法を提案した。ＴＯＷアルゴリズムは単細胞のアメーバ状生物（真性粘菌粘菌（true slime mold）の一種であるモジホコリカビ（Physarum polycephalum））の時空間的動態に触発されたものである（非特許文献１５〜２１）。この巨大な単細胞生物は細胞内資源の堆積を一定に維持しつつ、その偽足状になった複数の末端部分を同時に膨張或いは収縮させることによって環境情報を収集する。この生体によって触発されたアルゴリズムでは、それが基づいている対象が持っているところの綱引きゲームに似ている物理的な特性から意思決定関数が導出される。この綱引き的な現象の動力学における物理的な制約、すなわちアメーバ状の生体での体積保存則により、上述した複数の末端部分の間の非局所的な相関が引き起こされる。つまり、一つの末端部分の体積が増大すると、それは他の一つまたは複数の部分の体積が減少することによって直ちに補償される。本願発明者による以前の研究（非特許文献１５〜２１）が明らかにしたところでは、体積保存則によってもたらされた非局所的な相関的な作用によって、ＴＯＷアルゴリズムの動作はＵＣＢ１を調節したアルゴリズム（非特許文献９で、パラメータなしアルゴリズム中の最良の選択とされている）に匹敵する修正ε-greedyアルゴリズムや修正ＳＯＦＴＭＡＸアルゴリズムのような、他の良く知られているＭＡＢアルゴリズムよりも高い性能を示す。これらの考察から、本願発明者は保存則のようなある共通の物理的な属性を保持する限りでの任意の物理的な物体を使用して効率的な意思決定装置を実現できるとの着想を得た。実際、本願発明者は、量子ドット間における光学的なエネルギー転送の挙動でエネルギーが保存されることをＴＯＷアルゴリズム動作を実現するために利用できることを示した（非特許文献２２〜２４）。
【００１３】
本願発明者は上記知見・考察に基づいて、原子スイッチの原理に基づく意思決定装置（atomic switch-based decision maker；以下ＡＳＤＭと称する）を発明した。以下の説明から明らかなように、ＡＳＤＭはＴＯＷに基づいて意思決定を行うハードウエアである。
【００１４】
本発明の一実施例によれば、ＡＳＤＭは２つの原子スイッチを互いに近接して並置した構造を有する。ここで、固体電解質（ＳＥ）の一方の側（以下、上面側と称するが、この側を「上」にする必要があるという意味ではなく、２つの面を識別するために便宜上付与した単なる識別用の記号であると理解されたい。以下の「下面」についても同じ）に１つのＰｔ（白金）電極が設けられ、その反対側（以下、下面側と称する）には２つの白金電極が並置された状態で設けられている。この構造を図１の左側に概念的に示す。すなわち、図１に示されたＡＳＤＭは、２つの原子スイッチ（図中の左側の原子スイッチを原子スイッチＡ、右側を原子スイッチＢと呼ぶ）が、上面側の電極を共通とし、下面側の電極については夫々の個別の電極を維持した形態で並置し融合した構造になっている。ＡＳＤＭを構成する２つの原子スイッチの夫々は金属／イオン伝導体／金属（ＭＩＭ）という構成で動作する。ＭＩＭスイッチは不活性の電極上への金属の析出によって上下の電極間に金属フィラメントを形成できるので、これを無ギャップ型原子スイッチ（gapless type atomic switch）（非特許文献２５）と呼ぶ。ここで、両原子スイッチは相互に影響を受けるものとするが、このことは、両原子スイッチ間で何らかの相互作用が存在することを意味している。
【００１５】
図示したＡＳＤＭの初期状態では、金属イオン（ここではＡｇ（銀）イオンを使用）が固体電解質中に一様に分布していて、Ａｇイオンの総数は一定であるものとする。上面側のＰｔ電極と下面側の２つのＰｔ電極Ａ，Ｂとの間にバイアス電圧−Ｖ０を印加する（ＶＡ＝ＶＢ＝−Ｖ０）と、Ａｇイオンが下面側の両Ｐｔ電極に移動し、当該電極上で還元されることによりＡｇ原子がそれぞれの下面側Ｐｔ電極上に析出する。初期状態において両方の原子スイッチに同じバイアス電圧−Ｖ０を印加した際には、２つの下面側の電極に同量のＡｇ原子が析出するものとし、この析出したＡｇ原子の集団の高さを、図１に示すようにＸ０で表す。また、その後の動作に当たって、時刻ｔにおける下面側の２つのＰｔ電極上のＡｇ原子集団の高さのＸ０からの変位をＸｋ（ｔ）（ｋ∈｛Ａ，Ｂ｝）で表す（原子スイッチｋをＡＳＤＭに対応付けられているＭＡＢにおけるスロットマシンと同一視し、対応するスロットマシンもｋとして識別する）。従って、時刻ｔにおけるこれら下面側Ｐｔ電極上のＡｇ原子の集団の高さはＸ０＋Ｘｋ（ｔ）となる。
【００１６】
図２（ｂ）に示すように、ＡＳＤＭの上下の電極間には信号印加期間Δｔ＋休止期間Δｔｉｎｔ＝ｔｓの周期で信号パルスが印加される。各原子スイッチを流れる電流Ｉｋをｔｓの時間間隔で測定する。より具体的には休止期間Δｔｉｎｔ内のある決まった時点（ここでは各Δｔの直後）において測定する。原子スイッチｋ側を流れる電流ＩｋがＩｋ＞θである場合には、ＡＳＤＭが対応するスロットマシンｋ（スロットマシンＡ及び／またはＢ）を選択して、図１の右側に示す「問題」側へこの情報を送り出す。問題側では各未知ＰＤＦ（平均報酬μｋも未知とする）から生成される報酬Ｒｋ（ｊ）が、スロットマシンをプレイすることによる確率事象の結果として得られる。ここで、ｊは何回目のプレイであるかを示すステップ番号である。この報酬により、上記バイアス電圧−Ｖ０に加えることで原子スイッチへ印加する電圧を変位させる電圧であるΔＶｋ（ｊ）は以下の式（１）のように定められ、これがＡＳＤＭ側に戻される。
【００１７】
【数１】
0006536957.tif 000002
【００１８】
上式で、Ｒｋ（ｊ）は任意の実数値を取る「報酬」である。また、Ｋは後程詳述するパラメータである。これにより、各原子スイッチのバイアス電圧Ｖｋは以下の式（２）で表す通りとなる。
【００１９】
【数２】
0006536957.tif 000003
【００２０】
なお、選択されなかった方の原子スイッチのバイアス電圧Ｖｋは−Ｖ０のままである（図２（ｂ）の上半分にあるＶＡ及びＶＢの時間変化を示すグラフを参照）。また、選択された側の原子スイッチに印加されるバイアスを変位させる電圧ΔＶｋ（ｊ）は正負両方の極性を取り得る点に注意されたい。ΔＶｋ（ｊ）が正の場合には原子スイッチＡとＢの電極上に析出したＡｇ原子の集団の高さの差が増大し、負の場合にはこの差は減少する。
【００２１】
ここにおいて、以下の条件が満たされているものとする。
【００２２】
１．初期平衡状態では、固体電解質ＳＥ中には析出できるＡｇイオンはほとんどない。これは一方の原子スイッチの下面側電極上にＡｇ原子が増加してその高さが一段階分増加することは他方の原子スイッチで対応する高さが一段階分減少することを意味する（式（３）が成立する）。
【００２３】
２．Ｘ０＋Ｘｋ＞Ｔｈの場合、電流Ｉｋはθより大きい。ここで、Ｔｈ及びθは閾値である。ＴｈがＸ０よりも小さく設定されている場合には、この挙動はまだ変動（fluctuation）を受けていない初期状態から成立する。すなわち、閾値が小さく設定されていれば、ゆらぎがなくとも時刻０から選択が始まる。
【００２４】
３．簡単化のため、ΔＶｋと選択された原子スイッチにΔｔのパルス電圧（図２（ｂ）参照）を印加した時の析出量の変化量ΔＸとの間の関係（式（３）及び式（４））が線形であると仮定する（この関係は厳密には析出したＡｇ原子集団の形状及び残っているＡｇイオンの量に依存する）。
【００２５】
４．図２（ｂ）に示すように、バイアス電圧Ｖｋ（ｔ）は所定時間の信号印加期間Δｔの間だけ印加されるとともに、次回のバイアス電圧Ｖｋ（ｔ＋１）の印加の間に休止期間Δｔｉｎｔを置き、この間においては初期動作で印加したバイアス電圧−Ｖ０を印加する。ここで、ΔｔをΔｔｉｎｔに比べて充分に長くして、時間Δｔｉｎｔの休止期間におけるＡｇ原子集団の減衰効果が無視できるようにする。
【００２６】
上に説明した動作を繰り返すにつれて、ＡＳＤＭは最後には原子スイッチＡとＢの何れか一方を選択するようになる。この様子を図２（ｂ）に示す。この図において、Ｔｈ＝Ｘ０としている。この条件下でも、高さＸｋに対応する電流Ｉｋはθ（Ｔｈ）の周りで時間とともに変動している。各時間ステップｊにおいて、ＡＳＤＭはθよりも大きな電流（Ｔｈよりも大きな析出高）を示す原子スイッチを検出して、対応するスロットマシンを選択する。次に、両原子スイッチに印加される電圧は、スロットマシンから得られた報酬に従って更新される。
【００２７】
ここでＡＳＤＭとＴＯＷアルゴリズムとの関係を説明すれば、ＴＯＷのモデルでは、選択されたスロットマシンをプレイした結果の報酬に応じて、非圧縮性の物体（以下では単に物体と呼ぶ）上の当該スロットマシンに対応させておいた位置に力を加えることでその物質に変動を与え（移動、変形等）、物体の当該変動を累積させた結果から各プレイ毎にどのスロットマシンをプレイ対象として選択するかを判断する。すなわち、ＡＳＤＭでは「物体」として下面側の複数の電極上に析出しているＡｇ原子全体（より厳密には、析出した金属原子と固体電解質ＳＥに溶けている金属イオンとの総和）を採用し、「変動」には１回のプレイに相当する電圧の印加によって下面側の電極間でＡｇ原子が移動すること、より具体的にはこの移動により各電極上に析出して堆積しているＡｇ原子の集団の高さ（Ａｇ原子の総量）の変化分を対応付けている。
【００２８】
従って、原理的には各電極上に析出しているＡｇ原子（一般的には金属原子）集団の高さＸｋを電極間で比較することで上記選択を行うことができる。しかし、現実的には、固体素子内部でプレイ毎に高さＸｋそれ自体を測定することは、不可能でないとしても非常に困難である。
【００２９】
そこで、下面側の電極上にＡｇ原子の集団が析出してその高さが増加することは、電気的には下面側の電極が上限側の電極に接近することと等価であり、それにより高さＸｋと上面側電極−下面側電極間に電圧を印加することによって原子スイッチｋに流れる電流Ｉｋの大きさとの間に単調な関係が成立することを利用する。すなわち、電流Ｉｋを閾値θと比較し、電流Ｉｋの方が大きい場合に次回のプレイ対象のスロットマシンとしてｋを選択する。
【００３０】
なお、上の説明では各原子スイッチを流れる電流Ｉｋを所定の閾値θと比較するものとしたが、このような比較を行う代わりに原子スイッチ間での相対的な比較を行って、一番大きな電流が流れる原子スイッチを選択するようにしてもよい。
【００３１】
変位ＸＡ（＝−ＸＢ）は以下の式（３）及び式（４）によって定められる。
【００３２】
【数３】
0006536957.tif 000004
【００３３】
上式において、Ｑｋ（｛ｋ∈｛Ａ，Ｂ｝｝）は初期時刻１から現在時刻ｔまで累算した過去の経験の近似情報であり、Ｎｋはスロットマシンｋがプレイされた回数であり、ΔＶｋはスロットマシンｋをプレイする際にバイアスに加える変位電圧であり、δ（ｔ）は物体がその影響を受ける任意の変動であり、Ｋは上で言及したように後述するパラメータである。式（１）及び式（２）は学習則（learning rule）と呼ばれる。従って、このＡＳＤＭ動作は以下のとりわけ簡単なルールに従って進行する：スロットマシンｋが各時刻ｔ毎にプレイされるとき、Ｒｋ−ＫがＸｋ（ｔ）に加算される（図２）。
【００３４】
なお、上で「変位ＸＡ（＝−ＸＢ）」と書いたが、これは析出した原子塊の高さの総量の保存を前提とした説明であるためにこのような扱いになったものである。一般的には厳密には両者は「より緩い関係」で結ばれている。つまり、一方が１増えても他方が１ではなく、１＞α＞０で表されるαしか減らない等の場合もあることに注意されたい。
【００３５】
ＡＳＤＭの構成要素となっている原子スイッチ自体はその構造、製造方法、特性等はよく知られており、したがって上の説明からＡＳＤＭを実際に作成することは容易である。以下では、ＡＳＤＭと従来のＳＯＦＴＭＡＸアルゴリズムとを比較し、またＡＳＤＭ動作理論的な解析結果を説明する。
【００３６】
なお、上ではＡＳＤＭを構成する原子スイッチ（また、それに対応付けられたスロットマシン）が２つであるとし、これらをＡ及びＢと呼ぶことで識別している。しかし、当然のことであるが、ＴＯＷアルゴリズムがそうであるように、使用されるスロットマシンの台数には制限がなく、またそれに対応付けて一つのＡＳＤＭ中に含まれる原子スイッチの個数にも当然制限がない。また、このように原子スイッチ（スロットマシン）の個数を２つに限定しない一般的な説明を行う際には、これらにＡ、Ｂではなく自然数の番号を付与して、この自然数により原子スイッチを参照することがある。このような場合、例えばＡ＝１、Ｂ＝２とすることで、原子スイッチが２つの特別な場合の説明と原子スイッチの個数を特に限定せずに行う議論とを関連付けることができることに注意されたい。
【００３７】
＜ＳＯＦＴＭＡＸアルゴリズム＞
ＳＯＦＴＭＡＸアルゴリズムはＭＡＢ問題のための良く知られたアルゴリズムである（非特許文献２６）。このアルゴリズムでは、Ａを選択する確率Ｐ'Ａ（ｔ）、Ｂを選択する確率Ｐ'Ｂ（ｔ）は下式で与えられる。
【００３８】
【数４】
0006536957.tif 000005
【００３９】
ここでＡｋ（ｔ）（ｋ∈｛Ａ，Ｂ｝）は
【００４０】
【数５】
0006536957.tif 000006
【００４１】
で与えられる。また、βは本願では下式で与えられる時間依存した形態である。
【００４２】
【数６】
0006536957.tif 000007
【００４３】
β＝０はランダムな選択に対応し、β→∞は欲張り行動（greedy action）に対応する。
【００４４】
＜ＡＳＤＭの理論解析＞
報酬を０または１に限定したBernoulliタイプのＭＡＢ問題についてのＴＯＷ動作の理論解析は、非特許文献２１に記載されている。本願ではＡＳＤＭの理論解析を報酬が０または１に限定されていない一般のＭＡＢについて示す。
【００４５】
≪ＭＡＢの可解性≫
ＭＡＢの可解性を検討するため、図３（ａ）に示すランダムウォークモデルを考える。ここでＲｋ（ｔ）（ｋ∈｛Ａ，Ｂ｝）は時刻ｔでの報酬であり、Ｋはパラメータ（式（１）を参照）である。簡単にするため、Ｒｋの確率密度関数の平均がμＡ＞μＢを満足すると仮定する。時間ステップｔの後の変位Ｄｋ（ｋ∈｛Ａ，Ｂ｝）を以下のように記述することができる。
【００４６】
【数７】
0006536957.tif 000008
【００４７】
変位Ｄｋの期待値Ｅ（Ｄｋ（ｔ））は下式から得ることができる。
【００４８】
【数８】
0006536957.tif 000009
【００４９】
図３（ｂ）に示す、２つの分布の間の重複領域中では何れが大きいかを正確に評価できない。この重複領域はＮｋが増大するについて減少して間違った判定を避けるようにしなければならない。この要件は以下の形で表現できる。
【００５０】
【数９】
0006536957.tif 000010
【００５１】
上記２本の式は以下のように書き換えることができる。
【００５２】
【数１０】
0006536957.tif 000011
【００５３】
換言すれば、パラメータＫは、どちらが大きいかをランダムウォークが正しく判定するようにするように、上記条件を満足しなければならない。
【００５４】
Ｋが以下のようであれば上記条件を満足することを簡単に確認することができる。
【００５５】
【数１１】
0006536957.tif 000012
【００５６】
Ｑｋ（ｔ）及び式（１３）より、以下の結果が得られる。
【００５７】
【数１２】
0006536957.tif 000013
【００５８】
ここでパラメータＫをＫ０に設定した。従って、パラメータをＫ０とした学習則Ｑｋを使用したＡＳＤＭ動作によりＭＡＢを正しく解くことができると結論付けられる。
【００５９】
≪高性能の源泉≫
ε-greedyアルゴリズムのような多くの良く知られたアルゴリズムでは、時刻ｔ毎にプレイ対象の２台のスロットマシンの何れかについて報酬確率の見積もりを更新する。他方、平均報酬の合計γ＝μＡ＋μＢをプレーヤーが知っているという状況を仮定した場合には、一方のスロットマシンでしかプレイしなかったとしても両方のスロットマシンについての見積もりを同時に更新することができる。以下の表の上の行及び下の行は、夫々スロットマシンＡをＮＡ回プレイしたとの知識及びスロットマシンＢをＮＢ回プレイしたとの知識に基づいた平均報酬の見積もりを示す。なお、平均報酬γ＝μＡ＋μＢであることが既知であると仮定している。ここで、γが与えられていることを利用して、プレイされなかったスロットマシンについての報酬の見積もりも更新できることに注意されたい。
【００６０】
【表１】
0006536957.tif 000014
【００６１】
上に示した見積もりから、期待報酬Ｑ’ｋ（ｋ∈｛Ａ，Ｂ｝）は各々下式のように与えられる。
【００６２】
【数１３】
0006536957.tif 000015
【００６３】
これらの期待報酬Ｑ'ｊは、式（１）及び式（４）においてＴＯＷ動作の学習則により与えられたＱｊと同じではない。しかしながら、ＴＯＷ動作で実質的に使用しているものは下式で表される差分である。
【００６４】
【数１４】
0006536957.tif 000016
【００６５】
上式で期待報酬Ｑ'ｊにＱ"ｊ＝Ｑ'ｊ／２を代入することにより、以下の差分を得る。
【００６６】
【数１５】
0006536957.tif 000017
【００６７】
式（１８）と式（１９）とを比較すると、Ｋ＝Ｋ０（式（１４））が満足されている場合には両式を構成する項は常に等しい。結局、γで表されたほぼ最適のパラメータＫ０を得ることができる。
【００６８】
上述した導出はＡＳＤＭの動作についての学習則は両方の見積もりを同時に更新することができるという先に仮定したシステム学習則と等価であることを含意している。換言すれば、ＡＳＤＭの動作は、２台のスロットマシンの一方が時刻ｔでは実際にプレイされていなかった場合であっても、これら２台についての見積もりを参照して時刻ｔ＋１におけるその次回の動きを決定する仮想のシステムを模倣する。これは平均報酬の合計が事前に与えられていることから導かれる学習則の面でのユニークな特徴であって、このことがＡＳＤＭ動作の高性能の一つの原因であると考えられる。
【００６９】
モンテカルロ法によるシミュレーションを行った結果、Ｋ０を使ったＡＳＤＭ動作は、最適パラメータＫｏｐｔを使用して達成されるピーク性能と同等な、格別に高い性能を発揮することが確かめられた。最適値Ｋｏｐｔを正確に導くためには先に述べた変動を考慮する必要がある。
【００７０】
これに加えて、ここで説明した過程の本質はＭ台のスロットマシンを使用する場合に一般化することができる。図３（ｂ）に示すような、上からｍ台目のスロットマシンでの分布と上からｍ＋１台目のスロットマシンでの分布とを分離するためには、下式で示すようなＫ０を得るだけで良い。
【００７１】
【数１６】
0006536957.tif 000018
【００７２】
ここで、μ（ｍ）はｍ番目の平均を示し、ｍは１〜Ｍ−１の任意の整数である。ＭＢＰはｍ＝１とした特別の場合である。実際、本願発明者は、Ｍ台のスロットマシンをＸ人のプレーヤーでプレイする場合に「社会的最大（social maximum）」と呼ばれる全体の最適状態を素早くかつ正確に決定できるシステムを策定した（非特許文献２８、２９）。
【００７３】
＜性能評価＞
ＡＳＤＭ動作の高い性能を評価するため、ＭＡＢを解くための「カンニングアルゴリズム（cheater algorithm）」と呼ぶ仮想のモデルを検討する。このカンニングアルゴリズムは下式で表される見積もりＳｋ（ｋ∈｛Ａ，Ｂ｝）に従ってプレイするスロットマシンを選択する。
【００７４】
【数１７】
0006536957.tif 000019
【００７５】
ここでＸｋ，ｉはランダムな変数である。時刻ｔ＝ＮにおいてＳＡ＞ＳＢである場合、時刻ｔ＝Ｎ＋１においてはスロットマシンＡをプレイする。時刻ｔ＝ＮにおいてＳＢ＞ＳＡである場合には、時刻ｔ＝Ｎ＋１においてはスロットマシンＢをプレイする。時刻ｔ＝ＮにおいてＳＡ＝ＳＢである場合は、時刻ｔ＝Ｎ＋１ではスロットマシンＡ、Ｂからランダムに選んでプレイする。このアルゴリズムは、時刻ｔにおける両方のスロットマシンの結果を時刻ｔ−１においてどちらのスロットマシンが使用されたかに注意を払わずに利用していることに着目されたい。換言すれば、このアルゴリズムは不正行為を働いているのである。つまり、ここでは両方のスロットマシンでプレイして両方の結果を得ているのに、一時点では一つのスロットマシンでしかプレイしていないと宣言しているからである。
【００７６】
Ｘｋの期待値及び分散を夫々Ｅ（Ｘｋ）＝μｋ及びＶ（Ｘｋ）＝σ２ｋで表す。ここで、μｋは先に定義したＰｋと同じである。中心極限定理より、Ｓｋはガウス分布を有し、Ｅ（Ｓｋ）＝μｋＮ及びＶ（Ｓｋ）＝σ２ｋＮとなる。ここで新たに変数Ｓ＝ＳＡ−ＳＢを定義すれば、Ｓはガウス分布を有しており、下式の値を与える。
【００７７】
【数１８】
0006536957.tif 000020
【００７８】
図４から、スロットマシンＢは相対的に低い報酬確率を持っているのであるが、このスロットマシンをプレイする確率はＱ（Ｅ（Ｓ）／σ（Ｓ））で表すことができる。ここで、Ｑ（ｘ）はＱ関数である。これより下式が得られる。
【００７９】
【数１９】
0006536957.tif 000021
【００８０】
ここで、
【００８１】
【数２０】
0006536957.tif 000022
【００８２】
である。
【００８３】
Chernoff上界（Chernoff bound）Ｑ（ｘ）≦（１／２）ｅｘｐ（−ｘ２／２）を使用すれば、カンニングアルゴリズムの累積された損失（loss）を定量化する測定量の上界（「regret」と呼ぶ）を下式のようにして計算することができる。
【００８４】
【数２１】
0006536957.tif 000023
【００８５】
ここで、Ｎが大きくなるにつれてregretは定数になることに注意されたい（式（３１）参照）。
【００８６】
「カンニング」の結果を使用して、ＡＳＤＭ動作を同じように計算することができる。ここでは以下のような結果を得る。
【００８７】
【数２２】
0006536957.tif 000024
【００８８】
ここでもＸｋ，ｉはランダムな変数である。従って下式が得られる。
【００８９】
【数２３】
0006536957.tif 000025
【００９０】
新たな変数Ｓ＝ＳＡ−ＳＢ、Ｎ＝ＮＡ＋ＮＮ及びＤ＝ＮＡ−ＮＮを使用して更に下式を得る。
【００９１】
【数２４】
0006536957.tif 000026
【００９２】
条件Ｋ＝Ｋ０及びσＡ＝σＢ≡σが満足される場合には、下式を得る。
【００９３】
【数２５】
0006536957.tif 000027
【００９４】
及び
【００９５】
【数２６】
0006536957.tif 000028
【００９６】
ここで
【００９７】
【数２７】
0006536957.tif 000029
【００９８】
である。
【００９９】
ＡＳＤＭ動作のregretを以下のようにして計算することができる。
【０１００】
【数２８】
0006536957.tif 000030
【０１０１】
ＡＳＤＭ動作のregretもＮが増大するにつれて定数になることに注意されたい。
【０１０２】
非特許文献９で与えられたＭＡＢのための最適なアルゴリズムはｌｏｇ（Ｎ）に比例するregretを有することが知られている。このregretにはＮが増大したときの有限な上界はない。このようになるのは、このアルゴリズムでは低報酬のスロットマシンをプレイし続け、正しくない判定の確率が確実に０になっていくようにするためである。regretが定数になるということは、ＡＳＤＭの動作では正しくない判定の確率はほぼ０であるが完全にはゼロにはならないことを意味する。しかしながら、意思決定が必要となる現実の状況においては報酬確率はしばしば変化し、長期的な挙動は多くの実際的な用途では重要でないと考えられるだろう。
【０１０３】
＜シミュレーション結果＞
ＳＯＦＴＭＡＸは効率的な意思決定のための良好なアルゴリズムとして良く知られているのであるが（非特許文献２７）、コンピュータシミュレーションから、ほとんど全ての場合、パラメータＫ０（＝（μＡ＋μＢ）／２）を使ったＡＳＤＭは最適パラメータμｏｐｔを使ったＳＯＦＴＭＡＸアルゴリズムよりも高い報酬を獲得できることが確認された。図２にＡＳＤＭとＳＯＦＴＭＡＸアルゴリズムとの性能比較の例を示す。図５（ａ）に示すグラフの縦軸はregretの値を示し、横軸はＫの値を示す。図５（ｂ）のグラフはＡＳＤＭとＳＯＦＴＭＡＸとの性能比較を示す。その縦軸はregret（１０００サンプルの平均値）を示し、横軸はプレイの回数を示す。水平の点線はＫ０を用いたＡＤＳＭの上界（式（４３））を示す。ここで報酬ＰＤＦについては、μＡ＝０．５、μＢ＝０．６及びσ＝０．２とした正規分布Ｎ（μＡ，σ２）及びＮ（μＢ，σ２）を使用した。コンピュータシミュレーションはＴｈ＝Ｘ０及びδ＝ｓｉｎ（π／２＋πｔ）の条件のもとに行った。
【産業上の利用可能性】
【０１０４】
以上説明したように、本発明の意思決定装置ＡＳＤＭは、ＴＯＷアルゴリズムを素子レベルで実現し、その構成要素となっている原子スイッチの特徴から小型化、高速化が可能である。従って、本発明はＭＡＢでモデル化できる多くの分野に応用可能であり、またサイズ、速度、コスト等の点で従来技術では対応が困難であった新たな応用分野への適用も大いに期待できる。
【先行技術文献】
【非特許文献】
【０１０５】
【非特許文献１】Castro L N. (2007) Fundamentals of natural computing: an overview. Physics of Life Reviews 4: 1-36.
【非特許文献２】Kari L, & Rozenberg G. (2008) The many facets of natural computing. Communications of the ACM 51: 72-83.
【非特許文献３】Terabe K, Hasegawa T, Nakayama T, & Aono M. (2005) Quantized conductance atomic switch. Nature 433: 47-50.
【非特許文献４】Robbins H. (1952) Some aspects of the sequential design of experiments. Bull Amer Math Soc 58: 527-536.
【非特許文献５】Thompson W. (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25: 285-294.
【非特許文献６】Gittins J, & Jones D. (1974) Dynamic allocation index for the sequential design of experiments（ Gans, J. Progress in Statistics North Holland, 241-266所収）
【非特許文献７】Gittins J. (1979) Bandit processes and dynamic allocation indices. J R Stat Soc B 41: 148-177.
【非特許文献８】Agrawal R. (1995) Sample mean based index policies with O(log n) regret for the multi-armed bandit problem. Adv Appl Prob 27: 1054-1078.
【非特許文献９】Auer P, Cesa-Bianchi N, & Fischer P. (2002) Finite-time analysis of the multiarmed bandit problem. Machine Learning 47: 235-256.
【非特許文献１０】Lai L, Jiang H, & Poor H. V. (2008) Medium access in cognitive radio networks: a competitive multi-armed bandit framework. Proc. of IEEE 42nd Asilomar Conference on Signals, System and Computers, 98-102.
【非特許文献１１】Lai L, Gamal H. E, Jiang H, & Poor H. V. (2011) Cognitive medium access: exploration, exploitation, and competition. IEEE Trans. on Mobile Computing 10: 239-253.
【非特許文献１２】Agarwal D, Chen B.-C, & Elango P. (2009) Explore/exploit schemes for web content optimization. Proc of ICDM2009, http://dx.doi.org/10.1109/ICDM.2009.52.
【非特許文献１３】Kocsis L, & Szepesv´ari C. (2006) Bandit based monte-carlo planning, In: Carbonell, J. G. et al., 17th European Conference on Machine Learning, Lecture Notes in Artificial Intelligence 4212, Springer, 282-293.
【非特許文献１４】Gelly S, Wang Y, Munos R, & Teytaud O. (2006) Modification of UCT with patterns in Monte-Carlo Go. RR-6062-INRIA, 1-19.
【非特許文献１５】Kim S-J, Aono M, & Hara M. (2010) Tug-of-war model for multi-armed bandit problem, In: Calude C. et al. Unconventional Computation, Lecture Notes in Computer Science 6079, Springer, 69-80.
【非特許文献１６】Kim S-J, Aono M, & Hara M. (2010) Tug-of-war model for the two-bandit problem: Nonlocally-correlated parallel exploration via resource conservation. BioSystems 101: 29-36.
【非特許文献１７】Kim S-J, Nameda E, Aono M, & Hara M. (2011) Adaptive tug-of-war model for two-armed bandit problem. Proc of NOLTA2011, 176-179.
【非特許文献１８】Kim S-J, Aono M, Nameda E, & Hara M. (2011) Amoeba-inspired tug-of-war model: Toward a physical implementation of an accurate and speedy parallel search algorithm. Technical Report of IEICE (CCS-2011-025), 36-41.
【非特許文献１９】Aono M, Kim S-J, Hara M, & Munakata T. (2014) Amoeba-inspired tug-of-war algorithms for explorationexploitation dilemma in extended bandit problem. BioSystems 117: 1-9.
【非特許文献２０】Kim S-J, & Aono M. (2014) Amoeba-inspired algorithm for cognitive medium access. NOLTA 5: 198-209.
【非特許文献２１】Kim S-J, Aono M, & Nameda E. (2014) Efficient decision-making by volume-conserving physical object. New J Phys, http://arxiv.org/abs/1412.6141.
【非特許文献２２】Kim S-J, Naruse M, Aono M, Ohtsu M, & Hara M. (2013) Decision maker based on nanoscale photo-excitation transfer. Sci Rep 3: 2370.
【非特許文献２３】Naruse M, Nomura W, Aono M, Ohtsu M, Sonnefraud Y, Drezet, A, Huant S, & Kim S-J. (2014) Decision making based on optical excitation transfer via near-field interactions between quantum dots. J Appl Phys 116: 154303.
【非特許文献２４】Naruse M, Berthel M, Drezet A, Huant S, Aono M, Ohtsu M, Hori H, & Kim S-J. (2015) Single photon decision maker Sci Rep.
【非特許文献２５】Tsuruoka T, Hasegawa T, Terabe K, & Aono M. (2012) Conductance quantization and synaptic behavior in a Ta2O5-based atomic switch. Nanotechnology 23: 435705.
【非特許文献２６】Sutton R, & Barto A. (1998) Reinforcement Learning: An Introduction, MIT Press.
【非特許文献２７】Vermorel J, & Mohri M. (2005) Multi-armed bandit algorithms and empirical evaluation（Gama J., et al. 16th European Conference on Machine Learning. Lecture Notes in Artificial Intelligence 3720, Springer, 437-448所収）
【非特許文献２８】Kim S-J, & Aono M. (2015) Decision maker using coupled incompressible-fluid cylinders. Special issue of Advances in Science, Technology and Environmentology B11: 41-45, http://arxiv.org/abs/1502.03890.
【非特許文献２９】Kim S-J, Naruse M, & Aono M. (2015) Harnessing natural fluctuations: analogue computer for efficient socially-maximal decision-making. eprint arXiv, http://arxiv.org/abs/1504.03451.
【図１】
0006536957.tif 000031
【図２】
0006536957.tif 000032
【図３】
0006536957.tif 000033
【図４】
0006536957.tif 000034
【図５】
0006536957.tif 000035