JP7207423B2

JP7207423B2 - 作業集合選択装置、作業集合選択方法および作業集合選択プログラム

Info

Publication number: JP7207423B2
Application number: JP2020560675A
Authority: JP
Inventors: 晴道横山
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2018-12-18
Filing date: 2018-12-18
Publication date: 2023-01-18
Anticipated expiration: 2038-12-18
Also published as: JPWO2020129149A1; US20220019942A1; WO2020129149A1

Description

本発明は、作業集合選択装置、作業集合選択方法および作業集合選択プログラムに関し、特にサポートベクトルマシンによる最適化に用いられる作業集合を選択できる作業集合選択装置、作業集合選択方法および作業集合選択プログラムに関する。

機械学習は、データから定められる評価関数の値を最小にするようなパラメータの値を探索する最適化問題の一種である。以下、機械学習における最適化を、単に「学習」とも呼ぶ。

有用な機械学習アルゴリズムとして、サポートベクトルマシン(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 による学習処理において、収束までのステップ数を増やすことなく作業集合の選択処理を並列化できる。

１０、１００、２００作業集合選択装置
１１、１３０、２５０ソート部
１２、１４０、２６０選択部
１０１ＣＰＵ
１０２主記憶部
１０３通信部
１０４補助記憶部
１０５入力部
１０６出力部
１０７システムバス
１１０、２３０特徴量変換判定部
１２０、２４０特徴量変換部
２１０パラメータ所属判定部
２２０バイアス決定部

Claims

最適化の対象の複数のパラメータにそれぞれ対応する各特徴量をソートするソート部と、
ソートされた各特徴量のうち最初の特徴量から昇順に並んだ前記最初の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合、または最後の特徴量から降順に並んだ前記最後の特徴量を含む前記所定の数の特徴量にそれぞれ対応するパラメータの集合を、部分的に最適化が行われるパラメータの集合である作業集合として選択する選択部と、
前記複数のパラメータにそれぞれ対応する各特徴量を変換するか否かを所定の条件に従ってそれぞれ判定する判定部と、
変換すると判定された特徴量を所定の変換関数を用いて変換する変換部とを備える
ことを特徴とする作業集合選択装置。
ソート部は、変換された特徴量を含む各特徴量をソートする
請求項１記載の作業集合選択装置。
各特徴量の代表値を決定する決定部を備える
請求項１または請求項２記載の作業集合選択装置。
パラメータが所定の集合に所属するか否かを複数のパラメータそれぞれに対して判定する所属判定部を備える
請求項１から請求項３のうちのいずれか１項に記載の作業集合選択装置。
最適化は、サポートベクトルマシンにより行われる
請求項１から請求項４のうちのいずれか１項に記載の作業集合選択装置。
作業集合選択装置で実行される作業集合選択方法であって、
前記作業集合選択装置が、
最適化の対象の複数のパラメータにそれぞれ対応する各特徴量をソートし、
ソートされた各特徴量のうち最初の特徴量から昇順に並んだ前記最初の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合、または最後の特徴量から降順に並んだ前記最後の特徴量を含む前記所定の数の特徴量にそれぞれ対応するパラメータの集合を、部分的に最適化が行われるパラメータの集合である作業集合として選択し、
前記複数のパラメータにそれぞれ対応する各特徴量を変換するか否かを所定の条件に従ってそれぞれ判定し、
変換すると判定された特徴量を所定の変換関数を用いて変換する
ことを特徴とする作業集合選択方法。
作業集合選択装置が、変換された特徴量を含む各特徴量をソートする
請求項６記載の作業集合選択方法。
作業集合選択装置が、各特徴量の代表値を決定する
請求項６または請求項７記載の作業集合選択方法。
コンピュータに、
最適化の対象の複数のパラメータにそれぞれ対応する各特徴量をソートするソート処理、
ソートされた各特徴量のうち最初の特徴量から昇順に並んだ前記最初の特徴量を含む所定の数の特徴量にそれぞれ対応するパラメータの集合、または最後の特徴量から降順に並んだ前記最後の特徴量を含む前記所定の数の特徴量にそれぞれ対応するパラメータの集合を、部分的に最適化が行われるパラメータの集合である作業集合として選択する選択処理、
前記複数のパラメータにそれぞれ対応する各特徴量を変換するか否かを所定の条件に従ってそれぞれ判定する判定処理、および
変換すると判定された特徴量を所定の変換関数を用いて変換する変換処理
を実行させるための作業集合選択プログラム。
コンピュータに、
ソート処理で、変換された特徴量を含む各特徴量をソートさせる
請求項９記載の作業集合選択プログラム。