(57)【要約】【課題】安定した予測を得る処理時間を短縮することを課題とする。【解決手段】学習装置は、それぞれに説明変数および目的変数を有する訓練データから、説明変数の組合せにより構成され、説明変数の真偽により目的変数の推定をそれぞれ行う複数の決定木を生成する。学習装置は、複数の決定木と等価な線形モデルであって、説明変数の組み合わせにより構成される項をもれなく列挙した線形モデルを生成する。学習装置は、入力データから、線形モデルを用いて予測結果を出力する。【選択図】図１
2020046891.tif 000002
【特許請求の範囲】
【請求項１】
それぞれに説明変数および目的変数を有する訓練データから、前記説明変数の組合せにより構成され、前記説明変数の真偽により前記目的変数の推定をそれぞれ行う複数の決定木を生成し、
前記複数の決定木と等価な線形モデルであって、前記説明変数の組み合わせにより構成される項をもれなく列挙した前記線形モデルを生成し、
入力データから、前記線形モデルを用いて予測結果を出力する
処理をコンピュータに実行させる、予測プログラム。
【請求項２】
前記生成する処理は、前記複数の決定木それぞれについて、葉が真であるパスの和、または、葉が偽であるパスの和を用いて、前記複数の決定木それぞれに対応する複数の部分的な線形モデルを生成し、前記複数の部分的な線形モデルの和を前記複数の決定木の合計数で除算して得られる結果を、前記複数の決定木と等価な前記線形モデルとして生成する、請求項１に記載の予測プログラム。
【請求項３】
前記出力する処理は、前記予測結果が閾値以上であれば、前記目的変数に該当すると予測し、前記予測結果が前記閾値未満であれば、前記目的変数に該当しないと予測する、請求項１または２に記載の予測プログラム。
【請求項４】
それぞれに説明変数および目的変数を有する訓練データから、前記説明変数の組合せを特定し、
前記説明変数の組み合わせにより構成され、前記説明変数の真偽により前記目的変数の推定をそれぞれ行う複数の決定木と等価な線形モデルであって、前記説明変数の組み合わせにより構成される項をもれなく列挙した前記線形モデルを生成し、
入力データから、前記線形モデルを用いて予測結果を出力する
処理をコンピュータに実行させる、予測プログラム。
【請求項５】
前記訓練データが有する各説明変数の積項の組み合わせに基づき、特定の積項に該当する複数のキューブを特定し、
前記複数のキューブそれぞれについて、各キューブに対応する前記特定の積項により特定される各決定木と等価である各部分的な線形モデルを生成し、
前記複数のキューブそれぞれに対応する前記各部分的な線形モデルに基づき、前記複数の決定木を含むモデル全体と等価な前記線形モデルを生成する、処理を前記コンピュータに実行させる請求項４に記載の予測プログラム。
【請求項６】
前記各キューブについて、キューブ内の正例数とキューブ外の負例数との合計である第１の合計値と、キューブ内の負例数とキューブ外の正例数との合計である第２の合計値とを算出し、
前記各キューブについて、前記第１の合計値と前記第２の合計値との和である総数を算出し、
前記各キューブに対応する前記各部分的な線形モデルの和を、前記各キューブに対応する総数の和で除算した結果を、前記線形モデルとして生成する、処理を前記コンピュータに実行させる請求項５に記載の予測プログラム。
【請求項７】
それぞれに説明変数および目的変数を有する訓練データから、前記説明変数の組合せにより構成され、前記説明変数の真偽により前記目的変数の推定をそれぞれ行う複数の決定木を生成し、
前記複数の決定木と等価な線形モデルであって、前記説明変数の組み合わせにより構成される項をもれなく列挙した前記線形モデルを生成し、
入力データから、前記線形モデルを用いて予測結果を出力する
処理をコンピュータが実行する、予測方法。
【請求項８】
それぞれに説明変数および目的変数を有する訓練データから、前記説明変数の組合せを特定し、
前記説明変数の組み合わせにより構成され、前記説明変数の真偽により前記目的変数の推定をそれぞれ行う複数の決定木と等価な線形モデルであって、前記説明変数の組み合わせにより構成される項をもれなく列挙した前記線形モデルを生成し、
入力データから、前記線形モデルを用いて予測結果を出力する
処理をコンピュータが実行する、予測方法。
【請求項９】
それぞれに説明変数および目的変数を有する訓練データから、前記説明変数の組合せにより構成され、前記説明変数の真偽により前記目的変数の推定をそれぞれ行う複数の決定木を生成する生成部と、
前記複数の決定木と等価な線形モデルであって、前記説明変数の組み合わせにより構成される項をもれなく列挙した前記線形モデルを生成する生成部と、
入力データから、前記線形モデルを用いて予測結果を出力する出力部と
を有する、学習装置。
【請求項１０】
それぞれに説明変数および目的変数を有する訓練データから、前記説明変数の組合せを特定する特定部と、
前記説明変数の組み合わせにより構成され、前記説明変数の真偽により前記目的変数の推定をそれぞれ行う複数の決定木と等価な線形モデルであって、前記説明変数の組み合わせにより構成される項をもれなく列挙した前記線形モデルを生成する生成部と、
入力データから、前記線形モデルを用いて予測結果を出力する出力部と
を有する、学習装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予測プログラム、予測方法および学習装置に関する。
【背景技術】
【０００２】
機械学習において、離散化可能なデータを扱う場合に、可読性や解釈可能性の観点から、決定木に基づく学習モデルが利用される。単一の決定木を用いた場合、学習データの少なさや不正確さ、学習モデル構築時のパラメータ等に起因して、実際の現象とは異なる学習モデルが作られ、適用時の精度が極端に低くなる可能性を排除できない。
【０００３】
近年では、学習に使用するデータや特徴をランダムに変えて複数の決定木を作り、多数決を取るランダムフォレストが利用されている。ランダムフォレストでは、適用時に極端に精度が悪くなる木が含まれていても、全体としてある程度の精度を確保できる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】L.Breiman,“RANDOM  FORESTS”，Machine  Learning，vol.45，pp.5-32（2001）
【非特許文献２】J.R.Quinlan,“Induction  of  Decision  Trees”，Machine  Learning，vol.1，pp.81-106  （1986）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、機械学習の応用では、結果が妥当か他の可能性が無いか検討したい場合や過去の学習モデルと比較したい場合など、結果に何らかの根拠が存在する安定した学習モデルが要求されることがある。
【０００６】
しかしながら、ランダムフォレストは、学習モデル生成にランダム性を含むので、生成される決定木が偏よることが起こりうる。また、学習データが少ない場合や不正確な場合、ランダムフォレストによる学習モデルの生成において利用されるランダム性が、学習モデルの出力精度にどの程度の影響を与えているかを知ることができない。このため、偏りが起きていないことの根拠を示せず、機械学習による予測結果の信頼性は必ずしも高くない。また、ランダム性の影響を少なくするためには、ランダムに生成される決定木の数を増やすことも考えられるが、学習時間や学習後の学習モデルによる予測時間が長くなり、現実的ではない。
【０００７】
一つの側面では、安定した予測を得る処理時間を短縮することができる予測プログラム、予測方法および学習装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
第１の案では、予測プログラムは、それぞれに説明変数および目的変数を有する訓練データから、前記説明変数の組合せにより構成され、前記説明変数の真偽により前記目的変数の推定をそれぞれ行う複数の決定木を生成する処理をコンピュータに実行させる。予測プログラムは、前記複数の決定木と等価な線形モデルであって、前記説明変数の組み合わせにより構成される項をもれなく列挙した前記線形モデルを生成する処理をコンピュータに実行させる。予測プログラムは、入力データから、前記線形モデルを用いて予測結果を出力する処理をコンピュータに実行させる。
【発明の効果】
【０００９】
一実施形態によれば、安定した予測を得る処理時間を短縮することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施例１にかかる学習装置を説明する図である。
【図２】図２は、実施例１にかかる学習装置の機能構成を示す機能ブロック図である。
【図３】図３は、訓練データＤＢに記憶される訓練データの一例を示す図である。
【図４】図４は、決定木から線形モデルへの変換を説明する図である。
【図５】図５は、森モデルから線形モデルへの変換および係数の算出例を説明する図である。
【図６】図６は、学習処理の流れを示すフローチャートである。
【図７】図７は、実施例２にかかる学習装置を説明する図である。
【図８】図８は、単純な決定木の例を示す図である。
【図９】図９は、単純な森モデルの単純な決定木を用いた具体例を説明する図である。
【図１０】図１０は、キューブに対応する線形モデルの生成の具体例を説明する図である。
【図１１】図１１は、実施例２にかかる線形モデルの具体例を説明する図である。
【図１２】図１２は、実施例２にかかる学習処理の流れを示すフローチャートである。
【図１３】図１３は、一般技術との比較結果を説明する図である。
【図１４】図１４は、ハードウェア構成例を説明する図である。
【発明を実施するための形態】
【００１１】
以下に、本願の開示する予測プログラム、予測方法および学習装置の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。また、各実施例は、矛盾のない範囲内で適宜組み合わせることができる。
【実施例１】
【００１２】
［全体構成］
図１は、実施例１にかかる学習装置１０を説明する図である。図１に示す学習装置１０は、正解ラベルが付与された訓練データを用いて教師有学習を実行して学習モデルを生成し、学習後の学習モデルを用いて予測対象データの予測（推定）を実行するコンピュータ装置の一例である。なお、ここでは、学習と予測とを同じ装置で実現する例を説明するが、これに限定されるものではなく、学習と予測とを別々の装置で実現することもできる。
【００１３】
一般的なランダムフォレストでは、モデル生成にランダム性を含むので、生成される決定木が偏よることが起こりうる。このため、偏りにより全体の精度も極端に低くなる可能性を排除できず、毎回結果が変わりうるなどの事象が発生する。一方、ランダムに生成される決定木を増やすと偏る可能性を低減できるが学習や適用に時間がかかる。つまり、精度の低下と処理時間の高速とがトレードオフの関係にあり、安定した精度で高速に処理できる学習モデルが切望されている。
【００１４】
そこで、実施例１にかかる学習装置１０は、訓練データから生成され得る決定木を決定的にすべて生成し、多数決を行う森モデル（フォレストモデル）を生成することで、安定なモデルを作る。そして、学習装置１０は、森モデルを同等の結果を返す線形モデルに変換することで、適用時の計算時間を削減する。
【００１５】
具体的には、図１に示すように、学習装置１０は、それぞれに説明変数および目的変数を有する訓練データから、説明変数の組合せにより構成され、説明変数の真偽により目的変数の推定をそれぞれ行う複数の決定木を生成する。続いて、学習装置１０は、複数の決定木と等価な線形モデルであって、説明変数の組み合わせにより構成される項をもれなく列挙した線形モデルを生成する。
【００１６】
詳細には、学習装置１０は、森モデルに含まれる各々の決定木をパスに分解し、パスの有無を変数とする線形モデルを構築し、線形モデルの各変数の係数を森モデルに含まれるそのパスを含む決定木の数に基づいて決定する。その後、学習装置１０は、決定された線形モデルに、予測対象のデータを入力し、線形モデルに基づく算出を行って、予測結果を出力する。
【００１７】
このように、学習装置１０は、学習時には、安定性を向上させるために決定木の数が増やし、予測時（適用時）には、決定木を使わずに予測を行うことができるので、安定した予測を得る処理時間を短縮することができる。
【００１８】
［機能構成］
図２は、実施例１にかかる学習装置１０の機能構成を示す機能ブロック図である。図２に示すように、学習装置１０は、通信部１１、記憶部１２、制御部２０を有する。なお、ここで示した処理部は、一例であり、各種情報を表示する表示部などを有することもできる。
【００１９】
通信部１１は、他の装置の間の通信を制御する処理部であり、例えば通信インタフェースなどである。例えば、通信部１１は、学習対象の訓練データ、学習開始の指示、予測対象のデータ、予測開始の指示などを管理者端末などから受信し、訓練結果や予測結果などを管理者端末などに送信する。
【００２０】
記憶部１２は、データや制御部２０が実行するプログラムなどを記憶する記憶装置の一例であり、例えばメモリやハードディスクなどである。この記憶部１２は、訓練データＤＢ１３、学習結果ＤＢ１４、予測対象ＤＢ１５などを記憶する。
【００２１】
訓練データＤＢ１３は、学習対象のデータである訓練データを記憶するデータベースである。具体的には、訓練データＤＢ１３は、それぞれに説明変数および目的変数を有する複数の訓練データを記憶する。なお、ここで記憶される訓練データは、管理者等により格納および更新される。
【００２２】
図３は、訓練データＤＢ１３に記憶される訓練データの一例を示す図である。図３に示すように、訓練データＤＢ１３は、「データＩＤ、変数、ラベル」を対応付けた訓練データを記憶する。「データＩＤ」は、訓練データを識別する識別子である。「変数」は、目的変数を説明する変数であり、例えば説明変数に対応する。この変数には、数値データやカテゴリデータなどの様々な形式のデータを用いることができる。「ラベル」は、訓練データに与えられる正解情報であり、例えば目的変数に対応する。
【００２３】
なお、図３の例では、目的変数である事象に該当する訓練データに対して、ラベル「Ｙ＝１（以降、真、または、肯定、または、プラス（＋）と記載する場合がある））と記載する場合がある）」が付与されており、ある事象に該当しない訓練データに対して、ラベル「Ｙ＝０（以降、偽、または、否定、または、マイナス（−）と記載する場合がある）と記載する場合がある）」が付与されている。図３におけるデータＩＤ１は、ラベル「Ｙ」に「真」が付与されており、変数Ａ、Ｂ、Ｃが真、変数Ｄが偽である訓練データであることを示す。
【００２４】
ある事象の一例としては、「熱射病の危険性が高いか否か」などを判定する例などであり、熱射病の危険性が高いことを示す訓練データのラベルＹに「１」が設定され、それ以外を示す訓練データのラベルＹには「０」が設定される。この場合に、上記変数Ａなどの説明変数としては、「温度が３０℃以上か否か」などが挙げられ、温度が３０℃以上に該当する場合は、変数Ａが「１」と判定され、温度が３０℃以上に該当しない場合は、変数Ａが「０」と判定される。
【００２５】
学習結果ＤＢ１４は、後述する制御部２０による学習結果を記憶するデータベースである。具体的には、学習結果ＤＢ１４は、学習済みの学習モデルであり、予測に使用される線形モデルを記憶する。
【００２６】
予測対象ＤＢ１５は、予測対象のデータを記憶するデータベースである。具体的には、予測対象ＤＢ１５は、複数の説明変数を有し、学習済みの学習モデルである線形モデルに入力する対象のデータである予測対象データを記憶する。
【００２７】
制御部２０は、学習装置１０全体を司る処理部であり、例えばプロセッサなどである。この制御部２０は、学習部２１、生成部２２、予測部２３を有する。なお、学習部２１、生成部２２、予測部２３は、プロセッサが有する電子回路やプロセッサが実行するプロセスの一例である。
【００２８】
学習部２１は、訓練データに基づいて、複数の決定木を含む森モデルを生成する処理部である。具体的には、学習部２１は、訓練データＤＢ１３に記憶される各訓練データを読み込み、訓練データから生成され得る決定木を決定的にすべて生成する。そして、学習部２１は、生成される各決定木の出力結果を多数決によって判定する森モデルを生成して、生成部２２に出力する。
【００２９】
例えば、学習部２１は、訓練データそれぞれについて、説明変数の組合せにより構成され、説明変数の真偽により目的変数の推定（予測）をそれぞれ行う複数の決定木を生成する。また、学習部２１は、訓練データそれぞれについて、変数とその値の組によって表現されたデータをいくつかのサブセットに分割して、決定木を生成することもできる。なお、決定木の生成方法は、公知の様々な手法を採用することができる。
【００３０】
生成部２２は、学習部２１により生成された複数の決定木を用いて、線形モデルを生成する処理部である。具体的には、生成部２２は、複数の決定木と等価な線形モデルであって、説明変数の組み合わせにより構成される項をもれなく列挙した線形モデルを生成する。そして、生成部２２は、線形モデルを学習済みの学習モデルとして学習結果ＤＢ１４に格納する。
【００３１】
例えば、生成部２２は、森モデルに含まれる各々の決定木をパスに分解し、パスの有無を変数とする線形モデル（部分的な線形モデル）を構築し、線形モデルの各変数の係数を森モデルに含まれるそのパスを含む決定木の数に基づいて決定する。
【００３２】
ここで、決定木から線形モデルへの変換について具体的に説明する。図４は、決定木から線形モデルへの変換を説明する図である。図４に示す決定木は、変数Ｃに該当しない場合は目的変数に該当し、変数Ｃにも変数Ａにも該当する場合は目的変数に該当せず、変数Ｃには該当するが変数Ａおよび変数Ｄには該当しない場合は目的変数に該当せず、変数Ｃと変数Ｄには該当するが変数Ａには該当しない場合は目的変数に該当することを判定する決定木である（図４の（ａ）参照）。
【００３３】
このような決定木に対して、生成部２２は、決定木のパスに相当する、目的変数のリテラルの積項であるキューブを生成する（図４の（ｂ）参照）。このキューブとは、例えば説明変数の積項であり、正（真）の各説明変数の積項、否定（偽）の各説明変数の積項、正の各説明変数と否定の各説明変数との積項である。
【００３４】
図４を用いて、具体的に説明する。例えば、図４では、変数Ｃに該当しない場合と、変数Ｃに該当し変数Ａには該当せず変数Ｄには該当する場合とが、同じ判定（真）となることを示す。また、変数Ｃおよび変数Ａに該当する場合と、変数Ｃに該当し変数Ａおよび変数Ｄに該当しない場合とが、同じ判定（偽）となることを示す。なお、本実施例の図面（例えば図４など）では、変数Ｃに該当しないこと（言い換えると変数Ｃが偽（否定）であること）を「Ｃのオーバーライン」で記載しているが、明細書上では「Ｃ−」または「Ｃバー」と記載するが、これらは同一である。
【００３５】
そして、生成部２２は、決定木における、「葉が真（＋）のパスに相当するキューブの和」、または、「１−（葉が偽（−）のパスに相当するキューブの和）」を用いて、決定木と等価である線形モデルを生成する（図４の（ｃ））参照）。なお、本実施例では、「葉が「真（＋）」のパスに相当するキューブの和」を用いて説明する。
【００３６】
ここで、決定木の根から葉に至るパスに現れるリテラルの積をその葉を表す積項（キューブ）と呼ぶ。決定木のすべての正の葉を表すキューブの和、又は、決定木のすべての負の葉を表すキューブの和を１から減じた式が、その木と同等の線形モデルの式となる。１つ以上の決定木からなる森モデルが与えられたとき、森モデルに含まれるすべての決定木を、上記何れかの方法で線形モデルの式に変換し、それらの式を合計し、森モデルに含まれる決定木の数で除したものが、森モデルと同等の線形モデルの式となる。
【００３７】
図４の例では、生成部２２は、「葉が真」となるパスである、変数Ｃに該当しないパス「Ｃ−」と、変数Ｃに該当し変数Ａには該当せず変数Ｄに該当するパス「ＣＡ−Ｄ」との和により、線形モデル「Ｙ＝Ｃ−＋ＣＡ−Ｄ」を生成する。または、生成部２２は、「葉が偽」となるパスである、変数Ｃおよび変数Ａに該当するパス「ＣＡ」と、変数Ｃに該当し変数Ａおよび変数Ｄに該当しないパス「ＣＡ−Ｄ−」との和を用いて、線形モデル「Ｙ＝１−（ＣＡ＋ＣＡ−Ｄ−）」を生成する。このようにして、生成部２２は、各決定木に対応する線形モデルを生成する。
【００３８】
次に、生成部２２は、「葉が「真（＋）」のパスに相当するキューブの和」に基づいて、各決定木から生成された部分的な線形モデルの和を算出し、算出された「部分的な線形モデルの和」を決定木の合計数で除算することで、森モデルと同等の結果を返す線形モデルへ変換する。
【００３９】
図５は、森モデルから線形モデルへの変換および係数の算出例を説明する図である。図５では、一例として、決定木（ａ）と決定木（ｂ）と決定木（ｃ）の３つの決定木を含む森モデルから線形モデルへの変換を説明する。図５に示すように、生成部２２は、決定木（ａ）から部分的な線形モデル「Ｙ＝ＡＢ−＋Ａ−Ｄ」を生成し、決定木（ｂ）から部分的な線形モデル「Ｙ＝Ａ＋Ａ−Ｄ＋Ａ−Ｄ−Ｃ」を生成し、決定木（ｃ）から部分的な線形モデル「Ｙ＝Ａ−Ｃ」を生成する。
【００４０】
続いて、生成部２２は、これらの部分的な線形モデルの和「（ＡＢ−＋Ａ−Ｄ）＋（Ａ＋Ａ−Ｄ＋Ａ−Ｄ−Ｃ）＋（Ａ−Ｃ）」＝「ＡＢ−＋２Ａ−Ｄ＋Ａ＋Ａ−Ｄ−Ｃ＋Ａ−Ｃ」を算出する。その後、生成部２２は、部分的な線形モデルの和を決定木の数である３で除算した「（ＡＢ−＋２Ａ−Ｄ＋Ａ＋Ａ−Ｄ−Ｃ＋Ａ−Ｃ）／３」を生成する。すなわち、生成部２２は、学習済みの学習モデル（線形モデル）として、「Ｙ＝（ＡＢ−＋２Ａ−Ｄ＋Ａ＋Ａ−Ｄ−Ｃ＋Ａ−Ｃ）／３」を生成する。
【００４１】
図２に戻り、予測部２３は、生成部２２によって最終的に生成された線形モデルを用いて、予測対象ＤＢ１５に記憶される予測対象データの予測を実行する処理部である。上記した例で説明すると、予測部２３は、予測対象ＤＢ１５から予測対象データを取得するとともに、学習結果ＤＢ１４から線形モデル「Ｙ＝（ＡＢ−＋２Ａ−Ｄ＋Ａ＋Ａ−Ｄ−Ｃ＋Ａ−Ｃ）／３」を取得する。
【００４２】
そして、予測部２３は、予測対象データに含まれる変数を線形モデルに代入して値を代入することで、０以上１以下のスコアを得ることができ、このスコアが０．５を超える場合、予測対象データの目的変数を１、それ以外の場合を０と推定することができる。
【００４３】
例えば、予測部２３は、予測対象データにおける変数Ａと変数Ｂが「１，０」であった場合、「ＡＢ−＝１」を代入する。このようにして、予測部２３は、予測対象データを線形モデルに入力したときの値を算出し、算出された値が「０．５」以上であればある事象に該当する「真：＋」と予測し、算出された値が「０．５」未満であればある事象に該当しない「偽：−」と予測する。そして、予測部２３は、予測結果をディスプレイに表示したり、管理者端末に送信したりする。
【００４４】
［処理の流れ］
図６は、学習処理の流れを示すフローチャートである。図６に示すように、学習部２１は、学習開始が管理者等により指示されると（Ｓ１０１：Ｙｅｓ）、訓練データＤＢ１３から各訓練データを読み込み（Ｓ１０２）、複数の決定木を生成する学習を実行する（Ｓ１０３）。そして、学習部２１は、学習が終了するまで（Ｓ１０４：Ｎｏ）、Ｓ１０２以降を繰り返す。なお、学習を終了するタイミングは、予め定めた数の訓練データを用いて学習が実行された場合など、任意に設定することができる。
【００４５】
そして、生成部２２は、学習が終了すると（Ｓ１０４：Ｙｅｓ）、生成された森モデルに含まれる各決定木に対応する線形モデル（部分的な線形モデル）を生成する（Ｓ１０５）。続いて、生成部２２は、各決定木に対応する部分的な線形モデルと、森モデルに含まれる決定木の数とを用いて、森モデルと同等の線形モデルを生成する（Ｓ１０６）。
【００４６】
その後、予測部２３は、予測開始が指示されると（Ｓ１０７：Ｙｅｓ）、予測対象ＤＢ１５から予測対象データを読み込み（Ｓ１０８）、Ｓ１０６で生成された線形モデルに入力して予測結果を取得する（Ｓ１０９）。そして、予測部２３は、予測対象データが残っている場合（Ｓ１１０：Ｎｏ）、Ｓ１０８以降を繰り返し、予測を終了する場合（Ｓ１１０：Ｙｅｓ）、処理を終了する。
【００４７】
なお、図６では、学習と予測とを一連のフローで実行する例を説明したが、これに限定されるものではなく、別々のフローで実行することもできる。また、学習処理は、訓練データが更新されるたびに繰り返し実行され、線形モデルを随時更新することができる。
【００４８】
［効果］
上述したように、学習装置１０は、訓練データから作成できる各決定木に対応する部分的な線形モデルを生成し、各部分的な線形モデルの和を用いて、森モデルに対応する線形モデルを生成することができる。したがって、学習装置１０は、安定した予測を得る学習モデルを構築することができる。また、学習装置１０は、決定木による判定と多数決による判定を実行せずに、１つの線形モデルによって、予測対象データに対して予測を実行することができるので、処理時間を短縮することができる。
【００４９】
また、学習装置１０は、生成部２２が訓練データから生成され得る決定木を決定的にすべて生成することで、決定木による偏りを抑制できるので、偏りによる精度劣化を抑制できる。また、学習装置１０は、各訓練データに対応する決定木の線形モデルを生成するので、決定木に偏りがないことを示すこともできる。また、学習装置１０は、偏りを抑制できるので、同じデータからは常に同じ結果を得ることができ、決定木の数が増えたとしても学習や適用を高速化できる。すなわち、学習装置１０は、ランダムフォレストの欠点を克服できる。
【実施例２】
【００５０】
ところで、実施例１では、複数の決定木を含む森モデルを一度生成してから、線形モデルを生成する例を説明したが、これに限定されるものではない。例えば、森モデルの大きさがキューブの数に比較して十分に大きいとき、決定木を一つずつ変換して合計するよりも、各キューブに対してそれを含む決定木の数を数え上げるほうが容易な場合がある。そこで、実施例２では、森モデルが構築されたと仮定したときにそのパスを含む決定木の数を計数し、線形モデルの係数を、実際に森モデルを構築せずに生成することで、学習時の計算時間を削減する。
【００５１】
［学習装置の説明］
図７は、実施例２にかかる学習装置１０を説明する図である。図７に示すように、実施例２にかかる学習装置１０は、訓練データから森モデルを生成せずに、訓練データが有するリテラルの積を用いた各キューブを生成し、各キューブに含まれる決定木を計数する。
【００５２】
具体的には、学習装置１０は、訓練データからキューブＣ１からキューブＣｉ（ｉは自然数）を生成する。そして、学習装置１０は、各キューブに対して、キューブを含む決定木Ｔ１から決定木Ｔｎ（ｎは自然数）を検討してその数を計数する。このようにして、学習装置１０は、訓練データから生成できる各キューブと、キューブを含むと考えうる決定木の数とを特定し、これらを用いて線形モデルを生成する。例えば、森モデルＦにキューブＣを含む木の本数を「＃Ｆ（Ｃ）」とした場合、線形モデルＹは式（１）にように算出することができる。
【００５３】
【数１】
2020046891.tif 000003
【００５４】
ここで、単純な決定木を例にして説明する。図８は、単純な決定木の例を示す図である。図８に示すように、単純な決定木は、真（＋）（または偽（−））の葉が１個であり、キューブ１個の線形モデルに変換できる決定木である。ｎ個のデータの部分集合それぞれに対して単純な決定木を列挙する。列挙対象は、チャンスレート（例えば０．５）より高い精度が出せるすべての決定木とする。
【００５５】
この場合、ｎ個のデータの部分集合を例にすると、変数の数をｍとして１つの部分集合に対して２ｎ＋ｍ個程度の決定木を含む森モデルが生成できる。例えば、ｎ＝２００、ｍ＝２０とした場合、２２２０程度の決定木を含む森モデルとなることから、多数決を用いる手法では、膨大な時間がかかり、現実的ではない。このように森モデルに含まれる決定木の数が膨大な時は、実施例２で説明する手法が特に有効である。
【００５６】
図９は、単純な森モデルの単純な決定木を用いた具体例を説明する図である。学習装置１０の学習部２１は、係数を求めるそれぞれのキューブに対して、ｎ個の訓練データから、キューブＱの条件を満たす（Ｑの中にある）正例データと、条件を満たさない（Ｑの外にある）負例データの合計である「ａ値」を求める。上記の合計に含まれなかったデータ数（キューブＱの条件を満たす負例データと、条件を満たさない正例データの合計）である「ｂ値（ｂ＝ｎ−ａ）」を求める。
【００５７】
また、学習部２１は、０以上ａ以下の整数ｉと、０以上ｂ以下の整数ｊに対して、ａからｉ個選択する組合せ個数Ｃ（ａ，ｉ）と、ｂからｊ個選択する組合せの個数Ｃ（ｂ，ｊ）の積をすべて求める。そして、学習部２１は、訓練データの正例割合を「ｒ＝正例数／ｎ」としたとき、上記の組合せの個数のうち、ｉ／（ｉ＋ｊ）＞ｒとｉ／（ｉ＋ｊ）＜ｒを満たす  ｉ，ｊに関するものの合計＃（Ｐ）と＃（Ｎ）をそれぞれ求める。
【００５８】
このようにして、キューブＱの係数「＃（Ｐ）−＃（Ｎ）」と定数「＃（Ｎ）」、キューブＱに関する木の合計本数「＃（Ｐ）＋＃（Ｎ）」を求め、すべてのキューブに対して、定数と係数を合計し、決定木の合計本数の和で除することで単純な決定木を使った森モデルと同等の結果を返す線形モデルを得ることができる。
【００５９】
図９で説明すると、学習部２１は、あるキューブＱを真（＋）として持つ決定木の数と、偽（−）として持つ決定木の数とを計数する。ここで、学習部２１は、キューブ内の正例数＋キューブ外の負例数の数を「ａ個」、キューブ内の負例数＋キューブ外の正例数の数を「ｂ個」とした場合、図９に示す表を生成する。なお、チャンスレートは０．５とする。
【００６０】
図９に示される表から、ｉ／（ｉ＋ｊ）＝０．５＝ｒとなる場合、＃（Ｐ）に計数されるｉ／（ｉ＋ｊ）＞ｒの条件、および、＃（Ｎ）に計数されるｉ／（ｉ＋ｊ）＜ｒの条件のいずれも満たさず、いずれの木も存在しないこととなるから、上記ａとｂのそれぞれを同じ数だけ選択する条件（図１０の対角線）は対象外とする。
【００６１】
例えば、学習部２１は、表の対角線から右上に該当する、「真（＋）」の枝を持つ単純な決定木の数の和を「＃（Ｐ）」と計数する。また、学習部２１は、表の対角線から左下に該当する、「偽（−）」の枝を持つ単純な決定木の数の和を「＃（Ｎ）」と計数する。そして、生成部２２は、図９に対応するキューブに関する線形モデル（部分的な線形モデル）として、「＃（Ｐ）Ｑ＋＃（Ｎ）（１−Ｑ）＝＃（Ｎ）＋（＃（Ｐ）−＃（Ｎ））Ｑ」を算出する。
【００６２】
図１０を用いて具体例を説明する。図１０は、キューブに対応する線形モデルの生成の具体例を説明する図である。学習部２１により、図１０の（ａ）に示す訓練データから、訓練データの変数Ａ、Ｂ、Ｃ、Ｄの組み合わせにより、図１０に（ｂ）に示す表ができたとする。この例では、図１０の（ｂ）におけるキューブＱ（Ｑ＝Ｂ−Ｃ）を含む単純な決定木の数を計数する例を説明する。
【００６３】
図１０の（ｂ）より、学習部２１は、キューブＱ内の正例数が１かつキューブ外の負例数が０であることから上記「ａ値」を「１」と計数し、キューブＱ内の負例数が２かつキューブ外の正例数が１であることから上記「ｂ値」を「３」と計数する。
【００６４】
続いて、学習部２１は、「ａ値」を横軸、「ｂ値」を縦軸とする図１０の（ｃ）に示す表を生成し、キューブＱを含む決定木の本数を計数する。具体的には、学習部２１は、正例の葉へのパスを有する決定木が正解する数として、「ａ値」から１つを選択する組み合わせである「１」を計数する。また、学習部２１は、負例の葉へのパスを有する決定木が正解する数として、「ｂ値」から１つを選択する組み合わせである「３」、「ｂ値」から２つを選択する組み合わせである「３」、「ｂ値」から３つを選択する組み合わせである「１」を計数する。同様に、学習部２１は、負例の葉へのパスを有する決定木が正解する数として、「ｂ値」から２つと「ａ値」から１つを選択する組み合わせである「３」、「ｂ値」から３つと「ａ値」から１つを選択する組み合わせである「１」を計数する。
【００６５】
すなわち、学習部２１は、正例の葉へのパスを有する決定木の総数「＃（Ｐ）」を「１本」と、負例の葉へのパスを有する決定木の総数「＃（Ｎ）」を「３＋３＋１＋３＋１＝１１本」と算出する。この結果、学習部２１は、キューブＱに対応する線形モデルとして、「＃（Ｐ）Ｑ＋＃（Ｎ）（１−Ｑ）＝１Ｑ＋１１（１−Ｑ）＝１１−１０Ｑ」を生成することができる。
【００６６】
その後、学習部２１は、図１０の（ｂ）に示す表に含まれる各キューブに対して線形モデルの生成および当該キューブを含む決定木の本数の計数を実行する。生成部２２は、学習部２１の結果を用いて、訓練データから決定的にもれなく生成される複数の決定木を含む森モデルと等価な線形モデル（学習モデル）を生成する。
【００６７】
図１１は、実施例２にかかる線形モデルの具体例を説明する図である。図１１に示すように、学習部２１により、キューブＱ１について「線形モデルＸ」および決定木の本数「ｘ」、キューブＱ２について「線形モデルＹ」および決定木の本数「ｙ」、キューブＱ３について「線形モデルＺ」および決定木の本数「ｚ」、キューブＱ４について「線形モデルＧ」および決定木の本数「ｇ」、キューブＱ５について「線形モデルＨ」および決定木の本数「ｈ」が生成されたとする。
【００６８】
この場合、生成部２２は、最終的な線形モデル（学習モデル）として、「Ｙ＝各線形モデルの和（Ｘ＋Ｙ＋Ｚ＋Ｇ＋Ｈ）／各線形モデルを含む決定木の総数の和（ｘ＋ｙ＋ｚ＋ｇ＋ｈ）」を生成する。この結果、学習装置１０は、実際に森モデルを構築せずに、学習済みの学習モデルである線形モデルを生成することができ、学習時の計算時間を削減することができる。
【００６９】
［処理の流れ］
図１２は、実施例２にかかる学習処理の流れを示すフローチャートである。図１２に示すように、学習装置１０は、学習開始が指示されると（Ｓ２０１：Ｙｅｓ）、訓練データＤＢ１３から訓練データを読み込む（Ｓ２０２）。
【００７０】
続いて、学習装置１０は、訓練データのリテラルを特定し、複数のキューブを抽出する（Ｓ２０３）。そして、学習装置１０は、１つのキューブを選択し（Ｓ２０４）、キューブに対応する線形モデルの生成し、線形モデルが含まれる決定木の本数を計数する（Ｓ２０５）。
【００７１】
ここで、未処理にキューブが存在する場合（Ｓ２０６：Ｎｏ）、Ｓ２０４以降が繰り返される。一方、全キューブについて処理が完了すると（Ｓ２０６：Ｙｅｓ）、学習装置１０は、各キューブに対応する線形モデルの和を算出し（Ｓ２０７）、各キューブが含まれる決定木の本数を加算する（Ｓ２０８）。
【００７２】
そして、学習装置１０は、線形モデルの和を決定木の本数で除算することで、森モデルと等価な線形モデルを生成する（Ｓ２０９）。なお、予測処理は、実施例１と同様なので、詳細な説明は省略する。
【００７３】
［効果］
上述したように、学習装置１０は、２ｍ＋ｎ個程度の木の多数決による森モデルを２ｍｎ２回程度のカウンティングで計算でき、処理速度を高速化することができる。図１３は、一般技術との比較結果を説明する図である。図１３では、図１０の（ａ）の訓練データにおいて、「（データ２）、（データ２，３，４）、（データ２，４）」の各データセットが選択された場合（１）と、「（データ１，３）、（データ１、２，３）、（データ２）」の各データセットが選択された場合（２）と、実施例２による手法（３）との比較結果を示す。
【００７４】
（１）の手法では＃（Ｐ）の数が０となり、（２）の手法では＃（Ｎ）の数が０となり、サンプリングによる極端な結果になることを抑制できない。これに対して、実施例２の手法は、各決定木を漏れなく検討できるので、＃（Ｐ）と＃（Ｎ）についても検討することができ、極端な結果に偏った学習モデルの生成を抑制することができる。
【実施例３】
【００７５】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。
【００７６】
［パスの限定］
例えば、線形モデルに使用するパスを限定することもできる。具体的には、説明変数のリテラルの数が所定値以下となるパスに制限する。一つのリテラルはある説明変数の値が１（肯定:真）または０（否定：偽）であることに対応しているため、リテラルの数が所定の値以下である条件は、関係する説明変数を所定の数以下に制限することになり、学習の汎化性を高めることができる。
【００７７】
［システム］
上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００７８】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散や統合の具体的形態は図示のものに限られない。つまり、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、学習部２１と生成部２２とを有する学習装置と、予測部２３を有する判別装置とのように、学習と予測とを別々の装置で構成することもできる。
【００７９】
さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００８０】
［ハードウェア］
図１４は、ハードウェア構成例を説明する図である。図１４に示すように、学習装置１０は、通信インタフェース１０ａ、ＨＤＤ（Hard  Disk  Drive）１０ｂ、メモリ１０ｃ、プロセッサ１０ｄを有する。また、図１４に示した各部は、バス等で相互に接続される。
【００８１】
通信インタフェース１０ａは、ネットワークインタフェースカードなどであり、他のサーバとの通信を行う。ＨＤＤ１０ｂは、図２に示した機能を動作させるプログラムやＤＢを記憶する。
【００８２】
プロセッサ１０ｄは、図２に示した各処理部と同様の処理を実行するプログラムをＨＤＤ１０ｂ等から読み出してメモリ１０ｃに展開することで、図２等で説明した各機能を実行するプロセスを動作させる。すなわち、このプロセスは、学習装置１０が有する各処理部と同様の機能を実行する。具体的には、プロセッサ１０ｄは、学習部２１、生成部２２、予測部２３等と同様の機能を有するプログラムをＨＤＤ１０ｂ等から読み出す。そして、プロセッサ１０ｄは、学習部２１、生成部２２、予測部２３等と同様の処理を実行するプロセスを実行する。
【００８３】
このように学習装置１０は、プログラムを読み出して実行することで予測方法を実行する情報処理装置として動作する。また、学習装置１０は、媒体読取装置によって記録媒体から上記プログラムを読み出し、読み出された上記プログラムを実行することで上記した実施例と同様の機能を実現することもできる。なお、この他の実施例でいうプログラムは、学習装置１０によって実行されることに限定されるものではない。例えば、他のコンピュータまたはサーバがプログラムを実行する場合や、これらが協働してプログラムを実行するような場合にも、本発明を同様に適用することができる。
【符号の説明】
【００８４】
１０  学習装置
１１  通信部
１２  記憶部
１３  訓練データＤＢ
１４  学習結果ＤＢ
１５  予測対象ＤＢ
２０  制御部
２１  学習部
２２  生成部
２３  予測部
【図１】
2020046891.tif 000004
【図２】
2020046891.tif 000005
【図３】
2020046891.tif 000006
【図４】
2020046891.tif 000007
【図５】
2020046891.tif 000008
【図６】
2020046891.tif 000009
【図７】
2020046891.tif 000010
【図８】
2020046891.tif 000011
【図９】
2020046891.tif 000012
【図１０】
2020046891.tif 000013
【図１１】
2020046891.tif 000014
【図１２】
2020046891.tif 000015
【図１３】
2020046891.tif 000016
【図１４】
2020046891.tif 000017