はじめに
最近，GP界隈でも確率的にデータを選ぶ手法が注目を集めているので，それについて
今回は回帰問題で良い精度をたたき出したε-Lexicase Selectionと，それの概念を取り入れつつ高速化したBatch Tournamentに焦点を当てます．
ε-Lexicase Selection
Selectionと名のついている通り，次世代の個体の選択法です．このとき，一般的なGPでは，学習データの誤差の平均値を評価値としますが，Lexicase Selectionや後述するBatch Tournamentでは，各学習データ$t \in T$に対する誤差の集合$E(t)$を，各個体が持つものと考えてください．
Algorithm
アルゴリズムはこんな感じ．なおε-Lexicase Selectionでは，許容量$ε$をパラメータとして与えることができますが，原著1ではMAD(Median Absolute Deviation)を使えば適当なεが与えられると書いてあります．
def EpsilonLexicaseSelection(population, T)
next_population = {}
while |next_population| < |population|:
T = shuffle(T)
pool = population
for t in T:
errors_t = {individual.E(t) | individual in pool}
epsilon = MAD(errors_t)
best_error = min(errors_t)
next = {individual | individual.E(t) <= best_error + epsilon, individual in pool}
pool = next
if |pool| == 1:
next_population = next_population || {pool[0]}
break
if t is last:
next_population = next_population || {randomChoice(pool)}
return next_population
def MAD(errors):
med = median(errors)
return median({abs(e - med) | e in errors})
簡単に要約すると，「ランダムな訓練データにおける誤差が，最も良い個体と許容量$ε$の個体を残し，訓練データを変えて繰り返す」こと．
そして，「残った個体が1つになった時にそれの個体を次世代の母集団へ加える」といったアルゴリズムになります．疑似コードではなく，pythonのコードが知りたい人は，DEAP2に実装されているので参照してください．
これによって評価する訓練データをばらつかせることで集団の多様性を保ち，探索精度を向上させます．
しかし，このアルゴリズムには大きなデメリットがあります．それは計算量が多きするぎるという点です．
いま，訓練データ数を$|T|$，個体数を$|P|$としたとき，最悪の計算量は
$$O(|T|\times|P|^2)$$
となります．個体数と訓練データ数が大きくなると計算量が大きくなるのです．比較のために最も安易に使われるTournament Selectionの計算量は
$$O(\text{Tournament_size}\times|P|)$$
です．だいたい$Tournament_{size}$は10以下であることを想定すると，ε-Lexicase Selectionは控えめに言ってめっちゃ遅いです．
さらに，選ばれた訓練データごとに，その時残っている個体のMADを計算しなければいけません．このMADの計算量も，ソートアルゴリズムを内包しているために高速とは言えません．
しかも，進化計算の特徴である「世代が進むと個体は収束する」という特徴によって，計算すればするほど最悪計算量に近づきます．
DEAP2にも実装されていますが，実用的に使える速度ではないと判断できるほどです(pythonで実装されているためかもしれませんが)．
しかし，Tournament Selectionよりも圧倒的に精度がよくなるのです．C言語かなんかで実装して使うことをお勧めします．
Batch Tournament Selection
ε-Lexicase Selectionのデメリットは計算量が多きすぎることでした．では，どうやって計算量をへらしつつ精度を保とうか？っといって生まれたのがBatch Tournament Selection3です．実験では「ε-Lexicase Selectionよりも25倍速くなった」と言っています．実際，アルゴリズム自体はTournament Selectionに寄っているので高速な理由も理解できます．
Algorithm
このBatch Tournament Selectionは，Lexicase Selectionで行われていた「訓練データを確立的に選ぶ」ということを，Tournament Selectionに組み込んだアルゴリズムになります．
def BatchTournamentSelection(population, T, batch_size, tournamnet_size):
if do shuffle:
T = shuffle(T)
else:
best_ind = best(population)
T = (t | t in T, best_ind.E(T[i]) > best_ind.E(T[i+1])) #Order by difficulty sort
batches = split(T, batch_size)
batch = batches.first(batches)
next_population = {}
while |next_population| < |population|:
choice = randomSample(population, tournament_size)
errors_batch = {sum({individual.E(t) | t in batch})/|batch| | individual in choice}
bests = choice[min_arg(errors_batch)]
if |bests| == 1:
next_population = next_population || {bests[0]}
else:
next_population = next_population || {randomChoice(bests)}
batch = batches.next(batches)
return next_population
簡単に要約すると，「batchサイズで切り出した訓練データにおける平均誤差が，最も良い個体と許容量$ε$の個体を次世代の母集団へ加える」といったアルゴリズムになります．また，batchの並び順を，shuffleもしくは誤差が悪い順に変更することができます．
原著中では，batchの並び順をshuffleしたほうがTournament_sizeとbatch_sizeに対する性能差が少なく，パラメータ選択が容易であること．shuffleのほうが性能が多少悪化するが，Tournament_sizeとbatch_size次第であることが書かれています．私も自分で使うときはshuffleにしています．
さて，計算量ですが
$$O(\text{batch_size}\times\text{tournament_size}\times|P|)$$
であることは明らかなので，ε-Lexicase Selectionよりも明らかに少ないです．精度自体は，ε-Lexicase Selectionと同程度，もしくは少し劣るのですが，問題依存な気もするので気にするほどではないと思います．速くなった分，集団サイズを大きくすれば精度向上しますしね．
注意点ですが，原著中ではTournament_sizeを結構大きめにしたほうが性能が良いと書かれています．64とか128くらいですかね．通常の進化計算的に見ればかなり大きいのですが，「ランダムに訓練データを選ぶ」という性質上仕方ないのかもしれません．
おわりに
機械学習でも確率的にデータを選ぶことは重要でしたが，進化計算でも重要です．今後，GP界隈でも確率的データ選択の手法は広まっていくと思います．しかし，進化計算でブームになっている多目的最適化に，この確率的データ選択を組み込もうと思うとかなり大変です．パレートフロントが不定になってしまうためです．次は多目的最適化と確率的データ選択の論文が注目されると予測します．おわり
-
La Cava, William, Lee Spector, and Kourosh Danai. "Epsilon-lexicase selection for regression." Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, 2016. ↩
-
Melo, Vinicius V., Danilo Vasconcellos Vargas, and Wolfgang Banzhaf. "Batch Tournament Selection for Genetic Programming." arXiv preprint arXiv:1904.08658 (2019). ↩