(57)【要約】【課題】Boostingにおいて再現性を保持しつつ学習の偏りを無くすように規則の学習を行う。【解決手段】1又は複数の素性を含む素性集合と-1又は+1であるラベルとを含む学習事例と当該学習事例の重みとの組み合わせを含む学習データの各素性を、所定数のバケットに分配する分配工程と、各バケットについて、当該バケットに属する素性のうち学習事例の重みに基づくゲインの値が最大となる素性を規則として特定し、当該特定された規則について確信度を算出して当該規則と当該確信度との組を格納すると共に、当該規則と対応確信度とを用いて次の段階で用いるべき各学習事例の重みを算出し、更新登録するバケット処理工程と、全てのバケットについてバケット処理工程が実施されても規則及び確信度の生成が必要な場合には、分配工程を再度実施させ、さらにバケット処理工程を実施させる工程とを含む。【選択図】図１２
2010033214.tif 000002
【特許請求の範囲】
【請求項１】
１又は複数の素性を含む素性集合と−１と＋１のうちいずれかであるラベルとを含む学習事例と当該学習事例の重みとの組み合わせを複数格納する学習事例データ格納部に登録されている各素性を、前記学習事例の重みに基づく当該素性の重みに応じて、所定個数のバケットに分配する分配ステップと、
各前記バケットについて、当該バケットに属する前記素性のうち前記学習事例の重みに基づくゲインの値が最大となる素性を規則として特定し、当該特定された規則について前記学習事例の重みに基づき確信度を算出して当該特定された規則と当該確信度との組を規則データ格納部に格納すると共に、当該特定された規則と対応する前記確信度と前記学習事例のデータと当該学習事例の重みとを用いて次の段階で用いるべき各学習事例の重みを算出し、前記学習事例データ格納部に格納されている重みを更新するバケット処理ステップと、
全ての前記バケットについて前記バケット処理ステップが実施されてもさらに規則及び確信度の生成が必要な場合には、前記分配ステップを再度実施させ、その後さらに前記バケット処理ステップを実施させるステップと、
を含み、コンピュータにより実行される規則学習方法。
【請求項２】
前記分配ステップが、
前記学習事例に含まれる各素性について、前記学習事例の重みに基づいて当該素性の重みを算出するステップと、
前記素性の重みの値によって各素性を降順にソートし、ソート順に前記所定個数のバケットの各々に、各前記素性を分配するステップと、
を含む請求項１記載の規則学習方法。
【請求項３】
前記素性の重みが、当該素性が出現する学習事例の重みの和である
請求項１又は２記載の規則学習方法。
【請求項４】
前記ゲインが、処理対象の素性が出現する学習事例であってラベルが＋１のものの学習事例の重みの和の平方根と、前記処理対象の素性が出現する学習事例であってラベルが−１のものの学習事例の重みの和の平方根との差の絶対値で算出される
請求項１記載の規則学習方法。
【請求項５】
１又は複数の素性を含む素性集合と−１と＋１のうちいずれかであるラベルとを含む学習事例と当該学習事例の重みとの組み合わせを複数格納する学習事例データ格納部に登録されている各素性を、前記学習事例の重みに基づく当該素性の重みに応じて、所定個数のバケットに分配する分配ステップと、
各前記バケットについて、当該バケットに属する前記素性のうち前記学習事例の重みに基づくゲインの値が最大となる素性を規則として特定し、当該特定された規則について前記学習事例の重みに基づき確信度を算出して当該特定された規則と当該確信度との組を規則データ格納部に格納すると共に、当該特定された規則と対応する前記確信度と前記学習事例のデータと当該学習事例の重みとを用いて次の段階で用いるべき各学習事例の重みを算出し、前記学習事例データ格納部に格納されている重みを更新するバケット処理ステップと、
全ての前記バケットについて前記バケット処理ステップが実施されてもさらに規則及び確信度の生成が必要な場合には、前記分配ステップを再度実施させ、その後さらに前記バケット処理ステップを実施させるステップと、
をコンピュータに実行させるための規則学習プログラム。
【請求項６】
１又は複数の素性を含む素性集合と−１と＋１のうちいずれかであるラベルとを含む学習事例と当該学習事例の重みとの組み合わせを複数格納する学習事例データ格納部と、
前記学習事例データ格納部に登録されている各素性を、前記学習事例の重みに基づく当該素性の重みに応じて、所定個数のバケットに分配する分配手段と、
規則データ格納部と、
各前記バケットについて、当該バケットに属する前記素性のうち前記学習事例の重みに基づくゲインの値が最大となる素性を規則として特定し、当該特定された規則について前記学習事例の重みに基づき確信度を算出して当該特定された規則と当該確信度との組を前記規則データ格納部に格納すると共に、当該特定された規則と対応する前記確信度と前記学習事例のデータと当該学習事例の重みとを用いて次の段階で用いるべき各学習事例の重みを算出し、前記学習事例データ格納部に格納されている重みを更新するバケット処理手段と、
を有し、
全ての前記バケットを前記バケット処理手段が処理してもさらに規則及び確信度の生成が必要な場合には、前記分配手段を再度動作させ、その後さらに前記バケット処理手段を動作させる、
規則学習装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、 機械学習に関し、より詳しくは機械学習における規則学習の高速化技術に関する。
【背景技術】
【０００２】
機械学習アルゴリズムには様々なものが知られているが、その中でもブースティング（Ｂｏｏｓｔｉｎｇ）というアルゴリズムが存在している。ここでは、Ｂｏｏｓｔｉｎｇアルゴリズムの中でもＡｄａＢｏｏｓｔという手法に基づく学習手法について検討する。以下、特に述べない限り、ＢｏｏｓｔｉｎｇはＡｄａＢｏｏｓｔを示すものとする。
【０００３】
Ｂｏｏｓｔｉｎｇでは、与えられた弱学習器を使って、異なる重みを持つ学習事例から複数の弱仮説（すなわち規則）を生成する。そして、事例の重みを変更しつつ、学習事例から繰り返し複数の弱仮説を生成して、最終的に、弱仮説の組み合わせである最終仮説を生成する。なお、今までに学習した弱仮説にて正しく分類できる事例には小さい重みを、正しく分類できない事例には大きい重みが割り当てられるようにする。
【０００４】
今回の説明では、弱学習器としてある規則学習器を扱うＢｏｏｓｔｉｎｇアルゴリズムに基づき説明を行う。また、以降、このアルゴリズムをＢｏｏｓｔｉｎｇアルゴリズムと記すことにする。Ｂｏｏｓｔｉｎｇアルゴリズムについての前提を以下に述べておく。
まず、Ｂｏｏｓｔｉｎｇアルゴリズムが扱う問題について述べる。ここでχを事例集合とし、扱うラベル集合をｙ＝｛−１、＋１｝とする。また、学習の目的は、学習データＳ＝｛（ｘ1，ｙ1），．．．，（ｘm，ｙ1）｝から、マッピングＦ：χ−＞ｙを導出することである。
【０００５】
ここで、｜ｘ｜を、事例ｘ∈χに含まれる素性の種類とする。ｘi∈χ（１≦ｉ≦ｍ）とは、｜ｘi｜種類の素性から構成される素性集合とする。また、ここではｋ個の素性から構成される素性集合をｋ−素性集合と記する。さらに、ｙi∈ｙは、Ｓ中のｉ番目の素性集合のクラスレベルである。
【０００６】
ＦＴ＝｛ｆ1，ｆ2，．．．，ｆM｝をＢｏｏｓｔｉｎｇアルゴリズムが対象とするＭ種類の素性とする。各事例ｘiの各素性は、ｘi,j∈ＦＴ（１≦ｊ≦｜ｘi｜）となる。このＢｏｏｓｔｉｎｇアルゴリズムでは、バイナリのベクトルを取り扱うことも可能であるが、以下で述べる例では、各素性は、文字列で表現されるものとする。
【０００７】
また、ある素性集合が他の素性集合を包含する場合を次に定義する。
【０００８】
定義１
二つの素性集合ｘ、ｘ’において、ｘが有する全ての素性をｘ’が有する場合には、ｘはｘ’の部分素性集合と呼び、次のように記す。
ｘ⊆ｘ’
【０００９】
さらに、以下で列挙する４番目の非特許文献で用いられているreal-valued predictions and abstaining（ＲＶＰＡ）の考えを元に規則を定義する。ＲＶＰＡでは、入力の素性集合が条件に合う場合、実数で表現される確信度を返し、条件に合わない場合は、「０」を返す。素性集合を分類するための弱仮説を次のように定義する。
【００１０】
定義２
素性集合ｆを規則、ｘを入力の素性集合とする。また、実数ｃを規則ｆの確信度としたとき、規則の適用を以下に定義する。
【数１】
2010033214.tif 000003
【００１１】
Ｂｏｏｓｔｉｎｇに基づく規則学習は、Ｔ種類の規則素性集合とその確信度の組み合わせ（<ｆ1，ｃ1>，．．．，<ｆT，ｃT>）をＴ回のＢｏｏｓｔｉｎｇラウンドでの弱学習器による学習にて獲得し、以下に定義されるＦを構築するものである。
【数２】
2010033214.tif 000004
なお、ここでｓｉｇｎ（ｘ）は、ｘが０以上であれば１を、それ以外の場合には−１という関数を表す。
【００１２】
弱学習器は、学習データＳ｛（ｘi，ｙi）｝（１≦ｉ≦ｍ）と、ｔ回目のＢｏｏｓｔｉｎｇラウンドの時点での各学習事例の重み｛ｗt,1，．．．，ｗt,m｝を用いて、規則ｆt及びその確信度ｃtを導出する。ｗt,i（０＜ｗt,i）とは、ｉ番目（１≦ｉ≦ｍ）の事例（ｘi，ｙi）のｔ回目（１≦ｔ≦Ｔ）のＢｏｏｓｔｉｎｇラウンドの重みである。
【００１３】
弱学習器は、与えられた学習データと学習事例の重みを基に、規則として、以下の式を最小にする素性集合ｆとその確信度ｃを選択する。
【数３】
2010033214.tif 000005
なお、［［π］］は、ある命題πが成り立つ場合に１、それ以外の場合に０とする。
【００１４】
式（１）を規則選択の基準として用いるのは、Ｂｏｏｓｔｉｎｇに基づく学習アルゴリズムのトレーニングエラーの上限値は、事例の重みの和に関連するためである。
【００１５】
式（１）を、ある規則ｆによって最小化する場合、その時の確信度ｃは以下のようになる。
【数４】
2010033214.tif 000006
【００１６】
式（２）を式（１）に代入することで、以下の式が得られる。
【数５】
2010033214.tif 000007
【００１７】
式（３）から、式（１）を最小化することは、以下に定義されるｓｃｏｒｅを最大化する素性集合ｆを選択することと等価であることが分かる。
【数６】
2010033214.tif 000008
【００１８】
次に、（ｆt，ｃt）を用いて、各事例の重みを更新する処理について説明する。なお、重みについては、全ての重みの和が１となるように正規化する場合と、そうでない場合とがある。
【００１９】
正規化する場合、ｔ＋１回目のラウンドでの重みｗt+1,iは以下のように定義される。
【数７】
2010033214.tif 000009
【００２０】
正規化しない場合には、以下のように定義される。
【数８】
2010033214.tif 000010
【００２１】
なお、正規化する場合の重みの初期値ｗ1,iは１／ｍ（ｍは学習事例数）であり、正規化しない場合の重みの初期値ｗ1,iは１とする。
【００２２】
また、素性の出現がスパース（わずかな事例にしか出現しないという意味）である場合には、Ｗt,+1（ｆ）又はＷt,-1（ｆ）が非常に小さい値又は０になることが生ずる。これを避けるために、スムージングのための値εを導入する。
【００２３】
すなわち、式（２）を以下のように変形する。
【数９】
2010033214.tif 000011
【００２４】
例えば、ε＝１／ｍやε＝１を用いる。
【００２５】
上で述べたような基本的なＢｏｏｓｔｉｎｇアルゴリズムでは、規則の候補数（すなわち素性の数）と規則の生成回数（すなわち、繰り返し処理のラウンド数）とが膨大である場合には、学習時間も非常に長くなり、問題となる。
【００２６】
そのため、規則の候補のうちの一部のみを利用して学習を行うような手法が考案されている。例えば、頻度やエントロピーなどの尺度で予め規則の候補の集合（バケットとも呼ぶ）を複数生成し、各ラウンドで１つの集合から１つの規則を選択するという手法がある。以下、この手法による処理内容を図１乃至図１１を用いて説明する。
【００２７】
まず、１又は複数の素性を含む素性集合ｘiと−１又は＋１であるラベルｙiとの組み合わせである事例をｍ個含む学習データＳ＝｛（ｘ1，ｙ1），（ｘ2，ｙ2），．．．（ｘm，ｙm）｝と、ｍ個の事例に対応するｍ個の重みの初期値Ｄ1(i)＝１（１≦ｉ≦ｍ）と、繰り返し回数Ｎと、繰り返し回数をカウントするための変数ｌ＝１と、バケット数Ｍと、バケットＩＤの変数ｂ＝１（１≦ｂ≦Ｍ）とを設定する（ステップＳ１０１）。理解を促すため、図２に示すような学習データについて処理する例を説明する。図２では、４つの学習事例が含まれている。第１の学習事例は、素性ａ，ｂ及びｃを含む素性集合と＋１のラベルを含み、当該学習事例の重みは１である。第２の学習事例は、素性ｃ及びｄを含む素性集合と−１のラベルを含み、当該学習事例の重みは１である。第３の学習事例は、素性ａ及びｃを含む素性集合と＋１のラベルを含み、当該学習事例の重みは１である。第４の学習事例は、素性ａ及びｂを含む素性集合と＋１のラベルを含み、当該学習事例の重みは１である。
【００２８】
次に、学習データＳに含まれる素性を規則候補として抽出し、各素性について、関係する学習事例の重みから素性の重みを算出し、当該素性の重みに応じてＭ個のバケット（Ｂ[1]，．．．，Ｂ[M]）に分配する（ステップＳ１０３）。具体的には、素性ａは、第１、第３及び第４の学習事例の素性集合に含まれ、それらの重みを加算することによって、素性ａの重み＝３が得られる。同様に、素性ｂは、第１及び第４の学習事例の素性集合に含まれ、それらの重みを加算することによって、素性ｂの重み＝２が得られる。素性ｃは、第１、第２及び第３の学習事例の素性集合に含まれ、それらの重みを加算することによって、素性ｃの重み＝３が得られる。素性ｄは、第２の学習事例の素性集合に含まれ、それらの重みが加算することによって、素性ｄの重み＝１が得られる。これをまとめると、図３に示すような素性と素性の重みとが得られる。そして、素性の重みで素性を降順にソートすると、図４に示すような結果が得られる。すなわち、ａ、ｃ、ｂ、ｄの順番が得られる。ここでＭ＝２とすると、素性ａをバケット１に、素性ｃをバケット２に、素性ｂをバケット１に、素性ｄをバケット２に、交互に分配する。すなわち、図５に示したように、バケット１には、素性ａ及びｂが含まれ、バケット２には、素性ｃ及びｄが含まれるようになる。
【００２９】
次に、重みＤl(i)に従って、バケットＢ[b]に含まれる各規則候補（すなわち素性）についてゲインを算出し、ゲイン最大値の規則候補を規則ｈlとして選択する（ステップＳ１０５）。ゲインは、規則候補ｆに対して以下のように定義される。
ｇａｉｎ（ｆ）＝｜ｓｑｒｔ（Ｗ(f,+1)），ｓｑｒｔ（Ｗ(f,-1)）｜
ここで、Ｗ(f,LABEL)は、規則候補ｆが出現する学習事例であってラベルがLABEL（＋１又は−１)である学習事例の重みの和である。ｓｑｒｔ（ｘ）はｘ1/2を表し、｜ｘ｜はｘの絶対値を表す。
【００３０】
例えばバケット１に含まれる規則候補ａ及びｂについて処理する場合には、図２によれば、ｇａｉｎ（ａ）＝｜ｓｑｒｔ（３）−ｓｑｒｔ（０）｜＝３1/2と計算される。同様に、ｇａｉｎ（ｂ）＝｜ｓｑｒｔ（２）−ｓｑｒｔ（０）｜＝２1/2と計算される。まとめると、図６に示すようになる。よって、規則候補ａ及びｂのうち、ゲインの値の大きい規則候補ａが規則ｈ1として選択される。
【００３１】
次に、重みＤl(i)を用いて、規則ｈlの確信度αlを算出し、規則ｈl及び確信度αlを規則データ格納部に登録する（ステップＳ１０７）。確信度αlの計算については、式（７）に従って行われる。但し、ｃ＝αlである。例えば、規則ａの確信度は「１．２８」と計算される。
【００３２】
さらに、規則ｈl及び確信度αlを基に、重みＤl(i)を重みＤl+1(i)に更新する（ステップＳ１０９）。次の段階のための重みは、式（５）又は（６）によって計算される。図２に示した重みは、式（６）を用いると、図７に示すような重みに更新される。なお、ｗt,i＝Ｄl(i)である。具体的には、第１、第３及び第４の学習事例についての重みが０．２７に更新される。
【００３３】
そして、ｌを１インクリメントし（ステップＳ１１１）、ｂを１インクリメントする（ステップＳ１１３）。但し、Ｍ＜ｂとなった場合には、ｂを１に戻す。
【００３４】
その後、ｌがＮより小さいか判断し（ステップＳ１１５）、ｌがＮより小さい場合にはステップＳ１０５に戻る。一方、ｌがＮより大きくなった場合には処理を終了する。
【００３５】
上で述べた例では、Ｂ[2]の処理に移行して、バケット２に含まれる規則候補ｃ及びｄについて、それぞれゲインを算出すると、図８に示すような値が得られる。具体的には、ｇａｉｎ（ｃ）＝｜ｓｑｒｔ（０．５４）−ｓｑｒｔ（１）｜＝０．２５であり、ｇａｉｎ（ｄ）＝｜ｓｑｒｔ（０）−ｓｑｒｔ（１）｜＝１である。これによって、規則候補ｄが規則ｈ2として選択される。
【００３６】
次に、規則ｄの確信度を式（７）に従って計算すると「−０．８１」が得られる。この規則ｄとその確信度「−０．８１」を用いて、次の段階の学習事例の重みを式（６）を用いて算出すると、図９に示すような値が得られる。素性ｄが含まれる第２の学習事例の重みのみが「０．４４」に更新される。
【００３７】
さらに、Ｂ[1]の処理に移行して、バケット１に含まれる規則候補ａ及びｂについて、それぞれゲインを算出すると、図１０に示すような値が得られる。ここでも、ゲインの大きい方の規則候補は、ａである。従って、ａが規則として選択される。そして、規則ａの確信度を式（７）に従って計算すると「０．７３」が得られる。
【００３８】
このような処理を実施して、規則データ格納部に登録される規則及び確信度の組は、図１１に示すようなものになる。
【００３９】
この段階において学習が終了して分類時（すなわち−１か＋１の判別時）には、以下のような処理が行われる。すなわち、「ａｂｅ」が入力事例として入力されると、図１１の第１及び第３レコードから、確信度の和＝１．２８＋０．７３＝２．０１が得られる。このように、確信度の和が正であれば、「ａｂｅ」は＋１と分類される。
【００４０】
一方、「ｄｅ」が入力事例として入力されると、図１１の第２レコードから、確信度の和＝−０．８１が得られる。このように、確信度の和が負であれば、「ｄｅ」は−１と分類される。
【００４１】
但し、図１のステップＳ１０５乃至Ｓ１１５を繰り返しても、規則ａ及びｄが連続して選択されてしまい、規則候補ｂ、ｃ及びｅは選択されない。すなわち、最初のバケットへの分配処理に依存してしまって、学習の対象が偏ってしまう。このように、第１乃至第４の学習事例についての分類精度は１００％になっても、規則候補ｂ、ｃ及びｅは一度も選択されず、規則は生成されない。従って、「ｂｅ」という入力事例が入力された場合、確信度の和は「０」となり、適切に分類されない。但し、「０」の場合には、予め＋１又は−１のいずれかにするか決めておく。
【００４２】
図１に示したような方法ではなく、（１）所定回数以上出現する規則候補のみを利用して、学習を行う方法や、（２）各ラウンドで規則候補をランダムに選択する方法などがある。しかしながら、（１）では、学習されない規則候補が出てきてしまうという問題がある。また、（２）では、異なる規則候補が各ラウンドで選択されるようになるが、学習の再現性がないという問題がある。
【非特許文献１】Y. Freund and L. Mason. The alternating decision tree learning algorithm,. In Proc.of 16th ICML,pages124-133,1999
【非特許文献２】R. E. Schapire and Y. Singer. Improved boosting using confidence-rated predictions. Machine Learning,37(3):297-336,1999
【非特許文献３】R. E. Schapire and Y. Singer. Boostexter:A boosting-based system for text categorization. Machine Learning,39(2/3):135-168,2000
【非特許文献４】Gerard Escudera, Llu' is M'arquez, and German Rigau, 200, Boosting applied to word sense disambiguation, In Proc. of 11th ECML, pages 129-141
【発明の開示】
【発明が解決しようとする課題】
【００４３】
以上のように、従来技術では、学習する規則候補に偏りが生じたり、学習に再現性がなかったりというような問題がある。
【００４４】
従って、本技術の目的は、Ｂｏｏｓｔｉｎｇアルゴリズムにおいて再現性を保持しつつ学習の偏りを無くすように規則の学習を行うことである。
【課題を解決するための手段】
【００４５】
本規則学習方法は、１又は複数の素性を含む素性集合と−１と＋１のうちいずれかであるラベルとを含む学習事例と当該学習事例の重みとの組み合わせを複数格納する学習事例データ格納部に登録されている各素性を、学習事例の重みに基づく当該素性の重みに応じて、所定個数のバケットに分配する分配ステップと、各バケットについて、当該バケットに属する素性のうち学習事例の重みに基づくゲインの値が最大となる素性を規則として特定し、当該特定された規則について学習事例の重みに基づき確信度を算出して当該特定された規則と当該確信度との組を規則データ格納部に格納すると共に、当該特定された規則と対応する確信度と学習事例のデータと当該学習事例の重みとを用いて次の段階で用いるべき各学習事例の重みを算出し、学習事例データ格納部に格納されている重みを更新するバケット処理ステップと、全てのバケットについてバケット処理ステップが実施されてもさらに規則及び確信度の生成が必要な場合には、分配ステップを再度実施させ、その後さらにバケット処理ステップを実施させるステップとを含む。
【発明の効果】
【００４６】
Ｂｏｏｓｔｉｎｇアルゴリズムにおいて再現性を保持しつつ学習の偏りを無くすように規則の学習を行うことができる。
【発明を実施するための最良の形態】
【００４７】
以下、本技術の実施の形態を説明する。図１２に本実施の形態におけるシステムの機能ブロック図を示す。本システムは、学習データなどの入力を行うための学習データ入力部１と、学習データ入力部１によって入力された学習データなどを格納する学習データ格納部３と、学習データ格納部３に格納されているデータを用いて本実施の形態における主要な処理を実施する規則学習部５と、規則学習部５の処理結果である規則データを格納する規則データ格納部７と、生成された規則を適用して分類を行う対象である分類データを入力するための分類データ入力部９と、分類データ入力部９によって入力された分類データを格納する分類データ格納部１１と、規則データ格納部７に格納されている規則データを、分類データ格納部１１に格納されている処理対象データに適用して、分類を行う規則適用部１３と、規則適用部１３の処理結果を格納する処理結果格納部１５とを有する。
【００４８】
なお、本技術の前提において述べたマッピングＦ：χ−＞ｙを実施するのが規則適用部１３であり、χが分類データを表し、ｙが処理結果を表す。このように、規則適用部１３の処理内容については従来と同じであり、規則データ格納部７に格納される規則データと、分類データ入力部９によって分類データ格納部１１に格納されている分類データとが用意されれば、従来どおり処理が行われ、処理結果についても、同様に格納される。すなわち、χに含まれる素性に対応する規則の確信度の和が正であれば＋１に、負であれば−１に分類する。従って、以下では説明を省略する。
【００４９】
次に、図１３乃至図１８を用いて、本実施の形態における規則学習部５等の処理内容について説明する。
【００５０】
まず、学習データ入力部１は、例えばユーザからの指示に従って、１又は複数の素性を含む素性集合ｘiと−１又は＋１であるラベルｙiとの組み合わせである事例をｍ個含む学習データＳ＝｛（ｘ1，ｙ1），（ｘ2，ｙ2），．．．（ｘm，ｙm）｝と、ｍ個の事例に対応するｍ個の重みの初期値Ｄ1(i)＝１と、繰り返し回数Ｎと、繰り返し回数をカウントするためのｌ＝１と、バケット数Ｍと、バケットＩＤの変数ｂ＝１（１≦ｂ≦Ｍ）とについての入力を受け付け、学習データ格納部３に格納する（ステップＳ１）。なお、背景技術の欄で用いた具体例を、比較のためにそのまま本実施の形態でも用いることとする。すなわち、図２と同じ学習データを処理するものとする。
【００５１】
次に、規則学習部５は、学習データＳに含まれる素性を規則候補として抽出し、各素性について、関係する学習事例の重みから素性の重みを算出し、当該素性の重みに応じてＭ個のバケット（Ｂ[1]，．．．，Ｂ[M]）に分配する（ステップＳ３）。素性の重みについては、背景技術の欄で述べたのと同じように計算される。すなわち、図３に示すような素性と素性の重みとが得られる。そして、素性の重みで素性を降順にソートすると、図４に示すような結果が得られる。すなわち、ａ、ｃ、ｂ、ｄの順番が得られる。そして、Ｍ＝２であるので、素性ａをバケット１に、素性ｃをバケット２に、素性ｂをバケット１に、素性ｄをバケット２に、交互に分配する。すなわち、図５に示したように、バケット１には、素性ａ及びｂが含まれ、バケット２には、素性ｃ及びｄが含まれるようになる。
【００５２】
次に、規則学習部５は、重みＤl(i)（１≦ｌ≦ｍ）に従って、バケットＢ[b]に含まれる各規則候補（すなわち素性）についてゲインを算出し、ゲイン最大値の規則候補を規則ｈlとして選択する（ステップＳ５）。ゲインは、背景技術の欄で述べたのと同じように計算される。そして、ゲインの計算結果は、図６に示すようになる。よって、規則候補ａ及びｂのうち、ゲインの値の大きい規則候補ａが規則ｈ1として選択される。
【００５３】
次に、規則学習部５は、重みＤl(i)を用いて、規則ｈlの確信度αlを算出し、規則ｈl及び確信度αlを規則データ格納部７に登録する（ステップＳ７）。確信度αlの計算については、式（７）に従って行われる。例えば、規則ａの確信度は「１．２８」と計算される。
【００５４】
さらに、規則学習部５は、規則ｈl及び確信度αlを基に、重みＤl(i)を重みＤl+1(i)に更新する（ステップＳ９）。次の段階のための重みは、式（５）又は（６）によって計算される。図２に示した重みは、式（６）を用いると、図７に示すような重みに更新される。
【００５５】
その後、規則学習部５は、ｌを１インクリメントすると共に（ステップＳ１１）、ｂも１インクリメントする（ステップＳ１３）。処理は端子Ａを介して、図１４の処理に移行する。
【００５６】
図１４の処理の説明に移行して、規則学習部５は、ｂがＭを超えたか判断する（ステップＳ１５）。ｂがＭを超えていない場合には、ｌがＮより小さいか判断する（ステップＳ１９）。ｌがＮより小さい場合には、端子Ｂを介してステップＳ５に戻る。一方、ｌがＮ以上となった場合には、処理を終了する。
【００５７】
上で述べた例では、次にバケット２について処理に移行して、バケット２に含まれる規則候補ｃ及びｄについて、それぞれゲインを算出すると、図８に示すような値が得られる。これによって、規則候補ｄが規則ｈ2として選択される。
【００５８】
次に、規則ｄの確信度を式（７）に従って計算すると「−０．８１」が得られる。この規則ｄとその確信度「−０．８１」を用いて、次の段階の学習事例の重みを式（６）を用いて算出すると、図９に示すような値が得られる。ここまでの処理結果は、背景技術の欄で述べたものと同じである。
【００５９】
一方、ｂがＭを超えた場合には、規則学習部５は、バケット再配分処理を実施する（ステップＳ１７）。このバケット再配分処理については、図１５を用いて説明する。
【００６０】
まず、規則学習部５は、学習データ格納部３に格納されている学習データに含まれる未処理の素性を１つ特定する（ステップＳ２１）。そして、特定された素性について、関係する学習事例の重みＤl(i)（すなわち、特定された素性が素性集合に含まれる学習事例についての重み）から素性の重みを算出し、事例重みテーブルに登録する（ステップＳ２３）。その後、学習データに含まれる全ての素性について処理したか判断する（ステップＳ２５）。未処理の素性が存在する場合にはステップＳ２１に戻る。一方、全ての素性について処理した場合には、ステップＳ２７に移行する。
【００６１】
図９の状態において、素性ａ、ｂ、ｃ及びｄについてそれぞれ素性の重みを算出すると、図１６Ａに示すような事例重みテーブルが得られる。具体的には、素性ａの重みは、０．２７＋０．２７＋０．２７＝０．８１である。素性ｂの重みは、０．２７＋０．２７＝０．５４である。素性ｃの重みは、０．２７＋０．４４＋０．２７＝０．９８である。さらに、素性ｄの重みは、０．４４である。
【００６２】
そして、規則学習部５は、事例重みテーブルのレコードを、素性の重みを基に降順にソートする（ステップＳ２７）。図１６Ａに示した事例重みテーブルをソートすると、図１６Ｂに示すようになる。すなわち、素性ｃ、ａ、ｂ、ｄの順番に並べられる。
【００６３】
そして、規則学習部５は、カウンタｔを１に初期化し（ステップＳ２９）、ｔ番目のレコードの素性を、（ＭＯＤ（ｔ，Ｍ））番目のバケットに配分する（ステップＳ３１）。ＭＯＤ（ｔ，Ｍ）は、Ｍを法とするｔの剰余であり、ｔ／Ｍの余りである。ｔ＝１であれば、１／２で余り１である。すなわち、素性ｃはバケット１に配分される。
【００６４】
そして規則学習部５は、ｔを１インクリメントし（ステップＳ３３）、事例重みテーブルにおいて未処理のレコードがあるか判断する（ステップＳ３５）。未処理のレコードが存在すればステップＳ３１に戻る。
【００６５】
次に素性ａについては、バケット２に分配され、素性ｂについては、バケット１に分配され、素性ｄについては、バケット２に分配される。すなわち、図１７に示すように、バケット１には、素性ｂ及びｃが分配され、バケット２には、素性ａ及びｄが分配される。
【００６６】
そして、未処理のレコードが存在していなければ、ｂを１に戻して、元の処理に戻る（ステップＳ３７）。
【００６７】
図１３のステップＳ５に戻ると、バケット１の中からゲイン最大の素性を選択するが、図９の学習事例の重みの状態からゲインは図１８に示すように計算される。図１８に示すように、素性ｂのゲインが最大となるので、素性ｂが選択される。背景技術の欄のようなバケットの再構成が行われない場合には、素性ａとｃとが繰り返し選択されて、素性ｂが選択されることはなかったが、本実施の形態では素性ｂが選択されるようになるので、学習の偏りを無くすことができるようになる。当然ながら、同じ学習事例であれば同じように学習が行われるので、再現性も担保されている。
【００６８】
なお、適切な素性を選択するために素性の種類を変更して実験することがしばしば行われるが、再現性がないと、素性の変更の是非を正しく判断できなくなるので、再現性は非常に重要である。
【００６９】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、図１２に示した機能ブロック図は一例であって、必ずしも実際のプログラムモジュールと対応するわけではない。
【００７０】
また、同じような効果が得られる限りにおいて処理ステップの順番を入れ替えたり、並列に実行させることができる。
【００７１】
また、本技術を他の弱学習器を扱うＢｏｏｓｔｉｎｇアルゴリズムにも適用可能である。例えば、他の弱学習器の例としては、Ｃ４．５というアルゴリズムが存在している（例えば、C4.5: Programs for Machine Learning (Morgan Kaufmann Series in Machine Learningを参照のこと）。Ｃ４．５は、Decision Tree（決定木）という形の弱仮説（すなわち、規則）を学習する。このＣ４．５に対して本技術を適用する場合には、Decision Tree を構成する最初のノードを学習する候補として、あるバケットに存在する素性だけを使うということで適用可能である。後は通常のＣ４．５のアルゴリズムと同じである。
さらに、木やグラフを分類する弱学習器を扱うＢｏｏｓｔｉｎｇアルゴリズムであっても最初に計算を開始する素性をあるバケットに存在するものと制限することで、同様に適用することができる。
【００７２】
例えば以下のような文献を参照のこと。
文献：Kudo, Taku, Matsumoto, Yuji. A Boosting Algorithm for Classification of Semi-Structured Text.  2004,. Proceedings of EMNLP 2004, 301-308.
文献：Taku Kudo, Eisaku Maeda, Yuji Matsumoto. An Application of Boosting to Graph Classification. 2004. Proceedings of NIPS 2004.
【００７３】
上で述べた本実施の形態をまとめると以下のようになる。
【００７４】
本規則学習方法は、１又は複数の素性を含む素性集合と−１と＋１のうちいずれかであるラベルとを含む学習事例と当該学習事例の重みとの組み合わせを複数格納する学習事例データ格納部に登録されている各素性を、学習事例の重みに基づく当該素性の重みに応じて、所定個数のバケットに分配する分配ステップと、各バケットについて、当該バケットに属する素性のうち学習事例の重みに基づくゲインの値が最大となる素性を規則として特定し、当該特定された規則について学習事例の重みに基づき確信度を算出して当該特定された規則と当該確信度との組を規則データ格納部に格納すると共に、当該特定された規則と対応する確信度と学習事例のデータと当該学習事例の重みとを用いて次の段階で用いるべき各学習事例の重みを算出し、学習事例データ格納部に格納されている重みを更新するバケット処理ステップと、全てのバケットについてバケット処理ステップが実施されてもさらに規則及び確信度の生成が必要な場合には、分配ステップを再度実施させ、その後さらにバケット処理ステップを実施させるステップとを含む。
【００７５】
このように学習事例の重みに応じてバケットを再構成することによって、選択される素性の偏りを生じさせることなく、学習の再現性も担保できる。
【００７６】
なお、上で述べた分配ステップは、学習事例に含まれる各素性について、学習事例の重みに基づいて当該素性の重みを算出するステップと、素性の重みの値によって各素性を降順にソートし、ソート順に所定個数のバケットの各々に、各素性を分配するステップとを含むようにしてもよい。これによって、現在の学習事例の重みに応じたバケットの再構成が適切に行われるようになる。
【００７７】
また、上で述べた素性の重みが、当該素性が出現する学習事例の重みの和である場合もある。
【００７８】
さらに、上で述べたゲインが、処理対象の素性が出現する学習事例であってラベルが＋１のものの学習事例の重みの和の平方根と、処理対象の素性が出現する学習事例であってラベルが−１のものの学習事例の重みの和の平方根との差の絶対値で算出されるようにしてもよい。
【００７９】
なお、上記方法は、コンピュータと当該コンピュータによって実行されるプログラムとの組み合わせにて実行される場合があり、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等の記憶媒体又は記憶装置に格納される。また、ネットワークなどを介してデジタル信号として配信される場合もある。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【００８０】
また、上記システムは、コンピュータ装置であって、図１９に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納される。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００８１】
（付記１）
１又は複数の素性を含む素性集合と−１と＋１のうちいずれかであるラベルとを含む学習事例と当該学習事例の重みとの組み合わせを複数格納する学習事例データ格納部に登録されている各素性を、前記学習事例の重みに基づく当該素性の重みに応じて、所定個数のバケットに分配する分配ステップと、
各前記バケットについて、当該バケットに属する前記素性のうち前記学習事例の重みに基づくゲインの値が最大となる素性を規則として特定し、当該特定された規則について前記学習事例の重みに基づき確信度を算出して当該特定された規則と当該確信度との組を規則データ格納部に格納すると共に、当該特定された規則と対応する前記確信度と前記学習事例のデータと当該学習事例の重みとを用いて次の段階で用いるべき各学習事例の重みを算出し、前記学習事例データ格納部に格納されている重みを更新するバケット処理ステップと、
全ての前記バケットについて前記バケット処理ステップが実施されてもさらに規則及び確信度の生成が必要な場合には、前記分配ステップを再度実施させ、その後さらに前記バケット処理ステップを実施させるステップと、
を含み、コンピュータにより実行される規則学習方法。
【００８２】
（付記２）
前記分配ステップが、
前記学習事例に含まれる各素性について、前記学習事例の重みに基づいて当該素性の重みを算出するステップと、
前記素性の重みの値によって各素性を降順にソートし、ソート順に前記所定個数のバケットの各々に、各前記素性を分配するステップと、
を含む付記１記載の規則学習方法。
【００８３】
（付記３）
前記素性の重みが、当該素性が出現する学習事例の重みの和である
付記１又は２記載の規則学習方法。
【００８４】
（付記４）
前記ゲインが、処理対象の素性が出現する学習事例であってラベルが＋１のものの学習事例の重みの和の平方根と、前記処理対象の素性が出現する学習事例であってラベルが−１のものの学習事例の重みの和の平方根との差の絶対値で算出される
付記１記載の規則学習方法。
【００８５】
（付記５）
１又は複数の素性を含む素性集合と−１と＋１のうちいずれかであるラベルとを含む学習事例と当該学習事例の重みとの組み合わせを複数格納する学習事例データ格納部に登録されている各素性を、前記学習事例の重みに基づく当該素性の重みに応じて、所定個数のバケットに分配する分配ステップと、
各前記バケットについて、当該バケットに属する前記素性のうち前記学習事例の重みに基づくゲインの値が最大となる素性を規則として特定し、当該特定された規則について前記学習事例の重みに基づき確信度を算出して当該特定された規則と当該確信度との組を規則データ格納部に格納すると共に、当該特定された規則と対応する前記確信度と前記学習事例のデータと当該学習事例の重みとを用いて次の段階で用いるべき各学習事例の重みを算出し、前記学習事例データ格納部に格納されている重みを更新するバケット処理ステップと、
全ての前記バケットについて前記バケット処理ステップが実施されてもさらに規則及び確信度の生成が必要な場合には、前記分配ステップを再度実施させ、その後さらに前記バケット処理ステップを実施させるステップと、
をコンピュータに実行させるための規則学習プログラム。
【００８６】
（付記６）
１又は複数の素性を含む素性集合と−１と＋１のうちいずれかであるラベルとを含む学習事例と当該学習事例の重みとの組み合わせを複数格納する学習事例データ格納部と、
前記学習事例データ格納部に登録されている各素性を、前記学習事例の重みに基づく当該素性の重みに応じて、所定個数のバケットに分配する分配手段と、
規則データ格納部と、
各前記バケットについて、当該バケットに属する前記素性のうち前記学習事例の重みに基づくゲインの値が最大となる素性を規則として特定し、当該特定された規則について前記学習事例の重みに基づき確信度を算出して当該特定された規則と当該確信度との組を前記規則データ格納部に格納すると共に、当該特定された規則と対応する前記確信度と前記学習事例のデータと当該学習事例の重みとを用いて次の段階で用いるべき各学習事例の重みを算出し、前記学習事例データ格納部に格納されている重みを更新するバケット処理手段と、
を有し、
全ての前記バケットを前記バケット処理手段が処理してもさらに規則及び確信度の生成が必要な場合には、前記分配手段を再度動作させ、その後さらに前記バケット処理手段を動作させる、
規則学習装置。
【図面の簡単な説明】
【００８７】
【図１】公知技術の処理フローを示す図である。
【図２】学習データの一例を示す図である。
【図３】素性の重みの計算例を示す図である。
【図４】素性の重みに応じたソート結果を示す図である。
【図５】公知技術におけるバケット構成例を示す図である。
【図６】バケット１のゲインの計算結果を示す図である。
【図７】第１ラウンドの結果に基づく重みの更新例を示す図である。
【図８】バケット２のゲインの計算結果を示す図である。
【図９】第２ラウンドの結果に基づく重みの更新例を示す図である。
【図１０】バケット１のゲインの計算結果を示す図である。
【図１１】規則データ格納部に格納される公知技術における規則及び確信度の組を表す図である。
【図１２】本技術の実施の形態におけるシステムの機能ブロック図である。
【図１３】本技術の実施の形態におけるメインの処理フローを示す図である。
【図１４】本技術の実施の形態におけるメインの処理フローを示す図である。
【図１５】バケット再配分処理の処理フローを示す図である。
【図１６Ａ】背景技術の欄の例についてバケット再配分処理において算出される素性の重みを示す図である。
【図１６Ｂ】素性の重みに応じたソート結果を示す図である。
【図１７】バケット再配分結果を示す図である。
【図１８】第３ラウンドにおけるバケット１のゲインの計算結果を示す図である。
【図１９】コンピュータの機能ブロック図である。
【符号の説明】
【００８８】
１  学習データ入力部    ３  学習データ格納部
５  規則学習部    ７  規則データ格納部
９  分類データ入力部    １１  分類データ格納部
１３  規則適用部    １５  処理結果格納部
【図１】
2010033214.tif 000012
【図２】
2010033214.tif 000013
【図３】
2010033214.tif 000014
【図４】
2010033214.tif 000015
【図５】
2010033214.tif 000016
【図６】
2010033214.tif 000017
【図７】
2010033214.tif 000018
【図８】
2010033214.tif 000019
【図９】
2010033214.tif 000020
【図１０】
2010033214.tif 000021
【図１１】
2010033214.tif 000022
【図１２】
2010033214.tif 000023
【図１３】
2010033214.tif 000024
【図１４】
2010033214.tif 000025
【図１５】
2010033214.tif 000026
【図１６Ａ】
2010033214.tif 000027
【図１６Ｂ】
2010033214.tif 000028
【図１７】
2010033214.tif 000029
【図１８】
2010033214.tif 000030
【図１９】
2010033214.tif 000031