回帰問題のための遺伝的プログラミングの自動的な知識利用手法

全文

(1)45. 論文. . 回帰問題のための遺伝的プログラミングの自動的な知識利用手法 Automatically Knowledge Reuse for Regression Problems in Genetic Programming 加藤慎二. 横浜国立大学大学院環境情報学府. Shinji Kato. Graduate School of Environment and Information Sciences, Yokohama National University. [email protected]. 長尾智晴. 横浜国立大学大学院環境情報研究院. Tomoharu Nagao. Faculty of Environment and Information Sciences,Yokohama National University. [email protected]. keywords: genetic programming, transfer learning, code reuse Summary Genetic programming has been applied to various problems, and many derived methods have been proposed. Genetic Programming is one of the meta-heuristic methods that has to follow the No Free Lunch (NFL) theorem to improve accuracy. NFL theorem states the importance of using problem knowledge. GP with transfer learning has been proposed as methods of using knowledge. However, when this method solves a problem, it needs to select a source problem. Another approach is to use knowledge by multi-task learning, but it is necessary to solve multiple problems at the same time. In this paper, we propose a method of extracting knowledge from multiple source problems and selecting appropriate knowledge. This method uses an island model to extract knowledge, and a machine learning model to select knowledge. The advantage of this approach is the end-to-end method and that it does not require source problem selection: it automatically uses knowledge. The experimental results show that the proposed method higher rank of the test data than GP without transfer learning on average of 70 real-world regression problems. In addition, the proposed method performs as well as popular machine learning and has lower trial variance than the machine learning methods such as random forest, gradient boost, and XGBoost.. 1. はじめに. ク構造を解表現とすることで木構造よりも複雑な表現を可能としている．また，GNP は閉路を持つ解表現によっ. 進化計算は柔軟な解表現と探索能力をもつため，幅広い分野の問題に適用されている．進化計算の一つに，関数を最適化する遺伝的プログラミング (Genetic Programming;. て，ループ処理を実現し，小さな構造でも複雑な処理を可能としている．. 2 つ目は効率的な遺伝子操作手法である．木構造の GP. GP)[Koza 94a] があり，回帰問題 [Orzechowski 18] やクラス分類問題 [La Cava 19]，マルチエージェント [Luke 96]，ニューラルネットワークの構造最適化 [Suganuma 17, Elsken 18] などの分野へ適用されている．さらに， GP は精度を向上させるための改良手法が数多く提案されており，これらの手法は，次の 3 つに分類できる．. においてはブロートの観点から，木のノード数を増やさ. 1 つ目は解表現の改良手法である．GP において一般的に利用される解表現の改良手法としては，Automatically Defined Functions(ADFs) が挙げられる．ADFs は解表現. Geometric Genetic Programming(GSGP)[Moraglio 12] な. に自己参照関数を組み込む手法であり，多くの問題に対. に，遺伝的アルゴリズム (Genetic Algorithm; GA) と同様. して有効性が確認されている [Koza 94b]．他にも，ADFs. にルーレット選択やトーナメント選択などの手法を用い. を用いない複雑な解の表現方法として，Cartesian Genetic. るが，初期収束による解探索の悪化が問題となっている．. Programming(CGP)[Miller 99, Miller 00] や Genetic Network Programming(GNP)[Hirasawa 01, Mabu 07] が提案されている．CGP はフィードフォワード型のネットワー. そこで，個体の多様性を保つ手法として，解が年齢の概念. ない交叉方法が提案されている [Ito 98, Langdon 99]．また，グラフ構造の GP においては，破壊的な交叉をしない交叉方法 [Clegg 07, Atkinson 18] がいくつか提案されており，それらの手法の比較がされている [Husa 18]．さらに，解の出力値にのみ着目した交叉方法である Semantic ども提案されている．. 3 つ目は世代交代手法である．GP の世代交代は一般的. を持つ Age Layered Population Structure(ALPS)[Hornby. 06] や Age Fitness Pareto[Schmidt 11] が提案されている．.

(2) 進化計算学会論文誌 Vol. 11. 46. No. 3（2020）. 他にも，評価データをランダムに選択する手法 [Spector. 由は，最適解が既知である問題で検証を行っている点で. 12, La Cava 16, Melo 19] が提案されており，近年では回帰問題において良い結果が報告されている [Orzechowski 18]．. ある．この検証方法では，最適解の構造によって問題間. これらの手法の有効性は様々な問題で示されている．し. であり，問題間の関係性を明確に把握することは困難で. かし，No Free Lunch の定理 [Wolpert 95, Wolpert 97] よ. ある．そのため，従来の GP における転移学習は実問題. り，GP を含む Black-Box 最適化アルゴリズムを用いた. に適用することができない．. の関係性が分かりやすいため，事前問題の選択が容易である．しかし，一般に実問題を解く場合，最適解は未知. すべての問題における性能の平均値は，どのようなアル. 他の知識利用手法としては，複数の集団を用いたマル. ゴリズムを用いても同一であることが示されている．つ. チタスク学習が提案されている [Scott 17]．また，別々の. まり，汎用的に使うことのできる精度向上手法の決定は. 問題を解くときに個体を共有することで，他の問題の知. 困難である．そのため，任意の問題において精度を向上. 識を利用する手法なども提案されている [Wang 19]．こ. させるためには，その問題の知識を用いた精度向上手法. れらの手法は複数の集団を用いており，他の母集団の個. を用いなければならない．. 体と別の母集団の個体を交叉させて子個体生成を行うこ. GP において問題の知識を利用する手法として，転移学習を用いる手法が提案されている [Dinh 15, O’Neill 17]．. とで，他の問題の知識を得ている．さらに，同様な手法. 転移学習とは，対象の問題を解く前に，別の問題を解き，. を獲得する手法も提案されている [Scott 19]．このマルチ. その知識を対象の問題に利用する手法である．このとき，. タスク学習は他の問題を利用可能であるが，同時に別々. 対象の問題を対象問題，事前に解く問題を事前問題と呼. の問題を解く必要があるため，従来の転移学習と同様に. ぶ．しかし，従来手法は，既知である最適解の共通部を. 別の問題の選択を必要とする．. によって多くの問題を同時に解くことで，自動的に知識. 考慮した問題設定で検証を行っている．そのため，最適解が未知である実問題では，最適解の共通部を考慮した. 3. 回帰問題への遺伝的プログラミングの適用. 事前問題の設定をすることはできない．また，事前問題の設定に経験的知識を必要とするため，従来手法の汎用的な利用は難しい．. 回帰問題は Xt から yt へ変換する関数 S を探し出す問題である．GP はこの関数を，木構造による基礎関数の. 本論文では，GP において対象問題に応じた事前問題. 組み合わせとして表現し，その組み合わせを最適化する. の自動的な選択を行う転移学習の手法を提案する．提案. 手法である．このとき，基礎関数の組み合わせを個体と. 手法では，事前問題からの知識の抽出に島モデルの特性. 呼び，回帰問題への適応度は式 (1) の誤差関数で計算す. を利用する．また，抽出された知識の選択は，機械学習. る．また，本論文では過学習を抑えるために木のノード. を用いた知識選択モデルを構築することで行う．実験で. 数によるペナルティ項を設ける．GP の個体の最適化は，. は，回帰問題の実問題で検証実験を行い，提案手法が汎. 図 1 に示すアルゴリズムで行う．はじめに，複数の個体. 用的に精度を向上させることを確認する．さらに，一般. をランダムに生成し，母集団を形成する．つぎに，すべ. 的な機械学習の手法と比較し，提案手法の有効性を検証. ての個体の適応度を評価し，選択によって，母集団中の. する．. 良い適応度を持つ個体を増やし，悪い適応度を持つ個体を減らす．そのあと，交叉および突然変異によって個体. 2. 関連研究. のもつ木構造の組み合わせの変更を行う．交叉は，一定確率で母集団中の 2 個体を選び，任意の部分木を交換す. GP における転移学習は，Neural Network における転. る．突然変異は，一定確率で個体の任意の部分木を変更. 移学習と異なり，部分木を転移する手法が提案されている. する．これらの評価，選択，交叉，突然変異の一連の操作. [Iqbal 17, Ja´skowski 14]．Dinh らはランダムに個体を転. を世代交代と呼び，一定回数の世代交代を繰り返し，終. 移する手法と，ランダムに部分木を転移する手法を比較. 了する．. した結果，部分木を転移する手法が転移学習に効果的であることを示している [Dinh 15]．しかし，この実験において転移させた部分木の数は 50 以上と多く，効率的な探. F (S) =. N 1 ∑ |S(Xt ) − yt | + p|V (T )| N t=1. (1). 索ではないことが指摘されている．そこで， O’Neill らは二つの事前問題を用いて，共通部分木を抽出することで，. 4. 提案手法. 転移させる部分木の数を減らすことに成功した [O’Neill 提案手法は，対象問題を解くとき、多数の事前問題か. 17]．一方で，従来の GP における転移学習は，2 つの理由から汎用的に利用することが難しい．1 つ目の理由は，. ら自動的に適切な知識を利用する手法である．提案手法. 事前問題の決定に経験的知識を必要とすることである．. では，各々の事前問題の解から知識である部分木を抽出. このため，汎用的に利用することが難しい．2 つ目の理. し，この部分木を 1 ノードとして扱い GP を用いて対象.

(3) 回帰問題のための遺伝的プログラミングの自動的な知識利用手法. 47. 6WDUW. 6WDUW ,QLWLDOL]H 3RSXODWLRQ. &RQGLWLRQ &KHFN. ,QLWLDOL]H 3RSXODWLRQ. ,QLWLDOL]H 3RSXODWLRQ. ,QLWLDOL]H 3RSXODWLRQ. &RQGLWLRQ &KHFN. &RQGLWLRQ &KHFN. &RQGLWLRQ &KHFN. (YDOXDWLRQ. (YDOXDWLRQ. (YDOXDWLRQ. 6HOHFWLRQ. 6HOHFWLRQ. 6HOHFWLRQ. (YDOXDWLRQ 6HOHFWLRQ &URVVRYHU 0XWDWLRQ. ,PPLJUDWLRQ &URVVRYHU. &URVVRYHU. &URVVRYHU. 0XWDWLRQ. 0XWDWLRQ. 0XWDWLRQ. %HVW ,QGLYLGXDO. %HVW¬,QGLYLGXDO. %HVW¬,QGLYLGXDO. ([WUDFW &RPPRQ 6XEWUHHV (QG. %HVW ,QGLYLGXDO. 図 2 島モデルと部分木抽出 (QG. 図1. GP の解探索アルゴリズム. れる．はじめに，X の各列に対して四分位を求めたあと，各行に対して四分位を求める．これによりテーブルデー. 問題を解く．このとき，部分木は元の木の葉ノードを含まず，ノードを 2 つ以上持つものとする．また，同型の部分木は一つのみ抽出し，重複した場合は抽出しない．抽出された部分木は，ノードセットに追加し，初期生成および突然変異において通常のノードと同様に扱う．. 4·1 事前問題の解の部分木抽出転移させる部分木は解の中で重要部分である必要がある．しかし，単純な GP では自身の解から重要部分を判定することが難しい．そこで本論文では島モデル GP の特. タ X から 5 × 5 の分布特徴量 PX が得られる．また，出力データ y に対しても分布の四分位を求めることで分布特徴量 Py が得られる．提案手法では問題特徴量を PX と Py を一次元に結合したものとして定義する．この方法の利点は次の 3 つがある．. • 説明変数間の分布と各説明変数の分布を特徴として抽出すること．. • 列が入れ替わった問題や，データ数を水増した問題に対しても，同じ特徴量として算出できること．. • テーブルデータのサイズ (行数と列数) が異なるの問題間でも，同一次元の特徴量として算出できること．. 性を利用する．島モデルは，単一の母集団ではなく複数. 提案手法における部分木特徴量の定義を次に示す．こ. の母集団を用いることで解の多様性を維持する手法であ. れは，グラフの特徴量 [Berlingerio 12] を参考に，木構造. る．提案手法では，島モデルにおける複数のエリートから共通部分を抽出することで，部分木中の重要部分を抽出する．島モデル GP と部分木抽出の流れを図 2 に示す．. 4·2 対象問題に適した部分木の選択対象問題を解くとき，部分木の数が多すぎる場合には組み合わせが膨大になるため，最適化することができず，対象問題の精度を向上させることができない．そのため，対象問題に適した部分木を判定する必要がある．提案手法では各事前問題から複数の部分木が得られる．そこで，問題と部分木に対して特徴量を定義することで，図 3 に示すように問題特徴量と部分木特徴量から，その. に対する特徴量として定義したものである．. • ノード数 • エッジ数 • 次数平均値 • 次数中央値 • 次数分散 • 隣接ノードの次数平均値 • 隣接ノードの次数中央値 • 隣接ノードの次数分散 • 隣接ノードの子の数の平均値 • 隣接ノードの子の数の中央値 • 隣接ノードの子の数の分散 • 各ノード関数の出現頻度. 問題に抽出された部分木が重要であるか否かを判定するクラス分類問題が生成できる．これを解くことで重要部. 5. 性能評価実験. 分判定モデルを構築し，部分木を選択する．提案手法における問題特徴量は次の手順で求める．問. 本実験では，提案手法が汎用的に精度を向上させるこ. 題としてはテーブルデータ X と出力データ y が与えら. とを確認する．また，一般的な機械学習手法と比較し，提.

(4) 進化計算学会論文誌 Vol. 11. 48. No. 3（2020）. 表 1 GP のハイパーパラメータ. 図3. 重要部分判定問題の生成. 案手法の利点を明らかにする．本実験で扱う問題は Penn. Machine Learning Benchmarks(PMLB)[Olson 17] および UCI Dataset に登録されている問題から実問題かつ回帰問題であるものを選択した．また，1 つの問題のパラメータチューニングを含めた探索時間の上限を 72 時間とし，表 5 に示す 70 個の実回帰問題を扱うこととした．本実験では Core i7-6850K(6 core) の CPU と 32GB のメモリを使用した．提案手法は，対象問題を解くときに事前問題を必要とするため，本実験では，1 つの問題を解くとき，他の 69 個の問題を事前問題として利用する．. parameter name. value. initial tree depth crossover rate mutation rate max generation batch size tournament size island num & population size immigration rate immigration interval penalty. [6] [0.8] [0.2] [200] [8] [8, 64]. 表2. [(10,50), (20,25), (50,10)] [0.1] [10] [0, 2−6 , 2−7 ]. GP の個体操作方法. operator. method name. initialization evaluation selection immigration crossover mutation node set leaf node set. grow and full mean absolute errors batch tournament selection random shift subtree swap subtree recreation {+, −, ×, ÷, sin, cos, exp, log} {xi , ERC}. 5·1 実験設定 GP のハイパーパラメータを表 1 に示す．本実験では 5 分割交差検証よってパラメータチューニングを行った．. を表 4 に示す．これらのパラメータは scikit-learn∗1 に従っ. また，最良のハイパーパラメータを用いて，対象問題と. て決定した．これらの手法も提案手法と同様に 5 分割交. 事前問題を 5 回試行した．各試行のテストデータは，オ. 差検証よってパラメータチューニングを行った．. リジナルデータの 2 割がランダムに選択され，残り 8 割のデータが学習データとして用られる．遺伝子操作の設定を表 2 に示す．本論文では，交叉に部分木交換交叉を，突然変異にノード変更突然変異をそれぞれ用いた．また，選択には近年，回帰問題で精度・速度共に良い結果を示している Batch Tournament Selection[Melo 19] を用いた．事前問題によって生成された部分木の重要部分判定問題は，高速に良い精度で分類問題を解くことができる XGBoost[Chen 16] を用いて解いた．XGBoost のパラメータを表 3 に示す．さらに，本実験では次に示す一般的な機械学習の手法と提案手法を比較した．. • Least Absolute Shrinkage and Selection Operator with Least Angle Regression; LASSO with LARS • Stochastic Gradient Descent Regression; SGD • Support Vector Regression; SVR • Multi-layer perceptron; MLP • Random Forest • Adaptive Boost; ada Boost • Gradient Boost • XGBoost[Chen 16] 本実験で用いた機械学習手法およびハイパーパラメータ. 5·2 実験結果 § 1 提案手法による GP の精度向上の検証実験によって，Simple GP(GP) および Island GP(IGP) と提案手法の GP の回帰精度を比較した．また，提案手法は，転移学習時が Simple GP(TSGP) である場合と Island GP(TIGP) である場合を比較した．ここで，TSGP および TIGP のどちらも，事前学習時は島モデル GP を用いているため，抽出された部分木の総数および特徴は同じである．さらに，提案手法である部分木の重要部分判定が有効であることを検証するために，XGboost を用いた重要部分判定 (XT) とランダムに 10 個の部分木を転移する手法 (RT) を比較した．そして，全ての手法を一律に評価するために，各手法の回帰問題における 5 試行の平均精度の順位を計測し，70 個の問題の分布を生成した．ま表3. 重要部分判定のための XGBoost のパラメータ. name. value. max depth estimator num. 6 1000. ∗1 scikit-learn: https://scikit-learn.org/stable/.

(5) 回帰問題のための遺伝的プログラミングの自動的な知識利用手法表4. model Linear Regression LASSO with LARS SGD SVR. MLP. Random Forest. ada Boost. Gradient Boost. XGBoost. 49. 機械学習のハイパーパラメータ. name:values defualt alpha: [0.0001, 0.001, 0.01, 0.1, 1.0] alpha: [0.000001, 0.0001, 0.01, 1.0] penalty: [l2, l1, elasticnet] kernel: [linear, poly, rbf, sigmoid] C: [0.000001, 0.0001, 0.1, 1.0] activation:[logistic, tanh, relu] solver:[lbfgs,adam,sgd] learning rate:[constant, invscaling, adaptive] n estimators:[10, 100, 1000] min weight fraction leaf:[0.0, 0.25, 0.5] max features:[sqrt, log2, None] n estimators:[10, 100, 1000] learning rate:[0.01, 0.1, 1, 10] n estimators:[10, 100, 1000] min weight fraction leaf:[0.0, 0.25, 0.5] max features:[sqrt, log2, None] n estimators:[10, 100, 500, 1000] max depth:[6, 8] subsample:[0.5, 0.75, 1.0]. た，機械学習の手法についても同様に順位を計測し，各習データにおける順位分布を図 6，テストデータにおけ. きる．一方で，図 6 の結果からテストデータにおいては， Random Forest を用いた回帰精度が平均的に最も良く，2 番目に XGBoost，3 番目に提案手法である TIGP and XT. る順位分布を図 7 に示す．. の精度が良いことを確認することができる．このとき，提. 手法の 70 個の回帰問題における順位分布を生成した．学. 図 6 の左半分の結果から，学習データにおいては SGP と. 案手法と RandomForest, XGBoost の平均順位はほとんど. TSGP，IGP と TIGP を比較すると転移学習を行う TSGP や TIGP の方が精度が良いことが確認できる．また，重要部分判定を行わない RT と行う XT には順位の差は明確ではない．一方で図 7 の左半分の結果から，テストデータにおいては，RT と XT を比較すると重要部分を判定する XT の方が精度が良いことが確認できる．つまり，提. 同程度である．そして，テストデータにおいては，学習. 案手法を用いて自動的な知識が抽出・選択することで，精. ことができる．. 度を向上させることができる．また，テストデータにお. § 3 提案手法による木の生成例. いて，XGboost を用いた重要部分判定の精度が良かったことから，提案手法は汎化性の高い木構造を転移することができる．この結果は，ランダムに部分木を選んだ RT では，対象問題の汎化性能とは関連しないノードが転移学習時に追加されただけであり，解の汎化性能の向上に寄与しなかったためだと考えられる．一方で，XT では，対象問題に適したノードを選択して追加するため，汎化性能の向上に寄与したと考えらえれる．. § 2 提案手法と機械学習の比較図 6 の結果から学習データにおいては，XGBoost を用. データと異なり，XGBoost や Random Forest の順位分布の四分位範囲が大きいのに対して，GP の順位分布の四分位範囲はほとんど変化していない．つまり，提案手法は Random Forest や XGBoost と比べて，ほとんど同じ性能でありながら，多くの問題で良い精度で問題を解く. 図 8 に提案手法による木の生成例を示す．図中の赤いノードは，転移された部分木ノードであり，黒いノードは通常の基礎ノードである．この図は TIGP and XT による最終世代の最良解であり，同図より，提案手法を用いることで多くの転移部分木が含まれていることがわかる．これは，転移された複雑な部分関数を，進化計算が自然淘汰によって選択した結果である．つまり，実験で扱った実回帰問題を GP で探索するためには，より複雑な基礎ノードが必要なことを示唆している．一方で，提案手法を用いると，基礎ノードの数は爆発的に増加するため，. いた回帰精度が平均的には最も良く，2 番目に Random. ブロートによる計算量の増加や汎化性能の低下が問題と. Forest, 3 番目に Gradient Boost，4 番目に提案手法である TIGP and XT の精度が良いことを確認することがで. なる．提案手法では，基礎ノード数の増加に対する根本的な対策は行なっていないため，今後の課題となる．.

(6) 進化計算学会論文誌 Vol. 11. 50. No. 3（2020）. 表 5 実験で用いた回帰問題. ID. Name. Referrer. ID. Name. Referrer. 0 1 2 3 4 5 6. UCI OpenML OpenML OpenML OpenML OpenML UCI. 35 36 37 38 39 40 41. no2 o-ring-erosion-only o-ring-erosion-or-blowby onlinenewspopularity parkinson speech parkinsons updrs pm10. OpenML UCI UCI UCI UCI UCI OpenML. UCI. 42. pollen. OpenML. 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23. airfoil-self-noise analcatdata apnea1 analcatdata apnea2 analcatdata election2000 analcatdata neavote analcatdata vehicle auto price behavior of the urban traffic of the city of sao paulo in brazil bike sharing day bike sharing hour bodyfat casp chatfield 4 chscase geyser1 cloud combined cycle power plant concrete data container crane controller data set cpu act cpu small cpu daily demand forecasting orders electrical grid stability simulated elusage. UCI UCI OpenML UCI OpenML OpenML OpenML UCI UCI UCI OpenML OpenML OpenML UCI UCI OpenML. 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58. OpenML OpenML OpenML OpenML UCI OpenML OpenML UCI OpenML OpenML OpenML OpenML UCI UCI UCI OpenML. 24. enb2012 data cooling. UCI. 59. 25 26 27 28 29 30 31 32 33 34. enb2012 data heating energydata complete era esl facultysalaries geographicaloriginalofmusic istanbule stock lev machine cpu machine. UCI OpenML OpenML OpenML OpenML OpenML UCI OpenML OpenML OpenML. 60 61 62 63 64 65 66 67 68 69. pollution puma8NH pwLinear rabe 266 real estate valuation rmftsa ladata satellite image servo sleuth case1202 sleuth case2002 sleuth ex1605 sleuth ex1714 student math studet portuguese superconductivty swd tamilnadu electricity board hourly readings tecator uscrime vineyard vinnie visualizing environmental visualizing galaxy wind winequality-red winequality-white yacht hydrodynamics. 7. UCI OpenML OpenML OpenML OpenML OpenML OpenML OpenML UCI UCI UCI. 6. 提案手法の解析と考察. についてのヒストグラムを示す．この図から，島数が 10，. 6·1 部分木抽出と島モデルの関係. 20 の場合には，抽出される部分木の数が 20 以下であることがわかる．また，島数が 50 の場合に多くの部分木が. 提案手法では，島モデル GP の各エリート個体から共. 抽出できることもわかる．つまり，提案手法における部. 通部分を抽出することで部分木を抽出するため，抽出さ. 分木の抽出結果は，島モデル GP のパラメータに左右さ. れる部分木の数およびサイズは，島モデルの島数に依存. れるため，事前学習時の島モデル GP において，多くの. すると考えられる．そこで，本節では 5 章の実験におけ. 島数を必要としない問題を解く場合には，提案手法の部. る島モデルの島数と抽出された部分木の数およびサイズ. 分木抽出は効果的に働かないと考えられる．. について解析した．図 4 に各島数で実行された場合に得られた部分木の数. また，図 5 に各島数で実行された場合に得られた部分木のサイズについてのヒストグラムを示す．この図から，.

(7) 回帰問題のための遺伝的プログラミングの自動的な知識利用手法. 51. 表6. 利用頻度が高い部分木 Top3 と利用された対象問題. subtree. target problem ID. cos(x0)*x1. sin(x0)*x1. 図 4 提案手法による島数と抽出される部分木の数の関係. sin(x0)+x1. 表7. 0 1 2 5 7 8 9 10 11 12 14 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 34 35 37 38 39 40 41 42 43 44 45 46 47 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 68 69 0 1 2 3 5 6 7 8 9 10 11 12 14 16 17 18 19 20 21 22 23 25 26 27 28 29 30 31 33 34 35 38 39 40 43 44 45 47 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 66 68 69 0 1 2 3 5 6 7 9 10 11 12 14 16 17 18 19 20 21 23 25 27 28 30 31 34 39 40 42 43 44 45 47 48 50 51 52 53 55 56 57 58 59 61 62 64 66 68. 利用頻度が低い部分木 Top3 と利用された対象問題. subtree exp((cos(x0)*x1)) exp(sin(x0)-x1) exp(cos(x0)-x1). target problem ID 56 68 68. 7 に示す部分木は，実験で用いた全ての対象問題では選択されなかった．つまり，提案した部分木の選択手法に図5. 提案手法による島数と抽出される部分木のサイズの関係. よって，利用されそうな対象問題を選別できた結果であると考えられる．また，部分木がどのような事前問題か. どのような島数であってもサイズが 4 の部分木が最も抽出されやすいことがわかる．また，大きいサイズの部分木は，島数が多い場合にしか出現していないが，島数が多い場合には抽出される部分木数が多いことを考慮すると，大きな部分木の出現割合は島数のパラメータから影響を受けにくいと考えられる．. ら抽出されたかを解析することで，事前問題と対象問題の関係を解析することができるが，利用されやすい部分木は，多くの事前問題でも抽出されやすいため，事前問題と対象問題の関係が多対多になり，関係性を明確することが困難である．そこで，利用頻度が低い部分木について，事前問題と対象問題の関係を解析した．表 7 より，提案手法によって選択される部分木は，一. 6·2 選択された部分木と対象問題の関係. 部の問題でしか選択されない部分木も存在することがわ. 本論文では部分木を選択する手法を提案した．提案し. かる．さらに，表 8 に表 7 に示した部分木が抽出された. た部分木の選択手法は，対象問題毎に適切な部分木を選選択手法の妥当性を検証するために，実験で用いた 70 の. 事前問題を示す．例えば，exp((cos(x0)*x1)) の部分木は ID56 の事前問題でのみ抽出され，ID57 の対象問題のみ利用された．この 2 つは超伝導とポルトガル語のテスト. 対象問題に対して利用されやすい部分木および，利用さ. の問題であるため，明確な関連性を人が考えることは難. れにくい部分木について解析した．表 6，表 7 に利用頻. しい．つまり提案手法は，人が考えることが難しい問題. 度が高かった部分木および利用頻度が低かった部分木に. 間での知識の利用も可能であると考えられる．また，事. おける利用された対象問題を示す．. 前問題と対象問題が似ている例として，exp(cos(x0)-x1). 択する手法である．そこで，本節では提案した部分木の. 表 6 より，提案手法によって選択される部分木は，非. が挙げられる．exp(cos(x0)-x1) は ID67 の事前問題で抽. 常に多くの問題で選択される部分木が存在することがわ. 出され，ID68 の問題で利用された．この 2 つの問題はど. かる．これは，表 6 に示す部分木が，多くの回帰問題に. ちらもワインの品質に関する問題であり，知識の利用が. て汎用的に利用できるためだと考えられる．一方で，表. 可能であると考えられる．.

(8) 進化計算学会論文誌 Vol. 11. 52. 表8. 部分木と抽出元の事前問題の例. subtree. source problem ID. exp((cos(x0)*x1)) exp(sin(x0)-x1) exp(cos(x0)-x1). 57 26 27 61 67 26 27 31 67. 6·3 事前問題の数が与える影響提案手法では，事前問題の数が多いほど，多くの部分木を考慮して選択することができるため，事前問題の数が提案手法の精度に与える影響は大きい．そこで，事前問題の数を制限し，5 章と同じ実験を行うことで，事前問題が少ない場合の提案手法の性能について解析した．このとき，事前問題の数は，10， 20，30，40，50，60 とし，69 個の問題から試行毎にランダムに選択した．図 9 に学習データにおける事前問題の数が提案手法に与える影響を，図 10 にテストデータにおける事前問題の数が提案手法に与える影響を示す．同図では事前問題の数が 60 個である TSGP and XT は TSGP and XT 60 のように表記した．図 9 より，学習データにおいては，事前問題を 60 個利用した場合が，最も性能が良いことがわかる．また，TSGP，TIGP どちらも事前問題を多く用意することで探索性能が向上することがわかる．一方で，テストデータにおいては，図 10 より，事前問題を増やしても，学習データのような単純な精度向上はみられないことがわかる．TSGP，TIGP どちらも事前問題の数が 60 であるときに最良だが，事前問題の数が 30 程度でもほとんど同程度の精度であることがわかる．これは，事前問題の数を増やしても，汎化精度を向上さ得るために必要な部分木の出現は少なくなってしまうためだと考えられる．つまり，提案手法の汎化性能をこれ以上向上させるためには，非常に多くの事前問題および部分木が必要となると考えられる．. 7. ま. と. め. 本論文では，GP における転移学習を用いた汎用的な精度向上手法を提案した．実験では 70 個の異なる実回帰問題に適用し，転移学習を行わない GP と比較して，統計的な精度向上を確認することができた．この結果，転移学習と転移知識の適切な選択を行うことで，問題に依存しない精度向上が可能であることを明らかにした．さらに，提案手法を一般的な機械学習手法と比較した結果，. XGBoost や RandomForest と同程度の精度であることを確認した．そして，提案手法の順位分布の四分位範囲が一般的な機械学習の手法より小さいことから，提案手法によって安定した回帰結果を得られることを確認した．今後の課題として，より多くの問題に対して適用し，提案手法の有効性を検証することが挙げられる．また，本論文にて一般的な機械学習と比較したが，ハイパーパラメータの数の差異などがあり，今後，より大規模な実験. No. 3（2020）. を行い提案手法のハイパーパラメータを調整する必要がある．. ♢ 参考文献 ♢ [Atkinson 18] Atkinson, T., Plump, D., and Stepney, S.: Evolving graphs by graph programming, in European Conference on Genetic Programming, pp. 35–51 (2018) [Berlingerio 12] Berlingerio, M., Koutra, D., Eliassi-Rad, T., and Faloutsos, C.: Netsimile: A scalable approach to size-independent network similarity, arXiv preprint arXiv:1209.2684 (2012) [Chen 16] Chen, T. and Guestrin, C.: Xgboost: A scalable tree boosting system, in Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pp. 785–794ACM (2016) [Clegg 07] Clegg, J., Walker, J. A., and Miller, J. F.: A new crossover technique for cartesian genetic programming, in Proceedings of the 9th annual conference on Genetic and evolutionary computation, pp. 1580–1587 (2007) [Dinh 15] Dinh, T. T. H., Chu, T. H., and Nguyen, Q. U.: Transfer learning in genetic programming, in Evolutionary Computation (CEC), 2015 IEEE Congress on, pp. 1145–1151 (2015) [Elsken 18] Elsken, T., Metzen, J. H., and Hutter, F.: Neural architecture search: A survey, arXiv preprint arXiv:1808.05377 (2018) [Hirasawa 01] Hirasawa, K., Okubo, M., Katagiri, H., Hu, J., and Murata, J.: Comparison between genetic network programming (GNP) and genetic programming (GP), in Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No. 01TH8546), Vol. 2, pp. 1276–1282 (2001) [Hornby 06] Hornby, G. S.: ALPS: the age-layered population structure for reducing the problem of premature convergence, in Proceedings of the 8th annual conference on Genetic and evolutionary computation, pp. 815–822 (2006) [Husa 18] Husa, J. and Kalkreuth, R.: A Comparative Study on Crossover in Cartesian Genetic Programming, in European Conference on Genetic Programming, pp. 203–219 (2018) [Iqbal 17] Iqbal, M., Xue, B., Al-Sahaf, H., and Zhang, M.: Crossdomain reuse of extracted knowledge in genetic programming for image classification, IEEE Transactions on Evolutionary Computation, Vol. 21, No. 4, pp. 569–587 (2017) [Ito 98] Ito, T., Iba, H., and Sato, S.: Non-destructive depthdependent crossover for genetic programming, in European Conference on Genetic Programming, pp. 71–82 (1998) [Ja´skowski 14] Ja´skowski, W., Krawiec, K., and Wieloch, B.: Crosstask code reuse in genetic programming applied to visual learning, International Journal of Applied Mathematics and Computer Science, Vol. 24, No. 1, pp. 183–197 (2014) [Koza 94a] Koza, J. R.: Genetic programming as a means for programming computers by natural selection, Statistics and computing, Vol. 4, No. 2, pp. 87–112 (1994) [Koza 94b] Koza, J. R.: Genetic programming II: Automatic discovery of reusable subprograms, Cambridge, MA, USA, Vol. 13, No. 8, p. 32 (1994) [La Cava 16] La Cava, W., Spector, L., and Danai, K.: Epsilonlexicase selection for regression, in Proceedings of the Genetic and Evolutionary Computation Conference 2016, pp. 741–748 (2016) [La Cava 19] La Cava, W., Silva, S., Danai, K., Spector, L., Vanneschi, L., and Moore, J. H.: Multidimensional genetic programming for multiclass classification, Swarm and evolutionary computation, Vol. 44, pp. 260–272 (2019) [Langdon 99] Langdon, W. B.: Size fair and homologous tree genetic programming crossovers, in Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation-Volume 2, pp. 1092– 1097Morgan Kaufmann Publishers Inc. (1999) [Luke 96] Luke, S. and Spector, L.: Evolving teamwork and coordination with genetic programming, Genetic Programming, Vol. 96, (1996) [Mabu 07] Mabu, S., Hirasawa, K., and Hu, J.: A graph-based evolutionary algorithm: Genetic network programming (GNP) and its.

(9) 回帰問題のための遺伝的プログラミングの自動的な知識利用手法. 53. 14 12 Rank. 10 8 6 4 2 SGP. TSGP and RT. TSGP and XT. IGP. TIGP and RT. TIGP XGBoost Random Gradient MLP and Forest Boost XT Methods. Ada Boost. SVR. Linear. LARS. SGD. SVR. Linear. LARS. SGD. 図 6 学習データにおける提案手法と機械学習の順位分布. 14 12 Rank. 10 8 6 4 2 SGP. TSGP and RT. TSGP and XT. IGP. 図7. TIGP and RT. TIGP XGBoost Random Gradient MLP and Forest Boost XT Methods. Ada Boost. テストデータにおける提案手法と機械学習の順位分布. (sin(x0)*x1). sin(cos(x0)). (sin(x0)/x1). (cos(x0)/x1). add. x4. const. (cos(x0)*x1). x1. x2. add. (sin(x0)/x1). cos(x0)+x1. cos(sin(x0)). (sin(x0)/x1). (sin(x0)/x1). add. cos(sin(x0)). add. x0. x2. add. cos(x0)-x1. x0. x0. const. x0. x0. add. x0. x4. add. add. x0. const. exp. sub. sin(cos(x0)). sin(x0)+x1. const. x0. (cos(x0)*x1). x1. x2. cos(sin(x0)). add. x0. cos(sin(x0)). x4. x3. 図 8 提案手法の木の生成例. extension using reinforcement learning, Evolutionary Computation, Vol. 15, No. 3, pp. 369–398 (2007) [Melo 19] Melo, V. V., Vargas, D. V., and Banzhaf, W.: Batch Tournament Selection for Genetic Programming, arXiv preprint arXiv:1904.08658 (2019) [Miller 99] Miller, J. F.: An empirical study of the efficiency of learning boolean functions using a cartesian genetic programming approach, in Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation-Volume 2, pp. 1135–1142 (1999) [Miller 00] Miller, J. F. and Thomson, P.: Cartesian genetic programming, in European Conference on Genetic Programming, pp. 121– 132 (2000) [Moraglio 12] Moraglio, A., Krawiec, K., and Johnson, C. G.: Geometric semantic genetic programming, in International Conference on Parallel Problem Solving from Nature, pp. 21–31 (2012). [Olson 17] Olson, R. S., La Cava, W., Orzechowski, P., Urbanowicz, R. J., and Moore, J. H.: PMLB: a large benchmark suite for machine learning evaluation and comparison, BioData mining, Vol. 10, No. 1, p. 36 (2017) [O’Neill 17] O’Neill, D., Al-Sahaf, H., Xue, B., and Zhang, M.: Common subtrees in related problems: A novel transfer learning approach for genetic programming, in Evolutionary Computation (CEC), 2017 IEEE Congress on, pp. 1287–1294 (2017) [Orzechowski 18] Orzechowski, P., La Cava, W., and Moore, J. H.: Where are we now? A large benchmark study of recent symbolic regression methods, Proceedings of the Genetic and Evolutionary Computation Conference 2018, pp. 1183–1190 (2018) [Schmidt 11] Schmidt, M. and Lipson, H.: Age-fitness pareto optimization, in Genetic Programming Theory and Practice VIII, pp. 129–146 (2011).

(10) 進化計算学会論文誌 Vol. 11. 54. No. 3（2020）. 14. 12. Rank. 10. 8. 6. 4. 2. SGP. TSGP. TSGP. TSGP. TSGP. TSGP. TSGP. IGP. TIGP. TIGP. TIGP. TIGP. TIGP. TIGP. and. and. and. and. and. and. and. and. and. and. and. and. XT 10. XT 20. XT 30. XT 40. XT 50. XT 60. XT 10. XT 20. XT 30. XT 40. XT 50. XT 60. TIGP. Methods. 図9. 学習データにおける事前問題の数を制限した提案手法. 14. 12. Rank. 10. 8. 6. 4. 2. SGP. TSGP. TSGP. TSGP. TSGP. TSGP. TSGP. TIGP. TIGP. TIGP. TIGP. TIGP. and. and. and. and. and. and. IGP. and. and. and. and. and. and. XT 10. XT 20. XT 30. XT 40. XT 50. XT 60. XT 10. XT 20. XT 30. XT 40. XT 50. XT 60. Methods. 図 10. テストデータにおける事前問題の数を制限した提案手法. [Scott 17] Scott, E. O. and De Jong, K. A.: Multitask evolution with cartesian genetic programming, arXiv preprint arXiv:1702.02217 (2017) [Scott 19] Scott, E. O. and De Jong, K. A.: Automating Knowledge Transfer with Multi-Task Optimization, in 2019 IEEE Congress on Evolutionary Computation (CEC), pp. 2252–2259IEEE (2019) [Spector 12] Spector, L.: Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report, in Proceedings of the 14th annual conference companion on Genetic and evolutionary computation, pp. 401–408 (2012) [Suganuma 17] Suganuma, M., Shirakawa, S., and Nagao, T.: A genetic programming approach to designing convolutional neural network architectures, in Proceedings of the Genetic and Evolutionary Computation Conference, pp. 497–504 (2017) [Wang 19] Wang, N., Xu, Q., Fei, R., Yang, J., and Wang, L.: Rigorous Analysis of Multi-Factorial Evolutionary Algorithm as MultiPopulation Evolution Model, International Journal of Computational Intelligence Systems, Vol. 12, No. 2, pp. 1121–1133 (2019) [Wolpert 95] Wolpert, D. H., Macready, W. G., et al.: No free lunch theorems for search, Technical report, Technical Report SFI-TR-9502-010, Santa Fe Institute (1995) [Wolpert 97] Wolpert, D. H. and Macready, W. G.: No free lunch theorems for optimization, IEEE transactions on evolutionary computation, Vol. 1, No. 1, pp. 67–82 (1997). 〔担当委員：小野景子〕. 2020 年 03 月 30 日受理. 著者. 紹. 介. 加藤慎二 2018 年サレジオ工業高等専門学校専攻科卒業．2020 年横浜国立大学大学院環境情報学府情報環境専攻博士前期課程修了．現在，同博士後期課程在学中．進化計算法の知能情報学の研究に従事．. 長尾智晴（一般会員） 1985 年東京工業大学大学院総合理工学研究科博士課程後期中退．同年同大学助手．同大学助教授を経て 2001 年横浜国立大学大学院環境情報研究院教授．工学博士．画像処理，進化計算法などの知能情報処理学の研究に従事．情報処理学会，電子情報通信学会，人工知能学会，電気学会，進化計算学会，IEEE 等各会員.

(11)