(57)【要約】【課題】多重トピック分類を高速かつ高精度におこなうこと。【解決手段】多重トピック分類装置２００は、学習処理をおこなう場合、取得部２１１により、分類済みデータ２０１とその訓練データセットＹを取得する。つぎに、生成部２１２により、分類済みデータ２０１の素性ベクトルｘを生成する。そして、算出部２１３によりトピック共起行列Ｋを算出する。このあと、設定部２１４により、重みベクトル設定処理を実行する。また、分類処理をおこなう場合、取得部２１１により、未分類データ２０２を取得する。つぎに、生成部２１２により、未分類データ２０２の素性ベクトルｘを生成する。そして、分類部２２１により、単独トピック分類実行処理および多重トピック分類実行処理をおこなう。最後に、出力部２２２により、分類結果を出力する。【選択図】図２
2008276344.tif 000002
【特許請求の範囲】
【請求項１】
未分類データの多重トピック分類を実行する多重トピック分類装置において、
分類済みデータと当該分類済みデータに付与されたトピックに関する訓練データとを取得する取得手段と、
前記取得手段によって取得された分類済みデータの素性ベクトルを生成する生成手段と、
前記取得手段によって取得された訓練データと前記生成手段によって生成された素性ベクトルとに基づいて、前記訓練データにより表現されるトピック間の相関をあらわすトピック共起カーネルを算出する算出手段と、
前記算出手段によって算出されたトピック共起カーネルに基づいて、前記未分類データの多重トピック分類に用いる重みベクトルを設定する設定手段と、
を備えることを特徴とする多重トピック分類装置。
【請求項２】
前記算出手段は、Dice係数によるトピック共起カーネルを算出することを特徴とする請求項１に記載の多重トピック分類装置。
【請求項３】
前記未分類データの多重トピック分類を実行する分類手段を備え、
前記取得手段は、未分類データを取得し、
前記生成手段は、前記取得手段によって取得された未分類データの素性ベクトルを生成し、
前記分類手段は、前記生成手段によって生成された前記未分類データの素性ベクトルと前記設定手段によって設定された重みベクトルとに基づいて、前記未分類データの多重トピック分類をおこなうことを特徴とする請求項１または２に記載の多重トピック分類装置。
【請求項４】
未分類データの多重トピック分類を実行する多重トピック分類方法において、
分類済みデータと当該分類済みデータに付与されたトピックに関する訓練データとを取得する取得工程と、
前記取得工程によって取得された分類済みデータの素性ベクトルを生成する生成工程と、
前記取得工程によって取得された訓練データと前記生成工程によって生成された素性ベクトルとに基づいて、前記訓練データにより表現されるトピック間の相関をあらわすトピック共起カーネルを算出する算出工程と、
前記算出工程によって算出されたトピック共起カーネルに基づいて、前記未分類データの多重トピック分類に用いる重みベクトルを設定する設定工程と、
を含んだことを特徴とする多重トピック分類方法。
【請求項５】
未分類データの多重トピック分類をコンピュータに実行させる多重トピック分類プログラムにおいて、
分類済みデータと当該分類済みデータに付与されたトピックに関する訓練データとを取得する取得工程と、
前記取得工程によって取得された分類済みデータの素性ベクトルを生成する生成工程と、
前記取得工程によって取得された訓練データと前記生成工程によって生成された素性ベクトルとに基づいて、前記訓練データにより表現されるトピック間の相関をあらわすトピック共起カーネルを算出する算出工程と、
前記算出工程によって算出されたトピック共起カーネルに基づいて、前記未分類データの多重トピック分類に用いる重みベクトルを設定する設定工程と、
を前記コンピュータに実行させることを特徴とする多重トピック分類プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、文書などの分類対象に複数のトピックを付与する多重トピック分類装置、多重トピック分類方法、および多重トピック分類プログラムに関する。
【背景技術】
【０００２】
従来、文書分類において１文書に１つの分類ラベルを付与することが前提となっていた。これは、排他的に分類され１文書に１つの分類ラベルが付与されていたほうが利用しやすいためと考えられる。しかし、この排他的な分類を実現するために分類器の性能向上はもちろん、厳密に構成された分類基準、分類ラベル定義が必要であった。この分類基準の構築とメンテナンスには多大なコストがかかるのが普通である。
【０００３】
一方、現在は、タグを使って種々の情報を整理するサービスがひろまってきている。その理由の１つは、１データに対して１整理タグを付与させるような厳密な分類システムや複雑な分類階層構造を使用せずに、シンプルでフラットな分類タグを複数付与させる簡易な仕様であると考えられる。
【０００４】
しかし、付与された多重分類タグを再利用する場合には、その複数タグ間の相関や階層を考慮しないと、効率的で有用な分類ができないようになってきている。こういった背景から、文書分類において１文書に複数の分類タグを付与する多重トピック文書分類の重要性は高くなってきている。現在までの多重トピック文書分類の研究は、Naive Bayes 法に基づく手法と、ＳＶＭ（Support Vector Machine）を多値分類へ一般化する手法と、に大別される。
【０００５】
A. McCallumらは、各トピックに対するNaive Bayes 分類器の混合モデルを構成し、その混合係数をＥＭアルゴリズムで推定することで多重トピック分類を実現する手法を提案した（下記非特許文献１を参照。）。
【０００６】
同じく上田らは、それぞれのトピックに対応するNaive Bayes 分類器の混合モデルであるパラメトリック混合モデル（ＰＭＭ）を提案し、ＳＶＭなどの従来法に比べて平均Ｆ１値で上回ることを実験で示した（下記非特許文献２を参照。）。
【０００７】
Altun らは、構造マッピングの学習を多値分類ＳＶＭの一般化として定式化した。彼らの定式化では、分類対象と分類先構造データを１つの素性空間での事例ベクトルと考え、その事例ベクトルと新に作った不正解構造データを伴う負例事例ベクトルとのマージンを最大化するように重みベクトルを決定する。彼らは、木構造の文書分類階層を持った文書分類タスクにこの手法を適用し一対他方式のＳＶＭに比べて精度性能で上回ったと報告している（下記非特許文献３を参照。）。
【０００８】
同じく、賀沢らは、多重トピック文書分類にマージン最大化法による分類手法（ＭＭＬ）を提案した（下記非特許文献４，５を参照。）。ＭＭＬでは、トピック素性空間と語彙素性空間にそれぞれカーネル関数が定義され、その結合カーネル関数を使用してＳＶＭと同じ枠組によって学習分類が実行される。
【０００９】
ＭＭＬの手法は基本的に上記の構造マッピングのマージン最大化学習と同じであるが、多重トピックのベクトル間の類似度に相当するカーネル関数に線形カーネルとトピックＦ１値に基づく非線型カーネルを使用している。そして、一対他方式のＳＶＭやＰＭＭを含む他の多重トピック文書分類器との精度比較実験を行い、精度性能で他の手法より優れていることと報告している。
【００１０】
【非特許文献１】A. McCallum. Multi-label text classification with a mixturemodel trained by EM. AAAI’99 Workshop on TextLearning, 1999.
【非特許文献２】N. Ueda and K. Saito. Single-shot detection of multiple categories of text using parametric mixture models. Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 626-631, 2002.
【非特許文献３】Y. Altun, I. Tsochantaridis, and T. Hofmann. Hidden markov support vector machines. Proc. ICML, 2003.
【非特許文献４】平博順，前田英作，磯崎秀樹，賀沢秀人，泉谷知範  最大マージン原理に基づく多重ラベリング学習”電子情報通信学会論文誌D-II Vol.J88-D-II No.11 pp.2246-2259 (2005).
【非特許文献５】Maximal Margin Labeling for Multi-Topic Text CategorizationAdvances in Neural Information Processing Systems 17, pp.649-656 (2005)
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、上述したＭＭＬは精度性能に優れた多重トピック文書分類器ではあるが、以下の問題がある。１つは、多重トピック分類の本来の目的である出力トピック数が大きい場合の精度性能において問題がある。彼らの報告では出力トピック数が４以上の場合においては、ＰＭＭと同等以下の性能を示している。
【００１２】
さらに、トピックＦ１値に基づく非線型カーネル関数を使用した場合、分類時にもカーネル関数を使って分類をする必要があり、現実にはその分類処理速度の遅さから実用が不可能であるという問題がある。
【００１３】
この発明は、上述した従来技術による問題点を解消するため、多重トピック分類を高速かつ高精度におこなうことができる多重トピック分類装置、多重トピック分類方法、および多重トピック分類プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上述した課題を解決し、目的を達成するため、この発明にかかる多重トピック分類装置、多重トピック分類方法、および多重トピック分類プログラムは、未分類データの多重トピック分類を実行する多重トピック分類装置、多重トピック分類方法、および多重トピック分類プログラムにおいて、分類済みデータと当該分類済みデータに付与されたトピックに関する訓練データとを取得し、取得された分類済みデータの素性ベクトルを生成し、取得された訓練データと生成された素性ベクトルとに基づいて、前記訓練データにより表現されるトピック間の相関をあらわすトピック共起カーネルを算出し、算出されたトピック共起カーネルに基づいて、前記未分類データの多重トピック分類に用いる重みベクトルを設定することを特徴とする。
【００１５】
また、上記発明において、Dice係数によるトピック共起カーネルを算出することとしてもよい。
【００１６】
また、上記発明において、未分類データを取得し、取得された未分類データの素性ベクトルを生成し、生成された前記未分類データの素性ベクトルと重みベクトルとに基づいて、前記未分類データの多重トピック分類をおこなうこととしてもよい。
【００１７】
これらの発明によれば、相関の強い多重トピックは、それ自身マルチトピックのサブ構造の1 つと考えることができるため、各トピック間の相関を明示的に表すカーネル関数を導入することで、多重トピックを単独トピックと相関の強い多重トピックの重ね合わせとして表現することができる。
【００１８】
また、Dice係数に基づくトピック共起カーネルを構築することにより、カーネル行列の非対角項でそのままトピック対の共起の強さをあらわすことができ、共起の強さによって異なるトピック間の類似度を設定することができる。
【発明の効果】
【００１９】
本発明にかかる多重トピック分類装置、多重トピック分類方法、および多重トピック分類プログラムによれば、多重トピック分類を高速かつ高精度におこなうことができるという効果を奏する。
【発明を実施するための最良の形態】
【００２０】
以下に添付図面を参照して、この発明にかかる多重トピック分類装置、多重トピック分類方法、および多重トピック分類プログラムの好適な実施の形態を詳細に説明する。
【００２１】
まず、本発明の概要について説明する。ＭＭＬでは、トピック素性空間と語彙素性空間にそれぞれカーネル関数が定義され、その結合カーネル関数を使用してＳＶＭと同じ枠組によって学習分類が実行されるが、本発明では、訓練データの各トピック間の共起情報からトピック素性空間のカーネル関数を構築する手法を採用する。
【００２２】
すなわち、ＭＭＬの上記２つの問題点を改善するためにマージン最大化多重トピック分類器にトピック共起カーネルを導入する。トピック共起カーネル関数は、各トピックの訓練データ中の共起頻度に基づいてDice係数から定義される。
【００２３】
異なるトピック間の類似度をDice係数で表現でき、これによって相関の強い、より関連したトピック対を１つの分類クラスのように扱うことができる。さらに、この効果によって、多重トピックを関連の強いトピック対の重ね合わせの状態として表現し、多重トピックのサイズの大きい場合でもより適切な分類をおこなうことができる。また、トピックF1 値に基づく非線型カーネルと異なり、トピック共起カーネルは斜交軸の空間で定義される線形カーネル関数であるため、分類時に重みベクトルを明示的に構成することができる。そのために高速な分類が可能になる。
【００２４】
（多重トピック分類装置のハードウェア構成）
まず、この発明の実施の形態にかかる多重トピック分類装置のハードウェア構成について説明する。図１は、この発明の実施の形態にかかる多重トピック分類装置のハードウェア構成を示すブロック図である。
【００２５】
図１において、多重トピック分類装置は、ＣＰＵ１０１と、ＲＯＭ１０２と、ＲＡＭ１０３と、ＨＤＤ（ハードディスクドライブ）１０４と、ＨＤ（ハードディスク）１０５と、ＦＤＤ（フレキシブルディスクドライブ）１０６と、着脱可能な記録媒体の一例としてのＦＤ（フレキシブルディスク）１０７と、ＣＤ−ＲＷドライブ１０８と、ＣＤ−ＲＷ１０９と、ディスプレイ１１０と、キーボード１１１と、マウス１１２と、ネットワークＩ／Ｆ１１３と、を備えている。また、各構成部はバス１００によってそれぞれ接続されている。
【００２６】
ここで、ＣＰＵ１０１は、多重トピック分類装置の全体の制御を司る。ＲＯＭ１０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ１０３は、ＣＰＵ１０１のワークエリアとして使用される。ＨＤＤ１０４は、ＣＰＵ１０１の制御にしたがってＨＤ１０５に対するデータのリード／ライトを制御する。ＨＤ１０５は、ＨＤＤ１０４の制御で書き込まれたデータを記憶する。
【００２７】
ＦＤＤ１０６は、ＣＰＵ１０１の制御にしたがってＦＤ１０７に対するデータのリード／ライトを制御する。ＦＤ１０７は、ＦＤＤ１０６の制御で書き込まれたデータを記憶したり、ＦＤ１０７に記憶されたデータを多重トピック分類装置に読み取らせたりする。
【００２８】
ＣＤ−ＲＷドライブ１０８は、ＣＰＵ１０１の制御にしたがってＣＤ−ＲＷ１０９に対するデータのリード／ライトを制御する。ＣＤ−ＲＷ１０９は、ＣＤ−ＲＷドライブ１０８の制御で書き込まれたデータを記憶したり、ＣＤ−ＲＷ１０９に記憶されたデータを多重トピック分類装置に読み取らせたりする。また、着脱可能な記録媒体として、ＭＯ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、メモリーカードなどであってもよい。
【００２９】
ディスプレイ１１０は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ１１０は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００３０】
キーボード１１１は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス１１２は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００３１】
ネットワークＩ／Ｆ１１３は、通信回線を通じてインターネットなどのネットワーク１１４に接続され、このネットワーク１１４を介して他の装置に接続される。そして、ネットワークＩ／Ｆ１１３は、ネットワーク１１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。ネットワークＩ／Ｆ１１３には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００３２】
（多重トピック分類装置の機能的構成）
つぎに、この発明の実施の形態にかかる多重トピック分類装置の機能的構成について説明する。図２は、この発明の実施の形態にかかる多重トピック分類装置の機能的構成を示すブロック図である。
【００３３】
図２において、多重トピック分類装置２００は、未分類データ２０２の多重トピック分類を実行する機能を有し、具体的には、学習処理部２１０と分類処理部２２０とから構成されている。これらの機能的構成は、図１に示したＲＯＭ１０２，ＲＡＭ１０３，ＨＤ１０５などの記録媒体に記録されているプログラムを、ＣＰＵ１０１に実行させることによって、またはネットワークＩ／Ｆ１１３によって、その機能を実現する。
【００３４】
まず、学習処理部２１０は、分類済みデータ２０１から未分類データ２０２を分類するための重みベクトルを設定する機能を有し、具体的には、取得部２１１と生成部２１２と算出部２１３と設定部２１４とから構成されている。取得部２１１は、各種データを取得する。学習処理部２１０においては、分類済みデータ２０１と当該分類済みデータ２０１に付与された多重トピックに関する訓練データとを取得する機能を有する。
【００３５】
ここで、分類済みデータ２０１とは、トピック（分類クラスともいう）がすでに付与されている電子データであり、たとえば、論文、図書、新聞、雑誌、漫画、小説などの電子文書が挙げられる。取得部２１１は、多重トピック分類装置２００の外部から与えられた分類対象または内部に保持されている分類済みデータ２０１を読み込む。
【００３６】
また、訓練データとは、訓練済みデータに付与されたトピックがどのトピックであるかを示すデータであり、たとえば、バイナリベクトル形式で表現される。１つの分類済みデータ２０１には、１または複数の訓練データが関連付けられている。ここでは、Ｄ個の訓練データｙ1，…，ｙd，…，ｙDが関連付けられている。以降、Ｄ個の訓練データｙ1，…，ｙd，…，ｙDを訓練データセットＹと称す。
【００３７】
訓練データｙdの個数Ｄは任意に設定される。多重トピック文書分類とは、１文書に複数のトピックを付与するタスクである。分類トピック集合をＴ＝｛Ｔi｜ｉ＝１，…，ｃ｝とすると、多重トピックが付与される訓練データｙdは、次のようなトピック素性空間のバイナリベクトルとして表現できる。
【００３８】
ｙd＝｛ｔ1，…，ｔi，…，ｔc｝
ｔi＝１      ｉ番目のトピックＴiが付与される
０      ｉ番目のトピックＴiが付与されない
【００３９】
例として、トピック総数ｃ＝４の分類トピック集合Ｔ＝｛Ｔ1，Ｔ2，Ｔ3，Ｔ4｝について、Ｔ1が「国際」、Ｔ2が「政治」、Ｔ3が「経済」、Ｔ4が「スポーツ」をあらわすとする。分類済みデータ２０１が「国際政治」を扱っている（分類済み）電子文書である場合に、トピックＴ1，Ｔ2が付与されると、その電子文書におけるｄ番目の訓練データｙdは、ｙd＝｛１，１，０，０｝と表現される。
【００４０】
生成部２１２は、取得部２１１によって取得された分類済みデータ２０１の素性ベクトルｘ＝｛ｘ1，…，ｘN｝を生成する機能を有する。素性ベクトルｘは未分類データ２０２の属性をあらわすベクトルである。たとえば、分類済みデータ２０１が電子文書である場合、単語（Ｎ個）ごとの出現頻度をベクトル化する、いわゆるbag-of-word表現により、素性ベクトルｘを生成する。この場合、ｘ1，…，ｘNは、電子文書内に出現するＮ個の単語の出現頻度となる。
【００４１】
また、算出部２１３は、取得部２１１によって取得された訓練データｙdと生成部２１２によって生成された素性ベクトルｘとに基づいて、訓練データｙdにより表現されるトピック間の相関をあらわすトピック共起カーネルを算出する機能を有する。トピック共起カーネルとは、トピック間の相関を明示的に表現するカーネル関数である。
【００４２】
多重トピック分類において、分類処理部２２０により出力される多重トピックは、いくつかの関連の少ないサブトピックの重ね合わせとして表現できると考えられる。線形カーネルの場合、そのサブトピックは１つのトピックそのものとして扱われていたことに対応する。
【００４３】
しかし、相関の強い多重トピックは、それ自身、多重トピックのサブ構造の１つと考えることができる。そこで、各トピック間の相関を明示的に表現するカーネル関数を導入することで、多重トピックを、単独トピックと相関の強い多重トピックの重ね合わせとして表現する。これは、畳み込みカーネルで実現されているサブ構造全体で、構造データを素性ベクトル化する手法の近似手法とも考えられる。
【００４４】
また、従来は訓練データｙd中の多重トピックの出現頻度等の統計情報は明示的には利用されてこなかった。それらの情報は多重トピック文書分類において有益な情報と考えられる。そこで、本実施の形態では、２次までのサブ構造である、トピック対の共起頻度を利用するトピック共起カーネルを提案する。
【００４５】
トピック対の相関を考慮するにはいくつかの可能性があるが、本実施の形態では、直感的にわかりやすい非対角項がそのままトピック対の共起の強さを表現するDice係数に基づくトピック共起カーネルを構築する。
【００４６】
このトピック共起カーネルは共起の強さによって異なるトピック間の類似度を設定することができ、非特許文献４の線形カーネルに基づくＭＭＬの出力トピック数が大きい場合のトピックＦ１値の低い欠点を改善できることが期待できる。また、トピック素性空間の非対角項を持つカーネル行列として表現されるため、分類時に明示的に重みベクトルの構成ができ、高速な分類を実行することができる。
【００４７】
ここで、Dice係数によるトピック共起カーネルについて具体的に説明する。多重トピックのなす素性空間において、非対角項を持つ線形カーネル関数を、下記式（１）とする。
【００４８】
【数１】
2008276344.tif 000003
【００４９】
上記式（１）において、<,>はベクトルの内積をあらわす記号である。ｙは任意の訓練データｙdであり、ｙ’はｙとは異なる他の訓練データｙdである。また、Ｋはトピック共起行列であり、Ｋijはトピック共起行列Ｋ内の行列要素である。また、ｉはｉ番目のトピックＴiを特定するインデックスである。ｊはｊ＝１，…，ｃであり、ｊ≠ｉである。
【００５０】
また、行列要素Ｋijは、下記式（２）によってあらわされる。
【００５１】
【数２】
2008276344.tif 000004
【００５２】
上記式（２）において、＃ｙiは訓練データセットＹにおける各訓練データｙdのi番
目のトピックＴiの出現頻度であり、＃ｙjは訓練データセットＹにおける各訓練データｙdのｊ番目のトピックＴjの出現頻度である。＃ｙi∩ｙjは、訓練データセットＹに
おける各訓練データｙdのｉ，ｊ番目のトピック対Ｔi，Ｔjの共起頻度である。
【００５３】
ここで、行列要素Ｋijの計算方法について説明する。ここでは、例として、上述のように、トピック総数ｃ＝４の分類トピック集合Ｔ＝｛Ｔ1，Ｔ2，Ｔ3，Ｔ4｝とし、Ｔ1が「国際」、Ｔ2が「政治」、Ｔ3が「経済」、Ｔ4が「スポーツ」をあらわすとする。また、訓練データ数ＤをＤ＝３とし、訓練データｙ1〜ｙ3を以下の通りとする。
【００５４】
ｙ1＝｛０，１，１，０｝
ｙ2＝｛１，１，０，０｝
ｙ3＝｛０，１，１，１｝
【００５５】
ｃ＝４であるため、トピック共起行列Ｋは４行４列の行列となる。ここで、各行列要素Ｋijの算出例を列挙する。
【００５６】
Ｋ12＝Ｋ21＝（２×１）／（１＋３）＝１／２
Ｋ13＝Ｋ31＝（２×０）／（１＋２）＝０
Ｋ14＝Ｋ41＝（２×０）／（１＋１）＝０
Ｋ23＝Ｋ32＝（２×２）／（３＋２）＝４／５
Ｋ24＝Ｋ42＝（２×１）／（３＋１）＝１／２
Ｋ34＝Ｋ43＝（２×１）／（２＋１）＝２／３
【００５７】
また、行列要素Ｋij中、対角項Ｋiiは共起情報から決定することはできないが、トピック共起行列Ｋがカーネル行列であるという要請、つまり正定値性を満たす条件から、下記式（３），（４）のように決めることができる。
【００５８】
【数３】
2008276344.tif 000005
【００５９】
行列Ｌ，Ｋの対角成分はよく知られている正定値対称行列のCholeskey分解アルゴリズムから決めることができる。ここで、行列Ｌの対角成分でＬii＝１であるという仮定を置いた。これは、任意のトピック共起行列が正定値性を満たし、行列Ｋの非対角成分が小さい時、Ｋは単位行列にほぼ同じであるという要請を考慮したものである。
【００６０】
また、設定部２１４は、算出部２１３によって算出されたトピック共起カーネルに基づいて、未分類データ２０２の多重トピック分類に用いる重みベクトルを設定する機能を有する。具体的には、上述したトピック共起行列Ｋを用いて重みベクトルｗKを算出する。重みベクトルｗKは下記式（５）により算出される。
【００６１】
【数４】
2008276344.tif 000006
【００６２】
上記式（５）において、ｍはｍ＝１，…，ｃであり、訓練データｙd内のｍ番目の成分をあらわす。すなわち、ｙ’dmは、訓練データｙd内のｍ番目の成分を反転させたバイナリベクトルであり、訓練データｙdの不正解ベクトルをあらわす。たとえば、訓練データｙ1＝｛０，１，１，０｝の不正解ベクトルｙ’dmは、以下のとおりである。
【００６３】
ｙ’d1＝｛１，１，１，０｝
ｙ’d2＝｛０，０，１，０｝
ｙ’d3＝｛０，１，０，０｝
ｙ’d4＝｛０，１，１，１｝
【００６４】
また、上記式（５）で、αdmは、下記式（６）〜（８）に示すマージン最適化多重ラベリング学習の最適化問題（双対問題表示）として定式化された公知の式の解の非ゼロ要素である。
【００６５】
【数５】
2008276344.tif 000007
【００６６】
また、｜,｜Kは、トピックのなす空間で内積としてトピック共起カーネルＫを使用したベクトルの長さをあらわす。
【００６７】
この重みベクトルｗKにより、通常の線形カーネルでは考慮できない、トピック間の相関を考慮しつつ、線形カーネルと同じく高速な分類処理速度を実現できる。分類時には、各事例のノルムに従うスコアの正規化処理がマルチトピック分類器には必要となる。それを含めた分類処理の詳細については後述する。
【００６８】
なお、上記式（６）〜（８）に示した最適化問題は２次計画問題であり、様々な効率的な解法アルゴリズムが存在する。しかし、多重トピック文書分類の場合、最適化する変数の個数は文書数×トピック数と大きくなり、通常はＳＶＭの場合と同じく一般的な解法アルゴリズムの適用が難しくなる。そこで、ＳＶＭのSequential Mimimum Optimization（ＳＭＯ）アルゴリズムを上記式（６）〜（８）式の最適化問題に拡張した解法アルゴリズムを本実施の形態で適用することができる。
【００６９】
ＳＶＭのＳＭＯアルゴリズムは最急降下法を基本とする反復解法の１つである。各反復で、最も目的関数を下げる２変数を選択しその変数のみを更新していく。ＳＶＭの場合には等式制約式が１つあるために、自由に更新できる最小の変数である２変数を選択し逐次更新していくが、本実施の形態の多重トピック分類の場合には、等式制約式がないため１変数を選択して更新していく拡張ＳＭＯアルゴリズムを使用する。
【００７０】
（１）拡張ＳＭＯアルゴリズムでは、まず、誤差定数ＥＰＳに正の定数を設定し、すべてのαdmを初期化（αdm＝０）する。
（２）つぎに、下記式（９）に示すバイオレーション値ｖdmが最大となる(ｄ，ｍ）を選択する。これは各訓練データの各反復数時での分類誤りを示している。
【００７１】
【数６】
2008276344.tif 000008
【００７２】
（３）そして、ｖdm＜ＥＰＳを満たしていれば終了、そうでなければ次の（４）へ移行する。（４）上記（２）で選択された(ｄ，ｍ）により特定されるαdmを、下記式（１０）により更新する。
【００７３】
【数７】
2008276344.tif 000009
【００７４】
（５）そして、αdmの更新に伴ってｖdmを更新して、上記（１）にもどる。学習処理部２１０による学習処理時は、αdmの更新に伴って、全訓練データに対するviolation値ｖdmの更新処理が発生する。その際に（１０）式によってカーネル計算を行う必要あるため、そのままの実装では学習時間は膨大となる。ＳＶＭのＳＭＯアルゴリズムと同じようにカーネル関数値のキャッシュを保持することで学習処理時間の短縮化を図ることができる。
【００７５】
つぎに、分類処理部２２０について説明する。図２において、分類処理部２２０は、学習処理部２１０により得られた重みベクトルを用いて未分類データ２０２を分類する機能を有し、具体的には、取得部２１１と生成部２１２と分類部２２１と出力部２２２とをから構成される。
【００７６】
取得部２１１は、分類処理部２２０においては、未分類データ２０２を取得する機能を有する。ここで、未分類データ２０２とは、トピックがまだ付与されていない電子データであり、たとえば、論文、図書、新聞、雑誌、漫画、小説などの電子文書が挙げられる。取得部２１１は、多重トピック分類装置２００の外部から与えられた分類対象または内部に保持されている分類済みデータ２０１を読み込む。
【００７７】
生成部２１２は、分類処理部２２０においては、取得部２１１によって取得された未分類データ２０２の素性ベクトルｘ＝｛ｘ1，…，ｘN｝を生成する機能を有する。素性ベクトルｘは未分類データ２０２の属性をあらわすベクトルである。たとえば、未分類データ２０２が電子文書である場合、単語（Ｎ個）ごとの出現頻度をベクトル化する、いわゆるbag-of-word表現により、素性ベクトルｘを生成する。この場合、ｘ1，…，ｘNは、電子文書内に出現するＮ個の単語の出現頻度となる。
【００７８】
また、図２において、分類部２２１は、未分類データ２０２の多重トピック分類を実行する機能を有する。具体的には、未分類データ２０２の素性ベクトルと重みベクトルとに基づいて、未分類データ２０２の多重トピック分類を実行する。
【００７９】
また、出力部２２２は、分類結果となるバイナリベクトルを出力する機能を有する。具体的には、たとえば、バイナリベクトルのみ出力したり、未分類データ２０２に関連付けて出力する。出力形式は、画面表示や印刷出力、記憶領域への格納、他のコンピュータ装置への送信が挙げられる。
【００８０】
（学習処理手順）
つぎに、この発明の実施の形態にかかる学習処理手順について説明する。図３は、この発明の実施の形態にかかる学習処理手順を示すフローチャートである。図３において、まず、取得部２１１により、分類済みデータ２０１とその訓練データセットを取得する（ステップＳ３０１）。
【００８１】
つぎに、生成部２１２により、分類済みデータ２０１の素性ベクトルｘを生成する（ステップＳ３０２）。そして、算出部２１３によりトピック共起行列Ｋを算出する（ステップＳ３０３）。このあと、設定部２１４により、重みベクトル設定処理を実行する（ステップＳ３０４）。これにより、一連の学習処理手順を終了する。
【００８２】
つぎに、重みベクトル設定処理（ステップＳ３０４）の詳細な処理手順について説明する。図４は、重みベクトル設定処理（ステップＳ３０４）の詳細な処理手順を示すフローチャートである。
【００８３】
まず、訓練データｙdのインデックスｄをｄ＝１とし（ステップＳ４０１）、ｍ（訓練データｙd内のｍ番目の成分をあらわすインデックス）をｍ＝１とする（ステップＳ４０２）。そして、上記式（５）のＡdmを算出する（ステップＳ４０３）。つぎに、ｍ＞ｃであるか否かを判断する（ステップＳ４０４）。ｍ＞ｃでない場合（ステップＳ４０４：Ｎｏ）、ｍをインクリメントして（ステップＳ４０５）、ステップＳ４０３に戻る。
【００８４】
一方、ｍ＞ｃである場合（ステップＳ４０４：Ｙｅｓ）、ｄ＞Ｄ（Ｄは訓練データｙdの総数）であるか否かを判断する（ステップＳ４０６）。ｄ＞Ｄでない場合（ステップＳ４０６：Ｎｏ）、ｄをインクリメントして（ステップＳ４０７）、ステップＳ４０３に戻る。一方、ｄ＞Ｄである場合（ステップＳ４０６：Ｙｅｓ）、上記式（５）により重みベクトルｗKを算出して（ステップＳ４０８）、一連の処理を終了する。
【００８５】
（分類処理手順）
つぎに、この発明の実施の形態にかかる分類処理手順について説明する。図５は、この発明の実施の形態にかかる分類処理手順を示すフローチャートである。図５において、まず、取得部２１１により、未分類データ２０２を取得する（ステップＳ５０１）。つぎに、生成部２１２により、未分類データ２０２の素性ベクトルｘを生成する（ステップＳ５０２）。そして、単独トピック分類実行処理（ステップＳ５０３）および多重トピック分類実行処理（ステップＳ５０４）をおこなう。最後に、出力部２２２により、分類結果を出力することにより（ステップＳ５０５）、一連の処理を終了する。
【００８６】
つぎに、単独トピック分類実行処理（ステップＳ５０３）の詳細な処理手順について説明する。図６は、単独トピック分類実行処理の詳細な処理手順を示すフローチャートである。図６において、まず、ｉ（ｉ番目のトピックＴｉを特定するインデックス）をｉ＝１とし（ステップＳ６０１）、単独トピックベクトルｙｉを生成する（ステップＳ６０２）。単独トピックベクトルｙiは、ｉ番目のトピックＴiの値ｔiのみがｔi＝１となるバイナリベクトルである。
【００８７】
つぎに、単独トピックスコアＳiを算出する（ステップＳ６０３）。単独トピックスコアＳiは、下記式（１１）により算出される。
【００８８】
【数８】
2008276344.tif 000010
【００８９】
なお、｜ｙi｜Kは単独トピックの長さである。そして、ｉ＞ｃであるか否かを判断する（ステップＳ６０４）。すなわち、すべての単独トピックに対して単独トピックスコアＳiを算出したか否かを判断する。ｉ＞ｃでない場合（ステップＳ６０５：Ｎｏ）、ｉをインクリメントして（ステップＳ６０６）、ステップＳ６０２に戻る。
【００９０】
一方、ｉ＞ｃである場合（ステップＳ６０４：Ｙｅｓ）、これまでに算出された単独トピックスコアＳ1〜ＳCを降順にソートする（ステップＳ６０５）。そして、その中から最大スコアＳmaxを保持して（ステップＳ６０７）、ステップＳ５０４に移行する。
【００９１】
つぎに、多重トピック分類実行処理（ステップＳ５０４）の詳細な処理手順について説明する。図６は、多重トピック分類実行処理（ステップＳ５０４）の詳細な処理手順を示すフローチャートである。図６において、まず、ｇ＝２とする（ステップＳ７０１）。ｇは、ステップＳ６０５においてソートされた降順をあらわす。なお、ｇ＝１の場合、単独トピックスコアＳmaxの算出元となる単独トピックべクトルである。
【００９２】
つぎに、多重トピックベクトルｚgを生成する（ステップＳ６０２）。多重トピックベクトルｚgとは、上位２番目の単独トピックスコアの算出元の単独トピックベクトルから上位ｇ番目までの単独トピックスコアの算出元の単独トピックベクトルの論理和である。
【００９３】
たとえば、ｇ＝４とした場合、上位２番目の単独トピックスコアの算出元の単独トピックベクトルｙAから上位３番目の単独トピックスコアの算出元の単独トピックベクトルｙCを以下の通りとすると、多重トピックベクトルｚ4は以下の通りとなる。
【００９４】
ｙA＝｛１，０，０，０｝
ｙB＝｛０，０，１，０｝
ｙC＝｛０，０，０，１｝
ｚ4＝｛１，０，１，１｝
【００９５】
そして、多重トピックスコアＭgを算出する（ステップＳ７０３）。多重トピックスコアＭgは、下記式（１２）により算出される。
【００９６】
【数９】
2008276344.tif 000011
【００９７】
なお、｜ｚg｜Kは多重トピックの長さである。多重トピックスコアＭgは線形カーネルであるため、多重トピックの長さ｜ｚg｜Kの正規化項を除いて、多重トピックスコアＭgは単独トピックスコアＳ1×｜ｙ1｜K〜ＳC×｜ｙc｜Kの和になっている。そのため、多重トピックに対するスコア計算には、一般のNaive Bayes分類器や、一対他方式のＳＶＭなどと同じ単独トピックに対する計算コストと、トピック素性空間での多重トピックの長さによる正規化計算コストとなり、比較的高速に分類を実行できる。
【００９８】
このあと、Ｍg＞Ｓmaxであるか否かを判断する（ステップＳ７０４）。Ｍg＞Ｓmaxである場合（ステップＳ７０４：Ｙｅｓ）、ｇ＞ｃであるか否かを判断する（ステップＳ７０５）。そして、ｇ＞ｃでない場合（ステップＳ７０５：Ｎｏ）、ｇをインクリメントして（ステップＳ７０６）、ステップＳ７０２に戻る。
【００９９】
一方、ｇ＞ｃである場合（ステップＳ７０５：Ｙｅｓ）、最終的に得られた多重トピック訓練データｚgを保持する（ステップＳ７０７）。一方、ステップＳ７０４において、Ｍg＞Ｓmaxでない場合（ステップＳ７０４：Ｎｏ）、１つ前の多重トピック訓練データｚg-1を保持する（ステップＳ７０８）。このあと、ステップＳ５０５に移行することで、多重トピック分類実行処理（ステップＳ５０４）の一連の処理を終了する。
【０１００】
このように、この発明の実施の形態によれば、カーネルにより相関の強いトピック対と語彙素性との関連をより強く学習することができ、トピック数の大きい場合のトピックＦ１値性能を向上させることができる。また、このトピック共起カーネルは非対角項を持つ線形カーネルとして表現できるため、分類時に明示的に重みベクトルを構成することができる。そのため、分類時にもカーネル関数を使用する場合に比べて高速な分類を実現することができる。
【０１０１】
なお、本実施の形態で説明した多重トピック分類方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な伝送媒体であってもよい。
【産業上の利用可能性】
【０１０２】
以上のように、本発明にかかる多重トピック分類装置、多重トピック分類方法、および多重トピック分類プログラムは、各種電子文書やソーシャルブックマークなどに有用である。
【図面の簡単な説明】
【０１０３】
【図１】この発明の実施の形態にかかる多重トピック分類装置のハードウェア構成を示すブロック図である。
【図２】この発明の実施の形態にかかる多重トピック分類装置の機能的構成を示すブロック図である。
【図３】この発明の実施の形態にかかる学習処理手順を示すフローチャートである。
【図４】重みベクトル設定処理の詳細な処理手順を示すフローチャートである。
【図５】この発明の実施の形態にかかる分類処理手順を示すフローチャートである。
【図６】単独トピック分類実行処理の詳細な処理手順を示すフローチャートである。
【図７】多重トピック分類実行処理の詳細な処理手順を示すフローチャートである。
【符号の説明】
【０１０４】
２００  多重トピック分類装置
２１０  学習処理部
２１１  取得部
２１２  生成部
２１３  算出部
２１４  設定部
２２０  分類処理部
２２１  分類部
２２２  出力部
【図１】
2008276344.tif 000012
【図２】
2008276344.tif 000013
【図３】
2008276344.tif 000014
【図４】
2008276344.tif 000015
【図５】
2008276344.tif 000016
【図６】
2008276344.tif 000017
【図７】
2008276344.tif 000018