機械学習：標本の重み付け：　バギングと独自性

ファイナンス機械学習―金融市場分析を変える機械学習アルゴリズムの理論と実践

分類器のバギングと独自性

$${I}$$個の要素を持つ集合から$${I}$$回の復元抽出を行うとき、ある要素$${i}$$が選ばれない確率は、$${(1-I^{-1})^I}$$、これをサンプル数を無限にして極限を取ると、$${\lim_{I \to \infty}(1-I^{-1})^{I}=e^{-1}}$$、であり、選ばれない（out_of_bag）は全体の$${1/e=1/3}$$となる。
　一方、同じ$${I}$$個の要素の中で、重複のない物の最大個数を$${K,K\lt I}$$とする。$${I}$$回の復元抽出を行い、重複のない要素$${i}$$を選ばない確率は、$${(1-K^{-1})^I}$$、$${\tau=\frac{K}{I}}$$
$${\lim_{I \to \infty}(1-K^{-1})^{I}=\lim_{I \to \infty}(1-(\tau I)^{-1})^{\tau I \cdot 1/\tau}=e^{-1 \cdot I/K} }$$
　重複のある要素がサンプリングされる確率は$${\frac{I}{K} \ge 1}$$で、IIDを仮定すると、過剰にサンプリングされることになる。
　よって、選ばれたサンプリングは互いに重複し合い、過剰適合を起こしやすくなっている。
　重複度の高い観測値でバギングを行う場合は、平均独自性を使い、観測値lから、この平均独自性の割合で抽出を行う。
　BaggingClassifierの引数、max_sampleを、max_sample=out['tW].mean()と指定する。これによって、独自性の高いサンプルは、その独自性より高い頻度で選ばれることはない。　
　RandomForestにはmax_sample機能はないので、アンサンブルでDecisionTreeを多く合成する方法を取る。

逐次ブーストラップ

　冗長性をコントロールするように、サンプリングの度に確率を変動させる。

• 1回目：観測値$${X_i}$$を一様分布から抽出する。任意のある$${X_i}$$を選ぶ確率は、$${\delta^{(1)}=I^{-1}}$$である。

• 2回目: ここで、$${X_i}$$と重複度の高い$${X_j}$$の抽出確率を減らしたい。ブーストラップであるから、$${X_i}$$が再び選ばれる確率もゼロではない。ここで、すでに選ばれている要素を$${\phi,\phi^{(1)}=\{i\}}$$と置く。これを用いて、時刻$${t}$$における観測値$${X_j,j=1\dots I}$$の独自性を、$${u^{(2)}_{t,j}=\bm{1}_{t,j}/(1+\sum_{k \in \phi}\bm{1}_{t,k})}$$と修正し、各平均独自性も$${\bar{u}^{(2)}_j=\sum^{T}_{\tau=1}u^{(2)}_{\tau,j}/\sum^{t}_{\tau}\bm{1}_{\tau,j}}$$と変更される。これを用いて、2回目の抽出を行う確率を$${\delta^{(2)}_j=\bar{u}^{(2)}_j/\sum^{I}_{k=1}\bar{u}^(2)_k}$$とする。

• $${\phi^{(2)}}$$を更新し、2回目と同じ手順で$${\delta^{(3)}_j}$$を計算する。

数値例

ラベル$${y_i,i=1,2,3}$$がある。
$${y_1}$$はリターン$${r_{0,3},t=0,1,2}$$、$${y_2}$$はリターン$${r_{2,4},t=2,3}$$、$${y_3}$$はリターン$${r_{4,6},t=4,5}$$の関数であるとする。
インディケータ行列は、
$${bm{1}=\displaystyle{\begin{bmatrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0& 1\\ \end{bmatrix}}}$$
と与えられる

• 1回目：$${\phi=\empty,\delta^{(1)}_i=1/3 \forall i=1,2,3 }$$。ここで、$${y_2}$$が選ばれたとする。

• 2回目：$${\phi=\{2\}}$$から、$${u^{(2)}=\bm{1}/(1+\bm{1}_{t,2})=\displaystyle{\bm{1}/ \begin{bmatrix}1 \\ 1 \\ 2 \\ 2 \\ 1 \\ 1\\ \end{bmatrix}=\begin{bmatrix} \bm{1}_{0,j} \\ \bm{1}_{1,j} \\ \frac{1}{2}\bm{1}_{2,j} \\ \frac{1}{2}\bm{1}_{3,j} \\ \bm{1}_{4,j} \\ \bm{1}_{5,j}\\ \end{bmatrix} = \begin{bmatrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1/2 & 1/2 & 0 \\ 0 & 1/2 & 0 \\ 0 & 0 & 1 \\ 0 & 0& 1\\ \end{bmatrix} }}$$。よって、$${u^{(2)}_1=\displaystyle\frac{1+1+1/2}{3}=\frac{5}{6}}$$、$${u^{(2)}_2=\displaystyle\frac{1/2+1/2}{2}=\frac{1}{2}}$$、$${u^{(2)}_3=\displaystyle\frac{1+1}{2}=1}$$。これを規格化して、$${\delta^{(2)}_1=\frac{5}{14},\delta^{(2)}_2=\frac{3}{14},\delta^{(2)}_3=\frac{3}{7}}$$となり、重複のない$${y_3}$$が選ばれる確率が高くなる。ここで、$${y_3}$$が選ばれたとする。

• 3回目：$${\phi=\{2,3\}}$$から、$${u^{(3)}=\bm{1}/(1+\bm{1}_{t,2}+\bm{1}_{t,3})=\displaystyle{\bm{1}/ \begin{bmatrix}1 \\ 1 \\ 2 \\ 2 \\ 2 \\ 2\\ \end{bmatrix}=\begin{bmatrix} \bm{1}_{0,j} \\ \bm{1}_{1,j} \\ \frac{1}{2}\bm{1}_{2,j} \\ \frac{1}{2}\bm{1}_{3,j} \\ \frac{1}{2}\bm{1}_{4,j} \\ \frac{1}{2}\bm{1}_{5,j}\\ \end{bmatrix} = \begin{bmatrix}1 & 0 & 0 \\ 1 & 0 & 0 \\ 1/2 & 1/2 & 0 \\ 0 & 1/2 & 0 \\ 0 & 0 & 1/2 \\ 0 & 0& 1/2\\ \end{bmatrix} }}$$。よって、$${u^{(3)}_1=\displaystyle{ \frac{5}{6}}}$$、$${u^{(3)}_2=\displaystyle{\frac{1}{2}}}$$、$${u^{(3)}_3=\displaystyle\frac{1/2+1/2}{2}=\frac{1}{2}}$$。これから、$${\delta^{(3)}_1=\frac{5}{11},\delta^{(3)}_2=\frac{3}{11},\delta^{(3)}_3=\frac{3}{11}}$$となる。

実装

インディケータ行列の実装はスニペット4.3、平均持続性の計算の実装はスニペット4.4、逐次ブーストラップからの抽出の実装はスニペット4.5で与えられ、これらを用いた逐次ブーストラップの例は、スニペット4.6で行われている。

def getIndMatrix(barIx,t1):
    # Get Indicator matrix
    indM=(pd.DataFrame(0,index=barIx,columns=range(t1.shape[0])))
    for i,(t0,t1) in enumerate(t1.items()):indM.loc[t0:t1,i]=1.
    return indM

def getAvgUniqueness(indM):
    # Average uniqueness from indicator matrix
    c=indM.sum(axis=1) # concurrency
    u=indM.div(c,axis=0) # uniqueness
    avgU=u[u>0].mean() # avg. uniqueness
    return avgU

def seqBootstrap(indM,sLength=None):
    # Generate a sample via sequential bootstrap
    if sLength is None:sLength=indM.shape[1]
    phi=[]
    while len(phi)<sLength:
        avgU=pd.Series(dtype='float64')
        for i in indM:
            indM_=indM[phi+[i]] # reduce indM
            avgU.loc[i]=getAvgUniqueness(indM_).iloc[-1]
        prob=avgU/avgU.sum() # draw prob
        phi+=[np.random.choice(indM.columns,p=prob)]
    return phi

def main():
    np.random.seed(1251) 
    t1=pd.Series([2,3,5],index=[0,2,4]) # t0,t1 for each feature obs
    barIx=range(t1.max()+1) # index of bars
    indM=getIndMatrix(barIx,t1)
    phi=np.random.choice(indM.columns,size=indM.shape[1])
    print('Random Choice:',phi)
    print(f'Standard uniqueness: {getAvgUniqueness(indM[phi]).mean():.4f}')
    phi=seqBootstrap(indM)
    print('Sequential Boostrap:',phi)
    print(f'Sequential uniqueness: {getAvgUniqueness(indM[phi]).mean():.4f}')
    
main()