技術資料トップへ戻る最適化の分野においてNP困難と呼ばれる問題がある。代表的なNP困難の問題例として、巡回セールスマン問題やナップサック問題が知られている。NP困難に属する問題は、解の候補が多く、大域的最適解の計算に膨大な時間がかかる。しかしそのような問題であっても、遺伝的アルゴリズムやタブーサーチなどに代表される、メタヒューリスティックなアルゴリズムを用いると、現実的な計算時間で近似解を求めることが可能である。
データマイニングの分野でも、パラメータチューニング（外部から与えられるパラメータの候補から、ある評価値を最高にする組合せを決めること）や変数選択（評価指標に影響が大きい変数を見つけること）という問題は、最適な組合せを発見するには時間がかかる。例えば、決定木を作成する際に、何らかの指標で良いとされるモデルを作成することを考える。このときユーザが、設定する最大分岐数や木を分岐する際の基準（Gini係数など）、あるいは利用するべき説明変数を人手で決めようとすると、パラメータの組合せは指数的に増えるため、すべての組を試すことは現実的ではない。そのため、コンピュータにより、近似解を求めるということが重要になる。
VMStudio ではoptimizeというスクリプト関数を提供している。optimize関数を用いることで、計算量が膨大なモデルのパラメータチューニングや最適化問題といった問題に対しても、近似解を自動的に得ることができる。
optimize関数が解く問題の形式は次の通りである．
fは評価値を返すユーザ定義関数（最適化問題であれば目的関数の値、モデルの評価であれば予測精度などを返す）である。Ηは外部からfの引数として与える、パラメータの組合せの集合、tableは評価値の計算のために利用するテーブルである(実際のoptimize関数ではtableの数は一つとは限らないことに注意)。optimize関数の返り値は、評価したパラメータの組合せの中で、最も高い評価値が得られたパラメータの組である。
optimize関数が最適なパラメータの組を探索する手順について大まかに述べる。
1)
ランダムに初期値を決定する。その値を
とする。はbest solutionsとelite solutionsに入れられる。best solutionsは探索全体で評価値の良い解、elite solutionsはそこから探索すれば、より良い評価が得られる可能性が高いと考えられる有望な解である。best solutionsとelite solutionsは、どちらも評価値が高いものから順に並べたパラメータの組合せのリストである。
2)
elite solutionsの中にある、ユーザ定義関数で最もよい評価になるパラメータの組合せを取り出す。その組合せを
と表す。を基に、探索するパラメータ集合を作成する。いま、fをから探索するパラメータ集合を生成するアルゴリズムとすると、探索対象となるパラメータ集合は
で表される。
パラメータ集合に対する探索の方法は、探索方法がDFSであれば、評価値が良さそうなパラメータから優先的に探索する。何度か途中で探索を区切り、そこまでの探索で、全体で最良の値を更新するものが含まれていれば、その時点で探索を打ち切り、3)へ進む。一方、探索方法がBFSであれば、途中で探索を打ち切ることはなく、パラメータ集合すべてに対しユーザ定義関数を計算し3)へ進む。
3)
探索対象となったパラメータ集合のユーザ定義関数の計算結果をbest
solutions、elite
solutionsに入れる。次に、更新したelite solutionsの中で最も良い評価値になるパラメータの組合せを
として、ステップ2)に戻る。これを、探索回数が指定した回数に達するまで繰り返す。なお、探索の基になった解は何度も探索するのを防ぐため、タブーリストに入れる。
実際のoptimize関数のフォーマットは次のようになる。
|
optimize(key,option,serarchOpt,patternList,table,…) |
入力引数ついて説明する。
l
key
精度を表す関数である。sys_procで呼ぶ関数であれば、その関数を示す数字が入る。DLLを用いる場合は{DLL中の関数名,DLLのパス}と指定する。
l
option
1行10列のテーブルである。パラメータの組合せの探索手法を指定する。
l
serarchOpt
探索する範囲について指定する。文字列型であれば最大で選択するサイズ、実数型であれば、どの程度まで細かく探索するかということについて指定する。
l
patternList
チューニングするパラメータのリストである。文字列型のデータに対しては候補となる値を，実数型のデータに対しては、候補となる値の範囲を入力する。
l
table
ユーザ定義関数で評価値を計算するために利用するテーブルである。tableはいくつ与えてもよい。
optimize関数の返り値は最適なパラメータの組合せを上位nTop個並べたものである(nTopはoptionテーブルで指定する)。また、返り値を得るのに時間がかかる場合には、optionテーブルで途中経過を保存するファイルパスを指定する。途中経過を見て探索戦略を変えながら、最適な組合せを探すことができる。
Fred Glover, Manuel Laguna(1997),Tabu Search,Kluwer Academic Publishers.
Kennedy, J.; Eberhart, R. (1995). Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks. IV. pp. 1942–1948.