プログラム自動生成に関する研究

はじめに

先日 Google から AutoML-Zero という機械学習のプログラムを自動生成する手法が発表された。

プログラム自動生成手法自体は以前から多く存在したが、実用的なレベルのものが出てきたことで、今後はプログラムの自動生成に関する研究もより盛んに行われるものと考えらる。

AutoML-Zero では遺伝的プログラミングにおいて突然変異のみによる探索を採用したような手法が採られているが、プログラム自動生成の手法は他にも、遺伝的ネットワークプログラミング、GRAPE(Graph Structured Program Evolution)など様々な手法が存在する。

本研究では GRAPE の改良に関する既存研究で採用されたノード関数の影響 及び 既存手法との組み合わせによるさらなる改良を提案する。

Graph Structured Program Evolution (GRAPE)

GRAPE は遺伝子型が整数列、表現型がグラフ構造をとる遺伝的アルゴリズム手法であり、1つの個体は複数のノードとデータセットを持つ。

1つのノードは

  1. 命令の種類
  2. 移動先
  3. 使用するデータセット

から構成され、複数のノードで構成されたプログラムはスタートノードから開始され、ノードの命令及び使用するデータセットによるデータの操作と移動先への遷移によってプログラムが順次実行され、出力ノードに達するとプログラムは停止し出力が得られる。

先行研究

GRAPE によるプログラム自動生成のベンチマークとして特に成功率が低いフィボナッチ数列を求めるプログラムに着目する。

論文成功率
1.提案論文0.06
2.局所探索0.14
3.線形遺伝子型0.19
4.多様性維持探索0.71
  1. Graph Structured Program Evolution によるプログラムの自動生成
  2. グラフ構造のプログラム自動生成手法のための子個体生成方法の提案
  3. 線形遺伝子型を導入したグラフ構造 GP
  4. プログラム自動生成手法における個体の多様性維持の提案

明らかに4.の研究の成功率が高く、論文では多様性の維持による成果だと結論づけている。

しかし探索方法以外を提案論文と同様の設定で再現実験をしたところ、論文のような高い成功率にはならなかった。

ノード関数の種類

4.の研究はここに挙げた他の論文とは異なり著者はアルゴリズムの提案者ではない。

そのためか実験の条件が異なる点がいくつか存在し、特にノード関数に Swap が含まれるという点で大きく異なる。

後述するいくつかの改善を行った提案手法と、その提案手法から Swap を除いた手法で大きく成功率が変わることを確認した。

Swap が含まれる手法で実際に生成されたプログラムは以下のようなものである。

function main(input)
{
	const data = [];
	data.push(...[...Array(3)].map(() => 0));
	data.push(...[...Array(3)].map(() => 1));
	data.push(...[...Array(4)].map(() => input));
	return func9(data, input);
}

function func9(data, input)
{
	[data[5], data[0]] = [data[0], data[5]];
	return func13(data, input);
}

function func13(data, input)
{
	while(true)
	{
		if (data[3] <= input)
		{
			data[3] += 1;
			data[0] += data[5];
			[data[5], data[0]] = [data[0], data[5]];
			continue;
		}

		return data[5];
	}
}

Swap がない場合、以下のように3つの変数を使用して和を求める処理と一つ前の値を代入する処理2回の計3回の処理をループ内で行う必要がある。

function main(input)
{
	let f0 = 0, f1 = 0, f2 = 1;
	for (let i = 0; i < input; ++i) {
		f0 = f1 + f2;
		f2 = f1;
		f1 = f0;
	}

	return f0;
}

Swap によって計算に必要な変数が2つになり、Swap と加算処理の計2回の処理をループ内で行うことになり、プログラムの生成が容易になっている。

したがってこの既存研究で結論付けられているような多様性が成功率上昇の主要因ではなく、使用されるノード関数が与えられた問題に有利に働いた結果によるものだと考えられる。

シミュレーション

提案手法に以下の改善を追加した結果、成功率は100%になった。

  1. ループ維持のための評価値の導入(学外未発表のため詳細は非公開)
  2. 局所探索+島分割(2.の論文+α)
  3. 初期データの変更(入力値と1 => 入力値と0と1)
  4. Forノードの導入(4.の論文)
  5. Swapノードの導入(4.の論文)

2.の論文での局所探索では親個体を入れ替えながら子個体を生成するが、プログラム高速化のため子個体生成は選択された親個体からのみ生成した。

テストデータでも成功したときの進捗度[0, 1]を記録し、より早く生成が完了するパラメータをざっくりとグリッドサーチを行った。

人口100
島数100
突然変異率0.05
局所子個体数5
進捗度ごとの成功数

ブラウザで動作するデモ
https://technote-space.github.io/ga-framework/samples/automatic-programming/

まとめ

本研究ではプログラム自動生成手法の性能向上に関する先行研究の改善要因の検討を行い、別の改善方法との組み合わせによる提案手法によりフィボナッチ数列を求めるプログラムの自動生成をほぼ確実なものにできることを示した。

より複雑なプログラムである機械学習のプログラムの自動生成手法として登場した AutoML-Zero などの手法でも、有効かつ合理的なノード関数があれば性能向上が望めると考えられる。

GRAPE は 非コード領域を持つ点や一般的な遺伝的アルゴリズムの遺伝的操作の適用が可能な点などAutoML-Zero の個体には存在しないいくつかの特徴があるので、機械学習のプログラム自動生成の探索方法として試してみたい。

コメント

タイトルとURLをコピーしました