"入力データを受け付けるルートノードと、複数の子ノードのうち一つの子ノードを入力データに従って選択する判断ノードおよび子ノードを有さないリーフノードのうち少なくとも一方と、が階層的に接続された決定木により前記入力データを処理する情報処理装置であって、前記ルートノード、判断ノード、およびリーフノードのそれぞれを識別するために、識別情報を二進数の表記により設定する設定手段と、それぞれの判断ノードによって、入力データに対する判断処理を行い、当該判断処理によって選択された子ノードの前記識別情報をそれぞれの判断ノードの選択結果として出力する判断手段と、同一階層に含まれる前記判断ノードの選択結果として求められた前記子ノードの識別情報に対してビットワイズ論理和演算を行う演算手段と、前記ビットワイズ論理和演算の結果に対してビットワイズ論理積演算を行い、当該ビットワイズ論理積演算により求められた二進数の表記を識別情報として有するリーフノードを検索し、当該検索されたリーフノードに関連付けられたクラスを前記入力データに対する決定木の実行結果として決定する決定手段と、を備えることを特徴とする情報処理装置。前記設定手段は、n個のリーフノードの識別情報をnビットの二進数の表記により設定し、子ノードとして有するリーフノードの識別情報に対するビットワイズ論理和演算により求めた二進数の表記を前記判断ノードの識別情報として設定することを特徴とする請求項1に記載の情報処理装置。それぞれの判断ノードの処理を、プログラム実行主体であるスレッドが一つのシングルスレッド環境、または、複数のスレッドが同時に処理を行うマルチスレッド環境で実行するために、各スレッドがアクセスできる記憶領域に前記入力データを保持する記憶手段を更に備えることを特徴とする請求項1または2に記載の情報処理装置。前記判断手段は、それぞれの判断ノードにおける判断処理を前記マルチスレッド環境で実行することを特徴とする請求項3に記載の情報処理装置。前記判断手段は、一つの判断ノードに対して一つのスレッドを割り当てることを特徴とする請求項4に記載の情報処理装置。前記判断手段は、同一階層に含まれる複数の判断ノードに対して一つのスレッドを割り当てることを特徴とする請求項4に記載の情報処理装置。前記判断手段は、同一階層に含まれる複数の判断ノードおよびルートノードに対して一つのスレッドを割り当てることを特徴とする請求項4に記載の情報処理装置。一のスレッドの処理と他のスレッドの処理とを同期させるために各スレッドの実行タイミングを制御する同期手段を更に備えることを特徴とする請求項3乃至7のいずれか1項に記載の情報処理装置。前記決定木による前記入力データの処理は、前記マルチスレッド環境を提供するGPGPUGeneralpurposecomputingongraphicsprocessingunits上の一つのワークグループOpenCL上で実行されることを特徴とする請求項3に記載の情報処理装置。コンピュータを、請求項1乃至9のいずれか1項に記載の情報処理装置の各手段として機能させるためのプログラム。入力データを受け付けるルートノードと、複数の子ノードのうち一つの子ノードを入力データに従って選択する判断ノードおよび子ノードを有さないリーフノードのうち少なくとも一方と、が階層的に接続された決定木により前記入力データを処理する情報処理装置のおける情報処理方法であって、前記情報処理装置の設定手段が、前記ルートノード、判断ノード、およびリーフノードのそれぞれを識別するために、識別情報を二進数の表記により設定する設定工程と、前記情報処理装置の判断手段が、それぞれの判断ノードによって、入力データに対する判断処理を行い、当該判断処理によって選択された子ノードの前記識別情報をそれぞれの判断ノードの選択結果として出力する判断工程と、前記情報処理装置の演算手段が、同一階層に含まれる前記判断ノードの選択結果として求められた前記子ノードの識別情報に対してビットワイズ論理和演算を行う演算工程と、前記情報処理装置の決定手段が、前記ビットワイズ論理和演算の結果に対してビットワイズ論理積演算を行い、当該ビットワイズ論理積演算により求められた二進数の表記を識別情報として有するリーフノードを検索し、当該検索されたリーフノードに関連付けられたクラスを前記入力データに対する決定木の実行結果として決定する決定工程と、を有することを特徴とする情報処理方法。しかしながら特許文献1の手法はデータのメモリ配置を工夫したものであり、決定木の実行に際しては、一つのスレッドが判断ノードを渡り歩きながら、判断を繰り返すことで結果を得ている。多くの計算コアスレッドがある状況では、いかに多くの計算コアを同時に計算に参加させ、アイドルコアを減らすことができるかが重要である。決定木の実行に関する従来の技術では、アイドルコアを減らすことができず、並列化による実行の高速化が図れない、という課題がある。本発明は、アイドルコアを減らし、処理の高速化を図ることが可能な情報処理技術を提供する。本発明の一つの側面にかかる情報処理装置は、入力データを受け付けるルートノードと、複数の子ノードのうち一つの子ノードを入力データに従って選択する判断ノードおよび子ノードを有さないリーフノードのうち少なくとも一方と、が階層的に接続された決定木により前記入力データを処理する情報処理装置であって、前記ルートノード、判断ノード、およびリーフノードのそれぞれを識別するために、識別情報を二進数の表記により設定する設定手段と、それぞれの判断ノードによって、入力データに対する判断処理を行い、当該判断処理によって選択された子ノードの前記識別情報をそれぞれの判断ノードの選択結果として出力する判断手段と、同一階層に含まれる前記判断ノードの選択結果として求められた前記子ノードの識別情報に対してビットワイズ論理和演算を行う演算手段と、前記ビットワイズ論理和演算の結果に対してビットワイズ論理積演算を行い、当該ビットワイズ論理積演算により求められた二進数の表記を識別情報として有するリーフノードを検索し、当該検索されたリーフノードに関連付けられたクラスを前記入力データに対する決定木の実行結果として決定する決定手段と、を備えることを特徴とする。本発明によれば、アイドルコアを減らし、処理の高速化を図ることができる。第1実施形態図1を参照して決定木を用いた本発明の第1実施形態にかかる情報処理方法および情報処理装置決定木の実行方法を説明する。子ノードの選択はルートノード11から行われる。ルートノード11は入力データを受け付け、その入力データに対する判別結果として子ノード121、122のどちらを選択すべきかを判断する。複数の子ノードのうち一つを選択するノードを判断ノードと呼ぶ。図1において、判断ノードは線幅の細い円で示されている。判断ノードが何を基に判断するかは決定木によって異なるが、例えば、入力データに複数の値変数があり、それらの値と予め定めた値との比較を行って決定する。その比較の結果により、変数から求められた値により適合する子ノードを選択する。図1では判断ノードから出る太い矢印が選択結果を示している。ルートノード11では、子ノード121、122のうち、子ノード121が選択されている。同様に判断ノード121では子ノード123、124のうち、子ノード124が選択されている。そして判断ノード124では子ノード130が選択されている。判断ノード130では子ノード141が選択されているが、ノード141は子ノードを有さないリーフノードである。リーフノードでは選択は行われず、関連付けられたクラスがそのまま結果となる。図1では9というクラスが決定木の実行結果となる。図2aは決定木を用いた第1実施形態にかかる情報処理方法の流れを説明する図であり、図2bは情報処理装置20の機能構成を示す図である。情報処理装置20は、決定木により入力データを処理する。決定木はルートノードと、複数の子ノードのうち一つの子ノードを入力データに従って選択する判断ノードおよび下位の階層に子ノードを有さないリーフノードのうち少なくともいずれか一方と、が階層的に接続されたものである。設定部21は、ルートノード、判断ノード、およびリーフノードのそれぞれを識別するために、識別情報を二進数の表記により設定する。判断部22は、それぞれの判断ノードによって、入力データに対する判断処理を行い、判断処理によって選択された子ノードの識別情報をそれぞれの判断ノードの選択結果として出力する。演算部23は、同一階層に含まれる判断ノードの選択結果として求められた子ノードの識別情報に対してビットワイズ論理和演算を行う。決定部24は、ビットワイズ論理和演算の結果に対してビットワイズ論理積演算を行い、ビットワイズ論理積演算により求められた二進数の表記を識別情報として有するリーフノードを検索する。そして、決定部24は、検索されたリーフノードに関連付けられたクラスを入力データに対する決定木の実行結果として決定する。記憶部25は、それぞれの判断ノードの処理を、プログラム実行主体のスレッドが一つのシングルスレッド環境、または、複数のスレッドが同時、並列に処理を行うマルチスレッド環境で実行するために入力データを保持する。制御部26は、決定木による入力データの処理を、マルチスレッド環境を提供するGPGPUGeneralpurposecomputingongraphicsprocessingunits上の一つのワークグループOpenCL上で実行する。制御部26は、マルチスレッド環境における一のスレッドの処理と他のスレッドの処理とを同期させるために各スレッドの実行タイミングを制御する。情報処理装置20の制御部26図2bが図2aの処理の全体的な処理を制御する。ノードID付与ステップS1では、決定木の各ノードに内部処理用に、決定木を構成する各ノードを識別するために、ノードの識別情報ノードIDを設定する。設定部21はノードIDはまずリーフノードから付与する。設定部21は重複のないよう整数値を適当に割り付ける。図1の場合、リーフノードのクラスがnnは整数=0~15の16個の整数値であるので、リーフノードに関連付けられるクラスの値をn=0~15としている。クラスの関連付けは特にこの値に拘るものではない。設定部21は、最終的にn個のリーフノードの識別情報をnビットの二進数の表記により設定する。図1においてノードIDは関連付けられたクラスに基づく16桁の二進数として各ノードの近傍に表記されている。リーフノードのノードIDの付与が終了後、設定部21は判断ノードのノードIDを付与する。判断ノードのノードIDには全ての子ノードのリーフノードのノードIDをビットワイズORビットワイズ論理和演算したものを付与する。例えば、判断ノード127の場合、子ノードはふたつあり、それぞれ二進数の表記で示すと1000000000000000と0100000000000000である。これらのOR論理和演算をとると1100000000000000となる。これがノードIDとなる。同様に全ての判断ノードにノードIDを付与する。このようにリーフノードのノードIDが決定すれば、全ての判断ノードのノードIDは自動的に決定できる。ルートノードのノードIDは、ルートノードに接続しているノード判断ノード、リーフノードのノードIDを論理和演算することにより求めることができる。次に入力データ準備ステップS2を行う。本発明はIntel社やAMD社のマルチコアCPU、NVIDIA社やAMD社のGPGPU等を搭載したコンピュータ情報処理装置20上で実行可能であるが、特にそれらに拘るものではない。本発明はプログラムの実行主体であるスレッドが一つであるシングルスレッド環境でも実行可能である。また、本発明は、複数のスレッドが同時、並列に処理を行うマルチスレッド環境でも実行可能であり、処理の同時、並列化により処理の高速化を図ることが可能である。各々のスレッドは続く判断ステップS3での判断を行うにあたり、その拠り所となる入力データが必要である。入力データ準備ステップS2ではこの判断に必要な入力データを各スレッドがアクセスできる記憶領域にセットする。判断ノードごとに判断内容が異なるため、各判断ノードで必要な入力データも異なる。Intel社やAMD社のマルチコアCPUに代表されるようなSMPSymmetricMultiprocessingアーキテクチャにおいては、判断のための入力データ保管場所として共有メモリを用いる。そのため、典型的にはスレッド専用のデータ保管場所にスレッドごとに異なる入力データをセットする必要はない。そのため、このステップは省略できる。一方、NVIDIA社やAMD社のGPGPUの場合、各スレッドが排他的にアクセスできるレジスタに値をセットする高速化テクニックが用いられる。続いて、判断ステップS3では、各判断ノードにおいて、記憶領域にセットされた入力データに対し予め定められた判断処理を行い、複数ある子ノードのうち、いずれか一つを選択し、結果として返すものである。判断処理とは、例えば、入力データに含まれるある変数の値と予め定められた値とを比較し、一致するか否かでどの子ノードを選択するかというものである。より具体的な例としては、入力データ内の変数天気が、予め定められた値晴れであるか否かにより、二つある子ノードのうちのいずれかを選ぶようなものが挙げられる。このように判断処理は単に変数の値を用いて比較することもあるが、さらに複雑な計算を必要とする判断もある。例えば、入力データに輝度画像と、この画像上の2点の座標が与えられ、各座標を中心とする3×3の範囲の画素値の平均値を比較し、前者の方が大きいか否かによって選択する子ノードを決定するようなものである。いずれの場合においても、子ノードを一つ選択するが、選択した子ノードのノードIDを判断ステップS3の選択結果とする。判断ステップS3の処理は並列実行が可能である。マルチスレッド環境において、一つのスレッドが一つまたは複数の判断ノードの処理を担当する。判断ステップS3では各判断ノードの判断結果を多くのスレッドが分散して保持している。次のORステップS4とANDステップS5とによって、各スレッドが保持している結果を集計して、決定木の実行結果を算出する。ORステップS4において、演算部23は同一階層の判断ノードの結果を集計する。階層とはルートノード11から判断ノードに至るまでに通過するブランチの数である。ブランチとは決定木内で親ノードと子ノードを繋ぐ矢印で示される。図1ではルートノード11は第0階層、判断ノード121,122は第1階層、判断ノード123,124,125,126は第2階層、その他の判断ノードは第3階層である。ORステップS4では同一階層の判断ノードの選択結果ビット表示の子ノードの識別情報に対してビットワイズOR演算ビットワイズ論理和演算を行う。図1の場合における、ORステップS4の集計結果を図3に示す。集計結果は階層ごと二進数表記でまとめられる。最後にANDステップS5において、決定部24はORステップS4で同一階層ごとに集計された結果を全ての階層についてビットワイズANDビットワイズ論理積演算する。図1の場合、図3に示した集計結果を全てビットワイズANDビットワイズ論理積演算をすればよい。その結果、二進表記で0000001000000000を得る。このノードIDを持つリーフノードに関連付けられたクラスが決定木の実行結果である。図1の場合、リーフノード141がこれに該当し、結果のクラスは9となる。図1の場合、従来技法のシングルスレッド処理では4回の判断処理が必要となり、決定木の実行には4TDTαの時間がかかる。ここでTDは1回の判断にかかる時間で、Tαは分岐等その他の処理にかかる時間である。一方、本発明の実施形態にかかる判断ステップS3において各判断ノードにおける判断処理を異なるスレッドで同時に行った場合、TDTTTβの時間がかかる。TTは集計のためのスレッド間データ転送にかかる時間で、Tβはその他の処理にかかる時間である。判断処理が十分複雑でTD≫TT,Tα,Tβの場合には、本実施形態は従来技法に比べ、約4倍高速に決定木の実行処理を行うことが可能である。図1の場合では15本のスレッドを使うが、従来技法ではアイドルコアとして使われなかった余剰の演算リソースである。このように本発明の実施形態ではアイドルコアを積極的に使用することにより、従来技法に比べ高速に判断木の実行を行うことが可能になる。第2実施形態先に説明した第1実施形態の決定木は平衡二分木であったが、本発明の趣旨はこの例に限定されず、例えば図4のような決定木の構造でもよい。ルートノード41の子ノードには判断ノード421とリーフノード431があり、判断ノード421の子ノードには、判断ノード423、判断ノード422、およびリーフノード432を有る。また、判断ノード423はリーフノード435、434を有し、判断ノード422はリーフノード433、434を有する。判断ノード421の子ノードは422,423,432と3つのノードがあるが、このように子ノードの数はいくつでもよい。判断ノード422,423の子ノードは共通のノード434であるが、このように親ノードの数はいくつでもよい。このように、一つのルートノードを持つループ経路のない決定木であれば、決定木の構造は問わない。図4の場合、TD≫TT,Tα,Tβとすると、従来技法では入力データによりTD~3TD程度の時間がかかる。本実施形態ではTDであり、従来技法に比べて最大で3倍程度の高速化を図ることが可能になる。第3実施形態TD≫TT,Tα,Tβの場合は、一つのスレッドで一つの判断ノードに関する判断ステップS3を同時に実行することにより、高速に判断木の実行を行うことができる。従来技法ではアイドルコアとして使われなかったn本のスレッドを演算リソースとして積極的に使用することにより、従来技法に比べ高速に判断木の実行を行うことが可能になる。2nの判断ノードがある平衡二分決定木を実行する場合、従来技法に比べ約n倍の高速化が図れる。第1実施形態の処理の流れでは判断ステップS3の並列実行処理のあと、ORステップS4およびANDステップS5によって、各判断ノードの選択結果を集計している。この集計処理にはスレッド間の通信を伴うため、並列実行処理に比べて十分に決定木の実行の高速化が図れないこともある。判断ステップS3における各判断ノードでの判断が時間のかかる処理であれば、スレッド間通信による律速よりも並列処理による高速化が効果的である。逆に各判断ノードでの判断が単純であまり時間がかからない処理であれば、並列化による高速化よりもスレッド間通信による律速の影響が大きくなる。TDとTTに関して、TD≫TTであれば処理ステップS3を最大限に並列化することによる高速化が有効である。そうではない場合には多少並列化を犠牲にしてもTTを小さくすることが有効である。これには判断ステップS3において、複数の判断ノードにおける判断処理を一つのスレッドで行う。これにより、処理並列度を下げる代わりにスレッド間通信での律速の影響を減らすことができる。いくつの判断ノードでの判断処理を一つのスレッドで行うかはトレードオフであり、実行環境に大きく依存するため、多くの場合試行を繰り返して実験的に求めることになるが、詳細は本発明の範囲外であるため省略する。スレッド間通信を効果的に減らすにはORステップS4で行う同一階層内の判断ノードでの処理を一つのスレッドで行うか、ANDステップS5で行う階層間の結果を集計する処理を一つのスレッドで行うのがよい。しかしながら、ANDステップS5におけるスレッド間通信は高々判断ステップの階層数のノードしか関与しておらず、効果は限定的となる上に、並列度を実験的に変更する際の柔軟度が低い。そこで、同一階層内の判断ノードの処理を、一つのスレッドで行う。図1において、どのスレッドがどの判断ノードの処理を行うかを図5に例示する。図5の例1では、一つのスレッドには1~2個の判断ノードの判断処理が割り当てられている。例2では、一つのスレッドには3~4個の判断ノードの判断処理が割り当てられている。例2ではスレッド番号1のスレッドには階層を跨って判断ノードの判断処理が割り当てられているが、同一階層内処理をした上で、さらに異なる階層の判断処理を行うように担当が割り当てられている。例1の場合にスレッド間通信にかかる時間が先の実施形態の半分であるとすると、決定木の実行にかかる時間は約2TDTT/2である。TT=2.5TDとすると、実施形態では従来技法に比べ14程度の高速化であったのが、約23の高速化が達成できる。図5の例では使用スレッド数は8本であり、使用スレッド数が15本の場合に比べてアイドルコアの利用率は減るが、従来技法に比べるとアイドルコアを積極的に活用した高速化が可能になる。第4実施形態図1において、下位の階層に子ノードを有さないリーフノードの数は16個、図4においてリーフノードの数は5個である。本実施形態においてノードIDは1リーフノードあたり1ビット要する。そのためノードIDのサイズとして、図1の場合は16ビット、図4の場合は5ビットが最低でも必要となる。またORステップS4およびANDステップS5ではビット演算を用いる。そこでノードIDを情報処理装置20が一度に読み書きできる単位のサイズを持つ整数値とすることで、情報処理装置20は効率よく処理を行うことができる。現在、よく使われているIntelやAMDのマルチコアCPUや、NVIDIAやAMDのGPGPUでは、8、16、32ビットといったサイズのデータを一度に読み書きできる。そこで図1の決定木では16ビット長、図4の決定木では8ビット長の整数とする。なお情報処理装置20によっては、複数のサイズのデータを一度に読み書きできるが、その中でも最も効率のよいサイズが存在する場合がある。そのサイズが32ビットであるとすると、図1、図4のどちらの場合も32ビット長の整数とすることで、データの読み書きを効率的に行うことが可能になる。第5実施形態NVIDIAのGPGPUGeneralpurposecomputingongraphicsprocessingunits開発環境であるCUDAや、AMDがGPGPU開発言語として採用しているOpenCLOpenComputingLanguageではGPUの構造を反映したスレッドの階層構造を持つ。詳細は各々のドキュメント非特許文献1~4に記載があるのでここでは省略するが、実行主体であるスレッドをCUDAではスレッド、OpenCLではワークアイテムと呼ぶ。さらにこれらをいくつかまとめたものをブロックCUDA、ワークグループOpenCLと呼ぶ。以下ではOpenCLの用語を用いる。CUDAの場合は適宜読み替えることで、同様の説明となる。ワークグループとはワークアイテムをまとめたもので、ワークグループ内のワークアイテムは論理的に同時並列処理が行われる。また同一ワークグループ内のワークアイテムは、ローカルメモリCUDAでは共有メモリを介して高速なワークアイテム間通信ができる。異なるワークグループが同時に実行されることは保障されておらず、そのためワークグループを跨いだワークアイテム間通信は原則として行えない。そこで一つの決定木の実行を一つのワークグループ上で行うことで、ワークアイテム間通信を行いつつ、並列処理により実行結果を算出することができる。第6実施形態具体的なGPUGraphicsProcessingUnitとの対応も考慮するとさらに細かい規則がある。基本的には同一ワークグループ内のワークアイテムスレッドは同一プログラムの同一位置の命令を実行することで、プログラムを高速に実行できる。そこで処理を早く終わった判断ノードに対するワークアイテムが次の処理を先行して実行しないように、各ステップ間で全ての全ワークアイテムスレッドの待ち合わせ同期を行う。制御部26図2bは、一のワークアイテムスレッドの処理と他のワークアイテムスレッドの処理とを同期させるために各スレッドの実行タイミングを制御する。こうすることにより各ステップの実行タイミングを合わせることができ、少なくとも各ステップの先頭では全ワークアイテムが同一プログラムの同一位置の命令を実行することが可能となる。その他の実施形態また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェアプログラムを、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータまたはCPUやMPU等がプログラムを読み出して実行する処理である。"