(57)【要約】【課題】  MapReduceによる分散粒子群最適化アルゴリズムにおけるパラメータパターンの試行回数を、乱数を利用しない方法で低減する。【解決手段】  本発明は、前記プログラムに試行されるパラメータパターンを３個ずつにグループ化し、グループ単位に該プログラムを並列に実行した結果の品質スコアを取得し、パラメータパターンと前記品質スコアの関係に基づいて新たなパラメータを生成する。このとき、直前の試行で得られたグループ毎のn個のパラメータパターンの品質スコアと、変化させたパラメータ値から分類された傾向に基づいて、品質スコアが高まると想定されるパラメータパターンをグループ毎に決定する。【選択図】  図５
2014229040.tif 000002
【特許請求の範囲】
【請求項１】
複数の計算機でそれぞれ実行される複数のプログラムに必要な各種パラメータを最適化するため分散パラメータ最適化処理装置であって、
前記プログラムに試行されるパラメータパターンを３個ずつにグループ化し、グループ単位に該プログラムを並列に実行した結果の品質スコアを取得するグループ化手段と、
前記パラメータパターンと前記品質スコアの関係に基づいて新たなパラメータを生成するパラメータ生成手段と、
を有し、
前記パラメータ生成手段は、
直前の試行で得られたグループ毎のパラメータパターンの品質スコアと、変化させたパラメータ値から分類された傾向に基づいて、品質スコアが高まると想定されるパラメータパターンをグループ毎に決定する手段を含む
ことを特徴とする分散パラメータ最適化処理装置。
【請求項２】
前記パラメータ生成手段は、
前記品質スコアと入力されたパラメータ値に基づいて分類された傾向に基づいて、品質スコアが高まると予想されるパラメータパターンを生成する手段を含む
請求項１記載の分散パラメータ最適化処理装置。
【請求項３】
前記プログラムを試行する前に、
前記パラメータ生成手段で生成したパラメータのパターンが、試行済みのパラメータパターンを格納した試行済みパラメータパターンリストに含まれている場合には、プログラムの試行を行わないパターン衝突判定手段を更に有する請求項１記載の分散パラメータ最適化処理装置。
【請求項４】
複数の計算機でそれぞれ実行される複数のプログラムに必要な各種パラメータを最適化するため分散パラメータ最適化処理方法であって、
グループ化手段とパラメータ生成手段を有する装置において、
前記グループ化手段において、前記プログラムに試行されるパラメータパターンを３個ずつにグループ化し、グループ単位に該プログラムを並列に実行した結果の品質スコアを取得するグループ化ステップと、
前記パラメータ生成手段が、前記パラメータパターンと前記品質スコアの関係に基づいて新たなパラメータを生成するパラメータ生成ステップと、
を行い、
前記パラメータ生成ステップは、
直前の試行で得られたグループ毎のパラメータパターンの品質スコアと、変化させたパラメータ値から分類された傾向に基づいて、品質スコアが高まると想定されるパラメータパターンをグループ毎に決定する
ことを特徴とする分散パラメータ最適化処理方法。
【請求項５】
前記パラメータ生成ステップにおいて、
前記品質スコアと入力されたパラメータ値に基づいて分類された傾向に基づいて、品質スコアが高まると予想されるパラメータパターンを生成する
請求項４記載の分散パラメータ最適化処理方法。
【請求項６】
前記プログラムを試行する前に、
前記パラメータ生成手段で生成したパラメータのパターンが、試行済みのパラメータパターンを格納した試行済みパラメータパターンリストに含まれている場合には、プログラムの試行を行わないパターン衝突判定ステップを更に行う
請求項４記載の分散パラメータ最適化処理方法。
【請求項７】
コンピュータを、
請求項１乃至３のいずれか１項に記載の分散パラメータ最適化処理装置の各手段として機能させるための分散パラメータ最適化処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散パラメータ最適化処理装置及び方法及びプログラムに係り、特に、機械学習、音声認識、画像認識処理等を行う各種プログラムに必要な各種パラメータを最適化するための分散パラメータ最適化処理装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
機械学習・音声認識・画像認識処理などを行うためのプログラムには、実行前に入力データに加えて事前に与えるべきパラメータ（以降は「パラメータ」と呼ぶ）値があり、パラメータ値は処理結果の品質スコア（機械学習であれば学習結果として出力された分類器の分類精度，認識処理であれば認識精度など）に影響を及ぼす場合が多い。そのような処理結果の品質スコアを左右するパラメータ値を与える必要があるプログラムを利用する際、良い品質スコアの出力結果を得るためにはパラメータ値の最適化が求められる。
【０００３】
遺伝的アルゴリズムや粒子群最適化アルゴリズムなどのいわゆる最適化アルゴリズムを用いることによって、そのようなプログラムのパラメータを自動的に最適化することが可能である。最適化アルゴリズムでは、自動生成したパラメータパターンを対象となるプログラムに与え、その処理結果の品質スコアを評価して次のパラメータパターンを生成し再びプログラムに与えるということが繰り返され、詳細な最適値探索や局所最適を回避するために、大量のパラメータパターンが生成・試行されて、最終的に最適化されたパラメータパターンを得ることができる。しかし、そのような大量のパラメータをひとつの計算機で試行していると、非常に長い処理時間を要するという問題がある。
【０００４】
この問題に対して、分散処理フレームワークMapReduce（特許文献1）を利用して、パラメータの最適化を複数の計算機資源を用いて並列に行うことで、最適化処理を高速化するための方法が提案されている（例えば、非特許文献１参照）。
【０００５】
例として、非特許文献１の方法を利用し、音声認識プログラムにおけるパラメータを最適化する場合の例を示す。以下の例では、図１のように複数の計算機２１０がネットワーク２００に接続され、図２に示す構成を有する相互に通信可能な計算機２１０を用いてパラメータの最適化処理を行う。従来技術の例における論理構成を図３に示し、処理フローを図４に示す。
【０００６】
以下、図３、図４に基づいて説明する。
【０００７】
ステップ４００）  計算機２００−４の制御部３００がクラスタを構成する各計算機２２０−１，２２０−２，２２０−３に対して、パラメータ設定値メモリ３３０'に格納された、最適化をしたいパラメータの下限値及び上限値、入力データセットファイル３２０のデータ（音声ファイル）を配布する。
【０００８】
ステップ４１０）次に、制御部３００はMapReduceジョブを開始し、MapReduceジョブでは、はじめに各計算機２２０−１，２２０−２，２２０−３においてMapTaskが実行される。MapTaskでは複数のパラメータパターンを1グループとして生成される。具体的には、各パラメータパターン生成部３１０は、xをパラメータパターン（パラメータ値を並べたベクトル）、vをパラメータ値の移動量とし、パラメータ最適化処理においてそれまでにt回パラメータパターン生成を行なっていた場合、以下の式に従ってt+1回目の新しいパラメータパターン３３０を生成する。
【０００９】
【数１】
2014229040.tif 000003
φ1=φ２＝2.5，Κ=1.0，φ＝φ1+φ2であり、U( )は均一分散によりベクトルを乱数によってサンプリングしたもの、
【００１０】
【数２】
2014229040.tif 000004
はベクトルの要素同士を乗算することを示している。
【００１１】
ステップ４２０）各計算機２２０−１，２２０−２，２２０−３において、生成した新しいパラメータパターンと事前に与えられた入力データを用いてプログラムを実行し、その処理結果を評価して品質スコアを算出する。各計算機は各々のそれまでの最大品質スコアとその時のパラメータパターンを保持しており、新たに得られた品質スコアがそれまでの最大値を上回る場合はそれを更新する。
【００１２】
ステップ４３０）各計算機２２０−１，２２０−２，２２０−３の処理結果とその品質スコアを収集し、例えばユーザが与えた品質スコア閾値以上のスコアを持つ処理結果がある、もしくは繰り返し回数が一定値を超えているかどうかを判定する。判定が真の場合は、ステップ４４０に移行し、判定が偽の場合はステップ４１０に戻り、試行パラメータ値の生成・試行を繰り返す。
【００１３】
ステップ４４０）  ステップ４３０の判定が真の場合は、最適化処理を終了して、それまでの最良の品質スコアが得られたパラメータパターンと処理結果を出力する。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】System and method for efficient large-scale data processing [Google, 米国特許7650331, 2010年1月]
【非特許文献】
【００１５】
【非特許文献１】Parallel PSO Using MapReduce [Andrew W. McNabb, Christopher K. Monson, and Kevin D. Seppi, IEEE 2003]
【発明の概要】
【発明が解決しようとする課題】
【００１６】
非特許文献1の技術は、分散処理によって一度に多数のパラメータパターンを試行し、最も良い品質スコアとなる処理結果に寄与したパラメータパターンを選びとることによって、対象となるプログラムのパラメータ最適化を高速化するが、試行するパラメータパターンが乱数に基づいて生成されているため、大量のパラメータパターンを試行することが前提となっている。
【００１７】
しかしながら、対象となるプログラムの負荷が高く1パターンの試行にも長い処理時間を要する場合に大量のパラメータパターン試行してしまうと、最適化に非常に長い時間を要することになる。つまり、試行するパラメータパターンを低減可能な最適化アルゴリズムが求められている。
【００１８】
本発明は上記の点に鑑みなされたもので、MapReduceによる分散粒子群最適化アルゴリズムにおけるパラメータパターンの試行回数を、乱数を利用しない方法で低減し、特に対象となるプログラムそのものの負荷が高い場合にパラメータ最適化のための総処理時間を短縮することが可能な分散パラメータ最適化処理装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
上記の課題を解決するため、一態様によれば、複数の計算機でそれぞれ実行される複数のプログラムに必要な各種パラメータを最適化するため分散パラメータ最適化処理装置であって、
前記プログラムに試行されるパラメータパターンを３個ずつにグループ化し、グループ単位に該プログラムを並列に実行した結果の品質スコアを取得するグループ化手段と、
前記パラメータパターンと前記品質スコアの関係に基づいて新たなパラメータを生成するパラメータ生成手段と、
を有し、
前記パラメータ生成手段は、
直前の試行で得られたグループ毎の３個のパラメータパターンの品質スコアと、変化させたパラメータ値から分類された傾向に基づいて、品質スコアが高まると想定されるパラメータパターンをグループ毎に決定する手段を含む分散パラメータ最適化処理装置が適用される。
【発明の効果】
【００２０】
上記のように一態様によれば、品質スコア向上に寄与する可能性の高いパラメータパターンを、乱数ではない手段で生成することによって、既存技術 "Parallel PSO Using MapReduce"（非特許文献1）よりも少ない試行回数でパラメータの最適化を実施することが見込まれる。また、事前に与える各パラメータの初期値・移動幅・最大値・最小値・試行回数を調節することにより、最適化に要する時間を制御することも可能である。
【図面の簡単な説明】
【００２１】
【図１】従来技術における計算機の物理構成図である。
【図２】従来技術における計算機の構成図である。
【図３】従来技術における計算機の論理構成図である。
【図４】従来技術のフローチャートである。
【図５】本発明の一実施の形態におけるシステムの論理構成図である。
【図６】本発明の一実施の形態におけるパラメータパターン生成部のフローチャートである。
【図７】本発明の一実施の形態におけるパラメータパターンの生成例である。
【図８】本発明の効果を示す図である。
【発明を実施するための形態】
【００２２】
以下、図面と共に本発明の実施の形態を説明する。
【００２３】
まず、本発明の概要を説明する。
【００２４】
図５は、本発明の一実施の形態におけるシステムの論理構成図である。同図において図３と同一構成要素には同一符号を付し、その説明を省略する。
【００２５】
本発明は、従来技術 "Parallel PSO Using MapReduce"（非特許文献１）と同様にMapReduceフレームワークによって複数のパラメータパターンを用いたプログラムの実行を並行して実行する。
【００２６】
本発明では従来技術との差分として、分散パラメータ最適化処理装置５００として、並列に試行される複数のパラメータパターンのうち３つずつを1グループとして扱う制御部５０５と、1グループ内の３つのパラメータパターンからパラメータ値による処理結果の品質スコアへの影響の傾向を判断し、それを元に新しいパラメータパターンを自動的に生成するパラメータパターン生成部５１０と、試行済みパラメータパターンのリストを保持して試行済みパラメータパターンの再試行を回避するためのパターン衝突判定部５３０を有する。
【００２７】
本発明のパラメータパターン生成部５１０では、乱数に基づく方法よりも急峻に品質スコアを高めるパラメータパターンを生成することによって、本発明が対象とする条件下でパラメータ値を最適化するためのパラメータパターンの試行数を低減する効果を得る。
【００２８】
具体的には、複数のパラメータパターンをMapReduceによって並列に試行するが、複数種類のパラメータ（例えばパラメータa, パラメータb）がある場合はそのうちの1種類のみ（パラメータaのみ）の値を変化させる。制御部５０５が管理するグループにおいて３つのパラメータパターン（p1, p2, p3）から３つの品質スコア（s1, s2, s3）が得られる際に、その３つの品質スコアと変化させたパラメータ値を2次元座標にプロット（x座標はパラメータaの値、y座標は品質スコアsの値）して、3点が成す2本の線分の形を単調増加・減少、凸型増加・減少、凹型増加・減少の6種類の傾向に分類し、予めパラメータ毎に与えておいた移動量vを元に、パターン衝突判定部５３０によって試行済みパラメータパターンの重複回避を考慮しつつ、より品質スコアが高まると想定されるパラメータパターンをグループ毎に3パターン（p1', p2', p3'）自動的に決定する。そして各グループのパラメータパターンを再びMapReduceによって並列に試行する。これを予め与えておいた回数（n）繰り返すか、または変化させているパラメータの次に試行すべき値が予め与えた上限・下限の範囲（amax, amin）にはない場合には、値を変化させるパラメータを別のもの（パラメータb）に切り替えて同様に繰り返し、最終的に予め与えた回数（t）に達するか、予め与えたしきい値（S）を超える品質スコアが得られるパターンが発見されたとき、最適化を終了する。
【００２９】
以下に、従来技術との差異を示す。
【００３０】
従来技術の例とは制御部（図３の３００および図５の５０５）とパラメータパターン生成部（図３の３１０および図５の５１０）が異なる。本発明の実施の形態における制御部５０５はパラメータパターン3つを1グループとして管理する。また、パラメータパターン生成部５１０は複数の計算機（図５ ２１０−1〜２１０−3）において実行されるのではなく、MapReduce処理におけるReduceフェーズの後に、制御部５０５が実行される分類パラメータ最適化処理装置５００においてのみ実行される。また、試行済みパラメータパターンの再試行を回避するための、パターン衝突判定部５３０も、当該分類パラメータ最適化処理装置５００において実行され、パターン衝突判定部５３０は試行済みパラメータパターンリスト５４０を管理する。なお、試行済みパラメータパターンリスト５４０は、パターン衝突判定部５３０内のメモリ、または、その外部のファイル等の記憶手段に格納されているものとする。
【００３１】
本発明は主にパラメータパターン生成部５１０の機能が、従来技術と異なっている。当該パラメータパターン生成部５１０の動作を図６に示す。
【００３２】
パラメータパターン生成部５１０によるパラメータパターンの生成はグループ毎に行われ、ひとつのグループは、そのグループにおいて直前に実施されたパラメータパターンとその処理結果の品質スコアを3組、最適化すべきパラメータが複数種類ある場合は現在どのパラメータを変動させているのかを示す変数、そのパラメータを変動させている状態でMapReduceが実行された回数、過去にそのグループにおいて試行したパラメータパターンと品質スコア組のうち品質スコア上位3組を保持している。
【００３３】
ステップ６００）パラメータパターン生成部５１０は、パターン衝突判定部５３０に試行済みパラメータパターンリストが空かどうかを問い合わせる。試行済みパラメータパターンリストが空であった場合は、ステップ６１０に移行し、そうでない場合はステップ６２０に移行する。
【００３４】
ステップ６１０）ステップ６００の判定結果が真であった場合は、初回のパラメータ試行であるため、初期パラメータパターンを任意の方法でグループ毎に生成し、パタメータが複数種類ある場合は、どの順序でパラメータ値を変えるかを決定し、出力して、当該処理を終了する。
【００３５】
例えば、事前に与えられた初期パラメータ値と、そのパラメータ毎の移動量の倍数を加減した値3点を初期パラメータパターンとして利用可能であり、パラメータ値を変える順序は一度初期パラメータパターンを利用してMapReduceによって品質スコアを取得し、パラメータ値の変動が品質スコアに寄与する割合が大きい順序とすることができる。
【００３６】
ステップ６２０）ステップ６００の判定結果が偽であった場合は、グループ毎に直前のMapReduceによって得られた、グループ毎の３つのパラメータパターン（p1, p2, p3）から３つの品質スコア（s1, s2, s3）を入力し、その3つの品質スコアと変化させたパラメータ値を2次元座標にプロット（x座標はパラメータaの値，y座標は品質スコアsの値）して、3点が成す2本の線分の形を図７のように単調増加（図７の１．）・減少（図７の４．）、凸型増加（図７の２．）・減少（図７の６．）、凹型増加（図７の３．）・減少（図７の５．）の６種類の傾向に分類し、パラメータ設定値メモリ３３０'の予めパラメータ毎に与えておいた移動量（v）を元に、図７のように、より品質スコアが高まると想定されるパラメータパターンをグループ毎に3パターン（p1', p2', p3'）を決定する。
【００３７】
また、現在の値を変動させているパラメータにおいてMapReduceが実行された回数が事前に与えた閾値に達している場合はその回数を0に戻し、値を変動させるパラメータを切り替えて、過去に得られた品質スコア上位３件のパラメータパターンを直前のMapReduceによって得られた3つのパラメータパターンとして上記と同様に次に試行すべきパラメータパターンを生成する。
【００３８】
ステップ６３０）ステップ６２０にてグループ毎に生成された3つのパラメータパターンが、パターン衝突判定部５３０によってグループ間で同じパラメータパターンがないか、もしくは試行済みパラメータパターンに含まれていないかを判定する。以降の処理はすべてグループ毎に実施される。判定結果が真の場合はステップ６４０に移行し、偽の場合は当該処理を終了する。
【００３９】
ステップ６４０）ステップ６３０にて衝突するパラメータパターンがある場合に、その時点で値を変動させているパラメータの上限値・下限値の範囲内に他に取りうる値があるかどうか判定する。取り得る値がある場合はステップ６５０に移行し、ない場合はステップ６６０に移行する。
【００４０】
ステップ６５０）ステップ６４０にて他に取りうる値がある場合は、現在変動させているパラメータの移動量を半減させてステップ６２０と同様の方法でパラメータパターンの再生成を行う。パラメータ毎の上限値や下限値を超える場合は超えない方向のパラメータパターンを生成する。（例えばステップ６２０で生成された3パターンのうち、1パターンが下限値を下回った場合はそのパターンを破棄し，3パターンのうちの最大値＋移動量の値をとるパターンを加える）
ステップ６６０）空のパラメータパターンを出力して、その時点で値を変動させているパラメータの試行を終える。パラメータが複数種類ある場合に、値を変動させるパラメータを切り替える。
【００４１】
図８に、上記の実施の形態で示した分散パラメータ最適化処理装置を実装し、音声認識プログラムのパラメータ最適化に適用した場合に、各グループにおいて、MapReduceジョブ毎において生成されたパラメータパターンを音声認識プログラムに適用した場合の処理結果の品質スコアをプロットしたものである。
【００４２】
３つのグループそれぞれの品質スコアはMapReduceジョブ毎に増加傾向にあることが分かり、20回目のMapReduceまでにほぼ品質スコアの最大値に達しているため、60パターン以下の試行回数でパラメータの最適化を達成していると考えられる。
【００４３】
なお、本発明は、図５に示す分散パラメータ最適化処理装置５００の構成要素の動作をプログラムとして構築し、分散パラメータ最適化処理装置として利用されるコンピュータにインストールして実行させる、または、ネットワーク介して流通させることが可能である。
【００４４】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００４５】
２２０  計算機
３３０  パラメータパターン
３３０'  パラメータ設定値メモリ
３３０"  最適化パラメータパターン
３４０  音声認識部
３５０  認識結果テキスト
３５０'  認識結果テキスト
３６０  出力結果評価部
３７０  品質スコア（認識率）
３８０  終了判定部
５００  分散パラメータ最適化処理装置
５０５  制御部
５１０  パラメータパターン生成部
５３０  パラーン衝突判定部
５４０  試行済みパラメータパターンリスト
【図１】
2014229040.tif 000005
【図２】
2014229040.tif 000006
【図３】
2014229040.tif 000007
【図４】
2014229040.tif 000008
【図５】
2014229040.tif 000009
【図６】
2014229040.tif 000010
【図７】
2014229040.tif 000011
【図８】
2014229040.tif 000012