(57)【要約】【課題】行動の選択のための空間が非常に大きいとき、学習精度、学習効率を高める学習機構付意思決定システムの開発。【解決手段】状況を理解して、その状況に適応した行動を決定する意思決定システムにおいて、行動選択肢が膨大な時、意思決定のためのルールを学習する学習部と、膨大な行動選択肢に対して階層クラスタリングを行う行動クラスタリング部を有し、前記学習部の学習と、前記行動クラスタリング部のクラスタリングが動的に行われることを特徴とする。【選択図】        図１
2007164406.tif 000002
【特許請求の範囲】
【請求項１】
状況を理解して、その状況に適応した行動を決定する意思決定システムにおいて、行動選択肢が膨大な時、意思決定のためのルールを学習する学習部と、膨大な行動選択肢に対して階層クラスタリングを行う行動クラスタリング部を有し、前記学習部の学習と、前記行動クラスタリング部のクラスタリングが動的に行われることを特徴とする学習機構付意思決定システム。
【請求項２】
前記行動クラスタリング部において、行動のクラスタリングに用いる属性に連続値と離散値を利用でき、連続値に対して離散化するために量子化部を有することを特徴とする請求項１に記載の学習機構付意思決定システム。
【請求項３】
前記学習部において、強化学習機構を用いて、同一クラスにおける未経験の行動に対する、状態行動価値に対しても強化する方式を有し、かつ前記行動クラスタリング部のクラスタリングに於いて、この状態行動価値を利用して類似性を求める方式を有しクラスタリングを行うことを特徴とする請求項１に記載の学習機構付意思決定システム。
【請求項４】
前記行動クラスタリング部において、行動の都度クラスタリングを行うのではなく、クラスタリングの更新を一定の間隔で行うことを特徴とする前記請求項１に記載の学習機構付意思決定システム。
【発明の詳細な説明】
【技術分野】
【０００１】
近年、知的ソフトウェア（ソフトウェア・エージェント）への期待が高まっている。いろいろな状況において、自律的に判断をして外界に対して行動を行うソフトウェアーである。ロボットや、人を知的に支援する意思決定支援システムに多く利用されている。
【背景技術】
【０００２】
知的ソフトウェア（以下エージェントと呼ぶ）として構築するためには、状況を適確に判断して、それに即した最適な行動を効率よく決めていく必要がある。システム設計時に全ての状況に対して、それに対応する行動選択を設定しておくことは、実問題の規模では不可能に近い。従って、そのエージェントが色々経験をつみながら学習して行き、状況に次第に適応していく機能が必要になってくる。この機能を実現する方法として、近年、強化学習という方法が注目を集めている。
2007164406.tif 000003
【０００３】
【数１】
2007164406.tif 000004
ここで、γ(0≦γ≦1)は割引率、α(0≦α≦1)は学習率である。この手法は、環境がマルコフ性を満たすときに状態行動の価値が最適解へと収束することを保証している。
しかし、状態Ｓは基本的に離散値パラメータの組合せで表現され、有限状態空間上をベースにしている。そのため、連続値パラメータに対しても、何らかの量子化（離散化）を行う必要はあり、色々な手法が提案されている。また、行動価値Ｑ（ｓｔ，ａｔ）の空間は状態空間とその状態における選択可能な行動空間の組合せになる。行動パラメータが連続値の場合（制御量としての速度、圧力など）の量子化するアイデアは、状態空間量子化と同様、色々行われている。しかし、状態Ｓについて取り得る行動が離散であっても何百、何千とある場合の対応はなされていない。
【非特許文献１】[Watkins 92] Watkins,C.J.H.&Dayan,P.:Technical Note:Q-Learning,Machine,vol.8, pp.55-68(1992)
【非特許文献２】[RL 98] Richard S.Sutton,Andrew G.Barto： Reinforcement Learning,MIT press(1998)
【非特許文献３】[Kohonen 96] T.コホネン著, 徳高平蔵  岸田悟  藤村喜久朗  訳:自己組織化マップ:シュプリンガー・フェアラーク東京(1996)
【非特許文献４】[吉岡  03] 吉岡信和  田原康之  本位田真一  著:モバイルエージェントによる柔軟なコンテンツ流通を実現するアクティブコンテンツ:情報処理学会論文誌(2003)
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は前記のように、行動の選択のための空間が非常に大きいとき、学習精度、学習効率を高めることを目的になされたものである。
【課題を解決するための手段】
【０００５】
(1)、状況を理解して、その状況に適応した行動を決定する意思決定システムにおいて、行動選択肢が膨大な時、意思決定のためのルールを学習する学習部と、膨大な行動選択肢に対して階層クラスタリングを行う行動クラスタリング部を有し、前記学習部の学習と、前記行動クラスタリング部のクラスタリングが動的に行われることを特徴とする学習機構付意思決定システム。
(2)、前記行動クラスタリング部において、行動のクラスタリングに用いる属性に連続値と離散値を利用でき、連続値に対して離散化するために量子化部を有することを特徴とする前記(1)に記載の学習機構付意思決定システム。
(3)、前記学習部において、強化学習機構を用いて、同一クラスにおける未経験の行動に対する、状態行動価値に対しても強化する方式を有し、かつ前記行動クラスタリング部のクラスタリングに於いて、この状態行動価値を利用して類似性を求める方式を有しクラスタリングを行うことを特徴とする前記(1)に記載の学習機構付意思決定システム。
(4)、前記行動クラスタリング部において、行動の都度クラスタリングを行うのではなく、クラスタリングの更新を一定の間隔で行うことを特徴とする前記(1)に記載の学習機構付意思決定システム。
【発明の効果】
【０００６】
上記のようなモデルで実験した結果、非常に高い学習効率で、学習精度のよい結果を得ることができ、このような、大規模な問題に対して有効な方式である。
つまり、従来方法では、学習が収束しないケースが多いが、本発明の方法では収束性が格段に向上する。また、従来のクラスタリングで行うより行動状態価値の類似性によるクラスタリングを組み合わせて階層型クラスタリングを用いる方が学習精度が一段と向上できる。
【発明を実施するための最良の形態】
【０００７】
図１に基づいて本発明システムの作用を説明する。
本発明の意思決定システムとしてエージェント１は環境２から得られる情報（状態情報）を基に最適な意思決定を行い行動する。その結果、環境に変化が生じ、またその状況を認知し最適な意思決定を行い行動するというサイクルを繰り返す。その間にエージェントはある望ましい状態（望ましくない状態）になることにより、報酬（罰）をうることになる。
つまり、環境２から状態情報を状態認識部１１で知覚し、その状態が、どの状態空間であるかを認識する。当然このとき、状態空間パラメータが連続値である場合、量子化する機構は組み込まれている。認識された状態ｓｔをもとに、行動選択部１３においてその状態での状態行動価値Ｑ（ｓｔ，ａｔ）から行動を選択する。行動を行うことにより環境２は変化する。このとき環境からの報酬（罰）をベースに状態行動価値Ｑ（ｓｔ，ａｔ）を数１にそって更新する。
本発明では、行動選択肢が非常に大きい場合を想定している。そこで、行動空間を減少させるために行動クラスタ部１４が作動し数多くある行動を階層的にクラスタ分類しその抽象クラスを用いることで行動選択、学習の効率化、高精度化を実現する。
本発明野の特徴の一つとして状態行動価値の類似性に基づいてクラスタリングを行うことが挙げられる。この方式を図２に基づいて説明する。
２１に於いて、全ての行動をALリストに格納する。２２に於いて、そのリストのトップの行動取り出し２１１のループの終端までの処理をALリストが空になるまで行う。まず、２３でa'が一度でも選択されたことのある行動かチェックし、もし一度も選択されていない行動なら２１２の処理を行う（後述）。一度でも経験ある行動ならば２４のようにALから取り出された行動a'とALに残されている行動との状態行動価値の類似度を全て調べる。類似性を計算する処理（２５）、つまり行動ａｉとajnの類似性は以下の数２で求める。
【０００８】
【数２】
2007164406.tif 000005
2007164406.tif 000006
行動ａ‘とＡＬの中にある行動との類似性で最も類似性の高い（σが最も小さい）行動ａ“を選ぶ（２７）。２８においてａ’が既にクラスに属しているならば（２８）、行動ａ”もａ‘と同じクラスとする（２９）。ａ’が、未だどのクラスにも所属していないのならば新しいクラスを作って、ａ‘とａ“をそのクラスに所属させる。２１２は、図３において行動ａ’が一度も選択されなかったケースであり、その場合は、ａ‘に対して新しいクラスを作成して単独のクラスとする。
【０００９】
以上、状態行動価値の類似性によるクラスタリングについて述べたが、図１の学習部12と連携しておく必要がある。つまり、非常に数多くある行動に対して、実際に選択行動できるものには限りがあり、状態行動価値を学習できない行動が多くでてきてしまう。そのために、学習部に於いては、ある行動が行われ、それによって、状態行動価値が更新される際に、その行動と同じクラスにある行動に対する状態行動価値もある影響度をもって更新する方式をとる。このことにより、未経験な行動に対しても、ある程度、学習できることになる。
学習における更新式を以下の数３のようにする。
【００１０】
【数３】
2007164406.tif 000007
ここでζ(0≦ζ≦1)は選択された行動の影響度を表す。影響度は、実行された行動が同じクラスに属する別の行動に与える影響の度合いであり、この値が高くなれば学習の速度が増加する。このような学習を行う理由は、同一クラス内の行動は類似しており、選択された行動以外にも報酬を伝播することで、学習効率を向上させることができると考えたからである。ただし、学習の初期段階では、同一クラス内に属する行動が本当に類似した行動かどうかの判断が難しいため、なるべく低い値に設定する必要がある。
以上のように、類似度によるクラスタリングにより、学習効率を向上させることが出来る。しかし、行動空間が非常に大きい場合、必ずしも行動空間がこのクラスタリングによって十分に小さくなる保証はない。そこで、階層型クラスタリングを導入する。
【００１１】
図３において、3-1は類似度によるクラスタリングを示している。図４において、3-2は階層型クラスタリングを示している。つまり、3-2の下位クラスは行動属性によるクラスタリングで事前にクラスタリングを行う。この行動属性によるクラスタリングは、通常の多変量解析によるクラスタリングやK-mean法によるクラスタリングなど、既存のクラスタリング手法は利用できる。3-2の下位クラスのC1、C2、…は通常のクラスタリングで行ったクラスであり、このC1、C2、…を図２の21の行動リストとして、類似度クラスタリングを行いC'1、C'2を得る。学習の方式は、下位階層の行動状態価値の計算方法は前記（１）式の通り行う。また、上位クラスの状態行動価値の計算は、そのクラスに属する下位クラスの状態行動価値の平均値として計算することとが出来る。
2007164406.tif 000008
以上により行動空間が非常に大きい問題に対しても効率よく学習することが出来る。
【実施例１】
【００１２】
本発明の中心である図１の行動クラスタ部１４について以下の実施例に基づいて詳述する。
今、ソフトウェアーエージェントを想定する。このエージェントは幾種類かのコンテンツ（例えば映像コンテンツなど）をもっており、これを各顧客にセールスにいくエージェントである。このエージェントは数多くいる顧客に対し、どの顧客を訪ねていけば効率の良いセールス活動ができるかを学習する。従来ネットワーク上でその様な行動をするには、全ての顧客に対してブロードキャストすれば良い。しかし、将来的にはこのような方式は難しくなるト考えられる。つまり各顧客に対し多くのエージェントがブロードキャスト的に訪問されること自体非常に煩わしく、またセキュリティの面でも問題があるため、その訪問に対して制約およびコストをかけるという方式に移行していくことを想定している。従って闇雲に顧客を訪問するのではなく、ある戦略のもとに訪問することが必要となってくる。また、コンテンツの販売に関しても数限りなくコピーして販売できるのではなく、販売元から許可された本数のみコピーし販売できるという前提に立っている。
【００１３】
以上のような前提のもと、エージェントの動作を述べる。コンテンツを販売するエージェントをセールスエージェントと呼ぶことにする。このセールスエージェントの動作を図５に添って説明する
図５の41においてセールスエージェントは５種類の商品のを受け取る（商品リストに格納する）。セールス基地をスタートする。
図５の42に於いて商品の販売対象となる顧客を選択する。このとき顧客の選択方法は上位階層(類似度クラスタで作成したクラスタ)から状態行動価値Q(ｓt,a)の高いクラスを選択し、次にそのクラスに属する行動クラス（通常のクラスタ処理で作成したクラスタ）そのクラスの状態行動価値が高いクラスを選択し、最終的にそのクラスに含まれる顧客集合（木構造のリーフ）の中からランダムで一つの顧客を選択する。このときの状態ｓｔは商品の品揃え状態であり行動ａは移動先（顧客の属するクラスを指している。選択後、商品郡（コンテンツ）を持ったコンテンツを持って、顧客の下へ移動する。
図５の43においてエージェントは訪問した顧客との交渉を行い、商品を販売する。もし、顧客にある商品が売れた時は、その商品を商品リストから削除する（同じ種類の商品を持っている場合は一つ減ずる）。これによって状態ｓｔが変化する。
図５の44に於いて、交渉結果に対しての報酬を得る。その顧客に対して商品は一つも売れなかった時は“０”。商品が売れた場合は“売れた商品の数＊０．２”の報酬を得る。また、その顧客に対して、一回の交渉ごとに“−０．１”の報酬も同時にえることとする。このようにしてセールスエージェントは交渉戦略を学習する。
図５の45において、次の顧客を訪れるかどうかを判断する。この実施例では、商品リストが空になるか、ある一定の回数顧客を訪問してしまったら、顧客の訪問をやめ、セールス基地に戻り、改めて商品の品揃えを整えて、上記の処理を繰り返す。このセールス基地を出発して、セールス基地に戻る一サイクルを１エピソードと呼ぶことにする。
図５の46はある一定のエピソード回数に達したかを判断し、達成したら学習を終了する。
この動作実験を実世界上で行うには大変なコストがかかるために下記のような顧客モデルを計算機上で作成して本発明の有用性を示す
【００１４】
＜顧客モデル＞
１．性別{男性,女性}(離散値)
２．年齢{15~65}(連続値)
３．年収{100~1000}(連続値)
４．職業{学生,会社員,無職}(離散値)
５．商品の嗜好{興味がある,普通,興味がない}(離散値)
ただし商品の嗜好は商品の数だけ存在する。今回は10個の商品データを使用するので商品の嗜好も10個存在する。商品はロック,クラシック,ジャズ,ブルース,メタル,演歌,ヒーリング,J-POP,トラッド,R&Bとする。顧客モデルのパラメータはセールスエージェントが自由に見ることができる。ただし、見る事のできないパラメータに購入確率がある。購入確率は嗜好の度合いにより5~95(%)の整数値で表され商品と同じ数だけ存在する。
【産業上の利用可能性】
【００１５】
本発明は、今後インターネットでの各種コンテンツ販売機能として広大なコンテンツ流通機構に利用できる。
【図面の簡単な説明】
【００１６】
【図１】本発明の機能構成図である。
【図２】類似度クラスタリングの処理フローである。
【図３】１段のクラスタリングを示したものである
【図４】２段の階層クラスタリングを示したものである
【図５】セールスエージェントの動作フローである。
【符号の説明】
【００１７】
１        エージェント
２        環境
１１      状態認識部
１２      学習部
１３      行動選択部
１４      行動クラスタ部
１５      量子化部
3-1        類似度クラスタ部
3-2            階層型クラスタ部
【図１】
2007164406.tif 000009
【図２】
2007164406.tif 000010
【図３】
2007164406.tif 000011
【図４】
2007164406.tif 000012
【図５】
2007164406.tif 000013