(57)【要約】  作業集合選択装置１０は、最適化の対象の複数のパラメータにそれぞれ対応する各特徴量をソートするソート部１１と、ソートされた各特徴量のうち最初の特徴量から昇順に並んだ最初の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合、または最後の特徴量から降順に並んだ最後の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合を、部分的に最適化が行われるパラメータの集合である作業集合として選択する選択部１２とを備える。
2020129149.tif 000002
【特許請求の範囲】
【請求項１】
最適化の対象の複数のパラメータにそれぞれ対応する各特徴量をソートするソート部と、
ソートされた各特徴量のうち最初の特徴量から昇順に並んだ前記最初の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合、または最後の特徴量から降順に並んだ前記最後の特徴量を含む前記所定の数の特徴量にそれぞれ対応するパラメータの集合を、部分的に最適化が行われるパラメータの集合である作業集合として選択する選択部とを備える
ことを特徴とする作業集合選択装置。
【請求項２】
複数のパラメータにそれぞれ対応する各特徴量を変換するか否かを所定の条件に従ってそれぞれ判定する判定部と、
変換すると判定された特徴量を所定の変換関数を用いて変換する変換部とを備える
請求項１記載の作業集合選択装置。
【請求項３】
ソート部は、変換された特徴量を含む各特徴量をソートする
請求項２記載の作業集合選択装置。
【請求項４】
各特徴量の代表値を決定する決定部を備える
請求項１から請求項３のうちのいずれか１項に記載の作業集合選択装置。
【請求項５】
パラメータが所定の集合に所属するか否かを複数のパラメータそれぞれに対して判定する所属判定部を備える
請求項１から請求項４のうちのいずれか１項に記載の作業集合選択装置。
【請求項６】
最適化は、サポートベクトルマシンにより行われる
請求項１から請求項５のうちのいずれか１項に記載の作業集合選択装置。
【請求項７】
最適化の対象の複数のパラメータにそれぞれ対応する各特徴量をソートし、
ソートされた各特徴量のうち最初の特徴量から昇順に並んだ前記最初の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合、または最後の特徴量から降順に並んだ前記最後の特徴量を含む前記所定の数の特徴量にそれぞれ対応するパラメータの集合を、部分的に最適化が行われるパラメータの集合である作業集合として選択する
ことを特徴とする作業集合選択方法。
【請求項８】
複数のパラメータにそれぞれ対応する各特徴量を変換するか否かを所定の条件に従ってそれぞれ判定し、
変換すると判定された特徴量を所定の変換関数を用いて変換する
請求項７記載の作業集合選択方法。
【請求項９】
コンピュータに、
最適化の対象の複数のパラメータにそれぞれ対応する各特徴量をソートするソート処理、および
ソートされた各特徴量のうち最初の特徴量から昇順に並んだ前記最初の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合、または最後の特徴量から降順に並んだ前記最後の特徴量を含む前記所定の数の特徴量にそれぞれ対応するパラメータの集合を、部分的に最適化が行われるパラメータの集合である作業集合として選択する選択処理
を実行させるための作業集合選択プログラム。
【請求項１０】
コンピュータに、
複数のパラメータにそれぞれ対応する各特徴量を変換するか否かを所定の条件に従ってそれぞれ判定する判定処理、および
変換すると判定された特徴量を所定の変換関数を用いて変換する変換処理を実行させる
請求項９記載の作業集合選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、作業集合選択装置、作業集合選択方法および作業集合選択プログラムに関し、特にサポートベクトルマシンによる最適化に用いられる作業集合を選択できる作業集合選択装置、作業集合選択方法および作業集合選択プログラムに関する。
【背景技術】
【０００２】
機械学習は、データから定められる評価関数の値を最小にするようなパラメータの値を探索する最適化問題の一種である。以下、機械学習における最適化を、単に「学習」とも呼ぶ。【０００３】
有用な機械学習アルゴリズムとして、サポートベクトルマシン(Support Vector Machine;SVM)が挙げられる。SVM は、広く使われている機械学習アルゴリズムである。SVM は、カーネルという特殊な関数を用いてデータの特徴を変換した上で学習を行う。【０００４】
非線形カーネルを用いるSVM による代表的な最適化手法に、SMO(Sequential Minimum Optimization)がある。SMO は、データのサンプルの数だけパラメータを最適化する。すなわち、最適化されるパラメータの数は、データのサンプルの数と等しい。よって、データのサンプルが増えると、SVM による学習に係る時間も長くなる。【０００５】
また、SVM による学習では、多数のパラメータから構成される評価関数の値が最小化されることが多い。評価関数を構成するパラメータの数は、例えば100,000 以上である。【０００６】
例えば、非特許文献１に記載されているcovtype と呼ばれるデータセットのサンプル数は、400,000 程度である。よって、学習にcovtype を用いる場合、SMO は、学習を完了させるまでに多くの時間を要する。【０００７】
SVM による学習に係る時間を短縮するために、並列計算機が用いられる並列処理を学習に導入する方法が考えられる。例えば、SVM をベクトルコンピュータで高速化することが考えられる。【０００８】
ベクトルコンピュータは、同一の演算を複数のデータに対して並列に実行し、高速に処理する計算機である。図１３は、ベクトルコンピュータによる演算の例を示す説明図である。【０００９】
例えば、ベクトルコンピュータは、配列A[0:256]中の１つの要素の値と、配列B[0:256]中の対応する１つの要素の値とを加算する。次いで、ベクトルコンピュータは、２つの要素の値の和を配列C[0:256]中の対応する１つの要素に書き込む。ベクトルコンピュータは、加算処理および書き込み処理を、各要素に対して並列に実行する。【００１０】
また、非特許文献２には、SVM による学習処理を、高い並列処理能力を有するGPU(Graphical Processing Unit)を用いて行うThundersvmが記載されている。【００１１】
図１４は、SVM による学習処理の例を示す説明図である。SVM による学習処理には、図１４に示す作業集合（図１４に示す斜線模様の楕円、サイズM ）の選択処理が含まれる。作業集合の選択処理は、SVM による最適化の対象であるパラメータ全体（図１４に示す白色の楕円、サイズN ）から、所定の数（M ）のパラメータを作業集合として選択する処理である。【００１２】
作業集合を選択した後、SVM は、選択された作業集合に所属するパラメータに対して部分的な最適化を行う。部分的な最適化は、作業集合に所属しないパラメータの値は固定し、作業集合に所属するパラメータの値のみ変動させることによって評価関数の値を最小にする処理である。【００１３】
１つの作業集合に対する部分的な最適化が終了した後、SVM は、他の作業集合の選択処理を行う。作業集合の選択処理と、選択された作業集合に対する部分的な最適化を繰り返すことによって、SVM は、パラメータ全体に対する最適化を実行する。【００１４】
図１４に示す学習処理を行う理由は、機械学習における最適化対象のパラメータが多いためである。SVM は、パラメータ全体から作業集合（例えば、1024個程度のパラメータ）を選択して部分的な最適化を行う学習処理を、パラメータ全体が収束する、すなわち各パラメータの値がそれぞれ最適値に至るまで繰り返し実行する。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】"UCI Machine Learning Repository: Covertype Data Set" 、[online]、UCI Machine Learning Repository 、[平成30年10月15日検索]、インターネット<https://archive.ics.uci.edu/ml/datasets/covertype>
【非特許文献２】"GitHub - Xtra-Computing/thundersvm: ThunderSVM: A Fast SVM Library on GPUs and CPUs" 、[online]、GitHub、[平成30年10月15日検索]、インターネット<https://github.com/Xtra-Computing/thundersvm>
【発明の概要】
【発明が解決しようとする課題】
【００１６】
最適化に要する計算のステップ数は、作業集合の選択方法に依存する。例えば、収束するまでの計算のステップは、パラメータ全体から作業集合をランダムに選択する場合よりも、特定の指標に基づいてパラメータ全体から作業集合を選択する場合の方が少ない。すなわち、特定の指標に基づいてパラメータ全体から作業集合を選択する技術が求められている。【００１７】
そこで、本発明は、上述した課題を解決する、特定の指標に基づいてパラメータ全体から作業集合を選択できる作業集合選択装置、作業集合選択方法および作業集合選択プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明による作業集合選択装置は、最適化の対象の複数のパラメータにそれぞれ対応する各特徴量をソートするソート部と、ソートされた各特徴量のうち最初の特徴量から昇順に並んだ最初の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合、または最後の特徴量から降順に並んだ最後の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合を、部分的に最適化が行われるパラメータの集合である作業集合として選択する選択部とを備えることを特徴とする。【００１９】
本発明による作業集合選択方法は、最適化の対象の複数のパラメータにそれぞれ対応する各特徴量をソートし、ソートされた各特徴量のうち最初の特徴量から昇順に並んだ最初の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合、または最後の特徴量から降順に並んだ最後の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合を、部分的に最適化が行われるパラメータの集合である作業集合として選択することを特徴とする。【００２０】
本発明による作業集合選択プログラムは、コンピュータに、最適化の対象の複数のパラメータにそれぞれ対応する各特徴量をソートするソート処理、およびソートされた各特徴量のうち最初の特徴量から昇順に並んだ最初の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合、または最後の特徴量から降順に並んだ最後の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合を、部分的に最適化が行われるパラメータの集合である作業集合として選択する選択処理を実行させることを特徴とする。
【発明の効果】
【００２１】
本発明によれば、特定の指標に基づいてパラメータ全体から作業集合を選択できる。
【図面の簡単な説明】
【００２２】
【図１】本発明による作業集合選択装置の第１の実施形態の構成例を示すブロック図である。
【図２】第１の実施形態の作業集合選択装置１００による作業集合選択処理の動作を示すフローチャートである。
【図３】本発明による作業集合選択装置の第２の実施形態の構成例を示すブロック図である。
【図４】上集合I_upと下集合I_low に所属するパラメータに対応する特徴量の例を示す説明図である。
【図５】上集合I_upと下集合I_low に所属するパラメータに対応する特徴量の選択例を示す説明図である。
【図６】上集合I_upと下集合I_low に所属するパラメータに対応する特徴量の選択アルゴリズムの例を示す説明図である。
【図７】上集合I_up、下集合I_low 、および集合I_0 に所属するパラメータに対応する特徴量の例を示す説明図である。
【図８】上集合I_up、下集合I_low 、および集合I_0 に所属するパラメータに対応する特徴量の他の例を示す説明図である。
【図９】上集合I_up、下集合I_low 、および集合I_0 に所属するパラメータに対応する特徴量の他の例を示す説明図である。
【図１０】第２の実施形態の作業集合選択装置２００による作業集合選択処理の動作を示すフローチャートである。
【図１１】本発明による作業集合選択装置のハードウェア構成例を示す説明図である。
【図１２】本発明による作業集合選択装置の概要を示すブロック図である。
【図１３】ベクトルコンピュータによる演算の例を示す説明図である。
【図１４】SVM による学習処理の例を示す説明図である。
【発明を実施するための形態】
【００２３】
以下、本発明の実施形態を、図面を参照して説明する。
【００２４】
各実施形態を説明する前に、説明に要する記法や概念を導入する。各実施形態では、パラメータ全体の数をN 、作業集合として選択されるパラメータの数（作業集合のサイズ）をM とそれぞれする。
【００２５】
また、N 個のパラメータの各値をまとめてa[1:N]と記載する。a[1:N]のi 番目の要素は、a[i]である。また、N 個のパラメータそれぞれに対応している特徴量をまとめてf[1:N]と記載する。f[1:N]のi 番目の要素は、f[i]である。なお、特徴量は、学習の途中で変化する量である。
【００２６】
なお、パラメータの値および特徴量以外のN 個の要素も、[1:N] の表記を用いてまとめて表す場合がある。
【００２７】
また、作業集合S を、作業集合S に所属するパラメータのインデックスの集合として表す。また、パラメータ全体の集合をS0とする。すなわち、S0 = {1,2,3,・・・,N} である。
【００２８】
実施形態１．
［構成の説明］
本発明による作業集合選択装置の第１の実施形態を、図面を参照して説明する。図１は、本発明による作業集合選択装置の第１の実施形態の構成例を示すブロック図である。図１に示すように、作業集合選択装置１００は、特徴量変換判定部１１０と、特徴量変換部１２０と、ソート部１３０と、選択部１４０とを備える。
【００２９】
作業集合選択装置１００は、パラメータの値a[1:N]と、特徴量f[1:N]と、作業集合のサイズM とを入力として受け取る。受け取った入力に対して、作業集合選択装置１００は、パラメータ全体のうちのM 個のパラメータが所属する作業集合S を出力として返す。
【００３０】
特徴量変換判定部１１０は、全てのパラメータに対して独立に、各パラメータに対応しているそれぞれの特徴量を変換するか否かを判定する機能を有する。特徴量変換判定部１１０は、パラメータの値a[1:N]および特徴量f[1:N]を入力として受け取り、N 個の真偽値が代入された配列bf[1:N] を出力として返す。
【００３１】
配列bf[1:N] のi 番目の要素bf[i] は、i 番目のパラメータ（以下、パラメータi と呼ぶ。）の値a[i]と、パラメータi に対応している特徴量f[i]とで決定される。要素bf[i] に代入された真偽値は、真(True)であれば特徴量f[i]を変換し、偽(False )であれば特徴量f[i]を変換しないことを意味する。
【００３２】
特徴量変換部１２０は、特徴量変換判定部１１０の出力に基づいて、パラメータごとに独立に特徴量を変換する機能を有する。特徴量を変換する理由は、作業集合を選択する処理を並列化するためである。
【００３３】
特徴量変換部１２０は、入力としてパラメータの値a[1:N]と、特徴量f[1:N]と、特徴量変換判定部１１０の出力bf[1:N] とを受け取り、変換後の特徴量が代入された配列xf[1:N] を出力として返す。
【００３４】
例えば、特徴量変換部１２０は、特徴量変換関数を保持する。特徴量変換関数は、パラメータj の値a[j]と特徴量f[j]とを受け取り、変換後の特徴量を返す。
【００３５】
特徴量変換部１２０は、パラメータi に関して、要素bf[i] に代入された真偽値が真であればパラメータの値a[i]と特徴量f[i]とを特徴量変換関数に入力する。次いで、特徴量変換部１２０は、特徴量変換関数の出力を要素xf[i] に代入する。また、特徴量変換部１２０は、要素bf[i] に代入された真偽値が偽であれば、特徴量f[i]をそのまま要素xf[i] に代入する。
【００３６】
ソート部１３０は、特徴量変換部１２０が出力した変換後の特徴量を含む各特徴量を、変換後の特徴量の昇順、または変換後の特徴量の降順にソートする機能を有する。具体的には、ソート部１３０は、特徴量変換部１２０の出力である配列xf[1:N] を入力として受け取る。次いで、ソート部１３０は、配列xf[1:N] の値をキーとして、配列xf[1:N] をソートする。
【００３７】
次いで、ソート部１３０は、ソート後のキー（変換後の特徴量）の配列をsxf[1:N]、ソート後のインデックス（パラメータの番号）の配列をsid[1:N]とそれぞれする。すなわち、xf、sxf 、sid に関して、sxf[i] = xf[sid[i]] という関係が成り立つ。ソート部１３０は、ソート後のキーの配列sxf[1:N]と、ソート後のインデックスの配列sid[1:N]とを出力として返す。
【００３８】
選択部１４０は、ソートされた変換後の特徴量の配列の最初の要素から所定の数の特徴量に対応するパラメータを選択する機能を有する。具体的には、選択部１４０は、ソート部１３０の出力である配列sxf[1:N]と配列sid[1:N]とを入力として受け取る。
【００３９】
次いで、選択部１４０は、配列sid[1:N]の１番目の要素からＭ番目までの要素、すなわち配列sid[1:M]を選択する。次いで、選択部１４０は、選択された配列sid[1:M]を作業集合S として出力する。なお、選択部１４０は、配列sid[1:N]のＮ番目の要素から所定の数だけ降順に要素を選択してもよい。
【００４０】
［動作の説明］
以下、本実施形態の作業集合選択装置１００の作業集合を選択する動作を図２を参照して説明する。図２は、第１の実施形態の作業集合選択装置１００による作業集合選択処理の動作を示すフローチャートである。
【００４１】
最初に、特徴量変換判定部１１０は、パラメータの値a[1:N]および特徴量f[1:N]を入力として受け取る。特徴量変換判定部１１０は、パラメータの値a[1:N]および特徴量f[1:N]に基づいて、各特徴量を変換するか否かをそれぞれ判定する（ステップS101）。
【００４２】
次いで、特徴量変換判定部１１０は、各判定結果を基に配列bf[1:N] の各要素に真偽値をそれぞれ代入する。次いで、特徴量変換判定部１１０は、N 個の真偽値が代入された配列bf[1:N] を特徴量変換部１２０に入力する。
【００４３】
次いで、特徴量変換部１２０は、パラメータの値a[1:N]および特徴量f[1:N]を入力として受け取る。次いで、特徴量変換部１２０は、特徴量変換判定部１１０から入力された配列bf[1:N] に基づいて、特徴量変換関数を用いて特徴量を変換する（ステップS102）。
【００４４】
具体的には、特徴量変換部１２０は、要素bf[i] に代入された真偽値が真であるパラメータi の値a[i]と特徴量f[i]とを特徴量変換関数に入力する。次いで、特徴量変換部１２０は、特徴量変換関数の出力を要素xf[i] に代入する。また、特徴量変換部１２０は、要素bf[i] に代入された真偽値が偽であるパラメータi の特徴量f[i]をそのまま要素xf[i] に代入する。
【００４５】
上記のように、特徴量変換部１２０は、配列xf[1:N] の各要素に特徴量をそれぞれ代入する。次いで、特徴量変換部１２０は、変換後の特徴量を含むN 個の特徴量が代入された配列xf[1:N] をソート部１３０に入力する。
【００４６】
次いで、ソート部１３０は、N 個の特徴量が代入された配列xf[1:N] を入力として受け取る。次いで、ソート部１３０は、変換後の特徴量を含む各特徴量をソートする（ステップS103）。具体的には、ソート部１３０は、配列xf[1:N] の値をキーとして、配列xf[1:N] をソートする。ソート部１３０は、配列xf[1:N] を昇順にソートしてもよいし、降順にソートしてもよい。
【００４７】
次いで、ソート部１３０は、配列sxf[1:N]の各要素にソート後のキーをそれぞれ代入する。また、ソート部１３０は、配列sid[1:N]の各要素にソート後のインデックスをそれぞれ代入する。次いで、ソート部１３０は、N 個のキーが代入された配列sxf[1:N]と、N 個のインデックスが代入された配列sid[1:N]を選択部１４０に入力する。
【００４８】
次いで、選択部１４０は、配列sxf[1:N]および配列sid[1:N]を入力として受け取る。次いで、選択部１４０は、ソート後の各特徴量（キー）から特徴量を昇順に選択する（ステップS104）。
【００４９】
次いで、選択部１４０は、選択された特徴量に対応するパラメータを作業集合S として出力する（ステップS105）。具体的には、選択部１４０は、配列sid[1:N]の１番目の要素からＭ番目までの要素、すなわち配列sid[1:M]を選択する。
【００５０】
次いで、選択部１４０は、選択された配列sid[1:M]を作業集合S として出力する。出力した後、作業集合選択装置１００は、作業集合選択処理を終了する。
【００５１】
なお、ステップS104〜ステップS105で、選択部１４０は、ソート後の各特徴量（キー）から特徴量を降順に選択し、選択された特徴量に対応するパラメータを作業集合S として出力してもよい。具体的には、選択部１４０は、配列sid[1:N]のＮ番目の要素から（Ｎ−（Ｍ−１））番目までの要素、すなわち配列sid[N-(M-1):N]を選択してもよい。
【００５２】
［効果の説明］
本実施形態の作業集合選択装置１００の選択部１４０は、ソート後の各特徴量から昇順または降順に選択された特徴量に対応するパラメータを作業集合に含めるという基準で作業集合を選択する。よって、作業集合選択装置１００は、特定の指標に基づいてパラメータ全体から作業集合を選択できる。
【００５３】
また、本実施形態の作業集合選択装置１００の特徴量変換判定部１１０は、特徴量の変換の有無の判定をパラメータごとに独立に行う。同様に、特徴量変換部１２０は、特徴量の変換をパラメータごとに独立に行う。
【００５４】
また、ソート部１３０によるソート処理は、既存の技術において並列に実行可能なことが知られている。また、選択部１４０によるソート済み配列からの要素の選択処理も、並列に実行可能である。従って、本実施形態の作業集合選択装置１００は、SVM による学習処理において、作業集合の選択処理を並列化できる。
【００５５】
実施形態２．
［構成の説明］
次に、本発明による作業集合選択装置の第２の実施形態を、図面を参照して説明する。図３は、本発明による作業集合選択装置の第２の実施形態の構成例を示すブロック図である。
【００５６】
図３に示すように、本実施形態の作業集合選択装置２００は、パラメータ所属判定部２１０と、バイアス決定部２２０と、特徴量変換判定部２３０と、特徴量変換部２４０と、ソート部２５０と、選択部２６０とを備える。
【００５７】
作業集合選択装置２００は、第１の実施形態と同様に、パラメータの値a[1:N]と、特徴量f[1:N]と、作業集合のサイズM とを入力として受け取る。受け取った入力に対して、作業集合選択装置２００は、パラメータ全体のうちのM 個のパラメータが所属する作業集合S を出力として返す。
【００５８】
本実施形態においてそれぞれのパラメータは、上集合I_upと下集合I_low の少なくとも１つの集合に所属する。上集合I_upと下集合I_low は、SVM による学習処理に関わる集合である。パラメータi が上集合I_up、下集合I_low に所属するか否かは、SVM が自動で決定する。
【００５９】
また、上集合I_upと下集合I_low の両方に所属するパラメータも存在する。すなわち、上集合I_upと下集合I_low の和集合は、パラメータ全体の集合S0に相当する。
【００６０】
また、上集合I_upと下集合I_low の共通部分は、一般的に空集合ではない。以下、上集合I_upと下集合I_low の共通部分をI_0 とする。
【００６１】
なお、一般的なSVM のアルゴリズムでは、作業集合の選択とパラメータの更新が交互に繰り返される。パラメータが変化すると、変化したパラメータが上集合I_up、下集合I_low に所属するか否かも変化する。すなわち、作業集合の選択処理ごとに、上集合I_upに所属するパラメータ、下集合I_low に所属するパラメータが変化する。
【００６２】
図４は、上集合I_upと下集合I_low に所属するパラメータに対応する特徴量の例を示す説明図である。図４は、選択される作業集合のサイズM が10である例を示す。
【００６３】
図４に示す上集合I_up中の縦線は、上集合I_upに所属するパラメータに対応する特徴量を表す。また、図４に示す下集合I_low 中の縦線は、下集合I_low に所属するパラメータに対応する特徴量を表す。また、図４に示す上集合I_upおよび下集合I_low 中の二重線は、上集合I_upと下集合I_low の両方に所属するパラメータに対応する特徴量を表す。
【００６４】
以下、本実施形態において、最適化に要する計算のステップ数を定める作業集合の選択方法を説明する。図５は、上集合I_upと下集合I_low に所属するパラメータに対応する特徴量の選択例を示す説明図である。
【００６５】
図５に示すように、上集合I_up中の特徴量f[i]が小さい方から、および下集合I_low 中の特徴量f[i]が大きい方から、M/2 個ずつ対応するパラメータを選択することによってサイズM の作業集合を選択すると、収束するまでのステップ数が比較的小さいことが知られている。図５に示す選択方法は、上集合I_upに関して小さい方から１つずつ、下集合I_low に関して大きい方から１つずつ、特徴量をそれぞれ同時に確認する。
【００６６】
次いで、選択方法は、確認された特徴量に対応するパラメータが作業集合に追加されていなければ、パラメータを作業集合に追加する。追加した後、選択方法は、パラメータが作業集合に追加されたことを表す目印を、対応する特徴量に付する。図５に示す「×」が、パラメータが作業集合に追加されたことを表す目印である。
【００６７】
パラメータが作業集合に追加されたことを表す目印を付する理由は、図４および図５に示すように、上集合I_upと下集合I_low の両方に所属するパラメータがある。よって、上集合I_up からの選択、または下集合I_low からの選択のいずれにおいても、両方に所属するパラメータが既に作業集合として選択されたか否かを逐次的に確認しないと、両方に所属するパラメータが重複して作業集合に格納される可能性があるためである。
【００６８】
図６は、上集合I_upと下集合I_low に所属するパラメータに対応する特徴量の選択アルゴリズムの例を示す説明図である。図６に示す選択アルゴリズムは、上述した選択処理を実行するためのアルゴリズムである。なお、図６に示す、パラメータが作業集合に追加されたことを表す配列selected[idx_up]の要素は、パラメータ全体の数（N 個）だけ求められる。
【００６９】
従って、図５および図６に示す選択方法が使用される場合、所定の精度に至るまでのステップ数を変えずに作業集合の選択処理を並列化することは困難である。図５および図６に示す選択方法を使用せずに、パラメータ全体から作業集合に含まれるパラメータを、パラメータの値等を考慮しないでランダムに選択すれば、作業集合の選択処理が並列化される。
【００７０】
しかし、パラメータをランダムに選択する方法では所定の精度に至るまでのステップが多くなるため、SVM による学習処理に係る時間が長くなる。本実施形態の作業集合選択装置２００は、図５および図６に示す選択方法が使用される場合であっても、所定の精度に至るまでのステップ数を大きく変えずに作業集合の選択処理を並列化することを主な目的とする。
【００７１】
パラメータ所属判定部２１０は、各パラメータが上集合I_upと下集合I_low に所属しているか否かを判定する機能を有する。
【００７２】
パラメータ所属判定部２１０は、例えばパラメータi に対して、パラメータi の値a[i]と、パラメータi に対応する特徴量f[i]とを入力とする所定の関数を用いて、要素is_I_up[i]に代入される真偽値と、要素is_I_low[i] に代入される真偽値をそれぞれ決定する。
【００７３】
要素is_I_up[i] に代入される真偽値が真であるとき、パラメータi は、上集合I_upに所属する。また、要素is_I_up[i] に代入される真偽値が偽であるとき、パラメータi は、上集合I_upに所属しない。
【００７４】
同様に、要素is_I_low[i] に代入される真偽値が真であるとき、パラメータi は、下集合I_low に所属する。また、要素is_I_low[i] に代入される真偽値が偽であるとき、パラメータi は、下集合I_low に所属しない。
【００７５】
パラメータ所属判定部２１０は、各パラメータに対して、２つの要素に代入される真偽値をそれぞれ決定する。パラメータ所属判定部２１０は、決定されたN 個の真偽値が代入された配列is_I_up[1:N]と、決定されたN 個の真偽値が代入された配列is_I_low[1:N] とを出力として返す。
【００７６】
図７は、上集合I_up、下集合I_low 、および集合I_0 に所属するパラメータに対応する特徴量の例を示す説明図である。図７に示すI_up-I_0は、上集合I_upに所属していて下集合I_lowに所属していないパラメータに対応する特徴量の集合である。
【００７７】
また、図７に示すI_low-I_0 は、下集合I_low に所属していて上集合I_upに所属していないパラメータに対応する特徴量の集合である。また、図７に示す２つの楕円内の特徴量は、作業集合に含めるパラメータに対応する特徴量である。
【００７８】
バイアス決定部２２０は、パラメータが所属している集合に基づいて、特徴量f[1:N]の代表値であるバイアスを決定する機能を有する。バイアスは、集合I_0 に所属するパラメータに対応する特徴量f[I_0]の中間的な値である。なお、パラメータ全体に対応する特徴量f[1:N]のうち、集合X に所属するパラメータに限定した特徴量の配列をf[X]と表す。
【００７９】
バイアス決定部２２０は、パラメータ所属判定部２１０の出力である配列is_I_up[1:N]および配列is_I_low[1:N] を入力として、集合I_0 を抽出する。次いで、バイアス決定部２２０は、抽出された集合I_0 を基に、バイアスb を決定する。バイアスb の決定方法は、複数存在する。以下、決定方法の例を説明する。
【００８０】
１つ目の決定方法は、f[I_0]の平均値をバイアスb とする方法である。平均値をバイアスb とする場合、バイアス決定部２２０は、最初に変数sum 、変数count をそれぞれ０に初期化する。
【００８１】
次いで、バイアス決定部２２０は、各パラメータに対して要素is_I_up[i]が真、かつ要素is_I_low[i] が真であるか否かをそれぞれ判定する。バイアス決定部２２０は、両方の真偽値が真であるパラメータi の特徴量f[i]を変数sum に加算する。また、バイアス決定部２２０は、変数count に１を加算する。
【００８２】
全てのパラメータに関して判定と加算を終えた後、バイアス決定部２２０は、変数sum を変数count で割った商をバイアスb とする。
【００８３】
図８は、上集合I_up、下集合I_low 、および集合I_0 に所属するパラメータに対応する特徴量の他の例を示す説明図である。図８に示すバイアスb は、集合I_0 を基に、１つ目の決定方法で得られたバイアスである。
【００８４】
２つ目の決定方法は、f[I_0]の最大値と最小値の中間値をバイアスb とする方法である。中間値をバイアスb とする場合、バイアス決定部２２０は、最初にf[I_0]をソートする。
【００８５】
次いで、バイアス決定部２２０は、ソート後の配列の最初の要素の値と最後の要素の値（最大値と最小値）の和を２で割った商をバイアスb とする。なお、バイアスb の決定方法は、上記の例に限定されない。
【００８６】
特徴量変換判定部２３０は、全てのパラメータに対して独立に、各パラメータに対応しているそれぞれの特徴量を変換するか否かを判定する機能を有する。特徴量変換判定部２３０は、パラメータ所属判定部２１０の出力である配列is_I_up[1:N]および配列is_I_low[1:N] と、バイアス決定部２２０の出力であるバイアスb とを入力として受け取る。
【００８７】
特徴量変換判定部２３０は、各パラメータに対応している特徴量を変換するか否かをそれぞれ表すN 個の真偽値が代入された配列bf[1:N] を出力として返す。
【００８８】
特徴量変換判定部２３０は、パラメータi に関して、例えば条件Ａが満たされたとき要素bf[i] に代入される真偽値を真とし、条件Ａが満たされないとき要素bf[i] に代入される真偽値を偽とする。条件Ａは、（（is_I_low[i] ==  真）または（is_I_low[i] ==  真  かつ  is_I_up[i] == 真  かつ  f[i] > b））である。
【００８９】
図９は、上集合I_up、下集合I_low 、および集合I_0 に所属するパラメータに対応する特徴量の他の例を示す説明図である。図９（ａ）に示す下集合I_low に相当する太枠が、条件Ａ中の（is_I_low[i] ==  真）を満たすパラメータに対応する特徴量の集合を表す。
【００９０】
また、図９（ａ）に示す集合I_0 中の太枠が、条件Ａ中の（is_I_low[i] ==  真  かつ  is_I_up[i] == 真  かつ  f[i] > b）を満たすパラメータに対応する特徴量の集合を表す。すなわち、集合I_0 中の太枠が表す特徴量の集合は、集合I_0 に含まれ、かつ、特徴量がバイアスb よりも大きいパラメータの集合に対応する。
【００９１】
特徴量変換部２４０は、特徴量変換判定部２３０の出力に基づいて、全てのパラメータに対して独立に、所定の条件に従って特徴量を変換する機能を有する。特徴量変換部２４０は、特徴量変換判定部２３０の出力bf[1:N] とバイアス決定部２２０の出力であるバイアスb とを入力として受け取り、変換後の特徴量を含むN 個の特徴量が代入された配列xf[1:N] を出力として返す。
【００９２】
特徴量変換部２４０は、要素bf[i] に代入された真偽値が真であるパラメータi に関して、特徴量f[i]がバイアスb に対して反転された値（2*b - f[i]）を要素xf[i] に代入する。また、特徴量変換部２４０は、要素bf[i] に代入された真偽値が偽であるパラメータi に関して、特徴量f[i]をそのまま要素xf[i] に代入する。
【００９３】
図９（ｂ）に示すように、条件Ａを満たした各パラメータに対応する特徴量の集合が、バイアスb に対して反転されている。図９（ｂ）に示す上から３つ目の太枠は、図９（ａ）に示す集合I_0 中の太枠が表す特徴量の集合が反転された集合を表す。また、図９（ｂ）に示す上から４つ目の矩形は、図９（ａ）に示す下集合I_low に所属するパラメータに対応する特徴量の集合が反転された集合を表す。
【００９４】
ソート部２５０は、特徴量変換部２４０が出力した変換後の特徴量を含む各特徴量を、変換後の特徴量の昇順、または変換後の特徴量の降順にソートする機能を有する。すなわち、ソート部２５０が有する機能は、第１の実施形態のソート部１３０が有する機能と同様である。
【００９５】
選択部２６０は、ソートされた変換後の特徴量の配列の最初の要素から所定の数の特徴量に対応するパラメータを選択する機能を有する。すなわち、選択部２６０が有する機能は、第１の実施形態の選択部１４０が有する機能と同様である。
【００９６】
図９（ｂ）に示す楕円内の上から１つ目の矩形が表す特徴量と上から４つ目の矩形が表す特徴量とを小さい方から並列に確認しても、選択部２６０は、同一の特徴量を確認する可能性が低い。その理由は、各特徴量の順番がソート部２５０により一意に定められるためである。よって、選択部２６０は、作業集合の選択処理を並列に実行できる。
【００９７】
［動作の説明］
以下、本実施形態の作業集合選択装置２００の作業集合を選択する動作を図１０を参照して説明する。図１０は、第２の実施形態の作業集合選択装置２００による作業集合選択処理の動作を示すフローチャートである。
【００９８】
最初に、パラメータ所属判定部２１０は、パラメータの値a[1:N]および特徴量f[1:N]を入力として受け取る。パラメータ所属判定部２１０は、パラメータの値a[1:N]および特徴量f[1:N]に基づいて、各パラメータが上集合I_up、下集合I_low に所属するか否かをそれぞれ判定する（ステップS201）。
【００９９】
次いで、パラメータ所属判定部２１０は、各判定結果を基に配列is_I_up[1:N]の各要素に真偽値をそれぞれ代入する。また、パラメータ所属判定部２１０は、各判定結果を基に配列is_I_low[1:N] の各要素に真偽値をそれぞれ代入する。次いで、パラメータ所属判定部２１０は、N 個の真偽値が代入された配列is_I_up[1:N]、およびN 個の真偽値が代入された配列is_I_low[1:N] を、バイアス決定部２２０と特徴量変換判定部２３０に入力する。
【０１００】
次いで、バイアス決定部２２０は、パラメータ所属判定部２１０から、配列is_I_up[1:N]および配列is_I_low[1:N] と、特徴量f[1:N]とを入力として受け取る。次いで、バイアス決定部２２０は、配列is_I_up[1:N]および配列is_I_low[1:N] に基づいて、集合I_0 に所属するパラメータのバイアスb を決定する（ステップS202）。次いで、バイアス決定部２２０は、決定されたバイアスb を特徴量変換判定部２３０と特徴量変換部２４０に入力する。
【０１０１】
次いで、特徴量変換判定部２３０は、パラメータの値a[1:N]および特徴量f[1:N]と、配列is_I_up[1:N]および配列is_I_low[1:N] と、バイアスb とを入力として受け取る。特徴量変換判定部２３０は、入力された各値に基づいて、各特徴量を変換するか否かをそれぞれ判定する（ステップS203）。
【０１０２】
次いで、特徴量変換判定部２３０は、各判定結果を基に配列bf[1:N] の各要素に真偽値をそれぞれ代入する。次いで、特徴量変換判定部２３０は、N 個の真偽値が代入された配列bf[1:N] を特徴量変換部２４０に入力する。
【０１０３】
次いで、特徴量変換部２４０は、パラメータの値a[1:N]および特徴量f[1:N]を入力として受け取る。次いで、特徴量変換部２４０は、バイアス決定部２２０から入力されたバイアスb と、特徴量変換判定部２３０から入力された配列bf[1:N] とに基づいて、特徴量変換関数を用いて特徴量を変換する（ステップS204）。
【０１０４】
具体的には、特徴量変換部２４０は、要素bf[i] に代入された真偽値が真であるパラメータi の特徴量f[i]がバイアスb に対して反転された値（2*b - f[i]）を要素xf[i] に代入する。また、特徴量変換部２４０は、要素bf[i] に代入された真偽値が偽であるパラメータi の特徴量f[i]をそのまま要素xf[i] に代入する。
【０１０５】
上記のように、特徴量変換部２４０は、配列xf[1:N] の各要素に特徴量をそれぞれ代入する。次いで、特徴量変換部２４０は、変換後の特徴量を含むN 個の特徴量が代入された配列xf[1:N] をソート部２５０に入力する。
【０１０６】
次いで、ソート部２５０は、N 個の特徴量が代入された配列xf[1:N] を入力として受け取る。次いで、ソート部２５０は、変換後の特徴量を含む各特徴量をソートする（ステップS205）。具体的には、ソート部２５０は、配列xf[1:N] の値をキーとして、配列xf[1:N] をソートする。ソート部２５０は、配列xf[1:N] を昇順にソートしてもよいし、降順にソートしてもよい。
【０１０７】
次いで、ソート部２５０は、配列sxf[1:N]の各要素にソート後のキーをそれぞれ代入する。また、ソート部２５０は、配列sid[1:N]の各要素にソート後のインデックスをそれぞれ代入する。次いで、ソート部２５０は、N 個のキーが代入された配列sxf[1:N]と、N 個のインデックスが代入された配列sid[1:N]を選択部２６０に入力する。
【０１０８】
次いで、選択部２６０は、配列sxf[1:N]および配列sid[1:N]を入力として受け取る。次いで、選択部２６０は、ソート後の各特徴量（キー）から特徴量を昇順に選択する（ステップS206）。
【０１０９】
次いで、選択部２６０は、選択された特徴量に対応するパラメータを作業集合S として出力する（ステップS207）。具体的には、選択部２６０は、配列sid[1:N]の１番目の要素からＭ番目までの要素、すなわち配列sid[1:M]を選択する。
【０１１０】
次いで、選択部２６０は、選択された配列sid[1:M]を作業集合S として出力する。出力した後、作業集合選択装置２００は、作業集合選択処理を終了する。
【０１１１】
なお、ステップS206〜ステップS207で、選択部２６０は、ソート後の各特徴量（キー）から特徴量を降順に選択し、選択された特徴量に対応するパラメータを作業集合S として出力してもよい。具体的には、選択部２６０は、配列sid[1:N]のＮ番目の要素から（Ｎ−（Ｍ−１））番目までの要素、すなわち配列sid[N-(M-1):N]を選択してもよい。
【０１１２】
［効果の説明］
非特許文献２に記載されているThundersvmでは、作業集合の選択処理以外の多くの処理がGPU で実行され、作業集合の選択処理がGPU をホストしているCPU(Central Processing Unit)で実行される。具体的な内容は、ファイルsrc/thundersvm/csmosolver.cpp 中の関数CSMOSolver::select_working_setに記載されている。
【０１１３】
すなわち、上記の関数には、作業集合の選択処理が逐次的に行われるように記載されている。よって、作業集合の選択処理がそのままGPU で実行されても、並列処理が行われない。また、GPU が逐次処理を迅速に実行することは困難であるため、作業集合の選択処理に係る時間が長くなることが想定される。
【０１１４】
以上のように、非特許文献２には、SVM による学習処理において、収束までのステップ数を増やすことなく作業集合の選択処理を並列化できる方法が記載されていない。
【０１１５】
本実施形態の作業集合選択装置２００は、SVM の収束性能を落とすことなく、作業集合の選択処理を並列化できる。その理由は、上集合I_upと下集合I_low の両方に所属するパラメータに対応する特徴量が重複して選択されないように、特徴量変換部２４０が特徴量の集合を変換し、ソート部２５０が変換後の特徴量を含む各特徴量をソートするためである。よって、作業集合選択装置２００は、SVM による学習処理において、収束までのステップ数を増やすことなく作業集合の選択処理を並列化できる。
【０１１６】
なお、作業集合選択装置２００を既存の実装に組み込んでSVM の収束性能を評価したところ、収束までのステップ数の変動は、5%以下に留まった。すなわち、図６に示す選択アルゴリズムから変更されたアルゴリズムに従って作業集合を選択する作業集合選択装置２００は、所定の精度に至るまでのステップ数を殆ど変えずに、作業集合の選択処理を並列化できる。換言すると、作業集合選択装置２００の構成を有するベクトルコンピュータは、SVM による学習処理を、処理性能を落とさずに実行できる。
【０１１７】
以下、各実施形態の作業集合選択装置のハードウェア構成の具体例を説明する。図１１は、本発明による作業集合選択装置のハードウェア構成例を示す説明図である。
【０１１８】
図１１に示す作業集合選択装置は、ＣＰＵ１０１と、主記憶部１０２と、通信部１０３と、補助記憶部１０４とを備える。また、ユーザが操作するための入力部１０５や、ユーザに処理結果または処理内容の経過を提示するための出力部１０６を備えてもよい。
【０１１９】
作業集合選択装置は、図１１に示すＣＰＵ１０１が各構成要素が有する機能を提供するプログラムを実行することによって、ソフトウェアにより実現される。
【０１２０】
すなわち、ＣＰＵ１０１が補助記憶部１０４に格納されているプログラムを、主記憶部１０２にロードして実行し、作業集合選択装置の動作を制御することによって、各機能がソフトウェアにより実現される。
【０１２１】
なお、図１１に示す作業集合選択装置は、ＣＰＵ１０１の代わりにＤＳＰ（Digital Signal Processor）を備えてもよい。または、図１１に示す作業集合選択装置は、ＣＰＵ１０１とＤＳＰとを併せて備えてもよい。
【０１２２】
主記憶部１０２は、データの作業領域やデータの一時退避領域として用いられる。主記憶部１０２は、例えばＲＡＭ（Random Access Memory）である。
【０１２３】
通信部１０３は、有線のネットワークまたは無線のネットワーク（情報通信ネットワーク）を介して、周辺機器との間でデータを入力および出力する機能を有する。
【０１２４】
補助記憶部１０４は、一時的でない有形の記憶媒体である。一時的でない有形の記憶媒体として、例えば磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、ＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory）、半導体メモリが挙げられる。
【０１２５】
入力部１０５は、データや処理命令を入力する機能を有する。入力部１０５は、例えばキーボードやマウス等の入力デバイスである。
【０１２６】
出力部１０６は、データを出力する機能を有する。出力部１０６は、例えば液晶ディスプレイ装置等の表示装置、またはプリンタ等の印刷装置である。
【０１２７】
また、図１１に示すように、作業集合選択装置において、各構成要素は、システムバス１０７に接続されている。
【０１２８】
補助記憶部１０４は、例えば第１の実施形態において、特徴量変換判定部１１０、特徴量変換部１２０、ソート部１３０、および選択部１４０を実現するためのプログラムを記憶している。また、補助記憶部１０４は、例えば第２の実施形態において、パラメータ所属判定部２１０、バイアス決定部２２０、特徴量変換判定部２３０、特徴量変換部２４０、ソート部２５０、および選択部２６０を実現するためのプログラムを記憶している。
【０１２９】
なお、作業集合選択装置は、ハードウェアにより実現されてもよい。例えば、作業集合選択装置１００は、内部に図１に示すような機能を実現するＬＳＩ（Large Scale Integration）等のハードウェア部品が含まれる回路が実装されてもよい。
【０１３０】
また、各構成要素の一部または全部は、汎用の回路（circuitry）または専用の回路、プロセッサ等やこれらの組み合わせによって実現されてもよい。これらは、単一のチップ（例えば、上記のＬＳＩ）によって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい。各構成要素の一部または全部は、上述した回路等とプログラムとの組み合わせによって実現されてもよい。
【０１３１】
各構成要素の一部または全部が複数の情報処理装置や回路等により実現される場合には、複数の情報処理装置や回路等は集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントアンドサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。
【０１３２】
次に、本発明の概要を説明する。図１２は、本発明による作業集合選択装置の概要を示すブロック図である。本発明による作業集合選択装置１０は、最適化の対象の複数のパラメータにそれぞれ対応する各特徴量をソートするソート部１１（例えば、ソート部１３０）と、ソートされた各特徴量のうち最初の特徴量から昇順に並んだ最初の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合、または最後の特徴量から降順に並んだ最後の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合を、部分的に最適化が行われるパラメータの集合である作業集合として選択する選択部１２（例えば、選択部１４０）とを備える。作業集合選択装置１０には、パラメータおよびパラメータに対応する特徴量が入力される。
【０１３３】
そのような構成により、作業集合選択装置は、特定の指標に基づいてパラメータ全体から作業集合を選択できる。
【０１３４】
また、作業集合選択装置１０は、複数のパラメータにそれぞれ対応する各特徴量を変換するか否かを所定の条件に従ってそれぞれ判定する判定部（例えば、特徴量変換判定部１１０）と、変換すると判定された特徴量を所定の変換関数を用いて変換する変換部（例えば、特徴量変換部１２０）とを備えてもよい。また、ソート部１１は、変換された特徴量を含む各特徴量をソートしてもよい。
【０１３５】
そのような構成により、作業集合選択装置は、上集合I_upと下集合I_low の両方に所属するパラメータに対応する特徴量が重複して選択されることを防ぐことができる。
【０１３６】
また、作業集合選択装置１０は、各特徴量の代表値を決定する決定部を備えてもよい。また、作業集合選択装置１０は、パラメータが所定の集合に所属するか否かを複数のパラメータそれぞれに対して判定する所属判定部を備えてもよい。
【０１３７】
そのような構成により、作業集合選択装置は、所属判定部の出力と決定部の出力とに基づいて、特徴量が変換されるか否かを判定できる。また、作業集合選択装置は、判定部の出力と、所属判定部の出力と、決定部の出力とに基づいて、特徴量を変換できる。
【０１３８】
また、最適化は、サポートベクトルマシンにより行われてもよい。
【０１３９】
そのような構成により、作業集合選択装置は、SVM による学習処理において、収束までのステップ数を増やすことなく作業集合の選択処理を並列化できる。
【符号の説明】
【０１４０】
１０、１００、２００  作業集合選択装置
１１、１３０、２５０  ソート部
１２、１４０、２６０  選択部
１０１  ＣＰＵ
１０２  主記憶部
１０３  通信部
１０４  補助記憶部
１０５  入力部
１０６  出力部
１０７  システムバス
１１０、２３０  特徴量変換判定部
１２０、２４０  特徴量変換部
２１０  パラメータ所属判定部
２２０  バイアス決定部
【図１】
2020129149.tif 000003
【図２】
2020129149.tif 000004
【図３】
2020129149.tif 000005
【図４】
2020129149.tif 000006
【図５】
2020129149.tif 000007
【図６】
2020129149.tif 000008
【図７】
2020129149.tif 000009
【図８】
2020129149.tif 000010
【図９】
2020129149.tif 000011
【図１０】
2020129149.tif 000012
【図１１】
2020129149.tif 000013
【図１２】
2020129149.tif 000014
【図１３】
2020129149.tif 000015
【図１４】
2020129149.tif 000016
【国際調査報告】
2020129149.tif 000017
2020129149.tif 000018