(57)【特許請求の範囲】
【請求項１】
コンピュータに、
複数の機械学習アルゴリズムそれぞれを訓練データを用いて実行し、
前記複数の機械学習アルゴリズムの実行結果に基づいて、前記複数の機械学習アルゴリズムによって生成される複数のモデルそれぞれの予測性能の増加速度を算出し、
前記増加速度に基づいて、前記複数の機械学習アルゴリズムの中から一の機械学習アルゴリズムを選択し、他の訓練データを用いて前記一の機械学習アルゴリズムを実行する、
処理を実行させる機械学習管理プログラム。
【請求項２】
前記他の訓練データは、前記訓練データよりもサイズが大きい、
請求項１記載の機械学習管理プログラム。
【請求項３】
前記一の機械学習アルゴリズムの実行結果に基づいて、前記一の機械学習アルゴリズムによって生成されるモデルの予測性能の増加速度を更新し、
前記更新された増加速度に基づいて、前記複数の機械学習アルゴリズムの中から次に実行する機械学習アルゴリズムを選択する、
処理を更に実行させる請求項１記載の機械学習管理プログラム。
【請求項４】
前記増加速度の算出では、前記複数の機械学習アルゴリズムそれぞれについて、訓練データサイズを増加した場合の予測性能の増加量と実行時間とを算出し、前記予測性能の増加量および前記実行時間に基づいて前記増加速度を算出する、
請求項１記載の機械学習管理プログラム。
【請求項５】
前記予測性能の増加量は、各機械学習アルゴリズムの実行結果を統計処理して算出される推定値よりも、所定量または統計誤差を示す量だけ大きい値とする、
請求項４記載の機械学習管理プログラム。
【請求項６】
前記実行時間は、機械学習アルゴリズムに応じて異なる計算式を用いて算出する、
請求項４記載の機械学習管理プログラム。
【請求項７】
前記複数の機械学習アルゴリズムそれぞれの実行は、当該機械学習アルゴリズムに適用可能な複数のパラメータ値を用いて２以上のモデルを生成し、当該機械学習アルゴリズムの実行結果として前記２以上のモデルの予測性能のうち最大の予測性能を判定することを含む、
請求項１記載の機械学習管理プログラム。
【請求項８】
前記複数の機械学習アルゴリズムそれぞれの実行は、一のパラメータ値について経過時間が閾値を超えた場合に、当該一のパラメータ値を用いたモデルの生成を停止することを含み、
前記一の機械学習アルゴリズムの選択は、前記増加速度に基づいて、前記他の訓練データを用いて実行するか、または、前記閾値を大きくして前記一のパラメータ値を用いて再実行するか選択することを含む、
請求項７記載の機械学習管理プログラム。
【請求項９】
機械学習に用いるデータを記憶する記憶部と、
複数の機械学習アルゴリズムそれぞれを前記データに含まれる訓練データを用いて実行し、前記複数の機械学習アルゴリズムの実行結果に基づいて、前記複数の機械学習アルゴリズムによって生成される複数のモデルそれぞれの予測性能の増加速度を算出し、前記増加速度に基づいて、前記複数の機械学習アルゴリズムの中から一の機械学習アルゴリズムを選択し、前記データに含まれる他の訓練データを用いて前記一の機械学習アルゴリズムを実行する演算部と、
を有する機械学習管理装置。
【請求項１０】
コンピュータが実行する機械学習管理方法であって、
複数の機械学習アルゴリズムそれぞれを訓練データを用いて実行し、
前記複数の機械学習アルゴリズムの実行結果に基づいて、前記複数の機械学習アルゴリズムによって生成される複数のモデルそれぞれの予測性能の増加速度を算出し、
前記増加速度に基づいて、前記複数の機械学習アルゴリズムの中から一の機械学習アルゴリズムを選択し、他の訓練データを用いて前記一の機械学習アルゴリズムを実行する、
機械学習管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は機械学習管理プログラム、機械学習管理装置および機械学習管理方法に関する。
【背景技術】
【０００２】
コンピュータを利用したデータ分析の１つとして、機械学習が行われることがある。機械学習では、幾つかの既知の事例を示す訓練データをコンピュータに入力する。コンピュータは、訓練データを分析して、要因（説明変数や独立変数と言うことがある）と結果（目的変数や従属変数と言うことがある）との間の関係を一般化したモデルを学習する。学習されたモデルを用いることで、未知の事例についての結果を予測することができる。例えば、複数人の生活習慣と病気の有無を調査した訓練データから、任意の人の病気の発症リスクを予測するモデルを学習できる。また、過去の商品・サービスの需要量を示す訓練データから、将来の商品・サービスの需要量を予測するモデルを学習できる。
【０００３】
機械学習では、学習されるモデルの正確さ、すなわち、未知の事例の結果を正確に予測する能力（予測性能と言うことがある）が高いことが好ましい。予測性能は、学習に用いる訓練データのサイズが大きいほど高くなる。一方、訓練データのサイズが大きいほど、モデルの学習時間も長くなる。そこで、実用上十分な予測性能をもつモデルを効率的に得られるようにする方法として、プログレッシブサンプリング法が提案されている。
【０００４】
プログレッシブサンプリング法では、コンピュータは、まず小さなサイズの訓練データを用いてモデルを学習する。コンピュータは、訓練データとは異なる既知の事例を示すテストデータを用いて、モデルによって予測した結果と既知の結果とを比較し、学習されたモデルの予測性能を評価する。予測性能が十分でない場合、コンピュータは、前回よりもサイズが大きい訓練データを用いてモデルを再度学習する。以上を予測性能が十分に高くなるまで繰り返すことで、過度にサイズの大きな訓練データを使用することを抑制でき、モデルの学習時間を短縮することができる。
【０００５】
プログレッシブサンプリング法において、予測性能が十分高くなったと判定する基準として、最新のモデルと１つ前のモデルとの間の予測性能の差（予測性能の上昇量）が所定の閾値未満になったことを基準とする方法が提案されている。また、予測性能が十分高くなったと判定する基準として、単位学習時間当たりの予測性能の上昇量が所定の閾値未満になったことを基準とする方法も提案されている。
【０００６】
なお、ニューラルネットワークを用いて商品需要を予測する需要予測システムが提案されている。提案の需要予測システムは、複数の予測モデルそれぞれを用いて、第１の時期の販売実績データから第２の時期の需要予測データを生成する。需要予測システムは、第２の時期の需要予測データと第２の時期の販売実績データとを比較し、複数の予測モデルのうち販売実績データに最も近い需要予測データを出力した予測モデルを選択する。需要予測システムは、選択した予測モデルを用いて以降の商品需要を予測する。
【０００７】
また、上水道施設における需要水量を予測する配水量予測装置が提案されている。提案の配水量予測装置は、配水実績データの中から機械学習に用いる訓練データを選択する。配水量予測装置は、選択した訓練データとニューラルネットワークとを用いて需要水量を予測し、また、選択した訓練データと重回帰分析とを用いて需要水量を予測する。配水量予測装置は、ニューラルネットワークによる予測結果と重回帰分析による予測結果とを統合し、統合された需要水量の予測結果を出力する。
【０００８】
また、将来の電力需要を予測する時系列予測システムが提案されている。提案の時系列予測システムは、誤差を拡大する要因に対する感応度が異なる複数の予測モデルを用いて複数の予測値を算出し、複数の予測値を組み合わせて最終的な予測値を算出する。時系列予測システムは、複数の予測モデルそれぞれの予測値と実績値との間の予測誤差を監視し、予測誤差の変化に応じて複数の予測モデルの組み合わせ方を変更する。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開平１０−１４３４９０号公報
【特許文献２】特開２０００−３０５６０６号公報
【特許文献３】特開２００７−１０８８０９号公報
【非特許文献】
【００１０】
【非特許文献１】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.
【非特許文献２】Christopher Meek, Bo Thiesson and David Heckerman, "The Learning-Curve Sampling Method Applied to Model-Based Clustering", Journal of Machine Learning Research, Volume 2 (Feb), pp. 397-418, 2002.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ところで、訓練データからモデルを学習する手順として、回帰分析、サポートベクタマシン（ＳＶＭ）、ランダムフォレストなどの様々な機械学習アルゴリズムが提案されている。使用する機械学習アルゴリズムが異なると、学習されたモデルの予測性能も異なることが多い。そのため、複数の機械学習アルゴリズムを使用可能である場合の方が、１つの機械学習アルゴリズムのみを使用する場合よりも予測性能を向上できる余地がある。
【００１２】
ただし、同じ機械学習アルゴリズムを使用しても、訓練データを変更したときの予測性能の変化や学習時間の変化は、学習内容の性質によって異なる。例えば、ある機械学習アルゴリズムを使用して商品の需要量を予測するモデルを学習する場合、訓練データのサイズを増加したときの予測性能の上昇量が大きい可能性がある。一方、同じ機械学習アルゴリズムを使用して病気の発症リスクを予測するモデルを学習する場合には、訓練データのサイズを増加したときの予測性能の上昇量が小さい可能性がある。このため、複数の機械学習アルゴリズムの中で、高い予測性能に到達できるものや短い学習時間で所望の予測性能に到達できるものを事前に知ることは難しい。
【００１３】
そこで、１つの機械学習方法として、複数の機械学習アルゴリズムを互いに独立に実行して複数のモデルを取得し、最も予測性能の高いモデルを採用する方法が考えられる。上記のプログレッシブサンプリング法のように、訓練データを変えながらモデルの学習を繰り返す方法を採用した場合、複数の機械学習アルゴリズムそれぞれについて当該繰り返しを実行する機械学習方法も考えられる。
【００１４】
しかし、複数の機械学習アルゴリズムそれぞれについて訓練データを変えながらモデルの学習を繰り返すと、最終的に採用するモデルの予測性能の向上に寄与しない無駄な学習が多く発生し、学習時間が過度に長くなってしまうという問題がある。また、上記の機械学習方法では、複数の機械学習アルゴリズム全ての実行が完了しないと、高い予測性能に到達できる機械学習アルゴリズムが判明しないという問題がある。
【００１５】
１つの側面では、本発明は、機械学習によって得られるモデルの予測性能を効率的に向上させることができる機械学習管理プログラム、機械学習管理装置および機械学習管理方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
１つの態様では、コンピュータに以下の処理を実行させる機械学習プログラムが提供される。複数の機械学習アルゴリズムそれぞれを訓練データを用いて実行する。複数の機械学習アルゴリズムの実行結果に基づいて、複数の機械学習アルゴリズムによって生成される複数のモデルそれぞれの予測性能の増加速度を算出する。増加速度に基づいて、複数の機械学習アルゴリズムの中から一の機械学習アルゴリズムを選択し、他の訓練データを用いて一の機械学習アルゴリズムを実行する。
【００１７】
また、１つの態様では、記憶部と演算部とを有する機械学習管理装置が提供される。また、１つの態様では、コンピュータが実行する機械学習管理方法が提供される。
【発明の効果】
【００１８】
１つの側面では、機械学習によって得られるモデルの予測性能を効率的に向上できる。
【図面の簡単な説明】
【００１９】
【図１】第１の実施の形態の機械学習管理装置を示す図である。
【図２】機械学習装置のハードウェア例を示すブロック図である。
【図３】サンプリングサイズと予測性能の関係例を示すグラフである。
【図４】学習時間と予測性能の関係例を示すグラフである。
【図５】複数の機械学習アルゴリズムの第１の使用例を示す図である。
【図６】複数の機械学習アルゴリズムの第２の使用例を示す図である。
【図７】複数の機械学習アルゴリズムの第３の使用例を示す図である。
【図８】第２の実施の形態の機械学習装置の機能例を示すブロック図である。
【図９】管理テーブルの例を示す図である。
【図１０】第２の実施の形態の機械学習の手順例を示すフローチャートである。
【図１１】第２の実施の形態の機械学習の手順例を示すフローチャート（続き）である。
【図１２】第２の実施の形態のステップ実行の手順例を示すフローチャートである。
【図１３】時間推定の手順例を示すフローチャートである。
【図１４】性能改善量推定の手順例を示すフローチャートである。
【図１５】第３の実施の形態の機械学習装置の機能例を示すブロック図である。
【図１６】推定式テーブルの例を示す図である。
【図１７】時間推定の他の手順例を示すフローチャートである。
【図１８】第４の実施の形態の機械学習装置の機能例を示すブロック図である。
【図１９】第４の実施の形態のステップ実行の手順例を示すフローチャートである。
【図２０】ハイパーパラメータベクトル空間の例を示す図である。
【図２１】ハイパーパラメータベクトル集合の分割例を示す第１の図である。
【図２２】ハイパーパラメータベクトル集合の分割例を示す第２の図である。
【図２３】第５の実施の形態の機械学習装置の機能例を示すブロック図である。
【図２４】第５の実施の形態の機械学習の手順例を示すフローチャートである。
【図２５】第５の実施の形態の機械学習の手順例を示すフローチャート（続き）である。
【発明を実施するための形態】
【００２０】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。
【００２１】
図１は、第１の実施の形態の機械学習管理装置を示す図である。
第１の実施の形態の機械学習管理装置１０は、既知の事例から機械学習によって、未知の事例の結果を予測するモデルを生成する。機械学習管理装置１０が行う機械学習は、病気の発症リスクの予測、将来の商品・サービスの需要量の予測、工場における新製品の歩留まりの予測など、様々な用途に用いることができる。機械学習管理装置１０は、ユーザが操作するクライアントコンピュータでもよいし、クライアントコンピュータからネットワーク経由でアクセスされるサーバコンピュータでもよい。
【００２２】
機械学習管理装置１０は、記憶部１１および演算部１２を有する。記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性の半導体メモリでもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性のストレージでもよい。演算部１２は、例えば、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサである。ただし、演算部１２は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路を含んでもよい。プロセッサは、ＲＡＭなどのメモリ（記憶部１１でもよい）に記憶されたプログラムを実行する。プログラムには、機械学習管理プログラムが含まれる。複数のプロセッサの集合（マルチプロセッサ）を「プロセッサ」と呼ぶこともある。
【００２３】
記憶部１１は、機械学習に用いるデータ１１ａを記憶する。データ１１ａは、既知の事例を示すものであり、センサなどのデバイスを用いて実世界から収集されたものでもよいし、ユーザが作成したものでもよい。データ１１ａは、複数の単位データ（レコードやエントリと言うこともある）を含む。１つの単位データは、１つの事例を示すものであり、例えば、要因を示す１または２以上の変数（説明変数や独立変数と言うことがある）の値と、結果を示す変数（目的変数や従属変数と言うことがある）の値とを含む。
【００２４】
演算部１２は、複数の機械学習アルゴリズムを実行することができる。実行可能な機械学習アルゴリズムには、ロジスティック回帰分析、サポートベクタマシン、ランダムフォレストなど、様々な機械学習アルゴリズムが含まれ得る。実行可能な機械学習アルゴリズムの数は、数十個〜数百個になることもある。ただし、第１の実施の形態では説明を簡単にするため、機械学習アルゴリズムＡ，Ｂ，Ｃの３つを一例として挙げることがある。
【００２５】
また、演算部１２は、機械学習アルゴリズムの使用方法として、モデルの学習に用いる訓練データを変更しながら同じ機械学習アルゴリズムを繰り返し実行する方法を採用する。例えば、演算部１２は、訓練データのサイズを増加しながら同じ機械学習アルゴリズムを繰り返し実行するプログレッシブサンプリング法を採用する。プログレッシブサンプリング法によれば、過度に大きなサイズの訓練データを使用することを抑制でき、所望の予測性能をもつモデルを短時間で学習することができる。複数の機械学習アルゴリズムを使用し、かつ、訓練データを変更しながら同じ機械学習アルゴリズムを繰り返し実行する方法を採用する場合に、演算部１２は、以下のような手順で機械学習を進める。
【００２６】
まず、演算部１２は、記憶部１１に記憶されたデータ１１ａの一部分を訓練データとして用いて、複数の機械学習アルゴリズムそれぞれを実行し、機械学習アルゴリズム毎にモデルを生成する。モデルは、例えば、要因を示す１または２以上の変数の値を引数として取得し、結果を示す変数の値（結果の予測値）を出力する関数である。機械学習によって、要因を示す変数それぞれの重み（係数）が決定される。
【００２７】
例えば、演算部１２は、データ１１ａから抽出した訓練データ１４ａを用いて、機械学習アルゴリズム１３ａ（機械学習アルゴリズムＡ）を実行する。また、演算部１２は、データ１１ａから抽出した訓練データ１４ｂを用いて、機械学習アルゴリズム１３ｂ（機械学習アルゴリズムＢ）を実行する。また、演算部１２は、データ１１ａから抽出した訓練データ１４ｃを用いて、機械学習アルゴリズム１３ｃ（機械学習アルゴリズムＣ）を実行する。訓練データ１４ａ，１４ｂ，１４ｃは、同じ単位データの集合でもよいし、異なる単位データの集合でもよい。後者の場合、訓練データ１４ａ，１４ｂ，１４ｃはそれぞれ、データ１１ａからランダムにサンプリングされたものでもよい。
【００２８】
複数の機械学習アルゴリズムがそれぞれ実行されると、演算部１２は、その実行結果に基づいて、機械学習アルゴリズム毎にモデルの予測性能の増加速度を算出する。モデルの予測性能は、モデルの正確さ、すなわち、未知の事例の結果を正確に予測する能力を示す。予測性能を表す指標値として、例えば、正答率（Accuracy）、適合率（Precision）、平均二乗誤差（ＲＭＳＥ：Root Mean Squared Error）などを用いることができる。予測性能は、データ１１ａの一部分であって訓練データとは異なる部分をテストデータとして用いて算出することができる。テストデータは、データ１１ａからランダムにサンプリングされたものでもよい。モデルから予測される結果と既知の結果とを比較することで、予測性能を算出できる。テストデータのサイズは、例えば、訓練データの半分程度でよい。
【００２９】
増加速度は、例えば、単位学習時間当たりの予測性能の上昇量を示す。次に訓練データを変更した場合の学習時間は、例えば、前回までの学習時間の実績から推定することができる。次に訓練データを変更した場合の予測性能の上昇量は、例えば、前回までに生成されたモデルの予測性能の実績から推定することができる。
【００３０】
例えば、演算部１２は、機械学習アルゴリズム１３ａの実行結果から、機械学習アルゴリズム１３ａに対応する増加速度１５ａを算出する。また、演算部１２は、機械学習アルゴリズム１３ｂの実行結果から、機械学習アルゴリズム１３ｂに対応する増加速度１５ｂを算出する。また、演算部１２は、機械学習アルゴリズム１３ｃの実行結果から、機械学習アルゴリズム１３ｃに対応する増加速度１５ｃを算出する。一例として、増加速度１５ａ＝２．０、増加速度１５ｂ＝２．５、増加速度１５ｃ＝１．０と算出される。この場合、機械学習アルゴリズム１３ｂの増加速度１５ｂが最も大きいことになる。
【００３１】
各機械学習アルゴリズムの増加速度が算出されると、演算部１２は、それら増加速度に基づいて、複数の機械学習アルゴリズムの中から何れか１つの機械学習アルゴリズムを選択する。例えば、演算部１２は、増加速度が最も大きい機械学習アルゴリズムを選択する。そして、演算部１２は、記憶部１１に記憶されたデータ１１ａの他の一部分を訓練データとして用いて、選択した機械学習アルゴリズムを実行する。次に使用する訓練データのサイズは、好ましくは、前回使用した訓練データのサイズよりも大きい。次に使用する訓練データは、前回使用した訓練データの一部または全部を包含していてもよい。
【００３２】
例えば、演算部１２は、増加速度１５ａ，１５ｂ，１５ｃのうち最も大きい増加速度１５ｂを特定し、増加速度１５ｂに対応する機械学習アルゴリズム１３ｂを選択する。そして、演算部１２は、データ１１ａから抽出した訓練データ１４ｄを用いて、機械学習アルゴリズム１３ｂを実行する。訓練データ１４ｄは、少なくとも、機械学習アルゴリズム１３ｂが前回使用した訓練データ１４ｂと異なる集合である。訓練データ１４ｄのサイズは、例えば、訓練データ１４ｂの２倍または４倍程度とする。
【００３３】
なお、演算部１２は、訓練データ１４ｄを用いて機械学習アルゴリズム１３ｂを実行した後、その実行結果に基づいて増加速度を更新してもよい。そして、演算部１２は、更新した増加速度に基づいて、機械学習アルゴリズム１３ａ，１３ｂ，１３ｃの中から次に実行する機械学習アルゴリズムを選択してもよい。演算部１２は、増加速度に基づいて機械学習アルゴリズムを１つずつ選択する処理を、モデルの予測性能が所定条件を満たすまで繰り返してもよい。このとき、機械学習アルゴリズム１３ａ，１３ｂ，１３ｃのうち一部の機械学習アルゴリズムが、最初の１回実行されて以降実行されない可能性もある。
【００３４】
第１の実施の形態の機械学習管理装置１０によれば、複数の機械学習アルゴリズムそれぞれが訓練データを用いて実行され、その実行結果に基づいて、機械学習アルゴリズム毎の予測性能の増加速度が算出される。そして、算出された増加速度に基づいて、次に異なる訓練データを用いて実行する機械学習アルゴリズムが選択される。
【００３５】
これにより、１つの機械学習アルゴリズムのみを使用する場合と比べて、高い予測性能をもつモデルを学習することができる。また、複数の機械学習アルゴリズムの全てを訓練データを変えながら繰り返し実行する場合と比べて、最終的に採用するモデルの予測性能の向上に寄与しない無駄な学習を削減でき、総合的な学習時間を短縮することができる。また、許容できる学習時間に制限がある場合であっても、増加速度が大きい機械学習アルゴリズムを優先的に選択することで、その制限のもとで最善の機械学習を行うことができる。また、ユーザが途中で機械学習を打ち切った場合でも、その時点までに得られたモデルが制限時間の範囲内で得られる最善のモデルとなる。このように、機械学習によって得られるモデルの予測性能を効率的に向上させることが可能となる。
【００３６】
［第２の実施の形態］
次に、第２の実施の形態を説明する。
図２は、機械学習装置のハードウェア例を示すブロック図である。
【００３７】
機械学習装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７を有する。ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７は、バス１０８に接続されている。なお、機械学習装置１００は、第１の実施の形態の機械学習管理装置１０に対応する。ＣＰＵ１０１は、第１の実施の形態の演算部１２に対応する。ＲＡＭ１０２またはＨＤＤ１０３は、第１の実施の形態の記憶部１１に対応する。
【００３８】
ＣＰＵ１０１は、プログラムの命令を実行する演算回路を含むプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されたプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、機械学習装置１００は複数のプロセッサを備えてもよく、以下で説明する処理を複数のプロセッサまたはプロセッサコアを用いて並列に実行してもよい。また、複数のプロセッサの集合（マルチプロセッサ）を「プロセッサ」と呼んでもよい。
【００３９】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムやＣＰＵ１０１が演算に用いるデータを一時的に記憶する揮発性の半導体メモリである。なお、機械学習装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。
【００４０】
ＨＤＤ１０３は、ＯＳ（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）、平均二乗誤差（ＲＭＳＥ）などが挙げられる。例えば、結果がＹＥＳ／ＮＯの２値で表されるとする。また、Ｎ件のテストデータの事例のうち、予測値＝ＹＥＳ・実績値＝ＹＥＳの件数をＴｐ、予測値＝ＹＥＳ・実績値＝ＮＯの件数をＦｐ、予測値＝ＮＯ・実績値＝ＹＥＳの件数をＦｎ、予測値＝ＮＯ・実績値＝ＮＯの件数をＴｎとする。この場合、正答率は予測が当たった割合であり、（Ｔｐ＋Ｔｎ）／Ｎと算出される。適合率は「ＹＥＳ」の予測を間違えない確率であり、Ｔｐ／（Ｔｐ＋Ｆｐ）と算出される。平均二乗誤差は、各事例の実績値をｙと表し予測値をｙ＾と表すと、（ｓｕｍ（ｙ−ｙ＾）2／Ｎ）1/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で学習したモデルを採用する。このとき、機械学習装置１００は、サンプリングサイズｓ5の機械学習を行わなくてよい。
【００５７】
プログレッシブサンプリング法の停止条件として、例えば、１つ前のモデルと今回のモデルとの間の予測性能の差（上昇量）が閾値未満になったことを停止条件とすることが考えられる。また、例えば、単位学習時間当たりの予測性能の上昇量が閾値未満になったことを停止条件とすることも考えられる。前者については、例えば、前述の非特許文献１に記載がある。後者については、例えば、前述の非特許文献２（"The Learning-Curve Sampling Method Applied to Model-Based Clustering"）に記載がある。
【００５８】
上記のように、プログレッシブサンプリング法では、１つのサンプリングサイズに対する処理（１つの学習ステップ）毎に、モデルの学習と当該モデルの予測性能の評価とを行う。各学習ステップ内の手順（バリデーション方法）としては、例えば、クロスバリデーションやランダムサブサンプリングバリデーションなどを用いることができる。
【００５９】
クロスバリデーションでは、機械学習装置１００は、サンプリングしたデータをｋ個（ｋは２以上の整数）のブロックに分割し、このうちｋ−１個のブロックを訓練データとして使用して１個のブロックをテストデータとして使用する。機械学習装置１００は、テストデータとして使用するブロックを変えながらモデルの学習と予測性能の評価をＫ回繰り返す。１つの学習ステップの結果として、例えば、Ｋ個のモデルのうち最も予測性能の高いモデルと、Ｋ回の予測性能の平均値とが出力される。クロスバリデーションは、限定された量のデータを活用して予測性能の評価を可能とする。
【００６０】
ランダムサブサンプリングバリデーションでは、機械学習装置１００は、データの母集合から訓練データとテストデータをランダムにサンプリングし、訓練データを用いてモデルを学習し、テストデータを用いてモデルの予測性能を算出する。機械学習装置１００は、サンプリングとモデルの学習と予測性能の評価をＫ回繰り返す。
【００６１】
各サンプリングは、非復元抽出サンプリングである。すなわち、１回のサンプリングの中で、訓練データ内に同じ単位データは重複して含まれず、テストデータ内に同じ単位データは重複して含まれない。また、１回のサンプリングの中で、訓練データとテストデータに同じ単位データは重複して含まれない。ただし、Ｋ回のサンプリングの間で、同じ単位データが選択されることはあり得る。１つの学習ステップの結果として、例えば、ｋ個のモデルのうち最も予測性能の高いモデルと、Ｋ回の予測性能の平均値とが出力される。
【００６２】
ところで、訓練データからモデルを学習する手順（機械学習アルゴリズム）には様々なものが存在する。機械学習装置１００は、複数の機械学習アルゴリズムを使用することができる。機械学習装置１００が使用できる機械学習アルゴリズムの数は、数十〜数百程度であってもよい。機械学習アルゴリズムの一例として、ロジスティック回帰分析、サポートベクタマシン、ランダムフォレストなどを挙げることができる。
【００６３】
ロジスティック回帰分析は、目的変数ｙの値と説明変数ｘ1，ｘ2，…，ｘkの値をＳ字曲線にフィッティングする回帰分析である。目的変数ｙおよび説明変数ｘ1，ｘ2，…，ｘkは、ｌｏｇ（ｙ／（１−ｙ））＝ａ1ｘ1＋ａ2ｘ2＋…＋ａkｘk＋ｂの関係を満たすと仮定される。ａ1，ａ2，…，ａk，ｂは係数であり、回帰分析によって決定される。
【００６４】
サポートベクタマシンは、Ｎ次元空間に配置された単位データの集合を、２つのクラスに最も明確に分割するような境界面を算出する機械学習アルゴリズムである。境界面は、各クラスとの距離（マージン）が最大になるように算出される。
【００６５】
ランダムフォレストは、複数の単位データを適切に分類するためのモデルを生成する機械学習アルゴリズムである。ランダムフォレストでは、母集合から単位データをランダムにサンプリングする。説明変数の一部をランダムに選択し、選択した説明変数の値に応じてサンプリングした単位データを分類する。説明変数の選択と単位データの分類を繰り返すことで、複数の説明変数の値に基づく階層的な決定木を生成する。単位データのサンプリングと決定木の生成を繰り返すことで複数の決定木を取得し、それら複数の決定木を合成することで、単位データを分類するための最終的なモデルを生成する。
【００６６】
図４は、学習時間と予測性能の関係例を示すグラフである。
曲線２２〜２４は、著名なデータ集合（ＣｏｖｅｒＴｙｐｅ）を用いて測定された学習時間と予測性能の間の関係を示している。予測性能の指標として、ここでは正答率を用いている。曲線２２は、機械学習アルゴリズムとしてロジスティック回帰を用いた場合の学習時間と予測性能の間の関係を示す。曲線２３は、機械学習アルゴリズムとしてサポートベクタマシンを用いた場合の学習時間と予測性能の間の関係を示す。曲線２４は、機械学習アルゴリズムとしてランダムフォレストを用いた場合の学習時間と予測性能の間の関係を示す。なお、図４の横軸は、学習時間について対数目盛になっている。
【００６７】
曲線２２が示すように、ロジスティック回帰を使用した場合、サンプリングサイズ＝８００における予測性能は約０．７１、学習時間は約０．２秒である。サンプリングサイズ＝３２００における予測性能は約０．７５、学習時間は約０．５秒である。サンプリングサイズ＝１２８００における予測性能は約０．７５５、学習時間は１．５秒である。サンプリングサイズ＝５１２００における予測性能は約０．７６、学習時間は約６秒である。
【００６８】
曲線２３が示すように、サポートベクタマシンを使用した場合、サンプリングサイズ＝８００における予測性能は約０．７０、学習時間は約０．２秒である。サンプリングサイズ＝３２００における予測性能は約０．７７、学習時間は約２秒である。サンプリングサイズ＝１２８００に対応する予測性能は約０．７８５、学習時間は約２０秒である。
【００６９】
曲線２４が示すように、ランダムフォレストを使用した場合、サンプリングサイズ＝８００における予測性能は約０．７４、学習時間は約２．５秒である。サンプリングサイズ＝３２００における予測性能は約０．７９、学習時間は約１５秒である。サンプリングサイズ＝１２８００に対応する予測性能は約０．８２、学習時間は約２００秒である。
【００７０】
このように、上記のデータ集合に対しては、ロジスティック回帰は、全体的に学習時間が短く予測性能が低い。サポートベクタマシンは、全体的にロジスティック回帰よりも学習時間が長く予測性能が高い。ランダムフォレストは、全体的にサポートベクタマシンよりも更に学習時間が長く予測性能が高い。ただし、図４の例では、サンプリングサイズが小さい場合のサポートベクタマシンの予測性能は、ロジスティック回帰の予測性能よりも低くなっている。すなわち、プログレッシブサンプリング法における初期段階の予測性能の上昇カーブも、機械学習アルゴリズムによって異なる。
【００７１】
また、前述のように、個々の機械学習アルゴリズムの予測性能の上限や予測性能の上昇カーブは、使用するデータの性質にも依存する。そのため、複数の機械学習アルゴリズムのうち、予測性の上限が最も高い機械学習アルゴリズムや上限に近い予測性能を最も短時間で達成できる機械学習アルゴリズムを事前に特定することは難しい。そこで、以下では、複数の機械学習アルゴリズムを使用し、かつ、プログレッシブサンプリング法を使用する場合に、予測性能の高いモデルを効率的に得られるようにする方法を検討する。
【００７２】
図５は、複数の機械学習アルゴリズムの第１の使用例を示す図である。
ここでは説明を簡単にするため、機械学習アルゴリズムＡ，Ｂ，Ｃの３つの機械学習アルゴリズムが存在する場合を考える。機械学習アルゴリズムＡのみを使用してプログレッシブサンプリング法を行う場合、機械学習装置１００は、学習ステップ３１，３２，３３（Ａ１，Ａ２，Ａ３）を順に実行する。機械学習アルゴリズムＢのみを使用してプログレッシブサンプリング法を行う場合、機械学習装置１００は、学習ステップ３４，３５，３６（Ｂ１，Ｂ２，Ｂ３）を順に実行する。機械学習アルゴリズムＣのみを使用してプログレッシブサンプリング法を行う場合、機械学習装置１００は、学習ステップ３７，３８，３９（Ｃ１，Ｃ２，Ｃ３）を順に実行する。なお、ここでは、学習ステップ３３，３６，３９でそれぞれ停止条件が満たされるものと仮定する。
【００７３】
学習ステップ３１，３４，３７のサンプリングサイズは同じである。例えば、学習ステップ３１，３４，３７の単位データ数はそれぞれ１万である。学習ステップ３２，３５，３８のサンプリングサイズは同じであり、学習ステップ３１，３４，３７のサンプリングサイズの２倍または４倍程度である。例えば、学習ステップ３２，３５，３８の単位データ数はそれぞれ４万である。学習ステップ３３，３６，３９のサンプリングサイズは同じであり、学習ステップ３２，３５，３８のサンプリングサイズの２倍または４倍程度である。例えば、学習ステップ３３，３６，３９の単位データ数はそれぞれ１６万である。
【００７４】
機械学習アルゴリズムＡ，Ｂ，Ｃとプログレッシブサンプリング法を組み合わせる方法としては、次のような第１の方法が考えられる。第１の方法は、機械学習アルゴリズムＡ，Ｂ，Ｃをそれぞれ独立に実行する方法である。機械学習装置１００は、機械学習アルゴリズムＡについて学習ステップ３１，３２，３３を実行する。次に、機械学習装置１００は、機械学習アルゴリズムＢについて学習ステップ３４，３５，３６を実行する。次に、機械学習装置１００は、機械学習アルゴリズムＣについて学習ステップ３７，３８，３９を実行する。そして、機械学習装置１００は、学習ステップ３１〜３９によって出力された全てのモデルの中から、最も予測性能の高いモデルを選択する。
【００７５】
しかし、第１の方法では、最終的に採用するモデルの予測性能の向上に寄与しない無駄な学習ステップが多く発生する。このため、全体の学習時間が長くなってしまうという問題がある。また、第１の方法では、機械学習アルゴリズムＡ，Ｂ，Ｃの全てが完了するまで最大の予測性能を達成できる機械学習アルゴリズムが判明しない。このため、学習時間に制限があり機械学習を途中で打ち切った場合に、終了時刻までに得られたモデルが、制限時間内に得られる最善のモデルであることを保証できないという問題がある。
【００７６】
図６は、複数の機械学習アルゴリズムの第２の使用例を示す図である。
機械学習アルゴリズムＡ，Ｂ，Ｃとプログレッシブサンプリング法を組み合わせる方法としては、次のような第２の方法も考えられる。第２の方法は、機械学習アルゴリズムＡ，Ｂ，Ｃの学習ステップを１つずつ実行し、以降は、最初の学習ステップで算出された予測性能が最大の機械学習アルゴリズムのみを実行する方法である。
【００７７】
機械学習装置１００は、機械学習アルゴリズムＡの学習ステップ３１と、機械学習アルゴリズムＢの学習ステップ３４と、機械学習アルゴリズムＣの学習ステップ３７とを実行する。機械学習装置１００は、学習ステップ３１，３４，３７によって算出された予測性能の中で最大の予測性能を判定し、最大の予測性能が算出された学習ステップ３７が属する機械学習アルゴリズムＣを選択する。機械学習装置１００は、選択した機械学習アルゴリズムＣについて学習ステップ３８，３９を実行する。このとき、機械学習装置１００は、選択しなかった機械学習アルゴリズムＡについての学習ステップ３２，３３と、選択しなかった機械学習アルゴリズムＢについての学習ステップ３５，３６とは実行しない。
【００７８】
しかし、図４について説明したように、複数の機械学習アルゴリズムの間で、サンプリングサイズが小さい場合の予測性能の大小とサンプリングサイズが大きい場合の予測性能の大小とが一致するとは限らない。このため、第２の方法では、選択した機械学習アルゴリズムによって最高の予測性能が達成できるとは限らないという問題がある。
【００７９】
図７は、複数の機械学習アルゴリズムの第３の使用例を示す図である。
機械学習アルゴリズムＡ，Ｂ，Ｃとプログレッシブサンプリング法を組み合わせる方法としては、次のような第３の方法も考えられる。第３の方法は、各機械学習アルゴリズムについて、サンプリングサイズが１段階大きい学習ステップを実行した場合の予測性能の改善速度を推定し、改善速度が最大の機械学習アルゴリズムを選択して学習ステップを１つだけ進める方法である。学習ステップを１つ進める毎に、改善速度の推定値が見直される。このため、第３の方法では、最初のうちは複数の機械学習アルゴリズムの学習ステップが混在して実行され、徐々に機械学習アルゴリズムが限定されていく。
【００８０】
改善速度の推定値は、性能改善量の推定値を実行時間の推定値で割ったものである。性能改善量の推定値は、次の学習ステップの予測性能の推定値と、複数の機械学習アルゴリズムを通じて現在までに達成された予測性能の最大値（以下では達成予測性能と言うことがある）との差である。次の学習ステップの予測性能は、同じ機械学習アルゴリズムの過去の予測性能と次の学習ステップのサンプリングサイズとに基づいて推定される。実行時間の推定値は、次の学習ステップに要する時間の推定値であり、同じ機械学習アルゴリズムの過去の実行時間と次の学習ステップのサンプリングサイズとに基づいて推定される。
【００８１】
機械学習装置１００は、機械学習アルゴリズムＡの学習ステップ３１と、機械学習アルゴリズムＢの学習ステップ３４と、機械学習アルゴリズムＣの学習ステップ３７とを実行する。機械学習装置１００は、学習ステップ３１，３４，３７の実行結果に基づいて、機械学習アルゴリズムＡ，Ｂ，Ｃの改善速度をそれぞれ推定する。ここでは、機械学習アルゴリズムＡの改善速度＝２．５、機械学習アルゴリズムＢの改善速度＝２．０、機械学習アルゴリズムＣの改善速度＝１．０と推定されたとする。すると、機械学習装置１００は、改善速度が最大の機械学習アルゴリズムＡを選択し、学習ステップ３２を実行する。
【００８２】
学習ステップ３２が実行されると、機械学習装置１００は、機械学習アルゴリズムＡ，Ｂ，Ｃの改善速度を更新する。ここでは、機械学習アルゴリズムＡの改善速度＝０．７３、機械学習アルゴリズムＢの改善速度＝１．０、機械学習アルゴリズムＣの改善速度＝０．５と推定されたとする。学習ステップ３２によって達成予測性能が上昇したため、機械学習アルゴリズムＢ，Ｃの改善速度も低下している。機械学習装置１００は、改善速度が最大の機械学習アルゴリズムＢを選択し、学習ステップ３５を実行する。
【００８３】
学習ステップ３５が実行されると、機械学習装置１００は、機械学習アルゴリズムＡ，Ｂ，Ｃの改善速度を更新する。ここでは、機械学習アルゴリズムＡの改善速度＝０．０、機械学習アルゴリズムＢの改善速度＝０．８、機械学習アルゴリズムＣの改善速度＝０．０と推定されたとする。機械学習装置１００は、改善速度が最大の機械学習アルゴリズムＢを選択し、学習ステップ３６を実行する。学習ステップ３６によって予測性能が十分に上昇したと判定されると、機械学習は終了する。この場合、機械学習アルゴリズムＡの学習ステップ３３や機械学習アルゴリズムＣの学習ステップ３８，３９は実行されない。
【００８４】
なお、次の学習ステップの予測性能を推定するにあたっては、統計誤差を考慮し、予測性能が今後上昇する可能性のある機械学習アルゴリズムを早期に切り捨ててしまうリスクを低減することが好ましい。例えば、機械学習装置１００は、回帰分析によって予測性能の期待値とその９５％予測区間を算出し、９５％予測区間の上限値（ＵＣＢ：Upper Confidence Bound）を、改善速度を算出する際の予測性能を推定値として使用することが考えられる。９５％予測区間は、測定される予測性能（測定値）のばらつきを示すものであり、新たな予測性能が９５％の確率でこの区間に収まると予想されることを示す。すなわち、統計上の期待値よりも統計誤差に応じた幅だけ大きい値を使用する。
【００８５】
ただし、ＵＣＢに代えて、機械学習装置１００は、推定される予測性能の分布を積分して、予測性能が達成予測性能を超える確率（ＰＩ：Probability of Improvement）を算出してもよい。また、機械学習装置１００は、推定される予測性能の分布を積分して、予測性能が達成予測性能を超える期待値（ＥＩ：Expected Improvement）を算出してもよい。統計誤差に関するリスクについては、例えば、次の非特許文献にも記載がある：Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer, "Finite-time Analysis of the Multiarmed Bandit Problem", Machine Learning vol. 47, pp. 235-256, 2002。
【００８６】
第３の方法では、予測性能の改善に寄与しない学習ステップは実行されず、全体の学習時間を短縮することができる。また、単位時間当たりの性能改善量が最大である機械学習アルゴリズムの学習ステップが優先的に実行される。このため、学習時間に制限があり機械学習を途中で打ち切った場合であっても、終了時刻までに得られたモデルが、制限時間内に得られる最善のモデルとなる。また、少しでも予測性能の改善に寄与する学習ステップは、実行順序が後になる可能性はあるものの実行される余地が残される。このため、予測性能の上限が高い機械学習アルゴリズムを切り捨ててしまうリスクを低減できる。
【００８７】
以下では、機械学習装置１００が上記の第３の方法で機械学習を行う場合を説明する。
図８は、第２の実施の形態の機械学習装置の機能例を示すブロック図である。
機械学習装置１００は、データ記憶部１２１、管理テーブル記憶部１２２、学習結果記憶部１２３、制限時間入力部１３１、ステップ実行部１３２、時間推定部１３３、性能改善量推定部１３４および学習制御部１３５を有する。データ記憶部１２１、管理テーブル記憶部１２２および学習結果記憶部１２３は、例えば、ＲＡＭ１０２またはＨＤＤ１０３に確保した記憶領域を用いて実現できる。制限時間入力部１３１、ステップ実行部１３２、時間推定部１３３、性能改善量推定部１３４および学習制御部１３５は、例えば、ＣＰＵ１０１が実行するプログラムモジュールを用いて実現できる。
【００８８】
データ記憶部１２１は、機械学習に使用できるデータの集合を記憶する。データの集合は、それぞれが目的変数の値（結果）と１または２以上の説明変数の値（要因）とを含む単位データの集合である。データ記憶部１２１に記憶されたデータは、機械学習装置１００または他の情報処理装置が各種デバイスから収集したものでもよいし、機械学習装置１００または他の情報処理装置に対してユーザが入力したものでもよい。
【００８９】
管理テーブル記憶部１２２は、機械学習の進行を管理する管理テーブルを記憶する。管理テーブルは、学習制御部１３５によって更新される。管理テーブルの詳細は後述する。
学習結果記憶部１２３は、機械学習の結果を記憶する。機械学習の結果には、目的変数と１または２以上の説明変数との間の関係を示すモデルが含まれる。例えば、各説明変数の重みを示す係数が、機械学習によって決定される。また、機械学習の結果には、学習されたモデルの予測性能が含まれる。また、機械学習の結果には、モデルの学習に用いた機械学習アルゴリズムとサンプリングサイズの情報が含まれる。
【００９０】
制限時間入力部１３１は、機械学習の制限時間の情報を取得し、制限時間を学習制御部１３５に通知する。制限時間の情報は、入力デバイス１１２を通じてユーザから入力されてもよい。また、制限時間の情報は、ＲＡＭ１０２またはＨＤＤ１０３に記憶された設定ファイルから読み出すようにしてもよい。また、制限時間の情報は、ネットワーク１１４を介して他の情報処理装置から受信してもよい。
【００９１】
ステップ実行部１３２は、複数の機械学習アルゴリズムを実行することができる。ステップ実行部１３２は、学習制御部１３５から、機械学習アルゴリズムとサンプリングサイズの指定を受け付ける。すると、ステップ実行部１３２は、データ記憶部１２１に記憶されたデータを用いて、指定された機械学習アルゴリズムおよび指定されたサンプリングサイズについての学習ステップを実行する。すなわち、ステップ実行部１３２は、指定されたサンプリングサイズに基づいて、データ記憶部１２１から訓練データとテストデータを抽出する。ステップ実行部１３２は、訓練データと指定された機械学習アルゴリズムを用いてモデルを学習し、テストデータを用いて予測性能を算出する。
【００９２】
モデルの学習と予測性能の算出について、ステップ実行部１３２は、クロスバリデーションやランダムサブサンプリングバリデーションなどの各種のバリデーション方法を使用できる。使用するバリデーション方法は、ステップ実行部１３２に予め設定されてもよい。また、ステップ実行部１３２は、１つの学習ステップに要した実行時間を測定する。ステップ実行部１３２は、モデルと予測性能と実行時間を学習制御部１３５に出力する。
【００９３】
時間推定部１３３は、ある機械学習アルゴリズムの次の学習ステップの実行時間を推定する。時間推定部１３３は、学習制御部１３５から、機械学習アルゴリズムと、当該機械学習アルゴリズムの何番目の学習ステップであるかを示すステップ番号の指定を受け付ける。すると、時間推定部１３３は、指定された機械学習アルゴリズムに属する実行済みの学習ステップの実行時間と、指定されたステップ番号に対応するサンプリングサイズと、所定の推定式とから、指定されたステップ番号の学習ステップの実行時間を推定する。時間推定部１３３は、推定した実行時間を学習制御部１３５に出力する。
【００９４】
性能改善量推定部１３４は、ある機械学習アルゴリズムの次の学習ステップの性能改善量を推定する。性能改善量推定部１３４は、学習制御部１３５から、機械学習アルゴリズムとステップ番号の指定を受け付ける。すると、性能改善量推定部１３４は、指定された機械学習アルゴリズムに属する実行済みの学習ステップの予測性能と、指定されたステップ番号に対応するサンプリングサイズと、所定の推定式とから、指定されたステップ番号の学習ステップの予測性能を推定する。このとき、性能改善量推定部１３４は、統計誤差を考慮して、ＵＣＢなど予測性能の期待値よりも大きい値を用いる。性能改善量推定部１３４は、現在の達成予測性能からの改善量を算出し、学習制御部１３５に出力する。
【００９５】
学習制御部１３５は、複数の機械学習アルゴリズムを用いた機械学習を制御する。学習制御部１３５は、複数の機械学習アルゴリズムそれぞれの最初の学習ステップをステップ実行部１３２に実行させる。学習制御部１３５は、１つの学習ステップが実行される毎に、同じ機械学習アルゴリズムの次の学習ステップの実行時間を時間推定部１３３に推定させ、次の学習ステップの性能改善量を性能改善量推定部１３４に推定させる。学習制御部１３５は、性能改善量を実行時間で割った改善速度を算出する。
【００９６】
そして、学習制御部１３５は、複数の機械学習アルゴリズムの中から改善速度が最大のものを選択し、選択した機械学習アルゴリズムの次の学習ステップをステップ実行部１３２に実行させる。学習制御部１３５は、改善速度の更新と機械学習アルゴリズムの選択とを、予測性能が所定の停止条件を満たすか、学習時間が制限時間を超えるまで繰り返す。学習制御部１３５は、機械学習の停止までに得られたモデルのうち予測性能が最大のモデルを学習結果記憶部１２３に保存する。また、学習制御部１３５は、予測性能と機械学習アルゴリズムの情報とサンプリングサイズの情報を学習結果記憶部１２３に保存する。
【００９７】
図９は、管理テーブルの例を示す図である。
管理テーブル１２２ａは、学習制御部１３５によって生成されて管理テーブル記憶部１２２に記憶される。管理テーブル１２２ａは、アルゴリズムＩＤ、ステップ番号、改善速度、予測性能および実行時間の項目を含む。
【００９８】
アルゴリズムＩＤは、機械学習アルゴリズムを識別する識別情報である。以下の説明では、ｉ番目（ｉ＝１，２，３，…）の機械学習アルゴリズムのアルゴリズムＩＤをａiと表記することがある。ステップ番号は、プログレッシブサンプリング法の学習ステップを示す番号である。管理テーブル１２２ａには、機械学習アルゴリズム毎に、次に実行される学習ステップのステップ番号が登録される。以下の説明では、ｉ番目の機械学習アルゴリズムに対応するステップ番号をｋiと表記することがある。
【００９９】
また、ステップ番号からはサンプリングサイズを一意に特定することができる。以下の説明では、ｊ番目の学習ステップのサンプリングサイズをｓjと表記することがある。データ記憶部１２１に記憶されたデータ集合をＤとし、Ｄのサイズ（単位データの数）を｜Ｄ｜とすると、例えば、ｓ1＝｜Ｄ｜／２10，ｓj＝ｓ1×２j-1と決定される。
【０１００】
改善速度の項目には、機械学習アルゴリズム毎に、次に実行される学習ステップの改善速度の推定値が登録される。改善速度の単位は、例えば、［秒-1］である。以下の説明では、ｉ番目の機械学習アルゴリズムに対応する改善速度をｒiと表記することがある。予測性能の項目には、機械学習アルゴリズム毎に、既に実行された学習ステップの予測性能が列挙される。以下の説明では、ｉ番目の機械学習アルゴリズムのｊ番目の学習ステップで算出された予測性能をｐi,jと表記することがある。実行時間の項目には、機械学習アルゴリズム毎に、既に実行された学習ステップの実行時間が列挙される。実行時間の単位は、例えば、［秒］である。以下の説明では、ｉ番目の機械学習アルゴリズムのｊ番目の学習ステップの実行時間をＴi,jと表記することがある。
【０１０１】
図１０は、第２の実施の形態の機械学習の手順例を示すフローチャートである。
（Ｓ１０）学習制御部１３５は、データ記憶部１２１を参照して、プログレッシブサンプリング法における学習ステップのサンプリングサイズｓ1，ｓ2，ｓ3，…を決定する。例えば、学習制御部１３５は、データ記憶部１２１に記憶されたデータ集合Ｄのサイズに基づいて、ｓ1＝｜Ｄ｜／２10，ｓj＝ｓ1×２j-1と決定する。
【０１０２】
（Ｓ１１）学習制御部１３５は、管理テーブル１２２ａの各機械学習アルゴリズムのステップ番号を１に初期化する。また、学習制御部１３５は、各機械学習アルゴリズムの改善速度を、改善速度が取り得る最大値に初期化する。また、学習制御部１３５は、達成予測性能Ｐを、達成予測性能Ｐが取り得る最小値（例えば、０）に初期化する。
【０１０３】
（Ｓ１２）学習制御部１３５は、管理テーブル１２２ａの中から、改善速度が最大の機械学習アルゴリズムを選択する。ここで選択した機械学習アルゴリズムをａiとする。
（Ｓ１３）学習制御部１３５は、機械学習アルゴリズムａiの改善速度ｒiが、閾値Ｒ未満であるか判断する。閾値Ｒは、予め学習制御部１３５に設定されていてもよい。例えば、閾値Ｒ＝０．００１／３６００［秒-1］とする。改善速度ｒiが閾値Ｒ未満である場合はステップＳ２８に処理が進み、それ以外の場合はステップＳ１４に処理が進む。
【０１０４】
（Ｓ１４）学習制御部１３５は、管理テーブル１２２ａから、機械学習アルゴリズムａiに対応するステップ番号ｋiを検索する。ここでは、ｋi＝ｊであるとする。
（Ｓ１５）学習制御部１３５は、ステップ番号ｊに対応するサンプリングサイズｓjを算出し、ステップ実行部１３２に対して機械学習アルゴリズムａiとサンプリングサイズｓjを指定する。ステップ実行部１３２は、機械学習アルゴリズムａiについてｊ番目の学習ステップを実行する。ステップ実行部１３２の処理の詳細は後述する。
【０１０５】
（Ｓ１６）学習制御部１３５は、ステップ実行部１３２から、学習されたモデルと当該モデルの予測性能ｐi,jと実行時間Ｔi,jとを取得する。
（Ｓ１７）学習制御部１３５は、ステップＳ１６で取得した予測性能ｐi,jと、達成予測性能Ｐ（現在までに達成された最大の予測性能）とを比較し、前者が後者より大きいか判断する。予測性能ｐi,jが達成予測性能Ｐよりも大きい場合はステップＳ１８に処理が進み、それ以外の場合はステップＳ１９に処理が進む。
【０１０６】
（Ｓ１８）学習制御部１３５は、達成予測性能Ｐを予測性能ｐi,jに更新する。また、学習制御部１３５は、達成予測性能Ｐと対応付けて、その予測性能が得られた機械学習アルゴリズムａiとステップ番号ｊとを記憶しておく。
【０１０７】
（Ｓ１９）学習制御部１３５は、管理テーブル１２２ａに記憶されたステップ番号のうち、機械学習アルゴリズムａiに対応するステップ番号ｋiをｊ＋１に更新する。すなわち、ステップ番号ｋiをインクリメント（１だけ加算）する。また、学習制御部１３５は、合計時間ｔsum＝０に初期化する。
【０１０８】
図１１は、第２の実施の形態の機械学習の手順例を示すフローチャート（続き）である。
（Ｓ２０）学習制御部１３５は、機械学習アルゴリズムａiの次の学習ステップのサンプリングサイズｓj+1を算出する。学習制御部１３５は、サンプリングサイズｓj+1とデータ記憶部１２１に記憶されたデータ集合Ｄのサイズとを比較し、前者が後者より大きいか判断する。サンプリングサイズｓj+1がデータ集合Ｄのサイズよりも大きい場合はステップＳ２１に処理が進み、それ以外の場合はステップＳ２２に処理が進む。
【０１０９】
（Ｓ２１）学習制御部１３５は、管理テーブル１２２ａに記憶された改善速度のうち、機械学習アルゴリズムａiに対応する改善速度ｒiを０に更新する。これにより、機械学習アルゴリズムａiは実行されなくなる。そして、前述のステップＳ１２に処理が進む。
【０１１０】
（Ｓ２２）学習制御部１３５は、時間推定部１３３に対して機械学習アルゴリズムａiとステップ番号ｊ＋１を指定する。時間推定部１３３は、機械学習アルゴリズムａiについて次の学習ステップ（ｊ＋１番目の学習ステップ）を実行した場合の実行時間ｔi,j+1を推定する。時間推定部１３３の処理の詳細は後述する。
【０１１１】
（Ｓ２３）学習制御部１３５は、性能改善量推定部１３４に対して機械学習アルゴリズムａ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とサンプリングサイズｓjとを特定する。また、ステップ実行部１３２は、データ記憶部１２１に記憶されているデータ集合Ｄを特定する。
【０１１８】
（Ｓ３１）ステップ実行部１３２は、サンプリングサイズｓjが、データ集合Ｄのサイズの２／３よりも大きいか判断する。サンプリングサイズｓjが２／３×｜Ｄ｜よりも大きい場合、ステップ実行部１３２は、データ量が不足しているためクロスバリデーションを選択する。そして、ステップＳ３８に処理が進む。サンプリングサイズｓjが２／３×｜Ｄ｜以下である場合、ステップ実行部１３２は、データ量が十分あるためランダムサブサンプリングバリデーションを選択する。そして、ステップＳ３２に処理が進む。
【０１１９】
（Ｓ３２）ステップ実行部１３２は、データ集合Ｄからサンプリングサイズｓjの訓練データＤtをランダムに抽出する。訓練データの抽出は、非復元抽出サンプリングとして行う。よって、訓練データには、互いに異なるｓj個の単位データが含まれる。
【０１２０】
（Ｓ３３）ステップ実行部１３２は、データ集合Ｄのうち訓練データＤtを除いた部分から、サイズｓj／２のテストデータＤsをランダムに抽出する。テストデータの抽出は、非復元抽出サンプリングとして行う。よって、テストデータには、訓練データＤtと異なりかつ互いに異なるｓj／２個の単位データが含まれる。なお、ここでは訓練データＤtのサイズとテストデータＤsのサイズの比を２：１としたが、比を変更してもよい。
【０１２１】
（Ｓ３４）ステップ実行部１３２は、機械学習アルゴリズムａiとデータ集合Ｄから抽出した訓練データＤtとを用いてモデルｍを学習する。
（Ｓ３５）ステップ実行部１３２は、学習したモデルｍとデータ集合Ｄから抽出したテストデータＤsとを用いて、モデルｍの予測性能ｐを算出する。予測性能ｐを表す指標として、正答率、適合率、ＲＭＳＥなど任意の指標を用いることができる。予測性能ｐを表す指標が、予めステップ実行部１３２に設定されてもよい。
【０１２２】
（Ｓ３６）ステップ実行部１３２は、上記ステップＳ３２〜Ｓ３５の繰り返し回数と閾値Ｋとを比較し、前者が後者未満であるか判断する。閾値Ｋは、予めステップ実行部１３２に設定されていてもよい。例えば、閾値Ｋ＝１０とする。繰り返し回数が閾値Ｋ未満の場合はステップＳ３２に処理が進み、それ以外の場合はステップＳ３７に処理が進む。
【０１２３】
（Ｓ３７）ステップ実行部１３２は、ステップＳ３５で算出されたＫ個の予測性能ｐの平均値を算出し、予測性能ｐi,jとして出力する。また、ステップ実行部１３２は、ステップＳ３０が開始されてからステップＳ３２〜Ｓ３６の繰り返しが終了するまでの実行時間Ｔi,jを算出して出力する。また、ステップ実行部１３２は、ステップＳ３４で学習されたＫ個のモデルｍのうち予測性能ｐが最大のモデルを出力する。そして、ランダムサブサンプリングバリデーションによる１つの学習ステップが終了する。
【０１２４】
（Ｓ３８）ステップ実行部１３２は、上記のランダムサブサンプリングバリデーションに代えて、前述したクロスバリデーションを実行する。例えば、ステップ実行部１３２は、データ集合Ｄからサンプリングサイズｓjのサンプルデータをランダムに抽出し、抽出したサンプルデータをＫ個のブロックに均等に分割する。ステップ実行部１３２は、Ｋ−１個のブロックを訓練データとして使用し１個のブロックをテストデータとして使用することを、テストデータのブロックを変えながらＫ回繰り返す。ステップ実行部１３２は、Ｋ個の予測性能の平均値と、実行時間と、予測性能が最大のモデルを出力する。
【０１２５】
図１３は、時間推定の手順例を示すフローチャートである。
（Ｓ４０）時間推定部１３３は、学習制御部１３５から指定された機械学習アルゴリズムａiとステップ番号ｊ＋１とを特定する。
【０１２６】
（Ｓ４１）時間推定部１３３は、機械学習アルゴリズムａiの学習ステップが２つ以上実行済みか、すなわち、ステップ番号ｊ＋１が２より大きいか判断する。ｊ＋１＞２の場合はステップＳ４２に処理が進み、それ以外の場合はステップＳ４５に処理が進む。
【０１２７】
（Ｓ４２）時間推定部１３３は、管理テーブル１２２ａから機械学習アルゴリズムａiに対応する実行時間Ｔi,1，Ｔi,2を検索する。
（Ｓ４３）時間推定部１３３は、サンプリングサイズｓ1，ｓ2と実行時間Ｔi,1，Ｔi,2を用いて、サンプリングサイズｓから実行時間ｔを推定する推定式ｔ＝α×ｓ＋βの係数α，βを決定する。係数α，βは、Ｔi,1およびｓ1をｔおよびｓにそれぞれ代入した式と、Ｔi,2およびｓ2をｔおよびｓにそれぞれ代入した式からなる連立方程式を解くことで決定できる。ただし、機械学習アルゴリズムａiの学習ステップが３つ以上実行済みである場合、時間推定部１３３は、それら学習ステップの実行時間から回帰分析によって係数α，βを決定してもよい。実行時間をサンプリングサイズの一次式と仮定することは、前述の非特許文献２（"The Learning-Curve Sampling Method Applied to Model-Based Clustering"）にも記載がある。
【０１２８】
（Ｓ４４）時間推定部１３３は、上記の推定式とサンプリングサイズｓj+1を用いて（ｓj+1を推定式のｓに代入して）、ｊ＋１番目の学習ステップの実行時間ｔi,j+1を推定する。時間推定部１３３は、推定した実行時間ｔi,j+1を出力する。
【０１２９】
（Ｓ４５）時間推定部１３３は、管理テーブル１２２ａから機械学習アルゴリズムａiに対応する実行時間Ｔi,1を検索する。
（Ｓ４６）時間推定部１３３は、サンプリングサイズｓ1，ｓ2と実行時間Ｔi,1を用いて、２番目の学習ステップの実行時間ｔi,2＝ｓ2／ｓ1×Ｔi,1と推定する。時間推定部１３３は、推定した実行時間ｔi,2を出力する。
【０１３０】
図１４は、性能改善量推定の手順例を示すフローチャートである。
（Ｓ５０）性能改善量推定部１３４は、学習制御部１３５から指定された機械学習アルゴリズムａiとステップ番号ｊ＋１とを特定する。
【０１３１】
（Ｓ５１）性能改善量推定部１３４は、管理テーブル１２２ａから機械学習アルゴリズムａiに対応する全ての予測性能ｐi,1，ｐi,2，…を検索する。
（Ｓ５２）性能改善量推定部１３４は、サンプリングサイズｓ1，ｓ2，…と予測性能ｐi,1，ｐi,2，…を用いて、サンプリングサイズｓから予測性能ｐを推定する推定式ｐ＝β−α×ｓ-rの係数α，β，γを決定する。係数α，β，γは、非線形回帰分析によってサンプリングサイズｓ1，ｓ2，…と予測性能ｐi,1，ｐi,2，…を上記の曲線にフィッティングすることで決定できる。また、性能改善量推定部１３４は、上記の曲線の９５％予測区間を算出する。なお、上記の曲線については、次の文献にも記載がある：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。
【０１３２】
（Ｓ５３）性能改善量推定部１３４は、上記の推定式の９５％予測区間とサンプリングサイズｓj+1を用いて、ｊ＋１番目の学習ステップの予測性能について９５％予測区間の上限値（ＵＣＢ）を算出し、推定上限値ｕとする。
【０１３３】
（Ｓ５４）性能改善量推定部１３４は、現在の達成予測性能Ｐと推定上限値ｕを比較して性能改善量ｇi,j+1を推定し、推定した性能改善量ｇi,j+1を出力する。性能改善量ｇi,j+1は、ｕ＞Ｐであればｕ−Ｐであり、ｕ≦Ｐであれば０である。
【０１３４】
第２の実施の形態の機械学習装置１００によれば、複数の機械学習アルゴリズムそれぞれについて、次の学習ステップを実行した場合の単位時間当たりの予測性能の改善量（改善速度）が推定される。そして、改善速度が最大の機械学習アルゴリズムが選択され、選択された機械学習アルゴリズムの学習ステップが１つだけ進められる。改善速度の推定と機械学習アルゴリズムの選択が繰り返され、最終的に１つのモデルが選択される。
【０１３５】
これにより、予測性能の改善に寄与しない学習ステップは実行されず、全体の学習時間を短縮することができる。また、改善速度の推定値が最大の機械学習アルゴリズムが選択されるため、学習時間に制限があり機械学習を途中で打ち切った場合であっても、終了時刻までに得られたモデルが、制限時間内に得られる最善のモデルとなる。また、少しでも予測性能の改善に寄与する学習ステップは、実行順序が後になる可能性はあるものの実行される余地が残される。このため、予測性能の上限が高い機械学習アルゴリズムをサンプリングサイズが小さいうちに切り捨ててしまうリスクを低減できる。このように、複数の機械学習アルゴリズムを利用してモデルの予測性能を効率的に向上させることができる。
【０１３６】
［第３の実施の形態］
次に、第３の実施の形態を説明する。第２の実施の形態との違いを中心に説明し、第２の実施の形態と同様の事項については説明を省略することがある。
【０１３７】
第２の実施の形態の機械学習装置１００は、サンプリングサイズｓと学習ステップの実行時間ｔとの間の関係を、一次式を用いて表した。これに対し、サンプリングサイズｓと実行時間ｔとの間の関係は、機械学習アルゴリズムによって大きく異なる可能性がある。例えば、機械学習アルゴリズムの中には、サンプリングサイズｓの増加に対して、実行時間ｔが直線的ではなく曲線的に増加するものもある。そこで、第３の実施の形態の機械学習装置は、機械学習アルゴリズムによって異なる推定式を用いて実行時間ｔを推定する。
【０１３８】
図１５は、第３の実施の形態の機械学習装置の機能例を示すブロック図である。
機械学習装置１００ａは、データ記憶部１２１、管理テーブル記憶部１２２、学習結果記憶部１２３、推定式記憶部１２４、制限時間入力部１３１、ステップ実行部１３２、性能改善量推定部１３４、学習制御部１３５および時間推定部１３６を有する。機械学習装置１００ａは、第２の実施の形態の時間推定部１３３に代えて時間推定部１３６を有している。推定式記憶部１２４は、例えば、ＲＡＭまたはＨＤＤに確保した記憶領域を用いて実現できる。時間推定部１３６は、例えば、ＣＰＵが実行するプログラムモジュールを用いて実現できる。なお、機械学習装置１００ａは、図２に示した第２の実施の形態の機械学習装置１００と同様のハードウェアを用いて実現できる。
【０１３９】
推定式記憶部１２４は、推定式テーブルを記憶する。推定式テーブルは、機械学習アルゴリズム毎に、サンプリングサイズｓと実行時間ｔとの間の関係を示す推定式を記憶する。機械学習アルゴリズム毎の推定式は、予めユーザによって決定されている。例えば、ユーザが事前に、幾つかの異なるサイズの訓練データを用いて各機械学習アルゴリズムを試行して、実行時間を計測しておく。そして、ユーザが事前に、非線形回帰などの統計処理によって、サンプリングサイズと実行時間から推定式を決定する。
【０１４０】
時間推定部１３６は、推定式記憶部１２４に記憶された推定式テーブルを参照して、ある機械学習アルゴリズムの次の学習ステップの実行時間を推定する。時間推定部１３６は、学習制御部１３５から、機械学習アルゴリズムとステップ番号の指定を受け付ける。すると、時間推定部１３６は、推定式テーブルから、指定された機械学習アルゴリズムに対応する推定式を検索する。時間推定部１３６は、指定されたステップ番号に対応するサンプリングサイズと検索した推定式とから、指定されたステップ番号の学習ステップの実行時間を推定し、推定した実行時間を学習制御部１３５に出力する。
【０１４１】
ここで、実行時間の増加曲線は、機械学習アルゴリズムに加えて、プロセッサ能力・メモリ容量・キャッシュ容量などのハードウェア性能、機械学習を行うプログラムの実装方法、機械学習に用いるデータの性質など、各種の実行環境にも依存する。そこで、時間推定部１３６は、推定式テーブルに記憶された推定式をそのまま使用するのではなく、その推定式に対して補正係数を適用することとする。すなわち、時間推定部１３６は、実行済みの学習ステップについて、実行時間の実績と推定式によって算出される推定値とを比較することで、推定式に対して適用する補正係数を算出する。
【０１４２】
図１６は、推定式テーブルの例を示す図である。
推定式テーブル１２４ａは、推定式記憶部１２４に記憶されている。推定式テーブル１２４ａは、アルゴリズムＩＤと推定式の項目を有する。
【０１４３】
アルゴリズムＩＤは、機械学習アルゴリズムを識別する。推定式の項目には、機械学習アルゴリズム毎の推定式が登録される。各推定式は、サンプリングサイズｓを引数として使用する。前述のように、時間推定部１３６によって後で補正係数が算出されるため、推定式は推定式全体に係る係数を含まなくてよい。以下の説明では、機械学習アルゴリズムａiに対応する推定式をｆi（ｓ）と表記することがある。
【０１４４】
一例として、機械学習アルゴリズムＡに対応する推定式はｆ1（ｓ）＝ｓ×ｌｏｇ  ｓ、機械学習アルゴリズムＢに対応する推定式はｆ2（ｓ）＝ｓ2、機械学習アルゴリズムＣに対応する推定式はｆ3（ｓ）＝ｓ3となる。このように、機械学習アルゴリズムの中には、実行時間の増加曲線が直線（一次式）よりも著しく急峻になるものがある。
【０１４５】
図１７は、時間推定の他の手順例を示すフローチャートである。
（Ｓ６０）時間推定部１３６は、学習制御部１３５から指定された機械学習アルゴリズムａiとステップ番号ｊ＋１とを特定する。
【０１４６】
（Ｓ６１）時間推定部１３６は、推定式テーブル１２４ａから機械学習アルゴリズムａiに対応する推定式ｆi（ｓ）を検索する。
（Ｓ６２）時間推定部１３６は、管理テーブル１２２ａから機械学習アルゴリズムａiに対応する全ての実行時間Ｔi,1，Ｔi,2，…を検索する。
【０１４７】
（Ｓ６３）時間推定部１３６は、サンプリングサイズｓ1，ｓ2，…と実行時間Ｔi,1，Ｔi,2，…と推定式ｆi（ｓ）を用いて、推定式ｆi（ｓ）に乗算する補正係数ｃを算出する。例えば、時間推定部１３６は、ｃ＝ｓｕｍ（Ｔi）／ｓｕｍ（ｆi（ｓ））とする。ｓｕｍ（Ｔi）は、実行時間の実績値であるＴi,1，Ｔi,2，…を合計した値である。ｓｕｍ（ｆi（ｓ））は、補正前の推定値であるｆi（ｓ1），ｆi（ｓ2），…を合計した値である。補正前の推定値は、推定式にサンプリングサイズを代入することで算出できる。すなわち、補正係数ｃは、補正前の推定値に対する実績値の比を表す。
【０１４８】
（Ｓ６４）時間推定部１３６は、推定式ｆi（ｓ）と補正係数ｃとサンプリングサイズｓj+1を用いて、ｊ＋１番目の学習ステップの実行時間ｔi,j+1を推定する。具体的には、ｔi,j+1＝ｃ×ｆi（ｓj+1）のように算出する。時間推定部１３６は、推定した実行時間ｔi,j+1を出力する。
【０１４９】
第３の実施の形態の機械学習装置１００ａによれば、第２の実施の形態の機械学習装置１００と同様の効果が得られる。更に、第３の実施の形態では、次の学習ステップの実行時間の推定精度が向上する。その結果、予測性能の改善速度の推定精度が向上し、改善速度の小さい機械学習アルゴリズムを誤って選択するリスクが低減する。よって、予測性能の高いモデルを一層短い学習時間で取得することができる。
【０１５０】
［第４の実施の形態］
次に、第４の実施の形態を説明する。第２の実施の形態との違いを中心に説明し、第２の実施の形態と同様の事項については説明を省略することがある。
【０１５１】
各機械学習アルゴリズムは、その動作を制御するための１または２以上のハイパーパラメータをもつことが多い。ハイパーパラメータは、モデルに含まれる係数（パラメータ）と異なり、機械学習を通じて値が決定されるものではなく、機械学習アルゴリズムの実行前に値が与えられるものである。ハイパーパラメータの例として、ランダムフォレストにおける決定木の生成本数、回帰分析のフィッティング精度、モデルに含まれる多項式の次数などが挙げられる。ハイパーパラメータの値として、固定値が使用されることもあるし、ユーザから指定された値が使用されることもある。
【０１５２】
ただし、モデルの予測性能は、ハイパーパラメータの値にも依存する。機械学習アルゴリズムとサンプリングサイズが同じでも、ハイパーパラメータの値が変わるとモデルの予測性能も変化し得る。予測性能が最大化になるハイパーパラメータの値が、事前にはわからないことも多い。そこで、第４の実施の形態では、機械学習全体を通じてハイパーバラメータを自動的に調整できるようにする。以下では、一の機械学習アルゴリズムに適用するハイパーパラメータの集合を「ハイパーパラメータベクトル」と言うことがある。
【０１５３】
図１８は、第４の実施の形態の機械学習装置の機能例を示すブロック図である。
機械学習装置１００ｂは、データ記憶部１２１、管理テーブル記憶部１２２、学習結果記憶部１２３、制限時間入力部１３１、時間推定部１３３、性能改善量推定部１３４、学習制御部１３５、ハイパーパラメータ調整部１３７およびステップ実行部１３８を有する。機械学習装置１００ｂは、第２の実施の形態のステップ実行部１３２に代えてステップ実行部１３８を有している。ハイパーパラメータ調整部１３７およびステップ実行部１３８は、例えば、ＣＰＵが実行するプログラムモジュールを用いて実現できる。なお、機械学習装置１００ｂは、図２に示した第２の実施の形態の機械学習装置１００と同様のハードウェアを用いて実現できる。
【０１５４】
ハイパーパラメータ調整部１３７は、ステップ実行部１３８からの要求に応じて、ステップ実行部１３８が実行しようとする機械学習アルゴリズムに適用するハイパーパラメータベクトルを生成する。ハイパーパラメータベクトルの生成方法として、グリッドサーチやランダムサーチを利用することができる。また、ハイパーパラメータベクトルの生成方法として、ガウス過程を用いる方法やＳＭＡＣ、ＴＰＥを利用することもできる。
【０１５５】
ガウス過程を用いる方法については、例えば、次の非特許文献に記載されている。Jasper Snoek, Hugo Larochelle and Ryan P. Adams, "Practical Bayesian Optimization of Machine Learning Algorithms", In Advances in Neural Information Processing Systems 25 (NIPS '12), pp. 2951-2959, 2012。ＳＭＡＣについては、例えば、次の非特許文献に記載されている。Frank Hutter, Holger H. Hoos and Kevin Leyton-Brown, "Sequential Model-Based Optimization for General Algorithm Configuration", In Lecture Notes in Computer Science, Vol. 6683 of Learning and Intelligent Optimization, pp. 507-523. Springer, 2011。ＴＰＥについては、例えば、次の非特許文献に記載されている。James Bergstra, Remi Bardenet, Yoshua Bengio and Balazs Kegl, "Algorithms for Hyper-Parameter Optimization", In Advances in Neural Information Processing Systems 24 (NIPS '11), pp. 2546-2554, 2011。
【０１５６】
また、ハイパーパラメータ調整部１３７は、同じ機械学習アルゴリズムの前の学習ステップで使用したハイパーパラメータベクトルを参照して、好ましいハイパーパラメータベクトルの探索を効率化することもできる。例えば、ハイパーパラメータ調整部１３７は、１つ前の学習ステップで最良の予測性能が得られたハイパーパラメータベクトルθj-1から始めて、探索を行うことが考えられる。この方法については、例えば、次の非特許文献に記載されている。Matthias Feurer, Jost Tobias Springenberg and Frank Hutter, "Initializing Bayesian Hyperparameter Optimization via Meta-Learning", In Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15), pp. 1128-1135, 2015。
【０１５７】
また、１つ前の学習ステップで最良の予測性能が得られたハイパーパラメータベクトルをθj-1、２つ前の学習ステップで最良の予測性能が得られたハイパーパラメータベクトルをθj-2とする。ハイパーパラメータ調整部１３７は、２θj-1−θj-2を、今回使用するハイパーパラメータベクトルとして生成することも考えられる。これは、最良の予測性能が得られるハイパーパラメータベクトルは、サンプリングサイズの変化に合わせて変化していると仮定したものである。また、ハイパーパラメータ調整部１３７は、１つ前のステップで平均以上の予測性能が得られたハイパーパラメータベクトルとその近傍のハイパーパラメータベクトルを、今回使用するものとして生成することも考えられる。
【０１５８】
ステップ実行部１３８は、学習制御部１３５から、機械学習アルゴリズムとサンプリングサイズの指定を受け付ける。すると、ステップ実行部１３８は、ハイパーパラメータ調整部１３７に要求してハイパーパラメータベクトルを取得する。ステップ実行部１３８は、データ記憶部１２１に記憶されたデータと取得したハイパーパラメータベクトルを用いて、指定された機械学習アルゴリズムおよび指定されたサンプリングサイズについての学習ステップを実行する。ステップ実行部１３８は、１つの学習ステップの中で、異なる複数のハイパーパラメータベクトルを用いた機械学習を繰り返す。
【０１５９】
そして、ステップ実行部１３８は、複数のハイパーパラメータベクトルに対応する複数のモデルの中から、予測性能が最良のモデルを選択する。ステップ実行部１３８は、選択したモデルと、そのモデルについての予測性能と、そのモデルの生成に使用したハイパーパラメータベクトルと、実行時間を出力する。実行時間は、１つの学習ステップ全体の時間（複数のハイパーパラメータベクトルについての総時間）でもよいし、選択したモデルの学習に要した時間（１つのハイパーパラメータベクトルについての時間）でもよい。なお、学習結果記憶部１２３に記憶される学習結果には、モデル、予測性能、機械学習アルゴリズムおよびサンプリングサイズに加えて、ハイパーパラメータベクトルが含まれる。
【０１６０】
図１９は、第４の実施の形態のステップ実行の手順例を示すフローチャートである。
（Ｓ７０）ステップ実行部１３８は、学習制御部１３５から指定された機械学習アルゴリズムａiとサンプリングサイズｓjとを特定する。また、ステップ実行部１３８は、データ記憶部１２１に記憶されているデータ集合Ｄを特定する。
【０１６１】
（Ｓ７１）ステップ実行部１３８は、次に使用するハイパーパラメータベクトルをハイパーパラメータ調整部１３７に要求する。ハイパーパラメータ調整部１３７は、前述のような方法によってハイパーパラメータベクトルθhを決定する。
【０１６２】
（Ｓ７２）ステップ実行部１３８は、サンプリングサイズｓjが、データ集合Ｄのサイズの２／３よりも大きいか判断する。サンプリングサイズｓjが２／３×｜Ｄ｜よりも大きい場合、ステップＳ７９に処理が進む。サンプリングサイズｓjが２／３×｜Ｄ｜以下である場合、ステップＳ７３に処理が進む。
【０１６３】
（Ｓ７３）ステップ実行部１３８は、データ集合Ｄからサンプリングサイズｓjの訓練データＤtをランダムに抽出する。
（Ｓ７４）ステップ実行部１３８は、データ集合Ｄのうち訓練データＤtを除いた部分から、サイズｓj／２のテストデータＤsをランダムに抽出する。
【０１６４】
（Ｓ７５）ステップ実行部１３８は、機械学習アルゴリズムａiとハイパーパラメータベクトルθhと訓練データＤtとを用いてモデルｍを学習する。
（Ｓ７６）ステップ実行部１３８は、学習したモデルｍとテストデータＤsとを用いて、モデルｍの予測性能ｐを算出する。
【０１６５】
（Ｓ７７）ステップ実行部１３８は、上記ステップＳ７３〜Ｓ７６の繰り返し回数と閾値Ｋとを比較し、前者が後者未満であるか判断する。例えば、閾値Ｋ＝１０とする。繰り返し回数が閾値Ｋ未満の場合はステップＳ７３に処理が進み、繰り返し回数が閾値Ｋに達した場合はステップＳ７８に処理が進む。
【０１６６】
（Ｓ７８）ステップ実行部１３８は、ステップＳ７６で算出されたＫ個の予測性能ｐの平均値を、ハイパーパラメータベクトルθhに対応する予測性能ｐhとして算出する。また、ステップ実行部１３８は、ステップＳ７５で学習されたＫ個のモデルｍのうち予測性能ｐが最大のモデルを、ハイパーパラメータベクトルθhに対応するモデルｍhと判定する。そして、ステップＳ８０に処理が進む。
【０１６７】
（Ｓ７９）ステップ実行部１３８は、上記のランダムサブサンプリングバリデーションに代えて、クロスバリデーションを実行する。そして、ステップＳ８０に処理が進む。
（Ｓ８０）ステップ実行部１３８は、ステップＳ７１〜Ｓ７９の繰り返し回数と閾値Ｈとを比較し、前者が後者未満であるか判断する。繰り返し回数が閾値Ｈ未満の場合はステップＳ７１に処理が進み、繰り返し回数が閾値Ｈに達した場合はステップＳ８１に処理が進む。なお、ｈ＝１，２，…，Ｈである。Ｈは所定数であり、例えば、Ｈ＝３０とする。
【０１６８】
（Ｓ８１）ステップ実行部１３８は、予測性能ｐ1，ｐ2，…，ｐHの中から、最大のものを予測性能ｐi,jとして出力する。また、ステップ実行部１３８は、モデルｍ1，ｍ2，…，ｍHの中から、予測性能ｐi,jに対応するモデルを出力する。また、ステップ実行部１３８は、ハイパーパラメータベクトルθ1，θ2，…，θHの中から、予測性能ｐi,jに対応するハイパーパラメータベクトルを出力する。また、ステップ実行部１３８は、実行時間を算出して出力する。実行時間は、ステップＳ７０〜Ｓ８１までの１つの学習ステップ全体の時間でもよいし、出力したモデルが得られたときのステップＳ７２〜Ｓ７９の時間でもよい。そして、１つの学習ステップが終了する。
【０１６９】
第４の実施の形態の機械学習装置１００ｂによれば、第２の実施の形態の機械学習装置１００と同様の効果が得られる。更に、第４の実施の形態では、ハイパーパラメータベクトルも可変とし、機械学習を通じてハイパーパラメータベクトルを最適化できる。これにより、モデルの予測性能を向上させることができる。
【０１７０】
［第５の実施の形態］
次に、第５の実施の形態を説明する。第２および第４の実施の形態との違いを中心に説明し、第２および第４の実施の形態と同様の事項については説明を省略することがある。
【０１７１】
１つの学習ステップにつき、多数のハイパーパラメータベクトルを使用して機械学習を繰り返すと、全体の実行時間が長くなってしまう。一方で、同じ機械学習アルゴリズムを実行しても、適用するハイパーパラメータベクトルによって実行時間が変わることがあるため、時間がかかる実行は制限時間を設けて打ち切りたい。しかし、実行時間が長くなるハイパーパラメータベクトルほど、モデルの予測性能が高くなる可能性がある。よって、ハイパーパラメータベクトル１つ当たりの機械学習に対して一律の打ち切り時間を設けると、高い予測性能をもつモデルを得る機会を見逃すリスクがある。
【０１７２】
そこで、第５の実施の形態では、ハイパーパラメータベクトルの集合を学習時間レベル（モデルを学習し終えるまでに要する時間のレベル）に応じて分割する。そして、学習時間レベルの異なるハイパーパラメータベクトルを使用した機械学習を、仮想的に異なる機械学習アルゴリズムとして取り扱うようにする。すなわち、機械学習アルゴリズムと学習時間レベルの組を、仮想アルゴリズムとして取り扱う。これにより、同じ機械学習アルゴリズムの中でも、学習時間レベルの大きいハイパーパラメータベクトルを使用した機械学習は実行の優先順位が低くなり、その完了を待たずに同一または異なる機械学習アルゴリズムの次の学習ステップに進むことができる。一方、学習時間レベルの大きいハイパーパラメータベクトルを使用した機械学習も、優先順位は低くなるものの後で実行される可能性があり、予測性能の向上に寄与する機会が残される。
【０１７３】
図２０は、ハイパーパラメータベクトル空間の例を示す図である。
ハイパーパラメータベクトルに含まれる２以上のハイパーパラメータそれぞれが取り得る値の範囲によって、ハイパーパラメータベクトル空間が形成される。図２０の例では、ハイパーパラメータベクトルに含まれるハイパーパラメータθ1，θ2によって、２次元のハイパーパラメータベクトル空間４０が形成されている。図２０の例では、ハイパーパラメータベクトル空間４０が、領域４１〜４４に分割されている。
【０１７４】
ここで、機械学習アルゴリズムａiとサンプリングサイズｓjと学習時間レベルｑに対して、打ち切り時間φqi,jとハイパーパラメータベクトル集合ΔΦqi,jが定義される。打ち切り時間φqi,jは、学習時間レベルｑが大きいほど大きくなる。ΔΦqi,jに属するハイパーパラメータベクトルは、サンプリングサイズｓjの訓練データを用いて機械学習アルゴリズムａiを実行した場合に、打ち切り時間φqi,j未満でモデル学習が終了したもの（ただし、それより小さい学習時間レベルに属するものを除く）である。
【０１７５】
領域４１〜４４は、サンプリングサイズｓ1の訓練データを用いて機械学習アルゴリズムａ1を実行した場合のハイパーパラメータベクトル空間４０の分割例である。領域４１は、ハイパーパラメータベクトル集合ΔΦ11,1、すなわち、学習時間レベル＃１に対応する。領域４１に属するハイパーパラメータベクトルは、例えば、０．０１秒未満でモデル学習が終了したものである。領域４２は、ハイパーパラメータベクトル集合ΔΦ21,1、すなわち、学習時間レベル＃２に対応する。領域４２に属するハイパーパラメータベクトルは、例えば、０．０１秒以上０．１秒未満でモデル学習が終了したものである。領域４３は、ハイパーパラメータベクトル集合ΔΦ31,1、すなわち、学習時間レベル＃３に対応する。領域４３に属するハイパーパラメータベクトルは、例えば、０．１秒以上１秒未満でモデル学習が終了したものである。領域４４は、ハイパーパラメータベクトル集合ΔΦ41,1、すなわち、学習時間レベル＃４に対応する。領域４４に属するハイパーパラメータベクトルは、例えば、１秒以上１０秒未満でモデル学習が終了したものである。
【０１７６】
図２１は、ハイパーパラメータベクトル集合の分割例を示す第１の図である。
テーブル５０は、サンプリングサイズｓjと学習時間レベルｑの組に対して、機械学習アルゴリズムａ1によって使用されるハイパーパラメータベクトルを示している。
【０１７７】
サンプリングサイズｓ1の学習時間レベル＃１では、ハイパーパラメータベクトル集合Φ11,1が使用される。Φ11,1は、ハイパーパラメータベクトル空間４０全体から領域の制限なしに抽出されたハイパーパラメータベクトルの集合である。Φ11,1のうち打ち切り時間φ11,1未満で終了したハイパーパラメータベクトルが、ΔΦ11,1に属する。サンプリングサイズｓ1の学習時間レベル＃２では、ハイパーパラメータベクトル集合Φ21,1が使用される。Φ21,1は、Φ11,1からΔΦ11,1を除いたもの、すなわち、サンプリングサイズｓ1の学習時間レベル＃１で打ち切られたハイパーパラメータベクトルの集合である。Φ21,1のうち打ち切り時間φ21,1未満で終了したハイパーパラメータベクトルが、ΔΦ21,1に属する。サンプリングサイズｓ1の学習時間レベル＃３では、ハイパーパラメータベクトル集合Φ31,1が使用される。Φ31,1は、Φ21,1からΔΦ21,1を除いたもの、すなわち、サンプリングサイズｓ1の学習時間レベル＃２で打ち切られたハイパーパラメータベクトルの集合である。
【０１７８】
サンプリングサイズｓ2の学習時間レベル＃１では、ハイパーパラメータベクトル集合Φ11,2が使用される。Φ11,2は、ΔΦ11,1、すなわち、サンプリングサイズｓ1の学習時間レベル＃１で打ち切られなかったハイパーパラメータベクトルの集合である。Φ11,2のうち打ち切り時間φ11,2未満で終了したハイパーパラメータベクトルが、ΔΦ11,2に属する。サンプリングサイズｓ2の学習時間レベル＃２では、ハイパーパラメータベクトル集合Φ21,2が使用される。Φ21,2は、Φ11,2からΔΦ11,2を除いたもの、すなわち、サンプリングサイズｓ2の学習時間レベル＃１で打ち切られたハイパーパラメータベクトルを含む。また、Φ21,2は、ΔΦ21,1、すなわち、サンプリングサイズｓ1の学習時間レベル＃２で打ち切られなかったハイパーパラメータベクトルを含む。Φ21,2のうち打ち切り時間φ21,2未満で終了したハイパーパラメータベクトルが、ΔΦ21,2に属する。サンプリングサイズｓ2の学習時間レベル＃３では、ハイパーパラメータベクトル集合Φ31,2が使用される。Φ31,2は、Φ21,2からΔΦ21,2を除いたもの、すなわち、サンプリングサイズｓ2の学習時間レベル＃２で打ち切られたハイパーパラメータベクトルを含む。また、Φ31,2は、ΔΦ31,1、すなわち、サンプリングサイズｓ1の学習時間レベル＃３で打ち切られなかったハイパーパラメータベクトルを含む。
【０１７９】
サンプリングサイズｓ3の学習時間レベル＃１では、ハイパーパラメータベクトル集合Φ11,3が使用される。Φ11,3は、ΔΦ11,2、すなわち、サンプリングサイズｓ2の学習時間レベル＃１で打ち切られなかったハイパーパラメータベクトルの集合である。Φ11,3のうち打ち切り時間φ11,3未満で終了したハイパーパラメータベクトルが、ΔΦ11,3に属する。サンプリングサイズｓ3の学習時間レベル＃２では、ハイパーパラメータベクトル集合Φ21,3が使用される。Φ21,3は、Φ11,3からΔΦ11,3を除いたもの、すなわち、サンプリングサイズｓ3の学習時間レベル＃１で打ち切られたハイパーパラメータベクトルを含む。また、Φ21,3は、ΔΦ21,2、すなわち、サンプリングサイズｓ2の学習時間レベル＃２で打ち切られなかったハイパーパラメータベクトルを含む。Φ21,3のうち打ち切り時間φ21,3未満で終了したハイパーパラメータベクトルが、ΔΦ21,3に属する。サンプリングサイズｓ3の学習時間レベル＃３では、ハイパーパラメータベクトル集合Φ31,3が使用される。Φ31,3は、Φ21,3からΔΦ21,3を除いたもの、すなわち、サンプリングサイズｓ3の学習時間レベル＃２で打ち切られたハイパーパラメータベクトルを含む。また、Φ31,3は、ΔΦ31,2、すなわち、サンプリングサイズｓ2の学習時間レベル＃３で打ち切られなかったハイパーパラメータベクトルを含む。
【０１８０】
このように、サンプリングサイズｓjの学習時間レベルｑで使用したハイパーパラメータベクトルのうち、打ち切り時間φq1,j未満でモデル学習が終了したものは、サンプリングサイズｓj+1の学習時間レベルｑに引き継がれる。一方、サンプリングサイズｓjの学習時間レベルｑで使用したハイパーパラメータベクトルのうち実行が打ち切られたものは、サンプリングサイズｓjの学習時間レベルｑ＋１に引き継がれる。
【０１８１】
図２２は、ハイパーパラメータベクトル集合の分割例を示す第２の図である。
テーブル５１は、Φ11,1に属するハイパーパラメータベクトル（θ1，θ2）とその実行結果（実行時間ｔおよび予測性能ｐ）の例を示している。テーブル５２は、Φ21,1に属するハイパーパラメータベクトル（θ1，θ2）とその実行結果の例を示している。テーブル５３は、Φ11,2に属するハイパーパラメータベクトル（θ1，θ2）とその実行結果の例を示している。テーブル５４は、Φ21,2に属するハイパーパラメータベクトル（θ1，θ2）とその実行結果の例を示している。
【０１８２】
テーブル５１（Φ11,1）は、ハイパーパラメータベクトルとして（０，３）、（４，２）、（１，５）、（−５，−１）、（２，３）、（−３，−２）、（−１，１）および（１．４，４．５）を含む。サンプリングサイズｓ1の学習時間レベル＃１では、（０，３）、（−５，−１）、（−３，−２）、（−１，１）および（１．４，４．５）が打ち切り時間内に終了し、（４，２）、（１，５）および（２，３）が終了せずに打ち切られている。そこで、打ち切られた（４，２）、（１，５）および（２，３）は、Φ21,1に引き継がれる。一方、打ち切られなかった（０，３）、（−５，−１）、（−３，−２）、（−１，１）および（１．４，４．５）は、Φ11,2に引き継がれる。
【０１８３】
テーブル５２に示すように、サンプリングサイズｓ1の学習時間レベル＃２では、（４，２）、（１，５）および（２，３）の全てが打ち切り時間内に終了している。そこで、打ち切られなかった（４，２）、（１，５）および（２，３）は、Φ21,2に引き継がれる。また、テーブル５３に示すように、サンプリングサイズｓ2の学習時間レベル＃１では、（０，３）、（−５，−１）、（−３，−２）および（−１，１）が打ち切り時間内に終了し、（１．４，４．５）が終了せずに打ち切られている。そこで、打ち切られた（１．４，４．５）は、Φ21,2に引き継がれる。
【０１８４】
テーブル５４に示すように、サンプリングサイズｓ2の学習時間レベル＃２では、（４，２）、（１，５）、（２，３）および（１．４，４．５）が使用される。このうち、（１，５）、（２，３）および（１．４，４．５）が打ち切り時間内に終了し、（４，２）が終了せずに打ち切られている。
【０１８５】
図２３は、第５の実施の形態の機械学習装置の機能例を示すブロック図である。
機械学習装置１００ｃは、データ記憶部１２１、管理テーブル記憶部１２２、学習結果記憶部１２３、制限時間入力部１３１、時間推定部１３３ｃ、性能改善量推定部１３４、学習制御部１３５ｃ、ハイパーパラメータ調整部１３７ｃ、ステップ実行部１３８ｃおよび探索領域決定部１３９を有する。探索領域決定部１３９は、例えば、ＣＰＵが実行するプログラムモジュールを用いて実現できる。なお、機械学習装置１００ｃは、図２に示した第２の実施の形態の機械学習装置１００と同様のハードウェアを用いて実現できる。
【０１８６】
探索領域決定部１３９は、学習制御部１３５ｃからの要求に応じて、次の学習ステップにおいて使用するハイパーパラメータベクトルの集合（探索領域）を決定する。探索領域決定部１３９は、学習制御部１３５ｃから、機械学習アルゴリズムａiとサンプリングサイズｓjと学習時間レベルｑの指定を受け付ける。探索領域決定部１３９は、前述のようにしてΦqi,jを決定する。すなわち、探索領域決定部１３９は、Φqi,j-1に含まれるハイパーパラメータベクトルのうちモデル学習が終了したものを、Φqi,jに追加する。また、探索領域決定部１３９は、サンプリングサイズｓjの学習時間レベルｑ−１が実行済みである場合、Φq-1i,jに含まれるハイパーパラメータベクトルのうちモデル学習が打ち切られて終了しなかったものを、Φqi,jに追加する。
【０１８７】
ただし、ｊ＝１かつｑ＝１である場合、探索領域決定部１３９は、ハイパーパラメータベクトル空間の中から、ランダムサーチやグリッドサーチなどによってできる限り多くのハイパーパラメータベクトルを選択し、Φ1i,1に追加する。
【０１８８】
管理テーブル記憶部１２２は、図９に示した管理テーブル１２２ａを記憶する。ただし、第５の実施の形態では、機械学習アルゴリズムと学習時間レベルの組を仮想アルゴリズムとして取り扱う。そこで、管理テーブル１２２ａには、機械学習アルゴリズムと学習時間レベルの組に対して、１つのレコードが登録される。
【０１８９】
時間推定部１３３ｃは、第２の実施の形態と同様に、学習制御部１３５ｃからの要求に応じて、一の機械学習アルゴリズムおよび一の学習時間レベルについて次の学習ステップ（次のサンプリングサイズ）の実行時間を推定する。更に、時間推定部１３３ｃは、一の機械学習アルゴリズムおよび一の学習時間レベルについて次のサンプリングサイズの打ち切り時間を推定する。機械学習アルゴリズムａi、サンプリングサイズｓj+1、学習時間レベルｑの打ち切り時間は、例えば、φqi,j+1＝γ×φqi,jによって算出できる。
【０１９０】
上記式の係数γは、第２の実施の形態で説明した実行時間を推定する式の係数αと同様の方法（回帰分析など）によって決定することができる。ただし、実行時間が短くなるハイパーパラメータベクトルを使用すると、モデルの予測性能が低くなる傾向にあり、実行時間が長くなるハイパーパラメータベクトルを使用すると、モデルの予測性能が高くなる傾向にある。そのため、モデル学習が終了したハイパーパラメータベクトルについての実行時間をそのまま回帰分析に用いると、打ち切り時間が過小に設定されて、予測性能の低いモデルが生成されやすくなるおそれがある。そこで、例えば、時間推定部１３３ｃは、モデル学習が終了したハイパーパラメータベクトルの実行時間のうち、予測性能が平均以上のものを抽出して回帰分析に使用することもできる。また、抽出した実行時間の最大値、平均値、中央値などを用いて回帰分析に使用することも考えられる。
【０１９１】
学習制御部１３５ｃは、機械学習アルゴリズムａiと学習時間レベルｑの組を、仮想アルゴリズムａqiと定義する。学習制御部１３５ｃは、次に実行する学習ステップの仮想アルゴリズムとサンプリングサイズを、第２の実施の形態と同様の方法で選択していく。また、学習制御部１３５ｃは、機械学習アルゴリズムａiのサンプリングサイズｓ1について、打ち切り時間φ1i,1，φ2i,1，…，φQi,1を決定する。Ｑは、学習時間レベルの最大値である。例えば、Ｑ＝５とする。この打ち切り時間は、複数の機械学習アルゴリズムの間で共通であってもよい。例えば、φ1i,1＝０．０１秒、φ2i,1＝０．１秒、φ3i,1＝１秒、φ4i,1＝１０秒、φ5i,1＝１００秒とする。サンプリングサイズｓ2以降の打ち切り時間は、時間推定部１３３ｃによって算出される。学習制御部１３５ｃは、機械学習アルゴリズムａi、サンプリングサイズｓj、探索領域決定部１３９が決定した探索領域（Φqi,j）および打ち切り時間φqi,jを、ステップ実行部１３８ｃに指定する。
【０１９２】
ハイパーパラメータ調整部１３７ｃは、ステップ実行部１３８ｃからの要求に応じて、学習制御部１３５ｃから指定された探索領域に含まれるハイパーパラメータベクトルまたは探索領域の近傍のハイパーパラメータベクトルを選択する。
【０１９３】
ステップ実行部１３８ｃは、第４の実施の形態と同様の方法で学習ステップを１つずつ実行する。ただし、あるハイパーパラメータベクトルを用いた機械学習を開始してから打ち切り時間φqi,jが経過した場合、ステップ実行部１３８ｃは、その機械学習が終了するのを待たずにその機械学習を打ち切る。この場合、当該ハイパーパラメータベクトルに対応するモデルは生成されない。また、当該ハイパーパラメータベクトルに対応する予測性能は、予測性能の指標値が取り得る最小値であるとみなされる。なお、１つの学習ステップにおいて使用するハイパーパラメータベクトルの数（閾値Ｈ）は、サンプリングサイズがｓ1以外の場合、例えば、Ｈ＝３０とする。サンプリングサイズがｓ1である場合、例えば、Ｈ＝Ｍａｘ（１００００／１０q-1，３０）とする。
【０１９４】
図２４は、第５の実施の形態の機械学習の手順例を示すフローチャートである。
（Ｓ１１０）学習制御部１３５ｃは、プログレッシブサンプリング法における学習ステップのサンプリングサイズｓ1，ｓ2，ｓ3，…を決定する。
【０１９５】
（Ｓ１１１）学習制御部１３５ｃは、学習時間レベルの最大値Ｑ（例えば、Ｑ＝５）を決定する。そして、学習制御部１３５ｃは、使用可能な機械学習アルゴリズムと学習時間レベルの組を、仮想アルゴリズムとして決定する。
【０１９６】
（Ｓ１１２）学習制御部１３５ｃは、サンプリングサイズｓ1に対する各仮想アルゴリズムの打ち切り時間を決定する。例えば、全ての機械学習アルゴリズムについて共通の値として、学習時間レベル＃１は０．０１秒、学習時間レベル＃２は０．１秒、学習時間レベル＃３は１秒、学習時間レベル＃４は１０秒、学習時間レベル＃５は１００秒とする。
【０１９７】
（Ｓ１１３）学習制御部１３５ｃは、各仮想アルゴリズムのステップ番号を１に初期化する。また、学習制御部１３５ｃは、各仮想アルゴリズムの改善速度を、改善速度が取り得る最大値に初期化する。また、学習制御部１３５ｃは、達成予測性能Ｐを、達成予測性能Ｐが取り得る最小値（例えば、０）に初期化する。
【０１９８】
（Ｓ１１４）学習制御部１３５ｃは、管理テーブル１２２ａの中から、改善速度が最大の仮想アルゴリズムを選択する。ここで選択した仮想アルゴリズムをａqiとする。
（Ｓ１１５）学習制御部１３５ｃは、仮想アルゴリズムａqiの改善速度ｒqiが、閾値Ｒ未満であるか判断する。例えば、閾値Ｒ＝０．００１／３６００［秒-1］とする。改善速度ｒqiが閾値Ｒ未満である場合はステップＳ１３２に処理が進み、それ以外の場合はステップＳ１１６に処理が進む。
【０１９９】
（Ｓ１１６）学習制御部１３５ｃは、管理テーブル１２２ａから、仮想アルゴリズムａqiに対応するステップ番号ｋqiを検索する。ここでは、ｋqi＝ｊであるとする。
（Ｓ１１７）探索領域決定部１３９は、仮想アルゴリズムａqi（機械学習アルゴリズムａiとが学習時間レベルｑの組）およびサンプリングサイズｓjに対応する探索領域を決定する。すなわち、探索領域決定部１３９は、前述の方法により、ハイパーパラメータベクトル集合Φqi,jを決定する。
【０２００】
（Ｓ１１８）ステップ実行部１３８ｃは、仮想アルゴリズムａqiについてｊ番目の学習ステップを実行する。すなわち、ハイパーパラメータ調整部１３７ｃは、ステップＳ１１７で決定された探索領域に含まれるハイパーパラメータベクトルまたはその近傍のハイパーパラメータベクトルを選択する。ステップ実行部１３８ｃは、選択されたハイパーパラメータベクトルを機械学習アルゴリズムａiに適用し、サンプリングサイズｓjの訓練データを用いてモデルを学習する。ただし、モデル学習を開始してから打ち切り時間φqi,jを経過すると、ステップ実行部１３８ｃは、そのハイパーパラメータベクトルについてのモデル学習を打ち切る。ステップ実行部１３８ｃは、以上を複数のハイパーパラメータベクトルについて繰り返す。ステップ実行部１３８ｃは、打ち切られなかった学習の結果から、モデルと予測性能ｐqi,jと実行時間Ｔqi,jとを決定する。
【０２０１】
（Ｓ１１９）学習制御部１３５ｃは、ステップ実行部１３８ｃから、学習されたモデルと当該モデルの予測性能ｐqi,jと実行時間Ｔqi,jとを取得する。
（Ｓ１２０）学習制御部１３５ｃは、ステップＳ１１９で取得した予測性能ｐqi,jと、達成予測性能Ｐ（現在までに達成された最大の予測性能）とを比較し、前者が後者より大きいか判断する。予測性能ｐqi,jが達成予測性能Ｐよりも大きい場合はステップＳ１２１に処理が進み、それ以外の場合はステップＳ１２２に処理が進む。
【０２０２】
（Ｓ１２１）学習制御部１３５ｃは、達成予測性能Ｐを予測性能ｐqi,jに更新する。また、学習制御部１３５ｃは、達成予測性能Ｐと対応付けて、その予測性能が得られた仮想アルゴリズムａqiとステップ番号ｊとを記憶しておく。
【０２０３】
図２５は、第５の実施の形態の機械学習の手順例を示すフローチャート（続き）である。
（Ｓ１２２）学習制御部１３５ｃは、管理テーブル１２２ａに記憶されたステップ番号のうち、仮想アルゴリズムａqiに対応するステップ番号ｋqiをｊ＋１に更新する。また、学習制御部１３５ｃは、合計時間ｔsum＝０に初期化する。
【０２０４】
（Ｓ１２３）学習制御部１３５ｃは、仮想アルゴリズムａqiの次の学習ステップのサンプリングサイズｓj+1を算出する。学習制御部１３５ｃは、サンプリングサイズｓj+1とデータ記憶部１２１に記憶されたデータ集合Ｄのサイズとを比較し、前者が後者より大きいか判断する。サンプリングサイズｓj+1がデータ集合Ｄのサイズよりも大きい場合はステップＳ１２４に処理が進み、それ以外の場合はステップＳ１２５に処理が進む。
【０２０５】
（Ｓ１２４）学習制御部１３５ｃは、管理テーブル１２２ａに記憶された改善速度のうち、仮想アルゴリズムａqiに対応する改善速度ｒqiを０に更新する。そして、前述のステップＳ１１４に処理が進む。
【０２０６】
（Ｓ１２５）学習制御部１３５ｃは、時間推定部１３３ｃに対して仮想アルゴリズムａqiとステップ番号ｊ＋１を指定する。時間推定部１３３ｃは、仮想アルゴリズムａqiについて次の学習ステップ（ｊ＋１番目の学習ステップ）を実行した場合の実行時間ｔqi,j+1を推定する。
【０２０７】
（Ｓ１２６）学習制御部１３５ｃは、仮想アルゴリズムａqiについて次の学習ステップ（ｊ＋１番目の学習ステップ）の打ち切り時間φqi,j+1を決定する。
（Ｓ１２７）学習制御部１３５ｃは、性能改善量推定部１３４に対して仮想アルゴリズムａqiとステップ番号ｊ＋１を指定する。性能改善量推定部１３４は、仮想アルゴリズムａqiについて次の学習ステップ（ｊ＋１番目の学習ステップ）を実行した場合の性能改善量ｇqi,j+1を推定する。
【０２０８】
（Ｓ１２８）学習制御部１３５ｃは、時間推定部１３３ｃから取得した実行時間ｔqi,j+1に基づいて、合計時間ｔsum＝ｔsum＋ｔqi,j+1に更新する。また、学習制御部１３５ｃは、更新した合計時間ｔsumと性能改善量推定部１３４から取得した性能改善量ｇqi,j+1とに基づいて、改善速度ｒqi＝ｇqi,j+1／ｔsumを算出する。学習制御部１３５ｃは、管理テーブル１２２ａに記憶された改善速度ｒqiを上記の値に更新する。
【０２０９】
（Ｓ１２９）学習制御部１３５ｃは、改善速度ｒqiが閾値Ｒ未満であるか判断する。改善速度ｒqiが閾値Ｒ未満の場合はステップＳ１３０に処理が進み、改善速度ｒqiが閾値Ｒ以上の場合はステップＳ１３１に処理が進む。
【０２１０】
（Ｓ１３０）学習制御部１３５ｃは、ｊ＝ｊ＋１に更新する。そして、ステップＳ１２３に処理が進む。
（Ｓ１３１）学習制御部１３５ｃは、機械学習を開始してからの経過時間が、制限時間入力部１３１から指定された制限時間を超えたか判断する。経過時間が制限時間を超えた場合はステップＳ１３２に処理が進み、それ以外の場合はステップＳ１１４に処理が進む。
【０２１１】
（Ｓ１３２）学習制御部１３５ｃは、達成予測性能Ｐと当該予測性能が得られたモデルとを学習結果記憶部１２３に保存する。また、学習制御部１３５ｃは、達成予測性能Ｐに対応付けられた機械学習アルゴリズムのアルゴリズムＩＤと、達成予測性能Ｐに対応付けられたステップ番号に相当するサンプリングサイズとを、学習結果記憶部１２３に保存する。また、学習制御部１３５ｃは、上記モデルの学習に用いたハイパーパラメータベクトルθを学習結果記憶部１２３に保存する。
【０２１２】
第５の実施の形態の機械学習装置１００ｃによれば、第２および第４の実施の形態と同様の効果が得られる。更に、第５の実施の形態では、学習時間レベルの大きいハイパーパラメータベクトルについては、機械学習が途中で打ち切られてその優先順位が低くなる。よって、全てのハイパーパラメータベクトルの機械学習が終了するのを待たずに、同一または異なる機械学習アルゴリズムの次の学習ステップに進むことができる。よって、学習ステップ１つ当たりの実行時間を短縮できる。また、学習時間レベルの大きいハイパーパラメータベクトルを使用した機械学習も後で実行される可能性がある。よって、予測性能の向上に寄与するハイパーパラメータベクトルを見逃すリスクを低減できる。
【０２１３】
なお、前述のように、第１の実施の形態の情報処理は、機械学習管理装置１０にプログラムを実行させることで実現できる。第２の実施の形態の情報処理は、機械学習装置１００にプログラムを実行させることで実現できる。第３の実施の形態の情報処理は、機械学習装置１００ａにプログラムを実行させることで実現できる。第４の実施の形態の情報処理は、機械学習装置１００ｂにプログラムを実行させることで実現できる。第５の実施の形態の情報処理は、機械学習装置１００ｃにプログラムを実行させることで実現できる。
【０２１４】
プログラムは、コンピュータ読み取り可能な記録媒体（例えば、記録媒体１１３）に記録しておくことができる。記録媒体として、例えば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。プログラムは、可搬型の記録媒体に記録されて配布されることがある。その場合、可搬型の記録媒体から他の記録媒体（例えば、ＨＤＤ１０３）にプログラムをコピーして実行してもよい。
【符号の説明】
【０２１５】
１０  機械学習管理装置
１１  記憶部
１２  演算部
１３ａ，１３ｂ，１３ｃ  機械学習アルゴリズム
１４ａ，１４ｂ，１４ｃ，１４ｄ  訓練データ
１５ａ，１５ｂ，１５ｃ  増加速度
【図１】
0006555015.tif 000002
【図２】
0006555015.tif 000003
【図３】
0006555015.tif 000004
【図４】
0006555015.tif 000005
【図５】
0006555015.tif 000006
【図６】
0006555015.tif 000007
【図７】
0006555015.tif 000008
【図８】
0006555015.tif 000009
【図９】
0006555015.tif 000010
【図１０】
0006555015.tif 000011
【図１１】
0006555015.tif 000012
【図１２】
0006555015.tif 000013
【図１３】
0006555015.tif 000014
【図１４】
0006555015.tif 000015
【図１５】
0006555015.tif 000016
【図１６】
0006555015.tif 000017
【図１７】
0006555015.tif 000018
【図１８】
0006555015.tif 000019
【図１９】
0006555015.tif 000020
【図２０】
0006555015.tif 000021
【図２１】
0006555015.tif 000022
【図２２】
0006555015.tif 000023
【図２３】
0006555015.tif 000024
【図２４】
0006555015.tif 000025
【図２５】
0006555015.tif 000026