ε-Lexicase SelectionとBatch Tournament Selection

#はじめに
最近，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)を使えば適当なεが与えられると書いてあります．

```python
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のコードが知りたい人は，DEAP[^2]に実装されているので参照してください．
これによって評価する訓練データをばらつかせることで集団の多様性を保ち，探索精度を向上させます．

しかし，このアルゴリズムには大きなデメリットがあります．それは計算量が多きするぎるという点です．
いま，訓練データ数を$|T|$，個体数を$|P|$としたとき，最悪の計算量は
$$O(|T|\times|P|^2)$$
となります．個体数と訓練データ数が大きくなると計算量が大きくなるのです．比較のために最も安易に使われるTournament Selectionの計算量は
$$O(\text{Tournament_size}\times|P|)$$
です．だいたい$Tournament_{size}$は10以下であることを想定すると，ε-Lexicase Selectionは控えめに言ってめっちゃ遅いです．
さらに，選ばれた訓練データごとに，その時残っている個体のMADを計算しなければいけません．このMADの計算量も，ソートアルゴリズムを内包しているために高速とは言えません．
しかも，進化計算の特徴である「世代が進むと個体は収束する」という特徴によって，計算すればするほど最悪計算量に近づきます．
DEAP[^2]にも実装されていますが，実用的に使える速度ではないと判断できるほどです(pythonで実装されているためかもしれませんが)．

しかし，Tournament Selectionよりも圧倒的に精度がよくなるのです．C言語かなんかで実装して使うことをお勧めします．
#Batch Tournament Selection
ε-Lexicase Selectionのデメリットは計算量が多きすぎることでした．では，どうやって計算量をへらしつつ精度を保とうか？っといって生まれたのがBatch Tournament Selection[^3]です．実験では**「ε-Lexicase Selectionよりも25倍速くなった」**と言っています．実際，アルゴリズム自体はTournament Selectionに寄っているので高速な理由も理解できます．

### Algorithm
このBatch Tournament Selectionは，Lexicase Selectionで行われていた「訓練データを確立的に選ぶ」ということを，Tournament Selectionに組み込んだアルゴリズムになります．

```python
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界隈でも確率的データ選択の手法は広まっていくと思います．しかし，進化計算でブームになっている多目的最適化に，この確率的データ選択を組み込もうと思うとかなり大変です．パレートフロントが不定になってしまうためです．次は多目的最適化と確率的データ選択の論文が注目されると予測します．おわり

[^1]: La Cava, William, Lee Spector, and Kourosh Danai. "Epsilon-lexicase selection for regression." Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, 2016.
[^2]: https://github.com/DEAP/deap
[^3]: Melo, Vinicius V., Danilo Vasconcellos Vargas, and Wolfgang Banzhaf. "Batch Tournament Selection for Genetic Programming." arXiv preprint arXiv:1904.08658 (2019).