説明

トランスダクティブデータ分類のための方法およびシステム、ならびに機械学習手法を用いたデータ分類方法

データを分類するためのシステム、方法、データ処理装置、および製品が提供される。機械学習手法を用いたデータ分類方法がまた、開示される。該データ分類方法の一実施形態は、ラベル付きデータ点を受信するステップと、ラベルなしデータ点を受信するステップと、該ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因を受信するステップと、該少なくとも1つのコスト要因ならびに該ラベル付きデータ点および該ラベルなしデータ点を訓練例として、最大エントロピー識別を用いてトランスダクティブ分類器を訓練するステップと、該ラベルなしデータ点、該ラベル付きデータ点、および入力データ点の少なくとも1つを分類するために訓練された分類器を適用するステップと、分類されたデータ点の分類、またはその派生物を出力するステップと、を含む。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、全体としてデータ分類のための方法および装置に関する。より詳細には、本発明は、改良されたトランスダクティブ機械学習法を提供する。本発明はまた、機械学習手法を用いた新規なアプリケーションにも関する。
【背景技術】
【0002】
データを処理する方法は、情報化時代において重要性を増しており、より最近では、とりわけ、スキャンした文書、ウェブ材料、検索エンジンデータ、文字データ、画像、音声データファイル等を含む、あらゆる生活分野における電子データの急増と共に、その重要性を増してきている。
【0003】
探究が始まったばかりの1つの分野は、データの非手動分類である。多くの分類法において、機械またはコンピュータは、手作業で入力され生成されたルールセットおよび/または手作業で生成された訓練例に基づいて学習しなければならない。訓練例が用いられる機械学習では、学習例の数は、推定する必要のあるパラメータの数と比較して少ないことが一般的である。すなわち、訓練例によって与えられる制約を満たす解の数が多いということである。機械学習の課題は、制約の不足にもかかわらず十分に汎用化する解を求めることである。従って、従来技術と関連するこれらのおよび/または他の問題を克服する必要がある。
【0004】
さらに必要とされることは、あらゆる種類の機械学習手法のための実用的なアプリケーションである。
【発明の開示】
【課題を解決するための手段】
【0005】
コンピュータベースのシステムでは、本発明の一実施形態によるデータの分類手法は、ラベル付きデータ点が指定されたカテゴリに含まれるべきデータ点の訓練例であるのか、あるいは指定されたカテゴリから除外されたデータ点の訓練例であるかを示す少なくとも1つのラベルを各々が有するラベル付きデータ点を受信するステップと、ラベルなしデータ点を受信するステップと、ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因を受信するステップと、少なくとも1つのコスト要因と、ラベル付きデータ点と、ラベルなしデータ点とを訓練例として用い、繰り返し計算によって、最大エントロピー識別法(MED)を用いてトランスダクティブ分類器を訓練するステップであって、計算の各繰り返しに対して、ラベルなしデータ点のコスト要因は期待ラベル値の関数として調整され、データ点ラベルの事前確率はデータ点のクラス帰属確率の推定に基づいて調整されるステップと、訓練された分類器を適用して、ラベルなしデータ点、ラベル付きデータ点、および入力データ点のうちの少なくとも1つを分類するステップと、分類されたデータ点の分類、またはその派生物を、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力するステップとを含む。
【0006】
本発明の別の実施形態によるデータの分類方法は、コンピュータ上に配備して実行されることになるコンピュータ実行可能プログラムコードを準備するステップを含む。このプログラムコードは、データ点が指定されたカテゴリに含まれるべきデータ点の訓練例であるのか、あるいは指定されたカテゴリから除外されたデータ点の訓練例であるのかを示す少なくとも1つのラベルを各々が有する、コンピュータのメモリ内の格納されたラベル付きデータ点にアクセスする命令と、コンピュータのメモリからラベルなしデータ点にアクセスする命令と、コンピュータのメモリからラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因にアクセスする命令と、計算の各繰り返しに対して、ラベルなしデータ点のコスト要因が期待ラベル値の関数として調整され、データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に応じて調整される、少なくとも1つの格納されたコスト要因と、格納されたラベル付きデータ点と、ラベルなしデータ点とを訓練例として用いる繰り返し計算によって、最大エントロピー識別(MED)トランスダクティブ分類器を訓練する命令と、ラベルなしデータ点、ラベル付きデータ点、および入力データ点のうちの少なくとも1つを分類するために、訓練された分類器を適用する命令と、分類されたデータ点の分類、またはその派生物を、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力するための命令と、を備える。
【0007】
本発明の別の実施形態によるデータ処理装置は、(i)データ点が指定されたカテゴリに含まれているデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されているデータ点に対する訓練例であるのかを示す少なくとも1つのラベルを各々が有するラベル付きデータ点と、(ii)ラベルなしデータ点と、(iii)ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因と、を格納するための少なくとも1つのメモリと、少なくとも1つの格納されたコスト要因ならびに格納されたラベル付きデータ点および格納されたラベルなしデータ点を訓練例として用い、トランスダクティブ最大エントロピー識別(MED)を用いてトランスダクティブ分類器に繰り返し教示するためのトランスダクティブ分類器訓練装置とを含む。MED計算の各繰り返し時に、ラベルなしデータ点のコスト要因が期待ラベル値の関数として調整され、データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に応じて調整され、トランスダクティブ分類器訓練装置によって訓練された分類器を用いて、ラベルなしデータ点、ラベル付きデータ点、および入力データ点のうちの少なくとも1つが分類され、分類されたデータ点、またはその派生物は、ユーザ、別のシステム、別のステップのうちの少なくとも1つに出力される。
【0008】
本発明の別の実施形態による製品は、コンピュータ可読のプログラム格納媒体を備えており、該媒体は、データ点が指定されたカテゴリに含まれるべきデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されているデータ点に対する訓練例であるのかを示す少なくとも1つのラベルを各々が有するラベル付きデータ点を受信するステップと、ラベルなしデータ点を受信するステップと、ラベルなしデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因を受信するステップと、MED計算の各繰り返し時に、ラベルなしデータ点のコスト要因が期待ラベル値の関数として調整され、データ点の事前確率がデータ点のクラス帰属確率の推定値に応じて調整される、少なくとも1つの格納されたコスト要因ならびに格納されたラベル付きデータ点および格納されたラベルなしデータ点を用いて、繰り返し最大エントロピー識別(MED)によってトランスダクティブ分類器を訓練するステップと、訓練された分類器を適用して、ラベルなしデータ点、ラベル付きデータ点、および入力データ点のうちの少なくとも1つを分類するステップと、分類されたデータ点の分類、またはその派生物を、ユーザ、別のシステム、および別のステップのうちの少なくとも1つに出力するステップとを包含する、分類法を実行するためのコンピュータによって実行可能な命令からなる1つ以上のプログラムを明白に具体化している。
【0009】
コンピュータベースのシステムでは、本発明の別の実施形態によるラベルなしデータを分類する方法は、データ点が指定されたカテゴリに含まれるべきデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されているデータ点に対する訓練例であるのかを示す少なくとも1つのラベルを各々が有するラベル付きデータ点を受信するステップと、ラベル付きおよびラベルなしデータ点を受信するステップと、ラベル付きデータ点およびラベルなしデータ点の事前ラベル確率を受信するステップと、ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因を受信するステップと、データ点のラベルの事前確率に基づいて各ラベル付きおよびラベルなしデータ点に対する期待ラベルを決定するステップと、データ値がほぼ収束するまで、以下の下位ステップ、すなわち、
・データ点の期待ラベルの絶対値に比例して各ラベルなしデータ点に対するスケーリングされたコスト値を生成するステップと、
・ラベル付きおよびラベルなしデータをそれらの期待ラベルに従って訓練例として用い、含まれた訓練例および除外された訓練例を与えられた決定関数パラメータの事前確率分布に対してKLダイバージェンスを最小化する決定関数を決定することによって、分類器を訓練するステップと、
・訓練された分類器を用いて、ラベル付きおよびラベルなしデータ点の分類スコアを決定するステップと、
・訓練された分類器の出力をクラス帰属確率に対して較正するステップと、
・決定されたクラス帰属確率に従って、ラベルなしデータ点のラベルの事前確率を更新するステップと、
・更新されたラベルの事前確率および先に決定された分類スコアを用い、最大エントロピー識別(MED)を用いて、ラベルおよびマージンの確率分布を決定するステップと、
・先に決定されたラベルの確率分布を用いて、新たな期待ラベルを計算するステップと、
・前回の繰り返しにより得た期待ラベルと共に新たな期待ラベルを組み込むことによって、各データ点に対する期待ラベルを更新するステップと、
を繰り返すステップと、を含む。
入力データ点の分類、またはその派生物は、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力される。
【0010】
本発明の別の実施形態による文書を分類する方法は、ラベル割り当てに関して既知の信頼水準を有する少なくとも1つのラベル付きシード文書を受信するステップと、ラベルなし文書を受信するステップと、少なくとも1つの所定コスト要因を受信するステップと、計算の各繰り返しに対して期待ラベル値の関数として調整される少なくとも1つの所定コスト要因、少なくとも1つのシード文書、およびラベルなし文書を用い、繰り返し計算によってトランスダクティブ分類器を訓練するステップと、少なくともある程度の繰り返しの後に、ラベルなし文書に対する信頼スコアを格納するステップと、最も高い信頼スコアを有するラベルなし文書の識別子を、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力するステップと、を含む。
【0011】
本発明の別の実施形態による、法的開示手続(discovery)と関連する文書を分析する方法は、法的事項と関連する文書を受信するステップと、該文書に関して文書分類手法を実行するステップと、該文書の分類に基づいて、文書のうちの少なくとも一部の識別子を出力するステップと、を含む。
【0012】
本発明の別の実施形態によるデータを整理する方法は、複数のラベル付きデータ項目を受信するステップと、複数のカテゴリの各々に対して、複数のカテゴリの各々に対するデータ項目のサブセットを選択するステップと、各サブセット内のデータ項目に対する不確実性をほぼゼロに設定するステップと、サブセット内に存在しないデータ項目に対する不確実性をほぼゼロではない所定値に設定するステップと、不確実性、サブセット内のデータ項目、およびサブセット内に存在しないデータ項目を訓練例として用い、繰り返し計算によってトランスダクティブ分類器を訓練するステップと、データ項目の各々を分類するために、訓練された分類器をラベル付きデータ項目の各々に適用するステップと、入力データ項目の分類またはその派生物を、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力するステップと、を含む。
【0013】
本発明の別の実施形態によるインボイスと実体との関連を検証する方法は、第1の実体と関連するインボイスの形式に基づいて分類器を訓練するステップと、第1の実体および他の実体のうちの少なくとも1つと関連する旨のラベルが付けられた複数のインボイスにアクセスするステップと、分類器を用いて、インボイスに関して文書分類手法を実行するステップと、第1の実体と関連していない確率が高いインボイスのうちの少なくとも1つの識別子を出力するステップと、を含む。
【0014】
本発明の別の実施形態による医療記録を管理する方法は、医学的診断に基づいて分類器を訓練するステップと、複数の医療記録にアクセスするステップと、分類器を用い、医療記録に関して文書分類を実行するステップと、医学的診断と関連している確率が低い医療記録のうちの少なくとも1つの識別子を出力するステップと、を含む。
【0015】
本発明の別の実施形態による顔認識方法は、既知の信頼水準を有する少なくとも1つのラベル付きの顔のシード画像を受信するステップと、ラベルなし画像を受信するステップと、少なくとも1つの所定コスト要因を受信するステップと、少なくとも1つの所定コスト要因、少なくとも1つのシード画像、およびラベルなし画像を用い、各々に対してコスト要因が期待ラベル値の関数として調整される繰り返し計算によってトランスダクティブ分類器を訓練するステップと、少なくともある程度の繰り返しの後に、ラベルなしシード画像に対する信頼スコアを格納するステップと、最も高い信頼スコアを有するラベルなし画像の識別子を、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力するステップと、を含む。
【0016】
本発明の別の実施形態による従来技術文書を分析する方法は、検索クエリに基づいて分類器を訓練するステップと、複数の先行技術文書にアクセスするステップと、分類器を用いて、従来技術文書のうちの少なくともいくつかに関して文書分類手法を実行するステップと、従来技術文書の分類に基づいて、文書のうちの少なくとも一部の識別子を出力するステップと、を含む。
【0017】
本発明の別の実施形態による文書内容のシフトに特許分類を順応させる方法は、少なくとも1つのラベル付きシード文書を受信するステップと、ラベルなし文書を受信するステップと、少なくとも1つのシード文書およびラベルなし文書を用いてトランスダクティブ分類器を訓練するステップと、分類器を用いて、所定の閾値を上回る信頼水準を有するラベルなし文書を複数の既存のカテゴリに分類するステップと、分類器を用いて、所定の閾値を下回る信頼水準を有するラベルなし文書を少なくとも1つの新たなカテゴリに分類するステップと、分類器を用いて、カテゴライズされた文書のうちの少なくとも一部を既存のカテゴリおよび少なくとも1つの新たなカテゴリに再分類するステップと、カテゴライズされた文書の識別子を、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力するステップと、を含む。
【0018】
本発明の別の実施形態による、文書を請求項にマッチングする方法は、特許文書または特許出願書類の少なくとも1つの請求項に基づいて、分類器を訓練するステップと、複数の文書にアクセスするステップと、分類器を用いて、文書のうちの少なくとも一部に関して文書分類手法を実行するステップと、文書の分類に基づいて、文書のうちの少なくとも一部の識別子を出力するステップと、を含む。
【0019】
本発明の別の実施形態による特許文書または特許出願書類を分類する方法は、特定の特許分類に存在することが分かっている複数の文書に基づいて分類器を訓練するステップと、特許文書または特許出願書類の少なくとも一部を受信するステップと、分類器を用いて、特許文書または特許出願書類の少なくとも一部に関して文書分類手法を実行するステップと、特許文書または特許出願書類の分類を出力するステップと、を含み、文書分類手法は、はい/いいえ式分類手法である。
【0020】
本発明の別の実施形態による特許文書または特許出願書類を分類する方法は、特定の特許分類と関連する少なくとも1つの文書に基づいて訓練された分類器を用い、特許文書または特許出願書類の少なくとも一部に関して、はい/いいえ式分類手法である文書分類手法を実行するステップと、特許文書または特許出願書類の分類を出力するステップと、を含む。
【0021】
本発明の別の実施形態による文書内容のシフトに順応する方法は、少なくとも1つのラベル付きシード文書を受信するステップと、ラベルなし文書を受信するステップと、少なくとも1つの所定コスト要因を受信するステップと、少なくとも1つの所定コスト要因、少なくとも1つのシード文書、およびラベルなし文書を用いてトランスダクティブ分類器を訓練するステップと、分類器を用いて、所定の閾値を上回る信頼水準を有するラベルなし文書を複数のカテゴリに分類するステップと、分類器を用いて、カテゴライズされた文書のうちの少なくとも一部をカテゴリに再分類するステップと、カテゴライズされた文書の識別子を、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力するステップと、を含む。
【0022】
本発明の別の実施形態による文書を分離する方法は、ラベル付きデータを受信するステップと、一連のラベルなし文書を受信するステップと、ラベル付きデータおよびラベルなし文書に基づくトランスダクションを用いて、確率的分類規則を順応させるステップと、確率的分類規則に従って文書分類用に用いられる重みを更新するステップと、一連の文書における分離位置を決定するステップと、決定された連なりにおける分離位置の標識を、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力するステップと、標識と相関するコードのフラグを文書に立てるステップと、を含む。
【0023】
本発明の別の実施形態による文書検索方法は、検索クエリを受信するステップと、検索クエリに基づいて文書を取り出すステップと、文書を出力するステップと、文書のうちの少なくとも1つに対する、検索クエリとの文書の関連性を示すユーザ入力ラベルを受信するステップと、検索クエリおよびユーザ入力ラベルに基づいて分類器を訓練するステップと、文書を再分類するために、分類器を用いて、文書に関して文書分類手法を実行するステップと、文書の分類に基づいて、文書のうちの少なくとも一部の識別子を出力するステップと、を含む。
【発明を実施するための最良の形態】
【0024】
以下の記述は、本発明を実施するために現在企図される最良の形態である。この記述は、本発明の一般的原理を説明する目的でなされるものであり、本明細書において主張される発明の概念を制限することを意図するものではない。さらに、本明細書において記述される特定の特徴は、記述される他の特徴と、種々の可能な組み合わせおよび順列の各々において、組み合わせて用いられ得る。
【0025】
本明細書において別途具体的に定義しない限り、すべての用語は、本明細書によりもたらされる意味、および当業者によって理解され、また辞書、専門書などに定義される意味を含んで、それらの用語に可能な限りの最も幅広い解釈を与えられる。
【0026】
(文字分類)
文字データの分類に対する関心および必要性は特に強く、いくつかの分類手法が採用されてきた。以下に、文字データの分類法について検討する。
【0027】
分類法の有用性および知能を向上させるために、例えばコンピュータのような機械が、常に増加し続ける内容に対象を分類する(または認識する)ために必要とされる。例えば、コンピュータは、光学式文字認識を用いて、手書きまたはスキャンした数字および文字を分類することができ、パターン認識を用いて、顔、指紋、戦闘機などのような画像を分類することができ、あるいは、音声認識を用いて、音、声などを分類することができる。
【0028】
機械は、例えば文字からなるコンピュータファイルまたは文書のような文字情報オブジェクトを分類するためにも必要とされてきた。文字分類用アプリケーションは様々であり、かつ重要である。例えば、文字分類は、文字情報オブジェクトを、例えば所定のクラスまたはカテゴリの階層構造に編成するために、使用され得る。この手法で、特定の主題に関連する文字情報オブジェクトの発見(またはそれへのナビゲーション)が簡易化される。文字分類は、文字情報オブジェクトを、しかるべき人々または場所に送るために使用され得る。この手法で、情報サービス産業は、多岐にわたる主題(例えば、ビジネス、スポーツ、株式市場、フットボール、特定の会社、特定のフットボールチーム)をカバーする文字情報オブジェクトを、様々な関心を有する人々に送ることができる。文字分類は、望まない文字内容(ジャンクメール、または「スパム」とも呼ばれる望まない未承諾メールのような)によって個人が迷惑を被らないように、文字情報オブジェクトにフィルタをかけるために使用され得る。これら少数の例から分かるように、文字分類に対する多くの魅力的かつ重要な用途がある。
【0029】
(ルールベースの分類)
一部の場合には、文字内容は、特定の承認された論理に基づき、絶対的確実性をもって分類される必要がある。ルールベースシステムは、そのような種類の分類を行うために使用され得る。基本的に、ルールベースシステムは、次の形の生成規則を用い:
もし、(条件)であれば、(事実)である。
ここで条件は、文字情報が特定の語または語句を含むか否か、特定の構文を有するか否か、または特定の属性を有するか否かを、含み得る。例えば、文字内容が語「終える」、語句「ナスダック」および数を有する場合には、それは「株式市場」に関する文字に分類される。
【0030】
この10年間ほどの間に、他の種類の分類器が次第に用いられるようになってきた。これらの分類器は、ルールベースの分類器のように静的で事前定義された論理を用いるものではないが、それらは、多くのアプリケーションにおいて、ルールベース分類器を上回る性能を示してきた。このような分類器は通常、学習要素と実行要素とを含む。このような分類器は、ニューラルネットワークと、ベイジアン(Bayesian)ネットワークと、サポートベクタマシンとを含み得る。これらの分類器の各々が公知であるが、読者の便宜のために、各々を以下に簡単に紹介する。
【0031】
(学習要素および実行要素を有する分類器)
前節末でちょうど言及したとおり、学習要素および実行要素を有する分類器は、多くのアプリケーションにおいて、ルールベース分類器を上回る性能を有する。繰り返して述べると、これらの分類器は、ニューラルネットワークと、ベイジアンネットワークと、サポートベクタマシンとを含み得る。
【0032】
(ニューラルネットワーク)
ニューラルネットワークは、基本的に、ニューロンとも呼ばれる同一の処理要素の多層にわたる階層的な配列である。各ニューロンは、1つ以上の入力を有し得るが、出力はひとつだけである。各ニューロン入力は、係数によって重み付けされる。ニューロンの出力は通常、重み付けされた入力の合計とバイアス値との関数である。活性化関数とも呼ばれるこの関数は、一般的にシグモイド関数である。すなわち、活性化関数は、S字状で、単調に増加し得、その入力(単数または複数)がそれぞれ正または負の無限大に近づくにつれて漸近的に固定値(例えば、+1、0、−1)に接近し得る。シグモイド関数と個々のニューラル重み付けおよびバイアス値が、入力信号に対するニューロンの応答または「敏感性」を決定する。
【0033】
ニューロンの階層的配列においては、1つの層におけるニューロンの出力は、次の層における1つ以上のニューロンへの入力として分配され得る。典型的なニューラルネットワークは、入力層と2つの別個の層、すなわち、入力層、中間ニューロン層、および出力ニューロン層を含み得る。入力層のノードはニューロンではないことに留意されたい。むしろ、入力層のノードは、1つだけの入力を有しており、基本的に、該入力を、無処理の状態で次の層の入力に供給する。例えば、ニューラルネットワークが20×15ピクセルアレイ内の数字を認識するために用いられる場合には、入力層は300ニューロン(すなわち、入力の各ピクセルに対して1つ)を有し得、出力アレイは、10ニューロン(すなわち、10個の数字の各々に対して1つ)を有し得る。
【0034】
ニューラルネットワークの使用法は、全体として、2つの連続する段階を含む。最初に、ネットワークが初期化され、既知の出力値(または分類)を有する既知の入力に関して訓練される。ひとたびニューラルネットワークが訓練されると、それは、次いで、未知入力を分類するために使用され得る。ニューラルネットワークは、ニューロンの重みおよびバイアスを一般的にガウス分布から生成されるランダム値に設定することによって、初期化され得る。次いで、既知の出力(または分類)を有する一連の入力を用いて、ニューラルネットワークが訓練される。訓練入力がニューラルネットワークに供給される際に、各個々の訓練パターンについてのニューラルネットワークの出力が既知の出力に近づくか、またはそれに一致するように、ニューロンの重みおよびバイアスの値が調整(例えば、既知の逆伝播法に従って)される。基本的に、重み空間における最急降下法(gradient descent)が、出力誤差を最小化するために用いられる。この手法で、連続的訓練入力を用いた学習は、重みおよびバイアスに対する局所最適解に向けて収束する。すなわち、重みおよびバイアスは、誤差を最小化するように調整される。
【0035】
実際には、このシステムは、通常は、最適解に収束する点に至るまで訓練されることはない。さもなければ、このシステムは「過度に訓練」され、その結果として、このシステムは訓練データに対して過度に特殊化されることになり、訓練集合内の入力とどこか異なる入力を分類することに、適さなくなり得る。従って、訓練期間中の様々な時点で、このシステムは一組の検証データを使用して試験される。検証セットを使用したこのシステムの性能がもはや向上しなくなったときに、訓練は中止される。
【0036】
ひとたび訓練が完了すれば、ニューラルネットワークは、訓練中に算出された重みおよびバイアスに基づいて、未知の入力を分類するために使用され得る。ニューラルネットワークが信頼性をもって未知の入力を分類できる場合には、出力層におけるニューロンの出力の1つは、他よりもはるかに高くなる。
【0037】
(ベイジアンネットワーク)
一般的に、ベイジアンネットワークは、データ(例えば特徴ベクトル入力)と予測(例えば分類)との間の中間段階のものとして、仮説を用いる。データを所与として、各仮説の確率(「P(hypo|data)」)が推定され得る。仮説の事後確率を用いて、仮説から予測が行われ、各々の仮説に関する個々の予測が重み付けされる。データDを所与とした場合の予測Xの確率は、
【0038】
【数1】

で表され、ここで、Hはi番目の仮説である。Dを所与とした場合のHの確率(P(H|D))を最大化する最も確からしい仮説は、最大事後仮説(または「HMAP」)と呼ばれ、
【0039】
【数2】

で表すことができる。
ベイズの定理を用いると、データDを所与とした場合の仮説H.sub.iの確率は、
【0040】
【数3】

で表すことができる。データDの確率は固定されたままである。従って、HMAPを求めるためには分子を最大化する必要がある。
【0041】
分子の第1項は、仮説をiをとしてそのデータが観測されたであろう確率を表す。第2項は、所与の仮説iに割り当てられた事前確率を表す。
【0042】
ベイジアンネットワークは、変数と、変数間の有向辺(directed edge)とを含んでおり、それによって有向非巡回(directed acyclic)グラフ(または「DAG」)を定義する。各変数は、相互排他的状態の任意の有限数をとることができる。親変数B、...B、を有する各変数Aに対して、確率テーブル(P(A|B...B)が添付されている。ベイジアンネットワークの構造は、各変数が、その親変数を所与とした場合、各変数の非子孫(non−descendant)とは条件付きで独立であるという仮定を、符号化している。
【0043】
ベイジアンネットワークの構造が既知であり、変数が観測可能であると仮定すれば、条件付き確率テーブルの集合のみを学習すればよい。これらのテーブルは、一組の学習例からもたらされる統計を用いて直接推定され得る。構造が既知であるが一部の変数が隠されている場合には、学習は、上に論じたニューラルネットワークの学習に類似している。
【0044】
簡単なベイジアンネットワークの一例を以下に紹介する。変数「MML」は、「私の芝生の水分」を表し得、「湿った」状態と「乾燥した」状態を有し得る。MML変数は、「雨」という親変数と「私のスプリンクラーが作動している」という親変数とを有し得、各々の親変数は「はい」の状態と「いいえ」の状態とを有する。別の変数「MNL」は、「私の隣人の芝生の水分」を表し得、「湿った」状態と「乾燥した」状態を有し得る。MNL変数は、「雨」という親変数を共有し得る。この例では、予測は、私の芝生が「湿っている」か、または「乾燥している」かであり得る。この予測は、仮説(i)「もし雨が降れば、私の芝生は確率(x)で湿るであろう」と、仮説(ii)「もし私のスプリンクラーが作動していたら、私の芝生は確率(x)で湿るであろう」とに依存し得る。雨が降ったという確率または私のスプリンクラーが作動していたという確率は、他の変数に依存し得る。例えば、もし私の隣人の芝生が湿っており、かつ隣人がスプリンクラーを持っていなければ、雨が降ったという可能性がより高くなる。
【0045】
上に論じたように、ベイジアンネットワークにおける条件付き確率テーブルは、ニューラルネットワークの場合のように訓練され得る。有用にも、予備的知識の提供を許容することによって、学習過程は短縮され得る。しかしながら、残念なことに、条件付き確率に対する事前確率は通常未知であり、その場合には、一様な事前確率が用いられる。
【0046】
本発明の一実施形態は、2つの基本機能、すなわち分類器用パラメータの生成と、文字情報オブジェクトのようなオブジェクトの分類とのうちの、少なくとも1つを実行し得る。
【0047】
基本的に、パラメータは、一組の訓練例に基づいて、分類器用に生成される。一組の訓練例から、一組の特徴ベクトルが生成され得る。一組の特徴ベクトルの特徴が縮約され得る。生成されるべきパラメータは、定義済みの単調(例えばシグモイド)関数および重みベクトルを含み得る。重みベクトルは、SVM訓練(または別の公知の手法)によって決定され得る。単調(例えば、シグモイド)関数は、最適化手法を用いて定義され得る。
【0048】
文字分類器は、重みベクトルと、定義済みの単調(例えば、シグモイド)関数とを含み得る。基本的に、本発明の文字分類器の出力は、
【0049】
【数4】

で表すことができる。ここで、
=カテゴリcに関する分類出力、
=カテゴリcと関連付けられた重みベクトルのパラメータ、
x=未知の文字情報オブジェクトに基づく(縮約)特徴ベクトル、であり、
AおよびBは、単調(例えばシグモイド)関数の調整パラメータである。
【0050】
式(2)からの出力の計算は、式(1)からの出力の計算よりも速い。
【0051】
分類されるべきオブジェクトの形に応じて、分類器は、(i)文字情報オブジェクトを特徴ベクトルに変換し、(ii)特徴ベクトルを縮約してより少ない要素を有する特徴ベクトルとする、ことができる。
【0052】
(トランスダクティブ機械学習)
商用の自動分類システムにおける現在の最先端手法は、ルールベースのものであるか、または帰納的機械学習、すなわち手動でラベルを付けた訓練例を用いる機械学習を利用している。いずれの手法も一般的に、トランスダクティブ法と比較して、多くの手作業による設定努力を必要とする。ルールベースシステムまたは帰納的手法によって提供される解は静的な解であり、それは、人手による努力なくしては、ドリフトする分類概念に順応することができない。
【0053】
帰納的機械学習は、特徴または関係を、トークン(すなわち、1つまたは少数の観測または経験)に基づいた種類に帰するために、または繰り返し起こるパターンの限られた観測に基づいて法則を定式化するために用いられる。帰納的機械学習は、一般規則を生成するための観測済み訓練例からの推論を含み、該一般規則はその後、試験例に適用される。
【0054】
特に、好適な実施形態は、トランスダクティブ機械学習手法を用いる。トランスダクティブ機械学習は、これらの不利点を被らない強力な手法である。
【0055】
トランスダクティブ機械手法は、ドリフトする分類概念に自動的に順応し、かつラベル付き訓練例を自動的に修正しながら、極めて小さい組のラベル付き訓練例から学習することができる。これらの利点が、トランスダクティブ機械学習を、多種多様な商用アプリケーション用の興味深くかつ価値ある手法としている。
【0056】
トランスダクション法は、データ内のパターンを学習する。ラベル付きデータからのみならず、ラベルなしデータからも学習することによって、それは帰納的学習の概念を拡張する。これにより、トランスダクション法は、ラベル付きデータ内では捕捉されないか、または部分的にしか捕捉されないパターンを学習することが可能となる。その結果として、ルールベースシステムまたは帰納的学習に基づくシステムとは対照的に、トランスダクション法は、動的に変化する環境に順応し得る。この能力によって、トランスダクション法が、文書の発見、データの整理、および、とりわけドリフトする分類概念への対処のために、用いられることを可能とする。
【0057】
以下は、サポートベクタマシン(SVM)による分類および最大エントロピー識別(MED)の枠組みを使用した、トランスダクティブ分類の一実施形態の説明である。
【0058】
(サポートベクタマシン)
サポートベクタマシン(SVM)は、文字分類に採用される1つの手法であり、このような手法は、正則化理論の概念を用いてあり得る解に制約を導入することによって、多数の解に関する問題点およびその結果生じる一般化の問題に対処する。例えば、2値のSVM分類器は、訓練データを適切に分離するすべての超平面から、解として、マージンを最大化する超平面を選択する。訓練データが適切に分類されるという制約下での最大マージン正規化は、一般化と記憶との間の適切なトレードオフを選択するという、前述の問題の学習に取り組む。訓練データ上の制約は該データを記憶するが、一方で、正規化が適切な一般化を確実なものとする。帰納的分類は、既知のラベルを有する訓練例から学習する、すなわち、すべての訓練例のクラス帰属が既知である。帰納的分類は既知のラベルから学習するが、トランスダクティブ分類は、ラベル付きデータおよびラベルなしデータから分類規則を決定する。トランスダクティブSVM分類の一例を表1に示す。
【0059】
(トランスダクティブSVM分類の原理)
【0060】
【数5】

表1は、サポートベクタマシンを用いたトランスダクティブ分類の原理を示している。解は、ラベルなしデータの全てのあり得るラベル割り当てに関して、最大マージンをもたらす超平面(hyperplane)によって与えられる。あり得るラベル割り当ては、ラベルなしデータの数において指数関数的に増加し、実際に当てはまる解に対しては、表1のアルゴリズムを近似的に使用する必要がある。そのような近似の例は、T.Joachimsによる「Transductive inference for text classification using support vector machines」、 Technical report、 Universitaet Dortmund、 LAS VIII、 1999年に記載され(Joachims)ている。
【0061】
表1におけるラベル割り当て全体にわたる一様分布は、ラベルなしデータ点がクラスの正の例となる1/2の確率および負の例となる1/2の確率を有すること、すなわち、y=+1(正の例)およびy=−1(負の例)という2つのあり得るラベル割り当ての確率は等しく、その結果として期待されるラベルはゼロであることを、意味している。ゼロのラベル期待値は、1/2に等しい固定クラスの事前確率によって、または一様な事前分布を有するランダム変数であるクラスの事前確率、すなわち未知のクラスの事前確率によって求められ得る。従って、1/2に等しくない既知のクラスの事前確率を有するアプリケーションにおいては、この追加情報を組み込むことによってアルゴリズムが改善され得る。例えば、表1のラベル割り当てに関する一様分布を用いる代わりに、クラスの事前確率に従って、他のものよりも一部のラベル割り当てを優先することが、選択され得る。しかしながら、尤もらしいラベル割り当てを有するより小さいマージンの解と、より高いマージンを有するがラベル割り当ての尤もらしさにおいて劣る解との間の、トレードオフは困難である。ラベル割り当ての確率とマージンとは、尺度を異にする。
【0062】
(最大エントロピー識別)
別の分類法、最大エントロピー識別(MED)法(例えばT.Jebara「Machine Learning Discriminative and Generative」、Kluwer Academic Publishersを参照されたい)(Jebara)は、決定関数正規化項およびラベル割り当て正規化項の両方とも解上の事前確率分布から導出され、従って、両方とも同一の確率的尺度上にあるので、SVMに関連する問題に遭遇することはない。従って、クラスの事前確率、従って、ラベルの事前確率が既知の場合には、トランスダクティブMED分類は、理にかなった手法で事前ラベル知識の組み込みを許容するので、トランスダクティブSVM分類よりも優れている。
【0063】
帰納的MED分類法は、決定関数のパラメータの上に事前分布を、バイアス項の上に事前分布を、マージンの上に事前分布を仮定する。帰納的MED分類法は、これらのパラメータの上の最終分布として、事前分布に最も近いものを選択し、データ点を適切に分類する推定決定関数を得る。
【0064】
形式的には、例えば線形分類器とすれば、この問題は、次のように定式化される。超平面パラメータに関する分布p(Θ)、バイアス分布p(b)、データ点分類マージンp(γ)を、それらの結合された確率分布が結合されたそれぞれの事前分布pに対して最小のカルバックライブラーダイバージェンスKLを有するように求める、すなわち、
【0065】
【数6】

は、下の制約条件に従う。
【0066】
【数7】

ここで、
【0067】
【数8】

は、分離超平面の重みベクトルとt番目のデータ点の特徴ベクトルとのドット積である。ラベル割り当てyは既知でありかつ固定されているので、2値のラベル割り当てに対する事前分布は必要ではない。従って、帰納的MED分類をトランスダクティブMED分類に一般化する直接的手法は、2値のラベル割り当てを、あり得るラベル割り当てに対する事前分布によって制約されるパラメータとして処理することである。トランスダクティブMEDの一例を表2に示す。
【0068】
(トランスダクティブMED分類)
【0069】
【数9】

ラベル付きデータに対しては、ラベルの事前分布はδ関数であり、従って、+1または−1となるようにラベルを効果的に固定する。ラベルなしデータに対しては、ラベルの事前確率p(y)は、すべてのラベルなしデータ点に、p(y)の確率を有するy=+1の正のラベルおよび1−p(y)の確率を有するy=−1の負のラベルを割り当ると仮定される。情報を提供しないラベルの事前確率(p(y)=1/2)を仮定することで、上に論じたトランスダクティブSVM分類に類似したトランスダクティブMED分類が得られる。
【0070】
トランスダクティブSVM分類の場合のように、このようなMEDアルゴリズムの実用的実施は、あり得る全ラベル割り当てにわたって検索を近似する必要がある。T.Jaakkola、M.MeilaおよびT.Jebaraによる「Maximum entropy discrimination」、 Technical Report AITR−1668、マサチューセッツ工科大学、人工知能研究所、1999年に記載された(Jaakkola)手法は、近似式として、期待値最大化(EM)の定式化に類似して、手順を2段階に分解することを選んでいる。この定式化には、解決すべき2つの問題点がある。第1は、EMアルゴリズムのM段階に類似し、ラベル割り当てに関する現在最善の推測に従って全データ点を適切に分類する一方での、マージンの最大化と似ている点である。第2の段階は、E段階に類似して、M段階で決定された分類結果を用いて各例のクラス帰属に関する新たな値を推定する。この第2の段階を、本発明者らはラベル帰納と呼ぶ。全体的な説明は表2に示されている。
【0071】
本明細書において参照するJaakkolaの手法の特定の実装は、超平面のパラメータに対して、平均ゼロと単位分散を有するガウス分布を、バイアスのパラメータに対して、平均ゼロと分散σを有するガウス分布を、上に論じたラベルなしデータに対して、γがデータ点のマージン、cがコスト要因である式exp[−c(1−γ)]の形のマージン事前確率、およびp(y)の2値ラベルの事前確率を、仮定する。本明細書において参照するトランスダクティブ分類アルゴリズム、Jaakkolaに関する以下の論述に関しては、簡略化の理由から、また一般性を喪失しないために、1/2のラベルの事前確率を仮定する。
【0072】
ラベル帰納段階は、超平面のパラメータに関する固定確率分布を所与としたラベルの確率分布を決定する。上に紹介したマージンおよびラベルの事前確率を用いて、ラベル帰納段階に対する以下の目的関数が得られる(表2参照)。
【0073】
【数10】

ここで、λはt回目の訓練例のラグランジュ乗数、sは先のM段階で決定されたその分類スコア、cはコスト要因である。訓練例に関する合計の中の最初の2つの項はマージンの事前分布から導出されるが、それに対して、3番目の項はラベルの事前分布によって与えられる。
【0074】
【数11】

を最大化することによってラグランジュ乗数が決定され、その結果として、ラベルなしデータに関するラベルの確率分布が決定される。式3から分かるように、各データ点は独立して目的関数に寄与する。従って、各ラグランジュ乗数は、他のすべてのラグランジュ乗数に関係なく決定され得る。例えば、その分類スコアの高い絶対値|s|を有するラベルなしデータ点の寄与を最大化するためには、小さいラグランジュ乗数λが必要であるが、それに対して、小さい値|s|を有するラベルなしデータ点は、大きいラグランジュ乗数と共に、
【0075】
【数12】

に対する寄与を最大化する。その一方では、ラベルなしデータ点の分類スコアsおよびそのラグランジュ乗数λの関数としてのラベルなしデータ点の期待ラベル<y>は、
【0076】
【数13】

となる。
図1に、c=5およびc=1.5のコスト要因を用いた分類スコアsの関数としての期待ラベル<y>を示す。図1の生成に用いたラグランジュ乗数は、c=5およびc=1.5のコスト要因を用いて式3を解くことによって決定された。図1から分かるように、マージンの外側、すなわち|s|>1のラベルなしデータ点は、ゼロに近い期待ラベル<y>を有しており、マージンに近い、すなわち|s|≒1のデータ点は、最も高い期待ラベル絶対値をもたらし、超平面に近い、すなわち|s|<∈のデータ点は、|<y>|<∈をもたらす。|s|→∞に対して<y>→0というこの非直感的ラベル割り当ての理由は、分類上の制約が満たされる限りはできるだけ事前分布の近傍にとどまろうとする、選択された識別的手法にある。これは、表2の既知の手法によって選択された近似式のアーチファクトではなく、すなわち、あり得る全ラベル割り当てを網羅的に検索し、従って、大域的最適解を求めることを保証するするアルゴリズムがまた、マージンの外側のラベルなしデータにもゼロに近いかまたはゼロに等しい期待ラベルを割り当てる。上に述べたように、ここでもまた、識別的観点からそれが期待される。マージンの外側のデータ点は、例を分離するのには重要ではなく、従って、これらのデータ点のすべての個々の確率分布は、それらの事前確率分布に戻る。
【0077】
本明細書において参照するJaakkolaのトランスダクティブ分類アルゴリズムのM段階は、下記の制約下で、それぞれの事前分布に最も近い、超平面のパラメータ、バイアス項、およびデータ点のマージンに関する確率分布を決定する。
【0078】
【数14】

ここで、sはt回目のデータ点分類スコア、〈y〉はその期待ラベル、〈γ〉はその期待マージンである。ラベル付きデータに対しては、期待ラベルは固定されており、<y>=+1または<y>=−1である。ラベルなしデータに関する期待ラベルは、区間(−1、+1)の中にあり、ラベル帰納段階で推定される。式5によれば、分類スコアは期待ラベルによってスケーリングされるので、ラベルなしデータは、ラベル付きデータよりも厳しい分類制約を満たす必要がある。さらに、図1を参照し、分類スコアの関数としての期待ラベルの依存性を所与とすると、分離超平面に近いラベルなしデータは、最も厳しい分類制約を有する。なぜならば、それらのスコアおよびそれらの期待ラベルの絶対値|〈y〉|が小さいからである。上述の事前分布を所与としたM段階の全目的関数は、
【0079】
【数15】

となる。
第1項はガウスの超平面パラメータ事前分布から導出され、第2項はマージン事前正規化項、最後の項は、平均ゼロと分散σとを有するガウス事前分布から導出されるバイアスの事前正規化項である。バイアス項に対する事前分布は、クラスの事前確率に対する事前分布として解釈され得る。従って、バイアスの事前分布に対応する正規化項は、正から負までの例の重みを制約する。式6によれば、バイアス項の寄与は、超平面上での正の例の一括プルと負の例の一括プルとが等しくなる場合に最小化される。バイアスの事前分布によるラグランジュ乗数に対する一括制約は、データ点の期待ラベルによって重み付けされ、従って、ラベル付きデータに対するよりもラベルなしデータに対する方が制約が少ない。従って、ラベルなしデータは、最終解に対して、ラベル付きデータよりも強い影響を与える能力を有する。
【0080】
要約すれば、本明細書において参照するJaakkolaのトランスダクティブ分類アルゴリズムのM段階で、ラベルなしデータは、ラベル付きデータよりも厳しい分類上の制約を満たす必要があり、解に対するラベルなしデータの累積重みは、ラベル付きデータに対するよりも少ない制約を受ける。さらに、現在のM段階のマージン内に位置するゼロに近い期待ラベルを有するラベルなしデータは、解に最も影響を与える。この手法でE段階およびM段階を定式化することから得られた正味の効果が、データセットに対してこのアルゴリズムを適用することによって、図2において示される。このデータセットは、2つのラベル付き例、すなわちx−位置−1に位置する負の例(×)および+1に位置する正の例(+)と、x−軸に沿って−1と+1との間に位置する6つのラベルなしの例(○)とを含む。×印(×)はラベル付きの負の例、プラス記号(+)はラベル付きの正の例、円(○)はラベルなしデータを示す。様々なプロットは、M段階の種々の繰り返し時点で求められた分離超平面を示す。本明細書において参照するJaakkolaのトランスダクティブMED分類器によって選ばれた最終解は、正のラベル付き訓練例を誤分類する。図2に、M段階のいくつかの繰り返しを示す。M段階の最初の繰り返しでは、ラベルなしデータについては考慮されず、分離超平面はx=0に位置する。負のx値を有する1つのラベルなしデータ点は、他のどのラベルなしデータよりもこの分離超平面に近い。次のラベル帰納段階で、このラベルなしデータ点は、最小の|<y>|を割り当てられることになり、従って、次のM段階で、これは、正のラベル付き例に向けて超平面をプッシュする最も大きい力を有する。ラベルなしデータ点の特定の間隔と結合された、選択されたコスト要因によって決定される分類スコアの関数としての期待ラベル<y>の特定の形状(図1参照)は、各連続的M段階において分離超平面が正のラベル付き例に向けて次第に近づいてゆくブリッジ効果を生成する。直観的に、M段階では、最新の分離超平面に最も近いラベルなしデータ点が該平面の最終位置を最も決定し、さらに離れたデータ点はさほど重要ではない、一種の近視状態となる。最終的に、ラベル付きデータの一括プルよりもラベルなしデータの一括プルをより少なく制約するバイアスの事前分布項により、分離超平面は正のラベル付き例を超えて先へ移動し、最終解、すなわち、図2の15回目の繰り返しが得られ、それは正のラベル付き例を誤分類する。σ=1のバイアス分散およびc=10のコスト要因が図2で用いられた。σ=1を有すれば、9.8<c<13の範囲内の任意のコスト要因が、結果的に、1つの正のラベル付き例を誤分類する最終超平面をもたらす。区間9.8<c<13の外のコスト要因は、2つのラベル付き例の間のいずれかの位置に分離超平面をもたらす。
【0081】
このアルゴリズムのこの不安定さは、図2に示す例に限定されるものではなく、本明細書において参照するJaakkola法を当業者に公知のロイターのデータセットを含む実世界に適用する間にも、経験されている。表2に記載した方法に固有の不安定さは、この実装の主要な欠点であり、その一般的利用性を限定するが、しかし、Jaakkola法は本発明の一部の実施形態において実行され得る。
【0082】
本発明の1つの好適な手法は、最大エントロピー識別(MED)の枠組みを用いたトランスダクティブ分類を採用している。本発明の種々の実施形態は、分類に適用可能であると同時に、これに限定するものではないが、トランスダクティブMED回帰およびグラフィカルモデルを含む、トランスダクションを用いた他のMED学習上の問題にもまた適用可能であることが、理解されるべきである。
【0083】
最大エントロピー識別法は、パラメータに対する事前確率分布を仮定することによって、あり得る解に制約を加えて縮約する。最終解は、期待される解が訓練データを適切に記述するという制約下で、仮定された事前確率分布に最も近い確率分布に従ったあり得るすべての解の期待値である。解の上の事前確率分布は、正規化項にマッピングする。すなわち、特定の事前分布を選択することによって、特定の正規化を選択したことになる。
【0084】
サポートベクタマシンによって適用される識別的推定は、数少ない例から学習する際に効果的である。本発明の一実施形態のこの方法および装置は、これをサポートベクタマシンと同様に有しており、与えられた問題を解くために必要以上のパラメータを推定しようとせず、その結果、スパース解をもたらす。これは、基礎となるプロセスを説明しようとし、かつ一般的に識別的推定よりも大きな統計データを必要とする、生成的モデル推定と対照的である。一方では、生成的モデルはより用途が広く、より多種多様な問題に適用され得る。さらに、生成的モデル推定は、従来知識の直接的包含が可能である。最大エントロピー識別を用いた本発明の一実施形態の方法および装置は、純粋に識別的な、例えばサポートベクタマシン学習と、生成的モデル推定との間のギャップを埋める。
【0085】
表3に示す本発明の一実施形態の方法は、本明細書において参照するJaakkolaにおいて論じた方法の不安定さの問題を有しない、改良されたトランスダクティブMED分類アルゴリズムである。相違点は、これに限定するものではないが、本発明の一実施形態では、各データ点がそのラベル期待絶対値|<y>|に比例するそれ自体のコスト要因を有することを含む。さらに、各データ点のラベルの事前確率は、決定関数までのデータ点の距離の関数としての推定クラス帰属確率に従って、各M段階の後に更新される。本発明の一実施形態の方法は、以下の表3で説明される。
【0086】
(改良されたトランスダクティブMED分類)
【0087】
【数16】

|<y>|によってデータ点のコスト要因をスケーリングすることは、ラベルなしデータがラベル付きデータよりも超平面上でより強い累積プルを有し得るという問題を緩和する。なぜならば、ラベルなしデータのコスト要因は今やラベル付きのコスト要因よりも小さい、すなわち各ラベルなしデータ点の最終解に対する個々の寄与はラベル付きデータ点の個々の寄与よりも常に小さいからである。しかしながら、ラベルなしデータの量がラベル付きデータの数よりもはるかに大きい場合には、ラベルなしデータは依然として、ラベル付きデータよりも最終解に影響を与え得る。さらに、コスト要因のスケーリングと推定クラス確率を用いたラベルの事前確率の更新との結合は、上に概説したブリッジ効果の問題を解決する。最初のM段階で、ラベルなしデータは、極めて平坦な分類スコアの関数として期待ラベルをもたらす小さいコスト要因を有し(図1参照)、従って、小さい重みにすぎないが、ある程度まで、全ラベルなしデータは超平面上でプルすることが可能である。さらに、ラベルの事前確率の更新の結果として、分離超平面から離れたラベルなしデータはゼロに近い期待ラベルを割り当てられないが、数回の繰り返しの後に、y=+1またはy=−1に近いラベルが割り当てられ、かくして、ラベル付きデータのようにゆっくりと処理される。
【0088】
本発明の一実施形態の方法の特定の実装において、決定関数パラメータΘに対して、平均ゼロと単位分散とを有するガウス事前分布を仮定することによって、次のようになる。
【0089】
【数17】

決定関数パラメータに対する事前分布は、当面の特定の分類上の問題に関する重要な従来知識を組み込んでいる。分類上の問題にとって重要な決定関数パラメータの他の事前分布は、例えば、多項分布、ポアソン分布、コーシー分布(Breit−Wigner)、マクスウェル−ボルツマン分布、またはボーズ−アインシュタイン分布である。
【0090】
決定関数の閾値bに対する事前分布は、平均μと分散σとを有するガウス分布によって与えられる。
【0091】
【数18】

データ点の分類マージンγの事前分布として、
【0092】
【数19】

が選ばれ、ここで、cはコスト要因である。この事前分布は、式exp[−c(l−γ)]の形を有する本明細書において参照するJaakkolaで用いられるものとは異なっている。式9で与えられた形が本明細書において参照するJaakkolaで用いられる形を越えることが好ましく、なぜならば、Jaakkolaの形が1より小さいコスト要因に対してさえも正の期待マージンをもたらすのに対して、式exp[−c(l−γ)]は、c<1に対して負の期待マージンをもたらすからである。
【0093】
これらの事前分布が与えられると、対応する分配関数Ζを決定することは容易であり(例えば、T.M.CoverおよびJ.A.Thomas「Elements of Information Theory」、 John Wiley & Sons, Inc.参照)(Cover)、目的関数
【0094】
【数20】

は、
【0095】
【数21】

となる。本明細書において参照するJaakkolaによれば、M段階の目的関数は、
【0096】
【数22】

となり、E段階の目的関数は、
【0097】
【数23】

となる。ここで、sは先のM段階で決定されたt番目のデータ点の分類スコアであり、p0,t(y)はデータ点の2値ラベル事前確率である。ラベルの事前確率は、ラベル付きデータに対してはp0,t(y)=1に、ラベルなしデータに対しては、p0,t(y)=1/2の情報を与えない事前確率またはクラスの事前確率に初期化される。
【0098】
本明細書におけるM段階と題する章は、M段階の目的関数を解くためのアルゴリズムについて説明する。また、本明細書におけるE段階と題する章は、E段階のアルゴリズムについて説明する。
【0099】
表3の行5の、EstimateClassProbabilityの段階は、訓練データを用いて、分類スコアをクラス帰属確率に、すなわちスコアp(c|s)を与えられたクラスの確率に、変えるための較正パラメータを決定する。確率に関するスコア較正を推定するための関連する方法は、J.Platt「Probabilistic outputs for support vector machines and comparison to regularized likelihood methods」、61−74頁、2000年(Platt)に、ならびにB.ZadroznyおよびC.Elkan「Transforming classifier scores into accurate multi−class probability estimates」、2002年(Zadrozny)に、記載されている。
【0100】
図3を特に参照し、×印(×)はラベル付きの負の例、プラス記号(+)はラベル付きの正の例、円(○)はラベルなしデータを示す。様々なプロットは、M段階の種々の繰り返し時点で決定された分離超平面を示す。20回目の繰り返しは、改良されたトランスダクティブMED分類器によって選ばれた最終解を示す。図3は、上で紹介した玩具データセットに適用された改良型トランスダクティブMED分類アルゴリズムを示す。使用パラメータは、c=10、σ=1、およびμ=0である。異なるcがx≒−0.5とx=0との間に位置する分離超平面をもたらし、それにより、c<3.5で、超平面はx<0を有する1つのラベルなしデータの右に位置し、c≧3.5でこのラベルなしデータ点の左に位置する。
図4を特に参照して、本発明の一実施形態のラベルなしデータの分類法を示す制御流れ図が示されている。方法100は、ステップ102で始まり、ステップ104で、格納されたデータ106にアクセスする。データは記憶域に格納されており、ラベル付きデータと、ラベルなしデータと、少なくとも1つの所定コスト要因とを含む。データ106は、割り当てられたラベルを有するデータ点を含む。割り当てられたラベルは、ラベル付きデータ点が特定のカテゴリに含まれることを意図されているのか、あるいは特定のカテゴリから除外されることを意図されているのかを識別する。
【0101】
ひとたびステップ104でデータがアクセスされると、本発明の一実施形態の方法は次いで、ステップ108で、データ点のラベル情報を用いて、データ点のラベルの事前確率を決定する。次いで、ステップ110で、ラベルの事前確率に従って、データ点の期待ラベルが決定される。ステップ110で決定された期待ラベルと、ラベル付きデータ、ラベルなしデータ、およびコスト要因と共に、ステップ112は、コスト要因のラベルなしデータ点のスケーリングによるトランスダクティブMED分類器の繰り返し訓練を含む。計算の各繰り返しの中で、データ点のコスト要因がスケーリングされる。かくして、MED分類器は、計算の反復繰り返しを通じて学習する。訓練された分類器は次いで、ステップ116で入力データ114にアクセスする。訓練された分類器は次いで、ステップ118で入力データ分類のステップを完了し得、ステップ120で終了する。
【0102】
106のラベルなしデータおよび入力データ114は、単一のソースから導出され得ることが、理解されるべきである。かくして、入力データ/ラベルなしデータは、112の繰り返しプロセスに用いられ得、それは次いで、118で分類するために使用される。さらに、本発明の一実施形態は、入力データ114が、該入力データを106に格納されたデータに供給するためのフィードバック機構を含み、それにより112のMED分類器が、入力された新たなデータから動的に学習し得ることを、企図している。
【0103】
図5を特に参照して、ユーザ定義の事前確率情報を含む、本発明の一実施形態のラベルなしデータの別の分類法を示す制御流れ図が示されている。方法200は、ステップ202で始まり、ステップ204で格納されたデータ206にアクセスする。データ206は、ラベル付きデータと、ラベルなしデータと、所定コスト要因と、ユーザによって提供された事前確率情報とを含む。206のラベル付きデータは、割り当てられたラベルを有するデータ点を含む。割り当てられたラベルは、ラベル付きデータ点が特定のカテゴリに含まれることを意図されているのか、あるいは特定のカテゴリから除外されることを意図されているのかを識別する。
【0104】
ステップ208で、期待ラベルが206のデータから計算される。期待ラベルは次いで、ステップ210で、ラベル付きデータ、ラベルなしデータ、およびコスト要因と共に、トランスダクティブMED分類器の繰り返し訓練を行うために用いられる。210の繰り返し計算は、各計算時点で、ラベルなしデータのコスト要因をスケーリングする。計算は、分類器が適切に訓練されるまで続く。
【0105】
訓練された分類器は次いで、214で、入力データ212からの入力データにアクセスする。訓練された分類器は次いで、ステップ216で、入力データを分類するステップを完了し得る。図4で説明したプロセスおよび方法の場合と同様に、入力データおよびラベルなしデータは単一のソースから導出され得、206と212との両方においてシステムに入力され得る。かくして、入力データ212は210での訓練に影響を与え得、その結果として、プロセスは継続入力データで動的に経時変化し得る。
【0106】
図4および図5に示す両方の方法において、モニタが、システムが収束に到達したか否かを判断し得る。収束は、MED計算の各繰り返しの間における超平面の変化が所定の閾値を下回ったときに、判断され得る。本発明の代替の実施形態では、この閾値は、決定された期待ラベルの変化がある所定の閾値を下回ったときに、判断され得る。収束に到達した場合には、繰り返し訓練プロセスは終了し得る。
【0107】
図6を特に参照して、本発明の方法の少なくとも1つの実施形態の、繰り返し訓練プロセスのより詳細な制御流れ図が示されている。プロセス300は、ステップ302で始まり、ステップ304で、データ306からデータがアクセスされる。データ306は、ラベル付きデータと、ラベルなしデータと、少なくとも1つの所定コスト要因と、事前確率情報とを含み得る。306のラベル付きデータ点は、データが指定されたカテゴリに含まれるべきデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されるべきデータ点に対する訓練例であるのかを識別するラベルを含む。306の事前確率情報は、ラベル付きデータセットおよびラベルなしデータセットの確率情報を含む。
【0108】
ステップ308で、306の事前確率情報からのデータから期待ラベルが決定される。ステップ310で、データ点の期待ラベルの絶対値に比例して、各ラベルなしデータに対するコスト要因がスケーリングされる。次いで、ステップ312で、ラベル付きデータとラベルなしデータをそれらの期待ラベルに従って訓練例として用い、含まれた訓練例と除外された訓練例との間のマージンを最大化する決定関数を決定することによって、MED分類器が訓練される。ステップ314で、312の訓練された分類器を用いて、分類スコアが決定される。316で、クラス帰属確率に対して分類スコアが較正される。ステップ318で、クラス帰属確率に基づいて、ラベルの事前確率情報が更新される。ステップ320でMED計算が行われ、ラベルおよびマージンの確率分布が決定される。ここで、先に決定された分類スコアがMED計算に用いられる。その結果として、ステップ322で新たな期待ラベルが計算され、ステップ322からの計算結果を用いて、ステップ324で期待ラベルが更新される。ステップ326で本方法は、収束に到達したか否かを判断する。到達した場合には、本方法はステップ328で終了する。収束に到達していない場合には、ステップ310で始まる、本方法の別の繰り返しが完了される。繰り返しは収束に到達するまで反復され、その結果として、MED分類器が繰り返して訓練される。MED計算の各繰り返しの間における決定関数の変化が所定の値を下回ったときに、収束に到達し得る。本発明の代替の実施形態では、決定された期待ラベル値の変化が所定の閾値を下回ったときに、収束に到達し得る。
【0109】
図7は、一実施形態によるネットワークアーキテクチャ700を示す。図に示すように、第1の遠隔ネットワーク704および第2の遠隔ネットワーク706を含む複数の遠隔ネットワーク702が提供される。ゲートウェイ707が、遠隔ネットワーク702と隣接ネットワーク708と間に結合され得る。本ネットワークアーキテクチャ700の状況においては、ネットワーク704、706はそれぞれ、これに限定するものではないが、LAN、インターネットのようなWAN、PSTN、内部電話ネットワークなどを含む、任意の形態をとり得る。
【0110】
使用時には、ゲートウェイ707は、遠隔ネットワーク702から隣接ネットワーク708への入口点としての役割を果たす。かくして、ゲートウェイ707は、ゲートウェイ707に到達する与えられたデータパケットを誘導するルータとして、また与えられたパケットに対してゲートウェイ707を出入りする実際の経路を提供するスイッチとして、機能し得る。
【0111】
さらに、隣接ネットワーク708に結合され、ゲートウェイ707を介して遠隔ネットワーク702からアクセス可能な、少なくとも1つのデータサーバ714が含まれる。データサーバ(単数または複数)714は任意の種類の計算装置/グループウェアをも含み得ることが、留意されるべきである。各データサーバ714に、複数のユーザ装置716が結合されている。このようなユーザ装置716は、デスクトップコンピュータ、ラップトップコンピュータ、ハンドヘルドコンピュータ、プリンタまたは任意の他の種類の論理を含み得る。一実施形態では、ユーザ装置717はまた任意のネットワークに直接的に結合され得ることが、留意されるべきである。
【0112】
1つのファクシミリ装置720または一連のファクシミリ装置720が、ネットワーク704、706、708のうちの1つ以上に結合され得る。
【0113】
データベースおよび/または追加の構成要素が、ネットワーク704、706、708に結合された任意の種類のネットワーク要素と共に用いられ得、またはそれに統合され得ることが、留意されるべきである。本説明の文脈の中で、ネットワーク要素は、ネットワークの任意の構成要素を参照し得る。
【0114】
図8は、一実施形態による、図7のユーザ装置716と関連付けられた代表的なハードウェア環境を示す。当該の図は、マイクロプロセッサのような中央処理ユニット810、およびシステムバス812を介して相互に接続された多数の他のユニットを有する、ワークステーションの一般的なハードウェア構成を示している。
【0115】
図8に示すワークステーションは、ランダムアクセスメモリ(RAM)814と、読取り専用メモリ(ROM)816と、磁気ディスク装置820のような周辺装置をバス812に接続するためのI/Oアダプタ818と、キーボード824、マウス826、スピーカ828、マイクロホン832、および/またはタッチスクリーンおよびデジタルカメラ(図示せず)のような他のインタフェース装置をバス812に接続するためのユーザインタフェースアダプタ822と、ワークステーションを通信ネットワーク835(例えば、データ処理ネットワーク)に接続するための通信アダプタ834と、バス812をディスプレイ装置838に接続するためのディスプレイアダプタ836と、を含む。
【0116】
図9を特に参照して、本発明の一実施形態の装置414が示されている。本発明の一実施形態は、ラベル付きデータ416を格納するためのメモリ装置814を備える。ラベル付きデータ点416はそれぞれ、データ点が指定されたカテゴリに含まれるデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されたデータ点に対する訓練例であるのかを示すラベルを含む。メモリ814はまた、ラベルなしデータ418、事前確率データ420、およびコスト要因データ422をも格納する。
【0117】
プロセッサ810は、メモリ814からのデータにアクセスし、トランスダクティブMED計算を用いて2値分類器を訓練し、それがラベルなしデータを分類できるようにする。プロセッサ810は、ラベル付きデータとラベルなしデータとからのコスト要因および訓練例を用いることによって、かつそのコスト要因を期待ラベル値の関数としてスケーリングして、その後プロセッサ810に再入力されるコスト要因データ422のデータに影響を与えることによって、繰り返しトランスダクティブ計算を使用する。従って、コスト要因422は、プロセッサ810によるMED分類の各繰り返しと共に変化する。ひとたびプロセッサ810が適切にMED分類器を訓練すると、プロセッサは次いで、ラベルなしデータを分類済みデータ424に分類するための分類器を構築し得る。
【0118】
従来技術のトランスダクティブSVM定式化およびMED定式化は、あり得るラベル割り当ての指数関数的増加をもたらし、実用化のためには、近似式を開発する必要がある。本発明の代替の実施形態においては、あり得るラベル割り当てが指数関数的に増加せず、一般的な閉形式解を可能にする、トランスダクティブMED分類の異なる定式化が導入されている。線形分類器に対して、この問題は以下のように定式化される。超平面パラメータに関する分布p(Θ)、バイアス分布p(b)、データ点分類マージンp(γ)を、これらの結合された確率分布が結合されたそれぞれの事前分布pに対して最小のカルバックライブラーダイバージェンスKLを有するように求める、すなわち、
【0119】
【数24】

であり、ラベル付きデータに対して以下の制約に従い、
【0120】
【数25】

ラベルなしデータに対して以下の制約に従い、
【0121】
【数26】

ここで、ΘXは、分離超平面の重みベクトルとt番目のデータ点の特徴ベクトルとのドット積である。ラベルに対する事前分布は必要ではない。ラベル付きデータは、それらの既知のラベルに従って分離超平面の右側に位置するように制約されているが、ラベルなしデータに対する唯一の要求条件は、超平面までのラベルなしデータの距離の2乗がマージンよりも大きいということである。要約すると、本発明のこの実施形態は、選択された事前分布に最も近く、ラベル付きデータを適切に分離し、かつマージン間にラベルなしデータを全く有しないという、妥協点となる分離超平面を求める。利点は、ラベルに対する事前分布を導入する必要がなく、従って、指数関数的に増加するラベル割り当てに関する問題が回避されることである。
【0122】
本発明の別の実施形態の特定の実装では、超平面パラメータ、バイアス、およびマージンに対して式7、式8、および式9に与えられた事前分布を用いて、以下の分配関数が得られ、
【0123】
【数27】

ここで、tはラベル付きデータの添え字であり、t´はラベルなしデータの添え字である。下記の表記法を用いると、
【0124】
【数28】

式16は、以下のように書き換えられる。
【0125】
【数29】

積分の後に、以下の分配関数が得られる。
【0126】
【数30】

すなわち、最終目的関数は、
【0127】
【数31】

となる。目的関数
【0128】
【数32】

は、本明細書においてM段階と題する章で述べられる、既知のラベルの場合の手法に類似した手法を適用することによって解かれ得る。差異は、最大マージン項の二次形式におけるマトリックスG−1が、ここで非対角項を有する点である。
【0129】
分類に加えて、最大エントロピー識別の枠組みを採り入れた本発明の方法の用途は、数多く存在する。例えば、MEDは、一般的なデータの分類、任意の種類の識別関数および事前分布、回帰モデルおよびグラフィカルモデルを解くために適用され得る(T.Jebara「Machine Learning Discriminative and Generative」、 Kluwer Academic Publishers)(Jebara)。
【0130】
本発明の実施形態のアプリケーションは、既知のラベルを有する純粋に帰納的な学習問題として、およびラベル付きとラベルなしの訓練例を有するトランスダクティブ学習問題として、定式化され得る。後者の場合には、表3に記載されたトランスダクティブMED分類アルゴリズムに対する改良が、一般のトランスダクティブMED分類、トランスダクティブMED回帰、グラフィカルモデルのトランスダクティブMED学習に対しても、同様に適用可能である。かくして、本開示および特許請求の範囲の目的に対して、語「分類」は、回帰またはグラフィカルモデルを含み得る。
【0131】
(M段階)
式11によれば、M段階の目的関数は、
【0132】
【数33】

となる。これにより、ラグランジュ乗数λは、Jを最大化することによって決定される。
【0133】
λ<cという冗長制約を省くと、上記の双対問題に対するラグランジアンは、
【0134】
【数34】

となる。最適性に対して必要かつ十分なKKT条件は、
【0135】
【数35】

となる。ここで、Fは、
【0136】
【数36】

である。最適点において、基底は期待バイアス
【0137】
【数37】

と等しくなり、
【0138】
【数38】

が得られる。
【0139】
これらの式は、δλ=0制約を用いた2つの例を考察することによって、要約され得る。第1の例は、すべてに対してλ=0、第2の例は、すべてに対して0<λ<c、である。SVMアルゴリズムに適用された、S.Keerthi、S.Shevade、 C.Bhattacharyya、およびK.Murthy「Improvements to plait’s smo algorithm for svm classifier design」、1999年(Keerthi)に記載されているような、第3の例は必要でない。この定式化におけるポテンシャル関数は、λ≠cを保っている。
【0140】
【数39】

最適条件に到達するまでに、一部のデータ点tに対するこれらの条件の侵害が存在する。すなわち、λがゼロでないときにはF≠−〈b〉、またはλがゼロのときにはF〈y〉<−〈b〉〈y〉、である。残念なことに、〈b〉の計算は、最適なλのそれなくしては不可能である。これに対する良解は、以下の3つの組を構築することによって、再び本明細書において参照するKeerthiから借用される。
【0141】
【数40】

これらの組を利用して、以下の定義を用いた最も極端な最適性条件違反を定義することができる。Iの要素は、それらが−〈b〉に等しくないときは常に違反であり、従って、Iからの最大Fおよび最小Fは、違反の候補である。Iの要素は、F<−〈b〉のときに違反であり、従って、Iからの最小要素は、もしあるとすれば、最も極端な違反である。最後に、Iの要素は、F>−〈b〉のときに違反であり、それはIからの最大要素を違反候補にする。従って、−〈b〉は以下に示すように、これらの組に関する最小および最大によって制限される。
【0142】
【数41】

最適な−bupと−blowとは等しくなければならず、すなわち−〈b〉であるので、−bupと−blowとの間のギャップを減らすことが、訓練アルゴリズムを収束に向けてプッシュする。さらに、ギャップはまた、数値的収束を判断するための手法として、測定され得る。
【0143】
先に述べたように、b=〈b〉の値は、収束するまでは未知である。この代替の実施形態の方法は、1度に1例のみが最適化され得るという点で異なる。従って、訓練のヒューリスティックは、1回おきに、Iの例とすべての例との間で行きつ戻りつすることである。
【0144】
(E段階)
式12のE段階の目的関数は、
【0145】
【数42】

であり、ここでsは、先のM段階で決定されたt番目のデータ点の分類スコアである。ラグランジュ乗数λは、
【0146】
【数43】

を最大化することによって決定される。
【0147】
λ<cという冗長制約を省くと、上記の双対問題に対するラグランジアンは、
【0148】
【数44】

となる。最適性に対して必要かつ十分なKKT条件は、
【0149】
【数45】

である。KKT条件を最適化することによってラグランジュ5乗数に対する解を求めることは、KKT条件が例を分解する(factorize)ので、例を1回パスすることによって行われ得る。
【0150】
ラベル付き例に対しては、期待ラベル〈y〉は、P0,t(y)=1およびP0,t(−y)=0を有するものであり、KKT条件を
【0151】
【数46】

に簡略化し、ラベル付き例のラグランジュ乗数に対する解として、
【0152】
【数47】

をもたらす。ラベルなし例に対して、式35は解析的に解くことはできないが、しかしながら、式35を満たす各ラベルなし例のラグランジュ乗数に対して、例えば線形探索を適用することによって、決定されねばならない。
【0153】
以下は、上述の手法によって可能となるいくつかの非限定的な例、それらの派生物または変形物、および当業界で公知の他の手法である。各例は、好適な算法と、基本的な好適な手法の中で実装され得る任意選択的な算法またはパラメータとを含む。
【0154】
図10に提示される一実施形態では、ラベル付きデータ点がステップ1002で受信され、そこでは、データ点が指定されたカテゴリに含まれるべきデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されるデータ点に対する訓練例であるのかを示す、少なくとも1つのラベルを、ラベル付きデータ点の各々が有する。さらに、ラベルなしデータ点が、ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因と共に、ステップ1004で受信される。データ点は、任意の媒体、例えば語、画像、音響等を含み得る。ラベル付きとラベルなしデータ点の事前確率情報がまた、受信され得る。また、含まれた訓練例のラベルは、第1の数値、例えば+1などにマッピングされ得、除外された訓練例のラベルは、第2の数値、例えば−1などにマッピングされ得る。さらに、ラベル付きデータ点、ラベルなしデータ点、入力データ点、ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因が、コンピュータのメモリに格納され得る。
【0155】
さらに、ステップ1006で、上述の少なくとも1つのコスト要因と、ラベル付きデータ点およびラベルなしデータ点とを訓練例として用いて、繰り返し計算によってトランスダクティブMED分類器が訓練される。計算の各繰り返しに対して、ラベルなしデータ点のコスト要因は、期待ラベル値、例えばデータ点の期待ラベルの絶対値などの関数として調整され、データ点のラベルの事前確率は、データ点のクラス帰属確率の推定値に基づいて調整され、これによって安定性を確保する。また、トランスダクティブ分類器は、ラベル付きとラベルなしデータの事前確率情報を用いて学習し得、これは安定性をさらに向上させる。トランスダクティブ分類器を訓練する繰り返しステップは、データ値が収束に到達するまで、例えば、トランスダクティブ分類器の決定関数の変化が所定の閾値を下回るとき、決定された期待ラベル値の変化が所定の閾値を下回るとき、などまで反復され得る。
【0156】
さらに、ステップ1008で、訓練された分類器は、ラベルなしデータ点、ラベル付きデータ点、および入力データ点のうちの少なくとも1つを分類するために適用される。入力データ点は、分類器が訓練される前に、または後に受信され得、あるいは全く受信され得ない。また、含まれた訓練例および除外された訓練例を与えられた、決定関数パラメータの事前確率分布に対するKLダイバージェンスを最小化する決定関数は、ラベル付きとラベルなしデータ点をそれらの期待ラベルに従って学習例として用いて決定され得る。代替案としては、決定関数パラメータに対して多項分布を用いた最小のKLダイバージェンスによって、決定関数が決定され得る。
【0157】
ステップ1010で、分類されたデータ点の分類、またはその派生物が、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力される。本システムは遠隔の、または局地のものであり得る。分類の派生物の例は、これに限定するものではないが、分類されたデータ点そのもの、分類されたデータ点を表現したものまたはその識別子、あるいはホストファイル/文書、などであり得る。
【0158】
別の実施形態では、コンピュータ実行可能なプログラムコードがコンピュータシステムに配備され、その上で実行される。このプログラムコードは、コンピュータのメモリ内に格納されたラベル付きデータ点にアクセスするための命令を備え、該ラベル付きデータ点の各々は、データ点が指定されたカテゴリに含まれるべきデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されたデータ点に対する訓練例であるのかを示す少なくとも1つのラベルを有する。さらに、コンピュータコードは、コンピュータのメモリからラベルなしデータ点にアクセスするための命令と、コンピュータのメモリからラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因にアクセスするための命令をも含む。コンピュータのメモリ内に格納されたラベル付きとラベルなしデータ点の事前確率情報がまた、アクセスされ得る。また、含まれた訓練例のラベルは、第1の数値、例えば+1などにマッピングされ得、除外された訓練例のラベルは、第2の数値、例えば−1などにマッピングされ得る。
【0159】
さらに、プログラムコードは、少なくとも1つの格納されたコスト要因と格納されたラベル付きデータ点、および格納されたラベルなしデータ点、ならびに訓練例を用いた繰り返し計算によって、トランスダクティブ分類器を訓練するための命令を備える。また、計算の各繰り返しに対して、ラベルなしデータ点のコスト要因が、該データ点の期待ラベル値、例えばデータ点の期待ラベルの絶対値の関数として調整される。また、各繰り返しに対して、データ点のクラス帰属確率の推定値に基づき、事前確率情報が調整され得る。トランスダクティブ分類器を訓練する繰り返しステップは、データ値の収束に到達するまで、例えば、トランスダクティブ分類器の決定関数の変化が所定の閾値を下回るとき、決定された期待ラベル値の変化が所定の閾値を下回るとき、などまで反復され得る。
【0160】
さらに、プログラムコードは、訓練された分類器を適用して、ラベルなしデータ点、ラベル付きデータ点、および入力データ点のうちの少なくとも1つを分類するための命令と、分類されたデータ点の分類、またはその派生物を、ユーザ、別のシステム、および別のプロセスに出力するための命令とを備える。また、含まれた訓練例および除外された訓練例を与えられた、決定関数パラメータの事前確率分布に対してKLダイバージェンスを最小化する決定関数は、ラベル付きとラベルなしデータ点をそれらの期待ラベルに従って学習例として用いて、決定され得る。
【0161】
さらに別の実施形態では、データ処理装置は、(i)データ点が指定されたカテゴリに含まれるデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されたデータ点に対する訓練例であるのかを示す、少なくとも1つのラベルを各々が有するラベル付きデータ点、(ii)ラベルなしデータ点、および(iii)ラベル付きデータ点とラベルなしデータ点の少なくとも1つの所定コスト要因、を格納するための少なくとも1つのメモリを備える。このメモリは、ラベル付きとラベルなしデータ点の事前確率情報をも格納し得る。また、含まれた訓練例のラベルは、第1の数値、例えば+1などにマッピングされ得、除外された訓練例のラベルは、第2の数値、例えば−1などにマッピングされ得る。
【0162】
さらに、このデータ処理装置は、少なくとも1つの格納されたコスト要因および格納されたラベル付きデータ点ならびに格納されたラベルなしデータ点を訓練例として用いて、トランスダクティブ最大エントロピー識別(MED)を用いてトランスダクティブ分類器に繰り返し教示するためのトランスダクティブ分類器訓練装置を備える。さらに、MED計算の各繰り返しにおいて、ラベルなしデータ点のコスト要因が、データ点の期待ラベル値、例えばデータ点の期待ラベルの絶対値などの関数として調整される。また、MED計算の各繰り返しにおいて、事前確率情報が、データ点のクラス帰属確率の推定値に基づいて調整され得る。本装置は、例えば、トランスダクティブ分類器の計算の決定関数の変化が所定の閾値を下回ったとき、決定された期待ラベル値の変化が所定の閾値を下回ったときなどに、データ値の収束を判断するための手段、および収束の判断と同時に計算を終了するための手段を、さらに備え得る。
【0163】
さらに、訓練された分類器を用いて、ラベルなしデータ点、ラベル付きデータ点、および入力データ点のうちの少なくとも1つが分類される。さらに、含まれた訓練例および除外された訓練例を与えられた、決定関数パラメータの事前確率分布に対してKLダイバージェンスを最小化する決定関数が、ラベル付きとラベルなしデータをそれらの期待ラベルに従って学習例として用いてプロセッサによって決定され得る。また、分類されたデータ点の分類、またはその派生物が、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力される。
【0164】
さらなる実施形態において、製品は、コンピュータ読み取り可能なプログラム格納媒体を備え、該媒体は、データの分類法を実行するためのコンピュータによって実行可能な命令の1つ以上のプログラムを明白に具体化する。使用時には、データ点が指定されたカテゴリに含まれるデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されたデータ点に対する訓練例であるのかを示す、少なくとも1つのラベルを各々が有するラベル付きデータ点が受信される。さらに、ラベルなしデータ点と、ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因とが、受信される。ラベル付きとラベルなしデータ点の事前確率情報がまた、コンピュータのメモリ内に格納され得る。また、含まれた訓練例のラベルは、第1の数値、例えば+1などにマッピングされ得、除外された訓練例のラベルは第2の数値、例えば−1などにマッピングされ得る。
【0165】
さらに、トランスダクティブ分類器は、少なくとも1つの格納されたコスト要因ならびに格納されたラベル付きデータ点およびラベルなしデータ点を訓練例として用いて、繰り返し最大エントロピー識別(MED)計算によって訓練される。MED計算の各繰り返しにおいて、ラベルなしデータ点のコスト要因が、データ点の期待ラベル値、例えばデータ点の期待ラベルの絶対値などの関数として調整される。また、MEDの各繰り返しにおいて、事前確率情報が、データ点のクラス帰属確率の推定値に基づいて調整され得る。トランスダクティブ分類器を訓練する繰り返しステップは、データ値の収束に到達するまで、例えば、トランスダクティブ分類器の決定関数の変化が所定の閾値を下回るとき、決定された期待ラベル値の変化が所定の閾値を下回るとき、などまで、反復され得る。
【0166】
さらに、入力データ点がコンピュータのメモリからアクセスされ、訓練された分類器が、ラベルなしデータ点、ラベル付きデータ点、および入力データ点のうちの少なくとも1つを分類するために適用される。また、含まれた訓練例および除外された訓練例を与えられた、決定関数パラメータの事前確率分布に対してKLダイバージェンスを最小化する決定関数が、ラベル付きとラベルなしデータをそれらの期待ラベルに従って学習例として用いて決定され得る。さらに、分類されたデータ点の分類、またはその派生物が、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力される。
【0167】
さらに別の実施形態において、コンピュータベースのシステムにおけるラベルなしデータの分類法が提示される。使用時には、データ点が指定されたカテゴリに含まれるべきデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されたデータ点に対する訓練例であるのかを示す、少なくとも1つのラベルを各々が有するラベル付きデータ点が受信される。
【0168】
さらに、ラベル付きデータ点およびラベルなしデータ点の事前ラベル確率情報と同様に、ラベル付きデータ点およびラベルなしデータ点が受信される。さらに、ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因が受信される。
【0169】
さらに、各ラベル付きとラベルなしデータ点に対する期待ラベルが、データ点のラベルの事前確率に基づいて決定される。データ値の実質的な収束まで、以下の下位ステップが繰り返される。すなわち、
・データ点の期待ラベルの絶対値に比例して、各ラベルなしデータ点に対するスケーリングされたコスト値を生成し、
・ラベル付きとラベルなしデータをそれらの期待ラベルに従って訓練例として用いて、含まれた訓練例および除外された訓練例を与えられた、決定関数パラメータの事前確率分布に対してKLダイバージェンスを最小化する決定関数を決定することによって、最大エントロピー識別(MED)分類器を訓練し、
・訓練された分類器を用いて、ラベル付きデータ点とラベルなしデータ点の分類スコアを決定し、
・訓練された分類器の出力をクラス帰属確率に対して較正し、
・決定されたクラス帰属確率に従って、ラベルなしデータ点のラベルの事前確率を更新し、
・更新されたラベルの事前確率および先に決定された分類スコアを用いて、最大エントロピー識別(MED)を用いてラベルおよびマージンの確率分布を決定し、
・先に決定されたラベルの確率分布を用いて、新たな期待ラベルを計算し、
・新たな期待ラベルを前回の繰り返しの期待ラベルで補間することによって、各データ点に対する期待ラベルを更新する。
【0170】
また、入力データ点の分類またはその派生物が、ユーザ、別のシステム、および別のプロセスのうちの少なくとも1つに出力される。
【0171】
決定関数の変化が所定の閾値を下回ったときに、収束に到達し得る。さらに、算出された期待ラベル値の変化が所定の閾値を下回ったときにも、収束に到達し得る。さらに、含まれた訓練例のラベルは、任意の値、例えば+1という値を有し得、除外された訓練例のラベルは、任意の値、例えば−1という値を有し得る。
【0172】
本発明の一実施形態における、文書を分類する方法が図11に提示される。使用時には、ステップ1100で、ラベルなし文書および少なくとも1つの所定コスト要因と共に、既知の信頼水準を有する少なくとも1つのシード文書が受信される。シード文書および他のアイテムは、コンピュータのメモリ、ユーザ、ネットワーク接続などから受信され得、本方法を実行中のシステムからの要求後に受信され得る。少なくとも1つのシード文書は、該文書が指定されたカテゴリに含まれているか否かを示すラベルを有し得、キーワードのリストを含み得、または文書の分類を支援し得る任意の他の属性を有し得る。さらに、ステップ1102で、少なくとも1つの所定コスト要因、少なくとも1つのシード文書、およびラベルなし文書を用いた繰り返し計算によって、トランスダクティブ分類器が訓練され、ここで、各計算の繰り返しに対して、コスト要因が期待ラベル値の関数として調整される。ラベル付きとラベルなし文書に関するデータ点のラベルの事前確率がまた受信され得、ここで、計算の各繰り返しに対して、データ点のクラス帰属確率の推定に従って、データ点のラベルの事前確率が調整され得る。
【0173】
さらに、少なくともいくつかの繰り返しの後に、ステップ1104で、ラベルなし文書に対する信頼スコアが格納され、ステップ1106で、最も高い信頼スコアを有するラベルなし文書の識別子が、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力される。識別子は、文書自体の電子コピー、それらの部分、それらの表題、それらの名前、それらのファイル名、それらの文書へのポインタなどであり得る。また信頼スコアは、各々の繰り返しの後に格納され得、その場合、各繰り返し後に最も高い信頼スコアを有するラベルなし文書の識別子が出力される。
【0174】
本発明の一実施形態は、最初の文書を残りの文書にリンクするパターンを発見することができる。開示手続きという仕事は、このパターン発見が特に価値のあるものとなる分野である。例えば、事実審理前の法的開示手続では、当面の訴訟と関連を有し得る大量の文書を調査する必要がある。究極の目標は、「決定的証拠」を発見することである。別の例では、発明者、特許審査官、および特許専門弁護士の日常的な仕事は、従来技術の検索によって技術の新規性を評価することである。詳細には、この仕事は、公開されたすべての特許および他の広報を検索して、新規性に関して審査されている特定の技術に関連し得る文書をこの組の中に発見することである。
【0175】
開示手続の仕事は、一組のデータ内の一文書または一組の文書の発見を含む。最初の文書または概念を得ると、ユーザは、該最初の文書または概念に関連する文書の発見を望み得る。しかしながら、最初の文書または概念と、標的文書、すなわち発見対象の文書との間の関係性の見解は、発見が生じた後にのみ十分に理解される。ラベル付きデータ点およびラベルなし文書、概念などから学習することによって、本発明は、最初の一文書または複数の文書と標的文書との間のパターンおよび関連性を学習し得る。
【0176】
本発明の別の実施形態における、法的開示手続と関連する文書を分析する方法が図12に提示される。使用時には、ステップ1200で、法的事項と関連する文書が受信される。そのような文書は、文書自体の電子コピー、それらの部分、それらの表題、それらの名前、それらのファイル名、文書へのポインタなどを含み得る。さらに、ステップ1202で、文書分類手法が文書に関して実行される。さらに、ステップ1204で、文書の分類に基づいて、文書の少なくとも一部の識別子が出力される。オプションとして、文書間のリンクを表示するものが、出力され得る。
【0177】
文書分類手法は、任意の種類の処理、例えばトランスダクティブ処理などを含み得る。例えば、上述の任意の帰納的手法またはトランスダクティブ手法が使用され得る。好ましい手法では、少なくとも1つの所定コスト要因、少なくとも1つのシード文書、および法的事項と関連する文書を用いた繰り返し計算によって、トランスダクティブ分類器が訓練される。計算の各繰り返しに対して、コスト要因が期待ラベル値の関数として好適にも調整され、この訓練された分類器が、受信された文書を分類するために使用される。このプロセスは、ラベル付きとラベルなし文書に関するデータ点のラベルの事前確率を受信するステップをさらに含み得、ここで、計算の各繰り返しに対して、データ点のラベルの事前確率が、データ点のクラス帰属確率の推定に応じて調整される。さらに、文書分類手法は、サポートベクタマシン処理および最大エントロピー識別処理のうちの1つ以上を含み得る。
【0178】
さらに別の実施形態における、従来技術文書を分析する方法が図13に提示される。使用時には、ステップ1300で、検索クエリに基づいて分類器が訓練される。ステップ1302で、複数の従来技術文書がアクセスされる。そのような従来技術文書は、所与の日付よりも前に任意の形で公表された任意の情報を含み得る。そのような従来技術は、所与の日付よりも前の時点では任意の形において公表されていない任意の情報をさらに、あるいは代替案として含み得る。例示的な従来技術文書は、任意の種類の文書、例えば特許庁の広報、データベースから取り出されたデータ、従来技術を収集したもの、ウェブサイトの一部、などであり得る。また、文書分類手法が、ステップ1304で、分類器を用いて従来技術文書の少なくとも一部に関して実行され、従来技術文書の少なくとも一部の識別子が、従来技術文書の分類に基づいてステップ1306で出力される。この文書分類手法は、サポートベクタマシン処理、最大エントロピー識別処理、または上述の任意の帰納的手法またはトランスダクティブ手法を含む、任意の1つ以上の処理を含み得る。また、あるいは代替案として、文書間のリンクを表示するものが、出力され得る。さらに別の実施形態では、少なくとも一部の従来文書の関連性スコアが、文書の分類に基づいて出力される。
【0179】
検索クエリは、特許情報開示の少なくとも一部を含み得る。例示的な特許情報開示は、発明を要約した、発明者によって作成された開示、特許仮出願、非暫定特許出願、外国特許出願、または特許出願、などを含む。
【0180】
好適な一手法では、検索クエリは、特許文書または特許出願書類から取り出した請求項の少なくとも一部を含む。別の手法では、検索クエリは、特許文書または特許出願書類の要約書の少なくとも一部を含む。さらに別の手法では、検索クエリは、特許文書または特許出願書類から取り出された概要の少なくとも一部を含む。
【0181】
図27は、文書を請求項とマッチングするための方法を示す。ステップ2700で、特許文書または特許出願書類の少なくとも1つの請求項に基づいて、分類器が訓練される。従って、1つ以上の請求項またはそれらの一部が、分類器を訓練するために用いられ得る。ステップ2702で、複数の文書がアクセスされる。そのような文書は、従来技術文書、潜在的に侵害または出し抜きをはかる製品を記載している文書、などを含み得る。ステップ2704で、分類器を用いて、少なくとも一部の文書に関して文書分類手法が実行される。ステップ2706で、少なくとも一部の文書の識別子が、文書の分類に基づいて出力される。少なくとも一部の文書の関連性スコアがまた、文書の分類に基づいて出力され得る。
【0182】
本発明の一実施形態は、特許出願の分類に使用され得る。例えば、米国では、特許および特許出願は現在、米国特許分類(USPC)システムを用いて、主題によって分類されている。この仕事は現在手作業で行われており、従って、非常に費用がかかりかつ多大な時間を必要とする。このような手作業による分類はまた、人為的ミスを被る。特許文書または特許出願書類が多数のクラスに分類され得ることが、そのような仕事の複雑さの度合いを増している。
【0183】
図28は、一実施形態による特許出願を分類する方法を示す。ステップ2800で、特定の特許分類に入ることが分かっている複数の文書に基づいて、分類器が訓練される。そのような文書は一般的に、特許文書および特許出願書類(またはそれらの一部)であり得るが、特定の特許分類の標的主題を記載した概要票でもあり得る。ステップ2802で、特許文書または特許出願書類の少なくとも一部が受信される。この一部は、請求項、概要、要約書、明細書、タイトルなどを含み得る。ステップ2804で、分類器を用いて、特許文書または特許出願書類の少なくとも一部に関して文書分類手法が実行される。ステップ2806で、特許文書または特許出願書類の分類が出力される。オプションとして、ユーザは、特許出願の一部または全部の分類を、手動で検証し得る。
【0184】
文書分類手法は、はい/いいえ式の分類手法であることが好ましい。換言すれば、文書が特定のクラスにある確率が閾値を上回る場合には、判定は「はい」で、その文書はこのクラスに属する。文書が特定のクラスにある確率が閾値を下回る場合には、判定は「いいえ」で、その文書はこのクラスに属さない。
【0185】
図29は、特許出願を分類するさらに別の方法を示している。ステップ2900で、特定の特許分類と関連する少なくとも1つの文書に基づいて訓練された分類器を用いて、特許文書または特許出願書類の少なくとも一部に関して文書分類手法が実行される。この場合にもまた、分類手法は、はい/いいえ式の分類手法であることが好ましい。ステップ2902で、特許文書または特許出願書類の分類が出力される。
【0186】
図28および図29に示す方法のいずれにおいても、異なる特許分類に入ることが分かっている複数の文書に基づいて訓練された異なる分類器を用いて、それぞれの方法が反復され得る。
【0187】
公式には、特許の分類は、請求項に基づくべきである。しかしながら、(任意のIP関連内容)と(任意のIP関連内容)との間のマッチングを行うことが、また所望され得る。一例を挙げれば、1つの手法は、特許の明細書を用いて訓練を行い、該特許の請求項に基づいて出願を分類する。別の手法は、明細書と請求項を用いて訓練を行い、要約書に基づいて分類する。特に好適な手法では、特許文書または特許出願書類のいかなる部分を用いて訓練が行われても、分類時にもそれと同じ種類の内容が用いられることであり、すなわち、システムが請求項に基づいて訓練される場合には、分類は請求項に基づいて行われることである。文書分類手法は、任意の種類の処理、例えばトランスダクティブ処理などを含み得る。例えば、上述の任意の帰納的手法またはトランスダクティブ手法が用いられ得る。好適な手法では、分類器はトランスダクティブ分類器であり得、トランスダクティブ分類器は、少なくとも1つの所定コスト要因、少なくとも1つのシード文書、および従来技術文書を用いた繰り返し計算によって訓練され得、ここで、計算の各繰り返しに対して、コスト要因が期待ラベル値の関数として調整され、訓練された分類器は、従来技術文書を分類するために使用され得る。シード文書および従来技術文書に対するデータ点のラベルの事前確率がまた、受信され得、ここで、計算の各繰り返しに対して、データ点のラベルの事前確率が、データ点のクラス帰属確率の推定値に応じて調整され得る。シード文書は任意の文書、例えば特許庁の広報、データベースから取り出されたデータ、従来技術を収集したもの、ウェブサイト、特許開示情報、などであり得る。
【0188】
図14は、1つの手法における、本発明の一実施形態を説明する。ステップ1401で、一組のデータが読み込まれる。この組の中の、ユーザと関連する文書の発見が所望されている。ステップ1402で、最初の1シード文書または複数のシード文書にラベルが付けられる。文書は任意の種類の文書、例えば特許庁の公報、データベースから取り出されたデータ、従来技術を収集したもの、ウェブサイト、などであり得る。ユーザによって提供された異なる一連のキーワードまたは文書で、トランスダクション処理をシードすることが、また可能である。ステップ1406で、トランスダクティブ分類器の訓練が、ラベル付きデータおよび所与の組のラベルなしデータの組を用いて行われる。繰り返しトランスダクション処理中の各ラベル帰納ステップで、ラベル帰納中に決定された信頼スコアが格納される。ひとたび訓練が終了すると、ラベル帰納ステップで高い信頼スコアを達成した文書が、ステップ1408でユーザに対して表示される。高い信頼スコアを有するこれらの文書は、発見という目的に対してユーザに関連する文書を表す。表示は、最初のシード文書から始まり、最後のラベル帰納ステップで発見された最終組の文書まで、ラベル帰納ステップの時間順になされ得る。
【0189】
本発明の別の実施形態は、例えば業務処理の自動化と結びついた、データの整理および正確な分類を含む。整理および分類の手法は、任意の種類の処理、例えばトランスダクティブ処理、などを含み得る。例えば、上述の任意の帰納的手法またはトランスダクティブ手法が使用され得る。好適な手法では、データベースへのエントリキーが、データベースの期待清浄度に応じて、一部の信頼水準と関連付けられたラベルとして用いられる。次いで、関連付けられた信頼水準を併せ持つラベル、すなわち期待ラベルが、トランスダクティブ分類器を訓練するために使用され、該トランスダクティブ分類器がラベル(キー)を修正し、データベース内のデータのより一貫性のある編成を達成する。例えば、自動的データ抽出、例えば合計金額、発注番号、製品量、発送先などの決定を可能にするために、インボイスは、該インボイスを発行した会社または個人に従って最初に分類される必要がある。通常、自動分類システムを準備するためには、訓練例が必要である。しかしながら、顧客によって提供される訓練例は、誤分類文書または他のノイズ―例えばファックスの表紙−をしばしば含んでおり、それらは、正確な分類を得るために自動分類システムの訓練に先立って識別され除去されねばならない。別の例では、患者記録の分野において、医師によって書かれた報告書と診断との間の矛盾を検出するために役立つ。
【0190】
別の例では、特許庁は持続的に再分類プロセスを実施していることが知られており、その際に特許庁は、(1)混同に対する特許庁の分類法の既存の分岐を評価し、(2)過度に輻輳しているノードを平等に分配するために分類法を再構築し、かつ(3)既存の特許を新たな構造内に再分類する。本明細書に提示されるトランスダクティブ学習法は、特許庁、およびこの作業を外部委託する会社によって、その分類法を再評価し、(1)所与の主要分類に対して新たな分類法を構築し、かつ(2)既存の特許を再分類することで、それを支援するために使用され得る。
【0191】
トランスダクションは、ラベル付きとラベルなしデータから学習し、それによって、ラベル付きデータからラベルなしデータへの移行が滑らかとなる。スペクトルの一方の端部には、完全な予備的知識を有するラベル付きデータがある。すなわち、与えられたラベルは例外なく正しい。他方の端部には、予備的知識が与えられていないラベルなしデータがある。あるレベルのノイズを含む編成されたデータは、ラベル付けに誤りのあるデータを構成し、上述の2つの最端部の間のスペクトル上のどこかに位置している。データの編成によって与えられたラベルは、ある程度まで正しいとして信用され得るが、完全にではない。従って、トランスダクションは、データの所与の編成内に一定のレベルの誤りを仮定することによって、および、これらをラベル割り当てに関する予備的知識における不確実性として解釈することによって、既存のデータ編成を整理するために使用され得る。
【0192】
一実施形態における、データを整理する方法が、図15に提示される。使用時には、ステップ1500で、複数のラベル付きデータ項目が受信され、ステップ1502で、複数のカテゴリの各々に対するデータ項目のサブセットが選択される。さらに、ステップ1504で、各サブセット内のデータ項目に対する不確実性がほぼゼロに設定され、ステップ1506で、サブセット内に存在しないデータ項目に対する不確実性が、ほぼゼロではない所定値に設定される。さらに、ステップ1508で、不確実性、サブセット内のデータ項目、およびサブセット内に存在しないデータ項目を訓練例として用いて、繰り返し計算によってトランスダクティブ分類器が訓練され、ステップ1510で、訓練された分類器が、データ項目の各々を分類するために、ラベル付きデータ項目の各々に適用される。また、ステップ1512で、入力データ項目の分類またはその派生物が、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力される。
【0193】
さらに、サブセットは無作為に選択され得、またユーザによって選択および検証され得る。少なくとも一部のデータ項目のラベルは、分類に基づいて変更され得る。また、データ項目の分類後、所定の閾値を下回る信頼水準を有するデータ項目の識別子が、ユーザに出力され得る。識別子は、文書自体の電子コピー、それらの部分、それらの表題、それらの名前、それらのファイル名、文書へのポインタ、などであり得る。
【0194】
本発明の一実施形態では、図16に示すように、ステップ1600で、整理プロセスを開始する2つの選択肢がユーザに提示される。1つ選択肢は、ステップ1602での完全自動整理であり、この場合には、各概念またはカテゴリに対して、特定数の文書が無作為に選択され、正しく編成されていると見なされる。代替案としては、ステップ1604で、いくつかの文書が、各概念またはカテゴリに対する1つ以上のラベル割り当てが適切に編成されていることの、人手による再調査および検証のために、フラグを立てられ得る。ステップ1606で、データ内のノイズレベルの推定値が受信される。ステップ1610で、検証済み(人手により検証された、または無作為に選択された)データおよびステップ1608の未検証データを用いて、トランスダクティブ分類器が訓練される。ひとたび訓練が終了すれば、文書は、新たなラベルに従って再編成される。ステップ1612で、ラベル割り当てにおいて特定の閾値を下回る低い信頼度を有する文書が、人手による再調査のためにユーザに対して表示される。ステップ1614で、ラベル割り当てにおいて特定の閾値を上回る信頼水準を有する文書が、トランスダクティブラベル割り当てに従って自動的に修正される。
【0195】
別の実施形態における、医療記録を管理する方法が、図17に示される。使用時には、ステップ1700で、医学的診断に基づいて分類器が訓練され、ステップ1702で、複数の医療記録がアクセスされる。さらに、ステップ1704で、分類器を用いて医療記録に関して文書分類手法が実行され、ステップ1706で、医学的診断と関連する低い確率を有する、少なくとも1つの医療記録の識別子が出力される。文書分類手法は、任意の種類の処理、例えばトランスダクティブ処理、などを含み得、かつ、サポートベクタマシン処理、最大エントロピー識別処理などを含む、1つ以上の上述の任意の帰納的手法またはトランスダクティブ手法を含み得る。
【0196】
一実施形態では、分類器はトランスダクティブ分類器であり得、トランスダクティブ分類器は、少なくとも1つの所定コスト要因、少なくとも1つのシード文書、および医療記録を用いた繰り返し計算によって訓練され得、ここで、計算の各繰り返しに対して、コスト要因が期待ラベル値の関数として調整され、その後、訓練された分類器は、医療記録を分類するために使用され得る。シード文書および医療記録に対するデータ点のラベルの事前確率がまた、受信され得、ここで、計算の各繰り返しに対して、データ点のラベルの事前確率が、データ点のクラス帰属確率の推定値に従って調整され得る。
【0197】
本発明の別の実施形態は、動的な、シフトする分類概念に対して責任を負う。例えば、アプリケーションを処理する形式では、文書は、その後の処理に備えて文書を分類するために、文書のレイアウト情報および/または内容情報を用いて分類される。多くのアプリケーションにおいて、文書は静的ではなく、時間と共に進化する。例えば、文書の内容および/またはレイアウトは、新たな法律の制定によって変化し得る。トランスダクティブ分類は、これらの変化に自動的に順応し、ドリフトする分類概念にもかかわらず、同一のまたは同等の分類精度をもたらす。これは、人手による調整なくしては、概念のドリフトによって最初から分類精度に苦しむ、ルールベースシステムまたは帰納的分類法とは対照的である。この一例はインボイス処理であり、それは従来から帰納的学習を含み、またはインボイスのレイアウトを利用するルールベースシステムが用いられる。これら従来のシステムの下では、レイアウトに変化が生じた場合には、新たな訓練データにラベルを付けるか、または新たなルールを定めることによって、システムは手動で再構成されねばならない。しかしながら、トランスダクションの使用は、インボイスのレイアウトの小さな変化にも自動的に順応することによって、手動での再構成を不要とする。別の例では、トランスダクティブ分類は顧客の苦情分析に適用され得、そのような苦情の性質の変化を監視することができる。例えば、会社は、製品の変更を顧客の苦情と自動的に結び付け得る。
【0198】
トランスダクションは、ニュース記事の分類にも用いられ得る。例えば、2001年9月11日のテロリストによる攻撃に関する記事で始まり、アフガニスタンでの戦争を経て、今日のイラク情勢に関するニュース報道内容までの、テロとの戦いに関するニュース記事が、トランスダクションを用いて自動的に特定され得る。
【0199】
さらに別の例では、生物体の分類(アルファ分類学)が、生物体の新たな種を生成し他の種が絶滅することによる進化と共に、時間と共に変化し得る。分類体系または分類学のこれらの法則は、時間と共にシフトまたは変化する分類概念を有する、動的なものであり得る。
【0200】
ラベルなしデータとして分類されるべき入力データを用いることによって、トランスダクションは、シフトする分類概念を認識し得、従って、進化する分類体系に動的に順応し得る。例えば、図18は、ドリフトする分類概念を与えられた、トランスダクションを用いた本発明の一実施形態を示す。ステップ1802に示すように、文書セットDは、時刻tにシステムに入る。ステップ1804で、トランスダクティブ分類器Cが、これまで蓄積されたラベル付きデータおよびラベルなしデータを用いて訓練され、ステップ1806で、セットDの中の文書が分類される。手動モードが用いられる場合には、ステップ1808で判定されたユーザ指定閾値を下回る信頼水準を有する文書が、ステップ1810で、手動による再調査のためにユーザに提示される。ステップ1812に示すように、自動モードでは、ある信頼水準を有する文書が、システムに追加される新たなカテゴリの生成をトリガし、次いで該文書は、その新たなカテゴリに割り当てられる。選択された閾値を上回る信頼水準を有する文書は、ステップ1820A〜1820Bで、現在のカテゴリ1からNまでに分類される。ステップtの前に現在のカテゴリに分類されてきた、現在のカテゴリ内の全文書が、ステップ1822で分類器Cによって再分類され、以前に割り当てられたカテゴリに分類されない全ての文書が、ステップ1824および1826で新たなカテゴリに移される。
【0201】
さらに別の実施形態における、文書内容のシフトに順応する方法が、図19に提示される。文書の内容は、これに限定するものではないが、グラフィカルな内容、文字の内容、レイアウト、ナンバリング、などを含み得る。シフトの例は、時間的なシフト、スタイルのシフト(2人以上の人間が1つ以上の文書に関して作業する場合)、施される処理のシフト、レイアウトのシフト、などを含み得る。ステップ1900で、ラベルなし文書および少なくとも1つの所定コスト要因と共に、少なくとも1つのラベル付きシード文書が受信される。文書は、これに限定するものではないが、顧客の苦情、インボイス、様式文書、領収書、などを含み得る。さらに、ステップ1902で、少なくとも1つの所定コスト要因、少なくとも1つのシード文書、およびラベルなし文書を用いて、トランスダクティブ分類器が訓練される。また、ステップ1904で、所定の閾値を上回る信頼水準を有するラベルなし文書は、分類器を用いて複数のカテゴリに分類され、少なくとも一部のカテゴライズされた文書は、ステップ1906で、分類器を用いてカテゴリに再分類される。さらに、ステップ1908で、カテゴライズされた文書の識別子が、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力される。識別子は、文書自体の電子コピー、それらの部分、それらの表題、それらの名前、それらのファイル名、文書へのポインタ、などであり得る。さらに、製品の変更が、顧客の苦情などと結び付けられ得る。
【0202】
さらに、所定の閾値を下回る信頼水準を有するラベルなし文書が、1つ以上の新たなカテゴリに移され得る。また、少なくとも1つの所定コスト要因、少なくとも1つのシード文書、およびラベルなし文書を用いた繰り返し計算によって、トランスダクティブ分類器が訓練され得、ここで、計算の各繰り返しに対して、コスト要因が期待ラベル値の関数として調整され得、訓練された分類器を用いてラベルなし文書を分類し得る。さらに、シード文書およびラベルなし文書に対するデータ点のラベルの事前確率が、受信され得、ここで、計算の各繰り返しに対して、データ点のラベルの事前確率が、データ点のクラス帰属確率の推定値に従って調整され得る。
【0203】
別の実施形態における、特許分類を文書内容のシフトに対して順応させる方法が、図20に提示される。ステップ2000で、ラベルなし文書と共に、少なくとも1つのラベル付きシード文書が受信される。ラベルなし文書は、任意の種類の文書、例えば、特許出願書類、裁判所提出書類、情報開示フォーム、文書の修正、などを含み得る。シード文書(単数または複数)は、特許文書(単数または複数)、特許出願書類(単数または複数)、などを含み得る。ステップ2002で、少なくとも1つのシード文書およびラベルなし文書を用いて、トランスダクティブ分類器が訓練され、所定の閾値を上回る信頼水準を有するラベルなし文書は、分類器を用いて複数の既存のカテゴリに分類される。分類器は任意の種類の分類器、例えばトランスダクティブ分類器であり得、文書分類手法は任意の手法、例えばサポートベクタマシン処理、最大エントロピー識別処理、などであり得る。例えば、上述の任意の帰納的手法またはトランスダクティブ手法が用いられ得る。
【0204】
また、ステップ2004で、所定の閾値を下回る信頼水準を有するラベルなし文書が、分類器を用いて少なくとも1つの新たなカテゴリに分類され、ステップ2006で、少なくとも一部のカテゴライズされた文書が、分類器を用いて既存のカテゴリおよび少なくとも1つの新たなカテゴリに再分類される。さらに、ステップ2008で、カテゴライズされた文書の識別子が、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力される。また、トランスダクティブ分類器が、少なくとも1つの所定コスト要因、検索クエリ、および文書を用いた繰り返し計算によって訓練され得、ここで、計算の各繰り返しに対して、コスト要因が期待ラベル値の関数として調整され得、訓練された分類器が、文書を分類するために使用され得る。さらに、検索クエリおよび文書に対するデータ点のラベルの事前確率が受信され得、計算の各繰り返しに対して、データ点のラベルの事前確率が、データ点のクラス帰属確率の推定に従って調整される。
【0205】
本発明のさらに別の実施形態は、文書分離の分野における文書のドリフトに対して責任を負う。文書分離に対する1つの実用例は、抵当文書の処理を含む。一連の様々な貸付文書、例えば、融資申込書、融資承認書、融資依頼書、融資金額などからなる、融資関係文書フォルダがスキャンされ、一連の画像内の様々な文書が、その後の処理の前に確認される必要がある。用いられる文書は静的ではなく、時が経つにつれて変化し得る。例えば、融資関係文書フォルダ内で用いられる納税申告用紙は、法律の変更により、時が経つにつれて変化し得る。
【0206】
文書分離は、一連の画像内の文書または部分文書の境界を見出すという問題を解決する。一連の画像を生成する一般的な例は、デジタルスキャナまたは多機能周辺装置(MFP)である。分類の場合と同様に、トランスダクションが、文書およびそれらの境界の経時ドリフトに対処するために、文書分離に用いられ得る。ルールベースシステムまたは帰納的学習による解決に基づくシステムのような静的分離システムは、ドリフトする分離概念に自動的に順応し得ない。これらの静的分離システムの性能は、ドリフトが発生したときは常に、経時低下する。性能をその初期のレベルに維持するためには、ルールに手動で順応させる(ルールベースシステムの場合)か、または手動で新たな文書にラベルを付け、システムを再学習させる(帰納的学習による解決の場合)必要がある。いずれの方法も、時間と費用を要する。文書分離にトランスダクションを適用することにより、分離概念のドリフトに自動的に順応するシステムの開発が可能となる。
【0207】
一実施形態における、文書分離の方法が、図21に提示される。ステップ2100でラベル付きデータが受信され、ステップ2102で、一連のラベルなし文書が受信される。そのようなデータおよび文書は、法定開示文書、拒絶理由通知書、ウェブページデータ、代理人と依頼者との間の往復書簡、などを含み得る。さらに、ステップ2104で、ラベル付きデータおよびラベルなし文書に基づいて、トランスダクションを用いて確率的分類規則が順応され、ステップ2106で、文書分離用に用いられる重みが、確率的分類規則に従って更新される。また、ステップ2108で、一連の文書の中の分離位置が決定され、ステップ2110で、一連の文書の中の決定された分離位置の標識が、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力される。標識は、文書自体の電子コピー、それらの部分、それらの表題、それらの名前、それらのファイル名、文書へのポインタ、などであり得る。さらに、ステップ2112で、文書は、標識と相関するコードのフラグを立てられる。
【0208】
図22は、文書分離と関連して用いられる本発明の分類法および装置の実装を示す。自動文書分離は、デジタルスキャン後の文書の分離および特定に含まれる、人手による努力を低減するために用いられる。1つのそのような文書分類方法は、本明細書に記載する分類方法を用い、分類規則を結合して、入手可能な全情報から可能性が最も高い分離を減じる推論アルゴリズムを使用することによって、ページの連なりを自動的に分離する。図22に示す本発明の一実施形態では、本発明のトランスダクティブMEDの分類法が、文書分離に採用されている。より詳細には、文書ページ2200がデジタルスキャナ2202またはMFPに挿入され、一連のデジタル画像2204に変換される。文書ページは、任意の種類の文書、例えば、特許庁の公報、データベースから取り出されたデータ、従来技術を集めたもの、ウェブサイト、などからのページであり得る。ステップ2206で、一連のデジタル画像が入力され、トランスダクションを用いて、確率的分類規則を動的に順応させる。ステップ2206は、ラベルなしデータとしての一連の画像の2204、およびラベル付きデータ2208を使用する。ステップ2210で、確率的ネットワーク内の重みが更新され、動的に順応された分類規則に従って、自動的文書分離に用いられる。出力ステップ2212は、一連のデジタル化されたページ2214が分離シート2216の自動画像によりインタリーブされる、分離画像の自動挿入の動的順応であり、ステップ2212で、一連の画像に分離シートの画像を自動的に挿入する。本発明の一実施形態では、ソフトウェアで生成された分離ページ2216はまた、分離ページ2216のすぐ後に続くかまたは先行する文書の種類を示し得る。ここで説明するシステムは、経時的に生じる文書のドリフトする分離概念に自動的に順応し、ルールに基づく解決または帰納的機械学習に基づく解決のような静的システムのように、分離精度の低下を被ることはない。アプリケーション処理の形式におけるドリフトする分離概念または分類概念の一般的な例は、先に述べたように、新たな法律の制定による文書の改正である。
【0209】
さらに、図22に示すシステムは、図23に示すシステムに修正され得る。図23に示すシステムでは、ページ2300がデジタルスキャナ2302またはMFPに挿入され、一連のデジタル画像2304に変換される。ステップ2306で、一連のデジタル画像が入力され、トランスダクションを用いて確率的分類規則を動的に順応させる。ステップ2306は、ラベルなしデータとしての一連の画像2304、およびラベル付きデータ2308を使用する。ステップ2310は、採用された動的に順応された分類規則に従って自動文書分離に用いられる、確率的ネットワーク内の重みを更新する。ステップ2312では図18で説明したように分離シート画像を挿入せずに、ステップ2312は、分離情報の自動挿入を動的に順応させ、文書の画像2314に、コード化された記述のフラグを立てる。このようにして、文書ページ画像は、可視化処理されたデータベース2316に入力され得、文書はソフトウェア識別子によってアクセスされ得る。
【0210】
本発明のさらに別の実施形態は、トランスダクションを用いて顔認識を行うことができる。上に述べたように、トランスダクションの利用は、多くの利点、例えば、必要となる訓練例が比較的少数であること、訓練にラベルなしの例を利用できること、などを有する。上述の利点を活用することによって、トランスダクティブ顔認識は、犯罪の検挙のために実装され得る。
【0211】
例えば、国土安全保障省は、テロリストが民間航空機への搭乗を許可されないことを保証しなければならない。空港のスクリーニングプロセスの一部は、空港の検問所で各乗客の写真を撮り、その人物を認識しようとすることであり得る。本システムは先ず、テロリスト容疑者に関して入手可能な限られた写真からの小数の例を用いて、訓練され得る。同じく訓練に用いられ得る、入手可能な同一テロリストのより多くのラベルなし写真がまた、他の捜査当局のデータベースにもあるかもしれない。従って、トランスダクティブ訓練装置は、機能的顔認識システムを生成するために、最初の疎なデータを活用するだけでなく、他の供給源からのラベルなし例をも用いて性能を向上させる。空港の検問所で撮られた写真を処理した後に、トランスダクティブシステムは、対比され得る帰納的システムよりもより正確に、問題の人物を認識することができる。
【0212】
さらに別の実施形態における、顔認識法が、図24に提示される。ステップ2400で、既知の信頼水準を有する少なくとも1つのラベル付きの顔のシード画像が受信される。この少なくとも1つのシード画像は、該画像が指定されたカテゴリに含まれているか否かを示すラベルを有し得る。さらに、ステップ2400で、ラベルなし画像が、例えば、警察、政府系機関、迷子データベース、空港警備部門、またはその他の任意の場所から受信され、少なくとも1つの所定コスト要因が受信される。また、ステップ2402で、少なくとも1つの所定コスト要因、少なくとも1つのシード画像、およびラベルなし画像を用いて、繰り返し計算によって、トランスダクティブ分類器が訓練され、ここで、各計算の繰り返しに対して、コスト要因が期待ラベル値の関数として調整される。少なくとも一部の繰り返しの後に、ステップ2404で、ラベルなしシード画像に対する信頼スコアが格納される。
【0213】
さらに、ステップ2406で、最も高い信頼スコアを有するラベルなし文書の識別子が、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力される。識別子は、文書自体の電子コピー、それらの部分、それらの表題、それらの名前、それらのファイル名、文書へのポインタ、などであり得る。また、各繰り返しの後に、信頼スコアが格納され得、各繰り返しの後に最も高い信頼スコアを有する、ラベルなし画像の識別子が出力される。さらに、ラベル付きとラベルなし画像に対するデータ点のラベルの事前確率が受信され得、計算の各繰り返しに対して、データ点のラベルの事前確率が、データ点のクラス帰属確率の推定に従って調整され得る。さらに、例えば上述の空港の検問所の例からの、顔の第3のラベルなし画像が受信され得、この第3のラベルなし画像は、最も高い信頼スコアを有する少なくとも一部の画像と比較され得、第3のラベルなし画像の顔の信頼度がシード画像の顔と同一である場合には、第3のラベルなし画像の識別子が出力され得る。
【0214】
本発明のさらに別の実施形態は、文書発見システムにフィードバックを提供することによって、ユーザが自身の検索結果を向上させることを可能にする。例えば、インターネットの検索エンジン上で、特許文書または特許出願書類の検索結果など、検索を行っているときに、ユーザは、自身の検索クエリに応答した多数の結果を入手し得る。本発明の一実施形態は、ユーザが検索エンジンから提案された結果を再吟味して、1つ以上の取り出された結果についての関連度、例えば「私が望んだものに近いが、そのものではない」、「全く違う」などをエンジンに報告することを可能にする。ユーザがエンジンにフィードバックを提供するたびに、より良い結果がユーザの再吟味のために優先される。
【0215】
一実施形態における、文書検索法が、図25に提示される。ステップ2500で、検索クエリが受信される。検索クエリは、大文字と小文字を区別するクエリ、ブールクエリ、近似マッチングクエリ、構造化クエリ、などを含む、任意の種類のクエリであり得る。ステップ2502で、検索クエリに基づいた文書が取り出される。さらに、ステップ2504で文書が出力され、ステップ2506で、少なくとも一部の文書に対して、検索クエリへの文書の関連性を示すユーザ入力ラベルが受信される。例えば、ユーザは、クエリから返送された特定の結果が関連性を有するか否かを示し得る。また、ステップ2508で、検索クエリおよびユーザ入力ラベルに基づいて分類器が訓練され、ステップ2510で、文書を再分類するために分類器を用いて、文書に関して文書分類手法が実行される。さらに、ステップ2512で、少なくとも一部の文書の識別子が、文書の分類に基づいて出力される。識別子は、文書自体の電子コピー、それらの部分、それらの表題、それらの名前、それらのファイル名、文書へのポインタ、などであり得る。再分類された文書がまた、最初に出力された最も高い信頼性を有する文書と共に、出力され得る。
【0216】
文書分類手法は、任意の種類の処理、例えば、トランスダクティブ処理、サポートベクタマシン処理、最大エントロピー識別処理、などを含み得る。上述の任意の帰納的手法またはトランスダクティブ手法が、使用され得る。好適な手法では、分類器はトランスダクティブ分類器であり得、トランスダクティブ分類器は、少なくとも1つの所定コスト要因、検索クエリ、および文書を用いて、繰り返し計算によって訓練され得、ここで、計算の各繰り返しに対して、コスト要因が期待ラベル値の関数として調整され得、訓練された分類器が文書を分類するために使用され得る。さらに、検索クエリおよび文書に対するデータ点のラベルの事前確率が受信され得、計算の各繰り返しに対して、データ点のラベルの事前確率が、データ点のクラス帰属確率の推定に従って調整され得る。
【0217】
本発明のさらなる実施形態は、ICR/OCR、および音声認識を向上させるために用いられ得る。例えば、音声認識プログラムおよび音声認識システムの多くの実施形態は、システムを訓練するために、オペレータがいくつかの語を繰り返すことを必要とする。本発明は、例えば電話での会話を聴くことによって、最初に、あらかじめ設定された期間だけユーザの声をモニタして、「未分類」の内容を集め得る。その結果として、ユーザが認識システムの訓練を開始するときに、本システムは、トランスダクティブ学習を活用してモニタした音声を利用し、メモリモデルの構築を支援する。
【0218】
さらに別の実施形態における、インボイスと実体との関連付けを検証する方法が、図26に提示される。ステップ2600で、第1の実体と関連するインボイスの形式に基づいて分類器が訓練される。インボイスの形式は、インボイスの上での荷印の物理的レイアウト、またはインボイスの上のキーワード、インボイス番号、顧客名などのような特徴の、いずれかまたは両方を指すことができる。さらに、ステップ2602で、第1の実体および他の実体のうちの少なくとも1つと関連する旨のラベルが付けられた複数のインボイスがアクセスされ、ステップ2604で、分類器を用いて、インボイスに関して文書分類手法が実行される。例えば、上述の任意の帰納的手法またはトランスダクティブ手法が、文書分類手法として用いられ得る。例えば、文書分類手法は、トランスダクティブ処理、サポートベクタマシン処理、最大エントロピー識別処理、などを含み得る。また、ステップ2606で、第1の実体と関連していない高い確率を有するインボイスのうちの、少なくとも1つの識別子が出力される。
【0219】
さらに、分類器は、任意の種類の分類器、例えばトランスダクティブ分類器であり得、トランスダクティブ分類器は、少なくとも1つの所定コスト要因、少なくとも1つの文書分類、およびインボイスを用いて、繰り返し計算によって訓練され得、計算の各繰り返しに対して、コスト要因が期待ラベル値の関数として調整され、訓練された分類器を用いてインボイスを分類する。また、シード文書およびインボイスに対するデータ点のラベルの事前確率が受信され得、計算の各繰り返しに対して、データ点のラベルの事前確率が、データ点のクラス帰属確率の推定に従って調整される。
【0220】
本明細書に記述された実施形態によって提供される利点の1つは、トランスダクティブアルゴリズムの安定性である。この安定性は、コスト要因のスケーリングおよびラベルの事前確率の調整によって達成される。例えば、一実施形態では、トランスダクティブ分類器は、少なくとも1つのコスト要因、ラベル付きデータ点、およびラベルなしデータ点を訓練例として用いて、繰り返し分類によって訓練される。計算の各繰り返しに対して、ラベルなしデータ点のコスト要因が、期待ラベル値の関数として調整される。さらに、計算の各繰り返しに対して、データ点のラベルの事前確率が、データ点のクラス帰属確率の推定に従って調整される。
【0221】
ワークステーションは、Microsoft Windows(登録商標)オペレーティングシステム(OS)、MAC OS、またはUNIX(登録商標)オペレーティングシステムのような、オペレーティングシステムを搭載して有し得る。好適な実施形態がまた、言及したもの以外のプラットフォームおよびオペレーティングシステム上で実装され得ることが、理解される。好適な実施形態は、JAVA(登録商標)、XML、C、および/またはC++言語、または他のプログラミング言語、また、オブジェクト指向のプログラム方法論を用いて、記述され得る。複雑なアプリケーションを開発するためにますます多く用いられる、オブジェクト指向プログラミング(OOP)が、使用され得る。
【0222】
上述のアプリケーションは、トランスダクティブ学習を用いて、帰納的顔認識システムに困難をもたらす極めて疎なデータの問題を克服する。トランスダクティブ学習のこの局面は、このアプリケーションに限定されるものではなく、疎なデータに起因する他の機械学習上の問題を解決するために使用され得る。
【0223】
当業者は、本明細書において開示される本発明の種々の実施形態の範囲および精神内にある、変形形態を工夫し得る。さらに、本明細書において開示される実施形態の種々の特徴は、単独で、または相互の様々な組み合わせの形で用いられ得、本明細書において記載される特定の組み合わせに限定されることを意図されてはいない。従って、特許請求の範囲は、例示された実施形態によって限定されない。
【図面の簡単な説明】
【0224】
【図1】図1は、ラベル帰納に応用されたMED識別学習を採り入れることによって得られる、分類スコアの関数として期待ラベルをプロットしたチャートの描画である。
【図2】図2A〜図2Hは、トランスダクティブMED学習によって得られる、決定関数の計算の繰り返しを示す、一連のプロットの描画である。
【図3】図3A〜図3Hは、本発明の一実施形態の、改良されたトランスダクティブMED学習によって得られる、決定関数の計算の繰り返しを示す、一連のプロットの描画である。
【図4】図4は、スケーリングされたコスト要因を用いる本発明の一実施形態による、ラベルなしデータの分類のための制御流れ図を示す。
【図5】図5は、ユーザ定義の事前確率情報を用いる本発明の一実施形態による、ラベルなしデータの分類のための制御流れ図を示す。
【図6】図6は、スケーリングされたコスト要因および事前確率情報と共に最大エントロピー識別を用いる、本発明の一実施形態による、ラベルなしデータの分類のための詳細な制御流れ図を示す。
【図7】図7は、本明細書に記載される種々の実施形態が実装され得る、ネットワークアーキテクチャを示す、ネットワーク図である。
【図8】図8は、ユーザ装置と関連付けられる代表的なハードウェア環境の系統図である。
【図9】図9は、本発明の一実施形態の装置のブロック図を示す。
【図10】図10は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図11】図11は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図12】図12は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図13】図13は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図14】図14は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図15】図15は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図16】図16は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図17】図17は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図18】図18は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図19】図19は、一実施形態に従って実行される分類プロセスを、フローチャートで示す。
【図20】図20は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図21】図21は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図22】図22は、第1の文書分離システムに適用された本発明の、一実施形態の方法を示す制御流れ図を示す。
【図23】図23は、第2の分離システムに適用された本発明の、一実施形態の方法を示す制御流れ図を示す。
【図24】図24は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図25】図25は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図26】図26は、一実施形態に従って実行される分類プロセスを、フローチャートに示す。
【図27】図27は、一実施形態に従って実行される分類プロセスを、フローチャートで示す。
【図28】図28は、一実施形態に従って実行される分類プロセスを、フローチャートで示す。
【図29】図29は、一実施形態に従って実行される分類プロセスを、フローチャートで示す。

【特許請求の範囲】
【請求項1】
コンピュータベースのシステムにおける、データ分類の方法であって、
ラベル付きデータ点を受信するステップであって、該ラベル付きデータ点の各々が、該データ点が指定されたカテゴリに含まれるべきデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されるデータ点に対する訓練例であるのかを示す、少なくとも1つのラベルを有する、ステップと、
ラベルなしデータ点を受信するステップと、
該ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因を受信するステップと、
該少なくとも1つのコスト要因ならびに該ラベル付きデータ点および該ラベルなしデータ点を訓練例として用いる繰り返し計算によって、最大エントロピー識別(MED)を用いてトランスダクティブ分類器を訓練するステップであって、計算の各繰り返しに対して、該ラベルなしデータ点のコスト要因が期待ラベル値の関数として調整され、データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に従って調整される、ステップと、
該ラベルなしデータ点、該ラベル付きデータ点、および入力データ点のうちの少なくとも1つを分類するために、該訓練された分類器を適用するステップと、
該分類されたデータ点の分類、またはその派生物を、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力するステップと、
を包含する、方法。
【請求項2】
前記関数は、データ点の前記期待ラベルの絶対値である、請求項1に記載の方法。
【請求項3】
ラベル付きとラベルなしデータ点の事前確率情報を受信するステップ、をさらに包含する、請求項1に記載の方法。
【請求項4】
前記トランスダクティブ分類器は、前記ラベル付きとラベルなしデータの事前確率情報を用いて学習する、請求項3に記載の方法。
【請求項5】
前記記ラベル付きデータと前記ラベルなしデータとをそれらの期待ラベルに従って学習例として利用して、前記含まれる訓練例および除外される訓練例を与えられた決定関数パラメータに対してガウス事前分布を用いて、最小のKLダイバージェンスを有する決定関数を決定する、さらなるステップを包含する、請求項1に記載の方法。
【請求項6】
決定関数パラメータに対して多項事前分布を用いて、最小のKLダイバージェンスを有する決定関数を決定する、さらなるステップを包含する、請求項1に記載の方法。
【請求項7】
トランスダクティブ分類器を訓練する前記繰り返しステップは、データ値の収束に到達するまで反復される、請求項1に記載の方法。
【請求項8】
前記トランスダクティブ分類器の決定関数の変化が所定の閾値を下回ったときに、収束に到達する、請求項7に記載の方法。
【請求項9】
決定された期待ラベル値の変化が所定の閾値を下回ったときに、収束に到達する、請求項7に記載の方法。
【請求項10】
前記含まれる訓練例の前記ラベルは+1の値を有し、前記除外される訓練例のラベルは−1の値を有する、請求項1に記載の方法。
【請求項11】
前記含まれる例の前記ラベルは第1の数値にマッピングされ、前記除外される例の前記ラベルは第2の数値にマッピングされる、請求項1に記載の方法。
【請求項12】
前記ラベル付きデータ点をコンピュータのメモリ内に格納するステップと、
前記ラベルなしデータ点をコンピュータのメモリ内に格納するステップと、
前記入力データ点をコンピュータのメモリ内に格納するステップと、
前記ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因をコンピュータのメモリ内に格納するステップと、
をさらに包含する、請求項1に記載の方法。
【請求項13】
コンピュータシステム上に配備され実行されるコンピュータ実行可能なプログラムコードを提供するステップを包含する、データ分類の方法であって、
該プログラムコードは、
ラベル付きデータ点の各々が、該データ点が指定されたカテゴリに含まれるべきデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されるデータ点に対する訓練例であるのかを示す少なくとも1つのラベルを有する、コンピュータのメモリ内に格納された該ラベル付きデータ点にアクセスし、
コンピュータのメモリからラベルなしデータ点にアクセスし、
コンピュータのメモリから該ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因にアクセスし、
該少なくとも1つの格納されたコスト要因ならびに格納されたラベル付きデータ点および格納されたラベルなしデータ点を用いて、繰り返し計算によって最大エントロピー識別(MED)トランスダクティブ分類器を訓練し、計算の各繰り返しに対して、該ラベルなしデータ点のコスト要因が期待ラベル値の関数として調整され、データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に従って調整され、
該ラベルなしデータ点、該ラベル付きデータ点、および入力データ点のうちの少なくとも1つを分類するために、該訓練された分類器を適用し、
該分類されたデータ点の分類、またはその派生物を、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力する、
ための命令を備える、
方法。
【請求項14】
前記関数は、データ点の前記期待ラベルの絶対値である、請求項13に記載の方法。
【請求項15】
コンピュータのメモリ内に格納されたラベル付きとラベルなしデータ点の事前確率情報にアクセスするステップ、をさらに包含する、請求項13に記載の方法。
【請求項16】
各繰り返しに対して、前記事前確率情報がデータ点のクラス帰属確率の推定値に従って調整される、請求項15に記載の方法。
【請求項17】
前記ラベル付きとラベルなしデータをそれらの期待ラベルに従って学習例として利用して、前記含まれる訓練例および除外される訓練例を与えられた決定関数パラメータの事前分布に対して最小のKLダイバージェンスを有する決定関数を決定するための命令を、さらに備える、請求項13に記載の方法。
【請求項18】
トランスダクティブ分類器を訓練する前記繰り返しステップは、データ値の収束に到達するまで反復される、請求項13に記載の方法。
【請求項19】
トランスダクティブ分類の決定関数の変化が所定の閾値を下回ったときに、収束に到達する、請求項18に記載の方法。
【請求項20】
決定された期待ラベル値の変化が所定の閾値を下回ったときに、収束に到達する、請求項18に記載の方法。
【請求項21】
前記含まれる訓練例の前記ラベルは+1の値を有し、前記除外される訓練例の前記ラベルは−1の値を有する、請求項13に記載の方法。
【請求項22】
前記含まれる例の前記ラベルは第1の数値にマッピングされ、前記除外される例の前記ラベルは第2の数値にマッピングされる、請求項13に記載の方法。
【請求項23】
データ処理装置であって、該装置は、
(i)ラベル付きデータ点の各々が、該データ点が指定されたカテゴリに含まれるべきデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されるデータ点に対する訓練例であるのかを示す、少なくとも1つのラベルを有する、該ラベル付きデータ点と、(ii)ラベルなしデータ点と、(iii)該ラベル付きとラベルなしデータ点の少なくとも1つの所定コスト要因と、を格納する、少なくとも1つのメモリと、
該少なくとも1つの格納されたコスト要因ならびに格納されたラベル付きデータ点および格納されたラベルなしデータ点を訓練例として用いて、トランスダクティブ最大エントロピー識別(MED)を用いてトランスダクティブ分類器に繰り返し教示するためのトランスダクティブ分類器訓練装置であって、MED計算の各繰り返しにおいて、該ラベルなしデータ点の該コスト要因が期待ラベル値の関数として調整され、データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に従って調整される、訓練装置と、
を備え、
該トランスダクティブ分類器訓練装置によって訓練された分類器は、該ラベルなしデータ点、該ラベル付きデータ点、および入力データ点のうちの少なくとも1つを分類するために用いられ、
該分類されたデータ点の分類、またはその派生物が、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力される、
装置。
【請求項24】
前記関数は、データ点の前記期待ラベルの絶対値である、請求項23に記載の装置。
【請求項25】
前記メモリは、ラベル付きとラベルなしデータ点の事前確率情報をも格納する、請求項23に記載の装置。
【請求項26】
前記MED計算の各繰り返しにおいて、前記事前確率情報がデータ点のクラス帰属確率の推定値に従って調整される、請求項25に記載の装置。
【請求項27】
前記ラベル付きとラベルなしデータをそれらの期待ラベルに従って学習例として用いて、前記含まれる訓練例および除外される訓練例を与えられた決定関数の事前分布に対して、最小のKLダイバージェンスを有する該決定関数を決定するためのプロセッサをさらに備える、請求項23に記載の装置。
【請求項28】
データ値の収束を判定し、収束の判定と同時に計算を終了する手段をさらに備える、請求項23に記載の装置。
【請求項29】
前記トランスダクティブ分類器計算の決定関数の変化が所定の閾値を下回ったときに、収束に到達する、請求項28に記載の装置。
【請求項30】
決定された期待ラベル値の変化が所定の閾値を下回ったときに、収束に到達する、請求項28に記載の装置。
【請求項31】
前記含まれる訓練例の前記ラベルは+1の値を有し、前記除外される訓練例の前記ラベルは−1の値を有する、請求項23に記載の装置。
【請求項32】
前記含まれる例の前記ラベルは第1の数値にマッピングされ、前記除外される例の前記ラベルは第2の数値にマッピングされる、請求項23に記載の装置。
【請求項33】
コンピュータによって読み取り可能なプログラム格納媒体を備える製品であって、該媒体は、コンピュータによって実行可能な命令の1つ以上のプログラムを明白に具体化してデータ分類の方法を実行し、該方法は、
ラベル付きデータ点の各々が、該データ点が指定されたカテゴリに含まれるべきデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されたデータ点に対する訓練例であるのかを示す、少なくとも1つのラベルを有する該ラベル付きデータ点を受信するステップと、
ラベルなしデータ点を受信するステップと、
該ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定のコスト要因を受信するステップと、
該少なくとも1つの格納されたコスト要因ならびに格納されたラベル付きデータ点および格納されたラベルなしデータ点を訓練例として用いて、繰り返し最大エントロピー識別(MED)計算によってトランスダクティブ分類器を訓練するステップであって、該MED計算の各繰り返しにおいて、該ラベルなしデータ点のコスト要因が期待ラベル値の関数として調整され、データ点の事前確率がデータ点のクラス帰属確率の推定値に従って調整される、ステップと、
該ラベルなしデータ点、該ラベル付きデータ点、および入力データ点のうちの少なくとも1つを分類するために、該訓練された分類器を適用するステップと、
該分類されたデータ点の分類、またはその派生物を、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力するステップと、
を包含する、
製品。
【請求項34】
前記関数は、データ点の前記期待ラベルの絶対値である、請求項33に記載の製品。
【請求項35】
前記方法は、ラベル付きとラベルなしデータ点の事前確率情報をコンピュータのメモリ内に格納するステップをさらに包含する、請求項33に記載の製品。
【請求項36】
前記MED計算の各繰り返しにおいて、前記事前確率情報がデータ点のクラス帰属確率の推定値に従って調整される、請求項35に記載の製品。
【請求項37】
前記方法は、前記ラベル付きとラベルなしデータをそれらの期待ラベルに従って学習例として用いて、前記含まれる訓練例および除外される訓練例を与えられた決定関数パラメータの事前分布に対して、最小のKLダイバージェンスを有する該決定関数を決定する、さらなるステップを包含する、請求項33に記載の製品。
【請求項38】
トランスダクティブ分類器を訓練する前記繰り返しステップは、データ値の収束に到達するまで反復される、請求項33に記載の製品。
【請求項39】
前記トランスダクティブ分類の決定関数の変化が所定の閾値を下回ったときに、収束に到達する、請求項38に記載の製品。
【請求項40】
決定された期待ラベル値の変化が所定の閾値を下回ったときに、収束に到達する、請求項38に記載の製品。
【請求項41】
前記含まれる訓練例の前記ラベルは+1の値を有し、前記除外される訓練例の前記ラベルは−1の値を有する、請求項33に記載の製品。
【請求項42】
前記含まれる例の前記ラベルは第1の数値にマッピングされ、前記除外される例の前記ラベルは第2の数値にマッピングされる、請求項33に記載の製品。
【請求項43】
コンピュータベースのシステムにおける、ラベルなしデータの分類の方法であって、
ラベル付きデータ点を受信するステップであって、該データ点が指定されたカテゴリに含まれるべきデータ点に対する訓練例であるのか、あるいは指定されたカテゴリから除外されるデータ点に対する訓練例であるのかを示す、少なくとも1つのラベルを、該ラベル付きデータ点の各々が有する、ステップと、
ラベル付きとラベルなしデータ点を受信するステップと、
ラベル付きデータ点およびラベルなしデータ点の事前ラベル確率情報を受信するステップと、
該ラベル付きデータ点およびラベルなしデータ点の少なくとも1つの所定コスト要因を受信するステップと、
該データ点の該ラベルの事前確率に従って、各ラベル付きとラベルなしデータ点に対する期待ラベルを決定するステップと、
データ値が実質的に収束するまで、以下の下位ステップ、すなわち
・該データ点の期待ラベルの絶対値に比例して各ラベルなしデータ点に対するスケーリングされたコスト値を生成するステップと、
・該ラベル付きとラベルなしデータをそれらの期待ラベルに従って訓練例として用いて、該含まれる訓練例および除外される訓練例を与えられた決定関数パラメータの事前確率分布に対してKLダイバージェンスを最小化する該決定関数を算出することによって、分類器を訓練するステップと、
・該訓練された分類器を用いて、該ラベル付きとラベルなしデータ点の分類スコアを決定するステップと、
・該訓練された分類器の出力をクラス帰属確率に対して較正するステップと、
・決定された該クラス帰属確率に従って該ラベルなしデータ点の該ラベルの事前確率を更新するステップと、
・該更新されたラベルの事前確率および先に決定された分類スコアを用いて、最大エントロピー識別(MED)を用いて該ラベルおよびマージンの確率分布を決定するステップと、
・該先に決定されたラベルの確率分布を用いて、新たな期待ラベルを計算するステップと、
・前回の繰り返しによる該期待ラベルで該新たな期待ラベルを補間することによって、各データ点に対する期待ラベルを更新するステップと、
を繰り返すステップと、
該入力データ点の分類、またはその派生物を、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力するステップと、
を包含する、方法。
【請求項44】
前記決定関数の変化が所定の閾値を下回ったときに、収束に到達する、請求項43に記載の方法。
【請求項45】
決定された期待ラベル値の変化が所定の閾値を下回ったときに、収束に到達する、請求項43に記載の方法。
【請求項46】
前記含まれる訓練例の前記ラベルは+1の値を有し、前記除外される訓練例の前記ラベルは−1の値を有する、請求項43に記載の方法。
【請求項47】
ラベル割り当てに関する既知の信頼水準を有する、少なくとも1つのラベル付きシード文書を受信するステップと、
ラベルなし文書を受信するステップと、
少なくとも1つの所定コスト要因を受信するステップと、
該少なくとも1つの所定コスト要因、該少なくとも1つのシード文書、および該ラベルなし文書を用いて、繰り返し計算によってトランスダクティブ分類器を訓練するステップであって、該計算の各繰り返しに対して、該コスト要因が期待ラベル値の関数として調整される、ステップと、
少なくとも一部の該繰り返しの後に、該ラベルなし文書に対する信頼スコアを格納するステップと、
最も高い信頼スコアを有する該ラベルなし文書の識別子を、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力するステップと、
を包含する、文書を分類する方法。
【請求項48】
前記少なくとも1つのシード文書は、キーワードのリストを有する、請求項47に記載の方法。
【請求項49】
信頼スコアが、前記各繰り返しの後に格納され、各繰り返しの後に、前記最も高い信頼スコアを有する前記ラベルなし文書の識別子が出力される、請求項47に記載の方法。
【請求項50】
前記ラベル付きとラベルなし文書に対するデータ点のラベルの事前確率を受信するステップ、をさらに包含する、請求項47に記載の方法であって、前記計算の各繰り返しに対して、該データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に従って調整される、方法。
【請求項51】
法的事項と関連する文書を受信するステップと、
該文書に関して文書分類手法を実行するステップと、
該文書の分類に基づいて、該文書の少なくとも一部の識別子を出力するステップと、
を包含する、法的開示手続と関連する文書を分析する方法。
【請求項52】
前記文書分類手法は、トランスダクティブ処理を含む、請求項51に記載の方法。
【請求項53】
少なくとも1つの所定コスト要因、少なくとも1つのシード文書、および法的事項と関連する文書を用いて、繰り返し計算によってトランスダクティブ分類器を訓練するステップであって、該計算の各繰り返しに対して、該コスト要因が期待ラベル値の関数として調整される、ステップをさらに包含する、請求項52に記載の方法。
【請求項54】
前記ラベル付きとラベルなし文書に対するデータ点のラベルの事前確率を受信するステップをさらに包含する、請求項53に記載の方法であって、前記計算の各繰り返しに対して、該データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に応じて調整される、方法。
【請求項55】
前記文書分類手法は、サポートベクタマシン処理を含む、請求項51に記載の方法。
【請求項56】
前記文書分類手法は、最大エントロピー識別処理を含む、請求項51に記載の方法。
【請求項57】
前記文書間のリンクを表すものを出力するステップをさらに包含する、請求項51に記載の方法。
【請求項58】
複数のラベル付きデータ項目を受信するステップと、
複数のカテゴリの各々に対する該データ項目のサブセットを選択するステップと、
各サブセット内の該データ項目に対する不確実性を、ほぼゼロに設定するステップと、
該サブセット内に存在しない該データ項目に対する不確実性を、ほぼゼロではない所定値に設定するステップと、
該不確実性、該サブセット内のデータ項目、および該サブセット内に存在しない該データ項目を訓練例として用いて、繰り返し計算によってトランスダクティブ分類器を訓練するステップと、
該データ項目の各々を分類するために、該訓練された分類器を該ラベル付きデータ項目の各々に適用するステップと、
該入力データ項目の分類、またはその派生物を、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力するステップと、
を包含する、データを整理する方法。
【請求項59】
前記サブセットは、無作為に選択される、請求項58に記載の方法。
【請求項60】
前記サブセットは、ユーザによって選択および検証される、請求項58に記載の方法。
【請求項61】
前記分類に基づいて、少なくとも一部の前記データ項目の前記ラベルを変更するステップ、をさらに包含する、請求項58に記載の方法。
【請求項62】
データ項目の分類後に、所定の閾値を下回る信頼水準を有するデータ項目の識別子がユーザに出力される、請求項58に記載の方法。
【請求項63】
第1の実体と関連するインボイスの形式に基づいて分類器を訓練するステップと、
該第1の実体および他の実体のうちの少なくとも1つと関連する旨のラベルが付けられた複数のインボイスにアクセスするステップと、
該分類器を用いて、該インボイスに関して文書分類手法を実行するステップと、
該第1の実体と関連していない高い確率を有する該インボイスのうちの少なくとも1つの識別子を出力するステップと、
を包含する、インボイスと実体との関連性を検証する方法。
【請求項64】
前記文書分類手法は、トランスダクティブ処理を含む、請求項63に記載の方法。
【請求項65】
前記分類器はトランスダクティブ分類器である、請求項64に記載の方法であって、該方法は、少なくとも1つの所定コスト要因、少なくとも1つのシード文書、および前記インボイスを用いて、繰り返し計算によって該トランスダクティブ分類器を訓練するステップであって、該計算の各繰り返しに対して、該コスト要因が期待ラベル値の関数として調整される、ステップと、該訓練された分類器を用いて該インボイスを分類するステップと、を包含する、方法。
【請求項66】
前記シード文書およびインボイスに対するデータ点のラベルの事前確率を受信するステップをさらに包含する、請求項65に記載の方法であって、前記計算の各繰り返しに対して、該データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に従って調整される、方法。
【請求項67】
前記文書分類手法は、サポートベクタマシン処理を含む、請求項63に記載の方法。
【請求項68】
前記文書分類手法は、最大エントロピー識別処理を含む、請求項63に記載の方法。
【請求項69】
医学的診断に基づいて分類器を訓練するステップと、
複数の医療記録にアクセスするステップと、
該分類器を用いて、該医療記録に関して文書分類手法を実行するステップと、
該医学的診断と関連する低い確率を有する該医療記録のうちの少なくとも1つの識別子を出力するステップと、
を包含する、医療記録を管理する方法。
【請求項70】
前記文書分類手法は、トランスダクティブ処理を含む、請求項69に記載の方法。
【請求項71】
前記分類器はトランスダクティブ分類器である、請求項70に記載の方法であって、少なくとも1つの所定コスト要因、少なくとも1つのシード文書、および前記医療記録を用いて、繰り返し計算によって該トランスダクティブ分類器を訓練するステップであって、該計算の各繰り返しに対して、該コスト要因が期待ラベル値の関数として調整される、ステップと、該医療記録を分類するために該訓練された分類器を使用するステップと、をさらに包含する、方法。
【請求項72】
前記シード文書および医療記録に対するデータ点のラベルの事前確率を受信するステップをさらに包含する、請求項71に記載の方法であって、前記計算の各繰り返しに対して、該データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に従って調整される、方法。
【請求項73】
前記文書分類手法は、サポートベクタマシン処理を含む、請求項69に記載の方法。
【請求項74】
前記文書分類手法は、最大エントロピー識別処理を含む、請求項69に記載の方法。
【請求項75】
既知の信頼水準を有する、少なくとも1つの顔のラベル付きシード画像を受信するステップと、
ラベルなし画像を受信するステップと、
少なくとも1つの所定コスト要因を受信するステップと、
該少なくとも1つの所定コスト要因、該少なくとも1つのシード画像、および該ラベルなし画像を用いて、繰り返し計算によってトランスダクティブ分類器を訓練するステップであって、該計算の各繰り返しに対して、該コスト要因が期待ラベル値の関数として調整される、ステップと、
少なくとも一部の該繰り返しの後に、ラベルなしシード画像に対する信頼スコアを格納するステップと、
最も高い信頼スコアを有する該ラベルなし画像の識別子を、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力するステップと、
を包含する、顔認識方法。
【請求項76】
前記少なくとも1つのシード画像は、該画像が指定されたカテゴリに含まれているか否かを示すラベルを有する、請求項75に記載の方法。
【請求項77】
信頼スコアが、各前記繰り返しの後に格納され、各繰り返しの後に前記最も高い信頼スコアを有する前記ラベルなし画像の識別子が出力される、請求項75に記載の方法。
【請求項78】
前記ラベル付きとラベルなし画像に対するデータ点のラベルの事前確率を受信するステップ、をさらに包含する、請求項75に記載の方法であって、前記計算の各繰り返しに対して、該データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に従って調整される、方法。
【請求項79】
顔の第3のラベルなし画像を受信するステップと、該第3のラベルなし画像を前記最も高い信頼スコアを有する前記画像の少なくとも一部と比較するステップと、該第3のラベルなし画像の顔の信頼度が前記シード画像の前記顔と同一である場合には、該第3のラベルなし画像の識別子を出力するステップと、をさらに包含する、請求項75に記載の方法。
【請求項80】
検索クエリに基づいて分類器を訓練するステップと、
複数の従来技術文書にアクセスするステップと、
該分類器を用いて、該従来技術文書に関して文書分類手法を実行するステップと、
該従来技術文書の分類に基づいて、該従来技術文書の少なくとも一部の識別子を出力するステップと、
を包含する、従来技術文書を分析する方法。
【請求項81】
前記文書分類手法は、トランスダクティブ処理を含む、請求項80に記載の方法。
【請求項82】
前記分類器はトランスダクティブ分類器である、請求項81に記載の方法であって、少なくとも1つの所定コスト要因、少なくとも1つのシード文書、および前記従来技術文書を用いて、繰り返し計算によって該トランスダクティブ分類器を訓練するステップであって、該計算の各繰り返しに対して、該コスト要因が期待ラベル値の関数として調整される、ステップと、該従来技術文書を分類するために該訓練された分類器を用いるステップと、を包含する、方法。
【請求項83】
前記シード文書および従来技術文書に対するデータ点のラベルの事前確率を受信するステップをさらに包含する、請求項82に記載の方法であって、前記計算の各繰り返しに対して、データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に従って調整される、方法。
【請求項84】
前記検索クエリは、特許開示情報の少なくとも一部を含む、請求項80に記載の方法。
【請求項85】
前記検索クエリは、特許文書または特許出願書類から取り出された請求項の少なくとも一部を含む、請求項80に記載の方法。
【請求項86】
前記検索クエリは、特許文書または特許出願書類の要約書の少なくとも一部を含む、請求項80に記載の方法。
【請求項87】
前記検索クエリは、特許文書または特許出願書類から取り出された概要の少なくとも一部を含む、請求項80に記載の方法。
【請求項88】
前記文書分類手法は、サポートベクタマシン処理を含む、請求項80に記載の方法。
【請求項89】
前記文書分類手法は、最大エントロピー識別処理を含む、請求項80に記載の方法。
【請求項90】
前記従来技術文書は、特許庁の公開文書である、請求項80に記載の方法。
【請求項91】
前記文書間のリンクを表すものを出力するステップ、をさらに包含する、請求項80に記載の方法。
【請求項92】
前記従来技術文書の分類に基づいて、該従来技術文書の少なくとも一部の関連性スコアを出力するステップをさらに包含する、請求項80に記載の方法。
【請求項93】
少なくとも1つのラベル付きシード文書を受信するステップと、
ラベルなし文書を受信するステップと、
該少なくとも1つのシード文書および該ラベルなし文書を用いてトランスダクティブ分類器を訓練するステップと、
該分類器を用いて、所定の閾値を上回る信頼水準を有する該ラベルなし文書を複数の既存のカテゴリに分類するステップと、
該分類器を用いて、所定の閾値を下回る信頼水準を有する該ラベルなし文書を少なくとも1つの新たなカテゴリに分類するステップと、
該分類器を用いて、該カテゴライズされた文書の少なくとも一部を、該既存のカテゴリおよび該少なくとも1つの新たなカテゴリに再分類するステップと、
該カテゴライズされた文書の識別子を、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力するステップと、
を包含する、文書内容のシフトに特許分類を順応させる方法。
【請求項94】
前記分類器はトランスダクティブ分類器である、請求項93に記載の方法であって、少なくとも1つの所定コスト要因、検索クエリ、および前記文書を用いて、繰り返し計算によって該トランスダクティブ分類器を訓練するステップであって、該計算の各繰り返しに対して、該コスト要因が期待ラベル値の関数として調整される、ステップと、該文書を分類するために該訓練された分類器を用いるステップと、をさらに包含する、方法。
【請求項95】
前記検索クエリおよび文書に対するデータ点のラベルの事前確率を受信するステップをさらに包含する、請求項94に記載の方法であって、前記計算の各繰り返しに対して、該データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に従って調整される、方法。
【請求項96】
前記文書分類手法は、サポートベクタマシン処理を含む、請求項93に記載の方法。
【請求項97】
前記文書分類手法は、最大エントロピー識別処理を含む、請求項93に記載の方法。
【請求項98】
前記ラベルなし文書は特許出願書類である、請求項93に記載の方法。
【請求項99】
前記少なくとも1つのシード文書は、特許文書および特許出願書類からなる群から選択される、請求項93に記載の方法。
【請求項100】
特許文書または特許出願書類の少なくとも1つの請求項に基づいて分類器を訓練するステップと、
複数の文書にアクセスするステップと、
該分類器を用いて、該文書の少なくとも一部に関して文書分類手法を実行するステップと、
該文書の分類に基づいて、該文書の少なくとも一部の識別子を出力するステップと、
を包含する、文書を請求項にマッチングする方法。
【請求項101】
前記文書の前記分類に基づいて、該文書の少なくとも一部の関連性スコアを出力するステップ、をさらに包含する、請求項100に記載の方法。
【請求項102】
前記文書は従来技術文書である、請求項100に記載の方法。
【請求項103】
前記文書は製品について記載する、請求項100に記載の方法。
【請求項104】
特定の特許分類に存在することが知られている複数の文書に基づいて、分類器を訓練するステップと、
特許文書または特許出願書類の少なくとも一部を受信するステップと、
該分類器を用いて、該特許文書または特許出願書類の該少なくとも一部に関して、文書分類手法を実行するステップと、
該特許文書または特許出願書類の分類を出力するステップと、
を包含する、特許文書または特許出願書類を分類する方法であって、
該文書分類手法は、はい/いいえ式分類手法である、方法。
【請求項105】
前記文書は、特許文書および特許出願書類からなる群から選択される、請求項104に記載の方法。
【請求項106】
前記特許文書または特許出願書類の前記少なくとも一部は、特許文書または特許出願書類から取り出された請求項の少なくとも一部を含む、請求項105に記載の方法。
【請求項107】
前記特許文書または特許出願書類の前記少なくとも一部は、特許文書または特許出願書類の要約書の少なくとも一部を含む、請求項105に記載の方法。
【請求項108】
前記特許文書または特許出願書類の前記少なくとも一部は、特許文書または特許出願書類から取り出された概要の少なくとも一部を含む、請求項105に記載の方法。
【請求項109】
特定の特許分類と関連する少なくとも1つの文書に基づいて訓練された分類器を用いて、特許文書または特許出願書類の少なくとも部分に関して文書分類手法を実行するステップであって、該文書分類手法は、はい/いいえ式分類手法である、ステップと、
該特許文書または特許出願書類の分類を出力するステップと、
を包含する、特許文書または特許出願書類を分類する方法。
【請求項110】
第2の特許分類に存在することが知られている複数の文書に基づいて訓練された異なる分類器を用いて、前記方法を反復するステップをさらに包含する、請求項109に記載の方法。
【請求項111】
前記特許文書または特許出願書類の前記少なくとも一部は、特許文書または特許出願書類から取り出された請求項の少なくとも一部を含む、請求項109に記載の方法。
【請求項112】
前記特許文書または特許出願書類の前記少なくとも一部は、特許文書または特許出願書類の要約書の少なくとも一部を含む、請求項109に記載の方法。
【請求項113】
前記特許文書または特許出願書類の前記少なくとも一部は、特許文書または特許出願書類から取り出された概要の少なくとも一部を含む、請求項109に記載の方法。
【請求項114】
少なくとも1つのラベル付きシード文書を受信するステップと、
ラベルなし文書を受信するステップと、
少なくとも1つの所定コスト要因を受信するステップと、
該少なくとも1つの所定コスト要因、該少なくとも1つのシード文書、および該ラベルなし文書を用いて、トランスダクティブ分類器を訓練するステップと、
該分類器を用いて、所定の閾値を上回る信頼水準を有する該ラベルなし文書を複数のカテゴリに分類するステップと、
該カテゴライズされた文書の識別子を、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力するステップと、
を包含する、文書内容のシフトに順応する方法。
【請求項115】
前記所定の閾値を下回る信頼水準を有するラベルなし文書を、1つ以上の新たなカテゴリに移すステップ、をさらに包含する、請求項114に記載の方法。
【請求項116】
少なくとも1つの所定コスト要因、前記少なくとも1つのシード文書、および前記ラベルなし文書を用いて、繰り返し計算によって前記トランスダクティブ分類器を訓練するステップであって、該計算の各繰り返しに対して、該コスト要因が期待ラベル値の関数として調整される、ステップと、該ラベルなし文書を分類するために該訓練された分類器を用いるステップと、をさらに包含する、請求項114に記載の方法。
【請求項117】
前記シード文書およびラベルなし文書に対するデータ点のラベルの事前確率を受信するステップ、をさらに包含する、請求項116に記載の方法であって、前記計算の各繰り返しに対して、該データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に従って調整される、方法。
【請求項118】
前記ラベルなし文書は顧客の苦情である、請求項114に記載の方法であって、製品の変更を顧客の苦情とリンクするステップをさらに包含する、方法。
【請求項119】
前記ラベルなし文書はインボイスである、請求項114に記載の方法。
【請求項120】
ラベル付きデータを受信するステップと、
ラベルなし文書の連なりを受信するステップと、
該ラベル付きデータおよび該ラベルなし文書に基づいて、トランスダクションを用いて確率的分類規則を順応させるステップと、
該確率的分類規則に従って、文書分離に用いられる重みを更新するステップと、
該文書の連なりにおける分離位置を決定するステップと、
該連なりにおける該決定された該分離位置の標識を、ユーザ、別のシステム、および別のプロセスの少なくとも1つに出力するステップと、
該標識と相関するコードのフラグを、該文書に立てるステップと、
を包含する、文書を分離する方法。
【請求項121】
検索クエリを受信するステップと、
該検索クエリに基づいて文書を取り出すステップと、
該文書を出力するステップと、
該文書の少なくとも一部に対するユーザ入力ラベルを受信するステップであって、該ラベルは、該文書の該検索クエリとの関連性を示す、ステップと、
該検索クエリおよび該ユーザ入力ラベルに基づいて、分類器を訓練するステップと、
該文書を再分類するために、該分類器を用いて該文書に関して文書分類手法を実行するステップと、
該文書の該分類に基づいて、該文書の少なくとも一部の識別子を出力するステップと、
を包含する、文書検索の方法。
【請求項122】
前記文書分類手法は、トランスダクティブ処理を含む、請求項121に記載の方法。
【請求項123】
前記分類器はトランスダクティブ分類器である、請求項122に記載の方法であって、少なくとも1つの所定コスト要因、前記検索クエリ、および前記文書を用いて、繰り返し計算によって該トランスダクティブ分類器を訓練するステップであって、該計算の各繰り返しに対して、該コスト要因が期待ラベル値の関数として調整される、ステップと、該文書を分類するために該訓練された分類器を用いるステップと、をさらに包含する、方法。
【請求項124】
前記検索クエリおよび文書に対するデータ点ラベルの事前確率を受信するステップ、をさらに包含する、請求項123に記載の方法であって、前記計算の各繰り返しに対して、該データ点のラベルの事前確率がデータ点のクラス帰属確率の推定値に従って調整される、方法。
【請求項125】
前記文書分類手法は、サポートベクタマシン処理を含む、請求項121に記載の方法。
【請求項126】
前記文書分類手法は、最大エントロピー識別処理を含む、請求項121に記載の方法。
【請求項127】
前記再分類された文書は出力され、最も高い信頼度を有する文書が最初に出力される、請求項121に記載の方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate


【公表番号】特表2009−543254(P2009−543254A)
【公表日】平成21年12月3日(2009.12.3)
【国際特許分類】
【出願番号】特願2009−519439(P2009−519439)
【出願日】平成19年6月7日(2007.6.7)
【国際出願番号】PCT/US2007/013484
【国際公開番号】WO2008/008142
【国際公開日】平成20年1月17日(2008.1.17)
【出願人】(501477886)コファックス インコーポレイテッド (2)
【氏名又は名称原語表記】Kofax, Inc.
【Fターム(参考)】