日: 2024年11月6日

“Understanding Machine Learning” Lemma19.2 について

概要

(Shalev-Shwartz and Ben-David 2009) を読んでいる。ふと定理の数式を実験できないかと考えた。

lemma 19.2

詳細は省くが、以下のような数式がある。 これを実験できないか？

\[ \underset{S \sim \mathcal{D}^m}{\mathbb{E}}\left[\sum_{i: C_i \cap S=\emptyset} \mathbb{P}\left[C_i\right]\right] \leq \frac{r}{m e} \]

コード

\(\mathcal{D}^m\) を 0 から 1000000 の値を一様に出力する確率分布だとして実験する。 

import numpy as np

def D(size, low=0, high=1000000):
    return np.random.randint(X_low, X_high, size)
def P(n, low=0, high=1000000):
    return n / (X_high - X_low)

m = 2000
r = 10
C = D((r, 10))

N = 100
lst_sum_P = []
for _ in range(N):
    sum_P = 0
    S = D(m)
    for i in range(r):
        if np.intersect1d(S, C[i]).size == 0:
            pass
        else:
            sum_P += P(C[i].size)
    lst_sum_P.append(sum_P)

np.mean(lst_sum_P) <= r / (m * np.e)

True

参考文献

Shalev-Shwartz, Shai, and Shai Ben-David. 2009. Understanding Machine Learning. Cambridge University Press. https://doi.org/10.1017/cbo9781107298019.