(57)【特許請求の範囲】
【請求項１】
データの特徴量の入力を受け付けるデータ受付手段と、
木構造を持つ識別器の入力を受け付ける識別器受付手段と、
前記木構造の葉ノードに確率テーブル及び特徴量テーブルを保存するテーブル保存手段と、
前記確率テーブルを補正する確率テーブル補正手段と、
データのクラスを推定するクラス推定手段と、
を具えたクラス推定装置。
【請求項２】
前記補正手段が、前記特徴量テーブルの値を用いて前記確率テーブルを補正する、請求項１に記載のクラス推定装置。
【請求項３】
前記補正手段が、前記確率テーブルの値から算出された尤度と、入力されたデータの特徴量及び前記特徴量テーブルの値から算出された距離と、を用いて前記確率テーブルを補正する、請求項２に記載のクラス推定装置。
【請求項４】
前記補正手段が、入力されたデータの特徴量及び前記特徴量テーブルの値から算出された確率密度を用いて前記確率テーブルを補正する、請求項２に記載のクラス推定装置。
【請求項５】
更に、前記木構造の葉ノードに重要度を保存する重要度保存手段を具えた、請求項１〜４のいずれかに記載のクラス推定装置。
【請求項６】
データの特徴量の入力を受け付けるデータ受付ステップと、
木構造を持つ識別器の入力を受け付ける識別器受付ステップと、
前記木構造の葉ノードに確率テーブル及び特徴量テーブルを保存するテーブル保存ステップと、
前記確率テーブルを補正する確率テーブル補正ステップと、
データのクラスを推定するクラス推定ステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラス推定装置及びプログラムに関する。
【背景技術】
【０００２】
下記非特許文献１には、木構造の識別器を再作成するための手法として、葉ノードの確率テーブルのみを更新する手法である、ＵＬＳ（Update Leaf  Statics）、葉ノードを親ノードとして新規分岐条件を追加する手法である、ＩＧＴ（Incrementally Grow Tree）、一部の葉ノードの親の分岐条件を新規に作成した後、葉ノードを親ノードとして新規分岐条件を追加する手法である、ＲＴＳＴ（Re-Train SubTree）、及び、一部の葉ノードの親の分岐条件に条件を追加した後、葉ノードを親ノードとして新規分岐条件を追加する手法である、ＲＵＳＴ（Re-Use SubTree）が開示されている。
【０００３】
下記特許文献１には、対象画像から選択された部分領域に対する第１の特徴ベクトルを算出する算出手段と、学習用画像の部分領域に対して算出された第２の特徴ベクトルと学習用画像全体に対して付与された第２の識別情報とに基づいて決定木群を用いて対象画像の内容を表す第１の識別情報を当該対象画像に付与する手段であって、第２の特徴ベクトル群と第２の識別情報群を決定木群に流したとき、決定木群の各葉に到達した第２の識別情報の数の全体に対する割り合いから求まる尤度関数を掛け合わせたものと第１の特徴ベクトルの事前確率を掛け合わせたものとの比に、第２の識別情報の事前確率を掛けることにより、第１の識別情報を決定して付与する付与手段とを備えた、画像識別情報付与装置が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１２−０４２９９０号公報
【非特許文献】
【０００５】
【非特許文献１】M.Ristin, M.Guillaumin, J.Gall, and L.V.Gool, "Incremental Learning of NCM Forests for Large-Scale Image Classification", CVPR, 2014.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
木構造を持つ識別器を用いて属するクラスが未知であるデータの属するクラスを推定する、という処理において、クラスが追加される等によって対象クラスに変更が生じた場合には、変更されたクラスに対応するために、再度学習を行うことにより識別器を再作成する必要がある。単純に識別器を再作成しようとすると、木構造を新規に再構築することが考えられるが、その場合全ての分岐条件を新規に作成することになるため時間を要することとなる。
【０００７】
木構造を再作成せずに確率テーブルの更新のみを行うことにより、識別器の再作成に要する時間を低減させることができるＵＬＳに対して、推定精度の改善がなされているＩＧＴ、ＲＴＳＴ、及び、ＲＵＳＴが提案されているが、いずれもの手法も葉ノードを親ノードとして分岐条件を新規に作成するものであるため、木構造の分岐条件の作成のために時間を要するものであった。
【０００８】
本発明は、識別器の再作成を行う際、木構造の分岐条件を新規に作成することなく、ＵＬＳを用いた場合よりも、推定精度を向上させることを目的とする。
【課題を解決するための手段】
【０００９】
［クラス推定装置］
請求項１に係る本発明は、データの特徴量の入力を受け付けるデータ受付手段と、
木構造を持つ識別器の入力を受け付ける識別器受付手段と、
前記木構造の葉ノードに確率テーブルと特徴量テーブルを保存するテーブル保存手段と、
前記確率テーブルを補正する確率テーブル補正手段と、
データのクラスを推定するクラス推定手段と、
を具えたクラス推定装置である。
【００１０】
請求項２に係る本発明は、前記補正手段が、前記特徴量テーブルの値を用いて前記確率テーブルを補正する、請求項１に記載のクラス推定装置である。
【００１１】
請求項３に係る本発明は、前記補正手段が、前記確率テーブルの値から算出された尤度と、入力されたデータの特徴量及び前記特徴量テーブルの値から算出された距離と、を用いて前記確率テーブルを補正する、請求項２に記載のクラス推定装置である。
【００１２】
請求項４に係る本発明は、入力されたデータの特徴量及び前記特徴量テーブルの値から算出された確率密度を用いて前記確率テーブルを補正する、請求項２に記載のクラス推定装置である。
【００１３】
請求項５に係る本発明は、更に、前記木構造の葉ノードに重要度を保存する重要度保存手段を具えた、請求項１〜４のいずれかに記載のクラス推定装置である。
【００１４】
［プログラム］
請求項６に係る本発明は、データの特徴量の入力を受け付けるデータ受付ステップと、
木構造を持つ識別器の入力を受け付ける識別器受付ステップと、
前記木構造の葉ノードに確率テーブルと特徴量テーブルを保存するテーブル保存ステップと、
前記確率テーブルを補正する確率テーブル補正ステップと、
データのクラスを推定するクラス推定ステップと、
をコンピュータに実行させるためのプログラムである。
【発明の効果】
【００１５】
請求項１に係る本発明よれば、識別器の再作成を行う際、木構造の分岐条件を新規に作成することなく、ＵＬＳを用いた場合よりも推定精度を向上させることができる。
【００１６】
請求項２に係る本発明よれば、識別器の再作成を行う際、木構造の分岐条件を新規に作成することなく、ＵＬＳを用いた場合よりも推定精度を向上させることができる。
【００１７】
請求項３に係る本発明よれば、識別器の再作成を行う際、木構造の分岐条件を新規に作成することなく、ＵＬＳを用いた場合よりも推定精度を向上させることができる。
【００１８】
請求項４に係る本発明よれば、識別器の再作成を行う際、木構造の分岐条件を新規に作成することなく、ＵＬＳを用いた場合よりも推定精度を向上させることができる。
【００１９】
請求項５に係る本発明よれば、確率テーブルの補正の際に、より重要度の高い葉ノードの影響を高くすることができる。
【００２０】
請求項６に係る本発明よれば、識別器の再作成を行う際、木構造の分岐条件を新規に作成することなく、ＵＬＳを用いた場合よりも推定精度を向上させることができる。
【図面の簡単な説明】
【００２１】
【図１】本実施形態に係るクラス推定装置における処理の基本的な構成を示す概念図である。
【図２】本実施形態に係るクラス推定装置における処理の一例を示すフローチャートである。
【図３】事前学習データとしての木構造識別器を示す概念図である。
【図４】従来手法を用いて再作成された木構造識別器を示す概念図である。
【図５】本実施形態に係るクラス推定装置によって作成された木構造識別器を示す概念図である。。
【発明を実施するための形態】
【００２２】
以下、本発明を実施するための形態を詳細に説明する。但し、以下に示す実施形態は、本発明の技術思想を具体化するためのクラス推定装置の一例を示すものであって、本発明をこの実施形態に限定することを意図するものではなく、本発明は特許請求の範囲に示した技術思想を逸脱することなく種々の変更を行ったものにも均しく適用し得るものである。
【００２３】
本実施形態に係るクラス推定装置は、データの特徴量が入力されるデータ受付部と、木構造を持つ識別器が入力される識別器受付部と、木構造の葉ノードに確率テーブル及び特徴量テーブルを保存するテーブル保存部と、確率テーブルを補正する確率テーブル補正部と、属するクラスが未知のデータのクラスを推定した結果を出力するクラス推定部を具えている。
【００２４】
本実施形態の処理の流れについて図１及び図２を用いて説明する。図１は、本実施形態に係るクラス推定装置における基本的な処理の流れを示し、図２は、学習データとして画像データを用いた場合のより詳細な処理の一例を示す。
［事前学習データ保存ステップ］
事前学習データ保存ステップＳ１では、予め作成された木構造識別器が識別器受付部に、その木構造識別器を作成した際の学習データ及び各データの属するクラスがデータ受付部に、それぞれ入力され、事前学習データとして保存される。
【００２５】
学習データは、データの種類を問わないが、Ｍ次元のベクトルデータとする。例えば、画像データであれば、各画像から抽出した、色やエッジ情報等の特徴量を学習データとし、その画像に予め付与されているラベルをその学習データが属するクラスとする。その際、1枚の画像から複数個の特徴量を抽出しても良い。この際、DeepLearning手法を用いて予め大量の画像から学習を行い作成した特徴抽出器を用いて特徴量を抽出しても良い。
【００２６】
また、音声データであれば、各音声から抽出した、音素の周波数成分情報等の特徴量を学習データとし、各音声に予め付与されているラベル(話した人、単語等)をその学習データが属するクラスとする。
【００２７】
また、テキストデータであれば、各テキストから抽出した、単語をベクトル化した特徴量を学習データとし、各テキストに予め付与されているラベル(文書の種類、極性等)をその学習データが属するクラスとする。
【００２８】
事前学習データ内に保存される木構造識別器としては、根ノード、内部ノード、葉ノードから成り、根ノードと内部ノードは、分岐条件、葉ノードは確率テーブル(葉ノードに属するクラスとデータ数のペア)を持つ識別器とし、１つの決定木からなるもの、RandomForest、AdaBoost、GradientBoostingDecisionTrees等がある。また、分岐条件は、RandomForestの場合、学習時にエントロピーやジニ係数を基に、内部ノード毎に選択するベクトルの次元と閾値が決定されており、閾値以下の場合は左ノードに、大きい場合は右ノードになるというものとなっている。なお、葉ノードには更に後述する特徴量テーブルを持たせていても良い。
【００２９】
［再作成用データ保存ステップ］
再作成用データ保存ステップＳ２では、事前学習データ保存ステップにおいてに保存された事前学習データと、追加・変更を行う学習データと各データの属するクラスがデータ受付部に入力され、再作成用データが保存される。
【００３０】
再作成用データとしては、全学習データ数、各クラスの学習データ数、再作成用学習データとそのクラス、更新用識別器等がある。再作成用学習データとしては、全学習データを対象としても良いし、クラスやデータの追加を行う場合、かつ事前学習データ内の識別器が確率テーブルと特徴量テーブルを持つ識別器である場合は、追加する学習データのみを対象にしても良い。
【００３１】
更新用識別器は、事前学習データ内の予め作成された木構造識別器に対し、全データを更新時に使用する場合は、確率テーブルをリセットしたものとする。また、クラスやデータの追加を行う場合、かつ事前学習データ内の識別器が確率テーブルと特徴量テーブルを持つ識別器である場合は、確率テーブルや特徴量テーブルを保持したままでも良い。
識別器がRandomForestの場合等は、再作成用学習データは、ランダムサンプリングを行っても良く、予め作成された木構造識別器が複数個ある場合は、同数個までの再作成に使用する学習データと更新用識別器を作成することができる。
【００３２】
［識別器再作成ステップ］
識別器再作成ステップＳ３では、再作成用データが入力された後、再作成用学習データと各データの属するクラスを用いて更新用識別器の葉ノードが更新され、テーブル保存部によって葉ノードに確率テーブルと特徴量テーブルが保存されることによって、葉ノードに確率テーブルと特徴量テーブルを持つ更新後の木構造識別器が再作成される。
【００３３】
特徴量テーブルは、葉ノードに属するクラスと特徴量情報のペアとする。例えば、特徴量情報は、葉ノードに属する学習データのクラス毎の平均値、分散値、中央値、標準偏差値、最小値、最大値等とする。また、葉ノードの親の分岐条件として使用する次元のみを使用する、根ノードから葉ノードに至るまで通る内部ノードの分岐条件で使用する次元のみを使用する、ランダムに選んだ次元のみを使用する等、学習データの一部の次元だけを使用し、クラス毎の平均値、分散値、中央値、標準偏差値、最小値、最大値等を求め、特徴量情報としても良い。なお、確率テーブルと特徴量テーブルは同数であるため、１つのテーブルに纏めても良い。表１は通常の確率テーブルの例であり、表２にその確率テーブルに対して特徴量テーブルが一つに纏められたものの例を示した。
【００３４】
【表１】
0006687894.tif 000002
【００３５】
【表２】
0006687894.tif 000003
【００３６】
［所属葉ノードデータ取得ステップ］
所属葉ノードデータ取得ステップＳ４では、クラス推定を行う対象である属するクラスが未知のデータと、更新後の木構造識別器が入力され、属するクラスが未知のデータの所属する葉ノードが探索され、その葉ノードへ至るまでに通る内部ノードとその分岐条件、及び、その葉ノードの確率テーブルと特徴量テーブルが、葉ノードデータとして取得される。なお、本実施形態に係るスコア推定装置においては、更に葉ノードの重要度を保存するための、重要度保存部を具えていても良く、その場合、必要に応じて、葉ノードデータに重要度を含めることができる。
【００３７】
重要度は、推定スコアの精度をより高めるために使用することが可能で、葉ノードへ至るまでに通る内部ノードの各分岐条件を設定した際に用いる、エントロピーやジニ係数の減少値の平均値、中央値等とし、葉ノードから任意の数遡った内部ノードまでの減少値を用いることができる。
【００３８】
［確率テーブル補正ステップ］
確率テーブル補正ステップＳ５では、確率テーブル補正部において、属するクラスが未知のデータと、所属葉ノードデータと、再作成用データが入力され、属するクラスが未知のデータと葉ノードへ至るまでの内部ノードと分岐条件と特徴量テーブルを用いて、確率テーブルが補正される。
【００３９】
例えば、識別器をRandomForestとし、葉ノードの親の分岐条件として使用する次元の平均値と分散値を特徴量情報とする場合、再作成用学習データの数をN、クラスを(C1，…，Cc)、各クラスの再作成用学習データの数を(N1，…，Nc)、クラスが未知のデータをX(X1，…，XM)、親の分岐条件で使用する次元をD、葉ノード内にあるクラスを(C1，C3，Cc)、その数を(P1，P3，Pc)、その平均値を(M1，M3，Mc)、その分散値を(V1，V3，Vc)、確率テーブルと特徴量テーブルをまとめたテーブルを｛(C1，P1，M1，V1)，(C3，P3，M3，V3) ，(Cc ，Pc，Mc，Vc)｝とした際は、下記のような補正ができる。なお、補正パターン１による補正がされない場合に、補正パターン２を適用するというように、補正パターン１と補正パターン２は組み合わせて用いても良い。
【００４０】
（補正パターン１）：尤度関数P(X|C)が最も大きいクラスと、クラスが未知のデータとの距離dcが最短となる平均値を持つクラスが同じ場合に、当該クラス以外のクラスのデータ数を0とする。
【数１】
0006687894.tif 000004
【００４１】
（補正パターン２）：各クラスの確率密度fnを求め、それを基にリーフ内の各クラスのデータ数を補正することで、確率テーブルを補正する。
【数２】
0006687894.tif 000005
確率テーブルを補正する際には、例えば、葉ノードの重要度の値に任意の閾値を設けておき、補正する確率テーブルを選別する、あるいは、重要度の値を確率テーブルに掛けあわせる、などのように重要度を利用することで、推定スコアの精度をより向上させることができる。
【００４２】
［推定スコア算出ステップ］
推定スコア算出ステップＳ６では、クラスが未知のデータと補正した確率テーブルと再作成用学習データが入力され、各クラスの事後確率を基に各クラスの推定スコアを算出する。
【００４３】
例えば、全学習データの総数をA、クラスCの学習データ数をAc、再作成用学習データの総数をN、クラスCの再作成用学習データの数をNc、確率テーブル内のデータ総数をP、確率テーブル内のクラスCに対応する値をPcとすると、クラスが未知のデータXに対する、クラスCの事後確率は、尤度関数を用いて、以下の式で定義することができる。
【数３】
0006687894.tif 000006
【００４４】
推定スコアSCは事後確率P(C|X)をそのまま用いても良いし、以下の式で定義しても良い。
【数４】
0006687894.tif 000007
【００４５】
識別器がRandomForestの場合等で、T個の木構造識別器から成る場合、以下の式のように各木構造識別器の確率テーブルの平均から尤度関数を求める。
【数５】
0006687894.tif 000008
【００４６】
データが画像から抽出された特徴量等で、1つの対象からM個のデータが抽出される場合は、クラスが未知のデータは(X1，…，XM)となり、クラスが未知のデータXiに対する、クラスCの事後確率として、以下の式で定義することができる。
【数６】
0006687894.tif 000009
【００４７】
推定スコアSCとしては事後確率P(C|X1，…，XM)をそのまま用いても良いし、以下の式で定義しても良い。
【数７】
0006687894.tif 000010
【００４８】
［推定結果出力ステップ］
推定結果出力ステップＳ７では、クラス推定部において、属するクラスが未知のデータと各クラスの推定スコアが入力され、クラスが未知のデータのクラスが推定結果として出力される。クラス推定については、例えば、推定スコアが最も高いクラスを推定結果としても良いし、推定スコアが予め設定した閾値以上のクラスを推定結果としても良く、全てが閾値以下ならば、該当クラスなしという結果を出力しても良い。
【００４９】
次に、確率テーブルの補正について、２０個のクラス１のデータ、１０個のクラス２のデータ、及び、図３に示す木構造識別器を事前学習データとし、これに１０個のクラス３のデータを追加する場合の具体例を説明する。
【００５０】
まず、従来手法であるＩＧＴを用いた場合、クラス３追加により再作成された後の木構造識別器は例えば図４のようになる。ここでは、事前学習データの木構造識別器における葉ノード１及び葉ノード４において新規に分岐条件が追加され内部ノードとなり、計６個の葉ノードを持つ識別器として再作成されている。
【００５１】
次に、本実施形態による再作成後の木構造識別器を図５に示す。なお、図５は、確率テーブルと特徴量テーブルを纏めた例で示している。本実施形態では、各葉ノードには特徴量テーブルが格納されているが、分岐条件が新規に追加されることはないので、木構造識別器の構造については図３すなわち事前学習データの木構造識別器と同一となっている。
【００５２】
ここで、属するクラスが未知のデータとして、５次元ベクトルＸ（０．５，０．７，０．４，０．５，０．３）というデータに関して、クラス推定を行う場合は、以下のようになる。
【００５３】
（従来手法のＩＧＴを用いた場合）
木構造識別器は図４に示されるものであり、根ノードからスタートし、根ノードの分岐では、特徴次元の２次元目が、０．７（すなわち、閾値である０．６よりも大きい）であるため、右の子ノードへ辿ることになる。次の分岐では、特徴次元の５次元目が０．３（＞０．２）であるため、右の子ノード、というルートを通り、特徴次元の１次元目が０．５（＞０．４）であるため、最終的に、｛（クラス３，６）｝という確率テーブルを持つ葉ノード６に属する、と判断される。
【００５４】
（本実施形態に係るクラス推定装置を用いた場合）
木構造識別器は図５に示されるものであり、根ノードからスタートし、特徴次元の２次元目が０．７（＞０．６）であるため、右の子ノードを辿り、特徴次元の５次元目が０．３（＞０．２）であるため、まず、葉ノード４に属すると判断される。
【００５５】
この葉ノード４は、｛（クラス１，９），（クラス３，６）｝という確率テーブルを持っており、次いで確率テーブルの補正を行う。
【００５６】
ここで、尤度関数、Ｐ（Ｘ｜クラス１）＝９／２０、Ｐ（Ｘ｜クラス３）＝６／１０  であるため、尤度関数が最大となるクラスは、「クラス３」となる。
【００５７】
また、親ノードで分岐条件に選んだ特徴次元が５次元目であるため、データＸの５次元目と葉ノードの特徴量テーブルの平均値の距離を求めると、ｄクラス1＝（０．３−０．８）2の平方根＝０．５、ｄクラス3＝（０．３−０．４）2の平方根＝０．１である。従って、距離が最短となるクラスは「クラス３」となる。
【００５８】
補正パターン１の適用により、クラス１のデータ数が０に補正され、補正後の葉ノード４の確率テーブルは、｛（クラス１，０），（クラス３，６）｝となるため、データ数が０であるクラス１が除去されて、葉ノード４の確率テーブルは最終的に｛（クラス３，６）｝に補正されることになる。以上の様に、今回のデータＸでは、本実施形態による手法により、木構造の分岐条件の追加なしに、従来手法であるＩＧＴと同じ確率テーブルを用いて推定を行うことができることになる。
【００５９】
［実施例］
［識別器の再作成に要する時間の比較］
識別器の再作成に要する時間及び推定精度について、従来手法との比較による評価を行った。画像認識のベンチマークで多く用いられるＶＯＣ２００７を用いて、１０個のクラスのデータ（学習用画像：５０１１枚）と、そのデータから作成されたRandomForestsに対し、１０クラスの追加（評価用画像：４９５２枚）による、識別器再作成に要する時間を計測すると共に、推定精度の評価のため、得られた識別器を用いた場合のＭＡＰ（Mean Average Precision）値（各再現率レベル（０．１−１．０を０．１刻み）での適合率の平均の全クラスでの平均の値）を算出した。
【００６０】
本実施例として、１０クラスで作成されたRandomForestsをそのまま用い、全学習データで確率テーブルと特徴量テーブルを更新することで、識別器を再作成するものと、比較例１として、RandomForestsを２０ラベルで新規に再作成するものとで比較した。ＭＡＰ値については、本実施形態に係るスコア推定装置において、確率テーブルの補正を行わない場合（これは、従来手法であるＵＬＳに相当する）を比較例２とした。ＭＡＰ値の比較を表３に示し、識別器の再作成時間について表４に示す。
【００６１】
【表３】
0006687894.tif 000011
【００６２】
【表４】
0006687894.tif 000012
【００６３】
本実施形態のクラス推定装置では、表３からわかるように、ＵＬＳよりも推定精度を向上させることができる。
【００６４】
また、表４に示されるように、識別器の再作成に必要な時間を新規に識別器を作成する場合と比較すると、大幅に低減されていることがわかる。これは、本実施形態のクラス推定装置では、新規の分岐条件を作成していないため、識別器の再作成に必要な時間が従来手法であるＵＬＳとほぼ同じで済むことによる。
【符号の説明】
【００６５】
Ｓ１…事前学習データ保存ステップ
Ｓ２…画再作成用データ保存ステップ
Ｓ３…識別器再作成ステップ
Ｓ４…所属葉ノードデータ取得ステップ
Ｓ５…確率テーブル補正ステップ
Ｓ６…推定スコア算出ステップ
Ｓ７…推定結果出力ステップ
【図１】
0006687894.tif 000013
【図２】
0006687894.tif 000014
【図３】
0006687894.tif 000015
【図４】
0006687894.tif 000016
【図５】
0006687894.tif 000017