(57)【要約】【課題】複数の機械学習アルゴリズムの間の予測性能に関する比較の精度を向上させる。【解決手段】処理部１２は、第１の機械学習アルゴリズムを用いて、サンプルサイズ１６ａ，１６ｂの訓練データを用いて複数の学習モデルを生成することにより、予測性能測定値１７ａ，１７ｂを算出する。処理部１２は、予測性能に関する期待値と分散の間の関係を示す関係情報１３と予測性能測定値１７ａ，１７ｂとを用いて、分散推定値１８ａ，１８ｂを算出する。処理部１２は、予測性能測定値１７ａ，１７ｂと分散推定値１８ａ，１８ｂとを用いた回帰分析により、予測性能曲線１４を生成する。処理部１２は、予測性能曲線１４とサンプルサイズ１６ｃとに基づいて評価値１９ａを算出する。処理部１２は、評価値１９ａと、第２の機械学習アルゴリズムに対応する予測性能曲線１５とサンプルサイズ１６ｃとに基づいて算出される評価値１９ｂとを比較する。【選択図】図１
2018173813.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
第１の機械学習アルゴリズムを用いて、同一のデータ母集合から抽出される複数の第１のサンプルサイズの訓練データを用いて複数の学習モデルを生成することにより、前記複数の学習モデルそれぞれが有する予測性能の測定結果を示す複数の予測性能測定値を算出し、
予測性能に関する期待値と分散との間の関係を示す関係情報と、前記複数の予測性能測定値とを用いて、前記複数の第１のサンプルサイズそれぞれに対して生じる予測性能の分散の推定結果を示す複数の分散推定値を算出し、
前記複数の予測性能測定値と前記複数の分散推定値とを用いた回帰分析により、サンプルサイズと予測性能との間の関係を示す曲線であって予測性能が一定の予測性能上限値に漸近する第１の予測性能曲線を生成し、
前記第１の予測性能曲線と第２のサンプルサイズとに基づいて前記第１の機械学習アルゴリズムに対する第１の評価値を算出し、
前記第１の評価値と、第２の機械学習アルゴリズムに対応する第２の予測性能曲線と前記第２のサンプルサイズとに基づいて算出される前記第２の機械学習アルゴリズムに対する第２の評価値とを比較する、
処理を実行させる比較プログラム。
【請求項２】
前記関係情報は、予測の失敗度の期待値を示す期待ロスと前記期待ロスの低下限界を示す期待バイアスと予測性能の分散との間の関係を示し、
前記複数の分散推定値の算出では、前記複数の予測性能測定値に基づいて、前記複数の第１のサンプルサイズそれぞれに対する前記期待ロスの推定結果を示す複数の期待ロス推定値と、前記期待バイアスの推定結果を示す期待バイアス推定値とを算出し、前記複数の期待ロス推定値と前記期待バイアス推定値とを用いて前記複数の分散推定値を算出する、
請求項１記載の比較プログラム。
【請求項３】
前記関係情報は、予測性能の分散が前記期待ロスと前記期待バイアスの和に比例しかつ前記期待ロスと前記期待バイアスの差に比例することを示す、
請求項２記載の比較プログラム。
【請求項４】
前記第１の予測性能曲線の生成では、前記複数の分散推定値に基づいて、分散推定値が小さいほど重みが大きくなるように前記複数の予測性能測定値に対して複数の重みを割り当て、前記複数の予測性能測定値と前記複数の重みとを用いて前記回帰分析を行う、
請求項１記載の比較プログラム。
【請求項５】
コンピュータが実行する比較方法であって、
第１の機械学習アルゴリズムを用いて、同一のデータ母集合から抽出される複数の第１のサンプルサイズの訓練データを用いて複数の学習モデルを生成することにより、前記複数の学習モデルそれぞれが有する予測性能の測定結果を示す複数の予測性能測定値を算出し、
予測性能に関する期待値と分散との間の関係を示す関係情報と、前記複数の予測性能測定値とを用いて、前記複数の第１のサンプルサイズそれぞれに対して生じる予測性能の分散の推定結果を示す複数の分散推定値を算出し、
前記複数の予測性能測定値と前記複数の分散推定値とを用いた回帰分析により、サンプルサイズと予測性能との間の関係を示す曲線であって予測性能が一定の予測性能上限値に漸近する第１の予測性能曲線を生成し、
前記第１の予測性能曲線と第２のサンプルサイズとに基づいて前記第１の機械学習アルゴリズムに対する第１の評価値を算出し、
前記第１の評価値と、第２の機械学習アルゴリズムに対応する第２の予測性能曲線と前記第２のサンプルサイズとに基づいて算出される前記第２の機械学習アルゴリズムに対する第２の評価値とを比較する、
比較方法。
【請求項６】
同一のデータ母集合から抽出される複数の第１のサンプルサイズの訓練データおよび第１の機械学習アルゴリズムを用いて生成される複数の学習モデルそれぞれが有する予測性能の測定結果を示す複数の予測性能測定値と、予測性能に関する期待値と分散との間の関係を示す関係情報とを記憶する記憶部と、
前記関係情報と前記複数の予測性能測定値とを用いて、前記複数の第１のサンプルサイズそれぞれに対して生じる予測性能の分散の推定結果を示す複数の分散推定値を算出し、前記複数の予測性能測定値と前記複数の分散推定値とを用いた回帰分析により、サンプルサイズと予測性能との間の関係を示す曲線であって予測性能が一定の予測性能上限値に漸近する第１の予測性能曲線を生成し、前記第１の予測性能曲線と第２のサンプルサイズとに基づいて前記第１の機械学習アルゴリズムに対する第１の評価値を算出し、前記第１の評価値と、第２の機械学習アルゴリズムに対応する第２の予測性能曲線と前記第２のサンプルサイズとに基づいて算出される前記第２の機械学習アルゴリズムに対する第２の評価値とを比較する処理部と、
を有する比較装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は比較プログラム、比較方法および比較装置に関する。
【背景技術】
【０００２】
コンピュータを利用したデータ分析の１つとして、機械学習が行われることがある。機械学習では、幾つかの既知の事例を示す訓練データをコンピュータに入力する。コンピュータは、訓練データを分析して、要因（説明変数や独立変数と言うことがある）と結果（目的変数や従属変数と言うことがある）との間の関係を一般化したモデルを学習する。学習されたモデルを用いることで、未知の事例についての結果を予測することができる。
【０００３】
機械学習では、学習されるモデルの正確さ、すなわち、未知の事例の結果を正確に予測する能力（予測性能と言うことがある）が高いことが好ましい。予測性能は、学習に用いる訓練データのサンプルサイズが大きいほど高くなる。一方、訓練データのサンプルサイズが大きいほど学習時間も長くなる。そこで、実用上十分な予測性能をもつモデルを効率的に得られるようにする方法として、プログレッシブサンプリング法が提案されている。
【０００４】
プログレッシブサンプリング法では、コンピュータは、まず小さなサンプルサイズの訓練データを用いてモデルを学習する。コンピュータは、訓練データとは異なる既知の事例を示すテストデータを用いて、モデルによって予測した結果と既知の結果とを比較し、学習されたモデルの予測性能を評価する。予測性能が十分でない場合、コンピュータは、前回よりもサンプルサイズが大きい訓練データを用いてモデルを再度学習する。以上を予測性能が十分に高くなるまで繰り返すことで、過度にサンプルサイズの大きな訓練データを使用することを抑制でき、モデルの学習時間を短縮することができる。
【０００５】
また、小さなサンプルサイズの訓練データに対応する予測性能の実測値を用いて、訓練データのサンプルサイズと予測性能との間の関係を示す予測性能曲線を推定し、推定した予測性能曲線を用いて大きなサンプルサイズの訓練データに対応する予測性能を算出する方法が提案されている。提案の方法では、予測性能曲線を示す推定式として、サンプルサイズが小さいうちは予測性能の上昇量が大きく、サンプルサイズが大きくなると予測性能が一定の上限値に収束する非線形関数が仮定される。提案の方法では、予測性能の実測値を用いて非線形回帰分析を行い、推定式に含まれる未知の係数を決定する。
【０００６】
また、非線形回帰分析によって予測性能曲線を推定する際に、複数の予測性能の実測値に対して異なる重みを付与する方法も提案されている。提案の方法では、小さなサンプルサイズの訓練データに対応する実測値には小さな重みを付与し、大きなサンプルサイズの訓練データに対応する実測値には大きな重みを付与する。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Foster Provost, David Jensen and Tim Oates, "Efficient Progressive Sampling", Proc. of the 5th International Conference on Knowledge Discovery and Data Mining, pp. 23-32, Association for Computing Machinery (ACM), 1999.
【非特許文献２】Prasanth Kolachina, Nicola Cancedda, Marc Dymetman and Sriram Venkatapathy, "Prediction of Learning Curves in Machine Translation", Proc. of the 50th Annual Meeting of the Association for Computational Linguistics, pp. 22-30, 2012.
【非特許文献３】Rosa L Figueroa, Qing Zeng-Treitler, Sasikiran Kandula and Long H Ngo, "Predicting sample size required for classification performance", BMC Medical Informatics and Decision Making, Vol. 12 No. 8, 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ところで、訓練データからモデルを生成するアルゴリズムとして、回帰分析、サポートベクタマシン（ＳＶＭ）、ランダムフォレストなど様々な機械学習アルゴリズムがある。使用する機械学習アルゴリズムが異なると、生成されるモデルの予測性能も異なることが多い。そのため、複数の機械学習アルゴリズムを試行する方が、１つの機械学習アルゴリズムのみを使用する場合よりも予測性能を向上できることが多い。
【０００９】
複数の機械学習アルゴリズムを使用する機械学習では、機械学習アルゴリズム毎に予測性能曲線を推定し、推定した予測性能曲線に基づいて複数の機械学習アルゴリズムの間でモデルの予測性能に関する比較を行い、機械学習を制御することが考えられる。例えば、大きなサンプルサイズにおける予測性能の推定値が高い機械学習アルゴリズムを優先的に実行することなどが考えられる。各機械学習アルゴリズムの予測性能曲線は、例えば、幾つかの小さなサンプルサイズの訓練データによってモデルを生成して予測性能を測定し、幾つかの予測性能の実測値から回帰分析によって算出することが考えられる。
【００１０】
しかし、予測性能の実測値は、訓練データおよびテストデータの選択の偶然性などの影響を受けて、期待値からの乖離としての誤差を含んでいる。このとき、訓練データのサンプルサイズが異なると偶然性の影響度が異なるため、予測性能の実測値に含まれる誤差はサンプルサイズによって変わる。特に、小さなサンプルサイズにおける予測性能の実測値は、偶然性の影響を強く受けて大きな誤差を含むことがある。
【００１１】
そのため、上記の非特許文献２のように、等分散性を前提とした通常の回帰分析によって予測性能曲線を推定すると、予測性能曲線の推定精度が低下するという問題がある。また、予測性能の実測値に含まれる誤差の程度を直接的に把握することは難しい。
【００１２】
上記の非特許文献３は予測性能の実測値に重みを付与しているものの、実際の誤差の程度を反映しておらず、予測性能曲線の推定精度を向上させることが難しいという問題がある。よって、複数の機械学習アルゴリズムの間の予測性能に関する比較の精度が低くなってしまう。
【００１３】
１つの側面では、本発明は、複数の機械学習アルゴリズムの間の予測性能に関する比較の精度を向上させる比較プログラム、比較方法および比較装置を提供することを目的とする。
【課題を解決するための手段】
【００１４】
１つの態様では、コンピュータに以下の処理を実行させる比較プログラムが提供される。第１の機械学習アルゴリズムを用いて、同一のデータ母集合から抽出される複数の第１のサンプルサイズの訓練データを用いて複数の学習モデルを生成することにより、複数の学習モデルそれぞれが有する予測性能の測定結果を示す複数の予測性能測定値を算出する。予測性能に関する期待値と分散との間の関係を示す関係情報と、複数の予測性能測定値とを用いて、複数の第１のサンプルサイズそれぞれに対して生じる予測性能の分散の推定結果を示す複数の分散推定値を算出する。複数の予測性能測定値と複数の分散推定値とを用いた回帰分析により、サンプルサイズと予測性能との間の関係を示す曲線であって予測性能が一定の予測性能上限値に漸近する第１の予測性能曲線を生成する。第１の予測性能曲線と第２のサンプルサイズとに基づいて第１の機械学習アルゴリズムに対する第１の評価値を算出する。第１の評価値と、第２の機械学習アルゴリズムに対応する第２の予測性能曲線と第２のサンプルサイズとに基づいて算出される第２の機械学習アルゴリズムに対する第２の評価値とを比較する。
【００１５】
また、１つの態様では、コンピュータが実行する比較方法が提供される。また、１つの態様では、記憶部と処理部とを有する比較装置が提供される。
【発明の効果】
【００１６】
１つの側面では、複数の機械学習アルゴリズムの間の予測性能に関する比較の精度を向上できる。
【図面の簡単な説明】
【００１７】
【図１】第１の実施の形態の比較装置を説明する図である。
【図２】機械学習装置のハードウェア例を示すブロック図である。
【図３】サンプルサイズと予測性能の関係例を示すグラフである。
【図４】学習時間と予測性能の関係例を示すグラフである。
【図５】複数の機械学習アルゴリズムの使用例を示す図である。
【図６】予測性能の分布例を示すグラフである。
【図７】予測性能曲線の推定例を示すグラフである。
【図８】サンプルサイズとロスの関係例を示すグラフである。
【図９】機械学習装置の機能例を示すブロック図である。
【図１０】管理テーブルの例を示す図である。
【図１１】性能改善量推定部の機能例を示すブロック図である。
【図１２】機械学習の手順例を示すフローチャートである。
【図１３】機械学習の手順例を示すフローチャート（続き）である。
【図１４】ステップ実行の手順例を示すフローチャートである。
【図１５】時間推定の手順例を示すフローチャートである。
【図１６】性能改善量推定の手順例を示すフローチャートである。
【図１７】予測性能曲線算出の手順例を示すフローチャートである。
【図１８】予測性能の分布の第１の推定例を示すグラフである。
【図１９】予測性能の分布の第２の推定例を示すグラフである。
【図２０】予測性能の分布の第３の推定例を示すグラフである。
【発明を実施するための形態】
【００１８】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。
【００１９】
図１は、第１の実施の形態の比較装置を説明する図である。
第１の実施の形態の比較装置１０は、機械学習に用いる訓練データのサンプルサイズと学習モデルの予測性能との間の関係を示す予測性能曲線を推定し、異なる機械学習アルゴリズムの間で予測性能に関する比較を行う。比較装置１０は、ユーザが操作するクライアント装置でもよいしサーバ装置でもよい。比較装置１０はコンピュータでもよい。
【００２０】
比較装置１０は、記憶部１１および処理部１２を有する。記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性の半導体メモリでもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性のストレージでもよい。処理部１２は、例えば、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサである。ただし、処理部１２は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路を含んでもよい。プロセッサは、ＲＡＭなどのメモリ（記憶部１１でもよい）に記憶されたプログラムを実行する。プログラムには比較プログラムが含まれる。複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」と言うこともある。
【００２１】
記憶部１１は、関係情報１３と予測性能測定値１７ａ，１７ｂとを記憶する。
予測性能測定値１７ａ，１７ｂは、処理部１２によって算出される。処理部１２は、第１の機械学習アルゴリズムにより同一のデータ母集合から抽出されるサンプルサイズ１６ａ，１６ｂの訓練データを用いて異なる学習モデルを生成し、異なる学習モデルが有する予測性能の測定結果を示す予測性能測定値１７ａ，１７ｂを算出する。予測性能測定値１７ａはサンプルサイズ１６ａに対応し、予測性能測定値１７ｂはサンプルサイズ１６ｂに対応する。第１の実施の形態では説明を簡単にするため、処理部１２は２つのサンプルサイズに対応する２つの予測性能測定値を算出しているが、３以上のサンプルサイズに対応する３以上の予測性能測定値を算出してもよい。なお、機械学習アルゴリズムの種類には、ロジスティック回帰分析、サポートベクタマシン、ランダムフォレストなどが含まれる。予測性能は、未知の事例の結果を正確に予測する能力であり「精度」と言うこともできる。予測性能の指標には、正答率（Accuracy）、適合率（Precision）、平均二乗誤差（ＭＳＥ）、二乗平均平方根誤差（ＲＭＳＥ）などが含まれる。
【００２２】
関係情報１３は、予測性能に関する期待値と分散との間の所定の関係を示す。関係情報１３が示す関係は、予測性能に関する期待値と分散との間に経験的に見出された法則であってもよい。関係情報１３が示す関係は、例えば、所定の数式によって表現される。関係情報１３は、学習モデルによる予測の失敗度の期待値を示す期待ロスＥＬと、第１の機械学習アルゴリズムにとっての期待ロスの低下限界を示す期待バイアスＥＢ２と、予測性能の分散ＶＬとの間の関係を示すものであってもよい。また、関係情報１３は、予測性能の分散ＶＬが、期待ロスＥＬと期待バイアスＥＢ２の和に比例し、かつ、期待ロスＥＬと期待バイアスＥＢ２の差に比例することを示すものであってもよい。
【００２３】
処理部１２は、関係情報１３と予測性能測定値１７ａ，１７ｂとを用いて、サンプルサイズ１６ａ，１６ｂに対して生じる予測性能の分散の推定結果を示す分散推定値１８ａ，１８ｂを算出する。分散推定値１８ａはサンプルサイズ１６ａにおける予測性能の分散を示し、分散推定値１８ｂはサンプルサイズ１６ｂにおける予測性能の分散を示す。通常、サンプルサイズが小さいほど予測性能の分散は大きくなる。
【００２４】
例えば、処理部１２は、予測性能測定値１７ａ，１７ｂをそれぞれ期待ロス推定値に変換すると共に、予測性能測定値１７ａ，１７ｂに基づいて第１の機械学習アルゴリズムにとっての期待バイアス推定値を算出する。予測性能測定値１７ａ，１７ｂを期待ロス推定値に変換する方法は、使用する予測性能の指標や期待ロスの指標に依存する。例えば、予測性能測定値ｙに対応する期待ロス推定値は、１−ｙ，ｙ，ｙ2などになることがある。期待バイアス推定値は、例えば、予測性能測定値１７ａ，１７ｂを試行錯誤的に曲線にフィッティングすることで、期待ロスの下限値として算出することができる。処理部１２は、複数の期待ロス推定値それぞれと期待バイアス推定値とを関係情報１３が示す式に代入することで、分散推定値１８ａ，１８ｂを算出することができる。
【００２５】
処理部１２は、予測性能測定値１７ａ，１７ｂと分散推定値１８ａ，１８ｂを用いて、非線形回帰分析により、第１の機械学習アルゴリズムについての予測性能曲線１４を生成する。予測性能曲線１４は、サンプルサイズと予測性能との間の関係を示す曲線であって、予測性能が一定の予測性能上限値に漸近する非線形の回帰曲線である。このとき、処理部１２は、分散推定値１８ａ，１８ｂに応じて予測性能測定値１７ａ，１７ｂに対して重みを付与してもよい。分散推定値が大きいほど重みが小さくなることが好ましく、例えば、重みは分散推定値に反比例する。重みが小さいことは、予測性能曲線１４上の予測性能推定値と予測性能測定値との間に大きな残差が許容されることを意味する。
【００２６】
処理部１２は、予測性能曲線１４とサンプルサイズ１６ｃとに基づいて、第１の機械学習アルゴリズムに対する評価値１９ａを算出する。サンプルサイズ１６ｃは、例えば、予測性能測定値を算出済みであるサンプルサイズ１６ａ，１６ｂよりも大きい。評価値１９ａは、サンプルサイズ１６ｃの予測性能の推定結果に関する値である。例えば、処理部１２は、予測性能曲線１４によって推定されるサンプルサイズ１６ｃの予測性能推定値を求め、予測性能推定値または予測性能推定値から変換された値を評価値１９ａとする。
【００２７】
また、処理部１２は、第２の機械学習アルゴリズムについての予測性能曲線１５を取得する。処理部１２は、予測性能曲線１４と同様の方法で予測性能曲線１５を生成してもよい。処理部１２は、予測性能曲線１５とサンプルサイズ１６ｃとに基づいて、第２の機械学習アルゴリズムに対する評価値１９ｂを算出する。評価値１９ｂは、評価値１９ａと同様にサンプルサイズ１６ｃの予測性能の推定結果に関する値である。例えば、処理部１２は、予測性能曲線１５によって推定されるサンプルサイズ１６ｃの予測性能推定値を求め、予測性能推定値または予測性能推定値から変換された値を評価値１９ｂとする。
【００２８】
そして、処理部１２は、評価値１９ａと評価値１９ｂとを比較し、比較結果（評価値１９ａと評価値１９ｂの大小）に応じて機械学習の実行を制御する。例えば、処理部１２は、第１の機械学習アルゴリズムと第２の機械学習アルゴリズムのうち評価値が高い方の機械学習アルゴリズムが優先的に実行されるように制御する。
【００２９】
第１の実施の形態の比較装置１０によれば、ある機械学習アルゴリズムの複数のサンプルサイズにおける予測性能測定値と関係情報１３とから、各サンプルサイズで生じる分散を推定した分散推定値が算出される。複数のサンプルサイズそれぞれにおける予測性能測定値と分散推定値とを用いて、回帰分析により予測性能曲線１４が生成される。そして、予測性能曲線１４から算出される評価値１９ａと他の機械学習アルゴリズムの予測性能曲線１５から算出される評価値１９ｂとが比較される。
【００３０】
これにより、サンプルサイズによって予測性能の分散が異なること（異分散性）を考慮しない場合よりも、予測性能曲線１４の推定精度が向上する。その結果、異なる機械学習アルゴリズムの間の予測性能に関する比較の精度を向上させることができる。
【００３１】
［第２の実施の形態］
次に、第２の実施の形態を説明する。
図２は、機械学習装置のハードウェア例を示すブロック図である。
【００３２】
機械学習装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７を有する。ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７は、バス１０８に接続されている。なお、機械学習装置１００は、第１の実施の形態の比較装置１０に対応する。ＣＰＵ１０１は、第１の実施の形態の処理部１２に対応する。ＲＡＭ１０２またはＨＤＤ１０３は、第１の実施の形態の記憶部１１に対応する。
【００３３】
ＣＰＵ１０１は、プログラムの命令を実行する演算回路を含むプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されたプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、機械学習装置１００は複数のプロセッサを備えてもよく、以下で説明する処理を複数のプロセッサまたはプロセッサコアを用いて並列に実行してもよい。また、複数のプロセッサの集合（マルチプロセッサ）を「プロセッサ」と呼んでもよい。
【００３４】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムやＣＰＵ１０１が演算に用いるデータを一時的に記憶する揮発性の半導体メモリである。なお、機械学習装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。
【００３５】
ＨＤＤ１０３は、ＯＳ（Operating System）やミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性の記憶装置である。プログラムには比較プログラムが含まれる。なお、機械学習装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよく、複数の不揮発性の記憶装置を備えてもよい。
【００３６】
画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、機械学習装置１００に接続されたディスプレイ１１１に画像を出力する。ディスプレイ１１１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ（ＰＤＰ：Plasma Display Panel）、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなどを用いることができる。
【００３７】
入力信号処理部１０５は、機械学習装置１００に接続された入力デバイス１１２から入力信号を取得し、ＣＰＵ１０１に出力する。入力デバイス１１２としては、マウスやタッチパネルやタッチパッドやトラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなどを用いることができる。また、機械学習装置１００に、複数の種類の入力デバイスが接続されていてもよい。
【００３８】
媒体リーダ１０６は、記録媒体１１３に記録されたプログラムやデータを読み取る読み取り装置である。記録媒体１１３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。媒体リーダ１０６は、例えば、記録媒体１１３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００３９】
通信インタフェース１０７は、ネットワーク１１４に接続され、ネットワーク１１４を介して他の装置と通信を行うインタフェースである。通信インタフェース１０７は、スイッチなどの通信装置とケーブルで接続される有線通信インタフェースでもよいし、基地局と無線リンクで接続される無線通信インタフェースでもよい。
【００４０】
次に、機械学習におけるサンプルサイズと予測性能と学習時間の間の関係、および、プログレッシブサンプリング法について説明する。
第２の実施の形態の機械学習では、既知の事例を示す複数の単位データを含むデータを予め収集しておく。機械学習装置１００または他の情報処理装置が、センサデバイスなどの各種デバイスからネットワーク１１４経由でデータを収集してもよい。収集されるデータは、「ビッグデータ」と呼ばれるサイズの大きなデータであってもよい。各単位データは、通常、１以上の説明変数の値と１つの目的変数の値とを含む。例えば、商品の需要予測を行う機械学習では、気温や湿度など商品需要に影響を与える要因を説明変数とし、商品需要量を目的変数とした実績データを収集する。
【００４１】
機械学習装置１００は、収集されたデータの中から一部の単位データを訓練データとしてサンプリングし、訓練データを用いてモデルを学習する。モデルは、説明変数と目的変数との間の関係を示し、通常、１以上の説明変数と１以上の係数と１つの目的変数とを含む。モデルは、例えば、線形式、二次以上の多項式、指数関数、対数関数などの各種数式によって表されてもよい。数式の形は、機械学習の前にユーザによって指定されてもよい。係数は、機械学習によって訓練データに基づいて決定される。
【００４２】
学習されたモデルを用いることで、未知の事例の説明変数の値（要因）から、未知の事例の目的変数の値（結果）を予測することができる。例えば、来期の気象予報から来期の商品需要量を予測できる。モデルによって予測される結果は、０以上１以下の確率などの連続量であってもよいし、ＹＥＳ／ＮＯの２値などの離散値であってもよい。
【００４３】
学習されたモデルに対しては「予測性能」を算出することができる。予測性能は、未知の事例の結果を正確に予測する能力であり、「精度」と言うこともできる。機械学習装置１００は、収集されたデータの中から訓練データ以外の単位データをテストデータとしてサンプリングし、テストデータを用いて予測性能を算出する。テストデータのサイズは、例えば、訓練データのサイズの１／２程度とする。機械学習装置１００は、テストデータに含まれる説明変数の値をモデルに入力し、モデルが出力する目的変数の値（予測値）とテストデータに含まれる目的変数の値（実績値）とを比較する。なお、学習したモデルの予測性能を検証することを「バリデーション」と言うことがある。
【００４４】
予測性能の指標としては、正答率（Accuracy）、適合率（Precision）、平均二乗誤差（ＭＳＥ）、二乗平均平方根誤差（ＲＭＳＥ）などが挙げられる。例えば、結果がＹＥＳ／ＮＯの２値で表されるとする。また、Ｎ1件のテストデータの事例のうち、予測値＝ＹＥＳ・実績値＝ＹＥＳの件数をＴｐ、予測値＝ＹＥＳ・実績値＝ＮＯの件数をＦｐ、予測値＝ＮＯ・実績値＝ＹＥＳの件数をＦｎ、予測値＝ＮＯ・実績値＝ＮＯの件数をＴｎとする。正答率は予測が当たった割合であり、（Ｔｐ＋Ｔｎ）／Ｎ1と算出される。適合率は「ＹＥＳ」の予測を間違えない確率であり、Ｔｐ／（Ｔｐ＋Ｆｐ）と算出される。平均二乗誤差ＭＳＥは、各事例の実績値をｙと表し予測値をｙ＾と表すと、ｓｕｍ（ｙ−ｙ＾）2／Ｎ1と算出される。二乗平均平方根誤差ＲＭＳＥは、（ｓｕｍ（ｙ−ｙ＾）2／Ｎ1）1/2と算出される。ＭＳＥ＝ＲＭＳＥ2である。
【００４５】
ここで、ある１つの機械学習アルゴリズムを使用する場合、訓練データとしてサンプリングする単位データの数（サンプルサイズ）が大きいほど予測性能は高くなる。
図３は、サンプルサイズと予測性能の関係例を示すグラフである。
【００４６】
曲線２１は、モデルの予測性能とサンプルサイズとの間の関係を示す。サンプルサイズｓ1，ｓ2，ｓ3，ｓ4，ｓ5の間の大小関係は、ｓ1＜ｓ2＜ｓ3＜ｓ4＜ｓ5である。例えば、ｓ2はｓ1の２倍または４倍、ｓ3はｓ2の２倍または４倍、ｓ4はｓ3の２倍または４倍、ｓ5はｓ4の２倍または４倍である。
【００４７】
曲線２１が示すように、サンプルサイズがｓ2の場合の予測性能はｓ1の場合よりも高い傾向にある。サンプルサイズがｓ3の場合の予測性能はｓ2の場合よりも高い傾向にある。サンプルサイズがｓ4の場合の予測性能はｓ3の場合よりも高い傾向にある。サンプルサイズがｓ5の場合の予測性能はｓ4の場合よりも高い傾向にある。このように、サンプルサイズが大きくなるほど予測性能も高くなる傾向にある。ただし、予測性能が低いうちは、サンプルサイズの増加に応じて予測性能が大きく上昇する。一方で、予測性能には上限があり、予測性能が上限に近づくと、サンプルサイズの増加量に対する予測性能の上昇量の比は逓減する。
【００４８】
また、サンプルサイズが大きいほど、機械学習に要する学習時間も大きくなる傾向にある。このため、サンプルサイズを過度に大きくすると、学習時間の点で機械学習が非効率になる。図３の例の場合、サンプルサイズをｓ4とすると、上限に近い予測性能を短時間で達成できる。一方、サンプルサイズをｓ3とすると、予測性能が不十分であるおそれがある。また、サンプルサイズをｓ5とすると、予測性能は上限に近いものの、単位学習時間当たりの予測性能の上昇量が小さく、機械学習が非効率になる。
【００４９】
このようなサンプルサイズと予測性能との間の関係は、同じ機械学習アルゴリズムを使用する場合であっても、使用するデータの性質（データの種類）によって異なる。このため、予測性能の上限や上限に近い予測性能を達成できる最小のサンプルサイズを、機械学習を行う前に事前に推定することは難しい。そこで、プログレッシブサンプリング法という機械学習方法が提案されている。プログレッシブサンプリング法については、例えば、前述の非特許文献１（"Efficient Progressive Sampling"）に記載がある。
【００５０】
プログレッシブサンプリング法では、サンプルサイズを小さな値から始めて段階的に大きくしていき、予測性能が所定条件を満たすまで機械学習を繰り返す。例えば、機械学習装置１００は、サンプルサイズｓ1で機械学習を行い、学習されたモデルの予測性能を評価する。予測性能が不十分であれば、機械学習装置１００は、サンプルサイズｓ2で機械学習を行って予測性能を評価する。このとき、サンプルサイズｓ2の訓練データは、サンプルサイズｓ1の訓練データ（前に使用した訓練データ）の一部または全部を包含していてもよい。同様に、機械学習装置１００は、サンプルサイズｓ3で機械学習を行って予測性能を評価し、サンプルサイズｓ4で機械学習を行って予測性能を評価する。サンプルサイズｓ4で予測性能が十分と判断すると、機械学習装置１００は、機械学習を停止しサンプルサイズｓ4で学習したモデルを採用する。
【００５１】
上記のように、プログレッシブサンプリング法では、１つのサンプルサイズに対する処理（１つの学習ステップ）毎に、モデルの学習と当該モデルの予測性能の評価とを行う。各学習ステップ内の手順（バリデーション方法）としては、例えば、クロスバリデーションやランダムサブサンプリングバリデーションなどを用いることができる。
【００５２】
クロスバリデーションでは、機械学習装置１００は、サンプリングしたデータをＫ個（Ｋは２以上の整数）のブロックに分割し、このうちＫ−１個のブロックを訓練データとして使用して１個のブロックをテストデータとして使用する。機械学習装置１００は、テストデータとして使用するブロックを変えながらモデルの学習と予測性能の評価をＫ回繰り返す。１つの学習ステップの結果として、例えば、Ｋ個のモデルのうち最も予測性能の高いモデルと、Ｋ回の予測性能の平均値とが出力される。クロスバリデーションは、限定された量のデータを活用して予測性能の評価を可能とする。
【００５３】
ランダムサブサンプリングバリデーションでは、機械学習装置１００は、データの母集合から訓練データとテストデータをランダムにサンプリングし、訓練データを用いてモデルを学習し、テストデータを用いてモデルの予測性能を算出する。機械学習装置１００は、サンプリングとモデルの学習と予測性能の評価をＫ回繰り返す。
【００５４】
各サンプリングは、非復元抽出サンプリングである。すなわち、１回のサンプリングの中で、訓練データ内に同じ単位データは重複して含まれず、テストデータ内に同じ単位データは重複して含まれない。また、１回のサンプリングの中で、訓練データとテストデータに同じ単位データは重複して含まれない。ただし、Ｋ回のサンプリングの間で、同じ単位データが選択されることはあり得る。１つの学習ステップの結果として、例えば、Ｋ個のモデルのうち最も予測性能の高いモデルと、Ｋ回の予測性能の平均値とが出力される。
【００５５】
ところで、訓練データからモデルを学習する手順（機械学習アルゴリズム）には様々なものが存在する。機械学習装置１００は、複数の機械学習アルゴリズムを使用することができる。機械学習装置１００が使用できる機械学習アルゴリズムの数は、数十〜数百程度であってもよい。機械学習アルゴリズムの一例として、ロジスティック回帰分析、サポートベクタマシン、ランダムフォレストなどを挙げることができる。
【００５６】
ロジスティック回帰分析は、目的変数ｙの値と説明変数ｘ1，ｘ2，…，ｘkの値をＳ字曲線にフィッティングする回帰分析である。目的変数ｙおよび説明変数ｘ1，ｘ2，…，ｘkは、ｌｏｇ（ｙ／（１−ｙ））＝ａ1ｘ1＋ａ2ｘ2＋…＋ａkｘk＋ｂの関係を満たすと仮定される。ａ1，ａ2，…，ａk，ｂは係数であり、回帰分析によって決定される。
【００５７】
サポートベクタマシンは、空間に配置された単位データの集合を、２つのクラスに最も明確に分割するような境界面を算出する機械学習アルゴリズムである。境界面は、各クラスとの距離（マージン）が最大になるように算出される。
【００５８】
ランダムフォレストは、複数の単位データを適切に分類するためのモデルを生成する機械学習アルゴリズムである。ランダムフォレストでは、母集合から単位データをランダムにサンプリングする。説明変数の一部をランダムに選択し、選択した説明変数の値に応じてサンプリングした単位データを分類する。説明変数の選択と単位データの分類を繰り返すことで、複数の説明変数の値に基づく階層的な決定木を生成する。単位データのサンプリングと決定木の生成を繰り返すことで複数の決定木を取得し、それら複数の決定木を合成することで、単位データを分類するための最終的なモデルを生成する。
【００５９】
なお、機械学習アルゴリズムは、その挙動を制御するための１以上のハイパーパラメータをもつことがある。ハイパーパラメータは、モデルに含まれる係数（パラメータ）と異なり機械学習を通じて値が決定されるものではなく、機械学習アルゴリズムの実行前に値が与えられるものである。ハイパーパラメータの例として、ランダムフォレストにおける決定木の生成本数、回帰分析のフィッティング精度、モデルに含まれる多項式の次数などが挙げられる。ハイパーパラメータの値として、固定値が使用されることもあるし、ユーザから指定された値が使用されることもある。生成されるモデルの予測性能は、ハイパーパラメータの値にも依存する。機械学習アルゴリズムとサンプルサイズが同じでも、ハイパーパラメータの値が変わるとモデルの予測性能も変化し得る。
【００６０】
第２の実施の形態では、機械学習アルゴリズムの種類が同じでハイパーパラメータの値が異なる場合、異なる機械学習アルゴリズムを使用したものとして取り扱ってもよい。機械学習アルゴリズムの種類とハイパーパラメータの値の組み合わせを、コンフィギュレーションと言うこともある。すなわち、機械学習装置１００は、異なるコンフィギュレーションを異なる機械学習アルゴリズムとして取り扱ってもよい。
【００６１】
図４は、学習時間と予測性能の関係例を示すフラグである。
曲線２２〜２４は、著名なデータ集合（ＣｏｖｅｒＴｙｐｅ）を用いて測定された学習時間と予測性能の間の関係を示している。予測性能の指標として、ここでは正答率を用いている。曲線２２は、機械学習アルゴリズムとしてロジスティック回帰分析を用いた場合の学習時間と予測性能の間の関係を示す。曲線２３は、機械学習アルゴリズムとしてサポートベクタマシンを用いた場合の学習時間と予測性能の間の関係を示す。曲線２４は、機械学習アルゴリズムとしてランダムフォレストを用いた場合の学習時間と予測性能の間の関係を示す。なお、図４の横軸は、学習時間について対数目盛になっている。
【００６２】
曲線２２が示すように、ロジスティック回帰分析を使用した場合、サンプルサイズ＝８００における予測性能は約０．７１、学習時間は約０．２秒である。サンプルサイズ＝３２００における予測性能は約０．７５、学習時間は約０．５秒である。サンプルサイズ＝１２８００における予測性能は約０．７５５、学習時間は１．５秒である。サンプルサイズ＝５１２００における予測性能は約０．７６、学習時間は約６秒である。
【００６３】
曲線２３が示すように、サポートベクタマシンを使用した場合、サンプルサイズ＝８００における予測性能は約０．７０、学習時間は約０．２秒である。サンプルサイズ＝３２００における予測性能は約０．７７、学習時間は約２秒である。サンプルサイズ＝１２８００における予測性能は約０．７８５、学習時間は約２０秒である。
【００６４】
曲線２４が示すように、ランダムフォレストを使用した場合、サンプルサイズ＝８００における予測性能は約０．７４、学習時間は約２．５秒である。サンプルサイズ＝３２００における予測性能は約０．７９、学習時間は約１５秒である。サンプルサイズ＝１２８００における予測性能は約０．８２、学習時間は約２００秒である。
【００６５】
このように、上記のデータ集合に対しては、ロジスティック回帰分析は全体的に学習時間が短く予測性能が低い。サポートベクタマシンは、全体的にロジスティック回帰分析よりも学習時間が長く予測性能が高い。ランダムフォレストは、全体的にサポートベクタマシンよりも更に学習時間が長く予測性能が高い。ただし、図４の例では、サンプルサイズが小さい場合のサポートベクタマシンの予測性能は、ロジスティック回帰分析の予測性能よりも低くなっている。すなわち、プログレッシブサンプリング法における初期段階の予測性能の上昇カーブも、機械学習アルゴリズムによって異なる。
【００６６】
また、前述のように、個々の機械学習アルゴリズムの予測性能の上限や予測性能の上昇カーブは、使用するデータの性質にも依存する。そのため、複数の機械学習アルゴリズムのうち、予測性能の上限が最も高い機械学習アルゴリズムや上限に近い予測性能を最も短時間で達成できる機械学習アルゴリズムを事前に特定することは難しい。そこで、機械学習装置１００は、以下のように複数の機械学習アルゴリズムを使用して、予測性能の高いモデルを効率的に得られるようにする。
【００６７】
図５は、複数の機械学習アルゴリズムの使用例を示す図である。
ここでは説明を簡単にするため、機械学習アルゴリズムＡ，Ｂ，Ｃの３つの機械学習アルゴリズムが存在する場合を考える。機械学習アルゴリズムＡのみを使用してプログレッシブサンプリング法を行う場合、学習ステップ３１，３２，３３（Ａ１，Ａ２，Ａ３）が順に実行される。機械学習アルゴリズムＢのみを使用してプログレッシブサンプリング法を行う場合、学習ステップ３４，３５，３６（Ｂ１，Ｂ２，Ｂ３）が順に実行される。機械学習アルゴリズムＣのみを使用してプログレッシブサンプリング法を行う場合、学習ステップ３７，３８，３９（Ｃ１，Ｃ２，Ｃ３）が順に実行される。なお、ここでは、学習ステップ３３，３６，３９でそれぞれ停止条件が満たされるものと仮定する。
【００６８】
学習ステップ３１，３４，３７のサンプルサイズは同じである。例えば、学習ステップ３１，３４，３７の単位データ数はそれぞれ１万である。学習ステップ３２，３５，３８のサンプルサイズは同じであり、学習ステップ３１，３４，３７のサンプルサイズの２倍または４倍程度である。例えば、学習ステップ３２，３５，３８の単位データ数はそれぞれ４万である。学習ステップ３３，３６，３９のサンプルサイズは同じであり、学習ステップ３２，３５，３８のサンプルサイズの２倍または４倍程度である。例えば、学習ステップ３３，３６，３９の単位データ数はそれぞれ１６万である。
【００６９】
機械学習装置１００は、各機械学習アルゴリズムについて、サンプルサイズが１段階大きい学習ステップを実行した場合の予測性能の改善速度を推定し、改善速度が最大の機械学習アルゴリズムを選択して実行する。学習ステップを１つ進める毎に、改善速度の推定値が見直される。このため、最初のうちは複数の機械学習アルゴリズムの学習ステップが混在して実行され、徐々に使用する機械学習アルゴリズムが限定されていく。
【００７０】
改善速度の推定値は、性能改善量の推定値を実行時間の推定値で割ったものである。性能改善量の推定値は、次の学習ステップの予測性能の推定値と、複数の機械学習アルゴリズムを通じて現在までに達成された予測性能の最大値（達成予測性能と言うことがある）との差である。次の学習ステップの予測性能は、同じ機械学習アルゴリズムの過去の予測性能と次の学習ステップのサンプルサイズとに基づいて推定される。実行時間の推定値は、次の学習ステップに要する時間の推定値であり、同じ機械学習アルゴリズムの過去の実行時間と次の学習ステップのサンプルサイズとに基づいて推定される。
【００７１】
機械学習装置１００は、機械学習アルゴリズムＡの学習ステップ３１と、機械学習アルゴリズムＢの学習ステップ３４と、機械学習アルゴリズムＣの学習ステップ３７とを実行する。機械学習装置１００は、学習ステップ３１，３４，３７の実行結果に基づいて、機械学習アルゴリズムＡ，Ｂ，Ｃの改善速度をそれぞれ推定する。ここでは、機械学習アルゴリズムＡの改善速度＝２．５、機械学習アルゴリズムＢの改善速度＝２．０、機械学習アルゴリズムＣの改善速度＝１．０と推定されたとする。すると、機械学習装置１００は、改善速度が最大の機械学習アルゴリズムＡを選択し、学習ステップ３２を実行する。
【００７２】
学習ステップ３２が実行されると、機械学習装置１００は、機械学習アルゴリズムＡ，Ｂ，Ｃの改善速度を更新する。ここでは、機械学習アルゴリズムＡの改善速度＝０．７３、機械学習アルゴリズムＢの改善速度＝１．０、機械学習アルゴリズムＣの改善速度＝０．５と推定されたとする。学習ステップ３２によって達成予測性能が上昇したため、機械学習アルゴリズムＢ，Ｃの改善速度も低下している。機械学習装置１００は、改善速度が最大の機械学習アルゴリズムＢを選択し、学習ステップ３５を実行する。
【００７３】
学習ステップ３５が実行されると、機械学習装置１００は、機械学習アルゴリズムＡ，Ｂ，Ｃの改善速度を更新する。ここでは、機械学習アルゴリズムＡの改善速度＝０．０、機械学習アルゴリズムＢの改善速度＝０．８、機械学習アルゴリズムＣの改善速度＝０．０と推定されたとする。機械学習装置１００は、改善速度が最大の機械学習アルゴリズムＢを選択し、学習ステップ３６を実行する。学習ステップ３６によって予測性能が十分に上昇したと判定されると、機械学習は終了する。この場合、機械学習アルゴリズムＡの学習ステップ３３や機械学習アルゴリズムＣの学習ステップ３８，３９は実行されない。
【００７４】
ここで、次の学習ステップの予測性能を推定するにあたっては、統計誤差を考慮し、予測性能が今後上昇する可能性のある機械学習アルゴリズムを早期に切り捨ててしまうリスクを低減することが好ましい。例えば、機械学習装置１００は、回帰分析によって予測性能の期待値とその９５％予測区間を算出し、９５％予測区間の上限値（ＵＣＢ：Upper Confidence Bound）を、改善速度を算出する際の予測性能を推定値として使用することが考えられる。９５％予測区間は、測定される予測性能のばらつきを示すものであり、新たに測定される予測性能が９５％の確率でこの区間に収まると予想されることを示す。すなわち、統計上の期待値よりも統計誤差に応じた幅だけ大きい値を使用する。
【００７５】
ただし、ＵＣＢに代えて、機械学習装置１００は、推定される予測性能の分布を積分して、予測性能が達成予測性能を超える確率（ＰＩ：Probability of Improvement）を算出してもよい。また、機械学習装置１００は、推定される予測性能の分布を積分して、予測性能が達成予測性能を超える期待値（ＥＩ：Expected Improvement）を算出してもよい。
【００７６】
このように、予測性能の改善に寄与しない学習ステップは実行されず、全体の学習時間を短縮することができる。また、単位時間当たりの性能改善量が最大である機械学習アルゴリズムの学習ステップが優先的に実行される。このため、学習時間に制限があり機械学習を途中で打ち切った場合であっても、終了時刻までに得られたモデルが、制限時間内に得られる最善のモデルとなる。また、少しでも予測性能の改善に寄与する学習ステップは、実行順序が後になる可能性はあるものの実行される余地が残される。このため、予測性能の上限が高い機械学習アルゴリズムを切り捨ててしまうリスクを低減できる。
【００７７】
次に、予測性能の推定について説明する。
図６は、予測性能の分布例を示すグラフである。
あるサンプルサイズに対する予測性能の実測値は、機械学習アルゴリズムとデータの母集合の性質とから決まる期待値から乖離するリスクがある。すなわち、同じデータ母集合を使用しても、訓練データおよびテストデータの選択の偶然性などによって、予測性能の実測値にばらつきが生じる。予測性能のばらつき（分散や標準偏差など）は、サンプルサイズが小さいほど大きく、サンプルサイズが大きいほど小さくなる傾向にある。
【００７８】
グラフ４１は、サンプルサイズと予測性能との間の関係を示す。ここでは、同じ機械学習アルゴリズムおよび同じデータ母集合を用いて、サンプルサイズ１つ当たり５０回ずつ学習ステップを実行している。グラフ４１は、１つのサンプルサイズにつき５０個の予測性能の実測値をプロットしたものである。なお、グラフ４１では、予測性能の指標として、値が大きいほど予測性能が高いことを示す正答率を用いている。
【００７９】
この例では、グラフ４１に示すように、サンプルサイズが「１００」の場合の予測性能の実測値は、約０．５８〜０．６８であり広範囲に広がっている。サンプルサイズが「５００」の場合の予測性能の実測値は、約０．６９〜０．７５であり、サンプルサイズが「１００」の場合よりもその範囲が狭くなっている。以降、サンプルサイズが大きくなるに従い、予測性能の実測値の範囲は狭くなる。サンプルサイズが十分に大きくなると、予測性能の実測値は約０．７６に収束している。
【００８０】
上記のように、機械学習装置１００は、機械学習アルゴリズム毎に、次の学習ステップを実行した場合に達成される予測性能を推定する。予測性能の推定のため、機械学習装置１００は、それまでに取得した予測性能の実測値に基づいて予測性能曲線を推定する。しかし、予測性能の実測値（特に、小さなサンプルサイズにおける予測性能の実測値）は、期待値から乖離することがある。また、グラフ４１ではサンプルサイズ１つ当たり５０回ずつ学習ステップを実行しているが、時間的制約から、サンプルサイズ１つ当たりの学習ステップの実行回数を１回または少数回とすることが好ましい。よって、推定される予測性能曲線の精度が問題となる。
【００８１】
図７は、予測性能曲線の推定例を示すグラフである。
ここでは、複数のサンプルサイズのうち小さい方から６つについて学習ステップを実行して予測性能の実測値を取得し、その６つの予測性能の実測値を用いて予測性能曲線を推定している。そして、それ以降のサンプルサイズについて学習ステップを進め、取得された予測性能の実測値と推定した予測性能曲線とを対比している。
【００８２】
曲線４２は、予測性能の実測値を非線形関数に直接フィッティングして、非線形回帰分析により算出した予測性能曲線である。この例では、４番目と５番目の実測値が期待値よりも小さくなっている。このため、曲線４２は、４番目と５番目の実測値の影響を受けて予測性能の上限を小さく見積もったものとなっている。その結果、７番目以降のサンプルサイズについて、曲線４２が示す予測性能の推定値は実測値を大きく下回っている。
【００８３】
曲線４２ａは、曲線４２に対する予測区間の上限を示す。曲線４２ｂは、曲線４２に対する予測区間の下限を示す。予測区間は、同じ条件で実測値を繰り返し取得した場合に、取得した実測値の９５％が収まると予想される範囲である。予測区間は、回帰分析の過程で曲線４２と併せて算出される。曲線４２ａ，４２ｂが示すように、予測性能の実測値を非線形関数に直接フィッティングすると、予測区間が著しく広くなっている。そのため、予測性能が推定値から乖離するリスクを適切に評価することが難しい。
【００８４】
このように、単純な非線形回帰分析では、算出される予測性能曲線の推定精度が高くならないおそれがある。これは、サンプルサイズによって予測性能のばらつきが異なる、すなわち、等分散性が成立しないことが一因である。等分散性は、推定式に含まれる説明変数の何れの値に対しても、目的変数の実測値と推定値の差（残差）の分散が等しくなるという統計上の性質である。通常、回帰分析では等分散性が成立していることを仮定する。これに対し、グラフ４１に示したように、サンプルサイズと予測性能には等分散性が成立しない。そのため、サンプルサイズを説明変数とし予測性能を目的変数とする回帰分析において、予測性能曲線を高精度に推定することは容易でない。
【００８５】
そこで、機械学習装置１００は、以下のようにして予測性能曲線を推定する。
まず、バイアス・バリアンス分解の考え方について説明する。バイアス・バリアンス分解は、１つの機械学習アルゴリズムの良否や機械学習アルゴリズムに適用するハイパーパラメータの良否を評価するために用いられることがある。バイアス・バリアンス分解では、ロス（損失）とバイアスとバリアンスという３つの指標が用いられる。ロス＝バイアスの二乗＋バリアンスという関係が成立する。
【００８６】
ロスは、機械学習によって生成されるモデルが予測を外す度合いを示す指標である。ロスの種類には０−１ロスや二乗ロスなどがある。０−１ロスは、予測に成功すれば０を付与し予測に失敗すれば１を付与することで算出されるロスであり、その期待値は予測が失敗する確率を示す。予測が外れることが少ないほど０−１ロスの期待値は小さく、予測が外れることが多いほど０−１ロスの期待値は大きい。二乗ロスは、予測値と真の値との差（予測誤差）の二乗である。予測誤差が小さいほど二乗ロスは小さく、予測誤差が大きいほど二乗ロスは大きい。期待ロス（ロスの期待値）と予測性能とは相互に変換できる。予測性能が正答率（Accuracy）でありロスが０−１ロスである場合、期待ロス＝１−予測性能である。予測性能が平均二乗誤差（ＭＳＥ）でありロスが二乗ロスである場合、期待ロス＝ＭＳＥである。予測性能が二乗平均平方根誤差（ＲＭＳＥ）でありロスが二乗ロスである場合、期待ロス＝ＲＭＳＥの二乗である。
【００８７】
バイアスは、機械学習によって生成されるモデルの予測値が真の値に対して偏る程度を示す指標である。バイアスが小さいほど精度の高いモデルであると言うことができる。バリアンスは、機械学習によって生成されるモデルの予測値がばらつく程度を示す指標である。バリアンスが小さいほど精度の高いモデルであると言うことができる。ただし、バイアスとバリアンスの間にはトレードオフの関係があることが多い。
【００８８】
次数の小さい多項式など複雑性の低いモデル（表現力の低いモデルと言うこともできる）では、モデルの係数をどの様に調整しても、複数のサンプルケースの全てについて真の値に近い予測値を出力するようにすることは難しい。すなわち、複雑性の低いモデルを用いると複雑な事象を表現できない。よって、複雑性の低いモデルのバイアスは大きくなる傾向にある。この点、次数の大きい多項式など複雑性の高いモデル（表現力の高いモデルと言うこともできる）では、モデルの係数を適切に調整することで、複数のサンプルケースの全てについて真の値に近い予測値を出力することができる余地がある。よって、複雑性の高いモデルのバイアスは小さくなる傾向にある。
【００８９】
一方で、複雑性の高いモデルでは、訓練データとして使用するサンプルケースの特徴に過度に依存したモデルが生成されるという過学習が生じるリスクがある。過学習によって生成されたモデルは、他のサンプルケースについて適切な予測値を出力できないことが多い。例えば、ｎ次の多項式を用いると、ｎ＋１個のサンプルケースについて真の値と完全に一致する予測値を出力するモデル（残差が０のモデル）を生成できる。しかし、あるサンプルケースについて残差が０になるモデルは、通常は過度に複雑なモデルであり、他のサンプルケースについて予測誤差が著しく大きい予測値を出力してしまうリスクが高くなる。よって、複雑性の高いモデルのバリアンスは大きくなる傾向にある。この点、複雑性の低いモデルでは、予測誤差が著しく大きい予測値を出力してしまうリスクは低く、バリアンスは小さくなる傾向にある。このように、ロスの成分としてのバイアスとバリアンスは、モデルを生成する機械学習アルゴリズムの特性に依存している。
【００９０】
次に、ロスとバイアスとバリアンスの形式的定義を説明する。ここでは、二乗ロスをバイアスとバリアンスに分解する例について説明する。
同一のデータ母集合からＫ個の訓練データＤk（ｋ＝１，２，…，Ｋ）が抽出され、Ｋ個のモデルが生成されたとする。また、上記のデータ母集合からｎ個のテストケースを含むテストデータＴが抽出されたとする。ｉ番目のテストケースは、説明変数の値Ｘiと目的変数の真の値Ｙiとを含む（ｉ＝１，２，…，ｎ）。ｋ番目のモデルからは説明変数の値Ｘiに対して目的変数の予測値ｙikが算出される。
【００９１】
すると、ｋ番目のモデルとｉ番目のテストケースとの間で算出される予測誤差ｅikはｅik＝Ｙi−ｙikと定義され、そのロス（二乗ロス）はｅik2と定義される。ｉ番目のテストケースに対しては、バイアスＢiとバリアンスＶiとロスＬiが定義される。バイアスＢiはＢi＝ＥD［ｅik］と定義される。ＥD［］はＫ個の訓練データの間の平均値（期待値）を表す。バリアンスＶiはＶi＝ＶD［ｅik］と定義される。ＶD［］はＫ個の訓練データの間の分散を表す。ロスＬiはＬi＝ＥD［ｅik2］と定義される。前述のロスとバイアスとバリアンスの間の関係からＬi＝Ｂi2＋Ｖiが成立する。
【００９２】
テストデータＴ全体に対しては、期待バイアスＥＢ２と期待バリアンスＥＶと期待ロスＥＬが定義される。期待バイアスＥＢ２はＥＢ２＝Ｅx［Ｂi2］と定義される。Ｅx［］はｎ個のテストケースの間の平均値（期待値）を表す。期待バリアンスＥＶはＥＶ＝Ｅx［Ｖi］と定義される。期待ロスＥＬはＥＬ＝Ｅx［Ｌi］と定義される。前述のロスとバイアスとバリアンスの間の関係からＥＬ＝ＥＢ２＋ＥＶが成立する。
【００９３】
次に、予測性能曲線を推定するにあたって、各サンプルサイズで測定される予測性能に生じるばらつき度（分散度）を推定する方法を説明する。第２の実施の形態では、予測性能の分散の推定に上記のバイアス・バリアンス分解の考え方を応用する。
【００９４】
本出願の発明者らは、各サンプルサイズにおける予測性能の分散が、次の数式によって近似されることを発見した。ＶＬj＝Ｃ×（ＥＬj＋ＥＢ２）×（ＥＬj−ＥＢ２）。ＶＬjはサンプルサイズｓjにおける予測性能の分散を表す。Ｃは所定の定数である。第２の実施の形態では複数のサンプルサイズの間の分散ＶＬjの比を予測性能曲線の推定に利用するため、定数Ｃの値は不明であってもよい。例えば、Ｃ＝１と仮定してもよい。ＥＬjはサンプルサイズｓjにおける期待ロスを表す。ＥＢ２は機械学習アルゴリズムの期待バイアスを表す。以下、この数式の意味について説明を加える。
【００９５】
図８は、サンプルサイズとロスの関係例を示すグラフである。
曲線４３はサンプルサイズとロスの推定値との間の関係を示すロス曲線である。図３では縦軸が予測性能であるのに対し、図８では縦軸がロスに変換されている。前述のように予測性能とロスは、予測性能の指標とロスの指標に応じて相互に変換可能である。曲線４３は、サンプルサイズの増加に応じてロスが単調に減少し一定の下限ロスに漸近する非線形曲線である。サンプルサイズが小さいうちはロスの減少量が大きく、サンプルサイズが大きくなるとロスの減少量が小さくなっていく。
【００９６】
サンプルサイズｓjにおける曲線４３上の点のロス（ロス＝０から曲線４３上の点までの距離）は、サンプルサイズｓjの期待ロスＥＬjに相当する。曲線４３によって特定される下限ロスは、図３の曲線２１によって特定される予測性能上限に対応しており、０より大きい値である。例えば、予測性能上限をｃとおくと、予測性能が正答率（Accuracy）である場合、下限ロスは１−ｃとなる。予測性能が平均二乗誤差（ＭＳＥ）である場合、下限ロスはｃとなる。予測性能が二乗平均平方根誤差（ＲＭＳＥ）である場合、下限ロスはｃ2となる。下限ロスは、この機械学習アルゴリズムにとっての期待バイアスＥＢ２に相当する。サンプルサイズが十分大きくなると、機械学習に使用する訓練データの特徴がデータ母集合の特徴に一致し、期待バリアンスが０に近づくためである。
【００９７】
期待ロスＥＬjと期待バイアスＥＢ２の差は、サンプルサイズｓjにおけるギャップと言うことができる。ギャップは、サンプルサイズを大きくすることでその機械学習アルゴリズムがロスを低減できる余地を表している。ギャップは、図３の曲線２１上の点と予測性能上限との間の距離に対応し、サンプルサイズを大きくすることでその機械学習アルゴリズムが予測性能を改善できる余地を表しているとも言える。ギャップは、サンプルサイズｓjにおける期待バリアンスの影響を受ける。
【００９８】
ここで、上記の分散ＶＬjの近似式は、ＥＬj＋ＥＢ２という項とＥＬj−ＥＢ２という項を含む。これは、分散ＶＬjは、期待ロスと期待バイアスの和に比例する側面と、期待ロスと期待バイアスの差であるギャップに比例する側面を有していることを意味している。
【００９９】
期待バイアスＥＢ２が十分に小さい、すなわち、予測性能上限が十分に大きい機械学習アルゴリズムでは、サンプルサイズがある程度大きくなってもＥＬj＋ＥＢ２の値とＥＬj−ＥＢ２の値は共に変化する。また、この場合にはＥＬj＋ＥＢ２の値はＥＬj−ＥＢ２の値に近似する。よって、分散ＶＬjは全体としてギャップの二乗に比例する傾向にある。一方、期待バイアスＥＢ２が十分に大きい、すなわち、予測性能上限が十分に大きいとは言えない機械学習アルゴリズムでは、サンプルサイズがある程度大きくなるとＥＬj＋ＥＢ２の値はほとんど変化しなくなり、早期に定数化する。よって、分散ＶＬjは全体としてギャップに比例する傾向にある。このように、機械学習アルゴリズムによって、分散ＶＬjが概ねギャップの二乗に比例する場合とギャップに比例する場合とがある。
【０１００】
第２の実施の形態で使用するＶＬj＝Ｃ×（ＥＬj＋ＥＢ２）×（ＥＬj−ＥＢ２）という数式の導出過程の詳細については後述する。
次に、機械学習装置１００が行う処理について説明する。
【０１０１】
図９は、機械学習装置の機能例を示すブロック図である。
機械学習装置１００は、データ記憶部１２１、管理テーブル記憶部１２２、学習結果記憶部１２３、制限時間入力部１３１、ステップ実行部１３２、時間推定部１３３、性能改善量推定部１３４および学習制御部１３５を有する。データ記憶部１２１、管理テーブル記憶部１２２および学習結果記憶部１２３は、例えば、ＲＡＭ１０２またはＨＤＤ１０３に確保した記憶領域を用いて実装される。制限時間入力部１３１、ステップ実行部１３２、時間推定部１３３、性能改善量推定部１３４および学習制御部１３５は、例えば、ＣＰＵ１０１が実行するプログラムモジュールを用いて実装される。
【０１０２】
データ記憶部１２１は、機械学習に使用できるデータの集合を記憶する。データの集合は、それぞれが目的変数の値（結果）と１以上の説明変数の値（要因）とを含む単位データの集合である。データ記憶部１２１に記憶されたデータは、機械学習装置１００または他の情報処理装置が各種デバイスから収集したものでもよいし、機械学習装置１００または他の情報処理装置に対してユーザが入力したものでもよい。
【０１０３】
管理テーブル記憶部１２２は、機械学習の進行を管理する管理テーブルを記憶する。管理テーブルは、学習制御部１３５によって更新される。管理テーブルの詳細は後述する。
学習結果記憶部１２３は、機械学習の結果を記憶する。機械学習の結果には、目的変数と１以上の説明変数との間の関係を示すモデルが含まれる。例えば、各説明変数の重みを示す係数が機械学習によって決定される。また、機械学習の結果には、学習されたモデルの予測性能が含まれる。また、機械学習の結果には、モデルの学習に用いた機械学習アルゴリズムとサンプルサイズを示す情報が含まれる。機械学習アルゴリズムを示す情報には、使用されたハイパーパラメータが含まれることがある。
【０１０４】
制限時間入力部１３１は、機械学習の制限時間の情報を取得し、制限時間を学習制御部１３５に通知する。制限時間の情報は、入力デバイス１１２を通じてユーザから入力されてもよい。また、制限時間の情報は、ＲＡＭ１０２またはＨＤＤ１０３に記憶された設定ファイルから読み出すようにしてもよい。また、制限時間の情報は、ネットワーク１１４を介して他の情報処理装置から受信してもよい。
【０１０５】
ステップ実行部１３２は、複数の機械学習アルゴリズムそれぞれを実行する。ステップ実行部１３２は、学習制御部１３５から、機械学習アルゴリズムとサンプルサイズの指定を受け付ける。すると、ステップ実行部１３２は、データ記憶部１２１に記憶されたデータを用いて、指定された機械学習アルゴリズムおよび指定されたサンプルサイズについての学習ステップを実行する。すなわち、ステップ実行部１３２は、指定されたサンプルサイズに基づいて、データ記憶部１２１から訓練データとテストデータを抽出する。ステップ実行部１３２は、訓練データおよび指定された機械学習アルゴリズムを用いてモデルを学習し、テストデータを用いて予測性能を算出する。
【０１０６】
モデルの学習と予測性能の算出について、ステップ実行部１３２は、クロスバリデーションやランダムサブサンプリングバリデーションなどの各種のバリデーション方法を使用できる。使用するバリデーション方法は、ステップ実行部１３２に予め設定されてもよい。また、ステップ実行部１３２は、１つの学習ステップに要した実行時間を測定する。ステップ実行部１３２は、モデルと予測性能と実行時間を学習制御部１３５に出力する。
【０１０７】
時間推定部１３３は、ある機械学習アルゴリズムのある学習ステップの実行時間を推定する。時間推定部１３３は、学習制御部１３５から機械学習アルゴリズムとサンプルサイズの指定を受け付ける。すると、時間推定部１３３は、指定された機械学習アルゴリズムに属する実行済みの学習ステップの実行時間から、実行時間の推定式を生成する。時間推定部１３３は、指定されたサンプルサイズと生成した推定式から実行時間を推定する。時間推定部１３３は、推定した実行時間を学習制御部１３５に出力する。
【０１０８】
性能改善量推定部１３４は、ある機械学習アルゴリズムのある学習ステップの性能改善量を推定する。性能改善量推定部１３４は、学習制御部１３５から機械学習アルゴリズムとサンプルサイズの指定を受け付ける。すると、性能改善量推定部１３４は、指定された機械学習アルゴリズムに属する実行済みの学習ステップの予測性能から、予測性能の推定式を生成する。性能改善量推定部１３４は、指定されたサンプルサイズと生成した推定式から予測性能を推定する。このとき、性能改善量推定部１３４は、統計誤差を考慮して、ＵＣＢなど期待値よりも大きい予測性能を用いる。性能改善量推定部１３４は、現在の達成予測性能からの改善量を算出し、学習制御部１３５に出力する。
【０１０９】
学習制御部１３５は、複数の機械学習アルゴリズムを用いた機械学習を制御する。学習制御部１３５は、まず複数の機械学習アルゴリズムそれぞれについて少なくとも１つの学習ステップをステップ実行部１３２に実行させる。学習制御部１３５は、学習ステップが進むと、同じ機械学習アルゴリズムの次の学習ステップの実行時間を時間推定部１３３に推定させ、次の学習ステップの性能改善量を性能改善量推定部１３４に推定させる。学習制御部１３５は、性能改善量を実行時間で割った改善速度を算出する。
【０１１０】
そして、学習制御部１３５は、複数の機械学習アルゴリズムの中から改善速度が最大のものを選択し、選択した機械学習アルゴリズムの次の学習ステップをステップ実行部１３２に実行させる。学習制御部１３５は、改善速度の更新と機械学習アルゴリズムの選択とを、予測性能が所定の停止条件を満たすか学習時間が制限時間を超えるまで繰り返す。学習制御部１３５は、機械学習の停止までに得られたモデルのうち予測性能が最大のモデルを学習結果記憶部１２３に保存する。また、学習制御部１３５は、予測性能と機械学習アルゴリズムの情報とサンプルサイズの情報を学習結果記憶部１２３に保存する。
【０１１１】
図１０は、管理テーブルの例を示す図である。
管理テーブル１２２ａは、学習制御部１３５によって生成されて管理テーブル記憶部１２２に記憶される。管理テーブル１２２ａは、アルゴリズムＩＤ、サンプルサイズ、改善速度、予測性能および実行時間の項目を含む。
【０１１２】
アルゴリズムＩＤの項目には、機械学習アルゴリズムを識別する識別情報が登録される。以下では、ｉ番目（ｉ＝１，２，３，…）の機械学習アルゴリズムのアルゴリズムＩＤをａiと表記することがある。サンプルサイズの項目には、ある機械学習アルゴリズムについて次に実行すべき学習ステップのサンプルサイズが登録される。以下では、ｉ番目の機械学習アルゴリズムに対応するサンプルサイズをｋiと表記することがある。
【０１１３】
なお、ステップ番号とサンプルサイズとは１対１に対応する。以下では、ｊ番目の学習ステップのサンプルサイズをｓjと表記することがある。データ記憶部１２１に記憶されたデータ集合をＤとし、Ｄのサイズ（単位データの数）を｜Ｄ｜とすると、例えば、ｓ1＝｜Ｄ｜／２10，ｓj＝ｓ1×２j-1と決定される。
【０１１４】
改善速度の項目には、機械学習アルゴリズム毎に、次に実行すべき学習ステップの改善速度の推定値が登録される。改善速度の単位は、例えば、［秒-1］である。以下では、ｉ番目の機械学習アルゴリズムに対応する改善速度をｒiと表記することがある。予測性能の項目には、機械学習アルゴリズム毎に、既に実行された学習ステップの予測性能の実測値が列挙される。以下では、ｉ番目の機械学習アルゴリズムのｊ番目の学習ステップで算出された予測性能をｐi,jと表記することがある。実行時間の項目には、機械学習アルゴリズム毎に、既に実行された学習ステップの実行時間の実測値が列挙される。実行時間の単位は、例えば、［秒］である。以下では、ｉ番目の機械学習アルゴリズムのｊ番目の学習ステップの実行時間をＴi,jと表記することがある。
【０１１５】
図１１は、性能改善量推定部の機能例を示すブロック図である。
性能改善量推定部１３４は、推定式生成部１４１、重み設定部１４２、非線形回帰部１４３、分散推定部１４４、予測性能推定部１４５および推定値出力部１４６を有する。
【０１１６】
推定式生成部１４１は、ある機械学習アルゴリズムの実行履歴から、当該機械学習アルゴリズムについてサンプルサイズと予測性能の関係を示す予測性能曲線を推定する。予測性能曲線は、サンプルサイズの増加に応じて予測性能が一定の限界値に漸近する曲線であって、サンプルサイズが小さいときは予測性能の変化が大きくサンプルサイズが大きいときは予測性能の変化が小さくなる曲線である。予測性能の期待値は、ｙ＝ｃ−ｅｘｐ（ａ×ｌｏｇ（ｘ）＋ｂ）などの非線形式によって表される。ｘはサンプルサイズを示す説明変数、ｙは予測性能を示す目的変数、ａ，ｂ，ｃは係数である。
【０１１７】
非線形回帰分析によって係数ａ，ｂ，ｃが決定される。推定式生成部１４１は、予測性能曲線の推定に用いる実測データとして、実行済みの学習ステップのサンプルサイズｘjと測定された予測性能ｙjの組＜ｘj，ｙj＞の集合を取得する。推定式生成部１４１は、この実測データに基づいて係数ａ，ｂ，ｃを決定するよう重み設定部１４２に指示する。推定式生成部１４１は、決定された係数ａ，ｂ，ｃを含む上記の非線形式を、サンプルサイズから予測性能の期待値を推定する関数として生成する。また、推定式生成部１４１は、サンプルサイズから予測性能の分散を推定する関数を生成する。各サンプルサイズに対する分散は、上記の非線形回帰分析を通じて、各サンプルサイズに対する期待値と合わせて統計処理によって特定される。推定式生成部１４１は、予測性能曲線に関する期待値の関数と分散の関数を予測性能推定部１４５に出力する。
【０１１８】
重み設定部１４２は、非線形回帰分析に用いる実績データの中の各サンプルサイズｘjに対して重みｗjを設定する。重み設定部１４２は最初に、重みｗjをｗj＝１に初期化する。重み設定部１４２は、設定した重みｗjを非線形回帰部１４３に通知し、非線形回帰分析によって算出された係数ａ，ｂ，ｃを非線形回帰部１４３から取得する。重み設定部１４２は、係数ａ，ｂ，ｃが十分に収束したか判断する。十分に収束したとは言えない場合、重み設定部１４２は、係数ｃを分散推定部１４４に通知し、係数ｃに依存する各サンプルサイズｘjの分散ＶＬjを分散推定部１４４から取得する。重み設定部１４２は、分散ＶＬjを用いて重みｗjを更新する。通常、分散ＶＬjと重みｗjは反比例し、ＶＬjが大きいほどｗjは小さくなる。例えば、重み設定部１４２はｗj＝１／ＶＬjとする。重み設定部１４２は、更新した重みｗjを非線形回帰部１４３に通知する。このように、係数ａ，ｂ，ｃが十分に収束するまで重みｗjの更新と係数ｃの更新が繰り返される。
【０１１９】
非線形回帰部１４３は、重み設定部１４２から通知された重みｗjを用いて、実績データの＜ｘj，ｙj＞を上記の非線形式にフィッティングして係数ａ，ｂ，ｃを決定する。非線形回帰部１４３は、決定した係数ａ，ｂ，ｃを重み設定部１４２に通知する。非線形回帰部１４３が行う非線形回帰分析は重み付き回帰分析である。重みが小さいサンプルサイズについては相対的に大きな残差が許容され、重みが大きいサンプルサイズについては相対的に残差の制限が強くなる。例えば、各サンプルサイズの重みと残差平方の積を合計した評価値が最小になるように係数ａ，ｂ，ｃが決定される。よって、重みが大きいサンプルサイズにおける残差を小さくすることが優先される。通常、サンプルサイズが大きいほど重みが大きいため、大きなサンプルサイズの残差を小さくすることが優先される。
【０１２０】
分散推定部１４４は、重み設定部１４２から通知された係数ｃを用いて、実績データの予測性能ｙjに内包される誤差に関して各サンプルサイズｘjの分散ＶＬjを推定する。分散ＶＬjは前述のように、期待バイアスＥＢ２とサンプルサイズｘjにおける期待ロスＥＬjとから算出される。具体的には、ＶＬj＝Ｃ×（ＥＬj＋ＥＢ２）×（ＥＬj−ＥＢ２）である。ただし、複数のサンプルサイズの間のＶＬjの比のみが重要であり各ＶＬjの大きさ自体は重要でないことから、分散推定部１４４は計算を簡単にするため定数Ｃ＝１とみなす。期待バイアスＥＢ２は係数ｃから算出される。期待ロスＥＬjは予測性能ｙjから算出される。分散推定部１４４は、推定した分散ＶＬjを重み設定部１４２に通知する。
【０１２１】
予測性能推定部１４５は、推定式生成部１４１から通知された関数と学習制御部１３５から指定されたサンプルサイズｋiとを用いて、サンプルサイズｋiにおける予測性能の期待値と分散を推定する。すなわち、期待値を出力する関数の引数にｋiを代入し、分散を出力する関数の引数にｋiを代入することで、期待値および分散を算出する。予測性能推定部１４５は、推定した期待値と分散を推定値出力部１４６に通知する。
【０１２２】
推定値出力部１４６は、予測性能推定部１４５から通知された予測性能の期待値と分散を用いて性能改善量ｇi,j+1を算出する。例えば、推定値出力部１４６は、予測性能の期待値と分散から、予測性能の９５％予測区間の推定上限値Ｕｐを算出する。推定値出力部１４６は、推定上限値Ｕｐから現在の達成予測性能Ｐを引いて性能改善量ｇi,j+1を算出する。ただし、Ｕｐ−Ｐ＜０である場合にはｇi,j+1＝０とする。推定値出力部１４６は、算出した性能改善量ｇi,j+1を学習制御部１３５に通知する。
【０１２３】
図１２は、機械学習の手順例を示すフローチャートである。
（Ｓ１０）学習制御部１３５は、データ記憶部１２１を参照して、プログレッシブサンプリング法における学習ステップのサンプルサイズｓ1，ｓ2，ｓ3，…を決定する。例えば、学習制御部１３５は、データ記憶部１２１に記憶されたデータ集合Ｄのサイズに基づいて、ｓ1＝｜Ｄ｜／２10，ｓj＝ｓ1×２j-1と決定する。
【０１２４】
（Ｓ１１）学習制御部１３５は、管理テーブル１２２ａの各機械学習アルゴリズムのサンプルサイズを最小値ｓ1に初期化する。また、学習制御部１３５は、各機械学習アルゴリズムの改善速度を、改善速度が取り得る最大値に初期化する。また、学習制御部１３５は、達成予測性能Ｐを、達成予測性能Ｐが取り得る最低値（例えば、０）に初期化する。
【０１２５】
（Ｓ１２）学習制御部１３５は、管理テーブル１２２ａの中から、改善速度が最大の機械学習アルゴリズムを選択する。ここで選択した機械学習アルゴリズムをａiとする。
（Ｓ１３）学習制御部１３５は、機械学習アルゴリズムａiの改善速度ｒiが、閾値Ｔｒ未満であるか判断する。閾値Ｔｒは、予め学習制御部１３５に設定されていてもよい。例えば、閾値Ｔｒ＝０．００１／３６００とする。改善速度ｒiが閾値Ｔｒ未満である場合はステップＳ２８に処理が進み、それ以外の場合はステップＳ１４に処理が進む。
【０１２６】
（Ｓ１４）学習制御部１３５は、管理テーブル１２２ａから、機械学習アルゴリズムａiに対応する次のサンプルサイズｋiを検索する。
（Ｓ１５）学習制御部１３５は、ステップ実行部１３２に対して機械学習アルゴリズムａiとサンプルサイズｋiを指定する。ステップ実行部１３２は、機械学習アルゴリズムａiとサンプルサイズｋiとに基づく学習ステップを実行する。ステップ実行部１３２の処理の詳細は後述する。
【０１２７】
（Ｓ１６）学習制御部１３５は、ステップ実行部１３２から、学習されたモデルと当該モデルの予測性能ｐi,jと実行時間Ｔi,jとを取得する。
（Ｓ１７）学習制御部１３５は、ステップＳ１６で取得した予測性能ｐi,jと、達成予測性能Ｐ（現在までに達成された最大の予測性能）とを比較し、前者が後者より大きいか判断する。予測性能ｐi,jが達成予測性能Ｐよりも大きい場合はステップＳ１８に処理が進み、それ以外の場合はステップＳ１９に処理が進む。
【０１２８】
（Ｓ１８）学習制御部１３５は、達成予測性能Ｐを予測性能ｐi,jに更新する。また、学習制御部１３５は、達成予測性能Ｐと対応付けて、その予測性能が得られた機械学習アルゴリズムａiとサンプルサイズｋiとを記憶しておく。
【０１２９】
（Ｓ１９）学習制御部１３５は、管理テーブル１２２ａに記憶されたサンプルサイズｋiを、１段階大きなサンプルサイズ（例えば、現在のサンプルサイズの２倍）に増加させる。また、学習制御部１３５は、合計時間ｔsumを０に初期化する。
【０１３０】
図１３は、機械学習の手順例を示すフローチャート（続き）である。
（Ｓ２０）学習制御部１３５は、機械学習アルゴリズムａiの更新後のサンプルサイズｋiとデータ記憶部１２１に記憶されたデータ集合Ｄのサイズとを比較し、前者が後者より大きいか判断する。サンプルサイズｋiがデータ集合Ｄのサイズよりも大きい場合はステップＳ２１に処理が進み、それ以外の場合はステップＳ２２に処理が進む。
【０１３１】
（Ｓ２１）学習制御部１３５は、管理テーブル１２２ａに記憶された改善速度のうち、機械学習アルゴリズムａiに対応する改善速度ｒiを０に更新する。これにより、機械学習アルゴリズムａiは実行されなくなる。そして、前述のステップＳ１２に処理が進む。
【０１３２】
（Ｓ２２）学習制御部１３５は、時間推定部１３３に対して機械学習アルゴリズムａiとサンプルサイズｋiを指定する。時間推定部１３３は、機械学習アルゴリズムａiについてサンプルサイズｋiに基づく次の学習ステップを実行した場合の実行時間ｔi,j+1を推定する。時間推定部１３３の処理の詳細は後述する。
【０１３３】
（Ｓ２３）学習制御部１３５は、性能改善量推定部１３４に対して機械学習アルゴリズムａiとサンプルサイズｋiを指定する。性能改善量推定部１３４は、機械学習アルゴリズムａiについてサンプルサイズｋiに基づく次の学習ステップを実行した場合の性能改善量ｇi,j+1を推定する。性能改善量推定部１３４の処理の詳細は後述する。
【０１３４】
（Ｓ２４）学習制御部１３５は、時間推定部１３３から取得した実行時間ｔi,j+1に基づいて、合計時間ｔsumをｔsum＋ｔi,j+1に更新する。また、学習制御部１３５は、更新した合計時間ｔsumと性能改善量推定部１３４から取得した性能改善量ｇi,j+1とに基づいて、改善速度ｒi＝ｇi,j+1／ｔsumを算出する。学習制御部１３５は、管理テーブル１２２ａに記憶された改善速度ｒiを上記の値に更新する。
【０１３５】
（Ｓ２５）学習制御部１３５は、改善速度ｒiが閾値Ｔｒ未満であるか判断する。改善速度ｒiが閾値Ｔｒ未満の場合はステップＳ２６に処理が進み、改善速度ｒiが閾値Ｔｒ以上の場合はステップＳ２７に処理が進む。
【０１３６】
（Ｓ２６）学習制御部１３５は、サンプルサイズｋiを１段階大きなサンプルサイズに増加させる。そして、ステップＳ２０に処理が進む。
（Ｓ２７）学習制御部１３５は、機械学習を開始してからの経過時間が、制限時間入力部１３１から指定された制限時間を超えたか判断する。経過時間が制限時間を超えた場合はステップＳ２８に処理が進み、それ以外の場合はステップＳ１２に処理が進む。
【０１３７】
（Ｓ２８）学習制御部１３５は、達成予測性能Ｐとその達成予測性能Ｐが得られたモデルとを学習結果記憶部１２３に保存する。また、学習制御部１３５は、達成予測性能Ｐに対応付けられた機械学習アルゴリズムのアルゴリズムＩＤと達成予測性能Ｐに対応付けられたサンプルサイズとを、学習結果記憶部１２３に保存する。このとき、当該機械学習アルゴリズムに対して設定されたハイパーパラメータを更に保存してもよい。
【０１３８】
図１４は、ステップ実行の手順例を示すフローチャートである。
ここでは、バリデーション方法として、データ集合Ｄのサイズに応じて、ランダムサブサンプリングバリデーションまたはクロスバリデーションを実行する場合を考える。ただし、ステップ実行部１３２は、他のバリデーション方法を用いてもよい。
【０１３９】
（Ｓ３０）ステップ実行部１３２は、学習制御部１３５から指定された機械学習アルゴリズムａiとサンプルサイズｋi＝ｓj+1とを特定する。また、ステップ実行部１３２は、データ記憶部１２１に記憶されているデータ集合Ｄを特定する。
【０１４０】
（Ｓ３１）ステップ実行部１３２は、サンプルサイズｋiが、データ集合Ｄのサイズの２／３よりも大きいか判断する。サンプルサイズｋiが２／３×｜Ｄ｜よりも大きい場合、ステップ実行部１３２は、データ量が不足しているためクロスバリデーションを選択する。そして、ステップＳ３８に処理が進む。サンプルサイズｋiが２／３×｜Ｄ｜以下である場合、ステップ実行部１３２は、データ量が十分あるためランダムサブサンプリングバリデーションを選択する。そして、ステップＳ３２に処理が進む。
【０１４１】
（Ｓ３２）ステップ実行部１３２は、データ集合Ｄからサンプルサイズｋiの訓練データＤtをランダムに抽出する。訓練データの抽出は、非復元抽出サンプリングとして行う。よって、訓練データには互いに異なるｋi個の単位データが含まれる。
【０１４２】
（Ｓ３３）ステップ実行部１３２は、データ集合Ｄのうち訓練データＤtを除いた部分から、サイズｋi／２のテストデータＤsをランダムに抽出する。テストデータの抽出は、非復元抽出サンプリングとして行う。よって、テストデータには、訓練データＤtと異なりかつ互いに異なるｋi／２個の単位データが含まれる。なお、ここでは訓練データＤtのサイズとテストデータＤsのサイズの比を２：１としたが、比を変更してもよい。
【０１４３】
（Ｓ３４）ステップ実行部１３２は、機械学習アルゴリズムａiとデータ集合Ｄから抽出した訓練データＤtとを用いてモデルｍを学習する。
（Ｓ３５）ステップ実行部１３２は、学習したモデルｍとデータ集合Ｄから抽出したテストデータＤsとを用いて、モデルｍの予測性能ｐを算出する。予測性能ｐを表す指標として、正答率、適合率、ＭＳＥ、ＲＭＳＥなど任意の指標を用いることができる。予測性能ｐを表す指標が、予めステップ実行部１３２に設定されてもよい。
【０１４４】
（Ｓ３６）ステップ実行部１３２は、上記ステップＳ３２〜Ｓ３５の繰り返し回数と閾値Ｋとを比較し、前者が後者未満であるか判断する。閾値Ｋは、予めステップ実行部１３２に設定されていてもよい。例えば、閾値Ｋ＝１０とする。繰り返し回数が閾値Ｋ未満の場合はステップＳ３２に処理が進み、それ以外の場合はステップＳ３７に処理が進む。
【０１４５】
（Ｓ３７）ステップ実行部１３２は、ステップＳ３５で算出されたＫ個の予測性能ｐの平均値を算出し、予測性能ｐi,jとして出力する。また、ステップ実行部１３２は、ステップＳ３０が開始されてからステップＳ３２〜Ｓ３６の繰り返しが終了するまでの実行時間Ｔi,jを算出して出力する。また、ステップ実行部１３２は、ステップＳ３４で学習されたＫ個のモデルのうち予測性能ｐが最大のモデルを出力する。そして、ランダムサブサンプリングバリデーションによる１つの学習ステップが終了する。
【０１４６】
（Ｓ３８）ステップ実行部１３２は、上記のランダムサブサンプリングバリデーションに代えて、前述のクロスバリデーションを実行する。例えば、ステップ実行部１３２は、データ集合Ｄからサンプルサイズｋiのサンプルデータをランダムに抽出し、抽出したサンプルデータをＫ個のブロックに均等に分割する。ステップ実行部１３２は、Ｋ−１個のブロックを訓練データとして使用し１個のブロックをテストデータとして使用することを、テストデータのブロックを変えながらＫ回繰り返す。ステップ実行部１３２は、Ｋ個の予測性能の平均値と、実行時間と、予測性能が最大のモデルとを出力する。
【０１４７】
図１５は、時間推定の手順例を示すフローチャートである。
（Ｓ４０）時間推定部１３３は、学習制御部１３５から指定された機械学習アルゴリズムａiとサンプルサイズｋi＝ｓj+1とを特定する。
【０１４８】
（Ｓ４１）時間推定部１３３は、機械学習アルゴリズムａiについてサンプルサイズが異なる２以上の学習ステップを実行済みか判断する。２以上の学習ステップを実行済みである場合はステップＳ４２に処理が進み、実行済みの学習ステップが１つのみである場合はステップＳ４５に処理が進む。
【０１４９】
（Ｓ４２）時間推定部１３３は、管理テーブル１２２ａから機械学習アルゴリズムａiに対応する実行時間Ｔi,1，Ｔi,2を検索する。
（Ｓ４３）時間推定部１３３は、サンプルサイズｓ1，ｓ2と実行時間Ｔi,1，Ｔi,2を用いて、サンプルサイズｓから実行時間ｔを推定する推定式ｔ＝α×ｓ＋βの係数α，βを決定する。係数α，βは、Ｔi,1をｔに代入しｓ1をｓに代入した式と、Ｔi,2をｔに代入しｓ2をｓに代入した式とを含む連立方程式を解くことで決定できる。ただし、機械学習アルゴリズムａiについて３以上の学習ステップを実行済みである場合、時間推定部１３３は、それら学習ステップの実行時間から回帰分析によって係数α，βを決定してもよい。ここでは、サンプルサイズと実行時間とが一次式で説明できると仮定している。
【０１５０】
（Ｓ４４）時間推定部１３３は、上記の実行時間の推定式とサンプルサイズｋiを用いて（ｋiを推定式のｓに代入して）、次の学習ステップの実行時間ｔi,j+1を推定する。時間推定部１３３は、推定した実行時間ｔi,j+1を出力する。
【０１５１】
（Ｓ４５）時間推定部１３３は、管理テーブル１２２ａから機械学習アルゴリズムａiに対応する実行時間Ｔi,1を検索する。
（Ｓ４６）時間推定部１３３は、サンプルサイズｓ1，ｓ2と実行時間Ｔi,1を用いて、２番目の学習ステップの実行時間ｔi,2をｓ2／ｓ1×Ｔi,1と推定する。時間推定部１３３は、推定した実行時間ｔi,2を出力する。
【０１５２】
図１６は、性能改善量推定の手順例を示すフローチャートである。
（Ｓ５０）性能改善量推定部１３４の推定式生成部１４１は、学習制御部１３５から指定された機械学習アルゴリズムａiとサンプルサイズｋi＝ｓj+1とを特定する。
【０１５３】
（Ｓ５１）推定式生成部１４１は、管理テーブル１２２ａから機械学習アルゴリズムａiに対応する全ての予測性能ｐi,1，ｐi,2，…を検索する。
（Ｓ５２）推定式生成部１４１は、サンプルサイズｓ1，ｓ2，…と実測値としての予測性能ｐi,1，ｐi,2，…とを用いて、サンプルサイズから予測性能を推定する予測性能曲線を算出する。算出される予測性能曲線の情報は、例えば、サンプルサイズから予測性能の期待値を求める関数と、サンプルサイズから予測性能の分散を求める関数とを含む。予測性能曲線算出の詳細は後述する。
【０１５４】
（Ｓ５３）予測性能推定部１４５は、ステップＳ５２で算出された予測性能曲線とサンプルサイズｋiを用いて（例えば、ｋi＝ｓj+1を関数に代入して）、ｋiに対応する予測性能の期待値を算出する。同様に、予測性能推定部１４５は、予測性能曲線とサンプルサイズｋiを用いて、ｋiに対応する予測性能の分散を算出する。
【０１５５】
（Ｓ５４）推定値出力部１４６は、ステップＳ５３で算出された期待値と分散に基づいて、サンプルサイズｋiにおける９５％予測区間の推定上限値Ｕｐを算出する。
（Ｓ５５）推定値出力部１４６は、現在の達成予測性能Ｐと推定上限値Ｕｐを比較して性能改善量ｇi,j+1を算出し、算出した性能改善量ｇi,j+1を出力する。性能改善量ｇi,j+1は、Ｕｐ＞ＰであればＵｐ−Ｐであり、Ｕｐ≦Ｐであれば０である。
【０１５６】
図１７は、予測性能曲線算出の手順例を示すフローチャートである。
この予測性能曲線算出は、上記のステップＳ５２で実行される。
（Ｓ６０）推定式生成部１４１は、予測性能の実測データとして、サンプルサイズｘjと予測性能ｙjの組である＜ｘj，ｙj＞の集合を取得する。この実測データは、予測性能曲線を学習するための訓練データとしての意味をもつ。
【０１５７】
（Ｓ６１）重み設定部１４２は、各ｘjに対する重みｗjをｗj＝１に初期化する。
（Ｓ６２）非線形回帰部１４３は、ステップＳ６０で取得された＜ｘj，ｙj＞の集合を用いて、非線形回帰分析により非線形式ｙ＝ｃ−ｅｘｐ（ａ×ｌｏｇ（ｘ）＋ｂ）の係数ａ，ｂ，ｃの値を算出する。サンプルサイズｘが説明変数であり、予測性能ｙが目的変数である。この非線形回帰分析は、残差の評価に当たって各ｘjに対する重みｗjを考慮する重み付き回帰分析である。重みが小さいサンプルサイズについては相対的に大きな残差が許容され、重みが大きいサンプルサイズについては相対的に残差の制限が強くなる。複数のサンプルサイズの間で異なる重みを設定できる。これにより、予測性能の等分散性が成立しない（異分散性が成立する）ことによる回帰分析の精度低下をカバーすることができる。なお、上記の非線形式は推定式の一例であり、ｘが増加したときにｙが一定の限界値に漸近する曲線を示すような他の非線形式を用いてもよい。このような非線形回帰分析は、例えば、統計パッケージソフトウェアを用いて実行できる。
【０１５８】
（Ｓ６３）重み設定部１４２は、ステップＳ６２で算出された今回の係数ａ，ｂ，ｃと前回の係数ａ，ｂ，ｃとを比較し、係数ａ，ｂ，ｃが所定の収束条件を満たすか判断する。例えば、重み設定部１４２は、今回の係数ａ，ｂ，ｃと前回の係数ａ，ｂ，ｃとが一致したとき、または、両者の差が閾値未満であるとき、収束条件を満たすと判断する。１回目に算出された係数ａ，ｂ，ｃは、まだ収束条件を満たしていないと判断される。収束条件を満たさない場合はステップＳ６４に処理が進み、収束条件を満たす場合（係数ａ，ｂ，ｃが十分に収束した場合）はステップＳ６８に処理が進む。
【０１５９】
（Ｓ６４）分散推定部１４４は、ステップＳ６２で算出された係数ｃを期待バイアスＥＢ２に変換する。係数ｃは機械学習アルゴリズムａiを用いた場合の予測性能向上の限界を表しており、期待バイアスＥＢ２と対応している。係数ｃと期待バイアスＥＢ２との間の関係は、予測性能ｙの指標に依存する。予測性能ｙが正答率（Accuracy）である場合、ＥＢ２＝１−ｃである。予測性能ｙが平均二乗誤差（ＭＳＥ）である場合、ＥＢ２＝ｃである。予測性能ｙが二乗平均平方根誤差（ＲＭＳＥ）である場合、ＥＢ２＝ｃ2である。
【０１６０】
ただし、実測データに含まれる予測性能ｙjの数が少ないうちは、非線形回帰分析によって算出される係数ｃの信頼性が著しく低くなるおそれがある。そこで、分散推定部１４４は、以下のようにして期待バイアスＥＢ２を算出してもよい。
【０１６１】
サンプルサイズｘjの学習ステップが実行された際には、抽出された訓練データに対するロスの期待値（訓練ロス）を直接的に求めることができる。この訓練ロスは一般にバイアスより大きくはならず、バイアスの下限としての意味をもつ。そこで、分散推定部１４４は、各サンプルサイズｘjに対して測定された訓練ロスを取得する。分散推定部１４４は、上記のように係数ｃから変換された値および複数の訓練ロスを相互に比較し、係数ｃから変換された値および複数の訓練ロスの中の最大値を期待バイアスＥＢ２する。この場合、ステップ実行部１３２は１つの学習ステップを実行する毎に更に訓練ロスを出力し、管理テーブル１２２ａに訓練ロスが記録されることになる。
【０１６２】
（Ｓ６５）分散推定部１４４は、各サンプルサイズｘjに対する予測性能ｙjを期待ロスＥＬjに変換する。測定された予測性能ｙjと期待ロスＥＬjとの間の関係は、予測性能ｙの指標に依存する。予測性能ｙが正答率（Accuracy）である場合、ＥＬj＝１−ｙjである。予測性能ｙが平均二乗誤差（ＭＳＥ）である場合、ＥＬj＝ｙjである。予測性能ｙが二乗平均平方根誤差（ＲＭＳＥ）である場合、ＥＬj＝ｙj2である。
【０１６３】
（Ｓ６６）分散推定部１４４は、ステップＳ６４の期待バイアスＥＢ２とステップＳ６５の期待ロスＥＬjとを用いて、各サンプルサイズｘjに対する予測性能の分散ＶＬjを算出する。ＶＬj＝（ＥＬj＋ＥＢ２）×（ＥＬj−ＥＢ２）である。
【０１６４】
（Ｓ６７）重み設定部１４２は、各ｘjに対する重みｗjをｗj＝１／ＶＬjに更新する。そして、処理がステップＳ６２に戻り、再び非線形回帰分析が行われる。
（Ｓ６８）推定式生成部１４１は、最後にステップＳ６２で算出された係数ａ，ｂ，ｃを用いた推定式（ステップＳ６２の非線形式）を、サンプルサイズから予測性能の期待値を推定する関数として生成する。また、推定式生成部１４１は、サンプルサイズから予測性能の分散を推定する関数を生成する。各サンプルサイズにおける予測性能の分散は、ステップＳ６２の非線形回帰分析を通じて非線形回帰部１４３によって算出される。例えば、統計パッケージソフトウェアによって期待値と合わせて分散が推定される。推定式生成部１４１は、期待値を求める関数と分散を求める関数を出力する。
【０１６５】
次に、第２の実施の形態における予測性能の分散の推定精度について説明する。
図１８は、予測性能の分布の第１の推定例を示すグラフである。
このグラフは、前述の非特許文献２（"Prediction of Learning Curves in Machine Translation"）に従って単純な非線形回帰分析によって推定した予測性能曲線を示している。また、このグラフは、複数のサンプルサイズそれぞれに対する予測性能の実測値を示している。各サンプルサイズについて５０個の予測性能の実測値がプロットされている。予測性能の指標として、値が大きいほど予測性能が高いことを示す正答率を用いている。
【０１６６】
曲線４４は、幾つかの予測性能の実測値から推定された、サンプルサイズと予測性能の期待値との間の関係を示す予測性能曲線である。直線４４ａは、曲線４４から推定される予測性能上限を示している。曲線４４ｂは、回帰分析を通じて算出された９５％信頼区間の上限を示しており、測定される予測性能の上方向への分布を推定したものである。曲線４４ｃは、回帰分析を通じて算出された９５％信頼区間の下限を示しており、測定される予測性能の下方向への分布を推定したものである。
【０１６７】
曲線４４ｂ，４４ｃによれば、推定した９５％信頼区間はサンプルサイズが小さいほど狭くなりサンプルサイズが大きいほど広くなっている。これは、サンプルサイズが小さいほど予測性能の分散が大きくサンプルサイズが大きいほど予測性能の分散が小さいという、実際のプロットの分布と矛盾している。よって、予測性能曲線の推定にあたって、サンプルサイズ毎の予測性能の分散が適切に評価されているとは言えない。
【０１６８】
図１９は、予測性能の分布の第２の推定例を示すグラフである。
このグラフは、第２の実施の形態とは別の方法によって推定した予測性能曲線を示している。別の方法とは、各サンプルサイズにおける予測性能の分散が、当該サンプルサイズにおける予測性能の期待値と予測性能上限との間の差（ギャップ）に比例すると仮定して、予測性能曲線を推定する方法である。この別の方法は、第２の実施の形態よりも簡易的な推定方法であると言うこともできる。複数のサンプルサイズそれぞれに対する予測性能の実測値のプロットは、図１８と同じである。
【０１６９】
曲線４５は、サンプルサイズと予測性能の期待値との間の関係を示す予測性能曲線である。直線４５ａは、曲線４５から推定される予測性能上限を示している。曲線４５ｂは、回帰分析を通じて算出された９５％信頼区間の上限を示している。曲線４５ｃは、回帰分析を通じて算出された９５％信頼区間の下限を示している。
【０１７０】
曲線４５ｂ，４５ｃによれば、推定した９５％信頼区間はサンプルサイズが小さいほど広くなりサンプルサイズが大きいほど狭くなっている。この傾向は、予測性能の実測値の分布と適合している。しかし、推定した９５％信頼区間の広さは、必ずしも実際の予測性能の分散と一致していない。小さいサンプルサイズでは、推定した９５％信頼区間の広さは実際の分散よりも過大となっており、大きいサンプルサイズでは、推定した９５％信頼区間の広さは実際の分散よりも過小となっている。よって、予測性能曲線の推定にあたって、サンプルサイズ毎の予測性能の分散が適切に評価されているとは言えない。
【０１７１】
図２０は、予測性能の分布の第３の推定例を示すグラフである。
このグラフは、前述の第２の実施の形態の方法によって推定した予測性能曲線を示している。複数のサンプルサイズそれぞれに対する予測性能の実測値のプロットは、図１８，１９と同じである。曲線４６は、サンプルサイズと予測性能の期待値との間の関係を示す予測性能曲線である。直線４６ａは、曲線４６から推定される予測性能上限を示している。曲線４６ｂは、回帰分析を通じて算出された９５％信頼区間の上限を示している。曲線４６ｃは、回帰分析を通じて算出された９５％信頼区間の下限を示している。
【０１７２】
曲線４６ｂ，４６ｃによれば、推定した９５％信頼区間はサンプルサイズが小さいほど広くなりサンプルサイズが大きいほど狭くなっている。この傾向は、予測性能の実測値の分布と適合している。また、推定した９５％信頼区間の広さは、小さいサンプルサイズと大きいサンプルサイズの両方について実際の予測性能の分散と十分に整合している。すなわち、図１９よりも９５％信頼区間の精度が高くなっている。よって、予測性能曲線の推定にあたって、サンプルサイズ毎の予測性能の分散が適切に評価されていると言える。予測性能の分散が適切に評価されることで、予測性能曲線の推定精度が向上する。また、複数の機械学習アルゴリズムの間の予測性能の比較を正確に行うことができる。
【０１７３】
次に、予測性能の分散を算出する数式の数学的根拠について説明する。
（ａ）問題の形式的な記述
同一の母集合からｍ通りの訓練データＤ1，Ｄ2，…，ＤmとテストデータＴが抽出されたとする。ある機械学習アルゴリズムに対して訓練データＤkを与えて学習されたモデルをｆkとする（ｋ＝１，２，…，ｍ）。テストデータＴをインスタンス＜Ｙi，Ｘi＞の集合とする（ｉ＝１，２，…，ｎ）。Ｘiは説明変数の値（入力値）であり、Ｙiは入力値Ｘiに対応する目的変数の既知の値（真値）である。入力値Ｘiに対してモデルｆkが予測した値（予測値）をｙik＝ｆk（Ｘi）とする。入力値Ｘiに対するモデルｆkによる予測の誤差はｅik＝Ｙi−ｙikと定義される。テストデータＴに含まれるインスタンスの数、すなわち、テストデータＴのサイズはｎである。以下では主に、添え字ｉ，ｊはテストデータＴのインスタンスを識別する変数、添え字ｋはモデルを識別する変数として使用する。
【０１７４】
機械学習アルゴリズムが回帰を目的とする場合、予測値は連続量であり、ロスの指標として数式（１）の二乗ロスが用いられることが多い。この二乗ロスをテストデータＴの全てのインスタンスについて平均したものが数式（２）のＭＳＥ（平均二乗誤差）である。
【０１７５】
【数１】
2018173813.tif 000003
【０１７６】
【数２】
2018173813.tif 000004
【０１７７】
ここで、Ｅ［・］は期待値を求める演算子であり、Ｖ［・］は分散を求める演算子である。Ｅ［・］，Ｖ［・］に付加する添え字Ｘは、この演算子がテストデータＴの複数のインスタンスの間の演算であることを示す。Ｅ［・］，Ｖ［・］に付加する添え字Ｍは、この演算子が複数のモデルの間の演算であることを示す。すなわち、ＥX［・］はテストデータＴの複数のインスタンスの間で平均化した期待値を示し、ＥM［・］は複数のモデルの間で平均化した期待値を示す。ＶX［・］はテストデータＴの複数のインスタンスの間の分散を示し、ＶM［・］は複数のモデルの間の分散を示す。また、ｃｏｖ（・，・）は共分散を求める共分散関数であり、ｃｏｒ（・，・）は相関係数を求める相関係数関数である。ｃｏｖ（・，・），ｃｏｒ（・，・）にも添え字Ｘ，Ｍが付加される。
【０１７８】
機械学習アルゴリズムが二値分類を目的とする場合、予測値は｛−１，１｝のような二値の離散値であり、ロスの指標として数式（３）の０−１ロスが用いられることが多い。この０−１ロスをテストデータＴの全てのインスタンスについて平均して１から引いたものが、数式（４）の正答率（Accuracy）である。
【０１７９】
【数３】
2018173813.tif 000005
【０１８０】
【数４】
2018173813.tif 000006
【０１８１】
ＭＳＥは値が小さいほど予測性能が高いことを示し、正答率は値が大きいほど予測性能が高いことを示す。ただし、両者ともテストデータＴ全体について平均化したロスがモデルの予測性能の良否を表している点で共通しており、モデルロスと言うことができる。モデルｆkに対するモデルロスＭＬkは数式（５）の通りである。予測性能の分散は、数式（６）のように複数のモデルの間のモデルロスの分散として表される。
【０１８２】
【数５】
2018173813.tif 000007
【０１８３】
【数６】
2018173813.tif 000008
【０１８４】
（ｂ）バイアス・バリアンス分解
モデルによる予測で生じるロスはバイアスとバリアンスに分解できる。バイアスはモデルの予測値の偏りを示す量である。バイアスが低いモデルほど正確なモデルであると言える。表現力の低いモデル（調整可能な係数が少ないような複雑性の低いモデル）はバイアスが高くなる傾向にある。バリアンスはモデルの予測値のばらつきを示す量である。バリアンスが低いほど正確なモデルであると言える。表現力の高いモデル（調整可能な係数が多いような複雑性の高いモデル）はバリアンスが高くなる傾向にある。表現力の高いモデルには、訓練データに過剰適合するという過学習のリスクがある。
【０１８５】
テストデータＴの入力値Ｘiに対するロスＬi、バイアスＢiおよびバリアンスＶiは、数式（７）〜（９）のように定義される。ロスＬiは複数のモデルの間の二乗誤差の期待値であり、バイアスＢiは複数のモデルの間の誤差の期待値であり、バリアンスＶiは複数のモデルの間の誤差の分散である。ロスＬiとバイアスＢiとバリアンスＶiとの間には、数式（１０）の関係（バイアス・バリアンス分解）が成立する。
【０１８６】
【数７】
2018173813.tif 000009
【０１８７】
【数８】
2018173813.tif 000010
【０１８８】
【数９】
2018173813.tif 000011
【０１８９】
【数１０】
2018173813.tif 000012
【０１９０】
様々な入力値Ｘiに対するロスＬiの期待値を期待ロスＥＬ、バイアスＢiの二乗の期待値を期待バイアスＥＢ２、バリアンスＶiの期待値を期待バリアンスＥＶとする。期待ロスＥＬ、期待バイアスＥＢ２、期待バリアンスＥＶは、数式（１１）〜（１３）のように定義される。期待ロスＥＬと期待バイアスＥＢ２と期待バリアンスＥＶとの間には、数式（１４）の関係（バイアス・バリアンス分解）が成立する。
【０１９１】
【数１１】
2018173813.tif 000013
【０１９２】
【数１２】
2018173813.tif 000014
【０１９３】
【数１３】
2018173813.tif 000015
【０１９４】
【数１４】
2018173813.tif 000016
【０１９５】
ここでの目的は、ＥＬ，ＥＢ２，ＥＶとモデルロスの分散との間の関係を導出することである。なお、期待ロスＥＬとモデルロスＭＬkの期待値とは、数式（１５）に示すように等価である。一方、ロスＬiの分散とモデルロスＭＬkの分散とは等価でない。以下では、予測性能の分散を推定する数式を次の流れで導出する。第１に、インスタンスのロスの分散をバイアスとバリアンスで記述する。第２に、モデルロスの分散をインスタンス成分と相互作用成分に分解する。第３に、インスタンス成分を算出する。第４に、相互作用成分を算出する。第５に、モデルロスの分散をバイアスとバリアンスで記述する。
【０１９６】
【数１５】
2018173813.tif 000017
【０１９７】
（ｃ）ロスの分散をバイアスとバリアンスで記述
テストデータＴの入力値Ｘiを固定して複数のモデルの誤差を並べた誤差ベクトルを考える。誤差ｅを確率変数とみなしてその分布が正規分布に従うと仮定すると、複数のモデルの間のロスの分散は数式（１６）のように定義され、バイアスＢiとバリアンスＶiの組またはロスＬiとバイアスＢiの組によって記述することができる。数式（１６）の１行目から２行目への変形では、数式（１７）に示す統計学上の性質（確率変数の４乗の期待値）が利用されている。数式（１７）においてＸは確率変数であり、Ｓは歪度であり、Ｋは尖度である。正規分布の場合はＳ＝０かつＫ＝３である。
【０１９８】
【数１６】
2018173813.tif 000018
【０１９９】
【数１７】
2018173813.tif 000019
【０２００】
（ｄ）モデルロスの分散をインスタンス成分と相互作用成分に分解
分散の基本的性質から、予測性能の分散（複数のモデルの間のモデルロスの分散）について数式（１８）が成立する。これをｎ×ｎ行列の成分の平均と考えると、ｉ＝ｊである対角成分は入力値Ｘiに対するロスの分散を表しており、その相関係数は１になる。一方、ｉ≠ｊである非対角成分の相関係数は異なる入力値の間のロスの相関を表している。異なる入力値に対する誤差の発生状況は共通点が少ないため、その相関係数は十分に小さくなることが多く、予測性能の高いモデルほどその相関係数は０に近づく。対角成分と非対角成分とは性質が異なるため、数式（１９）のように両者を分離して考える。
【０２０１】
【数１８】
2018173813.tif 000020
【０２０２】
【数１９】
2018173813.tif 000021
【０２０３】
数式（１９）では、モデルロスの分散を第１項のインスタンス成分と第２項の相互作用成分とに分解している。第１項はインスタンスのロスの分散の期待値を表しており、モデルロスの分散の大部分を占めることが多い。第２項は異なる入力値の間の共分散の期待値を表しており、モデルロスの分散に対する寄与は小さいことが多い。第１項はテストデータＴのサイズｎに反比例するため、テストデータＴのインスタンスを増やすことでモデルロスの分散を低減できる。ただし、第２項が存在することから低減効果には限界がある。
（ｅ）インスタンス成分を算出
数式（１９）の第１項について検討する。上記の数式（１６）より数式（２０）が成立する。ここで、数式（２０）の第１項と第２項を算出するために幾つかの仮定をおく。多くの機械学習アルゴリズムは不偏推定量を出力するようにモデルを学習することから、数式（２１）のように誤差の期待値が０になるという仮定をおく。数式（２１）からバイアスＢiについて数式（２２）の性質が導出される。
【０２０４】
【数２０】
2018173813.tif 000022
【０２０５】
【数２１】
2018173813.tif 000023
【０２０６】
【数２２】
2018173813.tif 000024
【０２０７】
確率分布の中には、訓練データのサンプルサイズやサンプリング方法に依存して期待値や分散が変化することはあっても、確率分布の形状を示す歪度や尖度は変化しない（または、変化が非常に緩やかである）ものがあると仮定する。具体的には、入力値Ｘiに対する複数のモデルの間の誤差の分布は正規分布を形成し、尖度＝３かつ歪度＝０になることを仮定する。また、バイアスＢiの分布の尖度Ｋ１は変化しないことを仮定する。バイアスＢiの分布の尖度Ｋ１は、数式（２３）のように定義される。数式（２３）と上記の数式（１２）から数式（２４）が算出される。
【０２０８】
【数２３】
2018173813.tif 000025
【０２０９】
【数２４】
2018173813.tif 000026
【０２１０】
また、モデルｆkに対する複数の入力値の間の誤差の分布の尖度Ｋ２は、モデル間で共通でありかつ変化しないことを仮定する。尖度Ｋ２は数式（２５）のように定義される。Ｋ１，Ｋ２の値はそれぞれ３〜１０の範囲内であることが多く、両者は近いことが多い。
【０２１１】
【数２５】
2018173813.tif 000027
【０２１２】
数式（２５）から数式（２６）が導出される。数式（２６）を数式（１８），（１９）に代入することで数式（２７）が算出される。ここで、尖度Ｋ２はサイズｎより十分に小さいため、１−Ｋ２／ｎは１に近似される。数式（２０），（２３）を数式（１８），（１９）に代入することで数式（２８）が算出される。数式（２８）から数式（２７）を減算して数式（２９）が算出される。そして、数式（２０），（２４），（２９）から数式（３０）が算出される。これが、数式（１９）の第１項の主要成分である。
【０２１３】
【数２６】
2018173813.tif 000028
【０２１４】
【数２７】
2018173813.tif 000029
【０２１５】
【数２８】
2018173813.tif 000030
【０２１６】
【数２９】
2018173813.tif 000031
【０２１７】
【数３０】
2018173813.tif 000032
【０２１８】
（ｆ）相互作用成分を算出
不動点Ｃｏｒ１ｖを数式（３１）のように定義する。不動点Ｃｏｒ１ｖは、訓練データのサンプルサイズを変化させても値が変化しないかまたは非常に緩やかに変化することが多いため、ここではサンプルサイズに依存しないと仮定する。不動点Ｃｏｒ１ｖの値は０．００１〜０．１程度であることが多い。
【０２１９】
【数３１】
2018173813.tif 000033
【０２２０】
ここで、数式（３２）に示す統計学上の性質（誤差の相関係数の期待値）を利用する。誤差の期待値が０であるとき、２つの誤差の相関係数の期待値は０に近似する。この性質から数式（３３）が成立し、上記の数式（３１）から数式（３４）が算出される。
【０２２１】
【数３２】
2018173813.tif 000034
【０２２２】
【数３３】
2018173813.tif 000035
【０２２３】
【数３４】
2018173813.tif 000036
【０２２４】
また、数式（３５）が成立する。数式（３５）の２行目から３行目への変形では、相関係数ｃｏｒMとバリアンスＶi，Ｖjとは互いに独立であることを仮定している。数式（３５）の３行目から４行目への変形では、上記の数式（３４）を利用しており、また、Ｖi・Ｖjの期待値がＥＶ2に近似することを利用している。数式（３５）の４行目の近似では、サイズｎが１より十分に大きいため１／（ｎ−１）2を無視している。
【０２２５】
【数３５】
2018173813.tif 000037
【０２２６】
ここで、数式（３６）に示す統計学上の性質（共分散の二乗と二乗の共分散の関係）を利用する。確率変数Ｘ，Ｙの結合確率が二次元正規分布に従うならば数式（３６）が成立する。上記の仮定より誤差の分散が正規分布に従うため、数式（３６）を利用して数式（３７）が算出される。また、数式（３８）が成立する。数式（３８）の１行目から２行目への変形では、共分散ｃｏｖMとバイアスＢi，Ｂjは概ね独立であることを仮定している。数式（３８）の２行目の近似では、ＢiＢjの期待値はバイアスＢiの期待値の二乗に近似しその結果０に近似するという性質を利用している。数式（３５），（３８）を数式（３７）に代入することで数式（３９）が算出される。これが、数式（１９）の第２項の主要成分である。
【０２２７】
【数３６】
2018173813.tif 000038
【０２２８】
【数３７】
2018173813.tif 000039
【０２２９】
【数３８】
2018173813.tif 000040
【０２３０】
【数３９】
2018173813.tif 000041
【０２３１】
（ｇ）モデルロスの分散をバイアスとバリアンスで記述
上記の数式（１８），（１９），（３０），（３９）より数式（４０）の近似式が成立する。尖度Ｋ２は尖度Ｋ１に近似するため、数式（４０）は数式（４１）のように近似される。典型的にはＫ１（ＥＬ＋ＥＢ２）はｃｏｒ１ｖ（ＥＬ−ＥＢ２）より十分に大きいため、数式（４１）は更に数式（４２）のように近似される。尖度Ｋ１は事前には不明であるが、第２の実施の形態ではその具体的な値は不要である。よって、数式（４２）は比例定数Ｃを用いて数式（４３）のように単純化できる。これにより、予測性能の分散が、期待ロスＥＬと期待バイアスＥＢ２の差に比例し、かつ、期待ロスＥＬと期待バイアスＥＢ２の和に比例するという数式が導出される。
【０２３２】
【数４０】
2018173813.tif 000042
【０２３３】
【数４１】
2018173813.tif 000043
【０２３４】
【数４２】
2018173813.tif 000044
【０２３５】
【数４３】
2018173813.tif 000045
【０２３６】
第２の実施の形態の機械学習装置１００によれば、複数の機械学習アルゴリズムそれぞれについて、１段階大きなサンプルサイズを用いた次の学習ステップを実行した場合の単位時間当たりの予測性能の改善量（改善速度）が推定される。そして、改善速度が最大の機械学習アルゴリズムが選択され、選択された機械学習アルゴリズムの次の学習ステップが実行される。改善速度の推定と機械学習アルゴリズムの選択とが繰り返され、予測性能が最も高くなったモデルが最終的に出力される。
【０２３７】
これにより、予測性能の改善に寄与しない学習ステップは実行されず、全体の学習時間を短縮することができる。また、改善速度の推定値が最大の機械学習アルゴリズムが選択されるため、学習時間に制限があり機械学習を途中で打ち切った場合であっても、終了時刻までに得られたモデルが、制限時間内に得られる最善のモデルとなる。また、少しでも予測性能の改善に寄与する学習ステップは、実行順序が後になる可能性はあるものの実行される余地が残される。このため、予測性能の上限が高い機械学習アルゴリズムをサンプルサイズが小さいうちに切り捨ててしまうリスクを低減できる。このように、複数の機械学習アルゴリズムを利用してモデルの予測性能を効率的に向上させることができる。
【０２３８】
また、次の学習ステップで達成される予測性能を推定するにあたり、サンプルサイズと予測性能の実測値とを対応付けた実測データから、非線形回帰分析により予測性能曲線が推定される。このとき、予測性能の実測値に内包される誤差の分散がサンプルサイズによって異なるという異分散性をカバーするため、サンプルサイズによって異なる重みが付与される。あるサンプルサイズの重みは、当該サンプルサイズにおける分散の推定値に反比例するように設定される。あるサンプルサイズにおける分散は、バイアス・バリアンス分解の考え方を応用して、分散と期待ロスと期待バイアスの間の関係を示す所定の計算式に従って推定される。これにより、非線形回帰分析の精度が向上し、誤差を含む実測値からも信頼性の高い予測性能曲線を推定することができ、未実行のサンプルサイズについての予測性能の期待値と分散を精度よく推定することが可能となる。
【０２３９】
また、予測性能の推定精度が向上することで、予測性能の上限値が低い機械学習アルゴリズムを誤選択してしまうリスクが下がり、全体の学習時間を短縮することができる。また、各機械学習アルゴリズムについて予測性能が上限値に十分近づいたか否かを早い段階で判断することができ、学習ステップの打ち切りを適切なタイミングで判断できる。
【符号の説明】
【０２４０】
１０  比較装置
１１  記憶部
１２  処理部
１３  関係情報
１４，１５  予測性能曲線
１６ａ，１６ｂ，１６ｃ  サンプルサイズ
１７ａ，１７ｂ  予測性能測定値
１８ａ，１８ｂ  分散推定値
１９ａ，１９ｂ  評価値
【図１】
2018173813.tif 000046
【図２】
2018173813.tif 000047
【図３】
2018173813.tif 000048
【図４】
2018173813.tif 000049
【図５】
2018173813.tif 000050
【図６】
2018173813.tif 000051
【図７】
2018173813.tif 000052
【図８】
2018173813.tif 000053
【図９】
2018173813.tif 000054
【図１０】
2018173813.tif 000055
【図１１】
2018173813.tif 000056
【図１２】
2018173813.tif 000057
【図１３】
2018173813.tif 000058
【図１４】
2018173813.tif 000059
【図１５】
2018173813.tif 000060
【図１６】
2018173813.tif 000061
【図１７】
2018173813.tif 000062
【図１８】
2018173813.tif 000063
【図１９】
2018173813.tif 000064
【図２０】
2018173813.tif 000065