(57)【要約】【課題】汎化性能の意味で適切なサイズの木のモデルを、枝刈り用のテストセットなしに高速に得る。【解決手段】ノードを説明変数の各次元の各スプリットポイントでスプリットする場合の評価値を計算するスプリット評価値計算手段５１と、ノードをスプリットしない場合の評価値を計算するスプリット無し評価値計算手段５３と、得られた評価値を基にノードを最も評価値のよい次元でスプリットするか、またはノードをスプリットしないかを判定するスプリット判定手段５４とを備え、スプリット評価値計算手段およびスプリット無し評価値計算手段は、各々、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを表す項と、子ノードに落ちたデータの数に応じて評価値を下げる方向に働くペナルティー項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算する。【選択図】図９
2014241060.tif 000002
【特許請求の範囲】
【請求項１】
説明変数の指定された次元を用いて、指定されたノードを当該次元の各スプリットポイントでスプリットする場合の評価値を計算するスプリット評価値計算手段と、
前記スプリット評価値計算手段によって得られる評価値を基に、説明変数の次元ごとに指定されたノードをスプリットするのに最もよいスプリットポイントを検索するスプリットポイント検索手段と、
前記ノードをスプリットしない場合の評価値を計算するスプリット無し評価値計算手段と、
前記次元ごとの最もよいスプリットポイントでの評価値と、前記スプリットしない場合の評価値とを基に、前記ノードを最も評価値のよい次元でスプリットするか、または前記ノードをスプリットしないかを判定するスプリット判定手段とを備え、
前記スプリット評価値計算手段は、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、分岐ノードと葉ノードに関して、それぞれ通過データ数または落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算し、
前記スプリット無し評価値計算手段は、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、葉ノードに関して、落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算する
ことを特徴とする木モデル学習装置。
【請求項２】
前記スプリット評価値計算手段によって計算された評価値の信頼区間を計算するスプリット評価値信頼区間計算手段と、
前記スプリット無し評価値計算手段によって計算された評価値の信頼区間を計算するスプリット無し評価値信頼区間計算手段とを備え、
前記スプリット判定手段は、前記ノードに対して所定数のデータが読み込まれて前記スプリットする場合の評価値とスプリットしない場合の評価値とが計算される度に、説明変数の次元ごとの最もよいスプリットポイントでの評価値およびそれらの信頼区間と、スプリットしない場合の評価値およびその信頼区間とを基に、前記ノードを最も評価値のよい次元でスプリットするか、または前記ノードをスプリットしないか、もしくは処理したデータ数ではスプリットするか否かを決定するのに十分でないかを判定する
請求項１に記載の木モデル学習装置。
【請求項３】
前記スプリット判定手段は、処理したデータ数ではスプリットするか否かを決定するのに十分でないと判定した場合には、前記ノードに対してさらにデータを読み込んで、前記ノードをスプリットする場合の評価値およびその信頼区間と、スプリットしない場合の評価値およびその信頼区間とを再計算させる
請求項２に記載の木モデル学習装置。
【請求項４】
前記スプリット判定手段により処理したデータ数ではスプリットするか否かを決定するのに十分でないと判定された場合に、その判定時に最もよかった評価値の信頼区間の下限よりも、２番以降の評価値の信頼区間の上限が小さい次元を、新たに読み込んだデータを用いた評価値およびその信頼区間の再計算の対象から除外する処理を行う計算不要次元削除手段を備えた
請求項３に記載の木モデル学習装置。
【請求項５】
各次元についての少なくとも前記スプリット評価値計算手段による評価値の計算処理を並列で動作させる
請求項１から請求項４のうちのいずれか１項に記載の木モデル学習装置。
【請求項６】
ルートノードから順に、各ノードに対して、
説明変数の次元ごとに、当該ノードを当該次元の各スプリットポイントでスプリットする場合の評価値を、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、分岐ノードと葉ノードに関して、それぞれ通過データ数または落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて計算し、
得られた前記評価値を基に、説明変数の次元ごとに前記ノードをスプリットするのに最もよいスプリットポイントを検索し、
前記ノードをスプリットしない場合の評価値を、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、葉ノードに関して、落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて計算し、
前記次元ごとの最もよいスプリットポイントでの評価値と、前記スプリットしない場合の評価値とを基に、前記ノードを最も評価値のよい次元でスプリットするか、または前記ノードをスプリットしないかを判定する
ことを特徴とする木モデル学習方法。
【請求項７】
少なくとも前記次元ごとの最もよいスプリットポイントでの評価値と前記スプリットしない場合の評価値とについて、各々信頼区間を計算し、
前記ノードに対して所定数のデータが読み込まれて前記スプリットする場合の評価値とスプリットしない場合の評価値とが計算される度に、前記次元ごとの最もよいスプリットポイントでの評価値およびそれらの信頼区間と、前記スプリットしない場合の評価値およびその信頼区間とを基に、前記ノードを最も評価値のよい次元でスプリットするか、または前記ノードをスプリットしないか、もしくは処理したデータ数ではスプリットするか否かを決定するのに十分でないかを判定する
請求項６に記載の木モデル学習方法。
【請求項８】
コンピュータに、
説明変数の指定された次元を用いて、指定されたノードを当該次元の各スプリットポイントでスプリットする場合の評価値を計算するスプリット評価値計算処理、
前記スプリット評価値計算処理によって得られる評価値を基に、説明変数の次元ごとに指定されたノードをスプリットするのに最もよいスプリットポイントを検索するスプリットポイント検索処理、
前記ノードをスプリットしない場合の評価値を計算するスプリット無し評価値計算処理、および
前記次元ごとの最もよいスプリットポイントでの評価値と、前記スプリットしない場合の評価値とを基に、前記ノードを最も評価値のよい次元でスプリットするか、または前記ノードをスプリットしないかを判定するスプリット判定処理を実行させ、
前記スプリット評価値計算処理で、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、分岐ノードと葉ノードに関して、それぞれ通過データ数または落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算させ、
前記スプリット無し評価値計算処理で、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、葉ノードに関して、落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算させる
ための木モデル学習プログラム。
【請求項９】
前記コンピュータに、
前記スプリット評価値計算処理で計算された評価値の信頼区間を計算するスプリット評価値信頼区間計算処理、および
前記スプリット無し評価値計算処理で計算された評価値の信頼区間を計算するスプリット無し評価値信頼区間計算処理を実行させ、
前記スプリット判定処理で、前記ノードに対して所定数のデータが読み込まれて前記スプリットする場合の評価値とスプリットしない場合の評価値とが計算される度に、前記次元ごとの最もよいスプリットポイントでの評価値およびそれらの信頼区間と、前記スプリットしない場合の評価値およびその信頼区間とを基に、前記ノードを最も評価値のよい次元でスプリットするか、または前記ノードをスプリットしないか、もしくは処理したデータ数ではスプリットするか否かを決定するのに十分でないか、のいずれかを決定させる
請求項８に記載の木モデル学習プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、回帰木や決定木といったデータ空間の分割を木で表現するモデルを学習する木モデル学習装置、木モデル学習方法および木モデル学習プログラムに関する。
【背景技術】
【０００２】
回帰木や決定木と呼ばれる木のモデルがある。回帰木は回帰を行う木のモデルであり、決定木は分類を行う木のモデルである。この他にもデータのクラスタリング用途に利用できる木のモデルなどもある。
【０００３】
これら木のモデルは、ある指標において似たものが同じ葉に落ちるようにデータの空間を分割する。
【０００４】
より具体的には、木のモデルは、木の各ノードから伸びる枝に説明変数に関する条件が対応づけられており、その条件に従ってルートノードからリーフノードまで辿り、辿り着いたリーフノードに関連付けられた値（回帰木の場合は実数値、決定木の場合はカテゴリ値）を予測値として出力する。このような木のモデルを用いて、ある未知のデータサンプルに対する予測を行うことができる。
【０００５】
回帰木や決定木といった木のモデル学習は、学習の手法がシンプルであるため高速に動作し、また得られるモデルが人間が解釈しやすいというメリットがある。一方、精度の面ではサポートベクターマシンなどと比べると一般的に悪い。しかし、木のモデル学習において、複数の木を学習し組み合わせるブースティングを行うことで、高い精度が達成できることが知られている。回帰木や決定木は現在でもよく使われるデータマイニング手法の一つである。
【０００６】
しかし、学習の手法がシンプルな木のモデルであっても、データが大量になると学習に時間がかかるため、高速化が必要となる。近年の分散、並列処理基盤の整備に伴い、学習アルゴリズムの分散並列化による高速化が進んでいる（例えば、非特許文献１参照）。また、分散並列とは別軸での高速化の方法として、Ｈｏｅｆｆｄｉｎｇ木（Ｈｏｅｆｆｄｉｎｇ  ｔｒｅｅ）と呼ばれる木アルゴリズムがある（例えば、非特許文献２参照。）。
【０００７】
Ｈｏｅｆｆｄｉｎｇ木はデータストリームを対象にした決定木の学習アルゴリズムであるが、対象がデータストリームである場合に限らず、回帰木や決定木のバッチ学習の高速化にも有効な方法である。Ｈｏｅｆｆｄｉｎｇ木による高速化のアイディアは、すべてのデータを処理後に木をスプリット（分割）させる、すなわち木を成長させるのではなく、データの一部を処理した後にそれが精度を担保するのに統計的に十分なデータであればその時点で木をスプリットさせるというものである。データが大量の場合に、精度保証に必要最低限のデータだけを処理しながら木を構築できるので、高速に木のモデル学習ができる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Panda Biswanath, Herbach J.S., Basu Sugato, Bayarde R.J., "PLANET:massively parallel learning of tree ensembles with MapReduce", VLDB Endowment, 2009.
【非特許文献２】Domingos Pedro, Hulten Geoff, "Mining high-speed data streams", PCM SIGKDD, 2000.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、Ｈｏｅｆｆｄｉｎｇ木アルゴリズムは以下に述べるような問題がある。すなわち、Ｈｏｅｆｆｄｉｎｇ木アルゴリズムは、スプリットの評価関数から木の成長をどこで止めるべきかの判定ができないという問題がある。Ｈｏｅｆｆｄｉｎｇ木アルゴリズムでは、スプリットの評価関数に情報利得やジニ係数を用いているため、評価結果が必ずスプリットした方がよいという結果になる。このような評価関数を基に、ノードをスプリットさせていくと、木が成長しすぎて過学習となり、汎化性能が失われてしまう。このような問題を回避するために、成長し過ぎた木の枝刈り用にテスト用のデータセットでが必要であった。
【００１０】
枝刈りとは別に、設定により深さや葉の多さ、１リーフあたりのデータ数に制限を設けて過学習を防止する手法も考えられているが、予測対象データを限定することなしにこれらの適切な値を前もって設定することは困難である。適切な値が設定されなければ、木の成長が足りずに精度の劣ったモデルが生成されたり、木が成長しすぎて汎化性能が失われることになる。
【００１１】
本発明は、上述した課題に鑑み、汎化性能の意味で適切なサイズの木のモデルを、枝刈り用のテストセットなしに高速に得ることができる木モデル学習装置、木モデル学習方法および木モデル学習プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明による木モデル学習装置は、説明変数の指定された次元を用いて、指定されたノードを当該次元の各スプリットポイントでスプリットする場合の評価値を計算するスプリット評価値計算手段と、スプリット評価値計算手段によって得られる評価値を基に、説明変数の次元ごとに指定されたノードをスプリットするのに最もよいスプリットポイントを検索するスプリットポイント検索手段と、ノードをスプリットしない場合の評価値を計算するスプリット無し評価値計算手段と、説明変数の次元ごとの最もよいスプリットポイントでの評価値と、スプリットしない場合の評価値とを基に、ノードを最も評価値のよい次元でスプリットするか、またはノードをスプリットしないかを判定するスプリット判定手段とを備え、スプリット評価値計算手段は、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、分岐ノードと葉ノードに関して、それぞれ通過データ数または落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算し、スプリット無し評価値計算手段は、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、葉ノードに関して、落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算することを特徴とする。
【００１３】
また、本発明による木モデル学習方法は、ルートノードから順に、各ノードに対して、説明変数の次元ごとに、当該ノードを当該次元の各スプリットポイントでスプリットする場合の評価値を、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、分岐ノードと葉ノードに関して、それぞれ通過データ数または落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて計算し、得られた評価値を基に、説明変数の次元ごとにノードをスプリットするのに最もよいスプリットポイントを検索し、ノードをスプリットしない場合の評価値を、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、葉ノードに関して、落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて計算し、説明変数の次元ごとの最もよいスプリットポイントでの評価値と、スプリットしない場合の評価値とを基に、ノードを最も評価値のよい次元でスプリットするか、またはノードをスプリットしないかを判定することを特徴とする。
【００１４】
また、本発明による木モデル学習プログラムは、コンピュータに、説明変数の指定された次元を用いて、指定されたノードを当該次元の各スプリットポイントでスプリットする場合の評価値を計算するスプリット評価値計算処理、スプリット評価値計算処理によって得られる評価値を基に、説明変数の次元ごとに指定されたノードをスプリットするのに最もよいスプリットポイントを検索するスプリットポイント検索処理、ノードをスプリットしない場合の評価値を計算するスプリット無し評価値計算処理、および説明変数の次元ごとの最もよいスプリットポイントでの評価値と、スプリットしない場合の評価値とを基に、ノードを最も評価値のよい次元でスプリットするか、またはノードをスプリットしないかを判定するスプリット判定処理を実行させ、スプリット評価値計算処理で、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、分岐ノードと葉ノードに関して、それぞれ通過データ数または落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算させ、スプリット無し評価値計算処理で、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、葉ノードに関して、落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算させることを特徴とする。
【発明の効果】
【００１５】
本発明によれば、汎化性能の意味で適切なサイズの木のモデルを、枝刈り用のテストセットなしに高速に得ることができる。
【図面の簡単な説明】
【００１６】
【図１】第１の実施形態の木モデル学習システムの構成例を示すブロック図である。
【図２】木モデル学習装置１０のハードウェア構成例を示すブロック図である。
【図３】データ記憶部１０１に格納される学習データの一例を示す説明図である。
【図４】木モデル記憶部１０２に格納される木のモデルの一例を模式的に示す説明図である。
【図５】ビンニングポイントの計算の結果、分けられたビンの一例を示す説明図である。
【図６】第１の実施形態の木モデル学習システムの動作の一例を示すフローチャートである。
【図７】第２の実施形態の木モデル学習システムの構成例を示すブロック図である。
【図８】第２の実施形態の木モデル学習システムの動作の一例を示すフローチャートである。
【図９】本発明の木モデル学習装置の最小の構成例を示すブロック図である。
【図１０】本発明の木モデル学習装置の他の構成例を示すブロック図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態について図面を参照して説明する。なお、以下の説明はすべて木のモデルが回帰木である場合を例に説明する。本発明による木のモデル学習方法に用いたスプリットの評価方法や信頼区間の算出方法の技術コンセプトは他の木のモデル学習においても共通して使用可能である。例えば、決定木の学習であれば、文献「Bouchard Guillaume, "Efficient Bounds for the softmax Function, Applications to Inference in Hybrid Models", NIPS 2007」などに開示されている技術により、回帰木の学習と同様な処理に帰着できる。また、回帰木以外の木のモデルであっても、枝の分岐がデータ空間の分割に対応しているものであれば、回帰木の学習と同様な処理に帰着できる。
【００１８】
実施形態１．
図１は、本発明の第１の実施形態の木モデル学習システムの構成例を示すブロック図である。図１に示すように、本実施形態の木モデル学習システムは、木モデル学習装置１０を備えている。そして、木モデル学習装置１０は、データ記憶部１０１と、木モデル記憶部１０２と、スプリットポイント計算手段１０３と、スプリット無し計算手段１０４と、ビンニングポイント計算手段１０５と、スプリット判定手段１０６と、木ノード生成手段１０７とを備えている。なお、図１には、１つの木モデル学習装置１０がこれらの記憶部および処理手段を備える例が示されているが、これらの記憶部および処理手段は複数の装置に分けて実装されていてもよい。
【００１９】
また、図１には、木モデル学習装置１０と併せて、学習された木モデルを用いて予測を行う予測手段２０が示されているが、木モデル学習装置１０が予測手段２０を含んでいてもよい。
【００２０】
図２は、木モデル学習装置１０のハードウェア構成例を示すブロック図である。図２に示すように、木モデル学習装置１０は、演算部１１、記憶部１２および入出力部１３を含んでいてもよい。このような装置は、例えばプログラムに従って動作するパーソナルコンピュータ等の情報処理装置によって実現される。また、この場合、演算部１１、記憶部１２および入出力部１３は、それぞれＣＰＵ、メモリおよび各種入出力装置（例えば、キーボート、マウス、ネットワークインタフェース部等）によって実現される。
【００２１】
本実施形態において、データ記憶部１０１および木モデル記憶部１０２は、記憶装置（例えば、図２に示す記憶部１２）によって実現される。また、スプリットポイント計算手段１０３、スプリット無し計算手段１０４、ビンニングポイント計算手段１０５、スプリット判定手段１０６および木ノード生成手段１０７は、例えばプログラムに従って動作するＣＰＵ（例えば、図２に示す演算部１１）によって実現される。
【００２２】
データ記憶部１０１は、木のモデルを学習する際に用いるデータ（以下、学習データという。）を格納する。図３は、データ記憶部１０１に格納される学習データの一例を示す説明図である。
【００２３】
図３に示す例では、１行が１学習データを表している。また、列は各学習データの属性値を表すマトリックスデータである。図３には、３次元の説明変数から目的変数を予測する回帰用の学習データの例が示されている。
【００２４】
木モデル記憶部１０２は、学習された木のモデルを格納する。図４は、木モデル記憶部１０２に格納される木のモデルの一例を模式的に示す説明図である。木モデル記憶部１０２は、生成された木モデルの木構造（例えば、ノードがいくつ存在し、それらノードが他のノードとどのように繋がっているか等）を表す情報とともに、各ノードに対応づけて、予測値、そのノードに落ちる学習データのＩＤリスト、もし子ノードが存在すれば子ノードへのエッジに対応する説明変数の条件、などを格納する。図４には、ＩＤ＝ｉで識別される子ノードに対応づけて、予測値として「１３５」が、子ノードへのエッジに対応する説明変数の条件として「６０．０  ＜  Ｘ２」が格納されている例が示されている。子ノードへのエッジに対応する説明変数の条件は、このようにスプリット次元（Ｎｏｄｅ  ｉの例では第２次元）とスプリット値の情報とで表わされる情報であってもよい。なお、木のモデルのデータ格納形式はこの限りでなく、学習された木のモデルが具体的に把握できるよう構成されていれば特に限定されない。
【００２５】
ビンニングポイント計算手段１０５は、データの次元ごとに、当該次元においてデータをビンに分ける区切り点であるビンニングポイントを計算する。ビンニングポイント計算手段１０５は、例えば図３に示すような学習データの説明変数の各次元について、それらがとりうる値の中からビンを分ける区切り点を求めればよい。ビンニングポイントの計算方法としては、例えば、等幅で区切る方法や、各ビンの中に入るデータ数がほぼ等しくなるようにビンニングポイントを求める方法などがある。図５は、ある次元についてビンニングポイントを計算した結果、分けられたビンの一例を示す説明図である。図５には、説明変数の第１次元のデータの値域を等幅で区切る方法により分けられたｎ個のビン（Ｂｉｎ１〜Ｂｉｎｎ）の例が示されている。
【００２６】
スプリットポイント計算手段１０３は、説明変数の各次元ごとに、スプリットするか否かの判定対象となったノード（以下、対象ノードという。）をスプリットするのに最もよいとされるスプリットポイント（境界条件となるスプリット値）を計算するための手段であって、ビンニング手段１０３１と、スプリット評価値計算手段１０３２と、スプリット評価値信頼区間計算手段１０３３と、スプリットポイント検索手段１０３４とを含む。
【００２７】
ビンニング手段１０３１は、指定された次元について、ビンニングポイント計算手段１０５で得られたビンニングポイントを基準に、対象ノードに落ちる学習データをビンに振り分け、ビンごとの統計量を計算し、保存する。統計量は、評価値の計算式にあわせ必要なものを計算する。ビンニング手段１０３１は、例えばビンごとに当該ビンに含まれる学習データを対象にしたΣｙ２、Σｙ、Σ１といった３種類の統計量を計算し、保存してもよい。なお、本例のビンニング手段１０３１は、ビンごとの統計量を計算するとともに、すべてのビンについて累積した統計量も計算し、保存する。上述の例でいえば、すべてのビンについて累積したΣｙ２、Σｙ、Σ１の値を計算すればよい。
【００２８】
スプリット評価値計算手段１０３２は、指定された次元について、予め定められている評価関数を使い、対象ノードにおけるスプリットの各候補点でスプリットした場合の評価値を計算する。以下では、スプリット評価値計算手段１０３２が求めた評価値を「スプリット評価値」という場合がある。スプリット評価値計算手段１０３２は、スプリット可能なすべての点を候補点としてスプリット評価値を計算するのではなく、ビンニングポイント計算手段１０５が計算したビンニングポイントによって区切られるビンとビンの間のみをスプリットの候補点としてスプリット評価値を計算してもよい。
【００２９】
スプリット評価値計算手段１０３２は、例えば以下の式（１）で表される評価関数を使い、スプリットの評価値を計算してもよい。
【００３０】
【数１】
2014241060.tif 000003
【００３１】
上述の式（１）の評価関数には、データへのフィッティングを表す項の他に、木のモデルの複雑さに伴うペナルティ項が含まれている。ペナルティ項とは、具体的には、子ノードに落ちるデータ数に応じて評価値を悪くする方向に働く項である。式（１）では、第２項が左葉ノードに関するペナルティ項、第４項が右葉ノードに関するペナルティ項、第６項が分岐ノードに関するペナルティ項となっている。これらの項において、それぞれのノードに落ちるデータ（分岐ノードの場合は通過するデータ）の数に応じたペナルティを掛けている。
【００３２】
式（１）において、Ｎは対象ノードに落ちるデータの総数を表している。また、ｒＬ、ｒＲはそれぞれ対象ノードの左右の葉ノードに落ちるデータの割合を表している。すなわち、ｒＬ、ｒＲは、ある次元について対象ノードに対してｎ個のデータを見たときにそれぞれ左右の葉ノードに落ちるデータ数がｎＬ、ｎＲであった場合にｒＬ＝ｎＬ／ｎ、ｒＲ＝１−ｒＬで表される確率変数である。また、ハット付きσＬ、σＲの二乗はそれぞれ左右の葉ノードに落ちたデータの目的変数の分散を表している。なお、式（１）はスプリット評価値を求める評価関数の一つの例であって、これに限られない。
【００３３】
Ｈｏｅｆｆｄｉｎｇ木アルゴリズムで用いられる評価関数は、データのフィッティングを表す項しか含まれていなかった。このため、スプリットした後の木がどれだけ複雑になるかといったことは何ら考慮されずにデータのフィッティング具合だけをみて評価値が計算されていた。このような評価値では、後述するスプリット無し計算手段１０４が計算するスプリット無し評価値と比較しても常にスプリットした方がよいという判定結果になってしまう。
【００３４】
一方、本実施形態のスプリット評価値計算手段１０３２が用いる評価関数は、木の成長に対してトレードオフ関係になる２種類の項を含んでいる。すなわち、木を成長させると値が大きくなる項と、木を成長させると値が小さくなる項を少なくとも含んでいる。上記の評価関数の例では、葉におけるデータへのフィット具合を評価値の良さで表す項（２分木なら右と左）と、木の複雑さによって評価値を悪くするペナルティ項（分岐ノードと葉ノード）とが含まれ、これらがトレードオフ関係になっている。このようなトレードオフ関係になる２項を含ませることによって、各ポイントでスプリットした場合のデータへのフィッティングのメリットと、木が複雑になるペナルティとを比較考量した値がスプリット評価値として表れるようにしている。
【００３５】
このような評価関数を用いれば、例えばスプリットによるデータへのフィッティングのメリットがスプリットして木が複雑になるペナルティよりも大きい場合は当該ポイントでのスプリットを許可し、一方、スプリットによるデータへのフィッティングのメリットがスプリットして木が複雑になるペナルティよりも小さい場合は当該ポイントでのスプリットを許可しないといった判定もできる。
【００３６】
スプリット評価値信頼区間計算手段１０３３は、スプリット評価値計算手段１０３２が算出したスプリット評価値の信頼区間を求める。木のモデル学習にＨｏｅｆｆｄｉｎｇ木アルゴリズムにおける高速化の手法を適用した場合、学習データの一部を読み出してスプリット評価値を計算するため、正確な値は得られない。そのような場合に、スプリット評価値信頼区間計算手段１０３３が、算出されたスプリット評価値の信頼区間を求めることにより、該スプリット評価値に含まれる誤差を考慮した判定を行えるようにする。信頼区間とは、データをｎ個だけ読み込んだ時に、正確な評価値が高い確率１−δで存在している区間をいう。なお、δは信頼区間の誤り確率を表す。
【００３７】
ところで、スプリット評価値を得る評価関数がデータへのフィッティング項と木の複雑さに伴うペナルティ項に分かれる場合、ペナルティ項には対数が用いられていることが予想される。このような場合、評価関数全体を確率変数とみて信頼区間を求めることはできない。スプリット評価値信頼区間計算手段１０３３は、そのような場合には、評価関数のうち確率変数にあたる部分のみ（上述の例でいえば、左・右葉に落ちるデータの割合、左・右葉のデータの二乗誤差）に着目して信頼区間を着目し、それらの信頼区間をつかって評価関数全体の信頼区間を算出する。
【００３８】
スプリット評価値信頼区間計算手段１０３３は、例えば、上述の式（１）を、以下に示す式（２）〜式（７）を使って最大化および最小化することで、スプリット評価値の信頼区間を計算してもよい。なお、式（２）〜式（７）は、葉に落ちたデータの二乗誤差はχ二乗分布に従うという仮定を基にしたスプリット評価値の信頼区間の導出用の条件式の例であるが、これに限定されない。
【００３９】
【数２】
2014241060.tif 000004
【００４０】
スプリットポイント検索手段１０３４は、説明変数の次元ごとに最もよいスプリットポイントを検索する。スプリットポイント検索手段１０３４は、説明変数の各次元について、スプリット評価値計算手段１０３２に対象ノードにおけるスプリットの各候補点でのスプリット評価値を計算させ、その結果を基に、説明変数の次元ごとに最もよいスプリットポイントを検索する。スプリットポイント検索手段１０３４は、例えば、各次元で最もよいスプリット評価値を得た候補点を当該次元で最もよいスプリットポイントとすればよい。
【００４１】
スプリットポイント計算手段１０３ではこのようにして、説明変数の次元ごとに、対象ノードにおいてスプリットするのに最もよいとされるスプリットポイントの情報として、スプリット条件と、スプリット評価値と、信頼区間とを計算によって得る。
【００４２】
スプリット無し計算手段１０４は、対象ノードをスプリットしない場合の評価値およびその信頼区間を計算する手段であって、スプリット無し評価値計算手段１０４１と、スプリット無し評価値信頼区間計算手段１０４２とを含む。
【００４３】
スプリット無し評価値計算手段１０４１は、予め定められている評価関数を用い、対象ノードをスプリットしない場合の評価値を計算する。以下では、スプリット無し評価値計算手段１０４１が計算した評価値を「スプリット無し評価値」という場合がある。スプリット無し評価値計算手段１０４１は、例えば以下の式（８）で表される評価関数を使い、スプリット無し評価値を計算してもよい。
【００４４】
【数３】
2014241060.tif 000005
【００４５】
式（８）において、Ｎは対象ノードに落ちるデータの総数を表している。また、ハット付きのσの二乗は対象ノードに落ちたデータの目的変数の分散を表している。なお、学習データは、スプリット評価値を求めたときの学習データと同じものを用いる。具体的には、ビンニング手段１０３１が算出した統計量を利用すればよい。
【００４６】
スプリット無し評価値計算手段１０４１が用いる評価関数は、対象ノードにおける木の成長に対してトレードオフ関係になる２種類の項を含んでいればよい。上記評価関数の例では、葉におけるフィット具合を評価値の良さで表す項と、木の複雑さによって評価値を悪くするペナルティ項とが含まれ、これらがトレードオフ関係になっている。具体的には、式（８）では、第２項が葉ノードに関するペナルティ項となっており、葉ノードに落ちるデータの数に応じたペナルティを掛けている。なお、式（８）はスプリット無し評価値を求める評価関数の一つの例であり、これに限られない。
【００４７】
スプリット無し評価値信頼区間計算手段１０４２は、スプリット無し評価値計算手段１０４１が算出したスプリット無し評価値の信頼区間を求める。スプリット無し評価値信頼区間計算手段１０４２は、例えば、上述の式（８）を、以下に示す式（９）を使って最大化および最小化することで、スプリット無し評価値の信頼区間を計算してもよい。
【００４８】
【数４】
2014241060.tif 000006
【００４９】
なお、式（９）は、葉に落ちたデータの二乗誤差はχ二乗分布に従うという仮定を基にしたスプリット無し評価値の信頼区間の導出用の条件式の一例であり、これに限られない。
【００５０】
スプリット無し計算手段１０４ではこのようにして、対象ノードでスプリットしない場合の評価値であるスプリット無し評価値と、その信頼区間とを計算によって得る。
【００５１】
スプリット判定手段１０６は、スプリットポイント計算手段１０３およびスプリット無し計算手段１０４によって得られた評価値およびその信頼区間に基づいて、スプリットするか否かを判定する。スプリット判定手段１０６は、例えば、対象ノードにおける次元ごとの最もよいスプリットポイントでのスプリット評価値およびスプリット無し評価値の中で最もよい評価値がスプリット評価値であればそのスプリット評価値を得た次元でのスプリットポイントでスプリットし、一方、最もよい評価値がスプリット無し評価値であれば対象ノードではスプリットしないとの判定をしてもよい。
【００５２】
また、スプリット判定手段１０６は、各評価値の信頼区間も考慮に加えて、次の三つの選択肢による判定を行ってもよい。すなわち、スプリット判定手段１０６は、当該判定において、対象ノードに対して、スプリットする、スプリットしない、学習データの追加のいずれかを決定するようにしてもよい。なお、学習データの追加を決定した場合は、対象ノードに対するスプリット有無の判定は保留される。スプリット判定手段１０６は、例えば、対象ノードにおける次元ごとの最もよいスプリットポイントでのスプリット評価値およびスプリット無し評価値の中から評価の高い１位と２位を抽出する。そして、その１位と２位の評価値の信頼区間に重なりがある場合には処理したデータ数ではスプリット有無を決定するのに十分でないとして、さらに学習データを読み込んで評価値を再計算させてもよい。一方、信頼区間に重なりがなければ、上述した場合と同様に１位の評価値がスプリット評価値であるかスプリット無し評価値であるかによってスプリットするか否かを判定すればよい。ここで、評価値の信頼区間に重なりがある場合とは、具体的には、１位の評価値の信頼区間の下限が、２位の評価値の信頼区間の上限よりも小さい場合をいう。
【００５３】
木ノード生成手段１０７は、スプリット判定手段１０６による判定の結果、対象ノードをスプリットすることが決定した場合に、対象ノードを指定されたスプリット次元およびスプリット値でスプリットする。具体的には、対象ノードに子ノードを追加して対象ノードを親ノードとし、該親ノードに予測値、スプリット次元、スプリット値の情報を対応づけ、子ノードに該子ノードに落ちるデータのＩＤを対応づける。そして、これらの情報を木モデル記憶部１０２に格納する。
【００５４】
予測手段２０は、未知のデータサンプルが入力された場合に、木モデル記憶部１０２に格納されている木のモデルを用いて、予測を行う。予測手段２０は、例えば入力されたデータサンプルから得られる説明変数の各次元の値を基に、木のモデルをルートから辿り、最終的に辿り着いた葉ノードに対応づけられる予測値を返す処理を行えばよい。
【００５５】
なお、図示省略しているが、木モデル学習装置１０には、木のモデル学習に関して、学習データを読み出したり、各処理手段を起動して、必要な作業指示を与えるなどの全体制御を行う学習指示手段が含まれていてもよい。学習指示手段は、例えばプログラムに従って動作するＣＰＵ（例えば、図２に示す演算部１１）によって実現される。
【００５６】
次に、本実施形態の動作について説明する。
【００５７】
図６は、本実施形態の木モデル学習システムの動作の一例を示すフローチャートである。図６に示す例では、まず木モデル学習装置１０（より具体的には、学習指示手段）が、データ記憶部１０１から学習データを読み出して、ビンニングポイント計算手段１０５を起動する。起動されたビンニングポイント計算手段１０５は、読み出された学習データを基に、説明変数の各次元についてビンニングポイントを計算する（ステップＳ１０１）。以下では、ビンニングとして１００等分する例を示す。例えば、ある説明変数の次元が０から１０００までの値をとる場合、値１０刻みにビンニングポイントが置かれる。
【００５８】
次に、木モデル学習装置１０は、ノードキュー（以下、ＮＱと略記する）にルートノードを追加する（ステップＳ１０２）。なお、ＮＱは追加した順番でノードを取り出すことができるＦＩＦＯ構造のバッファである。なお、木モデル記憶部１０２には、ルートノードに関する情報として、当該ノードに落ちるデータのＩＤに全学習データが指定された情報が格納されているものとする。
【００５９】
次に、木モデル学習装置１０は、ＮＱが空かどうかをチェックし（ステップＳ１０３）、空でなければＮＱからノードを１つ取り出す（ステップＳ１０３のＮｏ，Ｓ１０４）。ここでは、最初にルートノードが取り出される。以下、ステップＳ１０４で取り出されたノードをスプリットの対象ノードとし、ステップＳ１０５〜Ｓ１１５の処理を行う。
【００６０】
一方、ＮＱが空であれば木のモデル学習を終了する（ステップＳ１０３のＹｅｓ）
【００６１】
ステップＳ１０５では、ＮＱから取り出した対象ノードについて、木モデル学習装置１０は、対象ノードに落ちるデータのＩＤ集合を参照して、対象ノードに落ちるｎ個の学習データを読み込む。
【００６２】
次いで、木モデル学習装置１０は、算出対象とする説明変数の次元を表す変数Ｄを初期化する（ステップＳ１０６）。ここでは、第１次元を表すようＤ＝１とする。
【００６３】
対象ノードに対して、学習データの読み込みおよび変数Ｄの初期化が完了すると、木モデル学習装置１０は、スプリットポイント計算手段１０３を起動して、変数Ｄが示す次元について、対象ノードにおいて最もよいスプリットポイントを求める処理を開始させる。
【００６４】
スプリットポイント計算手段１０３が起動すると、まずビンニング手段１０３１が、変数Ｄが示す次元についてビンニング処理を行う（ステップＳ１０７）。ビンニング手段１０３１は、ビンニングポイント計算手段１０５で計算したビンニングポイントを基に、ステップＳ１０５で読み出されたｎ個の学習データを処理し、ビンごとの統計量を計算する。ビンニング手段１０３１は、例えば、あるビンが［１０，２０）の範囲であった場合、説明変数のＤ次元目がこの範囲のデータについて、当該ビンの統計量として目的変数の二乗和と、目的変数の和、データ数を計算し、ビンの統計情報として保存する。なお、後述する判定処理の結果、同一ノード、同一次元に対して学習データが追加された後の当該ステップ処理では、保存されているビンの統計情報に対してビンの統計量を累積していく。
【００６５】
次に、スプリットポイント検索手段１０３４が、変数Ｄが示す次元で最もよいスプリットポイントを探索する（ステップＳ１０８）。ステップＳ１０８では、スプリットポイント検索手段１０３４は、まずスプリット評価値計算手段１０３２を起動して、変数Ｄが示す次元によるスプリットの各候補点のスプリット評価値を計算させる。スプリット評価値計算手段１０３２は、ステップＳ１０７で作成されるビンの統計情報を基に、指定された次元のスプリットの候補点である各ビンとビンの間でスプリットした場合のスプリット評価値を、例えば式（１）を使い計算する。
【００６６】
次いで、スプリット評価値信頼区間計算手段１０３３が、ステップＳ１０８で求めたスプリット評価値の信頼区間を計算する（ステップＳ１０９）。スプリット評価値信頼区間計算手段１０３３は、ステップＳ１０８で求めたスプリット評価値の信頼区間を、例えば式（２）〜（７）を使い計算する。
【００６７】
次に、スプリットポイント検索手段１０３４は、D＜次元数かの判定を行い、そうであればＤをインクリメントした上でステップＳ１０７に戻る（ステップＳ１１０のＹｅｓ，Ｓ１１１）。一方、D＜次元数でなければ全ての次元について当該処理を完了したとして、ステップＳ１１２に進む（ステップＳ１１０のＮｏ）。
【００６８】
以上の処理によって、評価変数の全ての次元について、評価関数を最大にするスプリットポイントと、そのスプリット評価値と、その信頼区間とを得る。
【００６９】
ステップＳ１１２に進むと、木モデル学習装置１０は、スプリット無し計算手段１０４を起動して、対象ノードにおいてスプリットしない場合の評価値（スプリット無し評価値）とその信頼区間を計算させる。ステップＳ１１２では、まずスプリット無し評価値計算手段１０４１が、スプリット無し評価値を計算する。スプリット無し評価値計算手段１０４１は、対象ノードにおいてスプリットしない場合の評価値を、例えば式（８）を使い計算する。
【００７０】
次いで、スプリット無し評価値信頼区間計算手段１０４２が、ステップＳ１１２で求めたスプリット無し評価値の信頼区間を計算する（ステップＳ１１３）。スプリット無し評価値信頼区間計算手段１０４２は、ステップＳ１１２で求めたスプリット無し評価値の信頼区間を、例えば式（８）、（９）を使い計算する。
【００７１】
このようにして対象ノードについて、各次元のスプリットポイントでのスプリット評価値とその信頼区間と、スプリット無し評価値とその信頼区間とが求まると、スプリット判定手段１０６が、対象ノードをスプリットをするか否か、もしくは学習データを追加するかを判定する（ステップＳ１１４）。
【００７２】
ステップＳ１１４では、スプリット判定手段１０６が、例えばこれら評価値の中で最も評価のよい１位および２位を求め、その結果により次のように判定する。
【００７３】
以下に示す例では、ケース１を「１位の評価値がある次元のスリット評価値であり、かつ、１位の評価値の信頼区間の下限より２位の評価値の信頼区間の上限が小さい」場合とし、ケース２を「１位の評価値がスプリット無し評価値であり、かつ、１位の評価値の信頼区間の下限より２位の評価値の信頼区間の上限が小さい」場合とし、ケース３を「１位の評価値がいずれの評価値であれ、１位の評価値の信頼区間の下限より２位の評価値の信頼区間の上限が大きい」場合とする。スプリット判定手段１０６は、１位および２位の評価値が３つのうちのいずれのケースに該当するかを判定し、ケース１であれば、１位の評価値を得たスプリット候補点でスプリットする旨の決定をする。また、ケース２であれば、スプリットしない旨の決定をする。また、ケース３であれば、処理したデータ数ではスプリット有無を決定するのに十分でないとして学習データを追加する旨の決定をする。
【００７４】
ステップＳ１１４の判定の結果、スプリットする旨が決定された場合には、木ノード生成手段１０７が、指定された次元のスプリットポイントで対象ノードをスプリットする（ステップＳ１１５）。木ノード生成手段１０７は、具体的には、木モデル記憶部１０２に、対象ノードを親ノードとする子ノードの情報を新たに追加し、親ノードである対象ノードに対して追加した子ノードへのエッジに対応する説明変数の条件を対応づけるとともに、追加した子ノードに対して予測値と当該子ノードに落ちる学習データのＩＤリストとを対応づけて保持させる。また、木ノード生成手段１０７は、ノードを追加した際には、追加した子ノードをＮＱに追加する。これにより、次回以降のスプリットの判定対象ノードに追加した子ノードが加えられる。
【００７５】
一方、ステップＳ１１４の判定の結果、スプリットしない旨が決定された場合には、木モデル学習装置１０は、対象ノードをスプリットさせずに当該対象ノードに関する処理を終了し、次のノードのスプリット有無を判定するためにステップＳ１０３に戻る。戻った先のステップＳ１０３では、あるノードにおけるスプリット判定の結果、ステップＳ１１５でＮＱに追加された子ノードがあれば、それら子ノードが順に取り出されて、対象ノードとされる。このようにして、ＮＱが空になるまで対象ノードを変えながら、スプリット判定を繰り返し行っていく過程で木が成長していく。
【００７６】
一方、ステップＳ１１４の判定の結果、学習データを追加する旨が決定された場合には、対象ノードはそのままにステップＳ１０５に戻る。木のモデル学習の高速化のために、Ｈｏｅｆｆｄｉｎｇ木アルゴリズムを取り入れた場合、求まる評価値は誤差を含んだ値となる。従って、上記判定において、その誤差を含めても１位の評価値が２位の評価値よりも高ければその評価値によりスプリットの有無を決定するが、そうでなければ学習データの追加を決定するようにしている。ステップＳ１０５に戻ると、学習データがｎ個追加され、ステップＳ１０８およびＳ１１２で評価値が再計算される。このような学習データの追加を、例えばステップＳ１１４の判定で対象ノードにおけるスプリットの有無が決定できる精度になるまで繰り返す。
【００７７】
以上のように、本実施形態によれば、枝刈り用のテストデータセットを用意すること無しに、汎化性能の意味で適切なサイズの木のモデルを学習できる。その理由は、各ノードにつき、木の成長に対してトレードオフの関係にある２項を含む評価関数を用いて複数のスプリット候補の良し悪しを決めるスプリット評価値を計算する手段と、同じく木の成長に対してトレードオフの関係にある２項を含む評価関数を用いてスプリットしない場合の評価値を計算する手段とを備えているからである。それにより、各ノードでスプリットするのが良いのかストップするのが良いのかを、各々データへのフィッティング具合と木の複雑さ具合とを比較考量して表す評価値を用いて判定できるからである。そして、そのような評価値を用いて各ノードでスプリット有無の判定を行うことで、汎化性能の意味で最適なサイズで木の成長を止めることができるからである。
【００７８】
また、本実施形態によれば、そのような汎化性能の意味で最適なサイズとなる木のモデル学習を高速に行うことができる。その理由は、データの一部分から計算された上記評価値の信頼区間を計算する手段を備えているからである。それにより、全データを処理しなくても、精度の担保に必要な統計的に十分な一部のデータだけでスプリット有無を決定できるからである。
【００７９】
実施形態２．
図７は、本発明の第２の実施形態の木モデル学習システムの構成例を示すブロック図である。本実施形態の木モデル学習システムは、図１に示す木モデル学習システムと比べて、スプリットポイント計算手段１０３がスプリットポイント並列計算手段２０３となっている点、および新たに計算不要次元削除手段１０８を備えている点が異なる。
【００８０】
本実施形態において、スプリットポイント並列計算手段２０３は、第１の実施形態においてスプリットポイント計算手段１０３が次元ごとに行っていた処理を次元別に並列に処理する。スプリットポイント並列計算手段２０３は、例えば、説明変数の次元数分備えられる。
【００８１】
計算不要次元削除手段１０８は、ある対象ノードについてスプリット判定手段１０６が学習データの追加を決定した場合に、学習データ追加後の評価値の再計算の対象から除外可能なスプリット次元の有無を判定し、あれば当該スプリット次元を再計算の対象から削除する処理を行う。
【００８２】
計算不要次元削除手段１０８は、例えば、スプリット判定手段１０６が判定を行ったときに得ていた評価値の中で、１位の評価値の信頼区間の下限よりも、信頼区間の上限が小さい評価値があれば、その評価値を得た次元については当該ノードにおける以降の評価値の再計算の対象から除外する処理を行ってもよい。すなわち、ある次元の最もよいスプリットポイントでの評価値の信頼区間の上限が、１位の評価値の信頼区間の下限よりも小さければ、当該次元は以降の評価値の再計算の対象から除外される。
【００８３】
計算不要次元削除手段１０８は、例えば、再計算時に、除外対象となった次元に対応づけられているスプリットポイント並列計算手段２０３が起動されないように、その旨を示すフラグ等を設けてもよい。
【００８４】
図８は、本実施形態の木モデル学習システムの動作の一例を示すフローチャートである。図８に示すように、本実施形態の動作は、図６に示す第１の実施形態の動作と比べて、次元を示す変数Ｄに関する処理が削除されてステップＳ１０７〜Ｓ１０９の処理が並列実行される点、および計算不要次元削除ステップ（ステップＳ２０１）が追加される点が異なる。
【００８５】
ステップＳ１０７〜Ｓ１０９の並列実行は、例えば、対象ノードに対して、学習データの読み込みが完了すると、木モデル学習装置１０が、各スプリットポイント並列計算手段２０３を起動して、対応する次元について、対象ノードにおいて最もよいスプリットポイントを求める処理を開始させればよい。
【００８６】
また、ステップＳ２０１では、学習データの追加が決定されたことを受けた計算不要次元削除手段１０８が、学習データ追加後の評価値の再計算の対象から除外可能なスプリット次元の有無を判定し、あればあれば当該スプリット次元を再計算の対象から削除する処理を行う。計算不要次元削除手段１０８は、判定に用いた評価値の中から１位の評価値と任意の順位ｉの評価値を比べ、一位の評価値の信頼区間の下限より順位ｉの評価値の信頼区間の上限の方が小さい場合に、当該順位ｉの評価値を得たスプリット次元をそのノードについての以降のスプリットポイントの計算対象から除外する処理を行う。
【００８７】
以上のように、本実施形態によれば、処理のボトルネックとなる、スプリット候補の各評価値を得るための計算部分を並列化して行うだけでなく、さらに計算不要次元を削除する手段を備えることで、計算が不要な次元のスプリットポイントの再計算処理を省くことができ、さらに高速化される。
【００８８】
次に、本発明による木モデル学習装置の最小構成について説明する。図９は、本発明による木モデル学習装置の最小の構成例を示すブロック図である。図９に示すように、本発明による木モデル学習装置は、最小の構成要素として、スプリット評価値計算手段５１と、スプリットポイント検索手段５２と、スプリット無し評価値計算手段５３と、スプリット判定手段５４とを備える。
【００８９】
スプリット評価値計算手段５１（例えば、スプリット評価値計算手段１０３２）は、説明変数の指定された次元を用いて、指定されたノードを当該次元の各スプリットポイントでスプリットする場合の評価値を計算する。
【００９０】
スプリットポイント計算手段５２（例えば、スプリットポイント検索手段１０３４）は、スプリット評価値計算手段５１によって得られる評価値を基に、説明変数の次元ごとに指定されたノードをスプリットするのに最もよいスプリットポイントを検索する。
【００９１】
スプリット無し評価値計算手段５３（例えば、スプリット無し評価値計算手段１０４１）は、指定されたノードをスプリットしない場合の評価値を計算する。
【００９２】
スプリット判定手段５４は、説明変数の次元ごとの最もよいスプリットポイントでの評価値と、スプリットしない場合の評価値とを基に、指定されたノードを最も評価値のよい次元でスプリットするか、または指定されたノードをスプリットしないかを判定する。
【００９３】
本発明において、スプリット評価値計算手段５１は、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、分岐ノードと葉ノードに関して、それぞれ通過データ数または落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算する。また、スプリット無し評価値計算手段５３は、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、葉ノードに関して、落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算する。
【００９４】
従って、最小構成の木モデル学習装置によれば、汎化性能の意味で適切なサイズの木のモデルを、枝刈り用のテストセットなしに高速に得ることができる。木の成長に対してトレードオフの関係にある２項を含む評価関数を用いて複数のスプリット候補の良し悪しを決めるスプリット評価値を計算するとともに、同じく木の成長に対してトレードオフの関係にある２項を含む評価関数を用いてスプリットしない場合の評価値を計算することによって、シンプルな学習手法を維持したまま、木の成長をどこで止めるべきかの判定が妥当性をもって行えるからである。
【００９５】
また、図１０は、本発明の木モデル学習装置の他の構成例を示すブロック図である。図１０に示すように、本発明による木モデル学習装置は、スプリット評価値信頼区間計算手段５５と、スプリット無し評価値信頼区間計算手段５６とを備えていてもよい。
【００９６】
スプリット評価値信頼区間計算手段５５（例えば、スプリット評価値信頼区間計算手段１０３３）は、スプリット評価値計算手段５１によって計算された評価値の信頼区間を計算する。また、スプリット無し評価値信頼区間計算手段５６（例えば、スプリット無し評価値信頼区間計算手段１０４２）は、スプリット無し評価値計算手段５３によって計算された評価値の信頼区間を計算する。
【００９７】
また、そのような場合にスプリット判定手段５４は、ノードに対して所定数のデータが読み込まれてスプリットする場合の評価値とスプリットしない場合の評価値とが計算される度に、説明変数の次元ごとの最もよいスプリットポイントでの評価値およびそれらの信頼区間と、スプリットしない場合の評価値およびその信頼区間とを基に、ノードを最も評価値のよい次元でスプリットするか、またはノードをスプリットしないか、もしくは処理したデータ数ではスプリットするか否かを決定するのに十分でないかを判定してもよい。
【００９８】
そのような構成によれば、学習データの一部のみを用いて木のモデル学習を行うことができるので、さらに高速に汎化性能の意味で適切なサイズの木のモデルを得ることができる。
【００９９】
また、木モデル学習装置は、各次元についての少なくともスプリット評価値計算手段５１による評価値の計算処理を並列で動作させてもよい。
【０１００】
そのような構成によれば、さらに高速に汎化性能の意味で適切なサイズの木のモデルを得ることができる。
【０１０１】
また、木モデル学習装置は、スプリット判定手段５４が処理したデータ数ではスプリットするか否かを決定するのに十分でないと判断した場合には、指定されたノードに対してさらにデータを読み込んで、指定されたノードをスプリットする場合の評価値およびその信頼区間と、スプリットしない場合の評価値およびその信頼区間とを再計算させてもよい。
【０１０２】
そのような構成によれば、１度に読み込むデータ数を調整することにより、さらに高速に汎化性能の意味で適切なサイズの木のモデルを得ることができる。
【０１０３】
また、木モデル学習装置は、さらに計算不要次元削除手段５７を備えていてもよい。計算不要次元削除手段５７（例えば、計算不要次元削除手段１０８）は、スプリット判定手段５４により処理したデータ数ではスプリットするか否かを決定するのに十分でないと判定された場合に、その判定時に最もよかった評価値の信頼区間の下限よりも、２番以降の評価値の信頼区間の上限が小さい次元を、新たに読み込んだデータを用いた評価値およびその信頼区間の再計算の対象から除外する処理を行う。
【０１０４】
そのような構成によれば、計算が不要な次元のスプリットポイントの再計算処理を省くことができるので、さらに高速に汎化性能の意味で適切なサイズの木のモデルを得ることができる。
【０１０５】
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１０６】
例えば、本発明の他の態様としては、上記各実施態様に係る各構成をコンピュータに実現させるコンピュータプログラムであってもよいし、このようなプログラムを記録したコンピュータが読み取り可能な記憶媒体であってもよい。この記録媒体は、非一時的な有形の媒体を含む。
【０１０７】
また、上記の実施形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１０８】
（付記１）ルートノードから順に、各ノードに対して、説明変数の次元ごとに、当該ノードを当該次元の各スプリットポイントでスプリットする場合の評価値を、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、分岐ノードと葉ノードに関して、それぞれ通過データ数または落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて計算し、得られた評価値を基に、説明変数の次元ごとにノードをスプリットするのに最もよいスプリットポイントを検索し、ノードをスプリットしない場合の評価値を、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、葉ノードに関して、落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて計算し、次元ごとの最もよいスプリットポイントでの評価値と、スプリットしない場合の評価値とを基に、ノードを最も評価値のよい次元でスプリットするか、またはノードをスプリットしないかを判定する木モデル学習方法。
【０１０９】
（付記２）少なくとも次元ごとの最もよいスプリットポイントでの評価値とスプリットしない場合の評価値とについて、各々信頼区間を計算し、ノードに対して所定数のデータが読み込まれてスプリットする場合の評価値とスプリットしない場合の評価値とが計算される度に、次元ごとの最もよいスプリットポイントでの評価値およびそれらの信頼区間と、スプリットしない場合の評価値およびその信頼区間とを基に、ノードを最も評価値のよい次元でスプリットするか、またはノードをスプリットしないか、もしくは処理したデータ数ではスプリットするか否かを決定するのに十分でないかを判定する付記１に記載の木モデル学習方法。
【０１１０】
（付記３）処理したデータ数ではスプリットするか否かを決定するのに十分でないと判定した場合には、ノードに対してさらにデータを読み込んで、ノードをスプリットする場合の評価値およびその信頼区間と、スプリットしない場合の評価値およびその信頼区間とを再計算させる付記２に記載の木モデル学習方法。
【０１１１】
（付記４）処理したデータ数ではスプリットするか否かを決定するのに十分でないと判定した場合に、その判定時に最もよかった評価値の信頼区間の下限よりも、２番以降の評価値の信頼区間の上限が小さい次元を、新たに読み込んだデータを用いた評価値およびその信頼区間の再計算の対象から除外する付記３に記載の木モデル学習方法。
【０１１２】
（付記５）各次元についての少なくともスプリットする場合の評価値を計算する処理を並列で動作させる付記１から付記４のうちのいずれかに記載の木モデル学習方法。
【０１１３】
（付記６）コンピュータに、説明変数の指定された次元を用いて、指定されたノードを当該次元の各スプリットポイントでスプリットする場合の評価値を計算するスプリット評価値計算処理、スプリット評価値計算処理によって得られる評価値を基に、説明変数の次元ごとに指定されたノードをスプリットするのに最もよいスプリットポイントを検索するスプリットポイント検索処理、ノードをスプリットしない場合の評価値を計算するスプリット無し評価値計算処理、および次元ごとの最もよいスプリットポイントでの評価値と、スプリットしない場合の評価値とを基に、ノードを最も評価値のよい次元でスプリットするか、またはノードをスプリットしないかを判定するスプリット判定処理を実行させ、スプリット評価値計算処理で、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、分岐ノードと葉ノードに関して、それぞれ通過データ数または落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算させ、スプリット無し評価値計算処理で、木の成長に対してトレードオフの関係にある２種類の項であって、データへのフィッティングを評価値の良さで表す項と、葉ノードに関して、落ちるデータ数に応じて評価値を悪くする方向に働くペナルティ項の２種類の項を少なくとも含む評価関数を用いて、評価値を計算させるための木モデル学習プログラム。
【０１１４】
（付記７）コンピュータに、スプリット評価値計算処理で計算された評価値の信頼区間を計算するスプリット評価値信頼区間計算処理、およびスプリット無し評価値計算処理で計算された評価値の信頼区間を計算するスプリット無し評価値信頼区間計算処理を実行させ、スプリット判定処理で、ノードに対して所定数のデータが読み込まれてスプリットする場合の評価値とスプリットしない場合の評価値とが計算される度に、次元ごとの最もよいスプリットポイントでの評価値およびそれらの信頼区間と、スプリットしない場合の評価値およびその信頼区間とを基に、ノードを最も評価値のよい次元でスプリットするか、またはノードをスプリットしないか、もしくは処理したデータ数ではスプリットするか否かを決定するのに十分でないかを判定させる付記６に記載の木モデル学習プログラム。
【０１１５】
（付記８）コンピュータに、スプリット判定処理において処理したデータ数ではスプリットするか否かを決定するのに十分でないと判定された場合に、ノードに対してさらにデータを読み込んで、ノードをスプリットする場合の評価値およびその信頼区間と、スプリットしない場合の評価値およびその信頼区間とを再計算させる付記７に記載の木モデル学習プログラム。
【０１１６】
（付記９）コンピュータに、スプリット判定処理において処理したデータ数ではスプリットするか否かを決定するのに十分でないと判定された場合に、その判定時に最もよかった評価値の信頼区間の下限よりも、２番以降の評価値の信頼区間の上限が小さい次元を、新たに読み込んだデータを用いた評価値およびその信頼区間の再計算の対象から除外する計算不要次元削除処理を実行させる付記８に記載の木モデル学習プログラム。
【０１１７】
（付記１０）コンピュータに、各次元についての少なくともスプリット評価値計算処理を並列で動作させる付記６から付記９までのいずれかに記載の木モデル学習プログラム。
【産業上の利用可能性】
【０１１８】
本発明は、回帰木や決定木に限らず、データ空間の分割を木で表現する木のモデルを得る用途に好適に適用可能である。
【符号の説明】
【０１１９】
１０  木モデル学習装置
１０１  データ記憶部
１０２  木モデル記憶部
１０３  スプリットポイント計算手段
１０３１  ビンニング手段
１０３２  スプリット評価値計算手段
１０３３  スプリット評価値信頼区間計算手段
１０３４  スプリットポイント検索手段
１０４  スプリット無し計算手段
１０４１  スプリット無し評価値計算手段
１０４２  スプリット無し評価値信頼区間計算手段
１０５  ビンニングポイント計算手段
１０６  スプリット判定手段
１０７  木ノード生成手段
１０８  計算不要次元削除手段
２０  予測手段
【図１】
2014241060.tif 000007
【図２】
2014241060.tif 000008
【図３】
2014241060.tif 000009
【図４】
2014241060.tif 000010
【図５】
2014241060.tif 000011
【図６】
2014241060.tif 000012
【図７】
2014241060.tif 000013
【図８】
2014241060.tif 000014
【図９】
2014241060.tif 000015
【図１０】
2014241060.tif 000016