Project Euler 0001-0010

今年末で某の一次試験が終わるとすると（終わると信じたい）、
いよいよ普段の生活で数学っぽい活動が殆ど無くなってしまうことになる。
 
このまま数学の力が落ちていってしまうのも勿体無いので、

今後は趣味として"Project Euler"をゆっくり進めていくことにする。
（いつまで興味が続くかは不明）

projecteuler.net

Project Eulerとは、一言で表せば数学クイズで競うサイトである。
特に、プログラミングを上手く用いると解ける問題が多いようである。

例えば、

Problem 10 - Project Euler

2,000,000以下の全ての素数の和を求めよ。

といった具合である。

最初の方は高校数学の範囲で解けたり、愚直に計算するだけであったりとごく簡単であるが、
番号が進むにつれてかなり難しくなっていくようである。
（statisticsから確認できる情報だと、最新の数問はいずれも世界で数百人にしか解かれていない。）

 

AtCoderなどの競技プログラミングとは異なり、特に時間制限などは無いため、遊びだと思ってやる気の湧いたときにゆっくり進めていこうと思う。

 

進捗：0001-0010 まで完了
 
問題を解く上では今の所手が止まることはなかった。


f:id:tennismonkey01:20200919221942p:plain


●エラトステネスの篩

N以下の素数を列挙する関数として、pythonでエラトステネスの篩を作ったのだが、動作が少し遅く感じた。

#n以下の素数
def prime_under_(n):
    num_ls = [i for i in range(2,n+1)]
    prime_ls =[]
    item = num_ls[0]
    while item < int(np.sqrt(n))+1:
        prime_ls.append(item)
        num_ls = [i for i in num_ls if i % item !=0]
        item = num_ls[0]
    return prime_ls + num_ls

%%time
prime_under_(1000000)

CPU times: user 2.4 s, sys: 159 ms, total: 2.56 s
Wall time: 2.62 s





numpyで置き換えることで、以下の通り高速化することができた。

def np_prime_under_(n):
    is_prime = np.ones(n).astype(int)
    is_prime[:2]=0
    for j in range(2,int(np.sqrt(n)+1)):
        if(is_prime[j]):
            is_prime[j*j::j] = 0
    ans_ls = np.arange(n)[is_prime]*np.array(list(range(n)))
    return list(ans_ls.nonzero()[0])

%%time
np_prime_under_(1000000)

CPU times: user 147 ms, sys: 29.8 ms, total: 176 ms
Wall time: 179 ms


また調べたところ、sympyというライブラリを使えばそのまま出せるようであった。

import sympy

%%time
ans_ls = [i for i in sympy.primerange(2, 1000000)]

CPU times: user 3.32 s, sys: 34.9 ms, total: 3.36 s
Wall time: 3.49 s

sympyを用いた場合の速度としては、numpyを使わない場合と同程度となった。

  • pythonの計算で速度が求められる場合には、上手くnumpyを活用することが大事であるということを再確認できた。
  • ライブラリを読み込んだとしても、numpyを使って自分で書いた方が動作が速い場合もある。

期待値E(X)の累積分布関数による表示

 

損保数理8~10章で度々証明なしに利用されている以下の命題について考える。

命題：指数型分布族に従う確率変数Xの期待値E(X)はXの累積分布関数F(x)=P(X \leq x)で
E(X) = \int_{0}^{\infty}(1-F(x))dx - \int_{-\infty}^{0}F(x)dx
と表せる。
証明：X^{+} := \max \{ X,0 \}、 X^{-} := \min \{ X,0 \}とすると、
　　E(X) = \int_{\Omega}XdP
　　　　　=\int_{\Omega}(X^{+}(\omega)+X^{-}(\omega))dP(\omega)
　　　　　=\int_{\Omega}\int_{0}^{X^{+}(\omega)}1dydP(\omega)-\int_{\Omega}\int_{X^{-}(\omega)}^{0}1dydP(\omega)
　　　　　=\int_{\Omega}\int_{0}^{\infty}1_{ \{ y \lt X^{+}(\omega)\} }dydP(\omega) -\int_{\Omega}\int_{-\infty}^{0}1_{ \{ y \gt X^{-}(\omega) \} }dydP(\omega)
　　　　　=\int_{0}^{\infty}(\int_{\Omega}1_{ \{ y \lt X^{+}(\omega)\} }dP(\omega))dy - \int_{-\infty}^{0}(\int_{\Omega}1_{ \{ y \gt X^{-}(\omega) \} }dP(\omega))dy （フビニの定理）
　　　　　=\int_{0}^{\infty}P(X^{+} \gt y)dy - \int_{-\infty}^{0}P(X^{-} \lt y)dy
　　　　　=\int_{0}^{\infty}(1-F(y))dy - \int_{-\infty}^{0}F(y)dy
　　　で、 yを xに取り替えればいえる。　（証明終）
 
特に、Xが非負ならば次のようにできる。
系：指数型分布族に従う非負の確率変数Xの期待値E(X)は累積分布関数F(x)で 
E(X) = \int_{0}^{\infty}(1-F(x))dx
と表せる。
 
指数型分布族ではない分布の場合、必ずしも成り立たないので注意が必要である。
 
こちらのサイトは初等的な分布について各パラメータを既知・未知としたときに指数型分布族となるかどうかが記されている。
 
 
 

統計・データ分析おすすめ本

その他

 

ここ1年は確率・統計・データ解析を中心に勉強してきた。この分野は近年のブームもあり新しい本がどんどん出ていて、勉強を始めた頃は参考書選びやどういう順番で勉強したら良いか分からず苦労した。そこで今回は、今までに触れた確率・統計・データ解析系の入門書で、実際に読んだ中から個人的に良かったと思ったものをまとめていきたいと思う*1。

 

 

教養基礎統計、統計学(初級)〜

統計学入門 (基礎統計学?)

統計学入門 (基礎統計学?)

 

東大出版の有名な基礎統計の教科書である。

スタイルとしてはカジュアルな本と数学書の中間程度で、内容は確率分布や記述統計、推定量、検定、回帰あたりの基礎をコンパクトに、しかし最低限必要な部分は一通り漏らさず書いてある。例データや章末問題、内容の説明や話の流れも全体的に質が高く、独学でも無理なく読み進められる。また、入門書でありがちな「本の最後の方は発展的な内容の雑なまとめ・紹介」といったこともなく、最初から最後まで重要事項の説明に終始している。

大学1年生など、大学以上の参考書をあまり読んだことがないという人だとひょっとすると読み進めるのに苦労するかもしれないが、統計に少しでも関わることを勉強したいならば読んでみる価値は間違いなくあると思う。あえて欠点を挙げるとするならば、確率変数の変数変換の所は初学者だとこの本の説明では少し理解しづらいかもしれない。

類書として、*2等がある。

  

  •  明解演習 数理統計

統計学(初級)〜

明解演習 数理統計 (明解演習シリーズ)

明解演習 数理統計 (明解演習シリーズ)

 

代表的な統計学の入門の演習書である。

内容としてはおおよそ上の「統計学入門」に対応している。「統計学入門」を一通り読むだけでは手薄になりがちな、確率変数、各種分布、各種統計量の扱いや区間推定、仮説検定について演習を通じ補って理解を深めることができる。

また、アクチュアリー試験の数学の科目も、上の「統計学入門」とこの本の二冊をこなせば基本的には対応できる。(なお、この二冊で対応できない範囲として、順序統計量、推定・検定の精密法、モデリング範囲等があるが、これらを別途補うことはそれほど大変ではない。*3 )

有効数字やいくつかの説明でおかしい所はあるものの、いずれも理解の妨げになることはない。

類書も*4等いくつかあるが、個人的にはこちらの方がおすすめである。

 

 

  • 現代数理統計学の基礎：久保川達也

 統計学(中級〜)

現代数理統計学の基礎 (共立講座 数学の魅力)

現代数理統計学の基礎 (共立講座 数学の魅力)

 

 出たばかりの新しい本であるが、*5、*6などと同様、「統計学入門」の次に読む2冊目以降の本としておすすめである。

特徴としては、これらの本よりも数学書のスタイルに近く、定義、命題、証明、、、といった流れで話が進んでいく。内容は自己完結的であって、また統計学の基礎的な話題の多くを抑えている。説明や例も読んでいて分かりやすい。また、後半では統計的決定理論やMCMC、確率過程の基本といった話題にも軽くではあるがわかりやすく触れている。

ある程度以上数学を勉強してきた人に対しては、2冊目の本としては現時点でこの本が一番おすすめ出来ると思う。

なお、更に数学方面に寄せた本として、*7や*8などもある。

 

 

測度論ありの確率論

確率論 (新しい解析学の流れ)

確率論 (新しい解析学の流れ)

 

ルベーグ積分、測度論を勉強したばかりの人をメインの対象に、スムーズに測度論を用いた確率論に移行できる橋渡し的な役割の本である。

第1章の50ページ弱に、確率の概念が測度論でどのように記述されるかから始まり、大数の弱法則、強法則、中心極限定理を中心に、各種の収束や確率論の基本的な命題についてコンパクトにまとまっている。証明も分かりやすく書かれていて、省略されている部分も多くは他の本を参照してあり遡れば分かるようになっている。また、付録として測度論の基礎がが本文と同じ記号でまとめられており、他の本と照らし合わせて復習する手間が省けて便利である。

標準的な内容の中では、π-λ定理、単調族定理が書かれておらず、その分Hopfの拡張定理周りについて詳しい。(これらについては、例えば*9の付録Aなどで補うことができる。)

  

 

  • Python機械学習プログラミング　達人データサイエンティストによる理論と実践

 機械学習、Python

[第2版]Python 機械学習プログラミング 達人データサイエンティストによる理論と実践 (impress top gear)

[第2版]Python 機械学習プログラミング 達人データサイエンティストによる理論と実践 (impress top gear)

 

 Pythonとそのパッケージを用いて機械学習の基本的な手法について学ぶことができる本である。

コンセプトとしては、基本的な機械学習アルゴリズムについて、理論的な側面よりは、各手法の特性や、実際にコンピュータ上で動かす手順に重点を置いて説明している。サンプルコードがPythonのパッケージ(sklearn,matplotlibら)によって豊富に用意されており、一通り動かしながら読むことですぐにでも自分でPythonによるデータ分析を実践し始めることができる。なお、サンプルコードを読むには、ある程度Pythonの基本的な文法知識が必要と思われる。

実践的なコンセプトの本とはいっても、学習不足と過学習との関係や、汎化性能、クロスバリデーション法など、重要な基礎概念についてはきちんと紙面を割いて説明されている。また、データの前処理や可視化についてもある程度触れられている。

第1版は回帰問題やにNNついてはほんの軽くしか書かれていないというものであったが、第2版では補われて改良されているようである。

じっくり仕組みを学ぶよりも先にまず実践から入りたいという人には、PRML*10やESL*11よりもこちらの方がおすすめできるだろう。

 

  

--------------------------------------

*1:2018年8月現在

*2:倉田博史、入門統計解析、新世社

*3:それぞれ、例えば順序統計量と精密法は 国沢清典,確率統計演習2 統計,培風館、モデリングは モデリング,日本アクチュアリー会 編 で補うことができる

*4:藤田岳彦、弱点克服大学生の確率・統計、東京図書

*5:稲垣宣生、数理統計学、裳華房

*6:竹村彰通、現代数理統計学、創文社

*7:吉田朋広、数理統計学、朝倉書店

*8:Rabi Bhattacharya et al. 、A Course in Mathmathecal Statistics and Large Sample Theory、Springer

*9:舟木直久、確率論、朝倉書店

*10:訳書：C.M. ビショップ、パターン認識と機械学習 上,下、丸善出版

*11:訳書：Trevor Hasite et al.、統計的機械学習の基礎、共立出版