読者です 読者をやめる 読者になる 読者になる

daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

次元下げ part2

前回
daruma3940.hatenablog.com

f:id:daruma3940:20160520223745p:plain
さあ今回からApery-twigの次元下げの部分を詳しく見ていくのじぇ。
詳しくって行ってもまずはだいたいどんなことをしているのか把握することからはじめようじぇ。
f:id:daruma3940:20160520223745p:plain
まず次元下げが行われている関数は learnParse2()関数の中の

lowerDimension(parse2EvalBase_, parse2Data_.params);

のとこなのじぇ
この関数の引数のparse2Data_.paramsっていうのがparse2bodyで計算された
教師データに出てくる特徴量には加点、教師データに出てこない特徴量には減点をされた特徴量のことなのじぇ。
そしてparse2EvalBase_っていうのが
parse2Data_.paramsから作られた、次元下げ特徴量が格納されていくEvaluaterBase構造体の実態だと考えられるのじぇ。

f:id:daruma3940:20160520223745p:plain
さあここで一旦次元下げにはどのような次元下げがあるのか知っておくために一旦EvaluaterBase構造体の中身を見てみようじぇ?


template <typename KPPType, typename KKPType, typename KKType> struct EvaluaterBase {


	static const int R_Mid = 8; // 相対位置の中心のindex
	constexpr int MaxWeight() const { return 1 << 22; } // KPE自体が1/32の寄与。更にKPEの遠隔駒の利きが1マスごとに1/2に減衰する分(最大でKEEの際に8マス離れが2枚)
														// 更に重みを下げる場合、MaxWeightを更に大きくしておく必要がある。
														// なぜか clang で static const int MaxWeight を使っても Undefined symbols for architecture x86_64 と言われる。

	constexpr int TurnWeight() const { return 8; }//手番につける重み

	/*17という数字が入っているのは相対位置きふわらべのアピール文書参照*/

	// 冗長に配列を確保しているが、対称な関係にある時は常に若いindexの方にアクセスすることにする。
	// 例えば kpp だったら、k が優先的に小さくなるようする。左右の対称も含めてアクセス位置を決める。
	// ただし、kkp に関する項目 (kkp, r_kkp_b, r_kkp_h) のみ、p は味方の駒として扱うので、k0 < k1 となるとは限らない。
	struct KPPElements {
		KPPType dummy; // 一次元配列に変換したとき、符号で += を表すようにしているが、index = 0 の時は符号を付けられないので、ダミーを置く。
		KPPType kpp[SquareNoLeftNum][fe_end][fe_end];

		// 相対位置は[file][rank]の順
		KPPType r_kpp_bb[PieceNone][17][17][PieceNone][17][17];
		KPPType r_kpp_hb[fe_hand_end][PieceNone][17][17];
		KPPType xpp[FileNoLeftNum][fe_end][fe_end];
		KPPType ypp[RankNum][fe_end][fe_end];
		KPPType pp[fe_end][fe_end];
		KPPType r_pp_bb[PieceNone][PieceNone][17][17];
		KPPType r_pp_hb[fe_hand_end][PieceNone];

		// e は Effect の頭文字で利きを表す。(Control = 利き という説もあり。)
		// todo: 玉の利きは全く無視しているけれど、それで良いのか?
		KPPType kpe[SquareNoLeftNum][fe_end][ColorNum][SquareNum];
		KPPType kee[SquareNoLeftNum][ColorNum][SquareNum][ColorNum][SquareNum];
		KPPType r_kpe_b[PieceNone][17][17][ColorNum][17][17];
		KPPType r_kpe_h[fe_hand_end][ColorNum][17][17];
		KPPType r_kee[ColorNum][17][17][ColorNum][17][17];
		KPPType xpe[FileNoLeftNum][fe_end][ColorNum][SquareNum];
		KPPType xee[FileNoLeftNum][ColorNum][SquareNum][ColorNum][SquareNum];
		KPPType ype[RankNum][fe_end][ColorNum][SquareNum];
		KPPType yee[RankNum][ColorNum][SquareNum][ColorNum][SquareNum];
		KPPType pe[fe_end][ColorNum][SquareNum];
		KPPType ee[ColorNum][SquareNum][ColorNum][SquareNum];
		KPPType r_pe_b[PieceNone][ColorNum][17][17];
		KPPType r_pe_h[fe_hand_end][ColorNum];
		KPPType r_ee[ColorNum][ColorNum][17][17];
	};
	KPPElements kpps;//実態を作っている

	struct KKPElements {
		KKPType dummy; // 一次元配列に変換したとき、符号で += を表すようにしているが、index = 0 の時は符号を付けられないので、ダミーを置く。
		KKPType kkp[SquareNoLeftNum][SquareNum][fe_end];
		KKPType kp[SquareNoLeftNum][fe_end];
		KKPType r_kkp_b[17][17][PieceNone][17][17];
		KKPType r_kkp_h[17][17][fe_hand_end];
		KKPType r_kp_b[PieceNone][17][17];
		KKPType r_kp_h[fe_hand_end];

		KKPType kke[SquareNoLeftNum][SquareNum][ColorNum][SquareNum];
		KKPType ke[SquareNoLeftNum][ColorNum][SquareNum];
		KKPType r_kke[17][17][ColorNum][17][17];
		KKPType r_ke[ColorNum][17][17];
	};
	KKPElements kkps;

	struct KKElements {
		KKType dummy; // 一次元配列に変換したとき、符号で += を表すようにしているが、index = 0 の時は符号を付けられないので、ダミーを置く。
		KKType kk[SquareNoLeftNum][SquareNum];//kの左側抜きとkの全場所
		KKType k[SquareNoLeftNum];//kの左側抜き
		KKType r_kk[17][17];//kkの相対位置
	};
	KKElements kks;

	// これらは↑のメンバ変数に一次元配列としてアクセスする為のもの。
	// 配列の要素数は上のstructのサイズから分かるはずだが無名structなのでsizeof()使いにくいから使わない。
	// 先頭さえ分かれば良いので要素数1で良い。
	KPPType* oneArrayKPP(const u64 i) { return reinterpret_cast<KPPType*>(&kpps) + i; }
	KKPType* oneArrayKKP(const u64 i) { return reinterpret_cast<KKPType*>(&kkps) + i; }
	KKType* oneArrayKK(const u64 i) { return reinterpret_cast<KKType*>(&kks) + i; }

	// todo: これらややこしいし汚いので使わないようにする。
	//       型によっては kkps_begin_index などの値が異なる。
	//       ただ、end - begin のサイズは型によらず一定。
	constexpr size_t kpps_end_index() const { return sizeof(kpps)/sizeof(KPPType); }
	constexpr size_t kkps_end_index() const { return sizeof(kkps)/sizeof(KKPType); }
	constexpr size_t kks_end_index() const { return sizeof(kks)/sizeof(KKType); }

(省略)

f:id:daruma3940:20160521003616p:plain
この辺りはきふわらべさんのアピール文書にも詳しい解説があるわね
http://www.computer-shogi.org/wcsc26/appeal/KifuWarabe/appeal.pdf

f:id:daruma3940:20160709192554j:plain
上のコードの中の構造体KPPElements,KKPElements,KKElementsの中身が次元下げの種類なのかな?
それにしてもいっぱいあるね....
でも
r_(relative) 相対
k(king) 王
p(piece)王以外の駒
e(effect)利き  
x(横方向)
y(縦方向)
b(board) 盤上の駒
h(hand) 手駒

ということがわかっていればなんとか意味はわかってくるね...

f:id:daruma3940:20160520223530p:plain
KPPElements構造体はone_arrayKPPという関数で構造体の先頭ポインタを配列の先頭とした1次元配列としても表現されるんだね!

f:id:daruma3940:20160520223745p:plain
ここで lowerDimension()関数にもどってこようじぇ
まずはlowerDimension()関数中のKPPの次元下げの部分から読んでいこうじぇ!
KPP次元下げがKKP、KKよりも難しいはずなので
ここが何をしているのかわかればKKP,KKの次元下げが何をしているかも必然的に理解できるはずなのじぇ!

// KPP
	{

		for (int ksq = I9; ksq < SquareNum; ++ksq) {//王の全マスについて

			std::pair<ptrdiff_t, int> indices[base.KPPIndicesMax];//indexと重みがペアになっている

			//kppの全要素についてのループ
			for (int i = 0; i < fe_end; ++i) {
				for (int j = 0; j < fe_end; ++j) {


					/*
					kppIndices()
					 KPP に関する相対位置などの次元を落とした位置などのインデックスを全て返す。
					 負のインデックスは、正のインデックスに変換した位置の点数を引く事を意味する。
					0 の時だけは正負が不明だが、0 は歩の持ち駒 0 枚を意味していて無効な値なので問題なし。
					 ptrdiff_t はインデックス、int は寄与の大きさ。MaxWeight分のいくつかで表記することにする。
					ここで次元下げした要素のindexとそのindex番目がどれぐらい最終的なKPPに寄与するのかを計算している。
					*/
					base.kppIndices(indices, static_cast<Square>(ksq), i, j);

					//raw.kpp_raw[ksq][i][j]がbase.oneKPPに足される
					FOO(indices, base.oneArrayKPP, raw.kpp_raw[ksq][i][j]);//目的関数の計算により得られたkpp_raw[ksq][i][j]と上の関数によって作られたindexと重みを利用して一次元化された次元下げ特徴ベクトルに値が代入される

				}
			}
		}
	}

f:id:daruma3940:20160520223745p:plain
std::pair(ptrdiff_t, int) indices[base.KPPIndicesMax];
というのは
ptrdiffがポインタ差分のことでさっきれいみゅが言ってた一次元配列化されたKPPElementsの先頭ポインタからいま注目している次元下げ要素のポインタまでどれぐらい離れているか
つまりindexみたいなもので、intがそのindexがどれだけ最終的なKKPに寄与しているのかを表す重みということなのじぇ。

ここでbase.KPPIndicesMax=3000という値が割り振られているのじぇ。
ということはindicesは大きさ3000の配列ということになるけれどなんで3000なのかはよくわからないのじぇ。

このindicesの<インデックス、重み>をきめるのがbase.kppIndices(indices, static_cast(ksq), i, j);関数で
indicesとparse2で計算された次元サゲされていない特徴ベクトル(raw.kpp_raw[ksq][i][j])を用いて次元サゲされた要素に値を入れていくのがFOO()関数マクロなのじぇ!!


ここで上に出てきたマクロFOOの中身はこんな感じなのじぇ
まあ目的関数の計算により得られたkpp_raw[ksq][i][j]と上の関数によって作られたindexと重みを利用して一次元化された次元下げ特徴ベクトルに値が代入するための関数マクロだと思っておけばいいと思うのじぇ。

//ptrdiff_t:ポインタ同士の減算
	//indexandweightのfirstがnumeric_limits::maxであればbreak;
	//oneArreyが元となる特徴ベクトル値、 sum[0] * indexAndWeight.second / base.MaxWeight()が特徴ベクトルに足される値
	/*
	indexAndWeight.firstが正の場合と負の場合で
	ADDかSUBか(-indexAndWeight.first)の符号をどうするかを変更する
	*/
	/*========================
	このFOOによって次元下げされた要素の配列に
	値が代入される!!!!
	========================*/
	//define FOOはここから
#define FOO(indices, oneArray, sum)										\
	for (auto indexAndWeight : indices) {								\
		if (indexAndWeight.first == std::numeric_limits<ptrdiff_t>::max()) break; \
		if (0 <= indexAndWeight.first) {								\
			atomicAdd((*oneArray( indexAndWeight.first))[0], sum[0] * indexAndWeight.second / base.MaxWeight()); \
			atomicAdd((*oneArray( indexAndWeight.first))[1], sum[1] * indexAndWeight.second / base.MaxWeight()); \
		}																\
		else {															\
			atomicSub((*oneArray(-indexAndWeight.first))[0], sum[0] * indexAndWeight.second / base.MaxWeight()); \
			atomicAdd((*oneArray(-indexAndWeight.first))[1], sum[1] * indexAndWeight.second / base.MaxWeight()); \
		}																\
	}


// float 型の atomic 減算
//memory_order_consume:異なるスレッド使用時のメモリ消費命令
//compare_exchange_weak:弱い比較で値を入れ替える
//現在の値とexpectedをバイトレベルで等値比較を行い、trueである場合は現在の値をdesiredで置き換え、falseである場合はexpectedを現在の値で置き換える。
inline float atomicSub(std::atomic<float> &x, const float diff) {
	float old = x.load(std::memory_order_consume);
	float desired = old - diff;
	//xの中身がoldと同じにならない間desiredをoldに代入し、desiredをdiffだけ増やす
	while (!x.compare_exchange_weak(old, desired, std::memory_order_release, std::memory_order_consume))
		desired = old - diff;

	return desired;
}


// float 型の atomic 加算(他スレッド時に用いる。)
inline float atomicAdd(std::atomic<float> &x, const float diff) {
	float old = x.load(std::memory_order_consume);
	float desired = old + diff;

	//xの中身がoldと同じにならない間desiredをoldに代入し、desiredをdiffだけ増やす
	while (!x.compare_exchange_weak(old, desired, std::memory_order_release, std::memory_order_consume))
		desired = old + diff;

	return desired;
}

f:id:daruma3940:20160520223745p:plain
one_Arrayが何なのかがわかってくると
評価値ベクトルを更新し、ファイルに書き出す関数updateEval()も何やってたのかよくわかってくるのじぇ。

//特徴ベクトルの更新&書き出し
	template <bool UsePenalty>
	void updateEval(const std::string& dirName) {

		//特徴ベクトルの更新
		for (size_t i = 0; i < eval_.kpps_end_index(); ++i)
			//第一引数:特徴ベクトル	第二引数:目的関数の微分(without 罰金項)
			updateFV<UsePenalty>(*eval_.oneArrayKPP(i), *parse2EvalBase_.oneArrayKPP(i));
		for (size_t i = 0; i < eval_.kkps_end_index(); ++i)
			updateFV<UsePenalty>(*eval_.oneArrayKKP(i), *parse2EvalBase_.oneArrayKKP(i));
		for (size_t i = 0; i < eval_.kks_end_index(); ++i)
			updateFV<UsePenalty>(*eval_.oneArrayKK(i), *parse2EvalBase_.oneArrayKK(i));

      eval_.write(dirName);//更新した特徴ベクトルの値をここでファイルに書き出す。
		eval_.init(dirName, false);//書きだした値をもう一度読み込む
(省略)

f:id:daruma3940:20160521003616p:plain
なるほど。低次元化された値を使って特徴量ベクトルを更新していたのね....

f:id:daruma3940:20160520223745p:plain
ここまでの内容をまとめると

learnParse2で特徴ベクトルの更新分を計算
それをlowerDimension()で次元下げしてから
updateEval()で実際に更新!

ということなのじぇ。
f:id:daruma3940:20160520223745p:plain
今回の記事はわかりにくすぎるのじぇ。自分でもそう思うのじぇ。
でもこの辺りどうやってストーリー付けしながら文章に起こせばいいのか難しいところなのじぇ。堪忍して欲しいのじぇ。
f:id:daruma3940:20160520223745p:plain
次回はbase.kppIndices(indices, static_cast(ksq), i, j);の中でどのようにしてindexと重みが生成されているのかを理解できればいいなと思っているのじぇ!
学習のPhaseの理解もしたいけど後回しにするのじぇ!