Site cover image

Site icon imageSen(Qian)’s Memo

This website is Donglin Qian (Torin Sen)’s memo, especially about machine learning papers and competitive programming.
2024-04-10
講義ノート統計的機械学習

(講義ノート)統計的機械学習第1回

記号

入力はx∈Xx \in \mathcal{X}であり、出力はy∈Yy \in \mathcal{Y}とする。

h:X→Yh : \mathcal{X} \to \mathcal{Y}を仮説=Hypothesisという。h∈Hh \in \mathcal{H}とする。1つのモデルH\mathcal{H}はパラメタを変えることで複数の仮説hhを作る、という感じ。

l:(X×Y)×H→Rl : (\mathcal{X \times Y}) \times \mathcal{H} \to \mathbb{R}を損失関数という。入力を仮説に入れた予測結果と真の結果を受け取ることで、それらの距離を測り、それを最適化するということになる。

汎化は何がカギか

  • どのモデル=関数集合を使うか
  • どの損失関数を最小化するか

この2つそれぞれに対して、汎化の理論を作る必要がある。

確率不等式

確率不等式での評価が主である。基本的によく使われる記法は以下の通り。

ϵ>0,δ∈[0,1],P[L≤ϵ]>1−δ\epsilon > 0, \delta \in [0, 1], P[L \leq \epsilon] > 1 - \delta

損失関数LLがϵ\epsilonより小さい確率は、少なくとも1−δ1 - \deltaだけの確率がある。

これを逆にしたP[L>ϵ]≤δP[L > \epsilon] \leq \deltaのほうが数式の取り扱いでは楽だったりするけど。

データの設定

真のデータ生成分布をD\mathcal{D}とする。そこからnn個のサンプルは独立に選択され=i.i.d、{(xi,yi)}i=1n\{ (x_i, y_i) \}_{i=1}^nで得られ、(xi,yi)∼D(x_i, y_i) \sim \mathcal{D}と書くことができる。

すでに得られたサンプルたちを使って○○をやるときは、経験○○という名前がつく。

例えば、経験分布Sn\mathcal{S}_nは以下のように定義できる。各データごとに1/n1/nの重みが付与されており、生成されたら1、そうじゃなかったら0として扱ったときの分布である。

Sn=1n∑i=1n1[(x,y)=(xi,yi)]\mathcal{S}_n = \frac{1}{n} \sum _{i=1}^n \mathbf{1}[(x,y)=(x_i, y_i)]

期待損失と経験損失

期待損失とは、理想的な真のデータ生成分布の元での損失である。

L(h)=E(x,y)∼D[l((x,y),h)]L(h) = \mathbb{E} _{(x,y) \sim \mathcal{D}} [l((x,y),h)]

だが現実では、期待値はサンプルからの経験で代替するしかない。以下の経験損失を使うことになる(以下の期待値は経験分布についての期待値の意味である)

L^n(h)=E(x,y)∈Sn[l((x,y),h)]=1n∑i=1nl((xi,yi),h)\hat{L}_n(h) = \mathbb{E} _{(x,y) \in \mathcal{S}_n} [l((x,y),h)] = \frac{1}{n} \sum_{i=1}^n l((x_i, y_i),h)

我々にできるのは、h∈Hh \in \mathcal{H}を選んで経験損失L^n(h)\hat{L}_n(h)を最小化することしかない。

Tips: h^\hat{h}はサンプルから訓練されるので、サンプルを変数としてh^(Sn)\hat{h}(\mathcal{S}_n)と書くこともある。ただしこれは仮説hhにSn\mathcal{S}_nを直接与えてるわけではなく、便宜的な書き方である。

汎化誤差

汎化理論で示す主な確率不等式は以下のようになる。

PSn∼D[L(h^(Sn))−L(h∗)≤ϵ]>1−δP _{\mathcal{S}_n \sim \mathcal{D}} [L(\hat{h}(\mathcal{S}_n)) - L(h^*) \leq \epsilon] > 1 - \delta

つまり経験誤差と期待誤差は、1−δ1 - \delta以上の確率で必ずϵ\epsilonに収まるという流れを作りたい。

これを示していきたい。まずは(1)以下の式が成り立つことを示す。

L(h^)−L(h∗)≤L(h^)−L^n(h^)+L^n(h∗)−L(h∗)L(\hat{h}) - L(h^*) \leq L(\hat{h}) - \hat{L}_n(\hat{h}) + \hat{L}_n(h^*) - L(h^*)
証明

右辺でL^n(h∗)−L^n(h^)≥0\hat{L}_n(h^*) - \hat{L}_n(\hat{h}) \geq 0を示せればよい。L^n\hat{L}_nにおいての最適な仮説はh^\hat{h}なので、これは自明に示せた。

なお、この式を出すのは本来、以下のように足して0になるものを複数挟み込んでいる。

L(h^)−L(h∗)={L(h^)−L^n(h^)}+{L^n(h^)−L^n(h∗)}+{L^n(h∗)−L(h∗)}L(\hat{h}) - L(h^*) = \{L(\hat{h}) - \hat{L}_n(\hat{h})\} + \{ \hat{L}_n(\hat{h}) - \hat{L}_n(h^*)\} + \{\hat{L}_n(h^*) - L(h^*)\}

これによって、真ん中のものは上の議論によって自明に負であるので、取り除いたら不等式ができる。これで証明の構えを作りたい。

(1)で示した式を前半L(h^)−L^n(h^)L(\hat{h}) - \hat{L}_n(\hat{h})と後半L^n(h∗)−L(h∗) \hat{L}_n(h^*) - L(h^*)と分割することができる。

  • 後半L^n(h∗)−L(h∗)\hat{L}_n(h^*) - L(h^*)は、h∗h^*は訓練サンプル集合に関係なく固定値であるので、確率的に変動する独立なnn個のサンプルを入力した損失関数の和によってのみ変わる。独立なので、扱いやすい。
    • 大数の弱法則で0へ収束すること、中心極限定理についてはO(1/n)O(1/\sqrt{n})のオーダになるなどと扱える。
  • 前半L(h^)−L^n(h^)L(\hat{h}) - \hat{L}_n(\hat{h})はh^\hat{h}が訓練サンプル集合によって変わるのが後半と違うところ。これによって、既存の各道具を使うのは難しい。
    • ここをがんばるのが、統計的機械学習です。

講義ノート統計的機械学習