(57)【要約】【課題】損失を低減するための行動を指示する行動決定関数を効率的に算出する。【解決手段】ある対象に対して採るべき行動を示す行動決定関数を生成することによって、利用者の行動を支援するシステム１０を提供する。このシステム１０は、対象に対して既に採られた複数の行動のそれぞれについて、当該行動を対象に対して採った結果として生じたコストを、行動決定関数を生成するための訓練データとして取得するデータ取得部１１０と、対象に対して行動を採った結果として得られるコストの期待ショートフォールを最小化する行動決定関数を、訓練データに基づいて生成する関数生成部１２０とを備える。【選択図】図１
2007133477.tif 000002
【特許請求の範囲】
【請求項１】
ある対象に対して採るべき行動を示す行動決定関数を生成することによって、利用者の行動を支援するシステムであって、
前記対象に対して既に採られた複数の行動のそれぞれについて、当該行動を前記対象に対して採った結果として生じたコストを、前記行動決定関数を生成するための訓練データとして取得するデータ取得部と、
前記対象に対して行動を採った結果として得られるコストの期待ショートフォールを最小化する前記行動決定関数を、前記訓練データに基づいて生成する関数生成部と
を備えるシステム。
【請求項２】
前記関数生成部は、
与えられた値をコストのバリュー・アット・リスクとした場合において、前記バリュー・アット・リスクを超えるコストの合計に基づく指標値を最小化する前記行動決定関数を、前記訓練データに基づいて算出してメモリに記憶する第１算出部と、
前記第１算出部によって算出された行動決定関数を前記メモリから読み出して、前記行動決定関数によって示される行動を採った結果として生じるコストのバリュー・アット・リスクを、前記訓練データに基づいて算出して、前記第１算出部に与える第２算出部と、
前記指標値に基づく期待ショートフォールが、予め定められた範囲内の値に収束したか否かを判定する収束判定部と
を有し、前記期待ショートフォールが収束したことを条件に、前記第１算出部によって算出された前記行動決定関数を出力する
請求項１に記載のシステム。
【請求項３】
前記関数生成部は、前記訓練データに基づいて、コストの期待値を最小化する前記行動決定関数を算出する第３算出部を更に有し、
前記第１算出部は、前記訓練データに含まれるそれぞれの行動に対応するコストから、与えられた前記バリュー・アット・リスクを差し引いて前記第３算出部に与えることにより、前記指標値を最小化する前記行動決定関数を算出する
請求項２に記載のシステム。
【請求項４】
前記第１算出部は、与えられた前記バリュー・アット・リスクをα´とし、以下の式（１）によって算出される指標値ＣＥα´（θ）を最小化する前記行動決定関数のパラメータθを算出し、
前記第２算出部は、算出された前記パラメータθに対し、以下の式（２）および式（３）によって算出されるαＥβ（θ）をバリュー・アット・リスクとして算出して、前記第１算出部に与え、
前記収束判定部は、以下の式（４）によって算出された値が、予め定められた範囲内の値に収束したか否かを判定する
請求項２に記載のシステム。
但し、式（１）から式（４）を以下のように定義する。
【数１】
2007133477.tif 000021
但し、前記訓練データにおける行動の対象を、ｘ（１）からｘ（ｎ）とし、前記行動決定関数を、対象ｘを入力として、パラメータθに応じて採るべき行動ｙを決定するための関数ｈとし、前記訓練データにおける前記コストを、ｃ（ｘ（ｉ），ｈ（θ））とし、［ｘ］＋を、ｘが正の場合はｘを、それ以外の場合には０を返す関数とする。
【数２】
2007133477.tif 000022
【数３】
2007133477.tif 000023
【数４】
2007133477.tif 000024
但し、引数によって示される条件が満たされる場合に１を、当該条件が満たされない場合に０を採る関数を関数Ｉとし、バリュー・アット・リスクを越えるコストが発生する確率を定数βとする。
【請求項５】
前記第１算出部は、以下の式（５）によって、前記訓練データにおける対象ｘ（ｉ）および行動ｙに対するコストｃ（ｉ）から、与えられた前記バリュー・アット・リスクであるα´を差し引くことにより、コストｃ´（ｉ）を算出して前記第３算出部に与え、
前記第３算出部は、以下の式（６）によって示されるコストＣ´Ｅα´（θ）を最小化する前記行動決定関数を算出する請求項３に記載のシステム。但し、式（５）および式（６）を以下のように定義する。
【数５】
2007133477.tif 000025
【数６】
2007133477.tif 000026
【請求項６】
前記システムは、ある検査結果を有する患者に対する治療方針の決定を支援するシステムであって、
前記行動決定関数は、前記患者に対する治療方針を決定する関数であり、
前記データ取得部は、既に治療した複数の患者のそれぞれについて、当該患者において生じた損失の大きさを、前記訓練データとして取得し、
前記関数生成部は、治療によって生じる損失の期待ショートフォールを最小化する前記行動決定関数を、前記訓練データに基づいて生成する
請求項１に記載のシステム。
【請求項７】
ある対象に対して採るべき行動を示す行動決定関数を生成することによって、利用者の行動を支援する方法であって、
前記対象に対して既に採られた複数の行動のそれぞれについて、当該行動を前記対象に対して採った結果として生じたコストを、前記行動決定関数を生成するための訓練データとして取得するステップと、
前記対象に対して行動を採った結果として得られるコストの期待ショートフォールを最小化する前記行動決定関数を、前記訓練データに基づいて生成するステップと
を備える方法。
【請求項８】
ある対象に対して採るべき行動を示す行動決定関数を生成することによって、利用者の行動を支援するシステムとして、情報処理装置を機能させるプログラムであって、
前記情報処理装置を、
前記対象に対して既に採られた複数の行動のそれぞれについて、当該行動を前記対象に対して採った結果として生じたコストを、前記行動決定関数を生成するための訓練データとして取得するデータ取得部と、
前記対象に対して行動を採った結果として得られるコストの期待ショートフォールを最小化する前記行動決定関数を、前記訓練データに基づいて生成する関数生成部と
して機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、利用者の行動を支援するシステムに関する。特に、本発明は、行動決定関数の生成によって利用者の行動を支援するシステムに関する。
【背景技術】
【０００２】
データマイニングの基礎技術として分類学習が研究されている。分類学習は、過去にある対象に対して採った行動の結果を示す情報（以下、訓練データという）に基づいて、その対象について将来採るべき行動を出力することを目的とする。この技術を応用すれば、過去の事象によれば統計的に最も適切な（例えば誤りの回数を最小化する）行動を利用者に示唆し、利用者の行動を支援することができる。
【０００３】
分類学習は、例えば、以下のように様々な技術分野に応用可能である。
（１）医療分野における診断
対象：患者の検査結果
行動：ある治療を行う、または、その治療を行わない
この例における訓練データは、ある検査結果を有する患者に対して過去にある治療を行った場合に治療が成功したか否かを示す情報となる。分類学習によれば、このような訓練データに基づいて、将来の患者に対する治療の適否を予測できる。
【０００４】
（２）金融分野における与信審査
対象：キャッシングの申込者のプロファイル
行動：融資を許可する、または、融資を拒否する
この例における訓練データは、あるプロファイルを有する申込者に対して過去に融資を行った場合に債権が回収できたか否かを示す情報となる。分類学習によれば、このような訓練データに基づいて、将来ある申込者に融資すべきか否かを判断できる。
【０００５】
（３）検索エンジンにおけるトピック分類
対象：ニュースのウェブ・ページ
行動：経済分野に分類、スポーツ分野に分類、または、政治分野に分類
この例における訓練データは、あるウェブ・ページを過去にある分野に分類した場合に、その分類が正しかったか否かを示す情報となる。分類学習によれば、このような訓練データに基づいて、将来作成されるウェブ・ページを適切に分類できる。
【０００６】
以上のような分類学習においては、通常、対象に対して採るべき行動を正しく予想することを目的とする。即ち、行動の誤り回数や誤り確率を最小化することを目的としている。
【０００７】
しかしながら、問題によっては、単に誤り回数を最小化するだけでは十分でない場合がある。例えば上述の（１）の例の場合、健康な患者を病気と判断して不要な治療を行った結果として生じる損失（以下、コストと呼ぶ）、病気の患者を放置して死に至らしめるコストとは、明らかに異なる。また、患者の社会的地位に応じてコストが異なる場合もあり得る。同様に、上述の（２）の例の場合、優良な申込者に対する融資を拒否した結果として生じるコストは利息のみであるが、不良な申込者に対する融資を許可した結果として生じるコストは融資額全体となり得る。この場合も、それぞれの融資額や不良度合いに応じて、コストは異なってくる。
【０００８】
このような、対象および行動毎にコストが異なり、かつ、それらが予測時に未知である場合に適用可能な技術として、従来、コスト考慮型学習(Cost-Sensitive Learning)が提案されている（非特許文献１から９を参照。）。コスト考慮型学習は、行動の誤り率を最小化するのではなく、コストの期待値を最小化することを目的としているので、より広範囲の問題を扱うことができる。
【０００９】
以下、コスト考慮型学習について更に具体的に述べる。まず、以下の（１）から（３）によって、コスト考慮型学習が対象とする問題を定義する。
（１）コスト関数
コストとは、例えば、ある対象に対して採った行動の結果として生じた損失を表す指標である。Xを対象の集合(たとえばX=RM)とし、Yをこれらに対して採り得る行動の集合とする。但し、Ｙは離散的で有限な集合とする。対象x∈Xに対し、行動y∈Yを採った結果として生じるコストをc(x,y)∈Rとおく。
【００１０】
例えば、ある検査結果xであった患者に、ある治療yを行なったときに引き起こされる結果の悪さがc(x,y)となる。正しい治療ならc(x,y)は小さく、誤った治療なら大きくなる。この患者に対する治療としてyが非常に不適切で、死に至った場合、そのコストは非常に大きくなる。なお、初期の研究段階における問題設定(非特許文献２を参照。)では、コストがxに直接依存せず、潜在変数としてクラスを設け、コストはクラスと行動に依存して、しかもコストの大きさは既知であるような簡単なケースが扱われている。ここでは、より一般的な、対象によってコストが異なり、かつ、真のコスト関数c(x,y)は未知であるようなケースを扱う(非特許文献７などを参照。)。
【００１１】
（２）行動決定モデル
Ｘを対象の集合（たとえばＸ＝ＲＭ）とし、Ｙをこれらに対して採りうる行動の集合（離散的で有限）とする。対象ｘ∈Ｘに対し、行動ｙ∈Ｙを決定するために用いる関数を、以下の式（１）とする。
【数１】
2007133477.tif 000003
ここで、θはモデルのパラメータである。これを用いて通常、採るべき行動ｙ´は、以下の式（２）によって択一的に決定される。ｈ（ｘ，ｙ；θ）には、以下の式（３）のような確率的な制約が入っていてもよい。
【数２】
2007133477.tif 000004
【数３】
2007133477.tif 000005
即ち、対象ｘ∈Ｘが与えられたとき、これに対してこの場合、行動の決定は式（２）に代えて、式（３）によって確率的に行われてもよい。また、行動の決定が資源分散型、即ち、実際に採ることのできる行動がひとつではなくてｈ（ｘ，ｙ；θ）に割合に応じて資源を分散投資できるような場合も考えられるが、本発明の実施の形態では式（２）によって行動が択一的に決定されるものとする。
また、c(x,h(θ))を、xに対してh(x,y;θ)を用いて行動を決定した場合に引き起こされるコストとする。択一的アクションの場合(1)には、c(x,h(θ))は、以下の式（４）となる。
【数４】
2007133477.tif 000006
分散投資型のアクションの場合には、その定義は必ずしも自明ではないが、ここではもっとも簡単な場合としてc(x,h(θ))が、式（５）のように、それぞれのアクションからもたらされるコストが、投資量に比例するものとする。
【数５】
2007133477.tif 000007
【００１２】
（３）訓練データ
対象とコストはX×RYで定義された確率分布Dから一様に発生すると考え、Dからサンプリングされた、N個のデータの集合Eが訓練データとして与えられるとする。ここで、Eのi番目の訓練データe(i) = (x(i),{c(i)(x(i),y)}y∈Y)とする。x(i)∈Xは訓練データのi番目の対象とし、これに対するそれぞれのアクションy∈Yに対し、コストc(i)(x(i),y)が与えられているとする。
【００１３】
以上のような問題について、従来、コストを考慮するような分類問題に対しては、コストの期待値を最小化することを目的とした手法が用いられてきた。具体的には、データの分布Dに対する期待コスト（式（６））を最小化するようにθを決定したいところではあるが、実際には分布Ｄは分からないので、経験期待コスト（式（７））を最小化するようにパラメータθを決定することになる（非特許文献１、６、および、７を参照。）。
【数６】
2007133477.tif 000008
【数７】
2007133477.tif 000009
【００１４】
なお、対象とコストはX×RYで定義された確率分布Dから互いに独立に発生すると考え、Dからサンプリングされた、N個のデータの集合Eが訓練データとして与えられるとする。ここで、Eのi番目の訓練データe(i) = (x(i), {c(i)(x(i), y)}y∈Y)とする。x(i)∈Xは訓練データのi番目の対象とし、それぞれの行動y∈Yを採った場合のコストc(i)(x(i),y)が与えられているとする。
【００１５】
【非特許文献１】N. Abe and B. Zadrozny. An iterative method for multi-class cost-sensitive learning. In Proceedings of ACM SIGKDD Conference, 2004.
【非特許文献２】J. P. Bradford, C. Kunz, R. Kohavi, C. Brunk, and C. E. Brodley. Pruning decision trees with misclassification costs. In Proceedings of the 9th European Conference on Machine Learning (ECML), 1998.
【非特許文献３】P. Domingos. MetaCost: A general method for making classifier cost sensitive. In Proceedings of the 5th International Conference on Knowledge Discovery and Data Mining, pages 155-164, 1999.
【非特許文献４】C. Elkan. The foundations of cost-sensitive learning. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI), pages 973-978, 2001.
【非特許文献５】W. Fan, S. J. Stolfo, J. Zhang, and P. K. Chan. Ada-Cost: Missclassification cost sensitive boosting. In Proceedings of the 16th International Conference on Machine Learning (ICML), pages 97-105, 1999.
【非特許文献６】P. Geibel, U. Bredford, and F. Wysotzki. Perceptron and SVM learning with generalized cost models. Intelligent Data Analysis, 8(5):439-455, 2004.
【非特許文献７】B. Zadrozny and C. Elkan. Learning and making decisions when costs and probabilities are both unknown.In Proceedings of ACM SIGKDD Conference, 2001.
【非特許文献８】B. Zadrozny, J. Langford, and N. Abe. Cost-sensitive learning by cost-proportionate example weighting. In Proceedings of the 3rd International Conference on Data Mining (ICDM), pages 435-442, 2003.
【非特許文献９】鈴木. 正確な学習よりも得する学習- 誤分類コストを考慮する分類学習- (1)(2). 情報処理, 45(4-5), 2004.
【非特許文献１０】T. C. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.
【非特許文献１１】R. T. Rockafellar and S. Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 2(3):21-41, 2000.
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、リスク管理の立場から考えると、単に経験期待コストを最小化するというアプローチでは十分でない場合がある。訓練後、Ｍ個のデータに対して行動を採るものとする。Ｍが大きいときには、これらに対するコストの和はM・ＣＤ(θ)に近づくため、CE(θ)を学習の目的関数とすることに問題はないように思える。しかしながら、Ｍが比較的少ないため上記の近似が成り立たず、また、大きなコストの発生が致命的になるような状況を考えてみる。例えば、資金をどこに投資するべきかを決定するような問題の場合、大きな失敗が何度か連続して起きるということは、破産のリスクに直結する重大な問題である。起こる確率は小さいが、許容できないほど大きなコストが発生してしまうような可能性がある場合、ユーザーはそのリスクをなるべく回避することを望むであろう。
【００１７】
また、たとえば、同じだけのコスト期待値が望める２つの決定関数h1とh2があったとする。h1によってもたらされるコストの確率分布は期待値の周りに高いピークをもつが、h2によってもたらされるコストの確率分布は高コストの領域に、なだらかで裾野が厚い形をもっているとする。この場合、期待コストは等しくとも、望ましいのは、高いコストが発生してしまう可能性がより小さいh1のほうであろう。このような場合においては、経験期待コスト最小化では目的を正しく反映しているとはいえず、コストの分布を考慮して、リスクをより積極的に回避するような学習手法が望まれる。
そこで本発明は、上記の課題を解決することのできるシステム、方法、および、プログラムを提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【００１８】
上記課題を解決するために、本発明の実施形態においては、ある対象に対して採るべき行動を示す行動決定関数を生成することによって、利用者の行動を支援するシステムであって、対象に対して既に採られた複数の行動のそれぞれについて、当該行動を対象に対して採った結果として生じたコストを、行動決定関数を生成するための訓練データとして取得するデータ取得部と、対象に対して行動を採った結果として得られるコストの期待ショートフォールを最小化する行動決定関数を、訓練データに基づいて生成する関数生成部とを備えるシステム、当該システムとして情報処理装置を機能させるプログラム、および、当該システムによって利用者の行動を支援する方法を提供する。
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【００１９】
本発明によれば、損失を低減するための行動を指示する行動決定関数を、効率的に算出することができる。
【発明を実施するための最良の形態】
【００２０】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００２１】
図１は、行動支援システム１０の機能構成を示す。行動支援システム１０は、利用者がある対象について採るべき行動の決定を支援することを目的とする。一例として、行動支援システム１０は、医師が、ある検査結果を有する患者に対する治療方針の決定を支援することを目的とする。
【００２２】
行動支援システム１０は、訓練データＤＢ１００と、データ取得部１１０と、関数生成部１２０と、行動決定部１３０とを備える。訓練データＤＢ１００は、行動支援システム１０が行動決定関数を生成するための訓練データを記憶している。この訓練データは、例えば、ある対象に対して既に採られた複数の行動のそれぞれについて、当該行動をその対象に対して採った結果として生じたコストを示す。訓練データは、過去にある対象に対して行動した履歴に基づいて生成されてもよいし、各種のシミュレーションや実験の結果に基づいて生成されてもよい。医療方針の決定支援の例では、訓練データとは、既に治療した複数の患者のそれぞれについて、当該患者において生じた損失の大きさを示すデータである。
【００２３】
データ取得部１１０は、訓練データを訓練データＤＢ１００から取得して関数生成部１２０に提供する。関数生成部１２０は、ある対象に対して行動を採った結果として得られるコストの期待ショートフォールを最小化する行動決定関数を、訓練データに基づいて生成する。医療方針の決定支援の例では、行動決定関数は、患者に対する治療方針を決定する関数である。そして、行動決定関数は、治療によって生じる損失の期待ショートフォールを最小化するように生成される。この関数は、ある対象が与えられた場合に一つの治療方針を一意に出力してもよいし、複数の治療方針のそれぞれが妥当である程度を示す指標値を出力してもよい。
【００２４】
行動決定部１３０は、ある行動の対象が与えられた場合に、関数生成部１２０によって生成された行動決定関数に基づいて、その対象に対して採るべき行動を決定し、利用者に通知する。これにより、利用者は、期待ショートフォールという、現実の事象に即した指標値を最小化するような行動を、行動の決定に先立って知ることができ、将来のリスクを低減することができる。即ち具体的には、医師は医療過誤によって重要な患者を死亡させるリスクを低減でき、融資実行者は貸し倒れ損失額を低減でき、また、投資家は破産のリスクを低減できる。
【００２５】
また、ある対象におけるコストの期待ショートフォールは、その対象に対して行動を採った結果として得られるコストのバリュー・アット・リスク（以下、ＶａＲ、非特許文献１０を参照。）、および、行動決定関数のパラメータθの関数として表される。そして、本実施形態においては、期待ショートフォールの上界を示す指標値を採用する。この指標値は、ＶａＲおよびパラメータθについて、下に凸の関数として表される。本実施例の関数生成部１２０は、この性質を利用して、まずＶａＲを固定して、この指標値を最小化するようなパラメータθを算出する。次に、関数生成部１２０は、パラメータθを固定して、この指標値を最小化するようなＶａＲを算出する。関数生成部１２０は、期待ショートフォールが収束するまでこれらの算出を繰り返す。このように、本実施例における行動支援システム１０は、最小化するリスク指標を期待ショートフォールとし、その上界を凸関数で表す指標値を最小化することで、適切な行動決定関数を迅速に算出することができる。
【００２６】
図２は、訓練データＤＢ１００のデータ構造の一例を示す。訓練データＤＢ１００は、ある患者に対して治療を行った結果として生じた損失を、訓練データとして記憶している。図２の例では、行動の対象が検査結果に対応し、行動は治療方針に対応し、損失は治療によって生じた不利益に対応する。訓練データＤＢ１００に記憶された訓練データによれば、ある検査結果Ａを有するある患者に対し、治療方針１に従って治療を行った場合における損失は１０であり、治療方針２に従って治療を行った場合における損失は６である。一方で、同じ検査結果Ａを有する他の患者に対し、治療方針１に従って治療を行った場合における損失は１であり、治療方針２に従って治療を行った場合における損失は５である。
【００２７】
この損失は、１から１０によって正規化して示すが、実際には、例えば、治療の結果として表れた現象を数値化したものである。即ち例えば、１０は、死亡やそれに準ずる状態を示し、１は、投薬の副作用が発生した状態を示す。これに代えて、この損失は、治療の結果として現れた現象を金銭の価値に置き換えたものであってもよい。
【００２８】
ここで、検査結果Ａの患者に対して治療方針１に従って治療を行った場合の平均損失は５．５であり、治療方針２に従って治療を行った場合の平均損失も５．５である。このように、治療方針１と治療方針２とでは、共に、平均損失は５．５であるが、治療方針１の最大損失は１０であり、治療方針２の最大損失は６である。死亡に相当する損失は避けるべきであるから、この例においては、例え平均損失が同じであっても、最大損失の少ない治療方針２を採用するべきと判断できる。このような判断は、より複雑な事例では困難な場合が多いが、本実施例においては、最小化すべき指標を期待ショートフォールとすることで、このような判断を適切に行うことができる。
【００２９】
同様に、検査結果Ｂを有するある患者に対し、治療方針１に従う治療を行った結果として生じる損失は８であり、治療方針２に従う治療を行った結果として生じる損失は６である。一方で、同じ検査結果Ｂを有する他の患者に対し、治療方針１に従う治療を行った結果として生じる損失は７であり、治療方針２に従う治療を行った結果として生じる損質は７である。
【００３０】
以上、図２に示すように、訓練データＤＢ１００は、ある対象に対してある行動を採った結果として生じるコストを記憶している。このコストは、その対象に対して過去に実際に行動を採った結果の履歴に基づいて定められてもよいし、各種の実験結果やシミュレーションの結果に基づいて定められてもよい。
【００３１】
図３は、関数生成部１２０の機能構成を示す。関数生成部１２０は、第１算出部３００と、第３算出部３０５と、第２算出部３１０と、収束判定部３３０とを有する。第１算出部３００は、与えられた値をコストのＶａＲとした場合において、そのＶａＲを超えるコストの合計に基づく指標値を最小化する行動決定関数を、訓練データに基づいて算出してメモリに記憶する。この指標値は、例えば、期待ショートフォールの上界を示す所定の値となっており、なおかつ、この指標値を最小化するときの行動決定関数が、期待ショートフォールを最小化することが予め分かっている。
【００３２】
第３算出部３０５は、訓練データに基づいて、コストの期待値を最小化する行動決定関数を算出する。コストの期待値を最小化する行動決定関数を効率的に算出する技術は、コスト考慮型アルゴリズム（cost-sensitive algorithm）と呼ばれている。この技術の実現方法は、例えば、非特許文献１、６、および、８に記載されており従来公知であるから説明を省略する。第１算出部３００は、訓練データに含まれるそれぞれに行動に対応するコストから、与えられたＶａＲを差し引いて、新たな訓練データとして第３算出部３０５に与える。そして、第１算出部３００は、第３算出部３０５によって、当該新たな訓練データにおけるコストの期待値を最小化する行動決定関数を算出させる。算出させた行動決定関数が、与えられたこの値をＶａＲとした場合における期待ショートフォールを最小化する行動決定関数となる。
【００３３】
第２算出部３１０は、第１算出部３００によって算出された行動決定関数をメモリから読み出して、その行動決定関数によって示される行動を採った結果として生じるコストのＶａＲを、訓練データに基づいて算出して、第１算出部３００に与える。収束判定部３３０は、第１算出部３００によって最小化された指標値と、第２算出部３１０によって算出されたＶａＲとに基づいて、これらに基づいて算出される期待ショートフォールが、予め定められた範囲内の値に収束したか否かを判定する。関数生成部１２０は、期待ショートフォールが収束したことを条件に、第１算出部３００によって算出された行動決定関数を出力する。
【００３４】
このように、関数生成部１２０によれば、期待ショートフォールをより小さくするような行動決定関数とＶａＲとを交互に算出して、期待ショートフォールを最小値に近づけていく。そして、期待ショートフォールが収束したことを条件に、その時点の行動決定関数を出力する。この際、期待ショートフォールの上界は、パラメータθおよびＶａＲについて下に凸の関数として表されることから、期待ショートフォールを最小化するパラメータθおよびＶａＲは、θおよびＶａＲに対しグリーディーなアルゴリズムによって算出することができる。これにより、行動決定関数を算出する毎に期待ショートフォールは最小値に近づき、目的の行動決定関数を効率的に算出することができる。更に、行動決定関数の算出においては、第３算出部３０５において、コストの期待値を算出する既存技術を利用することができ、既存技術の蓄積を利用して処理を効率化することができる。
【００３５】
以下、図４および図５を用いて、本実施例の処理の流れを説明する。処理の流れの説明に先立って、まず、期待ショートフォールを最小化する行動決定関数を算出するアルゴリズムを導く過程を説明する。このアルゴリズムは、行動決定関数のパラメータθを算出することによって行動決定関数を生成する。即ち、行動決定関数とは、対象ｘ、行動ｙ、および、パラメータθを入力として、その行動の妥当性の程度を数値化して出力するものとし、その行動決定関数の性質を定めるパラメータをθとする。
【００３６】
パラメータθを用いて、期待ショートフォールは、以下の式（８）によって表される。但し、式（８）において、［ｘ］＋を、ｘが正の場合はｘを、それ以外の場合には０を返す関数とする。
【数８】
2007133477.tif 000010
【００３７】
この式において、コストの分布Ｄは未知であるので、分布Ｄに代えて、訓練データの分布Ｅを用いる。これにより、式（８）は式（９）のように書き換えられる。但し、式（９）において、訓練データにおける行動の対象を、ｘ（１）からｘ（ｎ）とする。また、行動決定関数を、対象ｘを入力として、パラメータθに応じて採るべき行動ｙを決定するための関数ｈとする。また、訓練データにおけるコストを、ｃ（ｘ（ｉ），ｈ（θ））とする。また、ＶａＲを越えるコストが発生する確率を定数βとする。
【数９】
2007133477.tif 000011
【００３８】
ここで、αＥβ（θ）は、訓練データの分布Ｅに対するＶａＲであり、式（１０）によって表される。但し、関数Ｉを、引数によって示される条件が満たされる場合に１を、当該条件が満たされない場合に０を採る関数とする。
【数１０】
2007133477.tif 000012
【００３９】
さて、式（９）において、仮にαＥβ（θ）が既知の定数α´であるとすると、式（９）の第２項に含まれる以下の式（１１）だけを最小化すればよいことになる。
【数１１】
2007133477.tif 000013
なお、関数［ｘ］＋はｘについて非減少な凸関数であるので、ｃ（ｘ（ｉ），ｈ（θ））がθについて凸であれば、式（１１）も同様に凸になる。式（１１）を最小化するアルゴリズムについては後述する。
【００４０】
次に、与えられたパラメータθについて、このθに対するＶａＲは、訓練データについて定義されているから、以下の式（１２）および式（１３）のように表すことができる。
【数１２】
2007133477.tif 000014
【数１３】
2007133477.tif 000015
【００４１】
これは、θによって発生するコストのなかで、（１−β）・Ｎ番目（端数は切り捨て）に大きいもの（ｃ（ｘ（ｋ），ｈ（θ））に等しいので、順序統計量を求めるアルゴリズムによって、Ｏ（Ｎ）時間で発見することができる（例えば、非特許文献１０を参照。）。
以上の導出に基づき、以下、図４を用いて、期待ショートフォールを最小化する行動決定関数を算出する処理を説明する。
【００４２】
図４は、行動支援システム１０が利用者の行動の決定を支援する処理のフローチャートを示す。データ取得部１１０は、訓練データを訓練データＤＢ１００から取得する（Ｓ４００）。この訓練データに基づき、関数生成部１２０は、以下の処理を行う。まず、第１算出部３００は、与えられた値をコストのＶａＲとした場合において、そのＶａＲを超えるコストの合計に基づく指標値を最小化する行動決定関数を、訓練データに基づいて算出する（Ｓ４１０）。与えられる値とは、第１回目の算出においては、予め定められた初期値（例えば、０）のあり、その後の算出においては、第２算出部３１０によって与えられるＶａＲである。詳細には、第１算出部３００は、与えられたＶａＲをα´とし、上述の式（１１）によって算出される指標値ＣＥα（θ）を最小化する行動決定関数のパラメータθ´を算出する。パラメータθ´の値を、新たなθの値とする。
【００４３】
次に、第２算出部３１０は、第１算出部３００によって算出された行動決定関数によって示される行動を採った結果として生じるコストのＶａＲを、訓練データに基づいて算出する（Ｓ４２０）。詳細には、第２算出部３１０は、算出されたパラメータθに対し、上述の式（１２）および式（１３）によって算出されるαＥβ（θ）をＶａＲとして算出する。そして、第２算出部３１０は、この値をα´として第１算出部３００に与える。
【００４４】
次に、収束判定部３３０は、第１算出部３００によって最小化された指標値ＣＥα´と、第２算出部３１０によって算出されたＶａＲに基づいて、期待ショートフォールの上界を示す指標値ＦＥβ（θ，α）を算出する（Ｓ４３０）。この指標値は、例えば、第１算出部によって最小化された指標値ＣＥα´を、コストがバリュー・アット・リスク以下である確率（１−β）で除算した値を、ＶａＲに加えた値であり、以下の式（１４）によって表される。
【数１４】
2007133477.tif 000016
【００４５】
この式（１４）については、非特許文献１１において示されているように、以下の式（１５）が満たされることが知られている。また、式（１４）がαについて凸であり、更に、式（７）がθについて凸であるから、式（１４）はθとαについて凸である。そして、更に、以下の式（１６）が成立する。
【数１５】
2007133477.tif 000017
【数１６】
2007133477.tif 000018
【００４６】
以上より、式（１６）の指標値が最小値に収束する場合には、期待ショートフォールも最小値に収束することがわかる。さらに、この指標値は、ＶａＲおよびθの関数によって表され、ＶａＲおよびθについて下に凸の関数となる。従って、収束判定部３３０は、式（１６）の指標値が予め定められた範囲内の値に収束するか否かを判断することによって、期待ショートフォールが収束したか否かを判断する（Ｓ４４０）。なお、期待ショートフォールの収束に伴い、ＶａＲおよびθも所定の値に収束していくことから、収束判定部３３０は、ＶａＲの収束を判定することによって期待ショートフォールの収束を判定してもよいし、θの収束を判定することによって期待ショートフォールの収束を判定してもよい。
【００４７】
期待ショートフォールが収束していなければ（Ｓ４４０：ＮＯ）、関数生成部１２０は、Ｓ４１０に処理を戻す。この場合、第１算出部３００は、Ｓ４２０において算出されたＶａＲを用いてパラメータθを再度算出する。一方で、期待ショートフォールが収束したことを条件に（Ｓ４４０：ＹＥＳ）、関数生成部１２０は、第１算出部３００によって算出された行動決定関数のパラメータθを出力する（Ｓ４５０）。行動決定部１３０は、以上の処理によって算出された行動決定関数に基づいて、利用者の行動を支援する（Ｓ４６０）。
【００４８】
図５は、Ｓ４１０において、行動決定関数を算出処理の詳細を示す。行動決定関数によって行動が択一的に定まる場合において、コストは、［Ｃ（ｉ）（ｘ（ｉ），ｙ）−α´］＋＋α´の形に限定される。上述の式（１１）がα´を超えるコストの期待値になっていることに注意すると、以下の式（１７）を、もともとのコストに置き換えることにより、式（７）は、以下の式（１８）として表される。これは、式（７）と同じ形になるので、既存の事例依存コスト考慮型アルゴリズムに、式（１７）のようにコストを変更した訓練例を与えることによって、期待ショートフォールを最小化することができる。
【数１７】
2007133477.tif 000019
【数１８】
2007133477.tif 000020
【００４９】
以上の考察により、第１算出部３００は、以下の処理を行う。まず、第１算出部３００は、式（１７）によって、訓練データにおける対象ｘ（ｉ）および行動ｙに対するコストｃ（ｉ）から、与えられたバリュー・アット・リスクα´を差し引くことにより、コストｃ´（ｉ）を算出して第３算出部３０５に与える（Ｓ５００）。そして、第３算出部３０５は、式（１８）によって示されるコストＣ´Ｅα´（θ）を最小化する行動決定関数のパラメータθを算出する（Ｓ５１０）。
【００５０】
この式（１８）によって表されるコストＣ´Ｅα´（θ）は、訓練データから求められるコストの期待値となる。コストの期待値を算出するアルゴリズムは、非特許文献１、６、および、８などによって従来から研究されており、その効率的な実行方法が知られている。本実施形態における第１算出部３００は、訓練データに含まれる各コストから、与えられたＶａＲを差し引くことによって、期待ショートフォールを最小化させる問題をコストの期待値を最小化させる問題に帰着させることができる。これにより、従来から研究されている効率的なアルゴリズムを利用して、期待ショートフォールを効率的に最小化することができる。
【００５１】
図６は、本実施形態に係る行動支援システム１０によって実験を行った結果を示す。実験データとして、非特許文献６で用いられているGerman Credit Dataを用いた。実験が対象とする問題は、顧客の信用リスクを予測する問題であり、顧客の情報をもとに、その人がよい顧客か悪い顧客かを分類するという問題である。顧客情報xの属性は、性別や職業、資金の使用目的や過去の履歴など、２０の項目から構成される。
【００５２】
この実験では、データセットに付属している、すべての属性を２４の数値属性に変換したものを用いた。行動は、融資を実行する、または、融資を実行しない、の２種類である。実行すべき融資を実行しないと、利息分の損失が発生する。一方で、実行すべきでない融資を実行すると、融資額の大部分に相当する損失が発生する。その他の条件は、非特許文献６に準ずる。
【００５３】
実験では、アクションを択一的に選択する場合のモデルh(x, y)および分散投資型のアクションの場合の弱仮説ft(x, y)として用いる。何れの場合においても、コスト考慮型学習器としてはコスト考慮型パーセプトロン（非特許文献６を参照。）をカーネル化したものを用いた。カーネル関数としてはガウシアンカーネル(σ= 50)を用いる。
【００５４】
本実験の結果は、データを３分割（訓練データ666個、テストデータ334個）した交差検定による値の平均値によって計測した。Cost-Sensitive の列は、期待コストを目的関数とするような従来のコスト考慮型パーセプトロンによる結果を、Risk-Sensitiveの列は、期待ショートフォールを目的関数とするような提案手法(β= 0.20, 0.10, 0.05, 0.01それぞれの場合)による結果を示した。
【００５５】
各行はテストデータにおける各βでの期待ショートフォールの３回の平均を示している。また、括弧内の数値はそれぞれの場合でのバリュー・アット・リスクを示している。Cost-Sentitiveの列の最下行のMean Cost の行は平均コストを示している。期待通り、コスト考慮型学習の場合には対応するβにおける期待ショートフォールを減少できていることがわかる。βが大きくなるほどリスク回避型による期待ショートフォールの減少分は著しくなくなっているが、これは、コスト分布が左側（0付近）に大きく偏っているため、期待ショートフォールと、期待コストの違いが小さくなっているためと思われる。また、β= 0.20 では、コスト考慮型のほうがリスク回避型よりも小さなバリュー・アット・リスクを実現していることがみてとれる。これはバリュー・アット・リスクが小さいことは、かならずしも小さな確率で起こる大きなコストそのものを抑えることにはならないことを示唆している。
【００５６】
図７は、行動支援システム１０として機能する情報処理装置７００のハードウェア構成の一例を示す。情報処理装置７００は、ホストコントローラ１０８２により相互に接続されるＣＰＵ１０００、ＲＡＭ１０２０、及びグラフィックコントローラ１０７５を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＢＩＯＳ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。
【００５７】
ホストコントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００及びグラフィックコントローラ１０７５とを接続する。ＣＰＵ１０００は、ＢＩＯＳ１０１０及びＲＡＭ１０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、ＣＰＵ１０００等がＲＡＭ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、ＣＰＵ１０００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【００５８】
入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して外部の装置と通信する。ハードディスクドライブ１０４０は、情報処理装置７００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からプログラム又はデータを読み取り、ＲＡＭ１０２０又はハードディスクドライブ１０４０に提供する。
【００５９】
また、入出力コントローラ１０８４には、ＢＩＯＳ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＢＩＯＳ１０１０は、情報処理装置７００の起動時にＣＰＵ１０００が実行するブートプログラムや、情報処理装置７００のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からプログラム又はデータを読み取り、入出力チップ１０７０を介してＲＡＭ１０２０またはハードディスクドライブ１０４０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【００６０】
情報処理装置７００に提供されるプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、入出力チップ１０７０及び/又は入出力コントローラ１０８４を介して、記録媒体から読み出され情報処理装置７００にインストールされて実行される。プログラムが情報処理装置７００等に働きかけて行わせる動作は、図１から図６において説明した行動支援システム１０における動作と同一であるから、説明を省略する。
【００６１】
以上に示したプログラムは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムを情報処理装置７００に提供してもよい。
【００６２】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【００６３】
【図１】図１は、行動支援システム１０の機能構成を示す。
【図２】図２は、訓練データＤＢ１００のデータ構造の一例を示す。
【図３】図３は、関数生成部１２０の機能構成を示す。
【図４】図４は、行動支援システム１０が利用者の行動の決定を支援する処理のフローチャートを示す。
【図５】図５は、Ｓ４１０において、行動決定関数を算出処理の詳細を示す。
【図６】図６は、本実施形態に係る行動支援システム１０によって実験を行った結果を示す。
【図７】図７は、行動支援システム１０として機能する情報処理装置７００のハードウェア構成の一例を示す。
【符号の説明】
【００６４】
１０  行動支援システム
１００  訓練データＤＢ
１１０  データ取得部
１２０  関数生成部
１３０  行動決定部
３００  第１算出部
３０５  第３算出部
３１０  第２算出部
３３０  収束判定部
７００  情報処理装置
【図１】
2007133477.tif 000027
【図２】
2007133477.tif 000028
【図３】
2007133477.tif 000029
【図４】
2007133477.tif 000030
【図５】
2007133477.tif 000031
【図６】
2007133477.tif 000032
【図７】
2007133477.tif 000033