TOP > 国内特許検索 > 分類モデル生成装置、分類装置、分類モデル生成方法、分類方法、分類モデル生成プログラム、分類プログラムおよび記録媒体 > 明細書

明細書 :分類モデル生成装置、分類装置、分類モデル生成方法、分類方法、分類モデル生成プログラム、分類プログラムおよび記録媒体

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5164209号 (P5164209)
公開番号 特開2010-003106 (P2010-003106A)
登録日 平成24年12月28日(2012.12.28)
発行日 平成25年3月21日(2013.3.21)
公開日 平成22年1月7日(2010.1.7)
発明の名称または考案の名称 分類モデル生成装置、分類装置、分類モデル生成方法、分類方法、分類モデル生成プログラム、分類プログラムおよび記録媒体
国際特許分類 G06F  17/30        (2006.01)
G06N   5/04        (2006.01)
FI G06F 17/30 210D
G06N 5/04 580A
G06N 5/04 550J
請求項の数または発明の数 11
全頁数 22
出願番号 特願2008-161237 (P2008-161237)
出願日 平成20年6月20日(2008.6.20)
審査請求日 平成23年5月27日(2011.5.27)
特許権者または実用新案権者 【識別番号】000004226
【氏名又は名称】日本電信電話株式会社
【識別番号】504132272
【氏名又は名称】国立大学法人京都大学
発明者または考案者 【氏名】岩田 具治
【氏名】田中 利幸
個別代理人の代理人 【識別番号】100064414、【弁理士】、【氏名又は名称】磯野 道造
【識別番号】100127720、【弁理士】、【氏名又は名称】大石 恵
【識別番号】100162374、【弁理士】、【氏名又は名称】中村 新二
審査官 【審査官】吉田 誠
参考文献・文献 国際公開第2004/084096(WO,A1)
特開2006-302269(JP,A)
特開2006-4103(JP,A)
特開2006-338263(JP,A)
調査した分野 G06F 17/30
G06N 5/04
特許請求の範囲 【請求項1】
分類対象データを分類する分類体系であるターゲット分類体系においてすでに分類されている1つ以上の既分類データと、前記ターゲット分類体系とは異なる分類体系である補助分類体系においてすでに分類されている1つ以上の既分類データと、を用いて学習を行うことで、前記分類対象データを前記ターゲット分類体系における複数のクラスのいずれかに分類するための分類モデルを生成する分類モデル生成装置であって、
情報を記憶する記憶手段と、
前記した2種類の既分類データにおける個別の各既分類データを前記ターゲット分類体系のいずれかのクラスに分類したと予測したときの前記分類モデルの誤差関数と、当該予測をしたときの前記した2種類の既分類データにおける個別の各既分類データの前記分類モデルへの影響度を示す各重みと、を用いて、前記した2種類の既分類データにおける個別の既分類データごとの前記誤差関数の値と前記重みとの積の総和である期待誤差を最小化させるように、前記重みを推定して、当該重みを前記記憶手段に格納する重み推定部と、
前記記憶手段に格納された重みと、前記した2種類の既分類データと、を用いて、前記分類モデルを生成するモデル構築部と、
を備えることを特徴とする分類モデル生成装置。
【請求項2】
前記重み推定部は、
前記ターゲット分類体系と前記補助分類体系とを統合した場合の確率分布モデルを、前記ターゲット分類体系の確率分布モデルに近似させるための、前記ターゲット分類体系と前記補助分類体系とのクラスごとの前記分類モデルへの影響度の比率を示す混合比を用いて、前記した2種類の既分類データに関する事後確率を推定して、当該事後確率を前記記憶手段に格納する事後確率推定部と、
前記記憶手段に格納された事後確率を用いて、前記ターゲット分類体系の既分類データに対する尤度を最大化するように、前記混合比を推定し、前記尤度が最大化されたときの前記混合比から前記重みを推定して、当該重みを前記記憶手段に格納する混合比推定部と、
を備えることを特徴とする請求項1に記載の分類モデル生成装置。
【請求項3】
前記モデル構築部は、
前記記憶手段に格納された重みと、前記した2種類の既分類データと、を用いて、前記分類モデルにおいて前記分類対象データを前記ターゲット分類体系に分類するためのモデルパラメータを推定して、当該モデルパラメータを前記記憶手段に格納するモデルパラメータ推定部
を備えることを特徴とする請求項1に記載の分類モデル生成装置。
【請求項4】
請求項3に記載の分類モデル生成装置の前記記憶手段に格納されたモデルパラメータを用いて、前記分類対象データを前記ターゲット分類体系における複数のクラスのいずれかに分類する分類部
を備えることを特徴とする分類装置。
【請求項5】
分類対象データを分類する分類体系であるターゲット分類体系においてすでに分類されている1つ以上の既分類データと、前記ターゲット分類体系とは異なる分類体系である補助分類体系においてすでに分類されている1つ以上の既分類データと、を用いて学習を行うことで、前記分類対象データを前記ターゲット分類体系における複数のクラスのいずれかに分類するための分類モデルを生成する分類モデル生成装置による分類モデル生成方法であって、
前記分類モデル生成装置は、情報を記憶する記憶手段と、重み推定部と、モデル構築部と、を備えており、
前記重み推定部は、前記した2種類の既分類データにおける個別の各既分類データを前記ターゲット分類体系のいずれかのクラスに分類したと予測したときの前記分類モデルの誤差関数と、当該予測をしたときの前記した2種類の既分類データにおける個別の各既分類データの前記分類モデルへの影響度を示す各重みと、を用いて、前記した2種類の既分類データにおける個別の既分類データごとの前記誤差関数の値と前記重みとの積の総和である期待誤差を最小化させるように、前記重みを推定して、当該重みを前記記憶手段に格納する重み推定ステップを実行し、
前記モデル構築部は、前記記憶手段に格納された重みと、前記した2種類の既分類データと、を用いて、前記分類モデルを生成するモデル構築ステップを実行する
ことを特徴とする分類モデル生成方法。
【請求項6】
前記重み推定部は、事後確率推定部と、混合比推定部と、を備えており、
前記重み推定ステップにおいて、
前記事後確率推定部は、前記ターゲット分類体系と前記補助分類体系とを統合した場合の確率分布モデルを、前記ターゲット分類体系の確率分布モデルに近似させるための、前記ターゲット分類体系と前記補助分類体系とのクラスごとの前記分類モデルへの影響度の比率を示す混合比を用いて、前記した2種類の既分類データに関する事後確率を推定して、当該事後確率を前記記憶手段に格納し、
前記混合比推定部は、前記記憶手段に格納された事後確率を用いて、前記ターゲット分類体系の既分類データに対する尤度を最大化するように、前記混合比を推定し、前記尤度が最大化されたときの前記混合比から前記重みを推定して、当該重みを前記記憶手段に格納する
ことを特徴とする請求項5に記載の分類モデル生成方法。
【請求項7】
前記モデル構築部は、モデルパラメータ推定部を備えており、
前記モデル構築ステップにおいて、
前記モデルパラメータ推定部は、前記記憶手段に格納された重みと、前記した2種類の既分類データと、を用いて、前記分類モデルにおいて前記分類対象データを前記ターゲット分類体系に分類するためのモデルパラメータを推定して、当該モデルパラメータを前記記憶手段に格納する
ことを特徴とする請求項5に記載の分類モデル生成方法。
【請求項8】
請求項7に記載の分類モデル生成方法によって前記記憶手段に格納されたモデルパラメータを用いて、
前記分類対象データを分類する分類装置における分類部は、
前記分類対象データを前記ターゲット分類体系における複数のクラスのいずれかに分類するステップを実行する
ことを特徴とする分類方法。
【請求項9】
コンピュータを請求項1から請求項3のいずれか一項に記載の分類モデル生成装置の各部として機能させるための分類モデル生成プログラム。
【請求項10】
コンピュータを請求項4に記載の分類装置の分類部として機能させるための分類プログラム。
【請求項11】
請求項9に記載の分類モデル生成プログラム、または、請求項10に記載の分類プログラムが記録されたことを特徴とするコンピュータに読み取り可能な記録媒体。
発明の詳細な説明 【技術分野】
【0001】
本発明は、分類対象データを分類する分類体系(以下、「ターゲット分類体系」という。)のデータだけでなく、別の分類体系(以下、「補助分類体系」という。)のデータも用いて、分類モデルを学習し、また、その学習した分類モデルを用いて分類対象データをターゲット分類体系において分類する技術に関する。
【背景技術】
【0002】
学習データ(学習用のデータ)の数が少ない場合、一般に、分類モデルの性能は低くなる。そこで、補助分類体系におけるクラスのラベル(以下、「クラスラベル」または単に「ラベル」という。)が付与されたデータを用いることにより、分類モデルの性能を向上させることができれば好ましい。その場合、例えば、あるWebページを、あるターゲット分類体系のクラス(以下、「ターゲットクラス」ともいう。)に分類したいとする。そして、ディレクトリ型検索エンジンやソーシャルブックマークサイトにおける多数のユーザによって、ターゲット分類体系とは異なる補助分類体系に、多くのWebページがすでに分類されており、そのような情報を活用できれば望ましい。
【0003】
また、例えば、オンラインショッピングなどの商品について購買順序を考慮した予測(分類)に関する技術が知られている(非特許文献1参照)。

【非特許文献1】岩田具治、山田武士、上田修功、“購買順序を考慮した協調フィルタリング”、人工知能と知識処理研究会、AI2007-3,13-18,2007
【発明の開示】
【発明が解決しようとする課題】
【0004】
しかし、補助分類体系とターゲット分類体系とでは、一般にクラスラベルが異なり、また、同じラベルがあったとしても意味が異なる可能性もある。そのため、従来の教師あり学習の技術(非特許文献1など)を用いて、補助分類体系のクラス(以下、「補助クラス」ともいう。)のデータを利用することはできないという問題がある。
【0005】
そこで、本発明は、前記問題に鑑みてなされたものであり、補助分類体系のデータを有効に利用することで、ターゲット分類体系に関する高精度な分類モデルを生成することを課題とする。また、その生成した分類モデルを用いて、分類対象データをターゲット分類体系において高精度に分類することを、他の課題とする。
【課題を解決するための手段】
【0006】
前記課題を解決するために、本発明は、分類対象データを分類する分類体系であるターゲット分類体系においてすでに分類されている1つ以上の既分類データと、前記ターゲット分類体系とは異なる分類体系である補助分類体系においてすでに分類されている1つ以上の既分類データと、を用いて学習を行うことで、前記分類対象データを前記ターゲット分類体系における複数のクラスのいずれかに分類するための分類モデルを生成する分類モデル生成装置であって、情報を記憶する記憶手段と、前記した2種類の既分類データにおける個別の各既分類データを前記ターゲット分類体系のいずれかのクラスに分類したと予測したときの前記分類モデルの誤差関数と、当該予測をしたときの前記した2種類の既分類データにおける個別の各既分類データの前記分類モデルへの影響度を示す各重みと、を用いて、前記した2種類の既分類データにおける個別の既分類データごとの前記誤差関数の値と前記重みとの積の総和である期待誤差を最小化させるように、前記重みを推定して、当該重みを前記記憶手段に格納する重み推定部と、前記記憶手段に格納された重みと、前記した2種類の既分類データと、を用いて、前記分類モデルを生成するモデル構築部と、を備えることを特徴とする。
【0007】
かかる発明によれば、ターゲット分類体系における既分類データだけでなく、補助分類体系における既分類データも用い、誤差関数と重みとの積の総和である期待誤差を最小化させるように重みを推定し、その推定された重みと2種類の既分類データとを用いて分類モデルを生成することで、補助分類体系のデータも有効に利用し、ターゲット分類体系に関する高精度な分類モデルを生成することができる。
【0008】
また、本発明は、前記重み推定部が、前記ターゲット分類体系と前記補助分類体系とを統合した場合の確率分布モデルを、前記ターゲット分類体系の確率分布モデルに近似させるための、前記ターゲット分類体系と前記補助分類体系とのクラスごとの前記分類モデルへの影響度の比率を示す混合比を用いて、前記した2種類の既分類データに関する事後確率を推定して、当該事後確率を前記記憶手段に格納する事後確率推定部と、前記記憶手段に格納された事後確率を用いて、前記ターゲット分類体系の既分類データに対する尤度を最大化するように、前記混合比を推定し、前記尤度が最大化されたときの前記混合比から前記重みを推定して、当該重みを前記記憶手段に格納する混合比推定部と、を備えることを特徴とする。
【0009】
かかる発明によれば、重み推定部が、事後確率推定部と、混合比推定部とを備えているので、例えば、事後確率推定部が、EM(Expectation-Maximization)アルゴリズムにおけるE(Expectation)ステップを行い、かつ、混合比推定部がM(Maximization)ステップを行うことで、混合比についての大域的最適解を求め、求めた混合比から重みを決定(推定)することができる。
【0010】
また、本発明は、前記モデル構築部が、前記記憶手段に格納された重みと、前記した2種類の既分類データと、を用いて、前記分類モデルにおいて前記分類対象データを前記ターゲット分類体系に分類するためのモデルパラメータを推定して、当該モデルパラメータを前記記憶手段に格納するモデルパラメータ推定部を備えることを特徴とする。
【0011】
かかる発明によれば、モデルパラメータ推定部が、例えば、後記する式(10)を用いてモデルパラメータを推定することができる。
【0012】
また、本発明は、分類装置が、分類モデル生成装置の前記記憶手段に格納されたモデルパラメータを用いて、前記分類対象データを前記ターゲット分類体系における複数のクラスのいずれかに分類する分類部を備えることを特徴とする。
【0013】
かかる発明によれば、分類部が、推定したモデルパラメータを用いて分類対象データをターゲット分類体系における複数のクラスのいずれかに分類する、つまり、高精度な分類モデルを用いることで高精度な分類を実現することができる。
【0014】
また、本発明は、コンピュータを、分類モデル生成装置または分類装置の各部として機能させるためのプログラムである。これにより、このプログラムをインストールされたコンピュータは、このプログラムに基づいた各機能を実現することができる。
【0015】
また、本発明は、前記プログラムが記録されたことを特徴とするコンピュータに読み取り可能な記録媒体である。これにより、この記録媒体を装着されたコンピュータは、この記録媒体に記録されたプログラムに基づいた各機能を実現することができる。
【発明の効果】
【0016】
本発明によれば、補助分類体系のデータも有効に利用することで、ターゲット分類体系に関する高精度な分類モデルを生成することができる。また、その生成した分類モデルを用いて、分類対象データをターゲット分類体系において高精度に分類することができる。
【発明を実施するための最良の形態】
【0017】
以下、本発明を実施するための最良の形態(以下、「実施形態」という。)について、詳細に説明する。図1は、本実施形態に係る分類装置の構成を示すブロック図である。図1に示すように、分類装置1は、演算手段2と、入力手段3と、記憶手段4と、出力手段5とを備えている。各手段2~5はバスライン11に接続されている。なお、分類装置1は、分類モデル(以下、単に「モデル」ともいう。)を生成する分類モデル生成装置としての機能と、その生成した分類モデルによって分類対象データを分類する分類装置としての機能とを兼ね備えるものであるが、いずれか一方の機能のみを有するものとして実現されてもよい。
【0018】
演算手段2は、例えば、CPU(Central Processing Unit)およびRAM(Random Access Memory)から構成される主制御装置である。この演算手段2は、図1に示すように、重み推定部21と、モデル構築部22と、分類部23と、メモリ24とを含んで構成される。なお、各部21~23の説明は後記するが、従来手法と比較した場合の本実施形態における主な特徴は重み推定部21であるので、重み推定部21に関して特に詳細に説明する。また、モデル構築部22と分類部23に関しては、従来手法を大きく変更せずに適用できるので、詳細な説明を省略する。
【0019】
入力手段3は、例えば、キーボード、マウス、ディスクドライブ装置等から構成される。この入力手段3は、各種データを入力し、記憶手段4に格納する(詳細は後記)。
【0020】
記憶手段4は、例えば、一般的なハードディスク装置等から構成され、演算手段2で用いられる各種プログラムや各種データ等を記憶する。この記憶手段4は、プログラムとして、重み推定プログラム41と、モデル構築プログラム42と、分類プログラム43とをプログラム格納部40aに記憶する。そして、演算手段2は、これらのプログラム41~43を記憶手段4から読み込んでメモリ24に展開して実行することで、前記した重み推定部21、モデル構築部22、分類部23の各機能を実現する。
【0021】
また、記憶手段4は、入力データ44と、重み45と、モデルパラメータ46と、テストデータ47とをデータ格納部40bに記憶する。ここで、入力データ44は、入力手段3から入力されるデータであり、学習用サンプルである。重み45は、演算手段2の重み推定部21の演算処理によって推定された重みに関するデータである(詳細は後記)。モデルパラメータ46は、演算手段2のモデル構築部22の演算処理によって算出されたデータである(詳細は後記)。テストデータ47は、テスト用サンプルである(詳細は後記)。なお、入力データ44、重み45、モデルパラメータ46およびテストデータ47に関しては、以下、符号を適宜省略する。
【0022】
出力手段5は、例えば、グラフィックボード(出力インタフェース)およびそれに接続されたモニタである。このモニタは、例えば、液晶ディスプレイ等から構成され、演算処理結果(分類対象データの分類結果等)を表示する。
【0023】
本実施形態では、ターゲット分類体系のデータ(既分類データ。以下、「ターゲットデータ」ともいう。)だけでなく、補助分類体系のデータ(既分類データ以下、「補助データ」ともいう。)も用いて、分類器(分類モデル)を学習する。ターゲットクラス集合をZ、補助クラス集合をA、全クラス集合をY={Z,A}とする。
【0024】
学習データとして、ターゲットデータであるD={x,yNzn=1(本明細書において、「Nzn=1」は「n」に「1」から「N」までを代入することを意味する。他の文字についても同様)と、
補助データであるD={x,yn=Nz+1とが与えられたとき、クラスが未知のサンプルx(分類対象データ。後記するテストデータ47)のクラスy∈Zを予測する分類モデルを学習する。
【0025】
ここで、Webページデータの場合、サンプルは例えば単語出現頻度ベクトルx=(xn1,・・・,xnw)で表される(xnwは第nサンプルに単語wが出現した回数を表す)。
【0026】
また、y∈Z(if 1≦n≦N)、y∈A(if N+1≦n≦N)であり、Webページの場合、yは第nサンプルが分類されているカテゴリを表す。なお、yは離散値である。また、xを離散変数として扱うが、連続変数の場合へも容易に拡張可能である。
【0027】
本実施形態では、ターゲットデータに補助データ(補助分類体系のデータ)も含めた全データに関する重み付き経験誤差E(M)(式(1))を最小化することにより、モデルMを学習する。
【数1】
JP0005164209B2_000002t.gif

【0028】
ここで、w(z|y)はクラスy∈Yのサンプルがターゲットクラスz∈Zのモデル学習にどのくらい参考になるかをあらわす重みを表す。なお、式(1)において、太字の文字(ここではxとZ)は、複数の成分を有していることを示し、以下の他の式についても同様である。また、文章中の文字については、いずれも太字で示していないが、各式と整合をとったものであるものとする。
【0029】
また、J(x,z;M)はサンプルxのクラスをzと予測したときのモデルMの誤差関数を表す。誤差関数の例として、
負の対数尤度J(x,z;M)=-logP(z|x;M)や、
0-1損失関数J(x,z;M)=0(if f(x)=y),
J(x,z;M)=1(otherwise)、などが考えられる。なお、本明細書では、対数は自然対数、すなわち、対数logの底は「e」であるものとする。
【0030】
重みを、以下のように決定する(動作主体については後記。以下同様)。まず、クラスyにおける経験分布を近似するモデル分布P(x|y)(本明細書において、経験分布を意味する記号「」はその直前の文字の上に付される記号であるものとする。後記する「^」についても同様)を推定する(式(2))。ここで、δ(x,xn)はクロネッカーのデルタを表し、N(y)はクラスがyであるサンプルの数を表す。
【数2】
JP0005164209B2_000003t.gif

【0031】
次に、モデル分布の全クラスの混合がターゲットクラスz∈Zの真の分布P(x|z)を近似するように、混合比P(y)を推定する(式(3))。ここで、混合比とは、ターゲット分類体系と補助分類体系とを統合した場合の確率分布モデルを、ターゲット分類体系の確率分布モデルに近似させるための、ターゲット分類体系と補助分類体系とのクラスごとの、分類モデルに対する影響度の比率を示すものである。
【数3】
JP0005164209B2_000004t.gif

【0032】
なお、混合比P(y)、および、混合比P(y)の集合Pは、
P={{P(y)}y∈Yz∈Z(0≦P(y)≦1,Σy∈Y(y)=1)を満たすものとする。
【0033】
そして、重みw(z|y)を設定(算出)する(式(4))。なお、P(z)は、あるサンプルに関してクラスzが選ばれる確率である。
【数4】
JP0005164209B2_000005t.gif

【0034】
このとき、重み付き誤差E(M)は期待誤差の近似となる(式(5))。
【数5】
JP0005164209B2_000006t.gif

【0035】
式(5)において、右辺の1行目から2行目への式変形は、nについての総和の式をxとyについての総和の式に変えたものである。右辺の2行目から3行目への式変形は、式(4)を使ったものである。右辺の3行目から4行目への式変形は、式(2)を使ったものである。右辺の4行目から5行目への式変形は、式(3)を使ったものである。右辺の5行目から6行目への式変形は、条件付確率の公式(定義)を使ったものであり、P(x,z)はxとzが同時に発生する確率を示す。
【0036】
右辺の6行目から7行目への式変形は、期待値の公式(定義)を使ったものであり、ε[J(x,z;M)]はターゲットクラスzに関する誤差の期待値を示す。このため、補助データも利用した重み付き誤差E(M)を最小化することにより、頑健な(高精度な)モデルが推定できると期待できる。
【0037】
式(3)の近似を満たす集合Pは、ターゲットデータに対する対数尤度L(P)をEM(Expectation-Maximization)アルゴリズムを用いて最大化することにより推定する(式(6))。EMアルゴリズムとは、E(Expectation)ステップとM(Maximization)ステップとの2つの手順を収束条件が満たされるまで繰り返すことで、パラメータ(ここでは集合P)の最尤推定を行うアルゴリズムである。
【数6】
JP0005164209B2_000007t.gif

【0038】
ここで、P-n(x|y)は、n番目のサンプルを除いたデータを用いて推定したモデル分布を表す。モデル分布の推定に用いたサンプルを用いて混合比を推定する場合、過学習を起こし、P(z)=1、P(y≠z)=0という自明な解が得られてしまうため、式(6)のように1eave-one-out(LOO)法を用いる。P-n(x|y)をクラスyのデータを用いて推定し固定した場合、L(P)はPに関して上に凸であるため、解の大域的最適性が保証される。EMアルゴリズムにおける第τステップでの推定値をP(τ)とする。ここで、τは、EステップとMステップとの2つの手順を繰り返した回数(τ=0,1,2,…)を指す。なお、τ=0のときには推定値の予め定められた初期値を示す。このとき、最大化すべき完全データ対数尤度の条件付き期待値Q(P|P(τ))は、式(7)のように表すことができる。
【数7】
JP0005164209B2_000008t.gif

【0039】
Eステップにおける計算は式(8)のように表すことができる。なお、式(8)の右辺の分母におけるy’は、式(8)の他の箇所におけるyと区別するために便宜上記号を変えたもので、yと同じ意味である。
【数8】
JP0005164209B2_000009t.gif

【0040】
Mステップにおける計算は式(9)のように表すことができる。
【数9】
JP0005164209B2_000010t.gif

【0041】
このEステップにおける計算とMステップにおける計算を、収束条件が満たされるまで繰り返すことにより、集合Pの推定値が得られる。
【0042】
なお、EMアルゴリズムではなく、準ニュートン法など他の最適化手法を用いて式(6)を最大化することによっても、集合Pを推定できる。
【0043】
<重み推定>
図2を参照しながら、重み推定部21の構成について説明する。図2は、本実施形態に係る重み推定部のブロック図を含む図である。図2に示すように、重み推定部21は、入力データ読込部211と、事後確率推定部212と、混合比推定部213と、重み書込部214とを備えている。
【0044】
まず、入力データ読込部211により、入力データ44を読み込む。そして、事後確率推定部212によって式(8)を用いて全学習用サンプルの全時刻に対する事後確率を推定し、また、混合比推定部213によって式(9)を用いて混合比を推定する。この事後確率推定と混合比推定を式(6)が収束するまで交互に繰り返し、重み書込部214において、
重みをw(z|y)=P(z)P(y)/N(y)と設定(算出)し、重み45に格納する。なお、格納された重み45は、モデル構築部22で利用される。
【0045】
<モデル構築>
図3を参照しながら、モデル構築部22の構成について説明する。図3は、本実施形態に係るモデル構築部のブロック図を含む図である。図3に示すように、モデル構築部22は、入力データ読込部221と、重み読込部222と、モデルパラメータ推定部223と、モデルパラメータ書込部224とを備えている。
【0046】
まず、入力データ読込部221により、入力データ44を読み込む。また、重み読込部222により、重み45を読み込む。そして、モデルパラメータ推定部223によって式(10)を用いてモデルパラメータM^を推定する。
【数10】
JP0005164209B2_000011t.gif

なお、式(10)の左辺においてMに付した記号「^(ハット)」は、そのMがargmin関数の引数を最小化させることを示すものである。
【0047】
モデルパラメータ書込部224は、モデルパラメータ推定部223が推定したモデルパラメータをモデルパラメータ46に格納する。なお、格納されたモデルパラメータ46は、分類部23で利用される。
【0048】
図4を参照しながら、分類部23の構成について説明する。図4は、本実施形態に係る分類部のブロック図を含む図である。図4に示すように、分類部23は、テストデータ読込部231と、モデルパラメータ読込部232と、分類結果出力部233とを備えている。
【0049】
まず、テストデータ読込部231により、未分類のテストデータ47を読み込む。また、モデルパラメータ読込部232により、モデルパラメータ46を読み込む。そして、分類結果出力部233において、テストデータとモデルパラメータを使って分類結果を計算し、分類結果を出力する。
【0050】
図1に示した分類装置1の動作について図5を参照(適宜図1参照)して説明する。図5は、本実施形態に係る分類装置の処理の流れを示す説明図である。
【0051】
まず、分類装置1は、重み推定部21によって、記憶手段4(図1参照)に予め格納された入力データ44に基づいて重みを推定する(ステップS10:重み推定ステップ)。推定された重みは、重み45として記憶手段4に格納される。次に、分類装置1は、モデル構築部22によって、記憶手段4(図1参照)に予め格納された入力データ44および重み45に基づいてモデルを構築する(ステップS20:モデル構築ステップ)。構築されたモデルは、モデルパラメータ46として記憶手段4に格納される。このステップS10とステップS20はモデルの学習に関する処理である。
【0052】
続いて、分類装置1は、分類部23によって、記憶手段4(図1参照)に予め格納された未分類であるテストデータ47(分類対象データ)を、モデルパラメータ46に基づいて分類する(ステップS30:分類ステップ)。このステップS30は分類対象データの分類に関する処理である。
【0053】
次に、前記したステップS10の重み推定ステップについて図6を参照(適宜図1ないし図5参照)して説明する。図6は、重み推定ステップの処理を示すフローチャートである。
【0054】
まず、図6に示すように、重み推定部21は、入力データ読込部211によって、記憶手段4(図1参照)から、入力データ44を読み込む(ステップS1)。次に、重み推定部21は、事後確率推定部212によって、モデル分布の推定を行う(ステップS2)。具体的には、前記した式(2)を満たすモデル分布を推定する。
【0055】
その後、重み推定部21は、事後確率推定部212によって、初期化を行う(ステップS3)。具体的には、事後確率推定部212は、EMアルゴリズムのEステップとMステップとの2つの手順の繰り返し回数τを0に設定し、混合比P(y)の分布をランダムに設定する。
【0056】
次に、重み推定部21は、事後確率推定部212によって、EMアルゴリズムのEステップを実行する(ステップS4)。具体的には、事後確率推定部212は、前記した式(8)により、前記事後確率を推定する。続いて、重み推定部21は、混合比推定部213によって、EMアルゴリズムのMステップを実行する(ステップS5)。具体的には、混合比推定部213は、前記した式(9)により、前記混合比を推定する。次に、重み推定部21は、混合比推定部213によって、収束条件が満たされたか否かを判別する(ステップS6)。具体的には、混合比推定部213は、前記した式(6)に示す尤度L(P)が収束したか否かを判別する。この収束の判別は、閾値や変化率などを使用することにより行うことができる。
【0057】
収束条件が満たされた場合、すなわち前記した式(6)に示す尤度L(P)が収束した場合(ステップS6:Yes)、混合比推定部213は、重みw(z|y)を計算する(ステップS8)。具体的には、混合比推定部213は、
w(z|y)=P(z)P(y)/N(y)の式を用いて重みを計算する。そして、重み推定部21は、重み書込部214によって、その重みを、重み45として、記憶手段4(図1参照)に書き込み、処理を終了する。
【0058】
一方、ステップS6において、収束条件が満たされていない場合、すなわち前記した式(6)に示す尤度L(P)が収束していない場合(ステップS6:No)、重み推定部21は、EステップおよびMステップの繰り返し回数τに「1」を加算し(τ=τ+1)(ステップS7)、ステップS4に戻る。
【0059】
本実施形態によれば、分類装置1は、ターゲット分類体系における既分類データだけでなく、補助分類体系における既分類データも用い、誤差関数と重みとの積の総和である期待誤差(式(5)参照)を最小化させるように重みを推定し、その推定された重みと2種類の既分類データとを用いて分類モデルを生成することで、補助分類体系のデータも有効に利用し、ターゲット分類体系に関する高精度な分類モデルを生成することができる。
【0060】
また、重み推定部21が、事後確率推定部212と、混合比推定部213とを備えているので、例えば、事後確率推定部212が、EMアルゴリズムにおけるEステップを行い、かつ、混合比推定部213がMステップを行うことで、混合比についての大域的最適解を求め、求めた混合比から重みを決定(推定)することができる。
【0061】
また、例えば、モデルパラメータ推定部223が、式(10)を用いてモデルパラメータを推定することができる。
【0062】
また、分類部23が、推定したモデルパラメータを用いて分類対象データをターゲット分類体系における複数のクラスのいずれかに分類する、つまり、高精度な分類モデルを用いることで高精度な分類を実現することができる。
【0063】
また、分類装置1は、一般的なコンピュータに、前記した各処理のプログラムを実行させることで実現することもできる。このプログラムは、通信回線を介して配布することも可能であるし、CD-ROM(Compact Disc-Read Only Memory)等の記録媒体に書き込んで配布することも可能である。
【0064】
以上で本実施形態の説明を終えるが、本発明の態様はこれらに限定されるものではない。例えば、本発明は、任意の誤差関数およびモデルを用いることが可能である。その他、ハードウェアやフローチャート等の具体的な構成について、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【実施例】
【0065】
《人工データにおける実施例》
本実施形態の分類装置1を評価するため、人工データを用いた2クラス分類実験を行った。この2クラス分類実験とは、ターゲットデータと補助データから生成した分類モデルに基づき、テストデータを2つのクラスのいずれかに分類する実験である。
【0066】
ターゲットデータは平均の異なる2つの100次元正規分布からデータが生成されるものとする。ここで、クラスc、cの平均はそれぞれ
μ=(-1,0,0,・・・,0),μ=(1,0,0,・・・,0)であり、共分散行列はともに単位行列であるものとする。そして、補助データとして,以下の3パターンを考える。なお、第3次元以降の平均はターゲットデータと同じく全て0、共分散行列は全て単位行列とする。図7(a)にターゲットデータ,図7(b)~(d)に各補助データの生成モデルの第1,第2次元を示す。図7(a)~(d)は、特に軸や目盛りを図示していないが、2次元の座標平面を表しており、中央部分が原点である。また、各円は標準偏差のラインを表す。
【0067】
図7(b)に示す同一補助データは、ターゲットデータと同一の生成モデルから生成され、クラスc、cの平均はそれぞれ
μ=(-1,0,0,・・・,0),μ=(1,0,0,・・・,0)である。
【0068】
図7(c)に示す相関補助データは、ターゲットデータとクラス間関係に相関がある生成モデルから生成され、クラスc、cの平均はそれぞれ
μ=(-√0.5,√0.5,0,・・・,0),
μ=(√0.5,-√0.5,0,・・・,0)である。
【0069】
図7(d)に示す混合補助データは、同一補助データ、および、ターゲットデータとクラス間関係が直交する補助データの組合せ(混合)であり、クラスc、c、c、cの平均はそれぞれ
μ=(-1,0,0,・・・,0),μ=(1,0,0,・・・,0),
μ=(0,1,0,・・・,0),μ=(0,-1,0,・・・,0)である。なお、補助データのうち、この混合補助データのみ4補助クラスであり、それ以外は2補助クラスである。
【0070】
ターゲットデータとして各クラス2,4,8,16,32,64,128,256サンプル(入力データ44)、補助データとして各クラス256サンプル(入力データ44)、テストデータとして各クラス100サンプル(テストデータ47)を生成した。これらに基づき、分類モデルを生成し、補助データを使わない場合(ターゲットデータのみ)と各補助データを使った場合の、テストデータの分類に関する正答率を計算した。その結果、表1のようになった。表1において、右4列の数字は平均正答率の百分率を示し、それぞれの括弧内の数字は標準偏差を示している。本実施形態の分類装置1の分類方法に基づいて補助データを使うことによって、補助データを使わない場合よりも正答率が向上していることがわかる。
【0071】
【表1】
JP0005164209B2_000012t.gif

【0072】
《テキストデータにおける実施例》
本実施形態の分類装置1を評価するため、テキストデータを用いて分類実験を行った。
【0073】
<モデル分布>
モデル分布P(x|y)として、正規分布、多項分布など任意の分布を仮定することができる。ここでは、入力データ44およびテストデータ47としてテキストデータを想定し、xを単語出現頻度ベクトルと考え、モデル分布として多項分布P(x|y)(式(11))を用いる。
【数11】
JP0005164209B2_000013t.gif

ここで、Vは総語彙数、θyjはクラスyのときj番目の単語が出現する確率、xnjはn番目のサンプルにおけるj番目の単語の出現頻度を表す。
【0074】
多項分布のパラメータθyjのn番目のサンプルを除いたときのLOO最尤推定値θ^-n,yjは式(12)で得られる。
【数12】
JP0005164209B2_000014t.gif

【0075】
ここで、ゼロ確率問題を回避するために、LOO最尤推定値と一様分布の線形和を用いてスムージングする(式(13))。
【数13】
JP0005164209B2_000015t.gif

【0076】
ここで、0≦α≦1はハイパーパラメータである。ハイパーパラメータを人手で設定してもよいが、一般化EMアルゴリズムを用いることにより、以下の
Q(P,α|P(τ),α(τ))を最大化するように、混合比の集合Pとハイパーパラメータαを同時にデータから推定することも可能である(式(14))。
【数14】
JP0005164209B2_000016t.gif

【0077】
Eステップは式(8)、Mステップにおける混合比の更新は式(9)で、通常のEMアルゴリズムと同様に実現できる。Mステップにおけるハイパーパラメータの更新はニュートン法を用いて行う(式(15))。
【数15】
JP0005164209B2_000017t.gif

【0078】
ここで、式(15)に記載されている式(14)のαによる一階偏微分は式(16)となる。
【数16】
JP0005164209B2_000018t.gif

【0079】
また、式(15)に記載されている式(14)のαによる二階偏微分は式(17)となる。
【数17】
JP0005164209B2_000019t.gif

【0080】
式(17)から明らかなように、二階偏微分は常に負になるため、
Q(P,α|P(τ),α(τ))はαに関して上に凸である。この実験では、一般化EMアルゴリズムを用いて混合比の集合Pおよびハイパーパラメータαをデータから推定した。
【0081】
<分類モデル>
代表的なテキスト分類モデルであるナイーブベイズモデルとロジスティック回帰モデルをモデルMとして用いた場合について説明する。
【0082】
(ナイーブベイズモデル)
ナイーブベイズモデルではクラスが与えられたとき、文書中の各単語は独立に生成されると仮定され、クラスzにおける単語出現頻度ベクトルxの分布P(x|z)が多項分布で表される(式(18))。
【数18】
JP0005164209B2_000020t.gif

【0083】
ここで、φzjはクラスzの文書におけるj番目の単語が出現する確率を表す。誤差関数として負の対数尤度を用い、また、φ={{φzjj=1z∈Zの事前確率としてディリクレ分布P(φ)∝Πz∈ZΠj=1φβzjを用いたとき、重み付き誤差関数E(MNB)は、式(19)のように表される。
【数19】
JP0005164209B2_000021t.gif

【0084】
式(19)を最小化するφzjの推定値φ^zjは、式(20)によって得られる。
【数20】
JP0005164209B2_000022t.gif

【0085】
(ロジスティック回帰モデル)
ロジスティック回帰モデルでは、単語出現頻度ベクトルxが与えられたとき、クラスzに属する確率P(z|x)は式(21)のように表される。
【数21】
JP0005164209B2_000023t.gif

【0086】
ここで、λはクラスzに関する未知パラメータベクトル、λはλの転置を表す。誤差関数として負の対数尤度を用い、また、λの事前確率として平均0、共分散行列γ-1I(Iは単位行列)の正規分布を用いたとき、重み付き誤差(期待誤差)E(MLR)は、式(22)のように表される。
【数22】
JP0005164209B2_000024t.gif

【0087】
準ニュートン法などを用いて式(22)の値を最小化することにより、未知パラメータベクトル{λz∈Zを推定できる。ロジスティック回帰モデルを用いた場合、各サンプルの誤差関数を付加するのみであるため、これまで提案されている多くの分類モデルを若干修正するのみで適用することができる。
【0088】
<比較手法>
分類モデルとしてナイーブベイズモデルを用いた本手法(本実施形態の分類装置1による手法)(CA-NB)と、分類モデルとしてロジスティック回帰モデルを用いた本手法(CA-LR)と、補助データを用いないナイーブベイズモデルによる手法(NB)、ロジスティック回帰モデルによる手法(LR)の4手法を比較した。NBの推定値は、推定値である式(20)の重みを
w(z|z)=1,w(z|y≠z)=0としたものである。同様に、LRの推定値は、本手法における重み付き誤差である式(22)の重みを
w(z|z)=1,w(z|y≠z)=0として最小化することにより得られる。
【0089】
それぞれの実験において評価用データセットを100作成し、その平均正答率を用いて評価した。また、評価用データセットとは別に1つの開発用データセットを作成し、各手法において開発用データセットの正答率を最も高くする分類モデルのハイパーパラメータ(βもしくはγ)を{10-3,10-2,10-1,1}の4候補から選択した。
【0090】
<Toyデータ>
20Newsgroups(20news)から作成したデータセットを用い、各補助クラスの分布が、あるターゲットクラスと同じ分布である場合の、本手法の効果を評価する。20newsは、20のディスカッショングループに投稿された約2万の英語文書から成る。各文書の特徴量として単語出現頻度を用いた。このとき、停止語(文書に含まれる意味的な内容を持たない前置詞や冠詞などの一般的に機能語と呼ばれ検索に役立たない単語)および出現頻度が1以下の単語は省き、総語彙数は52,647であった。
【0091】
20のグループのうち、コンピュータ(comp)を親ディレクトリにもつ5つのグループ(graphics,os.ms-windows.misc,sys.ibm.pc.hardware,sys.mac.hardware,windows.x)に分類する問題について、
ターゲットクラス集合をZ={c,・・・,c}、
補助クラス集合をA={c,・・・,c10}とする。
【0092】
そして、graphicsの記事をターゲットクラスcもしくは補助クラスcに、os.ms-windows.miscの記事をターゲットクラスcもしくは補助クラスcに、sys.ibm.pc.hardwareの記事をターゲットクラスcもしくは補助クラスcに、sys.mac.hardwareの記事をターゲットクラスcもしくは補助クラスcに、windows.xの記事をターゲットクラスcもしくは補助クラスc10に、ランダムに割り当て、ターゲットデータおよび補助データを作成した。
【0093】
このとき、テストデータとして各クラス100サンプル、ターゲットデータとして各クラス2,4,8,16,32,64,128,256サンプル、補助データとして残り全サンプル用いた。総学習サンプル数は4,363であった。このときの正答率を表2に示す。表2において、右4列の数字は平均正答率の百分率を示し、それぞれの括弧内の数字は標準偏差を示している。
【0094】
【表2】
JP0005164209B2_000025t.gif

【0095】
本手法であるCA-NB、CA-LRの正答率は学習サンプル数が少ない場合でも極めて高く、補助データを適切に利用することにより、頑健な(高精度な)モデル推定ができていると言える。
【0096】
<20Newsgroupsデータ>
20newsの20グループのうち、comp.graphics,rec.sport.baseba11,sci.electronics,talk.religion.miscの4グループをターゲットクラスとし、他の16グループを補助クラスとしてデータを作成し、本手法を評価した。テストデータ47として各クラス100サンプル、ターゲットデータ(入力データ44)として各クラス2,4,8,16,32,64,128,256サンプル、補助データ(入力データ44)として全サンプル用いた、総補助サンプル数は15,211であった。このときの正答率を表3に示す。表3において、右4列の数字は平均正答率の百分率を示し、それぞれの括弧内の数字は標準偏差を示している。本手法であるCA-NBの正答率が最も高くなっている。
【0097】
【表3】
JP0005164209B2_000026t.gif

【0098】
<Webページデータ>
日本語のディレクトリ型検索エンジンgoo(登録商標)カテゴリ検索(2003年9月取得)とyahoo(登録商標)カテゴリ(2003年3月取得)のデータを用いて本手法を評価した。形態素解析により単語を抽出し、両カテゴリで出現数が10以上の単語を特徴量として用いた。このとき、総語彙数は43,200であった。goo(登録商標)とyahoo(登録商標)でクラスラベルが同一のクラスや、関連していると思われるクラスもあるが、明確な対応付けが難しいクラスもあり、また、クラス数も異なる(goo(登録商標):13クラス、yahoo(登録商標):14クラス)。
【0099】
goo(登録商標)ディレクトリのクラスをターゲットクラスとし、テストデータ47として各クラス100サンプル、ターゲットデータ(入力データ44)として各クラス2,4,8,16,32,64,128,256サンプル、補助データ(入力データ44)としてyahoo(登録商標)ディレクトリに含まれる全サンプル用いた。総補助サンプル数は51,728であった。このときの正答率を表4に示す。表4において、右4列の数字は平均正答率の百分率を示し、それぞれの括弧内の数字は標準偏差を示している。本手法であるCA-NR、CA-LRの正答率が総じて高くなっている。
【0100】
【表4】
JP0005164209B2_000027t.gif

【図面の簡単な説明】
【0101】
【図1】本実施形態に係る分類装置の構成を示すブロック図である。
【図2】本実施形態に係る重み推定部のブロック図を含む図である。
【図3】本実施形態に係るモデル構築部のブロック図を含む図である。
【図4】本実施形態に係る分類部のブロック図を含む図である。
【図5】本実施形態に係る分類装置の処理の流れを示す説明図である。
【図6】重み推定ステップの処理を示すフローチャートである。
【図7】(a)はターゲットデータ、(b)~(d)は各補助データの生成モデルの第1、第2次元を示す図である。
【符号の説明】
【0102】
1 分類装置
2 演算手段
3 入力手段
4 記憶手段
5 出力手段
11 バスライン
21 重み推定部
22 モデル構築部
23 分類部
24 メモリ
40a プログラム格納部
41 重み推定プログラム
42 モデル構築プログラム
43 分類プログラム
40b データ格納部
44 入力データ
45 重み
46 モデルパラメータ
47 テストデータ
211 入力データ読込部
212 事後確率推定部
213 混合比推定部
214 重み書込部
221 入力データ読込部
222 重み読込部
223 モデルパラメータ推定部
224 モデルパラメータ書込部
231 テストデータ読込部
232 モデルパラメータ読込部
233 分類結果出力部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6