MITの6.0002のIntroduction to Computational Thinking and Data Science、全15回の内容をoutputして行きます。
Youtube動画のplaylistはこちら
講義で使われていたスライドはこちらから入手できます。
講義内容
第1回、第2回 : 最適化問題
第3回 : グラフ理論
第4回 : 確率論
第5回 : ランダムウォーク
第6回 : モンテカルロシュミレーション
第7回 : 信頼区間
第8回 : 標本と標準誤差
第9回、第10回 : 実験データの理解
第11回 : 機械学習の紹介
第12回 : クラスタリング
第13回 : クラス分類
第14回 : 統計学の落とし穴
第15回 : まとめ
全体のまとめ
我々が生きている世界の問題の多くは、最適化問題、つまり最大値、最小値を見つける事として考えることができる。例えば、食料危機に関して、どのように食料を分配すれば、食品ロスが最小化でき、必要な量の食事を取れる人を最大化できるのか？
これまでの科学は実験室中心で行われていたが、それをコンピューターを使ってどのような事ができるのかを学ぶ。コンピューターを使ってシュミレーションを行うことで気候変動に関して予測したりすることができるようになる。
最初に、いろんな種類の最適化問題に対する解放が紹介されて、機械学習に進む前に知っておくべき知識を身につけることができる。例えば、ナップサック問題の解放、グラフ理論を使って最短距離を求める。
確率論では、一見、無意味なランダムな数値を使って、現実にある問題を解いていく手法なども紹介される。シュミレーションにおけるランダムの値の力を知ることができる。
サンプリング、最小2乗法、回帰(regression)、過学習(over fitting) などを、単純な問題に対して適応することで、数学的な式や原理が理解できる。
最後に、機械学習を用いて教師あり、なしモデルを作成する。交差検証を使ってモデルの評価手法を学習する。
全体を通して、pythonを使って実装しながら講義が進むので、Data分析の知識を身につけながら、pythonの勉強、英語の勉強もでき一石三鳥である。
最適化問題
最適化問題とは、ある制限の中で、価値を最大化したり、負荷を最小化する組み合わせを見つける事である。
例えば、泥棒がどれだけリュックサックに価値あるもの詰め込んで盗めるか、それを最大化するにはどうすればいいのか、ナップサック問題。
以下のように、20ℓのカバンに、金の延棒、宝石、パソコン、スマートフォンをどの組み合わせで入れれば、最大の価値を盗むことができるのか？
1ℓあたりの価値の高いものから詰め込んでいく手法を貪欲法という。この手法では、最適解が得られることもあるが、そうでないこともある。
今回の例では、1ℓあたりの価値が高いのはスマートフォンで、その次が金の延棒。この二つを入れると、20ℓになりこれ以上は入らないので、合計は13,000円になる。
最適解は得られないが、計算方法が単純で、ある程度の最適な値を見つけることができる。
一方で、全ての組み合わせを試す方法では、宝石、パソコン、スマートフォンの3つを入れる組み合わせが、価値が最大だとわかる。総当たりで調べると、最適解を見つけることができるが、全ての組み合わせの試すので時間がかかる。変数が増えると、指数関数的に計算量が増加していく。
ピボナッチ数列の計算
ピボナッチ数列は、１、１、２、３、５、８、１３、２１、３４、５５、８９、１４４、２３３、３７７… 「どの数字も前２つの数字を足した数字」という規則の数列
python で実装してみると、以下のような再帰的に関数を呼び出すのだが、これだと何度も同じ計算をすることになって効率が悪くなる。
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 2) + fib(n - 1)例えば、n=6の場合、fib(4), fib(3),fib(2) が何度も計算されてい非効率である。
それを解決するために、一度計算したものをメモしておくことで、効率化することができる。fib(4) = 3, fib(3) = 2 をメモしておくことで、同じ計算をすることを避けることで高速化する。
ナップサック問題のような最適化問題でも、組み合わせの計算結果をメモしておくことで、総当たりアルゴリズムでも計算量を抑えて高速に最適解を求めることが可能になる。
グラフ理論
多くの事がグラフで表現することができる。家系図であったり、ネットワークの構成、電車の乗り換え図など。
グラフを構成しているのもに、ノード(点)とEdeg(節)があり、Edgeは単方向であったり、双方向、重みが付いたりする。
最短経路を見つける問題で使われることが多い。決定木もグラフの一つである。
最短経路を見つける方法には、
1. 深さ優先探索(Depth First Search)
2. 幅優先探索(Breadth First Search)
がある。
深さ優先探索では、ノードをどんどん深くしながら探索する方法
例えば
A -> B,
A -> B -> G,
A -> B -> G -> F,
幅優先探索では、繋がっているノードを順番に探索する方法
A -> B,
A -> D,
A -> C,
A -> B-> G,
A -> D -> E,
A -> D -> F,
Comentários