数学弱者の奮闘記

数学弱者目線の記事を書いていきます

はじめてのパターン認識(はじパタ) 第2章 2.2.1 解説という名の妄想

はじパタの2章2.2.1で個人的にわかりにくかったところについてお気持ちを解説（妄想）していきます。
やはりはじパタの内容は数学弱者にとって重い。 ちなみに1章の超次元立方体の話は本文で語られているお気持ちだけ理解して、細かい理解はもちろん飛ばしました。

だいぶ妄想なので、合っているかはわかりません。

目次

2.2.1 学習データとテストデータの作り方

(1)ホールドアウト法

いきなり出てくる以下の式の期待値が何なのかがすぐに理解できなかった。

E_{D_L} \{\varepsilon(p_L,\ p_L) \} \le \varepsilon(p,\ p) \le E_{D_T} \{\varepsilon(p_L,\ p_T)\}

本文の説明も理解が難しい。

「 E_{D_L}\{\}は多くの学習データセット D_Lを用いて設計し（以下略） 、 E_{D_T}\{\}は一つの学習データセット p_Lを用いて設計し（以下略）」

いや、意味わからんけど(笑)
わからないが、わからないなりに以下で妄想してみる。

まず、「設計」は、巷で言うところのモデルの訓練（または学習、トレーニング）ということにしておく。もしかしたらモデル選択まで含めているのかもしれないが、まあ訓練ということでいいでしょう。

次に、期待値が一体何なのかについて改めて考えてみたい。
個人的には、期待値は(標本)平均と似たものだと思っている。大数の法則から、(標本)平均 \bar{X}は期待値E[X]に確率収束する。取ってきた標本（データ）の数が多いと、標本平均はE[X]にほぼ等しい。

では、 E_{D_L} \{\varepsilon(p_L,\ p_L) \}はどのような意味なのか。
とある一つのデータセット D_Lが得られたとする。このデータセットで識別器を設計し、同じデータセットでテストをし、誤り率を測定する。これをN回行う。つまり、N回新たなデータセット \{D_L\}_i, \ (i=1,2,...,N)を得て、その度ごとにそのデータセットでテストをし、誤り率を測定する。このN回で得た誤り率の平均 \dfrac{1}{N} \sum_{i=1}^{N}\varepsilon_i(p_L,\ p_L)は、 E_{D_L} \{\varepsilon(p_L,\ p_L) \}に確率収束する。この場合、 E_{D_L} \{\varepsilon(p_L,\ p_L) \}の期待値の計算で使う確率密度関数は \varepsilon(p_L,\ p_L)の確率密度関数である、ということでいいのだろうか。計量経済学をテキスト使いながら学んでいた時にも思ったことだが、期待値に関して曖昧な説明しかしないせいで、この期待値は一体何なんだとなることが多くてイライラする。この手のテキストはいちいち天才を想定しすぎなんだよな。
また、「 E_{D_L}\{\}は多くの学習データセット D_Lを用いて設計し」の「多くの」というのは、多くの \{D_L\}_i, \ (i=1,2,...,N)で期待値（平均）を取るということなのだろう。たぶん。

E_{D_T} \{\varepsilon(p_L,\ p_T)\} に関しては、同様に考えると、「一つのデータセット p_L( D_Lと表記しないのはなぜだろう？)で識別器を設計し、この識別器を数多くのテストデータセット \{D_T\}_i,\ i=1,2,...,Nで測定した誤り率の期待値（≒平均）」ということになるだろうか。
合ってるかは全くわからん（笑）。

(4)ブートストラップ法

これもまぁ意味が分からない。事前知識無しでこれだけ読んで理解できる人はいるのだろうか。
ブートストラップ法については他の本でちゃんと勉強しないといけないんだろうな。 以下でまた妄想を展開していく。

数式の展開

まず、下の脚注にある (1-\dfrac{1}{N})^N の展開がよくわからない。これは単純に数学の勉強不足。テイラー展開だとは思うが、、、。
代わりに、以下のように考えると同じ結果が得られるので、別解を紹介する。 (ここを参考にしました： ネピア数eに関連したいろいろな数列の極限値を求めてみよう - 身勝手な主張 )

(1) lim_{n\rightarrow-\infty}\left(1+\dfrac{1}{n}\right)^n = eが成り立つ。
(2) lim_{n\rightarrow\infty}\left(1-\dfrac{1}{n}\right)^n = lim_{-n\rightarrow-\infty}\left\{\left(1+\dfrac{1}{-n}\right)^{-n}\right\}^{-1} = e^{-1}

(1)の証明： x = -nとする。 lim_{n\rightarrow-\infty}\left(1+\dfrac{1}{n}\right)^n = lim_{x\rightarrow\infty}\left(1-\dfrac{1}{x}\right)^{-x} = lim_{x\rightarrow\infty}\left(\dfrac{x-1}{x}\right)^{-x} = lim_{x\rightarrow\infty}\left(\dfrac{x}{x-1}\right)^{x} = lim_{x\rightarrow\infty}\left(\dfrac{x}{x-1}\right)^{x-1}\left(\dfrac{x}{x-1}\right) = lim_{x\rightarrow\infty}\left(1+\dfrac{1}{x-1}\right)^{x-1}\left(\dfrac{x}{x-1}\right) = e \times 1 = e

ブートストラップ法の気持ち

次に、ブートストラップ法の気持ちを考えてみたい。
なにをやっているのかは本文を読めば分かるのだが、なぜそれをバイアスの推定値として使うのかが全く説明されておらず、ちんぷんかんぷんである。

なので以下で気持ちを妄想していく。
まず、整理をしてみる。

バイアスの理論値(真の誤り率-再代入誤り率)：
bias = \varepsilon(p, p) - \varepsilon(N, N)

バイアスの推定値：
\hat{bias} = \varepsilon(N^*, N^*) - \varepsilon(N^*, N)

バイアスの推定値の平均： \bar{bias}

バイアスの理論値と推定値を比較してみると、 \varepsilon(N^*, N^*)を \varepsilon(p, p)と同じものとみなしているお気持ちが見えてくる。もちろん \varepsilon(N^*, N^*)は \varepsilon(p, p)とは違うものなので、その差異を抑えるために、N回抽出する作業を何回も行って複数の \varepsilon(p, p)を得て、その平均を取るのだろう。

もとのデータセットNが例えば無限大のデータ数だとするとこれは真の分布となり、Nから無限回データを復元抽出してその抽出データで算出する誤り率は真の誤り率 \varepsilon(p, p)と同じである（同じだよね？）。ブートストラップ法はNが大きいことを仮定しないといけなそうだ。

一方の \varepsilon(N^*, N)だが、真のバイアスの方と比較すると、 N^*と Nを同一視しているように見えてくる。 Nから抽出したものなのだから N^*は Nと同じとみなすということなのだろうか。

atcoder ABC122 参加記

ブログ始めます。

Qiitaにも記事を１つ書いたんだけど、ミスがありそうで怖くて未公開。

ブログなら気楽にかけそうだしいいかな、と。

超今更ながらABC122の感想。

感想なので解説を期待している方はブラウザバック推奨

全体の感想

3完でパフォ1034。灰色勢としてかつてない出来！
そして茶色になった。

初めて難しめ（？）のC問題を解けた。精進の結果が初めて出たので割と嬉しい。これが競プロの醍醐味なんだろうけど、ここに至るまでがなかなか辛くて敷居が高いなと思ってしまったり。

Bで一度WA,　Cで一度TLEを出してペナルティを食らったのが悔やまれる。

A - Double Helix

愚直に解いてif文まみれに。解ければ何でもいいよね。Aだし（おい）。

ACコード(Python)

B - ATCoder

Bはいつもどおりな感じだったがテンパっててWAを出してしまい絶望。当方初心者でC以降を解けることがまだ少ない。 ２完勢とのスピード勝負でやばいと思った。

落ち着いてデバッガーで動きを見てみると、コーナーケース？（ACGTのみからなる文字列）でのバグを発見。 絶望した結果かえって落ち着いていた。すぐに直してAC。

ACコード(Python)

C - GeT AC

問題文はちゃんと読んだのに、変数の範囲105を見てなかった。 初回提出は無事TLE。萎えた。

質問は最大で105個ある。 １個１個の質問に対し最大105回探索する必要がある。計算量は1010くらいとなりどう考えても無理(たぶん)。 正確な計算量に関してはまだ初心者なので勘弁して下さい＾＾。

107~108くらいまでが行けるラインらしい。

質問の個数に関してはアルゴリズムではどうしようもないので、無視。 問題は探索である。質問の各ループ中にO(logN)かO(1)の計算量（本当か？）で'AC'が何個かを探索をしないといけない。

各質問では被る範囲があるからまずはそこに目をつけてみる。 →うまくいかない。

次に、２重for文の中から内側のfor文を外部に取り出すことを考えてみる。 どういうことかと言うと、1からQまでの各質問のforループの中にある探索部分のforループを、外に出したいということ。

for(int i=0; i<Q; ++i){
    for(int j=0; j<N; ++i){
    
    }
}

つまり、上のこれを下のようにする。

for(int j=0; j<N; ++i){

}

for(int i=0; i<Q; ++i){

}

そうすれば、当たり前だが２重for文は１重for文になり、計算量の問題はなくなる。 こういう考え方はわりと典型だと思う。 いもす法もこういう形（本当か？）。

最初に、文字列S全体に関し'AC'を探し、場所を配列等に記録していく。 その配列をつかってO(1)で各質問内において'AC'の数を探索出来ないだろうか。 考えてみる。→累積和じゃん！！

これは感想だし他にも解説あるだろうしで累積和については飛ばします。

というか、累積和のこの使い方でもまあまあむずいのに、今回の問題は累積和を使うに至るまでが難しすぎる。 これ本当にC問題妥当なんだろうか。 今回は運良く思いついたけど、次もそうなるとは限らない。 C問題まじで恐ろしい・・・。

速度に不安があったので一応PyPyで提出。

ACコード(PyPy3)

D - We Like AGC

問題文見てどうみてもDPだろと決めつけて（適当）、最終的には4次元DPにたどり着いた。 解説放送で4次元DP使ってたから多分想定解もそうなのかな？

自分がやろうとした4次元DPはこんな感じ。

dp[ i ][ j ][ k ][ l ]
i:一個前の文字
j:現在の文字
k:一文字目からスタートした場合の現在の文字数
l:条件を満たす文字列かどうか（1か0か）

 

    そして、科学の叡智が集積したこの特異点にて遂に――、                                                        4次元ゴミが爆誕した。

    ~fin~

 

冗談はともかく、もちろん見当はずれだった。 しばらく体調崩しててACコードまだ書いてない。すぐに書かないと。

4次元ゴミ(C++)