「ファイナンス機械学習」CSCVとCPCV

# はじめに
「ファイナンス機械学習」のバックテストPartで登場したCSCVとCPCVを簡単にまとめたいと思います。
CSCV(Combinatorially Symmetric Cross-Validation:組合せ対称交差検証法)
CPCV(Combinatorial Purged Cross-Validation:組合せパージング交差検証法)

ファイナンス機械学習は以下の流れで様々な手法を紹介しています。

１．金融データの特徴を述べる
２．特徴を踏まえて、従来手法もしくは機械学習一般手法を使う問題点を指摘する
３．解決するための手法を紹介する

例えばCVで通常のK-Foldを使うことの問題点としてリークが発生することを指摘し、パージングという手法を紹介しています。

---
### パージング
金融データに限らず、時系列データの予測タスクで目的変数が未来の値の場合、通常のK-Foldスプリットではリークが起きうる。
例えば、ある標本Aが時刻tの説明変数と時刻t+Tの目的変数からなる場合、標本Aは時刻t～t+Tの情報を含むことになる。
trainデータに標本Aがあり、valデータに時刻t+t0(0<t0<T)の標本がある場合、モデルは標本Aから得られた時刻t～t+Tの情報を基に目的変数を推測してしまう。
これを防ぐためにtrainデータとvalデータの間に使用しない期間を設ける。これをパージングと言う。

---

この記事でも同様の流れで手法を紹介していきます。
質問や意見、誤りのご指摘等ありましたらぜひコメントお願いします！


# CSCV
CSCV(Combinatorially Symmetric Cross-Validation:組合せ対称交差検証法)


## 既存手法の問題点
バックテストにはウォークフォワード法という従来手法がある。これの問題点は単一の検証経路で良い結果が出るまで何度もバックテストできるので偽陽性が起きやすく、簡単にオーバーフィットすること。
ウォークフォワード法で選択された戦略はオーバーフィットしている可能性が高い。

バックテスト最適化を避けるためには通常のCVのようなランダム化が必要だが、普通のShuffle K-Foldではリークが発生する。
そこで戦略選択にCSCVを使う。
CSCVではバックテストオーバーフィット確率(PBO)を推定できる。

## CSCVの説明
バックテストで長さ$T$の損益配列が得られるとする。特定のモデル設定で$N$回試行し、長さ$T$の配列を$N$個得て、損益配列を縦に並べて、$(T,N)$行列にする。
この行列を使って、インサンプル(IS)で最高評価となるバックテストでのアウトオブサンプル(OOS)での評価を測り、PBO(probably backtest overfitting:バックテストオーバーフィット確率)を推定する。

1. 行を$S$個のグループに分ける。
2. $S$個のグループから$S/2$個を選び、それらのグループに属する行だけ抜き出して$(T/2,N)$行列を作る。これをインサンプル(IS)行列とする。
3. 同じようにそれらのグループに属さない行だけを抜き出して$(T/2,N)$行列を作る。アウトオブサンプル(OOS)行列とする。
4. 任意の$S/2$個の選び方で以下を計算する。
  IS行列およびOOS行列の各列(=各損益配列)を評価する。評価はシャープレシオなど、なんでもいい。  
  IS行列で最大評価となるカラム$n*$を選ぶ。  
  OOS行列におけるカラム$n*$の順位$w$を記録する。$w$はカラム数で割って$w<1$とする。  
  このwが「ISでの最高評価となるバックテストでのOOSでの評価」である。  
5. 記録した各$w$についてロジット$λ$を計算する。
  $λ=log(w/(1-w))$  
  これはw<0.5で負となり、w>0.5なら正となる。
6. PBOをロジット$λ$の確率分布関数の$-∞〜0$の積分で定義する。  
   実装上は記録した$w$の内、0.5未満になるものの割合がPBOとなる。  
   
PBOは、要は適当に期間を二つに分けて片方で最高評価の試行を選んだ時、もう片方でその試行が上位50%に入らない確率のこと。


## CSCVの実装

```.py

def CSCV(df,n_split,eval=None):
    """
    CSCVでPBOを計算する
    :param df:は(T,N)行列:T期間のバックテストで得た損益配列 x N回の試行
    :param n_split:グループ数
    :param eval:評価関数.Noneの場合シャープレシオ
    """
    if eval is None:# Noneならシャープレシオ
        eval=lambda x:np.mean(x)/np.std(x)
    length=len(df)
    X=df.values

    # 行をn_split個のグループに分ける。
    split_idx=[int(length*i/n_split) for i in range(n_split)]+[length]
    group=[list(range(split_idx[i],split_idx[i+1])) for i in range(n_split)]

    # n_split個のグループを二分する分割方法を列挙。DFSを使う。
    all_split=[]
    q=[[i] for i in range(n_split)]
    while q:
        s=q.pop()
        if len(s)==n_split//2:
            all_split.append(set(s))
            continue
        for i in range(s[-1]+1,n_split):
            q.append(s+[i])
    
    # 分割を1つずつ評価し配列に保存
    w_ary=[]
    for spl in all_split:
        insample=[]
        outsample=[]
        for i in range(n_split):
            if i in spl:
                insample.extend(group[i])
            else:
                outsample.extend(group[i])
        X_is=X[insample,:]
        X_os=X[outsample,:]
        eval_array_is=[]
        eval_array_os=[]
        for i in range(X.shape[1]):
            eval_array_is.append(eval(X_is[:,i]))
            eval_array_os.append(eval(X_os[:,i]))
        n_star=np.argmax(eval_array_is)
        w=sts.rankdata([-x for x in eval_array_os])[n_star]
        w/=X.shape[1]
        w_ary.append(w)
    # PBOを計算
    pbo = len([x for x in w_ary if x<0.5])/len(w_ary)
    return pbo

```

## 所感
正直あまり理解しておらず、使いどころがわかりません。
・N回の試行というのは、同じモデルをパラメータ違いでバックテストしたN回ということ？
・CSCVで得たPBOはどの試行に対する確率なのか？
・N個の中から1つの試行を選択したとき、それがオーバーフィットしている確率がPBOという解釈？
前後の文脈を飛ばしているかもしれません。
何かコメントいただけると嬉しいです。


# CPCV
CPCV(Combinatorial Purged Cross-Validation:組合せパージング交差検証法)

## 既存手法の問題点
ウォークフォワード法には3つの問題点がある。
・単一の経路でバックテストするのでオーバーフィットしやすい。
・特定の順序（ヒストリカル経路）に基づいたものであり、必ずしも本来のパフォーマンスの代表にならない。
・初期の投資判断がごく少数のサンプルにのみ基づいて行われる。
2つめ3つめはパージ付きK-Foldで防ぐことができるが、1つめは回避できない。
CPCVを使えば複数のバックテスト経路を得ることができ、バリアンスを小さくできる。

## CPCVの説明
通常のK-Foldではvalデータとして一つのFoldを選び、他をTrainデータとするが、CPCVではvalデータとして2つのFoldを選び、他をtrainデータとする。
Fold数が$S$なら通常のK-Foldでは$S$個のCVができ、バックテスト経路が1つできるが、CPCVなら$S(S-1)/2$個のCVができ、バックテスト経路は$S-1$個できる。
K-Foldはパージ付きK-Fold。

複数のバックテスト経路ができるので複数の評価が得られ、たまたま評価が上振れた、というケースの影響を小さくできる。
以下の記事が詳しいです。
https://qiita.com/nokomitch/items/ccd2722a4c5ef93a994a#cpcvは何がうれしいのか125節

## CPCVの実装
CPCV用のパージ付きK-Fold

```.py
def KFoldSplitPurgeCPCV(df,n_split=5,n_purge=5):
    """
    CPCV用のK-Fold
    :param df:特徴量と目的変数を格納したDataFrame
    :param n_split:CVの分割数
    :param n_purge:パージングする数
    """
    length=len(df)
    idx=list(range(length))
    ret=[]
    split_idx=[int(length*i/n_split) for i in range(n_split)]+[length]
    for i in range(n_split):
        for j in range(i+1,n_split):
            val_from1=split_idx[i]
            val_to1=split_idx[i+1]
            val_from2=split_idx[j]
            val_to2=split_idx[j+1]
            val_idx1=idx[val_from1:val_to1]
            val_idx2=idx[val_from2:val_to2]
            train_idx=[]
            if val_from1-n_purge>1:
                train_idx+=idx[:val_from1-n_purge]
            if val_to1+n_purge<val_from2-n_purge:
                train_idx+=idx[val_to1+n_purge:val_from2-n_purge]
            if val_to2+n_purge<len(idx):
                train_idx+=idx[val_to2+n_purge:]
            ret.append([train_idx,val_idx1,val_idx2])
    return ret
```

CPCV本体

```.py

def CPCV(df,features,y,model,n_split=5):
    """
    :param df:特徴量と目的変数を格納したDataFrame
    :param feature:特徴量
    :param y:目的変数のカラム
    :param model:評価したいmodel
    :param n_split:CVの分割数
    """
    cv=KFoldSplitPurgeCPCV(df,n_split)
    n_path=n_split-1

    # 結果格納用のDataFrame
    ret=df[[y]]
    for i in range(n_path):
        ret[i]=np.nan
    for train_idx,val_idx1,val_idx2 in cv:
        train_idx=df.index[train_idx]
        val_idx1=df.index[val_idx1]
        val_idx2=df.index[val_idx2]
        model.fit(df.loc[train_idx,features],df.loc[train_idx,y])
        for i in range(n_path):# 対象Foldが未格納のカラムに格納する
            if np.isnan(ret.at[val_idx1[0],i]):
                ret.loc[val_idx1,i]=model.predict(df.loc[val_idx1,features])
                break
        for i in range(n_path):
            if np.isnan(ret.at[val_idx2[0],i]):
                ret.loc[val_idx2,i]=model.predict(df.loc[val_idx2,features])
                break
    return ret

```


## 所感
Fold数を$S$とすると通常のK-Foldに比べ$(S-1)/2$倍の時間がかかる。それ以外にデメリットはない気がするので、実行時間を気にしないなら使った方がよさそう。